# Dynamic Correlation Clustering in Sublinear Update Time

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 13 Jun 2024.

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

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Correlation Clustering in Constant Many Parallel Rounds](https://mlsanity.com/paper/2106.08448/) (2021)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [Consistent k-Clustering for General Metrics](https://mlsanity.com/paper/2011.06888/) (2020)
- [Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions](https://mlsanity.com/paper/2109.14528/) (2021)
- [Almost 3-Approximate Correlation Clustering in Constant Rounds](https://mlsanity.com/paper/2205.03710/) (2022)
- [Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries](https://mlsanity.com/paper/2303.11843/) (2023)
- [Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering](https://mlsanity.com/paper/2309.17243/) (2023)
- [Understanding the Cluster LP for Correlation Clustering](https://mlsanity.com/paper/2404.17509/) (2024)
- [Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time](https://mlsanity.com/paper/1909.03478/) (2019)
- [Combinatorial Correlation Clustering](https://mlsanity.com/paper/2404.05433/) (2024)

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

- [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)

## Abstract (arXiv)

We study the classic problem of correlation clustering in dynamic node streams. In this setting, nodes are either added or randomly deleted over time, and each node pair is connected by a positive or negative edge. The objective is to continuously find a partition which minimizes the sum of positive edges crossing clusters and negative edges within clusters. We present an algorithm that maintains an O(1)-approximation with O(polylog n) amortized update time. Prior to our work, Behnezhad, Charikar, Ma, and L. Tan achieved a 5-approximation with O(1) expected update time in edge streams which translates in node streams to an O(D)-update time where D is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data.