1 Introduction↩︎

The Traveling Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem [1]. Exact methods are computationally expensive and often require lots of time to solve large-scale instances. As a fundamental benchmark problem in combinatorial optimization, the Euclidean TSP has been extensively studied due to its broad applications in transportation planning, circuit design, and routing systems. Improving the efficiency of solving Euclidean TSP instances is therefore of both theoretical and practical significance. In particular, Euclidean TSP instances are typically formulated on complete graphs, where the number of edges grows quadratically with the number of nodes, leading to significant computational overhead in exact or high-quality approximate solvers.

Graph sparsification [2] is a widely used strategy to reduce the computational complexity of TSP instances by restricting the search space to a subset of candidate edges. Traditional approaches are mainly based on geometric heuristics, which construct sparse graphs without exploiting instance-specific information.

One of the most commonly used sparsification techniques is the \(k\)-nearest neighbor (KNN) graph [3], where each node is connected to its \(k\) closest neighbors in terms of Euclidean distance. Another widely adopted sparsification method is Delaunay triangulation [4], which constructs a planar graph by maximizing the minimum angle of all triangles. Delaunay graphs possess strong geometric properties and are known to contain many edges of optimal Euclidean TSP tours in practice. However, although it provides a more structured sparsification compared to KNN graphs, it still includes redundant edges or miss problem-specific structures in certain distributions.

In recent years, learning-based end-to-end approaches have been proposed for TSP [5]–[9]. These methods directly learn to construct tours from data, typically using sequence models or attention-based architectures. However, they often exhibit limited generalization capability and involve complex model architectures with a large number of parameters.

Recent studies have explored learning-based approaches for graph sparsification. Instead of directly constructing tours, these methods aim to identify a subset of promising edges that are likely to appear in high-quality solutions. In particular, Graph Neural Networks (GNNs) can leverage node and edge features to predict edge importance, enabling the construction of sparse graphs that significantly reduce computational complexity while preserving solution quality.

2 Related works↩︎

Fitzpatrick et al. [10] propose a learning-based method that reformulates the TSP sparsification problem as a binary classification task, with the aim of retaining edges that are likely to appear in the optimal tour. They extract a variety of edge features to characterize the structural and geometric properties of the graph. Based on these features, they use traditional machine learning models, such as logistic regression and support vector machines, to predict the importance of edges, typically formulated as a binary classification problem. Xin et al. [11] propose an Sparse Graph Network (SGN) framework to construct a sparse candidate edge set to improve the Lin-Kernighan-Helsgaun (LKH) heuristic. They use node coordinates as node features and Euclidean distances as edge features. Based on these inputs, they use proposed SGN to predict edge scores. Afterwards, for each node, only the top-\(k\) edges with the highest scores are retained to construct a candidate edge set. Tian et al. [12] also use GNNs for graph sparsification, but their approach mainly focuses on the Vertex Cover and Maximum Independent Set problems. However, these methods either suffer from limited generalization capability or fail to fully exploit structural information of the graph.

In this paper, we propose GES, a learning-based sparsification approach that effectively captures structural information and instance-specific graph data, and integrates combinatorial optimization techniques to improve both efficiency and solution quality.

3 Preliminaries↩︎

3.1 TSP and Graph Sparsification↩︎

The TSP seeks a shortest tour that visits each vertex exactly once and returns to the starting point. Given a weighted graph \(G=(V,E)\), the goal is to find a Hamiltonian cycle with minimum total cost, where each edge \((i,j)\) is associated with a cost \(c_{ij}\).

In this work, we focus on the Euclidean TSP (ETSP), where each vertex \(i \in V\) is embedded in a 2D coordinate \(p_i=(x_i,y_i)\), and edge costs are defined as Euclidean distances between points.

Since the Euclidean TSP is defined on a complete graph, the number of edges increases rapidly as the number of vertices grows. As a result, solving the problem to optimality using exact solvers can be computationally expensive, especially for large-scale instances. This motivates the use of graph sparsification techniques to reduce the problem size while preserving solution quality.

