Exact computation of graph edit distance for uniform and non-uniform metric edit costs
Blumenthal DB, Gamper J (2017)
Publication Type: Conference contribution
Publication year: 2017
Journal
Publisher: Springer Verlag
Book Volume: 10310 LNCS
Pages Range: 211-221
Conference Proceedings Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Event location: Anacapri, ITA
ISBN: 9783319589602
DOI: 10.1007/978-3-319-58961-9_19
Abstract
The graph edit distance is a well-established and widely used distance measure for labelled, undirected graphs. However, since its exact computation is NP-hard, research has mainly focused on devising approximative heuristics and only few exact algorithms have been proposed. The standard approach A_-GED, a node-based best-first search that works for both uniform and non-uniform metric edit costs, suffers from huge runtime and memory requirements. Recently, two better performing algorithms have been proposed: DF-GED, a node-based depth-first search that works for uniform and non-uniform metric edit costs, and CSI GED, an edge-based depth-first search that works only for uniform edit costs. Our paper contains two contributions: First, we propose a speed-up DF-GEDu of DF-GED for uniform edit costs. Second, we develop a generalisation CSI GEDnu of CSI GED that also covers non-uniform metric edit cost. We empirically evaluate the proposed algorithms. The experiments show, i.a., that our speed-up DF-GEDu clearly outperforms DF-GED and that our generalisation CSI GEDnu is the most versatile algorithm.
Authors with CRIS profile
Involved external institutions
Italy (IT)How to cite
APA:
Blumenthal, D.B., & Gamper, J. (2017). Exact computation of graph edit distance for uniform and non-uniform metric edit costs. In Pasquale Foggia, Mario Vento, Cheng-Lin Liu (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 211-221). Anacapri, ITA: Springer Verlag.
MLA:
Blumenthal, David B., and Johann Gamper. "Exact computation of graph edit distance for uniform and non-uniform metric edit costs." Proceedings of the 11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017, Anacapri, ITA Ed. Pasquale Foggia, Mario Vento, Cheng-Lin Liu, Springer Verlag, 2017. 211-221.
BibTeX: Download