🤖 AI

GES-TSP: Graph Edge Sparsification for TSP

This paper introduces GES, a learning-based graph edge sparsification method for Euclidean TSP that adaptively reduces graph size by up to 99% while maintaining an optimality gap of less than 1%, significantly accelerating the solution of large-scale instances.

Original authors: Tianfeng Chen, Xianyue Li

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianfeng Chen, Xianyue Li

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

Imagine you are a delivery driver with a map of a whole city, and your boss says, "Visit every single house exactly once and come back home, but do it as fast as possible." This is the Traveling Salesman Problem (TSP). Now, imagine that map isn't just a list of houses; it's a giant web where every single house is connected to every other house by a direct road. If you have 1,000 houses, that's nearly a million roads to check! Trying to find the perfect route on a map that big is like trying to find a specific grain of sand in a desert while blindfolded—it takes forever and costs a fortune in computer power.

For a long time, people tried to solve this by using "fixed rules," like always picking the nearest neighbor or drawing triangles between points. It's a bit like saying, "I'll only look at the three closest houses to me," or "I'll only look at houses that form perfect triangles." The authors of this paper, Tianfeng Chen and Xianyue Li, say these old rules are too rigid. They don't pay attention to the specific quirks of this particular city. They might miss a shortcut or include a road that's actually a dead end.

The Big Idea: A Smart Filter
The authors propose a new trick called GES-TSP (Graph Edge Sparsification). Think of it as hiring a super-smart, AI-powered scout who looks at the entire messy web of roads and says, "Hey, 95% of these roads are useless for the best route. Let's throw them away and only keep the most promising ones."

Here is how their "scout" works, step-by-step:

The Rough Draft (Coarse Graph): First, the scout uses a classic geometry trick called "Delaunay triangulation." Imagine connecting dots on a piece of paper so that no dot is inside the circle of any triangle you draw. This instantly cuts out a huge chunk of the crazy long roads, leaving a much smaller, cleaner web. It's a good start, but not perfect.
The Smart Brain (GNN): Next, they feed this smaller web into a "Graph Neural Network" (GNN). You can think of this as a student who has studied thousands of previous delivery routes. The student looks at the roads and asks four specific questions about each one:
- How long is the road? (Short is usually better).
- Are these two houses neighbors? (Are they close by?).
- How does this road compare to the best road leaving this house? (Is it a "good" choice or a "bad" one?).
- What does the big picture say? (Does this road fit into the overall structure of the city?).
The Scorecard: Based on these questions, the AI gives every road a score. High scores mean "Keep this!" Low scores mean "Toss it!"
The Safety Net: To make sure they don't accidentally throw away the only road that connects two parts of the city, they add back a few specific roads found by an old-school algorithm called "Christofides." This guarantees that a valid route is always possible.

The Results: Cutting the Fat
When they tested this on the MATILDA dataset (a collection of 100-house city maps), the results were impressive. Their method managed to cut away 95% of the roads! That means instead of checking a million connections, the computer only had to check about 50,000. Even better, the route they found was still incredibly close to the perfect one—usually within 1% of the best possible answer.

They also tested it on the TSPLIB benchmark, which includes much bigger cities with up to 2,392 houses. On these giant maps, the method was even more aggressive, cutting away more than 99% of the roads, while still keeping the solution gap under 1%.

What They Rejected and What They Didn't
The authors were very clear about what didn't work well enough. They explicitly argued against relying solely on fixed geometric rules (like just picking the nearest neighbors) because those methods miss the specific "personality" of each map. They also noted that while some other AI methods try to build the whole route from scratch, those often struggle to generalize (work well on new, unseen maps) or are too complicated. Their approach is different: they don't build the route; they just clean up the map so a standard solver can find the route much faster.

How Sure Are They?
The authors are quite confident in their numbers because they ran actual experiments. They didn't just guess; they ran their method on real datasets (MATILDA and TSPLIB) and compared it directly against other methods like "SGN" and "Fitzpatrick."

On MATILDA: Their method consistently had the smallest error rate (optimality gap) and the highest road-cutting rate (pruning rate).
On TSPLIB: They showed that as the cities got bigger, their method got even better at cutting roads without losing accuracy.
Speed: Because they removed so many roads, the computer solved the problems much faster. In their tests, their method was the fastest of the bunch.

They also did a "what-if" test (an ablation study) where they removed parts of their system. When they took away the "Delaunay" rough draft, the performance dropped. When they took away the "smart questions" (the features), the performance dropped. This proves that every part of their system is actually doing important work.

The Bottom Line
The paper suggests that by mixing old-school geometry with a modern, learning-based AI that understands the specific shape of the problem, you can make solving these massive delivery puzzles much faster and easier. They haven't "solved" the Traveling Salesman Problem forever (it's still a tough nut to crack!), but they have shown a very effective way to shrink the problem down so it becomes manageable, even for huge cities. They are currently focused only on these specific types of maps (Euclidean TSP) and haven't tried it on other types of puzzles yet, but the results so far are very promising.

Technical Summary: GES-TSP: Graph Edge Sparsification for TSP

Problem Statement
The Traveling Salesman Problem (TSP), particularly the Euclidean variant (ETSP), is a classical NP-hard combinatorial optimization problem. While exact methods (e.g., CPLEX, SCIP) can solve instances to optimality, they become computationally prohibitive for large-scale instances due to the quadratic growth of edges ( $O(n^2)$ ) in the complete graph formulation. Traditional graph sparsification techniques, such as $k$ -nearest neighbor (KNN) graphs and Delaunay triangulation, reduce search spaces using fixed geometric heuristics. However, these methods often fail to fully exploit instance-specific structural information, leading to either redundant edges or the omission of critical problem-specific structures. Conversely, recent learning-based end-to-end TSP solvers often suffer from limited generalization and complex architectures. The core challenge addressed by this paper is how to adaptively generate a sparse graph that significantly reduces computational overhead while preserving high-quality solutions and maintaining strong generalization across different instance distributions.

Methodology
The authors propose GES-TSP (Graph Edge Sparsification for TSP), a learning-based framework that integrates geometric structures with Graph Neural Networks (GNNs) to identify promising edges. The methodology proceeds through four key stages:

Coarse Graph Construction: To mitigate the computational burden of training on complete graphs, the method first constructs a coarse sparse graph using Delaunay triangulation. This geometric structure preserves local proximity relationships and contains $O(n)$ edges, serving as a strong initial candidate set that is significantly smaller than the complete graph.
Feature Construction: The model utilizes a four-dimensional feature vector for each edge $(i, j)$ $(i, j)$ :
- Euclidean Distance ( $d_{ij}$ ): The fundamental cost metric.
- KNN Indicator ( $KNN_{ij}$ ): A binary feature indicating if nodes are mutual $k$ -nearest neighbors, capturing local density.
- Q-value ( $Q_{ij}$ ): A normalized metric comparing an edge's length to the shortest edge connected to node $i$ , providing a finer-grained measure of local edge quality than binary KNN.
- IMST (Iterative Minimum Spanning Tree): A global feature derived by iteratively computing and removing MSTs, normalized to ensure scale invariance across different graph sizes.
GNN Inference: A Graph Attention Network (GAT) is employed to predict edge importance. The model uses an attention mechanism to aggregate neighbor information, incorporating both node embeddings and the aforementioned edge features. The output is a score for each edge, trained as a binary classification task (edge inclusion in the optimal tour) using binary cross-entropy loss with class imbalance weighting.
Sparse Graph Generation and Solving: Edges are filtered based on a score threshold. Crucially, to guarantee the existence of a feasible solution, edges from a Christofides algorithm solution are forcibly included in the sparse graph. This ensures connectivity and the presence of at least one valid Hamiltonian cycle. The resulting sparse graph is then passed to an exact solver (SCIP) to compute the final tour.

Key Contributions

Hybrid Framework: The paper introduces a novel approach that combines deterministic geometric heuristics (Delaunay triangulation, Christofides) with data-driven learning (GAT) to create a robust sparsification pipeline.
Adaptive Feature Engineering: The authors propose a specific set of edge features, including the Q-value and normalized IMST, designed to capture both local structural quality and global graph properties effectively.
Feasibility Guarantee: Unlike some learning-based pruning methods that risk disconnecting the graph, GES-TSP integrates Christofides edges to mathematically guarantee that the pruned graph remains solvable.
Generalization: The method demonstrates strong generalization capabilities, performing well on both the synthetic MATILDA dataset and the real-world TSPLIB benchmark without retraining for specific instance sizes.

Experimental Results
Experiments were conducted on the MATILDA dataset (various distributions of 100-node instances) and the TSPLIB benchmark (instances ranging from 130 to 2392 nodes).

Pruning Rate: GES-TSP achieves significantly higher edge pruning rates compared to baseline methods (SGN and Fitzpatrick et al.). On the MATILDA dataset, it prunes up to 94% of edges. On large-scale TSPLIB instances (e.g., pcb1002, vm1748, pr2392), the pruning rate exceeds 99%.
Solution Quality: Despite aggressive pruning, the method maintains a tight optimality gap. On MATILDA, the average gap is 0.10% (vs. 0.68% for SGN and 0.17% for Fitzpatrick). On TSPLIB, the gap remains below 1% even for the largest instances.
Efficiency: The high pruning rates translate to significant speedups. GES-TSP consistently outperforms baselines in solving time, demonstrating that the reduced graph size allows exact solvers to run much faster.
Ablation Studies: Removing the Delaunay coarse filter or replacing it with KNN reduces the pruning rate by approximately 3–5%. Feature ablation confirms that KNN and IMST features are the most impactful, while the Q-value and distance features provide necessary refinements.

Significance and Claims
The paper claims that GES-TSP offers a practical and effective solution for scaling exact TSP solvers to large instances. By reducing the graph size by over 95% (and up to 99% in some cases) while keeping the solution gap within 1%, the method bridges the gap between the scalability of heuristics and the optimality guarantees of exact methods. The authors emphasize that their approach successfully leverages geometric structural information to guide learning, resulting in a system that generalizes well across different data distributions and problem scales. The work highlights the potential of integrating geometric heuristics with Graph Neural Networks for combinatorial optimization, though the authors modestly note that the current framework is limited to TSP and has not yet been extended to other combinatorial problems.

Technical Summary: GES-TSP: Graph Edge Sparsification for TSP

More like this