基于子图划分的多尺度节点分类方法

李浩然 张红梅

(桂林电子科技大学信息与通信学院 广西 桂林 541004)

0 引 言

近年来,随着图卷积神经网络(Graph Convolutional Networks,GCNs)理论的发展和成熟,成为了当前图领域研究的重要理论。常见的图任务包括节点分类[1]、链接预测[2]等。但传统图神经网络在对大规模图数据进行处理时通常存在着由于模型层数过深引起的过平滑问题,即迭代地进行邻域特征提取导致每个节点都学习到了图中其他所有节点的信息,使每个节点的特征信息都趋于一个相似的值,这对于节点分类是非常不利的。因此,图神经网络中的过平滑问题亟待进一步的研究。

1 相关工作

1.1 GCNs

图神经网络(Graph Neural Networks,GNNs)这一概念是由Gori等[3]首次提出;Bruna等[4]则通过傅里叶变换将图的拉普拉斯矩阵从空间域转换至频域,基于卷积定理,创造性地提出了图卷积神经网络GCNs的概念;后来,Kipf等[1]和Defferrard等[5]在原始GCNs的基础上分别提出了两种简化的方法,在降低算法复杂度的同时极大地提高了算法的效率。另外,为了解决算法的可扩展性问题,Hamilton等[6]和Velickovic等[7]又提出几种基于空间域的方法,通过聚集邻居节点的信息直接在图上执行卷积操作,同样达到了不错的效果。

1.2 DeepGCNs

在图神经网络的研究中,不乏有人提出通过扩展模型的深度来提高算法的准确率。例如Kipf等[1]采用残差连接的方法对GCNs模型进行堆叠,但当网络增至2层以上时,模型性能反而会随着层数的叠加而下降。Li等[8]提出过平滑问题是限制图卷积神经网络深度扩展的主要原因。这是由于GCNs通过逐层迭代来聚集高阶邻域信息,在经过足够多层网络后,同一连通分量内每个节点都会聚集到各自的特征信息,导致该连通分量内所有节点的特征信息都会收敛于一个相同的值。于是Chiang等[9]提出了一种Cluster-GCN,利用改变网络结构来优化特征提取过程,一定程度上缓解了过平滑的问题,但子图划分同样带来了部分特征信息的损失,对算法准确率造成了影响。Abu-EI-Haija等[10]则设计了一种具有优良局部拓扑结构的N-GCN网络,通过对较小尺寸的卷积核进行组合,实现了对深层特征的等效,避免了过平滑的问题,但在处理大规模数据集时,由于组合了多个卷积核的算法机制,导致模型对于显存的消耗十分巨大。

2 方法设计

2.1 子图划分方法

为了解决图神经网络中的过平滑问题,在训练前采用一种数据预处理方法,具体是将原始图划分为多个子图,每个子图各属于一个连通分量,各个连通分量之间通过边缘互相连接,但并不进行信息交换;连通分量内部节点互相连接,以此限制节点只能在其所属的连通分量内进行特征的聚集和更新。将图划分出越多的子图,过平滑现象就会越不明显,在极端情况下,将每个节点作为一个子图,节点之间都不进行信息传递,则完全不会出现过平滑的问题,但同时节点也无法学习到邻域内的信息。图1展示了节点在两幅图上的邻域扩展过程。

图1 节点邻域扩展过程示例

图1中,以节点0作为中心节点进行分析,节点1代表一阶邻居节点,节点2代表二阶邻居节点,节点3代表三阶邻居节点,虚线代表两个子图(连通分量)之间的连接。左图代表原始的图数据,经过三次邻域扩展后,中心节点提取到了图中所有节点的信息;右图则代表经过划分后的图,删除了连通分量之间的连线,将原始图分为了两个子图,经过两次邻域扩展后,中心节点提取了其所在子图内所有的邻域信息。对子图内邻域特征的提取已经足够表示中心节点的性质,所以,对整幅图的信息提取在邻域搜索的过程中浪费了大量的计算资源。

本文采用图聚类算法Metis[11]对图数据进行子图划分,一般分为三个步骤:粗化阶段、初始划分阶段和细化阶段。首先,粗化过程主要是将原始图中的部分边和节点逐层合并为新的节点表示,并保存粗化过程中的节点映射关系,最后得到节点数较少但具有原图特征和性质的缩略图,以此降低划分过程中的计算复杂度。其次,在初始划分阶段将缩略图中的节点分为规模大致相等的c部分(c值一般通过经验设定,并在实验中进行微调)。最后,在细化阶段按照节点映射关系逐步将缩略图还原为原始图,并在还原过程中对节点划分状态进行微调和优化。该算法旨在使子图内的连接远多于子图间的连接,以更完整地保留原始图数据的局部结构和特征信息。以G=(V,E)为例,将其分为c个子图,表示为:

