# The Power of $D$-hops in Matching Power-Law Graphs

Liren Yu, Jiaming Xu, and Xiaojun Lin  L. Yu and X. Lin are with School of
Electrical and Computer Engineering, Purdue University, West Lafayette, USA,
<EMAIL_ADDRESS><EMAIL_ADDRESS>J. Xu is with The Fuqua School of
Business, Duke University, Durham, USA<EMAIL_ADDRESS>L. Yu and J. Xu are
supported by the NSF Grant IIS-1932630.

###### Abstract

This paper studies seeded graph matching for power-law graphs. Assume that two
edge-correlated graphs are independently edge-sampled from a common parent
graph with a power-law degree distribution. A set of correctly matched vertex-
pairs is chosen at random and revealed as initial seeds. Our goal is to use
the seeds to recover the remaining latent vertex correspondence between the
two graphs. Departing from the existing approaches that focus on the use of
high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm
that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods.
Specifically, we first match a set of vertex-pairs with appropriate degrees
(which we refer to as the first slice) based on the number of low-degree seeds
in their $D$-hop neighborhoods. This significantly reduces the number of
initial seeds needed to trigger a cascading process to match the rest of
graphs. Under the Chung-Lu random graph model with $n$ vertices, max degree
$\Theta(\sqrt{n})$, and the power-law exponent $2<\beta<3$, we show that as
soon as $D>\frac{4-\beta}{3-\beta}$, by optimally choosing the first slice,
with high probability our algorithm can correctly match a constant fraction of
the true pairs without any error, provided with only $\Omega((\log
n)^{4-\beta})$ initial seeds. Our result achieves an exponential reduction in
the seed size requirement, as the best previously known result requires
$n^{1/2+\epsilon}$ seeds (for any small constant $\epsilon>0$). Performance
evaluation with synthetic and real data further corroborates the improved
performance of our algorithm.

##  1 Introduction

Given two edge-correlated graphs, graph matching aims to find a bijective
mapping between their vertex sets so that their edge sets are maximally
aligned. It is a fundamental problem with numerous applications in a variety
of fields, including social network de-anonymization [NS09], machine learning
[CSS07, FSV+13], computer vision [CFSV04, SS05], pattern recognition [BBM05,
CK04], computational biology [SXB08, KHGM16] and natural language processing
[HNM05].

This paper focuses on seeded graph matching, wherein an initial set of seeds,
i.e., 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 is available and has been successfully utilized to match
many real-world networks111For example, in social network de-anonymization,
some users provide identifiable information in their service registrations or
explicitly link their accounts across different social networks. [NS08, NS09].
Using seeds, we can then measure the similarity of a vertex-pair by its
“witnesses”. More precisely, let $G_{1}$ and $G_{2}$ denote two graphs. For
each pair of vertices $(u,v)$ with $u$ in $G_{1}$ and $v$ in $G_{2}$, a seed
$(w,w^{\prime})$ is called a _1-hop witness_ for $(u,v)$ if $w$ is a neighbor
of $u$ in $G_{1}$ and $w^{\prime}$ is a neighbor of $v$ in $G_{2}$. Since
$G_{1}$ and $G_{2}$ are graphs with correlated edges, a candidate pair of
vertices are expected to have more witnesses if they are a true pair than if
they are a fake pair. This idea has been applied to many graph matching
problems, and strong performance guarantees (in term of the required number of
seeds) have been obtained, in particular, for matching Erdős-Rényi graphs
[PG11, YG13, LFP13, KL14, KHG15, SGE17, FAP18, MX19, LS18, YXL21].

However, Erdős-Rényi graphs fall short of capturing many fundamental
structural properties of real-world networks. Notably, many real-world
networks exhibit a power-law degree distribution, i.e., the fraction of nodes
with degree at least $k$ decays as $k^{-\beta+1}$ for some exponent $\beta>0.$
As a consequence, we expect to see very large degree fluctuations, with some
nodes having very high degrees (so-called hubs) and some other sparsely-
connected nodes with small degrees. Intuitively, this degree fluctuation may
confuse witness-based vertex matching, e.g., a fake pair with high degrees may
have many more witnesses than a true pair with low degrees, which foils the
existing seeded algorithms designed for matching Erdős-Rényi graphs.

There have been several attempts to design seeded graph matching algorithms
for power-law graphs [KL14, CGL16, BFK18]. However, they tend to require a
larger number of seeds than Erdős-Rényi graphs. Note that to address the
above-mentioned degree variations, a common idea is to first partition graphs
into slices consisting of vertex-pairs with similar degrees. Then, the
vertices are matched slice-by-slice, starting from the highest-degree slice to
lower-degree slices. A cascade process is triggered, in the sense that the
matched vertices in the current slice is used as new seeds to match the next
slice. Intuitively, it is critical to correctly match the first slice in order
to successfully trigger the cascading matching process for the later slices.
[KL14, CGL16, BFK18] all use this idea and match the first slice based on
1-hop witnesses. Unfortunately, they also require a large number of correct
seeds to match the first slice successfully. Specifically, [KL14] assumes
preferential-attachment graphs with $n$ vertices [BA99] and their algorithm
requires $\Omega(n/\log(n))$ seeds to match a constant fraction of all
vertices correctly. [CGL16, BFK18] instead assume the Chung-Lu graph model
[CCG+06] (cf. Section 2). When all seeds are chosen from the high-degree
vertices, [CGL16, BFK18] show that their algorithm require only $n^{\epsilon}$
seeds to correctly match a constant fraction of the vertices. However, if the
seeds are chosen uniformly from all vertices, the number of high-degree seeds
will be much smaller than $n^{\epsilon}$. In that case, the degree-driven
graph matching (DDM) algorithm in [CGL16] requires $n^{1/2+\epsilon}$ seeds to
match a constant fraction of vertices correctly.

In this paper, we propose a new algorithm for matching power-law graphs that
only requires $\Omega((\log n)^{4-\beta})$ initial seeds chosen randomly, to
correctly match a provably constant fraction of all vertices. Our key
departure from [KL14, CGL16, BFK18] is to use “witnesses” in larger $D$-hop
neighborhoods. More precisely, a seed $(w,w^{\prime})$ is a $D$-hop witness
for $(u,v)$ if $w$ is a $D$-hop neighbor of $u$ in $G_{1}$ and $w^{\prime}$ is
a $D$-hop neighbor of $v$ in $G_{2}.$ To see why using $D$-hop witnesses is
crucial, note that, under the Chung-Lu model of [CCG+06] (cf. Section 2), even
the highest degree vertices only have a 1-hop neighborhood of size at most
$O(\sqrt{n})$. Since seeds are uniformly chosen, it is clear that at least
$\Omega(\sqrt{n})$ seeds are needed to ensure that a true pair in the first
slice can have $\Omega(1)$ 1-hop witnesses. In contrast, as $D$ increases, the
size of the $D$-hop neighborhoods grows rapidly, and thus there are
substantially more seeds that can serve as $D$-hop witnesses for true pairs,
which provides hope to significantly reduce the number of initial seeds.

The idea of $D$-hop witnesses has also been used for matching Erdős-Rényi
graphs in [MX19, YXL21]. However, as can be seen in the rest of the paper, the
application of $D$-hop witnesses to power-law graphs is highly non-trivial.
Specifically, due to the power-law degree variations, the $D$-hop
neighborhoods of some high-degree vertices may become so large that even a
fake pair can have many $D$-hop witnesses. Therefore, a key challenge is to
properly control the size of the $D$-hop neighborhoods. This size depends not
only on the degrees of the vertex pair to be matched, but also that of the
intermediate nodes (to reach $D$-hop) and that of the seeds. To overcome this
challenge, our algorithm design (to be explained in Section 3) (i) carefully
chooses the first slice of vertices to be matched. (ii) carefully chooses the
intermediate vertices when constructing the $D$-hop neighborhoods, and (iii)
carefully avoids high-degree seeds in order to eliminate the confusion for
fake pairs. These three ideas altogether ensure that the true pairs in the
first slice have many more $D$-hop witnesses than the fake pairs, and thus can
be correctly matched to trigger the cascading process to match the rest of the
graphs. See Section 3 for more detailed discussions.

To fully realize the power of $D$-hops, we further need to carefully construct
overlapping slices to account for the potential mismatch in the vertex slicing
of graphs $G_{1}$ and $G_{2}$, and to design effective ways to match the
remaining slices. Assembling all these pieces together enables us to achieve
an exponential reduction in the required number of seeds compared to state-of-
art results in [CGL16]. Specifically, under the Chung-Lu model with power-law
exponent $2<\beta<3$ and max degree $\Theta(\sqrt{n})$, we prove the following
performance guarantee of our algorithm, stated informally here and formally in
Section 5.

######  Theorem 1 (Summary of main result).

Suppose $D>\frac{4-\beta}{3-\beta}$. If there are $\Omega((\log n)^{4-\beta})$
initial seeds chosen independently at random, by optimally choosing the first
slice, our algorithm correctly matches $\Omega(n)$ vertex-pairs without any
error with high probability.

This reduces the seed size requirement exponentially, as the best previously
known result [CGL16] requires $n^{1/2+\epsilon}$ seeds. To prove Theorem 1,
there are several key innovations in our analysis in particular to address the
difficult dependency issues across edges and slices. First, note that when we
define the $D$-hop neighborhoods, we use vertex degrees to construct the
slices and to select the seeds and intermediate nodes. This degree-based
slicing unfortunately brings dependency issues. In particular, if we condition
on the vertex degrees, then the edges are no longer independently generated
according to the Chung-Lu model. To circumvent this dependency issue, we first
show that the degree-guided construction and selection can be closely
approximated by the weight-guided counterparts with high probability. Then we
restore the independence by studying the weight-guided construction and
selection, since the edges are independently generated according to the Chung-
Lu model given the weights. Second, as we use the matched pairs in the current
slice as new seeds to match the next slice, the matching results are
correlated across different slices. To deal with these correlations, we
carefully construct sets of matched pairs that only depend on vertex weights
to “sandwich” the original set of matched pairs at each slice, but are not
correlated any more, which allows us to eliminate the slice-dependency issue.
Last but not least, to derive the optimal choice of the first slice and attain
the smallest seed size requirement, we tightly bound the sizes of the common
$D$-hop neighborhoods for both true pairs and fake pairs. Compared to the
Erdős-Rényi graphs, this requires much more sophisticated lines of analysis of
the neighborhood exploration process in the power-law graphs due to the
heterogeneous vertex weights.

In the literature, the idea of $D$-hop witnesses has been used in Erdős-Rényi
graphs [MX19, YXL21]. However, there is a significant difference in our
results for power-law graphs. Specifically, in the Erdős-Rényi graphs with
average degree $d$, the sizes of the $D$-hop neighborhoods are highly
concentrated on $d^{D}$. Moreover, when the average degree $d$ is a constant,
the size of $D$-hop neighborhoods is always $O(1)$ for any constant $D$. Thus,
unless $D$ increases with $n$, at least $\Omega(n)$ seeds are still needed to
ensure that there are enough $D$-hop witnesses for true pairs. In stark
contrast, the power of the $D$-hop becomes much more significant for matching
power-law graphs. In particular, for power-law graphs with constant average
degrees, by properly using the $D$-hop witnesses, we dramatically reduce the
seed requirement to $\Omega((\log n)^{4-\beta})$, as soon as $D$ exceeds
$\frac{4-\beta}{3-\beta}$. Further, we note that the algorithms in [MX19,
YXL21] do not need to worry about controlling the $D$-hop neighborhood, as
they do not face the challenge of power-law degree variations.

Finally, we conduct extensive experiments on both synthetic and real power-law
graphs to corroborate our theoretical analysis. In particular, we compare our
algorithm with five other state-of-the-art seeded graph matching algorithms.
Numerical results demonstrate that our algorithm drastically boosts the
matching accuracy and requires substantially fewer seeds to correctly match a
large fraction of vertices. Further, although our analysis focuses on matching
two graphs of the same number of vertices, our algorithm can be readily
applied to match two graphs of different sizes and return an accurate matching
between vertices in the common subgraph of the two graphs. Indeed, our
experiments on real networks in Section 6.3.2 and Section 6.3.3 show that our
algorithm still achieves outstanding matching performance, even when two
graphs are of very different sizes.

##  2 Model

Following [CGL16, BFK18], we adopt the Chung-Lu random graph model [CCG+06] to
generate the underlying parent graph with a power-law degree distribution.
Here, $[n]$ denotes the set $\\{1,2,...,n\\}$.

######  Definition 1.

Given parameters $\overline{w}>0,$ $\overline{w}\ll
w_{\max}\leq\sqrt{n\overline{w}},$ and $\beta>2$, the Chung-Lu graph is a
random graph $G_{0}([n],E)$ generated as follows. Each vertex $i\in[n]$ is
associated with a positive weight
$w_{i}=\overline{w}\frac{\beta-2}{\beta-1}\left(\frac{n}{i+i_{0}}\right)^{\frac{1}{\beta-1}}$,
where
$i_{0}=n\left(\frac{\overline{w}(\beta-2)}{w_{\max}(\beta-1)}\right)^{\beta-1}$.
For any pair of two vertices $i,j\in[n]$ with $i\neq j$, they are connected
independently by an edge with probability
$p_{ij}=\frac{w_{i}w_{j}}{n\overline{w}}$.

Note that $i_{0}$ is chosen such that $w_{0}=w_{\max}$, which is the largest
weight among all vertices. Further, $\overline{w}$ approximates the average
weight as follows. Since $\overline{w}\ll w_{\max}$, it follows that $i_{0}\ll
n$. It can then be verified that
$\frac{1}{n}\sum_{i=1}^{n}w_{i}\to\overline{w}$ and
$\frac{1}{n}\sum_{i=1}^{n}{\mathbf{1}_{\left\\{{w_{i}\geq w}\right\\}}}\propto
w^{-\beta+1}$ as $n\to\infty.$222To see the first part of the statement, let
$f(x)=w_{x}/n$. Then
$\int_{1}^{n+1}f(x)dx\leq\frac{1}{n}\sum_{i=1}^{n}w_{i}\leq
f(n)+\int_{1}^{n}f(x)dx$. Moreover,
$\int_{1}^{n}f(x)dx=\overline{w}n^{\frac{2-\beta}{\beta-1}}\bigg{(}(n+i_{0}+1)^{\frac{\beta-2}{\beta-1}}-(i_{0}+1)^{\frac{\beta-2}{\beta-1}}\bigg{)}\to
w,$ in view of $i_{0}\ll n$ due to $w_{\max}\gg\overline{w}$. Further, we can
verify the second part of the statement by
$\frac{1}{n}\sum_{i=1}^{n}{\mathbf{1}_{\left\\{{w_{i}\geq
w}\right\\}}}=\left(\frac{(\beta-2)\overline{w}}{(\beta-1)w}\right)^{\beta-1}-\frac{i_{0}}{n}$
$\to\left(\frac{(\beta-2)\overline{w}}{(\beta-1)w}\right)^{\beta-1}.$ Thus,
the degree of vertex $i$ is expected to be close to $w_{i}$, which admits a
power-law distribution with exponent $\beta.$

The Chung-Lu model is convenient for modelling the degree variations in real-
world networks. In these real-world networks, while the average degree is
often a constant, a small but non-negligible fraction of the vertices has very
large degrees (the so-called hubs) [B+16]. To model such sparse power-law
graphs with hubs, we assume $\overline{w}=\Theta(1)$ and $2<\beta<3$.
Empirical studies have shown that the vertex degrees of many real-world
networks indeed follow a power-law distribution with $2<\beta<3$ [B+16, CSN09,
New03]. Note that if $0<\beta\leq 2$, the average degree diverges and the
network cannot be sparse; if $\beta\geq 3$, the degree variance is bounded and
no large hub can appear [B+16].

Next, we obtain a subgraph $G_{1}$ by sampling each edge of $G_{0}$ into
$G_{1}$ independently with probability $s$, which is a constant independent of
$n$. To construct another subgraph $G_{2}$, repeat the same sub-sampling
process independently and relabel the vertices according to an _unknown_
permutation $\pi:[n]\to[n]$. Throughout the paper, we denote a vertex-pair by
$(u,v)$, where $u\in G_{1}$ and $v\in G_{2}$. For each vertex-pair $(u,v)$, if
$v=\pi(u)$, then $(u,v)$ is a true pair; if $v\neq\pi(u)$, then $(u,v)$ is a
fake pair.

Finally, there is an initial seed set ${\mathcal{S}}$ consisting of true
pairs. Each true pair is added into ${\mathcal{S}}$ with probability $\theta$
independently. Our goal is to recover $\pi$ based on the observation of
$G_{1},G_{2}$ and ${\mathcal{S}}$.

##### Notation

We use standard asymptotic notation: for two positive sequences $\\{a_{n}\\}$
and $\\{b_{n}\\}$, we write $a_{n}=O(b_{n})$ or $a_{n}\lesssim b_{n}$, if
$a_{n}\leq Cb_{n}$ for some an absolute constant $C$ and for all $n$;
$a_{n}=\Omega(b_{n})$ or $a_{n}\gtrsim b_{n}$, if $b_{n}=O(a_{n})$;
$a_{n}=\Theta(b_{n})$ or $a_{n}\asymp b_{n}$, if $a_{n}=O(b_{n})$ and
$a_{n}=\Omega(b_{n})$; $a_{n}=o(b_{n})$ or $b_{n}=\omega(a_{n})$, if
$a_{n}/b_{n}\to 0$ as $n\to\infty$.

##  3 Key Algorithmic Ideas

As we discussed in Section 1, previous graph matching algorithms that use
1-hop witnesses to match power-law graphs [KL14, CGL16, BFK18] require at
least $n^{1/2+\epsilon}$ seeds if the seeds are chosen uniformly from all
vertices. In order to significantly reduce the number of seeds, it is then
crucial to use $D$-hop witnesses. However, for power-law graphs, the use of
$D$-hop witnesses is highly non-trivial because, as the size of the $D$-hop
neighborhood increases, fake pairs may also have many $D$-hop witnesses and
thus could be confused as true pairs. Therefore, it is important to carefully
control the $D$-hop neighborhood. In this section, we elaborate on our three
design choices to properly control the $D$-hop neighborhood sizes: the weight
of the seeds, the weight of the candidate vertex-pairs, and the weight of the
intermediate vertices.

First, it is important to utilize low-weight seeds while avoiding high-weight
seeds. Due to the power-law degree distribution, when seeds are uniformly
chosen, there are many more low-weight seeds than high-weight seeds. Thus, the
$D$-hop neighborhoods need to be large enough to reach sufficiently many low-
weight seeds. However, for fake pairs, their large $D$-hop neighborhoods may
also overlap. This implies that high-weight seeds may easily become witnesses
for fake pairs, which can appear in many $D$-hop neighborhoods. Therefore, in
order to avoid having too many witnesses for fake pairs, it is important to
eliminate the high-weight seeds.

Second, for a given $D$, we need to carefully choose the first slice of
candidate vertex-pairs to be matched using the $D$-hop witnesses. Recall that
[KL14, CGL16, BFK18] also use this idea of slicing the vertices according to
their degrees, and focus on matching the first slice with vertices of high
degree. However, we find that the degree range of this first slice needs to be
carefully chosen. On the one hand, if the weight of the candidate vertex-pairs
is too small, the common $D$-hop neighborhoods of a true pair are too small to
produce enough witnesses. On the other hand, if the weight of the candidate
vertex-pairs is too large, the $D$-hop neighborhoods of a fake pair would
intersect a lot, leading to too many $D$-hop witnesses.

Third, the high-weight vertices are not suitable to be the intermediate
vertices in $D$-hop neighborhoods when $D$ is large. This is because, when $D$
is large, there exist some high-weight vertices with very large $d$-hop
($d<D$) neighborhoods. If these high-weight vertices become $(D-d)$-hop
neighbors of the candidate vertices, the $D$-hop neighborhoods of the fake
pairs would become too large. Thus, we should avoid using the high-weight
vertices as the intermediate vertices.

Prompted by the above three ideas, we partition the graph into “perfect”
slices

$\displaystyle{P}_{k}=\\{u:w_{u}\in[\alpha_{k},\alpha_{k-1}]\\}\quad\text{
where }\alpha_{k}=n^{\gamma}/2^{k}\text{ for }k\geq 0,\text{ and
}\alpha_{-1}=\infty,$ (1)

for some $\gamma\in(0,\log_{n}w_{\max}]$. In particular, the first slice
$P_{1}$ is the set of vertices with weight in $[n^{\gamma}/2,n^{\gamma}]$,
which is the first set of the vertices that we wish to match. We will show in
(8) that for a vertex in the first slice $P_{1}$, its number of
$\Theta(1)$-weight $D$-hop neighbors is on the order of
$n^{\gamma((3-\beta)(D-1)+1}$. Hence, we optimally choose $\gamma$ close to
$\frac{1}{(3-\beta)(D-1)+1}$ so that its number of $\Theta(1)$-weight $D$-hop
neighbors is close to $\Theta(n).$ Under this optimal choice, we prove that
sufficiently many vertex-pairs in the first slice are correctly matched so
that they can be used as new seeds to trigger the cascading process to match
the rest of the graphs slice-by-slice. In fact, for slice $k\geq 2$ until
$k=k^{*}$ for some $k^{*}$, since the earlier slices provide so many new
seeds, it turns out that using $1$-hop witnesses suffices. When $k>k^{*}$, the
slice-by-slice matching process stops, as there are not enough $1$-hop
witnesses to correctly match the slices with low-weight vertices. Fortunately,
for the fake pairs with such low-weights, there are very few $1$-hop witnesses
as well. Thus we treat all the low-weight vertices as a single slice and apply
the PGM algorithm in [KHG15] to match them. Finally, we use all the matched
vertex-pairs as new seeds to match the zero slice $P_{0}$ with very high
weights.

For the above ideas to work, however, it is important that the earlier slices
do not produce wrong matches; otherwise, the wrong matches will propagate
errors to the subsequent slices. As such, we only match pairs with the number
of witnesses larger than a threshold, as we will see next in the detailed
algorithm.

##  4 The Power-Law $D$-hop (PLD) Algorithm

In this section, we present our Power-Law D-hop (PLD) algorithm, shown in
Algorithm 1 and provide the intuition why it works.

###  4.1 Algorithm description

We first introduce some notations regarding $D$-hop neighborhoods. Given any
graph $G$ and two vertices $u,v$ in $G$, we denote the length of the shortest
path from $u$ to $v$ in $G$ by $\text{dist}_{G}(u,v)$. For each vertex $u\in
G$, the $d$-hop neighbors of $u$ is denoted by $\Gamma_{d}^{G}(u)=\left\\{v\in
G:\text{dist}_{G}(u,v)=d\right\\}$. The neighbors within $d$-hop of $u$ is
denoted by $N_{d}^{G}(u)=\bigcup_{j=1}^{d}\Gamma_{j}^{G}(u)$.

Our PLD algorithm carefully incorporates the key algorithmic ideas described
in Section 3. At a high-level, we first slice the vertices according to their
degrees. We then apply the $D$-hop algorithm to the first slice (which is
carefully chosen). Afterwards, we apply the $1$-hop algorithm to the lower-
degree slices $2$ to $k^{*}$, until the vertex degrees are about poly-
logarithmic in $n$, in which case we apply the PGM algorithm to the last slice
with the lowest-degree vertices. Finally, we return to slice 0 of vertices
with very high degrees.

The full algorithm is presented in Algorithm 1. We now describe the details.

Algorithm 1 The Power-Law D-hop (PLD) Algorithm.

1: Input: Graphs $G_{1}$ and $G_{2},$ initial seed set ${\mathcal{S}}$,
parameters $D,\gamma,\tau_{1},\tau_{2},k^{*}$

2: Construct a subset of low-degree seeds
$\widehat{{\mathcal{S}}}=\left\\{(u,v)\in{\mathcal{S}}:\left|\Gamma_{1}^{G_{1}}(u)\right|,\left|\Gamma_{1}^{G_{2}}(v)\right|\leq
5\log n\right\\}$.

3: Let $\widehat{G}_{i}$ denote the subgraph of $G_{i}$ induced by the vertex
set
$V_{i}=\left\\{u:\left|\Gamma_{1}^{G_{i}}(u)\right|\leq(1+\delta)n^{\gamma}s\right\\}$
for $i=1,2.$

4: Partition the graph $G_{i}$ into slices $\widehat{P}_{k}^{G_{i}}$ for
$i=1,2$ and $0\leq k\leq k^{*}$, according to (2).

5: In $\widehat{G}_{1}$ and $\widehat{G}_{2}$, for candidate vertex-pairs in
$\widehat{Q}_{1}$, count their $D$-hop witnesses in $\widehat{{\mathcal{S}}}$
and use GMWM to match pairs with more than $\tau_{1}$ $D$-hop witnesses
($\tau_{1}$ is given in (3)). The set of matched pairs is ${\mathcal{R}}_{1}$.

6: for $k=2$ to $k^{*}$ do

7: For candidate vertex-pairs in $\widehat{Q}_{k}$, count their $1$-hop
witnesses in ${\mathcal{R}}_{k-1}$ and use GMWM to match pairs with more than
$\tau_{2}(k)$ $1$-hop witnesses ($\tau_{2}(k)$ is given in (5)). The set of
matched pairs is ${\mathcal{R}}_{k}$.

8: end for

9: Let $G^{\prime}_{i}$ denote the subgraph of $G_{i}$ induced by the vertex
set
$V^{\prime}_{i}=\left\\{u:\left|\Gamma_{1}^{G_{i}}(u)\right|\leq(1+\delta)\alpha_{k^{*}-1}s\right\\}$,
for $i=1,2.$

10: Apply PGM to $G^{\prime}_{1}$ and $G_{2}^{\prime}$, with the seed set
${\mathcal{R}}_{k^{*}}$ and the threshold $r=3$. The set of matched pairs is
denoted by ${\mathcal{R}}_{k^{*}+1}$.

11: For candidate vertex-pairs in $\widehat{Q}_{0}$, count their $1$-hop
witnesses in
$\widehat{{\mathcal{R}}}\triangleq\bigcup_{k=1}^{k^{*}+1}{\mathcal{R}}_{k}$
and match pairs with GMWM. The set of matched pairs is ${\mathcal{R}}_{0}$.

12: Output: All matched pairs
${\mathcal{R}}=\widehat{{\mathcal{R}}}\cup{\mathcal{R}}_{0}\cup{\mathcal{S}}$

In line 2, we construct a subset of low-weight seeds to use a future
witnesses. Recall from Section 3 that we aim to utilize low-weight seeds while
avoiding high-weight seeds. Specifically, in our algorithm we wish to use
seeds with $\Theta(1)$ weights. However, since we do not have access to the
vertex weights directly, we have to estimate vertex weights by vertex degrees.
Therefore, we construct a seed subset $\widehat{{\mathcal{S}}}$ that contains
seeds with degrees no larger than $5\log n$ to ensure that all seeds with
$\Theta(1)$ weights are included.

In line 3, we eliminate the vertices with degrees larger than
$(1+\delta)n^{\gamma}$ and their adjacent edges, because we do not want to use
the high-weight vertices as the intermediate vertices.

In line 4, we partition the graphs $G_{1}$ and $G_{2}$ into slices. Recall
that the “perfect” slices $P_{k}$ in (1) described in Section 3 are defined
with the vertex weights. Again, since we can not observe the vertex weight
directly, we need to use the vertex degree as an estimate of the vertex
weight. However, using vertex degree to slice vertices creates new technical
difficulties. Specifically, for two vertices corresponding to a true pair,
their actual degrees in $G_{1}$ and $G_{2}$ may differ because the edges are
sub-sampled from the parent graph randomly. As a result, it is possible that
these two vertices are assigned to two slices of different indices in $G_{1}$
and $G_{2}.$ This becomes problematic because, if we only match slices with
the same index, such a true pair would never be matched. (This problem does
not occur for the “perfect” slices since they are based on the weight of the
vertex in the original parent graph.) Fortunately, the actual degrees of the
vertices corresponding to a true pair should not differ too much (assuming a
common sub-sampling probability $s$ for both graphs). Thus, to address the
above difficulty, we enlarge the slices a little bit, so that with high
probability the two vertices corresponding to a true pair can fall into slices
with the same index, and therefore have the opportunity to be matched. More
precisely, for $k\geq 0$, we define the imperfect slice as

$\displaystyle\widehat{P}_{k}^{G}=\left\\{u:(1-\delta)\alpha_{k}s\leq\left|\Gamma_{1}^{G}(u)\right|\leq(1+\delta)\alpha_{k-1}s\right\\},\text{
for }k\geq 0,$ (2)

where $\delta=\frac{1}{8}$ throughout this paper. Here, $\alpha_{k}$ are the
same as (1), and the parameters $\gamma$ and $D$ will be set to satisfy (10)
in Theorem 2. The imperfect slice-pair is then defined as
$\widehat{Q}_{k}=\widehat{P}_{k}^{G_{1}}\times\widehat{P}_{k}^{G_{2}}=\\{(u,v):u\in\widehat{P}_{k}^{G_{1}},v\in\widehat{P}_{k}^{G_{2}}\\}$.
However, these enlarged imperfect slices also create a new problem of matching
fake pairs, which will be discussed next.

In line 5, we count the $D$-hop witnesses for all vertex-pairs in the first
slices $\widehat{P}_{1}^{G_{1}}$ and $\widehat{P}_{1}^{G_{2}}$, and then use
Greedy Maximum Weight Matching (GMWM) [Avi83] to find the vertex
correspondence such that the total number of witnesses is large. Here, we note
that our earlier idea of enlarging the imperfect slices $\widehat{P}_{k}$
creates a new problem. That is, the imperfect slices with neighboring indices
now have some overlap. As a result, it is possible that a slice pair contains
a fake pair $(u,\pi(v))$, but does not contain the true pairs $(u,\pi(u))$ and
$(v,\pi(v))$333This phenomenon does not contradict the idea of enlarging the
slices. Enlarging the slices only guarantees the true pairs $(u,\pi(u))$ and
$(v,\pi(v))$ are assigned into some slice-pairs. However, for other slice-
pairs that contain the fake pair $(u,\pi(v))$, it is still possible that the
two true pairs are not included.. When that happens, the fake pairs
$(u,\pi(v))$ may have the most witnesses among all the candidate vertex-pairs
containing either $u$ or $\pi(v)$. Thus, the fake pair $(u,\pi(v))$ may be
matched by GMWM. Fortunately, the number of witnesses of these fake pairs is
still expected to be smaller than that of any true pair. Therefore, to resolve
this difficulty and to ensure that only the true pairs are matched, for the
first slice we match only the vertex-pairs with no less than $\tau_{1}$
$D$-hop witnesses, where $\tau_{1}$ is set to be a constant fraction of the
expected number of the $D$-hop witnesses for true pairs, i.e.,

$\displaystyle\tau_{1}=\frac{3}{10}\left(\frac{Cs^{2}}{12\overline{w}}\right)^{D}n^{\gamma((3-\beta)(D-1)+1)}\theta,$
(3)

where
$C\triangleq(2^{\beta-1}-1)\left(\frac{(\beta-2)\overline{w}}{(\beta-1)}\right)^{\beta-1}$.
Similar thresholds are also used in the following steps when we match other
slices.

In line 6-8, we use the matched pairs from the previous slice as new seeds,
and use the 1-hop algorithm to match the vertices in slices $k=2,...,k^{*}$,
where

$\displaystyle
k^{*}=\left\lfloor\log_{2}\left(n^{\gamma}\left(\frac{Cs^{2}}{192\overline{w}\log
n}\right)^{\frac{1}{3-\beta}}\right)\right\rfloor.$ (4)

In other words, we match the vertices with degrees larger than
$(1-\delta)\alpha_{k^{*}}$, where
$\alpha_{k^{*}}\geq\left(\frac{192\overline{w}\log
n}{Cs^{2}}\right)^{\frac{1}{3-\beta}}$. Again to ensure that only the true
pairs are matched for each slice, we only match the vertex-pairs with at least
$\tau_{2}(k)$ $1$-hop witnesses, where $\tau_{2}(k)$ is set to be half of the
expected number of the 1-hop witnesses of the true pairs, i.e.,

$\displaystyle\tau_{2}(k)=\frac{C\alpha_{k-1}^{3-\beta}s^{2}}{16\overline{w}}.$
(5)

In line 9-10, we apply the PGM algorithm [YG13, Section 3] to match the
remaining vertices with degrees no larger than $(1+\delta)\alpha_{k^{*}}$.
Note that when the vertex weight is this small, estimating the vertex weight
based on its degree is not accurate anymore. Thus, it is difficult to use the
vertex degree to distinguish which slices should these vertices fall into.
Instead, we treat all of these low-weight vertices as one slice. Further, for
such low-degree vertices, using 1-hop algorithm based on the seeds from
earlier slices will lead to poor performance, because even the true pairs in
this slice have too few 1-hop witnesses. Fortunately, there are even fewer
witnesses for the fake pairs with such low degrees. Thus, we can use the PGM
algorithm, which iteratively generates new seeds as new correct matches are
found. In this way, PGM can match a constant fraction of the rest of vertex-
pairs, while avoiding matching fake pairs.

Finally, in line 11, the algorithm uses all vertex-pairs matched above as new
seeds and matches the vertices in $\widehat{Q}_{0}$ via the 1-hop algorithm.

The total complexity of our algorithm is $O(n^{3-2\gamma(\beta-1)})$. The
proof can be found in Appendix A.

###  4.2 Intuition

Before we present the main results, we explain the intuition why the above
algorithm will work only with $\Omega((\log n)^{4-\beta})$ seeds. For the
purpose of explaining this intuition, we ignore the inaccuracy of estimating
the weights by the vertex degrees and assume that the graphs can be
partitioned into perfect slices $P_{k}$. We further assume that the true
mapping $\pi$ is the identity permutation. Also, when we write $\approx$, we
ignore the constant factors that are non-essential.

The key to the success of Algorithm 1 is appropriately choosing the first
slice to apply the $D$-hop algorithm. We first calculate the probability that
a vertex of $\Theta(1)$ weight lies in the $D$-hop neighborhood of a vertex in
the first slice. Specifically, given a vertex $u$ in the first slice ${P}_{1}$
and another vertex $v$ of weight $1$, we want to compute the probability
$q_{D}$ that $v$ is a $D$-hop neighbor of $u$, i.e.,
$q_{D}\triangleq\mathbb{P}\left\\{v\in\Gamma_{D}^{\widehat{G}_{j}}(u)\right\\}$,
where $j$ is either 1 or 2. Note that if $v$ is a $D$-hop neighbor of $u$,
then $v$ is connected to some $(D-1)$-hop neighbors $i$ of $u$. Therefore,
$q_{D}$ satisfies the following recursion:

$\displaystyle q_{D}\approx$
$\displaystyle\sum_{i\in\widehat{G}_{j}}\mathbb{P}\left\\{v\in\Gamma_{1}^{\widehat{G}_{j}}(i)\right\\}\times\mathbb{P}\left\\{i\in\Gamma_{D-1}^{\widehat{G}_{j}}(u)\right\\}$
$\displaystyle\overset{(a)}{\approx}$ $\displaystyle
c\int_{0}^{n^{\gamma}}nw^{-\beta}\cdot\frac{w}{n\overline{w}}\cdot wq_{D-1}dw$
$\displaystyle=$ $\displaystyle
c\frac{q_{D-1}}{\overline{w}}\int_{0}^{n^{\gamma}}w^{2-\beta}dw=\frac{cn^{\gamma(3-\beta)}}{\overline{w}(3-\beta)}q_{D-1}.$
(6)

In step $(a)$, we integrate over the degree $w$ of the $(D-1)$-hop neighbor
$i$. Thus, $\mathbb{P}\left\\{i\in\Gamma_{D-1}^{\widehat{G}_{j}}(u)\right\\}$
is $wP_{D-1}$ by our definition. Further, $w/n\bar{w}$ is the probability that
$v$ (with degree 1) is connected to $i$, and number of such vertices $i$ with
degree in $[w,w+dw]$ is about $\sum_{i=1}^{n}{\mathbf{1}_{\left\\{{w\leq
w_{i}\leq w+dw}\right\\}}}\to cnw^{-\beta}dw$ with
$c=\left(\frac{(\beta-2)\overline{w}}{(\beta-1}\right)^{\beta-1}(\beta-1).$ By
the Chung-Lu model, $q_{1}\approx\frac{n^{\gamma}}{n\overline{w}}$. Iterating
(4.2) over $D$, it follows that

$\displaystyle
q_{D}\approx\left(c\frac{n^{\gamma(3-\beta)}}{\overline{w}(3-\beta)}\right)^{D-1}q_{1}\;\approx\frac{c^{D-1}n^{\gamma\left((3-\beta)(D-1)+1\right)}}{n\overline{w}^{D}(3-\beta)^{D-1}}.$
(7)

As explained in Section 3, for the success of the $D$-hop algorithm, there are
two key considerations. On the one hand, we need to ensure that the fake pairs
in $Q_{1}\triangleq P_{1}\times P_{1}$ have very few $D$-hop witnesses. As
such, we want to prevent the fake pairs in $Q_{1}$ from having too many common
neighbors of small weight. Therefore, we require $q_{D}\ll 1$ which roughly
corresponds to $n^{\gamma((3-\beta)(D-1)+1)}\ll n$ and is close to the
condition (10) (stated later in Theorem 2). On the other hand, we need to
ensure that the true pairs in $Q_{1}$ have sufficiently many
$\Theta(1)$-weight $D$-hop witnesses. Indeed, for $u\in P_{1}$, its number of
common $D$-hop neighbors of $\Theta(1)$-weight is at least

$\displaystyle\left|\\{v:w_{v}=\Theta(1)\\}\cap\Gamma_{D}^{\widehat{G}_{1}\land\widehat{G}_{2}}(u)\right|\approx
nq_{D}\approx n^{\gamma((3-\beta)(D-1)+1)},$ (8)

where the first approximation holds because there are about $\Theta(n)$
vertices with $\Theta(1)$ weight based on the power-law weight distribution.
Therefore, under condition (11) stated in Theorem 2, which is roughly
$\theta=\Omega\left(\frac{\log n}{n^{\gamma((3-\beta)(D-1)+1)}}\right)$, all
the true pairs have at least $\Omega(\log n)$ low-degree $D$-hop witnesses.
The above choices thus ensure that all true pairs (but no fake pairs) are
matched.

Interestingly, after matching the first slice, it triggers a cascading
process, where the new matches at one slice can be used as new seeds to match
the subsequent slice by the 1-hop algorithm. To see why using 1-hop witnesses
is sufficient, recall that the weight of vertices in $P_{k}$ satisfies

$\displaystyle\alpha_{k}\leq
w_{i}\leq\alpha_{k-1}\Longleftrightarrow\frac{n}{\left(\frac{(\beta-1)\alpha_{k-1}}{(\beta-2)\overline{w}}\right)^{\beta-1}}-i_{0}\leq
i\leq\frac{n}{\left(\frac{(\beta-1)\alpha_{k}}{(\beta-2)\overline{w}}\right)^{\beta-1}}-i_{0}.$

According to the index range of these vertices, we get that the number of
vertices in $P_{k}$ is $\Theta\left(n\alpha_{k-1}^{1-\beta}\right)$. Since the
vertices in $P_{k}$ and the vertices in $P_{k+1}$ are connected independently
with probability at least $\frac{\alpha_{k}\alpha_{k+1}}{n\overline{w}}$, it
follows that, for a vertex in $P_{k+1}$, its number of 1-hop neighbors in
$P_{k}$ is about

$\displaystyle
n\alpha_{k-1}^{1-\beta}\times\frac{\alpha_{k}\alpha_{k+1}}{n\overline{w}}=\frac{\alpha_{k-1}^{1-\beta}\alpha_{k}\alpha_{k+1}}{\overline{w}}\geq\frac{\alpha_{k}^{3-\beta}}{8\overline{w}}.$
(9)

Note that for the 1-hop algorithm to succeed, the true pairs need to have more
than $\log n$ 1-hop witnesses [MX19]. Since $2<\beta<3$, we have
$\frac{\alpha_{k}^{3-\beta}}{8\overline{w}}>\log n$, as long as
$\alpha_{k}>\alpha_{k^{*}}\approx(\log n)^{\frac{1}{3-\beta}}$. Therefore,
assuming that the true pairs in $Q_{k}\triangleq P_{k}\times P_{k}$ are
correctly matched, we expect that the 1-hop algorithm can correctly match the
true pairs in $Q_{k+1}$ as long as $k<k^{*}.$

However, when $k\geq k^{*}$, for a vertex in $P_{k+1}$, its number of 1-hop
neighbors in $P_{k}$ becomes smaller than $\log n$, and thus the 1-hop
algorithm can no longer match the vertices in $P_{k+1}$ correctly. Even worse,
the vertex degrees become inaccurate to distinguish the vertices with at most
poly-logarithmic weights, and hence the 1-hop algorithm can not even match the
vertices slice by slice. As discussed in Section 3, we instead resort to the
PGM algorithm to match a constant fraction of the rest of low-weight vertices.
Note that the key to the success of the PGM is that the number of witnesses
for a fake pair is no more than $2$ [KHG15]. To see why this condition holds
for the remaining low-weight vertices, note that the probability that a low-
weight seed (with weight no larger than $\alpha_{k^{*}}$) becomes a 1-hop
witnesses for a fake pair with weight no larger than $\alpha_{k^{*}}$ is at
most
$\left(\frac{\alpha_{k^{*}}\alpha_{k^{*}}}{n\overline{w}}\right)^{2}=\frac{\alpha_{k^{*}}^{4}}{n^{2}\overline{w}^{2}}$.
Since there are at most $n$ seeds and the majority of them are low-weight, the
number of witnesses for any fake pair with low-weights is about
$\frac{\alpha_{k^{*}}^{4}}{n\overline{w}^{2}}\lesssim\frac{(\log
n)^{\frac{4}{3-\beta}}}{n\overline{w}^{2}}\ll 1$. Thus, we can use the PGM
algorithm with threshold $r=3$ to match a constant fraction of the low-weight
vertex-pairs without errors.

Finally, the number of vertices with weight less than $\alpha_{0}$ is
$\Theta(n)$. If most true pairs with weight less than $\alpha_{0}$ are
matched, we can use them as new seeds to exactly match the remaining vertex-
pairs in $Q_{0}$.

##  5 Main Results

The following theorem provides a sufficient condition for our algorithm to
correctly match a constant fraction of nodes without any errors. We define
$C\triangleq(2^{\beta-1}-1)\left(\frac{(\beta-2)\overline{w}}{(\beta-1)}\right)^{\beta-1}$
and
$\kappa\triangleq\frac{(1+2\delta)^{2}2^{5-\beta}C}{(2^{3-\beta}-1)\overline{w}}$
throughout this paper.

######  Theorem 2.

Suppose $\gamma>0$ and the positive integer $D$ are chosen such that
$\gamma\leq\log_{n}w_{\max}$, $n^{2\gamma}=o(n)$, and

$\displaystyle
n^{\gamma((3-\beta)(D-1)+1)}\leq\frac{Cs(2^{3-\beta}-1)}{20\cdot
2^{3-\beta}}\left(\frac{Cs^{2}}{12\kappa^{2}\cdot\overline{w}}\right)^{D}\frac{n}{(\log
n)^{3-\beta}}\,.$ (10)

If the fraction $\theta$ of seeds satisfies

$\displaystyle\theta\geq\frac{320\log
n}{\left(\frac{Cs^{2}}{12\cdot\overline{w}}\right)^{D}n^{\gamma((3-\beta)(D-1)+1)}},$
(11)

then for all sufficiently large $n$, Algorithm 1 with $\tau_{1}$ in (3) and
$\tau_{2}(k)$ in (5) outputs $\Theta(n)$ true pairs and zero fake pairs with
probability at least $1-n^{-1+o(1)}$.

Recall from (8) that $n^{\gamma((3-\beta)(D-1)+1)}$ is roughly the size of the
$D$-hop neighborhood of a vertex (with weight around $n^{\gamma}$) in the
first slice $P_{1}$. Therefore, on the one hand, (10) ensures that for two
distinct vertices $(u,v)$ in the first slice, the intersection of their
$D$-hop neighborhoods is much smaller than the two neighborhoods, so that the
fake pairs have much fewer $D$-hop witnesses than the true pairs. On the other
hand, (11) ensures that the true pairs have at least $\Omega(\log n)$ $D$-hop
witnesses.

Assuming $w_{\max}=\Theta(\sqrt{n})$, if we set $D=1$ and
$\gamma=\frac{1}{2}-\epsilon$ for a small constant $\epsilon>0$, then Theorem
2 recovers the seed requirement $n^{1/2+\epsilon}$ for the $1$-hop algorithm
which is comparable to the result in [CGL16]. Surprisingly, for larger $D$, if
we optimally choose $n^{\gamma}$ in (13), then the seed requirement can be
dramatically reduced to $\Omega((\log n)^{4-\beta})$, as shown by the
following corollary.

######  Corollary 1 (The formal version of Theorem 1).

Suppose

$\displaystyle D\geq\frac{1}{3-\beta}\left(\frac{\log
n}{\log(w_{\max})}-1\right)+1\quad\text{ and }\quad
D>\frac{4-\beta}{3-\beta}.$ (12)

Choose

$\displaystyle n^{\gamma((3-\beta)(D-1)+1)}=\frac{cn}{(\log n)^{3-\beta}},$
(13)

for a sufficiently small constant $c$ so that (10) is satisfied, and
$\tau_{1},\tau_{2}(k)$ according to (3) and (5), respectively. If the fraction
of seeds satisfies

$\theta\geq\frac{C_{0}\left(\log n\right)^{4-\beta}}{n}$

for a sufficiently large constant $C_{0}$, then for all sufficiently large
$n$, Algorithm 1 outputs $\Omega(n)$ true pairs and zero fake pairs, with
probability at least $1-n^{-1}$.

According to (13), we choose $\gamma$ asymptotically equal to
$\frac{1}{\left[(3-\beta)(D-1)+1\right]}$. Condition (12) is imposed to ensure
that this choice satisfies $\gamma<1/2$ and $\gamma\leq\log_{n}(w_{\max})$ in
Theorem 2. Theorem 1 is a special case of Corollary 1, where
$w_{\max}=\Theta(\sqrt{n})$ so that $(\ref{eq:cond_D})$ reduces to
$D>\frac{4-\beta}{3-\beta}.$

##  6 Numerical experiments

In this section, we conduct numerical experiments to verify our theoretical
findings and the effectiveness of the PLD algorithm. For all experimental
results, we calculate the accuracy rate as the median of the proportion of
vertices that are correctly matched, taken over 10 independent runs.

###  6.1 Choice of $D$ and $\gamma$

In this section, we simulate our PLD algorithm with different $D$ and $\gamma$
to investigate the impact of the two parameters. We generate the underlying
parent graph $G_{0}$ according to the Chung-Lu model with $n=10000$,
$\beta=2.5$ and $\overline{w}=10$. Then, we construct $G_{1}$ and $G_{2}$ by
sampling each edge of $G_{0}$ twice independently with probability $s=0.8$.
The seeds are selected such that each true pair becomes a seed with
probability $\theta$ independently.

In Fig. 1, we first plot the accuracy rates of our PLD algorithm with $D=3$
and different $\gamma$, when $\theta$ varies from $0$ to $0.01$. We observe
that for a given accuracy rate, when $\gamma=1/\left[(3-\beta)(D-1)+1\right]$,
the PLD algorithm requires the smallest number of seeds. This is consistent
with the theoretical prediction in Corollary 1, i.e., the optimal choice of
$\gamma$ approaches $1/\left[(3-\beta)(D-1)+1\right]$ as $n\to\infty$.

Figure 1: The performance of the PLD algorithm with $D=3$ and varying
$\gamma$.

Then, in Fig. 2, we plot the accuracy rates of our PLD algorithm with
different choices of $D$ by fixing $\gamma=1/[(3-\beta)(D-1)+1]$. We can see
that the curves for different $D$ align well with each other, showing that the
PLD algorithm with different $D$ requires a comparable number of seeds to
succeed when $\gamma$ is optimally chosen, as suggested by Corollary 1.

Figure 2: The performance of the PLD algorithm with different $D$ and
$\gamma=\frac{1}{(3-\beta)(D-1)+1}$.

###  6.2 Performance Comparison with Synthetic Data

For our experiments on synthetic data, we still use the graphs generated in
Section 6.1 according to the Chung-Lu model. Then, our PLD algorithm is
simulated and compared with the other five state-of-the-art seeded graph
matching algorithms, namely DDM [CGL16], Y-test [BFK18], User-Matching [KL14],
2-hop [MX19] and PGM [KHG15] algorithms. For the PLD algorithm, we select
$D=2,3,4$ and $\gamma=1/((3-\beta)(D-1)+1)$ as suggested in Corollary 1. In
Fig. 3, we plot the performance comparison when $\theta$ varies from $0$ to
$0.03$. We observe that our PLD algorithm with different $D$ achieves similar
performance, and it significantly outperforms all the other algorithms.
Specifically, our PLD algorithm only requires around 50 seeds to match almost
all vertices, while the User-Matching algorithm requires at least 150 seeds,
and the DDM requires at least 220 seeds. The other algorithms perform even
worse. Note that roughly $5\%$ of vertices have degree at most 1 in both
graphs; thus we do not expect to correctly match them. That is why the
accuracy rates of our PLD algorithm saturated around $95\%$.

Note that the $2$-hop and PGM algorithms have been known to work well for
matching Erdős-Rényi graphs [MX19, KHG15]. However, we see that they are
brittle to the power-law degree variations. The DDM, Y-test, and User-Matching
algorithms perform slightly better. However, since they all rely on the
$1$-hop witnesses, they still require a large number of seeds to succeed.

Figure 3: Performance comparison of our PLD algorithm and five other
algorithms on the Chung-Lu model with different $\theta$.

###  6.3 Performance Comparison with Real Data

####  6.3.1 Estimate Parameters for Real Graphs

We see that the performance of our PLD algorithm is outstanding on synthetic
graphs. To further demonstrate the power of $D$-hops, we investigate its
performance in matching real graphs. However, our algorithm based on the
Chung-Lu model requires several parameters, which are unknown for real graphs.
As such, in this section, we describe our method to estimate the key model
parameters before implementing our algorithm.

First and foremost, we estimate the power-law exponent of real graphs by
fitting them to the Chung-Lu model using the maximum-likelihood estimation
given in [CSN09]:

$\displaystyle\widehat{\beta}=1+N\left[\sum_{d_{i}\geq
d_{\min}}\text{ln}\left(\frac{d_{i}}{d_{\min}-1/2}\right)\right]^{-1},$ (14)

where $d_{i}$ is the degree of vertex $i$, $N$ is the number of vertices with
degree at least $d_{\min}$, and $d_{\min}$ is some lower bound on the vertex
degrees to be specified. It is suggested in [CSN09] to estimate $d_{\min}$
using the Kolmogorov-Smirnov approach, which minimizes the maximum distance
between the empirical CDF and the theoretical CDF of vertex degrees. More
precisely,

$d_{\min}=\mathop{\arg\min}_{d}\max_{d_{i}\geq
d}\left|\widehat{F}_{d}(d_{i})-F_{d}(d_{i})\right|,$

where $\widehat{F}_{d}(x)$ is the CDF of the observed vertex degrees with
values at least $d$, and $F(x)$ is the CDF of the power-law vertex
distribution restricted to $[d,+\infty)$. Numerical experiments in [CSN09]
show $\widehat{\beta}$ is accurate to $1\%$ or better if $d_{\min}$ is set to
be around $6$. Thus, we fix $d_{\min}=6$ throughout our real-data experiments.

Next, we estimate the subsampling probability $s$, which characterizes the
edge correlation between the two observed graphs. Let $G_{j}[S]$ denote the
subgraph of $G_{j}$ induced by vertices in $S=\\{i:(i,i)\in{\mathcal{S}}\\}$,
where ${\mathcal{S}}$ is the initial seed set. Note that under our subsampling
model, given an edge in one graph, it appears in the other graph with
probability $s.$ Thus we estimate the sampling probability $s$ by

$\displaystyle\widehat{s}=\frac{2\left|E[G_{1}[S]\land
G_{2}[S]]\right|}{\left|E[G_{1}[S]]\right|+\left|E[G_{2}[S]]\right|},$ (15)

where $E[G]$ denotes the edge set of graph $G$.

Based on $\widehat{s}$, we can further estimate the average weight
$\overline{w}$. Recall that $\overline{w}$ is close to the average degree
under the Chung-Lu model. Thus, we estimate $\overline{w}$ by
$\frac{\overline{d}(G_{1})+\overline{d}(G_{2})}{2\widehat{s}},$ where
$\overline{d}(G)$ is the average degree in graph $G.$ Finally, for the
fraction of seeds $\theta$, if it is unknown, we can simply estimate it by
$\frac{\left|{\mathcal{S}}\right|}{n}$. Note that since $w_{\max}$ will not be
used by our algorithm, we do not need to estimate it.

Based on the estimated model parameters, we can then determine the input
parameters of our PLD algorithm. Since we optimally choose
$\gamma=1/((3-\beta)(D-1)+1)$, the threshold $\tau_{1}$ in (3) can be
simplified to
$\tau_{1}=\frac{3}{10}\left(\frac{Cs^{2}}{12\overline{w}}\right)^{D}n\theta.$
Further, the threshold $\tau_{2}(k)$ can be set according to (5).

####  6.3.2 Facebook Friendship Networks

We use a Facebook friendship network (provided in [TMP12]) of 63392 students
and staffs from University of Oregon as the parent graph $G_{0}$. There are
1633772 edges in $G_{0}$. The power-law exponent of the Facebook social
network is estimated as 2.09 by (14). To obtain two edge-correlated subgraphs
$G_{1}$ and $G_{2}$ of different sizes, we independently sample each edge of
$G_{0}$ twice with probability $s=0.9$ and sample each vertex of $G_{0}$ twice
with probability $0.8$. Then, we relabel the vertices in $G_{2}$ according to
a random permutation $\pi:[n_{2}]\to[n_{2}]$, where $n_{2}$ is the number of
nodes in $G_{2}$. Let $m$ denote the number of common vertices that appear in
both $G_{1}$ and $G_{2}$. The initial seed set is constructed by including
each true pair independently with probability $\theta$. We treat $G_{1}$ as
the public network and $G_{2}$ as the private network, and the goal is to de-
anonymize the node identities in $G_{2}$ by matching $G_{1}$ and $G_{2}$. In
Fig. 4, we show the performance of our PLD algorithm and five other
algorithms, when the fraction of initial seeds $\theta$ varies from $0$ to
$0.05$. We can observe that our PLD algorithm significantly outperforms the
other algorithms.

Figure 4: Performance comparison of the PLD algorithm and five other
algorithms applied to the Facebook networks.

####  6.3.3 Autonomous Systems Networks

Following [FMWX20], we use the Autonomous Systems (AS) data set from [LK14] to
further test the graph matching performance on power-law graphs. The data set
consists of 9 graphs of Autonomous Systems peering information inferred from
Oregon route-views between March 31, 2001, and May 26, 2001. Since some
vertices and edges are changed over time, these nine graphs can be viewed as
correlated versions of each other. The number of vertices of the 9 graphs
ranges from 10,670 to 11,174 and the number of edges from 22,002 to 23,409. We
aim to match each graph to that on March 31, with vertices randomly permuted.
The initial seed set is obtained by including each true pair independently
with probability $\theta=0.1$.

The power-law exponent of the Autonomous Systems networks is estimated to be
2.01 according to (14). Note that in this experiment, the two correlated
graphs are provided by the real data set. Thus, we further estimate the
correlation parameter $s$ according to (15).

The performance comparison of the six algorithms is plotted in Fig. 5 for
$\theta=0.1$. We observe that our PLD algorithm again significantly
outperforms the other algorithms. Note that the accuracy rates for all
algorithms decay in time, because over time the graphs become less correlated
with the initial one on March 31.

Figure 5: Performance comparison of the PLD algorithm and five other
algorithms applied to the Autonomous Systems graphs when $\theta=0.1$.

##  7  Analysis

In this section, we present the proof for Theorem 2. In Section 7.1, we
describe the dependency issue in our analysis and how we deal with it. In
Section 7.2, we prove that all the true pairs in the first slice $Q_{1}$ are
matched error-free by the $D$-hop algorithm. Using the matched vertices in the
previous slice as new seeds, we show in Section 7.3 that all the true pairs in
slice $Q_{k}$ are matched error-free by the $1$-hop algorithm for $2\leq k\leq
k^{*}$. Further, Section 7.4 proves that using the match pairs in slice
$k^{*}$ as new seeds, the PGM algorithm correctly matches a constant fraction
of true pairs with low weights. Finally, in Section 7.5, we come back to
$Q_{0}$ and prove that using all the matched pairs as seeds, all the true
pairs in $Q_{0}$ are matched error-free by the $1$-hop algorithm. Theorem 2
readily follows by combining these results. The proofs of auxiliary lemmas can
be found in Appendix B.2.

For ease of presentation, throughout the analysis, we assume without loss of
generality that the true mapping $\pi$ is the identity permutation. We further
assume $\gamma>0$ and the integer $D$ are such that
$\gamma\leq\log_{n}w_{\max}$, $n^{2\gamma}=o(n)$, and (10) holds.

###  7.1 Deal with the Dependency Issues

In Algorithm 1, we use degrees as guidance to define the imperfect slice
$\widehat{P}_{k}^{G_{j}}$ for $j=1,2$ and the induced graphs
$\widehat{G}_{1},\widehat{G}_{2}$. However, if we condition on the degrees,
then the edges are no longer independently generated with probability $p_{ij}$
as defined in the Chung-Lu model. To deal with this dependency issue, we
construct slices based on vertex weight that “sandwich”
$\widehat{P}_{k}^{G_{j}}$. Recall that the perfect slices defined as
$P_{k}=\\{u:w_{u}\in[\alpha_{k},\alpha_{k-1}]\\}$. By construction and the
concentration of vertex degrees, we expect that
$P_{k}\subset\widehat{P}_{k}^{G_{j}}$. We also need another weight-guided
slice to contain $\widehat{P}_{k}^{G_{j}}$. Specifically, define

$\overline{P}_{k}=\\{u:w_{u}\in[(1-2\delta)\alpha_{k},(1+2\delta)\alpha_{k-1}]\\},$

where $\delta=\frac{1}{8}$. We also define
$\overline{Q}_{k}\triangleq\overline{P}_{k}\times\overline{P}_{k}$. The
following lemma shows that with high probability,
$P_{k}\subset\widehat{P}_{k}^{G_{j}}\subset\overline{P}_{k}$ and hence
$Q_{k}\subset\widehat{Q}_{k}\subset\overline{Q}_{k}$. Similarly, we define two
different subsets of vertices that “sandwich” $V_{j}$:

$\underline{V}=\\{u:w_{u}\in[0,n^{\gamma}]\\}\quad\text{ and
}\quad\overline{V}=\\{u:w_{u}\in[0,(1+2\delta)n^{\gamma}]\\}.$

Further, let $\underline{G}_{j}$ and $\overline{G}_{j}$ denote the subgraph of
$G_{j}$ induced by the vertex set $\underline{V}$ and $\overline{V}$,
respectively, for $j=1,2$. The following lemma shows that with high
probability, $\underline{V}\subset V_{j}\subset\overline{V}$ and hence
$\underline{G}_{j}\subset\widehat{G}_{j}\subset\overline{G}_{j}$.

######  Lemma 1.

For any $0\leq k\leq k^{*}$,

$\displaystyle\mathbb{P}\left\\{Q_{k}\subset\widehat{Q}_{k}\subset\overline{Q}_{k}\right\\}\geq
1-n^{-4+o(1)},$

and

$\mathbb{P}\left\\{Q_{\geq k^{*}}\subset\widehat{Q}_{\geq
k^{*}}\subset\overline{Q}_{\geq k^{*}}\right\\}\geq 1-n^{-4+o(1)}.$

For $j=1,2$,

$\mathbb{P}\left\\{\underline{V}\subset
V_{j}\subset\overline{V}\right\\}=\mathbb{P}\left\\{\underline{G}_{j}\subset\widehat{G}_{j}\subset\overline{G}_{j}\right\\}\geq
1-n^{-3+o(1)}.$

###  7.2 Match Pairs in $\widehat{Q}_{1}$ using $D$-hop Algorithm

Recall that we give a heuristic argument of (8), showing that for a true pair
in $Q_{1}$, the number of common $D$-hop neighbors of $\Theta(1)$ weights is
on the order of $n^{\gamma(3-\beta)(D-1)+1}$, by ignoring the the potential
dependency between $\widehat{G}_{j},\widehat{Q}_{1}$ and graphs $G_{1},G_{2}$.
To resolve this dependency, we crucially exploit the fact that with high
probability $Q_{1}\subset\widehat{Q}_{1}$ and
$\underline{G}_{j}\subset\widehat{G}_{j}$ as shown in Lemma 1. In particular,
we consider a true pair $(u,u)$ in ${Q}_{1}$ and bound its number of
$\Theta(1)$-weight $D$-hop neighbors in $\underline{G}_{j}$. Unfortunately,
even when $\underline{G}_{j}\subset\widehat{G}_{j}$, the $D$-hop neighbors of
$u$ in $\underline{G}_{j}$ may contain some vertices that are within the
$(D-1)$-hop neighborhood of $u$ in $\widehat{G}_{j}$, which means
$\Gamma_{D}^{\underline{G}_{j}}\nsubseteq\Gamma_{D}^{\widehat{G}_{j}}$. In
order to exclude such vertices, we bound the number of $\Theta(1)$-weight
vertices in $N_{D-1}^{\overline{G}_{j}}(u)$ from above. Fortunately,
$\big{|}N_{D-1}^{\overline{G}_{j}}(u)\big{|}$ is close to
$\big{|}\Gamma_{D-1}^{\overline{G}_{j}}(u)\big{|}$, which is on the order of
$n^{\gamma(3-\beta)(D-2)+1}$ and thus is much smaller than
$\big{|}\Gamma_{D}^{\underline{G}_{j}}\big{|}$. To be more precise, we have
the following lemma.

######  Lemma 2.

Fix any vertex $u\in P_{1}$ and constant $c$. For all sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{D}^{\underline{G}_{1}\land\underline{G}_{2}}(u)\cap\\{i:w_{i}\leq
c\\}\right|\geq\Gamma_{\min}\right\\}\geq 1-n^{-4+o(1)},$ (16)
$\displaystyle\mathbb{P}\left\\{\left|N_{D-1}^{\overline{G}_{j}}(u)\cap\\{i:w_{i}\leq
c\\}\right|\leq N_{\max}\right\\}\geq 1-n^{-4+o(1)},\text{ for }j=1,2,$ (17)

where $\Gamma_{\min}=\frac{1}{2}\left(\frac{C\cdot
s^{2}}{12\cdot\overline{w}}\right)^{D}n^{\gamma((3-\beta)(D-1)+1)}$ and
$N_{\max}=2c\kappa^{D}n^{\gamma((3-\beta)(D-2)+1)}$.

To appreciate the utility of Lemma 2, note that under the high-probability
event $\underline{G}_{j}\subset\widehat{G}_{j}\subset\overline{G}_{j}$ for
$j=1,2$, we have

$\Gamma_{D}^{\widehat{G}_{1}}(u)\cap\Gamma_{D}^{\widehat{G}_{2}}(u)\supset\Gamma_{D}^{\underline{G}_{1}\land\underline{G}_{2}}(u)\setminus\left(N_{D-1}^{\overline{G}_{1}}(u)\cup
N_{D-1}^{\overline{G}_{2}}(u)\right).$

Therefore, combining (16) and (17) implies that with high probability,

$\displaystyle\left|\Gamma_{D}^{\widehat{G}_{1}}(u)\cap\Gamma_{D}^{\widehat{G}_{2}}(u)\cap\\{i:w_{i}\leq
c\\}\right|\geq\Gamma_{\min}-2N_{\max}\approx\Gamma_{\min},$ (18)

where the last approximation holds because $\Gamma_{\min}\gg N_{\max}$ due to
$2<\beta<3.$ Hence, the last display yields the desired lower bound (8) to the
number of common $D$-hop neighbors of $\Theta(1)$ weights for a true pair
$(u,u)$ in $Q_{1}$.

Next, we adopt a similar strategy to study fake pairs. In particular, for a
fake pair in $\widehat{Q}_{1}$, we bound from above its number of common
$D$-hop neighbors of weights smaller than $\frac{15}{s}\log n$.444The
threshold $\frac{15}{s}\log n$ is chosen such that
$\\{i:w_{i}\leq\frac{15}{s}\log n\\}$ contains
$\\{i:|\Gamma_{1}^{G_{1}}(i)|\leq 5\log n,|\Gamma_{1}^{G_{2}}(i)|\leq 5\log
n\\}$ with high probability. Again, to circumvent the dependency between
$\widehat{G}_{j},\widehat{Q}_{1}$ and graphs $G_{1},G_{2}$, we consider a fake
pair $(u,v)$ in $\overline{Q}_{1}$ and bound from above its number of
$\Theta(1)$-weight neighbors within the common $D$-hop neighborhood in
$\overline{G}_{1}$ and $\overline{G}_{2}.$

######  Lemma 3.

Fix any two distinct vertices $u,v\in\overline{P}_{1}$. For sufficiently large
$n$,

$\displaystyle\mathbb{P}\left\\{\left|N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(v)\cap\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right|\leq\Psi_{\max}\right\\}\geq 1-n^{-4+o(1)},$ (19)

where
$\Psi_{\max}=\frac{2^{3-\beta}\kappa^{2D}n^{2\gamma((3-\beta)(D-1)+1)}}{(2^{3-\beta}-1)Cn}\left(\frac{15}{s}\log
n\right)^{3-\beta}+\frac{2^{\beta-2}}{2^{\beta-2}-1}\kappa^{D-1}n^{(\gamma(3-\beta)(D-2)+1)}(4+6\log
n).$

######  Remark 1.

To see how (19) follows, note that

$N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(v)\subset\left(\Gamma_{D}^{\overline{G}_{1}}(u)\cup
N_{D-1}(u,v)\right)\cap\left(\Gamma_{D}^{\overline{G}_{2}}(v)\cup
N_{D-1}(u,v)\right)=\left(\Gamma_{D}^{\overline{G}_{1}}(u)\cap\Gamma_{D}^{\overline{G}_{2}}(v)\right)\cup
N_{D-1}(u,v),$

where $N_{D-1}(u,v)=N_{D-1}^{\overline{G}_{1}}(u)\cup
N_{D-1}^{\overline{G}_{2}}(v)$. We have already obtained an upper bound to
$\left|N_{D-1}^{\overline{G}_{j}}\right|$ when proving (17) for $j=1,2$. Thus,
it remains to bound from above
$\left|\Gamma_{D}^{\overline{G}_{1}}(u)\cap\Gamma_{D}^{\overline{G}_{2}}(v)\right|$.
A simple yet key observation is that for a vertex $i$ of weight 1, there are
two extreme cases in which $i$ becomes a common $D$-hop neighbor of $(u,v)$.
One case is that $i$ connects to some vertex in
$\Gamma_{D-1}^{\overline{G}_{1}}(u)\setminus\Gamma_{D-1}^{\overline{G}_{2}}(v)$,
and connects to some other vertex in
$\Gamma_{D-1}^{\overline{G}_{2}}(v)\setminus\Gamma_{D-1}^{\overline{G}_{1}}(u)$.
It can be shown that each of these two connections happens independently with
probability approximately $q_{D}$ and thus the number of such common $D$-hop
neighbors is about $nq_{D}^{2}$, which roughly gives rise to the first term of
$\Psi_{\max}$. The other extreme case is that $i$ is a $(D-1)$-hop neighbor of
some common neighbor of $(u,v)$. Luckily, the common 1-hop neighborhood of
$(u,v)$ is typically of a very small size and thus we can bound from above
$\left|\Gamma_{1}^{\overline{G}_{1}}(u)\cap\Gamma_{1}^{\overline{G}_{2}}(v)\right|$
by approximately $\log n$. Moreover, $i$ becomes a $(D-1)$-hop neighbor of a
given vertex in
$\Gamma_{1}^{\overline{G}_{1}}(u)\cap\Gamma_{1}^{\overline{G}_{2}}(v)$ with
probability at most $q_{D-1}$. Thus, the number of such common $D$-hop
neighbors is at most around $nq_{D-1}\log n$, which gives an expression close
to the second term of $\Psi_{\max}$. These two extreme cases turn out to be
the dominating cases as shown in the proof of Lemma 3.

To see the usage of Lemma 3, note that under the high-probability event
$\widehat{G}_{j}\subset\overline{G}_{j}$ for $j=1,2$, we have
$\Gamma_{D}^{\widehat{G}_{1}}(u)\cap\Gamma_{D}^{\widehat{G}_{2}}(v)\subset
N_{D}^{\overline{G}_{1}}(u)\cap N_{D}^{\overline{G}_{2}}(v).$ Therefore, (19)
implies that with high probability

$\displaystyle\left|\Gamma_{D}^{\widehat{G}_{1}}(u)\cap\Gamma_{D}^{\widehat{G}_{2}}(v)\cap\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right|\leq 2\Psi_{\max},$ (20)

which yields the desired upper bound to the number of common $D$-hop neighbors
of $\Theta(1)$ weights for a fake pair $(u,v)$ in $\widehat{Q}_{1}$.

Finally, since we have $n^{\gamma(3-\beta)}\gg\log n$ and
$n^{\gamma((3-\beta)(D-1)+1)}(\log n)^{3-\beta}=O(n)$ based on the choice in
(11), it follows that $\Gamma_{\min}>2\Psi_{\max}$. Moreover, (11) ensures
that $\Gamma_{\min}\theta=\Omega(\log n)$. Therefore, combining (18) and (20)
implies that the true pairs in $Q_{1}$ have more $D$-hop witnesses than the
fake pairs in $\widehat{Q}_{1}$. Hence, we can use Algorithm 1 to match pairs
in $\widehat{Q}_{1}$ correctly. More precisely, we have the following lemma.

######  Lemma 4.

Under the conditions of Theorem 2, for all sufficiently large $n$, the set of
matched pairs in Step 5 of Algorithm 1, denoted by ${\mathcal{R}}_{1}$,
contains all true pairs in ${Q}_{1}$ and no fake pairs in $\widehat{Q}_{1}$
with probability at least $1-n^{-1.5+o(1)}$.

###  7.3 Match Pairs in $\widehat{Q}_{k}$ Slice by Slice using $1$-hop
Algorithm

Given that all the true pairs in $Q_{1}$ are matched error-free, we show that
all the true pairs in $Q_{k}$ are matched error-free by the $1$-hop algorithm
for all $2\leq k\leq k^{*}$.

Note that when matching pairs in $\widehat{Q}_{k}$, we use
${\mathcal{R}}_{k-1}$, the set of matched vertices in $\widehat{Q}_{k-1}$, as
seeds. Suppose slice $k-1$ is successfully matched. Then,
${\mathcal{R}}_{k-1}$ contains all the true pairs in $Q_{k-1}$. Therefore, for
a true pair in $Q_{k}$, to bound from below its number of $1$-hop witnesses in
${\mathcal{R}}_{k-1}$, it suffices to consider its number of $1$-hop common
neighbors in $P_{k-1}$, which is on the order of
$\frac{\alpha_{k-1}^{3-\beta}}{2\overline{w}}$ as we explained in (9). This is
made precise by the following lemma.

######  Lemma 5.

Fix any $2\leq k\leq k^{*}$ and any vertex $u\in P_{k}$. For all sufficiently
large $n$,

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(u)\cap
P_{k-1}\right|\geq\xi_{k}\right\\}\geq 1-n^{-4},$ (21)

