Sharp threshold for alignment of graph databases with Gaussian weights
  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 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 \leq 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^*(i)})_{1 \leq i\leq
n}$ where $(u_i, v_{\pi^*(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.
