Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
Jesús Arroyo Daniel L. Sussman Carey E. Priebe Vince Lyzinski




#1 1





	
  1]Jesús Arroyo
  2]Daniel L. Sussman
  1,3]Carey E. Priebe
  4]Vince Lyzinski
  [1]Center for Imaging Science, Johns Hopkins University
  [2]Department of Mathematics and Statistics, Boston University
  [3]Department of Applied Mathematics and Statistics, Johns Hopkins University
  [4]Department of Mathematics, University of Maryland
  
  Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks
    [
    
================================================================================





Given a pair of graphs with the same number of vertices, the inexact graph matching problem consists in finding a correspondence between the vertices  of these graphs that minimizes the  total number of induced edge disagreements. 
We study this problem from a statistical framework in which one of the graphs is an errorfully observed copy of the other. 
We introduce a corrupting channel model, and show that in this model framework, the solution to the graph matching problem is a maximum likelihood estimator (MLE). 
Necessary and sufficient conditions for consistency of this MLE are presented, as well as a relaxed notion of consistency in which a negligible fraction of the vertices need not be matched correctly. 
The results are used  to study matchability in several families of random graphs, including edge independent models, random regular graphs and small-world networks. 
We also use these results to introduce measures of matching feasibility, and experimentally validate the results on simulated and real-world networks.



Keywords:  Graph matchability, corrupting channel, consistency


1 




§ INTRODUCTION



Graphs are a popular data structure used to represent relationships between objects or agents, with successful applications in many different fields, including finance, neuroscience, biology, and sociology, among others. Many applications deal with multiple graph observations that can come as different instances of the graph for the same or related set of vertices, and thus studying these data jointly usually requires knowledge of the correspondence between the vertices first. When this correspondence is unknown or observed with errors, graph matching can be used to first recover the true correspondence before performing subsequent inference. Simply stated, the graph matching problem consists in finding an alignment between the vertices of two different graphs that minimizes a measure of dissimilarity between them (usually specified to be the number of edge differences).  This problem has found many useful applications in different areas including de-anonymizing social networks <cit.>, aligning biological networks <cit.>, and unsupervised word translation <cit.>, among others; see the surveys <cit.> for a review (up to 2016) of the graph matching literature and applications.




 §.§ The graph matching problem


Formally, given a pair of adjacency matrices for some graphs A = (E_1, V_1) and B=(E_2,V_2) with equal number of vertices |V_1|=|V_2| (where |V| denotes cardinality of a set of vertices V), the graph matching problem (GMP) consists of finding a mapping π:V_1→ V_2 which aligns the vertices between the two graphs to make the structure most similar; i.e., if Π_n is the set of n× n permutation matrices, then the GMP  is _P∈Π_nA-PBP^T_F, where E_F=(∑_i=1^n∑_j=1^nE^2_ij)^1/2 is the Frobenius norm of some matrix E∈ℝ^n× n.
Variants of this basic formulation have been proposed in the literature to accommodate more nuanced graph structure including, incorporating weighted and directed edges, |V_1|≠|V_2| <cit.>, 
vertex and edge covariates <cit.>, and matching multiple graphs simultaneously <cit.>.

A special case of the problem is
exact graph matching, also known as the graph isomorphism problem <cit.>, where the goal is to determine if there exists an alignment between the vertices of the graphs yielding identical edge structure across networks. 
Even for this special case, 
it is currently not known whether the problem is solvable in polynomial time.
However, an exact unique solution exists as long as there is no non-identity automorphisms (i.e., ∀ P≠ I_n, A≠ PAP^T) . 
In practice, the applicability of exact graph matching is limited due to the fact that data often consists of noisy observations of a graph, and thus one can only hope to recover an alignment that preserves a significant portion of the structure.

In the inexact version of the graph matching problem, a pair of graphs with the same number of vertices is observed, and the goal is to find an alignment of the vertices that best preserves the structure of the graphs.
This is often accomplished by minimizing an appropriate dissimilarity measure over all the possible permutations (e.g., the Frobenius norm formulation considered above). 


Several random graph models have been proposed in the recent literature, and these have been used to study the difficulty and feasibility of this problem. 
These models often parametrically enforce a natural similarity between the graphs while still allowing for structural differences.
They vary in complexity from correlated homogeneous Erdős-Rényi networks <cit.>, to correlated stochastic blockmodel networks <cit.>, to correlated general edge independent networks <cit.>, to independent graphon generated networks <cit.>.
Within these models, the dual problems of developing efficient graph matching algorithms and studying the theoretical feasibility of the GMP have been considered.
However, beyond (conditionally) edge-independent networks, few theoretical guarantees exist for either algorithmic performance (see <cit.> for an example of matching guarantees in a preferential attachment model).



 §.§ Graph matchability and maximum likelihood estimation



These random graph models have allowed for the exploration of the related notion of graph matchability:  given a natural correspondence between the vertex sets of two networks, can the GMP uncover this correspondence in some statistical sense <cit.>?
In this paper, we cast the problem of graph matchability in the framework of maximum likelihood (ML) estimation, equating matchability with the consistency of the maximum likelihood estimator (MLE) of an unknown correspondence.
The results bear a similar flavor to those in <cit.> (and <cit.>), wherein a model for correlated stochastic blockmodels is proposed.
In their framework, they showed that maximum a posteriori (MAP) estimation is the same as optimizing a weighted variant of the classical graph matching problem.
Unlike previous work, our model (see Section <ref>) is designed to be distribution-free, allowing for corrupted or correlated observations of arbitrarily structured networks to be considered.
We note that while we are not the first to frame the GMP as a ML estimation problem (see, for example, <cit.>), 
our model allows for a novel understanding of the relationship between the two, seemingly disparate, ideologies.

While maximum likelihood estimation is a core concept in modern statistical inference <cit.>, estimation of an unknown correspondence between two networks presents the challenge of ML estimation in the presence of a growing parameter dimension. Our model is parameterized by the shuffling permutation, which is the parameter of interest, and corrupting probabilities for each edge that are nuisance parameters.
Indeed, viewing the correspondence between vertices as a parameter to be estimated, this parameter naturally contains n-1 free variables, 
where n is the number of vertices in the observed network, while the number of nuisance parameters can grow as O(n^2).
Asymptotics (as n→∞, yielding n2 sample size) resist the classical theoretical framework when the number of (nuisance) parameters grow with the sample size (see, for example, <cit.>), and the MLE can be inconsistent in this  setting <cit.>.
Recently, statistical network inference (see, for example, <cit.>) has presented further examples of consistent ML estimation in networks when the parameter dimension is growing, notably for the inference task of community detection in stochastic blockmodel random graphs.

By equating consistent ML estimation with graph matchability, we provide another class of examples in the network literature for which consistency of the MLE is achieved as the graph size (and parameter dimension) increases.







The paper is organized as follows. In Section <ref> we introduce the  corrupting channel model and show that maximum likelihood estimation of the latent vertex correspondence is a solution to the graph matching problem (and vice versa). Next, in Section <ref> we derive necessary and sufficient conditions (depend on the structure of the given graph and the channel noise) for consistency of the MLE.
In Section <ref> we introduce a notion of quasi-consistency in which we allow a fraction of the vertices to be incorrectly matched, and present sufficient conditions to achieve this property.
Results of consistency and quasi-consistency of the MLE in a variety of random graph models are
presented, including some new results for small-world and random regular graphs. In Section <ref> we introduce a practical approach to studying matchability, and validate our theoretical results with numerical experiments  on simulated networks from popular random graph models and real-world data from different domains. We conclude with a discussion and remarks in Section <ref>.




§ EQUIVALENCE BETWEEN MAXIMUM LIKELIHOOD ESTIMATION AND GRAPH MATCHING




 §.§ Uniformly corrupting channel



Consider the set of undirected graphs with no self-loops and n labeled vertices, which we denote by 𝒢_n. Each graph will be represented with an adjacency matrix A∈{0,1}^n× n, which is symmetric and hollow (i.e., with zeros in the diagonal). Let p∈[0,1], P∈Π_n={n× n  permutation matrices}, and A∈𝒢_n. We model passing A through an edge and vertex-label corrupting channel as follows.

	
	Define the graph-valued random variable
	B_p,P (i.e., the channel-corrupted A)
	parameterized by (p,P) via
	B_p,P:=P(X∘ (1-A)+(1-X)∘ A)P^T,
	where X∈ℝ^n× n is a symmetric, hollow matrix with i.i.d. Bernoulli(p) entries in its upper triangular part, X is independent of A, and “∘" is the Hadamard matrix product.
	For ease of notation, we shall write B_p,P=B∼C(A,p,P) for B distributed as the channel corrupted A.

Note that if A is a graph-valued random variable, then we further assume that X is independent of A.
This model is similar to the noisily observed network models of <cit.>.  
Note that here we make no assumptions on the distribution of the underlying graph A; indeed, below we often view A as deterministic and not random, and consider the distribution of B conditional on A. 


Stated simply, B_p,P is formed by first uniformly corrupting (i.e., bit-flipping) edges in A independently with probability p and then shuffling the labels via P.
Given observed (A,B), the likelihood of (p,P) in this model is given by

    L(p,P)=∏_i<j (1-p)^1{A_i,j=(P^TBP)_i,j}p^1{A_i,j≠(P^TBP)_i,j},

so that the log-likelihood is given by

    ℓ(p,P)   =∑_i<j1{A_i,j=(P^TBP)_i,j}log(1-p)+1{A_i,j≠(P^TBP)_i,j}log p
       =1/2tr(AP^TBP)log(1-p) + 1/2(n(n-1) -tr(AP^TBP)log p)
       = 1/2tr(AP^TBP)(log(1-p)-log p) + n(n-1)log p/2,

and given a fixed value of p, observing that 2tr(AP^TBP)=A_F^2+B_F^2 - A-P^TBP_F^2, the (possibly non-unique) MLE of P is then given by







    P̂_MLE=any P∈_P∈Π_nA-P^TBP_F^2    for p<1/2
    any P∈argmin_P∈Π_nA-P^TB̆P_F^2     for p>1/2
    any P∈Π_n    for p=1/2,

where B̆ is the complement of the graph B (i.e., B̆_ij=1-B_ij). In the p<1/2 setting, the problem of maximum likelihood estimation is equivalent to the problem of graph matching, as the classical GMP formulation is to find the (possibly non-unique) minimizer of a quadratic assignment problem (QAP) of the form

    P̂_GM∈_P∈Π_nA-P^TBP_F^2

Analogously, when p>1/2, ML estimation is equivalent to matching one graph with the complement of the other. 

A natural first question to ask is what properties 
A (and p) must possess in order for the MLE for P to be consistent, and hence the vertex-label corruption introduced into B can be undone via graph matching. 
We note here that the parameter dimension of P is growing in n and classical ML estimation consistency results do not directly apply (see, for example, <cit.>).
Nonetheless, in Section <ref> our main result, Theorem <ref>, will establish consistency of the MLE under fairly modest assumptions on A and p. 























 §.§ Heterogeneous corrupting channel



The uniform corrupting channel model defined above assumes that all edges of A are corrupted with the same probability. However, in some cases it is more reasonable to consider a model in which each pair of vertices might be corrupted with different probabilities. For example, we can consider the setting in which edges and non-edges in A are corrupted by the channel independently with different probabilities, or in which certain vertices or edges are more likely to be corrupted. 
Thus, we also consider an heterogeneous corrupting channel defined as follows.


	Let Ψ^(m)∈[0,1]^n× n, m=1,2  be two matrices that correspond to the corrupting probabilities for edges and non-edges, and P∈Π_n. For a given adjacency matrix A∈{0,1}^n× n, we define B_Ψ^(1),Ψ^(2),P as
	
    B_Ψ^(1),Ψ^(2),P=P( X ∘ (1-A)+ (1-Y) ∘ A)P^T,

	where X and Y are symmetric hollow matrices such that X_ij∼Bernoulli(Ψ^(1)_ij) and Y_ij∼Bernoulli(Ψ^(2)_ij) and {X_i,j,Y_i,j}_i<j are independent. 
	Dropping subscripts to ease notation when possible, we denote it via B ∼C(A, Ψ^(1), Ψ^(2), P) for B distributed as the heterogeneous corrupting channel A.

Note that if A is a graph-valued random variable, then we further assume that X and Y are independent of A. The heterogeneous corrupting channel model is saturated, but the only parameter of interest is P.

The flexibility of having different corrupting probabilities for each edge allows us to include other popular graph models within this framework. 
In particular, if A∼Bernoulli(Λ), the heterogeneous corrupting channel model can be used to describe the distribution of a pair of correlated Bernoulli graphs conditional on the first graph. 
In more detail, given a pair of hollow symmetric matrices R,Λ∈[0,1]^n× n, the pair of graphs A,B is said to be distributed as R-correlated random Bernoulli(Λ) graphs if marginally A, B∼Bernoulli(Λ) (i.e., for 1≤ i<j≤ n, A_ij are independently distributed as Bern(Λ_ij) random variables; similarly for B) and each pair of variables A_ij,B_ℓ k,  1≤ i<j≤ n, 1≤ℓ<k≤ n, (i,j)≠ (ℓ, k) are mutual independent, except that for each 1≤ i<j≤ n, corr(A_ij,B_ij) = R_ij.  Note that in the correlated Bernoulli graphs model, P(B_ij=1|A_ij) = A_ijR_ij + (1-R_ij)Λ_ij, so the distribution of B conditioned on A can be written using an heterogeneous channel with 

    Ψ^(1)_ij    =     (1-R_ij)Λ_ij
    Ψ^(2)_ij    =     (1-R_ij)(1-Λ_ij).

This correlated Bernoulli graph model, and in particular, the correlated Erdős-Rényi (ER) model (in which  each of the matrices Λ and R have the same value in all the entries), have been extensively used in studying the inexact graph matching problem <cit.>. The corrupting channel model is thus comprehensive enough to include other popular settings in literature (see for example Corollary <ref> for a result in correlated ER graphs), while allowing to extend some of the results to graphs with arbitrary structure.


In the heterogeneous corrupting channel, the MLE of the unshuffling permutation is also exactly equivalent to the minimizer of the graph matching objective (<ref>). Note that in this case, the likelihood is given by

    ℓ(Ψ^(1), Ψ^(2),P)     =    ∑_i<j{ (P^TBP)_ijlog((1- Ψ^(1)_ij)A_ij +Ψ^(2)_ij(1-A_ij)) .
          .   + (1-(P^TBP)_ij)log( Ψ^(1)_ijA_ij + (1-Ψ^(2)_ij)(1-A_ij) ) }.

In general, the MLE for P in this model is not unique since the corrupting probabilities can arbitrarily alter the graph. Thus, we impose a further assumption that the probability of any pair of corresponding edges in the graphs A and B to be the same is at least 0.5. Formally, let p̃ = max_i,j,kΨ^(k)_ij be the largest corrupting probability for an edge. Under the assumption that p̃≤1/2, for a given P∈Π_n we can calculate a  profile MLE for Ψ^(k), k=1,2, denoted by Ψ̂^(k)(P), as

    (Ψ̂^(k)(P))_ij =
    
    0    if A_ij=(P^TBP)_ij,
    1/2   if A_ij≠  (P^TBP)_ij
    .

Thus, the profile loglikelihood for P can be expressed as

    ℓ(Ψ̂^(1)(P),Ψ̂^(2)(P),P)     = ∑_i<j 21(A_ij≠(P^TBP)_ij)  log(1/2) 
        =   -log(2) A - (P^TBP)_F^2,

which does not depend on the particular values of Ψ̂^(1)(P), Ψ̂^(2)(P) and is proportional to the graph matching objective (<ref>). Therefore, the (possibly non-unique) MLE for P, given by

    P̂_MLE∈_P∈Π_nℓ(Ψ̂^(1)(P),Ψ̂^(2)(P),P)

is exactly equivalent to the solution of the GMP.

 








































§ CONSISTENCY OF THE MAXIMUM LIKELIHOOD ESTIMATOR



For a given positive integer n_0, consider a sequence of graphs (A_n)_n=n_0^∞ (with the order of A_n being n).
For the parameter sequence ( (p_n,P_n) )_n=n_0^∞, consider the sequence of channel-corrupted A_n's defined via

    (B_n=P_n(X_n∘ (1-A_n)+(1-X_n)∘ A_n)P_n^T )_n=n_0^∞,

where each X_n is a symmetric, hollow matrix with i.i.d. Bernoulli(p_n) entries in its upper triangular part,
and the X_n's are mutually independent across index n.
In this setting, we define consistency of a sequence of estimators as follows.

	
	With (B_n∼C(A_n,p_n,P_n))_n=n_0^∞ defined as above, for n≥ n_0 
	
	we say that a sequence of estimators (P̂_n:=P̂_n(A_n,B_n))_n=n_0^∞ of (P_n)_n=n_0^∞, 
	is a [   weakly; strongly ] consistent estimator if P̂_n-P_n_F[   P →; a.s.→ ]0 as n→∞, for all sequences (P_n)_n=n_0^∞.


As the MLE of (P_n)_n=n_0^∞ is not necessarily uniquely defined (i.e., there are multiple possible MLEs for a given n), we write that the MLE of (P_n)_n=n_0^∞ is 
[   weakly; strongly ] consistent if max_Q_n∈𝒫^*_nQ_n-P_n_F[   P →; a.s.→ ]0 as n→∞,
where

    𝒫^*_n=_P∈Π_nA_n - P^TB_nP^2_F.

Note that, as max_Q_n∈𝒫^*_nQ_n-P_n^2_F is integer-valued, strong consistency of the MLE is equivalent to

    (max_Q_n∈𝒫^*_nQ_n-P_n^2_F=0 for all but finitely many n)=1
       ⟺(𝒫^*_n={P_n} for all but finitely many n)=1.


Loosely speaking,  a estimator
is consistent if the number of vertices that are incorrectly matched by the estimator goes to zero as the size of the graph increases.
It is clear that consistency of an estimator hinges on the properties of (A_n)_n=n_0^∞.
Indeed, if infinitely many A_n have a non-trivial automorphism group, so that there is at least one Q_n∈Π_n such that Q_n≠ I_n but A_n=Q_n^TA_nQ_n, then the MLE has no hope of consistency in the strong or weak sense. In those circumstances, the most we can hope is that the MLE converges to an element within the automorphism group of the graph (see Remark <ref>). If, on the other hand, the A_n's are sufficiently asymmetric (see Theorem <ref> below for a precise definition of this) then the MLE will be strongly consistent under mild model assumptions.

Before stating the theorem, recall that two permutation matrices Q,Q'∈Π_n are disjoint if each one permutes different vertices, that is, if σ_Q,σ_Q' are the permutations associated to each matrix, then {i  s.t. σ_Q(i)≠ i}∩{i  s.t. σ_Q'(i)≠ i}=∅. The same definition holds for sets of k permutations.
To wit we have the following result (the proof is provided in Appendix <ref>).



	
	Let n_0>0, and consider a sequence of graphs (A_n)_n=n_0^∞.  
	Define the sequence (B_n∼C(A_n,p_n,P_n))_n=n_0^∞ of channel-corrupted A_n's with parameter sequence ( (p_n,P_n) )_n=n_0^∞ and p_n<1/2.



	
		
  i. For each n≥ n_0 and each k∈[n], k≥ 2, let Π_n,k be the set of permutation matrices in Π_n permuting precisely k labels.
		If there exists an n_1≥ n_0 such that for all n≥ n_1 and k∈[n],
		
    min_Q∈Π_n,kA_n - Q^T A_nQ^2_F>6klog(n)  /log(1/4p_n(1-p_n))        ∀ k ≥ 2,

		then 
		the MLE of (P_n)_n=n_0^∞

		is strongly consistent.
		
		
		
		
		
		
		
		
		
		
		
		
  ii. If for infinitey many n>n_0 there exists a sequence (k_n) with k_n=Θ(1) and a set of disjoint permutations S_n⊂ (∪_i=2^k_nΠ_n,i)∖{P_n} with |S_n| = Θ(n) , such that
		
    min_Q_n∈ S_nlog(1/4p_n(1-p_n))(A_n -Q_n^T A_nQ_n^2_F)=ω(1)
       max_Q_n∈ S_nlog(1/4p_n(1-p_n))A_n -Q_n^T A_nQ_n^2_F/logA_n -Q_n^T A_nQ_n^2_F=o(1)

		then the MLE of (P_n)_n=n_0^∞ is not weakly consistent. 
		
  iii. If for infinitely many n≥ n_0, there exists Q_n∈Π_n∖{P_n} such that 
		
    log(1/4p_n(1-p_n))A_n - Q_n^T A_nQ_n^2_F= O(1),

		then the MLE of (P_n)_n=n_0^∞ is not weakly consistent.
	
	


The previous theorem presents necessary and sufficient conditions  in the sequence of graphs (A_n) to determine whether  the MLE for the unshuffling permutation is consistent. Equation (<ref>) quantifies how different A_n needs to be from any shuffled version Q^TA_nQ so that the minimizer of the GMP matches the vertices correctly in the limit. Although verifying this condition for a given graph is computationally hard, it can be shown to hold with high probability via a union bound in some popular random graph models, including the Erdős̋-Rényi model (see Corollaries <ref>, <ref> and <ref>). Note that for a given sequence of graphs (A_n)_n=1^∞, Equation (<ref>) implies that any sequence of corrupting probabilities (p_n) such that

    p_n ≤min_k∈[n]{p_n,k^∗ := min_Q∈Π_n,k[1/2 - 1/2(1 - exp(-6klog n/A_n- Q^T A_nQ^2_F))^1/2]}.

 will ensure that the MLE is strongly consistent. The right hand side of Equation (<ref>) thus quantifies how much noise can be supported by the graph, and hence provides a measure of  matching feasibility. 


 
The second and third parts of Theorem <ref> provide sufficient conditions for inconsistency of the MLE. If for infinitely many values of n there are  enough permutations Q_n∈Π_n∖{I_n} for which A_n - Q_n^TA_nQ_n_F^2 is small, then there is a non-negligible probability that A_n-Q_n^T(P_nBP_n^T)Q_n_F^2 ≤A_n-P_nBP_n^T_F^2
for some Q_n, and hence, the MLE is not consistent.  The number of permutations required for this to happen depends on how small  A_n - Q_n^TA_nQ_n_F^2 is, and only one permutation is enough if Equation (<ref>) hold, or Θ(n) of them with the weaker bound in Equation (<ref>). Note that condition (<ref>) can essentially be dropped since when this condition fails then (<ref>) holds. Conditions (<ref>)–(<ref>) imply that p_n→ 1/2 and so log(1/(4p_n(1-p_n)))=(1+o(1)) (1/2-p_n)^2; this fact will be used often in the sequel  (for example, in Corollary <ref>). Finally, for part ii.,  observe that when max_Q∈ S_nA_n-Q_n^TA_nQ_n_F^2=Ω(n^δ) for some δ>0, then the rates in Equations (<ref>)  and (<ref>) have the same order.




 
    Denote by Aut(A_n)={Q∈Π_n: Q^TAQ = A} the automorphism group of a graph A_n. As mentioned before, when Aut(A_n)≠ I_n for infinitely many values of n, there is no hope of consistency, but the estimator might still converge to an element within the automorphism group of the graphs so that P̂_n^T (P_nA_nP_n^T)P̂_̂n̂ - A_F^2→ 0 in some weak or strong sense. In this setting, it is possible to derive a result analogous to Theorem <ref> by counting the number of edge disagreements A_n-Q^T_nA_nQ_n_F^2 only for the permutations  Q_n∈Π_n∖Aut(A_n). The statement and proof of this result are analogous to Theorem <ref>.
















While the correlation structure between A and B in the above Theorem is different than the ρ-correlated Bernoulli model of <cit.>, this theorem, in a sense, partially unifies many of the edge-independent matchability results appearing in previous work <cit.>.
To wit, we have the following corollary,

whose proof follows immediately from Theorem <ref> and results in <cit.> (see Appendix <ref> for proof details).


	
	Let n_0>0, and consider an independent sequence of graphs (A_n)_n=n_0^∞ where for each n, A_n∼Bernoulli(Λ_n) with α_n≤Λ_n≤ 1-α_n entry-wise.  
	Define the sequence (B_n∼C(A_n,p_n,P_n))_n=n_0^∞ of channel-corrupted A_n's with parameter sequence ( (p_n,P_n) )_n=n_0^∞ and p_n<1/2.
	
	
	If α_n(1/2-p_n)=ω( √(log n/n)),
	then the MLE (obtained by solving the GMP) is strongly consistent.



The Erdős-Renyi model (ER) <cit.> G(n,α), α∈(0,1) is a particular example of a Bernoulli graph Bernoulli(Λ) in which all entries of Λ are equal to α, and hence the result of the previous corollary directly applies. By considering concentration bounds on the number of edges in Erdős-Rényi G(n,α) random graphs (i.e., the number of edges is in nα±√(nlog n) with high probability) and the growth rate of α_n in Corollary <ref>, we arrive at the following corollary for Erdős-Renyi graphs G(n,m) (i.e., uniformly distributed on the set of graphs with exactly m∈N edges): 

	
	
	
	Let n_0>0, and consider an independent sequence of graphs (A_n)_n=n_0^∞ where for each n, A_n∼G(n,m_n). 
	Define the sequence (B_n∼C(A_n,p_n,P_n))_n=n_0^∞ of channel-corrupted A_n's 
	with p_n<1/2.
	
	
	If 
    m_n(1/2-p_n)=ω( √(nlog n)),

	then the MLE of ( P_n)_n=n_0^∞ is strongly consistent.
	
	


Small-world graph models aim to reproduce the property that in many real networks the clustering coefficient is relatively small and paths between any pair of vertices have a short length, usually of order log n <cit.>. The Newman-Watts (NW) model <cit.>—a more easily analyzed variant of the original Watts-Strogatz model —is one such model that adheres to these properties with high probability. 
The NW model NW(n,d,β) starts with a d-ring lattice A in which each vertex is connected with all neighbors that are at a distance no larger than d; that is, A_ij=1 whenever 0<|i-j| mod(n-1-d)< d. To generate a small-world behavior, random edges are added independently with probability β between vertices that are not connected in the d-ring lattice, so A_ij∼Bernoulli(β) for |i-j| mod(n-1-d)≥ d. 

In the Newman-Watts model, the average path length when β=0 is O(n/d_n), and as β increases and more edges are added to the graph, there is a phase transition in which the small-world property appears. The next corollary establishes a similar phenomenon in the matching feasibility context: when β is small, the MLE is not weakly consistent for matching a NW graph A with a random copy generated from the corrupting channel model, but once there are enough random edges  included, the MLE becomes strongly consistent and hence graph matching is feasible. See Appendix <ref> for the proof details.


	Let n_0>0 and consider (A_n)_n=n_0^∞ an independent sequence of graphs such that A_n∼ NW(n, d_n, β_n). Define (B_n)_n=n_0^∞ as a sequence of channel corrupted graphs with B_n∼C(A_n, p_n, P_n) and p_n<1/2. 
	
		
  * For any sequence (d_n)_n=n_0^∞, if (1/2-p_n)^2=o(√(log n/n)) and
		
    β_n=o(log n/(1/2-p_n)^2n),

		then the MLE of (P_n)_n=n_0^∞ (obtained by solving the GMP (<ref>)) is not weakly consistent.
		
  * If d_n=o(β_n^2 n), β_n≤ 1/2 and 
		
    β_n = ω(√(log n/(1/2 - p_n)^2n)) ,

		then the MLE of (P_n)_n=n_0^∞ is strongly consistent.
	 

Using  results on the diameter of Erdős-Renyi graphs <cit.>, it can be verified that if β_n satisfies Equation (<ref>) for a fixed value of p_n<1/2 and β_n=ω(1/n), then diam(A_n) = O(log (n)/log(nβ_n)). Thus, there is a regime for β_n in which NW graphs are small-world but the MLE is not consistent.  However, since ω(1) = log(nβ_n) = o(loglog n) in this regime, the diameter of the graph  is close to O(log n) and hence it is not far from the phase transition of small-world graphs. If part b) of  Corollary <ref> holds, then diam(A_n) = O(1), so the average path length in NW graphs with a strongly consistent MLE is much smaller than  in small-world graphs.

Corollary <ref> also suggests a way of making any given graph A, with a sufficiently large number of vertices n, matchable with a graph corrupted with probability p. 
By setting β=√(log(n)/((1/2-p)^2n)) as in Equation (<ref>) and generating a graph A'∼C(A, β, I), the solution of the graph matching problem between A' and B will correctly align all of the vertices with high probability. 
This result can have applications in settings such as network anonymization <cit.> and differential privacy <cit.>, among others.





 §.§ Consistency on the heterogeneous corrupting channel



We now present a more general version of Theorem <ref> for the heterogeneous corrupting channel introduced in Section <ref>. In the heterogeneous model, Ψ^(1) and Ψ^(2) are nuisance parameters when estimating the permutation parameter P, so the number of nuisance parameters is n(n-1), which scales with the sample size. Moreover, as can be observed from Equation (<ref>), the MLE of these parameters is not consistent.  In this setting, one should be careful when using the MLE for P since this estimator can be  inconsistent as shown in the famous Neyman-Scott paradox <cit.>. Fortunately, this is not the case here and the MLE can consistently estimate P.  See Section <ref> for the proof of this Theorem.


	
	Let n_0>0, and consider a sequence of graphs (A_n)_n=n_0^∞.  
	Define the sequence (B_n∼C(A_n,Ψ^(1)_n, Ψ^(2)_n,P_n))_n=n_0^∞ of channel-corrupted A_n's with parameter sequence ( (Ψ_n^(1),Ψ_n^(2),P_n) )_n=n_0^∞ and p̃_n:=max_i,j,k(Ψ^(k)_n)_ij<1/2, p̆_n=min_i,j,k(Ψ^(k)_n)_ij≥ 0.

	
		
  i. For each n≥ n_0 and each k∈[n], k≥ 2, let Π_n,k be the set of permutation matrices in Π_n permuting precisely k labels.
		If there exists an n_1≥ n_0 such that for all n≥ n_1 and k∈[n],
		
    min_Q∈Π_n,kA_n - Q^T A_nQ^2_F>6klog(n)  /log(1/4p̃_n(1-p̃_n))        ∀ k ≥ 2,

		then 
		the MLE of (P_n)_n=n_0^∞ is strongly consistent.

		
		
  ii. If for infinitely many n>n_0 there exists a sequence (k_n) with k_n=Θ(1) and a set of disjoint permutations S_n⊂ (∪_i=2^k_nΠ_n,i)∖{P_n} with |S_n| = Θ(n), such that 
			
    min_Q_n∈ S_nlog(1/4p̃_n(1-p̃_n))(A_n -Q_n^T A_nQ_n^2_F)=ω(1)
       max_Q_n∈ S_nlog(1/4p̆_n(1-p̆_n))A_n -Q_n^T A_nQ_n^2_F/logA_n -Q_n^T A_nQ_n^2_F=o(1)

		then the MLE of (P_n)_n=n_0^∞ is not weakly consistent. 
		
  iii. If for infinitely many n≥ n_0, there exists Q_n∈Π_n∖{P_n} such that 
		
    log(1/4p̆_n(1-p̆_n))A_n - Q_n^T A_nQ_n^2_F= O(1),

		then the MLE of (P_n)_n=n_0^∞ is not weakly consistent.
	



As described in Section <ref>, the heterogeneous corrupting channel model can describe pairs of Bernoulli graphs with correlated edges. In particular, the correlated Erdős-Rényi graph model with parameters q,ρ∈[0,1], denoted as ρ-ER(q) generates  a pair of networks A,B that are marginally distributed as Erdős-Rényi A,B∼G(n,q), but  each pair of corresponding edges satisfies corr(A_ij,B_ij)=ρ, while the rest of the variables are mutually independent. The following result shows the consistency of the MLE in this model.


	Let n_0>0, and consider an independent sequence of graphs (A_n,B_n)_n=n_0^∞ where for each n, (A_n,B_n)∼ ρ_n-ER(q_n), with q_n≤ 1/2 and p̃_n:=(1-q_n)(1-ρ_n)≤ 1/2. 
	If q_nlog(1/4p̃_n(1-p̃_n))=ω( log n/n) and q_n=ω( log n/n),
	then the MLE (obtained by solving the GMP) is strongly consistent. 


The correlated Erdős-Rényi model has been popularly used to study the performance of different methods in solving the graph matching problem <cit.>, and in particular, <cit.> established the information-theoretic threshold  for exact recovery of the unshuffling permutation. The parameterization of the corrupting channel model and the constraint on the parameters to obtain the equivalence between MLE and the GMP enforces some additional restrictions in our setting, but we can verify than in some parameter regimes the rates of Corollary <ref> are optimal. For example, when the graphs are dense and q_n=1/2, the conditions of Corollary <ref> reduce to log(1/4p̃_n(1-p̃_n))∼ρ_n=ω(√(log n/n)), achieving the information theoretic rate <cit.>. Similarly, when ρ_n=Ω(1), the requirement on the density of the graphs is q_n=ω(log n/n).


    A further generalization of the heterogeneous corrupting channel model can consider dependent noise, in which the random variables {X_i,j, Y_i,j}_i<j introduced in Definition <ref> are dependent.
    Concentration results for sums of dependent random variables can be used to obtain  an analogous statement to part i. of Theorem 9 for a suitable dependence structure between the edges <cit.>.
    




§ RELAXED CONSISTENCY



In many label recovery settings in the network literature, consistency is defined as recovering the correct labels of all but a small, vanishing fraction of the vertices; for examples in the community detection literature, see <cit.>, in the graph matching literature, see <cit.>.
In real data settings, networks are often complex, heterogeneous objects, and defining consistency as perfect recovery of the alignment/labels is an often unrealistic standard to apply in practice.
This is especially the case in the presence of network sparsity, as often
recovering the alignment/labels of low degree vertices is practically and theoretically impossible.


In our errorful channel setting it is entirely reasonable to expect low-degree vertices in A to have their labels irrevocably permuted by the channel permutation P.
We demonstrate this in the following illustrative example.

	
	
		Consider A_n constructed as follows.  Let G_n∼G(n-2,q) be an ER graph for fixed q.  A_n is then formed by 
		attaching two leaves (labeled n-1 and n) to G_n at two uniformly randomly chosen elements of G_n.
		Form B_n via the channel parameters (p_n,P_n) with p_n=p fixed and P_n the transposition of n-1 and n. 
		It is immediate that with probability at least p^2 (i.e., if the two edges connecting the leaves to G_n are corrupted), the MLE will not equal P_n.


In the previous example, we see that the MLE will often be unable to recover periphery vertex labels. 
However, in Example <ref> it is not difficult to see that for p fixed, the MLE will recover all but potentially the two peripheral vertex labels.
It will be practically useful to extend the definition of consistency to account for these situations where the MLE can recover almost all of the vertex labels.
This motivates our next definition.

	
	
	For a sequence of numbers (α_n)_n=n_0^∞,
	we say that a sequence of estimators (P̂_n:=P̂_n(A_n,B_n))_n=n_0^∞ of (P_n)_n=n_0^∞,
	is a [   weakly; strongly ] α_n-consistent estimator of (P_n)_n=n_0^∞ if 
    Q-P_n_F/α_n[   P →; a.s.→ ]0
 as n→∞ for all sequences (P_n)_n=n_0^∞.

As before, as the MLE of (P_n)_n=n_0^∞ is not necessarily uniquely defined (i.e., there are multiple possible MLEs for a given n), we write that the MLE of (P_n)_n=n_0^∞ is 
[   weakly; strongly ] α_n-consistent if 
    max_Q_n∈𝒫^*_nQ_n-P_n_F/α_n[   P →; a.s.→ ]0
 as n→∞,
where

    𝒫^*_n=_P∈Π_nA_n - P^TB_nP^2_F.



This relaxed definition allows us to consider situations in which the MLE will correctly align all but a vanishing fraction of the vertices in (A_n,B_n); indeed, if α_n=o(n), then the fraction of misaligned vertices is o(1). Note also that a consistent estimator according to Definition <ref> is Θ(1)-consistent, and viceversa.
In the remainder of this section, we will establish α_n consistency for a variety of models.



Example <ref> continued.  Consider A_n as constructed in Example <ref>.  If we consider p_n≡ p<1/2 fixed, then it is immediate that the MLE will be strongly α_n-consistent for any α_n=ω(1).
Indeed, with high probability the only two vertices potentially misaligned by the MLE for n sufficiently large are the two leaves attached to G_n. 




The notion of α_n-relaxed consistency allows to have at most o(α_n) vertices incorrectly matched, and hence, to check whether an estimator is consistent it is enough to only consider the permutations that permute at least Ω(α_n) vertices. Hence, the α_n-consistency analogue of Theorem <ref>, parts i. and iii., can be formulated as follows.
The proof is omitted, as it follows the proof of Theorem <ref> mutatis mutandis by only considering permutations of enough vertices.


	
	Let n_0>0, and consider a sequence of graphs (A_n)_n=n_0^∞.  
	As above, define (B_n)_n=n_0^∞ to be the sequence of channel-corrupted A_n's with parameter sequence ( (p_n,P_n) )_n=n_0^∞ and p_n<1/2. If we have that there exists an n_1≥ n_0 such that for all n≥ n_1
	
    min_Q∈Π_n,kA_n -Q^T A_nQ^2_F≥6klog(n)  /log(1/4p_n(1-p_n))        ∀ k ≥ k_n,

	then the MLE of (P_n)_n=n_0^∞ is strongly α_n-consistent for any sequence (α_n)_n=n_0^∞ with α_n=ω(k_n).
	







	







	
	
	
	
	
	
	
	
	
	
	
	
	
	












The  previous theorem is analogous to part i. of Theorem <ref>, but here Equation (<ref>) is only required to hold for permutations that shuffle at least k_n vertices, so if k_n=ω(1) then condition a) is significantly weaker. 
Part ii. of Theorem <ref> requires the existence of a set with Θ(n) disjoint permutations, so most permutations in this set need to be permuting Θ(1) vertices, hence this statement is capturing the setting when the MLE with high probability will not align a small (Θ(1) in the Theorem) number of vertices. As such, it is not immediate what the α_n-consistency analogue of this result would be.

Our next result partially extends Corollaries <ref> and <ref> to the case of random regular graphs. Let A∼G_n,d be shorthand for A is uniformly distributed on the set of d-regular, n-vertex graphs. Solving the exact version of the graph matching problem (that is, for p=0 in the corrupting channel model) is usually (at least theoretically) possible, as these graphs almost surely have a trivial automorphism group under mild assumptions <cit.>. 
The next corollary thus partially extends this result to the inexact graph matching setting (proof provided in Appendix <ref>). 



	
	Let ϵ∈(0,1/3) be fixed, and consider d_n=ω(n^2/3+ϵ) (with d_n bounded away from n). 
	There exists a constant C>0 such that 
	if A∼G_n,d_n and 1/2 - p_n ≥√(Cd_n^-1log n),
	then the MLE of  (P_n)_n=n_0^∞ is strongly α_n-consistent for α_n=ω(n^2/3).


The previous result raises the question of whether there will always be a fraction of misaligned node in a random regular graph. Although we do not have a definite answer, it is possible to  construct non-trivial examples of  sequences of d-regular graphs for which the MLE is not strongly consistent according to Definition <ref>. In fact, consider A_n as the d_n-ring lattice with n vertices and any sequence of (d_n). Then, according to parth a) of Corollary <ref>, the MLE is not strongly consistent for any (P_n)_n=n_0^∞. Numerical simulations on the d_n-ring lattice (see Section <ref>) suggest that for the d_n-ring lattice in particular, a large fraction of the vertices can be correctly aligned if d_n is large enough.


































§ EXPERIMENTS


In light of the theoretical results presented in the previous sections, we perform experiments to study the matchability of channel corrupted graphs. Using simulated and real data, we study the question of whether the vertices of a given graph are matchable to the vertices of a random graph generated after passing the original graph through a corrupting channel.

As observed in the previous sections, the feasibility of graph matching in the errorful channel model depends on the number of edge disagreements between the original graph and a shuffled version of it. 
Equation (<ref>) provides an upper bound on the probability p_n of the corrupting channel model that ensures that the MLE is a consistent estimator;
indeed, min_k p^∗_n,k gives a measure of how much noise can a graph A safely tolerate while keeping the feasibility of perfect graph de-anonymization in the limit. 
Similarly, using the result in Theorem <ref>, min_k≥ k_0 p_n,k^∗ gives a (limiting) measure of how much noise can a graph A safely tolerate while keeping the feasibility of de-anonymizing all but o(k_0) of the vertices. 
The value of p^∗_n,k depends on X_k,min(A) =min_Q∈Π_n,kA-Q^TAQ_F^2, the smallest number of edge disagreements over all permutations of k vertices.  Computing the exact value of p^∗_n,k is infeasible for large values of k, but using a sample of random permutations we can obtain an exact upper bound for p^∗_n,k, given by

    p̂^∗_n,k(A) = 1/2 - 1/2(1-exp(-6klog n/X̂_k,min(A)))^1/2,

