Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem

Blumenthal DB, Daller E, Bougleux S, Brun L, Gamper J (2018)

Publication Type: Conference contribution

Publication year: 2018

Journal

Proceedings - International Conference on Pattern Recognition

Publisher: Institute of Electrical and Electronics Engineers Inc.

Book Volume: 2018-August

Pages Range: 934-939

Conference Proceedings Title: Proceedings - International Conference on Pattern Recognition

Event location: Beijing CN

ISBN: 9781538637883

DOI: 10.1109/ICPR.2018.8546055

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.

Authors with CRIS profile

David Blumenthal Professur für Biomedical Network Science

Involved external institutions

Free University of Bozen - Bolzano IT Italy (IT) Normandy University / Normandie Université FR France (FR)

How to cite

APA:

Blumenthal, D.B., Daller, E., Bougleux, S., Brun, L., & Gamper, J. (2018). Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem. In Proceedings - International Conference on Pattern Recognition (pp. 934-939). Beijing, CN: Institute of Electrical and Electronics Engineers Inc..

MLA:

Blumenthal, David B., et al. "Quasimetric Graph Edit Distance as a Compact Quadratic Assignment Problem." Proceedings of the 24th International Conference on Pattern Recognition, ICPR 2018, Beijing Institute of Electrical and Electronics Engineers Inc., 2018. 934-939.

BibTeX: Download