Zero-Shot Logical Reasoning for Arbitrarily Structured Queries on Knowledge Graphs

Real-world complex logical query answering (CLQA) requires reasoning over arbitrarily structured existential first-order (EFO) queries on unseen knowledge graphs (KGs). However, existing methods are often restricted to tree-shaped queries or fixed KGs. Moreover, they often rely on link predictors designed to predict a missing entity for a single triplet, making them suboptimal for queries involving multiple atoms that form complex structures. We propose VASIL, the first foundation model for CLQA designed to directly answer EFO queries with arbitrary structures in a zero-shot manner. Given an EFO query on a KG, VASIL autoregressively infers probability distributions of the variables while jointly predicting mutually dependent variables. At each step, it labels the entities and relations in the KG based on the atoms involving the variables being resolved and performs message passing over the labeled KG. The resulting representations are used to resolve the variables, yielding predictions conditioned on both the KG and the query. To train VASIL across diverse query structures, we construct queries by merging multiple random walks, a procedure that theoretically covers all conjunctive EFO query structures. Because variables are predicted based solely on the structures of the query and the labeled KG, VASIL can perform CLQA on KGs containing unseen entities and relations. Experiments on 37 benchmarks show that VASIL outperforms baselines in answering queries requiring reasoning beyond simple link prediction, including non-tree-shaped or multi-free-variable queries.