A Foundation Model for Zero-shot Logical Query Reasoning

Authors: mikhail  galkin
jincheng  zhou
bruno  ribeiro
jian  tang
zhaocheng  zhu
eth  zurich
three  answ
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:12:29

Abstract: Complex logical query answering (CLQA) in knowledge graphs (KGs) goes beyond simple KG completion and aims at answering compositional queries comprised of multiple projections and logical operations. Existing CLQA methods that learn parameters bound to certain entity or relation vocabularies can only be applied to the graph they are trained on which requires substantial training time before being deployed on a new graph. Here we present UltraQuery, the first foundation model for inductive reasoning that can zero-shot answer logical queries on any KG. The core idea of UltraQuery is to derive both projections and logical operations as vocabulary-independent functions which generalize to new entities and relations in any KG.
With the projection operation initialized from a pre-trained inductive KG completion model, UltraQuery can solve CLQA on any KG after finetuning on a single dataset. Experimenting on 23 datasets, UltraQuery in the zero-shot inference mode shows competitive or better query answering performance than best available baselines and sets a new state of the art on 15 of them.

Main paper: 
 related work: 
 Complex Logical Query Answering. To the best of our knowledge, there is no existing approach for generalizable and inductive query answering where the method is required to deal with new entitis and relations at inference time.Due to the necessity of learning entity and relation embeddings, the vast majority of existing methods like GQE [19] , BetaE [25] , ConE [40] , MPQE [10] (and many more from the survey by Ren et al. [27] ) are transductive-only and tailored for a specific set of entities and relations. Among them, CQD [3] and QTO [5] are inference-only query answering engines that execute logical operators with non-parametric fuzzy logic operators (e.g., product logic) but still require pre-trained entity and relation embedding matrices to execute relation projections (link prediction steps). We refer the interested reader to the comprehensive survey by Ren et al. [27] that covers query answering theory, a taxonomy of approaches, datasets, and open challenges. × × × × × × Parametric, × × × CQD [3], FuzzQE [9], QTO [5] × × × × × × Fuzzy, ✓ GNN-QE [43], NodePiece-QE [14] ✓ × × × Fuzzy, ✓ ULTRAQUERY (this work) ✓ ✓ Fuzzy, ✓A few models [43, 14, 17] generalize only to new entities by modeling entities as a function of relation embeddings. Gebhart et al. [17] apply the idea of cellular sheaves and harmonic extension to translation-based embedding models to answer conjunctive queries (without unions and negations). NodePiece-QE [14] trains an inductive entity encoder (based on the fixed vocabulary of relations) that is able to reconstruct entity embeddings of the new graph and then apply non-parametric engines like CQD to answer queries against new entities. The most effective inductive (entity) approach is GNN-QE [43, 14] that parameterizes each entity as a function of the relational structure between the query constants and the entity itself. However, all these works rely on a fixed relation vocabulary and cannot generalize to KGs with new relations at test time. In contrast, our model uses inductive relation projection and inductive logical operations that enable zero-shot generalization to any new KG with any entity and relation vocabulary without any specific training.Inductive Knowledge Graph Completion. In CLQA, KG completion methods execute the projection operator and are mainly responsible for predicting missing links in incomplete graphs during query execution. Inductive KG completion is usually categorized [8] into two branches: (i) inductive entity (inductive (e)) approaches have a fixed set of relations and only generalize to new entities, for example, to different subgraphs of one larger KG with one set of relations; and (ii) inductive entity and relation (inductive (e, r)) approaches that do not rely on any fixed set of entities and relations and generalize to any new KG with arbitrary new sets of entities and relations.Up until recently, the majority of existing approaches belonged to the inductive (e) family (e.g., GraIL [29] , NBFNet [42] , RED-GNN [38] , NodePiece [13] , A*Net [44] , AdaProp [39] ) that generalizes only to new entities as their featurization strategies are based on learnable relation embeddings.Recently, the more generalizable inductive (e, r) family started getting more attention, e.g., with RMPI [18] , InGram [22] , ULTRA [15] , and the theory of double equivariance introduced by Gao et al. [16] followed by ISDEA and MTDEA [41] models. In this work, we employ ULTRA to obtain transferable graph representations and execute the projection operator with link prediction over any arbitrary KG without input features. Extending our model with additional input features is possible (although deriving a single fixed-width model for graphs with arbitrary input space is highly non-trivial) and we leave it for future work. 
