A novel hierarchical-based framework for upper bound computation of graph edit distance

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.