第十一章：GCN——图卷积神经网络：全面回顾

0.摘要

        图在许多应用领域中自然出现，包括社交分析、生物信息学和计算机视觉。图的独特能力使其能够捕捉数据之间的结构关系，从而可以比单独分析数据获得更多的见解。然而，在图上解决学习问题往往非常具有挑战性，因为

        (1)许多类型的数据最初并不是以图的形式存在，比如图像和文本数据，

        (2)对于图结构化数据，底层的连接模式通常复杂且多样化。

        另一方面，表示学习在许多领域取得了巨大成功。因此，一个潜在的解决方案是在低维欧几里德空间中学习图的表示，以保留图的特性。尽管在解决图表示学习问题方面已经做出了巨大努力，但其中许多方法仍然受限于其浅层学习机制。在机器学习和其他相关领域中，基于图的深度学习模型（如图神经网络）近年来出现并在各种问题中展现出优越的性能。在这项调查中，尽管有许多类型的图神经网络，我们专门对最具代表性的图卷积网络这一新兴领域进行了全面回顾。首先，我们根据卷积类型将现有的图卷积网络模型分为两类，并详细介绍了一些图卷积网络模型。然后，我们根据应用领域对不同的图卷积网络进行分类。最后，我们提出了该领域的几个开放挑战，并讨论了未来研究的潜在方向。

关键词：图卷积网络、图表示学习、深度学习、谱方法、空间方法、聚合机制。

1.引言

        图在许多现实世界的应用中自然而然地出现，包括社交分析[1]、欺诈检测[2,3]、交通预测[4]、计算机视觉[5]等等。通过将数据表示为图，可以将结构信息编码以建模实体间的关系，并提供更有前景的数据洞察。例如，在交通网络中，节点通常是传感器，边表示传感器之间的空间接近性。除了传感器本身提供的时间信息外，通过空间相关性建模的图结构在交通预测问题中显著改善了结果[4]。此外，通过将人们之间的交易建模为图，可以挖掘复杂的交易模式，用于合成身份检测[3]和洗钱检测[6]等领域。

        然而，图的复杂结构[7]常常限制了获得图背后真正见解的能力。这种复杂性，例如，存在于图结构数据的非欧几里德性质中。解决复杂模式的一个潜在方法是通过嵌入技术在低维欧几里德空间中学习图表示，包括传统的图嵌入方法[8-10]和最近的网络嵌入方法[11,12]。一旦学习到低维表示，许多与图相关的问题就可以很容易地解决，例如经典的节点分类和链接预测[12]。已经有许多对传统图嵌入和最近的网络嵌入方法进行了全面的综述。例如，Yan等人对几种成熟的传统图嵌入方法进行了综述，并讨论了图维度降低的一般框架[13]。Hamilton等人综述了一般的图表示学习方法，包括节点嵌入和子图嵌入[14]。此外，Cui等人讨论了传统图嵌入和最近的网络嵌入方法之间的差异[15]。一个显著的区别是，最近的网络嵌入更适用于任务特定的网络推断。关于网络嵌入的其他现有文献综述包括[16,17]。

        尽管这些嵌入方法取得了一些成功，但其中许多方法受到浅层学习机制的限制[11,12]，可能无法发现图背后更复杂的模式。另一方面，深度学习模型在许多应用中展示了其强大的能力。例如，卷积神经网络（CNN）在许多计算机视觉[18]和自然语言处理[19]应用中取得了令人期待的性能。这样成功的一个关键原因是CNN模型能够高度利用某些类型数据的平稳性和组合性特性。特别是由于图像的网格状特性，CNN中的卷积层能够利用层次化的模式并提取图像的高级特征，从而获得很强的表达能力。基本的CNN模型旨在学习一组固定大小的可训练局部滤波器，这些滤波器扫描图像中的每个像素并结合周围像素。核心组件包括卷积和池化层，可以在具有欧几里德或网格状结构的数据上进行操作。

        然而，图的非欧几里德特性（例如，不规则的结构）使得在图上进行卷积和滤波不像在图像上那样定义明确。在过去几十年中，研究人员一直致力于如何在图上进行卷积操作。一个主要的研究方向是从频谱的角度定义图卷积，因此，图信号处理，如图滤波和图小波变换，引起了很多研究兴趣。Shuman等人全面概述了图信号处理，包括对图的常见操作和分析[20]。简而言之，谱图卷积是在频谱域中基于图傅里叶变换进行定义的，类似于一维信号的傅里叶变换。通过这种方式，基于谱的图卷积可以通过对两个傅里叶变换后的图信号进行乘法运算的逆傅里叶变换来计算。另一方面，图卷积也可以在空间域（即顶点域）中定义为从节点邻域聚合节点表示。这些操作的出现为图卷积网络打开了一扇门。一般来说，图卷积网络模型是一种可以利用图结构并以卷积方式聚合邻域中的节点信息的神经网络架构。图卷积网络具有很强的表达能力，可以学习图的表示，并在各种任务和应用中取得优越的性能。需要注意的是，在过去几年中，还提出了许多其他类型的图神经网络，包括（但不限于）：

        （1）图自编码器[21]，

        （2）图生成模型[22,23]，

        （3）图注意模型[24,25]和

        （4）图循环神经网络[26,27]。

        关于图神经网络的主题还有其他几篇相关的调研报告。Bronstein等人回顾了地理深度学习在图和流形上的数学细节和一些早期方法[28]。张等人详细回顾了许多超出图卷积网络范围的现有图神经网络，如图注意网络和门控图神经网络[29]。此外，吴等人还回顾了关于图生成模型和时空网络的神经网络研究[30]。此外，Lee等人重点介绍了图注意网络的图神经网络概述[31]。然而，由于图卷积网络是一个非常热门且快速发展的研究领域，这些现有的调研报告可能无法涵盖最新的模型。在本次调研报告中，我们专注于回顾图卷积网络的现有文献，并涵盖最新的进展。本次调研报告的主要贡献总结如下：

