# Stochastic Iterative Graph Matching

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [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)
- [IMRAM: Iterative Matching with Recurrent Attention Memory for Cross-Modal Image-Text Retrieval](https://mlsanity.com/paper/2003.03772/) (2020)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [Iterative Amortized Inference](https://mlsanity.com/paper/1807.09356/) (2018)
- [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)
- [Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network](https://mlsanity.com/paper/1905.11605/) (2019)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [On the challenges of learning with inference networks on sparse, high-dimensional data](https://mlsanity.com/paper/1710.06085/) (2017)
- [Iterative Amortized Policy Optimization](https://mlsanity.com/paper/2010.10670/) (2020)
- [Reparameterizing the Birkhoff Polytope for Variational Permutation Inference](https://mlsanity.com/paper/1710.09508/) (2017)

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

- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [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)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching](https://mlsanity.com/paper/2301.02780/) (2023)
- [Ensemble Quadratic Assignment Network for Graph Matching](https://mlsanity.com/paper/2403.06457/) (2024)
- [Unsupervised Manifold Alignment with Joint Multidimensional Scaling](https://mlsanity.com/paper/2207.02968/) (2022)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning](https://mlsanity.com/paper/2210.10643/) (2022)
- [AMatFormer: Efficient Feature Matching via Anchor Matching Transformer](https://mlsanity.com/paper/2305.19205/) (2023)
- [Learning Partial Graph Matching via Optimal Partial Transport](https://mlsanity.com/paper/2410.16718/) (2024)

## Abstract (arXiv)

Recent works leveraging Graph Neural Networks to approach graph matching tasks have shown promising results. Recent progress in learning discrete distributions poses new opportunities for learning graph matching models. In this work, we propose a new model, Stochastic Iterative Graph MAtching (SIGMA), to address the graph matching problem. Our model defines a distribution of matchings for a graph pair so the model can explore a wide range of possible matchings. We further introduce a novel multi-step matching procedure, which learns how to refine a graph pair's matching results incrementally. The model also includes dummy nodes so that the model does not have to find matchings for nodes without correspondence. We fit this model to data via scalable stochastic optimization. We conduct extensive experiments across synthetic graph datasets as well as biochemistry and computer vision applications. Across all tasks, our results show that SIGMA can produce significantly improved graph matching results compared to state-of-the-art models. Ablation studies verify that each of our components (stochastic training, iterative matching, and dummy nodes) offers noticeable improvement.