Pith. sign in

REVIEW 3 major objections 5 minor 28 references

Multi Target Tracking by Learning from Generalized Graph Differences

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a network-flow multi-object tracker can be trained from pairs of feasible tracking solutions using a simple ranking loss, reaching 63.1 MOTA on the hard DukeMTMCT test set without backpropagating through the linear…

desk verdict Useful learning technique for network-flow trackers, with real but fixable reproducibility gaps and an unaddressed gap between pairwise ranking and global LP optimality. read the letter →

arxiv 1908.06646 v1 pith:EBGGZWSD submitted 2019-08-19 cs.CV

H{aa}kan Ardö , Mikael Nilsson This is my paper · ORCID
classification cs.CV
keywords multi-objecttrackingnetworkflowgeneralizedgraphdifferencesrankinglossdataaugmentationDukeMTMCTopticalfeaturessampleefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a way to train a network-flow multi-object tracker by learning a scalar score that ranks the correct track solution above incorrect ones. Instead of backpropagating through the linear programming solver at each training step, the authors train a ranking loss on pairs of near-miss solutions. The near-miss solutions are generated automatically by applying small perturbations to ground-truth tracks, such as ID switches, splits, merges, false positives, skips, and overly short tracks, and each pair is encoded compactly as a generalized graph difference. If the learned ranking is correct, inference reduces to solving the usual network-flow linear program, which finds the best-scoring solution. On DukeMTMCT single-camera tracking, the resulting tracker reaches 63.1 MOTA on the hard test set, the best among the compared methods.

What carries the argument

Generalized graph differences are the central object: a representation of the symmetric difference between two feasible tracking solutions, keeping edges and vertices present in only one solution with positive weights and those present only in the other with negated weights. Because the scoring function is linear over the graph, almost all terms cancel when comparing close solutions, leaving a small and efficiently computable difference. The ranking loss is then evaluated on this difference only, making training independent of graph size. The architecture also uses per-connection neural networks with average pooling over an arbitrary number of optical-flow point tracks or long-range motion-projected connections, so edge features have fixed length regardless of the variable number of connecting tracks.

What would settle it

A direct test would be to record the actual mistakes the trained tracker makes on a validation set, meaning which ID switches, splits, merges, and false positives occur, then regenerate training pairs from exactly those observed error patterns and check whether ranking accuracy and downstream MOTA change. If the fixed catalog is sufficient, the retrained model should not improve; if it improves, the catalog is not covering the error modes.

Watch

Extended reading notes

Core claim

The central claim is that the scoring functions of a network-flow tracker, one per detection and one per edge, can be learned without solving a linear program at every stochastic gradient descent step. The method embeds every feasible solution as a one-dimensional score and trains the embedding with a sigmoid ranking loss on pairs of the form correct solution versus perturbed incorrect solution. Because only terms that differ between the two solutions matter, each pair is represented as a generalized graph difference, which is small for the deliberately generated near-miss pairs. A companion data-augmentation recipe creates many such pairs from a single annotated clip by applying a fixed catalog of local errors to ground-truth tracks. The paper reports that, with public detections and no appearance re-identification, the learned model achieves 63.1 MOTA on the hard DukeMTMCT test set and preserves a median validation MOTA of 75.1 when trained on only one percent of the generated pairs.

Load-bearing premise

The hand-designed catalog of perturbations, such as ID switches, splits, merges, false positives, skips, and too-short tracks, must cover the kinds of errors the tracker actually makes at inference, because the learned score is trained exclusively on these constructed pairs; if a novel failure mode appears at test time that the perturbations do not resemble, nothing in the training procedure guarantees that the true solution will outrank it.

Editorial extensions

