融合二连通模体结构信息的节点分类算法

doi:10.11772/j.issn.1001-9081.2023050846

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1464-1470.DOI: 10.11772/j.issn.1001-9081.2023050846

所属专题：第十九届中国机器学习会议(CCML 2023)

• 第十九届中国机器学习会议(CCML 2023) • 上一篇下一篇

融合二连通模体结构信息的节点分类算法

郑文萍¹^,²^,³(), 葛慧琳¹, 刘美麟¹, 杨贵¹

^1.山西大学计算机与信息技术学院, 太原 030006
^2.计算智能与中文信息处理教育部重点实验室(山西大学), 太原 030006
^3.山西大学智能信息处理研究所, 太原 030006

收稿日期:2023-06-29 修回日期:2023-07-26 接受日期:2023-07-31 发布日期:2023-08-16 出版日期:2024-05-10
通讯作者: 郑文萍
作者简介:葛慧琳（1997—），女，山西阳泉人，硕士研究生，主要研究方向：复杂网络分析
刘美麟（1996—），女，山西吕梁人，博士研究生，主要研究方向：复杂网络分析、高阶网络
杨贵（1975—），男，山西大同人，高级实验师，硕士，主要研究方向：数据挖掘、生物信息学。
第一联系人：郑文萍（1979—），女，山西晋中人，教授，博士，CCF会员，主要研究方向：复杂网络分析、生物信息学
基金资助:
国家自然科学基金资助项目(62072292);山西省1331工程项目;教育部产学合作协同育人项目(220902842025336)

Node classification algorithm fusing 2-connected motif-structure information

Wenping ZHENG¹^,²^,³(), Huilin GE¹, Meilin LIU¹, Gui YANG¹

^1.School of Computer and Information Technology，Shanxi University，Taiyuan Shanxi 030006，China
^2.Key Laboratory of Computation Intelligence and Chinese Information Processing of Ministry of Education （Shanxi University），Taiyuan Shanxi 030006，China
^3.Institute of Intelligent Information Processing，Shanxi University，Taiyuan Shanxi 030006，China

Received:2023-06-29 Revised:2023-07-26 Accepted:2023-07-31 Online:2023-08-16 Published:2024-05-10
Contact: Wenping ZHENG
About author:GE Huilin， born in 1997， M. S. candidate. Her research interests include complex network analysis.
LIU Meilin， born in 1996， Ph. D. candidate. Her research interests include complex network analysis， higher-order network.
YANG Gui， born in 1975， M. S.， senior experimentalist. His research interests include data mining， bioinformatics.
Supported by:
National Natural Science Foundation of China(62072292);1331 Engineering Project of Shanxi Province, University-Industry Collaborative Education Program of Ministry of Education(220902842025336)

摘要/Abstract

摘要：

节点表示学习将图结构数据信息编码到低维的潜在空间中，在节点分类、聚类、链路预测等机器学习任务中被广泛应用。在复杂网络中，节点与节点之间不仅存在直接相连的低阶结构，也存在以特殊连接模式形成的高阶结构，称为模体。提出一种融合二连通模体结构信息的节点分类算法（FMI），利用节点间高阶二连通模体信息学习节点表示，完成节点分类任务。首先，统计网络中的二连通模体，利用其中信息提出一个节点重要性的度量指标——模体比值。根据模体比值计算采样概率进行邻域采样；构造一个带权辅助图以融合网络节点连接的低阶关系与高阶关系，对节点进行加权邻域聚合以得到节点表示。在5个数据集Cora、Citeseer、Pubmed、Wiki和DBLP上执行节点分类任务，与5种经典基准算法进行对比，所提算法FMI在准确度和F1-分数等指标上表现良好。

关键词: 节点表示, 二连通模体, 邻域采样, 邻域聚合, 节点分类

Abstract:

Node representation learning has been widely applied in machine learning tasks， such as node classification， clustering and link prediction， since it can encode graph structure data information into low-dimensional potential space. In complex networks， nodes are interacted through not only low-order interactions， but also higher-order interactions formed by special connection modes. The higher-order interactions of a complex network are also called motifs. A node classification algorithm Fusing 2-connected Motif-structure Information （FMI） was proposed to use motif information among nodes to obtain node representation for node classification tasks. Firstly， the 2-connected motifs in the network were counted. A measure index of node importance， named motif-ratio， was proposed by using the motif information in the node； and a sampling probability was calculated according to the motif-ratio to carry out neighborhood sampling. A weighted auxiliary graph was constructed to fuse the low-order relations and the high-order relations of network nodes to aggregate neighborhoods weightedly. The node classification was performed on 5 datasets， Cora， Citeseer， Pubmed， Wiki and DBLP. By comparing with 5 classical baseline algorithms， the proposed algorithm FMI shows better performance on Accuracy， F1-score and other indicators.

