Sharp threshold for alignment of graph databases with Gaussian weights

Abstract

We study the fundamental limits for reconstruction in weighted graph (or matrix) database alignment. We consider a model of two graphs where ${\pi }^{\ast }$ is a planted uniform permutation and all pairs of edge weights $(A_{i,j},B_{{\pi }^{\ast }(i),{\pi }^{\ast }(j)}{)}_{1\le i<j\le n}$ are i.i.d. pairs of Gaussian variables with zero mean, unit variance and correlation parameter $\rho \in [0,1]$. We prove that there is a sharp threshold for exact recovery of ${\pi }^{\ast }$: if $n{\rho }^2\ge (4+\epsilon )\log n+\omega (1)$ for some $\epsilon >0$, there is an estimator $\hat{\pi }$ -- namely the MAP estimator -- based on the observation of databases $A,B$ that achieves exact reconstruction with high probability. Conversely, if $n{\rho }^2\le 4\log n-\log \log n-\omega (1)$, then any estimator $\hat{\pi }$ verifies $\hat{\pi }=\pi$ with probability $o(1)$. This result shows that the information-theoretic threshold for exact recovery is the same as the one obtained for detection in a recent work by Wu et al. (2020): in other words, for Gaussian weighted graph alignment, the problem of reconstruction is not more difficult than that of detection. Though the reconstruction task was already well understood for vector-shaped database alignment (that is taking signal of the form $(u_i,v_{{\pi }^{\ast }(i)}{)}_{1\le i\le n}$ where $(u_i,v_{{\pi }^{\ast }(i)})$ are i.i.d. pairs in ${\mathbb{R}}^{d_u}\times {\mathbb{R}}^{d_v}$), its formulation for graph (or matrix) databases brings a drastically different problem for which the hard phase is conjectured to be wide. The proofs build upon the analysis of the MAP estimator and the second moment method, together with the study of the correlation structure of energies of permutations.

arXiv comment18 pages, 2 figures. Latest version: typos corrected

References in corpus (6)

• De-anonymizing Social Networks
• Efficient random graph matching via degree profiles
• Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
• Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
• Testing correlation of unlabeled random graphs
• Spectral Alignment of Correlated Gaussian matrices

Cited by in corpus (3)

• Aligning random graphs with a sub-tree similarity message-passing algorithm
• Impossibility of Partial Recovery in the Graph Alignment Problem
• Graph Matching via convex relaxation to the simplex