SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network
This addresses scalability issues in GNNs for graph-level tasks, offering a practical solution for large-scale applications, though it appears incremental as it builds on existing GNN and forest-based methods.
The paper tackles the challenge of scaling Graph Neural Networks (GNNs) to large graphs for graph-level tasks by introducing SHAKE-GNN, a scalable framework based on Kirchhoff Forests that produces multi-scale representations, achieving competitive performance on benchmarks with improved scalability.
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.