This paper investigates using Graph Neural Networks (GNNs) to approximate betweenness and closeness centrality as a scalable node-ranking problem. The authors evaluate whether message-passing GNNs can learn transferable structural representations across different graph topologies rather than merely fitting the training distribution.
- On unseen Erdos renyi graphs, models achieved Kendall's tau of 0.851 for betweenness and 0.894 for closeness centrality.
- A large-scale betweenness model trained on graphs with N = 5,000 nodes reached a tau of 0.938, demonstrating scalability.
- Mixed-distribution training across Erdos renyi, Barabasi-Albert, and Gaussian Random Partition graphs improved betweenness transfer across graph families.
- Closeness centrality remained sensitive to community-structured graphs, showing reduced transfer to real-world topologies.
- GNN inference achieved up to a 97.7x speedup over exact computation methods.
The results indicate that mixed-distribution training improves structural transfer in GNN-based centrality approximation, while highlighting closeness centrality's sensitivity to topology as an open challenge.