Offre de thèse : Apprentissage géométrique : vers des réseaux de neurones sur graphes à haute expressivité

Au cours des dernières années, les réseaux de neurones sur graphes (Graph Neural Networks, GNNs) ont émergé comme une méthode incontournable pour résoudre des tâches d'apprentissage sur des données structurées sous forme de graphes, en tirant parti des relations entre les entités. Pour évaluer le pouvoir expressif de ces GNNs (i.e.leur capacité à distinguer des graphes non isomorphes et donc leur adaptabilité à des données diverses), la hiérarchie de Weisfeiler-Lehman (WL), fondée sur le test d'isomorphisme éponyme [1], s'est imposée comme la méthode de référence [2,3,4,5] en complément des analyses centrées sur leurs capacités spectrales [6].

Un résultat clé dans ce domaine réside dans la démonstration que les réseaux de type Message Passing Neural Networks (MPNNs) utilisés dans la plupart des applications réelles des GNNs, sont, au mieux, aussi puissants que le test WL de premier ordre (1-WL) [7][8]. Sur cette base, de nombreuses contributions se sont focalisées sur le dépassement de cette limite 1-WL pour concevoir des GNNs plus expressifs (et donc mieux adaptés à des données plus difficiles). Parmi ces approches, les GNNs basés sur des sous-graphes ont démontré une expressivité supérieure à 1-WL, tout en restant limités par la puissance de 3-WL [9].

En adoptant un point de vue algébrique, l'équipe de F. Geerts a proposé dans [10] de reformuler les tests 1-WL et 3-WL grâce à des langages basés sur des sous-ensembles spécifiques d'opérations algébriques appliquées à la matrice d'adjacence. Ces fragments du langage matriciel MATLANG, nommés ML(L1) et ML(L3), ont été prouvés comme aussi expressifs que 1-WL et 3-WL [10].

S’appuyant sur ces avancées, nous avons proposé au sein de l'équipe Apprentissage du LITIS le modèle GNNML1 [11]. Ce modèle, prouvé comme équivalent à 1-WL, est capable de générer l’ensemble des phrases de ML(L1). Un modèle plus expressif, GNNML3, a également été développé dans cette étude. Bien que ce dernier ait démontré des performances expérimentales comparables à celles des modèles 3-WL existants [12], son expressivité théorique au niveau 3-WL n’a pas été établie dans [11].

Dans le cadre de la thèse de Jason Piquenot qui sera soutenue en 2025, cette recherche a été approfondie et étendue pour développer une procédure de génération de GNNs à partir de la définition d’un langage, en s’appuyant sur des grammaires non-contextuelles.

Ce travail, publié à ICLR'24 [13], a conduit à la conception du modèle G2N2, démontré comme atteignant une expressivité équivalente à 3-WL. Ce résultat positionne G2N2 parmi les deux seuls modèles de réseaux de neurones sur graphes actuels à posséder cette expressivité, tout en affichant des performances expérimentales supérieures à l’autre modèle 3-WL existant : PPGN. Les développements théoriques issus de ces travaux ont également permis la proposition du modèle GPN (Grammatical Path Network) [14] , un GNN spécialement conçu pour capturer des cycles de longueur (l+1) au niveau des arêtes en pré-calculant des chemins de longueur (l).

Ces résultats marquent une avancée significative, positionnant l’équipe Apprentissage du LITIS comme un acteur majeur de la communauté scientifique internationale travaillant à la conception de modèles à l’état de l’art en apprentissage sur graphes. Ils ont également mis en lumière certaines limitations dont en particulier l'enjeu central de définir de nouveaux langages permettant de dépasser l’expressivité de 3-WL.

Cette thèse propose d’explorer précisément cet axe, ainsi que ses applications.