preliminaries and problem definition: 
 We introduce the basic concepts pertaining to logical query answering and KGs largely following the existing literature [14, 27, 15] .Knowledge Graphs and Inductive Setup. Given a finite set of entities V (nodes), a finite set of relations R (edge types), and a set of triples (edges ) E = (V × R × V), a knowledge graph G is a tuple G = (V, R, E).G inf = (V inf , R, E inf ).The inference graph can be an extension of the training graph if V train ⊆ V inf or be a separate disjoint graph (with the same set of relations) if V train ∩ V inf = ∅. In CLQA, the former setup with the extended training graph at inference is tackled by InductiveQE approaches [14] .In the hardest inductive entity and relation (inductive (e, r)) case, both entities and relations sets are different, i.e., V train ∩ V inf = ∅ and R train ∩ R inf = ∅. In CLQA, there is no existing approach tackling this case and our proposed ULTRAQUERY is the first one to do so.First-Order Logic Queries. Applied to KGs, a first-order logic (FOL) query q is a formula that consists of constants Con (Con ⊆ V), variables Var (Var ⊆ V, existentially quantified), relation projections R(a, b) denoting a binary function over constants or variables, and logic symbols (∃, ∧, ∨, ¬).The answers A G (q) to the query q are assignments of variables in a formula such that the instantiated query formula is a subgraph of the complete, non observable graph Ĝ. Answers are denoted as easy if they are reachable by graph traversal over the incomplete graph G and denoted as hard if at least one edge from the non observable, complete graph Ĝ has to be predicted during query execution.For example, in Figure 2 , a query Which band member of Dire Straits played guitar? is expressed in the logical form as ?U : BandMember(Dire Straits, U )∧Plays -1 (Guitar, U ) as an intersection query. Here, U is a projected target variable, Dire Straits and Guitar are constants, BandMember and Plays are relation projections where Plays -1 denotes the inverse of the relation Plays. The task of CLQA is to predict bindings (mappings between entities and variables) of the target variable, e.g., for the example query the answer set is a single entity A q = {(U, Mark Knopfler)} and we treat this answer as an easy answer as it is reachable by traversing the edges of the given graph. In practice, however, we measure the performance of CLQA approaches on hard answers.Inductive Query Answering. In the transductive CLQA setup, the training and inference graphs are the same and share the same set of entities and relations, i.e., G train = G inf meaning that inference queries operate on the same graph, the same set of constants Con and relations. This allows query answering models to learn hardcoded entity and relation embeddings at the same time losing the capabilities to generalize to new graphs at test time.In the inductive entity (e) setup considered in Galkin et al. [14] , the inference graph extends the training graph G train ⊂ G inf but the set of relations is still fixed. Therefore, the proposed models are still bound to a certain hardcoded set of relations and cannot generalize to any arbitrary KG.In this work, we lift all the restrictions on the training and inference graphs' vocabularies and consider the most general, inductive (e, r) case when G inf ̸ = G train and the inference graph might contain a completely different set of entities and relation types. Furthermore, missing links still have to be predicted in the inference graphs to reach hard answers.Labeling Trick GNNs. Labeling tricks (as coined by Zhang et al. [37] ) are featurization strategies in graphs for breaking symmetries in node representations which are particularly pronounced in link prediction and KG completion tasks. In the presence of such node symmetries (automorphisms), classical uni-and multi-relational GNN encoders [21, 33, 32] assign different automorphic nodes the same feature making them indistinguishable for downstream tasks. In multi-relational graphs, NBFNet [42] and A*Net [44] apply a labeling trick by using the indicator function INDICATOR(h, v, r) that puts a query vector r on a head node h and puts the zeros vector on other nodes v. The indicator function does not require entity embeddings and such models can naturally generalize to new entities (while the set of relation types is still fixed). Theoretically, such a labeling strategy learns conditional node representations and is provably more powerful [20] than node-level GNN encoders. In CLQA, only GNN-QE [43] applies NBFNet as a projection operator making it the only approach generalizable to the inductive (e) setup [14] with new nodes at inference time. This work leverages labeling trick GNNs to generalize CLQA to arbitrary KGs with any entity and relation vocabulary.  
