kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree
KTH, School of Electrical Engineering and Computer Science (EECS), Robotics, Perception and Learning.ORCID iD: 0000-0002-6649-3325
University of Amsterdam. (Amsterdam Machine Learning Lab (AMLab))
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Algebra, Combinatorics and Topology.ORCID iD: 0009-0004-8248-229X
Universiteit Leiden. (Leiden Institute of Advanced Computer Science)
Show others and affiliations
2026 (English)In: The 29th International Conference on Artificial Intelligence and Statistics, Tangier, May 2-5, 2026., 2026Conference paper, Published paper (Refereed)
Abstract [en]

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 in to the expansion process and refines candidate trees via Riemannian gradient descent optimization. Experiments on synthetic datasets 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.

Place, publisher, year, edition, pages
2026.
Keywords [en]
hyperbolic geometry, Steiner minimal tree, optimization, machine learning, hierarchy discovery
National Category
Computer Sciences
Research subject
Computer Science; Applied and Computational Mathematics, Optimization and Systems Theory
Identifiers
URN: urn:nbn:se:kth:diva-387193OAI: oai:DiVA.org:kth-387193DiVA, id: diva2:2092548
Conference
The 29th International Conference on Artificial Intelligence and Statistics (AISTATS)
Note

QC 20260817

Available from: 2026-08-16 Created: 2026-08-16 Last updated: 2026-10-19Bibliographically approved
In thesis
1. Hyperbolic Geometric Inference: Preserve, Analyze, Extract, and Interpret Structures in Latent Data Representations
Open this publication in new window or tab >>Hyperbolic Geometric Inference: Preserve, Analyze, Extract, and Interpret Structures in Latent Data Representations
2026 (English)Doctoral thesis, comprehensive summary (Other academic) [Artistic work]
Abstract [en]

High-dimensional data are often represented in lower-dimensional latentspaces for analysis. The geometry chosen for such a representation determines how distances, neighborhoods, and other relations between observations are expressed. Hyperbolic geometry is well suited to hierarchical and tree-like data because of its negative curvature and exponential growth. Once a hyperbolic representation has been constructed, a further question arises: what information can be inferred? This thesis studies this question from the perspective of hyperbolic geometric inference: the analysis and extraction of structural information encoded in hyperbolic latent representations, together with their interpretation. We first consider the upstream problem of preserving selected structure during representation learning, using geometric and topological constraints in variational auto-encoders. We then develop methods for geometric inference from hyperbolic latent representations, with applications in single-cell biology and olfactory perception. Hyperbolic Delaunay Geometric Alignment compares predefined subsets through their Delaunay connectivity. A complementary study of olfactory descriptor data investigates radial, directional, and regional organization. Finally, HyperSteiner and Randomized HyperSteiner (RHS) construct approximate solutions to the hyperbolic Steiner minimal tree problem using Delaunay triangulation. RHS broadens the exploration of candidate tree topologies and refines Steiner-point locations through Riemannian optimization. The main contribution of this thesis is a set of methods for geometric inference from hyperbolic latent representations: quantifying geometric relations, analyzing geometric organization, and extracting parsimonious tree structures.

Abstract [sv]

Högdimensionella data representeras ofta i latenta rum med lägre dimension för analys. Den geometri som väljs för en sådan representation avgör hur avstånd, grannskap och andra relationer mellan observationer uttrycks. Hyperbolisk geometri är väl lämpad för hierarkiska och trädliknande data på grund av dess negativa krökning och exponentiella tillväxt. När en hyperbolisk representation har konstruerats uppstår frågan: vilken information kan härledas? Denna avhandling studerar denna fråga utifrån perspektivet hyperbolisk geometrisk inferens: analys och extraktion av strukturell information som är kodad i hyperboliska latenta representationer, tillsammans med tolkningen av denna information. Vi behandlar först det föregående problemet att bevara utvald struktur under representationsinlärning genom geometriska och topologiska begränsningar i variational auto-encoders. Därefter utvecklar vi metoder för geometrisk inferens från hyperboliska latenta representationer, med tillämpningar inom encellsbiologi och olfaktorisk perception. Hyperbolic Delaunay Geometric Alignment jämför fördefinierade delmängder genom deras Delaunay-konnektivitet. En kompletterande studie av olfaktoriska deskriptordata undersöker radiell, riktningsberoende och regional organisation. Slutligen konstruerar HyperSteiner och Randomized HyperSteiner (RHS) approximativa lösningar till det hyperboliska Steiner-minimalträdsproblemet med hjälp av Delaunay-triangulering. RHS breddar utforskningen av möjliga trädtopologier och förfinar Steinerpunkternas positioner genom Riemannsk optimering. Avhandlingens bidrag är metoder för geometrisk inferens från hyperboliska latenta representationer: kvantifiering av geometriska relationer, analys av organisation och extraktion av parsimoniska trädstrukturer.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2026. p. xxix, 113
Series
TRITA-EECS-AVL ; 2026:89
Keywords
Hyperbolic data analysis, computational geometry, optimization, machine learning, Hyperbolisk dataanalys, beräkningsgeometri, optimering, maskininlärning
National Category
Computer Sciences Computational Mathematics
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-390935 (URN)978-91-8106-733-0 (ISBN)
Public defence
2026-11-12, https://kth-se.zoom.us/j/65209779499, F3 (Flodis), Lindstedtsvägen 26, Stockholm, 13:00 (English)
Opponent
Supervisors
Funder
Swedish Research CouncilEU, European Research CouncilKnut and Alice Wallenberg Foundation
Note

QC 20261019

Available from: 2026-10-19 Created: 2026-10-19 Last updated: 2026-10-26Bibliographically approved

Open Access in DiVA

fulltext(1618 kB)23 downloads
File information
File name FULLTEXT01.pdfFile size 1618 kBChecksum SHA-512
e6f322d68f5e0531570dcb8ce4e6e6cedb7f23d9ffcf37a2085bcbd864a1452e16547f7700a0dad6fe1199aa7aa4983e76b9d6f72d4033e33452a4e08366c6e1
Type fulltextMimetype application/pdf

Other links

Publisher

Authority records

Medbouhi, Aniss AimanMarchetti, Giovanni LucaKragic, Danica

Search in DiVA

By author/editor
Medbouhi, Aniss AimanMarchetti, Giovanni LucaKragic, Danica
By organisation
Robotics, Perception and LearningAlgebra, Combinatorics and Topology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 23 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 586 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf