# On the Effectiveness of Pretraining for Graph Combinatorial Optimization

arXiv: https://arxiv.org/abs/2607.19072 · HTML: https://mlsanity.com/paper/2607.19072/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 9 references that are in the map.
- First posted on arXiv 21 Jul 2026.

## Builds on (most cited first, 7 of 7)

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [GraphMAE: Self-Supervised Masked Graph Autoencoders](https://mlsanity.com/paper/2205.10803/) (2022)
- [SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation](https://mlsanity.com/paper/2202.03104/) (2022)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/1506.07776/) (2015)

## Abstract (arXiv)

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.