L’apprentissage sur graphes a émergé ces dernières années comme une thématique majeure de la communauté de l'apprentissage automatique, avec pour objectif de profiter du pouvoir expressif et de la généricité des graphes pour modéliser des systèmes complexes, où les relations entre entités jouent un rôle crucial. Dans la littérature, une large majorité des contributions concerne les graphes statiques, pour lesquels la structure du graphe est fixée, tout comme les attributs des noeuds et des arcs. Or, dans de nombreux domaines, les entités et les relations décrites par le graphe évoluent au fil du temps, nécessitant une modélisation dynamique pour capturer non seulement la structure des graphes, mais aussi leur évolution temporelle. Cette nécessité a récemment donné lieu au développement des Dynamic Graph Neural Networks (DGNN), une extension des réseaux de neurones sur graphes statiques qui permet de tenir compte à la fois des dépendances temporelles et des dépendances structurelles. Les revues de littérature récentes [1,2,3,4] soulignent les très nombreuses applications de tels modèles : L’analyse des réseaux sociaux : dans les plateformes sociales, la dynamique des interactions (nouvelles connexions, échanges de messages) permet de détecter des communautés émergentes, d’identifier des influenceurs ou de prédire des événements viraux. La détection de fraudes et anomalies : dans les réseaux financiers, les transactions suspectes peuvent être détectées en étudiant les dynamiques des relations entre comptes. Les DGNN offrent un cadre robuste pour capturer ces anomalies. La biologie computationnelle : la modélisation des interactions dynamiques entre protéines ou cellules aide à comprendre les mécanismes biologiques sous-jacents, tels que les réponses immunitaires ou les mutations. Les réseaux de transport : les flux de trafic et les réseaux de transport évoluent constamment. Les DGNN permettent de prédire la congestion ou d’optimiser les réseaux en fonction de données dynamiques.
Dans le cadre de la thèse de Leshanshui Yang (CIFRE LITIS/SAAGIE), nous avons abordé cette problématique des réseaux de neurones sur graphes dynamiques. En bénéficiant de travaux antérieurs du laboratoire sur les graphes statiques [5], nous avons proposé le modèle Dynamic Spectral-Parsing Graph Neural Network (DSPGNN) [6] qui a permis l'obtention de meilleures performances dans des tâches de régression d'attributs d'arêtes, tout en optimisant la complexité de calcul sur des graphes dynamiques ayant un grand nombre de noeuds. Malgré ces progrès significatifs, la capacité des DGNN à capturer l’évolution temporelle reste encore limitée, notamment dans le cas de longues séquences. Dans ce cas, l’utilisation des transformers s’est révélée efficace pour la modélisation de graphes dynamiques [1], mais leur complexité quadratique par rapport à la taille de la séquence limite leur utilisation à certains contextes applicatifs particuliers.
Parallèlement à la thèse de Leshanshui Yang, la thèse de Jason Piquenot (ANR CodeGNN) a exploré des aspects théoriques de l'expressivité des réseaux de neurones sur graphes statiques [7,8]. Ces travaux s'appuient sur la hiérarchie des tests d'isomorphisme de Weisfeiler-Lehman (WL) [9], méthode la plus courante pour caractériser le pouvoir expressif des GNN. Au-delà de la caractérisation de l'expressivité des modèles, ces travaux ont également permis le développement de nouveaux modèles performants [10,11,12]. À notre connaissance, aucune étude similaire n'a été réalisée sur la catégorisation de l'expressivité des DGNN alors qu’elle pourrait permettre de faire progresser l’état de l’art.
L’apprentissage de métrique entre graphes statiques est également un sujet qui a émergé ces 5 dernières années. Pourtant, à l’image de la problématique précédente, très peu detravaux sont développés dans la littérature dans le cas des graphes dynamiques.
Ces travaux sont pourtant utiles quand il s’agit de mieux expliquer les résultats des algorithmes d’IA. Dans la continuité de la thèse d’Aldo Moscatelli (ANR HAISCODE) [13], ce sujet sera exploré dans le cadre de ce projet.
Cette thèse s’inscrit donc dans la continuité de 3 thèses qui seront soutenues d’ici novembre 2025 (une a été soutenue en décembre 24, une autre le sera en juin 25 et la dernière en novembre 25), en abordant 3 nouvelles questions de recherche liées aux graphes dynamiques. Les contributions scientifiques seront essentiellement de nature théorique et méthodologique, mais avec le souci de les appliquer sur des données des projets ANR OCTOPUSSY (chimie) et DYNATEAM (sciences du sport). Au niveau régional, le projet permettra de renforcer les synergies avec le laboratoire GREYC sur les thématiques d’apprentissage sur graphes issues notamment du projet ANR CodeGNN. Les collaborations avec le laboratoire de chimie COBRA ainsi qu’avec le CETAPS seront également enrichies grâce aux débouchés applicatifs de la thèse. Aux niveaux national et international, les contributions de cette thèse permettront de pérenniser la reconnaissance du LITIS pour ses contributions à l’apprentissage automatique sur graphes.
L'apprentissage sur graphe dynamique nécessite la conception de modèles capables de s'adapter à l'information structurelle des graphes mais aussi de capturer leur évolution temporelle. Concernant le second aspect, la plupart des modèles proposés dans la littérature sont basés sur l’utilisation de réseaux récurrents [14,15] ou sur les architectures de type transformers [16,17] qui ont fait le succès des LLMs. Une alternative à ces deux modèles de référence est apparue très récemment dans le domaine du traitement de séquences : les Structured State Space Models (SSM). Ces modèles réutilisent le concept ancien de modèle d'état et ont la propriété très importante de réduire la complexité combinatoire par rapport à la taille du signal d'entrée (O(n) pour les SSM
contre O(nÇ) pour les transformers). Il vont donc dans le sens d’une réduction des exigences de calculs, et donc d’une amélioration de l’impact écologique des modèles.
Dans une première étape de la thèse, à faible risque compte tenu des travaux existants au LITIS, nous explorerons l'utilisation de ce type de modèle et, plus particulièrement, de Mamba [18], dans la conception de nouveaux DGNNs .
À la suite de ces travaux, nous aborderons la thématique de la caractérisation de l’expressivité des réseaux de neurones appliqués aux graphes dynamiques, qui reste un sujet de recherche largement inexploré dans la littérature. Nous chercherons à établir une base théorique pour caractériser l’expressivité des DGNNs. En nous inspirant des résultats obtenus au LITIS en autre pour l’apprentissage sur graphes statiques, tels que la hiérarchie de Weisfeiler-Lehman, l’objectif sera de développer une hiérarchie adaptée aux graphes dynamiques, qui intègre à la fois les relations structurelles et temporelles. Cette hiérarchie permettra de comparer le pouvoir expressif des modèles existants, mais aussi d’en tirer des enseignements pour la conception de modèles plus expressifs, à l’image de ce qui a été proposé dans le domaine des graphes statiques.
Finalement, nous intégrerons les architectures expressives proposées dans les deux premières questions de recherche dans un contexte d'apprentissage de métriques entre graphes dynamiques. À notre connaissance, ce champ de recherche n'a pas encore été exploré, malgré un intérêt applicatif important en termes d'explicabilité des modèles. Ce travail s'appuiera sur les résultats récents obtenus dans le cadre de la thèse d'Aldo Moscatelli (2024), au travers d'architectures siamoises produisant des embeddings des graphes à comparer [19].
Outre les bases de données de la littérature, ces contributions seront appliquées et évaluées dans deux domaines applicatifs pour lesquels les graphes dynamiques constituent un formalisme adapté : la chimie et les sciences du sport.
● Chimie : Des discussions récentes avec le laboratoire de chimie rouennais COBRA dans le cadre du projet ANR Octopussy (https://anr.fr/Projet-ANR-24-
CE29-2570) ont fait émerger des applications potentiellement intéressantes des graphes dynamiques à des problèmes de chimie, généralement restreints à des graphes statiques. En effet, le mouvement des atomes composant les molécules dans l'espace influe sur les propriétés énergétiques des molécules. Cette évolution peut être capturée par des graphes dynamiques représentant des molécules dont les propriétés atomiques évoluent dans le temps, ainsi que les niveaux de liaison entre les atomes. La prise en compte de ces informations pourrait amener à l'amélioration des modèles prédictifs de réaction chimique. A notre connaissance, les réseaux de neurones sur graphes dynamiques n’ont pas encore été utilisés dans ce cadre.
● Sciences du sport : Nous exploiterons les données du projet ANR Dynateam (https://anr.fr/Projet-ANR-23-CE38-0008), qui cherche à analyser les dynamiques d'équipes au sein de sports collectifs tels que le basketball et le rugby. Dans ce cadre, les travaux menés sur les métriques entre graphes dynamiques seront particulièrement utiles pour comparer différentes stratégies d’équipes.
Les candidats intéressés par ce sujet doivent envoyer à
Clement.Chatelain@insa-rouen.fr, Sebastien.Adam@univ-rouen.fr, Benoit.Gauzere@insa-rouen.fr :
• CV
• Lettre de motivations
• Relevés de notes du Master (M1+M2) ou des deux dernières années d’école
d’ingénieur.
La date limite de candidature est fixée au 30/04/2025