Information Recovery in Shuffled Graphs

arXiv:1605.02315v2 [stat.ML] 27 Sep 2017

via Graph Matching
Vince Lyzinski
University of Massachusetts Amherst

September 29, 2017

Abstract
While many multiple graph inference methodologies operate under the implicit assumption that an explicit vertex correspondence is known across the vertex sets of the graphs, in
practice these correspondences may only be partially or errorfully known. Herein, we provide
an information theoretic foundation for understanding the practical impact that errorfully
observed vertex correspondences can have on subsequent inference, and the capacity of graph
matching methods to recover the lost vertex alignment and inferential performance. Working
in the correlated stochastic blockmodel setting, we establish a duality between the loss of
mutual information due to an errorfully observed vertex correspondence and the ability of
graph matching algorithms to recover the true correspondence across graphs. In the process, we establish a phase transition for graph matchability in terms of the correlation across
graphs, and we conjecture the analogous phase transition for the relative information loss
due to shuffling vertex labels. We demonstrate the practical effect that graph shuffling—
and matching—can have on subsequent inference, with examples from two sample graph
hypothesis testing and joint spectral graph clustering.
Keywords. Graph matching, information theory, stochastic blockmodel

1

1

Introduction

Graphs are an increasingly popular data modality in scientific research and statistical inference,
with diverse applications in connectomics [6], social network analysis [7], and pattern recognition
[21], to name a few. Many joint graph inference methodologies (see, for example, [45, 18, 6, 37]),
joint graph embedding algorithms (see, for example, [19, 34, 41, 39]) and graph-valued time-series
methodologies (see, for example, [23, 33, 46, 50]) operate under the implicit assumption that an
explicit vertex correspondence is a priori known across the vertex sets of the graphs. While this
assumption is natural in a host of real data settings, in many applications these correspondences
may be unobserved and/or errorfully observed [48]. Connectomics offers a striking example of this
continuum. Indeed, while for some simple organisms (e.g., the C. elegans roundworm [52]) explicit
neuron labels are known across specimen, and in human DTMRI connectomes, the vertices are
often regions of the brain registered to a common template (see [18]), explicit cross-subject neuron
labels are often unknown for more complex organisms.
How can we quantify the effect of the added uncertainty due to an errorfully observed vertex
correspondence? Heuristically, if (G1 , G2 ) is a realization from a bivariate random graph model
with the property that vertices that are aligned across graphs behave similarly in their respective
networks, then the uncertainty in G2 is greatly reduced by observing G1 and the latent alignment.
Indeed, in the extreme case of G1 and G2 being isomorphic, observing the latent alignment function and G1 completely determines G2 . However, as the vertex labels are shuffled uncertainty is
introduced into the bivariate model. In order to formalize this heuristic, we adopt an information
theoretic perspective (see [11] for the necessary background). We develop a bivariate graph model,
the ρ-correlated stochastic blockmodel (Section 2.1), in which we are able to formally address the
information loss/increase in uncertainty due to an errorful labeling across graphs, and we further
explore the impact this lost information has on subsequent inference (see Section 5).
In the presence of a latent vertex correspondence that is errorfully observed across graphs, graph
matching methodologies can be applied to recover the latent vertex alignment before performing
subsequent inference. Consequently, as multiple graph inference has surged in popularity, so
2

has graph matching; see [10] and [16] for an excellent review of the graph matching literature.
Formally, given two graphs with respective adjacency matrices A and B, the graph matching
problem (GMP) seeks to minimize kA − P BP T kF over permutation matrices P — i.e., the GMP
seeks a relabeling of the vertices of B that minimizes the number of induced edge disagreements
between A and P BP T ; see Section 2.3 for more detail. While the related graph isomorphism
problem has recently been shown to be of sub-exponential complexity [5], there are no efficient
algorithms known for the more general problem of graph matching. Due to its practical utility and
computational difficulty, myriad heuristics have been proposed in the literature for approximately
solving the GMP; see, for example, [10] and [49] and the references contained therein.
Working in the aforementioned correlated stochastic blockmodel setting, we uncover a duality
between graph matchability (see Definition 5) and information loss. We show that in the regime
where graph matching can recover the latent vertex alignment after label shuffling, relatively
little information is lost in the shuffle. We conjecture the inverse statement to be true as well:
In the regime where graph matching cannot recover the latent vertex alignment after shuffling, a
relatively nontrivial amount of information is lost in the shuffle. Formalizing graph matching as the
antithetical operation to label shuffling allows us to better understand the utility of graph matching
as a data preprocessing tool. Indeed, while in the presence of modest correlation relatively little
information is lost due to shuffling, this lost information can have a dramatic negative effect on
subsequent inference. While this may seem like an indictment against joint inference in the errorful
correspondence setting, we demonstrate that graph matching can effectively recover almost all of
the lost information (see Theorem 14) and, consequently, the lost inferential performance.
Note: Throughout, for real-valued function f (·) : R 7→ R and g(·) : R 7→ R, we shall write
f (n) ∼ g(n) if limn→∞ f (n)/g(n) = 1. We will also make use of the abbreviation a.a.s. (for
asymptotically almost surely) which will be used as follows. A sequence of events En occurs a.a.s.
P
if P(Enc ) → 0 at a rate fast enough to ensure n P(Enc ) < ∞.

3

2

Background and Definitions

We seek to understand the information lost due to the vertex correspondence across graphs being
errorfully known, as well as the capacity of graph matching to recover this lost information. In
this section we provide a statistical framework and the necessary definitions amenable to pursuing
these problems further.

2.1

Correlated Stochastic Blockmodels

The random graph framework in which we will anchor our analysis is the correlated stochastic
blockmodel (SBM) random graph model of [30]. SBM’s are widely used to model networks exhibiting an underlying community structure [20, 51], and provide a simple model family which has
been effectively used to approximate the behavior of complex network data [2, 53, 9]. Letting Gn
denote the set of labeled, n-vertex, simple, undirected graphs, we define:
Definition 1. (G1 , G2 ) ∈ Gn × Gn are ρ-correlated SBM(K, ~n, b, Λ) random graphs (abbreviated
ρ-SBM) if:
1. G1 = (V, E1 ) and G2 = (V, E2 ) are marginally SBM(K, ~n, b, Λ); i.e., for each i = 1, 2,
i. The vertex set V is the union of K blocks V1 , V2 , . . . , VK , which are disjoint sets with
respective cardinalities n1 , n2 , . . . , nK ;
ii. The block membership function b : V 7→ [K] = {1, 2, . . . , K} is such that for each v ∈ V ,
b(v) denotes the block of v; i.e., v ∈ Vb(v) ;
iii. The block adjacency probabilities are given by the symmetric matrix Λ ∈ [0, 1]K×K ; i.e., for

each pair of vertices {j, `} ∈ V2 , the adjacency of j and ` is an independent Bernoulli trial
with probability of success Λb(j),b(`) .
2. The random variables {1[{j, k} ∈ Ei ]}i=1,2;{j,k}∈(V ) are collectively independent except that for
2

V
each {j, k} ∈ 2 , the correlation between 1[{j, k} ∈ E1 ] and 1[{j, k} ∈ E2 ] is ρ ≥ 0.

4

One of the keys to the theoretical tractability of the ρ-SBM model is that we can construct ρ-SBM(K, ~n, b, Λ) random graphs (G1 , G2 ) as follows. First draw G1 from the underly
ing SBM(K, ~n, b, Λ) model. Conditioning on G1 = (V, E1 ), for each {j, `} ∈ V2 , if {j, `} ∈ E1
then 1[{j, `} ∈ E2 ] is an independent Bernoulli trial with parameter Λb(j),b(`) + ρ(1 − Λb(j),b(`) ); if
{j, `} ∈
/ E1 then 1[{j, `} ∈ E2 ] is an independent Bernoulli trial with parameter Λb(j),b(`) (1 − ρ).
If ρ ∈ (0, 1) so that G1 and G2 are a.a.s. not isomorphic, this construction highlights a natural
alignment between the vertex sets of G1 and G2 : namely the identity function idn : [n] 7→ [n].
Indeed, for modest ρ the identity function is (with high probability) the permutation of the vertex
set of G2 that best preserves the shared structure between G1 and G2 ; see Theorem 12. As, in
practice, this alignment is often errorfully observed, we shall refer to idn as the latent alignment
between G1 and G2 .
Remark 2. Note that ρ-correlated Erdős-Rényi(n, p), abbreviated ρ-ER(n, p), random graphs
(resp., ρ-correlated heterogeneous Erdős-Rényi(P ) random graphs) are easily realized by letting
K = 1 (resp., K = n) in Definition 1

2.2

Shuffled ρ-correlated SBM random graphs

To understand the effect of an errorfully observed latent alignment function, we first need to define
the action of errorfully aligning two ρ-SBM random graphs. Slightly abusing notation, we let Π(n)
denote both the set of permutation matrices and the set of permutations of [n]; to avoid confusion
in the sequel, we will use the Greek letters φ, τ, and σ to denote permutations of [n] and capital
Roman letters P and Q to denote permutation matrices. For x = (V, Ex ) ∈ Gn , and φ ∈ Π(n),
we define the φ-shuffled graph φ(x) = (V, Eφ(x) ) ∈ Gn via {i, j} ∈ Ex iff {φ(i), φ(j)} ∈ Eφ(x) .
Equivalently, if the adjacency matrix of x is Ax and the permutation matrix associated with φ is
Pφ , then the adjacency matrix of φ(x) is Pφ Ax PφT .
For a deterministic permutation φ, the act of shuffling (G1 , G2 ) ∼ ρ-SBM is realized as follows.
For all x, y ∈ Gn , P(G1 = x, φ(G2 ) = y) := P(G1 = x, G2 = φ−1 (y)). The action of randomly
shuffling the vertices of ρ-SBM random graphs can then be defined via:
5

Definition 3. Let σ be an Π(n)-valued random variable. (G1 , σ(G2 )) ∈ Gn × Gn are σ-shuffled,
ρ-correlated SBM(K, ~n, b, Λ) random graphs (abbreviated σ, ρ-SBM) if
i. (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ);
ii. For any x, y ∈ Gn × Gn , we have

P(G1 = x, σ(G2 ) = y) =

X


P(σ = φ)P G1 = x, G2 = φ−1 (y) .

φ∈Π(n)

Simply stated, we first realize σ; conditioned on σ = φ, we then independently realize (G1 , φ(G2 )).
Note: In the sequel, we shall use φ and τ to denote deterministic permutations, and σ to denote
a permutation-valued random variable.

2.3

Graph matching and graph matchability

If the latent alignment between A and B is errorfully known, graph matching methods can applied
to approximately recover the true alignment. We formally define the graph matching problem as
follows:
Definition 4. Given two graphs n-vertex graphs G1 and G2 with respective adjacency matrices A
and B, the graph matching problem (GMP) is defined as minP ∈Π(n) kA − P BP T kF .
Note that the GMP objective function kA−P BP T kF is equal to kAP −P BkF and solving the GMP
is equivalent to solving maxP ∈Π(n) trace(AP BP T ). Intuitively, solving the GMP is equivalent to
relabeling the vertices of G2 so as to minimize the number of induced edge disagreements between
G1 and G2 .
While solving the graph matching problem is NP-hard in general, there are a bevy of approximation algorithms and heuristics in the literature that perform well in practice [55, 49, 15, 13, 28]
(in addition, see the excellent survey papers [10, 16] for a thorough review of the prescient literature and discussion of numerous alternate formulations of the GMP). Note that in Section 5, to

6

approximately match the shuffled graphs in our synthetic and real data applications, we use FAQ
algorithm of [49] and, when seeded vertices are present, the SGM algorithm of [15]. Seeded vertices,
or seeds, are those vertices whose latent alignments are known a priori and are not subjected to
any label shuffling.
Note also that the graph matching problem is closely related to the problem of entity resolution/record linkage (see, for example, [56, 40]), especially in the setting of highly attributed networks. In the present ρ-SBM setting, there is a key difference between the paradigms highlighted
by the non-recoverability of vertex correspondences in the presence of general edge-shuffling; see
Section 3.1.1 for detail.
In the ρ-SBM setting the correlation structure across G1 and G2 highlights the natural alignment, namely idn , between the two graphs. In Theorems 10 and 12, we establish a phase transition
for the values of ρ under which graph matching can/cannot recover the latent alignment in the
presence of vertex shuffling. Before being able to state these results, we first must define the
concepts of graph matchability and σ(G2 ) matched to G1 .
Definition 5. Let (G1 , G2 ) be vertex-aligned random graphs with respective adjacency matrices A
and B. We say that G1 and G2 are matchable if argminP ∈Π(n) kA − P BP T kF = {In }.
To define the random graph σ(G2 ) matched to G1 , we first define the concept of a matched
∗
graph for deterministic x, y ∈ Gn . To this end, let Px,y
:= argminP ∈Π(n) kAx P − P By kF . If

(G1 , G2 ) = (x, y), then it is natural to define GG2 →G1 , G2 matched to G1 , as any element of

∗
∗
∗
Px,y
(y) := φ(y) s.t. Pφ ∈ Px,y
, with all elements of Px,y
(y) being equally probable. Formally,
we define
Definition 6. Let (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ). The Gn × Gn × Gn -valued random variable
(G1 , G2 , GG2 →G1 ) has distribution defined via
∗



 1{z ∈ Px,y
(y)}
,
P (G1 , G2 , GG2 →G1 ) = (x, y, z) = P (G1 , G2 ) = (x, y)
∗
|Px,y (y)|

so that P[(G1 , GG2 →G1 ) = (x, z)] =

P

y

1 ,G2 )=(x,y)]
∗
1{z ∈ Px,y
(y)} P[(G|P
.
∗ (y)|
x,y

7

A consequence of Definition 6 is that if (G1 , σ(G2 )) ∼ σ, ρ−SBM(K, ~n, b, Λ), then





P (G1 , Gσ(G2 )→G1 ) = (x, z) = P (G1 , GG2 →G1 ) = (x, z) , and




P (G1 , G2 , Gσ(G2 )→G1 ) = (x, y, z) = P (G1 , G2 , GG2 →G1 ) = (x, y, z) .

3

Information loss and graph matching

Given graph-valued random variables, (G1 , G2 ), the mutual information of G1 and G2 is defined


P
P(G1 =x,G2 =y)
in the standard way via I(G1 , G2 ) = x,y∈Gn P(G1 = x, G2 = y) log P(G
. Similarly,
1 =x)P(G2 =y)
P
we define the entropy of G1 via H(G1 ) = − x∈Gn P(G1 = x) log(P(G1 = x)). If ρ = 0, then two
ρ-correlated SBM random graphs are independent, and the mutual information between them is
0, regardless of whether the latent vertex alignment is known across graphs or not. If ρ = 1, then
G1 and G2 are isomorphic and I(G1 ; G2 ) = H(G1 ) = H(G2 ), the entropy of G1 . If ρ > 0, then
there is nontrivial information shared across graphs, information which is potentially lost if the
labeling is corrupted. To this end, we have the following proposition, which is proved in Section
A.1.
Proposition 7. Let (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ).
i. If Λ, K and ρ are fixed in n, then I(G1 ; G2 ) = Θ(n2 ).
ii. For fixed Λ and K, if ρ → 0 as n → ∞ then I(G1 ; G2 ) ∼ ρ2

n
2



/2.

iii. For fixed ρ and K, if p := maxi,j (Λi,j ) → 0 as n → ∞ and mini (ni ) = Θ(n) then we have


ρ(1−p)
I(G1 ; G2 ) ∼ Cpρ log 1 + p
n2 , for a constant C > 0.
Proposition 7 highlights the suitability of mutual information as a vehicle for studying graph
correlation (and subsequently graph matchability). It is natural (in light of Theorems 10 and
12) to attempt to quantify the edge-wise correlation ρ through the lens of graph matchability,
as matchable graphs are precisely those whose correlation is above a phase transition threshold.
However, in the ρ-SBM setting the graph matching objective function computed at the latent
alignment satisfies E(kA−Bk2F ) = cn2 (1−ρ) for a real constant c > 0. Likewise, the expected trace
8

form of the graph matching objective function (shown in [27] to be preferable for capturing the true
alignment operationally) computed at the latent alignment satisfies E(trace(AB)) = n2 (c1 − c2 ρ)
for real c1 , c2 > 0. In both cases, for correlation decaying to 0 the lead order term is correlation
independent, and neither readily captures the edge-wise dependency structure across graphs. The

mutual information, however, satisfies I(G1 ; G2 ) ∼ ρ2 n2 /2. The correlation in the lead order
term emphasizes the utility of mutual information for teasing out graph correlation (and hence
graph matchability) in the low correlation regimes. Unfortunately, while computing kA − Bk2F
and trace(AB) is immediate, we are unaware of an efficient method for computing I(G1 ; G2 ). If
available, computing a properly normalized version of I(G1 ; G2 ) after matching would allow us to
a posteriori judge the suitability of having matched the graphs in the first place.

3.1

Information lost and matchability in the high correlation regime

What is the degradation in information due to the uncertainty introduced by randomly permuting the labels of G2 via σ? According to the information processing inequality, I(G1 ; G2 ) ≥
I(G1 ; σ(G2 )) with equality if and only if σ has a point mass distribution. Below we codify (see
Theorems 8 and 10) the following duality between graph matchability and information loss: The
correlation regime in which graph matching can successfully “unshuffle” the graphs—i.e., there
is enough signal even in the shuffled graphs to recover the latent alignment—is precisely that in
which relatively little information will be lost in the shuffle. Note that the proofs of Theorems 8
and 10 can be found in Section A.2 and Section A.3 respectively.
Theorem 8. Let (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ), with K and Λ fixed in n, and let σ be uniformly
distributed on Π(n).
i. For all values of ρ, it holds that I(G1 ; G2 ) − I(G1 ; σ(G2 )) = O(n log n).
p
ii. If ρ = ω( log n/n) and mini ni = Θ(n), then I(G1 ; G2 ) − I(G1 ; σ(G2 )) = Ω(nρ2 ).
If ρ is constant in n, then the asymptotic upper bound of Theorem 8 part i. and the asymptotic
lower bound of Theorem 8 part ii. differ only by a logarithmic factor. We suspect that the true
9

order is ω(n log n), as H(σ) = Θ(n log n) is the loose upper bound we derive on the information
loss in the proof of part i. of the Theorem. In addition, while Theorem 8 is proven with σ uniformly
distributed on Π(n), we suspect that an analogous result holds for other distributions on Π(n)
that place suitable mass on permutations that shuffle k = Θ(n) elements of [n], though we do not
pursue this further here.
Remark 9. In the proof of Theorem 8 part ii., we essentially prove a stronger statement than
that presented in the theorem. If we define Π(n)∗ := {φ ∈ Π(n) | b(i) = b(φ(i)) for all i ∈ [n]},
to be the set of permutations that preserve vertex block assignments and let σ ∗ be uniformly
distributed on Π(n)∗ , then we prove that under the assumptions of the theorem, I(G1 ; G2 ) −
I(G1 ; σ ∗ (G2 )) = Ω(nρ). The information processing inequality (see Proposition 22) then gives us
that I(G1 ; σ(G2 )) ≤ I(G1 ; σ ∗ (G2 )); indeed, there is information in the vertices block assignments
which is lost in σ and not in σ ∗ . Working with σ ∗ allows for errors of the vertex correspondences
without having to deal with the mathematical complications that arise from also errorfully observed
block memberships.
In light of Proposition 7, relatively little information is lost due to shuffling in the ρ =
p
ω( log n/n) regime: indeed, under this assumption on ρ we have that
I(G1 ; G2 ) − I(G1 ; σ(G2 ))
= o(1).
I(G1 ; G2 )
Insomuch as graph matching is the antithetical operation to vertex shuffling, if relatively little
information is lost in the shuffle then the graphs should be matchable (i.e., GM can unshuffle the
networks); we formalize this below in Theorem 10.
Theorem 10. With notation as above, let A and B be the adjacency matrices of ρ−SBM(K, ~n, b, Λ)
random graphs with K, and Λ fixed in n. There exists a constant α > 0 such that if ρ ≥
p


α log n/n, then P ∃ P ∈ Π(n) \ {In } s.t. kA − P BP T kF < kA − BkF = O e−3 log n .
Remark 11. We note here that results similar to Theorem 10 for a much-simplified 2-block SBM
appear in [32], although the authors there consider a different MAP-based objective function in
10

their matching setup.

3.1.1

Shuffling sans graphs

Considering an analogue of Theorem 8 in the non-graph setting illuminates the special role that
GM plays in recovering the lost information. Consider the following example: let (X1 , Y1 ), . . . ,
iid

(Xn , Yn ) ∼ FXY , and suppose we observe the sequence of X’s and a shuffled version of the sequence
of Y ’s. What is the information loss due to this shuffling? In the Bernoulli setting, this is partially
answered by Theorem 8, as that theorem can be immediately cast in the classical setting with
(1{u,v}∈E1 , 1{u,v}∈E2 ) playing the role of (Xi , Yi ). The key difference between the graph setting and
the classical setting is the structure the graph imposes on the shuffling, as not all edge-shuffles are
feasibly obtained via vertex shuffles. This structure is what allows GM to unshuffle the graphs,
since optimizing the GM objective over all edge-shuffles (i.e., optimally unshuffling in the classical
setting) would potentially induce significantly more edge-correlation than initially present in the
graphs and would not be effective for recovering the lost vertex alignment. Indeed, in this Bernoulli
setting, it is easy to see that under mild model assumptions, we have I(X, YY 7→X ) > I(X, Y ) where
YY 7→X is the matched sequence of Y ’s.

3.2

The low correlation regime

In the ρ-SBM model, Theorem 10 asserts that, under mild model assumptions, if ρ is sufficiently
large then G1 and G2 are matchable a.a.s. In Theorem 12 below, we identify the second half of the
p
matchability phase transition at ρ = Θ( log n/n). Indeed, a consequence of Theorem 12 below
p
is that, under mild assumptions, there exists a constant β > 0 such that if ρ ≤ β log n/n then
G1 and G2 are asymptotically not matchable with probability 1.
Theorem 12. With notation as above, let A and B be the adjacency matrices of ρ−SBM(K, ~n, b, Λ)
random graphs with K, and Λ fixed in n. Further assume there is an η > 0 such that Λ ∈
P ni
[η, 1 − η]K×K . Let {τi }N
i=1 be a collection of N :=
i b 2 c disjoint within-block transpositions; i.e.,
if τi = k ↔ `, then b(k) = b(`) = b(τi (k)) = b(τi (`)). There exists a constant β > 0 such that if
11

ρ≤

p
β log n/n, then
!
N n
o
\
lim P
kA − BkF < kA − Pτi BPτTi kF
= 0.

n→∞

i=1

