Approximate Graph Edit Distance by Several Local Searches in Parallel - Normandie Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Approximate Graph Edit Distance by Several Local Searches in Parallel

Résumé

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

Dates et versions

hal-01664529 , version 1 (14-12-2017)

Identifiants

  • HAL Id : hal-01664529 , version 1

Citer

É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⟩
331 Consultations
401 Téléchargements

Partager

Gmail Facebook X LinkedIn More