mlsanityData to 14 Oct 2026

Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures

arXiv 2308.09250 ↗First posted 18 Aug 2023cs.LG cs.DM cs.NAcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the representation capacity of deep hyperbolic neural networks (HNNs) with a ReLU activation function. We establish the first proof that HNNs can varepsilon-isometrically embed any finite weighted tree into a hyperbolic space of dimension d at least equal to 2 with prescribed sectional curvature kappa<0, for any varepsilon> 1 (where varepsilon=1 being optimal). We establish rigorous upper bounds for the network complexity on an HNN implementing the embedding. We find that the network complexity of HNN implementing the graph representation is independent of the representation fidelity/distortion. We contrast this result against our lower bounds on distortion which any ReLU multi-layer perceptron (MLP) must exert when embedding a tree with L>2d leaves into a d-dimensional Euclidean space, which we show at least Omega(L1/d); independently of the depth, width, and (possibly discontinuous) activation function defining the MLP.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 36 of its 79 references that are in the map. First posted on arXiv 18 Aug 2023.

Builds on

36 of 79 references.

References · 36

  1. 2017Poincar'e Embeddings for Learning Hierarchical Representationscited by 684
  2. 2016Error bounds for approximations with deep ReLU networkscited by 574
  3. 2018Hyperbolic Neural Networkscited by 402
  4. 2019Hyperbolic Graph Convolutional Neural Networkscited by 402
  5. 2019Hyperbolic Graph Neural Networkscited by 244
  6. 2020Low-Dimensional Hyperbolic Knowledge Graph Embeddingscited by 195
  7. 2018Hyperbolic Entailment Cones for Learning Hierarchical Embeddingscited by 162
  8. 2019Multi-relational Poincar'e Graph Embeddingscited by 126
  9. 2018Hyperbolic Attention Networkscited by 122
  10. 2013Manopt, a Matlab toolbox for optimization on manifoldscited by 113
  11. 2019Constant Curvature Graph Convolutional Networkscited by 108
  12. 2016Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiationcited by 94
24 more
  1. 2019Mixed-curvature Variational Autoencoderscited by 86
  2. 2020Differentiable Graph Module (DGM) for Graph Convolutional Networkscited by 86
  3. 2018Embedding Text in Hyperbolic Spacescited by 76
  4. 2018geomstats: a Python Package for Riemannian Geometry in Machine Learningcited by 71
  5. 2019Hyperbolic Graph Attention Networkcited by 70
  6. 2020Graph Geometry Interaction Learningcited by 55
  7. 2018HyperML: A Boosting Metric Learning Approach in Hyperbolic Space for Recommender Systemscited by 47
  8. 2021Universal Approximation Theorems for Differentiable Geometric Deep Learningcited by 41
  9. 2020Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embeddingcited by 36
  10. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  11. 2015Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Supportcited by 30
  12. 2020Non-Euclidean Universal Approximationcited by 29
  13. 2020HyperText: Endowing FastText with Hyperbolic Geometrycited by 28
  14. 2022Hyperbolic Deep Reinforcement Learningcited by 25
  15. 2017Hyperbolic Representation Learning for Fast and Efficient Neural Question Answeringcited by 23
  16. 2022Heterogeneous manifolds for curvature-aware graph embeddingcited by 23
  17. 2022Latent Graph Inference using Product Manifoldscited by 23
  18. 2020Ultrahyperbolic Representation Learningcited by 17
  19. 2022Small Transformers Compute Universal Metric Embeddingscited by 12
  20. 2019Hydra: A method for strain-minimizing hyperbolic embedding of network- and distance-based datacited by 11
  21. 2023Topological Point Cloud Clusteringcited by 5
  22. 2020Are Hyperbolic Representations in Graphs Created Equal?cited by 4
  23. 2023High-dimensional Clustering onto Hamiltonian Cyclecited by 2
  24. 2023Online embedding of metricscited by 1

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 2.

4 papers.

  1. 2023Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometriescited by 6
  2. 2024Neural Spacetimes for DAG Representation Learningcited by 5
  3. 2023AMES: A Differentiable Embedding Space Selection Framework for Latent Graph Inferencecited by 3
  4. 2024Metric Learning for Clifford Group Equivariant Neural Networkscited by 0