RAMA: A Rapid Multicut Algorithm on GPU
This provides a rapid solution for large-scale graph clustering tasks in machine learning and computer vision, though it is incremental as it builds on existing multicut methods with parallelization.
The paper tackles the multicut problem in graph clustering by proposing a highly parallel primal-dual algorithm implemented on GPUs, achieving one to two orders-of-magnitude speed improvements while maintaining solution quality, solving problems with up to 10^8 variables in seconds with small primal-dual gaps.
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.