Hyperbolic embeddings place the nodes of a graph in a curved space whose volume grows exponentially with distance from the origin. That lets a tree-like graph such as the WordNet noun hierarchy fit into five dimensions better than a flat embedding fits into two hundred. There is a catch that nobody has treated as an optimization problem. For the usual training losses, the loss reaches zero only in the limit where nodes are pushed infinitely far out, toward the boundary of the space. Hyperbolic embedding is therefore an interpolation problem: the model can drive every training term toward zero. Interpolation is exactly the regime where recent optimization theory says step-size tuning should become easy, because per-example gradients vanish at the solution. In hyperbolic space, though, getting closer to zero loss means moving outward. Moving outward is what makes training numerically fragile, and it is also what makes the generalization bound grow exponentially.
We propose to take this tension seriously in two parts. First, we diagnose it by decomposing the coupled, node-by-node training dynamics into independent graph modes, the way control theorists decouple networked systems. Second, we build an adaptive step size that works with that diagnosis rather than a hand-tuned "burn-in" schedule. This step size is a stochastic Polyak step: it sets each update's length from the current loss divided by the squared gradient norm. We give it two caps, a per-node cap from a radius budget and a global cap from the top eigenvalue of a curvature-weighted graph Laplacian. The claim to test is that this step matches or beats tuned Riemannian optimizers on hierarchical link prediction without a learning-rate search. It must also keep the embedding radius, and so the generalization penalty, under explicit control.
Core Claim
The Euclidean interpolation results rest on the fact that per-example gradients vanish at an attainable minimizer. That fact yields linear convergence with constant step sizes (The Power of Interpolation; Fast and Faster Convergence of SGD for Over-Parameterized Models) and parameter-free Polyak steps (Stochastic Polyak Step-size for SGD). The hyperbolic case breaks that premise in a specific way.
The situation resembles logistic regression on separable data. The infimum of the loss is zero but is approached only as the radius $R$ of the embedding grows. On such problems the loss and the gradient shrink together, so an uncapped Polyak step lengthens as training succeeds. In Euclidean space this is tolerable. In hyperbolic space it collides with two documented facts. Generalization Bounds for Graph Embedding Using Negative Sampling proves the hyperbolic generalization bound grows as $O(e^R)$ against polynomial growth in flat space. Hyperbolic Hierarchy-Aware Knowledge Graph Embedding and Poincaré Embeddings report numerical breakdown and step-size hypersensitivity near the boundary.
Our hypothesis is that the right fix is neither a tuned learning rate nor a decay schedule. The step should be a Polyak step whose ceiling is set by geometry. Each node may move no farther than its remaining radius budget, and the global step may not exceed the stability limit of the linearized dynamics. We further hypothesize that this stability limit is predictable. Near a configuration, the training dynamics of all nodes are coupled through the graph, and they approximately separate along eigenvectors of a Laplacian whose edge weights depend on how deep the endpoint nodes sit. Nodes at different depths behave like heterogeneous agents. That heterogeneity is exactly the case the spectral-decoupling literature flags as open.
Research Program
The first part of the program is a measurement study. Standard optimization analysis already gives the fact we build on: gradient descent on a quadratic with Hessian $H$ is stable at constant step $\gamma$ only if $\gamma < 2/\lambda_{\max}(H)$. For a pairwise embedding loss, the Hessian has a graph structure. It couples node $u$ to node $v$ only when they share an edge or a sampled negative pair, and each coupling carries a $d \times d$ local block. Optimal Control of Network-Coupled Subsystems shows that when the local blocks are identical and the coupling matrix is symmetric, such a system splits into independent low-dimensional problems, one for each distinct eigenvalue of the coupling matrix. We supply that method and test how far it survives when the blocks differ by node depth. Concretely, we approximate the Riemannian Hessian at checkpoints by a weighted graph Laplacian,
$$ H \approx L_w \otimes I_d, \qquad (L_w)_{uv} = -w(r_u, r_v) \ \text{for each edge } (u,v), $$
where $r_u$ is the hyperbolic distance of node $u$ from the origin, $d$ is the embedding dimension, and $w$ is the loss curvature along the edge at the current radii. We compute $\lambda_{\max}(L_w)$ by power iteration, which costs time linear in the number of edges. We then check three things against the exact Hessian-vector-product spectrum on small graphs. The first is whether $\lambda_{\max}(L_w)$ tracks the empirical divergence threshold of constant-step Riemannian SGD. The second is how the threshold grows with tree depth and radius. The third is how much off-mode coupling the depth heterogeneity introduces.
The second part is the optimizer. For a sampled term $f_i$ touching node $u$, the update moves along the geodesic retraction with step
$$ \gamma_{i,k} = \min\left( \frac{f_i(x_k)}{c\,\|\operatorname{grad} f_i(x_k)\|_{g}^2},\ \frac{R - r_u}{\|\operatorname{grad} f_i(x_k)\|_{g}},\ \frac{2}{\lambda_{\max}(L_w)} \right). $$
Here $\|\cdot\|_g$ is the norm under the hyperbolic metric, $c$ is the Polyak constant (kept at the value analyzed in the SPS paper), $R$ is the radius budget, and $\lambda_{\max}(L_w)$ is refreshed every epoch. The first term is the Polyak step with target loss zero. The second term stops any node from stepping past radius $R$. The third term is the stability cap from the measurement study. It replaces the $\gamma_b$ ceiling that SPSmax leaves as a free hyperparameter. The only remaining knob is $R$, and $R$ has a meaning: it is the quantity the generalization bound penalizes. We implement the optimizer in the Lorentz model to avoid the conformal-factor overflow of the Poincaré ball, following the direct-manifold approach of Fully Hyperbolic Rotation for Knowledge Graph Embedding.
The third part is theory, kept modest. We aim for a linear-rate statement for this step on the radius-constrained problem. Inside the ball of radius $R$ the loss has a nonzero minimum, so the result would be convergence to a neighborhood whose size is set by that minimum. We also want an explicit dependence of the rate on $\lambda_{\max}(L_w)$ as a function of $R$. That dependence is what would connect the optimization side to the exponential-in-$R$ bound of Suzuki et al.
Scalability enters as a constraint, not as the contribution. Every added quantity is either per-node and $O(1)$ per update (the radius cap) or a single linear-time power iteration per epoch (the stability cap). The optimizer adds no extra forward passes, unlike stochastic line search (Painless Stochastic Gradient). It should therefore run at the scale of OGB WikiKG 2 as a drop-in for shallow embedding tables. Compressing those tables, as NodePiece and Tensor-Train methods do, is orthogonal and out of scope.
Baselines
The naive reference point is Riemannian SGD with a single constant learning rate and the burn-in phase of Poincaré Embeddings. That paper trains with projection back inside the ball and a reduced-rate warm-up. We run it with a grid over learning rate and burn-in length. The grid gets the same number of full training runs as the radius-budget grid for our method, so both sides have an equal tuning budget. We report the best configuration by validation score.
The strongest competitor in practice is Riemannian Adam applied to the same Lorentz-model embeddings. Per-coordinate adaptivity can in principle absorb depth-dependent scaling on its own, which makes it the most direct threat. It receives the same trial budget over learning rate. We also tune the radius projection for it, so that radius control is not an advantage unique to our method.
For published reference numbers we use the strongest results in the file. On WN18RR, HBE reports MRR 0.488 against 0.481 for MuRP and 0.476 for RotatE (Hyperbolic Hierarchy-Aware Knowledge Graph Embedding). On the WordNet noun closure, Poincaré embeddings report reconstruction MAP 0.823 at dimension 5, against 0.168 for a 200-dimensional Euclidean baseline. On FB15k-237, HBE reports MRR 0.336 and RotatE 0.338. On OGB WikiKG 2, no reported MRR number was found on Lacuna for NodePiece or for any hyperbolic model. There we report our own reruns of Riemannian SGD and Riemannian Adam only.
Beating the baselines has a precise meaning. Our optimizer should reach the tuned baselines' best validation score with no learning-rate search, averaged over five seeds. Alternatively, it should exceed their score at equal tuning budget. On WN18RR the target is to reach or exceed the 0.488 HBE figure with a comparable decoder.
Three ablations isolate the ingredients. The first uses the Polyak step without either cap and should reproduce the predicted radius runaway. The second uses tuned Riemannian SGD with the same radius budget $R$, which isolates the Polyak step from radius control. The third uses our step with a hand-tuned ceiling instead of $2/\lambda_{\max}(L_w)$, which tests whether the spectral stability cap is doing real work.
Why not just…?
Why not just tune Riemannian SGD with burn-in, as everyone does? Tuned Riemannian SGD works, and that is the reason it is the naive baseline. The cost is the search. The Poincaré paper documents sensitivity to initialization and learning rate, and a schedule tuned on one graph depth need not transfer to another. Our measurement study tests this directly: if the divergence threshold scales with $\lambda_{\max}(L_w)$, a rate tuned on a shallow tree should fail on a deeper one. If instead a single tuned rate transfers across depths on the synthetic trees, the diagnostic motivation weakens and we will say so.
Why not just use Riemannian Adam? This is the real threat. Adam's per-coordinate rescaling may already compensate for depth heterogeneity. What it does not do is set its own rate or control radius, since its normalized steps keep pushing nodes outward as loss falls. The head-to-head comparison at equal budget settles the question. If Riemannian Adam with a tuned radius projection matches our method on WN18RR and WordNet, the contribution shrinks to the spectral diagnosis and the no-tuning property. We would report the method as tuning-free rather than as more accurate.
Why not just early-stop? Early stopping controls radius implicitly, and the file contains no evidence against it. The difference is that early stopping ties radius control to the optimizer's speed. A fast optimizer overshoots between validation checks, and a slow one never reaches the useful radius. We will include early stopping as a stopping rule for every baseline and log the final radius distribution. The comparison is then about accuracy at a matched final radius, not merely at the best checkpoint.
Why not just switch coordinates, as HBE or the Lorentz model do? Better coordinates fix floating-point overflow near the boundary but leave the loss unchanged. Its infimum still sits at infinite radius, and the $O(e^R)$ generalization penalty of Suzuki et al. is stated in terms of radius, not coordinates. We already use Lorentz coordinates in every arm, so any remaining gap is attributable to the step rule.
Proposed Experiments
The controlled study uses the synthetic balanced 5-ary tree from Suzuki et al. and deeper variants built the same way. On these trees we sweep depth and radius budget. For each setting we measure three things: the empirical constant-step divergence threshold, $\lambda_{\max}(L_w)$, and the exact top Hessian eigenvalue from Hessian-vector products. We also measure the fraction of Hessian mass outside the graph-mode approximation.
The first decisive check is whether $2/\lambda_{\max}(L_w)$ predicts the divergence threshold within a small constant factor across depths. If it does not, the stability cap is unjustified and falls back to a tuned ceiling.
On real hierarchies we train on the WordNet noun transitive closure (82,115 nouns) in dimensions 5 and 10, reporting reconstruction MAP. We also run WN18RR link prediction, reporting MRR and Hits@10, and use FB15k-237 as a non-hierarchical control where hyperbolic geometry is not expected to help. For every run we log wall-clock time to reach 95% of final validation score, the final radius distribution, and the number of tuning runs consumed.
The second decisive check is the generalization curve. We sweep $R$ and plot validation MRR against training loss. Suzuki et al. predict a regime where more radius buys lower training loss but worse held-out performance. Our method should let us sit at the peak of that curve by choice of $R$, whereas uncapped Polyak should run past it.
The scale check runs the optimizer on OGB WikiKG 2 (2.5M nodes, 17.1M edges) with shallow Lorentz tables. We report MRR, per-epoch overhead relative to Riemannian SGD, and the cost of the epochly power iteration. The expected overhead is a few percent. A per-epoch cost that grows faster than the edge count would contradict the scalability constraint.
A fair negative outcome is possible: our method might match but not beat tuned Riemannian Adam, while cutting the tuning cost to a one-dimensional search over a quantity with a meaning. That is still a useful result for practitioners, and we will report it that way.
References
- The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
- Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
- Generalization Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic
- Hyperbolic Hierarchy-Aware Knowledge Graph Embedding for Link Prediction
- Poincaré Embeddings for Learning Hierarchical Representations
- Optimal Control of Network-Coupled Subsystems: Spectral Decomposition and Low-Dimensional Solutions
- Fully Hyperbolic Rotation for Knowledge Graph Embedding
- Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates