Approximate Graph Edit Distance by Several Local Searches in Parallel

Abstract : Solving or approximating the linear sum assignment problem (LSAP) is an important step of several constructive and local search strategies developed to approximate the graph edit distance (GED) of two attributed graphs, or more generally the solution to quadratic assignment problems. Constructive strategies find a first estimation of the GED by solving an LSAP. This estimation is then refined by a local search strategy. While these search strategies depend strongly on the initial assignment, several solutions to the linear problem usually exist. They are not taken into account to get better estimations. All the estimations of the GED based on an LSAP select randomly one solution. This paper explores the insights provided by the use of several solutions to an LSAP, refined in parallel by a local search strategy based on the relaxation of the search space, and conditional gradient descent. Other generators of initial assignments are also considered, approximate solutions to an LSAP and random assignments. Experimental evaluations on several datasets show that the proposed estimation is comparable to more global search strategies in a reduced computational time.
Type de document :
Communication dans un congrès
7th International Conference on Pattern Recognition Applications and Methods, Jan 2018, Funchal, Madeira, Portugal
Liste complète des métadonnées

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

https://hal.archives-ouvertes.fr/hal-01664529
Contributeur : Sébastien Bougleux <>
Soumis le : jeudi 14 décembre 2017 - 23:27:15
Dernière modification le : jeudi 11 janvier 2018 - 06:27:17

Fichier

icpram18-multistart-ged.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01664529, version 1

Citation

Évariste Daller, Sébastien Bougleux, Benoit Gaüzère, Luc Brun. Approximate Graph Edit Distance by Several Local Searches in Parallel. 7th International Conference on Pattern Recognition Applications and Methods, Jan 2018, Funchal, Madeira, Portugal. 〈hal-01664529〉

Partager

Métriques

Consultations de la notice

44

Téléchargements de fichiers

32