基于子图划分的多尺度节点分类方法_李浩然.pdf

第 40 卷第 3 期计算机应用与软件Vol.40 No 32023 年 3 月Computer Applications and SoftwareMar 2023基于子图划分的多尺度节点分类方法李浩然张红梅*(桂林电子科技大学信息与通信学院广西 桂林 541004)收稿日期:2020 07 11。国家自然科学基金项目(61461010);“认知无线电与信息处理”省部共建教育部重点实验室基金项目(CKL170103，CKL170104);广西教育大数据与网络安全协同创新中心项目;广西自然科学基金重点项目(2020GXNSFDA238001)。李浩然，硕士生，主研领域:智能信息处理。张红梅，教授。摘要为了解决深度图神经网络中存在的过平滑问题，提出一种基于子图划分的多尺度节点分类方法。该方法以 Graph-Inception 网络结构为核心，采用一种基于子图划分的数据预处理方法，通过改变图中的网络结构，优化特征聚集方式，有效地抑制了冗余搜索带来的过平滑问题;利用不同尺寸卷积核的组合来提取目标节点多尺度邻域的特征信息，以实现对图神经网络深度扩展的等效，一定程度上抑制了深层网络结构带来的过平滑问题。实验结果表明，该方法能够有效地抑制图神经网络中出现的过平滑问题，在基准数据集 PPI、eddit 和 Amazon 上的分类准确率都得到了不同程度的提高。关键词子图划分多尺度图神经网络节点分类中图分类号TP3文献标志码ADOI:10 3969/j issn 1000-386x 2023 03 044MULTI-SCALE NODE CLASSIFICATION METHOD BASED ON SUBGAPH PATITIONLi HaoranZhang Hongmei*(School of Information and Communication，Guilin University of Electronic Technology，Guilin 541004，Guangxi，China)AbstractIn order to solve the problem of over-smooth in the deep graph neural networks，a multi-scale nodeclassification method based on subgraph partition is proposed Taking the Graph-Inception as the core，this method useda subgraph partition as a data preprocess method The network structure in the graph was changed，the method of featureaggregation was optimized，which effectively suppressed the over-smooth caused by redundant features searching Theneighborhood feature information of the target node at multi-scale was extracted through the combination of convolutionkernels of different sizes，so as to achieve the equivalent of the depth expansion of the graph neural networks To acertain extent，the over-smooth problem caused by the deep network structure was suppressed Experimental results showthat the proposed method can effectively suppress the over-smooth problem in graph neural networks，and improve theclassification accuracy on the benchmark datasets PPI，eddit and Amazon to vary degreesKeywordsSubgraph partitionMulti-scaleGraph neural networksNode classification0引言近年来，随着图卷积神经网络(Graph Convolution-al Networks，GCNs)理论的发展和成熟，成为了当前图领域研究的重要理论。常见的图任务包括节点分类1、链接预测2 等。但传统图神经网络在对大规模图数据进行处理时通常存在着由于模型层数过深引起的过平滑问题，即迭代地进行邻域特征提取导致每个节点都学习到了图中其他所有节点的信息，使每个节点的特征信息都趋于一个相似的值，这对于节点分类是非常不利的。因此，图神经网络中的过平滑问题亟待进一步的研究。1相关工作1 1GCNs图神经网络(Graph Neural Networks，GNNs)这一282计算机应用与软件2023 年概念是由 Gori 等3 首次提出;Bruna 等4 则通过傅里叶变换将图的拉普拉斯矩阵从空间域转换至频域，基于卷积定理，创造性地提出了图卷积神经网络 GCNs的概念;后来，Kipf 等1 和 Defferrard 等5 在原始 GCNs的基础上分别提出了两种简化的方法，在降低算法复杂度的同时极大地提高了算法的效率。另外，为了解决算法的可扩展性问题，Hamilton 等6 和 Velickovic等7 又提出几种基于空间域的方法，通过聚集邻居节点的信息直接在图上执行卷积操作，同样达到了不错的效果。1 2DeepGCNs在图神经网络的研究中，不乏有人提出通过扩展模型的深度来提高算法的准确率。例如 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代表三阶邻居节点，虚线代表两个子图(连通分量)之间的连接。左图代表原始的图数据，经过三次邻域扩展后，中心节点提取到了图中所有节点的信息;右图则代表经过划分后的图，删除了连通分量之间的连线，将原始图分为了两个子图，经过两次邻域扩展后，中心节点提取了其所在子图内所有的邻域信息。对子图内邻域特征的提取已经足够表示中心节点的性质，所以，对整幅图的信息提取在邻域搜索的过程中浪费了大量的计算资源。本文采用图聚类算法 Metis11 对图数据进行子图划分，一般分为三个步骤:粗化阶段、初始划分阶段和细化阶段。首先，粗化过程主要是将原始图中的部分边和节点逐层合并为新的节点表示，并保存粗化过程中的节点映射关系，最后得到节点数较少但具有原图特征和性质的缩略图，以此降低划分过程中的计算复杂度。其次，在初始划分阶段将缩略图中的节点分为规模大致相等的 c 部分(c 值一般通过经验设定，并在实验中进行微调)。最后，在细化阶段按照节点映射关系逐步将缩略图还原为原始图，并在还原过程中对节点划分状态进行微调和优化。该算法旨在使子图内的连接远多于子图间的连接，以更完整地保留原始图数据的局部结构和特征信息。以 G=(V，E)为例，将其分为 c 个子图，表示为:G=G1，G2，Gt，Gc=(V1，E1)，(V2，E2)，(Vt，Et)，(Vc，Ec)(1)式中:Vt代表子图 Gt中的节点集合，Et是指 Vt中节点之间的连线，t 1，c。新图中的邻接矩阵与原始邻接矩阵之间的关系表示为:A=A+=A11A12A1cA21A22A2cAc1Ac2Acc(2)A=A11Acc=A1cAc1(3)式中:A 为 G 的邻接矩阵，也称为图 G 的对角近似矩阵;为误差矩阵;位于 A 中对角线上的 Att代表子图第 3 期李浩然，等:基于子图划分的多尺度节点分类方法283的邻接矩阵。Yt Y1，Y2，Yc 代表子图 Gt的标签向量，A=D1/2(A+I)D1/2代表 A 经过归一化的形式，D 为 A 的节点度矩阵，I 为单位矩阵。2 2Graph-Inception 网络结构本节结合 N-GCN 的网络框架，将对模型宽度的拓展工作应用于图神经网络研究领域，设计了一种 Graph-Inception 网络，网络结构如图 2 所示。图 2Graph-Inception 网络结构从节点特征信息流向的角度进行分析，当图神经网络采用了上述结构之后，模型中就同时存在了两种节点特征聚集的方式，分别是横向扩展的邻域特征聚集方式用来提取图的局部结构信息，以及纵向扩展的层间特征聚集方法用来提取图的层级表征信息。横向特征聚集方式对应 Graph-Inception 结构中的GCN，为每个图卷积神经网络设置不同尺寸的卷积核，以提取目标节点多尺度感受野内的邻域表征信息。本文选择了文献 5 中提出的图卷积神经网络，如式(4)所示，利用切比雪夫多项式对原始图卷积核4 进行化简。其中 K 代表切比雪夫多项式的阶数，特别地，也可以代表图卷积核的尺寸，通过改变 K 值便能改变图卷积核的感受野以提取到不同尺寸邻域内的信息。GCNK(X)=UK1k=0kTk(L)()X(4)式中:为需要训练的参数;X 为输入特征矩阵;L=L+I，L 为图的拉普拉斯矩阵，I 为单位矩阵;切比雪夫多项式可由 Tk(L)=2LTk 1(L)Tk 2(L)、T0(L)=I、T1(L)=L递归得到;U 为 L 矩阵分解后的特征向量矩阵;为非线性激活函数。另一方面，既然深层特征存在问题，那就将浅层的特征保留下来，通过对一些较小尺寸的卷积核进行组合，将所有卷积层的输出结果拼接为一个高维特征图，以实现对模型深度扩展的等效。纵向特征聚集方式就是基于这样的思想，通过对不同感受野下 GCN 的输出进行拼接，使结果包含不同层的层级表征。一方面，这样的做法即使不需要深层的网络模型也能提取到丰富的特征信息;另一方面，采用这样的多头机制，即使某一个图卷积神经网络的输入存在噪声或扰动时，分类子网的权重会向其他 GCN 中的信息进行转移，从而起到了一定的修正和优化作用。因此，将预处理后的图数据 G=G1，G2，Gc以及特征矩阵 X 输入 Graph-Inception 网络，则每个GCN 的输出可以等效地表示为:GCNK(A，X，W)=GCNK(A11，X1，W1)GCNK(A22，X2，W2)GCNK(Acc，Xc，Wc)(5)式中:X=(X1，X2，Xc)，Xc代表子图 Gc对应的特征矩阵。将所有 GCN 的输出经过拼接后输入循环神经网络(NN)，利用循环单元中的逻辑门结构为每个输出分配合适的权重，从而使特征矩阵中能自适应地融合进丰富的层级表征信息;再通过一个多层感知机(MLP)输出最终的特征;最后经过 Softmax 操作，便得到了 Graph-Inception 网络的输出:H=NN(GCN0(A，X，WGCN)GCNK1(A，X，WGCN)GCNKn(A，X，WGCN)(6)Y=Softmax(MLP(H)(7)式中:Y 代表模型预测节点的标签矩阵。2 3算法步骤本节将给出基于子图划分的多尺度节点分类方法的具体步骤:Step1首先利用预处理方法对原始图 G 进行子图划分。Step2将每个子图中的所有节点视为一个 batch，输入 Graph-Inception 网络，并经过 MLP 处理后得到模型的输出。Step3使用模型预测的分类结果与真实标签计算负对数似然损失 NLL，并计算损失函数的梯度，利用梯度对参数进行优化。Step4开始训练，重复 Step2、Step3，直至损失函数连续 10 次迭代后不再下降时，停止训练。3实验仿真与分析3 1实验环境和数据集介绍实验硬件环境:8 核 Inter()Xeon()处理器，32 GB内存;NVIDIA GeForce GTX 1080Ti 的 GPU，16 GB 内存。软件环境为64 位 Windows 10、CUDA10 2、Python 3 7、284计算机应用与软件2023 年Pytorch1 5 0。为了研究和验证本文实验的有效性，本文选择了三个节点任务数据集，下面对数据集中的内容进行简单介绍。PPI:是一个包含了 24 幅图的蛋白质相互作用网络数据集，每幅图代表不同的人体组织。节点代表不同的蛋白质，节点特征包括位置基因信息、基因序列特征和免疫学特征，预测任务是对蛋白质的功能进行判断;eddit:是一个包含了 eddit 网站中 232 000个帖子的社交数据集，图中节点代表帖子，如果两个帖子被同一个用户评论过，则建立一条边，节点的特征通过 Glove 词嵌入方法生成，预测任务是对帖子所属的子论坛进行判断;Amazon:该数据集包括亚马逊网站中 Computers 和 Photo 品类的共同购买关系图，其中节点代表商品，节点特征是由商品评价的词袋编码产生，边缘表示经常一起购买的产品，预测任务是对产品的类别进行判断。数据集主要参数如表 1 所示。表 1数据集主要参数数据集图数节点数边数特征数类别数PPI242 37334 11350121eddit1232 96557 309 39060241Amazon127 504983 44476783 2模型与超参数设置模型设置:本文中的模型采用了图 2 所示的网络结构，并采用 4 个 GCN 网络，NN 采用 LSTM 网络。超参数设置:参照文献 10中采用四种感受野K 的组合，并分别设置为 1、2、3、4;参照文献 9将PPI 数据集划分为50 个子图，将 eddit 数据集划分为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 和 eddit 数据集上，本文方法分别得到了 0 84 百分点和 3 07 百分点的提升。可以看出，本文方法对于规模越大的数据集准确率提升越明显，这是因为在子图划分的过程中，一些边被屏蔽导致部分信息丢失，大数据集仍能保留多数特征信息，而越小的数据集由于信息损失后不足以保证自身表示的完整性。另一方面，从表 2 中数据看出，使用 N-GCN 对eddit 数据进行处理时，由于数据集过大以及 N-GCN算法机制的原因，导致训练时占用内存过高，导致 GPU溢出，无法正常进行训练。侧面验证了基于子图划分的预处理方法的必要性。表 2模型检测准确率(%)模型数据集PPIedditAmazonN-GCN10 97 42内存溢出90 40Cluster-GCN9 98 5890 4290 74Graph-Inception99 0293 4991 583 4计算效率分析为了验证本文方法的计算效率，表 3 展示了 N-GCN 和 Cluster-GCN 以及 Graph-Inception 方法在三个基准数据集上的计算耗时对比，以测试集中所有节点的测试时间作为评价指标。可以看出，Cluster-GCN 由于采用了子图划分的数据预处理方法，部分节点之间不用进行信息交换，所需的训练时间最短;N-GCN 由于采用了多个 GCN 的组合，所需训练时间较多;而本文方法则是在 N-GCN 的基础上，对数据进行了预处理，优化了特征提取过程。因此本文方法训练所需的时间，与 N-GCN 相比较少，而与 Cluster-GCN 相比较多。表 3模型检测耗时对比单位:s模型数据集PPIedditAmazonN-GCN10 0 334 6内存溢出1 068 3Cluster-GCN9 0 309 524 535 70 601 9Graph-Inception0 321 028 271 90 816 53 5损失值分析图 3 图 5 展示了 N-GCN 和 Cluster-GCN 以及Graph-Inception 方法在三个基准数据集上的损失函数曲线变化。通过对比可以看出，本文方法在训练过程中可以使损失曲线更早地收敛，且损失值最终能够收敛至一个更小的数值，这是由于循环单元中的门结构对于噪声信息的传播具有很好的抑制能力。其中，Cluster-GCN 相比于另外两个模型损失值较高，原因可第 3 期李浩然，等:基于子图划分的多尺度节点分类方法285能在于子图划分导致部分信息丢失，侧面验证了多尺度下特征提取的必要性。图 3eddit 数据集损失值变化图 4PPI 数据集损失值变化图 5Amazon 数据集损失值变化3 6子图划分分析图 6 图 8 展示了采用不同子图数下本文方法在三个基准数据集上的检测准确率和时间变化。可以看出，随着子图数的增加，检测时间也随之变短，这是由于每个子图内节点数也在逐渐减少;通过实验，数据集PPI、eddit 和 Amazon 的检测准确率分别在子图数为50、1 500 和 200 处取得最优值。因此为了保证在检测时间尽可能短的情况下检测准确率较高，选择此组子图数作为模型的超参数。图 6不同子图数 PPI 数据集检测准确率、时间变化图 7不同子图数 eddit 数据集检测准确率、时间变化图 8不同子图数 Amazon 数据集检测准确率、时间变化3 7多尺度感受野分析为了验证 Graph-Inception 方法中感受野对模型检测准确率的影响，表4 展示了不同尺度感受野组合下本文方法在三个基准数据集上的准确率变化，其中 K 表示采用的 k 1，K 的感受野组合。可以看出，模型的检测准确率在如下范围内随 K 值变大而增高，这是由于感受野越大，提取到的层级特征越丰富。但是感受野过大同样会带来过平滑现象导致的检测准确率降低，这在规模较小的 PPI 数据集上得到了体现。286计算机应用与软件2023 年表 4不同感受野下检测准确率对比数据集K12345PPI0 971 60 985 40 991 60 990 20 986 3eddit0 880 30 897 10 916 00 934 90 942 3Amazon0 885 00 898 10 914 80 914 80 926 84结语本文介绍了一种基于子图划分的多尺度节点分类方法，旨在从网络结构和特征聚集方式两方面抑制图神经网络中的过平滑问题。首先以子图划分的数据预处理方式改变原始图中的邻域结构，然后通过使用不同尺寸卷积核的组合对目标节点多尺度下的邻域特征信息进行融合。最后通过实验证明，本文方法能够有效抑制图神经网络中的过平滑问题，在基准节点分类数据集 PPI、eddit 和 Amazon 上的预测准确率都取得了不同程度的提高。参考文献1 Kipf T N，Welling M Semi-supervised classification withgraph convolutional networks EB arXiv:160902907，20162 Zhang M，Chen Y Link prediction based on graph neuralnetworksC/Advances in Neural Information ProcessingSystems，2018:5165 51753 Gori M，Monfardini G，Scarselli F A new model for learn-ing in graph dominas C/IEEE International Joint Confer-ence on Neural Networks，2005:729 7344 Bruna J，Zaremba W，Szalam A，et al Spectral networksand locally connected networks on graphs EB arXiv:160902907，20165 Defferrard M，Bresson X，Vandergheynst P Convolutionalneural networks on graphs with fast localized spectral filtering C/Advances in Neural Information Processing Systems，2016:3844 38526 Hamilton W，Ying Z，Leskovec J Inductive representationlearning on large graphsC/Advances in Neural Informa-tion Processing Systems，2017:1024 10347 Velic kovicP，Cucurull G，Casanova A，et al Graph atten-tion networks EB arXiv:1710 10903，20178 Li Q，Han Z，Wu X M Deeper insights into graph convolu-tional networks for semi-supervised learning C/32ndAAAI Conference on Artificial Intelligence，20189 Chiang W L，Liu X，Si S，et al Cluster-gcn:An efficientalgorithm for training deep and large graph convolutional net-works C/25th ACM SIGKDD International Conference onKnowledge Discovery Data Mining，2019:257 266 10 Abu-El-Haija S，Kapoor A，Perozzi B，et al N-GCN:Multi-scale graph convolution for semi-supervised node classifica-tion EB arXiv:1802 08888，2018 11 Karypis G，Kumar V A fast and high quality multilevelscheme for partitioning irregular graphs J SIAM Journal onScientific Computing，1998，20(1):359 392(上接第 275 页)4 Tomasi C，Manduchi Bilateral filtering for gray and colorimagesC/International Conference on Computer VisionIEEE，20025 Petschnigg G，Szeliski，Agrawala M，et al Digital pho-tography with flash and no-flash image pairsJ ACMTransactions on Graphics，2004，23(3):664 6726 Le A V，Jung S W，Won C S Directional joint bilateral fil-ter for depth imagesJ Sensors，2014，14(7):11362 113787 Esfahani M A，Pourreza H Kinect depth recovery based onlocal filters and plane primitivesC/Integral Methods onScience and Engineering，20168 Deng H，Wu J，Zhu L，et al Texture edge-guided depth re-covery for structured light-based depth sensor J Multime-dia Tools Applications，2017，76(3):4211 42269 Dong W，Shi G，Li X，et al Color-guided depth recoveryvia joint local structural and nonlocal low-rank regularization J IEEE Transactions on Multimedia，2017，19(2):293 301 10 Wei L，Chen X，Jie Y，et al obust color guided depthmap restorationJ IEEE Transactions on Image Process-ing，2017，26(1):315 328 11 He L Y，Wu S S，Wu C Y obust laser strip extraction forthree-dimensional reconstruction based on a cross-structuredlight sensor J Applied Optics，2017，56(4):823 832 12 Li Y H，Zhou J B，Huang F S，et al Sub-pixel extraction oflaser stripe center using an improved gray-gravity method J Sensors，2017，17(4):814 13 李明磊，宗文鹏，李广云，等 基于体素生长的点云结构直线段提取 J 光学学报，2018，38(1):152 162 14 聂建辉，刘烨，高浩，等 基于符号曲面变化度与特征分区的点云特征线提取算法 J 计算机辅助设计与图形学学报，2015，27(12):2332 2339 15 Wang Z Y，Hu J H，Wang S Z，et al Trilateral constrainedsparse representation for Kinect depth hole fillingJ Pat-tern ecognition Letters，2015，65(1):95 102 16 Mandal S，Bhavsar A，Sao A K Depth map restoration fromundersampled data J IEEE Transactions on Image Process-ing，2017，26(1):119 134 17 Bumsub H，Minsu C，Jean P obust image filtering usingjoint static and dynamic guidanceC/Computer Vision Pattern ecognition IEEE，2015