Elamur Research⌕
☰
home / papers / 2015 / Modeling Relation Paths for Representation Learning of Knowledge Bases

Modeling Relation Paths for Representation Learning of Knowledge Bases

Summary

Knowledge bases such as Freebase are large but far from complete. Translation-based embedding models like TransE learn vectors for entities and relations, but they only look at direct links between two entities. This paper introduces PTransE, which also learns from multi-step relation paths. A path such as BornInCity → CityInState → StateInCountry hints at Nationality, so PTransE treats the whole path as a translation between head and tail. Two problems are addressed. First, many paths are noisy, so a path-constraint resource allocation (PCRA) algorithm scores how reliable each path is for a given entity pair. Second, a path needs its own vector, so it is built by composing relation embeddings with addition, multiplication or an RNN. The model is trained with margin-based losses and SGD on datasets built from Freebase. Its evaluation spans three tasks (predicting missing entities, predicting missing relations, and extracting relations from textual data), and on each of them it consistently outperforms TransE and other baselines. The work shows that graph structure beyond single edges can make embeddings more useful for completing KBs.

Key points

  • PTransE extends TransE (h + r ≈ t). Its energy adds a reliability-weighted, normalized sum of path energies to the usual direct-triple energy.
  • PCRA scores a path by sending one unit of "resource" from the head entity along the path. At each step the resource is split evenly among successors, and whatever reaches the tail becomes the path's reliability.
  • Three path composition operators are compared: ADD (sum of relation vectors), MUL (element-wise cumulative product) and RNN (c_i = f(W[c_{i-1}; r_i])).
  • The path energy is ||p − r||, which compares the composed path directly with the direct relation, without entity vectors. Training uses margin losses with negative sampling, SGD and norm constraints on embeddings.
  • Evaluation uses three Freebase-based tasks: predicting missing entities, predicting missing relations, and pulling relations out of textual data. Code is released at github.com/mrlyk423/relation_extraction.

Interesting ideas

  • I1. Flow-based reliability scoring for paths: sending a unit of mass along typed edges and measuring what reaches the target is a cheap, training-free way to discount ambiguous, high-fan-out paths. The same trick could filter noisy multi-hop connections in any typed graph, such as trade-partner or geographic adjacency networks.
  • I2. Path energy without entities: once direct triples have pushed r toward t − h, the paper compares the composed path vector with r alone. Comparing composed structure to a single target vector this way could carry over to other compositional settings where the endpoint representations are noisy.
  • I3. Pluggable composition operators: testing ADD, MUL and RNN side by side gives a clean ablation of how much composition complexity is actually needed. It is a useful template when deciding how to represent sequences of relations or morphemes.
  • I4. Multi-path evidence for inference: the Forrest Gump → English example shows that several independent paths pointing to the same relation strengthen a prediction. This suggests aggregating path evidence as a simple confidence signal when proposing new KB facts.
  • I5. Honest scope limits: the authors note that unary implications such as Queen(e) ⇒ Female(e) are out of reach and point to first-order logic as a next step. This is a reminder to check which inference pattern types an embedding model can express before relying on it.

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: Natural language processing

Topics: Knowledge graphs & ontologies

Institutions

🎓Tsinghua UniversityBeijing · China92 works · 77 045 citations🔬State Key Laboratory of Intelligent Technology and SystemsBeijing14 works · 8 004 citations🏢SamsungSeoul · South Korea2 works · 1 050 citations

Also on the byline: Samsung (China).

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d15-1082

