Timezone: »

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

Thu Jul 12 08:00 AM -- 08:20 AM (PDT) @ K11
in Dimensionality Reduction 2 »

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.

[ PDF]  [ Video] 

Author Information

Frederic 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