基于图结构增强的图神经网络方法

摘" " 要： 针对图卷积网络（GCNs）在面对低同质性的图结构时性能骤降问题，提出了一种新颖的基于图结构增强的图神经网络方法，用于学习改善的图节点表示。首先将节点信息通过消息传播和聚合，得到节点的初始表示；然后计算节点表示的相似性度量，得到图的同质结构；最后融合图的原始结构和同质结构进行节点的信息传递得到节点表示用于下游任务。结果表明：在6个公开的数据集上，所提算法在节点分类的多个指标上均优于对比算法，特别是在同质性较低的4个数据集上，所提算法的准确度（ACC）分数分别超过最高基准5.53%、6.87%、3.08%、4.00%，宏平均（F1）值分别超过最高基准5.75%、8.06%、6.46%、5.61%，获得了远高于基准的优越表现，表明所提方法成功改善了图数据的结构，验证了该算法对图结构优化的有效性。

关键词： 图结构增强； 相似性度量； 图卷积网络； 节点分类

中图分类号： TP183" " " " " " 文献标志码： A" " " " " " " " 文章编号： １６７１－０２４Ｘ（２０24）０3－００58－08

Graph neural network method based on graph structure enhancement

ZHANG Fang1，2， SHAN Wanjin3， WANG Wen1，2

（1. School of Life Sciences， Tiangong University， Tianjin 300387， China； 2. Tianjin Key Laboratory of Optoelectronic Detection Technology and System， Tiangong University， Tianjin 300387， China； 3. School of Electronics and Information Engineering， Tiangong University， Tianjin 300387， China）

Abstract： In response to the problem of sudden performance degradation in graph convolutional networks（GCNs） facing low homogeneity graph structures， a novel graph structure enhancement method is proposed for learning improved graph node representations. Firstly， the node information is propagated and aggregated by messages to obtain an initial representation of the nodes. Then the similarity metric of the node representation is calculated to obtain the homogeneous structure of the graph. Finally， the original structure of the graph and the homogeneous structure are fused for node information transfer to obtain the node representation for downstream tasks. The results show that the proposed algorithm outperforms the comparison algorithm in several metrics of node classification on six publicly available datasets， especially on the four datasets with low homogeneity， the ACC scores of the proposed algorithm exceed the highest benchmark by 5.53%， 6.87%， 3.08% and 4.00%， and the F1 values exceed the highest benchmark by 5.75%， 8.06%， 6.46% and 5.61%， respectively， obtaining superior performance well above the benchmark， indicating that the proposed method successfully improves the structure of graph data and verifies the effectiveness of the algorithm for graph structure optimization.

Key words： graph structure enhancement； similarity measure； graph convolution network； node classification

为了实现对各种信息网络的可靠定量分析，获取图结构数据的高质量表示已成为当前的热门话题之一。图神经网络（graph neural networks， GNNs）[1]在从知识谱图[2]到社交网络[3]以及金融网络的各种应用中的表示学习非常强大。近年来，GNNs发展出了许多人工神经网络，例如图卷积网络（GCN）[1]、图注意力网络（GAT）[4]和图同构网络（GIN）[5]等。对于GNNs，每个节点可以通过聚合节点本身及其邻居的特征表示来迭代更新其特征表示。邻域通常被定义为图中的相邻节点集，GNNs可以采用多种聚合函数聚合其邻居信息来迭代更新其特征表示[6]，例如求和、最大值和平均值[7-9]。图学习的基本思想是提取图结构数据中的高维信息，并将其嵌入到低维向量表示中。这些节点表示向量可以潜在地用于各种下游任务，例如节点分类[10]、链路预测[11]、图分类[12]和推荐系统[13]。

但是，由于现有的GNNs依赖于节点的信息传播[14]，所以其邻居的类别会直接影响节点获得的消息表示。当邻居具有正确的信息即节点及其邻居属于同一类时，节点经过网络传播后会获得较好的表示。而当节点和它的邻居不属于同一类，它将会接收到相对错误的信息。在统计样本的连接关系时会获得较为真实的边连接，但是具有连接关系的样本之间可能只具有弱相关，并不属于同一类，而同一类的样本在现实生活中可能并没有交集，这样统计而来的图数据具有较低的同质性[15]。同质性即连接的节点通常属于同一类，可分为边同质性（edge homophily， hedge） [16]以及节点同质性（node homophily， hnode）[8]，具体的同质性定义在符号定义章节给出。

