基于剪边策略的图残差卷积深层网络模型

毛国君，王者浩，黄 山，王 翔

（福建工程学院福建省大数据挖掘与应用重点实验室,福建福州 350118）

1 引言

图是描述对象及其相互关系的直观表达，基于图结构的图数据在现实世界中普遍存在而且具有强大的表示能力，已经成为学习的一种重要的数据来源［1］.图数据具有以下特征：（1）节点特征：节点自身的属性（作为观察对象需要关注的特征集）.（2）结构特征：图数据中的节点之间构成的拓扑结构（由节点之间的边来刻画）.图数据分析有着广泛的应用价值，如：图分类任务［2］、图形图像的结构推理［3～5］、社交网络的链路预测和节点聚类［6～8］等.

在图数据分析领域，图神经网络（Graph Neural Networks，GNN）已经被提出，近年成为一个重要的研究分支.它的一个直接动力来自于深度神经网络的成功.深度学习作为人工智能第三次浪潮的标志性成果，已经在包括图像、语音分析应用上取得重要突破.但是一个不容忽略的事实是：目前最热门的卷积神经网络（Convolutional Neural Networks，CNN）仍然在传统的欧氏空间来思考和解决问题.如图1所示，传统的CNN把观察的对象独立当做输入来迭代分析，忽略了对象之间的关系对分析的影响，而近年提出的GNN则可以把对象的结构图作为输入来直接进行分析.毋容置疑，GNN突破了传统的图像处理的欧氏空间限制，有着巨大潜在的应用价值.

图1 CNN和GNN在图像处理上的输入数据

简言之，相比于使用CNN，GNN特点主要有：（1）现实世界中，一组对象及其关系是不可分割的整体，GNN更符合人类思维模式，应用范围会更广；（2）在处理对象关系时，对象及其关系作为整体来输入，而传统的CNN没有处理关系的机制，需要人为设计进而很难避免主观因素的影响.当然，GNN仍在发展中，即使是研究最早的图卷积神经网络（Graph Convolutional Network，GCN）在关键的卷积核和池化等操作的有效性上仍然面临挑战.

目前困扰图卷积神经网络的最主要问题是过平滑现象［9］.事实上，最初提出的GCN模型只有2层［10］，而且发现随着深度加深，GCN模型并不像深度CNN那样推理能力得到有效提升，甚至效果会变差［11，12］，这种过平滑现象已经成为GCN发展的主要障碍.究其原因是图数据结构没有点阵图像所拥有的空间平移等恒定性质，本质上是多层的拉普拉斯变换，因此图中的大部分节点的特征值很容易到达某一固定平滑值.快速的拉普拉斯平滑本身没有错，问题是由于快速的平滑会导致调整空间变窄，很难实施精细化地学习，模型的性能就很难得到持续地提升.

通过加深网络层次来改善图神经网络的表达能力研究已经开始被关注［13～15］，其中Chen等在ICML2020中提出了GCNII（Graph Convolutional Network via Initial residual and Identity mapping），是目前已知的最具代表性的深度图神经网络模型［13］.简单地说，GCNII就是在恒等连接的学习中通过附加了初始输入信息，来实现了跨层跳跃的平稳连接.此外，之前引入跨层跳转思想来实现深度GCN的一个比较成功的工作是JKNet（Jumping Knowledge Networks）［14］.JKNet模型中提出了自适应选择性聚合机制，利用跨层的跳转链接将浅层的特征值融入到深层中，使得每个节点可以根据多层信息融合结果来自适应实现聚合半径的动态调整，从一定程度上有效避免过平滑带来的语义偏差.简言之，GCNII和JKNet都在深度GCN模型上进行了有效尝试，可以预见深度的图神经网络将是未来一个重要的研究方向.