If this is right

  • Network-flow multi-object trackers can be trained end-to-end with standard gradient descent and no linear-program solving per training example, reducing training time and implementation complexity.
  • Because generalized graph differences are small for near-miss pairs, many training examples can be generated from one annotated sequence, so the annotation budget per clip goes further.
  • Training on just one percent of the generated differences loses only 0.55 MOTA on the validation set, showing the data-augmentation recipe is highly sample-efficient.
  • Long-range connections that skip over occlusions fit naturally into the framework, since edge features are built by average pooling over a variable number of motion-projected connections.
  • The method reaches strong MOTA on the hard crowd test set but does not include appearance re-identification, leaving IDF1 trailing behind re-identification-based trackers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension the paper does not pursue: the same recipe of generating near-miss feasible solutions, encoding their difference, and optimizing a linear scoring function by ranking could apply to any combinatorial optimization with a linear objective over a graph, such as assignment or matching problems.
  • The hand-designed perturbation catalog could be replaced by an automatically learned error model fitted to the tracker's actual failure modes; sampling perturbations from that model might close the gap between training and test error distributions.
  • The average-pooled, fixed-length edge features could accept appearance descriptors as additional inputs, letting the method be combined with re-identification without changing the training procedure.
  • Because the paper reports a higher MOTA on the full-data validation set than on the easy test set, tuning the perturbation catalog toward long, clean tracks could improve easy-scene performance.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a network-flow-based multi-object tracker in which vertex and edge costs are learned from supervised training data. Instead of backpropagating through the linear program that solves Eq. (8), the authors train a linear score function with a pairwise ranking loss (Eq. 11) on pairs (x*, x), where x* is a ground-truth solution and x is a feasible solution obtained by applying a small, hand-defined perturbation from Tables 1-4 to x*. The differences between x* and x are represented as "generalized graph differences," which cancel common terms and make the training signal sparse. Training examples are generated from a single annotated sequence by enumerating all positions where each perturbation type can be applied, with one mistake per example. Experiments on the DukeMTMCT benchmark report a MOTA of 63.1 on the hard test set, which the paper describes as state of the art, alongside competitive results on the easy set. The paper also presents a data-utilization experiment (Figure 4) showing that comparable MOTA is obtained with only 1% of the generated training data.

Significance. If the central claims hold, the framework offers a computationally attractive alternative to training flow-based trackers by differentiating through a linear program, and the generalized-graph-difference representation is a sensible way to generate many hard training pairs from a modest amount of annotation. The release of the evaluation code and the careful experimental setup for data-utilization are strengths, and the empirical gap on the hard DukeMTMCT test set is meaningful if confirmed. However, the significance is weakened by three load-bearing gaps: the perturbation taxonomy is entirely absent from the manuscript, the argument that local single-modification ranking pairs control the global LP argmax is not established, and the headline comparison in Table 6 rests on single-run scores without error bars despite known run-to-run variance.

major comments (3)
  1. [Section 3.3, Tables 1-4] The four perturbation tables, which specify the exact error types (ID switch, split/merge, skip, false positive, too-short track) used to generate training pairs, are missing from the manuscript; only placeholder captions appear. This is load-bearing because the learned score function is trained exclusively on these perturbations, so the entire method is underspecified and not reproducible without them. Please include the full taxonomy with clear graphical or formal definitions of every perturbation and its constraints.
  2. [Section 3.2-3.3, Eq. (11)] The paper trains a pairwise ranking loss on single-modification perturbations of ground truth and then selects the global argmax over the feasible set S via linear programming. No argument or experiment is provided to show that high accuracy on these local pairs transfers to correctly ranking the global optimum against arbitrary feasible solutions at test time. The statement in Section 3.3 that the perturbations are "sufficient to train the system without ... any additional form of bootstrapping or hard mining" is asserted without evidence. Please add either a theoretical margin-based analysis, a comparison with hard-negative mining or LP-in-the-loop training, or an empirical measurement of the test-time error distribution against the perturbation taxonomy.
  3. [Table 6 and Figure 4] Table 6 reports only a single run for each method, while Figure 4 shows substantial variance across ten runs for the proposed tracker (the MOTA spread between the 10% and 90% quantiles is several points). Without multiple-seed results or error bars on the hard test set, the claim of state-of-the-art MOTA (63.1 versus 60.9 for the closest comparison) is not statistically supported. Please report mean and standard deviation (or equivalent) over at least a few runs for the main comparison, and clarify whether the reported number is the best or the mean run.
