On the exact computation of the graph edit distance
Blumenthal DB, Gamper J (2020)
Publication Type: Journal article
Publication year: 2020
Journal
Book Volume: 134
Pages Range: 46-57
DOI: 10.1016/j.patrec.2018.05.002
Abstract
The graph edit distance is a widely used distance measure for labelled graph. However, A★−GED, the standard approach for its exact computation, suffers from huge runtime and memory requirements. Recently, three better performing algorithms have been proposed: The general algorithms DF−GED and BIP−GED, and the algorithm CSI−GED, which only works for uniform edit costs. All newly proposed algorithms outperform the standard approach A★−GED. However, cross-comparisons are lacking. This paper consolidates and extends these recent advances. To this purpose, we present all existing algorithms in a unified way and show that the slightly different definitions of the graph edit distance underlying A★−GED and DF−GED, on the one side, and CSI−GED, on the other side, can be harmonised. This harmonisation allows us to develop a generalisation of CSI−GED to non-uniform edit cost. Moreover, we present a speed-up of A★−GED and DF−GED for uniform edit costs, which build upon the fact that, in the uniform case, a continuously used subroutine can be implemented to run in linear rather than cubic time. We also suggest an algorithm MIP−GED which builds upon a very compact new mixed integer linear programming formulation. Finally, we carry out a thorough empirical evaluation, which, for the first time, compares all existing exact algorithms.
Authors with CRIS profile
Involved external institutions
Italy (IT)How to cite
APA:
Blumenthal, D.B., & Gamper, J. (2020). On the exact computation of the graph edit distance. Pattern Recognition Letters, 134, 46-57. https://doi.org/10.1016/j.patrec.2018.05.002
MLA:
Blumenthal, David B., and Johann Gamper. "On the exact computation of the graph edit distance." Pattern Recognition Letters 134 (2020): 46-57.
BibTeX: Download