Unsupervised Learning for the Elementary Shortest Path Problem
This addresses a challenging combinatorial optimization problem for researchers and practitioners in fields like logistics and network design, but it appears incremental as it builds on existing unsupervised and neural network approaches.
The paper tackles the NP-hard Elementary Shortest-Path Problem (ESPP) with negative-cost cycles by proposing an unsupervised graph neural network method that learns node values and edge probabilities, achieving near-optimal solutions and outperforming baselines and heuristics on graphs up to 100 nodes.
The Elementary Shortest-Path Problem(ESPP) seeks a minimum cost path from s to t that visits each vertex at most once. The presence of negative-cost cycles renders the problem 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.