Improved lower bounds for graph edit distance
Blumenthal DB, Gamper J (2018)
Publication Type: Journal article
Publication year: 2018
Journal
Book Volume: 30
Pages Range: 503-516
Journal Issue: 3
DOI: 10.1109/TKDE.2017.2772243
Abstract
The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version BRANCH that runs in O(n2Δ3 + n3) time, where Δ is the maximum of the maximum degrees of input graphs G and H. We also develop a speed-up BRANCHFAST that runs in O(n2Δ2 + n3) time and computes an only slightly less accurate lower bound. The lower bounds produced by BRANCH and BRANCHFAST are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm BRANCHTIGHT that iteratively improves BRANCH's lower bound. BRANCHTIGHT runs in O(n3Δ2 + I(n2Δ3 + n3)) time, where the number of iterations I is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks.
Authors with CRIS profile
Involved external institutions
Italy (IT)How to cite
APA:
Blumenthal, D.B., & Gamper, J. (2018). Improved lower bounds for graph edit distance. IEEE Transactions on Knowledge and Data Engineering, 30(3), 503-516. https://dx.doi.org/10.1109/TKDE.2017.2772243
MLA:
Blumenthal, David B., and Johann Gamper. "Improved lower bounds for graph edit distance." IEEE Transactions on Knowledge and Data Engineering 30.3 (2018): 503-516.
BibTeX: Download