Efficient and Expressive Knowledge Base Completion Using Subgraph Feature Extraction

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1488–1498, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Efficient and Expressive Knowledge Base Completion Using Subgraph Feature Extraction Matt Gardner and Tom Mitchell Carnegie Mellon University mg1@cs.cmu.edu, tom.mitchell@cmu.edu Abstract We explore some of the practicalities of using random walk inference meth- ods, such as the Path Ranking Algorithm (PRA), for the task of knowledge base completion. We show that the random walk probabilities computed (at great ex- pense) by PRA provide no discernible benefit to performance on this task, so they can safely be dropped. This allows us to define a simpler algorithm for gener- ating feature matrices from graphs, which we call subgraph feature extraction (SFE). In addition to being conceptually simpler than PRA, SFE is much more efficient, re- ducing computation by an order of mag- nitude, and more expressive, allowing for much richer features than paths between two nodes in a graph. We show experi- mentally that this technique gives substan- tially better performance than PRA and its variants, improving mean average preci- sion from .432 to .528 on a knowledge base completion task using the NELL KB. 1 Introduction Knowledge bases (KBs), such as Freebase (Bol- lacker et al., 2008), NELL (Mitchell et al., 2015), and DBPedia (Mendes et al., 2012) contain large collections of facts about things, people, and places in the world. These knowledge bases are useful for various tasks, including training rela- tion extractors and semantic parsers (Hoffmann et al., 2011; Krishnamurthy and Mitchell, 2012), and question answering (Berant et al., 2013). While these knowledge bases may be very large, they are still quite incomplete, missing large percentages of facts about common or popular entities (West et al., 2014; Choi et al., 2015). The task of knowl- edge base completion—filling in missing facts by examining the facts already in the KB, or by look- ing in a corpus—is one attempt to mitigate the problems of this knowledge sparsity. In this work we examine one method for performing knowledge base completion that is currently in use: the Path Ranking Algorithm (PRA) (Lao et al., 2011; Dong et al., 2014). PRA is a method for performing link prediction in a graph with labeled edges by computing feature matrices over node pairs in the graph. The method has a strong connection to logical inference (Gard- ner et al., 2015), as the feature space considered by PRA consists of a restricted class of horn clauses found in the graph. While PRA can be applied to any link prediction task in a graph, its primary use has been in KB completion (Lao et al., 2012; Gardner et al., 2013; Gardner et al., 2014). PRA is a two-step process, where the first step finds potential path types between node pairs to use as features in a statistical model, and the sec- ond step computes random walk probabilities as- sociated with each path type and node pair (these are the values in a feature …

Content truncated to 500 words