Title: Annealed Training for Combinatorial Optimization on Graphs. Abstract: The hardness of combinatorial optimization (CO) problems hinders collecting solutions for supervised learning. However, learning neural networks for CO problems is notoriously difficult in lack of the labeled data as the training is easily trapped at local optima. In this work, we propose a simple but effective annealed training framework for CO problems. In particular, we transform CO problems into the smoothest unbiased energy-based models (EBMs) by adding carefully selected penalties, then train graph neural networks to approximate the EBMs. We prevent the training from being stuck at local optima near the initialization by introducing an annealed loss function.
An experimental evaluation demonstrates that our annealed training framework obtains substantial improvements. In four types of CO problems, our method achieves performance substantially better than other unsupervised neural methods on both synthetic and real-world graphs.