Sharp threshold for alignment of graph databases with Gaussian weights. (arXiv:2010.16295v3 [stat.ML] UPDATED)

We study the fundamental limits for reconstruction in weighted graph (or
matrix) database alignment. We consider a model of two graphs where $\pi^*$ is
a planted uniform permutation and all pairs of edge weights $(A_{i,j},
B_{\pi^*(i),\pi^*(j)})_{1 \leq i<j \leq 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^*$:
if $n \rho^2 \geq (4+\epsilon) \log n + \omega(1)$ for …

alignment arxiv databases graph graph databases threshold