Traversing Knowledge Graphs in Vector Space

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 318–327, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Traversing Knowledge Graphs in Vector Space Kelvin Guu Stanford University kguu@stanford.edu John Miller Stanford University millerjp@stanford.edu Percy Liang Stanford University pliang@cs.stanford.edu Abstract Path queries on a knowledge graph can be used to answer compositional ques- tions such as “What languages are spoken by people living in Lisbon?”. However, knowledge graphs often have missing facts (edges) which disrupts path queries. Re- cent models for knowledge base comple- tion impute missing facts by embedding knowledge graphs in vector spaces. We show that these models can be recursively applied to answer path queries, but that they suffer from cascading errors. This motivates a new “compositional” training objective, which dramatically improves all models’ ability to answer path queries, in some cases more than doubling accuracy. On a standard knowledge base comple- tion task, we also demonstrate that com- positional training acts as a novel form of structural regularization, reliably improv- ing performance across all base models (reducing errors by up to 43%) and achiev- ing new state-of-the-art results. 1 Introduction Broad-coverage knowledge bases such as Free- base (Bollacker et al., 2008) support a rich array of reasoning and question answering applications, but they are known to suffer from incomplete cov- erage (Min et al., 2013). For example, as of May 2015, Freebase has an entity Tad Lincoln (Abra- ham Lincoln’s son), but does not have his ethnic- ity. An elegant solution to incompleteness is using vector space representations: Controlling the di- mensionality of the vector space forces generaliza- tion to new facts (Nickel et al., 2011; Nickel et al., 2012; Socher et al., 2013; Riedel et al., 2013; Nee- lakantan et al., 2015). In the example, we would hope to infer Tad’s ethnicity from the ethnicity of his parents. Figure 1: We propose performing path queries such as tad lincoln/parents/location (“Where are Tad Lincoln’s parents located?”) in a parallel low-dimensional vector space. Here, entity sets (boxed) are represented as real vectors, and edge traversal is driven by vector-to-vector transforma- tions (e.g., matrix multiplication). However, what is missing from these vector space models is the original strength of knowledge bases: the ability to support compositional queries (Ullman, 1985). For example, we might ask what the ethnicity of Abraham Lincoln’s daugh- ter would be. This can be formulated as a path query on the knowledge graph, and we would like a method that can answer this efficiently, while generalizing over missing facts and even missing or hypothetical entities (Abraham Lincoln did not in fact have a daughter). In this paper, we present a scheme to answer path queries on knowledge bases by “composi- tionalizing” a broad class of vector space mod- els that have been used for knowledge base com- pletion (see Figure 1). At a high level, we inter- pret the base vector space model as implementing a soft edge traversal operator. This operator can then be recursively applied to predict …

Content truncated to 500 words