# Kernelized multi-graph matching

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 11 Oct 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)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [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)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [Higher-order Projected Power Iterations for Scalable Multi-Matching](https://mlsanity.com/paper/1811.10541/) (2018)
- [Near-Optimal Performance Bounds for Orthogonal and Permutation Group Synchronization via Spectral Methods](https://mlsanity.com/paper/2008.05341/) (2020)
- [Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence](https://mlsanity.com/paper/1811.11829/) (2018)
- [Convex Relaxations for Permutation Problems](https://mlsanity.com/paper/1306.4805/) (2013)
- [KerGM: Kernelized Graph Matching](https://mlsanity.com/paper/1911.11120/) (2019)
- [A General Multi-Graph Matching Approach via Graduated Consistency-regularized Boosting](https://mlsanity.com/paper/1502.05840/) (2015)
- [Robust Multi-object Matching via Iterative Reweighting of the Graph Connection Laplacian](https://mlsanity.com/paper/2006.06658/) (2020)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)
- [Improved Performance Guarantees for Orthogonal Group Synchronization via Generalized Power Method](https://mlsanity.com/paper/2012.00470/) (2020)
- [Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation](https://mlsanity.com/paper/2110.00053/) (2021)

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

- [CURSOR: Scalable Mixed-Order Hypergraph Matching with CUR Decomposition](https://mlsanity.com/paper/2402.16594/) (2024)
- [MIXER: Multiattribute, Multiway Fusion of Uncertain Pairwise Affinities](https://mlsanity.com/paper/2210.08360/) (2022)
- [Population-wise Labeling of Sulcal Graphs using Multi-graph Matching](https://mlsanity.com/paper/2301.13532/) (2023)

## Abstract (arXiv)

Multigraph matching is a recent variant of the graph matching problem. In this framework, the optimization procedure considers several graphs and enforces the consistency of the matches along the graphs. This constraint can be formalized as a cycle consistency across the pairwise permutation matrices, which implies the definition of a universe of vertex~citeppachauri2013solving. The label of each vertex is encoded by a sparse vector and the dimension of this space corresponds to the rank of the bulk permutation matrix, the matrix built from the aggregation of all the pairwise permutation matrices. The matching problem can then be formulated as a non-convex quadratic optimization problem (QAP) under constraints imposed on the rank and the permutations. In this paper, we introduce a novel kernelized multigraph matching technique that handles vectors of attributes on both the vertices and edges of the graphs, while maintaining a low memory usage. We solve the QAP problem using a projected power optimization approach and propose several projectors leading to improved stability of the results. We provide several experiments showing that our method is competitive against other unsupervised methods.