「图神经网络复杂图挖掘」的研究进展

2022 年 10 月 23 日 专知

图神经网络对非欧式空间数据建立了深度学习框架,相比传统网络表示学习模型,它对图结构能够实施更加深层的信息聚合操作.近年来,图神经网络完成了向复杂图结构的迁移,诞生了一系列基于复杂图的图神经网络模型. 然而,现有综述文章缺乏对复杂图神经网络全面、系统的归纳和总结工作.将复杂图分为异质图、动态图和超图3种类型.将异质图神经网络按照信息聚合方式划分为关系类型感知和元路径感知两大类,在此基础上,分别介绍普通异质图和知识图谱.将动态图神经网络按照处理时序信息的方式划分成基于循环神经网络、基于自编码器以及时空图神经网络三大类.将超图神经网络按照是否将超图展开成成对图划分为展开型和非展开型两大类,进一步按照展开方式将展开型划分成星形展开、团式展开和线形展开3种类型.详细阐述了每种算法的核心思想,比较了不同算法间的优缺点,系统列举了各类复杂图神经网络的关键算法、(交叉)应用领域和常用数据集,并对未来可能的研究方向进行了展望.

http://www.jos.org.cn/jos/article/abstract/6626

1 背景与分类

图(Graph)作为一种数据结构, 能够精确描述事物间复杂的相互作用关系, 因而被广泛应用于诸多科学和工程领域. 近年来, 由于图结构丰富的信息表达能力, 利用机器学习对图进行分析的研究受到越来越多的关注. 图表示学习, 便是将图中丰富的结构和语义信息转化成低维稠密的节点表示向量, 以便于后续利用机器学习方法进行诸如节点分类、链接预测和知识推断等图相关应用. 其中, 图神经网络(graph neural networks, GNNs)由于对图结构建立了深度学习框架, 相比于 DeepWalk[1]、Node2vec[2]等传统网络表示学习方法, 可以同时利用图结构信息和节点特征信息, 并构造更加复杂深层的神经网络进行表示学习, 因而逐渐成为了近年来的研究热点.

为了简化问题和便于建模, 早期的图神经网络大多基于简单图结构, 即静态、同质的成对图结构. Sperduti 等人[3]最早尝试将神经网络应用到有向无环图上. 他们提出了一个将输入的图结构转化成固定维度的节点向量的编码器, 并将向量输入到一个前馈神经网络中进行分类. 在此基础上, Gori 等人[4]首次提出了图神经网络的概念, 他们将递归神经网络(recursive neural network, RNN)扩展到了图结构, 进而提出了递归图神经网络. 由此衍生出一系列早期图神经网络研究[5,6]. 然而, 这些早期方法有着很高的计算复杂度, 难以应用到大型图结构上, 因此并没有得到广泛应用.

近年来, 得益于卷积神经网络(convolutional neural network, CNN)在计算机视觉领域的成功, 许多方法开始尝试对图结构定义卷积操作, 并将卷积神经网络迁移到图结构上. 这些方法统称为图卷积神经网络(graph convolutional networks, GCNs). 图卷积神经网络可以按照实施卷积的方式分为谱方法(spectral-based GCNs)和空间方法(spatial-based GCNs)两种类型. 其中, 谱方法利用卷积定理从谱域定义图卷积. 例如, Xu 等人提出的 GWNN[7]引入小波变换替换傅里叶变换作为基底, 使得模型拥有更好的局部性; Defferrard 等人[8]和 Kipf 等人[9]通过对卷积核参数化, 实现了局部性并降低了复杂度. 空间方法则致力于从节点所在的空间域出发, 通过定义聚合操作和连接操作来聚合邻居信息并与中心节点信息合并从而形成新的中心节点表示. 例如, MPNN[10]将图卷积转化成节点间信息的传递, 并提出了空间方法的一个通用框架. 后续的 GraphSage[11]使用采样选取固定数量的邻居节点, 并给出更加丰富的聚合函数类型.

随着 GNNs 在简单图上的逐渐完善, 人们开始考虑更加复杂多样的图结构. 通过赋予图异质性、时序性或高阶关联等特征, GNNs 衍生出了一大批基于复杂图结构的变种, 使其拥有更加灵活广泛的应用场景. 本文按照复杂图的结构类型将这些方法分为异质图、动态图和超图三大类. 图 1 表示了简单图和 3 种复杂图结构

(1) 异质图神经网络

在真实世界中, 事物之间的相互作用关系构成的图结构往往是异质的, 即节点和边具有多种类型. 例如, 在社交网络中同时存在用户、贴文和评论等类型的节点和用户-贴文、用户-评论和贴文-评论等多种关系. 边和节点的异质造成了节点间语义关系的多样性, 同时, 边和节点所具有的属性特征也位于不同的特征空间中, 这些原因导致传统的图神经网络方法无法高效、准确地处理异质图. 为了解决这些问题, Schlichtkrull 等人[12]最早通过对不同类型的关系定义不同的系数矩阵, 将 GCN[9]成功迁移到了异质图上; Hu 等人[13]在此基础上, 进一步使用注意力机制计算不同类型关系的重要程度; 后续的 Wang 等人[14]则引入了元路径概念将异质图转化为同质图, 再进行表示学习. 这些方法被统一归纳为异质图神经网络(heterogeneous graph neural networks, HetGNNs).

(2) 动态图神经网络

在真实世界中, 图的结构信息和节点特征会随着时间发生变化, 从而导致对图神经网络的输入发生变化. 这类复杂图出现在交通网络、生物网络及知识图谱等各种应用中. 例如, 在时序链接预测问题上, 模型需要根据网络在 0 到 t 时刻的变化情况预测 t+1 时刻的网络状态; 在交通流预测问题中, 某一位置的交通状态既受到邻近位置交通流的影响, 也受到这些位置历史交通状态的影响. 因此, 为了在实施图卷积的过程中充分考虑图结构和节点属性的动态特性, 一些研究者[15,16]开始将循环神经网络与 GNNs 相结合, 或引入自编码器来处理动态图[17]. 此外, Yan 等人[18]将时序关系转化成时间连接, 提出了时空图神经网络. 这些方法都被归纳为动态图神经网络(dynamic graph neural networks, DGNNs).

(3) 超图神经网络

在现实世界中, 节点间的关系常常不是成对出现的, 而是两个或两个以上节点间共同构成相互作用关系. 例如, 在生物蛋白质交互网络中, 往往是多个蛋白质共同作用行使某项生物功能; 在引文网络中, 往往是多位作者共同写作了某篇文章. 这些高阶关联形成了一个完整的关系整体, 因而将这种高阶关联使用成对图结构分别表示将会带来信息损失[19]. 超图(hypergraph)扩展了图的定义, 其中的一条超边(hyperedge)可以包含任意数量的节点, 因此可以直接储存高阶关联. 近年来, 超图的优势引起了学术界和工业界的广泛关注, 一系列超图神经网络方法(hypergraph neural network, HyperGNN)被相继提出. 按照是否将超图展开为成对图, 这些方法可分为展开型[20,21]和非展开型[22,23]超图神经网络. 图 2 展示了本综述对于图神经网络方法的分类框架.

简单图神经网络

为了简化问题, 便于建模, 早期图神经网络的研究多基于简单图结构. 这一时期的研究重点集中在如何将深度学习方法(RNN、CNN、Autoencoder 等)应用到图结构学习当中, 并衍生出不同的发展路线. 基于简单图的图神经网络是基于复杂图的图神经网络的基础, 为了方便读者理解, 本节我们将简要介绍简单图神经网络. 我们将其大致分成 3 种类型: 递归图神经网络、卷积图神经网络和图自编码器, 并分别进行阐述.

异质图神经网络

在真实世界中, 网络中节点和边往往具有多种类型, 而图神经网络的早期研究多基于同质图. 由于异质图中复杂的语义关系和多样的特征类型, 传统的基于同质图的 GNN 无法直接迁移到这类图结构. 近年来, 随着图神经网络在同质图上的研究逐渐成熟, 研究者们开始将目光投向异质图, 并提出了一系列方法. 我们按照节点特征聚合过程中信息的传递方式将这些方法分成关系类型感知和元路径感知这两种类型. 值得注意的是, 知识图谱由于复杂的语义关系和庞大的规模, 是一种较为特殊的异质图, 而针对它设计的图神经网络方法大多是与领域问题相结合[57,58], 学习图谱中的语义信息辅助进行推断或辨识. 这也与传统异质图 GNN 方法进行节点分类或链接预测的任务不同. 因此, 在上述分类的基础上, 我们将分开讨论普通异质图与知识图谱.

动态图神经网络

真实世界中的图往往具有时序性, 即网络结构和节点属性会随着时间动态变化. 传统图神经网络[9]基于静态图结构, 因此无法直接用于处理动态图. 为了解决这个问题, 研究者们提出了一系列基于时序图的图神经网络. 这些方法按照处理时序信息的方式可以分为基于循环神经网络、基于自编码器和时空图神经网络这 3 种类型. 所有动态图 GNN 的分类及描述见前文表 3.

超图神经网络

在真实世界中, 事物间的关联关系往往不是成对出现的, 而是两个以上实体间共同构成相互作用关系. 直接使用简单图表示这种非成对关系将会带来信息损失[19]. 超图(hypergraph)扩展了简单图的定义. 在超图中, 一条超边可以包含任意数量的节点, 因此可以直接储存非成对关系. 超图相比于简单图拥有更加灵活的边定义方式, 因而对于复杂关系有着更加强大的表达能力. 对于超图的研究最早可以追溯到 20 世纪 80 年代, 这一时期的研究集中在对超图数学性质的推导上[98100]. 更近些时候, 伴随着机器学习方法在图结构上的成功应用, 越来越多的研究者再次将目光投向超图, 并借助机器学习方法对超图结构进行更深层次的挖掘.