[(V1,E1),(V2,E2),…,(Vt,Et),…,(Vc,Ec)]

(1)

式中:Vt代表子图Gt中的节点集合,Et是指Vt中节点之间的连线,t∈[1,c]。新图中的邻接矩阵与原始邻接矩阵之间的关系表示为:

2.2 Graph-Inception网络结构

本节结合N-GCN的网络框架,将对模型宽度的拓展工作应用于图神经网络研究领域,设计了一种Graph-Inception网络,网络结构如图2所示。

图2 Graph-Inception网络结构

从节点特征信息流向的角度进行分析,当图神经网络采用了上述结构之后,模型中就同时存在了两种节点特征聚集的方式,分别是横向扩展的邻域特征聚集方式用来提取图的局部结构信息,以及纵向扩展的层间特征聚集方法用来提取图的层级表征信息。

横向特征聚集方式对应Graph-Inception结构中的GCN,为每个图卷积神经网络设置不同尺寸的卷积核,以提取目标节点多尺度感受野内的邻域表征信息。本文选择了文献[5]中提出的图卷积神经网络,如式(4)所示,利用切比雪夫多项式对原始图卷积核[4]进行化简。其中K代表切比雪夫多项式的阶数,特别地,也可以代表图卷积核的尺寸,通过改变K值便能改变图卷积核的感受野以提取到不同尺寸邻域内的信息。

另一方面,既然深层特征存在问题,那就将浅层的特征保留下来,通过对一些较小尺寸的卷积核进行组合,将所有卷积层的输出结果拼接为一个高维特征图,以实现对模型深度扩展的等效。纵向特征聚集方式就是基于这样的思想,通过对不同感受野下GCN的输出进行拼接,使结果包含不同层的层级表征。一方面,这样的做法即使不需要深层的网络模型也能提取到丰富的特征信息;另一方面,采用这样的多头机制,即使某一个图卷积神经网络的输入存在噪声或扰动时,分类子网的权重会向其他GCN中的信息进行转移,从而起到了一定的修正和优化作用。

式中:X=‖(X1,X2,…,Xc),Xc代表子图Gc对应的特征矩阵。

将所有GCN的输出经过拼接后输入循环神经网络(RNN),利用循环单元中的逻辑门结构为每个输出分配合适的权重,从而使特征矩阵中能自适应地融合进丰富的层级表征信息;再通过一个多层感知机(MLP)输出最终的特征;最后经过Softmax操作,便得到了Graph-Inception网络的输出:

Y=Softmax(MLP(H))

(7)

式中:Y代表模型预测节点的标签矩阵。

2.3 算法步骤

本节将给出基于子图划分的多尺度节点分类方法的具体步骤:

Step1首先利用预处理方法对原始图G进行子图划分。

Step2将每个子图中的所有节点视为一个batch,输入Graph-Inception网络,并经过MLP处理后得到模型的输出。

Step3使用模型预测的分类结果与真实标签计算负对数似然损失NLL,并计算损失函数的梯度,利用梯度对参数进行优化。

Step4开始训练,重复Step 2、Step 3,直至损失函数连续10次迭代后不再下降时,停止训练。

3 实验仿真与分析

3.1 实验环境和数据集介绍

实验硬件环境:8核Inter(R)Xeon(R)处理器,32 GB内存;NVIDIA GeForce GTX 1080Ti的GPU,16 GB内存。软件环境为64位Windows 10、CUDA10.2、Python 3.7、Pytorch1.5.0。

为了研究和验证本文实验的有效性,本文选择了三个节点任务数据集,下面对数据集中的内容进行简单介绍。PPI:是一个包含了24幅图的蛋白质相互作用网络数据集,每幅图代表不同的人体组织。节点代表不同的蛋白质,节点特征包括位置基因信息、基因序列特征和免疫学特征,预测任务是对蛋白质的功能进行判断;Reddit:是一个包含了Reddit网站中232 000个帖子的社交数据集,图中节点代表帖子,如果两个帖子被同一个用户评论过,则建立一条边,节点的特征通过Glove词嵌入方法生成,预测任务是对帖子所属的子论坛进行判断;Amazon:该数据集包括亚马逊网站中Computers和Photo品类的共同购买关系图,其中节点代表商品,节点特征是由商品评价的词袋编码产生,边缘表示经常一起购买的产品,预测任务是对产品的类别进行判断。数据集主要参数如表1所示。

表1 数据集主要参数

3.2 模型与超参数设置

模型设置:本文中的模型采用了图2所示的网络结构,并采用4个GCN网络,RNN采用LSTM网络。

