计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (2): 107-115.doi: 10.11896/jsjkx.240600091

• 数据库&大数据&数据科学 • 上一篇    下一篇

融合高阶组结构信息的节点分类算法

郑文萍1,2,3, 韩艺恒1, 刘美麟1   

  1. 1 山西大学计算机与信息技术学院 太原 030006
    2 计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006
    3 山西大学智能信息处理研究所 太原 030006
  • 收稿日期:2024-06-17 修回日期:2024-09-16 出版日期:2025-02-15 发布日期:2025-02-17
  • 通讯作者: 郑文萍(wpzheng@sxu.edu.cn)
  • 基金资助:
    国家自然科学基金(62072292);山西省1331工程项目;教育部产学合作协同育人项目(220902842025336)

Node Classification Algorithm Fusing High-order Group Structure Information

ZHENG Wenping1,2,3, HAN Yiheng1, LIU Meilin1   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computation Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China
    3 Institute of Intelligent Information Processing,Shanxi University,Taiyuan 030006,China
  • Received:2024-06-17 Revised:2024-09-16 Online:2025-02-15 Published:2025-02-17
  • About author:ZHENG Wenping,born in 1979.Ph.D,professor,Ph.D supervisor,is a member of CCF(No.22709M).Her main research interests include complex network analysis,bioinformatics,etc.
  • Supported by:
    National Natural Science Foundation of China(62072292),1331 Engineering Project of Shanxi Province,China and Ministry of Education Industry-University Cooperation and Collaborative Education Project,China(220902842025336).

PDF (PC)

131

摘要： 节点的局部邻域内通常存在具有特定局部连接模式且频繁出现的高阶组结构,这些组结构可以更准确地刻画节点拓扑特征,有助于理解网络的结构特征及节点间的交互模式。基于此,利用节点局部邻域内的高阶组结构特征计算节点间的结构相似性,并提出了一种融合高阶组结构信息的节点分类算法NHGS(Node Classification Algorithm Fusing High-order Group Structure Information)。该算法将k元组内形成的不同构的导出子图作为其初始组标签,利用Weisfeiler-Lehman(WL)算法迭代地聚合其邻域k元组的标签信息以更新k元组标签;节点在不同k元组标签中的出现次数构成了节点的特征向量,利用节点间特征向量的相似性表示节点间的结构相似性;结合节点的属性信息,并通过自编码器神经网络得到节点嵌入,进而对网络中的节点进行分类。NHGS将节点局部邻域内的k元节点组结构信息与节点的属性信息相结合,得到了包含高阶结构信息的节点表示。在真实属性网络上的实验表明,所提方法能有效计算出节点间的结构相似性,提升了节点分类任务的性能。

关键词: 节点分类, 高阶结构, 结构相似性, 网络表示, 图神经网络

Abstract: There are usually high-order group structures with specific local connection patterns in local neighborhood of nodes,which can more accurately describe the topological characteristics of nodes and help to understand the structural characteristics of the network and the interaction patterns between nodes.The structural similarity between nodes can be computed using high-order group structural features within the local neighbors of a node,and a node classification algorithm is proposed based on fusing high-order group structure information(NHGS).Weisfeiler-Lehman(WL) algorithm is used to iteratively aggregate the label information of the k-tuple in a node's neighborhood to update its k-tuple label.The number of occurrences of nodes in different k-tuple labels constitutes the feature vector of nodes,and the cosine similarity between feature vectors is used to represent the structural similarity between nodes.Combined with the attribute information of the nodes,the node embedding is obtained through the autoencoder neural network,and then the nodes in the network are classified.NHGS combines the k-tuple node group structure information with the attribute information of a node to obtain the node representation containing the high-order structure information.Experiments on real attribute networks show that the proposed method can effectively calculate the structural similarity between nodes,and improve the performance of node classification tasks.

Key words: Node classification, High-order structure, Structural similarity, Network representation, Graph neural network

中图分类号: 

  • TP391
