A new paper argues that graph neural networks don't have to play second fiddle to classical algorithms.
Researchers trained a non-autoregressive GNN to solve the Euclidean Travelling Salesman Problem — a classic combinatorial puzzle about finding the shortest route through a set of cities — without labels, rewards, sequential decoding, or any search procedure. The only supervision signal was a differentiable Hamiltonian-cycle objective, meaning the model learned to produce valid tours by optimizing a mathematical condition directly. Once trained, it generates a complete tour in a single forward pass. Inference stays in the millisecond range on GPUs, and the team used dropout plus snapshots from one training run to get solution diversity without hand-engineered moves.
The standard GNN playbook has been to bolt neural networks onto existing solvers — use them to guide search, score candidates, or mimic known algorithms. This paper treats the GNN itself as the heuristic, which matters because it removes the classical solver dependency entirely. On benchmark sets of 100, 200, and 500 cities, the model consistently beat nearest-neighbor greedy baselines, a standard sanity check for TSP solvers.
The results don't unseat state-of-the-art TSP solvers like LKH3 or Concorde, and the paper doesn't claim they do — beating a greedy baseline is a low bar. But the framing is the point: unsupervised GNNs as a standalone heuristic class, not a training-wheels attachment to something else.