We conjecture a similar phase transition for the relative information loss due to σ. Namely,
when G1 and G2 are not matchable we conjecture that a nontrivial fraction of the mutual information is lost in the shuffle.
Conjecture 13. Let (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ), with K and Λ fixed in n, and let σ be unip
2 )−I(G1 ;σ(G2 ))
= Θ(1).
formly distributed on Π(n). If ρ = o( log n/n), then I(G1 ;GI(G
1 ;G2 )
While the matchability phase transition in Theorems 10 and 12 is tighter than the conjectured
phase transition in Conjecture 13, if true, Conjecture 13 would imply a duality between information
loss and matchability:
p
I(G1 ; G2 ) − I(G1 ; σ(G2 ))
1. if ρ = ω( log n/n) then
= o(1), and G1 and G2 are matchable
I(G1 ; G2 )
p
I(G1 ; G2 ) − I(G1 ; σ(G2 ))
= Θ(1), and G1 and G2 are not matchable.
2. if ρ = o( log n/n) then
I(G1 ; G2 )
In Section 3.3, we show that in the high correlation regime—where the graphs are matchable
and relatively little information is lost due to shuffling—graph matching can effectively recover
the information lost due to shuffling a.a.s.; see Theorem 14. This provides a theoretical foundation
for understanding the utility of graph matching as a pre-processing step for a host of inference
tasks: often when the lost information due to shuffling has a negative effect on inference, graph
matching can recover the lost information and improve the performance in subsequent inference.
p
In the ρ = o( log n/n) regime, while the graphs are no longer matchable, we conjecture (and
experiments bear out) that the alignment found by graph matching still recovers much of the lost
information. However, theoretically working in this regime will require new proof techniques, and
we do not pursue this further here.

12

3.3

Graph matching: Recovering the lost information

In Section 5 we show that the information lost, even when relatively small (see Theorem 8),
can have a deleterious effect on subsequent inference, and we demonstrate the potential of graph
matching to recover the lost inference performance. Theorem 14 below provides a major step
p
towards formalizing this intuition, proving that in the ρ = ω( log n/n) regime, graph matching
recovers almost all of the lost information. The practical effect of this is the recovery of the lost
inferential performance. Note that the proof of Theorem 14 can be found in Section A.5.
Theorem 14. Let (G1 , σ(G2 )) ∈ Gn × Gn ∼ σ, ρ-SBM(K, ~n, b, Λ) with Λ and K fixed in n. If
p
ρ = ω( log n/n), then I(G1 ; G2 ) − I(G1 ; Gσ(G2 )→G1 ) = o(1).
Theorem 14 provides a sharp contrast to the information lost in the shuffled graph regime in this
high correlation setting. Indeed, recall that Theorem 8 implies that I(G1 ; G2 ) − I(G1 ; σ(G2 )) =
Ω(nρ2 ) = Ω(log n).
Remark 15. The information processing inequality states that, given random variables X and
Y and measurable T , I(X; Y ) ≥ I(X; T (Y )). Intuitively, we cannot transform Y independently
of X and increase the mutual information between Y and X. At first glance, Theorem 14, which
implies that I(G1 ; σ(G2 )) < I(G1 ; Gσ(G2 )→G1 ), seems to contradict this. However, we note that
Gσ(G2 )→G1 is a function of both G1 and σ(G2 ). Indeed, if Z = T (X, Y ) then the information
processing inequality need not hold (for a simple example, let X have nontrivial entropy, let Y be
independent of X, and let T (x, y) = x).

4

Empirically matching in the low correlation regime

In the low correlation regime, graph matching with high probability cannot recover the true
correspondence in the presence of vertex shuffling. We conjecture that this is due, in part, to
a nontrivial amount of the information between G1 and G2 being irrevocably lost due to the
vertex shuffling. To explore this further empirically, we consider the following experiment. For

13

Matching in the low correlation setting

Estimated edge correlation: shuffling and matching

Match error

7500

Method
5000

||A−B||
||AP−PB||

2500

Estimated edge correlation

1.00

0.75

Method
Matched

0.50

Shuffled

0.25

0.00

0
−Infinity

−5

−4

−3

−2

−1

0

−Infinity

Correlation, log base 2 scale

−5

−4

−3

−2

−1

0

Correlation, log base 2 scale

(a) Match error versus correlation

(b) Sample edge correlation vs. correlation

Figure 1: For (G1 , G2 ) ∼ ρ-SBM(3, (50, 50, 50), b, Λ), we plot the mean number of edge disagreements ±2 s.e. against correlation ρ when the graphs are aligned with the true latent correspondence
(“kA − Bk” in the legend), and the graphs are aligned by initializing the FAQ graph matching
algorithm at the true correspondence (“kAP − P Bk” in the legend). In the right panel we plot
the mean sample edge correlation against ρ for the matched graphs (G1 , GG2 →G1 ) (“Matched” in
the legend), and for the shuffled graphs (G1 , σ(G2 )) with σ uniformly distributed over Π(150)
(“Shuffled” in the legend). In each case, the means are computed across 200 Monte Carlo iterates.
(G1 , G2 ) ∼ ρ-SBM(3, (50, 50, 50), b, Λ), with

b(i) = 1[50] (i) + 2151:100 (i) + 31101:150 (i) and Λ =



0.5 0.3 0.2
0.3 0.5 0.3
0.2 0.3 0.5



,

we plot in the left panel of Figure 1 the mean number of edge disagreements ±2 s.e. against
correlation ρ ∈ (0, 1/32, 1/16, 1/8, 1/4, 1/2, 1) when the graphs are aligned with the true latent
correspondence (“kA − Bk” in the legend), and the graphs are aligned by initializing the FAQ
graph matching algorithm at the true correspondence (“kAP − P Bk” in the legend). In each case,
the means are computed across 200 Monte Carlo iterates. In the right panel we plot the mean
sample edge correlation against ρ for the matched graphs (G1 , GG2 →G1 ) (“Matched” in the legend),
and for the shuffled graphs (G1 , σ(G2 )) with σ uniformly distributed over Π(150) (“Shuffled” in
the legend), again averaged over 200 Monte Carlo iterates. We note here that we observe similar

14

phenomena as in Figure 1 across a broad swath of parameter values as well.
From the figure we make the following observations. First, as the FAQ algorithm is a FrankWolfe based approach, the agreement between the two methods in Figure 1 panel (a) for ρ ∈
(1/2, 1) implies that for these large correlation levels, the latent alignment is a (local) optimum
for the graph matching objective function. Likewise, the improvement in the match error induced
by matching the graphs via FAQ initialized at I150 for ρ ∈ (0, 1/32, 1/16, 1/8) implies that the
latent alignment is not a (global and local) optimum for the graph matching objective function
for these lower correlation values. This coincides with our intuition that in the presence (resp.,
absence) of enough correlation graph matching can (resp., cannot) recover the latent alignment in
the presence of shuffling. In the figure we also see that in the graph matched setting, the matched
error roughly asymptotes after the matchability phase transition. This is due, in part, to the
matchability of G1 and GG2 →G1 —indeed, if the vertex alignment induced in GG2 →G1 is viewed as
the true latent alignment then (absent symmetries) this alignment is clearly recoverable via graph
matching. Below the phase transition, matching the shuffled, correlated graphs artificially induces
more edge-wise correlation than present in the latent alignment—see the right panel of Figure 1—
in all cases bringing the edge correlation between GG2 →G1 and G1 to the phase transition threshold.
Shuffling effectively makes the edges across graphs independent (uncorrelated equals independent
in the Bernoulli setting), and matching the shuffled graphs induces the same local edge correlation
structure as would matching independent graphs; the original edge-correlation structure which is
captured in I(G1 , G2 ) is truly lost in the shuffle and the global structure preserved in the shuffle
(subgraph counts, community structure, etc.) is not enough for graph matching to recover the
latent alignment.

5

The effect on subsequent inference

While the loss in information due to shuffling has little effect on inference tasks that are independent of vertex labels (for example, the nonparametric hypothesis testing methodologies of [44, 4]),
the effect on inference that assumes an a priori known vertex alignment may be dramatic. We
15

demonstrate this in the context of joint graph clustering and two sample hypothesis testing for
graphs. The trend we demonstrate below is as follows: diminished performance as the alignment
is shuffled and the performance loss due to shuffling being recovered via graph matching. We
expect this trend to generalize to a host of other joint inference tasks as well. We note here that
these results provide a striking contrast to those in [48], where it was shown that even if the
graph labeling contain relevant class signal, obfuscating the labels does not necessarily decrease
classification performance in a single graph setting.

5.1

Hypothesis Testing

We first consider the simple setting of testing whether two ρ-correlated Erdős-Rényi graphs have
the same edge probability. Formally, given (G1 , G2 ) ∼ ρ-ER(n, p, q)—i.e., the edgewise correlation
of G1 ∼ER(n, p) and G2 ∼ER(n, q) is ρ where, as p and q potentially differ here, we require
q

q
p(1−q)
p(1−q)
,
—we wish to test the hypotheses H0 : p = q versus H1 : p 6= q. If
ρ ≤ min
q(1−p)
q(1−p)
the edges across graphs were uncorrelated, under H0 we can view the two edge sets as samples

from independent Bin( n2 , p) random variables and a natural test statistic for testing H0 versus
H1 would be that of the two proportion pooled z-test; namely T1 (G1 , G2 ) = q p̂1 −p̂2 n where
2p̂(1−p̂)/( 2 )


n
n
p̂1 = |E1 |/ 2 , p̂2 = |E2 |/ 2 , and p̂ = (p̂1 + p̂2 )/2. As the edges are positively correlated (with the
same ρ) across graphs, a more powerful test of H0 versus H1 would be a paired two proportion
z-test; namely that with test statistic T2 (G1 , G2 ) =

p̂1 −p̂2
q

2̂p(1−p̂)(1−ρ̂)/(n
2)

, where ρ̂ is the empirical

correlation between the edge sets of G1 and G2 . In this paired setting, directly applying the two
proportion pooled test would yield an overly conservative (level less than α) test. Correcting for
the type-I error in the pooled test (to make it approximately level α) is achieved by multiplying
√
the z-test critical value by 1 − ρ̂ yielding an equivalent test to the paired test using T2 . A natural
question in this paired setting is what level of shuffling is necessary for the pairedness of the data
to become so corrupted (i.e., the information in the pairing being lost) as to render the unpaired
test more powerful, and can graph matching recover the lost inferential performance in the paired
regime? Insomuch as I(G1 ; G2 ) captures the edge-wise correlation across networks, this question

16

0.1 0.2 0.3 0.4 0.5 0.6 0.7

Power

Power decay with shuffling
n=50, p=0.4, q=0.375, rho=0.4
Unpaired, Type−I
error not corrected
Paired, 0 shuffled
in H1
Paired, <= 10
shuffled in H1
Paired, <= 20
shuffled in H1
Paired, <= 30
shuffled in H1
Paired, <= 40
shuffled in H1
Paired, <= 50
shuffled in H1

0

10

20

30

40

50

Paired, matched

Shuffled Vertices in H0

Figure 2: We plot the power (based on 2000 Monte Carlo trials) when testing H0 : p = q versus
H1 : p 6= q against the number of unseeded (potentially shuffled) vertices, n − s. In black, we
plot the power of the paired test when at most min(n − s, x) of the n − s unseeded vertices have
their labels shuffled under H1 for x ∈ (0, 10, 20, 30, 40, 50). The blue line plots the power of the
unpaired test (not type-I error corrected), and the red line plots the power of the paired test when
graph matching is used to align the networks before computing T2 .
is precisely addressing the effect that the reduced information (due to shuffling) has on testing
power.
Exploring this further, we consider the above tests with p = 0.4, q = 0.375, n = 50, and ρ = 0.7
when s vertex correspondences are assumed known across G1 and G2 for s ∈ (0, 10, 20, 30, 40, 50)
(i.e., n − s unseeded and potentially shuffled vertex labels), noting here that we observed similar
phenomena across a broad swath of parameter choices. As we can empirically sample from the null
distribution of T2 given the level of shuffling, to ensure a level α test the shuffled null distribution is
computed under the least favorable element of the null hypothesis for T2 , which here corresponds
to none of the n − s unseeded vertex having their labels shuffled.
In Figure 2, we plot the power (based on 2000 Monte Carlo trials) when testing H0 : p = q
versus H1 : p 6= q against the number of unseeded (potentially shuffled) vertices. In black, we
plot the power of the paired test when at most min(n − s, x) of the n − s unseeded vertices have
17

their labels shuffled under H1 for x ∈ (0, 10, 20, 30, 40, 50). The blue line plots the power of the
unpaired test (not type-I error corrected), and the red line plots the power of the paired test when
graph matching is used to align the networks before computing T2 . As expected, we see that as
more vertices are shuffled under H1 the power of the paired test decreases precipitously. From the
figure, we also see that the information which is lost in the the shuffle—and the subsequent lost
testing power—is recovered by first graph matching the networks before computing T2 (at least
when n − s < 50 and the graph matching is effective in recovering the latent correspondence).
Note that the matched test is more powerful than the unpaired alternative for all levels of
shuffling in this example, and is more powerful than the shuffled test as long as the graphs are
sufficiently shuffled under H1 . As the exact level of shuffling amongst the unseeded vertices (in H0
or H1 ) is unknown a priori, we propose the graph matching version of the test as a conservative,
more robust, version of testing H0 versus H1 . We view the decreased power at n − s = 50 of
the matched test as an algorithmic artifact; indeed, with no seeds the GM algorithm we employ
often does not recover the true correspondence after shuffling. With a perfect matching, we would
expect the matched power to be ≈ 0.67 for all values of n − s.
An interesting aspect of Figure 2 is that the power of the unpaired test and the paired test
with n − s = 50 are identical. For T1 and T2 to yield approximately the same power with the
same critical value used (which is the case in the least favorable element of the null for T2 with
0 seeds), it is necessary that ρ̂ ≈ 0. As we are in a Bernoulli setting, the edge-wise correlation
being effectively 0 is indicative of the edges across graphs being effectively pairwise independent
(sample correlation has mean of order 1/n2 ), in which case the paired test we are using reduces
to its unpaired alternative. Although the edges are effectively pairwise independent, the graphs
globally are not. Indeed, less local structures (i.e., subgraph counts, community structures, etc.)
are still correlated after shuffling. In this high correlation setting, this global structure is also
captured by I(G1 , σ(G2 )) which, though diminished by shuffling, is still nontrivial. It is this
global structure that is able to be leveraged by graph matching to recover the lost local signal and
the lost information. This is precisely what separates the present graph setting from the more

18

classical paired data setting, in which shuffling data labels is potentially irreversibly detrimental
to subsequent inference.

5.1.1

The effect of shuffling on embedding-based tests

In [45], we propose a semiparametric hypothesis testing framework for determining whether two
graphs are generated from the same underlying random graph model. Note that while this test
is not provably UMP (indeed, no such tests exist in the literature for sufficiently complex graph
models), it is nonetheless one of the first provably consistent two-sample graph hypothesis tests
posed in the literature. The test proceeds as follows. Given G1 distributed as heterogeneous
ER(P ) and G2 distributed as heterogeneous ER(Q) with P and Q assumed positive semidefinite
rank d edge-probability matrices, G1 and G2 are first embedded into Rn×d via adjacency spectral
embedding.
Definition 16. Let G be an n-vertex graph with adjacency matrix A. The d-dimensional adjacency




b = UA S 1/2 , where |A| = UA |U
eA SA ⊕ SeA UA |U
eA
spectral embedding (ASEd ) of G1 is given by X
A
is the spectral decomposition of |A| = (AT A)1/2 , SA ∈ Rd×d is the diagonal matrix containing the
d largest eigenvalues of |A| on its diagonal, and UA ∈ Rn×d is the matrix whose columns are the
corresponding orthonormal eigenvectors.
b = ASEd (G1 )
In [45] it is proven that, under mild assumptions, the (suitably rotated) rows of X
concentrate tightly around the corresponding scaled eigenvectors of P with high probability. This
fact is leveraged to produce a consistent hypothesis test for testing H0 : P = Q versus H1 : P 6= Q
b Yb ) = minW ∈Rd×d s.t.
based on a suitably scaled version of the test statistic T1 (X,

W T W =Id

b −
kXW

b = ASEd (G1 ) and Yb = ASEd (G2 ).
Yb kF , where X
In [24], the test is further refined to more explicitly take advantage of the assumed known vertex
correspondence across networks. Inspired by [8] and the joint manifold embedding methodology
of [34, 29] , we proceed as follows. Given vertex-aligned G1 and G2 , we use ASE to first embed


A
(A+B)/2
the omnibus adjacency matrix O = (A+B)/2
. By jointly embedding G1 and G2 via
B
the omnibus matrix, the Procrustes rotation necessary in computing T1 can be circumvented,
19

which is empirically shown to increase testing power in [24]. To wit, if ASEd (O) =

h

bO
X
b
YO

i

with

bO , YbO ∈ Rn×d , then the omnibus test statistic is a suitably scaled version of T2 (X
bO , YbO ) =
both X
bO − YbO kF .
kX
As in the correlated Erdős-Rényi setting, we wish to understand the impact of vertex shuffling
on testing power using T2 . As before, we expect that as the labels are progressively more corrupted,
tests based on graph invariants that do not utilize the latent alignment will achieve higher power
than testing based on T2 . Exploring this further, we consider the following experiment. Let P =
XX T be a rank 3 positive semidefinite matrix with the rows of X distributed as i.i.d. samples from
a Dirichlet(1,1,1) distribution, and let G1 be distributed as heterogeneous ER(P ) (so that G1 can be
viewed as a sample form a random dot product graph with parameter X [54]). Consider Q = Y Y T
where the final n−20 rows of Y are identical to those of X and the first 20 rows of Y are realized via
Y (1 : 20, ·) = 0.8∗X(1 : 20, ·)+0.2∗D where D ∈ R20×3 has i.i.d. Dirichlet(1,1,1) rows, independent
of X. We let G2 be distributed as heterogeneous ER(Q), with edges maximally correlated to
p

p
Q ∗ (1 − P )/(P ∗ (1 − Q)), P ∗ (1 − Q)/(Q ∗ (1 − P )) , where the
those of G1 by ρ = min
multiplication and division in the computation of ρ is entry-wise for the matrices there involved.
We are interested in understanding the power of the test using T2 for detecting the anomalous
behavior of the 20 vertices in G2 . In Figure 3, we plot (“Omni w/ Shuffling” in the legend) the
power ±2 s.e. of the test of H0 versus H1 using T2 when x = (0, 25, 50, 75) vertices have their
labels potentially shuffled (i.e., 100 − x seeded vertices). To control the level of the test using
T2 here, we sample the null distribution under the least favorable member of the composite null
which corresponds to all unseeded vertices being shuffled under H0 . Rather than considering
different levels of shuffling under H1 as in Section 5.1, we plot the best possible performance for
the composite alternative hypothesis; this is achieved when all unseeded vertices are also shuffled
under H1 . We also plot the power ±2 s.e. of the test using T2 (“Matched Omni” in the legend)
when the seeded vertices are used to first matched the graphs before computing T2 to directly test
H0 versus H1 . In each case, the power is averaged over 25 Monte Carlo replicates, which here
corresponds to 25 different realizations of G1 and G2 .

20

Testing power: Graph invariants versus
using vertex correspondences
0.3

Method
Triangle Count

Power

0.2

Spectral Norm
Omni w/ Shuffling
Max Degree
Matched Omni
0.1

0

20

40

60

Shuffled Vertices

Figure 3: We plot (“Omni w/ Shuffling” in the legend) the power ±2 s.e. of the test of H0 versus
H1 using T2 (with appropriate Type-I error correction) when x = (0, 25, 50, 75) vertices have their
labels potentially shuffled (i.e., 100 − x seeded vertices). We plot the power ±2 s.e. of the test
using T2 (“Matched Omni” in the legend) when the seeded vertices are used to first matched the
graphs before computing T2 to directly test H0 versus H1 . We plot the power ±2 s.e. of testing
H0 versus H1 using test statistics T3 = |M (A) − M (B)|, T4 = |t(A) − t(B)|, T5 = |s(A) − s(B)|
(resp., “Max Degree”, “Triangle Count”, and “Spectral Norm” in the legend). In all cases, the
power is averaged over 25 Monte Carlo replicates.
To compare the omnibus embedding based test to graph invariant based tests, we consider
P
the following graph invariants. For an adjacency matrix A, we let M (A) := maxi ( j Ai,j ) be the
maximum vertex degree in A, t(A) := trace(A3 )/6 be the number of triangle subgraphs present
in A, and s(A) := kAk2 be the spectral norm of A. In Figure 3 we then plot the power ±2
s.e. of testing H0 versus H1 using these graph invariant test statistics: T3 = |M (A) − M (B)|,
T4 = |t(A) − t(B)|, and T5 = |s(A) − s(B)| (resp., “Max Degree”, “Triangle Count”, and “Spectral
Norm” in the legend). In all cases, the power is averaged over 25 Monte Carlo replicates, which
here corresponds to 25 different realizations of G1 and G2 .
From the figure, we see that in the presence of sufficient shuffling the graph invariant based
21

tests are more powerful than the test that leverages the errorful correspondence. However, graph
matching successfully recovers the lost information and subsequently the lost testing power. The
increased variance in the graph matching based test at x = 75 can be attributed to errors induced in
the matching under H1 with only 25 seeds. With this number of seeds our matching algorithm can
effectively recover the latent alignment under H0 , while under H1 the graph matching algorithm
occasionally fail to recover the true correspondence. These errors under H1 result in strictly
increased testing power here (and hence the increased standard error). While at first glance this
would suggest using an imperfect matching to optimize power, the red curve demonstrates the
dangers of having an imperfect matching in both H0 and H1 . As practically there is no way
to know whether the matching is perfect or not or whether we are in H0 or H1 , we view the
matched test (always matching under both H0 and H1 ) as a conservative, robust alternative to its
unmatched paired alternative.
We lastly note that while the graph invariant methods perform poorly in this heterogeneous
ER anomaly setting, under alternate testing regimes we expect these tests to outperform the
embedding based test here presented (for example, when testing in certain non-edge independent models). Further understanding the properties of the underlying model that dictate this
performance is paramount in practice, and we are presently pursuing this line of research.
Remark 17. Note that while it is perhaps more natural to use an appropriately centered and
scaled version of kA − BkF as our test statistic, as noted in [45], kA − BkF yields a test that is
inconsistent for a large class of alternatives (e.g., if G2 ∼ ER(n, 0.5) in the G1 and G2 independent
setting), whereas the test based on T1 is provably level-α consistent over the entire range of (fixed)
alternative distributions. In [24], we posit the same level-α consistency for testing based on T2 .

5.2

Joint versus single graph clustering

We next explore the impact that label shuffling has on spectral graph clustering. Spectral graph
clustering has become an important and widely-used machine learning method, with a sizable
literature devoted to various spectral clustering algorithms under several model assumptions; see,
22

Joint versus single graph clustering
0.9

0.8

ARI

Method
G1 only
0.7

Omni

0.6

0.00

0.25

0.50

0.75

1.00

Correlation

Figure 4: Joint versus single graph clustering of two ρ-correlated SBM. Over a range of ρ, we embed
O and cluster the jointly embedded vertices. The dashed line plots the mean Adjusted Rand Index
(ARI) ± 2 s.e. for the clustering of G1 against its true block assignments when embedding O and
jointly clustering the vertices. The solid line plots the ARI ± 2 s.e. of clustering ASE(G1 ) against
the true block assignments for single graph clustering. In each case the number of Monte Carlo
trials was 500.
for example, [25, 35, 38, 43, 14, 31]. We focus here on a variant of the methodology of [43, 8],
which embeds (a pair of) graphs into an appropriate Euclidean space and subsequently employs
the k-means algorithm to cluster the data. Here, rather than using k-means clustering to cluster
the data, we will employ the model-based clustering algorithm Mclust [17].
When we have multiple graph valued observations of the same data, can we efficiently utilize
the information between the graphs to increase clustering performance? In the manifold matching
literature, there are numerous examples of this heuristic: leveraging the signal across multiple
data sets can increases inference performance within each of the data sets (see, for example,
[34, 29, 42, 39]). Inspired by this, given vertex-aligned G1 and G2 , we use ASE to embed the
Omnibus adjacency matrix O and use Mclust to cluster the embedded vertices.
To demonstrate the potential performance increase achievable via jointly embedding G1 and

0.05
G2 versus a separate embedding, we consider (G1 , G2 ) ∼ ρ − SBM 2, ~n = (50, 50), b, 0.1
.
0.05 0.2
Results are displayed in Figure 4. Over a range of ρ, we jointly embed and cluster G1 and G2

23

Correlation=0.5

Correlation=0.7

0.7
0.6
0.6
G1 only
Omni w/ matching

0.5

Method
ARI

ARI

Method
0.5

G1 only
Omni w/ matching

Omni w/o matching

Omni w/o matching
0.4

0.4

0.3

0.3
0

20

40

60

80

0

Seeds

20

40

60

80

Seeds

(a) ρ = 0.5

(b) ρ = 0.7

Figure 5: We plot the mean ARI ±2 s.e. of: i) the clustering of G1 obtained via jointly embedding/clustering when 100 − s of the vertices in G2 have their labels randomly permuted (labeled
“Omni w/o matching” in the legend); ii) embedding and clustering applied to G1 only (labeled
“G1 only” in the legend); iii) the clustering of G1 obtained via jointly embedding/clustering after
matching the shuffled B back to A (labeled “Omni w/ matching” in the legend). In the left plot,
the across graph correlation is 0.5, and is 0.7 in the rightmost plot.
via ASE(O) and Mclust with the dashed line plotting the mean Adjusted Rand Index [36] (ARI)
± 2 s.e. for the clustering obtained for G1 against its true block assignments. We also embed
and cluster G1 alone, and the solid line plots the mean ARI ± 2 s.e. of the obtained clustering
of G1 against its true block assignments. In each case the number of Monte Carlo trials was 500.
Across these synthetic experiments, we used the true d = k = 2. In Figure 4, we see significantly
improved clustering accuracy achieved by joint inference for modest to lowly correlated (G1 , G2 ).
Note that as the correlation increases, the increased performance due to the borrowed strength
of joint inference diminishes. This is unsurprising as the amount of additional information added
by G2 is less for larger ρ (indeed if ρ = 0 then H(G2 |G1 ) = H(G2 ) = O(n2 ) while if ρ = 1 then
H(G2 |G1 ) = 0).
Does this increased performance due to joint inference degrade in the presence of an errorfully
observed vertex correspondence? To explore this further, we randomly permute the labels of
100 − s vertices in B, so that there are s ∈ {0, 20, 40, 60, 80} seeded vertices whose labels are kept

24

0.150

0.125

0.125

0.100

ARI

Ac only
Omni w/ matching
0.100

Method
Ag only

ARI

Method

Omni w/o matching

Omni w/ matching
Omni w/o matching

0.075

0.075

0.050

0.050

0.025
0

50

100

150

0

Seeds

50

100

150

Seeds

(a) Chemical connectome

(b) Electrical connectome

Figure 6: We plot the mean ARI ±2 s.e. (against the true clustering of the connectome into
inter, motor, and sensory neurons) of: i) jointly embedding/clustering when 247 − s of the vertices
in G2 (chosen uniformly at random) have their labels randomly permuted (labeled “Omni w/o
matching” in the legend); ii) embedding and clustering only a the single graph (labeled “Ac only”
and “Ag only” in the legend); iii) jointly embedding/clustering after matching the shuffled B back
to A (labeled “Omni w/ matching” in the legend). In the left plot, we plot the performance on
the chemical connectome, and on the right the electrical connectome. Each plot is computed with
50 Monte Carlo trials.
true (note that these seeded vertices are randomly chosen from the 100 total vertices). We plot the
performance of joint clustering pre- and post-graph matching for ρ = 0.5 and ρ = 0.7 in Figure 5.
In light of Theorem 8, we see that the modest information lost due to the shuffling dramatically
decreases the performance of our paired graph inference. This can be readily explained: the
information lost due to shuffling is precisely the information leveraged by the joint embedding,
namely the vertex correspondences across graphs.
In Figure 5, we also explore the inferential impact of graph matching in recovering this lost
performance. In light of Theorem 14, we see that graph matching recovers the information lost
in shuffling, and therefore recovers much of lost performance. It is notable that when s = 0, GM
using FAQ performs little better than chance in recovering the true across graph labeling (recall,

25

exact GM is NP-hard and note that seeding was shown in [15] to dramatically increase GM
performance). We note that FAQ does (errorfully) recover the across-graph block assignments,
and so aligns the graphs in a way that preserves some of the necessary structure leveraged by
the joint embedding/clustering procedure. This suggests an extension of Theorems 14, in which
perfect matching is not needed for a significant portion of the information lost by shuffling to be
fully recovered.
Note also that in the lower correlation setting, the performance after matching is significantly
better than the corresponding performance in the higher correlation setting (relative to the base
single graph inference level). This confirms the intuition proposed by Figure 4: With higher
correlation, there is less additional information to be recovered by matching (although fewer seeds
are needed to recover this lost information), and therefore, there is a comparatively smaller increase
in performance achieved by the joint inference even post matching.
As a second example, we consider jointly clustering the C. elegans connectomes [47]. The
connectome of the C. elegans roundworm has been completely mapped and neurons interact with
each other in two distinct modes: via electrical gap junctions and via chemical synapses. In
[26, 8], the authors showed that the electrical and chemical connectomes contain complimentary
signal, and both papers suggest that inference should proceed in the joint graph space. To explore
this further, as in [8], we pre-process the data by removing the isolated neurons (under either
modality) and symmetrizing each connectome. The resulting connectomes each have 253 vertices
which are classified into 3 neural types: motor neurons, sensory neurons, and inter neurons. In the
left (resp., right) panel of Figure 6, we plot the performance of jointly embedding/clustering the
vertices in the chemical (resp., electrical) connectome versus embedding and clustering the single
graphs. Throughout, we estimate d via computing an elbow in the SCREE plot and use Mclust
to cluster the data into k = 3 clusters.
In both modalities, significantly better clustering performance is achieved by working in the
joint graph space; indeed, in the case where the correspondence is perfectly observed across graphs,
the ARI for the joint embedding/clustering of the chemical (resp., electrical) connectome is 0.15

26

