Preference-Based Gradient Estimation for ML-Based Approximate Combinatorial Optimization
作者: Arman Mielke, Uwe Bauknecht, Thilo Strauss, Mathias Niepert
发布时间: 2025-02-27
来源: arxiv
研究方向: 组合优化（Combinatorial Optimization, CO）与机器学习结合的研究，特别是基于图神经网络（GNN）的近似算法改进。
主要内容
本文提出了一种数据驱动的方法，通过参数化现有的非学习型近似算法，并使用图神经网络（GNN）预测参数值，以改进组合优化问题的求解质量。该方法通过自监督的方式进行端到端训练，并引入了一种新的梯度估计方案——基于偏好的梯度估计（Preference-Based Gradient Estimation, PBGE）。该方法结合了GNN和传统近似算法的优势，能够在保证解可行性的同时，利用数据集中的信息找到更好的解。
主要贡献
1. 提出了一种自监督的GNN训练方法，用于组合优化问题。
2. 引入了一种新的梯度估计方案——基于偏好的梯度估计（PBGE），用于通过组合优化近似算法进行反向传播。
3. 在两个常见的组合优化问题（旅行商问题TSP和最小k割问题）上进行了广泛的实验验证，证明了该方法的有效性。
研究方法
1. 使用图神经网络（GNN）预测近似算法的参数值。
2. 通过自监督的方式进行端到端训练，使用梯度估计技术（如REINFORCE、I-MLE和PBGE）进行反向传播。
3. 提出了基于偏好的梯度估计（PBGE），通过对比更好和更差的解来估计梯度。
4. 在训练和测试阶段使用相同的管道，确保一致性。
实验结果
在最小k割问题和旅行商问题（TSP）上的实验结果表明，使用PBGE训练的GNN显著提高了近似算法的性能。在最小k割问题中，PBGE训练的GNN在最优性差距上比未使用GNN的Karger-Stein算法提高了近一个数量级。在TSP问题中，PBGE训练的GNN在最优性差距上也显著优于其他自监督方法，接近监督学习的性能。
未来工作
未来的工作可以集中在以下几个方面：1）减少训练过程中的计算开销；2）扩展该方法到其他类型的组合优化问题，特别是那些解不能仅通过图的边表示的问题；3）引入额外的约束条件，以处理更复杂的组合优化问题。