# Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 66 references that are in the map.
- First posted on arXiv 29 Sep 2021.

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

- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Correlation Clustering in Data Streams](https://mlsanity.com/paper/1812.02023/) (2018)
- [Correlation Clustering with Adaptive Similarity Queries](https://mlsanity.com/paper/1905.11902/) (2019)
- [Query-Efficient Correlation Clustering](https://mlsanity.com/paper/2002.11557/) (2020)
- [Local Correlation Clustering with Asymmetric Classification Errors](https://mlsanity.com/paper/2108.05697/) (2021)
- [Local correlation clustering](https://mlsanity.com/paper/1312.5105/) (2013)
- [Min-Max Correlation Clustering via MultiCut](https://mlsanity.com/paper/1907.00117/) (2019)
- [Massively Parallel Correlation Clustering in Bounded Arboricity Graphs](https://mlsanity.com/paper/2102.11660/) (2021)
- [Tight Analysis of Randomized Greedy MIS](https://mlsanity.com/paper/1707.05124/) (2017)
- [Independent Sets in Vertex-Arrival Streams](https://mlsanity.com/paper/1807.08331/) (2018)
- [Efficient Randomized Distributed Coloring in CONGEST](https://mlsanity.com/paper/2012.14169/) (2020)
- [An Optimal Distributed (Delta+1)-Coloring Algorithm?](https://mlsanity.com/paper/1711.01361/) (2017)
- [When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time](https://mlsanity.com/paper/2006.07628/) (2020)
- [Palette Sparsification Beyond (Delta+1) Vertex Coloring](https://mlsanity.com/paper/2006.10456/) (2020)

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

- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (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)
- [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)
- [On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling](https://mlsanity.com/paper/2602.13684/) (2026)

## Abstract (arXiv)

We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this problem. In particular, we obtain the following algorithms for n-vertex (+/-)-labeled graphs G: -- A sublinear-time algorithm that with high probability returns a constant approximation clustering of G in O(nlog2n) time assuming access to the adjacency list of the (+)-labeled edges of G (this is almost quadratically faster than even reading the input once). Previously, no sublinear-time algorithm was known for this problem with any multiplicative approximation guarantee. -- A semi-streaming algorithm that with high probability returns a constant approximation clustering of G in O(nlogn) space and a single pass over the edges of the graph G (this memory is almost quadratically smaller than input size). Previously, no single-pass algorithm with o(n2) space was known for this problem with any approximation guarantee. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions that are used extensively in the graph coloring literature. To our knowledge, this connection is the first application of these decompositions beyond graph coloring, and in particular for the correlation clustering problem, and can be of independent interest.