An In-depth Comparison of Subgraph Isomorphism
Algorithms in Graph Databases∗∗†

Jinsoo Lee

Wook-Shin Han

School of Computer Science and Engineering
Kyungpook National University, Korea

School of Computer Science and Engineering
Kyungpook National University, Korea

jslee@www-db.knu.ac.kr

wshan@knu.ac.kr

Romans Kasperovics∗

Jeong-Hoon Lee

School of Computer Science and Engineering
Kyungpook National University, Korea

School of Computer Science and Engineering
Kyungpook National University, Korea

romans.kasperovics@gmail.com

jhlee@www-db.knu.ac.kr

ABSTRACTquerying biological pathways, and ﬁnding protein complexesin protein interaction networks.
Ullmann [14] proposes the ﬁrst practical algorithm for
subgraph isomorphism search for graphs. It is a backtracking algorithm which ﬁnds solutions by incrementing partial
solutions or abandoning them when it determines they cannot be completed. In recent years, many algorithms suchas VF2 [2], QuickSI [11], GraphQL [5], GADDI [17], andSPath [18] have been proposed to enhance the Ullmann
algorithm. These algorithms exploit diﬀerent join orders,pruning rules, and auxiliary information to prune out falsepositive candidates as early as possible, thereby increasing
performance.
Figure 1 shows the reported comparisons of the state-ofthe-art subgraph isomorphism algorithms. Here, a directededge depicts reported superiority. For example, accordingto [18], SPath is superior to GraphQL. Note that, in [17],GADDI is compared with TALE [13] which ﬁnds only approximate embeddings.

Finding subgraph isomorphisms is an important problem inmany applications which deal with data modeled as graphs.
While this problem is NP-hard, in recent years, many algorithms have been proposed to solve it in a reasonable time forreal datasets using diﬀerent join orders, pruning rules, andauxiliary neighborhood information. However, since they
have not been empirically compared one another in mostresearch work, it is not clear whether the later work outperforms the earlier work. Another problem is that reported
comparisons were often done using the original authors’ binaries which were written in diﬀerent programming environments. In this paper, we address these serious problems
by re-implementing ﬁve state-of-the-art subgraph isomorphism algorithms in a common code base and by comparing
them using many real-world datasets and their query loads.
Through our in-depth analysis of experimental results, wereport surprising empirical ﬁndings.

1.

INTRODUCTION

GraphQL

Many complex objects, such as chemical compounds, social networks, and biological structures are modeled as graphs.
Many real applications in bioinformatics, chemistry, andsoftware engineering require eﬃcient and eﬀective management of graph structured data.
One of most important graph queries in graph databasesis the subgraph isomorphism query. That is, given a query q
and a data graph g, ﬁnd all embeddings of q in g. This problem belongs to NP-hard [10] and has many important applications, such as searching chemical compound databases,∗The ﬁrst three authors contributed equally to this work.
†Corresponding author
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. Articles from this volume were invited to present
their results at The 39th International Conference on Very Large Data Bases,
August 26th - 30th 2013, Riva del Garda, Trento, Italy.
Proceedings of the VLDB Endowment, Vol. 6, No. 2
Copyright 2012 VLDB Endowment 2150-8097/12/12... $ 10.00.

133

[19]

QuickSI[12]
Ullmann

SPath
GADDI

[2]

VF2

Figure 1: Comparisons of state-of-the-art graph isomorphism algorithms.
We observe serious problems in the current practice ofexperiments for these algorithms: 1) It is diﬃcult to compare each algorithm since they have not been described in acommon framework; 2) They have not been compared empirically in most research work. Only four comparisons as
depicted in Figure 1 were reported. Thus, it is not clear
whether the later work outperforms the earlier work; 3)
The reported comparisons were done by comparing the binary executables provided by the original authors, ignoringa number of factors that heavily inﬂuence the performance(e.g., programming languages, implementer’s programmingskills, main memory vs. disk, and buﬀer size, etc.).
In order to address these problems, we re-implement all
representative subgraph isomorphism algorithms in a common framework using C++. For this purpose, we use besteﬀort re-implementations based on the original papers andon email communications with the original authors, since
we were unable to acquire the source code of any techniqueexcept VF2 from its authors. However, since GraphQL
is implemented in Java, we exploit a java bytecode analyzer to fully understand the original implementation. We
also perform extensive experiments using many real datasetsand their query workload and provide an in-depth analysis. We note that a similar experience has been reported
in iGraph [3], which compares only graph indexing techniques rather than the subgraph isomorphism algorithms
themselves.
Our contributions can be summarized as follows.
• We clearly explain the diﬀerences of existing algorithms
using a common framework in Section 3.
• We re-implement ﬁve state-of-the-art algorithms (VF2,
QuickSI, GraphQL, GADDI, and SPath) in the common code base.
• We fairly and empirically compare these algorithms
using many real and synthetic datasets in Section 4.
• We analyze experiments in depth in order to understand why one algorithm outperforms another for speciﬁc query and data graphs in Section 4• We report surprising ﬁndings through our analysis: 1)
QuickSI designed for handling small graphs often outperforms the more recent algorithms GraphQL, GADDI,
and SPath which are designed for handling large graphs.
2) QuickSI, VF2, and GADDI fail to ﬁnd embeddingsin trees in a reasonable time, showing exponential behavior. 3) GraphQL is the only method to process
all query sets tested but shows slower performance
than QuickSI in many query sets and datasets. 4)
It should be noted that in this paper, unlike in [18],SPath is almost consistently slower than GraphQL.
This is mainly because a) they are implemented in
diﬀerent programming languages, and b) the cost ofreading signatures from disk is not taken into account.
Note that SPath is implemented in C++, while GraphQL
is implemented in Java. This strongly indicates that,unless both methods are implemented in a common
framework, empirical comparisons would be useless.
5) We ﬁnd that all existing algorithms have problems
in their join order selections for some datasets, although GraphQL processes all queries we test in reasonable times. The blind computation of signaturesof GraphQL regardless of queries and data sets incurs signiﬁcant performance overhead compared with
QuickSI. This calls for new subgraph algorithms combining the strengths of both algorithms.
The remainder of this paper is organized as follows. Section 2 reviews the background information as well as existing work on subgraph isomorphism. Section 3 presents thedetails of our implementations. Section 4 presents the results of performance evaluation. Section 5 summarizes andconcludes our paper.

2. BACKGROUND
2.1 Problem Definition
All datasets and query sets used in [2, 5, 11, 17, 18] aremodeled as undirected labeled graphs. An undirected labeledgraph g is deﬁned as a triple (V, E, L) where V is the set ofvertices, E (⊆ V ×V ) is the set of undirected edges, and L isa labeling function which maps a vertex or an edge to a set

134

of labels or a label, respectively. Without loss of generality,
all subgraph isomorphism algorithms can be easily extended
to handle graphs whose edges have a set of labels. Unlessotherwise speciﬁed, we use symbols q, g, u, and v to denotea query graph, a data graph, a query vertex, and a datavertex, respectively.
Given a query graph q = (V, E, L), a data graph g =(V  , E  , L ), a subgraph isomorphism (or an embedding) is
an injective function M : V → V  such that (1) ∀u ∈ V ,L(u) ⊆ L (M (u)), and (2) ∀(ui , uj ) ∈ E, (M (ui ), M (uj )) ∈E  , and L(ui , uj ) = L (M (ui ), M (uj )).
Problem Definition 1. [5, 14, 18]Given a query graph q
and a data graph g, the subgraph isomorphism problem is tofind all distinct embeddings of q in g.
Figure 2 shows an example of query q and data graphg. We have two embeddings M1 and M2 for this subgraphisomorphism query.

a
B
u2

A
u1
a

b

A
v1

b
A
u4

C
u3

a

b
A
v4

B,C
v7

(a) query graph
q.

B
v2
a

a

b

a

A
v3

B,D a
v5
b

b
A
v6

B
C
v8
v9
(b) data graph g.
b

M1 = {(u1 , v3 ), (u2 , v5 ), (u3 , v9 ), (u4 , v6 )}M2 = {(u1 , v6 ), (u2 , v5 ), (u3 , v9 ), (u4 , v3 )}(c) resulting subgraph isomorphisms.
Figure 2: Example of query and data graphs.
In practice, we may stop the subgraph isomorphism search
after the ﬁrst k embeddings are found. In [5, 18], k is set to1000.

