Can hyperbolic graph embeddings use one metric and optimize with another?

Large radii freeze angular motion in hyperbolic optimization

Hierarchical graphs embed in hyperbolic space with lower distortion than in Euclidean space because of its negative curvature, but gradient-based learning is hampered at large radii, exactly where hierarchical graphs place most nodes. The Poincare ball and the Lorentz hyperboloid both lose precision through catastrophic cancellations: the Lorentz model recovers distances from a Minkowski product of two nearly equal numbers of order e^(2r), and the cancellation already corrupts the distance of two nodes at distance 1 by 1% at r about 16, becoming zero at r about 19. The ball, whose points approach its boundary as 1 - tanh(r/2) about 2e^(-r), suffers the same kind of cancellation.

Polar coordinates avoid this failure and stay accurate up to r about 350, but they introduce a different problem. In polar coordinates a point is stored as a hyperbolic radius and a unit direction, x = (r, v), and the hyperbolic metric scales the angular component by sinh^2(r). Under natural gradient descent the angular step becomes delta theta = -eta * d_theta f / sinh^2(r), so the arc moved is delta s = eta * |d_theta f| / sinh(r), which decays exponentially with radius. At the radii a hierarchical embedding may reach, around 20 or 30, the angular coordinates are frozen no matter how large the angular derivative is.

The step metric is a choice, not a constraint

The central observation is that the metric used to take gradient steps need not be the metric in which the embeddings live. The loss is always evaluated with the hyperbolic distance at curvature -1, so the optimizer's metric acts only as a preconditioner: it changes the path the optimizer follows, not the problem being solved. Existing implementations silently fix this choice. Riemannian methods step with the exact hyperbolic metric, while the Euclidean tangent parametrization stores each embedding as a single unconstrained vector z = rv and applies ordinary Euclidean gradient descent, which implicitly scales the angular component by the radius itself.

Replacing sinh^2(r) by an arbitrary positive warp w(r)^2 gives a family of preconditioners, and both existing choices are endpoints of a one-parameter family w_c(r) = sinh(sqrt(c) r) / sqrt(c). Here c = 1 recovers the exact hyperbolic metric and c approaching 0 gives the flat warp w_0(r) = r. Each w_c is the warp of a constant-curvature -c metric, but it acts only as a preconditioner: the loss is untouched, the distance between embeddings stays at curvature -1 for every c, and the warp enters only when moving coordinates. This differs from mixed-curvature approaches, which change the embedding space itself.

Why both endpoints fail across a wide radial span

The paper identifies the spread of radii as the necessary condition for the preconditioner to matter. With the flat preconditioner the freeze is removed, but if embeddings span from a small r_min to a large r_max, the ratio between the movement of outer and inner nodes scales like e^(r_max - r_min) unless the angular derivative decreases exponentially with r, which for the stress objective is the opposite. A single learning rate therefore cannot usefully move all nodes under c approaching 0: it either moves only the outer nodes or diverges.

The exact hyperbolic metric fails in the opposite way. It freezes angular motion, so correcting a warm start whose layout is globally wrong requires rotations of relatively large angles at large radius, which only a small c supplies. Intermediate values of c reduce the difference in movement between outer and inner nodes, with the ratio becoming roughly e^((1 - sqrt(c))(r_max - r_min)). The extreme case c = 1, which apparently cancels the radial span, would bring back the freeze.

A two-stage schedule separates coarse and fine work

The authors run two stages: a coarse phase at c approaching 0, a handover of the coordinates, and a fine phase at an interior c with a fresh optimizer state and its own learning rate. A preconditioner leaves the critical points of the loss untouched, since G_c^(-1) grad f vanishes exactly where grad f does, but the loss is not convex and the path decides which critical point is reached. The coarse phase is therefore not merely a faster start on one descent: it can hand over a configuration from which the fine phase settles somewhere the fine phase alone would never have found.

The schedule matters as much as the curvature. Run from the initialization alone, an intermediate curvature is often worse than the flat metric. Its largest advantage appears once a flat first stage has done the large-scale rearrangement, leaving the curved metric to refine a roughly correct configuration.

