Research map / Graph learning / Graph algorithms and clustering
Repelling 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.
Introduces repelling random walks, a quasi-Monte Carlo scheme where walkers at the same node sample distinct neighbours without replacement, leaving marginal transition probabilities unchanged, and shows variance reductions for graph kernel, PageRank and graphlet estimators.
Problem
Independent random walkers on graphs mix poorly, so Monte Carlo estimators built from them (graph kernels, PageRank, graphlet concentrations) have high variance; existing variance-reduction methods change marginal walk probabilities and so cannot be used for non-asymptotic unbiased estimators.
Approach
Correlate an ensemble of walkers so that walkers co-located at a node are split into blocks of size equal to the node degree and assigned to distinct neighbours without replacement; each walker's marginal transition probabilities are unchanged, so estimators stay unbiased while their concentration improves.
Key results
- For the PageRank estimator with 2 walkers, repelling walks reduce L2 error relative to i.i.d. on all 8 graphs tested (e.g., karate 0.0124 to 0.0115).
- On the torus mesh (N=4350), combining antithetic termination and repelling walks reduces kernel-regression angular error from 0.000506 (GRFs) to 0.000181 (q-r-GRFs), nearly a factor of 3.
- With m=16 walkers the kernel estimation error is often halved relative to i.i.d. GRFs; theory proves variance reduction for the transient repelling scheme on trees and 2D grids in the small-weight limit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use repelling random walks instead of i.i.d. walks for GRF kernel regression | GRFs · cylinder | angular error (1-cos θ): 0.0650(7) -> 0.0466(3) | Helped |
| Use repelling random walks instead of i.i.d. walks for GRF kernel regression | GRFs · teapot | angular error (1-cos θ): 0.0331(2) -> 0.0224(1) | Helped |
| Use repelling random walks instead of i.i.d. walks for GRF kernel regression | GRFs · idler-riser | angular error (1-cos θ): 0.0528(3) -> 0.0408(2) | Helped |
| Use repelling random walks instead of i.i.d. walks for GRF kernel regression | GRFs · busted | angular error (1-cos θ): 0.00463(2) -> 0.003833(6) | Helped |
| Use repelling random walks instead of i.i.d. walks for GRF kernel regression | GRFs · torus | angular error (1-cos θ): 0.000506(1) -> 0.000180(1) | Helped |
| Add antithetic termination to repelling random walks (ablation) | q-r-GRFs · cylinder | angular error (1-cos θ): 0.0466(3) -> 0.0459(2) | Helped |
| Add antithetic termination to repelling random walks (ablation) | q-r-GRFs · teapot | angular error (1-cos θ): 0.0224(1) -> 0.0215(1) | Helped |
| Add antithetic termination to repelling random walks (ablation) | q-r-GRFs · idler-riser | angular error (1-cos θ): 0.0408(2) -> 0.0408(2) | No clear effect |
| Add antithetic termination to repelling random walks (ablation) | q-r-GRFs · busted | angular error (1-cos θ): 0.003833(6) -> 0.003817(6) | Helped |
| Add antithetic termination to repelling random walks (ablation) | q-r-GRFs · torus | angular error (1-cos θ): 0.000180(1) -> 0.000181(1) | No clear effect |
| Use repelling random walks instead of i.i.d. walks | PageRank estimation · Small ER | PageRank L2 error: 0.0208(2) -> 0.0196(2) | Helped |
| Use repelling random walks instead of i.i.d. walks | PageRank estimation · Larger ER | PageRank L2 error: 0.00420(2) -> 0.00406(2) | Helped |
Surprising findings
- Theory shows the PageRank estimator variance is reduced by transient repulsion on any graph, not only special topologies.
Limitations
- Kernel variance-reduction proof only covers transient repelling walks, trees and 2D grids, small-weight limit, and equal edge weights.
- No rigorous theory for graphlet concentration estimators; the study is empirical.
- Theory for general graphs (kernel case) remains an open problem.
Experimental setup
Datasets: karate dolphins football eurosis polbooks triangular mesh graphs (cylinder, teapot, idler-riser, busted, torus) Erdos-Renyi synthetic graphs binary tree d-regular graph
Benchmarks: relative Frobenius norm of 2-regularised Laplacian kernel estimates angular error on node normal prediction (kernel regression on triangular meshes) PageRank L2 error graphlet concentration fractional error / MSE
Metrics: relative Frobenius norm 1-cos theta angular error L2 norm error mean squared error variance
Baselines: i.i.d. graph random features (GRFs) antithetic termination (q-a-GRFs) i.i.d. random walks for PageRank i.i.d. random walks for graphlet concentration
Builds on: graph random features antithetic termination non-backtracking random walks orthogonal Monte Carlo
Closest papers by meaning
- Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs (ICML 2025 · similarity 0.89)
- Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.86)
- NETS: A Non-equilibrium Transport Sampler (ICML 2025 · similarity 0.84)
- Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.84)
- Hypergraph Generation via Structured Stochastic Diffusion (NeurIPS 2026 · similarity 0.84)
- Revisiting Random Walks for Learning on Graphs (ICLR 2025 · similarity 0.84)
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.