所以现阶段如何得到神经网络所期待的同质性较高的图结构成为一个具有挑战的话题[17]。上述问题引发了围绕图结构学习（graph structure learning， GSL）[18]这一中心主题的大量研究，现有的解决这一问题的方法要么固定节点间的相似度图，要么同时学习GNNs参数和图结构。在这两种情况下，一个主要目标是构建或学习相对于标签具有高度同质性的图结构，以帮助GNNs分类。后一种方法被称为潜在图学习（latent graph learning）[19]，与前一种方法相比，通常会产生更高的预测性能。但是上述方法在完成重构图结构的同时会丢弃掉原始的图结构[18]，这是不可取的，因为原始的图结构代表现实生活中的真实连接，即使它们不是同质的。当抛弃原始图结构时，图数据已然不复存在，只剩下孤立的样本，这违背了GNNs的初衷。

为应对上述问题，本文提出了一种基于相似性度量的图结构增强学习方法，获取节点表示，以用于下游任务。首先，将原始节点特征和邻接矩阵数据经过GCN编码进行节点的传播和聚合；其次将初步得到的节点表示进行相似性计算，进而将具有较高相似度的节点之间赋予权重边；然后把得到的权重边加上原始边和节点特征输入至GCN编码器中得到节点的高级表示；最后将高级节点表示与给定的标签进行对比优化。在此节点高级表示的基础上可以对节点进行分类任务。

1 相关工作

推断图结构的一种方法是选择相似性度量，并将两个节点之间的边权重设置为它们的相似性[19]。为了获得稀疏结构，可以创建k近邻相似图，仅连接相似度超过某个预定义阈值的节点对。Wang等[20]通过在GNN的每一层中基于嵌入在该层中的节点的相似性创建新的图来扩展这一思想。Halcrow等[21]不是选择单一的相似性度量，而是融合了多个相似性度量。这些方法的预测质量在很大程度上取决于相似性度量的选择。

另一种方法是从完全连通的图开始，并使用可用的元数据来分配边权重，或者使用GNN变体，其经由注意力机制为每条边提供权重[22]。这种方法已经用于计算机视觉[23]、自然语言处理[24]和少样本学习[25]。这种方法的复杂性迅速增加，使其仅适用于小尺寸的图。刘杰等[26]建议为每个节点定义本地邻居，并且仅假设这些本地邻居是完全连接的。他们的方法依赖于一个初始的图结构来定义当地社区。

2 模 型

本章介绍所提出的基于图结构增强的图神经网络方法，并具体介绍所提出方法的关键技术以及优化方法。图1展示了本文方法的整体框架图。首先对原始的节点特征和邻接矩阵通过GCN进行消息的传播和聚合得到节点表示，计算节点表示的相似度作为生成的权重边，然后将节点表示和原始邻接矩阵以及生成的权重边作为下一层GCN编码器的输入；最后由GCN编码出高级节点表示HS。HS即为最终的节点表示用于类别预测对节点进行分类。

2.1 符号定义

首先定义本文用到的各种变量及其符号表示。本文将无向图定义为G = （V，E），使用的图数据集，它们的节点集用V = {v1，v2，…，vN}表示，vi代表节点i；节点特征矩阵用X = {x1，x2，…，xN}∈R表示。其中xi表示节点vi的特征向量，N代表节点数量，d0代表节点的特征维度。A∈R表示图的邻接矩阵，其中边ei，j = （vi，vj）∈E意味着节点vi和vj具有连接关系，|E|代表边的数量。表1给出了本文的符号定义。

定义1" " 边同质性：指连接同一类节点的边占总边数的比例：

hedge = "（1）

定义2" " 节点同质性：指节点的一阶邻居中和节点属于同一类的节点所占的比例：

hnode = "（2）

式中：d为节点vi的一阶邻居的数量；d 为和节点vi具有相同类别标签的邻居数量。

2.2 基于相似性度量的图结构增强学习框架

