# Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers

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

## Key facts

- Cited by 81 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2020.

## Built on by (most cited first, 30 of 81)

- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [Relationformer: A Unified Framework for Image-to-Graph Generation](https://mlsanity.com/paper/2203.10202/) (2022)
- [LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matching](https://mlsanity.com/paper/2306.11925/) (2023)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Convolutional Hough Matching Networks](https://mlsanity.com/paper/2103.16831/) (2021)
- [SD4Match: Learning to Prompt Stable Diffusion Model for Semantic Matching](https://mlsanity.com/paper/2310.17569/) (2023)
- [SIMPLE: A Gradient Estimator for k-Subset Sampling](https://mlsanity.com/paper/2210.01941/) (2022)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [Backpropagation through Combinatorial Algorithms: Identity with Projection Works](https://mlsanity.com/paper/2205.15213/) (2022)
- [Jigsaw: Learning to Assemble Multiple Fractured Objects](https://mlsanity.com/paper/2305.17975/) (2023)
- [Densely Constrained Depth Estimator for Monocular 3D Object Detection](https://mlsanity.com/paper/2207.10047/) (2022)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [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)
- [Equivariant Hypergraph Neural Networks](https://mlsanity.com/paper/2208.10428/) (2022)
- [Convolutional Hough Matching Networks for Robust and Efficient Visual Correspondence](https://mlsanity.com/paper/2109.05221/) (2021)
- [Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.04862/) (2022)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)
- [Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach](https://mlsanity.com/paper/2106.03188/) (2021)
- [Assessing SATNet's Ability to Solve the Symbol Grounding Problem](https://mlsanity.com/paper/2312.11522/) (2023)
- [IKOL: Inverse kinematics optimization layer for 3D human pose and shape estimation via Gauss-Newton differentiation](https://mlsanity.com/paper/2302.01058/) (2023)
- [Joint Graph Learning and Matching for Semantic Feature Correspondence](https://mlsanity.com/paper/2109.00240/) (2021)
- [Total Variation Optimization Layers for Computer Vision](https://mlsanity.com/paper/2204.03643/) (2022)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent](https://mlsanity.com/paper/2409.17500/) (2024)

## Abstract (arXiv)

Building on recent progress at the intersection of combinatorial optimization and deep learning, we propose an end-to-end trainable architecture for deep graph matching that contains unmodified combinatorial solvers. Using the presence of heavily optimized combinatorial solvers together with some improvements in architecture design, we advance state-of-the-art on deep graph matching benchmarks for keypoint correspondence. In addition, we highlight the conceptual advantages of incorporating solvers into deep learning architectures, such as the possibility of post-processing with a strong multi-graph matching solver or the indifference to changes in the training setting. Finally, we propose two new challenging experimental setups. The code is available at https://github.com/martius-lab/blackbox-deep-graph-matching