mlsanityData to 7 Oct 2026

On Measuring Long-Range Interactions in Graph Neural Networks

arXiv 2506.05971 ↗First posted 6 Jun 2025cs.LG cs.AIcited by 9

Not on the map. Why?

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.

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

Builds on

40 of 52 references.

References · 40

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2017Understanding Black-box Predictions via Influence Functionscited by 1,714
  6. 2019Strategies for Pre-training Graph Neural Networkscited by 964
  7. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  8. 2019Graph Neural Networks for Social Recommendationcited by 711
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  10. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  12. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
28 more
  1. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  2. 2019Diffusion Improves Graph Learningcited by 414
  3. 2017Residual Gated Graph ConvNetscited by 341
  4. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  5. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  6. 2022Long Range Graph Benchmarkcited by 258
  7. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  8. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 193
  9. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  10. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  11. 2024Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spacescited by 132
  12. 2019Fake News Detection on Social Media using Geometric Deep Learningcited by 115
  13. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 104
  14. 2023Understanding Oversquashing in GNNs through the Lens of Effective Resistancecited by 94
  15. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  16. 2023Where Did the Gap Go? Reassessing the Long-Range Graph Benchmarkcited by 83
  17. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  18. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  19. 2022Expander Graph Propagationcited by 75
  20. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  21. 2023How does over-squashing affect the power of GNNs?cited by 53
  22. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  23. 2025On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learningcited by 42
  24. 2023Cooperative Graph Neural Networkscited by 35
  25. 2025Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learningcited by 18
  26. 2021Hierarchical graph neural nets can capture long-range interactionscited by 12
  27. 2024SpoT-Mamba: Learning Long-Range Dependency on Spatio-Temporal Graphs with Selective State Spacescited by 7
  28. 2020Improving the Long-Range Performance of Gated Graph Neural Networkscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 5.

9 papers.

  1. 2025Return of ChebNet: Understanding and Improving an Overlooked GNN on Long Range Taskscited by 12
  2. 2025Can You Hear Me Now? A Benchmark for Long-Range Graph Propagationcited by 8
  3. 2025Over-squashing in Spatiotemporal Graph Neural Networkscited by 6
  4. 2026Position: Don't be Afraid of Over-Smoothing And Over-Squashingcited by 1
  5. 2025Quantifying Memory Use in Reinforcement Learning with Temporal Rangecited by 0
  6. 2026Can Graph Foundation Models Generalize Over Architecture?cited by 0
  7. 2026Graph Hierarchical Recurrence for Long-Range Generalizationcited by 0
  8. 2026Ramanujan Graph Rewiring with Non Negative Resistance Curvaturecited by 0
  9. 2026Reachability is not enough: Diagnosing long-range behavior in GNNscited by 0