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

Introduction

• A one-hop-short deterministic selector must be infeasible or a factor Δ from optimal, while at two hops a bounded-depth GNN reproduces RFC 7181 greedy and inherits its (1 + ln Δ2)-approximation.The protocol fixes the two-hop horizon; greater network depth does not extend it.Source: Introduction · p. 1
• The weighted objective is the main opportunity for improvement because even a reasonably cost-effective greedy approach leaves a substantial performance gap.For cardinality, greedy is already near-optimal.Source: Introduction · p. 1
• The paper formalizes hard-horizon optimization as local set cover on weighted relay selection and proves lower bounds below the horizon and constructive guarantees at it for both objectives.It also trains an ILP-cloned GATv2 selector with a feasible-by-construction decoder and reports transfer to real-world mobility at full coverage.Source: Introduction · p. 1

Horizon

• Each node selects a minimum-weight subset of its one-hop candidates that covers all strict two-hop terminals, using center-facing link costs.The local instance is a weighted set-cover problem, with candidate count bounded by Δ and the greedy guarantee governed by Δ2.Source: Horizon · p. 2
• Local decisions are independent, and global feasibility is the conjunction of per-node coverage constraints; the union of selected sets forms the forwarding overlay.The horizon limits each node’s topological context rather than coordination between centers.Source: Horizon · p. 2
• The protocol supplies exactly a two-hop ball, so message-passing depth cannot extend the receptive radius beyond two hops.At that horizon, depth O(Δ) reproduces greedy for cardinality, while width O(cmaxΔ) suffices for the weighted analogue; both inherit the (1 + ln Δ2)-approximation.Source: Horizon · p. 2
• OLSRv2 routers choose symmetric one-hop neighbors to reach all two-hop neighbors, and the selected relays flood control traffic as a routing backbone.Assigning link costs such as ETX or energy makes each router’s objective the total cost of its relay set rather than its size.Source: Horizon · p. 2

Global Cover

• For every Δ ≥ 2, a deterministic one-hop selector has an instance where it is infeasible or its cardinality ratio is at least Δ.Paired instances with identical one-hop views demand different relay sets, forcing the same selector either to omit a required candidate or choose all Δ.Source: Global Cover · p. 2
• An L-layer message-passing GNN read out at a node is an L-hop-local selector, so one-layer networks cannot overcome the one-hop bound through greater width.The selector’s output depends only on its attributed L-hop ball.Source: Global Cover · p. 2
• A depth O(Δ) GNN with constant hidden dimensions reproduces the RFC 7181 cardinality greedy and achieves a (1 + ln Δ2)-approximation within the two-hop ball.Each round aggregates marginal gains, selects the candidate with the fixed deterministic key, and updates the covered terminals; at most Δ rounds are needed.Source: Global Cover · p. 3
• For integer link costs in {1, . . . , cmax}, a depth O(Δ), width O(cmaxΔ) GNN reproduces weighted cost-effectiveness greedy with a (1 + ln Δ2)-approximation.Ranking the bounded set of possible cost-to-gain ratios converts weighted selection into integer selection.Source: Global Cover · p. 3

• Every decoded solution covers all terminals: the decoder sorts candidates once by learned score, force-selects always-forward relays, then selects candidates that reach uncovered terminals.Ties use a fixed candidate enumeration, and the decoder—not the network—ensures feasibility.Source: A Feasible-by-Construction Neural… · p. 4
• The 3-layer GATv2 produces one score per candidate and uses incident edge attributes to consume link costs directly.The roughly 240k-parameter encoder represents local MPR instances with role, degree, willingness, coverage-degree, terminal-reach, and link-cost features.Source: A Feasible-by-Construction Neural… · pp. 3–4
• Unlike the theorem’s adaptive marginal-gain rule, the decoder ranks candidates once by learned score; this forfeits the approximation guarantee, leaving feasibility provable and weighted near-optimality empirical.The coverage loop runs outside the network, so the encoder supplies a single ordering rather than implementing the theorem’s sequential rounds.Source: A Feasible-by-Construction Neural… · p. 4
• Behavior cloning trains the network to rank optimal CP-SAT-selected relays above rejected candidates, using the protocol-constrained optimum as the demonstration.Every candidate has default willingness in these instances, making the always-forward constraint vacuous.Source: A Feasible-by-Construction Neural… · p. 4
• The design assigns the horizon to the input, coverage completion to the decoder, and the cost-aware ordering to the learned encoder.The decoder is a static-score variant of the theorem’s greedy skeleton.Source: A Feasible-by-Construction Neural… · p. 4

Experimental Setup

