A Metric Learning Approach to Graph Edit Costs for Regression
Jia, Linlin; Gaüzère, Benoit; Yger, Florian; Honeine, Paul (2021), A Metric Learning Approach to Graph Edit Costs for Regression, in Torsello, Andrea; Rossi, Luca; Pelillo, Marcello, Structural, Syntactic, and Statistical Pattern Recognition, Springer, p. 238-247. 10.1007/978-3-030-73973-7_23
TypeCommunication / Conférence
Conference titleJoint IAPR International Workshops, S+SSPR 2020
Book titleStructural, Syntactic, and Statistical Pattern Recognition
Book authorTorsello, Andrea; Rossi, Luca; Pelillo, Marcello
Number of pages378
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)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.
Subjects / KeywordsGraph edit distance; Edit costs; Metric Learning
Showing items related by title and author.
Chevallier, Sylvain; Corsi, Marie-Constance; Yger, Florian; de Vico Fallani, Fabrizio (2022) Article accepté pour publication ou publié