Ring Based Approximation of Graph Edit Distance - Archive ouverte HAL Access content directly
Conference Papers Year :

Ring Based Approximation of Graph Edit Distance

Approximation de la distance d'édition entre graphes par anneaux.

, (1) , (2) , (1)
1
2

Abstract

The graph edit distance (GED) is a flexible graph dissimilar-ity 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.
Fichier principal
Vignette du fichier
sspr18ring-bged.pdf (358.16 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01865194 , version 1 (31-08-2018)

Identifiers

  • HAL Id : hal-01865194 , version 1

Cite

David Blumenthal, Sébastien Bougleux, Johann Gamper, Luc Brun. Ring Based Approximation of Graph Edit Distance. Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Aug 2018, Pékin, China. ⟨hal-01865194⟩
45 View
170 Download

Share

Gmail Facebook Twitter LinkedIn More