Luca Ganassali
email: luca.ganassali@inria.fr.

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 π * is a planted uniform permutation and all pairs of edge weights (Ai,j, B π * (i),π * (j) ) 1≤i<j≤n are i.i.d. pairs of Gaussian variables with zero mean, unit variance and correlation parameter ρ ∈ [0, 1]. We prove that there is a sharp threshold for exact recovery of π * : if nρ 2 ≥ (4 + ε) log n + ω(1) for some ε > 0, there is an estimator π -namely the MAP estimator -based on the observation of databases A, B that achieves exact reconstruction with high probability. Conversely, if nρ 2 ≤ 4 log n -log log nω(1), then any estimator π verifies π = π 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 [WXY20]: 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 (ui, v π * (i) ) 1≤i≤n where (ui, v π * (i) ) are i.i.d. pairs in R du × R dv ), 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.

Introduction

Aligning databases We address the following problem: suppose that we have two databases consisting in weighted graphs represented by their adjacency matrices A and B. For simplicity, assume that the two graphs have same size and that each individual appears in both graphs. For a given individual, its attached signal consists in weighted edges with all other users. Across databases, edges that correspond to pairs of matched individuals are correlated. We consider the following question: if the graphs are shown unlabeled (that is, if users are anonymized), is it possible to recover the corresponding matching between databases by aligning them at the sight of their correlation structure?

Intuitively, when the matrices are correlated enough, one can learn the true matching between individuals present in the databases. In this study we investigate the precise conditions on correlation under which exact reconstruction (or perfect de-anonymization) is feasible with high probability.

De-anonymization problems aroused great interest when [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF] were able to de-anonymize an unlabeled dataset of film ratings (namely, the Netflix prize dataset) with the observation of a publicly available database (namely the Internet Movie Database), using correlations between the ratings. Since then, they have been studied in recent literature, in several versions and reformulations. The range of applications has been widened to quantifying privacy issues related to databases ( [START_REF] Dwork | Differential privacy: A survey of results[END_REF]) or social networks ( [START_REF] Narayanan | De-anonymizing social networks[END_REF]).

Widespread attention was given on the graph alignment problem, focusing on more geometrical databases ([CK17, CKMP18, DMWX18, FMWX19a, FMWX19b, GM20]). Lots of other natural applications can be mentioned, such as pattern recognition in image processing ( [START_REF] Berg | Shape matching and object recognition using low distortion correspondences[END_REF][START_REF] Cour | Balanced graph matching[END_REF]), aligning protein interaction networks in computational biology ( [START_REF] Singh | Global alignment of multiple protein interaction networks with application to functional orthology detection[END_REF]) or performing ontology alignment in natural language processing [START_REF] Aria | Robust textual inference via graph matching[END_REF]).

Vector-shaped and graph-shaped databases From the theoretical point of view, fundamental limits for the deanonymisation problem are now well understood when data only consists in vectors u, v of given sizes n ([CMK18, ECK19]), that is when each user has its own signal, regardless of its connections with others. In this setting, the problem can be phrased in terms of a Linear Assigment Problem (LAP):

arg max Π Πu, v , (1)
where the maximum runs over all permutation matrices of size n. Even if greedy optimization is easily seen to be exponential-time, LAP can be solved efficiently in O(n 3 ) steps using the classical Hungarian algorithm ( [START_REF] Kuhn | The hungarian method for the assignment problem[END_REF]).

Another related problem is that of linear regression with an unknown permutation, studied in [START_REF] Pananjady | Linear Regression with an Unknown Permutation: Statistical and Computational Limits[END_REF]: this time, one observes y = Π * Ax * + w, where x * ∈ R d is an unknown vector, Π * is an unknown n × n permutation matrix, and w ∈ R n is additive Gaussian noise. Here again, the permutation Π * applies only on the left side of A, which corresponds to row permutation.

On the other hand, when the databases are graphs, the problem is different and can be phrased this time in terms of a Quadratic Assigment Problem (QAP):

arg max Π A, ΠBΠ T .
(2)

A significant difference with the previous vector-shaped setting is that this problem is known to be NP-hard in the worst case, as well as some of its approximations ([MMS14, PRW94]). In the case where the signal lies in the graph structure itself -that is, when

(A i,j , B π * (i),π * (j) ) 1≤i<j≤n
are correlated pairs of Bernoulli variables -recent work ([CK17, CKMP18]) showed that there exists a sharp threshold for exact recovery, where the signal-to-noise ratio can be expressed in the correlated Erdős-Rényi model in terms of the size n of both graphs, the marginal edge probability p and the correlation parameter s between edges of the two graphs. Indeed, they established that exact (resp. almost exact) reconstruction is feasible with high probability if and only if nps ≥ log n + ω(1) (resp. nps ≥ ω(1)). When the signal is sparser, e.g. np = Θ(1), the problem of partial graph alignment (that is, recovering only a positive fraction of vertices) has been recently explored algorithmically ( [START_REF] Ganassali | From tree matching to sparse graph alignment[END_REF]) and theoretically ([HM20]).

Model of Gaussian Wigner matrices

This paper focuses on the case where signal lies in weights on edges between all pairs of nodes. In order to rigorously analyze the fundamental limits of our reconstruction problem, we will work in a probabilistic setting. The correlated Gaussian Wigner model is first introduced by [DMWX18] as a standard model for random graph alignment, and has been further investigated for its own sake in recent work ([FMWX19a, GLM19, WXY20]). Assume that the weighted adjacency matrices A and B of the two graphs G and G are symmetric, and sampled as follows: first draw the planted permutation π * uniformly at random in S n . Then all pairs of edge weights (A i,j , B π * (i),π * (j) ) 1≤i<j≤n are i.i.d. couples of normal variables with zero mean, unit variance and correlation parameter ρ ∈ [0, 1]. Since all Gaussian variables are independent from π * , matrix B can also be drawn from A as follows:

B = ρ • Π * T AΠ * + 1 -ρ 2 • H, (3)
where H is an independent copy of A, and Π * is the n × n matrix representation of permutation π * , that is Π * i,j = 1 j=π * (i) .

Figure 1: A sample from model (3) with n = 5. For representation, edges are colored according to their weights, and the underlying alignment is u → u for u ∈ {1, 2, 3, 4, 5}.

Detection problem A most recent paper ([WXY20]

) studies fundamental limits for detection, both in correlated Gaussian weighted and correlated Erdős-Rényi graphs. This time, the problem is as follows: given A, B, are we able to distinguish between model (3) and a null model, where the two graphs are just independent Gaussian weighted graphs? Intuitively, this problem is less demanding than that of exact alignment, since the task is to detect -wherever in the graph -the presence of a hidden planted alignment. Under the same model (3), Y. Wu, J. Xu and S. Yu showed that detection is feasible with high probability if nρ 2 ≥ 4 log n, whereas it is impossible if nρ 2 ≤ (4ε) log n for some ε > 0. Their study builds on an analysis of the likelihood ratio -as often in detection problems. The contribution of this paper is to show that this sharp detection threshold is also that of exact reconstruction. Interestingly, for Gaussian weighted graph alignment, the problem of reconstruction is in fact not more difficult than that of detection. After this paper was completed, the author was made aware of recent and independent work conducted by [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF], which also obtains -among other things -the results of this paper, albeit with different proof techniques.

Main results

In the sequel, we work with the correlated Gaussian Wigner model described in (3), and establish the precise (sharp) threshold for exact recovery of π * in this model.

Theorem 1 (Achievability part). If for n large enough

ρ 2 ≥ (4 + ε) log n n (4)
for some ε > 0, then there is an estimator (namely, the MAP estimator) π of π given A, B such that π = π * with probability 1 -o(1).

Theorem 2 (Converse part). Conversely, if

ρ 2 ≤ 4 log n -log log n -ω(1) n (5)
then any estimator π of π given A, B verifies π = π * with probability o(1).

Computational limits of exact recovery

For the correlated Gaussian Wigner model (3), several algorithms have been studied, usually as a first step in order to analyze further graph alignment algorithms. The state-of-the-art polynomial-time algorithms are either based on degree profiles ([DMWX18]), or on a spectral method ( [START_REF] Zhou Fan | Spectral graph matching and regularized quadratic relaxations I: The gaussian model[END_REF]). In both cases, these methods require the noise parameter 1 -ρ 2 to be O log -1 n . [GLM19] study a simpler algorithm with lower computational complexity (O(n 2 ) versus O(n 3 )), requiring 1 -ρ 2 to be O(n -7/6 ). In any case, ρ needs to tend to 1, and the regimes in which these methods work well are far from the fundamental limits established in this paper. The present paper thus corroborates the idea that matrix alignment may be computationally hard even in the feasibility regime. In other words, the hard phase can be conjectured to be really wide for this reconstruction problem. Proving a result of that form however remains a very thorny question.

Paper organization

We first define our notations at the beginning of Section 1, and then establish a control on correlations between energies of permutations, using Hanson-Wright inequality. The achievability result is proved in Section 2: after showing that the classical first moment method fails, we take advantage of the correlation structure established before to handle the sharp bound. Then, second moment method is applied in Section 3 to show that lots of small perturbations of the true underlying permutation have lower energies, establishing the converse bound. Finally, some additional proofs are deferred to Appendix A. The proof techniques are not far from those used by [START_REF] Osman Emre Dai | Database Alignment with Gaussian Features[END_REF], the main novelty being the use of correlation of energies, which is essential to both achievability and impossibility result.

1 Preliminaries

Definitions and notations

For any positive integer n, let [n] = {1, 2, . . . , n}. For two positive sequences {u n } and {v n }, denote

u n = O(v n ) if there exists C > 0 such that u n ≤ Cv n for all n.
We will also write

u n = o(v n ) (resp. u n = ω(v n )) if u n /v n → 0 (resp. v n /u n → 0).
All limits considered are taken when n → ∞.

Linear algebra

We work with the canonical euclidean norm • on R n , and •, • the canonical inner product on R n or R n×n . For any n × n matrix M with real entries, its Frobenius norm M F and its operator norm M op are defined as follows:

M F :=   1≤i,j≤n A 2 i,j   1/2
and M op := sup

X∈R n \{0} M X X .
Note that for any normal matrix (that is, if

M T M = M M T ), then M op equals ρ(M ), the spectral radius of M .
Probability When working with model (3), we will denote by P A (resp. E A ) the conditional probability (resp. the conditional expectation) with respect to the random matrix A. Throughout the paper, N (µ, v) denotes a Gaussian variable (resp. vector) with mean µ and variance (resp. covariance matrix) v. Such a Gaussian variable (resp. vector) is called standard if µ = 0 and v = 1 (resp. v is the identity matrix). We say that an event A n happens with high probability (w.h.p) if

P(A n ) → 1 when n → ∞.
Permutations We denote by S m the set of permutations of [m]. To any permutation σ ∈ S m , we can associate its m × m matrix representation Σ defined by Σ i,j = 1 j=σ(i) . Define F σ the set of fixed points of σ:

