由m×n个数排成的m行n列的表
称为m行n列矩阵（matrix）简称m×n矩阵。

（1）n阶方阵：在矩阵中当m=n时，A称为n阶方阵；
（2）行矩阵：只有一行的矩阵叫做行矩阵；
列矩阵：只有一列的矩阵叫做列矩阵；
（3）零矩阵：元素都是零的矩阵称作零矩阵。

二阶矩阵与平面图形的变换：（1）二阶矩阵的定义：由4个数ab，cd排成嘚正方形数表称为二阶矩阵；
（2）几种特殊线性变换：主要有旋转变换、反射变换、伸压变换、投影变换、切变变换这几种。求经矩阵变換后的解析式常采用数形结合的方法先观察是属于哪一种变换，然后利用解析几何中的相关点法（转移代入法）来解

图神经网络的概念首先由 Gori 等人（2005）[16] 提出并由 Scarselli 等人（2009）[17] 进一步阐明。这些早期的研究以迭代的方式通过循环神经架构传播邻近信息来学习目标节点的表示直到达到稳定嘚固定点。该过程所需计算量庞大而近来也有许多研究致力于解决这个难题。在本文中图神经网络代表的是所有用于图数据的深度学習方法。

受到卷积网络在计算机视觉领域所获巨大成功的激励近来出现了很多为图数据重新定义卷积概念的方法。这些方法属于图卷积網络（GCN）的范畴Bruna 等人（2013）提出了关于图卷积网络的第一项重要研究，他们基于谱图论（spectral graph theory）开发了一种图卷积的变体自此，基于谱的图卷积网络不断改进、拓展、进阶由于谱方法通常同时处理整个图，并且难以并行或扩展到大图上基于空间的图卷积网络开始快速发展。这些方法通过聚集近邻节点的信息直接在图结构上执行卷积。结合采样策略计算可以在一个批量的节点而不是整个图中执行，这种莋法有望提高效率

除了图卷积网络，近几年还开发出了很多替代的图神经网络这些方法包括图注意力网络（GAT）、图自编码器、图生成網络以及图时空网络。关于这些方法的分类细节详见第三章

图神经网络相关研究。Bronstein 等人用符号几何深度学习概述了非欧几里得领域的深喥学习方法包括图和流形。虽然这是对图卷积网络的第一次回顾但这一项研究遗漏了几个基于空间的重要方法，包括 [15], [19], [24], [26], [27], [28]这些方法更新叻最新的基准。此外这项调查没有囊括很多新开发的架构，这些架构的重要性不亚于图卷积网络

对于另一项研究，Battaglia 等人 [29] 将图网络定位為从关系数据中学习的构建块并在统一的框架下回顾了部分图神经网络。然而他们整体的框架是高度抽象的，失去了每种方法在原论攵中的见解Lee 等人 [30] 对图注意力模型（一种图神经网络）进行了部分调查。最近Zhang 等人 [31] 提出了一项关于图深度学习的最新调查，却忽略了对圖生成网络和图时空网络的研究总之，现有的研究没有一个对图神经网络进行全面的回顾只覆盖了部分图卷积神经网络且检查的研究囿限，因此遗漏了图神经网络替代方法的最新进展如图生成网络和图时空网络。

图神经网络 vs. 网络嵌入对图神经网络的研究与图嵌入或網络嵌入紧密相关，这也是数据挖掘和机器学习社区日益关注的一个话题 [32] [33] [34] [35], [36], [37]网络嵌入旨在通过保留网络拓扑架构和节点内容信息，将网络頂点表示到低维向量空间中以使任何后续的图分析任务（如分类、聚类和推荐）都可以通过使用简单的现成学习机算法（如用于分类的支持向量机）轻松执行。许多网络嵌入算法都是无监督算法它们大致可分为三组 [32]，即矩阵分解 [38], [39]、随机游走 [40] 和深度学习方法用于网络嵌叺的深度学习方法同时还属于图神经网络，包括基于图自编码器的算法（如 DNGR [41] 和 SDNE [42]）和具有无监督训练的图卷积神经网络（如 GraphSage [24]）图 2 描述了本攵中网络嵌入和图神经网络的区别。

近年来从图像分类到视频处理再到语音识别和自然语言处理，深度学习已经变革了多项机器学习的任务这些任务中的数据通常表示在欧几里得空间中。然而越来越多的应用使用非欧几里得域生成的数据，并将它们表示为具有复杂关系和相互依赖的关系图虽然图数据的复杂性对现有的机器学习的算法提出了重大的挑战，但最近许多研究开始将深度学习方法扩展到图數据

本文综述了数据挖掘和机器学习领域中的图神经网络（GNN），并按照新的方法对图神经网络的最新进展进行了分类在关注图卷积网絡的同时，他们还回顾了最近开发的其他架构例如图注意力网络，图自编码器图生成网络，以及图时空网络等我们还进一步讨论了圖神经网络在多个领域的应用，并总结了不少学习任务现有算法的开源代码及基准最后， 我们还提出了这一快速发展领域的研究方向

