The graph alignment problem: fundamental limits and efficient algorithms
Alignement de graphes : limites fondamentales et algorithmes efficaces
Résumé
This thesis focuses on statistical inference in graphs (or matrices) in high dimension
and studies the graph alignment problem which aims to recover a hidden underlying
matching between the nodes of two correlated random graphs.
Similarly to many other inference problems in planted models, we are interested in understanding
the fundamental information-theoretical limits as well as the computational hardness
of graph alignment.
First, we study the Gaussian setting, when the graphs are complete and the signal lies
on correlated Gaussian edges weights. We prove that the exact recovery task exhibits a
sharp information-theoretic threshold, characterize it, and study a simple and natural spectral
method for recovery, EIG1, which consists in aligning the leading eigenvectors of the adjacency
matrices of the two graphs.
While most of the recent work on the subject was dedicated to recovering the hidden
signal in dense graphs, we next explore graph alignment in the sparse regime, where the mean
degrees 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 any
algorithm. Our second contribution is an information-theoretical result which characterizes
a regime where even this partial alignment is impossible, and gives upper bounds on the
reachable overlap between any estimator and the true planted matching.
We next propose an algorithm that performs partial alignment, NTMA, which is based on
a measure of similarity – called the tree matching weight – between tree-like neighborhoods
of 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 in
testing whether two trees are correlated or independent. The tree matching weight yields
a first method for this question as well; another contribution is to study an optimal test
based on the likelihood ratio. In a correlated Galton-Watson model, which is well-known
to be the local approximation of sparse Erdos-Rényi graphs, we characterize the regimes of
performance 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-passing
algorithm is analyzed and provably recovers a fraction of the planted signal in some
regimes 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 à retrouver
un 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 nous
inté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 complets
et 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 étudions
un algorithme spectral simple, EIG1, consistant à aligner les vecteurs propres dominants
des matrices d’adjacence des deux graphes.
Tandis que la grande majorité des travaux récents sur le sujet est dédiée à l’alignement
exact dans les graphes denses, nous explorons dans la suite de la thèse un régime dit creux
dans lequel le degré moyen des sommets est constant, indépendant de la taille du graphe. Pour
les graphes d’Erdos-Rényi, dans ce régime ou l’alignement est plus difficile, n’importe quel
algorithme ne pourra aligner seulement qu’une fraction des noeuds : on parle d’alignement
partiel. Nous démontrons un résultat informationnel caractérisant un régime dans lequel
l’alignement partiel est impossible, et donnant une borne supérieure sur la fraction de noeuds
du graphe qu’un estimateur peut espérer correctement aligner.
Nous proposons par la suite un algorithme, NTMA, pour l’alignement partiel dans le régime
où 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 passage
de 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égimes
de paramètres.
Origine : Fichiers produits par l'(les) auteur(s)