mlsanityData to 14 Oct 2026

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

arXiv 2510.09328 ↗First posted 10 Oct 2025cs.CG cs.AIcited by 1

Not on the map. Why?

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.

Key facts. Cited by 1 paper 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

27 of 77 references.

References · 27

  1. 2017Attention Is All You Needcited by 60,361
  2. 2017Poincar'e Embeddings for Learning Hierarchical Representationscited by 684
  3. 2018Hyperbolic Neural Networkscited by 402
  4. 2018Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometrycited by 265
  5. 2018Representation Tradeoffs for Hyperbolic Embeddingscited by 206
  6. 2018Poincar'e GloVe: Hyperbolic Word Embeddingscited by 156
  7. 2018Hyperbolic Attention Networkscited by 122
  8. 2022Riemannian Diffusion Modelscited by 122
  9. 2019Continuous Hierarchical Representations with Poincar'e Variational Auto-Encoderscited by 112
  10. 2021Fully Hyperbolic Neural Networkscited by 108
  11. 2019Trivializations for Gradient-Based Optimization on Manifoldscited by 79
  12. 2020From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clusteringcited by 65
15 more
  1. 2016Global rates of convergence for nonconvex optimization on manifoldscited by 62
  2. 2017Neural Embeddings of Graphs in Hyperbolic Spacecited by 58
  3. 2020Latent Variable Modelling with Hyperbolic Normalizing Flowscited by 49
  4. 2021HoroPCA: Hyperbolic Dimensionality Reduction via Horospherical Projectionscited by 47
  5. 2024Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Spacecited by 43
  6. 2021CO-SNE: Dimensionality Reduction and Visualization for Hyperbolic Datacited by 28
  7. 2025HELM: Hyperbolic Large Language Models via Mixture-of-Curvature Expertscited by 26
  8. 2022Hyperbolic Deep Reinforcement Learningcited by 25
  9. 2025Hyperbolic Deep Learning for Foundation Models: A Surveycited by 20
  10. 2022Bringing motion taxonomies to continuous domains via GPLVM on hyperbolic manifoldscited by 10
  11. 2023GeoPhy: Differentiable Phylogenetic Inference via Geometric Gradients of Tree Topologiescited by 10
  12. 2024HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Treescited by 3
  13. 2025Variational Combinatorial Sequential Monte Carlo for Bayesian Phylogenetics in Hyperbolic Spacecited by 3
  14. 2024Hyperbolic Delaunay Geometric Alignmentcited by 2
  15. 2025Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spacescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Geometric organization of olfactory descriptor data in the Poincar'e diskcited by 1