# A Polyhedral Study of Lifted Multicuts

arXiv: https://arxiv.org/abs/2202.08068 · HTML: https://mlsanity.com/paper/2202.08068/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 65 references that are in the map.
- First posted on arXiv 16 Feb 2022.

## Builds on (most cited first, 5 of 5)

- [Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs](https://mlsanity.com/paper/1412.0681/) (2014)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [Coalition Structure Generation over Graphs](https://mlsanity.com/paper/1401.6428/) (2014)
- [Correlation Clustering with Low-Rank Matrices](https://mlsanity.com/paper/1611.07305/) (2016)
- [Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation](https://mlsanity.com/paper/1901.07904/) (2019)

## Built on by (most cited first, 3 of 3)

- [A Graph Multi-separator Problem for Image Segmentation](https://mlsanity.com/paper/2307.04592/) (2023)
- [Box Facets and Cut Facets of Lifted Multicut Polytopes](https://mlsanity.com/paper/2402.16814/) (2024)
- [The canonical facets of multi-separator polytopes](https://mlsanity.com/paper/2608.16861/) (2026)

## Abstract (arXiv)

Fundamental to many applications in data analysis are the decompositions of a graph, i.e. partitions of the node set into component-inducing subsets. One way of encoding decompositions is by multicuts, the subsets of those edges that straddle distinct components. Recently, a lifting of multicuts from a graph G = (V, E) to an augmented graph hat G = (V, E cup F) has been proposed in the field of image analysis, with the goal of obtaining a more expressive characterization of graph decompositions in which it is made explicit also for pairs F subseteq tbinomV2 setminus E of non-neighboring nodes whether these are in the same or distinct components. In this work, we study in detail the polytope in ℝE cup F whose vertices are precisely the characteristic vectors of multicuts of hat G lifted from G, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope.