Publication
Title
A novel hierarchical-based framework for upper bound computation of graph edit distance
Author
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. (C) 2018 Elsevier Ltd. All rights reserved.
Language
English
Source (journal)
Pattern recognition. - Oxford
Publication
Oxford : 2018
ISSN
0031-3203
Volume/pages
80(2018), p. 210-224
ISI
000432511200017
Full text (Publisher's DOI)
Full text (publisher's version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 12.06.2018
Last edited 21.07.2021
To cite this reference