F σ := {i ∈ [m], σ(i) = i} , (6)
and denote f σ := F σ . Similarly, we define the set of unfixed points of σ:

D σ := [m] \ F σ = {i ∈ [m], σ(i) = i} , (7)
and we denote d σ := D σ . For any d ∈ {0, . . . , m} we define S m,d the set of permutations of S m with exactly d unfixed points. Note that S m,1 = 0 and that we have the inequality

S m,d = m m -d {σ ∈ S d , F σ = 0} ≤ m m -d d! ≤ m d . (8)
Similarity between two permutations σ, σ ∈ S n is measured by their overlap:

ov(σ, σ ) := 1 n n i=1 1 σ(i)=σ (i) = 1 n f σ -1 •σ .
Observe that on a graph of size n, each permutation σ of the vertices [n] has a natural extension to a canonical permutation on edges σ E : [n] 2 → [n] 2 defined as follows:

σ E : e = {i, j} → σ E (e) = {σ(i), σ(j)} .
Note that the mapping σ → σ E is one-to-one as soon as n ≥ 3, since for all i ∈ [n] and j = j ∈

[n] \ {i}, edges σ E ({i, j}) and σ E ({i, j }) have only one node in common, which is σ(i). We will use the notation

F E σ = F σ E (resp. D E σ = D σ E ) the set of fixed edges (resp. unfixed edges) of σ. Similarly we denote f E σ = f σ E and f E σ := d σ E , for brievity. Note that d E
σ and are d σ are closely tied, since for all σ ∈ S n , we have the inequality

d σ n - d σ 2 ≤ d E σ ≤ d σ n - d σ -1 2 . ( 9
)
Indeed, observe that (i) the number of fixed edges is at least the number of pairs of fixed points, and

(ii) the number of fixed edges is exactly the number of pairs of fixed points plus the number of pairs (i, j), i < j that are exchanged by σ (that is, the number of transpositions), this number being at most d σ /2.

These remarks give that

n -d σ 2 ≤ n 2 -d E σ ≤ n -d σ 2 + d σ 2 ,
which directly implies (9).

Remark 1. Note that inequality (9) gives the almost sure equivalents

d E σ ∼ d σ n when d σ = o(n), and d E σ ∼ 1 2 α(2 -α)n 2 when d σ = αn. In any case, d E σ ∈ 1 2 d σ n, d σ n .

MAP estimation, relative energy of permutations

Since π * is uniformly chosen, we work in a Bayesian setting: let us evaluate the posterior probability density of π * given A, B:

p π * |A,B (π|a, b) ∝ p π * ,A,B (π, a, b) ∝ exp   - 1 2(1 -ρ 2 ) 1≤i<j≤n B π(i),π(j) -ρA i,j 2   ,
where ∝ indicates equality up to some factors that do not depend on σ. Define the loss function

L(π, A, B) := 1≤i<j≤n B π(i),π(j) -ρA i,j 2 . ( 10
)
This loss function can also be viewed as the energy associated with permutation π. Note that the posterior distribution is a Gibbs measure corresponding to this energy L, with inverse temperature β = 1 2(1-ρ 2 ) . The MAP (maximum a posteriori) estimator is thus

πMAP := arg max π p π * |A,B (π|A, B) = arg min π L(π, A, B), (11)
where the minimum is taken over all permutations π ∈ S n . The above formulation (11) is standard in the literature of graph and matrix alignment and meets the classical QAP formulation (2), since arg min

π L(π, A, B) = arg max Π A, ΠBΠ T .
Theory from Bayesian optimal estimation guarantees that the best possible estimator for our exact reconstruction problem, in the Bayes risk sense, is πMAP . Thus, if MAP estimator fails with high probability, then no estimator can succeed. This is why this estimator is often studied in exact reconstruction problems, as already done in previous works ([CK17, CMK18, ECK19]).

From now on we work conditionally on π * which can always be assumed to be id without loss of generality. More precisely, we will make the variable change σ = π * • π -1 ; writing B as a function of σ, A and H, (10) becomes

L(σ, A, H) = ρ 2 1≤i<j≤n A i,j -A σ(i),σ(j) 2 -2ρ 1 -ρ 2 1≤i<j≤n H i,j A i,j -A σ(i),σ(j) + (1 -ρ 2 ) 1≤i<j≤n H 2 i,j .
The loss function L applied to the ground truth π = π * -that is σ = id -gives the energy reference (1 -ρ 2 ) 1≤i<j≤n H 2 i,j . In order to compare any π with π * -or any σ with id -we further define the relative energy of a permutation σ ∈ S n :

δ(σ) := L(σ, A, H) -L(id, A, H) = ρ 2 1≤i<j≤n A i,j -A σ(i),σ(j) 2 -2ρ 1 -ρ 2 1≤i<j≤n H i,j A i,j -A σ(i),σ(j) . (12)
We next omit in our notations the dependency on A and H of δ(σ).

Remark 2. This relative energy δ, also introduced by [START_REF] Cullina | Exact alignment recovery for correlated Erdős-Rényi graphs[END_REF] for Erdős-Rényi graph alignment, is a measurement of the quality of a proposed alignment: δ(σ) ≤ 0 means that σ -1 • π * is a better alignment than π * for A and B in the posterior sense. A crucial set is then

Q := {σ ∈ S n , δ(σ) ≤ 0} .
Points of Q are alignments on which the posterior distribution puts important weights -at least greater weights than that of the ground truth -or equivalently points of low energy. Note that id ∈ Q.

In view of (12), conditionally on A, δ(σ) is as follows:

δ(σ) = ρ 2 v σ -2ρ 1 -ρ 2 X σ , (13)
where

v σ := 1≤i<j≤n A i,j -A σ(i),σ(j) 2 ,
and X = (X σ ) σ∈Sn is a Gaussian vector, centered, with covariance given by Cov

(X σ , X σ ) = 1≤i<j≤n A i,j -A σ(i),σ(j) A i,j -A σ (i),σ (j) := c σ,σ .
Note that for all σ ∈ S n , c σ,σ = v σ . Elaborating on the correlation structure of these relative energies is the object of the end of this section.

Control of covariance structure of relative energies

For all σ, σ ∈ S n , c σ,σ can be written as follows

c σ,σ = e∈( [n]
2 )

A e -A σ E (e) A e -A σ E (e)
and satisfies

E [c σ,σ ] = (D E σ ∩ D E σ ) + (D E σ ∩ D E σ ∩ F E σ -1 •σ ). In particular, E [v σ ] = d E σ + d E σ = 2d E σ .
Random variables c σ,σ only depend on the entries of A, which are Gaussian. Moreover, c σ,σ being a quadratic form evaluated on a Gaussian vector, it can therefore be controlled using Hanson-Wright inequality: Lemma 1.1 (Hanson-Wright inequality ([HW71])). Let X be a standard Gaussian vector, and M a deterministic matrix. Then there exists a universal constant c > 0 such that with probability at least 1-2δ:

X T M X -TrM ≤ c M F log(1/δ) + M op log(1/δ) . (14)
We refer to [START_REF] Hanson | A bound on tail probabilities for quadratic forms in independent random variables[END_REF] for a proof. Inequality (14) used in our context leads to the following Corollary 1.1. There exists a universal constant C > 0 such that with high probability, for every d ∈ {2, . . . , n}, for all σ, σ ∈ S n,d ,

c σ,σ -(D E σ ∩ D E σ ) -(D E σ ∩ D E σ ∩ F E σ -1 •σ ) ≤ Cd n log n.
Proof. We first make the following observation: for any σ, σ ∈ S n ,

c σ,σ = e A e -A σ(e) A e -A σ (e) = A T (I N -Σ) T (I N -Σ )A,
where A = (A e ) e is viewed as a standard Gaussian vector of size N = n 2 , and Σ (resp. Σ ) is the N × N permutation matrix associated with σ E (resp. σ E ). Note that

Tr((I N -Σ) T (I N -Σ )) = N -f E σ -f E σ + f E σ -1 •σ (a) = (D E σ ∩ D E σ ) + (D E σ ∩ D E σ ∩ F E σ -1 •σ ),
where (a) is obtained by noticing that

(D E σ ∩ D E σ ) + (D E σ ∩ D E σ ∩ F E σ -1 •σ ) = d E σ + d E σ -(D E σ ∪ D E σ ) + f E σ -1 •σ -(F E σ ∪ F E σ )
and that

(D E σ ∪ D E σ ) + (F E σ ∪ F E σ ) = N.
For a fixed d and σ, σ ∈ S n,d , one has

(I N -Σ) T (I N -Σ ) F ≤ (I N -Σ ) F + Σ T (I N -Σ ) F = 2 (I N -Σ ) F ≤ 2 2d E σ ≤ 2 √ 2dn,
where we used (9) in the last step. One also has

(I N -Σ) T (I N -Σ ) op ≤ ρ(I N -Σ) × ρ(I N -Σ ) ≤ 2 × 2 = 4.
Taking δ = n -(2d+2) , Lemma 1.1 gives that with probability at least 1 -2δ,

c σ,σ -(D E σ ∩ D E σ ) -(D E σ ∩ D E σ ∩ F E σ -1 •σ ) ≤ c 2 √ 2 d(2d + 2) n log n + 4(2d + 2) log n ≤ Cd n log n, (15)
for some universal constant C > 0. The proof is concluded by checking that this inequality holds w.h.p. for all d and σ, σ ∈ S n,d : the probability that at least one pair (σ, σ ) contradicts ( 15) is upper bounded by n × ( S n,d ) 2 × 2δ ≤ 2n 1+2d-2d-2 = o(1).

In the rest of the paper we define the event

A := ∀d ∈ [n], ∀σ, σ ∈ S n,d , c σ,σ -(D E σ ∩ D E σ ) -(D E σ ∩ D E σ ∩ F E σ -1 •σ ) ≤ Cd n log n , (16)

Achievability result

In this section, we establish Theorem 1.

Failure of first moment method

For the achievability result, the first strategy is to use the union bound (or first moment method) to show that under condition (4) of Theorem 1,

P (MAP fails) = P (π MAP = π) = o(1).
As described hereafter, this naive method does not give the correct bound. Indeed, let us evaluate P (δ(σ) ≤ 0) for a given σ = id. In view of the conditional distribution (13) of δ(σ) we have

P (δ(σ) ≤ 0) = E E A 1 δ(σ)≤0 = E P A ρ 2 v σ -2ρ 1 -ρ 2 X σ ≤ 0 = E P A ρ 2 v σ -2ρ 1 -ρ 2 √ v σ • N (0, 1) ≤ 0 = E P A N (0, 1) ≥ ρ √ v σ 2 1 -ρ 2 ≤ E exp - ρ 2 8(1 -ρ 2 ) v σ ,
where we used standard Gaussian concentration in the last inequality: P (N (0, 1) ≥ t) ≤ exp(-t 2 /2). Note that on event A defined in (16) and inequality (9),

∀d ∈ [n], ∀σ ∈ S n,d , v σ ≥ 2d E σ -Cd σ n log n ≥ d E σ (2 -2ε n ) ,
setting ε n = 2C log n/n. Union bound then gives

