【GNN】高被引图神经网络（GNN）全面综述论文_a comprehensive survey on graph neural networks下载

论文名称：A Comprehensive Survey on Graph Neural Networks
论文下载：https://arxiv.org/abs/1901.00596
论文年份：TNNLS 2020
论文被引：3203（2022/04/23）

个人笔记：

Abstract

Deep learning has revolutionized many machine learning tasks in recent years, ranging from image classification and video processing to speech recognition and natural language understanding. The data in these tasks are typically represented in the Euclidean space. However, there is an increasing number of applications where data are generated from non-Euclidean domains and are represented as graphs with complex relationships and interdependency between objects. The complexity of graph data has imposed significant challenges on existing machine learning algorithms. Recently, many studies on extending deep learning approaches for graph data have emerged. In this survey, we provide a comprehensive overview of graph neural networks (GNNs) in data mining and machine learning fields. We propose a new taxonomy to divide the state-of-the-art graph neural networks into four categories, namely recurrent graph neural networks, convolutional graph neural networks, graph autoencoders, and spatial-temporal graph neural networks. We further discuss the applications of graph neural networks across various domains and summarize the open source codes, benchmark data sets, and model evaluation of graph neural networks. Finally, we propose potential research directions in this rapidly growing field.

近年来，深度学习彻底改变了许多机器学习任务，从图像分类和视频处理到语音识别和自然语言理解。这些任务中的数据通常在欧几里得空间中表示。然而，越来越多的应用程序将数据从非欧几里德域生成并表示为具有复杂关系和对象之间相互依赖关系的图。图数据的复杂性对现有的机器学习算法提出了重大挑战。最近，出现了许多关于扩展图数据深度学习方法的研究。在本次调查中，我们全面概述了数据挖掘和机器学习领域中的图神经网络 (graph neural networks, GNN)。我们提出了一种新的分类法，将最先进的图神经网络分为四类，即：

• 循环图神经网络（recurrent graph neural networks，RecGNN）
• 卷积图神经网络（convolutional graph neural networks，ConvGNN）
• 图自动编码器（graph autoencoders，GAE）
• 时空图神经网络（spatial-temporal graph neural networks，STGNN）

我们进一步讨论了图神经网络在各个领域的应用，并总结了图神经网络的开源代码、基准数据集和模型评估。最后，我们在这个快速发展的领域提出了潜在的研究方向。

I. INTRODUCTION

神经网络最近的成功推动了模式识别和数据挖掘的研究。许多机器学习任务，如对象检测 [1]、[2]、机器翻译 [3]、[4] 和语音识别 [5]，曾经严重依赖手工特征工程来提取信息特征集，最近已经由各种端到端深度学习范式彻底改变，例如卷积神经网络 (CNN) [6]、递归神经网络 (RNN) [7] 和自动编码器 [8]。深度学习在许多领域的成功部分归功于快速发展的计算资源（例如 GPU）、大训练数据的可用性以及深度学习从欧几里得数据（例如图像、文本、和视频）。以图像数据为例，我们可以将图像表示为欧几里得空间中的规则网格。卷积神经网络 (CNN) 能够利用图像数据的移位不变性、局部连通性和组合性 [9]。因此，CNN 可以提取与整个数据集共享的局部有意义的特征，用于各种图像分析。

虽然深度学习有效地捕获了欧几里得数据的隐藏模式，但越来越多的应用程序以图形的形式表示数据。例如，

• 在电子商务中，基于图的学习系统可以利用用户和产品之间的交互来做出高度准确的推荐。
• 在化学中，分子被建模为图形，并且需要确定它们的生物活性以进行药物发现。
• 在引文网络中，论文通过引文相互链接，并且需要将它们分类到不同的组中。

图数据的复杂性对现有的机器学习算法提出了重大挑战。

• 由于图可能是不规则的，图可能具有可变大小的无序节点，并且来自图中的节点可能具有不同数量的邻居，导致一些重要的操作（例如卷积）在图像域中很容易计算，但是难以应用于图域。
• 此外，现有机器学习算法的一个核心假设是样本相互独立。这个假设不再适用于图数据，因为每个实例（节点）都通过各种类型的链接（例如引用、友谊和交互）与其他实例相关联。

最近，人们对扩展图形数据的深度学习方法越来越感兴趣。受来自深度学习的 CNN、RNN 和自动编码器的推动，在过去几年中，重要操作的新泛化和定义得到了迅速发展，以处理图数据的复杂性。例如，可以从 2D 卷积推广图卷积。如图 1 所示，可以将图像视为图形的特殊情况，其中像素由相邻像素连接。与 2D 卷积类似，可以通过取节点邻域信息的加权平均值来执行图卷积。

关于图神经网络 (GNN) 主题的现有综述数量有限。

• Bronstein et al. [9] 使用术语几何深度学习（geometric deep learning），概述了非欧几里得领域中的深度学习方法，包括图和流形。这是对 GNN 的第一次综述，主要回顾了卷积 GNN。
• Hamilton et al. [10] 涵盖了有限数量的 GNN，重点是解决网络嵌入问题。
• Battaglia et al. [11] 将图网络定位为从关系数据中学习的构建块，在统一框架下回顾 GNN 的一部分。
• Lee et al. [12] 对应用不同注意机制的 GNN 进行了部分调查。

总之，现有的调查只包括一些 GNN 并检查了有限数量的作品，因此错过了 GNN 的最新发展。我们的调查为想要进入这个快速发展的领域的感兴趣的研究人员和想要比较 GNN 模型的专家提供了 GNN 的全面概述。为了涵盖更广泛的方法，本调查将 GNN 视为图形数据的所有深度学习方法。

我们的论文做出了显著的贡献，总结如下：

• 新分类法：我们提出了一种新的图神经网络分类法。图神经网络分为四类：循环图神经网络、卷积图神经网络、图自动编码器和时空图神经网络。
• 综合回顾：我们提供了最全面的图数据现代深度学习技术概述。对于每种类型的图神经网络，我们都提供了代表性模型的详细描述，进行了必要的比较，并总结了相应的算法。
• 丰富的资源：我们收集了丰富的图神经网络资源，包括最先进的模型、基准数据集、开源代码和实际应用。本调查可用作理解、使用和开发适用于各种现实生活应用的不同深度学习方法的实践指南。
• 未来方向：我们讨论了图神经网络的理论方面，分析了现有方法的局限性，并在模型深度、可扩展性权衡、异质性和动态性方面提出了四个可能的未来研究方向。

我们的调查组织 本调查的其余部分组织如下。第二节概述了图神经网络的背景，列出了常用的符号，并定义了与图相关的概念。第三节阐明了图神经网络的分类。第 IV-VII 节概述了图神经网络模型。第 VIII 节介绍了跨各个领域的应用程序集合。第九节讨论了当前的挑战并提出了未来的方向。第 X 节总结了本文。

II. BACKGROUND & DEFINITION

在本节中，我们概述了图神经网络的背景，列出了常用的符号，并定义了图相关的概念。

A. Background

图神经网络简史。

Sperduti et al. (1997) [13] 首次将神经网络应用于有向无环图，这激发了对 GNN 的早期研究。图神经网络的概念最初是在 Goriet al. (2005) [14] 中概述的。并在 Scarselli et al. (2009) [15] 和 Gallicchio et al. (2010) [16] 中进一步阐述。这些早期研究属于循环图神经网络（RecGNNs）的范畴。他们通过以迭代方式传播邻居信息来学习目标节点的表示，直到达到一个稳定的固定点。这个过程在计算上是昂贵的，并且最近已经越来越多地努力克服这些挑战 [17]，[18]。

受 CNN 在计算机视觉领域的成功的鼓舞，大量重新定义图数据卷积概念的方法被并行开发。这些方法属于卷积图神经网络 (ConvGNN) 的范畴。 ConvGNN 分为两个主流，基于光谱的 (spectral-based) 方法和基于空间 (spatial-based) 的方法。Bruna 等人（2013）[19] 提出了第一个关于基于光谱的 ConvGNN 的杰出研究，它开发了一种基于谱图理论的图卷积。从那时起，基于谱的 ConvGNN [20]、[21]、[22]、[23] 的改进、扩展和近似值不断增加。基于空间的 ConvGNN 的研究比基于光谱的 ConvGNN 早得多。 2009 年，Micheli 等人 [24] 首先通过架构复合非递归层解决了图相互依赖问题，同时继承了 RecGNN 的消息传递思想。然而，这项工作的重要性被忽视了。直到最近，出现了许多基于空间的 ConvGNN（例如，[25]、[26]、[27]）。代表性 RecGNNs 和 ConvGNNs 的时间线如表 II 的第一列所示。除了 RecGNNs 和 ConvGNNs，在过去几年中还开发了许多替代 GNN，包括图自动编码器 (GAE) 和时空图神经网络 (STGNN)。这些学习框架可以建立在 RecGNN、ConvGNN 或其他用于图建模的神经架构上。第 III 节给出了这些方法分类的详细信息。

图神经网络与网络嵌入 (Graph neural networks vs. network embedding)

GNN 的研究与图嵌入或网络嵌入密切相关，这是另一个越来越受到数据挖掘和机器学习社区关注的话题 [10]、[28]、[29]、[30 ]，[31]，[32]。网络嵌入旨在将网络节点表示为低维向量表示，同时保留网络拓扑结构和节点内容信息，以便任何后续的图分析任务，如分类、聚类和推荐，都可以使用简单的现成的轻松执行机器学习算法（例如，用于分类的SVM）。同时，GNN 是深度学习模型，旨在以端到端的方式解决与图相关的任务。许多 GNN 显式提取高级表示。 GNN 和网络嵌入之间的主要区别在于，GNN 是一组为各种任务设计的神经网络模型，而网络嵌入涵盖了针对同一任务的各种方法。因此，GNN 可以通过图自动编码器框架解决网络嵌入问题。另一方面，网络嵌入包含其他非深度学习方法，例如矩阵分解[33]、[34]和随机游走[35]。

图神经网络与图核方法 (Graph neural networks vs. graph kernel methods )

图核在历史上是解决图分类问题的主要技术 [36]、[37]、[38]。这些方法采用核函数来测量图对之间的相似性，以便基于核的算法（如支持向量机）可用于图的监督学习。与 GNN 类似，图核可以通过映射函数将图或节点嵌入到向量空间中。不同之处在于这个映射函数是确定性的而不是可学习的。由于成对相似度计算，图核方法严重受到计算瓶颈的影响。一方面，GNN 直接基于提取的图表示进行图分类，因此比图核方法更有效。对于图核方法的进一步回顾，推荐阅读 [39]。

B. Definition

在本文中，我们使用粗体大写字符表示矩阵，粗体小写字符表示向量。除非特别说明，本文中使用的符号如表 I 所示。现在我们定义理解本文所需的最小定义集。

定义 1（图，Graph）：图表示为 $G=(V,E)$，其中 $V$ 是顶点或节点的集合（我们将在整个论文中使用节点），$E$ 是边的集合。

• 令 $v_i\in V$ 表示一个节点， $e_{ij}=(v_i,v_j)\in E$ 表示一条从 $v_j$ 指向 $v_i$ 的边。节点 $v$ 的邻域定义为 N ( v ) = { u ∈ V ∣ ( v , u ) ∈ E } N(v) = \{u ∈ V |(v, u) ∈ E\} N(v)={u∈V∣(v,u)∈E}。
• 邻接矩阵 $A$ 是一个 $n\times n$ 矩阵，如果 $e_{ij}\in E$，则 $A_{ij}$ = 1，如果 $e_{ij}\notin E$，则 $A_{ij}$ = 0。
• 图可能具有节点属性 $X$，其中 $X\in R^{n\times d}$ 是节点特征矩阵，$x_v\in R^d$ 表示节点 $v$ 的特征向量。
• 图可能具有边属性 $X^e$，其中 $X^e\in R^{m\times c}$ 是边特征矩阵，$x_{v,u}^e\in R^c$ 表示边 $(v,u)$ 的特征向量。

定义2（有向图，Directed Graph）：有向图是所有边都从一个节点指向另一个节点的图。无向图被认为是有向图的一种特殊情况，如果两个节点相连，则有一对反向的边。一个图是无向的，当且仅当邻接矩阵是对称的。

定义3（时空图，Spatial-Temporal Graph）：时空图是一个属性图，其中节点属性随时间动态变化。时空图定义为 $G^{(t)}=(V,E,X^{(t)})$，其中 $X^{(t)}\in R^{n\times d}$。

III. CATEGORIZATION AND FRAMEWORKS

在本节中，我们介绍了图神经网络 (GNN) 的分类，如表 II 所示。我们将图神经网络 (GNN) 分为循环图神经网络 (RecGNN)、卷积图神经网络 (ConvGNN)、图自动编码器 (GAE) 和时空图神经网络 (STGNN)。图 2 给出了各种模型架构的示例。下面，我们对每个类别进行简要介绍。

A. Taxonomy of Graph Neural Networks (GNNs)

循环图神经网络（RecGNNs）大多是图神经网络的先驱作品。 RecGNN 旨在学习具有循环神经架构的节点表示。他们假设图中的一个节点不断地与其邻居交换信息/消息，直到达到稳定的平衡。 RecGNN 在概念上很重要，并启发了后来对卷积图神经网络的研究。特别是，基于空间的卷积图神经网络继承了消息传递的思想。

卷积图神经网络 (ConvGNNs) 将卷积操作从网格数据推广到图数据。主要思想是通过聚合它自己的特征 $x_v$ 和邻居的特征 $x_u$ 来生成节点 $v$ 的表示，其中 $u\in N(v)$。与 RecGNN 不同，ConvGNN 堆叠多个图卷积层以提取高级节点表示。 ConvGNN 在构建许多其他复杂的 GNN 模型中发挥着核心作用。图 2a 显示了用于节点分类的 ConvGNN。图 2b 展示了用于图分类的 ConvGNN。

图自动编码器 (GAE) 是无监督学习框架，它将节点/图编码到潜在向量空间并从编码信息中重建图数据。 GAE 用于学习网络嵌入和图形生成分布。对于网络嵌入，GAE 通过重构图结构信息（例如图邻接矩阵）来学习潜在节点表示。对于图的生成，一些方法逐步生成图的节点和边，而另一些方法一次全部输出图。图 2c 展示了一个用于网络嵌入的 GAE。

时空图神经网络 (STGNNs) 旨在从时空图中学习隐藏模式，这在各种应用中变得越来越重要，例如交通速度预测 [72]、驾驶员机动预期 [73] 和人类动作识别 [ 75]。 STGNN 的关键思想是同时考虑空间依赖和时间依赖。许多当前的方法集成了图卷积来捕获空间依赖性，并使用 RNN 或 CNN 对时间依赖性进行建模。图 2d 说明了用于时空图预测的 STGNN。

B. Frameworks

以图结构和节点内容信息作为输入，GNN 的输出可以通过以下机制之一专注于不同的图分析任务：

节点级（Node-level）输出与节点回归和节点分类任务相关。RecGNNs 和 ConvGNNs 可以通过信息传播/图卷积提取高级节点表示。使用多感知器或 softmax 层作为输出层，GNN 能够以端到端的方式执行节点级任务。

边缘级（Edge-level）输出与边缘分类和链接预测任务相关。将来自 GNN 的两个节点的隐藏表示作为输入，可以利用相似函数或神经网络来预测边缘的标签/连接强度。

图级（Graph-level）输出与图分类任务相关。为了在图级别上获得紧凑的表示，GNN 通常与池化和读出（readout，本质上是求和或者均值操作）操作相结合。有关池化和 readout 的详细信息将在第 V-C 节中进行回顾。

训练框架。许多 GNN（例如，ConvGNN）可以在端到端学习框架内以（半）监督或纯无监督的方式进行训练，具体取决于手头可用的学习任务和标签信息。

• 用于节点级分类的半监督学习。给定一个网络，其中部分节点被标记而其他节点未标记，ConvGNNs 可以学习一个强大的模型，该模型有效地识别未标记节点的类标签 [22]。为此，可以通过堆叠几个图卷积层和一个用于多类分类的 softmax 层来构建端到端框架。
• 图级分类的监督学习。图级分类旨在预测整个图的类标签 [52]、[54]、[78]、[79]。该任务的端到端学习可以通过图卷积层、图池化层和/或读出层的组合来实现。虽然图卷积层负责精确的高级节点表示，但图池化层起着下采样的作用，每次都将每个图粗化为一个子结构。读出层将每个图的节点表示折叠成一个图表示。通过将多层感知器和 softmax 层应用于图形表示，我们可以构建一个端到端的图形分类框架。图 2b 给出了一个例子。
• 图嵌入的无监督学习。当图中没有可用的类标签时，我们可以在端到端框架中以纯无监督的方式学习图嵌入。这些算法以两种方式利用边缘级信息。一种简单的方法是采用自动编码器框架，其中编码器采用图卷积层将图嵌入到潜在表示中，解码器用于重建图结构[61]，[62]。另一种流行的方法是利用负采样方法，该方法将部分节点对采样为负对，而在图中具有链接的现有节点对是正对。然后应用逻辑回归层来区分正负对[42]。