本文的图结构增强学习模型框架如图1所示。框架的每层由图结构重构和图编码两部分组成，是一种融合原始图拓扑结构并重构为同质图的人工神经网络，致力于得到节点的高级表示并应用于下游任务。

图结构重构致力于连接在原始图中没有连接关系但具有较高相似性的节点，由图编码器GCN和相似性度量组成，使节点能够正确聚合同类节点的信息，从而得到正确的节点表示。将节点的特征矩阵X和邻接矩阵A作为GCN的输入，经GCN对节点进行信息的传播和聚合得到低维的节点表示：

H0 = σ（XWGCN） （3）

式中：H0∈R 为经过GCN编码得到的节点表示矩阵；为归一化的邻接矩阵；WGCN为GCN的网络权重参数；σ（·）为非线性激活函数，本文采用ReLU非线性激活函数。

接着计算节点之间的相似性，可以采用的相似性度量有余弦相似度、欧氏距离和曼哈顿距离等。为了计算的简单，本文采用向量的内积作为节点之间的相似性度量：

si，j = h· h （4）

式中：si，j为节点，表示hi和hj之间的相似性度量，hi，hj∈H0。则对于整个图来说各节点之间的相似性度量可表示为：

S0 = H0·H" " " " "（5）

式中：S0为节点的相似性矩阵。

最后取每个节点的前Top_k个相似节点进行连接，除去相似度较低的连接，即采取kNN策略，增加图结构的同质性， 并归一化相似度矩阵：

0 = normalize（kNN（S0）） （6）

在图结构重构后即可进行图编码工作得到高级节点表示。原始邻接矩阵代表图数据的真实连接，能够代表节点之间的真实关系，但这种关系可能并不是网络所期望的同质性较高的连接关系，所以需要将原始图邻接矩阵和生成的相似度矩阵以及节点表示H0作为输入传入下一层GCN编码器，继续重构图结构。经过最后一层GCN编码器得到高级节点表示：

Hs = ReLU（GCN（ + s-1，Hs-1））（7）

Hs经过softmax进行类别预测：

Z = softmax（Hs）（8）

对于半监督多类分类，本文评估所有带标签样本节点的交叉熵损失：

L = -Yi， j ln Zi，j（9）

式中：YL为具有标签Y的节点索引集；C为类别数。经过反向传播来优化神经网络的参数，从而达到较好的结果。

3 实 验

本文基于引文网络图数据集和维基百科图数据集，将提出的用于节点分类的潜在图学习方法与其他方法进行了对比，并且分析了实验结果，通过消融实验展示了算法实现的关键部分。

3.1 数据集

为了验证本文所提的图结构增强学习网络的有效性，本文选取了6个图数据集进行实验，包括Cora和Citeseer 2个具有较高同质性的引文网络图数据集，以及Chameleon、Squirrel、Actor和 Wisconsin 4个具有较低同质性的维基百科图数据集（https：//github.com/CUAI/Non-Homophily-Large-Scale）。6个数据集的信息在表 2中给出。

表2中，Cora和Citeseer数据集跟随文献[1]的分割方式，Chameleon、Squirrel、Actor和Wisconsin按照文献[27]的分割方式。

3.2 对比方法

为了验证本文所提出的潜在图学习方法的有效性，本文将其与GCN[1]、GAT[4]两种经典的网络以及先进的图结构增强网络SLAPS[18]进行对比：

（1） GCN是一种半监督图卷积网络框架，它聚集来自邻居的输入以学习节点表示。

（2） GAT是一种使用注意力机制聚集节点特征的半监督图神经网络框架。

（3） SLAPS是一种图结构学习框架，通过计算节点之间的相似度生成权重边，并且通过额外的自监督任务解决图结构增强中存在的监督匮乏问题。

3.3 实验设置

本文采用GCN作为编码器，使用Adam优化器来训练，并且将训练的初始学习率设置为0.001。对6个数据集在本文方法以及对比方法上分别进行了节点的多分类实验，对于每个方法均采用GCN中使用的softmax作为分类器。对于节点分类，本文一方面采用准确度（accuracy， ACC）和宏平均（Macro_F1， F1）作为评价指标，并且采用10次实验取平均值的方法来减少随机误差；另一方面，为了进一步评价方法的有效性，本文对学习到的节点表示还进行了不同类型的聚类可视化实验，这样可以直观地看出节点表示的表现力。

