KGEval: Accuracy Estimation of Automatically Constructed Knowledge Graphs

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1741–1750 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics KGEval: Accuracy Estimation of Automatically Constructed Knowledge Graphs Prakhar Ojha Indian Institute of Science prakhar@iisc.ac.in Partha Talukdar Indian Institute of Science ppt@iisc.ac.in Abstract Automatic construction of large knowl- edge graphs (KG) by mining web-scale text datasets has received considerable at- tention recently. Estimating accuracy of such automatically constructed KGs is a challenging problem due to their size and diversity and has largely been ignored in prior research. In this work, we try to fill this gap by proposing KGEval. KGEval uses coupling constraints to bind facts and crowdsource those few that can infer large parts of the graph. We demonstrate that the objective optimized by KGEval is submodular and NP-hard, allowing guarantees for our approxima- tion algorithm. Through experiments on real-world datasets, we demonstrate that KGEval best estimates KG accuracy com- pared to other baselines, while requiring significantly lesser number of human eval- uations. 1 Introduction Automatic construction of Knowledge Graphs (KGs) from Web documents has received signif- icant interest over the last few years, resulting in the development of several large KGs consist- ing of hundreds of predicates (e.g., isCity, sta- diumLocatedInCity(Stadium, City)) and millions of their instances called beliefs (e.g., (Joe Luis Arena, stadiumLocatedInCity, Detroit)). Exam- ples of such KGs include NELL (Mitchell et al., 2015), Knowledge-Vault (Dong et al., 2014) etc. Due to imperfections in the automatic KG con- struction process, many incorrect beliefs are also found in these KGs. Knowing accuracy for each predicate in the KG can provide targeted feedback for improvement and highlight its strengths from weaknesses, whereas overall accuracy of a KG can quantify the effectiveness of its construction- process. Knowing accuracy at predicate-level granularity is immensely helpful for Question- Answering (QA) systems that integrate opinions from multiple KGs (Samadi et al., 2015). For such systems, being aware that a particular KG is more accurate than others in a certain domain, say sports, helps in restricting the search over relevant and accurate subsets of KGs, thereby improving QA-precision and response time. In comparison to the large body of recent work focused on con- struction of KGs, the important problem of accu- racy estimation of such large KGs is unexplored – we address this gap in this paper. True accuracy of a predicate may be estimated by aggregating human judgments on correctness of each and every belief in the predicate1. Even though crowdsourcing marketplaces such as Ama- zon Mechanical Turk (AMT) provide a convenient way to collect human judgments, accumulating such judgments at the scale of larges KGs is pro- hibitively expensive. We shall refer to the task of manually classifying a single belief as true or false as a Belief Evaluation Task (BET). Thus, the crucial problem is: How can we select a subset of beliefs to evaluate which will best estimate the true (but unknown) accuracy of KG and its predi- cates? A naive and popular approach is …

Content truncated to 500 words