PhD Position F/M Combinatorial Optimization with GNNs
Inria
Paris
PhD Position F/M Combinatorial Optimization with GNNs
Le descriptif de l’offre ci-dessous est en Anglais
Niveau de diplôme exigé : Bac + 5 ou équivalent
Fonction : Doctorant
A propos du centre ou de la direction fonctionnelle
The position is being posted on Inria's website, but the employer is ENS (Ecole Normale Supérieure).
Mission confiée
Combinatorial optimization (CO) is a field of computer science and mathematics with many significant applications in the real world. They consist of optimizing a specific cost function in a finite collection of objects, for example, a selection of edges to form a cycle in a graph. Many prominent CO problems (including max clique and traveling salesman problem) were classified in the NP class, posing them as computationally intractable for large instances. Since then, many improvements have been made to either finding optimal solutions, good heuristics, or approximate solutions.
However, in many practical situations, one often needs to solve problem instances that share particular characteristics or patterns. Hence, machine learning approaches could develop faster algorithms for practical cases by exploiting common patterns in the given instances. In this thesis, we will explore new methods by first studying three different CO problems: maximum clique, traveling salesman problem, and minimum bisection.
Very recently, geometric deep learning [1] emerged as an attempt for a geometric unification of a broad class of machine learning problems from the perspectives of symmetry and invariance. These principles not only underlie the breakthrough performance of convolutional neural networks and the recent success of graph neural networks but also provide a principled way to construct new types of problem-specific inductive biases.
We believe that geometric deep learning and the ideas around it in machine learning will have a much broader impact and could be used in CO. Indeed, we started investigating new architectures based on equivariant layers[2-3] and obtained results for combinatorial optimization problems: we showed that it is possible to learn representations for the input of hard (typically NP-hard) problems on which simple algorithms have state of the art performances while using much fewer resources. Such techniques open the way to new algorithms that can learn heuristics, which will be very efficient in practical instances.
**References**
– [1] [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://arxiv.org/abs/2104.13478)
Michael M. Bronstein, Joan Bruna, Taco Cohen, Petar Veličković
– [2] [How Powerful are Graph Neural Networks?](https://arxiv.org/abs/1810.00826)
Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka
– [3] [Attention Is All You Need](https://arxiv.org/abs/1706.03762)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, Illia Polosukhin
Principales activités
Rémunération
INRIA PhD students are paid €2082 gross/month (for the first two years of their thesis) and €2190 gross/month (for the third year of their thesis).