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


Book Volume: 29

Pages Range: 419-458

Journal Issue: 1

DOI: 10.1007/s00778-019-00544-1


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

Involved external institutions

How to cite


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.


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

BibTeX: Download