method: 
 We aim at designing a single foundation model for CLQA on any KG in the zero-shot fashion, i.e., without training on a target graph. In the CLQA literature [19, 26, 25, 3, 43] , it is common to break down query execution into a relation projection to traverse graph edges and predict missing links, and logical operators that model conjunction, disjunction, and union. The main challenge boils down to designing inductive projection and logical operators suitable for any entity and relation vocabulary.The vast majority of CLQA methods are inherently transductive and implement relation projections as functions over entity and relation embeddings fixed to a certain KG vocabulary, e.g., with scoring functions from KG completion methods [19, 3, 5] , geometric functions [26, 40] , or pure neural methods [2, 34] . The only method inductive to new entities [43] learns relation embeddings and uses those as a labeling trick (Section 3) for a GNN that implements the projection operator.As fixed relation embeddings do not transfer to new KGs with new relations, we adapt ULTRA [15] , an inductive approach that builds relation representations dynamically using the invariance of relation interactions, as the backbone of the relation projection operator thanks to its good zero-shot performance on simple KG completion tasks across a variety of graphs. ULTRA leverages theoretical findings in multi-relational link prediction [6, 20] and learns relation representations from a metagraph of relation interactions 3 . The meta-graph includes four learnable edge types or meta-relations (head-to-tail, tail-to-head, head-to-head, tail-to-tail) which are independent from KG's relation vocabulary and therefore transfer across any graph. Practically, given a graph G and projection query (h, r, ?), ULTRA employs labeling trick GNNs on two levels. First, it builds a meta-graph G r of relation interactions (a graph of relations where each node is a unique edge type in G) and applies a labeling trick to initialize the query node r. Note that |R| ≪ |E|, the number of unique relations is much smaller than number of entities in any KG, so processing this graph of relations introduces a rather marginal computational overhead. Running a message passing GNN over G r results in conditional relation representation which are used as initial edge type features in the second, entity-level GNN. There, a starting node h is initialized with a query vector from the obtained relation representations and running another GNN over the entity graph (with a final sigmoid readout) returns a scalar score in [0, 1] representing a probability of each node to be a tail of a query (h, r, ?).The only learnable parameters in ULTRA are four meta-relations for the graph of relations and GNN weights. The four meta-relations represent structural patterns and can be mined from any multi-relational KG independent of their entity and relation vocabulary. GNN weights are optimized during pre-training. Since the model does not rely on any KG-specific entity or relation vocabulary, a single pre-trained ULTRA model can be used as a zero-shot relation projection operator on any KG. Figure 3 (a) illustrates the intersection-projection query execution process where each projection step is tackled by the same inductive projection operator with initialization depending on the start anchor node or intermediate variables.The multi-source propagation issue. While it is tempting to leverage ULTRA pre-trained on multiple KG datasets for relation projection, there is a substantial distribution shift (Figure 3(b) ) between KG completion and CLQA. Specifically, KG completion is a special case of relation projection where the input always contains a single node. By comparison, in multi-hop complex queries, several likely nodes might have high intermediate scores and will be labeled with non-zero vectors leading to the multiple sources propagation mode where a pre-trained operator is likely to fail. To alleviate the issue, we experimentally study two strategies: (1) short fine-tuning of the pre-trained projection operator on complex queries (used in the main ULTRAQUERY model), or (2) use the frozen pre-trained operator and threshold intermediate scores setting all scores below 0 < k < 1 to zero (denoted as ULTRAQUERY LP). The insight is to limit the propagation to one or a few source nodes, thereby reducing the discrepancy between training and test distributions.Learnable logical operators parameterized by neural nets in many CLQA approaches [19, 26, 40, 2] fit a particular embedding space and are not transferable. Instead, we resort to differentiable but non-parametric fuzzy logics [31] that implement logical operators as algebraic operations (t-norms for conjunction and t-conorms for disjunction) in a bounded space [0, 1] and are used in several neuro-symbolic CLQA approaches [3, 43, 4, 5, 36] . ULTRAQUERY employs fuzzy logical operators over fuzzy sets x ∈ [0, 1] |V| as the relation projection operator assigns a scalar in range [0, 1] for each entity in a graph. The choice of a fuzzy logic is often a hyperparameter although van Krieken et al. [31] show that the product logic is the most stable. In product logic, given two fuzzy sets x, y, conjunction is element-wise multiplication x ⊙ y and disjunction is x + yx ⊙ y. Negation is often implemented as 1x where 1 is the universe vector of all ones. For second-and later i-th hop projections, we obtain initial node states h v by weighting a query vector r i with their probability score x v from the fuzzy set of a previous step:h v = x v r i .Following existing works [25, 43] , ULTRAQUERY is trained on complex queries to minimize the binary cross entropy lossEQUATIONwhere A q is the answer to the query q and p(a|q) is the probability of entity a in the final output fuzzy set. ULTRAQUERY LP uses a frozen checkpoint from KG completion and is not trained on complex logical queries. 
