A new study shows a graph neural network can nearly match optimal solutions for a core routing decision, even when each node in the network can only see two hops of its surroundings.
The researchers tested the approach on multipoint relay selection, the NP-hard problem at the heart of OLSRv2, the routing protocol defined in RFC 7181. The protocol forces every node to decide which neighbors should relay its traffic using only a 2-hop view, a limit built into the protocol, not chosen by the researchers. They proved that no amount of extra model capacity fixes a network that can't see one hop further than it's allowed to, since a neural network's read-out is mathematically equivalent to its hop depth. Trained by copying optimal solutions from a constraint solver, a 3-layer GATv2 model landed within 3 percent of optimal cost, beating the greedy algorithm already built into OLSRv2, which runs 13.8 percent above optimal.
This matters for mesh and tactical radio networks, where OLSRv2 already runs and centralizing the decision isn't an option. On 40,308 real battalion mobility traces, the trained model closed 48 percent of the gap to optimal without retraining, hinting at real efficiency gains for decentralized routing in drone swarms or military networks.
The catch: shave the model down to one-hop visibility and it collapses to 34.4 percent above optimal, worse than the dumb greedy algorithm it was supposed to beat. The lesson isn't that neural networks are smarter than hand-written algorithms. It's that how much a node is allowed to see matters more than how big its brain is.