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, Automatique 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 metadatas

Cited literature [75 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02189832
Contributor : Luc Brun <>
Submitted on : Saturday, July 20, 2019 - 12:08:56 PM
Last modification on : Thursday, February 13, 2020 - 1:57:05 PM

File

AAM_VLDB_J_2019.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

85

Files downloads

86