# Deep Probabilistic Graph Matching

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 100 references that are in the map.
- First posted on arXiv 5 Jan 2022.

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

- [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)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [Image Matching across Wide Baselines: From Paper to Practice](https://mlsanity.com/paper/2003.01587/) (2020)
- [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)
- [Skeleton-Based Action Recognition with Multi-Stream Adaptive Graph Convolutional Networks](https://mlsanity.com/paper/1912.06971/) (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)
- [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)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [Dynamic Label Graph Matching for Unsupervised Video Re-Identification](https://mlsanity.com/paper/1709.09297/) (2017)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Sinkhorn Algorithm for Lifted Assignment Problems](https://mlsanity.com/paper/1707.07285/) (2017)
- [Joint Graph Learning and Matching for Semantic Feature Correspondence](https://mlsanity.com/paper/2109.00240/) (2021)
- [Learning Graph Edit Distance by Graph Neural Networks](https://mlsanity.com/paper/2008.07641/) (2020)

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

- [SG-PGM: Partial Graph Matching Network with Semantic Geometric Fusion for 3D Scene Graph Alignment and Its Downstream Tasks](https://mlsanity.com/paper/2403.19474/) (2024)

## Abstract (arXiv)

Most previous learning-based graph matching algorithms solve the textitquadratic assignment problem (QAP) by dropping one or more of the matching constraints and adopting a relaxed assignment solver to obtain sub-optimal correspondences. Such relaxation may actually weaken the original graph matching problem, and in turn hurt the matching performance. In this paper we propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. In particular, we design an affinity-assignment prediction network to jointly learn the pairwise affinity and estimate the node assignments, and we then develop a differentiable solver inspired by the probabilistic perspective of the pairwise affinities. Aiming to obtain better matching results, the probabilistic solver refines the estimated assignments in an iterative manner to impose both discrete and one-to-one matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k), and it outperforms all previous state-of-the-arts on all benchmarks.