Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - Université de Rouen Normandie

Cette présentation porte sur mes travaux de thèse consacrés à l’étude du pouvoir expressif des réseaux de neurones sur graphes (GNNs), avec un accent particulier sur leurs liens profonds avec les grammaires algébriques. Les GNNs sont aujourd’hui des outils majeurs pour le traitement de données structurées en graphes, mais leur capacité à représenter et calculer certaines propriétés combinatoires fondamentales reste encore mal comprise.
Mes travaux proposent un cadre théorique reliant l’expressivité des GNNs à celle de grammaires algébriques. Cette perspective met en évidence que certaines limitations expressives des GNNs correspondent à des restrictions grammaticales sous-jacentes, tandis que des extensions contrôlées de ces grammaires permettent d’accroître significativement leur pouvoir de représentation.
Dans ce contexte, j’introduis l’algorithme Grammar Reinforcement Learning, une approche originale combinant apprentissage par renforcement et exploration d’espaces de grammaires algébriques. Cet algorithme nous a permis de découvrir de nouvelles formules algébriques, plus efficientes, pour le comptage de chemins et de cycles dans les graphes, dépassant à la fois des constructions classiques et des formulations implicitement apprises par les GNNs standards.
Ces résultats établissent un pont inédit entre apprentissage profond, théorie des graphes et méthodes algébriques, et ouvrent la voie à la conception de modèles sur graphes à la fois plus expressifs, plus interprétables et plus efficaces pour des tâches combinatoires complexes.