Key words: node representation, 2-connected motif, neighborhood sampling, neighborhood aggregation, node classification

中图分类号:

TP391

郑文萍, 葛慧琳, 刘美麟, 杨贵. 融合二连通模体结构信息的节点分类算法[J]. 计算机应用, 2024, 44(5): 1464-1470.

Wenping ZHENG, Huilin GE, Meilin LIU, Gui YANG. Node classification algorithm fusing 2-connected motif-structure information[J]. Journal of Computer Applications, 2024, 44(5): 1464-1470.

图/表 9

参考文献 23

1	HAMILTON W L， YING R， LESKOVEC J. Representation learning on graphs： methods and applications［J］. IEEE Data Engineering Bulletin， 2017， 40： 52-74.
2	HAMILTON W L， YING R， LESKOVEC J. Inductive representation learning on large graphs［C］// Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2017： 1025-1035. 10.7551/mitpress/11474.003.0014
3	BACKSTROM L， LESKOVEC J. Supervised random walks： predicting and recommending links in social networks［C］// Proceedings of the 4th ACM International Conference on Web Search and Data Mining. New York： ACM， 2011： 635-644. 10.1145/1935826.1935914
4	COLEMAN J S. Foundations of Social Theory［M］. Cambridge： Harvard University Press， 1990.
5	JEON H， KIM S-R， NAM D， et al. Analysis of triangular motifs in protein interaction networks and their implications to protein ages and cancer genes［J］. International Journal of Data Mining and Bioinformatics， 2018， 19（4）： 340-365. 10.1504/ijdmb.2017.091365
6	ROTABI R， KAMATH K， KLEINBERG J， et al. Detecting strong ties using network motifs［C］// Proceedings of the 26th International Conference on World Wide Web Conference. New York： ACM， 2017： 983-992. 10.1145/3041021.3055139
7	MILO R， SHEN-ORR S， ITZKOVITZ S， et al. Network motifs： simple building blocks of complex networks［J］. Science， 2002， 298（5594）： 824-827. 10.1126/science.298.5594.824
8	KIPF T N， WELLING M. Semi-supervised classifition with graph convolutional networks［C］// Proceedings of the 5th International Conference on Learning Representations. London： dblp Computer Science Bibliography， 2017： 1-14.
9	VELIČKOVIĆ P， CUCURULL G， CASANOVA A， et al. Graph attention networks［C/OL］// Proceedings of the 6th International Conference on Learning Representations. ［S.l.］： ICLR， 2018 ［2023-05-01］. .
10	DEFFERRARD M， BRESSON X， VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering［C］// Proceedings of the 30th International Conference on Neural Information Processing Systems. Red Hook： Curran Associates Inc.， 2016： 3844-3852.
11	XU K， LI C， TIAN Y， et al. Representation learning on graphs with jumping knowledge networks［C］// Proceedings of the 35th International Conference on Machine Learning. New York： PMLR， 2018， 80： 5453-5462.
12	KIPF T N， WELLING M. Variational graph auto encoders［C/OL］// Proceedings of the 2016 Bayesian Deep Learning Workshop. ［S.l.］： NeurIPS， 2016 ［2023-05-01］. . 10.48550/arXiv.1611.07308
13	ZHANG J， SHI X， XIE J， et al. GaAN： gated attention networks for learning on large and spatiotemporal graphs［C］// Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence. ［S.l.］： Association for Uncertainty in Artificial Intelligence， 2018： 339-349.
14	CHEN J， MA T， XIAO C. FastGCN： fast learning with graph convolutional networks via importance sampling［C/OL］// Proceedings of the 6th International Conference on Learning Representations. ［S.l.］： ICLR， 2018 ［2018-01-30］. .
15	YING R， HE R， CHEN K， et al. Graph convolutional neural networks for web-scale recommender systems［C］// Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2018： 974-983. 10.1145/3219819.3219890
16	BENSON A R， GLEICH D F， LESKOVEC J. Higher order organization of complex networks［J］. Science， 2016， 353（6295）： 163-166. 10.1126/science.aad9029
17	ROSSI R A， AHMED N K， KOH E. Higher-order network representation learning［C］// Proceedings of the 27th International Conference on World Wide Web Conference. Republic and Canton of Geneva， CHE： International World Wide Web Conferences Steering Committee， 2018： 3-4. 10.1145/3184558.3186900
18	ZHAO H， XU X， SONG Y， et al. Ranking users in social networks with higher-order structures［J］. Proceedings of the AAAI Conference on Artificial Intelligence， 2018， 32（1）： 232-239. 10.1609/aaai.v32i1.11287
19	MONTI F， OTNESS K， BRONSTEIN M. MotifNet： a motif-based graph convolutional network for directed graphs［C］// Proceedings of the 2018 IEEE Data Science Workshop. Piscataway： IEEE， 2018： 225-228. 10.1109/dsw.2018.8439897
20	YU Y， LU Z， LIU J， et al. RUM： network representation learning using motifs［C］// Proceedings of the 2019 IEEE 35th International Conference on Data Engineering. Piscataway： IEEE， 2019： 1382-1393. 10.1109/icde.2019.00125
21	WANG L， REN J， XU B， et al. MODEL： motif-based deep feature learning for link prediction［J］. IEEE Transactions on Computational Social Systems， 2020， 7（2）： 503-516. 10.1109/tcss.2019.2962819
22	邱小波.关于2-连通图可迹性的两个充分条件［D］. 武汉：华中师范大学，2022.
	QIU X B. Two sufficient conditions for a 2‑connected graphs to be traceable［D］. Wuhan： Central China Normal University， 2022.
