1

Seeded Graph Matching: Efficient Algorithms
and Theoretical Guarantees
Farhad Shirani, Siddharth Garg, and Elza Erkip
{fsc265,siddharth.garg,elza}@nyu.edu

arXiv:1711.10360v1 [] 28 Nov 2017

Department of Electrical and Computer Engineering
New York University, New York, New York, 11201

Abstract
In this paper, a new information theoretic framework for graph matching is introduced. Using this
framework, the graph isomorphism and seeded graph matching problems are studied. The maximum degree
algorithm for graph isomorphism is analyzed and sufficient conditions for successful matching are rederived
using type analysis. Furthermore, a new seeded matching algorithm with polynomial time complexity is
introduced. The algorithm uses ‘typicality matching’ and techniques from point-to-point communications for
reliable matching. Assuming an Erdös-Rényi model on the correlated graph pair, it is shown that successful
matching is guaranteed when the number of seeds grows logarithmically with the number of vertices in the
graphs. The logarithmic coefficient is shown to be inversely proportional to the mutual information between
the edge variables in the two graphs.

I. Introduction
Network graphs emerge naturally in modeling a wide range of phenomena including social interactions,
database systems, biological systems, and epidemiology. In many applications such as DNA sequencing,
pattern recognition, and image processing, it is desirable to find algorithms to match correlated network
graphs. In other applications, such as social networks and database systems, privacy considerations require
the network operators to enforce security safeguards in order to preclude de-anonymization using graph
matching.
In this work, we consider two formulations of the graph matching problem: i) Graph Isomorphism: In
this formulation it is assumed that an agent is given two identical copies of the same graph. The vertices
in the first graph g1 are labeled. Whereas the second graph, g2 , is an unlabeled graph. The objective is to
This work was presented in the 51 st Annual Asilomar Conference on Signals, Systems, and Computers.

DRAFT

2

!"

!#

Fig. 1: The graph pair (g1 , g2 ) are correlated. The objective is to restore the labels in graph g2 based on the
labels in g1 and the seed vertices.

find the natural labeling of the vertices in g2 based on the labels in g1 [1], [2], [3], [4]. ii) Seeded Graph
Matching: In this formulation, g1 and g2 are two statistically correlated graphs. Here, it is assumed that
the agent is provided with additional side-information in the form of seeds. More precisely, for a small
subset of vertices, the correct labeling across both graphs g1 and g2 is given [5], [6], [7], [8], [9], [10], [11].
This is shown in Figure 1. There are various practical scenarios captured in this formulation. One pertinent
application is the de-anonymization of users who are members of multiple social networks. Currently, many
web users are members of multiple online social networks such as Facebook, Twitter, Google+, LinkedIn,
etc.. Each online network represents a subset of the users’ “real" ego-networks. Graph matching provides
algorithms to de-anonymize the users by reconciling these online network graphs, that is, to identify all the
accounts belonging to the same individual. In this context, the availability of seeds is justified by the fact
that a small fraction of individuals explicitly link their accounts across multiple networks. In this case, these
linked accounts can be used as seeds in the agent’s matching algorithm. It turns out, that in many cases, the
agent may leverage these connections to identify a very large fraction of the users in the network [5], [6],
[7], [8], [10].
Graph matching is a classical problem which is of significant interest in multiple disciplines. As a
result, there is a large body of work considering the problem under varying assumptions on the graph
statistics. The graph isomorphism problem was studied in [1], [2], [3], [4]. Under the Erdös- Rényi graph
model, tight necessary and sufficient conditions were derived [12], [13] and polynomial time algorithms were
proposed [1], [2], [4]. The problem of matching of correlated graphs was considered for pairs of Erdös- Rényi
graphs [14], [15], [16], [17], as well as graphs with community structure [18], [10], [9], [11]. Furthermore,
conditions for seeded and seedless graph matching were derived for general graph scenarios [5], [6], [7], [8].
While great progress has been made in determining the conditions for successful matching and providing
feasible matching algorithms, there are shortcomings in the current approaches. Many of the results provide
solutions which assume unbounded computational resources (i.e. existence results). Furthermore, performance

