🤖 AI

Graph Neural Networks are Heuristics

本文证明了图神经网络可以通过使用无监督训练在单次前向传播中生成完整路径，从而作为欧几里得旅行商问题的快速学习启发式算法，其性能优于传统的贪婪基准模型，且不依赖于标签、奖励或序列解码。

原作者： Yimeng Min, Carla P. Gomes

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Yimeng Min, Carla P. Gomes

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

以下是关于论文《图神经网络即启发式算法》（Graph Neural Networks are Heuristics）的解释，采用了通俗易懂的语言和富有创意的类比。

核心思想：无需规则手册，学习解题

想象一下你正在尝试解决一个巨大的拼图：旅行商问题（TSP）。你有一张包含 100、200 甚至 500 个城市的地图，你需要找到一条最短的路线，访问每个城市恰好一次并回到起点。

传统上，人类有两种解决方法：

“完美”法： 使用超级计算机检查每一条可能的路线。这能保证得到最优解，但耗时极长（就像为了在图书馆里找一句话而试图读完所有的书）。
“足够好”法（启发式算法）： 使用一套手工设计的规则，比如“总是下一步去最近的城市”。这种方法很快，但往往会导致平庸的路线，因为它容易陷入局部陷阱。

论文的观点：
作者 Yimeng Min 和 Carla Gomes（来自康奈尔大学）认为，图神经网络（GNN） 不仅仅是引导这些旧规则的“助手”。相反，GNN 本身就可以成为最聪明的规则制定者。

他们构建了一个系统，该系统通过观察问题的形状来学习解决 TSP 问题，而无需被告知正确答案（没有标签），无需通过获取奖励来玩猜谜游戏（没有强化学习），也无需在事后检查工作以修正错误（没有搜索或局部改进）。它纯粹是通过观察问题的结构进行学习。

工作原理：“一击即中”的艺术家

大多数解决谜题的 AI 模型都像是一个缓慢的画家，一次添加一笔（决定下一个城市，然后下一个，再下一个）。这篇论文使用的是一种**非自回归（Non-Autoregressive）**模型。

类比：瞬间完成的马赛克
想象你有一个装满代表城市的瓷砖盒。

旧式 AI： 拿起一块瓷砖，放好，再拿起另一块，放在旁边，如此循环。它是一步步构建路径的。
本论文的 AI： 一眼看穿整盒瓷砖，瞬间将它们拼接在一起，形成一个完整、精美的马赛克。它不是在构建路径，而是瞬间洞察了全局。

秘诀：单模型的三个绝招

由于 AI 不被允许在做出猜测后进行“搜索”或“修正”错误，它是如何变得如此优秀的呢？作者使用了三个巧妙的技巧，使模型既鲁棒又具有多样性：

对称感知视觉（“旋转地图”技巧）：
如果你旋转一张城市地图，最短路线不会改变，只是看起来不同了。作者教会了 AI 理解路线的“形状”才是关键，而不是具体的坐标。他们给了 AI 一种特殊的“内在”观察地图的方式（类似于使用相对于中心的指南针和尺子），这样它就不会因为地图在桌子上的摆放位置而感到困惑。
受控的混乱（“丢弃”技巧）：
通常在训练 AI 时，我们会随机关闭一些神经元（称为“Dropout”）以防止它死记硬背训练数据。作者甚至在 AI 解决谜题时也保持了这个“关闭”开关处于开启状态。
- 类比： 想象要求一位厨师把同一道菜做 10 次。通常情况下，他们会做得完全一样。但在这里，厨师会被轻微地分心，或者每次使用的盐量略有不同。这创造了 1 0个略有差异的版本。AI 会带着这种“分心”运行 10 次谜题，生成 10 条不同的路线。然后你只需从中选出最好的那条即可。这创造了多样性，而无需训练 10 个不同的厨师。
快照集成（“时空旅行”技巧）：
在训练模型时，它会随时间发生变化。作者在训练的不同阶段保存了模型（就像在每个月月底为学生拍一张照片）。
- 类比： 他们不仅仅使用学生的期末考试成绩，还使用了学生在 9 月、10 月、11 月和 12 月的表现。有时，“9 月份”版本的模型在处理特定类型的谜题时，可能比“12 月份”的版本表现得更好。通过结合这些“快照”，他们获得了一支来自同一次训练过程的专家团队，且所有成员都在免费协作。

结果：快速且出人意料地出色

论文在包含 100、200 和 500 个城市的地图上进行了测试。

速度： 它非常快。在现代计算芯片（GPU）上，它在毫秒级内就能解决谜题。它比人类眨眼的速度还要快。
质量：
- 它大幅超越了标准的“前往最近邻居”贪婪算法。
- 它能与使用搜索和优化等更慢、更复杂的算法相媲美。
- 它达到了“完美”数学答案（由极其缓慢的 Concorde 求解器找到）的 4% 到 12% 左右，对于一个不进行搜索或修正错误的系统来说，这是一个巨大的成就。

总结

论文得出结论：图神经网络不仅是助手，它们本身就是启发式算法。

与其让工程师编写复杂的规则集来解决问题，我们可以训练一个神经网络去“感受”问题的结构，并在一瞥之间输出高质量的解决方案。AI 直接从数据中学习解题的“语法”，证明了如果你能教会计算机理解游戏的结构，你就不需要预先编写游戏的规则。

技术摘要：图神经网络即启发式算法

