# Strong recovery of geometric planted matchings

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2021.

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

- [Random Graph Matching in Geometric Models: the Case of Complete Graphs](https://mlsanity.com/paper/2202.10662/) (2022)
- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [One-Way Matching of Datasets with Low Rank Signals](https://mlsanity.com/paper/2204.13858/) (2022)
- [Seeded graph matching for the correlated Gaussian Wigner model via the projected power method](https://mlsanity.com/paper/2204.04099/) (2022)
- [On Correlation Detection and Alignment Recovery of Gaussian Databases](https://mlsanity.com/paper/2211.01069/) (2022)
- [Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem](https://mlsanity.com/paper/2405.14532/) (2024)
- [Testing Dependency of Unlabeled Databases](https://mlsanity.com/paper/2311.05874/) (2023)
- [Matching Map Recovery with an Unknown Number of Outliers](https://mlsanity.com/paper/2210.13354/) (2022)
- [Robust Point Matching with Distance Profiles](https://mlsanity.com/paper/2312.12641/) (2023)
- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networks](https://mlsanity.com/paper/2402.07340/) (2024)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)

## Abstract (arXiv)

We study the problem of efficiently recovering the matching between an unlabelled collection of n points in ℝd and a small random perturbation of those points. We consider a model where the initial points are i.i.d. standard Gaussian vectors, perturbed by adding i.i.d. Gaussian vectors with variance σ2. In this setting, the maximum likelihood estimator (MLE) can be found in polynomial time as the solution of a linear assignment problem. We establish thresholds on σ2 for the MLE to perfectly recover the planted matching (making no errors) and to strongly recover the planted matching (making o(n) errors) both for d constant and d = d(n) growing arbitrarily. Between these two thresholds, we show that the MLE makes nδ + o(1) errors for an explicit δ ∈ (0, 1). These results extend to the geometric setting a recent line of work on recovering matchings planted in random graphs with independently-weighted edges. Our proof techniques rely on careful analysis of the combinatorial structure of partial matchings in large, weakly dependent random graphs using the first and second moment methods.