Atoms and Pivot Based Correlation Clustering

Correlation clustering seeks a partitioning of the vertices of a graph that minimizes the number of disagreements: edges between different clusters and non-edges within the same cluster. The classic *pivot-based correlation clustering* algorithm of Ailon, Charikar, and Chawla [JACM'08] achieves a factor-$3$ approximation. However, known worst-case examples attaining this bound rely on highly structured instances with exceptionally strong clusters, such as complete graphs minus a matching. In this work, we show that such worst-case behavior is inherently tied to these highly clique-like substructures. Building on the notion of *atoms* introduced by Cohen-Addad, Lattanzi, Mitrovic, Norouzi-Fard, Parotsidis, and Tarnawski [FOCS'23] — subsets of vertices that cannot be separated in any optimal clustering — we prove that the approximation ratio of $3$ can only be realized when the pivot algorithm makes errors on such atoms. Motivated by this insight, we propose a modified pivot algorithm that removes atoms prior to each pivot step. We prove that this yields an improved approximation ratio of $2.9995$ in expectation. Additionally, we evaluate our algorithm on synthetic datasets with varying amount of noise, demonstrating consistent empirical improvements over both the classic pivot algorithm and existing methods for identifying atoms.