# Deep Graph Matching under Quadratic Constraint

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 11 Mar 2021.

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

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Focal Loss for Dense Object Detection](https://mlsanity.com/paper/1708.02002/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels](https://mlsanity.com/paper/1711.08920/) (2017)
- [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)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Training Deep Networks with Structured Layers by Matrix Backpropagation](https://mlsanity.com/paper/1509.07838/) (2015)
- [A Functional Representation for Graph Matching](https://mlsanity.com/paper/1901.05179/) (2019)
- [GLMNet: Graph Learning-Matching Networks for Feature Matching](https://mlsanity.com/paper/1911.07681/) (2019)

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

- [SIGMA: Semantic-complete Graph Matching for Domain Adaptive Object Detection](https://mlsanity.com/paper/2203.06398/) (2022)
- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Bi-VLGM : Bi-Level Class-Severity-Aware Vision-Language Graph Matching for Text Guided Medical Image Segmentation](https://mlsanity.com/paper/2305.12231/) (2023)
- [Joint Graph Learning and Matching for Semantic Feature Correspondence](https://mlsanity.com/paper/2109.00240/) (2021)
- [Synchronous Diffusion for Unsupervised Smooth Non-Rigid 3D Shape Matching](https://mlsanity.com/paper/2407.08244/) (2024)
- [Ensemble Quadratic Assignment Network for Graph Matching](https://mlsanity.com/paper/2403.06457/) (2024)
- [SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching](https://mlsanity.com/paper/2205.13679/) (2022)
- [Graph Matching Optimization Network for Point Cloud Registration](https://mlsanity.com/paper/2302.05844/) (2023)
- [Learning Partial Graph Matching via Optimal Partial Transport](https://mlsanity.com/paper/2410.16718/) (2024)
- [Deep Probabilistic Graph Matching](https://mlsanity.com/paper/2201.01603/) (2022)
- [Normalized Matching Transformer](https://mlsanity.com/paper/2503.17715/) (2025)
- [CLAP: Concave Linear APproximation for Quadratic Graph Matching](https://mlsanity.com/paper/2410.17101/) (2024)
- [Bridge the Gap Between Visual and Linguistic Comprehension for Generalized Zero-shot Semantic Segmentation](https://mlsanity.com/paper/2503.23806/) (2025)
- [Graph Alignment via Dual-Pass Spectral Encoding and Latent Space Communication](https://mlsanity.com/paper/2509.09597/) (2025)
- [Chaining 2-FWL GNNs for Combinatorial Graph Alignment](https://mlsanity.com/paper/2510.03086/) (2025)
- [Data-driven Projection Generation for Efficiently Solving Heterogeneous Quadratic Programming Problems](https://mlsanity.com/paper/2510.26061/) (2025)
- [Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2609.32661/) (2026)

## Abstract (arXiv)

Recently, deep learning based methods have demonstrated promising results on the graph matching problem, by relying on the descriptive capability of deep features extracted on graph nodes. However, one main limitation with existing deep graph matching (DGM) methods lies in their ignorance of explicit constraint of graph structures, which may lead the model to be trapped into local minimum in training. In this paper, we propose to explicitly formulate pairwise graph structures as a quadratic constraint incorporated into the DGM framework. The quadratic constraint minimizes the pairwise structural discrepancy between graphs, which can reduce the ambiguities brought by only using the extracted CNN features. Moreover, we present a differentiable implementation to the quadratic constrained-optimization such that it is compatible with the unconstrained deep learning optimizer. To give more precise and proper supervision, a well-designed false matching loss against class imbalance is proposed, which can better penalize the false negatives and false positives with less overfitting. Exhaustive experiments demonstrate that our method competitive performance on real-world datasets.