2.2 Basic Concepts
We explain the concept of the induced subgraph, the partial subgraph isomorphism, the adjacency set, and the kneighborhood.
A graph q  is an induced subgraph of a graph q iﬀ V(q  ) ⊆V(q), and E(q  ) contains only the edges present in q, i.e.,E(q  ) = E(q) ∩ (V(q  ) × V(q  )). Note that an induced subgraph q  of q can be deﬁned solely with its vertex set V(q  ).
For example, the induced graph of the vertices v3 , v5 , v6 , v9
is marked with bold lines in Figure 2.
Let g  be an induced subgraph of g, and let M  be a
subgraph isomorphism from g  to g. We call M  a partial
solution when searching all subgraph isomorphisms from g 
to g if V(g  ) ⊂ V(g) (as opposed to a complete solution suchthat V(g  ) = V(g)).
The adjacency set of a vertex v of a graph g, denoted asadj(v), is a set of vertices directly connected (adjacent) tov. The k-neighborhood of a vertex v of a graph g, denotedas Nk (v), is a set of vertices of g where for each vertex v  in
Nk (v), the shortest distance between v  and v is less than orequal to k. That is, Nk (v) includes v itself.
Consider the vertex v4 in the data graph g from Figure 2(b). The adjacency set adj(v4 ) is {v1 , v2 , v5 , v8 }. The 1neighborhood N1 (v4 ) is {v1 , v2 , v4 , v5 , v8 }. The 2-neighborhood
N2 (v4 ) contains all vertices in the data graph g.

2.3 Related Workalgorithm calls NextQueryVertex to select a query vertexu ∈ V(q) which is not yet matched (Line 4). After that, it
calls RefineCandidates to obtain a reﬁned candidate vertex set CR from C(u) by using algorithm-speciﬁc pruning
rules (Line 5). Next, for each candidate data vertex v ∈ CR
such that v is not matched yet, the IsJoinable subroutine
checks whether the edges between u and already matchedquery vertices of q have corresponding edges between v andalready matched data vertices of g (Line 7). If v is qualiﬁed,
it is matched to u, and SubgraphSearch updates status
information by calling UpdateState (Line 9), and the algorithm proceeds to match the remaining query vertices ofq by recursively calling SubgraphSearch (Line 10). Next,
all changes done by UpdateState are restored by calling
RestoreState (Line 11). The algorithm terminates when
all possible embeddings are found.

We can classify existing algorithms into two categories
depending on whether or not they use exact search: (1) exact
subgraph matching and (2) approximate subgraph matching.
Each matching has its own important target applications.
Exact subgraph matching algorithms can also be classiﬁed into two subcategories depending on the usage of graphindexing techniques. The ﬁrst subcategory includes GraphGrep [12], gIndex [16], FG-Index [1], Tree+Δ [19], gCode[20], SwiftIndex [11], and C-Tree [4]. These indexing algorithms are based on a two-step ﬁlter-and-reﬁne strategy
where the ﬁltering step uses graph indexes to minimize thenumber of candidate graphs, and the reﬁnement step checks
if there exists one subgraph isomorphism for each candidate. The second subcategory includes Ullmann [14], VF2[2], QuickSI [11], GraphQL [5], GADDI [17], and SPath[18]. These algorithms ﬁnd all embeddings for a given querygraph and a data graph. We will detail each algorithm inthe following section. We note that Ullmann, VF2, andQuickSI have been originally designed for handling small
graphs while GraphQL, GADDI, and SPath have been originally designed for handling large graphs.
Approximate subgraph matching algorithms ﬁnd approximate embeddings with their own similarity measures. Representative algorithms in this area include TALE [13], SIGMA[9], and Ness [6].

3.

Algorithm 1 GenericQueryProc
Input: query graph q
Input: data graph g
Output: all subgraph isomorphisms of q in g
1: M := ∅;2: for each u ∈ V(q) do
3:
C(u) := FilterCandidates (q, g, u, . . .);[[ ∀v ∈ C(u)((v ∈ V(g)) ∧ (L(u) ⊆ L(v))) ]]4:
if C(u) = ∅ then5:
return;6:
end if
7: end for
8: SubgraphSearch (q, g, M, . . .);Subroutine SubgraphSearch (q, g, M, . . .)1: if |M | = |V (q)| then2:report M ;3: else4:u := NextQueryVertex (. . .);[[ u ∈ V(q) ∧ ∀(u , v) ∈ M (u = u) ]]5:
CR := RefineCandidates (M, u, C(u), . . .);[[ CR ⊆ C(u) ]]6:
for each v ∈ CR such that v is not yet matched do
7:
if IsJoinable (q, g, M, u, v, . . .) then8:[[ ∀(u , v ) ∈ M ((u, u ) ∈ E(q) =⇒(v, v ) ∈ E(g) ∧ L(u, u ) = L(v, v )) ]]9:
UpdateState (M, u, v, . . .);[[ (u, v) ∈ M ]]10:
SubgraphSearch (q, g, M, . . .);11:
RestoreState (M, u, v, . . .);[[ (u, v) ∈/ M ]]
12:
end if13:
end for
14: end if

IMPLEMENTATIONIn this section, we describe how we implement the ﬁvestate-of-the-art algorithms in a common framework. For
this purpose, we introduce a generic subgraph isomorphism
algorithm so that each algorithm can be implemented byextending this generic algorithm according to its speciﬁcs.

3.1 Generic Subgraph Isomorphism Algorithm
The generic subgraph isomorphism algorithm is implemented as a backtracking algorithm [7] which ﬁnds solutions
by incrementing partial solutions or abandoning them when
it determines they cannot be completed.
Algorithm 1 shows a generic subgraph isomorphism algorithm, GenericQueryProc. Its inputs are a query graphq and a data graph g, and its output is a set of subgraphisomorphisms (or embeddings) of q in g. Here, to represent
an embedding, we use a list M of pairs of a query vertex
and a corresponding data vertex.
For each vertex u in q, GenericQueryProc ﬁrst invokes
FilterCandidates to ﬁnd a set of candidate vertices C(u)(⊆ V(g)) such that L(u) ⊆ L(v) (Line 3). Note that weplace logical expressions in double square brackets to show
the necessary post-conditions for each subroutine. If C(u)is empty, we can safely exit, making early termination possible (Line 5). After that, GenericQueryProc invokes arecursive subroutine, SubgraphSearch, to ﬁnd mapping
pairs of a query vertex and matching data vertices at a time(Line 8). Note that SubgraphSearch of SPath matches
one query path at a time for each recursive call.

The SPath algorithm grows partial solutions with one
path at a time rather than a vertex at a time. Thus, although our generic recursive algorithm accommodates thecharacteristics of SPath, we will explain SPath separately in
Section 3.7 for ease of understanding.

Common Graph Storage
Depending on the size of a data graph, we store the graphas a tuple in a heap ﬁle or a large object in a BLOB ﬁle asin iGraph. We also use a B+-tree to eﬃciently ﬁnd a datagraph using a graph ID.
For each subgraph isomorphism algorithm, we tune thedisk representation of a data graph in order to support fast
retrieval and construction of its main memory data structures. In subsequent subsections, we describe data structures for each method.

SubgraphSearch Subroutine
SubgraphSearch takes as parameters a query graph q, adata graph g, and a partial embedding M and reports allembeddings of q in g.
The recursion stops when the algorithm ﬁnds the complete
solution (i.e., when |M | = |V (q)|) (Line 1). Otherwise, the135

3.2 Ullmann Algorithm

generic algorithm is called 14 times (Figure 3(b)). However,
if we match query vertices in order (u1 , u4 , u2 , u3 ), SubgraphSearch is called 12 times (see Figure 3(a)). Notethat in both cases, at least eight recursive calls are necessary to output two complete solutions.

FilterCandidates: FilterCandidates returns a set ofdata graph vertices with a matching label u.
NextQueryVertex: NextQueryVertex returns one vertex at a time from the vertices in the order they appear in
the input. It is clear that the performance of the Ullmann
algorithm highly depends on the input order of the query
vertices. We will describe this issue in detail when we describe the NextQueryVertex function of VF2.
RefineCandidates: RefineCandidates prunes out all candidate vertices v ∈ C(u) that have a smaller degree than u.
IsJoinable: IsJoinable iterates through all adjacent query
vertices of u. If the adjacent query vertex u is alreadymatched, i.e., (u , v  ) ∈ M , then it checks whether there isa corresponding edge (v, v  ) in the data graph. Note that,since IsJoinable is called in a most inner loop, we must
carefully design this function. If there is no edge betweenu and already matched query vertices, we can optimize thisprocess by skipping this checking process. Such optimization will be explained in IsJoinable of QuickSI.
UpdateState, RestoreState: UpdateState appends apair (u, v) to M while RestoreState restores M by removing the pair (u, v) from M .
In the following algorithms, we describe only the subroutines which are diﬀerent from those in Ullmann.

u1 :v1 v3 v4 v6

u2 :
u3 :

v5
v9

X

v1 v3

v4

v6

X
u2 :

v5 v2 v5 v8 v5

v5

u3 :

v9

v9

u4 :

v6

u4 : v 4 v 6 v 1 v 3
X

u1 :

O
O
(a) matching order (u1 , u4 , u3 ,
u4 ).