P (MAP fails) ≤ P (∃σ ∈ S n \ {id} , δ(σ) ≤ 0) ≤ o(1) + σ∈Sn\{id} E exp - ρ 2 8(1 -ρ 2 ) v σ 1 A ≤ o(1) + σ∈Sn\{id} exp - ρ 2 8(1 -ρ 2 ) (2 -2ε n )d E σ ≤ o(1) + σ∈Sn\{id} exp - ρ 2 4 (1 -ε n )d E σ ,
where we used 1/(1 -ρ 2 ) > 1 in the last step. Let us now study the last sum, distinguishing the terms according to d := d σ :

• As long as d = o(n), by Remark 1, the terms behave like exp -

ρ 2 4 (1 -ε n )dn . By (8), log S n,d ≤ d log n so the partial sum is small if ρ 2 4 (1 -ε n )n -log n > 0,
which gives the necessary condition ρ 2 ≥ 4 log n n . • However, the situation is different when it comes to large values of d. For instance, let us study the contribution of derangements to the sum (that is, σ such that d σ = n). Note that these derangements are very numerous (their number is ∼ e -1 n!). Again by Remark 1, their contribution is thus of order

e -1 n! exp ρ 2 (1 -ε n )n 2 /8(1 -o(1)) = exp n log n -ρ 2 n 2 /8 (1 -o(1)) ,
which gives a more restrictive condition: ρ 2 ≥ 8 log n n . As seen here-above, this naive first moment method enables to ensure feasibility of exact reconstruction only in the regime where ρ 2 ≥ 8 log n n , which is not the optimal one. This bound is actually quite rough here, because the variables are substantially correlated when d gets large and their contributions make the first moment explode. The next section takes advantage of these correlations in order to get access to the sharp bound.

Improving the first moment method with correlations.

For all d ∈ {2, . . . , n}, define E d the event:

E d := {∃σ ∈ S n,d , δ(σ) ≤ 0} .
In this Section we will assume that

ρ ≥ (2 + ε) log n n ,
for some ε > 0. Recall that we work on the event A defined in ( 16), and that conditionally on entries of matrix A, we can write

δ(σ) = ρ 2 v σ -2ρ 1 -ρ 2 X σ , (17)
where X = (X σ ) σ∈S n,d is a Gaussian vector, centered, with covariance given by Cov(X σ , X σ ) = c σ,σ . Also note that on event A, for all d ≤ αn and σ ∈ S n,d , inequality (9) gives

v σ = (1 -o(1))2dn(1 -α/2). ( 18
)
In view of (18), as previously done in Section 2.1, naive first moment method may suffice for d ≤ αn:

P   2≤d≤αn E d   ≤ o(1) + αn d=2 S n,d × P N (0, 1) ≥ ρ √ v σ 2 1 -ρ 2 ∩ A ≤ o(1) + αn d=2 S n,d × P N (0, 1) ≥ (1 + ε/2) 2d log n(1 -α/2)(1 -o(1)) ≤ o(1) + αn d=2 exp (d log n -d log n(1 + ε)(1 -α/2) + o(d log n)) ,
which is o(1) as soon as α < α 0 := 2ε 1-ε/2 . It then remains to control the probabilities P(E d ) for d ≥ α 0 n. As mentioned earlier, we take advantage of the correlation structure in (17). More precisely, we show that all variables X σ at a given level d = αn have substantial positive covariance when compared to their variance -of order α(2 -α)n 2 on A by (18) -as shown in Figure 2. To do so, we derive an appropriate lower bound for c σ,σ for σ, σ ∈ S n,αn . This is the scope of the following Lemma: Lemma 2.1. With high probability, there exists a universal constant C 1 > 0 such that for any d = αn with fixed α > 0 and σ, σ ∈ S n,αn :

Cov(X σ , X σ ) = c σ,σ ≥ f (α)n 2 -C 1 n 3/2 log 1/2 n, with f (α) := α 2 if α < 1/2 α 2 -1 2 (2α -1) 2 if α ≥ 1/2 (19)
Thus for any ε > 0, with high probability, for any d = αn with fixed α > 0, max σ∈Sn,αn

X σ ≤ 2α (α(2 -α) -f (α))n 3/2 log 1/2 n + (2 + ε )n log 1/2 n.
The proof of this Lemma is obtained by working on event A defined in (16), and establishing a lower bound on (D E σ ∩ D E σ ), which is simply the number of edges that are deranged both by σ E and σ E . It can be found in Appendix A.1. Then, since f (α) ≤ α(2 -α) with elementary computations, according to Lemma 2.1, there is an event B of probability

1 -o(1) such that max σ∈S n,d X σ ≤ (1 + o(1)) 2α (α(2 -α) -f (α))n 3/2 log 1/2 n
holds for all d = αn with α > α 0 . Note that on event A ∩ B, for all d = αn and σ ∈ S n,d ,

ρ -1 δ(σ) ≥ ρv σ -2 1 -ρ 2 max σ∈S n,d X σ ≥ (1 + o(1))n 3/2 log 1/2 n (2 + ε)α(2 -α) -2 2α (α(2 -α) -f (α)) ≥ (1 + o(1)) × 2 × α(2 -α) -2α (α(2 -α) -f (α)) n 3/2 log 1/2 n ≥ 0,
for n large enough, since it can be easily checked (see Appendix A.3) that Lemma 2.2. For every α ∈ [0, 1],

α(2 -α) -2α (α(2 -α) -f (α)) ≥ 0. (20)
Previous computations give that

P   d≥αn E d   ≤ 1 -P(A ∩ B) = o(1),
and ends the proof of Theorem 1.

Converse bound: second moment method for transpositions

In this section, we prove Theorem 2. As already stated in the introduction, theory from Bayesian optimal estimation guarantees that the best possible estimator for our exact reconstruction problem, in the Bayes risk sense, is πMAP . We will show that under assumption (5) of Theorem 2, this MAP estimator fails with high probability, which implies that no estimator can succeed. This converse bound is obtained by a second moment argument, showing that with high probability, there are lots of permutation τ = id -in fact, transpositions -such that δ(τ ) is negative, that is, τ -1 • π * is a substantially better alignment than π * , with lowest energy. Let us denote T n ⊂ S n the set of all permutations of [n] that are transpositions. For all τ ∈ T n , we have d E τ = 2(n -2). Corollary 1.1 gives that the event

C := ∀τ, τ ∈ T n , c τ,τ -(D E τ ∩ D E τ ) -(D E τ ∩ D E τ ∩ F E τ •τ ) ≤ C n log n
happens with probability 1 -o(1) for C > 0 large enough. In particular, on C, for C > 0 large enough, ∀τ ∈ T n , |v τ -4n| ≤ C n log n.

In this section we are working under the assumption (5) that we recall here:

ρ 2 ≤ 4 log n -log log n -ω(1) n
We are about to show the following: under condition (5), with high probability,

{τ ∈ T n , δ(τ ) < 0} = ω(1). (21)
To do so, we use the classical Paley-Zygmund inequality, proven in Appendix A.4 for self-containment:

Lemma 3.1 (Paley-Zygmund inequality). Let Y be a real random variable with positive mean and finite variance. Then for all 0 ≤ c ≤ 1,

P (Y ≥ c E [Y ]) ≥ (1 -c) 2 E [Y ] 2 E [Y 2 ]
.

Thus, in the case where

E Y 2 ∼ E [Y ] 2 , taking c → 0 implies that Y ≥ o(E [Y ]
) with high probability.

Define X := τ ∈Tn 1 δ(τ )<0 . (22)
Using a standard coupling argument in (22), one can see that X is decreasing with ρ, thus we can assume without loss of generality that

ρ 2 = 4 log n -log log n -a n n , (23)
with a sequence (a n ) n such that a n = ω(1) and a n = o(log log n). We compute the first moment of X, in view of the conditional distribution of δ(τ ) given in (13):

E [X] ≥ E [X1 C ] = n(n -1) 2 E P A N (0, 1) ≥ ρ √ v τ 2 1 -ρ 2 ∩ C ≥ n(n -1) 2 E (1 -o(1))P A N (0, 1) ≥ 1 2 4 log n -log log n -a n 4 -Cn -1/2 log 1/2 n = n(n -1) 2 E (1 -o(1))P A N (0, 1) ≥ 4 log n -log log n -a n -o(1) ∼ n 2 4 √ 2π √ log n exp -2 log n + log log n 2 + a n 2 = 1 4 √ 2π exp a n 2 → ∞.
E Y 2 ≤ (1 + o(1))E [Y ] 2 .
Proof of Lemma 3.2. We represent a transposition τ by its only 2-cycle (i j) with i < j. We then distinguish two cases in couples τ = (i j) = τ = (k ) ∈ T n :

• We write τ ∩ τ = ∅ when τ and τ have no common point in their 2-cycle: i = k and j = l. When τ ∈ T n is fixed, note that

{τ ∈ T n , τ ∩ τ = ∅} = (n -2)(n -3) 2 .
• We write τ ∩ τ = ∅ when τ and τ are different but share one common point: for instance τ = (3 5) and τ = (5 11) verify τ ∩ τ = ∅. When τ ∈ T n is fixed, note that

{τ ∈ T n , τ ∩ τ = ∅} = 2(n -2).
Note that

E Y 2 = E [Y ] + τ ∈Tn τ ,τ ∩τ =∅ P(δ(τ ) < 0, δ(τ ) < 0, C) + τ ∈Tn τ ,τ ∩τ =∅ P(δ(τ ) < 0, δ(τ ) < 0, C).
We now evaluate these two sums. For this, we will need the following Lemma, which proof is deferred to Appendix A.5.

Lemma 3.3 (Control of deviation probabilities for correlated Gaussians). Let Z 1 , Z 2 be two Gaussian variables with mean 0, variance 1 and correlation α n ∈ [0, 1]. For any t n such that t n → ∞, (i) If α n t n → 0, then for n large enough

P (Z 1 > t n , Z 2 > t n ) ≤ e -2t 2 n + (1 + o(1))P (Z 1 > t n ) P (Z 2 > t n ) . (24)
(ii) More generally,

P (Z 1 > t n , Z 2 > t n ) ≤ (1 + o(1)) 1 + α n √ 2π t n exp - t 2 n 1 + α n . ( 25
)
First case: τ ∩ τ = ∅. Without loss of generality we can assume that τ = (1 2) and τ = (3 4).

The following diagram shows the simple action of τ and τ on an interesting (overlapping) subset of edges.

{1, 3} τ ←→ {2, 3} τ τ {1, 4} τ ←→ {2, 4}
We then see that

(D E τ ∩ D E τ ) + (D E τ ∩ D E τ ∩ F E τ •τ ) = 4 + 0 = 4. So, denoting α τ,τ := c τ,τ √ vτ v τ , on C, |α τ,τ | ≤ C √ n log n + 4 4n -C √ n log n = O log n n .
In view of the conditional distribution of δ(τ ) given in (13):

τ ∈Tn τ ,τ ∩τ =∅ P(δ(τ ) < 0, δ(τ ) < 0, C) = (1 -o(1)) τ ∈Tn τ ,τ ∩τ =∅ P (Z τ > t n , Z τ > t n ) , (26)
with t n = √ 4 log n -log log n -a n , where Z τ , Z τ are two Gaussian variables of mean 0, with correlation coefficient α n of order O(log 1/2 n -1/2 ). Since α n t n → 1, by lemma 3.3 case (i), the sum in (26) is upper bounded by

(1 -o(1)) n(n -1) 2 × (n -2)(n -3) 2 × Ce -2t 2 n + (1 -o(1))P (Z 1 > t n ) P (Z 2 > t n ) ≤ (1 + o(1))E [Y ] 2 .
Second case: τ ∩ τ = ∅. Without loss of generality we can assume that τ = (1 2) and τ = (2 3).

We can immediately deduce that

(D E τ ∩ D E τ ) + (D E τ ∩ D E τ ∩ F E τ •τ ) = (n -2) + 0 = n -2. So, denoting α τ,τ := c τ,τ √ vτ v τ , on C, |α τ,τ | ≤ C √ n log n + n -2 4n -C √ n log n ∼ 1 4 .
Again, in view of the conditional distribution of δ(τ ) given in (13):

τ ∈Tn τ ,τ ∩τ =∅ P(δ(τ ) < 0, δ(τ ) < 0, C) = (1 -o(1)) τ ∈Tn τ ,τ ∩τ =∅ P (Z τ > t n , Z τ > t n ) , (27)
with t n = √ 4 log n -log log n -a n , where Z τ , Z τ are two Gaussian variables of mean 0, with correlation coefficient α n ∼ 1/4. By Lemma 3.3 case (ii), the sum in ( 27) is upper bounded by Remark 3. We have shown here that under condition (5), there is with high probability a great number of negative relative energy points near the ground truth, none of them being of significant interest to recover exactly our permutation. We may also study this relative energy far from the planted permutation, which would be interesting to address the problem of almost exact (resp. partial) alignment, which consists in finding an estimator π that coincides with π on at least n -o(n) (resp. some positive fraction of n) points. In the light of our result which shows that exact recovery is not more difficult than detection, we can also conjecture that the same threshold nρ 2 / log n = 4 is sharp for the tasks of almost exact and partial recovery.

(1 -o(1)) n(n -1) 2 × 2(n -2) × (1 + o(1)) 1 + α n √ 2π t n exp - t 2 n 1 + α n ≤ C n 3 log -1/2 (n) exp - 16 5 log n + o(log n) = o(1) = o(E [Y ] 2 ).

A.2 Proof of Lemma A.1: maximum of totally correlated Gaussian variables

Proof. Let us make a change of variables which preserves the joint distribution:

(Z 1 , Z 2 , . . . , Z N ) = √ c ξ 0 + √ v -c ξ 1 , . . . , √ c ξ 0 + √ v -c ξ N ,
where ξ 0 , . . . , ξ N are independent standard Gaussian random variables. The maximum thus writes max

1≤i≤N Z i = √ c ξ 0 + √ v -c max 1≤i≤N ξ i
Then, with the classical inequality P (N (0, 1) ≥ t) ≤ e -t 2 /2 , then with probability at least 1 -1/(log N ), one has:

A.3 Proof of Lemma 2.2

Proof. For α ∈ (0, 1],

(20) ⇐⇒ α 2 (2 -α) 2 ≥ 2α (α(2 -α) -f (α)) ⇐⇒ f (α) ≥ α 2 -α 3 /2.
The inequality is verified for α < 1/2. To conclude the proof of (20), it remains to check that for 1 ≥ α ≥ 1/2, f (α) ≥ α 2 -α 3 /2, which is equivalent to

α 2 - 1 2 (2α -1) 2 ≥ α 2 -α 3 /2 ⇐⇒ α 3 -4α 2 + 4α -1 ≥ 0 ⇐⇒ (α -1)(α 2 -3α + 1) ≥ 0 ⇐⇒ α 2 -3α + 1 ≤ 0 ⇐⇒ α ≥ 3 - √ 5 2
∼ 0.382...

A.4 Proof of Lemma 3.1: Payley-Zygmund inequality

Proof. Using Cauchy-Schwarz inequality,

E[Y ] = E Y 1 Y <c E[Y ] + E Y 1 Y ≥c E[Y ] ≤ c E [Y ] + E[Y 2 ] 1/2 P(Y ≥ c E [Y ]) 1/2 , which gives E[Y ] 2 (1 -c) 2 ≤ E[Y 2 ] P(Y ≥ c E [Y ]).

A.5 Proof of Lemma 3.3: Control of deviation probabilities for correlated Gaussians

Proof. Let us first make a change of variable which preserves the joint distribution:

(Z 1 , Z 2 ) = (Z, α n Z + 1 -α 2 n Z ),
with Z, Z two independent standard Gaussian variables.

Proof of (i): Note that standard Gaussian concentration gives P Z > 2t n Z > t n ∼ 1 2 e -3t 2 n /2 . Thus, for n large enough

P (Z 1 > t n , Z 2 > t n ) ≤ P (Z > t n ) e -

  which happens with probability 1 -o(1) by Corollary 1.1.

Figure 2 :

 2 Figure 2: Plot on [0, 1] of normalized variance α(2 -α), together with the lower bound on the normalized covariance (function f ) defined by (19).

  Note that (23) is thus precisely the condition ensuring that E [X1 C ] → ∞. The second moment argument computation being a little more technical, we encapsulate it into the following Lemma: Lemma 3.2 (Second moment computation of X1 C ). Let Y := X1 C . Under assumption (23),

  Lemma 3.2 together with Payley-Zigmund inequality (Lemma 3.1) implies that Y ≥ o (E[Y ]) with high probability and thus proves (21) and the converse result of Theorem 2.

√ c ξ 0 ≤

 0 2c log log N , and√ v -c max 1≤i≤N ξ i ≤ 2(v -c) log N 1 + log log N log N ,so with probability at least 1 -2/(log N ):max 1≤i≤N Z i ≤ 2(v -c) log N + 2 log log N √ c + √ v -c ≤ 2(v -c) log N + 2 v log log N ,where we used√ c + √ v -c ≤ √2v in the last step.

  3t 2 n /2 + P (Z > t n ) P α n Z + 1 -α 2 n Z > t n , Z ≤ 2t n Z > t n ≤ e -2t 2 n + P (Z > t n ) P Z > t n -2α n t n + O(t n α 2 n ) ≤ e -2t 2 n + P (Z > t n ) P (Z > t n -o(1)) ≤ e -2t 2 n + (1 + o(1))P (Z > t n ) P (Z > t n ) = e -2t 2 n + (1 + o(1))P (Z 1 > t n ) P (Z 2 > t n ) .Proof of (ii): For any (s n ) such that s n ≤ t n for all n, one hasE e snZ Z > t n = -(t n -s n ) 2 /2 + t 2 n /2 = t n t n -s n e sntn .Using independence of Z, Z and Chernoff bound, we get, taking s n such that αs n = ut n with u < 1, for n large enough,P αZ + 1 -α 2 Z > t n Z > t n ≤ (1 + o(1)) t n t n -αs n exp αs n t n + 1 -α 2 2 s 2 n -s n t nThe proof follows from this last inequality, together with the bound P (Z > t n ) ≤ 1

			1 √ 2π	+∞ tn	e snz-z 2 /2 dz	1 √ 2π	tn +∞	e -z 2 /2 dz	-1
		= e s 2 n /2		+∞	e -z 2 /2 dz		+∞	e -z 2 /2 dz
					tn-sn		tn
		∼	t n t n -s n	exp s 2 n /2 ≤ (1 + o(1))	1 1 -u	exp	u +	u 2 (1 -α 2 ) 2α 2	-	u α	t 2 n
						(a) ≤ (1 + o(1))(1 + α) exp -	1 -α 1 + α	•	t 2
	√	2πtn exp -	t 2 n 2		.

n 2 where we took u = α 1+α < 1 in (a).

Acknowledgments

The author would like to thank Léo Miolane, Marc Lelarge, and Laurent Massoulié for helpful discussions. This work was supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).

A Additional proofs A.1 Proof of Lemma 2.1: lower bound on correlations of relative energies

Proof. Recall that we work under event A. Fix α ∈ (0, 1] and take d = αn and σ, σ ∈ S n,d . The proof is obtained by establishing a fine lower bound on (D E σ ∩ D E σ ), which is simply the number of edges that are deranged both by σ E and σ E . In order to establish this lower bound, let us assume that σ and σ have (D σ ∩ D σ ) = βn common unfixed points, with β ∈ [0, α]. We then form edges in D E σ ∩ D E σ in the following way: • First, by taking all pairs but the pairs made of points in the complement of D σ ∩ D σ and those made of pairs (i, j) that are transpositions of σ or σ , we obtain at least 1 2 β(2-β)n 2 -αn edges.

• Then, add new edges made of one extremity in D σ \ D σ and one in

The first inequality is established by applying inequality (16) of event A.

For the second part, consider a centered vector Z = (Z σ ) σ∈Sn,αn such that all Z σ have same variance v α and Cov(Z σ , Z σ ) = c α for σ = σ , with v α , c α defined as follows:

for some C 1 > 0 large enough. Note that on event A, for all α ∈ (0, 1], all σ, σ ∈ S n,αn , Cov(Z σ , Z σ ) ≤ Cov(X σ , X σ ), so one has that for all t > 0, P max σ∈Sn,αn

We now control the right-hand side of (29) with this classical Lemma, which proof is find hereafter in Appendix A.2:

Lemma A.1 (Maximum of totally correlated Gaussian variables). Let Z be a centered Gaussian vector of size N , such that all Z i have same variance v and Cov(Z i , Z j ) = c for i = j. Then

Note that for v α , c α previously defined, one has

and for n large enough,

Finally, we use equations ( 29)-(32) to conclude that for n large enough:


Luca Ganassali

Marc Lelarge
email: marc.lelarge@ens.fr

Laurent Massoulié
email: laurent.massoulie@

Mikhail Belkin

Samory Kpotufe

Impossibility of Partial Recovery in the Graph Alignment Problem

Keywords: graph alignment, probabilistic method, Erdős-Rényi random graphs, partial recovery

Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For the correlated Erdős-Rényi model, we prove an impossibility result for partial recovery in the sparse regime, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erdős-Rényi graph.

Introduction

Graph alignment, also known as graph matching, aims at finding a bijective mapping between the vertex sets of two graphs so that the number of adjacency disagreements between the two graphs is minimized. It reduces to the graph isomorphism problem in the noiseless setting where the two graphs can be matched perfectly. The paradigm of graph alignment has found numerous applications across a variety of diverse fields, such as network privacy [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF]), computational biology [START_REF] Singh | Global alignment of multiple protein interaction networks with application to functional orthology detection[END_REF]), computer vision [START_REF] Conte | Thirty Years Of Graph Matching In Pattern Recognition[END_REF]), and natural language processing.

