Soutenance de Thèse – Martin GJORGJEVSKI

Depuis le début du XXIe siècle, des efforts considérables ont été déployés pour concevoir des algorithmes 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’un signal 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 graphes où le signal n’est observé que sur un sous-ensemble de 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’accompagnent de garanties théoriques de performance. La raison principale en est sans doute l’absence de modé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 plusieurs décennies, et il serait donc utile de comprendre
les propriétés théoriques des différents algorithmes 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œuds et 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, non observée dans l’espace euclidien. En adoptant le modèle de position latente, nous disposons d’une base théorique claire issue 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éoriques pour les problèmes de régression des nœuds et de lissage des signaux pour divers algorithmes dans le contexte des graphes aléatoires du modèle de position latente.