Tuesday, April 6, 2021 1:00 pm
-
2:30 pm
EDT (GMT -04:00)
Abstract: Combinatorial optimization (CO) problems are notoriously challenging for neural networks, especially in the absence of labelled 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.
Speaker Bio:
Andreas Loukas is a research scientist at the LTS2 lab in EPFL, Switzerland. Previously, he has spent time at TU Berlin, Ben Gurion, and TU Delft. His research focuses on the foundations and applications of graph methods in machine learning and data science. Andreas aims to find elegant explanations for phenomena associated with learning and to exploit them in order to design specialized learning machines. He is also interested in graph problems in signal processing and theoretical computer science, as well as in the analysis of neural networks.
https://andreasloukas.blog/
Recording: https://www.youtube.com/watch?v=kivJQYPKrZE