图卷积算法的研究进展*

郑睿刚 ，陈伟福 , 冯国灿

(1. 中山大学数学学院，广东 广州 510275；2. 中山大学广东省计算科学重点实验室，广东 广州 510275)

深度神经网络有着悠久的研究历史。由于模型大，参数多，对训练数据和计算条件要求非常苛刻。2006 年Hinton 和Salakhutdinov[1]在Science上发表了一篇用神经网络来对数据进行降维的论文引起人们极大的关注。此外，以AlexNet[2]在2012年ImageNet[3]图像识别大赛上表现大放异彩为肇始，深度学习的热潮由此开启。有赖于大数据量、非凸优化、硬件计算和网络结构等多方面的进展，以卷积神经网络、循环神经网络、生成对抗网络为代表的深度学习方法近年来在图像、音频、视频、文本等规则数据处理方面都取得了优异的甚至大幅超越传统方法的结果。以卷积神经网络(Convolutional Neural Network, CNN)为例，残差神经网络(Residual Networks, ResNet)[4]在ImageNet[3]上的图片分类中top5的错误率只有3.57%，能力超越人类水平。由于深度神经网络在规则数据处理上取得了极大的成功，进一步考虑如何将深度学习方法推广到其他不同于网格与序列的非规则数据结构上是目前神经网络领域一个研究热点。

以图(graph)为代表的非规则数据，如以城市为节点的交通流量网络、以用户为节点的社交网络和以各类原子为节点的分子结构网络等，在数据的存储和描述实体间的关系方面正发挥着越来越重要的作用。基于图结构的数据处理，主要涉及到图节点的表示学习、图节点的分类、图上边的预测(链接预测)、图的分类等问题。比如说，对于文献引用网络(citation network),节点的分类主要是预测节点代表的文献是属于哪一个主题(如图1(a)所示)，在社交网络(social network)中经常需要预测哪两者之间是有关联的则属于链接预测(如图1(b)所示)。

图1 图结构数据处理图例(部分图片取自文[5])

经典的图结构数据处理算法主要依据图谱嵌入、随机游走、图核等，然而此类浅层模型主要的缺点在于模型能够学习的表达能力较为简单，无法从大规模复杂的网络中提取有价值的信息。然而，如果直接运用传统的深度神经网络的方法来处理这些非规则结构的数据，效果也并不理想。为了更有效处理这些图结构的数据，近年来涌现了大量图卷积网络。不同于经典方法，这些图卷积算法模型参数量大，表达能力强，且可结合样本特征与图结构作端到端的各项任务，既利用了图结构，亦减少了对图结构的依赖，在处理图结构数据中取得了超越经典图方法的良好效果。

目前图卷积算法主要是考虑如何将处理规则数据的卷积网络迁移过来。对于像网格那样的规则数据，由于有内在的序的关系，很容易在同一模板上定义具有紧支撑的卷积算子。然而，图等不规则数据不具有这样序的关系，因此无法在空间上定义这样的卷积算子。由欧氏空间中的卷积定理可知，两个光滑函数的卷积的傅立叶变换等价于函数傅立叶变换后的乘积。因此，目前定义图卷积的一个主要思路是先将傅立叶变换推广到图结构数据上，然后再根据卷积定理和逆傅立叶变换求得图谱卷积。另一方面，从计算上角度出发，规则数据的卷积运算等价于相关性计算，即中心点与周围网格数据的加权求和，类似地可以将图上的卷积定义问题转化为图上相关性计算的定义问题，对相关节点加权求和，由此引出图上的空间卷积。类比于传统的卷积网络，当定义好卷积层后，可考虑图上的池化(pooling)操作。对于图卷积后结果应该以何种方式聚合最后，不同论文从层次聚类和Weisfeiler-Lehmance测试[6]等角度给出了不同的池化定义。最后，对于理论上界定不同图卷积网络的表达能力的问题，已有若干结果，这些结果对于本质上理解和搭建图卷积网络具有重要的指导意义。

