Fast Computation of Graph Edit Distance
Xiaoyang Chen† , Hongwei Huo∗† , Jun Huan‡ , Jeffrey Scott Vitter

arXiv:1709.10305v1 [] 29 Sep 2017

†

§

Dept. of Computer Science, Xidian University, chenxyu1991@gmail.com, hwhuo@mail.xidian.edu.cn
‡
Dept. of Electrical Engineering and Computer Science, The University of Kansas, jhuan@ku.edu
§
Dept. of Computer and Information Science, The University of Mississippi, JSV@OleMiss.edu

Abstract—The graph edit distance (GED) is a well-established
distance measure widely used in many applications. However,
existing methods for the GED computation suffer from several
drawbacks including oversized search space, huge memory
consumption, and lots of expensive backtracking. In this paper,
we present BSS GED, a novel vertex-based mapping method for
the GED computation. First, we create a small search space
by reducing the number of invalid and redundant mappings
involved in the GED computation. Then, we utilize beam-stack
search combined with two heuristics to efficiently compute GED,
achieving a flexible trade-off between available memory and
expensive backtracking. Extensive experiments demonstrate that
BSS GED is highly efficient for the GED computation on sparse
as well as dense graphs and outperforms the state-of-the-art
GED methods. In addition, we also apply BSS GED to the graph
similarity search problem and the practical results confirm its
efficiency.

I. I NTRODUCTION
Graphs are widely used to model various complex structured
data, including social networks, molecular structures, etc. Due
to extensive applications of graph models, there has been a
considerable effort in developing techniques for effective graph
data management and analysis, such as graph matching [3] and
graph similarity search [14], [17], [19].
Among these studies, similarity computation between two
graphs is a core and essential problem. In this paper, we focus
on the similarity measure based on graph edit distance (GED)
since it is applicable to virtually all types of data graphs and
can also precisely capture structural differences. Due to the
flexible and error-tolerant characteristics of GED, it has been
successfully applied in many applications, such as molecular
comparison in chemistry [8], object recognition in computer
vision [2] and graph clustering [9].
Given two graphs G and Q, the GED between them, denoted
by ged(G, Q), is defined as the minimum cost of an edit
path that transforms one graph to another. Unfortunately,
unlike the classical graph matching problem, such as subgraph
isomorphism [15], the fault tolerance of GED allows a vertex
of one graph to be mapped to any vertex of the other graph,
regardless of their labels and degrees. As a consequence, the
complexity of the GED computation is higher than that of
subgraph isomorphism, which has been proved to be an NPhard [17] problem.
The GED computation is usually carried out by means
of a tree search algorithm which explores the space of all
possible mappings of vertices and edges of comparing graphs.
The underlying search space can be organized as an ordered
search tree. Based on the way of generating successors of

nodes in the search tree, existing methods can be divided into
two broad categories: vertex-based and edge-based mapping
methods. When generating successors of a node, the former
extends unmapped vertices of comparing graphs, while the
later extends unmapped edges. A? -GED [5], [7] and DFGED [16] are two major vertex-based mapping methods. A? GED adopts the best-first search paradigm A? [6], which picks
up a partial mapping with the minimum induced edit cost to
extend each time. The first found complete mapping induces
the GED of comparing graphs. However, DF-GED carries out
a depth-first search, which quickly reaches a leaf node. The
edit cost of a leaf node in fact is an upper bound of GED
and hence can be used to prune nodes later to accelerate the
GED computation. Different from the above two methods,
CSI GED [4] is a novel edge-based mapping method based
on common substructure isomorphism, which works well for
the sparse and distant graphs. Similar to DF-GED, CSI GED
also adopts the depth-first search paradigm.
Even though existing methods have achieved promising
preliminary results, they still suffer from several drawbacks.
Both A? -GED and DF-GED enumerate all possible mappings
between two graphs. However, among these mappings, some
mappings must not be optimal, called invalid mappings, or
they induce the same edit cost, called redundant mappings.
For invalid mappings, we do not have to generate them, and
for redundant mappings, we only need to generate one of them
so as to avoid redundancy. The search space of A? -GED and
DF-GED becomes oversized as they generate plenty of invalid
and redundant mappings.
In addition, for A? -GED, it needs to store enormous
partial mappings, resulting in a huge memory consumption.
In practice, A? -GED cannot compute the GED of graphs with
more than 12 vertices. Though DF-GED performing a depthfirst search is efficient in memory, it is easily trapped into a
local (i.e., suboptimal) solution and hence produces lots of
expensive backtracking. On the other hand, for CSI GED, it
adopts the depth-first search paradigm, and hence also faces
the expensive backtracking problem. Besides, the search space
of CSI GED is exponential with respect to the number of
edges of comparing graphs, making it naturally be unsuitable
for dense graphs.
To solve the above issues, we propose a novel vertex-based
mapping method for the GED computation, named BSS GED,
based on beam-stack search [11] which has shown an excellent
performance in AI literature. Our contributions in this paper
are summarized below.

We propose a novel method of generating successors of
nodes in the search tree, which reduces a large number
of invalid and redundant mappings involved in the GED
computation. As a result, we create a small search space.
Moreover, we also give a rigorous theoretical analysis of
the search space.
• Incorporating with the beam-stack search paradigm into
our method to compute GED, we achieve a flexible tradeoff between available memory and the time overhead of
backtracking and gain a better performance than the bestfirst and depth-first search paradigms.
• We propose two heuristics to prune the search space,
where the first heuristic produces tighter lower bound and
the second heuristic enables to fast search of tighter upper
bound.
• We have conducted extensive experiments on both real
and synthetic datasets. The experimental results show that
BSS GED is highly efficient for the GED computation
on sparse as well as dense graphs, and outperforms the
state-of-the-art GED methods.
• In addition, we also extend BSS GED as a standard graph
similarity search query method and the practical results
confirm its efficiency.
The rest of this paper is organized as follows: In Section II,
we introduce the problem definition and then give an overview
of the vertex-based mapping method for the GED computation.
In Section III, we create a small search space by reducing the
number of invalid and redundant mappings involved in the
GED computation. In Section IV, we utilize the beam-stack
search paradigm to traverse the search space to compute GED.
In Section V, we propose two heuristics to prune the search
space. In Section VI, we extend BSS GED as a standard graph
similarity search query method. In Section VII, we report the
experimental results and our analysis. Finally, we investigate
research works related to this paper in Section VIII and then
make concluding remarks in Section IX.
•

II. P RELIMINARIES
In this section, we introduce basic notations. For simplicity
in exposition, we only focus on simple undirected graphs
without multi-edges or self-loops.
A. Problem Definition
Let Σ be a set of discrete-valued labels. A labeled graph
is a triplet G = (VG , EG , L), where VG is the set of vertices,
EG ⊆ VG × VG is the set of edges, L : VG ∪ EG → Σ is a
labeling function which assigns a label to a vertex or an edge.
For a vertex u, we use L(u) to denote its label. Similarly,
L(e(u, v)) is the label of an edge e(u, v). ΣVG = {L(u) :
u ∈ VG } and ΣEG = {L(e(u, v)) : e(u, v) ∈ EG } are the
label multisets of VG and EG , respectively. For a graph G,
S(G) = (VG , EG ) is its unlabeled version, i.e., its structure.
In this paper, we refer |VG | to the size of graph G.
Definition 1 (Subgraph Isomorphism [15]). Given two graphs
G and Q, G is subgraph isomorphic to Q, denoted by G ⊆ Q,

if there exists an injective function φ : VG → VQ , such that
(1) ∀u ∈ VG , φ(u) ∈ VQ and L(u) = L(φ(u)). (2) ∀e(u, v) ∈
EG , e(φ(u), φ(v)) ∈ EQ and L(e(u, v)) = L(e(φ(u), φ(v))).
If G ⊆ Q and Q ⊆ G, then G and Q are graph isomorphic
to each other, denoted by G ∼
= Q.
There are six edit operations can be used to transform one
graph to another [12], [20]: insert/delete an isolated vertex,
insert/delete an edge, and substitute the label of a vertex or
an edge. Given two graphs G and Q, an edit path P =
hp1 , . . . , pk i is a sequence of edit operations that transforms
pk
p1
one graph to another, such as G = G0 −→, . . . , −→ Gk ∼
= Q.
The edit cost of P isPdefined as the sum of edit cost of all
k
operations in P , i.e., i=1 c(pi ), where c(pi ) is the edit cost
of the edit operation pi . In this paper, we focus on the uniform
cost model, i.e., c(pi ) = 1 for ∀i, thus the edit cost of P is its
length, denoted by |P |. For P , we call it is optimal if and only
if it has the minimum length among all possible edit paths.
Definition 2 (Graph Edit Distance). Given two graphs G
and Q, the graph edit distance between them, denoted by
ged(G, Q), is the length of an optimal edit path that transforms G to Q (or vice versa).
Example 1. In Figure 1, we show an optimal edit path P that
transforms graph G to graph Q. The length of P is 4, where
we delete two edges e(u1 , u2 ) and e(u1 , u3 ), substitute the
label of vertex u1 with label A and insert one edge e(u1 , u4 )
with label a.
u1
u2
b
B
A
b

u1
B

a

A a C
u3
u4
G

u2
A
a

A a C
u3
u4
G1

u1
A

u2
A
a

A a C
u3
u4
Q1

v1
A
a
A a C a A
v3
v4
v2
Q

Fig. 1: An optimal edit path P between graphs G and Q.

B. Graph Mapping
In this part, we introduce the graph mapping between two
graphs, which can induce an edit path between them. In order
to match two unequal size graphs G and Q, we extend their
vertex sets as VG∗ and VQ∗ such that VG∗ = VG ∪ {un } and
VQ∗ = VQ ∪ {v n }, respectively, where un and v n are dummy
vertices labeled with ε, s.t., ε ∈
/ Σ. Then, we define graph
mapping as follows:
Definition 3 (Graph Mapping). A graph mapping from
graph G to graph Q is a bijection ψ : VG∗ → VQ∗ , such that
∀u ∈ VG∗ , ψ(u) ∈ VQ∗ , and at least one of u and ψ(u) is not
a dummy vertex.
Given a graph mapping ψ from G to Q, it induces an
unlabeled graph H = (VH , EH ), where VH = {u : u ∈
VG ∧ ψ(u) ∈ VQ } and EH = {e(u, v) : e(u, v) ∈ EG ∧
e(ψ(u), ψ(v)) ∈ EQ }, then H ⊆ S(G) and H ⊆ S(Q).
Let Gψ (resp. Qψ ) be the labeled version of H embedded
in G (resp. Q). Accordingly, we obtain an edit path Pψ :

