Graph Hierarchical Recurrence for Long-Range Generalization

Graph Neural Networks and Graph Transformers have become central to graph learning, combining expressive representation learning with sample-efficient in- ductive biases. Yet they remain fundamentally limited when predictions depend on correlations between distant graph regions. We address this limitation with Graph Hierarchical Recurrence (GHR), a novel framework that jointly operates on the input graph and a pooled hierarchical abstraction. We also show that ex- isting models degrade more sharply under out-of-range generalization, where test instances require interactions across distances exceeding those observed during training. Despite its minimal design, GHR consistently strengthens every tested message-passing backbone, yielding robust performance on long-range dependen- cies and particularly pronounced gains in out-of-range regimes. Across a broad suite of long-range benchmarks, GHR achieves state-of-the-art or competitive re- sults on multiple tasks, establishing hierarchical recurrence as an effective mech- anism for extending graph models beyond their observed interaction range.