Sparse-pivot: Dynamic correlation clustering for node insertions

Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:12256-12279, 2025.

Abstract

We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $\log^{O(1)}(n)$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al. in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-dalirrooyfard25a, title = {Sparse-pivot: Dynamic correlation clustering for node insertions}, author = {Dalirrooyfard, Mina and Makarychev, Konstantin and Mitrovi\'{c}, Slobodan}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {12256--12279}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/dalirrooyfard25a/dalirrooyfard25a.pdf}, url = {https://proceedings.mlr.press/v267/dalirrooyfard25a.html}, abstract = {We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $\log^{O(1)}(n)$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al. in practice.} }
Endnote
%0 Conference Paper %T Sparse-pivot: Dynamic correlation clustering for node insertions %A Mina Dalirrooyfard %A Konstantin Makarychev %A Slobodan Mitrović %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-dalirrooyfard25a %I PMLR %P 12256--12279 %U https://proceedings.mlr.press/v267/dalirrooyfard25a.html %V 267 %X We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $\log^{O(1)}(n)$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al. in practice.
APA
Dalirrooyfard, M., Makarychev, K. & Mitrović, S.. (2025). Sparse-pivot: Dynamic correlation clustering for node insertions. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:12256-12279 Available from https://proceedings.mlr.press/v267/dalirrooyfard25a.html.

Related Material