Timezone: »

 
Annealed Training for Combinatorial Optimization on Graphs
Haoran Sun · Etash Guha · Hanjun Dai

@
in OPT 2022: Optimization for Machine Learning »
Event URL: https://openreview.net/forum?id=fo3b0XjTkU »

Learning neural networks for CO problems is notoriously difficult given the lack of labeled data as the training gets trapped easily at local optima. However, the hardness of combinatorial optimization (CO) problems hinders collecting solutions for supervised learning. We propose a simple but effective unsupervised annealed training framework for CO problems in this work. In particular, we transform CO problems into unbiased energy-based models (EBMs). We carefully selected the penalties terms to make the EBMs as smooth as possible. Then we train graph neural networks to approximate the EBMs and we introduce an annealed loss function to prevent the training from being stuck at local optima near the initialization.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.

Author Information

Haoran Sun (Georgia Institute of Technology)
Etash Guha (Georgia Institute of Technology)
Hanjun Dai (Google Brain)

More from the Same Authors