PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperbolic Entailment Cones for Learning Hierarchical Embeddings

Octavian-Eugen Ganea, Gary Bécigneul, Thomas Hofmann

arXiv:1804.01882v3cs.LGstat.ML

TL;DR

Low-dimensional embeddings struggle to represent hierarchical and entailment relations, especially when Euclidean geometry treats them symmetrically. The paper introduces geodesically convex entailment cones, derives optimal closed forms in Euclidean and hyperbolic spaces, and uses them to learn DAG embeddings. Experiments report improved capacity and generalization over recent baselines, while the cone construction excludes a neighborhood around the Poincaré-ball origin.

  • Problem

    Euclidean symmetric models inadequately reflect hierarchical structure, while order-embedding regions have limited capacity and heavy intersections for wide hierarchies.

  • Method

    The paper uses geodesically convex entailment cones to induce partial orders and drive efficient hierarchical embedding learning for DAGs.

  • Results

    The method improves over recent baselines on hypernymy link prediction in representational capacity and generalization performance.

  • Takeaways & Limitations

    Geodesically convex entailment cones provide a theoretical and practical model for hierarchical embeddings in hyperbolic and Euclidean spaces.

  • Takeaways & Limitations

    The cone construction excludes an open ball around the Poincaré-ball origin because useful cones cannot be defined there.

Abstract

from arXiv · show

Learning graph representations via low-dimensional embeddings that preserve relevant network properties is an important class of problems in machine learning. We here present a novel method to embed directed acyclic graphs. Following prior work, we first advocate for using hyperbolic spaces which provably model tree-like structures better than Euclidean geometry. Second, we view hierarchical relations as partial orders defined using a family of nested geodesically convex cones. We prove that these entailment cones admit an optimal shape with a closed form expression both in the Euclidean and hyperbolic spaces, and they canonically define the embedding learning process. Experiments show significant improvements of our method over strong recent baselines both in terms of representational capacity and generalization.

1. Introduction

The paper targets hierarchical and entailment relations whose structure is poorly represented by symmetric Euclidean embeddings, proposing geodesically convex entailment cones in hyperbolic and Euclidean spaces. It derives their optimal forms, uses them to learn DAG embeddings, and reports improved capacity and generalization over recent baselines.

  • Motivation: Euclidean symmetric models inadequately reflect latent hierarchical structure, while order-embedding regions have limited capacity and heavy intersections.The latter restricts representation of wide hierarchies with high branching factors.
  • Motivation: Hyperbolic spaces provide greater capacity for tree-like structures because ball volume grows exponentially with radius rather than polynomially.This growth enables embedding weighted trees while almost preserving their metric.
  • Contributions: The method replaces order-embedding entailment regions with geodesically convex cones that induce partial orders on a broad class of Riemannian manifolds.These cones are designed to represent asymmetric entailment relations.
  • Contributions: The paper derives canonical closed-form optimal entailment cones in both Euclidean and hyperbolic geometry.The expressions satisfy four natural properties.
  • Contributions: An efficient cone-driven algorithm learns hierarchical embeddings of directed acyclic graphs.The learning process is driven by the proposed entailment cones.
  • Experiments: The method improves over recent baselines on hypernymy link prediction in both representational capacity and generalization performance.The comparison is against the methods of Nickel and Kiela and Vendrov et al.
  • Contributions: The paper also derives an analytic closed-form exponential map for the n-dimensional Poincaré ball, enabling full Riemannian optimization.This replaces the approximate optimization method used by Nickel and Kiela.

2. Mathematical preliminaries

The preliminaries introduce the differential-geometric and hyperbolic concepts used to define and optimize embeddings in the Poincaré ball. They motivate hyperbolic geometry for trees through its exponential volume growth and low-distortion representation capacity.

  • Differential geometry: A manifold is locally approximated by Euclidean space, while a tangent space provides the first-order vector-space approximation around a point.The preliminaries use these concepts to formulate geometry on curved spaces.
  • Differential geometry: A Riemannian metric assigns smoothly varying inner products to tangent spaces and induces global distances through shortest curve lengths.A smooth manifold equipped with such a metric is a Riemannian manifold.
  • Differential geometry: Geodesics generalize straight lines as shortest paths, and the exponential map sends tangent-space vectors to points reached along geodesics.In Euclidean space, the exponential map is exp_x(v) = x + v and supports gradient descent on manifold-valued parameters.
  • Hyperbolic geometry: The n-dimensional Poincaré ball is a conformal hyperbolic model whose metric tensor changes the Euclidean metric by a scalar field, preserving angles while distorting distances.The paper chooses this model because it offers closed-form geodesics and an exponential map.
  • Hyperbolic geometry: The paper derives unit-speed geodesics and a closed-form exponential map in the Poincaré ball, which is geodesically complete.It also establishes that every geodesic lies in a plane with the origin.
  • Trees and hyperbolic space: Hyperbolic spaces suit trees because exponential volume growth provides enough capacity for quasi-isometric embeddings, unlike Euclidean spaces.The paper notes that any tree can be embedded with arbitrarily low distortion into the two-dimensional Poincaré disk.

3. Entailment Cones in the Poincar´e Ball

The paper defines entailment cones in the Poincaré ball as geodesically convex regions that encode hierarchical partial orders through nesting and transitivity. It derives optimal closed-form cone apertures, restricts their domain near the origin, and provides a practical learning formulation.

  • Cone construction: Entailment cones generalize order-embedding regions by defining hierarchical partial orders with geodesically convex regions in the Poincaré ball.The cones are intended to improve on Euclidean order embeddings for hierarchical structures.
  • Cone construction: The construction uses the exponential map to transport a cone from the tangent space at x into a subset of the manifold.For hyperbolic space, the exponential map is globally usable because the injectivity radius is infinite.
  • Cone properties: The cones are designed to be axially symmetric, rotation invariant, continuous, and transitive as nested angular regions.Rotation invariance makes the aperture depend only on the Euclidean norm of the apex, while transitivity establishes the partial-order structure.
  • Optimal aperture: Transitivity constrains the aperture function through h(r) = r/(1 − r^2) sin(ψ(r)), whose optimal value is constant at K.Making h constant maximizes cone aperture subject to the transitivity constraints.
  • Optimal aperture: The optimal hyperbolic cones have a closed-form aperture and satisfy transitivity, but their domain must exclude a neighborhood of the origin.The construction restricts the aperture domain to [ϵ, 1) because a useful nonzero aperture cannot extend continuously to the origin.
  • Euclidean counterpart: The same strategy yields Euclidean entailment cones, with h(r) = r sin(ψ(r)) and ordinary Euclidean gradient steps for learning.The Euclidean derivation replaces hyperbolic cosine-law and geodesic machinery with their Euclidean counterparts.

4. Learning with entailment cones

The learning procedure represents entailment by nested cones and trains embeddings with an angular max-margin objective, using Riemannian optimization for hyperbolic parameters.

  • Entailment links are modeled by requiring the subconcept embedding v to lie inside the entailment cone Sψ(u) of u.
  • The model trains on positive and negative edges with a max-margin loss whose energy penalizes pairs according to v’s angular distance from Sψ(u).Positive pairs are encouraged toward zero energy, while negative pairs are required to exceed margin γ.
  • For hyperbolic embeddings, optimization uses Riemannian gradients in tangent spaces and moves points along corresponding geodesics rather than Euclidean subtraction.The Riemannian gradient is obtained by rescaling the Euclidean gradient by the inverse metric tensor.
  • A closed-form exponential map enables full Riemannian optimization in the Poincaré ball, although experiments use a faster retraction approximation without significant empirical loss.

5. Experiments

The experiments evaluate hierarchical link prediction on WordNet under varying training coverage, comparing cone models with order, Poincaré, and Euclidean baselines. Hyperbolic cones perform best once training includes some non-basic transitive edges, with gains increasing as coverage grows.

  • Evaluation setup: The evaluation predicts unseen edges in the WordNet noun hierarchy using the full transitive closure of a directed acyclic graph.
  • Evaluation setup: Negative evaluation pairs are generated by corrupting either endpoint, producing ten times as many negative pairs as positive pairs for precision, recall, and F1 measurement.
  • Dataset splitting: Training coverage is varied across 0%, 10%, 25%, and 50% of randomly selected non-basic edges, each combined with the basic edges.
  • Training details: Initialization is important for most methods, with the best hyperbolic-cone results obtained from Poincaré embeddings pretrained for 100 epochs.Models use 10 negative edges per positive edge during training, and cone models use margin γ = 0.01.
  • Results: In 5- and 10-dimensional settings, hyperbolic cones outperform all baselines except Order Embeddings at 0% coverage, sometimes improving F1 by more than 8%.Hyperbolic cones also show the largest growth when transitive-closure edges are added during training.

