从拓扑的角度缓解图卷积网络的过平滑问题

柏 玉,宋 敏，刘士虎，唐 轶，杨昔阳

(1.云南民族大学 数学与计算机科学学院，云南 昆明 650504;2.泉州师范学院 数学与计算机科学学院，福建 泉州 362000)

图数据作为一种通用语言，用于建模结构化和关系数据，例如社交网络、点云和交通网络.近年来，许多研究关注于开发图数据的深度学习方法，导致了图神经网络(graph neural networks, GNNs)领域的快速发展.GCNs是一种常用而高效的GNNs方法，其在半监督节点分类[1]、推荐系统[2]和链接预测[3]等任务上取得了很大的成功.GCNs主要有2种方法，即基于谱域的方法和基于空间的方法. 然而，由于其简单性、较低的计算成本和对大型图更好的可扩展性，基于空间的方法最近变得越来越流行.遵循空间方法的 GCNs模型的操作可以表示为2个阶段，即消息传递阶段和读出阶段.在消息传递阶段，图中的一个节点从它的邻居接收消息，其中每个消息都是从一个邻居节点的特征或连接到该节点的边的特征计算出来的.在消息传递阶段经常执行的两个步骤是聚合和更新步骤.在聚合步骤中，节点通过执行加权求和操作.在更新步骤中，将对聚合的消息应用非线性转换，以生成更新的节点表示.在GCNs模型中，消息传递阶段通常使用图卷积层来实现.通过叠加多个图卷积层，可以建立一个深度GCNs模型，并允许在相隔不止一跳的节点之间传递消息，以及通过一系列非线性转换学习抽象的中间节点嵌入.在读出阶段，学习到的节点嵌入被转换为节点或整个图的最终表示.然后将这些表示提供给分类器，根据下游任务产生合适的输出.

卷积神经网络(convolutional neural networks,CNNs) 在许多领域中都取得了优越的性能， CNNs的成功受益于它们能够设计和训练一个深层的网络模型.受此启发，研究者们可能期望通过堆叠更多的图卷积层，使GCNs具有更好的表现力来表征更丰富的邻居拓扑.而构建深层并有表达性的GCNs并不容易实现.这是因为深层GCNs实际上受到了主要由过平滑[4]引起的表达能力的损害，该问题指出，重复使用图卷积使不同类的节点表示无法区分.

构建深层GCNs的尝试可以追溯到GCN模型[1]，其应用了残差机制.出乎意料的是，当深度为3层及以上时，残差GCN的表现仍然较差.文献[4]首先指出了构建深层网络的主要困难在于过平滑，但遗憾的是，他们未提出解决这个问题的方法.后续研究[5]通过使用个性化的PageRank解决了过平滑问题，该PageRank还将根节点加入到消息传递循环中.文献[6]提出了宽度拓展的方法，即采用多阶近邻连接和序列化连接来缓解深层GCNs的过平滑现象.文献[7]采用密集连接进行多跳消息传递，用于构建深层GCNs.最近,文献[8]通过首先将表示转换与传播解耦，利用自适应调整机制来平衡每个节点的局部和全局邻居之间的信息来改进GCNs的体系结构.文献[9]从理论上证明了深层GCNs的节点特征会收敛到子空间而导致信息丢失，通过考虑ReLu函数和卷积滤波器，推广了文献[4]中的结论.文献[10]提出了DropEdge的方法，可以将其视为消息传递减速器，应用该方法可以去除某些边使得节点连接更加稀疏，从而在一定程度上避免了深层GCNs存在的过平滑问题.文献[11]在文献[4]结论的基础上开发了一种过平滑度量，并提出了一种基于监督优化的方法来缓解过平滑.最近其他一些防止过度平滑的研究采用激活归一化[12]和双残留连接[13]，它们与文献[10]中的DropEdge是互补的.最近的一种方法[14]将残差层、密集连接和膨胀卷积纳入GCNs, 以促进深层结构的发展.然而，该模型的目标是图分类，其中没有讨论过平滑.

1 预备知识

为了行文简洁及后文叙述的需要，这里给出文中要用到的一些基本知识的相关数学表示.

