  Combinatorial optimization 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.
