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 de travaux 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.
[1] L. Yang, C. Chatelain, and S. Adam. Dynamic graph representation learning with neural
networks: A survey. IEEE Access, 12:43460–43484, 2024.
[2] S.M. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and P. Poupart. Representation
learning for dynamic graphs: A survey. JMLR, 21(1):2648–2720, 2020.
[3] J. Skarding, B. Gabrys, and K. Musial. Foundations and Modeling of Dynamic Networks Using
Dynamic Graph Neural Networks: A Survey. IEEE Access, 9:79143–79168, 2021.
[4] C. DT Barros, M. RF Mendonca A. B Vieira, and A. Ziviani. A survey on embedding dynamic
graphs. ACM Computing Surveys (CSUR), 55(1):1–37, 2021.
[5] M. Balcilar, G. Renton, P. Héroux, B. Gaüz.re, S. Adam, and P. Honeine. Analyzing the
expressive power of graph neural networks in a spectral perspective. In ICLR, 2020.
[6] L. Yang, C. Chatelain, and S. Adam. Dspgnn: Bringing spectral design to discrete time
dynamic graph neural networks for edge regression. In TGL Workshop@ NeurIPS 2023.
[7] J. Piquenot, A. Moscatelli, M. Berar, P. Héroux, R. Raveaux, J-Y. Ramel, and S. Adam.
G2N2 : Weisfeiler and lehman go grammatical. ICLR, 2024.
[8] J. Piquenot, M. Berar, P. Heroux, R. Raveaux, JY Ramel, and S. Adam. Grammar
reinforcement learning: path and cycle counting in graphs with a CFG and transformer
approach. ICLR, 2025 (https://openreview.net/forum?id=yEox25xAED).
[9] AA Lehman and B. Weisfeiler. A reduction of a graph to a canonical form and an algebra arising
during this reduction. Nauchno-Technicheskaya Informatsiya, 2(9):12–16, 1968.
[10] C. Morris, M. Ritzert, M. Fey, W. L Hamilton, JE Lenssen, G. Rattan, and M. Grohe. Weisfeiler
and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
[11] C. Bodnar, F. Frasca, N. Otter, Y. Wang, P. Lio,G. F Montufar, and M. Bronstein. Weisfeiler
and lehman go cellular: Cw networks. NEURIPS, 34:2625–2640, 2021.
[12] C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. F Montufar, P. Lio, and M. Bronstein. Weisfeiler
and lehman go topological: Message passing simplicial networks. In ICML 2021.
[13] A. Moscatelli, J. Piquenot, M. Berar, P. Heroux, and S. Adam. Graph node matching for
edit distance. Pattern Recognition Letters, 184:14–20, 2024.
Projet détaillé
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 lacomplexité 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.
[14] Y. Yu, X. Si, C. Hu, and J. Zhang. A review of recurrent neural networks: Lstm cells and
network architectures. Neural computation, 31(7):1235–1270, 2019
[15] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel. Gatedgraph sequence neural networks,
2017.
[16] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N Gomez, L. Kaiser, and I.
Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017
[17] Y. Liu, S. Pan, Y. Guang Wang, F. Xiong, L. Wang, and V. C. S. Lee. Anomaly detection indynamic graphs via transformer.CoRR, abs/2106.09876, 2021.
[18] A. Gu and T. Dao. Mamba: Linear-time sequence modeling with selective state spaces.
arXivpreprintarXiv:2312.00752, 2023.
[19] A. Moscatelli, J. Piquenot, M. Bérar, P. Héroux, and S. Adam. Graph node
matching for edit distance. Pattern Recognition Letters, 184:14–20, 2024.
Les candidats intéressés par ce sujet doivent envoyer à Clement.Chatelain@insarouen.
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