Matchability of heterogeneous networks pairs

arXiv:1705.02294v2 [math.ST] 6 Mar 2018

Vince Lyzinski† and Daniel L. Sussman‡
†

Department of Mathematics and Statistics, University of Massachusetts Amherst
‡ Department

of Mathematics and Statistics, Boston University

March 8, 2018

Abstract
We consider the problem of graph matchability in non-identically distributed networks. In a general class of edge-independent networks, we demonstrate that graph
matchability is almost surely lost when matching the networks directly, and is almost
perfectly recovered when first centering the networks using Universal Singular Value
Thresholding before matching. These theoretical results are then demonstrated in both
real and synthetic simulation settings. We also recover analogous core-matchability
results in a very general core-junk network model, wherein some vertices do not correspond between the graph pair.

1

Introduction and Background

The graph matching problem seeks to find an alignment between the vertex sets of two graphs
that best preserves common structure across graphs. At its simplest, it can be formulated as
follows: Given two adjacency matrices A and B corresponding to n-vertex graphs, the graph
matching problem seeks to minimize kA − P BP T kF over permutation matrices P ; i.e., the
graph matching problem seeks a relabeling of the vertices of B that minimizes the number of
induced edge disagreements between A and P BP T . Variants and extensions of this problem
have been extensively studied in the literature, with applications across areas as diverse
as biology and neuroscience [39, 7], computer vision [31, 12, 22], and pattern recognition
[20, 32, 40], among others. For a survey of many of the recent applications and approaches
to the graph matching problem, see the sequence of survey papers [10, 14, 11]. While recent
1

results [3] have whittled away at the complexity of the related graph isomorphism problem—
determining whether a permutation matrix P exists satisfying A = P BP T — at its most
general, where A and B are allowed to be weighted and directed, the graph matching problem
is known to be NP-hard. Indeed, in this case, the graph matching problem is equivalent to
the notoriously difficult quadratic assignment problem [23, 5].
Recently, there has been a flurry of activity studying the closely related problem of graph
matchability [30, 18, 26, 27, 25, 30, 24]: Given a latent alignment between the vertex sets
of two graphs, can graph matching uncover this alignment in the presence of shuffled vertex
labels? This problem arises in a variety of contexts, from network de-anonymization to
the graph analogue of signal recovery in the presence of an errorful channel, to name a
few. Many existing results are concerned with recovering a latent alignment present across
random graph models where each of A and B have identical marginal distributions.
While this has served to establish a novel theoretical understanding of the matchability
problem, this assumption is often not met in real data. Often, the graph topologies can differ
significantly even amongst vertices that correspond to the same entity across networks. Social
networks offer a compelling example of this, where matching across different social network
platforms (or within a single time varying social network) requires the understanding that not
all users will be behaving homogeneously in time or across different network platforms [21].
Both theoretically (see Example 4) and practically (see, for example, [7]), this distributional
heterogeneity can have a deleterious effect on graph matchability.
Herein, we propose to ameliorate the effect of A and B not being identically distributed
by means of a Universal Singular Value Thresholding [6] (USVT) centering preprocessing
step. Working in a general correlated edge-independent random graph model (see Definition
1), we theoretically demonstrate that USVT centering asymptotically almost surely recovers
the matchability for all but a vanishing fraction of the networks (see Theorem 7). In addition,
we recover analogous result (see Theorem 12) in the setting in which only a fraction of the
vertices possess a true correspondence across networks, generalizing and extending the results
of [30, 18, 37] to this more general model setting.
This centering step is practically implementable on even very large networks and is
demonstrated to have a significant positive impact on graph matchability in both real and
synthetic data settings (see Section 3). While the results contained herein do not guarantee that any particular algorithm will be able to perfectly (or almost perfectly) align any
given networks after USVT centering, they provide a theoretical foundation for subsequently
studying algorithmic effectiveness. Indeed, they ensure that with high probability the op-

2

timal alignment according to the graph matching objective function is, essentially, the true
latent vertex alignment, guaranteeing that subsequent optimization procedures are, at the
least, seeking the right permutation.
Notation The following notation will be used throughout the manuscript: for k ∈ Z > 0,
we will let Jk denote the hollow k × k matrix with all 1’s on its off-diagonal, [0]k will denote
the k × k matrix of all 0’s, and [k] will denote the set {1, 2, . . . , k}. We will consider A
and B interchangeably as adjacency matrices and as the corresponding graphs consisting of
vertices and edges. For a set S ⊂ V (A), we denote by A[S] the induced subgraph of A on
the vertices of S.

1.1

Correlated heterogeneous Erdős-Rényi graphs

Formally the graph matching problem (GMP) we will consider is defined as follows.
Definition 1. Let A, B ∈ Rn×n be weighted, symmetric adjacency matrices. The graph
matching problem is to find an element of
argminP ∈Π(n) kA − P BP T k2F = argminP ∈Π(n) − trace(AP B T P T ),

(1)

where Π(n) is the set of n × n permutation matrices.
In the presence of a latent vertex alignment, φ : [n] 7→ [n], we wish to understand the
extent to which graph matching A and B will recover φ; i.e., if Pφ is the permutation
matrix corresponding to φ, will {Pφ } = argminP ∈Π(n) kA − P BP T k2F ? In order to study
this problem from a probabilistic perspective, we introduce a bivariate random graph model
with a natural vertex alignment across graphs: the bivariate, correlated, heterogeneous,
Erdős-Rényi random graph.
Definition 2. For R, Q1 , Q2 ∈ Rn×n symmetric, hollow matrices, we say A, B are instantiations of the R-correlated Heterogeneous Erdős-Rényi random graph model with parameters
R, Q1 , Q2 (abbreviated as R-CorrER(Q1 , Q2 )) if:
1. A ∼ER(Q1 ); i.e., A is an independent edge random graph with

1{u,v}∈E(A) ∼ Bernoulli(Q1 (u, v))
for each {u, v} ∈

V
2



;

3

2. B ∼ER(Q2 ); i.e., B is an independent edge random graph with

1{u,v}∈E(B) ∼ Bernoulli(Q2 (u, v))
for each {u, v} ∈

V
2



;

3. Edges across networks are collectively independent except that for each {u, v} ∈

V
2


,

the correlation between A(u, v) and B(u, v) is R(u, v) ≥ 0.
Before proceeding further, we will make a few remarks on the R-CorrER(Q1 , Q2 ) random
graph model.
• By allowing Q1 and Q2 to differ, this model allows for a latent correspondence to exist
in settings where the underlying topology and degree structure of the graphs to be
matched differs significantly. This generalizes the work of [25, 18, 24], in which it is
assumed that A and B are marginally identically distributed. This distributional heterogeneity is often observed in real data settings (see, for example, the connectomes
being aligned in [7] and the social networks aligned in [21]), and we seek to understand the limitations of graph matching approaches when attempting to overcome this
heterogeneity.
• Note also that when Q1 6= Q2 , there are restrictions on feasible correlations R: Indeed, if X ∼Bernoulli(p) andqY ∼Bernoulli(q) are %-correlated with p > q, then the
.
correlation must satisfy % ≤ q(1−p)
p(1−q)
• By considering a partition of V into V = C ∪ J such that R(u, v) 6= 0 only if u, v ∈ C,
we can model the fact that often in real data, only a fraction of the vertices in A and B
have a corresponding vertex across networks. In this situation, we denote the vertices
possessing a corresponding pair across graphs—i.e., those in C (with |C| = nc )—as core
vertices, with the remaining vertices who do not possess a corresponding pair across
networks—i.e., those in J (with |J | = nj )—as junk vertices. A natural question to
ask is when an optimal GM algorithm will correctly align the cores across networks;
this problem was studied in the context of homogeneous ER networks with constant
correlation in [18]. The results in Section 2.1 generalize and extend those in [18] to
this more adaptable network model.

4

2

Graph matchability

In the R-CorrER(Q1 , Q2 ) model, we seek to understand when an oracle graph matching
procedure will correctly align the vertices across networks. This question motivates the
definition of graph matchability:
Definition 3. We will say that (A, B) ∼ R-CorrER(Q1 , Q2 ) are matchable if
argminP ∈Π(n) kAP − P BkF = {In },
where In denotes the identity matrix.
In recent work addressing the question of graph matchability, the special case of R = %Jn
(for % ≥ 0) was considered in the case of A, B ∼ ER(p) in [30, 26], for A, B identically
distributed stochastic block-models in [29, 24], and for general A, B ∼ ER(P ) in [25]. In
each of these cases, the correlation considered was constant across each vertex-pair, and
the graphs were marginally identically distributed. In each setting, the results showed that
p
for % sufficiently large (usually of the order ω( log n/n)), A and B were asymptotically
almost surely matchable. As the next example demonstrates, the degree and structural
heterogeneity across networks allowed for in the R-CorrER(Q1 , Q2 ) model makes the question
of matchability a bit more nuanced.
Example 4. Consider the following correlated heterogeneous stochastic blockmodel example.
Let p, q, r ∈ [0, 1] be distinct, and define
pJn rJn

!

qJn rJn

!

and Q2 =
.
rJn pJn
rJn qJn
q
Assuming p > q, and letting %1 ≤ q(1−p)
and %2 ∈ [0, 1] we consider R of the form
p(1−q)
!
%1 Jn %2 Jn
.
R=
%2 Jn %1 Jn
Q1 =

In this example, letting P ∈ Π(2n) be any permutation such that P Q2 P T = Q1 , we see that
 
1
n
T
E[tr(AP BP ) − tr(AB)] ≥
(p2 + q 2 ) + n2 r2
2
2
 
p
n
−
(2%1 p(1 − p)q(1 − q) + 2pq) − n2 r(r + %2 (1 − r))
2
 

p
n
=
(p − q)2 − 2%1 p(1 − p)q(1 − q) − n2 %2 r(1 − r)
2


p
1
2
2
=n
[(p − q) − 2%1 p(1 − p)q(1 − q)] − %2 r(1 − r) + O(n).
2
5

Numerous choices of the parameters in this model (for example, p = 0.8, q = 0.2, r = 0.1,
%1 = 0.25, %2 = 0.3) yields that E[tr(AP BP T )−tr(AB)] ≥ cn2 +O(n) for a positive constant
c > 0 (in the example, c = 0.113). As E[tr(AP BP T ) − tr(AB)] is highly concentrated about
its expectation (see Proposition 3.2 from [19]), there is high probability that
{In } ∈
/ argmaxP ∈Π(n) tr(AP BP T ) = argminP ∈Π(n) kAP − P BkF ;
i.e., A andB would not be matchable.
The key to achieving matchability in this heterogeneous setting is to transform the problem back into the homogeneous case. Ideally, rather than matching A and B, we could
e = A − Q1 and B
e = B − Q2 ; yielding once again EB
e = EA.
e As the next theorem
match A
demonstrates, this is sufficient to recover matchability.
e = A − Q1 and B
e = B − Q2 .
Theorem 5. Let (A, B) ∼ R-CorrER(Q1 , Q2 ) and consider A
Define
p
 = min R(u, v) Q1 (u, v) [1 − Q1 (u, v)] Q2 (u, v) [1 − Q2 (u, v)].
u,v

p
e and B
e are matchable) ≥ 1 − {−Ω(2 n)} .
If  = ω( log(n)/n), then P(A
The proof of Theorem 5 can be found in Appendix B.1.
Unfortunately, centering A and B by the true edge probability matrices Q1 and Q2 is
impractical, as these model parameters are unknown in practice. Our solution to this hurdle
is to estimate the unknown Qi ’s and approximately center the networks via estimators of Q1
and Q2 before matching. Our method for estimating Q1 and Q2 is based on the Universal
Singular Value Thresholding (USVT) work of [6]. USVT applied in the present setting can
be summarized as outlined in Algorithm 1.
Algorithm 1 USVT for estimating Q
Input: Adjacency matrices A ∼ER(Q), threshold t > 0;
P
1. Let A = ni=1 σi ui viT be the singular value decomposition of A, with singular values
ordered via σ1 ≥ σ2 ≥ · · · ≥ σn ;
2. Let T = {σi > t} be the set of singular values greater than the threshold t;
b = P|T | σi ui v T
Output: Q
i=1

i

bi using USVT, can we recover the matchability using the centered
If we estimate Qi via Q
b=A−Q
b1 and B
b =B−Q
b2 ? Given the error introduced in estimating the edge
matrices A
probability matrices, the answer is unsurprisingly no, at least for the definition of perfect
6

matchability in Definition 3 (and for the proof techniques we employ herein). However, if
we slightly weaken Definition 3 to allow for a vanishing fraction of unmatched nodes, then
we can recover an analogous result to Theorem 5. This motivates the following definition:
Definition 6. Let (A, B) ∼ R-CorrER(Q1 , Q2 ) and define
Π(n, k) := {P ∈ Π(n) s.t.

n
X

P (i, i) = n − k}

i=1

We say that A and B are fn -matchable if



argminP ∈Π(n) kAP − P BkF ∩ ∪∞
i=fn +1 Π(n, i) = ∅.

Unwrapping Definition 6, we see that fn -matchability is equivalent to any optimal graph
matching permutation correctly recovering the labels of at least n − fn vertices across A
b and B
b are
and B. As the following theorem indicates, under mild model assumptions, A
√
θ( n)-matchable asymptotically almost surely. The proof of Theorem 7 can be found in
Appendix B.2.
Theorem 7. Let (A, B) ∼ R-CorrER(Q1 , Q2 ) and further assume that for each i = 1, 2,
i. There exists a constant ρi ∈ [0, 1] such that Qi ≤ ρi entry-wise.
ii. We have that minj

P

`

Qi (j, `) = ω(log n).

iii. Qi is approximately low rank in that there exists a di = o(n) such that

P

j>di

s2j (Qi ) =

o(nρi di ) where s1 (Qi ) ≥ s2 (Qi ) ≥ · · · ≥ sn (Qi ) are the singular values of Qi .
As in Theorem 5, define
p
 = min R(u, v) Q1 (u, v) [1 − Q1 (u, v)] Q2 (u, v) [1 − Q2 (u, v)].
u,v

bi is the USVT estimate of Qi
For each i = 1, 2, there exists constants ai > 0 such that if Q
√
with threshold level ti = ai nρi and if
√
√

 √
√
( ρ1 + ρ2 )( nρ1 d1 + nρ2 d2 )
k0 = ω
,

and
r
=ω

log n
n

!
,

