Analysis and Optimization of Graph Decompositions by Lifted Multicuts

Andrea Horňáková, Jan-Hendrik Lange, Bjoern Andres
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1539-1548, 2017.

Abstract

We study the set of all decompositions (clusterings) of a graph through its characterization as a set of lifted multicuts. This leads us to practically relevant insights related to the definition of classes of decompositions by must-join and must-cut constraints and related to the comparison of clusterings by metrics. To find optimal decompositions defined by minimum cost lifted multicuts, we establish some properties of some facets of lifted multicut polytopes, define efficient separation procedures and apply these in a branch-and-cut algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-hornakova17a, title = {Analysis and Optimization of Graph Decompositions by Lifted Multicuts}, author = {Andrea Hor{\v{n}}{\'a}kov{\'a} and Jan-Hendrik Lange and Bjoern Andres}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1539--1548}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/hornakova17a/hornakova17a.pdf}, url = {https://proceedings.mlr.press/v70/hornakova17a.html}, abstract = {We study the set of all decompositions (clusterings) of a graph through its characterization as a set of lifted multicuts. This leads us to practically relevant insights related to the definition of classes of decompositions by must-join and must-cut constraints and related to the comparison of clusterings by metrics. To find optimal decompositions defined by minimum cost lifted multicuts, we establish some properties of some facets of lifted multicut polytopes, define efficient separation procedures and apply these in a branch-and-cut algorithm.} }
Endnote
%0 Conference Paper %T Analysis and Optimization of Graph Decompositions by Lifted Multicuts %A Andrea Horňáková %A Jan-Hendrik Lange %A Bjoern Andres %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-hornakova17a %I PMLR %P 1539--1548 %U https://proceedings.mlr.press/v70/hornakova17a.html %V 70 %X We study the set of all decompositions (clusterings) of a graph through its characterization as a set of lifted multicuts. This leads us to practically relevant insights related to the definition of classes of decompositions by must-join and must-cut constraints and related to the comparison of clusterings by metrics. To find optimal decompositions defined by minimum cost lifted multicuts, we establish some properties of some facets of lifted multicut polytopes, define efficient separation procedures and apply these in a branch-and-cut algorithm.
APA
Horňáková, A., Lange, J. & Andres, B.. (2017). Analysis and Optimization of Graph Decompositions by Lifted Multicuts. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1539-1548 Available from https://proceedings.mlr.press/v70/hornakova17a.html.

Related Material