BRAVA-GNN: Betweenness Ranking Approximation Via Degree MAss Inspired Graph Neural Network
Authors:
- Justin DachilleJDJustin Dachille
- Aurora RossiARAurora Rossi
- Sunil Kumar MauryaSMSunil Kumar Maurya
- Frederik Mallman-TrennFMFrederik Mallman-Trenn
- Xin LiuXLXin Liu
- Frédéric GiroireFGFrédéric Giroire
- Tsuyoshi MurataTMTsuyoshi Murata
- Emanuele NataleENEmanuele Natale
- Frederik Mallman- TrennFTFrederik Mallman- Trenn
Preprint
Abstract
Computing node importance 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, which becomes computationally prohibitive on large‑scale networks.Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state‑of‑the‑art methods fail to generalize to high‑diameter graphs such as road networks.We propose BRAVA‑GNN, a lightweight GNN architecture that leverages the empirically observed correlation linking betweenness centrality to degree‑based quantities, in particular multi-hop degree mass. This correlation motivates the use of degree masses as size-invariant node features and synthetic training graphs that closely match the degree distributions of real networks.Furthermore, while previous work relies on scale-free synthetic graphs, we leverage the hyperbolic random graph model, which reproduces power‑law exponents outside the scale‑free regime, better capturing the structure of real‑world graphs like road networks.This design enables BRAVA-GNN to generalize across diverse graph families while using 54$\times$ fewer parameters than the most lightweight existing GNN baseline. Extensive experiments on 19 real-world networks, spanning social, web, email, and road graphs, show that BRAVA-GNN achieves up to 214\% improvement in Kendall–Tau correlation and up to 70$\times$ speedup in inference time over state-of-the-art GNN-based approaches, particularly on challenging road networks.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Betweenness centrality of teams in social networksChaos: An Interdisciplinary Journal of Nonlinear Science, 2021
- The diameter of KPKVB random graphsAdvances in Applied Probability, 2019
- NetworKit: A tool suite for large-scale complex network analysisNetwork Science, 2016
- Into the Square: On the Complexity of Some Quadratic-time Solvable ProblemsElectronic Notes in Theoretical Computer Science, 2016
- Augmented Betweenness Centrality for Environmentally Aware Traffic Monitoring in Transportation NetworksJournal of Intelligent Transportation Systems, 2012
- Random Hyperbolic Graphs: Degree Sequence and Clustering2012
- Hyperbolic geometry of complex networksPhysical Review E, 2010
- Sustaining the Internet with hyperbolic mappingNature Communications, 2010
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001