Elamur Research⌕
☰
home / papers / 2020 / Low-Dimensional Hyperbolic Knowledge Graph Embeddings

Low-Dimensional Hyperbolic Knowledge Graph Embeddings

Paper · 2020 · Ines Chami, Adva Wolf, Da-Cheng Juan et al.

Summary

Knowledge graphs (KGs) are typically incomplete, so missing links are often predicted with entity and relation embeddings. KGs mix tree-like hierarchies with logical relation patterns such as symmetry, anti-symmetry and inversion. Euclidean and complex-space models usually need very high dimensions, which is costly in memory. The earlier hyperbolic model MuRP handles hierarchies but cannot express many of these logical patterns.

The authors propose a family of hyperbolic models (RefH, RotH and AttH) built in the Poincaré ball, with a separately learned curvature for each relation. Relations act as hyperbolic isometries made from Givens reflections and rotations. AttH uses hyperbolic attention to blend the two transformations. Training happens in tangent space, so Riemannian optimization is unnecessary.

Evaluated on WN18RR, FB15k-237 and YAGO3-10, the method clearly beats Euclidean and hyperbolic baselines at 32 dimensions. At high dimensions, the model family sets new state-of-the-art results. This matters because compact embeddings that preserve hierarchy make link prediction on large KGs cheaper.

Key points

  • At 32 dimensions, MRR rises by up to 6.1% over previous Euclidean and hyperbolic methods. Hierarchical WordNet relations (hypernym, member meronym) gain 16–24% relative to Euclidean baselines.
  • Reflections tend to model symmetric relations, while rotations capture anti-symmetric ones. AttH's attention learns to select the appropriate operator for each relation.
  • At high dimensions (up to 500), the family reaches new SotA MRR scores of 49.6% on WN18RR (RotH) and 57.7% on YAGO3-10.
  • Trainable curvature is essential: learned curvatures shrink toward zero as dimension grows. With fixed curvature, embeddings crowd near the ball boundary and performance drops, which may explain MuRP's weakness at high dimensions.
  • Visualizations of a WN18RR sub-tree show that RotH preserves the hierarchy, whereas the Euclidean RotE does not.

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

 Institutions

🏢GoogleMountain View · United States353 works · 364,806 citations🎓Stanford UniversityStanford · United States310 works · 284,480 citations🏢AmazonSeattle · United States70 works · 39,977 citations

📚 Shelves 5 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works Information Systems · 523 works

🧭 Topics 1 Knowledge graphs & ontologies · 103 works

Cite

Cite as Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi and Christopher Ré. 2020. Low-Dimensional Hyperbolic Knowledge Graph Embeddings. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.acl-main.617

@inproceedings{chami2020low,
  title = {{Low-Dimensional Hyperbolic Knowledge Graph Embeddings}},
  author = {Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi and Christopher Ré},
  booktitle = {Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.617},
  url = {https://doi.org/10.18653/v1/2020.acl-main.617}
}

References

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

  1. Ivana Balažević, Carl Allen, and Timothy Hospedales. 2019. Multi-relational poincaré graph embeddings. In Advances in Neural Information Processing Systems, pages 4465–4475. find
  2. Ivana Balazevic, Carl Allen, and Timothy Hospedales. 2019. Tucker: Tensor factorization for knowledge graph completion. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),… our card
  3. Trapit Bansal, Da-Cheng Juan, Sujith Ravi, and Andrew McCallum. 2019. A2n: Attending to neighbors for knowledge graph inference. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4387–4392. find
  4. Silvere Bonnabel. 2013. Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217–2229. find
  5. Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, pages 2787–2795. find
  6. Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. 2019. Hyperbolic graph convolutional neural networks. In Advances in Neural Information Processing Systems, pages 4869–4880. find
  7. Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. 2018. Convolutional 2D knowledge graph embeddings. In Thirty-Second AAAI Conference on Artificial Intelligence. find
  8. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul):2121–2159. find
  9. Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. 2018. Hyperbolic neural networks. In Advances in Neural Information Processing Systems. find
  10. Albert Gu, Fred Sala, Beliz Gunel, and Christopher Ré. 2019. Learning mixed-curvature representations in product spaces. In International Conference on Learning Representations. find
  11. Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao. 2015. Knowledge graph embedding via dynamic mapping matrix. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long… our card
  12. Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In International Conference for Learning Representations. find
  13. David Krackhardt. 1994. Graph theoretical dimensions of informal organizations. In Computational organization theory, pages 107–130. Psychology Press. find
  14. Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. 2018. Canonical tensor decomposition for knowledge base completion. International Conference on Machine Learning. find
  15. Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015. Learning entity and relation embeddings for knowledge graph completion. In Twenty-ninth AAAI Conference on Artificial Intelligence. find
  16. Qi Liu, Maximilian Nickel, and Douwe Kiela. 2019. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems, pages 8228–8239. find
  17. Farzaneh Mahdisoltani, Joanna Biega, and Fabian M Suchanek. 2013. Yago3: A knowledge base from multilingual wikipedias. our card
  18. George A Miller. 1995. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39– 41. our card
  19. Deepak Nathani, Jatin Chauhan, Charu Sharma, and Manohar Kaul. 2019. Learning attention-based embeddings for relation prediction in knowledge graphs. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics. our card
  20. Dai Quoc Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Phung. 2018. A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network. In Proceedings of the 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Lang… our card
  21. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011. A three-way model for collective learning on multi-relational data. In International Conference on Machine Learning, pages 809–816. Omnipress. find
  22. Maximillian Nickel and Douwe Kiela. 2017. Poincaré embeddings for learning hierarchical representations. In Advances in Neural Information Processing Systems, pages 6338–6347. our card
  23. Joel W Robbin and Dietmar A Salamon. Introduction to differential geometry. Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. 2018. Representation tradeoffs for hyperbolic embeddings. In International Conference on Machine Learning, pages 4457–4466. find
  24. Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pages 593–607. Springer. find
  25. Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007. Yago: a core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pages 697–706. ACM. find
  26. Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations. find
  27. Alexandru Tifrea, Gary Bécigneul, and Octavian-Eugen Ganea. 2019. Poincaré GloVe: Hyperbolic word embeddings. In International Conference on Learning Representations. find
  28. Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, pages 57–66. our card
  29. Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016. Complex embeddings for simple link prediction. In International Conference on Machine Learning, pages 2071–2080. find
  30. Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014. Knowledge graph embedding by translating on hyperplanes. In Twenty-Eighth AAAI Conference on Artificial Intelligence. find
  31. Canran Xu and Ruijiang Li. 2019. Relation embedding with dihedral group in knowledge graph. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics. find
  32. Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015. Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Representations. our card
  33. Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. 2019. Quaternion knowledge graph embeddings. In Advances in Neural Information Processing Systems, pages 2731–2741. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/chami-2020-low-dimensional-hyperbolic-knowledge-graph/