DRAFT

3

characterizations are often provided in the form of complex algebraic characterizations which lead to limited
insight for application in practical scenarios. In this work, we propose a new information theoretic framework
for the study of the fundamental limits of graph matching as well as for the design of feasible algorithms.
We use the new framework to study the graph isomorphism problem as well as seeded graph matching.
The contributions can be summarized as follows. In graph isomorphism, we use tools from information
theory such as concentration of measure properties and type analysis to analyze the sufficient conditions for
successful matching for the maximum degree algorithm studied in [1], [2]. We rederive the conditions for
successful matching given in [2] under the Erdös-Rényi graph model. In seeded matching, we propose a
new matching algorithm which is inspired by a fingerprinting strategy introduced recently in [19]. The new
algorithm makes use of information theoretic tools such as typicality as well as ideas from point-to-point
communications. This strategy has polynomial-time complexity and guarantees reliable matching under the
Erdös-Rényi graph model as long as the seed size Λ satisfies
!
log n
,
Λn > Θ
I(X1 ; X2 )
where I(X1 ; X2 ) represents the mutual information between the edge distributions in g1 and g2 and n is the
number of vertices. In contrast with [20], [10], which also consider the seeded de-anonymization problem,
our results have a clear information theoretic interpretation. That is, each seed provides roughly I(X1 ; X2 )
bits of information about the label of any unlabeled vertex. As a result, almost

log n
I(X1 ;X2 )

seeds are necessary

for successful matching.
The rest of the paper is organized as follows: In Section II we introduce our notation and problem
formulation, Section III considers the graph isomorphism problem, Section IV investigates seeded graph
matching, and Section V concludes the paper.

II. Problem Formulation
In this section, we construct the foundations of our study of the graph matching problem by providing
a rigorous formalization of the problem. We assume a stochastic model where the graphs are generated
randomly based on an underlying distribution. Particularly, the two graphs are produced based on the ErdösRényi model. Furthermore, the edges in the two graphs are statistically correlated through a joint probability
distribution. More precisely, each edge in the second graph is correlated with its corresponding edge in the
first graph and is independent of all other edges. The first graph is labeled whereas the second graph is
unlabeled. The objective is to determine the labeling of the second graph which conforms with the joint
distribution between the edges of the two graphs. We proceed by presenting our formalization of the graph
matching problem.

DRAFT

4

Definition 1. An unlabeled graph g consists of a pair (Vn , En ). The set Vn = {vn,1 , vn,2 , · · · , vn,n } is called the
set of vertices of the graph, and the set En ⊂ {(vn,i , vn, j )|i ∈ [1, n], j ∈ [1, n]} is called the set of edges of the
graph. For a given vertex vn,i , i ∈ [1, n] the set of neighboring vertices is defined as En,i = {vn, j |(vn,i , vn, j ) ∈ En }.
The degree of vn,i is defined as dvn,i = |En,i |.
Definition 2. For an unlabeled graph g = (Vn , En ), a labeling is defined as a bijective function σ : Vn →
[1, n].
Definition 3. A labeled graph g̃ consists of a pair (g, σ), where g is an unlabeled graph and σ is a labeling
for g.
Definition 4. For a given p ∈ [0, 1], an Erdös-Rényi (ER) graph gn,p is a randomly generated unlabeled
graph with vertex set Vn and edge set En , such that
n
Pr(gn,p ) = p|En | (1 − p)((2)−|En |) .

In this work, we consider families of correlated pairs of labeled Erdös-Rényi graphs g

n,Pn,X1 ,X2

= (g̃1n,pn,1 , g̃2n,pn,2 ).

Definition 5. For a given joint distribution PX1 ,X2 on binary random variables X1 and X2 , a correlated pair
of labeled Erdös-Renyi (CER) graphs g̃

