Skip to Main content Skip to Navigation
Journal articles

Comparing heuristics for graph edit distance computation

David Blumenthal 1 Nicolas Boria 2 Johann Gamper 1 Sébastien Bougleux 2 Luc Brun 2 
2 Equipe Image - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
Abstract : 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.
Complete list of metadata

Cited literature [75 references]  Display  Hide  Download
Contributor : Luc Brun Connect in order to contact the contributor
Submitted on : Saturday, July 20, 2019 - 12:08:56 PM
Last modification on : Saturday, June 25, 2022 - 9:53:46 AM


Files produced by the author(s)



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



Record views


Files downloads