Given two graphs with adjacency matrices A and B, the graph matching problem can be viewed as a special case of the quadratic assignment problem (QAP) [START_REF] Pardalos | The Quadratic Assignment Problem: A Survey and Recent Developments[END_REF]):

max Π A, ΠBΠ T (1)
where Π ranges over all n × n permutation matrices, and •, • denotes the matrix inner product. QAP is NP-hard in general. These hardness results are applicable in the worst case, where the observed graphs are designed by an adversary. In many applications, the graphs can be modeled by random graphs; as such, our focus is not in the worst-case instances, but rather in recovering partially the underlying vertex permutation with high probability.

Correlated Erdős-Rényi model Driven by applications in social networks and biology, a recent line of work [START_REF] Lyzinski | Seeded graph matching for correlated erdos-renyi graphs[END_REF]; [START_REF] Feizi | Spectral alignment of networks[END_REF]; [START_REF] Cullina | Exact alignment recovery for correlated Erdős-Rényi graphs[END_REF]; [START_REF] Mossel | Seeded graph matching via large neighborhood statistics[END_REF]; Cullina et al. (2018a); [START_REF] Ding | Efficient random graph matching via degree profiles[END_REF]; Cullina et al. (2018b); Fan et al. (2019a); [START_REF] Ganassali | Spectral alignment of correlated Gaussian random matrices[END_REF]; [START_REF] Wu | Testing correlation of unlabeled random graphs[END_REF]; [START_REF] Ganassali | Sharp threshold for alignment of graph databases with gaussian weights[END_REF]; Fan et al. (2019b); [START_REF] Ganassali | From tree matching to sparse graph alignment[END_REF]; [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF]) initiated the statistical analysis of graph matching by assuming that matrices A and B are generated randomly. The simplest such model is the following correlated Erdős-Rényi model: we are given two graphs G and G with the same set of nodes [n] and with respectively blue and red edges. The blue and red edges are obtained by sampling uniformly at random:

• with probability λs/n to get two-colored edges;

• with probability λ(1 -s)/n to get a blue (monochromatic) edge;

• with probability λ(1 -s)/n to get a red (monochromatic) edge;

• with probability 1 -λ(2 -s)/n to get a non-edge, where λ > 0 and s ∈ [0, 1] are fixed parameters and n is large. Hence each G and G is a sparse Erdős-Rényi model with edge probability λ/n. For large values of n, the fraction of edges of G (resp. G ) that are shared with G (resp. G) is. of order s (see Figure 1). and s = 0.7. For the sake of readability, red edges are always dashed.

We then relabel the vertices of the red graph G with a uniform independent permutation π * ∈ S n , and we observe G and H := G π * , see Figure 2. Upon observing G and H, the goal is to recover (or, reconstruct) partially the latent vertex correspondence π * with probability converging to 1 as n → ∞.

Partial alignment in the sparse regime We now define our notion of performance. First note that since we are in the sparse regime, even without any noise, i.e. with s = 1, there is no way to be able to map the Θ(n) isolated vertices in G and H better than chance. Hence, we concentrate on the partial alignment problem where we ask for the best possible fraction of matched vertices between G and H. More formally, an estimator π (of π * ) is a S n -valued measurable function of (G, H). In order to match the two graphs correctly, we do not want to allow π to learn any information from the unique observation of G: indeed, since there is no canonical labeling of graphs, the estimator π must perform well even after any relabeling of the nodes of G. Hence, for any estimator π = π(G, H) of π * , we define its overlap as follows

ov(π(G, H), π * ) := 1 n! σ∈Sn n i=1 1 π(G σ ,H)(i)=π * •σ -1 (i) .
(2) With this definition, it is then easy to check that as wanted, for any σ ∈ S n ,

ov(π(G σ , H), π * ) = ov(π(G, H), π * • σ). (3)
Remark 1.1 This natural definition (2) is here to put aside trivial estimators such as π = id. Note that for the maximum a posteriori estimator πMAP , which is the permutation solving the maximization problem (1), the first sum in (2) can be simplified to one term. Indeed πMAP -similarly to a lot of other 'natural' estimators -verifies an equivariance property, in the sense that for all σ ∈ S n ,

π(G σ , H) = π(G, H) • σ -1 .
Partial alignment thus consists in finding a estimator π of π * satisfying ov(π, π * ) > αn with high probability, for some α > 0. Let us start by stating a conjecture:

Conjecture (i) If λs ≤ 1,
partial reconstruction is impossible, i.e. for any α > 0, for all estimator π,

P (ov(π, π * ) > αn) -→ n→∞ 0.
(ii) If λs > 1, partial reconstruction is possible (feasible), i.e. there exists α > 0 and an estimator π such that

P (ov(π, π * ) > αn) -→ n→∞ 1.
Results in the regime with constant mean degree and correlation In this paper, we work in the regime where λ > 0 and s ∈ [0, 1] are fixed constants. Our results prove part (i) of the conjecture, which had not been previously studied, and give an upper bound on the maximal reachable overlap in case (ii). Let us mention straightaway the related results in our regime that are helpful for our conjecture: [START_REF] Ganassali | From tree matching to sparse graph alignment[END_REF] prove that partial recovery is possible (in polynomial time) in a region R := {(λ, s); λ ∈ [1, λ 0 ) and s ∈ (s * (λ), 1]} for some function s * (λ) < 1, so that interestingly the case λ > λ 0 is left open, nevertheless much in step with (ii). Previous results from [START_REF] Hall | Partial Recovery in the Graph Alignment Problem[END_REF] showed that partial reconstruction was feasible for λs > C, with an unspecified constant C > 20. At the very time when this paper is being finished, new results from [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF] are significantly improving these results, narrowing down the gap for (ii).

When translated with our notations, it is shown that partial alignment is possible (theoretically) if λs ≥ 4 + ε. These results are summed up in a diagram in Figure 3. In particular, our bound is tight and our conjecture is almost solved for the case s = 1, with a remaining gap [λ 0 , 4] being still open.

[WXY21]

Main result

The main result of our paper is as follows:

Theorem 1 For λ > 0 and s ∈ [0, 1], we have for any α > 0, for any estimator π:

P (ov(π, π * ) > (c(λs) + α)n) -→ n→∞ 0, (4)
where c(µ) is the greatest non-negative solution to the equation e -µx = 1 -x.

Note that a well-known result (see e.g. [START_REF] Bollobás | Random Graphs[END_REF]) is that c(µ) is the typical fraction of nodes in the largest component of an Erdős-Rényi graph with average degree µ, and that c(µ) = 0 if µ ≤ 1, and c(µ) ∈ (0, 1) whenever µ > 1. Hence, Theorem 1 implies that partial reconstruction is impossible for λs ≤ 1. Moreover, if λs > 1, any estimator can reach an overlap of at most c(λs)n + o(n). Note that c(λs) is the typical fraction of nodes in the largest component of the intersection graph.

Further related work Graph matching has also been widely studied in the case where the mean degree and correlation are not fixed constants. The model is the same, with adapted notations: the probability for two-colored (resp. monochromatic, non-) edges are now qs (resp. q(1 -s), 1-q(2-s)), with s ≥ q and q and s that may depend on n. Note that our study focuses on the sparse setting where q = λ/n and s is constant, and that interesting results in other regimes are known for partial, almost exact, and exact recovery. We hereafter give them in detail, for completeness.

• Exact recovery (when ov(π, π * ) = n) has been studied theoretically in recent work from [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF] refining previous results of [START_REF] Cullina | Exact alignment recovery for correlated Erdős-Rényi graphs[END_REF], exhibiting a tight threshold at

nq √ s - √ q 2 log n = 1,
with the only condition that1 q/s is bounded away from 1.

• For almost exact recovery (i.e. ov(π, π * ) ≥ (1 -ε)n for all ε > 0), in a sparse regime where q/s = n -Ω(1) , it is known (Cullina et al. (2018a)) that almost exact recovery is possible if and only if nqs → ∞. In a denser regime where q/s = n -o(1) , [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF] show that there is a tight threshold exhibiting an "all-or-nothing" phenomenon at

nq s log s q -(s -q) log n = 2,
above which almost exact recovery is possible and below which even partial recovery is impossible.

• For partial recovery, the first investigation made by Hall and Massoulié (2020) -though rather difficult to translate in our model -showed that nqs → 0 is an impossibility condition, whereas nqs ≥ C (with a large, non-explicit constant C), together with some additional sparsity constraints, ensures feasibility. As mentioned, [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF] improve these results, showing that in the case q/s = n -Ω(1) , nqs ≥ 4 + ε suffices to ensure possibility. In addition, an impossibility condition of the form nqs ≤ 1 -ε is also established, but in a denser case, where nq/s = ω(log 2 n). Note that this last impossibility result does not cover our regime, where both the mean degree nq and the correlation parameter s are of order 1.

For the impossibility part, [START_REF] Wu | Settling the sharp reconstruction thresholds of random graph matching[END_REF] works with the mutual information I(π * ; G, G ), closely related to the minimum mean squared error. They are able to derive an upper bound on the expectation of ov(π, π * ), for any estimator, which happens to be o(1) when the mean degree in the parent graph of G and G is at least of order log 2 n, but not when λ, s are of order 1. In our result, we do not work directly with the mutual information, but we are considering the posterior distribution of π * : in simple words, we show that under the assumption λs < 1 the posterior distribution puts equal weights on permutations that overlap only on a vanishing fraction of points. This is done by building ad hoc permutations with the probabilistic method.

In this paper, we derive information-theoretic results: our proof is not constructive, i.e. not related to a particular algorithm. The search for efficient algorithms is a very active field of research: using spectral methods [START_REF] Feizi | Spectral alignment of networks[END_REF]Fan et al. (2019b)), degree profiles [START_REF] Ding | Efficient random graph matching via degree profiles[END_REF]), convex relaxation [START_REF] Dym | Ds++: A flexible, scalable and provably tight relaxation for matching problems[END_REF]), etc. Unfortunately, except from [START_REF] Ganassali | From tree matching to sparse graph alignment[END_REF], these algorithms are not known to give a positive fraction of overlap in the regime λs ≥ 1, hence leaving the question of the tightness of our bound open.

Main results and global intuition 2.1. Some definitions

Throughout the paper, some proposition A n is said to be true with high probability (w.h.p.) if

P(A n ) → 1 when n → ∞.
Finite sets, permutations For all n > 0, we define [n] := {1, 2, . . . , n}. For any finite set X , we denote by |X | its cardinal. S X is the set of permutations on X . We also denote S k = S [k] for brevity, and we will often identify S k to S X whenever |X | = k. For any permutations σ, σ ∈ S n we denote by Fix(σ, σ ) the number of points on which σ = σ , namely

Fix(σ, σ ) := n i=1 1 σ(i)=σ (i) .
Graphs Through all the paper, we will implicitly consider that every graph G of size n has the canonical vertex set [n]. We will denote by E(G) its edge set and e(G) its number of edges.

