  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.
