Dynamic Correlation Clustering in Sublinear Update Time

2024/06/13 by Vincent Cohen-Addad, Silvio Lattanzi, Cohen-Addad, Vincent +5 · 2 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2406.09137

openalex publication_date 2024/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Fully Dynamic Algorithms for Chamfer Distance
• 1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP

Related

• Correlation Clustering in Data Streams
• Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
• Correlation Clustering Beyond the Pivot Algorithm
• Static to Dynamic Correlation Clustering
• SPARSE-PIVOT: Dynamic correlation clustering for node insertions