# KerGM: Kernelized Graph Matching

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2019.

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

- [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)
- [Bilateral Cross-Modality Graph Matching Attention for Feature Fusion in Visual Question Answering](https://mlsanity.com/paper/2112.07270/) (2021)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [An Exact Hypergraph Matching Algorithm for Nuclear Identification in Embryonic Caenorhabditis elegans](https://mlsanity.com/paper/2104.10003/) (2021)
- [A Semi-automatic Cell Tracking Process Towards Completing the 4D Atlas of C. elegans Development](https://mlsanity.com/paper/2207.13611/) (2022)
- [CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment](https://mlsanity.com/paper/2208.10682/) (2022)
- [Population-wise Labeling of Sulcal Graphs using Multi-graph Matching](https://mlsanity.com/paper/2301.13532/) (2023)
- [Multiple Hypothesis Hypergraph Tracking for Posture Identification in Embryonic Caenorhabditis elegans](https://mlsanity.com/paper/2111.06425/) (2021)
- [Improved Algorithm for the Network Alignment Problem with Application to Binary Diffing](https://mlsanity.com/paper/2112.15336/) (2021)
- [Training Free Graph Neural Networks for Graph Matching](https://mlsanity.com/paper/2201.05349/) (2022)
- [CLAP: Concave Linear APproximation for Quadratic Graph Matching](https://mlsanity.com/paper/2410.17101/) (2024)
- [Matching and mixing: Matchability of graphs under Markovian error](https://mlsanity.com/paper/2601.20020/) (2026)

## Abstract (arXiv)

Graph matching plays a central role in such fields as computer vision, pattern recognition, and bioinformatics. Graph matching problems can be cast as two types of quadratic assignment problems (QAPs): Koopmans-Beckmann's QAP or Lawler's QAP. In our paper, we provide a unifying view for these two problems by introducing new rules for array operations in Hilbert spaces. Consequently, Lawler's QAP can be considered as the Koopmans-Beckmann's alignment between two arrays in reproducing kernel Hilbert spaces (RKHS), making it possible to efficiently solve the problem without computing a huge affinity matrix. Furthermore, we develop the entropy-regularized Frank-Wolfe (EnFW) algorithm for optimizing QAPs, which has the same convergence rate as the original FW algorithm while dramatically reducing the computational burden for each outer iteration. We conduct extensive experiments to evaluate our approach, and show that our algorithm significantly outperforms the state-of-the-art in both matching accuracy and scalability.