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

arXiv: https://arxiv.org/abs/2510.09328 · HTML: https://mlsanity.com/paper/2510.09328/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 77 references that are in the map.
- First posted on arXiv 10 Oct 2025.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry](https://mlsanity.com/paper/1806.03417/) (2018)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Poincar'e GloVe: Hyperbolic Word Embeddings](https://mlsanity.com/paper/1810.06546/) (2018)
- [Hyperbolic Attention Networks](https://mlsanity.com/paper/1805.09786/) (2018)
- [Riemannian Diffusion Models](https://mlsanity.com/paper/2208.07949/) (2022)
- [Continuous Hierarchical Representations with Poincar'e Variational Auto-Encoders](https://mlsanity.com/paper/1901.06033/) (2019)
- [Fully Hyperbolic Neural Networks](https://mlsanity.com/paper/2105.14686/) (2021)
- [Trivializations for Gradient-Based Optimization on Manifolds](https://mlsanity.com/paper/1909.09501/) (2019)
- [From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering](https://mlsanity.com/paper/2010.00402/) (2020)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [Latent Variable Modelling with Hyperbolic Normalizing Flows](https://mlsanity.com/paper/2002.06336/) (2020)
- [HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projections](https://mlsanity.com/paper/2106.03306/) (2021)
- [Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Space](https://mlsanity.com/paper/2407.01290/) (2024)
- [CO-SNE: Dimensionality Reduction and Visualization for Hyperbolic Data](https://mlsanity.com/paper/2111.15037/) (2021)
- [HELM: Hyperbolic Large Language Models via Mixture-of-Curvature Experts](https://mlsanity.com/paper/2505.24722/) (2025)
- [Hyperbolic Deep Reinforcement Learning](https://mlsanity.com/paper/2210.01542/) (2022)
- [Hyperbolic Deep Learning for Foundation Models: A Survey](https://mlsanity.com/paper/2507.17787/) (2025)
- [Bringing motion taxonomies to continuous domains via GPLVM on hyperbolic manifolds](https://mlsanity.com/paper/2210.01672/) (2022)
- [GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologies](https://mlsanity.com/paper/2307.03675/) (2023)
- [HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees](https://mlsanity.com/paper/2409.05671/) (2024)
- [Variational Combinatorial Sequential Monte Carlo for Bayesian Phylogenetics in Hyperbolic Space](https://mlsanity.com/paper/2501.17965/) (2025)
- [Hyperbolic Delaunay Geometric Alignment](https://mlsanity.com/paper/2404.08608/) (2024)
- [Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces](https://mlsanity.com/paper/2509.01443/) (2025)

## Built on by (most cited first, 1 of 1)

- [Geometric organization of olfactory descriptor data in the Poincar'e disk](https://mlsanity.com/paper/2609.09573/) (2026)

## Abstract (arXiv)

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.