  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.