3.4 实验结果分析

本文对比了2种经典的网络以及1种先进的图结构学习网络用于半监督节点分类。表3展示了节点分类在ACC和F1指标上的所有结果，最佳结果标记为粗体。

从表3可以观察到，在每个数据集的分类结果中，本文提出的方法均好于其他对比方法，在多个指标的节点分类实验中，本文所提方法在同质性较低的数据集上相比于对比方法获得了更加优秀的结果，相比于GCN更是获得超过5%的提升，而同质性较高的数据集在以GCN为编码器的条件下仍然普遍好于GCN。造成这种结果的原因在于提出的方法充分考虑了低同质性图的特征，即低同质性的图中的节点不能够从自己的同类节点中获取足够的同类信息，导致和其他类节点不能够彻底区分开。

3.5 实验结果可视化

为了更加直观地看到本文方法与对比方法在节点表示方面的差异，本文对得到的节点表示进行可视化操作。为了展示本文方法在同质性较高和较低的数据集上的表现力，实验在本文方法和对比方法上分别对同质性较高的Cora数据集和同质性较低的Chameleon数据集上进行了t-SNE[28]可视化和热图可视化，分别如图2和图3所示。

3.5.1 t-SNE可视化

为了直观地反映出节点表示在向量空间中的分布情况，本文接着对测试集的节点表示进行了t-SNE可视化操作。从图2中可以看出，在Cora数据集下，相比于其他方法，本文的算法具有更小的类内距离以及更大的类间距离，并且可以明显看出7个突触和类别数相对应；在Chameleon数据集上，本文方法相对于对比方法拥有更加清晰的类别簇，这些要归功于网络的优秀设计：将具有同质性的节点进行连接，使每个节点可以获取更多的同类信息，在分类时更具有竞争力。

3.5.2 热图可视化

热图可视化能够直观地看出同一类别内的样本之间的相似程度。在热力图中，从对角线上的方块边长可以看出此样本的数量多少，而方块的颜色深浅则带边同类节点的相似程度。从图3中可以看出，在具有高同质性的Cora数据集上，相比于其他方法，本文方法拥有更加清晰的方块边界以及颜色更深的方块颜色，这代表它在获取节点表示上具有强大的表现力。低同质性的数据集Chameleon在测试集中每类节点数量分别为224、245、227、252、190，每一类数量几乎相等，但是在图3中，3种对比方法的Heatmap可视化中的方块都不具有几乎相等大小的方块，但是本文方法拥有几乎相等大小的方块，且边界较为清晰。以上实验结果充分展示出所提方法在各类数据集上的优秀表现，证明增加图结构的同质性可以有效获取节点的邻居信息，从而获得更好的节点表示用于下游任务。

3.6 消融实验

为了直观地看出融合原始拓扑结构对模型的影响，本文对模型进行了消融实验来探索其影响。为此，需要将公式（7）变成：

Hs = ReLU（GCN（S-1，HS-1））（10）

则输入变成重构后的同质图结构和节点表示，忽略原始图结构，具体的表现如图4所示。

由图4可以观察到，在ACC精度和F1值2个指标上，完整的模型表现均优于缺失原始拓扑结构的模型，证明了融合原始图拓扑结构的有效性。

4 结束语

本文研究了图结构的同质性对节点表示学习的影响，并提出了一种基于图结构增强的图学习框架。首先对节点特征通过原始图结构进行消息传播和聚合进行特征提取，得到节点表示；然后计算节点表示的相似度从而获得同质矩阵；最后将节点表示，原始图结构以及生成的同质结构输入至图编码器中获得高级节点表示用于下游任务。结果表明，在节点分类任务中，本文方法在同质性较高的Cora和Citeseer数据集上获得了优于基线的结果，在同质性较低的Chame-leon等4个数据集上获得了优于基线平均5%以上的性能提升。这些实验充分验证了本文所提模型在图结构重构上的强大能力，有效地提高了节点的分类结果。