另一方面，图卷积本质是特征聚合问题，所谓的学习实质上就是寻找聚合收敛的状态，而且收敛结果只有和领域本身语义相一致才是成功的学习.事实上，GCN中的输入是信息更丰富的图结构（不仅节点还考虑边），相邻节点特征的重复利用加速了GCN收敛速度，极易产生过平滑现象.从这个角度说，对输入的图数据进行“裁剪”可以增加图网络的泛化能力，增强语义的可扩展性，进而可以预防过平滑现象的过快出现.裁剪GCN大致有3条路径：剪输出（DropOut）［16］、剪点（DropNode）［17］和剪边（DropEdge）［18］.剪输出就是通过适度地裁剪隐含层节点的输出值（使之不到下一层），它在普通的深度神经网络中就被提出，而且得到广泛应用［19］.顾名思义，剪点就是裁剪输入图中的节点，而剪边就是裁剪输入图中的边.直观上讲，剪点比剪边力度更大，即一个节点被裁减不仅它对应的实体不存在、而且依附它的边也会自然消失.Rong Y等人的研究证实了剪点技术很难被控制，可能剪边比剪点更适合于GCN网络［18］；对应实验也验证了在GCN中适度剪边可以延缓过平滑现象发生，使构建深度GCN成为可能［18］.

本文的主要工作及贡献包括：将残差卷积（residual convolution）、恒等映射（identity mapping）和剪边处理融合到图神经网络的设计中，提出了dri_GCN深度网络模型，并在多个标准数据集上完成了比较性实验.

2 相关工作

Gori等人最先关注图数据的处理，在2009年提出了图神经网络模型（GNN）［20］.它借鉴了普通神经网络的结构来直接处理图结构数据.这个模型可以被认为是图神经网络的开创性工作，为后续图神经网络的发展奠定了基础.2013年，Bruna等人利用拉普拉斯算子与傅里叶变换等技术，解决了图数据的卷积计算问题，提出了第一个图卷积神经网络［21］.2016年，Kipf和Welling运用了一阶邻阶聚合思想，提出了GCN模型［10］，被之后大多数研究作为基础GCN模型来使用.当然Kipf和Welling提出的GCN模型的最优性能层数只有2层，而且之后的许多研究都证实这个GCN模型不适合构建深层网络，即继续加深模型深度会导致聚合效果急剧下降.

2018年，Xu等人提出了一种改进型的图神经网络模型JKNet［14］.JKNet利用跳跃链接和自适应选择性聚合机制，运用跳跃链接在构建深层GCN网络上进行了有效尝试.2020年，Chen等人设计了GCNII模型［13］，它是目前为止比较成功的一个深层GCN模型.另一个比较成功的工作来自于Rong等人［18］，他们发现对图结构数据适度进行剪边可以很好地解决GCN的过平滑问题.事实上，通过删除输入图数据的部分边，一定程度上改变了节点间的连接方式，使节点的聚合产生了差异化，增强了训练数据的多样性，进而提升了模型的泛化能力.

近年对图数据的应用也成为了热门的研究方向.例如：2020年，郭嘉琰等人把GCN应用到动态网络异常检测中，提出一种基于图神经网络的异常检测算法［22］；2020年，Wang等人利用GCN网络实现了人体姿态估计［23］；2020年，Yu等人利用GCN解决了社交网络中谣言检测问题［24］.

3 dri_GCN：融入剪边操作的图残差卷积网络设计

首先明确几个GCN相关的名词和表示：

（1）图：G=（V，E），其中V是节点集，E是边集.特别地，和CNN不同，GCN的输入就是图本身.

（2）邻接矩阵：图G的邻接矩阵A=（aij）是一个方阵，aij=1意味着第i个节点和第j个节点存在边，否则为0.很显然，无向图的邻接矩阵是一个对称矩阵.

（3）度矩阵：图G的度矩阵D=（dij）是一个对角阵，对于无向图而言，dii就是第i个顶点的度，并且dij=0（i≠j）.对于有向图，需要通过顶点的出度和入度来分别表示.

（4）单位矩阵：是一个特殊对角阵图I=（pij），pii=1，并且pij=0（i≠j）.

（5）拉普拉斯矩阵：图G的拉普拉斯矩阵定义为L=D-A，其中D和A是G的度矩阵和邻接矩阵.

3.1 基于谱域的GCN的预备知识

基本的图卷积神经网络是基于谱域（Spectral domain）方法构建的，其中的核心是拉普拉斯矩阵及其计算.

