A parallel graph edit distance algorithm

Abstract : Graph edit distance (GED) has emerged as a powerful and flexible graph matching paradigm that can be used to address different tasks in pattern recognition, machine learning, and data mining. GED is an error-tolerant graph matching problem which consists in minimizing the cost of the sequence that transforms a graph into another by means of edit operations. Edit operations are deletion, insertion and substitution of vertices and edges. Each vertex/edge operation has its associated cost defined in the vertex/edge cost function. Unfortunately, Unfortunately, the GED problem is NP-hard. The question of elaborating fast and precise algorithms is of first interest. In this paper, a parallel algorithm for exact GED computation is proposed. Our proposal is based on a branch-and-bound algorithm coupled with a load balancing strategy. Parallel threads run a branch-and-bound algorithm to $ Fully documented templates are available in the elsarticle package on CTAN. explore the solution space and to discard misleading partial solutions. In the mean time, the load balancing scheme ensures that no thread remains idle. Experiments on 4 publicly available datasets empirically demonstrated that under time constraints our proposal can drastically improve a sequential approach and a naive parallel approach. Our proposal was compared to 6 other methods and provided more precise solutions while requiring a low memory usage.
Type de document :
Article dans une revue
Expert Systems with Applications, Elsevier, 2018, 94, pp.41 - 57. 〈10.1016/j.eswa.2017.10.043〉
Liste complète des métadonnées

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

https://hal-espci.archives-ouvertes.fr/hal-01629290
Contributeur : Romain Raveaux <>
Soumis le : lundi 6 novembre 2017 - 13:36:36
Dernière modification le : vendredi 23 novembre 2018 - 15:38:47

Fichier

ESWA-load balancing.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, Patrick Martineau. A parallel graph edit distance algorithm. Expert Systems with Applications, Elsevier, 2018, 94, pp.41 - 57. 〈10.1016/j.eswa.2017.10.043〉. 〈hal-01629290〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

65