# Learning Long Range Dependencies on Graphs via Random Walks

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 71 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [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)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model](https://mlsanity.com/paper/2401.09417/) (2024)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [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)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (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)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)

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

- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [Flock: A Knowledge Graph Foundation Model via Learning on Random Walks](https://mlsanity.com/paper/2510.01510/) (2025)
- [AI Research Agents Narrow Scientific Exploration](https://mlsanity.com/paper/2605.27905/) (2026)
- [Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention](https://mlsanity.com/paper/2407.05649/) (2024)
- [Toward a Graph Foundation Model: Pre-Training Transformers With Random Walks](https://mlsanity.com/paper/2506.14098/) (2025)
- [Chimera: State Space Models Beyond Sequences](https://mlsanity.com/paper/2510.12111/) (2025)
- [Generalizable Insights for Graph Transformers in Theory and Practice](https://mlsanity.com/paper/2511.08028/) (2025)
- [Random Search Neural Networks for Efficient and Expressive Graph Learning](https://mlsanity.com/paper/2510.22520/) (2025)
- [From Message-Passing to Linearized Graph Sequence Models](https://mlsanity.com/paper/2605.12358/) (2026)
- [End-to-End Subgraph Detection with GraphDETR](https://mlsanity.com/paper/2606.06364/) (2026)
- [Differential Encoding for Improved Representation Learning over Graphs](https://mlsanity.com/paper/2407.02758/) (2024)
- [Are Graph Attention Networks Able to Model Structural Information?](https://mlsanity.com/paper/2505.21288/) (2025)
- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)
- [Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchies](https://mlsanity.com/paper/2509.01381/) (2025)
- [Plain Transformers are Surprisingly Powerful Link Predictors](https://mlsanity.com/paper/2602.01553/) (2026)
- [DuConTE: Dual-Granularity Text Encoder with Topology-Constrained Attention for Text-attributed Graphs](https://mlsanity.com/paper/2604.17411/) (2026)
- [GLACIER: Rethinking Mass Spectrum Prediction as an Object Detection Problem](https://mlsanity.com/paper/2606.29161/) (2026)

## Abstract (arXiv)

Message-passing graph neural networks (GNNs) excel at capturing local relationships but struggle with long-range dependencies in graphs. In contrast, graph transformers (GTs) enable global information exchange but often oversimplify the graph structure by representing graphs as sets of fixed-length vectors. This work introduces a novel architecture that overcomes the shortcomings of both approaches by combining the long-range information of random walks with local message passing. By treating random walks as sequences, our architecture leverages recent advances in sequence models to effectively capture long-range dependencies within these walks. Based on this concept, we propose a framework that offers (1) more expressive graph representations through random walk sequences, (2) the ability to utilize any sequence model for capturing long-range dependencies, and (3) the flexibility by integrating various GNN and GT architectures. Our experimental evaluations demonstrate that our approach achieves significant performance improvements on 19 graph and node benchmark datasets, notably outperforming existing methods by up to 13% on the PascalVoc-SP and COCO-SP datasets. The code is available at https://github.com/BorgwardtLab/NeuralWalker.