Combinatorial optimization (CO) problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality.
Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem.
The probabilistic proof of existence is then derandomized to
decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid
solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.
Nikolaos Karalias (EPFL)
Andreas Loukas (EPFL)
Researcher fascinated by graphs and machine learning.
Related Events (a corresponding poster, oral, or spotlight)
2020 Oral: Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs »
Thu. Dec 10th 02:15 -- 02:30 PM Room Orals & Spotlights: Graph/Relational/Theory
More from the Same Authors
2022 Poster: Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions »
Nikolaos Karalias · Joshua Robinson · Andreas Loukas · Stefanie Jegelka
2021 Poster: What training reveals about neural network complexity »
Andreas Loukas · Marinos Poiitis · Stefanie Jegelka
2021 Poster: SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning »
Mattia Atzeni · Jasmina Bogojeska · Andreas Loukas
2021 Poster: Partition and Code: learning how to compress graphs »
Giorgos Bouritsas · Andreas Loukas · Nikolaos Karalias · Michael Bronstein
2020 Poster: How hard is to distinguish graphs with graph neural networks? »
2020 Poster: Building powerful and equivariant graph neural networks with structural message-passing »
Clément Vignac · Andreas Loukas · Pascal Frossard