experiments: 
 Our experiments focus on the following research questions: (1) How does a single ULTRAQUERY model perform in the zero-shot inference mode on unseen graphs and queries compared to the baselines? (2) Does ULTRAQUERY retain the quality metrics like faithfullness and identify easy answers reachable by traversal? (3) How does the multi-source propagation issue affect the performance?Datasets. We employ 23 different CLQA datasets each with 14 standard query types and its own underlying KG with different sets of entities and relations. Following Section 3, we categorize the datasets into three groups (more statistics of the datasets and queries are provided in Appendix A):• Transductive (3 datasets) where training and inference graphs are the same (G train = G inf ) and test queries cover the same set of entities and relations: FB15k237, NELL995 and FB15k all from Ren and Leskovec [25] with at most 100 answers per query.• Inductive entity (e) (9 datasets) from Galkin et al. [14] where inference graphs extend training graphs (G train ⊂ G inf ) being up to 550% larger in the number of entities. The set of relations is fixed in each training graph and does not change at inference making the setup inductive with respect to the entities. Training queries might have more true answers in the extended inference graph.• Inductive entity and relation (e, r) (11 datasets): we sampled a novel suite of WikiTopics-QA datasets due to the absence of standard benchmarks evaluating the hardest inductive setup where inference graphs have both new entities and relations (G train ̸ = G inf ). The source graphs were adopted from the WikiTopics datasets [16] , we follow the BetaE setting when sampling 14 query types with at most 100 answers. More details on the dataset creation procedure are in Appendix A.Implementation and Training. ULTRAQUERY was trained on one FB15k237 dataset with complex queries for 10,000 steps with batch size of 32 on 4 RTX 3090 GPUs for 2 hours (8 GPU-hours in total). We initialize the model weights with an available checkpoint of ULTRA reported in Galkin et al. [15] . Following the standard setup in the literature, we train the model on 10 query types and evaluate on all 14 patterns. We employ product t-norm and t-conorm as non-parametric fuzzy logic operators to implement conjunction (∧) and disjunction (∨), respectively, and use a simple 1x negation. For the ablation study, ULTRAQUERY LP uses the same frozen checkpoint (pre-trained on simple 1p link prediction) with scores thresholding to alleviate the multi-source propagation issue (Section 4.1). More details on all hyperparameters are available in Appendix B.Evaluation Protocol. As we train an ULTRAQUERY model only on one FB15k237 dataset and run zero-shot inference on other 22 graphs, the inference mode on those is inductive (e, r) since their entity and relation vocabularies are all different from the training set.As common in the literature [25, 27] , the answer set of each query is split into easy and hard answers. Easy answers are reachable by graph traversal and do not require inferring missing links whereas hard answers are those that involve at least one edge to be predicted at inference. In the rank-based evaluation, we only consider ranks of hard answers and filter out easy ones and report filtered Mean Reciprocal Rank (MRR) and Hits@10 as main performance metrics.Other qualitative metrics include: (1) faithfullness [28] , i.e., the ability to recover easy answers reachable by graph traversal. Here, we follow the setup in Galkin et al. [14] and measure the performance of training queries on larger inference graphs where the same queries might have new true answers; (2) the ROC AUC score to estimate whether a model ranks easy answers higher than hard answers -we compute ROC AUC over unfiltered scores of easy answers as positive labels and hard answers as negative. (3) Mean Absolute Percentage Error (MAPE) [43] between the number of answers extracted from model's predictions and the number of ground truth answers (easy and hard combined) to estimate whether CLQA models can predict the cardinality of the answer set.Baselines. In transductive and inductive (e) datasets, we compare a single ULTRAQUERY model with the best reported models trained end-to-end on each graph (denoted as Best baseline in the experiments): QTO [5] for 3 transductive datasets (FB15k237, FB15k, and NELL995) and GNN-QE [14] for 9 inductive (e) datasets. While a single ULTRAQUERY model has 177k parameters, the baselines are several orders of magnitude larger with a parameters count depending on the number of entities and relations, e.g., a QTO model on FB15k237 has 30M parameters due to having 2000d entity and relation embeddings, and GNN-QE on a reference FB 175% inductive (e) dataset has 2M parameters. For a newly sampled suite of 11 inductive (e, r) datasets, we compare against the edge-type heuristic baseline introduced in Galkin et al. [14] . The heuristic selects the candidate nodes with the same incoming relation as the last hop of the query. More details on the baselines are reported in Appendix BIn the main experiment, we measure the zero-shot query answering performance of ULTRAQUERY trained on a fraction of complex queries of one FB15k237 dataset. Figure 1 measure the average MRR on 9 EPFO queries with projection, intersection, and union operators, and 5 negation queries with the negation operator, respectively.Averaged across 23 datasets, ULTRAQUERY outperforms available baselines by relative 50% in terms of MRR and Hits@10 on EPFO and 70% on negation queries (e.g., 0.31 vs 0.20 MRR on EPFO queries and 0.178 vs 0.105 on negation queries). The largest gains are achieved on the hardest inductive (e, r) datasets where the heuristic baseline is not able to cope with the task. On inductive (e) datasets, ULTRAQUERY outperforms the trainable SOTA GNN-QE model on larger inductive inference graphs and performs competitively on smaller inductive versions. On transductive benchmarks, ULTRAQUERY lags behind the SOTA QTO model which is expected and can be attributed to the sheer model size difference (177k of ULTRAQUERY vs 30M of QTO) and the computationally expensive brute-force approach of QTO that materializes the whole (V × V × R) 3D tensor of scores of all possible triples. Pre-computing such tensors on three datasets takes considerable space and time, e.g., 8 hours for FB15k with heavy sparsification settings to fit onto a 24 GB GPU. Still, ULTRAQUERY outperforms a much larger QTO model on the FB15k dataset on both EPFO and negation queries. The graph behind the NELL995 dataset is a collection of disconnected components which is disadvantageous for GNNs.We note a decent performance of ULTRAQUERY LP trained only on simple 1p link prediction and imbued with score thresholding to alleviate the multi-source message passing issue described in Section 4.1. Having a deeper look at other qualitative metrics in the following section, we reveal more sites where the issue incurs negative effects.Here, we study four aspects of model performance: the effect of the multi-source message passing issue mentioned in Section 4.1, the ability to recover answers achievable by edge traversal (faithfullness), the ability to rank easy answers higher than hard answers, and the ability to estimate the cardinality of the answer set.The multi-source message passing effect. The pre-trained ULTRA checkpoint used in ULTRAQUERY LP is tailored for singe-source message passing and struggles in the CLQA setup on later hops with several initialized nodes (Table 2 ). Training ULTRAQUERY on complex queries alleviates this issue as inductive (e) and 3 transductive datasets averaged across all 14 query types. Faithfullness, MRR (left): ULTRAQUERY successfully finds easy answers in larger inference graphs and outperforms trained GNN-QE baselines. Ranking of easy vs hard answers, ROC AUC (center): zero-shot inference methods slightly lag behind trainable GNN-QE due to assigning higher scores to hard answers. Cardinality Prediction, MAPE (right): ULTRAQUERY is comparable to a much larger trainable baseline QTO. In all cases, ULTRAQUERY LP is significantly inferior to the main model. shown in Figure 4 , i.e., while 1p performance of ULTRAQUERY LP is higher, the overall performance on EPFO and negative queries is lacking. In contrast, ULTRAQUERY trades a fraction of 1p singlesource performance to a much better performance on negative queries (about 2× improvement) and better performance on many EPFO queries, for example, on 3i queries. Besides that, we note that the zero-shot performance of both ULTRAQUERY models does not deteriorate from the increased size of the inference graph compared to the baseline GNN-QE.Recovering easy answers on any graph. Faithfullness [28] is the ability of a CLQA model to return easy query answers, i.e., the answers reachable by edge traversal in the graph without predicting missing edges. While faithfullness is a common problem for many CLQA models, Figure 5 demonstrates that ULTRAQUERY almost perfectly recovers easy answers on any graph size even in the zero-shot inference regime in contrast to the best baseline. Simple score thresholding does not help ULTRAQUERY LP to deal with complex queries as all easy intermediate nodes have high scores above the threshold and the multi-source is more pronounced.Ranking easy and hard answers. A reasonable CLQA model is likely to score easy answers higher than hard ones that require inferring missing links [14] . Measuring that with ROC AUC (Figure 5 ), ULTRAQUERY is behind the baseline due to less pronounced decision boundaries (overlapping distributions of scores) between easy and hard answers' scores. Still, due to scores filtering when computing ranking metrics, this fact does not have a direct negative impact on the overall performance.Estimating the answer set cardinality. Neural-symbolic models like GNN-QE and QTO have the advantage of estimating the cardinality of the answer set based on the final scores without additional supervision. As shown in Figure 5 , ULTRAQUERY is comparable to the larger and trainable QTO baseline on FB15k237 (on which the model was trained) as well as on other datasets in the zero-shot inference regime. Since cardinality estimation is based on score thresholding, ULTRAQUERY LP is susceptible to the multi-source propagation issue with many nodes having a high score and is not able to deliver a comparable performance. Varying the number of graphs in training. Figure 6 and Table 3 6 Discussion and Future WorkLimitations. The only parameterized component of ULTRAQUERY is the projection operator and, therefore, limitations and improvement opportunities stem from the projection operator [15] and its interplay with the multi-hop query answering framework. For instance, new mechanisms of tackling the multi-source propagation, better pre-training strategies, and scaling might positively impact the zero-shot CLQA performance. The support for very large KGs could be further improved by adopting more scalable entity-level GNN predictors like A*Net [44] or AdaProp [39] which have been shown to scale to graphs of millions of nodes. We are optimistic that ULTRAQUERY could scale to such graphs when integrated with those models.Conclusion and Future Work. We presented ULTRAQUERY, the first foundation model for inductive zero-shot complex logical query answering on any KG that combines a parameterized, inductive projection operator with non-parametric logical operators. Alleviating the multi-source message propagation issue is the key to adapt pre-trained projection operators into the multi-hop query answering framework. ULTRAQUERY performs comparably to or better than strong baselines trained specifically on each graph and at the same time retains key qualitative features like faithfullness and answer cardinality estimation. Having a single query answering model working on any KG, the scope for future work is vast as highlighted by Ren et al. [27] and includes, for example, better theoretical understanding of logical expressiveness bounds, supporting more query patterns beyond simple trees [35, 36] , queries without anchor nodes [7] , hyper-relational queries [1] , queries with numerical literals [11] , or temporal queries [23] .Impact Statement. We do not envision direct ethical or societal consequences of this work. Still, models capable of zero-shot inference on any graph might be applied to domains other than those designed by the authors. Positive impacts include saving compute resources and reducing carbon footprint of training specific models tailored for each graph.A.1 Dataset statistics First, Table 4 , Table 5 , and Table 6 provide the necessary details on the graphs behind the CLQA datasets. Then, Table 7 , Table 8 , and Table 9 list the query statistics. Transductive datasets are BetaE [25] datasets (MIT license), inductive (e) datasets are adopted from Galkin et al. [14] (CC BY 4.0 license) where validation and test inference graphs extend the training graph. The ratio denotes the size of the inference graph to the size of the training graph (in the number of nodes), that is, V inf /V train . In the following Appendix A.2 we provide more details in sampling 11 new inductive (e, r) datasets WikiTopics-CLQA (available under the CC BY 4.0 license). training 135,613 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 40,000 50,000 50,000 50,000 validation 6,582 10,000 10,000 10,000 10,000 10,000 10,000 10,000 10,000 1,000 1,000 1,000 1,000 1,000 test 5,446 10,000 10,000 10,000 10,000 10,000 10,000 10,000 10,000 1,000 1,000 1,000 1,000 1,000 113% training 115,523 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 40,000 50,000 50,000 50,000 validation 10,256 10,000 10,000 10,000 10,000 10,000 10,000 10,000 10,000 1,000 1,000 1,000 1,000 1,000 test 9,782 10,000 10,000 10,000 10,000 10,000 10,000 10,000 10,000 1,000 1,000 1,000 1,000 1,000 121% training 91,228 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 40,000 50,000 50,000 50,000 validation 12,696 10,000 10,000 10,000 10,000 10,000 10,000 10,000 10,000 5,000 5,000 5,000 5,000 5,000 test 14,458 10,000 10,000 10,000 10,000 10,000 10,000 10,000 10,000 5,000 5,000 5,000 5,000 5,000 133% training 75,326 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 40,000 50,000 50,000 50,000 validation 15,541 50,000 50,000 50,000 50,000 50,000 50,000 20,000 20,000 5,000 5,000 5,000 5,000 5,000 test 15,270 50,000 50,000 50,000 50,000 50,000 50,000 20,000 20,000 5,000 5,000 5,000 5,000 5,000 150% training 56,114 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 40,000 50,000 50,000 50,000 validation 16,229 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 5,000 5,000 5,000 5,000 5,000 test 17,683 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 5,000 5,000 5,000 5,000 5,000 175% training 38,851 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 40,000 50,000 50,000 50,000 validation 17,235 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 test 17,476 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 217% training 22,422 30,000 30,000 50,000 50,000 50,000 50,000 50,000 50,000 30,000 30,000 50,000 50,000 50,000 validation 18,168 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 test 16,902 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 300% training 11,699 15,000 15,000 40,000 40,000 50,000 50,000 50,000 50,000 15,000 15,000 50,000 40,000 50,000 validation 16,189 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 test 17,105 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 550% training 3,284 15,000 15,000 40,000 40,000 50,000 50,000 50,000 50,000 10,000 10,000 30,000 30,000 30,000 validation 13,616 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000 test 13,670 50,000 50,000 50,000 50,000 50,000 50,000 50,000 50,000 10,000 10,000 10,000 10,000 10,000Table 9 : WikiTopics-CLQA statistics: the number of queries generated per query pattern for each topic knowledge graph of WikiTopics [16] . Numbers are the same for both the training and inference graph. We follow the same 14 query patterns introduced by Ren and Leskovec [25] . 6 shows the statistics of the 11 topic-specific knowledge graphs in WikiTopics.We follow the procedures in BetaE [25] to generate queries and answers of the 14 query patterns using the knowledge graphs in WikiTopics. We name the resulting dataset WikiTopics-CLQA. For each topic T , we generate three sets of queries and answers (training, validation, test), using the training graph G inf and the test queries and answers for evaluating zero-shot inference performance. Table 9 shows the statistics of the WikiTopics-CLQA dataset.Both ULTRAQUERY and ULTRAQUERY LP are implemented with PyTorch [24] (BSD-style license) and PyTorch-Geometric [12] (MIT license). Both ULTRAQUERY and ULTRAQUERY LP are initialized from the pre-trained ULTRA checkpoint published by the authors and have the same GNN architectures with parameter count (177k). ULTRAQUERY is further trained for 10,000 steps on complex queries from the FB15k237 dataset. Hyperparameters of ULTRAQUERY and its training details are listed in Table 10 .ULTRAQUERY LP employs thresholding of intermediate fuzzy set scores as one of the ways to alleviate the multi-source propagation issue (Section 4.1). Generally, the threshold is set to 0.8 with a few exceptions:• 0.97 in NELL995 Below, we discuss the best available baselines for each dataset family.Transductive (3 datasets): QTO [5] . QTO requires 2000d ComplEx [30] entity and relation embeddings pre-computed for each graph, e.g., taking 30M parameters on the FB15k237 graph with 15k nodes. Further, QTO materializes the whole (V × V × R) 3D tensor of scores of all possible triples for each graph. Pre-computing such tensors on three datasets takes considerable space and time, e.g., 8 hours for FB15k with heavy sparsification settings to fit onto a 24 GB GPU.Inductive (e) (9 datasets): GNN-QE [43] . The framework of GNN-QE is similar to ULTRAQUERY but the backbone relation projection operator is implemented with NBFNet [42] which is only inductive to entities and still learns graph-specific relation embeddings. Parameter count, therefore, depends on the number of unique relation types, e.g., 2M for the FB 175% split with 436 unique relations.Inductive (e, r) (11 datasets): for newly sampled datasets, due to the absence of fully inductive trainable baselines, we compare against a rule-based heuristic baseline similar to the baseline in Galkin et al. [14] . The baseline looks up candidate entities that have the same incoming relation type as the current relation projection (note that the identity of the starting head node in this case is ignored). The heuristic filters entities into two classes (satisfying the incoming relation type or not), hence, in order to create a ranking, we randomly shuffle entities in each class. This baseline is non-parametric, does not require any training, and represents a sanity check of CLQA models. Still, as shown in Galkin et al. [14] , the baseline might outperform certain inductive reasoning approaches parameterized by neural networks.Table 11 corresponds to Figure 1 and Table 2 and provides MRR and Hits@10 results for ULTRA-QUERY, ULTRAQUERY LP, and Best Baseline for each dataset averaged across 9 EPFO query types and 5 negation query types. Figure 7 is the full version of Figure 4 and illustrates the performance of all 3 compared models on 9 inductive (e) datasets on 14 query types together with their averaged values (EPFO avg and neg avg, respectively). MRR Hits@10 MRR Hits@10 MRR Hits@10 MRR Hits@10 MRR Hits@10 MRR Hits@10 • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: Section 6. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Appendices A, B. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.We assume the presence of respective inverse relations r -1 .The meta-graph can be efficiently obtained from any KG.https://mila.quebec/https://www.calculquebec.ca/https://alliancecan.ca/ 
