Unifying Knowledge Base Completion with PU Learning to Mitigate the Observation Bias

Jonas Schouterden, Jessa Bekker, Jesse Davis, Hendrik Blockeel

Introduction

Knowledge Bases (KBs) such as Wikidata and YAGO serve as critical backbones for modern AI, yet they are inherently incomplete and subject to significant observation bias. We are far more likely to find recorded facts about prominent figures or specific geographic regions than about less visible entities. Traditional rule-based Knowledge Base Completion (KBC) methods often fail to account for this selection mechanism, leading to biased confidence estimates. This paper reframes KBC through the lens of Positive and Unlabeled (PU) learning, introducing a framework that utilizes propensity scores to mitigate these systemic biases.

The Challenge of Observation Bias

When estimating the precision or "confidence" of a rule (e.g., "If X is married to Y, then X lives in the same country as Y"), researchers typically rely on two restrictive assumptions because KBs only contain positive examples:

  1. Closed-World Assumption (CWA): Assumes any fact not present in the KB is false.
  2. Partial-Completeness Assumption (PCA): Assumes that if a subject has at least one known object for a specific predicate, all other objects for that subject-predicate pair are also known.

Both assumptions ignore the underlying selection mechanism, often overestimating the confidence of rules that align with existing data biases while penalizing those that do not.

Methodology: KBC as PU Learning

By bridging KBC with PU learning—a field designed to learn from positive and unlabeled data—the authors categorize KB population into a taxonomy of bias. This ranges from Selected Completely At Random (SCAR) to Selected At Random (SAR), where the probability of a fact being recorded (the propensity score) depends on its specific characteristics, such as the subject's popularity.

The conceptual framework for generating observed facts from the set of all possible triples under different assumptions.

To address these biases, the paper introduces two novel estimators:

  • Inverse Propensity Weighted (IPW): This estimator weights observed facts by the inverse of their likelihood of being recorded, effectively giving more weight to under-reported types of facts.
  • IPW-PCA: A hybrid approach that combines the strengths of the PCA assumption with propensity weighting to improve robustness.

Experimental Evaluation and Results

The proposed methods were evaluated using Yago3-10. By treating the full dataset as ground truth and simulating various incomplete "known" KBs through biased selection mechanisms, the authors compared their estimators against traditional baselines using metrics like the Brier score.

Comparison of confidence estimators under Selected Completely At Random (SCAR) and Selected At Random (SAR) bias scenarios.

As demonstrated in the experimental results, the IPW estimator achieves significantly higher accuracy in SAR scenarios. While the CWA estimator's performance degrades as the selection probability decreases, the IPW estimator remains remarkably stable and close to the true confidence level. Furthermore, the study found that even "noisy" or imperfect propensity scores (estimated within a $\pm 10\%$ margin) still yielded better results than assuming the data was unbiased.

Conclusion

This work demonstrates that formalizing KBC as a PU learning problem provides a mathematically rigorous way to handle observation bias. By moving beyond naive assumptions like CWA and PCA, the proposed IPW estimators ensure that rule-based completion systems do not simply reinforce the cultural or systemic biases already present in the data. Future work will explore extending these insights to embedding-based KBC methods and automating the estimation of propensity scores using external domain knowledge.

Summary updated

Abstract

Methods for Knowledge Base Completion (KBC) reason about a knowledge base (KB) in order to derive new facts that should be included in the KB. This is challenging for two reasons. First, KBs only contain positive examples. This complicates model evaluation which needs both positive and negative examples. Second, those facts that were selected to be included in the knowledge base, are most likely not an i.i.d. sample of the true facts, due to the way knowledge bases are constructed. In this paper, we focus on rule-based approaches, which traditionally address the first challenge by making assumptions that enable identifying negative examples, which in turn makes it possible to compute a rule's confidence or precision. However, they largely ignore the second challenge, which means that their estimates of a rule's confidence can be biased. This paper approaches rule-based KBC through the lens of PU-learning, which can cope with both challenges. We make three contributions.: (1) We provide a unifying view that formalizes the relationship between multiple existing confidences measures based on (i) what assumption they make about and (ii) how their accuracy depends on the selection mechanism. (2) We introduce two new confidence measures that can mitigate known biases by using propensity scores that quantify how likely a fact is to be included the KB. (3) We show through theoretical and empirical analysis that taking the bias into account improves the confidence estimates, even when the propensity scores are not known exactly.
BibTeX
@inproceedings{schouterden2022unifying,
  author = {Jonas Schouterden and Jessa Bekker and Jesse Davis and Hendrik Blockeel},
  title = {{Unifying Knowledge Base Completion with PU Learning to Mitigate the Observation Bias}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20332},
}
Figure