EDISCO: 欧氏组合优化的等变离散扩散模型¶

会议: NeurIPS 2026
arXiv: 2610.04953
OpenReview: https://openreview.net/forum?id=wzGLCsImQ1
代码: https://github.com/ValleyC/EDISCO
领域: 优化/理论
关键词: 欧氏组合优化, 离散扩散模型, E(2)等变神经网络, 连续时间马尔可夫链, 旅行商问题与车辆路径问题

一句话总结¶

本文提出首个端到端具备精确 $E(2)$ 几何不变性生成分布的欧氏组合优化离散扩散模型 EDISCO，结合等变图神经网络、连续时间马尔可夫链多步后验采样与原生边扩展解码器，仅用基线 33%–50% 的训练数据即可刷新从 100 到 10000 规模 TSP/CVRP 的最前沿求解质量，并在空间与容量约束偏移下展现出极强的零样本泛化能力。

研究背景与动机¶

欧氏组合优化问题（Euclidean Combinatorial Optimization Problems, ECOPs）如旅行商问题（TSP）和带容量限制的车辆路径问题（CVRP），是组合优化与空间决策领域的基石基准。近年来，基于扩散模型（Diffusion Models）的非自回归生成方法显著缩小了与传统运筹求解器（如 Concorde、LKH-3、HGS-CVRP）之间的求解差距，将上千节点的近似求解相对误差压缩到 1% 以下。然而，现有神经求解器绝大多数仅在均匀分布的合成数据上过度拟合，一旦面对现实场景中常见的空间几何分布偏移（如聚类、聚集或爆炸分布）或约束严格度变化（如车辆载重极端紧张或宽松），求解质量和可行性往往出现断崖式崩溃。

造成这一脆弱性的核心矛盾在于：欧氏平面中的组合优化解（以节点索引表示的闭合回路或边指示矩阵）在二维欧氏群 $E(2)$（包含旋转、平移和镜像反射）变换下具有严格的几何不变性。也就是说，不管将城市坐标系如何整体平移或旋转，最优的连接拓扑结构完全一致。然而，现有的神经求解器（如 DIFUSCO、T2T、Fast-T2T、StruDiCO 等）大多依赖数据增强（Data Augmentation）或软对称正则化损失（如 Sym-NCO）来“近似”拟合几何对称性。这种基于有限采样的机制不仅浪费了大量模型容量去反复学习同一几何构型在不同坐标系下的重复表征，更无法在生成分布层面上保证严格的不变性。在扩散模型中，反向去噪过程若有一步破坏对称性，累积误差就会导致最终生成的边概率场和解码出的路径发生偏移。

为了彻底消除坐标系冗余并实现几何归纳偏置的最大化，本文的切入角度是：从模型架构底层构建严格的“轨道共享”（Orbit-Sharing），将问题直接投射到商流形（Quotient Manifold）上求解。核心 idea：构建首个从评分网络、连续时间马尔可夫链反向采样到可行域解码全流程保持精确 $E(2)$ 分布级不变性的离散扩散模型 EDISCO，使局部几何模式在商空间共享表征，以极少数据实现对极端空间几何偏移与约束漂移的稳健泛化。

方法详解¶

整体框架¶

EDISCO 专为欧氏空间中的边决策矩阵 $\mathbf{X} \in \{0,1\}^{n \times n}$ 设计，涵盖连续时间马尔可夫链（CTMC）正向加噪、基于 $E(n)$ 等变图神经网络（EGNN）的边评分网络、多步快速后验采样以及无须外部局部搜索的原生边扩展（NEE）解码器。

整个推理管线从均匀噪声或完全离散的先验边状态 $\mathbf{X}_{t_0}$ 开始，根据扩散时间反向迭代 $T$ 步。在每一步，等变评分网络在保持坐标协变更新的同时，输出关于真实未加噪边结构 $\mathbf{X}_0$ 的严格 $E(2)$ 不变边预测概率；随后，多步求解器利用 Adams-Bashforth 式预测平滑结合解析后验转移核完成降噪；最后，原生边扩展解码器读取边概率矩阵与欧氏成对距离，在保持拓扑约束（度数、子回路消除、车辆容量限制）的同时迭代构造可行解回路。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入节点坐标 {c_i} 与初始边状态 X_t"] --> B["E(2)等变图网络与不变标量消息传递<br/>坐标协变位移更新 + 边特征时间调制"]
    B --> C["连续时间离散扩散反向更新<br/>预测 x_0 边概率 + AB 预测平滑多步后验采样"]
    C -->|迭代反向去噪 T 步| D["反向终点边概率矩阵 P = p(X_0=1)"]
    D --> E["原生边扩展 (NEE) 拓扑约束解码<br/>并查集子回路消除 + CVRP 容量投影"]
    E --> F["输出全局严格可行的最优闭合回路"]

