aiqbench analysis
SHAKE-GNN addresses the critical bottleneck of scaling Graph Neural Networks for large-scale graph-level tasks by leveraging hierarchical Kirchhoff Forests for stochastic multi-resolution decomposition. This approach enables flexible trade-offs between computational efficiency and model performance, with data-driven parameter selection validated across multiple benchmarks. The work represents a significant methodological advance in making GNNs viable for massive datasets without sacrificing accuracy.
SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network
arXiv:2509.22100v2 Announce Type: replace Abstract: Graph Neural Networks (GNNs) have achieved remarkable success across a range of learning tasks. However, scaling GNNs to large graphs remains a significant challenge, especially for graph-level tasks. In this work, we introduce SHAKE-GNN, a novel scalable graph-level GNN framework based on a hierarchy of Kirchhoff Forests, a class of random spanning forests used to construct stochastic multi-resolution decompositions of graphs. SHAKE-GNN produces multi-scale representations, enabling flexible trade-offs between efficiency and performance. We introduce an improved, data-driven strategy for selecting the trade-off parameter and analyse the time-complexity of SHAKE-GNN. Experimental results on multiple large-scale graph classification benchmarks demonstrate that SHAKE-GNN achieves competitive performance while offering improved scalability.
Abstract:Graph Neural Networks (GNNs) have achieved remarkable success across a range of learning tasks. However, scaling GNNs to large graphs remains a significant challenge, especially for graph-level tasks. In this work, we introduce SHAKE-GNN, a novel scalable graph-level GNN framework based on a hierarchy of Kirchhoff Forests, a class of random spanning forests used to construct stochastic multi-resolution decompositions of graphs. SHAKE-GNN produces multi-scale representations, enabling flexible trade-offs between efficiency and performance. We introduce an improved, data-driven strategy for selecting the trade-off parameter and analyse the time-complexity of SHAKE-GNN. Experimental results on multiple large-scale graph classification benchmarks demonstrate that SHAKE-GNN achieves competitive performance while offering improved scalability.
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2509.22100 [cs.LG]
(or arXiv:2509.22100v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2509.22100 Focus to learn more arXiv-issued DOI via DataCite
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.
Full text under the publisher's open licence · 202 words
Related coverage
PIRAMID: Progress and Plans
LessWrong · Jul 27, 2026
News
Quantum Computing Report · Jul 25, 2026
HI-MeshGraphNets: Efficient and Accurate Mesh-based Physics Learning with Hierarchical Multi-scale Graph Neural Networks
arXiv · Aug 17, 2026
Graph-Based Inference and Topology-Aware Multi-Agent Reinforcement Learning for Large-Scale Railway Network Management
arXiv · Sep 26, 2026