GES-TSP: Graph Edge Sparsification for TSP

# GES-TSP: Graph Edge Sparsification for TSP
Source: [https://arxiv.org/html/2607.09708](https://arxiv.org/html/2607.09708)
Tianfeng Chen School of Mathematics and Statistics Lanzhou Universtiy chentf2025@lzu\.edu\.cn&Xianyue Li\* School of Mathematics and Statistics Lanzhou Universtiy lixianyue@lzu\.edu\.cn

###### Abstract

Solving large\-scale instances of the Traveling Salesman Problem \(TSP\) exactly is computationally expensive\. Researchers often employ graph sparsification methods to improve computational efficiency\. Traditional sparsification methods typically rely on fixed heuristics and fail to fully exploit instance\-specific structural information\. In this paper, we propose Graph Edge Sparsification \(GES\), a learning\-based sparsification approach for Euclidean TSP\. By incorporating geometric structural information and combinatorial optimization technology, our proposed method adaptively generates a sparsification graph for different instances, significantly reducing the graph size and accelerating the solving process\. Experimental results demonstrate that our sparsification method can prune up to 95% of edges on the MATILDA dataset, while keeping the solution gap within 1% of the optimal value\. Moreover, our approach exhibits strong generalization capability on the TSPLIB benchmark\.In some large\-scale instances, the pruning rate exceeds 99%, while the optimality gap remains below 1%\.

## 1Introduction

The Traveling Salesman Problem \(TSP\) is a classical NP\-hard combinatorial optimization problemJüngeret al\.\([1995](https://arxiv.org/html/2607.09708#bib.bib1)\)\. 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 sparsificationSpielman and Teng \([2011](https://arxiv.org/html/2607.09708#bib.bib2)\)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 thekk\-nearest neighbor \(KNN\) graphDe Berget al\.\([2008](https://arxiv.org/html/2607.09708#bib.bib3)\), where each node is connected to itskkclosest neighbors in terms of Euclidean distance\. Another widely adopted sparsification method is Delaunay triangulationXuet al\.\([2020](https://arxiv.org/html/2607.09708#bib.bib4)\), 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 TSPBresson and Laurent \([2021](https://arxiv.org/html/2607.09708#bib.bib9)\); Joshiet al\.\([2019](https://arxiv.org/html/2607.09708#bib.bib7)\); Vinyalset al\.\([2015](https://arxiv.org/html/2607.09708#bib.bib5)\); Belloet al\.\([2016](https://arxiv.org/html/2607.09708#bib.bib8)\); Kwonet al\.\([2020](https://arxiv.org/html/2607.09708#bib.bib6)\)\. 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\.

## 2Related works

Fitzpatrick et al\.Fitzpatricket al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib10)\)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\.Xinet al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib11)\)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\-kkedges with the highest scores are retained to construct a candidate edge set\. Tian et al\.Tianet al\.\([2024](https://arxiv.org/html/2607.09708#bib.bib12)\)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\.

## 3Preliminaries

### 3\.1TSP and Graph Sparsification

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

In this work, we focus on the Euclidean TSP \(ETSP\), where each vertexi∈Vi\\in Vis embedded in a 2D coordinatepi=\(xi,yi\)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 sparsificationHashemiet al\.\([2024](https://arxiv.org/html/2607.09708#bib.bib13)\)selects existing edges from the graphGG, and outputsG′G^\{\\prime\}=\(V,E′\)\(V,E^\{\\prime\}\), whereE′E^\{\\prime\}is the subset ofEE\. Our goal is to reduce the number of edges in the graph as much as possible while preserving high\-quality TSP solutions\.

### 3\.2GNNs

Graph Neural Networks \(GNNs\) are widely used for learning on graph\-structured dataScarselliet al\.\([2008](https://arxiv.org/html/2607.09708#bib.bib14)\); Huet al\.\([2020](https://arxiv.org/html/2607.09708#bib.bib20)\)\. 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\)Velickovicet al\.\([2018](https://arxiv.org/html/2607.09708#bib.bib15)\), which uses an attention mechanism to learn the importance of neighboring nodes adaptively\. For nodevvand its neighboru∈𝒩​\(v\)u\\in\\mathcal\{N\}\(v\), the attention coefficient is computed as:

ev​u=LeakyReLU​\(𝐚⊤​\[𝐖𝐡v​‖𝐖𝐡u‖​𝐖e​𝐫v​u\]\),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\),\(1\)where𝐡v\(l\)\\mathbf\{h\}\_\{v\}^\{\(l\)\}denotes the embedding of nodevv,𝒩​\(v\)\\mathcal\{N\}\(v\)denotes its neighbor set,𝐖\\mathbf\{W\}and𝐖e\\mathbf\{W\}\_\{e\}are learnable weight matrices,𝐚\\mathbf\{a\}is the attention vector,𝐫v​u\\mathbf\{r\}\_\{vu\}denotes edge features, and∥\\\|represents concatenation\. The normalized attention coefficients are then used to aggregate neighbor information:

𝐡v′=σ​\(∑u∈𝒩​\(v\)αv​u​𝐖𝐡u\)\.\\mathbf\{h\}\_\{v\}^\{\\prime\}=\\sigma\\left\(\\sum\_\{u\\in\\mathcal\{N\}\(v\)\}\\alpha\_\{vu\}\\mathbf\{W\}\\mathbf\{h\}\_\{u\}\\right\)\.\(2\)
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\.3Delaunay 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ℝ2\\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 tourXuet al\.\([2020](https://arxiv.org/html/2607.09708#bib.bib4)\)\. Moreover, the number of edges in the Delaunay triangulation is linear in the number of vertices, i\.e\.,𝒪​\(n\)\\mathcal\{O\}\(n\), which is significantly smaller than the𝒪​\(n2\)\\mathcal\{O\}\(n^\{2\}\)edges in the complete graph\.

### 3\.4Christofides algorithm

The Christofides algorithmChristofides \([2022](https://arxiv.org/html/2607.09708#bib.bib17)\)is a classical approximation algorithm for the TSP with a worst\-case approximation ratio of3/23/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 satisfiesc​\(C\)≤32​c​\(OPT\)c\(C\)\\leq\\frac\{3\}\{2\}c\(\\mathrm\{OPT\}\), wherec​\(OPT\)c\(\\mathrm\{OPT\}\)denotes the optimal tour length\.

## 4GES\-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 SCIPAchterberg \([2009](https://arxiv.org/html/2607.09708#bib.bib18)\)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 algorithmHelsgaun \([2015](https://arxiv.org/html/2607.09708#bib.bib19)\)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𝒪​\(n2\)\\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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/frame.png)Figure 1:Overview of the GES\-TSP and Solving Framework### 4\.1Coarse 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𝒪​\(n\)\\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\.2Features 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 nodeii, let𝒩k​\(i\)\\mathcal\{N\}\_\{k\}\(i\)denote the set of itskknearest neighbors\. For an edge\(i,j\)\(i,j\), we define a binary variable:

KNNi​j=\{1,if​j∈𝒩k​\(i\)​or​i∈𝒩k​\(j\),0,otherwise\.\\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\}\(3\)
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\)\(i,j\), it is defined as

Qi​j=1\+di​j1\+mink⁡di​k\.Q\_\{ij\}=\\frac\{1\+d\_\{ij\}\}\{1\+\\min\_\{k\}d\_\{ik\}\}\.\(4\)
Fitzpatrick et al\.Fitzpatricket al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib10)\)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 nodeii\. A smaller value indicates a more preferred connection\. Compared with the KNN feature, the Q\-value provides a finer\-grained measure of local edge qualitySunet al\.\([2020](https://arxiv.org/html/2607.09708#bib.bib21)\)\. 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\.Fitzpatricket al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib10)\)propose IMST features\. We iteratively compute the MST of the current graph, remove its edges, and assign each selected edge a weight of1/k1/kat iterationkk\. The process runs for at most⌈log⁡n⌉\\lceil\\log n\\rceiliterations 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 depthR=⌈log2⁡n⌉R=\\lceil\\log\_\{2\}n\\rceildepends on graph size, causing the accumulated IMST weights to grow withnn\. 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\.

ei​j=\[di​j,KNNi​j,IMSTi​j,Qi​j\]e\_\{ij\}=\[d\_\{ij\},\\text\{KNN\}\_\{ij\},\\text\{IMST\}\_\{ij\},\\text\{Q\}\_\{ij\}\]\(5\)

### 4\.3GNN 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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/GAT1.png)Figure 2:Architecture of the Proposed GNNs Model
### 4\.4Sparse Graph

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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/clkhard_070_sparse_solution_compare.png)Figure 3:Sparse Graph for a TSP Instance

## 5Experiments 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\.1Comparative 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\.Xinet al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib11)\)propose an SGN\-based framework, which uses GNNs to score edges and constructs a sparse candidate set by retaining the top\-kkhighest\-scoring edges for each node\. Fitzpatrick et al\.Fitzpatricket al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib10)\)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 inFitzpatricket al\.\([2021](https://arxiv.org/html/2607.09708#bib.bib10)\)\)\.

Table 1:Optimality Gap Comparison of TSP Solving on the MATILDATable 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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/tspchart.png)Figure 4:Optimality Gap Comparison of TSP Solving on the TSPLIBFigure 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:Pruning Rate Comparison of TSP Solving on the MATILDATable 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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/pruning.png)Figure 5:Pruning Rate Comparison of TSP Solving on the TSPLIB![Refer to caption](https://arxiv.org/html/2607.09708v1/MATILDA_speedup.png)Figure 6:Average speed\-up on the MATILDAAfter 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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/clkhard_090_complete_graph_edge_score_distribution.png)Figure 7:Distribution of Edge Prediction Scores
### 5\.2Ablation 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%\.

Table 3:Pruning Rate Comparison with Different Coarse Filtering StrategiesSection 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\.

![Refer to caption](https://arxiv.org/html/2607.09708v1/wo.png)Figure 8:Ablation Results of Edge FeaturesAfter 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\.

## 6Conclusion

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\.

## References

- \[1\]\(2009\)SCIP: solving constraint integer programs\.Mathematical Programming Computation1\(1\),pp\. 1–41\.Cited by:[§4](https://arxiv.org/html/2607.09708#S4.p1.1)\.
- \[2\]I\. Bello, H\. Pham, Q\. V\. Le, M\. Norouzi, and S\. Bengio\(2016\)Neural combinatorial optimization with reinforcement learning\.arXiv preprint arXiv:1611\.09940\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p4.1)\.
- \[3\]X\. Bresson and T\. Laurent\(2021\)The transformer network for the traveling salesman problem\.arXiv preprint arXiv:2103\.03012\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p4.1)\.
- \[4\]N\. Christofides\(2022\)Worst\-case analysis of a new heuristic for the travelling salesman problem\.InOperations Research Forum,Vol\.3,pp\. 20\.Cited by:[§3\.4](https://arxiv.org/html/2607.09708#S3.SS4.p1.3)\.
- \[5\]M\. De Berg, O\. Cheong, M\. Van Kreveld, and M\. Overmars\(2008\)Computational geometry: algorithms and applications\.Springer\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p3.2)\.
- \[6\]J\. Fitzpatrick, D\. Ajwani, and P\. Carroll\(2021\)Learning to sparsify travelling salesman problem instances\.InInternational Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research,pp\. 410–426\.Cited by:[§2](https://arxiv.org/html/2607.09708#S2.p1.1),[§4\.2](https://arxiv.org/html/2607.09708#S4.SS2.p6.1),[§4\.2](https://arxiv.org/html/2607.09708#S4.SS2.p7.5),[§5\.1](https://arxiv.org/html/2607.09708#S5.SS1.p1.1),[§5\.1](https://arxiv.org/html/2607.09708#S5.SS1.p2.1)\.
- \[7\]M\. Hashemi, S\. Gong, J\. Ni, W\. Fan, B\. A\. Prakash, and W\. Jin\(2024\)A comprehensive survey on graph reduction: sparsification, coarsening, and condensation\.Cited by:[§3\.1](https://arxiv.org/html/2607.09708#S3.SS1.p4.5)\.
- \[8\]K\. Helsgaun\(2015\)Solving the equality generalized traveling salesman problem using the lin–kernighan–helsgaun algorithm\.Mathematical Programming Computation7\(3\),pp\. 269–287\.Cited by:[§4](https://arxiv.org/html/2607.09708#S4.p1.1)\.
- \[9\]W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. Leskovec\(2020\)Open graph benchmark: datasets for machine learning on graphs\.Advances in neural information processing systems33,pp\. 22118–22133\.Cited by:[§3\.2](https://arxiv.org/html/2607.09708#S3.SS2.p1.1)\.
- \[10\]C\. K\. Joshi, T\. Laurent, and X\. Bresson\(2019\)An efficient graph convolutional network technique for the travelling salesman problem\.arXiv preprint arXiv:1906\.01227\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p4.1)\.
- \[11\]M\. Jünger, G\. Reinelt, and G\. Rinaldi\(1995\)The traveling salesman problem\.Handbooks in operations research and management science7,pp\. 225–330\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p1.1)\.
- \[12\]Y\. Kwon, J\. Choo, B\. Kim, I\. Yoon, Y\. Gwon, and S\. Min\(2020\)Pomo: policy optimization with multiple optima for reinforcement learning\.Advances in neural information processing systems33,pp\. 21188–21198\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p4.1)\.
- \[13\]F\. Scarselli, M\. Gori, A\. C\. Tsoi, M\. Hagenbuchner, and G\. Monfardini\(2008\)The graph neural network model\.IEEE transactions on neural networks20\(1\),pp\. 61–80\.Cited by:[§3\.2](https://arxiv.org/html/2607.09708#S3.SS2.p1.1)\.
- \[14\]D\. A\. Spielman and S\. Teng\(2011\)Spectral sparsification of graphs\.SIAM Journal on Computing40\(4\),pp\. 981–1025\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p2.1)\.
- \[15\]Y\. Sun, A\. Ernst, X\. Li, and J\. Weiner\(2020\)Generalization of machine learning for problem reduction: a case study on travelling salesman problems\.arXiv preprint arXiv:2005\.05847\.Cited by:[§4\.2](https://arxiv.org/html/2607.09708#S4.SS2.p6.1)\.
- \[16\]H\. Tian, S\. Medya, and W\. Ye\(2024\)Combhelper: a neural approach to reduce search space for graph combinatorial problems\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 20812–20820\.Cited by:[§2](https://arxiv.org/html/2607.09708#S2.p1.1)\.
- \[17\]P\. Velickovic, G\. Cucurull, A\. Casanova, A\. Romero, P\. Lio, and Y\. Bengio\(2018\)GRAPH attention networks\.stat1050,pp\. 4\.Cited by:[§3\.2](https://arxiv.org/html/2607.09708#S3.SS2.p2.2)\.
- \[18\]O\. Vinyals, M\. Fortunato, and N\. Jaitly\(2015\)Pointer networks\.Advances in neural information processing systems28\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p4.1)\.
- \[19\]L\. Xin, W\. Song, Z\. Cao, and J\. Zhang\(2021\)Neurolkh: combining deep learning model with lin\-kernighan\-helsgaun heuristic for solving the traveling salesman problem\.Advances in Neural Information Processing Systems34,pp\. 7472–7483\.Cited by:[§2](https://arxiv.org/html/2607.09708#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.09708#S5.SS1.p1.1)\.
- \[20\]X\. Xu, J\. Li, and M\. Zhou\(2020\)Delaunay\-triangulation\-based variable neighborhood search to solve large\-scale general colored traveling salesman problems\.IEEE Transactions on Intelligent Transportation Systems22\(3\),pp\. 1583–1593\.Cited by:[§1](https://arxiv.org/html/2607.09708#S1.p3.2),[§3\.3](https://arxiv.org/html/2607.09708#S3.SS3.p2.2)\.

## Appendix ATechnical Appendices and Supplementary Material

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

Table 4:Optimality Gap Comparison of TSP Solving on the TSPLIBTable 5:Pruning Rate Comparison of TSP Solving on the TSPLIBTable 6:Ablation Results of Edge FeaturesTable 7:Impact of Christofides Edge Augmentation on Feasibility![Refer to caption](https://arxiv.org/html/2607.09708v1/time1.png)\(a\)small\-scale TSP instances
![Refer to caption](https://arxiv.org/html/2607.09708v1/time2.png)\(b\)large\-scale TSP instances

Figure 9:Comparison of running times on the TSPLIB