在表 III 中，我们总结了代表性 RecGNN 和 ConvGNN 的主要特征。在各种模型之间比较输入源、池化层、读出层和时间复杂度。更详细地说，我们只比较每个模型中消息传递/图卷积操作的时间复杂度。由于[19]和[20]中的方法需要特征值分解，时间复杂度为O(n3)。由于节点成对最短路径计算，[46] 的时间复杂度也是 O(n3)。其他方法会产生等效的时间复杂度，如果图邻接矩阵是稀疏的，则为 O(m)，否则为 O(n2)。这是因为在这些方法中，每个节点 vi 的表示的计算都涉及到它的 di 邻居，并且所有节点上的 di 之和正好等于边的数量。表 III 中缺少几种方法的时间复杂度。这些方法要么在他们的论文中缺乏时间复杂度分析，要么报告其整体模型或算法的时间复杂度。

IV. RECURRENT GRAPH NEURAL NETWORKS

递归图神经网络（RecGNNs）大多是 GNNs 的先驱作品。他们在图中的节点上反复应用相同的参数集以提取高级节点表示。受计算能力的限制，早期的研究主要集中在有向无环图[13]、[80]。

Scarselli 等人提出的图神经网络 ($GN{N}^{\ast }$)。扩展了先前的循环模型以处理一般类型的图，例如无环图、循环图、有向图和无向图 [15]。基于信息扩散机制，$GN{N}^{\ast }$ 通过反复交换邻域信息来更新节点的状态，直到达到稳定的平衡。节点的隐藏状态通过以下方式反复更新

其中 $f(\cdot )$ 是参数函数，$h_v^{(0)}$ 是随机初始化的。求和运算使 GNN* 适用于所有节点，即使相邻节点的数量不同且不知道相邻节点的顺序。为了确保收敛，循环函数 $f(\cdot )$ 必须是收缩映射 (contraction mapping)，它在将两点投影到潜在空间后收缩两点之间的距离。在 $f(\cdot )$ 是神经网络的情况下，必须对参数的雅可比矩阵施加惩罚项。当满足收敛标准时，最后一步节点隐藏状态被转发到读出层。 GNN* 交替进行节点状态传播阶段和参数梯度计算阶段以最小化训练目标。该策略使 GNN 能够处理循环图*。在后续工作中，Graph Echo State Network (GraphESN) [16] 扩展了回声状态网络以提高 GNN* 的训练效率。 GraphESN 由编码器和输出层组成。编码器是随机初始化的，不需要训练。它实现了一个收缩状态转换函数来循环更新节点状态，直到全局图状态达到收敛。之后，通过将固定节点状态作为输入来训练输出层。

门控图神经网络（GGNN）[17]采用门控循环单元（GRU）[81]作为循环函数，将循环减少到固定的步数。优点是不再需要约束参数来确保收敛。节点隐藏状态由其先前的隐藏状态及其相邻隐藏状态更新，定义为

其中 $h_v^{(0)}=x_v$ 。与 GNN* 和 GraphESN 不同，GGNN 使用时间反向传播 (BPTT) 算法来学习模型参数。这对于大型图可能是有问题的，因为 GGNN 需要在所有节点上多次运行循环函数，需要将所有节点的中间状态存储在内存中。

随机稳态嵌入 (SSE) 提出了一种学习算法，该算法对大图更具可扩展性 [18]。 SSE 以随机和异步的方式反复更新节点隐藏状态。它交替地对一批节点进行状态更新和一批节点进行梯度计算。为了保持稳定性，将 SSE 的循环函数定义为历史状态和新状态的加权平均值，其形式为

其中 α 是一个超参数，$h_v^{(0)}$ 是随机初始化的。虽然在概念上很重要，但 SSE 并没有从理论上证明节点状态会通过重复应用公式 3 逐渐收敛到固定点。

V. CONVOLUTIONAL GRAPH NEURAL NETWORKS

卷积图神经网络 (ConvGNNs) 与循环图神经网络密切相关。 ConvGNN 不是使用收缩约束来迭代节点状态，而是在架构上使用固定数量的层在每层中具有不同权重来解决循环相互依赖关系。这一关键区别如图 3 所示。由于图卷积更有效且更方便地与其他神经网络组合，因此近年来 ConvGNN 的流行度迅速增长。 ConvGNN 分为两类，基于光谱的和基于空间的。基于谱的方法通过从图信号处理的角度引入滤波器来定义图卷积[82]，其中图卷积操作被解释为从图信号中去除噪声。基于空间的方法继承了 RecGNN 的思想，通过信息传播来定义图卷积。由于 GCN [22] 弥合了基于光谱的方法和基于空间的方法之间的差距，因此基于空间的方法由于其具有吸引力的效率、灵活性和通用性而最近迅速发展。

A. Spectral-based ConvGNNs

背景

基于谱的方法在图信号处理方面具有坚实的数学基础 [82]、[83]、[84]。他们假设图是无向的。归一化图拉普拉斯矩阵是无向图的数学表示，定义为 $L=I_n-D^{-1/2}A{D}^{-1/2}$ ，其中 $D$ 是节点度数的对角矩阵，$D_{ii}={\sum }_j(A_{i,j})$。归一化图拉普拉斯矩阵具有实对称正半定性质。有了这个性质，归一化拉普拉斯矩阵可以分解为 $L=U\Lambda U^T$ ，其中 $U=[u_0,u_1,\cdot \cdot \cdot ,u_{n-1}]\in R^{n\times n}$ 是按特征值排序的特征向量矩阵，$\Lambda$ 是对角矩阵特征值（谱），${\Lambda }_{ii}={\lambda }_i$。归一化拉普拉斯矩阵的特征向量形成一个正交空间，用数学术语 $U^{T}U=I$。在图信号处理中，图信号 $x\in R^n$ 是图的所有节点的特征向量，其中 $x_i$ 是第 $i$ 个节点的值。图傅里叶变换到信号 $x$ 定义为 $F(x)=U^{T}x$，逆图傅里叶变换定义为 $F^{-1}(\hat{x})=U\hat{x}$，其中 $\hat{x}$ 表示图傅里叶变换的结果信号。图傅里叶变换将输入图信号投影到正交空间，其中基由归一化图拉普拉斯算子的特征向量形成。变换后的信号 $\hat{x}$ 的元素是图信号在新空间中的坐标，因此输入信号可以表示为 $x={\sum }_i{\hat{x}}_i{u}_i$，这正是图傅里叶逆变换。现在输入信号 $x$ 与滤波器 $g\in R^n$ 的图卷积定义为

频谱卷积神经网络 (Spectral CNN) [19] 假设滤波器 $g_{\theta }={\Theta }_{i,j}^{(k)}$ 是一组可学习的参数，并考虑具有多个通道的图形信号。 Spectral CNN 的图卷积层定义为

其中 $k$ 是层索引，$H^{(k-1)}\in R^{n\times f_{k-1}}$ 是输入图信号，$H^0=X$，$f_{k-1}$ 是输入通道数，$f_k$ 是输出通道数， ${\Theta }_{i,j}^{(k)}$ 是一个填充了可学习参数的对角矩阵。由于拉普拉斯矩阵的特征分解，Spectral CNN 面临三个限制。

• 首先，对图的任何扰动都会导致特征基的变化。
• 其次，学习到的滤波器是域相关的（domain dependent），这意味着它们不能应用于具有不同结构的图。
• 第三，特征分解需要 O(n3) 的计算复杂度。在后续工作中，ChebNet [21] 和 GCN [22] 通过进行一些近似和简化，将计算复杂度降低到 O(m)。
  

