# Efficient and Local Parallel Random Walks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 42 references that are in the map.
- First posted on arXiv 1 Dec 2021.

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

- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Spectral Clustering Oracles in Sublinear Time](https://mlsanity.com/paper/2101.05549/) (2021)
- [Distributed Random Walks](https://mlsanity.com/paper/1302.4544/) (2013)
- [Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank](https://mlsanity.com/paper/1507.08967/) (2015)
- [Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs](https://mlsanity.com/paper/1805.02974/) (2018)
- [Simulating Random Walks on Graphs in the Streaming Model](https://mlsanity.com/paper/1811.08205/) (2018)

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

- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)

## Abstract (arXiv)

Random walks are a fundamental primitive used in many machine learning algorithms with several applications in clustering and semi-supervised learning. Despite their relevance, the first efficient parallel algorithm to compute random walks has been introduced very recently (Lacki et al.). Unfortunately their method has a fundamental shortcoming: their algorithm is non-local in that it heavily relies on computing random walks out of all nodes in the input graph, even though in many practical applications one is interested in computing random walks only from a small subset of nodes in the graph. In this paper, we present a new algorithm that overcomes this limitation by building random walk efficiently and locally at the same time. We show that our technique is both memory and round efficient, and in particular yields an efficient parallel local clustering algorithm. Finally, we complement our theoretical analysis with experimental results showing that our algorithm is significantly more scalable than previous approaches.