图卷积神经网络在利用拉普拉斯矩阵之前需要使用了两个小技巧来改善其性能：（1）对所有节点增加自环保证节点自身和邻居节点一起参与推理，即A=A+I（本文仍记为A）；（2）进行归一化以预防梯度爆炸或者消失问题.

定义1（适用拉普拉斯矩阵）［10］给定增加自环的图G，设G的邻接矩阵、度矩阵及单位矩阵分别为A、D和I，则一种适用的拉普拉斯矩阵归一化方法是：

定义1被称为对称归一化的拉普拉斯矩阵（Symmetric-normalized Laplacian）.设̂=D-1/2AD-1/2，则作为一个适用的操作单元被目前大多数GCN模型作为推演的基础（本文亦是）.

定义2（拉普拉斯矩阵的傅里叶变换）给定图G，设它的拉普拉斯矩阵L的特征值和对应的特征向量分别为Λ=(λ1，λ2，…，λn)(λ1≤λ2≤…≤λn)和U=(u1，u2，…，un)，对G上的任意信号x∈Rn，定义它的傅立叶变换为=f(x)=UTxˉ，对应逆傅立叶变换为x=f-()=.

基于谱域分析的卷积一般是在傅里叶域上完成的，依靠定义2的傅里叶变换和逆傅里叶变换，我们就可仿照CNN的卷积方法完成图的卷积计算.

定义3（简化的图卷积）［10］一个简化的GCN模型的卷积公式为：

其中̂=D-1/2AD-1/2（A含自环），W（l）是第l层的学习权重，σ（.）是某个激活函数.

和普通CNN一样，卷积运算解决了输入的前向传播问题，但是还要依靠反向传播来进行误差评估.当然，图卷积需要依据图结构进行，因此反向传播的基础是边导数.

定义4（GCN中的梯度）［21］给定图G，eij是G中节点vi到vj的一条边，A=（aij）和D=（dij）分别是的G的邻接矩阵和度矩阵.设J∈Rn是G上一个n维向量，则eij在vi节点上的边导数如下计算：

节点相关的梯度表示为

3.2 残差网络与跨层连接

带残差的图卷积模型主要在一个残差单元中引入浅层到深层的跳转链接.如图2所示，对于l+l层而言，除了l层输出作为输入之外，通过增加（l层）之前的跳转链接来防止计算偏差地蔓延，提升聚合效能.

图2 一个残差块的连接结构示意

定义5（带残差的图卷积）［13］一个带残差的GCN模型的基本卷积公式为：

其中H（*）表示*层或者更浅层次的输出.

引入残差的初始动机是为了防止梯度消失问题［25］.近年研究也发现：在GCN中引入残差进行卷积计算可以加强深层与浅层之间信息互补.此外，引入残差的卷积网络需要恒等映射机制，这不仅保证了浅层和深层信息的兼容性，而且可以使网络结构更加均匀化，更利于通过加深网络层次来提高学习精度.

图2给出的残差块只是个示意，浅层跳转到深层的途径可以有许多，需要和实际应用结合起来考虑.如：GCNII［13］就是采用一种称为初始残差（Initial residual）的技术，即所有的中间层残差块都是直连初始的输入.再如：JKnet［14］则是仅在最后一层选择之前的卷积层的输出进行融合聚集.从本质上说，通过跨层连接来改善残差卷积网的性能是目前一个探索最多的方法之一，相信未来还会继续得到关注.

图3给出了引入残差和恒等映射的GCN的工作原理示意.

图3 残差和恒等映射在GCN中工作原理示意

如图3所示，假如在GCN网络中，不使用残差连接，节点的特征值会很快趋于同质（如图3的l和l+1层的黄色部分），即出现过平滑现象.假如加入浅层的第*层到深层的第l层的跳转通路，那么第l+1层的节点就需要综合考虑第l层和第*层计算结果，这样就利用浅层信息修正了学习中的偏差，延缓了过平滑现象过早发生，为深层GCN提供有力支撑.

当然，节点特征的有效叠加，要归功于恒等映射技术.就是说，经过若干层的GCN推理后，恒等映射保证了各个节点处于同一量纲上，让引入残差的节点特征能够成功的叠加在到深层单元.

3.3 dri_GCN模型设计

集成图剪边、初始网络和恒等映射技术，结合上一节的相关定义，本文提出了一种图神经网络模型dri_GCN.

剪边被证明是实现深层GCN的一个有效技术［18］，其主要作用概括为：

（1）剪边可以看作一种数据增强技术，在训练过程中对输入的邻接矩阵进行随机地删减，可以增加模型的输入数据的多样性.

（2）剪边技术用于训练中，使用得当可以增强节点之间的区分度，减少信息的重复利用率，进而减缓了过平滑现象.

融入剪边和初始残差技术，图4给出了对应的恒等卷积网络模型dri_GCN的运行框架，其中表示剪边操作后并归一化后的邻接矩阵.

图4 dri_GCN运行框架

定义6（dri_GCN的图卷积）对于图G，设：剪边概率为1-p，则用表示剪边后归一化的邻接矩阵；α和β为用来控制跳跃连接的两个超参数；σ为激励函数；W（l）为l层的权重.dri_GCN的图卷积公式表示为：

其中H（l）为l层的输出向量，I是单位阵.

如式（6）所示，dri_GCN只使用初始残差H（0），这主要是我们的实验发现初始残差对该模型更有效.

基于初始残差和恒等映射，融入剪边操作的dri_GCN模型的第l层的处理步骤如下.

步骤1设定剪边系数p，按概率随机丢弃：←re-normalization(A-A')．

步骤2设定控制参数α，按α导入初始输入αH（0）．

步骤3融合H（l）和H（0），生成带有残差的l层输出：H*←(1-α)(l)+αH(0)．

步骤4设定控制参数β，对权重实施恒等映射：W*←(1-β)I+βW(l)．

步骤5选定激励函数σ，生成层l输出：H(l+1)←σ(H*，W*).

值得注意的是，dri_GCN模型中参数p、α和β以及激励函数σ的设定是个经验问题，需要根据应用背景来逐步尝试获得优化值.我们在实验中获得的经验包括：

（1）p是图保留边的比例（剪边的比例为1-p），对应的就是正则化的输入矩阵.一般地，p不宜过小，过小会导致图结构性的数据不足，丧失图网络的优势；当然p也不宜过大，过大会使迭代过程的数据多样性不足，容易产生过平滑.我们实验的经验p值在0.7～0.9之间.

（2）控制初始残差的参数α不宜过大，一般设置在0.1或者0.2比较适中［13］.如式（6）所示，α过大将直接减弱上层计算对本层计算的作用，严重影响学习效率.

（3）式（6）使用（1-β）I+βW（l）来替换普遍使用的权值向量W（l），这可以保证与浅层模型具有等价的性能，有利于跨层信息聚合.事实上，（1-β）I+βW（l）是W（l）的正则化结果，当β足够小时，（1-β）I+βW（l）的奇异值会接近于1［26］.这样就可以通过合适的β值设定，来达到权重向量修正和网络等价性维护的平衡目的，提升系统的自适应性.我们实验中β设为随层数l变换的变量，为为控制系数，一般设为0.5.

为了说明dri_GCN模型的基本原理，对2层的dir_GCN网络学习过程的主要结构进行了跟踪和解析，其中数据集使用的是标准数据集Citeseer［27］.图5给出了2层dri_GCN网络的处理过程示意.

图5 dri_GCN网络的学习过程示意

依据图5，设定p=0.9、α=0.1和λ=0.5，2层dri_GCN网络对Citeseer数据集处理的基本过程是：

（1）由Citeseer数据集的原始数据，得到输入特征H（0）和剪边后归一化的邻接矩阵Âp（如式（7））.值得注意地是，剪边仅仅是将邻接矩阵部分数值置零，并不改变邻接矩阵维度.

（2）H（0）经过全连接层后特征维度变为64，以便与预先设置的权重矩阵W维度相匹配，其中权重矩阵的值是随机生成的.经过第一个dri_GCN卷积层后与初始残差αH（0）叠加得到中间特征向量H（1）.

（3）将更新后的H（1）和Âp输入到下一个dri_GCN卷积层，再经过全连接层后，得到最后的输出特征向量H（2）.

式（8）给出了100次网络学习后最终输出的H（2）与分类结果.式（9）中分类结果（3 0 1…）只给出了前三个节点1、2、3被分成的类标识“3”、“0”、“1”.具体得到方式是：节点对应行在H（2）中的最大值所在的位置.

4 实验与分析

4.1 数据集

实验采用了标准数据集Cora、Citeseer和Pubmed进行评估和比较［27］.对于所有数据集，都按照无向图进行处理，并且仅考虑最大的连通部分，即每个数据集都对应一个无向连通图.表1给出了本文实验中的3种数据集的基本信息.

表1 三个数据集的基本信息

按照目前大多数论文的处理惯例和本文需求，实验前对3个数据集做无向图处理，之后使用它们评估本文模型和对比模型.图6展示了3个数据集的部分连通图，其中对一些节点进行了标识以直观地反映对应数据集情况.

图6 数据集对应的部分无向连通图

4.2 学习准确率与分类精度的比较性实验

实验中准确率和精度由式（10）和式（11）计算得到：

其中式（10）和式（11）对应的符号及含义如下：

（1）P（Positive）和N（Negative）：分别代表训练样本中的正例和负例数目.

（2）TP（True Positives）：被正确划分为正例的数目，即实际为正例且被模型划分为正例的样本数.

（3）TN（True negatives）：被正确划分为负例的数目，即实际为负例且被分类器划分为负例的样本数.

（4）FP（False Positives）：被错误划分为正例的数目，即实际为负例但被分类器划分为正例的样本数.

（5）FN（False Negatives）：被错误划分为负例的数目，即实际为正例但被分类器划分为负例的样本数.

从式（10）、式（11）的计算方式可以看出：准确率主要反映一个学习方法或算法的整体学习效果；精度只关心正例集的分类情况，深入到一个具体的类别进行评价，可以更准确地反映某个类别分类的效果.

首先使用式（10），比较性地评价本文模型的准确率.表2给出了对比实验中使用的主要参数设置情况，其中的参数是根据数据集和模型特点，在多次实验后获得的优化值.

表2 实验模型所用的参数

根据本文使用的主要技术，从基本的GCN模型（简称G）、剪边技术（简称d）和恒等映射下的初始残差技术（简称r）3个维度来择选比较算法：

（1）单独考虑G.实验中使用的是典型算法GCN［10］；

（2）考虑d+G.文献［18］提出了在GCN中进行剪边的理由和部分效果的展示，我们在此基础上进行了完善，并命名为d_GCN来用于本文比较性实验；

（3）考虑r+G.GCNII［13］属于这类模型的典型代表.

（4）考虑d+r+G.本文提出的dri_GCN模型属于该类.

按照如上4个方法类别，择选了GCN、d_GCN、GCNII和 本 文 的dri_GCN模 型，在Cora、Citeseer和Pubmed数据集上进行了对比实验.表3至表5给出了实验结果（下划线数据为获得的最高准确率），其中的准确率是100次实验获得的平均值.

表3 不同方法在Cora数据集上的分类准确率(%)

表4 不同方法在Citeseer数据集上的分类准确率(%)

表5 不同方法在Pubmed数据集上的分类准确率(%)

从表3～表5可以看出：

（1）本文dri_GCN模型在3个标准数据集上最高准确率均有所提升.

（2）GCN模型在2层网络上还能获得较好的学习准确率，但是随着深度加深，学习准确率会急剧下降，而且简单地使用剪边技术（对应d+G模型）也很难支撑深度GCN的构建.

（3）dri_GCN和GCNII模型可以支撑深层卷积网的构建，而且在3个标准数据集上dri_GCN比GCNII的学习准确率都有不同程度地提升.

究其原因，dri_GCN融合了初始残差、恒等映射及剪边技术，整体上减缓了过平滑现象，使图结构的信息聚合更精细.具体地说，初始残差技术将最初的节点特征叠加在深层模型上，阻止了节点聚合偏差的放大或累加，延长了网络的生命周期；恒等映射技术使初始残差能有效地融入到深层的卷积单元，保证网络加深后的继续学习能力；剪边技术进一步削弱了残差网络退化的可能性，通过图结构数据的变化使得残差单元的数据输入的相异度增加，避免某些节点的特征向量在相邻残差层的快速同化，因而提升了学习的精细度.

此外，依据式（11），对单个类别的分类精度进行了跟踪实验.图7给出了dir_GCN在Cora数据集上4个类别的精度比较实验.图7的横坐标是一次dir_GCN网络学习的迭代次数，纵坐标的精度值采用的是20次dir_GCN网络学习在对应迭代次数上得到平均精度值.

仔细分析图7，可以看出：

图7 dri_GCN在Cora数据集的精度对比

（1）在Cora数据集上，对于前面3个类（类标识为0，1，2），剪边后的分类精度在所有迭代阶段均好于未剪边的图神经网络；

（2）对于类标识为3，前面的剪边效果不是很理想，但是迭代270次后剪边效果开始显现.可以推断，对于分类精度不佳的类来说，可以通过适当增加学习过程中的迭代次数来提升分类精度.

4.3 剪边有效性分析

为了更详尽地说明剪边技术对模型的影响，我们通过设置不同的层数和不同p值，对模型dri_GCN的剪边效果进行了实验.表6给出了在Cora数据集上不同p值对应的学习准确率（实验的结果也是采用20次网络学习的平均值）.

从表6可以看出：

表6 Cora数据集p参数实验(%)

（1）针对Cora数据集，剪边技术在p=0.9或0.8，层数在16层以上，dri_GCN模型的准确率基本都在84%左右，说明通过设置合适的剪边系数p，通过加深模型层次可以获得稳定的更高的学习准确率.

（2）当p在0.6以下，dri_GCN模型的准确率不高，说明剪边效果不理想.这是因为过多的剪边丢失了图数据结构，也从一个侧面说明图神经网络的科学性，即合理利用节点的关联信息能够提升节点的评估效果.

为了更直观地表达剪边在GCN上的有效性，实验跟踪了4层dri_GCN模型在3个标准数据集上的损失值.图8给出了随着迭代训练次数增多时剪边（p=0.9）和不剪边（p=1）的损失值变化趋势.

图8表明：融入剪边技术可以使验证集的损失值平稳而迅速地下降（相对于不剪边）.说明剪边技术很好利用了数据多样性，可以及时修正迭代过程中的偏差，更有利于实现精细化学习.

图8 dri_GCN损失函数对比

图神经网络中的验证集的准确率反映了所使用模型的聚合能力.实验跟踪了3个数据集在剪边前后（p=1，p=0.9）的验证集准确率变化.实验的准确率也是采用每组数据进行20次网络学习取平均值.实验结果如图9所示.

图9 dri_GCN验证集准确率对比

从图9可以看出：在维持学习准确率的前提下，剪边可以加速聚合速度.在迭代100次之前，剪边后3个数据集的在验证集的准确率快速提升（相比未剪边），说明剪边技术的确可以提升聚合效率.此外，迭代100次之后，剪边模型的准确率也和剪边前相当，说明剪边技术不会减弱模型的学习能力.

5 总结与展望

图神经网络已经成为图学习中的一个重要而活跃的研究分支.现存的图神经网络的关键瓶颈是过平滑问题.本文集成了剪边、初始残差和恒等映射技术，提出了一种图神经网络模型dri_GCN.本文提出的模型直接面向于图神经网络研究中亟待解决的过拟合和过平滑问题，通过多种技术集成来提升图学习的性能，在深层图残差卷积的结构及其计算方法等方面进行了相关工作.实验结果表明，dri_GCN可以提升学习数据的多样性，减少训练数据的过拟合现象；可以更精细地完成基于图结构的信息聚合，有效防止过平滑现象；具备构建深层图神经网络的能力，为实现深层图学习提供一个有效途径.

本文模型为构建深层GCN网络提供新的解决途径.从结果来看，所提模型在标准数据集上的学习准确率和分类精度方面得到有效提升.未来的工作包括：本文模型在实际应用场景上的应用研究；融合其他技术进一步改进深层图神经网络性能等.