where $\xi_{k}=\frac{C\alpha_{k-1}^{3-\beta}s^{2}}{16\overline{w}}.$

Moreover, if slice $k-1$ is successfully matched, since there is no matching
error, on the high-probability event
$\widehat{P}_{k-1}\subset\overline{P}_{k-1},$ ${\mathcal{R}}_{k-1}$ is
contained by the set of true pairs in
$\overline{Q}_{k-1}\triangleq\overline{P}_{k-1}\times\overline{P}_{k-1}$.
Therefore, for a fake pair in $\widehat{Q}_{k}$, to bound from above its the
number of $1$-hop witnesses in ${\mathcal{R}}_{k-1}$, it suffices to bound its
number of $1$-hop common neighbors in $\overline{P}_{k-1}$, which is done in
the following lemma. Note that to resolve the potential dependency between
$\widehat{Q}_{k}$ and graphs $G_{1},G_{2}$, we state the lemma for a fake pair
in $\overline{Q}_{k}$, which contains $\widehat{Q}_{k}$ with high probability.

######  Lemma 6.

Fix any $2\leq k\leq k^{*}$ and any two distinct vertices
$u,v\in\overline{P}_{k}$, Then for all sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(v)\cap\overline{P}_{k-1}\right|\leq\zeta_{k}\right\\}\geq
1-n^{-4},$ (22)

