随着图结构化数据挖掘的兴起, 超图作为一种特殊的图结构化数据, 在社交网络分析、图像处理、生物反应解析等领域受到广泛关注. 研究者通过解析超图中的拓扑结构与节点属性等信息, 能够有效解决实际应用场景中所遇到的如兴趣推荐、社群划分等问题. 根据超图学习算法的设计特点, 将其划分为谱分析方法和神经网络方法, 根据方法对超图处理的不同手段, 可进一步划分为展开式方法和非展开式方法. 若将展开式方法用于不可分解超图, 则很有可能会造成信息损失. 然而, 现有的超图相关综述文章鲜有就超图学习方法适用于哪类超图这一问题做出相关归纳. 因此, 分别从超图上的谱分析方法和神经网络方法两方面出发, 对展开式方法和非展开式方法展开讨论, 并结合其算法特性和应用场景作进一步细分; 然后, 分析比较各类算法的设计思路, 结合实验结果总结各类算法的优缺点; 最后, 对超图学习未来可能的研究方向进行了展望.
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.
图(graph)作为一种高效的关系表达结构, 被广泛地应用于成对关系的建模中, 例如对论文引用关系、私人社交、蛋白质交互反应等网络的建模. 然而除了成对关系外, 在很多场景中还存在大量一般简单图结构难以表达的非成对关系, 例如社交网络中存在的社区结构、特征关系中的簇结构等. 在这些场景中, 研究者很难甚至无法区分各类结构内部样本与样本之间的交互关系. 而超图具有的一条边内包含任意个数节点的特性, 使其对于这种数据关系的表达有着天然的优势. 具体来说, 超图(hypergraph)是一类一条边可以包含任意节点数量的图结构, 其形式化表达如下: 超图
超图样例[
事实上, 学术界一直都在进行超图的相关研究, 但早期的研究焦点主要在传统图论问题上[
从方法层面来看, 谱分析方法作为一直以来图学习的传统主流方法, 在超图学习上也占据着主导地位. 在神经网络被引入到超图学习领域之前, 大部分研究都是建立在谱理论之上的. 但是随着神经网络被引入到超图学习领域, 一系列将传统成对图网络上的学习算法推广到超图上的研究成果被研究者提了出来[
与此同时, 神经网络的出现为超图学习研究注入了新的活力. 如何将神经网络结构用于超图学习, 成为了一个新的研究热点. 近年来也有很多这方面的优秀工作被先后提出, 其中, 代表性工作hyperedge based embedding (HEBE)[
然而上述提到的文章在考虑超图各类特性的同时大多忽视了一个潜在的问题, 就是超图的可分解性. 图展开是超图分析的一类经典方法, 即把超边展开成普通边, 具体的又分为团式展开[
本文第1节介绍超图学习的研究背景并提出超图学习方法的基本分类. 第2节对超图学习相关概念及定义进行具体说明. 第3节对不同类别的超图学习方法进行归纳和比较. 第4节对超图学习的具体应用领域进行说明, 分析超图学习的重要意义. 第5节对具有代表性的超图学习算法进行实验比较与分析. 第6节与第7节对超图学习中未解决的问题和未来展望进行讨论并对本文进行总结.
超图结构是一种比传统成对关系图更加泛化的关系类型. 在过去的几十年间, 超图理论已被证明能够有效解决众多真实世界问题. 超图强大的表达能力, 使其能够很好地对各类网络、数据结构、进程调度以及一些对象关系复杂的系统进行高效建模. 从理论上来看, 超图可以归纳普通图上的某些定理, 甚至可以用一个超图定理代替传统图上的几个定理. 例如, Berge的弱完全图猜想(一个图是完美的当且仅当它的补图是完美的)就是使用超图概念进行证明的[
超图研究早在2000年以前就已被众多学者所关注. 超图理论最早是由Berge[
随着时间的推进, 超图学习的研究方向不再局限于传统图论问题, 超图上的聚类[
随着近年来图结构数据数据量的爆炸式增长以及神经网络模型的快速衍变, 对于异构、高阶、非均匀超图的挖掘学习成为了新的研究热点. 2016年, Huan等人[
超图学习方法种类繁多, 但根据超图学习方法自身特点和所适用的超图结构特点, 超图学习方法可分为:
● 谱分析超图学习方法: 以超图拉普拉斯矩阵为核心的一类矩阵分析方法, 通常具有满足严密数理推导的目标函数最优解求解过程. 同时, 相关的理论基础对很多算法模型的设计有着重要的指导意义. 这类方法因为理论限制, 通常泛化性较差, 能够适用的超图结构有限. 并且, 该类超图谱分析方法通过矩阵分解的方式求解, 无法直接应用于大规模超图挖掘场景;
● 神经网络超图学习方法: 以人工神经网络及其衍生结构为模型主体结构的超图学习方法. 这类方法通常学习能力强、结构设计灵活且泛化性高, 很好地弥补了谱分析类方法的缺陷. 将神经网络用于超图学习, 成为近年来一个新的研究热点;
● 其他方法: 在超图学习场景中还有一些既不像谱分析方法那样具有严格的解析解, 同时也不具备神经网络结构的机器学习方法. 这类方法通常在特定的应用场景下结合场景特点定义模型目标, 并通过相应的优化方法求解. 由于相关方法场景特异性强, 本文只给出简要说明.
在谱分析超图学习方法和神经网络超图学习方法中, 又可进一步地划分为:
● 展开式超图学习方法: 展开式超图学习方法针对于可分解超图, 这一类方法将会对超图进行拆解, 从而将超图转化为传统成对图网络. 因此, 这类方法需要超图结构具备可分解性. 这类超图学习方法的普适性较强, 但在对超图进行拆解的同时, 容易造成信息损失;
● 非展开式超图学习方法: 非展开式超图学习方法针对于不可分解超图, 这类方法无需对超图进行拆解, 而是直接对超图结构进行建模. 在不可分解超图中, 超边中的点通常具有很强的关联性, 而其超边中节点的子集则没有这种强关联性. 例如, 在推荐系统中, 用户、电影、标签三者形成的超边, 用户和标签之间通常就不存在强关联[
● 超图结构
超图
紧接着上述定义, 超图的邻接矩阵
● 拉普拉斯矩阵
拉普拉斯矩阵通常用于图的矩阵化表示, 可用于发现许多图的有用性质. 传统成对关系图的拉普拉斯矩阵通常定义为
其中,
● 展开
将超图转化为传统成对图网络的过程, 团式展开[
● 异构超图
传统超图结构中, 节点与边的种类只有一种; 而异构超图中, 节点或边的种类在两种以上(目前公开的异构超图数据集中大多为节点异构类型).
● 不可分解超图
不可分解超图通常是异构超图, 这类超图中, 同一超边上的节点有较强的关联关系, 但超边子集中的节点则很可能缺少强关联. 例如, 推荐系统中, 用户、电影、标签形成的三元组能够有效反映用户对电影的评价三者间有强关联关系, 但用户和标签所形成的子集则关联关系较弱[
● 结构属性
结构属性是网络结构中最为重要的信息, 通过结构属性, 我们可以构建网络节点之间的拓扑关系. 有效捕捉这种拓扑关系, 是很多图学习方法的研究动机. 结构属性可分为局部结构和全局结构[
● 其他属性
除了超图中的拓扑结构信息以外, 超图中还含有其他有价值的数据信息, 如节点的属性信息、边的属性信息等. 将这些拓扑结构信息以外的信息引入到模型中, 可以让模型从更多的角度去挖掘超图上的潜在相似关系.
随着图结构化数据挖掘的兴起, 超图作为一种特殊的图结构化数据, 也受到研究者广泛研究. 本文采用层次化的分类方法对超图学习方法进行分类, 首先将超图学习方法分为谱分析方法、神经网络方法以及其他方法, 再进一步根据方法建模思路的不同将其分为展开式方法和非展开式方法, 具体分类以及代表模型如
超图模型分类
超图上的谱分析方法是超图学习的传统主流方法, 它是一类以谱理论为基础的矩阵分析方法. 这类方法通常具有满足严密数理推导的目标函数最优解求解过程, 相关的理论基础对很多算法模型的设计有着重要的指导意义. 近年来炙手可热的graph convolutional network (GCN)[
超图上的展开式谱分析方法一般通过将超图转化成传统成对图网络的方式, 将超图学习问题简化成传统成对图网络学习问题, 再根据拉普拉斯矩阵的谱特性求解. 这类方法大多在同构超图上展开研究.
(1) 星式展开和团式展开
星式展开(SE)和团式展开(CE)[
星式展开算法为每个超图
其中,
其中,
其中,
星式展开和团式展开
团式展开算法[
其中,
其中,
有了展开图的标准拉普拉斯矩阵后, 将其带入最小二乘目标函数[
两种展开方式的不同点在于: 团式展开中, 同一条超边的节点直接相连具有明确的相似性; 而星式展开中, 同一条超边内节点则是通过超边节点间接相连, 具有隐性相似性. 相同点在于, 两种展开方式都是一个将超图转化为成对图的过程. 在
在标准星式展开和团式展开的影响下, 一些以它们为基础的变体展开方式被提了出来.
Yu等人[
其中,
Rodriguez’s Laplacian(RL)[
其中,
类似地, Agarwal等人[
实际上, 上述几种变体的不同主要集中在展开后超图的权重分配函数上, 权重分配函数不同, 将会直接影响拉普拉斯矩阵的构建结果. 类似的研究还有很多[
(2) 采样展开
星式展开和团式展开虽然有效, 但其缺点也非常明显: 展开图的边数量远高于原图. 因此, 这些方法在高阶超图中难以应用. 针对这一问题, 一些基于采样的展开方式被提了出来[
Louis[
Chan等人[
与展开式方法不同, 非展开式谱分析方法直接对超图进行建模, 即直接构建超图上的拉普拉斯矩阵, 这一建模过程保证了超图信息的完整性.
文章共同作者[
Carletti等人[
Bolla’s Laplacian方法[
其中,
随后, Zhou等人[
根据标准线性代数理论, 超图最小切割问题的解即为拉普拉斯矩阵
Huang等人[
此外, 在谱分析方法中还有一类超图随机游走算法. 这类算法是以随机游走算法为基础的一类谱分析方法. Huang等人[
其中,
近来, Carletti等人[
谱分析相关算法的对比总结见
谱分析方法总结
算法名称 | 展开方式 | 权重分配 | 拉普拉斯矩阵 | 超图类型 | 是否展开 | 优势 | 劣势 |
SE | SE | 有权同构 | 是 | 能够有效将超图转化成普通图处理 | 同一超边上的点为隐式关联 | ||
CE | CE | 有权同构 | 是 | 能够有效将超图转化成普通图处理 | 展开后会造成数量的膨胀 | ||
HCIS | CE | 有权同构 | 是 | 有效分析高阶模块的交互关系 | 本质上是团式展开, 因而仍存在展开后边的膨胀问题 | ||
RL | CE | 无权同构 | 是 | 为无权超图定义了拉普拉斯矩阵并证明其有效性 | 本质上是团式展开, 因而仍存在展开后边的膨胀问题 | ||
CA | CE | - | 有权同构 | 是 | 保证了超图展开前后权重的一致, 使得权重分配函数更加合理 | 权重分配函数的拟合增加了额外的计算开销 | |
BKR | BKR | 有权同构 | 是 | 大大降低了展开后节点和边的数量, 降低了后续计算的消耗 | 放弃了过多的中间节点, 丢了较多中间信息 | ||
Mediator | Mediator | 有权同构 | 是 | 降低了展开后边的数量, 且保留了大部分的中间信息 | 作为一种采样展开方式, 仍会有一定的信息损失 | ||
Bolla | - | - | 无权同构 | 否 | 能够有效解决无权图上的最小切割问题 | 只可应用于无权图, 迁移应用性较差, 且只可应用于连通图 | |
Zhou | - | - | 有权同构 | 否 | 解决了有权图上的最小切割问题, 具有较强的迁移性, 被众多工作所借鉴 | 超图结构中存在孤立节点时, 拉普拉斯算子将失效 | |
Hyper2vec | - | - | 有权同构 | 否 | 导向函数使得方法能够更好地保留网络的结构和固有属性 | 导向函数为分段函数较为简单 | |
RWH | - | - | 无权同构 | 否 | 模拟了微观物理学多体近邻更易交换的特性, 对高阶超边变化敏感 | 仅可应用于无权超图 |
近年来, 随着神经网络研究的逐渐深入, 研究者将神经网络方法引入到了各个研究领域, 其中就包括了超图学习. 谱分析类方法的优点在于其方法本身拥有较强的数理可解释性, 但也正因如此, 谱分析类方法的灵活性较差, 很多方法适用的超图场景十分有限. 此外, 由于谱分析类方法的求解特性, 很多谱分析方法往往无法直接应用于大规模超图挖掘场景. 而神经网络算法的出现, 则很好地弥补了这些缺陷. 本节将对超图上的神经网络方法进行展开讨论.
Feng等人[
其中,
超边卷积层图示[
实际上, 上述图卷积计算过程就是在模拟前文提到的星式展开过程的一个神经网络推广,
受HGNN模型的启发, Ji等人[
JHConv的计算过程通过在卷积过程中额外引入上一层的表征结果
Yi等人[
Yadati等人[
超图拉普拉斯算子和带中介的超图拉普拉斯算子[
Yang等人[
线式展开[
在图
其中,
(1) 基于自编码器的方法
Tu等人[
(2) 基于自注意力机制的方法
针对DHNE方法仅限于处理固定类型和固定大小的异构超边这一问题, Zhang等人[
其中,
(3) 基于卷积的方法
类似地, Bai等人[
注意力机制[
其中,
非展开式超图神经网络还被引入到了流形学习中, Jin等人[
其中, 前项是
超图构建过程示例[
与上述工作不同的是, Jiang等人[
神经网络相关算法的对比总结见
超图神经网络方法总结
算法名称 | 主要结构 | 展开方式 | 输入 | 超图类型 | 是否展开 | 优势 | 劣势 |
HGNN | 基于谱的图卷积网络 | Star expansion | 节点特征、邻接矩阵 | 同构有权 | 是 | 能够对超图的结构属性信息和节点特征信息进行更好的融合 | 该卷积计算的拉普拉斯算子在超图结构存在孤立点时会失效 |
DHCF | 基于谱的图卷积网络 | Star expansion | 节点特征、邻接矩阵 | 异构无权 | 是 | 双通道超图协同过滤在对不同对象关系进行学习的同时, 保证了不同对象自身的表征特性 | 模型仅通过共享权重的方式来构建不同对象之间的关联关系, 使得不同对象之间的联系完全依赖于数据质量, 这将难以应对噪声数据 |
HGC- RNN | 基于谱的图卷积网络、循环神经网络 | Star expansion | 节点特征、邻接矩阵 | 同构无权 | 是 | 与现有基于GNN的结构化时间序列模型相比, HGC-RNN所涉及的参数更少, 对于复杂网络具有更好的鲁棒性 | 该方法只适用于无权时序超图 |
Hyper- GCN | 基于谱的图卷积网络 | Mediator | 节点特征、邻接矩阵 | 同构有权 | 是 | 采样过程一定程度上过滤了可能存在的数据噪声 | 可能会忽略掉一些有效信息, 且需要更多的迭代次数才能够收敛 |
LE | 基于谱的图卷积网络 | LE | 节点特征、邻接矩阵 | 同构有权 | 是 | 展开方式保留了原始超图数据的共现性 | 展开后的结构为非常见结构, 需要特殊处理 |
DHNE | 自编码器、注意力机制 | - | 超边元组 | 异构无权 | 否 | 适用于异构超图且能够保留节点的一阶、二阶信息 | 只适用均匀超图, 很难扩展到任意规模超图上 |
Hyper- SAGNN | 注意力机制 | - | 超边元组 | 异构无权 | 否 | 模型输入的元组节点可为任意类型, 与DHNE相比具有更好的泛化性 | 模型计算复杂度较高 |
AM | 注意力机制、基于谱的卷积网络 | - | 节点特征、邻接矩阵 | 同构有权 | 否 | 使图卷积神经网络获得了可学习的注意力机制 | 需要保证节点与超边的相似度之间存在可比性的前提下 |
H-CMN | 基于谱的卷积网络 | - | 节点特征、邻接矩阵 | 同构无权 | 否 | 能够实现大规模数据集的训练, 且模型对于数据中的噪声有更好的鲁棒性 | 重建过程存在随机性, 可能丢失信息 |
DHGNN | 基于谱的卷积网络 | - | 节点特征、邻接矩阵 | 同构无权 | 否 | 能够不断地重构超图结构来适应原始数据中隐藏的节点关系 | 训练效率较低, 无法应用于大规模超图网络 |
除了上述两类超图学习方法外, 在超图学习场景中, 还有一些既不像谱分析方法那样具有严格的解析解, 同时也不具备神经网络结构的机器学习方法. 这类方法通常在特定的应用场景下, 结合场景特点定义模型目标, 并通过相应的优化方法求解.
HEBE[
其中,
Du等人[
类似地, 近来, Wen等人[
其中,
Su等人[
Lin等人[
Lee等人[
对于上述方法的总结介绍, 再次说明了超图结构普遍存在于真实世界中, 对于超图学习方法的研究具有普适的现实意义.
超图学习作为一种能够有效挖掘超图信息的手段, 被广泛应用于图像处理任务[
超图分割[
George等人[
网络聚类是指将网络顶点划分为一组簇的任务, 使得同一簇中的顶点彼此紧密连接, 而不同簇之间连接较弱. 这样的集群结构广泛存在于生物信息学、计算机科学、物理学、社会学等众多网络系统中, 并具有重要意义.
实际上, 超图分割也能实现聚类的目的, 在很多超图聚类的研究工作中, 将超图分割算法也归类于聚类算法中[
除了上面提到的超图分割、聚类分析外, 节点分类也是超图学习方法的一大应用研究方向. 节点分类任务是建立在相似节点具有相似标签的假设前提下的一类任务. 大多数节点分类算法都是将有标签节点的数据分析结论推广到其他无标签数据上的一个过程, 这在超图中也不例外.
标签传播算法是一类非常经典的半监督图节点分类算法. 超图上的标签传播算法最早是由Zhou等人[
连接预测[
超图上的连接预测模型主要分为两类: 一类是以DHNE[
随着数据量爆炸式的增长, 节点重要性排序一直以来都是国内外研究的焦点, PageRank等算法也被各界广泛应用. 在大规模超图上如何定量分析节点的重要程度, 也是超图网络研究所需要解决的问题.
随机游走是一类高效的重要性排序算法, 超图上的随机游走可以追溯到Zhou等人[
电子商务在世界范围内规模不断扩大, 商品类目随之快速增长. 如何为顾客推荐想要的商品, 成为各大电商的难题, 为了解决这一问题, 推荐系统应运而生. 作为学术界与工业界联系最为紧密的应用方向之一, 研究者们对于推荐系统的研究层出不穷.
面对推荐的复杂场景, 很多研究工作提出使用超图对多元信息进行建模[
超图学习算法在视觉任务上也有广泛的应用. 在计算机视觉中, 超图用于描述视觉特征之间的关系, 例如视觉分类[
分子结构的图表示在计算化学中有着广泛的应用. 而传统图结构不能充分描述非经典结构的化合物, 不准确的分子图使得分子结构分析无法顺利进行. 为了解决这一问题, Konstantinova等人[
近来, Kajino[
在生物网络中, 节点通常描述蛋白质、代谢物、基因或其他生物实体, 而边缘代表节点之间的功能关系或相互作用, 如“结合”“催化”或“转化为”. 传统图的一个重要性质是每条边都连接两个节点, 然而许多生物过程的特点是有两个以上的参与伙伴. 用传统图常常无法恰当表达这些生物过程, 而超图提供了一个框架能够有效解决这一问题.
近来, Tsuyuzaki[
本节将针对超图上的节点分类任务和连接预测任务分别展开对比实验. 在节点分类任务中, 我们将对谱分析方法中提到的3种展开式方法star expansion[
为了对比上述方法, 实验数据除了经典网络引文数据Cora外, 实验使用
用于评估节点分类的数据集
数据集 | 节点数量 | 超边数量 | 平均超边尺寸 | 特征维度 | 类别数 |
ORL | 400 | 400 | 3 | 1 024 | 40 |
COIL20 | 1 440 | 1 440 | 3 | 1 024 | 20 |
Yeast | 1 484 | 1 484 | 3 | 7 | 10 |
Cora | 2 388 | 1 072 | 4.3 | 1 433 | 7 |
MINIST | 10 000 | 10 000 | 3 | 784 | 10 |
● ORL: 人脸数据库ORL包含了40个不同的主题, 每个主题有10幅不同的图像. 这些图像是在不同时间拍摄的, 因此在光线、表情、面部细节等方面存在不同. 这里, 我们使用
● COIL20[
● Yeast[
● Cora[
● MINIST[
对于连接预测实验, 我们使用的数据集信息如下(见
用于评估连接预测的数据集
数据集 | 节点数量 | 边数量 | 平均超边尺寸 |
GPS | 221 | 1 436 | 3 |
MovieLens | 17 100 | 47 957 | 3 |
drug | 7 486 | 171 756 | 3 |
● GPS[
● MovieLens[
● Drug[
在节点分类任务对比实验中, 我们将ORL、COIL20、Yeast、Cora、MINIST这5个数据集进行了随机划分, 50%的数据用于训练, 另外50%的数据用于测试, 以对比不同模型的节点分类准确率, 随机数种子设置为0. 在传统谱分析方法中, Zhou、Star expansion、Clique expansion这3种有权算法使用了LLRE[
在连接预测实验中, 本文将DHNE、Hyper-SAGNN这两种算法在GPS、MovieLens、Drug数据集上进行了对比实验, 分别使用了10%、20%、30%、40%、50%的超边信息进行训练, 其余用于测试.
本节对实验中的算法性能进行分析和对比. 以下图表中的结果均为错误率.
由
谱方法节点分类结果
Database | Zhou | Star-expansion | Clique-expansion | Bolla | Rodriguez | |||
COIL20 ( |
LLRE | 5.42±1.81 | LLRE | 5.62±2.01 | LLRE | 5.42±1.81 | 5.42±1.81 | 5.49±1.87 |
CENTROID | CENTROID | 5.62±2.01 | CENTROID | |||||
TRACE | 5.69±1.81 | TRACE | 5.83±1.94 | TRACE | 5.69±1.81 | |||
VOLUME | 5.62±1.6 | VOLUME | 5.56±1.81 | VOLUME | 5.62±1.6 | |||
ORL ( |
LLRE | 10.75±1.75 | LLRE | 13.75±1.75 | LLRE | 10.75±1.75 | 11.25±0.75 | |
CENTROID | 10.75±2.25 | CENTROID | 11.0±2.0 | CENTROID | 10.5±2.5 | |||
TRACE | 14.25±1.75 | TRACE | 14.5±1.5 | TRACE | 14.25±1.75 | |||
VOLUME | 13.25±1.25 | VOLUME | 14.75±1.75 | VOLUME | 13.5±1.5 | |||
MINIST ( |
LLRE | 15.34±0.16 | LLRE | 15.75±0.01 | LLRE | 14.94±0.16 | 14.82±0.04 | |
CENTROID | 15.26±0.18 | CENTROID | 15.65±0.5 | CENTROID | 14.94±0.22 | |||
TRACE | 18.44±0.18 | TRACE | 18.66±0.12 | TRACE | 18.49±0.19 | |||
VOLUME | 15.78±0.04 | VOLUME | 16.4±0.06 | VOLUME | 15.49±0.01 | |||
Yeast ( |
LLRE | 49.66±0.2 | LLRE | LLRE | 49.12±0.2 | 49.26±0.47 | 46.9±2.02 | |
CENTROID | 49.73±0.27 | CENTROID | 46.43±1.28 | CENTROID | 49.12±0.2 | |||
TRACE | 49.66±0.2 | TRACE | TRACE | 49.12±0.2 | ||||
VOLUME | 49.8±0.2 | VOLUME | 47.24±2.09 | VOLUME | 49.73±0.4 | |||
Cora | LLRE | LLRE | 40.45±0.75 | LLRE | 36.73±1.21 | 36.35±1.34 | 37.86±1.59 | |
CENTROID | 36.31±1.3 | CENTROID | 40.49±0.8 | CENTROID | 36.64±1.21 | |||
TRACE | 37.9±1.55 | TRACE | 41.83±1.13 | TRACE | 38.19±1.68 | |||
VOLUME | 38.23±1.13 | VOLUME | 39.24±1.38 | VOLUME | 38.07±1.21 |
神经网络的节点分类结果见
图神经网络方法节点分类结果
Database | HyperGCN | HGNN | Hyper-SAGNN | DHGNN |
COIL20( |
1.04±0.07 | 0.28±0 | 51.18±0.76 | 0.56±0 |
ORL( |
13±2.5 | 6.75±0.25 | 27.75±0.75 | 8.5±0.5 |
MINIST( |
5.37±0.17 | 4.63±0.07 | 40.6±0.71 | 5.54±0.02 |
Yeast( |
43.87±0.47 | 44.21±0.27 | 59.43±1.89 | 51.82±0.07 |
Cora | 17.47±0.8 | 16.88±0.12 | 45.06±0.75 | 19.35±0.17 |
上述9种方法的节点表征经过tsne算法降维后的可视化结果如
节点分类任务的节点嵌入结果
此外, 模型鲁棒性实验的结果如
不同百分比数据训练模型的结果
连接预测实验, 我们同样选取了10%、20%、30%、40%、50%的超边信息进行训练, 其余用于测试. 在
链接预测结果
durg连接预测结果
Method | Time (ms) | Erro rate (%) |
Hyper-SAGNN | 195 | 6.36 |
DHNE | 18 | 9.38 |
随着图结构研究的兴起, 作为一种可以对高阶关系进行建模的灵活数据结构, 超图结构近几年受到的关注也逐渐增多. 由于图卷积神经网络、图注意力机制、自编码器等神经网络结构的发展和成熟, 研究者对于超图的研究手段变得更加灵活、多变. 虽然超图学习算法应用于解决聚类、视觉等任务由来已久, 但大规模真实网络数据场景下超图学习算法的研究近来才被研究者所重视. 在大规模真实网络数据场景下, 超图学习算法面临着异构节点、非均匀超边以及模型鲁棒性等诸多问题的挑战. 针对目前超图学习算法的不足, 本节提出超图学习算法研究的几个潜在的研究方向.
(1) 有很大一部分超图学习算法只能处理均匀超图或同构超图, 这类算法显然无法在大规模真实网络数据场景下使用. 因为这类场景下通常有很多异构节点以及复杂的节点关系, 受超图本身复杂结构的影响(一条边包含多个节点), 上述问题将会变得更加棘手. 一些算法虽然可以处理异构超图, 但因模型复杂度过高因而不具备应用价值. 如何在保证模型性能的前提下处理超图中的异构节点和各类超边, 是超图学习算法的一个重要研究方向;
(2) 高阶关系广泛存在于真实场景中, 但这种高阶关系往往容易被忽略. 很多真实场景下的数据仅有节点信息和节点的成对关系而没有超边信息. 超图结构想要得到进一步的应用推广, 首先要解决如何在这类数据上根据目标任务建立超边关系, 从而利用超图学习算法来处理这类任务获得更好的性能表现. 因而, 如何根据节点信息和成对关系获得超边关系, 也是一个超图学习的重要研究方向;
(3) 超图结构数据在真实场景中由于数据观测的局限性, 一些隐含的重要关系并没有直接体现在固有结构中, 且一些局部超图结构还有可能会误导模型. 因而有人提出动态超图模型, 即: 在模型优化的过程中对超图结构进行动态修改, 从而使得超图结构可以更加贴合目标任务, 以获得更好的性能表现. 动态超图能够在一定程度上解决超图上的不一致性问题, 是一个极具潜力的研究方向;
(4) 像很多传统图应用场景一样, 超图应用场景也存在标签稀疏的问题. 因而, 通过部分有标签节点来预测其余节点标签的超图半监督学习, 也是超图学习的一大热点问题. 与传统图不同的是, 超图上的每条超边涉及两个以上的节点, 如何处理同一超边上的节点之间的关系就变得尤为重要. 一些超图学习算法通过将超图展开成普通的方式来解决这一问题. 这一类方法虽然直观、灵活, 但超边展开过程容易丢失超边信息;
(5) 超图结构信息除了节点信息、节点邻居信息外, 还包括一些高阶全局信息. 一些方法通过注意力机制、图卷积等结构来抽取超图的节点信息和节点邻居信息, 但鲜有方法可将高阶全局信息引入超图模型. 如何有效抽取超图中的高阶结构信息, 将其引入到超图学习模型中, 是一个仍待解决的问题;
(6) 超图分割一直以来都是超图的研究热点之一, 尽管已有很多算法能够实现对超图结构在不同的目标条件下进行切割, 但研究者对于降低算法的时间和空间复杂度这一问题的研究一直都未停止. 所以, 如何快速获得符合目标条件的超图切割结果, 也是一个重要研究方向;
(7) 除此之外, 在超图上还存在一些特殊应用场景的研究, 如利用超图进行多元关系推理、解决图像处理问题等. 研究这类问题时需要将超图学习方法和研究场景特点进行结合, 对超图学习方法进行一些特异性设计, 从而使超图机制能够贴合任务场景.
本文对超图学习方法进行了梳理分析: 首先, 将超图学习方法分为谱分析方法、神经网络方法以及其他方法, 再进一步根据方法建模思路的不同将其分为展开式方法和非展开式方法; 在讨论具体方法时, 根据方法的特点进行了进一步细分, 并对同类方法进行了分析比较; 通过实验对比了主流超图学习方法的算法性能; 最后, 对当前超图学习的研究方向进行了展望.
https://en.wikipedia.org/wiki/Hypergraph#Definitions]]>
Karypis G, Aggarwal R, Kumar V,
Karypis G, Kumar V. Multilevel
Eiter T, Gottlob G. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 1995, 24(6): 1278-1304.
doi: 10.1145/1401890.1401971]]]>
Carletti T, Battiston F, Cencetti G,
Huang Y, Liu Q, Metaxas D. Video object segmentation by hypergraph cut. In: Proc. of the 2009 IEEE Conf. on Computer Vision and Pattern Recognition. IEEE, 2009. 1738-1745.
Gao Y, Wang M, Tao D,
doi: 10.1145/1143844.1143847]]]>
Jiang J, Wei Y, Feng Y,
Tu K, Cui P, Wang X,
Zhou D, Huang J, Schölkopf B. Learning with hypergraphs: Clustering, classification, and embedding. In: Advances in Neural Information Processing Systems, 2006, 19: 1601-1608.
Liu Y, Shao J, Xiao J,
Wu F, Han YH, Zhuang YT. Multiple hypergraph clustering of Web images by miningword2image correlations. Journal of Computer Science and Technology, 2010, 25(4): 750-760.
Gui H, Liu J, Tao F,
Zhang R, Zou Y, Ma J. Hyper-SAGNN: A self-attention based graph neural network for hypergraphs. In: Proc. of the Int'l Conf. on Learning Representations (ICLR). 2020.
Louis A. Hypergraph Markov operators, eigenvalues and approximation algorithms. In: Proc. of the 47th Annual ACM Symp. on Theory of Computing. 2015. 713-722.
Bretto A. Hypergraph Theory — An Introduction. Cham: Springer, 2013.
Berge C. Hypergraphs: Combinatorics of Finite Sets. Elsevier, 1984.
Kahng AB. Fast hypergraph partition. In: Proc. of the 26th ACM/IEEE Design Automation Conf. 1989. 762-766.
Alon N. Transversal numbers of uniform hypergraphs. Graphs and Combinatorics, 1990, 6(1): 1-4.
Gunopulos D, Mannila H, Khardon R,
doi: 10.1090/dimacs/010/03]]]>
Cooper J, Dutle A. Spectra of uniform hypergraphs. Linear Algebra and Its Applications, 2012, 436(9): 3268-3292.
Bulo SR, Pelillo M. A game-theoretic approach to hypergraph clustering. In: Proc. of the NIPS. Citeseer, 2009. 1571-1579.
Papa DA, Markov IL. Hypergraph partitioning and clustering. In: Handbook of Approximation Algorithms and Metaheuristics. 2007. 61-71.
Zass R, Shashua A. Probabilistic graph and hypergraph matching. In: Proc. of the 2008 IEEE Conf. on Computer Vision and Pattern Recognition. IEEE, 2008. 1-8.
Bretto A, Gillibert L. Hypergraph-Based image representation. In: Proc. of the Int'l Workshop on Graph-based Representations in Pattern Recognition. Springer-Verlag, 2005. 1-11.
Yadati N, Nimishakavi M, Yadav P,
Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv Preprint arXiv: 160902907, 2016.
Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering. In: Proc. of the 30th Int'l Conf. on Neural Information Processing Systems. 2016. 3844-3852.
Zien JY, Schlag MD, Chan PK. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Trans. on Computer- Aided Design of Integrated Circuits and Systems, 1999, 18(9): 1389-1399.
Yu L, Shen X, Jiang X,
Rodríguez JA. On the Laplacian eigenvalues and metric parameters of hypergraphs. Linear and Multilinear Algebra, 2002, 50(1): 1-14.
Rodriguez JA. On the Laplacian spectrum and walk-regular hypergraphs. Linear and Multilinear Algebra, 2003, 51(3): 285-297.
Agarwal S, Lim J, Zelnik-Manor L,
Hadley SW. Approximation techniques for hypergraph partitioning problems. Discrete Applied Mathematics, 1995, 59(2): 115-127.
Ihler E, Wagner D, Wagner F. Modeling hypergraphs by graphs with the same mincut properties. Information Processing Letters, 1993, 45(4): 171-175.
Huang S, Elgammal A, Yang D. On the effect of hyperedge weights on hypergraph learning. Image and Vision Computing, 2017, 57: 89-101.
Chan THH, Liang Z. Generalizing the hypergraph Laplacian via a diffusion process with mediators. Theoretical Computer Science, 2020, 806: 416-428.
Alon N, Milman VD.
Alon N. Eigenvalues and expanders. Combinatorica, 1986, 6(2): 83-96.
Bolla M. Spectra, euclidean representations and clusterings of hypergraphs. Discrete Mathematics, 1993, 117(1-3): 19-39.
Purkait P, Chin TJ, Sadri A,
Huang Y, Liu Q, Zhang S,
Ma X, Liu W, Li S,
Huang J, Chen C, Ye F,
Feng Y, You H, Zhang Z,
Ji S, Feng Y, Ji R,
Yi J, Park J. Hypergraph convolutional recurrent neural network. In: Proc. of the 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining. 2020. 3366-3376.
Yang C, Wang R, Yao S,
Vaswani A, Shazeer N, Parmar N,
Veličković P, Cucurull G, Casanova A,
https://arxiv.org/pdf/1901.08150.pdf ]]>
Jin T, Cao L, Zhang B,
Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 2006, 7(11).
He X, Niyogi P. Locality preserving projections. Advances in Neural Information Processing Systems, 2004, 16(16): 153-160.
Du D, Qi H, Wen L,
Wen L, Du D, Li S,
Su L, Gao Y, Zhao X,
Lin S, Xiao G, Yan Y,
Lee G, Ko J, Shin K. Hypergraph motifs: Concepts, algorithms, and discoveries. Proc. of the VLDB Endowment, 2020, 13(12): 2256-2269.
Tan S, Bu J, Chen C,
Hein M, Setzer S, Jost L,
Lawler EL. Cutsets and partitions of hypergraphs. Networks, 1973, 3(3): 275-285.
Li P, Milenkovic O. Inhomogeneous hypergraph clustering with applications. Advances in Neural Information Processing Systems, 2017, 2017: 2309-2319.
Veldt N, Benson AR, Kleinberg J. Minimizing localized ratio cut objectives in hypergraphs. In: Proc. of the 26th ACM SIGKDD Int'l Conf. on Knowledge Discovery & Data Mining. 2020. 1708-1718.
Whang JJ, Du R, Jung S,
Yang D, Qu B, Yang J,
Martino A, Giuliani A, Rizzi A. (Hyper) Graph embedding and classification via simplicial complexes. Algorithms, 2019, 12(11): 223.
Zhang Z, Lin H, Gao Y. Dynamic hypergraph structure learning. In: Proc. of the 27th Int'l Joint Conf. on Artificial Intelligence. 2018. 3162-3169.
Li D, Xu Z, Li S,
Fatemi B, Taslakian P, Vazquez D,
Helali A, Löwe M. Hitting times, commute times, and cover times for random walks on random hypergraphs. Statistics & Probability Letters, 2019, 154: 108535.
Lu L, Peng X. High-ordered random walks and generalized Laplacians on hypergraphs. In: Proc. of the Int'l Workshop on Algorithms and Models for the Web-graph. Springer, 2011. 14-25.
Zhu Y, Guan Z, Tan S,
Bu J, Tan S, Chen C,
Wang M, Liu X, Wu X. Visual classification by $\ell _1 $-hypergraph modeling. IEEE Trans. on Knowledge and Data Engineering, 2015, 27(9): 2564-2574.
Chen F, Gao Y, Cao D,
Ji R, Chen F, Cao L,
Konstantinova EV, Skorobogatov VA. Application of hypergraph theory in chemistry. Discrete Mathematics, 2001, 235(1-3): 365-383.
Kajino H. Molecular hypergraph grammar with its application to molecular optimization. In: Proc. of the Int'l Conf. on Machine Learning. PMLR, 2019. 3183-3191.
Tsuyuzaki K, Ishii M, Nikaido I. Uncovering hypergraphs of cell-cell interaction from single cell RNA-sequencing data. bioRxiv, 2019. 566182.
Wu MY, Hill CS. TGF-
Schwob M, Zhan J, Dempsey A. Modeling cell communication with time-dependent signaling hypergraphs. IEEE/ACM Trans. on Computational Biology and Bioinformatics, 2019.
http://www.cad.zju.edu.cn/home/dengcai/Data/MLData.html]]>
https://archive.ics.uci.edu/ml/datasets/Yeast]]>
https://github.com/malllabiisc/HyperGCN/tree/master/data/coauthorship/cora]]>
Zheng V, Cao B, Zheng Y,
Harper FM, Konstan JA. The movielens datasets: History and context. ACM Trans. on Interactive Intelligent Systems (TⅡS), 2015, 5(4): 1-19.
http://www.fda.gov/Drugs/]]>