Source-linked AI summary
Constrained Entity Selection under Partial Knowledge for LLM-Based Knowledge Graph QA
Emanuel Kitzelmann
TL;DR
LLM-based KGQA can generate candidates that are not grounded in the underlying graph, while existing parsing and reasoning approaches have practical or formal limitations. CES-PK verifies such candidates with lightweight constraints and three-valued semantics for incomplete graphs. In controlled Hetionet experiments, verification improved precision while preserving recall, with exclusion constraints filtering and positive relation constraints supporting retained answers.
Problem
LLM-based KGQA systems can produce answers that are not correctly grounded in the underlying knowledge graph, while existing approaches face practical or formal limitations.
Method
CES-PK applies lightweight necessary constraints and three-valued semantics to verify LLM-generated candidate answers without requiring full semantic parsing.
Results
Constraint-based verification improves precision while preserving recall, with exclusion constraints providing filtering signals and positive relation constraints providing support.
Takeaways & Limitations
The framework provides a symbolic verification layer that filters invalid candidates and supports retained answers under incomplete knowledge.
Takeaways & Limitations
The evaluation uses controlled candidate sets, assumes a factually correct but incomplete graph with all candidates present, and does not capture end-to-end performance under noisy graphs.
Abstract
from arXiv · showhide
Large language models are increasingly used for knowledge graph question answering (KGQA), but can fail to correctly ground answers in the underlying graph. Current approaches to LLM-based KGQA either rely on full semantic parsing into executable queries such as SPARQL, which is brittle in practice due to complex schemas or incompleteness of real-world KGs, or on LLM-reasoning and answer generation over KGs, which can be more robust but lacks formal guarantees. In this work, we study a complementary setting in which \emph{candidate} answers are generated by an LLM-based system and subsequently verified using lightweight symbolic constraints derived from the question. We introduce \emph{Constrained Entity Selection under Partial Knowledge (CES-PK)}, a problem formulation that focuses on eliminating invalid answers and providing symbolic support for valid ones without requiring construction of executable logical forms. To account for incomplete KGs, we employ a three-valued constraint semantics (\emph{satisfied, violated, unknown}) that avoids incorrect rejections under open-world assumptions. To demonstrate the effects of our method, we instantiate this framework over the Hetionet biomedical knowledge graph and evaluate the impact of type, relation, and exclusion constraints. Experiments show that precision improves by filtering invalid candidates, while recall is preserved due to retaining candidates whose constraints are not explicitly violated. Satisfied constraints provide additional positive symbolic evidence to rank remaining candidates.
1 Introduction
LLM-based KGQA can produce answers that are not grounded in the graph, while existing semantic-parsing and unconstrained-reasoning approaches have complementary limitations. CES-PK adds lightweight constraint verification with three-valued semantics, improving precision while preserving recall and supplying symbolic support.
- LLMs used for KGQA can fail to ground answers in the underlying graph or satisfy structural and semantic constraints.
- Semantic parsing enables verifiable answers, but generating executable queries is challenging for complex schemas and incomplete knowledge graphs.
- CES-PK verifies upstream candidate answers using lightweight necessary constraints rather than constructing complete executable logical forms.
- Three-valued semantics distinguishes satisfied, violated, and unknown constraints, rejecting candidates only when explicit violations are present.
- Hetionet experiments show that constraint-based verification improves precision while preserving recall and provides support scores for retained answers.
- Exclusion constraints support filtering, whereas positive relation constraints provide verification through symbolic support.
2 Problem and Method
CES-PK addresses KGQA settings where an upstream component supplies potentially incorrect candidates. It filters candidates against necessary question-derived constraints and assigns support scores to those retained.
- CES-PK considers candidate answers produced by an upstream component that may include incorrect or unsupported entities.
- Given a candidate set and necessary conditions implied by a question, the method identifies candidates consistent with those conditions rather than deriving all correct answers directly.
- The framework retains candidates that violate no constraint under incomplete knowledge and associates them with support scores reflecting constraint satisfaction.
2.2 Assumptions on the Knowledge Graph
The framework assumes a factually correct but incomplete knowledge graph and requires candidate entities to be present in it. It uses lightweight schema-based necessary constraints that can be extended to richer conditions.
- The knowledge graph follows an open-world assumption: represented triples are true, but some true facts may be missing.
- All candidate entities are assumed to be present in the knowledge graph.
- Constraints are lightweight necessary conditions extracted from the question with respect to a known schema.
- The framework includes type, relation, and exclusion constraints, represented respectively by type membership, positive relations, and negated relations.
2.4 Three-Valued Constraint Semantics
Because the knowledge graph may omit true facts, CES-PK evaluates each constraint with three possible outcomes: satisfied, violated, or unknown.
- Constraint evaluation under incomplete knowledge assigns each candidate-constraint pair one of three values: satisfied, violated, or unknown.
2.5 Constraint-Based Filtering and Support-Based Verification
The method retains candidates without explicit constraint violations and assigns support based on satisfied positive constraints.
- Candidates are retained only when no constraint evaluates to an explicit violation.This makes filtering robust under incomplete knowledge because unknown constraints do not cause rejection.
- Support measures the fraction of positive-evidence constraints that evaluate as satisfied.The positive-constraint subset is denoted C+(q).
3 Experiments
Controlled Hetionet experiments simulate LLM-generated candidate sets and show that lightweight constraints improve precision while preserving recall and providing verification evidence.
- 3.1 Experimental Setup: The evaluation simulates LLM-generated answers by combining gold answers with sampled distractors, including type-incorrect and exclusion-violating candidates.Queries and gold answers are sampled from the Hetionet biomedical knowledge graph.
- 3.1 Experimental Setup: Type, relation, and exclusion constraints are evaluated using precision before and after filtering plus support scores after filtering.Because every gold answer remains in the candidate sets, recall is fixed at 1.0; type and positive relation constraints provide support.
- 3.2 Results: 0.17 to 0.62 (+0.45) precision for Q2 results from exclusion constraints eliminating candidates that violate the negated condition.Q1 gains a modest +0.04 from removing type-inconsistent candidates.
- 3.2 Results: Overall precision improves from 0.41 to 0.66 while recall remains unaffected.The result summarizes filtering performance on the Hetionet knowledge graph.
- 3.2 Results: Type constraints consistently filter, exclusion constraints primarily drive Q2 filtering, and relation constraints provide support without violations under OWA.Positive relation constraints contribute verification evidence when satisfied.
- 3.2 Results: Gold answers achieve mean support 1.0 versus 0.42 for Q1 and 0.74 for Q2 non-gold candidates.Support scores therefore discriminate among retained candidates even when filtering is limited.
- 3.3 Discussion: 10% edge removal lowers precision and support scores but the method continues to preserve recall.Missing edges reduce detectable violations and verifications.
- 3.3 Discussion: The evaluation uses controlled candidate sets, assumes a factually correct but incomplete KG, and may falsely reject or support answers with incorrect triples or missing entities.These assumptions limit direct interpretation as end-to-end KGQA performance.
4 Related Work
Related KGQA work either translates questions into executable logical forms or uses LLMs to reason over retrieved graph information, with different trade-offs in precision, robustness, and guarantees.
- Semantic parsing approaches translate natural-language questions into executable logical forms such as SPARQL queries.They enable precise and verifiable answers but are brittle when correct queries must be generated over complex schemas or incomplete KGs.
- LLM reasoning approaches retrieve graph information or explore graph neighborhoods to construct reasoning paths and generate answers.They are typically more robust and require no additional training, but may produce hallucinated or non-grounded answers.
- Generation-followed-by-verification research reports that LLMs generate solution candidates effectively but verify them unreliably.
5 Conclusions
CES-PK provides post-hoc verification for KGQA candidates using lightweight necessary constraints and three-valued semantics, filtering invalid answers while supporting valid ones under incomplete knowledge. Controlled experiments show improved precision with preserved recall, while evaluation and assumptions leave noisy, end-to-end settings for future work.
- 5 Conclusions: CES-PK verifies candidate answers after generation without relying on full semantic parsing or unconstrained neural generation.It combines lightweight necessary constraints with three-valued semantics for incomplete knowledge graphs.
- 5 Conclusions: Constraint-based verification substantially improves precision while preserving recall in a controlled setting.The evaluation uses controlled candidate sets rather than end-to-end KGQA.
- 5 Conclusions: Exclusion constraints provide strong negative signals for filtering, whereas positive relation constraints provide verification support.The two constraint types therefore play complementary roles in candidate selection.
- 5 Conclusions: The approach assumes a factually correct but incomplete graph and that all candidate entities are present in it.These assumptions constrain applicability when graph facts are noisy or candidates are absent from the graph.
- 5 Conclusions: Future work targets integration into full KGQA pipelines, robustness under incomplete and noisy graphs, and more complex query types and schemas.These directions extend the current controlled evaluation and constraint-extraction setting.