RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems

• URL: http://arxiv.org/abs/2506.00533v4
• Date: Fri, 26 Sep 2025 02:01:49 GMT
• Title: RsGCN: Subgraph-Based Rescaling Enhances Generalization of GCNs for Solving Traveling Salesman Problems
• Abstract summary: GCN-based traveling salesman problem (TSP) solvers face two critical challenges: poor cross-scale generalization for TSPs and high training costs.<n>We propose a Subgraph-Based Rescaling Graph Convolutional Network (RsGCN)<n>Under a unified subgraph perspective, RsGCN can efficiently learn scale-generalizable representations from small-scale TSPs at low cost.<n>Based on a combined architecture of RsGCN and RBS, our solver achieves remarkable generalization and low training cost.
• Score: 10.605940576092507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: GCN-based traveling salesman problem (TSP) solvers face two critical challenges: poor cross-scale generalization for TSPs and high training costs. To address these challenges, we propose a Subgraph-Based Rescaling Graph Convolutional Network (RsGCN). Focusing on the scale-dependent features (i.e., features varied with problem scales) related to nodes and edges, we design the subgraph-based rescaling to normalize edge lengths of subgraphs. Under a unified subgraph perspective, RsGCN can efficiently learn scale-generalizable representations from small-scale TSPs at low cost. To exploit and assess the heatmaps generated by RsGCN, we design a Reconstruction-Based Search (RBS), in which a reconstruction process based on adaptive weight is incorporated to help avoid local optima. Based on a combined architecture of RsGCN and RBS, our solver achieves remarkable generalization and low training cost: with only 3 epochs of training on a 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 advanced 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.

Related papers

• GeoRouteNet: Geometry-Enhanced Non-Autoregressive Neural Solver for the Traveling Salesman Problem [5.202950948929751]
  GeoRouteNet is a geometry-enhanced neural solver for Euclidean traveling salesman problem (TSP)<n>On the model side, GeoRouteNet incorporates centered node features, learnable radial distance basis functions, distance-aware graph attention, LayerNorm-SwiGLU feed-forward blocks, and cross-layer attentive residual encoder mixing.<n>On the training side, we design multi-candidate self-comparison reinforcement learning (MCS-RL), which samples multiple candidate tours per instance.
  arXiv  Detail & Related papers  (2026-06-22T02:31:22Z)
• Learning to Reduce Search Space for Generalizable Neural Routing Solver [12.396576646539252]
  Constructive neural optimization (NCO) has attracted growing research attention due to its ability to solve complex routing problems without relying on handcrafted rules.<n>Existing NCO methods face challenges in generalizing to large-scale problems due to high computational complexity and inefficient capture of structural patterns.<n>We propose a novel learning-based search space reduction method that adaptively selects a small set of promising candidate nodes at each step of the constructive NCO process.
  arXiv  Detail & Related papers  (2025-03-05T03:25:09Z)
• TSC: A Simple Two-Sided Constraint against Over-Smoothing [17.274727377858873]
  We introduce a simple Two-Sided Constraint (TSC) for Graph Convolutional Neural Network (GCN) The random masking acts on the representation matrix's columns to regulate the degree of information aggregation from neighbors. The contrastive constraint, applied to the representation matrix's rows, enhances the discriminability of the nodes.
  arXiv  Detail & Related papers  (2024-08-06T12:52:03Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks [89.28881869440433]
  This paper provides the first theoretical characterization of joint edge-model sparse learning for graph neural networks (GNNs) It proves analytically that both sampling important nodes and pruning neurons with the lowest-magnitude can reduce the sample complexity and improve convergence without compromising the test accuracy.
  arXiv  Detail & Related papers  (2023-02-06T16:54:20Z)
• $\rm A^2Q$: Aggregation-Aware Quantization for Graph Neural Networks [18.772128348519566]
  We propose the Aggregation-Aware mixed-precision Quantization ($rm A2Q$) for Graph Neural Networks (GNNs) Our method can achieve up to 11.4% and 9.5% accuracy improvements on the node-level and graph-level tasks, respectively, and up to 2x speedup on a dedicated hardware accelerator.
  arXiv  Detail & Related papers  (2023-02-01T02:54:35Z)
• Binary Graph Convolutional Network with Capacity Exploration [58.99478502486377]
  We propose a Binary Graph Convolutional Network (Bi-GCN), which binarizes both the network parameters and input node attributes. Our Bi-GCN can reduce the memory consumption by an average of 31x for both the network parameters and input data, and accelerate the inference speed by an average of 51x.
  arXiv  Detail & Related papers  (2022-10-24T12:05:17Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling [83.77955213766896]
  Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graphstructured data. To address its scalability issue, graph topology sampling has been proposed to reduce the memory and computational cost of training Gs. This paper provides first theoretical justification of graph topology sampling in training (up to) three-layer GCNs.
  arXiv  Detail & Related papers  (2022-07-07T21:25:55Z)
• Non-Recursive Graph Convolutional Networks [33.459371861932574]
  We propose a novel architecture named Non-Recursive Graph Convolutional Network (NRGCN) to improve both the training efficiency and the learning performance of GCNs. NRGCN represents different hops of neighbors for each node based on inner-layer aggregation and layer-independent sampling. In this way, each node can be directly represented by concatenating the information extracted independently from each hop of its neighbors.
  arXiv  Detail & Related papers  (2021-05-09T08:12:18Z)
• MG-GCN: Fast and Effective Learning with Mix-grained Aggregators for Training Large Graph Convolutional Networks [20.07942308916373]
  Graph convolutional networks (GCNs) generate the embeddings of nodes by aggregating the information of their neighbors layer by layer. The high computational and memory cost of GCNs makes it infeasible for training on large graphs. A new model, named Mix-grained GCN (MG-GCN), achieves state-of-the-art performance in terms of accuracy, training speed, convergence speed, and memory cost.
  arXiv  Detail & Related papers  (2020-11-17T14:51:57Z)
• Temporal Attention-Augmented Graph Convolutional Network for Efficient Skeleton-Based Human Action Recognition [97.14064057840089]
  Graphal networks (GCNs) have been very successful in modeling non-Euclidean data structures. Most GCN-based action recognition methods use deep feed-forward networks with high computational complexity to process all skeletons in an action. We propose a temporal attention module (TAM) for increasing the efficiency in skeleton-based action recognition.
  arXiv  Detail & Related papers  (2020-10-23T08:01:55Z)
• Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Network [10.36962234388739]
  We propose a general subgraph-based training framework, namely Ripple Walk Training (RWT), for deep and large graph neural networks. RWT samples subgraphs from the full graph to constitute a mini-batch, and the full GNN is updated based on the mini-batch gradient. Extensive experiments on different sizes of graphs demonstrate the effectiveness and efficiency of RWT in training various GNNs.
  arXiv  Detail & Related papers  (2020-02-17T19:07:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.