: 
 Complex logical query answering (CLQA) generalizes simple knowledge graph (KG) completion to more complex, compositional queries with logical operators such as intersection (∧), union (∨), and negation (¬). Such queries are expressed in a subset of first-order logic (FOL) where existentially quantified (∃) variables and given constants comprise relation projections (or atoms), and logical operators combine projections into a logical query (graph pattern). A typical example of a logical query [27] is presented in Figure 2 : ?U.∃V : Win(NobelPrize, V ) ∧ Citizen(USA, V ) ∧ Graduate(V, U ) where Win() is a relation projection, NobelPrize is a constant, and V is an existentially quantified variable.Due to the incompleteness of most KGs, these logical queries cannot be directly solved by graph traversal algorithms. Consequently, CLQA methods have to deal with missing edges when modeling the projection operators. The vast majority of existing CLQA methods [27, 26, 25, 3, 5] predict missing edges by learning graph-specific entity and relation embeddings making such approaches transductive and not generalizable to other KGs. A few approaches [43, 14, 17] are able to generalize query answering to new nodes at inference time but still need a fixed relation vocabulary.In this work, we focus on the hardest inductive generalization setup where queries and underlying graphs at inference time are completely different from the training graph, i.e., both entities and relations are new. Furthermore, we aim at performing CLQA in the zero-shot setting with one single model. That is, instead of finetuning a model on each target dataset, we seek to design a unified approach that generalizes to any KG and query at inference time. For example, in Figure 2 , the training graph describes academic entities with relations Win, Citizen, Graduate2 whereas the inference graph describes music entities with relations Band Member and Plays. The query against the inference graph ?U : BandMember(Dire Straits, U ) ∧ Plays -1 (Guitar, U ) involves both new entities and relations and, to the best of our knowledge, cannot be tackled by any existing CLQA method that learns a fixed set of entities or relation embeddings from the training graph.Contributions. Our contributions are two-fold. First, none of the existing CLQA methods can generalize to query answering over new arbitrary KGs with new entities and relations at inference time. We bridge this gap by leveraging the recent progress in inductive KG reasoning [15, 16] and devise ULTRAQUERY, the first foundation model for CLQA that generalizes to logical queries on any arbitrary KG with any entity and relation vocabulary in the zero-shot fashion without relying on any external node or edge features. ULTRAQUERY parameterizes the projection operator by an inductive graph neural network (GNN) and implements non-parametric logical operators with fuzzy logics [31] . The pre-trained projection operator [15] does not learn any graph-specific entity nor relation embeddings thanks to the generalizable meta-graph representation of relation interactions, and therefore enables zero-shot generalization to any KG.Second, in the absence of existing datasets for our inductive generalization setup, we curate a novel suite of 11 inductive query answering datasets where graphs and queries at inference time have new entity and relation vocabularies. Experimentally, we train a single ULTRAQUERY model on one dataset and probe on other 22 transductive and inductive datasets. Averaged across the datasets, a single ULTRAQUERY model outperforms by 50% (relative MRR) the best reported baselines in the literature (often tailored to specific graphs) on both EPFO queries and queries with negation. 
 
 Appendix:  