6. Conclusion

The paper concludes that geodesically convex entailment cones provide theoretical and practical benefits for hierarchical graph embeddings. Performance varies with taxonomy observability, and the proposed method benefits most from additional training data.

  • Geodesically convex entailment cones form the paper’s proposed model for embedding hierarchical structures and entailment relations.
  • Strong embedding methods can vary substantially with the percentage of the taxonomy observed during training.
  • The proposed method benefits most from increasing the size of the training data.
  • Future work could examine whether entailment cones can embed more complex data such as sentences or images.

B. Proof of Theorem 1

The proof derives Poincaré-ball geodesics by mapping them isometrically to the hyperboloid model, applying the known hyperboloid expression, and mapping back.

  • An isometry ψ maps geodesics from the Poincaré ball D^n to geodesics in the hyperboloid model H^n.
  • The hyperboloid geodesic is expressed as φ(t) = x′ cosh(t) + v′ sinh(t) for suitable point and tangent-vector terms.
  • Applying ψ−1 to the hyperboloid geodesic yields the closed-form Poincaré-ball geodesic expression.
  • The derived formula is checked against the required initial-point, initial-velocity, and unit-speed conditions.

C. Proof of Corollary 1.1

The corollary is derived by combining the preceding equations and notations, although the supplied passage fragments do not state the resulting claim.

  • The supplied proof excerpt does not include the explicit corollary statement or intermediate derivation.
  • Using the notations from the preceding development, the proof derives the corollary from Eq. 3 and Eq. 6.

D. Proof of Corollary 1.2

The proof considers a geodesic and uses a planar reduction: the plane spanned by x and v contains every point on that geodesic.

  • The plane spanned by x and v contains all points of the geodesic γx,v(t).This follows from Theorem 1 in the supplied proof excerpt.
  • The planar containment is established as an intermediate fact in the proof of the corollary.

E. Proof of Lemma 2

The proof of Lemma 2 uses transitivity, continuity, coplanarity, and hyperbolic angle properties to establish geometric constraints on entailment-cone borders.

  • The proof assumes a contradiction involving ψ(∥x∥) > π and invokes transitivity to constrain the cone-angle function.
  • Moving x′ continuously along the cone border toward x yields a contradiction from the continuity of ψ(∥·∥).
  • For x′ on the cone border, points y and z are selected along geodesic and spoke constructions so the relevant hyperbolic angles are well-defined.
  • The points O, x, x′, y, and z are coplanar, and the Poincaré-ball metric is conformal with the Euclidean metric in that plane.
  • The remaining argument assumes an angle inequality and constructs a point t in the plane P to continue the contradiction.

F. Proof of Theorem 3

The theorem proof establishes a monotonicity-related inequality by combining transitivity, continuity of geodesic norms, hyperbolic trigonometry, and algebraic reformulations.

  • Lemma 7: Lemma 7 states that transitivity implies sin(ψ(∥x′∥)) sinh(∥x′∥D) ≤ sin(ψ(∥x∥)) sinh(∥x∥D).
  • Lemma 7: The proof reuses the geometric configuration from Lemma 2 and introduces a boundary point b where a spoke intersects ∂Dn.
  • Lemma 7: Angles at x′ are represented in two ways, and the hyperbolic law of sines is applied to triangle Oxx′.
  • Lemma 7: Combining Eqs. 48–52 and monotonicity of sin on [0, π/2] yields the helper lemma’s conclusion.
  • Theorem 3: For arbitrary radii r < r′, the proof reduces the required result to an intermediate inequality and applies Lemma 7.
  • Theorem 3: The resulting inequality is used to prove that the function h is non-increasing.
  • Theorem 3: A cone-border geodesic reaches ∂Dn, and continuity of its norm ensures it attains every intermediate radius r′ ∈ (r, 1).
  • Theorem 3: An axial-symmetry angle inequality is converted using the hyperbolic cosine law and then algebraically reformulated as Eq. 28.
Loading 1804.01882v3…