# A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2016.

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

- [LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matching](https://mlsanity.com/paper/2306.11925/) (2023)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (2021)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2204.12805/) (2022)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [Factor Graph Neural Networks](https://mlsanity.com/paper/2308.00887/) (2023)
- [A Comparative Study of Graph Matching Algorithms in Computer Vision](https://mlsanity.com/paper/2207.00291/) (2022)
- [Joint Graph Learning and Matching for Semantic Feature Correspondence](https://mlsanity.com/paper/2109.00240/) (2021)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [ExGra-Med: Extended Context Graph Alignment for Medical Vision-Language Models](https://mlsanity.com/paper/2410.02615/) (2024)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections](https://mlsanity.com/paper/2103.17229/) (2021)
- [Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?](https://mlsanity.com/paper/2108.00394/) (2021)
- [Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision](https://mlsanity.com/paper/2202.00418/) (2022)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (2022)
- [Learnable Graph Matching: A Practical Paradigm for Data Association](https://mlsanity.com/paper/2303.15414/) (2023)
- [Unsupervised Deep Graph Matching Based on Cycle Consistency](https://mlsanity.com/paper/2307.08930/) (2023)
- [Convex Joint Graph Matching and Clustering via Semidefinite Relaxations](https://mlsanity.com/paper/2110.11335/) (2021)
- [Deep Probabilistic Graph Matching](https://mlsanity.com/paper/2201.01603/) (2022)
- [Normalized Matching Transformer](https://mlsanity.com/paper/2503.17715/) (2025)
- [Training Free Graph Neural Networks for Graph Matching](https://mlsanity.com/paper/2201.05349/) (2022)
- [M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering](https://mlsanity.com/paper/2310.18444/) (2023)
- [Convergence of Some Convex Message Passing Algorithms to a Fixed Point](https://mlsanity.com/paper/2403.07004/) (2024)
- [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)

## Abstract (arXiv)

We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore s direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art any-time solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.