近年来，深度学习彻底改变了从图像分类和视频处理到语音识别和自然语言理解的许多机器学习任务。这些任务中的数据通常在欧几里得空间中表示。然而，越来越多的应用从非欧几里德领域生成数据。这些数据表示为具有复杂关系和对象之间相互依赖性的图。图数据的复杂性对现有的机器学习算法提出了重大挑战。最近，出现了许多关于扩展图数据深度学习方法的研究。在本次调查中，我们全面概述了数据挖掘和机器学习领域中的图神经网络 (GNNs)。我们使用了一种新的分类法，将最先进的图神经网络分为四类，即：
- recurrent graph neural networks 循环图神经网络
- convolutional graph neural networks 卷积图神经网络
- graph autoencoders 图自编码
- spatial-temporal graph neural networks 时空图神经网络
我们进一步讨论了图神经网络在各个领域的应用，并总结了图神经网络的开源代码、基准数据集和模型评估。最后，我们提出了这个快速发展领域的潜在研究方向。
最近神经网络的成功推动了模式识别和数据挖掘的研究。许多机器学习任务，如对象检测 [1]，[2] 、机器翻译 [3]，[4] 、语音识别 [5] ，曾经严重依赖手工特征工程来提取信息特征集，最近已经发生了革命性的变化。这主要归功于各种端到端深度学习范例，例如，卷积神经网络 (CNNs)[6] 、递归神经网络 (RNNs)[7] 和自动编码器 [8]。深度学习在许多领域的成功部分归功于快速发展的计算资源（例如 GPU）、大训练数据的可用性以及深度学习从欧几里得数据（例如图像、文本、和视频）提取潜在表示的高效性。以图像数据作为例，我们可以将图像表示为欧几里德空间中的规则网格。卷积神经网络 (CNN) 能够利用图像数据的移位不变性、局部连通性和组合性 [9]。因此，CNN 可以提取局部有意义的特征，这些特征由整个数据集共享，用于各种图像分析。
虽然深度学习有效地捕获了欧几里德数据的隐藏模式，但越来越多的应用程序将数据以图的形式表示。例如，在电子商务中，基于图的学习系统可以利用用户和产品之间的交互来做出高度准确的推荐。在化学中，分子被建模为图，并且需要确定它们的生物活性以用于药物发现。在引文网络中，论文通过引用关系相互链接，并且需要将它们分类到不同的组中。图数据的复杂性对现有的机器学习算法提出了重大挑战。由于图可能是不规则的，因此图可能具有可变大小的无序节点，并且图中的节点可能具有不同数量的邻居，从而导致一些重要的操作（例如，卷积）在图像域中易于计算，但是很难应用于图域。此外，现有机器学习算法的一个核心假设是实例相互独立。这个假设不再适用于图数据，因为每个实例（节点）都通过各种类型的链接与其他实例相关，例如引用、友谊和交互。
最近，人们对扩展图形数据的深度学习方法越来越感兴趣。在 CNNs、RNNs 和深度学习的自动编码器的推动下，在过去几年中，重要操作的新概括和定义得到迅速发展，以处理图数据的复杂性。例如，图卷积可以从 2D 卷积推广。如图 1 所示，可以将图像视为图的特例，其中像素由相邻像素连接。类似于 2D 卷积，可以通过取节点邻域信息的加权平均值来执行图卷积。
Delete Block
关于图神经网络 (GNNs) 主题的现有评论数量有限。使用术语几何深度学习，Bronstein 等人 [9] 概述了非欧几里得领域的深度学习方法，包括图和流形。虽然这是对 GNNs 的第一次回顾，但本次调查主要回顾了卷积 GNNs。汉密尔顿等人 [10] 涵盖了有限数量的 GNNs，重点是解决网络嵌入问题。巴塔利亚等人 [11] 位置图网络作为构建块用于从关系数据中学习，在统一框架下审查部分 GNNs。李等人 [12]对应用不同注意力机制的 GNNs 进行了部分调查。
总而言之，现有调查仅包括部分 GNN 并检查了有限数量的作品，因此错过了 GNN的最新发展。我们的调查为想要进入这个快速发展领域的感兴趣的研究人员和想要比较 GNN 模型的专家提供了 GNN 的全面概述。为了涵盖更广泛的方法，本次调查将 GNN 视为图数据的所有深度学习方法。
综述其余部分整理如下：第二部分概述了图神经网络的背景，列出了常用的符号，并定义了与图相关的概念。第三节阐明了图神经网络的分类。第四到七节概述了图神经网络模型。第八节介绍了一系列跨领域的应用程序。第九节讨论了当前的挑战并提出了未来的方向。第十节总结了这篇文章。
图神经网络简史 (GNNs)。
Sperduti 等人 (1997) [13] 首先将神经网络应用于有向无环图，这激发了对 GNNs 的早期研究。Gori 等人 (2005) [14] 最初概述了图神经网络的概念 (2005)，Scarselli 等人 (2009) [15] 和 Gallicchio 等人 (2010) [16] 进一步阐述了它。这些早期研究属于循环图神经网络 (RecGNNs) 类别。他们通过以迭代方式传播邻居信息来学习目标节点的表示，直到达到稳定的固定点。这个过程在计算上是昂贵的，最近人们越来越努力地克服这些挑战 [17]，[18]。
受 CNNs 在计算机视觉领域取得成功的鼓舞，大量重新定义图形数据卷积概念的方法被同时开发。这些方法属于卷积图神经网络 (ConvGNNs) 的范畴。ConvGNNs 分为两个主要流派，基于光谱的方法和基于空间的方法。Bruna 等人 (2013) [19] 提出了第一个关于基于光谱的 ConvGNNs 的突出研究。这项研究开发了一种基于光谱图理论的图卷积。从那时起，基于光谱的 ConvGNNs 的改进、扩展和近似不断增加 [20]，[21]，[22]，[23]。基于空间的 ConvGNNs 的研究比基于光谱的 ConvGNNs 起步更早。2009 年，Micheli 等人 [24] 首先通过结构上使用复合非递归层解决图相互依赖，同时继承从 RecGNNs 传递消息的想法。然而，这项工作的重要性被忽视了。直到最近，出现了许多基于空间的 ConvGNNs (比如，[25]，[26]，[27])。具有代表性的 RecGNNs 和 ConvGNNs 的时间线显示在表 II 的第一列中。除了 RecGNNs 和 ConvGNNs，过去几年还开发了许多替代 GNNs，包括图自动编码器 (GAE) 和时空图神经网络 (STGNNs)。这些学习框架可以建立在 RecGNNs、ConvGNNs 或其他用于图建模的神经架构上。关于这些方法分类的详细信息在第三节中给出。
Graph neural networks vs. network embedding
GNN 的研究与图嵌入或网络嵌入密切相关，这是另一个引起数据挖掘和机器学习计算机越来越多关注的话题 [10]、[28]、[29]、[30]、[31]、[32]。网络嵌入旨在将网络节点表示为低维向量表示，同时保留网络拓扑结构和节点内容信息，以便可以使用简单的现成方法轻松执行任何后续图分析任务，如分类、聚类和推荐。货架机器学习 算法（例如，用于分类的支持向量机）。同时，GNN 是深度学习模型，旨在以端到端的方式解决与图相关的任务。许多 GNN 显式提取高级表示。
GNN 和网络嵌入之间的主要区别在于，GNN 是一组为各种任务设计的神经网络模型，而网络嵌入涵盖了针对同一任务的各种方法。因此，GNN 可以通过图形自动编码器框架解决网络嵌入问题。另一方面，网络嵌入包含其他非深度学习方法，例如矩阵分解[33]、 [34]和随机游走[35]。
图神经网络与图核方法图核是解决图分类问题的历史主导技术[36]、[37]、 [38]。这些方法使用核函数来衡量图对之间的相似性，因此支持向量机等基于核的算法可用于图的监督学习。
与 GNN 类似，图核可以通过映射函数将图或节点嵌入向量空间。不同之处在于这个映射函数是确定性的而不是可学习的。由于成对相似性计算，图核方法受到计算瓶颈的严重影响。
在本文中，我们使用粗体大写字符表示矩阵，使用粗体小写字符表示向量。循环图神经网络（RecGNNs）大多是图神经网络的先驱。RecGNN 旨在学习具有递归神经架构的节点表示。
表 I：常用符号。
除非特别说明，否则本文中使用的符号如表 I 所示。现在我们定义理解本文所需的最小定义集。
定义 1（图）：图表示为 G = (V, E)，其中 V 是顶点或节点的集合（我们将在整篇论文中使用节点），E 是边的集合。令
定义2（有向图）：有向图是所有边从一个节点指向另一个节点的图。无向图被认为是有向图的特例，如果两个节点相连，则存在一对方向相反的边。当且仅当邻接矩阵是对称的时，图是无向的。
定义3（时空图）：时空图是节点属性随时间动态变化的属性图。时空图定义为 G(t) = (V, E, X(t)) 其中 X(t) ∈ Rn×d 。
在本节中，我们介绍了图神经网络 (GNN) 的分类，如表II 所示。我们将图神经网络 (GNN) 分为循环图神经网络 (RecGNN)、卷积图神经网络 (Con vGNN)、图自动编码器 (GAE) 和时空图神经网络 (STGNN)。图 2 给出了各种模型架构的示例。下面，我们对每个类别进行简要介绍。
循环图神经网络（RecGNNs）大多是图神经网络的先驱。 RecGNN 旨在学习具有递归神经架构的节点表示。他们假设图中的一个节点不断地与其邻居交换信息/消息，直到达到稳定的平衡到达。RecGNN 在概念上很重要，并启发了后来对卷积图神经网络的研究。特别是，基于空间的卷积图神经网络继承了消息传递的思想。
卷积图神经网络（ConvGNNs）概括了从网格数据到图数据的卷积操作。主要思想是通过聚合自身的特征xv和邻居的特征xu 来生成节点 v 的表示，其中 u ∈ N(v)。与 RecGNN 不同，ConvGNN 堆叠多个图形卷积层以提取高级节点表示。ConvGNN 在构建许多其他复杂的 GNN 模型中发挥着核心作用。图2a显示了用于节点分类的 ConvGNN。图2b演示了用于图形分类的 ConvGNN。
图自动编码器 (GAE)是无监督学习框架，它将节点/图编码到潜在向量空间中，并从编码信息中重建图数据。 GAE 用于学习网络嵌入和图形生成分布。对于网络嵌入，GAE 通过重建图形结构信息（例如图形邻接矩阵）来学习潜在节点表示。对于图生成，一些方法逐步生成图的节点和边，而另一些方法一次输出一个图。图2c展示了用于网络嵌入的 GAE。
时空图神经网络 (STGNN)旨在从时空图中学习隐藏模式，这在交通速度预测[72]、驾驶员机动预测[73]和人类行为识别等各种应用中变得越来越重要[ 75]。 STGNN的关键思想是同时考虑空间依赖性和时间依赖性。当前许多集成图卷积的方法通过RNN 或 CNN 捕获空间依赖性来对时间依赖性进行建模。图2d说明了用于时空图预测的 STGNN。
以图结构和节点内容信息作为输入，GNN 的输出可以通过以下机制之一专注于不同的图分析任务：
-
节点级 输出与节点回归和节点分类任务相关。RecGNNs 和 ConvGNNs 可以通过信息传播/图卷积提取高级节点表示。使用多感知器或 softmax 层作为输出层，GNN 能够以端到端的方式执行节点级任务。
-
边级 输出与边分类和链路预测任务相关。将来自 GNN 的两个节点的隐藏表示作为输入，可以利用相似函数或神经网络来预测边的标签/连接强度。
-
图级 输出与图分类任务相关。为了在图级别上获得紧凑的表示，GNN 通常与池化和读出操作相结合。有关汇集和读数的详细信息将在第 VC 节中进行审查。
训练框架。许多 GNN（例如，ConvGNN）可以在端到端学习框架内以（半）监督或纯无监督的方式进行训练，具体取决于手头的学习任务和标签信息。
-
用于节点级分类的半监督学习。给定一个部分节点被标记而其他节点未标记的单个网络，ConvGNN 可以学习一个强大的模型，该模型可以有效地识别未标记节点的类标签[22]。为此，可以通过堆叠几个图卷积层和一个用于多类分类的 softmax 层来构建端到端框架。
-
图级分类的监督学习。图级分类旨在预测整个图的类标签[52]、 [54]、 [78]、 [79]。该任务的端到端学习可以通过图卷积层、图池化层和/或读出层的组合来实现。图卷积层负责精确的高级节点表示，而图池化层则起到下采样的作用，每次都将每个图粗化为一个子结构。读出层将每个图形的节点表示折叠为图形表示。通过将多层感知器和 softmax 层应用于图形表示，我们可以构建用于图形分类的端到端框架。图 2b 给出了一个例子。
-
图嵌入的无监督学习。当图中没有可用的类标签时，我们可以在端到端框架中以完全无监督的方式学习图嵌入。这些算法以两种方式利用边缘级信息。一种简单的方法是采用自动编码器框架，其中编码器使用图卷积层将图嵌入到潜在表示中，解码器用于重建图结构[61]、[62]。另一个流行方式是利用负采样方法，将一部分节点对采样为负对，而图中具有链接的现有节点对为正对。然后应用逻辑回归层来区分正负对[42]。
在表III 中，我们总结了具有代表性的 RecGNN 和 ConvGNN 的主要特征。输入源、池化层、读出层和时间复杂度在各种模型之间进行了比较。更详细地说，我们只比较了每个模型中消息传递/图卷积操作的时间复杂度。由于[19]和[20]中的方法需要特征值分解，因此时间复杂度为 O(n [46]的时间复杂度也是 O(n 明智的最短路径计算。其他方法产生等效的时间复杂度，即 O(m ) 如果图的邻接矩阵是稀疏的，否则是O(n )。这是因为在这些方法中，每个节点vi 的表示的计算涉及它的di邻居，并且所有节点上di的总和恰好等于边的数量。表III中缺少几种方法的时间复杂度。这些方法要么在论文中没有时间复杂度分析，要么报告了它们的整体模型或算法的时间复杂度。
循环图神经网络 (RecGNN) 大多是 GNN 的先驱。他们在图中的节点上循环应用相同的一组参数，以提取高级节点表示。受计算能力的限制，早期的研究主要集中在有向无环图[13]、[80]上。
Scarselli 等人提出的图神经网络 (GNN*)。扩展先前的循环模型以处理一般类型的图，例如非循环图、循环图、有向图和无向图[15]。基于信息扩散机制，GNN* 通过循环交换邻域信息来更新节点的状态，直到达到稳定的平衡。节点的隐藏状态由以下方式循环更新
其中 f(·) 是参数函数，h 是随机的。求和运算使 GNN* 适用于所有节点，即使邻居的数量不同并且不知道邻域顺序也是如此。为确保收敛，循环函数 f(·) 必须是收缩映射，将两点投影到潜在空间后缩小它们之间的距离。在 f(·) 是神经网络的情况下，必须对参数的雅可比矩阵施加惩罚项。当满足收敛标准时，最后一步节点隐藏状态被转发到读出层。GNN* 交替节点状态传播阶段和参数梯度计算阶段以最小化训练目标。该策略使 GNN* 能够处理循环图。在后续工作中，图回声状态网络(GraphESN)[16]扩展了回声状态网络以改进 GNN* 的训练效率。GraphESN 由一个编码器和一个输出层组成。编码器是随机初始化的，不需要训练。它实现了一个收缩状态转换函数来循环更新节点状态，直到全局图状态达到收敛。之后，通过将固定节点状态作为输入来训练输出层。
门控图神经网络 (GGNN) [17]采用门控循环单元 (GRU) [81]作为循环函数，将循环减少到固定数量的步骤。优点是不再需要约束参数来保证收敛。节点隐藏状态由其先前的隐藏状态及其相邻隐藏状态更新，定义为
其中 h = xv。与 GNN* 和 GraphESN 不同，GGNN 使用时间反向传播 (BPTT) 算法来学习模型参数。这对于大型图可能会有问题，因为 GGNN 需要在所有节点上多次运行循环函数，需要将所有节点的中间状态存储在内存中。
Stochastic Steady‑state Embedding (SSE) 提出了一种学习算法，该算法更适用于大型图[18]。 SSE 以随机和异步的方式循环更新节点隐藏状态。它交替地采样一批节点用于状态更新和一批节点用于梯度计算。
为了保持稳定性，SSE 的循环函数被定义为历史状态和新状态的加权平均值，其形式为
其中α是超参数，h是随机初始化的。
虽然在概念上很重要，但 SSE 并没有在理论上证明节点状态将通过重复应用等式3逐渐收敛到不动点。
卷积图神经网络 (ConvGNN) 与循环图神经网络密切相关。 ConvGNN 不是使用收缩约束迭代节点状态，而是使用固定数量的层在每一层中使用不同的权重来解决循环相互依赖关系。
图 3 说明了这一关键区别。由于图卷积更高效且更便于与其他神经网络组合，因此近年来 ConvGNN 的流行度一直在迅速增长。 ConvGNN 分为两类，基于光谱的和基于空间的。基于谱的方法通过从图信号处理的角度引入滤波器来定义图卷积[82] ，其中图卷积运算被解释为从图信号中去除噪声。基于空间的方法继承了 RecGNN 的思想，通过信息传播定义图卷积。由于 GCN [22]弥合了基于光谱的方法和基于空间的方法之间的差距，基于空间的方法由于其具有吸引力的效率、灵活性和通用性，最近得到了迅速发展。
背景基于谱的方法在图形信号处理中具有坚实的数学基础[82]、 [83]、[84]。他们假设图是无向的。归一化图拉普拉斯矩阵是无向图的数学表示，定义为 L = In − D−其中 D 是节点度数的对角矩阵， Dii = 归一化图拉普拉斯矩阵具有实对称半正定性质。有了这个属性归一化的拉普拉斯矩阵可以分解L = UΛUT其中 U = [u0, u1, · · · , un−1] ∈ Rn×n是按特征值排序的特征向量矩阵，Λ 是特征值（谱）的对角矩阵， Λii = λi 。x G g = F−1 (F(x) F(g)),背景基于谱的方法在图形信号处理中具有坚实的数学基础[82]、 [83]、[84]。他们假设图是无向的。归一化图拉普拉斯矩阵是无向图的数学表示，定义为 L = In − D−其中 D 是节点度数的对角矩阵， Dii = 归一化图拉普拉斯矩阵具有实对称半正定性质。有了这个属性，归一化的拉普拉斯矩阵可以分解为归一化拉普拉斯矩阵的特征向量形成一个正交空间，用数学术语UT U = I。在图信号处理中，图信号 x ∈ Rn是一个特征图中所有节点的向量，其中xi是第 i 个节点的值。信号 x 的图傅里叶变换定义为 F(x) = UT x，图傅里叶逆变换定义为F−1 (^x) = Ux^，其中 ^x 表示图傅里叶变换的结果信号。图傅里叶变换将输入图信号投影到正交空间，其中基础由归一化图拉普拉斯算子的特征向量形成。变换后的信号 ^x 的元素是图信号在新空间中的坐标，因此输入信号可以表示为 x = x ^iui ，这正是逆图傅里叶变换。现在输入信号 x 与滤波器 g ∈ Rn的图卷积定义为
其中表示元素乘积。如果我们将滤波器表示为gθ = diag(UT g)，则谱图卷积被 简化为
基于频谱的 ConvGNN 都遵循这个定义。关键区别在于滤波器 gθ 的选择。
谱卷积神经网络 (Spectral CNN) (k) [19]假设滤波器gθ = Θ 是一组可学习的i,j参数，并考虑具有多个通道的图信号。 Spectral CNN 的图卷积层定义为
其中k是层索引， H(k−1) ∈ Rn×fk−1是输入图信号， H(0) = X， fk−1是输入通道数是对角线充满可学习参数的矩阵。由于拉普拉斯矩阵的特征分解，Spectral CNN 面临三个限制。首先，对图的任何扰动都会导致本征基的变化。其次，学习到的过滤器是域相关的，这意味着它们不能应用于具有不同结构的图。第三，特征分解需要 O(n) 的计算复杂度。在后续工作中，ChebNet [21]和 GCN [22]通过进行多次近似和简化将计算复杂度降低到 O(m)。
Chebyshev Spectral CNN (ChebNet) [21]通过θiTi(Λ�)的对角矩阵的Chebyshev 多项式逼近滤波器gθ ，其中 Λ� = 2Λ/λmax−特征值，即gθ =In， Λ� 的值位于在 [−1, 1] 中。切比雪夫多项式由Ti(x) =2xTi−1(x)−Ti−2(x)递归定义，其中T0(x) = 1 且T1(x) = x。因此，图形信号x 与定义的滤波器gθ的卷积是
其中 L≈ = 2L/λmax − In。由于Ti(L�) = UTi(Λ�)UT ，可以通过对 i 的归纳来证明，ChebNet 的形式为，
作为对 Spectral CNN 的改进，ChebNet 定义的过滤器在空间中进行了局部化，这意味着过滤器可以独立于图形大小提取局部特征。 ChebNet 的频谱线性映射到[−1, 1]。 CayleyNet [23]进一步应用 Cayley 多项式，这是参数有理复函数来捕获窄频带。
CayleyNet 的谱图卷积定义为
其中 Re(·) 返回复数的实部， c0是实系数， cj是复系数，i 是虚数，h 是控制凯莱滤波器频谱的参数。在保留空间局部性的同时，CayleyNet 表明 ChebNet 可以被视为 CayleyNet 的特例。
图卷积网络 (GCN) [22]引入了 ChebNet 的一阶近似。假设 K = 1 和λmax = 2 ，等式8简化为
为了限制参数的数量并避免过拟合GCN 进一步假设 θ = θ0 = −θ1，导致图卷积的以下定义
为了允许多通道的输入和输出，GCN 修改了方程11转化为复合层，定义为
作为一种基于光谱的方法，GCN 也可以解释为一种基于空间的方法。从基于空间的角度来看，GCN 可以被认为是聚合来自节点邻域的特征信息。等式12可以表示为
最近的几项工作通过探索替代对称矩阵对 GCN [22]进行了增量改进。自适应图卷积网络 (AGCN) [40]学习图邻接矩阵未指定的隐藏结构关系。它通过以两个节点的特征作为输入的可学习距离函数构造所谓的残差图邻接矩阵。双图卷积网络(DGCN) [41]引入了具有两个并行图卷积层的双图卷积架构。尽管这两个层共享参数，它们使用归一化邻接矩阵 A¯ 和正点互信息 (PPMI) 矩阵，该矩阵通过从图中采样的随机游走捕获节点共现信息。 PPMI 矩阵定义为
节点 u 在采样随机游走中共同出现/出现的频率。通过集成双图卷积层的输出，DGCN 无需堆叠多个图卷积层即可对局部和全局结构信息进行编码
类似于传统 CNN 在图像上的卷积运算，基于空间的方法根据节点的空间关系定义图卷积。图像可以被认为是一种特殊形式的图形，每个像素代表一个节点。每个像素都直接连接到其附近的像素，如图1a 所示。通过对每个通道的中央节点及其相邻节点的像素值进行加权平均，将过滤器应用于 3×3 块。类似地，基于空间的图卷积将中心节点的表示与其邻居的表示进行卷积，以导出中心节点的更新表示，如图 1b 所示。从另一个角度来看，基于空间的 ConvGNN 与 RecGNN 共享相同的信息传播/消息传递思想。空间图卷积运算本质上是沿边传播节点信息。
与 GNN* 并行提出的图神经网络 (NN4G) [24]是针对基于空间的 ConvGNN 的第一项工作。与 RecGNN 截然不同的是，NN4G 通过在每一层具有独立参数的组合神经架构来学习图形相互依赖。
节点的邻域可以通过体系结构的增量构建来扩展。 NN4G 通过直接对节点的邻域信息求和来执行图卷积。它还应用剩余连接和跳过连接来记忆每一层的信息。因此，NN4G 通过以下方式导出其下一层节点状态
其中f(·)为激活函数，h 15也可以写成矩阵形式：
这类似于 GCN [22] 的形式。一个区别是 NN4G 使用未归一化的邻接矩阵，这可能会导致隐藏节点状态具有极其不同的尺度。上下文图马尔可夫模型 (CGMM) [47]提出了一种受 NN4G 启发的概率模型。在保持空间局部性的同时，CGMM 具有概率可解释性的优势。
扩散卷积神经网络 (DCNN) [25]将图卷积视为扩散过程。它假设信息以一定的转移概率从一个节点传递到它的相邻节点之一，这样信息分布可以在几轮之后达到平衡。 DCNN 将扩散图卷积定义为
概率转移矩阵 P ∈ Rn×n由 P = D−1A 计算。请注意，在 DCNN 中，隐藏表示矩阵H(k)与输入特征矩阵X 保持相同的维度，并且不是其先前隐藏表示矩阵 H(k−1) 的函数。 DCNN 连接H(1) 作为最终的模型输出。由于扩散过程的平稳分布是概率转移矩阵幂级数的总和，扩散图卷积 (DGC) [72]对每个扩散步骤的输出求和而不是串联。它通过以下方式定义扩散图卷积
其中W(k) ∈ RD×F ，f(·) 是激活函数使用转移概率矩阵的幂意味着远邻向中心节点贡献的信息非常少。 PGC‑DGCNN [46]基于最短路径增加了远邻的贡献。它定义了一个最短路径邻接矩阵S (j)
如果从节点 v 到(j)节点 u 的最短路径的长度为j，则 S = 1 否则为 0。使用超参数 r 来控制感受野大小，PGC DGCNN 引入图卷积运算如下H(k ) =
邻接矩阵可能很昂贵，O(n) 分区图卷积 (PGC) [75]根据不限于最短路径的特定标准将节点的邻居划分为 Q 组。PGC 根据每个组定义的邻域构造 Q 邻接矩阵。然后，PGC将具有不同参数矩阵的GCN [22]应用于每个邻居组并对结果求和：
消息传递神经网络 (MPNN) [27]概述了基于空间的 ConvGNN 的一般框架。它将图卷积视为一种消息传递过程，在该过程中，信息可以直接沿着边从一个节点传递到另一个节点。 MPNN 运行 K 步消息传递迭代，让信息进一步传播。消息传递函数（即空间图卷积）定义为 h (k−1)
Uk(·) 和Mk(·) 是具有可学习参数的函数。在导出每个节点的隐藏表示(K)之后，h 可以传递到输出层以执行节点级预测任务或传递到读出函数以执行图级预测任务。读出函数基于节点隐藏表示生成整个图的表示。一般定义为
其中 R(·) 表示具有可学习参数的读出函数。 MPNN 可以通过假设Uk(·)、Mk(·) 和 R(·) 的不同形式来覆盖许多现有的 GNN，例如[22]、 [85]、[86]、 [87]。然而，图同构网络（GIN） [57]发现以前基于 MPNN 的方法无法根据它们产生的图嵌入来区分不同的图结构。为了修正这个缺点，GIN 通过一个可学习的参数(k)来调整中心节点的权重 它通过以下方式执行图形卷积
其中 MLP(·) 表示多层感知器。
由于节点的邻居数量可以从一到一千甚至更多不等，因此获取节点邻域的全部大小是低效的。 GraphSage [42]采用采样的方式为每个节点获取固定数量的邻居。它通过以下方式执行图形卷积
fk(·)是聚合函数， SN(v)是节点v邻居的随机样本。聚合函数应该对节点排序的排列不变，例如均值、求和或最大值函数。
图注意力网络 (GAT) [43]假设相邻节点对中心节点的贡献既不像GraphSage [42] 那样相同，也不像 GCN [22]那样预先确定（这种差异如图4 所示）。 GAT 采用注意力学习两个连接节点之间的相对权重的机制。根据 GAT 的图卷积运算定义为，
其中 g(·) 是 LeakyReLU 激活函数，a 是可学习参数的向量。 softmax 函数确保注意权重总和为节点 v 的所有邻居中的一个。GAT 进一步执行多头注意以增加模型的表达能力。这表明在节点分类任务上比 GraphSage 有了显着的改进。虽然 GAT假设注意力头的贡献是相等的，但门控注意力网络 (GAAN) [48]引入了一种自注意力机制，该机制为每个注意力头计算额外的注意力分数。除了在空间上应用图形注意力之外，GeniePath [55]还提出了一种类似于 LSTM 的门控机制来控制跨图形卷积层的信息流。还有其他可能感兴趣的图形注意力模型[88]、 [89]。但是，它们不属于ConvGNN 框架。
混合模型网络 (MoNet) [44]采用不同的方法为节点的邻居分配不同的权重。它引入节点伪坐标来确定节点与其邻居之间的相对位置。一旦知道两个节点之间的相对位置，权重函数就会将相对位置映射到这两个节点之间的相对权重。以这种方式，图形过滤器的参数可以在不同位置共享。在 MoNet 框架下，流形的几种现有方法，例如测地线 CNN (GCNN) [90]、各向异性 CNN (ACNN) [91]、样条 CNN [92]，以及图，例如 GCN [22]、 DCNN [25]可以通过构造非参数权重函数将其推广为 MoNet的特殊实例。 MoNet 还提出了一个具有可学习参数的高斯核来自适应地学习权重函数。
另一项不同的工作通过根据特定标准对节点的邻居进行排名并将每个排名与可学习的权重相关联来实现跨不同位置的权重共享。 PATCHY‑SAN [26]根据每个节点的图标签对每个节点的邻居进行排序，并选择前 q 个邻居。图标签本质上是节点分数，可以通过节点度、中心性和 Weisfeiler Lehman 颜色[93]、 [94] 得出。由于每个节点现在都有固定数量的有序邻居，因此图结构数据可以转换为网格结构数据。 PATCHY‑SAN 应用标准的一维卷积滤波器来聚合邻域特征信息，其中滤波器权重的顺序对应于节点邻居的顺序。 PATCHY‑SAN 的排序标准仅考虑图结构，这需要大量的数据处理计算。大规模图卷积网络 (LGCN) [45]根据节点特征信息对节点的邻居进行排序。对于每个节点，LGCN 组装一个由其邻域组成的特征矩阵，并沿每一列对该特征矩阵进行排序。
排序后的特征矩阵的前q行作为中心节点的输入数据。
训练效率方面的提升
Training Con vGNNs 例如 GCN [22]通常需要将整个图数据和所有节点的中间状态保存到内存中。
ConvGNN 的全批训练算法受到内存溢出问题的严重影响，尤其是当图形包含数百万个节点时。为了节省内存，Graph Sage [42]提出了一种用于 ConvGNN 的批量训练算法。它通过以固定样本大小将根节点的邻域递归扩展 K 步来对以每个节点为根的树进行采样。对于每个采样树，GraphSage 通过从下到上分层聚合隐藏节点表示来计算根节点的隐藏表示。
Fast Learning with Graph Convolutional Network (Fast GCN) [49]为每个图卷积层采样固定数量的节点，而不是像 GraphSage [42] 那样为每个节点采样固定数量的邻居。它将图卷积解释为节点嵌入函数在概率度量下的积分变换。采用蒙特卡洛近似和方差减少技术来促进训练过程。由于 FastGCN 为每一层独立采样节点，层间连接可能是稀疏的。黄等。 [51]提出了一种自适应分层采样方法，其中下层的节点采样以顶层为条件。与 FastGCN 相比，该方法以采用更复杂的采样方案为代价实现了更高的精度。
在另一项工作中，图卷积网络随机训练 (StoGCN) [50]使用历史节点表示作为控制变量，将图卷积的感受野大小减小到任意小的规模。即使每个节点有两个邻居，StoGCN 也能达到相当的性能。然而，StoGCN 仍然需要保存所有节点的中间状态，这对于大图来说是非常耗内存的。
Cluster‑GCN [58]使用图聚类算法对子图进行采样，并对采样子图中的节点执行图卷积。由于邻域搜索也被限制在采样子图中，因此 Cluster‑GCN 能够处理更大的图并同时使用更深的架构，耗时更短，内存更少。 Cluster GCN 特别为现有的ConvGNN 训练算法提供了时间复杂度和内存复杂度的直接比较。我们根据表四分析其结果
在表IV 中， GCN [22]是进行全批次训练的基线方法。 GraphSage以牺牲时间效率为代价来节省内存。同时，GraphSage的时间和内存复杂度随着K和r的增加呈指数级增长。 Sto GCN的时间复杂度最高，内存的瓶颈没有解决。然而，Sto‑GCN可以在非常小的 r 下获得令人满意的性能。 Cluster‑GCN 的时间复杂度与基线方法相同，因为它没有引入冗余计算。在所有方法中，Cluster GCN 实现了最低的内存复杂度。
频谱模型和空间模型之间的比较
频谱模型在图形信号处理中具有理论基础。通过设计新的图形信号滤波器（例如，Cayleynets [23]），可以构建新的ConvGNN。然而，由于效率、通用性和灵活性问题，空间模型优于光谱模型。首先，光谱模型的效率低于空间模型。谱模型要么需要执行特征向量计算，要么同时处理整个图。空间模型更适合大型图，因为它们通过信息传播直接在图域中执行卷积。可以在一批节点而不是整个图中执行计算。其次，依赖图傅立叶基础的谱模型对新图的泛化能力很差。他们假设一个固定的图。对图的任何扰动都会导致本征基的变化。另一方面，基于空间的模型在每个节点上本地执行图卷积，其中可以轻松地在不同位置和结构之间共享权重。第三，基于谱的模型仅限于在无向图上运行。基于空间的模型更灵活地处理多源图输入，例如边输入[15]、 [27]、 [86]、 [95]、 [96]、有向图[25]、 [72]、有符号图[97]和异构图[98]、 [99]，因为这些图输入可以很容易地合并到聚合函数中。
在 GNN 生成节点特征后，我们可以将它们用于最终任务。但是直接使用所有这些特征在计算上可能具有挑战性，因此需要一种下采样策略。根据目标和它在网络中扮演的角色，该策略有不同的名称：（1）池化操作旨在通过对节点进行下采样以生成更小的表示来减少参数的大小，从而避免过度拟合，置换不变性和计算复杂性问题； (2)读出操作主要用于在节点表示的基础上生成图级表示。它们的机制非常相似。在本章中，我们使用池化来指代应用于 GNN的各种下采样策略。
在一些早期的工作中，图粗化算法使用特征分解来根据拓扑逻辑结构粗化图。然而，这些方法都存在时间复杂度问题。 Graclus 算法[100]是特征分解的替代方案，用于计算原始图的聚类版本。最近的一些作品[23]将其用作池化操作来粗化图形。
如今，mean/max/sum pooling是自计算以来实现降采样的最原始、最有效的方式池窗口中的均值/最大值/总和值很快
其中 K 是最后一个图卷积层的索引
赫纳夫等人。 [20]表明，在网络开始时执行简单的最大/均值池对于降低图域中的维数和减轻昂贵的图傅里叶变换操作的成本尤为重要。此外，一些作品[17]、 [27]、 [46]也使用注意力机制来增强均值/和池化
即使使用注意力机制，缩减操作（例如总和池）也不能令人满意，因为它会使嵌入效率低下：无论图大小如何，都会生成固定大小的嵌入。 Vinyals等。 [101]提出了 Set2Set 方法来生成随输入大小而增加的内存。然后它实现了一个 LSTM，该 LSTM 旨在在应用减少之前将依赖于顺序的信息集成到内存嵌入中，否则会破坏该信息。
Defferrard 等人。 [21]通过以有意义的方式重新排列图形的节点，以另一种方式解决了这个问题。他们在他们的 ChebNet 方法中设计了一种有效的池化策略。输入图首先通过 Graclus 算法 [100] 粗化为多个级别。粗化后，输入图的节点及其粗化版本被重新排列成平衡二叉树。从下往上任意聚合平衡二叉树，会将相似的节点排列在一起。汇集这样一个重新排列的信号比汇集原始信号要有效得多。
张等。 [52]提出了具有类似池化策略的 DGCNN，名为 SortPooling，它通过将节点重新排列为有意义的顺序来执行池化。与 Cheb Net [21] 不同，DGCNN 根据节点在图中的结构角色对节点进行排序。来自空间图卷积的图的无序节点特征被视为连续的 WL 颜色[93]，然后它们用于对节点进行排序。除了对节点特征进行排序外，它还通过截断/扩展节点特征矩阵将图大小统一为q。如果 n > q，则删除最后的 n‑q 行，否则添加 q‑n 零行。
上述池化方法主要考虑图的特征，忽略图的结构信息。最近，提出了一种可微分池（DiffPool） [54] ，它可以生成图的层次表示。 与之前所有的粗化方法相比，DiffPool 并不是简单地将图中的节点聚类，而是在第 k 层学习一个聚类作为符号矩阵 S，称为 S (k ) ∈ Rnk×nk+1 ，其中nk是第 k 层的节点数矩阵 S (k)中的 k 个概率
在节点特征和拓扑结构上使用其核心思想是学习同时考虑图的拓扑和特征信息的综合节点分配，因此可以使用任何标准的 ConvGNN 来实现等式28 。然而，DiffPool 的缺点是它在池化后生成密集图，此后计算复杂度变为 O(n^2)
最近，提出了SAGPool [102]方法，该方法同时考虑了节点特征和图拓扑，并以自我注意的方式学习池化。
总的来说，池化是减少图形大小的基本操作。如何提高池化的有效性和计算复杂度是一个有待研究的悬而未决的问题。
我们从不同的角度讨论图神经网络工作的理论基础。
Shape of receptive field
节点的感受野是有助于确定其最终结果的节点集合a。当合成多个空间图卷积层时，节点的感受野每次都会向其远邻节点增长一步。 Micheli [24]证明存在有限数量的空间图卷积层，使得对于每个节点 v ∈ V，节点 v 的感受野覆盖图中的所有节点。因此，ConvGNN 能够通过堆叠局部图卷积层来提取全局信息。
VC 维度
VC 维度是模型复杂性的度量，定义为模型可以打散的最大点数。关于分析GNN 的 VC 维度的工作很少。给定模型参数 p 的数量和节点 n 的数量，Scarselli 等人。 [103]得出 GNN* [15]的 VC 维度如果使用 S 形或正切双曲线激活函数则为O(p 4n 2 )，如果使用分段多项式激活函数则为 O(p 2n)。
这一结果表明，如果使用 sigmoid 或正切双曲线激活， GNN* [15]的模型复杂性会随着 p 和 n 迅速增加。
图同构
如果两个图在拓扑上相同，则它们是同构的。给定两个非同构图G1和G2， Xu等人。 [57]证明，如果 GNN 将G1和G2映射到不同的嵌入，则可以通过同构的Weisfeiler‑Lehman (WL) 测试将这两个图识别为非同构的[93]。他们表明，常见的GNN，如 GCN [22]和 GraphSage [42]无法区分不同的图结构。许等。 [57]进一步证明如果 GNN 的聚合函数和读出函数是单射的，则 GNN 在区分不同图方面至多与WL 测试一样强大。
等变性和不变性
GNN 在执行节点级任务时必须是等变函数，而在执行图级任务时必须是不变函数。对于节点级任务，令 f(A, X) ∈ Rn×d为 GNN，Q 为任意改变节点顺序的置换矩阵。如果 GNN 满足 f(QAQT , QX) = Qf(A, X)，则它是等变的。对于图级任务，令 f(A, X) ∈ Rd 。如果 GNN 满足 f(QAQT , QX)= f(A, X)，则它是不变的。为了实现等变性或不变性，GNN 的组件必须对节点顺序不变。马龙等。 [104]从理论上研究了图数据的置换不变和等变线性层的特性。
通用逼近
众所周知，具有一个隐藏层的多感知器前馈神经网络可以逼近任何 Borel可测函数[105]。 GNN 的通用逼近能力很少被研究。锤子等。 [106]证明级联相关可以近似具有结构化输出的函数。斯卡塞利等人。 [107]证明 RecGNN [15]可以逼近任何保留展开等价性的函数，达到任何精度。如果两个节点的展开树相同，则两个节点展开等价，其中节点的展开树是通过在特定深度迭代扩展节点的邻域而构建的。许等。 [57]表明，消息传递框架下的 ConvGNN [27]不是定义在多重集上的连续函数的通用逼近器。
马龙等。 [104]证明不变图网络可以逼近图上定义的任意不变函数。
图自动编码器 (GAE) 是深度神经架构，可将节点映射到潜在特征空间并从潜在表示中解码图信息。 GAE 可用于学习网络嵌入或生成新图。表V总结了所选 GAE 的主要特征。
在下文中，我们从网络嵌入和图形生成两个角度对 GAE 进行简要回顾。
网络嵌入是节点的低维向量表示，它保留了节点的拓扑信息。 GAE 使用编码器学习网络嵌入以提取网络嵌入，并使用解码器强制执行网络嵌入以保留图形拓扑信息，例如 PPMI 矩阵和邻接矩阵。
早期的方法主要使用多层感知器来构建用于网络嵌入学习的 GAE。图表示的深度神经网络 (DNGR) [59]使用堆叠式去噪自动编码器[108]通过多层感知器对 PPMI 矩阵进行编码和解码。同时，结构深度网络嵌入 (SDNE) [60]使用堆叠式自动编码器来共同保留节点的一阶邻近度和二阶邻近度。 SDNE 分别对编码器的输出和解码器的输出提出了两个损失函数。第一损失函数通过最小化节点的网络嵌入与其邻居的网络嵌入之间的距离，使学习到的网络嵌入能够保持节点的一阶邻近性。
第一个损失函数L1st定义为
其中xv = Av,:和 enc(·) 是一个由多层感知器组成的编码器。第二个损失函数使学习到的网络嵌入能够通过最小化节点输入与其重构输入之间的距离来保持节点二阶接近度。具体地，第二个损失函数L2nd定义为
其中bv,u = 1 如果Av,u = 0， bv,u = β > 1 如果Av,u = 1，并且 dec(·) 是由多层感知器组成的解码器。
DNGR [59]和 SDNE [60]只考虑节点结构信息，即节点对之间的连接性。他们忽略节点可能包含描述节点本身属性的特征信息。图自动编码器(GAE*3 ) [61]利用 GCN [22]同时对节点结构信息和节点特征信息进行编码
GAE* 的编码器由两个图形卷积层组成，其形式为
其中 Z 表示图的网络嵌入矩阵，f(·) 是 ReLU 激活函数，并且Gconv(·) 函数是由等式12定义的图卷积层。GAE* 的解码器旨在通过重构图邻接矩阵从其嵌入中解码节点关系信息，定义为
其中zv是节点 v 的嵌入。GAE* 是通过在给定真实邻接矩阵 A 和重构邻接矩阵 A^ 的情况下最小化负交叉熵来训练的
由于自动编码器的容量，简单地重建图邻接矩阵可能会导致过度拟合。Variational Graph Autoencoder (VGAE) [61]是一个变分版本
GAE 学习数据的分布。 VGAE 优化变分下界 L： L = Eq(Z|X,A) [log p(A|Z)] − KL[q(Z|X, A)||p(Z)], (33) 其中 KL(·) 是 Kullback‑ Leibler 散度函数测量两个分布之间的距离，p(Z) 是高斯先验 p(Z) = N(zi |0, I), i zj ), q(Z|X, A) = ))
平均向量µi是由公式31定义的 i ，log σi 的导出方式与使用另一个编码器的µi类似。根据等式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 没有优化重建误差，而是表明两个节点之间的关系信息可以通过负采样来保留，损失为：L(zv) = −log(dec(zv, zu))−QEvn�Pn(v)log( −dec(zv, zvn )), (34) 其中节点 u 是节点 v 的邻居，节点vn是节点 v的远节点并且从负采样分布Pn(v) 中采样，Q 是负样本。这种损失函数本质上强制近节点具有相似的表示，远距离节点具有不同的表示。
DGI [56]或者通过最大化局部互信息来驱动局部网络嵌入来捕获全局结构信息。它在实验上显示出对 GraphSage [42]的明显改进。
对于上述方法，他们本质上是通过解决链接预测问题来学习网络嵌入。
然而，图的稀疏性导致正节点对的数量远小于负节点对的数量。为了缓解学习网络嵌入中的数据稀疏性问题，另一行工作通过随机排列或随机游走将图转换为序列。这样，那些适用于序列的深度学习方法可以直接用于处理图。深度递归网络嵌入 (DRNE) [63]假设节点的网络嵌入应该近似于其邻域网络嵌入的聚合。它采用长短期记忆 (LSTM) 网络[7]来聚合节点的邻居。 DRNE 的重构误差定义为
其中zv是通过字典查找获得的节点 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 的有效性。
对于多个图，GAE 能够通过将图编码为隐藏表示并解码给定隐藏表示的图结构来学习图的生成分布。大多数用于图生成的 GAE 旨在解决分子图生成问题，这在药物发现中具有很高的实用价值。这些方法要么以顺序方式或以全局方式提出新图。
顺序方法通过逐步提出节点和边来生成图。戈麦斯等人。 [111]，库斯纳等人。 [112]，戴等人。 [113]对名为 SMILES 的分子图的字符串表示的生成过程进行建模，深度 CNN 和 RNN 分别作为编码器和解码器。
虽然这些方法是特定领域的，但替代解决方案适用于一般图，方法是将节点和边迭代地添加到不断增长的图，直到满足某个标准。图的深度生成模型(DeepGMG) [65]假设图的概率是所有可能的节点排列的总和：
其中 π 表示节点排序。它捕获图中所有节点和边的复杂联合概率。DeepGMG 通过做出一系列决策来生成图，即是否添加节点、添加哪个节点、是否添加边以及将哪个节点连接到新节点。生成节点和边的决策过程取决于节点状态和由 RecGNN 更新的生长图的图状态。在另一项工作中，GraphRNN[66]提出了图级 RNN 和边级 RNN 来模拟节点和边的生成过程。图级 RNN每次都会向节点序列添加一个新节点，而边级 RNN 会生成一个二进制序列，指示新节点与序列中先前生成的节点之间的连接。
全局方法一次输出一个图形。图变分自编码器 (GraphVAE) [67]将节点和边的存在建模为独立的随机变量。通过假设编码器定义的后验分布qφ(z|G)和解码器定义的生成分布pθ(G|z)，GraphVAE 优化了变分下界：
遵循高斯先验，φ 和 θ 是可学习的参数。使用 ConvGNN 作为编码器和简单的多层感知器作为解码器，GraphVAE 输出生成的图及其邻接矩阵、节点属性和边属性。控制生成图的全局属性（例如图连通性、有效性和节点兼容性）具有挑战性。正则化图变分自编码器 (RGVAE) [68]进一步对图变分自动编码器施加有效性约束，以正则化解码器的输出分布。分子生成对抗网络 (MolGAN)[69]集成了 convGNNs [114]、 GANs [115]和强化学习目标以生成具有所需属性的图。 MolGAN 由生成器和鉴别器组成，它们相互竞争以提高生成器的真实性。在 MolGAN 中，生成器试图提出一个假图及其特征矩阵，而鉴别器旨在将假样本与经验数据区分开来。此外，奖励网络与鉴别器并行引入，以鼓励生成的图根据外部评估器具有某些属性。 NetGAN [70]将 LSTM [7]与Wasserstein GAN [116]相结合，以基于随机游走的方法生成图形。NetGAN 训练生成器通过 LSTM 网络生成似是而非的随机游走，并强制执行鉴别器以从真实随机游走中识别假随机游走。训练后，一个新的图是由归一化基于生成器产生的随机游走计算的节点共现矩阵。
简而言之，顺序方法将图形线性化为序列。由于循环的存在，它们可能会丢失结构信息。全局方法一次生成一个图表。它们不能作为输出扩展到大图
GAE 的空间最多为 O(n^2)
许多实际应用程序中的图在图结构和图输入方面都是动态的。时空图神经网络 (STGNN) 在捕获图的动态性方面占据重要地位。此类别下的方法旨在模拟动态节点输入，同时假设连接节点之间的相互依赖性。例如，交通网络由放置在道路上的速度传感器组成，其中边缘权重由传感器对之间的距离确定。由于一条道路的交通状况可能取决于其相邻道路的状况，因此在进行交通速度预测时需要考虑空间依赖性。作为一种解决方案，STGNN 同时捕获图形的空间和时间依赖性。 STGNN 的任务可以是预测未来的节点值或标签，或者预测时空图标签。 STGNN 遵循两个方向，基于 RNN 的方法和基于 CNN 的方法。
大多数基于 RNN 的方法通过使用图卷积[48]、 [71]、 [72]过滤传递给循环单元的输入和隐藏状态来捕获时空依赖性。为了说明这一点，假设一个简单的 RNN 采用H(t) = σ(WX(t) + UH(t−1) + b)的形式，其中X(t) ∈ Rn×d是时间步长的节点特征矩阵吨
插入图卷积后，等式39变为H(t) = σ(Gconv(X(t) , A;W)+Gconv(H(t−1) , A; U) +b), (40) 其中 Gconv( ·)是一个图卷积层。图卷积循环网络 (GCRN) [71]将 LSTM 网络与 ChebNet [21] 相结合。扩散卷积递归神经网络 (DCRNN) [72]将提议的扩散图卷积层（方程式18）合并到 GRU 网络中。此外，DCRNN 采用编码器‑解码器框架来预测节点值的未来 K 步。
另一项并行工作使用节点级 RNN 和边缘级 RNN 来处理时间信息的不同方面。Structural‑RNN [73]提出了一个循环框架来预测每个时间步的节点标签。它包括两种 RNN，即 node‑RNN 和 edge‑RNN。每个节点和每条边的时间信息分别通过节点‑RNN 和边‑RNN 传递。为了合并空间信息，节点 RNN 将边缘RNN 的输出作为输入。由于为不同的节点和边假设不同的 RNN 会显着增加模型的复杂性，因此它将节点和边拆分为语义组。同一语义组中的节点或边共享相同的 RNN 模型，从而节省了计算成本。
基于 RNN 的方法存在耗时的迭代传播和梯度爆炸/消失问题。作为作为替代解决方案，基于 CNN 的方法以非递归方式处理时空图，具有并行计算、稳定梯度和低内存需求等优点。如图2d 所示，基于 CNN 的方法将 1D‑CNN 层与图卷积层交错以分别学习时间和空间依赖性。假设时空图神经网络的输入是张量 X ∈ RT ×n×d 1D‑CNN 层沿时间轴在X[:,i,:]上滑动以聚合每个节点的时间信息，而图卷积层对X[i,:,:]进行操作，以在每个时间步聚合空间信息。 CGCN [74]将一维卷积层与 ChebNet [21]或 GCN [22]层集成。它通过按顺序堆叠一个门控一维卷积层、一个图卷积层和另一个门控一维卷积层来构造一个时空块。
ST‑GCN [75]使用一维卷积层和 PGC 层（等式 20）组成时空块
以前的方法都使用预定义的图形结构。他们假设预定义的图结构反映了节点之间真正的依赖关系。然而，通过时空设置中的许多图数据快照，可以从数据中自动学习潜在的静态图结构。为了实现这一点，Graph WaveNet [76]提出了一种自适应邻接矩阵来执行图卷积。
自适应邻接矩阵定义为
其中 SoftMax 函数是沿行维度计算的，E1 表示源节点嵌入，E2 表示具有可学习参数的目标节点嵌入。
将E1与E2相乘，可以得到源节点和目标节点之间的依赖权重。使用复杂的基于 CNN 的时空神经网络，Graph WaveNet 在没有给定邻接矩阵的情况下表现良好。
学习潜在的静态空间依赖性可以帮助研究人员发现网络中不同实体之间可解释且稳定的相关性。然而，在某些情况下，学习潜在的动态空间依赖性可能会进一步提高模型精度。例如，在交通网络中，两条道路之间的行驶时间可能取决于它们当前的交通状况。 GaAN [48]采用注意力机制通过基于 RNN的方法学习动态空间依赖性。注意函数用于在给定当前节点输入的情况下更新两个连接节点之间的边权重。 ASTGCN [77]进一步包括空间注意功能和时间注意功能，以通过基于 CNN 的方法学习潜在的动态空间依赖性和时间依赖性。学习潜在空间依赖的共同缺点是需要计算每对节点之间的空间依赖权重，其成本为 O(n
由于图结构数据无处不在，因此 GNN 具有广泛的应用。在本节中，我们总结了分别对标图数据集、评估方法和开源实现。我们详细介绍了 GNN 在各个领域的实际应用。
我们主要将数据集分为四组，即引文网络、生化图谱、社交网络和其他。在表VI 中，我们总结了选定的基准数据集。补充材料 A 中提供了更多详细信息。
节点分类和图形分类是评估 RecGNN 和 ConvGNN 性能的常见任务。
节点分类
在节点分类中，大多数方法都遵循基准数据集（包括 Cora、Citeseer、Pubmed、PPI 和 Reddit）的训练/有效/测试的标准划分。他们报告了多次运行的测试数据集的平均准确度或 F1 分数。可以在补充材料 B 中找到方法实验结果的总结。应该注意的是，这些结果不一定代表严格的比较。舒尔等。确定了[131]在评估 GNN 在节点分类上的性能时的两个陷阱。首先，在所有实验中使用相同的训练/有效/测试拆分会低估泛化误差。其次，不同的方法采用了不同的训练技术，例如超参数调整、参数初始化、学习率衰减和提前停止。为了进行相对公平的比较，我们建议读者参考 Shchur 等人。 [131]。
图分类
在图分类中，研究人员通常采用 10 折交叉验证 (cv) 来进行模型评估。
然而，正如[132]所指出的，实验设置是模棱两可的，并且在不同的作品中并不统一。特别是， [132]提出了正确使用数据拆分进行模型选择与模型评估的问题。一个经常遇到的问题是每一折的外部测试集既用于模型选择又用于风险评估。 [132]在标准化和统一的评估框架中比较 GNN。他们应用外部 10 倍 CV 来估计模型的泛化性能，并应用具有 90%/10% 训练/验证拆分的内部保持技术来选择模型。另一种方法是双cv 方法，它使用外部 k 折 cv 进行模型评估，使用内部 k 折 cv 进行模型选择。我们建议读者参考[132] ，以详细和严格地比较用于图分类的 GNN 方法。
开源实现
开源实现促进了深度学习研究中基线实验的工作。在补充材料 C 中，我们提供了本文中审查的 GNN 模型的开源实现的超链接。值得注意的是，Fey 等人。 [92]在PyTorch 中发布了一个名为 PyTorch Geometric 的几何学习库，它实现了许多GNN。最近，发布了深度图库 (DGL) [133] ，它在 PyTorch 和 MXNet 等流行的深度学习平台之上提供了许多 GNN 的快速实现。
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]。
自然语言处理
GNNs 在自然语言处理中的一个常见应用是文本分类。GNN 利用文档或单词的相互关系来推断文档标签[22]、 [42]、 [43]。 尽管自然语言数据表现出顺序，但它们也可能包含内部图形结构，例如句法依赖树。句法依赖树定义了句子中单词之间的句法关系。 Marcheggiani 等人。 [152]提出了在 CNN/RNN 句子编码器之上运行的句法 GCN。句法 GCN 基于句子的句法依赖树聚合隐藏词表示。巴斯廷斯等。 [153]将句法 GCN应用于神经机器翻译任务。 Marcheggiani 等人。 [154]进一步采用与 Bastings等人相同的模型。 [153]处理句子的语义依赖图。
Graph‑to‑sequence学习学习生成具有相同含义的句子给定抽象的语义图词（称为抽象含义表示）。宋等。 [155]提出了一种图 LSTM 来编码图级语义信息。贝克等。 [156]将 GGNN [17]应用于图到序列学习和神经机器翻译。
逆向任务是序列到图的学习。在给定句子的情况下生成语义图或知识图在知识发现中非常有用[157]、 [158]。
交通准确预测交通网络中的交通速度、交通量或道路密度对于智能交通系统至关重要。 [48]、 [72]、 [74]使用 STGNN 解决交通预测问题。他们将交通网络视为一个时空图，其中节点是安装在道路上的传感器，边缘由节点对之间的距离测量，每个节点将窗口内的平均交通速度作为动态输入特征。
另一个工业级应用是出租车需求预测。鉴于历史出租车需求、位置信息、天气数据和事件特征，Yao 等人。 [159]结合由 LINE [160]训练的 LSTM、CNN 和网络嵌入，为每个位置形成联合表示，以预测某个时间间隔内某个位置所需的出租车数量。
推荐系统基于图的推荐系统将项目和用户作为节点。通过利用项目与项目、用户与用户、用户与项目以及内容信息之间的关系，基于图的推荐系统能够产生高质量的推荐。
推荐系统的关键是对项目对用户的重要性进行评分。因此，它可以转化为链接预测问题。为了预测用户和项目之间的缺失链接，Van 等人。 [161]和应等人。 [162]提出了一种使用 ConvGNN 作为编码器的 GAE。蒙蒂等。 [163]将 RNN 与图卷积相结合，以学习生成已知评级的基础过程。
化学在化学领域，研究人员应用 GNN 来研究分子/化合物的图结构。在一个分子/化合物图，原子被视为节点，化学键被视为边。节点分类、图分类和图生成是针对分子/化合物图的三个主要任务，以学习分子指纹[85]、[86]、预测分子特性[27]、推断蛋白质界面[164]、并合成化合物[65]、[69]、[165]。
其他GNN 的应用不限于上述领域和任务。人们已经探索将 GNN 应用于各种问题，例如程序验证[17]、程序推理[166]、社会影响预测[167]、对抗性攻击预防[168]、电子健康记录建模[169]、 [ 170]、大脑网络[171]、事件检测[172]和组合优化[173]。
尽管 GNN 已经证明了它们在学习图数据方面的能力，但由于图的复杂性，挑战仍然存在。在本节中，我们提出了 GNN 的四个未来方向。
模型深度
深度学习的成功在于深度神经架构[174]。然而，李等人。表明随着图卷积层数量的增加，ConvGNN 的性能急剧下降[53]。随着图卷积将相邻节点的表示推向彼此更近，理论上，对于无限数量的图卷积层，所有节点的表示将收敛到一个点 [ 53]。这就提出了一个问题，即深入研究是否仍然是学习图数据的好策略。
可扩展性
权衡GNN 的可扩展性是以破坏图的完整性为代价的。无论是使用采样还是聚类，模型都会丢失部分图形信息。通过采样，节点可能会错过其有影响力的邻居。通过聚类，图形可能会被剥夺独特的结构模式。如何权衡算法的可扩展性和图的完整性可能是未来的研究方向。
异质性
当前的大多数 GNN 都假设同质图。很难将当前的 GNN 直接应用于异构图，异构图可能包含不同类型的节点和边，或者不同形式的节点和边输入，例如图像和文本。因此，应该开发新的方法来处理异构图。
动态图
本质上是动态的，节点或边可能会出现或消失，并且节点/边输入可能会随时间变化。需要新的图卷积来适应图的动态性。尽管 STGNN 可以部分解决图的动态性问题，但很少有人考虑如何在动态空间关系的情况下执行图卷积。
在本次调查中，我们对图神经网络进行了全面的概述。我们提供了一种分类法，将图神经网络分为四类：循环图神经网络、卷积图神经网络、图自动编码器和时空图神经网络。我们对类别内或类别间的方法进行了彻底的审查、比较和总结。然后我们介绍了图神经网络的广泛应用。
总结了图神经网络的数据集、开源代码和模型评估。最后，我们提出了图神经网络的四个未来方向。