When Correct Edges Cannot Be Verified: A Provenance Gap in Incomplete KGQA and a Provenance-Favoring Completion Policy

2026-06-14 · Source: Computation and Language · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, quick

Summary

A study on Incomplete Knowledge Graph Question Answering (IKGQA) identifies a significant "provenance gap," revealing that textual verifiability often fails to confirm the correctness of completed edges. Researchers found that 76-96% of gold-correct completed edges, across datasets like CWQ and WebQSP, deletion rates of 20% and 40%, and various relation types, lack supporting passages even with exhaustive retrieval. This indicates textual faithfulness measures provenance, not correctness. Critically, 95-97% of correct answers in IKGQA do not rely on unsupported edges. This reframes edge completion, shifting focus to "admit or abstain under provenance uncertainty." The paper introduces TGComplete, a provenance-favoring admission policy. TGComplete achieves 15-21% higher edge precision against gold compared to the GoG baseline (3-14%), with 3.1-7.4 times higher strict faithfulness of admitted edges and no statistically detectable EM loss, positioning it for applications prioritizing auditability.

Key takeaway

For Machine Learning Engineers developing Incomplete Knowledge Graph Question Answering systems, recognize that relying solely on textual support for edge verification introduces a significant "provenance gap," not a correctness guarantee. Your systems should prioritize explicit provenance-favoring admission policies like TGComplete, especially when auditability is critical. Be prepared for a trade-off, as higher precision and faithfulness in admitted edges may come at the cost of lower recall, requiring careful balancing for your specific application.

Key insights

Textual verifiability in IKGQA measures provenance, not correctness, due to a significant "provenance gap" in textual support for gold-correct edges.

Principles

• Textual support for KG edges often indicates provenance, not correctness.
• Most correct IKGQA answers are independent of unsupported edges.
• Edge completion should prioritize "provenance uncertainty."

Method

TGComplete retrieves evidence at a reasoning breakpoint, verifies candidates via a lightweight loop, and abstains when textual support is absent.

In practice

• Prioritize provenance in IKGQA for auditability.
• Implement admission policies favoring textual evidence.
• Evaluate edge completion based on precision/provenance trade-offs.

Topics

• Incomplete KGQA
• Provenance Gap
• Edge Completion Policies
• Textual Verifiability
• TGComplete
• Question Answering

Best for: Research Scientist, AI Scientist, Machine Learning Engineer, NLP Engineer

Related on AIssential

• Where Provenance Ends, Knowledge Decays — LLMs inherently destroy knowledge provenance, leading to systemic degradation of information trustworthiness and creating a feedback loop of false data.
• Generalized Rank-based Evaluation for Knowledge Graph Completion: Perspectives, Framework, and Analyses — PROBE offers a generalized framework for KGC evaluation, addressing predictive sharpness and popularity-bias robustness for more reliable model assessment.
• Down the RDFS Rabbit Hole — RDF-Star annotations bridge the gap between RDFS entailment and SHACL validation for property hierarchies.
• Provenance-Enhanced Statements in Knowledge Graphs — DEC interprets knowledge graph provenance as epistemic stance, enabling principled reasoning over attributed claims and disagreements without collapsing into inconsistencies.
• GS-Quant: Granular Semantic and Generative Structural Quantization for Knowledge Graph Completion — GS-Quant aligns graph embeddings with LLM tokens using semantically coherent, hierarchically structured discrete codes.
• Strikingness-Aware Evaluation for Temporal Knowledge Graph Reasoning — Current TKGR evaluation overestimates model ability by uniformly weighting trivial and outstanding events.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Computation and Language.