Annealed Training for Combinatorial Optimization on Graphs
This work addresses the problem of unsupervised learning for combinatorial optimization on graphs, which is incremental as it builds on existing energy-based models and graph neural networks.
The paper tackles the difficulty of training neural networks for combinatorial optimization problems due to lack of labeled data and local optima traps by proposing an annealed training framework, achieving substantial performance improvements over other unsupervised neural methods on synthetic and real-world graphs.
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 unbiased energy-based models (EBMs). We carefully selected the penalties terms so as to make the EBMs as smooth as possible. Then we train graph neural networks to approximate the EBMs. To prevent the training from being stuck at local optima near the initialization, we introduce 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.