# Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 44 references that are in the map.
- First posted on arXiv 1 Aug 2021.

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

- [Deep Learning for Person Re-identification: A Survey and Outlook](https://mlsanity.com/paper/2001.04193/) (2020)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels](https://mlsanity.com/paper/1711.08920/) (2017)
- [SPair-71k: A Large-scale Benchmark for Semantic Correspondence](https://mlsanity.com/paper/1908.10543/) (2019)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [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)
- [GLMNet: Graph Learning-Matching Networks for Feature Matching](https://mlsanity.com/paper/1911.07681/) (2019)

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

- [Factor Graph Neural Networks](https://mlsanity.com/paper/2308.00887/) (2023)
- [GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales](https://mlsanity.com/paper/2506.06634/) (2025)
- [Surrogate Interpretable Graph for Random Decision Forests](https://mlsanity.com/paper/2506.01988/) (2025)

## Abstract (arXiv)

Graph matching is an important problem that has received widespread attention, especially in the field of computer vision. Recently, state-of-the-art methods seek to incorporate graph matching with deep learning. However, there is no research to explain what role the graph matching algorithm plays in the model. Therefore, we propose an approach integrating a MILP formulation of the graph matching problem. This formulation is solved to optimal and it provides inherent baseline. Meanwhile, similar approaches are derived by releasing the optimal guarantee of the graph matching solver and by introducing a quality level. This quality level controls the quality of the solutions provided by the graph matching solver. In addition, several relaxations of the graph matching problem are put to the test. Our experimental evaluation gives several theoretical insights and guides the direction of deep graph matching methods.