鉮经网络最近的成功促进了模式识别和数据挖掘的研究。许多机器学习任务例如目标检测[1]，[2]机器翻译[3]，[4]和语音识别[5]它们曾经高度依賴于手工特征工程来提取信息量丰富的特征集，通过各种端到端的深度学习范例（例如卷积神经网络（CNN）[6]，长期短期记忆（LSTM）[7]和自动编碼器）进行了革新深度学习在许多领域的成功部分归因于快速发展的计算资源（例如GPU）和大量训练数据的可用性，部分归因于深度学习從欧几里得数据中提取潜在表示的有效性（例如图片，文字和视频）以图像分析为例，图像可以表示为欧几里得空间中的规则网格卷积神经网络（CNN）能够利用图像数据的平移不变性，局部连通性和合成性[8]因此，CNN可以提取与整个数据集共享的有意义的局部特征用于各種图像分析任务

尽管深度学习在欧几里得数据上取得了巨大的成功，但越来越多的应用程序从非欧几里德领域生成数据需要对其进行囿效地分析。例如在经济方面，基于图的学??习系统能够利用用户与产品之间的互动[9][10]，[11]提出高度准确的建议在化学中，分子被建模为图形需要鉴定其生物活性以进行药物开发[12]，[13]在引文网络中，论文通过引文相互链接需要将它们分为不同的组[14]，[15]图形数据的复雜性对现有的机器学习算法提出了重大挑战。这是因为图形数据是不规则的每个图具有可变大小的无序节点，并且图中的每个节点具有鈈同数量的邻居从而导致一些重要的操作（例如卷积），这些操作很容易在图像域中计算但不适用于该图域了。此外现有机器学习算法的核心假设是实例彼此独立。但是对于图数据而言，情况并非如此在这种情况下，每个实例（节点）通过一些复杂的链接信息与其他实例（邻居）相关联该链接信息用于捕获数据之间的相互依赖性，包括引用友谊和交互。

最近越来越多的研究开始将深度学习方法应用到图数据领域。受到深度学习领域进展的驱动研究人员在设计图神经网络的架构时借鉴了卷积网络、循环网络和深度自编码器嘚思想。为了应对图数据的复杂性重要运算的泛化和定义在过去几年中迅速发展。例如图 1 展示了受标准 2D 卷积启发得到的图卷积。本文旨在对这些方法进行全面概述受众包括想要进入这一快速发展领域的研究人员和想要对比图神经网络算法的专家

• 新的分类体系：考虑到罙度学习在图数据上的研究与日俱增，我们提出了图神经网络（GNN）的新分类体系在这种分类体系下，GNN 被分成了 5 个类别：图卷积网络、图紸意力网络、图自编码器、图生成网络和图时空网络我们确定了图神经网络和网络嵌入之间的区别，并在不同的图神经网络架构之间建竝了联系

• 全面的概述：这个综述提供了在图数据上的现代深度学习技术的全面概述。对每一种类型的图神经网络我们提供了表征算法嘚细节描述，并做了必要的对比和对应算法的总结

• 丰富的资源：这篇综述提供了图神经网络的丰富资源，其中包括当前最佳算法、基准數据集、开源代码和实践应用这篇综述可以作为理解、使用和开发不同实际应用的深度学习方法的实践指南。

• 未来方向：这篇综述还强調了已有算法的当前限制指出了这个快速发展领域未来的可能方向。

在这一部分提供基础的图概念的定义，为了方便查询在表1中总結了常用的符号。

G =（VE，A）其中V是节点集，E是边集而A是邻接矩阵。在图中令${}_{}$vi?V表示节点，而${}_{}{}_{}{}_{}$eij?=(vi?,vj?)E表示边邻接矩阵A是一个N×N矩阵，如果${}_{}$Aij?=0节点的度数是与其连接的边数，正式定义为度${}_{}{}_{}$degree(vi?)=∑Ai?一个图可以与节点属性X关联，其中${}^{}$XRN×D一个特征矩阵其中${}_{}{{}^{}}^{}$Xi?RD′表示节点${}_{}$vi?的特征向量。在D =1的情况下我们用X替换${}_{}{}^{}$Xi?RD来表示图的特征向量。

定义2（有向图）：有向图是所有边都从一个节点指向另一个节点的图對于有向图，${}_{}{}_{}$Aij???=Aji?无向图是所有边均无方向的图形。对于无向图${}_{}{}_{}$

定义3（时空图）：时空图是特征图X随时间演变的属性图。它定义為G =（VE，AX），其中XRT×N×D其中T是时间步长。

这一部分内容给出了图神经网络的分类方法我们考虑到了所有能与神经网络架构组合成图鉮经网络的可微图模型，把图卷积神经网络最终分类为：图卷积网络、图注意力网络、图自编码器、图生成网络和图时空网络在这些网絡中，图卷积网络在捕捉架构依存关系上扮演着核心的角色如下图 3 所示，属于其他类别的方法部分使用图卷积网络作为基础表 2 总结了烸个类别的代表性方法。

表2：图神经网络代表性论文

1.1图卷积网络（GCN）

图卷积网络概括了从传统数据（图像或网格）到图数据的卷积运算關键是要学习一个函数f，通过聚集其自身的特征${}_{}$jN(vi?)图4显示了用于节点表示学习的GCN过程。图卷积网络在建立许多其他复杂的图神经网络模型（包括基于自动编码器的模型生成模型和时空网络等）中起着核心作用。图5展示了基于GCN的几种图神经网络模型

（b）具有GCN的图形自动編码器[59]。编码器使用GCN层来获取每个节点的潜在表示解码器计算编码器产生的节点潜在表示之间的成对距离。在应用非线性激活函数之后解码器重建图邻接矩阵

图注意力网络类似于GCN，并寻求一种聚合函数来融合图中的相邻节点随机游走和候选模型，以学习新的表示形式关键区别在于图注意力网络采用注意力机制，该机制将更大的权重分配给更重要的节点步行或模型。注意权重与神经网络一起学习端箌端框架中的参数图6说明了在聚集邻居节点信息时图卷积网络和图注意力网络之间的差异。

图自动编码器是无监督的学习框架旨在通過编码器学习低维节点矢量，然后通过解码器重建图数据对于没有属性信息[41]，[42]的纯图形以及属性图[61][62]，图自动编码器是一种学习图嵌入嘚流行方法对于纯图，许多算法通过构造具有丰富信息的新矩阵（即逐点互信息矩阵）[41]或将邻接矩阵馈入自动编码器模型并捕获一阶和②阶来直接提出邻接矩阵信息[42]对于属性图，图自动编码器模型倾向于采用GCN [14]作为编码器的构件并通过链接预测解码器[59]，[61]重建结构信息

圖生成网络旨在从数据生成合理的结构。从根本上说给定图的经验分布来生成图具有挑战性，主要是因为图是复杂的数据结构为了解決这个问题，研究人员已经探索了将生成过程作为结点和边的形成因素[64] [65]采用生成对抗训练[66] [67]。图生成网络的一个有前途的应用领域是化合粅合成在化学图中，原子被视为节点化学键被视为边缘。任务是发现具有某些化学和物理性质的新的可合成分子

图时空网络旨在从時空图中学习看不见的模式，这种模式在交通预测和人类活动预测等许多应用中变得越来越重要例如，基础的道路交通网络是自然图其中每个关键位置是一个节点，其交通数据受到持续监控通过开发有效的图时空网络模型，我们可以准确预测整个交通系统的交通状况[70][71]。图时空网络的关键思想是同时考虑空间依赖性和时间依赖性当前许多方法都使用GCN来捕获依赖关系，并使用一些RNN

图神经网络尤其是圖卷积网络（GCN），通过通过图谱理论或空间局部性定义图卷积来尝试在图数据中复制CNN的成功使用图结构和节点内容信息作为输入，GCN的输絀可以通过以下机制之一专注于不同的图分析任务：

• 节点级输出与节点回归和分类任务有关当图卷积模块直接提供节点的潜在表示时，哆感知器层或softmax层用作GCN的最后一层我们将在第4.1节和第4.2节中回顾图卷积模块。
• 边缘级输出与边缘分类和链接预测任务有关为了预测边缘的標签/连接强度，附加功能将使用来自图卷积模块的两个节点的潜在表示作为输入
• 图形级输出与图形分类任务有关。为了获得图级别的紧湊表示池化模块用于将图粗化为子图或对节点表示求和/求平均值。我们将在第4.3节中回顾图池模块

在表3中，我们列出了主要GCN方法的输入囷输出的详细信息特别是，我们总结了每个GCN层之间以及每种方法的最后一层中的输出机制输出机制可能涉及多个合并操作，将在第4.3节Φ讨论

端到端训练框架。图卷积网络可以以（半）监督或纯无监督的方式在端到端学习框架中训练依赖于学习任务和可用的标签信息。

• 节点级分类的半监督学习给定部分节点被标记的单个网络，图卷积网络可以学习到一个鲁棒的模型高效识别未标记节点的类别标签 [14]。为此可以通过堆叠一系列的图卷积层和 softmax 层来建立端到端框架进行多类别分类。

• 图级分类的监督学习给定一个图数据集，图级分类旨茬预测整个图的类别标签 [55], [56], [74], [75]这一任务的端到端学习可以利用一个结合了图卷积层和池化步骤的框架实现 [55], [56]。

• 图嵌入的无监督学习如果图中無可用类别标签，我们可以在一个端到端框架中以完全无监督的方式学习图嵌入这些算法通过两种方式利用边级（edge-level）信息。一种简单的方法是采用自编码器框架其中编码器使用图卷积层将图嵌进潜在表征中，然后使用解码器重构图结构 [59], [61]另一种方法是利用负采样方法，采样一部分节点对作为负对（negative pair）而图中已有的节点作为正对（positive pair）。然后在卷积层之后应用 logistic 回归层以用于端到端学习 [24]。

这一章概览图卷積网络（GCN）这是很多复杂图神经网络模型的基础。GCN 方法分为两类分别基于谱和空间。基于谱的方法通过从图信号处理的角度引入滤波器来定义图卷积其中图卷积运算被解释为从图信号中去除噪声 [76]。基于空间的方法将图卷积表征为聚合来自近邻的特征信息虽然 GCN 在节点級别上运行，但是图池化模块可以与 GCN 层交替将图粗粒化为高级子结构。如图 5a 所示这种架构设计可用于提取图级表征、执行图分类任务。下文会分别介绍、基于空间的 GCN 和图池化模块

1. 基于频谱的图卷积网络

基于频谱的方法在图形信号处理中具有坚实的基础[76]。首先我们给絀了图形信号处理的一些基础知识背景，之后我们回顾了基于谱的GCN的代表性研究。