本文综述了以图谱卷积和空间卷积为两大脉络的各图卷积神经网络定义与模型沿革，并对图上池化操作、图卷积网络表达能力与实际应用作了相应的介绍。本文内容顺序如下：第1节为相关的数学符号与定义，第2节为图谱卷积模型，第3节为空间卷积模型，第4节介绍图上池化操作，第5节为关于图卷积网络的表达能力探讨，第6节为相关实际应用，第7节为全文总结。

1 符号与定义

本小节将给出后续内容涉及的较为基本的数学符号及其定义，并以表格的形式汇总。

定义3设f∈Rn为一图上向量。设边e连接节点vi与vj。定义关于边e在节点vi上的边导数为

(1)

或

(2)

同理有边e在节点vj上的边导数，符号与上述相反。

记关于节点vi的局部波动为

(3)

定义关于f的图上光滑性为

(4)

事实上，对应式(1)，有

fTLuf=S(f)

(5)

对应式(2)，有

fTLsf=S(f)

(6)

从而可以用统一形式

fTLf=S(f)

(7)

表达，依采用的拉普拉斯矩阵L=Lu或L=Ls确定图上光滑性S(f)对应的边导数定义。

定义4面向节点分类和链接预测的图卷积神经网络通常包括输入层，卷积层，激活层和输出层，其结构示意图如图2所示。

图2 面向节点分类的图卷积神经网络结构示意图[8]

此处，输入层的输入为图G，包括节点信息和边信息。隐层为卷积层，卷积函数记为Gconv,根据不同的卷积算法，Gconv有不同的定义方法。卷积层是图卷积神经网络的核心层，下面介绍各种算法时，重点也是介绍各卷积算子的动机、物理意义和定义形式。在卷积层中，当节点带有多维属性时，通常需要对属性进行拼接，我们以‖ 表示向量拼接操作，例如x=[x1,…,xn]，y=[y1,…,ym]，则x‖y=[x1,…,xn,y1,…,ym]。激活层是模拟人脑对接收信息的处理方式，当信息的强度大于某一阈值时，阀门打开，信息通过，反之，阀门关闭，信息丢弃。为了方便训练网络参数，激活函数σ一般定义为非线性的可导函数，常是有Sigmoid函数，tanh函数，Relu函数等，由于Sigmoid函数和tanh函数容易出现梯度消失的问题，目前的神经网络主要使用Relu函数作为激活函数，图2显示了Relu函数的形式，需要注意的是，当σ作用于向量或矩阵时，是对其每一个元素分别作激活。对于节点分类的问题，网络的输出层一般为节点的类标或隶属于各类的概率。

面向图分类的卷积网络，在前述网络的基础上通常会加多池化(pooling)层和Readout层[9]。图3显示了该类网络的结构。我们在后面将专门介绍池化层，对于Readout层，一般是从各节点的隐层表示中，通过Readout函数得到能代表整个图的一个向量，最后对图分类转变为对该图的表示向量进行分类。

为便于查看，表1给出了本文所用数学符合及其所代表的意义。

图3 面向图分类的图卷积神经网络结构示意图[8]

表1 符号表

2 图谱卷积模型

=U(UTx⊙UTy)

(8)

即将图上的卷积定义为两图上函数(信号)在图上频谱(图谱)的逐分量相乘后再经逆傅立叶变换得到的图上函数(信号)。以上图信号处理的内容围绕无向图展开，事实上，存在更为广泛的图傅立叶变换与图滤波算子定义[10]。一般卷积层如图4所示。下面介绍四种经典的图谱卷积网络。

图4 图卷积网络第k层图例

2.1 Spectral CNN[11]

(9)

2.2 Chebyshev Spectral CNN[12]

(10)

其中gi,j是某Chebyshev多项式。由于参数为多项式系数，与图的节点数无关，因此以上定义可用于涉及不同大小的图分类问题。

2.3 CayleyNet[13]

