Post #339

Erdős goes neural This is a post by Andreas Loukas about their recent work on solving combinatorial problems, accepted to NeurIPS 2020. There is great progress in combinatorial optimization (CO) problems with neural networks. Unsupervised learning (UL) is a particularly appealing direction as it aspires to avoid common drawbacks (computational cost, limited generalization) associated with the use of labeled instances. A major challenge in UL is to ensure that the discretized output respects CO constraints. Researchers have often tackled these problems by various ad-hoc heuristics that repair/improve upon the fractional solutions. Our paper proposes a principled approach to use UL GNNs for CO that ensures that constraints will be met without breaking differentiability. Our idea is to utilize the probabilistic method pioneered by Paul Erdős to bridge the gap between the discrete and continuous worlds. The probabilistic method. To prove the existence of an object with a property π one invents a distribution over possible objects. Showing that P(object has π)>0 is a certificate for the object's existence. For example, we can solve the maximum cut problem by using a fair coin toss to decide in which partition each node is placed. It is easy to show that, on average, half the edges of the graph will be cut, implying the existence of a 1/2-approximation for the maxcut problem. Erdős goes neural. We utilize the same procedure but learn the node probabilities with a GNN. To achieve this, we analytically construct a differentiable "probabilistic penalty loss" for the discrete problem. As shown, by minimizing the latter, the GNN provides a probabilistic certificate for the existence of a low cost and feasible solution. At inference time, discrete solutions of guaranteed cost are deterministically obtained with the method of conditional expectation. In practice. We demonstrated the efficacy of this approach on two NP-hard problems: the maximum clique problem and the constrained min-cut problem. In our experiments, our approach always yields feasible solutions and is competitive with neural baselines, MIP solvers, and heuristics. Future work. There are subtleties in our framework that need to be carefully addressed. On the theoretical front, it can be challenging to derive a probabilistic penalty loss for certain types of constraints (such as TSP). On the computational front, finding ways to accelerate our decoding module could significantly improve the running time during inference. TLDR: * We propose a differentiable way to solve CO problems with unsupervised GNNs. * In our approach, the neural network is learning a distribution of solutions. Successfully minimizing our loss provides a certificate of existence of low-cost feasible solutions in the learned distribution. * We obtain competitive results against neural baselines, heuristics, and solvers. blogpost: https://andreasloukas.blog/2020/10/31/erdos-goes-neural paper: https://rb.gy/uktdfa