Differentiable solvers for the linear assignment problem (LAP) have attracted
much research attention in recent years, which are usually embedded into
learning frameworks as components. However, previous algorithms, with or
without learning strategies, usually suffer from the degradation of the
optimality with the increment of the problem size. In this paper, we propose a
learnable linear assignment solver based on deep graph networks. Specifically,
we first transform the cost matrix to a bipartite graph and convert the
assignment task to the problem of selecting reliable edges from the constructed
graph. Subsequently, a deep graph network is developed to aggregate and update
the features of nodes and edges. Finally, the network predicts a label for each
edge that indicates the assignment relationship. The experimental results on a
synthetic dataset reveal that our method outperforms state-of-the-art baselines
and achieves consistently high accuracy with the increment of the problem size.
Furthermore, we also embed the proposed solver, in comparison with
state-of-the-art baseline solvers, into a popular multi-object tracking (MOT)
framework to train the tracker in an end-to-end manner. The experimental
results on MOT benchmarks illustrate that the proposed LAP solver improves the
tracker by the largest margin.

本文提出了一种可学习的线性分配求解器，基于深度图网络实现，将费用矩阵转换为二分图，并通过节点和边的特征聚合和更新来选择可靠边，实验结果表明，与现有算法相比，该方法在保证准确性的前提下，能有效提高处理规模。此外，该分配求解器在多目标跟踪领域有着广泛的应用。