Annonce

Les commentaires sont clos.

Stage M2 - Machine Learning Framework for Temporal Graph Exploration

6 December 2024

Catégorie : Stagiaire

Transportation systems with scheduled travels, like trains, flights, and buses, pose optimization challenges such as finding the fastest routes or maximizing stops within a time frame, which fall under the temporal graph exploration problem (TEXP). Despite its importance in fields like logistics and cybersecurity, TEXP's NP-hardness makes exact solutions infeasible for large graphs, and current approximation methods achieve limited success. Graph neural networks (GNNs) have proven to be an effective tool to approxiamte combinatorial problems in static graphs. This internship aims to build upon the success of GNNs explore the use of temporal GNNs as a means to tackle TEXP.

Transportation systems with scheduled travels, such as trains, flights, and buses, often require solving complex optimization questions like identifying the fastest itinerary to visit all destinations or maximizing the number of stops visited within a given time window. These problems fall under the umbrella of the temporal graph exploration problem (TEXP), which involves finding the quickest time-respecting walk in a temporal graph that visits all vertices. While TEXP has applications in logistics, cybersecurity, and fraud detection, its NP-hardness makes exact solutions impractical for large graphs.

Current approaches to TEXP focus on approximating solutions by exploring the solution space efficiently. Yet, such methods still achieve limited approximation ratios. Recent advances in graph neural networks (GNNs) suggest that these models, when adequately tuned, can represent combinatorial transformations effectively. While many works extend GNNs to temporal graphs, none have yet tackled TEXP.
This internship aims to address this gap by leveraging an unsupervised framework for combinatorial optimization to develop a custom loss function optimized for time-respecting walks. Additionally, the project will replace static GNNs with temporal graph neural networks, exploring architectures with temporal walk-based embedding modules to improve the inductive bias needed for TEXP.

This internship is directed at students with various backgrounds (computer science, data science, operations
research, complex systems) but with a strong interest in combinatorial optimization and graph machine learning.
To apply, please send an e-mail to esteban.bautista@univ-littoral.fr and rym.guibadj@univ-littoral.fr while attaching the
documents that can support your application:
• your resume;
• a cover letter;
• your transcripts from the last year of B.Sc to the last year of M.Sc. (if the latter is already available);
• two reference letters or the names and means of contact of two academic advisers.
Applications will be reviewed on a rolling basis until the position is filled.