Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree

arXiv (Cornell University)

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.

Authors 6

1. Aniss Aiman Medbouhi

   KTH Royal Institute of Technology

   Affiliation as printed

   School of Electrical Engineering and Computer Science , KTH Royal Institute of Technology

2. Alejandro García-Castellanos

   University of Amsterdam

   Affiliation as printed

   Amsterdam Machine Learning Lab (AMLab) , University of Amsterdam

3. Giovanni Luca Marchetti

   KTH Royal Institute of Technology

   Affiliation as printed

   School of Engineering Sciences , KTH Royal Institute of Technology

4. Daniël M. Pelt Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science , Universiteit Leiden

5. Erik J. Bekkers

   University of Amsterdam

   Affiliation as printed

   Amsterdam Machine Learning Lab (AMLab) , University of Amsterdam

6. Danica Kragić

   KTH Royal Institute of Technology

   Affiliation as printed

   School of Electrical Engineering and Computer Science , KTH Royal Institute of Technology