🤖 machine learning

Machine Learning for Two-Stage Graph Sparsification for the Travelling Salesman Problem

该论文提出了一种结合 $\alpha$ -Nearest 与 POPMUSIC 启发式方法以最大化召回率、并利用机器学习模型进行二次剪枝的两阶段图稀疏化框架，该框架在多种距离类型、空间分布及规模下均能显著降低候选图密度并保持高覆盖率，且优于现有的单阶段神经稀疏化方法。

原作者： Bo-Cheng Lin, Yi Mei, Mengjie Zhang

发布于 2026-04-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Bo-Cheng Lin, Yi Mei, Mengjie Zhang

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

这篇论文讲述了一个关于**“如何更聪明地解决旅行商问题（TSP）”**的故事。

想象一下，你是一位超级导游，手里有一张巨大的地图，上面有 50 到 500 个不同的城市。你的任务是规划一条最短的路线，让游客恰好访问每个城市一次，最后回到起点。

1. 核心难题：地图太大了，怎么办？

如果地图上的城市很多，城市之间的连线（可能的路线）就会多到天文数字。

全图搜索：就像让你把地图上所有可能的连线都走一遍，看看哪条最短。这太慢了，计算机算到宇宙毁灭也算不完。
现有方法：聪明的导游（算法）不会看所有线，他们只画一个**“候选路线图”**（只保留一部分看起来不错的线）。
- 问题在于：这个“候选路线图”怎么画才完美？
  - 画得太少（太稀疏）：可能会漏掉那条真正的最短路线，导致你走冤枉路。
  - 画得太多（太密集）：虽然不会漏掉好路线，但计算机还得在密密麻麻的线里找，速度还是慢。

这就好比你在找宝藏，如果只给一张只有几条线的草图，你可能找不到宝藏；如果给一张画满所有街道的地图，你又要花半天时间筛选。

2. 以前的“独门秘籍”不够用

以前，导游们主要靠两种经验法则（启发式算法）来画这张图：

α-Nearest：像是一个**“保守派”。它画出的线比较多，虽然有点乱，但很少漏掉**真正的宝藏路线（召回率高）。
POPMUSIC：像是一个**“激进派”。它画出的线非常少，非常精简，但在城市变多或地形复杂时，它容易漏掉**关键的路线。

困境：没有一种方法既能画得少（快），又能保证不漏（准）。

3. 这篇论文的“两步走”绝招

作者提出了一种**“先做加法，再做减法”的两阶段策略，就像是一个“先广撒网，再精筛选”**的过程。

第一阶段：广撒网（Union，求并集）

做法：把“保守派”和“激进派”画的所有线全部加在一起。
比喻：就像两个侦探，一个负责查所有可能的线索，另一个负责查最关键的线索。把两个人的线索本合在一起，虽然本子很厚（线很多），但几乎肯定包含了真正的宝藏路线。
关键点：这时候，每条线都有一个**“出身标签”**：
- 是只有侦探 A 发现的？
- 是只有侦探 B 发现的？
- 还是两个侦探都确认过的？
- 作者发现：两个侦探都确认的线，几乎肯定是好线！

第二阶段：精筛选（Machine Learning，机器学习）

做法：训练一个**“智能过滤器”**（机器学习模型）。这个过滤器不看全图，只看第一阶段合出来的那张“厚本子”。
任务：它根据每条线的“出身标签”和其他特征，给每条线打分。
- 两个侦探都确认的线：分数极高，坚决保留。
- 只有一个侦探确认的线：分数较低，果断剪掉。
结果：原本厚厚的本子，被剪掉了很多没用的线，变得既薄（速度快），又准（没漏掉宝藏）。

4. 为什么这个方法这么厉害？（三大亮点）

不仅快，而且稳：
- 它能把路线的数量减少 37% 到 47%，但依然保留了 99.69% 以上的最优路线。
- 就像把原本拥挤的早高峰地铁，清理掉了一半的无效车厢，但所有要下车的乘客（最优解）都还在车上。
不挑地图（通用性强）：
- 以前的很多 AI 方法只能看懂“欧几里得距离”（就像在平地上看直线距离）。
- 这个方法不看坐标，只看距离数值。无论是平地上的城市、球面上的城市，还是像迷宫一样的城市，它都能用同一套逻辑处理。就像一把万能钥匙，能开各种锁。
越大的地图越有用：
- 以前那种“激进派”方法，城市一多就容易出错。
- 而这个“两步走”方法，在城市数量变大（比如从 100 个变成 500 个）时，表现反而比单独用任何一种老方法都要好。就像老练的船长，船越大，他的导航技术越显得珍贵。

5. 和“神经网络”比怎么样？

现在很火的深度学习（神经网络）也能做这件事，但它们：

太挑环境：只能处理平地上的城市（欧几里得距离）。
太慢：需要昂贵的显卡（GPU）来算。
结果：作者的方法用普通的 CPU 就能跑，而且比那些复杂的神经网络更准、更省资源。

总结

这篇论文的核心思想就是：不要试图一步到位。
先让两个老手（传统算法）把所有可能的路都找出来（虽然多，但保险），然后请一个聪明的助手（机器学习）根据“谁推荐的”这个线索，把那些不靠谱的线剪掉。

最终效果：得到了一张既精简又完美的路线图，让计算机能像闪电一样算出旅行商的最优解。

论文技术总结：基于机器学习的两阶段图稀疏化求解旅行商问题

1. 研究背景与问题定义

核心问题：
高性能旅行商问题（TSP）求解器（如 LKH）通常不在完全图上搜索，而是在一个稀疏的候选图（Candidate Graph）中搜索。构建候选图面临一个核心权衡：

边太少：可能丢失最优解中的关键边，导致求解器无法找到高质量解。
边太多：搜索空间过大，浪费计算时间。

现有方法的局限性：

启发式方法：目前最强大的两种启发式方法是 $\alpha$ $α$ -Nearest 和 POPMUSIC。
- POPMUSIC 在规模较小时稀疏性好且召回率高，但在大规模或复杂分布下召回率显著下降。
- $\alpha$ -Nearest 召回率稳定但密度较高。
- 两者取并集（Union）虽能保证高召回率，但会导致图密度过高。
现有机器学习方法：大多直接在完全图（Complete Graph）或稠密子图上进行边剪枝。这不仅计算成本高昂，而且通常局限于欧几里得距离（Euclidean），难以推广到其他距离度量（如曼哈顿距离、地理距离等）。

研究目标：
提出一种通用的、高效的图稀疏化方法，能够在保持高最优边覆盖率（Recall）的同时，显著降低候选图的密度，并适用于多种距离类型和分布。

2. 方法论：两阶段图稀疏化框架

作者提出了一种两阶段（Two-Stage）的图稀疏化流程：

第一阶段：最大化召回率（Heuristic Union）

策略：取 $\alpha$ -Nearest 和 POPMUSIC 两种启发式方法生成的候选边的并集（Union）。
目的：构建一个具有近乎完美覆盖率（Near-perfect coverage）的基础候选图 $G_b$ 。
关键创新（源来源信号 Source-Provenance Signal）：
- 并集操作不仅增加了边，还引入了“来源”信息：一条边是仅来自 $\alpha$ -Nearest、仅来自 POPMUSIC，还是两者共有。
- 实验表明，同时出现在两个启发式中的边极大概率属于最优解，而仅出现在一个启发式中的边更可能是冗余的。这一信号为后续的机器学习剪枝提供了强有力的监督信号。

第二阶段：基于学习的剪枝（Learned Pruning）

输入：第一阶段生成的稀疏基础图 $G_b$ （而非完全图）。
特征工程：
- 设计了与距离类型无关（Distance-type agnostic）的特征，仅依赖边权重、排名、局部统计量（如 Z-score）和候选图拓扑结构，不依赖坐标几何。
- 特征包括：距离幅度、端点排名百分位、局部归一化比率、邻域结构（如 kNN 重叠）、候选图拓扑度以及源来源特征（Source Provenance）。
模型训练：
- 训练一个轻量级分类/回归模型（Logistic Regression, Linear SVM, 或 XGBoost）来对 $G_b$ 中的每条边打分。
- 标签 $y_e=1$ 表示该边属于 Concorde 求解器计算出的最优解。
剪枝规则：
- 采用节点级（Node-level）的剪枝策略，而非全局阈值。
- 对每个节点的邻接边按得分排序，保留得分最高的边，直到累积 Softmax 概率质量达到阈值 $\eta$ ，同时保证每个节点至少保留 $m_{min}=2$ 条边以维持解的可行性。

3. 实验设置

