On the Effectiveness of Pretraining for Graph Combinatorial Optimization

• URL: http://arxiv.org/abs/2607.19072v1
• Date: Tue, 21 Jul 2026 13:04:13 GMT
• Title: On the Effectiveness of Pretraining for Graph Combinatorial Optimization
• Abstract summary: This paper introduces a self-supervised pretraining framework for graph optimization.<n>It is designed to address the nature of routing problems like the Traveling Salesman Problem.<n>Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales.
• Score: 40.74618635552097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a self-supervised pretraining framework for graph combinatorial optimization specifically designed to address the nature of routing problems like the Traveling Salesman Problem. By utilizing graph contrastive learning with geometric augmentations (specifically, rotations and axial reflections) the model is forced to learn invariant structural representations and global relative distance distributions. Results demonstrate that this pretraining strategy outperforms non-pretrained models across various problem scales. Notably, the hybrid strategy (combining rotation and reflection) achieved a 6.57% improvement in tour length for TSP1000, proving that geometric pretraining is an important inductive bias for effectively scaling neural solvers to high-dimensional instances.

Related papers

• Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization [40.74618635552097]
  We propose a geometric self-supervised pre-training framework for routing graphs.<n>The framework learns robust structural representations prior to the policy optimization phase.<n>The proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde.
  arXiv  Detail & Related papers  (2026-07-31T20:23:21Z)
• Neural Network Optimization Reimagined: Decoupled Techniques for Scratch and Fine-Tuning [49.751529745537546]
  We propose DualOpt, a novel approach that decouples optimization techniques specifically tailored for training from scratch.<n>For training from scratch, we introduce real-time layer-wise weight decay, designed to enhance both convergence and generalization.<n>We extend the layer-wise weight decay to dynamically adjust the rollback levels across layers, adapting to the varying demands of different downstream tasks.
  arXiv  Detail & Related papers  (2026-04-21T06:27:18Z)
• HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers [0.0]
  Job Shop Scheduling Problem (JSSP) is commonly formulated as a disjunctive graph in which nodes represent operations and edges encode technological precedence constraints as well as machine-sharing conflicts.<n>Most existing reinforcement learning approaches model this graph as homogeneous, merging job-precedence and machine-contention edges into a single relation type.<n>We propose the Heterogeneous Graph Transformer (HGT)-Scheduler, a reinforcement learning framework that models the JSSP as a heterogeneous graph.
  arXiv  Detail & Related papers  (2026-03-06T17:59:12Z)
• Bridging Training and Merging Through Momentum-Aware Optimization [8.035521056416242]
  Training large neural networks and task-specific computation models require parameter importance estimation.<n>Current compute curvature information during training, discard it, then recompute similar information for merging.<n>We introduce a unified framework that factorized momentum and curvature statistics during training, then recompute similar information for merging.
  arXiv  Detail & Related papers  (2025-12-18T22:37:33Z)
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing [58.52119063742121]
  Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance.<n>This paper addresses the question of how to optimally combine the model's predictions and the provided labels.<n>Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels.
  arXiv  Detail & Related papers  (2025-05-21T07:16:44Z)
• Space-Variant Total Variation boosted by learning techniques in few-view tomographic imaging [0.0]
  This paper focuses on the development of a space-variant regularization model for solving an under-determined linear inverse problem. The primary objective of the proposed model is to achieve a good balance between denoising and the preservation of fine details and edges. A convolutional neural network is designed, to approximate both the ground truth image and its gradient using an elastic loss function in its training.
  arXiv  Detail & Related papers  (2024-04-25T08:58:41Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  We take a closer theoretical look at Independent Subnetwork Training (IST) IST is a recently proposed and highly effective technique for solving the aforementioned problems. We identify fundamental differences between IST and alternative approaches, such as distributed methods with compressed communication.
  arXiv  Detail & Related papers  (2023-06-28T18:14:22Z)
• End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
  This paper proposes the first end-to-end differentiable meta-BO framework that generalises neural processes to learn acquisition functions via transformer architectures. We enable this end-to-end framework with reinforcement learning (RL) to tackle the lack of labelled acquisition data.
  arXiv  Detail & Related papers  (2023-05-25T10:58:46Z)
• Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models [5.933030735757292]
  Laplacian regularized stratified models (LRSM) are models that utilize the explicit or implicit network structure of the sub-problems. This paper shows the importance and sensitivity of graph weights in LRSM, and provably show that the sensitivity can be arbitrarily large. We propose a generic approach to jointly learn the graph while fitting the model parameters by solving a single optimization problem.
  arXiv  Detail & Related papers  (2023-05-04T06:06:29Z)
• Extrapolation for Large-batch Training in Deep Learning [72.61259487233214]
  We show that a host of variations can be covered in a unified framework that we propose. We prove the convergence of this novel scheme and rigorously evaluate its empirical performance on ResNet, LSTM, and Transformer.
  arXiv  Detail & Related papers  (2020-06-10T08:22: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.