arXiv:2604.20744cs.AIcs.LG2026-04

提出可微分地标压缩模块AAC,让经典最短路径算法在保持正确性的同时实现端到端训练。

AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT

论文配图:AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT
图 1 · 摘自论文原文
  • 通过构造随机行混合的下界,保证每次前向传播都满足可允许性。
  • 在道路网络上比传统方法快1.2~1.5倍,误差仅0.9~3.9个百分点。
  • 适合需要可微分启发式搜索的图神经网络与路径规划研究者。

我们提出 extbf{AAC}(架构可接受压缩器),一种针对 ALT(A*、地标与三角不等式)最短路径启发式的可微分地标选择模块。其输出在构造上始终可允许:每次前向传播均为三角不等式下界的行随机混合,因此对任意参数设置均无需收敛、校准或投影即可保证可允许性。部署时,该模块退化为基于学习子集的经典 ALT,可与神经编码器端到端结合,同时保留经典工具链。该构造是首个可微分实现‘压缩但保持可允许性’范式的实例。在每顶点内存匹配条件下,我们证明远点采样地标(FPS-ALT)在度量图上具有理论近优覆盖率,任何选择器留下的余地不足几个百分点。AAC 运行接近此上限:在9个道路网络上差距为0.9–3.9个百分点,在合成图上≤1.3个百分点,且在超过1500次查询和所有记录运行中无一例可允许性违规。在匹配内存下,AAC 在 DIMACS 道路网络上的中位查询速度比 FPS-ALT 快1.2–1.5倍,其离线开销可在170–1924次查询内摊销。受控消融实验表明,关键瓶颈是默认初始化下的训练目标漂移,而非架构容量;采用前m项恒等初始化可完全消除扩展次数差距。我们公开模块、匹配内存基准测试协议(含配对单侧检验TOST与预注册)及参考压缩差分启发式基线。

原文摘要 · Abstract (English)

We introduce \textbf{AAC} (Architecturally Admissible Compressor), a differentiable landmark-selection module for ALT (A*, Landmarks, and Triangle inequality) shortest-path heuristics whose outputs are admissible by construction: each forward pass is a row-stochastic mixture of triangle-inequality lower bounds, so the heuristic is admissible for \emph{every} parameter setting without requiring convergence, calibration, or projection. At deployment, the module reduces to classical ALT on a learned subset, composing end-to-end with neural encoders while preserving the classical toolchain. The construction is the first differentiable instance of the compress-while-preserving-admissibility tradition in classical heuristic search. Under a matched per-vertex memory protocol, we establish that ALT with farthest-point-sampling landmarks (FPS-ALT) has provably near-optimal coverage on metric graphs, leaving at most a few percentage points of headroom for \emph{any} selector. AAC operates near this ceiling: the gap is $0.9$--$3.9$ percentage points on 9 road networks and ${\leq}1.3$ percentage points on synthetic graphs, with zero admissibility violations across $1{,}500+$ queries and all logged runs. At matched memory, AAC is also $1.2$--$1.5{\times}$ faster than FPS-ALT at the median query on DIMACS road networks, amortizing its offline cost within $170$--$1{,}924$ queries. A controlled ablation isolates the binding constraint: training-objective drift under default initialization, not architectural capacity; identity-on-first-$m$ initialization closes the expansion-count gap entirely. We release the module, a reusable matched-memory benchmarking protocol with paired two-one-sided-test (TOST) equivalence and pre-registration, and a reference compressed-differential-heuristics baseline.

可微分搜索路径规划图神经网络启发式算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。