Comparing heuristics for graph edit distance computation

Comparaison d'heuristiques pour le calcul de la distance d'édition entre graphes.

David Blumenthal (1) , Nicolas Boria (2) , Johann Gamper (1) , Sébastien Bougleux (2) , Luc Brun (2)

1 Free University of Bozen-Bolzano
2 Equipe Image - Laboratoire GREYC - UMR6072

Because of its flexibility, intuitiveness, and ex-pressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP-hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error-correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper , we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.

Keywords: Empirical evaluation; Similarity search; Graph databases; Graph edit distance

Domains: Computer Science [cs]; Computer Vision and Pattern Recognition [cs.CV]; Computer Science [cs]; Data Structures and Algorithms [cs.DS]

David Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, Luc Brun. Comparing heuristics for graph edit distance computation. The VLDB Journal, 2020, 29 (1), pp.419-458. ⟨10.1007/s00778-019-00544-1⟩. ⟨hal-02189832⟩