Database Reference
In-Depth Information
Figure 6. Graph closure
CTree defines graph similarity based on edit distance, and computes it using heuristic graph mapping
methods. It conceptually approximates subgraph isomorphism by sub-isomorphism using adjacent
subgraphs then it approximates sub-isomorphism by using adjacent subtrees.
SAGA
Tian et al. (2007) have presented an approach of approximate graph query matching named
SAGA
(sub-
structure index-based approximate graph alignment). SAGA measures graph similarity by a distance
value such that graphs that are more similar have a smaller distance. The distance model contains three
components:
1. The
StructDist
component measures the structural differences for the matching node pairs in the
two graphs.
2. The
NodeMismatches
component is the penalty associated with matching two nodes with different
labels.
3. The
NodeGaps
component is used to measure the penalty for the gap nodes in the query graph.
SAGA index is built on small substructures of graphs in the database (
Fragment Index
). Each fragment
is a set of
k
nodes from the graphs in the database where
K
is a user-defined parameter. The index does
not enumerate all possible
k
-node sets. It uses another user-defined parameter
dist
max
to avoid indexing
any pair of nodes in a fragment if its distance measure is greater than
dist
max
. The fragments in SAGA
do not always correspond to connected subgraphs. The reason behind this is to allow node gaps in the
matching process. To efficiently evaluate the subgraph distance between a query graph and a database
graph, an additional index called
DistanceIndex
is also maintained. This index is used to look up the
pre-computed distance between any pair of nodes in a graph. The graph matching process goes through
the following three steps:
1. The query is broken into small fragments and the Fragment Index is probed to find database frag-
ments that are similar to the query fragments.
2. The hits from the index probes are combined to produce larger candidate matches. A hit-compatible
graph is built for each matching graph. Each node in the hit-compatible graph corresponds to a pair of
matching query and database fragments. An edge is drawn between two nodes in the hit-compatible
