基于相似度随机游走聚合的图节点分类算法

doi:10.13229/j.cnki.jdxbgxb20231043

摘要/Abstract

摘要：

针对异质图节点分类任务中MLP、GCN等方法准确率相对较低的问题，提出了一种基于相似度随机游走聚合的图神经网络（SRW-GNN）。为降低异质性对节点嵌入的影响，SRW-GNN利用节点间的相似度作为概率进行随机游走，并将采样路径作为邻域以获取更多同质信息。为解决大多数现有GNN聚合器对节点顺序不敏感的问题，本文引入基于循环神经网络（RNN）的路径聚合器来同时提取路径中节点的特征和顺序信息。此外，节点对不同路径有不同的偏好，为了自适应地学习不同路径在节点编码中的重要性，采用注意力机制动态地调整各路径对最终嵌入的贡献。在多个常用的异质图数据集的实验结果表明，本文方法的准确率明显优于MLP、GCN、H2GCN、HOG-GCN等方法，验证了其在异质图节点分类任务中的有效性。

关键词: 计算机应用技术, 图神经网络, 异质图, 节点分类

Abstract:

In addressing the issue of relatively low accuracy in node classification tasks on heterophily graphs using methods such as MLP and GCN， a Graph Neural Network based on Similarity Random Walk Aggregation （SRW-GNN） was proposed. To address the impact of heterophily on node embeddings， SRW-GNN employs the similarity between nodes as probabilities for conducting random walks. The sampled paths serve as the neighborhood， enabling the model to gather more homophily-based information. To address the issue of insensitivity to node order in most existing graph neural network （GNN） aggregators， a path aggregator based on recurrent neural networks （RNNs） was introduced to simultaneously extract features and order information of each node in the path. Furthermore， nodes exhibit varying preferences for different paths. To adaptively learn the importance of different paths in node encoding， an attention mechanism was employed to dynamically adjust the contributions of each path to the final embedding. Experimental results on several commonly used heterophily graph datasets demonstrate that the proposed SRW-GNN method achieves significantly higher accuracy compared to the methods such as MLP， GCN， H2GCN， HOG-GCN， validating its effectiveness in heterophily graph node classification tasks.

Key words: computer application technology, graph neural network, heterophily graph, node classification

中图分类号:

TP391.4

车翔玖,孙雨鹏. 基于相似度随机游走聚合的图节点分类算法[J]. 吉林大学学报(工学版), 2025, 55(6): 2069-2075.

Xiang-jiu CHE,Yu-peng SUN. Graph node classification algorithm based on similarity random walk aggregation[J]. Journal of Jilin University(Engineering and Technology Edition), 2025, 55(6): 2069-2075.

图/表 4

图1

图2

表1

表2

参考文献 19

[1]	徐冰冰, 岑科廷, 黄俊杰, 等. 图卷积神经网络综述[J].计算机学报, 2020, 43(5): 755-780.
	Xu Bing-bing, Cen Ke-yan, Huang Jun-jie, et al. A survey on graph convolutional neural network[J]. Chinese Journal of Computers, 2020, 43(5): 755-780.
[2]	LeCun Y, Bottou L, Bengio Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278-2324.
[3]	Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry[C]∥Proceedings of the International Conference on Machine Learning, Sydney, Australia, 2017: 1263-1272.
[4]	Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J/OL]. [2023-08-11].
[5]	Hamilton W L, Ying R, Leskovec J. Inductive representation learning on large graphs[J/OL]. [2023-08-11].
[6]	Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. Stat, 2017, 1050(20): No.48550.
[7]	Zhu J, Rossi R A, Rao A, et al. Graph neural networks with heterophily[J]. AAAI Technical Track on Machine Learning V, 2021, 35(12): 11168-11176.
[8]	Wang T, Jin D, Wang R, et al. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily[C]∥Proceedings of the AAAI Conference on Artificial Intelligence, Philadelphia, USA, 2022, 36(4): 4210-4218.
[9]	He D, Liang C, Liu H, et al. Block modeling-guided graph convolutional neural networks[C]∥Proceedings of the AAAI Conference on Artificial Intelligence, Philadelphia, USA, 2022: 4022-4029.
[10]	Yan Y, Hashemi M, Swersky K, et al. Two sides of the same coin: heterophily and oversmoothing in graph convolutional neural networks[C]∥2022 IEEE International Conference on Data Mining (ICDM), Chennai, India,2022: 1287-1292.
[11]	Zhu M, Wang X, Shi C, et al. Interpreting and unifying graph neural networks with an optimization framework[C]∥Proceedings of the Web Conference, New York, NY, USA, 2021: 1215-1226.
[12]	Pei H, Wei B, Chang K C C, et al. Geom-GCN: geometric graph convolutional networks[J/OL]. [2023-08-11].
[13]	Zhu J, Yan Y, Zhao L, et al. Beyond homophily in graph neural networks: current limitations and effective designs[C]∥Advances in Neural Information Processing Systems, Long Beach, USA,2020, 33: 7793-7804.
[14]	Chien E, Peng J, Li P, et al. Adaptive universal generalized pagerank graph neural network[J/OL]. [2023-08-11].
[15]	Jin D, Wang R, Ge M, et al. Raw-gnn: random walk aggregation based graph neural network[C]∥Proceedings of the 31st International Joint Conference on Artificial Intelligence,Shenzhen, China, 2022: 2108-2114.
[16]	Fu X Y, Zhang J N, Meng Z Q, et al. Magnn: metapath aggregated graph neural network for heterogeneous graph embedding[C]∥Proceedings of the Web Conference, Taipei, China, 2020: 2331-2341.
[17]	Luan S, Hua C, Lu Q, et al. Revisiting heterophily for graph neural networks[J]. Advances in Neural Information Processing Systems, 2022, 35: 1362-1375.
[18]	Hochreiter S, Schmidhuber J. Long short-term memory[J]. Neural Computation, 1997, 9(8): 1735-1780.
[19]	Chung J, Gulcehre C, Cho K H, et al. Empirical evaluation of gated recurrent neural networks on sequence modeling[J/OL].[2023-08-11].