G → Gψ → Qψ → Q. Let CD (ψ), CS (ψ) and CI (ψ) be
the respective edit cost of transforming G to Gψ , Gψ to Qψ ,
and Qψ to Q. As Gψ is a subgraph of G, we only need
to delete vertices and edges that do not belong to Gψ when
transforming G to Gψ . Thus, CD (ψ) = |VG | − |VH | + |EG | −
|EH |. Similarly, CI (ψ) = |VQ |−|VH |+|EQ |−|EH |. Since Gψ
and Qψ have the same structure H, we only need to substitute
the corresponding vertex and edge labels between G ψ and Q ψ ,
thus CS (ψ) = |{u : u ∈ VH ∧ L(u) 6= L(ψ(u))}| + |{e(u, v) :
e(u, v) ∈ EH ∧ L(e(u, v)) 6= L(e(ψ(u), ψ(v)))}|.

generating successors. For a leaf node r, we compute the edit
cost of its corresponding edit path Pψr by Theorem 1. Thus,
when we generate all leaf nodes, we must find an optimal
graph mapping and then obtain ged(G, Q).
Algorithm 1: BasicGenSuccr(r)
1
2
3
4
5

Theorem 1 ([4]). Given a graph mapping ψ from graph G to
graph Q. Let Pψ be the edit path induced by ψ, then |Pψ | =
CD (ψ) + CI (ψ) + CS (ψ).
Example 2. Consider graphs G and Q in Figure 1. Given a
graph mapping ψ : {u1 , u2 , u3 , u4 } → {v1 , v2 , v3 , v4 }, where
ψ(u1 ) = v1 , ψ(u2 ) = v2 , ψ(u3 ) = v3 , and ψ(u4 ) = v4 , we
have H = ({u1 , u2 , u3 , u4 }, {e(u2 , u4 ), e(u3 , u4 )}). Then ψ
induces an edit path Pψ : G → G ψ → Q ψ → Q shown in
Figure 1, where Gψ = G1 and Qψ = Q1 . By Theorem 1, we
compute that CD (ψ) = 2, CI (ψ) = 1 and CS (ψ) = 1, thus
|Pψ | = CD (ψ) + CI (ψ) + CS (ψ) = 4.
Hereafter, for ease of presentation, we assume that G and Q
are the two comparing graphs, and VG = {u1 , . . . , u|VG | }
and VQ = {v1 , . . . , v|VQ | }. For a graph mapping ψ from G
to Q, we call it is optimal only when its induced edit path Pψ
is optimal. Next, we give an overview of the vertex-based
mapping method for computing ged(G, Q) by enumerating
all possible graph mappings from G to Q.
C. GED computation: Vertex-based Mapping Approach
Assuming that vertices in VG∗ are processed in the order
(ui1 , . . . , ui|VG | , un , . . . , un ), where i1 , . . . , i|VG | is a permutation of 1, . . . , |VG | detailed in Section V-B.∗ Then, we denote
S|VG |
a graph mapping from G to Q as ψ = l=1
{(uil → vjl )} in
the following sections, such that (1) uil = un if il > |VG |; (2)
vjl = v n if jl > |VQ |; and (3) vjl = ψ(uil ) for 1 ≤ l ≤ |VG∗ |.
The GED computation is always achieved by means of an
ordered search tree, where inner nodes correspond to partial
graph mappings and leaf nodes correspond to complete graph
mappings. Such a search tree is created dynamically at runtime
by iteratively generating successors linked by edges to the
currently considered node. Let ψr = {(ui1 → vj1 ), . . ., (uil →
vjl )} be the (partial) mapping associated with a node r,
where vjk is the mapped vertex of uik for 1 ≤ k ≤ l , then
Algorithm 1 outlines the method of generating successors of r.
Algorithm 1 is easy to understand. First, we compute the
r
r
sets of unmapped vertices CG
and CQ
in G and Q, respectively
r
(line 2). Then, if |CG
| > 0, for the vertex uil+1 to be extended,
r
we choose a vertex z from CQ
or {v n } as its mapped vertex,
and finally generate all possible successors of r (lines 4–8);
otherwise, all vertices in G were processed, then we insert all
r
vertices in CQ
into G and obtain a unique successor leaf node
(lines 10–11).
Staring from a dummy root node root such that ψroot = ∅,
we can create the search tree layer-by-layer by iteratively

6

ψr ← {(ui1 → vj1 ), . . . , (uil → vjl )}, succ ← ∅;
r
r
CG
← VQ \{vj1 , . . . , vjl };
← VG \{ui1 , . . . , uil }, CQ
r
if |CG
| > 0 then
r
foreach z ∈ CQ
do
generate successor q, s.t., ψq ← ψr ∪ {(uil+1 → z)};
succ ← succ ∪ {q};
generate successor q, s.t., ψq ← ψr ∪ {(uil+1 → v n )};
succ ← succ ∪ {q};

7
8
9
10
11
12

else
generate successor q, s.t., ψq ← ψr ∪
succ ← succ ∪ {q};

S

r {(u
z∈CQ

n

→ z)};

return succ;

However, the above method BasicGenSuccr used in A? GED [5] and DF-GED [16] generates all possible successors.
As a result, both A? -GED and DF-GED enumerate all possible
graph mappings from G to Q and their search space size
is O(|VQ ||VG | ) [4]. However, among these mappings, some
mappings certainly not be optimal, called invalid mappings,
or they induce the same edit cost, called redundant mappings.
For invalid mappings, we do not have to generate them, and
for redundant mappings, we only need to generate one of
them. Next, we present how to create a small search space
by reducing the number of invalid and redundant mappings.
III. C REATING S MALL S EARCH S PACE
A. Invalid Mapping Identification
Let |ψ| be the length of a graph mapping ψ, i.e., |VG∗ |. We
give an estimation of |ψ| in Theorem 2, which can be used to
identify invalid mappings.
Theorem 2. Given an optimal graph mapping ψ from graph G
to graph Q, then |ψ| = max{|VG |, |VQ |}.
Proof: Suppose for the purpose of contradiction that
|ψ| > max{|VG |, |VQ |}. Then (x → v n ) and (un → y) must
be present simultaneously in ψ, where x ∈ VG and y ∈ VQ . We
construct another graph mapping ψ 0 = (ψ\{(x → v n ), (un →
y)}) ∪ {(x → y)}, and then prove |Pψ0 | < |Pψ | as follows:
Let H and H 0 be two unlabeled graphs induced by ψ and ψ 0 ,
respectively, then VH 0 = {u : u ∈ VG ∧ ψ 0 (u) ∈ VQ } = {u :
u ∈ VG ∧ ψ(u) ∈ VQ } ∪ {x : ψ 0 (x) ∈ VQ } = VH ∪ {x}. Let
Ax = {z : z ∈ VH ∧ e(x, z) ∈ EG ∧ e(y, ψ(z)) ∈ EQ }, then
EH 0 = {e(u, v) : e(u, v) ∈ EG ∧ e(ψ 0 (u), ψ 0 (v)) ∈ EQ } =
{e(u, v) : e(u, v) ∈ EG ∧ e(ψ(u), ψ(v)) ∈ EQ } ∪ {e(x, z) :
z ∈ VH 0 ∧e(x, z) ∈ EG ∧e(y, ψ(z)) ∈ EQ } = EH ∪{e(x, z) :
z ∈ Ax }. As x ∈
/ VH , e(x, z) ∈
/ EH for ∀z ∈ Ax . Thus,
|VH 0 | = |VH | + 1 and |EH 0 | = |EH | + |Ax |.
As CD (ψ) = |VG |−|VH |+|EG |−|EH | and CI (ψ) = |VQ |−
|VH |+|EQ |−|EH |, we have CD (ψ 0 ) = CD (ψ)−(1+|Ax |) and

CI (ψ 0 ) = CI (ψ) − (1 + |Ax |). Since CS (ψ) = |{u : u ∈ VH ∧
L(u) 6= L(ψ(u))}| + |{e(u, v) : e(u, v) ∈ EH ∧ L(e(u, v)) 6=
L(e(ψ(u),
ψ(v)))}|, we have CS (ψ 0 ) = CS (ψ) + c(x → y) +
P
z∈Ax c(e(x, z) → e(y, ψ(z))), where c(·) gives the edit cost
of relabeling a vertex or an edge, such that c(a → b) = 0 if
L(a) = L(b), and c(a → b) = 1 otherwise, and a (resp. b) is
a vertex or an edge in G (resp. Q). Thus, CS (ψ 0 ) ≤ CS (ψ) +
1 + |Ax |. Therefore, |Pψ0 | = CD (ψ 0 ) + CI (ψ 0 ) + CS (ψ 0 ) ≤
CD (ψ)−(1+|Ax |)+CI (ψ)−(1+|Ax |)+CS (ψ)+1+|Ax | =
|Pψ |−(1+|Ax |) < |Pψ |. This would be a contradiction that Pψ
is optimal. Hence |ψ| = max{|VG |, |VQ |}.
Theorem 2 states that a graph mapping whose length
is greater than |V | must be an invalid mapping, where
|V | = max{|VG |, |VQ |}. For example, considering graphs G
and Q in Figure 1, and a graph mapping ψ = {(u1 →
v1 ), (u2 → v n ), (u3 → v3 ), (u4 → v4 ), (un → v2 )},
we know that ψ with an edit cost 7 must be invalid as
|ψ| = 5 > max{|VG |, |VQ |} = 4.

For an edge e(u, v) in EH , e(ψ(u), ψ(v)) is its mapped
edge in EQ . As π(ψ(u)) = π(ψ 0 (u)), we have ψ(u) ∼ ψ 0 (u)
and then obtain NQ (ψ(u)) = NQ (ψ 0 (u)). Thus, we have
e(ψ 0 (u), ψ(v)) ∈ EQ . Similarly, since π(ψ(v)) = π(ψ 0 (v)),
we obtain ψ(v) ∼ ψ 0 (v). Thus, there must exist edges between
ψ(u) and ψ 0 (v), ψ 0 (u) and ψ 0 (v) (an illustration is shown
in Fig. 2), thus e(ψ 0 (u), ψ 0 (v)) ∈ EQ and hence we obtain
e(u, v) ∈ EH 0 . Thus, EH ⊆ EH 0 . Similarly, we also obtain
EH 0 ⊆ EH . So, EH = EH 0 .
Since VH = VH 0 and EH = EH 0 , we have H = H 0 . Thus,
CI (ψ) = CI (ψ 0 ) and CD (ψ) = CD (ψ 0 ). Next, we do not
distinguish H and H 0 anymore.

u

v

ψ(u)

ψ(v)

ψ 0 (u)

ψ 0 (v)

B. Redundant Mapping Identification
For a vertex u in VQ , its neighborhood information is defined as NQ (u) = {(v , L(e(u, v ))) : v ∈ VQ ∧ e(u, v ) ∈ EQ }.
Definition 4 (Vertex Isomorphism). Given two vertices
u, v ∈ VQ , u is isomorphic to v, denoted by u ∼ v, if and
only if L(u) = L(v) and NQ (u) = NQ (v).
By Definition 4, we know that the isomorphic relationship
between vertices is an equivalence relation. Thus, we can
λ
divide VQ into λQ equivalent classes VQ1 , . . . , VQ Q of isomorphic vertices. Each vertex u is said to belong to class π(u) = i
if u ∈ VQi . Dummy vertices in {v n } are isomorphic to each
other, and let π(v n ) = λQ + 1.
Definition 5 (Canonical Code). Given a graph mapping
S|ψ|
ψ = l=1 {(uil → vjl )}, where vjl = ψ(uil ) for 1 ≤
l ≤ |ψ|. The canonical code of ψ is defined as code(ψ) =
hπ(vj1 ), . . . , π(vj|ψ| )i.
Given two graph mappings ψ and ψ 0 such that |ψ| = |ψ 0 |,
we say that code(ψ) = code(ψ 0 ) if and only if π(vjl ) =
π(vj0 l ), where vjl = ψ(uil ) and vj0 l = ψ 0 (uil ) for 1 ≤ l ≤ |ψ|.
Theorem 3. Given two graph mappings ψ and ψ 0 . Let Pψ
and Pψ0 be edit paths induced by ψ and ψ 0 , respectively. If
code(ψ) = code(ψ 0 ), then we have |Pψ | = |Pψ0 |.
Proof: As discussed in Section II-B, |Pψ | = CI (ψ) +
CD (ψ) + CS (ψ). In order to prove |Pψ | = |Pψ0 |, we first
prove CI (ψ) = CI (ψ 0 ) and CD (ψ) = CD (ψ 0 ), then prove
CS (ψ) = CS (ψ 0 ).
Let H and H 0 be two unlabeled graphs induced by ψ and ψ 0 ,
respectively. For a vertex u in VH , ψ(u) and ψ 0 (u) are the
mapped vertices of u, respectively. Since code(ψ) = code(ψ 0 ),
we have π(ψ(u)) = π(ψ 0 (u)) and hence obtain ψ(u) ∼ ψ 0 (u).
As ψ(u) 6= v n , we have ψ 0 (u) 6= v n by Definition 4. Thus
u ∈ VH 0 , and hence we obtain VH ⊆ VH 0 . Similarly, we also
obtain VH 0 ⊆ VH . So, VH = VH 0 .

Fig. 2: Illustration of isomorphic vertices.
For any vertex u in VH , we have L(ψ(u)) = L(ψ 0 (u))
as ψ(u) ∼ ψ 0 (u). Thus, |{u : u ∈ VH ∧ L(u) 6=
L(ψ(u))}| = |{u : u ∈ VH ∧ L(u) 6= L(ψ 0 (u))}|. For
any edge e(u, v) in EH , since ψ(u) ∼ ψ 0 (u), we know
that L(e(ψ(u), ψ(v))) = L(e(ψ 0 (u), ψ(v))). Similarly, we
obtain L(e(ψ 0 (u), ψ(v))) = L(e(ψ 0 (u), ψ 0 (v))) as ψ(v) ∼
ψ 0 (v). Thus L(e(ψ(u), ψ(v))) = L(e(ψ 0 (u), ψ 0 (v))). Hence
|{e(u, v) : e(u, v) ∈ EH ∧L(e(u, v)) 6= L(e(ψ(u), ψ(v)))}| =
|{e(u, v) : e(u, v) ∈ EH ∧ L(e(u, v)) 6= L(e(ψ 0 (u), ψ 0 (v)))}|.
Therefore, CS (ψ) = CS (ψ 0 ). So, we have |Pψ | = |Pψ0 |.
Example 3. Consider graphs G and Q in Figure 1. For Q,
we know that L(v1 ) = L(v2 ) = L(v3 ) = A, and NQ (v1 ) =
NQ (v2 ) = NQ (v3 ) = {(v4 , a)}, thus v1 ∼ v2 ∼ v3 . So, we
divide VQ into equivalent classes VQ1 = {v1 , v2 , v3 }, VQ2 =
{v4 }. Given two graph mappings ψ = {(u1 → v1 ), (u2 →
v2 ), (u3 → v3 ), (u4 → v4 )} and ψ 0 = {(u1 → v2 ), (u2 →
v3 ), (u3 → v1 ), (u4 → v4 )}, we have code(ψ) = code(ψ 0 ) =
h1, 1, 1, 2i, and then obtain |Pψ | = |Pψ0 | = 4.
Theorem 3 states that graph mappings with the same
canonical code induce the same edit cost. Thus, among these
mappings, we only need to generate one of them. Next,
we apply Theorems 2, 3 into the procedure GenSuccr of
generating successors, which can prevent from generating the
above invalid and redundant mappings.
C. Generating Successors
Consider a node r associated with a partial graph mapping
ψr = {(ui1 → vj1 ), . . . , (uil → vjl )} in the search tree. Then,
r
the sets of unmapped vertices in G and Q are CG
=
r
VG \{ui1 , . . . , uil } and CQ
= VQ \{vj1 , . . . , vjl }, respectively.
r
For the vertex uil+1 to be extended, let z ∈ CQ
∪ {v n } be a
possible mapped vertex.
By Theorem 2, if |VG | ≤ |VQ |, we have |ψ| = |VQ |, which
means that none of the vertices in VG is allowed to be mapped

to a dummy vertex, i.e., (u → v n ) ∈
/ ψ for ∀u ∈ VG .
r
r
r
Rule 1. If |CG
| ≤ |CQ
|, then z ∈ CQ
; otherwise z = v n or
r
z ∈ CQ .
Applying rule 1 into the process GenSuccr of generating
successors of each node, we know that if |VG | ≤ |VQ | then
none of the vertices in VG will be mapped to a dummy vertex
otherwise only |VG |−|VQ | vertices do. As a result, the obtained
graph mapping ψ must satisfy |ψ| = max{|VG |, |VQ |}.

Layer

VG

1

u1

2

u2

3

u3

v3

4

u4

v4

root
v1
v2

v4
v4

v1

v4

v2

v2

v3

v3

v3

Fig. 3: Search tree created by GenSuccr.

0

