无需标签和搜索，图神经网络可直接生成旅行商问题的高效解。
Graph Neural Networks are Heuristics
- 用可微分环路目标监督，训练非自回归GNN直接输出完整路径。
- 在TSP100/200/500上优于最近邻贪心基线，且推理仅需毫秒级时间。
- 通过丢弃和快照自然产生解多样性，适合需要快速求解的场景。
图神经网络通常被视为组合优化中的辅助工具：模仿算法、引导搜索或为经典方法提供评分。本文表明，这种辅助角色并非本质属性。GNN本身即可成为启发式算法。针对欧氏旅行商问题，我们训练了一个无标签、无奖励、无序列解码、无搜索或局部改进的非自回归GNN。唯一的监督信号是可微分的哈密顿回路目标函数。训练后的模型能在一次前向传播中生成完整路径，同时通过丢弃和单次训练轨迹的快照实现解的多样性，无需人工设计操作。该启发式是学习所得，而非编程实现。其速度极快：在GPU上批量推理始终维持在毫秒级别。在TSP100、TSP200和TSP500上的实验表明，该模型持续优于最近邻贪心基线。这些结果揭示了无监督GNN是一类用于组合优化的快速学习型启发式方法。
原文摘要 · Abstract (English)
Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。