作为对 Spectral CNN 的改进，ChebNet 定义的滤波器是在空间中定位的，这意味着滤波器可以独立于图形大小提取局部特征。 ChebNet 的频谱线性映射到 [−1, 1]。 CayleyNet [23] 进一步应用 Cayley 多项式是参数有理复函数来捕获窄频带。 CayleyNet的谱图卷积定义为

其中 Re(·) 返回复数的实部，c0 是实数系数，cj 是复数系数，i 是虚数，h 是控制 Cayley 滤波器频谱的参数。在保留空间局部性的同时，CayleyNet 表明 ChebNet 可以被视为 CayleyNet 的一个特例。

图卷积网络 (GCN) [22] 引入了 ChebNet 的一阶近似。假设 K = 1 和 λmax = 2 ，公式 8 简化为

最近的几项工作通过探索替代对称矩阵对 GCN [22] 进行了增量改进。

• 自适应图卷积网络（AGCN）[40] 学习图邻接矩阵未指定的隐藏结构关系。它通过以两个节点的特征作为输入的可学习距离函数构造所谓的残差图邻接矩阵。

• Dual 图卷积网络 (DGCN) [41] 引入了一种双图卷积架构，具有两个并行的图卷积层。虽然这两层共享参数，但它们使用归一化邻接矩阵 ¯A 和正点互信息 (PPMI) 矩阵，该矩阵通过从图中采样的随机游走捕获节点共现信息。 PPMI 矩阵定义为
  

  其中 $v_1,v_2\in V,|D|={\sum }_{v_1,v_2}count(v_1,v_2)$ 和 $count(\cdot )$ 函数返回节点 $v$ 和/或节点 $u$ 在抽样随机游走中同时出现/出现的频率。通过集成双图卷积层的输出，DGCN 对局部和全局结构信息进行编码，而无需堆叠多个图卷积层。

B. Spatial-based ConvGNNs

类似于传统 CNN 对图像的卷积操作，基于空间的方法以节点的空间关系定义图卷积。图像可以被认为是一种特殊形式的图形，每个像素代表一个节点。每个像素都直接连接到其附近的像素，如图 1a 所示。通过对每个通道的中心节点及其相邻节点的像素值进行加权平均，将过滤器应用于 3 × 3 补丁 (patch)。类似地，基于空间的图卷积将中心节点的表示与其相邻节点的表示进行卷积，以得出中心节点的更新表示，如图 1b 所示。从另一个角度来看，基于空间的 ConvGNN 与 RecGNN 共享信息传播/消息传递的相同思想。空间图卷积操作本质上是沿边传播节点信息。

与 GNN* 并行提出的图神经网络 (NN4G) [24] 是针对基于空间的 ConvGNN 的第一项工作。与 RecGNN 明显不同的是，NN4G 通过在每一层具有独立参数的组合神经架构来学习图的相互依赖关系。节点的邻域可以通过架构的增量构建来扩展。 NN4G 通过直接总结节点的邻域信息来执行图卷积。它还应用残差连接和跳过连接来记忆每一层的信息。因此，NN4G 通过以下方式导出其下一层节点状态

这类似于 GCN [22] 的形式。一个区别是 NN4G 使用未归一化的邻接矩阵，这可能会导致隐藏节点状态具有极其不同的尺度。上下文图马尔可夫模型（CGMM）[47]提出了一种受NN4G启发的概率模型。在保持空间局部性的同时，CGMM 具有概率可解释性的优点。

扩散卷积神经网络（DCNN）[25]将图卷积视为扩散过程。它假设信息以一定的转移概率从一个节点转移到其相邻节点之一，使得信息分布在几轮后达到平衡。 DCNN 将扩散图卷积定义为

使用转移概率矩阵的幂意味着远邻向中心节点贡献的信息非常少。 PGC-DGCNN [46] 基于最短路径增加远邻的贡献。它定义了一个最短路径邻接矩阵 $S^{(j)}$。如果从节点 v 到节点 u 的最短路径长度为 j，则 $S_{v,u}^{(j)}=1$ 否则为 0。使用超参数 r 来控制感受野大小，PGC-DGCNN 引入如下图卷积操作

最短路径邻接矩阵的计算可能很昂贵，最大为 O(n3)。分区图卷积（PGC）[75]根据某些不限于最短路径的标准将节点的邻居划分为 Q 个组。 PGC 根据每组定义的邻域构造Q个邻接矩阵。然后，PGC 将具有不同参数矩阵的 GCN [22] 应用于每个邻居组并对结果求和：

消息传递神经网络 (MPNN) [27] 概述了基于空间的 ConvGNN 的一般框架。它将图卷积视为消息传递过程，其中信息可以直接沿边从一个节点传递到另一个节点。 MPNN 运行 K 步消息传递迭代以让信息进一步传播。消息传递函数（即空间图卷积）定义为

在推导出每个节点的隐藏表示之后，$h_v^{(K)}$ 可以传递到输出层以执行节点级预测任务或传递到读出函数以执行图级预测任务。读出函数基于节点隐藏表示生成整个图的表示。一般定义为

其中 R(·) 表示具有可学习参数的读出函数。 MPNN 可以通过假设不同形式的 Uk(·)、Mk(·) 和 R(·) 来覆盖许多现有的 GNN，例如 [22]、[85]、[86]、[87]。然而，图同构网络 (GIN) [57] 发现，以前基于 MPNN 的方法无法根据它们产生的图嵌入来区分不同的图结构。为了弥补这个缺点，GIN 通过一个可学习的参数 ${ϵ}^{(k)}$ 来调整中心节点的权重。它通过以下方式执行图卷积

由于节点的邻居数量可以从一到一千甚至更多不等，因此获取节点邻居的全部大小是低效的。 GraphSage [42] 采用采样为每个节点获取固定数量的邻居。它通过以下方式执行图卷积

聚合函数应该对节点排序的排列保持不变，例如均值、求和或最大值函数。

Graph Attention Network (GAT) [43] 假设相邻节点对中心节点的贡献既不像 GraphSage [42] 那样相同，也不像 GCN [22] 那样预先确定（这种差异如图 4 所示）。GAT 采用注意力机制来学习两个连接节点之间的相对权重。根据 GAT 的图卷积操作定义为，

其中 g(·) 是 LeakyReLU 激活函数，a 是可学习参数的向量。 softmax 函数确保节点 v 的所有邻居的注意力权重总和为 1。GAT 进一步执行多头注意力以增加模型的表达能力。这显示了 GraphSage 在节点分类任务上的显着改进。虽然 GAT 假设注意力头的贡献是相等的，但门控注意力网络 (GAAN) [48] 引入了一种自注意力机制，该机制为每个注意力头计算额外的注意力分数。除了在空间上应用图注意力，GeniePath [55] 还提出了一种类似 LSTM 的门控机制来控制跨图卷积层的信息流。还有其他可能感兴趣的图注意模型[88]，[89]。但是，它们不属于 ConvGNN 框架。

混合模型网络（MoNet）[44]采用不同的方法为节点的邻居分配不同的权重。它引入了节点伪坐标来确定节点与其邻居之间的相对位置。一旦知道两个节点之间的相对位置，权重函数就会将相对位置映射到这两个节点之间的相对权重。通过这种方式，图过滤器的参数可以在不同的位置共享。在 MoNet 框架下，几种关于流形（manifolds）的现有方法，例如 Geodesic CNN (GCNN) [90]、Anisotropic CNN (ACNN) [91]、Spline CNN [92]，以及 GCN [22]、DCNN [25] 等图通过构造非参数权重函数，可以将其概括为 MoNet 的特殊实例。 MoNet 还提出了一个具有可学习参数的高斯核来自适应地学习权重函数。

另一类不同的工作通过根据特定标准对节点的邻居进行排名并将每个排名与可学习的权重相关联来实现不同位置的权重共享。 PATCHY -SAN [26] 根据每个节点的图标签对每个节点的邻居进行排序，并选择前 q 个邻居。图标签本质上是节点分数，可以通过节点度、中心性和 WeisfeilerLehman 颜色 [93]、[94] 得出。由于每个节点现在都有固定数量的有序邻居，因此可以将图形结构数据转换为网格结构数据。 PATCHY-SAN 应用标准的 1D 卷积滤波器来聚合邻域特征信息，其中滤波器权重的顺序对应于节点邻居的顺序。 PATCHY-SAN的排名标准只考虑图结构，数据处理需要大量计算。大规模图卷积网络（LGCN）[45]根据节点特征信息对节点的邻居进行排名。对于每个节点，LGCN 组装一个由其邻域组成的特征矩阵，并沿每一列对该特征矩阵进行排序。排序后的特征矩阵的前 q 行作为中心节点的输入数据。

