On Statistical Learning theory for Random Graphs

Depuis le début du XXIe siècle, des efforts considérables ont été déployés pour concevoir desalgorithmes fonctionnant sur des réseaux : sociaux (Instagram, LinkedIn), World Wide Web, sémantiques,etc. Ces ensembles de données peuvent naturellement être représentés par un graphe, dans lequel les entités d'intérêt (par exemple, les utilisateurs de réseaux sociaux, les pages web) sont modélisées sous forme de nœuds et leurs relations sont représentées par des arêtes (potentiellement pondérées). Outre la structure du graphe, ces ensembles de données sont souvent accompagnés d'unsignal supplémentaire au niveau des nœuds. Par conséquent, divers problèmes d'apprentissage automatique liés à une paire graphe-signal se posent. Dans cette thèse, nous examinerons deux de ces problèmes : la régression des nœuds et le lissage des signaux sur les graphes.La régression des nœuds est une tâche d'apprentissage automatique sur les graphes où le signal n'est observé que sur un sous-ensemble des nœuds. L'objectif est de prédire la partie manquante du signal. Dans le problème étroitement liédu lissage des signaux, des observations bruitées sont disponibles pour tous les nœuds du graphe et l'objectif est de réduire le bruit dans ces observations.Malgré l'abondante littérature sur les méthodes utilisées pour ces tâches, il est surprenant de constater que peu d'entre elles s'accompagnentde garanties théoriques de performance. La raison principale en est sans doute l'absence demodélisation statistique de la paire graphe-signal — il est courant de traiter le graphe comme un objet non aléatoire. D'autre part, les graphes aléatoires sont utilisés dans des applications depuis plusieursdécennies, et il serait donc utile de comprendre les propriétés théoriques de diversalgorithmes pour les problèmes énoncés dans le contexte des modèles de graphes aléatoires.Dans cette thèse, nous fournirons une analyse théorique des problèmes énoncés (régression des nœudset lissage des signaux) dans le contexte d'un modèle spécifique de graphe aléatoire, à savoir le modèle de position latente (LPM). Dans le modèle de position latente, chaque nœud est associé à une position latente et non observée dans l'espace euclidien. En adoptant le modèle de position latente, nous disposons d'une base théorique claire issu des travaux classiques dans le domaine de la régression non paramétrique, que nous nous efforçons d'atteindre en concevant des méthodes qui opèrent sur la paire graphe-signal. Nous dériverons des garanties théoriquespour les problèmes de régression des nœuds et de lissage des signaux pour divers algorithmes dans lecontexte des graphes aléatoires du modèle de position latente.