超图学习综述__算法分类与应用分析-胡秉德，王新根，王新宇，宋明黎，陈纯.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software, 2022,33(2):498523 [doi: 10.13328/j.cnki.jos.006353] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
超图学习综述: 算法分类与应用分析
胡秉德
,
王新根
,
王新宇
,
宋明黎
,
陈
纯
(浙江大学 计算机科学与技术学院, 浙江 杭州 310007)
通信作者: 王新根, E-mail: newroot@zju.edu.cn
摘 要: 随着图结构化数据挖掘的兴起, 超图作为一种特殊的图结构化数据, 在社交网络分析、图像处理、生物
反应解析等领域受到广泛关注. 研究者通过解析超图中的拓扑结构与节点属性等信息, 能够有效解决实际应用场
景中所遇到的如兴趣推荐、社群划分等问题. 根据超图学习算法的设计特点, 将其划分为谱分析方法和神经网络
方法, 根据方法对超图处理的不同手段, 可进一步划分为展开式方法和非展开式方法. 若将展开式方法用于不可
分解超图, 则很有可能会造成信息损失. 然而, 现有的超图相关综述文章鲜有就超图学习方法适用于哪类超图这
一问题做出相关归纳. 因此, 分别从超图上的谱分析方法和神经网络方法两方面出发, 对展开式方法和非展开式
方法展开讨论, 并结合其算法特性和应用场景作进一步细分; 然后, 分析比较各类算法的设计思路, 结合实验结
果总结各类算法的优缺点; 最后, 对超图学习未来可能的研究方向进行了展望.
关键词: 超图学习; 谱分析; 神经网络; 展开; 非展开
中图法分类号: TP181
中文引用格式: 胡秉德, 王新根, 王新宇, 宋明黎, 陈纯. 超图学习综述: 算法分类与应用分析. 软件学报, 2022,33(2):
498–523. http://www.jos.org.cn/1000-9825/6353.htm
英文引用格式: Hu BD, Wang XG, Wang XY, Song ML, Chen C. Survey on Hypergraph Learning: Algorithm Classification and
Application Analysis. Ruan Jian Xue Bao/Journal of Software, 2022, 33(2): 498523 (in Chinese). http://www.jos.org.cn/1000-9825/
6353.htm
Survey on Hypergraph Learni ng: Algorithm Classific ation and Application Analysis
HU Bing-De, WANG Xin-Gen, WANG Xin-Yu, SONG Ming-Li, CHEN Chun
(College of Computer Science and Technology, Zhejiang University, Hangzhou 310007, China)
Abstra ct : With the rise of graph structured data mining, hypergraph, as a special type of graph structured data, is widely concerned in
social network analysis, image processing, biological response analysis, and other fields. By analyzing the topological structure and node
attributes of hypergraph, many problemscan be effectively solved such as recommendation, community detection, and so on. According to
the characteristics of hypergraph learning algorithm, it can be divided into spectral analysis method, neural network method, and other
method. According to the methods used to process hypergraphs, it can be further divided into expansion method and non-expansion
method. If the expansion method is applied to the indecomposable hypergraph, it is likely to cause information loss. However, the existing
hypergraph reviews do not discuss that hypergraph learning methods are applicable to which type of hypergraphs. So, this article discusses
the expansion method and non-expansion method respectively from the aspects of spectral analysis method and neural network method,
and further subdivides them according to their algorithm characteristics and application scenarios. Then, the ideas of different algorithms
are analyzed and comparedin experiments. The advantages and disadvantages of different algorithms are concluded. Finally, some
promising research directionsare proposed.
Key words: hypergraph learning; spectral analysis; neural network; expansion; non-expansion
图(graph)作为一种高效的关系表达结构, 被广泛地应用于成对关系的建模中, 例如对论文引用关系、私人
基金项目: 广东省重点领域研发计划(2020B0101100005); 浙江省重点研发计划(2021C01014)
收稿时间: 2020-08-07; 修改时间: 2020-09-30; 采用时间: 2021-04-17; jos 在线出版时间: 2021-05-20
胡秉德 等: 超图学习综述: 算法分类与应用分析
499
社交、蛋白质交互反应等网络的建模. 然而除了成对关系外, 在很多场景中还存在大量一般简单图结构难以
表达的非成对关系, 例如社交网络中存在的社区结构、特征关系中的簇结构等. 在这些场景中, 研究者很难甚
至无法区分各类结构内部样本与样本之间的交互关系. 而超图具有的一条边内包含任意个数节点的特性, 使
其对于这种数据关系的表达有着天然的优势. 具体来说, 超图(hypergraph)是一类一条边可以包含任意节点数
量的图结构, 其形式化表达如下: 超图 H=(X,E), 其中, X 是一组称为节点的元素, E 是一组 X 的非空子集, 称
为超边或边
[1]
. 图 1 即为一个简单的超图样例.
图 1 超图样例
[1]
事实上, 学术界一直都在进行超图的相关研究, 但早期的研究焦点主要在传统图论问题上
[24]
. 随着超图
理论的快速发展, 一些更为广泛的应用性问题才在超图上被有针对性地加以研究, 并逐步成为研究热点, 例
如图节点分类问题
[5]
、图节点重要性排序问题
[6]
以及一些图像处理任务
[7,8]
. 而近年来, 神经网络研究的突飞猛
进, 又使得超图学习有了新的研究方向. 研究者利用神经网络超强的学习能力以及模型本身的灵活性, 对超
图的高阶交互关系
[9]
、动态超图
[10]
以及不可分解超图
[11]
等问题的研究正在逐步展开.
从方法层面来看, 谱分析方法作为一直以来图学习的传统主流方法, 在超图学习上也占据着主导地位.
在神经网络被引入到超图学习领域之前, 大部分研究都是建立在谱理论之上的. 但是随着神经网络被引入到
超图学习领域, 一系列将传统成对图网络上的学习算法推广到超图上的研究成果被研究者提了出来
[1214]
. 超
图学习首次被作为一种在超图结构上的传播过程是在 Zhou 等人的工作
[12]
中被提出来的, Zhou 等人使用的就
是在超图上的谱分析方法. 这类方法通常具有满足严密数理推导的解析过程, 但也正因为如此, 这类方法有
很多的局限性.
与此同时, 神经网络的出现为超图学习研究注入了新的活力. 如何将神经网络结构用于超图学习, 成为
了一个新的研究热点. 近年来也有很多这方面的优秀工作被先后提出, 其中, 代表性工作 hyperedge based
embedding (HEBE)
[15]
方法希望通过超图来为每个事件中涉及的对象学习一个表征的思路为后续的神经网络
方法带来了启发. Tu 等人
[11]
证明了 HEBE 方法在稀疏超图下的表现并不理想, 并提出了 deep hyper-network
embedding (DHNE)模型. 然而, DHNE 方法直接使用多层感知机对元组关系进行建模, 使其只能应用于均匀
超图(所有超边所包含的顶点数相同的图), 将 DHNE 应用于非均匀异构超图会消耗大量的计算资源, 并损失
模型的泛化能力. 面对上述挑战, Zhang 等人
[16]
提出了 Hyper-SAGNN, 通过引入自注意力机制达到对非均匀
异构超图进行学习挖掘的目的.
然而上述提到的文章在考虑超图各类特性的同时大多忽视了一个潜在的问题,就是超图的可分解性. 图
展开是超图分析的一类经典方法, 即把超边展开成普通边, 具体的又分为团式展开
[5]
、星式展开
[9]
、采样式展
开
[17]
等. 但展开式方法需要建立在超图可分解的前提下, 即任意超边的子集能够组成超边. 针对不可分解超
图, Tu 等人
[11]
提出了 DHNE 模型, 并从理论上证明: 现有方法中, 任何线性相似性度量在常用的嵌入空间中
都无法维持超图网络的不可分解性. 因此, 针对模型算法的分解特性, 本文将对现有的超图学习方法进行
梳理.
本文第 1 节介绍超图学习的研究背景并提出超图学习方法的基本分类. 第 2 节对超图学习相关概念及定
义进行具体说明. 第 3 节对不同类别的超图学习方法进行归纳和比较. 第 4 节对超图学习的具体应用领域进
行说明, 分析超图学习的重要意义. 第 5 节对具有代表性的超图学习算法进行实验比较与分析. 第 6 节与第 7
节对超图学习中未解决的问题和未来展望进行讨论并对本文进行总结.
of 26
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论