# Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 39 references that are in the map.
- First posted on arXiv 15 Nov 2024.

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

- [Fair Correlation Clustering](https://mlsanity.com/paper/2002.02274/) (2020)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [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)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Scalable Community Detection via Parallel Correlation Clustering](https://mlsanity.com/paper/2108.01731/) (2021)
- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Almost 3-Approximate Correlation Clustering in Constant Rounds](https://mlsanity.com/paper/2205.03710/) (2022)
- [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)
- [Local correlation clustering](https://mlsanity.com/paper/1312.5105/) (2013)
- [Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time](https://mlsanity.com/paper/1909.03478/) (2019)
- [Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary](https://mlsanity.com/paper/2004.08432/) (2020)
- [Combinatorial Correlation Clustering](https://mlsanity.com/paper/2404.05433/) (2024)
- [Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time](https://mlsanity.com/paper/1909.03445/) (2019)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models](https://mlsanity.com/paper/2402.15668/) (2024)
- [A (3+varepsilon)-Approximate Correlation Clustering Algorithm in Dynamic Streams](https://mlsanity.com/paper/2205.07593/) (2022)
- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)

## Abstract (arXiv)

We study the dynamic correlation clustering problem with textitadaptive edge label flips. In correlation clustering, we are given a n-vertex complete graph whose edges are labeled either (+) or (-), and the goal is to minimize the total number of (+) edges between clusters and the number of (-) edges within clusters. We consider the dynamic setting with adversarial robustness, in which the textitadaptive adversary could flip the label of an edge based on the current output of the algorithm. Our main result is a randomized algorithm that always maintains an O(1)-approximation to the optimal correlation clustering with O(log2n) amortized update time. Prior to our work, no algorithm with O(1)-approximation and polylog(n) update time for the adversarially robust setting was known. We further validate our theoretical results with experiments on synthetic and real-world datasets with competitive empirical performances. Our main technical ingredient is an algorithm that maintains textitsparse-dense decomposition with polylog(n) update time, which could be of independent interest.