minor comments (5)
  1. [Section 4.1] The text says "Results are evaluated on MOTA16 and presented in Tab ??" but the table is actually Table 5; please fix the cross-reference.
  2. [Section 3.3] The sentence "Thus the focus here is on the graph-difference in a general sense when referring to general graph difference" is circular and should be rewritten to clarify what property is being invoked by the name.
  3. [Section 3.1, Eq. (10)] Equation (10) has an awkward indexing artifact after the averaging symbol; please clean up the notation to make the sum over the long connections unambiguous.
  4. [Section 4.1] The description of the comparison with Schulter et al. uses the label [23] for what appears to be the same experiment; please check the reference numbering and make sure the cited prior work matches the table source.
  5. [Figure 4] The figure legend and axes are difficult to read in the PDF; please increase font sizes and ensure the caption fully explains both the purple MOTA curves and the red training-time curve.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the learned tracker is trained on ground-truth perturbations and evaluated on a held-out test set.

full rationale

The paper's derivation chain is self-contained. The score function fscore is defined in Eq. (6), the feasible set S in Eq. (7), and inference is the argmax in Eq. (8); no component is defined in terms of the DukeMTMCT test outputs. The parameters are learned with the ranking loss Eq. (11) over pairs (x*, x), where x* is annotation-derived ground truth and x is generated by applying one perturbation from Tables 1-4 to ground truth. The held-out hard test set contributes neither gradients nor model selection, so the reported MOTA 63.1 is not forced by construction. The generalized graph difference is an algebraic cancellation of common terms in the linear score difference, which is a representation identity rather than a prediction smuggled from the input. The concern that test-time errors may be combinations of perturbation types not covered by the taxonomy is a generalization assumption, not a circular reduction, and the absence of Tables 1-4 from the manuscript is a reproducibility gap, not circularity. The paper contains no load-bearing self-citations and imports no uniqueness theorems from the authors' prior work.

Assumptions & free parameters 7 free parameters · 4 assumptions · 1 invented entities

The paper is an empirical machine learning method, so the central claim rests on hand-chosen hyperparameters (free parameters), standard mathematical guarantees, and domain assumptions about optical flow and the distribution of tracking errors. The learned neural network weights are supervised from training data and are not counted as ad hoc free parameters. The generalized graph difference is a new representation introduced by the paper with direct empirical validation.

free parameters (7)
  • rneighbours = 5
    Number of preceding/following detections considered neighbours along a feature point track (Section 2.1, Section 4.2).
  • tmax = 3*nfps
    Maximum temporal gap for an edge in the tracking graph (Section 2.1, Section 4.2).
  • nvelest = 0.5*nfps
    Number of feature point positions used to estimate incoming and outgoing velocity (Section 2.2, Section 4.2).
  • nproject = nfps
    Number of future frames over which long-range connections project detections (Section 2.2, Section 4.2).
  • nminlen = 2
    Minimum track length for the 'too short track' training pairs (Section 3.3, Section 4.2).
  • Network architecture sizes = ndetlayers=4, ndetfeat=32, nkltlayers=7, nkltfeat=64, nlonglayers=7, nlongfeat=32, ncombinelayers=4, ncombinefeat=256
    Hand-chosen widths and depths of the fully connected networks used for detection scores, KLT-track features, long-connection features, and the combine network (Section 4.2).
  • nlinpkt = not reported
    Number of interpolation points for the normalized trajectory shape in edge features (Section 3.1); the value is not given in the text, so the feature extraction is not fully specified.
assumptions (4)
  • standard math The flow polytope of the constructed graph is totally unimodular, so the linear programming relaxation yields an integer solution.
    Invoked in Section 2.4 to guarantee that solving the LP gives a feasible tracking solution; cited to Berclaz et al. [2].
  • domain assumption KLT optical flow feature point tracks provide reliable motion evidence connecting detections of the same object.
    The entire graph construction in Section 2.1 depends on KLT tracks intersecting detections; if the tracks frequently jump between objects or fail, the edge structure itself is corrupted.
  • domain assumption Small perturbations of ground-truth tracks approximate the distribution of errors made by the tracker at inference time.
    Section 3.3 constructs training pairs only from these perturbations and claims they are sufficient without bootstrapping or hard mining; no evidence is provided that the perturbation distribution matches actual inference error patterns.
  • domain assumption Average pooling over a varying number of feature point tracks preserves the information needed for accurate edge scoring.
    Equations (9) and (10) use average pooling to combine per-track feature vectors into a fixed-length representation; the paper does not analyze whether averaging loses critical information, such as the reliability of individual tracks.
