剪掉99%的边还能保持最优解差距不到1%，这个图稀疏化方法让大规模TSP求解效率飙升！
Dual-GNN Multilevel Coarsening for Maximum Independent Set
📖 AI 总结
该论文提出一种面向最大独立集问题的双图神经网络多层粗化方法。针对大规模图上的组合优化难题，作者将图神经网络与多层粗化框架相结合，通过双重GNN结构在粗化过程中同时学习节点与边的保留策略，以更有效地压缩图规模并保留关键结构信息。摘要中提及的实验结果显示，该方法在保持解质量的同时显著降低了计算规模，在部分数据集上可剪除高达95%至99%的边，而解与最优值的差距仍控制在1%以内，并在多个基准数据集上展现出较强的泛化能力。该研究的意义在于将学习型策略引入经典组合优化的图缩减环节，为最大独立集及其他大规模图问题的求解提供了兼顾效率与精度的新思路。
🔑 关键词速览
| Traveling Salesman Problem (TSP) | 旅行商问题，即寻找访问所有城市并返回起点的最短闭合路径的经典组合优化问题。 |
| Graph Sparsification | 图稀疏化，通过删除图中部分边或顶点来减小图规模，同时尽量保持原图关键性质的技术。 |
| Graph Edge Sparsification (GES) | 图边稀疏化，本文提出的基于学习的稀疏化方法，针对欧氏TSP自适应地生成稀疏图。 |
| Euclidean TSP | 欧氏旅行商问题，指城市位于欧几里得平面且距离由欧氏距离定义的TSP变体。 |
| Optimality Gap | 最优性差距，衡量近似解与最优解之间相对误差的指标，通常以百分比表示。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