(resp., 0.18) compared to 0.12 (resp., 0.08) ARI via single graph regime. The larger increase in the
performance of jointly clustering the electrical connectome versus the chemical connectome can
be attributed to the stronger cluster structure present in the chemical connectome. Indeed, the
electrical connectome can borrow the strength of that signal when the graphs are jointly embedded,
whereas there is not much auxiliary signal present in the electrical connectome for the chemical
connectome to leverage.
We lastly note that these graphs are particularly challenging to match, with only ≈ 10% of the
vertices correctly matched by the state-of-the-art SGM algorithm even with 150 seeds (see [15,
Figure 4]). Nonetheless, the structure that is uncovered by graph matching (namely the recovery
of vertex classes across graphs) is enough to recover a large portion of the performance increase
seen in the perfectly matched omnibus embedding setting. Again, this suggests an extension of
Theorems 14, in which perfect matching is not needed for a significant portion of the information
lost by shuffling to be fully recovered.

6

Discussion and future work

Many joint graph inference procedures assume that the vertex correspondence between graphs is
known a priori. However, in practice the correspondence may only be partially known or errorfully
known, and we seek to understand the effect that errors in the labeling have on subsequent
inference. To this end, we provide an information theoretical foundation for answering the following
questions: What is the increase in uncertainty (i.e., loss of the mutual information) between two
graphs when the labeling across graphs is errorfully observed, and can this lost information be
recovered via graph matching? Working in the correlated stochastic blockmodel setting, we prove
that when graph matching can perfectly recover an errorfully observed correspondence (Theorem
10), relatively little information is lost due to shuffling (Theorem 8). However, we demonstrate
that this lost information can have a dramatic effect on the performance of subsequent inference.
We also show that asymptotically almost all of the lost information can be recovered via graph
matching (Theorem 14), which has the effect of recovering much of the lost inferential performance.
27

In the process, we are able to establish a phase transition for graph matchability at ρ =
p
Θ( log n/n) for (G1 , G2 ) ∼ ρ-SBM. We prove in Theorems 10 and 12 that under mild assumptions
p
there exists constants 0 < β < α such that ρ ≥ α log n/n implies G1 and G2 are matchable
p
and ρ ≤ β log n/n implies G1 and G2 are unmatchable. We conjecture the analogous phase
p
transition at ρ = Θ( log n/n) for the relative information loss due to shuffling in Conjecture
13. Establishing Conjecture 13 would cement a duality between the information lost due to
shuffling and matchability (i.e., the ability to undo the shuffling via graph matching): if ρ =
p
p
2 )−I(G1 ;σ(G2 ))
=
o(1),
and
G
and
G
are
matchable;
if
ρ
=
o(
log n/n)
ω( log n/n) then I(G1 ;GI(G
1
2
1 ;G2 )
then

I(G1 ;G2 )−I(G1 ;σ(G2 ))
I(G1 ;G2 )

= Θ(1), and G1 and G2 are not matchable. The difficulty in proving the

conjecture lies in lower bounding the mutual information in the mixture model (G1 , σ(G2 )) with
low correlation.
While graph matching cannot correctly recover the lost correspondence in the low correlation
p
setting, ρ = o( log n/n), we suspect—and the experiments of Section 5, demonstrate—that a
significant portion of the lost information is recovered even by an imperfect matching. This would
have at least two immediate consequences. First, the estimated correlation across different real
data networks—even on the same vertex sets—is often very small. A theorem proving that GM
can recover much of the lost information with an imperfect matching in these low correlation
regimes would further highlight the applicability of GM across a broad class of data sets. Second,
as graph matching is NP-hard in general and no algorithm exists that can perfectly match even
modestly sized graphs, extending Theorem 14 to the case of an imperfect matching would serve
to further highlight the practical utility of graph matching algorithms.
Moreover, across correlation levels we see the dramatic algorithmic impact of seeds on our
ability to successfully unshuffle networks. It is natural to ask what the theoretical impact of
seeding is in terms of lost information. For seeds chosen uniformly at random, the impact on
information loss is marginal: If cn of the vertices are seeded for constant c ∈ (0, 1), then the
bounds of Theorem 8 are affected only by a constant multiplicative factor and not in their order
of magnitude. This is a stark contrast to the algorithmic impact obtained by seeds, as in [28]

28

it is shown that only logarithmically many random seeds are needed to asymptotically perfectly
match graphs. While this suggests that randomly chosen seeds have a more practical impact on
algorithmic performance than in mitigating information loss, we suspect that well-chosen seeds
will have a measurable impact on the bounds in Theorem 8. While this is outside the scope of the
present manuscript, we are actively pursuing seed selection strategies both from the theoretical
and practical perspectives.
Lastly, can we extend this theory to a broader class of random graph models? Note that
while the results of Proposition 7 translates mutatis mutandis to the more general ρ-correlated
heterogeneous Erdős-Rényi model considered in [27], the methods for proving Theorems 10 and
12 do not, hence the present focus on the ρ-SBM model. Also note that deriving the analogous
results to Theorems 10–14 for directed, weighted graphs with a block weighting structure (i.e.,
the edge-weights depend only on the block membership function b of the in and out vertices) is
immediate given almost surely nonnegative and bounded weight distributions. While stochastic
blockmodels (weighted and unweighted) are widely used to model data with latent community
structure, they are an overly simplistic model for many real data applications. We are working to
extend the theory and results to non-edge-independent random graph models (for example, power
law graphs, bounded degree graphs, etc.). However, these non-edge-independent graphs require a
novel correlation structure and new graph matching theory to be developed.

7

Acknowledgments

We wish to thank Donniell Fishkind, Carey Priebe, Daniel Sussman, Minh Tang, Avanti Athreya
and Joshua T. Vogelstein for their comments and suggestions which greatly helped the exposition
and ideas in this paper.

29

A

Proofs and supporting results

Herein, we collect the proofs of the main theorems and supporting results. Note that for φ ∈ Π(n)
we define s(φ) := {i ∈ [n] s.t. φ(i) 6= i} to be the number of vertices shuffled by φ. To ease
notation, for g1 , g2 ∈ Gn we will adopt the following shorthand:

P(g1 , g2 ) := P(G1 = g1 , G2 = g2 ),
Pσ (g1 , g2 ) := P(G1 = g1 , σ(G2 ) = g2 ),

A.1

P(g1 ) := P(G1 = g1 ) = P(G2 = g1)
Pσ (g2 ) := P(σ(G2 ) = g2 ).

Proof of Proposition 7

In this section, we will provide a proof of Proposition 7. Recall that the random variables

{1[{j, k} ∈ E(Gi )]}i=1,2;{j,k}∈(V ) are collectively independent except that for each {j, k} ∈ V2 ,
2
the correlation between 1[{j, k} ∈ E(G1 )] and 1[{j, k} ∈ E(G2 )] is ρ ≥ 0. Next note that if
(X, Y ) ∼ ρ-correlated Bern(p) then


(1 − p)
I(X; Y ) = p(p + ρ(1 − p)) log 1 + ρ
+ 2p(1 − p)(1 − ρ) log(1 − ρ)
p


p
.
+ (1 − p)(1 − p + pρ) log 1 + ρ
1−p

(1)

Together this yields

I(G1 ; G2 ) =



X

P(g1 , g2 ) log

g1 ,g2 ∈Gn

=

K
X
i,j∈[K]
i<j


ni,j

P(g1 , g2 )
P(g1 )P(g2 )





1 − Λi,j
Λi,j (Λi,j +ρ(1 − Λi,j )) log 1+ ρ
+2Λi,j (1 − Λi,j )(1 − ρ) log(1 − ρ)
Λi,j


+ (1 − Λi,j )(1 − Λi,j

where ni,j = ni nj if i 6= j and ni,j =

Λi,j
+ Λi,j ρ) log 1 + ρ
1 − Λi,j

ni
2




,

(2)

if i = j. Expanding Eq. (1) for p fixed and ρ → 0 and

applying this to Eq. (2) yields part ii. of the proposition, and expanding Eq. (1) for ρ fixed and

30

p → 0 and applying this to Eq. (2) yields part iii. of the proposition.

A.2

Proof of Theorem 8

If σ is uniformly distributed on Π(n), then for any fixed τ ∈ Π(n), it is immediate that Pσ (τ (g2 )) =
Pσ (g2 ). We also have that
X

I(G1 ; σ(G2 )) =


Pσ (g1 , g2 ) log

g1 ,g2 ∈Gn




Pσ (g1 , g2 )
P(g1 )Pσ (g2 )






1 P(g1 , τ (g2 )) 
1
P(g1 , φ(g2 )) log 
|Π(n)|
|Π(n)| P(g1 )Pσ (g2 )
g1 ,g2 ∈Gn
τ ∈Π(n)
φ∈Π(n)


−1
X
X
X
1
1 P(g1 , τ ◦ φ (g2 )) 
=
.
P(g1 , g2 ) log 
|Π(n)| g ,g ∈G
|Π(n)| P(g1 )Pσ (φ−1 (g2 ))
X

=

X

X



φ∈Π(n)

1

2

τ ∈Π(n)

n

We then have that I(G1 ; G2 ) − I(G1 ; σ(G2 )) is equal to


−

X
φ∈ Π(n)

−1





X
X P(g1 , τ ◦ φ (g2 ))
X
1
P
(g
)
σ
2
+
P(g1 , g2 ) log 
P(g2 ) log
. (3)
|Π(n)| g ,g ∈G
|Π(n)| · P(g1 , g2 )
P(g
2)
g ∈G
1

2

τ ∈Π(n)

n

2

n

Proof of Theorem 8 part i. We begin by proving part i. of the theorem. Note that
X
g2 ∈Gn


P(g2 ) log

Pσ (g2 )
P(g2 )


= −H(σ(G2 )) + H(G2 ) ≤ 0.

(4)

where the final inequality follows from the concavity of the entropy function H(·). Applying this

31

to Eq. (3) then yields



−1
X
1
P(g1 , τ ◦ φ (g2 )) 
I(G1 ; G2 ) − I(G1 ; σ(G2 )) ≤ −
P(g1 , g2 ) log 
|Π(n)| g ,g ∈G
|Π(n)|P(g1 , g2 )
φ∈ Π(n)
τ ∈Π(n)
n
1 2

X

=−

X
φ∈ Π(n)

≤−

X
φ∈ Π(n)

X



X
X P(g1 , τ ◦ φ−1 (g2 )) 
 1
1

P(g1 , g2 ) log 
+
 |Π(n)|
|Π(n)| g ∈G ,
|Π(n)|P(g1 , g2 ) 
1

τ ∈Π(n)
τ 6=φ

n

g2 ∈Gn

X
1
P(g1 , g2 ) log
|Π(n)| g ∈G ,
1



1
|Π(n)|


= log(|Π(n)|) ∼ (n log n),

n

g2 ∈Gn

as desired.
Proof of Theorem 8 part ii. Let (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ). To prove part ii. of Theorem 8, we
will consider permutations in

Π(n)∗ := {φ ∈ Π(n) | b(i) = φ(b(i)) for all i ∈ [n]},

i.e., permutations of the vertex sets of G1 and G2 that fix block assignments. For σ ∗ uniformly
distributed in Π(n)∗ , we will show that

I(G1 ; G2 ) − I(G1 ; σ ∗ (G2 )) = Ω(nρ2 ).

To complete the proof, we use the information processing inequality to show that I(G1 ; σ(G2 )) ≤
I(G1 ; σ ∗ (G2 )) (see Proposition 22 for detail).
We now establish some notation and preliminary results. For φ ∈ Π(n)∗ , write φ = (φ1 , φ2 , . . . , φK ),
where φi : Vi 7→ Vi is the restriction of φ to Vi .
Definition 18. Let (G1 , G2 ) be ρ-correlated SBM(K, ~n, b, Λ) random graphs, and let x, y ∈ Gn .
1. For each of i = 1, 2, and j = 1, 2, . . . , K, let Gji = GiVj (resp., xj = xVj , y j = yVj ) be the
induced subgraph of Gi (resp., fixed x, y ∈ Gn ) restricted to Vj .

32

j,`
j,`
2. For j, ` ∈ [K] with j < `, let Gj,`
i (resp., x , y ) be the induced bipartite subgraph of Gi

(resp., x, y) composed of the edges in Gi (resp., x, y) between vertex sets Vj and V` .
The key to restricting our attention to permutations in Π(n)∗ is the following. Working with
permutations in Π(n)∗ allows us to split the SBM random graphs along block assignments, and
then tackle each block (and each bipartite between-block) subgraph separately. Before formalizing
this in Claim 20, we will need to define the analogues of correlated bipartite graphs. To this end,
if Bm1 ,m2 is the set of all labeled bipartite graphs G = (U, V, E) with |U | = m1 , |V | = m2 , and
E ⊂ U × V, then we define:
Definition 19. Two m1 m2 -vertex bipartite random graphs (G1 , G2 ) ∈ Bm1 ,m2 × Bm1 ,m2 are ρcorrelated Bipartite(m1 , m2 , p) random graphs (abbreviated ρ-Bipartite) if
i. For each i = 1, 2, Gi ∈ Bm1 ,m2 , and edges between the bipartite sets U and V are independently present with common probability p;
ii. The random variables {1[(j, k) ∈ E(Gi )]}i=1,2;j∈U,k∈V are collectively independent except that
for each (j, k) ∈ U × V, the correlation between 1[(j, k) ∈ E(G1 )] and 1[(j, k) ∈ E(G2 )] is
ρ ≥ 0.
The deterministic shuffling of ρ-Bipartite graphs can be defined completely analogously to the
φ-shuffled graph of Section 2.2. To wit, if x ∈ Bm1 ,m2 , and τ ∈ Sm1 , φ ∈ Sm2 , we define the
[τ, φ]-shuffled graph, denoted by [τ, φ](x) = (V, E[τ,φ](x) ) ∈ Bm1 ,m2 , via (i, j) ∈ Ex iff (τ (i), φ(j)) ∈
E[τ,φ](x) ; i.e., U is shuffled according to τ and V is shuffled according to φ. The following claim is
immediate.
Claim 20. Let (G1 , G2 ) ∼ ρ-SBM(K, ~n, b, Λ), and let φ ∈ Π(n)∗ .
1. P(G2 = y) = P(G2 = φ(y)) for all y ∈ Gn ;
2. For each j = 1, 2, . . . , K, (Gj1 , Gj2 ) are distributed as ρ-ER(nj , Bj,j ) random graphs;
j,`
3. For j, ` ∈ [K] with j < `, (Gj,`
1 , G2 ) are distributed as ρ-Bipartite(nj , n` , Bj,` );