invented entities (1)
  • Generalized graph difference independent evidence
    purpose: Compact representation of the difference between two feasible tracking solutions, used to define the ranking loss and to generate training examples from ground-truth perturbations.
    The concept is a mathematical/data representation rather than a physical entity. The paper provides empirical evidence of its utility by training a tracker that achieves competitive MOTA, so it has a falsifiable handle through benchmark performance. The 'graviton problem' does not apply because the representation is not a free postulate used to explain away a result; it is the mechanism of the proposed method.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multi Target Tracking by Learning from Generalized Graph Differences." pith.science (2026). https://pith.science/paper/EBGGZWSD

@misc{pith2026190806646,
  author       = {Pith},
  title        = {Pith review of: Multi Target Tracking by Learning from Generalized Graph Differences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EBGGZWSD}},
  note         = {Machine review of arXiv:1908.06646}
}
read the original abstract

Formulating the multi object tracking problem as a network flow optimization problem is a popular choice. In this paper an efficient way of learning the weights of such a network is presented. It separates the problem into one embedding of feasible solutions into a one dimensional feature space and one optimization problem. The embedding can be learned using standard SGD type optimization without relying on an additional optimizations within each step. Training data is produced by performing small perturbations of ground truth tracks and representing them using generalized graph differences, which is an efficient way introduced to represent the difference between two graphs. The proposed method is evaluated on DukeMTMCT with competitive results.

Figures

Figures reproduced from arXiv: 1908.06646 by the authors.