关键设计¶

1. 商空间几何约简与 E(2) 等变图网络：从底层消除坐标自由度 针对非等变模型在不同坐标视角下重复拟合导致的样本效率低下问题，EDISCO 确立了分布级 $E(2)$ 不变性理论（Proposition 1）。在满足常规位置（无重合、无三点共线）的点集配置 $\mathcal{X}_{\text{gp}} \subset \mathbb{R}^{2n}$ 上，欧氏群 $E(2)$（包含 2 维平移和 1 维旋转组成的 3 维李群连续自由度）的作用是自由且真（free and proper）的。因此，商空间 $\mathcal{X}_{\text{gp}}/E(2)$ 是一个光滑流形，维度严格为 $2n-3$。任何 $E(2)$ 不变函数 $F$ 均可唯一分解为商空间上的函数 $\widetilde{F}$ 与标准投影 $\pi$ 的复合：$F = \widetilde{F} \circ \pi$。学习目标从而从 $\mathbb{R}^{2n}$ 直接压缩到 $2n-3$ 维的商流形，大幅降低了函数假设空间。

为了在网络结构中内嵌该性质，EDISCO 采用 12 层 $E(n)$ 等变图神经网络（EGNN），维护等变坐标 $\mathbf{x}_i^{(\ell)}$、不变节点特征 $\mathbf{h}_i^{(\ell)}$ 与不变边特征 $\mathbf{e}_{ij}^{(\ell)}$。成对消息计算仅依赖旋转平移不变的相对距离标量： $$\mathbf{m}_{ij}^{(\ell)} = \text{MLP}_m([\mathbf{h}_i^{(\ell)}, \mathbf{h}_j^{(\ell)}, \mathbf{e}_{ij}^{(\ell)}, \|\mathbf{x}_i^{(\ell)} - \mathbf{x}_j^{(\ell)}\|_2])$$ 而坐标更新则严格限制于标量加权的相对位移向量场： $$\Delta \mathbf{x}_i = \alpha \sum_{j \neq i} w_{ij} \cdot \frac{\mathbf{x}_j^{(\ell)} - \mathbf{x}_i^{(\ell)}}{\|\mathbf{x}_j^{(\ell)} - \mathbf{x}_i^{(\ell)}\|_2 + \epsilon}, \quad w_{ij} = \tanh(\text{MLP}_c(\mathbf{m}_{ij}^{(\ell)})/\tau)$$ 其中 $\alpha=0.1$，$\tau=10$。当输入坐标经过任意刚体变换 $g \cdot \mathbf{c} = R\mathbf{c} + \mathbf{t}$ 时，差分向量中平移项抵消，旋转矩阵 $R \in O(2)$ 可完全提取到加权求和外侧，使得坐标更新严格协变：$\Delta (g \cdot \mathbf{x}_i) = R \cdot \Delta \mathbf{x}_i$。由于输出预测头仅读取不变边状态，全网输出的边选择概率在整个 $E(2)$ 轨道上严格相等（Corollary 2），最大概率偏差达到机器浮点精度底限（$1.2 \times 10^{-7}$）。

2. 连续时间分类马尔可夫链 (CTMC) 扩散与多步解析采样：灵活平衡精度与速度 针对离散组合边变量松弛为连续高斯变量时带来的分布失真与无效边冗余，EDISCO 直接在离散二值边空间 $\{0,1\}$ 上建立分类连续时间马尔可夫链。正向加噪过程的瞬时转移速率矩阵定义为 $\mathbf{Q}(t) = \beta(t)(\mathbf{1}\mathbf{1}^T - K\mathbf{I})$（对于二值边 $K=2$），采用线性加噪策略 $\beta(t) = \beta_{\min} + t(\beta_{\max} - \beta_{\min})$（$\beta_{\min}=0.1, \beta_{\max}=1.5$）。该过程满足 Kolmogorov 前向微分方程，具有解析闭式转移概率： $$P(X_{t,ij}=b \mid X_{0,ij}=a) = \frac{1}{2} + \left(\delta_{ab} - \frac{1}{2}\right) \exp\left(-2 \int_0^t \beta(u)du\right)$$ 这允许训练时在任意时间步 $t \in [0,1]$ 单步瞬时采样加噪状态 $\mathbf{X}_t$，无须模拟中间连续跳跃。