n,PX1 ,X2

= (g̃1n,p1 , g̃2n,p2 ) is characterized by: i) the pair of Erdös-Renyi

graphs gin,pi , i ∈ {1, 2}, ii) the pair of labelings σi for the unlabeled graphs gin,p1 , i ∈ {1, 2}, and iii) the
probability distribution PX1 ,X2 (x1 , x2 ), (x1 , x2 ) ∈ {0, 1}2 , such that:
1)The pair gin,pi , i ∈ {1, 2} have the same set of vertices Vn = Vn1 = Vn2 .
2) The marginals satisfy PXi (Xi = 1) = pi , i ∈ {1, 2}.
3) For any two edges ei = (vin,1 , vin,2 ), i ∈ {1, 2}, we have





 
if σ1j (v1n, j ) = σ2j (v2n, j ), j ∈ {1, 2}

PX1 ,X2 (α, β),
1
1
2
2
Pr 1(e ∈ En ) = α, 1(e ∈ En ) = β) = 
, ∀α, β ∈ {0, 1}2 ,




PX1 (α)PX2 (β), Otherwise
where 1(·) is the indicator function.
Definition 6. For a given joint distribution PX1 ,X2 , a correlated pair of partially labeled Erdös-Renyi (CPER)
graphs g

n,PX1 ,X2
1

= (g̃1n,p1 , g2n,p2 ) is characterized by: i) the pair of Erdös-Renyi graphs gin,pi , i ∈ {1, 2}, ii) a

labeling σ for the unlabeled graph g1n,p1 , and iii) the probability distribution PX1 ,X2 (x1 , x2 ), (x1 , x2 ) ∈ {0, 1}2 ,
such that there exists a labeling σ2 for the graph g2n,p2 for which (g̃1n,p1 , g̃2n,p2 ) is a CER, where g̃2n,p2 , (g2n,p2 , σ2 ).
The following defines a matching algorithm:

DRAFT

5

Definition 7. A matching algorithm for the family of CPERs g
7→ σ̂2n such that P(σ2n = σ̂2n )
n,Pn,X1 ,X2
(g̃1n,pn,1 , g̃2n,pn,2 ) is a CER, where g̃2n,pn,2

n,Pn,X1 ,X2

= (g̃1n,pn,1 , g2n,pn,2 ), n ∈ N is a sequence

of functions fn : g

→ 1 as n → ∞, where σ2n is the labeling for the graph

g2n,pn,2 for which

, (g2n,pn,2 , σ2n ).

Definition 8. A matching algorithm for the family of CPERs g
graph isomorphism algorithm if X1 = X2 with probability one.

n,Pn,X1 ,X2

Definition 9. A seeded matching algorithm for the family of CPERs g
Sn ⊂ Vn2 is a sequence of functions fn : g
σ2n S
n

is the restriction of

σ2n

n,Pn,X1 ,X2

= (g̃1n,pn,1 , g2n,pn,2 ), n ∈ N is called a

n,Pn,X1 ,X2

= (g̃1n,pn,1 , g2n,pn,2 ) and seed sets

× σ2n S 7→ σ̂2n such that P(σ2n = σ̂2n ) → 1 as n → ∞, where
n

to the subset Sn of the vertices. Λn = |Sn | is called the seed size.

The following defines an achievable region for the graph matching problem.
e = (Pn )n∈N is said to be
Definition 10. For the graph matching problem, a family of sets of distributions P
in the achievable region if for every sequence of distributions Pn,X1 ,X2 ∈ Pn , n ∈ N, there exists a matching
algorithm.
Definition 11. For the seeded graph matching problem, a family of pairs of distribution sets and seed sizes
es = (Pn , Λn )n∈N is said to be in the achievable region if for every sequence of pairs Pn,X1 ,X2 ∈ Pn and
P
Sn ∈ Vn2 such that Sn = |Λn |, there exists a seeded matching algorithm.

