Contribution to the theory of graph neural networks on large random graphs

Contribution à la théorie des réseaux de neurones en graphes sur des grands graphes aléatoires Une grande variété de données, comme les molécules, la propagation des épidémies, ou plus généralement tout type de réseaux, sont fidèlement représentées par des graphes. Contrairement aux données classiques, dites euclidiennes, comme les images digitales, les données en graphes renferment une double information. D'une part, le graphe lui-même, structure irrégulière qui gouverne la propagation de l'information au sein du réseau. D'autre part, la donnée portée par chaque nœud, dont l'ensemble est appelé signal sur graphe.En apprentissage statistique, une base de données suffisamment vaste est essentielle. De telles bases de données existent pour des petits graphes, tandis que pour les grands graphes, elles se résument souvent à un unique graphe géant (de l'ordre du million, voire milliard de nœuds). On distingue donc deux types de tâches en apprentissage sur graphes. D'abord, les tâches sur les graphes, comme la classification de graphes, où on demande à un algorithme de retourner un attribut global pour le graphe. Ces tâches concernent quasi exclusivement les petits graphes, pour lesquels de vastes bases de données sont disponibles. Ensuite, les tâches sur les nœuds, comme la détection de communautés, pour lesquelles un algorithme devra renvoyer un signal sur le graphe. Dans ce cas, on s'intéresse plutôt aux grands graphes et moins aux petits graphes, pour lesquels on privilégiera des méthodes plus directes comme le partitionnement spectral. Ainsi, les grands graphes sont essentiellement liés aux tâches sur les nœuds et vice versa.Malgré cette dichotomie, tout modèle pour les donnée en graphes doit utiliser chacunes des deux facettes de l'information, à savoir le graphe et le signal qu'il porte. Une solution moderne, objet d'étude de cette thèse, est le réseau de neurones en graphe (RNG), une architecture d'apprentissage profond spécialement conçue pour traiter les données en graphe. Un même RNG peut traiter des graphes de toute taille et s'adapter d'une tâche sur nœuds à une tâche sur graphes via une légère modification. De plus, un RNG exploite toujours la double information grâce au mécanisme de «message passing», par lequel le signal sur les nœuds est propagé selon la structure du graphe.Cependant, bien que les RNG soient devenus une référence en apprentissage sur graphes, leur théorie reste mal comprise. Par exemple, il arrive qu'un RNG avec des paramètres aléatoires non entraînés réussisse aussi bien qu'un modèle entraîné. Ce genre de phénomène demeure surprenant, et des notions clés, comme la généralisation ou l'expressivité, sont encore mal définies pour l'apprentissage statistique sur graphes et les RNG.L'axe de recherche dominant en théorie des RNG s'appuie sur des idées combinatoires et se concentre sur les tâches sur graphes. Ce point de vue est mal adapté aux grands graphes et aux tâches sur les nœuds, pour lesquelles la théorie des RNG est à peine balbutiante. L'objectif de cette thèse est de contribuer à l'étude des RNG pour les grands graphes. Nous adoptons une approche statistique et analytique en modélisant les grands graphes et leurs signaux par un modèle de graphes aléatoires dit à espace latent. Les nœuds sont tirés aléatoirement dans un espace inconnu, puis connectés aléatoirement selon un noyau agissant sur cet espace. Quant aux signaux, ils sont échantillonnés à partir de fonctions sur l'espace latent. Notre première contribution est d'établir que certains RNG à «message passing» sur des graphes aléatoires de taille croissante convergent vers un homologue dit continu. Le RNG discret traite un signal sur graphe, tandis que sa limite continue traite une fonction sur l'espace latent. Ainsi, ce théorème de convergence permet de passer du monde discret au monde continu et vice versa, par passage à la limite ou échantillonnage. Notre seconde contribution est d'exploiter cette convergence pour proposer et étudier une notion d'expressivité adaptée aux RNG sur les grands graphes aléatoires.