Timezone: »
Correlation clustering is a central topic in unsupervised learning, with many applications in ML and data mining. In correlation clustering, one receives as input a signed graph and the goal is to partition it to minimize the number of disagreements. In this work we propose a massively parallel computation (MPC) algorithm for this problem that is considerably faster than prior work. In particular, our algorithm uses machines with memory sublinear in the number of nodes in the graph and returns a constant approximation while running only for a constant number of rounds. To the best of our knowledge, our algorithm is the first that can provably approximate a clustering problem using only a constant number of MPC rounds in the sublinear memory regime. We complement our analysis with an experimental scalability evaluation of our techniques.
Author Information
Vincent Cohen-Addad (Google)
Silvio Lattanzi (Google)
Slobodan Mitrović (MIT)
Ashkan Norouzi-Fard (Google)
Nikos Parotsidis (Google)
Jakub Tarnawski (Microsoft Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Oral: Correlation Clustering in Constant Many Parallel Rounds »
Fri. Jul 23rd 02:00 -- 02:20 AM Room
More from the Same Authors
-
2023 Poster: Fairness in Streaming Submodular Maximization over a Matroid Constraint »
Marwa El Halabi · Federico Fusco · Ashkan Norouzi-Fard · Jakab Tardos · Jakub Tarnawski -
2023 Poster: Speeding Up Bellman Ford via Minimum Violation Permutations »
Silvio Lattanzi · Ola Svensson · Sergei Vassilvitskii -
2023 Poster: Fully Dynamic Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2022 Oral: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Spotlight: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2022 Poster: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 Spotlight: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2021 Poster: Fairness and Bias in Online Selection »
Jose Correa · Andres Cristi · Paul Duetting · Ashkan Norouzi-Fard -
2021 Spotlight: Fairness and Bias in Online Selection »
Jose Correa · Andres Cristi · Paul Duetting · Ashkan Norouzi-Fard -
2019 Poster: A Better k-means++ Algorithm via Local Search »
Silvio Lattanzi · Christian Sohler -
2019 Oral: A Better k-means++ Algorithm via Local Search »
Silvio Lattanzi · Christian Sohler -
2019 Poster: Improved Parallel Algorithms for Density-Based Network Clustering »
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović -
2019 Poster: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Improved Parallel Algorithms for Density-Based Network Clustering »
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams »
Ashkan Norouzi-Fard · Jakub Tarnawski · Slobodan Mitrovic · Amir Zandieh · Aidasadat Mousavifar · Ola Svensson -
2018 Oral: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams »
Ashkan Norouzi-Fard · Jakub Tarnawski · Slobodan Mitrovic · Amir Zandieh · Aidasadat Mousavifar · Ola Svensson -
2017 Poster: Robust Submodular Maximization: A Non-Uniform Partitioning Approach »
Ilija Bogunovic · Slobodan Mitrovic · Jonathan Scarlett · Volkan Cevher -
2017 Talk: Robust Submodular Maximization: A Non-Uniform Partitioning Approach »
Ilija Bogunovic · Slobodan Mitrovic · Jonathan Scarlett · Volkan Cevher -
2017 Poster: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii -
2017 Talk: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii