PaperlayerView exact revision on arXiv

Source-linked AI summary

Representation Tradeoffs for Hyperbolic Embeddings

Christopher De Sa, Albert Gu, Christopher Ré, Frederic Sala

arXiv:1804.03329v2cs.LGstat.ML

TL;DR

Hierarchical data can be embedded in hyperbolic space with high fidelity using few dimensions, but quality depends on graph structure, precision, and scale. The paper develops a combinatorial construction for trees and h-MDS for general metrics, with strong WordNet performance and recovery methods for noisy or incomplete data.

  • Problem

    Hyperbolic embedding optimization is challenging, and the quality, dimensionality, precision, and recovery tradeoffs require characterization across tree-like and general metric data.

  • Method

    The paper combines an optimization-free tree-to-hyperbolic construction with h-MDS, perturbation and recovery analysis, and PyTorch SGD methods for noisy or incomplete information.

  • Results

    0.989 mean average precision is achieved on WordNet with two dimensions, versus 0.87 for Nickel and Kiela’s construction with 200 dimensions; h-MDS obtains low distortion on graphs far from tree-like.

  • Takeaways & Limitations

    Hyperbolic embeddings can represent hierarchies accurately with few dimensions, while graph structure and precision determine the dimensionality required.

  • Takeaways & Limitations

    Hyperbolic optimization is nonconvex with stable local minima, making global optimization difficult; some formulations also require guarding against NaNs.

Abstract

from arXiv · show

Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures like synonym or type hierarchies. Given a tree, we give a combinatorial construction that embeds the tree in hyperbolic space with arbitrarily low distortion without using optimization. On WordNet, our combinatorial embedding obtains a mean-average-precision of 0.989 with only two dimensions, while Nickel et al.'s recent construction obtains 0.87 using 200 dimensions. We provide upper and lower bounds that allow us to characterize the precision-dimensionality tradeoff inherent in any hyperbolic embedding. To embed general metric spaces, we propose a hyperbolic generalization of multidimensional scaling (h-MDS). We show how to perform exact recovery of hyperbolic points from distances, provide a perturbation analysis, and give a recovery result that allows us to reduce dimensionality. The h-MDS approach offers consistently low distortion even with few dimensions across several datasets. Finally, we extract lessons from the algorithms and theory above to design a PyTorch-based implementation that can handle incomplete information and is scalable.

1 Introduction

The paper develops optimization-free and scalable methods for hyperbolic embeddings, analyzing their quality, dimensionality, precision, and recovery properties. Its combinatorial construction performs strongly on WordNet, while h-MDS addresses general metrics and noisy or incomplete data.

  • Motivation: Hyperbolic embeddings capture hierarchical structure, but their underlying optimization problem is challenging and involves subtle tradeoffs.The paper studies these tradeoffs across graph structure, dimensionality, precision, and optimization.
  • Combinatorial construction: The combinatorial approach embeds a tree or nearly tree-like graph into a weighted tree and then into the hyperbolic disk.It avoids surrogate-loss minimization with gradient descent, runs in nearly linear time, and has formal quality guarantees.
  • Tradeoffs: 500 bits of precision are required for the WordNet combinatorial embedding, reducible to 32 bits by increasing dimensionality from two to 10.For fixed precision, required dimension scales linearly with longest-path length and logarithmically with maximum tree degree.
  • Hyperbolic MDS: h-MDS reduces hyperbolic multidimensional scaling to a standard eigenvalue problem using a non-standard centering operation and scalable power methods.The approach includes perturbation analysis and can recover lower-dimensional submanifolds from distance data.
  • Noisy and incomplete data: The PyTorch implementation supports incomplete distance information, while SGD initialized with h-MDS can recover data submanifolds under some full-dimensional noise.The implementation minimizes a loss derived from the PGA loss.

2 Background

The background explains why hyperbolic geometry is suited to trees and how embedding fidelity is measured. It introduces the Poincaré models, tree-like distance behavior, local and global metrics, and methods for incomplete distances.

  • Hyperbolic spaces: The Poincaré disk is a two-dimensional hyperbolic model, and the Poincaré ball generalizes it to higher dimensions.The models map conformally to Euclidean space, preserving angles but not distances.
  • Tree-like geometry: As points approach the disk boundary, their hyperbolic distance approaches the sum of their distances through the origin.This makes the shortest path resemble a tree path through a parent, even for arbitrarily small angles.
  • Lines and geodesics: Hyperbolic geodesics are orthogonal-circle segments or disk diameters, and geodesic reflections correspond to circle inversions in the Euclidean model.These geometric facts support the paper’s algorithms and proofs.
  • Fidelity measures: MAP measures local neighbor-ranking quality, whereas distortion measures how the underlying distances are preserved globally.Worst-case distortion is the ratio of maximal expansion to minimal contraction, and its best value is 1.
  • Incomplete information: When distances are incomplete, missing values can be recovered using the triangle inequality or matrix completion of scaled Euclidean distances.An embedding can then be computed with the approaches described in the paper.