1. 我们引入了两个分类法来对现有的图卷积网络模型进行分组（图1）。首先，根据卷积的类型，我们将图卷积网络分为基于谱的模型和基于空间的模型。然后，我们介绍了几种根据应用领域分类的图卷积网络。
2. 通过调查和讨论最新的图卷积网络模型，我们为每个分类法提供了动机。
3. 我们讨论了当前模型面临的挑战，并强调了未来工作的一些有前景的方向。

        文章的剩余部分按照以下方式组织。我们首先在“符号和预备知识”部分总结符号并介绍图卷积网络的一些基础知识。然后，在“谱图卷积网络”和“空间图卷积网络”部分，我们通过图滤波的类型将现有的模型分为基于谱的方法和基于空间的方法，并给出一些详细的例子。在“图卷积网络的应用”部分，我们从应用的视角介绍了一些方法。在“挑战和未来研究”部分，我们讨论了现有图卷积网络模型面临的一些挑战，并提供了一些未来工作的方向。最后，在“总结和展望”部分，我们对调研进行总结。

图1：图卷积网络概述

 符号和预备知识

        在本节中，我们介绍图卷积网络的符号和一些预备知识。通常情况下，我们使用粗体大写字母表示矩阵，粗体小写字母表示向量，小写字母表示标量。对于矩阵索引，我们使用A(i,j)表示第i行和第j列的元素。我们用AT表示矩阵A的转置。

图和图信号

        在这个调研中，我们对无向连通图G={V,E,A}上的图卷积网络模型感兴趣，其中V是节点的集合，|V|=n，E是边的集合，|E|=m，A是邻接矩阵。如果节点i和节点j之间存在一条边，那么A(i,j)表示边的权重；否则，A(i,j)=0。对于无权图，我们简单地将A(i,j)设置为1。我们将A的度矩阵表示为对角矩阵D，其中D(i,i)=∑_{j=1}^n A(i,j)。然后，A的拉普拉斯矩阵被表示为L=D-A。对应的对称归一化拉普拉斯矩阵是L˜=I-D^(-1/2)AD^(-1/2)，其中I是单位矩阵。在节点上定义的图信号表示为向量x∈R^n，其中x(i)是节点i上的信号值[20]。例如，节点属性可以被视为图信号。将X∈R^n×d表示为带属性图的节点属性矩阵，X的列是图的d个信号。

图傅里叶变换

        众所周知，一维信号f的经典傅里叶变换计算公式为fˆ(ξ)=∫f(t)e^(2πiξt)dt，其中ξ是fˆ在频谱域中的频率，而复数指数是拉普拉斯算子的特征函数。类似地，图拉普拉斯矩阵L是在图上定义的拉普拉斯算子。因此，与其相应的特征值相关的特征向量类似于某个频率上的复数指数。注意，对称归一化拉普拉斯矩阵L˜和随机游走转移矩阵也可以用作图拉普拉斯算子。特别地，将L˜的特征值分解表示为L˜=UΛU^T，其中U的第l列是特征向量ul，Λ(l,l)是相应的特征值λl，然后我们可以计算图信号x的傅里叶变换如下：上述方程在频谱域中表示了在顶点域中定义的图信号。然后，逆图傅里叶变换可以表示为：x(i) = (∑_{l=1}^n xˆ(λl)ul(i)) / √n，其中xˆ(λl)是x在频谱域中的系数，ul(i)是特征向量ul在节点i上的值。

图滤波

        图滤波是对图信号进行局部操作的一种方法。类似于在时域或频谱域中对经典信号进行滤波，可以将图信号在其顶点域或频谱域中进行局部化操作。

        (1)频率滤波：回顾一下，经典信号的频率滤波通常表示为在时域中与滤波信号的卷积。然而，由于图的不规则结构（例如，不同节点具有不同数量的邻居），在顶点域中的图卷积不像时域中的经典信号卷积那样直观。需要注意的是，对于经典信号，时域中的卷积等价于两个信号在频谱表示上的乘法的逆傅里叶变换。因此，频谱图卷积的定义类似于：需要注意的是，xˆ(λl)yˆ(λl)表示频谱域中的滤波操作。因此，图G上信号x的频率滤波与方程(3)完全相同，并进一步重写为：

        (2)顶点滤波：在顶点域中，信号x的图滤波通常定义为节点邻域中信号分量的线性组合。数学上，节点i处的信号x的顶点滤波为：其中N(i,K)表示图中节点i的K跳邻域，参数{wi,j}是用于组合的权重。可以证明，使用K次多项式滤波器，可以从顶点滤波的角度解释频率滤波[20]。

谱图卷积网络

        在本节和后续的“空间图卷积网络”一节中，我们将图卷积神经网络分为基于谱的方法和基于空间的方法。我们认为基于谱的方法是从构建频率滤波开始的方法。

        第一个显著的基于谱的图卷积网络是由Bruna等人提出的[32]。受经典CNN的启发，这个在图上的深度模型包含几个谱卷积层，它们将大小为n × dp的向量Xp作为第p层的输入特征图，并通过以下方式输出大小为n × dp+1的特征图Xp+1：其中Xp(:,i)(Xp+1(:,j))分别是输入特征图（输出特征图）的第i（j）维，θp i,j表示第p层滤波器的可学习参数向量。V的每一列都是L的特征向量，σ(·)是激活函数。然而，这种卷积结构存在几个问题。

        首先，特征向量矩阵V需要显式计算图拉普拉斯矩阵的特征值分解，因此时间复杂度为O(n^3)，对于大规模图来说是不可行的。

        其次，虽然特征向量可以预先计算，但是方程(6)的时间复杂度仍然为O(n^2)。

        第三，每一层中有O(n)个要学习的参数。

        此外，这些非参数化滤波器在顶点域中不是局部化的。为了克服这些限制，作者还提出使用特征值分解的秩-r近似。具体而言，他们使用V的前r个特征向量，这些特征向量携带了图的最平滑的几何性质，并因此将每个滤波器的参数数量减少到O(1)。此外，如果图包含可以通过这种秩-r分解来探索的聚类结构，滤波器有可能是局部化的。基于[32]，Henaff等人提出应用输入平滑核（例如，样条函数）并使用相应的插值权重作为图谱卷积的滤波器参数[33]。如[33]所述，顶点域中的空间局部化可以在一定程度上实现。然而，计算复杂度和局部化能力仍然阻碍了对图的更好表示的学习。

        为了解决这些限制，Defferrard等人提出了ChebNet，它在卷积层中使用了K次多项式滤波器来实现局部化[34]。这样一个K次多项式滤波器可以表示为yˆ(l)=∑ K k=1 θk * ψk(l)。如“符号和预备知识”部分所述，K次多项式滤波器通过在K跳邻域内整合节点特征来实现在顶点域中的良好局部化[20]，且可训练参数的数量减少到O(K)=O(1)。此外，为了进一步减少计算复杂度，Chebyshev多项式逼近[35]被用于计算谱图卷积。数学上，k阶Chebyshev多项式Tk(x)可以通过Tk(x)=2xTk−1(x)−Tk−2(x)的递归计算得到，其中T0 =1，T1(x)=x。Defferrard等人通过将滤波器归一化为˜l =2 max l −1，使得缩放后的特征值位于[-1,1]之间。因此，卷积层的计算方式为：Xp+1(:,j)=σ∑ K k=0 θp i,j(k +1)Tk(L˜)Xp(:,i),∀j =1,...,dp+1。（7）其中，θp i,j是第-p层输入特征图的第i列和第j列输出特征图的一个K维参数向量。

        作者还设计了一种使用多级聚类方法Graclus [36]的最大池化操作，这种方法非常有效地揭示了图的分层结构。作为一种特殊变体，Kipf等人提出的图卷积网络（称为GCN）旨在对图上的半监督节点分类任务进行建模[37]。在这个模型中，作者将Chebyshev多项式截断为一阶（即在方程（7）中取K = 2），并特别设定(θ)i,j(1)=−(θ)i,j(2)=θi,j。此外，由于L˜的特征值位于[0,2]之间，放宽max = 2仍然保证−1 ≤ ˜l ≤ 1，∀l = 1,···,n。这导致简化后的卷积层形式为：其中A˜=I +A相当于在原始图上添加自环，D˜是A˜的对角度矩阵，而p是一个dp+1 × dp的参数矩阵。

        此外，方程（8）与Weisfeiler-Lehman同构性检验[38]有密切关系。由于方程（8）本质上等同于从直接邻域聚合节点表示，GCN具有明确的顶点定位意义，因此经常被认为是将基于谱的方法与基于空间的方法之间的桥梁。然而，对于大规模图，训练过程可能在内存方面代价高昂。此外，GCN的传导干扰了泛化过程，使得在同一图中学习未见节点的表示以及在完全不同的图中的节点更加困难[37]。为了解决GCN [37]的问题，FastGCN [39]通过实现高效的小批量训练来改进原始的GCN模型。

        首先，它假设输入图G是可能无限图G'的诱导子图，使得图G的节点V是在某种概率测度P下的图G'的节点V'的独立同分布样本。这样，通过蒙特卡洛采样，可以近似表示方程（8）所代表的原始卷积层。假设在第p层有一些独立同分布的样本u^1,...,u^t_p，可以通过以下方式估计图卷积：注意，这种蒙特卡洛估计器可能导致估计的方差很高。为了减少方差，作者提出了一个重要性采样分布P的方差，并为节点的重要性采样分布P进行求解。此外，Chen等人开发了基于控制变量的算法来近似GCN模型[37]，并提出了一种用于训练的高效的基于采样的随机算法[40]。此外，作者在训练阶段理论上证明了算法的收敛性，不受采样大小的影响[40]。

        最近，Huang等人在GCN模型中开发了一种自适应的逐层采样方法来加速训练过程[41]。他们首先以自顶向下的方式构建图卷积网络中的层，然后提出了一种逐层采样器，以避免由于固定大小的采样而导致邻域的过度扩展。为了进一步减少方差，推导出了显式的重要性采样。除了基于切比雪夫多项式逼近的模型之外，还提出了其他基于局部多项式滤波器及其对应的图卷积网络模型。例如，Levie等人提出使用一种更复杂的逼近方法，即Cayley多项式，来逼近滤波器[42]。所提出的CayleyNet模型的动机是，由于Chebyshev多项式中使用的拉普拉斯矩阵的特征值被缩放到区间[-1,1]，狭窄的频带（即围绕某一频率集中的特征值）很难被检测到。鉴于这种狭窄频带的特性经常出现在社区结构图中，ChebNet在更广泛的图挖掘问题上具有有限的灵活性和性能。具体而言，Cayley滤波器的阶为K，具有以下形式：其中c = [c0,···,cK]是待学习的参数，h > 0是用于扩展图谱的频谱缩放参数，使得Cayley滤波器可以专门使用不同的频率带。进一步使用Jacobi逼近可以实现局部性质和线性复杂度[42]。此外，LanczosNet [43]提出了一种自然地编码图中多尺度特征，并且突破了大多数现有模型中涉及指数化的图拉普拉斯算子以捕捉多尺度信息（例如[34]）的计算瓶颈。具体而言，作者首先通过Lanczos算法计算矩阵A˜的低秩逼近，使得A˜≈VRVT，其中V = QB，Q ∈ Rn×K 包含前K个Lanczos向量，BRBT是一个三对角矩阵T的特征分解。通过这种方式，A˜的t次幂可以简单地近似为A˜t ≈ VRtVT。在此基础上，LanczosNet中提出的谱滤波器的公式为：其中Rˆ(k)=fk([R0,...,RK−1])是一个对角矩阵，fk是一个多层感知器（MLP）。

        为了利用多尺度信息，上述谱滤波器通过添加短尺度参数和长尺度参数进行修改。[43]中还提出了一种用于节点表示学习的变种。除了基于傅里叶变换的谱滤波器，Xu等人提出在图上使用谱小波变换，以便捕捉不同尺度的图[44]。此外，由于许多图结构是基于数据点之间的相似性手动构建的（例如，kNN图），这些固定的图可能对某些特定任务的学习能力不是最佳的。为此，Li等人提出了一种可以同时学习图拉普拉斯矩阵的谱图卷积层[45]。具体而言，该谱图卷积层不直接参数化滤波器系数，而是通过引入残差拉普拉斯的概念，在图拉普拉斯矩阵上参数化一个函数。然而，该方法的主要缺点是不可避免的O(n2)复杂度。