参考文献：

[1]" " 徐冰冰，岑科廷，黄俊杰，等. 图卷积神经网络综述[J]. 计算机学报，2020，43（5）：755-780.

XU B B， CEN K T， HUANG J J， et al. A survey on graph convolutional neural network[J]. Chinese Journal of Computers， 2020， 43（5）： 755-780（in Chinese）.

[2]" " SCHLICHTKRULL M， KIPF T N， BLOEM P， et al. Modeling relational data with graph convolutional networks[C]//European Semantic Web Conference. Cham： Springer， 2018： 593-607.

[3]" " 郝志峰， 柯妍蓉， 李烁， 等. 基于图编码网络的社交网络节点分类方法[J]. 计算机应用， 2020， 40（1）： 188-195.

HAO Z F， KE Y R， LI S， et al. Node classification method in social network based on graph encoder network[J]. Journal of Computer Applications， 2020， 40（1）： 188-195 （in Chinese）.

[4]" " 范洪玉， 张永库， 孟祥福. 基于知识图残差注意力网络的推荐方法[J]. 计算机科学， 2023，50（S2）：479-485.

FAN H Y， ZHANG Y K， MENG X F. Recommendation me-thod based on residual attention network of knowledge graph[J]. Computer Science， 2023， 50（S2）： 479-485（in Chinese）.

[5]" " 徐立祥， 葛伟， 陈恩红， 等. 基于图核同构网络的图分类方法[J]. 计算机研究与发展， 2024， 61（4）： 903-915.

XU L X， GE W， CHEN E H， et al. Graph classification method based on graph kernel isomorphism network[J]. Journal of Co-mputer Research and Development， 2024，61（4）： 903-915（Chinese）

[6]" " HUANG W B， ZHANG T， RONG Y， et al. Adaptive sampling towards fast graph representation learning[C]//Proceedings of the 32nd International Conference on Neural Information Processing" Systems. Montréal， Canada： ACM， 2018： 4563-4572.

[7]" " 刘俊奇， 涂文轩， 祝恩. 图卷积神经网络综述[J]. 计算机工程与科学，2023，45（8）： 1472-1481.

LIU J Q， TU W X， ZHU E. Survey on graph convolutional ne-ural network[J]. Computer Engineering amp; Science， 2023， 45（8）： 1472-1481（in Chinese）.

[8]" " 张丽英， 孙海航， 孙玉发， 等. 基于图卷积神经网络的节点分类方法研究综述[J]. 计算机科学，2024，51（4）：95-105.

ZHANG L Y， SUN H H， SUN Y F， et al. Review of node classification methods based on graph convolutional neural networks[J]. Computer Science， 2024， 51（4）：95-105（in Chinese）.

