用无监督图神经网络找最短路径，能高效避开负权环并泛化到新图。
Unsupervised Learning for the Elementary Shortest Path Problem
- 用无监督GNN联合学习节点价值和边选择概率，通过代理损失优化。
- 在100节点图上优于传统启发式方法，跨规模跨拓扑泛化能力强。
- 适合需要快速求解复杂最短路径的算法研究者或工业应用者。
基本最短路径问题（ESPP）要求从起点s到终点t找到一条不重复经过任一顶点且总成本最低的路径。由于存在负成本环，该问题属于NP难。本文提出一种基于概率的近似求解方法，利用无监督图神经网络联合学习节点值估计与边选择概率，通过代理损失函数实现优化。该损失函数在降低负成本环的同时，嵌入了期望的算法对齐结构，提供高概率保证找到接近最优的解。推理阶段，采用解码算法将学习到的边概率转化为一条基本路径。在最多100个节点的图上进行实验，结果表明该方法优于所有无监督基线及经典启发式方法，并在未见过的合成图上展现出优异的跨规模与跨拓扑泛化能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。