For any pair of graphs (G, G ), both labeled on [n], we denote by G ∨ G (resp. by G ∧ G ) the union graph (resp. intersection graph) of G and G . The symmetric difference of G and G , denoted by G G , is the subgraph made of edges of G ∨ G that are not in G ∧ G .

In the case where edges are colored (say G is blue and G is red), these definitions extend to ensure colour preservation: note e.g. that in this case G ∧ G is simply the subgraph of G ∨ G consisting of two-colored edges (see Figure 4). When the pair (G, G ) is drawn under the correlated Erdős-Rényi model, for all u, v ∈ [n], we write u ←→ v (resp. u ←→ v) if u and v are connected in G, that is the edge is either blue or two-colored (resp. in G , either red or two-colored).

For G a graph with vertex set [n] and σ ∈ S n , we denote by G σ the relabeling of G with σ, which is the graph with same vertex set [n] and edges (σ(u), σ(v)) for all (u, v) ∈ E(G).

Finally we recall the definition of c(µ): for all µ > 0, c(µ) is the greatest non-negative solution to the equation e -µx = 1 -x. We also recall the fact that for µ ≤ 1, c(µ) = 0.

General intuition on main result

Let us describe the general intuition for our result : recall that we are given (G, H) drawn under the correlated Erdős-Rényi model with planted relabeling π * . The idea of the argument for impossibility is to show that, there are w.h.p. lots of permutations that have the same weight for the posterior distribution of π * given G, H, and that are far apart. In other words, an informal statement is as follows :

(Informal Statement) We want to show that there exists lots of relabelings G σ i of G such that:

(i) There is no way of deciding (statistically) whether the two graphs we observe are (G, G ) or some (G σ i , G ).

(ii) These relabelings are far apart from each other and small components of G ∧ G .

Let us give a formal version of the previous intuition. First note that for any labeled graphs G, G on [n]:

P(G = G, G = G ) = λs n e(G∧G ) λ(1 -s) n e(G G ) 1 - λ(2 -s) n ( n 2 )-e(G∨G )
.

Since

e(G ∨ G ) = e(G) + e(G ) -e(G ∧ G ) and e(G G ) = e(G ∨ G ) -e(G ∧ G ), P(G = G, G = G ) is uniquely determined by e(G)
, e(G ) and e(G ∧ G ). In particular, the dependence of the joint distribution in e(G ∧ G ) is given by:

P(G = G, G = G ) ∝ s(n -λ(2 -s)) λ(1 -s) 2 e(G∧G )
.

(5)

In view of ( 5), preserving the posterior distribution by relabeling a graph G is simply preserving the number of edges of their intersection graph. We now have a formal rephrasing for our conditions (i) and (ii) above: we encapsulate them in a theorem, which will constitute the bulk of our paper.

Theorem 2 Fix an integer p > 0. Consider (G, G ) drawn under the correlated Erdős-Rényi model. Then, with high probability, there exists {σ i } i∈[p] -that depend on the intersection graph G ∧ Gsuch that

(i) ∀i ∈ [p], e (G σ i ∧ G ) = e (G ∧ G ), (ii) ∀i, j ∈ [p], i = j =⇒ Fix(σ i , σ j ) ≤ c(λs)n + o(n), where the o(n) is independent of i, j ∈ [p].
Let us now explain how Theorem 2 implies our impossibility result via a simple pigeonhole principle.

Proof [Proof of Theorem 1] Let us take α > 0. We want to control the probability that the overlap between an estimator π and π * is greater than αn + c(λs)n. Fix ε > 0, and take p large enough so that αεp > 2.

First note that point (i) together with (5) gives that the joint probability of (G, G , π * ) is is equal to that of (G σ i , G , π * ), for all i ∈ [p]. Thus, for all estimator π depending on G, H = G π * , one has

∀i ∈ [p], ov (π(G σ i , H), π * ) (d) = ov (π(G, H), π * ) , (6)
and by (3), we also have

∀i ∈ [p], ov (π(G σ i , H), π * ) = ov (π(G, H), π * • σ i ) . (7) Let X := i∈[p] 1 ov(π,π * •σ i )>(c(λs)+α)n Note that because of point (ii), all Fix(π * • σ i , π * • σ j ) are at most c(λs)n + o(n) for i = j ∈ [p].
Thus, there are at least X × (α -o(1))n distinct points among the node set [n]. This gives that one necessarily has

X ≤ 1 α -o(1) . ( 8
)
Then, taking the expectation and considering the event on which the set {σ i } i∈[p] of Theorem 2 exists -which happens with probability 1 -o(1) -gives

E [X] ≥ p i=1 P (ov(π, π * • σ i ) > (c(λs) + α)n) -p × o(1) = p × P (ov(π, π * ) > (c(λs) + α)n) -o(1).
Hence,

P (ov(π, π * ) > (c(λs) + α)n) ≤ 1 p(α -o(1)) + o(1). (9)
For n large enough, the right-hand side of the last term is less that 1 p(α/2) , which is less than ε. This proves as desired that for all α > 0

P (ov(π, π * ) > (c(λs) + α)n) -→ n→∞ 0. ( 10
)
We are now left to understand how to build ad hoc permutations verifying points (i) and (ii) of Theorem 2. In order to build these permutations, we are going to relabel the vertices on small tree components of the intersection graph G ∧ G . As a first step, we hereafter check that they indeed nearly cover the whole graph, when letting aside the giant component.

Vertices on small tree components

We briefly recall the definition of the simple Erdős-Rényi model G(n, p): it consist in drawing a (single) graph with node set [n] in which every edge is independently present with probability p. Let us begin with a classical result: We need here a slight adaptation of this result, showing that (1 -c(µ))n -o(n) vertices are in fact on small tree components.

Lemma 2.2 Let G ∼ G(n, µ/n) with µ > 0, and K(n) → ∞. Then with high probability, 1 -c(µ))n -o(n) vertices are on tree components of size at most K(n).

Proof Assume without loss of generality that K(n) = o(log n). Let T > be the number of vertices that are on tree components of size ≥ K(n). Taking a n = o(n) in Lemma 2.1, it remains to show that w.h.p., T > = o(n). This is done easily by bounding very roughly the first moment. Another classical result (see e.g. [START_REF] Janson | Random graphs[END_REF], Theorem 5.4) is that with probability 1 -o(1), all tree components are of size O(log n), which gives

E [T > ] n ≤ o(1) + O(log n) k=K(n) 1 n • k • n k k k-2 µ n k-1 1 - µ n k(n-k)+( k 2 )-k+1 ≤ o(1) + (1 + o(1)) O(log n) k=K(n) e k k µ k-1 e -kµ ,
using n k ≤ en k k together with Cayley's formula2 and the fact that for all indices

K(n) ≤ k ≤ O(log n) in the sum, k 2 ≤ o(n) (uniformly)
. Now, the series in the right hand term has general terms which is O e -k(µ-log µ+1) , and since µ -log µ + 1 > 0 the series converges, which implies that E [T > / n] = o(1). The proof is concluded by Markov's inequality.

Since in our model G ∧ G is an Erdős-Rényi graph of parameters (n, λs/n), the previous results ensures that all but a vanishing part of the (1 -c(µ))n vertices outside the giant component are on small (i.e. ≤ K(n)) tree components of the intersection graph. For the rest of the paper, we will take

K(n) = log n .
This first step suggests to build the permutations (relabelings) only by looking at G ∧ G . Hence, we will first consider the random generation of the intersection graph, then create some permutations σ i , and finally reveal the monochromatic edges.

The generating process is as follows: since almost all (1 -c(µ))n vertices are on small trees in G ∧G , we can prove that each small tree up to isomorphism will have a number of occurrences in the intersection graph of order n (this is claimed more precisely in Lemma 3.1). Permuting iteratively these isomorphic trees, we may derange them quite a lot, and each time differently.

In order to prove Theorem 2, we use the probabilistic method3 : we give in the next section a simple detailed stochastic method to build p permutation candidates, and we will next prove that these permutations satisfy conditions (i) and (ii) with positive probability, hence proving the desired existence.

Building automorphisms of G ∧ G tree-wise

Through all this section, we work conditionally on the intersection graph G ∧ G (that is the twocolored edges).

Mathematical formalization

Recall that we fix K := K(n) = √ log n . For all k ∈ [K], we will denote by T k the set of unlabeled trees of size k. T k can also be viewed as the set of equivalence classes of labeled trees of size k for the isomorphism relation. Note that T k is finite and that we can roughly upper bound its size by the number of labeled trees of size k which equals k k-2 , by Cayley's formula4 . For a given tree T ∈ T k , we will denote by X T the number of distinct connected components of G ∧ G that are isomorphic to T, H T := {T 1 , T 2 , . . . , T X T } the set of the corresponding labeled subgraphs of G ∧ G , and V (H T ) the set of vertices of [n] that belong to one of the trees in H T .

T 4 = , T 6 = , , , , ,
Our global recursion will be done on the finite set

T := K k=1 T k = {T 1 , T 2 , . . . , T M } , (11)
which we assume to have been ordered increasingly according to tree sizes, for convenience. The global permutation σ is built block-wise by composing permutations σ T for T ∈ T such that each σ T only acts on vertices of H T . More precisely, for a fixed T ∈ T, σ T will consists in permuting the vertices tree by tree, so σ T will be determined by a tree permutation Σ T of size X T . Assume that for all trees T 1 , . . . , T X T isomorphic to T in G ∧ G , we fix some isomorphisms ψ 1 , . . . , ψ X T such that T i ∼

ψ i T for all i ∈ [X T ]
. More generally we will denote i(u) the index of the tree that u ∈ V (H T ) belongs to (when there is no ambiguity on T), and u u when two vertices of G ∧ G are sent onto the same point of T by these isomorphisms. Then, the natural definition of the node permutation σ T according to Σ T and these isomorphisms is given by

σ T : u → ψ -1 Σ T (i(u)) • ψ i(u) (u) (∈ T Σ T (i(u)) ) if u ∈ V (H T ), u if u / ∈ V (H T ). ( 12
)
Note that by definition, V (H T ) is stable by σ T , and σ T fixes all nodes in [n] \ V (H T ). Recall that M denotes the total size of T as defined in (11). The recursive construction is as follows :

Algorithm 1 Recursive construction of σ Initialize σ 0 ← id for i = 1 to M do Consider T = T i and draw uniformly at random the tree permutation Σ T ∈ S X T , independently from the past Consider σ T the node permutation associated with Σ T by ( 12)

σ i ← σ T • σ i-1 end return σ = σ M
Note that at the end of the procedure, σ fixes all points that are either on the giant component of the intersection graph, or on a component that is not a tree a size ≤ K(n). Figure 6 gives an example of this random recursive construction (for convenience, λs < 1, the true labels are in red, whereas blue labels enables to keep track of the relabeling recursively built on the blue graph).

Through the analysis we will need the following control on X T for T ∈ T:

Lemma 3.1 Recall that K(n) = √ log n . For all k ∈ [K(n)], define f (k) := (λs) k-1 e -λsk k!
. Then, with high probability (on the intersection graph),