Figure 1
Figure 1. Concept of proposed method to address tracking with a graph and learning mapping for edges and vertices. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The architecture of fedge (Pk1,k2 , Ck1,k2 , vk1 , vk2 ) [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. A pair of detections, (vk1 , vk2 ) (black boxes) connected with [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: MOTA score (median and quantiles over ten runs) of [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Generic fully connect neural network used in framework. [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 24 canonical work pages

  1. [23]

    Y . T. Tesfaye, E. Zemene, A. Prati, M. Pelillo, and M. Shah. Multi-target tracking in multiple non-overlapping cameras using constrained dominant sets. CoRR, abs/1706.06196,

    arXiv

  2. [22]

    Schulter, P

    S. Schulter, P. Vernaza, W. Choi, and M. K. Chandraker. Deep network flow for multi-object tracking. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2730–2739, 2017. 1, 6

    work page 2017

  3. [1]

    R. K. Ahuja, T. L. Magnanti, and J. B. Orlin.Network Flows: Theory, Algorithms, and Applications . Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993. 4

    work page 1993

  4. [2]

    Berclaz, F

    J. Berclaz, F. Fleuret, E. Turetken, and P. Fua. Multiple object tracking using k-shortest paths optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(9):1806–1819, Sept 2011. 1, 4

    work page 2011

  5. [3]

    Bernardin and R

    K. Bernardin and R. Stiefelhagen. Evaluating multiple ob- ject tracking performance: The clear mot metrics. EURASIP Journal on Image and Video Processing , 2008(1):246309, May 2008. 7

    work page 2008

  6. [4]

    Bertsekas and R

    D. Bertsekas and R. Gallager. Data Networks (2Nd Ed.) . Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1992. 4

    work page 1992

  7. [5]

    Z. Cao, T. Simon, S. Wei, and Y . Sheikh. Realtime multi- person 2d pose estimation using part affinity fields. In 2017 IEEE Conference on Computer Vision and Pattern Recogni- tion (CVPR), pages 1302–1310, July 2017. 1

    work page 2017

  8. [6]

    J. Dai, Y . Li, K. He, and J. Sun. R-fcn: Object detection via region-based fully convolutional networks. In D. D. Lee, M. Sugiyama, U. V . Luxburg, I. Guyon, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems 29, pages 379–387. Curran Associates, Inc., 2016. 1

    work page 2016

Show all 28 references
  1. [7]

    P. F. Felzenszwalb, D. A. McAllester, and D. Ramanan. A discriminatively trained, multiscale, deformable part model. In 2008 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2008), 24-26 June 2008, Anchorage, Alaska, USA, 2008. 7

    2008

  2. [8]

    Frossard and R

    D. Frossard and R. Urtasun. End-to-end learning of multi- sensor 3d tracking by detection. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 635– 642, May 2018. 1, 4

    2018

  3. [9]

    C. Kim, F. Li, A. Ciptadi, and J. M. Rehg. Multiple hy- pothesis tracking revisited. In 2015 IEEE International Con- ference on Computer Vision (ICCV), pages 4696–4704, Dec

    2015

  4. [10]

    D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2014. 8

    2014 arXiv

  5. [11]

    Y . Li, C. Huang, and R. Nevatia. Learning to associate: Hy- bridboosted multi-target tracker for crowded scene. In 2009 IEEE Conference on Computer Vision and Pattern Recogni- tion, pages 2953–2960, June 2009. 7

    2009

  6. [12]

    T. Lin, P. Doll ´ar, R. Girshick, K. He, B. Hariharan, and S. Belongie. Feature pyramid networks for object detection. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 936–944, July 2017. 1

    2017

  7. [13]

    W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C. Fu, and A. Berg. Ssd: Single shot multibox detector. In B. Leibe, J. Matas, M. Welling, and N. Sebe, editors, Computer Vision - 14th European Conference, ECCV 2016, Proceedings, Lec- ture Notes in Computer Science (includi...

    2016

  8. [14]

    W. Luo, X. Zhao, and T. Kim. Multiple object tracking: A review. CoRR, abs/1409.7618, 2014. 3

    2014 arXiv

  9. [15]

    R. P. S. Mahler. Multitarget bayes filtering via first-order multitarget moments. IEEE Transactions on Aerospace and Electronic Systems, 39(4):1152–1178, Oct 2003. 1

    2003

  10. [16]

    R. P. S. Mahler. Statistical Multisource-Multitarget Informa- tion Fusion. Artech House, Inc., Norwood, MA, USA, 2007. 1

    2007

  11. [17]

    Maksai, X

    A. Maksai, X. Wang, F. Fleuret, and P. Fua. Non-markovian globally consistent multi-object tracking. In 2017 IEEE In- ternational Conference on Computer Vision (ICCV) , pages 2563–2573, Oct 2017. 8

    2017

  12. [18]

    Pirsiavash, D

    H. Pirsiavash, D. Ramanan, and C. C. Fowlkes. Globally- optimal greedy algorithms for tracking a variable number of objects. In Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’11, pages 1201–1208, Washington, DC, USA, 2011. IEEE Comput...

    2011

  13. [19]

    Redmon and A

    J. Redmon and A. Farhadi. Yolo9000: Better, faster, stronger. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6517–6525, July 2017. 1

    2017

  14. [20]

    Ristani, F

    E. Ristani, F. Solera, R. S. Zou, R. Cucchiara, and C. Tomasi. Performance measures and a data set for multi-target, multi- camera tracking. In Computer Vision - ECCV 2016 Work- shops - Amsterdam, The Netherlands, October 8-10 and 15- 16, 2016, Proceedings, Part II, pages 17–3...

    2016

  15. [21]

    Ristani and C

    E. Ristani and C. Tomasi. Tracking multiple people online and in real time. In Asian Conference on Computer Vision, pages 444–459. Springer, 2014. 7

    2014

  16. [24]

    B. Xiao, H. Wu, and Y . Wei. Simple baselines for human pose estimation and tracking. In European Conference on Computer Vision (ECCV), 2018. 1

    2018

  17. [25]

    K. Yoon, Y . Song, and M. Jeon. Multiple hypothesis tracking algorithm for multi-target multi-camera tracking with dis- joint views. IET Image Processing, 12(7):1175–1184, 2018. 8

    2018

  18. [26]

    yves Bouguet

    J. yves Bouguet. Pyramidal implementation of the lucas kanade feature tracker. Intel Corporation, Microprocessor Research Labs, 2000. 2

    2000

  19. [27]

    Zhang, Y

    L. Zhang, Y . Li, and R. Nevatia. Global data association for multi-object tracking using network flows. In 2008 IEEE Computer Society Conference on Computer Vision and Pat- tern Recognition (CVPR 2008), 24-26 June 2008, Anchor- age, Alaska, USA, 2008. 1, 4

    2008

  20. [28]

    Zhang, J

    Z. Zhang, J. Wu, X. Zhang, and C. Zhang. Multi-target, multi-camera tracking by hierarchical clustering: Recent progress on dukemtmc project. CoRR, abs/1712.09531,

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.