---

在训练效率方面的改进

训练卷积神经网络（如 GCN [22]）通常需要将整个图数据和所有节点的中间状态保存到内存中。 ConvGNNs 的全批训练算法受到内存溢出问题的严重影响，尤其是当一个图包含数百万个节点时。为了节省内存，GraphSage [42] 提出了一种用于 ConvGNN 的批量训练算法。它通过以固定样本大小将根节点的邻域递归地扩展 K 步来对以每个节点为根的树进行采样。对于每个采样树，GraphSage 通过从下到上分层聚合隐藏节点表示来计算根节点的隐藏表示。

使用图卷积网络进行快速学习 (FastGCN) [49] 为每个图卷积层采样固定数量的节点，而不是像 GraphSage [42] 那样为每个节点采样固定数量的邻居。它将图卷积解释为概率度量下节点嵌入函数的积分变换。蒙特卡洛近似和方差减少技术被用来促进训练过程。由于 FastGCN 为每一层独立采样节点，层间连接可能是稀疏的。Huang et al. [51] 提出了一种自适应逐层采样方法，其中下层的节点采样以顶层为条件。与 FastGCN 相比，这种方法以采用更复杂的采样方案为代价实现了更高的精度。

在另一项工作中，图卷积网络的随机训练 (StoGCN) [50] 使用历史节点表示作为控制变量，将图卷积的感受野大小减小到任意小规模。即使每个节点有两个邻居，StoGCN 也能实现相当的性能。然而，StoGCN 仍然需要保存所有节点的中间状态，这对于大图来说是非常消耗内存的。

Cluster-GCN [58] 使用图聚类算法对子图进行采样，并对采样子图中的节点执行图卷积。由于邻域搜索也被限制在采样子图中，Cluster-GCN 能够在更短的时间和更少的内存中同时处理更大的图并使用更深的架构。 ClusterGCN 特别为现有的 ConvGNN 训练算法提供了时间复杂度和内存复杂度的直接比较。我们根据表 IV 分析其结果。

在表 IV 中，GCN [22] 是进行全批次训练的基线方法。 GraphSage 以牺牲时间效率为代价来节省内存。同时，GraphSage 的时间和内存复杂度随着 K 和 r 的增加呈指数增长。 StoGCN 的时间复杂度最高，内存瓶颈仍未解决。然而，StoGCN 可以以非常小的 r 达到令人满意的性能。 Cluster-GCN 的时间复杂度与基线方法相同，因为它没有引入冗余计算。在所有方法中，ClusterGCN 实现了最低的内存复杂度。

---

谱模型与空间模型的比较

谱模型在图信号处理中具有理论基础。通过设计新的图信号滤波器（例如 Cayleynets [23]），可以构建新的 ConvGNN。然而，由于效率、通用性和灵活性问题，空间模型优于光谱模型。

• 首先，光谱模型的效率低于空间模型。光谱模型要么需要执行特征向量计算，要么同时处理整个图。空间模型更适合大型图，因为它们通过信息传播直接在图域中执行卷积。计算可以在一批节点中执行，而不是整个图。
• 其次，依赖于图傅里叶基的谱模型对新图的泛化能力很差。它们假设一个固定的图。对图的任何扰动都会导致特征基的变化。另一方面，基于空间的模型在每个节点上局部执行图卷积，可以在不同的位置和结构之间轻松共享权重。
• 第三，基于谱的模型仅限于在无向图上运行。基于空间的模型更灵活地处理多源图输入，例如边输入 [15]、[27]、[86]、[95]、[96]、有向图 [25]、[72]、有符号图[97] 和异构图 [98]、[99]，因为这些图输入可以很容易地合并到聚合函数中。

C. Graph Pooling Modules

在 GNN 生成节点特征后，可以将它们用于最终任务。但是直接使用所有这些特征在计算上可能具有挑战性，因此需要下采样策略。根据目标及其在网络中扮演的角色，该策略有不同的名称：（1）池化操作旨在通过对节点进行下采样以生成更小的表示来减少参数的大小，从而避免过拟合、排列不变性和计算复杂性问题； (2) 读出操作主要用于基于节点表示生成图级表示。它们的机制非常相似。在本章中，我们使用池化来指代应用于 GNN 的各种下采样策略。

在一些早期的工作中，图粗化（graph coarsening）算法基于图的拓扑结构使用特征分解来粗化图。然而，这些方法存在时间复杂度问题。 Graclus 算法 [100] 是特征分解的替代方案，用于计算原始图的聚类版本。最近的一些工作 [23] 将其用作池化操作来粗化图。

如今，mean/max/sum pooling 是实现下采样最原始和最有效的方法，因为在 pooling 窗口中计算 mean/max/sum 值很快：

其中 K 是最后一个图卷积层的索引。

Henaff et al. [20] 表明，在网络开始时执行简单的最大/均值池化对于降低图域中的维数和降低昂贵的图傅里叶变换操作的成本尤为重要。此外，一些作品 [17]、[27]、[46] 还使用注意机制来增强均值/总和池化。

即使使用注意机制，缩减操作（reduction operation，例如 sum pooling）也不能令人满意，因为它使嵌入效率低下：无论图大小如何，都会生成固定大小的嵌入。 Vinyals et al. [101] 提出了 Set2Set 方法来生成随着输入大小而增加的内存。然后，它实现了一个 LSTM，旨在将依赖于顺序的信息集成到内存嵌入中，然后再应用缩减，否则会破坏该信息。

Defferrard et al. [21] 通过以有意义的方式重新排列图的节点，以另一种方式解决了这个问题。他们在 ChebNet 方法中设计了一种有效的池化策略。输入图首先通过 Graclus 算法 [100] 粗化为多个级别。粗化后，输入图的节点及其粗化版本被重新排列成平衡的二叉树。从下到上任意聚合平衡二叉树会将相似的节点排列在一起。池化这样一个重新排列的信号比池化原始信号更有效。

Zhang et al. [52] 提出了具有类似池化策略的 DGCNN，称为 SortPooling，它通过将节点重新排列为有意义的顺序来执行池化。与 ChebNet [21] 不同，DGCNN 根据节点在图中的结构角色对节点进行排序。来自空间图卷积的图的无序节点特征被视为连续的 WL 颜色 [93]，然后用于对节点进行排序。除了对节点特征进行排序外，它还通过截断/扩展节点特征矩阵将图大小统一为 q。如果 n > q，则删除最后的 n - q 行，否则添加 q-n 零行。

上述池化方法主要考虑图的特征，而忽略了图的结构信息。最近，提出了一种可微池化（DiffPool）[54]，它可以生成图的层次表示。与之前所有的粗化方法相比，DiffPool 不是简单地对图中的节点进行聚类，而是在第 $k$ 层学习一个聚类分配矩阵 $S$，称为 $S(k)\in R^{n_k\times n_{k+1}}$，其中 nk 是第 k 层的节点数。第k层。矩阵 S(k) 中的概率值是基于节点特征和拓扑结构生成的

其核心思想是学习综合考虑图的拓扑和特征信息的节点分配，因此公式 28 可以用任何标准的 ConvGNN 来实现。然而，DiffPool 的缺点是它在池化后生成密集图，此后计算复杂度变为 O(n2)。

最近，提出了 SAGPool [102] 方法，该方法同时考虑节点特征和图拓扑，并以自注意方式学习池化。

总的来说，池化是减少图大小的必要操作。如何提高池化的有效性和计算复杂性是一个有待研究的悬而未决的问题。

D. Discussion of Theoretical Aspects

我们从不同的角度讨论了图神经网络的理论基础。

感受野的形状

节点的感受野是有助于确定其最终节点表示的节点集合。当合成多个空间图卷积层时，节点的感受野每次都向其远邻增长一步。 Micheli [24] 证明存在有限数量的空间图卷积层，使得对于每个节点 v ∈ V，节点 v 的感受野覆盖图中的所有节点。因此，ConvGNN 能够通过堆叠局部图卷积层来提取全局信息。

VC 维度

