Elamur Research
☰
home / papers / 2017 / Poincaré Embeddings for Learning Hierarchical Representations

Poincaré Embeddings for Learning Hierarchical Representations

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive licence to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1705.08039v2

Summary

Most embedding methods place symbols such as words, graph nodes or concepts in Euclidean space. That space handles tree-like data poorly: faithfully encoding a deep hierarchy requires many dimensions. Nickel and Kiela (Facebook AI Research) instead embed data in hyperbolic space, specifically the n-dimensional Poincaré ball. There, available volume grows exponentially with distance from the origin, much as the number of nodes in a tree grows with depth. General or root items settle near the center, and specific items drift toward the boundary. One embedding therefore captures both similarity and hierarchy, and no explicit hierarchy labels are needed. Training uses a Riemannian (natural-gradient-style) optimization procedure that parallelizes and scales to large datasets. The authors test the method on WORDNET taxonomy embedding, link prediction in collaboration networks and graded lexical entailment. Poincaré embeddings beat Euclidean ones, most clearly at low dimensionality. The result suggests hyperbolic geometry gives a useful structural bias for compact, hierarchy-aware representations.

Key points

  • Points live in the open unit ball, where distances grow sharply near the edge. Embedding norm thus acts as a proxy for a node's level in the hierarchy.
  • The link prediction experiments use four co-authorship networks:
    • ASTROPH (18,772 nodes / 198,110 edges)
    • CONDMAT (23,133 / 93,497)
    • GRQC (5,242 / 14,496)
    • HEPPH (12,008 / 118,521)
  • In those experiments, edge probability follows a Fermi-Dirac formulation. Results are reported as MAP, and Poincaré embeddings lead mainly in small dimensionalities.
  • On the noun portion of HYPERLEX (2163 rated pairs), 5-dimensional WORDNET embeddings reach Spearman's ρ = 0.512. This compares with 0.389 for Euclidean embeddings and lower scores for prior baselines, even though the embeddings were not trained for this task.
  • The same embeddings achieve 0.86 accuracy on WBLESS, a non-graded lexical entailment benchmark.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: AI & machine learning

Cited by

158 papers of our library cite it (of the 140673 whose bibliographies we read); 2 of them have a page here, 156 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1705.08039 · arXiv 1705.08039

@misc{nickel2017poincare,
  title = {{Poincaré Embeddings for Learning Hierarchical Representations}},
  author = {Nickel, Maximilian and Kiela, Douwe},
  year = {2017},
  doi = {10.48550/arxiv.1705.08039},
  eprint = {1705.08039},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1705.08039}
}

References

35 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aaron B Adcock, Blair D Sullivan, and Michael W Mahoney. Tree-like structure in large social and information networks. In Data Mining (ICDM), 2013 IEEE 13th International Conference on, pages 1–10. IEEE, 2013. find
  2. Shun-ichi Amari. Natural gradient works efficiently in learning. Neural Computation, 10(2): 251–276, 1998. find
  3. M Boguñá, F Papadopoulos, and D Krioukov. Sustaining the internet with hyperbolic mapping. Nature communications, 1:62, 2010. find
  4. Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. arXiv preprint arXiv:1607.04606, 2016. find
  5. Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Trans. Automat. Contr., 58(9):2217–2229, 2013. find
  6. Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26, pages 2787–2795, 2013. find
  7. Guillaume Bouchard, Sameer Singh, and Theo Trouillon. On approximate reasoning capabilities of low-rank vector spaces. AAAI Spring Syposium on Knowledge Representation and Reasoning (KRR): Integrating Symbolic and Neural Approaches, 2015. find
  8. Aaron Clauset, Cristopher Moore, and Mark EJ Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98–101, 2008. find
  9. John Rupert Firth. A synopsis of linguistic theory, 1930-1955. Studies in linguistic analysis, 1957. find
  10. Mikhael Gromov. Hyperbolic groups. In Essays in group theory, pages 75–263. Springer, 1987. find
  11. Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 855–864. ACM, 2016. find
  12. Zellig S Harris. Distributional structure. Word, 10(2-3):146–162, 1954. find
  13. Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460):1090–1098, 2002. find
  14. Douwe Kiela, Laura Rimell, Ivan Vulic, and Stephen Clark. Exploiting image generality for lexical entailment detection. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics (ACL 2015), pages 119–124. ACL, 2015. find
  15. Robert Kleinberg. Geographic routing using hyperbolic space. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pages 1902–1909. IEEE, 2007. find
  16. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010. find
  17. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. CoRR, abs/1310.4546, 2013. find
  18. George Miller and Christiane Fellbaum. Wordnet: An electronic lexical database, 1998. find
  19. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. In Proceedings of the 28th International Conference on Machine Learning, ICML, pages 809–816, 2011. find
  20. Maximilian Nickel, Xueyan Jiang, and Volker Tresp. Reducing the rank in relational factorization models by including observable patterns. In Advances in Neural Information Processing Systems 27, pages 1179–1187, 2014. find
  21. Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowledge graphs. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1955–1961, 2016. find
  22. Alberto Paccanaro and Geoffrey E. Hinton. Learning distributed representations of concepts using linear relational embedding. IEEE Trans. Knowl. Data Eng., 13(2):232–244, 2001. find
  23. Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In EMNLP, volume 14, pages 1532–1543, 2014. find
  24. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014. find
  25. Erzsébet Ravasz and Albert-László Barabási. Hierarchical organization in complex networks. Physical Review E, 67(2):026112, 2003. find
  26. Benjamin Recht, Christopher Ré, Stephen J. Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems 24, pages 693–701, 2011. find
  27. Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin M Marlin. Relation extraction with matrix factorization and universal schemas. In Proceedings of NAACL-HLT, pages 74–84, 2013. find
  28. Mark Steyvers and Joshua B Tenenbaum. The large-scale structure of semantic networks: Statistical analyses and a model of semantic growth. Cognitive science, 29(1):41–78, 2005. find
  29. Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 2071–2080, 2016. find
  30. Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. arXiv preprint arXiv:1511.06361, 2015. find
  31. Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. In International Conference on Learning Representations (ICLR), 2015. find
  32. Ivan Vulić, Daniela Gerz, Douwe Kiela, Felix Hill, and Anna Korhonen. Hyperlex: A large-scale evaluation of graded lexical entailment. arXiv preprint arXiv:1608.02117, 2016. find
  33. Julie Weeds, Daoud Clarke, Jeremy Reffin, David Weir, and Bill Keller. Learning to distinguish hypernyms and co-hyponyms. In Proceedings of the 25th International Conference on Computational Linguistics COLING, pages 2249–2259. Dublin City University and Association for Computational Linguistics, 20… find
  34. Hongyi Zhang, Sashank J. Reddi, and Suvrit Sra. Riemannian SVRG: fast stochastic optimization on riemannian manifolds. In Advances in Neural Information Processing Systems 29, pages 4592–4600, 2016. find
  35. George Kingsley Zipf. Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley, 1949. find