Source-linked AI summary
KEA Explain: Explanations of Hallucinations using Graph Kernel Analysis
Reilly Haskins, Benjamin Adams
TL;DR
LLMs can produce plausible-sounding but factually incorrect claims, and the paper addresses how to detect and explain them. KEA Explain compares knowledge graphs built from LLM outputs with Wikidata or provided context, then generates contrastive explanations. It performs competitively across open- and closed-domain tasks, with graph discrepancies supporting explanations of why a claim is judged hallucinatory.
Problem
LLMs generate semantically incorrect outputs, while hallucination detection needs to explain why claims are judged hallucinatory.
Source: §1 · pp. 1–2Method
Results
KEA Explain performs competitively with state-of-the-art approaches across open- and closed-domain tasks and supplies contrastive explanations of detected discrepancies.
Source: §5 · p. 10Takeaways & Limitations
Graph-based comparisons let the framework pinpoint discrepancies and help users understand differences between generated outputs and factual knowledge.
Source: §5 · p. 10The method is sensitive to domain-specific graph-kernel thresholds and can struggle with highly specific entities in open-domain settings.
Source: §5 · p. 10
Abstract
from arXiv · showhide
Large Language Models (LLMs) frequently generate hallucinations: statements that are syntactically plausible but lack factual grounding. This research presents KEA (Kernel-Enriched AI) Explain: a neurosymbolic framework that detects and explains such hallucinations by comparing knowledge graphs constructed from LLM outputs with ground truth data from Wikidata or contextual documents. Using graph kernels and semantic clustering, the method provides explanations for detected hallucinations, ensuring both robustness and interpretability. Our framework achieves competitive accuracy in detecting hallucinations across both open- and closed-domain tasks, and is able to generate contrastive explanations, enhancing transparency. This research advances the reliability of LLMs in high-stakes domains and provides a foundation for future work on precision improvements and multi-source knowledge integration.
1. Introduction
Hallucinations challenge LLM reliability, particularly in high-stakes domains. KEA Explain detects and explains them using knowledge-graph comparisons, including contrastive explanations of why a claim is wrong and what would make it correct.
1. Introduction
- Hallucinations are grammatically plausible but semantically incorrect, threatening reliability and user trust in high-stakes domains.The cited examples include healthcare, legal advice, and education.Source: §1 · p. 1
- KEA Explain detects and explains semantic hallucinations in both open-domain and closed-domain LLM outputs.It compares knowledge graphs built from outputs against Wikidata in open-domain settings or provided context in closed-domain settings.Source: §1 · p. 1
- The framework uses graph kernels to compare knowledge-graph structure and semantic embeddings to cluster similar labels and select relevant triples.Open-domain comparisons use Wikidata; closed-domain comparisons use a graph constructed from the supplied context.Source: §1 · p. 1
- KEA Explain offers contrastive explanations of why an output was classified as a hallucination and what fact would make it non-hallucinatory.The paper identifies contrastive explanations as explanations of why one outcome occurred rather than a plausible alternative.Source: §1 · p. 2
- The contributions include graph-kernel analysis of symbolic knowledge graphs and explainable classifications driven by graph structure.The framework also compares semanticity between entity and relation labels.Source: §1 · p. 2
2. Related Work
Prior hallucination-detection work spans LLM-based, probabilistic, and knowledge-graph approaches. The review identifies limits in domain generalizability, ground-truth use, and explainability.
2. Related Work
- The review frames hallucination detection as pertinent despite mitigation approaches such as fine-tuning and RAG, whose retrieval can depend on prompt quality.RAG may retrieve relevant but insufficient context (Guan et al., 2024).Source: §2 · p. 2
2.1. LLM-based and Probabilistic Techniques
- LLM-based and probabilistic methods face trade-offs in explainability, ground-truth validation, and computational cost.ChainPoll aggregates multiple LLM votes but is resource-intensive and lacks ground-truth validation; SelfCheckGPT also requires multiple queries and lacks explainability, while BTPROP's tree expansion has exponential time complexity.Source: §2.1 · p. 2
2.2. Knowledge Graphs for Hallucination Detection and Prevention
- Knowledge-graph approaches include open-domain methods with synthetic-training or entity-detection concerns and closed-domain methods with coverage, scalability, or setting constraints.FactAlign's triple-level comparison cannot use wider graph context, a limitation the paper says its graph-kernel approach overcomes.Source: §2.2 · pp. 2–3
2.3. Summary
- The review identifies three recurring limitations: restricted generalizability, proxy rather than ground-truth evidence, and limited explainability.The cited passages associate synthetic training data with applicability limits, proxy evidence with bias, and neural opacity with difficulty understanding classifications and degraded user trust.Source: §2.3 · p. 3
3. Method
KEA Explain represents LLM claims and their grounding sources as knowledge graphs, selects relevant relations, and compares graph structure and labels. When a comparison indicates a potential hallucination, it identifies discrepancies and uses them to generate a contrastive natural-language explanation.
3. Method
- The framework compares a claim knowledge graph with a ground-truth graph, using a graph-kernel score to flag potential hallucinations for explanation.Open-domain ground truth comes from Wikidata; for closed-domain tasks, it is constructed from the supplied context.Source: §3 · p. 3
3.1. Knowledge Graph Construction
- Knowledge-graph construction extracts entities, resolves coreferences, and identifies relations from text.For open-domain tasks, entity linking and SPARQL queries retrieve Wikidata triples, with entity descriptions from Wikidata and Wikipedia added for semantic depth.Source: §3.1 · p. 4
3.2. Knowledge Graph Relation Selection
- Relation selection matches each claim triple to the most semantically similar context or ground-truth triple using SBERT embeddings and cosine similarity.The resulting refined ground-truth graph contains at most as many triples as the claim graph.Source: §3.2 · p. 5
3.3. Semantic Clustering of Knowledge Graph Labels
- Semantic clustering groups graph labels with similar SBERT embeddings so semantically similar but differently worded labels can be compared together.The paper reports an empirically chosen distance threshold of 0.35.Source: §3.3 · p. 5
3.4. Graph Kernel Comparison of Knowledge Graphs
- The Weisfeiler-Lehman graph kernel iteratively aggregates neighboring node labels to compare graph structure and relationships at multiple abstraction levels.The implementation uses five iterations and normalizes similarity scores to the range zero to one.Source: §3.4 · pp. 5–6
3.5. Generation of Explanations
- Explanation generation identifies contradictory relation pairs, applies graph edits to reconcile them, and has an LLM express the discrepancy in natural language.The edit sequence specifies operations that transform the claim graph's contradictory relations into those of the ground-truth graph.Source: §3.5 · p. 6, Figure 2 · p. 6
4. Experiments
The experiments evaluate KEA Explain on closed- and open-domain hallucination detection and manually assess generated explanations. Results are comparable to existing closed-domain knowledge-graph methods, show a recall–precision trade-off on WikiBio, and vary with hallucination severity in explanation evaluation.
4.1. Closed-Domain Hallucination Detection
- KEA Explain outperformed four of six GraphEval methods on average and achieved the best SummEval balanced accuracy (0.761), ranking second overall.It ranked fourth on QAGS-C; the graph-kernel thresholds were 0.15 for SummEval and 0.5 for QAGS-C.Source: Table 1 · p. 7, §4.1 · p. 7
- ROC AUC was 0.79 on SummEval and 0.70 on QAGS-C; at higher thresholds, the SummEval classifier approached random guessing.Both curves bend toward the top-left, indicating high true-positive rates with low false-positive rates.Source: §4.1 · p. 7, Figure 3 · p. 8
4.2. Open-Domain Hallucination Detection
- The authors hypothesize that Wikidata’s failure to retrieve niche or highly specific entities contributes to false positives; other methods also showed lower precision than recall.The authors note that Wikidata provides a ground-truth reference for factual accuracy, which SelfCheckGPT and AlignScore lack.Source: §4.2 · p. 8
- On WikiBio, KEA Explain had a similar F1 to comparison methods, lower precision, and higher recall, indicating stronger detection of true positives.The comparison used results reported by the authors of FactAlign for SelfCheckGPT and AlignScore.Source: §4.2 · p. 8, Table 2 · p. 9
- PR AUC was 0.77, with precision stabilizing around 0.75–0.8 across recall 0.1–0.9; 73% of WikiBio examples were hallucinatory.The authors report that the abundant positive class helps maintain precision as the threshold decreases and recall rises.Source: §4.2 · pp. 8–9, Figure 4 · p. 9
4.3. Hallucination Explanations
- For 20 low-consistency SummEval examples, average explanation ratings fell from 4.85 to 4.15 to 3.15 as consistency rose, with detail declining most.The evaluation focused on the closed domain and assessed accuracy and reliability, trustworthiness, detail, and completeness.Source: §4.3 · p. 9, Figure 5 · p. 10
- The authors hypothesize that sparse, nuanced hallucinations yield fewer conflicting triples to guide explanations, risking omitted details.This is offered as an explanation for why explanation quality declines as the output becomes more consistent.Source: §4.3 · pp. 9–10
5. Discussion and Conclusion
KEA Explain compares knowledge-graph representations to detect and explain hallucinations across open- and closed-domain tasks. The authors report competitive benchmark performance and note limitations involving domain-specific thresholds and highly specific open-domain entities.
5. Discussion and Conclusion
- The authors present graph-based mechanisms as providing interpretability and robustness across open- and closed-domain tasks.Source: §5 · p. 10
- KEA Explain achieves competitive benchmark scores across open- and closed-domain tasks while identifying discrepancies between generated claims and external knowledge or supplied context.The framework uses knowledge graphs to present contrastive explanations of those discrepancies.Source: §5 · p. 10
- Graph kernels compare neighboring subgraph structure at varying abstraction levels, capturing more structural information and accommodating missing data than individual-triple matching.The comparison is contrasted with FactAlign and GraphEval (Sansford et al., 2024).Source: §5 · p. 10
- The method is sensitive to domain-specific graph-kernel thresholds and faces challenges with highly specific entities in open-domain settings.Proposed directions include refining entity linking, improving explanations for nuanced hallucinations, and integrating multiple knowledge bases.Source: §5 · p. 10
Appendix A. Definition of the Weisfeiler-Lehman Graph Kernel
A graph kernel measures similarity between graphs, and the paper uses the Weisfeiler-Lehman Subtree Kernel to compare subtree patterns. Its feature representation counts node-label patterns across iterations, with computation stated to scale as O(hm).
Appendix A. Definition of the Weisfeiler-Lehman Graph Kernel
- A graph kernel measures similarity between graphs by comparing structural and attribute-based features, expressible as an inner product in a feature space.The feature mapping embeds graphs into a d-dimensional vector space and can capture shared subgraphs, paths, and tree structures.Source: Appendix A · p. 14
- The Weisfeiler-Lehman Subtree Kernel uses the Weisfeiler-Lehman graph isomorphism test to generate subtree patterns for comparison.Source: Appendix A · p. 14
- The feature vectors ϕ(G) and ϕ(G′) encode counts of node-label patterns across Weisfeiler-Lehman iterations.The count map c_i gives the number of occurrences of label σ_ij in a graph; Σ_0 contains the original node labels.Source: Appendix A · p. 14
- O(hm) is the stated computation time for the Weisfeiler-Lehman Subtree Kernel, where h is the iteration count and m is the total number of edges across the graphs.Source: Appendix A · p. 14
B.1. Explanation Criteria Ratings
Table 3 provides qualitative rating descriptions for four criteria used to assess generated explanations.
B.1. Explanation Criteria Ratings
- Table 3 describes qualitative ratings for explanation detail, completeness, accuracy and reliability, and trustworthiness.Source: §B.1 · p. 14, Table 3 · p. 15
B.2.1. Sample 1
The sample describes a knowledge graph whose timeline claim about Space Invaders conflicts with the account that it was developed in the late 1970s.
B.2.1. Sample 1
- The output graph incorrectly links Space Invaders to 1970 and omits the correct relationship to the late 1970s.Source: §B.2.1 · p. 15
B.2.2. Sample 2
The LLM output misstates Ben Stokes’s injury and cricket context, including his location and relationship to Kensington Oval.
B.2.2. Sample 2
- The output says Stokes broke his neck during the Ashes, although the account says he broke his wrist after punching a locker the previous year.This changes both the injury and its timing.Source: §B.2.2 · p. 15
- The injury claim also shifts the account’s emphasis from managing aggression to an unsupported severe injury.The source text emphasizes managing aggression.Source: §B.2.2 · p. 15
- The output implies Stokes is at Kensington Oval, while the context places him back in the England team preparing for a match in Barbados.It also misrepresents the Oval’s connection to England as a venue where Stokes has faced challenges.Source: §B.2.2 · p. 16
Appendix C. Full Hallucination Detection Experiment Results
The appendix reports full hallucination-detection experiment results across benchmarks and gives the prompt used to generate knowledge graphs from unstructured text.
Appendix C. Full Hallucination Detection Experiment Results
- Table 4 presents the method’s full hallucination-detection results across benchmarks, with bold metrics indicating the comparison focus used for graph-kernel threshold selection.The supplied caption does not state specific scores or a winning method.Source: Table 4 · p. 16
Appendix D. LLM Prompt
- The knowledge-graph prompt calls for entity detection, cross-text coreference resolution, relation extraction, and refinement of similar triples.It asks that entities referring to the same concept be named consistently across both texts.Source: Appendix D · p. 16
- The prompt requires a parseable JSON object containing one list of triples for each of the two input texts.Each triple is formatted as a three-item list.Source: Appendix D · p. 17