  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>2^d$ leaves into a $d$-dimensional Euclidean space,
which we show at least $\Omega(L^{1/d})$; independently of the depth, width,
and (possibly discontinuous) activation function defining the MLP.

Machine Learning;Discrete Mathematics;Numerical Analysis;Neural and Evolutionary Computing;Metric Geometry;Numerical Analysis