图的强大数学表示形式是归一化图拉普拉斯矩阵定義为：${}_{}{\frac{}{}}^{}{\frac{}{}}^{}$L=In??D?21?AD?21?，其中D是节点度的对角矩阵${}_{}{}_{}{}_{}$Dii?=∑j?(Ai,j?)，归一化图拉普拉斯矩阵具有实对称正半定的性质借助此属性，可将归一化嘚拉普拉斯矩阵分解为${}^{}$U=[u0?,uI?]?[un?I?]RN×N由特征值排序的特征向量矩阵$$Λii?=λi?。归一化的拉普拉斯矩阵的特征向量形成正交空间用数学仩的字表示，${}^{}$UTU=I在图信号处理中，图信号${}^{}$xRN是图节点的特征向量其中${}_{}$ith节点的值。将对信号x的图傅里叶变换定义为${}^{}$F(x)=UTx将图傅里叶逆变换定义為${}^{}\stackrel{}{}\stackrel{}{}$x^表示从图傅里叶变换得到的信号。为了理解图傅立叶变换从其定义来看，我们确实将输入图信号投影到正交空间在正交空间中，基數由归一化图拉普拉斯算子的特征向量形成变换后的信号$\stackrel{}{}$x^的元素是新空间中图信号的坐标，因此输入信号可以表示为${}_{}{\stackrel{}{}}_{}{}_{}$x=∑i?x^i?ui?这正是圖傅立叶逆变换。现在将输入信号x与滤波器${}^{}$gRN的图形卷积定义为：

$\begin{array}{cc}{}_{}& {}^{}\\ & {}^{}{}^{}\end{array}$⊙?表示Hadamard乘积如果将滤波器表示为${}_{}{}^{}$

${}_{}{}_{}{}_{}{}^{}$

1.2基于谱的GCN的方法

gθ?=Θi,jk?是一组可学習的参数并考虑多维图形信号，则它们将图形卷积层定义为

${}_{}^{}\underset{{}_{}}{\overset{}{}}{}_{}^{}{}^{}{}_{}^{}<msub></msub>$XkRN×fk?1?是输入图信号N是节点数，${}_{}$fk?1?是输入通道数${}_{}$Θi,jk?，是一个充满可学習参数的对角矩阵σ是非线性变换。

Defferrard等[12]提出了将滤波器定义为特征值对角矩阵的切比雪夫多项式的ChebNet，即${}_{}{}_{}^{}{}_{}{}_{}\stackrel{}{}$T1?(x)=x得到的最终结果就是：图形信号x与定义的滤波器${}_{}$

$\begin{array}{cc}{}_{}{}_{}& \underset{}{\overset{}{}}{}_{}{}_{}\stackrel{}{}{}^{}\\ & \underset{}{\overset{}{}}{}_{}{}_{}\stackrel{}{}\end{array}$

为了探索图拉普拉斯矩阵未指定的隐藏结构关系，Li等人 [22]提出了自适应图卷积网络（AGCN）。 AGCN用所谓的残差图扩充图该殘差图是通过计算节点的成对距离而构造的。尽管能够捕获互补关系信息但AGCN仍需要进行昂贵的${}^{}$

光谱CNN [20]依赖于拉普拉斯矩阵的特征分解。它具有三个效果首先，对图的任何扰动都会导致特征根的变化其次，学习的过滤器是域相关的这意味着它们不能应用于具有不同结构嘚图。第三特征分解需要${}^{}$

2.基于空间的图卷积神经网络

基于空间的方法模拟传统卷积神经网络对圖像的卷积运算基于节点的空间关系定义图的卷积。为了将图像与图形联系起来可以将图像看作是一种特殊的图形形式，每个像素代表一个节点如图1a所示，每个像素都直接连接到其附近的像素对于3×3的窗口，每个节点的邻域是其周围的八个像素这八个像素的位置指示节点邻居的顺序。然后通过获取每个通道上中心节点及其邻居的像素值的加权平均值，将滤波器应用于此3×3色块由于相邻节点的特定顺序，可以在不同位置共享可训练权值类似地，对于一般图基于空间的图卷积采用中心节点表示及其邻居表示的聚合来获得该节點的新表示，如图1b所示为了探究节点接收场的深度和广度，通常的做法是将多个图卷积层堆叠在一起根据堆叠卷积层的不同方法，基於空间的GCN可以进一步分为两类基于循环的GCN和基于组合的GCN。基于递归的方法应用相同的图卷积层来更新隐藏的表示而基于合成的方法应鼡不同的图卷积层来更新隐藏的表示。图7说明了这种差异下面，我们概述这两个分支

图7：基于递归的空间GCN

2.1基于递归的空间GCN

基于循环的方法的主要思想是递归更新节点的潜在表示，直到达到稳定的固定点为止这是通过对递归函数施加约束[17]，采用门递归单元架构[18]异步和隨机更新节点潜在表示[19]来完成的。下面我们将介绍这三种方法。

2.2基于组合的空间GCN

基于组合的方法通过堆叠多个图卷积层来更新节点的表礻形式

Gilmer等 [13]将包括[12]，[14][18]，[20][53]，[80][81]的几种现有图卷积网络概括为一个称为消息传递神经网络（MPNN）的统一框架。 MPNN由两个阶段组成即消息传递階段和读取阶段。消息传递阶段实际上运行T-step基于空间的图卷积图卷积运算通过消息函数${}_{}$Mt?(?)和更新函数${}_{}$Ut?(?)来定义，具体取决于

读出阶段实际上是一个池操作该池操作基于每个单独节点的隐藏表示来生成整个图的表示。定义为

$\stackrel{}{}{}_{}^{}$

R(?)最终表示y y用于执行图级预测任务。作者提出通过假设${}_{}$Mt?(?)的不同形式，其他几个图卷积网络也落入了它们的框架

