Help Privacy Policy Disclaimer
  Advanced SearchBrowse





RAMA: A Rapid Multicut Algorithm on GPU


Abbas,  Ahmed
Computer Vision and Machine Learning, MPI for Informatics, Max Planck Society;


Swoboda,  Paul
Computer Vision and Machine Learning, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 11MB

Supplementary Material (public)
There is no public supplementary material available

Abbas, A., & Swoboda, P. (2021). RAMA: A Rapid Multicut Algorithm on GPU. Retrieved from https://arxiv.org/abs/2109.01838.

Cite as: https://hdl.handle.net/21.11116/0000-0009-B3E6-9
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
Our algorithm produces primal solutions and dual lower bounds that estimate
the distance to optimum. We implement our algorithm on GPUs and show resulting
one to two order-of-magnitudes improvements in execution speed without
sacrificing solution quality compared to traditional serial algorithms that run
on CPUs. We can solve very large scale benchmark problems with up to
$\mathcal{O}(10^8)$ variables in a few seconds with small primal-dual gaps. We
make our code available at https://github.com/pawelswoboda/RAMA.