尽管Chebyshev Spectral CNN[13]通过采用多项式函数拟合卷积核频谱系数函数减少了计算复杂度，但其依旧缺乏关于频谱滤波方面的一些理想性质。以具有簇结构的图为例，这些图上的簇内连边较为密集，簇间连边较为稀疏，图信号在频谱上的表现为集中在低频部分。为了在卷积过程中捕捉到这种信号的频带集中特点，卷积核的频谱系数应在低频部分取较大的值，对卷积核频谱系数函数而言，则应与某区间上的特征函数I[a,b](x)尽可能相似。文[13]提到了Chebyshev多项式拟合区间特征函数所需的参数量大致与区间长度成反比，因而捕捉越短狭的频带需要更高阶的Chebyshev多项式，从而导致了计算量的增加。

文[13]提出的CayleyNet通过结合Cayley变换与复系数多项式函数的Cayley多项式实现了低阶多项式下的频带捕捉。文中的卷积核频谱函数被定义为Cayley变换与复系数多项式函数实部的复合：

(11)

(12)

gc,h(λ)=c0+2R(p(C(λ))-c0)

(13)

若记C(hL)=(hL-iI)(hL+iI)-1，相应的卷积与卷积层定义为：

(14)

(15)

由于Cayley变换的非线性特点，实轴的任意区间频带[a,b]可通过调整h改变映射至复平面单位环的放缩程度，从而可以实现对特定频带的过滤。

2.4 Graph Convolutional Network (GCN)[14]

对于图上的半监督问题，由于有监督样本的占比往往是比较小的，相应模型的复杂度不应过大，否则易导致对有监督样本的过拟合。基于以上考虑，GCN模型极大简化了Chebyshev Spectral CNN[12]中Chebyshev多项式函数的设置，具体而言，Chebyshev多项式的阶数设为1，且合并了常数项与一阶项的系数，并对图上各节点添加自环，即

(16)

以上四个图卷积模型，围绕图谱卷积这一主题，从最初简单地将频谱系数设为参数，发展到定义卷积和频谱系数函数，模型定义逐步改善，模型间具有明显的逻辑上的先后关系。表2汇总了以上四个模型的定义和主要特点。

表2 四种图谱卷积层

3 图的空间卷积模型

除图谱卷积外，另一个在图上推广经典卷积定义的思路是仿照经典卷积计算过程，即图上空间卷积。经典卷积的计算过程实际是同一模板在网格不同位置作加权求和计算的结果，且对于奇数长度的卷积核而言，其涉及计算范围实际上是中心网格与其在八连通网格图上的k阶邻域。从更一般的角度出发，经典卷积与相关性计算是等价的，卷积的计算等同于用翻转过的卷积核计算空间上的相关性，因而对于图这种不规则的结构，定义了图上的相关性计算即定义了图上的空间卷积，由此图上的卷积的定义问题化归为图上相关性计算的定义问题。以下小节将从随机采样和注意力机制的角度介绍两篇较为具有代表性的工作。

3.1 GraphSAGE[16]

图谱卷积需要在给定图上定义，因为无法处理具有变化结构的图学习问题，例如动态社交网络上的实体分类。通过观察(16)我们可以看出，GCN[20]实际上是在各节点的一阶邻域内加权求和，GraphSAGE模型[16]因而从宏观的角度将图卷积网络的学习目标定义为结合图结构和邻域节点的关于各节点特征的学习，并将图卷积看做是各节点与其邻域内节点的的聚合过程，即某种意义上的相关性计算。在此图卷积定义下，若相关性计算的定义可随节点的邻域的变化而变化，则此卷积定义可应用于具有变化结构的图学习问题。GraphSAGE[16]将图卷积层定义为领域表示的获得和关于中心节点与其邻域表示的结合，即

(17)

3.2 Graph Attention Network[17]

Graph Attention Network (GAT)模型[17]通过注意力机制，将GCN模型中一阶邻域加权求和的固定权重改为需要通过样本特征表示的变化权重，使得模型表达的丰富性和灵活性进一步提高。GAT模型[17]中的卷积层定义为