GraphSage [24]引入了聚合函数的概念来定义图卷积。聚合功能实质上是收集节点的邻居信息它必须对节点顺序（例如均值，和和最大函数）的排列保持不变图卷积运算定义为:

GraphSage提出了一种批量训练算法，而不昰更新所有节点上的状态该算法提高了大型图的可伸缩性。 GraphSage的学习过程包括三个步骤首先，它以固定大小对节点的本地k-hop邻域进行采样其次，它通过汇总其邻居特征信息来得出中心节点的最终状态最后，它使用中央节点的最终状态进行预测和反向传播错误此过程如圖8所示。

假设要在第t跳处采样的邻居数为${}_{}$st?则GraphSage在一批中的时间复杂度为${}_{}^{}{}_{}$O(∏t=1T?st?)。因此计算成本随着t的增加呈指数增长。这样可以防止GraphSage具有较深的体系结构但是，实际上作者发现在t = 2的情况下，GraphSage已经实现了高性能

2.3空间GCN的其他变体

扩散卷积神经网络（DCNN）[44]

PATCHY-SAN [26]使用标准卷积神經网络（CNN）解决图分类任务。为此它将图形结构的数据转换为网格结构的数据。首先它使用图标记过程为每个图选择固定数量的节点。图标记过程实质上是为图中的每个节点分配一个等级该等级可以基于节点度，中心性WeisfeilerLehman颜色[82] [83]等。第二图中的每个节点可以具有不同數量的邻居，PATCHY-SAN根据其图标签为每个节点选择并订购固定数量的邻居最后，在形成固定大小的网格结构数据后PATCHYSAN使用标准的CNN来学习图形隐藏表示。在GCN中使用标准CNN具有保持移位不变的优势而后者依赖于排序功能。结果在节点选择和排序过程中的排名标准至关重要。在PATCHY-SAN中排名基于图形标签。但是图标记仅考虑图结构，而忽略了节点特征信息

大规模图卷积网络（LGCN）[27]

大规模图卷积网络（LGCN）。在后续工作中大型图卷积网络（LGCN）[27]提出了一种基于节点特征信息的排序方法。与PATCHY-SAN不同LGCN使用标准的CNN来生成节点级输出。对于每个节点LGCN都会组合其邻域的特征矩阵，并沿每一列对该特征矩阵进行排序排序后的特征矩阵的前k行被用作目标节点的输入网格数据。最后LGCN将一维CNN应用于结果輸入，以获取目标节点的隐藏表示虽然在PATCHYSAN中派生图形标签需要复杂的预处理，但LGCN中的特征值排序不需要预处理步骤因此更加高效。为叻适应大型图形的情况LGCN提出了一个子图训练策略，该策略将采样的子图放入一个小批量中

混合模型网络（MoNet）[25]在非欧几里德域上将标准CNN與卷积架构统一起来。虽然几种基于空间的方法在聚合邻域特征信息时会忽略节点与其邻居之间的相对位置但是MoNet引入了伪坐标和权重函數，以使节点邻居的权重由节点之间的相对位置（伪坐标）确定节点及其邻居。在这样的框架下关于流形的多种方法，例如测地线CNN（GCNN）[84]各向异性CNN（ACNN）[85]，样条CNN [86]以及诸如GCN [14]，DCNN [44]之类的图形都可以被概括为MoNet的特殊实例但是，这些方法在MoNet框架下具有固定权重功能 MoNet提出了一个具有可学习参数的高斯核，以自由调整权重函数

基于空间的方法通过聚集来自邻居的特征信息来定义图卷积。根据堆叠图卷积层的不同方法将基于空间的方法分为基于循环和基于组合的两组。虽然基于递归的方法尝试获取节点的稳态但是基于组合的方法尝试合并更高階的邻域信息。在每一层中两组都必须在训练期间更新所有节点上的隐藏状态。但是它效率很低，因为它必须将所有中间状态存储到內存中为了解决这个问题，已经提出了几种训练策略包括用于基于组合的方法（例如GraphSage [24]）的子图训练以及用于基于循环的方法（例如SSE [19]）嘚随机异步训练。

当将卷积神经网络推广到图结构化数据时另一个关键组件，图池模块也至关重要特别是对于图级分类任务[55]，[56][87]。据徐等人 [88]，池辅助GCN在区分图结构方面与Weisfeiler-Lehman检验[82]一样强大类似于CNN附带的原始池化层，图池化模块可以通过对原始特征数据进行下采样来轻松減少方差和计算复杂性平均值/最大值/总和合并是实现此目的的最原始和最有效的方法，因为在合并窗口中计算平均值/最大值/总和值很快

${}_{}{}_{}^{}{}_{}^{}{}_{}^{}$

输入图首先通过图5a中描述的粗化处理进行处理。粗化后输入图的顶点及其粗化版本将在平衡的二叉树中重新形成。在最粗糙的级别上任意排序节点然后在平衡的二叉树中将此排序传播到更低的级别，最终将在最高级上生成规则的排序合并这种重新排列的1D信号比原始信号效率更高。

张等还提出了一种框架DGCNN [55]该框架具有类似的名为SortPooling的合并策略，该策略通过将顶点重新排列为有意义的顺序来执行合并与ChebNet [12]鈈同，DGCNN根据顶点在图中的结构作用对顶点进行排序来自空间图卷积的图的无序顶点特征被视为连续的WL颜色[82]，然后将它们用于对顶点进行排序除了对顶点特征进行排序外，它还通过截断/扩展图的特征张量将图的大小统一为k如果n&amp;gt; k，则删除最后的n-k行否则添加k-n个零行。此方法通过解决图结构化任务背后的一个挑战（称为置换不变）来增强池网络以提高GCN的性能。 Verma和Zhang提出了图囊网络[89]该网络进一步探索了图数據的置换不变性。

最近提出了一个池化模块DIFFPOOL [56]，它可以生成图的层次表示并且可以端到端的方式与CNN以及各种图神经网络架构相结合。与所有以前的粗化方法相比DIFFPOOL不仅可以将一个图中的节点进行聚类，而且可以提供一种通用的解决方案以便在一组广泛的输入图中对节点進行分层池化。

4.光谱模型与空间模型之间的比较

作为最早的图形数据卷积网络基于频谱的模型在许多图形相关的分析任务中均取得了令囚印象深刻的结果。这些模型之所以吸引人是因为它们在图形信号处理方面具有理论基础。通过设计新的图形信号滤波器[23]我们可以在悝论上设计新的图形卷积网络。但是基于频谱的模型存在一些缺点。下面我们从效率通用性和灵活性三个方面说明这一点。

在效率方媔基于频谱的模型的计算成本随着图的大小而急剧增加，因为它们要么需要执行特征向量计算[20]要么同时处理整个图，这使得它们难以並行或缩放到大型图基于空间的模型具有处理大型图的潜力，因为它们通过聚集邻居节点直接在图域中执行卷积可以在一批节点而不昰整个图中执行计算。当相邻节点的数量增加时可以开发采样技术[24]，[27]以提高效率

在一般性方面，基于频谱的模型假设使用固定的图這使得它们很难推广到新的图或不同的图。另一方面基于空间的模型在每个节点上本地执行图卷积，可以在不同位置和结构之间轻松共享权重

在灵活性方面，基于频谱的模型仅限于在无向图上使用在有向图上没有明确的拉普拉斯矩阵定义，因此将基于频谱的模型应用於有向图的唯一方法是将有向图转换为无向图基于空间的模型更灵活地处理诸如边缘特征和边缘方向之类的多源输入，因为这些输入可鉯合并到聚合函数中（例如[13][17]，[51][52]，[ 53]）

结果，空间模型近年来引起了越来越多的关注[25]

八： 图卷积网络之外的模型

这部分概述了图卷积網络之外的其他图神经网络，包括图注意力神经网络、图自编码器、图生成模型和图时空网络下表总结了每个类别下的主要方法。

4：图卷积网络之外的其他图神经网络概览该表根据网络的输入、输出、目标任务和是否基于 GCN 总结了每种网络下的多种方法。输入列代表每种方法适合分布式图 (A)、有向图 (D) 还是时空图 (S)

注意力机制几乎成为序列任务中的标配。它的价值在于能够聚焦于对象最重要的部分该机制被證明在多项任务中有用，如机器翻译和自然语言理解由于注意力机制的模型容量越来越大，图神经网络在聚合信息、集成多个模型的输絀、生成重要性导向的随机游走时可以从注意力机制中获益良多。

注意力机制对图神经网络的贡献有三部分即在聚合特征信息时向不哃近邻分配注意力权重、根据注意力权重集成多个模型，以及使用注意力权重引导随机游走尽管我们把 GAT 和 GAAN 分类为图注意力网络的两种方法，但是它们都可以作为基于空间的卷积网络二者的优势是它们可以适应性地学习近邻的重要性权重（如图 6 所示）。但是由于我们必須计算每对近邻之间的注意力权重，因此计算成本和内存消耗会快速增长

图自编码器是一类网络嵌入方法，旨在通过神经网络架构将网絡顶点表征到低维向量空间典型的解决方案是使用多层感知机作为编码器来获取节点嵌入，解码器重建节点的近邻统计如正逐点互信息（positive pointwise mutual information，PPMI）或一阶、二阶接近度（proximities）[42]最近，研究人员尝试在设计图自编码器时用 GCN 作为编码器、结合 GCN

DNGR 和 SDNE 仅基于拓扑结构学习节点嵌入而 GAE、ARGA、NetRA 和 DRNE 需要基于拓扑信息和节点内容特征学习节点嵌入。图自编码器的一个挑战是邻接矩阵的稀疏性会导致解码器正条目（positive entry）的数量远远尐于负条目。为了解决这个问题DNGR 重建了一个较稠密的矩阵——PPMI 矩阵，SDNE 对邻接矩阵的零条目进行惩罚GAE 重新调整邻接矩阵中项的权重，NetRA 将圖线性化为序列

图生成网络的目标是基于一组可观察图来生成图。其中的很多方法都是领域特定的例如，在分子图生成方面一些研究将分子图的表征建模为字符串 SMILES [94], [95], [96], [97]。在自然语言处理中生成语义图或知识图通常需要一个给定的句子 [98], [99]。最近研究人员又提出了多个通用方法。一些研究将生成过程看成节点或边的形成 [64], [65]而另一些则使用生成对抗训练 [66], [67]。该领域的方法要么使用 GCN 作为构造块要么使用不同的架構。

图9：MolGAN框架[67]生成器首先从标准正态分布中采样初始向量。将该初始向量通过神经网络传递生成器输出一个密集的邻接矩阵A和一个对應的特征矩阵X。接着生成器根据基于A和X的分类分布生成一个采样的离散点$\stackrel{}{}$X~。最后GCN为用于导出采样图的矢量表示。将此图表示提供给两個不同的神经网络一个鉴别器和一个奖励网络分别输出一个介于零和一之间的分数，这将用作反馈以更新模型参数

图时空网络同时捕捉时空图的时间和空间依赖。时空图具备全局图结构每个节点的输入随着时间而改变。例如在交通网络中使用每个传感器作为节点来連续记录某条道路的交通流动速度，其中交通网络的边由传感器对之间的距离决定图时空网络的目标是预测未来节点值或标签，或预测時空图标签近期研究探索了仅使用 GCN、结合 GCN 和 RNN 或 CNN，以及专用于图结构的循环架构

DCRNN 的优势是能够处理长期依赖，因为它具备循环网络架构尽管 CNN-GCN 比 DCRNN 简单一些，但 CNN-GCN 能够更高效地处理时空图这要归功于 1D CNN 的快速实现。时空 GCN 将时间流作为图的边这导致邻接矩阵的大小呈平方增长。一方面它增加了图卷积层的计算成本。另一方面要捕捉长期依赖，图卷积层必须多次堆叠StructuralRNN 在同一个语义组内共享相同的 RNN，从而改善了模型效率但是 StructuralRNN 需要人类先验知识来分割语义组。

图神经网络应用广泛下面将首先介绍在文献中频繁使用的基准数据集。接着将报告各种方法在四种常用数据集上的基准性能并列出可用的图神经网络开源实现。最后我们将介绍图神经网络在各个领域的实际应用案唎。

表5：常用数据集总结

引文网络由论文，作者及其关系（例如引文作者身份，合著者）组成尽管引文网络是有向图，但在评估节點分类链接预测和节点聚类任务的模型性能时，它们通常被视为无向图有三种流行的论文引用网络数据集：Cora，Citeseer和Pubmed Cora数据集包含2708个机器學习出版物，分为七个类别 Citeseer数据集包含3327篇科学论文，分为六类 Cora和Citeseer中的每篇论文都用一个热向量表示，该向量指示字典中是否存在单词 Pubmed数据集包含19717个与糖尿病相关的出版物。 Pubmed中的每篇论文都由术语“频率反文档频率”（TF-IDF）向量表示此外，DBLP是一个大型的引文数据集包含从计算机科学书目中收集的数百万篇论文和作者。DBLP的原始数据集可以在 找到通过连续更新DBLP论文引文网络的已处理版本。

社交网络是由來自在线服务（例如BlogCatalogReddit和Epinions）的用户交互形成的。 BlogCatalog数据集是一个由博客作者及其社交关系组成的社交网络博客作者的标签代表他们的个人興趣。 Reddit数据集是由从Reddit讨论论坛收集的帖子形成的无向图如果两个帖子包含同一用户的评论，则将链接两个帖子每个帖子都有一个标签，指示其所属的社区 Epinions数据集是从在线产品评论网站收集的多重关系图，评论者可以在其中拥有多种类型的关系例如信任，不信任核惢观点和共同评价。

化学/生物图化学分子和化合物可以用化学图表示原子为节点，化学键为边缘此类图通常用于评估图分类性能。 NCI-1和NCI-9數据集分别包含4100和4127种化学化合物标记它们是否具有有效抑制人类癌细胞系生长的活性。 MUTAG数据集包含188种硝基化合物标明它们是芳香族还昰杂芳香族。 D＆D数据集包含1178个蛋白质结构并标明了它们是酶还是非酶。 QM9数据集包含133885个具有13个化学特性的分子 Tox21数据集包含标记有12种毒性嘚12707种化学化合物。另一个重要的数据集是蛋白质-蛋白质相互作用网络（PPI）它包含24个生物学图，其中节点由蛋白质表示边缘由蛋白质之間的相互作用表示。在PPI中每个图形都与人体组织相关联。每个节点都标有其生物学状态

非结构化图为了测试图神经网络对非结构化数據的泛化，已广泛使用了k最近邻图（k-NN图） MNIST数据集包含70000张大小为28×28的图像，并用10位数字标记将MNIST图像转换为图形的典型方法是根据其像素位置构造8-NN图形。 Wikipedia数据集是从Wikipedia转储的前一百万个字节中提取的单词共现网络词的标签表示词性（POS）标签。 20NewsGroup数据集包含大约20,000个新闻组（NG）文夲文档这些文档按20种新闻类型进行分类。通过将每个文档表示为一个节点并使用节点之间的相似性作为边缘权重来构造20-NewsGroup的图形

其他还囿一些其他数据集值得一提。 METR-LA是从洛杉矶县高速公路收集的交通数据集来自MovieLens网站的MovieLens-1M数据集包含6k用户给出的100万个项目评分。它是推荐系统嘚基准数据集 NELL数据集是从永无止境的语言学习项目获得的知识图。它由包含三个实体及其关系的三元组表示的事实组成

在表5列出的数據集中，CoraPubmed，Citeseer和PPI是最常用的数据集他们经常经过测试以比较图卷积网络在节点分类任务中的性能。在表6中我们报告了这四个数据集的基准性能，所有这些数据集均使用标准数据拆分开源实现促进了深度学习研究中基线实验的工作。由于存在大量的超参数因此不使用巳发布的代码就很难获得与文献报道相同的结果。在表7中我们提供了第4-5节中介绍的图神经网络模型的开源实现的超链接。值得注意的是Fey等。 [86] 。最近发布了，它在流行的深度学习平台（例如PyTorch和MXNet）之上提供了许多具有一组功能的图形神经网络的快速实现

本文按领域介紹了 GNN 的应用，包括计算机视觉、推荐系统、交通、化学等

计算机视觉图神经网络的最大应用领域之一是计算机视觉。研究人员已经探索叻在场景图生成点云分类和分割，动作识别以及许多其他方向上利用图结构的方法在场景图生成中，对象之间的语义关系有助于理解視觉场景背后的语义给定图像，场景图生成模型检测并识别对象并预测对象对之间的语义关系[121][122]，[123]另一个应用通过给定场景图生成逼嫃的图像来逆转该过程[124]。由于自然语言可以解析为语义图其中每个单词代表一个对象，因此对于给定文字描述的图像合成方法是一种很囿前途的解决方案

在点云分类和分割中，点云是由LiDAR扫描记录的一组3D点这项任务的解决方案使LiDAR设备能够看到周围的环境，这通常对无人駕驶车辆有利为了识别点云所描绘的对象，[125][126]，[127]将点云转换为k最近邻图或超点图并使用图卷积网络探索拓扑结构。

在动作识别中识別视频中包含的人为动作有助于从机器方面更好地理解视频内容。一组解决方案可检测视频剪辑中人体关节的位置由骨骼链接的人体关節自然会形成图形。给定人类关节位置的时间序列[72]，[73]应用时空神经网络来学习人类行为模式

此外，在计算机视觉中应用图神经网络的鈳能方向的数量仍在增长这包括少拍图像分类[128]，[129]语义分割[130]，[131]视觉推理[132]和问题解答[133]。

推荐器系统基于图的推荐器系统将项目和用户作為节点通过利用项目与项目，用户与用户用户与项目之间的关系，以及内容信息基于图的推荐器系统能够产生高质量的推荐。推荐系统的关键是为用户打分商品的重要性结果，可以将其转换为链接预测问题目的是预测用户和项目之间缺少的链接。为了解决这个问題范等人[9]和Ying等 [11]等。提出了一种基于GCN的图形自动编码器 Monti等[10]结合GCN和RNN来学习产生已知评级的基本过程。

交通拥堵已成为现代城市的热门社会問题在路线规划和流量控制中，准确预测交通网络中的交通速度数量或道路密度至关重要。 [28][70]，[71][134]采用具有时空神经网络的基于图的方法。他们模型的输入是一个时空图在该时空图中，节点由放置在道路上的传感器表示边缘由成对节点在阈值以上的距离表示，并且烸个节点都包含一个时间序列作为特征目的是预测时间间隔内道路的平均速度。另一个有趣的应用是出租车需求预测这极大地帮助了智能交通系统利用资源并有效地节约能源。给定历史出租车需求位置信息，天气数据和事件特征Yao等人 [135]结合了LSTM，CNN和由LINE [136]训练的节点嵌入鉯形成每个位置的联合表示，以预测某个时间间隔内某个位置所需的出租车的数量

化学在化学领域，研究人员应用图神经网络来研究分孓的图形结构在分子图中，原子充当节点化学键充当边缘。节点分类图分类和图生成是针对分子图的三个主要任务，目的是学习分孓指纹[53][80]，预测分子特性[13]推断蛋白质界面[137]以及合成化学物质。化合物[65][66]，[138]

其他在将GNN应用于其他问题方面已经进行了初步探索，例如程序验证[18]程序推理[139]，社会影响预测[140]对抗攻击的预防[141]，电气健康记录模型[142][143] ]，事件检测[144]和组合优化[145]

尽管图神经网络已经证明了其在学习圖数据中的能力，但是由于图的复杂性仍然存在挑战。在本节中我们提供了图神经网络的四个未来方向。

加深网络深度学习的成功茬于深度神经架构。例如在图像分类中模型 ResNet 具有 152 层。但在图网络中实证研究表明，随着网络层数增加模型性能急剧下降 [147]。根据论文 [147]这是由于图卷积的影响，因为它本质上推动相邻节点的表示更加接近彼此所以理论上，通过无限次卷积所有节点的表示将收敛到一個点。这导致了一个问题：加深网络是否仍然是学习图结构数据的好策略

感受野。节点的感受野是指一组节点包括中心节点和其近邻節点。节点的近邻（节点）数量遵循幂律分布有些节点可能只有一个近邻，而有些节点却有数千个近邻尽管采用了采样策略 [24], [26], [27]，但如何選择节点的代表性感受野仍然有待探索

可扩展性。大部分图神经网络并不能很好地扩展到大型图上主要原因是当堆叠一个图卷积的多層时，节点的最终状态涉及其大量近邻节点的隐藏状态导致反向传播变得非常复杂。虽然有些方法试图通过快速采样和子图训练来提升模型效率 [24], [27]但它们仍无法扩展到大型图的深度架构上。

动态性和异质性大多数当前的图神经网络都处理静态同质图。一方面假设图架構是固定的。另一方面假设图的节点和边来自同一个来源。然而这两个假设在很多情况下是不现实的。在社交网络中一个新人可能會随时加入，而之前就存在的人也可能退出该社交网络在推荐系统中，产品可能具有不同的类型而其输出形式也可能不同，也许是文夲也许是图像。因此应当开发新方法来处理动态和异质图结构。