空间图卷积网络

        由于谱图卷积依赖于拉普拉斯矩阵的特定特征函数，因此将在一个特定图上学习的基于谱的图卷积网络模型转移到具有不同特征函数的另一个图上仍然是非平凡的。另一方面，根据顶点域中的图滤波（即Eq.(5)），图卷积可以通过节点邻域内的图信号的某些聚合进行替代性地泛化。在本节中，我们将空间图卷积网络分为经典的基于CNN的模型、基于传播的模型以及其他相关的通用框架。

经典基于CNN的空间图卷积网络

        对于类似于网格的数据，如图像，经典的CNN模型在许多相关应用中取得了巨大的成功，包括图像分类[46-48]、目标检测[18,49]、语义分割[50,51]等。卷积结构利用的基本网格数据属性包括：

        （1）每个像素的相邻像素数量是固定的，

        （2）扫描图像的空间顺序自然确定，即从左到右，从上到下。

        然而，与图像不同的是，在任意图数据中，相邻单元的数量和它们之间的空间顺序都不是固定的。为了解决这些问题，许多研究提出了直接在经典CNN上构建图卷积网络的方法。Niepert等人提出通过从图中提取局部连接区域来解决上述挑战[52]。提出的PATCHY-SAN模型首先通过给定的图标记方法（如基于中心性的方法，如度、PageRank、介数等）确定节点的排序，并选择一个固定长度的节点序列。其次，为了解决节点的任意邻域大小问题，为每个节点构建一个固定大小的邻域。最后，根据图标记过程对邻域图进行归一化，以便将具有相似结构角色的节点分配相似的相对位置，然后使用经典CNN进行表示学习。然而，由于节点的空间顺序是由给定的图标记方法确定的，通常仅基于图结构，PATCHY-SAN缺乏对更广泛应用的学习灵活性和普适性。

        不同于PATCHY-SAN模型通过结构信息对节点进行排序[52]，LGCN模型[53]提出通过使用结构信息和第p层的输入特征图将不规则的图数据转化为类似于网格的数据。具体而言，对于图G中的节点u ∈V，LGCN模型将节点u的邻居的输入特征图堆叠成一个矩阵M ∈R|N(u)|×dp，其中|N(u)|表示节点u的一跳邻居节点的数量。对于M的每一列，保留前r个最大值并形成一个新的矩阵M˜∈Rr×dp。通过这种简单的方式，将输入特征图和图的结构信息转化为一个1-D的类似于网格的数据X˜p Xp ∈Rn×(r+1)×dp。然后，经典的1-D CNN可以应用于X˜p，并学习新的节点表示Xp+1。值得注意的是，还提出了一种基于子图的训练方法，以便将模型扩展到大规模图。由于经典CNN中的卷积只能处理具有相同拓扑结构的数据，将经典CNN扩展到图数据的另一种方法是开发一种对欧几里得和非欧几里得数据都具有结构感知的卷积操作。Chang等人首先建立了经典滤波器和单变量函数（即函数滤波器）之间的联系，然后将图结构建模为结构感知的广义函数滤波器[54]。由于这种结构感知的卷积需要学习无限数量的参数，因此使用Chebyshev多项式[35]进行近似。另一项工作[55]通过设计一组固定大小的可学习滤波器（例如，大小为1到大小K）重新构建了经典CNN，并表明这些滤波器对图的拓扑结构具有适应性。

基于传播的空间图卷积网络

        在这一小节中，我们关注的是在顶点域中从邻居节点传播和聚合节点表示的空间图卷积。其中一项显著的工作是[56]，其中在第p层的节点u的图卷积被设计为：其中|N(u)|是在第p层与|N(u)|具有相同度的节点的权重矩阵。然而，对于任意大的图，节点度的唯一值的数量通常是一个非常大的数。因此，在每一层将有许多需要学习的权重矩阵，可能导致过拟合问题。Atwood等人提出了一种基于扩散的图卷积网络（称为DCNN），通过图扩散过程引发节点表示的传播和聚合[57]。通过转移矩阵Pk的k次幂进行k步扩散，其中P = D−1A。然后，扩散-卷积操作被公式化为：其中Z(u,k,i)是基于Pk聚合的节点u的第i个输出特征，非线性激活函数σ(·)选择为双曲正切函数。假设考虑了K跳扩散，那么转移矩阵的K次幂需要O(n2K)的计算复杂度，这对于大规模图来说是禁止的。Monti等人提出了一个名为MoNet的通用图卷积网络框架[5]，通过设计一个将节点邻域内的信号集成起来的宇宙块算子。具体而言，对于一个节点i和它的邻居节点j ∈ N(i)，他们定义了一个d维伪坐标u(i,j)并将其输入到可学习的核函数P(w1(u),...,wP(u))中。然后，块算子被公式化为D p D p(i)=j∈N(i)wp(u(i,j))x(j),p =1,...,P，其中x(j)是节点j处的信号值。空间域中的图卷积则基于块算子进行：研究表明，通过精心选择u(i,j)和核函数wp(u)，许多现有的图卷积网络模型[37,57]可以看作是MoNet的特例。SplineCNN [58]遵循相同的框架[即方程(15)]，但使用基于B样条的不同卷积核。

        对于附带边属性信息的图，滤波器的权重参数通常会根据节点邻域中特定的边属性进行调整。为了利用边属性，设计了一种边条件卷积（ECC）操作[59]，借鉴了动态滤波器网络的思想[60]。对于第p层ECC中节点v和节点u之间的边，使用相应的滤波器生成网络Fp：Rs →Rdp+1×dp 生成特定于边的权重矩阵p v,u，卷积操作的数学表示如下： 其中bp是可学习的偏置项，滤波器生成网络Fp通过多层感知器来实现。此外，Hamilton等人提出了一种基于聚合的归纳表示学习模型，称为GraphSAGE [61]。算法的全批处理版本简单明了：对于节点u，GraphSAGE中的卷积层（1）通过一些可学习的聚合器聚合当前层所有直接邻居的表示向量，（2）将节点u的表示向量与其聚合表示向量连接在一起，然后（3）将连接的向量输入到一个全连接层，使用某个非线性激活函数σ(·)，然后进行归一化处理。GraphSAGE中的第p层卷积层具体包括： 聚合函数有几种选择，包括均值聚合器、LSTM聚合器和池化聚合器。使用均值聚合器，可以简化公式(17)为： 此外，池化聚合器的公式为： 其中(x ∗s y)(i)表示元素i在x和y中的最大值。

        为了支持小批量训练，作者还提供了一种变体，即对每个节点均匀采样固定数量的邻居节点[61]。然而，随着图卷积模型变得更深，节点表示学习的性能往往会下降。实践表明，在GCN [37]和GraphSAGE [61]中，两层图卷积模型通常可以获得最佳性能。根据[62]，GCN [37]中的卷积与拉普拉斯平滑[63]有关，更多的卷积层会导致不同簇中的节点表示变得不太可区分。从不同的角度来看，Xu等人分析了两种类型节点的不同扩展行为，包括图中类似扩展器的核心部分的节点和树状部分的节点，并展示了相同数量的传播步骤可能导致不同的效果[64]。例如，对于核心部分内的节点，其特征的影响传播比树状部分的节点更快，因此这种快速平均导致节点表示不可区分。为了缓解这个问题并使图卷积模型变得更深，Xu等人借鉴了计算机视觉中残差网络[65]的思想，提出了一种跳跃知识网络的跳跃连接架构[64]。跳跃知识网络可以自适应地选择不同卷积层的聚合方式。换句话说，模型的最后一层可以独立地选择聚合每个节点的中间表示。逐层聚合器包括连接聚合器、最大池化聚合器和LSTM-attention聚合器。此外，跳跃知识网络模型还可以与其他现有的图神经网络模型结合使用，如GCN [37]、GraphSAGE [61]和GAT [24]。

