Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4752–4765 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 4752 Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion Rajarshi Das, Ameya Godbole, Nicholas Monath, Manzil Zaheer, Andrew McCallum University of Massachusetts, Amherst, USA Google Research, USA {rajarshi, agodbole, nmonath, mccallum}@cs.umass.edu manzilzaheer@google.com Abstract A case-based reasoning (CBR) system solves a new problem by retrieving ‘cases’ that are sim- ilar to the given problem. If such a system can achieve high accuracy, it is appealing owing to its simplicity, interpretability, and scalability. In this paper, we demonstrate that such a sys- tem is achievable for reasoning in knowledge- bases (KBs). Our approach predicts attributes for an entity by gathering reasoning paths from similar entities in the KB. Our proba- bilistic model estimates the likelihood that a path is effective at answering a query about the given entity. The parameters of our model can be efficiently computed using simple path statistics and require no iterative optimization. Our model is non-parametric, growing dynam- ically as new entities and relations are added to the KB. On several benchmark datasets our approach significantly outperforms other rule learning approaches and performs compa- rably to state-of-the-art embedding-based ap- proaches. Furthermore, we demonstrate the ef- fectiveness of our model in an “open-world” setting where new entities arrive in an online fashion, significantly outperforming state-of- the-art approaches and nearly matching the best offline method.1 1 Introduction We live in an evolving world with a lot of het- erogeneity as well as new entities being created continuously. For example, scientific papers and Wikipedia pages describing facts about new enti- ties, are being constantly added (e.g. COVID-19). These new findings further trigger the inference of newer facts, each with its own diverse reasoning. We are interested in developing such automated rea- soning systems for large knowledge-bases (KBs). In machine learning, non-parametric methods hold the promise of handling evolving data (Cover 1Code available at https://github.com/ ameyagodbole/Prob-CBR and Hart, 1967; Rasmussen, 2000). Most current KG completion models learn low dimensional parametric representation of entities and relations via tensor factorization or sophisticated neural ap- proaches (Nickel et al., 2011; Bordes et al., 2013; Socher et al., 2013; Sun et al., 2019; Vashishth et al., 2020). Another line of work learns Horn- clause style reasoning rules from the KG and stores them in its parameters (Rockt¨aschel and Riedel, 2017; Das et al., 2018; Minervini et al., 2020). However, these parametric approaches work with a fixed set of entities and it is unclear how these models will adapt to new entities. This paper presents a k-nearest neighbor (KNN) based approach for KG reasoning that is reminis- cent of case-based reasoning (CBR) in classical AI. A CBR system solves a new problem by re- trieving ‘cases’ that are similar to the given prob- lem, revising the solution to retrieved cases (if necessary) and reusing it for the new problem (Schank, 1982; Leake, 1996, inter-alia). For the task of finding a target entity given a source entity …

Content truncated to 500 words