Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time

Abstract

We study the dynamic correlation clustering problem with adaptive 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 adaptive 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(^2n) 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 sparse-dense decomposition with polylog(n) update time, which could be of independent interest.

Tasks

Reproductions