Graph sparsification [13] selects existing edges from the graph \(G\), and outputs \(G'\)=\((V,E')\), where \(E'\) is the subset of \(E\). Our goal is to reduce the number of edges in the graph as much as possible while preserving high-quality TSP solutions.

3.2 GNNs↩︎

Graph Neural Networks (GNNs) are widely used for learning on graph-structured data [14], [15]. Typical GNNs update node representations through iterative message passing, where each node aggregates information from its neighbors.

Among various GNNs architectures, this paper adopts the Graph Attention Network (GAT) [16], which uses an attention mechanism to learn the importance of neighboring nodes adaptively. For node \(v\) and its neighbor \(u \in \mathcal{N}(v)\), the attention coefficient is computed as: \[e_{vu} = \text{LeakyReLU}\left( \mathbf{a}^{\top} [\mathbf{W} \mathbf{h}_v \| \mathbf{W} \mathbf{h}_u \| \mathbf{W}_e \mathbf{r}_{vu}] \right),\] where \(\mathbf{h}_v^{(l)}\) denotes the embedding of node \(v\), \(\mathcal{N}(v)\) denotes its neighbor set, \(\mathbf{W}\) and \(\mathbf{W}_e\) are learnable weight matrices, \(\mathbf{a}\) is the attention vector, \(\mathbf{r}_{vu}\) denotes edge features, and \(\|\) represents concatenation. The normalized attention coefficients are then used to aggregate neighbor information: \[\mathbf{h}_v' = \sigma\left( \sum_{u \in \mathcal{N}(v)} \alpha_{vu} \mathbf{W} \mathbf{h}_u \right).\]

Compared with traditional GNNs, GAT can better capture the relative importance of different neighbors, making it particularly suitable for graph optimization problems such as the TSP.

3.3 Delaunay Triangulation↩︎

The Delaunay triangulation is a fundamental structure in computational geometry that provides a sparse graph representation for a set of points in the plane. Given a set of points in \(\mathbb{R}^2\), the Delaunay triangulation constructs a triangulation such that no point lies inside the circumcircle of any triangle.

An important property of the Delaunay triangulation is that it preserves proximity relationships between points and contains many edges that are likely to appear in the optimal Euclidean TSP tour [4]. Moreover, the number of edges in the Delaunay triangulation is linear in the number of vertices, i.e., \(\mathcal{O}(n)\), which is significantly smaller than the \(\mathcal{O}(n^2)\) edges in the complete graph.

3.4 Christofides algorithm↩︎

The Christofides algorithm [17] is a classical approximation algorithm for the TSP with a worst-case approximation ratio of \(3/2\). It first computes a Minimum Spanning Tree (MST), which is a connected subgraph spanning all vertices with minimum total edge weight. Then, a minimum-weight perfect matching is constructed on the odd-degree vertices of the MST, where each selected vertex is matched exactly once with minimum total matching cost. By combining the MST and matching edges, an Eulerian graph is obtained, i.e., a graph containing a closed trail that traverses every edge exactly once. Finally, repeated vertices in the Eulerian tour are shortcut to produce a Hamiltonian cycle. The resulting tour satisfies \(c(C)\le \frac{3}{2}c(\mathrm{OPT})\), where \(c(\mathrm{OPT})\) denotes the optimal tour length.

4 GES-TSP↩︎

Common approaches for solving the TSP include exact methods, heuristic methods, and approximation algorithms. Exact methods typically rely on optimization solvers such as CPLEX and SCIP [18] to obtain optimal solutions, but they are computationally expensive and do not scale well to large instances. Compared to exact methods, heuristic approaches are more scalable and can efficiently produce high-quality solutions for large-scale instances, among which the LKH algorithm [19] is one of the most effective. Approximation algorithms provide theoretical performance guarantees and can compute solutions within a bounded ratio of the optimum in polynomial time.

Most methods of TSP operate on the complete graph, leading to significant computational overhead due to the \(\mathcal{O}(n^2)\) number of edges. This motivates the use of graph sparsification techniques to reduce the problem size. In particular, our GES-TSP offers a promising data-driven approach to identify relevant edges and enable efficient TSP solving. Figure 1 shows the overview of the GES-TSP and solving framework.

4.1 Coarse Graph↩︎

To reduce the computational burden of solving the TSP and training GNNs models on a complete graph, we first perform a coarse graph sparsification based on geometric structures.

Specifically, given a set of points in the Euclidean plane, we construct the Delaunay triangulation, which provides a sparse graph that preserves important proximity relationships between vertices. The Delaunay graph contains \(\mathcal{O}(n)\) edges and is known to retain many edges that are likely to appear in high-quality TSP tours.

By leveraging the Delaunay triangulation, we obtain an initial sparse graph that significantly reduces the number of edges while preserving local geometric structure. This coarse graph serves as a strong candidate edge set and provides a more efficient input for subsequent learning-based refinement using GNNs.

4.2 Features Construction↩︎

After obtaining the coarse graph, we construct feature representations for both nodes and edges. Node features are defined as normalized coordinates, while edge features are carefully designed to capture structural information, since TSP primarily depends on edge selection.

In the Euclidean TSP, the cost of an edge is determined by the Euclidean distance between two nodes. We directly use this distance as a fundamental edge feature. In optimal tours, shorter edges are significantly more likely to be included, while longer edges are rarely selected. However, distance alone is insufficient. It does not capture local structure and may not work well in regions with different node densities. This limitation motivates the incorporation of additional features.

We choose the KNN feature as the second edge feature. For each node \(i\), let \(\mathcal{N}_k(i)\) denote the set of its \(k\) nearest neighbors. For an edge \((i,j)\), we define a binary variable: \[\text{KNN}_{ij} = \begin{cases} 1, & \text{if } j \in \mathcal{N}_k(i) \text{ or } i \in \mathcal{N}_k(j), \\ 0, & \text{otherwise}. \end{cases}\]

This feature shows whether two nodes are close and provides local structure information. It helps the model handle regions with different densities.

While the KNN feature captures whether two nodes are locally close, it only provides a binary signal and cannot reflect the relative quality of edges. To address this limitation, we introduce stronger local features. For an edge \((i,j)\), it is defined as \[Q_{ij} = \frac{1 + d_{ij}}{1 + \min_{k} d_{ik}}.\]

Fitzpatrick et al. [10] constructs six local features. In this work, we simplify them into one feature. This feature measures how good an edge is compared with the shortest edge of node \(i\). A smaller value indicates a more preferred connection. Compared with the KNN feature, the Q-value provides a finer-grained measure of local edge quality [20]. It does not only indicate whether two nodes are close, but also reflects how much worse an edge is relative to the best local choice. This makes it more informative for edge selection.

Finally, we also need global features to fully describe the structure of a graph. Fitzpatrick et al. [10] propose IMST features. We iteratively compute the MST of the current graph, remove its edges, and assign each selected edge a weight of \(1/k\) at iteration \(k\). The process runs for at most \(\lceil \log n \rceil\) iterations or until the graph becomes disconnected. Finally, all edge weights are normalized over the accumulated edge set. In our method, the IMST feature is further normalized to ensure numerical stability across different graph sizes. The iteration depth \(R = \lceil \log_2 n \rceil\) depends on graph size, causing the accumulated IMST weights to grow with \(n\). Without normalization, this leads to scale-inconsistent features and unstable GNNs training across graphs of different sizes. Therefore, we normalize the IMST weights to make the feature scale-invariant and reflect only the relative importance of edges.

Therefore, each edge is represented by a four-dimensional feature vector. \[e_{ij}=[d_{ij},\text{KNN}_{ij}, \text{IMST}_{ij}, \text{Q}_{ij}]\]

4.3 GNN Model Inference↩︎

We use GAT to predict the importance of edges in the TSP graph. First, each node coordinate is mapped into a hidden representation using a linear transformation. Then, we apply a GAT-based message passing network. In each layer, node representations are updated by aggregating information from neighboring nodes, while edge features are incorporated during the message passing process. ReLU activation is applied after each layer.

After message passing, we construct an edge representation by concatenating the source node embedding, the target node embedding, and the corresponding edge features. This representation is then fed into a multi-layer perceptron (MLP), which outputs a score for each edge. Higher scores indicate a higher likelihood of being included in the optimal tour. The model is trained as a binary edge classification problem using the binary cross-entropy loss with logits. Figure 2 shows the overall training pipeline of the proposed method.

4.4 Sparse32Graph↩︎

Now we obtain the predicted scores for all edges in the full graph. These scores reflect how likely each edge is to be part of the optimal tour. We then use these scores to build a sparse graph. A threshold is applied to filter edges: edges with scores higher than the threshold are kept, while the others are removed. In this way, we keep only a small set of candidate edges. This step greatly reduces the number of edges in the graph. At the same time, most important edges are still kept, since they usually receive higher scores from the model. Therefore, the graph becomes much smaller but still contains the key structure of the original problem.

To ensure that a feasible solution always exists, we further include the edges from the Christofides algorithm solution. These edges guarantee that the sparse graph remains connected and contains at least one valid tour.

The sparse graph is then passed to an optimization solver to compute the final TSP solution. Since the graph is smaller, the solver can run faster and use less memory. This makes it possible to handle larger problem instances more efficiently. Figure 3 shows a sparse graph for a TSP instance (CLKhard 070). Orange edges appear only in the sparse-graph solution, blue edges appear only in the global optimum. Red edges are shared by both tours.

5 Experiments and Results↩︎

All experiments are implemented in Python 3.12, and the optimization is performed using SCIP. All computations were performed on a Dell laptop running Windows 11 with 15.8 GB of RAM, an Intel® Core™ i7-10870H 2.60GHz CPU and an NVIDIA GeForce RTX 3060 Laptop GPU. We use a GATv2-based graph neural network to perform binary classification on candidate TSP edges. The model consists of 3 GATv2Conv layers with hidden dimension 64 and 4 attention heads. Edge prediction is performed by concatenating node embeddings and edge features, followed by an MLP with dropout rate 0.1. The network is trained using the Adam optimizer with learning rate 0.001, batch size 4, and 50 training epochs. To address class imbalance, BCEWithLogitsLoss with positive class weight 30 is adopted.

5.1 Comparative study on TSP↩︎

We primarily evaluate the performance of GES-TSP on the MATILDA and TSPLIB benchmarks, we consider instances ranging from ch130 to pr2392, since optimal solution files are not available for larger instances beyond pr2392. and compare it with two representative baseline methods from the existing literature. Xin et al. [11] propose an SGN-based framework, which uses GNNs to score edges and constructs a sparse candidate set by retaining the top-\(k\) highest-scoring edges for each node. Fitzpatrick et al. [10] formulate graph sparsification as a binary edge classification problem and employ classical machine learning models to construct a sparse graph.

The MATILDA dataset consists of seven categories, each containing 190 instances of 100-node 2D Euclidean TSP problems. We use one third of the CLKhard and LKCChard instances for training, and the rest for validation and testing (the same as in [10]).

Table 1 presents the optimality gap of the three methods with respect to the optimal solutions. Except for CLKeasy and LKCCeasy, GES consistently outperforms the other methods by achieving the lowest optimality gap across all remaining datasets. On more challenging datasets such as CLKhard and LKCChard, our method significantly outperforms SGN and consistently improves upon Fitzpatrick. On simpler datasets such as CLKeasy and LKCCeasy, all methods achieve near-optimal solutions, leaving limited room for improvement.

Figure 4 shows the optimality gap of different methods on TSPLIB instances. Our method consistently achieves the lowest optimality gap across all instances. Compared with SGN, our method significantly reduces the gap, especially on larger and more challenging instances such as tsp225 and vm1748, etc. Compared with Fitzpatrick, our method still demonstrates consistent improvements, particularly on large-scale instances including pcb1002, vm1748, and pr2392. Moreover, the performance advantage becomes more pronounced as the problem size increases, indicating strong scalability. Overall, our method maintains a stable and near-optimal performance across all instances, demonstrating excellent generalization capability.

Table 2 reports the pruning rate of different methods on the MATILDA dataset. GES consistently achieves the highest pruning rate across all datasets. Compared with SGN and Fitzpatrick, GES significantly increases the pruning rate while maintaining stability across different instance types. In particular, the improvement over Fitzpatrick is significant on harder datasets such as CLKhard and LKCChard. Although SGN achieves a relatively high pruning rate, Table 1 shows that it suffers from a larger optimality gap.

We further evaluate the pruning rate on TSPLIB instances to assess the generalization ability of our method. As shown in Figure 5, GES consistently achieves the highest pruning rate across all TSPLIB instances. Compared with SGN and Fitzpatrick, our method maintains a clear advantage, especially on large-scale instances such as pcb1002, vm1748, and pr2392, where the pruning rate exceeds 99%. In contrast, although SGN also achieves relatively high pruning rates, it remains consistently lower than GES, while Fitzpatrick shows a more noticeable gap. Moreover, the pruning rate of GES remains highly stable across instances of varying scales, demonstrating strong robustness and generalization beyond the training distribution.

After showing that our method achieves superior solution quality and higher pruning rates, we further analyze the solving time of the three methods. Figure 6 shows the average speedup of the three methods on the MATILDA dataset compared to directly solving the original graph. It can be observed that GES consistently achieves the best speedup performance, followed by SGN, while Fitzpatrick performs the worst. This ranking is highly consistent with the pruning rate patterns we obtained.

Figure 7 illustrates the distribution of edge prediction scores generated by the GNNs model. Kernel Density Estimation (KDE) is employed to provide a smooth approximation of the underlying distributions. The blue curve denotes the distribution over all edges, the red curve corresponds to positive edges (i.e., edges belonging to the optimal tour), and the green curve represents negative edges.

It can be observed that most edges receive low scores (below 0.2), while a relatively small proportion of edges are assigned high scores (above 0.8). This aligns with the class imbalance in the complete TSP graph, where the number of negative edges far exceeds that of positive ones. Moreover, positive edges are predominantly concentrated near 1, while negative edges cluster around 0, indicating that the model exhibits strong discriminative capability in identifying edges that are likely to belong to the optimal tour.

5.2 Ablation Study↩︎

We first conduct a comparative study on different coarse filtering strategies. Table 3 shows the differences in the pruning rate when removing the Delaunay triangulation and replacing it with a KNN-based coarse filtering strategy. It can be observed that, without the Delaunay triangulation, the overall pruning rate decreases by approximately 5%. When the Delaunay triangulation is replaced with a KNN-based coarse filtering strategy, as adopted in SGN, the pruning rate decreases by approximately 3%.

Section 4.2 introduces four types of edge features. To assess the impact of each feature, we carry out separate ablation studies on the TSPLIB benchmark dataset. Figure 8 illustrates the optimality gap variations under different feature ablation settings. The results indicate that all feature types contribute positively to the model performance. The KNN-based feature exhibits the most significant impact, consistent with its role as a widely used heuristic in TSP. The distance feature shows a relatively smaller effect, likely due to its inherent correlation with the KNN. In comparison, the Q-value feature, which acts as an additional refinement over KNN, has the least influence. The IMST feature, as a global edge feature, also plays an important role and shows a relatively large influence on performance.

After selecting edges based on the threshold, we further incorporate the edges from the Christofides algorithm solution. As shown in Table 7 in appendices, without these additional edges, some instances may fail to admit a Hamiltonian cycle. In particular, for harder instances such as CLKhard and LKCChard, the number of infeasible cases increases significantly when Christofides-based augmentation is not applied.

6 Conclusion↩︎

In this paper, we propose GES, a learning-based graph sparsification framework for the Euclidean Traveling Salesman Problem. By combining geometric structures with data-driven learning, our method effectively reduces the size of the candidate edge set while preserving high-quality solutions.

Extensive experiments on the MATILDA and TSPLIB benchmarks demonstrate that GES consistently achieves superior performance compared to existing methods. Our approach attains higher pruning rates—often exceeding 95% and even 99% on large-scale instances, while maintaining an optimality gap within 1%. Moreover, the results show that GES generalizes well across different datasets and significantly accelerates the solving process, especially for large-scale problems. However, our current framework is limited to solving the TSP and has not yet been extended to other combinatorial optimization problems.

Overall, this work highlights the effectiveness of integrating geometric heuristics with graph neural networks for combinatorial optimization. In future work, we plan to explore more advanced GNNs architectures and extensions to other combinatorial optimization problems.

7 Technical Appendices and Supplementary Material↩︎

This appendix supplements the line charts in the main text by reporting the corresponding detailed numerical results in tabular form.

References↩︎