Decision: This work is built on top of the transferable graph representations from (ULTRA[15]), and fuzzy logics. In order to achieve multi-step reasoning it employees
1) inductive parametric projection operators (IPP, similar to those of ULTRA) to produce a scalar score for each node in KG given starting or intermediate node information.
2) non-parametric logical operators (fuzzy logics) to perform logic operation over sets of weights.

The projection operator is fine-tuned from the ULTRA model's project operations (cross entropy loss on the final answer) to bridge the gap between link prediction and CLQA.  Experiment on 23 datasets shows comparable (yet lower) performance on inductive (e,r) tasks, compared to Inductive(e) and transductive tasks.

All reviewers recognize the importance of the problem and the demonstrated capability. However, they also have concerns about the lack of clarity for the novelty and theoretical contribution, and the scalability with large KGs. The paper can benefit from more detailed analysis and explanation of the projection/logical operators and computational complexities.

Reviews: review: paper_summary: paper_summary: This paper proposes ULTRA QUERY, a foundation model for zero-shot logical query reasoning on knowledge graphs (KGs). Existing complex logical query answering (CLQA) methods are either transductive or only partially inductive, requiring training on each specific graph. ULTRA QUERY overcomes this limitation by deriving projection and logical operations as vocabulary-independent functions that generalize to new entities and relations in any KG. The model is pre-trained on a simple KG completion task and then fine-tuned on a single complex query dataset, enabling it to perform CLQA on unseen KGs in a zero-shot manner. Experiments show that ULTRA QUERY achieves competitive or better performance compared to baselines trained specifically on each dataset, setting a new state of the art on 15 out of 23 tested datasets.
strength_weakness: strength_weakness: 1. While the experiments cover a range of datasets, a more in-depth analysis of the model's behavior under different conditions (e.g., varying graph sizes, query complexity) could provide further insights.
2. The paper does not discuss the model's scalability to very large KGs, which is an important aspect for practical applications.
3. And the scalability of the model (parameters and performance) can be further discussed.
questions: questions: How the model scales as the pretraining data scales up?
limitations: limitations: The authors have made an effort to discuss the limitations of their work, particularly regarding the model's reliance on the pre-trained inductive KG completion model and the multi-source propagation issue.
paper_summary: paper_summary: The paper presents ULTRAQUERY, a groundbreaking model for zero-shot logical query answering on knowledge graphs. It introduces a novel approach that combines inductive reasoning with non-parametric fuzzy logics to generalize to new entities and relations without additional training. The model demonstrates competitive performance across various datasets and query types, setting new benchmarks in the field.
strength_weakness: strength_weakness: 1. While the model's generalizability is a strength, the complexity introduced by the inductive reasoning might make it challenging to scale or adapt to very large KGs.
2. The paper does not present formal theoretical results or proofs to support the empirical findings, which could have strengthened the contribution.
3. The reliance on a pre-trained model could lead to overfitting on the training dataset, potentially affecting the model's performance on unseen data. The paper could have provided more details on the computational efficiency of ULTRAQUERY, especially in the context of large-scale KGs.
questions: questions: 1. How does ULTRAQUERY handle extremely large KGs, and what are the scalability challenges?
2. Can the authors provide more insights into the decision-making process behind the choice of fuzzy logics for logical operations?
limitations: limitations: Applications to more general scenarios.
paper_summary: paper_summary: This paper proposes a new framework for the generalization of complex logical question answering (CLQA). Specifically, the authors handle an extreme situation where the knowledge graph at the test time is completely different from the training time, which requires the model to adapt well to new entities and relations. The authors implement a foundation model that can construct a relation graph for any type of relation for execution. The authors examine the foundation model on generalization between extremely different knowledge graphs, which shows advantages when understanding new relations is important.
strength_weakness: strength_weakness: While I am optimistic about accepting this paper, I find it hard to get the novelty of the proposed method, whose main difference from the previous ones is the ability to handle new relations. However, the contribution on this part is not clearly presented. I feel the main problem is the lack of a detailed description of the ULTRA method and how it is adapted to the foundation model. Also, the contribution beyond the ULTRA framework needs further explanation. Still, I am glad to accept this paper for its contribution of a generally generalizable CLQA model.
questions: questions: Please refer to the weakness part
limitations: limitations: Yes
paper_summary: paper_summary: This paper considers the inductive setting of complex logical query over incomplete knowledge graph, in which unseen entities and relations exist. To address this challenge but the particularly important setting, this paper generalizes the foundation model of knowledge graph completion Ultra and proposes UltraQuery. Experiments show that UltraQuery trained on FB15k-237 can achieve competitive performance across 22 out-of-distribution KG datasets and can zero-shot answer the logical query on other KG.
strength_weakness: strength_weakness: 1. I am concerning about the novelty of the proposed methods. While the results of UltraQuery is impressive, the zero-shot ability is naturally derived from the foundation model of KG completeness, Ultra. This extension reminds the extension NBF-NET to GNN-QE.
questions: questions: 1. The feature used in UltraQuery is the intersection between entity and relation, which deprecates the representation of the specified entity (relations) and can generalize the unseen entity (relation). I am wondering if UltraQuery can exploit the feature from entity (relation) like attributes, types, and so on to improve the performance by fine-tuning.