使用卷积聚合的图卷积网络

        是一种通用图神经网络的特殊类型。还存在基于不同类型聚合的其他图神经网络变体，例如门控图神经网络[26]和图注意力网络[24]。在本小节中，我们简要介绍一些通用图神经网络模型，其中图卷积网络可以被视为特殊的变体。 最早的图神经网络之一是[66]，它定义了参数化的局部转换函数f和局部输出函数g。设X0(u,:)为节点u的输入属性，Eu为与节点u相连的边的属性。然后，局部转换函数和局部输出函数定义如下： 其中H(u,:)、X(u,:)分别表示节点u的隐藏状态和输出表示。方程(19)定义了图神经网络中聚合的一般形式。在[66]中，函数f被限制为压缩映射，以确保收敛性，并受到Banach不动点定理的启发。通过这种方式，经典的迭代方案被用于更新隐藏状态。然而，以迭代的方式更新状态以获得稳定状态效率低且效果较差。 相反，SSE [68]旨在以随机方式迭代地学习节点表示的稳定状态。具体而言，对于节点u，SSE首先从V中采样一组节点V˜，然后通过T次迭代更新节点表示，使其接近稳定状态。更新方式如下： 其中节点u ∈ V˜，T表示迭代次数，聚合函数定义如下： 其中X0(u,:)表示节点u的输入属性。 在[69]中提出的消息传递神经网络（MPNN）广义上包括许多图神经网络的变体，例如图卷积网络（如[37,56,61]）和门控图神经网络[26]。MPNN可以看作是一个两阶段的模型，包括消息传递阶段和读出阶段。在消息传递阶段，模型对节点进行P步的聚合，每一步包含以下两个函数： 其中Mp、Up分别是第p步的消息函数和更新函数，eu,v表示边（u,v）的属性。然后，在读出阶段通过以下方式计算整个图的特征向量： 其中R表示读出函数。 此外，Xu等人在理论上分析了现有基于邻域聚合的图神经网络的表达能力[70]。他们分析了基于图神经网络与Weisfeiler-Lehman图同构测试之间密切关系的现有图神经网络的能力，并得出结论，现有的基于邻域聚合的图神经网络（如[37,61]）最多可以与一维Weisfeiler-Lehman同构测试具有相同的能力。为了实现与Weisfeiler-Lehman测试相等的表达能力，Xu等人提出了一个简单的架构，称为图同构网络[70]。

图卷积网络的应用可以根据其应用领域进行分类。在本节中，我们主要介绍图卷积网络在计算机视觉、自然语言处理、科学和其他领域中的应用。

1. 计算机视觉：图卷积网络在计算机视觉领域中被广泛应用于图像分类、目标检测、图像分割等任务。通过将图像表示为图的形式，可以利用图卷积网络对图像进行特征提取和表示学习，从而提升计算机视觉任务的性能。
2. 自然语言处理：图卷积网络在自然语言处理领域中也有着重要的应用。例如，可以将文本数据表示为图的形式，利用图卷积网络进行文本分类、关系抽取、命名实体识别等任务。图卷积网络可以捕捉文本中的语义关系和依赖关系，提升自然语言处理任务的效果。
3. 科学领域：图卷积网络在科学领域中有广泛的应用，例如化学分子图的表示学习、蛋白质结构预测、社交网络分析等。通过将科学数据表示为图的形式，并利用图卷积网络进行特征提取和分析，可以帮助科学家们更好地理解和预测复杂的科学现象。
4. 其他领域：除了上述领域，图卷积网络还可以应用于社交网络分析、推荐系统、交通网络优化等其他领域。通过利用图卷积网络对图结构进行建模和分析，可以提供更准确和有效的解决方案。 总之，图卷积网络在多个领域中都有广泛的应用，通过对图结构进行建模和分析，可以提供更强大的特征提取和表示学习能力，从而提升各种任务的性能。

计算机视觉中的应用 计算机视觉是过去几十年来最热门的研究领域之一。许多现有的深度学习架构都是基于经典的卷积神经网络（CNNs）构建的。尽管CNNs取得了巨大的成功，但它们很难编码特定学习任务中的内在图结构。相比之下，图卷积网络已经被应用于解决一些计算机视觉问题，并展示出了可比甚至更好的性能。在本小节中，我们将根据数据类型进一步分类这些应用。

1. 图像分类：图卷积网络已被用于图像分类任务。通过将图像表示为图的形式，可以利用图卷积网络对图像进行特征提取和表示学习，从而提高图像分类的准确性。
2. 目标检测：图卷积网络在目标检测中也有应用。通过在图上进行滑动窗口或区域提议，并利用图卷积网络对每个窗口或区域进行特征提取和分类，可以实现准确的目标检测。
3. 图像分割：图卷积网络在图像分割任务中也有应用。通过将图像表示为图的形式，并利用图卷积网络对图像中的每个像素进行特征提取和分类，可以实现精确的图像分割。
4. 图像生成：图卷积网络可以用于图像生成任务，如图像修复、图像超分辨率等。通过对图像进行表示学习和重建，可以生成具有高质量和真实感的图像。 总之，图卷积网络在计算机视觉领域的应用非常广泛。通过对图像进行表示学习和分析，可以提供更准确和有效的解决方案，提高各种计算机视觉任务的性能。

图像

        图像分类在许多实际应用中非常重要。通过一些精心设计的图构建方法（例如kNN相似度图）或其他监督方法，可以将无结构的图像转换为结构化的图数据，从而可以应用于图卷积网络。现有的图像分类模型包括但不限于[5,32,34,71,72]。 图像的另一个应用是视觉问答，它探索对图像上的问题的答案。Narasimhan等人提出了一种基于图卷积网络的深度学习模型，利用来自知识库的图像多个事实的信息来辅助问题回答，这样可以减少对图像单个正确事实的检索的依赖[73]。 此外，由于图像通常包含多个对象，理解对象之间的关系（即视觉关系）有助于描述它们之间的相互作用，这使得视觉推理成为计算机视觉中的热门主题。对于视觉关系检测，Cui等人提出了一种利用词语的语义图和空间场景图的图卷积网络[74]。此外，Yao等人提出了一种图卷积网络和LSTM的架构，用于探索图像字幕的视觉关系[75]。 为了生成场景图，尽管存在一些基于消息传递的方法[76,77]，但其中许多方法可能无法处理不可靠的视觉关系。Yang等人提出了一种注意力图卷积模型，可以将注意力放在可靠的边缘上，同时抑制不太可能的边缘的影响[78]。在相反的方向上，Johnson等人使用图卷积网络模型处理输入的场景图，并通过级联的改进网络生成图像[79]，并通过对抗训练进行训练[80]。

视频

        视频的一个高影响应用是动作识别，可以帮助理解视频。在[81]中，设计了一个时空图卷积模型，消除了手工分配部分的需求，并且可以获得更强的表达能力。另一个基于骨架的方法是[82]，提出了一个广义图构建过程，用于捕捉骨架序列中的变化，然后将广义图输入到图卷积网络中进行变化学习。Wang和Gupta [83]将输入视频表示为时空区域图，构建了两种连接（即外观相似性和时空接近性），然后通过应用图卷积网络来识别动作。张等人提出了一种用于动作识别的张量卷积网络[84]。

点云

        点云为计算机图形学和计算机视觉中的许多应用提供了一种灵活的几何表示。在开创性的PointNet [85]之后，最先进的深度神经网络考虑了点云的局部特征[85,86]。然而，这些工作忽略了点之间的几何关系。另一方面，EdgeConv [87]被提出来捕捉局部几何结构，同时保持置换不变性，并在点云分割任务中胜过其他现有方法。在[88]中，提出了一种用于点云分割的正则化图卷积网络模型，其中图拉普拉斯矩阵动态更新以捕捉学习特征的连接性。FeaStNet [89]基于图卷积网络动态确定了滤波器权重和图邻域之间的关联，展示了在部件标记方面具有可比较的性能。Wang等人提出了一种用于点云分类和分割的局部谱图卷积网络[90]。对于点云分类，其他基于图卷积的方法包括[45,59]。Valsesia等人提出了一个使用图卷积生成3D点云的局部生成模型[91]。

网格

        我们在这篇论文中考虑的网格应用之一是形状对应，即在多个3D形状之间找到对应关系。除了经典的基于CNN的方法（例如[92,93]），还提出了几种基于图卷积网络的方法，包括[5,89]。此外，Litany等人提出将图卷积网络与变分自编码器结合起来，用于形状完成任务[94]。

自然语言处理中的应用

        文本分类是自然语言处理中最经典的问题之一。通过将文档视为节点，将它们之间的引用关系视为边，可以构建引用网络，在这种情况下，节点属性通常由词袋模型建模。在这种情况下，将文档分类到不同的类别的直接方法是节点分类。已经提出了许多图卷积网络模型，包括[5,37,42,61,95]。另一种方法是将文档视为图级别（即，每个文档被建模为一个图），并通过图分类来对文本进行分类[33,34]。此外，TextGCN [96]将整个语料库建模为一个异构图，并同时学习词嵌入和文档嵌入，然后使用softmax分类器进行文本分类。Gao等人使用图池化层和图卷积与经典卷积的混合卷积来结合节点排序信息，相对于传统的基于CNN和GCN的方法，取得了更好的性能[97]。当存在许多不同主题粒度的标签时，这些单一粒度的方法可能会达到次优性能。在[98]中，构建了一个词语图来捕捉长距离语义，然后应用递归正则化图卷积模型来利用标签的层次结构。信息抽取通常是许多与自然语言处理相关的应用的基石，图卷积网络广泛应用于信息抽取及其变体问题。例如，GraphIE [99]首先使用递归神经网络生成单词或句子的本地上下文感知隐藏表示，然后学习文本单元之间的非本地依赖关系，最后使用解码器对单词级别进行标注。GraphIE可以应用于诸如命名实体抽取等信息抽取任务。图卷积网络已被设计用于词语之间的关系抽取[100,101]和事件抽取[102,103]。

        此外，Marcheggiani等人开发了一种可以在句法依赖树之上使用的句法图卷积网络模型，适用于各种自然语言处理应用，如语义角色标注[104]和神经机器翻译[105]。对于语义机器翻译，图卷积网络可以用于向句子编码器注入语义偏差，并实现性能改进[106]。此外，还设计了扩张迭代图卷积网络模型用于依赖解析[107]。

在科学物理学中

        喷注是指高能强子的聚集喷射，与喷注相关的许多任务，包括与产生喷注的原初粒子相关的分类和回归问题。最近，基于消息传递神经网络的变体[69]已经被设计用于将喷注分类为两类：基于量子色动力学的喷注和基于W玻色子的喷注[108]。ParticleNet是基于边缘卷积[87]构建的一个定制的神经网络架构，直接对粒子云进行喷注标记[109]。此外，图卷积网络模型也被应用于IceCube信号分类[110]。另一个有趣的应用是预测物理动力学，例如，一个立方体在与地面碰撞时的变形情况。Mrowca等人提出了一种基于层次图的物体表示方法，将一个物体分解为粒子，并将同一组内的粒子连接起来，或者与祖先和后代连接[111]。然后他们提出了一种层次图卷积网络来学习物理预测。

在化学、药物发现和材料科学中

        对分子的学习引起了很多关注。例如，图卷积网络已经被用于分子指纹预测[56,112]。在药物发现中，使用了一种基于注意力机制的图卷积网络模型DeepChemStable[113]，用于化合物的化学稳定性预测。此外，通过将蛋白质-蛋白质相互作用、药物-蛋白质靶点相互作用建模为多模态图，可以应用图卷积来预测多药物副作用[114]。化学中另一个重要的应用是分子性质预测。消息传递神经网络（MPNNs）[69]是一种通用的图神经网络框架，可以用于预测分子的量子性质。PotentialNet[115]首先对化学键进行图卷积，学习原子的特征，然后进行基于键和空间距离的传播，最后通过全连接层进行分子性质预测。蛋白质界面预测是药物发现中的一个具有挑战性的问题。Fout等人构建了一个图，其中蛋白质中的每个残基被视为一个节点，并且节点伴随着根据氨基酸序列和结构计算得出的特征[116]。为了预测蛋白质界面，使用了图卷积层来处理不同的蛋白质图，然后是一个或多个全连接层。此外，[117]提出了一种称为晶体图卷积神经网络的方法，可以直接从晶体中原子之间的连接中学习材料的性质。

