Appears in collection : 9e Journée Statistique et Informatique pour la Science des Données à Paris-Saclay

Aligning two (weighted or unweighted) graphs, or matching two clouds of high-dimensional embeddings, are fundamental problems in machine learning with applications across diverse domains such as natural language processing to computational biology. In this presentation I will introduce the graph alignment problem, which can be viewed as an average-case and noisy version of the graph isomorphism problem. I will talk about the main challenges when the graphs are sparse, give some insights on the fundamental limits, and present efficient algorithms for this task. Then, switching focus on aligning clouds of embeddings, I will delve into the Procrustes-Wassertein problem. We will emphasize differences from the previous graph-to-graph case. Statistical and computational results will be presented to shed light on these emerging questions.