🤖 AI

Graph Neural Networks are Heuristics

This paper demonstrates that Graph Neural Networks can function as fast, learned heuristics for the Euclidean Travelling Salesman Problem by using unsupervised training to generate complete tours in a single forward pass, outperforming traditional greedy baselines without relying on labels, rewards, or sequential decoding.

Original authors: Yimeng Min, Carla P. Gomes

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yimeng Min, Carla P. Gomes

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Learning to Solve Puzzles Without a Rulebook

Imagine you are trying to solve a massive puzzle: the Travelling Salesman Problem (TSP). You have a map of 100, 200, or even 500 cities, and you need to find the shortest possible route that visits every city exactly once and returns home.

Traditionally, humans solve this in two ways:

The "Perfect" Way: Use a super-computer to check every single possible route. This guarantees the best answer but takes forever (like trying to read every book in a library to find one specific sentence).
The "Good Enough" Way (Heuristics): Use a set of hand-crafted rules, like "always go to the nearest city next." This is fast, but it often leads to a mediocre route because it gets stuck in local traps.

The Paper's Claim:
The authors, Yimeng Min and Carla Gomes from Cornell University, argue that Graph Neural Networks (GNNs) don't just need to be "helpers" that guide these old rules. Instead, the GNN itself can be the smartest rule-maker.

They built a system that learns to solve the TSP without being taught the right answers (no labels), without playing a guessing game to get rewards (no reinforcement learning), and without checking its work afterward to fix mistakes (no search or local improvement). It learns purely by looking at the shape of the problem.

How It Works: The "One-Shot" Artist

Most AI models that solve puzzles work like a slow painter, adding one brushstroke at a time (deciding the next city, then the next, then the next). This paper uses a Non-Autoregressive model.

The Analogy: The Instant Mosaic
Imagine you have a box of tiles representing cities.

Old AI: Picks up one tile, places it, picks up another, places it next to it, and so on. It builds the path step-by-step.
This Paper's AI: Looks at the whole box of tiles at once and instantly snaps them together into a complete, finished mosaic in a single flash. It doesn't build the path; it sees the whole picture immediately.

The Secret Sauce: Three Tricks for a Single Model

Since the AI isn't allowed to "search" or "fix" its mistakes after making a guess, how does it get so good? The authors used three clever tricks to make the model robust and diverse:

Symmetry-Aware Vision (The "Rotating Map" Trick):
If you rotate a map of cities, the shortest route doesn't change; it just looks different. The authors taught the AI to understand that the shape of the route matters, not the specific coordinates. They gave the AI a special "intrinsic" way of seeing the map (like using a compass and ruler relative to the center) so it doesn't get confused by where the map is placed on the table.
Controlled Chaos (The "Dropout" Trick):
Usually, when you train an AI, you turn off some of its neurons randomly (called "dropout") to stop it from memorizing the training data. The authors kept this "off" switch active even when the AI was solving the puzzle.
- The Analogy: Imagine asking a chef to cook the same dish 10 times. Usually, they would cook it exactly the same way. But here, the chef is slightly distracted or uses a slightly different pinch of salt each time. This creates 10 slightly different versions of the dish. The AI runs the puzzle 10 times with this "distraction," generating 10 different routes. You then just pick the best one. This creates variety without needing to train 10 different chefs.
Snapshot Ensembling (The "Time-Travel" Trick):
When training a model, it changes over time. The authors saved the model at different moments during its training (like taking photos of a student at the end of every month).
- The Analogy: Instead of just using the student's final exam score, they use the student's performance from September, October, November, and December. Sometimes the "September" version of the model is better at a specific type of puzzle than the "December" version. By combining these "snapshots," they get a team of experts from the same training session, all working together for free.

The Results: Fast and Surprisingly Good

The paper tested this on maps with 100, 200, and 500 cities.

Speed: It is incredibly fast. On a modern computer chip (GPU), it solves the puzzle in milliseconds. It's faster than a human can blink.
Quality:
- It beats the standard "Go to the nearest neighbor" greedy method by a wide margin.
- It is competitive with much slower, complex methods that use search and refinement.
- It gets within about 4% to 12% of the "perfect" mathematical answer (found by the super-slow Concorde solver), which is a huge achievement for something that doesn't search or fix its mistakes.

The Bottom Line

The paper concludes that Graph Neural Networks are not just assistants; they are heuristics themselves.

Instead of a human engineer writing a complex set of rules to solve a problem, we can train a neural network to "feel" the structure of the problem and output a high-quality solution in a single, lightning-fast glance. The AI learns the "grammar" of the solution directly from the data, proving that you don't need to program the rules of the game if you can teach the computer to understand the game's structure.

Technical Summary: Graph Neural Networks are Heuristics

Problem Definition
The paper addresses the Euclidean Travelling Salesman Problem (TSP), a canonical combinatorial optimization problem where the goal is to find the shortest Hamiltonian cycle through a set of $n$ cities. The authors challenge the prevailing paradigm where Graph Neural Networks (GNNs) serve merely as auxiliaries—providing scores, guiding search, or imitating algorithms for classical solvers. Instead, the paper posits that a GNN can function as a standalone, learned heuristic. The specific challenge is to construct a complete tour in a single forward pass without relying on autoregressive decoding, reinforcement learning rewards, explicit search procedures (like beam search), or post-hoc local improvement (like 2-opt).