III. Graph Isomorphism
In this section, we consider the graph isomorphism problem. First, we analyze the maximum degree
algorithm (MDA) proposed in [1], [2] and re-derive the achievable distribution region using information
theoretic quantities.

A. Maximum Degree Algorithm
In their seminal paper, Babai et. al. [1] proposed the first polynomial time algorithm for graph isomorphism
for families of CPERs with parameter pn =

1
2, n

∈ N. This result was later extended to include a larger
1

1

achievable region, namely the region characterized by pn ∈ [ω(log n/n 5 ), 1−ω(log n/n 5 )], [2] . The algorithm
operates in two steps. In the first step, the agent who is matching the two graphs exploits the uniqueness
of the degrees of the highest degree vertices in the graphs to match these vertices. In the next step, these
vertices are used as seeds to match the rest of the vertices. More precisely, the agent orders the vertices in
j
j
j
both graphs based on their degrees. Let dn,(i)
, j ∈ {1, 2} be the ith largest degree in gn,p
. Also, let kn,(i)
be
n, j

DRAFT

6

j
j
j
j
, k ∈ [1, kn,(i)
] be the kth vertex with degree
with degree dn,(i)
and let vn,(i),k
the number of vertices in gn,p
n, j
j
kn,(i)
. Define
1
dn,u = argmin{i|kn,(
j) = 1, ∀ j ≥ i}.

In other words, if we list the vertices in g1 in decreasing degree order and start from the vertex with the
highest degree, the first dn,u vertices have unique degrees. The following lemma provides a lower bound on
dn,u .
Lemma 1 ( [2] Theorem 3.15). Suppose m = o



p(1−p)n
log n

P(dn,u > m) → 1

 14 

. Then,

as

n → ∞.

The agent matches the first dn,u vertices in the two graphs. Formally, the agent sets σ̂2 (v2n,(i),1 ) = σ1 (v1n,(i),1 ), i ∈
j
[1, dn,u ]. Next, it constructs a signature vector for each of the unmatched vertices. For each vertex vn,(i),k
,j∈
j
j
j
j
= (Fn,(i),k
(1), Fn,(i),k
(2), · · · , Fn,(i),k
(dn,u )).
{1, 2}, i < dn,u , k ∈ [1, ki ], its signature is defined as the binary vector F n,(i),k

which indicates its connections to the matched vertices:



j
j


(vn,(i),k
, vn,(l),1
) ∈ Enj

1 if
j
Fn,(i),k (l) = 
,




0 Otherwise

l ∈ [1, dn,u ].

For any arbitrary vertex v1n,(i),k , if there exists a unique vertex v2n,(i),k0 such that F 1n,(i),k =F 2n,(i),k0 , then the agent
matches the two vertices by setting σ̂2 (v2n,(i),k ) = σ1 (v1n,(i),k0 ). If all of the vertices are matched at this step,
then the algorithm succeeds, otherwise the algorithm fails. The following theorem provides the achievable
distribution region for this algorithm.
1

1

Theorem 1. Let pn ∈ [ω(log n/n 5 ), 1 − ω(log n/n 5 )]. Then, the MDA is a graph isomorphism algorithm for
the CPER g

n,Pn,X1 ,X1

= (g̃1n,pn , g2n,pn ).

Proof. This result was shown by Bollobás [2]. We reprove the theorem using a new method. The tools
introduced in the proof are used in the next section when we study seeded graph matching. Throughout the
proof we write p instead of pn for brevity. As explained above, the matching algorithm succeeds if every
vertex has a unique signature. Define the following error event:
Dn = {g

n,Pn,X1 ,X1

j
j
|∃k , k0 , F n,(i),k
= F n,(i),k
0 }.

DRAFT

7

The algorithm succeeds as long as P(Dn ) → 0 as n → ∞. We have:




