A Graph Pre-image Method Based on Graph Edit Distances - Normandie Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

A Graph Pre-image Method Based on Graph Edit Distances

Linlin Jia
Benoit Gaüzère
Paul Honeine

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
101 Consultations
116 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More