Frederic Sala, Christopher De Sa, Albert Gu and Christopher Ré (2018), Proceedings of the 35th International Conference on Machine Learning (ICML 2018), PMLR 80:4460–4469 — ARXIV-1804.03329
Key takeaways
- Why trees fit. In the Poincaré disk, as two points at equal radius move toward the boundary, d_H(x, y) approaches d_H(x, 0) + d_H(0, y) at any fixed angle: the shortest path between siblings runs through the parent, as in a tree. Sarkar’s construction (Algorithm 1) uses this. Each node is reflected to the origin, its children are placed evenly on a hyperbolic circle of radius τ, maximally far from the parent, and the picture is reflected back. With τ = ((1 + ε)/ε)·2 log(deg_max/(π/2)) the worst-case distortion is at most 1 + ε, in two dimensions, for any tree. The paper contrasts this with Euclidean space, where trees cannot be embedded with arbitrarily low distortion in any dimension; that contrast is cited, not proved.
- What the fit costs. A point at hyperbolic distance d from the origin has 1 − ‖x‖ of order e^(−d), so it needs about d bits, against log d in Euclidean space. A sphere-covering argument makes this independent of the model: hyperbolic balls grow exponentially in volume. Sarkar’s embedding has largest distance O((ℓ/ε) log deg_max), so that many bits (§3.2). A root with deg_max chains of length m forces Ω((ℓ/ε) log deg_max) bits for any embedding into H² with distortion 1 + ε (Lemma D.1). The paper’s summary: an exponential advantage over Euclidean space for short, bushy hierarchies, and less of one for graphs with long paths. WordNet took 495 bits per coordinate at ε = 1 and 2,877 at ε = 0.1 (Table 7).
- Dimension buys precision for bushy trees only. In H^r, placing children at hypercube vertices chosen by a binary code with large minimum Hamming distance (a Hadamard code) gives O((1/ε)(ℓ/r) log deg_max) bits for r ≤ log deg_max + 1, and O(ℓ/ε) beyond (Proposition 3.1). Extra dimensions widen the angle between siblings, so they help with high degree and do little for depth. No matching lower bound is given for r > 2.
- Hierarchies by distance, not by direction. Weighting each edge below depth s by 2^s keeps every ancestor of a node nearer to it than any non-ancestor (Proposition D.2). Embedding the weighted tree therefore represents the transitive closure of a hierarchy, the full ancestor relation, by nearest-neighbour ranking.
- Exact hyperbolic MDS. In the hyperboloid model cosh d_H(x_i, x_j) = x_{0,i}x_{0,j} − x⃗_iᵀx⃗_j, so the matrix Y = cosh(D) is uuᵀ − XXᵀ. If the points are centred at a minimiser of Σ sinh² d_H(x_i, z), a new “pseudo-Euclidean mean”, then Xᵀu = 0 (Lemma 4.1), u is Y’s one positive eigenvector, and PCA on −Y returns X up to rotation (Algorithm 2). Both this mean and the Karcher mean lie in any geodesic submanifold containing the points (Lemma 4.2), so the recovered dimension is the true one. To second order, a perturbation ΔH of the distances moves the recovered configuration by at most (2n²/λ_min) sinh²(‖H‖∞)‖ΔH‖²∞ (Lemma F.1): nearly flat for small diameters, and exponentially sensitive for large ones.
- Dimensionality reduction is not PCA. Principal geodesic analysis in H² has stable local minima that are not global (Figure 3, four points). Lemma 4.3 gives a sufficient condition for local convexity at a geodesic, read as a recovery result for noise within that regime.
Standing in the record
Filed on 2026-10-09 at the owner’s request, in a batch of six works on hierarchy and hyperbolic geometry asked for right after the record opened QUESTION-025. That question asks whether attributes that imply or exclude each other in co-occurrence still give linear attribute directions, and a concept lattice that is not Boolean. It builds on THEORY-185 and LIT-863. The batch is Cagnetta et al.’s random hierarchy model, Krioukov et al. (2010) on the hyperbolic geometry of complex networks, this paper, Lin et al. (2023) on multiscale diffusion geometry, Zhang et al. (2023) on hyperbolic geometry in hippocampal representations, and Yang et al. (2023) on hyperbolic latent geometry that fails to give the intended hierarchy. The owner described this one as “mathematical reasons trees admit efficient hyperbolic representations”. It was read on its own merits (NOTE-679), and the reading produces THEORY-196. It cites Krioukov et al. (2010) among the networks known to be hyperbolic.
It does not answer QUESTION-025. The paper represents a hierarchy by distances, so that ancestors are nearest neighbours, and says nothing about linear attribute directions, co-occurrence statistics or half-space incidence. Its bearing is as a contrast. A tree is exactly the structure that independent binary attributes exclude (THEORY-185), and here a tree is represented with near-zero distortion in two curved dimensions, at a precision cost that grows with depth. So a hierarchy can have a faithful geometric representation that is not a set of linear directions. The NOTE says more.