除了在社会科学经典问题中的应用，如社区检测[42,118]和链接预测[21,119,120]，图卷积网络还被应用于许多其他问题。DeepInf[121]旨在通过学习用户的潜在特征来预测社交影响。Vijayan等人提出使用图卷积网络来预测转发数量[122]。此外，假新闻也可以通过图卷积来检测[123]。图卷积网络广泛应用于社交推荐，旨在利用用户-物品交互和/或用户-用户交互来提高推荐性能。Wu等人提出了一种神经影响扩散模型，考虑了用户受其信任的朋友影响的因素，以实现更好的社交推荐[124]。Ying等人提出了一种非常高效的图卷积网络模型PinSage[125]，基于GraphSAGE[61]，利用了Pinterest中pin和board之间的交互。Wang等人提出了一种神经图协同过滤框架，将用户-物品交互整合到图卷积网络中，并明确利用协同信号[126]。

挑战和未来研究：深度图卷积网络

        尽管图卷积网络模型的最初目标是利用深度架构来实现更好的表示学习，但目前大多数模型仍然受制于其浅层结构。例如，GCN[37]在实践中只使用了两层，而使用更多的图卷积层甚至可能损害性能。这是因为其简单的传播过程导致的直观结果。随着架构的加深，节点的表示可能变得更加平滑，即使对于那些不同且相距较远的节点也是如此。这个问题违反了使用深度模型的目的。尽管已经提出了一些方法来解决这个问题（例如基于跳跃连接的模型），但如何构建一个深度架构，能够更好地自适应地利用图的更深层次的结构模式，仍然是一个开放的挑战。

用于动态图的图卷积网络

        现有的大部分图卷积网络明确假设输入图是静态的。然而，在实际情况中，网络经常以动态方式变化。例如，社交网络本质上是动态网络，因为用户经常加入/退出网络，用户之间的友谊也在动态变化。因此，在静态图上学习图卷积网络可能无法达到最佳性能。因此，研究高效的动态图卷积网络模型非常重要。

更强大的图卷积网络

        现有的大部分空间图卷积网络模型都是基于邻居聚合的。这些模型在理论上被证明最多与一维Weisfeiler-Lehman图同构测试一样强大，而图同构网络已被提出以达到极限[70]。然而，一个自然的问题是：我们能否突破一维Weisfeiler-Lehman图同构测试的限制？一些研究已经探讨了相关问题，如[127-129]。然而，对于这个问题的进一步研究仍然是非常具有挑战性的。

多图卷积网络

        如前所述，谱图卷积网络的主要缺点是无法在两个具有不同傅里叶基（即拉普拉斯矩阵的特征函数）的图之间进行适应。现有的工作[130]通过将单个图的特征函数推广到多个输入图的克罗内克积图的特征函数来学习滤波器参数。作为另一种方法，对于许多空间图卷积网络模型，归纳学习是可能的，即在一个或多个图上学习的模型可以应用于其他图。然而，这些方法的一个缺点是没有利用多个图之间的交互（例如，锚链接、跨网络节点相似性）或相关性（例如，多个视图之间的相关性）。实际上，对于给定的多个图，唯一节点的表示学习应该能够从跨图或视图提供的更多信息中受益。然而，据我们所知，目前没有针对这种情况的现有模型来解决这些问题。

2.总结

        作为图神经网络模型的一种，图卷积网络模型已成为机器学习和其他相关领域的热门话题，并且已经提出了大量模型来解决不同的问题。在本调查中，我们对图卷积网络这一新兴领域进行了全面的文献综述。具体而言，我们引入了两个直观的分类法，以根据图滤波操作的类型和应用领域对现有工作进行分组。对于每个分类法，我们从独特的角度提供了一些详细的例子。我们还讨论了现有图卷积网络的一些挑战和潜在问题，并提供了一些未来的研究方向。

缩写词

CNN：卷积神经网络；

ChebNet：基于切比雪夫多项式的图卷积（在[34]中提出的模型）；

GCN：图卷积网络（在[37]中提出的模型）；

FastGCN：用于GCN的小批量训练（在[39]中提出的模型）；

CayleyNet：基于Cayley多项式的图卷积（在[42]中提出的模型）；

LanczosNet：基于Lanczos算法的多尺度图卷积网络（在[43]中提出的模型）；

PATCHY-SAN：图卷积神经网络（在[52]中提出的模型）；

LGCN：大规模图卷积神经网络（在[53]中提出的模型）；

DCNN：基于扩散的图卷积网络（在[57]中提出的模型）；

MoNet：基于伪坐标的图卷积网络（在[5]中提出的模型）；

SplineCNN：用于图和网格的B样条基础的卷积核（在[58]中提出的模型）；

ECC：边缘条件卷积（在[59]中提出的模型）；

GraphSAGE：基于平均值/LSTM/池化聚合的图卷积网络（在[61]中提出的模型）；

GAT：图注意力网络（在[24]中提出的模型）；MPNN：消息传递神经网络（在[69]中提出的模型）。