arXiv：cs.LG（机器学习，全量分类）· Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz, Maxime Schwarzer, Tobias Huerten, Roberto Rigolin F. Lopes·· 14 小时前AI 评分35
在硬信息视界下学习局部覆盖：图神经网络组合优化
Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
AI 导读
研究提出"硬信息视界"下的组合优化问题：每个节点仅凭 k-hop 邻域决定自身方案，且须组合成全局可行解，并在 OLSRv2 路由协议的加权多点中继（MPR）选择上实例化。
正文
Abstract:Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its $k$-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC~7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor $\Delta$ from optimal, and an $L$-layer graph neural network (GNN) read out at the deciding node is exactly an $L$-hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth $O(\Delta)$ reproduces the RFC~7181 covering greedy, and at width $O(c_{\max}\Delta)$ its metric-aware weighted analogue, inheriting the $(1+\ln\Delta_2)$-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches $\text{cost}/\text{opt}=1.030\pm0.001$ against greedy's $1.138$, closing $79.1\%$ of the gap at $100\%$ coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to $1.344$, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on $200/200$ unit-cost instances, and on $40{,}308$ instances of real battalion mobility the frozen model closes $48\%$ of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.
| Subjects: | Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.00422 [stat.ML] |
| (or arXiv:2610.00422v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.00422 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Maxime Schwarzer [view email]
[v1]
Wed, 30 Sep 2026 15:23:36 UTC (313 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org