# Correlation Clustering in Constant Many Parallel Rounds

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 15 Jun 2021.

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

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Communication Steps for Parallel Query Processing](https://mlsanity.com/paper/1306.5972/) (2013)
- [Correlation Clustering in Data Streams](https://mlsanity.com/paper/1812.02023/) (2018)
- [Massively Parallel Correlation Clustering in Bounded Arboricity Graphs](https://mlsanity.com/paper/2102.11660/) (2021)
- [Round Compression for Parallel Matching Algorithms](https://mlsanity.com/paper/1707.03478/) (2017)

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

- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Better Private Algorithms for Correlation Clustering](https://mlsanity.com/paper/2202.10747/) (2022)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [Online Correlation Clustering for Dynamic Complete Signed Graphs](https://mlsanity.com/paper/2211.07000/) (2022)
- [Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach](https://mlsanity.com/paper/2301.00384/) (2023)
- [Learning-Augmented Streaming Algorithms for Correlation Clustering](https://mlsanity.com/paper/2510.10705/) (2025)
- [Four Algorithms for Correlation Clustering: A Survey](https://mlsanity.com/paper/2208.12636/) (2022)
- [Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better](https://mlsanity.com/paper/2404.16131/) (2024)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)
- [On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling](https://mlsanity.com/paper/2602.13684/) (2026)
- [Inductive Correlation Clustering with Graph Neural Networks](https://mlsanity.com/paper/2608.27153/) (2026)

## Abstract (arXiv)

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 on graphs using only a constant number of MPC rounds in the sublinear memory regime. We complement our analysis with an experimental analysis of our techniques.