Pith. sign in

REVIEW 2 major objections 4 minor 32 references

Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Pre-training a neural TSP encoder on rotated and reflected copies of training instances lets the same policy produce tours about 7% shorter at 1,000 nodes than training from scratch, with no inference slowdown.

desk verdict Sensible idea, real confound: the 7.23% extrapolation gain is not separated from a 3x larger training budget, so the central claim is currently under-supported. read the letter →

arxiv 2608.00270 v1 pith:54S3I6VE submitted 2026-07-31 cs.AI

David Aguado , Daniel Fuertes , Carlos R. del-Blanco , Fernando Jaureguizar This is my paper · ORCID
classification cs.AI
keywords geometricself-supervisedpre-trainingcontrastivelearningtravelingsalesmanproblemzero-shotextrapolationgraphneuralnetworksreinforcementisometrictransformationscombinatorialoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the main obstacle to scaling neural TSP solvers is not architecture but representation: an encoder trained from scratch memorizes absolute coordinates at the training scale. It proposes a pre-training phase that feeds the encoder rotated and reflected copies of the same instance and uses a contrastive loss to force the global embedding to be invariant to distance-preserving transformations. After this phase the encoder is fine-tuned with reinforcement learning on 50-node instances. The authors report that this consistently beats training from scratch, with a 7.23% reduction in average tour length at zero-shot extrapolation to TSP1,000, at roughly the same inference speed.

What carries the argument

The load-bearing mechanism is the geometric pretext task: the InfoNCE loss applied to global graph embeddings of an instance and its isometrically transformed view. The transformations are central rotation, axial reflection, and translation, composed randomly; the encoder is a GatedGCN with edge-gated anisotropic message passing, and a temporary two-layer MLP projection head maps the global embedding to a lower-dimensional space for the contrastive loss and is discarded before RL. The paper's argument is that maximizing agreement between views with identical pairwise distances but different coordinates makes the encoder capture distance distributions rather than absolute positions.

What would settle it

Run the same architecture under three conditions with identical total training epochs: (1) proposed rotation+reflection pre-training then RL, (2) RL from scratch for the full budget, (3) a control pretext task such as predicting the rotation angle from the global embedding, then RL. Compare zero-shot optimality gaps at TSP1,000. If condition (2) or (3) matches condition (1)'s 55.1% gap, the geometric-invariance explanation is falsified.

Watch

Extended reading notes

Core claim

The paper's claim is that for the Euclidean TSP, the reason reinforcement-learned solvers fail at large scale is that their encoders memorize absolute coordinate distributions instead of relative distances. To fix this, the authors add a self-supervised phase before RL: they generate augmented views by rotating and reflecting each instance around its center, and train the GatedGCN encoder with the InfoNCE contrastive loss so that global embeddings of the original and transformed views agree. Because these isometric transformations preserve all pairwise distances, the optimal tour is unchanged, so the encoder is forced to represent structure that matters for routing. After this phase the proj

Load-bearing premise

The paper credits the geometric pre-training for the gains, but its baseline receives no pre-training phase, so the comparison mixes augmentation choice with a 100-epoch training advantage; if an equivalent-budget or non-geometric-pre-text baseline matches the results, the central claim loses support.

Editorial extensions

