On the Effectiveness of Pretraining for Graph Combinatorial Optimization· 预训练在图组合优化中的有效性
This paper introduces a self-supervised pretraining framework for graph combinatorial optimization specifically designed to address the nature of routing problems like the Traveling Salesman Problem. By utilizing graph contrastive learning with geometric augmentations (specifically, rotations and axial reflections) the model is forced to learn invariant structural representations and global relative distance distributions. Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales. Notably, the hybrid strategy (combining rotation and reflection) achieved a 6.57% improvement in tour length for TSP1000, proving that geometric pretraining is an important inductive bias for effectively scaling neural solvers to high-dimensional instances.
研究预训练在图组合优化中的应用，特别是对旅行商问题的有效性。
- 核心方法
- 提出一种自监督预训练框架，利用几何增强（旋转和轴反射）的图对比学习，训练模型学习结构不变表示和全局相对距离分布。
- 适合谁读
- 研究者、工程师
- 要解决的问题
- 论文旨在解决图组合优化问题，特别是旅行商问题（TSP）等路由问题的高效求解。
- 关键实验
- 实验展示了在不同问题规模下，预训练模型均优于未预训练模型。关键实验在TSP1000上表现优异，通过混合策略（旋转和反射）实现了路径长度的显著改善。
- 主要贡献
- 证明了几何预训练能够显著提升模型在高维实例上的性能，尤其是TSP1000的求解路径长度改善了6.57%。
- 意义与局限
- 该研究为图组合优化问题提供了一种有效的预训练方法，显著提升了神经求解器在高维问题上的表现，但其效果在其他类型的图问题上的通用性仍有待验证。