在反向推理时，为了在不重新训练的前提下灵活调整采样速度，EDISCO 将高阶常微分数值求解器（如 PNDM、DEIS-2）推广到离散分类空间。评分网络采用稳定的 $\mathbf{x}_0$ 参数化预测 clean 边概率 $\hat{\mathbf{X}}_0$；随后利用 Adams-Bashforth 式多步平滑融合历史预测信息得到 $\tilde{p}$；最终基于贝叶斯定理的严格一步后验概率核进行独立边状态转移： $$q(x_{s,ij} \mid x_{t,ij}, \tilde{p}_{ij}) = \sum_{x_0 \in \{0,1\}} \frac{P(x_{t,ij} \mid x_{s,ij}) P(x_{s,ij} \mid x_0)}{P(x_{t,ij} \mid x_0)} \tilde{p}_{ij}(x_0 \mid x_{t,ij}) \quad (s < t)$$ 这种设计将计算密集的多步扩散压缩到仅需 5 步即可完成，同时精准保持分类概率流的几何对称性。

3. 原生边扩展 (NEE) 拓扑解码与容量特征调制：无需后处理的端到端保对称闭环 许多扩散模型输出的边概率矩阵需要依赖繁重且打破理论对称保证的外部启发式搜索（如多轮 2-opt、Beam Search、LKH）。EDISCO 提出了原生边扩展解码器（NEE），仅读取几何距离与边生成概率构建综合排序评分： $$r_{ij} = \frac{P_{ij} + P_{ji}}{2(d_{ij} + \epsilon)}$$ 随后以贪心方式依次将最高分边加入候选集，并通过动态维护节点度数（各节点度数不超过 2）与基于并查集（Union-Find）的连通分量判断，严格杜绝提前闭合子回路，仅在最后一步闭合哈密顿回路。

针对更复杂的 CVRP 约束，EDISCO 将容量比率 $\lambda = Q/Q_{\text{default}}$、局部需求比 $d_i/Q$ 及全局总负荷通过轻量级 MLP 编码为不变容量嵌入向量 $\mathbf{z}_c$，并通过特征仿射调制（FiLM）作用于消息传递层： $$\tilde{\mathbf{m}}_{ij}^{(\ell)} = \boldsymbol{\gamma}_\ell(\mathbf{z}_c) \odot \mathbf{m}_{ij}^{(\ell)} + \boldsymbol{\beta}_\ell(\mathbf{z}_c)$$ 在 NEE 解码过程中，系统维护当前各条车辆路径的累积载荷，一旦加入候选边会导致路径载荷超标，则立即拒绝该边并触发车辆向车场（Depot）闭合回程。由于 NEE 的所有输入标量、排序规则以及并查集可行性判断均不受坐标刚体变换影响，整个解码过程输出的节点索引排列严格保持 $E(2)$ 不变性。

损失函数 / 训练策略¶

模型采用有监督学习范式，目标直接对齐真实解（来自 Concorde、LKH-3 或 HGS-CVRP 的邻接矩阵 $\mathbf{X}_0$）。为了提升反向扩散在低噪声重建关键期的预测精度，训练损失采用信噪比（Min-SNR）加权的二元交叉熵： $$\mathcal{L} = (1 - \sqrt{t}) \cdot \text{CE}(s_\theta(\mathbf{X}_t, t, \{\mathbf{c}_i\}, \mathbf{z}_c), \mathbf{X}_0)$$ 权重系数 $(1 - \sqrt{t})$ 在 $t \to 0$ 时逼近 1，优先惩罚低噪声阶段的边分类误差。优化器使用 AdamW，在大规模图（$N \ge 500$）上采用 $k$ 近邻图（$k=50$ 或 $100$）进行空间稀疏化，显存占用由 $O(n^2)$ 骤降至 $O(kn)$，使得单张 48GB A6000 显卡即可直接支持 10000 节点超大规模 TSP 模型的端到端训练与推理。