[1]WANG W Q,YIN H Z,DU X Z,et al.Online user representation learning across heterogeneous social networks [C]//Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval.New York:ACM,2019:545-554.
[2]WANG K S,SHEN Z H,HUANG C Y,et al.Microsoft academic graph:When experts are not enough [J].Quantitative Science Studies,2020,1(1):396-413.
[3]FOUT A,BYRD J,SHARIAT B,et al.Protein interface prediction using graph convolutional networks[C]//Proceedings of the 31th International Conference on Neural Information Processing System.California:NIPS,2017:6533-6542.
[4]BENGIO Y.Learning deep architectures for AI [J].Foundationsand trends in Machine Learning,2009,2(1):1-127.
[5]GAO H C,HUANG H.Deep attributed network embedding[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence.San Francisco:Morgan Kaufmann,2018:3364-3370.
[6]ARVIND V,FUHLBRUCK F,KOBLER J,et al.On weisfeiler-leman invariance:Subgraph counts and related graph properties [J].Journal of Computer and System Sciences,2020,113:42-59.
[7]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks [J].National Academy of Sciences,2002,99(12):7821-7826.
[8]ROSSI R A,AHMED N K.Role discovery in networks [J].IEEE Transactions on Knowledge and Data Engineering,2014,27(4):1112-1131.
[9]ERTTL O.ProbMinHash:A class of locality-sensitive hash algorithms for the(probability) jaccard similarity [J].IEEE Transactions on Knowledge and Data Engineering,2022,34(7):3491-3506.
[10]TAN F,XIA Y X,ZHU B Y.Link prediction in complex networks:a mutual information perspective [J].Public Library of Science,2014,9(9):e107056.
[11]ZHANG Q,LI M Z,DENG Y.Measure the structure similarity of nodes in complex networks based on relative entropy [J].Physica A:Statistical Mechanics and Its Applications,2018,491:749-763.
[12]KATZ L.A new status index derived from sociometric analysis [J].Psychometrika,1953,18(1):39-43.
[13]ZHOU T,LV L Y,ZHANG Y C.Predicting missing links via local information[J].The European Physical Journal B,2009,71(4):623-630.
[14]CHEN Z Q,XIE Z,ZHANG Q.Community detection based on local topological information and its application in power grid [J].Neurocomputing,2015,170(C):384-392.
[15]ZHENG W P,CHE C H,QIAN Y H,et al.A Graph clustering algorithm based on internode path metrics [J].Chinese Journal of Computers,2020,43(7):1312-132.
[16]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online lear-ning of social representations [C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.New York:ACM,2014:701-710.
[17]GROVER A,LESKOVEC J.Node2vec:scalable feature learning for networks [C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.New York:ACM,2016:855-864.
[18]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.New York:ACM,2015:1067-1011.
[19]WANG D X,CUI P,ZHU W W.Structural deep network embedding [C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2016:1225-1234.
[20]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:ACM,2017:385-394.
[21]MARSDEN P V,FRIEDKIN N E.Network studies of social influence [J].Sociological Methods & Research,1993,22(1):127-151.
[22]MCPHERSON M,LOVIN S L,COOK J M.Birds of a feather:Homophily in social networks [J].Annual Review of Sociology,2001,27(1):415-444.
[23]MARSDEN P V.Homogeneity in confiding relations [J].SocialNetworks,1988,10(1):57-76.
[24]ZHANG Z,YANG H X,BU J J,et al.ANRL:Attributed network representation learning via deep neural networks [C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence.San Francisco:Morgan Kaufmann,2018:3155-3161.
[25]YANG H,CHEN L,PAN S R,et al.Discrete embedding for attributed graphs [J].Pattern Recognition,2022,123(C):108-368.
[26]CHEN J,ZHONG M,LI J X,et al.Effective deep attributednetwork representation learning with topology adaptedsmoo-thing [J].IEEE Transactions on Cybernetics,2021,52(7):5935-5946.
[27]JIANG J W,HU Y S,LI X S,et al.Analyzing online transaction networks with network motifs [C]//Proceedings of the 28th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.New York:ACM,2022:3098-3106.
[28]ROSSI R A,AHMED N K,KOH E,et al.A structural graph representation learning framework [C]//Proceedings of the 13th International Conference on Web Search and Data Mining.New York:ACM,2020:483-491.
[29]CHEN J S,GAO K Y,LI G C,et al.NAGphormer:A tokenized graph transformer for node classification in large graphs[C]//Proceedings of the 11st International Conference on Learning Representations.Washington DC:ICLR,2023.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发