∀k ∈ [K(n)], ∀T ∈ T k , X T ≥ n(1 -o(1))f (k). ( 13
)
The proof of this result is deferred to Appendix B.1.

Remark 3.1 Note that since λse -λs < 1, k → f (k) is decreasing with k. Moreover, for K(n) ≤ √
log n, we have that for any t > 0,

f (K(n)) ≥ exp -C log n log log n n -t .

Ensuring that the permutations are 'far apart'

We check in this section that Algorithm 3.1 generates permutations that will verify condition (ii) of Theorem 2, w.h.p. Let σ 1 , . . . , σ p be generated independently with Algorithm 3.1. We then have the following results:

Lemma 3.2 With high probability, for all i = j ∈ [p], Fix(σ i , σ j ) = c(λs)n + o(n).
This lemma is proved in Appendix B.2. In the sequel we will denote by V ∞ the set of vertices that are on the giant component of G ∧ G (if there is one), and by

V > the vertices of [n] \ V ∞ that are not on tree components of size ≤ K(n). Finally we set V ∞,> := V ∞ ∪ V > . Define S in := [n] \ V ∞,> 2 , S out := [n] 2 \ V ∞,> 2 ∩ [n] \ V ∞,> 2 , S := S in ∪S out . ( 14
)
S in is the set of edges that have both endpoints outside V ∞,> , whereas edges of S out have exactly one endpoint in V ∞,> . We say that an edge (u, v) ∈ [n] 2 is a common fixed edge of permutations σ 1 , . . . , σ r if {σ 1 (u), σ 1 (v)} = . . . = {σ r (u), σ r (v)} . ΣT 1 = (2)(1 3 5 6 4) ΣT 4 = (1) For all subset of edges W ⊆ [n] 2 , we define

σT 1 = (8)(5 11 21 22 13) T 1 T 2 T 3 1/1 2/2 3/
ΣT 2 = (2)(1 3) σT 2 = (6)(7)(9 14)(10 20) T 1 T 2 1/1 2/2 3/
σT 4 = (1)(2)(3)(4) 1
F (W, σ 1 , . . . , σ r ) := e∈W 1 e is a common fixed edge of σ 1 ,...,σr . (15)
We now state a result -which proof is deferred to B.3 -that will be useful in next section.

Lemma 3.3 With high probability, we have, for any t > 0,

• for any

i 1 = i 2 ∈ [p], F (S, σ i 1 , σ i 2 ) ≤ n 1+t , (16)
• for any i

1 , i 2 , i 3 ∈ [p] pairwise distinct, F (S, σ i 1 , σ i 2 , σ i 3 ) ≤ n t , (17)
• for any r ≥ 4, i 1 , . . . , i r ∈ [p] pairwise distinct, F (S, σ i 1 , . . . , σ ir ) = 0.

(18)

Emergence of extra double edges

In the example of Figure 6, we can see that the number of two-colored edges in the relabeled union graph G σ i ∨ G is constant through time. This property is fundamental for point (i) of Theorem 2. However, depending on the random σ T i drawn through the process -we recall that they are drawn independently from the monochromatic edges, that are not revealed yet -we may see extra two-colored edges appear (extra double edges hereafter). Figure 7 shows a case in which there is an emergence of an extra double edge in the process.

T 1 Note the number of two-coloured edges can only be greater or equal to e(G ∧ G ) through this process, since by definition we are preserving edges of the intersection graph.

T 2 T 3 1/1 2/2 3/
The last part of our work is to prove that there is a positive probability that applying independently Alg.3.1 p times gives p permutations that do not present extra double edges, before using the probabilistic method. This step will require a Poisson approximation, described hereafter.

Poisson approximation to avoid extra double edges, proof of Theorem 2.

In this section we introduce n to be the number of vertices that the permutations actually act on:

n := |[n] \ V ∞,> | ∼ (1 -c(λs))n w.h.p. ( 19
)
Then, we assume that we fix a set {σ i } i∈ We will work under the event E S on which n ∼ (1 -c(λs))n and |S| ∼ n 2 ∼ n 2 /2 = (1 -c(λs)) 2 n 2 /2. It is easy (see e.g. [START_REF] Bollobás | Random Graphs[END_REF]) to show that E S is satisfied w.h.p. As explained before, some extra double edges (e.d.e. hereafter) may appear when revealing the non double edges of S (that is, blue and red edges that are not between vertices of V ∞,> ). Note that for every edge we have

P u ←→ v | (u, v) / ∈ E(G ∧ G ) = P u ←→ v | (u, v) / ∈ E(G ∧ G ) = P (u ←→ v, (u, v) / ∈ E(G ∧ G )) P ((u, v) / ∈ E(G ∧ G )) = λ(1 -s)/n 1 -λs/n ∼ λ(1 -s) n .
For any permutation σ, define the number of created e.d.e. by the relabeling of G by σ as follows:

∆(σ) := {u,v}∈S 1 u←→v 1 σ(u)←→σ(v) . (20)
We now present the key result for our analysis, with the notation n k for the falling factorial

n k := n(n -1) • • • (n -k + 1).
Theorem 3 (Asymptotic Poisson behavior of {∆(σ i )} i∈[p] ) Assume that {σ i } i∈[p] verify (H1), (H2) and (H3). Then, for all 1 , 2 , . . . , p ≥ 0,

E ∆(σ 1 ) 1 ∆(σ 2 ) 2 • • • ∆(σ p ) p G ∧ G , E S -→ n→∞ λ 2 (1 -s) 2 (1 -c(λs)) 2 2 1 + 2 +...+ p .
(21) In other words, conditionally to graph G ∧ G and event E S , the random variables {∆(σ i )} i∈[p] are asymptotically distributed as independent Poisson variables of parameter λ 2 (1-s) 2 (1-c(λs)) 2 2 .

The proof of Theorem 3, based on a fine control of terms of unusually high contribution, is deferred to Appendix A.

Proof of Theorem 2

Proof The proof is quite straightforward now. Fixing p > 0, Lemma 3.3 gives that (H1), (H2) and (H3) are verified w.h.p. by some σ 1 , . . . , σ p generated independently with Algorithm 3.1. Then, the probability (on the remaining monochrome edges) that the p permutations given satisfy conditions (i) and (ii) of Theorem 2 is equivalent to

(1 -o(1)) × P Poi λ 2 (1 -s) 2 2 = 0 p = (1 -o(1)) exp -p λ 2 (1 -s) 2 2 > 0, (22)
which gives the existence with high probability of a set a permutations of size p satisfying conditions (i) and (ii) of Theorem 2.

1 = 4 2 = 3 3 = 3 1 Figure 8: Example of a dependency graph, with (k 1 , k 2 , k 3 , k 4 ) = (3, 2, 1, 0).
In order to upper bound the contribution due to large terms, we must understand both the expectation of the product of indicators in (23) (this only depends on (k 1 , k 2 , k 3 , k 4 )), as well as the number of possible (labeled) dependency graphs with a given (k 1 , k 2 , k 3 , k 4 ).

First, all plain (resp. dashed) dependency edge makes 1 (resp. 1) indicators disappear in the expectation (for any event A, 1 2 A = 1 A ). In the same way, all thick plain isolated edge (resp. thick plain isolated path of length 2) makes 2 (resp. 4) indicators disappear the expectation for a given case with given

(k 1 , k 2 , k 3 , k 4 ) is q 2( 1 +...+ p)-(k1+k2+2k3+4k4) ≤ C 1 n -2( 1 +...+ p)+(k1+k2+2k3+4k4) (24)
where C 1 is a constant depending on 1 , . . . , p , Second, an upper bound for the number of possible (labeled) dependency graphs with a given (k 1 , k 2 , k 3 , k 4 ) can be established as follows. First, we have k 1 + k 2 + k 3 + 2k 4 equalities, leaving at most 1 + . . . + p -(k 1 + k 2 + k 3 + 2k 4 ) degrees of freedom in the choices of the edges. Moreover, we force k 3 of these edges to be common fixed edges between two (distinct) permutations, and k 4 of them to be common fixed edges between three (pairwise distinct) permutations. In view of hypotheses (H1) and (H2), the number of possible (labeled) dependency graphs with a given (k 1 , k 2 , k 3 , k 4 ) is at most

k 1 + k 2 + k 3 + k 4 k 3 + k 4 |S| 1 +...+ p-(k1+k2+k3+2k4)-k3-k4 × (n 1+t ) k 3 × n tk 4 ≤ C 2 n 2( 1 +...+ p)-2(k1+k2)-(3-t)k3-(6-t)k4 , (25)
where C 2 is a constant depending on 1 , . . . , p . Hence, in view of ( 24) and ( 25), the total contribution of higher terms is upper bounded by

1 +...+ p s=1 k 1 +k 2 +k 3 +2k 4 =s C 1 C 2 n -2( 1 +...+ p)+(k1+k2+2k3+4k4) n 2( 1 +...+ p)-2(k1+k2)-(3-t)k3-(6-t)k4 ≤ C 1 C 2 1 +...+ p s=1 k 1 +k 2 +k 3 +2k 4 =s n -k 1 n -k 2 n -(1-t)k 3 n -(2-t)k 4 ≤ C 1 C 2 × ( 1 + . . . + p ) × ( 1 + . . . + p ) 4( 1 +...+ p) × n -(1-t) -→ n→∞ 0.
This last convergence concludes the proof.

where

f (k) := µ k-1 e -µk k! . (26)
We used in (a) that all (1 -ε)α(T) -E [X T ] are negative for n large enough, in (b) uniformity in k ≤ K(n), in (c) the lower bound nf (k) for α(T ), and finally in (d) that k → f (k) is decreasing since µe -µ < 1.

Taking now e.g. ε = n -1/4 , the last fact to check to establish the Lemma is that K K /f (K) = o(n 1/2 ) when K = K(n) = log 1/2 (n): First notice that for any permutations σ i , σ j with i = j generated with Algorithm 3.1, we have the following equality:

K K /f (K) = K K K!(1/µ) K-1 e µK
Fix(σ i , σ j ) = T ∞ + T > + K(n) k=1 T∈T k k • Fix(Σ (i) T , Σ (j) T ), (27)
where Σ

(i)

T (resp. Σ (j)
T ) is the tree permutation associated with T in σ i (resp. in σ j ). We know that T ∞ = c(λs)n + o(n) w.h.p. and by Lemma 2.2, T > = o(n) w.h.p. Define

Fix (σ i , σ j ) :=

K(n) k=1 T∈T k k • Fix(Σ (i) T , Σ (j)
T ),

the second term in (27). We dominate Fix (σ i , σ j ) as follows:

Lemma B.1 If X = Fix(Σ (i) T , Σ (j)
T ),, then for all t ∈ R, E e tX ≤ exp(e t ). ≤ exp -

n α K(n) log n 1-α K(n) K(n)+2 -1 , taking t = 1 K(n) log n α K(n) K(n)+2
. The right hand side tend to 0 for any α ∈ (0, 1), and a simple use of the union bound ends the proof.