X

v9
X

X

v9
v3

O
O
(b) matching order (u1 ,
u2 , u3 , u4 ).

Figure 3: Recursion trees using the generic subgraph isomorphism algorithm for the query and datagraphs in Figure 2.
The original VF2 version used in iGraph uses a reordering technique which sorts query vertices by the frequency ofthe query vertex label and then feeds these reordered query
vertices as input to VF2. This technique could be eﬀective
when the reordered vertex sequence is similar to the one ordered by the frequency of the data vertex label. We also
optimize the original VF2 version in several ways: 1) On
comparing labels of two vertices, we directly compare thelabel IDs (i.e., integer comparison) of those vertices insteadof calling expensive virtual function calls. 2) By exploiting
the inverse vertex label list, we accelerate the search performance of ﬁnding vertices having a given vertex label. 3)
When returning from each recursive call, Cq and Cg must be
restored. By maintaining additional stacks, this process canalso be accelerated eﬃciently. By putting these optimizations including the reordering technique all together, ourVF2 version outperforms the original by up to 29.86 times.

3.3 VF2 Algorithm
NextQueryVertex: Unlike Ullmann, VF2 starts with theﬁrst vertex and selects a vertex connected from the alreadymatched query vertices. Note that the original VF2 algorithm does not deﬁne any order in which query vertices are
selected.
RefineCandidates: VF2 uses the following three pruning
rules to prune out data vertex candidates: (1) Prune out
any vertex v in C(u) such that v is not connected fromalready matched data vertices; (2) Let Mq and Mg be a setof matched query vertices and a set of matched data vertices,
respectively. Let Cq and Cg be a set of adjacent and notyet-matched query vertices connected from Mq and a set ofadjacent and not-yet-matched data vertices connected from
Mg , respectively. Let adj(u) be a set of adjacent vertices toa vertex u. Then, prune out any vertex v in C(u) such that|Cq ∩ adj(u)| > |Cg ∩ adj(v)|; (3) prune out any vertex v inC(u) such that |adj(u) \ Cq \ Mq | > |adj(v) \ Cg \ Mg |.
For example, consider again the query graph q and thedata graph g from Figure 2. Suppose that the current partial solution M = {(u1 , v4 )} and that u2 is the next vertex returned by NextQueryVertex with C(u2 ) = {v2 , v5 ,v7 , v8 }. Then, Mq = {u1 }, Mg = {v4 }, Cq = {u2 , u4 },Cg = {v1 , v2 , v5 , v8 }. The RefineCandidates subroutine
prunes out v7 using the pruning rule (1), because v7 is
not connected to any vertex in Mg . The subroutine also
prunes out v8 from C(u2 ) using the pruning rule (2), sinceadj(u2 ) ∩ Cq = {u4 } and adj(v8 ) ∩ Cg = {}. The subroutine
prunes out v2 from C(u2 ) using the pruning rule (3) sinceadj(u2 ) \ Cq \ Mq = {u3 } and adj(v2 ) \ Cg \ Mg = {}.

Disk Representation
VF2 represents a graph using three structures: 1) vertex label list that allows access to the ordered vertex label list ofa vertex by a given ID (see Figure 4(a)); 2) inverse vertex
label list that allows access to the ordered vertex ID list by
a given vertex label (see Figure 4(b)); and 3) adjacency lists(see Figure 4(c)) of each vertex which store adjacency information, i.e., a list of pairs (vertex ID, edge label) ordered by
the vertex ID. Note that we materialize the inverse vertex
label list in the graph database for speedup, although it canbe constructed from the vertex label list.

3.4 QuickSI Algorithm
NextQueryVertex: QuickSI tries to access vertices having infrequent vertex labels and infrequent, adjacent edge
labels as early as possible. Speciﬁcally, instead of using label frequency information from a query graph as in VF2,
QuickSI pre-processes data graphs to compute the frequencies of vertex labels and the frequencies of a triple (source
vertex label, edge label, target vertex label). By using thecomputed edge label frequencies, we assign a weight to eachquery edge and obtain a minimum spanning tree using a
modiﬁed Prim algorithm. QuickSI creates a sequence byusing the order in which the vertices are inserted into the

Improvements
We note that the matching order driven by NextQueryVertex signiﬁcantly impacts the query performance by reducing
the size of the recursive call tree. For instance, consider thequery and data graphs from Figure 2. If we match query
vertices in order (u1 , u2 , u3 , u4 ), SubgraphSearch of the136

|V(g)|

oﬀsets

3.5 GADDI Algorithm

vertex labels

9 1 2 3 4 6 7 9 10 11 A B A A B D Av 1 v 2 v3 v4 v 5 v6 v7 v 8 v 9 v 1 v 2 v 3 v 4 v 5 v 6(a) vertex label list.
labelsC
v9

Before explaining each subroutine speciﬁc to GADDI, we
ﬁrst need to understand the concept of the neighboring discriminating substructure (NDS) distance.
The NDS distance between v1 and v2 using a subgraph
P , denoted as ΔNDS (v1 , v2 , P ), is deﬁned as the number of
embeddings of P in an induced subgraph of Nk (v1 )∩Nk (v2 ).
Noth that k is a given parameter of GADDI.
Figure 5 displays the data graph g from Figure 2 with
the induced subgraph of N2 (v1 ) ∩ N2 (v4 ) drawn with thicker
lines. For the substructures P1 , P2 , and P3 shown in thesame ﬁgure, the NDS distances are calculated as follows:
ΔNDS (v1 , v4 , P1 ) = 3; ΔNDS (v1 , v4 , P2 ) = 8; and ΔNDS (v1 , v4 ,P3 ) = 24.

oﬀsets

A
B
C D
v
v
v
v
v
v
v
v
v
v9 v5
1
3
4
6
2
5
7
8
7
4 A B C D 4 8 10 11
A B C D(b) inverse vertex label list.
|V(g)||V(g)|

v1

oﬀsets

9 1 3 5 9v 1 v 2 v3 v4v2

20 (v4 ,b)(v4 ,a)(v5 ,b)v9oﬀsetsv4(v1 ,b)(v2 ,a)(v5 ,a)(v8 ,a)(c) adjacency lists.
v1

A
v1

9 1 3 5 7 9 9 10 10 10 (v4 ,1,3,8,24)(v4 ,1,6,40,144)v 1 v 2 v3 v4 v 5 v6 v 7 v 8 v 9(d) NDS distances for pairs of vertices within the shortest
distance one.
v1
v2
v3
v9
oﬀsets|V(g)|
9 1 4 7 12 17 20 21 24 26 A A B D A B Dv 1 v 2 v3 v 4 v 5 v 6 v 7 v 8 v 9(e) GraphQL neighborhood signatures.
v1
oﬀsets|V(g)|

B,C
v7

v4 ,B

(v4 ,b) (v4 ,a) (v5 ,b) (v5 ,b)(v1 ,b) (v2 ,a) (v5 ,a) (v8 ,a) (v5 ,a)

b

B
v2

b

a

A
v3

a

B,D a
v5
b

B
v8

C
v9

a

P1

b
A
v6

P2

P3

ΔNDS (v1 , v4 , P1 ) = 3, ΔNDS (v1 , v4 , P2 ) = 8,
ΔNDS (v1 , v4 , P3 ) = 24
Figure 5: The NDS distances between v1 and v4
when k = 2.

9 3 9 15 21 26 32 34 40 44 (1,A,1)(2,B,3)(2,D,1)v 1 v2 v3 v4 v 5 v6 v7 v8 v 9(f) SPath neighborhood signatures when k0 =2.
v4 ,A

b
A
v4

B D

v1 ,A v2 ,A v2 ,B v2 ,DaNow, we explain how GADDI selects substructures forcalculating NDS distances. For this purpose, GADDI samples 100 pairs of vertices from the data graph, and for eachpair (v1
, v2 ), we construct an induced unlabeled graph1 of
Nk (v1 ) Nk (v2 ). For those induced graphs, [17] suggests
selecting top ten frequent subgraphs using a frequent subgraph mining algorithm such as gSpan [15]. We construct amatrix L where each row corresponds to an induced graph g,and each column corresponds to a subgraph selected P , andeach entry in L corresponds to the number of embeddings of
P in g. We select the three columns (i.e., subgraphs) thathave the largest numbers of distinct values as substructures.
NextQueryVertex: GADDI ﬁrst selects a query vertex
appearing ﬁrst in the input and then performs a depth-ﬁrst
search to ﬁnd next query vertices.
RefineCandidates: RefineCandidates of the GADDI
algorithm prunes out v in C(u), if, for each query vertexu ∈ Nk (u), there is no data vertex v  ∈ Nk (v) satisfying
the following three conditions: 1) L(u ) ⊆ L(v  ); 2) for
each Pi in a given set of substructures, ΔNDS (u , u, Pi ) ≤ΔNDS (v  , v, Pi ); and 3) the shortest distance between u andu is greater than or equal to the shortest distance betweenv  and v.
UpdateState, RestoreState: GADDI uses an additional
pruning technique that reduces the candidate sets of allquery vertices. For each data vertex v  in Nk (v), if there
does not exist a query vertex u in Nk (u) satisfying thethree conditions used in RefineCandidates, we can prunev  from all the current candidate sets except C(u). Therefore, UpdateState identiﬁes those prunable data vertices
and additionally removes them from all C(ui )s except C(u)(1 ≤ i ≤ |V(q)|), and RestoreState additionally restoresthe removed vertices.

v4 ,D(g) SPath adjacency lists.
Figure 4: Disk representation of the data graph from
Figure 2.
minimum spanning tree. When the algorithm selects a starting edge (u1 , u2 ), the algorithm uses u1 as the ﬁrst vertex
in the sequence if the vertex label frequency of u1 is lower
than that of u2 . Otherwise, u2 is used as the ﬁrst vertex.
For detailed explanation, we refer readers to [11].
RefineCandidates: For the ﬁrst query vertex u, QuickSI
does not reﬁne u. For the subsequent vertices u returned
by NextQueryVertex, let upar be the parent vertex of u
in the minimum spanning tree and v  be the matching datavertex of upar . Then, QuickSI prunes out v in C(u), if there
is no edge between v and v  .
IsJoinable: Unlike IsJoinable of Ullmann which blindly
iterates through all adjacent query vertices of u, IsJoinableof QuickSI iterates through adjacent and already matchedquery vertices of u.
Although this important property is not elaborated in[11], our empirical analysis shows that this mechanism contributes to speedups of QuickSI, making the invocation costof the SubgraphSearch of QuickSI the lowest among all
ﬁve algorithms.

Disk Representation
QuickSI stores a graph in the same format as the VF2 algorithm. In addition, QuickSI uses two B+-trees, one B+-tree
for storing all distinct vertex labels along with their frequencies and the other for storing all distinct triples (source
vertex label, edge label, target vertex label) along with theirfrequencies.

1
We have communicated with one of the original authors tolearn how to construct such induced graphs.

137

Improvements

Disk Representation

We use the reordering technique which is used in the improved VF2 version to reduce the size of the recursive calltree of SubgraphSearch.
According to [17], subgraphs selected for computing NDS
distances are connected, unlabeled graphs having three orfour edges. Thus, there are only eight diﬀerent connected
graphs having three or four edges. By exploiting this important fact, we can safely skip the expensive frequent subgraphmining.

GraphQL stores a graph using an inverse vertex label list
(see Figure 4(b)), an adjacency list(Figure 4(c)), and a GraphQL
neighborhood signature (Figure 4(e)). GraphQL does not
use the vertex label list, since it can construct candidate
vertex lists during the neighborhood signature based pruning. Note that GraphQL materializes GraphQL neighborhood signatures of all vertices for a data graph, which ismore eﬃcient than constructing such signatures on the ﬂyduring query processing. Figure 4(e) illustrates the disk representation of GraphQL signatures of the data graph from
Figure 2.

Disk Representation
GADDI stores a graph in the same representation as it does
for the VF2 algorithm. In addition, for each pair of data
vertices of a graph, we store the precomputed NDS and theshortest distances along with the graph. Speciﬁcally, foreach pair (vi , vj ) of vertices (i < j) within a given shortest
distance, we store an entry storing the shortest distance andthree NDS distances. These entries are ordered by the IDs of
the ﬁrst and the second vertices, and we use binary search tolocate the distances between the given pair of vertices. Figure 4(d) shows a fragment of the disk representation of thedata graph g in Figure 2 storing the precomputed shortest
distance and three NDS distances for the pairs of vertices
within the distance of one. In this fragment, v1 has just one
vertex v4 within distance one from v1 , and the corresponding
entry stores the NDS distances from Figure 5.

3.7 SPath Algorithm

3.6 GraphQL Algorithm
FilterCandidates: The GraphQL algorithm uses two additional pruning rules to reduce the size of the candidate
sets: 1) neighborhood signature based pruning and 2) the
pseudo subgraph isomorphism test based pruning.
We ﬁrst explain the concept of the GraphQL neighborhood
signature of a vertex v, denoted as sigGraphQL (v). sigGraphQL (v)is a multiset of labels of adj(v). For example, sigGraphQL (u2 )in Figure 2 is {A, A, C}, and sigGraphQL (v2 ) is {A, B, D}.
The neighborhood signature based pruning prunes out acandidate vertex v if sigGraphQL (u)  sigGraphQL (v). For
example, assume that u is u2 (Line 3 of Algorithm 1). Then,v2 is pruned since sigGraphQL (u2 )  sigGraphQL (v2 ).
Now, we explain the concept of the pseudo isomorphism
test, which is an iterative algorithm using the depth d as aparameter. At ﬁrst iteration, we obtain two breadth ﬁrst
search trees Tu and Tv for u and v respectively, where theirdepth is 1(i.e., d = 1). Then, we can prune out v if Tu is notcontained in Tv . We can iterate this process by increasing
d by one until d = r, where r is called the refinement level.
For detailed explanation, we refer readers to [5].
NextQueryVertex: The GraphQL algorithm ﬁnds next
query vertices by using a greedy strategy similar to theheuristic-based join order optimization based on the cardinality of intermediate joined results. NextQueryVertexof GraphQL ﬁrst selects a query vertex u which has thesmallest candidate set size |C(u)|. In the subsequent calls,
NextQueryVertex returns a query vertex u that is connected already matched query vertices and that makes thesmallest size of intermediate results.

Improvements
For graphs having labeled edges, we extend GraphQL neighborhood signature of v with labels of the adjacent edges to
v to improve pruning power. For instance, sigGraphQL (v2 )from Figure 2 becomes {(a,A), (b,B), (b,D)}.

138

