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

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.

Keywords: Graph Edit Distance; Pre-image problem; Machine Learning; Graph Kernels

Domains: Statistics [stat]; Machine Learning [stat.ML]; Engineering Sciences [physics]; Signal and Image processing; Mathematics [math]; Statistics [math.ST]; Computer Science [cs]; Signal and Image Processing; Computer Science [cs]; Neural and Evolutionary Computing [cs.NE]; Computer Science [cs]; Machine Learning [cs.LG]; Computer Science [cs]; Computers and Society [cs.CY]; Computer Science [cs]; Computer Vision and Pattern Recognition [cs.CV]; Computer Science [cs]; Artificial Intelligence [cs.AI]

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⟩