On the exact computation of the graph edit distance
MetadataShow full item record
The graph edit distance is a widely used distance measure for labelled graph. However, 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 and and the algorithm which only works for uniform edit costs. All newly proposed algorithms outperform the standard approach . 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 and on the one side, and on the other side, can be harmonised. This harmonisation allows us to develop a generalisation of to non-uniform edit cost. Moreover, we present a speed-up of and 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 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.