A Non-commutative Bilinear Model for Answering Path Queries in Knowledge Graphs

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 2422–2430, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 2422 A Non-commutative Bilinear Model for Answering Path Queries in Knowledge Graphs Katsuhiko Hayashi †,∗ katsuhiko-h@sanken.osaka-u.ac.jp Masashi Shimbo ‡,∗ shimbo@is.naist.jp †Osaka University Suita, Osaka, Japan ‡NAIST Ikoma, Nara, Japan ∗Riken AIP Chuo-ku, Tokyo, Japan Abstract Bilinear diagonal models for knowledge graph embedding (KGE), such as DistMult and Com- plEx, balance expressiveness and computa- tional efficiency by representing relations as di- agonal matrices. Although they perform well in predicting atomic relations, composite rela- tions (relation paths) cannot be modeled nat- urally by the product of relation matrices, as the product of diagonal matrices is commuta- tive and hence invariant with the order of rela- tions. In this paper, we propose a new bilin- ear KGE model, called BlockHolE, based on block circulant matrices. In BlockHolE, rela- tion matrices can be non-commutative, allow- ing composite relations to be modeled by ma- trix product. The model is parameterized in a way that covers a spectrum ranging from diag- onal to full relation matrices. A fast compu- tation technique is developed on the basis of the duality of the Fourier transform of circu- lant matrices. 1 Introduction Large-scale knowledge graphs (Nickel et al., 2016a) are indispensable resources for knowledge- intensive applications such as question answering, dialog systems, and distantly supervised relation extraction. A knowledge graph is a collection of triplets (s, r, o) representing the fact that (binary) relation r holds between subject entity s and object entity o. Although efforts continue to enrich exist- ing knowledge graphs with more facts, many facts are still missing (Nickel et al., 2016a). Knowledge graph completion (KGC) aims to automatically detect missing facts in an incomplete knowledge graph, and has become an active field of research in recent years. Knowledge graph embedding (KGE) is a promis- ing approach to KGC. It embeds entities and rela- tions in vector space, and defines a scoring function William Harry Charles . . . Elizabeth Andrew Beatrice Eugenie . . . (a) motherOf motherOf motherOf motherOf fatherOf−1 fatherOf fatherOf fatherOf fatherOf brotherOf brotherOf fatherOf−1 William (b) fatherOf−1 brotherOf fatherOf William (c) brotherOf fatherOf−1 fatherOf Figure 1: (a) A knowledge graph and (b,c) two relation paths starting from William. φ(s, r, o) to evaluate the degree of factuality of a given triplet (s, r, o) in terms of vector operations. Bilinear KGE models are a popular choice for a scoring function, along with those based on transla- tion and neural networks. RESCAL (Nickel et al., 2011) adopts a generic bilinear form as the scor- ing function, given by φRESCAL(s, r, o) = eT s Rreo. In this formula, es, eo are the n-dimensional vec- tor embeddings of entities s and o, respectively, and Rr is the n × n matrix embedding of rela- tion r. Some of the more recent models have constrained the relation matrices to …

Content truncated to 500 words