Estimation of the accuracy of a large-scale knowledge graph (KG) often
requires humans to annotate samples from the graph. How to obtain statistically
meaningful estimates for accuracy evaluation while keeping human annotation
costs low is a problem critical to the development cycle of a KG and its
practical applications. Surprisingly, this challenging problem has largely been
ignored in prior research. To address the problem, this paper proposes an
efficient sampling and evaluation framework, which aims to provide quality
accuracy evaluation with strong statistical guarantee while minimizing human
efforts. Motivated by the properties of the annotation cost function observed
in practice, we propose the use of cluster sampling to reduce the overall cost.
We further apply weighted and two-stage sampling as well as stratification for
better sampling designs. We also extend our framework to enable efficient
incremental evaluation on evolving KG, introducing two solutions based on
stratified sampling and a weighted variant of reservoir sampling. Extensive
experiments on real-world datasets demonstrate the effectiveness and efficiency
of our proposed solution. Compared to baseline approaches, our best solutions
can provide up to 60% cost reduction on static KG evaluation and up to 80% cost
reduction on evolving KG evaluation, without loss of evaluation quality.

通过使用簇抽样、加权和两阶段抽样，以及分层的抽样设计，提出了一种有效的抽样和评估框架，该框架旨在在最小化人力成本的同时提供具有强大统计保证的高质量的准确性评估。