数据集：涵盖 TSPLIB 中的 4 种距离类型（EUC_2D, ATT, MAN_2D, GEO）和 5 种空间分布（均匀、聚类、网格抖动、离群混合、走廊），共 20 个 TSP 族。
规模：训练集为 N=100，测试集涵盖 N=50, 100, 200, 500（包含训练集 5 倍规模的外推测试）。
基线对比：
- 单阶段启发式（ $\alpha$ -Nearest, POPMUSIC）。
- 完全图直接剪枝。
- 近期神经稀疏化方法（DIFUSCO, AttGCN, DIMES），这些方法通常仅限欧几里得距离且基于完全图。
下游求解器：LKH（默认配置，无额外调优）。

4. 关键结果

4.1 稀疏性与覆盖率

密度降低：在保持高覆盖率的前提下，XGBoost 模型将候选图密度降低了 37% - 47%。
- 例如在 TSP500 上，边数从约 $5.93N$ 降至 $3.14N$ 。
覆盖率保持：在所有测试规模和距离类型上，保留了 $\ge 99.69\%$ 的最优解边。
泛化能力：
- 模型在 N=100 训练，在 N=500（5 倍规模）上表现依然优异，证明了其跨规模泛化能力。
- 在四种非欧几里得距离类型上均表现稳定，而神经基线方法无法处理非欧几里得数据。

4.2 求解器性能提升

速度提升：稀疏后的图使 LKH 求解速度提升了 1.20 - 1.28 倍（Union + Logistic Regression 表现最佳）。
解质量：最优性间隙（Optimality Gap）未增加，甚至在某些情况下略有降低，证明剪除的边确实是冗余的。

4.3 与神经稀疏化方法的对比（EUC_2D 场景）

覆盖率：本文方法（Union + XGBoost）在 5 种分布中的 4 种上覆盖率最高（99.91% - 99.95%），优于 DIFUSCO 和 AttGCN。
密度：本文方法生成的图更稀疏（2.7N - 4.0N vs 神经方法的 3.7N - 4.8N）。
效率：本文方法仅需 CPU 运行，推理时间极短（<83ms/实例），而神经方法需要 GPU 且推理时间较长。

4.4 消融实验

两阶段 vs 单阶段：直接对完全图进行剪枝效果极差（密度高且难以学习）。先取并集再剪枝是关键。
Union vs 单一启发式：
- 在 N=200 以上，"Union + 学习剪枝"的覆盖率甚至超过了单独使用 POPMUSIC（后者在大规模下召回率下降）。
- 证明了“源来源信号”是模型能够稳定迁移到大规模实例的核心原因。

5. 主要贡献与意义

提出了高效的两阶段稀疏化流水线：
- 改变了以往在完全图上学习剪枝的模式，转而在已经稀疏的启发式候选图上进行学习。
- 实现了在多种距离类型和分布下的通用性，打破了神经方法对欧几里得坐标的依赖。
揭示了“源来源信号”（Source-Provenance Signal）的关键作用：
- 发现融合两个启发式方法产生的“双重来源”信号是预测边重要性的最强特征。
- 这一发现使得学习问题变得简单，甚至简单的逻辑回归（Logistic Regression）就能达到很好的效果，且具备极强的跨规模泛化性。
证明了在大规模问题上的优势：
- 传统启发式（如 POPMUSIC）在大规模下性能下降，而本文提出的“并集 + 学习剪枝”方法在 N $\ge$ 200 时，其覆盖率反而优于单一的最佳启发式方法。
实际效能：
- 显著降低了候选图密度，直接提升了 LKH 等主流求解器的运行速度（约 20%-28% 加速），且无需重新调优求解器参数。
- 计算开销极低，适合集成到现有的工业级 TSP 求解流程中。

6. 局限性与未来方向

缺乏理论保证：目前主要是实证结果，缺乏对“学习剪枝保留所有最优边”的理论证明。
训练依赖：训练需要 Concorde 求解器生成精确的最优解标签，限制了在超大规模实例上的直接训练（尽管模型可以泛化）。
极端情况：在“走廊（Corridor）”分布的大规模实例上，覆盖率略有下降，主要是因为长距离边在局部特征中难以被识别。

总结：该论文通过巧妙的“先融合后剪枝”策略，利用启发式方法的互补性构建强监督信号，成功利用轻量级机器学习模型解决了 TSP 候选图构建中的稀疏性与可靠性权衡问题，在性能、通用性和效率上均超越了现有的启发式和神经方法。