Offre en lien avec l’Action/le Réseau : – — –/– — –

Laboratoire/Entreprise : LISIC – ULCO
Durée : 6 mois
Contact : esteban.bautista-ruiz@lip6.fr
Date limite de publication : 2025-03-01

Contexte :
Dans les systèmes de transport avec trajets programmés (trains, avions, bus, etc.), des questions fondamentales se posent : existe-t-il un itinéraire permettant de visiter tous les arrêts ? Quel est le plus rapide ? Comment maximiser le nombre de lieux visités dans un temps limité ? Ces problématiques relèvent du Temporal Graph Exploration Problem (TEXP), qui consiste à trouver un chemin temporel permettant de visiter tous les sommets d’un graphe aussi vite que possible. Bien que crucial pour la logistique, la cybersécurité ou la détection de fraudes, le TEXP est un problème NP-difficile, ce qui rend le calcul de solutions exactes impraticable pour de grands graphes.

Des algorithmes heuristiques et d’approximation existent pour résoudre le TEXP, mais ils ont du mal à trouver un bon compromis entre vitesse et qualité des solutions. Les Graph Neural Networks (GNNs) se sont montrés efficaces pour résoudre des problèmes combinatoires sur des graphes statiques, et des versions plus récentes permettent maintenant de gérer les graphes temporels. Pourtant, ces outils n’ont pas encore été utilisés pour aborder le TEXP.

Sujet :
Nous visons à aborder le problème TEXP sous l’angle de l’apprentissage automatique en nous appuyant sur un cadre récent non supervisé pour l’optimisation combinatoire. Plus précisément, nous cherchons à (1) exploiter ce cadre pour concevoir une fonction de perte, basée sur la méthode probabiliste d’Erdős, qui optimise les parcours respectant les contraintes temporelles ; et (2) explorer des architectures récentes qui font l’embedding des parcours temporels, offrant un biais plus adapté au TEXP que les GNN classiques.

Profil du candidat :
Étudiants en informatique, science des données, recherche opérationnelle, ou systèmes complexes, ayant un fort intérêt pour l’optimisation combinatoire et l’apprentissage automatique sur graphes.

Formation et compétences requises :

Pour postuler, merci d’envoyer un e-mail à

– esteban.bautista@univ-littoral.fr
– rym.guibadj@univ-littoral.fr

en joignant les documents suivants pour appuyer votre candidature :

• votre CV ;
• une lettre de motivation ;
• vos relevés de notes de la dernière année de Licence à la dernière année de Master (si disponible) ;
• deux lettres de recommandation ou les noms et moyens de contact de deux conseillers académiques.

Les candidatures seront examinées au fur et à mesure jusqu’à ce que le poste soit pourvu.

Adresse d’emploi :
LISIC laboratory – St Omer site

Document attaché : 202412051118_Internship_ML-Temporal-Graph-Exploration.pdf