You are in:Home/Publications/A novel hierarchical-based framework for upper bound computation of graph edit distance

Dr. Mona Mohamed Arafa Abd Elmonem :: Publications:

Title:
A novel hierarchical-based framework for upper bound computation of graph edit distance
Authors: Karam Gouda, Mona Arafa and Toon Calders
Year: 2018
Keywords: Graph similarity;Graph edit distance; Upper bound
Journal: Pattern Recognition
Volume: 80
Issue: Not Available
Pages: 210-224
Publisher: Elsevier
Local/International: International
Paper Link: Not Available
Full paper Not Available
Supplementary materials Not Available
Abstract:

Graph similarity is an important notion with many applications. Graph edit distance is one of the most flexible graph similarity measure 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. The present paper is concerned with efficient solutions with high quality approximation of graph edit distance. In particular, we present a novel upper bound computation framework for graph edit distance. It is based on breadth-first hierarchical views of the graphs and a novel hierarchical traversing and matching method to build a graph mapping. The main advantage of this framework is that it combines map construction with edit counting in easy and straightforward manner. It also allows to compare the graphs from different hierarchical views to improve the bound. Furthermore, to avoid the complexity of multi-view comparisons and preserve distance accuracy, two new view-selection methods, based on the vertex and edge star structures, are introduced to scale the computations. Contrasting our approach with the state-of-the-art overestimation methods, experiments show that it delivers comparable upper bounds with over three orders of magnitude speedup on real data graphs. Experiments also show that this approach improves the classification accuracy of the KNN classifiers by over 15 percent when compared with the state-of-the-art overestimation methods.

Google ScholarAcdemia.eduResearch GateLinkedinFacebookTwitterGoogle PlusYoutubeWordpressInstagramMendeleyZoteroEvernoteORCIDScopus