b=A−Q
b1 and B
b =B−Q
b2 satisfy
then A
b and B
b are k0 -matchable) ≥ 1 − 3n−2 .
P(A
7

Let us take a moment to explore the assumptions in Theorem 7. Assumption i. and ii.
control the allowable sparsity of the networks, ensuring that the minimum expected degree
grows asymptotically faster than log n. If the mean expected degree was o(log n), then
the graphs would be a.s. disconnected [4], and we suspect that fn -matchability would be
unachievable for fn = θ(n). For each i, ρi controls the amount of degree heterogeneity of Gi ,
with small values of ρi ensuring that there is not too much variance in the degree distribution
of Gi . In the event that

ρ1
ρ2

= θ(1) and each entry of Qi is θ(ρi ) (which is indeed the case in

the oft adopted setting where each Qi = ρi Mi for a matrix Mi with entries of order θ(1)),
√
then  = O( ρ1 ρ2 minu,v R(u, v)) and
√

nd1 + nd2 )
.
minu,v R(u, v)

√
k0 = ω

(2)

The rank assumption in iii. is needed to control the accuracy of the USVT estimates of
bi of
the unknown Qi ’s. Practically, smaller di allow us to use suitable low-rank estimates Q
Qi that are computationally easier to implement; this is indeed the case in many common
random graph models such as the Stochastic blockmodel [17] (where often di = O(1)),
random dot product graphs [38] and latent position random graphs [16] (where di is often
taken to be O(polylog(n)) [34]), among others. If, in addition to the assumptions preceding
Eq. 2, each di = O(polylog(n)) and R is bounded away from 0 entry-wise, then up to a
b and B
b are θ(√n)-matchable, and an oracle graph matching algorithm
logarithmic factor A
would properly align all but a vanishing fraction of the nodes across the graphs.
bi using USVT with threshold t ≈ √n. In
Remark 8. In Theorem 7, we estimate Qi via Q
application, often suitable estimates of Qi can be obtained with rank of order log n or Θ(1)
[34], especially in the setting of latent space graph models. We do not explore this model
selection question further here (i.e., estimating a suitable rank rather than a threshold for
our USVT estimates). as in applications often only a relatively small number of eigenvectors
√
are above the USVT threshold of t ≈ n.

2.1

Core Matchability

As mentioned previously, often in applications only a fraction of the vertices in A possess
a latent matched pair in B with the remaining, vertices having uncorrelated connectivity.
Using the notation established after Definition 2, we seek to understand the ability of an
oracle graph matching procedure to correctly match the cores across graphs. This motivates
the following definition of core-matchability.
8

Definition 9. Let (A, B) ∼ R-CorrER(Q1 , Q2 ), and consider a partition of the vertex sets
V = C∪J = {1, 2, . . . , nc }∪{nc +1, nc +2, . . . , n}. Suppose further that R can be decomposed
as R = Rc ⊕ 0nj . We say that A and B are core-matchable (abbreviated C-matchable) if
P̃ ∈ argminP ∈Π(n) kAP − P BkF ⇒

nc
X

P (i, i) = nc ;

i=1

i.e., if any optimal permutation aligning A and B perfectly matches the cores across networks.
If we define PnC := {P ∈ Π(n) s.t.

Pnc

i=1

P (i, i) = nc } to be the set of core matching

permutations, then C-matchability amounts to
argminP ∈Π(n) kAP − P BkF ⊂ PnC .
Completely analogously to the setting considered in Example 4, it is immediate that A
and B need not be asymptotically almost surely C-matchable even with non-vanishing core
e = A − Q1 and B
e = B − Q2 recovers the
correlation in R. As in Theorem 5, centering A
e and B.
e The proof of Theorem 10 is contained in Appendix B.3.
C-matchability of A
e = A − Q1 and B
e = B − Q2 .
Theorem 10. Let (A, B) ∼ R-CorrER(Q1 , Q2 ) and consider A
Suppose that R is of the form R = Rc ⊕ 0nj satisfying Rc > 0 entry-wise. With
p
 := min R(u, v) Q1 (u, v) [1 − Q1 (u, v)] Q2 (u, v) [1 − Q2 (u, v)],
u,v∈[nc ]

if we have that nc 2 = ω (nj log(nj )) and nc 2 = ω (log(nc )) , then there exists a constant
C > 0 such that



2
e
e
P A and B are C-matchable ≥ 1 − e−C nc .
e and B
e are
In the event that  is Θ(1) or Θ(1/polylog(n)), then Theorem 10 implies that A
C-matchable in the presence of nearly linear junk, with arbitrary junk structure. This result
extends and generalizes the results in [18] to the non-homogeneous ER setting.
As before, if the unknown Q1 and Q2 are centered via USVT estimates, then we recover
partial core matchability. Before formalizing this, we first need the following definition.
Definition 11. Let (A, B) ∼ R-CorrER(Q1 , Q2 ) and define
C
Pn,k

:= {P ∈ Π(n) s.t.

nc
X

P (i, i) = n − k}

i=1

We say that A and B are fn , C-matchable if



C
argminP ∈Π(n) kAP − P BkF ∩ ∪∞
k=fn +1 Pn,k = ∅.
9

The following Theorem provides the analogue of Theorem 7 in the core-junk setting.
Note that the proof is completely analogous to that in Theorem 7, and so is omitted.
Theorem 12. Let (A, B) ∼ R-CorrER(Q1 , Q2 ). With the assumptions on Q1 and Q2 from
Theorem 7, in and define
p
 = min R(u, v) Q1 (u, v) [1 − Q1 (u, v)] Q2 (u, v) [1 − Q2 (u, v)].
u,v∈[nc ]

bi is the USVT estimate of Qi
For each i = 1, 2, there exists constants ai > 0 such that if Q
√
with threshold level ti = ai nρi and if

k0 = ω

√
√

√
√
n( ρ1 + ρ2 )( nρ1 d1 + nρ2 d2 )
,
nc 

