Geometry-aware Distance Measure for Diverse Hierarchical Structures in Hyperbolic Spaces

Pengxiang Li, Zhi Gao, Xiaomeng Fan, Wu Wei, Yuwei Wu, Zhipeng Lu, Yunde Jia, Mehrtash HarandiSubmission to ICLR 2025 · Withdrawn

TL;DR

Standard hyperbolic neural networks use a fixed Riemannian distance metric with a constant curvature, implicitly assuming that all data pairs share a uniform hierarchical depth. This paper introduces a geometry-aware distance measure that dynamically predicts pairwise curvatures and low-rank transformation matrices tailored to the complexity of individual sample relationships, backed by theoretical error bounds and efficient hard-pair mining.

What Problem Does This Paper Address?

Hyperbolic spaces are ideal for modeling hierarchical data because their exponential volume expansion naturally mirrors branching tree structures. However, existing methods typically measure similarity using standard geodesic distance over a manifold with a single, static curvature $c$.

This uniform geometry breaks down on real-world datasets where taxonomic complexity varies widely. For example, comparing closely related species (like dog vs. wolf) represents a shallow, simple subtree, whereas comparing distant concepts (like aircraft carrier vs. school bus) spans multiple abstraction levels. Enforcing a single fixed curvature distorts these relationships, misaligning continuous geodesics with the true underlying semantic hierarchies.

Methods

The authors propose HDMG (Hyperbolic Distance Measure Generator), which dynamically maps sample pairs into an adaptive hyperbolic space before calculating geodesic distances:

$$d_{M, c}(x_i, x_j) = d_c(M \otimes_c x_i, M \otimes_c x_j)$$

where $\otimes_c$ denotes Möbius matrix multiplication in the Poincaré ball model. The framework consists of three core components:

  • Adaptive Curvature Generator ($g_c$): Uses factorized bilinear pooling to capture expressive second-order interactions between features $x_i$ and $x_j$, followed by sum pooling and a sigmoid activation to output a pair-specific curvature $c_{ij} \in [0, 1]$.
  • Residual Low-Rank Projection Generator ($g_t$): Learning an unconstrained $n \times n$ transformation matrix per pair causes optimization instability and heavy computational overhead. The authors stabilize training via a residual formulation: $$M = I + M_{a}^{\text{res}} (M_{b}^{\text{res}})^\top$$ where $M_a, M_b \in \mathbb{R}^{n \times k}$ with rank $k \ll n$ (e.g., $k=16$ for $n=512$). Using polynomial partitioning and Talagrand’s concentration inequality, they prove that the low-rank approximation error is bounded with high probability.

  • Hard-Pair Mining (HPM): To prevent $O(N^2)$ distance evaluations, only challenging samples near classification decision boundaries (where the ratio of distances to the nearest and second-nearest prototypes $d_1 / d_2 > T$) receive dynamically generated metrics; easy samples retain standard geodesic distances.

       Input Pair (xi, xj)
           /        \
          v          v
   Curvature Gen   Low-Rank Residual Matrix Gen
     [gc(xi, xj)]       M = I + Ma(Mb)^T
          \          /
           v        v
   Möbius Projection & Distance:
   dc(M ⊗c xi, M ⊗c xj)

Datasets

The authors evaluate on both standard visual benchmarks and hierarchical/few-shot tasks:

  • Standard Classification: MNIST, CIFAR-10, and CIFAR-100.
  • Hierarchical Classification: CIFAR-100 organized into a 5-level coarse-to-fine hierarchy (Levels 0 to 4) based on WordNet-style superclasses.
  • Few-Shot Learning: mini-ImageNet (100 classes) and tiered-ImageNet (608 classes, grouped into higher-level categories to test generalization across distinct semantic branches).

Key Insights and Ideas

  • Curvature controls tree capacity: Higher negative curvature $|c|$ creates a larger manifold volume and steeper geodesics, making it mathematically better suited for modeling deep, complex hierarchies, whereas lower $|c|$ fits local, shallow groupings.
  • Residual stabilization is crucial: Predicting dense manifold transformations from scratch destabilizes Riemannian optimization. Framing the projection as a low-rank residual deviation from the identity matrix ($I + M_a M_b^\top$) ensures smooth convergence.
  • Most pairs are easy: Empirical analysis shows that the vast majority of sample-prototype pairs do not need bespoke geometries. Generating metrics only for borderline cases reduces computational load without sacrificing discriminative precision.

Key Results

  • Few-Shot Image Classification: On mini-ImageNet, the proposed method achieves 64.75% (1-shot) and 81.89% (5-shot), outperforming fixed-metric hyperbolic proto-networks (Hyp-ProtoNet: 59.47% / 76.84%) and adaptive Euclidean baselines (TADAM: 58.50% / 76.70%). On tiered-ImageNet, it reaches 72.59% (1-shot) and 86.14% (5-shot).
  • Hierarchical Classification: On 5-level CIFAR-100 evaluation using ResNet-101, the adaptive distance outperforms the fixed baseline across all levels (e.g., Level 0 coarse accuracy improves from 95.95% to 97.88%, and Level 4 fine accuracy improves from 80.97% to 83.44%).
  • Computational Efficiency: Hard-pair mining eliminates 79% of pairwise metric generations on mini-ImageNet, cutting running time from 6.10 ms to 1.52 ms while slightly improving accuracy (81.80% vs. 81.89%).

Limitations and Future Work

  • Asymmetric Pairwise Distance: Because subnetworks $f_a$ and $f_b$ have separate weights, strict symmetry $d(x_i, x_j) = d(x_j, x_i)$ is not mathematically guaranteed (though empirical ablations show negligible performance variation when inputs are swapped).
  • Data-Distribution Sensitivity: The pairwise generators $g_t$ and $g_c$ could potentially overfit to specific dataset-level taxonomic priors.
  • Preliminary Low-Rank Decomposition: The current low-rank factorization operates algebraically; future work could investigate manifold-native matrix decompositions that explicitly preserve isometric properties.

Summary updated

Abstract

Learning in hyperbolic spaces has gained increasing attention due to the superior capability of modeling hierarchical structures. Existing hyperbolic learning methods use a fixed distance measure that assumes a uniform hierarchical structure across all data points. However, this assumption does not always hold in real-world scenarios, considering the diversity of the hierarchical structures of data. This work proposes to learn geometry aware distance measures that dynamically adjust to accommodate diverse hierarchical structures in hyperbolic spaces. We derive geometry aware distance measures by generating projections and curvatures for each pair of samples, which maps each pair to a suitable hyperbolic space. We introduce a revised low-rank decomposition scheme and a hard-pair mining mechanism to reduce the computational cost incurred by the pairwise generation without compromising accuracy. Moreover, we derive an upper bound of the low-rank approximation error via Talagrand concentration inequality to guarantee the effectiveness of our low-rank decomposition scheme. Theoretical analysis and experiments on standard image classification and few-shot learning tasks affirm the effectiveness of our method in refining hyperbolic learning through our geometry aware distance measures.
BibTeX
@misc{li2025geometry,
  author = {Pengxiang Li and Zhi Gao and Xiaomeng Fan and Wu Wei and Yuwei Wu and Zhipeng Lu and Yunde Jia and Mehrtash Harandi},
  title = {{Geometry-aware Distance Measure for Diverse Hierarchical Structures in Hyperbolic Spaces}},
  year = {2025},
  eprint = {2506.18533},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.18533},
}

Loading related content...

Figure