标题 | A Comprehensive Survey on Graph Neural Networks |
---|---|
作者 | Zonghan Wu , Shirui Pan,Fengwen Chen,Guodong Long |
邮箱 | shirui.pan@monash.edu |
机构 | Centre for Artificial Intelligence, Faculty of Engineering and Information Technology, University of Technology Sydney, Ultimo, Australia |
论文 | https://ieeexplore.ieee.org/document/9046288 |
深度学习中的图像分类和视频处理到语音识别和自然语言理解,这些任务中的数据通常在欧几里得空间中表示。虽然深度学习有效地捕获了欧几里得数据的隐藏模式,然而,越来越多的数据从非欧几里得域生成并表示为具有复杂关系以及对象之间存在相互依赖关系的图。例如:
1.在电子商务中,基于图的学习系统可以利用用户和产品之间的交互来做出高度准确的推荐。
2.在化学领域中,分子被建模为图形,并且需要确定它们的生物活性以进行药物发现。
3.在引文网络中,论文通过引文相互链接,并且需要将它们分类到不同的组中。
图数据的复杂性对现有的机器学习算法提出了重大挑战。由于图可能是不规则的,因此图可能具有可变大小的无序节点,并且来自图中的节点可能具有不同数量的邻居,导致一些重要的操作(例如卷积)在图像域中很容易计算,但是难以应用于图域。此外,现有机器学习算法的一个核心假设是各个实例相互独立。这个假设不再适用于图数据,因为每个实例(节点)都通过各种类型的链接(例如引用、友谊和交互)与其他实例相关联。
近年来,出现了许多关于扩展图数据深度学习方法的研究。目前,最先进的图神经网络分为四类,即循环图神经网络、卷积图神经网络、图自动编码器和时空图神经网络。
另外,在论文中,给出了与图有关常用的符号,如下图。
1、循环图神经网络(RecGNN)
这些大多是GNN的先驱作品。RecGNN旨在通过循环神经结构学习节点表示。他们假设图中的一个节点不断地与其邻居交换信息,直到达到稳定的平衡。RecGNN在概念上很重要,并启发了后来对ConvGNN的研究。特别是,基于空间的卷积神经网络继承了消息传递的思想。
2、卷积图神经网络(ConvGNN)
这些将卷积操作从网格数据推广到图数据。
主要思想是通过聚合节点自身的特征Xv和邻居的特征Xu来生成节点v的表示,其中u∈N(v)(v的邻居)。与RecGNN不同,ConvGNN将多个图卷积层叠加以提取高级节点表示。卷积图神经网络在建立许多其他复杂的GNN模型中起着核心作用。
下图是用于结点分类的ConvGNN。具有多个图卷积层的 ConvGNN。 图卷积层通过聚合来自其邻居的特征信息以封装每个节点的隐藏表示。 在特征聚合之后,对结果输出应用非线性变换。 通过堆叠多个层,使得每个节点的最终隐藏表示能从更远的邻域接收消息。
下图是用于图分类的ConvGNN。具有用于图分类的池化和读出层的 ConvGNN。 图卷积层之后是一个池化层,用于将图粗化为子图(压缩),粗化图上的节点表示表示更高的图级表示。读出层通过获取子图的隐藏表示的总和/平均值来总结最终的图表示。
3、图自编码器(GAEs)
这些是无监督学习框架,将节点/图编码到潜在向量空间中,并从编码信息中重构图数据。GAEs被用来学习网络嵌入和图生成分布。对于网络嵌入,GAEs通过重构图的结构信息(如图的邻接矩阵)来学习潜在节点表示。对于图的生成,一些方法是一步一步地生成图的节点和边,而另一些方法是一次输出一个图。
下图是用于网络嵌入的GAE。编码器使用图卷积层为每个节点获取网络嵌入。解码器计算给定网络嵌入的成对距离。 应用非线性激活函数后,解码器重构图邻接矩阵。通过最小化真实邻接矩阵和重构邻接矩阵之间的差异来训练网络。
4、时空图神经网络(STGNN)
旨在从时空图中学习隐藏模式,这在各种应用中变得越来越重要,如交通速度预测、驾驶员机动预测和人类行为识别。STGNN的核心思想是同时考虑空间依赖性和时间依赖性。许多当前的方法将图卷积与RNN或CNN集成来捕获空间依赖性来建模时间依赖性。
下图是用于时空图预测的 STGNN。图卷积层之后是1维-CNN 层。 图卷积层对 A 和 X(t) 进行操作以捕获空间依赖性,而 1维-CNN 层沿时间轴在 X 上滑动以捕获时间依赖性。 输出层是一个线性变换,为每个节点生成一个预测,比如它在下一个时间步的未来值。
在这里,作者给出了不同图神经网络的主要论文表格。
将模型框架分为任务框架和训练框架。
1、任务框架
将图结构和节点内容信息作为输入,GNN的输出可以专注于不同的图分析任务,主要有以下几种:
·(1)Node Level。节点一级的输出能应用到与节点回归和节点分类相关的任务。RecGNNs和ConvGNNs可以通过信息传输或图卷积提取节点的高级表示。GNN可以使用MLP或softmax层作为输出层,能够以端到端的方式执行节点级任务。
·(2)Edge-level。边一级的输出能应用到与边分类或链接预测相关的任务。通过GNN中两个节点的隐藏表示,可以利用相似性函数或神经网络来预测边的标签或连接强度。
·(3)Graph-level。图一级的输出能应用到与图分类相关的任务。为了在图一级上获得紧凑的表示,GNN通常与池化和readout操作结合使用。
2、训练框架
许多GNN(例如,ConvGNNs)可以在端到端的学习框架中以半监督,有监督或无监督的方式进行训练,具体取决于已有的学习任务和标签信息。
·(1)Semi-supervised learning for node-level classification。给定一个部分节点带有标注而其它节点未被标注的网络,ConvGNNs可以学习一个鲁棒的模型,该模型能有效地标识了未被标注的节点的类别。为此,可以通过堆叠几个图卷积层,然后堆叠用于多分类的softmax层来构建端到端框架。
·(2)Supervised learning for graph-level classification。图一级分类旨在预测整个图的类别。该任务的端到端学习可以通过使用图卷积层,图池化层和readout层的组合来实现。其中图卷积层负责建模节点的高级表示,图池化层起到下采样的作用,每次都会将每个图缩小到一个子结构中。readout层将每个图的节点表示折叠成图表示。通过将多层感知器和softmax层应用于图表示,我们可以构建用于图分类的端到端框架。
·(3)Unsupervised learning for graph embedding。当没有图的类别标签时,我们可以在端到端框架中以无监督的方式学习图嵌入。这些算法通过两种方式利用边一级的信息。 一种简单的方法是采用一个自编码器框架,其中编码器采用图卷积层将图嵌入到潜在表示中,并在其上使用解码器重建图结构。另一种流行的方法是利用负采样方法,该方法将一部分节点对作为负例对,而图中彼此链接的节点对是正例对。然后应用logistic回归层以区分正例和负例对。
3、总结
在下图中,我们总结了若干具有代表性的RecGNNs和ConvGNN的主要特点。我们在各种模型之间对输入,池化层,readout层和时间复杂度进行了比较。
1、数据集
论文主要将数据集分为四组,即引文网络、生化图、社交网络等。在下表中,总结了选定的基准数据集。
2、评估、开源实现
评估
节点分类和图分类是评估 RecGNN 和 ConvGNN 性能的常见任务。
(1)节点分类。在节点分类中,大多数方法在基准数据集(包括 Cora、Citeseer、Pubmed、PPI 和 Reddit)上遵循训练/验证验证/测试的标准拆分。他们报告了多次运行测试数据集的平均准确率或 F1 分数。
(2)图分类。在图分类中,研究人员通常采用 10 折交叉验证进行模型评估。然而,正如Federico等人所指出的,实验设置是模棱两可的,并且在不同的工作中并不统一。
开源实现
开源实现促进了深度学习研究中基线实验的工作。在补充材料 C 中,论文提供了本文回顾的 GNN 模型的开源实现的超链接。值得注意的是,Fey 等人在 PyTorch 中发布了一个名为 PyTorch Geometric 的几何学习库,它实现了许多 GNN。最近,随着Deep Graph Library (DGL) 发布,其在 PyTorch 和 MXNet 等流行的深度学习平台上提供了许多 GNN 的快速实现。
3、实际应用
(1)计算机视觉:GNN在计算机视觉中的应用包括场景图生成、点云分类和动作识别。此外,GNN在计算机视觉中的应用方向还在不断增加。它包括人-物交互、少镜头图像分类、语义分割、视觉推理和问答。
(2)自然语言处理:GNN在自然语言处理中的一个常见应用是文本分类。GNN利用文档或单词的相互关系来推断文档标签。
(3)交通:准确预测交通速度、流量或交通网络中的道路密度对智能交通系统至关重要。另一个工业级应用是出租车需求预测。
(4)推荐系统:基于图的推荐系统将项目和用户作为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息,基于图的推荐系统能够产生高质量的推荐。推荐系统的关键是对项目对用户的重要性进行评分。最终,它可以被转换为链接预测问题。
(5)化学:在化学领域,研究人员应用GNN来研究分子/化合物的图结构。节点分类、图分类和图生成是针对分子/化合物图的三个主要任务,用于学习分子指纹、预测分子性质、推断蛋白质界面、合成化合物。
(6)其他:GNN的应用并不局限于上述领域和任务。已经有将GNN应用于各种问题的探索,如程序验证、程序推理、社会影响预测、对抗性攻击预防、电子健康记录建模、脑网络、事件检测和组合优化。
在论文中,作者提出了图神经网络的四个发展方向。
1、模型深度
深度学习的成功在于深度的神经架构,但有学者发现随着深度增加,ConvGNN的性能却急剧下降,由于图卷积将相邻节点的表示推得更近,理论上,当图卷积层数无限时,所有节点的表示都会收敛到一个点。这就提出一个问题,增加深度是否是学习图数据的一个好的策略?
2、可拓展性的权衡
GNN的可扩展性是以破坏图完备性为代价的。无论使用抽样还是聚类,模型都会丢失部分图信息。通过抽样,一个节点可能会错过它有影响力的邻居。通过聚类,一个图可能被剥夺了一个明显的结构模式。如何权衡算法的可扩展性和图的完整性可能是未来的研究方向。
3、异构性
目前大多数GNN假设为同构图,直接将GNN应用于异构图是困难的,因为异构图可能包含不同类型的节点和边,或者不同形式的节点和边输入,如图像和文本。因此,应该开发新的方法来处理异构图。
4、动态性
图在本质上是动态的,节点或边可能出现或消失,节点/边的输入可能会一次次改变。为了适应图的动态性,需要新的图卷积。虽然STGNN可以部分解决图的动态性问题,但很少有人考虑如何在动态空间关系的情况下执行图卷积。
在本文中,论文对GNN进行了全面的概述。提供了一个分类法,将GNN分为四类:RecGNN, ConvGNN, GAEs和STGNN。提供了一个在各类别中方法的概述、比较和总结。然后,介绍了GNN的广泛应用、GNN的数据集、开源代码和模型评估。最后,提出了GNN的四个未来发展方向。 对于论文的内容来说,内容全面,涵盖了概述、模型分类、模型的比较、模型架构、典型的模型介绍、原理推导、研究方向、经典论文和数据集、使用工具等各个方面,表格众多,比较清晰。
联系客服