Alignement de graphes : limites informationnelles et algorithmes efficaces
1 : Inria de Paris
Institut National de Recherche en Informatique et en Automatique, Ecole Normale Supérieure de Paris - ENS Paris
Le problème d'alignement de graphes, dans sa version plantée, a pour but la reconstruction d'un appariement sous-jacent entre les noeuds de deux graphes dont les arêtes sont correlées : il peut ainsi être vu comme la version bruitée du problème d'isomorphisme de graphe. Pour les graphes d'Erdős-Rényi correlés, nous donnerons tout d'abord des résultats sur les limites fondamentales pour ce problème de reconstruction. Du point de vue algorithmique, l'enjeu est de proposer des méthodes efficaces (c'est-à-dire polynomiales) pour l'alignement de graphes. Dans un régime dit sparse (i.e. avec degré moyen constant), nous étudierons la reformulation locale de ce problème : la détection de corrélation dans des arbres. Ce point de vue donne des résultats théoriques et s'avère utile pour le design d'un algorithme de message-passing (belief-propagation) pour notre problème initial. Travail en collaboration avec Laurent Massoulié et Marc Lelarge: https://arxiv.org/abs/2002.01258, https://arxiv.org/abs/2102.02685, https://arxiv.org/abs/2107.07623.
Planted graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For correlated Erdős-Rényi random graphs, we will give insights on the fundamental limits for this problem, pinning down statistical thresholds for exact or partial recovery of the planted structure. From the computational point of view we are interested in designing and analyzing efficient (polynomial-time) algorithms to reconstruct efficiently the underlying alignment: in a sparse regime, we exhibit an local rephrasing of the planted alignment problem as a correlation detection problem in trees, which helps deriving a belief propagation algorithm for our initial task. Based on joint works with Laurent Massoulié and Marc Lelarge: https://arxiv.org/abs/2002.01258, https://arxiv.org/abs/2102.02685, https://arxiv.org/abs/2107.07623.
| Type : | : | Résumé |
| Thématiques | : | Probabilités discrètes et mécanique statistique |
| PDF version | : |  PDF version |
