Capacity Bounds for Hyperbolic Neural Network Representations of Latent Tree Structures
This provides foundational theoretical guarantees for using hyperbolic neural networks to represent tree-structured data, which is incremental but with rigorous bounds.
The paper proves that hyperbolic neural networks (HNNs) can embed any finite weighted tree into hyperbolic space with a distortion bound, and shows that the network complexity for this is independent of distortion, while Euclidean MLPs require at least Ω(L^{1/d}) distortion for trees with many leaves.
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 $κ<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>2^d$ leaves into a $d$-dimensional Euclidean space, which we show at least $Ω(L^{1/d})$; independently of the depth, width, and (possibly discontinuous) activation function defining the MLP.