# Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures

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

## 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 (most cited first, 30 of 36)

- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [Hyperbolic Graph Convolutional Neural Networks](https://mlsanity.com/paper/1910.12933/) (2019)
- [Hyperbolic Graph Neural Networks](https://mlsanity.com/paper/1910.12892/) (2019)
- [Low-Dimensional Hyperbolic Knowledge Graph Embeddings](https://mlsanity.com/paper/2005.00545/) (2020)
- [Hyperbolic Entailment Cones for Learning Hierarchical Embeddings](https://mlsanity.com/paper/1804.01882/) (2018)
- [Multi-relational Poincar'e Graph Embeddings](https://mlsanity.com/paper/1905.09791/) (2019)
- [Hyperbolic Attention Networks](https://mlsanity.com/paper/1805.09786/) (2018)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Constant Curvature Graph Convolutional Networks](https://mlsanity.com/paper/1911.05076/) (2019)
- [Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation](https://mlsanity.com/paper/1603.03236/) (2016)
- [Mixed-curvature Variational Autoencoders](https://mlsanity.com/paper/1911.08411/) (2019)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [Embedding Text in Hyperbolic Spaces](https://mlsanity.com/paper/1806.04313/) (2018)
- [geomstats: a Python Package for Riemannian Geometry in Machine Learning](https://mlsanity.com/paper/1805.08308/) (2018)
- [Hyperbolic Graph Attention Network](https://mlsanity.com/paper/1912.03046/) (2019)
- [Graph Geometry Interaction Learning](https://mlsanity.com/paper/2010.12135/) (2020)
- [HyperML: A Boosting Metric Learning Approach in Hyperbolic Space for Recommender Systems](https://mlsanity.com/paper/1809.01703/) (2018)
- [Universal Approximation Theorems for Differentiable Geometric Deep Learning](https://mlsanity.com/paper/2101.05390/) (2021)
- [Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding](https://mlsanity.com/paper/2005.03847/) (2020)
- [Provable Memorization via Deep Neural Networks using Sub-linear Parameters](https://mlsanity.com/paper/2010.13363/) (2020)
- [Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support](https://mlsanity.com/paper/1510.00012/) (2015)
- [Non-Euclidean Universal Approximation](https://mlsanity.com/paper/2006.02341/) (2020)
- [HyperText: Endowing FastText with Hyperbolic Geometry](https://mlsanity.com/paper/2010.16143/) (2020)
- [Hyperbolic Deep Reinforcement Learning](https://mlsanity.com/paper/2210.01542/) (2022)
- [Hyperbolic Representation Learning for Fast and Efficient Neural Question Answering](https://mlsanity.com/paper/1707.07847/) (2017)
- [Heterogeneous manifolds for curvature-aware graph embedding](https://mlsanity.com/paper/2202.01185/) (2022)
- [Latent Graph Inference using Product Manifolds](https://mlsanity.com/paper/2211.16199/) (2022)
- [Ultrahyperbolic Representation Learning](https://mlsanity.com/paper/2007.00211/) (2020)

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

- [Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries](https://mlsanity.com/paper/2310.15003/) (2023)
- [Neural Spacetimes for DAG Representation Learning](https://mlsanity.com/paper/2408.13885/) (2024)
- [AMES: A Differentiable Embedding Space Selection Framework for Latent Graph Inference](https://mlsanity.com/paper/2311.11891/) (2023)
- [Metric Learning for Clifford Group Equivariant Neural Networks](https://mlsanity.com/paper/2407.09926/) (2024)

## 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.