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.