# RAMA: A Rapid Multicut Algorithm on GPU

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 78 references that are in the map.
- First posted on arXiv 4 Sep 2021.

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

- [The Cityscapes Dataset for Semantic Urban Scene Understanding](https://mlsanity.com/paper/1604.01685/) (2016)
- [Lifted Disjoint Paths with Application in Multiple Object Tracking](https://mlsanity.com/paper/2006.14550/) (2020)
- [InstanceCut: from Edges to Instances with MultiCut](https://mlsanity.com/paper/1611.08272/) (2016)
- [ArtTrack: Articulated Multi-person Tracking in the Wild](https://mlsanity.com/paper/1612.01465/) (2016)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [Parallel Correlation Clustering on Big Graphs](https://mlsanity.com/paper/1507.05086/) (2015)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [A new look at reweighted message passing](https://mlsanity.com/paper/1309.5655/) (2013)
- [Higher-order Segmentation via Multicuts](https://mlsanity.com/paper/1305.6387/) (2013)
- [A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems](https://mlsanity.com/paper/1612.05460/) (2016)
- [End-to-end Learning for Graph Decomposition](https://mlsanity.com/paper/1812.09737/) (2018)
- [Combinatorial persistency criteria for multicut and max-cut](https://mlsanity.com/paper/1812.01426/) (2018)
- [Moral Lineage Tracing](https://mlsanity.com/paper/1511.05512/) (2015)
- [Joint Graph Decomposition and Node Labeling: Problem, Algorithms, Applications](https://mlsanity.com/paper/1611.04399/) (2016)
- [A High Performance Implementation of Spectral Clustering on CPU-GPU Platforms](https://mlsanity.com/paper/1802.04450/) (2018)

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

- [SeMoLi: What Moves Together Belongs Together](https://mlsanity.com/paper/2402.19463/) (2024)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [DOGE-Train: Discrete Optimization on GPU with End-to-end Training](https://mlsanity.com/paper/2205.11638/) (2022)
- [FreePoint: Unsupervised Point Cloud Instance Segmentation](https://mlsanity.com/paper/2305.06973/) (2023)
- [ClusterFuG: Clustering Fully connected Graphs by Multicut](https://mlsanity.com/paper/2301.12159/) (2023)
- [MaxCutPool: differentiable feature-aware Maxcut for pooling in graph neural networks](https://mlsanity.com/paper/2409.05100/) (2024)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [Unsupervised Instance Segmentation with Superpixels](https://mlsanity.com/paper/2509.05352/) (2025)
- [Graph Neural Networks with Triangle-Based Messages for the Multicut Problem](https://mlsanity.com/paper/2605.13673/) (2026)

## Abstract (arXiv)

We propose a highly parallel primal-dual algorithm for the multicut (a.k.a. correlation clustering) problem, a classical graph clustering problem widely used in machine learning and computer vision. Our algorithm consists of three steps executed recursively: (1) Finding conflicted cycles that correspond to violated inequalities of the underlying multicut relaxation, (2) Performing message passing between the edges and cycles to optimize the Lagrange relaxation coming from the found violated cycles producing reduced costs and (3) Contracting edges with high reduced costs through matrix-matrix multiplications. Our algorithm produces primal solutions and lower bounds that estimate the distance to optimum. We implement our algorithm on GPUs and show resulting one to two orders-of-magnitudes improvements in execution speed without sacrificing solution quality compared to traditional sequential algorithms that run on CPUs. We can solve very large scale benchmark problems with up to O(108) variables in a few seconds with small primal-dual gaps. Our code is available at https://github.com/pawelswoboda/RAMA.