Skip to Main content Skip to Navigation
Conference papers

A Metric Learning Approach to Graph Edit Costs for Regression

Linlin Jia 1 Benoit Gaüzère 1 Florian yger 2, 3 Paul Honeine 1 
1 DocApp - LITIS - Equipe Apprentissage
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
3 MILES - Machine Intelligence and Learning Systems
LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
Abstract : Graph edit distance (GED) is a widely used dissimilarity measure between graphs. It is a natural metric for comparing graphs and respects the nature of the underlying space, and provides interpretability for operations on graphs. As a key ingredient of the GED, the choice of edit cost functions has a dramatic effect on the GED and therefore the classification or regression performances. In this paper, in the spirit of metric learning, we propose a strategy to optimize edit costs according to a particular prediction task, which avoids the use of predefined costs. An alternate iterative procedure is proposed to preserve the distances in both the underlying spaces, where the update on edit costs obtained by solving a constrained linear problem and a re-computation of the optimal edit paths according to the newly computed costs are performed alternately. Experiments show that regression using the optimized costs yields better performances compared to random or expert costs.
Complete list of metadata
Contributor : Paul Honeine Connect in order to contact the contributor
Submitted on : Tuesday, February 2, 2021 - 1:13:29 PM
Last modification on : Wednesday, March 2, 2022 - 10:10:12 AM
Long-term archiving on: : Monday, May 3, 2021 - 7:15:44 PM


Files produced by the author(s)


  • HAL Id : hal-03128664, version 1


Linlin Jia, Benoit Gaüzère, Florian yger, Paul Honeine. A Metric Learning Approach to Graph Edit Costs for Regression. 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-03128664⟩



Record views


Files downloads