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
this https URL

本文提出了一种高度并行化的基于原始 - 对偶算法的方法来解决基于图的聚类问题，通过 GPU 实现，相比于传统的顺序算法在执行速度方面取得了 1-2 个数量级的提升，同时解决了规模为 O (10^8) 的问题。

RAMA：一种基于 GPU 的快速多割算法

RAMA: A Rapid Multicut Algorithm on GPU

We propose a novel end-to-end trainable framework for the graph decomposition
problem. The minimum cost multicut problem is first converted to an
unconstrained binary cubic formulation where cycle consistency constraints are
incorporated into the objective function. The new optimization problem can be
viewed as a Conditional Random Field (CRF) in which the random variables are
associated with the binary edge labels of the initial graph and the hard
constraints are introduced in the CRF as high-order potentials. The parameters
of a standard Neural Network and the fully differentiable CRF are optimized in
an end-to-end manner. Furthermore, our method utilizes the cycle constraints as
meta-supervisory signals during the learning of the deep feature
representations by taking the dependencies between the output random variables
into account. We present analyses of the end-to-end learned representations,
showing the impact of the joint training, on the task of clustering images of
MNIST. We also validate the effectiveness of our approach both for the feature
learning and the final clustering on the challenging task of real-world
multi-person pose estimation.

提出了一种基于条件随机场的端到端可训练框架来解决图分解问题，用于图的二值化和特征表示学习，并在 MNIST 和真实世界中的多人姿态估计任务中进行了验证。

图分解的端到端学习

End-to-end Learning for Graph Decomposition

In combinatorial optimization, partial variable assignments are called
persistent if they agree with some optimal solution. We propose persistency
criteria for the multicut and max-cut problem as well as fast combinatorial
routines to verify them. The criteria that we derive are based on mappings that
improve feasible multicuts, respectively cuts. Our elementary criteria can be
checked enumeratively. The more advanced ones rely on fast algorithms for upper
and lower bounds for the respective cut problems and max-flow techniques for
auxiliary min-cut problems. Our methods can be used as a preprocessing
technique for reducing problem sizes or for computing partial optimality
guarantees for solutions output by heuristic solvers. We show the efficacy of
our methods on instances of both problems from computer vision, biomedical
image analysis and statistical physics.

本研究提出了用于验证多割问题和最大割问题的持久性准则，基于可行多割与割的改进映射，通过枚举检查基本准则，使用快速算法获得高级准则，并利用最大流技术处理辅助最小割问题。该方法可用于预处理，减小问题规模或计算启发式算法输出的部分最优解的优化保证，并在计算机视觉、生物医学图像分析和统计物理中表现出良好的效果。

多割和最大割的组合持久性准则

Combinatorial persistency criteria for multicut and max-cut

In [1], we proposed a graph-based formulation that links and clusters person
hypotheses over time by solving a minimum cost subgraph multicut problem. In
this paper, we modify and extend [1] in three ways: 1) We introduce a novel
local pairwise feature based on local appearance matching that is robust to
partial occlusion and camera motion. 2) We perform extensive experiments to
compare different pairwise potentials and to analyze the robustness of the
tracking formulation. 3) We consider a plain multicut problem and remove
outlying clusters from its solution. This allows us to employ an efficient
primal feasible optimization algorithm that is not applicable to the subgraph
multicut problem of [1]. Unlike the branch-and-cut algorithm used there, this
efficient algorithm used here is applicable to long videos and many detections.
Together with the novel feature, it eliminates the need for the intermediate
tracklet representation of [1]. We demonstrate the effectiveness of our overall
approach on the MOT16 benchmark [2], achieving state-of-art performance.

本文提出了一种基于图形的跟踪方法，使用新的本地成对特征，解决包含离群点的多切割问题并在 MOT16 基准测试上取得了最优效果。