# Gaussian Database Alignment and Gaussian Planted Matching

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 5 Jul 2023.

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

- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs](https://mlsanity.com/paper/1805.02349/) (2018)
- [Seeded Graph Matching via Large Neighborhood Statistics](https://mlsanity.com/paper/1807.10262/) (2018)
- [Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universality](https://mlsanity.com/paper/1907.08883/) (2019)
- [Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2007.00533/) (2020)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Impossibility of Partial Recovery in the Graph Alignment Problem](https://mlsanity.com/paper/2102.02685/) (2021)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [Database Alignment with Gaussian Features](https://mlsanity.com/paper/1903.01422/) (2019)
- [The Planted Matching Problem: Phase Transitions and Exact Results](https://mlsanity.com/paper/1912.08880/) (2019)
- [The planted matching problem: Sharp threshold and infinite-order phase transition](https://mlsanity.com/paper/2103.09383/) (2021)
- [A Concentration of Measure Approach to Database De-anonymization](https://mlsanity.com/paper/1901.07655/) (2019)
- [Health Data in an Open World](https://mlsanity.com/paper/1712.05627/) (2017)

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

- [Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery](https://mlsanity.com/paper/2501.02851/) (2025)
- [Attributed Network Alignment: Statistical Limits and Efficient Algorithm](https://mlsanity.com/paper/2604.04365/) (2026)
- [Sharp Statistical Thresholds for Attributed Gaussian Graph Matching](https://mlsanity.com/paper/2603.23305/) (2026)

## Abstract (arXiv)

Database alignment is a variant of the graph alignment problem: Given a pair of anonymized databases containing separate yet correlated features for a set of users, the problem is to identify the correspondence between the features and align the anonymized user sets based on correlation alone. This closely relates to planted matching, where given a bigraph with random weights, the goal is to identify the underlying matching that generated the given weights. We study an instance of the database alignment problem with multivariate Gaussian features and derive results that apply both for database alignment and for planted matching, demonstrating the connection between them. The performance thresholds for database alignment converge to that for planted matching when the dimensionality of the database features is (ω(log n)), where (n) is the size of the alignment, and no individual feature is too strong. The maximum likelihood algorithms for both planted matching and database alignment take the form of a linear program and we study relaxations to better understand the significance of various constraints under various conditions and present achievability and converse bounds. Our results show that the almost-exact alignment threshold for the relaxed algorithms coincide with that of maximum likelihood, while there is a gap between the exact alignment thresholds. Our analysis and results extend to the unbalanced case where one user set is not fully covered by the alignment.