Constrained Entity Selection under Partial Knowledg...

Constrained Entity Selection under Partial Knowledg... | AI Research

Key Takeaways

Constrained Entity Selection under Partial Knowledge (CES-PK) is a framework designed to improve the accuracy of Large Language Model (LLM) responses in Know...
Large language models are increasingly used for knowledge graph question answering (KGQA), but can fail to correctly ground answers in the underlying graph.
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.
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.

Paper AbstractExpand

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.

Constrained Entity Selection under Partial Knowledge (CES-PK) is a framework designed to improve the accuracy of Large Language Model (LLM) responses in Knowledge Graph Question Answering (KGQA). Instead of forcing an LLM to generate complex code or perform unconstrained reasoning, this method uses a post-hoc verification layer to filter out incorrect answers and rank valid ones based on symbolic constraints derived from the user's question.

Addressing LLM Limitations in KGQA

Current LLM-based KGQA systems often struggle with two extremes: either they attempt to translate questions into formal database queries (like SPARQL), which is brittle and prone to failure with complex or incomplete data, or they rely on open-ended reasoning, which can lead to hallucinations. Emanuel Kitzelmann proposes CES-PK as a middle ground. This approach accepts candidate answers from an LLM and applies a verification layer to ensure these answers align with the structural and semantic requirements of the knowledge graph.

How the Verification Works

The framework uses a three-valued logic system—satisfied, violated, or unknown—to evaluate candidates against constraints. This is specifically designed for the "open-world" nature of real-world knowledge graphs, where missing information is common.

Filtering: If a candidate answer explicitly violates a constraint (such as a type mismatch or a forbidden relation), it is removed from the candidate set.
Support: If a constraint is satisfied, it provides positive evidence for the candidate.
Unknowns: If information is missing from the graph, the system labels the constraint as unknown rather than violated. This prevents the system from incorrectly rejecting valid answers simply because the graph is incomplete.

Performance and Results

In experiments conducted on the Hetionet biomedical knowledge graph, the method significantly improved precision. By filtering out invalid candidates, the system increased precision from 0.41 to 0.66 across tested query types. Because the method only removes candidates with explicit violations, it successfully preserved recall. Additionally, the researchers found that calculating a "support score"—the fraction of satisfied constraints—helped distinguish between gold-standard answers and incorrect distractors, as gold answers consistently achieved higher support scores.

Limitations and Considerations

The framework assumes that the underlying knowledge graph is factually correct, even if it is incomplete. The current study relies on controlled candidate sets to isolate the performance of the verification layer, meaning it does not yet account for end-to-end performance in a live pipeline where the LLM might generate highly noisy or incorrect data. Furthermore, if the knowledge graph contains incorrect triples, the system could potentially produce false rejections or provide misleading support scores. Future work is expected to focus on integrating this verification layer into full-scale KGQA pipelines and testing its robustness against noisier data.