An edge-aware graph autoencoder trained on scale-imbalanced data for traveling salesman problems

Shiqing Liu, Xueming Yan, Yaochu Jin

Abstract

The Traveling Salesman Problem (TSP) is a cornerstone of combinatorial optimization, yet traditional exact solvers struggle with computational scalability. While Neural Combinatorial Optimization (NCO) has emerged as a promising alternative, existing models often suffer from poor generalization across different problem scales and are sensitive to the distribution of training data. This paper introduces EdgeGAE, an edge-aware graph autoencoder that reformulates the TSP as a link prediction task. By prioritizing edge-centric embeddings and employing a novel Active Sampling (AS) strategy, EdgeGAE effectively addresses scale imbalance and demonstrates superior zero-shot generalization to large-scale problems.

Introduction

The Traveling Salesman Problem (TSP)—finding the shortest possible route that visits a set of cities exactly once and returns to the origin—is a classic NP-hard problem. While exact solvers like Concorde can find optimal solutions, their execution time grows exponentially with the number of cities, making them impractical for real-time or extremely large-scale applications.

Neural Combinatorial Optimization (NCO) seeks to bridge this gap by using deep learning to approximate solutions rapidly. However, two significant challenges persist in the field:

  1. Scale Sensitivity: Models trained on small graphs (e.g., 50 nodes) often fail to maintain performance when applied to larger graphs (e.g., 500 nodes).
  2. Data Imbalance: High-quality, optimized training data for large-scale TSPs is computationally expensive to generate, leading to datasets dominated by small-scale instances. This imbalance often causes models to overfit to smaller problems.

Methodology

EdgeGAE shifts the paradigm of TSP solving from sequential path-finding (autoregressive) to a global link prediction task. This approach allows the model to evaluate the entire graph structure simultaneously.

Edge-Aware Architecture

Unlike standard Graph Neural Networks (GNNs) that focus on node-level features, EdgeGAE treats edges as first-class citizens.

  • Edge-Aware Encoder: Utilizing residual gated graph convolutions, the encoder learns explicit edge embeddings. Since the TSP is fundamentally defined by the distances (edges) between cities, this architecture captures the geometric essence of the problem more effectively than node-centric alternatives.
  • Edge-Centered Decoder: The decoder aggregates information from both source and target nodes back into the edge embeddings to predict the probability of an edge being part of the optimal tour.

Active Sampling (AS)

To combat the issue of scale imbalance, the authors developed the Active Sampling strategy. In a typical imbalanced dataset, small-scale problems are overrepresented. Active Sampling forces the training process to select problem sizes uniformly. By ensuring the model encounters rare, large-scale instances as frequently as common, small-scale ones, the model learns features that are invariant to the size of the graph.

Experimental Setup

The researchers evaluated EdgeGAE using a custom benchmark designed to simulate real-world data scarcity:

  • Training Data: 50,000 instances ranging from 50 to 500 cities, with a distribution heavily skewed toward smaller sizes.
  • Testing Data: Five scales (50, 100, 300, 500, and 700 cities). The 700-city test set serves as a "zero-shot" benchmark, as the model never encountered problems of this size during training.

Results and Discussion

EdgeGAE demonstrated significant improvements over baseline models such as GCN, GAT, and GatedGCN in several key areas:

Generalization and Accuracy

The model consistently achieved the lowest "Optimal Gap" (the percentage difference from the perfect solution found by an exact solver). Notably, its performance remained robust even on the 700-city test set, suggesting that the edge-aware features and Active Sampling allowed the model to learn generalizable optimization rules rather than simple pattern memorization.

Computational Efficiency

One of the most striking results was the inference speed. While the computation time for exact solvers increased exponentially with problem size, EdgeGAE’s inference time remained nearly constant. For a 700-city problem, EdgeGAE provided a solution in a fraction of a second, compared to approximately 25 seconds for an exact solver.

Non-Autoregressive Advantages

By treating the problem as link prediction, EdgeGAE avoids the "compounding error" problem inherent in autoregressive models, where a single incorrect node selection in a sequence can degrade the entire remaining path. Instead, EdgeGAE produces a probability heatmap for the entire graph, which is then refined into a valid tour.

Conclusion and Future Work

EdgeGAE represents a significant step forward in making neural solvers practical for real-world logistics and optimization. By focusing on edge embeddings and balancing the training scale, the model achieves high efficiency and impressive generalization.

Future research directions include:

  • Hybrid Learning: Integrating Reinforcement Learning to further narrow the optimality gap without relying on labeled optimal tours.
  • Federated Learning: Applying the model to distributed, private datasets to enable collaborative learning across different logistics entities without compromising data privacy.
  • Search Integration: Improving the post-hoc search algorithms (like 2-opt) used to convert the model's probability heatmaps into final valid tours.

Summary updated

Abstract

In recent years, there has been a notable surge in research on machine learning techniques for combinatorial optimization. It has been shown that learning-based methods outperform traditional heuristics and mathematical solvers on the Traveling Salesman Problem (TSP) in terms of both performance and computational efficiency. However, most learning-based TSP solvers are primarily designed for fixed-scale TSP instances, and also require a large number of training samples to achieve optimal performance. To fill this gap, this work proposes a data-driven graph representation learning method for solving TSPs with various numbers of cities. Specifically, we formulate the TSP as a link prediction task and propose an edge-aware graph autoencoder (EdgeGAE) model that can solve TSPs by learning from various-scale samples with an imbalanced distribution. A residual gated encoder is trained to learn latent edge embeddings, followed by an edge-centered decoder to output link predictions in an end-to-end manner. Furthermore, we introduce an active sampling strategy into the training process to improve the model’s generalization capability in large-scale scenarios. To investigate the model’s practical applicability, we generate a scale-imbalanced dataset comprising 50,000 TSP instances ranging from 50 to 500 cities. The experimental results demonstrate that the proposed edge-aware graph autoencoder model achieves a highly competitive performance among state-of-the-art graph learning-based approaches in solving TSPs with various scales, implying its remarkable potential in dealing with practical optimization challenges.
BibTeX
@article{liu2024edge,
  author = {Shiqing Liu and Xueming Yan and Yaochu Jin},
  title = {{An edge-aware graph autoencoder trained on scale-imbalanced data for traveling salesman problems}},
  journal = {Knowledge-Based Systems},
  year = {2024},
  doi = {10.1016/j.knosys.2024.111559},
}
Figure