图神经网络概述第三弹：来自IEEE Fellow的GNN综述
引言
深度网络的最新进展推进了模式识别和数据挖掘领域的研究。目标检测、机器翻译、语音识别等许多机器学习任务曾高度依赖手工特征工程来提取信息特征集合，但多种端到端深度学习方式（即卷积神经网络、长短期记忆网络和自编码器）改变了这种状况。深度学习在多个领域的成功主要归功于计算资源的快速发展（如 GPU）、大量训练数据的收集，还有深度学习从欧几里得数据（如图像、文本和视频）中提取潜在表征的有效性。例如 CNN 可以利用平移不变性、局部连通性和图像数据语意合成性，从而提取出与整个数据集共享的局部有意义的特征，用于各种图像分析任务。
尽管深度学习已经在欧几里得数据中取得了很大的成功，但从非欧几里得域生成的数据已经取得更广泛的应用，它们需要有效分析。例如，在电子商务领域，一个基于图的学习系统能够利用用户和产品之间的交互以实现高度精准的推荐。在化学领域，分子被建模为图，新药研发需要测定其生物活性。在论文引用网络中，论文之间通过引用关系互相连接，需要将它们分成不同的类别。
图数据的复杂性对现有机器学习算法提出了重大挑战，因为图数据是不规则的。每张图大小不同、节点无序，一张图中的每个节点都有不同数目的邻近节点，使得一些在图像中容易计算的重要运算（如卷积）不能再直接应用于图。此外，现有机器学习算法的核心假设是实例彼此独立。然而，图数据中的每个实例都与周围的其它实例相关，含有一些复杂的连接信息，用于捕获数据之间的依赖关系，包括引用、朋友关系和相互作用。
最近，越来越多的研究开始将深度学习方法应用到图数据领域。受到深度学习领域进展的驱动，研究人员在设计图神经网络的架构时借鉴了卷积网络、循环网络和深度自编码器的思想。为了应对图数据的复杂性，重要运算的泛化和定义在过去几年中迅速发展。例如，图 1 展示了受标准 2D 卷积启发得到的图卷积。本文旨在对这些方法进行全面概述，受众包括想要进入这一快速发展领域的研究人员和想要对比图神经网络算法的专家。
图 1：2D 卷积 vs. 图卷积
图神经网络简史
图神经网络的概念首先由 Gori 等人（2005）[16] 提出，并由 Scarselli 等人（2009）[17] 进一步阐明。这些早期的研究以迭代的方式通过循环神经架构传播邻近信息来学习目标节点的表示，直到达到稳定的固定点。该过程所需计算量庞大，而近来也有许多研究致力于解决这个难题。在本文中，图神经网络代表的是所有用于图数据的深度学习方法。
受到卷积网络在计算机视觉领域所获巨大成功的激励，近来出现了很多为图数据重新定义卷积概念的方法。这些方法属于图卷积网络（GCN）的范畴。Bruna 等人（2013）提出了关于图卷积网络的第一项重要研究，他们基于谱图论（spectral graph theory）开发了一种图卷积的变体。自此，基于谱的图卷积网络不断改进、拓展、进阶。由于谱方法通常同时处理整个图，并且难以并行或扩展到大图上，基于空间的图卷积网络开始快速发展。这些方法通过聚集近邻节点的信息，直接在图结构上执行卷积。结合采样策略，计算可以在一个批量的节点而不是整个图中执行，这种做法有望提高效率。
除了图卷积网络，近几年还开发出了很多替代的图神经网络。这些方法包括图注意力网络（GAT）、图自编码器、图生成网络以及图时空网络。关于这些方法的分类细节详见第三章。
图神经网络相关研究。Bronstein 等人用符号几何深度学习概述了非欧几里得领域的深度学习方法，包括图和流形。虽然这是对图卷积网络的第一次回顾，但这一项研究遗漏了几个基于空间的重要方法，包括 [15], [19], [24], [26], [27], [28]，这些方法更新了最新的基准。此外，这项调查没有囊括很多新开发的架构，这些架构的重要性不亚于图卷积网络。
对于另一项研究，Battaglia 等人 [29] 将图网络定位为从关系数据中学习的构建块，并在统一的框架下回顾了部分图神经网络。然而，他们整体的框架是高度抽象的，失去了每种方法在原论文中的见解。Lee 等人 [30] 对图注意力模型（一种图神经网络）进行了部分调查。最近，Zhang 等人 [31] 提出了一项关于图深度学习的最新调查，却忽略了对图生成网络和图时空网络的研究。总之，现有的研究没有一个对图神经网络进行全面的回顾，只覆盖了部分图卷积神经网络且检查的研究有限，因此遗漏了图神经网络替代方法的最新进展，如图生成网络和图时空网络。
图神经网络 vs. 网络嵌入。对图神经网络的研究与图嵌入或网络嵌入紧密相关，这也是数据挖掘和机器学习社区日益关注的一个话题 [32] [33] [34] [35], [36], [37]。网络嵌入旨在通过保留网络拓扑架构和节点内容信息，将网络顶点表示到低维向量空间中，以使任何后续的图分析任务（如分类、聚类和推荐）都可以通过使用简单的现成学习机算法（如用于分类的支持向量机）轻松执行。许多网络嵌入算法都是无监督算法，它们大致可分为三组 [32]，即矩阵分解 [38], [39]、随机游走 [40] 和深度学习方法。用于网络嵌入的深度学习方法同时还属于图神经网络，包括基于图自编码器的算法（如 DNGR [41] 和 SDNE [42]）和具有无监督训练的图卷积神经网络（如 GraphSage [24]）。图 2 描述了本文中网络嵌入和图神经网络的区别。
图 2：网络嵌入 vs 图神经网络。
本文作出的贡献如下：
- 新的分类体系：考虑到深度学习在图数据上的研究与日俱增，我们提出了图神经网络（GNN）的新分类体系。在这种分类体系下，GNN 被分成了 5 个类别：图卷积网络、图注意力网络、图自编码器、图生成网络和图时空网络。我们确定了图神经网络和网络嵌入之间的区别，并在不同的图神经网络架构之间建立了联系。
- 全面的概述：这个综述提供了在图数据上的现代深度学习技术的全面概述。对每一种类型的图神经网络，我们提供了表征算法的细节描述，并做了必要的对比和对应算法的总结。
- 丰富的资源：这篇综述提供了图神经网络的丰富资源，其中包括当前最佳算法、基准数据集、开源代码和实践应用。这篇综述可以作为理解、使用和开发不同实际应用的深度学习方法的实践指南。
- 未来方向：这篇综述还强调了已有算法的当前限制，指出了这个快速发展领域未来的可能方向。
论文：A Comprehensive Survey on Graph Neural Networks
论文链接：https://arxiv.org/pdf/1901.00596v1.pdf
摘要：近年来，从图像分类到视频处理再到语音识别和自然语言处理，深度学习已经变革了多项机器学习任务。这些任务中的数据通常表示在欧几里得空间中。然而，越来越多的应用使用非欧几里得域生成的数据，并将它们表示为具有复杂关系和相互依赖关系的图。虽然图数据的复杂性对现有机器学习算法提出了重大挑战，但最近许多研究开始将深度学习方法扩展到图数据。
本文综述了数据挖掘和机器学习领域中的图神经网络（GNN），并按照新的方法对图神经网络的最新进展进行了分类。在关注图卷积网络的同时，他们还回顾了最近开发的其他架构，例如图注意力网络、图自编码器，图生成网络以及图时空网络等。我们还进一步讨论了图神经网络在多个领域的应用并总结了不同学习任务现有算法的开源代码及基准。最后，我们提出了这一快速发展领域的研究方向。
2. 定义
在这一节，我们提供基础图概念的定义。为了方便查询，我们在表 1 总结了常用的符号。
表 1：常用符号。
3. 分类与框架
这一部分内容给出了图神经网络的分类方法。我们考虑到了所有能与神经架构组合成图神经网络的可微图模型，把图神经网络最终分类为：图卷积网络、图注意力网络、图自编码器、图生成网络和图时空网络。这些网络中，图卷积网络在捕捉架构依存关系上扮演着核心角色。如下图 3 所示，属于其他类别的方法部分使用图卷积网络作为基础。表 2 总结了每个类别的代表性方法。
图 3：图神经网络分类
表 2：图神经网络代表性论文
下图 4 展示了图卷积网络节点表征学习的过程。
图 4：有多层 GCN 层的图卷积网络变体。通过从邻域聚合特征信息，一个 GCN 层把每个节点的隐藏表征进行压缩。在特征聚合之后，非线性置换被应用到生成的输出上。通过多层堆叠，每个节点的最终隐藏表征从后续邻域获得信息。
下图 5 展示了多个建立在 GCN 上的图神经网络模型。
图 5：建立在 GCN 上的不同图神经网络模型。
下图展示了图卷积网络和图注意力网络在聚合邻近节点信息方面的区别。
3.2 框架
表 3：图卷积网络的总结。Node-level 输出与节点回归和分类任务相关，Edge-level 输出与边分类和链接预测任务相关，Graph-level 输出与图分类任务相关。
端到端训练框架。图卷积网络可以以（半）监督或纯无监督的方式在端到端学习框架中训练，依赖于学习任务和可用的标签信息。
- 节点级分类的半监督学习。给定部分节点被标记的单个网络，图卷积网络可以学习到一个鲁棒的模型，高效识别未标记节点的类别标签 [14]。为此，可以通过堆叠一系列的图卷积层和 softmax 层来建立端到端框架进行多类别分类。
- 图级分类的监督学习。给定一个图数据集，图级分类旨在预测整个图的类别标签 [55], [56], [74], [75]。这一任务的端到端学习可以利用一个结合了图卷积层和池化步骤的框架实现 [55], [56]。
- 图嵌入的无监督学习。如果图中无可用类别标签，我们可以在一个端到端框架中以完全无监督的方式学习图嵌入。这些算法通过两种方式利用边级（edge-level）信息。一种简单的方法是采用自编码器框架，其中编码器使用图卷积层将图嵌进潜在表征中，然后使用解码器重构图结构 [59], [61]。另一种方法是利用负采样方法，采样一部分节点对作为负对（negative pair），而图中已有的节点作为正对（positive pair）。然后在卷积层之后应用 logistic 回归层，以用于端到端学习 [24]。
4. 图卷积网络
这一章概览图卷积网络（GCN），这是很多复杂图神经网络模型的基础。GCN 方法分为两类，分别基于谱和空间。基于谱的方法通过从图信号处理的角度引入滤波器来定义图卷积，其中图卷积运算被解释为从图信号中去除噪声 [76]。基于空间的方法将图卷积表征为聚合来自近邻的特征信息。虽然 GCN 在节点级别上运行，但是图池化模块可以与 GCN 层交替，将图粗粒化为高级子结构。如图 5a 所示，这种架构设计可用于提取图级表征、执行图分类任务。下文会分别介绍、基于空间的 GCN 和图池化模块。
基于谱的 GCN 部分介绍了其背景、方法等，这些方法包括 Spectral CNN、Chebyshev Spectral CNN (ChebNet)、First order of ChebNet (1stChebNet) 和 Adaptive Graph Convolution Network (AGCN)。
基于空间的 GCN 分为两类：Recurrent-based Spatial GCN 和 Composition Based Spatial GCN。前者包括图神经网络（Graph Neural Networks，GNN）、门控图神经网络（Gated Graph Neural Networks，GGNN）和 Stochastic Steady-state Embedding (SSE)。后者涉及了：Message Passing Neural Networks (MPNN)、GraphSage。此外，这部分还介绍了这两大类之外的空间 GCN 变体，包括 Diffusion Convolution Neural Networks (DCNN)、PATCHY-SAN、Large-scale Graph Convolution Networks (LGCN)、Mixture Model Network (MoNet)。
SSE 算法。
这一章还从效率、通用性和灵活性方面，对比了基于谱的 GCN 和基于空间的 GCN，认为基于空间的 GCN 更具优势，也因此吸引了更多研究兴趣。
5 图卷积网络之外的模型
这部分概述了图卷积网络之外的其他图神经网络，包括图注意力神经网络、图自编码器、图生成模型和图时空网络。下表总结了每个类别下的主要方法。
表 4：图卷积网络之外的其他图神经网络概览。该表根据网络的输入、输出、目标任务和是否基于 GCN 总结了每种网络下的多种方法。输入列代表每种方法适合分布式图 (A)、有向图 (D) 还是时空图 (S)。
5.1 图注意力网络
注意力机制几乎成为序列任务中的标配。它的价值在于能够聚焦于对象最重要的部分。该机制被证明在多项任务中有用，如机器翻译和自然语言理解。由于注意力机制的模型容量越来越大，图神经网络在聚合信息、集成多个模型的输出、生成重要性导向的随机游走时，可以从注意力机制中获益良多。
这部分介绍了图注意力网络的多种方法，包括图注意力网络（Graph Attention Network，GAT）、门控注意力网络（Gated Attention Network，GAAN）、图注意力模型（Graph Attention Model，GAM）、注意力游走（Attention Walks）。
注意力机制对图神经网络的贡献有三部分，即在聚合特征信息时向不同近邻分配注意力权重、根据注意力权重集成多个模型，以及使用注意力权重引导随机游走。尽管我们把 GAT 和 GAAN 分类为图注意力网络的两种方法，但是它们都可以作为基于空间的卷积网络。二者的优势是它们可以适应性地学习近邻的重要性权重（如图 6 所示）。但是，由于我们必须计算每对近邻之间的注意力权重，因此计算成本和内存消耗会快速增长。
5.2 图自编码器
图自编码器是一类网络嵌入方法，旨在通过神经网络架构将网络顶点表征到低维向量空间。典型的解决方案是使用多层感知机作为编码器来获取节点嵌入，解码器重建节点的近邻统计，如正逐点互信息（positive pointwise mutual information，PPMI）或一阶、二阶接近度（proximities）[42]。最近，研究人员尝试在设计图自编码器时用 GCN 作为编码器、结合 GCN 和 GAN，或者结合 LSTM 和 GAN。
这部分介绍了基于 GCN 的自编码器和其他变体。基于 GCN 的自编码器部分介绍了：图自编码器（Graph Auto-encoder，GAE）、对抗正则化图自编码器（Adversarially Regularized Graph Autoencoder，ARGA）。其他变体包括：具备对抗正则化自编码器的网络表征（Network Representations with Adversarially Regularized Autoencoders，NetRA）、用于图表征的深度神经网络（Deep Neural Networks for Graph Representations，DNGR）、结构化深度网络嵌入（Structural Deep Network Embedding，SDNE）、深度递归网络嵌入（Deep Recursive Network Embedding，DRNE）。
DNGR 和 SDNE 仅基于拓扑结构学习节点嵌入，而 GAE、ARGA、NetRA 和 DRNE 需要基于拓扑信息和节点内容特征学习节点嵌入。图自编码器的一个挑战是邻接矩阵的稀疏性，会导致解码器正条目（positive entry）的数量远远少于负条目。为了解决这个问题，DNGR 重建了一个较稠密的矩阵——PPMI 矩阵，SDNE 对邻接矩阵的零条目进行惩罚，GAE 重新调整邻接矩阵中项的权重，NetRA 将图线性化为序列。
5.3 图生成网络
图生成网络的目标是基于一组可观察图来生成图。其中的很多方法都是领域特定的。例如，在分子图生成方面，一些研究将分子图的表征建模为字符串 SMILES [94], [95], [96], [97]。在自然语言处理中，生成语义图或知识图通常需要一个给定的句子 [98], [99]。最近，研究人员又提出了多个通用方法。一些研究将生成过程看成节点或边的形成 [64], [65]，而另一些则使用生成对抗训练 [66], [67]。该领域的方法要么使用 GCN 作为构造块，要么使用不同的架构。
这部分介绍了基于 GCN 的图生成网络和其他图生成网络。前者包括：分子生成对抗网络（Molecular Generative Adversarial Networks，MolGAN）和深度图生成模型（Deep Generative Models of Graphs，DGMG）；后者涉及 GraphRNN（通过两级循环神经网络使用深度图生成模型）和 NetGAN（结合 LSTM 和 Wasserstein GAN 从基于随机游走的方法中生成图）。
图 9：MolGAN 框架图示。
5.4 图时空网络
图时空网络同时捕捉时空图的时间和空间依赖。时空图具备全局图结构，每个节点的输入随着时间而改变。例如在交通网络中，使用每个传感器作为节点来连续记录某条道路的交通流动速度，其中交通网络的边由传感器对之间的距离决定。图时空网络的目标是预测未来节点值或标签，或预测时空图标签。近期研究探索了仅使用 GCN、结合 GCN 和 RNN 或 CNN，以及专用于图结构的循环架构。
这部分介绍了基于 GCN 的图时空网络和其他图时空网络。前者包括：Diffusion Convolutional Recurrent Neural Network (DCRNN)、CNN-GCN、时空 GCN（Spatial Temporal GCN，ST-GCN）。其他方法有 Structural-RNN，一种循环结构化框架。
DCRNN 的优势是能够处理长期依赖，因为它具备循环网络架构。尽管 CNN-GCN 比 DCRNN 简单一些，但 CNN-GCN 能够更高效地处理时空图，这要归功于 1D CNN 的快速实现。时空 GCN 将时间流作为图的边，这导致邻接矩阵的大小呈平方增长。一方面，它增加了图卷积层的计算成本。另一方面，要捕捉长期依赖，图卷积层必须多次堆叠。StructuralRNN 在同一个语义组内共享相同的 RNN，从而改善了模型效率，但是 StructuralRNN 需要人类先验知识来分割语义组。
6 应用
图神经网络应用广泛。下面将首先介绍在文献中频繁使用的基准数据集。接着将报告各种方法在四种常用数据集上的基准性能，并列出可用的图神经网络开源实现。最后，我们将介绍图神经网络在各个领域的实际应用案例。
6.1 数据集
表 5：常用数据集总结。
6.2 基准和开源实现
表 6：各种方法在四种最常用数据集上的基准性能。以上列出的方法都使用相同的训练、验证和测试数据集进行评估。
表 7：开源实现概览。
6.3 实际应用案例
本文按领域介绍了 GNN 的应用，包括计算机视觉、推荐系统、交通、化学等。
7 未来方向
加深网络。深度学习的成功在于深度神经架构。例如在图像分类中，模型 ResNet 具有 152 层。但在图网络中，实证研究表明，随着网络层数增加，模型性能急剧下降 [147]。根据论文 [147]，这是由于图卷积的影响，因为它本质上推动相邻节点的表示更加接近彼此，所以理论上，通过无限次卷积，所有节点的表示将收敛到一个点。这导致了一个问题：加深网络是否仍然是学习图结构数据的好策略？
感受野。节点的感受野是指一组节点，包括中心节点和其近邻节点。节点的近邻（节点）数量遵循幂律分布。有些节点可能只有一个近邻，而有些节点却有数千个近邻。尽管采用了采样策略 [24], [26], [27]，但如何选择节点的代表性感受野仍然有待探索。
可扩展性。大部分图神经网络并不能很好地扩展到大型图上。主要原因是当堆叠一个图卷积的多层时，节点的最终状态涉及其大量近邻节点的隐藏状态，导致反向传播变得非常复杂。虽然有些方法试图通过快速采样和子图训练来提升模型效率 [24], [27]，但它们仍无法扩展到大型图的深度架构上。
动态性和异质性。大多数当前的图神经网络都处理静态同质图。一方面，假设图架构是固定的。另一方面，假设图的节点和边来自同一个来源。然而，这两个假设在很多情况下是不现实的。在社交网络中，一个新人可能会随时加入，而之前就存在的人也可能退出该社交网络。在推荐系统中，产品可能具有不同的类型，而其输出形式也可能不同，也许是文本，也许是图像。因此，应当开发新方法来处理动态和异质图结构。