Methodology
The proposed method is a non-autoregressive, unsupervised GNN framework that learns to solve TSP instances directly from the problem's geometric structure.

Objective and Formulation:
The TSP is formulated as minimizing the trace of the product between the distance matrix $D$ and a permutation matrix $P$ transformed by a cyclic shift matrix $V$ . To enable end-to-end gradient-based optimization, the discrete permutation $P$ is relaxed to a soft permutation matrix $T$ using the Gumbel-Sinkhorn relaxation during training. The loss function is simply the expected tour length: $L_{TSP} = \langle D, TVT^\top \rangle$ . At inference, the soft permutation is converted to a hard permutation using the Hungarian algorithm.
Symmetry-Aware Feature Extraction:
To ensure the model respects the symmetries of the Euclidean group (permutation and translation invariance/equivariance), the authors introduce a deterministic feature extractor.
- Translation Invariance: City coordinates are centered by subtracting the mean.
- Canonical Frame: An orthonormal frame is constructed using the eigenvectors of the empirical covariance matrix of the centered points. This removes rotation and reflection ambiguities.
- Harmonic Encoding: Points are projected onto this canonical frame to derive intrinsic polar coordinates ( $r, \theta$ ). Angular information is encoded using $M$ Fourier harmonics ( $\sin(m\theta), \cos(m\theta)$ ), providing the GNN with rotation-invariant structural cues.
Network Architecture:
The core model is a Scattering-Attention Graph Neural Network (SCT-GNN). It combines diffusion-based representations (using graph operators derived from powers of a smoothed random-walk matrix) with learnable attention mechanisms that adaptively mix features across different diffusion scales. The network is permutation-equivariant by construction.
Ensemble Strategies for Diversity:
To generate solution diversity without training multiple models or performing iterative search, the paper employs two mechanisms within a single training trajectory:
- Monte Carlo (MC) Dropout: Dropout is applied during inference. By performing multiple stochastic forward passes with different dropout masks, the model generates diverse tours from a single trained instance.
- Snapshot Ensembling: Multiple checkpoints are saved at different epochs during a single training run. These snapshots, representing distinct points in the optimization landscape, are used jointly at inference. The best tour among the snapshots is selected.

Key Contributions

GNNs as Standalone Heuristics: The paper demonstrates that a GNN can be a complete heuristic, producing a valid tour in one forward pass without auxiliary search or refinement.
Unsupervised Learning: The model requires no ground-truth optimal solutions or reinforcement rewards; it learns solely by minimizing the tour length objective.
Global Structure Learning: By removing local greedy mechanisms and relying on a global Hamiltonian-cycle objective, the model learns non-local combinatorial constraints that purely local decision rules (like nearest-neighbor) miss.
Efficiency: The method achieves millisecond-scale inference on GPUs, offering a favorable quality-efficiency trade-off compared to classical heuristics and other learning-based approaches that rely on autoregressive decoding or search.

Results
Experiments were conducted on TSP instances with $n=100, 200,$ and $500$ nodes drawn from a uniform Euclidean distribution.

Performance vs. Greedy: The model consistently outperforms the Greedy Nearest-Neighbor (NN) baseline. For TSP100, the mean tour length improved from 9.67 (Greedy) to 8.18 (Deterministic GNN).
Performance vs. Classical Heuristics: The method significantly outperforms the Christofides heuristic on smaller instances (TSP100, TSP200) and matches it on TSP500, but with orders-of-magnitude lower inference time on GPUs.
Performance vs. Learning-Based Baselines: Compared to Reinforcement Learning (RL) and Supervised Learning (SL) baselines (e.g., GAT, GCN), the proposed method achieves competitive or superior optimality gaps (e.g., 4.39% gap on TSP100 vs. 2.48% for a strong RL baseline with beam search) while being significantly faster because it avoids autoregressive decoding and beam search.
Ensemble Effects: Both MC dropout and snapshot ensembling further reduce the optimality gap. The combination of both strategies yielded the best results (4.39% gap on TSP100, 8.25% on TSP200, 12.11% on TSP500) with inference times remaining in the millisecond regime (up to ~82ms for the combined ensemble on TSP500).

Significance and Claims
The paper claims that heuristics need not be hand-crafted rules or search procedures but can emerge directly from learning the structure of the problem. By formulating TSP as direct permutation learning with a differentiable Hamiltonian-cycle objective, the authors show that GNNs can internalize global combinatorial constraints. The significance lies in shifting the paradigm of combinatorial optimization: structural constraints and generative models can replace explicit search as the foundation for solving intractable problems. The results suggest that "learned heuristics" can rival or surpass classical engineered methods in both solution quality and computational efficiency, particularly when the cost of search is prohibitive. The work positions unsupervised GNNs as a new class of fast, learned heuristics for combinatorial optimization.