# On Measuring Long-Range Interactions in Graph Neural Networks

arXiv: https://arxiv.org/abs/2506.05971 · HTML: https://mlsanity.com/paper/2506.05971/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 52 references that are in the map.
- First posted on arXiv 6 Jun 2025.

## Builds on (most cited first, 30 of 40)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2402.00789/) (2024)
- [Fake News Detection on Social Media using Geometric Deep Learning](https://mlsanity.com/paper/1902.06673/) (2019)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark](https://mlsanity.com/paper/2309.00367/) (2023)
- [DRew: Dynamically Rewired Message Passing with Delay](https://mlsanity.com/paper/2305.08018/) (2023)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)

## Built on by (most cited first, 11 of 11)

- [Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Tasks](https://mlsanity.com/paper/2506.07624/) (2025)
- [Can You Hear Me Now? A Benchmark for Long-Range Graph Propagation](https://mlsanity.com/paper/2512.17762/) (2025)
- [Over-squashing in Spatiotemporal Graph Neural Networks](https://mlsanity.com/paper/2506.15507/) (2025)
- [Position: Don't be Afraid of Over-Smoothing And Over-Squashing](https://mlsanity.com/paper/2601.07419/) (2026)
- [Quantifying Memory Use in Reinforcement Learning with Temporal Range](https://mlsanity.com/paper/2512.06204/) (2025)
- [Can Graph Foundation Models Generalize Over Architecture?](https://mlsanity.com/paper/2603.22984/) (2026)
- [Graph Hierarchical Recurrence for Long-Range Generalization](https://mlsanity.com/paper/2605.18387/) (2026)
- [Ramanujan Graph Rewiring with Non Negative Resistance Curvature](https://mlsanity.com/paper/2606.21333/) (2026)
- [Reachability is not enough: Diagnosing long-range behavior in GNNs](https://mlsanity.com/paper/2609.33674/) (2026)
- [Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing](https://mlsanity.com/paper/2610.03556/) (2026)
- [Global Communication or Graph-Specific Memory?](https://mlsanity.com/paper/2610.05874/) (2026)

## Abstract (arXiv)

Long-range graph tasks -- those dependent on interactions between distant nodes -- are an open problem in graph neural network research. Real-world benchmark tasks, especially the Long Range Graph Benchmark, have become popular for validating the long-range capability of proposed architectures. However, this is an empirical approach that lacks both robustness and theoretical underpinning; a more principled characterization of the long-range problem is required. To bridge this gap, we formalize long-range interactions in graph tasks, introduce a range measure for operators on graphs, and validate it with synthetic experiments. We then leverage our measure to examine commonly used tasks and architectures, and discuss to what extent they are, in fact, long-range. We believe our work advances efforts to define and address the long-range problem on graphs, and that our range measure will aid evaluation of new datasets and architectures.