VC 维度是模型复杂性的度量，定义为模型可以粉碎的最大点数。分析 GNN 的 VC 维度的工作很少。给定模型参数 p 的数量和节点数量 n，Scarselli 等人。 [103] 推导出 GNN* [15] 的 VC 维度如果使用 sigmoid 或正切双曲线激活，则为 O(p4n2)，如果使用分段多项式激活函数，则为 O(p2n)。这一结果表明，如果使用 sigmoid 或正切双曲线激活，GNN [15] 的模型复杂度会随着 p 和 n 迅速增加*。

图同构

如果两个图在拓扑上相同，则它们是同构的。给定两个非同构图 G1 和 G2， Xu et al. [57] 证明，如果 GNN 将 G1 和 G2 映射到不同的嵌入，则可以通过 Weisfeiler-Lehman (WL) 的同构测试将这两个图识别为非同构图 [93]。他们表明，GCN [22] 和 GraphSage [42] 等常见的 GNN 无法区分不同的图结构。 Xu et al. [57] 进一步证明如果 GNN 的聚合函数和读出函数是单射的（injective），则 GNN 在区分不同图方面最多与 WL 测试一样强大。

等变和不变性（Equivariance and invariance）

GNN在执行节点级任务时必须是等变函数，在执行图级任务时必须是不变函数。对于节点级任务，设 $f(A，X)\in R^{n\times d}$ 为GNN，$Q$ 为任意改变节点顺序的置换矩阵。如果GNN满足 $f(QA{Q}^T，QX)=Qf(A，X)$，则它是等变的。对于图级任务，设$f(A，X)\in R^d$。如果GNN满足 $f(QA{Q}^T，QX)=f(A，X)$，则它是不变的。为了实现等方差或不变性，GNN的分量必须对节点排序不变。Maron et al. [104]从理论上研究了图形数据的排列不变和等变线性图层的特征。

通用逼近（Universal approximation）

众所周知，具有一个隐藏层的多感知器前馈神经网络可以逼近任何 Borel 可测量函数 [105]。 GNN 的通用逼近能力很少被研究。Hammer 等人[106] 证明级联相关可以逼近具有结构化输出的函数。Scarselli等人 [107] 证明 RecGNN [15] 可以逼近任何将展开等价保持到任何精度的函数。如果两个节点的展开树是相同的，则两个节点是展开等效的，其中节点的展开树是通过在某个深度处迭代扩展节点的邻域来构造的。徐等人[57] 表明消息传递框架下的 ConvGNN [27] 不是在多集上定义的连续函数的通用逼近器。Maron等人[104]证明不变图网络可以逼近图上定义的任意不变函数。

VI. GRAPH AUTOENCODERS

图自动编码器 (GAE) 是一种深度神经架构，可将节点映射到潜在特征空间并从潜在表示中解码图信息。 GAE 可用于学习网络嵌入或生成新图。表 V 总结了所选 GAE 的主要特征。下面，我们从网络嵌入和图生成两个角度对 GAE 进行简要回顾。

A. Network Embedding

网络嵌入是节点的低维向量表示，它保留了节点的拓扑信息。 GAE 使用编码器来学习网络嵌入以提取网络嵌入，并使用解码器来强制网络嵌入以保留图拓扑信息，例如 PPMI 矩阵和邻接矩阵。

早期的方法主要采用多层感知器来构建用于网络嵌入学习的 GAE。

• 图表示的深度神经网络 (DNGR) [59] 使用堆叠去噪自动编码器 [108] 通过多层感知器对 PPMI 矩阵进行编码和解码。
• 同时，结构深度网络嵌入（SDNE）[60]使用堆叠自动编码器来共同保持节点的一阶接近度和二阶接近度。

SDNE 分别在编码器的输出和解码器的输出上提出了两个损失函数。第一个损失函数使学习的网络嵌入能够通过最小化节点的网络嵌入与其邻居的网络嵌入之间的距离来保持节点的一阶接近度。第一个损失函数 L1st 定义为

其中 $x_v=A_{v,:}$ 和 $enc(\cdot )$ 是一个由多层感知器组成的编码器。第二个损失函数使学习到的网络嵌入能够通过最小化节点输入与其重构输入之间的距离来保持节点二阶接近度。具体来说，第二个损失函数 L2nd 定义为

DNGR [59] 和 SDNE [60] 只考虑节点结构信息，即关于节点对之间的连接性。他们忽略节点可能包含描述节点本身属性的特征信息。 Graph Autoencoder ($GA{E}^{\ast }$) [61] 利用 GCN [22] 同时编码节点结构信息和节点特征信息。 $GA{E}^{\ast }$ 的编码器由两个图卷积层组成，其形式为

其中 Z 表示图的网络嵌入矩阵，f(·) 是 ReLU 激活函数，Gconv(·) 函数是由等式 12 定义的图卷积层。GAE* 的解码器旨在从它们的通过重构图邻接矩阵进行嵌入，该矩阵定义为

其中 zv 是节点 v 的嵌入。给定真实邻接矩阵 A 和重构的邻接矩阵 ^A，通过最小化负交叉熵来训练 GAE*。

由于自动编码器的容量，简单地重构图邻接矩阵可能会导致过度拟合。变分图自动编码器（VGAE）[61] 是 GAE 的变分版本，用于学习数据的分布。VGAE 优化变分下界 L：

根据公式 33，VGAE 假设经验分布 q(Z|X, A) 应尽可能接近先验分布 p(Z)。为了进一步加强经验分布 q(Z|X, A) 逼近先验分布 p(Z)，对抗正则化变分图自动编码器 (ARVGA) [62]、[109] 采用了生成对抗网络 (GAN) 的训练方案) [110]。 GAN 在训练生成模型时会在生成器和判别器之间进行竞争游戏。生成器试图生成尽可能真实的“假样本”，而鉴别器试图将“假样本”与真实样本区分开来。受 GAN 的启发，ARVGA 努力学习一种编码器，该编码器产生与先验分布 p(Z) 无法区分的经验分布 q(Z|X, A)。

与 GAE* 类似，GraphSage [42] 使用两个图卷积层对节点特征进行编码。 GraphSage 没有优化重构误差，而是表明两个节点之间的关系信息可以通过带有损失的负采样来保留：

其中节点 u 是节点 v 的邻居，节点 vn 是节点 v 的距离较远的节点，并且是从负采样分布 Pn(v) 中采样的，Q 是负样本的数量。这种损失函数本质上是强制靠近的节点具有相似的表示，而远距离的节点具有不同的表示。

DGI [56] 交替驱动本地网络嵌入，通过最大化本地互信息来捕获全局结构信息。它在实验上显示出对 GraphSage [42] 的明显改进。

对于上述方法，它们本质上是通过解决链接预测问题来学习网络嵌入。然而，图的稀疏性导致正节点对的数量远远少于负节点对的数量。为了缓解学习网络嵌入中的数据稀疏问题，另一行工作通过随机排列或随机游走将图转换为序列。这样，那些适用于序列的深度学习方法可以直接用于处理图。深度递归网络嵌入（DRNE）[63]假设节点的网络嵌入应该近似于其邻域网络嵌入的聚合。它采用长短期记忆（LSTM）网络[7]来聚合节点的邻居。DRNE的重构误差定义为

其中 $z_v$ 是通过字典查找获得的节点 $v$ 的网络嵌入，LSTM网络将节点 $v$ 的邻居按节点度排序的随机序列作为输入。如公式 35 所示，DRNE 通过 LSTM 网络隐式学习网络嵌入，而不是使用 LSTM 网络生成网络嵌入。它避免了LSTM网络对节点序列的排列不不变的问题。 Network Representations with Adversarially Regularized Autoencoders (NetRA) [64] 提出了一种具有通用损失函数的图形编码器-解码器框架，定义为

其中 dist(·) 是节点嵌入 z 和重构 z 之间的距离度量。 NetRA 的编码器和解码器是 LSTM 网络，随机游走以每个节点 v ∈ V 作为输入。与 ARVGA [62] 类似，NetRA 通过对抗性训练在先验分布中对学习到的网络嵌入进行正则化。虽然 NetRA 忽略了 LSTM 网络的节点置换变体问题，但实验结果验证了 NetRA 的有效性。

B. Graph Generation

对于多个图，GAE 能够通过将图编码为隐藏表示并解码给定隐藏表示的图结构来学习图的生成分布。大多数用于图生成的GAE都是为了解决分子图生成问题而设计的，在药物发现中具有很高的实用价值。这些方法要么以顺序方式或以全局方式提出新图。

