Timezone: »

 
Poster
Efficient and Local Parallel Random Walks
Michael Kapralov · Silvio Lattanzi · Navid Nouri · Jakab Tardos

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @
in Poster Session 5 »

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 (Łącki 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 walks 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.

Keywords: Machine Learning · Graph Learning · Clustering · Semi-Supervised Learning

Author Information

Michael Kapralov (EPFL)
Silvio Lattanzi (Google Research)
Navid Nouri (Swiss Federal Institute of Technology Lausanne)
Jakab Tardos (EPFL)

More from the Same Authors