Insert-Stable Hyperbolic Tree Embeddings

Hierarchies such as taxonomies, phylogenies and ontologies fit poorly into ordinary flat vector spaces. A tree's node count grows exponentially with depth, while the room in Euclidean space grows only polynomially, so leaves end up crowded together. Hyperbolic space, a curved geometry whose volume grows exponentially with radius, has enough room, and constructive algorithms now place trees there almost without distortion and without any gradient training. These algorithms share one weakness. They need the whole tree in advance. When a leaf arrives, the usual fix is to rebuild, and a rebuild moves essentially every coordinate. Any system built on those coordinates then has to redo its work: a nearest-neighbor graph, a cache of model inputs, or an encrypted, authenticated index in which every changed record must be re-encrypted. The secure-storage literature names this cost "dynamic update overhead". Its standard remedy is localization, meaning a change touches only a short path through the index and never the whole dataset.

This note proposes an online constructive hyperbolic embedding in which inserting a node never moves an existing coordinate, apart from a logarithmic number of global "rescale epochs" over the whole stream. Distortion stays within a small constant of the best batch method. Two simple ingredients make this work. Each node assigns directions to its children from a fixed prefix-stable sequence on the sphere. Such a sequence has the property that its first $k$ points are always nearly as well spread as the best possible placement of $k$ points. Separately, the global edge length is grown only in doubling steps. The quantity we optimize is churn, the number of previously placed nodes whose coordinates change, alongside distortion.

Core Claim

Constructive hyperbolic embeddings place each child relative to its parent. HS-DTE (Low-distortion and GPU-compatible Tree Embeddings in Hyperbolic Space) is the strongest example. It spreads a node's $k$ children over a sphere by maximizing their minimum angle, which addresses the "Tammes" crowding problem, and it reports worst-case distortion 1.07 on 3-ary trees. Adding a $(k{+}1)$-th child changes the optimal placement of all $k$ siblings, so every sibling's subtree moves. In a Sarkar-style construction, the uniform edge length needed for a given distortion also depends on the smallest sibling angle anywhere in the tree. A single high-degree node can therefore force every coordinate to move. These two couplings, local angles and the global edge length, are the full source of churn.

We break the first coupling with a greedy farthest-point sequence of directions. In such a sequence, each new point is placed as far as possible from all earlier ones. A child receives the next unused direction in its parent's sequence, and existing children never move. The standard farthest-point argument guarantees that every prefix is well separated. If $\theta_k$ is the minimum pairwise angle among the first $k$ points and $\theta^*_k$ is the best achievable minimum angle for $k$ points on the sphere, then

$$\theta_k \;\ge\; \tfrac{1}{2}\,\theta^*_k ,$$

because the $k$-th greedy point is chosen at the current covering radius, and that radius bounds the optimal packing from below. In the 2D disk this sequence is simply the bit-reversal (van der Corput) ordering of angles. We break the second coupling by fixing the edge length $\tau$ for a degree budget $\Delta$, and doubling $\Delta$, which triggers a global recomputation of $\tau$, only when some node exceeds it. If $\Delta_{\max}$ is the largest degree ever reached and $N$ the number of nodes, total churn over the stream is at most

$$\text{churn}_{\text{total}} \;\le\; N \log_2 \Delta_{\max},$$

so amortized churn per insertion is $O(\log \Delta_{\max})$. This mirrors the $O(\log N)$ path-localized updates that balanced trees give encrypted indices, the result of Xingming Sun et al.. Between epochs, churn is exactly zero.

The claim to be tested has two parts. The first is that the factor-two loss in sibling angle costs only a small additive increase in the edge length, so worst-case distortion stays close to HS-DTE's. The second is that a rescale epoch preserves nearest-neighbor rankings almost exactly, since it only stretches tree distances uniformly. If so, a downstream hyperbolic proximity graph can survive an epoch without rewiring, and the effective churn seen by the index is lower still.

Research Program

The method is built on HS-DTE's top-down placement, with its global angle maximization replaced by per-node prefix-stable direction sequences. Within each node's local frame, the first direction always points back to the parent. Higher-dimensional sequences are computed once by greedy farthest-point search over a dense spherical sample and shared across all nodes. Coordinates are stored in the Lorentz model using HypFPE multi-float arithmetic from the same paper. That paper shows plain float64 collapses on deep trees, with distortion 9.42 on the depth-30 Mosses tree. Online insertion may grow trees deeper than a batch run ever sees, so this precision support matters more here than in the batch setting.

Deleting a leaf frees a direction slot and moves nothing. Re-parenting a subtree is one hyperbolic rigid motion applied to that subtree. Its churn equals the subtree size, which is also the minimum any low-distortion embedding must pay, because those distances genuinely change.

The analysis has two parts. The first bounds worst-case distortion as a function of the angle-loss factor and the degree budget $\Delta$. The goal is to show the degradation relative to the batch optimum is a constant independent of $N$. The second measures empirically how much of the analytic churn bound is really necessary, and checks whether rescale epochs leave neighbor rankings intact.

