Approximating GED using a Stochastic Generator and Multistart IPFP

Nicolas Boria 1 Sébastien Bougleux 1 Luc Brun 1
1 Equipe Image - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : The Graph Edit Distance defines the minimal cost of a sequence of elementary operations transforming a graph into another graph. This versatile concept with an intuitive interpretation is a fundamental tool in structural pattern recognition. However, the exact computation of the Graph Edit Distance is N P-complete. Iterative algorithms such as the ones based on Franck-Wolfe method provide a good approximation of true edit distance with low execution times. However, underlying cost function to optimize being neither concave nor convex, the accuracy of such algorithms highly depends on the initialization. In this paper, we propose a smart random initializer using promising parts of previously computed solutions.
Liste complète des métadonnées

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

https://hal-normandie-univ.archives-ouvertes.fr/hal-01865351
Contributeur : Nicolas Boria <>
Soumis le : vendredi 31 août 2018 - 13:26:37
Dernière modification le : mardi 2 avril 2019 - 01:35:55
Document(s) archivé(s) le : samedi 1 décembre 2018 - 14:11:55

Fichier

sspr18approx-ged-stoch-gen(1)....
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01865351, version 1

Citation

Nicolas Boria, Sébastien Bougleux, Luc Brun. Approximating GED using a Stochastic Generator and Multistart IPFP. S+SSPR 2018, Aug 2018, Beijing, China. ⟨hal-01865351⟩

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

58