Unsupervised Learning for the Elementary Shortest Path Problem

Jingyi Chen, Xinyuan Zhang, Xinwu Qian · 2025

Read Unsupervised Learning for the Elementary Shortest Path Problem by Jingyi Chen, Xinyuan Zhang, Xinwu Qian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01557.txt.

Introduction

Jingyi Chen, Xinyuan Zhang, and Xinwu Qian present a learning method for a hard routing problem in a 2025 paper. The elementary shortest path problem asks for the cheapest route between two points that never revisits a node. Loops that lower cost make it NP-hard, so exact answers are out of reach for large graphs. Their method learns its way toward near-best routes without labeled examples.

A graph neural network learns two things at once: a value guess for each node and a probability for choosing each edge. A stand-in loss rewards setups that promise near-optimal routes with high probability, while cutting cost-lowering loops. At use time, a decoder turns the edge probabilities into a single valid path. On graphs up to a hundred nodes, the method beat both rival learning schemes and classic heuristics, and it carried well to new sizes and shapes.

Catalog record

CREATORJingyi Chen, Xinyuan Zhang, Xinwu Qian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01557

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unsupervised Learning for the Elementary Shortest Path Problem Jingyi Chen, Xinyuan Zhang, Xinwu Qian Abstract The Elementary Shortest‑Path Problem (ESPP) seeks a minimum cost path from s s to t t that visits each vertex at most once. The presence of negative-cost cycles renders the problem 𝒩 ​ 𝒫 \mathcal{NP} ‑hard. We present a probabilistic method for finding near-optimal ESPP, enabled by an unsupervised graph neural network that jointly learns node value estimates and edge-selection probabilities via a surrogate loss function. The loss provides a high probability certificate of finding near-optimal ESPP solutions by simultaneously reducing negative-cost cycles and embedding the desired algorithmic alignment. At inference time, a decoding algorithm transforms the learned edge probabilities into an elementary path. Experiments on graphs of up to 100 nodes show that the proposed method surpasses both unsupervised baselines and classical heuristics, while exhibiting high performance in cross-size and cross-topology generalization on unseen synthetic graphs. 1 Introduction Given a weighted directed graph G=(V,E,w) , the Elementary Shortest-Path Problem (ESPP) seeks a minimum‑cost s-t path from a source s to a sink t , visiting each vertex at most once. It reduces to the standard shortest path problems (SPP) if the graph is acyclic. However, in general graphs when negative-cost cycles (NCCs) are present, solving ESPP is known to be \mathcal{NP} -hard ( Taccari 2016 ) . The elementary visitation constraint invalidates the traditional dynamic programming (DP)-based algorithm for SPP ( Drexl and Irnich 2014 ) . As a result, exact solutions for ESPP rely on labeling algorithm whose state spaces grow exponentially in |V| ( Feillet et al. 2004 ) and shares the same worst-case computational complexity as the Traveling Salesman Problem (TSP) with profits ( Feillet, Dejax, and Gendreau 2005 ) . While challenging, ESPP carries significant practical and theoretical implications. Practically, it arises naturally in transportation systems where a subset of edges offers one-time subsidies, which imposes elementary condition and introduces negative cycles. More fundamentally, ESPP forms the cornerstone of branch-and-price algorithms widely used for solving large-scale routing and scheduling problems ( Chabrier 2006 ; Amaldi, Coniglio, and Taccari 2014 ) . In these methods, ESPP instances are repeatedly solved as pricing subproblems, and optimality is established when ESPP solutions are non-negative. Consequently, unlike many other routing problems for which heuristic solutions may suffice, ESPP explicitly requires efficient algorithms with provable performance guarantees . Recent advances in machine learning, especially Graph Neural Networks (GNNs), have driven interest in solvers for hard combinatorial optimization problems ( Smith 1999 ; Kool, Van Hoof, and Welling 2018 ; Bengio, Lodi, and Prouvost 2021 ; Gasse et al. 2022 ; Khalil, Morris, and Lodi 2022 ; Cappart et al. 2023 ) , inspiring a new wave of learning heuristics. Previous successes in solving combinatorial optimization problems such as the TSP have primarily relied on supervised and reinforcement learning approaches ( Fu, Qiu, and Zha 2021 ; Hudson et al. 2021 ; Zheng et al. 2021 ; Joshi et al. 2022 ; Cheng et al. 2023 ; Pan et al. 2023 ) . Supervised pipelines fit neural models to optimal or near‑optimal solutions, but generating such labels quickly becomes intractable as graph size grows. Reinforcement learning typically relies on non‑differentiable policy updates, resulting in high computational cost and training instability. Both reinforcement learning and supervised learning can lead to poor generalization on large graphs ( Hu 2024 ; Yang et al. 2025 ) . Unsupervised learning aids in generalization and offers a promising escape from the label bottleneck. In practice, however, designing a differentiable objective whose minima align with both feasible and near-optimal solutions is challenging. Recent approaches have shown the promise of unsupervised learning GNN to guide neural models over some combinatorial optimization problems ( Karalias and Loukas 2020 ; Min, Bai, and Gomes 2023 ) . In particular, they adopt the probabilistic method ( Karalias and Loukas 2020 ) , which constructs a learned distribution that maximizes the probability of sampling a low-cost and feasible solution. This approach offers valid solutions with polynomial-time sampling complexity. However, these methods focus on modeling the combinatorial structure directly, often introducing bilinear interactions between node variables. For ESPP, however, directly modeling the problem will involve an exponential number of flow-based constraints such as subtour elimination constraints ( Taccari 2016 ) . Relaxing those elementary constraints and incorporating them into surrogate loss functions remains an open challenge in neural optimization. In light of the above observations and limitations, we propose a new learning framework that sidesteps the need to explicitly encode exponentially complex combinatorial structures. First, instead of introducing bilinear interactions between node variables, we independently learn edge-level probabilities and node value estimates, which improves stability and convergence during the training process. Second, we avoid exponential subtour elimination constraints by learning to construct subgraphs without negative cycles, enabling the use of efficient shortest path algorithms. Finally, inspired by the principle of algorithmic alignment ( Xu et al. 2019 ) , we embed algorithmic inductive bias in both the architecture and loss, guiding the model toward valid edge sequences and improving generalization in ESPP. This study is an initial work by introducing Espp-nnaa , an unsupervised graph‑neural-network solver for the ESPP. Here, Espp-nnaa stands for E lementary S hortest P ath P roblem via N on- N egative cycle with A lgorithm A lignment. We summarize our contributions as follows: • We propose a novel probabilistic method to solve ESPP via unsupervised learning, bypassing exponentially many constraints by constructing a tractable subspace aligned with the standard shortest path problem. • We provide high probability certificates of finding near-optimal ESPP using the proposed probabilistic method. • We conduct extensive computational experiments demonstrating that Espp-nnaa achieves superior performance over state-of-the-art baselines and effectively generalizes from small training graphs to larger graphs with different topological structures. 2 Preliminaries Probabilistic Method An effective solution to mitigate the computational challenges of ESPP is to approach the problem from the lens of the probabilistic method (PM) ( Alon and Spencer 2016 ) . Specifically, if an oracle support distribution D over the edge set E is available, one can sample low-cost and feasible solutions from D in polynomial time. The difficulties, however, arise from constructing such an oracle. When the underlying mathematical problem with objective function f and constraints \Omega can be analytically expressed, one can train g_{\theta} to yield a solution distribution \mathcal{D} where a surrogate loss certifies that the distribution contains valid solutions. ( Karalias and Loukas 2020 ) . Specifically, we construct such surrogate loss function to maintain feasibility via a penalty for constrained problems: \ell(\mathcal{D};G)=\mathbb{E}_{S\sim\mathcal{D}}[f(S;G)]+\beta\cdot\mathbb{P}_{S\sim\mathcal{D}}(S\notin\Omega) Minimizing \ell(\mathcal{D};G) encourages both low cost and feasibility, and guarantees that with high probability: a sample S_{\ast}\sim\mathcal{D} exists such that S_{\ast}\in\Omega and f(S_{\ast};G)\leq\ell(\mathcal{D};G)/(1-t) . Integer Programming Formulations for ESPP Leveraging the PM for ESPP requires analytical characterizing the underlying optimization problem for ESPP. We begin by presenting the mixed-integer linear programming (MILP) formulation of ESPP ( Taccari 2016 ) and highlighting its computational challenges. Let G=(V,E,w) be a directed graph with edge costs w_{uv}\in\mathbb{R} , each node must be visited at most once. N^{+}(u) and N^{-}(u) denote the sets of downstream and upstream nodes of node u , respectively, and A(S) denotes the set of edges with

Read the complete text