How the experiments were run

All experiments initialize embeddings with the closed-form HYDRA solution, obtained from the eigen-decomposition of cosh(D), and refine it by Riemannian Adam. The pipeline carries no randomness: the warm start is a deterministic eigendecomposition and the stress is evaluated full-batch. Learning rates are searched in each graph per preconditioner curvature, on a 1/3/10 ladder, and every reported result corresponds to the best rate in terms of loss that is bracketed, meaning it has a strictly worse or divergent neighbor on both sides. The reported value is the mean stress over the final 10% of iterations.

The stress objective is the squared difference between the embeddings' hyperbolic distance at fixed curvature -1 and the corresponding shortest-path distance in the graph. The graphs include five trees, four of them real phylogenies from the Open Tree of Life synthetic tree (release 16.1): induced subtrees of the clades Marsupialia, Cichlidae and Falconiformes, and a rooted subtree of Fabaceae. The fifth is a synthetic caterpillar, a path of 40 nodes with 4 leaves attached to each. Two hub-dominated graphs of small diameter are also included: a Holme-Kim scale-free graph generated with NetworkX's powerlaw cluster graph, and the European air-traffic network.

Single-curvature results show the exact metric is worst

In the single-curvature ablation, the exact metric using c = 1 is effectively frozen after a few iterations where stress does decrease, and larger learning rates simply diverge. From the HYDRA initialization it ends between 2 and 20 times above the best single curvature. Intermediate values of c can produce the best results overall, and c approaching 0 is systematically among the best single-curvature results, which is why it is used as the initialization for the two-stage scheme.

The radial span separates the graphs that benefit from those that do not. On the two hub-dominated graphs and on Falconiformes, whose span is 13.2, all curvatures, learning rates and schedules reach the same stress to within 1%. Graphs with larger radial spans are more sensitive to the preconditioner curvature.

Two-stage gains and where they vanish

The two-stage scheme produces significantly improved results. In the synthetic caterpillar, stress is decreased almost by two orders of magnitude. In real-world graphs the gain is more modest but still significant, with decreases of between 25 and 50% in graphs with large radial spans when compared to simply restarting Adam. Compared to choosing a single curvature throughout the whole number of iterations, the schedule gain is larger: the best two-stage run reduces stress by 46-74% over the best single curvature on real-world trees, and by 98.0% on the synthetic caterpillar.

The curvature gain, which compares the best of c in {0.2, 0.3} with c = 10^-6 during stage 2, is -98.7% on the caterpillar, -53.2% on Marsupialia, -26.5% on Fabaceae, -23.1% on Cichlidae, and -0.8% on Falconiformes. The schedule gain is -98.0%, -74.1%, -60.0%, -45.8%, +0.4%, +0.4% and +0.1% across the same graphs. In graphs with smaller radial spans the gains from the two-stage scheme are null: the preconditioner's curvature has no effect there, visible already in the single-phase scheme, and a second phase does not change that.

What the radial span threshold means for practice

The paper's own priority is the radial span of the warm start, s = r_max - r_min. Since r_min is about 0.5 and r_max is about diam/2, deep unbalanced trees of large diameter, with nodes spread over a wide range of depths, are the type of graphs for which the preconditioner choice should matter, whereas for small-world graphs it should not. The span acts as a threshold rather than a predictor: it separates the graphs that benefit from those that do not, but it does not order the size of the gain.

Two limitations qualify how far this transfers. The best curvature and learning rate were found by grid search separately for each graph, so a rule that sets them from the graph, or adapts them during optimization, would make the method more practical. And the study covers a single objective, stress; whether the same preconditioning view carries over to other hyperbolic embedding losses, and to larger graphs, remains an open question. For a reader deciding what to take from this paper, the actionable split is the radial span: on graphs whose warm start spreads nodes over a wide range of radii, the exact hyperbolic metric is the worst option tested and a flat-then-intermediate two-stage schedule is the priority; on small-span graphs, curvature and schedule choices collapse to the same stress within 1%, so the choice does not matter.

Sources used in this answer