Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
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 Δ 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(Δ) reproduces the RFC~7181 covering greedy, and at width O(cmaxΔ) its metric-aware weighted analogue, inheriting the (1+lnΔ2)-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches cost/opt=1.030±0.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.
Related
- EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference
- Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
- Combinatorial Optimization Augmented Machine Learning for Dynamic Electric Autonomous Dial-a-Ride Problem
- On Han- and Shearer-Type Information Inequalities: Equality Conditions and Combinatorial Applications
- On Sparse Graph Limits for Neural Combinatorial Optimization
BibTeX
@misc{loevenich2026learning,
title = {{Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon}},
author = {Johannes F. Loevenich and Thies Moehlenhof and Laurin Holz and Maxime Schwarzer and Tobias Huerten and Roberto Rigolin F. Lopes},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00422},
eprint = {2610.00422},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00422},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon
AU - Johannes F. Loevenich
AU - Thies Moehlenhof
AU - Laurin Holz
AU - Maxime Schwarzer
AU - Tobias Huerten
AU - Roberto Rigolin F. Lopes
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00422
UR - https://arxiv.org/abs/2610.00422
AB - 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 Δ 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(Δ) reproduces the RFC~7181 covering greedy, and at width O(c_maxΔ) its metric-aware weighted analogue, inheriting the (1+lnΔ_2)-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches cost/opt=1.030±0.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.
ER -