3 Combinatorial Constructions

The paper develops a fast, optimization-free combinatorial pipeline that embeds graphs into weighted trees and then into hyperbolic balls, while analyzing distortion, precision, dimensionality, and graph-specific limits.

  • Combinatorial construction: The combinatorial construction first embeds a graph into a tree, then embeds that tree into the Poincaré ball without minimizing a loss function.For trees, the full construction runs in linear time and uses Sarkar’s hyperbolic tree embedding as its second stage.
  • Combinatorial construction: Sarkar’s construction places children through reflections and equally spaced points, preserving each parent–child hyperbolic distance exactly.The children are placed on a circle with hyperbolic radius τ, maximally separated from the reflected parent, and then reflected back.
  • Quality and precision: 1 + ε worst-case distortion is obtained by choosing τ = 1 + ε, but the required precision grows logarithmically with degree and linearly with maximum path length.Hyperbolic representations need roughly d bits to express distance d, unlike the roughly log d bits needed in Euclidean space.
  • Higher-dimensional construction: Increasing dimension helps bushy trees by allowing more widely separated children, but has limited effect on tall trees with small maximum degree.The r-dimensional construction replaces circle placement with hypersphere placement and uses spherical coding; its bounds are O((1/ε)ℓ log degmax) bits for r ≤ log degmax + 1 and O((1/ε)ℓ) bits for larger r.
  • Limits and extensions: There is a fundamental precision–quality tension: hyperbolic embeddings have an exponential space advantage for short, bushy hierarchies but less advantage for graphs containing long paths.Steiner nodes can improve graph embeddings, while selecting the scaling factor τ is critical for quality and is later learned automatically in PyTorch.

4 Hyperbolic Multidimensional Scaling

Hyperbolic multidimensional scaling recovers hyperbolic embeddings from pairwise distances by centering points at a pseudo-Euclidean mean and reducing recovery to matrix factorization. The method supports exact recovery, preserves lower-dimensional geodesic structure, and provides a basis for dimensionality reduction and noise recovery.

  • Problem: h-MDS asks whether hyperbolic points can be recovered from their pairwise distances, extending the Euclidean MDS problem.The observed distance matrix is used to recover the original points or another configuration with identical pairwise distances.
  • Centering: The pseudo-Euclidean mean enables matrix-factorization recovery even though hyperbolic space lacks Euclidean linear subspaces.After recovery, points can be recentered around a more canonical mean without changing the underlying distance representation.
  • Algorithm: Algorithm 2 computes a scaled distance matrix, applies PCA, converts the result to the Poincaré model, and optionally recenters the points.The procedure takes a distance matrix and target rank as inputs, then returns the recovered embedding.
  • Recovery: h-MDS transforms hyperbolic distances into a matrix whose eigendecomposition recovers the embedding up to rotation.The matrix has one positive-eigenvalue direction for the time-like coordinate and negative eigenvalues for the remaining coordinates; PCA on −Y recovers X.
  • Guarantees: Centering with the pseudo-Euclidean mean preserves geodesic submanifolds and therefore preserves the embedding dimension when an exact lower-dimensional representation exists.Both the Karcher and pseudo-Euclidean means lie in the same dimension-k geodesic submanifold.
  • Dimensionality reduction: PGA defines lower-dimensional hyperbolic representations, while noise recovery is guaranteed when initialization and noise satisfy the stated conditions.Unlike Euclidean PCA, hyperbolic optimization can have attractive local minima, but a suitable initialization can guarantee convergence to the correct embedding.

5 Experiments

The experiments compare combinatorial embeddings, h-MDS, PCA, FB, and PyTorch SGD across tree-like and general datasets, including incomplete-distance settings. Results show strong distortion and MAP performance, especially for combinatorial embeddings on tree-like graphs and h-MDS for distortion.

  • Experimental setup: The evaluation covers trees, tree-like hierarchies, and non-tree-like graphs, using combinatorial embeddings, h-MDS, PCA, FB, and PyTorch SGD.The approaches are compared across datasets and incomplete-information settings.
  • Quality: 0.039 distortion was achieved by h-MDS on the phylogenetic tree dataset, and h-MDS consistently had the lowest distortion among h-MDS, PCA, and FB.The combinatorial construction also had exceedingly low distortion on tree and tree-like graphs.
  • Quality: 0.989 MAP was obtained on WordNet by the combinatorial construction, compared with 0.870 for FB at 200 dimensions.On trees and tree-like graphs, combinatorial MAP was close to 1; its MAP decreased as graphs became less tree-like.
  • SGD-Based Algorithm: Learned scale and exponential distance weighting improved MAP in the PyTorch implementation, particularly at lower rank.The weighting was added to penalize long paths and improve local reconstruction.
  • Incomplete Information: 4% sampling of the phylogenetic tree’s graph yielded MAP 0.74 and distortion below 0.6 after distance completion and embedding.The experiment samples the distance matrix and evaluates the recovered solution.

6 Conclusion and Future Work

The paper presents hyperbolic embeddings as high-fidelity representations requiring few dimensions and develops scalable, high-quality algorithms. It identifies downstream integration and future follow-on work as remaining directions.

  • Hyperbolic embeddings represent hierarchical information with high fidelity using few dimensions.
  • The paper describes scalable, high-quality algorithms and plans to release PyTorch code, a high-precision solver, and other routines on Github.
  • Future work will examine how to incorporate hyperbolic embeddings most effectively into downstream tasks and applications.

B Related Work

Related work covers hyperbolic embeddings and routing, hyperbolic multidimensional scaling, network hyperbolicity, matrix completion, and manifold principal-component methods. The paper positions its analyses and implementations against optimization-based and heuristic alternatives.

  • Hyperbolic embeddings and routing: Earlier work applied hyperbolic spaces to geographic routing and dynamic-network routing, while later work used them for embeddings in machine learning and link prediction.
  • Hyperbolic multidimensional scaling: Prior h-MDS work often used descent methods, whereas this paper emphasizes exact centering, noise robustness, and optimization guarantees.
  • Network hyperbolicity: Network-hyperbolicity research studies hyperbolic graphs, small-world and random graphs, and how real networks can be approximated by trees.
  • Incomplete information: Matrix completion provides a standard route for recovering missing distance information, with prior work giving entry-count bounds and convex programs for fixed-rank matrices.
  • Manifold dimensionality reduction: PGA generalizes PCA to manifold settings, while related GPCA work uses the paper’s loss function.
  • Implementation details: The implementation addresses hyperbolic optimization through a learned scale, differentiable squared-distance loss, curvature correction, projection, and gradient clipping.

D Combinatorial Construction Proofs

The proofs establish precision limits and distortion guarantees for combinatorial hyperbolic embeddings of trees and weighted tree representations. Higher dimension helps pack children in bushy trees, while weighted constructions preserve ancestor proximity in transitive closures.

  • Precision bounds: A bit-precision covering argument shows hyperbolic representations need O(d) bits for distances up to d at constant tolerance, independent of the hyperbolic model.Hyperbolic ball volume grows exponentially with radius, unlike Euclidean volume.
  • Precision bounds: The explicit lower-bound graph is a root with degmax chains of length m, totaling 1 + m(degmax) nodes and longest path ℓ = 2m.The construction exposes precision requirements for arbitrary embeddings into H2.
  • Combinatorial construction: Equalizing origin-to-child distances and scaling embedded points yields the stated distortion guarantee in the two-phase construction.The proof bounds maximum expansion and contraction using the closest pair of child directions.
  • Combinatorial construction: The generalized Hr combinatorial construction achieves worst-case distortion at most 1 + ε with dimension-dependent precision bounds.For r ≤ log degmax + 1, the node-component requirement is O((1/ε)ℓ log degmax) bits; for larger r it is O((1/ε)ℓ) bits.
  • Weighted trees: For transitive-closure hierarchies, depth-based edge weights ensure every node is closer to each ancestor than to any non-ancestor.Embedding the weighted tree therefore preserves ancestor ordering and retains properties such as perfect MAP on trees and linear-time construction.

E Proof of h-MDS Results

