Titel:
Multicut Optimization Guarantees & Geometry of Lifted Multicuts
Beteiligte:
Lange, Jan-Hendrik
[VerfasserIn]
Erschienen:
Saarländische Universitäts- und Landesbibliothek, 2020
Sprache:
Englisch
DOI:
https://doi.org/10.22028/D291-31813
Entstehung:
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Clustering of graph structured data is an important task across many areas of modern data science such as image analysis and machine learning. A particular model for partitioning graphs purely based on similarities and dissimilarities defined on the edges is known as the multicut problem in combinatorial optimization. Its key feature is that the number of components of the partition need not be specified, but is determined as part of the optimization process given the edge information. This promotes its application to various problems in image segmentation, social network analysis and computer vision. There are two challenges associated with the NP-hard multicut problem as a model for large scale graph partitioning, which we adress in this thesis. Firstly, the methods that are commonly employed to solve practical multicut problems are fast heuristics, due to the large size of the instances. Therefore, the provided solutions come without any (non-trivial) guarantees, neither in terms of the objective value nor in terms of the variable values. In this thesis we develop methods to provide such guarantees in regimes where common linear programming methods are intractable. Our algorithms allow to compute non-trivial lower bounds as well as partial variable assignments of optimal solutions efficiently for large instances. We demonstrate the effectiveness of our methods on benchmark data sets as well as instances from biomedical imaging. The good performance of our approach is facilitated by the inherent structural simplicity that practical instances often exhibit. Towards a further theoretical explanation for this phenomenon, we study sign patterns of the cost vector that prohibit tightness of the standard linear programming relaxation of the multicut problem. Our results enhance the understanding of the practical complexity of signed graph partitioning. Secondly, multicuts do not encode the same-cluster relationship for pairs of nodes that are not adjacent in the underlying graph. A generalization of the multicut ...