Research map / Graph learning / GNN architectures
Learning Long Range Dependencies on Graphs via Random Walks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes NeuralWalker, which treats sampled non-backtracking random walks as sequences processed by sequence models (Mamba, S4, CNN, transformer) interleaved with local GNN and global transformer/virtual-node message passing, evaluated on 19 graph and node benchmarks.
Problem
GNNs struggle with long-range dependencies and graph transformers compress graph structure into fixed-length node vectors, losing structural information; prior random-walk models (CRaWL) rely on small-kernel CNNs and lack message passing.
Approach
Treat random walks explicitly as sequences and process them with long-sequence models (bidirectional Mamba/SSMs), average walk-token features back to nodes, and interleave with local (GIN) and optional global message passing, yielding provably more expressive representations than 1-WL and CRaWL.
Key results
- Achieves up to ~10-13% improvement over the best baseline on PascalVOC-SP (F1 0.4912) and COCO-SP (F1 0.4398) in LRGB.
- Reaches ZINC MAE 0.053 with masked positional-encoding pretraining, versus 0.070 for GPS and 0.085 for CRaWL.
- Ablation: Mamba outperforms S4, CNN, and transformer sequence layers; transformers underperform on walk embeddings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add GIN local message passing to NeuralWalker (ablation) | NeuralWalker with Mamba · ZINC validation | MAE: 0.090 -> 0.085 | Helped |
| Add GIN local message passing to NeuralWalker (ablation) | NeuralWalker with Mamba · CIFAR10 validation | accuracy: 79.035 -> 80.885 | Helped |
| Add GIN local message passing to NeuralWalker (ablation) | NeuralWalker with Mamba · PascalVOC-SP validation | F1: 0.4525 -> 0.4611 | Helped |
| Add virtual-node global message passing (ablation) | NeuralWalker with GIN and Mamba · ZINC validation | MAE: 0.085 -> 0.078 | Helped |
| Add virtual-node global message passing (ablation) | NeuralWalker with GIN and Mamba · CIFAR10 validation | accuracy: 80.885 -> 78.610 | Hurt |
| Add virtual-node global message passing (ablation) | NeuralWalker with GIN and Mamba · PascalVOC-SP validation | F1: 0.4611 -> 0.4672 | Helped |
| Add transformer global message passing (ablation) | NeuralWalker with GIN and Mamba · ZINC validation | MAE: 0.085 -> 0.083 | Helped |
| Add transformer global message passing (ablation) | NeuralWalker with GIN and Mamba · CIFAR10 validation | accuracy: 80.885 -> 80.755 | No clear effect |
| Add transformer global message passing (ablation) | NeuralWalker with GIN and Mamba · PascalVOC-SP validation | F1: 0.4611 -> 0.4877 | Helped |
| Use bidirectional rather than unidirectional Mamba (ablation) | NeuralWalker · CIFAR10 validation | accuracy: 74.910 -> 80.885 | Helped |
| Use S4 instead of bidirectional Mamba (ablation) | NeuralWalker · CIFAR10 validation | accuracy: 80.885 -> 77.970 | Hurt |
| Use CNN instead of bidirectional Mamba (ablation) | NeuralWalker · CIFAR10 validation | accuracy: 80.885 -> 80.665 | Hurt |
Surprising findings
- Transformers consistently underperformed other sequence layers when applied to random walk embeddings, despite strong results elsewhere.
- Global message passing benefit varies across datasets; on some (CIFAR10) virtual node hurt performance.
Limitations
- Trade-off between random walk sampling efficiency and graph coverage on very large graphs.
- Few public graph datasets with well-defined long-range dependencies; only 2 of 5 LRGB datasets seem to exhibit them.
Experimental setup
Datasets: ZINC MNIST CIFAR10 PATTERN CLUSTER PascalVOC-SP COCO-SP Peptides-func Peptides-struct PCQM-Contact ogbg-molpcba ogbg-ppa
Benchmarks: ZINC MNIST CIFAR10 PATTERN CLUSTER PascalVOC-SP COCO-SP Peptides-func Peptides-struct PCQM-Contact ogbg-molpcba ogbg-ppa
Metrics: MAE accuracy F1 average precision ROC AUC MRR
Baselines: GCN GIN GAT GatedGCN Graphormer SAT GPS Exphormer GRIT CRaWL NAGphormer Polynormer
Builds on: CRaWL Mamba GPS Polynormer BERT
Closest papers by meaning
- Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks (NeurIPS 2025 · similarity 0.91)
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.89)
- On Measuring Long-Range Interactions in Graph Neural Networks (ICML 2025 · similarity 0.89)
- Generative Graph Pattern Machine (NeurIPS 2025 · similarity 0.88)
- Random Search Neural Networks for Efficient and Expressive Graph Learning (NeurIPS 2025 · similarity 0.88)
- Recurrent Distance Filtering for Graph Representation Learning (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.