Strain-minimizing hyperbolic network embeddings with landmarks

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

Abstract

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 the 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 the existing methods, we introduce an extension, L-hydra+, which outperforms the existing methods in both runtime and embedding quality.

Details

OriginalspracheEnglisch
Aufsatznummercnad002
FachzeitschriftJournal of complex networks
Jahrgang11
Ausgabenummer1
PublikationsstatusVeröffentlicht - 1 Feb. 2023
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0003-0913-3363/work/166762751

Schlagworte

Schlagwörter

  • dimensionality reduction, hyperbolic embedding, hyperbolic geometry, landmark embedding, network embedding

Bibliotheksschlagworte