The h-MDS proofs connect pseudo-Euclidean centering with hyperbolic geodesic submanifolds. Projection arguments show that relevant means remain within the submanifold, enabling equivalent centered representations.

  • Geodesic submanifolds: In the hyperboloid model, geodesic submanifolds are intersections of linear subspaces with the hyperboloid.This permits a submanifold to be centered at any point it contains.
  • Projection argument: Projection onto a geodesic submanifold strictly decreases distances from an external point to every point in the submanifold.The proof uses the hyperbolic Pythagorean theorem and the resulting right angle.
  • Means: A Karcher mean and a pseudo-Euclidean mean of points lying in a geodesic submanifold both lie in that submanifold.Projecting an external mean lowers the corresponding variance, so a minimizing mean exists inside the submanifold.
  • Centering equivalence: Pairwise distances embeddable in a centered dimension-r geodesic submanifold under one mean are also embeddable under the other mean.Reflection is isometric, so recentering preserves the distance embedding.

F.1 Handling Perturbations

The perturbation analysis transforms hyperbolic distances into a scaled Euclidean problem, applies Euclidean recovery bounds, and then controls projection back to the Poincaré model. The resulting sensitivity depends on distance scale and conditioning.

  • Sensitivity: When points are close, perturbations are less sensitive because hyperbolic space is approximately flat; distant points are sensitive in absolute terms.The stated intuition follows from the behavior of sinh^2(z) near the origin.
  • Error measure: The analysis measures configuration error after optimizing over orthogonal transformations, because rotations and reflections preserve the recovered distance matrix.The Euclidean gap is DE(X, Y) = inf{D(X, PY) : P^T P = I}.
  • Problem setup: Perturbed hyperbolic distances H + ∆(H) are compared through the gap between embeddings recovered from H and from the perturbed matrix.The perturbation matrix is symmetric with zero diagonal.
  • Perturbation analysis: h-MDS perturbation analysis proceeds by removing the acosh transformation, removing scale factors, applying Sibson’s Euclidean bound, and bounding Poincaré projection error.This decomposes hyperbolic recovery error into tractable Euclidean and projection steps.
  • Projection: Poincaré projection does not increase the optimized Euclidean configuration gap.The projected gap satisfies DE(Z, Ẑ) ≤ DE(X, X̂).
  • Hyperbolic error: The hyperbolic gap provides a more direct interpretation of perturbation error when recovering hyperbolic distances.The Euclidean column-wise gap can therefore be related to a distance-based hyperbolic error.

G Proof of Lemma 4.3

The proof establishes a sufficient condition for local convexity of the hyperbolic PGA objective. It analyzes component functions along geodesics and then uses convexity of their sum.

  • Geodesic reduction: The proof reduces optimization over geodesics through the origin to optimization over unit vectors on the hypersphere.A geodesic is parameterized by a unit vector u, and hypersphere geodesics are parameterized by an angle θ.
  • Component analysis: Each component function is rewritten in terms of the residual to the point and its norm before analyzing curvature.The resulting second-derivative bound depends only on those geometric quantities.
  • Curvature bound: The worst-case curvature analysis uses the largest allowable geodesic angle determined by the closest point on the geodesic.Concavity and monotonicity identify the angle maximizing tan^2(θ) for the lower bound.
  • Local convexity: A sufficient condition involving the residual R(z) ensures each component is locally convex at z.The proof combines R(z) ≤ 1 with the derived scalar inequality.
  • Local convexity: The full objective is locally convex because it is a sum of component functions that are locally convex under the stated condition.This is the final step from component-wise curvature to the lemma.

H Experimental Results

This section reports additional experimental results for the combinatorial construction and h-MDS, including construction parameters, rank variation, and precision effects. Results also include an additional less tree-like search-engine query-response graph.

  • The experiments include a search-engine query-response graph for “California,” described as less tree-like than the other graph datasets.
  • Combinatorial Construction: Parameters: The combinatorial-construction experiments report maximum degree, scaling factor ν, embedding time, and storage requirements for ε = 0.1 and ε = 1.0.These quantities are presented as parameters and results for each graph.
  • Hyperparameter: Effect of Rank: On the Phylogenetic tree dataset, h-MDS, PCA, and FB were evaluated at dimensions 2, 5, 10, 50, 100, and 200 using distortion and MAP metrics.Table 8 reports variation with rank using MAP, 2-MAP, and davg.
  • Hyperparameter: Effect of Rank: All evaluated techniques improved with better rank, while the optimization-based approach typically produced the best MAP by optimizing fine details accurately.
  • Precision Experiment: The precision experiment evaluates h-MDS on a balanced tree at fixed dimension 10, with Table 9 covering a 3-ary tree at rank 10.
Loading 1804.03329v2…