• The evaluation uses weighted MPR on random-geometric unit-disk graphs, with CP-SAT providing the exact cost/opt = 1.0 benchmark.The dataset contains 12,000 training, 2,400 validation, and 3,200 test instances from disjoint graph seeds; the model is a 3-layer GATv2.Source: Experiments · pp. 5–6

Impact of the Information Horizon

• Restricting the encoder to a 1-hop ball yields cost/opt = 1.344 ± 0.000, worse than the 2-hop model (1.030) and greedy baseline (1.138), while the decoder maintains 100% feasibility.Source: Experiments · p. 5

Component Ablation (E1)

• The ablation ladder improves from cost/opt = 1.218 for a structure-blind MLP to 1.057 with message passing and 1.029 with edge-conditioned attention.The table caption identifies this as the E1 ablation ladder on the 3,200-instance test set.Source: Experiments · p. 5, Table 1 · p. 5

Structural Feasibility Verification (E2)

• The decoder guarantees a coverage ratio of 1.0 even for random and MLP score-generating heuristics, while raw neural outputs do not ensure coverage.This makes constraint satisfaction an architectural invariant rather than a learned objective.Source: Experiments · p. 5

Primary Empirical Results

• On 3,200 test instances, the GNN reaches cost/opt = 1.030 ± 0.001 versus greedy’s 1.138, closing 79.1%±0.6% of the gap with 100% coverage.It matches or beats greedy on 93.5% of instances and is exactly optimal on 85%, versus 41% for greedy.Source: Experiments · p. 5, Figure 3 · p. 6

Protocol Validation and Real-World Mobility (E4)

• On 40,308 ANGLOVA mobility instances, the frozen model reaches cost ratio 1.033 versus greedy’s 1.080, closing 48.3% of the gap at 100% feasibility.Its relay assignments sum to 8.7% of full flooding’s one-hop forwarding assignments, versus 10.7% for greedy; this is a per-source sum, not a transmitter count.Source: Figure 3 · p. 6, Experiments · p. 6

Generalization and Transferability (E3)

• The n = 80 model retains approximately 74% gap-closed at n = 160, while dense networks at r = 0.46 yield 51% and remain 100% feasible.The reported transfer tests change network scale or density.Source: Experiments · p. 6

Protocol Validation and Real-World Mobility (E4)

• The greedy implementation matches unmodified RFC 7181 selections on 200 unit-cost instances; the link-budget sweep reports 85.8% gap-closed at 110 dB and −12.4% at 140 dB.The 140 dB point is identified as the noise threshold where greedy becomes competitive.Source: Experiments · p. 6

Related Work

• Earlier graph-optimization methods use global state, whereas this work has each node choose its part of a globally valid cover from its two-hop neighborhood.The paper frames the information horizon as the object of study, not an implementation detail.Source: Related Work · pp. 6–7
• Unlike DeepMPR’s per-packet forwarding decisions and graph-reinforcement routing policies, this work selects relay sets to cover each two-hop neighborhood.Its coverage-completing decoder guarantees 100% feasibility, and the graph-blind scorer ablation underperforms greedy.Source: Related Work · p. 7
• Weighted set-cover greedy has a (1 + ln ∆2)-approximation, but on this distribution weighted greedy leaves a gap that the metric-aware GNN reduces to cost/opt = 1.030.The paper reports unweighted greedy within 0.5% of optimal.Source: Related Work · p. 7
• The Local-model correspondence makes an L-layer message-passing GNN an L-hop selector, so the one-hop horizon dichotomy applies regardless of network width.Depth–width lower bounds constrain computation above the horizon and are described as complementary.Source: Related Work · p. 7
• The contribution extends established locality-versus-approximation theory to neural combinatorial optimization, with a weighted empirical gap and a unit-cost check against deployed RFC 7181 code.Reported gaps use an exact integer-program optimum rather than another heuristic as the yardstick.Source: Related Work · p. 7

Conclusion

• 79.1% of the greedy performance gap is closed by the GATv2 model at full coverage.The conclusion also reports out-of-distribution generalization on the ANGLOVA tactical mobility benchmark, with feasibility guarantees holding continuously.Source: Conclusion · p. 7
• Below two hops, deterministic policies face a ∆-factor optimality gap or infeasibility, while bounded-depth GNNs match RFC 7181 greedy performance and its (1+ln ∆2)-approximation.The weighted case inherits the upper bound, although the greedy heuristic remains suboptimal.Source: Conclusion · p. 7
• The conclusion leaves open whether larger observation radii could help with the coupled structure formed by the global union of selected sets.It also notes that the remaining weighted optimization gap may depend on architectural choices.Source: Conclusion · pp. 7–8