nucleation

LIT-870: Hyperbolic Diffusion Embedding and Distance for Hierarchical Representation Learning

3 min read

Properties4
StatusActive — read 2026-10-09 (NOTE-675); worth reading as a construction that recovers a latent tree from unlabelled data by distances alone, with a proof of what is recovered. Each point is represented by its diffusion densities P^(2^−k) e_i at dyadic times, each density is placed in a Poincaré half-space at a height set by its scale, and the hyperbolic diffusion distance is the ℓ1 sum over scales of the hyperbolic distances, 2 sinh⁻¹(2^(1−kα)‖φ_i^k − φ_j^k‖) with φ the square roots of the densities, a scale-weighted Hellinger distance. Theorem 1 (Appendix C, after Leeb and Coifman) says that for the heat kernel on a tree this is equivalent up to constants to min{1, d_T^(2α)}, 0 < α < 1/2: a thresholded snowflake of the tree metric, not the tree metric, and saturated beyond a fixed radius; the main text states it without the threshold. The tree heat-kernel bounds are stated, not proved, and one step of the Hölder bound (Proposition C.5) holds only for tree distances of at least 1, so the admissible range of α is not secured. Empirically it gives the best mean average precision on five graph benchmarks and two single-cell datasets and worse average distortion than hyperbolic MDS or Sarkar's construction: local neighbourhoods are kept, global distances are not. Nothing in it concerns attributes or linear directions.
Tagsrepresentation-learning, mathematics, anthology-candidate
Cited as “paper” byNOTE-675 — Hyperbolic Diffusion Embedding and Distance
Cited as “source” byTHEORY-478 — If the diffusion densities' Hellinger distances obey a Hölder bound with exponent θ in d_T / t^(1/β) and are bounded below once d_T exceeds a multiple of t^(1/β), then for 0 < α < θ/β summing scale-weighted hyperbolic distances between diffusion densities over dyadic times gives a distance two-sided equivalent, up to constants, to min{1, d_T^(αβ)} for pairs above the finest scale: it keeps the tree's neighbourhoods and not its global distances; whether a tree's heat kernel, or sampled data, meets the bounds, and with which θ, is not shown

Graph View

Ya-Wei Eileen Lin, Ronald R. Coifman, Gal Mishne and Ronen Talmon (2023), Proceedings of the 40th International Conference on Machine Learning, PMLR 202:21003–21025 — ARXIV-2305.18962

Key takeaways

  • The construction. From a kernel W = exp(−d²/ε), doubly normalised into a Markov matrix P (for a given graph, P = exp(−L)), each point i gets densities φ_i^k = √(P^(2^−k) e_i) at times 2^−k, k = 0, …, K. Each is a point [φ_i^k, 2^(kα−2)] of the half-space H^(n+1), so fine scales sit high and coarse scales low. The hyperbolic diffusion embedding is the tuple of K + 1 such points; the hyperbolic diffusion distance (HDD) is the ℓ1 sum of their hyperbolic distances, which reduces to Σ_k 2 sinh⁻¹(2^(1−kα) ‖φ_i^k − φ_j^k‖₂). No training and no tree is given; the hierarchy is read off the distance.
  • What is proved. Proposition 1: the single-scale distances shrink geometrically with k, within constants, as 2^−(k₂−k₁)α. Theorem 1, in the form the appendix proves (Proposition C.4 with β = 2): if the kernel obeys Gaussian-type upper and lower bounds and a Hölder bound in the tree distance d_T, the multiscale distance is equivalent up to constants to min{1, d_T^(2α)} for 0 < α < 1/2. The heat kernel on a tree is asserted to meet the bounds (Lemmas C.4–C.6, stated with citations, not proved). The argument adapts Leeb and Coifman’s multiscale diffusion distance, which recovers geodesic distance on non-negatively curved manifolds, to trees.
  • What the theorem does not give. A snowflake d_T^(2α) with 2α < 1 preserves the order of distances but not the tree metric itself, and the threshold means points farther apart than a fixed radius are only known to be far. The main text drops the threshold and says the result is “approximately 0-hyperbolic” as α → 1/2, which is not proved.
  • What the experiments show. On Sala et al.’s five graph benchmarks HDD has the best mean average precision (1.0 on the balanced and phylogenetic trees) but higher average distortion than tree representation, hyperbolic MDS, the SGD method and Sarkar’s construction; the authors call it a local-over-global trade-off. On two scRNA-seq datasets, with the cell-type tree held out for evaluation, it has the best MAP and nearest-centroid accuracy. Ablations: the ℓ2 product distance, any single scale, and a Euclidean distance on the same multiscale embedding all do worse, the last by a wide margin.

Standing in the record

Filed at the owner’s request on 2026-10-09, in a batch of six works on hierarchy and hyperbolic geometry asked for after the record opened QUESTION-025. Read the same day (NOTE-675).

It bears on that question only at a distance. QUESTION-025 asks whether attributes that imply each other keep linear directions in a co-occurrence embedding (THEORY-185, LIT-863). This paper has no attributes and no directions. It represents a hierarchy as a metric, recovered across scales of diffusion, and it finds a Euclidean distance on the same multiscale features far worse at it. What it supplies is a second, metric route to a latent hierarchy against which a linear-direction account could be compared, not an answer. Its object is also a tree, which is narrower than the concept lattice of CLAIM-119.

Backlinks