Dynamic Correlation Clustering in Sublinear Update Time

Autor:	Cohen-Addad, Vincent, Lattanzi, Silvio, Maggiori, Andreas, Parotsidis, Nikos
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Machine Learning
Druh dokumentu:	Working Paper
Popis:	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. Comment: ICML'24 (spotlight)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2406.09137 Zobrazit plný text záznamu View this record from Arxiv