Abstract
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.
Abstract (translated)
我们研究了在双曲空间中构造斯特恩最小树（SMTs）的问题。精确的SMT计算是NP难问题，现有的如HyperSteiner之类的双曲启发式算法通常是确定性的，并且往往陷入局部次优解。我们引入了一种随机化HyPerSteiner (RHS) 方法，这是一种采用随机方法进行Delaunay三角剖分的启发式算法，在扩展过程中加入随机性并通过黎曼梯度下降优化来改进候选树。在合成数据集和实际单细胞转录组数据上的实验表明，与最小生成树（MST）、邻接连接法以及标准HyperSteiner (HS) 相比，RHS表现更优。在接近边界配置的情况下，RHS可以比HS减少32%的总长度，这证明了它在不同数据环境下的有效性和鲁棒性。
URL
https://arxiv.org/abs/2510.09328
