【2020 图神经网络综述】A Comprehensive Survey on Graph Neural Networks
- 未经作者允许，本文禁止转载
- 1. 摘要：
- 2. 简介：
- 2.1 为什么要用图表示数据：
- 2.2 GNN与network embedding：
- 2.3 GNN与Graph Kernel：
- 2.4 一些符号表示：
- 3. GNN的分类和基本框架：
- 3.1 GNN的结构分类：
- 3.1.1 RecGNNs：
- 3.1.2 ConvGNNs：
- 3.1.3 GAEs：
- 3.1.4 STGNNs：
- 3.2 GNN的框架分类：
- 3.2.1 GNN的输出分类：
- 3.2.2 GNN的训练分类：
- 3.2.3 统计结果：
- 4. 递归图神经网络（RecGNN）：
- 4.1 GNN ∗ ^* ∗：
- 4.2 GraphESN：
- 4.3 GGNN：
- 5. 卷积图神经网络（ConvGNN）：
- 5.1 基于频谱的ConvGNN：
- 5.1.1 基本原理：
- 5.1.2 ChebNet：
- 5.1.3 CayleyNet：
- 5.1.4 GCN：
- 5.1.5 其他工作：
- 5.2 基于空间域的ConvGNN：
- 5.2.1 基本原理：
- 5.2.2 NN4G：
- 5.2.3 其他工作：
- 5.3 提高训练效率：
- 5.3.1 批量训练：
- 5.3.2 Fast-GCN：
- 5.3.3 自适应采样：
- 5.3.4 随机训练：
- 5.3.5 Cluster-GCN：
- 5.4 频谱模式和空间域模式的比较：
- 5.5 下采样模块：
- 5.5.1 Set2Set：
- 5.5.2 ChebNet：
- 5.5.3 SortPooling：
- 5.5.4 DiffPooling：
- 5.5.5 SAGPool：
- 5.6 理论方面的讨论：
- 5.6.1 感受野大小：
- 5.6.2 VC维数：
- 5.6.3 图的同构：
- 5.6.4 同变性和不变性：
- 5.6.5 通用逼近性：
- 6. 应用：
- 6.1 数据集：
- 6.2 评估方法和开源实现：
- 6.2.1 节点分类：
- 6.2.2 图分类：
- 6.2.3 开源实现：
- 6.3 实际应用场景：
- 6.3.1 计算机视觉：
- 6.3.2 自然语言处理：
- 6.3.3 智能交通：
- 6.3.4 推荐系统：
- 6.3.5 化学领域：
- 6.3.6 其他应用：
- 7. 研究方向：
- 7.1 模型深度：
- 7.2 可扩展性的权衡：
- 7.3 异质性：
- 7.4 动态性：
- 联系方式和作者简介：
论文地址：https://arxiv.org/abs/1901.00596
未经作者允许，本文禁止转载
1. 摘要：
近年来，深度学习已经彻底改变了许多机器学习任务，从图像分类和视频处理到语音识别和自然语言理解。这些任务中的数据通常在欧几里德空间中表示。然而，在越来越多的应用中，数据从非欧几里得域生成，并表示为具有复杂关系和对象之间相互依赖关系的图形。图数据的复杂性给现有的机器学习算法带来了重大挑战。
最近，出现了许多关于扩展图形数据深度学习方法的研究。这篇文章提供了一个图神经网络GNNs在数据挖掘和机器学习领域全面的概述，并将最先进的图形神经网络分为四类，即递归图形神经网络、卷积图形神经网络、图形自动编码器和时空图形神经网络。
我们进一步讨论了跨不同领域的图神经网络的应用，并总结了图神经网络的开放源代码、基准数据集和模型评估。
最后，提出了这一快速发展领域的潜在研究方向。
2. 简介：
2.1 为什么要用图表示数据：
深度学习在许多领域的成功部分归功于快速发展的计算资源(如GPU)、大训练数据的可用性，以及深度学习从欧几里得数据（如图像、文本和视频）中提取潜在表示的有效性。以图像数据为例，我们可以将图像表示为欧几里得空间中的规则网格。卷积神经网络(CNN)能够利用图像数据的移位不变性、局部连通性和组合性。因此，CNNs可以提取局部有意义的特征，并与整个数据集共享，用于各种图像分析。
虽然深度学习有效地捕获了欧几里得数据的隐藏模式，但数据以图形形式表示的应用越来越多。例如，在电子商务中，以图形为基础的学习系统可以利用用户与产品之间的互动，作出高度准确的推荐；在化学中，分子被建模为图形，他们的生物活性需要被识别为药物发现；在引文网络中，论文通过引文相互链接，需要被分类到不同的组中。
图数据的复杂性给现有的机器学习算法带来了重大挑战。由于图可能是不规则的，一个图可能有大小不等的无序节点，而来自图的节点可能有不同数量的邻居，这导致一些重要的操作(比如卷积)在图像域中容易计算，但很难应用到图域中。此外，现有机器学习算法的一个核心假设是实例是相互独立的。这个假设不再适用于图形数据，因为每个实例（节点）通过各种类型的链接（比如引用、友谊和交互）与其他实例（节点）相关联。
因此，人们对扩展图形数据的深度学习方法越来越感兴趣。受CNNs、RNNs和深度学习带来进展，过去几年来，为了处理复杂的图形数据，对重要操作（如卷积操作等）的新概括和定义得到了迅速的发展。例如，图卷积可以从二维卷积推广。如下图所示，图像可以认为是像素由相邻像素连接的图的一种特殊情况。与2D卷积类似，我们可以通过取节点邻域信息的加权平均值来进行图形卷积。
2.2 GNN与network embedding：
GNN的研究与图嵌入或网络嵌入（network embedding）密切相关。网络编码旨在将网络节点表示为低维向量表示，以维护网络拓扑结构和节点内容信息，并且便与后续图像和数据分析任务，如分类、聚类等。与此同时，GNN是一种深度学习模型，旨在以端到端方式解决与图结构相关的任务。
GNN与网络嵌入的主要区别在于，GMM是针对各种任务而设计的一组神经网络模型，而网络嵌入涵盖了针对同一任务的各种方法。因此，GNNs可以通过一个图形自动编码器框架来解决网络嵌入问题。另一方面，网络嵌入还包含其他非深度学习方法，如矩阵分解、随机游走等。
2.3 GNN与Graph Kernel：
Graph Kernel历来是解决图分类问题的主要技术。这些方法使用一个核函数来度量图对之间的相似性，那么这样基于核的算法（如支持向量机）就可以用于图的监督学习。与GNN类似，Graph Kernel可以通过映射函数将图或节点嵌入到向量空间中。不同的是，这个映射函数是确定性的，而不是可学习的。由于Graph Kernel方法采用两两相似度计算，因此存在较大的计算瓶颈。一方面，GNN直接根据所提取的图表示进行图分类，因此比Graph Kernel方法效率高得多。
2.4 一些符号表示：
3. GNN的分类和基本框架：
3.1 GNN的结构分类：
在本节中，我们将介绍图神经网络的分类，如下表所示：
这里将图神经网络（GNNs）分为递归图神经网络（RecGNNs）、卷积图神经网络（ConvGNNs）、图自编码器（GAEs）和时空图神经网络（STGNNs）。下面给出了各种模型架构的例子。
3.1.1 RecGNNs：
RecGNN基本上算是 GNN 的先驱，旨在通过循环神经体系结构学习节点表示。它们假设图中的节点不断与其邻居交换信息/消息，直到达到稳定的平衡。RecGNN 在概念上很重要，并启发了后来对卷积图神经网络的研究。
3.1.2 ConvGNNs：
ConvGNNs概括了从网格数据到图数据的卷积操作。主要思想是通过汇总节点自身的特征 x v x_v xv和邻居的特征 x u x_u xu来生成节点 v v v的表示形式，其中 u ∈ N ( v ) u\in N(v) u∈N(v)。与 RecGNN 不同，ConvGNN 堆叠多个图卷积层以提取高级节点的特征表示。ConvGNN 在建立许多其他复杂的 GNN 模型中起着核心作用。
3.1.3 GAEs：
GAEs是无监督的学习框架，可将节点/图编码到潜在的矢量空间中，并从编码后的信息中重建图数据。 GAE 用于学习网络嵌入和图生成分布。 对于网络嵌入，GAE 主要通过重建图结构信息（如图邻接矩阵）来学习潜在节点表示。对于图生成，某些方法逐步生成图的节点和边，而其他方法则一次全部输出图。
3.1.4 STGNNs：
STGNNs旨在从时空图学习隐藏模式，这种模式在各种应用中变得越来越重要，例如交通速度预测，驾驶员操纵预期和人类行为识别。 STGNN 的关键思想是同时考虑空间依赖性和时间依赖性。 许多当前的方法将图卷积与 RNN 或 CNN 集成在一起以捕获空间依赖性，从而对时间依赖性进行建模。
3.2 GNN的框架分类：
3.2.1 GNN的输出分类：
将图形结构和节点内容信息作为输入，GNNs的输出可以聚焦于不同的图形分析任务。
- 节点级输出与节点回归和分类任务有关。 RecGNN 和 ConvGNN 可以通过信息传播/图卷积来提取高级节点表示。 使用多感知器层或 softmax 层作为输出层，GNN能够以端到端的方式执行节点级任务。
- 边级输出与边的分类和链接预测任务相关。将来自 GNN 的两个节点的隐藏表示作为输入，可以利用相似度函数或神经网络来预测边的标签/连接强度。
- 图级输出与图分类任务有关。 为了获得图级的紧凑表示，GNN 通常与池化和readout操作结合使用。
3.2.2 GNN的训练分类：
许多 GNN （例如 ConvGNN）可以在端到端学习框架内以（半）监督或完全无监督的方式训练，具体取决于学习任务和数据集中可用的标签信息：
- 节点级分类的半监督学习：给定一个带有部分节点被标记而其他节点未被标记的单个网络，ConvGNN 可以学习一个健壮的模型，该模型可以有效地识别未标记节点的类标签。 为此，可以通过堆叠几个图卷积层，然后堆叠用于多类分类的 softmax 层，来构建端到端框架。
- 图级分类的监督学习：图级分类旨在预测整个图的类标签。 可以通过图卷积层，图池化层和/或读出层的组合来实现此任务的端到端学习。 图卷积层负责精确的高级节点表示，而图池化层则充当下采样的角色，从而每次将每个图都粗化为子结构。 读出层将每个图的节点表示折叠为图表示。 通过将多层感知器和 softmax 层应用于图表示，我们可以建立一个用于图分类的端到端框架。
- 图嵌入的无监督学习：当图中没有类标签可用时，我们可以在端到端框架中以纯粹无监督的方式学习图嵌入。这些算法以两种方式利用边级信息。一种简单的方法是采用自动编码器框架，其中编码器使用图卷积层将图嵌入到潜在表示中，在该表示上使用解码器来重构图结构。另一种流行的方法是利用负采样方法，该方法将一部分节点对采样为负对，而图中具有链接的现有节点对为正对。 然后在卷积层之后应用逻辑回归层进行端到端学习。
3.2.3 统计结果：
下表总结了具有代表性的 RecGNN 和 ConvGNN 的主要特征。在不同的模型中比较了输入、池化层、读出层和时间复杂度。
4. 递归图神经网络（RecGNN）：
递归图神经网络（RecGNNs）是网络神经网络的先驱。它们在图中的节点上递归应用相同的参数集，以提取高级节点表示。受计算能力的限制，早期的研究主要集中在有向无环图上。
4.1 GNN ∗ ^* ∗：
Scarselli等人提出的图神经网络（GNN ∗ ^* ∗）扩展了之前的递归模型，以处理一般类型的图，如无环图、循环图、有向图和无向图。基于信息扩散机制，GNN ∗ ^* ∗通过递归交换邻域信息来更新节点状态，直到达到稳定平衡。节点的隐藏状态通过下式递归更新：
其中 f ( ⋅ ) f(·) f(⋅)是一个参数函数，并且 h v ( 0 ) h_v^{(0)} hv(0)被随机初始化。 ∑ \sum ∑求和操作使得GNN ∗ ^* ∗能够应用到所有的节点上（即使邻居的数目不同并且邻居的排序未知）。为了保证能够收敛，递归函数 f ( ⋅ ) f(·) f(⋅)必须是一种压缩映射（contraction mapping），即能够在将两点投射到一个潜在空间后，缩小两点之间的距离。
那么当 f ( ⋅ ) f(·) f(⋅)为神经网络时，参数的雅可比矩阵（Jacobian）必须加一个惩罚项。当满足收敛准则时，将最后一步节点隐藏状态转发到读出层。GNN ∗ ^* ∗交替节点状态传播阶段和参数梯度计算阶段，以最小化训练目标，这个策略使GNN ∗ ^* ∗能够处理循环图。
4.2 GraphESN：
在后续的研究中，Graph Echo State Network （GraphESN，上图）对Echo State networks进行了扩展，提高了GNN ∗ ^* ∗的训练效率。GraphESN由编码器和输出层组成。编码器是随机初始化的，不需要训练。它实现了一个压缩状态转换函数来递归地更新节点状态，直到全局图状态达到收敛。然后以固定节点状态作为输入对输出层进行训练。
4.3 GGNN：
门控图神经网络（GGNN，上图）采用门控递归单元（GRU）作为递归函数，将递归减少到固定的步数。其优点是它不再需要约束参数来确保收敛。节点的隐藏状态由其先前的隐藏状态和相邻的隐藏状态更新，定义为：
其中 h v ( 0 ) = x v h_v^{(0)}=x_v hv(0)=xv。跟GNN ∗ ^* ∗和GraphESN不同的是，GGNN使用时间反向传播（BPTT）算法来学习模型参数。对于大型图来说，这可能是一个问题，因为GGNN需要在所有节点上多次运行循环函数，这需要将所有节点的中间状态存储在内存中。
随机稳态嵌入（SSE，上图）提出了一种可扩展到大图的学习算法。SSE以随机异步的方式递归更新节点隐藏状态。它交替抽取一批节点进行状态更新，抽取一批节点进行梯度计算。为保持稳定性，将SSE的回归函数定义为历史状态和新状态的加权平均，其形式为：
其中 α \alpha α是一个超参数， h v ( 0 ) h_v^{(0)} hv(0)被随机初始化。虽然SSE在概念上很重要，但通过反复应用上述公式，SSE并没有在理论上证明节点状态会逐渐收敛到不动点。
5. 卷积图神经网络（ConvGNN）：
卷积图神经网络（ConvGNNs）与循环图神经网络有着密切的关系。ConvGNNs没有使用收缩约束迭代节点状态，而是在架构上使用固定数量的层，每个层的权重不同，来解决循环相互依赖问题。这个关键区别如上图所示。
由于图卷积与其他神经网络的合成更加高效和方便，近年来非常流行。ConvGNNs分为两类，分别基于频谱和空间域。基于频谱的方法通过从图像信号处理的角度定义图上的卷积核，并将图卷积操作解释为从图信号移除噪声。基于空间域的方法继承了RecGNNs的思想，通过信息传播来定义图形卷积。由于GCN填补了基于频谱的方法和基于空间域的方法之间的差距，基于空间的方法由于其具有吸引力的效率、灵活性和通用性，最近得到了迅速发展。
5.1 基于频谱的ConvGNN：
5.1.1 基本原理：
基于频谱的卷积图神经网络在图信号处理方面有着坚实的数学基础。其中归一化的图拉普拉斯矩阵可以看作是一个无向图的数学表示，定义为：
其中 D D D 是节点度数的对角矩阵， D i i = ∑ j ( A i , j ) D_{ii}=\sum_j(A_{i,j}) Dii=∑j(Ai,j)。并且归一化图拉普拉斯矩阵具有实对称半正定的性质。利用这个性质，可以将规范化的拉普拉斯矩阵分解为：
其中 U = [ u 0 , u 1 , . . . , u n − 1 ] ∈ R n × n U = [u_0, u_1, ..., u_{n-1}]\in R^{n×n} U=[u0,u1,...,un−1]∈Rn×n 是由特征值排序的特征向量的矩阵， Λ Λ Λ 是特征值（频谱）的对角矩阵并且 Λ i i = λ i Λ_{ii}=\lambda_i Λii=λi。
用数学术语来说，归一化拉普拉斯矩阵的特征向量就构成了一个标准正交空间，即：
在图信号处理中，一个图信号 x ∈ R n x\in R^n x∈Rn 是图上的所有顶点的一个特征向量，并且 x i x_i xi 代表第 i i i 个顶点的值。那么信号 x x x 的图的傅里叶变换就可以定义为：
同样可以定义图的反傅里叶变换：
其中 x ^ \hat{x} x^ 代表图傅里叶变换的结果。
因此图的傅里叶变换将输入图信号投射到标准正交空间，其中基由归一化图的拉普拉斯特征向量构成。元素的转换信号 x ^ \hat{x} x^ 是图的信号在新空间的坐标，因此输入信号可以表示为：
这恰好就是反傅里叶变换。
那么现在输入信号 x x x 与滤波器 g ∈ R n g∈R^n g∈Rn 的图卷积就可以定义为：
其中 ⨀ \bigodot ⨀ 代表元素积。如果我们假设一个滤波器 g θ = d i a g ( U T g ) g_{\theta}=diag(U^Tg) gθ=diag(UTg)，那么频域图卷积就可以简化为：
所有基于频谱的卷积都遵循这一定义，它们关键的区别在于滤波器的选择。
基于频谱的卷积神经网络假设 g θ = Θ i , j ( k ) g_{\theta}=\Theta^{(k)}_{i,j} gθ=Θi,j(k) 是一组可学习的参数，并且考虑多通道的图信号。那么基于频谱的图卷积层就可以定义为：
其中 k k k 是层索引， H ( k − 1 ) ∈ R n × f k − 1 H^{(k-1)}\in R^{n×f_{k-1}} H(k−1)∈Rn×fk−1 是输入的图信号，并且 H ( 0 ) = X H^{(0)}=X H(0)=X， f k − 1 f_{k-1} fk−1 是输入的通道数， f k f_k fk 是输出的通道数。 Θ i , j ( k ) \Theta^{(k)}_{i,j} Θi,j(k) 是一个填充了可学习参数的对角矩阵。
由于Laplacian矩阵的特征分解，基于频谱的卷积神经网络面临三个限制：
- 首先，对图的任何扰动都会导致特征基的变化。
- 其次，学习到的滤波器参数是依赖于域的，这意味着它们不能应用于具有不同结构的图。
- 最后，特征分解需要 O ( n 3 ) O(n^3) O(n3) 的计算复杂度。
在后续的工作中，ChebNet和GCN通过进行几个近似和简化，将计算复杂度降低到 O ( m ) O(m) O(m)。
5.1.2 ChebNet：
Chebyshev Spectral CNN（切比雪夫频域卷积神经网络，简称ChebNet）通过特征值对角矩阵的切比雪夫多项式近似估计滤波器 g θ g_{\theta} gθ，例如 g θ = ∑ i = 0 K θ i T i ( Λ ^ ) g_{\theta}=\sum^K_{i=0}\theta_iT_i(\hat{Λ}) gθ=∑i=0KθiTi(Λ^)，其中 Λ ^ = 2 Λ / λ m a x − I n \hat{Λ}=2Λ/\lambda_{max}-I_n Λ^=2Λ/λmax−In，并且 Λ Λ Λ 的值在区间 [ − 1 , 1 ] [-1, 1] [−1,1] 之间。切比雪夫多项式被递归地定义为：
其中 T 0 ( x ) = 1 ， T 1 ( x ) = x T_0(x)=1，T_1(x)=x T0(x)=1，T1(x)=x。因此图信号 x x x 的卷积就可以定义为：
其中：
可以用归纳法证明：
那么ChebNet的形式就可以改写为：
作为对基于频谱的CNN的改进，ChebNet的滤波器是在空间上定义的，这意味着滤波器可以独立于图的大小提取来局部特征。ChebNet的频谱特征被线性映射到区间 [ − 1 , 1 ] [-1, 1] [−1,1]。
5.1.3 CayleyNet：
CayleyNet进一步应用参数有理复函数Cayley多项式来捕捉狭窄的频段。CayleyNet的谱图卷积定义为：
其中 R e ( ⋅ ) Re(·) Re(⋅) 返回复数的实数部分， c 0 c_0 c0 为实系数， c j c_j cj为复系数， i i i 为虚数， h h h 为控制Cayley滤波器频谱的参数。在保持空间局部性的同时，CayleyNet表明ChebNet可以视为CayleyNet的特例。
5.1.4 GCN：
卷积图神经网络（GCN）引入了ChebNet的一阶近似，即假设 K = 1 K=1 K=1 并且 λ m a x = 2 \lambda_{max}=2 λmax=2，那么下述式子：
可以简化为：
为了抑制参数量并避免过拟合，GCN进一步假设：
因此图卷积可以进一步定义为：
同时为了实现多通道输入和输出，GCN进一步将上述式子修改为组成层，定义为：
其中：
并且 f ( ⋅ ) f(·) f(⋅) 是激活函数。
然而使用 I n + D − 1 2 A D − 1 2 I_n+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} In+D−21AD−21 进行实验会导致GCN的数值不稳定。为了解决这个问题，GCN使用了归一化的技巧来替代上式：
其中：
尽管GCN是频域方法，但是它也可以解释为基于空间域的方法。从空间域的角度来看，GCN可以被认为是从一个节点的邻域聚集特征信息：
5.1.5 其他工作：
最近的一些工作通过探索可选对称矩阵对GCN进行了改进。自适应图卷积网络（AGCN）学习由图邻接矩阵未指定的隐藏结构关系。它通过一个可学习的距离函数构造一个所谓的残差图邻接矩阵，该函数以两个节点的特征作为输入。
Dual Graph Convolutional Network （DGCN）引入了并行两个Graph Convolutional layer的Dual Graph Convolutional architecture。虽然这两层共享参数，但它们使用标准化邻接矩阵 A ‾ \overline{A} A和正点态互信息（PPMI）矩阵，该矩阵通过从图中采样的随机游走获取节点共现信息。定义PPMI矩阵为：
其中 v 1 , v 2 ∈ V , ∣ D ∣ = ∑ v 1 , v 2 c o u n t ( v 1 , v 2 ) v_1,v_2\in V, |D|=\sum_{v_1,v_2}count(v_1,v_2) v1,v2∈V,∣D∣=∑v1,v2count(v1,v2)，并且 c o u n t ( ⋅ ) count(·) count(⋅) 函数返回返回节点 v v v和/或节点 u u u在抽样随机游动中同时发生的频率。通过集成对偶图卷积层的输出，DGCN可以编码局部和全局结构信息，而不需要堆叠多个图卷积层。
5.2 基于空间域的ConvGNN：
5.2.1 基本原理：
与传统CNN对图像的卷积操作类似，基于空间的方法根据节点的空间关系来定义图形卷积。图像可以看作是一种特殊形式的图形，每个像素代表一个节点。每个像素直接与其附近的像素相连接，如下图所示：
通过对每个通道的中心节点及其相邻节点的像素值进行加权平均，对一个3×3的patch进行滤波。类似地，基于空间的图形卷积将中心节点的表示与其邻居的表示进行卷积，从而得到中心节点的更新表示，如图所示：
从另一个角度来看，基于空间的ConvGNNs与RecGNNs在信息传播/消息传递方面有着相同的理念，即空间图的卷积操作本质上是沿边缘传播节点信息。
5.2.2 NN4G：
与GNN ∗ ^* ∗并行提出的图神经网络（NN4G），是第一个基于空间的卷积图神经网络。与RecGNNs不同的是，NN4G通过每层具有独立参数的组合神经结构来学习图的相互依赖性。节点的邻域可以通过架构的增量构建来扩展。NN4G通过直接总结节点的邻域信息来执行图的卷积，并利用剩余连接和跳过连接来记忆每一层的信息。因此，NN4G通过下式生成其下一层节点状态：
其中 f ( ⋅ ) f(·) f(⋅) 是激活函数， h v ( 0 ) = 0 h_v^{(0)}=0 hv(0)=0。上述式子也可以写成矩阵的形式：
它类似于GCN的形式。一个不同之处在于，NN4G使用了非标准化的邻接矩阵，这可能会导致隐藏节点状态具有极其不同的尺度。
5.2.3 其他工作：
CGMM：
上下文图马尔可夫模型（CGMM）提出了一个受NN4G启发的概率模型。在保持空间局部性的同时，CGMM具有概率可解释性的优点。
DCNN：
扩散卷积神经网络（DCNN）将图卷积看作是一个扩散过程。它假设信息以一定的转移概率从一个节点转移到相邻节点，使信息分布经过几轮后达到均衡。DCNN将扩散图卷积定义为：
其中 f ( ⋅ ) f(·) f(⋅) 是激活函数，并且概率迁移矩阵 P ∈ R n × n P\in R^{n×n} P∈Rn×n 通过 P = D − 1 A P=D^{-1}A P=D−1A 计算。注意在DCNN中，隐藏表示矩阵 H ( k ) H^{(k)} H(k) 与输入的特征矩阵 X X X 维度相同，而不是之前隐藏表示矩阵 H ( k − 1 ) H^{(k-1)} H(k−1) 的函数。DCNN将 H ( 1 ) , H ( 2 ) , . . . , H ( K ) H^{(1)},H^{(2)},...,H^{(K)} H(1),H(2),...,H(K) 连接在一起作为最后的模型输出。
DGC：
由于扩散过程的平稳分布是概率转移矩阵的幂级数的和，所以扩散图卷积（diffusion Graph Convolution, DGC）对每个扩散步骤的输出进行汇总而不是串联。它定义了扩散图卷积：
其中 W ( k ) ∈ R D × F W^{(k)}\in R^{D×F} W(k)∈RD×F 并且 f ( ⋅ ) f(·) f(⋅) 是激活函数。然而使用转移概率矩阵的幂意味着遥远的邻居对中心节点贡献很少的信息。
PGC-DGCNN：
PGC-DGCNN基于最短路径增加了遥远邻居顶点的贡献。它定义了一个最短路径邻接矩阵 S ( j ) S^{(j)} S(j)。如果从顶点 v v v 到顶点 u u u 的最短路径长度为 j j j，那么 S v , u ( j ) = 1 S^{(j)}_{v,u}=1 Sv,u(j)=1，否则为 0 0 0。通过引入超参数 r r r 来控制感受野大小，PGC-DGCNN将图卷积操作定义如下：
其中：
并且 ∣ ∣ || ∣∣ 表示向量连接操作。最短路径的邻接矩阵计算复杂度最大为 O ( n 3 ) O(n^3) O(n3)。
PGC：
分区图卷积（Partition Graph Convolution，PGC）根据一定的准则将节点的邻居划分为 Q Q Q 组，而不局限于最短路径。PGC根据每组定义的邻域构造 Q Q Q 个邻接矩阵。然后，PGC将参数矩阵不同的GCN应用于每个邻居组，并将结果相加：
其中：
并且：
MPPN：
消息传递神经网络（MPNN）概述了基于空间的图卷积神经网络的总体框架。它将图形卷积视为一种信息传递过程，在此过程中，信息可以沿边缘直接从一个节点传递到另一个节点。MPNN运行 K K K 步消息传递迭代，从而让信息进一步传播。消息传递函数（即空间图卷积）定义为：
其中 h v ( 0 ) = x v h_v^{(0)}=x_v hv(0)=xv， U k ( ⋅ ) U_k(·) Uk(⋅) 和 M k ( ⋅ ) M_k(·) Mk(⋅) 是有可学习参数的函数。
在派生出每个节点的隐藏表示后， h v ( K ) h_v^{(K)} hv(K) 可以被传递到输出层执行节点级预测任务，或者被传递到读出函数执行图级预测任务。读出函数根据节点隐藏表示生成整个图的表示。它通常被定义为：
其中 R ( ⋅ ) R(·) R(⋅) 表示有可学习参数的读出函数。通过假设不同的 U k ( ⋅ ) , M k ( ⋅ ) , R ( ⋅ ) U_k(·),M_k(·),R(·) Uk(⋅),Mk(⋅),R(⋅) 不同的形式，MPNN可以涵盖许多已经提出的GNNs。
GIN：
然而，图同构网络（GIN）发现，以往基于MPNN的方法无法根据产生的图嵌入来区分不同的图结构。为了弥补这一缺陷，GIN通过一个可学习参数 ϵ ( k ) \epsilon^{(k)} ϵ(k) 来调整中心节点的权值。它通过以下式子执行图的卷积：
其中 M L P ( ⋅ ) MLP(·) MLP(⋅) 表示一个多层感知器。
GraphSage：
由于节点的邻居的数量可以从1个到1000个甚至更多，因此计算顶点的完整邻居的大小是低效的。因此GraphSage采用抽样的方法，为每个节点获得固定数量的邻居。它通过以下式子执行图的卷积：
其中 h v ( 0 ) = x v h_v^{(0)}=x_v hv(0)=xv 是一个聚合函数， S N ( v ) S_{N(v)} SN(v) 是对顶点 v v v 的邻居的随机采样。注意聚合函数应该对节点顺序的排列如均值、和或者最大值函数不变。
GAT：
Graph Attention Network （GAT）假设邻近节点对中心节点的贡献既不像GraphSage那样完全相同，也不像GCN那样是预先确定的（这种差异如上图所示），GAT采用注意机制来学习两个连通节点之间的相对权值。根据GAT的图卷积操作定义为：
其中 h v ( 0 ) = x v h_v^{(0)}=x_v hv(0)=xv，并且注意力权重 α v u ( k ) \alpha^{(k)}_{vu} αvu(k) 用来衡量顶点 v v v 与其邻居 u u u 之间的连接强度：
其中 g ( ⋅ ) g(·) g(⋅) 是 L e a k y R e L U LeakyReLU LeakyReLU 激活函数， a a a 表示可学习的向量。 s o f t m a x softmax softmax 激活函数保证了顶点 v v v 的邻居的注意力权重之和为 1 1 1。
GAT进一步提高了模型的表达能力，在节点分类任务上比GraphSage有了很大的改进。
GAAN：
尽管GAT假设注意头的贡献度相等，门控注意网络（Gated Attention Network，GAAN）引入了一个自我注意机制，该机制为每个注意头计算一个额外的注意分数。
除了在空间上应用图注意力，GeniePath进一步提出了一种类似LSTM的门控机制来控制跨图卷积层的信息流。还有其他可能值得关注的图形注意模型。但是它们不属于ConvGNN框架。
5.3 提高训练效率：
5.3.1 批量训练：
训练像GCN这样的图卷积神经网络通常需要将整个图数据和所有节点的中间状态保存到内存中。图卷积神经网络的全批处理训练算法存在着严重内存溢出问题，特别是在图中包含数百万节点时。为了节省内存，GraphSage提出了一种批量训练算法。它以每个结点为根，在固定样本容量的情况下，通过递归地扩展根结点的邻域 K K K 步来对树进行采样。对于每棵采样树，GraphSage通过自下而上分层聚合隐藏节点表示来计算根节点的隐藏表示。
5.3.2 Fast-GCN：
Graph Convolutional Network （Fast-GCN）的快速学习方法为每个Graph Convolutional layer采样固定数量的节点，而不是像GraphSage那样为每个节点采样固定数量的邻居。它将图的卷积解释为节点嵌入函数在概率测度下的积分变换，并采用蒙特卡罗近似和方差减少技术来简化训练过程。
5.3.3 自适应采样：
由于Fast-GCN为每一层独立地示例节点，层之间的连接可能是稀疏的。Huang等人提出了一种自适应分层抽样方法，其中下层节点的抽样条件是上层节点的抽样。与Fast-GCN相比，该方法获得了更高的精度，但采用了更复杂的采样方案。
5.3.4 随机训练：
在另一项工作中，StoGCN利用历史节点表示作为控制变量，对图卷积网络进行随机训练，将图卷积的接受野减小到任意小的规模。即使每个节点有两个邻居，StoGCN也可以获得相当不错的性能。但是，StoGCN仍然需要保存所有节点的中间状态，这对于大型图来说是消耗内存的。
5.3.5 Cluster-GCN：
Cluster-GCN使用图聚类算法对一个子图进行采样，并对采样的子图内的节点进行图卷积。由于邻域搜索也被限制在采样的子图中，因此Cluster-GCN能够同时处理更大的图，使用更深层的架构，并且用更少的时间和更少的内存。值得注意的是，Cluster-GCN为现有图卷积神经网络训练算法的时间复杂度和内存复杂度提供了一个直观的比较，如下表所示：
5.4 频谱模式和空间域模式的比较：
通过设计新的图信号滤波器（如Cayleynets），可以建立新的图卷积神经网络。然而，由于效率、通用性和灵活性等问题，空间域模型比频谱模型更受青睐。
- 首先，频谱模型的效率低于空间域模型。频谱模型要么需要进行特征向量计算，要么同时处理整个图。空间域模型对大型图具有更大的可伸缩性，因为它们通过信息传播直接在图域中执行卷积。计算可以在一批节点中进行，而不是在整个图中进行。
- 其次，依赖于图傅里叶基的谱模型很难推广到新的图。假设有一个固定的图，对图的任何扰动都会导致特征基的改变。另一方面，基于空间域的模型在每个节点上执行局部的图卷积，在不同位置和结构之间可以轻松地共享权值。
- 最后，基于频谱的模型只能在无向图上运行。基于空间的模型更灵活地处理多源图输入，如边输入、有向图、有符号图和异构图，因为这些图输入可以很容易地合并到聚合函数中。
5.5 下采样模块：
在GNN生成节点特征之后，就可以将它们用于最终任务。但直接使用所有这些特征在计算复杂度上具有挑战性，因此需要采用下采样策略。根据目标和在网络中的功能，下采样策略可以分为以下几类：
- 池化操作：池化的目的是通过对节点进行向下采样来减少参数的大小，从而产生更小的表示，从而避免过拟合、置换不变性和计算复杂度问题。
- 读出操作：读出主要用于基于节点表示生成图级表示。
它们的机制非常相似但也有一定的不同。
在一些早期的研究中，图粗化算法使用特征分解来根据图的拓扑结构进行粗化。然而，这些方法都存在时间复杂度问题。Graclus算法是特征分解的另一种方法，用于计算原始图的聚类版本。一些最近的工作使用它作为一个池操作来粗化图。
目前，由于在池窗口中计算均值/最大值/和的速度非常快，均值/最大值/和池化是实现下采样最原始、最有效的方法：
其中 K K K 是最后一个卷积层的索引。
Henaff等人表明，在网络开始时执行一个简单的最大池化或者均值池化层对于降低图域的维数和减少计算复杂的图傅里叶变换操作的代价尤为重要。此外，一些模型也使用了注意机制来增强均值池化或者和池化层。
5.5.1 Set2Set：
即使有了注意机制，下采样操作（比如和池）也不能令人满意，因为它使得图嵌入效率低下：无论图的大小，都会生成固定大小的嵌入。Vinyals等人提出了Set2Set方法来生成随着输入大小增加的内存。随后它实现一个LSTM，用于在下采样可能破坏信息之前，将依赖序列顺序的信息集成到内存嵌入中。
5.5.2 ChebNet：
Defferrard等人用另一种方式解决了这个问题，即以一种有意义的方式重新排列图中的节点。他们在他们的方法ChebNet中设计了一个有效的集中策略，即首先将输入图粗化到多个层次。粗化后，输入图及其粗化版本的节点被重新排列成平衡二叉树。任意地从下到上聚合平衡二叉树会将相似的节点排列在一起。将这样重新安排的信号合用比将原始信号合用效率高得多。
5.5.3 SortPooling：
Zhang等人提出了具有类似池策略的DGCNN，名为SortPooling，即通过将节点重新安排到一个有意义的顺序来执行池化。与ChebNet不同，DGCNN根据节点在图中的结构角色对节点进行排序。空间图卷积产生的图的无序节点特征被视为连续的WL颜色，然后使用它们对节点进行排序。除了对节点特征进行排序，它还通过截断/扩展节点特征矩阵将图的大小统一到 q q q。如果有 n > q n > q n>q，则删除最后的 n − q n-q n−q 行，否则添加 q − n q-n q−n 行。
5.5.4 DiffPooling：
上述的pooling方法主要考虑图的特征，而忽略了图的结构信息。最近一种可微池（DiffPool）被提出，它可以生成图的层次表示。与之前所有粗化方法相比，DiffPool并不是简单地对图中的节点进行聚类，而是学习第 k k k 层上的聚类分配矩阵 S S S，即 S ( k ) ∈ R n k × n k + 1 S^{(k)}\in R^{n_k×n_{k+1}} S(k)∈Rnk×nk+1。其中， n k n_k nk 是第 k k k 层的顶点数目，并利用节点特征和拓扑结构生成矩阵 S ( k ) S^{(k)} S(k) 中的概率值：
其核心思想是学习综合考虑图的拓扑和特征信息的节点分配，因此上述等式可以用任何标准图卷积神经网络实现。然而，DiffPool的缺点是池化后生成稠密图，计算复杂度变成O(n2)。
5.5.5 SAGPool：
最近有研究者提出了SAGPool方法，该方法同时考虑节点特征和图的拓扑结构，并以自注意的方式学习池。
总的来说，池化是减小图神经网络计算复杂度的必要操作。如何提高池的效率和计算复杂度是一个有待研究的问题。
5.6 理论方面的讨论：
这一节从不同的角度讨论了图神经网络的理论基础。
5.6.1 感受野大小：
节点的感受野是决定最终节点表示的一组节点。在复合多个空间图形卷积层时，节点的感受野每次都向其遥远的邻居一步。Micheli证明空间图的卷积层数量有限，使得对于每个节点 v ∈ V v∈V v∈V，节点 v v v 的感受野覆盖图中的所有节点。因此，图卷积神经网络能够通过叠加局部图卷积层来提取全局信息。
5.6.2 VC维数：
VC维数是一个模型复杂度的度量，它定义为一个模型可以打碎的最大数量的点。目前对网络节点VC维数的分析还比较少。已知模型参数量 p p p 和节点数 n n n , Scarselli等人推导出，如果使用 s i g m o i d sigmoid sigmoid或 t a n h tanh tanh激活，则GNN ∗ ^* ∗的VC维数为 O ( p 4 n 2 ) O(p^4n^2) O(p4n2)，如果使用分段多项式激活函数，则为 O ( p 2 n ) O(p^2n) O(p2n)。这一结果表明，如果采用 s i g m o i d sigmoid sigmoid或 t a n h tanh tanh激活，GNN ∗ ^* ∗的模型复杂度随 p p p 和 n n n 的增加而迅速增加。
5.6.3 图的同构：
如果两个图拓扑相同，则它们是同构的。给定两个非同构图 G 1 G_1 G1和 G 2 G_2 G2, Xu等证明了如果一个GNN将 G 1 G_1 G1和 G 1 2 G_12 G12映射到不同的嵌入中，这两个图可以通过同构weisfeler - lehman （WL）检验判定为非同构。它们表明，通用的GNN（比如GCN和GraphSage）无法区分不同的图结构。Xu等人进一步证明了如果一个GNN的聚合函数和读出函数是内射的，那么GNN在区分不同图的能力上最多可以达到WL检验的水平。
5.6.4 同变性和不变性：
执行节点级任务时，GNN必须是等变函数；执行图形级任务时，GNN必须是不变函数。
对于节点级任务，假设 f ( A , X ) ∈ R n × d f(A,X)\in R^{n×d} f(A,X)∈Rn×d 是GNN并且 Q Q Q 是改变节点顺序的置换矩阵。一个GNN是等变的，如果它满足：
对域图形级任务，假设 f ( A , X ) ∈ R d f(A,X)\in R^{d} f(A,X)∈Rd 。个GNN是不变的，如果它满足：
为了能够满足等变性或者不变性，GNN的组件必须对节点的顺序保持不变。Maron等人从理论上研究了图数据的置换不变和等变线性层的特征。
5.6.5 通用逼近性：
众所周知，具有一个隐藏层的多层感知器前馈神经网络可以近似任何Borel可测函数，然而关于GNN的通用逼近能力的研究很少。Hammer等证明级联相关可以近似具有结构化输出的函数。Scarselli等人证明RecGNN可以近似任何保持展开等价的函数，其精度可达任何程度。如果两个节点的展开树是相同的，那么这两个节点的展开树是等价的，其中一个节点的展开树是通过在一定深度上迭代扩展一个节点的邻域来构造的。Xu等证明了在消息传递框架下的图卷积神经网络函数不是定义在多集上的连续函数的通用逼近器。Maron等证明了不变图网络可以近似定义在图上的任意不变函数。
6. 应用：
由于图结构数据的普遍存在，GNN具有广泛的应用前景。本节分别总结基准图数据集、评估方法和开源实现，并详细介绍了GNN在各个领域的实际应用。
6.1 数据集：
这里主要将数据集分为四组，分别是引文网络、生化图数据、社交网络和其他。下表总结了所选择的基准数据集。
6.2 评估方法和开源实现：
6.2.1 节点分类：
在节点分类中，大多数方法在基准数据集（包括Cora、Citeseer、Pubmed、PPI和Reddit）上遵循train/valid/test的标准分割，并报告测试数据集的平均精度或F1得分。应该注意的是，这些结果不一定代表一个严格的比较。Shchur等人指出在GNN评估节点分类上的性能时存在两个缺陷。
- 首先，在所有实验中使用相同的train/valid/test分割会低估泛化误差。
- 其次，不同的方法采用不同的训练技巧，如超参数调优、参数初始化、学习率衰减和早期停止。
方法的实验结果的总结如下：
6.2.2 图分类：
在图分类中，研究人员通常采用十折交叉验证（cv）对模型进行评估。然而不同算法之间的实验设置是模糊的，没有统一的。一个经常遇到的问题是，每个折叠的外部测试集都被用于模型选择和风险评估。
在标准化和统一的评估框架中比较GNNs的一种方法是，使用外部的十折交叉验证来估计模型的泛化性能，使用内部的90%/10%的训练/验证分割来进行模型选择。另一种方法是双cv法，即使用外部的K-折交叉验证进行模型评估，使用内部的K-折交叉验证进行模型选择。
6.2.3 开源实现：
开源实现促进了深度学习研究中的基线实验工作。值得注意的是，Fey等人在PyTorch中发布了一个名为PyTorch geometry 4的库，它实现了许多gnn。最近发布的Deep Graph Library （DGL）在流行的深度学习平台（如PyTorch和MXNet）上提供了许多GNN的快速实现。
下表提供了本文中讨论的GNN模型的开源实现的超链接：
6.3 实际应用场景：
GNN有许多跨不同任务和领域的应用。尽管通用任务可以由每个类别的GNN直接进行处理，包括节点分类、图像分类、网络嵌入图形生成和时空图预测，其他一般的与图数据相关的任务（如节点集群，链接预测和图分区等），也可以通过GNN来实现。下面详细介绍了基于以下研究领域的一些应用。
6.3.1 计算机视觉：
GNN在计算机视觉中的应用包括场景图生成、点云分类和动作识别。
场景图生成：
使用GNN识别物体之间的语义关系有助于理解视觉场景背后的意义。场景图生成模型的目的是将图像解析为由对象及其语义关系组成的语义图。另一个应用是通过生成给定场景图的真实图像来逆过程。由于自然语言可以被解析为语义图，其中每个词代表一个对象，因此将文本描述的图像合成是一种很有前途的解决方案。
点云分类：
分类和分割点云主要指的是使激光雷达设备“看到”周围的环境。点云是激光雷达扫描记录的一组三维点。一些研究将点云转化为k-近邻图或超点图，并利用图卷积神经网络来研究拓扑结构。
视频动作识别：
识别视频中包含的人类动作有助于从机器角度更好地理解视频内容。一些解决方案检测视频剪辑中人体关节的位置。人的关节是由骨骼连接起来的，自然形成一个图形。已知人类关节位置的时间序列，那就可以利用STGNNs等模型来学习人类动作模式。
此外，GNN在计算机视觉中的应用方向还在不断增加。它包括人-物交互、小样本图像分类、语义分割、视觉推理、问题回答等。
6.3.2 自然语言处理：
GNNs在自然语言处理中的一个常见应用是文本分类，即利用文档或单词之间的相互关系来推断文档标签。
尽管自然语言数据显示的是 时序数据，但它们也可能包含一个内部图结构，比如一个语法依赖树。句法依赖树定义句子中词之间的句法关系。因此Marcheggiani等人提出了基于CNN/RNN句子编码器的Syntactic GCN。
Syntactic GCN根据句子的句法依赖树聚合隐藏的词表示。Bastings等将Syntactic GCN应用到神经机器翻译任务中。Marcheggiani等人进一步采用与Bastings等人相同的模型来处理句子的语义依赖图。
GNN也可以通过图到序列学习，来生成具有相同意义的句子，并给出一个抽象词的语义图（称为抽象意义表示）。Song等人提出了一种Graph-LSTM来编码图形级语义信息。Beck等将GGNN应用于图序列学习和神经机器翻译。相反的任务是序列到图学习。给定一个句子生成一个语义图或知识图在知识发现中非常有用。
6.3.3 智能交通：
在智能交通系统中，准确预测交通网络中的交通速度、交通量或道路密度是至关重要的。
有的研究者使用STGNNs解决流量预测问题。他们认为交通网络是一个时空图，其中节点是安装在道路上的传感器，通过对节点之间的距离来测量边缘，每个节点以一个窗口内的平均交通速度作为动态输入特征。
另一个工业级应用是出租车需求预测。根据历史出租车需求、位置信息、天气数据和事件特征，Yao等将LSTM、CNN和LINE训练的网络嵌入结合在一起，形成对每个位置的联合表示，从而预测某一时段内某一位置的出租车需求数量。
6.3.4 推荐系统：
基于图神经网络的推荐系统以项目和用户为节点。通过利用项目与项目、用户与用户、用户与项目以及内容信息之间的关系，基于图的推荐系统能够产生高质量的推荐。
推荐系统的关键是给用户打分。因此，可以将其转换为一个链接预测问题。为了预测用户和物品之间缺失的链接，Van等人和Ying等人提出了一种使用ConvGNNs作为编码器的GAE。Monti等人将RNNs与图形卷积相结合，以学习生成已知评级的底层过程。
6.3.5 化学领域：
在化学领域，研究人员应用GNNs来研究分子/化合物的图形结构。在分子/化合物图中，原子被认为是节点，化学键被认为是边，因此GNN可用于分子指纹、预测分子性质、推断蛋白界面、合成化合。即节点分类、图分类和图生成是针对分子/化合物图的三大主要任务。
6.3.6 其他应用：
GNNs的应用并不局限于上述领域和任务。将GNNs应用于程序验证、程序推理、社会影响预测、对抗攻击预防、电子健康记录建模、脑网络、事件检测、组合优化等问题已经进行了探索。
7. 研究方向：
虽然GNN已经证明了它们在学习图数据方面的能力，但由于图的复杂性，挑战仍然存在。本节提出了GNNs未来的四个方向。
7.1 模型深度：
深度学习的成功在于深度神经结构。然而，Li等人表明，随着图卷积层数量的增加，ConvGNN的性能急剧下降。由于图卷积将相邻节点的表示法推得更近，理论上，在无限个图卷积层的情况下，所有节点的表示法都将收敛于一个单点。这就提出了一个问题：对于学习图数据来说，加深模型层数是否仍然是一个好的策略。
7.2 可扩展性的权衡：
获得了GNN的可扩展性通常要以破坏图的完整性为代价。无论是使用抽样还是聚类，模型都会丢失部分图的信息。通过抽样，一个节点可能会错过它的有影响的邻居。通过聚类，一个图可能被剥夺了一个独特的结构模式。如何在算法的可扩展性和图的完整性之间进行权衡是未来的研究方向。
7.3 异质性：
目前大多数GNN都采用齐次图。当前的GNN很难直接应用到异构图中，因为异构图中可能包含不同类型的节点和边，也可能包含不同形式的节点和边输入，如图像和文本。因此，需要开发新的方法来处理异构图。
7.4 动态性：
图本质上是动态的，节点或边可能会出现或消失，节点/边的输入可能会随着时间而改变。为了适应图的动态性，需要对图进行新的卷积。虽然STGNN可以部分解决图的动态性问题，但很少有人考虑如何在动态空间关系的情况下进行图的卷积。
联系方式和作者简介：
大二在读炼丹师，感兴趣方向为计算机视觉、图神经网络，欢迎各位炼丹师一起交流学习~
博客主页：https://blog.csdn.net/weixin_44936889
Github主页：https://github.com/Sharpiless
AI Studio主页：https://aistudio.baidu.com/aistudio/personalcenter/thirdview/67156
码字不容易，求三连~
