Hyperbolic Diffusion Embedding and Distance for Hierarchical Representation Learning

1. Introduction

• Unlike methods that require a known tree graph or tree distance, the proposed approach takes observational data without prior knowledge of its hierarchy.The paper frames this as recovering the underlying structure from the ground up.Source: §1 · pp. 1–2
• The method builds multi-scale diffusion operators, embeds each observation at each scale in hyperbolic space, and combines those embeddings in a product manifold.The resulting representation is called hyperbolic diffusion embedding (HDE); its associated hyperbolic diffusion distance (HDD) uses the product-space ℓ1 distance and hyperbolic Riemannian distance.Source: §1 · p. 2
• HDD is reported to improve standard hierarchical-representation quality measures and downstream classification accuracy, with shorter run times than most competing methods.The evaluation includes hierarchical graph benchmarks, single-cell RNA-sequencing data, and unsupervised hierarchical metric learning tasks.Source: §1 · p. 2
• The paper presents combining diffusion and hyperbolic geometries as a novel way to build multi-scale distances that capture data from fine to coarse scales.It reports that considering multiple scales plays a key role in recovering hierarchical structure.Source: §1 · p. 2

Diffusion Geometry

• Pairwise data affinities are normalized into a transition matrix, whose operator propagates mass between graph nodes.The affinities use a suitable distance and a tunable kernel scale parameter.Source: §2 · p. 2
• Applying the diffusion operator for multiple times gives each data point a collection of multi-scale densities and yields diffusion distances and embeddings.A density after t propagation steps is defined by applying the operator to the point’s indicator vector.Source: §2 · pp. 2–3
• Under the stated limiting conditions, the diffusion operator approximates the heat kernel of the underlying manifold.The passage identifies the heat kernel as H_t = exp(−t∆), with ∆ the Laplace–Beltrami operator.Source: §2 · p. 3

Poincaré Half-Space Model of Hyperbolic Space

• The paper uses the Poincaré half-space model of hyperbolic space with curvature −1.The supplied passage identifies it as an n-dimensional model.Source: §2 · p. 3

Product Manifolds and Distances

• A product manifold combines Riemannian manifolds, and the paper uses its ℓ1 distance because this choice enables recovery of the underlying hierarchical structure.The product manifold’s dimension is the sum of its factor-manifold dimensions.Source: §2 · p. 3

3. Problem Formulation

• In graph embedding, the input is a tree graph whose shortest-path distances define the hierarchical distances to be approximated by an embedding.The objective is to place nodes in a metric space with distances approximating the tree distances.Source: §3 · p. 3
• In hierarchical distance recovery, observations are treated as nodes of a hidden tree, while the tree and its hierarchical distances are inaccessible.The observations are typically embedded in a high-dimensional Euclidean space and assumed to have an underlying hierarchy.Source: §3 · p. 3
• The recovery task is to infer from the observations a distance that approximates the hidden hierarchical distance.The paper identifies this as its primary focus, in contrast to the graph-embedding setting.Source: §3 · p. 3

4. Hyperbolic Diffusion Distance

• The diffusion operator is built from a Gaussian-kernel graph on the observations and acts as its random-walk transition matrix.The method also applies when the diffusion operator approximates the heat kernel.Source: §4 · pp. 3–4
• Each point is embedded from its diffusion operator into the Poincaré half-space, with a 2^-2 term weighting the diffusion time to capture local intrinsic association across scales.The parameter α, where 0 < α < 1, scales diffusion propagation.Source: §4 · p. 4
• At dyadic diffusion times, each observation maps to a collection of hyperbolic points; fine scales give local views, while coarse scales yield tree-consistent exponential distance scaling.The embedding uses the Poincaré half-space model to represent multiple diffusion scales.Source: §4 · pp. 4–5
• The product embedding has dimension (n + 1)(K + 1), foregoing the usual dimensionality-reduction aim for the stated gain of recovering hierarchy.Each diffusion operator maps an n-dimensional density into H^(n+1), across K + 1 scales.Source: §4 · p. 5
• HDD is the ℓ1 distance on the product manifold of hyperbolic spaces, with the hyperbolic distance term attenuating large values.The inverse hyperbolic sine arises from the Riemannian distance at each scale.Source: §4 · p. 5

5. Theoretical Justification

• Diffusion operators reveal local connectivity at different neighborhood scales, and their multi-scale hyperbolic embedding endows those scales with a hierarchy.The paper presents this as the intuition behind recovery of the underlying hierarchical structure.Source: §5 · p. 5
• Theorem 1 states that HDD recovers the underlying hierarchical distance without the tree distance or explicit tree structure as input.The paper recommends α close to 1/2 so HDD approximates the hierarchical distance.Source: §5 · p. 5
• The metric-recovery theorem assumes point-wise approximation of the heat kernel and three strong regularity conditions.The passage says the heat kernel satisfies these conditions.Source: §5 · p. 5
• A product of hyperbolic spaces has a different metric from one hyperbolic space of combined dimension, and the paper says this specific HDD construction is essential for recovering hierarchy.The paper relates its derivation to prior diffusion-distance work while noting that the earlier approximation does not apply to hierarchical structures.Source: §5 · p. 6

6.1. Hierarchical Graph Embedding

• Across five graph benchmarks, HDD achieves the best MAP with small standard deviation, but its distortion exceeds TR, hMDS, and PT.The comparison uses the mean across the five graphs; whiskers show standard deviation.Source: Figure 2 · p. 6, §6.1 · p. 7
• Five graph benchmarks assess embeddings against shortest-path distances using MAP for local fidelity and average distortion for global similarity.The graph set includes trees, tree-like graphs, and a dense graph.Source: §6.1 · pp. 6–7

6.2. Single-Cell Gene Expression Data

