面向图神经网络的节点重要性排序研究进展

doi:10.3778/j.issn.1673-9418.2405056

摘要/Abstract

摘要： 节点重要性排序作为一项关键的图数据分析任务，对于识别和排序图中的重要节点至关重要。图神经网络（GNN）作为一种利用深度学习直接对图结构数据进行学习的框架，能够充分学习图结构数据中的节点和边的内在规律及更深层次的语义特征。在节点重要性排序任务中，GNN能够充分利用图结构信息和节点特征进行节点重要性的评估。相比于传统的节点排序方法，GNN可以更好地处理图结构数据的多样性和复杂性，捕捉节点间的复杂关联和语义信息，并自动学习节点特征表示，减少手工特征工程的偏差，提升节点重要性排序任务的准确性。因此，基于图神经网络的方法已成为节点重要性研究的主流方向。对近年来图神经网络的节点排序方法进行分类和综述。梳理了节点排序、图神经网络及经典节点重要性度量指标的核心概念。全面总结了基于图神经网络的节点重要性方法的最新进展，并根据基础图神经网络及其衍生的变体，将节点重要性排序方法分为基础图神经网络、图卷积神经网络、图注意力网络和图自编码器四类。同时，分析这些方法在社交网络、交通网络和知识网络等下游任务中的性能表现。对现有研究进行全面总结，分析现有方法的时间复杂度、优点、局限性和性能，并根据现有研究的不足讨论未来的研究方向。

关键词: 节点重要性, 节点排序, 图神经网络, 表示学习

Abstract: Node importance ranking is a critical task in graph analysis, as it plays a crucial role in identifying and prioritizing important nodes within a graph. Graph neural networks (GNNs) serve as an effective framework that leverages deep learning to directly comprehend the structural data of graphs, enabling comprehensive understanding of the internal patterns and deeper semantic features associated with nodes and edges. In the context of node importance ranking, GNNs can effectively harness graph structure information and node features to assess the significance of individual nodes. Compared with traditional node ranking methods, GNNs are better equipped to handle the diverse and intricate nature of graph structural data, capturing complex associations and semantic information between nodes while autonomously learning representations for node features. This reduces reliance on manual feature engineering, thereby enhancing accuracy in node importance ranking tasks. Consequently, approaches based on graph neural networks have emerged as the predominant direction for research into node importance. On this basis, this paper provides a classification of recent advancements in node ranking methods utilizing graph neural networks. This paper begins by revisiting core concepts related to node ranking, graph neural networks, and classical metrics for assessing node importance. It then summarizes recent developments in methods for evaluating node importance using graph neural networks. These techniques are categorized into four groups based on fundamental graph neural networks and their variants: basic GNNs, graph convolutional neural networks (GCNs), graph attention networks (GATs), and graph autoencoders (GAEs). Additionally, this paper analyzes the performance of these methods across various application domains, such as social networks, traffic networks, and knowledge graphs. Finally, it offers a comprehensive overview of existing research by analyzing time complexity along with advantages, limitations, and performance characteristics of current methodologies. Furthermore, it discusses future research directions based on identified shortcomings.

Key words: node importance, node ranking, graph neural network, representation learning

曹璐, 丁苍峰, 马乐荣, 延照耀, 游浩, 洪安琪. 面向图神经网络的节点重要性排序研究进展[J]. 计算机科学与探索, 2025, 19(4): 877-900.

CAO Lu, DING Cangfeng, MA Lerong, YAN Zhaoyao, YOU Hao, HONG Anqi. Advances in Node Importance Ranking Based on Graph Neural Networks[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(4): 877-900.

参考文献

[1] MAURYA S K, LIU X, MURATA T, et al. Fast approximations of betweenness centrality with graph neural networks[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. New York: ACM, 2019: 2149-2152.
[2] LIAO H, MARIANI M S, MEDO M, et al. Ranking in evolving complex networks[J]. Physics Reports, 2017, 689: 1-54.
[3] 熊熙, 胡勇. 基于社交网络的观点传播动力学研究[J]. 物理学报, 2012, 61(15): 104-110.
XIONG X, HU Y. Research on the dynamics of opinion spread based on social network services[J]. Acta Physica Sinica, 2012, 61(15): 104-110.
[4] BARABáSI A L, GULBAHCE N, LOSCALZO J. Network medicine: a network-based approach to human disease[J]. Nature Reviews Genetics, 2011, 12(1): 56-68.
[5] DENG Z P, HUANG D R, LIU J Y, et al. An assessment method for traffic state vulnerability based on a cloud model for urban road network traffic systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(11): 7155-7168.
[6] TYLOO M, PAGNIER L, JACQUOD P. The key player problem in complex oscillator networks and electric power grids: resistance centralities identify local vulnerabilities[J]. Science Advances, 2019, 5(11): eaaw8359.
[7] 郭程远, 陈鸿昶, 王庚润, 等. 复杂网络节点重要性排序算法及应用综述[J]. 信息工程大学学报, 2021, 22(3): 313-320.
GUO C Y, CHEN H C, WANG G R, et al. Node importance ranking based on complex network[J]. Journal of Information Engineering University, 2021, 22(3): 313-320.
[8] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. The Journal of Mathematical Sociology, 1972, 2(1): 113-120.
[9] CHEN D B, Lü L Y, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012, 391(4): 1777-1787.
[10] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6: 888-893.
[11] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 2002, 1(3): 215-239.
[12] KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43.
[13] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35.
[14] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30: 107-117.
[15] LV L Y, ZHANG Y C, YEUNG C H, et al. Leaders in social networks, the delicious case[J]. PLoS One, 2011, 6(6): e21202.
[16] XU K, HU W, LESKOVEC J, et al. How powerful are graph neural networks?[C]//Proceedings of the 7th International Conference on Learning Representations, 2019.
[17] 胡枫, 赵海兴, 何佳倍, 等. 基于超图结构的科研合作网络演化模型[J]. 物理学报, 2013, 62(19): 547-554.
HU F, ZHAO H X, HE J B, et al. An evolving model for hypergraph-structure-based scientific collaboration networks [J]. Acta Physica Sinica, 2013, 62(19): 547-554.
[18] GORI M, MONFARDINI G, SCARSELLI F. A new model for learning in graph domains[C]//Proceedings of the 2005 IEEE International Joint Conference on Neural Networks. Piscataway: IEEE, 2005: 729-734.
[19] SCARSELLI F, TSOI A C, GORI M, et al. Graphical-based learning environments for pattern recognition[C]//Procee-dings of the 2004 Joint IAPR International Workshops on Structural, Syntactic, and Statistical Pattern Recognition. Berlin, Heidelberg: Springer, 2004: 42-56.
[20] SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2009, 20(1): 61-80.
[21] 吴博, 梁循, 张树森, 等. 图神经网络前沿进展与应用[J]. 计算机学报, 2022, 45(1): 35-68.
WU B, LIANG X, ZHANG S S, et al. Advances and applications in graph neural network[J]. Chinese Journal of Computers, 2022, 45(1): 35-68.
[22] 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- Volume 70, 2017: 1263-1272.
[23] 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, 2018: 5453-5462.
[24] 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 and Data Mining. New York: ACM, 2018: 974-983.
[25] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1609.02907.
[26] VELICKOVIC P, CUCURULL G, CASANOVA A, et al. Graph attention networks[EB/OL]. [2024-02-23]. https://arxiv.org/abs/1710.10903.
[27] HAMILTON W L, YING R, LESKOVEC J, et al. Inductive representation learning on large graphs[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 1025-1035.
[28] MAURYA S K, LIU X, MURATA T. Graph neural networks for fast node ranking approximation[J]. ACM Transactions on Knowledge Discovery from Data, 2021, 15(5): 1-32.
[29] RAMACHANDRAN K, RJ T. Total centrality: a new centrality measure using graph neural network[J]. SSRN Electronic Journal, 2022. DOI: 10.2139/ssrn.4294847.
[30] PARK N, KAN A, DONG X L, et al. Estimating node importance in knowledge graphs using graph neural networks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2019: 596-606.
[31] DONG Y S, KANG J, TONG H H, et al. Individual fairness for graph neural networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2021: 300-310.
[32] HUANG C J, FANG Y X, LIN X M, et al. Estimating node importance values in heterogeneous information networks[C]//Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. Piscataway: IEEE, 2022: 846-858.
[33] MUNIKOTI S, DAS L, NATARAJAN B. Scalable graph neural network-based framework for identifying critical nodes and links in complex networks[J]. Neurocomputing, 2022, 468: 211-221.
[34] JANA D, MALAMA S, NARASIMHAN S, et al. Edge ranking of graphs in transportation networks using a graph neural network (GNN)[EB/OL]. [2024-02-26]. https://arxiv.org/abs/2303.17485.
[35] GUO Y G, XIE W X, WANG Q R, et al. Betweenness appro-ximation for edge computing with hypergraph neural network[EB/OL]. [2024-02-26]. https://arxiv.org/abs/2203.03958.
[36] QU H B, SONG Y R, LI R Q, et al. GNR: a universal and efficient node ranking model for various tasks based on graph neural networks[J]. Physica A: Statistical Mechanics and Its Applications, 2023, 632: 129339.
[37] CHEN Y K, FANG Y X, WANG Q Y, et al. Deep structural knowledge exploitation and synergy for estimating node importance value on heterogeneous information networks[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2024, 38(8): 8302-8310.
[38] WANG F, SHE J H, OHYAMA Y, et al. Deep-learning-based identification of influential spreaders in online social networks[C]//Proceedings of the IECON 2019 - 45th Annual Conference of the IEEE Industrial Electronics Society. Piscataway: IEEE, 2019: 6854-6858.
[39] ZHAO G H, JIA P, ZHOU A M, et al. InfGCN: identifying influential nodes in complex networks with graph convolutional networks[J]. Neurocomputing, 2020, 414: 18-26.
[40] YU E Y, WANG Y P, FU Y, et al. Identifying critical nodes in complex networks via graph convolutional networks[J]. Knowledge-Based Systems, 2020, 198: 105893.
[41] OU Y, GUO Q, XING J L, et al. Identification of spreading influence nodes via multi-level structural attributes based on the graph convolutional network[J]. Expert Systems with Applications, 2022, 203: 117515.
[42] KOSMATOPOULOS A, LOUMPONIAS K, THEODOSIADOU O, et al. Identification of key actor nodes: a centrality measure ranking aggregation approach[C]//Proceedings of the 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Piscataway: IEEE, 2022: 125-128.
[43] ZHANG C, LI W M, WEI D M, et al. Network dynamic GCN influence maximization algorithm with leader fake labeling mechanism[J]. IEEE Transactions on Computational Social Systems, 2023, 10(6): 3361-3369.
[44] LIU C, CAO T T, ZHOU L X. Learning to rank complex network node based on the self-supervised graph convolution model[J]. Knowledge-Based Systems, 2022, 251: 109220.
[45] ZHANG M, WANG X J, JIN L, et al. A new approach for evaluating node importance in complex networks via deep learning methods[J]. Neurocomputing, 2022, 497: 13-27.
[46] GAO L Y, LIU X Y, LIU C, et al. Key nodes identification in complex networks based on subnetwork feature extraction[J]. Journal of King Saud University -Computer and Information Sciences, 2023, 35(7): 101631.
[47] BHATTACHARYA R, NAGWANI N K, TRIPATHI S. Detecting influential nodes with topological structure via graph neural network approach in social networks[J]. International Journal of Information Technology, 2023, 15(4): 2233-2246.
[48] YU E Y, FU Y, ZHOU J L, et al. Predicting critical nodes in temporal networks by dynamic graph convolutional networks[J]. Applied Sciences, 2023, 13(12): 7272.
[49] SADHU S, BHUIYA A, DUTTA A. DSGCN: a degree strength graph convolution network for identifying influential nodes in complex networks[C]//Proceedings of the 2023 IEEE/WIC International Conference on Web Intelligence and Intelligent Agent Technology. Piscataway: IEEE, 2023: 330-334.
[50] CHEN Z X, SHU J, LIU L L. The node importance evaluation method based on graph convolution in multilayer heterogeneous networks[J]. Connection Science, 2023, 35(1): 2229964.
[51] RASHID Y, BHAT J I. OlapGN: a multi-layered graph convolution network-based model for locating influential nodes in graph networks[J]. Knowledge-Based Systems, 2024, 283: 111163.
[52] MAHMOUD A M, EID H F, DESUKY A S, et al. Graph neural network guided by feature selection and centrality measures for node classification on homophilic and heterophily graphs[J]. Al-Azhar Bulletin of Science, 2024, 35(1): 2.
[53] QIU J Z, TANG J, MA H, et al. DeepInf[C]//Proceedings of the 24th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining. New York: ACM, 2018: 2110-2119.
[54] XIANG Y, FUJIMOTO K, LI F, et al. Identifying influential neighbors in social networks and venue affiliations among young MSM: a data science approach to predict HIV infection[J]. AIDS, 2021, 35: 65-73.
[55] LIU Z M, QIU H, GUO W, et al. NIE-GAT: node importance evaluation method for inter-domain routing network based on graph attention network[J]. Journal of Computational Science, 2022, 65: 101885.
[56] KOU J H, JIA P, LIU J Y, et al. Identify influential nodes in social networks with graph multi-head attention regression model[J]. Neurocomputing, 2023, 530: 23-36.
[57] ZHAO Q, MIAO Y R, AN D D, et al. HGNN-QSSA: heterogeneous graph neural networks with quantitative sampling and structure-aware attention[J]. IEEE Access, 2024, 12: 25512-25524.
[58] FAN C J, ZENG L, DING Y H, et al. Learning to identify high betweenness centrality nodes from scratch[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management. New York: ACM, 2019: 559-568.
[59] RAKARADDI A, PRATAMA M. Unsupervised learning for identifying high eigenvector centrality nodes: a graph neural network approach[C]//Proceedings of the 2021 IEEE International Conference on Big Data. Piscataway: IEEE, 2021: 4945-4954.
[60] HUANG H, SUN L L, DU B W, et al. Representation learning on knowledge graphs for node importance estimation[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2021: 646-655.
[61] TRAN Q M, NGUYEN H D, HUYNH T, et al. Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph[J]. Journal of Combinatorial Optimization, 2022, 44(4): 2919-2945.
[62] XU M, ZHANG J. MGL2Rank: learning to rank the importance of nodes in road networks based on multi-graph fusion[EB/OL]. [2024-03-14]. https://arxiv.org/abs/2305.14375.
[63] LIN J J, LIANG W Y, CHEN G B, et al. Scholar influence maximization via opinion leader and graph embedding regression in social networks[C]//Proceedings of the 18th CCF Conference on Computer Supported Cooperative Work and Social Computing. Singapore: Springer, 2024: 78-92.
[64] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[65] HETHCOTE H W. The mathematics of infectious diseases[J]. SIAM Review, 2000, 42(4): 599-653.
[66] KEMPE D, KLEINBERG J, TARDOS é, et al. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146.
[67] PARK N, KAN A, DONG X L, et al. MultiImport: inferring node importance in a knowledge graph from multiple input signals[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2020: 503-512.
[68] HAN P, WANG J, YAO D, et al. A graph-based approach for trajectory similarity computation in spatial networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2021: 556-564.
[69] CALINSKI T, HARABASZ J. A dendrite method for cluster analysis[J]. Communications in Statistics - Theory and Methods, 1974, 3(1): 780133830.