# A Comparative Study of Graph Matching Algorithms in Computer Vision

arXiv: https://arxiv.org/abs/2207.00291 · HTML: https://mlsanity.com/paper/2207.00291/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 67 references that are in the map.
- First posted on arXiv 1 Jul 2022.

## Builds on (most cited first, 10 of 10)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems](https://mlsanity.com/paper/1404.0533/) (2014)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [A Solution for Multi-Alignment by Transformation Synchronisation](https://mlsanity.com/paper/1410.8546/) (2014)
- [Best practices for comparing optimization algorithms](https://mlsanity.com/paper/1709.08242/) (2017)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [Discrete graphical models -- an optimization perspective](https://mlsanity.com/paper/2001.09017/) (2020)
- [Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization](https://mlsanity.com/paper/2004.07715/) (2020)

## Built on by (most cited first, 14 of 14)

- [LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matching](https://mlsanity.com/paper/2306.11925/) (2023)
- [Partial-to-Partial Shape Matching with Geometric Consistency](https://mlsanity.com/paper/2404.12209/) (2024)
- [It's a (Blind) Match! Towards Vision-Language Correspondence without Parallel Data](https://mlsanity.com/paper/2503.24129/) (2025)
- [ExGra-Med: Extended Context Graph Alignment for Medical Vision-Language Models](https://mlsanity.com/paper/2410.02615/) (2024)
- [Fast Globally Optimal and Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2504.06385/) (2025)
- [Unsupervised Deep Graph Matching Based on Cycle Consistency](https://mlsanity.com/paper/2307.08930/) (2023)
- [CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment](https://mlsanity.com/paper/2406.13216/) (2024)
- [Optimizing Incomplete, Large-Scale and Sparse Multi-Graph Matching in Bioimaging](https://mlsanity.com/paper/2406.18215/) (2024)
- [Relative-Interior Solution for the (Incomplete) Linear Assignment Problem with Applications to the Quadratic Assignment Problem](https://mlsanity.com/paper/2301.11201/) (2023)
- [Normalized Matching Transformer](https://mlsanity.com/paper/2503.17715/) (2025)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [Cycle-Consistent Multi-Graph Matching for Self-Supervised Annotation of C.Elegans](https://mlsanity.com/paper/2503.07348/) (2025)
- [Bridge the Gap Between Visual and Linguistic Comprehension for Generalized Zero-shot Semantic Segmentation](https://mlsanity.com/paper/2503.23806/) (2025)
- [Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment](https://mlsanity.com/paper/2608.29635/) (2026)

## Abstract (arXiv)

The graph matching optimization problem is an essential component for many tasks in computer vision, such as bringing two deformable objects in correspondence. Naturally, a wide range of applicable algorithms have been proposed in the last decades. Since a common standard benchmark has not been developed, their performance claims are often hard to verify as evaluation on differing problem instances and criteria make the results incomparable. To address these shortcomings, we present a comparative study of graph matching algorithms. We create a uniform benchmark where we collect and categorize a large set of existing and publicly available computer vision graph matching problems in a common format. At the same time we collect and categorize the most popular open-source implementations of graph matching algorithms. Their performance is evaluated in a way that is in line with the best practices for comparing optimization algorithms. The study is designed to be reproducible and extensible to serve as a valuable resource in the future. Our study provides three notable insights: 1.) popular problem instances are exactly solvable in substantially less than 1 second and, therefore, are insufficient for future empirical evaluations; 2.) the most popular baseline methods are highly inferior to the best available methods; 3.) despite the NP-hardness of the problem, instances coming from vision applications are often solvable in a few seconds even for graphs with more than 500 vertices.