Timezone: »
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.
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
-
2022 : Scalable and Improved Algorithms for Individually Fair Clustering »
Mohammadhossein Bateni · Vincent Cohen-Addad · Alessandro Epasto · Silvio Lattanzi -
2023 Poster: Multi-Swap k-Means++ »
Lorenzo Beretta · Vincent Cohen-Addad · Silvio Lattanzi · Nikos Parotsidis -
2023 Poster: Fully Dynamic $k$-Clustering in $\tilde O(k)$ Update Time »
Sayan Bhattacharya · Martin Costa · Silvio Lattanzi · Nikos Parotsidis -
2022 Poster: Active Learning of Classifiers with Label and Seed Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice · Maximilian Thiessen -
2022 Poster: Near-Optimal Correlation Clustering with Privacy »
Vincent Cohen-Addad · Chenglin Fan · Silvio Lattanzi · Slobodan Mitrovic · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2022 Poster: Efficient and Stable Fully Dynamic Facility Location »
Sayan Bhattacharya · Silvio Lattanzi · Nikos Parotsidis -
2021 Poster: Online Facility Location with Multiple Advice »
Matteo Almanza · Flavio Chierichetti · Silvio Lattanzi · Alessandro Panconesi · Giuseppe Re -
2021 Poster: Robust Online Correlation Clustering »
Silvio Lattanzi · Benjamin Moseley · Sergei Vassilvitskii · Yuyan Wang · Rudy Zhou -
2021 Poster: Parallel and Efficient Hierarchical k-Median Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2021 Poster: Streaming Belief Propagation for Community Detection »
Yuchen Wu · Jakab Tardos · Mohammadhossein Bateni · André Linhares · Filipe Miguel Goncalves de Almeida · Andrea Montanari · Ashkan Norouzi-Fard -
2021 Poster: On Margin-Based Cluster Recovery with Oracle Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Poster: Fully Dynamic Algorithm for Constrained Submodular Optimization »
Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Jakub Tarnawski · Morteza Zadimoghaddam -
2020 Oral: Fully Dynamic Algorithm for Constrained Submodular Optimization »
Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Jakub Tarnawski · Morteza Zadimoghaddam -
2020 Poster: Sliding Window Algorithms for k-Clustering Problems »
Michele Borassi · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam -
2020 Poster: Fast and Accurate $k$-means++ via Rejection Sampling »
Vincent Cohen-Addad · Silvio Lattanzi · Ashkan Norouzi-Fard · Christian Sohler · Ola Svensson -
2020 Poster: Online MAP Inference of Determinantal Point Processes »
Aditya Bhaskara · Amin Karbasi · Silvio Lattanzi · Morteza Zadimoghaddam -
2020 Poster: Exact Recovery of Mangled Clusters with Same-Cluster Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Poster: Fairness in Streaming Submodular Maximization: Algorithms and Hardness »
Marwa El Halabi · Slobodan Mitrović · Ashkan Norouzi-Fard · Jakab Tardos · Jakub Tarnawski -
2020 Oral: Exact Recovery of Mangled Clusters with Same-Cluster Queries »
Marco Bressan · Nicolò Cesa-Bianchi · Silvio Lattanzi · Andrea Paudice -
2020 Session: Orals & Spotlights Track 05: Clustering/Ranking »
Silvio Lattanzi · Katerina Fragkiadaki -
2019 : Coffee Break & Poster Session 1 »
Yan Zhang · Jonathon Hare · Adam Prugel-Bennett · Po Leung · Patrick Flaherty · Pitchaya Wiratchotisatian · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam · Theja Tulabandhula · Fabian Fuchs · Adam Kosiorek · Ingmar Posner · William Hang · Anna Goldie · Sujith Ravi · Azalia Mirhoseini · Yuwen Xiong · Mengye Ren · Renjie Liao · Raquel Urtasun · Haici Zhang · Michele Borassi · Shengda Luo · Andrew Trapp · Geoffroy Dubourg-Felonneau · Yasmeen Kussad · Christopher Bender · Manzil Zaheer · Junier Oliva · Michał Stypułkowski · Maciej Zieba · Austin Dill · Chun-Liang Li · Songwei Ge · Eunsu Kang · Oiwi Parker Jones · Kelvin Ka Wing Wong · Joshua Payne · Yang Li · Azade Nazi · Erkut Erdem · Aykut Erdem · Kevin O'Connor · Juan J Garcia · Maciej Zamorski · Jan Chorowski · Deeksha Sinha · Harry Clifford · John W Cassidy -
2019 Poster: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Spotlight: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2018 Poster: Mallows Models for Top-k Lists »
Flavio Chierichetti · Anirban Dasgupta · Shahrzad Haddadan · Ravi Kumar · Silvio Lattanzi -
2017 Poster: Affinity Clustering: Hierarchical Clustering at Scale »
Mohammadhossein Bateni · Soheil Behnezhad · Mahsa Derakhshan · MohammadTaghi Hajiaghayi · Raimondas Kiveris · Silvio Lattanzi · Vahab Mirrokni -
2016 Poster: Community Detection on Evolving Graphs »
Stefano Leonardi · Aris Anagnostopoulos · Jakub Łącki · Silvio Lattanzi · Mohammad Mahdian -
2014 Poster: Distributed Balanced Clustering via Mapping Coresets »
Mohammadhossein Bateni · Aditya Bhaskara · Silvio Lattanzi · Vahab Mirrokni