The SPath algorithm also uses the GenericQueryProc,
though it invokes a diﬀerent SubgraphSearch in order tomatch a query path rather than a query vertex per recursive
call. Thus, it may minimize the depth of the recursion treeby matching a path per call [18]. However, as we will see
in our experiments, the selection order of paths signiﬁcantly
impacts the query performance, and the selection order ofSPath is far from optimal for most data sets.
FilterCandidates: Similar to the GraphQL algorithm,
SPath uses neighborhood signatures to minimize candidatesets. However, it attempts to exploit more neighborhood
information. The SPath neighborhood signature of a given
vertex u, denoted as sigSPath (u), is a set of triples where each
triple (d, l, c) is constructed from the vertices in Nk0 (u). The
triple (d, l, c) represents the fact that there are c vertices in
Nk0 (u) containing the label l such that the shortest distancefrom u is d. Here, k0 is called the neighborhood scope. For
instance, if k0 = 1, the signature of vertex v7 in Figure 2
is sigSPath (v7 ) = {(1, B, 1)}. If k0 = 2, the signature of thesame vertex v7 is sigSPath (v7 ) = {(1, B, 1), (2, A, 1)}.
Now, we explain how to use the SPath neighborhood signature. We ﬁrst deﬁne a function Sdl (v) to represent thecontainment relationship between two SPath neighborhood
signatures. If there exists a triple (d, l, c) in sig SPath (v),Sdl (v) = c. Otherwise, Sdl (v) = 0. Next, we deﬁne a rule forpruning data vertices using the SPath neighborhood signature. For the given signatures sigSPath (u) and sigSPath (v) of
query vertex u and data vertex v, we can prune out the datavertex v in C(u), if it does not satisfy the following condition: for all k ≤ k0 and all possible labels l in sigSPath (u),
k
k
l
l
i=1 Si (u) ≤i=1 Si (v). For example, assume that u is
u3 (Line 3 of Algorithm 1) and that k0 = 2. Here, the sig1), (2, A, 2)). We can prune v7 , sincenatureof u3 is ((1, B,22AA
i=1 Si (u3 )(= 2) >i=1 Si (v7 )(= 1).
Unlike [18] suggesting a large neighborhood scope (k0 =4), we observe that, if we increase the neighborhood scopeof SPath, the performance can decrease. This phenomenon
is explained as follows. A larger neighborhood scope increases ﬁltering power, but also increases the size of SPathneighborhood signature and the ﬁltering time. The optimalneighborhood scope, which is diﬃcult to choose, lies in abalance between ﬁltering power and ﬁltering time.
The following subroutine shows SubgraphSearch of SPath.
Note that the neighborhood scope k0 is used as an additionalparameter in order to limit the radius of the SPath neighborhood signature of a vertex.
The subroutine stops this recursion when the algorithm
ﬁnds the complete solution (i.e., when |M | = |V (q)|) (Line1). Otherwise, the subroutine calls NextQueryPath to se-lect a next query path pq whose length is shorter than orequal to k0 , and whose vertices except the ﬁrst vertex are
not yet matched. (Line 4). After that, it calls GetCandidatePaths to obtain all data paths matching the query
path pq in the data graph g (Line 5). Next, for each candidate data path pg ∈ P , the IsJoinable subroutine checks
whether the edges between the vertices in the pq and already matched query vertices of q have corresponding edges
between the vertices in the pg and already matched data
vertices of g (Line 7). Note that the ﬁrst vertex of pq isalready matched, so all the resulting candidate data paths
should start from the matched data vertex. If pg is qualiﬁed, it is matched to pq , and SubgraphSearch updates thepartial solution M by calling UpdateState (Line 8), andthe algorithm proceeds to match the remaining query pathsof q by recursively calling SubgraphSearch (Line 9).

SPA). We use best-eﬀort reimplementations based on theoriginal papers and on email communications with the original authors. As for GraphQL, we re-implement and optimize it in C++ by analyzing the original implementation
using a java bytecode analyzer.
Datasets: We use four real datasets referred to here as
AIDS, NASA, Yeast, and Human. The AIDS dataset wasused in [11]. The Yeast dataset was used in [5, 18]. The
NASA dataset was produced from a popular XML dataset[8] used in the XML research ﬁeld. Since the Human dataset
used in [17] could not be obtained from the original authors,
we re-created it using the same process described in [17],which is straightforward. We also experimented with thesynthetic datasets used in [5, 17]. However, there were no
signiﬁcant diﬀerences in overall performance trends of thealgorithms, and thus, we omit them to save space.
Note that these datasets have diﬀerent characteristics.
The AIDS dataset contains a set of sparse graphs where theaverage graph size is small (= 27.4 in terms of the number ofedges), and the number of unique labels is small (=51). The
NASA dataset contains a set of trees where the average tree
size is 32.2, and the number of unique labels is much larger(=117,302) than AIDS. The Yeast dataset contains only one
large graph having 3112 vertices and 12519 edges. A vertex corresponds to a protein, and an edge corresponds to aninteraction between two proteins. Since one protein can appear in several cellular components and biological processes,a vertex can have multiple labels. This graph is denser thangraphs in AIDS and NASA. The Human dataset contains alarge graph modeling a protein interaction network of 4675
proteins and 86282 interactions, which is larger and denser
than Yeast. This graph has a fewer number of labels and alarger average degree than Yeast. Table 1 summarizes theproperties of the four datasets.

Subroutine SubgraphSearch (q, g, M, k0 )1: if |M | = |V (q)| then2:report M ;3: else4:
pq := NextQueryPath (q, g, k0 );5:
P := GetCandidatePaths (pq , M, C);6:
for each pg ∈ P do
7:
if IsJoinable (pq , pg , M ) then8:
UpdateState (pq , pg , M );9:SubgraphSearch (q, g, M, k0 );10:
RestoreState (pq , pg , M );11:
end if
12:
end for
13: end if

Now, we explain the subroutine NextQueryPath further, which is most important in query performance of SPath.
NextQueryPath: The SPath algorithm ﬁrst selects a query
vertex u which has the smallest candidate set size |C(u)|. In
the subsequent call, SPath returns the most selective path
which starts from an already matched query vertex. Here,the selectivity function sel(p) for a given path p is calculated|V(p)|as  2 |C(u)| , where V(p) denotes all vertices in a path

Table 1: Summary of the real-world datasets.
Dataset# of graphs# of vertices# of edges
Avg. degreeMax. degree# of distinct v. labels# of distinct e. labels
Avg. # of labels pervertexu∈V(p)

p. Note that the denominator represents the join cardinalityof the candidate sets for all query vertices in p. However,this overestimate leads to signiﬁcant errors in estimating thejoin cardinality. Thus, in many query and datasets, SPathis bound to choose a suboptimal join order.

Disk Representation

Like the GraphQL algorithm, SPath stores only the inverse
vertex label list for accessing vertices by label and does notstore the vertex label list, which is constructed in memory
from the inverse vertex label listduring the SPath neighborhood signature based pruning. Each SPath neighborhood
signature for the data vertex vi is stored as a list of triples(d, l, c) ordered by d and l (Fig. 4(f)). As a distinction fromall other methods, SPath adjacency lists are grouped by labels of target vertices. For example, in Fig. 4(g), the adjacency list of the vertex v4 is split into three sublists: 1)
the adjacent vertices with label A ((v1 , b)), 2) the adjacentvertices with label B ((v2 , a), (v5 , a), (v8 , a)), and 3) the adjacent vertices with label D ((v5 , a)).

4.

AIDS
10000
2∼214
1∼217
1.95
11
51
4
1

NASA
36790
2∼889
1∼888
1
245
117302
0
1

Yeast
1
3112
12519
8.05
168
184
0
7.55

Human
1
4675
86282
36.82
771
90
0
4.63

Query sets: For AIDS, we use the existing query sets which
are currently downloadable together with the iGraph framework2 . There are six query sets. Each query set contains
1000 query graphs of the same size in terms of the numberof edges. The query sizes are 4, 8, 12, 16, 20, and 24 edges.
To generate queries of size 24, we randomly select connected
subgraphs of size 24 from data graphs. We then generate theother query sets so that the following containment relationship is satisﬁed. That is, a small size query graph q of sizes is constructed from a large size query graph q  of size s +4 by removing edges until q  is still connected and containss edges. For the other datasets, we generate query sets byusing this query generation process. In addition, we use two
types of query sets for Yeast and Human which were usedin [5]. These query sets were generated with a tool provided

EXPERIMENTS

In this section, we evaluate the performance of the ﬁve
representative subgraph isomorphism algorithms VF2 [2],QuickSI [11] (in short, QSI), GraphQL [5] (in short, GQL),GADDI [17] (in short, GAD), and SPath [18] (in short,2139

http://www.igraph.or.kr/

by the GraphQL authors and do not satisfy the containment
relationship.
Suppose that a large query graph q is a supergraph ofa small graph q  . Then, the number of embeddings for q is
typically smaller than or equal to the number of embeddingsfor q  . Thus, the performance of a good subgraph isomorphism algorithm would decrease as we increase the querysize. In contrast, the search space for a graph q exponentially increases as we increase the query size. If a query q hasn vertices, u1 , u2 , · · · , un , then the size of its search spacebecomes |C(u1 )|×|C(u2 )|×· · · ×|C(un )|. Thus, the performance of a good subgraph isomorphism algorithm is likely
to decrease as we increase the query size by exploiting powerful pruning rules and optimal join orders.
Setup: For all experiments, we use a PC with Intel Xeon
Quad Core 2.27GHz , 8 GB of main memory, and 1 TB
7200 RPM hard disk, running Windows Vista. We implement all algorithms in the iGraph framework using C++ andcompile them using Microsoft Visual-C++ compiler. We
run all algorithms with best possible parameter values foreach dataset. We stop subgraph isomorphism search after
the ﬁrst 1000 subgraph isomorphisms are found, as it wasdone in [5, 18]. The size of the database buﬀer is set to 500
MB, which allows the once read data from the database to
be kept in main memory.
We use the number of I/Os and the elapsed time as theperformance metrics for database construction. We use theaverage elapsed time and the average number of SubgraphSearch calls (# of recursive calls) as the performance metrics for query execution. Speciﬁcally, if there is more than
one data graph in a database, the elapsed time for a querymeans the accumulated elapsed time for processing all datagraphs for that query. Thus, we average the total elapsed
times for all queries to calculate the average elapsed time.
Note that each algorithm has the signiﬁcantly diﬀerent costof a SubgraphSearch call.
We divide our experimental section into four parts foreach dataset and give more details on each dataset in thecorresponding subsections.

which are pre-computed and stored together with graphs, although they do not use the vertex label list as explained in
Section 3.6. Since the AIDS dataset has a small average degree, the database of GraphQL is only 1.36 times larger thanthat of VF2. However, the database of SPath is 2.31 times
larger than that of VF2 due to a larger signature size thanGraphQL. GADDI stores pre-computed NDS and shortest
distances between data vertices. The size of these distances
is comparable to that of SPath signature.
Table 2: Database size and construction time for
AIDS dataset.
Alg.
VF2
QuickSI
GraphQL
SPath(k0 = 2)
GADDI

Size(MB)
9.25
9.28
12.59
21.40
21.47

# of total I/Os
1774
1780
2202
3330
3339

Time(msec.)
418
671
684
1420
9064

4.1.2 Query Processing
Figure 6 shows the subgraph isomorphism search performance using the AIDS dataset. SPath was run with the best
signature neighborhood scope k0 = 2, which is contradictory to [18] suggesting a large neighborhood scope (k0 = 4).
However, in this experiment, GraphQL was run with thebest reﬁnement level r = 1. The GADDI was run with theshortest distance d = 1 and the neighborhood scope k0 = 2.
200

QSI
VF2
GQL(r=1)
SPA(k=2)
GAD

120
100
80

Avg. # of rec. calls (x 1000)

Avg. elapsed time (msec.)

140

60
40
20
0

4

8
12
16
20
Subgraph size(# of edges)

24

QSI
VF2
GQL(r=1)
SPA(k=2)
GAD

150
100
50
0

4

8
12
16
20
Subgraph size(# of edges)

24(a) average elapsed time.
(b) avg. # of recursive calls.
Figure 6: AIDS dataset.
The average number of recursive calls for every algorithm
decreases as we increase the query size. Thus, all algorithms
behave well despite their inherent exponential time complexity by choosing good join orders and by exploiting eﬀective
pruning rules. In terms of the average number of recursive
calls, the ranking order is GraphQL, SPath, GADDI, VF2,and QuickSI. GraphQL and SPath exploit signature-basedpruning before calling SubgraphSearch, and thus, the sizeof the candidates (i.e., the search space) is the smallest. Notethat the number of recursive calls for GraphQL is 6.7 and6.4 smaller than those for QuickSI and VF2, respectively.
However, in terms of the average elapsed time, the ranking order is completely diﬀerent. QuickSI is the fastest algorithm. VF2, GraphQL, GADDI and, SPath are 1.73, 1.99,
2.88, and 6.62 times slower than QuickSI on average, respectively. We analyze this surprising phenomenon in depth asfollows: Although the average number of recursive calls for
VF2 is 1.05 times smaller than QuickSI, the average costof recursive calls for VF2 is 2.82 times larger than thatof QuickSI. This is due to QuickSI’s optimized design of
IsJoinable as we pointed out in Section 3.4. In GraphQL,the ﬁltering time spent for GraphQL neighborhood signature based ﬁltering and pseudo-isomorphism based pruning
constitutes 63.16% of the total elapsed time while the ﬁltering time for QuickSI is zero. Note that the ﬁltering is executed before starting to call SubgraphSearch. In addition,

4.1 AIDS Dataset
4.1.1 Database Construction
Table 2 shows the database sizes and database building
times for all ﬁve algorithms using the AIDS dataset. Notethat the number of read I/Os for all algorithms is 588. SPathwas run with the best neighborhood scope k0 = 2. The
GADDI algorithm was run with the shortest distance d = 1
and the neighborhood scope k0 = 2. Setting d = 1 andk0 = 2 produced the best performance results as in [17].
The VF2 database has the smallest disk space, and its
building time is the fastest, since the VF2 algorithm does notuse any auxiliary information. QuickSI has the same disk
representation as VF2 along with two additional B+-trees
to store the frequencies of 51 unique vertex labels and 240
unique edge features. However, the space of the frequency
information of QuickSI for the AIDS dataset is negligible.
Thus, the database sizes of both algorithms are almost thesame. However, in QuickSI, for each data graph, we ﬁrst
count unique vertex labels and unique edge features andupdate the frequencies in the corresponding B+-trees, resulting in 33582 + 60214 updates to both B+-trees. Thus,
the building time for QuickSI is 1.61 times slower than VF2.
GraphQL and SPath use additional neighborhood signatures

140

4

8
12
16
20
Subgraph size (# of edges)

24

SPA(k=4)
GAD

1000

100

4

8
12
16
20
Subgraph size (# of edges)

24

we ﬁrst changed the join orders of QuickSI with those ofGraphQL for some slow queries, and this modiﬁed versionof QuickSI completed these queries in a reasonable time.
We note that QuickSI uses statistics for label frequencies
for all data graphs in the database while GraphQL andSPath use statistics for label frequencies for each data graph.
Thus, GraphQL and SPath can generate a better join orderthan QuickSI for these queries. However, for the other slow
queries, especially, those having star-shaped subgraphs withmany same labeled vertices, although QuickSI uses the joinorders of GraphQL, it still shows exponential behavior. Notethat QuickSI compares one query vertex with one data vertex at a time, and thus, it tries to explore all combinationsof query vertices and data vertices of the same label for suchstar-shaped subgraphs. However, GraphQL and SPath caneﬃciently prune such subgraphs if query vertex signatures
are not contained in the corresponding data vertex signatures. Thus, both GraphQL and SPath eﬃciently process
such star-shaped queries, signiﬁcantly reducing the numberof candidates. This indicates that we need to combine goodjoin order strategies with signature-based pruning for theNASA query/data sets.
It should be noted that, at the query sizes 20, unlike
GraphQL, SPath shows jumps both in the number of recursive calls and the elapsed time. This is due to serious problem in its join order selection. However, at the query size 24,
we observe that signature-basedpruning signiﬁcantly prune
candidate sets. For example,
for the 61stu∈V (q) |C(u)|query of size 24 is 71.01 times smaller than u∈V (q) |C(u)|for the 61st query of size 20. Thus, in spite of the inherent
problem in join order selection of SPath, the elapsed timeof SPath signiﬁcantly is reduced for the query size 24 by
exploiting the signature-based pruning of SPath.
The average number of recursive calls for GraphQL increases as we increase the query size up to 16. This is due
to search space increments. However, when we increase thequery size further, the average number of recursive calls decreases. This phenomenon is explained as follows. As we
increase the size of a query, the search space also increases.
However, when a larger query has vertexes having infrequentlabels, the signature-based pruning of GraphQL signiﬁcantly
prunes candidates, thereby signiﬁcantly reduce the average
number of recursive calls.
In terms of the average elapsed time, the performance ofGraphQL is 10.38 times faster than SPath on average since1) the loading time including in-memory signature construction time for GraphQL is 5.55 times faster than that for
SPath, 2) the ﬁltering time for GraphQL is 2.45 times fasterthan that for SPath since SPath uses k0 = 4, and 3) the total cost of recursive calls for GraphQL is 14.33 times smaller
than that for SPath. Note that setting r to two in GraphQL
ﬁlters the number of candidates very eﬀectively. In order toTable 3 shows the database size and database building
times for all ﬁve algorithms using the NASA dataset. Notethat the number of read I/Os for all algorithms is 3,077.
The size of the database for QuickSI is 1.34 times large thanthat of VF2, since the sizes of the two B+-trees storing thefrequency information become large due to the large numberof unique labels (= 117,302). The size of the database for
SPath is 5.85 times larger than VF2 since the value of neighborhood scope k0 is set to four instead of two. Note that setting k0 to four shows the best query performance for NASA.
The increasing rate of GADDI over VF2 in NASA in termsof the database size and the elapsed time is smaller thanthat in AIDS since the average degree of NASA is smaller
than that of AIDS. The GADDI was run with the shortest
distance d = 1 and the neighborhood scope k0 = 2.
Table 3: Database size and construction time forNASA dataset.
# of total I/Os
8718
10634
10461
36089
15288

100

QSI
VF2
GQL(r=2)

10000(a) average elapsed time.
(b) avg. # of recursive calls.
Figure 7: NASA dataset.

4.2.1 Database Construction

Size(MB)
44.04
58.99
57.65
257.6895.33

SPA(k=4)
GAD

1000

10

4.2 NASA Dataset

Alg.
VF2
QuickSI
GraphQL
SPath(k0 =4)
GADDI

QSI
VF2
GQL(r=2)

10000

Avg. # of rec. calls (x 1000)

Avg. elapsed time (msec.)

the average cost of recursive calls for GraphQL is 1.94 times
larger than VF2. This is because 1) the query optimization
time of GraphQL constitutes 10.6% of SubgraphSearch
since the sizes of query graphs are relatively large comparedwith the sizes of data graphs, and 2) GraphQL does not use
any pruning rule for RefineCandidates.
In SPath, the ﬁltering time spent for SPath neighborhood signature based ﬁltering constitutes 61.23% of the total elapsed time. The average cost of recursive calls for
SPath is 5.18 times larger than that of GraphQL due tothe overhead in path-based matching. Furthermore, thelarger size of SPath neighborhood signature, compared to
the GraphQL neighborhood signature leads to slower reading times for accessing data graphs. In GADDI, for eachquery, calculating NDS distances for every pair of verticesof the query graph is very expensive. The average cost ofrecursive calls for GADDI is 3.76 times larger than that ofGraphQL since the data graphs are sparse, and thus the
NDS distances are often equal to zero, which does not help
to reﬁne candidates. Note that, unlike GraphQL and SPath,
there is no additional ﬁltering step for GADDI.

Time(msec.)
1697
3769
1950
21737
32167

4.2.2 Query Processing
Figure 7 shows the subgraph isomorphism search performance using the NASA dataset. SPath was run with thebest signature neighborhood scope k0 = 4, and GraphQL
was run with the best reﬁnement level r = 2. The GADDI
was run with the shortest distance d = 1 and the neighborhood scope k0 = 2.
The purpose of this experiment is to see if those ﬁve algorithms exploit this important characteristics of the dataset.
VF2,QuickSI, and GADDI show exponential behaviors at
the sizes of query sets 8, 12, and 8, respectively. Only
GraphQL and SPath complete their query execution in areasonable time. This striking phenomenon is due to the serious problems both in their join order selection and in theabsence of signature-based pruning. To verify our claim,141

compensate for the lack of the additional ﬁltering step using
pseudo-subgraph isomorphism of the GraphQL algorithm,
we have to use a larger neighborhood
scope (k0 =4) for theSPath algorithm. Thus,u∈V (q) |C(u)| of SPath is 1.21
times smaller than that of GraphQL. However, due to theoverhead of computing a larger SPath neighborhood signature, the ﬁltering time of SPath is 2.45 times larger thanthat of GraphQL.

Table 4: Database size and construction time for
Yeast dataset.
Alg.
VF2
QuickSI
GraphQL
SPath(k0 =1)
GADDI

4.3 Yeast Dataset

Size(MB)
0.41
1.07
2.03
3.73
0.91

# of total I/Os
89
175
296
514
152

Time(msec.)
46
378
284
437
25272

Figure 8(a) and Figure 9(a) show the subgraph isomorphism search performance using subgraph queries for Yeast
dataset. SPath was run with k0 = 1, and GraphQL was run
with r = 4. Note that if we increase k0 further, the query
performance decreases due to the increased ﬁltering cost.
The GADDI was run with d = 1 and k0 = 2. Only QuickSI,
GraphQL, and SPath complete their query execution in areasonable time. VF2 and GADDI show exponential behavior at query sizes nine and eight, respectively. This is due tothe combined factors of increased search space and ineﬃcientjoin ordering strategies of both algorithms. The average
number of recursive calls increases with the size of queries.
Note that such a trend is diﬀerent from the results of theexperiments on AIDS and NASA datasets. In terms of average elapsed time, QuickSI is the fastest algorithm until query
size eight. However, on average, QuickSI, SPath, GADDI,
and VF2 are 2.20, 3.78, 5.89, and 369.50 times slower thanGraphQL, respectively. Although QuickSI is designed forhandling small graphs, it often outperforms the more recent algorithms GraphQL and SPath which are designed
for handling large graphs. This indicates that signaturebased pruning might not be very eﬀective for the Yeast
dataset.
To analyze this phenomenon, we calculate the sizeof u∈V (q) |C(u)| for QuickSI, GraphQL, and SPath. Thesize of u∈V (q) |C(u)| for QuickSI is only 2.01 and 2.78 times
larger than those for SPath and GraphQL on average, respectively. However, increased ﬁltering and loading timesof SPath and GraphQL negate the advantage of signaturebased pruning.

In this experiment, we use three types of query sets: subgraph, clique, and path. The query sets of the ﬁrst typeare generated as is done for AIDS. The other types of querysets are provided by the original authors of GraphQL. The
query sets of the second type contain clique queries (complete graphs) that correspond to protein complexes. The
queries of the last type correspond to biological pathways.
The vertices of the last two types are randomly assignedwith the top 40 most frequent vertex labels, and each querygraph vertex has only one label. Note that, unlike subgraphqueries, path and clique queries do not satisfy the containment relationship since they are randomly generated.

4.3.1 Database Construction
Table 4 shows the database sizes and database building
times for all ﬁve algorithms using the Yeast dataset. The
SPath database is built with the best neighborhood scopek0 = 1. That is, a larger neighborhood scope (i.e., k0 > 1)
decreases the query performance of SPath due to the overhead of larger SPath neighborhood signatures, which is contrary to [18] suggesting a larger neighborhood scope for better query performance. The GADDI was run with the shortest distance d = 1 and the neighborhood scope k0 = 2.
Note that the number of read I/Os for all algorithms is
33. The size of the database for QuickSI is 2.58 times large
than that of VF2, because of the large size of the B+-treestoring the frequencies. In the Yeast dataset, each vertex
has 7.55 labels on average. Therefore the number of all
distinct triples (source vertex label, edge label, target vertex label) which we need to store in a B+-tree can increase
quadratically3 . The size of the database for SPath is 9.02
times larger than that of VF2 since the number of triples(d, l, c) in the SPath neighborhood signature and the number of adjacency lists in the SPath adjacency list increase
with the average number of vertex labels. The increasingrate of GADDI over VF2 in terms of the average elapsed
time is much larger than that for the AIDS dataset since
the number and the cost of NDS distance calculations increase due to the larger degree of Yeast. Note that the costof calculating an NDS distance depends on the size of theneighborhood. The increasing rate of GraphQL over VF2 inYeast in terms of the database size and elapsed time is larger
than that of AIDS because of the larger average degree andmultiple labels for each vertex.

4.3.3 Clique Queries
Figure 8(b) and Figure 9(b) show the subgraph isomorphism search performance using clique queries for the Yeast
dataset. We use the same parameter values as used in subgraph queries except for setting r = 1.
The average number of recursive calls for every algorithm
increases as we increase the query size until three or four,then it decreases, if we increase the query size further. This
trend is similar to that for NASA. Thus, all algorithms behave well despite their inherent exponential time complexity by choosing good join orders and by exploiting eﬀective
pruning rules. In terms of the average number of recursive
calls, the ranking order is GraphQL, QuickSI, GADDI, VF2,and SPath.
In terms of the average elapsed time, the ranking orderis QuickSI, GraphQL, VF2, SPath, and GADDI. This isdue to the lower cost of a recursive call of QuickSI and
VF2. Note that, although the numbers of recursive callsof GraphQL and SPath decrease as we increase the size ofqueries from ﬁve to seven, the elapsed times of GraphQL
and SPath slightly increase. This is due to increasing overhead of ﬁltering in GraphQL and SPath. As for GADDI,
since the data graphs are dense, the comparison costs basedon the NDS distance and the shortest path exponentially in-

4.3.2 Subgraph Queries
The purpose of this experiment is to analyze the trends
in query performance for Yeast using the same query generation technique as for AIDS and NASA datasets. We used
ten subgraph query sets with sizes ranging from one to ten.
These query sets have the same containment property as for
AIDS and NASA.

3i.e., =O (the average number of vertex labels)2

142

1000

100
10
1
0.1

QSI
VF2
GQL(r=1)
SPA(k=1)
GAD

100

Avg. elapsed time (msec.)

QSI
VF2
GQL(r=4)
SPA(k=1)
GAD

Avg. elapsed time (msec.)

Avg. elapsed time (msec.)

1000

10
1
0.1

1

2

3
4
5
6
7
8
Subgraph size (# of edges)

910(a) subgraph queries.

2

3
4
5
6
Subgraph size (# of vertices)

10

1

0.1

7

QSI
VF2
GQL(r=1)
SPA(k=1)
GAD

100

2

3

(b) clique queries (Y-axis in log
scale).

4
5
6
7
8
9
Subgraph size (# of vertices)10(c) path queries.

Figure 8: Average elapsed time for Yeast PIN dataset.
4500

QSI
VF2
GQL(r=1)
SPA(k=1)
GAD

Avg. # of rec. calls

Avg. # of rec. calls

4000
10000
1000
100
10

QSI
VF2
GQL(r=4)

1

2

SPA(k=1)
GAD

3 4 5 6 7 8 9Subgraph size (# of edges)(a) subgraph queries.
0

3500
3000
2500

Avg. # of rec. calls

100000

2000
1500
1000
500

10

0

2

3
4
5
6
Subgraph size (# of vertices)7(b) clique queries.

1000

QSI
VF2
GQL(r=1)
SPA(k=1)
GAD

100

2

3

4
5
6
7
8
9
Subgraph size (# of vertices)10(c) path queries.

Figure 9: Average number of recursive calls for Yeast PIN dataset.

crease as the size of a query increases. Thus, GADDI shows
the worst performance in terms of the average elapsed time.

4.3.4 Path Queries
Figure 8(c) and Figure 9(c) display the subgraph isomorphism search performance using path queries for the Yeast
dataset. We use the same parameter values as used in subgraph queries except for setting r = 1.
The performance results of all the algorithms increase as
the query size increases. In terms of the average elapsed
time, the ranking order is QuickSI, GraphQL, SPath, GADDI,
and VF2. This is because 1) QuickSI generates reasonably
good join orders for path queries, and 2) the cost of a recursive call for QuickSI is the lowest. In terms of the average
elapsed time, QuickSI is 2.53, 3.22, 56.96, and 65.12 times
faster than GraphQL, SPath, GADDI, and VF2 on average.
The VF2 and GADDI algorithms show exponential behaviors at query size ten because of the serious problems in theirjoin order selection.

4.4 Human Dataset
4.4.1 Database Construction
Table 5 shows the database sizes and database building
times for all ﬁve algorithms. Note that the number of read
I/Os for all algorithms is 148. SPath was run with k0 = 3 forsubgraph queries. Otherwise, it was run with k0 = 1. The
GADDI was run with d = 1 and k0 = 2. The ratio of the sizeof a QuickSI database over a VF2 database is 1.11, whichis smaller than the ratio for the Yeast dataset. This is dueto the smaller number of distinct vertex labels. Since thisdataset has a larger average degree than Yeast, the databasesizes of GraphQL and SPath are 5.27 and 13.58 times larger
than that of VF2. Due to a larger degree than Yeast, the costof calculating NDS distances sharply increases, and thus, theratio of the building time of GADDI over VF2 accordingly
increases compared with that for Yeast.

dataset. SPath was run with k0 = 3, and GraphQL was run
with r = 4. The GADDI was run with d = 1 and k0 = 2.
Table 5: Database size and construction time for
Human dataset.
Alg.
VF2
QuickSI
GraphQL
SPath(k0 =1)
SPath(k0 =3)
GADDI

Size(MB)
1.55
1.72
8.13
11.28
17.09
4.88

# of total I/Os
349
373
1193
1596
2340
775

Time(msec.)
93
964
774
1669
3323
624265In terms of the average elapsed time and the average number of recursive calls, the performance of all algorithms increases as the query size increases. Although QuickSI shows
the best performance in terms of the average elapsed time
until the query size four, all algorithms except GraphQL fail
to complete the subgraph queries due to their exponential
behaviors at query sizes ﬁve, seven, eight, and eight for VF2,GADDI, QuickSI, and SPath, respectively. This is due to 1)
the increasingly large search space size with increasing query
sizes and 2) the join order selection problem. Note that thisdataset has a higher density and fewer unique vertex labels
than those of Yeast.

4.4.3 Clique and Path Queries
Figures 10(b) and 11(b) show the performance results forthe clique queries. Figures 10(c) and 11(c) show the performance results for the path queries. We also use the same
parameter values except for setting r = 1 and k = 1 forclique queries and setting r = 4 and k = 1 for path queries.
The performance trend of both types of queries for the
Human dataset is similar to that of path queries for the
Yeast dataset. The only notable diﬀerence is that, in pathqueries, the performance of QuickSI at query size ten is better than that at query size nine. This is because QuickSI
fortunately selects better join orders at query size ten.

4.4.2 Subgraph queries

5. CONCLUSION

Figures 10(a) and 11(a) show the results of subgraph isomorphism search test using subgraph queries for the Human

In this paper, we provide a fair comparison of subgraphisomorphism algorithms by using a common framework. We

143

104

103 GQL(r=4)
102

SPA(k=3)
GAD

101
10
10

0

-1

1

2

3

4
5
6
7
8
Subgraph size (|E(q)|)

9

102
101
10
10

10

104

QSI
VF2
GQL(r=1)
SPA(k=1)
GAD

103

Avg. elapsed time (msec.)

QSI
VF2

Avg. elapsed time (msec.)

Avg. elapsed time (msec.)

104

0

-1

2

3
4
5
6
Subgraph size(# of vertices)

102
101
100
10-1

7

QSI
VF2
GQL(r=4)
SPA(k=1)
GAD

103

2

3

4
5
6
7
8
Subgraph size (# of vertices)

9

10

9

10

(a) subgraph queries.
(b) clique queries.
(c) path queries.
Figure 10: Average elapsed time for the Human dataset.
106

6

10

4

10

3

102
10

1

0

1

2

3

4
5
6
7
8
Subgraph size (|E(q)|)

9

10

10

104
10

107

QSI
VF2
GQL(r=1)
SPA(k=1)
GAD

5

3

102
10
0

1

2

3
4
5
6
Subgraph size(# of vertices)

5

10

4

10

3

10

2

7

2

3

4
5
6
7
8
Subgraph size (# of vertices)0(a) subgraph queries.
(b) clique queries.
(c) path queries.
Figure 11: Average number of recursive calls for the Human dataset.
[2] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A(sub)graph isomorphism algorithm for matching large graphs.
IEEE PAMI, 26(10):1367–1372, 2004.
[3] W.-S. Han, J. Lee, M.-D. Pham, and J. X. Yu. iGraph: A
framework for comparisons of disk-based graph indexing
techniques. PVLDB, 3(1):449–459, 2010.
[4] H. He and A. K. Singh. Closure-tree: An index structure forgraph queries. In ICDE, pages 38–49, 2006.
[5] H. He and A. K. Singh. Graphs-at-a-time: query language andaccess methods for graph databases. In SIGMOD, pages
405–418, 2008.
[6] A. Khan, N. Li, X. Yan, Z. Guan, S. Chakraborty, and S. Tao.
Neighborhood based fast graph search in large networks. In
SIGMOD, pages 901–912, 2011.
[7] D. E. Knuth. Estimating the eﬃciency of backtrack programs.
Technical report, Stanford, CA, USA, 1974.
[8] G. Miklau. Xml data repository.
http://www.cs.washington.edu/research/xmldatasets.
[9] M. Mongiovi, R. D. Natale, R. Giugno, A. Pulvirenti, A. Ferro,
and R. Sharan. Sigma: a set-cover-based inexact graphmatching algorithm. J. Bioinformatics and Computational
Biology, 8(2):199–218, 2010.
[10] R. Shamir and D. Tsur. Faster subtree isomorphism. Theory ofComputing Systems, Israel Symposium on the, 0:126, 1997.
[11] H. Shang, Y. Zhang, X. Lin, and J. X. Yu. Taming veriﬁcation
hardness: an eﬃcient algorithm for testing subgraphisomorphism. PVLDB, 1(1):364–375, 2008.
[12] D. Shasha, J. T. L. Wang, and R. Giugno. Algorithmics andapplications of tree and graph searching. In PODS, pages
39–52, 2002.
[13] Y. Tian and J. M. Patel. TALE: A tool for approximate large
graph matching. In ICDE, pages 963–972, 2008.
[14] J. R. Ullmann. An algorithm for subgraph isomorphism. J.
ACM, 23:31–42, January 1976.
[15] X. Yan and J. Han. gspan: Graph-based substructure patternmining. In ICDM, pages 721–724, 2002.
[16] X. Yan, P. S. Yu, and J. Han. Graph indexing: A frequent
structure-based approach. In SIGMOD, pages 335–346, 2004.
[17] S. Zhang, S. Li, and J. Yang. GADDI: distance index based
subgraph matching in biological networks. In EDBT, pages
192–203, 2009.
[18] P. Zhao and J. Han. On graph query optimization in large
networks. PVLDB, 3(1):340–351, 2010.
[19] P. Zhao, J. X. Yu, and P. S. Yu. Graph indexing: Tree + delta>= graph. In VLDB, pages 938–949, 2007.
[20] L. Zou, L. Chen, J. X. Yu, and Y. Lu. A novel spectral coding
in a large graph database. In EDBT, pages 181–192, 2008.

ACKNOWLEDGEMENTS

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (No. 2012033242) and the Engineering Research Center of Excellence Program of Korea Ministry of Education,
Science and Technology(MEST)/ National Research Foundation of Korea(NRF) (Grant 2012-0000474).

7.

10

101

performed extensive experiments with small and large real
datasets and analyzed performance in depth.
Although there is no single winner for all experiments,
to our surprise, QuickSI, the algorithm designed for handling small graphs, performs the best for many queries forboth small and large data graphs (the AIDS and YEAST
datasets) since the cost of its recursive call is the lowest.
QuickSI, VF2, and GADDI failed to ﬁnd embeddings intrees (the NASA set) in a reasonable time, showing exponential behavior due to serious problems in their join orderselection. GADDI shows very bad performance for many
queries tested due to expensive NDS distance calculationand lowest pruning power. GraphQL is the only algorithm
that completed all queries tested, although it is slower than
QuickSI for most queries. SPath almost performed worse
than GraphQL due to its large SPath neighborhood signature overhead and the serious problem in its join order selection. We also note that all existing algorithms had problems
in their join order selections, and signature-based pruning isonly eﬀective for some datasets. This calls for new subgraphalgorithms which exploit both good join order selection andselective signature-based pruning.
We believe that our community will beneﬁt greatly from
our implementations and new ﬁndings. The source code of
all algorithms that we implemented will be released alongwith publication of this paper.

6.

QSI
VF2
GQL(r=4)
SPA(k=1)
GAD

106
Avg. # of rec. calls

QSI
VF2
GQL(r=4)
5 SPA(k=3)
10
GAD

10

Avg. # of rec. calls

Avg. # of rec. calls

107

REFERENCES[1] J. Cheng, Y. Ke, W. Ng, and A. Lu. Fg-index: towards
veriﬁcation-free query processing on graph databases. In
SIGMOD, pages 857–872, 2007.

144