# Repelling Random Walks

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 7 Oct 2023.

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

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Random Walks: A Review of Algorithms and Applications](https://mlsanity.com/paper/2008.03639/) (2020)
- [Orthogonal Estimation of Wasserstein Distances](https://mlsanity.com/paper/1903.03784/) (2019)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)
- [Taming graph kernels with random features](https://mlsanity.com/paper/2305.00156/) (2023)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Quasi-Monte Carlo Graph Random Features](https://mlsanity.com/paper/2305.12470/) (2023)
- [Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections](https://mlsanity.com/paper/1304.1548/) (2013)
- [Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains](https://mlsanity.com/paper/2305.05097/) (2023)
- [Learning Manifold Implicitly via Explicit Heat-Kernel Learning](https://mlsanity.com/paper/2010.01761/) (2020)
- [Leveraging History for Faster Sampling of Online Social Networks](https://mlsanity.com/paper/1505.00079/) (2015)

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

- [Linear Transformer Topological Masking with Graph Random Features](https://mlsanity.com/paper/2410.03462/) (2024)
- [Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs](https://mlsanity.com/paper/2410.10368/) (2024)
- [Variance-Reducing Couplings for Random Features](https://mlsanity.com/paper/2405.16541/) (2024)
- [Computationally-efficient Graph Modeling with Refined Graph Random Features](https://mlsanity.com/paper/2510.07716/) (2025)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective](https://mlsanity.com/paper/2410.08389/) (2024)

## Abstract (arXiv)

We present a novel quasi-Monte Carlo mechanism to improve graph-based sampling, coined repelling random walks. By inducing correlations between the trajectories of an interacting ensemble such that their marginal transition probabilities are unmodified, we are able to explore the graph more efficiently, improving the concentration of statistical estimators whilst leaving them unbiased. The mechanism has a trivial drop-in implementation. We showcase the effectiveness of repelling random walks in a range of settings including estimation of graph kernels, the PageRank vector and graphlet concentrations. We provide detailed experimental evaluation and robust theoretical guarantees. To our knowledge, repelling random walks constitute the first rigorously studied quasi-Monte Carlo scheme correlating the directions of walkers on a graph, inviting new research in this exciting nascent domain.