where
$\zeta_{k}=\frac{8(1+2\delta)^{4}C\alpha_{k-1}^{5-\beta}}{\overline{w}^{2}n}+\frac{16}{3}\log
n.$

To see how (22) follows, note that a vertex in $\overline{P}_{k-1}$ is a 1-hop
common neighbor for the fake pair $(u,v)$ with probability at most on the
order of
$\left(\frac{\alpha_{k}\alpha_{k-1}}{n\overline{w}}\right)^{2}=\frac{\alpha_{k-1}^{4}}{4n^{2}\overline{w}^{2}}$.
Since there are $\Theta(n\alpha_{k-1}^{1-\beta})$ vertices in
$\overline{P}_{k-1}$, the number of 1-hop common neighbors in
$\overline{P}_{k-1}$ is about
$\frac{\alpha_{k-1}^{5-\beta}}{4n\overline{w}^{2}}$ on expectation. The extra
term $\frac{16}{3}\log n$ in (22) comes from the sub-exponential tail bounds
when we apply concentration inequalities.

Recall that we assume $n^{2\gamma}=o(n)$ and hence
$\alpha_{k-1}^{3-\beta}\gg\frac{\alpha_{k-1}^{5-\beta}}{n}$ for $2\leq k\leq
k^{*}$. Moreover,
$\alpha_{k-1}^{3-\beta}\geq\alpha_{k^{*}}^{3-\beta}\geq\frac{192\overline{w}\log
n}{Cs^{2}}$ for $2\leq k\leq k^{*}$. It then can be verified that
$\xi_{k}>\zeta_{k}$. Thus, we expect that the $1$-hop algorithm can match
vertex pairs in $\widehat{Q}_{k}$ correctly. More precisely, we have the
following lemma.

######  Lemma 7.

Under the conditions of Theorem 2, for all sufficiently large $n$, with
probability at least $1-n^{-1.5+o(1)}$, the set of matched pairs in Step 6-8
of Algorithm 1, denoted by ${\mathcal{R}}_{k}$, contains all true pairs in
${Q}_{k}$ and no fake pairs in $\widehat{Q}_{k}$ for all $2\leq k\leq k^{*}$.

###  7.4 Match Low-Weight Pairs by PGM

We proceed to match pairs with weight smaller than $\alpha_{k^{*}}$ using the
PGM algorithm. As explained in Section 4.2, we expect that the number of
common 1-hop neighbors for any fake pair with weights smaller than
$\alpha_{k^{*}}$ is at most $2$. Thus, even if all low-weight true pairs are
provided as seeds, no fake pair will be matched by the PGM algorithm with
threshold $r=3$. This is made precise by the following lemma.

######  Lemma 8.

Denote $\overline{P}_{\geq
k^{*}}=\\{u:w_{u}\in[0,(1+2\delta)\alpha_{k^{*}-1}]\\}$. Fix any two distinct
vertices $u,v\in\overline{P}_{\geq k^{*}+1}$. Then for all sufficiently large
$n,$

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(v)\cap\overline{P}_{\geq
k^{*}}\right|\leq 2\right\\}\geq 1-n^{-2}.$ (23)

Although the PGM algorithm may fail to match some true pairs with very few
common 1-hop neighbors, it is expected to match the true pair with at least
three 1-hop witnesses. In particular, let us recursively define

$S_{0}=P_{k^{*}},\quad S_{h}=\\{u:u\in P_{h+k^{*}},\
|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(u)\cap S_{h-1}|\geq
3\\}\quad\text{ for }h\geq 1.$

Note that $S_{0}=P_{k^{*}}$ has been correctly matched based on Lemma 7 in the
previous step. Also, once the true pairs in $S_{h-1}$ are added into the set
of matched pairs, the PGM algorithm with threshold $r=3$ can use the vertices
in $S_{h-1}$ as new seeds to match vertices in $S_{h}$ correctly. Therefore,
all the true pairs in $S_{h}$ for any $h\geq 1$ can be correctly matched.
Thus, to show the PGM matches many true pairs, it suffices to bound from below
the size of $S_{h}$ for $h\leq h^{*}$, which is done by the following theorem.

######  Lemma 9.

Let $\widetilde{w}\triangleq\left(\frac{192\overline{w}\ln
2}{Cs^{2}}\right)^{1/(3-\beta)}$. Define $h^{*}$ such that
$\widetilde{w}\leq\alpha_{k^{*}+h^{*}}<2\widetilde{w}.$ Then for any $1\leq
h\leq h^{*}$, and all sufficiently large $n,$

$\displaystyle\mathbb{P}\left\\{\left|S_{h}\right|\geq\frac{1}{2}n_{k^{*}+h}\right\\}\geq
1-n^{-3+o(1)}.$ (24)

The proof of Lemma 9 follows by induction. Assume (24) holds for $h-1$. Then
analogous to the intuition of (9), for any $u$ in $P_{k^{*}+h}$,
$\mathbb{E}\left[\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(u)\cap
S_{h-1}\right|\right]\approx\frac{\alpha_{k^{*}+h}^{3-\beta}Cs^{2}}{\overline{w}}\geq
4\ln 2$. Hence, we can show that $\mathbb{P}\left\\{u\in
S_{h}\right\\}\geq\frac{3}{4}$, which further implies (24) holds for $h$ by
concentration.

By Lemma 9, the PGM matches at least half of true pairs in $P_{k^{*}+h^{*}}$.
Note that the number of vertices in $P_{k^{*}+h^{*}}$ satisfies
$n_{k^{*}+h^{*}}=Cn(\alpha_{k^{*}+h^{*}-1})^{1-\beta}\geq
Cn(\widetilde{w})^{1-\beta}=\Theta(n)$, as $\widetilde{w}=\Theta(1)$. Thus,
the set of matched pairs by the PGM contains a constant fraction of true
pairs. More precisely, we have the following lemma.

######  Lemma 10.

Under the conditions of Theorem 2, for all sufficiently large $n$, with
probability at least $1-n^{-1+o(1)}$, the set of matched pairs in Step 10 of
Algorithm 1, denoted by ${\mathcal{R}}_{k^{*}+1}$, contains all true pairs in
$S_{h}$ and no fake pairs in $\widehat{Q}_{k^{*}+h}$ for all $h\geq 1$. In
particular, we have $\left|{\mathcal{R}}_{k^{*}+1}\right|=\Theta(n)$ with
probability at least $1-n^{-1+o(1)}$.

###  7.5 Match Pairs in $\widehat{Q}_{0}$ using $1$-hop Algorithm

Given that a large constant fraction of true pairs with weights smaller than
$\alpha_{0}$ are matched error-free, we show that all the true pairs in
$Q_{0}$ are matched error-free by the $1$-hop algorithm.

When we match vertices in $\widehat{Q}_{0}$, we use $\widehat{{\mathcal{R}}}$,
the set of pairs matched in Step $5-10$ of Algorithm 1, as seeds. Note that
all true pairs in $Q_{k^{*}}$ have been proved to be matched correctly with
high probability. The number of true pairs in $Q_{k^{*}}$ is
$\Theta(n\alpha_{k^{*}-1}^{1-\beta})$ and the vertex in $P_{0}$ has weight
larger than $n^{\gamma}$. Moreover, a vertex in $P_{0}$ connects to a vertex
in $P_{k^{*}}$ with probability at least
$\frac{\alpha_{0}\alpha_{k^{*}}}{n\overline{w}}$. Therefore, for a true pair
in $Q_{0}$, to bound from below its number of $1$-hop witnesses in
$\widehat{{\mathcal{R}}}$, it suffices to consider its number of $1$-hop
common neighbors in $P_{k^{*}}$, which is about
$n\alpha_{k^{*}-1}^{1-\beta}\times\frac{\alpha_{0}\alpha_{k^{*}}}{n\overline{w}}=\Theta(\alpha_{k^{*}}^{2-\beta}n^{\gamma})$.
More precisely, we have the following theorem.

######  Lemma 11.

Fix any vertex $u\in P_{0}$. For all sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(u)\cap
P_{k^{*}}\right|\geq\frac{C\alpha_{k^{*}}^{2-\beta}\alpha_{0}s^{2}}{8\overline{w}}\right\\}\geq
1-n^{-4}.$ (25)

We caution the reader that even though the true pair $(u,u)$ may have more
$1$-hop witnesses in $Q_{k^{*}+1}$ than $Q_{k^{*}}$, we cannot consider its
number of $1$-hop common neighbors in $P_{k^{*}+1}$, because the PGM algorithm
only matches a subset of the true pairs in $Q_{k^{*}+1}$ and this subset is
random and may incur dependency issues to the analysis.

Next we study fake pairs. Note that with high probability
$\widehat{{\mathcal{R}}}$ contains no fake pair in $\bigcup_{k\geq
1}\widehat{Q}_{k}$. Therefore, on the event that
$\widehat{P}_{k}\subset\overline{P}_{k}$ for all $k\geq 1,$ all the matched
pairs in $\widehat{{\mathcal{R}}}$ is contained by the set of true pairs in
$\overline{R}\times\overline{R}$, where $\overline{R}=\bigcup_{k\geq
1}\overline{P}_{k}=\\{i:w_{i}\in[0,(1+2\delta)n^{\gamma}]\\}$. Therefore, for
a fake pair in $\widehat{Q}_{0}$, to bound from above its the number of
$1$-hop witnesses in $\widehat{{\mathcal{R}}}$, it suffices to bound its
number of $1$-hop common neighbors in $\overline{R}$, which is done in the
following lemma. Again, to resolve the potential dependency between
$\widehat{Q}_{0}$ and graphs $G_{1},G_{2}$, we state the lemma for a fake pair
in $\overline{Q}_{0}$, which contains $\widehat{Q}_{0}$ with high probability.

######  Lemma 12.

Denote $\overline{R}=\\{i:w_{i}\in[0,(1+2\delta)n^{\gamma}]\\}$. Fix any two
distinct vertices $u,v\in\overline{P}_{0}$. For all sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(v)\cap\overline{R}\right|\leq
4\kappa n^{\gamma(3-\beta)}s^{2}\right\\}\geq 1-n^{-4},$ (26)

where
$\kappa=\frac{(1+2\delta)^{2}2^{5-\beta}C}{(2^{3-\beta}-1)\overline{w}}$.

To see how (26) follows, note that a vertex in $P_{k}$ becomes a common 1-hop
neighbor of the fake pair $(u,v)$ with probability at most
$\left(\frac{\alpha_{k}w_{\max}}{n\overline{w}}\right)^{2}\leq\frac{\alpha_{k}^{2}}{n\overline{w}}$.
Since there are $\Theta(n\alpha_{k}^{1-\beta})$ true pairs in $Q_{k}$, the
number of common 1-hop neighbors in $\overline{R}$ is on the order of
$\sum_{k=1}^{K}\frac{\alpha^{3-\beta}_{k}}{\overline{w}}=\Theta\left(n^{\gamma(3-\beta)}\right)$.

Recall that $\overline{P}_{0}\subset P_{0}\cup P_{1}$. Thus for any fake pair
$(u,v)\in\overline{Q}_{0}$, the two corresponding true pairs $(u,u),(v,v)\in
Q_{0}\cup Q_{1}$. If one of them is in $Q_{1},$ then it has already been
matched in $\widehat{Q}_{1}$ by Lemma 4. If one of them is in $Q_{0}$, since
$\alpha_{k^{*}}^{2-\beta}n^{\gamma}=\Theta\left(n^{\gamma}(\log
n)^{(2-\beta)/(3-\beta)}\right)\gg n^{\gamma(3-\beta)}$ in view of
$2<\beta<3$, it has more $1$-hop witnesses than the fake pair $(u,v).$ Thus,
we expect that the $1$-hop algorithm can match all the true pairs in
$\widehat{Q}_{0}$ error-free. More precisely, we have the following lemma.

######  Lemma 13.

Under the conditions of Theorem 2, for all sufficiently large $n$, with
probability at least $1-n^{-2.5}$, the set of matched pairs in Step 11 of
Algorithm 1, denoted by ${\mathcal{R}}_{0}$, contains all true pairs in
${Q}_{0}$ and no fake pairs in $\widehat{Q}_{0}$.

###  7.6 Proof of Theorem 2

Due to Lemma 10 and ${\mathcal{R}}_{k^{*}+1}\subset{\mathcal{R}}$, the set of
matched pairs by Algorithm 1 contains $\Theta(n)$ true pairs with probability
at least $1-n^{-1+o(1)}$. Combining Lemma 4, Lemma 7, Lemma 10 and Lemma 13,
${\mathcal{R}}$ contains no fake pairs with probability at least
$1-n^{-1+o(1)}$.

##  8 Conclusion

In this paper, we propose an efficient seeded algorithm for matching graphs
with power-law degree distributions. Theoretically, under the Chung-Lu model
with power-law exponent $2<\beta<3$ and max degree $\Theta(\sqrt{n})$, we show
that as soon as $D>\frac{4-\beta}{3-\beta}$, by optimally choosing the first
slice, our algorithm correctly matches a constant fraction of true pairs
without any error with high probability, provided with only $\Omega((\log
n)^{4-\beta})$ initial seeds. This achieves an exponential reduction in the
seed size requirement, as the previously best known result requires
$n^{1/2+\epsilon}$ initial seeds. Empirically, numerical experiments in both
synthetic and real power-law graphs further demonstrate that our algorithm
significantly outperforms the state-of-the-art algorithms. These results
uncover the enormous power of $D$-hops in seeded graph matching under power-
law graphs. An interesting and important future direction is to further
investigate the power of $D$-hops in matching power-law graphs without seeds.

##  Appendix A Computational Complexity Analysis

We analyze the computational complexity of Algorithm 1 in each step.

First, Algorithm 1 checks all the vertex degrees to construct the subgraphs
$\widehat{G}_{i}$, ${G}^{\prime}_{i}$ for $i=1,2$ and partition the vertices
in $G_{1}$ and $G_{2}$ into slices based on vertex degrees in line 2-4 and
line 9. The total time complexity of this step is $O(n)$.

We then apply the $D$-hop algorithm in the first slice. Searching for all
$D$-hop neighbors of a given vertex $u$ in the first slice takes a total of
$O(n)$ time steps. The number of vertices in the first slice in
$\Theta(n\alpha_{1}^{1-\beta})$. Thus, the complexity of counting $D$-hop
witnesses for all vertices-pairs in the first slice-pair is
$O(n^{3}\alpha_{1}^{2(1-\beta)})=O(n^{3-2\gamma(\beta-1)})$. Since we have
shown that with high probability, all the fake pairs have $D$-hop witnesses
fewer than the threshold, we only need to sort and match at most $n$ true
pairs using GMWM and hence the complexity of the GMWM step is $O(n\log n).$

We next apply the 1-hop algorithm in the subsequent slices. We compute the
number of $1$-hop witnesses via neighborhood exploration. For each matched
pair in $Q_{k-1}$, we fetch its 1-hop neighbors of size $O(\alpha_{k-1})$ in
$\widehat{G}_{1}$ and $\widehat{G}_{2}$, and then increase the number of 1-hop
witnesses by 1 for $O(\alpha_{k-1}^{2})$ vertex-pairs. Thus, the total
complexity of our algorithm to match vertices in $P_{k}$ is about
$n\alpha_{k-1}^{1-\beta}\times\alpha_{k-1}^{2}=O(n^{1+\gamma(3-\beta)})$.
Further, we match $k^{*}-1$ slices in line 6-8. Therefore, the total
complexity is $O(n^{1+\gamma(3-\beta)}\log n)$.

Analogously, the PGM algorithm explores the 1-hop neighbors of each matched
pair. There are at most $n$ matched pair, and for each mathced pair, we
increase the number of $1$-hop witnesses by $1$ for $O(\triangle^{2})$ vertex-
pairs, where $\triangle$ is the largest degree among $G_{1}^{\prime}$ and
$G_{2}^{\prime}$. By the definition, $\triangle$ is $O((\log
n)^{\frac{1}{3-\beta}})$. Therefore, the total complexity in line 10 is
$O(n(\log n)^{\frac{2}{3-\beta}})$.

Finally, there are at most $n$ true pairs to serve as 1-hop witnesses for
vertex-pairs in $\widehat{Q}_{0}$. For any true pair $(i,i)$, the complexity
of neighborhood exploration is
$O(|\Gamma_{1}^{G_{1}}(i)||\Gamma_{1}^{G_{2}}(i)|)$. Thus, the complexity of
line 11 is
$\sum_{i=1}^{n}|\Gamma_{1}^{G_{1}}(i)||\Gamma_{1}^{G_{2}}(i)|=O(\sum_{i=1}^{n}w_{i}^{2})=O(n^{1+(3-\beta)/2})$
as shown in [CL03, page 98].

In conclusion, by summing up the complexity for each step, the total
computational complexity of our algorithm is
$O\left((n^{3-2\gamma(\beta-1)}+n\log n+n^{1+\gamma(3-\beta)}\log n+n(\log
n)^{\frac{2}{3-\beta}}+n^{1+(3-\beta)/2}\right)=O\left(n^{3-2\gamma(\beta-1)}\right)$
due to $\gamma<1/2$ and $2<\beta<3.$

##  Appendix B Postponed Proofs

###  B.1 Supporting Theorems

######  Theorem 3.

Chernoff Bound ([DP09]): Let $X=\sum_{i\in[n]}X_{i}$, where $X_{i}$,
$i\in[n]$, are independent random variables taking values in $\\{0,1\\}$.
Then, for $\eta\in[0,1]$,

$\displaystyle\mathbb{P}\left\\{X\leq(1-\eta)\mathbb{E}\left[X\right]\right\\}\leq\exp\left(-\frac{{\eta}^{2}}{2}\mathbb{E}\left[X\right]\right),\
\mathbb{P}\left\\{X\geq(1+\eta)\mathbb{E}\left[X\right]\right\\}\leq\exp\left(-\frac{{\eta}^{2}}{3}\mathbb{E}\left[X\right]\right).$

######  Theorem 4.

Bernstein’s Inequality ([DP09]): Let $X=\sum_{i\in[n]}X_{i}$, where $X_{i}$,
$i\in[n]$, are independent random variables such that $|X_{i}|\leq K$ almost
surely. Then, for $t>0$, we have

$\displaystyle\mathbb{P}\left\\{X\geq\mathbb{E}\left[X\right]+t\right\\}\leq\exp\left(-\frac{{t}^{2}}{2(\sigma^{2}+Kt/3)}\right),$

where $\sigma^{2}=\sum_{i\in[n]}\mathsf{var}(X_{i})$ is the variance of $X$.
It follows then for $\rho>0$, we have

$\displaystyle\mathbb{P}\left\\{X\geq\mathbb{E}\left[X\right]+\sqrt{2\sigma^{2}\rho}+\frac{2K\rho}{3}\right\\}\leq\exp(-\rho).$

The obtained estimate holds for
$\mathbb{P}\left\\{X\leq\mathbb{E}\left[X\right]-\sqrt{2\sigma^{2}\rho}-\frac{2K\rho}{3}\right\\}$
too (by considering $-X$), i.e.,

$\displaystyle\mathbb{P}\left\\{X\leq\mathbb{E}\left[X\right]-\sqrt{2\sigma^{2}\rho}-\frac{2K\rho}{3}\right\\}\leq\exp(-\rho).$

######  Theorem 5.

([YXL21, Theorem 6]) For $r\geq 0$, every real number $x\in(0,1)$ and $rx\leq
1$, it holds that

$\displaystyle r\log{(1-x)}\leq\log\left(1-\frac{rx}{2}\right).$

######  Theorem 6.

([YXL21, Corollary 1]) Let $X$ denote a random variable such that $X\sim{\rm
Binom}(n,p)$. If $n\in[n_{\min},n_{\max}]$, then for $\lambda>0$,

$\displaystyle\mathbb{P}\left\\{X\geq
2n_{\max}\alpha+\frac{4\gamma}{3}\right\\}$ $\displaystyle\leq\exp(-\gamma)$
(27)

###  B.2 Proof of the Main Result

First, we define some notations related to graph slicing. We count the number
of vertices in the slice $P_{k}$ and $\overline{P}_{k}$. The vertices in
$P_{k}$ satisfies

$\displaystyle\alpha_{k}\leq
w_{i}\leq\alpha_{k-1}\Longleftrightarrow\frac{n}{\left(\frac{(\beta-1)n^{\gamma}}{(\beta-2)\overline{w}2^{k-1}}\right)^{\beta-1}}-i_{0}\leq
i\leq\frac{n}{\left(\frac{(\beta-1)n^{\gamma}}{(\beta-2)\overline{w}2^{k}}\right)^{\beta-1}}-i_{0}.$

According to the index range of the vertices, we define $n_{k}$ to be the
difference between the two bounds. To be more precise,

$\displaystyle n_{k}\triangleq Cn\alpha_{k-1}^{1-\beta},$ (28)

where $C$ throughout this paper denotes
$(2^{\beta-1}-1)\left(\frac{(\beta-2)\overline{w}}{(\beta-1)}\right)^{\beta-1}$.
Moreover, we have that

$\displaystyle n_{k}\leq\left|P_{k}\right|\leq n_{k}+1\leq\frac{11}{10}n_{k}.$
(29)

Similarly, the vertices in $\overline{P}_{k}$ satisfies

$\displaystyle(1-2\delta)\alpha_{k}\leq w_{i}\leq(1+2\delta)\alpha_{k-1}.$

Thus,

$\displaystyle\left|\overline{P}_{k}\right|\leq$
$\displaystyle\left(2^{\beta-1}(1+2\delta)^{\beta-1}-(1-2\delta)^{\beta-1}\right)\frac{n_{k}}{2^{\beta-1}-1}+1$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{\left(\frac{5}{2}\right)^{\beta-1}-\left(\frac{3}{4}\right)^{\beta-1}}{2^{\beta-1}-1}n_{k}+1\leq
2n_{k},$ (30)

where $(a)$ follows from $\delta=\frac{1}{8}$.

The number of perfect slices, denoted by $K$, is

$\displaystyle\log_{2}\left(n^{\gamma}\right)\leq K\leq
1+\log_{2}\left(n^{\gamma}\right).$

####  B.2.1 Proof of Lemma 1

First, we prove $P_{k}\subset\widehat{P}_{k}^{G_{j}}$ with high probability
for $0\leq k\leq k^{*}$ and $j=1,2$. Fix any vertex $u$ in $P_{k}$. It
suffices to show with high probability $u\in\widehat{P}_{k}^{G_{j}}$. Note
that any vertex $v$ connects to $u$ in $G_{j}$ independently with probability
$p_{uv}s$, where $j=1,2$ and $p_{uv}=\frac{w_{u}w_{v}}{n\overline{w}}$. Thus

$\mathbb{E}\left[\left|\Gamma_{1}^{G_{j}}(u)\right|\right]=\sum_{v\in
G_{j}}p_{uv}s=w_{u}s.$

Note that $\alpha_{k}\leq w_{u}\leq\alpha_{k-1}$ and
$\alpha_{k}\geq\alpha_{k^{*}}\geq\left(\frac{192\overline{w}\log
n}{Cs^{2}}\right)^{\frac{1}{3-\beta}}\geq\frac{20\log n}{\delta^{2}s}$ for the
choice of $k^{*}$ in (4) and sufficiently large $n$, in view of $2<\beta<3.$
Then, applying the Chernoff Bound in Theorem 3 with $\eta=\delta$ yields

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{j}}(u)\right|\geq(1+\delta)\alpha_{k-1}s\right\\}\leq\exp\left(-\delta^{2}\frac{\alpha_{k-1}s}{3}\right)\leq
n^{-5},$

and

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{j}}(u)\right|\leq(1-\delta)\alpha_{k}s\right\\}\leq\exp\left(-\delta^{2}\frac{\alpha_{k}s}{2}\right)\leq
n^{-5}.$

Combining the last two displayed equation yields that

$\mathbb{P}\left\\{u\notin\widehat{P}_{k}^{G_{j}}\right\\}\leq 2n^{-5}.$

Taking an union bound over $u$ gives

$\displaystyle\mathbb{P}\left\\{P_{k}\subset\widehat{P}_{k}^{G_{j}}\right\\}\geq
1-\sum_{u\in
P_{k}}\mathbb{P}\left\\{u\notin\widehat{P}_{k}^{G_{j}}\right\\}\geq
1-n^{-4+o(1)}.$ (31)

Next we show that $P_{\geq k^{*}}\subset\widehat{P}_{\geq k^{*}}^{G_{j}}$ with
high probability. Fix any vertex $u\in P_{k}$ with $k\geq k^{*}$. Take a
vertex $v\in P_{k^{*}}$ with $w_{v}=\alpha_{k^{*}-1}$. Since $w_{u}\leq
w_{v}$, we have
$\left|\Gamma_{1}^{G_{j}}(u)\right|\overset{s.t.}{\leq}\left|\Gamma_{1}^{G_{j}}(v)\right|$.
Therefore,

$\displaystyle\mathbb{P}\left\\{u\notin\widehat{P}_{\geq
k^{*}}^{G_{j}}\right\\}=\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{j}}(u)\right|\geq(1+\delta)\alpha_{k^{*}-1}s\right\\}\leq\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{j}}(v)\right|\geq(1+\delta)\alpha_{k^{*}-1}s\right\\}\leq
n^{-5},$

Taking a union bound over $u$ gives

$\displaystyle\mathbb{P}\left\\{P_{\geq k^{*}}\subset\widehat{P}_{\geq
k^{*}}^{G_{j}}\right\\}\geq 1-n^{-4+o(1)}.$ (32)

Second, we prove that for $0\leq k\leq k^{*}$, with high probability
$\widehat{P}_{k}\subset\overline{P}_{k}$, or equivalently,
$[n]\backslash\overline{P}_{k}\subset[n]\backslash\widehat{P}_{k}$, Fix any
vertex $u$ with $w_{u}>(1+2\delta)\alpha_{k-1}$, applying the Chernoff Bound
with $\eta=\frac{\delta}{1+2\delta}$ yields

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{j}}(u)\right|\leq(1+\delta)\alpha_{k-1}s\right\\}\leq\exp\left(-\delta^{2}\frac{\alpha_{k-1}s}{2(1+2\delta)}\right)\leq
n^{-5}.$ (33)

For any vertex $u$ with $w_{u}<(1-2\delta)\alpha_{k}$, applying the Chernoff
Bound with $\eta=\frac{\delta}{1-2\delta}$ yields

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{j}}(u)\right|\geq(1-\delta)\alpha_{k}s\right\\}\leq\exp\left(-\delta^{2}\frac{\alpha_{k}s}{3(1-2\delta)}\right)\leq
n^{-5}.$ (34)

Thus, we have

$\displaystyle\mathbb{P}\left\\{\widehat{P}^{G_{j}}_{k}\subset\overline{P}_{k}\right\\}=\mathbb{P}\left\\{[n]\backslash\overline{P}_{k}\subset[n]\backslash\widehat{P}^{G_{j}}_{k}\right\\}\geq
1-\sum_{u\notin\overline{P}_{k}}\mathbb{P}\left\\{u\in\widehat{P}^{G_{j}}_{k}\right\\}\geq
1-n^{-4},$ (35)

where the last inequality holds by combining (33) and (34). Moreover,