• On Zeisel and CBMC, HDD has the highest MAP by a large margin and the second-best average distortion, close to the best result.Cell-type tree information is used only for evaluation and is hidden from the distance-recovery methods.Source: Figure 3 · p. 7, §6.2 · p. 8
• HDD outperforms all competing methods by a large margin in nearest-centroid classification accuracy on both scRNA-seq datasets.Classification accuracy is averaged over ten runs with an 80%/20% train/test split.Source: Figure 4 · p. 7, §6.2 · p. 8

6.3. Unsupervised Hierarchical Metric Learning

• Across Zoo, Iris, Glass, and Segmentation, HDD ranks first in classification accuracy on three datasets and second on the fourth.The datasets have no supplied ground-truth hierarchy; the methods use cosine distances without label information, followed by repeated 80%/20% classification.Source: Table 1 · p. 8, §6.3 · p. 8

7. Conclusion

• HDE and HDD accept graphs or observations with hidden hierarchy; their multi-scale hyperbolic embeddings have an ℓ1 distance theoretically equivalent to the input’s tree-like distance.The conclusion also reports advantages on graph and single-cell benchmarks and improved downstream classification.Source: §7 · pp. 8–9

A.1. Diffusion Geometry

• Diffusion geometry builds a transition process, defines distances through differences between transition distributions, and uses eigenvector-based diffusion maps to approximate those distances.The appendix also describes diffusion operators at multiple dyadic scales as diffusion wavelets.Source: §A.1 · p. 13

A.2. Hyperbolic Geometry

• The appendix studies the Poincaré half-space at curvature −1 and defines δ-hyperbolicity by a four-point distance inequality; the two-dimensional half-plane is (log 2)-hyperbolic.Source: §A.2 · p. 13

A.3. Graph Preliminaries

• For graphs, the shortest-path metric is the length of the shortest path, and a 0-hyperbolic metric is one equal to a tree’s shortest-path metric.Source: §A.3 · p. 13

B. Proof of Proposition 1

• For k1 ≤ k2, Proposition 1 gives scale-dependent bounds whose lower bound is tightly bounded by 2^{-(k2-k1)α}.Source: B. Proof of Proposition 1 · pp. 13–14

C. Theoretical Analysis of Hyperbolic Diffusion Distance - Proof of Theorem 1

• HDD uses a multi-scale metric based on the inverse hyperbolic sine of scaled Hellinger distance, forming an ℓ1 distance on a product of hyperbolic spaces.Source: C. Theoretical Analysis of Hyperbolic… · p. 14

C.1. HDD in Continuous Space

• In continuous space, the metric applies inverse hyperbolic sine to scaled Hellinger measures, and exponential scale decay allows approximation by the first K terms.Source: §C.1 · p. 15

C.2. Regularity Conditions

• The hierarchical-distance approximation relies on regularity conditions that bound the kernel and impose Hölder continuity.Source: §C.2 · p. 15

C.3. Hierarchical Metric

• The multi-scale metric is equivalent to a thresholded Snowflake distance of the hierarchical metric under the stated regularity conditions.Source: §C.3 · pp. 15–17

C.4. Heat Kernel on Trees

• For the heat kernel on trees, the proposed multi-scale metric is equivalent to dT^{2α} for sufficiently large K.Source: §C.4 · pp. 17, 19

D. Additional Details on the Experimental Study

• The experiments use an NVIDIA GTX 1080 Ti GPU and fixed random seed 1234.Source: D. Additional Details on the… · p. 19

D.1. Baselines

• Graph-embedding comparisons include tree representation, Poincaré embedding, hyperbolic MDS, SGD-based methods, hyperbolic hierarchical clustering, and Sarkar’s combinatorial construction.Source: §D.1 · p. 19

D.2. Datasets

• The study uses five hierarchical graph benchmarks, two scRNA-seq datasets, and four UCI datasets for downstream classification.Source: §D.2 · p. 19

D.3. Implementation Details

• For graph data, the diffusion operator is exp(−L); for high-dimensional data, the method uses ambient-space cosine distance, with large diffusion-kernel computations identified as the main computational burden.Source: §D.3 · p. 19

E.1. Toy Example

• In a five-level balanced binary-tree example, propagated densities become more local at larger scales, and HDD-based MDS recovers the tree graph.Source: §E.1 · p. 20, Figure 5 · p. 20

E.2. Hierarchical Graph Embedding

• HDD attains MAP 1.0 on the small balanced tree and phylogenetic tree, and outperforms optimization-based methods on tree-like and dense graphs, though its average distortions are often higher.Source: §E.2 · pp. 20–21, Table 2 · p. 21

E.3. Ablation Study

• HDD outperforms the product-manifold ℓ2 distance and single-scale embedding, supporting the contribution of ℓ1 aggregation across multiple scales.Source: §E.3 · pp. 21–22
• Larger maximum scale K improves HDD embedding quality, whereas increasing single-embedding scale k has the opposite effect.Source: §E.3 · p. 22
• Replacing hyperbolic distance with Euclidean distance does not capture the hierarchical structure.Source: §E.3 · p. 22, Table 4 · p. 22

• HDD achieves the best MAP and classification accuracy on both scRNA-seq datasets, and the second-best average distortion.Source: §E.4 · p. 23, Table 5 · p. 23
• HDD uses maximum scales K = 9 for Zeisel and K = 13 for CBMC, slightly above the graph experiment because these data are larger and higher-dimensional.Source: §E.4 · p. 23
• Optimization-based methods PE, PT, and HHC take much longer than HDD without improving embedding quality or downstream classification accuracy; HDD is slower than TR and has slightly larger distortion.HDD nevertheless has significant advantages over TR in MAP and classification accuracy.Source: §E.4 · p. 23, Table 6 · p. 23