acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
hyper-relational knowledge graphs, complex query answering, neuro-symbolic reasoning, benchmark auditing, executable witnesses, compositional generalization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_u2BMOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies question answering over incomplete knowledge graphs where facts carry extra details, such as the work an award was given for. The authors introduce FIHR-CQA to select questions that require predicting at least two distinct missing facts and remove examples with specified shortcuts. They also propose HyWit, which predicts candidate facts and combines those that agree on shared entities. It learns which additional candidates to generate within a fixed budget and returns both an answer and its supporting facts. On the filtered WD50K-NFOL dataset, HyWit gets both the answer and its supporting facts right in 21.4% of cases, compared with 19.7% for the strongest baseline best-first search.

Critical strengths
  • The filter checks every possible way to answer a question in the full graph, not just one sampled path. This is a good setting as a different path might reach the same answer with fewer missing facts. The check for distinct missing facts removes 3,733 examples that passed the earlier check, so this distinction affects a large part of the dataset.
  • One ablation directly shows that training on supporting facts helps. With the candidate facts held fixed, removing this training objective lowers joint answer-and-evidence accuracy from 21.4% to 18.5%, while candidate coverage and answer accuracy stay the same. This shows the gain in better selection of the correct supporting facts.
Critical weaknesses
  • The practical benefit over the strongest baseline remains unclear. With the same proposer and scorer backbones, HyWit improves joint recovery over best-first search only from 19.7% to 21.4% (Table 1), and a simple deficit heuristic already reaches 18.3%. Coverage is only 44.8%, so for most questions the correct supporting facts are never generated, and better acquisition alone cannot fix this. In the ablations (Table 2), the largest drop comes from removing the evidence loss, not the learned acquisition, and the remaining differences are small and reported without variance. The runtime, transfer, and masking experiments compare only with Static, so it is unclear whether HyWit beats best-first search at the same runtime or in harder settings. Key details are also missing: the proposer and scorer architectures, the actual budget sizes, and how evidence is extracted for the baselines. This makes the results hard to reproduce and the comparisons hard to judge.
  • Figure 3 shows that the new checks remove many questions, but not how this changes model performance. Prior work already filters questions so that they require predicting multiple missing links; this paper instead requires multiple missing statements. To show why this difference matters, the authors should compare model performance before and after the new checks on questions with similar structures.
Questions for authors
  • Could you compare HyWit with best-first search at the same runtime and on unseen query structures? What is the additional cost of training the controller?
  • Do the search baselines (best-first, beam, and the deficit heuristic) use the same scorer trained with the evidence loss? If not, how much of HyWit’s improvement remains when they do?
  • Could you provide the proposer and scorer architectures, the actual budget settings, and the evidence-extraction procedure used for the baselines?
  • How does model performance change after the new filtering checks, when comparing questions with similar structures?
1 comment
AuthorsOpenReview ↗

Response to Reviewer u2BM (Orthogonal Ablation, BF across RQ4–6, Audit Strata & Specs)

Dear Reviewer u2BM,

We sincerely apologize for the late rebuttal due to urgent work commitments. We have uploaded the revised PDF with substantial new experiments, full architectural and protocol disclosures, and ten-seed statistical testing. We would be deeply grateful if you could spare time to read our updated manuscript. Below we directly address every technical concern you raised.

1. Margin Over Best-First Search & Whether Search Controls Share L_ev

Thank you for highlighting this crucial question. In Table 1, all four search controls (Static Acquisition, Deficit Heuristic, Beam Search, and Best-First Search) already share our exact StarE-Transformer proposer and L_score-trained (i.e., L_ev-supervised) scorer (Section 5.1 and Appendix F). Thus, Table 1's +1.7 pp (WD50K-NFOL) and +1.9 pp (WikiPeople) margins over Best-First isolate only the learned acquisition controller. To show the full contribution transparently, we added a complete ten-seed 2×2 orthogonal ablation (Figure 3(c) and Appendix D.1, Table 3):

  • Against unadapted Best-First Search (w/o L_ev), Full HyWit improves strict J@1 by +4.3 pp (+25.1% relative) on WD50K-NFOL (17.1% → 21.4%) and +4.2 pp (+26.9% relative) on WikiPeople (15.6% → 19.8%, exact paired sign-flip p = 0.0020).
  • L_ev and learned acquisition exhibit statistically significant synergy (+1.0 pp on WD50K, +1.1 pp on WikiPeople, p = 0.0020).

2. Adding Best-First Search & Deficit Heuristic to RQ4–RQ6 + Ten-Seed Variance

We upgraded all experiments across RQ1–RQ6 to include Best-First Search and Deficit Heuristic alongside Static Acquisition, with ten paired seeds (mean ± std) and exact two-sided paired sign-flip p-values (Table 1, Figures 3, 5, 6, 7, Appendix D):

  • RQ4 (OOD Transfer, Figure 5): HyWit outperforms Best-First Search across all unseen four-factor topologies under both fixed (B = 72) and scaled (B = 96) budgets, widening its lead to +2.3 pp J@1 on 4-Tree and +2.2 pp on scaled 4-Multi.
  • RQ5 (Robustness, Figure 6(a), Appendix D.4): HyWit retains a consistent lead over Best-First across 0%–40% test-time support masking and swapped-qualifier stress tests (7.1% vs. 6.3%).
  • RQ6 (Matched-Runtime Frontier, Figure 7(a)–(b), Appendix D.5): At matched median latency (168 ms vs. 167 ms), HyWit beats Best-First by +2.1 pp J@1 (21.4% vs. 19.3%); at matched quality (19.8% vs. 19.7%), HyWit runs 24.5% faster (139 ms vs. 184 ms) by cutting wasted requests from 43.6% to 32.4%.

3. Diagnosing the 44.8% Coverage Bottleneck

In Section 5.6 (Figure 6(b)–(c)) and Appendix D.4 (Table 6), we decompose HyWit's 44.8% covered targets into 47.8% Valid Joint Recovery (21.4% abs.), 19.6% Intra-Entity Spurious Witness Override (8.8% abs., reduced from 26.1% w/o L_ev), and 32.6% Inter-Entity Hub Distractor Competition (14.6% abs.). We also added four LLM/Graph-R1 agent baselines (Figure 7(c)), where HyWit leads Graph-R1 by +5.5 pp J@1 at 97.1% lower latency.

4. Pre- vs. Post-Audit Performance Comparison

We added a stage-by-stage evaluation across FIHR-CQA audit strata on structurally matched three-factor queries (Section 5.4, Figure 4(c); Appendix D.2, Table 4). Observed Projection Lookup drops from 64.2% H@1 on projection shortcuts (P_Γ(q)) to 0.0% on strict targets, and every learned model drops by >20 pp H@1 once single-record self-joins (D(q)) and projection shortcuts are removed, empirically validating the necessity of statement-level auditing.

5. Complete Architecture, Budget, and Baseline Extractor Specifications

We now fully specify all components in Section 5.1, Appendix C (Algorithm 1), Appendix F, and Appendix H: the 2-layer StarE encoder (d = 256) + 4-layer, 8-head Transformer decoder (beam b = 16), 2-layer Transformer scorer, 2-layer 64-unit MLP controller, exact budget parameters (B = 72, B_init = 18, k = 6, r = 4, D_max = 3, H = 18), and the shared reference-blind post-hoc witness extractor used for NQE and StarQE.

We would be truly grateful if you could spare time to read our revised PDF. If these comprehensive additions and clarifications resolve your concerns, we kindly ask you to consider raising your score. Thank you for your thorough feedback!

Reviewer_yCP2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This article looks into the problem of complex query answering in hyper-relational knowledge graphs. The author introduced FIHR-CQA, a strict evaluation protocol designed to eliminate shortcuts in reasoning. They also proposed the HyWit framework, which builds consistent evidence (Witness) through exact joins and selectively acquires additional candidate statements within a limited budget. Experiments on the WD50K-NFOL dataset show that HyWit outperforms existing query-answering models and search baseline methods, achieving 21.4% JointHit@1 and 44.8% Witness Coverage.

Critical strengths

The points the article pays attention to are really important, and it puts forward a fairly complete framework. The paper addresses a key problem in complex query answering: it’s not just about predicting the correct answer, but also about recovering reliable supporting evidence. Combining precise linking with budget-aware evidence retrieval is a meaningful contribution.

Critical weaknesses

The writing is really hard to follow. For example, Figure 2's framework isn't shown clearly, and it doesn't clearly separate offline auditing, training supervision, and inference during testing. The AI-made flowchart's steps are also not clear. At the same time, the text has obvious gaps in meaning, making it hard to read.

The model validation is insufficient, and the experimental details are lacking. Using only one dataset can't verify how the framework adapts to other data. The descriptions of experiments like observed HKG construction and simplified queries are insufficient, and the process is missing.

Questions for authors

1.Why is the JointHit@1 relatively low (21.4%) despite achieving 44.8% witness coverage? What are the main factors limiting the selection of correct witnesses?

2.The example given in fig1 makes it hard to understand the issues with the current method. In fig1(a) , I don't know what "country(x,c) already observed" means.

2 comments
AuthorsOpenReview ↗

Response to Reviewer yCP2 (Redrawn Vector Figs. 1–2, Error Attribution, and WikiPeople)

Dear Reviewer yCP2,

We sincerely apologize for the late rebuttal due to urgent work commitments. We have uploaded the revised PDF with two newly redrawn vector figures (Figures 1 and 2), a second benchmark, and a complete error-decomposition analysis, and we would be very grateful if you could spare time to review the updated manuscript. Below we address every concern point by point.

1. Presentation Clarity and Newly Redrawn Vector Figures (Figures 1 & 2)

Thank you for pointing out the ambiguities in Figures 1 and 2. We completely redesigned and replaced both Figure 1 and Figure 2 with clean, high-resolution vector graphics:

  • Figure 1: Explicitly depicts the observed graph G_obs and missing statements side by side. Panel (a) now clearly illustrates why an already-observed country branch δ_2 ∈ G_obs collapses the two-statement query into a trivial single-statement lookup (d(w) < 2); Panel (b) contrasts cross-record qualifier splicing and incompatible work bindings (x₁ ≠ x₂, V_ref = 0); Panel (c) shows HyWit's verifiable multi-statement witness (d(w) ≥ 2, V_ref = 1). We also simplified the Introduction Paragraph 1 prose to align directly with Figure 1.
  • Figure 2: Clearly separates the three execution boundaries with color-coded zones and explicit data-flow arrows: (A) Offline Statement-Level Inference Audit (over G_obs and G_ref), (B) Online Reference-Free Separator-Consistent Witness Inference (strictly over G_obs under budget B), and (C) Offline Budget-Aware Witness Learning (over masked observed subgraphs G_sub ⊂ G_0). Appendix A.1 (Table 2) further formalizes the exact information-access contract at every stage.

2. Observed HKG Construction and Simplified Query Reductions (Γ)

We clarified both the snapshot construction and the reduction grammar in Section 3, Section 4.1, and Appendices A.1–A.2:

  • Observed HKG (G_obs): Both benchmarks are partitioned at the main-triple group level (s, r, o) into nested deduplicated snapshots G₀ ⊂ G₁ ⊂ G₂ (80%/10%/10%), ensuring all qualifier attachments of a main triple remain in the same partition without cross-split ownership leakage.
  • Simplified Query Grammar (Γ): Appendix A.2 explicitly instantiates all three reduction families on the running award query: qualifier-free reductions (Γ_QF), connected atom deletions (Γ_CAD), and proper role projections (Γ_PRP), together with the formal proof of Proposition 1 and counterexamples in Appendix B.1.

3. Diagnosing the 44.8% Coverage vs. 21.4% JointHit@1 Gap

We added a dedicated within-coverage bottleneck attribution and witness-margin analysis in Section 5.6 (Figure 6(b)–(c)) and Appendix D.4 (Table 6):

  • Across HyWit's 44.8% covered target pool on WD50K-NFOL, every covered target falls into one of three mutually exclusive outcomes: 47.8% (21.4% abs.) succeed in Valid Joint Recovery, 19.6% (8.8% abs., CWS = 70.9%) suffer Intra-Entity Spurious Witness Override (correct answer ranked #1, but paired with an unsupported witness), and 32.6% (14.6% abs.) suffer Inter-Entity Hub Distractor Competition (a high-degree distractor outranks the true entity).
  • Removing L_ev increases spurious overrides from 19.6% to 26.1%, while adding L_ev flips the mean intra-entity witness margin ΔS(a) = P_a - N_a from negative (-0.11 without L_ev) to positive (+0.24 for Best-First and +0.39 for Full HyWit), directly curbing spurious overrides and isolating hub-entity ranking as the main residual bottleneck (illustrated in Appendix I, Cases 1–2).

4. Second Benchmark (WikiPeople) and Expanded Baselines

We added WikiPeople (4,892 strict targets) across all main and ablation tables (Table 1, Figure 3, Appendix D.1), where HyWit again leads Best-First Search by +1.9 pp J@1 (p = 0.0020) and QTO by +3.3 pp, plus four LLM/Graph-R1 agent baselines in Section 5.7 (Figure 7(c)).

We would deeply appreciate it if you could find time to read our revised PDF. If these redrawn vector figures, explanations, and new analyses address your concerns, we kindly ask you to consider raising your score. Thank you very much!

Thank you for the detailed response and substantial revisions. The redesigned figures, clearer methodological descriptions, additional WikiPeople benchmark, and error attribution analysis address most of my concerns. I appreciate the authors' efforts to improve the paper. However, the overall writing and presentation still need further polishing, as some parts of the methodology and pipeline remain difficult to follow. Therefore, I maintain my original rating of 2.

Reviewer_HfLsOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies complex query answering over hyper-relational knowledge graphs. Previous methods rank the candidate answers by score functions but cannot show the dependencies of the prediction. To address these issues, the paper first introduces FIHR-CQA as a statement-level benchmark protocol to extend full-inference evaluation and publish rejection certificates. The paper also proposes HyWit to utilize exact joins for incomplete queries and return an answer with a witness. The FIHR-CQA and HyWit are evaluated on the WD50K-NFOL dataset.

Critical strengths

The fair and utility evaluation of complex query answering is challenging. The paper first formulates the task and introduces a benchmark protocol (i.e., FIHR-CQA) for evaluation. Under this setting, the paper proposes a new method, HyWit, which can return both an answer and an executable typed witness.

Critical weaknesses

The paper conducts experiments only on one dataset (i.e., WD50K-NFOL), and the performance gain is limited, as shown in Table 1. The generalization and scalability of the proposed FIHR-CQA and HyWit are not well verified.

Questions for authors

In the era of powerful LLMs, what if we test LLMs on these complex query answering tasks?

1 comment
AuthorsOpenReview ↗

Response to Reviewer HfLs (Revised PDF Uploaded with WikiPeople, LLM Baselines, and Scalability)

Dear Reviewer HfLs,

Thank you very much for your positive assessment and encouraging recognition of our work. We sincerely apologize for the late rebuttal due to urgent work commitments. We have uploaded the revised PDF incorporating comprehensive new experiments and clarifications, and we would be deeply grateful if you could spare time to review our updated manuscript. Below we address each of your points in detail.

1. Evaluation Beyond a Single Dataset (Added WikiPeople Benchmark)

To verify that our findings generalize beyond WD50K-NFOL, we added a second public hyper-relational benchmark, literal-free WikiPeople (34,825 entities, 178 relations, 369,866 statements, yielding 4,892 strict test targets from 14,200 initial pairs; Section 5.1 and Appendix E). As shown in Table 1, HyWit consistently outperforms all baselines on both benchmarks across ten paired seeds, achieving +1.9 pp strict JointHit@1 (J@1) over Best-First Search (19.8% vs. 17.9%, exact paired sign-flip p = 0.0020) and +3.3 pp over QTO (16.5%) on WikiPeople, closely mirroring the WD50K-NFOL gains (+1.7 pp over Best-First, +3.2 pp over QTO).

2. Magnitude and Significance of Gains

In our original draft, all search controls (including Best-First Search) already used our evidence-supervised scorer (L_ev), which masked the full contribution of HyWit. In the revised Figure 3(c) and Appendix D.1 (Table 3), we report a full 2×2 orthogonal ablation isolating L_ev and the learned acquisition policy across ten paired seeds:

  • Compared with unadapted Best-First Search (w/o L_ev), Full HyWit improves strict J@1 by +4.3 pp (+25.1% relative) on WD50K-NFOL (17.1% → 21.4%) and +4.2 pp (+26.9% relative) on WikiPeople (15.6% → 19.8%, p = 0.0020).
  • Evidence supervision and learned acquisition act synergistically: L_ev yields +3.6 pp under HyWit vs. +2.6 pp under Best-First on WD50K-NFOL (+1.0 pp synergy).
  • At matched median latency (168 ms vs. 167 ms), HyWit leads Best-First by +2.1 pp J@1, and reaches Best-First's default accuracy 24.5% faster (139 ms vs. 184 ms) by cutting wasted requests from 43.6% to 32.4% (Figure 7(a)–(b), Appendix D.5).

3. Scalability and Computational Overhead

We added a dedicated scalability study across factor counts m ∈ {2, 3, 4, 5} (B ∈ {48, 72, 96, 120}) and offline training costs in Appendix D.3 (Table 5) and zero-shot four-factor OOD transfer in Figure 5. Because separator projections are hashed, join-tree message passing stays linear in table size (O(∑_j (1 + deg(j))|C_j|), Proposition 2) and adds only 1.4 MB of active query-table memory over Static Acquisition. At m = 5, HyWit runs faster than Best-First Search (289 ms vs. 338 ms) while improving J@1 (13.9% vs. 12.1%). Offline controller training adds only 18.5 min (9.1%) to the 3.4 h shared backbone on one A100 GPU.

4. Comparison with Agentic LLM Baselines

We added four open-weight and commercial LLM/agent baselines under a standardized reference-free JSON witness schema (Appendix A.3, Figure 8; Section 5.7, Figure 7(c); Appendices F and I): Llama-3.1-70B-RAG, Qwen2.5-72B-RAG, GPT-4o Wit-Agent, and iterative Graph-R1 (GPT-4o). While LLM agents achieve competitive answer H@1 (22.1%–27.6%), they lag in executable witness recovery (10.6%–15.9% J@1) because autoregressive decoding frequently splices qualifiers across distinct observed records (Appendix I, Case 4). HyWit outperforms Graph-R1 by +5.5 pp J@1 (21.4% vs. 15.9%) at 97.1% lower median latency (0.168 s vs. 5.84 s).

We would truly appreciate it if you could find time to read our revised PDF. If our new experiments and clarifications resolve your concerns, we kindly ask you to consider raising your score. Thank you again for your constructive review!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.