Research map / Graph learning / GNN architectures
Revisiting Random Walks for Learning on Graphs
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.
Formalizes random walk neural networks (RWNNs), showing that anonymized random walk records give probabilistic isomorphism invariance and universality, and uses DeBERTa and Llama 3 readers on graph separation and arXiv transductive classification.
Problem
Lacking principled understanding of random walk neural networks on graphs: how to ensure isomorphism invariance, what their expressive power is, and how over-smoothing and over-squashing manifest.
Approach
Decouple random walks, recording functions, and reader networks; achieve probabilistic invariance by using invariant walks and anonymized (optionally named-neighbor) recordings so any reader, including a language model reading plain-text records, can be used without invariance constraints.
Key results
- RWNN-DeBERTa reaches 100% accuracy on CSL, SR16, and SR25 isomorphism learning, the first RWNN to solve SR25 where 3-WL fails.
- RWNN-Llama3-70b with validation labels in context reaches 74.85% accuracy on ogbn-arxiv, competitive with MPNNs such as GCN (71.74%) and GAT (73.91%) and above GPT-3.5 zero-shot (73.50%).
- On the Clique over-smoothing and Barbell over-squashing tasks, RWNN-transformer attains MSE 0.023 and 0.007 at l=1000, the best among compared methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RWNN-transformer instead of BuNN | vertex regression on Clique · Clique | test MSE: 0.03 ± 0.01 -> 0.023 ± 0.006 | No clear effect |
| use RWNN-transformer instead of BuNN | vertex regression on Barbell · Barbell | test MSE: 0.01 ± 0.07 -> 0.007 ± 0.001 | Helped |
| use RWNN-DeBERTa | graph isomorphism classification · SR25 | accuracy: 100.0% -> 100.0% | No clear effect |
| use RWNN-Llama3-70b with labeled examples in the record | transductive classification · ogbn-arxiv | accuracy: 74.26% -> 74.85% | Helped |
| fine-tune the Llama3-8b reader with QLoRA (ablation) | RWNN-Llama3-8b · ogbn-arxiv | accuracy: 73.17% -> 74.95% | Helped |
| increase walk length from l = 100 to l = 1000 (ablation) | RWNN-transformer · Barbell | test MSE: 0.297 ± 0.050 -> 0.007 ± 0.001 | Helped |
| use uniform walks and omit anonymization from the walk record (ablation) | RWNN-transformer · Barbell, l = 100 | test MSE: 0.297 ± 0.050 -> 0.388 ± 0.048 | Hurt |
| use a transformer reader rather than an MLP reader (ablation) | RWNN · Barbell, l = 1000 | test MSE: 0.015 ± 0.005 -> 0.007 ± 0.001 | Helped |
| use a transformer reader rather than an MLP reader (ablation) | RWNN · Clique, l = 1000 | test MSE: 0.028 ± 0.026 -> 0.023 ± 0.006 | No clear effect |
| fine-tune DeBERTa rather than use random initialization (ablation) | RWNN-DeBERTa · CSL and SR16 | training convergence | Helped |
| add recording of the starting vertex feature at each step (ablation) | RWNN-transformer · Clique and Barbell | training | Helped |
| use anonymization plus named neighbors instead of anonymization alone (ablation) | RWNN graph recording · graph-level tasks | required walk length for universality: C_E(G)/δ -> C_V(G)/δ | Helped |
Surprising findings
- Language pre-training matters: randomly initialized DeBERTa converges very slowly on CSL and fails to converge on SR16.
- A training-free Llama 3-8b RWNN with 40 labeled shots beats the one-shot baselines (73.17% vs 52.81%) even though it observes fewer vertices on average.
Limitations
- Over-squashing manifests as probabilistic under-reaching, so long walks are needed for bottleneck graphs such as Barbell.
- Inputs were truncated to 512 tokens due to memory constraints for DeBERTa.
- Fine-tuned RWNN-Llama3-8b underperforms on Amazon Ratings relative to other methods on some settings, and CRaWl runs took over 3 days per run.
Experimental setup
Datasets: CSL SR16 SR25 Clique Barbell ogbn-arxiv Cora Citeseer Amazon Ratings
Benchmarks: CSL SR16 SR25 Clique Barbell ogbn-arxiv Cora Citeseer Amazon Ratings
Metrics: accuracy mean squared error cover time
Baselines: GIN PPGN GIN-AK+ PPGN-AK+ GIN+ELENE RW-AgentNet AgentNet CRaWl GCN GAT SAGE NSD
Builds on: DeepWalk node2vec CRaWl AWE minimum degree local rule walks
Closest papers by meaning
- Random Search Neural Networks for Efficient and Expressive Graph Learning (NeurIPS 2025 · similarity 0.92)
- Learning Long Range Dependencies on Graphs via Random Walks (ICLR 2025 · similarity 0.89)
- Non-convolutional graph neural networks. (NeurIPS 2024 · similarity 0.89)
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- Towards Scalable and Deep Graph Neural Networks via Noise Masking (AAAI 2025 · similarity 0.87)
- Towards Understanding Transformers in Learning Random Walks (NeurIPS 2025 · similarity 0.87)
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.