33

4. The collection of graph pairs



(Gi1 , Gi2 )

[
i∈[K]

j,`
(Gj,`
1 , G2 )

j,`∈[K], j<`

is mutually independent.
Analogues of Theorem 10 hold in the ρ-ER and ρ-Bipartite settings as well. The following
Lemma is proved similarly to Theorem 10, and so the proof is only briefly sketched.
Lemma 21. With notation as above,
i) If (G1 , G2 ) ∼ ρ-ER(m, p) with respective adjacency matrices A and B. If ρ = ω

q

log m
m


then

there exists a C > 0 such that

P(∃ φ ∈ Π(m) \ {idm } s.t. kA − Pφ BPφT k2F − kA − Bk2F ≤ Cmρ) = O(e−3 log m ).

(5)

ii) If (G1 , G2 ) ∼ ρ-Bipartite(m1 , m2 , p) with respective adjacency matrices A and B, and let m =
q

log m
min(m1 , m2 ). If ρ = ω
then there exists a C > 0 such that
m

P(∃ (φ, τ ) ∈ Π(m1 , m2 ) \ {idm1 ,m2 } s.t. kA − Pφ BPτT k2F − kA − Bk2F ≤ Cmρ) = O(e−3 log m ), (6)

where Π(m1 , m2 ) = Π(m1 ) × Π(m2 ), and idm1 ,m2 = (idm1 , idm2 ).
Proof. We will sketch the proof of part i) with part ii) following mutadis mutandis. For the
moment, fix φ ∈ Π(m) with s(φ) = k. For x, y ∈ Gn , define

 
V
FA (x, y, φ) := {u, v} ∈
s.t. u x v, u ∼φ(x) v, and u φ(y)
2

 
V
FO (x, y, φ) := {u, v} ∈
s.t. u ∼x v, u φ(x) v, and u ∼φ(y)
2


v ;

v .

We then have (if x and y have adjacency matrices A and B)
1
1
(kA − Pφ BPφT k2F − kA − Bk2F ) = kA − Pφ APφT k2F − 2FA (x, y, φ) − 2FO (x, y, φ).
2
2
34

(7)
(8)

k
2



+ k(m − k), applying [22, Proposition 3.2] to (G1 , G2 ) ∼ ρ-ER(m, p)
p
yields that there exists a constant c (which can be taken to be 48p(1 − p)) such that for m
With mk defined via mk =

sufficiently large

P G = g s.t.
1
kA
2

Conditioning on


p
1
T 2
kAg − Pφ Ag Pφ kF − 2mk p(1 − p) ≥ 2c mk k log m ≤ 2e−3k log m .
2

(9)

− Pφ APφT k2F = ∆, FO (G1 , G2 , φ) ∼ Bin(∆/2, p(1 − ρ)) independent of

FA (G1 , G2 , φ) ∼ Bin(∆/2, (1 − p)(1 − ρ)). Hoeffding’s inequality then yields



∆
ρ 1
2
T 2
P FO (G1 , G2 , φ) ≥
kA − Pφ APφ kF = ∆ ≤ e−∆ρ /9 ;
p(1 − ρ) +
2
3 2



∆
ρ 1
2
T 2
P FA (G1 , G2 , φ) ≥
(1 − p)(1 − ρ) +
kA − Pφ APφ kF = ∆ ≤ e−∆ρ /9 .
2
3 2

(10)
(11)

Unconditioning (10)–(11) combined with (9), and summing over k yields the desired result.
Next, note that



I(G1 ; G2 ) − I(G1 ; σ ∗ (G2 )) = −

X

P(g1 , g2 ) log 

X
τ ∈Π(n)∗

g1 ∈Gn ,
g2 ∈Gn

P(g1 , τ (g2 )) 
.
P(g1 , g2 )|Π(n)∗ |

The utility of Eq. (5) and (6) in the present ρ-SBM setting can be realized as follows. For each
i, j ∈ [K], we define ξi,j := 1 +

ρ
(1−Λi,j )Λi,j (1−ρ)2

> 1. Combining the above yields (where A1 is the

adjacency matrix of g1 and B2 the adjacency matrix of g2 , and for j, ` ∈ [K] Aj1 is A1 restricted
j,`
to g1j , and Aj,`
1 is A! restricted to g1 ; similarly for B2 )

I(G1 ; G2 ) − I(G1 ; σ ∗ (G2 ))
=−

X

P(g1 , g2 ) log

X
τ ∈Π(n)∗

g1 ∈Gn ,
g2 ∈Gn

Y
j,`∈[K]
s.t. j<`



Y
1
1 j
j
j T 2
j 2
exp log(ξj,j ) kA1 − B2 kF − kA1 − Pτj B2 Pτj kF
|Π(n)∗ |
4
j∈[K]




1  j,`
j,` 2
j,`
j,` T 2
exp log(ξj,` ) kA1 − B2 kF − kA1 − Pτj B2 Pτ` kF
4

35

!

If mini ni = Θ(n) and ρ = ω

q

log n
n



, for n sufficiently large there exists constants C > 0, C 0 > 0

such that for all τ ∈ Π(n)∗ ,

−


1  j,`
j,` 2
k
< −Cnρ
−
B
kA1 − Pτj B2j,` PτT` k2F − kAj,`
2
1
F
4

and
−


1 j
kA1 − Pτj B2j PτTj k2F − kAj1 − B2j k2F < −Cnρ
4

with probability at least 1 − C 0 e−3 log n . Therefore, for n sufficiently large there exists a constant
C 00 > 0 such that

I(G1 ; G2 ) − I(G1 ; σ ∗ (G2 )) ≥ C 00 nρ2 − C 0 e−3 log n n2 = Ω(nρ2 )

(12)

as desired. The proof is then completed by applying straightforward application of the information
processing inequality which yields the following proposition.
Proposition 22. Let σ be uniformly distributed on Π(n) independent of σ ∗ uniformly distributed
on Π(n)∗ . With notation as above, I(G1 ; σ(G2 )) ≤ I(G1 ; σ ∗ (G2 )).
The proof of Proposition 22 is straightforward and hence is omitted.

A.3

Proof of Theorem 10

Herein, we prove Theorem 10. With notation and assumptions as in the Theorem, for τ ∈ Π(n),
define Xτ,A,B := 21 (kA − Pτ BPτT k2F − kA − Bk2F ). Fix τ 6= idn ∈ Π(n), and suppose that τ permutes
the labels of exactly m ≥ 2 vertices (so that |{v : τ (v) = v}| = n − m). For each pair 1 ≤ i, j ≤ K,
let
τi,j := {v ∈ Vi s.t. τ (v) ∈ Vj , v 6= τ (v)} ,
and let
fiτ = {v ∈ Vi s.t. τ (v) = v} .
36

Note that for each i ∈ [K] and each τ ∈ Π(n), we have that

ni − fiτ =

X

τi,j =

j

X

τj,i .

j

As in the proof of Lemma 21, we note that if x, y ∈ Gn with adjacency matrices Ax and By
respectively, Xτ,Ax ,By = 21 kAx − Pτ Ax PτT k2F − 2FA − 2FO , where FA := FA (x, y, τ ) and FO :=
FO (x, y, τ ) are defined as in Eq. (7)–(8). We call the errors induced by τ on x of the form
u x v and u ∼τ (x) v addition errors (so that FA is the number of fixed addition errors), and the
errors induced by τ on x of the form u ∼x v and u τ (x) v occlusion errors (so that FO is the
number of fixed occlusion errors).
We will first show that if (G1 , G2 ) ∼ ρ−SBM(K, ~n, b, Λ) satisfying the assumptions in the
theorem, then with sufficiently high probability (G1 , G2 ) = (x, y) satisfying
1
kAx − Pτ Ax PτT k2F > 2FA (x, y, τ ) + 2FO (x, y, τ ),
2
implying that Xτ,Ax ,By > 0. To this end, with A and B the random adjacency matrices associated
with G1 and G2 respectively, note that
1
kA − Pτ AT PτT k2F =
2
=

X

(Av,v0 − Aτ (v),τ (v0 ) )2

{v,v 0 }∈(V2 )
K
X

X

Av,v0 (1 − Aτ (v),τ (v0 ) ) + (1 − Av,v0 )Aτ (v),τ (v0 )

(13)

X

(14)

i=1 {v,v 0 }∈(Vi )
2

+

K X
K
X
i=1 j>i

(v,v 0 )∈V

Av,v0 (1 − Aτ (v),τ (v0 ) ) + (1 − Av,v0 )Aτ (v),τ (v0 ) .

i ×Vj

Consider the sum in (13). For each i ∈ [K], the sum can be further decomposed into three terms:
1. For each j ∈ [K] there are n1 (i, i, j, j) :=

τi,j 
2

terms with both v 6= τ (v) and v 0 6= τ (v 0 )
(1)

mapped to Vj by τ. The expected number of addition errors (denoted Ai,i,j,j ) contributed by

37

these terms is
(1)
E(Ai,i,j,j )

τ 

= i,j (1 − Λi,i )Λj,j ,
2
(1)

and the expected number of occlusion errors (denoted Oi,i,j,j ) contributed by these terms is
(1)
E(Oi,i,j,j )

(1)

τ 

= i,j Λi,i (1 − Λj,j ).
2

(1)

Conditioning on Ai,i,j,j and Oi,i,j,j , each addition error is independently corrected in B with
probability (1 − ρ)(1 − Λj,j ), and each occlusion error is independently corrected (independently also of the corrected addition errors) in B with probability (1 − ρ)Λj,j .
2. For each j ∈ [K], ` ∈ [K], ` > j, there are n2 (i, i, j, `) := τi,j τi,` terms with v 6= τ (v) ∈
(2)

Vj and v 0 6= τ (v 0 ) ∈ V` . The expected number of addition errors (denoted Ai,i,j,` ) contributed
by these terms is
(2)

E(Ai,i,j,` ) = τi,j τi,` (1 − Λi,i )Λj,` ,
(2)

and the expected number of occlusion errors (denoted Oi,i,j,` )contributed by these terms is
(2)