If this is right

  • Pre-training with rotation and reflection cuts the zero-shot optimality gap at TSP1,000 from 67.2% to 55.1%, a 7.23% relative reduction in average tour length.
  • The improvement comes without slowing inference: the pre-trained model runs at roughly the same time as the baseline and up to two orders of magnitude faster than Concorde at 1,000 nodes.
  • Augmentation choice matters: translation as an augmentation makes extrapolation worse than no pre-training at TSP1,000 (76.2% vs 67.2% gap), so distance preservation alone is not enough.
  • Training on a variable range of instance sizes (20–50 nodes) helps zero-shot extrapolation to moderate scales, but at ultra-dense scales a model trained at a fixed size can outperform it.
  • These results hold for the GatedGCN encoder with a REINFORCE-trained attention decoder; the paper does not claim the same for other architectures.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next test is an equal-budget control: train the baseline from scratch for the same total number of epochs as pre-training plus fine-tuning, or with a non-geometric pretext task, to isolate whether the gain comes from geometric invariance or simply from extra encoder training.
  • The translation failure suggests a design rule for geometric contrastive learning on metric graphs: augmentations must preserve not just distances but also local neighborhood identity at the resolution of the instance, a principle likely to transfer to other routing and packing problems.
  • The pre-trained encoder might serve as a reusable geometric feature extractor for other optimization tasks beyond TSP, such as CVRP or facility location, without requiring the exact contrastive setup; this is an untested extension.
  • If the geometric pretext task genuinely induces distance-aware representations, one could probe the embedding geometry directly, e.g., check whether encoder distances between node embeddings correlate with Euclidean distances across scales.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a geometric self-supervised pre-training framework for neural TSP solvers. A GatedGCN encoder is pre-trained with an InfoNCE contrastive loss on pairs of TSP instances related by isometric transformations (rotation, axial reflection, translation), then fine-tuned with REINFORCE and a rollout baseline. The central claim is that this pre-training improves zero-shot extrapolation to large instances, with the abstract reporting a 7.23% improvement in tour length at TSP1,000, along with large speedups over Concorde. The authors include an ablation over transformation combinations, a scale-variability study, and comparisons to exact and heuristic solvers.

Significance. If validated, the method would be a simple and impactful contribution to neural combinatorial optimization, addressing a well-known generalization bottleneck. The paper's strengths are its clear problem motivation, the use of an invariance property that provably holds for Euclidean TSP tours, and the public release of code and pre-trained models. The ablation across transformation types is thorough, and the comparisons to Concorde are useful. However, the central empirical claim is currently confounded: the 'None' baseline receives no pre-training, so the reported gains cannot be attributed to geometric invariance as opposed to additional optimization budget. Controlled experiments are needed before the significance of the result can be assessed.

major comments (2)
  1. [Section 4.1, Table 1] The main comparison is not controlled for training budget. The 'None (Baseline)' model is trained from scratch for 50 RL epochs, while every pre-trained variant receives 100 contrastive pre-training epochs plus 50 RL epochs (Section 4.1). The differences in Table 1—especially the TSP1,000 gap reduction from 67.2% to 55.1%—therefore conflate the geometric pretext with an additional 100 epochs of gradient updates. To support the paper's central attribution, the authors must add (a) an RL-only baseline trained for the same total number of epochs (e.g., 150 RL epochs) and/or (b) a control pre-training with a non-geometric pretext that uses the same computational budget. Without such controls, the claim that 'pre-training consistently establishes a generalized superiority over random initialization' is not established.
  2. [Abstract, Section 4.2, Eq. (26)] The abstract's '7.23% improvement in tour length' is derived from a relative reduction in the optimality gap (12.1 percentage points relative to the baseline's 167.2% tour cost), not from directly measured tour lengths. This derivation should be stated explicitly, and the abstract should clarify what is being measured. As written, a reader could reasonably interpret the claim as a 7.23% reduction in average tour length, which is not what is reported.
minor comments (4)
  1. [Section 2.2, reference [8]] The reference for GraphCL is incorrect; [8] is 'Graph contrastive learning automated' (JOAO), not the original GraphCL paper. Please cite the original work and adjust the sentence accordingly.
  2. [Section 4.2, Table 2] The 'state-of-the-art comparison' does not include any recent neural NCO baselines (e.g., POMO, DIMES, or other attention-based models), only exact/heuristic solvers and the authors' own baseline. Either add published neural baselines or soften the 'state-of-the-art' language.
  3. [Section 4.3, Table 3] The row and column labels in Table 3 are difficult to parse in the current formatting; 'Pre-trainingTraining' is run together and the evaluation scale columns are not clearly separated. Please reformat for readability.
  4. [Section 4.2] The explanation for why translation hurts generalization is presented as a 'hypothesis' (Section 4.2). If this explanation is important to the narrative, support it with a targeted experiment (e.g., analyzing embedding distances or ablation with smaller translation magnitudes); otherwise, mark it clearly as speculative.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the geometric pre-training claim is empirical and benchmarked externally (Concorde); no equation-level self-reference or load-bearing self-citation.

full rationale

The paper's central claim is that isometric-transformation-based contrastive pre-training improves zero-shot TSP extrapolation. This is an empirical claim evaluated against Concorde, an external exact solver, so the performance numbers are not constructed from the method's own definitions. The invariance property used to motivate the augmentation (optimal tour unchanged under rotations/reflections) is a mathematical property of Euclidean TSP, not an assumption that embeds the target result. The InfoNCE loss (Eq. 23) is a standard contrastive objective; it does not include tour length or optimality gap as an input. There is no fitted parameter that is subsequently renamed as a prediction, no uniqueness theorem imported from the authors' prior work, and no self-citation chain supporting the central premise. The strongest methodological weakness is that the 'None' baseline receives no 100-epoch contrastive pre-training, confounding augmentation choice with total training budget. That is a correctness/experimental-design concern, not circularity: it does not make the claimed improvement equivalent to the method's inputs by construction. The paper is self-contained against external benchmarks, so the honest circularity score is 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on four main assumptions: the mathematical invariance of TSP under isometries (sound), the transfer of global contrastive agreement to node-level decisions (unproven but testable), the adequacy of k-NN sparsification (unreported k), and the causal attribution of gains to the pre-training objective rather than extra epochs (currently confounded). No new physical or model entities are introduced.

free parameters (4)
  • k-NN neighborhood size k
    The encoder is built on a k-nearest-neighbor sparsified graph (Section 3.2.1), but k is never reported. It controls which edges the GatedGCN sees and therefore what the contrastive views and the final policy depend on.
  • Maximum translation displacement = 15% of coordinate range
    Chosen 'to maintain numerical stability' (Section 3.3). Translation is later found to be harmful and is excluded from the best model, so the framework's stated augmentation space does not match the evaluated model.
  • Bernoulli augmentation probability p = 0.5
    Each geometric transformation is applied with independent probability p=0.5 in the hybrid strategy (Section 3.3). No sensitivity analysis is given, although Table 1 shows the transformation choice strongly changes results.
  • Scale variability range during pre-training/training = U(20,50) or U(20,100)
    The paper shows in Table 3 that variable node counts change extrapolation behavior; the chosen ranges are a factor in the claimed benefit and are not systematically swept.
assumptions (4)
  • standard math Euclidean TSP optimal tour is invariant under rotations, reflections, and translations.
    True for the objective in Eq. (5) under isometries; used in Section 3.3 to justify that augmented views have identical optimal solutions.
  • domain assumption Contrastive agreement between graph-level global embeddings transfers to node-level policy quality.
    InfoNCE is applied to mean-pooled global embeddings (Eq. 23), but the decoder selects nodes from per-node embeddings (Eqs. 9–15). The paper asserts transfer without derivation; this is the paper's central mechanism.
  • domain assumption A k-NN sparsified graph preserves enough metric structure for TSP solving at n up to 1,000.
    The dense graph is replaced by k-NN neighbors (Section 3.2.1) to reduce memory, with no ablation on k and no proof that the optimal Hamiltonian cycle remains representable.
  • ad hoc to paper The 100-epoch pre-training phase can be credited to the geometric objective rather than to the added optimization budget.
    The 'None' baseline receives only RL training (Section 4.1), while pre-trained models receive 100 extra epochs of contrastive learning; the comparison conflates objective choice with total training epochs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization." pith.science (2026). https://pith.science/paper/54S3I6VE

@misc{pith2026260800270,
  author       = {Pith},
  title        = {Pith review of: Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/54S3I6VE}},
  note         = {Machine review of arXiv:2608.00270}
}
read the original abstract

