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
2 LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
3 MILES - Machine Intelligence and Learning Systems

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.

Keywords: Graph edit distance; Edit costs; Metric Learning

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, 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. ⟨10.1007/978-3-030-73973-7_23⟩. ⟨hal-03128664⟩