Skip to Main content Skip to Navigation
Conference papers

A Graph Pre-image Method Based on Graph Edit Distances

Linlin Jia 1 Benoit Gaüzère 1 Paul Honeine 1
1 DocApp - LITIS - Equipe Apprentissage
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : 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.
Complete list of metadata
Contributor : Paul Honeine <>
Submitted on : Wednesday, March 31, 2021 - 3:18:43 PM
Last modification on : Friday, April 2, 2021 - 3:30:50 AM


Files produced by the author(s)


  • HAL Id : hal-03128660, version 2


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. ⟨hal-03128660v2⟩



Record views


Files downloads