Sharp threshold for alignment of graph databases with Gaussian weights

arXiv2010.16295MaRDI QIDQ6352654

Luca Ganassali

Publication date: 30 October 2020

Abstract: We study the fundamental limits for reconstruction in weighted graph (or matrix) database alignment. We consider a model of two graphs where $p{i}^{*}$ is a planted uniform permutation and all pairs of edge weights $(A_{i,j},B_{p{i}^{*}(i),p{i}^{*}(j)}{)}_{1leqi<jleqn}$ are i.i.d. pairs of Gaussian variables with zero mean, unit variance and correlation parameter $hoin[0,1]$. We prove that there is a sharp threshold for exact recovery of $p{i}^{*}$: if $nh{o}^{2}geq(4+epsilon)logn+omega(1)$ for some $epsilon>0$, there is an estimator $hatpi$ -- namely the MAP estimator -- based on the observation of databases $A,B$ that achieves exact reconstruction with high probability. Conversely, if $nh{o}^{2}leq4logn-loglogn-omega(1)$, then any estimator $hatpi$ verifies $hatpi=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_{p{i}^{*}(i)}{)}_{1leqileqn}$ where $(u_i,v_{p{i}^{*}(i)})$ are i.i.d. pairs in $mathbb{R}^{d_u}imesmathbb{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.

This page was built for publication: Sharp threshold for alignment of graph databases with Gaussian weights

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6352654)