1.1 符号

设G=(V,E)表示无权无向图，其中V是节点的集合，E⊆V×V是V中节点之间的边的集合，|V|=n和|E|=m分别是节点数和边数.整个图的拓扑信息由邻接矩阵A∈Rn×n描述，其具有如下性质:

用D=diag(d1,d2,…,dn)∈Rn×n表示图G的节点对角度矩阵，其中du=∑vA(u,v)，其矩阵形式为

节点特征矩阵表示为X∈Rn×d, 其中每行xv∈Rd表示节点v的特征向量，d是节点特征的维数.X也可使用矩阵的形式表示

1.2 图卷积运算

大多数GCNs中的图卷积运算遵循邻域聚合方式[16]，通过传播其邻居的表示并在此之后应用变换来学习节点表示.一般图卷积运算的第l层可以描述为

(1)

不失一般性，在下面的分析中重点讨论GCN模型，这是最具代表性的图卷积运算. 每个GCN层(GCN Layer, GCL)定义为:

(2)

一般来说，GCN模型中的2层可以得到很好的效果.两层时，GCN模型可简化为

Z=Softmax(σ(XW(0))W(1)).

(3)

采用GCN分类模型，验证文中的方法在缓解该模型加深时存在的过平滑现象上的有效性，从而提高了其在半监督节点分类任务上的性能.

1.3 半监督节点分类

半监督节点分类在训练阶段同时包含有标签的节点和无标签的节点，通常无标签节点远远多于有标签节点，与使用所有有标签节点的模型相比，其训练成本更低且效果更好.具体地，对于图G=(V,E),VL表示z(0

2 深层GCNs模型的实证分析

在本节中，目的是验证深层GCNs性能下降的主要原因是过平滑.为此，首先引入一个平滑度的定量度量来度量图节点表示的平滑性.然后，利用这一指标以及Zachary空手道俱乐部数据集来验证过平滑是影响更深层的GCNs模型性能下降的主要因素.

2.1 平滑度的定量度量

众所周知，平滑度是反映节点表示的相似性的指标.由于欧氏距离是一种简单而有效的度量节点表示的相似性的方法，特别是在高维空间中，首先用欧式距离表示节点u和节点v的表示之间的相似性度量

(4)

其中xu为节点u的特征表示，‖·‖为欧氏范数.欧式距离值越小，表示的相似性越高.为了消除特征表示大小的影响，我们使用归一化节点表示来计算它们的欧氏距离，从而将D(xu,xv)限制在[0,1]的范围内.

基于公式(4)中的相似性度量，提出节点u的平滑度度量QMSu(quantitative metric for smoothness),用于计算节点u到其他节点的平均距离

(5)

其中，n为图G中的节点数.因此，QMSu度量节点u的表示与整个图的相似性.进一步，可以使用QMSG来表示整个图G的平滑度度量值.其数学表达式定义为

(6)

这里，QMSG的值越小，则图G中节点表示的整体平滑度越高.

2.2 深层的GCNs模型性能下降的原因

基于上述研究，该部分主要探讨深层的GCNs性能下降的原因.为此，研究了具有不同层数的GCN模型，并在Cora数据集上对它们进行了评估.在该数据集上对GCN模型进行100次运行，使用与文献[1]相同的数据分割方案.

图1 在Cora上对不同GCN层数的节点表示的测试精度和平滑度度量值

在Cora数据集上的结果如图1所示.可以观察到，模型深度为2层时测试精度是最高的，但从3层开始精度随着层数的增加而减小.同时不难发现，GCN的平滑度度量值随着其层数的增加而变小.说明不同GCN层数所导出的不同标签的节点表示变得难以分离，整个图的表示不可避免地出现了过平滑现象.

除了从定量的角度使用上述度量外，还采用Zachary空手道俱乐部数据集的可视化说明这一点，该数据集被分为2个类别，有34个顶点和78条边.在这里，GCN未经过训练，其权重参数是随机初始化的，隐藏层的维数为16，输出层的维数为2.在这个数据集上应用具有不同层数的GCN模型，不同层的GCN模型的输出在图2中被绘制为二维平面上的点.通过图2,可以观察到不同层数的GCN模型对这个小数据集的影响.当GCN模型的层数为1层时，这些点没有很好地分离(图2a).当应用2层图卷积时，来自2个类别的点被相对较好地分离(图2b).而应用多个图卷积层时，这些点很快发生了混合，生成的节点表示很难分离(图2c、d、e、f).

图2 不同层数的GCN在Zachary空手道俱乐部网络上的顶点嵌入

3 从拓扑的角度缓解过平滑问题

在GCNs中，相邻节点间的消息传递是通过连接2个节点之间的边来实现的，用DropEdge技术随机删除掉一些边就可以让节点连接更加稀疏.与此同时，GCNs具有局部连接的特点，而混合阶传播能够包含更多的局部信息.它们能够在一定程度上避免深层GCNs存在的过平滑问题.因此，我们提出了一种DropEdge技术和混合阶传播结合的方法，从拓扑的角度来缓解过平滑问题(relieving over-smoothing problem from the topological view, ROPTV).在本节中，首先解释DropEdge技术和混合阶传播结合的方法如何缓解GCNs的过平滑问题.然后，将缓解了过平滑现象的深层GCNs用于半监督节点分类任务，预测未标记节点的标签.

3.1 DropEdge技术和混合阶传播结合的方法

DropEdge是一种简单而有效的技术，尤其是在缓解深层GCNs存在的过平滑现象方面.每次训练时，DropEdge技术会随机删除原始图中固定比例的边.由于文中遵循文献[1]中对邻接矩阵进行重归一化技巧的思想，所以该技术是在对称归一化邻接矩阵上随机选取Vp个非零元素，然后将它们置为零，其中超参数p∈[0,1]表示删除边的概率.删除后得到邻接矩阵DE, 用公式表示为

DE=-′,

(7)

(8)

3.2 半监督节点分类任务

(9)

(10)

(11)

对于半监督多分类问题，评估所有有标记节点的交叉熵损失

(12)

其中yL是具有标签的节点集合.

针对文中的研究目的，从拓扑的角度应用DropEdge技术和混合阶传播结合的方法来缓解深层GCNs模型存在的过平滑现象，将改进的更深层的GCNs模型应用于半监督节点分类任务.可以将这个过程总结为ROPTV算法.

4 实验

本节在3个引文网络数据集上对半监督节点分类任务进行实验，以评估本文提出的ROPTV的优越性.首先介绍需使用的数据集和实验设置.然后将ROPTV与代表2种不同类别的8个深度为2层的GCNs基线进行比较，包括6种图卷积: GCN[1]、 APPNP[5]、 N-GCN[6]、 Dropedge[9]、 GAT[17]、 SGC[18]; 2个基于采用的GCNs: GraphSAGE[19]和 FastGCN[20].此外，还对过平滑问题进行实验分析.验证ROPTV在缓解深层GCNs存在的过平滑现象上的有效性，并能提高其在半监督节点分类任务上的性能.ROPTV算法模型为：

输出 预测Z.

步骤：

3) 执行特征转换：由公式(10)来执行特征转换.

4) 由公式(11)来预测节点类别分布.

5) 由公式(12)计算半监督节点分类损失.

4.1 数据集

本文对3个公开的引文网络数据集Cora, Citeseer和Pubmed[21]进行实验，表2汇总了数据集的统计信息.通过将科学论文视为节点，论文之间的引用视为边，为这些数据集构建图，每个节点由从相应文档中提取的词袋(Bag-of-words)特征向量来表示.针对Cora, Citeseer和Pubmed的预处理脚本是参考文献[22]的代码实现的.在每个基准数据集上，使用与半监督图学习[1,17]完全相同的实验设置，例如特征和数据分割，并使用100个随机数种子对每个数据集上的所有结果进行了100次实验.

4.2 实验设置