where X̂_k,min(A)=min_i=1,…,mA-Q_i^TAQ_i_F^2 for a set of random permutations Q_1,…,Q_m, uniformly distributed on Π_n,k. Note that this bound p̂_n,k^∗ might be loose compared with the one in Equation <ref>, as only one permutation that was not sampled can decrease X_k,min significantly. Nevertheless, as observed in Section <ref>,  in many random graph models (including edge-independent graphs), the distribution of A_n-Q^TA_nQ_F^2 is usually bounded away from zero.



In addition, motivated by the bounds in Theorems <ref> and <ref>, we estimate the average value of A-QAQ^T_F^2 where Q∼Unif(Π_n,k) by
counting the number of edge disagreements introduced in A by a uniform shuffling of k vertices, and calculate

    X_k(A) = 1/m∑_i=1^m 1/2A-Q_i^TAQ_i_F^2.

In both cases, we generate a sample of m=1000 permutations.
In practice, we have found that larger values of X_k(A) indicate that graph matching (at least recovering all but k labels) is more feasible. 
We use a normalized version of this quantity 1/klog nX̂_k(A) to compare this number between different permutation sizes and number of vertices, where the normalizing constant is motivated by Theorem <ref>. 

These two statistics, p̂_k^∗(A) and X̂_k(A), are calculated for different values of k, 
and they are used  to compare matching feasibility in a variety of graphs generated from popular statistical models and real networks from different domains. In addition, we compare the results of these statistics with the  accuracy of  a matching algorithm for a given graph A and a corrupted version of it. Specifically, for a given graph A we generate a corrupted graph B∼C(A, p, P) using the channel model, and approximately solve the resulting GMP (<ref>) to estimate the MLE (as described below). We measure the number of incorrectly matched vertices P̂-P_F^2 for different values of p, and compare these results with the feasibility measures previously obtained. 


