Fast Combinatorial Algorithms for Min Max Correlation Clustering

Sami Davies, Benjamin Moseley, Heather Newman
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:7205-7230, 2023.

Abstract

We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the first purely combinatorial approximation algorithms for this problem. We construct a novel semi-metric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The paper demonstrates empirically that, compared to prior work, our algorithms sacrifice little in the objective quality to obtain significantly better run-time. Moreover, our algorithms scale to larger networks that are effectively intractable for known algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-davies23a, title = {Fast Combinatorial Algorithms for Min Max Correlation Clustering}, author = {Davies, Sami and Moseley, Benjamin and Newman, Heather}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {7205--7230}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/davies23a/davies23a.pdf}, url = {https://proceedings.mlr.press/v202/davies23a.html}, abstract = {We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the first purely combinatorial approximation algorithms for this problem. We construct a novel semi-metric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The paper demonstrates empirically that, compared to prior work, our algorithms sacrifice little in the objective quality to obtain significantly better run-time. Moreover, our algorithms scale to larger networks that are effectively intractable for known algorithms.} }
Endnote
%0 Conference Paper %T Fast Combinatorial Algorithms for Min Max Correlation Clustering %A Sami Davies %A Benjamin Moseley %A Heather Newman %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-davies23a %I PMLR %P 7205--7230 %U https://proceedings.mlr.press/v202/davies23a.html %V 202 %X We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the first purely combinatorial approximation algorithms for this problem. We construct a novel semi-metric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The paper demonstrates empirically that, compared to prior work, our algorithms sacrifice little in the objective quality to obtain significantly better run-time. Moreover, our algorithms scale to larger networks that are effectively intractable for known algorithms.
APA
Davies, S., Moseley, B. & Newman, H.. (2023). Fast Combinatorial Algorithms for Min Max Correlation Clustering. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:7205-7230 Available from https://proceedings.mlr.press/v202/davies23a.html.

Related Material