Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
This addresses the challenge of solving combinatorial optimization problems for researchers and practitioners in fields like network analysis, offering a novel approach but with incremental improvements over existing methods.
The paper tackles combinatorial optimization on graphs without labeled data by proposing an unsupervised learning framework that provides integral solutions with certified quality, achieving competitive results on maximum clique and local graph clustering tasks on real and synthetic datasets.
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.