使用 Pytorch 框架和Pytorch Geometric来实现所提出的方法和一些必要的基线，Pytorch Geometric是一个基于Pytorch构建的用于对不规则结构化数据进行深度学习的库. GCN的代码参考GCN模型的PyTorch版本实现.使用Glorot正态初始化器来初始化分类器的权重矩阵，采用Adam优化器来优化模型的参数，并采用基于验证损失的早期停止控制训练周期.另外，只在训练集上使用DropEdge技术，在验证集和测试集上不再使用. 对于GCNs的过平滑问题的实验，用GCN模型[1]做对比实验，将GCN模型和ROPTV模型的层数l设置为2到32层不等，而ROPTV模型的传播步长k被设置为2.

表1 基准数据集统计

所有实验都是在16GB内存大小的11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz 3.11 GHz上进行的.服务器操作系统为Windows 10.对于软件版本，使用Python3.7.3, PyTorch 1.2.0, NumPy 1.16.4, SciPy 1.3.0.

4.3 实验结果总体分析

半监督节点分类结果汇总在表2，其中每一列的最高精度用粗体加下划线突出显示.方法显示在表格的最后一行.

表2 总体分类准确率 %

从表2的顶部可以观察到，在Cora和Citeseer数据集上，ROPTV在所有基线上实现了较大幅度的超越，在Pubmed数据集上表现的不是很好，但是和其他基线差距不大，说明文中提出的方法是有效的.具体来说，ROPTV在Cora和Citeseer数据集上的精度比GCN分别提高了3.3%和3.6%, 而GCN相比较，GAT的精度分别只提高了1.5%和2.2%.与最近的基于正则化的模型DropEdge相比，所提出的方法实现了2.0%和1.6%的改进，而DropEdge对GCN的改进分别仅为1.3%, 2.0%和0.6%.

此外，与基于节点采样的方法——GraphSAGE和FastGCN相比，可以看到ROPTV在Cora, Citeseer和Pubmed数据集上的精度都得到了大幅度的提升.具体来说，ROPTV在3个数据集上的精度比GraphSAGE分别提高了5.9%, 6.5%和0.6%, 比FastGCN分别提高了3.4%, 5.1%和0.8%.该方法也被称为DropNode，其对删除边的影响是面向节点的和间接的.这说明本文从拓扑角度出发，采用面向边的DropEdge方法，其可以为训练保留所有节点特征，比DropNode方法表现出了更大的灵活性.

4.4 过平滑问题分析

当增加模型层数时，许多GCNs面临过平滑的问题——不同标签的节点变得难以区分.通过使用MADGap[13]来研究ROPTV是如何缓解这个现象的.MADGap是衡量节点表示的过平滑度的指标，MADGap值越小，说明节点表示越难以区分，因此过平滑问题越严重.具体实验结果如图3所示.

PORTV和GCN模型在Cora数据集上的过平滑现象，分别表示模型的MADGap值和不同层数的分类结果.可以观察到，随着模型层数加深到32层，GCN的2个指标都显著下降——MADGap值从70.10%下降到20.3%, 精度从81.5%下降到60.30%.这表明，随着模型层数的加深，由于发生了过平滑现象，模型性能急剧下降，即半监督节点分类的结果较差.然而，ROPTV方法随着模型层数的增加，虽然2个指标都在下降，但在模型加深到10层之前，下降的比较缓慢.并且直到层数加深到32层时，ROPTV的MADGap值和分类精度远高于GCN.这表明，随着模型层数的加深，当现有的代表性GCN模型非常容易受到过平滑的影响时，ROPTV在一定程度上缓解了过平滑现象，从而提高了深层GCNs在半监督节点分类任务上的性能.

(a)MADGap (b)分类结果图3 在Cora上的过平滑现象分析

5 结语

针对深层GCNs存在过平滑现象，从而影响其在半监督节点分类任务上的性能的问题，对GCNs的过平滑问题进行了定量的研究.引入了一个平滑度的定量度量，验证深层GCNs性能下降的主要原因是过平滑.然后从拓扑的角度出发，应用DropEdge技术和混合阶传播结合的方法来缓解深层GCNs存在的过平滑现象.实验结果表明，文中提出的方法缓解了深层GCNs模型存在的过平滑现象，在一定程度上提高了半监督节点分类的精度.