学习局部覆盖：硬信息视界下的图神经组合优化

arXiv:2610.00422v1 公告类型：cross 摘要：神经组合优化通常假设存在一个读取整个实例的集中式求解器。我们研究相反的情形：具有硬信息视界的组合优化，其中每个节点只能看到自身的 $k$ 跳邻域，却必须确定其在全局解中的份额，并且所有这些确定结果必须组合成一个全局可行解。我们将其形式化为局部集合覆盖问题，并将其应用于加权多点中继（MPR）选择，即 Optimized Link State Routing Protocol version 2（OLSRv2）路由协议（RFC~7181）中的 NP-hard 两跳覆盖问题；该问题的信息视界由协议规定，而非由建模者选择。我们证明了两个结果。任何信息视界少一跳的确定性选择器，都必然无法实现覆盖，或得到与最优解相差 $\Delta$ 倍的结果；而在决策节点读取的 $L$ 层图神经网络（GNN）恰好是一个 $L$ 跳选择器，因此增加模型容量无法弥补半径不足。反之，在达到规定视界时，深度为 $O(\Delta)$ 的 \ac{GNN} 可以复现 RFC~7181 的覆盖贪心算法；当宽度为 $O(c_{\max}\Delta)$ 时，还能复现其具备度量感知能力的加权版本，两种情况下都继承了 $(1+\ln\Delta_2)$ 近似保证。在实验中，一个配备覆盖补全解码器、通过 CP-SAT 最优解进行行为克隆的 3 层 \ac{GATv2}，在实现 $100\%$ 覆盖时达到 $\text{cost}/\text{opt}=1.030\pm0.001$，而贪心算法为 $1.138$，弥合了 $79.1\%$ 的差距。将同一个学习器限制为一跳、在使用相同实例、相同解码器和相同示范的情况下，其结果降至 $1.344$，远差于贪心算法。我们进行了两项面向真实网络的迁移检验。OLSRv2 未修改的选择代码在 $200/200$ 个单位成本实例上与我们的基数贪心算法结果一致；在 $40{,}308$ 个真实营级移动性实例上，冻结模型在实现完全覆盖时弥合了 $48\%$ 的差距。信息视界，而非模型容量，是最重要的变量。