💻 computer science

AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

本文介绍了各向异性图扩散网络（Anisotropic Graph Diffusion Network, AGDN），这是一种新型图神经网络框架，通过利用 MixScore 转移矩阵和各向异性扩散策略，解决了旅行商问题图中拓扑先验和节点丢失带来的挑战，从而实现了比现有方法更优越的性能和泛化能力。

原作者： Bolin Shen, Ziwei Huang, Zhiguang Cao, Yushun Dong

发布于 2026-06-19

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Bolin Shen, Ziwei Huang, Zhiguang Cao, Yushun Dong

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名快递员，手里拿着一张包含 100 个城市的地图。你的目标是访问每一个城市且仅访问一次，最后回到起点，但你希望行驶的总距离绝对最短。这就是旅行商问题 (Traveling Salesman Problem, TSP)。这听起来很简单，但随着城市数量的增加，可能的路线数量会呈爆炸式增长，以至于即使是超级计算机也难以快速找到完美答案。

最近，科学家们尝试通过图神经网络 (Graph Neural Networks, GNNs) 来教计算机解决这个问题。把 GNN 想象成一个试图通过观察城市间的连接来学习地图的学生。然而，这篇论文指出，目前的“学生”犯了两个大错误：

他们在盯着一张空白地图： 计算机看到的是所有城市都相互连接（一个“全连接”图），这就像是在盯着一面充满静态噪声的墙壁。它并不知道哪些连接才是重要的。
他们在把地图切碎： 为了降低难度，目前的方法经常将地图切成更小的碎片（稀疏化）。论文认为，这就像是把拼图拆开，然后扔掉了那些真正能把画面连接起来的碎片。如果计算机切断了一个属于“完美路径”的一部分连接，它就永远无法找到解。

解决方案：AGDN（智能导航员）

作者提出了一种名为 AGDN（各向异性图扩散网络，Anisotropic Graph Diffusion Network）的新框架。它是如何工作的，我们可以用简单的类比来说明：

1. “MixScore” 地图（给学生一个更好的引导）

AGDN 并没有让计算机盯着一堆杂乱的连接，而是创建了一个特殊的指南，叫做 MixScore。

类比： 想象你在猜测哪些城市是邻居。旧方法只是观察原始距离。而 AGDN 不仅观察距离，还会观察城市之间的“感觉”（即它们的特征或属性）。
作用： 它创建了一个转换图，告诉计算机：“嘿，这两个城市不仅距离近，而且它们的特征也表明它们应该被连接在一起。”这给了计算机一个聪明的起点（一种“拓扑先验”），而不是让它在黑暗中盲目猜测。

2. “双向车道”系统（各向异性扩散）

这是核心创新点。在普通的地图中，信息流向是单向的，或者容易陷入停滞。AGDN 使用了各向异性 (Anisotropic) 的方法。

类比： 想象信息在城市中流动。旧方法把交通处理成单行道，或者像是一个拥挤的环岛，导致每个人都感到混乱（过度平滑/over-smoothing）。
AGDN 的技巧： 它将交通流分为两个截然不同的车道：入向（S 空间）和出向（D 空间）。
- 一个车道负责倾听城市“从哪里来”。
- 另一个车道负责倾听城市“要到哪里去”。
为什么重要： 通过将这些方向分开处理但又保持沟通，计算机可以更好地理解复杂的路径。这就像是有一个专门负责“到达”的团队和一个专门负责“出发”的团队，他们能够完美地共享笔记，而不是所有人都在一个房间里大声喧哗。

3. “多跳”望远镜

有时候，最佳路径连接的两个城市并不相邻；它们可能通过三四个其他城市连接在一起。

类比： 旧方法就像是通过一根短吸管在看，只能看到紧邻的邻居。
AGDN 的技巧： 它使用了一个“多跳注意力 (Multi-hop Attention)”望远镜。它可以在单次注视中瞬间看到 5、10 甚至 20 个城市之外的情况，而不需要叠加更多的透镜层（因为叠加透镜通常会让图像变得模糊）。这使得它能够捕捉到其他方法会错过的完美长距离连接。

结果：更快、更聪明

作者在包含 200、500 甚至 1,000 个城市的地图上测试了 AGDN。

准确度： 它找到的路径比测试过的任何其他方法都更接近完美答案，包括那些需要运行数小时的方法。
速度： 它非常快。当竞争对手需要花费数分钟或数小时来计算路径时，AGDN 仅需几秒钟即可完成。
泛化能力： 最令人印象深刻的部分是：他们用 100 个城市的地图训练了计算机，而它成功解决了从未见过的 1,000 个城市的地图。它在奇特的聚类地图以及来自著名的 TSPLIB（一个收集真实世界路由问题的集合）的真实数据上也表现出色。

总结

简而言之，AGDN 是一种教计算机解决旅行商问题的新方法。它不再切碎地图或被噪声干扰，而是构建了一个智能的双向指南，让计算机能够“预见”长远，并理解行驶的方向。其结果是，该系统能更快地找到更好的路径，并且能处理比以前规模大得多的问题。

技术摘要：AGDN —— 基于各向异性图扩散网络学习求解旅行商问题

问题定义
旅行商问题（Traveling Salesman Problem, TSP）是一个基础的组合优化问题，其目标是找到一条访问一组城市且仅访问一次，并返回起点的最短路径。虽然图神经网络（GNNs）因其与 TSP 拓扑搜索空间的对齐而成为有效的工具，但目前的基于学习的方法面临两个关键局限性：

缺乏信息丰富的拓扑先验： 与标准的图学习任务不同，TSP 实例通常被建模为全连接图。这种结构缺乏关于最优解的内在拓扑先验，使得模型难以从噪声中区分出与解相关的有效信息。
通过稀疏化导致的信息交换丢失： 为了管理计算复杂度，现有方法通常会对 TSP 图进行稀疏化处理（例如使用 $k$ -NN）。然而，这一过程存在移除属于最优解之边的风险。当最优节点对被断开连接时，浅层 GNN 难以捕捉必要的跳数（multi-hop）关系，而深层 GNN 则会遭受过度平滑（over-smoothing）和过度挤压（over-squashing）的问题。

方法论：各向异性图扩散网络 (AGDN)
作者提出了 AGDN，一个旨在不依赖图稀疏化来解决 TSP 的框架。该方法由四个核心组件组成：

MixScore 转移矩阵：
AGDN 没有使用标准的邻接矩阵或简单的基于距离的转移，而是构建了一个 MixScore 转移矩阵。该矩阵整合了两类信息：
- 成对距离： 通过高斯核（ $\exp(-e_{ij}/\sigma)$ ）进行编码，以捕捉几何邻近性。
- 节点相似度： 源自两个不同潜在空间中的节点嵌入：源空间（Source, $S$ ）和目标空间（Destination, $D$ ）。
  该矩阵通过将来自这两个空间的内积（ $H_S H_D^T$ ）与归一化的距离矩阵（ $T_{rw}$ ）进行拼接，并经过多层感知机（MLP）处理来构建。这使得模型能够编码出既反映几何距离又反映学习到的结构相似性的转移概率。
各向异性图扩散：
AGDN 采用了一种扩散机制，分别在传入方向（ $S$ ）和传出方向（ $D$ ）传播信息。
- 多跳注意力机制： 该框架利用一种可学习的多跳注意力机制（由 $\theta_k$ 参数化），在单个卷积层内聚合 $K$ 跳内的信息。这避免了堆叠多个层的需求，从而缓解了过度平滑问题。
- 各向异性： 通过维护独立的 $S$ 和 $D$ 空间，模型捕捉到了方向性的信息流，增强了节点特征化的粒度。
节点信息聚合：
在扩散之后，来自 $S$ 空间和 $D$ 空间的嵌入被进行聚合。作者使用了一种自注意力机制，其中 $S$ 空间的嵌入作为查询（Query）， $D$ 空间的嵌入作为键（Key）和值（Value）。这种非对称聚合随后通过一个最终的 MLP 来生成统一的节点嵌入。
解的识别：
聚合后的节点嵌入通过外积生成边嵌入。一个边级注意力机制对这些嵌入进行重新加权，以突出关键的边。最后，一个 MLP 预测一个热图，代表每条边属于最优路径的概率。该热图引导蒙特卡洛树搜索（MCTS）来构建最终解。模型使用监督学习（针对地面真值热图的交叉熵）或无监督学习（最小化期望路径长度）进行优化。

核心贡献

问题表征： 本文识别并形式化了当前 GNN 方法的局限性，特别是图稀疏化导致的断连问题，以及全连接 TSP 图中缺乏信息丰富先验的问题。
算法设计： 引入了 MixScore 转移矩阵 和 各向异性图扩散 机制。这些创新使得高效的多跳信息传播在不进行稀疏化的前提下成为可能，从而保留了最优节点对之间的连通性。
实验验证： 大量实验表明，AGDN 在各种问题规模和节点分布下，在监督学习和无监督学习设置中均优于最先进的方法。

实验结果
作者在 200 到 1000 个节点的 TSP 实例以及来自 TSPLIB 的真实世界数据集上对 AGDN 进行了评估。

有效性： 在监督学习（SL）设置中，与 GatedGCN、Att-GCN 和 DIFUSCO 等基准模型相比，AGDN 实现了最低的相对于最优解的差距。例如，在 TSP-1000 上，AGDN 的差距为 1.28%，而 GatedGCN 为 7.26%。在无监督学习（UL）中，AGDN 也优于 UTSP 和 Position。
效率： AGDN 展示了卓越的计算效率。与 GatedGCN 相比，它所需的参数更少，推理时间更短，尤其是在增加信息聚合的跳数时。这归功于其在单个层内捕捉多跳信息的能力。
泛化能力： 模型表现出强大的泛化能力，在 TSP 100 上训练并在更大的实例（TSP-200, 500, 1000）以及多样化的节点分布（均匀分布、聚类分布、爆炸分布、内缩分布）上进行测试。它在无需重新训练的情况下，在真实的 TSPLIB 实例（tsp225, pcb442, pr1002）上也保持了高性能。

意义
本文声称 AGDN 解决了 TSP 求解中图稀疏化与信息丢失之间的根本权衡。通过引入各向异性扩散策略和 MixScore 先验，该框架使 GNN 能够有效地利用 TSP 图的全连接特性。结果表明，AGDN 提供了一个可扩展且泛化性强的解决方案，弥合了理论图学习能力与组合优化实际需求之间的差距，在实现最先进性能的同时保持了具有竞争力的推理时间。