Neural Combinatorial Optimization (NCO) techniques have emerged as a highly efficient alternative to traditional exact algorithms for solving routing problems such as the Traveling Salesman Problem (TSP). However, the generalization capabilities of these Reinforcement Learning-based models are severely hindered when scaling to high-dimensional instances. This issue has been mitigated in other domains, like computer vision and natural language processing, by adopting a self-supervised pre-training strategy. Nevertheless, its application to routing graphs, which lack complex topological attributes beyond 2D spatial coordinates, remains a challenge. In this paper, we propose a geometric self-supervised pre-training framework specifically designed to capture spatial invariance and global relative distance distributions. By applying isometric transformations, such as rotations and axial reflections, the model learns robust structural representations prior to the policy optimization phase. Empirical results demonstrate that this strategy consistently outperforms models trained from scratch (baselines), achieving a 7.23\% improvement in tour length for massive zero-shot extrapolation scenarios (TSP1,000). Furthermore, the proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde at massive scales. The source code and pre-trained models are publicly available at https://github.com/davidaguadocosano/TSP-GeoPretrain.git.

Figures

Figures reproduced from arXiv: 2608.00270 by the authors.

Figure 1
Figure 1. Overview of the proposed neural architecture. The system comprises a GatedGCN encoder for structural [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Geometric transformations for graph pre-training: (a) original instance, (b) rotation [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Visual comparison of the routes generated by different architectures in response to progressive increases in [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [1]

    Neural combinatorial optimization with heavy decoder: Toward large scale generalization.ArXiv, abs/2310.07985, 2023

    Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization.ArXiv, abs/2310.07985, 2023

    arXiv 2023

  2. [2]

    Attention, learn to solve routing problems! InInternational Conference on Learning Representations, 2019

    Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! InInternational Conference on Learning Representations, 2019

    2019

  3. [3]

    RRNCO: Towards real-world routing with neural combinatorial optimization

    Jiwoo Son, Zhikai Zhao, Federico Berto, Chuanbo Hua, Zhiguang Cao, Changhyun Kwon, and Jinkyoo Park. RRNCO: Towards real-world routing with neural combinatorial optimization. InWorkshop on Differentiable Learning of Combinatorial Algorithms, 2025

    2025

  4. [4]

    Toutanova

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina N. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. 2018

    2018

  5. [5]

    Masked autoencoders are scalable vision learners

    Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 15979–15988, 2022

    2022

  6. [6]

    Graphmae2: A decoding-enhanced masked self-supervised graph learner

    Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A decoding-enhanced masked self-supervised graph learner. InProceedings of the ACM Web Conference 2023, WWW ’23, page 737–746, New York, NY , USA, 2023. Association for Computing Machinery

    2023

  7. [7]

    Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm

    Petar Veliˇckovi´c, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. InInternational Conference on Learning Representations, 2019

    2019

  8. [8]

    Graph contrastive learning automated

    Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 12121–12132. PMLR, 18–24 Jul 2021

    2021

Show all 32 references
  1. [9]

    Applegate, Robert E

    David L. Applegate, Robert E. Bixby, Vašek Chvatál, and William J. Cook.The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006

    2006

  2. [10]

    Morrison, Sheldon H

    David R. Morrison, Sheldon H. Jacobson, Jason J. Sauppe, and Edward C. Sewell. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning.Discrete Optimization, 19:79–102, 2016

    2016

  3. [11]

    An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems: Technical report

    Keld Helsgaun. An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems: Technical report. 2017

    2017

  4. [12]

    David Astoquillca-Yaranga and Esther Berger-Vidal. Heurística de intercambio 2opt best improvement y nivel de eficacia de las soluciones del problema del agente viajero simétrico.Revista peruana de computación y sistemas, 5:65–81, 06 2023

    2023

  5. [13]

    K. T. Chung, C. K. M. Lee, and Y . P. Tsang. Neural combinatorial optimization with reinforcement learning in industrial engineering: a survey.Artificial Intelligence Review, 58(5):130, 2025

    2025

  6. [14]

    Pointer networks

    Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015

    2015

  7. [15]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017

    2017

  8. [16]

    Graph attention networks, 2018

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018

    2018

  9. [17]

    Gated graph sequence neural networks, 2017

    Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks, 2017

    2017

  10. [18]

    Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent

    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, April 2022

    2022

  11. [19]

    Graphmae: Self-supervised masked graph autoencoders

    Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. InProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, page 594–604, New York, NY , USA, 2022....

    2022

  12. [20]

    Self-supervised graph representation learning via topology transformations

    Xiang Gao, Wei Hu, and Guo-Jun Qi. Self-supervised graph representation learning via topology transformations. IEEE Transactions on Knowledge and Data Engineering, 35(4):4202–4215, April 2023

    2023

  13. [21]

    Graph contrastive learning with personalized augmentation

    Xin Zhang, Qiaoyu Tan, Xiao Huang, and Bo Li. Graph contrastive learning with personalized augmentation. IEEE Transactions on Knowledge and Data Engineering, 36(11):6305–6316, November 2024. 11 APREPRINT- AUGUST4, 2026

    2024

  14. [22]

    Wen-Zhi Li, Chang-Dong Wang, Jian-Huang Lai, and Philip S. Yu. Towards effective and robust graph contrastive learning with graph autoencoding.IEEE Transactions on Knowledge and Data Engineering, 36(2):868–881, February 2024

    2024

  15. [23]

    Multi-scale self- supervised graph contrastive learning with injective node augmentation.IEEE Transactions on Knowledge and Data Engineering, 36(1):261–274, January 2024

    Haonan Zhang, Yuyang Ren, Luoyi Fu, Xinbing Wang, Guihai Chen, and Chenghu Zhou. Multi-scale self- supervised graph contrastive learning with injective node augmentation.IEEE Transactions on Knowledge and Data Engineering, 36(1):261–274, January 2024

    2024

  16. [24]

    Sanfeng Zhang, Xinyi Liu, Zihao Qi, Xingchen Yan, and Wang Yang. GI-Graph: A generative invariant graph learning scheme towards out-of-distribution generalization.IEEE Transactions on Knowledge and Data Engineering, 37(10):5934–5947, October 2025

    2025

  17. [25]

    Data augmentation on graphs: A technical survey.ACM Comput

    Jiajun Zhou, Chenxuan Xie, Shengbo Gong, Zhenyu Wen, Xiangyu Zhao, Qi Xuan, and Xiaoniu Yang. Data augmentation on graphs: A technical survey.ACM Comput. Surv., 57(11), June 2025

    2025

  18. [26]

    C. E. Miller, A. W. Tucker, and R. A. Zemlin. Integer programming formulation of traveling salesman problems. J. ACM, 7(4):326–329, 1960

    1960

  19. [27]

    On layer normalization in the transformer architecture

    Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie-Yan Liu. On layer normalization in the transformer architecture. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

    2020

  20. [28]

    A simple framework for contrastive learning of visual representations

    Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

    2020

  21. [29]

    Householder

    Alston S. Householder. Unitary triangularization of a nonsymmetric matrix.J. ACM, 5(4):339–342, October 1958

    1958

  22. [30]

    Contrastive difference predictive coding

    Chongyi Zheng, Ruslan Salakhutdinov, and Benjamin Eysenbach. Contrastive difference predictive coding. In The Twelfth International Conference on Learning Representations, 2024

    2024

  23. [31]

    White and Douglas J

    Chelsea C. White and Douglas J. White. Markov decision processes.European Journal of Operational Research, 39(1):1–16, 1989

    1989

  24. [32]

    Williams

    Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229–256, May 1992. 12 APREPRINT- AUGUST4, 2026 A Visual comparison Baseline Rotation Reflection Rot + Ref TSP20 TSP50 TSP100 Translation Concor...

    1992

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.