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.
Liste complète des métadonnées

Littérature citée [75 références]  Voir  Masquer  Télécharger

https://hal-normandie-univ.archives-ouvertes.fr/hal-02189832
Contributeur : Luc Brun <>
Soumis le : samedi 20 juillet 2019 - 12:08:56
Dernière modification le : mardi 23 juillet 2019 - 01:27:08

Fichier

 Accès restreint
Fichier visible le : 2020-01-15

Connectez-vous pour demander l'accès au fichier

Identifiants

Citation

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

Partager

Métriques

Consultations de la notice

20