随机化方法提升双曲空间斯坦纳树构建效率与质量。
Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree
- 引入随机性与黎曼梯度优化，改进原有确定性算法
- 在近边界场景下比基线降低32%总长度
- 适合处理高维生物数据等复杂结构问题
我们研究双曲空间中构造斯坦纳最小树（SMT）的问题。精确计算SMT是NP难的，现有超双曲启发式方法如HyperSteiner（HS）为确定性算法，常陷入局部次优解。本文提出随机化超双曲斯坦纳树（RHS），一种基于随机Delaunay三角剖分的启发式方法，将随机性融入扩展过程，并通过黎曼梯度下降优化候选树。在合成数据集和真实单细胞转录组数据上的实验表明，RHS优于最小生成树（MST）、邻接法（Neighbour Joining）及原始的HyperSteiner（HS）。在近边界配置中，RHS可实现较HS降低32%的总长度，展现出优异的性能与鲁棒性。
原文摘要 · Abstract (English)
We study the problem of constructing Steiner Minimal Trees (SMTs) in hyperbolic space. Exact SMT computation is NP-hard, and existing hyperbolic heuristics such as HyperSteiner are deterministic and often get trapped in locally suboptimal configurations. We introduce Randomized HyperSteiner (RHS), a stochastic Delaunay triangulation heuristic that incorporates randomness into the expansion process and refines candidate trees via Riemannian gradient descent optimization. Experiments on synthetic data sets and a real-world single-cell transcriptomic data show that RHS outperforms Minimum Spanning Tree (MST), Neighbour Joining, and vanilla HyperSteiner (HS). In near-boundary configurations, RHS can achieve a 32% reduction in total length over HS, demonstrating its effectiveness and robustness in diverse data regimes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。