Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

Johannes F. Loevenich; Thies Moehlenhof; Laurin Holz; Maxime Schwarzer; Tobias Huerten; Roberto Rigolin F. Lopes

stat.MLSep 30, 2026

Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

Authors: Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz, Maxime Schwarzer, Tobias Huerten, Roberto Rigolin F. Lopes

Organizations: cortAIx Labs, Thales Deutschland, Ditzingen, Germany · Department of Mathematics/Computer Science, University of Osnabrück, Osnabrück, Germany

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 (RFC7181), 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 RFC7181 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 $\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.

Figures & tables

Figure 1: Combinatorial optimization under a hard information horizon. (a) At centre

v

, candidates

N_{1}

sit one hop out, each weighted by its centre-facing link cost, and terminals

N_{2}

two hops out must all be covered; nothing beyond the dashed horizon exists for

v

. The costs make the objective weighted. (b) Every node runs the same local selection and the relay sets union into one connected backbone; three local balls are drawn in full. (c) An edge-conditioned GATv2 scores each candidate and a coverage-completing decoder returns a cover feasible by construction, so the network never learns feasibility. Below, cost/optimum against the fair greedy on the test split.

Figure 2: Both graphs give

v

the identical one-hop view boxed in dashes. (a) Each candidate covers a private terminal, forcing all

\Delta

into the relay set. (b) All share one terminal, so any single candidate suffices. A selector restricted to one hop cannot distinguish them, so it is either infeasible in (a) or a factor

\Delta

from optimal in (b).

Figure 3: (a) Per-instance cost/optimum on the

3200

test instances. (b) Cost/optimum against

\Delta_{2}

. (c) Relay assignments summed over flood sources, as a percentage of full flooding’s, over the

130

-minute ANGLOVA mission (

40{,}308

instances sampled every

30

s); a per-source sum, not a transmitter count. (d) Link-budget sweep. Panels (a, b) use the released checkpoint; each point is a full-split aggregate.

Method	$\text{cost}/\text{opt}$
Random feasible	$1.641$
MLP, no graph (DeepMPR-style)	$1.218$
Greedy reference	$1.138$
GNN, node-summary costs	$1.057$
GNN, full (ours)	$\mathbf{1.029}$
Optimum (CP-SAT)	$1.000$

Table 1: E1 ablation ladder on the test set (

n=3200

Figure 4: (a) Cost/optimum (

1.0

= optimal) for every method. (b) Out-of-distribution transfer of the

n{=}80

model.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 1: The fair cost-effectiveness greedy grabs

c_{1}

first, it having the best cost-per-coverage, and finishes at cost

28

. The optimum avoids

c_{1}

entirely:

\{c_{2},c_{4}\}

covers the same five terminals for cost

20

, a

29\%

saving. The learned selector recovers exactly this kind of cost-aware choice, which no locally-greedy rule can see. The instance is node

16

of seed

130

drawn from the same generator as the test split at

n=45

r=0.30

(the released test split uses

n=80

); it is an illustration, not a sampled statistic.

Explore similar work

Graph Neural Networks are Heuristics
Jan 19, 2026Yimeng Min, Carla P. GomesGraph Neural Networks Combinatorial Optimization
Department of Computer Science Cornell University Ithaca, NY, USA
Learning to Approximate Uniform Facility Location via Graph Neural Networks
Feb 13, 2026Chendi Qian, Christopher Morris, Stefanie Jegelka +1Approximation Algorithms Message Passing Neural Networks
RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1
Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
Feb 16, 2026Sungwoo KangCombinatorial Optimization Algorithm Selection
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea

Jan 19, 2026, cs.AIJ/K move · Enter open · S save

Graph Neural Networks are Heuristics

Yimeng Min, Carla P. Gomes

Department of Computer Science Cornell University Ithaca, NY, USA

Graph Neural Networks Combinatorial Optimization Heuristics Neural Network Approximate Nearest-Neighbor Search Hamiltonian

Open paper AskPDF arXiv

Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.

Abstract

Explore similar work

Graph Neural Networks are Heuristics

Learning to Approximate Uniform Facility Location via Graph Neural Networks

Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks