# Phase Transitions in the Detection of Correlated Databases

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 7 Feb 2023.

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

- [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)
- [Testing correlation of unlabeled random graphs](https://mlsanity.com/paper/2008.10097/) (2020)
- [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)

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

- [Testing Dependency of Unlabeled Databases](https://mlsanity.com/paper/2311.05874/) (2023)
- [Detection of Correlated Random Vectors](https://mlsanity.com/paper/2401.13429/) (2024)
- [Testing Dependency of Weighted Random Graphs](https://mlsanity.com/paper/2409.14870/) (2024)

## Abstract (arXiv)

We study the problem of detecting the correlation between two Gaussian databases mathsfX∈ℝn× d and mathsfYn× d, each composed of n users with d features. This problem is relevant in the analysis of social media, computational biology, etc. We formulate this as a hypothesis testing problem: under the null hypothesis, these two databases are statistically independent. Under the alternative, however, there exists an unknown permutation σ over the set of n users (or, row permutation), such that mathsfX is ρ-correlated with mathsfYσ, a permuted version of mathsfY. We determine sharp thresholds at which optimal testing exhibits a phase transition, depending on the asymptotic regime of n and d. Specifically, we prove that if ρ2d→0, as d→∞, then weak detection (performing slightly better than random guessing) is statistically impossible, irrespectively of the value of n. This compliments the performance of a simple test that thresholds the sum all entries of mathsfXTmathsfY. Furthermore, when d is fixed, we prove that strong detection (vanishing error probability) is impossible for any ρ<ρ^star, where ρ^star is an explicit function of d, while weak detection is again impossible as long as ρ2d→0. These results close significant gaps in current recent related studies.