E(Oi,i,j,` ) = τi,j τi,` Λi,i (1 − Λj,` ).
(2)

(2)

Conditioning on Ai,i,j,` and Oi,i,j,` , each addition error is independently corrected in B with
probability (1 − ρ)(1 − Λj,` ), and each occlusion error is independently corrected (independently also of the corrected addition errors) in B with probability (1 − ρ)Λj,` .
3. For each j ∈ [K], there are n3 (i, i, i, j) := fiτ τi,j terms with v = τ (v) ∈ Vi and v 0 6= τ (v 0 ) ∈
(3)

Vj . The expected number of addition errors (denoted Ai,i,i,j ) contributed by these terms is
(3)

E(Ai,i,i,j ) = fiτ τi,j (1 − Λi,i )Λi,j ,

38

(3)

and the expected number of occlusion errors (denoted Oi,i,i,j ) contributed by these terms is
(3)

E(Oi,i,i,j ) = fiτ τi,j Λi,i (1 − Λi,j ).
(3)

(3)

Conditioning on Ai,i,i,j and Oi,i,i,j , each addition error is independently corrected in B with
probability (1 − ρ)(1 − Λi,j ), and each occlusion error is independently corrected (independently also of the corrected addition errors) in B with probability (1 − ρ)Λi,j .
In the sum in (14), for each i, j ∈ [K] with j > i, the sum can be further decomposed into three
terms:
4. For each ` ∈ [K], h ∈ [K], there are n4 (i, j, h, `) := τi,h τj,` terms with v ∈ Vi , v 6= τ (v) ∈
(4)

Vh and v 0 ∈ Vj , v 0 6= τ (v 0 ) ∈ V` . The expected number of addition errors (denoted Ai,j,h,` )
contributed by these terms is
(4)

E(Ai,j,h,` ) = τi,h τj,` (1 − Λi,j )Λh,` ,
(4)

and the expected number of occlusion errors (denoted Oi,j,h,` ) contributed by these terms is
(4)

E(Oi,j,h,` ) = τi,h τj,` Λi,j (1 − Λh,` ).
(4)

(4)

Conditioning on Ai,j,h,` and Oi,j,h,` , each addition error is independently corrected in B with
probability (1 − ρ)(1 − Λh,` ), and each occlusion error is independently corrected (independently also of the corrected addition errors) in B with probability (1 − ρ)Λh,` .
5. For each ` ∈ [K], there are n5 (i, j, i, `) := fiτ τj,` terms with v = τ (v) ∈ Vi and v 0 ∈ Vj , v 0 6=
(5)

τ (v 0 ) ∈ V` . The expected number of addition errors (denoted Ai,j,i,` ) contributed by these
terms is
(5)

E(Ai,j,i,` ) = fiτ τj,` (1 − Λi,j )Λi,` ,

39

(5)

and the expected number of occlusion errors (denoted Oi,j,i,` ) contributed by these terms is
(5)

E(Oi,j,i,` ) = fiτ τj,` Λi,j (1 − Λi,` ).
(5)

(5)

Conditioning on Ai,j,i,` and Oi,j,i,` , each addition error is independently corrected in B with
probability (1 − ρ)(1 − Λi,` ), and each occlusion error is independently corrected (independently also of the corrected addition errors) in B with probability (1 − ρ)Λi,` .
6. For each ` ∈ [K], there are n6 (i, j, `, j) := fjτ τi,` terms with v 0 = τ (v 0 ) ∈ Vj and v ∈
(6)

Vi , v 6= τ (v) ∈ V` . The expected number of addition errors (denoted Ai,j,`,j ) contributed
by these terms is
(6)

E(Ai,j,`,j ) = fjτ τi,` (1 − Λi,j )Λ`,j ,
(6)

and the expected number of occlusion errors (denoted Oi,j,`,j ) contributed by these terms is
(6)

E(Oi,j,`,j ) = fjτ τi,` Λi,j (1 − Λ`,j ).
(6)

(6)

Conditioning on Ai,j,`,j and Oi,j,`,j , each addition error is independently corrected in B with
probability (1 − ρ)(1 − Λ`,j ), and each occlusion error is independently corrected (independently also of the corrected addition errors) in B with probability (1 − ρ)Λ`,j .
For each s ∈ [6] and each feasible set of indices (a, b, c, d) ∈ K 4 , note that ns (a, b, c, d) = O(mn).
√
If ns (a, b, c, d) ≥ m n log n, then an application of [22, Proposition 3.2] yields that there exists a
constant γ > 0 such that for n sufficiently large


p
p
(s)
(s)
P |Aa,b,c,d − EAa,b,c,d | > γ ns (a, b, c, d) m log n ≤ 2e−3m log n ,

(15)

and

P

(s)
|Oa,b,c,d

−

(s)
EOa,b,c,d |


p
p
> γ ns (a, b, c, d) m log n ≤ 2e−3m log n .

40

(16)

√
Alternatively, if ns (a, b, c, d) < m n log n, then it is immediate that
p
p
(s)
(s)
(s)
(s)
|Aa,b,c,d − EAa,b,c,d | ≤ m n log n, and |Oa,b,c,d − EOa,b,c,d | ≤ m n log n.

(17)

Denote by E the event that A satisfies
(s)

(s)

p
ns (a, b, c, d) m log n,
p
p
(s)
(s)
|Oa,b,c,d − EOa,b,c,d | ≤ γ ns (a, b, c, d) m log n
|Aa,b,c,d − EAa,b,c,d | ≤ γ

p

√
for all s ∈ [6] and feasible indices (a, b, c, d) ∈ K 4 satisfying ns (a, b, c, d) ≥ m n log n. Eq.
(15)–(16) and a simple union bound imply that

P(E c ) ≤ 24K 4 e−3m log n .

(18)

At each sample point ε in E, recalling ns (a, b, c, d) = O(mn), we have that there exists a constant
C > 0 (which can be chosen independent of ε) such that
kA − Pτ AT PτT k2F
−E
2



kA − Pτ AT PτT k2F
2



p
≤ Cm n log n.

A brief calculation then yields

E FA + FO


ε

"
≤ (1 − ρ)

K X
K  τ 
X

i,j

i=1 j=1

+

K
K X
X

fiτ τi,j Λi,j (1 − Λi,j ) +

i=1 j=1

+

K X
K X
K
X
i=1 j>i `=1

2

Λj,j (1 − Λj,j ) +

K X
K X
K
X

τi,j τi,` Λj,` (1 − Λj,` )

i=1 j=1 `>j

K X
K X
K
K X
X

τi,h τj,` Λh,` (1 − Λh,` )

i=1 j>i `=1 h=1

fiτ τj,` Λi,` (1 − Λi,` ) +

K X
K X
K
X

#
p
fjτ τi,` Λ`,j (1 − Λ`,j ) + Cm n log n,

(19)

i=1 j>i `=1

where conditioning on ε is understood to mean conditioning on a value of A that satisfies the

41

conditions imposed by E. Note that the term in the brackets in Eq. (19) is equal to
K X
K X
K
K X
K  τ 
K X
K
X
X
X
i,j
τ τ
Λi,i (1 − Λi,i ) +
i,j i,` Λi,i (1 − Λi,i ) +
fiτ τi,j Λi,i (1 − Λi,i )
2
i=1 j=1 `>j
i=1 j=1
i=1 j=1

+

K X
K X
K X
K
X

τi,h τj,` Λi,j (1

− Λi,j ) +

i=1 j>i `=1 h=1

+

K X
K X
K
X

K X
K X
K
X

fiτ τj,` Λi,j (1 − Λi,j )

i=1 j>i `=1

fjτ τi,` Λj,i (1 − Λj,i ).

(20)

i=1 j>i `=1

Also note that for any indices i, j, k, ` ∈ [K],

Λi,j (1 − Λi,j ) + Λk,` (1 − Λk,` ) ≤ Λi,j (1 − Λk,` ) + Λk,` (1 − Λi,j ).

(21)

Combining Eqs. (19) and (20) with Eq. (21) then yields that for ε ∈ E
1−ρ
E (FA + FO | ε) ≤
E
2



1
kA − Pτ AT PτT k2F
2



p
+ Cm n log n.

Applying Hoeffding’s inequality to F := FA + FO yields that there exists constants c1 > 0, c2 , and
c3 , such that for n sufficiently large

1
P 2F ≥ kA − Pτ AT PτT k2F
2


ε



1
T T 2
= P 2F − 2E(F |ε) ≥ kA − Pτ A Pτ kF − 2E(F |ε) ε
2


p

ρ
≤ P F − E(F |ε) ≥ E kA − Pτ AT PτT k2F −3Cm n log n ε
4


p
2
≤ exp − c1 ρ mn + c2 ρm n log n + c3 m log n ,

where the last inequality follows from the fact that that F is the sum of at most

m
2



+ m(n − m)

independent Bernoulli random variables. Therefore, there exists a constant α > 0 such that if
q
ρ > α logn n then


1
T T 2
P 2F ≥ kA − Pτ A Pτ kF ε ≤ e−3m log n .
2

42

Combined with P(E c ) ≤ 24K 4 e−3m log n , we have that, unconditionally,


1
P 2F ≥ kA − Pτ AT PτT k2F
2



≤ (24K 4 + 1)e−3m log n .

Summing over τ and n yields that


P ∃ τ ∈ Π(n) with Xτ,A,B ≤ −1 ≤ (24K 4 + 1)e−3 log n ,

as desired.

A.4

Proof of Theorem 12

In this section, we will prove Theorem 12. Recall that for τ ∈ Π(n), we define Xτ,A,B := 12 (kA −
Pτ BPτT k2F − kA − Bk2F ). The proof of Theorem 12 will proceed as follows. For each i = 1, 2, . . . , N ,
P
let Eτi ,A,B be the event {Xτi ,A,B ≤ −1}, and let X = i 1{Eτi ,A,B }. We first show in Lemma 23
that for judiciously chosen β,

E(X) = Ω

N
√
1/5
n
log n


.

In Lemmas 24–25, we show that

Var(X) = O

N2
√
n


.

As X is a nonnegative integer-valued random variable, we apply the second moment method [3,
√

log n
=
O
Theorem 4.3.1] to derive P(X = 0) ≤ Var(X)
= o(1) as desired. We now establish the
E(X)2
n1/10
supporting Lemmas 23–25. We begin by noting that if τ = i ↔ j is a within-block transposition,
i.e., b(i) = b(τ (i)) = b(j) = b(τ (j)), then
X

Xτ := Xτ,A,B : = kA − Pτ BPτT k2F − kA − Bk2F = 2

A`,k B`,k − A`,k Bτ (`),τ (k)

`,k s.t. τ (`)6=`
or τ (k)6=k

=4

X

(Ai,k Bi,k − Ai,k Bj,k ) + 4

k6=i,j

X
k6=i,j

43

(Aj,k Bj,k − Aj,k Bi,k )



From this, we immediately arrive at
X

Xτ = 4

(Ai,k − Aj,k )(Bi,k − Bj,k ).

(22)

k6=i,j

(k)

For each k 6= i, j, the terms Xτ

(k)

= Xτ,A,B := 4(Ai,k −Aj,k )(Bi,k −Bj,k ) in Eq. (22) are independent

with mean
µk := E (4(Ai,k − Aj,k )(Bi,k − Bj,k )) = 8Λb(i),b(k) (1 − Λb(i),b(k) )ρ,
and variance

σk2 = Var (4(Ai,k − Aj,k )(Bi,k − Bj,k ))
= 16 2Λb(i),b(k) (1 − Λb(i),b(k) )ρ + 4Λ2b(i),b(k) (1 − Λb(i),b(k) )2 + 8(1 − Λb(i),b(k) )Λ3b(i),b(k) ρ

2
− 8Λ2b(i),b(k) (1 − Λb(i),b(k) )ρ + 4ρ2 Λ2b(i),b(k) (1 − Λb(i),b(k) )2 − 8Λb(i),b(k) (1 − Λb(i),b(k) )ρ .

Note here that for all k,

lim σk2 = 48Λ2b(i),b(k) (1 − Λb(i),b(k) )2 > 0.

lim µk = 0,

ρ→0

Next, note that ξk := E



ρ→0

4(Ai,k − Aj,k )(Bi,k − Bj,k ) − µk

3



≤ 83 and is bounded away from 0 as

ρ → 0. We define
µτ =

X

µk , στ2 =

k6=i,j

X
k6=i,j

σk2 , ξτ =

X

ξk .

k6=i,j

The classic Berry-Esseen theorem [12, Theorem XVI.5.2] yields

6ξτ
Xτ − µτ
≤ x − Φ(x) ≤ 3 ,
sup P
στ
στ
x


where Φ(·) is the standard normal cumulative distribution function. Using the inequality [1, Eq.
7.1.13]
1
2
√
e−x <
x + x2 + 2

Z

∞

2

e−t dt ≤

x

44

1
2
q
e−x for all x ≥ 0,
x + x2 + π4

which is equivalent to

√

π x+

1
√

x2

+2

we have that (with x :=

e

−x2

<1−Φ

√

1
2
q
2x ≤ √ 
 e−x for all x ≥ 0,
π x + x2 + π4


(23)

1+µτ
√
)
2στ


P(Xτ ≤ −1) = P

√
Xτ − µτ
≤ − 2x
στ



6ξτ
1
2
q
≤√ 
 e−x + 3 ,
στ
π x + x2 + π4

(24)

and

P(Xτ ≤ −1) = P

√
Xτ − µτ
≤ − 2x
στ


≥√

π x+

1
√

2

x2 + 2

 e−x −

6ξτ
.
στ3

Lemma 23. With notation as above, there exists a constant β such that if ρ ≤


1
√
P(Xτ ≤ −1) = Ω n1/4 log n
Proof. We first note that if ρ ≤

q

β log n
,
n

q

(25)

β log n
,
n

then

then there exists a constant c1 > 0 such that for n

sufficiently large, στ2 ≥ c1 n. Therefore,
r
√
1 + 2 βn log n
2β log n
1 + µτ
1 + 2ρn
1
√
≤
=
,
x= √
≤ √
+√
c1
2c1 n
2c1 n
2c1 n
2στ
and β can be chosen so that ρ ≤

q

β log n
n

implies that x ≤

q

log n
.
5

(26)

With this choice of β, The

lower bound in Eq. (25) is then bounded by

√

π x+

1
√

x2 + 2

e

−x2





exp − log5 n
6ξτ
1
−1/2

 −Θ n
√
− 3 ≥
=Ω
,
√ q log n q log n
στ
n1/5 log n
+
+2
π
5
5

as desired.

45

Recalling that Eτi = Eτi ,A,B is the event {Xτi ≤ −1}, Lemma 23 is equivalent to

E(1{Eτi }) = P(Eτi ) = P(Xτi ≤ −1) = Ω

1
√
1/5
n
log n


.

It follows immediately that (where N is as defined in Theorem 12)

E(X) = Ω

N
√
1/5
n
log n


.

We now turn our attention to bounding Var(X).
Lemma 24. With notation as above and assumptions as in Theorem 12, let τ1 = i ↔ j and
τ2 = h ↔ ` be two disjoint, within-block transpositions. There exists constants C1 > 0 and C2 > 0,


 


1
1
2
Cov(1{Eτi }, 1{Eτj }) ≤ C2 exp −C1 ρ n + Θ √
Θ √
n
n
Proof. Note

Cov(1{Eτ1 }, 1{Eτ2 }) = P(Xτ1 ≤ −1, Xτ2 ≤ −1) − P(Xτ1 ≤ −1)P(Xτ2 ≤ −1)
(k)

Observe that Xτ1 and Xτ2 are each then the sum of n − 2 independent terms ({Xτ1 }k6=i,j and
(k)

{Xτ2 }k6=h,` resp.) which are collectively independent except for the four terms
Xτ(h)
= 4(Ai,h − Aj,h )(Bi,h − Bj,h ), Xτ(`)
= 4(Ai,` − Aj,` )(Bi,` − Bj,` ),
1
1
Xτ(i)
= 4(Ah,i − A`,i )(Bh,i − B`,i ), Xτ(j)
= 4(Ah,j − A`,j )(Bh,j − B`,j ).
2
2
(j)
eτ2 = Xτ2 − Xτ(i)
e
e
Let X
2 − Xτ2 , so that Xτ1 and Xτ2 are independent. Noting that |Xτ2 − Xτ2 | ≤ 8,

we have

eτ2 ≤ 7) = P(Xτ ≤ −1)P(X
eτ ≤ 7).
P(Xτ1 ≤ −1, Xτ2 ≤ −1) ≤ P(Xτ1 ≤ −1, X
i
j

46

Therefore,



e
Cov(1{Eτ1 }, 1{Eτ2 }) ≤ P(Xτ1 ≤ −1) P(Xτ2 ≤ 7) − P(Xτ2 ≤ −1)


eτ2 ≤ 7) − P(X
eτ2 ≤ −9)
≤ P(Xτ1 ≤ −1) P(X

(27)

As in Eq. (26), there is a constant c2 > 0 such that στ2 ≤ c2 n for n sufficiently large, and
√
1 + µ τ1
1 + 8η(1 − η)ρn
8η(1 − η)ρn
8η(1 − η)ρ n
√
√
√
x1 := √
≥
≥
=
,
2c2 n
2c2 n
2c2
2στ1

(28)

and from Eq. (24) we have that
 

√ 2
8η(1−η)ρ n
√
exp −
2c2
P(Xτ1 ≤ −1) ≤



+Θ



1
1
2
= exp −C1 ρ n + Θ √
.
2
n
2

1
√
n



(29)

eτ2 ), and σ̃τ2 = Var(X
eτ2 ). By the same approach used
for a constant C1 > 0. Define µ̃τ2 = E(X
2


 
eτ2 ∈ [−8, 7] = Θ √1 .
above, the Berry-Esseen theorem yields (suppressing the details) P X
n
Combined with Eq. (29), this yields the desired result.
We now combine Lemmas 23 and 24 to bound Var(Xτ ) where τ is a within-block transposition.
Lemma 25. With notation as above and assumptions as in Theorem 12, let τ be a within-block
transposition. We have that

Var(Xτ ) = O

N2
√
n



Proof. From Eq. (29) there exists a constant C1 > 0 such that

1
Var(1{Xτ ≤ −1}) = (1 − P(Xτ ≤ −1))P(Xτ ≤ −1) ≤ exp −C1 ρ2 n + Θ
2

47



1
√
n


.

Combined with Lemma 24,
N
2
Var(X) ≤ e−C1 ρ n + Θ
2



N
√
n



2



−C1 ρ2 n

+ N C2 e


+Θ

1
√
n




Θ

1
√
n




=O

N2
√
n



as desired.

A.5

Proof of Theorem 14

The key to the proof of Theorem 14 is the following consequence of Theorem 10: If (G1 , G2 ) ∼
p
ρ−correlated SBM(K, ~n, b, Λ) with ρ = ω( log n/n) and respective adjacency matrices A and B,
then argminP ∈Π(n) kAP − P BkF = {In } with high probability.
p
Proposition 26. Let (G1 , σ(G2 )) ∼ σ, ρ−correlated SBM(K, ~n, b, Λ) with ρ = ω( log n/n).


Under the assumptions of Theorem 10, we have that P Gσ(G2 )→G1 6= G2 = O(e−3 log n ).
Proof. To ease notation, define



P(x, y, z) = P (G1 , G2 , Gσ(G2 )→G1 ) = (x, y, z) ,


P(x, z) = P (G1 , Gσ(G2 )→G1 ) = (x, z) ,


P(x, y) = P (G1 , G2 ) = (x, y) .

Note that
∗
X
X


1{z ∈ Px,y
(y)}
P Gσ(G2 )→G1 6= G2 =
P(x, y, z) =
P(x, y)
∗
|Px,y (y)|
(x,y,z)
s.t. z6=y

=

X
(x,y,z) s.t. z6=y,
∗ (y)
z∈Px,y

(x,y,z)
s.t. z6=y

X
P(x, y)
=
∗ (y)|
|Px,y
x,y

X
∗ (y)
z∈Px,y

s.t. z6=y

48

P(x, y)
≤
∗ (y)|
|Px,y

X
x,y s.t.
∗ (y)6={y}
Px,y

P(x, y).

∗
∗
6= {I}, this implies
(y) 6= {y} ⇒ Px,y
As Px,y

X
x,y s.t.
∗ (y)6={y}
Px,y

P(x, y) ≤

X

P(x, y) = O(e−3 log n ),

x,y s.t.
∗ 6={I}
Px,y

where the last equality is an immediate consequence of Theorem 10.
Theorem 14 is then a straightforward application of Fano’s inequality, which yields that





H Gσ(G2 )→G1 |G2 = o(1), and H G2 |Gσ(G2 )→G1 = o(1).




By the chain rule for entropy, it follows immediately that H G2 |G1 = H Gσ(G2 )→G1 |G1 + o(1),


 
and H Gσ(G2 )→G1 = H G2 + o(1). Combined, this yields that I(G1 ; G2 ) − I(G1 ; Gσ(G2 )→G1 ) =
o(1), as desired.

References
[1] M. Abramowitz and I. A. Stegun. Handbook of mathematical functions: with formulas, graphs,
and mathematical tables. Number 55. Courier Corporation, 1964.
[2] E. M. Airoldi, T. B. Costa, and S. H. Chan. Stochastic blockmodel approximation of a
graphon: Theory and consistent estimation. Advances in Neural Information Processing
Systems, 26:692–700, 2013.
[3] N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2015.
[4] D. M. Asta and C. R. 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.

49

[5] L. Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of
the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 684–697. ACM,
2016.
[6] E. Bullmore and O. Sporns. Complex brain networks: graph theoretical analysis of structural
and functional systems. Nature Reviews Neuroscience, 10(3):186–198, 2009.
[7] P. J. Carrington, J. Scott, and S. Wasserman. Models and methods in social network analysis,
volume 28. Cambridge university press, 2005.
[8] 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, page e1142041.
Taylor & Francis, 2016.
[9] D. Choi and P. J. Wolfe. Co-clustering separately exchangeable network data. The Annals
of Statistics, 42(1):29–63, 2014.
[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] T. M. Cover and J. A. Thomas. Elements of information theory. John Wiley & Sons, 2012.
[12] W. Feller. An introduction to probability theory and its applications, volume 2. John Wiley
& Sons, 2008.
[13] M. Fiori, P. Sprechmann, J. Vogelstein, P. Mus, and G. Sapiro. Robust multimodal graph
matching: Sparse coding meets graph matching. Advances in Neural Information Processing
Systems, pages 127–135, 2013.
[14] D. E. Fishkind, D. L. Sussman, M. Tang, J. T. Vogelstein, and C. E. Priebe. Consistent
adjacency-spectral partitioning for the stochastic block model when the model parameters
are unknown. SIAM Journal on Matrix Analysis and Applications, 34(1):23–39, 2013.
50

[15] D.E. Fishkind, S. Adali, H. G. Patsolic, L. Meng, Lyzinski V., and C.E. Priebe. Seeded graph
matching. arXiv preprint arXiv:1209.0367, 2017.
[16] 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.
[17] C. Fraley and A. E. Raftery. Mclust: Software for model-based cluster analysis. Journal of
Classification, 16(2):297–306, 1999.
[18] W. R. Gray, J. A. Bogovic, J. T. Vogelstein, B. A. Landman, J. L. Prince, and R. J. Vogelstein.
Magnetic resonance connectome automated pipeline: an overview. Pulse, IEEE, 3(2):42–48,
2012.
[19] D. Hardoon, S. Szedmak, and J. S. Shawe-Taylor. Canonical correlation analysis: An overview
with application to learning methods. Neural computation, 16(12):2639–2664, 2004.
[20] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social
networks, 5(2):109–137, 1983.
[21] A. Kandel, H. Bunke, and M. Last. Applied Graph Theory in Computer Vision and Pattern
Recognition, volume 1. Springer, 2007.
[22] 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.
[23] N. H. Lee and C. E. Priebe. A latent process model for time series of attributed random
graphs. Statistical inference for stochastic processes, 14(3):231–253, 2011.
[24] K. Levin, A. Athreya, M. Tang, V. Lyzinski, and C. E. Priebe. A central limit theorem for an
omnibus embedding of random dot product graphs. arXiv preprint arXiv:1705.09355, 2017.
[25] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395–416,
2007.
51

[26] V. Lyzinski, S. Adali, J. T. Vogelstein, Y. Park, and C. E. Priebe. Seeded graph matching via
joint optimization of fidelity and commensurability. arXiv preprint arXiv:1401.3813, 2014.
[27] V. Lyzinski, D. 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] V. Lyzinski, D.E. Fishkind, and C.E. Priebe. Seeded graph matching for correlated ErdosRenyi graphs. Journal of Machine Learning Research, 15:3513–3540, 2014.
[29] V. Lyzinski, Y. Park, C. E. Priebe, and M. Trosset. Fast embedding for jofc using the raw
stress criterion. Journal of Computational and Graphical Statistics, (just-accepted), 2017.
[30] 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.
[31] V. Lyzinski, D. L. Sussman, M. Tang, A. Athreya, and C. E. Priebe. Perfect clustering
for stochastic blockmodel graphs via adjacency spectral embedding. Electronic Journal of
Statistics, 8(2):2905–2922, 2014.
[32] E. Onaran, S. Garg, and E. Erkip. Optimal de-anonymization in random graphs with community structure. arXiv preprint arXiv:1602.01409, 2016.
[33] C. E. Priebe, N. H. Lee, Y. Park, and M. Tang. Attribute fusion in a latent process model for
time series of graphs. In The 2011 IEEE Workshop on Statistical Signal Processing (SSP2011),
2011.
[34] C.E. Priebe, D.J. Marchette, Z. Ma, and S. Adali. Manifold matching: joint optimization of
fidelity and commensurability. Brazilian Journal of Probability and Statistics, 27(3):377400,
2013.

52

[35] T. Qin and K. Rohe. Regularized spectral clustering under the degree-corrected stochastic
blockmodel. Advances in Neural Information Processing Systems, 2013.
[36] W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the
American Statistical association, 66(336):846–850, 1971.
[37] J. Richiardi, H. Eryilmaz, S. Schwartz, P. Vuilleumier, and D. Van De Ville. Decoding brain
states from fmri connectivity graphs. Neuroimage, 56(2):616–626, 2011.
[38] K. Rohe, S. Chatterjee, and B. Yu. Spectral clustering and the high-dimensional stochastic
blockmodel. Annals of Statistics, 39:1878–1915, 2011.
[39] C. Shen and C. E. Priebe. Manifold matching using shortest-path distance and joint neighborhood selection. Pattern Recognition Letters, 92:41–48, 2017.
[40] R. C. Steorts, R. Hall, and S. E. Fienberg. A bayesian approach to graphical record linkage and
deduplication. Journal of the American Statistical Association, 111(516):1660–1672, 2016.
[41] M. Sun and C. E. Priebe. Efficiency investigation of manifold matching for text document
classification. Pattern Recognition Letters, 34(11):1263–1269, 2013.
[42] M. Sun, C. E. Priebe, and M. Tang. Generalized canonical correlation analysis for disparate
data fusion. Pattern Recognition Letters, 34(2):194–200, 2013.
[43] D. L. Sussman, M. Tang, D. E. Fishkind, and C. E. Priebe. A consistent adjacency spectral
embedding for stochastic blockmodel graphs. Journal of the American Statistical Association,
107(499):1119–1128, 2012.
[44] M. Tang, A. Athreya, D. L. Sussman, V. Lyzinski, and C. E. Priebe. A nonparametric twosample hypothesis testing problem for random dot product graphs. Bernoulli, 23(3):1599–
1630, 2017.

53

[45] M. Tang, A. Athreya, D. L. Sussman, V. Lyzinski, and C. E. Priebe. A semiparametric twosample hypothesis testing problem for random dot product graphs. Journal of Computational
and Graphical Statistics, 26(2):344–354, 2017.
[46] M. Tang, Y. Park, N. H. Lee, and C. E. Priebe. Attribute fusion in a latent process model
for time series of graphs. IEEE Transactions on Signal Processing, 61(7):1721–1732, 2013.
[47] L. R. Varshney, B. L. Chen, E. Paniagua, D. H. Hall, and D. B. Chklovskii. Structural
properties of the caenorhabditis elegans neuronal network. PLoS computational biology,
7(2):e1001066, 2011.
[48] J. T. Vogelstein and C. E. Priebe. Shuffled graph classification: Theory and connectome
applications. Journal of Classification, 32(1):3–20, 2015.
[49] 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.
[50] H. Wang, M. Tang, Y. Park, and C. E. Priebe. Locality statistics for anomaly detection in
time series of graphs. Signal Processing, IEEE Transactions on, 62(3):703–717, 2014.
[51] Y. J. Wang and G. Y. Wong. Stochastic blockmodels for directed graphs. Journal of the
American Statistical Association, 82(397):8–19, 1987.
[52] J. G. White, E. Southgate, J. N. Thomson, and S. Brenner. The structure of the nervous
system of the nematode caenorhabditis elegans. Philosophical Transactions of the Royal
Society of London. B, Biological Sciences, 314(1165):1–340, 1986.
[53] P. J. Wolfe and S. C. Olhede.

Nonparametric graphon estimation.

http://arxiv.org/abs/1309/5936, 2013.

54

arXiv preprint at

[54] 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.
[55] 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.
[56] D. Zhang, B. I. P. Rubinstein, and J. Gemmell. Principled graph matching algorithms for
integrating multiple data sources. IEEE Transactions on Knowledge and Data Engineering,
27(10):2784–2796, 2015.

55

