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

CREATORStefano Carotti, Marco Pacini, Alessio Gravina, Davide Bacciu, Bruno Lepri, Sebastiano Bontorin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55578
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text