[9]" " CORSO G， CAVALLERI L， BEAINI D， et al. Principal neig-hbourhood aggregation for graph nets[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems. Vancouver， BC， Canada： ACM， 2020： 13260-13271.

[10]" ABU-EL-HAIJA S， PEROZZI B， KAPOOR A， et al. MixHop： Higher-order graph convolutional architectures via sparsified neighborhood mixing[C]//Proceedings of the 36th International Conference on Machine Learning. Long Beach， California， USA：PMLR， 2019： 21-29.

[11]" 代劲， 张奇瑞， 王国胤， 等. 基于多维云概念嵌入的变分图自编码器研究[J]. 电子学报，2023，51（12）：3507-3519.

DAI J， ZHANG Q R， WANG G Y， et al. Research on variational graph auto-encoder based on multidimensional cloud concept embedding[J]. Acta Electronica Sinica， 2023， 51（12）： 3507-3519（in Chinese）.

[12]" ZHANG M H， CUI Z C， NEUMANN M， et al. An end-to-end deep learning architecture for graph classification[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence. New Orleans， Louisiana， USA：AAAI，" 2018： 4438-4445.

[13]" YING R， HE R N， CHEN K F， et al. Graph convolutional neural networks for web-scale recommender systems[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining. London， United Kingdom： ACM， 2018： 974–983.

[14]" GILMER J， SCHOENHOLZ S S， RILEY P F， et al. Neural message passing for Quantum chemistry[C]//Proceedings of the 34th International Conference on Machine Learning. Sydney， NSW， Australia： ACM， 2017： 1263-1272.

[15]" BOJCHEVSKI A， GASTEIGER J， PEROZZI B， et al. Scaling graph neural networks with approximate PageRank[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining. CA， USA： ACM， 2020： 2464-2473.

[16]" ZHU J， YAN Y J， ZHAO L X， et al. Beyond homophily in graph neural networks： Current limitations and effective designs[C]//Proceedings of the 34th International Conference on Neural Information Proceeding Systems. Vancouver， Canada： MIT Press， 2020：7793-7804.

[17]" LUO D S， CHENG W， YU W C， et al. Learning to drop： Robust graph neural network via topological denoising[C]//Proceedings of the 14th ACM International Conference on Web Search and Data Mining. Israel： ACM， 2021： 779-787.

[18]" FATEMI B， EL ASRI L， KAZEMI S M. SLAPS： Self-supervision improves structure learning for graph neural networks[C]//Proceedings of the 35th International Conference on Neural Information Processing Systems. Beijing： MIT Press， 2021： 22667-22681.

[19]" TENENBAUM J B， DE SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science， 2000， 290（5500）： 2319-2323.

[20]" WANG Y， SUN Y B， LIU Z W， et al. Dynamic graph CNN for learning on point clouds[J]. ACM Transactions on Graphics， 2019， 38（5）： 146.

[21]" HALCROW J， MOSOI A， RUTH S， et al. Grale： Designing networks for graph learning[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining. CA， USA： ACM， 2020： 2523-2532.

[22]" ZHANG J N， SHI X J， XIE J Y， et al. GaAN： Gated attention networks for learning on large and spatiotemporal graphs[C]//Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence. Monterey， California， USA：AUAI， 2018：339-349.

[23]" SUHAIL M， SIGAL L. Mixture-kernel graph attention network for situation recognition[C]//2019 IEEE/CVF International Conference on Computer Vision （ICCV）. Seoul， Korea （South）： IEEE， 2019： 10362-10371.

[24]" ZHU H， LIN Y K， LIU Z Y， et al. Graph neural networks with generated parameters for relation extraction[C]//Proceeding of the 57th Conference of the Association for Computational Linguistics. Florence， Italy： Association for Computational Linguistics， 2019：1331-1339.

[25]" 杨洁祎， 董一鸿，钱江波. 基于图神经网络的小样本学习方法研究进展[J]. 计算机研究与发展，2024，61（4）：856-876.

YANG J Y， DONG Y H， QIAN J B. Research progress of few-shot learning methods based on graph neural networks[J]. Journal of Computer Research and Development， 2024， 61（4）： 856-876（in Chinese）.

[26]" 刘杰， 尚学群， 宋凌云， 等. 图神经网络在复杂图挖掘上的研究进展[J]. 软件学报， 2022， 33（10）： 3582-3618.

LIU J， SHANG X Q， SONG L Y， et al. Progress of graph neural networks on complex graph mining[J]. Journal of Software， 2022， 33（10）： 3582-3618（in Chinese）.

[27]" LIM D， HOHNE F， LI X， et al. Large scale learning on non-homophilous graphs： New benchmarks and strong simple me-thods[C]//Proceedings of the 35th International Conference on Neural Information Processing" Systems. Beijing： MIT Press，" 2021： 20887-20902.

[28]" 陈挺， 李国鹏， 王小梅. 基于t-SNE降维的科学基金资助项目可视化方法研究[J]. 数据分析与知识发现， 2018， 2（8）： 1-9.

CHEN T， LI G P， WANG X M. Visualizing appropriation of research funding with t-SNE algorithm[J]. Data Analysis and Knowledge Discovery， 2018， 2（8）： 1-9（in Chinese）.

本文引文格式：

张芳，单万锦，王雯，等. 基于图结构增强的图神经网络方法[J]. 天津工业大学学报，2024， 43（3）： 58-65.

ZHANG F， SHAN W J， WANG W， et al. Graph neural network method based on graph structure enhancement[J]. Journal of" Tiangong University， 2024， 43（3）： 58-65（in Chinese）.