Definition 6 (Canonical Code Partial Order). Let ψ and ψ
be two graph mappings such that code(ψ) = code(ψ 0 ). We
define that ψ  ψ 0 if ∃l, 1 ≤ l ≤ |ψ|, s.t., ψ(uik ) = ψ 0 (uik )
for 1 ≤ k < l and ψ(uil ) < ψ 0 (uil ).
By Theorem 3, we know that graph mappings with the same
canonical code induce the same edit cost, thus among these
mappings we only need to generate the smallest according
to the partial order defined in Definition 6. For uil+1 , we
only map it to the smallest unmapped vertex in VQm , for
1 ≤ m ≤ λQ . This will guarantee that the obtained graph
mapping is smallest among those mappings with the same
canonical code. Then we establish Rule 2 as follows:
SλQ
r
Rule 2. z ∈ m=1
∩ VQm }.
min{CQ
Based on the above Rule 1 and Rule 2, we give the method
of generating successors of r in Algorithm 2, where lines 4–8
corresponds to Rule 2 and lines 9–11 corresponds to Rule 1.
Algorithm 2: GenSuccr(r)
1
2
3
4
5
6
7
8

ψr ← {(ui1 → vj1 ), . . . , (uil → vjl )}, succ ← ∅;
r
r
← VQ \{vj1 , . . . , vjl };
← VG \{ui1 , . . . , uil }, CQ
CG
r
| > 0 then
if |CG
for m ← 1 to λQ do
r
∩ VQm 6= ∅ then
if CQ
r
∩ VQm };
z ← min{CQ
generate successor q, s.t.,
ψq ← ψr ∪ {(uil+1 → z)};
succ ← succ ∪ {q};

10
11
12
13
14
15

else
generate successor q, s.t., ψq ← ψr ∪
succ ← succ ∪ {q};

S

r {(u
z∈CQ

n

Replacing BasicGenSuccr (see Alg. 1) with GenSuccr
to generate successors, we reduce a large number of invalid
and redundant mappings and then create a small search tree.
Next, we analyze the size of search tree, i.e., the total number
of nodes in the search tree.
Nodes in the search tree are grouped into different layers
based on their distances from the root node. Hence, the search
tree is divided into layers, one for each depth. When all
vertices in VG were processed, for any node in the layer |VG |
(starting from 0), it generates a unique successor leaf node,
thus we regard this layer as the last layer. Namely, we only
need to generate the first |VG | layers. For the layer l, let Nl be
the total number of nodes in this layer. So, the total number of
P|VG |
nodes in the search tree can be computed as SR = l=0
Nl .
For the layer l, the set of vertices in G that have been
l
= {ui1 , . . . , uil }, correspondingly, we must
processed is BG
choose l vertices from VQ ∪ {v n } as their mapped vertices.
l
Let BQ
= {vj1 , . . . , vjl } be the l selected vertices, then we
use a vector x = [x1 , . . . , xλQ +1 ] to represent it, where xm is
l
that belong to VQm , i.e., xm =
the number of vertices in BQ
m
l
|BQ ∩ VQ |, for 1 ≤ m ≤ λQ , and xλQ +1 is the number of
l
dummy vertices in BQ
. Thus, we have
λQ +1

r
r
| then
| > |CQ
if |CG
generate successor q, s.t., ψq ← ψr ∪ {(uil+1 → v n )};
succ ← succ ∪ {q};

9

D. Search Space Analysis

→ z)};

return succ;

Example 4. Consider graphs G and Q in Figure 1. Figure 3
shows the entire search tree of G and Q created layer-bylayer by using GenSuccr, where vertices in G are processed
in the order (u1 , u2 , u3 , u4 ). In a layer, the values inside
the nodes are the possible mapped vertices (e.g., v1 and v4
in layer one are the possible mapped vertices of u1 ). The
sequence of vertices on the path from root to each leaf node
gives a complete graph mapping. In this example, we totally
generate 4 graph mappings, and then easily compute that
ged(G, Q) = 4.

X

xm = l.

(1)

m=1

where 0 ≤ xm ≤ |VQm | for 1 ≤ m ≤ λQ , and xλQ +1 ≥ 0.
For a solution x of equation (1), it corresponds to a
l
unique BQ
. The reason is as follows: In Rule 2, each time
we only select the smallest unmapped vertex in VQm as the
mapped vertex, for 1 ≤ m ≤ λQ . Thus, for xm in x, it means
l
that BQ
contains the first xm smallest vertices in VQm . For
example, let us consider the search tree in Figure 3. Let l = 3
l
and x = [2, 1, 0], then BQ
contains the first 2 smallest vertices
in VQ1 , i.e., v1 and v2 , and the smallest vertex in VQ2 , i.e., v4 ,
l
then we have BQ
= {v1 , v2 , v4 }.
Let Ψl be the set of solutions of equation (1), then it
l
covers all possible BQ
. For a solution x, it totally produces
l!
different
(partial)
canonical codes. For example,
QλQ +1
m=1

xm !

for x = [2, 1, 0], it produces 3 partial canonical codes, i.e.,
h1, 1, 2i, h1, 2, 1i and h2, 1, 1i. As we know, each (partial)
l
canonical code corresponds to a (partial) mapping from BG

l
to BQ
, which is associated with a node in the layer l, thus

Nl =

X
x∈Ψl

l!
QλQ +1
m=1

.

(2)

xm !

In Rule 1, only when the number of unmapped vertices in G
is greater than that in Q, we select a dummy vertex v n as the
mapped vertex. As a result, if |VG | ≤ |VQ | then the number
|V |
of dummy vertices in BQ G is 0 otherwise is |VG | − |VQ |. Let
l = |VG | and we then discuss the following two cases:
Case 1. When |VG | > |VQ |. For any x, we have
xλQ +1 = |VG | − |VQ |. Then equation (1) is reduced
PλQ
PλQ
m
to
m=1 xm = |VQ |. Since
m=1 |VQ | = |VQ | and
m
0 ≤ xm ≤ |VQ |, for 1 ≤ m ≤ λQ , then equation (1) has
λ
a unique solution x = [|VQ1 |, . . . , |VQ Q |, |VG | − |VQ |], Thus,
|VG |!
. As N0 = 1 and N1 ≤ · · · ≤
N|VG | =
QλQ
m

•

•

to denote the interval of layer l. For a node r in layer l, its
successor n in next layer l + 1 is allowed to be expanded
only when f (n) is in the interval bs[l], i.e., bs[l].fmin ≤
f (n) < bs[l].fmax .
priority queues open[0], . . . , open[|VG |], where open[l]
(0 ≤ l ≤ |VG |) is used to store the expanded nodes in
layer l.
a table new, where new[H(r)] stores all successors of r
and H(r) is a hash function which assigns a unique ID
to r.

B. Algorithm

Algorithm 3 performs an iterative search to obtain a more
and more tight upper bound ub of GED until ub = ged(G, Q).
In an iteration, we perform the following two steps: (1) we
utilize beam search [10] to quickly reach to a leaf node whose
(|VG |−|VQ |)! m=1 |VQ |!
edit cost is an upper bound of GED, then we update ub (line 4).
|VG |!
N|VG | , we obtain SR ≤ |VG |
+ 1.
Q λQ
As beam search expands at most w nodes in each layer, some
m
(|VG |−|VQ |)! m=1 |VQ |!
Case 2. When |VG | ≤ |VQ |. For any x, we have xλQ +1 = 0. nodes are inadmissible pruned when the number of nodes in a
PλQ
Then equation (1) is reduced to
x = |VG |. As layer is greater than w, where w is the beam width; Thus, (2)
Pm=1 m
we backtrack and pop items from bs until a layer l such
|VG |!
|VG | ≤ |VQ |, we have N|VG | =
≤
x∈Ψ|VG | QλQ
that bs.top().fmax < ub (lines 5–6), and then shift the range
m=1 xm !
xλQ +1 =0
P
of bs.top() (line 9) to re-expand those inadmissible pruned
|VQ |!
|VQ |!
= QλQ
. Since N0 = 1 and
x∈Ψ|VQ | QλQ
m |!
xm !
|VQ
nodes in next iteration to search for tighter ub. If l = −1,
m=1
m=1
xλQ +1 =0
it means that we finish a complete search and then obtain
|VQ |!
N1 ≤ · · · ≤ N|VG | , we have SR ≤ |VG | QλQ
+ 1.
m
ub = ged(G, Q) (lines 7–8).
m=1 |VQ |!
However, this will overestimate SR when |VG |  |VQ |.
In procedure Search, we perform a beam search starting
For the layer l, if we do not consider the isomorphic vertices from layer l to re-expand those inadmissible pruned nodes
l
l
l
. Since there to search for tighter ub, where P QL and P QLL are two
to BQ
, then there are l! mappings from BG
in BQ


|VQ |
|VQ |
l
,
we
have
N
≤
· l! = temporary priority queues used to record expanded nodes in
are at most
possible
B
l
Q
l
l
P|VG |
P|VG | |VQ |!
|VQ |!
two adjacent layers. Each time we pop a node r with the
l=0 Nl ≤
l=1 (|VQ |−l)! + 1
(|VQ |−l)! . So, SR =
smallest cost to expand (line 4). If r is a leaf node, then
P|VG |
|VQ |!
= (|VQ |−|VG |)! l=1 Q|VG |−l 1
+1
we
update ub and stop the search as g(z) ≥ g(r) holds for
(|V
|−|V
|+m)
Q
G
P|VG | m=1
|VQ |!
|VQ |!
1
∀z
∈ P QL (line 7); otherwise, we call ExpandNode to
≤ (|VQ |−|V
+
1
≤
2
+
1.
l=1 2|VG |−l
(|VQ |−|VG |)!
G |)!
generate all successors of r that are allowed to be expanded
|VG ||VG |!
);
In summary, if |VG | > |VQ |, SR = O(
QλQ
m |!
in next layer and then insert them into P QLL (lines 8–9). As
(|VG |−|VQ |)! m=1
|VQ
|V ||V |!
|VQ |!
at most w successors are allowed to be expanded, we only
otherwise, SR = O(min{ QλQG Qm , (|VQ |−|V
}).
G |)!
m=1 |VQ |!
keep the best w nodes (i.e., the smallest cost) in P QLL,
and the nodes left are inadmissible pruned (lines 11–13).
IV. GED C OMPUTATION USING B EAM - STACK S EARCH
Correspondingly, line 12, we modify the right boundary of
The previous section shows that we create a small search bs.top() as the lowest cost among all inadmissible pruned
space. However, we still need an efficient search paradigm to nodes to ensure that the cost of the w successors currently
traverse the search space to seek for an optimal graph mapping expanded is in this interval.
to compute GED. In this section, based on the efficient search
In procedure ExpandNode, we generate all successors of r
paradigm, beam-stack search [11], we give our approach for that are allowed to be expanded. Note that, all nodes first
the GED computation.
generated are marked as false. If r has not been visited, i.e.,
r .visited = false, then we call GenSuccr (i.e., Alg. 2) to
A. Data Structures
generate all successors of r and mark r as visited (lines 3–4);
For a node r in the search tree, f (r ) = g(r ) + h(r ) is the otherwise, we directly read all successors of r from new
total edit cost assigned to r, where g(r) is the edit cost of the (line 6). For a successor n of r, if f (n) ≥ ub or n.visited =
partial path accumulated so far, and h(r) is the estimated edit true, then we safely prune it, see Lemma 1. Meanwhile,
cost from r to a leaf node, which is less than or equal to the we delete all successors of n from new (line 9); otherwise,
real cost. Before formally presenting the algorithm, we first if bs.top().fmin ≤ f (n) < bs.top().fmax , we expand n. If all
introduce the data structures used as follows:
successors of r are safely pruned, we safely prune r, and
• a beam stack bs, which is a generalized stack. Each item
delete r from open[l] and its successors from new, resin bs is a half-open interval [fmin , fmax ), and we use bs[l] pectively (line 13).

Lemma 1. In ExpandNode, if f (n) ≥ ub or n.visited =
true, i.e., line 8, we safely prune n.
Proof: For the case f (n) ≥ ub, it is trivial. Next we prove
it in the other case.
Consider bs in the last iteration. Assuming that in this
iteration we perform Search starting from layer k (i.e.,
backtracking to layer k in the last iteration, see lines 5–6
in Alg. 3), and node r and its successors n are in layers l
and l + 1, respectively, then k ≤ l and bs[m].fmax ≥ ub
for l + 1 ≤ m ≤ |VG |. If n.visited = true, then we must
have called ExpandNode to generate successors of n in the
last iteration. For a successor x of n in layer l + 2, if x is
inadmissible pruned, then f (x) ≥ bs[l + 1].fmax ≥ ub, thus
we safely prune x; otherwise, we consider a successor of x and
repeat this decision process until a leaf node z. Then, it must
satisfy that f (z) = g(z) ≥ ub. Thus, none of descendants of n
can produce tighter ub. So, we safely prune it.
Lemma 2. A node r is visited at most O(|VQ |) times.
Proof: For a node r in layer l, it generates at most
|VQ | + 1 successors by GenSuccr. In order to fully generate
all successors in layer l + 1, we backtrack to this layer at most
|open[l]|·(|VQ |+1)/w ≤ |VQ |+1 times as |open[l]| ≤ w. After
that, when we visit r once again, all successors of r are either
pruned or marked, thus we safely prune them by Lemma 1.
So, r cannot produce tighter ub in this iteration and we safely
prune it, i.e., lines 12–13 in ExpandNode. Plus the first time
when generating r, we totally visit r at most |VQ | + 3 times,
i.e., O(|VQ |).
Theorem 4. Given two graphs G and Q, BSS GED must
return ged(G, Q).
Proof: By Lemma 2, a node is visited at most O(|VQ |)
times, thus all nodes are totally visited at most O(|VQ |SR )
times (see SR in Section III-D), which is finite. So, BSS GED
always terminates. In Search, we always update ub =
min{ub, g(r)} each time. Thus, ub becomes more and more
tight. Next, we prove that ub converges to ged(G, Q) when
BSS GED terminates by contradiction.
Suppose that ub > ged(G, Q). Let r and n be the leaf nodes
whose edit cost is ub and ged(G, Q), respectively. Let x in
layer l be the common ancestor of r and n, which is farthest
from root. Let z in layer l + 1 be a successor of x, which is
the ancestor of n. Then f (z) ≤ f (n) = ged(G, Q) < ub.
For z, it is not in the path from root to r, thus it must be
pruned in an iteration, i.e., f (z) ≥ ub or z.visited = false,
line 8 in ExpandNode (if z has been inadmissible pruned, we
backtrack and shift the range of bs[l] to re-expand it until that z
is pruned or marked). For the case f (z) ≥ ub, it contradicts
that f (z) < ub, and for the other case, we conclude that
f (n) ≥ ub by using the same analysis in Lemma 1, which
contradicts that f (n) < ub. Thus, ub = ged(G, Q).
V. S EARCH S PACE P RUNING
In BSS GED, for a node r, if f (r) = g(r) + h(r) ≥ ub,
then we safely prune r. As g(r) is the irreversible edit cost,

Algorithm 3: BSS GED(G, Q, w)
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7

ψroot ← ∅, bs ← ∅, open[] ← ∅, new[] ← ∅, l ← 0, ub ← ∞;
bs.push([0, ub)), open[0].push(root);
while bs 6= ∅ do
Search(l, ub, bs, open, new);
while bs.top().fmax ≥ ub do
bs.pop(), l ← l − 1;
if l = −1 then
return ub;
bs.top().fmin ← bs.top().fmax , bs.top().fmax ← ub;
return ub;
procedure Search(l, ub, bs, open, new)
P QL ← open[l], P QLL ← ∅;
while P QL 6= ∅ or P QLL 6= ∅ do
while P QL 6= ∅ do
r ← arg minn {f (n) : n ∈ P QL};
P QL ← P QL\{r};
if ψr is a complete graph mapping then
ub ← min{ub, g(r)}, return;
succ ←ExpandNode(r, l, ub, open, new);
P QLL ← P QLL ∪ succ;

8
9

if |P QLL| > w then
keepNodes ← the best w nodes in P QLL;
bs.top().fmax ← min{f (n) : n ∈ P QLL ∧ n ∈
/
keepNodes};
P QLL ← keepNodes;

10
11
12
13

open[l + 1] ← P QLL, P QL ← P QLL;
P QLL ← ∅, l ← l + 1, bs.push([0, ub));

14
15

1
2
3
4
5
6
7
8
9
10
11

procedure ExpandNode(r, l, ub, open, new)
expand ← ∅;
if r.visited = false then
succ ←GenSuccr(r);
new[H(r)] ← succ, r.visited ← true;
else
succ ← new[H(r)];
foreach n ∈ succ do
if f (n) ≥ ub or n.visited = true then
new[H(n)] ← ∅;
else if bs.top().fmin ≤ f (n) < bs.top().fmax then
expand ← expand ∪ {n};

13

if ∀n ∈ succ, f (n) ≥ ub or n.visited = true then
open[l] ← open[l]\{r}, new[H(r)] ← ∅;

14

return expand;

12

the upper bound ub and lower bound h(r) are the keys to
perform pruning. Here, we give two heuristics to prune the
search space as follows: (1) proposing an efficient heuristic
function to obtain tighter h(r); (2) ordering vertices in G to
enable to fast find of tighter ub.
A. Estimating h(r)
Let P be an optimal edit path that transforms G to Q,
then it contains at least max{|VG |, |VQ |} − |ΣVG ∩ ΣVQ | edit
operations performed on vertices. Next, we only consider the
edit operations in P performed on edges. Assuming that we
first delete γ1 edges to obtain G1 , then insert γ2 edges to

obtain G2 , and finally change γ3 edge labels to obtain Q.
When transforming G to G1 by deleting γ1 edges, we
have ΣEG1 ⊆ ΣEG , thus |ΣEG ∩ ΣEQ | ≥ |ΣEG1 ∩ ΣEQ |.
When transforming G1 to G2 by inserting γ2 edges, for
each inserted edge, we no longer change its label, thus
|ΣEG2 ∩ ΣEQ | = |ΣEG1 ∩ ΣEQ | + γ2 . When transforming G2 to Q by changing γ3 edge labels, we need to
substitute at least |ΣEQ | − |ΣEG2 ∩ ΣEQ | edge labels, thus
γ3 ≥ |ΣEQ | − |ΣEG2 ∩ ΣEQ |. So, we have
|ΣEG ∩ ΣEQ | + γ2 + γ3 ≥ |EQ |.

(3)
P3

Let lb(G, Q) = max{|VG |, |VQ |} − |ΣVG ∩ ΣVQ | + i=1 γi ,
then ged(G, Q) ≥ lb(G, Q). Obviously, the lower bound
lb(G, Q) should be as tight as possible. In order to achieve
this goal, we utilize the degree sequence of a graph.
For a vertex u in G, its degree du is the number of edges
adjacent to u. The degree sequence δG = [δG [1], . . . , δG [|VG |]]
of G is a permutation of d1 , . . . , d|VG | such that δG [i ] ≥ δG [j ]
for i < j . For unequal size G and Q, we extend δG and δQ
0
0
=
= [δG [1], . . . , δG [|VG |], 01 , . . . , 0|V |−|VG | ] and δQ
as δG
[δQ [1], . . . , δQ [|VQ |], 01 , . . . , 0|V |−|VQ | ], P
resp., where |V | =
0
max{|VG |, |VQ |}. Let ∆1 (G, Q) = d δ0 [i]>δ0 [i] (δG
[i] −
G
Q
P
0
0
0
δQ [i])/2e and ∆2 (G, Q) = d δ0 [i]≤δ0 [i] (δQ [i] − δG [i])/2e,
G
Q
for 1 ≤ i ≤ |V |, then we give the respective lower bounds
of γ1 and γ2 as follows:
Theorem 5 ([14]). Given two graphs G and Q, we have γ1 ≥
∆1 (G, Q) and γ2 ≥ ∆2 (G, Q).
Based on inequality (3) and Theorem 5, we then establish
the following lower bound of GED in Theorem 6.
Theorem 6. Given two graphs G and Q, we
have ged(G, Q) ≥ LB(G, Q), where LB(G, Q) =
max{|VG |, |VQ |} − |ΣVG ∩ ΣVQ | + max{∆1 (G, Q) +
∆2 (G, Q), ∆1 (G, Q) + |EQ | − |ΣEG ∩ ΣEQ |}.
Next, we discuss how to estimate h(r) based on Theorem 6.
Let ψr = {(ui1 → vj1 ), . . . , (uil → vjl )} be the partial
mapping associated with r, then we divide G into two parts Gr1
and Gr2 , where Gr1 is the mapped part of G, s.t., VGr1 =
{ui1 , . . . , uil } and EGr1 = {e(u, v) : u, v ∈ VGr1 ∧ e(u, v) ∈
EG }, and Gr2 is the unmapped part, s.t., VGr2 = VG \VGr1 and
EGr2 = {e(u, v) : u, v ∈ VGr2 ∧ e(u, v) ∈ EG }. Similarly, we
also obtain Qr1 and Qr2 . For r, by Theorem 6 we know that
LB(Gr2 , Qr2 ) is lower bound of ged(Gr2 , Qr2 ) and hence can
adopt it as h(r). However, for the potential edit cost on the
edges between Gr1 (resp. Qr1 ) and Gr2 (resp. Qr2 ), LB(Gr2 , Qr2 )
has not covered it.
Definition 7 (Outer Edge Set). For a vertex u in Gr1 , we define
its outer edge set as Ou = {e(u, v) : v ∈ VGr2 ∧e(u, v) ∈ EG },
which consists of edges adjacent to u that neither belong to
EGr1 nor EGr2 .
Correspondingly, Oψ(u) is the outer edge set of ψ(u).
Note that, if ψ(u) = v n , then Oψ(u) = ∅. Thus, ΣOu =
{L(e(u, v)) : e(u, v) ∈ Ou } is the label multiset of Ou . In
order to make Ou and Oψ(u) have the same label multiset,

assuming that we first delete ξ1u and then insert ξ2u edges on u,
and finally substitute ξ3u labels on the outer edges adjacent to u.
Similar to the previous analysis of obtaining inequality (3), we
have

|Ou | − ξ1u + ξ2u = |Oψ(u) |
(4)
|ΣOu ∩ ΣOψ(u) | + ξ2u + ξ3u ≥ |Oψ(u) |
P3
Thus, i=1 ξiu ≥ |Oψ(u) |−|ΣOu ∩ΣOψ(u) |. As |Ou |+ξ2u =
P3
|Oψ(u) | + ξ1u , we have i=1 ξiu ≥ |Oψ(u) | − |ΣOu ∩ ΣOψ(u) | +
ξ1u = |Ou |−|ΣOu ∩ΣOψ(u) |+ξ2u ≥ |Ou |−|ΣOu ∩ΣOψ(u) |. So,
P3
u
i=1 ξi ≥ max{|Ou |, |Oψ(u) |} − |ΣOu ∩ ΣOψ(u) |. Adding all
vertices in Gr1 , we obtain the lower bound LB1r as follows:
X
(max{|Ou |, |Oψ(u) |}
LB1r = LB(Gr2 , Qr2 ) +
u∈VGr
(5)
1
−|ΣOu ∩ ΣOψ(u) |).
Definition 8 (Outer Vertex Set). For a vertex u in Gr1 , we
define its outer vertex set as Au = {v : v ∈ VGr2 ∧ e(u, v) ∈
EG }, which consists of vertices in Gr2 adjacent to u.
Correspondingly, Aψ(u) denotes the outer vertex set
n
of ψ(u).
S Note that, if ψ(u) = v , then Aψ(u) =r ∅. Thus,
r
AG = u∈VGr Au denotes the set of vertices in G2 adjacent
1
to those outer Sedges between Gr1 and Gr2 . Similarly, we
obtain ArQ = z∈VQr Az . If |ArG | ≤ |ArQ |, then we need
1
to insert at leastP
|ArQ | − |ArG | outer edges on some vertices
u
in Gr1 , hence
≥ |ArQ | − |ArG |; otherwise,
u∈VGr ξ2
P
1
r
u
r
u∈VGr ξ1 ≥ |AG | − |AQ |. Considering equation (4), for a
1
r
vertex P
u in G1 , we have ξ2u + ξ3u ≥P|Oψ(u) | − |ΣOu ∩ ΣOψ(u) |.
Thus, u∈VGr (ξ1u + ξ2u + ξ3u ) ≥ u∈VGr (|Oψ(u) | − |ΣOu ∩
1
1
u
u
ΣOψ(u) |)+max{0,
|ArG |−|ArQ |}. As |O
u |+ξ2 = |Oψ(u) |+ξ1 ,
P
P
u
u
u
we have u∈VGr (ξ1 + ξ2 + ξ3 ) ≥ u∈VGr (|Ou | − |ΣOu ∩
1
1
ΣOψ(u) |) + max{0, |ArQ | − |ArG |}. So, we obtain the lower
bounds LB2r and LB3r as follows:
X
LB2r = LB(Gr2 , Qr2 ) +
(|Oψ(u) | − |ΣOu ∩ ΣOψ(u) |)
u∈VGr

1

+max{0, |ArG | − |ArQ |}.
(6)
LB3r = LB(Gr2 , Qr2 ) +

X

(|Ou | − |ΣOu ∩ ΣOψ(u) |)
(7)

u∈VGr

1

+max{0, |ArQ |

−

and LB3r , we
Based on the above lower bounds
r
r
r
adopt h(r) = max{LB1 , LB2 , LB3 } as the heuristic function
to estimate the edit cost of a node r in BSS GED.
Example 5. Consider graphs G and Q in Figure 4. For a node r
associated with a partial mapping ψ(r) = {(u1 → v1 ), (u2 →
v2 )}, then Gr2 = ({u3 , u4 , u5 }, {e(u3 , u5 ), e(u4 , u5 )}, L) and
Qr2 = ({v3 , v4 , v5 , v6 }, {e(v3 , v6 ), e(v4 , v6 ), e(v5 , v6 )}, L). By
Theorem 6, we compute LB(Gr2 , Qr2 ) = 2. Considering
vertices u1 and u2 that have been processed, we have Ou1 =
{e(u1 , u3 ), e(u1 , u4 )} and Ou2 = {e(u2 , u4 )}, and then obtain
ΣOu1 = {a, a} and ΣOu2 = {b}. Similarly, we have
LB1r ,

LB2r

|ArG |}.

ΣOv1 = {a, a} and ΣOv2 = {b}. Thus LB1r = LB(Gr2 , Qr2 ) +
P
u∈{u1 ,u2 } (max{|Ou |, |Oψ(u) |} − |ΣOu ∩ ΣOψ(u) |) = 2. As
ArG = {u3 , u4 } P
and ArQ = {v3 , v4 , v5 }, we obtain LB2r =
r
r
LB(G2 , Q2 ) + u∈{u1 ,u2 } (|Oψ(u) | − |ΣOu ∩ ΣOψ(u) |) +
max{0,
|ArG | − |ArQ |} = 2, and LB3r = LB(Gr2 , Qr2 ) +
P
r
r
u∈{u1 ,u2 } (|Ou | − |ΣOu ∩ ΣOψ(u) |) + max{0, |AQ | − |AG |}
r
r
r
= 3. So, h(r) = max{LB1 , LB2 , LB3 } = max{2, 2, 3} = 3.
u1

A

u3

b

A

A

a
u5

u2

B

a

a

u4 v3

b
C

G

v1
a
A

A

v2
b

B

a
v4

A

a a
v6 C

B

v5

b

Q

Fig. 4: Example of two comparing graphs G and Q.
B. Ordering Vertices in G
In BSS GED, we use GenSuccr to generate successors.
However, we need to determine the processing order of
vertices in G at first, i.e., (ui1 , . . . , ui|VG | ) (see Section II-C).
The most primitive way is to adopt the default vertex order
in G, i.e., (u1 , . . . , u|VG | ), which is used in A? -GED [5] and
DF-GED [16]. However, this may be inefficient as it has not
considered the structure relationship between vertices.
For vertices u and v in G such that e(u, v) ∈ EG , if u
has been processed, then in order to early obtain the edit cost
on e(u, v), we should process v as soon as possible. Hence,
our policy is to traverse G in a depth-first order to obtain
(ui1 , . . . , ui|VG | ). However, starting from different vertices to
traverse, we may obtain different orders.
In section V-A, we have proposed the heuristic estimate
function h(r), where an important part is LB(Gr2 , Qr2 ) presented in Theorem 6. As we know, the more structure Gr2
and Qr2 keep, the tighter lower bound LB(Gr2 , Qr2 ) we may
obtain. As a result, we preferentially consider vertices with
small degrees. This is because that when we first process those
vertices, the left unmapped parts Gr2 and Qr2 could keep the
structure as much as possible.
Definition 9 (Vertex Partial Order). For two vertices u and v
in G, we define that u ≺ v if and only if du < dv or du =
dv ∧ u < v.

verse G in a depth-first order, and finally obtain order =
[u2 , u4 , u1 , u3 , u5 ]. Thus, we process vertices in G in the order
(u2 , u4 , u1 , u3 , u5 ) in BSS GED.
VI. E XTENSION OF BSS GED
In this section, we extend BSS GED to solve the GED
based graph similarity search problem: Given a graph database
G = {G1 , G2 , . . . }, a query graph Q and an edit distance
threshold τ , the problem aims to find all graphs in G satisfy
ged (Gi , Q) ≤ τ . As computing GED is an NP-hard problem,
most of the existing methods, such as [12], [14], [19], [20],
all use the filter-and-verify schema, that is, first filtering some
graphs in G to obtain candidate graphs, and then verifying
them.
Here, we also use this strategy. For each data graph Gi ,
we compute the lower bound LB(Gi , Q) by Theorem 6. If
LB(Gi , Q) > τ , then ged(Gi , Q) ≥ LB(Gi , Q) > τ and hence
we filter Gi ; otherwise, Gi becomes a candidate graph.
For a candidate graph Gi , we need to compute ged(Gi , Q)
to verify it. The standard method is that we first compute
ged(Gi , Q) and then determine Gi is a required graph or not
by judging ged(Gi , Q) ≤ τ . Incorporating τ with BSS GED,
we can further accelerate it as follows: First, we set the initial
upper bound ub as τ + 1 (line 1 in Alg. 3). Then, during the
execution of BSS GED, when we reach to a leaf node r, if
the cost of r (i.e., g(r)) satisfies g(r) ≤ τ , then Gi must be a
required graph and we stop running of BSS GED. The reason
is that g(r) is an upper bound of GED and hence we know
that ged(Gi , Q) ≤ g(r) ≤ τ .
Algorithm 4: DetermineOrder(G)
1
2
3
4
5
6
7
1
2
3
4
5
6

In Algorithm 4, we give the method to compute the order
(ui1 , . . . , ui|VG | ). First, we sort vertices to obtain a global
order array rank based on the partial order ≺ (line 2). Then,
we call DFS to traverse G in a depth-first order (lines 3–6).
In DFS, we sequentially insert u into order and then mark u
as visited, i.e., set F [u] = true (line 1). Then, we obtain the
set Nu of vertices adjacent to u (line 2). Finally, we select a
smallest unvisited vertex v from Nu based on the partial order
≺, and then recursively call DFS to traverse the subtree rooted
at v (lines 3–7).
Example 6. For the graph G in Figure 4, we first compute rank = [u2 , u1 , u3 , u5 , u4 ]. Starting from u2 , we tra-

7

F [1..|VG |] ← false, order [] ← ∅, count ← 1;
rank ← sort vertices in VG according to the partial order ≺;
for i ← 1 to |VG | do
u ← rank [i];
if F [u] = false then
DFS(u, F, rank, order, count)
return order
procedure DFS(u, F, rank, order, count)
order[count] ← u, count ← count + 1, F [u] ← true;
Nu ← {v : v ∈ VG ∧ e(u, v) ∈ EG };
while |Nu | > 0 do
v ← argminj {rank [j] : j ∈ Nu };
Nu ← Nu \{v};
if F [v] = false then
DFS(v, F, rank, order, count);

VII. E XPERIMENTAL R ESULTS
In this section, we perform comprehensive experiments and
then analyse the obtained results.
A. Datasets and Settings
We choose several real and synthetic datasets used in the
experiment, described as follows:

A ID S - 1 0 K

P R O T E IN - 3 0 0

9 5
9 0
B S S _ G E D b
B S S _ G E D

8 5

1 0 0

A v e r a g e s o lv e r a tio ( % )

A v e r a g e s o lv e r a tio ( % )

A v e r a g e s o lv e r a tio ( % )

S 1 K .E 3 0 .D 3 0 .L 2 0

1 0 0

1 0 0

8 0
6 0
4 0

B S S _ G E D b
B S S _ G E D

2 0

8 0

A v e r a g e r u n n in g tim e ( s )

3 0 0

1 2
1 5
Q u e r y g r o u p
A ID S - 1 0 K

1 8

6

2 1

B S S _ G E D b
B S S _ G E D

1 5 0

1 2
1 5
Q u e r y g r o u p
P R O T E IN - 3 0 0

1 0 0 0

2 5 0
2 0 0

9

1 0 0
5 0
0

1 8

4 0

6

6 0 0

9

1 2
1 5
Q u e r y g r o u p

1 8

B S S _ G E D b
B S S _ G E D

2 0 0

1 2
1 5
Q u e r y g r o u p
S 1 K .E 3 0 .D 3 0 .L 2 0

1 8

2 1

1 8

2 1

B S S _ G E D b
B S S _ G E D

6 0 0
4 0 0
2 0 0
0

6

2 1

9

8 0 0

0

6

B S S _ G E D b
B S S _ G E D

1 0 0 0

8 0 0

4 0 0

6 0

2 0

2 1

A v e r a g e r u n n in g tim e ( s )

9

A v e r a g e r u n n in g tim e ( s )

6

8 0

9

1 2
1 5
Q u e r y g r o u p

1 8

2 1

6

9

1 2
1 5
Q u e r y g r o u p

Fig. 5: Effect of GenSuccr on the performance of BSS GED

AIDS1 . It is an antivirus screen compound dataset from
the Development and Therapeutics Program in NCI/NIH,
which contains 42687 chemical compounds. We generate
labeled graphs from these chemical compounds and omit
Hydrogen atom as did in [13], [14].
2
• PROTEIN . It is a protein database from the Protein
Data Bank, constituted of 600 protein structures. Vertices
represent secondary structure elements and are labeled
with their types (helix, sheet or loop). Edges are labeled
to indicate if two elements are neighbors or not.
• Synthetic. The synthetic dataset is generated by the synthetic graph data generator GraphGen3 . In the experiment,
we generate a density graph dataset S1K.E30.D30.L20,
which means that this dataset contains 1000 graphs; the
average number of edges in each graph is 30; the density4
of each graph is 30%; and the distinct vertex and edge
labels are 20 and 5, respectively.
Due to the hardness of computing GED, existing methods,
such as A? -GED [5], DF-GED [16] and CSI GED [4], cannot
obtain GED of large graphs within a reasonable time and
memory. Therefore, for AIDS and PROTEIN, we exclude large
graphs with more than 30 vertices as did in [1], and then
randomly select 10000 and 300 graphs to make up the datasets
AIDS-10K and PROTEIN-300. For S1K.E30.D30.L20, we use
the entire dataset.
As suggested in [1], [4], for each dataset, we randomly select 6 query groups, where each group consists of 3 data graphs
having three consecutive graph sizes. Specifically, the number
of vertices of each group is in the range: 6 ± 1, 9 ± 1, 12 ±
1, 15 ± 1, 18 ± 1 and 21 ± 1.
For the tested database D = {D1 , D2 , . . . } and query group
T = {T1 , T2 , . . . }, we need to perform |D| × |T | times GED
computation. For each pair of the GED computation, we set the
•

1 http://dtp.nci.nih.gov/docs/aids/aidsdata.html
2 http://www.fki.inf.unibe.ch/databases/iam-graph-database/download-theiam-graph-database
3 http://www.cse.ust.hk/graphgen/
2|EG |
4 the density of a graph G is defined as
.
|V |(|V |−1)
G

G

available time and memory be 1000s and 24GB, respectively,
and then define the metric average solve ratio as follows:
P|D| P|T |
i=1
j=1 slove(Di , Tj )
sr =
.
(8)
|D| × |T |
where slove(Di , Tj ) = 1 if we obtain ged(Di , Tj ) within both
1000s and 24GB, and slove(Di , Tj ) = 0 otherwise. Obviously,
sr should be as large as possible.
We have conducted all experiments on a HP Z800 PC with
a 2.67GHz GPU and 24GB memory, running Ubuntu 12.04
operating system. We implement our algorithm in C++, with
-O3 to compile and run. For BSS GED, we set the beam
width w = 15 for the sparse graphs in datasets AIDS-10K and
PROTEIN-300, and w = 50 for the density graphs in dataset
S1K.E30.D30.L20.
B. Evaluating GenSuccr
In this section, we evaluate the effect of GenSuccr on
the performance of BSS GED. To make a comparison, we
replace GenSuccr with BasicGenSuccr (i.e., Alg. 1) and
then obtain BSS GEDb , where BasicGenSuccr is the basic
method of generating successors used in A? -GED [5] and DFGED [16]. In BSS GEDb , we also use the same heuristics
proposed in Section V. Figure 5 shows the average solve ratio
and running time.
As shown in Figure 5, the average solve ratio of BSS GED
is much higher than that of BSS GEDb , and the gap between them becomes larger as the query graph size increases. This indicates that GenSuccr provides more reduction on the search space for larger graphs. Regarding the
running time, BSS GED achieves the respective 1x–5x, 0.4x–
1.5x and 0.1x–4x speedup over BSS GEDb on AIDS-10K,
PROTEIN-300 and S1K.E30.D50.L20. Thus, we create a small
search space by GenSuccr.
C. Evaluating BSS GED
In this section, we evaluate the effect of beam-stack search
and heuristics on the performance of BSS GED. We fix

datasets AIDS-10K, PROTEIN-300 and S1K.E30.D30.L20 as
the tested datasets and select their corresponding groups 15±1
as the query groups, respectively.
(1). Effect of w
As we know, beam-stack search achieves a flexible tradeoff between available memory and expensive backtracking by
setting different w, thus we vary w to evaluate its effect on
the performance. Figure 6 shows the average solve ratio and
running time.
4 0 0

9 0

A ID S -1 0 K
P R O T E IN -3 0 0
S 1 K .E 3 0 .D 3 0 .L 2 0

8 0
7 0

A v e r a g e r u n n in g tim e ( s )

A v e r a g e s o lv e r a tio ( % )

1 0 0

3 0 0
A ID S -1 0 K
P R O T E IN -3 0 0
S 1 K .E 3 0 .D 3 0 .L 2 0

2 0 0
1 0 0
0

6 0
1

5

1 5
B e a m

5 0
w id th w

1 0 0

1

5 0 0

5

1 5
B e a m

5 0
w id th w

1 0 0

5 0 0

Fig. 6: Effect of w on the performance of BSS GED.

B a s ic
+ h 1
+ h 2

A v e r a g e s o lv e r a tio ( % )

1 0 0
8 0
6 0
4 0
2 0
0
A ID S -1 0 K

P R O T E IN -3 0 0

S 1 K .E 3 0 .D 3 0 .L 2 0

A v e r a g e r u n n in g tim e ( s )

By Figure 6, we obtain that the average solve ratio first
increases and then decreases, and achieves maximum when
w = 15 on AIDS-10K and PROTEIN-300, and w = 50 on
S1K.E30.D30.L20. There are several factors may contribute
to this trend: (1) When w is too small, BSS GED may be
trapped into a local suboptimal solution and hence produces
lots of backtracking. (2) When w is too large, BSS GED
expands too many unnecessary nodes in each layer. Note that,
depth-first search is a special case of beam-stack search when
w = 1. Thus, beam-stack search performs better than depthfirst search. As previously demonstrated in [16], depth-first
search performs better than best-first search. Therefore, we
conclude that the beam-stack search paradigm outperforms
the best-first and depth-first search paradigms for the GED
computation.
1 0

3

1 0

2

1 0

1

B a is c
+ h 1
+ h 2

A ID S -1 0 K

P R O T E IN -3 0 0

S 1 K .E 3 0 .D 3 0 .L 2 0

Fig. 7: Effect of heuristics on the performance of BSS GED.
(2). Effect of Heuristics
In this part, we evaluate the effect of the proposed two
heuristics by injecting them one by one into the base algorithm. We use the term Basic for the baseline algorithm
without applying any heuristics. +h1 denotes the improved
algorithm of Basic by incorporating the first heuristics
(Section V-A). +h2 denotes the improved algorithm of +h1
by incorporating the second heuristic (Section V-B). Figure 7
plots the average solve ratio and running time.
By Figure 7, we know that the average solve ratio of
Basic is only 15% of that of +h1. This means that the
proposed heuristic function provides powerful pruning ability.
Considering the running time, +h1 brings the respective 50x,

2x and 9x speedup over Basic on AIDS-10K, PROTEIN300 and S1K.E30.D30.L20. Moreover, compared with +h1,
the running time needed by +h2 decreases 21%, 30% and
41% on AIDS-10K, PROTEIN-300 and S1K.E30.D30.L20,
respectively. Thus, the proposed two heuristics greatly boost
the performance.
D. Comparing with Existing GED Methods
In this section, we compare BSS GED with existing
methods A? -GED [5], DF-GED [16] and CSI GED [4].
Figure 8 shows the average solve ratio and running time.
By Figure 8, we know that BSS GED performs the best in
terms of average solve ratio. For A? -GED, it cannot obtain
GED of graphs with more than 12 vertices within 24GB. For
DF-GED, it cannot finish the GED computation of graphs with
more than 15 vertices in 1000s. Besides, for density graphs in
S1K.E30.D30.L20, the average solve ratio of CSI GED drops
sharply as the query graph size increases, which confirms that
it is unsuitable for dense graphs.
Regarding the running time, BSS GED still performs the
best in most cases. DF-GED performs better than A? -GED,
which is consistent with the previous results in [16]. Compared
with DF-GED, BSS GED achieves 50x–500x, 20x–2000x
and 15x–1000x speedup on AIDS-10K, PROTEIN-300 and
S1K.E30.D30.L20, respectively. Though CSI GED performs
better than BSS GED on AIDS-10K when the query graph
size is less than 9, BSS GED achieves 2x–5x speedup over
CSI GED when the graph size is greater than 12. Besides,
for S1K.E30.D30.L20, BSS GED achieves 5x–95x speedup
over CSI GED. Thus, BSS GED is efficient for the GED
computation on sparse as well as dense graphs.
E. Performance Evaluation on Graph Similarity Search
In this part, we evaluate the performance of BSS GED as a
standard graph similarity search query method by comparing it
with CSI GED and GSimJoin [19]. For each dataset described
in Section VII-A, we use its entire dataset and randomly select
100 graphs from it as query graphs. Figure 9 shows the total
running time (i.e., the filtering time plus the verification time).
It is clear from Figure 9 that BSS GED has the best performance in most cases, especially for large τ . For GSimJoin, it
cannot finish when τ ≥ 8 in AIDS and PROTEIN because of
the huge memory consumption. Compared with GSimJoin for
τ values where it can finish, BSS GED achieves the respective
1.6x–15000x, 3.8x–800x and 2x–3000x speedup on AIDS,
PROTEIN and S1K.E30.D30.L20. Considering CSI GED, it
performs slightly better than BSS GED when τ ≤ 4 on AIDS.
However, BSS GED performs much better than CSI GED
when τ ≥ 6 and the gap between them becomes larger as τ
increases. Specifically, BSS GED achieves 2x–28x, 1.2x–
100000x and 1.1x–187x speedup over CSI GED on AIDS,
PROTEIN and S1K.E30.D30.L20, respectively. As previously
discussed in [4], CSI GED performs much better than the
state-of-the-art graph similarity search query methods. Thus,
we conclude that BSS GED can efficiently finish the graph

4 0

6

1 0

3

1 0

2

1 0

1

1 0

0

1 0

- 1

1 0

- 2

1 0

9

G
- G
I_
S

E D
E D
G E D
_ G E D

- 3

9

8 0

G
- G
I_
S

E D
E D
G E D
_ G E D

6 0
4 0
2 0

1 0 0
8 0
6 0
4 0

1 8

1 2
1 5
Q u e r y g r o u p

1 8

E D
E D
G E D
_ G E D

6

1 0

3

1 0

2

1 0

1

1 0

0

1 0

2 1

G
- G
I_
S

E D
E D
G E D
_ G E D

0

2 1

G
- G
I_
S

A * D F
C S
B S

2 0

0

1 2
1 5
Q u e r y g r o u p
A ID S - 1 0 K

A * D F
C S
B S

6

S 1 K .E 3 0 .D 3 0 .L 2 0
A * D F
C S
B S

9

1 2
1 5
Q u e r y g r o u p
P R O T E IN - 3 0 0

1 8

A * D F
C S
B S

- 1

6

9

1 2
1 5
Q u e r y g r o u p

1 8

2 1

G
- G
I_
S

6

A v e r a g e r u n n in g tim e ( s )

A * D F
C S
B S

0

A v e r a g e r u n n in g tim e ( s )

A v e r a g e s lo v e r a tio ( % )

6 0

A v e r a g e r u n n in g tim e ( s )

A v e r a g e s o lv e r a tio ( % )

8 0

2 0

P R O T E IN - 3 0 0

1 0 0

A v e r a g e s lo v e r a tio ( % )

A ID S - 1 0 K
1 0 0

E D
E D
G E D
_ G E D

2 1

1 0

3

1 0

2

1 0

1

9

1 2
1 5
Q u e r y g r o u p
S 1 K .E 3 0 .D 3 0 .L 2 0

1 8

2 1

0

1 0
1 0

-1

1 0

-2

6

A * D F
C S
B S

9

1 2
1 5
Q u e r y g r o u p

G
- G
I_
S

1 8

E D
E D
G E D
_ G E D

2 1

Fig. 8: Performance comparison with existing state-of-the-art GED methods.

similarity search and runs much faster than existing methods.

VIII. R ELATED W ORKS
Recently, the GED computation has received considerable
attention. A? -GED [5], [7] and DF-GED [16] are two major
vertex-based mapping methods, which utilize the best-first
and depth-first search paradigms, respectively. Provided that
the heuristic function estimates the lower bound of GED of
unmapped parts, A? -GED guarantees that the first found complete mapping induces the GED of comparing graphs, which
seems very attractive. However, A? -GED stores numerous
partial mappings, resulting in a huge memory consumption. As
a result, it is only suitable for the small graphs. To overcome
this bottleneck, DF-GED performs a depth-first search, which
only stores the partial mappings of a path from the root to
a leaf node. However, it may be easily trapped into a local
suboptimal solution, leading to massive expensive backtracking. CSI GED [4] is an edge-based mapping method through
common substructure isomorphism enumeration, which has
an excellent performance on the sparse graphs. However, the
edge-based search space of CSI GED is exponential with
respect to the number of edges of comparing graphs, making it
naturally be unsuitable for dense graphs. Note that, CSI GED
only works for the uniform model, and [1] generalized it to
cover the non-uniform model.
Another work closely related to this paper is the GED
based graph similarity search problem. Due to the hardness
of computing GED, existing graph similarity search query
methods [12], [14], [17], [18], [19], [20] all adopt the filterand-verify schema, that is, first filtering graphs to obtain a
candidate set and then verifying those candidate graphs. In
the verification phase, most of the existing methods adopt
A? -GED as their verifiers. As discussed above, BSS GED
greatly outperforms A? -GED, hence it can be also used as
a standard verifier to accelerate those graph similarity search
query methods.

IX. C ONCLUSIONS AND F UTURE W ORK
In this paper, we present a novel vertex-based mapping
method for the GED computation. First, we reduce the number
of invalid and redundant mappings involved in the GED
computation and then create a small search space. Then, we
utilize beam-stack search to efficiently traverse the search
space to compute GED, achieving a flexible trade-off between
available memory and expensive backtracking. In addition, we
also give two efficient heuristics to prune the search space.
However, it is still very hard to compute GED of large graphs
within a reasonable time. Thus, the approximate algorithm that
fast suboptimally compute GED is left as a future work.
X. ACKNOWLEDGMENTS
The authors would like to thank Kaspar Riesen and Zeina
Abu-Aisheh for providing their source files, and thank Karam
Gouda and Xiang Zhao for providing their executable files.
This work is supported in part by China NSF grants 61173025
and 61373044, and US NSF grant CCF-1017623. Hongwei
Huo is the corresponding author.
R EFERENCES
[1] D. B. Blumenthal and J. J. Gamper. Exact computation of graph edit
distance for uniform and non-uniform metric edit costs. In GbRPR,
pages 211–221, 2017.
[2] D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph
matching in pattern recognition. Int. J. Pattern Recogn., 18(03):265–298,
2004.
[3] K. H. Bunke. Approximate graph edit distance computation by means of
bipartite graph matching. Image Vision Comput., 27(7):950–959, 2009.
[4] K. Gouda and M. Hassaan. CSI GED: An efficient approach for graph
edit similarity computation. In ICDE , pages 256–275, 2016.
[5] K. Riesen, S. Fankhauser, and H. Bunke. Speeding up graph edit distance
computation with a bipartite heuristic. In MLG, pages 21–24, 2007.
[6] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic
determination of minimum cost paths. IEEE Trans.SSC., 4(2):100–107,
1968.
[7] K. Riesen, S. Emmenegger, and H. Bunke. A novel software toolkit for
graph edit distance computation. In GbRPR, pages 142–151, 2013.
[8] R. M. Marı́n, N. F. Aguirre, and E. E. Daza. Graph theoretical similarity
approach to compare molecular electrostatic potentials. J. Chem. Inf.
Model., 48(1):109–118, 2008.
[9] A. Robles-Kelly and R. H. Edwin. Graph edit distance from spectral
seriation. IEEE Trans. Pattern Anal Mach Intell., 27(3):365–378, 2005.

1 0

5

1 0

4

1 0

3

1 0

2

1 0

1

1 0

0

G S im J o in
C S I_ G E D
B S S _ G E D

2

4

6
G E D

8
T h r e s h o ld

1 0

1 2

6

1 0

5

1 0

4

1 0

3

1 0

2

1 0

1

P R O T E IN

1 0

1 0

1 0

S 1 K .E 3 0 .D 3 0 .L 2 0

G S im J o in
C S I_ G E D
B S S _ G E D

1 0

4

1 0

3

1 0

2

1 0

1

G S im J o in
C S I_ G E D
B S S _ G E D

T o ta l r e s p o n s e tim e ( s )

6

T o ta l r e s p o n s e tim e ( s )

T o ta l r e s p o n s e tim e ( s )

A ID S
1 0

0

1 0

0
- 1

2

1 0

4

6
G E D

8
T h r e s h o ld

1 0

1 2

- 1

3

Fig. 9: Performance comparison with CSI GED and GSimJoin.

[10] S. Russell and P. Norvig. Artificial intelligence: a modern approach (2nd
ed.). Prentice-Hall, 2002.
[11] R. Zhou and E. A. Hansen. Beam-stack search: Integrating backtracking
with beam search. In ICAPS , pages 90–98, 2005.
[12] G. Wang, B. Wang, X. Yang, and G. Yu. Efficiently indexing large
sparse graphs for similarity search. IEEE Trans. Knowl Data Eng.,
24(3):440–451, 2012.
[13] D. W. Williams, J. Huan, and W. Wang. Graph database indexing using
structured graph decomposition. In ICDE , pages 976–985, 2007.
[14] X. Chen, H. Huo, J. Huan, and J. S. Vitter. MSQ-Index: A succinct
index for fast graph similarity search. arXiv preprint arXiv:1612.09155,
2016.
[15] X. Yan, P. S. Yu, and J. Han. Graph indexing: a frequent structure-based
approach. In SIGMOD, pages 335–346, 2004.
[16] Z. Abu-Aisheh, R. Raveaux, J. Y. Ramel, and P. Martineau. An exact
graph edit distance algorithm for solving pattern recognition problems.
In ICPRAM , pages 271–278, 2015.
[17] Z. Zeng, A. K. H. Tung, J. Wang, J. Feng, and L. Zhou. Comparing
stars: On approximating graph edit distance. PVLDB, 2(1):25–36, 2009.
[18] X. Zhao, C. Xiao, X. Lin, Q. Liu, and W. Zhang. A partition-based
approach to structure similarity search. PVLDB, 7(3):169–180, 2013.
[19] X. Zhao, C. Xiao, X. Lin, and W. Wang. Efficient graph similarity joins
with edit distance constraints. In ICDE , pages 834–845, 2012.
[20] W. Zheng, L. Zou, X. Lian, D. Wang, and D. Zhao. Efficient graph
similarity search over large graph databases. IEEE Trans. Knowl Data
Eng., 27(4):964–978, 2015.

6

9
G E D

1 2
T h r e s h o ld

1 5

1 8

