基于k核分解的网络嵌入

doi:10.19678/j.issn.1000-3428.0069028

摘要/Abstract

摘要：

近年来, 网络嵌入技术受到了广大研究者的关注。不过大多数网络嵌入算法并未考虑到处于相同层级结构的节点间的结构相似性, 这些节点在网络中通常具有相同的重要性。因此, 提出一种基于网络层级结构的网络嵌入算法, 称为KCNE。KCNE算法使用网络节点间的层级结构信息来保持节点之间的结构相似性。该算法首先基于k核(k-core)分解方法将网络中的节点划分为不同的层级, 并且使用定制的随机游走方法为每个节点生成游走序列, 该序列可以有效捕获节点的一阶邻域及处于同层级中的高阶相似节点, 随后将游走序列输入到Skip-gram模型中, 使学习到的节点表示具有更好的区分性。基于多个真实数据集的实验结果表明, 在链路预测和节点分类任务上, KCNE算法相比于8个基准算法中的次优算法性能提升最高分别约4%和5%。参数敏感性分析实验也表明了KCNE算法具有较好的鲁棒性。此外, 该算法在运行效率方面均优于Role2Vec、RARE和GEMSEC算法。

关键词: 网络嵌入, 结构相似性, 随机游走, 链路预测, 节点分类

Abstract:

In recent years, network embedding technology has attracted considerable attention from researchers. However, most network embedding algorithms have not adequately addressed the structural similarity among nodes within the same hierarchical level, even though these nodes typically share similar importance within the network. Therefore, this paper proposes a network embedding algorithm based on the hierarchical structure of a network, called KCNE. The KCNE algorithm utilizes hierarchical structural information among network nodes to preserve the structural similarity between nodes. Specifically, the algorithm initially employs the k-core decomposition method to categorize the nodes in the network into different levels. Subsequently, a customized random walk method is employed to generate a random walk sequence for each node. This sequence effectively captures the first-order neighborhood of nodes and high-order similar nodes within the same level. The generated random walk sequences are then input into a Skip-gram model to ensure that the learned node representations possess enhanced discriminative capabilities. Finally, experimental results on multiple real datasets demonstrate that, in link prediction and node classification tasks, the KCNE algorithm outperforms the second-best algorithm among eight benchmark algorithms by approximately 4% and 5%, respectively. Sensitivity analysis experiments further confirm the superior robustness of the KCNE algorithm. Additionally, the algorithm exhibits superior efficiency compared to the Role2Vec, RARE, and GEMSEC algorithms.

Key words: network embedding, structural similarity, random walk, link prediction, node classification

张和平, 张和贵, 谢晓尧, 张太华, 张思聪, 喻国军. 基于k核分解的网络嵌入[J]. 计算机工程, 2025, 51(2): 139-148.

ZHANG Heping, ZHANG Hegui, XIE Xiaoyao, ZHANG Taihua, ZHANG Sicong, YU Guojun. Network Embedding Based on k-core Decomposition[J]. Computer Engineering, 2025, 51(2): 139-148.

https://www.ecice06.com/CN/Y2025/V51/I2/139

图/表 11

图1 KCNE算法的总体流程

Fig.1 Overall workflow of the KCNE algorithm

图2 KCNE算法在不同数据集上的参数敏感性分析

Fig.2 Parameter sensitivity analysis of KCNE algorithm on different datasets

参考文献 37

1	ZHANG H G , CHEN X L , PENG Y , et al. The interaction of multiple information on multiplex social networks. Information Sciences, 2022, 605, 366- 380. doi: 10.1016/j.ins.2022.05.036
2	白明昌. 基于折叠路径聚合的属性网络节点嵌入方法. 计算机工程, 2023, 49 (7): 76- 84. doi: 10.19678/j.issn.1000-3428.0064318
	BAI M C . Node embedding method based on folded path aggregation on attributed network. Computer Engineering, 2023, 49 (7): 76- 84. doi: 10.19678/j.issn.1000-3428.0064318
