{"id":"7bfc0ed0-d9a5-4cd5-aa99-5248188a35fc","arxiv_id":"2508.01557","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"The authors propose ESPP-NNAA, an unsupervised GNN that learns node values and edge probabilities to decode near-optimal elementary paths, though the stated certificate does not cover the full trained objective.","lead":"This paper trains an unsupervised graph neural network to solve the elementary shortest path problem with negative-cost cycles, decoding likely good paths from learned edge probabilities. It claims a high-probability guarantee for near-optimal solutions and reports strong results on synthetic graphs up to 100 nodes, but the proof as written applies to a simpler loss than the one actually minimized.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1 is false: a small-cost two-edge negative cycle satisfies the stated Φ bound while surviving with probability 1/4, so Theorem 1's certificate fails even for the simplified loss.","rationale":"I read the central claim as the PAC-style guarantee that minimizing the surrogate yields a high-probability near-optimal ESPP path. For that claim to hold, Proposition 1 must be true, and the explicit 4-node construction satisfies every stated assumption while violating the conclusion by a large margin. This is a refutation of the theorem itself, not merely a missing link between the analyzed loss L and the implemented loss LFull. The reader's weakest assumption points to a genuine separation between L and LFull, but fixing that separation would not restore the certificate because the underlying probabilistic lemma is false. The paper provides no machine-checked proof, released code, or exact gap measurements at 100 nodes to offset this internal inconsistency, so the reject verdict stands. I mark agreement as partial because the decisive failure I find is in Proposition 1, not in the LFull/L mismatch the reader emphasized.","tokens_in":11685,"tokens_out":15205,"duration_ms":174477,"concrete_test":"Instantiate the 4-node counterexample: edges s→a(0), a→b(−0.0002), b→a(0), b→t(0); d(s)=d(t)=0, d(a)=d(b)=−0.0001; p_ab=p_ba=0.5, p_sa=0.1, p_bt=1. Enumerate all 16 edge subsets to compute Φ and Pr(Z=0). If Φ ≤ 0.001/8 holds while Pr(Z=0)=0.75, Proposition 1 is refuted, settling that the high-probability certificate in Theorem 1 is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1 is the probabilistic step on which Theorem 1 depends, and it is internally false as stated. Consider the graph with vertices s, a, b, t and edges s→a (cost 0), a→b (cost −η), b→a (cost 0), b→t (cost 0). Set dθ(s)=dθ(t)=0 and dθ(a)=dθ(b)=−η/2; this satisfies the printed condition dθ(u) ≤ w_uv − dθ(v) on every edge. Then δ_sa = η/2, δ_ab = η, δ_ba = 0, and δ_bt = 0. With p_ab = p_ba = 1/2, p_sa = 0.1, p_bt = 1, the surrogate equals Φ = 0.5125η. Here M = 2 and |E| = 4, so ε1 = ε/8. Taking η = 0.0002 and ε = 0.001 gives Φ ≈ 1.025e-4 ≤ 1.25e-4, satisfying the hypothesis of Proposition 1. But the negative cycle a→b→a is present whenever both of its edges survive, which has probability exactly 1/4; hence Pr(Z = 0) = 0.75, contradicting the claimed Pr(Z = 0) ≥ 1 − ε = 0.999. The proof lacks a lower bound on the positive slack of negative cycles, so its union bound over cycles cannot yield the stated guarantee. Consequently Theorem 1 is not a valid certificate even if the trained loss were exactly the simplified L; the LFull/L mismatch identified by the reader is real but secondary.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes ESPP-NNAA, an unsupervised graph-neural-network framework for the elementary shortest path problem (ESPP) on graphs with negative-cost cycles. The method learns node value estimates and edge-selection probabilities, and it minimizes a surrogate loss intended to reduce negative-cost cycles while embedding algorithmic alignment with Bellman-Ford. The paper claims a high-probability certificate of near-optimality for the decoded elementary path, and it reports experiments on Erdős–Rényi, grid, and Barabási–Albert graphs of up to 100 nodes, including comparisons with unsupervised baselines, an exact labeling algorithm, LP heuristics, beam search, and randomized decoding.","tokens_in":12093,"tokens_out":10082,"duration_ms":122192,"significance":"If the theoretical certificate were valid, the paper would be a substantial contribution: it would provide a label-free, finite-sample performance guarantee for an NP-hard combinatorial problem, and the experimental study is a genuine strength, with multiple graph families, cross-topology generalization tests, and component ablations. However, the central theoretical apparatus is not sound. The main probabilistic lemma is false as stated, and the guarantee is proved for a simplified loss that is not the objective actually minimized during training. The empirical comparisons may still be of interest, but the advertised theoretical contribution does not hold as written.","major_comments":[{"comment":"The high-probability non-negative-cycle guarantee is false as stated. Consider G with vertices s, a, b, t and edges s→a (cost 0), a→b (cost −η), b→a (cost 0), b→t (cost 0). Set dθ(s)=dθ(t)=0 and dθ(a)=dθ(b)=−η/2; the printed condition dθ(u) ≤ w_uv − dθ(v) holds on every edge. Set p_ab=p_ba=1/2, p_sa=0.1, and p_bt=1. Then δ_sa=η/2, δ_ab=η, and δ_ba=δ_bt=0, so Φθ(G)=0.5125η. For η=0.0002 and ε=0.001, we have Φθ(G)=1.025×10^{-4} ≤ ε/(M|E|)=1.25×10^{-4}, but the negative cycle a→b→a survives with probability p_ab p_ba = 1/4, so Pr(Z̃=0)=0.75, contradicting the claimed Pr(Z̃=0) ≥ 0.999. The union-bound proof lacks any lower bound on the positive slack of surviving negative cycles; a negative cycle with tiny edge violations can survive with high probability while keeping Φ small. Proposition 1 is therefore not a valid certificate, and Theorem 1, which depends on it, does not establish the advertised guarantee.","section":"Section 3, Proposition 1"},{"comment":"Theorem 1 bounds the simplified loss L(G,θ)=λ1|F^{(k*+1)}_θ(G)−F^{(k*)}_θ(G)|+λ2Φθ(G), but the objective actually trained is LFull(θ)=E[LADV+λ1LFlow+λ2Φθ+λ3(LDA+LDPA+LAB)]. No inequality in the paper relates LFull to L: LADV=Σ_uv w_uv p_uv − c_LP may be negative, and LFlow is a flow-conservation penalty, not the value-operator difference appearing in Theorem 1. Consequently, even if Proposition 1 were correct, minimizing LFull on training graphs does not imply the small empirical L(G_i,θ̂) required for the high-probability near-optimality conclusion. The certificate is established only for a loss that the manuscript does not train.","section":"Section 4, Integrated Surrogate Loss Function"},{"comment":"The deterministic bound Δ(G,θ) ≤ K1ε1 + K2ε2 is asserted without proof in the main text, and the constants K1, K2 are not shown to be uniform over G and θ. The optimality gap Δ belongs to a decoded path and therefore depends on the sampled edge probabilities, whereas the right-hand side depends on puv only through one term of Φθ(G). Without an explicit construction of K1 and K2 that is uniform in the quantities entering the concentration argument, the stated inequality is vacuous: for a fixed finite graph and parameters, some K1,K2 always exist regardless of whether the bound carries any information. The subsequent use of K=max(K1/λ2, K2/λ1) in Theorem 1 requires such uniformity, and the paper provides no argument for it.","section":"Section 3, Lemma 2"}],"minor_comments":[{"comment":"The displayed condition dθ(u) ≤ w_uv − dθ(v) is inconsistent with the definition δ_uv=[dθ(u)−w_uv−dθ(v)]_+, which measures violation of dθ(u) ≤ w_uv + dθ(v). The sign error propagates into Proposition 1 and Lemma 1; the correct Bellman-style condition should be dθ(u) ≤ w_uv + dθ(v).","section":"Section 3, Definition 3"},{"comment":"The caption of Table 1 does not define the reported 'gap'; because the values are negative and Definition 1 defines Δ(G,θ)≥0, the gap appears to be computed relative to beam search rather than relative to the optimal path. Please state the reference solver and the exact formula used for the percentage gap.","section":"Section 5, Table 1"},{"comment":"The hyperparameters λ1, λ2, λ3, the temperature τ, the number of unrolled Bellman-Ford steps T, and the number of decoding samples N are introduced but no values or ranges are reported in the experiments. Reporting these values would substantially improve reproducibility.","section":"Section 4 and Section 5"},{"comment":"The random variable Z̃ is described as the random number of negative-cost cycles, but the underlying probability space is not formalized in the main text. The proof appears to assume independent edge survival with probabilities p_uv; this should be stated explicitly before the proposition.","section":"Section 3, Proposition 1"}],"recommendation":"reject","confidential_remarks":"The rejection is driven by the counterexample to Proposition 1 and by the mismatch between the certified loss and the trained loss. These are load-bearing issues: the paper's main advertised contribution is the high-probability guarantee, and that guarantee is not established. The experimental section is reasonably broad, but without the theoretical certificate the contribution is largely empirical and incremental relative to existing unsupervised combinatorial-optimization methods. I would not ask for a revision solely on presentation grounds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the empirical method is genuinely new and works well in their tests: it is the first unsupervised GNN solver for the elementary shortest path problem with negative-cost cycles, and the results on graphs up to 100 nodes are strong, with sensible ablations. Second, the theoretical guarantee that the paper sells as its headline contribution is not supported. The stress-test counterexample is correct: Proposition 1 is false. Take the graph with s→a, a→b (cost −η), b→a, b→t, and set dθ(s)=dθ(t)=0, dθ(a)=dθ(b)=−η/2; the printed condition dθ(u) ≤ wuv − dθ(v) holds on every edge, yet the negative cycle a→b→a survives with probability 1/4 while Φ is below the stated threshold, so the claimed probability ≥ 1−ε fails. The sign error in Definition 3 also makes Lemma 1 false as written. The reader is right about a second problem: Theorem 1 bounds a simplified loss λ1|F(k*+1)−F(k*)| + λ2Φ, but the actual training objective LFull adds a potentially negative advantage term LADV and three alignment losses, with no inequality connecting LFull to the bounded L. So even if Proposition 1 were fixed, the certificate would not apply to the trained model.\n\nWhat is good: the problem is important, the idea of learning edge probabilities via the probabilistic method to avoid exponential subtour constraints is sensible, and the empirical study is more thorough than typical for a first paper on this topic. The ablations are informative, especially the distributional alignment loss, and the cross-topology generalization results are credible. The main disappointment is the gap between the empirical work and the theory: the paper does not provide exact optimality gaps at 100 nodes, and no code or data are released. Given the theory is central, the current manuscript is not publishable as is. But the method may still be useful as a heuristic. I would send this to a serious referee, focusing on the theoretical claims, rather than desk-reject it, because the empirical contribution deserves evaluation. As it stands, I would not cite the certificate, only the heuristic, and only after seeing code.","headline":"Novel unsupervised heuristic for ESPP, but the paper's central high-probability certificate is not valid as stated, and the trained loss is not the one being bounded.","tokens_in":12547,"tokens_out":4505,"would_cite":false,"duration_ms":48373,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A neural solver can find near-optimal elementary paths without any labeled solutions, and it comes with a high-probability guarantee.","keywords":["elementary shortest path problem","negative-cost cycles","unsupervised graph neural network","probabilistic method","algorithmic alignment","value function estimation","Bellman-Ford","high-probability certificate"],"falsifier":"Train ESPP-NNAA while logging the certified loss L = λ1|$F_θ^{{(k*+1)}}$ − $F_θ^{{(k*)}}$| + λ2Φ_θ; if L_Full decreases while L stays large or grows on graphs that still contain negative-cost cycles, the theorem does not apply to the trained model. Conversely, on any graph family where a model with small L decodes paths with large optimality gap, the Lemma 2 bound would be violated.","tokens_in":11475,"feed_emoji":"🛤️","tokens_out":4344,"duration_ms":49216,"temperature":0.7,"pith_summary":"The paper sets out to show that the Elementary Shortest Path Problem, which is NP-hard in the presence of negative-cost cycles, can be solved near-optimally without any labeled solutions. It trains an unsupervised graph neural network to output node value estimates and edge-selection probabilities, and proves that a particular surrogate loss gives a high-probability certificate that the decoded path's cost is within some tolerance of optimal. The key move is to avoid the exponentially many subtour-elimination constraints by driving the learned subgraph free of negative-cost cycles, so that standard shortest-path reasoning applies. Experiments on random, grid, and scale-free graphs up to 100 nodes support the claim that the method outperforms unsupervised baselines and classical heuristics and generalizes across sizes and topologies.","feed_headline":"No labels needed: neural solver certifies near-optimal elementary paths","feed_subtitle":"Training on random graphs transfers to grid and scale-free networks, beating exact solvers and heuristics up to 100 nodes.","key_machinery":"The load-bearing device is the negative-cost-cycle surrogate Φ_θ(G), defined as the average over edges of the slack δ_uv = [d_θ(u) − w_uv − d_θ(v)]_+ plus a probability-weighted version of the same slack; when the learned value estimates satisfy d_θ(u) ≤ w_uv + d_θ(v) on every edge, no negative-cost cycle survives in the weighted subgraph. Coupled with the value-operator alignment term |$F_θ^{{(k*+1)}}$(G) − $F_θ^{{(k*)}}$(G)|, the loss L = λ1 times that alignment term plus λ2 times Φ supplies the high-probability near-optimality certificate. In the implemented model, a message-passing network with a min-aggregation mirroring the Bellman operator outputs d_θ(v), edge probabilities p_uv = σ(d_θ(v) − d_θ(u)), and the full loss adds flow conservation, distributional alignment to a softmax target, softmin dynamic-programming alignment, unrolled Bellman-Ford consistency, and an advantage baseline from a fractional LP relaxation.","core_discovery":"The paper claims that the Elementary Shortest Path Problem becomes tractable in practice through an unsupervised graph neural network that jointly learns a node value function and edge probabilities from a surrogate loss. The central assertion is Theorem 1: with enough independent training graphs, if the empirical surrogate loss is small, then with probability at least 1−β over the training data, the decoded elementary path has optimality gap larger than γ with probability at most α. The proof decomposes the objective into a value-operator alignment term and a negative-cost-cycle surrogate, showing that a small surrogate forces the absence of negative cycles with high probability, after which an elementary shortest path exists and the optimality gap is bounded.","pith_inferences":["The certificate theorem bounds only the two-term loss L, while training minimizes L_Full, which includes a negative advantage term and three additional inductive-bias terms; closing that gap would require proving that minimizing L_Full controls L, or re-proving the theorem directly for L_Full.","The same negative-cycle surrogate could be applied to other combinatorial problems where feasibility is enforced by eliminating forbidden structures rather than by adding exponential constraint sets, such as resource-constrained or prize-collecting path variants.","A testable extension is to measure the empirical distribution of Φ and the Bellman residual on held-out graphs during training; the certificate predicts that small Φ concentrates probability on negative-cycle-free subgraphs, which could be checked directly.","Because the decoder is sequential and elementary by construction, the method could be plugged into column-generation pricing loops where current LP reduced costs define edge weights, an application the paper names but does not implement."],"forward_implications":["Elementary paths can be decoded in polynomial time from learned probabilities, and increasing the number of decoding samples reduces the optimality gap, with 200 samples nearly matching exact solutions on 30- and 50-node graphs.","Training on small Erdős–Rényi graphs transfers to larger graphs and to grid and Barabási–Albert topologies, so the learned value functions appear to capture routing structure rather than memorizing instances.","The certificate is directly relevant to branch-and-price frameworks, where repeatedly solving ESPP as a pricing subproblem requires provable performance guarantees rather than heuristic-only solutions.","Ablations show that the distributional alignment term is the most critical component; removing it collapses the gap from roughly −76% to −3% at 50 nodes, indicating that aligning edge probabilities with Bellman-optimal transitions carries most of the solution quality."],"supporting_citations":[{"why":"Supplies the probabilistic-method surrogate-loss framework that the paper adapts to ESPP.","marker":"Karalias and Loukas 2020"},{"why":"Provides the MILP formulation of ESPP with exponential subtour-elimination constraints that the method bypasses.","marker":"Taccari 2016"},{"why":"Gives the exact labeling algorithm used as a baseline and the source of the exponential state-space claim.","marker":"Feillet et al. 2004"},{"why":"Motivates the algorithmic-alignment inductive biases embedded in the architecture and loss.","marker":"Xu et al. 2019"},{"why":"Defines the Bellman-Ford iteration that the paper unrolls as differentiable layers and whose convergence anchors the value-operator alignment.","marker":"Bellman 1958"},{"why":"Establishes that dynamic programming is invalid for ESPP, motivating the surrogate loss and non-negative-cycle reduction.","marker":"Drexl and Irnich 2014"}],"fun_headline_variants":["Unsupervised neural net finds near-optimal elementary paths","No labels, no problem: GNN solves elementary shortest paths","Learning to certify near-optimal paths without supervision","GNN beats heuristics on elementary shortest paths without labels","Probabilistic certificate for elementary paths via unsupervised GNN"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The practical training loss L_Full includes terms beyond the two-term loss that Theorem 1 certifies, and the paper gives no proof that minimizing L_Full keeps the certified loss small.","fun_headline_variants_meta":{"raw":{"variants":["Unsupervised neural net finds near-optimal elementary paths","No labels, no problem: GNN solves elementary shortest paths","Learning to certify near-optimal paths without supervision","GNN beats heuristics on elementary shortest paths without labels","Probabilistic certificate for elementary paths via unsupervised GNN"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00074,"raw_usage":{"total_tokens":3239,"prompt_tokens":816,"completion_tokens":2423,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":432,"completion_tokens_details":{"reasoning_tokens":2343}},"tokens_in":432,"tokens_out":2423,"duration_ms":18994,"temperature":1.0,"reasoning_tokens":2343,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T05:33:10.626263+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train ESPP-NNAA while logging the certified loss L = λ1|$F_θ^{{(k*+1)}}$ − $F_θ^{{(k*)}}$| + λ2Φ_θ; if L_Full decreases while L stays large or grows on graphs that still contain negative-cost cycles, the theorem does not apply to the trained model. Conversely, on any graph family where a model with small L decodes paths with large optimality gap, the Lemma 2 bound would be violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the probabilistic-method surrogate-loss framework that the paper adapts to ESPP."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the MILP formulation of ESPP with exponential subtour-elimination constraints that the method bypasses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the exact labeling algorithm used as a baseline and the source of the exponential state-space claim."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Bellman-Ford iteration that the paper unrolls as differentiable layers and whose convergence anchors the value-operator alignment."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that dynamic programming is invalid for ESPP, motivating the surrogate loss and non-negative-cycle reduction."}],"review_version":1}