Graph similarity is a basic and essential operation
in many applications. In this paper, we are interested
in computing graph similarity based on edit distance. Existing
graph edit distance computation methods adopt the best
first search paradigm A∗. These methods are time and space
bound. In practice, they can compute the edit distance of
graphs containing 12 vertices at most. To enable graph edit
similarity computation on larger and distant graphs, we present
CSI_GED, a novel edge-based mapping method for computing
graph edit distance through common sub-structure isomorphisms
enumeration. CSI_GED utilizes backtracking search combined
with a number of heuristics to reduce memory requirements and
quickly prune away a large portion of the mapping search space.
Experiments show that CSI_GED is highly efficient for computing
the edit distance on small as well as large and distant graphs.
Furthermore, we evaluated CSI_GED as a stand-alone graph
edit similarity search query method. The experiments show that
CSI_GED is effective and scalable, and outperforms the state-ofthe-
art indexing-based methods by over two orders of magnitude. |
