NOTE-1323: Alvarez-Melis et al. — Hyperbolic OT hierarchy matching

Contribution

It poses unsupervised matching of hierarchies, cross-lingual WordNets and biomedical ontologies, as correspondence between their embeddings in the Poincaré ball, with no labels, no text similarity and no external knowledge. It reports a “negative” result, that Euclidean aligners and their orthogonal-map hyperbolic analogues fail. It attributes the failure to a phenomenon it names “branch permutation invariance”: embeddings of the same hierarchy from different seeds place branches differently. It proposes to register one space onto the other with a hyperbolic neural network fθ, trained end to end by minimising a Sinkhorn divergence under the hyperbolic distance.

Key insight

The arbitrariness between two learned representations need not be a group action. Between two runs of a hyperbolic embedding method, “the relative positions of branches in the hierarchy might change abruptly across different runs of the embedding algorithm, even for the exact same data and hyperparameters” (p. 6). That change is not an isometry: Fig. 2 measures it as a discrepancy between the two runs’ pairwise distance matrices, where “Truly isometric embeddings would yield 0 discrepancy” (p. 6). So no fixed class of global isometries can absorb it. The registration class has to be widened “not only beyond orthogonality but beyond linearity too” (p. 6). The price is that a very flexible map can fit a coupling to almost anything, and the result then depends heavily on how the map is initialised.

Assumptions

• Embeddings given and fixed: “we focus on the second step of this pipeline —the matching— and assume the embeddings of the hierarchies are already learned and fixed” (p. 2). All datasets are embedded by Nickel and Kiela’s method in 10 dimensions (§7, p. 7; Table 3, p. 13).
• The Poincaré ball D^d with distance d_D(u, v) = arcosh(1 + 2‖u − v‖²/((1 − ‖u‖²)(1 − ‖v‖²))) (eq. 1, p. 3).
• A hyperbolic Wasserstein cost d_D(x, fθ(y)), not squared, in the full model (Table 4, p. 13), with uniform weights.
• A registration fθ from hyperbolic linear layers (W⊗x)⊕b with ELU nonlinearities applied through exp₀ and log₀ (p. 6), 10 layers of hidden width 20 (Table 4), constrained only to map the ball into itself.
• Pretraining is essential: the full model uses CrossMap, which fits fθ to send each target point to a source point “in a random permuted order” (App. A, p. 12).

Key results

Geometry (§3, pp. 3–4)

• Eq. (1), and ‖u‖_D = d_D(0, u) = 2 arctanh(‖u‖) (eq. 2). Both checked.
• A misprint. The conformal factor is printed as λ_x := 1/(1 − ‖x‖²) (p. 3). Eq. (1) and the exponential and logarithmic maps on p. 4 correspond to λ_x = 2/(1 − ‖x‖²). Checked: near a point x, the distance stretches displacements by 2/(1 − ‖x‖²).
• An overstatement. “all isometries in the Poincaré Ball have the form T (x) = P(v ⊕ x), where v ∈ Dd and P ∈ SO(d), i.e., it is an orientation-preserving isometry” (p. 4). With P ∈ SO(d) these are the orientation-preserving isometries. Reflections are isometries too: P ∈ O(d) preserved the distance in my check, to 10⁻¹⁴.
• The Möbius addition (eq. 4) is the standard one; translations x ↦ v ⊕ x preserve d_D (checked).

Why OT over hyperbolic space is well posed (§§4.2, 5; App. E–F)

• For quadratic cost, the paper says, the optimal coupling “is guaranteed to exist, be unique, and correspond to a deterministic map” (p. 4). That is Brenier’s theorem, which needs an absolutely continuous source. The paper’s measures are discrete, where a map need not exist at all. App. F states McCann’s version with its regularity condition (Theorem F.1, p. 14).
• Theorem F.2 (Lee and Li 2012, cited): on a manifold of constant curvature −1, the costs −cosh∘d and −log∘(1 + cosh)∘d satisfy the strong MTW condition, and ±log∘cosh∘d the weak one. The quadratic cost does not, because MTW for d²/2 forces non-negative curvature (p. 14, citing Loeper). These are regularity results for continuous maps. The paper’s computations are entropic and discrete, and in its own ablation the theory-backed cost −cosh∘d does worse than plain d (Table 1a).

Branch permutation (§5, Figs. 1–2, pp. 5–6)

• Fig. 1 (p. 5): one simple hierarchy embedded twice in the Poincaré disk with different seeds; branches swap position, and a non-linear fθ is needed to register them.
• Fig. 2 (p. 6): the discrepancy between pairwise distance matrices across seeds is non-zero for the Poincaré, hyperbolic cones and PGA methods, “although less prominent” in high dimensions (p. 6).
• The cause is a conjecture: negative sampling “prioritizes distance preservation between entities that are ancestrally related in the hierarchy, at the cost of downweighting distances between unrelated entities. A formal explanation of this phenomenon is left for future work” (p. 6).
• The name is apt for the trees and misleading for the embeddings. A swap of isomorphic subtrees is an automorphism of the tree, so it preserves the tree metric. If the embeddings were faithful, it would preserve their distances too, and GW, which is invariant to every isometry, would be indifferent to it. Fig. 2 shows the distances do change. What the paper calls an “invariance” is a seed-dependent distortion. The tree’s own symmetries remain a separate ambiguity that no registration can resolve (THEORY-1133).

The method (§6, pp. 6–7)

• Objective (10): min over θ with fθ[D^d] ⊆ D^d of SD_ε(α, fθ♯β), with the Sinkhorn divergence SD_ε(α, β) = W_ε(α, β) − ½(W_ε(α, α) + W_ε(β, β)) (eq. 9, p. 6). The authors call it “convex, smooth and positive-definite” (p. 6), citing Feydy et al. That convexity is in the measures, not in θ: “The loss function (10) is highly non-convex with respect to θ” (p. 7).
• Optimisation: Riemannian Adam (Radam) through geoopt, ε annealed by 0.99 per step from 10 to 10⁻², 200 outer iterations (p. 7; App. B, p. 12). “Even suitable layer-wise random initialization of weights and biases proved futile” (p. 7), hence the pretraining.

Results (§7, Tables 1–2, p. 8)

• Self-matching, En→En (Table 1a): the same hierarchy embedded twice, “where the correspondences between the two datasets are perfect and unambiguous” (p. 8). Full model P@1 22.2, P@10 88.8. Ablations: smaller network 8.7 / 38.0; Euclidean metric 3.1 / 13.0; ReLU for ELU 6.9 / 37.6; RSGD for Radam 14.7 / 69.5; Möbius layers 11.9 / 54.3; cost −cosh∘d 16.6 / 70.2; no pretraining 0.1 / 0.2.
• Across languages (Table 1b, P@10): Hyp-OT + NN fθ reaches 43.9 / 56.8 (En↔Es), 48.0 / 60.1 (En↔It), 54.3 / 57.5 (En↔Fr), 38.4 / 57.4 (En↔Ca). Hyp-OT with an orthogonal map reaches 0.47 to 11.2. Muse, Self-Learn and Invar-OT stay under 2.3 except Invar-OT Ca→En at 7.65.
• Ontologies (Table 2): OAEI Anatomy and Biodiv, scores 4.49 to 16.67 for Hyp-OT against 0.00 to 4.00 for Muse and Self-Learn. The caption does not say which precision is reported. The authors read the low numbers as showing the domains are “less coherent (partly because of their vastly different sizes)” (p. 8).
• Noise (Fig. 4, p. 8; App. C): removing nodes at random from the CS-PhD hierarchy, “accuracy degrades rapidly with noise” (p. 8), less in higher dimension.

Claims

id	claim	strength	support
C1	Poincaré embeddings of one hierarchy from different seeds differ by more than a hyperbolic isometry	moderate	Fig. 2, pairwise-distance discrepancy over 5 repetitions, three embedding methods; magnitude not readable here
C2	Euclidean aligners and hyperbolic OT with an orthogonal map fail on these embeddings	strong	Table 1b, all four language pairs; Table 2
C3	A hyperbolic neural registration trained by Sinkhorn divergence recovers a substantial part of the correspondence	moderate	Table 1b, P@10 38–60; single runs; P@1 not reported across languages
C4	Even with perfect correspondences, the method finds the exact match for under a quarter of items	strong	Table 1a, P@1 22.2 on self-matching
C5	Success depends on pretraining that starts from a random permutation	strong	Table 1a, no pretraining 0.1
C6	The cause of branch permutation is negative sampling	weak	conjecture (p. 6)
C7	GW “cannot account for the type of invariances encountered” with hyperbolic embeddings (p. 3)	weak	asserted; GW is never run in the paper
C8	Riemannian OT theory (McCann, Lee–Li) justifies the method	weak	the theorems are about continuous measures and exact OT; the theory-backed cost does worse (Table 1a)

Method

