Graph Neural Networks for Scalable and Transferable Node Centrality Approximation

2026-07-10 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, quick

Summary

Graph Neural Networks (GNNs) are investigated for scalable approximation of betweenness and closeness centrality, framing the task as a node-ranking problem. The models are supervised using exact centrality values and evaluated with Kendall's tau rank correlation. On unseen Erdos renyi graphs, the proposed GNNs achieved a tau of 0.851 for betweenness and 0.894 for closeness. A large-scale betweenness model, trained on graphs with N = 5,000 nodes, demonstrated scalability with a tau of 0.938. Mixed-distribution training, incorporating Erdos renyi, Barabasi-Albert, and Gaussian Random Partition graphs, significantly improved betweenness transfer across different graph families. However, closeness centrality proved more sensitive to community-structured graphs, exhibiting reduced transfer to real-world topologies. GNN inference also delivered a substantial speedup, up to 97.7x, compared to exact computation. This highlights mixed-distribution training's role in enhancing structural transfer for GNN-based centrality approximation, while identifying closeness centrality's topological sensitivity as an ongoing challenge.

Key takeaway

For machine learning engineers needing efficient node centrality computations in large or varied graph datasets, you should consider implementing GNN-based approximation. This approach offers up to a 97.7x speedup over exact methods. When training your GNNs, prioritize mixed-distribution datasets to significantly improve transferability for betweenness centrality across different graph topologies. Be aware that closeness centrality remains challenging for transfer to real-world graphs, requiring further research or specialized models.

Key insights

GNNs offer scalable and transferable approximation of node centrality, achieving significant speedups, particularly with mixed-distribution training.

Principles

• Mixed-distribution training improves GNN transferability across graph topologies.
• Closeness centrality approximation is highly sensitive to graph topology.

Method

GNNs approximate node centrality by learning a node-ranking function, supervised by exact centrality values and evaluated via Kendall's tau.

In practice

• Apply GNNs for fast betweenness centrality approximation in large networks.
• Implement mixed-distribution training for GNNs to enhance structural transfer.

Topics

• Graph Neural Networks
• Node Centrality
• Transfer Learning
• Graph Topology
• Scalable Graph Algorithms

Best for: AI Engineer, Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Enhancing Graph Neural Networks Using Proximity Graphs for Dust Source Emission Forecasting — Proximity graphs significantly enhance GNNs for complex spatiotemporal forecasting, outperforming random graphs and LSTMs.
• When Spreadsheets Fall Short: A Plain-English Guide to Graph Neural Networks — Graph Neural Networks process interconnected data by converting nodes into embeddings through iterative message passing.
• Generative Modeling on Metric Graphs via Neural Optimal Transport — A novel deep generative model uses neural optimal transport to generate continuous distributions on metric graphs.
• Graph Neural Networks: Just Averaging Neighbors — Graph Neural Networks iteratively average neighbor features to create node vectors summarizing local graph structure.
• Zero-Shot Size Transfer for Neural ODEs on Sparse Random Graphs: Graphon Limits and Adjoint Convergence — Graph Neural Differential Equations (GNDEs) exhibit zero-shot size transfer, enabling training on small graphs for accurate deployment on larger, similar graphs.
• A Fair Evaluation of Graph Foundation Models for Node Property Prediction — Most GFMs for node property prediction do not surpass well-tuned GNNs, except recent Prior-data Fitted Networks with higher cost.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.