相关文章 15

[1]	王健,贾晨威. 面向智能网联车辆的轨迹预测模型[J]. 吉林大学学报(工学版), 2025, 55(6): 1963-1972.
[2]	周丰丰,郭喆,范雨思. 面向不平衡多组学癌症数据的特征表征算法[J]. 吉林大学学报(工学版), 2025, 55(6): 2089-2096.
[3]	蔡晓东,周青松,张言言,雪韵. 基于动静态和关系特征全局捕获的社交推荐模型[J]. 吉林大学学报(工学版), 2025, 55(2): 700-708.
[4]	车翔玖,武宇宁,刘全乐. 基于因果特征学习的有权同构图分类算法[J]. 吉林大学学报(工学版), 2025, 55(2): 681-686.
[5]	张玺君,余光杰,崔勇,尚继洋. 基于聚类算法和图神经网络的短时交通流预测[J]. 吉林大学学报(工学版), 2024, 54(6): 1593-1600.
[6]	金志刚,苏仁鋆,赵晓芳. 基于异质图网络的心理评估方法[J]. 吉林大学学报(工学版), 2024, 54(4): 1078-1085.
[7]	梁礼明,周珑颂,尹江,盛校棋. 融合多尺度Transformer的皮肤病变分割算法[J]. 吉林大学学报(工学版), 2024, 54(4): 1086-1098.
[8]	拉巴顿珠,扎西多吉,珠杰. 藏语文本标准化方法[J]. 吉林大学学报(工学版), 2024, 54(12): 3577-3588.
[9]	叶育鑫,夏珞珈,孙铭会. 增强现实环境中基于假想键盘的手势输入方法[J]. 吉林大学学报(工学版), 2024, 54(11): 3274-3282.
[10]	车娜,朱奕明,赵剑,孙磊,史丽娟,曾现伟. 基于联结主义的视听语音识别方法[J]. 吉林大学学报(工学版), 2024, 54(10): 2984-2993.
[11]	薛珊,张亚亮,吕琼莹,曹国华. 复杂背景下的反无人机系统目标检测算法[J]. 吉林大学学报(工学版), 2023, 53(3): 891-901.
[12]	时小虎,吴佳琦,吴春国,程石,翁小辉,常志勇. 基于残差网络的弯道增强车道线检测方法[J]. 吉林大学学报(工学版), 2023, 53(2): 584-592.
[13]	王振,杨宵晗,吴楠楠,李国坤,冯创. 基于生成对抗网络的序列交叉熵哈希[J]. 吉林大学学报(工学版), 2023, 53(12): 3536-3546.
[14]	周丰丰,颜振炜. 基于混合特征的特征选择神经肽预测模型[J]. 吉林大学学报(工学版), 2023, 53(11): 3238-3245.
[15]	董立岩,梁伟业,王越群,李永丽. 基于会话的结合全局潜在信息的图神经网络推荐模型[J]. 吉林大学学报(工学版), 2023, 53(10): 2964-2972.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

参数	数据集
参数	Cornell	Texas	Wisconsin
节点数/个	183	183	251
边数/个	295	309	499
特征维数/个	1 703	1 703	1 703
类别数量/个	5	5	5

方法		数据集
方法		Cornell	Texas	Wisconsin
基线方法	MLP	84.32±6.14	83.24±5.77	86.47±3.33
	GCN	55.14±7.57	55.68±9.61	53.73±7.65
	GraphSAGE	78.38±6.84	85.41±5.16	85.49±3.53
	GAT	54.59±7.33	57.30±3.38	54.31±5.62
	H2GCN	78.92±5.24	82.16±8.21	82.57±3.21
	CPGNN	63.51±5.83	74.32±7.38	81.76±6.74
	GPR-GNN	82.97±5.68	84.59±4.37	83.92±3.14
	BM-GCN	79.14±8.44	85.13±4.64	82.82±8.89
	HOG-GCN	84.32±4.32	85.17±4.40	86.67±3.36
	RAW-GNN	84.86±5.43	85.95±4.15	88.24±3.72
消融实验	COS-SRW	83.78±5.67	83.78±4.36	87.06±2.35
	SRW-MLP	56.76±6.62	57.57±8.47	44.12±9.62
	SRW-MEAN	84.32±5.64	82.97±6.74	86.47±2.83
本文方法	SRW-GNN	86.49±6.40	86.76±4.43	88.63±3.70