Graph Hierarchical Recurrence for Long-Range Generalization
Stefano Carotti, Marco Pacini, Alessio Gravina, Davide Bacciu, Bruno Lepri, Sebastiano Bontorin · 2026
Read Graph Hierarchical Recurrence for Long-Range Generalization by Stefano Carotti, Marco Pacini, Alessio Gravina, Davide Bacciu, Bruno Lepri, Sebastiano Bontorin (2026) 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-2605-18387.txt.
Introduction
Stefano Carotti and five co-authors present Graph Hierarchical Recurrence, a 2026 method that runs graph learning on both the input graph and a pooled hierarchical abstraction. Standard graph networks struggle when predictions hinge on links between distant regions, and degrade sharply when tests demand longer-range interactions than training showed. Across long-range benchmarks, the method strengthens every tested message-passing backbone and matches or beats the state of the art.
Catalog record
| CREATOR | Stefano Carotti, Marco Pacini, Alessio Gravina, Davide Bacciu, Bruno Lepri, Sebastiano Bontorin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55578 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18387
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Hierarchical Recurrence for Long-Range Generalization Stefano Carotti, Marco Pacini, Alessio Gravina, Davide Bacciu, Bruno Lepri, Sebastiano Bontorin Abstract Graph Neural Networks (GNNs) and Graph Transformers (GTs) are now a fundamental paradigm for graph learning, combining the representation-learning capabilities of deep models with the sample efficiency induced by their inductive biases. Despite their effectiveness, a large body of work has shown that these models still face fundamental limitations in tasks that require capturing correlations between distant regions of a graph. To address this issue, we introduce Graph Hierarchical Recurrence (GHR), a novel framework that operates jointly on the input graph and on a hierarchical abstraction obtained through pooling. We also show that the limitations of existing models are even more pronounced in out-of-range generalization , where test instances involve interactions over distances longer than those observed during training. By contrast, despite its simple design, GHR provides three key advantages: strong performance on long-range dependencies, improved out-of-range generalization, and high parameter efficiency. To corroborate these claims, we show that across a broad set of long-range benchmarks, GHR consistently outperforms existing graph models while using as little as 1 % 1\% of the parameters of current state-of-the-art models. These results suggest a complementary direction to the current trend of scaling architectures to obtain graph foundation models, indicating that increased model capacity alone may not be sufficient for generalization. † † footnotetext: 1 Department of Computer Science, University of Trento, Italy. 2 Fondazione Bruno Kessler, Italy. 3 Department of Computer Science, University of Pisa, Italy. Correspondence: [email protected] . 1 Introduction Figure 1: Out-of-Range Generalization for Graph Hierarchical Recurrence. Predicted distances on Single Source Shortest Path (SSSP) task from a sample source node in a Random Geometric Graph (RGG). We compare DeepGIN (10 layers) with our model GHR ( T_{L}=4 , T_{H}=3 ), both trained on distances of up to 10 hops. While both GIN and GHR accurately predict on in-range distances, only GHR achieves out-of-range generalization . Graph Neural Networks (GNNs) ( 24 ; 30 ) have become the standard framework for learning on graph-structured data. While most approaches rely on Message-Passing Neural Networks (MPNNs) ( 14 ) to propagate information through the graph, they are often affected by persistent well-known pathologies that hinder effective information propagation. First, over-squashing ( 1 ; 34 ; 9 ; 26 ) compresses an exponentially growing receptive field into a fixed-size vector node representation. Second, over-smoothing ( 27 ; 7 ) drives node features toward homogeneous and indistinguishable embeddings. Third, and more generally, training deep MPNNs suffers from vanishing gradients contributing to a poor node representation evolution dynamics ( 3 ) , exacerbating the previous issues and further limiting information to flow across large graph distances. Several solutions have been proposed to address these limitations. These include: graph rewiring ( 34 ; 18 ) and virtual nodes ( 32 ) , which introduce additional edges to shorten signal traversal, harming the topological information ( 1 ; 2 ) ; and Graph Transformers ( 10 ; 29 ) , which enable direct interactions between arbitrary node pairs via attention mechanisms, incurring quadratic computational complexity. Alternatively, hierarchical pooling methods construct multi-scale representations where distant nodes become closer at the high level ( 8 ; 38 ; 13 ) , typically generating the pooled abstraction in the feedforward architecture. Outside the graph domain, the transformer-based Hierarchical Reasoning Model (HRM) ( 37 ) has shown that a hierarchical recurrent architecture can achieve substantial computational depth within a compact parameter budget. Recurrent architectures provide an alternative paradigm for graph processing ( 30 ; 17 ; 33 ) . By reusing the same parameters across iterative steps, recurrent GNNs naturally enable extrapolation to larger graphs and longer reasoning horizons ( 36 ) . This property is particularly important in settings where training on full-scale graphs is infeasible, such as large-scale graph algorithmic problems ( 36 ) or predictions over massive knowledge graphs ( 19 ) . However, the approaches discussed above have their own limitations. In particular, rewiring creates non-existent edges, which distorts the topology of graphs, harming the inductive bias ( 1 ; 34 ) . Fully-connected attention incurs quadratic computational complexity, preventing scalability as the number of nodes increases ( 10 ; 29 ) . Conversely, recurrent architectures and NAR models operate on the original flat topology. Reaching distant nodes requires unrolling the shared message-passing process for a number of steps proportional to the graph diameter ( 22 ) . This produces over-squashing ( 1 ) and induces vanishing gradients during backpropagation ( 28 ; 3 ) . To better characterize these limitations, we introduce a more precise nomenclature: in-range generalization and out-of-range generalization . We refer to in-range generalization as the ability to propagate information and generalize to test instances that require interaction distances observed during training. Conversely, we refer to out-of-range generalization as the capacity to extrapolate and propagate information beyond the interaction distances observed during training. To address long-range generalization, both in- and out-of-range, we introduce Graph Hierarchical Recurrence (GHR), a framework that revitalizes the recurrent paradigm by combining it with multi-scale graph representations as shown in Figure 2 . In particular, GHR combines a two-timescale recurrent scheme inspired by ( 37 ) with a hierarchical pooling mechanism that constructs an abstracted graph without introducing artificial edges. By running two coupled message-passing processes on the original and high-level graphs, GHR enables efficient long-range propagation while preserving the inductive bias of the underlying topology. Unlike prior methods ( 38 ; 13 ) that use pooling as a feedforward downsampling layer, GHR alternates pooling and unpooling inside a recurrent loop, exploiting the pooled abstraction as a parallel routing that acts as a shortcut for long-range message passing. Our contributions are summarized as follows: • We introduce GHR, a dual-level recurrent architecture that uses graph pooling to build a hierarchy with two message-passing streams. The high-level stream operates on the pooled graph and guides the low-level stream operating on the original graph. • We validate these claims through an extensive experimental analysis on key benchmarks for long-range interactions, achieving state-of-the-art or competitive performance while often using one to two orders of magnitude fewer trainable parameters. • Through ablation studies in controlled, stylized settings, we show that each individual component of GHR is necessary for out-of-range generalization, as illustrated in Figure 1 . Figure 2: Visualization of the global recurrent step \mathcal{R}_{W} . Visual representation of the nested recurrent scheme as described in Algorithm 2 . \mathcal{R}_{L,W_{L}} and \mathcal{R}_{H,W_{H}} propagate nodes’ information across the low-level graph G_{L} and the high level abstraction G_{H} . Message passing is interleaved between two layers in a nested weight-sharing scheme, which enables deep computation with a minimal parameter budget. 2 Preliminaries Graphs and Features. Let G=(V,E,\mathbf{X},\mathbf{e}) be an attributed graph, where V is a finite set of nodes and E\subseteq\{\{i,j\}:i,j\in V,\,i\neq j\} is the edge set. Each node u\in V is associated with a feature vector \mathbf{x}_{u}\in\mathbb{R}^{d_{n}} , and the matrix collecting all node features is denoted by \mathbf{X}\in\mathbb{R}^{|V|\times d_{n}} . Each edge \{i,j\}\in E is associated with an edge feature \mathbf{e}_{ij}\in\mathbb{R}^{d_{e}} , and we denote the collection of all edge features by \mathbf{e}=\{\mathbf{e}_{ij}:\{i,j\}\in E\} . Finally, we define the local neighborhood of a node i