# Exact computation of graph edit distance for uniform and non-uniform metric edit costs

Blumenthal DB, Gamper J (2017)

**Publication Type:** Conference contribution

**Publication year:** 2017

### Journal

**Publisher:** Springer Verlag

**Book Volume:** 10310 LNCS

**Pages Range:** 211-221

**Conference Proceedings Title:** Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

**Event location:** Anacapri, ITA

**ISBN:** 9783319589602

**DOI:** 10.1007/978-3-319-58961-9_19

### Abstract

The graph edit distance is a well-established and widely used distance measure for labelled, undirected graphs. However, since its exact computation is NP-hard, research has mainly focused on devising approximative heuristics and only few exact algorithms have been proposed. The standard approach A_-GED, a node-based best-first search that works for both uniform and non-uniform metric edit costs, suffers from huge runtime and memory requirements. Recently, two better performing algorithms have been proposed: DF-GED, a node-based depth-first search that works for uniform and non-uniform metric edit costs, and CSI GED, an edge-based depth-first search that works only for uniform edit costs. Our paper contains two contributions: First, we propose a speed-up DF-GEDu of DF-GED for uniform edit costs. Second, we develop a generalisation CSI GEDnu of CSI GED that also covers non-uniform metric edit cost. We empirically evaluate the proposed algorithms. The experiments show, i.a., that our speed-up DF-GEDu clearly outperforms DF-GED and that our generalisation CSI GEDnu is the most versatile algorithm.

### Authors with CRIS profile

### Involved external institutions

### How to cite

**APA:**

Blumenthal, D.B., & Gamper, J. (2017). Exact computation of graph edit distance for uniform and non-uniform metric edit costs. In Pasquale Foggia, Mario Vento, Cheng-Lin Liu (Eds.), *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)* (pp. 211-221). Anacapri, ITA: Springer Verlag.

**MLA:**

Blumenthal, David B., and Johann Gamper. "Exact computation of graph edit distance for uniform and non-uniform metric edit costs." *Proceedings of the 11th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, GbRPR 2017, Anacapri, ITA* Ed. Pasquale Foggia, Mario Vento, Cheng-Lin Liu, Springer Verlag, 2017. 211-221.

**BibTeX:** Download