Pith. sign in

REVIEW 4 major objections 5 minor 6 references

Graph Neural Networks are Heuristics

T0 review · 4 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read A graph neural network trained only on a Hamiltonian-cycle objective can solve TSP in a single forward pass, beating greedy nearest-neighbor.

desk verdict Plausible empirical advance: an unsupervised single-pass GNN roughly halves greedy NN's TSP gap, though the unanalyzed relaxation gap and missing error bars keep it from being a slam dunk. read the letter →

arxiv 2601.13465 v4 pith:LAMO54GB submitted 2026-01-19 cs.AI cs.LG

Yimeng Min , Carla P. Gomes This is my paper · ORCID
classification cs.AIcs.LG
keywords graphneuralnetworkstravellingsalesmanproblemunsupervisedlearningcombinatorialoptimizationheuristicsGumbel-SinkhornHamiltoniancyclepermutation
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

This paper argues that graph neural networks need not play an auxiliary role in combinatorial optimization: a GNN can itself be the heuristic. For the Euclidean Travelling Salesman Problem, the authors train a non-autoregressive GNN with no labels, rewards, search, or sequential decoding, using only a differentiable Hamiltonian-cycle objective. The trained network emits a complete tour in a single forward pass and consistently outperforms the greedy nearest-neighbor baseline on TSP100, TSP200, and TSP500, with optimality gaps roughly halved or better. The result matters because it reframes learning for combinatorial problems as a way to instantiate new heuristics directly, rather than merely guide existing algorithms.

What carries the argument

The load-bearing object is the differentiable Hamiltonian-cycle objective L_TSP = <D, T V T^T>, built from the cyclic-shift matrix V and a Gumbel-Sinkhorn soft permutation T. The cyclic shift encodes the tour structure as a permutation similarity transform; the relaxation makes the combinatorial constraint differentiable; Hungarian decoding at inference turns the soft output into a hard permutation. Around this core sit three supporting mechanisms: an equivariant coordinate feature extractor that removes translation and rotation while preserving permutation equivariance, dropout as stochasticity for solution diversity, and snapshot ensembling along a single training trajectory to obtain seve

What would settle it

For a trained model, compute the rank correlation between the relaxed loss L_TSP and the decoded tour length on a held-out set; if it is weak or negative, the training signal is decoupled from tour quality. Alternatively, a sweep of temperature τ and Sinkhorn iterations l that collapses performance would show the result hinges on relaxation hyperparameters rather than learned structure.

Watch

Extended reading notes

Core claim

The paper's central claim is that encoding the Hamiltonian-cycle constraint directly into a differentiable objective lets a single feed-forward GNN internalize the global structure of TSP. Formally, TSP is written as minimizing <D, P V P^T> over permutation matrices, with V the cyclic shift; relaxing P to a Gumbel-Sinkhorn soft permutation T makes the objective differentiable, and decoding with the Hungarian algorithm recovers a tour. Trained solely on this objective, the model produces tours with gaps of 5.55% (TSP100), 9.18% (TSP200), and 13.30% (TSP500) deterministically, versus 24.77%, 25.87%, and 26.05% for greedy nearest-neighbor; snapshot and Monte-Carlo dropout ensembles from a singl

Load-bearing premise

The method assumes that minimizing the relaxed soft-permutation objective and then rounding with the Hungarian algorithm yields hard tours whose quality tracks the relaxed loss; if that soft-to-hard transfer fails, the training signal no longer reflects the tours being evaluated.

Editorial extensions

If this is right

  • If correct, unsupervised single-pass GNNs constitute a new class of learned heuristics for permutation-based combinatorial problems.
  • The consistent improvement over greedy on sizes 100–500 indicates the model exploits non-local structure, not just local shortcuts, because no search or refinement is allowed.
  • Batched GPU inference stays in the millisecond regime, so the method can be applied at scale where classical heuristics would be slower.
  • Diversity mechanisms (dropout, snapshots) improve solution quality without additional training, offering a controllable quality–cost trade-off.
  • The formulation suggests a template for other CO problems: encode the global constraint into a differentiable objective and train without labels.

Reading between the lines

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

  • A natural extension is to test whether the same unsupervised permutation-learning recipe transfers to other routing or assignment problems with permutation structure.
  • The paper compares against greedy nearest-neighbor; a stricter diagnostic would measure the soft-to-hard relaxation gap by correlating the relaxed loss with decoded tour length across instances.
  • On instance distributions with strong clustering, the relaxation gap may widen; checking whether the deterministic model's advantage persists there would bound the heuristic's regime of validity.
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

4 major / 5 minor

Summary. The paper proposes that a graph neural network can itself act as a heuristic for the Euclidean Travelling Salesman Problem, rather than as an auxiliary module for search or supervised decoding. The method trains a non-autoregressive GNN using only a differentiable Hamiltonian-cycle objective with Gumbel-Sinkhorn relaxation (Eqs. 5–8), then extracts a hard tour via the Hungarian algorithm (Eq. 9). The authors report that a single forward pass achieves optimality gaps of 5.55%, 9.18%, and 13.30% on TSP100, TSP200, and TSP500, respectively, improving upon a greedy nearest-neighbor baseline, and that dropout/snapshot ensembling further reduces these gaps. The paper claims this establishes learned, structure-aware GNN heuristics that do not require labels, rewards, sequential decoding, search, or local improvement.

Significance. If the empirical claims hold, the paper makes a useful contribution: it shows that a purely unsupervised, non-autoregressive GNN can produce competitive TSP tours in a single forward pass, outperforming a classical greedy heuristic and matching or exceeding Christofides on TSP500. The unsupervised training objective and the symmetry-aware feature extraction are interesting and potentially reusable. However, the central mechanism is currently supported only by end-to-end results with no analysis of the soft-to-hard relaxation gap and no statistical error bars. The contribution is therefore promising but needs substantive additional evidence before it can be considered established.

major comments (4)
  1. [§3.1–3.2, Eqs. (5)–(9)] The load-bearing premise is that minimizing the relaxed objective L_TSP = <D, T V T^T> over Gumbel-Sinkhorn soft permutations yields hard tours whose quality tracks the relaxed loss. This is not established. For doubly stochastic T, the objective is a mean-field quadratic form that treats assignments of cities to successive positions as independent; a fractional T can have low L_TSP while every nearby hard permutation has much higher cost. The paper provides no bound on this relaxation gap, no correlation analysis between L_TSP and post-Hungarian tour length during training, and no sensitivity study over the relaxation hyperparameters (τ, γ, l, α, s). Without such evidence, the gradient signal may be decoupled from the reported tour quality, and the success could be due to architectural inductive bias, ensembling, or Hungarian decoding rather than the Hamiltonian objective.
  2. [§7, Tables 1–3] All reported means (e.g., 8.18 vs 9.67 on TSP100) come from a single training run and 1,000 test instances, with no standard deviations, confidence intervals, or multiple independent seeds. The paper states it selects 'the model that achieves the lowest validation length across all hyperparameter settings,' which risks selection bias. Since the central claim is improvement over greedy NN, the results need error bars and at least a few independent training runs to establish statistical significance. This is particularly important for the smaller differences among ensemble variants (e.g., 8.09 vs 8.11 on TSP100).
  3. [§1, §5.3, §7] The abstract and introduction claim 'no search' and 'a complete tour in one forward pass,' but the inference procedure in Eq. (9) uses Hungarian decoding, and the ensemble methods in §5.3 (snapshots) and §5.2 (MC dropout) explicitly select the best among multiple forward passes. Selecting the best of 5–10 candidate tours is a form of search over the solution set, albeit a lightweight one. The claims should be qualified to 'no iterative refinement or neighborhood search' and 'a single forward pass per candidate,' or the definition of search should be stated precisely. As written, the claims are internally inconsistent with the ensemble selection procedure.
  4. [§6, Eqs. (6)–(8)] The method depends on several hyperparameters—distance scale s, Gumbel temperature τ, noise magnitude γ, Sinkhorn iterations l, logit scale α, Fourier harmonic count M, dropout probability, and ensemble sizes—but no sensitivity analysis is provided. Since the paper argues the Hamiltonian objective is what makes the method work, it is important to know how robust the results are to these choices. At minimum, report the range of hyperparameters explored and show that the qualitative conclusion (improvement over greedy NN) is stable within a reasonable neighborhood of the chosen values.
minor comments (5)
  1. [Abstract] The phrase 'consistently improves over nearest-neighbor greedy baselines' is accurate, but 'no search' is too strong given the ensemble selection step; see major comment.
  2. [§5.1] The sign convention 'u1 ≥ 0' fixes the eigenvector sign only generically; at u1 = 0 the convention is ill-defined. The paper acknowledges degeneracy for isotropic covariance, but it should also mention that the canonical frame can be discontinuous even for non-isotropic data when the leading component crosses zero, which may affect optimization.
  3. [§7, Table 3] Runtime reporting is inconsistent: 'Ours' reports batched GPU time per 512 instances, while classical heuristics report CPU time per instance. The comparison is useful but should state the hardware and batch size in the caption, and ideally report per-instance latency for both.
  4. [General] There are minor grammatical issues, e.g., 'Figures 2 show' (plural) and the incomplete sentence 'By directly embedding the Hamiltonian cycle constraint into the learning objective and predicting global permutation operators.' A final proofread is needed.
  5. [§2] The discussion of 'Nature Machine Intelligence' critiques would benefit from a more precise citation of which specific claims are being addressed; currently the references are grouped together without distinguishing the independent set results from TSP results.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the training objective is the true TSP cost under a relaxed permutation and all quality comparisons are against external solvers and heuristics.

full rationale

The derivation chain is self-contained. Equation 5, LTSP = <D, T V T^T>, is literally the TSP objective of Eq. 4 with the discrete permutation matrix P relaxed to a doubly stochastic T; no target tour length or optimality gap is used as a training label. The model is trained by minimizing this objective on randomly sampled instances with no ground-truth tours or reward signals, and inference decodes a hard permutation via the Hungarian algorithm (Eq. 9). Reported performance is compared against Concorde, an independent exact solver, and classical heuristics from external implementations (networkx C++, etc.), so the central empirical claim is not defined in terms of the paper's own outputs. The self-citations to prior Gumbel-Sinkhorn TSP work, scattering GNNs, and the Structure-as-Search framework are methodological or framing references, not load-bearing proofs of the present claim. The soft-to-hard relaxation gap discussed by critics is an empirical assumption about loss alignment, not a circularity: if the gap were large, the training signal would simply be poorly correlated with tour quality, but that would not mean the reported tours were fitted from the target. The best-of-k selection used in MC-dropout and snapshot ensembles does select tours by evaluating their length, but this is a post-hoc inference-time selection rule, not a parameter fitted to the evaluation metric, and the deterministic single-pass result already outperforms the greedy baseline. No circular step can be exhibited from the paper's own equations or cited results.

Assumptions & free parameters 8 free parameters · 7 assumptions · 1 invented entities

The method's mathematical core is the relaxed Hamiltonian cycle objective (Eq. 5) inherited from prior work, plus hand-selected hyperparameters and a transfer assumption from soft to hard permutations. No target quantity is used as an input; the TSP length itself is the objective, so circularity burden is low. The ledger records the free parameters and assumptions needed to make the pipeline run.

free parameters (8)
  • Adjacency distance scale s = 5.0
    Sets A = exp(-D/s) in Eq. 6; chosen by hand to match the training/inference distance scale; controls graph connectivity and therefore message passing.
  • Gumbel-Sinkhorn temperature τ = 3 (TSP100/200), 3.5 (TSP500)
    Controls softness of the permutation relaxation in Eq. 8; selected per problem size.
  • Gumbel noise magnitude γ = not reported
    Scales Gumbel noise in Eq. 8; no value or schedule is given in the text.
  • Sinkhorn iterations l = not reported
    Number of row/column normalizations in Eq. 8; affects how close T is to a permutation.
  • Fourier harmonic count M = not reported
    Number of angular harmonics in Eq. 17; determines feature dimensionality and angular resolution.
  • Logit scaling α = not reported
    Scales tanh output in Eq. 7; controls entropy of the logits before Sinkhorn.
  • Dropout probability = 0.1 (TSP100/200), 0.5 (TSP500)
    Used during training and retained at inference for MC dropout; chosen with other hyperparameters via validation.
  • Ensemble sizes (snapshots, MC passes) = 5 snapshots; 10 MC passes
    Diversity-generation settings in Tables 1-3; best solution selected per instance.
