# Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach

arXiv: https://arxiv.org/abs/1905.10418 · HTML: https://mlsanity.com/paper/1905.10418/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2019.

## Built on by (most cited first, 16 of 16)

- [Simplifying approach to Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2111.06748/) (2021)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [Stable Prediction on Graphs with Agnostic Distribution Shift](https://mlsanity.com/paper/2110.03865/) (2021)
- [Inductive Meta-path Learning for Schema-complex Heterogeneous Information Networks](https://mlsanity.com/paper/2307.03937/) (2023)
- [RoME: Domain-Robust Mixture-of-Experts for MILP Solution Prediction across Domains](https://mlsanity.com/paper/2511.02331/) (2025)
- [Demystifying Bitcoin Address Behavior via Graph Neural Networks](https://mlsanity.com/paper/2211.14582/) (2022)
- [Node Centrality Approximation For Large Networks Based On Inductive Graph Neural Networks](https://mlsanity.com/paper/2403.04977/) (2024)
- [Unsupervised Learning for Identifying High Eigenvector Centrality Nodes: A Graph Neural Network Approach](https://mlsanity.com/paper/2111.05264/) (2021)
- [Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2309.07153/) (2023)
- [PINE: Pipeline for Important Node Exploration in Attributed Networks](https://mlsanity.com/paper/2512.07244/) (2025)
- [Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks](https://mlsanity.com/paper/2602.09716/) (2026)
- [Centrality-Based Pruning for Efficient Echo State Networks](https://mlsanity.com/paper/2603.20684/) (2026)
- [Can one hear the position of nodes?](https://mlsanity.com/paper/2211.06325/) (2022)
- [Edge Ranking of Graphs in Transportation Networks using a Graph Neural Network (GNN)](https://mlsanity.com/paper/2303.17485/) (2023)
- [CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs](https://mlsanity.com/paper/2506.14122/) (2025)
- [Graph Neural Networks for Scalable and Transferable Node Centrality Approximation](https://mlsanity.com/paper/2607.09372/) (2026)

## Abstract (arXiv)

Betweenness centrality (BC) is one of the most used centrality measures for network analysis, which seeks to describe the importance of nodes in a network in terms of the fraction of shortest paths that pass through them. It is key to many valuable applications, including community detection and network dismantling. Computing BC scores on large networks is computationally challenging due to high time complexity. Many approximation algorithms have been proposed to speed up the estimation of BC, which are mainly sampling-based. However, these methods are still prone to considerable execution time on large-scale networks, and their results are often exacerbated when small changes happen to the network structures. In this paper, we focus on identifying nodes with high BC in a graph, since many application scenarios are built upon retrieving nodes with top-k BC. Different from previous heuristic methods, we turn this task into a learning problem and design an encoder-decoder based framework to resolve the problem. More specifcally, the encoder leverages the network structure to encode each node into an embedding vector, which captures the important structural information of the node. The decoder transforms the embedding vector for each node into a scalar, which captures the relative rank of this node in terms of BC. We use the pairwise ranking loss to train the model to identify the orders of nodes regarding their BC. By training on small-scale networks, the learned model is capable of assigning relative BC scores to nodes for any unseen networks, and thus identifying the highly-ranked nodes. Comprehensive experiments on both synthetic and real-world networks demonstrate that, compared to representative baselines, our model drastically speeds up the prediction without noticeable sacrifce in accuracy, and outperforms the state-of-the-art by accuracy on several large real-world networks.