23	RIBEIRO P， SILVA F. G-tries： an efficient data structure for discovering network motifs［C］// Proceedings of the 2010 ACM Symposium on Applied Computing. New York： ACM， 2010： 1559-1566. 10.1145/1774088.1774422

数据集	节点数	边数	类别数	特征维度	样本数
数据集	节点数	边数	类别数	特征维度	训练集	测试集	验证集
Cora	2 708	5 429	7	1 433	140	1 000	500
Citeseer	3 327	4 732	6	3 703	120	1 000	500
Pubmed	19 717	44 338	3	500	60	1 000	500
Wiki	2 405	17 981	17	4 973	340	1 000	500
DBLP	4 057	3 528	4	334	80	1 000	500

数据集	节点数	边数	类别数	特征维度	样本数
数据集	节点数	边数	类别数	特征维度	训练集	测试集	验证集
Cora	2 708	5 429	7	1 433	140	1 000	500
Citeseer	3 327	4 732	6	3 703	120	1 000	500
Pubmed	19 717	44 338	3	500	60	1 000	500
Wiki	2 405	17 981	17	4 973	340	1 000	500
DBLP	4 057	3 528	4	334	80	1 000	500

算法	准确度（均值±标准差）/%					平均排名
算法	Cora	Citeseer	Pubmed	Wiki	DBLP	平均排名
ChebNet	77.30±2.08（7）	65.83±1.82（6）	77.90±0.39（5）	69.08±1.16（3）	78.32±0.65（5）	5.2
GCN	79.78±0.58（1）	67.90±0.54（4）	77.93±0.60（4）	68.18±0.67（4）	77.38±0.60（6）	3.8
GAT	79.77±0.52（2）	66.78±0.91（5）	77.29±0.36（6）	67.66±0.94（5）	78.48±1.24（4）	4.4
JK-Nets	79.48±0.61（4）	65.26±0.88（7）	76.05±0.76（7）	66.76±1.72（6）	77.16±0.70（7）	6.2
GraphSAGE-Mean	78.92±0.45（5）	70.41±0.57（2）	78.36±0.20（2）	69.98±0.71（2）	78.56±0.53（3）	2.8
GraphSAGE-Max	78.29±0.50（6）	69.49±0.43（3）	78.20±0.31（3）	67.72±0.82（7）	78.68±0.63（2）	4.2
FMI	79.53±0.46（3）	70.65±0.39（1）	78.40±0.27（1）	72.68±0.63（1）	81.16±0.63（1）	1.4

算法	准确度（均值±标准差）/%					平均排名
算法	Cora	Citeseer	Pubmed	Wiki	DBLP	平均排名
ChebNet	77.30±2.08（7）	65.83±1.82（6）	77.90±0.39（5）	69.08±1.16（3）	78.32±0.65（5）	5.2
GCN	79.78±0.58（1）	67.90±0.54（4）	77.93±0.60（4）	68.18±0.67（4）	77.38±0.60（6）	3.8
GAT	79.77±0.52（2）	66.78±0.91（5）	77.29±0.36（6）	67.66±0.94（5）	78.48±1.24（4）	4.4
JK-Nets	79.48±0.61（4）	65.26±0.88（7）	76.05±0.76（7）	66.76±1.72（6）	77.16±0.70（7）	6.2
GraphSAGE-Mean	78.92±0.45（5）	70.41±0.57（2）	78.36±0.20（2）	69.98±0.71（2）	78.56±0.53（3）	2.8
GraphSAGE-Max	78.29±0.50（6）	69.49±0.43（3）	78.20±0.31（3）	67.72±0.82（7）	78.68±0.63（2）	4.2
FMI	79.53±0.46（3）	70.65±0.39（1）	78.40±0.27（1）	72.68±0.63（1）	81.16±0.63（1）	1.4

算法	F1-分数（均值±标准差）/%					平均排名
算法	Cora	Citeseer	Pubmed	Wiki	DBLP	平均排名
ChebNet	75.61±2.12（7）	62.73±1.82（6）	77.65±0.36（5）	54.89±1.07（4）	77.88±0.80（3）	5.0
GCN	79.27±0.52（1）	65.08±0.79（4）	77.73±0.58（3）	54.80±1.46（6）	76.61±0.64（6）	4.0
GAT	79.12±0.41（2）	63.70±0.79（5）	76.83±0.34（6）	54.74±1.05（7）	77.67±1.24（5）	5.0
JK-Nets	78.53±0.66（4）	62.42±0.77（7）	74.86±0.87（7）	55.56±1.63（3）	76.28±0.78（7）	5.6
GraphSAGE-Mean	77.90±0.35（5）	67.27±0.49（2）	77.89±0.23（2）	57.23±2.00（1）	77.75±0.46（4）	2.8
GraphSAGE-Max	77.53±0.41（6）	65.80±0.50（3）	77.71±0.27（4）	54.84±1.41（5）	78.38±0.60（2）	4.0
FMI	78.83±0.49（3）	67.60±0.34（1）	77.96±0.24（1）	55.64±1.40（2）	80.29±0.83（1）	1.6

融合二连通模体结构信息的节点分类算法

Node classification algorithm fusing 2-connected motif-structure information

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 23

相关文章 10

编辑推荐

Metrics

[1]	黎施彬, 龚俊, 汤圣君. 基于Graph Transformer的半监督异配图表示学习模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1816-1823.
[2]	徐大鹏, 侯新民. 基于网络结构设计的图神经网络特征选择方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 663-670.
[3]	周乐, 代婷婷, 李淳, 谢军, 楚博策, 李峰, 张君毅, 刘峤. 基于节点-属性二部图的网络表示学习模型[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2311-2318.
[4]	张继杰, 杨艳, 刘勇. 利用初始残差和解耦操作的自适应深层图卷积[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 9-15.
[5]	李扬, 吴安彪, 袁野, 赵琳琳, 王国仁. 基于节点相似度的无监督属性图嵌入模型[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 1-8.
[6]	樊玮, 王慧敏, 邢艳. 基于自编码器的多视图属性网络表示学习模型[J]. 计算机应用, 2021, 41(4): 1064-1070.
[7]	郝志峰, 柯妍蓉, 李烁, 蔡瑞初, 温雯, 王丽娟. 基于图编码网络的社交网络节点分类方法[J]. 计算机应用, 2020, 40(1): 188-195.
[8]	王文涛, 吴淋涛, 黄烨, 朱容波. 基于密集连接卷积神经网络的链路预测模型[J]. 计算机应用, 2019, 39(6): 1632-1638.
[9]	陈可佳, 杨泽宇, 刘峥, 鲁浩. 基于邻域选择策略的图卷积网络模型[J]. 计算机应用, 2019, 39(12): 3415-3419.
[10]	鲁强陈明. 基于分类节点的P2P语义路由模型[J]. 计算机应用, 2008, 28(1): 29-32.

算法	准确度（均值±标准差）/%					F1-分数（均值±标准差）/%
算法	Cora	Citeseer	Pubmed	Wiki	DBLP	Cora	Citeseer	Pubmed	Wiki	DBLP
FMI-s	79.31±0.54	70.51±0.35	78.30±0.35	71.75±0.60	80.84±0.43	78.77±0.53	67.58±0.32	77.80±0.32	53.30±1.64	79.79±0.81
FMI-a	79.44±0.45	70.66±0.37	78.32±0.42	72.28±0.76	81.32±0.65	78.79±0.55	67.58±0.27	77.86±0.28	54.92±1.47	80.40±0.90
FMI	79.53±0.46	70.65±0.39	78.40±0.27	72.68±0.63	81.16±0.63	78.83±0.49	67.60±0.34	77.96±0.24	55.64±1.40	80.29±0.83

算法	准确度（均值±标准差）/%					F1-分数（均值±标准差）/%
算法	Cora	Citeseer	Pubmed	Wiki	DBLP	Cora	Citeseer	Pubmed	Wiki	DBLP
FMI-s	79.31±0.54	70.51±0.35	78.30±0.35	71.75±0.60	80.84±0.43	78.77±0.53	67.58±0.32	77.80±0.32	53.30±1.64	79.79±0.81
FMI-a	79.44±0.45	70.66±0.37	78.32±0.42	72.28±0.76	81.32±0.65	78.79±0.55	67.58±0.27	77.86±0.28	54.92±1.47	80.40±0.90
FMI	79.53±0.46	70.65±0.39	78.40±0.27	72.68±0.63	81.16±0.63	78.83±0.49	67.60±0.34	77.96±0.24	55.64±1.40	80.29±0.83