Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering

Jan-Hendrik Lange, Andreas Karrenbauer, Bjoern Andres
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2892-2901, 2018.

Abstract

Weighted correlation clustering is hard to solve and hard to approximate for general graphs. Its applications in network analysis and computer vision call for efficient algorithms. To this end, we make three contributions: We establish partial optimality conditions that can be checked efficiently, and doing so recursively solves the problem for series-parallel graphs to optimality, in linear time. We exploit the packing dual of the problem to compute a heuristic, but non-trivial lower bound faster than that of a canonical linear program relaxation. We introduce a re-weighting with the dual solution by which efficient local search algorithms converge to better feasible solutions. The effectiveness of our methods is demonstrated empirically on a number of benchmark instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-lange18a, title = {Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering}, author = {Lange, Jan-Hendrik and Karrenbauer, Andreas and Andres, Bjoern}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2892--2901}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/lange18a/lange18a.pdf}, url = {https://proceedings.mlr.press/v80/lange18a.html}, abstract = {Weighted correlation clustering is hard to solve and hard to approximate for general graphs. Its applications in network analysis and computer vision call for efficient algorithms. To this end, we make three contributions: We establish partial optimality conditions that can be checked efficiently, and doing so recursively solves the problem for series-parallel graphs to optimality, in linear time. We exploit the packing dual of the problem to compute a heuristic, but non-trivial lower bound faster than that of a canonical linear program relaxation. We introduce a re-weighting with the dual solution by which efficient local search algorithms converge to better feasible solutions. The effectiveness of our methods is demonstrated empirically on a number of benchmark instances.} }
Endnote
%0 Conference Paper %T Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering %A Jan-Hendrik Lange %A Andreas Karrenbauer %A Bjoern Andres %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-lange18a %I PMLR %P 2892--2901 %U https://proceedings.mlr.press/v80/lange18a.html %V 80 %X Weighted correlation clustering is hard to solve and hard to approximate for general graphs. Its applications in network analysis and computer vision call for efficient algorithms. To this end, we make three contributions: We establish partial optimality conditions that can be checked efficiently, and doing so recursively solves the problem for series-parallel graphs to optimality, in linear time. We exploit the packing dual of the problem to compute a heuristic, but non-trivial lower bound faster than that of a canonical linear program relaxation. We introduce a re-weighting with the dual solution by which efficient local search algorithms converge to better feasible solutions. The effectiveness of our methods is demonstrated empirically on a number of benchmark instances.
APA
Lange, J., Karrenbauer, A. & Andres, B.. (2018). Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2892-2901 Available from https://proceedings.mlr.press/v80/lange18a.html.

Related Material