O N THE E FFECTIVENESS OF P RETRAINING FOR G RAPH C OMBINATORIAL O PTIMIZATION
David Aguado, Daniel Fuertes, Carlos R. del-Blanco, Fernando Jaureguizar Grupo de Tratamiento de Imágenes, Information Processing and Telecomunications Center, ETSI Telecomunicación, Universidad Politécnica de Madrid, 28040, Madrid, Spain [email protected], {d.fcoiras, carlosrob.delblanco, fernando.jaureguizar}@upm.es
July 22, 2026
arXiv:2607.19072v1 [cs.AI] 21 Jul 2026
A BSTRACT 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. Keywords Contrastive learning · combinatorial · optimization · graph pretraining · traveling salesman problem
1
Introduction
Neural Combinatorial Optimization (NCO) has recently emerged as a promising research area, leveraging deep learning to tackle classical NP-hard problems like Vehicle Routing Problems (VRPs). Among these, the Traveling Salesman Problem (TSP) [1] has become an important benchmark due to its simplicity and broad applicability. Learning-based approaches [2], usually trained with Deep Reinforcement Learning (DRL), have demonstrated competitive performance compared to traditional heuristics, such as 2-opt [3], Christofides [4], or the Lin-Kernighan algorithm [5]. However, their success relies heavily on the quality of the learned graph embeddings. In other domains, self-supervised pretraining is standard for extracting robust representations. For instance, GraphMAE [6] utilizes masked autoencoders in molecular biology, while frameworks like GCA [7] and SimGRACE [8] leverage adaptive augmentations and contrastive learning to exploit structural connectivity in social and functional networks. However, these methods are not directly applicable to VRPs. Unlike those domains, VRP graphs are “attribute-poor," consisting almost exclusively of 2D coordinates. Furthermore, routing requires capturing the global distribution of relative distances in fully connected graphs, rather than sparse topologies. To bridge this gap, we propose a pretraining framework specifically designed for the geometric nature of routing challenges. Our main contribution is a graph contrastive learning approach that employs geometric augmentations, such as rotations and axial reflections that do not change the graph topology, to force the model to learn invariant structural representations, and thus capturing the essential geometric properties of the graph representation.
2
Methodology
The proposed framework incorporates a geometric pretraining phase based on graph contrastive learning, consisting of forcing that embeddings from equivalent node graphs are similar and vise versa. The assumption for claiming that two different node graphs are equivalent is to share the same route solution. Given a graph representing a TSP, defined by its node Euclidean distances, another equivalent graph can be obtained by isometries transformations since they
n1
n2 n1
n2 n7
n7
n6
n3 n4
_____________
A PREPRINT - J ULY 22, 2026
n6 n3 n4
n5
n5
(a) Original
(b) Rotated
n1 n2 n7 n3 n6 n4 n5
(c) Reflected
Figure 1: Geometric transformations for graph pretraining: (a) original instance, (b) rotation fθ , and (c) axial reflection fϕ . Table 1: Performance comparison (average tour length ± 95% confidence interval) using geometric pretraining. Best in bold. Pretraining TSP20 TSP50 TSP100 TSP200 TSP500 TSP1000 None 3.989 ± 0.020 6.078 ± 0.019 8.796 ± 0.031 13.321 ± 0.064 24.052 ± 0.092 38.664 ± 0.137 Rotation 3.954 ± 0.020 6.039 ± 0.018 8.666 ± 0.033 13.080 ± 0.066 23.278 ± 0.094 36.835 ± 0.134 Reflection 3.953 ± 0.020 6.030 ± 0.019 8.651 ± 0.028 12.927 ± 0.064 23.201 ± 0.089 36.694 ± 0.132 Hybrid 3.953 ± 0.020 6.030 ± 0.018 8.623 ± 0.028 12.936 ± 0.066 22.887 ± 0.091 36.123 ± 0.139
preserve the distance between every pair of nodes and, therefore, the solution remains invariant. The proposed isometric transformations are rotations and axial reflections, illustrated in Fig. 1. Specifically, for a set of nodes N = {1, . . . , n} defined in a normalized space with coordinates xi ∈ [0, 1]2 ⊂ R2 , i ∈ N , we define a rotation transformation fθ : R2 → R2 relative to the unit square’s center c = [0.5, 0.5]⊤ . The rotation angle θ is sampled from the uniform distribution U(0, 2π), and The transformed coordinates are computed as follows: fθ (xi ) = Rθ (xi − c) + c,
Rθ =
cos θ sin θ
− sin θ cos θ
(1)
where Rθ ∈ R2×2 is the 2D rotation matrix. Similarly, we define an axial reflection fϕ : R2 → R2 across an axis passing through the center c with an orientation angle ϕ ∼ U (0, π). To represent this mathematically, let v = [cos ϕ, sin ϕ]⊤ be the unit vector defining the axis of reflection. The transformation is calculated using the Householder reflection matrix Sϕ = 2vv⊤ − I, resulting in the following expression for the reflected coordinates: fϕ (xi ) = Sϕ (xi − c) + c.
(2)
To further increase graph diversity, these functions can be applied independently or combined into a hybrid transformation g(xi ) = fθ (fϕ (xi )), which applies both operations simultaneously. To enhance the model’s adaptability across different problem scales, the pretraining dataset consists of TSP instances with variable sizes, where the number of nodes N is uniformly sampled such that N ∈ [20, 50]. The encoder is pretrained over 50 epochs with an epoch size of 128, 000 instances and a batch size of 256 graphs. This process exposes the model to a total of 6.4 × 106 unique graph geometric configurations, providing a massive and diverse pretraining. This strategic diversity in graph size prevents the encoder from overfitting to a single graph size, fostering a more flexible structural representation that facilitates zero-shot generalization to larger, unseen instances during the evaluation phase. 2
A PREPRINT - J ULY 22, 2026
During the pretraining phase, the model encoder generates an embedding for each graph and is trained, by means of the InfoNCE contrastive loss, to maximize similarity between embeddings from equivalent graphs and minimize similarity otherwise. The InfoNCE contrastive loss is given by exp q ⊤ k+/τ LInfoNCE = − log PK (3) ⊤ i=0 exp (q ki /τ ) where q represents an embedding of a graph G, k+ an embedding of a graph resulting from applying one of the proposed isometric transformations to G, and ki and embedding from another graph not equivalent to G. And τ is a temperature parameter. This loss function forces the encoder to capture relative distance distributions and connectivity patterns that are essential for the posterior training phase.
3
Results
The proposed pretraining strategy is evaluated in a Graph Convolutional Network (GCN) introduced in [9]. Qualitative results are provided in Fig. 2 showing a comparison of the tours generated on different scales. Observe that paths from pretrained models, especially under the hybrid strategy, exhibit fewer self-intersections.
Reflection
Rotation
Hybrid
TSP100
TSP50
TSP20
None
Figure 2: Examles of TSP solutions per strategy and scale. Quantitative results in table 1 demonstrate that all pretraining variants consistently outperform the baseline model in all instance sizes. Notably, performance improves significantly as instance complexity increases, highlighting the superior scalability of our approach. For TSP20, hybrid pretarining reduces tour length by 0.90%, while for TSP1000, by 6.57%. This growing margin indicates that, while standard DRL training is sufficient for small graphs, it struggles to generalize the underlying structural topology as the search space expands. By contrast, incorporating geometric transformations, such as rotation and axial reflection, forces the encoder to learn invariant representations, providing crucial inductive bias. This regularization allows the model to maintain a robust understanding of relative node distributions, which is critical for large-scale node instances. Finally, the hybrid approach remains the most robust, as the diversity of transformations encourages richer, more generalizable graph embeddings. 3
A PREPRINT - J ULY 22, 2026
4
Conclusions
This paper establishes that geometric graph contrastive learning provides an effective framework for pretraining on the attribute-poor graphs inherent to the TSP. By exploiting geometric symmetries such as rotation and axial reflection, our method successfully captures invariant structural representations that significantly enhance both solution quality and model robustness compared to training from scratch. Notably, this geometric inductive bias allows the model to maintain performance as graph complexity increases, reducing the scalability gap for large-scale instances. For future research, more complex strategies specifically tailored to the nature of VRPs will be investigated. Acknowledgment This work was supported in part by the Comunidad de Madrid under project TEC-2024/COM-322 (IDEALCVCM), in part by MCIU/AEI/10.13039/501100011033 of the Spanish Government under project PID2023148922OA-I00 (EEVOCATIONS), and in part by “Ayudas a la Investigación para el Personal Docente e Investigador de la ETSIT-UPM (2026)” under project “SATURNO”. The authors would also like to thank Airbus Defence and Space for their support.
References [1] M. Bellmore and G. L. Nemhauser. The traveling salesman problem: A survey. Operations Research, 16(3):538–558, 1968. [2] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019. [3] Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, 2020. [4] Kyle Genova and David P. Williamson. An experimental evaluation of the best-of-many christofides’ algorithm for the traveling salesman problem. Algorithmica, 78(4), 2017. [5] Keld Helsgaun. An effective implementation of the lin–kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106–130, 2000. [6] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. GraphMAE: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2022. [7] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, WWW ’21, New York, NY, USA, 2021. Association for Computing Machinery. [8] Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z. Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Conference 2022, WWW ’21, New York, NY, USA, 2022. Association for Computing Machinery. [9] {Chaitanya K.} Joshi, Quentin Cappart, {Louis Martin} Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2):70–98, 2022.
4