Oral
Representation Tradeoffs for Hyperbolic Embeddings
Frederic Sala · Christopher De Sa · Albert Gu · Christopher Re

Thu Jul 12th 05:00 -- 05:20 PM @ K11

Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures. We give a combinatorial construction that embeds trees into hyperbolic space with arbitrarily low distortion without optimization. On WordNet, this algorithm obtains a mean-average-precision of 0.989 with only two dimensions, outperforming existing work by 0.11 points. We provide bounds characterizing 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 enables us to reduce dimensionality. Finally, we extract lessons from the algorithms and theory above to design a scalable PyTorch-based implementation that can handle incomplete information.

Author Information

Fred Sala (Stanford)
Christopher De Sa (Cornell)
Albert Gu (Stanford University)
Christopher Re (Stanford)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors