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

• URL: http://arxiv.org/abs/2510.09328v1
• Date: Fri, 10 Oct 2025 12:31:55 GMT
• Title: Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree
• Abstract summary: We introduce Randomized HyperSteiner (RHS) to solve the problem of constructing Steiner Minimal Trees (SMTs) in hyperbolic space.<n>RHS incorporates randomness into the expansion process and refines candidate trees via a Delaunay triangulation gradient.<n>In near-boundary configurations, RHS can achieve a 32% reduction in total length over HS.
• Score: 51.52916554719886
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Multi-Source Complex Network Reconstruction via Wasserstein Distributionally Robust Optimization and Algorithm Unrolling [9.526111877241602]
  We propose MS-WDRO, a graph learning framework that fuses heterogeneous sources via their weighted Wasserstein barycenter.<n>Minimizing worst-case risk yields a tractable regularized Laplacian estimator solved efficiently via a provably convergent ADMM scheme.<n>MS-WDRO consistently outperforms seven baselines in graph recovery, sample efficiency, and downstream diagnostic utility.
  arXiv  Detail & Related papers  (2026-08-20T11:30:59Z)
• Simplicial Gaussian Models: Representation and Inference [13.687470962704744]
  We propose the simplicial Gaussian model (SGM), which extends Gaussian PGM to simplicial complexes.<n>Our model builds upon discrete Hodge theory and incorporates uncertainty at every topological level through independent random components.<n>Motivated by applications, we focus on the marginal edge-level distribution while treating node- and triangle-level variables as latent.
  arXiv  Detail & Related papers  (2025-10-14T20:51:56Z)
• FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data [0.0]
  Fast Approximate Minimum Spanning Tree (FAMST) is a novel algorithm that addresses the computational challenges of constructing Minimum Spanning Trees (MSTs)<n>FAMST enables MST-based analysis on datasets with millions of points and thousands of dimensions, extending the applicability of MST techniques to problem scales previously considered infeasible.
  arXiv  Detail & Related papers  (2025-07-18T12:53:58Z)
• Fast hyperboloid decision tree algorithms [0.6656737591902598]
  We present hyperDT, a novel extension of decision tree algorithms into hyperbolic space. Our approach is conceptually straightforward and maintains constant-time decision complexity. Building upon hyperDT we introduce hyperRF, a hyperbolic random forest model.
  arXiv  Detail & Related papers  (2023-10-20T22:31:10Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  In contextual bandits, an agent sequentially makes actions from a time-dependent action set based on past experience. We propose the first online continuous hyperparameter tuning framework for contextual bandits. We show that it could achieve a sublinear regret in theory and performs consistently better than all existing methods on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2023-02-18T23:31:20Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Hyperspectral Image Super-Resolution with Spectral Mixup and Heterogeneous Datasets [99.92564298432387]
  This work studies Hyperspectral image (HSI) super-resolution (SR) HSI SR is characterized by high-dimensional data and a limited amount of training examples. This exacerbates the undesirable behaviors of neural networks such as memorization and sensitivity to out-of-distribution samples.
  arXiv  Detail & Related papers  (2021-01-19T12:19:53Z)
• Sinkhorn Natural Gradient for Generative Models [125.89871274202439]
  We propose a novel Sinkhorn Natural Gradient (SiNG) algorithm which acts as a steepest descent method on the probability space endowed with the Sinkhorn divergence. We show that the Sinkhorn information matrix (SIM), a key component of SiNG, has an explicit expression and can be evaluated accurately in complexity that scales logarithmically. In our experiments, we quantitatively compare SiNG with state-of-the-art SGD-type solvers on generative tasks to demonstrate its efficiency and efficacy of our method.
  arXiv  Detail & Related papers  (2020-11-09T02:51:17Z)
• An Asymptotically Optimal Multi-Armed Bandit Algorithm and Hyperparameter Optimization [48.5614138038673]
  We propose an efficient and robust bandit-based algorithm called Sub-Sampling (SS) in the scenario of hyper parameter search evaluation. We also develop a novel hyper parameter optimization algorithm called BOSS. Empirical studies validate our theoretical arguments of SS and demonstrate the superior performance of BOSS on a number of applications.
  arXiv  Detail & Related papers  (2020-07-11T03:15:21Z)
• Augmented Sliced Wasserstein Distances [55.028065567756066]
  We propose a new family of distance metrics, called augmented sliced Wasserstein distances (ASWDs) ASWDs are constructed by first mapping samples to higher-dimensional hypersurfaces parameterized by neural networks. Numerical results demonstrate that the ASWD significantly outperforms other Wasserstein variants for both synthetic and real-world problems.
  arXiv  Detail & Related papers  (2020-06-15T23:00:08Z)
• The Statistical Cost of Robust Kernel Hyperparameter Tuning [20.42751031392928]
  We study the statistical complexity of kernel hyperparameter tuning in the setting of active regression under adversarial noise. We provide finite-sample guarantees for the problem, characterizing how increasing the complexity of the kernel class increases the complexity of learning kernel hyper parameters.
  arXiv  Detail & Related papers  (2020-06-14T21:56:33Z)
• Stochastic geometry to generalize the Mondrian Process [0.0]
  We show that a STIT process with cut directions drawn from a discrete distribution can be efficiently simulated by lifting to a higher dimensional axis-aligned Mondrian process. We also characterize all possible kernels that stationary STIT processes and their mixtures can approximate. This allows for precise comparisons between the Mondrian forest, the Mondrian kernel and the Laplace kernel in density estimation.
  arXiv  Detail & Related papers  (2020-02-03T14:47:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.