Hyperbolic Tree Coordinates with Portal Repairs: Hierarchical Embeddings That Stay Bounded on Cyclic Graphs

Hyperbolic embeddings place graph nodes in a curved space where room grows exponentially with distance from the center, much as the number of nodes in a tree grows with depth. They represent tree-shaped data very well: five hyperbolic dimensions do better on WordNet than two hundred Euclidean ones. Real graphs, however, contain cycles, and once a graph stops looking like a tree these methods offer no worst-case guarantee on how badly distances are stretched. The fastest such method, TREEREP, says so explicitly. A separate line of theory has solved a closely related problem by a different route. It maps planar and minor-free graphs into host graphs of low treewidth, meaning graphs that break apart along small vertex sets the way a tree breaks at a single vertex. It does this by recursively cutting the graph along shortest paths, placing evenly spaced "portal" vertices on those cutting paths, and adding shortcut edges so the recursion tree stays shallow. The resulting guarantees are strong, but they have never been turned into a representation a learning system could store and query.

This note proposes a representation that combines the two. Each node stores two things. The first is hyperbolic coordinates for its position in a spanning tree of the graph. The second is a short sketch of its distances to the portals on the cutting paths of its ancestors in a shallow, shortcut-compressed decomposition tree. The distance estimate is the smaller of the tree distance and the best route through a shared portal. Because both quantities are lengths of real walks in the graph, the estimate never underestimates a true distance. In the planar case, the portal term inherits a proven additive error bound. The main question is empirical: at a fixed number of bytes per node, does "one hyperbolic tree plus portal repairs" beat "several trees" and "distances to random landmarks" on graphs whose cycle structure defeats a single tree?

Core Claim

Two groups of prior work motivate the proposal. Tree! I am no Tree! I am a low dimensional Hyperbolic Embedding reconstructs a tree, including added junction nodes, directly from a metric and places it in hyperbolic space in linear time using Sarkar's construction. It recovers the metric exactly when the input is a tree, but its authors give no global distortion bound when the input is far from tree-like. Canonical Tree Cover Neural Networks replaces one tree with a cover of $O(\log n)$ spanning trees. It proves that such covers never contract distances and reduces empirical max stretch on ProteinShake from roughly 170x to 18x. Even so, 18x is far from $1+\epsilon$, and the leftover non-tree edges still need message passing.

A third group supplies the method. Low Treewidth Embeddings of Planar and Minor-Free Metrics routes cross-cluster distances through portals on shortest-path separators. It compresses decomposition depth from $O(\log n)$ to $O(\log\log n)$ with shortcut edges, obtaining host treewidth $O(\log\log n)^2$ at additive error $\epsilon\cdot\mathrm{diam}(G)$. Metric Embedding via Shortest Path Decompositions supplies the recursive shortest-path cutting. Embedding Planar Graphs into Graphs of Treewidth O(log3 n) supplies a multiplicative $1+\epsilon$ variant at treewidth $O(\epsilon^{-1}\log^3 n)$.

None of these three papers produces a per-node representation of coordinates plus a sketch, and none is evaluated as an embedding against hyperbolic methods. Our claim is that host treewidth, a quantity from theory, becomes a concrete storage cost per node. Paying that cost on top of a hyperbolic tree gives a non-contracting estimator that is provably bounded on planar inputs and measurably better than tree covers on cyclic real graphs.

Formally, let $T$ be a spanning tree of $G$, embedded hyperbolically so that $d_T(u,v)$ is read off coordinates. Let $P(u)$ be the portals on separators of the decomposition pieces containing $u$. For each $p \in P(u)$, node $u$ stores the exact graph distance $d(u,p)$. The estimate is

$$\hat d(u,v) = \min\Big\{\, d_T(u,v),\ \min_{p \in P(u)\cap P(v)} \big[d(u,p) + d(p,v)\big] \Big\}.$$

Both terms are lengths of walks in $G$, so $\hat d(u,v) \ge d(u,v)$ always holds. For planar $G$, the portal term alone satisfies $\hat d(u,v) \le d(u,v) + \epsilon\,\mathrm{diam}(G)$, by the portal-routing argument of Filtser and Le. The number of stored distances per node, $|P(u)|$, scales with the number of ancestor levels times the portals per separator. This is why the shortcut depth compression matters: it reduces the number of levels that must be stored.

Research Program

The build has three parts. The first is the decomposition. We recursively cut $G$ along a few shortest paths, following the shortest-path decomposition. On non-planar real graphs we use the same cutting heuristically, choosing paths by betweenness. We place portals at spacing $\epsilon\cdot\mathrm{diam}$ along each cutting path. We then add low-hop shortcuts over the decomposition tree so that each node needs portals from only $O(\log\log n)$ shortcut-ancestors rather than all $O(\log n)$ ancestors. For planar inputs this follows the published construction. For general graphs we treat it as a heuristic and measure its error directly.

The second part is the backbone. We use a shortest-path tree rooted at a central node, or the first canonical tree from the tree-cover construction, and embed it with Sarkar's construction. The backbone must be a subgraph of $G$ so that non-contraction holds. For this reason TREEREP's tree, which can contract distances, is used only as a comparison and not as the backbone. The shortcut-compressed decomposition also has a secondary benefit: it is shallow. Boundary collapse in the Poincaré ball, a known failure for deep trees, may therefore be less severe. We measure this with 32-bit coordinates.

The third part is analysis. For planar inputs we state and verify the inherited bound. For general graphs we report the empirical additive and multiplicative error as a function of Gromov's $\delta$. This directly addresses TREEREP's open question: how many bytes beyond a tree are needed for a global bound once $\delta$ is large? As a modest probe of the planar treewidth gap, $\Omega(\log n)$ against $O(\log^3 n)$ (Conjecture 1.1 in Chang et al.), we measure on planar triangulations how the per-node portal count needed for fixed $\epsilon$ grows with $n$. This is evidence about practical constructions, not a proof.

Baselines

The naive reference is a single hyperbolic tree. It is Sarkar's construction applied to the same spanning tree with no portals, which is the first term of $\hat d$ alone. TREEREP will be run on identical inputs as the strongest single-tree hyperbolic method. For TREEREP, there is no reported distortion number on Lacuna for WordNet; the paper reports only that it beats direct optimization "in most test cases" and runs over 10,000 times faster. We therefore rerun it ourselves.

The strongest continuous competitor is Poincaré embeddings trained with Riemannian gradient descent, from Poincaré Embeddings for Learning Hierarchical Representations. That paper reports a WordNet noun reconstruction MAP of 0.823 in 5 dimensions, against 0.168 for 200-dimensional Euclidean embeddings. We give it the same bytes per node as our method by raising its dimension, and the same hyperparameter-search budget.

The strongest multi-tree competitor is a canonical tree cover. The distance estimate is the minimum over $k$ covering spanning trees, each embedded hyperbolically, with $k$ chosen to match our byte count. The ProteinShake reference is the reported max stretch of 18x from Canonical Tree Cover Neural Networks. Minimum-distortion embedding from Minimum-Distortion Embedding serves as the Euclidean reference at equal bytes.

Two ablations isolate the key ingredient. The first replaces separator portals with the same number of uniformly random landmarks. The second removes the shortcut compression and stores portals for all ancestors, which shows what the depth compression saves in bytes. To count as a win, our method must show lower worst-case stretch and lower average distortion than both the tree cover and the landmark ablation at equal bytes, on at least the cycle-rich graphs, while not losing to Poincaré embeddings on WordNet MAP.

Why not just…?

Why not just use more trees? This is the real threat. Tree covers are simple and never contract distances. On sparse, nearly planar graphs, a handful of trees may already close most of the gap. The equal-byte comparison against $k$-tree covers settles this directly. We expect trees to lose specifically on pairs separated by long cycles, such as grids, road-like structure, and protein contact graphs, where no small number of spanning trees keeps both sides of every cycle short. If tree covers match us on real graphs and trail only on synthetic planar ones, we will say so, and the contribution narrows to the guarantee.

Why not just raise the hyperbolic dimension or use a product of hyperbolic spaces? Continuous optimization needs careful warm-up and is sensitive to initialization, as the Poincaré paper notes. More importantly, a smooth low-dimensional manifold has no mechanism for representing two short routes around a cycle simultaneously. The equal-byte Poincaré baseline, stratified by $\delta$, will show whether added dimensions substitute for portals.

Why not just store distances to random landmarks? Landmarks also give non-contracting estimates through the triangle inequality. However, they have no structural reason to lie on the paths that separate $u$ from $v$, so their error on nearby pairs in different regions can be large. This alternative is exactly the random-portal ablation. If random landmarks match separator portals, the decomposition machinery is unnecessary and the proposal reduces to "hyperbolic tree plus landmarks."

Proposed Experiments

The datasets are the WordNet noun hierarchy (about 82,000 nouns), serving as a near-tree control where portals should add little. The cyclic real graphs are the collaboration networks, Cora, Citeseer, Pubmed, Polblogs, and WebKB used in Curvature Regularization to Prevent Distortion in Graph Embedding, along with ProteinShake graphs. Synthetic planar grids and triangulations of increasing $n$ supply the regime where the planar guarantee applies.

The metrics are average distortion, max stretch, stretch stratified by true distance (because additive error hurts short pairs most), and WordNet reconstruction MAP. We also check HyperLex Spearman correlation, where Poincaré embeddings report 0.512, to confirm that the hierarchy-sensitive part of the representation is not degraded.

There are three decisive checks. First, on planar triangulations, max stretch at fixed bytes should stay bounded as $n$ grows for our method, while it grows for tree covers. Second, on real graphs, the advantage over tree covers should increase with Gromov's $\delta$. Third, the per-node portal count needed for fixed $\epsilon$ should grow far more slowly with shortcut compression than without it. If the first check fails, the transfer from theory is broken. If the second fails, the method is a theoretical curiosity for real data.