# Zero-Assignment Constraint for Graph Matching with Outliers

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2020.

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

- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [Correspondence-Free Non-Rigid Point Set Registration Using Unsupervised Clustering Analysis](https://mlsanity.com/paper/2406.18817/) (2024)
- [One-shot Key Information Extraction from Document with Deep Partial Graph Matching](https://mlsanity.com/paper/2109.13967/) (2021)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (2022)
- [SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm](https://mlsanity.com/paper/2202.02797/) (2022)

## Abstract (arXiv)

Graph matching (GM), as a longstanding problem in computer vision and pattern recognition, still suffers from numerous cluttered outliers in practical applications. To address this issue, we present the zero-assignment constraint (ZAC) for approaching the graph matching problem in the presence of outliers. The underlying idea is to suppress the matchings of outliers by assigning zero-valued vectors to the potential outliers in the obtained optimal correspondence matrix. We provide elaborate theoretical analysis to the problem, i.e., GM with ZAC, and figure out that the GM problem with and without outliers are intrinsically different, which enables us to put forward a sufficient condition to construct valid and reasonable objective function. Consequently, we design an efficient outlier-robust algorithm to significantly reduce the incorrect or redundant matchings caused by numerous outliers. Extensive experiments demonstrate that our method can achieve the state-of-the-art performance in terms of accuracy and efficiency, especially in the presence of numerous outliers.