论文标题
在图上进行组合优化的退火训练
Annealed Training for Combinatorial Optimization on Graphs
论文作者
论文摘要
组合优化（CO）问题的硬度阻碍收集用于监督学习的解决方案。但是，由于缺乏标记的数据，因此很难学习CO问题的神经网络，因为训练很容易被捕获到本地Optima。在这项工作中，我们为CO问题提出了一个简单但有效的退火培训框架。特别是，我们将CO问题转化为公正的基于能量的模型（EBM）。我们仔细选择了惩罚条款，以使EBM尽可能平滑。然后，我们训练图形神经网络以近似EBM。为了防止训练在初始化附近被卡在本地Optima上，我们引入了退火损失功能。实验评估表明，我们的退火训练框架可获得实质性改进。在四种类型的CO问题中，我们的方法在合成图和现实世界图上都比其他无监督神经方法更好地实现了性能。
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.
