# Ring based approximation of graph edit distance

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

**Publication Type:** Conference contribution

**Publication year:** 2018

### Journal

**Publisher:** Springer Verlag

**Book Volume:** 11004 LNCS

**Pages Range:** 293-303

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

**Event location:** Beijing

**ISBN:** 9783319977843

**DOI:** 10.1007/978-3-319-97785-0_28

### Abstract

The graph edit distance (GED) is a flexible graph dissimilarity measure widely used within the structural pattern recognition field. A widely used paradigm for approximating GED is to define local structures rooted at the nodes of the input graphs and use these structures to transform the problem of computing GED into a linear sum assignment problem with error correction (LSAPE). In the literature, different local structures such as incident edges, walks of fixed length, and induced subgraphs of fixed radius have been proposed. In this paper, we propose to use rings as local structure, which are defined as collections of nodes and edges at fixed distances from the root node. We empirically show that this allows us to quickly compute a tight approximation of GED.

### Authors with CRIS profile

### Involved external institutions

### How to cite

**APA:**

Blumenthal, D.B., Bougleux, S., Gamper, J., & Brun, L. (2018). Ring based approximation of graph edit distance. In Edwin R. Hancock, Tin Kam Ho, Battista Biggio, Richard C. Wilson, Antonio Robles-Kelly, Xiao Bai (Eds.), *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)* (pp. 293-303). Beijing, CN: Springer Verlag.

**MLA:**

Blumenthal, David B., et al. "Ring based approximation of graph edit distance." *Proceedings of the Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018, Beijing* Ed. Edwin R. Hancock, Tin Kam Ho, Battista Biggio, Richard C. Wilson, Antonio Robles-Kelly, Xiao Bai, Springer Verlag, 2018. 293-303.

**BibTeX:** Download