  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 $\mathcal{O}(10^8)$ variables in a few seconds with small
primal-dual gaps. Our code is available at
https://github.com/pawelswoboda/RAMA.
