Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - Université de Rouen Normandie

In this talk, we study notions of distances between graphs and their connections to optimal transport and combinatorial optimization. We focus in particular on graph edit distance and its relation to the Quadratic Assignment Problem (QAP), which provides a natural formulation for graph matching under structural constraints. We then introduce optimal transport-based distances, especially the Wasserstein distance and its extension to metric measure spaces via the Gromov–Wasserstein distance. These tools allow for comparing objects with different underlying supports by optimizing over all possible correspondences. We discuss the conceptual and mathematical links between graph edit distance and optimal transport, highlighting how edit operations can be interpreted through transport formulations with structured costs.Finally, we present a supervised learning approach to approximate these problems using Graph Neural Networks, aiming to learn efficient heuristics for graph matching and distance estimation from data.