mlsanityData to 14 Oct 2026

Repelling Random Walks

arXiv 2310.04854 ↗First posted 7 Oct 2023stat.ML cs.LGcited by 6

Not on the map. Why?

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.

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

15 of 48 references.

References · 15

  1. 2020Rethinking Attention with Performerscited by 1,601
  2. 2016Orthogonal Random Featurescited by 91
  3. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  4. 2017The Unreasonable Effectiveness of Structured Random Orthogonal Embeddingscited by 45
  5. 2020Random Walks: A Review of Algorithms and Applicationscited by 38
  6. 2019Orthogonal Estimation of Wasserstein Distancescited by 32
  7. 2014Heat kernel based community detectioncited by 30
  8. 2023Taming graph kernels with random featurescited by 17
  9. 2016A General Framework for Estimating Graphlet Statistics via Random Walkcited by 10
  10. 2023Simplex Random Featurescited by 9
  11. 2023Quasi-Monte Carlo Graph Random Featurescited by 9
  12. 2013Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collectionscited by 8
3 more
  1. 2023Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chainscited by 8
  2. 2020Learning Manifold Implicitly via Explicit Heat-Kernel Learningcited by 7
  3. 2015Leveraging History for Faster Sampling of Online Social Networkscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 4; 2025: 1; 2026: 1.

6 papers.

  1. 2024Linear Transformer Topological Masking with Graph Random Featurescited by 7
  2. 2024Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphscited by 3
  3. 2024Variance-Reducing Couplings for Random Featurescited by 2
  4. 2025Computationally-efficient Graph Modeling with Refined Graph Random Featurescited by 2
  5. 2026Manifold Random Featurescited by 1
  6. 2024Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspectivecited by 0