English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

RAMA: A Rapid Multicut Algorithm on GPU

MPS-Authors
/persons/resource/persons238023

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

/persons/resource/persons221924

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)

arXiv:2109.01838.pdf
(Preprint), 11MB

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

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
Abstract
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 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.