# ClusterFuG: Clustering Fully connected Graphs by Multicut

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 62 references that are in the map.
- First posted on arXiv 28 Jan 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [An Empirical Study of Training Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.02057/) (2021)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Panoptic Segmentation](https://mlsanity.com/paper/1801.00868/) (2018)
- [MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers](https://mlsanity.com/paper/2012.00759/) (2020)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [InstanceCut: from Edges to Instances with MultiCut](https://mlsanity.com/paper/1611.08272/) (2016)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [DeepLab2: A TensorFlow Library for Deep Labeling](https://mlsanity.com/paper/2106.09748/) (2021)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds](https://mlsanity.com/paper/2111.10699/) (2021)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [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)
- [GASP, a generalized framework for agglomerative clustering of signed graphs and its application to Instance Segmentation](https://mlsanity.com/paper/1906.11713/) (2019)
- [Correlation Clustering with Low-Rank Matrices](https://mlsanity.com/paper/1611.07305/) (2016)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)

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

- [I Spy With My Little Eye: A Minimum Cost Multicut Investigation of Dataset Frames](https://mlsanity.com/paper/2412.01296/) (2024)
- [Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network](https://mlsanity.com/paper/2502.14536/) (2025)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [Graph Neural Networks with Triangle-Based Messages for the Multicut Problem](https://mlsanity.com/paper/2605.13673/) (2026)
- [Dual-Learning based Penalized Multi-Align Clustering for Multi-View Incomplete and Disorderly Data](https://mlsanity.com/paper/2606.27984/) (2026)

## Abstract (arXiv)

We propose a graph clustering formulation based on multicut (a.k.a. weighted correlation clustering) on the complete graph. Our formulation does not need specification of the graph topology as in the original sparse formulation of multicut, making our approach simpler and potentially better performing. In contrast to unweighted correlation clustering we allow for a more expressive weighted cost structure. In dense multicut, the clustering objective is given in a factorized form as inner products of node feature vectors. This allows for an efficient formulation and inference in contrast to multicut/weighted correlation clustering, which has at least quadratic representation and computation complexity when working on the complete graph. We show how to rewrite classical greedy algorithms for multicut in our dense setting and how to modify them for greater efficiency and solution quality. In particular, our algorithms scale to graphs with tens of thousands of nodes. Empirical evidence on instance segmentation on Cityscapes and clustering of ImageNet datasets shows the merits of our approach.