SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network
Zhipu CUI & Johannes Lutzeyer · 2025
Read SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network by Zhipu CUI & Johannes Lutzeyer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22100.txt.
Introduction
Zhipu Cui and Johannes Lutzeyer present SHAKE-GNN in this 2025 paper, a graph neural network built to scale to very large graphs. Such networks learn from connected data, but whole-graph tasks, like classifying an entire network, strain them as graphs grow. The team's framework rests on Kirchhoff forests: random collections of spanning trees that break a graph into pieces at several scales at once.
From that hierarchy, SHAKE-GNN builds representations at multiple resolutions, so a user can trade computing cost against accuracy. The paper adds a data-driven way to choose that trade-off setting, improving on earlier hand-set choices, and analyzes the running time of the method. On several large graph classification benchmarks, SHAKE-GNN matched competitive performance while scaling better than rivals. The authors present the multi-resolution view as the source of that flexibility.
Catalog record
| CREATOR | Zhipu CUI & Johannes Lutzeyer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22100
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SHAKE-GNN: Scalable Hierarchical Kirchhoff-Forest Graph Neural Network Zhipu CUI & Johannes Lutzeyer 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. 1 Introduction Graph classification is a fundamental task in graph machine learning, in which one aims to determine the class of an entire graph based on its structure and attributes. This task is widely applicable across domains such as molecular property prediction, e.g., identifying active versus inactive compounds ( Wu et al. 2021 ) , social network analysis, e.g., bot detection ( Zhou et al. 2020 ) , and communication system diagnostics, e.g., faulty topology detection ( Zhang et al. 2022 ) . With the rapid advancement of Graph Neural Networks (GNNs), many approaches have achieved impressive results by leveraging local neighbourhood information through message passing ( Gilmer et al. 2017 ) . Despite their success, significant challenges remain in terms of scalability and global structure modelling, especially when dealing with large and complex graphs, such as protein graphs and social networks among others. Early GNNs such as Graph Convolutional Networks (GCNs) ( Kipf & Welling 2017 ) , Graph Attention Networks (GATs) ( Veličković et al. 2018 ) , and Graph Isomorphism Networks (GINs) ( Xu et al. 2019 ) rely on iterative message passing between neighbouring nodes. While these models exhibit linear time complexity in the number of edges and are effective for small to moderately sized graphs, their scalability can be further enhanced. In particular, repeated aggregation steps across multiple layers may incur redundant computations and memory overhead when deployed on large-scale or densely connected graphs. Furthermore, their design typically emphasises fine-grained, local feature interactions at the node level, which often leads to over-fragmented representations that fail to capture long-range dependencies and global semantic structure, which are critical components in tasks requiring global graph understanding. To address these limitations, we propose a new model called Scalable Hierarchical Kirchhoff-Forest Graph Neural Network (SHAKE-GNN) , a novel hierarchical graph neural architecture that constructs multi-resolution representations via a Kirchhoff Forest-based coarse-graining method. A spanning forest is a collection of spanning trees, each covering a connected component of a graph without forming cycles. Building on this, Kirchhoff Forests (KFs) are probabilistic ensembles of spanning forests, where the probability of each forest is determined by the graph Laplacian. This formulation provides a principled way to capture structural dependencies and connectivity patterns within graphs. Instead of relying on random or flat clustering schemes, we introduce a principled, layer-wise node merging strategy guided by Kirchhoff Forests (KFs), which generates a hierarchy of coarsened graphs. Each coarse node aggregates a substructure from the previous layer, using mean or sum pooling for node and edge features depending on the dataset. Our main contributions are summarised as follows: • We define a hierarchical graph decomposition pipeline based on KFs and integrate it with the model architecture SHAKE-GNN, which effectively leverages multi-resolution structural information for graph classification tasks. This framework is applicable across diverse graph domains and scales efficiently to large datasets. • We introduce an improved strategy for selecting the resolution parameter q , balancing computational complexity and information loss, and provide a theoretical time complexity analysis that demonstrates the scalability advantages of our architecture over conventional GNN frameworks in multi-resolution settings. • We empirically validate our approach through extensive experiments, showing that it achieves scalability compared to state-of-the-art GNN models. 2 Related Work Graph Neural Networks (GNNs). Graph Neural Networks (GNNs) have emerged as a powerful paradigm for representation learning on graph-structured data. GNNs function by recursively aggregating information from local neighbourhoods. The seminal Graph Convolutional Network (GCN) ( Kipf & Welling 2017 ) combines a node’s features with those of its neighbours and calculates a weighted average over neighbourhoods. Subsequent extensions such as Graph Attention Networks (GAT) ( Veličković et al. 2018 ) introduce adaptive weighting via an attention mechanism, while Graph Isomorphism Networks (GIN) ( Xu et al. 2019 ) employ injective aggregation functions to enhance expressive capacity. These models have been successfully applied to a range of tasks. Typical examples include molecular property prediction ( Hu et al. 2020 ) , citation graph classification ( Sen et al. 2008 ; Yang et al. 2016 ) , and social network modeling ( Hamilton et al. 2017 ; Li et al. 2020 ) . Despite their empirical success, conventional GNNs encounter significant limitations when scaled to large or densely connected graphs. Their reliance on multi-hop message passing increases computational overhead, particularly in deep architectures ( Dwivedi et al. 2022 ) . Moreover, their inherently local aggregation mechanisms often struggle to capture long-range dependencies and global semantics, resulting in representations that are focused on neighborhood-level patterns. Graph Pooling and Coarsening. To mitigate the locality and scalability issues inherent in GNNs, various graph pooling and coarsening techniques have been developed to enable hierarchical representation learning. Differentiable Pooling (DiffPool) ( Ying et al. 2018 ) introduces differentiable assignment matrices to softly cluster nodes into coarse representations, facilitating end-to-end hierarchical learning. Graph clustering using weighted cuts (Graclus) ( Dhillon et al. 2007 ) adopts a greedy coarsening strategy based on graph cuts, while minimum-cut-based pooling (minCUT pooling) ( Bianchi et al. 2020 ) imposes spectral regularisation to enforce partition quality. Traditional graph partitioning algorithms, such as METIS ( Karypis & Kumar 1998 ) , employ multilevel coarsening and refinement heuristics to minimize edge cuts while maintaining balanced partition sizes. This has enabled GNNs to scale to graphs with billions of nodes. A recent extension, LPMetis ( Zeng et al. 2023 ) , integrates label propagation into the coarsening phase to improve scalability and partition quality, particularly for distributed GNN training. Nevertheless, METIS and its variants are inherently non-stochastic. Personalised PageRank for Node-Level Scalability. To mitigate the computational inefficiencies associated with recursive message passing in Graph Neural Networks (GNNs), recent research has proposed decoupling feature propagation from transformation via Personalised PageRank (PPR) scores. An illustrative instance of this approach is PPRGo ( Bojchevski et al. 2020 ) , which utilises a precomputed and sparsified approximation to facilitate efficient feature aggregation. Despite their efficiency, PPR-based models such as PPRGo are node-centric in design. Each node’s prediction is computed conditioned solely on its personalised neighbourhood. This localised perspective, while computationally advantageous, limits their applicability to graph-level tasks, such as molecular property prediction or program classification, where coarse-grained, hierarchical, or long-range interactions are significant. 3 Preliminary In this section, we introduce the fundamental concepts required for our framework. We begin by recalling classical notions of spanning trees and spanning forests, which serve as the basis of Kirchhoff Forests. Definition 3.1 (Spanning Tree) . A spanning tree of \mathcal{G} is a subgraph \mathcal{T}=(\mathcal{V}_{\mathcal{T}},\mathcal{E}_{\mathcal{T}}) such