Embed each hierarchy in D¹⁰; pretrain fθ by CrossMap; then repeat for 200 steps: compute SD_ε between the source points and fθ of the target points with cost d_D, backpropagate through Sinkhorn (geomloss), take a Radam step, and decay ε. Read the matching from the final coupling and retrieve nearest neighbours for P@k (pp. 6–7, Fig. 3).

Concepts

• Branch permutation invariance — “a lack of consistent ordering of branches in the representations of a dataset across different runs of the embedding algorithm” (p. 2). Not a group invariance: it changes distances (Fig. 2).
• Registration function fθ — a map of the ball into itself that warps one embedding onto the other before transport (Fig. 3).
• Möbius layer — fMöbius(x) = P(v ⊕ x) with P ∈ SO(d), v ∈ D^d (p. 7), an orientation-preserving isometry.
• Sinkhorn divergence — entropic OT debiased so that SD_ε(α, α) = 0 (eq. 9).

Connections

• It extends Problem (8), joint transport and registration, from linear maps (LIT-1805, Zhang et al. 2017, Grave et al. 2019) to non-linear maps on a Riemannian manifold. It reads ICP as the hard-assignment, rigid, Euclidean special case (p. 3).
• It sets GW (LIT-1818) aside without testing it, and Fused GW (LIT-1813) because it “assumes node features and knowledge of the full graph structure” (p. 3).
• The embeddings come from Nickel and Kiela 2017 and 2018, Ganea et al. 2018b and Sala et al. 2018 (Fig. 2). None is held here.

Bearing on the record

• QUESTION-130: directed relations, the exchange’s point checked. The “Why this is here” says hyperbolic distance is still symmetric, so the paper is a partial answer to carrying directed, hierarchical relations. The text bears that out and narrows it. The hierarchy’s direction, “(u, v) ∈ D means that u is a subconcept of v” (p. 3), enters only through the embedding loss (eq. 3), which itself uses the symmetric distance. The transport cost is d_D, symmetric. The registration fθ is free to map the ball into itself, and nothing in it preserves distance from the origin, ancestry or the entailment order. So the method can carry direction only as far as it survives in the geometry of positions, and it does not check that it does. For a transport of entailment or obligation, the lesson is that matching points, however good the geometry, does not preserve the order on them unless the order is put into the cost or the map class.
• QUESTION-130 and THEORY-1140: a fourth kind of arbitrariness. The three-way distinction in LIT-1805’s “Why this is here” was a global isometry (GW), one global map from a class (global-invariance OT), and a frame at each node (gauge). This paper meets something that fits none of them: a seed-dependent, non-isometric warp, absorbed by one non-linear map of the whole space. It is global in that one fθ acts on every point. It is not a group action, so it has no frames, no connection and no holonomy. A fitted warp is a registration, not a transport.
• CLAIM-135: reconstruction, weakly. Self-matching, where identity is “perfect and unambiguous”, gives P@1 22.2 (Table 1a). Across languages only P@10 is reported. The paper reconstructs neighbourhoods more than it identifies items, and says nothing on constitution.
• CASE-185: the identification threat, in two forms. First, real hierarchies have isomorphic sibling subtrees, and any method using only structure is indifferent between their swaps (THEORY-1133). Second, a flexible registration adds ambiguity of its own: the full model starts from a random permutation (CrossMap) and still reports success. The correspondence it settles on is therefore decided by the optimiser’s path as much as by the data. The case’s plan to score correspondences on held-out items, and to validate anchors independently, is the right control for both.
• THEORY-1136: filed from this reading.
• An instruction for ML practice is present (pretraining schemes, Radam over RSGD, ε annealing). That belongs to the Anthology of the SOTA; the LIT carries the anthology-candidate flag.

Limitations

• Single runs, except Fig. 2’s 5 repetitions; no variance for Tables 1–2.
• GW is dismissed, not tested (p. 3), though it is the natural isometry-free baseline.
• P@10 only across languages, and the ontology table does not name its metric.
• The theory cited does not cover the computation: discrete, entropic, with a non-convex outer problem in θ.
• Two misprints in §3: the conformal factor, and “all isometries” for the orientation-preserving ones.
• Branch permutation’s cause is a conjecture.
• The figures’ plots did not survive extraction.

Open questions

• Does GW, which ignores every isometry and needs no registration, do as well as the neural registration on Table 1b? It would show whether the failure is distortion or merely the wrong invariance class.
• How much of the distortion is in the embedding method rather than in the hierarchies? A low-distortion construction, such as Sala et al.’s combinatorial embedding, matched across seeds, would say.
• Can the entailment order be built into the cost, for instance by penalising couplings that invert ancestor pairs, and does that improve P@1?