Beyond One Missing Hyperfact: Witness-Guided Full-Inference Complex Query Answering over Hyper-Relational Knowledge Graphs

Complex query answering over hyper-relational knowledge graphs enables multi-hop and logical reasoning over qualified facts. Existing query-embedding and graph-agent methods support diverse logical queries, yet current benchmarks may reward shortcuts through observed main triples, qualifier-free reductions, or lower-order role projections rather than genuine multi-hyperfact inference. Three challenges remain: alternative shortcut witnesses are difficult to exclude, joint role-typed bindings create a combinatorial search space, and answer-only supervision cannot distinguish valid inference from spurious correctness. To address them, we introduce Full-Inference Hyper-Relational Complex Query Answering (FIHR-CQA), a benchmark for strict, projection-clean reasoning, and propose HyWit, a verifier-guided neuro-symbolic framework for joint answer–witness inference. HyWit compiles each query into a role-typed factor hypergraph and performs sparse neural variable elimination with deterministic consistency constraints. A dual replay verifier guides witness learning and policy optimization, preventing invalid evidence from being rewarded. Experiments on WD50K-NFOL, WD50K, and WikiPeople show that HyWit outperforms query-embedding, symbolic-relaxation, and search baselines in answer accuracy and witness validity on strict full-inference queries, while achieving stronger compositional generalization with competitive inference efficiency.