A Graph Neural Network Approach for Solving the Ranked Assignment Problem in Multi-Object Tracking

Robin Dehler; Martin Herrmann; Jan Strohbeck; Michael Buchholz

cs.ROApr 2, 2026

A Graph Neural Network Approach for Solving the Ranked Assignment Problem in Multi-Object Tracking

Authors: Robin Dehler, Martin Herrmann, Jan Strohbeck, Michael Buchholz

Organizations: The authors are with the Institute of Measurement, Control and Microtechnology, Ulm University, D-89081 Ulm, Germany.

Abstract

Associating measurements with tracks is a crucial step in Multi-Object Tracking (MOT) to guarantee the safety of autonomous vehicles. To manage the exponentially growing number of track hypotheses, truncation becomes necessary. In the $δ$ -Generalized Labeled Multi-Bernoulli ( $δ$ -GLMB) filter application, this truncation typically involves the ranked assignment problem, solved by Murty's algorithm or the Gibbs sampling approach, both with limitations in terms of complexity or accuracy, respectively. With the motivation to improve these limitations, this paper addresses the ranked assignment problem arising from data association tasks with an approach that employs Graph Neural Networks (GNNs). The proposed Ranked Assignment Prediction Graph Neural Network (RAPNet) uses bipartite graphs to model the problem, harnessing the computational capabilities of deep learning. The conclusive evaluation compares the RAPNet with Murty's algorithm and the Gibbs sampler, showing accuracy improvements compared to the Gibbs sampler.

Figures & tables

Panel of Figure 1 — Fig. 1 : Architecture of the RAPNet. Left part: Encoding of the node and edge features. Before the multiplication step of $x_{s}$ and $x_{t}$ , the feature vectors are indexed with the respective edge index vectors to fit the dimensions. Right part: Decoding using LSTM layers and creation of predicted assignments. The channel sizes $C_{\text{enc}}=32$ , $C_{\text{lstm}}=128$ and $C_{\text{dec}}=32$ are shown above each neural network layer. The final output $y_{\text{pred}}$ is of shape $|\mathcal{E}|\times k_{\text{max}}$ .

Panel of Figure 2 — Fig. 2 : Plots of the two sweeps of the parameters $k_{\text{max}}$ and $\nu_{s}$ evaluated with the scores accuracy, wp and cost. For readability reasons in the accuracy plots, only the accuracies of the first $4$ solutions for the RAPNet with the post-processing and the Gibbs sampler are shown. The legends on the right are also valid for the left plots. In the legends, RAPNet-PP and RAPNet-a indicate the versions with and without post-processing, respectively.

Panel of Figure 3 — Fig. 3 : Distribution of matrix sizes in the simulation data.

Framework	Accuracies				wp	Cost
Framework	$i=1$	$i=2$	$i=3$	$i=4$	wp	Cost
RAPNet-a	$\underline{0.99}$	$\underline{0.91}$	$\underline{0.73}$	$\underline{0.54}$	$\underline{2.74}$	$\underline{5.68}$
RAPNet-PP	$\underline{0.99}$	$\mathbf{0.95}$	$\mathbf{0.82}$	$\mathbf{0.66}$	$\mathbf{2.80}$	$\mathbf{3.23}$
Gibbs	$\mathbf{1}$	$0.18$	$0.06$	$0.04$	$2.11$	$14.10$

TABLE I : Comparison of the RAPNet versions to the Gibbs sampler on simulation data.

Rows	Graph	RAP-	RAP-	PP 32	PP	Gibbs	Murty
$\nu_{s}$	Creation	Net 32	Net	PP 32	PP	Gibbs	Murty
$1$	0.29	0.12	3.04	0.32	0.53	0.05	0.03
$3$	0.30	0.15	3.03	0.39	0.59	0.12	0.14
$5$	0.30	0.19	3.06	0.45	0.64	0.19	0.28
$7$	0.31	0.25	3.11	0.47	0.68	0.26	0.43
$9$	0.31	0.32	3.15	0.48	0.70	0.32	0.61

TABLE II : Time consumption of the different modules, in ms.

Explore similar work

SSP-GNN: Learning to Track via Bilevel Optimization
Jul 5, 2024Griffin Golias, Masa Nakura-Fan, Vitaly AblavskyGraph Neural Networks Visual Object Tracking
Applied Physics Laboratory University of Washington Seattle, WA 98105 USA · Paul G. Allen School of Computer Science University of Washington Seattle, WA 98105 USA
DeepMTL2R: A Library for Deep Multi-task Learning to Rank
Feb 16, 2026Chaosheng Dong, Peiyao Xiao, Yijia Wang +1Learning to Rank Multi-Task Learning
Amazon USA
HDST-GNN: Heterogeneous Dynamic Spatiotemporal Graph Neural Networks for Multi-Object Tracking in UAV Aerial Imagery
Jun 4, 2026Phillip JiangHeterogeneous GNNs Visual Object Tracking
Appsofa LLC

Jul 5, 2024J/K move · Enter open · S save

SSP-GNN: Learning to Track via Bilevel Optimization

Griffin Golias, Masa Nakura-Fan, Vitaly Ablavsky

Applied Physics Laboratory University of Washington Seattle, WA 98105 USA · Paul G. Allen School of Computer Science University of Washington Seattle, WA 98105 USA

Graph Neural Networks Visual Object Tracking Multi-Object Tracking

Open paper AskPDF arXiv

We propose a graph-based tracking formulation for multi-object tracking (MOT) where target detections contain kinematic information and re-identification features (attributes). Our method applies a successive shortest paths (SSP) algorithm to a tracking graph defined over a batch of frames. The edge costs in this tracking graph are computed via a message-passing network, a graph neural network (GNN) variant. The parameters of the GNN, and hence, the tracker, are learned end-to-end on a training set of example ground-truth tracks and detections. Specifically, learning takes the form of bilevel optimization guided by our novel loss function. We evaluate our algorithm on simulated scenarios to understand its sensitivity to scenario aspects and model hyperparameters. Across varied scenario complexities, our method compares favorably to a strong baseline.

Abstract

Explore similar work

SSP-GNN: Learning to Track via Bilevel Optimization

DeepMTL2R: A Library for Deep Multi-task Learning to Rank

HDST-GNN: Heterogeneous Dynamic Spatiotemporal Graph Neural Networks for Multi-Object Tracking in UAV Aerial Imagery