kn,i X
n X
[
 j
 (b)

 j
 (a) X

j
j
j
j
P F n,(i),k
= F n,(i),k
≤ n2 P F n,(i),k
= F n,(i),k
P(Dn ) = P 
{g
|F n,(i),k = F n,(i),k0 } ≤
0
0 , (1)

 0 n,Pn,X1 ,X1
0
i=1 k=1 k <k

k,k
i∈[1,n]

where in (a) we have used the union bound and (b) follows from the fact that there are a total of n vertices.
 j

j
Next, we calculate P F n,(i),k
= F n,(i),k
0 :
X
X
 j

(a)
j
j
j
j
j
P F n,(i),k
= F n,(i),k
P(F 0 = F n,(i),k
= F n,(i),k
P(F 0 = F n,(i),k
)P(F 0 = F n,(i),k
0 =
0) =
0)
F 0 ⊂{0,1}dn,u

X

=
F
(b)

=

0

2wH (F 0 )

p

(1 − p)

F 0 ⊂{0,1}dn,u

2(n−wH (F 0 ))

⊂{0,1}dn,u

dn,u
X

1
p

i=1

λdn,u

2

i
nHb ( dn,u
)

!
dn,u
X
dn,u 2i
=
p (1 − p)2(dn,u −i)
i
i=1

!
1
) p2i (1 − p)2(dn,u −i) ,
1 + O(
dn,u

where (a) follows from the fact that the difference between subsequent unique degrees is at least 2 with
probability one 1 , and in (b) we have used the following equality.
!
!
i
dn,u
1
1
nHb ( dn,u
)
2
1 + O(
) ,
= p
dn,u
i
λdn,u
where λ = 2πp(1− p) and Hb is the binary entropy function. The proof of the equality follows from Sterling’s


√
approximation dn,u ! = 2πne−dn,u dn,u dn,u 1 + O( d1n,u ) . Following the steps in the proof of Theorem 2 in [19],
we have:
 j

j
2
2 dn,u
P F n,(i),k
= F n,(i),k
.
0 ≤ (p + (1 − p) )

(2)

Combining Equations (1) and (2) gives:
P(Dn ) ≤ n2 (p2 + (1 − p)2 )dn,u ,
which goes to zero as n → ∞ if dn,u = ω

 log n 
H2 (p)

(3)

, where H2 (p) is the Rényi entropy with parameter 2 given

by:
H2 (p) = log

p2

1
.
+ (1 − p)2

So, from Lemma 1, the algorithm succeeds with probability one as long as:


 p(1 − p)n ! 41 
log n
 .
= o 

H2 (p)
log n
Note that:
(a)
H2 (p)
1
= − loge (p2 + (1 − p)2 ) = loge ( 2
) ≥ 1−
2
log2 (e)
p + (1 − p)

1

1
1
p2 +(1−p)2

(b)

= 1 − p2 − (1 − p)2 = 2p(1 − p) ≥ p,

For a complete argument on the independence of the edge incidence refer to the proof of Theorem 3.17 in [2].

DRAFT

8

Labeled
1
vn;k
1

1
g~n;p
n;1

Seeds
1
vn;j
1

Unlabeled
2
vn;l
1

1
vn;j
2

1
vn;k
2

1
vn;k
n−Λn +1

Seeds
2
vn;i
1
2
vn;i
2

2
vn;l
2

1
vn;j
Λn −1

1
vn;k
n−Λn

2
gn;p
n;2

2
vn;i
Λn −1

2
vn;l
n−Λn +1

1
vn;j
Λn

2
vn;i
Λn

2
vn;l
n−Λn

Fig. 2: The agent constructs the bipartite graph which captures the connections between the unmatched
vertices with the seed vertices.

where in (a) we have used loge x ≥ 1 − 1x , and in (b) we have assumed p < 21 for sufficiently large n.

 41 
log e log n
n
=
Also, p < Hlog2 (p)e gives logp n > H2 2 (p) . So, if we show that logp n = o p(1−p)n
it follows that Hlog
log n
2 (p)
2

1

4
o p(1−p)n
. We have:
log n


 p(1 − p)n ! 14 
log n
 ⇔ n− 41 log n 54 = o(p 54 (1 − p) 14 )
= o 

p
log n
1

5

5

1

1

⇔ n− 4 log n 4 = o(p 4 ) ⇔ n− 5 log n = o(p) ⇔ p = ω(n− 5 log n).


IV. Seeded Graph Matching
In this section, we consider the seeded graph matching problem. We argue that seeded graph matching
is related to the active fingerprinting problem studied in [19]. In active fingerprinting, the agent has access
to two correlated bipartite graphs. The vertices in each graph are partitioned into a set of anonymized users
and a set of groups. The objective is to match a single anonymized user in the first bipartite graph to a
corresponding user in the second graph based on their connections with group vertices.
To demonstrate the connection between seeded graph matching and active fingerprinting, we view seeds
in graph matching as groups in active fingerprinting and unmatched vertices as anonymized users. Then. the
seeded matching problem can be solved using a variation of the active fingerprinting attacks in [19]. The
proposed graph matching algorithm operates as follows. First, the agent constructs the bipartite graph shown
in Figure 2 whose edges consist of the connections between the unmatched vertices with the seeded vertices
in each graph. Next, it matches the two bipartite graphs by iteratively applying the fingerprinting algorithm
proposed in [19]. The fingerprinting algorithm operates in two steps. First, the agent constructs signature
vectors for each of the unmatched vertices in the two bipartite graphs based on their connections to the seed

DRAFT

9

vertices. In the second step, it uses joint typicality between the signature vectors to match the two vertices.
The iterative application of this algorithm means that the agent first uses the fingerprinting algorithm to match
a subset of the vertices. Then, the matched vertices in this step are added to the seed set and this expanded
set of seeds is used in the next iteration to match the rest of the vertices.
Formally, assume that the agent is to match the CPER g

n,Pn,X1 ,X2

= (g̃1n,pn,1 , g2n,pn,2 ) using the seed set

Sn ⊂ Vn2 , and let n = ω( √1Λ ). Let Sn = {v2n,i1 , v2n,i2 , · · · , v2n,iΛn } and define the reverse seed set S−1
n =
n

{v1n, j1 , v1n, j2 , · · ·

, v1n, jΛn },

where

σ1n (v1n, jk )

= σ2n (v2n,ik ), k ∈ [1, Λn ]. The agent is given σ1n : Vn1 → [1, n] as well as

σ2n |Sn : Sn → [1, n]. The objective is to find σ̂2n : Vn2 → [1, n] such that P(σ̂2n = σ2n ) → 1 as n → ∞. To this
end, the agent first constructs a signature for each vertex in each of the graphs. For an arbitrary vertex v1n,i
in g1n,pn,1 , its signature is defined as the binary vector F 1n, j = (Fn,1 j (1), Fn,1 j (2), · · · , Fn,1 j (Λn )). which indicates
its connections to the reverse seed elements:





(v1n, j , v1n, jl ) ∈ E1n

1 if
1
Fn, j (l) = 
,




0 Otherwise

l ∈ [1, Λn ].

The signature of an arbitrary vertex v2n,i is defined in a similar fashion based on connections to the elements
of the seed set Sn . Take an unmatched vertex v2n,i < Sn . The agent matches v2n,i to a vertex v1n, j if it is the
unique vertex such that the signature pair (F 1n, j , F 2n,i ) are jointly -typical with respect to the distribution
Pn,X1 ,X2 . Alternatively,
∃!i : (F 1n, j , F 2n,i ) ∈ An (X1 , X2 ) ⇒ σ̂2n (v2n,i ) = σ1 (v1n, j ),
where An (X1 , X2 ) is the set of jointly -typical set sequences of length n with respect to Pn,X1 ,X2 . If a unique
match is not found, then vertex v2n,i is added to the ambiguity set L2n . Assume that at the end of this step,
the set of all matched vertices is Vn2 \L2n . In the next step, these vertices are added to the seed set and the
expanded seed set is used to match the vertices in the ambiguity set. The algorithm succeeds if all vertices
are matched at this step and fails otherwise. We call this strategy the Typicality Matching Strategy (TMS).
e as follows:
Theorem 2. Define the family of sets of pairs of distribution and seed sizes P
e = {(Pn , Λn )n∈N |∀Pn,X1 ,X2 ∈ Pn : 2 log n ≤ Λn }.
P
I(X1 , X2 )
e is achievable using the TMS.
Then, P
To prove Theorem 2, we need the following lemma on the cardinality of L2n :
Lemma 2. The following holds:
P(|L2n | >

2n
) → 0, as n → ∞,
Λn  2

DRAFT

10

Proof. Formally, L2n is defined as:
L2n = {v2n,i @! j : (F 1n, j , F 2n,i ) ∈ An (X1 , X2 )}.
From the Chebychev inequality, we have:
 Var(|L2 |)



P |L2n | > 2E(|L2n |) = P |L2n | − E(|L2n |) > E(|L2n |) ≤ 2 2n .
E (|Ln |)

(4)

Let A j be the event that v2n, j ∈ L2n , then

 n
n
n
X
 X
X
P(v2n, j ∈ L2n ) =
P(A j )
E(|L2n |) = E  1(v2n, j ∈ L2n ) =
j=1

j=1

j=1

 n
2
n
X
X
X

2
Var(|Ln |) =
P(A j ) +
P(Ai , A j ) − 
P(A j )
i, j

j=1

=

n
X

P(A j ) −

j=1

n
X

j=1

P2 (A j ) ≤ E(|L2n |).

j=1

So, from (4), we have:


P |L2n | > 2E(|L2n |) ≤

1
,
E(|L2n |)

which goes to 0 as n → ∞ provided that E(|L2n |) → ∞ (otherwise the claim is proved since E(|L2n |) is finite.).
It remains to find an upper bound on E(|L2n |). Let B j be the event that the signature F 2n, j is not typical with
respect to Pn,X2 and let Ci, j be the event that there exists i ∈ [1, n] such that F 1n, j and F 2n,i are jointly typical
with respect to Pn,X1 ,X2 . Then,



X
 [ [

(a)
1
c
 Ci, j  ≤ P(B j ) +
)
≤
P(A j ) ≤ P  B j
P(C
|B
+ n2−Λs (I(X1 ;X2 )−) ,
i,
j
j


2
Λ

s
i, j
i, j
where (a) follows from the standard information theoretic arguments (e.g proof of Theorem 3 in [19]). So,
E(|L2n |) ≤
From Λ s >

2 log n
I(X1 ;X2 ) ,

n
+ n2 2−Λs (I(X1 ;X2 )−) .
Λs 2

we conclude that the second term approaches 0 as n → ∞. This completes the proof of


Claim 1.
We proceed to prove Theorem 2:
Proof. Let H be the event the algorithm fails and K the event that |L2n | >

2n
.
Λn  2

Then:

P(H) ≤ P(K) + P(H|K c ).

DRAFT

11

From Claim 1, we know that P(K) → 0 as n → ∞. For the second term, let L0n be the set of vertices which
are not matched in the second iteration. The algorithm fails if L0n , φ. However, by a similar argument as
in the proof of claim 1, we have:
P(|L0n | >

1 2
2n
) → 0 as n → ∞.
|L | <
2 n
Λn  2

So, P(|L0n | = 0) → 1 as n → ∞. This completes the proof.


V. Conclusion
We have introduced a new information theoretic framework for analyzing graph matching problems. We
have used this framework to study both graph isomorphism as well as seeded graph matching. In graph
isomorphism, we have analyzed the performance of the maximum degree algorithm and rederived suffiecient
conditions for successful matching under the Erdös-Rényi model. Furthermore, we have proposed a new
seeded graph matching algorithm. The new algorithm operates using a method called typicality matching.
We have analyzed the performance of the new seeded matching algorithms and derived sufficient conditions
on the seed size as functions of graph statistics.

References
[1] László Babai, Paul Erdos, and Stanley M Selkow. Random graph isomorphism. SIaM Journal on computing, 9(3):628–635,
1980.
[2] Béla Bollobás. Random graphs. 2001. Cambridge Stud. Adv. Math, 2001.
[3] Derek G. Corneil and David G. Kirkpatrick. A theoretical analysis of various heuristics for the graph isomorphism problem.
SIAM Journal on Computing, 9(2):281–297, 1980.
[4] Tomek Czajka and Gopal Pandurangan. Improved random graph isomorphism. Journal of Discrete Algorithms, 6(1):85–92,
2008.
[5] Ehsan Kazemi, S Hamed Hassani, and Matthias Grossglauser. Growing a graph matching from a handful of seeds. Proceedings
of the VLDB Endowment, 8(10):1010–1021, 2015.
[6] Carla-Fabiana Chiasserini, Michele Garetto, and Emilio Leonardi. Social network de-anonymization under scale-free user
relations. IEEE/ACM Transactions on Networking, 24(6):3756–3769, 2016.
[7] Vince Lyzinski, Donniell E Fishkind, and Carey E Priebe. Seeded graph matching for correlated erdös-rényi graphs. Journal
of Machine Learning Research, 15(1):3513–3540, 2014.
[8] Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Musé, and Guillermo Sapiro. Robust multimodal graph matching:
Sparse coding meets graph matching. In Advances in Neural Information Processing Systems, pages 127–135, 2013.
[9] Efe Onaran, Siddharth Garg, and Elza Erkip. Optimal de-anonymization in random graphs with community structure. In
Signals, Systems and Computers, 2016 50th Asilomar Conference on,, pages 709–713. IEEE, 2016.
[10] Daniel Cullina and Negar Kiyavash. Improved achievability and converse bounds for erdos-renyi graph matching. SIGMETRICS
Perform. Eval. Rev., 44(1):63–72, June 2016.

DRAFT

12

[11] E. Kazemi, L. Yartseva, and M. Grossglauser. When can two unlabeled networks be aligned under partial overlap? In 2015
53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 33–42, Sept 2015.
[12] Paul Erdos and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
[13] Edward M Wright. Graphs on unlabelled nodes with a given number of edges. Acta Mathematica, 126(1):1–9, 1971.
[14] Ehsan Kazemi. Network alignment: Theory, algorithms, and applications. 2016.
[15] Lyudmila Yartseva and Matthias Grossglauser. On the performance of percolation graph matching. In Proceedings of the first
ACM conference on Online social networks, pages 119–130. ACM, 2013.
[16] Pedram Pedarsani, Daniel R Figueiredo, and Matthias Grossglauser. A bayesian method for matching two similar graphs without
seeds. In Communication, Control, and Computing (Allerton), 2013 51st Annual Allerton Conference on, pages 1598–1607.
IEEE, 2013.
[17] Shouling Ji, Weiqing Li, Mudhakar Srivatsa, and Raheem Beyah. Structural data de-anonymization: Quantification, practice,
and implications. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages
1040–1053. ACM, 2014.
[18] Xinzhe Fu, Zhongzhao Hu, Zhiying Xu, Luoyi Fu, and Xinbing Wang. De-anonymization of social networks with communities:
When quantifications meet algorithms. arXiv preprint arXiv:1703.09028, 2017.
[19] F. Shirani, S. Garg, and E. Erkip. An information theoretic framework for active de-anonymization in social networks based on
group memberships. In 2017 55rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), Sept
2017.
[20] S. Ji, W. Li, N. Z. Gong, P. Mittal, and R. Beyah. Seed-based de-anonymizability quantification of social networks. IEEE
Transactions on Information Forensics and Security, 11(7):1398–1411, July 2016.

DRAFT

