Partial Optimality in Cubic Correlation Clustering

David Stein, Silvia Di Gregorio, Bjoern Andres
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:32598-32617, 2023.

Abstract

The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-stein23a, title = {Partial Optimality in Cubic Correlation Clustering}, author = {Stein, David and Di Gregorio, Silvia and Andres, Bjoern}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {32598--32617}, 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/stein23a/stein23a.pdf}, url = {https://proceedings.mlr.press/v202/stein23a.html}, abstract = {The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.} }
Endnote
%0 Conference Paper %T Partial Optimality in Cubic Correlation Clustering %A David Stein %A Silvia Di Gregorio %A Bjoern Andres %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-stein23a %I PMLR %P 32598--32617 %U https://proceedings.mlr.press/v202/stein23a.html %V 202 %X The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.
APA
Stein, D., Di Gregorio, S. & Andres, B.. (2023). Partial Optimality in Cubic Correlation Clustering. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:32598-32617 Available from https://proceedings.mlr.press/v202/stein23a.html.

Related Material