Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem

Abstract : The graph edit distance (GED) is a widely used distance measure for attributed graphs. It has recently been shown that the problem of computing GED, which is a NP-hard optimization problem, can be formulated as a quadratic assignment problem (QAP). This formulation is useful, since it allows to derive well performing approximative heuristics for GED from existing techniques for QAP. In this paper, we focus on the case where the edit costs that underlie GED are quasimetric. This is the case in many applications of GED. We show that, for quasimetric edit costs, it is possible to reduce the size of the corresponding QAP formulation. An empirical evaluation shows that this reduction significantly speeds up the QAP-based approximative heuristics for GED.
Type de document :
Communication dans un congrès
24th International Conference on Pattern Recognition (ICPR), Aug 2018, Pékin, China
Liste complète des métadonnées

https://hal-normandie-univ.archives-ouvertes.fr/hal-01865214
Contributeur : Luc Brun <>
Soumis le : dimanche 9 septembre 2018 - 15:31:36
Dernière modification le : jeudi 7 février 2019 - 17:46:46
Document(s) archivé(s) le : lundi 10 décembre 2018 - 12:34:50

Identifiants

  • HAL Id : hal-01865214, version 1

Citation

David Blumenthal, Evariste Daller, Sébastien Bougleux, Luc Brun, Johann Gamper. Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem. 24th International Conference on Pattern Recognition (ICPR), Aug 2018, Pékin, China. 〈hal-01865214〉

Partager

Métriques

Consultations de la notice

29

Téléchargements de fichiers

33