- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper introduces VASIL, a foundation model for Complex Logical Query Answering (CLQA) over knowledge graphs (KGs), targeting arbitrary Existential First-Order (EFO) query structures in a zero-shot setting, including unseen entities and relations. VASIL employs an autoregressive variable-resolution process in which a Query-Conditioned Compositional Reasoner labels the KG according to query atoms, updates entity and relation representations through message passing, and predicts distributions over mutually dependent variables. To support training without predefined query templates, the authors further propose a Dynamic Query Synthesizer that generates diverse training queries on the fly by combining random walks.
Critical strengths
VASIL demonstrates strong fully inductive generalization, outperforming UltraQuery across all 11 unseen WikiTopics graphs, with particularly substantial gains on multi-hop chain queries. Ablation results further suggest that its end-to-end design supports multi-hop reasoning even when trained only on 1-hop queries, while reducing training costs. Beyond performance, VASIL provides a flexible and broadly evaluated framework that natively handles complex query structures, including cycles, multi-edges, and multiple free variables, without decomposition or assignment search. Its template-free query synthesizer, extensive evaluation across 37 benchmarks and three task families, and comprehensive ablations further strengthen its practical value.
Critical weaknesses
VASIL decomposes queries and resolves variables step-by-step, running message passing over a newly labeled KG at each autoregressive step. While the paper mentions competitive inference times in an appendix, dynamically relabeling and aggregating messages across massive, real-world KGs for every subproblem could introduce severe latency bottlenecks.
The paper’s positioning against closely related work requires further clarification, particularly regarding its claim of being the first CLQA foundation model to support arbitrary query structures over unseen KGs. The paper lacks zero-shot comparisons of AnyCQ+ULTRA, which would provide a relevant test of its handling of multiple free variables. While differences in task formulation and architectural design are meaningful, their implications for relative capabilities remain unclear. Furthermore, CKGC shows strong performance, but it has not been empirically tested.
Questions for authors
-
How does the Dynamic Query Synthesizer construct training queries beyond those whose answers are directly derived from connected triplets in the KG? Does its reliance on queries with non-empty answer sets limit the diversity of synthesized queries or introduce biases that affect the model’s ability to handle queries with no valid answers at inference time?
-
Could the authors provide a controlled comparison with UltraQuery using the same four KGs and synthesized training queries, or evaluate VASIL trained on UltraQuery’s training data?
-
Could the authors clarify why AnyCQ, FIT/QTO with ULTRA, and AnyCQ with ULTRA are omitted from Table 1 and the experimental evaluation?
2 comments
Response to Reviewer GKHt (2/2)
Q1.
How does the Dynamic Query Synthesizer construct training queries beyond those whose answers are directly derived from connected triplets in the KG? Does its reliance on queries with non-empty answer sets limit the diversity of synthesized queries or introduce biases that affect the model’s ability to handle queries with no valid answers at inference time?
Response: As stated in Appendix D, we probabilistically remove the edges used to construct queries in the KG, allowing training queries whose answers are not directly derived from connected triplets. Furthermore, since VASIL is primarily designed for the CLQA ranking task, it does not explicitly assume queries with no valid answers. While VASIL can handle queries with no valid answers via score thresholding, developing a more principled approach to address unanswerable queries remains an important direction for future work (Lines 529–531).
Q2.
Could the authors provide a controlled comparison with UltraQuery using the same four KGs and synthesized training queries, or evaluate VASIL trained on UltraQuery’s training data?
Response: As shown in its official repository, UltraQuery utilizes an Ultra backbone pre-trained on the exact same four KGs used in our experiments. Thus, VASIL and UltraQuery are trained on the identical set of KGs. The key distinction lies in how training queries are constructed. VASIL leverages our dynamic query synthesizer (one of the core contributions of our work) to generate diverse queries directly from these KGs. Our synthesizer encompasses complex structures such as non-tree-shaped queries and queries with multiple free variables, which UltraQuery cannot directly process. More importantly, while UltraQuery is fine-tuned on FB15k-237-BetaE training queries that share the same templates as the tree-shaped evaluation queries, VASIL is never exposed to any benchmark training queries.
Q3.
Could the authors clarify why AnyCQ, FIT/QTO with ULTRA, and AnyCQ with ULTRA are omitted from Table 1 and the experimental evaluation?
Response: These methods are omitted from Table 1 and the experimental evaluation because applying them to the standard CLQA task is computationally impractical:
- FIT / QTO + Ultra: FIT and QTO operate on a neural adjacency matrix of size |R|×|V|×|V|, which contains the link predictor scores for all possible triples and is sparsified by a threshold. Ultra relies on a labeling trick that runs its GNN conditioned on each (head, relation) pair. Computing this matrix therefore requires re-encoding the graph with a separate GNN forward pass for every head entity and relation, i.e., |V|×|R| (≈6.9M on FB15k-237) forward passes. Even when the scores are computed on demand only for the intermediate candidates remaining after thresholding, the cost grows rapidly as the candidate sets become large.
- AnyCQ, AnyCQ+Ultra: AnyCQ must verify every candidate entity individually for each query. Standard CLQA benchmarks contain thousands to tens of thousands of candidate entities, so this per-candidate verification becomes prohibitively costly. The cost grows further with Ultra. As mentioned above, Ultra must re-encode the graph with a separate GNN forward pass for every link prediction call made during verification due to its labeling trick.
To quantify this, we estimated the total evaluation time on FB15k-237-BetaE with a single A6000 GPU, based on the average inference time over five queries per query type:
| Method | Time per Query | Total Time | vs. VASIL |
|---|---|---|---|
| AnyCQ | 4,868 s | 118.7k h (≈13.5 years) | ~10⁵× |
| AnyCQ + Ultra | 35,690 s | 870k h (≈99 years) | ~7×10⁵× |
| FIT + Ultra | 19.9 s | 486 h (≈20 days) | ~395× |
| QTO + Ultra | 31.7 s | 773 h (≈32 days) | ~630× |
| VASIL | 0.050 s | 1.23 h | 1× |
Notably, AnyCQ-based methods require 13 to nearly 100 GPU-years, and even the fastest alternative, FIT with Ultra, requires over 395× more time than VASIL. Thus, these methods are impractical for CLQA.
Response to Reviewer GKHt (1/2)
We appreciate the reviewer’s time and effort in reviewing our manuscript. Below, we provide our responses to the review comments. All line numbers refer to the revised manuscript. Our code is available at https://anonymous.4open.science/r/VASIL_3d7a/
W1.
Response: Resolving queries step-by-step is a widely adopted strategy in CLQA (e.g., CQD, GNN-QE, and UltraQuery). Moreover, VASIL groups variables into subproblems by their distance from the target variable and resolves the variables within each subproblem jointly. Thus, the number of autoregressive steps depends only on the maximum distance from the target variable in the query graph, which is a small constant (at most 4 in our benchmarks) regardless of the KG size.
Empirically, as reported in Appendix E, VASIL’s autoregressive decoding does not introduce a significant latency overhead compared to UltraQuery, while consistently outperforming UltraQuery across all settings in Tables 2, 3, and 4.
W2.
Response: As discussed in the Related Work (Lines 127–139), AnyCQ and VASIL address different problem settings. AnyCQ targets Boolean query evaluation, whereas VASIL targets the standard CLQA setting, where answers must be ranked among a large set of candidate entities.
Evaluating AnyCQ (with Ultra) under the standard CLQA setting requires individually verifying every candidate entity per query, making full-scale evaluation computationally infeasible. Specifically, evaluating all test queries on a single dataset (FB15k-237-BetaE) is estimated to take 870,459 GPU hours (~99 GPU-years) on an A6000 GPU, whereas VASIL completes it in just 1.23 GPU hours. Please read our response to Q3 for the detailed runtime analysis.
VASIL is the first CLQA method that can simultaneously (i) handle complex queries with arbitrary structures and (ii) transfer to unseen KGs in a zero-shot manner. AnyCQ is not a CLQA method, and applying it to CLQA is infeasible due to its limited scalability.
Revision: We revised the Related Work section (Lines 134-137) to include the impracticality of applying AnyCQ to the standard CLQA task.
W3.
Response: We found that the official implementation of CKGC uses both the training and validation graphs as the observed graph during testing, whereas the standard evaluation protocol followed by all other methods in Table 2 uses only the training graph. Since this provides CKGC with additional information unavailable to the other methods, its reported results are not directly comparable, and thus we did not include them in Table 2.