Comparing heuristics for graph edit distance computation

Blumenthal DB, Boria N, Gamper J, Bougleux S, Brun L (2020)

Publication Type: Journal article

Publication year: 2020

Journal

Vldb Journal Springer Verlag (Germany)

Book Volume: 29

Pages Range: 419-458

Journal Issue: 1

DOI: 10.1007/s00778-019-00544-1

Abstract

Because of its flexibility, intuitiveness, and expressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP-hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper, we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.

Authors with CRIS profile

David Blumenthal Professur für Biomedical Network Science

Involved external institutions

Université de Caen Basse-Normandie FR France (FR) Free University of Bozen - Bolzano IT Italy (IT)

How to cite

APA:

Blumenthal, D.B., Boria, N., Gamper, J., Bougleux, S., & Brun, L. (2020). Comparing heuristics for graph edit distance computation. Vldb Journal, 29(1), 419-458. https://doi.org/10.1007/s00778-019-00544-1

MLA:

Blumenthal, David B., et al. "Comparing heuristics for graph edit distance computation." Vldb Journal 29.1 (2020): 419-458.

BibTeX: Download