b=A−Q
b1 and B
b =B−Q
b2 satisfy
and nc 2 = ω (nj log(nj )) and nc 2 = ω (log(nc )) , then A
b and B
b are k0 , C-matchable) ≥ 1 − 3n−2 .
P(A

3

Simulations and Experiments

In the following sections, we explore the impact on graph matchability of USVT centering
in both simulated and real data settings. We note here that precisely determining the level
of matchability is infeasible for even modestly sized networks, as this would require exactly
solving the NP-hard graph matching problem. To circumvent this, we instead match our
networks using the FAQ algorithm of [35] initialized at a variety of starting points including
the true correspondence. As it is a Frank-Wolfe [15] based algorithm, if FAQ terminates
at the true correspondence (or at a permutation which matches a high percentage of the
vertices), then we know the true correspondence is a local minima of the graph matching
problem, and comparing objective function values across local minima then allows us to
approximately gauge the global optimality of the true correspondence. While this is not
the same as directly finding the global minima desired in the definition of matchability, it
nonetheless provides a useful, principled heuristic for empirically studying both matchability
and deviations there from.

10

Centering before matching, varying alpha

Fraction matched correctly

1.00

0.75

Method
Approx. Centered
0.50

Centered
Uncentered

0.25

0.00
0.8

0.9

1.0

alpha

Fraction correctly matched by FAQ ±2s.e. (optimized over two different
initializations—I2n and at I˜2n ) versus α ∈ (0.75, 0.85, 0.95, 1) when matching i. A and
e = A − Q1 and B
e = B − Q2 (labeled “Centered”);
B directly (labeled “Uncentered”); ii. A
Figure 1:

b = A−Q
b1 and B
b = B −Q
b2 (labeled “Approx. Centered”). Here, n = 150 is fixed and
and A
results are averaged over 100 Monte Carlo replicates.

3.1

Simulation

To explore the utility of USVT centering as a graph matching preprocessing step, we consider
the following experiment. We let (A, B) ∼ R-CorrER(Q1 , Q2 ) with
!
!
0.8Jn 0.1Jn
0.2Jn 0.1Jn
Q1 =
and Q2 =
.
0.1Jn 0.2Jn
0.1Jn 0.8Jn
and R of the form
R=α

0.25Jn

0.3Jn

0.3Jn

0.25Jn

!
,

and we use the FAQ algorithm of [35] to match i. A and B directly (labeled “Uncentered”
e = A − Q1 and B
e = B − Q2 (labeled “Centered” in Figures 1–2);
in Figures 1–2); ii. A
b= A−Q
b1 and B
b = B−Q
b2 (labeled “Approx. Centered” in Figures 1–2). In each
and A
figure, we initialize
! the FAQ algorithm at I2n —i.e., at the true latent alignment—and at
0 In
I˜2n :=
—i.e., at the alignment completely confusing blocks one and two across
In 0
networks. We plot the mean fraction of vertices matched correctly (±2s.e.) by FAQ at the
starting point that achieves the lowest graph matching objective function score (averaged
11

Centering before matching, varying n

Fraction matched correctly

1.00

0.75

Method
Approx. Centered
0.50

Centered
Uncentered

0.25

0.00
100

200

300

Number of vertices=2n

Figure 2: Fraction correctly matched by FAQ (initialized at I2n ) ±2s.e.

versus n ∈
e = A − Q1
(25, 50, 100, 150) when matching i. A and B directly (labeled “Uncentered”); ii. A
e = B − Q2 (labeled “Centered”); and A
b = A−Q
b1 and B
b = B−Q
b2 (labeled “Approx.
and B
Centered”). Here, α = 1 is fixed and results are averaged over 100 Monte Carlo replicates.
over 100 Monte Carlo replicates). As the FAQ algorithm is a gradient descent algorithm, if
the fraction matched correctly is less than 1, then the true alignment is not a local minimum
of the graph matching objective function and the graphs are not matchable.
In Figure 1, we consider n = 150—i.e., the graphs are size 300—and in the USVT
√
bi we used t = 300. We plot α ∈ (0.75, 0.85, 0.95, 1) versus the the mean
estimates Q
fraction of vertices matched correctly ±2s.e. It is unsurprising in light of Example 4, that
A and B are not only directly unmatchable, but that the optimal alignment found by FAQ
matches none of the vertices correctly across graphs. Also of note in the figure is that as α
e and B
e appear to be nearly matchable (in that the
increases, the oracle centered graphs A
local minimum found by FAQ is close to I300 ). The steep performance drop off as α decreases
is a consequence of the fact that in low-correlation regimes (low for a given n), matchability
is often not recovered even through centering. With α = 0.75, we suspect that the centered
graph would again be matchable as n increased. Performance in the approximately centered
case tracks performance in the centered case, with the USVT centering recovering almost
all of the gains of the oracle centering. This empirically suggests that the k0 lower bound
in Theorem 7 is not sharp, as USVT centering recovers the full matchability in the high α
regime.
In Figure 2 we repeat the above simulation with α = 1 fixed and n ∈ (25, 50, 100, 150).
12

200

300

300

400

400

600
200

200

0

100

Degrees May

100

100

200

300

400

April

0

200

400

600

800

Degrees April
100

200

300

400

May

Degree Comparison

Figure 3: In the left two panels, we plot the weighted adjacency matrices of aligned Twitter
graphs from April and May. In the right panel, we plot the degrees of each vertex in April
versus the degrees of the same vertex in May. The vertices were sorted according to a
community finding algorithm [9] and according to weighted degree.
Using t ≈

√

2n as the USVT threshold, we again plot the mean fraction of vertices matched

correctly ±2 s.e. versus n. As before, without centering the optimal alignment found by
FAQ matches very few of the vertices correctly across graphs. The performance increase in
the oracle centered setting as n increases is a consequence of the matchability (in Theorem
5) being an asymptotic result; indeed, we should not expect correlated small networks to be
almost surely matchable even with the oracle centering. We note, however, that n = 150
(i.e., graph order = 300) here is sufficient for the asymptotically perfect matchability to
be recovered. Again we see that performance in the approximately centered case tracks
performance in the centered case, with the USVT centering achieving almost all of the gains
of the oracle centering.

3.2

Twitter data

In order to analyze the impact of USVT centering with real data, we considered two graphs
derived from Twitter.1 The two graphs are based on the most active twitter users from
April and May 2014. The graphs are weighted according the log of the number times a user
mentioned another user during the given month. We use the same algorithm for the weighted
graphs as for the unweighted graphs above, which seeks to minimize the same objective
function. After keeping only the largest common connected component, the number of users
1

These graphs were provided as part of the DARPA XDATA project.

13

was 431 in each graph.
As can be seen in Figure 3, many vertices in this data set have very similar connectivity
patterns. Indeed, the empirical Pearson correlation between the entries in the two weighted
adjacency matrices is ≈ 0.91. It is not surprising that the similar graph topology across
networks leads to excellent performance when matching the graphs without centering. Repeating the experiment in Section 3.1—i.e., matching the weighted adjacency matrices A
(“April”) and B (“May”) using FAQ initialized at I431 —yields 405 vertices correctly aligned
across networks. This suggests that although the true correspondence is not optimal (according to the GM objective function), the optimal correspondence does match over 90%
of the vertices correctly across networks without the need for centering. It is worth noting
that preprocessing the data via USVT centering before matching yields 402 vertices correctly
√
matched by FAQ initialized at I431 (with a suitable USVT threshold here being 2 431). This
suggests that the centering procedure does not hurt performance when the graph topologies
are similar across networks, and as we will demonstrate below, can significantly increase
performance when the graph topologies differ across networks.
While both the centered and uncentered graphs are nearly perfectly matchable, centering
does have a very interesting algorithmic effect here; see Figure 4. In the figure, we plot the
number of vertices in the April-May Twitter graphs correctly matched by FAQ versus the
graph matching objective function value. In each panel (on the left matching A and B,
b and B),
b we initialize FAQ at 100 different starting points: once at In
and on the right A
(labeled “P0=I” in the legend) and the rest at random restarts (labeled “rand. start” in the
legend). The figure suggests that centering has the effect of creating a more stable objective
function gap between the optimal permutation and suboptimal alternatives. In a setting
where multiple random restarts are possible—and needed—to recover an unknown latent
alignment, this suggests that the optimal alignment is more easily recognized in the centered
graph regime, and hence online stopping criterion more easily implementable.
To explore the performance of the two approaches (centering and not centering) in the
setting of different network topologies, we consider the following synthetic data experiment.
We choose 100 random users from the twitter networks and add w ∗ C to their induced
subgraphs in the May network, where C ∼ER(100, q); i.e., if the set of randomly chosen
vertices is V, then B[V] ←[ B[V] + w ∗ C before matching or centering. We consider q ∈
{0.1, 0.3, 0.5, 0.7, 0.9} and w ∈ {4, 8}. This experiment is simulating the setting where a
fraction of the network changes its behavior from April to May; in this case by increasing their
volume of mentions month to month. For each value of w and q, we repeat this experiment

14

250

300

350

400

450

500

300

P0=I
rand. start

100

100

300

P0=I
rand. start

0

Vertices matched correctly

Centered

0

Vertices matched correctly

Uncentered

220

Objective function value

240

260

280

300

320

Objective function value

Figure 4: We plot the number of vertices in the April-May Twitter graphs correctly matched
by FAQ versus the graph matching objective function value. In each panel (on the left
b and B),
b we initialize FAQ at 100 different starting
matching A and B, and on the right A
points: once at In (labeled “P0=I” in the legend) and the rest at random restarts (labeled
“rand. start” in the legend).
25 times and plot the mean accuracy (±2 s.e.) of graph matching using using FAQ initialized
at I431 both with and without USVT centering; see Figure 5. This experiment demonstrates
the capacity for USVT to maintain graph matchability in the face of additive deviations
in the network structure. These deviations have the effect of altering the graph topology
month–to–month, and with enough signal, they have a precipitously negative impact on the
performance of matching sans centering. Centering ameliorates this effect, and emphasizes
the common signal in the networks by removing the effect of this additive noise.
In the core-junk setting, the heterogeneity amongst the junk vertices offers a further
setting for demonstrating the utility of USVT-centered graph matching. To see this, we
consider the following experiment: choose nc = 100 uniformly sampled core vertices from
the twitter network and nj ∈ {25, 50, 100, 150} uniformly sampled junk vertices, J1 , for the
April graph and nj uniformly sampled junk vertices, J2 , for the May graph. As before,
we match A[C ∪ J1 ] and B[C ∪ J2 ] using FAQ initialized at Inc +nj both with and without
USVT centering; results are summarized in Figure 6. As seen previously, the ability of
USVT-centering to ameliorate the degree/distributional heterogeneity (here amongst the
junk vertices) leads to superior core matchability compared to the uncentered matching
setting.

15

Approx. Centered
Uncentered

0

0.92

600

Method

200

0.93

Degrees April

Fraction matched correctly

Centering before matching in synthetic Twitter data, w=4

0

0.91
0.25

0.50

q
alpha

200

400

600

800

Degrees May

0.75

Fraction matched correctly w = 4

Degree Comparison, w = 4, α = 0.9

Centering before matching in synthetic Twitter data, w=8

Uncentered

0

0.7

800

1200
Approx. Centered

400

Method

0.8

Degrees April

Fraction matched correctly

0.9

0
0.25

0.50

q
alpha

200

400

600

800

Degrees May

0.75

Fraction matched correctly w = 8

Degree Comparison, w = 8, α = 0.9

Figure 5: In the left two panels, we plot the average matching accuracy (±2 s.e.) of graph
matching using FAQ initialized at I431 when first choosing 100 random vertices, denoted V
from graph B and then substituting B[V] ←[ B[V] + w ∗ C before matching and centering;
here C ∼ ER(100, q). Accuracy is plotted versus q, with w = 4 in the top panel and w = 8
in the bottom. In the right two panels, we plot the degrees of each vertex in April versus the
degrees of the same vertex in May (with the B[V] ←[ B[V] + w ∗ C substitution); again with
w = 4 in the top panel and w = 8 in the bottom. As stated previously, the vertices were
sorted according to a community finding algorithm [9] and according to weighted degree.

4

Discussion

Understanding the limits of graph matchability is an essential step in robust multiple graph
inference regimes. When graphs are not matchable—i.e., the true node correspondence cannot be recovered in the face of noise—paired graph inference methodologies that utilize the
across graph correspondence (see, for example, [33, 2]) cannot gainfully be employed. Nonmatchability limits analysis to methods which rely on graph statistics which are invariant
16

Fraction matched correctly

Centering before matching in core−junk
Twitter data, nc=100
77.5

75.0

Method
Approx. Centered
72.5

Uncentered

70.0

67.5
40

80

120

n

Figure 6: We plot the average core matching accuracy (±2 s.e.) for A[C ∪ J1 ] and B[C ∪ J2 ]
using FAQ initialized at Inc +nj (with nc = 100) against nj ∈ {25, 50, 100, 150}. Results are
averaged over 100 Monte Carlo iterates.
to relabeling of the vertices, which can be useful but lack the full power of their parametric
(with the labeling as a parameter) counterparts. In this paper, we establish initial theoretical
results on graph matchability when the graphs to be match differ in distribution and when
only a fraction of the graphs are matchable.
While our theoretical results and subsequent simulations and experiments provide a basis for a deeper understanding of the effect that distributional heterogeneity has on graph
matchability, there is still much to be done. For example, in our present USVT centering
step the across graph correlation provided by R is not utilized. While the bounds in Lemma
15 may be nearly optimal in the one graph setting, we suspect that the error in the USVT
steps could be greatly reduced by leveraging R or an estimate thereof. We are also exploring
graph normalization strategies other than centering such as kernel smoothing (using a small
number of a priori known correspondences to choose the proper smoothing kernels), which
may be more appropriate in the presence of multiplicative or other non-linear noise structures. We suspect that the growth rate of k0 in Theorem 7 is not sharp, as in simulation and
real data settings almost all the matchability can be recovered via USVT centering; however,
sharpening the lower bound on k0 with our present methods does not seem feasible and new
ideas and techniques need be employed.
We suspect that the bounds on nj versus nc obtained in Theorem 12 are also suboptimal. As an informal argument we can consider known results for the quadratic assignment
problem for i.i.d. entries [5]. In the uncorrelated dense homogeneous Erdős-Rényi setting,

17

these results imply that the best best solution to the graph matching problem, Eq. (1) will
3/2

reduce the objective function Θ(nj ) as compared to a random guess. On the other hand,
in the dense homogeneous Erdős-Rényi setting with constant correlation, the best solution
is Θ(n2c ) better than a random guess. Under the heuristic that in order for the core vertices
to be matched correctly, the signal from correlation must be greater than the possible improvements in the all noise setting, we can conjecture that a core matchability threshold at
approximately nc = O(n3/4 ) may be possible. Using our present proof technique, we are unable to achieve this rate. This heuristic argument, though problematic, provides a potential
guidepost for future work.
In addition, while the results presented herein are for the case that the graphs are simple
undirected graph with no edge-weights, the graph matching framework of Definition 1 is
flexible, allowing us to accommodate many of the features—both those considered above,
and additional eccentricities—inherent to real data settings. In the weighted, loopy setting,
the matching can occur between the weighted adjacency matrices or normalized Laplacian
−1/2

−1/2

matrices, LA = DA ADA (where DA is the diagonal matrix with (i, i)-th entry equal to
P
j DA (i, j)) and the similarly defined LB . To match directed graphs, the graphs can either
be made undirected (for example, by matching A0 = (A + AT )/2 to B 0 = (B + B T )/2) or the
directed adjacency matrices can be directly plugged into Eq. (1). Developing similar results
to Theorems 7 and 12 in models (akin to our CorrER model) that incorporate these graph
features as well as additional vertex and edge features is a natural next step.
The information and computational limits for graph matchability are still open problems
for which we have pushed the boundaries, but significant more work is to be done. These
problems are in analogy to the recently addressed problems of detection and recovery for
the planted partition and planted clique problems for a single graph [13, 28, 1]. For these
settings, exact fundamental limits have been established and polynomial time algorithms
have been shown to achieve or nearly achieve these limits. Obtaining similar results for the
graph matching problem are key steps towards a robust statistical framework for multiple
graph inference.

Acknowledgments
Dr. Sussman’s contribution to this work was partially supported by a grant from MIT
Lincoln Labs and the Department of Defense. This work is partially supported by the MAA
program of the Defense Advanced Research Projects Agency (DARPA) via award number
FA8750-18-0035. We would also like to thank Prof. Carey E. Priebe, Prof. Minh Tang, and
18

Joshua Cape for their helpful discussions in the writing of this manuscript.

A

Bivariate Bernoulli Distribution

For the CorrER model, for each {u, v} ∈

[n]
2


, Auv and Buv can be realized as a bivariate

Bernoulli random variable. This will be a key insight in the proof of our main results,
Theorems 5 and 7. Spelling this out further, a pair of Bernoulli random variables (X, Y ) has
a BiBernoulli distribution with
(X, Y ) ∼ BiBern

p11 p10

!

p01 p00

(3)

if P[X = x, Y = y] = pxy for each (x, y) ∈ {0, 1}2 . A key property of BiBernoulli random
variables is that they can be generated by a triple of independent Bernoulli random variables.
For (X, Y ) as above, setting Z0 ∼ Bern(p11 + p10 ), Z1 ∼ Bern(p01 /(p01 + p00 )), and Z2 ∼
Bern(p11 /(p11 + p10 )), with Z0 , Z1 and Z2 independent yields
L

(X, Y ) = (Z0 , Z0 Z2 + (1 − Z0 )Z1 ).
The following simple proposition will be useful throughout our proofs.
Proposition 13. If (X, Y ) are %-correlated and identically distributed Bernoulli(p), then
!
p(p + %(1 − p))
p(1 − %)(1 − p)
(X, Y ) ∼ BiBern
,
p(1 − %)(1 − p) (1 − p)((1 − p) + %p)
and we can realize this pair with independent Bernoulli random variables
Z0 ∼ Bern(p), Z1 ∼ Bern(p(1 − %)), and Z2 ∼ Bern(p + %(1 − p)),
as above.
A fact we use later is that, with notation as in Proposition 13, we have
Var(Z0 + Z1 + Z2 ) = p(1 − p) + 2(1 − %)p(1 − p) + %(1 − %)(p2 + (1 − p)2 )
≤ 3p(1 − p) + %(1 − %)

B

Proofs

Herein we collect proofs of the main theoretical results in this manuscript.
19

(4)

B.1

Proof of Theorem 5

The key to the Proof of Theorem 5 will be the following proposition from [19].
Proposition 14 (Proposition 3.2 from [19]). Let X1 , . . . , Xm be a sequence of independent
Bernoulli random variables where E[Xi ] = pi . Let f : {0, 1}m 7→ R be such that changing
any Xi to 1 − Xi changes f by at most
M = sup sup |f (X1 , . . . , Xi , . . . , Xn ) − f (X1 , . . . , 1 − Xi , . . . , Xn )|.
i

Let σ 2 = M 2

P

i

X1 ,...,Xn

pi (1 − pi ) and let Y = f (X1 , . . . , Xn ).

Then
2 /4

P[|Y − E[Y ]| ≥ tσ] ≤ 2e−t
for all 0 < t < 2σ/M .

e = A − Q1 and B
e =
Proof of Theorem 5 Let G1 , G2 ∼ R-CorrER(Q1 , Q2 ), and consider A
B − Q2 . If X and Y are %-correlated Bernoulli random variables with respective parameters
p and q, then
p
pq(1 − p)(1 − q)
p
P(X = 0, Y = 1) =q(1 − p) − % pq(1 − p)(1 − q)
p
P(X = 1, Y = 0) =p(1 − q) − % pq(1 − p)(1 − q)
p
P(X = 0, Y = 0) =(1 − p)(1 − q) + % pq(1 − p)(1 − q).
P(X = 1, Y = 1) =pq + %

It follows then that
p
E[(X − p)(Y − q)] = % pq(1 − p)(1 − q).
If we let
p
 = min R(u, v) Q1 (u, v) [1 − Q1 (u, v)] Q2 (u, v) [1 − Q2 (u, v)],
u,v

then if P ∈ Π(n) is a permutation matrix that permutes k labels, we have that

 

k
T
e
e
e
e
Etr(AB) − Etr(AP BP ) ≥  (n − k)k +
− TP
2


k
≥ k n − 1 −
2
where TP is the number of transpositions induced by P .

20

(5)

eB)
e − tr(AP
e BP
e T ). Applying the
To ease notation moving forward, we will let XP := tr(A
observations in Appendix A, we have that XP is a function of

 


 
k
k
NP = 3 (n − k)k +
− TP ≤ 3 nk −
2
2
independent Bernoulli random variables. Let SP be the sum of these NP Bernoulli random
variables; it follows that Var(SP ) ≤ NP /4. With notation as in Proposition 14, we have that
M ≤ 2 and so there exists a constant c > 0 such that



 
k
k
2
k n − 1 −
< σ ≤ NP ≤ 3 nk −
.
2
2
By setting
k n − 1 −
t=
σ

k
2


,

Proposition 14 yields
P (XP ≤ 0) ≤ P (|XP − E(XP )| ≥ E(XP ))
≤ P (|XP − E(XP )| ≥ tσ)
(
2 )
k n − 1 − k2
≤ 2 exp −C
σ2
(
2 )
k n − 1 − k2

≤ 2 exp −C
nk − k2

≤ 2 exp −C2 nk
with C being an appropriate positive constant that may change line to line.
To finish the proof, we apply a union bound on all such P .

The number of such

permutations P that permute k vertex labels is upper bounded by n2k .
p
 = ω( log(n)/n) then
P[

min

P ∈Π(n)\{In }

XP ≤ 0] ≤

=

n
X


2n2k exp −C2 nk

k=1
n
X


2 exp −C2 nk − 2k log(n)

k=1


= exp −Ω(2 n) ,
as desired.

21

Therefore, if

B.2

Proof of Theorem 7

Key to the proof of Theorem 7 is the following Lemma adapted here from [36, Theorem 1].
Lemma 15. Given the assumptions of Theorem 7, for each i = 1, 2 there exists a constant
√
ai > 0 such that if ti = ai nρi , then with probability at least 1 − n−2 ,
bi − Qi k2F ≤ 16a2i (nρi di (1 + o(1))) .
kQ
To prove Theorem 7, we proceed as follows. Fix P ∈ Π(n) so that

P

i

P (i, i) = n − k; i.e.,

P permutes exactly k labels. A simple application of the triangle inequality yields that
b − P BP
b T kF ≥ kA
e − P BP
e T kF − kQ
b1 − Q1 kF − kQ2 − Q
b 2 kF ,
kA
and
b − Bk
b F ≤ kA
e − Bk
e F + kQ
b1 − Q1 kF + kQ2 − Q
b2 kF ,
kA
so that
b − P BP
b T kF − kA
b − Bk
b F ≥ kA
e − P BP
e T kF − k A
e − Bk
e F − 2kQ
b1 − Q1 kF − 2kQ2 − Q
b 2 kF .
kA
As in the proof of Theorem 5, there exists a constant C1 > 0 such that with probability
2 nk

at least 1 − 2e−C1 

,



k
1
T 2
2
e
e
e
e
.
kA − P BP kF − kA − BkF ≥ k n − 1 −
2
2
Similarly, as
 
n
=2
Q1 (`, j)(1 − Q1 (`, j)) < 2ρ1
and
2
`≥j
 
X
n
2
e
E(kBkF ) = 2
Q2 (`, j)(1 − Q2 (`, j)) < 2ρ2
,
2
`≥j
e 2F )
E(kAk

X

Hoeffding’s inequality (see, for example, [8]) yields then that with probability at least
(
(
 )
 )
2ρ22 n2
2ρ21 n2
− exp −
1−exp −
(1 − 2ρ1 )2
(1 − 2ρ2 )2
≥ 1 − 2e− log

2

n

22

(where the last inequality followed from the assumptions in the Theorem, as under the
assumptions nρi = ω(log n)) we have that
 
2
e < 3ρ1 n ⇒ kAk
e F < 2√ρ1 n
kAk
F
2
 
e F < 2√ρ2 n.
e 2F < 3ρ2 n ⇒ kBk
kBk
2
Let k0 be such that
√
√

 √
√
( ρ1 + ρ2 )( nρ1 d1 + nρ2 d2 )
,
k0 = ω

and define the events
n
o
b − P BP
b T kF ≤ kA
b − Bk
b F
EbP := kA
n
o
e − P BP
e T kF − k A
e − Bk
e F ≤ 2kQ
b1 − Q1 kF + 2kQ
b2 − Q2 kF
EeP := kA
n
o
p
p
b
b
A := kQ1 − Q1 kF + kQ2 − Q2 kF ≤ 5a1 nρ1 d1 + 5a2 nρ2 d2
n
o
e F + kBk
e F ≤ 2√ρ1 n + 2√ρ2 n .
Be := kAk
Note that EbP ⊂ EeP and
EeP ∩ A ∩ B
 √

p
p
√
T 2
2
e
e
e
e
⇒ kA − P BP kF − kA − BkF ≤ 10a1 nρ1 d1 + 10a2 nρ2 d2 (4 ρ1 n + 4 ρ2 n) .
2

If k ≥ k0 , then with probability at least 1 − 2e−C1  nk , we have that


1
k
T
2
2
e − P BP
e kF − k A
e − Bk
e F ≥ k n − 1 −
kA
2
2
n

1
≥ k0
−1
2
2

p
p
√
√
= ω n( ρ1 + ρ2 )( nρ1 d1 + nρ2 d2 ) .
Combined, this yields that
2 nk

P(EeP ∩ A ∩ B) ≤ 2e−C1 

23

.

Combining this all, we arrive at the following




[ [
b − P BP
b T kF ≤ kA
b − Bk
b F
P
EbP  = P ∃P ∈ Π(n, k) with k ≥ k0 and kA
k≥k0 P ∈Π(n,k)


≤ P


[

[

EeP 

k≥k0 P ∈Π(n,k)


= P 


[

[





EeP  ∩ (A ∩ B) + P 

k≥k0 P ∈Π(n,k)

≤

X

nk 2e−C1 

2 nk


[

[



EeP  ∩ (Ac ∪ B c )

k≥k0 P ∈Π(n,k)

+ n−2 + 2e− log

2

n

k≥k0

≤ 3n−2
as desired.

B.3

Proof of Theorem 10

For a given permutation τ on [n], we define the permutation τid uniquely as follows:

i,
if i ∈ C
τid (i) =
τ k (i), if i ∈ J , where k = min{` ≥ 1 : τ ` (i) ∈ J }.

(6)

For example, if nc = 4, nj = 4, and
τ=

1 2 3 4 5 6 7 8

!

3 6 7 1 8 5 4 2

then
τid =

1 2 3 4 5 6 7 8
1 2 3 4 8 5 7 6

,

!
.

For a permutation matrix P , we define Pid ∈ PnC analogously, where we recall here that PnC
P c
is the set of permutation matrices P in Π(n) satisfying ni=1
P (i, i) = nc (i.e., fixing all core
labels). Define QCn = Πn \ PnC . Define the events
e − QBk
e F ≤ kAP
e − P Bk
e F}
B1 := {∃Q ∈ QCn s.t. ∀P ∈ PnC , kAQ
e − QBk
e F ≤ kAQ
e id − Qid Bk
e F },
B2 := {∃Q ∈ QCn s.t. kAQ
and note that B1 ⊂ B2 .
24

Suppose that Q ∈ QCn (with corresponding permutation τ ∈ S(n)) permutes kc + kj > 0
core labels, where
kc = |{i ∈ C : i 6= τ (i) ∈ C}|,

(7)

kj = |{i ∈ C : i 6= τ (i) ∈ J }|

(8)

= |{i ∈ J : i 6= τ (i) ∈ C}|.
e − QBk
e 2 − kAQ
e id − Qid Bk
e 2 is a function of NP
Applying Section A, we see that kAQ
F
F
independent Bernoulli random variables, where



kc + kj
(kc + kj )nj + (nc − kc − kj )kj
NP = 3
+ (nc − kc − kj )(kc + kj ) +2
|
{z
}
2
{z
}
|
core–to–junk edges permuted differently by τ and τid
core–to–core edges permuted by τ and not τid
 
kj
+2
+ (nj − kj )kj
2
|
{z
}
junk–to–junk edges permuted differently by τ and τid

≤ 3(kc + 2kj )n.
Letting SP be the sum of these NP Bernoulli random variables, we have that Var(SP ) ≤
NP /4.
We next apply Proposition 14 to bound the probability that Q provides a better matching
that Qid . By the assumption that R(u, v) = 0 if either u or v is a junk vertex, it holds that




e − QBk
e 2F − kAQ
e id − Qid Bk
e 2F = E kAQ
e − QBk
e 2F − kA
e − Bk
e 2 ,
E kAQ
F
so that






kc + kj
2
2
e
e
e
e
E kAQ − QBkF − kAQid − Qid BkF ≥  (nc − kc − kj )(kc + kj ) +
− Tc
2



kc + kj
≥  (nc − kc − kj − 1/2)(kc + kj ) +
2
≥ (kc + 2kj )nc /8,
where, analogously to Section B.1,
p
 = min R(u, v) Q1 (u, v) [1 − Q1 (u, v)] Q2 (u, v) [1 − Q2 (u, v)].
u,v∈[nc ]

With notation as in Proposition 14, it holds that (kc + 2kj )nc /8 < σ 2 = 4Var(SP ) ≤
NP ≤ 3(kc + 2kj )n. By setting t =

(kc +2kj )nc /8
,
σ

25

we have (where, to ease notation, we define

e − QBk
e 2 − kAQ
e id − Qid Bk
e 2)
XQ := kAQ
F
F
P (XQ ≤ 0) ≤ P (|XQ − E(XQ )| ≥ E(XQ ))
≤ P (|XQ − E(XQ )| ≥ (kc + 2kj )nc /8)


(kc + 2kj )nc /8
·σ
= P |XQ − E(XQ )| ≥
σ


2 (kc + 2kj )2 n2c
≤ 2 exp −C
σ2


2 (kc + 2kj )n2c
.
≤ 2 exp −C
n
with C being an appropriate positive constant that may change line to line.
To use a union bound, note that the number of permutations Q ∈ QCn with error counts
2(kc +kj ) 2nj
nj .

in Eqs. (7)–(8) given by kc and kj is bounded above by nc

Hence, if

nc 2 = ω (nj log(nj )) ,
nc 2 = ω (log(nc ))
then we have that
P[ min XQ ≤ 0] ≤
Q∈QC
n

c −kc ,nj )
nc min(nX
X

kc =1

≤

kj =1

nj
nc X
X
kc =1 kj =1

≤

c +kj ) 2nj
2n2(k
nj
c

nj
nc X
X


2 exp

2 (kc + 2kj )n2c
exp −C
n





2 (kc + kj )n2c
−C
+ 2(kc + kj ) log(nc ) + 2nj log(nj )
n


2 exp{−C2 nc } = exp −C2 nc ,

kc =1 kj =1

as desired.

References
[1] E. Abbe and C. Sandon. Community detection in general stochastic block models:
Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual
Symposium on Foundations of Computer Science, pages 670–688, October 2015.
[2] D. Asta and C. Shalizi. Geometric network comparisons. In Proceedings of the ThirtyFirst Conference on Uncertainty in Artificial Intelligence, UAI’15, pages 102–110, Arlington, Virginia, United States, 2015. AUAI Press.
26

[3] L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth
annual ACM symposium on Theory of Computing, pages 684–697. ACM, 2016.
[4] B. Bollobás. Random Graphs. Springer, 1998.
[5] E. Cela. The quadratic assignment problem: theory and algorithms, volume 1. Springer
Science & Business Media, 2013.
[6] S. Chatterjee. Matrix estimation by universal singular value thresholding. The Annals
of Statistics, 43(1):177–214, 2015.
[7] L. Chen, J. T. Vogelstein, V. Lyzinski, and C. E. Priebe. A joint graph inference case
study: the c. elegans chemical and electrical connectomes. In Worm, volume 5. Taylor
& Francis, 2016.
[8] F. Chung and L. Lu. Concentration inequalities and martingale inequalities: a survey.
Internet Mathematics, 3(1):79–127, 2006.
[9] A. Clauset, M.E.J. Newman, and C. Moore. Finding community structure in very large
networks. Physical review. E, Statistical, nonlinear, and soft matter physics, 70(6 Pt
2):066111, December 2004.
[10] D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in
pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(03):265–298, 2004.
[11] F. Emmert-Streib, M. Dehmer, and Y. Shi. Fifty years of graph matching, network
alignment and network comparison. Information sciences, 346–347:180–197, 2016.
[12] F. Escolano, E. R. Hancock, and M. Lozano. Graph matching through entropic manifold alignment. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE
Conference on, pages 2417–2424. IEEE, 2011.
[13] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms
and a lower bound for detecting planted cliques. In Proceedings of the Forty-fifth Annual
ACM Symposium on Theory of Computing, STOC ’13, pages 655–664, New York, NY,
USA, 2013. ACM.
[14] P. Foggia, G. Percannella, and M. Vento. Graph matching and learning in pattern recognition in the last 10 years. International Journal of Pattern Recognition and Artificial
Intelligence, 28(01):1450001, 2014.
27

[15] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research
Logistics Quarterly, 3(1-2):95–110, 1956.
[16] P. D. Hoff, A. E. Raftery, and M. S. Handcock. Latent space approaches to social
network analysis. Journal of the american Statistical association, 97(460):1090–1098,
2002.
[17] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps.
Social networks, 5(2):109–137, 1983.
[18] E. Kazemi, L. Yartseva, and M. Grossglauser. When can two unlabeled networks be
aligned under partial overlap? In Communication, Control, and Computing (Allerton),
2015 53rd Annual Allerton Conference on, pages 33–42. IEEE, 2015.
[19] J. H. Kim, B. Sudakov, and V. H. Vu. On the asymmetry of random regular graphs
and random graphs. Random Structures and Algorithms, 21:216–224, 2002.
[20] J. Lee, M. Cho, and K. M. Lee. A graph matching algorithm using data-driven markov
chain monte carlo sampling. In Pattern Recognition (ICPR), 2010 20th International
Conference on, pages 2816–2819. IEEE, 2010.
[21] L. Li and W. M. Campbell. Matching community structure across online social networks.
NIPS Workshop on Networks in the Social and Information Sciences, 2015.
[22] L. Lin, X. Liu, and S.-C. Zhu. Layered graph matching with composite cluster sampling.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(8):1426–1442,
2010.
[23] E. M. Loiola, N. M. M. de Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido. A
survey for the quadratic assignment problem. European journal of operational research,
176(2):657–690, 2007.
[24] V. Lyzinski. Information recovery in shuffled graphs via graph matching. IEEE Transactions on Information Theory, DOI: 10.1109/TIT.2018.2808999, 2018.
[25] V. Lyzinski, D. E. Fishkind, M. Fiori, J. T. Vogelstein, C. E. Priebe, and G. Sapiro.
Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis and
Machine Intelligence, 38(1):60–73, 2016.

28

[26] V. Lyzinski, D. E. Fishkind, and C. E. Priebe. Seeded graph matching for correlated
Erdos-Renyi graphs. Journal of Machine Learning Research, 15:3513–3540, 2014.
[27] V. Lyzinski, D. L. Sussman, D. E. Fishkind, H. Pao, L. Chen, J. T. Vogelstein, Y. Park,
and C. E. Priebe. Spectral clustering for divide-and-conquer graph matching. Parallel
Computing, 47:70–87, 2015.
[28] E. Mossel, J. Neeman, and A. Sly. Belief propagation, robust reconstruction and optimal
recovery of block models. In Conference on Learning Theory, pages 356–370. jmlr.org,
29 May 2014.
[29] E. Onaran, S. Garg, and E. Erkip. Optimal de-anonymization in random graphs with
community structure. arXiv preprint arXiv:1602.01409, 2016.
[30] P. Pedarsani and M. Grossglauser. On the privacy of anonymized networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and
data mining, pages 1235–1243. ACM, 2011.
[31] A. Robles-Kelly and E. R. Hancock. A riemannian approach to graph embedding.
Pattern Recognition, 40(3):1042–1056, 2007.
[32] J. Sang and C. Xu. Robust face-name graph matching for movie character identification.
IEEE Transactions on Multimedia, 14(3):586–596, 2012.
[33] M. Tang, A. Athreya, D. L. Sussman, V. Lyzinski, Y. Park, and C. E. Priebe. A
semiparametric two-sample hypothesis testing problem for random dot product graphs.
Journal of Computational and Graphical Statistics, Accepted for publication, 2016.
[34] M. Udell and A. Townsend. Nice latent variable models have log-rank. arXiv preprint
arXiv:1705.07474, 2017.
[35] J. T. Vogelstein, J. M. Conroy, V. Lyzinski, L. J. Podrazik, S. G. Kratzer, E. T. Harley,
D. E. Fishkind, R. J. Vogelstein, and C. E. Priebe. Fast Approximate Quadratic Programming for Graph Matching. PLoS ONE, 10(04), 2014.
[36] J. Xu. Rates of convergence of spectral methods for graphon estimation. arXiv preprint
arXiv:1709.03183, 2017.
[37] L. Yartseva and M. Grossglauser. On the performance of percolation graph matching.
In Proceedings of the first ACM conference on Online social networks, pages 119–130.
ACM, 2013.
29

[38] S. Young and E. Scheinerman. Random dot product graph models for social networks.
In Proceedings of the 5th international conference on algorithms and models for the
web-graph, pages 138–149, 2007.
[39] M. Zaslavskiy, F. Bach, and J.P. Vert. A path following algorithm for the graph
matching problem. Pattern Analysis and Machine Intelligence, IEEE Transactions on,
31(12):2227–2242, 2009.
[40] F. Zhou and F. De la Torre. Factorized graph matching. In Computer Vision and
Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 127–134. IEEE, 2012.

30

