Multicut Optimization Guarantees & Geometry of Lifted Multicuts

Abstract

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 problem that allows to model such inter-cluster connectivity for arbitrary pairs of nodes is known as the lifted multicut problem. However, integer linear optimization for this higher-order version of the problem becomes more challenging and requires an analysis of the (convex hull of its) feasible set, the lifted multicut polytope. We study the polyhedral geometry of lifted multicuts by investigating under which conditions the fundamental inequalities associated with lifted multicuts define facets of the lifted multicut polytope. For the special case of trees, we draw a connection to pseudo-Boolean optimization and give a tighter description of the lifted multicut polytope, which is exact when the tree is a simple path. For the moral lineage tracing problem, which is a closely related clustering formulation for joint segmentation and tracking of biological cells in images, we present a tighter description of the associated polytope and an improved branch-and-cut method. Our results are valuable from a theoretical and practical perspective as they enable faster algorithms to solve the lifted multicut problem and related variants. In essence, this thesis develops methods and analyses for multicut optimization guarantees and investigates the polyhedral geometry of lifted multicuts.