(18)

事实上，以k阶多项式函数的为频谱系数函数的图谱卷积实质是在各节点的k阶邻域求加权和[7]，因此一部分图谱卷积模型本身亦是空间卷积模型，但求和权重固定，测试样本和训练样本需要同时存在，在半监督学习框架中属于直推式学习。以上两空间卷积模型则可看做是对采取固定加权求和策略的空间卷积模型的改进。这些模型从不同角度放宽空间卷积的定义，基于样本与其邻接样本学习卷积定义中的参数，在放宽定义的同时保证图上的有效语义提取，且可用于半监督学习框架下的归纳式学习，但也因此丧失了图谱卷积中关于特定频谱提取的模型可解释性。表3汇总了迄今为止的大部分图卷积网络模型。

表3 图卷积网络及其卷积层类别[8]

4 图卷积网络中的池化

图卷积中的邻域聚合过程与Weisfeiler-Lehmance测试[6]在计算方面十分相似。Weisfeiler-Lehmance测试是判别两图是否同构的算法，概括而言，此算法在一轮聚合过程中先对每一节点赋予一特殊字符，并根据各节点的一阶邻域内各节点字符构造字符串，以对字符串的哈希结果作为节点新的对应字符，两图的同构与否则通过比较每一轮聚合后字符集的相同与否判别。图卷积可类似地看做是以节点特征作为“连续型字符”构造“连续型字符串”的过程，池化操作则是获取“连续型字符集”的相关操作，网络依据池化的结果进行关于图的分类，相当于“连续型字符集”之间的比较。基于以上观点，DGCNN模型[29]将各层图卷积的结果合并后排序，截取序列的前k个节点作为“连续型字符集”的表示，并将此截断序列输入普通一维卷积层和全连接层从而获得关于图的最终表示。

以上例子仅从层次聚类和Weisfeiler-Lehmance测试的角度介绍了图上池化定义，限于篇幅，仍有其余方面的工作未被涉及。定义计算效率更高且在理论上更具有可解释性的图上池化定义仍旧是当前值得探讨的问题。

5 图卷积网络的表达能力

从原理上理解模型各方面能力对于确定模型关于具体问题的适用性是必要的，且有助于我们分析模型效果的成因，对于图卷积网络亦不例外。遗憾的是，在数学上确立图卷积模型的能力与模型之间的比较准则等机理探讨是此前大部分工作所欠缺的。以图分类为目标的图卷积网络为例，大部分模型缺乏对其能够区分的图的多样性，即以区分为目的的模型表达能力在数学上刻画与证明。

文[35,41]中的结果改变了以上局面。由于一阶邻域聚合与Weisfeiler-Lehmance测试在计算上的天然的相似性所带来的启发，文[35,41]都证明了Weisfeiler-Lehmance测试的图同构分辨能力是采用一阶邻域聚合的图卷积网络的上界。文[41]进一步证明了存在相应的图卷积网络，其表达能力等价于Weisfeiler-Lehmance测试[6]。由于Weisfeiler-Lehmance测试本身图同构判别能力的限制，文[41]构造了近似k维Weisfeiler-Lehmance测试且表达能力更为强大的图卷积网络。文[35]中的理论结果则更为全面。若将Weisfeiler-Lehmance测试[6]中的哈希过程解包，则Weisfeiler-Lehmance测试实际上是对以各节点为根的子树，或更一般地，对多重集合进行统计。基于此观点，若一图卷积网络能够达到Weisfeiler-Lehmance测试的区分能力，则应至少能够将不同的多重集合映射到不同的值，即网络为一关于多重集合的单映射。文[35]证明了图卷积网络网络相应模块的单映射性是达到Weisfeiler-Lehmance测试区分能力的充分条件，在此基础上结合多层感知机的逼近能力定义了能够达到Weisfeiler-Lehmance测试区分能力的GIN模型，并刻画了其余图卷积网络的缺陷所在，建立了平均池化(对所有节点表示取均值)与区分多重集合分布、最大池化(对所有节点取最大值)与区分多重集合的潜在集(即去重后的集合)之间的对应关系。

