Graph similarity is an important notion with many applications. Graph edit distance is one of the most
flexible graph similarity measures available. The main problem with this measure is that in practice it
can only be computed for small graphs due to its exponential time complexity. This paper addresses
the high complexity of graph edit distance computations. Specifically, we present CSI_GED, a novel
edge-centric approach 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 graph edit distance; it outperforms the state-ofthe-
art methods by over three orders of magnitude. It also shows that CSI_GED scales the computation
gracefully to larger and distant graphs on which current methods fail to run. Moreover, 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-of-the-art indexing-based methods by over
two orders of magnitude |
