You are in:Home/Publications/CSI_GED: An Efficient Approach for Graph Edit Similarity Computation. ICDE 2016. pp. 265--276.

Prof. karam gouda :: Publications:

CSI_GED: An Efficient Approach for Graph Edit Similarity Computation. ICDE 2016. pp. 265--276.
Authors: Karam Gouda and Mosab Hassaan
Year: 2016
Keywords: Graph edit distance, Graph data, similarity measures
Journal: ICDE
Volume: Not Available
Issue: Not Available
Pages: 265-276
Publisher: IEEE
Local/International: International
Paper Link: Not Available
Full paper karam gouda_Karam-Gouda_ICDE16.pdf
Supplementary materials Not Available

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.

Google ScholarAcdemia.eduResearch GateLinkedinFacebookTwitterGoogle PlusYoutubeWordpressInstagramMendeleyZoteroEvernoteORCIDScopus