Dans cette thèse, nous étudierons les récents développements et applications de l’apprentissage par renforcement [7]  et l’apprentissage sur les graphes [3,4,5] aux problèmes combinatoires difficiles. Nous viserons principalement à exploiter les avantages de l’apprentissage par renforcement pour automatiser la recherche d’heuristiques en entraînant un agent de manière supervisée ou auto-supervisée pour résoudre des problèmes classiques de la théorie des graphes [2,6]. Nous nous intéresserons en premier lieu à des problèmes liés à la simplification de graphes comme la sparsification (i.e., dédensification) préservant certaines propriétés, pour laquelle il existe déjà des résultats pour des propriétés simples comme le calcul des plus courts chemins ou le page rank [8], l’agrégation de graphes [1], le clustering ou les communautés ainsi que l’approximation du calcul de la distance d’édition sur lesquels l’équipe encadrante possède une expertise forte.

Nous explorerons deux approches dans notre étude : (1) une approche à deux étapes, dans laquelle
on calcule d’abord des plongements de graphes indépendamment du problème d’optimisation visé et, (2) une approche en une seule étape (end-to-end) où le plongement constitue une étape intermédiaire dans le calcul de la solution et d´dépend du problème d’optimisation traité. Une comparaison de ces deux approches permettra de concevoir des méthodes de plongement de graphes plus adaptées. Une application possible de notre étude, est la planification dans les processus d´décisionnels de Markov avec les réseaux de neurones de graphes. Les processus de d´décision de Markov (MDP) sont des modèles mathématiques utilisés pour ´étudier les problèmes de prise de d´décision dans des situations où les résultats sont partiellement aléatoires et partiellement sous le contrôle d’un agent. Dans un MDP, le processus de prise de d´décision est modélisé comme un processus de contrôle stochastique à temps discret. Il se compose d’un ensemble d´états, d’actions, de probabilités de transition, de récompenses et d’un facteur de réduction. L’objectif d’un MDP est de trouver une politique, qui est une cartographie des états aux actions, qui maximise les récompenses cumulées attendues au fil du temps. Plusieurs problèmes en informatique, comme trouver le chemin le plus court dans un graphe, peuvent être formulés dans ce cadre simple. Par conséquent, les efforts les plus récents se concentrent plutôt sur l’apprentissage d’heuristiques rapides qui peuvent ˆêtre généralisées à de nouveaux problèmes et qui peuvent être utilisées pour accélérer les algorithmes de planification traditionnels. Dans cette optique, nous explorons d’abord l’utilisation d’outils récents d’apprentissage en profondeur tels que les réseaux convolutifs de graphes (GCN) et les réseaux de transformateurs de graphes (GTN) pour apprendre des fonctions heuristiques qui peuvent fournir des solutions approximatives au probl`eme de planification dans les MDP de manière efficace en temps.

Références
[1]     C. Cai, D.Wang, and Y.Wang. Graph coarsening with neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[2]     H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6351–6361, Red Hook, NY, USA, 2017. Curran Associates Inc.
[3]     P. Goyal and E. Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 151:78–94, 2018.
[4]     I. Oluigbo, M. Haddad, and H. Seba. Evaluating network embedding models for machine learning tasks. In H. Cherifi, S. Gaito, J. F. Mendes, E. Moro, and L. M. Rocha, editors, Complex Networks and Their Applications VIII - Volume 1 Proceedings of the Eighth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2019, Lisbon, Portugal, December 10-12, 2019, volume 881 of Studies in Computational Intelligence, pages 915–927. Springer, 2019.
[5]     I. Oluigbo, H. Seba, and M. Haddad. Improving node embedding by a compact neighborhood representation. Neural Comput. Appl., 35(9):7035–7048, 2023.
[6]     Y. Peng, B. Choi, and J. Xu. Graph learning for combinatorial optimization: A survey of state-of-theart. Data Science and Engineering, 6(2):119–141, Jun 2021.
[7]     R. S. Sutton and A. G. Barto. Reinforcement learning - an introduction. Adaptive computation and machine learning. MIT Press, 1998.
[8]     R. Wickman, X. Zhang, and W. Li. A generic graph sparsification framework using deep reinforcement learning. In X. Zhu, S. Ranka, M. T. Thai, T. Washio, and X. Wu, editors, IEEE International Conference on Data Mining, ICDM 2022, Orlando, FL, USA, November 28 - Dec. 1, 2022, pages 1221–1226. IEEE, 2022.