实验关键数据¶

主实验¶

在标准 TSP 基准上，与运筹求解器及现代主流神经/扩散模型对比（Gap 相对于 Concorde 或 LKH-3，单线程 batch size=1 测速）。EDISCO 采用 5 步 DEIS-2 结合 NEE 解码。

数据集	指标	EDISCO (本文)	StruDiCO	GenSCO	NEXCO	Concorde / LKH-3
TSP-100	路径长度 / Gap / 耗时	7.76 / 0.000% / 0.075s	7.76 / 0.024% / 0.083s	7.76 / 0.000% / 0.50s	7.76 / 0.03% / 0.08s	7.76 / 0.00% / 0.23s
TSP-500	路径长度 / Gap / 耗时	16.55 / 0.018% / 0.28s	16.60 / 0.326% / 0.674s	16.55 / 0.023% / 1.10s	16.59 / 0.28% / 0.33s	16.55 / 0.00% / 4.64s
TSP-1000	路径长度 / Gap / 耗时	23.24 / 0.52% / 1.28s	23.24 / 0.535% / 2.614s	23.25 / 0.559% / 3.50s	23.26 / 0.63% / 1.31s	23.12 / 0.00% / 17.54s
CVRP-50	路径长度 / Gap / 耗时	10.40 / 0.29% / 0.06s	10.41 / 0.39% / 0.5s	– / – / –	10.48 / 1.12% / 0.08s	10.37 / 0.00% / 1.01s
CVRP-100	路径长度 / Gap / 耗时	15.60 / 0.26% / 0.10s	15.61 / 0.32% / 1.5s	– / – / –	15.78 / 1.40% / 0.12s	15.56 / 0.00% / 20.03s
CVRP-500	路径长度 / Gap / 耗时	37.78 / 1.70% / 0.50s	– / – / –	– / – / –	– / – / –	37.15 / 0.00% / 240s

消融实验¶

在 TSP-500 和 TSP-1000 上验证编码器对称性设计与解码器选择的贡献（固定 5 步 DEIS-2 求解器）：

配置模块	变量细节	TSP-500 Gap / 耗时	TSP-1000 Gap / 耗时	说明
EDISCO (Full 编码器)	架构内嵌 $E(2)$ 等变	2.10% / 0.11s	3.05% / 0.31s	贪心解码基线（验证编码器纯能力）
非等变 GNN (参数对齐)	无对称性归纳偏置	5.95% / 0.12s	7.85% / 0.32s	误差急剧扩大近 3 倍
+ $E(2)$ 数据增强	训练期随机旋转平移	4.10% / 0.12s	5.45% / 0.32s	仅能弥补约一半的对称性损失
+ Sym-NCO 软等变损失	对称性正则化约束	4.85% / 0.12s	6.55% / 0.32s	软惩罚无法替代结构内嵌等变性
NEE 解码器 (本文)	原生边扩展 (式 13)	0.018% / 0.28s	0.52% / 1.28s	编码器固定为 EDISCO，替代外部局部搜索
贪心解码 (Greedy)	仅度数与子回路判定	2.10% / 0.11s	3.05% / 0.31s	缺乏距离惩罚的原始贪心抽取
贪心 + 2-opt 局部搜索	传统局部重排后处理	0.18% / 0.19s	0.52% / 0.37s	NEE 在中大规模上完全超越 2-opt 质量

关键发现¶

分布外泛化压倒性胜出：在经典的 TSP-100 跨分布泛化评估中（训练于 Uniform，测试于 Cluster、Explosion、Implosion），传统扩散模型与非等变基线在 OOD 下的相对劣化幅度高达 133%（DIFUSCO）、687%（T2T）甚至 1961%（Fast-T2T），而 EDISCO 的平均劣化率仅为 4%，其跨分布平均 Gap 仅 0.04%，证实了商流形学习直接锁定了欧氏局域几何拓扑，不受坐标分布变形的干扰。
样本效率倍增：由于 $E(2)$ 商流形将问题参数化空间削减了 3 个连续自由度，EDISCO 仅需竞争对手 33%–50% 的训练样本量即可收敛至更优解（如 TSP-50/100 仅需 500K 样本，而 DIFUSCO/T2T 需 1500K；TSP-10000 仅需 3K 样本即可达到 1.98% Gap，完胜 DIFUSCO 用 6.4K 样本达到的 8.95%）。
约束漂移稳健性：在 CVRP-100 容量跨度测试（$Q \in [10, 500]$）中，固定 $Q=50$ 训练的基线在极端容量下 Gap 飙升至 5%–7%，而结合 FiLM 容量调制的 EDISCO 跨越整个超大范围保持在 0.26%–0.78% 的平稳区间，几乎逼近为各容量单独训练专有模型的理论性能上限。