$\displaystyle\mathbb{P}\left\\{\widehat{P}^{G_{j}}_{\geq
k^{*}}\subset\overline{P}_{\geq
k^{*}}\right\\}=\mathbb{P}\left\\{[n]\backslash\overline{P}_{\geq
k^{*}}\subset[n]\backslash\widehat{P}^{G_{j}}_{\geq k^{*}}\right\\}\geq
1-\sum_{u:w_{u}>(1+2\delta)\alpha_{k^{*}-1}}\mathbb{P}\left\\{u\in\widehat{P}_{\geq
k^{*}}^{G_{j}}\right\\}\geq 1-n^{-4},$ (36)

where the last inequality holds by (33).

Then, combining (31) and (35) with the union bound yields that
$\mathbb{P}\left\\{Q_{k}\subset\widehat{Q}_{k}\subset\overline{Q}_{k}\right\\}\geq
1-n^{-4+o(1)}$ for $0\leq k\leq k^{*}$. Similarly, combining (32) and (36)
with a union bound yields that $\mathbb{P}\left\\{Q_{\geq
k^{*}}\subset\widehat{Q}_{\geq k^{*}}\subset\overline{Q}_{\geq
k^{*}}\right\\}\geq 1-n^{-4+o(1)}.$

Finally, since $\underline{V}=\bigcup_{k\geq 1}P_{k}$, $V=\bigcup_{k\geq
1}\widehat{P}^{G_{j}}_{k}$ and $\overline{V}=\bigcup_{k\geq
1}\overline{P}_{k}$, combining (31), (32), (35), and (36) with the union
bound, we have

$\mathbb{P}\left\\{\underline{G}_{j}\subset\widehat{G}_{j}\subset\overline{G}_{j}\right\\}=\mathbb{P}\left\\{\underline{V}\subset
V_{j}\subset\overline{V}\right\\}\geq 1-n^{-3+o(1)}.$

####  B.2.2 Proof of Lemma 2

Note that $\underline{G}_{1}\land\underline{G}_{2}$, $\overline{G}_{1},$ and
$\overline{G}_{2}$ are graphs that are edge-sampled from $G_{0}$ with
probability $s^{2}$, $s$, $s$, respectively. Thus, we let $G$ denote a graph
obtained by sampling each edge of $G_{0}$ independently with probability
$t=\Theta(1)$ and $\overline{G}$ denote a subgraph of $G$ induced by the
vertex set $\overline{V}=\\{u:w_{u}\in[0,(1+2\delta)n^{\gamma}]\\}$. Fix a
vertex $u\in P_{1}$, we first study its number of $d$-hop neighbors in each
slice in $\overline{G}$. Then, we can arrive at Lemma 2 by selecting the
corresponding parameters. To be more precise, we define
$\Gamma_{d,k}^{\overline{G}}(u)=\Gamma_{d}^{\overline{G}}(u)\cap\overline{P}_{k}$
and $N_{d,k}^{\overline{G}}(u)=\bigcup_{1\leq j\leq
d}\Gamma_{j,k}^{\overline{G}}(u)$. We bound $\Gamma_{d,k}^{\overline{G}}(u)$
and $N_{d,k}^{\overline{G}}(u)$ by the following lemma.

######  Lemma 14.

Fix any vertex $u\in P_{1}$, and let $\Omega_{d}$ denote the event such that
the followings hold simultaneously for $k=1,\ldots,K$:

$\displaystyle\left|\Gamma_{d,k}^{\overline{G}}(u)\right|$ $\displaystyle\geq
2^{(k-1)(\beta-2)}\left(\frac{(1-2\delta)^{2}C\cdot
t}{12\cdot\overline{w}}\right)^{d}n^{\gamma(3-\beta)d}\triangleq\Gamma_{\min}(d,k),$
(37) $\displaystyle\left|\Gamma_{d,k}^{\overline{G}}(u)\right|$
$\displaystyle\leq
2^{(k-1)(\beta-2)}\kappa^{d}n^{\gamma(3-\beta)d}\triangleq\Gamma_{\max}(d,k),$
(38) $\displaystyle\left|N_{d,k}^{\overline{G}}(u)\right|$ $\displaystyle\leq
2^{(k-1)(\beta-2)+1}\kappa^{d}n^{\gamma(3-\beta)d},$ (39)

where
$\kappa=\frac{(1+2\delta)^{2}2^{5-\beta}C}{(2^{3-\beta}-1)\overline{w}}$.
Suppose $\gamma$ and $D$ are chosen such that condition (10) holds. Then, for
all $1\leq d\leq D$ and sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\Omega_{d}\right\\}\geq 1-(4^{d}-1)n^{-4}.$
(40)

######  Remark 2.

The intuition behind Lemma 14 is as follows. Recall that $q_{d}$, the
probability that a vertex of $\Theta(1)$ weight lies in the $d$-hop
neighborhood of a vertex in the first slice, is on the order of
$n^{\gamma[(3-\beta)(d-1)+1]-1}$ in view of (7). Note that the weight of
vertices in $P_{k}$ is about $\alpha_{k}$, and the size of $P_{k}$ is
$\Theta(n\alpha_{k-1}^{1-\beta})$. Thus, the expected number of vertices in
$P_{k}$ that are $d$-hop neighbors of a given vertex in the first slice is
roughly $nq_{d}\alpha_{k-1}^{2-\beta}\approx
2^{(k-1)(\beta-2)}n^{\gamma(3-\beta)d}$. Hence, we expect (37)-(39) to hold
with high probability by concentration.

Before proving Lemma 14, we first show how to apply Lemma 14 to prove Lemma 2.
By setting $\delta=0$ and $t=s^{2}$, we have
$\overline{G}=\underline{G}_{1}\land\underline{G}_{2}$. Thus, (37) with
$k=\lceil\log_{2}(n^{\gamma})\rceil$ and $d=D$ leads to the desired conclusion
(16). Moreover, there are at most $c$ slices in $\\{i:w_{i}\leq c\\}$. By
setting $\delta=\frac{1}{8}$, $d=D-1$, $\overline{G}=\overline{G}_{j}$ (i.e.,
$t=s$), (39) with $\log_{2}(n^{\gamma}/c)\leq k\leq
K\leq\log_{2}(n^{\gamma})+1$, we have

$\displaystyle\sum_{k=\lfloor\log_{2}(n^{\gamma}/c)\rfloor}^{K}2^{(k-1)(\beta-2)+1}\kappa^{D-1}n^{\gamma(3-\beta)(D-1)}\leq
2c\kappa^{D-1}n^{\gamma((3-\beta)(D-2)+1)}=N_{\max},$

where $N_{\max}$ is given in (17). Thus, we prove the desired conclusion (17).

We then present the proof of Lemma 14.

###### Proof of Lemma 14.

Fix a vertex $u$ in $P_{1}$, we study its $d$-hop neighborhood in
$\overline{G}$ from $d=1$.

##### For $d=1$:

For each vertex $i\in\overline{P}_{k}$, define an indicator variable

$x_{i}^{k}={\mathbf{1}_{\left\\{{i\in\Gamma_{1}^{\overline{G}}(u)}\right\\}}}.$

In other words, $x_{i}^{k}=1$ if $i$ is connected to $u$ in $\overline{G}$,
and $x_{i}^{k}=0$ otherwise. Since $u\in P_{1}$, it follows that

$\displaystyle
p_{\min}^{k}=(1-2\delta)\frac{\alpha_{k}\alpha_{1}}{n\overline{w}}t\leq\mathbb{P}\left\\{x_{i}^{k}=1\right\\}\leq(1+2\delta)\frac{\alpha_{k-1}\alpha_{0}}{n\overline{w}}t=p_{\max}^{k}.$

Then, we have
$\left|\Gamma_{1,k}^{\overline{G}}(u)\right|=\sum_{i\in\overline{P}_{k}}x_{i}^{k}$
and $x_{i}^{k}$’s are independent. Recall that
$n_{k}=Cn\alpha^{1-\beta}_{k-1}$ in view of (28) and
$n_{k}\leq\left|\overline{P}_{k}\right|\leq 2n_{k}$ in view of (30). Thus

$\displaystyle n_{k}p_{\min}^{k}$
$\displaystyle=(1-2\delta)C\frac{\alpha_{k-1}^{2-\beta}\alpha_{1}}{2\overline{w}}t=(1-2\delta)C\frac{n^{\gamma(3-\beta)}}{4\cdot
2^{(k-1)(2-\beta)}\overline{w}}t,$ $\displaystyle n_{k}p_{\max}^{k}$
$\displaystyle=(1+2\delta)C\frac{\alpha_{k-1}^{2-\beta}\alpha_{0}}{\overline{w}}t=(1+2\delta)C\frac{n^{\gamma(3-\beta)}}{2^{(k-1)(2-\beta)}\overline{w}}t.$

Hence, applying Chernoff Bound in Theorem 3 with $\eta=\frac{1}{2}$ yields
that

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1,k}^{\overline{G}}(u)\right|\leq(1-2\delta)\frac{Cn^{\gamma(3-\beta)}t}{8\cdot
2^{(k-1)(2-\beta)}\overline{w}}\right\\}\leq\mathbb{P}\left\\{{\rm
Binom}\left(n_{k},p_{\min}^{k}\right)\leq\frac{1}{2}n_{k}p_{\min}^{k}\right\\}\overset{(a)}{\leq}n^{-4},$
$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1,k}^{\overline{G}}(u)\right|\geq(1+2\delta)\frac{3Cn^{\gamma(3-\beta)}t}{2^{(k-1)(2-\beta)}\overline{w}}\right\\}\leq\mathbb{P}\left\\{{\rm
Binom}\left(2n_{k},p_{\max}^{k}\right)\leq
3n_{k}p_{\max}^{k}\right\\}\overset{(b)}{\leq}n^{-4},$

where $(a)$ and $(b)$ hold because $n_{k}p_{\max}^{k}\geq
n_{k}p_{\min}^{k}\geq(1-2\delta)\frac{Cn^{\gamma(3-\beta)}t}{4\cdot\overline{w}}\geq
108\log n$ for sufficiently large $n$.

We also have $\mathbb{P}\left\\{\left|N_{1,k}^{\overline{G}}(u)\right|\geq
3n_{k}p_{\max}^{k}\right\\}\leq n^{-4}$ due to
$N_{1,k}^{\overline{G}}(u)=\Gamma_{1,k}^{\overline{G}}(u)$. Finally, taking
the union bound leads to $(\ref{eq:Omega})$ for $d=1$.

##### For $2\leq d\leq D$:

We first count the $d$-hop neighbors conditional on the $(d-1)$-hop
neighborhood of $u$ such that $\Omega_{d-1}$ holds. The high-level idea is as
follows. After the conditioning, every vertex $i$ outside the $(d-1)$-hop
neighborhood of $u$ will become a $d$-hop neighbor by connecting to at least
one of the $(d-1)$-hop neighbors $v$ of $u$. These edge connections are still
independently generated across different $v$ and $i$ according to the Chung-Lu
model.

We first bound $\left|\Gamma_{d,k}^{\overline{G}}(u)\right|$ from below. For
each vertex
$i\in\overline{P}_{k}\setminus\left(N_{d-1,k}^{\overline{G}}(u)\right)\triangleq
P_{k}^{\prime}$, define an indicator variable

$y_{i}^{k}={\mathbf{1}_{\left\\{{\exists
v\in\Gamma_{d-1}^{\overline{G}}(u):\;i\in\Gamma_{1}^{\overline{G}}(v)}\right\\}}}.$

In other words, $y_{i}^{k}=1$ if $i$ is connected to at least one $(d-1)$-hop
neighbor of $u$ in $\overline{G}$, and $y_{i}^{k}=0$ otherwise. Thus, we have
$\left|\Gamma_{d,k}^{\overline{G}}(u)\right|=\sum_{i\in
P_{k}^{\prime}}y_{i}^{k},$ and $y_{i}^{k}$’s are independent across different
$i$ conditional on $\Omega_{d-1}$.

Note that
$\Gamma_{d-1,1}^{\overline{G}}(u)\subset\Gamma_{d-1}^{\overline{G}}(u)$. Thus,
we can bound $\mathbb{P}\left\\{y_{i}^{k}=1|\Omega_{d-1}\right\\}$ from below
by considering the possible edge connections between $i$ and vertices in
$\Gamma_{d-1,1}^{\overline{G}}(u)$. More precisely, we get that

$\displaystyle\mathbb{P}\left\\{y_{i}^{k}=1\mid\Omega_{d-1}\right\\}\geq$
$\displaystyle\mathbb{P}\left\\{\exists
v\in\Gamma_{d-1,1}^{\overline{G}}(u):i\in\Gamma_{1}^{\overline{G}}(v)\mid\Omega_{d-1}\right\\}$
$\displaystyle\overset{(a)}{\geq}$ $\displaystyle
1-\left(1-p_{vi}\right)^{\Gamma_{\min}(d-1,1)}$
$\displaystyle\overset{}{\geq}$ $\displaystyle
1-\left(1-(1-2\delta)^{2}\frac{\alpha_{k}\alpha_{1}}{n\overline{w}}t\right)^{\Gamma_{\min}(d-1,1)}$
$\displaystyle\overset{(b)}{\geq}$
$\displaystyle\frac{(1-2\delta)^{2}}{2}\Gamma_{\min}(d-1,1)\frac{\alpha_{k}\alpha_{1}t}{n\overline{w}}$
$\displaystyle\overset{}{=}$
$\displaystyle\frac{3}{2^{k}Cn}\left(\frac{(1-2\delta)^{2}C\cdot
t}{12\cdot\overline{w}}\right)^{d}n^{\gamma((3-\beta)(d-1)+2)}\triangleq
p_{\min}^{k,d}.$

where $(a)$ holds because
$\left\\{i\notin\Gamma_{1}^{\overline{G}}(v)\right\\}$ are independent across
$v$; $(b)$ follows from Theorem 5.

Now, to bound $\left|\Gamma_{d,k}^{\overline{G}}(u)\right|$ from below, we
also need a lower bound to $|P_{k}^{\prime}|$, or equivalently an upper bound
to $\left|N_{d-1,k}^{\overline{G}}(u)\right|$. Since we have conditioned on
the $(d-1)$-hop neighborhood of $u$ such that event $\Omega_{d-1}$ holds. It
follows from (39) that

$\displaystyle\left|N_{d-1,k}^{\overline{G}}(u)\right|\leq$ $\displaystyle
2^{(k-1)(\beta-2)+1}\kappa^{d-1}n^{\gamma(3-\beta)(d-1)}$ $\displaystyle=$
$\displaystyle
2\kappa^{d-1}n^{\gamma((3-\beta)(d-2)+1)}\alpha_{k-1}^{1-\beta}$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{C}{10}n\alpha_{k-1}^{1-\beta}\leq\frac{1}{9}n_{k},$

where $(a)$ holds due to the condition (10). Thus, we have
$\left|P_{k}^{\prime}\right|\geq\left|P_{k}\right|-\left|N_{d-1,k}^{\overline{G}}(u)\right|\geq\frac{8}{9}n_{k}$.

Note that for sufficiently large $n$,

$\frac{8}{9}n_{k}p_{\min}^{k,d}=\frac{4}{3\cdot
2^{(k-1)(2-\beta)}}\left(\frac{(1-2\delta)^{2}Ct}{12\cdot\overline{w}}\right)^{d}n^{\gamma(3-\beta)d}=\frac{4}{3}\Gamma_{\min}(d,k)\geq
128\log n.$

Thus, we apply the Chernoff Bound in Theorem 3 with $\eta=\frac{1}{4}$ and get

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}}(u)\right|\leq\Gamma_{\min}(d,k)\mid\Omega_{d-1}\right\\}\leq\mathbb{P}\left\\{{\rm
Binom}\left(\frac{8}{9}n_{k},p_{\min}^{k,d}\right)\leq\Gamma_{\min}(d,k)\mid\Omega_{d-1}\right\\}\leq
n^{-4}.$

Next, we bound $\left|\Gamma_{d,k}^{\overline{G}}(u)\right|$ from above. To
this end, we bound
$\mathbb{P}\left\\{\overline{y}_{i}^{k}=1|\Omega_{d-1}\right\\}$ from above
and get

$\displaystyle\mathbb{P}\left\\{\overline{y}_{i}^{k}=1|\Omega_{d-1}\right\\}\overset{(a)}{\leq}$
$\displaystyle\sum_{l=1}^{K}\mathbb{P}\left\\{\exists
j\in\Gamma_{d-1,l}^{\overline{G}}(u):i\in\Gamma_{1}^{\overline{G}}(j)\mid\Omega_{d-1}\right\\}$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle(1+2\delta)^{2}\sum_{l=1}^{K}\Gamma_{\max}(d-1,l)\frac{\alpha_{k-1}\alpha_{l-1}}{n\overline{w}}$
$\displaystyle=$
$\displaystyle(1+2\delta)^{2}\frac{\kappa^{d-1}n^{\gamma((3-\beta)(d-1)+2)}}{2^{k-1}n\overline{w}}\sum_{l=1}^{K}2^{(l-1)(\beta-3)}$
$\displaystyle\overset{}{\leq}$
$\displaystyle\frac{\kappa^{d}n^{\gamma((3-\beta)(d-1)+2)}}{2^{k+1}Cn}\triangleq
p_{\max}^{k,d},$ (41)

where $(a)$ follow from the union bound; $(b)$ holds due to the union bound
and event $\Omega_{d-1}$; $(b)$ follows from $(1+x)^{r}\geq 1+rx$ for every
integer $r\geq 0$ and every real number $x\geq-2$; and the last inequality
follows from the definition of
$\kappa=\frac{(1+2\delta)^{2}2^{5-\beta}C}{(2^{3-\beta}-1)\overline{w}}$.

Also, note that $P_{k}^{\prime}\subset\overline{P}_{k}$ and thus
$|P_{k}^{\prime}|\leq|\overline{P}_{k}|\leq 2n_{k}$. For sufficiently large
$n$, we have

$2n_{k}p_{\max}^{k,d}=2^{(k-1)(\beta-2)-1}{\kappa^{d}n^{\gamma(3-\beta)d}}=\frac{1}{2}\Gamma_{\max}(d,k).$

Hence, applying Chernoff Bound in Theorem 3 with $\eta=1$ yields that

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}}(u)\right|\geq\Gamma_{\max}(d,k)\mid\Omega_{d-1}\right\\}\leq\mathbb{P}\left\\{{\rm
Binom}\left(2n_{k},p_{\max}^{k,d}\right)\geq\Gamma_{\max}(d,k)\right\\}\leq
n^{-4}.$

##### Induction:

Finally, we prove (40) by induction.

For $d=1$, we have proved that (40) holds. Suppose that (40) holds for $d-1$.
Then we have

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}}(u)\right|\leq\Gamma_{\min}(d,k)\right\\}\leq\mathbb{P}\left\\{\Omega_{d-1}^{c}\right\\}+\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}}(u)\right|\leq\Gamma_{\min}(d,k)\mid\Omega_{d-1}\right\\}\mathbb{P}\left\\{\Omega_{d-1}\right\\}\leq
4^{d-1}\cdot n^{-4}.$ (42)

Similarly, we get

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}}(u)\right|\geq\Gamma_{\max}(d,k)\right\\}\leq
4^{d-1}\cdot n^{-4}$ (43)

Since
$\left|N_{d,k}^{\overline{G}}(u)\right|=\left|N_{d-1,k}^{\overline{G}}(u)\right|+\left|\Gamma_{d,k}^{\overline{G}}(u)\right|$,
we take an union bound and have

$\displaystyle\mathbb{P}\left\\{\left|N_{d,k}^{\overline{G}}(u)\right|\geq
2^{{(k-1)(\beta-2)}+1}\kappa^{d}n^{\gamma(3-\beta)d}\right\\}\leq$
$\displaystyle(4^{d-1}-1)\cdot n^{-4}+4^{d-1}\cdot n^{-4}=(2\cdot
4^{d-1}-1)n^{-4}.$ (44)

Combining (42), (43) and (44) with an union bound, we prove that (40) holds
for any $1\leq k\leq K$ and $1\leq d\leq D$.

∎

####  B.2.3 Proof of Lemma 3

Note that

