Thumbnail - Request a copy

Neural Maximum Independent Set

Pontoizeau, Thomas; Sikora, Florian; Yger, Florian; Cazenave, Tristan (2022), Neural Maximum Independent Set, Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Springer International Publishing : Berlin Heidelberg, p. 223–237. 10.1007/978-3-030-93736-2_18

Type
Communication / Conférence
Date
2022
Conference title
International Workshops of ECML PKDD 2021
Conference date
2021
Conference city
Virtual event
Conference country
SPAIN
Book title
Machine Learning and Principles and Practice of Knowledge Discovery in Databases
Publisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-93735-5
Pages
223–237
Publication identifier
Metadata
Show full item record
Author(s)
Pontoizeau, Thomas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian
Yger, Florian
Cazenave, Tristan
Abstract (EN)
The emergence of deep learning brought solutions to many difficult problems and has recently motivated new studies that try to solve hard combinatorial optimization problems with machine learning approaches. We propose a framework based on Expert Iteration, an imitation learning method that we apply to solve combinatorial optimization problems on graphs, in particular the Maximum Independent Set problem. Our method relies on training GNNs to recognize how to complete a solution, given a partial solution of the problem as an input. This paper emphasizes some interesting findings such as the introduction of learned nodes features helping the neural network to give relevant solutions. Moreover, we represent the space of good solutions and discuss the ability of GNN’s to solve the problem on a graph without training on it.