GLAN: A Graph-based Linear Assignment Network
This addresses a bottleneck in differentiable LAP solvers for applications like multi-object tracking, offering a novel method to maintain accuracy with larger problem sizes.
The paper tackles the degradation of optimality in differentiable linear assignment problem (LAP) solvers as problem size increases by proposing GLAN, a learnable solver based on deep graph networks that transforms the cost matrix to a bipartite graph and predicts edge assignments. It outperforms state-of-the-art baselines with consistently high accuracy on synthetic data and improves multi-object tracking by the largest margin when embedded into a tracker.
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.