文章目录
I. 引言II. 背景和定义A. 背景B. 定义 III. 分类和框架A. GNNs的分类B. 框架 IV. 循环图神经网络（Recurrent Graph Neural Networks，RecGNNs）V. 卷积图神经网络（Convolutional Graph Neural Networks，ConvGNNs）A. 基于谱的卷积神经网络（Spectral-based ConvGNNs）B. 基于空间的卷积图神经网络（Spatial-based ConvGNNs）C. 图池化模块D. 理论层面讨论 VI. 图自编码器（Graph Auto Encoders，GAEs）A. 网络嵌入（Network Embedding）B. 图生成 VII. 时空图神经网络（Spatial-Temporal Graph Neural Networks，STGNNs）VIII. 应用A. 数据集B. 评估及开源实现C. 实际应用 IX. 未来方向【论文链接】：A Comprehensive Survey on Graph Neural Networks
最近一些年，深度学习彻底革新了许多机器学习任务。从图像分类、视频处理到语音识别、自然语音理解。这些任务中的数据通常可在欧式空间中表示，然而，越来越多应用中的数据是从非欧式空间中生成，并以物体之间具有复杂关系和依赖的图表示。图数据的复杂性给现有机器学习算法带来了重大挑战。
最近，涌现很多扩展机器学习方法处理图数据的研究。在这份调查中，我们提供了图神经网络 (Graph Neural Networks, GNNs) 在数据挖掘和机器学习领域的综述。我们提出一种分类，将GNNs SOTA分4类：循环图神经网络、卷积图神经网络、图自动编码器和时域图神经网络。
我们进一步讨论了图神经网络在不同领域内的应用，并总结开源代码、基准数据集和GNNs模型评估。最后，我们提议了这一快速发展领域的可能研究方向。
索引：深度学习，图神经网络，图卷积神经网络，图表示学习，图自动编码器，网络嵌入
I. 引言
近些年，模式识别和数据挖掘在神经网络的成功下得以兴起。许多曾经严重依赖于手工提取特征的机器学习任务，诸如目标检测1,2、机器翻译3,4和语音识别5，近些年被各种各样的端到端深度学习范式所颠覆，如卷积神经网络 (Convolutional Neural Networks, CNNs)6 、循环神经网络 (Recurrent Neural Networks, RNNs)7 和自动编码器 (Auto Encoders, AE)8 等。
深度学习在许多领域的成功部分归因于：
快速发展的计算资源（如GPU）可利用的大数据深度学习从欧式空间数据（图像、文本和视频）中抽取潜在特征的有效性
以图像数据为例，我们可将其表示为欧氏空间中的规则网络。CNN能够利用图像数据的平移不变性、局部连接性和合成性9，因此，CNNs能够抽取整个数据集共享的局部特征信息，用于分析各种图片。
尽管深度学习能够有效抓取欧式空间中数据的隐藏模式，但仍有大量应用的数据以图形化表示，例如，在电子商务领域，基于图的学习系统能够挖掘用户和商品间的相互作用，给出高精准推荐；在化学领域，分子能以图形式建模，需鉴定它们的生物活性用于药品研发；在论文引用网络中，论文之间以引用关系相连，需将其分类至不同组。
图数据的复杂性向现有机器学习算法提出重大挑战。因为图可能的不规则性，一张图可能包含不定数目的无序节点，图节点可能有不同数目的邻接节点，使得一些在图像领域易于计算的重要操作（如卷积）难以应用于图领域。而且，机器学习具有实例间相互独立的核心假设，这一假设不再适用于图数据，因为每个实例（节点）与其他实例具有多种关联类型，如引用、朋友关系、相互作用等。
最近，人们对扩展深度学习方法处理图数据的兴趣日益提升。为应对图数据的复杂性，通过借鉴深度学习CNNs、RNNs和AE的设计思想，重要运算的泛化和定义在过去几年里得到快速发展。例如，可从二维卷积中推导出图卷积，如图1所示，图像可以看作为特殊情况的图，各像素与邻接像素相连。与二维卷积相似，通过加权平均邻接节点的信息可在图像上执行图卷积运算。
目前，有关GNNs主题的综述数量有限。[9]使用术语“几何 (geometric) 深度学习”，给出了深度学习方法在非欧式空间的综述，包括图和流形 (manifold) ，尽管这是有关GNNs的第一篇综述，但主要模型是卷积GNNs；[10]综述了有限数量的GNNs，主要关注于网络嵌入问题；[11]指出，图网络作为构建块，旨在从关系型数据中学习，并在统一框架下讨论一部分GNNs；[12]对应用不同注意力机制的GNNs作为部分调查。
总之，目前已有调查仅包含部分GNNs的研究工作，遗漏了GNNs的最新进展。我们的调查为希望踏足这一快速发展的领域的研究者，以及期望比较各种GNNs模型的专家，提供一份关于GNNs的全面综述。为更广覆盖现有方法，本调查认为GNNs是处理图数据的所有深度学习方法。
我们的贡献本论文的重要贡献总结如下：
新的分类：我们提出一种GNNs新的分类，GNNs可分为循环GNNs、卷积GNNs、图自动编码器以及时域GNNs，共四类。全面回顾：我们提供了现代深度学习技术处理图数据最全面的综述，对于每一种类型的GNN，我们对代表型模型做出详细描述，做必要比较，以及总结相关算法。丰富资源：我们收集了图神经网络大量的资源，包括SOTA模型、基线数据集、开源代码以及实际应用。这份调查可以作为理解、使用和开发不同深度学习方法用于各种真实应用的手册。未来方向：我们在理论层面讨论了GNNs，分析现有方法的局限性，提出四种未来可能的研究方向，即模型深度、权衡伸缩性、异质性以及动态性。
II. 背景和定义
本节中，我们概括GNNs的背景、列举常见符号以及定义图相关的概念。
A. 背景
GNNs简史受早期GNNs研究的启发，Sperduti (1997)13 首次在有向无环图中使用神经网络；Goriet ()14 首次概括图神经网络的概念；后来，Scarselli ()15 以及 Gallicchio ()16 作出详细说明。这些早期的研究属于循环图神经网络 (RecGNNs) 范畴。这些方法迭代地传播邻居信息直至到达稳定点，来学习目标节点表示，这一过程计算复杂，直至目前仍有工作在不断努力克服这些挑战17,18。
受CNNs在计算机视觉上取得成功的激励，近来出现很多方法重新定义图数据中的卷积概念，这些方法属于卷积神经网络 (ConvGNNs) 一类。ConvGNNs分为两个流派：基于谱的方法和基于空间的方法。
Bruna ()19 基于谱图论研究出一种图卷积，给出了第一篇基于谱的ConvGNNs的优秀研究，从这时起，开始不断涌现对基于谱的ConvGNNs进行大量改进、扩展和近似的工作20,23。
基于空间的ConvGNNs的研究远早于基于谱的ConvGNNs。，Micheli24 在从RecGNNs继承消息传递思想时，在模型结构上组合非递归层，首先解决了图的互依赖性，然而，人们忽略了他工作的重要性，直至最近许多基于谱的ConvGNNs25,26,27出现。表II中第一列包含RecGNNs和ConvGNNs代表性的时间线。
除RecGNNs和ConvGNNs之外，在过去几年里研究了许多可选的GNNs，包括GAEs和时空图卷积网络（STGNNs）。这些学习框架可以建立在RecGNNs，ConvGNNs，或者其它用于图建模的神经网络架构之上。第III部分给出这些方法的详细描述。
图神经网络 vs. 网络嵌入GNNs上的研究与图嵌入或网络嵌入密切相关，这同时也是吸引数据挖掘和机器学习群体更多关注的另一个热门话题10,28,29,30,31,32。网络嵌入旨在以低维向量表示网络节点，并保留网络拓扑结构和节点内容信息，使一些简单、现成的机器学习算法（如SVM分类）能被轻易应用在任意下游图分析任务（如分类、聚类和推荐）。
GNNs属于以端到端方式解决图相关任务的深度学习模型，许多GNNs显式地提取高层级表示。与网络嵌入的主要不同在于，GNNs是一组设计用于处理不同任务的神经网络模型，而网络嵌入则涵盖了处理相同任务的各种方法。因此，GNNs通过图自动编码框架可解决网络嵌入问题。另一方面，网络嵌入包含非深度学习方法，如矩阵因式分解33,34和随机游走35。
图神经网络 vs. 图核方法图核历来是解决图分类的主要技术36,37,38。这些方法使用核函数度量图对间的相似性，因此可在图上以监督学习的方式使用一些基于核的算法，如SVM。图核与GNNs相似，可利用映射函数将图或节点嵌入到向量空间，主要不同在于，映射函数是不可学习的确定的函数。由于成对的相似度计算，图核方法受计算瓶颈的严重影响，而GNNs基于抽取的图表示直接执行图分类，因此比图核方法更有效。读者可通过[39]进一步回顾图核方法。
B. 定义
论文全篇以粗体大写字母表示矩阵、粗体小写字母表示向量。除非特殊说明，论文中使用的符号说明如表1所示。现在我们定义理解本论文所需的最小定义集。
图：图可表示为 G = ( V , E ) G=(V, E) G=(V,E)，详细信息见表1。
有向图：所有边从一个节点指向另一个节点的图。无向图是有向图的一种特例，其任意连接的节点相互指向。无向图等价于邻接矩阵对称。
时空图：具有节点属性随时间动态变化属性的图。时空图定义为 G ( t ) = ( V , E , X ( t ) ) G^{(t)}=(\bm V,\bm E,\bm X^{(t)}) G(t)=(V,E,X(t))，其中 X ( t ) ∈ R n × d \bm X^{(t)}\in\R^{n\times d} X(t)∈Rn×d。
III. 分类和框架
本节中，我们提出了我们对GNNs的分类，如表II所示。
我们将GNNs分为循环图神经网络 (Recurrent Graph Neural Networks, RecGNNs)、卷积图神经网络 (Convolutional Graph Neural Networks, ConvGNNs)、图自动编码器 (Graph Autoencoders, GAEs)以及时空图神经网络 (Spatial-Temporal Graph Neural Networks, STGNNs)。
图2给出了不同模型架构的例子。接下来，我们对每个类别做简短介绍。
A. GNNs的分类
循环图神经网络 (RecGNNs)大多数为GNNs的先驱作品。RecGNNs旨在从循环网络架构中学习节点表示。它们假设图中节点不停的与邻接节点交换信息/消息，直至到达稳定平衡点。RecGNNs概念很重要，启发了后面有关GCN的研究。特别是，基于空间的GCN继承了这个消息传递思想。
卷积图神经网络 (ConvGNNs)将网格数据中的卷积运算泛化至图数据。主要思想是通过聚合节点 v v v自身特征 x v \bm x_v xv，及其邻接节点的特征 x u \bm x_u xu，生成节点 v v v特征表示。不同于RecGNNs，ConvGNNs使用堆叠的多层图卷积层抽取节点高级表示。ConvGNNs在构建许多其它复杂GNN时，扮演核心角色。图2a展示ConvGNNs节点分类，图2b展示了用于图分类的ConvGNNs。
图自动编码器 (GAEs)作为无监督学习框架将节点/图编码在潜在向量空间，并从编码信息中重构图数据。GAEs常用于学习网络嵌入和图生成分布。对于网络嵌入，GAEs通过重构图结构信息如图邻接矩阵，学习潜在节点表示。对于图生成，一些方法一步一步地生成图的节点和边，另一些方法直接生成完整图。图2c展示了用于网络嵌入的GAE。
时空图神经网络 (STGNNs)旨在从时空图中学习隐藏模式，在许多应用中越来越重要，如交通速度预测72、司机操作感知73和人类动作识别75。STGNNs的关键思想是同时考虑时间依赖性和空间依赖性。目前许多方法在使用RNNs或CNNs建模时间依赖性的同时，在模型中集成图卷积集来模型捕获空间依赖性。图2d图解了用STGNN进行时空图预测。
B. 框架
以图结构和节点内容信息作为输入，GNNs的输出可以根据以下几种机制应对不同的图分析任务：
节点级别输出与节点回归和节点分类任务有关。RecGNNs和ConvGNNs利用信息传播/图卷积，能够提取节点的高层级表示。利用多层感知机或softmax层作为输出层，GNNs能够以端到端的形式执行node-level任务。边级别输出与边分类和连接预测有关。利用GNNs中两节点的隐状态表示作为输入，利用相似性函数或神经网络，预测边的标签/连接强度。图级别输出与图分类任务有关。GNNs通常结合pooling和readout操作，获取图级别的压缩表示。Pooling和readouts的详细信息会在V-C章节详细介绍。
训练框架.许多GNNs（例如ConvGNNs）能够在端到端学习框架中以（半）监督或完全无监督的方式训练，这取决于学习任务和手边可用的标注信息。
节点级别分类的半监督学习给定一个部分节点标注的网络，ConvGNNs能够学习鲁棒的模型，有效地识别未标注节点的标签类别。鉴于此，使用堆叠的两层图卷积层和多分类softmax层构建端到端的框架。
图级别分类的监督学习图级别分类的目的是预测完整图的标签52,54,78,79。通过组合图卷积层和图池化层或readout层实现该任务的端到端学习。图卷积层负责提取节点高级表示，图池化层扮演每次将图粗化为子结构的负采样角色。Readout层将每张图的节点表示降为图表示。通过在图表示上应用多层感知机和softmax层，可创建图分类的端到端框架，示例见图2b。
图嵌入的无监督学习当图中无可用类别标签，我们可以在端到端框架中以完全无监督的方式学习图嵌入。这些算法以两种方式挖掘边信息。一种简单的方式是，采用自编码器框架，编码器利用图卷积层将图嵌入为潜在语义表示，在此基础上，使用解码器重构图结构61,62 ；另一种主流的方式是，当图中存在连接的节点对作为正样本对，利用负采样方法采样节点对作为负样本对，使用逻辑回归网络层判断样本对的正负性。
在表III中，我们总结了RecGNNs和ConvGNNs代表性模型的主要特征，比较了各种模型的输入源、池化层、readout层以及时间复杂度。更进一步，我们仅比较每个模型消息传递/图卷积操作的时间复杂度。
[19]和[20]中提出的方法要求特征值分解，时间复杂度为 O ( n 3 ) O(n^3) O(n3)；[46]需要计算所有节点对的最短路径，时间复杂度同样是 O ( n 3 ) O(n^3) O(n3)；其它方法的时间复杂度相当，当图的邻接矩阵是稀疏矩阵时，时间复杂度为 O ( m ) O(m) O(m)，否则为 O ( n 2 ) O(n^2) O(n2)。这是因为这些方法在计算每个节点 v i v_i vi的表示时，牵涉每个节点的 d i d_i di个邻接节点，所有节点 d i d_i di的和等价于边总数。
表III缺失了一些方法的时间复杂度，因为这些方法在论文中缺乏时间复杂度分析，或仅报告他们模型或算法的整体复杂度。
IV. 循环图神经网络（Recurrent Graph Neural Networks，RecGNNs）
RecGNNs作为多数GNNs的先驱。对于图中节点，它们使用相同参数提取节点高级特征表示。受计算力限制，早期研究主要关注于有向无环图13,80。
Scarselli 通过扩展先前的循环模型为GNN*，来解决一般类型的图，如无环、有环、有向和无向图。基于信息扩散机制，GNN*用与邻接点循环交换信息的方式来更新节点状态，直至到达稳定平衡点。节点隐状态的循环更新公式：
h v ( t ) = ∑ u ∈ N ( v ) f ( x v , x v , u e , x u , h u ( t − 1 ) ) , (1) h_v^{(t)}=\sum_{u\in N(v)}f(\bm x_v, \bm x_{v,u}^e, \bm x_u, \bm h_u^{(t-1)}), \tag 1 hv(t)=u∈N(v)∑f(xv,xv,ue,xu,hu(t−1)),(1)
式中 f ( ⋅ ) f(\cdot) f(⋅)是参数化的函数， h v ( 0 ) \bm h_v^{(0)} hv(0)由随机初始化。GNN*中求和操作适用于所有节点，即使是在邻接节点数量不同、排序未知的情况。为保证收敛性，循环函数 f ( ⋅ ) f(\cdot) f(⋅)必须是一个压缩映射，使得两点在潜在空间中的投影点之间的距离缩短。
当 f ( ⋅ ) f(\cdot) f(⋅)是神经网络时，必须向雅可比矩阵的参数中加入惩罚项。当满足收敛准则时，节点在最后一步的隐状态前向传至readout层。GNN*通过交替节点的状态传播和参数梯度计算，来最小化训练目标函数。GNN*利用这种策略能够处理有环图。
在后续工作中，图回声状态网络 (Graph Echo State Network, GraphESN)16 通过扩展回声状态网络改善GNN*的训练效率。GraphESN由编码器和输出层组成。编码器随机初始化且不需要训练，它等价于一个压缩的状态转移函数，用于循环更新节点状态，直至全局图状态收敛。之后，以固定的节点状态作为输入，来训练输出层。
门控图神经网络 (Gated Graph Neural Network, GGNN)17 利用GRU作为循环函数，使用固定的循环步数来降低循环次数。它的优势在于，不再约束参数来确保收敛。节点状态通过节点先前隐状态和邻接节点隐状态更新，定义如下：
h v ( t ) = G R U ( h v ( t − 1 ) , ∑ u ∈ N ( v ) W h u ( t − 1 ) ) , (2) \bm h_v^{(t)}=GRU(\bm h_v^{(t-1)},\sum _{u\in N(v)}\bm W\bm h_u^{(t-1)}),\tag 2 hv(t)=GRU(hv(t−1),u∈N(v)∑Whu(t−1)),(2)
其中， h v ( 0 ) = x v h_v^{(0)}=\bm x_v hv(0)=xv。不同于GNN*和GraphESN，GGNN使用BPTT后向传播算法学习模型参数。这对大型图来说可能会有问题，因为GGNN需要将循环函数在所有节点上乘多次，需在内存中保留所有节点的隐藏状态。
随机稳态嵌入 (Stochastic Steady-state Embedding, SSE)18 提出一种对大型图更具伸缩性的学习算法。SSE以随机和异步的方式循环地更新节点隐状态，它轮流采样batch中的节点，进行状态更新和梯度计算。为保证稳定性，SSE中的循环函数定义为历史状态和最新状态的加权平均，形式为
h v ( t ) = ( 1 − α ) h v ( t − 1 ) + α W 1 σ ( W 2 [ x v , ∑ u ∈ N ( v ) [ h u ( t − 1 ) , x u ] ] ) , (3) \bm h_v^{(t)}=(1-\alpha)\bm h_v^{(t-1)}+\alpha \bm W_1\sigma(\bm W_2[\bm x_v,\sum_{u\in N(v)}[\bm h_u^{(t-1)},\bm x_u]]),\tag 3 hv(t)=(1−α)hv(t−1)+αW1σ(W2[xv,u∈N(v)∑[hu(t−1),xu]]),(3)
其中， α \alpha α为超参数， h v ( 0 ) \bm h_v^{(0)} hv(0)随机初始化。SSE并未给出通过反复应用公式3节点状态逐渐收敛至固定点的理论证明。
V. 卷积图神经网络（Convolutional Graph Neural Networks，ConvGNNs）
ConvGNNs与RecGNNs关系密切。ConvGNNs的架构是每层使用不同权重、固定数量的层，解决循环相互依赖，并不使用收缩约束进行节点状态迭代。主要区别如图3所示。
由于将图卷积与其他神经网络组合的高效性和简便性，近些年ConvGNNs快速流行了起来。ConvGNNs分为两类：基于谱和基于空间。基于谱的方法从图信号处理的角度引入滤波器，定义图卷积，图卷积操作可解释为从图信号中移除噪声82。
基于空间的方法基于RecGNNs中信息传播的思想定义图卷积，自从GCN22跨越了基于谱的方法和基于空间的方法之间的沟壑，近些年，基于空间的方法以其具有吸引力的效率性、灵活性和通用性得到了快速的发展。
A. 基于谱的卷积神经网络（Spectral-based ConvGNNs）
背景基于谱的方法在图信号处理领域具有坚实的数学基础82,83,84。他们假设图是无向的。标准化图的拉普拉斯矩阵是无向图的数学表示，定义为 L = I n − D − 1 / 2 A D − 1 / 2 \bm L=\bm I_n - \bm D^{-1/2}\bm A\bm D^{-1/2} L=In−D−1/2AD−1/2，其中
D \bm D D是节点度的对角矩阵 D i i = ∑ j ( A i , j ) \bm D_{ii}=\sum_j(\bm A_{i,j}) Dii=∑j(Ai,j)
标准化的拉普拉斯居矩阵具有实对称半正定的性质，基于这个性质可分解（正交分解）为 L = U Λ U ⊤ \bm L=\bm U\bm \Lambda\bm U^\top L=UΛU⊤，其中
U = [ u 0 , u 1 , ⋯ , u n − 1 ] ∈ R n × n \bm U=[\bm u_0, \bm u_1,\cdots, \bm u_{n-1}] \in \R^{n\times n} U=[u0,u1,⋯,un−1]∈Rn×n是根据特征值排序的特征向量矩阵 Λ \bm\Lambda Λ是特征值（谱）对角矩阵， Λ i i = λ i \bm\Lambda_{ii}=\lambda_i Λii=λi
标准化的拉普拉斯矩阵的特征向量构成一个正交空间，具有数学性质 U ⊤ U = I \bm U^\top\bm U=\bm I U⊤U=I。在图信号处理中，图信号 x ∈ R n \bm x\in\R^n x∈Rn是图中所有节点的特征向量， x i x_i xi是第 i i i个节点的值（全图节点参与计算）。
信号 x \bm x x的图傅里叶变换定义为 F ( x ) = U ⊤ x \mathscr{F}(\bm x)=\bm U^\top \bm x F(x)=U⊤x，图傅里叶反变换定义为 F − 1 ( x ^ ) = U x ^ \mathscr{F}^{-1}( \hat{\bm x})=\bm U\hat{\bm x} F−1(x^)=Ux^，其中 x ^ \hat{\bm x} x^是傅里叶变换后的信号。图傅里叶变换将输入图信号投影到正交空间，以标准化图的拉普拉斯的特征向量作为基。转换后的信号 x ^ \hat{\bm x} x^中的值是图信号在新空间（傅里叶空间）中的坐标，使得输入信号可解释为 x = ∑ i x ^ i u i \bm x=\sum_i\hat x_i\bm u_i x=∑ix^iui，恰好是图傅里叶的反变换。
现在，输入信号 x \bm x x和滤波器 g ∈ R n \bm g\in\R^n g∈Rn的图卷积定义为
x ∗ G g = F − 1 ( F ( x ) ⊙ F ( g ) ) = U ( U ⊤ x ⊙ U ⊤ g ) , (4) \bm x*_G \bm g=\mathscr F^{-1}(\mathscr F(\bm x)\odot \mathscr F(\bm g))=\bm U(\bm U^\top\bm x\odot\bm U^\top\bm g),\tag 4 x∗Gg=F−1(F(x)⊙F(g))=U(U⊤x⊙U⊤g),(4)
其中， ⊙ \odot ⊙表示对应元素向乘。如果我们将滤波器表示为 g θ = d i a g ( U ⊤ g ) g_\theta=diag(\bm U^\top \bm g) gθ=diag(U⊤g)，则谱图卷积可简化为
x ∗ G g θ = U g θ U ⊤ x , (5) \bm x*_G \bm g_\theta=\bm U\bm g_\theta \bm U^\top\bm x,\tag 5 x∗Ggθ=UgθU⊤x,(5)
基于谱的ConvGNNs都遵循这一定义，关键不同在于对滤波器 g θ \bm g_\theta gθ的选择。
谱卷积神经网络 (Spectral Convolutional Neural Network, Spectral CNN)19 假设滤波器 g θ = Θ i , j ( k ) g_\theta=\Theta_{i,j}^{(k)} gθ=Θi,j(k)是一组可学习参数，并考虑具有多通道的图信号。Spectral CNN的图卷积层定义为
H : , j ( k ) = σ ( ∑ i = 1 f k − 1 U Θ i , j ( k ) U ⊤ H : , i ( k − 1 ) ) , ( j = 1 , 2 , ⋯ , f k ) , (6) \bm H_{:,j}^{(k)}=\sigma\left(\sum_{i=1}^{f_{k-1}}\bm U\Theta_{i,j}^{(k)}\bm U^\top\bm H_{:,i}^{(k-1)}\right),\quad (j=1,2,\cdots,f_k),\tag 6 H:,j(k)=σ(i=1∑fk−1UΘi,j(k)U⊤H:,i(k−1)),(j=1,2,⋯,fk),(6)
其中， k k k是层的索引； H ( k − 1 ) ∈ R n × f k − 1 \bm H^{(k-1)}\in\R^{n\times f_{k-1}} H(k−1)∈Rn×fk−1是图信号输入； H ( 0 ) = X \bm H^{(0)}=\bm X H(0)=X； f k − 1 f_{k-1} fk−1是输入通道数量； f k f_k fk是输出通道数量； Θ i , j ( k ) \Theta_{i,j}^{(k)} Θi,j(k)是参数可学习的对角矩阵。基于拉普拉斯矩阵的特征分解，Spectral CNN具有三个局限：
第一，任意对图结果的扰动都会造成特征基变化；第二，学习得到的滤波器依赖于邻域，这意味着它们不能应用于具有不同结构的图；第三，特征分解需要 O ( n 3 ) O(n^3) O(n3)复杂度，在后续工作中，ChebNet21和GCN22通过数种近似和简化将复杂度降至 O ( m ) O(m) O(m)；
切比雪夫谱CNN (Chebyshev Spectral CNN, ChebNet)21 利用特征值对角矩阵的切比雪夫（Chebyshev）多项式，近似滤波器 g θ \bm g_\theta gθ，例如：
g θ = ∑ i = 0 K θ i T i ( Λ ~ ) \bm g_\theta=\sum_{i=0}^K\theta_iT_i(\tilde{\bm\Lambda}) gθ=i=0∑KθiTi(Λ~)
其中 Λ ~ = 2 Λ / λ max − I n \tilde{\bm\Lambda}=2\bm\Lambda/\lambda_{\max}-\bm I_n Λ~=2Λ/λmax−In， Λ ~ \tilde{\bm\Lambda} Λ~中的值位于 [ − 1 , 1 ] [-1, 1] [−1,1]。切比雪夫多项式能够以循环形式定义，其中
T i ( x ) = 2 x T i − 1 ( x ) − T i − 2 ( x ) , T 0 ( x ) = 1 , T 1 ( x ) = x T_i(\bm x)=2\bm xT_{i-1}(\bm x)-T_{i-2}(\bm x),\quad T_0(\bm x)=1, T_1(\bm x)=\bm x Ti(x)=2xTi−1(x)−Ti−2(x),T0(x)=1,T1(x)=x
最后，图信号 x \bm x x和滤波器 g θ \bm g_\theta gθ定义为
x ∗ G g θ = U ( ∑ i = 0 K θ i T i ( Λ ~ ) U ⊤ x ) , (7) \bm x*_G\bm g_\theta=\bm U\left(\sum_{i=0}^K\theta_iT_i(\tilde{\bm\Lambda})\bm U^\top\bm x\right),\tag 7 x∗Ggθ=U(i=0∑KθiTi(Λ~)U⊤x),(7)
其中， L ~ = 2 L λ max − I n \tilde{\bm L}=2\bm L \lambda_{\max} - \bm I_n L~=2Lλmax−In。当 T i ( L ~ ) = U T i ( Λ ~ ) U ⊤ T_i(\tilde{\bm L})=\bm UT_i(\tilde{\bm\Lambda})\bm U^\top Ti(L~)=UTi(Λ~)U⊤，在 i i i处，利用归纳法可证明ChebNet的形式为
x ∗ G g θ = ∑ i = 0 K θ i T i ( L ~ ) x , (8) \bm x *_G\bm g_\theta=\sum_{i=0}^K\theta_iT_i(\tilde{\bm L})\bm x,\tag 8 x∗Ggθ=i=0∑KθiTi(L~)x,(8)
ChebNet通过在局部空间中定义滤波器改进Spectral CNN，意味着滤波器可抽取与图大小无关的局部特征。ChebNet的频谱被线性映射到 [ − 1 , 1 ] [-1, 1] [−1,1]。进一步地，CayleyNet23应用参数化有理数函数的Cayley多项式，来捕获窄频带。CayleyNet的谱图卷积定义为
x ∗ G g θ = c 0 x + 2 R e { ∑ j = 1 r c j ( h L − i I ) j ( h L + i I ) − j x } , (9) \bm x*_G\bm g_\theta=c_0\bm x+2Re\left\{\sum_{j=1}^rc_j(h\bm L-i\bm I)^j(h\bm L+i\bm I)^{-j}\bm x\right\},\tag 9 x∗Ggθ=c0x+2Re{j=1∑rcj(hL−iI)j(hL+iI)−jx},(9)
其中， R e ( ⋅ ) Re(\cdot) Re(⋅)返回复数的实数部分； c 0 c_0 c0是实系数； c j c_j cj是复系数； i i i是虚数； h h h是控制Cayley滤波器谱的参数。保持空间局部性的同时，ChebNet可认为是CayleyNet的一种特殊情况。
图卷积网络 (Graph Convolutional Network, GCN)22 介绍了ChebNet的一阶近似，假设 K = 1 K=1 K=1， λ max = 2 \lambda_{\max}=2 λmax=2，可将公式8简化为
x ∗ G g θ = θ 0 x − θ 1 D − 1 / 2 A D − 1 / 2 x , (10) \bm x*_G\bm g_\theta=\theta_0\bm x-\theta_1\bm D^{-1/2}\bm A\bm D^{-1/2}\bm x, \tag {10} x∗Ggθ=θ0x−θ1D−1/2AD−1/2x,(10)
为约束参数数量避免过拟合，GCN进一步假设 θ = θ 0 = − θ 1 \theta=\theta_0=-\theta_1 θ=θ0=−θ1，从而引出图卷积的如下定义：
x ∗ G g θ = θ ( I n + D − 1 / 2 A D − 1 / 2 ) x (11) \bm x *_G\bm g_\theta=\theta(\bm I_n+\bm D^{-1/2}\bm A\bm D^{-1/2})\bm x \tag{11} x∗Ggθ=θ(In+D−1/2AD−1/2)x(11)
为实现多通道输入输出，GCN修改公式11为合成层，定义为
H = X ∗ G g Θ = f ( A ˉ X Θ ) , (12) \bm H=\bm X*_G\bm g_\Theta=f(\bar{\bm A}\bm X\bm\Theta), \tag{12} H=X∗GgΘ=f(AˉXΘ),(12)
其中， A ˉ = I n + D − 1 / 2 A D − 1 / 2 \bar{\bm A}=\bm I_n+\bm D^{-1/2}\bm A\bm D^{-1/2} Aˉ=In+D−1/2AD−1/2， f ( ⋅ ) f(\cdot) f(⋅)是激活函数。根据经验，在GCN中使用 A ˉ \bar{\bm A} Aˉ会造成数值不稳定，为解决这个问题，GCN应用标准化的技巧，使用新的 A ˉ \bar{\bm A} Aˉ：
A ˉ = D ~ − 1 / 2 A ~ D ~ − 1 / 2 , A ~ = A + I n , D ~ i i = ∑ j A ~ i j \bar{\bm A}=\tilde{\bm D}^{-1/2}\tilde{\bm A}\tilde{\bm D}^{-1/2}, \quad \tilde{\bm A}=\bm A+\bm I_n,\ \tilde{\bm D}_{ii}=\sum_j\tilde{\bm A}_{ij} Aˉ=D~−1/2A~D~−1/2,A~=A+In,D~ii=j∑A~ij
作为一种基于谱的方法，GCN依然能够解释为基于空间的方法。从基于空间的角度来看，GCN可认为是从邻接节点中聚集信息。从这个角度，公式12可表示为
h v = f ( Θ ⊤ ( ∑ u ∈ { N ( v ) ∪ v } A ˉ v , u x u ) ) , ∀ v ∈ V . (13) \bm h_v=f(\Theta^\top(\sum_{u\in\{N(v)\cup v\}}\bar A_{v,u}\bm x_u)),\quad\forall v\in V. \tag{13} hv=f(Θ⊤(u∈{N(v)∪v}∑Aˉv,uxu)),∀v∈V.(13)
最近一些工作利用可选的对称矩阵对GCN做了逐步改进22。
自适应图卷积网络 (Adaptive Graph Convolutional Network, AGCN)40 学习图邻接矩阵中未指明的隐藏结构关系，它以两个节点的特征作为输入，通过一个可学习的距离函数构建一种所谓的残连接图邻接矩阵。对偶图卷积网络 (Dual Graph Convolutional Network, DGCN)41 引入一种具有两层并行图卷积层的对偶图卷积架构，两层图卷积共享参数，他们使用标准化的邻接矩阵 A ˉ \bar{\bm A} Aˉ以及PPMI矩阵（在采样图中随机游走捕获节点共现信息）。PPMI矩阵定义为
PPMI v 1 , v 2 = max ( log ( count ( v 1 , v 2 ) ⋅ ∣ D ∣ count ( v 1 ) count ( v 2 ) ) , 0 ) , (14) \text{PPMI}_{v_1,v_2}=\max(\log(\frac{\text{count}(v_1,v_2)\cdot |D|}{\text{count}(v_1)\text{count}(v_2)}),0), \tag{14} PPMIv1,v2=max(log(count(v1)count(v2)count(v1,v2)⋅∣D∣),0),(14)
其中， v 1 , v 2 ∈ V v_1,v_2\in V v1,v2∈V， ∣ D ∣ = ∑ v 1 , v 2 count ( v 1 , v 2 ) |D|=\sum_{v_1,v_2}\text{count}(v_1,v_2) ∣D∣=∑v1,v2count(v1,v2)， count ( ⋅ ) \text{count}(\cdot) count(⋅)返回节点 v v v和/或节点 u u u共现/出现在抽样随机游走中的频数。通过集成对偶卷积层的输出，DGCN在不使用堆叠的多层卷积层的情况下，分别编码了局部和全局结构信息。
B. 基于空间的卷积图神经网络（Spatial-based ConvGNNs）
与图像上传统CNN的卷积操作类似，基于空间的方法利用节点的空间关系定义图卷积。如果将图像的每一个像素看作一个节点，可认为图像是图的一种特殊形式。每个像素点直接与邻接像素相连，如图1a所示。在每个通道上，使用一个3x3的滤波器，将中心节点及其邻接节点的像素值加权平均。
类似地，基于空间的图卷积，通过将中心节点和邻接节点的表示执行卷积运算，更新中心节点表示，如图1b所示。从另一个角度看，基于空间的ConvGNNs借鉴了RecGNN中信息传播/传递的思想，时间图卷积操作本质上是沿着边传播节点信息。
用于图的神经网络 (Neural Network for Graphs, NN4G)24 与GNN*同时提出，是首个基于空间的ConvGNNs。不同于RecGNNs，NN4G使用每层参数独立的组合框架学习图相互依赖。可通过扩展架构的方式扩展邻接节点。NN4G以直接对邻接节点信息求和的方式计算卷积，它也应用于用于记忆各层信息的残连接和跳连接。最后，NN4G下层节点的状态更新公式为
h v ( k ) = f ( W ( k ) ⊤ x v + ∑ i = 1 k − 1 ∑ u ∈ N ( v ) Θ ( k ) ⊤ h u ( k − 1 ) ) , (15) \bm h_v^{(k)}=f(\bm W^{(k)\top}\bm x_v+\sum_{i=1}^{k-1}\sum_{u\in N(v)}\Theta^{(k)\top}\bm h_u^{(k-1)}), \tag{15} hv(k)=f(W(k)⊤xv+i=1∑k−1u∈N(v)∑Θ(k)⊤hu(k−1)),(15)
其中， f ( ⋅ ) f(\cdot) f(⋅)是激活函数， h v ( 0 ) = 0 \bm h_v^{(0)}=\bm 0 hv(0)=0。等式15也可以记作矩阵形式：
H ( k ) = f ( X W ( k ) + ∑ i = 1 k − 1 A H ( k − 1 ) Θ ( k ) ) , (16) \bm H^{(k)}=f(\bm X\bm W^{(k)}+\sum_{i=1}^{k-1}\bm A\bm H^{(k-1)}\bm\Theta^{(k)}), \tag{16} H(k)=f(XW(k)+i=1∑k−1AH(k−1)Θ(k)),(16)
上述公式类似于GCN22，不同点在于，NN4G使用未标准化的邻接矩阵，可能潜在地造成隐藏节点状态有极端值。
受NN4G启发，上下文图马尔可夫模型 (Contextual Graph Markov Model, CGMM)47 提出一种概率模型，仅保留局部空间，CGMM具有概率解释性的优点。扩散卷积神经网络 (Diffusion Convolutional Neural Network, DCNN)25 将图卷积看作为扩散过程，它假设信息在邻接节点以确定的转移概率流动，因此信息分布能在几轮后达到平衡。DCNN定义扩散图卷积为：
H ( k ) = f ( W ( k ) ⊙ P k X ) , (17) \bm H^{(k)}=f(\bm W^{(k)}\odot\bm P^k\bm X),\tag{17} H(k)=f(W(k)⊙PkX),(17)
其中， f ( ⋅ ) f(\cdot) f(⋅)是激活函数，转移概率矩阵 P ∈ R n × n \bm P\in \R^{n\times n} P∈Rn×n可由 P = D − 1 A \bm P=\bm D^{-1}\bm A P=D−1A计算。注意到在DCNN中，隐状态表示矩阵 H k \bm H^{k} Hk与输入特征矩阵 X \bm X X具有相同维度，并不是先前隐状态表示矩阵 H k − 1 \bm H^{k-1} Hk−1的函数。DCNN串接 H ( 1 ) , ⋯ , H ( K ) \bm H^{(1)},\bm \cdots,\bm H^{(K)} H(1),⋯,H(K)作为最终模型输出。
由于扩散过程的静态分布是概率转移矩阵的幂级数之和，扩散图卷积 (Diffusion Graph Convolution, DGC)72 对每个扩散步的输出求和，替代串接，它将扩散图卷积定义为：
H = ∑ k = 1 K f ( P k X W ( k ) ) , (18) \bm H=\sum_{k=1}^Kf(\bm P^k\bm X\bm W^{(k)}), \tag{18} H=k=1∑Kf(PkXW(k)),(18)
其中， W ( k ) ∈ R D × F \bm W^{(k)}\in\R^{D\times F} W(k)∈RD×F， f ( ⋅ ) f(\cdot) f(⋅)是激活函数。使用转移概率矩阵的幂意味着，离中心节点距离越远的邻接点提供的信息越少。
PGC-DGCNN46 基于最短路径增加了远距离点对中心节点的贡献，它定义了一个最短路径邻接矩阵 S ( j ) \bm S^{(j)} S(j)。如果从节点 v v v到 u u u的最短路径是 j j j，则 S v , u ( j ) = 1 S_{v,u}^{(j)}=1 Sv,u(j)=1，否则为 0 0 0。利用超参数 r r r控制接受域大小，PGC-DGCNN引入如下图卷积操作：
H ( k ) = ∣ ∣ j = 0 r f ( ( D ~ ( j ) ) − 1 S ( j ) H ( k − 1 ) W ( j , k ) ) , (19) \bm H^{(k)}=||_{j=0}^r f((\tilde{\bm D}^{(j)})^{-1}\bm S^{(j)}\bm H^{(k-1)}\bm W^{(j,k)}), \tag{19} H(k)=∣∣j=0rf((D~(j))−1S(j)H(k−1)W(j,k)),(19)
其中， D ~ i i ( j ) = ∑ l S i , l ( j ) \tilde D_{ii}^{(j)}=\sum_lS_{i,l}^{(j)} D~ii(j)=∑lSi,l(j)， H ( 0 ) = X \bm H^{(0)}=\bm X H(0)=X， ∣ ∣ || ∣∣表示对向量串接。邻接矩阵最短路径计算的最大时间复杂度为 O ( n 3 ) O(n^3) O(n3)。
分区图卷积 (Partition Graph Convolution, PGC)75 基于不限于最短路径的确定准则，将一个节点的邻接点分为 Q Q Q组。PGC通过每组定义的领域构造 Q Q Q邻接矩阵，然后，PGC对每个邻居应用具有不同参数矩阵的GCN，并对结果求和：
H ( k ) = ∑ j = 1 Q A ˉ ( j ) H ( k − 1 ) W ( j , k ) , (20) \bm H^{(k)}=\sum_{j=1}^Q\bar{\bm A}^{(j)}\bm H^{(k-1)}\bm W^{(j,k)}, \tag{20} H(k)=j=1∑QAˉ(j)H(k−1)W(j,k),(20)
其中， H ( 0 ) = X \bm H^{(0)}=\bm X H(0)=X， A ˉ ( j ) = ( D ~ ( j ) ) − 1 / 2 A ~ ( j ) ( D ~ ( j ) ) − 1 / 2 \bar{\bm A}^{(j)}=(\tilde{\bm D}^{(j)})^{-1/2}\tilde{\bm A}^{(j)}(\tilde{\bm D}^{(j)})^{-1/2} Aˉ(j)=(D~(j))−1/2A~(j)(D~(j))−1/2， A ~ ( j ) = A ( j ) + I \tilde{\bm A}^{(j)}=\bm A^{(j)}+\bm I A~(j)=A(j)+I。
消息传递神经网络 (Message Passing Neural Network, MPNN)27 概括了基于空间的ConvGNNs的通用框架，其将图卷积看作为消息传递过程，消息能够直接通过边从一个节点流向另一个节点。MPNN经过K步消息传递迭代，让消息进一步传播。消息传递函数（即空间图卷积）定义为
h v ( k ) = U k ( h v ( k − 1 ) , ∑ u ∈ N ( v ) M k ( h v ( k − 1 ) , h u ( k − 1 ) , x v u e ) ) , (21) \bm h_v^{(k)}=U_k(\bm h_v^{(k-1)},\sum_{u\in N(v)}M_k(\bm h_v^{(k-1)},\bm h_u^{(k-1)},\bm x_{vu}^e)), \tag{21} hv(k)=Uk(hv(k−1),u∈N(v)∑Mk(hv(k−1),hu(k−1),xvue)),(21)
其中， h v ( 0 ) = x v \bm h_v^{(0)}=\bm x_v hv(0)=xv， U k ( ⋅ ) U_k(\cdot) Uk(⋅)和 M k ( ⋅ ) M_k(\cdot) Mk(⋅)是可学习参数的函数。在获得每个节点的隐状态表示之后， h v K \bm h_v^{K} hvK可传递至输出层，执行节点级别的预测任务，或者传递至readout函数，执行图级别的预测任务。Readout函数基于节点隐状态表示，生成一个完整的图表示，通常定义为
h G = R ( h v ( K ) ∣ v ∈ G ) , (22) \bm h_G=R(\bm h_v^{(K)}|v\in G), \tag{22} hG=R(hv(K)∣v∈G),(22)
其中， R ( ⋅ ) R(\cdot) R(⋅)表示可学习参数的readout函数。MPNN基于不同形式的 U k ( ⋅ ) U_k(\cdot) Uk(⋅)， M k ( ⋅ ) M_k(\cdot) Mk(⋅)和 R ( ⋅ ) R(\cdot) R(⋅)，能够覆盖大多数现有GNNs，例如[22]，[85]，[86]，[87]。
图同构网络 (Graph Isomorphism Network, GIN)57 发现，先前基于MPNN的方法不能从他们生成的图嵌入中区分不同的图结构。为弥补这个缺陷，GIN利用参数 ϵ ( k ) \epsilon^{(k)} ϵ(k)调整中心节点的权重，执行以下图卷积：
h v ( k ) = M L P ( 1 + ϵ ( k ) ) h v ( k − 1 ) + ∑ u ∈ N ( v ) h u ( k − 1 ) , (23) \bm h_v^{(k)}=MLP(1+\epsilon^{(k)})\bm h_v^{(k-1)}+\sum_{u\in N(v)}\bm h_u^{(k-1)}, \tag{23} hv(k)=MLP(1+ϵ(k))hv(k−1)+u∈N(v)∑hu(k−1),(23)
其中 M L P ( ⋅ ) MLP(\cdot) MLP(⋅)表示多层感知机。
由于图节点的邻接点数量可能1至上千，甚至更多，考虑全部邻接点往往效率低。GraphSage42 为每个节点采样固定数目的邻接点，执行如下卷积：
h v ( k ) = σ ( W ( k ) ⋅ f k ( h v ( k − 1 ) , { h v ( k − 1 ) , ∀ u ∈ S N ( v ) } ) ) , (24) \bm h_v^{(k)}=\sigma(\bm W^{(k)}\cdot f_k(\bm h_v^{(k-1)},\{\bm h_v^{(k-1)}, \forall u\in S_{\mathcal N(v)}\})), \tag{24} hv(k)=σ(W(k)⋅fk(hv(k−1),{hv(k−1),∀u∈SN(v)})),(24)
其中， h v ( 0 ) = x v \bm h_v^{(0)}=\bm x_v hv(0)=xv， f k ( ⋅ ) f_k(\cdot) fk(⋅)是聚合函数， S N ( v ) S_{\mathcal N(v)} SN(v)是节点 v v v的随机采样集。聚合函数应对节点顺序具有不变性，如均值、求和或最大化函数。
图注意力网络 (Graph Attention Network, GAT)43 不同于GraphSage42、GCN22中邻接点对中心点分别具有完全相同、预定义的贡献（不同点详见图4），GAT采用注意力机制学习连接点的关系权重，GAT定义图卷积为：
h v ( k ) = σ ( ∑ u ∈ N ( v ) ∪ v α v u ( k ) W ( k ) h u ( k − 1 ) ) , α v u ( k ) = s o f t m a x ( g ( a ⊤ [ W ( k ) h v ( k − 1 ) ∣ ∣ W ( k ) h u ( k − 1 ) ] ) ) , (25,26) \bm h_v^{(k)}=\sigma(\sum_{u \in {\mathcal N(v)} \cup v}\alpha_{vu}^{(k)}\bm W^{(k)}\pmb h_u^{(k-1)}), \quad \alpha_{vu}^{(k)}=softmax(g(\bm a^\top [\bm W^{(k)}\pmb h_v^{(k-1)}||\pmb W^{(k)}\pmb h_u^{(k-1)}])), \tag{25, 26} hv(k)=σ(u∈N(v)∪v∑αvu(k)W(k)hhhu(k−1)),αvu(k)=softmax(g(a⊤[W(k)hhhv(k−1)∣∣WWW(k)hhhu(k−1)])),(25,26)
其中， h v ( 0 ) = x v \pmb h_v^{(0)}=\pmb x_v hhhv(0)=xxxv，注意力权重 α v u ( k ) \alpha_{vu}^{(k)} αvu(k)度量节点 v v v和邻接点 u u u的连接强度， a \pmb a aaa为可学参数。softmax确保节点 v v v对所有邻接点的注意力权重和为1。进一步，GAT使用多头注意力增强模型表达能力，使得在节点分类任务上比GraphSage具有显著提升。
与GAT假设每个注意力头具有同等贡献不同，门控注意力网络 (Gated Attention Network, GAAN)48 引入额外计算每个注意力头注意力的自注意力机制。除在空间上应用图注意力之外，GeniePath55 进一步引入门控注意力机制，控制卷积层之间的信息流。也有一些其它的图注意力模型，如[88]，[89]，然而，这些模型不属于ConvGNN框架。
混合模型网络 (Mixture Model Network, MoNet)44 采用不同的方法为邻接点分配权重，它引入节点伪坐标决定节点与邻接点的相对位置。当两节点的相对位置已知，使用权重映射函数将这两节点的相对位置映射为相对权重。这种方式，不同位置可共享同一个参数相同的滤波器。在MoNet框架下，一些现有的流形方法如Geodesic CNN (GCNN)90，Anisotropic CNN (ACNN)91 ，Spline CNN92，以及一些图方法如GCN22，DCNN25等，通过构造非参数权重函数，可以将这些模型作为MoNet特例泛化。此外，MoNet使用一种参数可学习的高斯核，用于自适应地学习权重函数。
另一些研究基于确定的准则对邻接节点排序，并将每个排名与一个可学习的参数关联，实现不同位置的参数共享。PATCHY-SAN26 根据节点的图标签对邻接点排序，并选择前 q q q个邻接点。图标签的本质是节点分数，分数可通过节点度、中心性、WeisfeilerLehman颜色推导93,94 。PATCHY-SAN使用标准的1D卷积滤波器聚合邻接点信息，滤波器的权值顺序与邻接点排序相关。PATCHY-SAN的排序仅依赖于图结构，需大量的数据处理计算。
大规模图卷积网络 (Largescale Graph Convolutional Network, LGCN)45 基于节点特征信息对邻接点排序，对每个节点，LGCN集成邻接点特征矩阵，并沿着列对特征排序，并将排序后的特征矩阵的前 q q q行作为中心节点的输入数据。
提高训练效率训练ConvGNNs如GCN22，通常需要在内存中保存完整的图数据和所有节点的中间状态。以全批次方式训练ConvGNNs，会遭遇严重的内存溢出问题，尤其是包含数百万节点的图。为降低内存消耗，GraphSage42 提出一种用于ConvGNNs训练的批处理算法，它以每个节点为树根，以递归K步的方式扩展根节点的邻接点，采样固定数量的样本。对每一颗采样树，GraphSage自底向上聚合节点表示作为根节点表示。
不同于GraphSage42为每个节点采样固定数量的邻接点，快速学习的图卷积网络 (Fast Learning with Graph Convolutional Network, FastGCN)49 为每个图卷积层采样固定数量的节点，它将图卷积解释为节点嵌入函数在概率度量下的积分变换。采用蒙特卡洛近似和方差缩减技术加速训练过程。FastGCN在每层独立采样节点，层间可能是稀疏连接。Huang等人51 提出一种自适应分层采样方法，以上层作为条件采样下层节点，该方法比FastGCN获得更高的准确率，而代价是使用了更复杂的采样方案。
随机训练的图卷积网络 (Stochastic Training of Graph Convolutional Networks, StoGCN)50 使用历史节点表示作为控制变量，将图卷积的感受域降低到任意小的尺度。即使每个节点仅有两个邻接，StoGCN仍获得相当的性能，然而，StoGCN仍需要保存所有节点的中间状态，在大图中内存开销大。
Cluster-GCN58 使用图聚类算法采样子图，并在子图的节点上执行图卷积。由于领域搜索局限于子图，使得Cluster-GCN能够用更少的时间和内存消耗处理大图，同时使用更深的架构。ClusterGCN提供一份与现有ConvGNN训练算法在时间和内存开销上的比较。我们基于表IV对其结果进行分析。
在表IV中，GCN22作为使用全批次训练的基线方法。GraphSage以时间换空间，且时间和内存复杂度随 K K K和 r r r指数级增长。StoGCN时间复杂度最高，且内存瓶颈仍未解决，然而，当 r r r值很小时，StoGCN能够获得满意的性能。Cluster-GCN未引入冗余计算，时间复杂度与基线方法相同，在所有方法中，Cluster-GCN的内存复杂度最低。
谱模型和空间模型的比较谱模型具有图信息处理的理论支持。通过设计新的图信号滤波器（例如Cayleynets23 ），可实现新的ConvGNNs。然而，因性能、通用性和灵活性的问题，人们偏爱空间模型：
第一，谱模型的效率低于空间模型。谱模型要么需要执行特征值计算，要么处理完整图。空间模型通过信息传播的方式在图领域直接执行卷积，能够扩展到大图上，且计算能使用批节点方式取代整个图；第二，谱模型假设处理固定图，依赖于图傅里叶基，难以泛化新图，因为对图的任意扰动都会改变特征基。另一方面，空间模型在每个节点执行局部图卷积，权重可以很容易在不同位置和结构间共享；第三，谱模型的操作局限于无向图，而空间模型能够灵活地应对多源图输入，如边输入15,27,86,95,96、有向图25,72、信号图97、异质图98,99，因为这些图输入能够很容易地融入进聚合函数。
C. 图池化模块
我们需要在最终任务中使用GNN生成的节点特征，然而在计算上直接使用所有这些特征具有挑战，因此需要降采样策略。依赖于目标和在网络中扮演的角色，策略具有不同的名称：
池化操作对节点负采样，生成更小的表示来降低参数量，从而避免过拟合、排列不变和计算复杂的问题；readout操作主要用于基于节点表示生成图级别表示；
它们的机制相似，本节中我们使用池化指代GNNs中各种降采样策略。在一些早期工作，基于图的拓扑结构使用特征分解的方法粗化图，然后，这些方法时间复杂度高。Graclus算法100 是一种可选的特征分解算法，计算原始图的类簇版本。现在，均值/最大/求和池化是实现降采样最简单的方式，因为可以在池化窗口中很快地计算这些池化操作：
h G = m e a n / m a x / s u m ( h 1 ( K ) , h 2 ( K ) , ⋯ , h n ( K ) ) , (27) \bm h_G=mean/max/sum(\bm h_1^{(K)}, \bm h_2^{(K)}, \cdots, \bm h_n^{(K)}), \tag{27} hG=mean/max/sum(h1(K),h2(K),⋯,hn(K)),(27)
其中， K K K是最后一层图卷积的索引。
Henaff等人20 说明在网络起始部分执行简单地最大/平均池化，对在图域降维，以及降低图傅里叶变换操作的开销十分重要。此外，一些研究工作17,27,46使用注意力机制增强平均和求和池化。
即使使用注意力机制，一些缩减操作（如求和池化）仍不能令人满意，因为不管图的大小，总是生成固定大小的嵌入，不能有效利用嵌入。Vinyals10 提出Set2Set方法用于生成随输入增加而增加的内存，然后，在执行可能破坏信息的缩减技术之前，它利用LSTM将具有顺序依赖的信息融入记忆嵌入。
Defferrard et al.21 通过重新排列图中节点的方式，解决了这一问题。他们在ChebNet方法中设计了一种有效的池化策略，即利用Graclus算法100 将输入图首先粗化为多级。经粗化之后，用平衡二叉树重新排列输入图及其粗化图中的节点，自底向上随机聚合平衡二叉树，使得相似的节点排在一起，在这种重新排列的信号上，池化比在原始图上更高效。
Zhang et al.52 提出的DGCNN中提出了相似的池化策略，名为SortPooling，将节点以有意义的形式重新排列，并执行卷积。与ChebNet21不同的是，DGCNN通过节点在图结构中的角色对节点排序。空间图卷积中无序的节点特征可认为是连续的WL颜色93，他们用这些颜色排序节点。为排序节点特征，通过扩展或裁剪节点特征矩阵，它将图大小统一为 q q q，如果 n > q n>q n>q，则删除最后 n − q n-q n−q行，否则加入 q − n q-n q−n行0值。
先前池化方法主要考虑了图特征，但忽略了图结构信息。最近，[54]提出一种可微的池化——DiffPool，用于生成层次化的图表示。与先前所有粗化方法相比，DiffPool并不是简单地聚类图中的节点，而是在第 k k k层学习分簇矩阵 S \bm S S， S ( k ) ∈ R n k × n k + 1 \bm S^{(k)}\in\R^{n_k\times n_{k+1}} S(k)∈Rnk×nk+1， n k n_k nk为第 k k k层的节点数量。矩阵 S ( k ) \bm S^{(k)} S(k)中的概率值，基于节点特征和拓扑结构生成：
S ( k ) = s o f t m a x ( C o n v G N N k ( A ( k ) , H ( k ) ) ) , (28) \bm S^{(k)}=softmax(ConvGNN_k(\bm A^{(k)}, \bm H^{(k)})), \tag{28} S(k)=softmax(ConvGNNk(A(k),H(k))),(28)
这个方法的核心思想综合考虑图的拓扑和特征信息，学习全面的节点分配，因此，任意标准的ConvGNNs都能实现公式28。然而，DiffPool的缺点在于，池化后的图变为密集图，之后的时间复杂度变为 O ( n 2 ) O(n^2) O(n2)。
最近提出SAGPool102 方法，它同时考虑了节点特征和图拓扑，且以自注意的方式学习池化。
总之，池化是一种削减图大小重要的方式，如何提高池化的有效性、降低池化的复杂度是一个开放问题。
D. 理论层面讨论
我们从不同角度讨论图神经网络的理论基础。
感受野的形状节点的感受野是指决定节点最终状态的节点集，当组合多个空间图卷积层，一个节点的感受野每次朝离它最远的邻接点移动一步。Micheli24证明了，存在有限数量的空间图卷积层，能够使图节点 v v v的感受野覆盖完整图，因此，ConvGNN能够利用堆叠的局部图卷积层提取全局信息。
VC维VC维是对模型复杂度的度量，定义为the largest number of points that can beshatteredby a model。很少有研究工作分析GNNs的VC维。给定模型参数的数量 p p p和节点数 n n n，Scarselli et al.103 推理出GNN* 的VC维，在使用sigmoid或tanh激活函数时为 O ( p 4 n 2 ) O(p^4n^2) O(p4n2)，使用分段多项式激活函数时为 O ( p 2 n ) O(p^2n) O(p2n)。表明，当使用sigmoid或tanh激活函数，GNN*的模型复杂度随 p p p和 n n n的增加而快速增加。
图同构拓扑相同的两个图同构。给定 G 1 G_1 G1和 G 2 G_2 G2这两个异构图，Xu et al.57 基于同形WL测试93证明，如果使用一个GNN将 G 1 G_1 G1和 G 2 G_2 G2映射为两个不同嵌入，则可认为这两个图异构，并指出常见的GNNs如GCN22和GraphSage42无法区分不同的图结构，并进一步证明，如果GNN的聚合函数和readout函数是单射函数，则GNN与WL测试一样，同样可区分不同的图结构。
等变性和不变性执行节点级任务的GNN必须是一个等变函数，执行图级任务的GNN必须是一个不变函数。对于节点级任务，以 f ( A , X ) ∈ R n × d f(\bm A, \bm X)\in\R^{n\times d} f(A,X)∈Rn×d表示GNN， Q Q Q表示任意改变节点排序的排列矩阵。若 f ( Q A Q ⊤ , Q X ) = Q f ( A , X ) f(\bm Q\bm A\bm Q^\top,\bm Q\bm X)=\bm Qf(\bm A,\bm X) f(QAQ⊤,QX)=Qf(A,X)，则GNN是等变的。对于图级任务，令 f ( A , X ) ∈ R d f(\bm A, \bm X)\in\R^d f(A,X)∈Rd，若满足 f ( Q A Q ⊤ , Q X ) = f ( A , X ) f(\bm Q\bm A\bm Q^\top,\bm Q\bm X)=\bm f(\bm A,\bm X) f(QAQ⊤,QX)=f(A,X)，则GNN是不变的。为获得等价性和不变性，GNN的组件必须不受节点排序影响。Maron et al.104 理论地研究了图数据的排列不变量和等变线性层的特征。
泛化逼近众所周知，包含一层隐藏层的多层前向感知机模型能够逼近任意Borel可测函数105 。很少有研究GNNs泛化逼近的工作，Hammer et al.106 证明，级联可近似结构化输出的函数。Scarselli et al.107 证明，RecGNN15 能以任意精度近似任意保持展开等价性的函数。节点的展开树可通过在一定深度上迭代扩展节点的邻接点构造，若两个节点的展开树等价，则两个节点展开等价。Xu et al.57 展示，在消息传递框架下的ConvGNNs不是定义在多重集上的连续函数的通用逼近器。Maron et al.104 证明，不变图网络能近似在图上定义的任意不变函数。
VI. 图自编码器（Graph Auto Encoders，GAEs）
GAEs是将节点映射至潜在特征空间，并从潜在特征空间中解码图信息的深度神经网络框架。GAEs可用于学习网络嵌入或者生成新图。表V总结了所选GAEs的主要特征。接下来，我们从两个角度简要介绍GAEs：网络嵌入和图生成。
A. 网络嵌入（Network Embedding）
网络嵌入是节点的低维向量表示，保留着节点的拓扑信息。GAEs使用编码器提取网络嵌入学习网络嵌入，使用解码器强制网络嵌入保留图拓扑信息，例如PPMI矩阵和邻接矩阵。
早期方法主要利用多层感知机构造GAEs，学习网络嵌入。深度神经网络图表示 (Deep Neural Network for Graph Representations, DNGR)59 使用堆叠去噪自编码器，通过多层感知机编码和解码PPMI矩阵。同期，结构型深度网络嵌入 (Structural Deep Network Embedding, SDNE)60 使用堆叠去噪自编码器同时保留节点一阶近似和二阶近似，SDNE提出两种损失函数分别用于编码器和解码器输出，第一个损失函数通过最小化节点与其邻接点网络嵌入的距离的方式学习网络，保留节点一阶近似，第一个损失函数 L 1 s t L_{1st} L1st定义为
L 1 s t = ∑ ( v , u ) ∈ E A v , u ∣ ∣ e n c ( x v ) − e n c ( x u ) ∣ ∣ 2 , (29) L_{1st}=\sum_{(v,u)\in E}A_{v,u}||enc(\bm x_v) - enc(\bm x_u)||^2, \tag{29} L1st=(v,u)∈E∑Av,u∣∣enc(xv)−enc(xu)∣∣2,(29)
其中， x v = A v , : \bm x_v=\bm A_{v,:} xv=Av,:， e n c ( ⋅ ) enc(\cdot) enc(⋅)是由多层感知机组成的编码器。第二个损失函数通过最小化节点输入及其重构后输入之间的距离的方式学习网络嵌入，保留节点二阶近似，具体地，第二个损失函数 L 2 s t L_{2st} L2st定义为
L 2 n d = ∑ v ∈ V ∣ ∣ ( d e c ( e n c ( x v ) ) − x v ) ⊙ b v ∣ ∣ 2 , (30) L_{2nd}=\sum_{v\in V}||(dec(enc(\bm x_v))-\bm x_v)\odot \bm b_v||^2,\tag{30} L2nd=v∈V∑∣∣(dec(enc(xv))−xv)⊙bv∣∣2,(30)
其中，如果 A v , u = 0 A_{v,u}=0 Av,u=0，则 b v , u = 1 b_{v,u}=1 bv,u=1；如果 A v , u = 1 A_{v,u}=1 Av,u=1，则 b v , u = β > 1 b_{v,u}=\beta > 1 bv,u=β>1； d e c ( ⋅ ) dec(\cdot) dec(⋅)是由多层感知机组成的解码器。
DNGR59 and SDNE60 仅考虑节点的连接结构信息，忽略了节点可能包含描述自身属性的特征信息。图自编码器 (Graph Autoencoder, GAE*)61 利用GCN22 同时编码节点结构信息和特征信息，GAE*的解码器由两层图卷积组成，形式为
Z = e n c ( X , A ) = G c o n v ( f ( G c o n v ( A , X ; Θ 1 ) ) ; Θ 2 ) , (31) \bm Z=enc(\bm X, \bm A)=Gconv(f(Gconv(\bm A,\bm X;\bm \Theta_1));\bm \Theta_2), \tag{31} Z=enc(X,A)=Gconv(f(Gconv(A,X;Θ1));Θ2),(31)
其中 Z \bm Z Z表示图的网络嵌入矩阵， f ( ⋅ ) f(\cdot) f(⋅)表示ReLU激活函数， G c o n v ( ⋅ ) Gconv(·) Gconv(⋅)是公式12定义的图卷积层。GAE*解码器通过重构图邻接矩阵，从它们的嵌入中解码节点关系信息，可定义为
A ^ v , u = d e c ( z v , z u ) = σ ( z v ⊤ z u ) , (32) \hat\bm A_{v,u}=dec(\bm z_v,\bm z_u)=\sigma(\bm z_v^\top \bm z_u), \tag{32} A^v,u=dec(zv,zu)=σ(zv⊤zu),(32)
其中， z v \bm z_v zv是节点 v v v的嵌入。GAE*通过最小化给定的真实邻接矩阵 A \bm A A和重构的邻接矩阵 A ^ \hat\bm A A^之间的负交叉熵训练。
由于自编码器的容量，仅简单重构邻接矩阵可能导致过拟合。变分图自编码器 (Variational Graph Autoencoder, VGAE)61 是GAE的变分版本，用于学习数据分布，VGAE优化变分下界 L L L：
L = E q ( Z ∣ X , A ) [ log p ( A ∣ Z ) ] − K L [ q ( Z ∣ X , A ) ∣ ∣ p ( Z ) ] , (33) L=E_{q(\bm Z|\bm X, \bm A)}[\log p(\bm A|\bm Z)]-KL[q(\bm Z|\bm X, \bm A)||p(\bm Z)], \tag{33} L=Eq(Z∣X,A)[logp(A∣Z)]−KL[q(Z∣X,A)∣∣p(Z)],(33)
其中， K L ( ⋅ ) KL(\cdot) KL(⋅)是度量不同分布间距离的KL散度函数， p ( Z ) p(\bm Z) p(Z)是高斯先验：
p ( Z ) = ∏ i = 1 n p ( z i ) = ∏ i = 1 n N ( z i ∣ 0 , I ) , p(\mathbf{Z})=\prod_{i=1}^{n} p\left(\mathbf{z}_{i}\right)=\prod_{i=1}^{n} N\left(\mathbf{z}_{i} \mid 0, \mathbf{I}\right),\\ p(Z)=i=1∏np(zi)=i=1∏nN(zi∣0,I),
其中
p ( A i j = 1 ∣ z i , z j ) = dec ( z i , z j ) = σ ( z i T z j ) q ( Z ∣ X , A ) = ∏ i = 1 n q ( z i ∣ X , A ) q ( z i ∣ X , A ) = N ( z i ∣ μ i , diag ( σ i 2 ) ) \begin{aligned} p\left(A_{i j}=1 \mid \mathbf{z}_{i},\mathbf{z}_{j}\right)&=\operatorname{dec}\left(\mathbf{z}_{i},\mathbf{z}_{j}\right)=\sigma\left(\mathbf{z}_{i}^{T} \mathbf{z}_{j}\right)\\ q(\mathbf{Z} \mid \mathbf{X}, \mathbf{A})&=\prod_{i=1}^{n} q\left(\mathbf{z}_{i} \mid \mathbf{X}, \mathbf{A}\right)\\ q\left(\mathbf{z}_{i} \mid \mathbf{X}, \mathbf{A}\right)&=N\left(\mathbf{z}_{i} \mid \mu_{i}, \operatorname{diag}\left(\sigma_{i}^{2}\right)\right) \end{aligned} p(Aij=1∣zi,zj)q(Z∣X,A)q(zi∣X,A)=dec(zi,zj)=σ(ziTzj)=i=1∏nq(zi∣X,A)=N(zi∣μi,diag(σi2))
均值向量 μ i \mu_i μi是编码器输出的第 i i i行，见公式31定义； log σ i \log\sigma_i logσi的推导类似于 μ i \mu_i μi作为另一个编码器。根据公式33，VGAE假设经验分布 q ( Z ∣ X , A ) q(\bm{Z}|\bm{X}, \bm{A}) q(Z∣X,A)应与先验分布 p ( Z ) p(\bm Z) p(Z)尽可能接近。
为进一步促使经验分布近似于先验分布，对抗标准化变分自编码器 (Adversarially Regularized Variational Graph Autoencoder, ARVGA)62,109 使用生成对抗网络 (generative adversarial networks, GAN)110 训练框架，在训练生成模型时，GAN类似于生成器和判别器之间的一场比赛，生成器尝试生成尽可能真的“伪样本”，而判别器尝试区分样本的真假。受GANs启发，ARVGA尽力学习一个编码器，来产生与真实先验分布 p ( Z ) p(\bm Z) p(Z)无法区别的经验分布 q ( Z ∣ X , A ) q(\bm{Z}|\bm{X}, \bm{A}) q(Z∣X,A)。
类似于GAE*，GraphSage42 使用两层图卷积层编码节点特征，为了替换优化重构误差，GraphSage表明两个节点之间的关系信息可以通过负采样保留，损失为
L ( z v ) = − log ( dec ( z v , z u ) ) − Q E v n ∼ P n ( v ) log ( − dec ( z v , z v n ) ) , (34) L\left(\mathbf{z}_{v}\right)=-\log \left(\operatorname{dec}\left(\mathbf{z}_{v}, \mathbf{z}_{u}\right)\right)-Q E_{v_{n} \sim P_{n}(v)} \log \left(-\operatorname{dec}\left(\mathbf{z}_{v}, \mathbf{z}_{v_{n}}\right)\right), \tag{34} L(zv)=−log(dec(zv,zu))−QEvn∼Pn(v)log(−dec(zv,zvn)),(34)
其中，节点 u u u是节点 v v v的邻接点， v n v_n vn是从负采样分布 P n ( v ) P_n(v) Pn(v)中采样的、与节点 v v v距离远的点。损失函数的本质是，使节点与其邻接点的表示尽可能相似，与其远距离点尽可能不相似。DGI56 通过最大化局部互信息，驱使局部网络嵌入捕获全局结构信息，它通过实验展示了对GraphSage42显著的改进。
对于先前方法，它们本质上通过解决连接预测问题学习网络嵌入，然而，在稀疏图中，正节点对明显少于负节点对。为缓解在稀疏图中学习网络嵌入的问题，另一种方法通过随机排列或随机游走，将图转变为序列。以这种方式，可用于处理序列的深度学习方法也可以直接应用于处理图。深度递归网络表示 (Deep Recursive Network Embedding, DRNE)63 假设一个节点的网络嵌入应于其邻接点网络嵌入的聚合近似，它采用LSTM聚合节点的邻接点，DRNE的重构误差定义为：
L = ∑ v ∈ V ∥ z v − L S T M ( { z u ∣ u ∈ N ( v ) } ) ∥ 2 , (35) L=\sum_{v \in V}\left\|\mathbf{z}_{v}-L S T M\left(\left\{\mathbf{z}_{u} \mid u \in N(v)\right\}\right)\right\|^{2}, \tag{35} L=v∈V∑∥zv−LSTM({zu∣u∈N(v)})∥2,(35)
其中， z v \bm z_v zv是从字典中查找的节点 v v v的网络嵌入，LSTM网络将节点 v v v按度随机排序的邻接点序列作为输入。如公式35所示，DRNE通过LSTM网络隐性地学习网络嵌入，而不是使用LSTM网络生成网络嵌入，它避免了LSTM网络受输入节点序列排列影响的问题。
对抗标准化自编码器网络表示 (Network Representations with Adversarially Regularized Autoencoders, NetRA)64 使用通用损失函数，提出一种图编/解码框架，损失函数定义为：
L = − E z ∼ P data ( z ) ( dist ( z , dec ( enc ( z ) ) ) ) , (36) L=-E_{\mathbf{z} \sim P_{\text {data}}(\mathbf{z})}(\operatorname{dist}(\mathbf{z}, \operatorname{dec}(\operatorname{enc}(\mathbf{z})))), \tag{36} L=−Ez∼Pdata(z)(dist(z,dec(enc(z)))),(36)
其中， d i s t ( ⋅ ) dist(\cdot) dist(⋅)是节点嵌入 z \bm z z和重构嵌入 z \bm z z之间的距离度量。NetRA的编码器和解码器是LSTM网络，将在每一个节点 v ∈ V v\in V v∈V为根上的随机游走作为网络输入。与ARVGA62 类似，NetRA通过对抗学习，在先验分布里，规范化学习到的网络嵌入，尽管NetRA忽略了LSTM网络受输入节点排列影响的问题，实验结果仍验证了NetRA的有效性。
B. 图生成
在多图情况下，GAEs通过将图编码在隐藏表示、解码给定隐藏表示的图结构，能够学习图的生成分布。由于药物研发领域的高实践价值，多数图生成GAEs被设计用于解决分子图生成问题，这些方法以顺序方式或全局方式产生一个新图。
顺序方法是通过一步接一步地生成节点和边的方式生成一张新图。[111]，[112]，[113]使用深度CNNs和RNNs各自作为编码器和解码器，建模分子图字符串表示的生成过程。虽然这些方式是基于特定领域的，但对于通用的图，可通过迭代的方式向图中增加边和节点直至满足确定准则，来生成图。
图深度生成模型 (Deep Generative Model of Graphs, DeepGMG)65 假定图的概率是所有节点可能排列的和：
p ( G ) = ∑ π p ( G , π ) , (37) p(G)=\sum_{\pi} p(G, \pi),\tag {37} p(G)=π∑p(G,π),(37)
其中， π \pi π表示一个节点排序。它捕获图中所有节点和边的联合概率。DeepGMG通过一系列决定生成图，如是否加入节点、加入哪个节点、是否加入边、哪一个节点与新节点相连，这个生成节点和边的决策过程以增长图的节点状态和图状态为条件，且状态由RecGNN更新。
在另一个网络中，GraphRNN66 提出一种图级别RNN和边级别RNN建模节点和边的生成过程。图级别的RNN每次向节点序列中接入新节点，而边级别的RNN产生一个指示新节点和序列与已生成节点之间连接信息的二进制序列。
全局方法一次输出一张图。图变分自编码器 (Graph Variational Autoencoder, GraphVAE)67 将已有的节点和边作为独立的随机变量，基于对编码器先验分布 q ϕ ( z ∣ G ) q_\phi(\bm z|G) qϕ(z∣G)和解码器生成分布 p θ ( G ∣ z ) p_\theta(G|\bm z) pθ(G∣z)的假设，GraphVAE优化变分下界：
L ( ϕ , θ ; G ) = E q ϕ ( z ∣ G ) [ − log p θ ( G ∣ z ) ] + K L [ q ϕ ( z ∣ G ) ∥ p ( z ) ] , (38) L(\phi, \theta ; G)=E_{q_{\phi}(z \mid G)}\left[-\log p_{\theta}(G \mid \mathbf{z})\right]+K L\left[q_{\phi}(\mathbf{z} \mid G) \| p(\mathbf{z})\right], \tag{38} L(ϕ,θ;G)=Eqϕ(z∣G)[−logpθ(G∣z)]+KL[qϕ(z∣G)∥p(z)],(38)
其中， p ( z ) p(\bm z) p(z)遵循高斯先验， ϕ \phi ϕ和 θ \theta θ是可学习参数。利用ConvGNN作为编码器、简单多层感知机作为解码器，GraphVAE使用它的邻接矩阵输出生成的图，但输出图的属性难以控制，如图连接性、有效性以及节点相容性。
标准化图自编码器 (Regularized Graph Variational Autoencoder, RGVAE)68 进一步向图变分自编码器中施加有效性约束，从而规范化解码器输出分布。
分子生成式对抗网络 (Molecular Generative Adversarial Network, MolGAN)68 集成convGNNs114 、GANs115和强化学习目标，生成具有期望性质的图，MolGAN由生成器和判别器组成，通过互相竞争，提高生成器输出的真实性。在MolGAN中，生成器试图从其特征矩阵中生成一张伪图，而判别器根据从经验数据中的采样辨别伪图，除此之外，在包含判别器的基础上，额外引入一个奖励网络，利用额外的评估器，鼓励生成的图包含某些属性。
NetGAN70 组合LSTMs7 和 Wasserstein GANs116，使用基于随机游走的方法生成图，NetGAN通过LSTM网络训练产生近似合理随机游走的生成器，并迫使判别器利用真集识别伪的随机游走。经过训练，通过对生成器基于随机游走产生的节点共现矩阵进行归一化，派生出新图。
简而言之，顺序方法将图线性化为序列，导致在有环图中可能丢失信息；全局方法一次产生一张完整图。由于GAE输出空间多达 O ( n 2 ) O(n^2) O(n2)，因此它们不能扩展到大图上。
VII. 时空图神经网络（Spatial-Temporal Graph Neural Networks，STGNNs）
就对图的结构和输入而言，图在真实场景下的应用是动态的。STGNNs在捕获图的动态性方面占据着重要位置。这个范畴下的方法假设连接的节点相互依赖，目的是建模节点输入的动态性。例如，交通网络有道路上的多个速度传感器组成，其边的权重由传感器对之间的距离决定。由于一条道路的交通状况可能依赖于其相邻道路的交通状况，在进行交通速度预测时，考虑空间依赖性很重要。
STGNNs的解决方案是，同时捕获图的空间和时间依赖性。STGNNs的任务可以预测节点未来的标签和值，或者预测时间图标签。STGNNs具有两个研究方案，基于RNN的方法和基于CNN的方法。
多数基于RNN的方法使用图卷积过滤流向循环单元的输入和隐状态，捕获时空依赖性48,71,72。以一个简单的RNN举例：
H ( t ) = σ ( W X ( t ) + U H ( t − 1 ) + b ) , (39) \bm H^{(t)}=\sigma(\bm W\bm X^{(t)}+\bm U\bm H^{(t-1)}+b),\tag{39} H(t)=σ(WX(t)+UH(t−1)+b),(39)
其中， X ( t ) ∈ R n × d \bm X^{(t)}\in\R^{n\times d} X(t)∈Rn×d是 t t t时间步节点特征矩阵，插入图卷积之后，公式39变为：
H ( t ) = σ ( G c o n v ( X ( t ) , A ; W ) + G c o n v ( H ( t − 1 ) , A ; U ) + b ) , (40) \bm H^{(t)}=\sigma(Gconv(\bm X^{(t)},\bm A;\bm W)+Gconv(\bm H^{(t-1)},\bm A;\bm U)+b),\tag{40} H(t)=σ(Gconv(X(t),A;W)+Gconv(H(t−1),A;U)+b),(40)
其中， G c o n v ( ⋅ ) Gconv(\cdot) Gconv(⋅)是一个图卷积层。图卷积循环神经网络 (Graph Convolutional Recurrent Network, GCRN)71将LSTM网络和ChebNet21集合。扩散卷积循环神经网络 (Diffusion Convolutional Recurrent Neural Network, DCRNN)72 在GRU网络中添加一个扩散图卷积层（公式18），此外，DCRNN采用编码器-解码器框架，预测未来 K K K步的节点值。
同期，也有一些工作使用节点级RNNs和边级RNNs从不同方面解决时间信息，Structural-RNN73 提出一个循环框架，在每个时间步预测节点标签，它包含两种类型的RNNs，称为节点RNN和边RNN。每个节点和每个边的时间信息各自通过节点RNN和边RNN。为体现空间信息，节点级RNN将边RNN的输出作为输入。由于不同的节点和边具有不同的RNNs，导致模型复杂度显著增加，因此，它将节点和边通过语义分组，相同语义中的节点和边共享相同RNN模型，从而降低计算开销。
基于RNN的方法具有迭代传播耗时和梯度消失/爆炸问题。作为一种解决方案，基于CNN的方法以非递归的方式处理时空图，利用并行计算的优势。如图2d所示，基于CNN的方法将一维卷积层和图卷积层交叉，各自学习时间和空间依赖性。假设时空图神经网络的输入是张量 X ∈ R T × n × d \mathcal X\in\R^{T\times n\times d} X∈RT×n×d，在每一步，一维卷积层沿着时间轴在 X [ : , i , : ] \mathcal X_{[:,i,:]} X[:,i,:]上滑动，聚合每一个节点的时间信息，而图卷积层在 X [ i , : , : ] \mathcal X_{[i,:,:]} X[i,:,:]上运算，聚合每一个节点的空间信息。
CGCN74 将一维卷积层与ChebNet或GCN层组合，通过堆叠门控一维卷积层、图卷积层以及另一个门控一维卷积层，重构时空块。ST-GCN75 使用一维卷积核和PGC层（公式20）合成时空块。
先前所有的方法都使用预定义的图结构，他们假设预定义的图结构能够反映节点之间真实的依赖关系。然而，利用时空场景下的图数据的快照，能从静态数据中自动地学习到潜在的图结构。Graph WaveNet76 提出自适应邻接矩阵执行图卷积，自适应邻接矩阵定义为
A a d p = S o f t M a x ( R e L U ( E 1 E 2 ⊤ ) ) , , (41) \bm A_{adp}=SoftMax(ReLU(\bm E_1\bm E_2^\top)), \tag{41}, Aadp=SoftMax(ReLU(E1E2⊤)),,(41)
其中，SoftMax函数沿着行维度计算， E 1 \bm E_1 E1表示源节点嵌入， E 1 \bm E_1 E1表示目标节点嵌入，两个嵌入参数可学习。通过将 E 1 \bm E_1 E1和 E 2 \bm E_2 E2相乘，可获得源节点和目标节点之间的依赖权重。在复杂的基于卷积的时空神经网络中，在不给定邻接矩阵的情况下，Graph WaveNe依然可以表现良好。
学习潜在的静态空间依赖，有助于研究者发现网络中不同实体可解释的、稳定的相关关系。然而，在某些场景下，学习潜在的动态空间依赖也有助于提升模型精度。例如，在交通网络中，两条道路之间的移动时间可能依赖于它们的当前交通状况。GaAN48 在基于RNN的方法中利用注意力机制，学习动态空间依赖，在给定连接的节点的当前输入时，注意力函数能够更新两节点直接的连接权重。ASTGCN77 在基于CNN的方法中，进一步包含了空间注意力函数和时间注意力函数，学习潜在的动态空间依赖和时间依赖，学习潜在空间依赖的常见弊端在于，计算节点对空间依赖权重的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
VIII. 应用
图结构数据无所不在，GNNs有多种形式应用，本节中，我们总结了基本图数据集、评估方法和开源实现，并详细介绍GNNs在各种领域的实际应用。
A. 数据集
我们将数据集主要分为四组：引用网络、生化网络、社交网络及其它。表VI中汇总了选定的基准数据集，更详细的介绍见补充材料A。
B. 评估及开源实现
节点分类和图分类是评估RecGNNs和ConvGNNs常见的任务。
节点分类节点分类任务中，多数方法遵循对基准数据集标准分割为训练集、验证级以及测试集，包括Cora、Citeseer、Pubmed、PPI以及Reddit。它们报告了在测试集运行多次的平均准确率或F1分数。补充材料B包含一些方法实验结果的总结。这些结果并不表示一个严格的比较。Shchur et al.131 在节点分类任务上评估GNNs性能时具有两个缺点：
第一，在所有实验上使用相同的训练集、验证集和测试集，这会低估泛化误差 ；第二，用不同的训练技术训练不同的方法，如超参调整、参数初始化、学习率缩减和提前终止。
为进行相对公平的比较，我们向读者推荐 Shchur et al.31。
图分类在图分类中，研究者通常使用十折交叉验证评估模型，然而，[132]指出不同任务的环境设置不明确、不统一，并说明数据分割在模型选择与模型评估时的正确使用方式。常见问题是，测试集中的每一折同时用于模型选择和风险评估。[132]在标准统一的评估框架下比较GNNs，他们使用额外的十折交叉验证评估模型泛化性能，以及用90%/10% 训练集/测试集的分割的内部抵抗技术选择模型。另一种方法是两倍交叉验证，使用外部的 k k k折交叉验证评估模型，使用内部的 k k k折交叉验证选择模型。更详细的比较见原文。
开放领域的实现促进深度学习研究的基线实现工作。在补充材料C中，我们提供了本文提及的GNNs模型在开放领域实现的超链接。Fey et al.92 发布一个pytorch中实现很多GNNs的几何学习库：PyTorch Geometric。最近发布的Deep Graph Library (DGL)133 ，提供了许多GNNs在主流深度学习平台上高效实现，如PyTorch和MXNet。
C. 实际应用
GNNs在不同任务和领域具有许多应用。通用的任务能被一些GNNs直接处理，如节点分类、图分类、网络嵌入、图生成，以及时空图预测，如节点聚类134 、连接预测135和图分区136，我们在以下研究领域详细介绍几种应用。
计算机视觉GNNs在计算机视觉中的应用包括：场景图生成、点群分类以及动作识别。
利用视觉场景下的语义理解识别物体之间的语义关系。场景图识别模型目的是将图片解析为语义图，图由物体及其语义关系组成137,138,139 。另外有一些反向应用，如基于给定场景图生成现实图像140 。由于自然语言能被解析为一张语义图，每个单词表示一个物体，基于给定的文本描述合同图片是一种可期待的解决方案。
分类和分割点群，使得LiDAR设备能够看到周围环境，一个点群是一组使用LiDAR扫描的3D点记录。[141]，[142]，[143]将点群转变为k近邻图，或者superpoint图，并使用ConvGNNs探索拓扑结构。
识别视频中人物动作能促使机器更好地理解视频内容。一些解决方案通过检测视频剪辑中人物关节位置。人类关节作为骨架的连接，能很自然的形成一张图。给定关节位置的时间序列，[73]，[75]应用STGNNs学习人类动作模式。
自然语言处理文本分类是GNNs在自然语言处理中常见的应用，GNNs利用文档或单词的内部关系推理文档标签22,42,43。尽管现实中自然语言数据以序列顺序表示，但它们仍包含一个内部图结构，例如句法依存树，句法依存树定义句中单词间的句法关系。
Marcheggiani et al.152 提出Syntactic GCN，作用于CNN/RNN句子编码器的输出，Syntactic GCN基于句子的依存关系树聚合隐藏单词表示。Bastings et al.153 在神经机器翻译任务上使用Syntactic GCN。进一步地，Marcheggiani et al.154 与 Bastings et al.153 采用同样的模型处理句子的语义依存图。
“图到序列学习”基于给定的摘要单词的语义图（抽象意义表示），学习生成具有相同意思的句子。Song et al.155 提出graph-LSTM编码图级别语义信息，Beck et al.156 使用GGNN学习"图到序列"和神经网络机器翻译。对应的反向过程是，基于给定的句子生成语义或知识图，在知识发现领域很有意义。
交通在智能交通系统中，准确地预测交通速度、容量和道路密度在交通网络中十分重要。[48]，[72]，[74]使用STGNNs解决交通预测问题，它们认为交通网络是一个时空图，其中节点是安装在道路上的传感器，图中边通过节点对之间的距离测量，图中每个节点在一个窗口中平均交通速度作为动态输入。另一个工业级别应用是，的士需求预测。基于历史的士需求，定位信息，天气数据和时间特征，Yao et al.159 利用LSTM，CNN和网络嵌入训练LINE160，从而形成每个位置的联合表示，用于预测某位置在一段时间内的士需求数量。
推荐系统基于图的推荐系统将商品和用户作为节点。通过利用商品和商品，用户和用户，用户和商品的关系，以及内容信息，基于图的推荐系统能够产生高质量的推荐。推荐系统的关键在于，为用户打分商品重要性，因此，它可看作为一个连接预测问题。为预测用户和商品之间丢失的连接，Van et al.161 和 Ying et al.162 提出一种使用ConvGNNs作为编码器的GAE，Monti et al.163 结合RNN和图卷积学习已知评级的潜在过程。
化学在化学领域，研究人员应用GNNs研究分子/化合物图结构。在分子/化合物图中，原子作为节点，化学键作为边。为学习分子指纹，预测分子属性，推理蛋白质接口，以及合成化学混合物，在分子/化合物图中有三个主要任务：节点分类、图分类和图生成。
其它GNNs的应用不限于以上领域和任务。对GNNs的应用一直在不断探索，如程序验证17，程序推理166，社交影响预测167，对抗攻击预防168，电子监控记录模型169,170，大脑网络171，时间预测172，以及组合优化173。
IX. 未来方向
尽管已证明GNNs学习图数据的有效性，由于图的复杂性，挑战依然存在，本节中，我们指出GNNs未来的四个方向。
模型深度深度学习的成功依靠于深度神经网络架构174。然而，Li et al. 表明在增加卷积层数量后，ConvGNN性能急剧下降53。由于图卷积目的是将节点及其邻接点的表示接近，理论上，利用无限多的图卷积层，所有节点的表示将收敛至单点53。那么在学习图数据时，增加模型深度是否是一个好的策略？
扩展性权衡以破坏图的完整性为代价来提高GNNs的扩展性。无论是使用采样还是聚类，模型都会丢失部分图信息。通过采样，节点可能丢失对其影响大的邻居；通过聚类，图可能丢失独特的结构模式。如何权衡算法扩展性和图的完整性可能是未来研究方向。
异质性目前大多数图为同质图，难以将目前的GNNs应用于包含不同类型，或不同输入形式的节点和边的异质图，例如图像和文本。因此，应当研发新的方法处理异质图。
动态性节点或边可能出现或消失，节点/边可能随时间变化的图本质是动态的。需要新的图卷积适应于动态图。尽管STGNNs能解决部分动态图，然而很少有人考虑如何在动态空间关系上进行图卷积。
