Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching

📄 arXiv: 2605.30920v1 📥 PDF

作者: Shengyu Feng, Tarun Suresh, Yiming Yang

分类: cs.LG

发布日期: 2026-05-29

备注: ICML26

🔗 代码/项目: GITHUB

💡 一句话要点

提出组合邻接匹配(CAM)，用于无监督求解组合优化问题的扩散模型。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 组合优化 扩散模型 无监督学习 伴随方法 随机控制

📋 核心要点

  1. 现有基于扩散模型的组合优化方法依赖于大量近优解的监督训练，成本高昂且泛化性受限。
  2. 提出组合邻接匹配(CAM)框架，将离散组合优化问题建模为随机控制问题，利用离散伴随动态传播优化信号。
  3. 实验结果表明，CAM在无监督条件下优于现有基线，性能可与监督模型和传统求解器竞争。

📝 摘要（中文）

基于扩散的神经求解器在组合优化（CO）方面表现出强大的潜力，但现有方法通常依赖于使用大量接近最优解的监督训练。本文将基于伴随的轨迹优化方法扩展到离散组合域。我们将基于扩散的CO问题建模为连续时间马尔可夫链上的随机控制问题，并引入离散伴随动态，用于在离散生成轨迹中传播优化信号。在此基础上，我们提出组合邻接匹配（CAM），这是一个用于离散扩散求解器的无监督训练框架，具有结构化和低方差的轨迹级优化信号。实验表明，CAM始终优于现有的无监督扩散基线，并在各种组合优化问题中实现了与强大的监督扩散求解器甚至传统求解器相媲美的性能。代码可在https://github.com/Shengyu-Feng/CAM获取。

🔬 方法详解

问题定义：论文旨在解决组合优化问题，现有基于扩散模型的求解器通常需要大量带标签的近优解进行监督训练，这限制了它们在实际应用中的可行性，因为获取这些高质量的标签数据成本很高。因此，如何在无监督的条件下训练扩散模型，使其能够有效地解决组合优化问题，是本文要解决的核心问题。

核心思路：论文的核心思路是将组合优化问题视为一个连续时间马尔可夫链上的随机控制问题，并利用伴随方法来估计目标函数关于扩散过程的梯度。通过引入离散伴随动态，可以在离散的生成轨迹中有效地传播优化信号，从而实现对扩散模型的无监督训练。这种方法避免了对大量标签数据的依赖，并且能够利用轨迹级别的优化信号来指导模型的学习。

技术框架：CAM框架主要包含以下几个阶段：1) 前向扩散过程：将离散的组合优化问题的解逐步扩散到噪声状态。2) 反向生成过程：从噪声状态逐步生成组合优化问题的解。3) 伴随动态计算：利用离散伴随动态计算目标函数关于生成轨迹的梯度。4) 模型更新：利用计算得到的梯度更新扩散模型的参数。整个框架通过最小化目标函数来学习生成高质量的组合优化解。

关键创新：CAM的关键创新在于提出了组合邻接匹配（Combinatorial Adjoint Matching）方法，这是一种用于离散扩散求解器的无监督训练框架。与传统的监督学习方法不同，CAM不需要任何标签数据，而是通过利用离散伴随动态来估计目标函数关于生成轨迹的梯度，从而实现对扩散模型的无监督训练。这种方法能够有效地利用轨迹级别的优化信号，并且具有较低的方差，从而提高了训练的效率和稳定性。

关键设计：CAM的关键设计包括：1) 离散伴随动态的定义：论文提出了适用于离散组合优化问题的伴随动态计算方法，用于在离散的生成轨迹中传播优化信号。2) 损失函数的设计：论文设计了基于轨迹级别的损失函数，用于指导扩散模型的学习。3) 网络结构的选择：论文使用了合适的神经网络结构来建模扩散过程，例如Transformer网络或图神经网络。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，CAM在各种组合优化问题上均优于现有的无监督扩散基线。例如，在旅行商问题上，CAM的性能与强大的监督扩散求解器和传统求解器相媲美。此外，CAM还具有较低的方差，从而提高了训练的效率和稳定性。代码已开源，方便研究人员进行复现和进一步研究。

🎯 应用场景

该研究成果可应用于各种组合优化问题，如旅行商问题、车辆路径问题、图着色问题等。在实际应用中，可以利用该方法在没有大量标签数据的情况下训练出高效的组合优化求解器，从而降低成本并提高效率。此外，该方法还可以应用于其他离散优化问题，例如自然语言处理中的序列生成和图像处理中的图像分割。

📄 摘要（原文）

Diffusion-based neural solvers have shown strong promise for combinatorial optimization (CO), but existing methods typically rely on supervised training with large collections of near-optimal solutions. In this work, we extend adjoint-based trajectory optimization methods to discrete combinatorial domains. We formulate diffusion-based CO as a stochastic control problem over Continuous-Time Markov Chains and introduce discrete adjoint dynamics for propagating optimization signals through discrete generative trajectories. Building on this formulation, we propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion solvers with structured and low-variance trajectory-level optimization signals. Empirically, CAM consistently outperforms existing unsupervised diffusion baselines and achieves performance competitive with strong supervised diffusion solvers and even traditional solvers across diverse combinatorial optimization problems. Our code is available at https://github.com/Shengyu-Feng/CAM.