Dynamic Correlation Clustering in Sublinear Update Time

Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:9230-9274, 2024.

Abstract

We study the classic problem of correlation clustering in dynamic vertex streams. In this setting, vertices are either added or randomly deleted over time, and each vertex 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(\text{polylog} n)$ amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in vertex 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-cohen-addad24d, title = {Dynamic Correlation Clustering in Sublinear Update Time}, author = {Cohen-Addad, Vincent and Lattanzi, Silvio and Maggiori, Andreas and Parotsidis, Nikos}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {9230--9274}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/cohen-addad24d/cohen-addad24d.pdf}, url = {https://proceedings.mlr.press/v235/cohen-addad24d.html}, abstract = {We study the classic problem of correlation clustering in dynamic vertex streams. In this setting, vertices are either added or randomly deleted over time, and each vertex 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(\text{polylog} n)$ amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in vertex 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.} }
Endnote
%0 Conference Paper %T Dynamic Correlation Clustering in Sublinear Update Time %A Vincent Cohen-Addad %A Silvio Lattanzi %A Andreas Maggiori %A Nikos Parotsidis %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-cohen-addad24d %I PMLR %P 9230--9274 %U https://proceedings.mlr.press/v235/cohen-addad24d.html %V 235 %X We study the classic problem of correlation clustering in dynamic vertex streams. In this setting, vertices are either added or randomly deleted over time, and each vertex 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(\text{polylog} n)$ amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in vertex 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.
APA
Cohen-Addad, V., Lattanzi, S., Maggiori, A. & Parotsidis, N.. (2024). Dynamic Correlation Clustering in Sublinear Update Time. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:9230-9274 Available from https://proceedings.mlr.press/v235/cohen-addad24d.html.

Related Material