超参数设置:参照文献[10]中采用四种感受野K的组合,并分别设置为1、2、3、4;参照文献[9]将PPI数据集划分为50个子图,将Reddit数据集划分为1 500个子图,将Amazon数据集划分为200个子图;初始学习率设置为0.005;每经过200个epoch将学习率降低为原来的0.5倍;batch-size设置为128。选择Adam作为参数优化器,使用L2正则化防止训练时过拟合,选择负对数似然函数NLL作为损失函数。

3.3 准确率分析

为了验证本文方法的有效性,采用N-GCN和Cluster-GCN作为对比模型进行实验,检测准确率对比如表2所示。可以看出,本节提出的Graph-Inception网络在节点分类任务中的准确率表现上取得了明显的提升。与Cluster-GCN相比,在总节点数较少的PPI数据集上,本文方法的准确率提高了0.44百分点;而在节点数目相对较多的Amazon和Reddit数据集上,本文方法分别得到了0.84百分点和3.07百分点的提升。可以看出,本文方法对于规模越大的数据集准确率提升越明显,这是因为在子图划分的过程中,一些边被屏蔽导致部分信息丢失,大数据集仍能保留多数特征信息,而越小的数据集由于信息损失后不足以保证自身表示的完整性。

另一方面,从表2中数据看出,使用N-GCN对Reddit数据进行处理时,由于数据集过大以及N-GCN算法机制的原因,导致训练时占用内存过高,导致GPU溢出,无法正常进行训练。侧面验证了基于子图划分的预处理方法的必要性。

表2 模型检测准确率(%)

3.4 计算效率分析

为了验证本文方法的计算效率,表3展示了N-GCN和Cluster-GCN以及Graph-Inception方法在三个基准数据集上的计算耗时对比,以测试集中所有节点的测试时间作为评价指标。可以看出,Cluster-GCN由于采用了子图划分的数据预处理方法,部分节点之间不用进行信息交换,所需的训练时间最短;N-GCN由于采用了多个GCN的组合,所需训练时间较多;而本文方法则是在N-GCN的基础上,对数据进行了预处理,优化了特征提取过程。因此本文方法训练所需的时间,与N-GCN相比较少,而与Cluster-GCN相比较多。

表3 模型检测耗时对比 单位:s

3.5 损失值分析

图3-图5展示了N-GCN和Cluster-GCN以及Graph-Inception方法在三个基准数据集上的损失函数曲线变化。通过对比可以看出,本文方法在训练过程中可以使损失曲线更早地收敛,且损失值最终能够收敛至一个更小的数值,这是由于循环单元中的门结构对于噪声信息的传播具有很好的抑制能力。其中,Cluster-GCN相比于另外两个模型损失值较高,原因可能在于子图划分导致部分信息丢失,侧面验证了多尺度下特征提取的必要性。

图3 Reddit数据集损失值变化

图4 PPI数据集损失值变化

图5 Amazon数据集损失值变化

3.6 子图划分分析

图6-图8展示了采用不同子图数下本文方法在三个基准数据集上的检测准确率和时间变化。可以看出,随着子图数的增加,检测时间也随之变短,这是由于每个子图内节点数也在逐渐减少;通过实验,数据集PPI、Reddit和Amazon的检测准确率分别在子图数为50、1 500和200处取得最优值。因此为了保证在检测时间尽可能短的情况下检测准确率较高,选择此组子图数作为模型的超参数。

图7 不同子图数Reddit数据集检测准确率、时间变化

图8 不同子图数Amazon数据集检测准确率、时间变化

3.7 多尺度感受野分析

为了验证Graph-Inception方法中感受野对模型检测准确率的影响,表4展示了不同尺度感受野组合下本文方法在三个基准数据集上的准确率变化,其中K表示采用的k[1,K]的感受野组合。可以看出,模型的检测准确率在如下范围内随K值变大而增高,这是由于感受野越大,提取到的层级特征越丰富。但是感受野过大同样会带来过平滑现象导致的检测准确率降低,这在规模较小的PPI数据集上得到了体现。

表4 不同感受野下检测准确率对比

4 结 语

本文介绍了一种基于子图划分的多尺度节点分类方法,旨在从网络结构和特征聚集方式两方面抑制图神经网络中的过平滑问题。首先以子图划分的数据预处理方式改变原始图中的邻域结构,然后通过使用不同尺寸卷积核的组合对目标节点多尺度下的邻域特征信息进行融合。最后通过实验证明,本文方法能够有效抑制图神经网络中的过平滑问题,在基准节点分类数据集PPI、Reddit和Amazon上的预测准确率都取得了不同程度的提高。