Offre de thèse : réseaux de neurones sur graphes dynamiques : vers des modèles plus expressifs

Contexte du poste

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.

Description

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.

Fichiers associés

Fiche de poste
Comment postuler ?



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