Which Bird Does Not Have Wings: Negative-Constrained KGQA with Schema-Guided Semantic Matching and Self-Directed Refinement¶

Conference: ACL 2026 arXiv: 2604.14749 Code: https://github.com/midannii/CUCKOO Area: Graph Learning / Knowledge Graph QA Keywords: Knowledge Graph QA, Negation Constraint, Semantic Parsing, Logical Form, Schema-Guided

TL;DR¶

This paper defines the NEST KGQA task and NestKGQA dataset for negation-constrained knowledge graph QA, designs PyLF (Python-format logical form) for clear negation expression, and proposes CUCKOO framework with constraint-aware draft generation, schema-guided semantic matching, and self-directed refinement, achieving efficient and precise answers for multi-constraint questions in few-shot settings.

Method¶

Key Designs¶

PyLF (Python-Format Logical Form): Adds a boolean neg parameter in JOIN functions to mark negation constraints (e.g., JOIN('producing', 'Saturn', neg=True)), leveraging LLMs' familiarity with Python syntax.
Schema-Guided Semantic Matching: Starting from the subject entity, retrieves candidate entities and their classes, then uses schema-level triples with similarity thresholds to prune invalid combinations, reducing exponential search space to polynomial.
Self-Directed Refinement Module: Triggered only when query execution returns empty results, diagnosing error types and re-generating drafts without external execution feedback.

Key Experimental Results¶

Dataset	CUCKOO(6)	KB-Coder(6)	KB-BINDER(6)
GrailQA (Overall) F1	64.2	56.3	54.5
NestKGQA F1	26.2	24.4	4.6

Highlights & Insights¶

PyLF's minimal modification approach — adding neg boolean to existing JOIN functions — elegantly solves the long-standing negation expression challenge
Schema-guided matching reduces exponential search space to polynomial through type system pruning

Rating¶

Novelty: ⭐⭐⭐⭐
Experimental Thoroughness: ⭐⭐⭐⭐
Writing Quality: ⭐⭐⭐⭐
Value: ⭐⭐⭐⭐