A Metric Learning Approach to Graph Edit Costs for Regression

Autor: Florian Yger, Paul Honeine, Linlin Jia, Benoit Gaüzère
Přispěvatelé: Equipe Apprentissage (DocApp - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Machine Intelligence and Learning Systems (MILES), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, ANR-18-CE23-0014,APi,Apprivoiser la Pré-image(2018), ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017)
Rok vydání: 2021
Předmět:
Theoretical computer science
Computer science
02 engineering and technology
[INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE]
Space (commercial competition)
01 natural sciences
Measure (mathematics)
[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Task (project management)
[STAT.ML]Statistics [stat]/Machine Learning [stat.ML]
[INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing
[INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG]
[INFO.INFO-CY]Computer Science [cs]/Computers and Society [cs.CY]
[MATH.MATH-ST]Mathematics [math]/Statistics [math.ST]
0103 physical sciences
0202 electrical engineering
electronic engineering
information engineering
010306 general physics
Interpretability
[INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV]
Edit costs
Regression
Metric (mathematics)
Key (cryptography)
020201 artificial intelligence & image processing
Graph edit distance
Graph operations
[SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Metric Learning
Zdroj: Lecture Notes in Computer Science ISBN: 9783030739720
S+SSPR
Proceedings of IAPR Joint International Workshops on Statistical techniques in Pattern Recognition (SPR 2020) and Structural and Syntactic Pattern Recognition (SSPR 2020)
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
DOI: 10.1007/978-3-030-73973-7_23
Popis: International audience; 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.
Databáze: OpenAIRE
Externí odkaz: