# Strain-Minimizing Hyperbolic Network Embeddings with Landmarks

arXiv: https://arxiv.org/abs/2207.06775 · HTML: https://mlsanity.com/paper/2207.06775/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 6 of 6)

- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space](https://mlsanity.com/paper/1602.06522/) (2016)
- [Hydra: A method for strain-minimizing hyperbolic embedding of network- and distance-based data](https://mlsanity.com/paper/1903.08977/) (2019)
- [Systematic comparison of graph embedding methods in practical tasks](https://mlsanity.com/paper/2106.10198/) (2021)
- [Hyperbolic Distance Matrices](https://mlsanity.com/paper/2005.08672/) (2020)

## Built on by (most cited first, 1 of 1)

- [Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts](https://mlsanity.com/paper/2402.03460/) (2024)

## Abstract (arXiv)

We introduce L-hydra (landmarked hyperbolic distance recovery and approximation), a method for embedding network- or distance-based data into hyperbolic space, which requires only the distance measurements to a few 'landmark nodes'. This landmark heuristic makes L-hydra applicable to large-scale graphs and improves upon previously introduced methods. As a mathematical justification, we show that a point configuration in d-dimensional hyperbolic space can be perfectly recovered (up to isometry) from distance measurements to just d+1 landmarks. We also show that L-hydra solves a two-stage strain-minimization problem, similar to our previous (unlandmarked) method 'hydra'. Testing on real network data, we show that L-hydra is an order of magnitude faster than existing hyperbolic embedding methods and scales linearly in the number of nodes. While the embedding error of L-hydra is higher than the error of existing methods, we introduce an extension, L-hydra+, which outperforms existing methods in both runtime and embedding quality.