3层GATv2硬信息视界下逼近最优解，成本仅1.030，碾压贪心算法！
Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
📖 AI 总结
本文研究在严格信息受限条件下的图神经组合优化问题，即每个节点仅能观测其k跳邻域并据此做出局部决策，且这些决策必须组合成全局可行解。作者将该问题形式化为局部集合覆盖，并以OLSRv2路由协议中的加权多点中继选择这一NP难问题为实例展开研究。理论分析表明，任何视野比所需少一跳的确定性选择器必然无法覆盖或偏离最优解达Δ倍，而L层图神经网络的表达能力恰好等价于L跳选择器，说明模型容量无法弥补信息视野的不足；反之，在足够视野下，深度为O(Δ)的GNN可复现协议中的贪心算法并继承其近似保证。实验显示，基于CP-SAT最优解行为克隆的三层GATv2在完全覆盖下将成本比降至1.030，显著优于贪心的1.138，而将视野限制为一跳后性能骤降至1.344。真实 battalion 机动网络上的迁移实验进一步验证了该方法的有效性。研究结论指出，信息视野而非模型容量是决定此类优化性能的最关键变量。
🔑 关键词速览
| 硬信息视界 | 指每个节点只能获取其 k 跳邻域内的信息，无法获知全局信息的限制条件。 |
| 局部集合覆盖 | 将组合优化问题形式化为每个节点仅基于局部信息选择集合以覆盖全局需求的问题。 |
| 加权多点中继选择 | OLSRv2 路由协议中 NP 难的 2 跳覆盖问题，用于选择中继节点以优化网络广播。 |
| 图神经网络 | 一种基于图结构数据的深度学习模型，通过消息传递聚合邻域信息，其层数对应信息传播的跳数。 |
| GATv2 | 图注意力网络 v2，一种改进的图神经网络变体，使用动态注意力机制聚合邻居特征。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