Automatic construction of large knowledge graphs (KG) by mining web-scale text datasets has received considerable attention 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 approximation algorithm.Through experiments on real-world datasets, we demonstrate that KGEval best estimates KG accuracy compared to other baselines, while requiring significantly lesser number of human evaluations.

Crowdsourcing is increasingly being used to solve complex tasks that require contributions from groups of individuals. In this paper, we consider the problem of distinguishing workers from idlers (who do not contribute positively) in group-based tasks. We consider a group as our smallest observable unit that can be evaluated and assume no knowledge of individual participant’s contribution. We propose the use of group testing based methods for estimating quality of an individual, based on the performance of teams they have been part of. We further extend these algorithms to identify subsets of workers and give theoretical analysis on size of these subsets. We account for several real-world constraints in our model and present empirical support to our theoretical guarantees by an array of simulation experiments.