# End-to-end Learning for Graph Decomposition

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2018.

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

- [Shape-aware Multi-Person Pose Estimation from Multi-View Images](https://mlsanity.com/paper/2110.02330/) (2021)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks](https://mlsanity.com/paper/2204.01366/) (2022)
- [Optimizing Edge Detection for Image Segmentation with Multicut Penalties](https://mlsanity.com/paper/2112.05416/) (2021)
- [Stateless actor-critic for instance segmentation with high-level priors](https://mlsanity.com/paper/2107.02600/) (2021)
- [Correlation Clustering of Bird Sounds](https://mlsanity.com/paper/2306.09906/) (2023)

## Abstract (arXiv)

We propose a novel end-to-end trainable framework for the graph decomposition problem. The minimum cost multicut problem is first converted to an unconstrained binary cubic formulation where cycle consistency constraints are incorporated into the objective function. The new optimization problem can be viewed as a Conditional Random Field (CRF) in which the random variables are associated with the binary edge labels of the initial graph and the hard constraints are introduced in the CRF as high-order potentials. The parameters of a standard Neural Network and the fully differentiable CRF are optimized in an end-to-end manner. Furthermore, our method utilizes the cycle constraints as meta-supervisory signals during the learning of the deep feature representations by taking the dependencies between the output random variables into account. We present analyses of the end-to-end learned representations, showing the impact of the joint training, on the task of clustering images of MNIST. We also validate the effectiveness of our approach both for the feature learning and the final clustering on the challenging task of real-world multi-person pose estimation.