Constrained Entity Selection under Partial Knowledge for LLM-Based Knowledge Graph QA

Knowledge graph question answering (KGQA) has evolved rapidly, with methods spanning semantic parsing (e.g., SPARQL translation) and neural reasoning (e.g., LLMs with retrieval). Semantic parsing offers precise, verifiable answers but struggles with complex schemas and incomplete data. Neural approaches are more flexible but prone to hallucinations and lack formal guarantees. As knowledge graphs grow in size and complexity, ensuring answer correctness amidst incompleteness becomes critical. Prior efforts incorporate constraints or reasoning paths but often depend on full logical forms or extensive training, limiting scalability and robustness in real-world scenarios.

The core challenge is verifying the correctness of candidate answers generated by LLMs over incomplete knowledge graphs. Existing methods either rely on brittle semantic parsing or unconstrained neural reasoning, both susceptible to errors under data incompleteness and schema complexity. This results in false positives (invalid answers) and false negatives (missed valid answers), undermining trust. The need is for a lightweight, interpretable, and robust verification mechanism that can operate post-hoc, handling uncertainty inherent in real-world knowledge bases.

This work introduces CES-PK, a novel framework that employs lightweight symbolic constraints extracted from questions, evaluated under a three-valued semantics. Key innovations include: 1) using minimal necessary constraints (type, relation, exclusion), 2) applying a three-valued logic to handle incomplete data, 3) leveraging support scores from satisfied constraints for answer ranking. Unlike prior approaches requiring full logical forms or neural hallucination mitigation, CES-PK offers a scalable, interpretable, and robust verification layer that enhances precision without sacrificing recall, even under knowledge graph incompleteness.

• �� Extract constraints: From the question, automatically identify type, relation, and exclusion constraints based on schema and question semantics.
• �� Evaluate candidate answers: For each candidate, assess constraints using a three-valued logic: sat (satisfied), viol (violated), unk (unknown).
• �� Filter candidates: Remove answers violating any explicit constraint, ensuring robustness to missing data.
• �� Compute support: For satisfied constraints, calculate support scores as the ratio of constraints met, aiding in candidate ranking.
• �� Experimental setup: Use Hetionet biomedical KG, simulate candidate answers by sampling gold answers and adding distractors, including incorrect types and exclusion violations.
• �� Measure performance: Use precision, recall, and support scores before and after filtering, analyze robustness under simulated edge removal.

The experiments involved generating candidate answer sets from Hetionet, simulating LLM outputs with added distractors. The evaluation focused on two query types: simple (treating diseases) and complex (excluding side effects). Metrics included precision, recall, and support scores. The method was tested under normal and incomplete conditions (10% edge removal). Results showed significant precision improvements, especially in complex queries, with minimal impact on recall. Support scores provided additional discrimination, aligning well with gold answers. The robustness was confirmed by consistent performance despite knowledge graph incompleteness.

Filtering increased precision from 0.66 to 0.70 in Q1 and from 0.17 to 0.62 in Q2. Support scores effectively distinguished gold answers, with gold candidates achieving a support of 1.0, while non-gold averaged 0.42-0.74. Even with 10% edge removal, precision remained high, demonstrating robustness. The combination of filtering and support scoring provided a balanced approach to improve accuracy and interpretability, confirming the effectiveness of lightweight symbolic verification in noisy, incomplete knowledge graphs.

This approach is directly applicable to biomedical, scientific, and industrial knowledge bases where data incompleteness and schema complexity are prevalent. It can serve as a post-processing layer to improve the trustworthiness of LLM-generated answers, especially in critical domains requiring high accuracy. Future integration into end-to-end KGQA pipelines and extension to multi-hop queries will broaden its utility, enabling scalable, interpretable, and robust AI systems for real-world knowledge management and decision-making.

The current validation is limited to entity-centric, single-hop questions; multi-hop or more complex query types are yet to be tested. The framework depends on accurate constraint extraction, which may be challenging in noisy or poorly annotated schemas. In scenarios with severe knowledge graph errors or missing data, the verification may produce false rejections or support, necessitating further robustness enhancements. Computational costs for large-scale graphs also warrant investigation for practical deployment.