顺序方法通过逐步提出节点和边来生成图。Gomez et al. [111]，Kusner et al. [112]和Dai et al. [113] 对名为 SMILES 的分子图的字符串表示的生成过程进行建模，其中深度 CNN 和 RNN 分别作为编码器和解码器。

虽然这些方法是特定于域的，但替代解决方案适用于一般图，方法是迭代地将节点和边添加到不断增长的图中，直到满足某个标准。图的深度生成模型（DeepGMG）[65]假设图的概率是所有可能节点排列的总和：

其中 π 表示节点排序。它捕获了图中所有节点和边的复杂联合概率。 DeepGMG 通过做出一系列决策来生成图，即是否添加节点、添加哪个节点、是否添加边以及将哪个节点连接到新节点。生成节点和边的决策过程取决于节点状态和由 RecGNN 更新的增长图的图状态。在另一项工作中，GraphRNN [66] 提出了图级 RNN 和边级 RNN 来对节点和边的生成过程进行建模。图级 RNN 每次都会向节点序列添加一个新节点，而边缘级 RNN 会生成一个二进制序列，指示新节点与序列中先前生成的节点之间的连接。

全局方法一次输出一个图形。 Graph Variational Autoencoder (GraphVAE) [67] 将节点和边的存在建模为独立随机变量。通过假设编码器定义的后验分布 qφ(z|G) 和解码器定义的生成分布 pθ(G|z)，GraphVAE 优化了变分下限：

其中 p(z) 遵循高斯先验，φ 和 θ 是可学习的参数。使用 ConvGNN 作为编码器和简单的多层感知作为解码器，GraphVAE 输出生成的图及其邻接矩阵、节点属性和边属性。控制生成图的全局属性是一项挑战，例如图的连通性、有效性和节点兼容性。正则化图变分自编码器（RGVAE）[68] 进一步对图变分自编码器施加有效性约束，以规范解码器的输出分布。分子生成对抗网络 (MolGAN) [69] 集成了 convGNN [114]、GAN [115] 和强化学习目标，以生成具有所需属性的图。 MolGAN 由生成器和判别器组成，相互竞争以提高生成器的真实性。在 MolGAN 中，生成器试图提出一个假图及其特征矩阵，而鉴别器旨在将假样本与经验数据区分开来。此外，奖励网络与鉴别器并行引入，以鼓励生成的图根据外部评估器具有某些属性。 NetGAN [70] 将 LSTM [7] 与 Wasserstein GAN [116] 相结合，从基于随机游走的方法生成图形。 NetGAN 训练生成器通过 LSTM 网络生成合理的随机游走，并强制鉴别器从真实随机游走中识别出虚假的随机游走。训练后，通过归一化基于生成器产生的随机游走计算的节点的共现矩阵来导出新图。

简而言之，顺序方法将图线性化为序列。由于存在循环，它们可能会丢失结构信息。全局方法一次生成一个图形。它们不能扩展到大图，因为 GAE 的输出空间高达 O(n2)。

VII. SPATIAL-TEMPORAL GRAPH NEURAL NETWORKS

许多现实世界应用程序中的图在图结构和图输入方面都是动态的。时空图神经网络 (STGNN) 在捕获图的动态性方面占据重要位置。此类别下的方法旨在对动态节点输入进行建模，同时假设连接节点之间的相互依赖关系。例如，交通网络由放置在道路上的速度传感器组成，其中边缘权重由传感器对之间的距离确定。由于一条道路的交通状况可能取决于其相邻道路的状况，因此在进行交通速度预测时需要考虑空间依赖性。作为一种解决方案，STGNN 同时捕获图的空间和时间依赖性。 STGNN 的任务可以是预测未来的节点值或标签，或者预测时空图标签。 STGNN 遵循两个方向，基于 RNN 的方法和基于 CNN 的方法。

大多数基于 RNN 的方法通过使用图卷积 [48]、[71]、[72] 过滤传递给循环单元的输入和隐藏状态来捕获时空依赖性。为了说明这一点，假设一个简单的 RNN 采用以下形式

其中 Gconv(·) 是一个图卷积层。图卷积循环网络 (GCRN) [71] 将 LSTM 网络与 ChebNet [21] 相结合。扩散卷积递归神经网络（DCRNN）[72] 将提出的扩散图卷积层（方程 18）合并到 GRU 网络中。此外，DCRNN 采用编码器-解码器框架来预测节点值的未来 K 步。

另一项并行工作使用节点级 RNN 和边缘级 RNN 来处理时间信息的不同方面。 Structural-RNN [73] 提出了一个循环框架来预测每个时间步的节点标签。它包括两种 RNN，即节点 RNN 和边缘 RNN。每个节点和每条边的时间信息分别通过一个节点-RNN和一个边-RNN。为了结合空间信息，node-RNN 将 edge-RNN 的输出作为输入。由于为不同的节点和边假设不同的 RNN 会显着增加模型的复杂性，因此它会将节点和边拆分为语义组。同一语义组中的节点或边共享相同的 RNN 模型，节省了计算成本。

基于 RNN 的方法存在耗时的迭代传播和梯度爆炸/消失问题。作为替代解决方案，基于 CNN 的方法以非递归方式处理时空图，具有并行计算、稳定梯度和低内存要求的优点。如图 2d 所示，基于 CNN 的方法将 1D-CNN 层与图卷积层交错以分别学习时间和空间依赖性。假设时空图神经网络的输入是张量 $X\in R^{T\times n\times d}$，1D-CNN 层沿时间轴在 $X_{[:,i,:]}$ 上滑动以聚合每个节点的时间信息，而图卷积层对 $X_{[i,:,:]}$ 进行操作，以在每个时间步聚合空间信息。 CGCN [74] 将一维卷积层与 ChebNet [21] 或 GCN [22] 层集成。它通过按顺序堆叠一个门控一维卷积层、一个图卷积层和另一个门控一维卷积层来构造一个时空块。 ST-GCN [75] 使用 1D 卷积层和 PGC 层（公式 20）组成时空块。

以前的方法都使用预定义的图结构。他们假设预定义的图结构反映了节点之间真正的依赖关系。然而，在空间-时间设置中使用许多图数据的快照，可以从数据中自动学习潜在的静态图结构。为了实现这一点，Graph WaveNet [76] 提出了一种自适应邻接矩阵来执行图卷积。自适应邻接矩阵定义为

其中 SoftMax 函数是沿行维度计算的，E1 表示源节点嵌入，E2 表示具有可学习参数的目标节点嵌入。通过将 E1 与 E2 相乘，可以得到源节点和目标节点之间的依赖权重。使用复杂的基于 CNN 的时空神经网络，Graph WaveNet 在没有邻接矩阵的情况下表现良好。

学习潜在的静态空间依赖关系可以帮助研究人员发现网络中不同实体之间可解释且稳定的相关性。然而，在某些情况下，学习潜在的动态空间依赖关系可能会进一步提高模型精度。例如，在交通网络中，两条道路之间的行驶时间可能取决于它们当前的交通状况。GaAN [48] 采用注意力机制通过基于 RNN 的方法来学习动态空间依赖关系。在给定当前节点输入的情况下，注意力函数用于更新两个连接节点之间的边权重。 ASTGCN [77] 进一步包括空间注意功能和时间注意功能，以通过基于 CNN 的方法学习潜在的动态空间依赖和时间依赖。学习潜在空间依赖的共同缺点是需要计算每对节点之间的空间依赖权重，成本为 O(n2)。

VIII. APPLICATIONS

由于图结构数据无处不在，GNN 具有广泛的应用。在本节中，我们分别总结了基准图数据集、评估方法和开源实现。我们详细介绍了 GNN 在各个领域的实际应用。

A. Data Sets

我们主要将数据集分为四组，即引文网络、生化图、社交网络等。在表 VI 中，我们总结了选定的基准数据集。补充材料 A 中提供了更多详细信息。

B. Evaluation & Open-source Implementations

节点分类和图分类是评估 RecGNN 和 ConvGNN 性能的常见任务

节点分类

在节点分类中，大多数方法在基准数据集（包括 Cora、Citeseer、Pubmed、PPI 和 Reddit）上遵循训练/有效/测试的标准拆分。他们报告了多次运行测试数据集的平均准确度或 F1 分数。方法实验结果的总结可以在补充材料 B 中找到。应该注意的是，这些结果并不一定代表严格的比较。Shchur et al. 确定了 [131] 在评估 GNN 在节点分类上的性能时存在的两个缺陷。

