MissDiag: Diagnostic Evaluation of Incomplete-Knowledge Robustness in KGQA and KG-RAG
A diagnostic tool that reveals why knowledge-graph QA systems break when information is missing
Knowledge-graph question answering systems degrade when their supporting graph is incomplete, but past evaluations only reported how much performance dropped, not why. MissDiag removes graph evidence in four distinct, structured ways and compares each system's paired performance before and after, pinpointing the source of degradation. It finds that losing evidence right next to the answer hurts the most, while removing question-related background evidence can be harmless or even helpful.
METAL MEDIA explanatory visual
A diagnostic tool that reveals why knowledge-graph QA systems break when information is missing
- 01KGQA and KG-RAG systems answer questions using facts stored in knowledge graphs, but real-world graphs are often sparse and outdated, making robustness to missing evidence essential
- 02MissDiag keeps the question, gold answer, and linked entities fixed while removing support-graph edges using four typed operators: random, source-context, relation-level, and answer-adjacent removal, then compares each system's output to its complete-graph output
- 03A severity budget scales edge removal proportionally to graph size, producing a typed degradation profile that reports F1 score drops broken down by removal type
- 04Tested across trained KGQA models, graph-prompting methods, KG agents, and direct LLM baselines, answer-adjacent evidence loss caused the largest degradation (10.3 to 21.3 F1 points), while removing source-context evidence sometimes even improved performance
- 05The gap between answer-adjacent and random-removal damage was largest for multi-answer questions and small support graphs, and this pattern held even when switching to a more lenient semantic answer-matching metric
What they did
- KGQA and KG-RAG systems answer questions using facts stored in knowledge graphs, but real-world graphs are often sparse and outdated, making robustness to missing evidence essential
- MissDiag keeps the question, gold answer, and linked entities fixed while removing support-graph edges using four typed operators: random, source-context, relation-level, and answer-adjacent removal, then compares each system's output to its complete-graph output
- A severity budget scales edge removal proportionally to graph size, producing a typed degradation profile that reports F1 score drops broken down by removal type
- Tested across trained KGQA models, graph-prompting methods, KG agents, and direct LLM baselines, answer-adjacent evidence loss caused the largest degradation (10.3 to 21.3 F1 points), while removing source-context evidence sometimes even improved performance
- The gap between answer-adjacent and random-removal damage was largest for multi-answer questions and small support graphs, and this pattern held even when switching to a more lenient semantic answer-matching metric
| Category | System | Complete | Paired degradation 𝚫F1 | |||
|---|---|---|---|---|---|---|
| F1 | Random | Source-context | Relation-level | Answer-adjacent | ||
| Trained KGQA Models | ReaRev | 80.8 | 4.5 | -1.2 | 2.7 | 11.9 |
| NuTrea | 77.2 | 1.9 | -9.9 | -2.7 | 12.2 | |
| NSM | 46.7 | 3.0 | -24.1 | -5.2 | 12.1 | |
| Graph Prompting Methods | MindMap | 46.2 | 10.1 | 0.6 | 11.2 | 12.7 |
| StructGPT | 52.9 | 9.6 | -0.7 | 8.0 | 13.8 | |
| KG-GPT | 45.7 | 7.0 | 4.2 | 5.3 | 10.3 | |
| KG Agents | ToG | 79.5 | 7.0 | 3.9 | 6.0 | 11.4 |
| PoG | 79.9 | 6.8 | 2.7 | 5.8 | 11.6 | |
| GoG | 81.7 | 12.1 | 2.3 | 8.9 | 19.8 | |
| Direct LLM Baselines | Qwen2.5-7B-Instruct | 85.3 | 11.1 | 3.0 | 7.4 | 21.3 |
| Qwen2.5-14B-Instruct | 90.0 | 6.7 | 1.2 | 5.5 | 17.0 | |
| Llama-3.1-8B-Instruct | 84.4 | 6.1 | -0.5 | 4.0 | 15.8 | |
| Mistral-7B-Instruct-v0.3 | 81.2 | 5.4 | 1.6 | 3.8 | 13.3 |
| System | Metric | Paired degradation 𝚫F1 | |||
|---|---|---|---|---|---|
| Rand | Src | Rel | Ans-adj | ||
| Qwen2.5-7B | Exact F1 | 11.1 | 3.0 | 7.4 | 21.3 |
| Semantic F1 | 11.6 | 3.2 | 8.0 | 21.4 | |
| Qwen2.5-14B | Exact F1 | 6.7 | 1.2 | 5.5 | 17.0 |
| Semantic F1 | 6.9 | 1.2 | 5.4 | 16.1 | |
| Llama-3.1-8B | Exact F1 | 6.1 | -0.5 | 4.0 | 15.8 |
| Semantic F1 | 5.1 | -1.0 | 3.9 | 15.1 | |
| Mistral-7B | Exact F1 | 5.4 | 1.6 | 3.8 | 13.3 |
| Semantic F1 | 5.1 | 0.9 | 3.2 | 13.5 |
| Slice | Group | N | Full | Rand | Ans-adj | Gap |
|---|---|---|---|---|---|---|
| Answer cardinality | Single-answer | 888 | 90.8 | 6.8 | 14.4 | 7.6 |
| Multi-answer | 163 | 54.5 | 10.4 | 30.2 | 19.9 | |
| Support size | Small support | 353 | 80.5 | 12.6 | 26.7 | 14.2 |
| Medium support | 527 | 87.0 | 5.2 | 13.3 | 8.0 | |
| Large support | 171 | 89.2 | 2.9 | 7.4 | 4.5 |
Why it matters
Knowing which type of missing knowledge is most damaging lets developers prioritize which gaps in a knowledge graph to fix first when deploying real-world systems. It also shows that a single aggregate robustness score can hide very different failure mechanisms, arguing for a more detailed way of reporting KGQA evaluation results going forward.
Terms in this paper
- Knowledge Graph · a database of facts stored as connections between entities
- KGQA · answering natural-language questions using facts from a knowledge graph
- KG-RAG · generating answers by retrieving supporting facts from a knowledge graph
- F1 score · a combined measure of how accurate and complete a system's answers are
- Degradation Profile · a breakdown of performance loss organized by type of missing evidence
Figures we cannot republish
- Figure 1: Motivation for typed degradation analysis. The same QA instance can show similar aggregate degradation under structurally different missingness conditions. Aggregate score drops alone do not reveal which evidence type was removed, whether answer-local evidence was affected, or whether the effect is systematic.
- Figure 2: Overview of MissDiag. (1) Input: an instance contains a question, gold answer set, and local support graph. (2) Typed Missingness Operators: typed operators select removable support edges for random, source-context, relation-level, and answer-adjacent missingness. (3) Severity-Controlled Missingness: a shared severity budget produces an incomplete support graph. (4) Paired Evaluation: the same system is evaluated under complete and incomplete support to compute paired degradation. (5) Typed Degradation Profile: degradation values are summarized across missingness type, severity, system, and metric.
- Figure 3: Severity effects on paired degradation. Curves show paired ΔF1 across missingness types for Qwen2.5-7B-Instruct and Llama-3.1-8B-Instruct as α increases.
Original abstract (English)
Knowledge graph question answering (KGQA) and knowledge-graph-based retrieval-augmented generation (KG-RAG) aim to ground answers in explicit graph evidence, but real-world knowledge graphs are often sparse, outdated, and incomplete. Existing robustness evaluations usually report aggregate changes in answer quality after evidence is removed or perturbed, which measures sensitivity to incomplete support but leaves the source of degradation under-specified: the same score change can conflate the type of missing evidence, the response of the evaluated system, and the sensitivity of the answer-matching protocol. To address this gap, we propose \textbf{MissDiag}, a diagnostic evaluation framework for incomplete-knowledge robustness in KGQA and KG-RAG. MissDiag keeps the question and gold answer fixed while applying structurally typed missingness interventions to benchmark-provided support graphs, enabling paired comparisons that decompose robustness changes by evidence type, system response, and evaluation protocol rather than reducing them to a single aggregate score drop. Experiments across multiple system families show that incomplete-knowledge robustness is better understood as a typed degradation phenomenon than as a uniform property: answer-adjacent evidence loss produces the largest observed degradation, source-context removal is often neutral and can be beneficial, and semantic answer matching changes absolute scores while preserving the main typed degradation patterns. By transforming aggregate robustness measurement into typed diagnostic attribution, MissDiag provides a more interpretable basis for comparing, diagnosing, and stress-testing KGQA and KG-RAG systems under incomplete knowledge.
Read on arXivLatest papers
- SWE-bench Science: Can Coding Agents Resolve Engineering Tasks in Science?AI coding agents were tested on fixing real scientific software, and even the best one failed more than half the time
- FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM ServingMaking sparse attention fast enough and accurate enough for real LLM serving, not just papers
- PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM AgentsMaking customer-service AI agents follow the whole procedure, not just avoid one bad action
- EXIMO: VLM Guided Exploration of VLA PoliciesTeaching a robot new chores without human teleoperation, by letting a chatty AI supervise it
- EnvHarness: Awakening Static Worlds for Agent LearningInstead of building new training worlds from scratch, this work adds a plug-in layer that reshapes existing ones around each agent's actual weaknesses
- Bounded Sovereignty and the Control Tax: Pricing AI Oversight When the Deployer Does Not Own the ModelCompanies that rent AI instead of owning it can only do half of AI safety oversight
- Beyond Imitation: Filtering On-Policy Distillation by Reasoning ProgressA fix for AI models that get penalized by their teacher even when they're reasoning correctly
- PersonalBench: Measuring the Authorship Gap in LLM PersonalizationAI can be prompted to write 'like someone,' but its own voice never fully disappears