问题定义
本文探讨了欧几里得旅行商问题（Euclidean Travelling Salesman Problem, TSP），这是一个经典的组合优化问题，目标是在一组 $n$ 个城市中找到最短的哈密顿回路。作者挑战了目前主流的范式，即图神经网络（GNN）仅作为辅助工具——提供评分、引导搜索或模仿经典求解器的算法。相反，本文提出 GNN 可以作为一个独立的、学习到的启发式算法。具体的挑战在于，如何在不依赖自回归解码、强化学习奖励、显式搜索程序（如束搜索）或事后局部改进（如 2-opt）的情况下，通过单次前向传播构建出完整的路径。

方法论
所提出的方法是一种非自回归、无监督的 GNN 框架，它直接从问题的几何结构中学习如何解决 TSP 实例。

目标与公式化：
TSP 被公式化为最小化距离矩阵 $D$ 与经循环移位矩阵 $V$ 变换后的置换矩阵 $P$ 之乘积的迹。为了实现端到端的基于梯度的优化，在训练期间使用 Gumbel-Sinkhorn 松弛将离散置换 $P$ 放宽为软置换矩阵 $T$ 。损失函数仅为期望路径长度： $L_{TSP} = \langle D, TVT^\top \rangle$ 。在推理阶段，软置换通过匈牙利算法转换为硬置换。
对称性感知特征提取：
为了确保模型遵循欧几里得群的对称性（置换和平移不变性/等变性），作者引入了一个确定性的特征提取器。
- 平移不变性： 通过减去均值来对城市坐标进行中心化处理。
- 规范框架（Canonical Frame）： 利用中心化点经验协方差矩阵的特征向量构建一个正交框架。这消除了旋转和反射的歧义。
- 谐波编码： 将点投影到该规范框架上以导出内在的极坐标（ $r, \theta$ ）。角度信息通过 $M$ 个傅里叶谐波（ $\sin(m\theta), \cos(m\theta)$ ）进行编码，为 GNN 提供旋转不变的结构性线索。
网络架构：
核心模型是一个散射注意力图神经网络（Scattering-Attention Graph Neural Network, SCT-GNN）。它结合了基于扩散的表示（使用由平滑随机游走矩阵的幂次导出的图算子）和可学习的注意力机制，后者能够自适应地混合不同扩散尺度的特征。该网络在构造上是置换等变的。
用于多样性的集成策略：
为了在不训练多个模型或进行迭代搜索的情况下生成解的多样性，本文在单个训练轨迹中采用了两种机制：
- 蒙特卡洛（MC）Dropout： 在推理期间应用 Dropout。通过使用不同的 Dropout 掩码进行多次随机前向传播，模型可以从单个训练实例中生成多样化的路径。
- 快照集成（Snapshot Ensembling）： 在单次训练运行期间，在不同轮次（epoch）保存多个检查点。这些快照代表了优化景观中的不同点，在推理时被共同使用。在这些快照中选择最优路径。

核心贡献

GNN 作为独立启发式算法： 本文证明了 GNN 可以成为一个完整的启发式算法，通过单次前向传播产生有效的路径，而无需辅助搜索或精炼。
无监督学习： 该模型不需要地面真值（ground-truth）最优解或强化学习奖励；它仅通过最小化路径长度目标进行学习。
全局结构学习： 通过移除局部贪婪机制并依赖全局哈密顿回路目标，模型学习到了纯局部决策规则（如最近邻）所缺失的非局部组合约束。
高效性： 该方法在 GPU 上实现了毫秒级的推理，在质量与效率的权衡上优于经典的启发式算法以及其他依赖自回归解码或搜索的学习型方法。

实验结果
实验针对从均匀欧几里得分布中提取的 $n=100, 200,$ 和 $500$ 个节点的 TSP 实例进行。

对比贪婪算法： 该模型一致优于贪婪最近邻（Greedy Nearest-Neighbor, NN）基准。对于 TSP100，平均路径长度从 9.67（贪婪算法）提升至 8.18（确定性 GNN）。
对比经典启发式算法： 该方法在较小实例（TSP100, TSP200）上显著优于 Christofides 启发式算法，并在 TSP500 上与其持平，但 GPU 推理时间低了几个数量级。
对比基于学习的基准模型： 与强化学习（RL）和监督学习（SL）基准（如 GAT, GCN）相比，所提方法实现了具有竞争力的或更优的近似比（例如，在 TSP100 上为 4.39%，优于带有束搜索的强 RL 基准的 2.48%），同时由于避免了自回归解码和束搜索，速度明显更快。
集成效应： MC Dropout 和快照集成都进一步降低了近似比。结合这两种策略取得了最佳结果（TSP100 为 4.39% 差距，TSP200 为 8.25%，TSP500 为 12.11%），且推理时间仍保持在毫秒量级（在 TSP500 上组合集成约为 82ms）。

意义与主张
本文主张，启发式算法不必是手工设计的规则或搜索程序，而是可以直接从学习问题结构中涌现。通过将 TSP 表述为直接的置换学习并结合可微的哈密顿回路目标，作者展示了 GNN 可以内化全局组合约束。其意义在于改变了组合优化的范式：结构约束和生成模型可以取代显式搜索，成为解决难解问题的基础。结果表明，“学习到的启发式算法”在解的质量和计算效率方面，都能与经典的工程化方法相媲美甚至超越，特别是在搜索成本过高的情况下。这项工作将无监督 GNN 定位为一种新型的快速、学习型组合优化启发式算法。

核心思想：无需规则手册，学习解题

工作原理：“一击即中”的艺术家

秘诀：单模型的三个绝招

结果：快速且出人意料地出色

总结

技术摘要：图神经网络即启发式算法

类似论文