• 首先，在所有实验中使用相同的训练/有效/测试拆分低估了泛化误差。
• 其次，不同的方法采用了不同的训练技术，例如超参数调整、参数初始化、学习率衰减和提前停止。

为了进行相对公平的比较，我们推荐阅读 Shchur et al. [131]。

图分类

在图分类中，研究人员通常采用 10 倍交叉验证（cv）进行模型评估。然而，正如 [132] 所指出的，实验设置是模棱两可的，并且在不同的作品中并不统一。特别是，[132] 提出了正确使用数据拆分来进行模型选择与模型评估的担忧。一个经常遇到的问题是每个折叠的外部测试集都用于模型选择和风险评估。 [132] 在标准化和统一的评估框架中比较 GNN。他们应用外部 10 倍 CV 来估计模型的泛化性能和内部保持技术，其中 90%/10% 训练/验证拆分用于模型选择。另一种方法是双 cv 方法，它使用外部 k 折 cv 进行模型评估，使用内部 k 折 cv 进行模型选择。我们推荐阅读 [132]，以详细和严格地比较 GNN 方法用于图分类。

开源实现

促进了深度学习研究中基线实验的工作。在补充材料 C 中，我们提供了本文回顾的 GNN 模型的开源实现的超链接。值得注意的是，Fey et al. [92] 在 PyTorch 中发布了一个名为 PyTorch Geometric 的几何学习库，它实现了许多 GNN。最近，Deep Graph Library (DGL) [133] 发布，它在 PyTorch 和 MXNet 等流行的深度学习平台上提供了许多 GNN 的快速实现。

C. Practical Applications

GNN 在不同的任务和领域中有许多应用。尽管每个类别的 GNN 都可以直接处理一般任务，包括节点分类、图分类、网络嵌入、图生成和时空图预测，但其他与图相关的一般任务，如节点聚类 [134]、链接预测 [135 ]，图分割[136]也可以通过GNN来解决。我们详细介绍了基于以下研究领域的一些应用。

计算机视觉

GNN 在计算机视觉中的应用包括场景图生成、点云分类和动作识别。

识别对象之间的语义关系有助于理解视觉场景背后的含义。场景图生成模型旨在将图像解析为由对象及其语义关系组成的语义图 [137]、[138]、[139]。另一个应用程序通过在给定场景图的情况下生成逼真的图像来反转该过程 [140]。由于自然语言可以被解析为每个单词代表一个对象的语义图，因此它是一种很有前途的解决方案，可以在给定文本描述的情况下合成图像。

分类和分割点云使 LiDAR 设备能够“看到”周围环境。点云是由 LiDAR 扫描记录的一组 3D 点。 [141]、[142]、[143] 将点云转换为 k-最近邻图或超点图，并使用 ConvGNN 探索拓扑结构。

识别视频中包含的人类行为有助于从机器方面更好地理解视频内容。一些解决方案检测视频剪辑中人体关节的位置。由骨骼连接起来的人体关节自然形成了一个图形。给定人类关节位置的时间序列，[73]、[75] 应用 STGNN 来学习人类动作模式。

此外，GNN 在计算机视觉中的适用方向数量仍在增长。它包括人-物交互[144]、小样本图像分类[145]、[146]、[147]、语义分割[148]、[149]、视觉推理[150]和问答[151]。

自然语言处理

GNN 在自然语言处理中的一个常见应用是文本分类。 GNN 利用文档或单词的相互关系来推断文档标签 [22]、[42]、[43]。

尽管自然语言数据表现出顺序，但它们也可能包含内部图结构，例如句法依赖树。句法依赖树定义了句子中单词之间的句法关系。Marcheggiani et al. [152] 提出了在 CNN/RNN 句子编码器之上运行的句法 GCN。 Syntactic GCN 基于句子的句法依赖树聚合隐藏的单词表示。Bastings et al. [153] 将句法 GCN 应用于神经机器翻译任务。 Marcheggiani et al.[154] 进一步采用与 Bastings 等人相同的模型。 [153]处理句子的语义依赖图。

图到序列学习 学习在给定抽象词的语义图（称为抽象意义表示）的情况下生成具有相同含义的句子。Song et al. [155] 提出了一种图 LSTM 来编码图级语义信息。Beck et al. [156] 将 GGNN [17] 应用于图到序列学习和神经机器翻译。逆向任务是序列到图的学习。给定句子，生成语义或知识图在知识发现中非常有用[157]，[158]。

交通

准确预测交通网络中的交通速度、交通量或道路密度对于智能交通系统至关重要。 [48]、[72]、[74] 使用 STGNN 解决交通预测问题。他们将交通网络视为一个时空图，其中节点是安装在道路上的传感器，边缘由节点对之间的距离测量，每个节点将窗口内的平均交通速度作为动态输入特征。另一个工业级应用是出租车需求预测。鉴于历史出租车需求、位置信息、天气数据和事件特征，Yao et al. [159] 结合 LSTM、CNN 和由 LINE [160] 训练的网络嵌入，形成每个位置的联合表示，以预测时间间隔内某个位置所需的出租车数量。

推荐系统

基于图的推荐系统将项目和用户作为节点。通过利用项目与项目、用户与用户、用户与项目之间的关系以及内容信息，基于图的推荐系统能够产生高质量的推荐。推荐系统的关键是对项目对用户的重要性进行评分。结果，它可以被转换为链接预测问题。为了预测用户和项目之间的缺失链接，Van et al. [161] 和 Ying et al. [162] 提出了一种使用 ConvGNN 作为编码器的 GAE。Monti et al. [163] 将 RNN 与图卷积相结合，以学习生成已知评级的基础过程。

化学

在化学领域，研究人员应用 GNN 来研究分子/化合物的图形结构。在分子/化合物图中，原子被视为节点，化学键被视为边缘。节点分类、图分类和图生成是针对分子/化合物图的三个主要任务，以学习分子指纹 [85]、[86]、预测分子特性 [27]、推断蛋白质界面 [164] 和合成化合物 [65]、[69]、[165]。

其他

GNN 的应用不仅限于上述领域和任务。已经探索将 GNN 应用于各种问题，例如程序验证 [17]、程序推理 [166]、社会影响预测 [167]、对抗性攻击预防 [168]、电子健康记录建模 [169]、[170] ]、大脑网络[171]、事件检测[172]和组合优化[173]。

IX. FUTURE DIRECTIONS

尽管 GNN 已经证明了它们在学习图数据方面的能力，但由于图的复杂性，挑战仍然存在。在本节中，我们提出了 GNN 的四个未来方向。

模型深度（Model depth）

深度学习的成功在于深度神经架构 [174]。然而，Li et al. 表明随着图卷积层数的增加，ConvGNN 的性能急剧下降 [53]。随着图卷积将相邻节点的表示推得更近，理论上，在无限数量的图卷积层中，所有节点的表示将收敛到一个点 [53]。这就提出了一个问题，即深入研究是否仍然是学习图数据的好策略。

可扩展性权衡（Scalability trade-off）

GNN 的可扩展性是以破坏图完整性为代价的。无论是使用采样还是聚类，模型都会丢失部分图信息。通过采样，节点可能会错过其有影响力的邻居。通过聚类，图可能被剥夺了独特的结构模式。如何权衡算法的可扩展性和图的完整性可能是未来的研究方向。

异质性（Heterogenity）

当前的大多数 GNN 都假设图是同质的。目前的 GNN 很难直接应用于异构图，异构图可能包含不同类型的节点和边，或者不同形式的节点和边输入，例如图像和文本。因此，应该开发新的方法来处理异构图。

动态（Dynamicity）

图本质上是动态的，节点或边可能出现或消失，节点/边输入可能会随时间变化。需要新的图卷积来适应图的动态性。虽然图的动态性可以通过 STGNN 部分解决，但很少有人考虑在动态空间关系的情况下如何执行图卷积。

X. CONCLUSION

在本次调查中，我们对图神经网络进行了全面概述。我们提供了一种分类法，将图神经网络分为四类：循环图神经网络、卷积图神经网络、图自动编码器和时空图神经网络。我们对类别内或类别之间的方法进行了全面的审查、比较和总结。然后我们介绍了图神经网络的广泛应用。总结了图神经网络的数据集、开源代码和模型评估。最后，我们提出了图神经网络的四个未来方向。