assumptions (7)
  • standard math Sinkhorn-Knopp theorem: iterative normalization of a positive matrix converges to a doubly stochastic matrix
    Used in Eq. 8 to make the Gumbel-Sinkhorn output a soft permutation; no convergence rate or finite-iteration guarantee is stated.
  • standard math Hungarian algorithm returns an optimal assignment for any square cost matrix
    Used in Eq. 9 to decode a discrete permutation from learned logits; assumes exact minimization is computationally feasible at the tested sizes.
  • standard math Hamiltonian cycles are in one-to-one correspondence with permutation matrices via H = P V P^T
    Matrix formulation (Eq. 4) from Min & Gomes 2023; fixes a canonical cycle orientation.
  • standard math Covariance eigenvectors provide a canonical frame that is almost-everywhere rotation-invariant under the stated sign convention
    Used in Theorem 3 and Eq. 13; excludes isotropic covariance (λ1=λ2) as measure-zero.
  • domain assumption Training and test instances are i.i.d. uniform Euclidean TSP; this distribution is the relevant benchmark
    All conclusions are restricted to this distribution; no out-of-distribution evaluation is provided.
  • domain assumption Minimizing the relaxed objective with gradient descent transfers to high-quality hard tours after Hungarian decoding
    This is the core empirical premise behind Eqs. 5-9; the paper does not analyze the relaxation gap.
  • domain assumption Scattering/diffusion operators used in SCT-GNN are permutation-equivariant and implementable
    The architecture (Sec. 5.2) relies on operators from Min et al. 2022; details are not fully re-derived.
invented entities (1)
  • Equivariant coordinate feature extractor (PCA canonical frame + Fourier harmonics)
    purpose: Produces permutation-equivariant, translation/rotation-invariant node features from raw 2D coordinates (Eqs. 11-18).
    This is a new architectural component introduced in Sec. 5.1. Its value is shown only on the paper's own TSP benchmarks; no external falsifiable prediction is attached to it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph Neural Networks are Heuristics." pith.science (2026). https://pith.science/paper/LAMO54GB

@misc{pith2026260113465,
  author       = {Pith},
  title        = {Pith review of: Graph Neural Networks are Heuristics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAMO54GB}},
  note         = {Machine review of arXiv:2601.13465}
}
read the original abstract

Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.

Figures

Figures reproduced from arXiv: 2601.13465 by the authors.

Figure 1
Figure 1. Training history on different sizes. 1,000 for testing. All experiments are conducted on a compute cluster equipped with Intel Xeon Gold 6154 CPUs and NVIDIA A100 GPUs. 7 Results [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Comparison showing our model vs. greedy nearest neighbor baseline. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 3 linked inside Pith

  1. [3]

    Attention, learn to solve routing problems!arXiv preprint arXiv:1803.08475,

    Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems!arXiv preprint arXiv:1803.08475,

    arXiv

  2. [1973]

    Learning latent permutations with gumbel-sinkhorn networks.arXiv preprint arXiv:1802.08665,

    Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel-sinkhorn networks.arXiv preprint arXiv:1802.08665,

    arXiv

  3. [1976]

    Learning heuristics for the tsp by policy gradient

    Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. InIntegration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings 15, pages 170–181. Springer,

    2018

  4. [2017]

    An efficient graph convolutional network technique for the travelling salesman problem.arXiv preprint arXiv:1906.01227,

    11 Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem.arXiv preprint arXiv:1906.01227,

    arXiv 1906

  5. [2018]

    Unsupervised learning permutations for tsp using gumbel-sinkhorn operator

    Yimeng Min and Carla Gomes. Unsupervised learning permutations for tsp using gumbel-sinkhorn operator. InNeurIPS 2023 Workshop Optimal Transport and Machine Learning,

    2023

  6. [2023]

    Structure as search: Unsupervised permutation learning for com- binatorial optimization.arXiv preprint arXiv:2507.04164,

    Yimeng Min and Carla P Gomes. Structure as search: Unsupervised permutation learning for com- binatorial optimization.arXiv preprint arXiv:2507.04164,

    arXiv

Pith tools

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