Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks

Abstract:Computing the importance of nodes in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, whose exact computation becomes prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict the ranking of nodes by betweenness centrality. However, existing GNN-based methods either have graph-size-dependent parameter counts or are limited to undirected graphs. We propose a lightweight GNN architecture that exploits the empirically observed relationship between betweenness centrality and multi-hop degree mass. This motivates the use of degree masses as size-invariant node features. To improve generalization, we train on synthetic graphs whose degree distributions more closely match those of real-world networks, including directed and undirected scale-free graphs and uniformly directed hyperbolic random graphs. We evaluate our model on 14 real-world networks spanning eight domains, including social, email, and citation networks, across both directed and undirected regimes. The experiments show that our model improves the Kendall $\tau_b$ correlation by up to 24.6\% on undirected and 10.9\% on directed graphs, while using 56$\times$ fewer parameters than the lightest competing GNN baseline and achieving competitive inference time, with up to a 24.5$\times$ speedup on selected directed graphs.

Machine Learning (cs.LG)

arXiv:2602.09716 [cs.LG]

(or arXiv:2602.09716v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2602.09716 Focus to learn more arXiv-issued DOI via DataCite

https://doi.org/10.1145/3799682.3840622 Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.