Source-linked AI summary
Predicting Completeness in Knowledge Bases
Luis Galárraga, Simon Razniewski, Antoine Amarilli, Fabian M. Suchanek
TL;DR
Knowledge-base correctness has received more attention than completeness, even though completeness describes how much of the real world a KB covers. The paper combines completeness signals through AMIE rule mining and reports high-precision predictions, reaching 100% precision in specific cases.
Problem
Knowledge-base completeness—the proportion of real-world facts covered—has been much less explored than correctness.
Source: §1 · p. 2Method
The paper studies completeness signals, learns assertions through AMIE rule mining, and obtains the needed training data through crowdsourcing.
Source: §1 · p. 3Results
Completeness predictions reached up to 100% precision for some relations in YAGO and Wikidata.
Source: §1 · p. 3Takeaways & Limitations
Completeness estimations improved fact prediction to 100% precision in specific cases.
Source: §8 · p. 19The paper establishes completeness assertions but leaves estimating how many objects are missing for future work.
Source: §3 · p. 5
Abstract
from arXiv · showhide
Knowledge bases such as Wikidata, DBpedia, or YAGO contain millions of entities and facts. In some knowledge bases, the correctness of these facts has been evaluated. However, much less is known about their completeness, i.e., the proportion of real facts that the knowledge bases cover. In this work, we investigate different signals to identify the areas where a knowledge base is complete. We show that we can combine these signals in a rule mining approach, which allows us to predict where facts may be missing. We also show that completeness predictions can help other applications such as fact prediction.
1 Introduction
Knowledge-base completeness is much less understood than correctness, leaving users and providers without a clear way to identify where facts are missing. This paper studies signals for predicting completeness, combines them through AMIE rule mining, and reports predictions with up to 100% precision for some relations.
1 Introduction
- Completeness is less explored than correctness: a KB may contain correct facts while still covering only an unknown proportion of real-world facts.The paper frames completeness as the proportion of real facts covered by a KB.Source: §1 · p. 2
- Knowing where a KB is incomplete could help users assess query coverage and help providers focus efforts on missing information.The paper also notes that completeness information could help identify erroneous facts and provide counterexamples for machine-learning algorithms.Source: §1 · p. 2
- The Open World Assumption means a missing KB fact is not necessarily false, while common KB formats offer little or no way to record negative information.The paper argues that KBs are therefore unable, by design, to indicate completeness.Source: §1 · pp. 2–3
- The paper systematically studies signals that indicate completeness for properties of KB entities.It presents this work as a first step toward generating completeness information automatically.Source: §1 · p. 3
- The work learns completeness assertions through AMIE rule mining and obtains the training data needed by AMIE through crowdsourcing.A completeness assertion states that the KB contains all values for a subject and relation.Source: §1 · pp. 2–3
- Up to 100% precision was achieved for completeness predictions on some relations in YAGO and Wikidata.The paper also reports that these predictions can increase the precision of rule mining.Source: §1 · p. 3
2 Related Work
Prior work assessed KB precision and documented widespread incompleteness, but generally did not identify which parts were complete. Existing approaches either rely on manual annotations, assume completeness in selected areas, or start from completeness information already supplied.
2 Related Work
- Precision estimates and larger KB size provide little direct information about recall or completeness.YAGO was manually evaluated as 95% correct, while size is described as only a coarse proxy for completeness.Source: §2 · p. 3
- Studies show that KBs are incomplete, but do not establish which parts are complete.Reported examples include 69%–99% of instances lacking at least one property found for other entities in their class.Source: §2 · p. 3
- Some completeness information is manually maintained, including Wikidata lists, no-value statements, and recall annotations.The paper's stated aim is to deduce such annotations automatically.Source: §2 · p. 4
- The partial completeness assumption and related local closed world assumption presume completeness in selected areas rather than automatically deriving it.The AMIE project used the partial completeness assumption.Source: §2 · p. 4
- Rule mining can reveal incompleteness among known instances, but cannot identify a missing spouse absent from the KB.Database completeness reasoning instead assumes the KB already has completeness assertions; this paper aims to generate them.Source: §2 · p. 4
3 Preliminaries
The paper defines completeness for a subject–relation pair against an ideal KB and focuses on relations where such judgments are meaningful. It also introduces completeness oracles and the precision, recall, and F1 measures used to assess them.
3 Preliminaries
- Functionality measures how many objects a relation has per subject, with values near 1 for functions and quasi-functions and lower values when subjects have many objects.The preliminaries represent facts as relation(subject, object) in a fixed KB.Source: §3 · pp. 4–5
- A subject–relation pair is complete when the KB contains every real-world object for that pair, represented by a completeness assertion.The definition compares the KB with a hypothetical ideal KB containing all real-world facts.Source: §3 · p. 5
- Completeness is more meaningful for high-functionality relations; when a relation has low functionality, the paper considers its high-functionality inverse.Source: §3 · p. 5
- The study establishes completeness assertions rather than estimating how many objects are missing, leaving cardinality estimation for future work.Source: §3 · p. 5
- The authors manually selected relations for which completeness is well-defined, excluding cases where the meaning of a relation makes completeness difficult to establish.The passage gives hasHobby and hasOfficialLanguage as examples of such ambiguity.Source: §3 · p. 5
Completeness Oracles
- A completeness oracle predicts whether a subject–relation pair is complete, and the paper evaluates oracle predictions using precision, recall, and F1.The Partial Completeness Assumption is given as an example of a simple oracle.Source: Completeness Oracles · pp. 5–6
4 Completeness Oracles
The paper defines completeness for subject–relation pairs and studies simple and parameterized oracles for predicting it. Simple oracles use assumptions or entity signals, while parameterized oracles use relation patterns or class information; the paper leaves other information sources for future work.
4.1 Simple Oracles
- The CWA treats the entire KB as complete, while popularity predicts completeness based on an entity’s popularity in the KB.The paper expects Wikipedia-based KBs to be more complete for famous entities than for stub-article entities.Source: §4.1 · pp. 6–7
- The PCA predicts completeness only when at least one object is already known, making it more cautious than the CWA and especially suited to functional relations.For a functional relation, a known object means the entity is necessarily complete.Source: §4.1 · p. 6
- The cardinality oracle predicts completeness when a subject has at least k objects; card0 equals CWA, card1 equals PCA, and card2 can predict completeness for hasParent.Larger k values are rarely useful in the authors’ experience.Source: §4.1 · p. 7
- The no-change oracle uses an unchanged set of objects for a subject–relation pair over time as a signal that the subject may be complete.It relies on comparing KB snapshots.Source: §4.1 · p. 7
4.2 Parameterized Oracles
- The star oracle predicts completeness when specified patterns of other relations around a subject are present.For example, the paper suggests that knowing someone won a Nobel Prize may indicate that their alma mater is known.Source: §4.2 · p. 7
- The class oracle uses an entity’s class to predict completeness for a relation, including plain classes and expressions combining a superclass with a negated subclass.For example, assuming the KB is correct, LivingPeople instances are complete for death-date information.Source: §4.2 · pp. 7–8
- The study limits itself to a single information source, leaving Web extraction, crowdsourcing, KB comparison, and external sources for future work.These are presented as other possible ways to build completeness oracles.Source: §4.2 · p. 8
5 Learning Completeness
The paper learns combinations and parameterizations of completeness oracles from gold-standard assertions using an adapted AMIE rule-mining approach. AMIE is extended with atoms and operators for completeness signals, then applies learned rules to predict completeness or incompleteness.
5.1 Combining Oracles
- Gold-standard completeness assertions provide training data for learning combinations and parameterizations of simple oracles with an adapted AMIE rule-mining approach.The paper says such assertions can be obtained from crowd users with good precision.Source: §5.1 · p. 8
5.2 AMIE
- AMIE mines Horn rules by iteratively refining rules with operators that add dangling, closing, or instantiated atoms, retaining rules above a support threshold.A rule’s confidence reflects its support relative to support for the rule and its counterexamples.Source: §5.2 · pp. 8–9
5.3 Enhancing AMIE
- AMIE is extended with atoms for completeness assertions, popularity, unchanged relations, class membership or negation, and relation cardinality, plus operators to add and refine types and cardinality constraints.The adaptations allow it to represent the paper’s completeness oracles and mine rules with completeness or incompleteness heads.Source: §5.3 · pp. 9–10
- Type and negated-type operators can produce rules such as predicting complete hasChild information for a Person who is not an Adult.Cardinality operators can tighten a threshold iteratively; the citizenship example narrows a less-than-three rule toward less than one.Source: §5.3 · pp. 10–11
- AMIE learns completeness and incompleteness rules using opposite training examples, then predicts completeness when no equally or more confident incompleteness rule overrides it.At equal confidence, the completeness rule wins only if it has greater support; otherwise the oracle returns false.Source: §5.3 · pp. 11–12
- The framework also defines Star and Class oracles by restricting AMIE to star atoms or class atoms, respectively.The framework permits star-pattern rules by relaxing the closed-variable constraint for body variables, while retaining constraints on new atom types and forbidding the target relation in rule bodies.Source: §5.3 · pp. 10, 12
6 Experiments
Experiments on YAGO3 and Wikidata evaluate basic and learned completeness oracles against gold-standard assertions. Combining complementary signals predicts completeness with high F1 for many relations, though hasChild and marriedTo remain harder.
6.1 Setup
- The study uses 89M-fact YAGO3 and 15M-fact Wikidata, with gold standards derived from cardinality rules, OpenFlights, and crowdsourced judgments.Source: §6.1 · pp. 12–13
- For low-prevalence relations, sampling balanced entities with and without objects required debiasing; crowdsourcing used three opinions per entity and retained only unanimous annotations.Only 55% of annotations were unanimous.Source: §6.1 · pp. 13–14
6.2 Basic Completeness Oracles
- CWA has 100% recall, but its precision corresponds to actual KB completeness; Wikidata is generally more complete than YAGO.Source: §6.2 · p. 14
- PCA reaches 100% precision on functional relations and 100% recall on mandatory relations, but performs less well on other relations.Source: §6.2 · p. 14
- card2 has low recall and is mainly useful for hasParent, while YAGO’s no-change oracle also has very low recall because most entities changed objects over time.card3 performs worse than card2 on both datasets.Source: §6.2 · pp. 14–15
- Popularity has generally good precision but low recall; popular entities can still lack parent facts or citizenship in YAGO and parent facts in Wikidata.Source: §6.2 · p. 14
6.3 Learned Completeness Oracles
- Over 90% F1 on more than half the relations in both YAGO and Wikidata; learned oracles combine complementary signals, while hasChild and marriedTo remain harder.For difficult relations without relation-specific rules, AMIE learns the CWA.Source: Table 3 · p. 15, §6.3 · pp. 16–17, Table 5 · p. 17
- The YAGO LivingPeople class oracle raises diedIn F1 from 60% to 99%, showing that parametrized oracles can help on particular relations.Source: Table 3 · p. 15, §6.3 · p. 16
7 Application
Completeness assertions can filter AMIE fact predictions, raising the precision of the remaining predictions to 100%. This gain comes with a cost: the filtering also removes roughly 25% of correct predictions.
7 Application
- Completeness assertions filter predictions r(s, o) whenever complete(s, r) holds, such as discarding an extra parent prediction when two parents are already known.Source: §7 · pp. 17–18
Setup
- The evaluation compared standard AMIE predictions with filtered predictions on YAGO3, grouping predictions by confidence and estimating precision from samples of 100 facts per bucket.Completeness assertions were produced by training AMIE with cross-validation on the gold-standard completeness assertions.Source: Setup · p. 18
- 100% precision remained after completeness assertions filtered out all wrong fact predictions.The remaining predictions were mainly citizenship predictions, with a few other relations also represented.Source: Setup · pp. 18–19, Figure 1 · p. 18
- The filtering removed 110K of 400K correct predictions, roughly 25% of the correct predictions.AMIE made 1.05M predictions in total.Source: Setup · p. 19
8 Conclusion
The paper presents a systematic study of knowledge-base completeness, a quality dimension distinct from correctness, and combines completeness oracles through rule mining. Experiments on YAGO and Wikidata show high-precision completeness predictions, which can improve fact prediction to 100% precision in specific cases.
8 Conclusion
- The work presents what the authors describe as the first systematic study of completeness in knowledge bases, a quality dimension orthogonal to correctness.Source: §8 · p. 19
- The paper defines and analyzes simple and parametrized completeness oracles, then combines them into more complex oracles by rule mining.Source: §8 · p. 19
- Experiments on YAGO and Wikidata show that completeness can be predicted with high precision for many relations.Source: §8 · p. 19
- Completeness estimations improve fact prediction to 100% precision in specific cases.Source: §8 · p. 19
- The authors hope this work will lead to research on knowledge bases that are both highly accurate and highly complete.Source: §8 · p. 19