Analysis and Optimization of Graph Decompositions by Lifted Multicuts

Understand

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 a class 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.