ComputingComputer ScienceComputational LinguisticsData StructuresGeometryDimension ReductionDimensionality ReductionHyperbolic GeometryMetric GeometryMetric LearningWord EmbeddingsBenchmark DatasetsHierarchical StructuresHyperbolic Word EmbeddingsLow-dimensional EmbeddingsLower BoundsMetric EmbeddingsMultidimensional Scaling
Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures like synonym or type hierarchies. Given a tree, we give a combinatorial construction that embeds the tree in hyperbolic space with arbitrarily low distortion without using optimization. On WordNet, our combinatorial embedding obtains a mean-average-precision of 0.989 with only two dimensions, while Nickel et al.'s recent construction obtains 0.87 using 200 dimensions. We provide upper and lower bounds that allow us to characterize the precision-dimensionality tradeoff inherent in any hyperbolic embedding. To embed general metric spaces, we propose a hyperbolic generalization of multidimensional scaling (h-MDS). We show how to perform exact recovery of hyperbolic points from distances, provide a perturbation analysis, and give a recovery result that allows us to reduce dimensionality. The h-MDS approach offers consistently low distortion even with few dimensions across several datasets. Finally, we extract lessons from the algorithms and theory above to design a PyTorch-based implementation that can handle incomplete information and is scalable.
5
K.-I. Goh, Michael E. Cusick, David Valle et al. · Proceedings of the National Academy of Sciences · 2007 · 3.2K citations · Full text
Hyperbolic geometry of complex networks
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak et al. · Physical Review E · 2010 · 1.1K citations · Full text
Curvature and temperature of complex networks
Dmitri Krioukov, Fragkiskos Papadopoulos, Amin Vahdat et al. · Physical Review E · 2009 · 127 citations · Full text
Computing, Computer Science, Physics +17