In practice, computing the MLE of the unshuffling permutation is computationally unfeasible in general since solving the GMP requires to perform an exhaustive search  over the discrete space of n! permutations; provably polynomial time algorithms  are only known for certain models such as correlated Erdős̋-Rényi graphs <cit.>. We obtain an approximate solution to the GMP  with the Fast Approximate Quadratic programming algorithm  <cit.>, which uses the Frank-Wolfe methodology <cit.> to solve an indefinite relaxation of the graph matching objective function before projecting the relaxed solution to the feasible space of permutations.
Frank-Wolfe is a constrained gradient descent procedure, and the algorithm terminates in a permutation P̂^FAQ that is an estimated local minimum of the relaxed GMP objective function. The computational complexity of this method is O(n^3), but because it is solving a non-convex optimization problem, there is no guarantee that the global minimum is achieved. When the indefinite relaxation problem is solved exactly, it recovers the correct permutation almost always in correlated Bernoulli graphs <cit.>.






 §.§ Simulations


In the first example, we generate graphs from two popular graph models and compare the effect of the parameters that control the structure of the network. First, we simulate Erdős-Renyi graphs  G(n,α) with n=500 vertices and rate α, changing the value of α∈{0.1,0.2, 0.3, 0.4, 0.5} to compare the effect of the average degree. 
We also generate graphs using the Watts-Strogatz small-world model WS(n, d, β), which are very similar to the Newman-Watts model (see Corollary <ref>); these graphs are intended  to produce graphs with the small-world property. 
The WS model is  initialized with a regular d/2-ring lattice like the NW model, and each edge is randomly rewired with probability β. As β increases, the distribution of the WS model becomes more similar to an ER graph. 

For each graph, we compute the estimated probability bounds p̂^∗_k(A) and the normalized average disagreements 1/klog nX̂(A) according to equations (<ref>) and (<ref>). We generate 35 random graphs according to each model and compute the average quantities.
These results are summarized on Figure <ref>. 
We can see that in the ER model channel probability bounds and the average number of disagreements increase  with  α, which suggests that matching in the corrupting channel model becomes more feasible as the average degree of the graph increases, and verifies the results in Corollary <ref>. Graphs with a WS distribution increase their matchability measures as the rewiring probability increases in accordance to Corollary <ref>, and this suggests that graphs that have a more uniformly random structure are easier to match.  
Matching all the vertices correctly in the WS model is difficult when β is small since the near degree regularity ensures that vertices are very similar to their neighbors, and hence switching a few of the vertices with their neighbors causes a small number of disagreements. 
This result agrees with Corollary <ref> for the related Newman-Watts small-world model. Nevertheless, Figure <ref> also shows that even for small β, permuting a large fraction of vertices also causes this probability bound to increase significantly, and by Theorem <ref> this suggests that it might be still feasible to match a large portion of the vertices correctly. 



In the second experiment, we compare the same statistics across different popular random graph models, fixing the expected average degree across the graphs. 
In particular, we use again the ER model G(n,m) but now with m fixed edges and the WS model. 
We additionally include the preferential attachment PA(n,γ,d) model proposed by <cit.>.  This model creates a graph by a random process in which a new vertex with d edges is added to the graph on each step t. 
For each new vertex the probability that it connects to an existing vertex i is proportional to d_it^-γ, where d_it is the degree of vertex i at time t, and γ≥ 0 is a constant that controls the preferential effect. 
Larger values of γ increase the preference of new vertices to connect with high degree vertices.

As observed in the previous experiment, the edge density of the graph plays an important role for matching feasibility. 
Thus, to make fair comparisons between the different models we adjust the model parameters to generate graphs with the same average degree d, by fixing  d=5 (1% density) and d=50 (10% density). 
For the WS model, we generate graphs from a WS(n, d,0.05) and WS(n, d,0.75), and for the PA model, we change the exponent γ to generate PA(n, 1,d) and PA(n,2,d). 
In all cases, we use the default implementation of  <cit.> to simulate the graphs. 
The results of these experiments are shown in Figure <ref>. We observe that in general the graphs that have a more random structure (the ER model and the WS model with a large rewiring probability) are the ones in which the measures of matching feasibility are larger. 
Matching in the PA model is complicated due to the low degree of many vertices, and thus the theoretical probability bound for perfect matchability is low. 












 §.§ Real-world networks

We also analyze graph matching in the corrupting channel model for real-world networks from different domains. 
The networks that we use  are the Zachary's karate club friendship network <cit.>, the graph of synapses between neurons of the C. elegans roundworm <cit.>, the graph of hyperlinks between political blogs from the 2004 US election <cit.>, a protein-protein interaction network in yeast <cit.>, and a citation network between arXiv papers in the condensed matter section <cit.>. 
Some graph statistics to summarize the data are included in Table <ref>. These include the number of nodes n, the average node degree d=1/n∑_ij A_ij, the density of the graph d/(n-1), the clustering coefficient C which counts the number of triangles in the graph divided over the maximum number of triangles possible, the skewness γ_1 and the relative standard deviation (RSD) of the degree distribution. In general, as observed in the simulations, we should expect that as the graphs become denser and with a more random structure (lower clustering coefficient and homogeneous degrees), matching becomes more feasible. 





Figure <ref> shows the bounds in the channel probability p̂_k(A) (top panel) and the normalized average number of edge disagreements X̂_k(A) (bottom panel) for the selected networks. 
When the fraction of shuffled vertices is small, all networks have a zero tolerance for noise in the corrupting channel model,  which can be due to the periphery nodes and the existence of (near) graph automorphisms between some of the vertices. 
Thus, exactly solving the graph matching problem in general is not feasible if p>0. However, as the fraction of shuffled vertices gets larger the value of p̂_k(A) increases for some of the networks, which suggests that partial matching is still possible. 
The political blogs and the C. elegans networks have the highest values for the measured quantities, X̂_k(A) and p̂_k(A), which can be explained by  their large average degree and  small clustering coefficient.
On the other hand, the protein-protein interaction and arXiv citation networks have the lowest values, possibly because of their low density. 
The probability bounds in the karate network might be very conservative since the results of Theorem <ref> are asymptotic, and n is small for this network.




In practice, computing the MLE of the unshuffling permutation is computationally unfeasible, as solving the GMP requires to optimize a loss function over Π_n. 
Thus, 

To validate the results above, we measure the accuracy of a graph matching solution of the problem 
(<ref>) given graphs A and B, where B is generated using a uniformly corrupting channel (p,I). Then, we perform graph matching using the FAQ programming algorithm ; we use the true parameter I as the initialization value of the FAQ algorithm in order to check whether I (the unshuffling permutation) is a local minimum of the matching objective function. 
While this is not finding a globally optimal solution to the graph matching problem in general, this strategy provides a useful surrogate for the difficulty/feasibility of the deanonymization task.




For each network A, we generate 30 independent random graphs B from the uniformly corrupting channel with the same value of p,  and measure the average matching accuracy of the solution P̂^FAQ. 
This process is repeated
for different values of p∈{10^-3, 10^-2.5, …, 10^-0.5}. 
The accuracy of the solution is measured in two ways: 
First, we calculate the total matching accuracy as the percentage of vertices that are correctly matched; i.e., we compute 1/n∑_i=1^n1(P̂^FAQ_ii=1). 
As mentioned in Section <ref>, matching  periphery vertices is usually hard in practice, thus, we also investigate whether it is possible to correctly match the core vertices by measuring the accuracy of matching the vertices with the highest degrees. 
If j_1,…, j_n is an ordering of the vertex indexes according to their degree, so that ∑_i=1^nA_j_ui≥∑_i=1^nA_j_vi if u<v, then the accuracy of matching a fraction c of the vertices with the highest degree is given by 1/⌊ cn⌋∑_i=1^⌊ cn⌋1(P̂^FAQ_j_ij_i=1), with c∈(0,1]. 


	

	
	



	
	
	
	




The overall matching accuracy and the matching accuracy of the vertices with highest degrees are shown in Figures <ref> and <ref>. 
When looking to all the vertices aggregated in Figure <ref>, the accuracy in the arXiv and protein interaction networks decreases fast as p increases, which agrees with the predicted matching feasibility of Figure <ref>.  The  Karate and C. elegans networks have the highest matching accuracy for most of the values of p. 
This suggests that the bound obtained in Theorem <ref> might be conservative for networks with a small number of vertices. However, when looking only to the vertices with the highest degree (Figure <ref>), the matching accuracy is higher in the political blogs networks, in which almost 25% of the vertices with the highest degree can be matched accurately even for large values of p; this is as expected by the results on Figure <ref> in which this network is the more resistant to noise for large values of k. 
Figure <ref> also shows the difficulty of matching vertices in the protein-protein interaction and arXiv citation networks, in which even the vertices with the highest degrees are usually incorrectly matched. 
This is especially true for the protein-protein interaction network, which has a core-periphery structure in which high-degree nodes are highly connected between each other. As observed in Table <ref>, this graph is characterized by a large clustering coefficient and a heavy tailed degree distribution.







§ DISCUSSION


The inexact graph matching problem aims to find the alignment that minimizes the number of edge disagreements between a pair of graphs. 
In this paper, we have shown that this intuitive notion of matching coincides with a maximum likelihood estimator in errorfully observed graphs, which is formally defined using the corrupting channel model. 
This model is able to accommodate different correlation structures between the edges of a pair of graphs, and many other popular models for the paired and correlated networks are encompassed by this framework.  
Within this model, we derive necessary and sufficient conditions to determine whether the MLE is consistent, and introduce a relaxed notion of consistency in which all but a small fraction of the vertices are correctly matched. 

Since the distribution of the corrupting channel model conditions on a given graph A, the consistency results we presented here only depend on the structure of A and the channel noise. This property allowed us to derive conditions that can be used to  check whether  the MLE is consistent for a given family of graphs, and hence whether it is feasible to solve the GMP. We used these results  to study matching feasibility  in some popular random graph models, unifying some previous matchability results within our framework and introducing some new ones as well. 
Our results were tested in simulated and real networks, and we introduced a statistic that can be used in practice to estimate matching feasibility.  
In addition, we believe that our results can be used to study the feasibility of solving the GMP in other graph models of interest.

This paper studies the information limits of the graph matching problem in the corrupting channel model, and currently there is no known efficient algorithm for finding the solution to the graph matching problem in this model framework. 
Hence, finding a polynomial-time algorithm to solve the GMP in this model and studying the corresponding computational limits are important open questions for future work. 
These questions have been partially addressed  in a number of settings (see for example <cit.>),  but existing methods usually require seeds to initialize the method, or impose restrictive constraints in the type of graphs or edge correlations that can be handled. Our framework offers a new insight which can be potentially useful in this direction.



Acknowledgements:
This material is based on research sponsored by the Air Force Research Laboratory and DARPA, under agreement number FA8750-18-2-0035. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Air Force Research Laboratory and DARPA, or the U.S. Government.






§ PROOF OF MAIN RESULTS









 §.§ Proof of Theorems <ref> and <ref>


Note that we will prove the more general Theorem <ref> here, with the proof of Theorem <ref> then following immediately as a special case.

	We will first prove part i. of the theorem. We show that under the conditions of the theorem, with high probability we have
	
    A_n-P_n^TB_nP_n_F^2 ≤A_n-Q_n^TP_n^TB_nP_nQ_n_F^2,

		for any Q_n≠ I_n, where I_n is the identity matrix. The proof proceeds by expressing the difference between the left and the right hand side of Equation (<ref>) can be expressed as a sum of independent random variables, and the tail of its distribution can be sufficiently bounded to show that Equation (<ref>) holds.
		
	Observe that P_n^TB_nP_n∼ C(A_n, Ψ_n^(1), Ψ_n^(2), I_n), so to this end, for a graph A∈𝒢_n, define B∼ C(A,Ψ_n^(1), Ψ_n^(2),I_n) to be the channel corrupted A with parameters (Ψ_n^(1), Ψ_n^(2),I_n).
	For each Q∈Π_n, define
	
    X_Q(A)   =X_Q:=1/2A-Q^TAQ^2_F
    X_Q(A)   =X_Q:=1/2(A-Q^TBQ^2_F-A-B^2_F).

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Consider a fixed Q^T∈Π_n,k, and let the permutation associated with Q^T be denoted via σ.
	Note that for any matrix M∈ℝ^n× n,
	[Q^TMQ]_ij=M_σ(i),σ(j). Recall that V is the set of all vertices, which is isomorphic to [n], and denote by V2={(i,j)∈[n]× [n], i<j} to the set of vertex pairs. Letting 
	
    Δ_1   :=|{  {i,j}∈V2 s.t. A_i,j≠ A_σ(i),σ(j), A_i,j= B_σ(i),σ(j)}|
    Δ_2   :=|{  {i,j}∈V2 s.t. A_i,j= A_σ(i),σ(j), A_i,j≠B_σ(i),σ(j)}|,

	we have that 
	
    1/2A-Q^TBQ^2_F   =X_Q+Δ_2-Δ_1,
    1/2A-B^2_F   =1/2Q^TAQ-Q^TBQ^2_F=Δ_2+Δ_1.

	And hence
	X_Q=X_Q-2Δ_1. Let Δ̃_1∼Binom(X_Q,p̃_n) be an independent binomial random variable.
	Noting that Δ_1∼∑_i=1^X_QBer(q_i) is a sum of independent Bernoulli random variables, with parameters q_i ≤p̃_n (each q_i is equal to its corresponding corrupting probability Ψ^(k)_i'j', which is upper bounded by p̃), we have that (Δ_1≥τ) ≤(Δ̃_1≥τ) for all τ≥ 0, and hence
	
    (X_Q≤ 0)   =( Δ_1≥ X_Q/2) ≤exp{-X_Q H(1/2,p̃_n)  }
       =exp{1/2X_Q log(4p̃_n(1-p̃_n))},

	where H(1/2,p) is the relative binomial entropy <cit.>. 
	If n≥ n_1, then the Assumption in Eq. <ref> implies  
	
    (X_Q≤ 0)≤exp{-3klog(n) },

	and this bound holds uniformly for all Q^T∈Π_n,k.
	
	Consider now n≥ n_1.
	Let B_n∼ C(A_n,Ψ^(1)_n, Ψ^(2)_n,P_n) and B_n∼ C(A_n,Ψ^(1)_n, Ψ^(2)_n,I_n).
For each Q∈Π_n, let 
	
    Y_Q(A)   =Y_Q:=1/2(A_n-Q^TB_nQ^2_F-A_n-P_n^TB_nP_n^2_F)
    X_Q(A)   =X_Q:=1/2(A_n-Q^TB_nQ^2_F-A_n-B_n^2_F).

	Note that X_P_n^TQ=Y_Q, and hence,
	
    (∃ Q≠ P_n s.t. Y_Q≤ 0)   =
    	(∃ P_n^T Q≠ I s.t. X_P_n^T Q≤ 0)
        =(∃ Q̃≠ I s.t. X_Q̃≤ 0)

	For each k>1, note that |Π_n,k|≤ n^k.
	For each k, applying Eq. (<ref>) uniformly for each Q̃∈Π_n,k and summing over k yields
	
    (∃ Q̃≠ I s.t. X_Q̃≤ 0)≤∑_k= 2^n exp{-2klog n  }≤exp{-4log n+log n  }=n^-3,

and therefore

    (∃ Q≠ P_n s.t. Y_Q≤ 0)   =
    ( _P∈Π_nA_n-P^TB_nP_F^2≠{P_n}) 
       =(∃  an MLE, , of P_n s.t. ≠ P_n)≤ n^-3.

	Therefore, with probability 1 it holds that for all but finitely many n (by the Borel-Cantelli lemma as n^-3 is finitely summable) the unique MLE of P_n is =P_n, and any sequence of MLE's, ()_n=n_0^∞, is strongly consistent.



Proof of Theorem <ref> part ii. 
Note that condition Eq. <ref> implies

    max_Q_n∈ S_nlog(1/4p̆_n(1-p̆_n))(A_n -Q_n^T A_nQ_n^2_F)=o(log(n) )


As in the proof of part i., we will work with P_n=I_n, as the consistency results for the MLE estimating I_n transfer immediately to consistency results for the MLE estimating a more general P_nConsider the notation as in the proof of part i, and consider the Θ(n) disjoint Q_n permutations with Q_n∈∪_i=2^k_nΠ_n,i∖I_n
(where S_n be the set of these Q_n) satisfying Eq.  (<ref>), (<ref>) as posited in Theorem <ref>.
Let Z_n=∑_Q_n∈ S_n,k1{X_Q≤ 0}.

Let Q∈ S_n be any of the permutations as defined above. We have that
Δ_1∼∑_i=1^X_QBer(q_i) for some independent Bernoulli random variables with parameters p̆_n≤ q_i≤p̃_n, and let
Δ̆_1∼Binom(X_Q,p̆_n).
We will make use of the following Theorem from <cit.> in our proof.

Suppose that X is centralized binomial distributed
with parameters (k,p). For any β > 1, there exist constants c_β, C_β > 0 that only rely on β, such
that

    (X ≥ x)≥ c_βexp(-C_β k h_p(p+x/k)),    if 0≤ x≤k(1-p)/β and x+kp≥ 1;
    
        =1-(1-p)^k,    if 0≤ kp+x<1
        
    (X ≤ -x)≥ c_βexp(-C_β k h_p(p-x/k)),    if 0≤ x≤kp/β and x+k(1-p)≥ 1;
    
        =1-p^k,    if 0≤ k(1-p)+x<1

where h_u(v)=vlog(v/u)+(1-v)log(1-v/1-u).

In the notation of the above theorem, let X=Δ̆_1-X_Qp̆_n (so that k=X_Q and p=p̆_n) and x=X_Q(1/2-p_n).
We have that

    x=X_Q(1/2-p̆_n)≤ X_Q(1-p̆_n)/2,

and we can take β=2.
Applying Eq. (<ref>) and the fact that  (Δ̆_1≥τ)≤(Δ_1≥τ) for all τ≥ 0, then implies (where c and C are constants independent of n)

    p_Q:=(Δ_1≥ X_Q/2 )   ≥(Δ̆_1-X_Qp̆_n≥ X_Q(1/2-p̆_n))
       ≥ c  exp{-C X_Q 1/2log(1/4p̆_n(1-p̆_n))}
       =Ω( c  exp( -1/2log(n) ))

where the last line follows from Eq. (<ref>).

Consider now disjoint Q=Q_n and Q'=Q_n' in S_n,k_n. 

Each X_Q=∑_i,jA_i,j(B_i,j-B_σ_Q(i),σ_Q(j)) is a function of Θ(nk_n) independent Bernoulli random variables (the B_i,j that are permuted).
The disjointedness of 
Q and Q' implies that there are at most 2k^2 common B_i,j that appear in both X_Q and X_Q',
and we can decompose 
X_Q' into 

    X_Q'=Y+W,
 where Y is independent of X_Q and |W|≤ 2k_n^2.
Note that k_n=Θ(1) by construction.
We then have that (where Δ_1' is the Δ_1 associated with X_Q')

    Cov( 1{X_Q≤ 0}, 1{X_Q'≤ 0})     =(X_Q≤ 0,X_Q'≤ 0)-(X_Q≤ 0)(X_Q'≤ 0) 
       ≤(Y≤ 2k_n^2,X_Q'≤ 0)-(Y≤ -2k^2)(X_Q≤ 0)
       =(X_Q≤ 0)(-2k_n^2≤ Y≤ 2k_n^2)
       ≤(X_Q≤ 0)(-4k_n^2≤X_Q'≤ 4k_n^2)
       =p_Q (X_Q'/2-2k_n^2≤Δ_1' ≤ X_Q'/2+2k_n^2)

Observe that conditions (<ref>) and (<ref>) imply that  that X_Q=ω(1) and that (1/2 -p̆_n)^2=o(1). The variable Δ_1'=∑_i=1^X_Q'Ber(q_i) is a sum of X_Q' independent binary variables with p̆_n≤ q_i≤p̃_n, and therefore, by the Lindeberg-Feller's Central Limit Theorem, s_n^-1(Δ_1'-𝔼[Δ_1']) converges in distribution to a standard normal, with

    X_Q'p̆_n≤𝔼[Δ_1']≤ X_Q'p̃_n,


    X_Q'p̆_n(1-p̆_n) ≤ s_n^2 ≤ X_Q'p̃_n(1-p̃_n).

Therefore, setting H_n:=√(X_Q')(1/2 - 𝔼[Δ_1']/X_Q'/s_n/√(X_Q')), we have that for n sufficiently large

    (Δ_1'-X_Q'/2∈[-2k_n^2,2k_n^2] )     = ( Δ_1' - 𝔼[Δ_1']/s_n∈[H_n -2k_n^2/s_n, H_n  +2k_n^2/s_n])
       ≤ C_1k_n^2/s_n≤C_2/√(X_Q').

for some constants C_1, C_2. Combining this bound with Equation (<ref>), we have

    Cov( 1{X_Q≤ 0}, 1{X_Q'≤ 0})≤ C_2 p_Q 1/√(X_Q')
 












	We now have that 
	
    Var(Z_n)≤(Z_n)+∑_Q_n∈ S_n,k∑_Q'_n≠ Q_np_Q_nC/√(X_Q_n').

	The second moment method (see <cit.> Theorem 4.3.1) can be applied to show 
	
    (∃ Q_n∈Π_n,k_n s.t. X_Q_n≤ 0)   =(Z_n>0) ≥ 1-Var(Z_n)/( Z_n)^2 
       ≥1- Z_n /( Z_n)^2-∑_Q_n∈ S_n,k∑_Q'_n≠ Q_np_Q_nC/√(X_Q_n')/∑_Q_n∑_Q'_np_Q_np_Q_n'.

By the assumption in Eq. (<ref>), we have that
	
    (Z_n)=Ω(ne^-1/2log n)=ω(1),

By the assumption in Eq.(<ref>), we have that p̆_n→1/2 (otherwise, the left hand side of Eq. (<ref>) is at least of a constant order). Combining this fact with p̆_n≤p̃_n and Eq.
(<ref>), we have that min_Q_n∈ S_nA_n-Q_n^TA_nQ_n_F^2=ω(1).

Combining these facts, we have that for each Q∈ S_n,

    -X_Q log(1/4p̆_n(1-p̆_n))+log(X_Q)    = log(X_Q)(1 - X_Q/log X_Qlog(1/4p̆_n(1-p̆_n))) 
       ≥log(X_Q)(1 - max_Q∈ S_nX_Q/log X_Qlog(1/4p̆_n(1-p̆_n)))
       ≥min_Q∈ S_nlog(X_Q)(1 - o(1))
        =ω(1).

Let 

    m_n:=min_Q∈ S_n-X_Q log(1/4p̆_n(1-p̆_n))+log(X_Q),

and note that m_n=ω(1).
Therefore,
	
    1/√(X_Q')/p_Q'   ≤
    	c1/√(X_Q') exp{C X_Q'1/2log(1/4p̆_n(1-p̆_n))}
       =c exp{C X_Q'1/2log(1/4p̆_n(1-p̆_n))-1/2log(X_Q')
    }
       ≤ c exp{ -C m_n}=o(1).

	We then have that
	
    ∑_Q_n∈ S_n,k∑_Q'_n≠ Q_np_Q_n1/√(X_Q_n')/∑_Q_n∑_Q'_np_Q_np_Q_n'   ≤ 
    		c exp{ -C m_n}∑_Q_n∈ S_n,k∑_Q'_n≠ Q_np_Q_np_Q_n'/∑_Q_n∑_Q'_np_Q_np_Q_n'   =o(1).

	
    (∃ Q_n∈ S_n s.t. X_Q_n≤ 0)=(Z_n>0)
    	≥ 1-o(1).

	Therefore, for any 1>ϵ>0
	
    (max_P∈𝒫^*P-I_n_F^2 ≤ϵ)→ 0

	giving the desired inconsistency result.
	
Proof of Theorem <ref> part iii.
As in the proofs of part i. and ii., we will work with P_n=I_n, as the consistency results for the MLE estimating I_n transfer immediately to consistency results for the MLE estimating a more general P_n.
Consider the notation as in the proof of parts i. and ii.
To prove part iii., consider first the case that p̆_n is bounded away from zero. 
Note that in this case, Equation (<ref>) (combined with the bound in Eq. (<ref>), and the fact that Δ̆_1 is stochastically less or equal than Δ_1) implies that 
	
	
    p_Q_n≥ c  exp{-C X_Q_n1/2log(1/4p̆_n(1-p̆_n))}=Θ(1)    if X_Q_n/2≥ 1
    ≥ 1-(1-p̆_n)^X_Q_n =Θ(1)    if X_Q_n/2< 1
 
	On the other hand, if p̆_n→ 0 as n goes to infinity, then  Equation (<ref>) implies that X_Q_n = o(1), and hence there exists infinitely many n's for which X_Q_n=0 and 
	the MLE would not be uniquely defined.
	Therefore, for any 1>ϵ>0
	
    lim sup(max_P∈𝒫^*P-I_n_F^2 ≤ϵ)<1






	and so the MLE is not weakly consistent.


 Observe that under the settings of the theorem, using the notation of Theorem <ref> we have that

    p̃_n=p_n = p̆_n.

