New binary linear programming formulation to compute the graph edit distance

Abstract : In this paper, a new binary linear programming formulation for computing the exact Graph Edit Distance (GED) between two graphs is proposed. A fundamental strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs. Moreover , a continuous relaxation of the domain constraints in the formulation provides an efficient lower bound approximation of the GED. A complete experimental study that compares the proposed formulations with six state-of-the-art algorithms is provided. By considering both the accuracy of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominate the others in the Pareto sense. In general, our formulation converges faster to optimality while being able to scale up to match the largest graphs in our experiments. The relaxed formulation leads to an accurate approach that is 12% more accurate than the best approximate method of our benchmark.
Type de document :
Article dans une revue
Pattern Recognition, Elsevier, 2017, 72, pp.254 - 265. 〈10.1016/j.patcog.2017.07.029〉
Liste complète des métadonnées

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

https://hal-espci.archives-ouvertes.fr/hal-01619308
Contributeur : Romain Raveaux <>
Soumis le : lundi 8 octobre 2018 - 11:45:54
Dernière modification le : samedi 27 octobre 2018 - 01:24:33

Fichier

Identifiants

Citation

Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, Sébastien Adam. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, Elsevier, 2017, 72, pp.254 - 265. 〈10.1016/j.patcog.2017.07.029〉. 〈hal-01619308〉

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

3