亮点与洞察¶

严格构造的分布级不变性：不同于绝大多数工作仅在“预测结果”或“数据采样”上尝试引入对称性，EDISCO 从网络层、连续时间马尔可夫链转移核到解码可行域，端到端构造了无缝闭环的 $E(2)$ 轨道不变分布，旋转测试下边概率浮点偏差仅 $1.2 \times 10^{-7}$。
商空间降维与样本复用：从几何深度学习视角将坐标输入精确降维至 $(2n-3)$ 维商流形，揭示了对称性内嵌不仅是“数据增强的替代品”，更是从根本上降低了组合优化函数假设空间的拓扑复杂度。
即插即用的离散连续时间采样器：成功将常用于连续扩散模型的 Adams-Bashforth 平滑多步 ODE 求解技巧迁移至离散分类后验转移核，打破了离散扩散求解步数多、推理慢的桎梏，仅用 5 步即达到 SOTA 解质量。

局限与展望¶

适用几何范围的边界：本文严格的 $E(2)$ 等变保证深度绑定于二维欧氏度量平面。对于非欧氏图优化（如非对称 TSP、非欧氏网络延迟、有向容量流等），由于不存在标准刚体群的作用，无法直接享受该几何归纳偏置（附录中 MIS 实验必须回退为非等变普通 GNN）。
超参数敏感度：等变网络中的坐标位移步长 $\alpha$ 对训练稳定性高度敏感（$\alpha \ge 0.2$ 时即出现坐标坍塌与发散），需依赖严格校准的固定超参数（$\alpha=0.1, \tau=10$）。
未来方向：探索结合 Finsler 多维缩放等度量学习方法，将现实中的非对称路网投影到带对称流形的嵌入空间，进而将等变离散扩散推广到工业级高维非欧交通调度系统。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出欧氏组合优化中分布级严格 $E(2)$ 不变的离散扩散理论与全流程实现。
实验充分度: ⭐⭐⭐⭐⭐ 跨越 TSP-100 到 10000、CVRP-50 到 2000、ESTP 与非欧 MIS，含严密的 OOD 泛化、噪声策略与超参消融。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严密自洽，商流形降维理论与算法架构图景阐述极其清晰。
价值: ⭐⭐⭐⭐⭐ 为学习型组合优化指明了从“基准小幅刷榜”走向“真实世界几何分布泛化”的关键路径。

配置模块	变量细节	TSP-500 Gap / 耗时	TSP-1000 Gap / 耗时	说明
EDISCO (Full 编码器)	架构内嵌 \(E(2)\) 等变	2.10% / 0.11s	3.05% / 0.31s	贪心解码基线（验证编码器纯能力）
非等变 GNN (参数对齐)	无对称性归纳偏置	5.95% / 0.12s	7.85% / 0.32s	误差急剧扩大近 3 倍
+ \(E(2)\) 数据增强	训练期随机旋转平移	4.10% / 0.12s	5.45% / 0.32s	仅能弥补约一半的对称性损失
+ Sym-NCO 软等变损失	对称性正则化约束	4.85% / 0.12s	6.55% / 0.32s	软惩罚无法替代结构内嵌等变性
NEE 解码器 (本文)	原生边扩展 (式 13)	0.018% / 0.28s	0.52% / 1.28s	编码器固定为 EDISCO，替代外部局部搜索
贪心解码 (Greedy)	仅度数与子回路判定	2.10% / 0.11s	3.05% / 0.31s	缺乏距离惩罚的原始贪心抽取
贪心 + 2-opt 局部搜索	传统局部重排后处理	0.18% / 0.19s	0.52% / 0.37s	NEE 在中大规模上完全超越 2-opt 质量