The secondary application is a dynamic hyperbolic nearest-neighbor index. Graph-based Nearest Neighbor Search in Hyperbolic Spaces shows that a static hyperbolic HNSW graph (Hierarchical Navigable Small World, a layered proximity graph searched greedily) needs fewer distance computations than a Euclidean one for the same recall. It leaves maintenance under insertions open. We measure how much edge rewiring that graph needs when the coordinates underneath it come from our method versus from rebuilds.

Private search systems are the motivating constraint rather than the target. In Pacmann, a private nearest-neighbor system that retrieves graph nodes from the server without revealing which ones, any change to the database forces a roughly 60 GB client setup to be repeated. Plinko makes updates to a flat table of records cheap in private retrieval. That cheapness only helps if few records change, which is exactly what low churn delivers. We do not build the cryptographic layer here. We report churn in units that would translate directly into re-encrypted records.

Baselines

The naive reference point is periodic batch rebuilding with HS-DTE. The tree is re-embedded from scratch after every $B$ insertions, for $B$ ranging from 1 to $N/10$, and new nodes are held in an un-embedded buffer in between. This is the strongest competitor on distortion, since it is the batch method. The paper reports worst-case distortion 1.07 on 3-ary trees, versus 1.14 for earlier constructive methods, and MAP 1.00 on the Mosses, Weevils and Carnivora phylogenies, all for static trees. On the streaming setting, no reported result found on Lacuna.

The rebuild baseline runs on the same hardware, with the same HypFPE precision and the same insertion orders. Beating it means two things. Our final worst-case distortion must be within 0.05 of the rebuild's on the synthetic trees, with MAP within 0.01 on the real hierarchies. Our cumulative churn must also be at least an order of magnitude lower at equal or better freshness, where freshness counts nodes that have arrived but are not yet embedded.

The second baseline is TREEREP (Tree! I am no Tree!), run in the same rebuild loop. It is a batch method that rebuilds a tree from pairwise distances and runs over 10,000 times faster than gradient-based embeddings. It represents the cheapest possible full rebuild.

The third baseline is Riemannian SGD fine-tuning: existing Poincaré coordinates are frozen and only each new node is optimized, with a matched wall-clock budget per insertion.

The key ablation is greedy-gap insertion. Each new child goes into the largest free angular gap at its parent, with no prefix-stable sequence and no degree budget. It also has zero churn, so it isolates whether the guaranteed spacing of the sequence matters. A second ablation removes rescale epochs and keeps $\tau$ fixed at its initial value. This isolates the cost of never moving anything.

Why not just…?

Why not just rebuild periodically, since constructive embedding is fast? Computing the new coordinates is cheap; that is not the cost. The cost is that a rebuild moves nearly every coordinate, and everything downstream must follow. That includes re-encrypting records, invalidating proximity-graph edges, and in Pacmann's design re-running the client setup. This alternative is a real threat whenever nothing downstream depends on stable coordinates, and we say so plainly. The experiments settle where the line falls by plotting distortion against cumulative churn for every rebuild interval $B$. If some $B$ matches our distortion at comparable churn, the proposal fails.

Why not just drop each new child into the largest empty gap? It is the obvious zero-churn heuristic. Its weakness is that an adversarial or simply skewed arrival order can leave a node with siblings far closer than the optimal spacing, and distortion compounds with depth, as the Tammes analysis in HS-DTE shows. The farthest-point prefix bound is exactly what greedy-gap lacks. If greedy-gap matches our distortion under random, breadth-first, depth-first and high-degree-first insertion orders, the sequence ingredient is unnecessary, and we would report the simpler method.

Why not just fine-tune new nodes with Riemannian gradient descent? TREEREP reports that optimization-based hyperbolic embeddings are over 10,000 times slower than constructive ones. Freezing existing coordinates also makes the optimization non-convex near the ball boundary, where small coordinate errors become large distance errors and float64 already fails at depth 30. We include it at matched wall-clock time. We expect it to lose on worst-case distortion for deep trees, and that is a measurement in this proposal, not an assumption.

Proposed Experiments

Synthetic trees. We stream balanced $m$-ary trees with $m \in \{3,5,7\}$, plus skewed trees with heavy-tailed degrees that stress the degree budget. We measure worst-case and average distortion, MAP, cumulative churn, and the number of rescale epochs, compared against the $N \log_2 \Delta_{\max}$ bound.

Real hierarchies. We stream the Mosses, Weevils and Carnivora phylogenies, the disease-relation and CS PhD advisor graphs from the HS-DTE benchmarks, and the 82,115-noun WordNet hierarchy. For WordNet we use a spanning tree, because the constructive methods assume trees. Insertion orders are random, breadth-first and depth-first. The deep Mosses tree is run at both float64 and HypFPE precision to check that insertion does not reintroduce the precision collapse.

Downstream index. We build hyperbolic HNSW over WordNet incrementally on each method's coordinates. We track Recall@1 against distance computations per query, together with total edge rewirings, and check whether rescale epochs need any rewiring at all.

Decisive checks. The proposal succeeds on two conditions. First, final worst-case distortion stays within 0.05 of batch HS-DTE on 3-ary trees, against its reported 1.07. Second, cumulative churn is at least ten times lower than the best rebuild interval at equal freshness. It fails if greedy-gap matches it on every insertion order, or if rescale epochs scramble neighbor rankings enough to force a full HNSW rebuild.