New binary linear programming formulation to compute the graph edit distance

Abstract : Graph edit distance (GED) is a powerful and flexible graph matching paradigm that can be used to address different tasks in structural pattern recognition, machine learning, and data mining. In this paper, some new binary linear programming formulations for computing the exact GED between two graphs are proposed. A major strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs (i.e. with attributes on both vertices and edges). Moreover, a relaxation of the domain constraints in the formulations provides efficient lower bound approximations of the GED. A complete experimental study comparing the proposed formulations with 4 state-of-the-art algorithms for exact and approximate graph edit distances is provided. By considering both the quality of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominates the others in the Pareto sense. As a consequence, faced to a given real-world problem, a trade-off between quality and efficiency has to be chosen w.r.t. the application constraints. In this context, this paper provides a guide that can be used to choose the appropriate method.
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 [7 références]  Voir  Masquer  Télécharger
Contributeur : Romain Raveaux <>
Soumis le : lundi 8 octobre 2018 - 11:44:47
Dernière modification le : jeudi 7 février 2019 - 17:32:11
Document(s) archivé(s) le : mercredi 9 janvier 2019 - 12:53:48


Fichiers produits par l'(les) auteur(s)



Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, Sebastien 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-01619313〉



Consultations de la notice


Téléchargements de fichiers