On the exact computation of the graph edit distance

Blumenthal DB, Gamper J (2020)

Publication Type: Journal article

Publication year: 2020


Book Volume: 134

Pages Range: 46-57

DOI: 10.1016/j.patrec.2018.05.002


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

How to cite


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


Blumenthal, David B., and Johann Gamper. "On the exact computation of the graph edit distance." Pattern Recognition Letters 134 (2020): 46-57.

BibTeX: Download