@inproceedings{lin2015modeling,
  title = {{Modeling Relation Paths for Representation Learning of Knowledge Bases}},
  author = {Lin, Yankai and Liu, Zhiyuan and Luan, Huanbo and Sun, Maosong and Rao, Siwei and Liu, Song},
  booktitle = {Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  doi = {10.18653/v1/d15-1082},
  url = {https://doi.org/10.18653/v1/d15-1082}
}

References

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

  1. Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of KDD, pages 1247–1250. find
  2. Antoine Bordes, Jason Weston, Ronan Collobert, Yoshua Bengio, et al. 2011. Learning structured embeddings of knowledge bases. In Proceedings of AAAI, pages 301–306. find
  3. Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. 2012. Joint learning of words and meaning representations for open-text semantic parsing. In Proceedings of AISTATS, pages 127– 135. find
  4. Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi-relational data. In Proceedings of NIPS, pages 2787–2795. find
  5. Antoine Bordes, Xavier Glorot, Jason Weston, and Yoshua Bengio. 2014. A semantic matching energy function for learning with multi-relational data. Machine Learning, 94(2):233–259. find
  6. Danqi Chen, Richard Socher, Christopher D Manning, and Andrew Y Ng. 2013. Learning new facts from knowledge bases with neural tensor networks and semantic word vectors. Proceedings of ICLR. find
  7. Matt Gardner, Partha Pratim Talukdar, Bryan Kisiel, and Tom M Mitchell. 2013. Improving learning and inference in a large knowledge-base using latent syntactic cues. In Proceedings of EMNLP, pages 833–838. find
  8. Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke Zettlemoyer, and Daniel S Weld. 2011. Knowledge-based weak supervision for information extraction of overlapping relations. In Proceedings of ACL-HLT, pages 541–550. find
  9. Rodolphe Jenatton, Nicolas L Roux, Antoine Bordes, and Guillaume R Obozinski. 2012. A latent factor model for highly multi-relational data. In Proceedings of NIPS, pages 3167–3175. find
  10. Charles Kemp, Joshua B Tenenbaum, Thomas L Griffiths, Takeshi Yamada, and Naonori Ueda. 2006. Learning systems of concepts with an infinite relational model. In Proceedings of AAAI, volume 3, page 5. find
  11. Ni Lao and William W Cohen. 2010. Relational retrieval using a combination of path-constrained random walks. Machine learning, 81(1):53–67. find
  12. Ni Lao, Tom Mitchell, and William W Cohen. 2011. Random walk inference and learning in a large scale knowledge base. In Proceedings of EMNLP, pages 529–539. find
  13. Ni Lao, Amarnag Subramanya, Fernando Pereira, and William W Cohen. 2012. Reading the web with learned syntactic-semantic inference rules. In Proceedings of EMNLP-CoNLL, pages 1017–1026. find
  14. Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015. Learning entity and relation embeddings for knowledge graph completion. In Proceedings of AAAI, pages 2181–2187. find
  15. Linyuan Lü and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 390(6):1150–1170. find
  16. Tomas Mikolov, Martin Karafiát, Lukas Burget, Jan Cernockỳ, and Sanjeev Khudanpur. 2010. Recurrent neural network based language model. In Proceedings of Interspeech, pages 1045–1048. find
  17. Kurt Miller, Michael I Jordan, and Thomas L Griffiths. 2009. Nonparametric latent feature models for link prediction. In Proceedings of NIPS, pages 1276– 1284. find
  18. Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. 2009. Distant supervision for relation extraction without labeled data. In Proceedings of ACL-IJCNLP, pages 1003–1011. find
  19. Jeff Mitchell and Mirella Lapata. 2008. Vector-based models of semantic composition. In Proceedings of ACL, pages 236–244. find
  20. Arvind Neelakantan, Benjamin Roth, and Andrew Mc-Callum. 2015. Compositional vector space models for knowledge base inference. In 2015 AAAI Spring Symposium Series. find
  21. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2011. A three-way model for collective learning on multi-relational data. In Proceedings of ICML, pages 809–816. find
  22. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. 2012. Factorizing yago: scalable machine learning for linked data. In Proceedings of WWW, pages 271–280. find
  23. Sebastian Riedel, Limin Yao, and Andrew McCallum. 2010. Modeling relations and their mentions without labeled text. In Proceedings of ECML-PKDD, pages 148–163. find
  24. Ajit P Singh and Geoffrey J Gordon. 2008. Relational learning via collective matrix factorization. In Proceedings of KDD, pages 650–658. find
  25. Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. 2013. Reasoning with neural tensor networks for knowledge base completion. In Proceedings of NIPS, pages 926–934. find our card
  26. Mihai Surdeanu, Julie Tibshirani, Ramesh Nallapati, and Christopher D Manning. 2012. Multi-instance multi-label learning for relation extraction. In Proceedings of EMNLP, pages 455–465. find
  27. Ilya Sutskever, Joshua B Tenenbaum, and Ruslan Salakhutdinov. 2009. Modelling relational data using bayesian clustered tensor factorization. In Proceedings of NIPS, pages 1821–1828. find
  28. Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006. Fast random walk with restart and its applications. In Proceedings of ICDM, pages 613–622. find
  29. Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014. Knowledge graph embedding by translating on hyperplanes. In Proceedings of AAAI, pages 1112–1119. find
  30. Jason Weston, Antoine Bordes, Oksana Yakhnenko, and Nicolas Usunier. 2013. Connecting language and knowledge bases with embedding models for relation extraction. In Proceedings of EMNLP, pages 1366–1371. find
  31. Tao Zhou, Jie Ren, Matúš Medo, and Yi-Cheng Zhang. 2007. Bipartite network projection and personal recommendation. Physical Review E, 76(4):046115. find
  32. Jun Zhu. 2012. Max-margin nonparametric latent feature models for link prediction. In Proceedings of ICML, pages 719–726. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lin-2015-modeling-relation-paths-representation-learning/