Seeded Graph Matching via Large Neighborhood Statistics
Elchanan Mossel Jiaming Xu


background
foreground
background,main,foreground










Seeded Graph Matching via Large Neighborhood Statistics
    
Elchanan Mossel 

MIT

elmos@mit.edu
Jiaming Xu

Duke University

jiaming.xu868@duke.edu

    26.7.2018
==============================================================================================





We study a well known noisy model of the graph isomorphism problem. In this model, the goal is to perfectly recover the
vertex correspondence between two edge-correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. Specifically, the model first generates a parent graph G_0 from Erdős-Rényi random graph 𝒢(n,p)  and then obtains two children graphs G_1 and G_2 by subsampling the edge set of G_0 twice independently with probability s=Θ(1). The vertex correspondence between G_1 and G_2 is obscured by randomly permuting the vertex labels of G_1 according to a latent permutation π^*. Finally, for each i, π^*(i) is revealed independently with probability α as seeds.   

In the sparse graph regime where np ≤ n^ϵ for any ϵ<1/6, we give a polynomial-time algorithm which perfectly recovers π^*, provided that nps^2 - log n → +∞ and α≥ n^-1+3ϵ. 
This further leads to a sub-exponential-time, exp( n^O(ϵ) ), matching algorithm even without seeds. On the contrary, if nps^2 - log n =O(1), then perfect recovery is information-theoretically impossible as long as α is bounded away from 1. 

In the dense graph regime, where np = b n^a, for fixed constants a, b ∈ (0,1], we give a polynomial-time algorithm which succeeds when b=O(s) and α = Ω( (np)^-⌊ 1/a ⌋log n). In particular, when a=1/k for an integer k ≥ 1, α = Ω(log n/n) suffices, yielding a quasi-polynomial-time n^O(log n) algorithm matching the best known algorithm by Barak et al. for the problem of graph matching without seeds when k ≥ 153 and extending their result to new values of p for k=2,…,152.  

Unlike previous work on graph matching, which used small neighborhoods or small subgraphs with a logarithmic number of vertices in order to match vertices, our algorithms match vertices if their large neighborhoods have a significant overlap in the number of seeds.
















§ INTRODUCTION


In this paper, we study a well-known model of noisy graph isomorphism. Our main interest is in polynomial time algorithms for seeded problems where the matching between a small subset of the nodes is revealed. For seeded problems, our result provides a dramatic improvement over previously known results. Our results also 
shed light on the unseeded problem. In particular, we give (the first) sub-exponential time algorithms for sparse models and an n^O(log n) algorithm for dense models for some parameters, 
including some that are not covered by recent results of Barak et al. <cit.>.  

We recall that two graphs are isomorphic if there exists an edge-preserving bijection between their vertex sets.  The Graph Isomorphism problem is not known to be solvable in polynomial time, except in special cases such as graphs of bounded degree <cit.> and bounded eigenvalue multiplicity <cit.>.  However, a recent breakthrough of Babai <cit.> gave a quasi-polynomial time algorithm. 


In a number of applications including network security <cit.>, systems biology <cit.>, computer vision <cit.>, and natural language processing <cit.>,
we are given two graphs as input which we believe have an underlying isomorphism between them.  However, they are not exactly isomorphic because they have each been perturbed in some way, adding or deleting edges randomly. 
This suggests a noisy version of Graph Isomorphism also known as graph matching <cit.>, where we seek a bijection that minimizes the number of edge disagreements.


Given two graphs with adjacency matrices G_1 and G_2, if our goal is to minimize the ℓ_2 distance between G_1 and 
some permuted version of G_2, then graph matching can be viewed 
as a special case of the quadratic assignment problem (QAP) <cit.>: namely, 

    min_Π G_1 - Π G_2 Π^⊤^2_F ,

where Π ranges over all n × n permutation matrices, and A ^2_F = ∑_ij A_ij^2 denotes the Frobenius norm.  QAP is NP-hard in the worst case.  There are 
exact search methods for QAP based on branch-and-bound and cutting planes, as well as various approximation algorithms  
based on linearization schemes, and convex/semidefinite programming relaxations (see <cit.> and the references therein).  However, approximating QAP within a factor 2^log^1-ϵ (n) for ϵ > 0 is NP-hard <cit.>. 

These hardness results only apply in the worst case, where the two graphs are designed by an adversary.  However, in many 
aforementioned applications, we are not interested in worst-case instances, but rather in instances for which
there is enough information in the data to recover the underlying isomorphism, , when the amount of data or signal-to-noise ratio is above the information-theoretic limit. The key question is whether there exists an efficient algorithm that is successful all the way down to this limit. 
In this vein, we consider the following random graph model denoted by (n,p;s) <cit.>.


Suppose we generate a parent graph G_0 from the random graph model (n,p). For a fixed 
realization of G_0, we generate two subgraphs G_1 and G_2 by subsampling the edges of G_0 
twice. More specifically, 


  * We let G^*_1 be a random subgraph of G_0 obtained by including every
edge of G_0 with probability s independently. 

  * We repeat the above subsampling procedure, but independently
to obtain another random subgraph of G_0, denoted by G_2. 

To further model the scenario that we do not know the vertex correspondence between G_1 and
G_2 a prior, we sample a random permutation π^* over [n] and let G_1 denote the
graph obtained by relabeling every vertex i in G^*_1 as π^*(i).  

The goal is to exactly recover π^* from the observation of G_1 and G_2 with high probability, ,
to design an estimator π̂ based on G_1 and G_2 such that

    π̂ (G_1, G_2) = π^* → 1,    as  n →∞.


As a motivating example, we can model G_0 as some true underlying friendship network of n persons, 
G_1 is an anonymized Facebook network of the same set of persons, and G_2 is a Twitter network with
known person identities. If we can recover the vertex correspondence between G_1 and G_2, then we
can de-anonymize the Facebook network G_1 (this example ignores many important facts such as additional graph structures in real life networks). 


Note that s is equal to the probability of e∈ E(G_2) conditional on e ∈ E(G_1), and hence can be viewed as a measure of the edge correlations. Throughout this paper, without further specifications, we shall assume s=Θ(1).

In the fully sampling case s=1, graph matching under (n,p;1) reduces to 
the Graph Automorphism problem for  graphs. In this case, a celebrated result <cit.> shows that
if log n+ ω(1)  ≤ np ≤ n- log n -ω(1),
then with probability 1-o(1), 
the size of the automorphism group  of G_0 is 1 and hence the underlying permutation π^*
can be exactly recovered; otherwise, with probability 1-o(1), the size of the automorphism group  of G_0 is 
strictly bigger than 1 and hence exact recovery of the underlying permutation is information-theoretically
impossible. 
Recent work <cit.>[
In fact, a more general correlated random graph model is considered in <cit.>, where G_1(i,j)=a, G_2(i,j)=b =p_a,b for a,b∈{0,1}. ] has extended this result to the partially sampling case s=Θ(1) and
p ≤ 1/2, showing that the Maximum Likelihood Estimator, or equivalently the optimum of QAP eq:QAP, coincides with the 
ground truth π^* with high probability, provided that nps^2 ≥log n + ω(1); on the contrary, any estimator is correct with probability o(1), if nps^2 ≤log n - ω(1).  



From a computational perspective, in the fully sampling case s=1, there exist linear-time algorithms 
which attain the recovery threshold, in the sense that they exactly recover the underlying permutation with high probability whenever np= log n+ω(1) <cit.>. However, 
in the partially sampling case, it is still open whether any efficient algorithm can succeed close to the threshold. 
A recent breakthrough result <cit.> obtains a quasi-polynomial-time (n^O(log n)) algorithm which
succeeds when np ≥ n^o(1) and s ≥ (log n)^-o(1). However, this is still far away from the information-theoretic limit nps^2 ≥log n + ω(1).

Another line of work <cit.> 
in this area considers a relaxed version of the graph matching problem, 
where an initial seed set of correctly matched vertex pairs is revealed as side information. This is motivated by the fact that in many
real applications, some side information on the vertex identities are available and have been successfully utilized to match many real-world networks <cit.>. Formally, in this paper, 
we assume the seed set
is randomly generated as follows. 

In addition to G_1, G_2 that are generated under (n,p;s) with a latent permutation π^*, 
we have access to π_0 such that π_0(i)=π^*(i) with probability α
and π_0(i)=? with probability 1-α independently across different i.
The goal is to recover π^* based on G_1, G_2, and π_0.

The vertex i such that π_0(i)=π^*(i) is called seeded vertices and 
the set of seed vertices is denoted by I_0. Note that according to our model, 
the number of seeds |I_0| 
is distributed as (n,α).  For a given size K, we could also consider a deterministic size model where I_0 is chosen uniformly at random from all possible subsets of 
[n] with size K. The main results of this paper readily extend to this deterministic size model with 
K=⌊ n α⌋. 

The results of the seeded graph matching turn out to be useful for 
designing graph matching without seeds. On the one hand, when a seed set of size K is not given, we could obtain it in n^O(K) steps by randomly choosing a set of K vertices and then enumerating all the possible mapping. This is known as the beacon set approach to graph isomorphism <cit.>. On the other hand, we could first apply a seedless graph matching algorithm and then apply a seeded graph matching algorithm to boost its accuracy. This two-step algorithms have been successful both theoretically <cit.> <cit.> and empirically <cit.>.   





In the sparse graph regime np=Θ(log n), it is shown in <cit.> 
that if α =Ω(1/log^2 n), or equivalently, the size of the seed set is Ω(n/log^2 n), 
then a percolation-based graph matching
algorithm correctly matches n-o(n) vertices  in polynomial-time with high probability. In the dense graph regime np=n^δ for some
constant δ∈ (0,1), a seed set of size Θ(n^1-δ) suffices as shown in <cit.>.  
Another work <cit.>
shows that if nps^2 α≥ 24 log n, then one can match all vertices correctly in polynomial-time with high probability
based on counting the number of “common” seeded vertices. 

Note that this exact recovery result requires the seed set size to be
linear in n in the sparse graph regime np=Θ(log n). 

In summary, despite a significant amount of previous work on seedless and seeded graph matching, the following two fundamental questions remain elusive:


In terms of graph sparsity, can we achieve the information-theoretic limit nps^2 - log n → +∞ in sub-exponential, or polynomial time?


In terms of seed set, what is the minimum number of seeds required for exact recovery in sub-exponential, or polynomial time?


Our main results shed light on this two questions by improving the state-of-the-art 
of seeded graph matching. 
First, we show that it is possible to achieve the information theoretic limit nps^2 ≥log n+ω(1) of graph sparsity in polynomial-time.
Then, we show the number of seeds needed for 
exact recovery in polynomial-time can be as low as n^ϵ in the sparse graph regime (np ≤ n^ϵ) and Ω(log n) in the dense graph regime. 




 §.§ Main Results


We first consider the sparse graph regime. 


Suppose np ≤ n^1/2-ϵ for a 
fixed constant ϵ>0 and s=Θ(1). Assume 

    nps^2 - log n    → + ∞
    α   ≥ n^-1/2+3ϵ.
 
Then there exists a polynomial-time algorithm, namely alg:graph_matching_ell_hop, which outputs π̂=π^* with probability at least 1-o(1) under the seeded (n,p;s,α) model.


Notice that eq:it_limit is the information-theoretic limit
for graph matching under the seedless (n,p;s) model. In fact, thm:converse shows that 
eq:it_limit is necessary for seeded graph matching
as long as α is bounded away from 1.
Its proof is standard and can be found in 
app:converse.


If 

    nps^2-log n = O(1),

then 
any algorithm outputs π̂≠π^* 
with at least a probability of Ω((1-α)^2 ) 
under the seeded (n,p;s,α) model.





Also, the condition eq:seed_limit
requires that the size of the seed set is n^1/2+3ϵ compared to the best previously known results that 
required the seed set to be almost linear in n. 

It is natural to ask if n^1/2 seeded nodes are required for polynomial time algorithm. 
While from the proof of thm:main, it might look that n^1/2 is optimal due to the birthday paradox effect, it turns out we can do better! 

The following result relaxes the size of seed set needed to 
n^3ϵ.

Suppose np ≤ n^ϵ for a fixed constant ϵ< 1/6 and s=Θ(1). Assume 

    nps^2 - log n    → + ∞
    α   ≥ n^-1+3ϵ.
 
Then there exists a polynomial-time algorithm, namely alg:graph_matching_ell_hop_witness_sparse, which outputs π̂=π^* with probability at least 1-o(1) under the seeded (n,p;s,α) model.



We next consider the dense graph regime, where we assume the average degree np is parameterized as: 

    np = b n^a
 
for some fixed constants a, b ∈ (0,1]. 
Let 

    d = ⌊1/a⌋ +1,



Consider the dense graph regime eq:dense_regime.

Assume

    b ≤s/16(2-s)^2,

and 

    α≥ 300 log n/(nps^2)^d-1,

where d is given in eq:def_d. 
Then there exists an polynomial-time algorithm, namely alg:graph_matching_ell_hop_witness, which 
outputs π̂ =π^* with probability 1-4n^-1
under the seeded (n,p;s,α) model.


Our results for seeded graph matching also imply the results for graph matching without seeds. 

Suppose a Seeded Graph Matching algorithm 
outputs π̂=π^* with high probability under the seeded graph matching model (n,p;s,α). Assume 
nps^2 -log n → +∞
and α n → +∞. 
Then there exists an algorithm, namely alg:graph_matching_seedless, which calls the Seeded Graph Matching algorithm n^O(α n) times and outputs 
π̂=π^* under the seedless model (n,p;s) with high probability. 



Consider the dense regime 
eq:dense_regime with a =1/k for an integer k ≥ 1. 
Then d=k+1 and 
(np)^d-1 = b^k n. Hence, as shown by thm:dense, 
α n ≥ 300 log n (bs^2)^-k,
or equivalently Ω(log n) number of 
seeds, suffice for exact recovery in polynomial-time.  Since we can enumerate over
all possible matchings for log n seeds in 
quasi-polynomial n^ O( log n) time, this implies a quasi-polynomial 
time matching algorithm even without seeds, as shown by thm:seedless_graph_matching. 
The previous work <cit.> gives a quasi-polynomial time
matching algorithm in the range 

    np ∈[ n^o(1), n^1/153] ∪ [n^2/3, n^1-ϵ].

Our results complement their results by filling in gaps in the above
range with points np ∈{ b n^1/k: 1 ≤ k ≤ 152 }. 





 §.§ Key Algorithmic Ideas and Analysis Techniques

Most previous work <cit.> on seeded graph matching exploits the seeded information by looking at the number of seeded vertices that are direct neighbors of a given vertex. Since the average degree of a vertex is np, np α≫ 1 is needed so that there are sufficiently many seeded vertices that are direct neighbors of a given vertex. 


Our idea is to explore much bigger (“global”) neighborhoods of a given vertex up to radius ℓ for a suitably chosen ℓ, and match two vertices 
by comparing the set of seeded vertices 
in their ℓ-th local neighborhoods. 
This idea was used before in the noiseless and seedless case, in <cit.> but to the best of our knowledge was not used
in the noisy and seeded case. 
Since we are looking at global neighborhoods, we can only perform very simple tests. Indeed, the test we perform to check if two vertices are matched is just to count how many seeded vertices do the two neighborhoods have in common. Thus, our algorithms are very simple. 

The main challenge in the analysis is to control the size of neighborhoods of the coupled graphs G_0, G_1 and G_2. In this regard, we draw on a number of tools from the literature on studying subgraph counts <cit.> and the diameter in random graphs <cit.>.
See app:neighborhood_expansion for details. 






















§ OUR ALGORITHMS























Before presenting our algorithms, we first explain why eq:it_limit is needed for graph matching
under (n,p,s). Denote the intersection graph 
and the union graph by G_1^* ∧ G_2 and G_1^* ∨ G_2.
Then 

    G_1^* ∧ G_2 ∼(n, ps^2)   and    
    G_1^* ∨ G_2 ∼(n, ps(2-s)).

Notice that  G_1^* ∧ G_2 contains the statistical signature
for matching vertices, as a subgraph in G_1^* ∧ G_2 will appear
in both G_1 and G_2. If nps^2 -log n =O(1), then classical random
graph theory implies that with high probability, 
G_1^* ∧ G_2 contains isolated vertices. The underlying true vertex correspondence of these isolated vertices cannot be correctly matched; hence the impossibility of exact recovery. See app:converse for a precise argument.  

In contrast, if nps^2 -log n → +∞, then G_1^* ∧ G_2 is connected
with high probability. Moreover, for a high-degree vertex i in G_1^* ∧ G_2, its local neighbhorhood  grows like a branching process.
In particular, the number of
vertices at distance ℓ from i is approximately (nps^2)^ℓ.
Furthermore, for a pair of two vertices i,j 
chosen at random in G_1^* ∨ G_2, 
the intersection of the local neighborhoods of i and j is
typically of size O ( (nps)^2ℓ n^-1). Therefore, if (nps^2)^ℓ≫ (nps)^2ℓ n^-1 and α (nps^2)^ℓ≫ 1, a large number of vertices can be distinguished with high probability based on the set of seeded vertices in their ℓ-th local neighborhoods. This is the key idea underlying our algorithms. 
 
 
We shall use the following notations of local neighborhoods. For a given graph G, we denote by Γ^G_k(u) the set of vertices at distance
k from v in G:

    Γ^G_k (u) = { v ∈ V(G): d(u,v) = k }

and write N^G_k(u) for the set of vertices within distance k from u:

    N^G_k (u) = ∪_i=0^k Γ_i (u).

When the context is clear, we abbreviate 
Γ^G_k (u) and N^G_k (u) as Γ_k(u) 
and N_k(u) for simplicity. 




 §.§ A Simple Algorithm in Sparse Graph Regime

We first present a simple seeded graph matching algorithm which succeeds up to the information-theoretic limit in terms of graph sparsity when the initial seed set is of size n^1/2+3ϵ. 

The idea of the algorithm is based on matching ℓ-th local neighborhoods of two vertices by finding independent paths (vertex-disjoint except for the starting vertex) to seeded vertices. The ℓ is chosen such that (np)^ℓ≈ n^1/2-ϵ. In this setting, we 
expect that if i in G_1 and j in G_2 are true matches, then their local neighborhoods intersect a lot; 
if i and j are wrong matches, then their local
neighborhoods barely intersect. Hence, if α (nps^2)^ℓ≫ 1,
then we can find a sufficiently large number of, say m, 
independent (vertex-disjoint except for i) paths of length 
ℓ from i to m seeded vertices in Γ^G_1^* ∧ G_2_ℓ (i). 
Such m paths of length ℓ
form a starlike tree T in G_1^* ∧ G_2 with root vertex i and 
a set of m seeded leaves, denoted by L (See 
 fig:STexample for an example of m=3 and ℓ=2). 
Note that T will appear in G_2 with root vertex i
and the set of seeded leaves L; it will also appear in 
G_1 with root vertex π^*(i) and 
the corresponding set of seeded leaves π^*(L).  
However, since the ℓ-th local neighborhoods of two distinct vertices barely intersect,  
T will not appear in G_1^* ∨ G_2 with a
root vertex other than i. Therefore, we can correctly match the vertex π^*(i) in G_1 with the 
high-degree vertex i in G_2
by finding such a starlike tree T, or equivalently m independent ℓ-paths  to
a set of m common seeded vertices. 





There are two tuning parameters ℓ and m in
alg:graph_matching_ell_hop. Later in our analysis, we will optimally choose

    ℓ = ⌊( 1/2 - ϵ) log n/log (nps^2) ⌋≥ 1

and 

    m = ⌈2/ϵ⌉.


Note that when nps^2 -log n → +∞, there may exist vertices with small degrees. 
In fact, classical random graph results say that the minimum degree of 
(n,p) is k with
high probability for a fixed integer k, provided that 

    (k-1) loglog n +ω(1) ≤ 
    nps^2 - log n  ≤  k loglog n -ω(1) ,

see, , <cit.>.
Hence, due to the existence of low-degree vertices, we may not be able to 
match all vertices correctly at one time based on the number of independent
paths to seeded vertices. Our idea is to first match high-degree vertices and then match the remaining low-degree vertices
with the aid of high-degree vertices matched in the first step. In particular, we let 

    τ = nps^2/log (nps^2) .




We say a vertex i high-degree, if its degree d_i ≥τ in G_1^*∧ G_2; 
otherwise, we say it is a low-degree vertex. As we will see in sec:sparse_simple, conditioning  on  that 
G_1^* ∧ G_2 and G_1^* ∨ G_2 satisfy some 
typical graph properties, all low-degree vertices can be
 easily matched correctly given a correct matching of high-degree vertices. 



In passing, we remark on the time complexity of alg:graph_matching_ell_hop.
Note that for ease of presentation, in alg:graph_matching_ell_hop, we do not specify  how to efficiently find out  
whether there exist m independent ℓ-paths in G_2 from i_2 to seed set L ⊂Γ^G_2_ℓ(i_2), and m independent 
ℓ-paths in G_1 from i_1 to the corresponding seed set π_0(L) ⊂Γ^G_1_ℓ(i_1). 
It turns out for a given pair of vertices i_1, i_2, this task can be reduced to a maximum flow problem in a directed graph, which can be solved via Ford–Fulkerson algorithm <cit.> 
in O(nα) time steps (see app:time_complexity_1 for details). Since there are at most n^2 pairs of vertices i_1, i_2 to consider, Step 3 of alg:graph_matching_ell_hop
taks at most O( n^3 α ). 
The Step 4 of matching low-degree vertices in alg:graph_matching_ell_hop takes at most O(n^3 p) time steps. Hence, in total  alg:graph_matching_ell_hop takes at
most O(n^3 (α+p) ) time steps. 






 §.§ A Simple Algorithm in Dense Graph Regime


In this subsection, we consider the dense graph regime given in eq:dense_regime,
where np=bn^a and d=⌊ 1/a⌋ +1. In this setting, since 
p^d n^d-1 - 2 log n→ +∞ and p^d-1n^d-2-2log n ≤ -∞, it follows from <cit.> that (n,p) has diameter d with high probability. Thus, when s=Θ(1), both G_1^* ∧ G_2
and G_1^* ∨ G_2  have diameter d with high probability. 
Therefore, we present an algorithm based on 
matching the d-1-th local neighborhood of 
two vertices. 






More specifically, our algorithm matches i_1 ∈ V(G_1) and vertex i_2 ∈ V(G_2) based on the number of seeded vertices within distance d-1 from i_1 in G_1 and within distance d-1 from i_2 in G_2. 




alg:graph_matching_ell_hop_witness runs in polynomial-time. The precise running time depends on the data structures for storing and processing graphs. To be specific, let us assume it takes one time step to fetch the set of direct neighbors of a given vertex. Then
fetching the set N^G_ℓ(i) of all vertices within distance ℓ from a
given vertex i takes 
a total of O(|N^G_ℓ(i)|)=O(n) time steps. Thus computing w_i_1,i_2 in
eq:def_witness_w for a given
pair of vertices i_1, i_2 takes at most O(n) time steps. Hence, in total 
alg:graph_matching_ell_hop_witness takes O(n^3) time steps. One could possibly obtain a better running time via a more careful analysis or a better data structure. 



The difference in the analysis compared to the first algorithm is that the (d-1)-th local neighborhoods are not tree-like anymore. Instead, we have to analyze the exposure process of the two neighborhoods, for which we use a previous result of <cit.>
in studying the diameter of random graphs. 



 §.§ An Improved Algorithm in Sparse Graph Regime

In the sparse regime where np is poly-logarithmic, alg:graph_matching_ell_hop_witness does not perform well. 
This is because for two distinct vertices u,v that are close by, 
their ℓ-th local neighborhoods have a large overlap, , 
| N^G_ℓ(u) ∩ N^G_ℓ(v)| is not much smaller than 
| N^G_ℓ(u) | or | N^G_ℓ(v)|, rendering  w_i_1,i_2 given in eq:def_witness_w ineffective to distinguish u from v. 

However, in the sparse regime, distinct vertices u,v only have very few common neighbors. Moreover, if we remove vertices u, v, 
the non-common neighbors become far apart, 
and for distinct vertices far apart, their local neighborhoods only have a small overlap.   
Therefore, we expect most of u,v's neighbor's ℓ-th local neighborhoods (after removing vertices u,v) 
do not have large
intersections for a suitably chosen ℓ. This gives rise to alg:graph_matching_ell_hop_witness_sparse. 




Note that in computing the number of seeded vertices within distance ℓ from
both vertex i in G_1 and vertex j in G_2 in eq:def_w_sparse,
we remove vertices u, x in G_1 and
vertices v,y in G_2, and take the minimum over all possible choices of x and y. As a result,

    w^u,v_i,j≤| { k ∈ I_0: π_0(k) ∈ N^G_1\{ u, v}_ℓ (i),  
    k ∈ N^G_2\{u,v}_ℓ (j) }|,

where the right hand side becomes independent from the 
edges incident to u and v in G^*_1 ∨ G_2. This independence is crucial in our analysis to ensure that 
Z_u,v is small for u ≠π^*(v) via concentration inequalities of multivariate polynomials <cit.>. 



There are two tuning parameters ℓ and η in 
alg:graph_matching_ell_hop_witness_sparse. 
In our analysis later, we will optimally choose 

    ℓ = ⌊(1-  ϵ) log n/log (np ) ⌋,

and 

    η =  4^2ℓ+2 n^1-2 ϵα.


As for time complexity, alg:graph_matching_ell_hop_witness_sparse
takes at most O(n^5+2ϵ) time steps. To see this, similar to alg:graph_matching_ell_hop_witness, if we assume one unit time to fetch a set of direct neighbors of a given vertex, then it takes at most O(n^3) time steps to 
compute eq:def_w_remove 
for given pairs of vertices (u,v) and (i,j). There are
at most n^2+2ϵ such pairs. 
The step of matching low-degree
vertices as specified in alg:graph_matching_ell_hop
takes O(n^3p) time steps in total. 
Thus in total alg:graph_matching_ell_hop_witness_sparse takes at most O(n^5+2ϵ ) time steps. 





 §.§ Graph Matching without Seeds

Even without an initial seed set revealed as side information, we can select a random subset of vertices I_0 in G_1 and enumerate all the possible mappings
f: I_0 → [n] from I_0 to vertices in G_2 in at most n^|I_0| steps. Each of the possible mappings can be viewed as seeds; thus we can apply our seeded graph matching algorithm. Among all possible n^|I_0| mappings, we finally output the best matching which minimizes the edge disagreements. See alg:graph_matching_seedless for details. 







Since one of the possible mapping f will correspond to the underlying true matches of vertices in I_0, it follows that if our seeded graph matching succeeds with high probability and we are above the information-theoretic limit (so that the true matching minimizes the edge disagreements with high probability), the final output will coincide with the true matching with high probability, as stated in thm:seedless_graph_matching.  More specifically, the proof is sketched below. 


If f: I_0 → [n] is such that 
f(i)=π^*(i) for all i ∈ I_0, then 
since our seeded graph matching succeeds with high probability, it follows that 
π_f = π^*
with high probability. 

Moreover, since we are above the information-theoretic limit, it follows from <cit.> that with high probability, 

    π^* ∈min_π G_1 - Π G_2 Π^⊤_F^2,

where Π is the permutation matrix corresponding to π. 

Therefore, π̂ =π^* with high probability.
Finally, since α n →∞, it follows that |I_0| is at most 2α n with high probability. Hence, alg:graph_matching_seedless calls the Seeded Graph Matching algorithm at most n^O(α n) times with high probability. 








§ ANALYSIS OF ALG:GRAPH_MATCHING_ELL_HOP IN 
SPARSE GRAPH REGIME


In this and next two sections, we give the analysis of our algorithms and 
prove our main theorems. For the sake of
analysis, we assume 
π^*=id, , π^*(i)=i
for all i∈[n],
without loss of generality. 
































Our analysis of alg:graph_matching_ell_hop uses the  technique for analyzing small subgraph containment <cit.>. 
Let T denote a starlike tree formed by m independent (vertex-disjoint expect the root vertex) paths of length ℓ from root vertex to m distinct leaves for ℓ,m ≥ 1. 
Note that T consists of mℓ+1 vertices and mℓ edges (See 
 fig:STexample for an example of m=3 and ℓ=2).  
Let r(T) denote the root vertex of T and L(T) denote the set of leaves of T.
We say T is a subgraph of G, denoted by T ⊂ G, 
if V(T)⊂ V(G) and E(T) ⊂ E(G).


The key  of our proof is to show that under certain conditions with high probability:


  * For every vertex i, there exists a copy of T rooted at i with all leaves seeded 
in the intersection graph G_1^* ∧ G_2;

  * There is no copy of T_1 ∪ T_2 
in  the union graph G_1^* ∨ G_2. 

















 §.§ Success of alg:graph_matching_ell_hop on the Intersection of Good Events


We first introduce a sequence of “good” events on whose intersection, alg:graph_matching_ell_hop 
correctly matches all vertices. We need the following graph properties:


  * there is no isolated vertex;
 
  
  
  * for any two adjacent vertices, there are at least τ vertices adjacent to
at least one of them;

  * For all vertices i with d_i ≥τ, 
there are at least 2m independent ℓ-paths from i to 2m distinct vertices in 
I_0;

  * There is no pairs of subgraphs T_1, T_2 ⊂ G that are isomorphic to  T 
such that r(T_1)≠ r(T_2), and L(T_1) = L(T_2) (See fig:STexample for an illustration).

  * For every vertex i, there exist at most m-1 independent ℓ-paths from i 
to m-1 distinct vertices in N^G_ℓ-1(i). 
  


Let 


  * _1 denote the event such that G_1^* ∧ G_2 satisfy properties (i)–(iii);

  * _2 denote the event such that G_1^* ∨ G_2 satisfy properties (iv) and (v);

  * _3 denote the event such that  
for any two vertices i,j that are connected by a 2-path in G_1^* ∨ G_2,
  at least one  of the two vertices i,j must be a high-degree vertex in G_1^* ∧ G_2.  








We claim that on event _1 ∩_2 ∩_3, 
alg:graph_matching_ell_hop
correctly matches all vertices. Recall that we can assume π^*=id and thus G_1=G^*_1 without loss of generality. 

First, since G_1^* ∧ G_2 satisfy graph property (iii), 
it follows that in G_1^* ∧ G_2, for all high-degree vertices  i, 
there exist 2m independent ℓ-paths to a set S ⊂Γ^G_1^* ∧ G_2_ℓ (i) 
of 2m seeded vertices. 
Let S̃ = S \ N^G^*_1 ∨ G_2_ℓ-1(i). 
Since G_1^* ∨ G_2 satisfy graph property (v), and 
G_1^* ∧ G_2 ⊂ G_1^* ∨ G_2, it follows that 

    | S ∩ N^G^*_1 ∨ G_2_ℓ-1 (i) |  ≤ m-1
  
and thus 
| S̃ | ≥ m+1 .
Moreover, since G_1^*∧ G_2 ⊂ G_1, G_2, it follows that 

    S̃⊂Γ^G_1^* ∧ G_2_ℓ (i) 
    \ N_ℓ-1^G_1^* ∨ G_2⊂Γ^G_1^*_ℓ (i) 
    ∩Γ^G_2_ℓ (i).

Therefore, in both G_1 and G_2, there are 
 at least m+1 independent
ℓ-paths from i to Γ^G_1^*_ℓ (i) 
∩Γ^G_2_ℓ (i).


Second, note that on event _2, G_1^* ∨ G_2 satisfy graph property (iv). 
For the sake of contradiction, suppose there exist a pair of distinct vertices i,j
and a set L of m seeded vertices
such that there exist m independent ℓ-paths from i to set L in G_1
and m independent ℓ-paths from j to set L in G_2. 
Let T_k
denote the starlike tree
formed by the m independent ℓ-paths in G_k for k=1,2.
Then T_1,T_2 ⊂ G_1^* ∨ G_2 are isomorphic to T such that r(T_1)=i, r(T_2)=j and 
L(T_1)=L(T_2)=L. This is in contradiction with the fact that 
G_1^* ∨ G_2 satisfy graph property (iv). 

It follows from the above two points that alg:graph_matching_ell_hop correctly matches all
high-degree vertices i in G_1^* ∧ G_2, , π̂(i)=i.

Next, we show that all low-degree vertices are matched correctly. 
Fix a low-degree vertex i. Since G_1^* ∧ G_2 satisfy 
graph properties (i) and (ii), it must have a high-degree neighbor j in G_1^* ∧ G_2.  Since 
the high-degree vertex j has been matched 
correctly, i is adjacent to j in G_1 and i is also adjacent to π̂(j)=j in G_2.
Moreover, for the sake of contradiction, suppose there exists a pair of two distinct low-degree vertices i_1 and i_2 such that
i_1 is adjacent to a matched vertex j_1 in G_1 and i_2 is adjacent to vertex π̂(j_1) in G_2.
Since π̂(j_1)=j_1, it follows that (i_1,j_1,i_2) form a 2-path in G_1^* ∨ G_2. However, on event
_3, i_1 and i_2 cannot be low-degree vertices simultaneously in G_1^* ∧ G_2, which leads to a contradiction. 
As a consequence, π̂(i)=i for every low-degree vertex i.


Finally, to prove thm:main, it remains to show that under the theorem assumptions, 
_i→ 1 for all i=1,2,3, which is done in the next subsection. 








 §.§ Bound the Probability of Good Events

It is standard to prove that G_1^* ∧ G_2 satisfies properties (i)–(ii) with high probability and _3→ 1 using union bounds. For completeness, we state the 
lemmas and leave the proofs to appendices. 


Suppose G ∼(n,p) with np - log n → +∞.

  
  * There is no isolated vertex in G with probability at least 1-o(1);


  * Assume τ=o(np). With probability at least 1-n^-1+o(1),  for any two adjacent vertices, there are at least τ vertices adjacent to at least one of them in G.








 
Assume 

    nps^2≥log n    and   τ=o(nps^2)    and   log (np)=o(nps^2).

With probability at least 1-n^-1+o(1), 
for any two vertices i,j that are connected by a 2-path in G_1^* ∨
G_2, at least one of the two vertices i,j must have degree at least τ in G_1^* ∧ G_2. 




It remains to show with high probability, G_1^* ∧ G_2 satisfy graph
property (iii) and G_1^* ∨ G_2 satisfy graph properties (iv) and (v).











We will apply the following lemma to show that with high probability, 
for every high-degree vertex i in G_1^* ∧ G_2, 
we can always
find at least 2m independent paths of length ℓ from 
i to 2m distinct seeded vertices in I_0. 




Suppose G∼(n,p) and each vertex in G is included in I_0 independently with probability α.  
Assume  

    α  (np/2)^ℓ-2τ (τ-2m) - 2m logτ≥ 2log n.

and 

    p(4np)^ℓ = o(1)

and τ→ +∞. 
Then with high probability, for all vertices i with d_i ≥τ, there are at least 2m independent ℓ-paths from i to I_0.



In view of prop:tree_process, we have
≥ 1-3n^-1+o(1), where on event , for every 
vertex i, there exists a tree T_ℓ(i) ⊂ G of depth ℓ rooted at i such that:


  * Root i has at most one children j who has fewer than τ children in T(i), ,  |Π_1(j)| ≤τ. 

  * For each children j of i with |Π_1(j)| ≥τ, the subtree T_ℓ-1(j) 
of depth ℓ-1 rooted at
j has at least τ (np/2)^ℓ-2 leaves, , |Π_ℓ-1(j)| ≥τ( np/2 )^ℓ-2.


Fix a vertex i in G. Then i has at least
d_i -1 children j such that 
|Π_1(j)| ≤τ. For each such j, define
Y_ij=1 if there is a path of length ℓ-1 from j to some vertex in I_0 in T_ℓ(i). Then the number of independent paths from i to I_0
is at least ∑_j=1^d_i-1 Y_ij.
 
Since each leaf vertex of T_ℓ-1(j) is included in I_0  with probability α
independently across different vertices and from  graph G, 
it follows that 

    Y_ij =1 |  d_i ≥τ,  
    = 1- (1- α)^ |Π_ℓ-1(j)| ≥  1- exp( - ατ( np/2 )^ℓ-2),

where we used 1-x ≤ e^-x and |Π_ℓ-1(j)| ≥τ( np/2 )^ℓ-2 on event .  
Therefore, 
 
    ∑_j=1^d_i-1 Y_ij≤ 2m-1 | d_i ≥τ,    ≤∑_j=1^τ-1 Y_ij≤ 2m-1 
       ≤( τ -1,  1 - e^- ατ( np/2 )^ℓ-2)
     ≤ 2m-1 
        = ∑_k=0^2m-1τ-1k e^- ατ( np/2 )^ℓ-2 (τ-1-k ) 
       ≤ e^- ατ( np/2 )^ℓ-2 (τ-2m)∑_k=0^m-1τ^k 
       ≤ 2 e^- ατ( np/2 )^ℓ-2 (τ-2m)τ^2m≤ 2 n^-2,

 where the last equality holds due to 
 the assumption α(τ-2m) ( np/2 )^ℓ-2 - 2m logτ≥ 2log n.
 

Define event 

    _i ={  d_i ≥τ}∩{∑_j=1^d_i-1 Y_ij≤ 2m -1 }.

Then we have that 

    _i ∩≤∑_j=1^d_i-1 Y_ij≤ 2m-1 | d_i ≥τ, ≤ 2 n^-2.


Let =∪_i _i. 
By the union bound, 

    = ∩ + ^c≤∑_i _i ∩ + ^c≤ 2n^-1 + 3n^-1+o(1)≤ 5n^-1+o(1).

Therefore, with high probability, for all vertices i with d_i ≥τ, 
∑_j=1^d_i-1 Y_ij≥ 2m. 













The following lemma will be useful to conclude that in G_1^* ∨ G_2, 
with high probability, there is no pair of subgraphs T_1, T_2
⊂ G_1^*∨ G_2 that are isomorphic to T,
such that r(T_1)≠ r(T_2) and L(T_1)=L(T_2).
See fig:STexample for an illustration of 
T_1 and T_2 isomorphic to T such that 
r(T_1)≠ r(T_2) and L(T_1)=L(T_2). 



Suppose G ∼(n,p) and ℓ,m ≥ 1. Then it holds that 

    ∃  T_1, T_2 ⊂ G  that are isomorphic to  T: r(T_1)≠ r(T_2), L(T_1) = L(T_2) 
    
       ≤( 2+ 8/np)^m(ℓ-1)  n^2mℓ+2-m p^2mℓ.



Let  denote the set of all possible subgraphs that are isomorphic to T in the complete graph K_n.  
By the union bound, we have

    ∃  T_1, T_2 ⊂ G  that are isomorphic to  T: r(T_1)≠ r(T_2), L(T_1) = L(T_2) 
    
       ≤∑_T_1, T_2 ∈:   r(T_1)≠ r(T_2), L(T_1) = L(T_2)  T_1, T_2 ⊂ G

For each such pair of T_1, T_2, 

    T_1, T_2 ⊂ G = p^ |E(T_1)| + |E(T_2)| - |E(T_1 ∩ T_2)|  = p^2mℓ-|E(T_1 ∩ T_2)|,

where the last equality holds because T_1 and T_2 are isomorphic to T and |E(T)|=2mℓ.


Next for any given unlabelled graph S, we enumerate 
all the possible distinct pairs of T_1, T_2 ∈ such that T_1 ∩ T_2 is isomorphic to S,
r(T_1)≠ r(T_2), and L(T_1) = L(T_2).
Let κ_S denote the number of subgraphs S' in T such that S' is isomorphic to S,
L(T) ⊂ V(S'), and r(T) ∉ V(S').
Then there 
are at most κ_S^2 ways of intersecting T_1 and T_2 such that T_1 ∩ T_2 is isomorphic to S,
r(T_1)≠ r(T_2), and L(T_1) = L(T_2).
For each such type of intersection, there are  at most
n^|V(S)| different choices for vertex labelings of T_1∩ T_2, and 
n^2 ( |V(T)| - |V(S)| ) different choices for vertex labelings of
(T_1 \ T_2) ∪ (T_2 \ T_1). 
Hence, the total number of 
distinct pairs of T_1, T_2 ∈ such that T_1 ∩ T_2 is isomorphic to S,
r(T_1)≠ r(T_2), and L(T_1) = L(T_2) 
is at most 

    κ^2_S n^|V(S)|  n^2 ( |V(T)| - |V(S)| )  = κ^2_S  
    n^2mℓ+2-|V(S)|,

where the last equality holds due to |V(T)|=mℓ+1. 


Combining the last two displayed equations yields that 

    ∑_T_1, T_2 ∈:   r(T_1)≠ r(T_2), L(T_1) = L(T_2)  T_1, T_2 ⊂ G ≤∑_Sκ_S^2 n^2mℓ+2-|V(S)| p^2mℓ-|E(S)|.

Note that if κ_S ≥ 1, then by the definition of κ_S, 
S is isomorphic to some S' ⊂ T
such that L(T) ⊂ V(S') and  r(T)∉ V(S').
By the starlike tree property of T, S' is 
a forest with at least m disjoint trees; hence 
so is S. See fig:STexample for two 
illustrating examples. Therefore, 

    E(S) ≤ V(S) -m.

Hence,

    ∑_Sκ_S^2 n^2mℓ+2-|V(S)| p^2mℓ-|E(S)|≤∑_S  κ_S^2  n^2mℓ+2-|V(S)| p^2mℓ+m-|V(S)|.

Finally, we break the summation in the right hand side of the last displayed equation 
according to |V(S)|. 


In particular, let |V(S)|=m+k
for 0 ≤ k ≤ m(ℓ-1). Note that 
∑_Sκ_S
is at most the number of distinct subgraphs S' of T
such that L(T) ⊂ V(S'), r(T) ∉ V(S') and |V(S')|=m+k, 
which is further upper bounded by
m(ℓ-1)k 2^k,
because there
are at most m(ℓ-1)k different choices for V(S')\ L(T)
and at most 2^|V(S')|-m choices for determining whether 
to include the edges induced by V(S') in T into S'. 
Hence, 

    ∑_Sκ_S^2 
    n^2mℓ+2-|V(S)| p^2mℓ+m-|V(S)|
         =  ∑_k=0^m(ℓ-1)  n^2mℓ+2-m-k p^2mℓ-k∑_S: |V(S)|=m+k  κ_S^2 
       (a)≤∑_k=0^m(ℓ-1)  n^2mℓ+2-m-kp^2mℓ-k( m(ℓ-1)k 2^k)^2  
       (b)≤ n^2mℓ+2-m p^2mℓ 2^m(ℓ-1)∑_k=0^m(ℓ-1)  n^-k p^-km(ℓ-1)k  4^k
        = n^2mℓ+2-m p^2mℓ 2^m(ℓ-1)( 1+ 4/np)^m(ℓ-1) ,

where (a) follows from ∑_Sκ_S ≤m(ℓ-1)k 2^k,
and (b) holds due to m(ℓ-1)k≤ 2^m(ℓ-1).




Finally, we need a result to conclude that with high probability, 
for every vertex i, there exist at most 
m-1 independent ℓ-paths from i to m-1 distinct vertices in
N^G_1^* ∨ G_2_ℓ-1(i). 



Fix m, ℓ≥ 1. We start with any vertex i and m 
independent (vertex-disjoint except for i)
paths of length ℓ 
from i to m distinct vertices j_1, …, j_m, denoted by P_1, …, P_m. 
Let P̃_k denote any path of length at most ℓ-1 from i to j_k
for k=1, …, m. Let H=∪_k=1^m ( P_k ∪P̃_k ) 
and _m,ℓ denote the family of all possible graphs H with V(H)⊂ [n]
obtained by the above procedure. 

Note that if there is no subgraph isomorphic to some H ∈_m,ℓ in G_1^* ∨ G_2,
then for every vertex i, there exist at most 
m-1 independent ℓ-paths from i to m-1 distinct vertices in
N^G_1^* ∨ G_2_ℓ-1(i). 
Hence, our task reduces to proving that with high probability, G_1^* ∨ G_2 does not contain 
some H ∈_m,ℓ as a subgraph. 


We first need a lemma showing that any H ∈_m,ℓ is so “dense” that 
it appears as a subgraph in (n,p) with a vanishing small probability. 


Fix m,ℓ≥ 1. For any H ∈_m,ℓ, 

    | E(H)|  ≥  |V(H)| + m -1.

 

Recall that H=∪_k=1^m ( P_k ∪P̃_k ), where 
P_1, …, P_m is a set of m (vertex-disjoint except for i)
paths of length ℓ 
from i to m distinct vertices j_1, …, j_m, and 
P̃_k is a path of length at most ℓ-1 from i to j_k
for k=1, …, m. 

Note that we order the vertices and edges in paths starting from i. 
For each k=1, …, m, let v_k denote the
 first vertex after which P_k and P̃_k completely conincide, 
and e_k denote the edge incident to v_k 
in P̃_k. Then by definition, v_k ≠ i and
e_k ∈P̃_k \ P_k. 
Let dist(u,v) denote the 
longest distance 
between u and v in H,
and σ denote any permutation on [m] such that 

    dist(i, v_σ(1)) ≥dist(i, v_σ(2))
    ⋯≥dist(i, v_σ(m)).

Without loss of generality, we assume σ=id, , σ(k)=k. 
We claim that e_j∉ P_k ∪P̃_̃k̃ for any 
1 ≤ j < k ≤ m. 
In fact, e_j ∉ P_k, because otherwise P_j and P_k share 
a common vertex v_j ≠ i, which violates the assumption that 
P_j and P_k are vertex-disjoint except for i.
Also, e_j ∉P̃_k \ P_k, because otherwise, 
e_j is ordered before e_k in path P̃_k starting
from i, which implies dist(i,v_k) > dist(i,v_j)
and leads to a contradiction. 




Finally, we recursively define H_0=H and H_k such that
V(H_k)= V( H_k-1) and E(H_k) = E(H_k-1) \{e_k}
for k=1, …, m. We prove that H_m
is connected by induction. For the base case k=0, clearly H_0=H
is connected. Suppose H_k-1 is connected. Since we have shown
that e_j∉ P_k ∪P̃_̃k̃ for any 
1 ≤ j < k ≤ m, it follows that 
P_k ∪P̃_̃k̃⊂ H_k-1.
Note that there is a path through i 
between the two endpoints of e_k in 
P_k ∪P̃_̃k̃. Hence, the
two endpoints of e_k are still connected in
H_k. Moreover, by the induction hypothesis, H_k-1
is connected. Therefore, H_k is connected. 
and it follows from induction that H_m is connected. 
Thus, 
| E(H_m) | - | V(H_m) | ≥ -1.
Since | E(H) |= |E(H_m)| +m and | V(H)| = |V(H_m)|,
it follows that 
|E(H)|-|V(H)| ≥ m-1.



Next we state a lemma which upper bounds the number of isomorphism classes in
_m,ℓ. This upper bound is by no means tight, but suffices for our purpose. 


Fix m,ℓ≥ 1. 
Denote by _m,ℓ the set of unlabelled graphs (isomorphism classes) in 
_m,ℓ. Then 

    | _m,ℓ| ≤  (3ℓ)^m 3^2m^2ℓ.

















Recall that H=∪_k=1^m ( P_k ∪P̃_k ), where 
P_1, …, P_m is a set of m (vertex-disjoint except for i)
paths of length ℓ 
from i to m distinct vertices j_1, …, j_m, and 
P̃_k is a path of length at most ℓ-1 from i to j_k
for k=1, …, m. 
Let T = ∪_k=1^m P_k. Then T is a starlike tree rooted at i
with m branches as depicted in fig:STexample. 



We fix a sequence of {ℓ_1, …, ℓ_m} with 1 ≤ℓ_k ≤ℓ-1.
Let _ℓ_1,…, ℓ_m denote all the possible 
unlabelled graphs formed by the union of T and 
P̃_k of length ℓ_k for k ∈ [m].  
For ease of notation, let P̃_0=T. 
We enumerate _ℓ_1,…, ℓ_m according to the pairwise intersections
 P̃_j ∩P̃_k for 
0 ≤ j < k ≤ m.
Specifically, for any given sequence 
 {S_jk: 0 ≤ j <k ≤ m } 
of unlabelled graphs, we enumerate
 all the possible sequences of (P̃_1, …, P̃_k) 
 such that P̃_j ∩P̃_k is isomorphic to S_jk 
 for 0 ≤ j < k ≤ m. 
Let κ_ℓ(S) denote the number of possible
 different subgraphs that are isomorphic to S
 in an ℓ-path.
 Recall β(S) denote the number of possible different
 subgraphs that are isomorphic to S in P̃_0=T. 

Then across all 1 ≤ j<k ∈ [m], there are at most 
 κ_ℓ_j(S) κ_ℓ_k(S) ways of 
 intersecting P̃_j and P̃_k
 such that P̃_j ∩P̃_k is isomorphic to S. 
 Also, for all k ∈ [m], there are at most 
 β(S) κ_ℓ_k(S) ways of 
 intersecting P̃_0 and P̃_k
 such that P̃_0 ∩P̃_k is isomorphic to S.
 Hence, the total number of 
 distinct sequences of (P̃_1, …, P̃_k) 
 such that P̃_j ∩P̃_k isat most the
 the number n_ℓ of distinct subgraphs in an ℓ-path isomorphic to S_jk 
 for 0 ≤ j <k ≤ m is at most 
 
    ∏_1 ≤ j<k ∈ [m]κ_ℓ_j (S_jk ) κ_ℓ_k (S_jk)
     ∏_ k ∈ [m]β(S_0k) κ_ℓ_k(S_0k).

 Therefore,
 
    |_ℓ_1,…, ℓ_m|    ≤∑_{ S_jk: 0 ≤ j < k ≤ m }∏_j<k ∈ [m]κ_ℓ_j (S_jk ) κ_ℓ_k (S_jk) ∏_ k ∈ [m]β(S_0k) κ_ℓ_k(S_0k) 
       ≤∏_ 1 ≤ j<k ∈ [m] ( ∑_S_jkκ_ℓ_j (S_jk )  ) 
      ( ∑_S_jkκ_ℓ_k (S_jk) ) 
      ∏_ k ∈ [m] ( ∑_S_0kβ (S_0k) ) ( ∑_S_0kκ_ℓ_k (S_0k)  )
      
       ≤∏_j<k ∈ [m]  n_ℓ_j n_ℓ_k∏_ k ∈ [m]  n(T) n_ℓ_k
      =  ( n(T) )^m∏_ k ∈ [m] ( n_ℓ_k)^m ,

 where the last inequality holds because  
 ∑_Sκ_ℓ (S) is at most the
 the number n_ℓ of distinct subgraphs S' in an ℓ-path, 
 and ∑_Sβ (S) is at most the
 the number n(T) of distinct subgraphs S' in T.
 Note that 
 
    n_ℓ≤∑_k=0^ℓℓk 2^k
     =3^ℓ,

 because if |V(S')|=k, then 
 there are at most ℓ k different
 choices for V(S') and at most 2^k choices for 
 determining whether to include the edges induced by V(S')
 in an ℓ-path into S'. 
 Also,
 
    n(T) ≤∑_k=0^mℓ+1mℓ+1k 2^k = 3^mℓ+1.

 Combinining the last three displayed equations yields that
 
    |_ℓ_1,…, ℓ_m| ≤ 3^2m^2ℓ + m.

Therefore,

    || = ∑_ (ℓ_1, …, ℓ_m):
    1 ≤ℓ_k ≤ℓ-1|_ℓ_1,…, ℓ_m|
     ≤ (3ℓ)^m 3^2m^2ℓ.























































































With lmm:e_v_diff and lmm:H_count, we are ready to bound
the probability that (n,p) contains some H ∈_m,ℓ as a subgraph. 

Suppose G∼(n,p) with np ≥ 1 and m,ℓ≥ 1. Then it holds that 

    ∃ H ∈_m,ℓ: H ⊂ G ≤ 
    n^2mℓ-2m+1 p^ 2mℓ-m (3ℓ)^m 3^2m^2ℓ.


Note that for any H ∈_m,ℓ, 

    m ℓ+1 ≤ | V(H)|  ≤ mℓ+1 + (ℓ-2) m = 2mℓ - 2m+1,

where the lower bound holds because H contains a starlike tree with mℓ+1 distinct
vertices, and the upper bound holds when P_k and P̃_k are all vertex-disjoint
except for the source vertex and sink vertices. 

For any given integer m ℓ +1 ≤ t ≤ 2mℓ -2m+1, define

    _m,ℓ,t = { H ∈_m,ℓ: V(H) ⊂ [n], |V(H)| =t }.

and let _m,ℓ_t denote the number of unlabelled graphs (isomorphism class) in 
_m,ℓ. 





Since V(H) ⊂ [n] and |V(H)| =t, there are at most n^t different
vertex labelings for a given unlabelled graph U ∈_m,ℓ,t. Hence,

    |  _m,ℓ,t| ≤| _m,ℓ,t| n^t.

By the union bound, we have

    ∃  H ∈_m,ℓ: H ⊂ G    ≤∑_t=mℓ+1^2mℓ-2m+1∑_H ∈_m,ℓ,t H ⊂ G
        = ∑_t=mℓ+1^2mℓ-2m+1∑_H ∈_m,ℓ,t p^ | E(H) | 
       (a)≤∑_t=mℓ+1^2mℓ-2m+1∑_H ∈_m,ℓ,t p^ t + m-1
       (b)≤∑_t=mℓ+1^2mℓ-2m+1  n^t p^ t + m-1| _m,ℓ,t|   
       (c)≤ n^2mℓ-2m+1 p^ 2mℓ-m| _m,ℓ| 
       ≤ n^2mℓ-2m+1 p^ 2mℓ-m (3ℓ)^m 3^2m^2ℓ,

where (a) holds in view of lmm:e_v_diff;
(b) holds in view of eq:isorm_count
(c) holds because np ≥ 1 and t ≤ 2mℓ-2m+1;
the last inequality holds due to lmm:H_count.







Recall that a rooted graph H is a graph H 
in which one vertex has been distinguished as the root
r(H). We say two rooted graph G, H are isomorphic, denoted
by G ≅ H, if 
there is a bijection  f between V(G) and V(H) such that 
r(G) is mapped to r(H), and (u,v) ∈ E(G)
if and only if (f(u),f(v)) ∈ E(H).

Let _ℓ denote the family of all mutually non-isomorphic
rooted graphs obtained by first taking the unions of 2 distinct paths of length at most ℓ
between a source vertex and a sink vertex and then designating the source vertex as 
the root. By definition, 
all rooted cycles of length at most 2ℓ are 
contained in _ℓ.



 
Suppose G∼(n,p) and ℓ, m ≥ 1. Then it holds that 

    ∃{ H_k }_k=1^m: 
    H_k ⊂ G  and  H_k ≅  P_k  for some  P_k ∈_ℓ and  r(H_k)=r(H_k'), H_k ≠ H_k' ∀ k ≠ k' ∈ [m] 
       ≤




Given a graph P ∈_ℓ, 
let (P) denote the set of 
all possible rooted subgraphs of 
the complete graph K_n that
are isomorphic to P. 




By the union bound, we have

    ∃{ H_k }_k=1^m: 
    H_k ⊂ G  and  H_k ≅  P_k  for some  P_k ∈_ℓ and  r(H_k)=r(H_k'),  ∀ k, k' ∈ [m] 
       ≤∑_P_1, …, P_m:   P_k ∈_ℓ∑_ H_1, …, H_m:   H_k ∈(P_k),   r(H_k) = r(H_k' )  H_k ⊂ G,  ∀ k ∈ [m] .

For each such sequence of H_1, …, H_m, let
H= ∪_k=1^m H_k. Then 

    H_k ⊂ G,  ∀ k ∈ [m]  = 
    H ⊂ G = p^ |E(H)| .


Next we fix a sequence of (P_1, …, P_k) such that P_k ∈_ℓ,
Let  denote the set of all possible rooted H=∪_k=1^m H_k, 
where  H_k ∈(P_k) for k ∈ [m] and 
r(H_k) =r (H_k') for k, k' ∈ [m].
Let  denote the set of non-isomorphic 
rooted graphs (isomorphism classes) in . For each I ∈, 
let C_I denote the total number of sequences of 
H_1, …, H_m such that H_k ∈(P_k) for k ∈ [m], 
r(H_k) =r (H_k') for k, k' ∈ [m], and H=∪_k=1^m H_k satisfies

    V( H ) = { 1, 2, …, |V(I)|  }   and    H ≅ I.

Then

    ∑_ H_1, …, H_m:   H_k ∈ (P_k),   r(H_k) = r(H_k' )  p^| E(H) | 
    =∑_I ∈ C_I n|V(I)| p^|E(I)| ≤∑_I ∈ C_I 1/|V(I)|! n^|V(I)|  p^ |E(I)|.

To proceed, we need the following crucial result.


For any m≥ 1 and H ∈, it holds that |V(H)| ≤ |E(H)| - (m-1). 


Define

    f_H = |V(H)| - |E(H)|.

We prove f_H ≤ -(m-1) by induction on m. 
First, for the base case m=1, 
it suffices to consider 
H ≅ P for some P ∈_ℓ. Hence,
f_H=f_P. It follows from the definition of 
_ℓ that there exist two distinct paths
T_1 and T_2 
of length at most ℓ with the same endpoints
such that T_1 ∪ T_2=P.
Note that the function f is modular, , for any
two graphs F_1 and F_2,

    f_F_1 ∪ F_2 = f_F_1 + f_F_2 - f_F_1 ∩ F_2.
 
Therefore,

    f_P = f_T_1 + f_T_2 - f_T_1 ∩ T_2
    = 2 - f_T_1 ∩ T_2,

where the last equality holds because T_1, T_2
are paths and hence f(T_1)=f(T_2)=1. Note that 
T_1 and T_2 share the same endpoints, but are
distinct. Thus T_1 ∩ T_2 is a forest with at 
least 2 disjoint trees. Therefore, 
f_T_1 ∩ T_2≤ -2. Combining this result
with the last displayed equation gives 
f_P ≤ 0, which finishes the proof in the base case m=1.

Suppose the induction hypothesis holds for 
all 1, …, m-1, we 
aim to prove that 
it also holds for m. 
We write H= H' ∪ H_m, where 
H'= ∪_k=1^m-1 H_k. 
By induction hypothesis, f_H'≤ -(m-2)
and f(H_m) ≤ 0.
By the modularity of f,

    f_H = f_H' + f(H_m) - f_H' ∩ H_m≤ - (m-2) - f_H' ∩ H_m

Since H' ∩ H_m ≠ H_m, 
it follows that H' ∩ H_m is a proper subgraph of 
H_m. 








Next we fix a sequence of (P_1, …, P_k) such that P_k ∈_ℓ,
and for a given integer v, let _v(P_1, …, P_k) denote the set of 
all possible sequences of  H_1, …, H_m
such that H_k ∈(P_k) for k ∈ [m] and 
r(H_k) =r (H_k') for k, k' ∈ [m] and |V(H)|=v.
Then 

    ∑_ H_1, …, H_m:   H_k ∈(P_k),   r(H_k) = r(H_k' )  H_k ⊂ G,  ∀ k ∈ [m] 
    =∑_v=1^2mℓ-m+1∑_H_1, …, H_m ∈_v(P_1, …, P_k)
    p^|E(H)|












We enumerate (P_1, …, P_k) according to the pairwise intersections
H_i ∩ H_j for i< j ∈ [m]. 
Specifically, for any given sequence {S_ij: i <j ∈ [m] } 
of unlabelled rooted graphs, we enumerate
all the possible sequences of (H_1, …, H_m) in 
(P_1, …, P_k) 
such that
H_i ∩ H_j ≅ S_ij for all i<j ∈ [m].
Let κ(S,P) denote the number of rooted subgraphs S' of 
a rooted graph P 
such that S' ≅ S and r(S')=r(P). 
Then across all i<j ∈ [m], there are at most 
κ (S_ij, P_i) κ (S_ij, P_j) ways of 
intersecting H_i and H_j such that 
H_i ∩ H_j ≅ S_ij and r(H_i)=r(H_j). 
For each such type of intersection, there are at most 
n^V(H) different choices of vertex labelings of 
H = ∪_k=1^m H_k. Hence, the total number of 
distinct sequences of (H_1, …, H_m) in (P_1, …, P_k)  
such that
H_i ∩ H_j ≅ S_ij for all i<j ∈ [m] is
at most

    n^ |V(H)|∏_i<j ∈ [m]κ (S_ij, P_i) κ (S_ij, P_j).

Therefore,

    | (P_1, …, P_k) |    ≤ n^ |V(H)|∑_{ S_ij: i < j ∈ [m]}∏_i<j ∈ [m]κ (S_ij, P_i) κ (S_ij, P_j) 
       ≤ n^ |V(H)|∏_i<j ∈ [m] ( ∑_S_ijκ (S_ij, P_i)  ) 
     ( ∑_S_ijκ (S_ij, P_j)  ) 
       ≤ n^ |V(H)|∏_i<j ∈ [m]  n(P_i) n(P_j) = n^ |V(H)|∏_ i ∈ [m] ( n(P_i) )^m-1,

where the last inequality holds because  
∑_Sκ (S, T) is at most the
the number of distinct rooted subgraphs S' of 
T such that r(S')=r(T), denoted by n(T). 






Note that 

    n(T) ≤∑_k=1^|V(T)| -1 k -1 2^,

because if |V(S')|=k, then 
there are at most |V(T)| -1 k -1 different
choices for V(S') \ r(S') and at most 
2


 


where n(T) denote 




































 §.§ Completing the Proof of thm:main 





Recall that the choices of 
ℓ in eq:def_ell_1, m in
eq:def_m, 
and τ in eq:def_tau. In particular,

    ( nps^2 )^ℓ≤ n^1/2-ϵ.


Recall that G_1^* ∧ G_2 ∼(n,ps^2). Under the assumption that α≥ n^-1/2+3ϵ, we get that

    α (nps^2/2)^ℓ-2τ (τ-m) - m logτ≥ 2log n.

Hence, applying lmm:existence_ell_path, we conclude that G_1^* ∧ G_2 satisfy graph property (iii). Combing this result with lmm:graph_properties, we get that 
_1≥ 1-o(1). 



Note that G_1^* ∨ G_2 ∼(n, ps(2-s)). 
We first apply lmm:subgraph_count_general to G_1^* ∨ G_2. 
In view of nps^2 ≥log n and n ≥ e, we get that nps(2-s)≥log n ≥ 1 and 
thus

    ( 2+ 8/nps(2-s))^m(ℓ-1)  n^2mℓ+2-m( ps (2-s) )^2mℓ
       ≤ 10^mℓ n^2-2ϵ m ( 2-s/s)^2ml
    
    =n^-2+o(1),

where the first inequality holds due to (nps^2)^ℓ≤ n^1/2-ϵ; the last equality holds by our choice of ℓ and m and s=Θ(1). 
Hence, applying lmm:subgraph_count_general to G_1^* ∨ G_2, we conclude that 
with high probability, there is no pair of subgraphs T_1, T_2 ⊂ G_1^* ∨ G_2 that
are isomorphic to T such that r(T_1)≠ r(T_2) and L(T_1)=L(T_2).

Then we apply lmm:cycle_bound to G_1^* ∨ G_2. Note that 

    n^2mℓ-2m+1( p s (2-s) )^ 2mℓ-m (3ℓ)^m 3^2m^2ℓ
       ≤  n^m (1-2ϵ) - m+1 (np)^-m( 2-s/s)^2mℓ -m (3ℓ)^m 3^2m^2ℓ≤ n^ -3 + o(1),

where the first inequality holds due to (nps^2)^ℓ≤ n^1/2-ϵ;
the last equality holds by our choice of ℓ and m and s=Θ(1). 
Hence, applying lmm:cycle_bound to G_1^* ∨ G_2,
we conclude that with high probability, G_1^* ∨ G_2 does not contain 
any graph H ∈_m,ℓ as a subgraph. By the construction of 
_m,ℓ, it further implies that with high probability, for every
vertex i, there exist at most m-1 independent paths from i
to m-1 distinct vertices in N^G_1^* ∨ G_2_ℓ-1. 

Combining the above two points, we get that _2→ 1.  
Finally, in view of lmm:low_degree_path, we get that 
_3≥ 1-o(1), completing the proof of thm:main.





§ ANALYSIS OF ALG:GRAPH_MATCHING_ELL_HOP_WITNESS IN  DENSE GRAPH REGIME


Recall that Γ^k_G(u) and N^G_k(u) denotes the set of vertices at and within distance k from u in graph G, respectively, as defined in eq:def_Gamma_neighbor and eq:def_N_neighbor. The key is to show that | N^G_1^* ∧ G_2_d-1 (u) | is larger than | N^G_1^* ∨ G_2_d-1 (u)  ∩ N^G_1^* ∨ G_2_d-1 (v)| for u ≠ v by a constant factor, so that we can matches two vertices correctly based on the number of common seeded vertices in their two large neighborhoods. 


Define event 

    = 
    {| N^G_1^* ∧ G_2_d-1 (u) |  ≥3/4 (nps^2)^d-1 ,  ∀ u }.

In view of claim (i) in lmm:bollobas_neighbor_expansion with
G= G_1^* ∧ G_2 and
the fact that Γ_k^G(u) ⊂ N_k^G(u), we get that ≥ 1-n^-10. 


Define event

    = 
    {| N^G_1^* ∨ G_2_d-1 (u)  ∩ N^G_1^* ∨ G_2_d-1 (v)  | ≤1/2 (nps^2)^d-1,  ∀ u ≠ v }.

Note that due to assumption eq:assumption_b, 

    1/2 (nps^2)^d-1≥ 8 n^2d-3( ps(2-s) )^2d-2.

Hence, applying claim (ii) in lmm:bollobas_neighbor_expansion with
G= G_1^* ∨ G_2, we get that ≥ 1-n^-10. 

Recall that I_0 is the initial set of seeded vertices. 
Define event 

    = {| N^G_1^* ∧ G_2_d-1 (u) ∩ I_0 |  > 3/5 (nps^2)^d-1α ,  ∀ u }.

Since each vertex is seeded independently with probability α, 
it follows that 

    ^c    ≤^c + ^c |
       ≤ n^-10 + ∑_u| N^G_1^* ∧ G_2_d-1 (u) ∩ I_0 |  ≤3/5 (nps^2)^d-1α|
       ≤ n^-10 + n ( 
    ⌈3/4 (nps^2)^d-1⌉, α) ≤3/5 (nps^2)^d-1α
       ≤ n^-10 + n exp( - 3/200 (nps^2)^d-1α) ≤ 2 n^-1,

where the last inequality holds due to assumption eq:assumption_alpha_dense. 

Similarly, define event

    = 
    {| N^G_1^* ∨ G_2_d-1 (u)  ∩ N^G_1^* ∨ G_2_d-1 (v) ∩ I_0  | < 3/5 (nps^2)^d-1α,  ∀ u ≠ v }.

It follows that 

    ^c    ≤^c + ^c |
       ≤ n^-10 + ∑_u| N^G_1^* ∨ G_2_d-1 (u)  ∩ N^G_1^* ∨ G_2_d-1 (v) ∩ I_0  |  ≥3/5 (nps^2)^d-1α|
       ≤ n^-10 + n ( 
    ⌈1/2 (nps^2)^d-1⌉, α) ≤3/5 (nps^2)^d-1α
       ≤ n^-10 + n exp( - 1/150 (nps^2)^d-1α) ≤ 2n^-1,

where the last inequality holds again due to assumption eq:assumption_alpha_dense. 
Hence, ∩≥ 1- 4n^-1. 

Finally, since G^*_1∧ G_2 is 
a subgraph of both G^*_1 and G_2,
it follows that 

    N^G_1^* ∧ G_2_d-1 (i_2)
    ⊂{ j ∈ I_0 : π_0(j) ∈ N_d-1^G_1(π^*(i_2) ), j ∈ N^G_2_d-1 (i_2)  }.

Similarly, both G^*_1 and G_2
are subgraphs of G_1^* ∨ G_2,
it follows that 

    { j ∈ I_0 : π_0(j) ∈ N_d-1^G_1( i_1 ) , j ∈ N^G_2_d-1 (i_2)  }⊂ 
    N^G_1^* ∨ G_2_d-1( (π^*)^-1(i_1) )  ∩ N^G_1^* ∨ G_2_d-1 (i_2).

Thus, on event
∩, for every vertex i_2 ∈ V(G_2) ∖ I_0, 

    w_i_1 , i_2
       > 3/5 (nps^2)^d-1α    if  i_1 = π^*(i_2) 
    
       < 3/5 (nps^2)^d-1α    o.w. .

Hence, alg:graph_matching_ell_hop_witness
outputs π̂ =π^* on event ∩. 







§ ANALYSIS OF ALG:GRAPH_MATCHING_ELL_HOP_WITNESS_SPARSE IN SPARSE GRAPH REGIME


Recall that we assume π^*=id without loss of generality in the analysis. Before proving thm:sparse_improved, we present two key lemmas. 


The first lemma will be used later to conclude that 
the test statistic Z_u,u given in eq:Z_sparse is large for all high degree vertices u.  


Suppose G ∼(n,p) with log n ≤ np ≤ n^ϵ,
and each vertex is included in I_0 with probability α. 
Recall that ℓ and η are given in eq:def_ell
and eq:def_eta, respectively. Assume η≥ 4 log n.  Let G\ S denote the graph G with set of vertices S removed. 
Then with probability at least 1-n^-1+o(1),

    ∑_j ∈Γ_1^G(i)  | Γ_ℓ^ G \ S  (j) 
    ∩ I_0 | ≥η≥ d_i -1,   ∀ S  s.t.  
    i∈ S, |S| ≤ 3.



For every vertex i and its neighbor j ∈Γ_1^G(i), define 

    a_ij  =  | Γ_ℓ^ G\ S  (j) | ≥ 4 η  /α.

and

    b_ij  =  | Γ_ℓ^ G \ S  (j) 
    ∩ I_0 | ≥η.

Define event

    =  {  |Γ_ℓ^G \ S (j)| ≥(np)^ℓ/2^ℓ-1log (np) ,  ∀ S  s.t.  |S| ≤ 3, ∀ j  s.t. np/log (np) ≤ |Γ_1^G \ S (j)| ≤ 4np }.

Note that G\ S ∼(n-|S|,p) and 
(4np)^ℓ =o(n). 
Applying cor:neighbor_grow_sparse together with
union bounds, we
get that 

    ≥ 1- n |S| 
    exp{ -Ω((np)^2/log (np) ) }≥ 1-n^ω(1).
 
Define event  such that for every vertex i, there is at most 1 neighbor j in G such that 
|Γ_1^G \ S (j) | ≤ (np)/log (np).
Recall  is the event that the maximum degree in G is at most 4np. In view of lmm:low_degree_children, 
we have that ∩|≥ 1-n^-1+o(1). 

Recall that ℓ = ⌊
(1-ϵ)log n/log (np) ⌋ and η = 4^2ℓ+2 n^1-2ϵα. Then for sufficiently large n, 

    (np)^ℓ/2^ℓ-1log (np) ≥4 η/α .

Hence, on event ∩∩,

    ∑_j ∈Γ_1^G(i)  a_ij≥ d_i -1,   ∀ i.


Let 

    = ∪_i,j( { a_ij=1   }∩{ b_ij =0 })

Then on event ^c, for all i,j such that a_ij=1, 
b_ij=1; thus a_ij≤ b_ij for all i,j. 
Hence, on event ∩∩∩^c,
we have

    ∑_j ∈Γ_1^G(i)  b_ij≥ d_i -1,   ∀ i.



It remains to show ∩∩∩^c≥ 1-n^-1+o(1), which further reduces to proving  ≤ n^-1+o(1) by the union bound. 
Note that 

    a_ij =1, b_ij =0     ≤b_ij =0 | a_ij =1
       ≤( ⌊  4 η /α⌋,  α)  ≤η
       ≤ e^ - η,

where the last inequality follows from the Binomial tail bound eq:binomial_lower. 
By the union bound, we have

    ≤∑_i,j a_ij =1, b_ij =0 ≤ n^2 e^ - η≤ n^-2,

where the last inequality holds due to the assumption that
η≥ 4log n. 











The second lemma is useful to conclude that 
the test statistic Z_u,v given in eq:Z_sparse is small for all distinct vertices u,v.  



Assume the same setup as lmm:signal_sparse. 
With probability at least 1-4/n, for all distinct u,v, there exists
a constant C depending only on ϵ such that 

    ∑_i ∈Γ^G_1(u) ∑_j ∈Γ^G_1(v) | N_ℓ^G \{u,v}   (i) ∩ 
    N_ℓ^G \{u,v}(j) ∩ I_0| ≥η≤ C.



For two vertices i,j, define

    c_ij =  | N_ℓ^G (i) ∩ 
    N_ℓ^G (j)| ≥η/(4α)

and an event

    = {max_i ∑_j c_ij≤ 2n^4ϵ}∩{max_j ∑_i c_ij≤ 2n^4ϵ}

In view of lmm:neighbor_intersect_small,
≥ 1-2/n. 


Define  

    a_ij =  | N_ℓ^G (i) ∩ 
    N_ℓ^G (j) ∩ I_0|   ≥η.

and an event 

    = {max_i ∑_j a_ij≤ 2n^4ϵ}∩{max_j ∑_i a_ij≤ 2n^4ϵ}


Moreover, let 

    = ∪_i,j[ { c_ij=0   }∩{ a_ij =1 }]

Then on ^c, for all i,j such that c_ij=0, 
a_ij=0; thus a_ij≤ c_ij for all i,j. 
Hence, ∩^c ⊂ and thus

    ≥∩^c≥ - .

Note that 

    c_ij =0, a_ij =1     ≤a_ij =1 | c_ij =0
       ≤( ⌊η / 4α⌋,  α)  ≥η
       ≤ e^ - 2η

By the union bound, we have

    ≤∑_i,j c_ij =0, a_ij =1 ≤ n^2 e^ - 2η≤ n^-6,

where the last inequality follows from the 
assumption that η≥ 4 log n. 
Thus ≥ 1-3/n. 


Fix a pair of vertices u ≠ v in the sequel, and 
let 

    b_ij = | N_ℓ^G \{u,v}   (i) ∩ 
    N_ℓ^G \{u,v}(j) ∩ I_0| ≥η

and

    _u,v = {max_i ∑_j b_ij≤ 2n^4ϵ}∩{max_j ∑_i b_ij≤ 2n^4ϵ}

Then by construction, 
b_ij≤ a_ij and thus
⊂_u,v. 


Let X_i = G(u,i) for i ∈ [n] 
and X_n+j=G (v, j) for j ∈ [n]. 
Define

    R_u,v = ∑_i ,j ∈ [n] \{u, v} b_ij X_i X_n+j,

which is a degree-2 polynomial of X_i's. 
Note that {b_ij; i,j ∈ [n] \{u, v}} only depends on G\{u,v}
and hence is independent from
X_i's. Moreover, X_i's are i.i.d. (p).

We condition on {b_ij} such that event _u,v holds. 
Let  

    μ_0= R_u,v| b  = p^2∑_ij b_ij≤ 2p^2n^1+4ϵ≤ 2 n^-1+6ϵ.

and

    μ_1= 
    max{max_i ∑_j b_ij X_j | b,
    max_j ∑_i b_ij X_i  | b}≤ 2p n^4ϵ≤ 2 n^-1+5ϵ.












By a concentration inequality for multivariate polynomials <cit.>, there exists a constant C>0 depending only on ϵ such that

    R_u,v≥ C | b≤  n^-3 .

Thus R_u,v≥ C |_u,v≤ n^-3.








Define event 
_u,v =
{ R_u,v≤ C  }
and 
=∩_u ≠ v_u,v.
It follows that  

    _u,v∩_u,v≤_u,v|_u,v≤   n^-3 .

Since ⊂_u,v, it 
further follows that 
_u,v∩≤  n^-3 .
By a union bound over u,v, we have
∩≤  n^-1.
Hence, 
≤∩ + ^c ≤  4/n.





With lmm:signal_sparse and lmm:noise_sparse, 
we are ready to finish the proof of
thm:sparse_improved.



Recall that τ is given in eq:def_tau and the definition of high-degree vertices. 
We first prove  that alg:graph_matching_ell_hop_witness correctly matches the high-degree
vertices in G_1^* ∧ G_2 with high probability. 

Recall the definition of Z give in eq:Z_sparse.
Applying lmm:signal_sparse with G= G_1^*∧ G_2, we get that with high probability, 
for all high-degree vertices u, 

    Z_u,u≥τ -1 = nps^2/log (nps^2)  -1 .


Moreover, by definition, 

    w^u,v_i,j   ≤| { k ∈ I_0: π_0(k) ∈ N^G_1\{ u, v}_ℓ (i),  
    k ∈ N^G_2\{u,v}_ℓ (j) }| 
       ≤| N^G_1^* ∨ G_2 \{ u, v}_ℓ (i)
     ∩  N^G_1^* ∨ G_2 \{u,v}_ℓ (j) ∩ I_0   |.

Applying lmm:noise_sparse with G= G_1^*∨ G_2, we get that with high probability, 

    Z_u,v≤ C,   ∀ u ≠ v

for a constant C>0 only depending on ϵ. 
Since for sufficiently large n, τ≥ C+1, it follows
that alg:graph_matching_ell_hop_witness correctly
matches all high-degree vertices with high probability. 


The proof of correctness for matching low-degree vertices is the same as alg:graph_matching_ell_hop
and thus omitted. 














§ PROOF OF THM:CONVERSE


Suppose nps^2-log n=c for c<+∞. 
Since G_1^* ∧ G_2 ∼(n, ps^2), 
classical random graph theory shows that 
the distribution of the number of isolated vertices in G_1^* ∧ G_2 converges to (e^-c), see, , <cit.>.
Let _1 denote the event that there are at least two isolated vertices in G_1^* ∧ G_2. 
Then _1 =Ω(1). 

Let _2 denote the event that there are at least two isolated vertices that are unseeded in G_1^* ∧ G_2. Since each vertex is seeded  with probability α independently across different vertices and from the graphs G_1 and G_2, it follows that 
F_2≥F_1 (1-α)^2=Ω((1-α)^2 ). 

Since the prior distribution of π^* is uniform, the maximum likelihood estimator π̂_ ML  minimizes the error probability π̂≠π^* among all possible estimators and thus we only need to find when MLE fails. 


Recall that I_0 is the seed set. 
Let  denote the set of all possible permutations π such that π(i)=π^*(i) for i ∈ I_0. 
Under the seeded model (n,p;s,α), the maximum likelihood estimator π̂_ ML is given by the minimizer of the (restricted) quadratic assignment problem, namely, 

    π̂_ ML∈minmin_π∈  G_1  -  Π G_2 Π^⊤_F^2,

where Π is the permutation matrix corresponding to permutation π; or equivalently, 

    π̂_ ML∈max _π∈G_1Π G_2 Π^⊤.



Let I denote 
the union of the initial seed set and the set of all
 non-isolated vertices in G_1^* ∧ G_2. Then I^c
 is the set of isolated vertices that are unseeded in G_1^* ∧ G_2.
Let   denote the set of 
all possible permutations π such that π(i)=π^*(i) for i ∈ I. Then π^* ∈⊂. Note that for any π∈, we have

    G_1  Π G_2 Π^⊤   ≥∑_(i, j) ∈ I× I G_1( π(i),π(j) ) G_2(i, j)  
       (a)=∑_(i, j) ∈ I× I G_1( π^*(i), π^*(j) ) G_2(i,j) 
        =∑_(i, j)  G_1( π^*(i), π^*(j) ) G_2(i,j),

where (a) follows from π(i)=π^*(i) for i ∈ I;
the last equality holds due to G_1( π^*(i), π^*(j) ) G_2(i,j) =0 for all (i,j) ∉ I × I. 
Hence, there at at least |I^c|! -1 different permutations in  whose likelihood is at least as large as the ground truth π^*, and hence the 
MLE is correct with probability at most 1/(|I^c|!-1). Note that on event _2, |I^c| ≥ 2; hence,  
MLE is correct with probability at most 1/2. 
In conclusion, MLE is correct with probability at most (1/2)_2 =Ω((1-α)^2). 

















§ PROOF OF LMM:GRAPH_PROPERTIES 



Claim (i): For each vertex i, its degree d_i ∼(n-1,p). 
By the union bound, the probability that G has an isolated vertex is 

    n(1-p)^n-1≤  n e^ - (n-1) p =o(1),

where the last equality holds due to the assumption that  np - log n → +∞. 



Claim (ii):
Fix any pair of two distinct vertices i,j, define

    _ij = { G(i,j) =1 }∩{ d_i ≤τ}∩{  d_j ≤τ}.

It suffices to show

    ∪_i≠ j_ij≤ n^-1+o(1).

Note that 

    d (i) ≤τ, d (j) ≤τ | G(i,j)=1    = (  ( n-2, p ) ≤τ -1)^2 
       ≤(  ( n-2, p ) ≤τ)^2

In view of Binomial tail bounds given in thm:binom_lower_tail and τ=o(np), we have that

    ( n-2, p ) ≤τ≤exp( - (n-2) p ( 1  - √(τ/ (n-2) p))^2 )
    =exp( - (1-o(1)) np  ).

Combining the last two displayed equations yields that

    _ij    = G(i,j)=1  d (i) ≤τ, d (j) ≤τ | G(i,j)=1
       ≤  p exp( - 2 (1-o(1)) np )


By the union bound,

    ∪_i≠ j E_ij   ≤ n^2 E_ij
       ≤ n^2 p exp( - 2 (1-o(1)) np )
    =n^-1+o(1),

where the last equality holds due to np-log n→ +∞.





§ PROOF OF LMM:LOW_DEGREE_PATH 


Let d_i denote the degree of vertex i in G_1^* ∧ G_2 and 
A denote the adjacency matrix of G_1^* ∨ G_2. 
For every pair of three distinct vertices i,j,k, define





    _ijk = { A_ik=1, A_jk=1 }∩{ d_i  ≤τ}∩{ d_j  ≤τ}.

It suffices to show that ∪_i,j,k F_ij≤ n^-1+o(1). 
Since G_1^*∨ G_2 ∼(n, ps(2-s)), it follows that

    A_ik=1, A_jk=1  = A_ik=1A_jk=1 = ( ps (2-s) )^2  
    ≤ p^2.

Moreover, since G_1^* ∧ G_2 ∼(n, ps^2), it follows that 

    { d_i  ≤τ}∩{ d_j  ≤τ}| A_ik=1, A_jk=1
      ≤( (n-3, ps^2) ≤τ)^2.

 In view of Binomial tail bound eq:binomial_lower and τ=o(nps^2), we have that
 
    (n-3, ps^2) ≤τ   ≤exp( - (n-3) ps^2 ( 1  - √(τ/ (n-3) ps^2))^2 ) 
        =exp( - n ps^2 ( 1 -o(1 ) ) )

 It follows that
 
    _ijk≤ p^2   exp( - 2 n ps^2   ( 1 -o(1 ) ) )

By the union bound, we have that

    ∪_i,j,k F_ij≤ n^3 p^2 exp( - 2 n ps^2   ( 1 -o(1 ) ) ) =n^-1+o(1).

where the last equality holds due to nps^2 ≥log n 
and log (np) = o (nps^2). 








§ NEIGHBORHOOD EXPLORATION IN (N,P)

Throughout this section, we assume graph G ∼(n,p)
with n p ≥log n. We first claim that the max degree in G 
is at most 4np with probability at least 1-1/n.  

Assume graph G ∼(n,p) with np ≥log n.  Let 

    ={max_v ∈ V(G) d_v ≤  4np }.

Then 

    ≥ 1- n^-1.



By the Binomial tail bound eq:binomial_upper,

    d_i ≥ 4 n p   =  (n-1, p) ≥ 4 n p ≤exp( - 2 np).

The proof follows by the union bound and the assumption
that np ≥log n. 



 
We fix a vertex u throughout this section, and abbreviate Γ^G_k(u) as Γ_k(u) and N^G_k(u) as N_k(u) for
simplicity. We are interested in studying the growth of |Γ_k(u)| as k increases. Note that |Γ_1(u)| is the degree d_u of vertex u in G.
Since the average
degree is (n-1)p, we expect typically |Γ_k(u)| grows as (np)^k. This is indeed true in the dense regime with np ≥ n^ϵ. 




 §.§ Dense Regime





The following lemma is adapted from <cit.>.


Suppose np ≥ n^ϵ for an arbitrarily small constant ϵ>0 and d is chosen such that 

    (np)^d-1≤n/8   and    (np)^d ≥ n log n

If n is sufficiently large, then with probability at least 1-n^-10, the following claims hold:


  * For every vertex u, 

    |  Γ_k (u) - (np)^k| ≤1/4 (np)^k.   ∀ 0 ≤ k ≤ d-1.


  * For every two distinct vertices u and v, 

    | N_d-1 (u) ∩ N_d-1 (v) |    ≤ 8 n^2d-3 p^2d-2.




lmm:bollobas_neighbor_expansion also upper bounds 
|Γ_d-1(u) ∩Γ_d-1(v)| for two distinct vertices u, v by 8p^2d-2n^2d-3. To see this intuitively, note that in the dense regime, Γ_d-2(u) ∩Γ_d-2(v) is typically 
of a much smaller size comparing to either Γ_d-2(u) or Γ_d-2(v). Hence, the majority of vertices w 
 in Γ_d-1(u) ∩Γ_d-1(v) are connected to some vertex in Γ_d-2(u) ∖Γ_d-2(v) and to some vertex in Γ_d-2(v) ∖Γ_d-2(u).  For a given vertex w ∉ N_d-2(u) ∪ N_d-2(v), since |Γ_d-2(u) ∖Γ_d-2(v)| ≤ |Γ_d-2(u)| ≤ 2 (np)^d-2 and similarly for
 |Γ_d-2(v) ∖Γ_d-2(u)|, w connects to some vertex in Γ_d-2(u) ∖Γ_d-2(v) with probability at most 2p (np)^d-2, and connects to some vertex in Γ_d-2(v) ∖Γ_d-2(u) independently with probability 2p(np)^d-2. Moreover, there are at most n such potential vertices w to consider. Hence, we expect |Γ_d-1(u) ∩Γ_d-1 (v)| to be smaller than 2n [ 2p (np)^d-2 ]^2= 8p^2d-2n^2d-3. 
 









 §.§ Sparse Regime

In contrast, in the sparse regime where

    np - log n → + ∞.

there exist vertices with small degrees, , |Γ_1(u)| is much smaller than
np. 


Hence, we cannot expect |Γ_k(u)| grows like (np)^k for all vertices u. Nevertheless, the following lemma shows that
conditional on |Γ_1(u)| is large, then |Γ_k (u)| ≍ (np) |Γ_k-1(u)|
for all 2 ≤ k ≤ d for some d
with high probability. 



Suppose 

    np ≥log n    and     
     p (4np)^d-1 = o(1).
 
Let u be a fixed vertex. For each 1 ≤ k ≤ d, define
 
    _k ={ |Γ_k(u)| ∈ I_k = [ τ( np/2)^k-1, (4np)^k] }
 
 for 1 ≤τ≤ np. Then  for 2 ≤ k ≤ d, 

    _k |_1, …, _k-1≥ 
    1 -exp( -  Ω(τ( np/2)^k-1) ).

It readily follows that

    _d ∩_d-1∩⋯∩_2 |_1≥  1 - exp( -  Ω(τ np ) ).



Fix 2 ≤ k ≤ d. 
Conditional on Γ_k-1(u) and N_k-1(u), the probability of a given
vertex v ∉ N_k-1(u) being connected to some vertices in Γ_k-1(u) is

    p_k ≜ 1- (1-p)^|Γ_k-1(u)|.


Therefore, conditional on |Γ_k-1(u)| and |N_k-1(u)|, 

    |Γ_k(u)| ∼( n - |N_k-1(u)|, p_k  )

Note that conditional on _1, …, _k-1, 

    |N_k-1(u)| = ∑_i=0^k-1 | Γ_i (u) | ≤∑_i=0^k-1 (4np)^i =  (4 np)^k -1 /4np-1 =o(n),

where the last equality holds due to the assumption eq:neighbor_p_assumption and 
k ≤ d.
Moreover, in view of the assumption eq:neighbor_p_assumption, conditional on _1, …, _k-1, 

    ( 1-o(1) ) p  τ( np/2)^k-2≤ p_k ≤  p (4np)^k-1.

Hence, for 2 ≤ k ≤ d,

    |Γ_k(u)|  ∉ I_k |_1, …, _k    ≤( n -o(n), ( 1-o(1) ) p  τ( np/2)^k-2) ≤τ( np/2)^k-1
        + ( n , p (4np)^k-1) ≥  (4np)^k
       ≤exp( - Ω(τ( np/2)^k-1) ) + exp( - 4^k-1 (np)^k ) 
       ≤exp( -  Ω(τ( np/2)^k-1) ).

Finally, we note that 

    _d ∩_d-1∩⋯∩_2 |_1    =_2 |_1_3 |_1, _2⋯_d |_1, …, _d-1
       ≥∏_i=0^d-1( 1 - exp( -  Ω(τ( np/2)^k-1) ) ) 
       ≥ 1 - ∑_i=0^d-1exp( -  Ω(τ( np/2)^k-1) ) 
       ≥ 1- exp( -  Ω(τ np ) ).



With lmm:neighbor_grow_sparse, we have the following 
immediate corollary. 

Suppose eq:neighbor_p_assumption holds. Define
event 

    = {  |Γ_k  (u) | ∈ I_k,  ∀ 1 ≤ k ≤ d,   ∀ u  s.t. τ≤ |Γ_1(u)| ≤ 4np }

Then 

    ≥ 1- n exp( -  Ω(τ np ) ).



Note that 

    ^c = ∪_u( {τ≤ |Γ_1(u)| ≤ 4np  }∩{  |Γ_k  (u) | ∉ I_k,  ∀ 1 ≤ k ≤ d }).

Hence, it follows from the union bound that 

    ^c    ≤∑_u 
    {τ≤ |Γ_1(u)| ≤ 4np  }∩{  |Γ_k  (u) | ∉ I_k,  ∀ 1 ≤ k ≤ d }
       ≤∑_u  |Γ_k  (u) | ∉ I_k,  ∀ 1 ≤ k ≤ d  |τ≤ |Γ_1(u)| ≤ 4np 
       ≤ n exp( -  Ω(τ np ) ),

where the last inequality follows from lmm:neighbor_grow_sparse.





Next, we upper bounds
|N_d(u) ∩ N_d(v)| for two distinct vertices u, v in the sparse regime. We need to introduce 
 
    Γ^*_k,ℓ (u, v) = {  
     w ∈Γ_k(u) ∩Γ_ℓ(v) : 
     Γ_1 ( w) ∩( Γ_k-1(u) ∖Γ_ℓ-1(v) ) ≠∅,  Γ_1 ( w) ∩( Γ_ℓ-1(v) ∖Γ_k-1(u) ) ≠∅}

 and we abbreviate Γ^*_k,k(u,v) as Γ^*_k (u,v)
 for simplicity. 
By definition, for any d ≥ 1, 

    Γ_d (u) ∩Γ_d (v) ⊂∪_k=1^dΓ_d-k( Γ^*_k (u, v) ).

and 

    N_d(u) ∩ N_d(v) ⊂∪_ℓ=-d^d ∪_k=0^d N_d-k - max{ℓ, 0}( Γ^*_k+ℓ, k (u,v) ).

The following lemma gives an upper bound to | Γ^*_k,ℓ (u,v)  | in high probability. 




For two distinct vertices u, v, define

    Δ_k,ℓ = { | Γ_k-1(u) |  ≤ (4np)^k-1,   
    | Γ_ℓ-1(v) |  ≤ (4np)^ℓ-1}.

For all k ≥ 1,  

    | Γ^*_k,ℓ(u,v) | ≥γ_k+ℓ|Δ_k,ℓ≤1/n^8,

where 

    γ_k  = 
    
    24 log n     if  np^2 ( 4np)^k-2≤ 4 log n 
    
    4 np^2 ( 4np)^k-2    o.w.




Conditional on _k-1(u), Γ_k-1(u) and _ℓ-1(v),Γ_ℓ-1(v), the probability that a  vertex w ∉_k-1(u) ∪_ℓ-1(v) being connected to some vertex in Γ_k-1(u) ∖Γ_ℓ-1(v) is 

    1- (1-p)^| Γ_k-1(u) ∖Γ_ℓ-1(v)| ≤ p | Γ_k-1(u) ∖Γ_ℓ-1(v)| ≤ p | Γ_k-1(u)|  .

Similarly, the probability that w is connected to some vertex in Γ_ℓ-1(v) ∖Γ_k-1(u) is 

    1- (1-p)^| Γ_ℓ-1(v) ∖Γ_k-1(u)| ≤ p | Γ_ℓ-1(v) ∖Γ_k-1(u)| ≤ p | Γ_ℓ-1(v)|.

Since Γ_k-1(u) ∖Γ_ℓ-1(v) is disjoint from Γ_ℓ-1(v) ∖Γ_k-1(u), the probability that w ∈Γ^*_u,v is at most p^2 | Γ_k-1(u)| | Γ_ℓ-1(v)|. 
Moreover, there are at most n vertices w ∉_k-1(u) ∪_ℓ-1(v).  
Hence,

    | Γ^*_k,ℓ(u,v) | ≥γ_k+ℓ|Δ_k,ℓ≤( n, p^2 (4np)^k+ℓ-2 )  ≥γ_k+ℓ.

If n p^2 (4np)^k+ℓ-2 ≤ 4 log n, then by the choice of γ_k+ℓ=24 log n, we have γ_k+ℓ≥ 6 n p^2 (4np)^k+ℓ-2. It follows from eq:binomial_upper_2 that 

    ( n, p^2 (4np)^k+ℓ-2 )  ≥γ_k+ℓ≤ 2^-γ_k+ℓ =2^-24 log n≤1/n^8.

If n p^2 (4np)^k+ℓ-2 ≥ 4 log n, then by the choice of 
γ_k+ℓ = 4 n p^2 (4np)^k+ℓ-2, it follows from eq:binomial_upper that 

    ( n, p^2 (4np)^k+ℓ-2 )  ≥γ_k+ℓ≤exp( - 2n p^2 (4np)^k+ℓ-2 ) ≤1/n^8.



































































With lmm:neighbor_intersect, we are ready to upper bound 
|N_d (u) ∩ N_d (v) | for d large enough. 


For a given small constant ϵ>0, choose an integer 1 ≤ d ≤ n such that

    ( 4np )^d ≥ n^1-ϵ

For each vertex u, define event

    _u = {∑_v |N_d (u) ∩ N_d (v) | > 4^2d+1 p^2d n^2d-1≤ 2 n^4ϵ}

and =∩_u _u. Then  
 
    ≥ 1- 2n^-1.



Define an event 

    = ∩_u ≠ v∩_1≤ k ≤ d ∩_1≤ k ≤ℓ{ |Γ^*_k,ℓ (u, v) | ≤γ_k+ℓ}

Recall  defined in eq:def_calE. Note that 

    (∩)^c = (^c ∩) ∪^c.

Therefore,  

    (∩)^c ≤^c ∩ + ^c.

Note that ^c≤ 1/n. Moreover,

    ^c ∩   ≤∑_u≠ v∑_ 1 ≤ k ≤ d ∑_1≤ℓ≤ d {  |Γ^*_k,ℓ (u, v)| ≥γ_k+ℓ}∩
       (a)≤∑_u≠ v∑_1 ≤ k ≤ d ∑_1≤ℓ≤ d {  |Γ^*_k,ℓ (u, v)| ≥γ_k+ℓ}∩Δ_k,ℓ
       ≤∑_u≠ v∑_ 1 ≤ k ≤ d ∑_1≤ℓ≤ d    |Γ^*_k,ℓ (u, v)| ≥γ_k+ℓ|Δ_k,ℓ≤  n^-4,

where (a) follows from  ⊂Δ_k
and the last inequality holds in view of 
lmm:neighbor_intersect and d ≤ n. 
Therefore, (∩)^c≤ 2/n. 

To prove the lemma, it suffices to argue that 
∩⊂. 
To see this, let us assume that ∩ holds in the 
sequel. 
Note that 

    N_d(u) ∩ N_d(v) ⊂∪_ℓ=-d^d ∪_k=0^d N_d-k - max{ℓ, 0}( Γ^*_k+ℓ, k (u,v) ).

It follows that 

    | N_d(u) ∩ N_d(v) | 
    ≤∑_ℓ=-d^d ∑_k=0^d 
    | Γ^*_k+ℓ, k (u,v) | (4np)^d-k-max{ℓ,0 }

Set k_0

    k_0= ⌊2ϵlog n/log (4np) ⌋

Then 

    |N_2k_0(u)| ≤∑_k=0^2k_0 (4np)^k = (4np)^2k_0+1 -1 /4np -1 ≤ 2 (4np)^2k_0≤ 2n^4ϵ,

where the second-to-the-last inequality holds due to 2np ≥ 1. 
Note that for all v ∉ N_2k_0(u), we have

    | Γ^*_k,ℓ (u,v) | =0 ,   ∀ 0 ≤ k +ℓ≤ 2k_0

and thus

    | N_d (u) ∩ N_d (v) | 
       ≤∑_ℓ=-d^d ∑_k=0^d 0 ≤ k+ℓ≤ d2k+ℓ≥ 2k_0+1γ_2k+ℓ (4np)^d-k-max{ℓ,0}
       ≤∑_ℓ=-d^d ∑_k=0^d 0 ≤ k+ℓ≤ d2k+ℓ≥ 2k_0+1( 24 log n + 4 np^2 
    (4np)^2k+ℓ-2)  (4np)^ d -k -max{ℓ,0}
       ≤  192 log n (4np)^ d-k_0-1/2  
    + 32 np^2 (4np)^ 2d-2 
       ≤ 64 np^2 (4np)^ 2d-2   = 4^2d+1 p^2d n^2d-1,

where the last inequality holds due to 
(4np)^d+k_0+1/2≥ 6 n log n for n sufficiently large. 
Hence, for every u, 

    ∑_v |N_d (u) ∩ N_d (v) | > (4)^2d+1 p^2d n^2d-1≤ |N_2k_0(u)|
    ≤ 2 n^4ϵ.

As a consequence, ∩⊂. 







































































































 §.§ Graph Branching in Sparse Regime


In this subsection, we describe a branching process to explore the vertices in N_k(u). See, , <cit.> for a reference. 



We begin with u and apply breadth-first-search to explore the vertices in N_k(u). In this process,
all vertices will be “live”, “dead”, or “neutral”. The live vertices will be contained in a queue. Initially,
at time 0, u is live and the queue consists of only u, and all the other vertices are neutral. At each time step
t,  a live vertex v is popped from the head of the queue, and we check all pairs {v, w} for all neutral vertices
w for adjacency. The poped vertex v is now dead and those neutral vertices w adjacent to v are added to the end
of the queue (in an arbitrary order) and now are live. The process ends when the queue is empty.


Note that such a branching process constructs a tree T(u) rooted at u. In particular, 
at each time step, those neutral vertices w adjacent to the poped vertex v can be viewed as children of v. 
For each vertex v in T(u), 


abusing notation slightly, we let 
T_k(v) denote the subtree rooted at v of depth k  in T(u) 
and Π_k(v) denote the 
set of vertices at distance k from root v in subtree T_k(v).
Note that by construction, Π_k(u)=Γ_k(u) for root u.














We are interested in bounding |Π_k(v)| for each children v of root u. The following lemma shows that with high probability, 
for all childen v of root u such that 
|Π_1(v)| ≥τ, |Π_k(v)| grows at least  as τ( np/2 )^k-1.

Let u be the root vertex and 1 ≤τ≤ np. Define 

    _1 = { |Π_1(u)| ≤ 4np }∩{ |Π_1(v)| ≤ 4np ,  ∀ v ∈Π_1(u) },

and for each 2 ≤ k ≤ d define
 
    _k =
     {  |Π_k(v)| ≤ (4np)^k,  ∀ v ∈Π_1(u)   }∩{ |Π_k(v)| ≥τ( np/2 )^k-1, 
     ∀ v ∈Π_1(u)  s.t.   |Π_1(v)| ≥τ}
 
Suppose 

    np ≥log n    and     
      (4np)^d+1 = o(n).
 
Then  for 2 ≤ k ≤ d, 

    _k |_1, …, _k-1≥ 
    1- 
    8np exp(  - Ω( τ( np/2)^k-1) ).

It readily follows that

    _d ∩_d-1∩⋯∩_2  |_1 ≥  1  - 8np exp( -Ω(τ np ) ).

Moreover, by letting 

    _u = ( _d ∩_d-1∩⋯_2 ) ∪_1^c,

we have 

    _u^c≤ 8np exp( -Ω(τ np ) ).




Fix 2 ≤ k ≤ d.
Suppose the neighbors of root vertex u are added to the queue in the order of 
v_1, v_2, …, v_d_u, where d_u= | Π_1(u)|. 
Then by the branching process aforementioned, 
Π_k(v_1), …, Π_k(v_i-1) are revealed
before Π_k(v_i). 

Fix 1 ≤ i ≤ d_u and define 

    _k,i = 
    { | Π_k (v_j) | ≤ (3np)^k,  ∀ j ∈ [i] }∩{ |Π_k(v_j)| ≥τ( np/2)^k-1, 
     ∀ j ∈ [i]  s.t.   |Π_1(v_j)| ≥τ}.

Then _k=_k,d_u.


Conditional on Π_k-1(v_i), the probability of a given
neutral vertex w being connected to some vertices in Π_k-1(v_i) is

    p_k ≜ 1- (1-p)^|Π_k-1(v_i)|≤ p |Π_k-1(v_i)|.
 

On the one hand, there are at most n neutral vertices. 
Therefore, conditional on |Π_k-1(v_i)|,  
|Π_k(v_i)| is stochastically dominated by 
( n ,   p |Π_k-1(v_i) |  )
and hence 

    |Π_k(v_i)|  ≥  (4np)^k|_1,…, _k-1, _k,i-1   ≤(  n, p (4np)^k-1 ) ≥ (4np)^k 
       ≤exp( -  4^k-1 (np)^k ),

where the last inequality follows from the Binomial tail bound eq:binomial_upper.

On the other hand, in view of assumption eq:neighbor_p_assumption_2, 
conditional on _1,…, _k-1, _k,i-1 
there are at least 

    n - 1 - ∑_i=1^d_u∑_ℓ=0^k-1 | Π_ℓ (v_i) |
    -∑_j=1^i-1  |Π_k(v_j)| 
    ≥ n - 1 - 4np ∑_ℓ=0^k (4np)^ℓ  
    = n- (4 np)^k+2 -1 /4np-1 = n-o(n)
 
neutral vertices to be connected to some vertices in Π_k-1(v_i),
and for each  v_i such that |Π_1(v_i)| ≥τ, 

    p_k = 1- (1-p)^|Π_k-1(v_i)|≥( 1-o(1) ) p  τ( np/2)^k-2.

Therefore, conditional on _1,…, _k-1, _k,i-1,
|Π_k(v_i)| is stochastically lower bounded by  

    ( n -o(n) , ( 1-o(1) ) p  τ( np/2)^k-2)

and hence for 2 ≤ k ≤ d,

    |Π_k(v_i)|  ≥τ( np/2)^k-1|_1,…, _k-1, _k,i-1
       ≤( n -o(n), ( 1-o(1) ) p  τ( np/2)^k-2) ≤τ( np/2)^k-1
       ≤exp( - Ω(  τ( np/2)^k-1) ).

Combining eq:neighbor_upper and eq:neighbor_lower yields that

    _k,i|_1,…, _k-1≥_k,i-1|_1,…, _k-1( 1- 2exp( - Ω(  τ( np/2)^k-1) )
     ).

Therefore,

    _k |_1,…, _k-1
    
    
     ≥ 1- 8np exp( - Ω( τ( np/2)^k-1) ).

Finally, we note that 

    _d ∩_d-1∩⋯∩_2 |_1
        =_2 |_1 _3 |_1, _2⋯_d |_1, …, _d-1
       ≥∏_k=2^d( 1- 8np exp( - Ω( τ( np/2)^k-1) ) ) 
       ≥ 1 -  8np
    ∑_k=2^dexp( - Ω( τ( np/2)^k-1) ) 
       ≥ 1- 8 np exp( -Ω(τ np )).

Moreover, by the definition of _u,
we have

    _u^c = (_d ∩_d-1∩⋯∩_2 )^c ∩_1 .

Hence,

    _u^c    =
    _1(_d ∩_d-1∩⋯∩_2 )^c |_1 
       ≤(_d ∩_d-1∩⋯∩_2 )^c |_1 
       ≤ 8 np exp( -Ω(τ np )),

completing the proof. 



The following lemma shows that with high probability, for all possible root vertex u,
it has at most one children v with |Π_1(v)| ≤τ for τ=o(np).
Let A denote the adjacency matrix of G.
For three distinct vertices u, v, w, define

    _u,v,w = { A_u,v =1, A_u, w =1}∩{ |Π_1(v)| ≤τ}∩{Π_1(w) ≤τ}.

and 
= ∪_u, v, w_u,v,w.
 
Assume 

    np ≥log n,  and  
    np =o(n^1/2),  and τ=o(np).

Then 

    ∩≤ n^-1+o(1).




 







By the union bound,

    ∩≤∑_u,v,w_u,v,w∩

it reduces to bounding _u,v,w∩.

Let N_v and N_w denote the number of 
neutral vertices in the branching process when v and w are popped from the head of the queue,
respectively. Then conditional on N_v and N_w, 
|Π_1(v)| and |Π_1(w)| are independent and
|Π_1(v)| ∼( N_v, p )  and |Π_1(w)| ∼(N_w, p).
On event , both N_v and N_w is at least 
n-1-4np-(4np)^2=n-o(n) in view of the assumption 
np=o(n^1/2). Therefore, 

    { |Π_1(v)| ≤τ, Π_1(w) ≤τ}∩| A_u,v=1, A_u,w=1 
       =∑_i,j=1^n-o(n){ |Π_1(v)| ≤τ, Π_1(w) ≤τ, N_v=i, N_w=j  }∩| A_u,v=1, A_u,w=1 
       ≤∑_i,j=n-o(n)^n |Π_1(v)| ≤τ, Π_1(w) ≤τ,  N_v=i, N_w=j | A_u,v=1, A_u,w=1 
        = ∑_i,j=n-o(n)^n N_v=i, N_w=j | A_u,v=1, A_u,w=1  |Π_1(v)| ≤τ, Π_1(w) ≤τ| N_v =i, N_w=j
        = ∑_i,j=n-o(n)^n N_v=i, N_w=j | A_u,v=1, A_u,w=1 ( ( n-o(n), p ) ≤τ)^2
       ≤exp(- 2 (1- o(1) ) np ),

where the last inequality holds due to the Binomial tail bound eq:binomial_lower
and the assumption that τ=o(np).
It follows that 

    _u,v,w∩≤ p^2 exp( -2 (1- o(1) ) np ) =o(1/n^3),

where the last equality holds due to np ≥log n.



Now we are ready to prove our main proposition. Let _u denote the event that tree T(u) satisfies 


  * u has at most one children v 
such that |Π_1(v)| ≤τ. 

  * For each children v of u with |Π_1(v)| ≥τ, |Π_k(v)| ≥τ( np/2)^k-1
for all 1 ≤ k ≤ d. 

Define =∩_u _u. 

Suppose eq:neighbor_p_assumption_2 and
eq:low_degree_childen_assump hold and τ→∞. Then 

    ≥ 1- 3n^-1+o(1).


 
 Note that 
 
    ( ∩_u _u ) ∩(^c ∪^c ) ∩⊂.

 Hence, 
 
    ≥ 1- ∑_u ^c_u  - ∩ - ^c .

 In view of lmm:branching_process, we have
 
    ^c_u ≤ n^-ω(1) .

 By lmm:low_degree_children, we have
 
    ∩≤ n^-1+o(1).

By lmm:graph_properties, we have
≥ 1-1/n. 
Then the conclusion readily follows. 
 



















































































§ TIME COMPLEXITY OF ALGORITHM <REF> 
 

Recall that in Algorithm <ref>, we need to 
efficiently check whether there exist m independent ℓ-paths from a given vertex i_2 to a set of
m seeded vertices L ⊂Γ^G_2_ℓ(i_2) in G_2 and 
m independent ℓ-paths from a given vertex i_1 to the corresponding seed set π_0(L) ⊂Γ^G_1_ℓ(i_1) in
G_1. Below we give the specific procedure to reduce this task to a maximum flow problem in a directed graph with source i_1 and sink i_2. 


First, we explore the local neighborhood N^G_1_ℓ(i_1) of i_1 in G_1 up to radius ℓ. We delete all the edges (u,v) found if (u,v) are at the same distance from i_1. Also, we direct all the edges (u,v) from u to v if u is closer to i_1 than v by distance 1. Afterwards, we get a local neighborhood of i_1, denoted by Ñ_ℓ^G_1(i_1), with edges pointing away from i_1. Note that Ñ_ℓ^G_1(i_1) is not exactly a tree because a vertex  may have multiple parents. 

Next, we repeat the above procedure for vertex i_2 in G_2 in exactly the same manner except that the edges are directed towards i_2. Let Ñ_ℓ^G_2(i_2) denote the resulting local neighborhood of i_2. 

Finally, we take the graph union of Ñ_ℓ^G_1(i_1) and 
Ñ_ℓ^G_2(i_2), by treating seeded vertex u ∈Γ_ℓ^G_2(i_2)
with its correspondence π_0(u) ∈Γ_ℓ^G_1(i_1) as the same vertex. 
All the other vertices, seeded or non-seeded, 
from the two different local neighborhoods are treated 
as distinct vertices. We denote the resulting graph union as N_ℓ (i_1, i_2). 

Recall that we aim to find independent (vertex-disjoint except for i_1) ℓ-paths from i_1 to seeded vertices in 
Γ_ℓ^G_1(i_1). Thus, we need to enforce the constraint that every vertex other than i_1 can appear at most once. Similarly for i_2. To this end, we apply the following procedure. 


  * Split each vertex u in N_ℓ(i_1,i_2) into to two vertices: uin and uout;

  * Add an edge of capacity 1 from uin to uout;

  * Replace each other edge (u,v) in N_ℓ(i_1,i_2) 
 with an edge  from uout to vin of capacity 1;

  * Find a max-flow from i_1out to i_2in. 


The idea behind this construction is as follows. Any flow path from the source vertex i_1out to the sink vertex i_2in must have capacity 1, since all edges have capacity 1. Since all capacities are integral, there exists an integral max-flow in which all flows are integers <cit.>.
No two flow paths can pass through the same intermediary vertex, because in passing through a vertex u in the graph the flow path must cross the edge from uin to uout, and the capacity here has been restricted to one.
Also, the flow path must pass exactly 2ℓ distinct uout vertices (including the source vertex i_1out, because all the edges are pointing away from i_1out and towards i_2in.
Thus each flow path from i_1out to i_2in represents a vertex-disjoint 2ℓ-path from the source vertex i_1 to sink vertex i_2 in N_ℓ (i_1, i_2).  As a consequence, the max-flow from i_1out to i_2in corresponds to the maximum number, m, of independent ℓ-paths from i_2 to a set of seeded vertices L ⊂Γ^G_2_ℓ(i_2) in G_2, and 
of independent ℓ-paths from i_1 to the corresponding seed set π_0(L) ⊂Γ^G_1_ℓ(i_1) in
G_1. 

As for time complexity, we can find a  max-flow from i_1out to i_2in via Ford–Fulkerson algorithm <cit.> in O( |E| f) time steps, where |E| is the total number of edges of N_ℓ (i_1, i_2) after vertex splitting and edge replacement,
and f is the max flow. Under the choice of ℓ given in eq:def_ell_1, the total number of vertices and
edges in N_ℓ(i_1,i_2) are O(n^1/2-ϵ). Hence, |E| = O(n^1/2-ϵ). Moreover, the max flow f is upper bounded by the number of seeded vertices in  Γ_ℓ^G_1(i_1) which is at most O(n^1/2-ϵα) with high probability.  Hence, in total it takes O(n α) time steps to compute the
max-flow from i_1out to i_2in via Ford–Fulkerson algorithm.




























































§ TAIL BOUNDS FOR BINOMIAL DISTRIBUTIONS


Let X ∼(n,p). It holds that

    X ≤ n t   ≤exp( - n ( √(p) - √(t))^2),   ∀ 0 ≤ t ≤ p 
    
    X ≥ n t   ≤exp( - 2n  ( √(t) - √(p))^2),   ∀ p ≤ t ≤ 1.
    
    X ≥ n t   ≤ 2^- nt,   ∀ 6p ≤ t ≥ 1.








§ ACKNOWLEDGMENT

 J. Xu would also like to thank Cris Moore, Jian Ding, Zongming Ma, and Yihong Wu 
for inspiring discussions
on graph matching and isomorphism. J. Xu was supported by the NSF Grant CCF-1755960.

alpha





