RsGCN: Rescaling Enhances Generalization of GCNs for Solving Scalable Traveling Salesman Problems
Neural traveling salesman problem (TSP) solvers face two critical challenges: poor generalization for scalable TSPs and high training costs. To address these challenges, we propose a new Rescaling Graph Convolutional Network (RsGCN). Focusing on the scale-dependent features (i.e., features varied with problem scales) related to nodes and edges that influence the sensitivity of GCNs to the problem scales, a Rescaling Mechanism in RsGCN enhances the generalization capability by (1) rescaling adjacent nodes to construct a subgraph with a uniform number of adjacent nodes for each node across various scales of TSPs, which stabilizes the graph message aggregation; (2) rescaling subgraph edges to adjust the lengths of subgraph edges to the same magnitude, which maintains numerical consistency. In addition, an efficient training strategy with a mixed-scale dataset and bidirectional loss is used in RsGCN. To fully exploit the heatmaps generated by RsGCN, we design an efficient post-search algorithm termed Re2Opt, in which a reconstruction process based on adaptive weight is incorporated to help avoid local optima. Based on a combined architecture of RsGCN and Re2Opt, our solver achieves remarkable generalization and low training cost: with only 3 epochs of training on the mixed-scale dataset containing instances with up to 100 nodes, it can be generalized successfully to 10K-node instances without any fine-tuning. Extensive experiments demonstrate our state-of-the-art performance across uniform distribution instances of 9 different scales from 20 to 10K nodes and 78 real-world instances from TSPLIB, while requiring the fewest learnable parameters and training epochs among neural competitors.
Code (0)
등록된 구현이 없습니다.
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
Modeling of spatially embedded networks via regional spatial graph convolutional networks
Efficient representation of complex infrastructure systems is crucial for system-level management tasks, such as edge prediction, component classification, and decision-making. However, the complex interactions between t…
Component ClassificationDecision MakingMultimodal Deep LearningRepresentation LearningTraining Lightweight Graph Convolutional Networks with Phase-field Models
In this paper, we design lightweight graph convolutional networks (GCNs) using a particular class of regularizers, dubbed as phase-field models (PFMs). PFMs exhibit a bi-phase behavior using a particular ultra-local term…
Spectral Multigraph Networks for Discovering and Fusing Relationships in Molecules
Spectral Graph Convolutional Networks (GCNs) are a generalization of convolutional networks to learning on graph-structured data. Applications of spectral GCNs have been successful, but limited to a few problems where th…
ClassificationGeneral ClassificationGraph ClassificationNode ClassificationBudget-Aware Graph Convolutional Network Design using Probabilistic Magnitude Pruning
Graph convolutional networks (GCNs) are nowadays becoming mainstream in solving many image processing tasks including skeleton-based recognition. Their general recipe consists in learning convolutional and attention laye…
Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization
Graph convolutional networks (GCNs) have emerged as powerful models for graph learning tasks, exhibiting promising performance in various domains. While their empirical success is evident, there is a growing need to unde…
Graph Learning