# Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchies

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 23 references that are in the map.
- First posted on arXiv 1 Sep 2025.

## Builds on (most cited first, 18 of 18)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [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)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunities](https://mlsanity.com/paper/2204.07321/) (2022)
- [Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing](https://mlsanity.com/paper/2102.08786/) (2021)
- [Learning Long Range Dependencies on Graphs via Random Walks](https://mlsanity.com/paper/2406.03386/) (2024)
- [Agent-based Graph Neural Networks](https://mlsanity.com/paper/2206.11010/) (2022)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Hierarchical graph neural nets can capture long-range interactions](https://mlsanity.com/paper/2107.07432/) (2021)
- [Non-convolutional Graph Neural Networks](https://mlsanity.com/paper/2408.00165/) (2024)
- [Next Level Message-Passing with Hierarchical Support Graphs](https://mlsanity.com/paper/2406.15852/) (2024)
- [Flood and Echo Net: Algorithmically Aligned GNNs that Generalize](https://mlsanity.com/paper/2310.06970/) (2023)
- [HiGNN: Hierarchical Informative Graph Neural Networks for Molecular Property Prediction Equipped with Feature-Wise Attention](https://mlsanity.com/paper/2208.13994/) (2022)

## Abstract (arXiv)

Message-passing architectures struggle to sufficiently model long-range dependencies in node and graph prediction tasks. We propose a novel approach exploiting hierarchical graph structures and adaptive random walks to address this challenge. Our method introduces learnable transition probabilities that decide whether the walk should prefer the original graph or travel across hierarchical shortcuts. On a synthetic long-range task, we demonstrate that our approach can exceed the theoretical bound that constrains traditional approaches operating solely on the original topology. Specifically, walks that prefer the hierarchy achieve the same performance as longer walks on the original graph. These preliminary findings open a promising direction for efficiently processing large graphs while effectively capturing long-range dependencies.