Comparing heuristics for graph edit distance computation - Normandie Université Accéder directement au contenu
Article Dans Une Revue The VLDB Journal Année : 2020

Comparing heuristics for graph edit distance computation

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

Résumé

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.
Fichier principal
Vignette du fichier
AAM_VLDB_J_2019.pdf (686.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02189832 , version 1 (20-07-2019)

Identifiants

Citer

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⟩
82 Consultations
397 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More