2. Will you present  the results of the setting providing in your further work? In terms of the query patterns, the results can be directedly evaluated without modifying the models.


[1] Hang Yin, Zihao Wang, Weizhi Fei, and Yangqiu Song. EFOk-cqa: Towards knowledge graph complex query answering beyond set operation. arXiv preprint arXiv:2307.13701, 2023.

[2] Hang Yin, Zihao Wang, and Yangqiu Song. Rethinking complex queries on knowledge graphs with neural link predictors. In The Twelfth International Conference on Learning Representa- tions, 2024. URL https://openreview.net/forum?id=1BmveEMNbG.

[3] Pablo Barcelo ́, Tamara Cucumides, Floris Geerts, Juan Reutter, and Miguel Romero. A neuro- symbolic framework for answering conjunctive queries. arXiv preprint arXiv:2310.04598, 2023.
limitations: limitations: None

Comments: title: The response
Response to Authors
comment: Thank you for your response! I don't have any concern.
Dear Reviewer 5vKU,

Thank you for the comments and suggestions for improving our paper. As the rebuttal deadline is approaching, we would like to ask whether our response and new experimental results addressed your concerns. We are happy to elaborate on any remaining questions.
Dear Reviewer vHv9,

Thank you for the comments and suggestions for improving our paper. As the rebuttal deadline is approaching, we would like to know whether our response addressed your concerns. We are happy to elaborate on any remaining questions.
Thanks for providing more details about the novelty and difference with important previous works. From your clarification, I get how your framework and implementation are novel against baselines. A possible way is to add which component in your framework addresses which issue in Table 1. Please consider adding these details to the main content of the paper.

Based on the rebuttal from the authors and opinions from other reviewers, I am glad to improve my confidence and score for a **clear acceptance** since no major issue is mentioned. I appreciate the authors' effort in establishing a solid work and defending it during the rebuttal period.