Interactive demo · Probabilistic Machine Learning · Chapter 23

Trees in the Poincaré disk and in the plane

A complete tree with branching \(b\) is built outwards from the root: every child is placed at distance \(\tau\) from its parent, in directions equally spaced around the parent (leaving out the direction back to the parent). On the left the geometry is that of the Poincaré disk, with the Poincaré distance (below) and geodesics drawn as circular arcs; in the middle the same recipe is carried out in the Euclidean plane.

\[d(\mathbf x,\mathbf y)=\operatorname{arcosh}\Big(1+\frac{2\|\mathbf x-\mathbf y\|^2}{(1-\|\mathbf x\|^2)(1-\|\mathbf y\|^2)}\Big).\]

If the embedding were perfect, the distance between two nodes would be \(\tau\) times the number of edges between them. The bars on the right show the average ratio \(d_{\rm embedding}/(\tau\,d_{\rm tree})\) for each tree distance (the ideal value is 1), and the readout the mean relative distortion over all node pairs.

Branching b

Depth

Edge length τ

Try these

The depth is capped so that the tree has at most 400 nodes (depth 7 for b = 2, 5 for b = 3, 4 for b = 4). Node colour is the depth. In the disk, the points near the rim are far apart in hyperbolic distance although they look close: the disk shows a space whose circumference grows like \(e^{r}\), the same rate at which the number of nodes at depth \(r\) grows.

In the lecture notes