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
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(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.
Figures & tables
Figure 1: Combinatorial optimization under a hard information horizon. (a) At centre v , candidates N1 sit one hop out, each weighted by its centre-facing link cost, and terminals N2 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 Δ 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 Δ from optimal in (b).
Figure 3: (a) Per-instance cost/optimum on the 3200 test instances. (b) Cost/optimum against Δ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
cost/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)
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 c1 first, it having the best cost-per-coverage, and finishes at cost 28 . The optimum avoids c1 entirely: {c2,c4} 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.
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.
Yimeng Min, Carla P. Gomes
Department of Computer Science Cornell University Ithaca, NY, USA
Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.
Chendi Qian, Christopher Morris, Stefanie Jegelka +1
RWTH Aachen University, Germany · Technical University of Munich, Germany · Massachusetts Institute of Technology, USA +1
The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to \emph{replace} solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict \emph{when} a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ≈0% optimality gap on all six adversarial configurations tested (vs.\ 3.75--59.24% for greedy). A hybrid allocator combining the hardness classifier with GNN and greedy solvers achieves 0.51% overall gap on mixed distributions. Our honest evaluation on CATS benchmarks confirms that GNNs do not outperform Gurobi (0.45--0.71 vs.\ 0.20 gap), motivating the algorithm selection framing. Learning \emph{when} to deploy expensive solvers is more tractable than learning to replace them.
Sungwoo Kang
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea