# CLAP: Concave Linear APproximation for Quadratic Graph Matching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 22 Oct 2024.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [SuperPoint: Self-Supervised Interest Point Detection and Description](https://mlsanity.com/paper/1712.07629/) (2017)
- [LoFTR: Detector-Free Local Feature Matching with Transformers](https://mlsanity.com/paper/2104.00680/) (2021)
- [LIFT: Learned Invariant Feature Transform](https://mlsanity.com/paper/1603.09114/) (2016)
- [FLOT: Scene Flow on Point Clouds Guided by Optimal Transport](https://mlsanity.com/paper/2007.11142/) (2020)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [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)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (2021)
- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [RF-Net: An End-to-End Image Matching Network based on Receptive Field](https://mlsanity.com/paper/1906.00604/) (2019)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [A Functional Representation for Graph Matching](https://mlsanity.com/paper/1901.05179/) (2019)
- [KerGM: Kernelized Graph Matching](https://mlsanity.com/paper/1911.11120/) (2019)
- [GLMNet: Graph Learning-Matching Networks for Feature Matching](https://mlsanity.com/paper/1911.07681/) (2019)

## Abstract (arXiv)

Solving point-wise feature correspondence in visual data is a fundamental problem in computer vision. A powerful model that addresses this challenge is to formulate it as graph matching, which entails solving a Quadratic Assignment Problem (QAP) with node-wise and edge-wise constraints. However, solving such a QAP can be both expensive and difficult due to numerous local extreme points. In this work, we introduce a novel linear model and solver designed to accelerate the computation of graph matching. Specifically, we employ a positive semi-definite matrix approximation to establish the structural attribute constraint.We then transform the original QAP into a linear model that is concave for maximization. This model can subsequently be solved using the Sinkhorn optimal transport algorithm, known for its enhanced efficiency and numerical stability compared to existing approaches. Experimental results on the widely used benchmark PascalVOC showcase that our algorithm achieves state-of-the-art performance with significantly improved efficiency. Source code: https://github.com/xmlyqing00/clap