B.3. Proof of Lemma 3.3

Proof Fix t > 0. We use a standard first moment method. We will use the results of Lemmas 2.2 and 3.1, conditioning on the event A where the corresponding results hold. Since P(A) = 1 -o(1), this conditioning is legitimate for our purpose.

Step 1. Let us first control the term F (S out , σ i 1 , . . . , σ ir ): edges of S out are made of exactly one vertex in V ∞,> . There are at most n 2 such edges, and the probability for a given edge of S out being a common fixed edge of σ i 1 , . . . , σ ir is 1 X r-1 T , which can be upper-bounded on A by (nf (K(n))) 1-r ≤ n 1-r+t/2 by Remark 3.1.

Edges of S out thus have a contribution in E [F (σ i 1 , . . . , σ ir )|A] of at most n 3-r+t/2 .

Step 2. In the edges appearing in F (σ i 1 , . . . , σ ir ), we consider three cases:

(i) edges of Intra: these are edges made with two vertices in the same tree T ∼ T ∈ T. On event A, there are at most

K(n) k=1 T∈T k X T k 2 ≤ nK(n)
such edges. The probability for a given edge of Intra made of vertices of T ∈ T being a common fixed edge of σ i 1 , . . . , σ ir is 1 X r-1 T , which can be upper-bounded by (nf (K(n))) 1-r ≤ n 1-r+t/2 . Edges of Intra thus have a contribution in E [F (σ i 1 , . . . , σ ir )|A] of at most n 2-r+t/2 .

Figure 1 :

 1 Figure1: A realization of (G, G ) from the correlated Erdős-Rényi model, with n = 11, λ = 1.9, and s = 0.7. For the sake of readability, red edges are always dashed.

Figure 2 :

 2 Figure 2: The pair (G, H) corresponding to (G, G ) of Figure 1, after relabeling G with the permutation π * = (6)(1 5 3 11 9 2 8 4 7 10).

Figure 3 :

 3 Figure 3: Diagram of the (λ, s) regions where partial reconstruction is known to be impossible (resp. possible), in the sparse regime where λ, s are fixed constants.

Figure 4 :

 4 Figure 4: The graph G ∨ G with (G, G ) of Figure 1. For the sake of readability, the two-colored edges of G ∧ G are always drawn thick and purple.

  Lemma 2.1[START_REF] Bollobás | Random Graphs[END_REF], Corollary 5.8, Theorem 6.11) Let G ∼ G(n, µ/n) with µ > 0, and a n → ∞. Then, with high probability, G has a giant component of order c(µ)n + o(n) and outside the giant component, at least (1 -c(µ))n -a n vertices are on tree components.

Figure 5 :

 5 Figure 5: Explicit composition of T 4 (of size 2) and T 6 (of size 6).

Figure 6 :

 6 Figure 6: Example of recursive (tree-wise) generation of a permutation with Algorithm 3.1.

Figure 7 :

 7 Figure 7: Example of the emergence of an extra double edge in Algorithm 3.1.

  [p] of p permutations of [n ], verifying :for all t > 0, for all m = m ∈ [p], F (S, σ m , σ m ) ≤ n 1+t . (H1) for all t > 0, for all m 1 , m 2 , m 3 ∈ [p] pairwise distinct , F (S, σ m 1 , σ m 2 , σ m 3 ) ≤ n t . (H2)There are no common fixed edge of any r-tuple in {σ i } i∈[p] . (H3)

≤

  exp (2K log K + (log(1/µ) + µ)K) = exp log 1/2 (n) log log n + (log(1/µ) + µ) log 1/2 (n) = o(n 1/2 ). B.2. Proof of Lemma 3.2 Proof Denote T ∞ := |V ∞ | and T > := |V > |.

  -1) . . . (k -m + 1) (k -m)! kUsing independence of the X variables, Equation (29) of Lemma B.1 give that for all t ∈ R,E e t•Fix (σ i ,σ j ) ≤ K(n) k=1 T∈T k exp(e tk ) ≤ exp e tK(n) K(n) K(n)+1 . (30)Now, we use the classical Chernoff bound, for positive t,P Fix (σ i , σ j ) ≥ n α ≤ exp -tn α + e tK(n) K(n) K(n)+1

© 2021 L. Ganassali, M. Lelarge & L. Massoulié.

q/s is often referred to as the mean degree in the parent graph of G, G . Indeed, another common way of generating the two graphs under the correlated Erdős-Rényi model is to consider F a parent Erdős-Rényi graph of n nodes and mean degree q/s, and perform two independent sub-samplings of F, keeping each edge independently with probability s, forming G and G , two correlated Erdős-Rényi graphs of mean degree q.

Cayley's formula states that the number of trees on k labeled vertices is k k-2 .

The main interest of this widely used method (see[START_REF] Alon | The Probabilistic Method[END_REF]) is to be non-constructive. Indeed, as detailed in the next Sections, explicitly giving the p permutations considered in Theorem 2 is very cumbersome, because of the extra double edges that may appear (see Section 3.3).

This upper bound is far from being optimal, but is enough for our use.

Acknowledgments

This work was partially supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).

Appendix A. Proof of Theorem 3

Proof [Proof of Theorem 3] Let 1 , 2 , . . . , p be non negative integers. Recall that conditioned to G ∧ G , each edge of S is independently blue (resp. red) with probability q = q(λ, s, n) := λ(1 -s) n -λs .

Now, let us explain why convergence (21) holds. First recall that for a given ≥ 0, E ∆(σ) is nothing else but the expected number of (ordered) p-tuples of edges {u, v} ∈ S such that 1 u←→v 1 σ(u)←→σ(v) = 1. Using the notation * for summation of ordered tuples of edges in S as well as linearity of expectation, we get:

1 }, {u

First observe that the total number of terms N in the previous sum is

Lower bound: Observe that the N terms in the sum of eq. ( 23) are made in general of 2( 1 + . . . + p ) indicator variables, not necessarily distinct. For most of the terms however, all involved edges are distinct, thus independent, and their contribution to the sum is q 2( 1 +...+ p) .

Whenever a pair of blue (resp. red) indicators are equal, at least one term may be canceled, so the contribution to the expectation is higher than q 2( 1 +...+ p) .

Whenever a pair of edges that appear in a blue/red pair of indicators are equal, the product of the indicators is necessarily 0 (indeed, an edge in S cannot be two-colored). These terms, where at least one equality of the form u

) occurs, cover the case where the contribution is strictly less that q 2( 1 +...+ p) (it is 0). There are at most

Upper bound: The terms that we now want to study are the terms for which the contribution is greater than q 2( 1 +...+ p) . Looking closely at the general product in ( 23), an unusual high contribution is the consequence of three possible type of constraints:

: note that since the sums are made of ordered tuples, this equality may happen only for pairs such that m = m . Moreover, transitivity of equality implies that a constraint implying some u

, which is impossible).

(ii) constraints of the form σ m (u

) . For the same reasons as in case (i), a constraint implying some σ m (u (iii) the last case is made of intersection of cases (i) and (ii), i.e. edges satisfying both constraints u

and σ m (u

) .

This implies in particular that u

is an common fixed edge for σ m and σ m . By assumption (H3), note that there cannot be a connected path of constraints of the form (iii) of length greater or equal to 3.

Let us now represent these constraints with a dependency graph. Each vertex a the graph represent one edge u

of the sum, that we will align column-wise according to m ∈ [p]. We put a plain (resp. dashed) edge between two nodes if they are enforced by constraint (i) but not (iii) (resp. (ii) but not (iii)). Finally we draw a thick plain edge between two nodes if they are enforced by constraint (iii).

In view of discussion in points (i) -(ii) -(iii), this dependency graph must be p-partite. Moreover, the subgraph made of plain thick or plain edges (resp. plain thick of dashed edges) only consists in a union of disjoint paths. The thick plain subgraph is only made of isolated edges and paths fo size 3. Finally, transitivity of the equality relationship enables to draw any path in any order: we shall take the left to right order by convention (no backtracking).

We denote by k 1 (resp. k 2 ) the number of plain (resp. dashed) edges. We also denote track k 3 the number of thick plain isolated edges, and k 4 the number of thick plain isolated paths of length 2. Figure 8 gives an example of such a dependency graph.

Appendix B. Proofs of Lemmas

B.1. Proof of Lemma 3.1 Proof For the control of X T we follow classical computations made in [START_REF] Bollobás | Random Graphs[END_REF] to establish asymptotic behavior of X T . For our purpose, we only need the two first moments. Assume that T is of size k = k(T) ≤ K, and that its automorphism group has a = a(T) elements. Then, letting µ = λs,

Indeed, we have n k choices for the nodes, then k! a ways of putting the edges.

We now compute E [X T (X T -1)] by classically counting the number of ordered pairs of distinct isolated tree components of G ∧ G isomorphic to T. This number is then multiplied by the probability of observing these two distinct isolated components. This gives

Denoting α = α(T) := nµ k-1 e -µk /a(T), these computations give that E [X T ] ∼ Var (X T ) ∼ α(T) when n → ∞, uniformly in k ≤ K(n) as soon as

Let us fix ε = ε(n) > 0 small enough. Applying Chebyshev's inequality together with the union bound gives

(ii) edges of Inter 1 : these are edges made with two vertices u, v in different trees T = T (but that may be ∼ to the same T ∈ T), and verifying u v. There are at most n 2 such edges. Since u v, there are only one possibility to map two edges of Inter 1 . The probability for a given edge of Inter 1 made of vertices of T ∼ T, T ∈ T being a common fixed edge is 1 (X T (X T -1)) r-1 , and edges of Inter 1 thus have a contribution in the expectation of at most n 4-2r+t/2 .

(iii) edges of Inter 2 : these are edges similar to case (ii), except that their endpoints belong necessarily to isomorphic trees, and verifying u v. There are at most n 2 such edges. Since u v, there are two ways to map two edges of Inter 2 . The probability for a given edge of Inter 2 made of vertices of T , T ∼ T being a common fixed edge is time

, and edges of Inter 2 thus have a contribution in the expectation of at most n 4-2r+t/2 .

Step 3. The first two steps show that E [F (σ i 1 , . . . , σ ir )|A] ≤ Cn 3-r+t/2 for all t > 0. Summing over all possible r-tuples of permutations, Markov inequality yields P (∃r ≥ 4, ∃σ i 1 , . . . , σ ir pairwise distinct, F (S, σ i 1 , . . . , σ ir ) ≥ 1) ≤ o(1) + ∞ r=4 p r Cn 3-r+t/2 ≤ Cp 4 n t/2-1 → 0, for t small enough, and P ∃σ i 1 , σ i 2 , σ i 3 pairwise distinct, F (S, σ i 1 , σ i 2 , σ i 3 ) ≥ n t ≤ o(1) + p 3 × Cn -t/2 → 0, and P ∃σ i 1 = σ i 2 , F (S, σ i 1 , σ i 2 ) ≥ n 1+t ≤ o(1) + p 2 × Cn -t/2 → 0.