$\displaystyle N_{D,k}^{\overline{G}_{1}}(u)\cap
N_{D,k}^{\overline{G}_{2}}(v)$
$\displaystyle\subset\left(\Gamma_{D,k}^{\overline{G}_{1}}(u)\cup
N_{D-1,k}(u,v)\right)\cap\left(\Gamma_{D,k}^{\overline{G}_{2}}(v)\cup
N_{D-1,k}(u,v)\right)$
$\displaystyle=\left(\Gamma_{D,k}^{\overline{G}_{1}}(u)\cap\Gamma_{D,k}^{\overline{G}_{2}}(v)\right)\cup
N_{D-1,k}(u,v),$ (45)

where $N_{D-1,k}(u,v)=N_{D-1,k}^{\overline{G}_{1}}(u)\cup
N_{D-1,k}^{\overline{G}_{2}}(v)$. Since we have already obtained the upper
bounds of $\left|N_{D-1,k}^{G_{1}}(u)\right|$ and
$\left|N_{D-1,k}^{G_{2}}(v)\right|$ by Lemma 14 by letting $\overline{G}$ to
be either $\overline{G}_{1}$ or $\overline{G}_{2}$, it remains to bound from
above
$\left|\Gamma_{D,k}^{\overline{G}_{1}}(u)\cap\Gamma_{D,k}^{\overline{G}_{2}}(v)\right|$,
which is done in the following lemma.

######  Lemma 15.

Suppose $\gamma$ and $D$ are chosen such that condition (10) holds. Fix any
two distinct vertices $u,v\in\overline{P}_{1}$, for all $1\leq d\leq D$,
$k=1,\ldots,K$, and sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\leq\Psi(d,k)\right\\}\geq
1-\frac{2\cdot 4^{d}}{3}\cdot n^{-4},$ (46)

where

$\Psi(d,k)=\frac{\kappa^{2}\Gamma_{\max}^{2}(d-1,1)n^{\gamma(5-\beta)}}{2^{(k-1)(3-\beta)}Cn}+\frac{6\Gamma_{\max}(d-1,1)\log
n}{2^{(k-1)(2-\beta)}}$

with $\Gamma_{\max}(d-1,1)=\kappa^{d-1}n^{\gamma(3-\beta)(d-1)}$ as defined in
(38) and
$\kappa=\frac{(1+2\delta)^{2}2^{5-\beta}C}{(2^{3-\beta}-1)\overline{w}}$.

######  Remark 3.

We provide an intuitive explanation on $\Psi(d,k).$ Analogous to Remark 1,
there are two extreme cases in which a vertex $i$ in $P_{k}$ becomes a common
$d$-hop neighbor of $(u,v)$. One case is that $i$ connects to some $(d-1)$-hop
neighbor of $u$ and $v$, respectively. Recall that $\Gamma_{\max}(d-1,l)$ is
an upper bound of its $(d-1)$-hop neighbors in $P_{l}$ by Lemma 14. Thus, a
vertex $i$ in $P_{k}$ connects to at least one $(d-1)$-hop neighbor of $u$
with probability at most
$\sum_{l=1}^{K}\Gamma_{\max}(d-1,l)\frac{\alpha_{k}\alpha_{l}}{n\overline{w}}\approx\Gamma_{\max}(d-1,1)\alpha_{k}n^{\gamma-1}$,
where the approximation holds because $l=1$ is the dominating term in the
summation. Moreover, there are $\Theta(n\alpha_{k}^{1-\beta})$ vertices in the
slice $P_{k}$. Thus, for a fake pair $(u,v)$, its number of such common
$d$-hop neighbors in $P_{k}$ is about
$\Gamma_{\max}^{2}(d-1,1)n^{2\gamma-1}\alpha_{k}^{3-\beta}$, which gives rise
to the first term of $\Psi(d,k).$ The other extreme case is that $i$ is a
$(d-1)$-hop neighbor of some common neighbor of $(u,v)$. As stated in Remark
1, we can bound from above
$\left|\Gamma_{1}^{\overline{G}_{1}}(u)\cap\Gamma_{1}^{\overline{G}_{2}}(v)\right|$
by $\log n$. Then, the vertex $i$ connects to at least one $(d-2)$-hop
neighbor of a given vertex in
$\Gamma_{1}^{\overline{G}_{1}}(u)\cap\Gamma_{1}^{\overline{G}_{2}}(v)$ with
probability at most
$\sum_{l=1}^{K}\Gamma_{\max}(d-2,l)\frac{\alpha_{k}\alpha_{l}}{n\overline{w}}\approx\Gamma_{\max}(d-2,1)\alpha_{k}n^{\gamma-1}$.
Again, there are $\Theta(n\alpha_{k}^{1-\beta})$ vertices in the slice
$P_{k}$. Thus, the number of such common $d$-hop neighbors in $P_{k}$ is about
$\Gamma_{\max}(d-2,1)\alpha_{k}^{2-\beta}n^{\gamma}\log n\approx
2^{(k-1)(\beta-2)}\Gamma_{\max}(d-1,1)\log n$, which gives rise to the second
term of $\Psi(d,k).$

Before proving Lemma 15, we first show how to apply Lemma 15 to prove Lemma 3.
combining (45), (39), and (46) yields that

$\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\leq\Psi(d,k)+2N_{\max}(d-1,k)\right\\}>1-n^{-4+o(1)}.$

Next we set $d=D$ and sum over $k$ for all the slices $P_{k}$ with weight at
most $\frac{15}{s}\log n$, i.e., $\alpha_{k}\leq\frac{15}{s}\log n$. In
particular, we have $k\geq
k_{0}\triangleq\lfloor\log_{2}(\frac{n^{\gamma}s}{15\log n})\rfloor$ and

$\displaystyle\sum_{k=k_{0}}^{K}\Psi(D,k)+2N_{\max}(D-1,k)$
$\displaystyle\leq$
$\displaystyle\sum_{k=k_{0}}^{K}\frac{\kappa^{2}\Gamma_{\max}^{2}(D-1,1)n^{\gamma(5-\beta)}}{2^{(k-1)(3-\beta)}Cn}+\frac{\Gamma_{\max}(D-1,1)}{2^{(k-1)(2-\beta)}}6\log
n+\frac{4\kappa^{D-1}n^{\gamma(3-\beta)(D-1)}}{2^{(k-1)(2-\beta)}}$
$\displaystyle\leq$
$\displaystyle\frac{2^{3-\beta}\kappa^{2}\Gamma_{\max}^{2}(D-1,1)n^{\gamma(5-\beta)}}{(2^{3-\beta}-1)2^{(k_{0}-1)(3-\beta)}Cn}+\frac{2^{\beta-2}}{2^{\beta-2}-1}\frac{\Gamma_{\max}(D-1,1)}{2^{(K-1)(2-\beta)}}6\log
n+\frac{2^{\beta-2}}{2^{\beta-2}-1}\frac{4\kappa^{D-1}n^{\gamma(3-\beta)(D-1)}}{2^{(K-1)(2-\beta)}}$
$\displaystyle\leq$
$\displaystyle\frac{2^{3-\beta}\kappa^{2D}n^{2\gamma((3-\beta)(D-1)+1)}}{(2^{3-\beta}-1)Cn}\left(\frac{15}{s}\log
n\right)^{3-\beta}+\frac{2^{\beta-2}}{2^{\beta-2}-1}\kappa^{D-1}n^{(\gamma(3-\beta)(D-2)+1)}(4+6\log
n)=\Psi_{\max},$

where $\Psi_{\max}$ is given in (19). Thus, we prove the desired conclusion
(19).

Next we present the proof of Lemma 15.

###### Proof of Lemma 15.

Fix two distinct vertices $u,v$ in $\overline{P}_{1}$, we study their common
$d$-hop neighborhood from $d=1$.

##### For $d=1$:

For each vertex $i\in\overline{P}_{k}$, define an indicator variable

$x_{i}^{k}={\mathbf{1}_{\left\\{{i\in\Gamma_{1}^{\overline{G}_{1}}(u)\cap\Gamma_{1}^{\overline{G}_{2}}(v)}\right\\}}}.$

In other words, $x_{i}^{k}=1$ if $i$ is connected to $u$ in $\overline{G}_{1}$
and $v$ in $\overline{G}_{2}$, and $x_{i}^{k}=0$ otherwise. Then, we have
$\left|\Gamma_{1,k}^{\overline{G}_{1}}(u)\cap\Gamma_{1,k}^{\overline{G}_{2}}(v)\right|=\sum_{i\in\overline{P}_{k}}x_{i}^{k}$.
Since $w_{u},w_{v}\in[(1-2\delta]\alpha_{1},(1+2\delta)\alpha_{0}]$, it
follows that

$\displaystyle\mathbb{P}\left\\{x_{i}^{k}=1\right\\}\leq\left((1+2\delta)^{2}\frac{\alpha_{k-1}\alpha_{0}}{n\overline{w}}\right)^{2}\triangleq
p_{\max}^{k}.$

Hence, we have

$\left|\Gamma_{1,k}^{\overline{G}_{1}}(u)\cap\Gamma_{1,k}^{\overline{G}_{2}}(v)\right|\overset{s.t.}{\leq}{\rm
Binom}\left(\left|\overline{P}_{k}\right|,p_{\max}^{k}\right).$

Recall $n_{k}=Cn\alpha^{1-\beta}_{k-1}$ in view of (28) and
$\left|\overline{P}_{k}\right|\leq 2n_{k}$ in view of (30). Hence,

$2n_{k}p_{\max}^{k}=(1+2\delta)^{4}\frac{2C\alpha_{k-1}^{3-\beta}n^{2\gamma}}{\overline{w}^{2}n}.$

Hence, we apply Lemma 6 with $\lambda=4\log n$, and get

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1,k}^{\overline{G}_{1}}(u)\cap\Gamma_{1,k}^{\overline{G}_{2}}(v)\right|\geq\frac{4(1+2\delta)^{4}C\alpha_{k-1}^{3-\beta}n^{2\gamma}}{\overline{w}^{2}n}+\frac{16}{3}\log
n\right\\}\leq n^{-4}.$

Since $\Gamma_{\max}(0,1)=1$, we have
$\Psi(1,k)=\frac{\kappa^{2}\alpha_{k-1}^{3-\beta}n^{2\gamma}}{Cn}+6\log n$.
Thus, (46) holds for $d=1$.

##### For $2\leq d\leq D$:

We first count the $d$-hop neighbors conditional on the $(d-1)$-hop
neighborhood of $u$ and $v$. We use $\Omega_{d}^{*}$ to denote the event that
$\Omega_{d-1}$ with $\overline{G}=\overline{G}_{1},\overline{G}_{2}$ hold, and
for all $k=1,\ldots,K$,

$\displaystyle\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\leq\Psi(d,k),$

with $\Psi(d,k)$ defined in Lemma 15.

Conditioning on $\Omega_{d-1}^{*}$, note that there are two possible cases
under which each true pair $(i,i)$ becomes a common $d$-hop neighbor of
$(u,v)$. One case is that $i$ connects to some common $(d-1)$-hop neighbors of
$(u,v)$ in both $\overline{G}_{1}$ and $\overline{G}_{2}$. The other case is
that $i$ connects to different $(d-1)$-hop neighbors of $(u,v)$ in
$\overline{G}_{1}$ and $\overline{G}_{2}$, respectively.

For each vertex $i\in\overline{P}_{k}\setminus N_{D-1}(u,v)$, define two
indicator variables

$\displaystyle y_{i}^{k}=$
$\displaystyle{\mathbf{1}_{\left\\{{i\in\Gamma_{d}^{\overline{G}_{1}}(u),i\in\Gamma_{d}^{\overline{G}_{2}}(v)}\right\\}}},$
$\displaystyle z_{i}^{k}=$ $\displaystyle{\mathbf{1}_{\left\\{{\exists
j\in\Gamma_{d-1}^{\overline{G}_{1}}(u)\cap\Gamma_{d-1}^{\overline{G}_{2}}(v):\;i\in\Gamma_{1}^{\overline{G}_{1}}(j)}\right\\}}}.$

In other words, $y_{i}^{k}=1$ if $i$ is a $d$-hop neighbor of $u$ in
$\overline{G}_{1}$ and $v$ in $\overline{G}_{2}$, and $y_{i}^{k}=0$ otherwise.
Similarly, $z_{i}^{k}=1$ if $i$ is connected to at least one common
$(d-1)$-hop neighbor of $(u,v)$ in both $\overline{G}_{1}$ and
$\overline{G}_{2}$, and $z_{i}^{k}=0$ otherwise. Note that $z_{i}^{k}=1$
includes the case that $i$ connects to some common $(d-1)$-hop neighbors of
$(u,v)$ in both $\overline{G}_{1}$ and $\overline{G}_{2}$.

We first bound $\mathbb{P}\left\\{z_{i}^{k}=1|\Omega_{d-1}^{*}\right\\}$ from
above by

$\displaystyle\mathbb{P}\left\\{z^{k}_{i}=1\mid\Omega_{d-1}^{*}\right\\}\overset{(a)}{\leq}$
$\displaystyle\sum_{l=1}^{K}\mathbb{P}\left\\{\exists
j\in\Gamma_{d-1}^{\overline{G}_{1}}(u)\cap\Gamma_{d-1}^{\overline{G}_{2}}(v):i\in\Gamma_{1}^{\overline{G}_{1}}(j)\mid\Omega_{d-1}^{*}\right\\}$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle(1+2\delta)^{2}\sum_{l=1}^{K}\Psi(d-1,l)\frac{\alpha_{k-1}\alpha_{l-1}}{n\overline{w}}$
$\displaystyle\leq$
$\displaystyle\left(\frac{\kappa^{2}\Gamma_{\max}^{2}(d-2,1)n^{\gamma(7-\beta)}}{2^{k-1}Cn^{2}\overline{w}}+\frac{6\Gamma_{\max}(d-2,1)n^{2\gamma}\log
n}{2^{k-1}n\overline{w}}\right)\sum_{l=1}^{K}\frac{(1+2\delta)^{2}}{2^{(l-1)(3-\beta)}}$
$\displaystyle\overset{}{\leq}$
$\displaystyle\frac{\kappa^{2d-1}n^{2\gamma(3-\beta)(d-2)}n^{\gamma(7-\beta)}}{2^{k+1}C^{2}n^{2}}+\frac{6\kappa^{d-1}n^{\gamma((3-\beta)(d-2)+2)}\log
n}{2^{k+1}Cn}=\nu_{1},$

where $(a)$ holds due to the union bound; $(b)$ follows from the union bound
and event $\Omega_{d-1}^{*}$.

Then, the event $\\{y_{i}^{k}=1\\}\setminus\\{z_{i}^{k}=1\\}$ denotes the
event that $i$ connects to some vertex in
$\Gamma_{d-1,k}^{\overline{G}_{1}}(u)\setminus\Gamma_{d-1,k}^{\overline{G}_{2}}(v)$
and connects to some vertex in $\Gamma_{d-1,k}^{\overline{G}_{2}}(v)$
independently. Thus,
$\mathbb{P}\left\\{\\{y_{i}^{k}=1\\}\setminus\\{z_{i}^{k}=1\\}\mid\Omega_{d-1}^{*}\right\\}$
can be bounded by

$\displaystyle\mathbb{P}\left\\{\\{y_{i}^{k}=1\\}\setminus\\{z_{i}^{k}=1\\}\mid\Omega_{d-1}^{*}\right\\}$
$\displaystyle\leq$ $\displaystyle\mathbb{P}\left\\{\exists
j\in\Gamma_{d-1,k}^{\overline{G}_{1}}(u)\setminus\Gamma_{d-1,k}^{\overline{G}_{2}}(v):i\in\Gamma_{1}^{\overline{G}_{1}}(j)\mid\Omega_{d-1}^{*}\right\\}\mathbb{P}\left\\{\exists
j\in\Gamma_{d-1}^{\overline{G}_{2}}(v):i\in\Gamma_{1}^{\overline{G}_{2}}(j)\mid\Omega_{d-1}^{*}\right\\}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left\\{i\in\Gamma_{d}^{\overline{G}_{1}}(v)\mid\Omega_{d-1}^{*}\right\\}\mathbb{P}\left\\{i\in\Gamma_{d}^{\overline{G}_{2}}(v)\mid\Omega_{d-1}^{*}\right\\}$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\left(\frac{\kappa^{d}n^{\gamma((3-\beta)(d-1)+2)}}{2^{k+1}Cn}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{\kappa^{2d}n^{2\gamma(3-\beta)(d-2)}}{2^{2(k+1)}C^{2}n^{2}}n^{2\gamma(5-\beta)}=\nu_{2},$

where $(a)$ follows from a similar proof of (B.2.2).

When we compare the first term of $\nu_{1}$ and $\nu_{2}$, we have

$\frac{n^{2\gamma(3-\beta)(d-2)}}{n^{2}}n^{\gamma(7-\beta)}\ll\frac{n^{2\gamma(3-\beta)(d-2)}}{n^{2}}n^{2\gamma(5-\beta)},$

where the inequality follows from
$\frac{n^{\gamma(7-\beta)}}{n^{2\gamma(5-\beta)}}=n^{\gamma(\beta-3)}=o(1)$.

Thus, we have

$\displaystyle\mathbb{P}\left\\{y_{i}^{k}=1\mid\Omega_{d-1}^{*}\right\\}$
$\displaystyle\leq\nu_{1}+\nu_{2}\leq
2\nu_{2}+\frac{4\kappa^{d}n^{\gamma((3-\beta)(d-2)+2)}\log n}{2^{k}Cn}$
$\displaystyle\leq\frac{\kappa^{2d}n^{2\gamma(3-\beta)(d-1)}n^{4\gamma}}{3\cdot
2^{2(k-1)}C^{2}n^{2}}+\frac{4\kappa^{d}n^{\gamma((3-\beta)(d-2)+2)}\log
n}{2^{k}Cn}\triangleq\mu_{k}.$

Thus, conditional on $\Omega_{d-1}^{*}$, we have

$\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\overset{s.t.}{\leq}{\rm
Binom}\left(\left|\overline{P}_{k}\right|,\mu_{k}\right).$

Recall $n_{k}=Cn\alpha^{1-\beta}_{k-1}$ in view of (28) and
$\left|\overline{P}_{k}\right|\leq 2n_{k}$ in view of (30). Therefore, for
sufficiently large $n$,

$2n_{k}\mu_{k}=\frac{2\kappa^{2d}n^{2\gamma(3-\beta)(d-1)}n^{\gamma(5-\beta)}}{3\cdot
2^{(k-1)(3-\beta)}Cn}+\frac{4\kappa^{d-1}n^{\gamma(3-\beta)(d-1)}\log
n}{2^{(k-1)(2-\beta)}}\leq\frac{2}{3}\Psi(d,k).$

We then apply Chernoff Bound with $\eta=\frac{1}{2}$ and get

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\geq\Psi_{\max}(d,k)\mid\Omega_{d-1}^{*}\right\\}\leq
n^{-4}.$

##### Induction:

Finally, we prove (46) by induction.

For $d=1$, we have proved that (46) holds.

Suppose (46) holds for $d-1$, then taking the union bound yields that

$\displaystyle\mathbb{P}\left\\{\Omega_{d-1}^{*c}\right\\}\leq$ $\displaystyle
2\cdot\mathbb{P}\left\\{\Omega_{d-1}^{c}\right\\}+\mathbb{P}\left\\{\left|\Gamma_{d-1,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d-1,k}^{\overline{G}_{2}}(v)\right|\geq\Psi_{\max}(d-1,k)\right\\}$
$\displaystyle\leq$ $\displaystyle 2(4^{d-1}-1)n^{-4}+\frac{2\cdot
4^{d-1}}{3}n^{-4}=\left(\frac{2\cdot 4^{d}}{3}-1\right)\cdot n^{-4}.$

Thus, we have

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\geq\Psi_{\max}(d,k)\right\\}$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left\\{\Omega_{d-1}^{*c}\right\\}+\mathbb{P}\left\\{\left|\Gamma_{d,k}^{\overline{G}_{1}}(u)\cap\Gamma_{d,k}^{\overline{G}_{2}}(v)\right|\geq\Psi_{\max}(d,k)\mid\Omega_{d-1}^{*}\right\\}$
$\displaystyle\leq$ $\displaystyle\left(\frac{2\cdot 4^{d}}{3}-1\right)\cdot
n^{-4}+n^{-4}\leq\frac{2\cdot 4^{d}}{3}\cdot n^{-4}.$

∎

####  B.2.4 Proof of Lemma 4

The main idea of the proof is to bound the number of $D$-hop witnesses for
both true pairs and fake pairs in the first slice, using the bounds to the
number of the $D$-hop neighbors established in Lemma 2 and Lemma 3.

Recall that in Algorithm 1, we select the set $\widehat{{\mathcal{S}}}$ of
low-degree seeds. Let $\widehat{S}=\\{i:(i,i)\in\widehat{{\mathcal{S}}}\\}$.
To circumvent the dependency between $\widehat{S}$ and the graphs $G_{1}$ and
$G_{2}$, we will introduce $\underline{S}$ and $\overline{S}$ such that they
are independent from graphs and
$\underline{S}\subset\widehat{S}\subset\overline{S}$ with high probability. To
this end, we define an event ${\mathcal{E}}$ such that

$\\{i:w_{i}\leq c\\}\subset\\{i:|\Gamma_{1}^{G_{1}}(i)|\leq 5\log
n,|\Gamma_{1}^{G_{2}}(i)|\leq 5\log n\\}\subset\\{i:w_{i}\leq\frac{15}{s}\log
n\\}.$

For any $i$ with $w_{i}\leq c$,
$\mathbb{E}\left[|\Gamma_{1}^{G_{1}}(i)|\right]=cs$. Thus, applying Lemma 6
with $\lambda=3\log n$ yields

$\mathbb{P}\left\\{|\Gamma_{1}^{G_{1}}(i)|\geq 5\log
n\right\\}\leq\mathbb{P}\left\\{|\Gamma_{1}^{G_{i}}(i)|\geq 2cs+4\log
n\right\\}\leq n^{-3}.$

Taking a union bound over $i$ gives $\mathbb{P}\left\\{\\{i:w_{i}\leq
c\\}\subset\\{i:|\Gamma_{1}^{G_{1}}(i)|\leq 5\log
n,|\Gamma_{1}^{G_{2}}(i)|\leq 5\log n\\}\right\\}\geq 1-n^{-2+o(1)}$.

For any $i$ with $w_{i}>\frac{15}{s}\log n$,
$\mathbb{E}\left[|\Gamma_{1}^{G_{1}}(i)|\right]=15\log n$. we apply Chernoff
Bound in Theorem 3 with $\eta=2/3$ and have

$\mathbb{P}\left\\{|\Gamma_{1}^{G_{1}}(i)|\leq 5\log
n\right\\}\leq\mathbb{P}\left\\{|\Gamma_{1}^{G_{i}}(i)|\leq\left(1-\frac{2}{3}\right){15}\log
n\right\\}\leq n^{-3}.$

Thus, we have

$\displaystyle\mathbb{P}\left\\{\\{i:|\Gamma_{1}^{G_{1}}(i)|\leq 5\log
n,|\Gamma_{1}^{G_{2}}(i)|\leq 5\log n\\}\subset\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right\\}$ $\displaystyle=$
$\displaystyle\mathbb{P}\left\\{\\{i:w_{i}>\frac{15}{s}\log
n\\}\subset\\{i:|\Gamma_{1}^{G_{1}}(i)|>5\log n,|\Gamma_{1}^{G_{2}}(i)|>5\log
n\\}\right\\}=1-n^{-2+o(1)}.$

Thus, $\mathbb{P}\left\\{{\mathcal{E}}\right\\}\geq 1-n^{-2+o(1)}.$ On event
${\mathcal{E}}$, we have

$\underline{S}\triangleq\\{i:w_{i}\leq c\\}\cap
S\subset\widehat{S}\subset\\{i:w_{i}\leq\frac{15}{s}\log n\\}\cap
S\triangleq\overline{S},$

where $S=\\{i:(i,i)\in{\mathcal{S}}\\}$ denotes the set of vertices selected
as the initial seed set ${\mathcal{S}}$. Note that crucially the initial seeds
in ${\mathcal{S}}$ are selected among all true pairs with probability
$\theta$, independently from everything else. Thus $\underline{S}$ and
$\overline{S}$ are independent from graphs. As a consequence, to bound from
below (resp. above) the number of $D$-hop witnesses for the true (resp. fake)
pair, it suffices to consider their common $D$-hop neighbors in
$\underline{S}$ (resp. $\overline{S}$).

More specifically, let us first consider the true pairs. Fix any vertex $u\in
P_{1}$. Let
$\Lambda(u)=\Gamma_{D}^{\underline{G}_{1}}(u)\cap\Gamma_{D}^{\underline{G}_{2}}(u)\setminus\left(N_{D-1}^{\overline{G}_{1}}(u)\cap
N_{D-1}^{\overline{G}_{2}}(u)\right)$. Define event

$\displaystyle{\mathcal{A}}_{u}=\left\\{\left|\Lambda(u)\cap\underline{S}\right|>\frac{3}{5}\Gamma_{\min}\theta\right\\},\text{
where }\Gamma_{\min}=\frac{1}{2}\left(\frac{C\cdot
s^{2}}{12\cdot\overline{w}}\right)^{D}n^{\gamma((3-\beta)(D-1)+1)}.$

Note that due to assumption (10) and $n^{\gamma(3-\beta)}\gg\log n$ for
sufficiently large $n$, $N_{\max}\leq\frac{1}{10}\Gamma_{\min}$. Hence it
follows from Lemma 2 that

$\mathbb{P}\left\\{\left|\Lambda(u)\cap\\{i:w_{i}\leq
c\right|<\frac{4}{5}\Gamma_{\min}\right\\}\leq n^{-4+o(1)}.$

Because the seeds ${\mathcal{S}}$ are selected among all true pairs with
probability $\theta$, independently from everything else, we have

$\left|\Lambda(u)\cap\underline{S}\right|\sim{\rm
Binom}\left(\left|\Lambda(u)\cap\\{i:w_{i}\leq c\\}\right|,\theta\right).$

Then, we apply Chernoff Bound in Theorem 3 with $\eta=\frac{1}{4}$ and get

$\displaystyle\mathbb{P}\left\\{{\mathcal{A}}_{u}^{c}\right\\}\leq$
$\displaystyle\mathbb{P}\left\\{\left|\Lambda(u)\cap\\{i:w_{i}\leq
c\\}\right|<\frac{4}{5}\Gamma_{\min}\right\\}+\mathbb{P}\left\\{{\mathcal{A}}_{u}^{c}\,\bigg{|}\,\left|\Lambda(u)\cap\\{i:w_{i}\leq
c\\}\right|\geq\frac{4}{5}\Gamma_{\min}\right\\}$
$\displaystyle\overset{}{\leq}$ $\displaystyle
n^{-4+o(1)}+\mathbb{P}\left\\{{\rm
Binom}\left(\Gamma_{\min},\theta\right)\leq\frac{3}{5}\Gamma_{\min}\theta\right\\}$
$\displaystyle\leq$ $\displaystyle
n^{-4+o(1)}+\exp\left(-\frac{1}{40}\Gamma_{\min}\theta\right)\overset{(a)}{\leq}n^{-4+o(1)},$

where $(a)$ holds due to assumption (11). Let ${\mathcal{A}}=\cap_{u\in
P_{1}}{\mathcal{A}}_{u}$. It follows from the union bound that
$\mathbb{P}\left\\{{\mathcal{A}}\right\\}\leq n^{-3+o(1)}.$

We next consider the fake pairs. Fix any two distinct vertices
$u,v\in\overline{P}_{1}$. Define an event

$\displaystyle{\mathcal{B}}_{uv}=\left\\{\left|N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(v)\cap\overline{S}\right|\leq\frac{1}{2}\Gamma_{\min}\theta\right\\}.$

Note that due to the assumption (10) and $n^{\gamma(3-\beta)}\gg\log n$ for
sufficiently large $n$,

$\Psi_{\max}\leq\frac{\kappa^{2D}}{\left(\frac{Cs^{2}}{12\cdot\overline{w}}\right)^{D}}\left(\frac{2^{3-\beta}n^{\gamma((3-\beta)(D-1)+1)}}{(2^{3-\beta}-1)Cn}\left(\frac{15}{s}\log
n\right)^{3-\beta}+\frac{2^{\beta-2}(4+6\log
n)}{(2^{\beta-2}-1)n^{\gamma(3-\beta)}}\right)\Gamma_{\min}\leq\frac{1}{4}\Gamma_{\min}.$

Hence, it follows from Lemma 3 that

$\mathbb{P}\left\\{\left|N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(v)\cap\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right|>\frac{1}{4}\Gamma_{\min}\right\\}\leq n^{-4+o(1)}.$

Since the seeds ${\mathcal{S}}$ are selected among all true pairs with
probability $\theta$ independently, we have

$\left|\Gamma_{D}^{\overline{G}_{1}}(u)\cap\Gamma_{D}^{\overline{G}_{2}}(v)\cap\overline{S}\right|\sim{\rm
Binom}\left(\left|N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(v)\cap\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right|,\theta\right).$

Then, we apply Chernoff Bound in Theorem 3 with $\eta=1$ and get

$\displaystyle\mathbb{P}\left\\{{\mathcal{B}}_{uv}^{c}\right\\}\leq$
$\displaystyle\mathbb{P}\left\\{\left|N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(v)\cap\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right|>\frac{1}{4}\Gamma_{\min}\right\\}$
$\displaystyle+\mathbb{P}\left\\{{\mathcal{E}}_{uv}^{c}\,\bigg{|}\,\left|N_{D}^{\overline{G}_{1}}(u)\cap
N_{D}^{\overline{G}_{2}}(u)\cap\\{i:w_{i}\leq\frac{15}{s}\log
n\\}\right|\leq\frac{1}{4}\Gamma_{\min}\right\\}$
$\displaystyle\overset{}{\leq}$ $\displaystyle
n^{-4+o(1)}+\mathbb{P}\left\\{{\rm
Binom}\left(\frac{1}{4}\Gamma_{\min},\theta\right)\leq\frac{1}{2}\Gamma_{\min}\theta\right\\}$
$\displaystyle\leq$ $\displaystyle
n^{-4+o(1)}+\exp\left(-\frac{1}{12}\Gamma_{\min}\theta\right)\overset{(a)}{\leq}n^{-4+o(1)},$

where $(a)$ holds due to assumption (11). Let
${\mathcal{B}}=\cap_{u,v\in\overline{P}_{1}:u\neq v}{\mathcal{B}}_{uv}$. It
follows from the union bound that
$\mathbb{P}\left\\{{\mathcal{B}}^{c}\right\\}\leq n^{-2+o(1)}.$

Finally, we define event ${\mathcal{C}}$ such that

$\underline{G}_{j}\subset\widehat{G}_{j}\subset\overline{G}_{j},\quad\forall
j=1,2\quad\text{ and }\quad
P_{1}\subset\widehat{P}_{1}\subset\overline{P}_{1}.$

It follows from Lemma 1 that $\mathbb{P}\left\\{{\mathcal{C}}\right\\}\geq
1-n^{-4+o(1)}.$ Taking the union bound, we have

$\mathbb{P}\left\\{{\mathcal{A}}\cap{\mathcal{B}}\cap{\mathcal{C}}\cap{\mathcal{E}}\right\\}\geq
1-n^{-3+o(1)}-n^{-2+o(1)}-2n^{-4+o(1)}\geq 1-n^{-2+o(1)}.$

It remains to verify that on the event
${\mathcal{A}}\cap{\mathcal{B}}\cap{\mathcal{C}}\cap{\mathcal{E}}$,
${\mathcal{R}}_{1}$ contains all true pairs in $Q_{1}$ and no fake pairs in
$\widehat{Q}_{1}$.

Recall that we uses seeds in $\widehat{{\mathcal{S}}}$ and count the $D$-hop
witnesses in $\widehat{G}_{1}$ and $\widehat{G}_{2}$ for all candidate vertex
pairs in $\widehat{Q}_{1}$ in Step 4 of Algorithm 1. On event
${\mathcal{A}}\cap{\mathcal{C}}\cap{\mathcal{E}}$,
$\Lambda(u)\subset\Gamma^{\widehat{G}_{1}}_{D}(u)\cap\Gamma^{\widehat{G}_{2}}_{D}(u)$
and the minimum number of $D$-hop witnesses among all true pairs $(u,u)$ in
$Q_{1}$ is lower bounded by $\frac{3}{5}\Gamma_{\min}\theta$. On event
${\mathcal{B}}\cap{\mathcal{C}}\cap{\mathcal{E}}$,
$\Gamma^{\widehat{G}_{1}}_{D}(u)\cap\Gamma^{\widehat{G}_{2}}_{D}(v)\subset
N^{\overline{G}_{1}}_{D}(u)\cap N^{\overline{G}_{2}}_{D}(v)$ the maximum
number of $D$-hop witnesses among all fake pairs $(u,v)$ in $\widehat{Q}_{1}$
is upper bounded by $\frac{1}{2}\Gamma_{\min}\theta$. Thus, GMWM with
threshold $\tau_{1}=\frac{1}{2}\Gamma_{\min}\theta$ outputs
${\mathcal{R}}_{1}$, which contains all true pairs in $Q_{1}$ and no fake
pairs in $\widehat{Q}_{1}$.

####  B.2.5 Proof of Lemma 5

Fix a vertex $u\in P_{k}$. For each vertex $i\in P_{k-1}$, let $x_{i}$ be a
binary random variable such that $x_{i}=1$ if $i$ connects to $u$ both in
$G_{1}$ and $G_{2}$, and $x_{i}=0$ otherwise. Then,
$\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(u)\cap
P_{k-1}\right|=\sum_{i\in P_{k-1}}x_{i}$ and $x_{i}$’s are independent.
Moreover, we have

$\displaystyle\mathbb{P}\left\\{x_{i}=1\right\\}\geq\frac{\alpha_{k}\alpha_{k-1}}{n\overline{w}}s^{2}.$

Therefore, applying Chernoff Bound in Theorem 3 with $\eta=\frac{1}{2}$ yields
that

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{{G}_{1}}(u)\cap\Gamma_{1}^{{G}_{2}}(u)\cap
P_{k-1}\right|\leq\frac{C\alpha_{k-1}^{3-\beta}s^{2}}{16\overline{w}}\right\\}\leq\mathbb{P}\left\\{{\rm
Binom}\left(n_{k-1},\frac{\alpha_{k}\alpha_{k-1}}{n\overline{w}}s^{2}\right)\leq\frac{C\alpha_{k-1}^{3-\beta}s^{2}}{2^{\beta+1}\overline{w}}\right\\}\leq
n^{-3},$

where the last inequality holds because
$n_{k-1}\frac{\alpha_{k}\alpha_{k-1}}{n\overline{w}}s^{2}=\frac{C\alpha_{k-1}^{3-\beta}s^{2}}{2^{\beta}\overline{w}}\geq
24\log n$ in view of
$\left(\alpha_{k^{*}}\right)^{3-\beta}\geq\frac{192\overline{w}\log
n}{Cs^{2}}$.

####  B.2.6 Proof of Lemma 6

Fix a pair of two distinct vertices $u,v\in\overline{P}_{k}$. For each vertex
$i\in\overline{P}_{k-1}$, let $x_{i}$ be a binary random variable such that
$x_{i}=1$ if $i$ is connected to $u$ in $G_{1}$ and $v$ in $G_{2}$, and
$x_{i}=0$ otherwise. Since the event that $i$ is connected to $u$ is
independent of the event that $i$ is connected to $v$, we have

$\displaystyle\mathbb{P}\left\\{x_{i}=1\right\\}\leq\left((1+2\delta)^{2}\frac{\alpha_{k-1}\alpha_{k-2}}{n\overline{w}}s\right)^{2}=\frac{4(1+2\delta)^{4}\alpha_{k-1}^{4}s^{2}}{n^{2}\overline{w}^{2}}\triangleq
p_{\max}.$

Moreover, $x_{i}$’s are independent. Therefore,
$\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(v)\cap\overline{P}_{k-1}\right|\overset{s.t.}{\leq}{\rm
Binom}\left(\left|\overline{P}_{k-1}\right|,p_{\max}\right)$. Recall
$n_{k-1}=Cn\alpha^{1-\beta}_{k-2}$ in view of (28) and
$\left|\overline{P}_{k-1}\right|\leq 2n_{k-1}$ in view of (30). Thus, we apply
Lemma 6 with $\lambda=4\log n$, and get

$\displaystyle\mathbb{P}\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(v)\cap\overline{P}_{k-1}\right|\geq\frac{8(1+2\delta)^{4}C\alpha_{k-1}^{5-\beta}s^{2}}{\overline{w}^{2}n}+\frac{16}{3}\log
n\right\\}\leq n^{-4}.$

####  B.2.7 Proof of Lemma 7

The proof is divided into two parts. The first part is to identify a set of
“good” events whose intersection holds with high probability. The second part
provides a deterministic argument, showing that on the intersection of these
good events, the $1$-hop algorithm successfully matches slice $k$ for all
$2\leq k\leq k^{*}.$

First, we identify a good event under which the number of common $1$-hop
neighbors of a true pair is large. More precisely, for any vertex $u\in
P_{k}$, define event

$\displaystyle\mathcal{A}_{k}(u)=\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(u)\cap
P_{k-1}\right|\geq\xi_{k}\right\\},\quad\text{ where
}\;\xi_{k}\triangleq\frac{C\alpha_{k-1}^{3-\beta}s^{2}}{16\overline{w}},$

and ${\mathcal{A}}=\cap_{2\leq k\leq k^{*}}\cap_{u\in
P_{k}}{\mathcal{A}}_{k}(u)$. By Lemma 5 and union bound, we have
$\mathbb{P}\left\\{{\mathcal{A}}^{c}\right\\}\leq n^{-2+o(1)}.$

Second, we determine a good event under which the number of common $1$-hop
neighbors of a fake pair is small. More formally, for any pair of distinct
vertices $u,v\in\overline{P}_{k}$, define event

$\displaystyle\mathcal{B}_{k}(u,v)=\left\\{\left|\Gamma_{1}^{G_{1}}(u)\cap\Gamma_{1}^{G_{2}}(v)\cap\overline{P}_{k-1}\right|\leq\zeta_{k}\right\\},\quad\text{
where
}\;\zeta_{k}\triangleq\frac{8(1+2\delta)^{4}C\alpha_{k-1}^{5-\beta}s^{2}}{\overline{w}^{2}n}+\frac{16}{3}\log
n,$

and ${\mathcal{B}}=\cap_{2\leq k\leq k^{*}}\cap_{u,v\in\overline{P}_{k}:u\neq
v}{\mathcal{B}}_{k}(u,v)$. By Lemma 6 and union bound, we have
$\mathbb{P}\left\\{{\mathcal{B}}^{c}\right\\}\leq n^{-3+o(1)}.$

Third, we define an event ${\mathcal{C}}=\cap_{2\leq k\leq
k^{*}}\left\\{Q_{k}\subset\widehat{Q}_{k}\subset\overline{Q}_{k}\right\\}.$ By
Lemma 1 and union bound, we have
$\mathbb{P}\left\\{{\mathcal{C}}^{c}\right\\}\leq n^{-4+o(1)}.$

Finally, we let ${\mathcal{F}}$ denote the event that the first slice is
successfully matched, i.e., ${\mathcal{R}}_{1}$ contains all true pairs in
$Q_{1}$ and no fake pairs in $\widehat{Q}_{1}$. By Lemma 4,
$\mathbb{P}\left\\{{\mathcal{F}}^{c}\right\\}\leq n^{-1.5+o(1)}.$

Combining the above, it follows that

$\mathbb{P}\left\\{{\mathcal{A}}\cap{\mathcal{B}}\cap{\mathcal{C}}\cap{\mathcal{F}}\right\\}\geq
1-n^{-2+o(1)}-n^{-3+o(1)}-n^{-4+o(1)}-n^{-1.5+o(1)}\geq 1-n^{-1.5+o(1)}.$

It remains to verify on the event
${\mathcal{A}}\cap{\mathcal{B}}\cap{\mathcal{C}}\cap F$, ${\mathcal{R}}_{k}$
contains all true pairs in ${Q}_{k}$ and no fake pairs in $\widehat{Q}_{k}$
for all $1\leq k\leq k^{*}$. We prove this by induction. The base case with
$k=1$ follows from the definition of ${\mathcal{F}}.$ Assume the induction