Upper Bounding Graph Edit Distance Based on Rings and Machine Learning

Blumenthal DB, Gamper J, Bougleux S, Brun L (2021)

Publication Type: Journal article

Publication year: 2021

Journal

International Journal of Pattern Recognition and Artificial Intelligence World Scientific Publishing

Article Number: 2151008

DOI: 10.1142/S0218001421510083

Abstract

The graph edit distance (GED) is a flexible distance measure which is widely used for inexact graph matching. Since its exact computation is-hard, heuristics are used in practice. A popular approach is to obtain upper bounds for GED via transformations to the linear sum assignment problem with error-correction (LSAPE). Typically, local structures and distances between them are employed for carrying out this transformation, but recently also machine learning techniques have been used. In this paper, we formally define a unifying framework LSAPE-GED for transformations from GED to LSAPE. We also introduce rings, a new kind of local structures designed for graphs where most information resides in the topology rather than in the node labels. Furthermore, we propose two new ring-based heuristics RING and RING-ML, which instantiate LSAPE-GED using the traditional and the machine learning-based approach for transforming GED to LSAPE, respectively. Extensive experiments show that using rings for upper bounding GED significantly improves the state of the art on datasets where most information resides in the graphs' topologies. This closes the gap between fast but rather inaccurate LSAPE-based heuristics and more accurate but significantly slower GED algorithms based on local search.

Authors with CRIS profile

David Blumenthal Professur für Biomedical Network Science

Involved external institutions

École nationale supérieure d'ingénieurs de Caen (ENSICAEN) FR France (FR) Free University of Bozen - Bolzano IT Italy (IT)

How to cite

APA:

Blumenthal, D.B., Gamper, J., Bougleux, S., & Brun, L. (2021). Upper Bounding Graph Edit Distance Based on Rings and Machine Learning. International Journal of Pattern Recognition and Artificial Intelligence. https://dx.doi.org/10.1142/S0218001421510083

MLA:

Blumenthal, David B., et al. "Upper Bounding Graph Edit Distance Based on Rings and Machine Learning." International Journal of Pattern Recognition and Artificial Intelligence (2021).

BibTeX: Download