SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network

The SHAKE-GNN architecture achieves competitive or superior performance compared to standard GCN baselines, while at the same time significantly reducing training time in several configurations. Across all datasets, we achieved at least 97% of the baseline performance with the cost of at most 50% of the baseline. These results further underscore the importance of architectural design choices. Allocating moderate depth to the coarse levels and optionally incorporating lightweight read-out MLPs helps to recover predictive capacity while preserving efficiency. In this way, SHAKE-GNN demonstrates that carefully tuned multi-resolution decomposition can simultaneously reduce computational burden in line with theoretical complexity estimates and maintain strong performance across diverse graph domains, thereby establishing itself as a principled and practical solution for scalable graph classification.