A Graph Pre-image Method Based on Graph Edit Distances - Archive ouverte HAL Access content directly
Conference Papers Year : 2021

A Graph Pre-image Method Based on Graph Edit Distances

Linlin Jia
Benoit Gaüzère
Paul Honeine


The pre-image problem for graphs is increasingly attracting attention owing to many promising applications. However, it is a challenging problem due to the complexity of graph structure. In this paper, we propose a novel method to construct graph pre-images as median graphs, by aligning graph edit distances (GEDs) in the graph space with distances in the graph kernel space. The two metrics are aligned by optimizing the edit costs of GEDs according to the distances between the graphs within the space associated with a particular graph kernel. Then, the graph pre-image can be estimated using a median graph method founded on the GED. In particular, a recently introduced method to compute generalized median graphs with iterative alternate minimizations is revisited for this purpose. Conducted experiments show very promising results while opening the computation of graph pre-image to any graph kernel and to graphs with non-symbolic attributes.
Fichier principal
Vignette du fichier
21.s+sspr.graphpreimage.pdf (917.27 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03128660 , version 1 (02-02-2021)
hal-03128660 , version 2 (31-03-2021)



Linlin Jia, Benoit Gaüzère, Paul Honeine. A Graph Pre-image Method Based on Graph Edit Distances. Proceedings of IAPR Joint International Workshops on Statistical techniques in Pattern Recognition (SPR 2020) and Structural and Syntactic Pattern Recognition (SSPR 2020)., Jan 2021, Venise, Italy. ⟨10.1007/978-3-030-73973-7_21⟩. ⟨hal-03128660v2⟩
86 View
95 Download



Gmail Facebook Twitter LinkedIn More