6 图卷积网络的应用

由于实体与节点、实体间互动与边的自然对应，现实中大量数据形式是可以由图表示的，图卷积网络因此具有广阔的应用领域。互联网应用是其中主要的一个工业应用场景。以推荐系统和恶意账户识别应用为例，文[42]利用用户-物品之间的关系二分图与用户、物品的丰富特征，结合RW-GCN空间图卷积网络，学得各用户、物品的向量表示，以选取近邻的方式确定推荐给用户的物品；GEM[43]则将网络购物系统中的账户与账户所涉及的设备(电话号码、MAC(media access control address)、IMEI(international mobile equipment identity)、SIM(subscriber identity module)卡号等)作为节点，对每一类设备单独构建表示设备与账户活动关系的异构设备二分图，结合空间图卷积网络，将各设备图上的图卷积结果聚合，得到账户节点的类型预测结果，在线下实验与线上应用都取得了十分良好的识别效果。

图卷积网络在计算机视觉和自然语言处理领域的应用亦表现出了不俗的效果。例如STGCN[44]，能够通过结合视频每帧人体骨架构建关于人体骨架动态变化的时空图，定义时空上的卷积从而实现对视频动作类型的高准确率判定；在神经机器翻译方面，Bastings等[45]通过在语法树上定义考虑边方向与语法类标信息的图卷积网络，使得模型能够利用语料库中的语法结构信息，提升了英-德与英-捷克语翻译的效果；TextGCN[46]通过定义词之间和词与文本之间的特殊边权构建结合词与文本的混合图，结合GCN模型实现文本分类目标。

除以上较为常见的应用领域外，图卷积网络亦可应用其他学科中的计算问题。如GIN[35]、DGCNN[29]等用于图分类的图卷积网络自然适用于蛋白质图类型的判别；文[24]利用度量学习学得残差拉普拉斯矩阵，结合图谱卷积模块，对化合物分子所涉及得若干指标作出估计；文[47]利用空间图卷积网络作为预处理模块，通过机器学习得方式估计两图之间的编辑距离，高效近似地求解了一NP难问题。

我们以文献网络为例详述图卷积网络在节点分类问题上的表现。文献网络上的节点分类一般涉及三个数据集：Cora[48]、Citeseer[48]、Pubmed[48]。以上文献网络的图为无向图，图上的节点对应文献，边对应文献间的引用关系且边权为1，即两节点间存在一条边当且仅当两文献存在引用关系。图5给出了这三个文献引用网络最大连通分量的平面示意图。在文献网络节点分类中，我们需要预测无标签节点(文献)所属的类别。表4和表5给出了数据集的具体指标和以GCN与GAT为代表的图卷积网络在各数据集上的分类表现。可以看出，相对于没有利用图结构的分类方法(MLP多层感知机)与没有利用节点特征传统类标传播方法LP[49]，图神经网络能够大幅提升分类准确率。

图5 三个文献引用网络中最大连通分量的平面图示

7 总结与展望

本文综述了图卷积神经网络所涉及的理论背景、各网络模块、相关理论研究与实际应用，以较为具有代表性的工作为例介绍了图谱卷积网络、空间卷积网络和相关模型沿革与对比。从层次聚类和Weisfeiler-Lehmance测试的角度介绍了图上池化模块，概述了联系Weisfeiler-Lehmance测试与图卷积网络表达能力的理论工作，并简单介绍了图卷积神经网络的应用实例。图卷积神经网络的出现正值当前的深度学习热潮，由于其理论的开拓性与潜在应用的广泛性，相关的理论与应用研究日益受到重视，未来图卷积神经网络必将拥有广阔的应用前景。

表4 数据集指标

表5 准确率[14,17]