3	KAZIENKO P , KAJDANOWICZ T . Label-dependent node classification in the network. Neurocomputing, 2012, 75 (1): 199- 209. doi: 10.1016/j.neucom.2011.04.047
4	KUMAR A , SINGH S S , SINGH K , et al. Link prediction techniques, applications, and performance: a survey. Physica A-Statistical Mechanics and Its Applications, 2020, 553, 124289. doi: 10.1016/j.physa.2020.124289
5	PIO G , CECI M , PRISCIANDARO F , et al. Exploiting causality in gene network reconstruction based on graph embedding. Machine Learning, 2020, 109 (6): 1231- 1279. doi: 10.1007/s10994-019-05861-8
6	PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2014: 701-710.10.1145/2623330.2623732
7	MIKOLOV T, CHEN K, CORRADO G, et al. Efficient estimation of word representations in vector space[EB/OL]. [2023-11-01]. https://arxiv.org/abs/1301.3781v1.
8	GROVER A, LESKOVEC J. node2vec: scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2016: 855-864.10.1145/2939672.2939754
9	TANG J, QU M, WANG M Z, et al. LINE: large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. Florence, Italy: International World Wide Web Conferences Steering Committee, 2015: 1067-1077.10.1145/2736277.2741093
10	KEIKHA M M , RAHGOZAR M , ASADPOUR M . Community aware random walk for network embedding. Knowledge-Based Systems, 2018, 148, 47- 54. doi: 10.1016/j.knosys.2018.02.028
11	GUO K , WANG Q Z , LIN J Q , et al. Network representation learning based on community-aware and adaptive random walk for overlapping community detection. Applied Intelligence, 2022, 52 (9): 9919- 9937. doi: 10.1007/s10489-021-02999-8
12	AHMED N K, ROSSI R A, LEE J B, et al. role2vec: role-based network embeddings[EB/OL]. [2023-11-01]. http://ryanrossi.com/pubs/role2vec-DLG-KDD.pdf.
13	ZHANG H G , KOU G , PENG Y , et al. Role-aware random walk for network embedding. Information Sciences, 2024, 652, 119765. doi: 10.1016/j.ins.2023.119765
14	GUO X , JIAO P F , ZHANG W , et al. Representation learning on heterostructures via heterogeneous anonymous walks. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35 (7): 9538- 9552. doi: 10.1109/TNNLS.2023.3234005
15	JIANG J Y, LI Z Y, JU C J T, et al. MARU: meta-context aware random walks for heterogeneous network representation learning[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management. New York, USA: ACM Press, 2020: 575-584.
16	LI X , WEI W , ZHANG R Z , et al. Representation learning of enhanced graphs using random walk graph convolutional network. ACM Transactions on Intelligent Systems and Technology, 2023, 14 (3): 1- 21. doi: 10.1145/3582841
17	ZHANG Y Y , SHI Z , FENG D , et al. Degree-biased random walk for large-scale network embedding. Future Generation Computer Systems, 2019, 100, 198- 209. doi: 10.1016/j.future.2019.05.033
18	LIU Q , SHU H , YUAN M , et al. Fuzzy hierarchical network embedding fusing structural and neighbor information. Information Sciences, 2022, 603, 130- 148. doi: 10.1016/j.ins.2022.04.042
19	焦鹏飞, 潘婷, 金弟, 等. 角色导向的网络表示学习综述. 计算机学报, 2023, 46 (2): 274- 303. doi: 10.11897/SP.J.1016.2023.00274
	JIAO P F , PAN T , JIN D , et al. A survey on role-guided network representation learning. Chinese Journal of Computers, 2023, 46 (2): 274- 303. doi: 10.11897/SP.J.1016.2023.00274
20	DUONG C T , NGUYEN T T , HOANG T D , et al. Deep MinCut: learning node embeddings by detecting communities. Pattern Recognition, 2023, 134, 109126. doi: 10.1016/j.patcog.2022.109126
21	TU C C , ZENG X K , WANG H , et al. A unified framework for community detection and network representation learning. IEEE Transactions on Knowledge and Data Engineering, 2019, 31 (6): 1051- 1065. doi: 10.1109/TKDE.2018.2852958
22	WANG X , CUI P , WANG J , et al. Community preserving network embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 2017, 31 (1): 203- 209. doi: 10.1609/aaai.v31i1.10488
23	ROZEMBERCZKI B, DAVIES R, SARKAR R, et al. GEMSEC: graph embedding with self clustering[C]//Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. New York, USA: ACM Press, 2020: 65-72.10.1145/3341161.3342890
24	吕少卿, 赵雪莉, 张潘, 等. 一种保留社区结构信息的网络嵌入算法. 计算机工程, 2021, 47 (12): 122- 130. doi: 10.19678/j.issn.1000-3428.0059448
	LV S Q , ZHAO X L , ZHANG P , et al. A network embedding algorithm preserving community structure information. Computer Engineering, 2021, 47 (12): 122- 130. doi: 10.19678/j.issn.1000-3428.0059448
25	李亚芳, 梁烨, 冯韦玮, 等. 基于社区优化的深度网络嵌入方法. 计算机应用, 2021, 41 (7): 1956- 1963. doi: 10.11772/j.issn.1001-9081.2020081193
	LI Y F , LIANG Y , FENG W W , et al. Deep network embedding method based on community optimization. Journal of Computer Applications, 2021, 41 (7): 1956- 1963. doi: 10.11772/j.issn.1001-9081.2020081193
26	MA X W, QIN G, QIU Z Y, et al. RiWalk: fast structural node embedding via role identification[C]//Proceedings of the IEEE International Conference on Data Mining (ICDM). Washington D. C., USA: IEEE Press, 2019: 478-487.10.1109/ICDM.2019.00058
27	ZHANG H G, KOU G. Role-based multiplex network embedding[C]//Proceedings of the 39th International Conference on Machine Learning. New York, USA: PMLR, 2022: 26265-26280.
28	WANG X , JIAN S L , LU K , et al. RED: learning the role embedding in networks via discrete-time quantum walk. Applied Intelligence, 2022, 52 (2): 1493- 1507. doi: 10.1007/s10489-021-02342-1
29	LI S, HUANG F H. A node role embedding method based on neighborhood clustering coefficient[C]//Proceedings of the 6th International Conference on Data Storage and Data Engineering (DSDE). Washington D. C., USA: IEEE Press, 2023: 1-5.10.1109/DSDE58527.2023.00007
30	SUN Y H , JIA M Y , LIU C , et al. Heterogeneous network representation learning based on role feature extraction. Pattern Recognition, 2023, 144, 109870. doi: 10.1016/j.patcog.2023.109870
31	李泽水, 冀俊忠, 杨翠翠. 基于边权重信息深度网络嵌入的PPIN功能模块检测. 计算机工程, 2023, 49 (8): 69- 76. doi: 10.19678/j.issn.1000-3428.0065072
	LI Z S , JI J Z , YANG C C . Functional module detection based on deep network embedding of edge weighing information in PPIN. Computer Engineering, 2023, 49 (8): 69- 76. doi: 10.19678/j.issn.1000-3428.0065072
32	KONG Y X , SHI G Y , WU R J , et al. k-core: theories and applications. Physics Reports, 2019, 832, 1- 32. doi: 10.1016/j.physrep.2019.10.004
33	RIBEIRO L F R, SAVERESE P H P, FIGUEIREDO D R. struc2vec: learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2017: 385-394.10.1145/3097983.3098061
34	YIN H, BENSON A R, LESKOVEC J, et al. Local higher-order graph clustering[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2017: 555-564.10.1145/3097983.3098069
35	ROSSI R , AHMED N . The network data repository with interactive graph analytics and visualization. Proceedings of the AAAI Conference on Artificial Intelligence, 2015, 29 (1): 4292- 4293.
36	YANG D Q, ROSSO P, LI B, et al. NodeSketch: highly-efficient graph embeddings via recursive sketching[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2019: 1162-1172.10.1145/3292500.3330951
37	MO Y J, LEI Y J, SHEN J L, et al. Disentangled multiplex graph representation learning[C]//Proceedings of the 40th International Conference on Machine Learning. New York, USA: PMLR, 2023: 24983-25005.

[1]	李政学, 李枝名, 彭德中, 陈杰. 基于特征对比学习和图卷积的社交网络用户分类[J]. 计算机工程, 2024, 50(4): 258-266.
[2]	李泽水, 冀俊忠, 杨翠翠. 基于边权重信息深度网络嵌入的PPIN功能模块检测[J]. 计算机工程, 2023, 49(8): 69-76.
[3]	袁立宁, 胡皓, 刘钊. 基于多通道图卷积自编码器的图表示学习[J]. 计算机工程, 2023, 49(2): 150-160,174.
[4]	王效灵, 胡志杰, 徐帅帅, 黄浩如. 改进暗通道先验和策略性融合的图像去雾算法[J]. 计算机工程, 2023, 49(10): 212-221.
[5]	刘宇航, 尹小庆, 林云. 基于网络资源流量的链路预测方法[J]. 计算机工程, 2022, 48(9): 78-88.
[6]	吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.
[7]	曾茜, 韩华, 马媛媛. 基于模体的朴素贝叶斯链路预测方法[J]. 计算机工程, 2022, 48(10): 95-102.
[8]	刘峰, 王宝亮, 邹荣宇, 赵浩淳. 基于随机游走的网络表示学习推荐算法[J]. 计算机工程, 2021, 47(9): 90-96,105.
[9]	黄鑫, 李赟, 熊瑾煜. 基于信息传播节点集的CTDN节点分类算法[J]. 计算机工程, 2021, 47(6): 188-196.
[10]	徐攸, 王晓萍, 熊贇. 基于角色的网络表征学习方法[J]. 计算机工程, 2021, 47(5): 52-57.
[11]	高宏屹, 张曦煌, 王杰. 生成对抗式分层网络表示学习的链路预测算法[J]. 计算机工程, 2021, 47(2): 60-68,76.
[12]	吕少卿, 赵雪莉, 张潘, 任新成. 一种保留社区结构信息的网络嵌入算法[J]. 计算机工程, 2021, 47(12): 122-130.
[13]	李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.
[14]	汤伟韬, 余敦辉, 魏世伟. 融合知识图谱与用户评论的商品推荐算法[J]. 计算机工程, 2020, 46(8): 93-100.
[15]	万美含, 熊贇, 朱扬勇. 基于异质网络层次注意力机制的基因功能预测[J]. 计算机工程, 2020, 46(7): 43-49.

选择文件类型/文献管理软件名称

选择包含的内容