From this observation, the result follows.




 §.§ Proof of Corollary <ref>



	By Lemma 4 in <cit.>, we have that for n sufficiently large and all Q∈Π_n,k,
	
    (A_n - Q^TA_nQ_F^2 ≤α_n k n/3) ≤ 2exp(-α_n^2kn/128).

	Note that for sufficiently large n, the condition of the corollary implies that
	
    6klog n/-log(4p_n(1-p_n))≤6klog n/(1/2-p_n)^2≤α_n k n/3.

	The same condition also implies that α_n=ω(√(log n /n)), and combining these facts with Equation (<ref>), we have that
	
    (min_Q∈Π_n,kA_n - Q^TA_nQ_F^2 ≤-6klog n/log(4p_n(1-p_n)) ∀ k∈[n])    ≤∑_k=2^n∑_Q∈Π_n,kexp(-α_n^2kn/128)
       ≤∑_k=2^nexp(klog n - 4klog n) 
       ≤1/n^2

	for n sufficiently large. As in the proof of Theorem <ref> part i., the result follows from an application of the Borell-Cantelli lemma.



 §.§ Proof of Corollary <ref>



	To prove part a), define P^(i) as the permutation that only switches vertices i and i+1, i.e., P^(i)_i,i+1=P^(i)_i+1,i = 1 and P^(i)_jj=1 for j=∈ [n]∖{i,i+1}, and let  
	
    S_n={P^(i):i mod 2=1}={P^(1),P^(3),⋯,P^(n-1)} if n is even
    {P^(1),P^(3),⋯,P^(n-2)} if n is odd

	be a set of disjoint permutations of this type. Without loss of generality, take P=P^(1). Then
		
    1/4A - P^TAP_F^2     = ∑_j=3^n(A_j2 - A_j1)^2
    
    			    =  (1 - A_d_n+2,1)^2 + (A_n-d_n+1,2 - 1)^2 + ∑_j=d_n+3^n-d_n(A_j2 - A_j1)^2,

		which is a sum of n-2d_n independent Bernoulli random variables; namely
		
    (1-A_d_n+2,1)^2   ∼Bern(1-β_n);
    
    		  (A_n-d_n+1,2 - 1)^2    ∼Bern(1-β_n);
    (A_j2 - A_j1)^2   ∼Bern(2β_n(1-β_n))
    		   for d_n+3≤ j≤ n-d_n.
 If n-2d_n=O(1), then part iii. of Theorem <ref> completes the proof. Hence, consider n-2d_n=ω(1). Define
		
		
    f(β_n)    := 1/4EAP-PA^2_F +  √(2nlog n)
       =2(1-β_n)[1+ (n-2d_n-2)β_n]+  √(2nlog n)
       =o(log n/(1/2-p_n)^2),

		
		where the last equality follows from the assumptions on the growth rate of β_n and p_n. 
		
		By Hoeffding's inequality,
		
    (1/4A-P^TAP^2_F≥ f(β_n) ) ≤exp(-4log n).

		Hence,
		
    (max_P∈S_n1/4A-P^TAP^2_F ≥ f(β_n))     ≤   ∑_P∈S_n(1/4A-P^TAP^2_F ≥ f(β_n) )
       ≤   n/2exp(-4log n) = 1/2n^3.

		By the Borell-Cantelli lemma, for all but finitely many n,  max_P∈𝒮1/4AP-PA^2_F < f(β_n)=o(log n/(1/2-p_n)^2), and using Theorem <ref> part ii. (resp., part iii.) if min_P∈𝒮_𝓃1/4AP-PA^2_F(1/2-p_n)^2=ω(1) (resp., min_P∈𝒮_𝓃1/4AP-PA^2_F(1/2-p_n)^2=O(1)), the result follows.
		
		For part b),  define a n× n graph B such that B_ij=A_ij whenever |i-j| mod(n-1-d_n)≥ d_n, and B_ij=B_ji∼Bern(β_n) otherwise. Then B∼G(n,β_n). 
		Consider a permutation Q∈Π_n,k, and observe that
		
    2A-Q^TAQ_F^2     = 2B - Q^TBQ + (A-B) - Q^T(A-B)Q^2_F
       ≥B-Q^TBQ_F^2 -8kd_n= B-Q^TBQ_F^2  - o(klog n/(1/2-p_n)^2).

		where
		
    2(A-B)-Q^T(A-B)Q_F^2≤ 8kd_n
 follows from (A-B) and Q^T(A-B)Q only disagreeing on edges incident to the k_n vertices that are permuted by Q_n, and there are at most 2d_n such edges per permuted vertex (each being double counted).
		Since B is an ER graph, following the proof of Corollary <ref> mutatis mutatandis, it can be shown that, with probability 1, for all but finitely many n 
    min_Q∈Π_n,kB-Q^TBQ_F^2≥-12klog n/log(4p_n(1-p_n),

		and thus
		 
    min_Q∈Π_n,kA-Q^TAQ_F^2≥-6klog n/log(4p_n(1-p_n)+ o(klog n/(1/2-p_n)^2).

	The result now follows from Theorem <ref> part i.





 §.§ Proof of Corollary <ref>


 Let A∼G(n,q_n) be an Erdős-Rényi graph. Given a permutation Q∈Π_n,k that shuffles exactly k vertices, the number of edge disagreements can be expressed as
 
    1/2A-Q^TAQ_F^2 
                = ∑_(i,j)∈𝒰_Q(A_i,j - A_σ_Q(i),σ_Q(j))^2,

     where 
 
    𝒰_Q := {(i,j)∈V2 : (σ_Q(i),σ_Q(j)) ≠ (i,j) and (σ_Q(i),σ_Q(j)) ≠ (j,i)}.

 To calculate the number of elements in 𝒰_Q, define the sets
    
    𝒰_Q^(1)    := {(i,j)∈V2 : σ_Q(i)≠ i and σ_Q(j) ≠ j},
    𝒰_Q^(2)    := {(i,j)∈V2 : σ_Q(i)≠ i and σ_Q(j) = j},
    𝒰_Q^(3)    := {(i,j)∈V2 : σ_Q(i)=j and σ_Q(j)=i},

 and observe that
  𝒰_Q = (𝒰^(1)_Q∪𝒰^(2)_Q)∖𝒰^(3)_Q, where | 𝒰^(1)_Q| = k2, | 𝒰^(2)_Q|=k(n-k), and | 𝒰^(3)_Q|≤k/2. Hence, 
  
    |𝒰_Q| ≥k(k-2)/2 + k(n-k) ≥nk/3.

    We make use of the following result of <cit.> as stated in <cit.>.
 
     Suppose  X is a function of η independent Bernoulli(q) random variables such that changing the value of any one of the Bernoulli random variables changes the value of X by at most 2. For any t:0 0≤ t <√(η q (1-q)), we have
    
    (|X-𝔼[X]|>4t√(η q(1-q))) ≤ 2exp(-t^2).

    
    Using the notation of the  theorem above, let
    X=1/2A-Q^TAQ_F^2, η = |𝒰_Q|, and observe that
    
    𝔼[X] = ηℙ(A_ij≠ A_σ_Q(i), σ_Q(j)) = 2η q_n(1-q_n)≥2nkq_n(1-q_n)/3.

    By the conditions in the corollary, there exists n_0 such that for all n>n_0
    
    nk/3q_n(1-q_n) > 6klog n/log(1/4p̃_n(1-p̃_n)).

    Observe that the assumptions of Theorem <ref> hold for any 0≤ t<√(η q_n(1-q_n)), and in particular let t=1/4√(nkq_n(1-q_n)/3). Then, using Theorem <ref> in combination with  Equations (<ref>) and (<ref>),
    
    (X ≤6klog n/log(1/4p̃_n(1-p̃_n)))    ≤(|X - 𝔼[X]| ≥𝔼[X] - 6klog n/log(1/4p̃_n(1-p̃_n)))
       ≤(|X - 𝔼[X]| ≥1/3nkq_n(1-q_n))
       ≤ 2exp(-nkq_n(1-q_n)/48)

    By the assumptions in Corollary <ref>, there exists n_1 sufficiently large such that for all n≥ n_1, it holds that q_n(1-q_n) > 192log n/n. Therefore, for all n>max{n_0,n_1},

    (min_Q_n∈Π_n,kA-Q^TAQ_F^2  ≤-6klog n/log(4p̃_n(1-p̃_n)) ∀ k≥ 2 )    ≤∑_k=2^n∑_Q∈Π_n,k2exp(-nkq_n(1-q_n)/48)
       ≤∑_k=2^n2exp(klog n -4klog n)
       ≤2/n^2.

As in the proof of Theorem <ref> part i., the result follows from an application of the Borell-Cantelli lemma.







 §.§ Proof of Theorem <ref>



The proof of this result follows  the proof of Theorem <ref> mutatis mutandis by only considering permutations of enough vertices. In particular, the conditions of part i. imply that an analogous to Equations (<ref>) and (<ref>) hold, that is,

    ( _P∈Π_nA_n-P^TB_nP_F^2∉⋃_k=k_n^n Π_n,k)     = (∃ Q∈⋃_k=k_n^n Π_n,k s.t. Y_Q≤ 0)
       ≤∑_k=k_n^n exp(-2klog n)
    
       ≤ n^-3.

Therefore, with probability 1 it holds that for all but finitely many n (by the Borel-Cantelli lemma as n^-3 is finitely summable) the  MLE of P_n is in Π_n ∖⋃_k=k_n^nΠ_n,k, so max - P_n_F^2≤ k_n, and because α_n = ω(k_n), the strong α_n-consistency follows.





 §.§ Proof of Corollary <ref>



	Let H∼G(n,d/n) be an ER graph with rate d/n.
	Define the events
	
    𝒜_n,d   ={ Eq. <ref> holds for A for all k=ω(n^2/3)}
    𝒜_n,d/n   ={ Eq. <ref> holds for H for all k=ω(n^2/3)}
    ℛ_n,d/n   ={H is d-regular}

	We then have that
	
    (𝒜_n,d/n^c)   ≥(𝒜_n,d/n^c|ℛ_n,d/n)(ℛ_n,d/n) =(𝒜_n,d^c)(ℛ_n,d/n).

	Note that for H_n in Π_n,k_n with k_n=k=ω(n^2/3), 
	
	    
  i. H_n - Q^TH_nQ^2_F is a function of k2+(n-k)k-O(k) independent Bern(p=d/n) random variables;
	    
  ii. Changing any one of these Bern(p=d/n) random variables can change H_n - Q^TH_nQ^2_F by at most 2;
	    
  iii. We have that 
	    
    μ_Q   =(H_n - Q^TH_nQ^2_F)=2(k2+(n-k)k-O(k))d/n(1-d/n)
       =(1+o(1))nkd/n(1-d/n).

	
	We then have (where c is a constant that can change line-to-line)
	
    (𝒜_n,d/n^c)    ≤(H_n - Q^TH_nQ^2_F < 6klog n/-log(4p_n(1-p_n)))
       =  (H_n - Q^TH_nQ^2_F-μ_Q < 6klog n/-log(4p_n(1-p_n))-(1+o(1))kd(1-d/n))
       ≤(H_n - Q^TH_nQ^2_F-μ_Q < 6klog n/c(1/2-p_n)^2-(1+o(1))kd(1-d/n))

	An appropriate choice of C in the conditions of the corollary combined with an application of McDiarmind's inequality then yields (where c is a constant that can change line-to-line)
		
    (𝒜_n,d/n^c)    ≤(H_n - Q^TH_nQ^2_F-μ_Q < -10kd(1-d/n))
       ≤exp{-ck^2d^2(1-d/n)^2  / (1+o(1))nkd/n(1-d/n)}
       ≤exp{-ckd
    	}

	Hence, by Lemma 4.1.iv in <cit.>, for n sufficiently large
	
    (ℛ_n,d/n)≥exp(-nd^1/2+ϵ/2),

	and so for n sufficiently large,
	
    (𝒜_n,d^c)   ≤(ℛ_n,d/n)^-1(𝒜_n,d/n^c) ≤exp{nd_n^1/2+ϵ/2-ω(n^2/3d_n )}
       ≤exp{(n-ω(n^2/3d_n^1/2-ϵ/2 )_
    	=n-ω(n)=-ω(n)  )d_n^1/2+ϵ/2}.

	As this probability is summable, we have that, with probability 1, 𝒜_n,d occurs for all but finitely many n by the Borel-Cantelli lemma.
	Therefore, with probability 1 the conditions of Theorem <ref> are met for any sequence α_n = ω(n^2/3) for all but finitely many n and the strong consistency of the MLE follows.



apa


