Repelling Random Walks
Isaac Reid Eli Berger Krzysztof Choromanski Adrian Weller
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.