Alignement de graphes : limites fondamentales et algorithmes efficaces

This thesis focuses on statistical inference in graphs (or matrices) in high dimensionand studies the graph alignment problem which aims to recover a hidden underlyingmatching between the nodes of two correlated random graphs.Similarly to many other inference problems in planted models, we are interested in understandingthe fundamental information-theoretical limits as well as the computational hardnessof graph alignment.First, we study the Gaussian setting, when the graphs are complete and the signal lieson correlated Gaussian edges weights. We prove that the exact recovery task exhibits asharp information-theoretic threshold, characterize it, and study a simple and natural spectralmethod for recovery, EIG1, which consists in aligning the leading eigenvectors of the adjacencymatrices of the two graphs.While most of the recent work on the subject was dedicated to recovering the hiddensignal in dense graphs, we next explore graph alignment in the sparse regime, where the meandegrees are constant, not scaling with the graph size. In this particularly challenging setting,for sparse Erdos-Rényi graphs, only a fraction of the nodes can be correctly matched by anyalgorithm. Our second contribution is an information-theoretical result which characterizesa regime where even this partial alignment is impossible, and gives upper bounds on thereachable overlap between any estimator and the true planted matching.We next propose an algorithm that performs partial alignment, NTMA, which is based ona measure of similarity – called the tree matching weight – between tree-like neighborhoodsof the nodes in the graphs.Under this local approach in the sparse regime, we are brought to study a related problem:correlation detection in random unlabeled trees. This hypothesis testing problem consists intesting whether two trees are correlated or independent. The tree matching weight yieldsa first method for this question as well; another contribution is to study an optimal testbased on the likelihood ratio. In a correlated Galton-Watson model, which is well-knownto be the local approximation of sparse Erdos-Rényi graphs, we characterize the regimes ofperformance of this test.Finally, we come back to graph alignment and propose a message-passing algorithm,MPAlign, naturally inspired by the study of the related problem on trees. This message-passingalgorithm is analyzed and provably recovers a fraction of the planted signal in someregimes of parameters.Cette thèse a pour contexte l’inférence statistique sur des graphes (ou matrices)en grande dimension et étudie le problème d’alignement de graphes, qui consiste à retrouverun appariement sous-jacent entre les sommets de deux graphes aléatoires correlés.Comme pour de nombreux problèmes d’inférence dans des modèles dit plantés, nous nousintéressons aux limites fondamentales ainsi qu’à la difficulté computationnelle du problème.Nous étudions tout d’abord un modèle Gaussien dans lequel les graphes sont completset où les poids des arêtes matchées sous la correspondence sous-jacente sont correlées. Nousétablissons un seuil informationnel pour la tâche d’alignement exact dans ce modèle, et étudionsun algorithme spectral simple, EIG1, consistant à aligner les vecteurs propres dominantsdes matrices d’adjacence des deux graphes.Tandis que la grande majorité des travaux récents sur le sujet est dédiée à l’alignementexact dans les graphes denses, nous explorons dans la suite de la thèse un régime dit creuxdans lequel le degré moyen des sommets est constant, indépendant de la taille du graphe. Pourles graphes d’Erdos-Rényi, dans ce régime ou l’alignement est plus difficile, n’importe quelalgorithme ne pourra aligner seulement qu’une fraction des noeuds : on parle d’alignementpartiel. Nous démontrons un résultat informationnel caractérisant un régime dans lequell’alignement partiel est impossible, et donnant une borne supérieure sur la fraction de noeudsdu graphe qu’un estimateur peut espérer correctement aligner.Nous proposons par la suite un algorithme, NTMA, pour l’alignement partiel dans le régimeoù les graphes sont creux, définissant une mesure de similarité – le tree matching weight –entre les voisinages arborescents des sommets des deux graphes.En étudiant l’alignement de graphes creux d’un point de vue local, un autre problème associéapparaît : la détection de corrélation dans les arbres. Ce problème de test d’hypothèses,non étudié auparavant, consiste à décider si deux arbres aléatoires sont correlés ou indépendants.Le tree matching weight donne une première méthode pour résoudre ce problème;dans une autre contribution, nous étudions un test optimal pour cette tâche de détection,basé sur le rapport de vraisemblance. Dans un modèle d’arbres de Galton-Watson corrélés,qui sont bien connus pour être les approximations locales des graphes d’Erdos-Rényi creux,nous caractérisons le régime de performance de ce test.L’étude de ce problème sur les arbres donne ainsi naturellement un algorithme de passagede messages en temps polynomial pour notre tâche initiale d’alignement de graphes : MPAlign.Nous prouvons que cette méthode retrouve une fraction du signal planté dans certains régimesde paramètres