由于超图对于多元关系的建模能力, 早期对于超图的研究主要集中于领域化的问题. 其中, Tan 等人[101] 率先利用超图结构进行了社交网络中用户对齐的研究; Zhu 等人[102]和 Bu 等人[103]则关注超图在推荐系统中的应用; Fatemi 等人[104]将基于三元组的传统知识图谱结构扩展到了知识超图形式; Hwang 等人[105]和 Klamt 等人[106]利用超图进行蛋白质或细胞网络的多元关系建模; Huang 等人[107]则将超图应用到计算机视觉上. 超图的应用将在第 8.3 节详细介绍. 尽管这一时期的研究者已经开始利用超图对各领域中的多元关系进行建模, 但这些方法仍然缺乏对超图表示学习系统的研究, 因此不具有普适性, 很难迁移到其他领域. 直到近年来, 随着图神经网络在简单图结构上的逐渐成熟, 研究者开始将 GNN 迁移到超图结构上, 并提出了一系列超图神经网络方法. 我们按照是将超图展开成成对图结构还是直接在超图上进行卷积操作, 将这些方法分成展开型和非展开型两大类.

应用

复杂图结构相比于简单图减少了诸如同质、静态等限制条件, 使得它们更加贴近实际情况, 进而拥有更加广泛的应用场景. 基于复杂图的 GNN 在不同领域都有着广泛应用, 例如时空图神经网络在交通流预测[95,96] 和动作识别[18]领域; 异质图神经网络在推荐系统[57,58,71]、视觉问答[65]和金融风控[120]领域; 或者超图神经网络在视觉[121,122]和化学领域[115]的重要作用. 除此之外, 一些实际应用则对多种复杂图进行了组合使用, 例如时序知识图谱[93]和超图知识图谱[104]的相关研究. 本节我们按照不同类型复杂图及其组合方式阐述复杂图 GNN 的相关应用方向.

数据集

复杂图 GNN 由于其广泛的应用场景拥有众多公开数据集. 我们按照复杂图种类以及具体的应用类型分别介绍相应的数据集. 由于数据集数量众多, 本文只介绍各应用中被广泛使用的一部分数据集. 对于想获取更多其他复杂图 GNN 相关数据集的读者, 可以访问 Network Repository (http://networkrepository.com)、 Standford Large Network (https://snap.stanford.edu/data/)、Open Graph Benchmark (https://ogb.stanford.edu)以及 LINQS (https://linqs.soe.ucsc.edu/data)等图数据仓库. 本文介绍的数据集分类及相应描述见表 5.

10 展望与总结

10.1 研究方向展望

GNNs 目前已经完成了向异质图、动态图和超图等复杂图结构的迁移, 并取得了优秀的成果. 但值得注意的是, 当前大多数 GNN 方法只在小型数据集上进行了简单任务(节点分类、链接预测等)的验证. 在真实应用场景下, 复杂图的巨大规模和快速更新频率对复杂图 GNN 进一步提出了可扩展、在线性等要求. 本节将讨论复杂图 GNN 几个潜在的研究方向.

可扩展性. 当前用于复杂图 GNN 测试的数据集数据量都不大, 大多在 1 万节点以下. 然而和众多深度学习模型一样, GNNs 在大规模图结构上的训练仍非常具有挑战性. 一方面, 随着 GNN 层数的增加, 模型训练所需要的时间将呈指数增长; 另一方面, 大规模图的邻接矩阵以及节点特征储存需要消耗大量的内存空间. 近年来, Cluster-GCN[178]等研究考虑到了 GNNs 在大规模图上扩展性的问题, 将训练的图规模提升到百万节点级别. 但 GNN 在千万级节点以上的知识图谱, 动态图上的训练仍是需要亟待解决的问题.
可解释性. 随着 GNN 在金融风控、疾病诊断等领域的应用, 对 GNN 可解释性的要求也越来越高. 随着可解释性研究在视觉和文本领域的重大进展, 近来一些研究者也开始从模型或梯度等角度给出图神经网络的可解释性[179]. GNN 模型的可解释性目前的研究还很不完善, 是一个极具潜力的研究方向.
在线性. 在动态网络方面, 在欺诈检测或推荐系统实际应用中, 用户行为网络的高频更新对 GNN 模型的响应时间提出了要求. 如何在极短时间内重新训练大规模复杂图从而得到新的节点嵌入表示是一个重要的研究方向. 近年来, 一些研究者开始注意到这个问题. 例如, Wu 等人[93]通过只训练变化的子图结构提出了一个大型知识图谱的在线学习模型.
迁移性. RNN 被用于动态图 GNN 以及简单图 GNN 向超图 GNN 的迁移已经证明了深度学习模型在不同图结构上的可迁移性. 一些原本针对某种图类型设计的方法经过简单修改和拓展后很可能用于其他图结构. 复杂图 GNN 之间的迁移研究是将来重要的研究方向之一.