Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion (2020)

Abstract: A case-based reasoning (CBR) system solves a new problem by retrieving ‘cases’ that are similar 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 system 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 probabilistic 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 dynamically as new entities and relations are added to the KB. On several benchmark datasets our approach significantly outperforms other rule learning approaches and performs comparably to state-of-the-art embedding-based approaches. Furthermore, we demonstrate the effectiveness 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.

## introduction we live in an evolving world with a lot of heterogeneity as well as new entities being created continuously. for example, scientific papers and wikipedia pages describing facts about new entities, 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 reasoning systems for large knowledge-bases (kbs). in machine learning, non-parametric methods hold the promise of handling evolving data @xcite . most current kg completion models learn low dimensional parametric representation of entities and relations via tensor factorization or sophisticated neural approaches @xcite @xcite @xcite . another line of work learns hornclause style reasoning rules from the kg and stores them in its parameters @xcite @xcite . 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 reminiscent of case-based reasoning (cbr) in classical ai. a cbr system solves a new problem by retrieving 'cases' that are similar to the given problem, revising the solution to retrieved cases (if necessary) and reusing it for the new problem @xcite . for the task of finding a target entity given a source entity and binary kg relation (e.g. (john von neu-man, place of death, ?) in figure 1 ), our approach first retrieves k similar entities (cases) to the query entity. next, for each retrieved entity, it finds multiple kg paths foot_1 (each path is a solution to retrieved cases) to the entity they are connected by the query relation (e.g. paths between (richard feynman, usa)). however, one solution seldom works for all queries. for example, even though the path 'born in' is predictive of 'place of death' for us-born scientists (figure 1 ), it does not work for scientists who have immigrated to usa. to handle this, we present a probabilistic cbr approach which learns to weighs paths with respect to an estimate of its prior and its precision, given the query. the prior of a path represents its frequency while the precision represents the likelihood that the path will lead to a correct answer entity. to obtain robust estimates of the path parameters, we cluster similar entities together and compute them by simple count statistics ( §2.2.3). apart from computing these estimates, our method needs no further training. overall, our simple approach outperforms several recent parametric rule learning methods @xcite and performs competitively with various state-of-the-art kg completion approaches @xcite on multiple datasets. an advantage of non-parametric models is that it can adapt to growing data by adjusting its number of parameters. in the same spirit, we show that our model can seamlessly handle an 'open-world' setting in which new entities arrive in the kg. this is made possible by several design choices such as (a) representing entities as sparse (non-learned) vector of its relation types ( §2.2.1), (b) our use of an online non-parametric hierarchical clustering algorithm @xcite that can efficiently recompute changes in cluster assignments because of the newly added entity ( §2.3), (c) and a simple and efficient way of recomputing the prior and precision parameters for paths per cluster ( §2.2.3). current models for kg completion that learn entity representations for a fixed set of entities cannot handle the open-world setting. in fact we show that, retraining the models continually with new data leads to severe degradation of the model performance with models forgetting what it had learned before. for example, the performance (mrr) of rotate model @xcite drops by 11 points (absolute) on wn18rr in this setting ( §3.4). on the other hand, we show that with new data, the performance of our model is consistent as it is able to seamlessly reason with the newly arrived data. our work is most closely related to a recent concurrent work by @xcite where they propose a model that gathers paths from entities similar to the query entity. however, @xcite encourages path that occur frequently in the kg and does not learn to weigh paths differently for queries. this often leads to wrong inference leading to low performance. for example, on the test-ii evaluation subset of fb122 where all triples can be inferred by logical rules, @xcite scores quite low (63 mrr) because of learning incorrect rules. on the other hand, we score significantly higher (94.83 mrr) demonstrating that we can learn more effective rules. in fact, we consistently and significantly outperform @xcite on several benchmark datasets. also, unlike us, they do not test themselves in the challenging open-world setting. the contributions of this paper are as follows: (a) we present a knn based approach for kg completion that gathers reasoning paths from entities that are similar to the query entity. following a principled probabilistic approach ( §2.2), our model weighs each path by its likelihood of reaching a correct answer which penalizes paths that are spurious in nature. (b) the parameters of our model grow with data and can be estimated efficiently using simple count statistics ( §2.3). apart from this, our approach needs no training. we show that our simple approach significantly outperforms various rule learning methods @xcite @xcite on many benchmark datasets. (c) we also show that our model can easily handle addition of facts about new entities and is able to seamlessly integrate and reason with the newly added data significantly outperforming parametric embedding based models. and @xmath0. also, following previous approaches @xcite , we add the inverse relation of every edge, i.e., for an fact (e 1 , r, e 2 ) ∈ e, we add the edge (e 2 , r -1 , e 1 ) to the graph. (if the set of binary relations r does not contain the inverse relation r -1 , it is added to r as well). task: we consider the task of query answering on kgs, i.e., answering questions of the form (e 1q , r q , ?), where answer is an entity in the kg. ## experiments in this section, we evaluate our proposed approach on a wide array of knowledge-base completion (kbc) benchmarks ( §3.3). to evaluate the nonparametric nature of our approach, we also evaluate on an 'open-world' setting ( §2.3) in which new entities are added to the kg. we demonstrate our proposed approach is competitive to several stateof-the-art methods on benchmarks in the standard setting, but it greatly outperforms other methods in the online setting ( §3.4). the best hyper-parameters for all experiments including the range of hyperparameter tried and results on validation set are noted in §a.6. ## conclusion we present a simple yet accurate approach for probabilistic case-based reasoning in knowledge bases. our method is non-parametric, deriving reasoning rules dynamically from similar entities in the kb and is capable of handling new entities. we cluster similar entities together and estimate per-cluster parameters that measures the prior and precision of paths using simple count statistics. our simple approach performs competitively to the best embeddings based models on several benchmarks and outperforms all models in the open-world setting. algorithm 1 select a flat clustering from a tree structure. threshold 2: output: c 1 ,c 2 , . . . ,c k : a flat partition 3: f rontier ← [root] 4: result ← {} 5: while f rontier is not empty do 6: n ← f rontier.pop() 7: if linkage(n) > τ then 8: result ← {n} ∪ result 9: else 10: for c in n.children do 11: f rontier.push(c) 12: end for 13: end if 14: end while 15: return result