A Foundation Model for Zero-shot Logical Query Reasoning
Authors: Mikhail Galkin
Jincheng Zhou
Bruno Ribeiro
Jian Tang
Zhaocheng Zhu
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
knowledge graph
knowledge graph reasoning
complex logical query answering
query reasoning
Primary area: graph_neural_networks
TL;DR: A single pre-trained model for zero-shot complex logical query answering on any knowledge graph

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.

A Foundation Model for Zero-shot Logical Query Reasoning
Mikhail Galkin', Jincheng Zhou?; Bruno Ribeiro", Jian Tang*45, Zhaocheng Zhu Intel AI Lab, PPurdue University, 'Mila Québec Al Institute, *HEC Montréal, 'CIFAR AI Chair Universitéé de Montréal
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 ULTRA QUERY, the first foundation model for inductive reasoning that can zero-shot answer logical queries on any KG. The core idea of ULTRAQQ ULERAQUERY is to derive both projections and logical operations oocaullay-independeett funcctions which generalize 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 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 new state of the art on 15 of them.
ULTRAQURRY (EPPO)
UrrRAQuRay (EPFO)
(EPFO) Vegation avg
0.8
Inductive (e.t)
Inductive
Tzaueduuciiv
0.7
0.5
MRR
0.4
0.3
0.2
0.1
WT
WT intra
WT people
WT health
WT tax
WT sport
WT art
WT award
WT edu
org
550
FB 300
FB 217
FB 175
FB 150
FB 133
FB 121
FB 113
108
FB15K
NELL995
FB15k237
Average
WT
Dataset
Figure 1: Zero-shot query answering performance (MRR, higher better) of single ULTRAQUERY model trained one FB 1:2277 queries dataset compared to the best available baselines and ablated ULTRAQUERY LP on 23 datasets. EPFO the average of query types with (A, V) operators, Negation is the average of 5 query types with the negation operator (-). On average, single ULTRAQUERY model outperforms the best basclines trained specifically on each dataset. More results presented in Table and Appendix C.
"Work done during the intersship at Intel. Code: https://github.ccmm hwg.ghhhw....oepppppppppeeerrnna
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Complex logical query answering (CLQA) gen- eralizes simple knowledge graph (KG) comple- tion to more complex, compositional queries with logical operators such as intersection (A), union (V), and negation (-). Such queries are expressed in a subset of first-order logic (FOL) where existentially quantified (3) vari- ables and given constants comprise relation projections (or atoms), and logical operators combine projections into a logical query (graph pattern). A typical example of logical query [27] is presented in Figure 2: 2UEV Win(XobelPrize, V) Citizen (USA, V) A Graduate V U) where Win() is a relation pro- jection, Nobel is constant, and V is existentially quantified variable.
Where did US citizens with Nobel Prize graduate? (ip)
--00DVV Win(NooeiPrize V) USSA A Graduato(V U)
win
Einstein
University
Nobel Prize
of Zurich
citieen
ETH Zurich
graduacs
Feynman
Princctton
Training graph query
ULTRA QUERAQQERY
Inference graph + query
Dire Straits
band member
Knopfler
Gultar
John IUsieey
Bass
arowers
Which band momber of Dire Stroits played gultar? (20
Due to the incompleteness of most KGs, these logical queries cannot be directly solved by graph traversal algorithms. CLQA methods have to deal with missing edges when modeling the projection operators. The vast majority of existing CLQQA 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 fixed relation vocabulary.
g 20
(enndMeemer Dire Straits, U.) A Plays" (Giitar U))
The inductive logical query answering setup where training and inference graphs (and queries) have different entity and relation vocabu- laries. We propose single model (ULTRAQUERY that zero-shot generalizes to query answering on any graph with new entity or relation vocabulary at inference time.
Figure 2:
Consequently,
In this work, we focus on the hardest inductive generalization setup where queries and underlying graphs 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 each target dataset, we seek to design 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, Graduate² 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 -a (Gui 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 UI.TRAQUERY 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. ULTTRAQUERY parameterizes the projection operator by an inductive graph neural network (GNN) and implements non-parametric logical operators with fuzzy logics [3]]. 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 UL.TRQUERR dataset and probe on other 22 transductive and inductive datasets. Averaged across the datasets, single ULTR AQURRYYRY model outperforms by 50% (relative MRR) the best reported baselines in the literature (often tailored specific graphs) on both EPFO queries and queries with negation.
model on one
We assume the presence of respective inverse relations r

---

2 Related Work
Complex Logical Query Answering. To the best of our knowledge, there is existing approach for generalizable and inductive query answering where the method 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 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-paraman pan--aarmttrcc 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, taxonomy of approaches, datasets, and open challenges.
A few models [43, 14, 17] generalize only to new entities by modeling entities as function of relation embeddings. Gebhart et al. [17] ap- ply the idea of cellular sheaves and harmonic ex- tension to translation-bass to answer conjunctive queries (without unions and negations). NodePiece-OO QE [14] trains an inductive entity encoder (based on the fixed vo- cabulary of relations) that able to reconstruct entity embeddings of the new graph and then ap- ply non-parametric engines like CQD to answer queries against new entities. The most effeectiee 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 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.
Table 1: Comparison with existing CLQA ap- proaches. Ind. denotes inductive generalization to new entities (e) and relations (r). ULTRAQUERY is the first inductive method the generalizes queries
embedding models
over new entities and relations at inference time.
Method
Ind. Ind.
Ind. Logical Ops
Query2Box [26]. BetaE [25]
Parametric, X
CQD [3], FarzQE 19), QTO
X
X
Pazzy,
GNN-QE (43), NodePisce-QEE QE (14)
Fuzzy,
ULTRAQUERY (this work)
Puzzy,
fixed relation vocabulary and cannot generalize to
Inductive Knowledge Graph Completion. In CLQA, KG completion methods execute the projec- tion 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.. GralL [29], NBFNet [42], RED-GNI [38], NodePiece [13], A "Net [44], AdaProp [39]) that general- izes only to new entities as their featurization strategies are based on learnable relation embeddings.
Recently, the more generalizable inductive (e,r) r) family started getting more attention, egg., 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 single fixed-width model for graphs with arbitrary input space highly non-trivial) and we leave it for future work.
3 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 finite set of entities V (nodes), a finite set of relations R (edge types), and set of triples (edges) & = (V x x V). knowledge graph g is tuple G = (V, R, E). The simplest transductive setup dictates that the graph at training time
3

---

Guain = (Virain: Ririin ) and the graph at inference (validation or test) time Ging (Vig, Ring End) are the same, i.e., A Ginz By default, we assume that the inference graph Gor is an incomplete part of a larger, non observable graph Geg with missing triples to be predicted at inference time. In the inductive setup, in the general case, the training and inference graphs are different, Grain o Ginf In the easier inductive entity (inductive (e)) setup tackled by most of the KG completion literature, the relation set fixed and shared between training and inference graphs, i.e., Grain = (Viraie R, Eirain) and Giny = (Ving R. Emr). The inference graph can be an extension of the training graph if Virain S Vin or be a separate disjoint graph (with the same set of relations) if Virain n Viny Ø. In CLQA, the former setup with the extended training graph at inference is tackled by Inductive approaches [14].
In the hardest inductive entity and relation (inductive (c, r)) case, both entities and relations sets are different, i.e., Viniin n Vin = Ø and Rimin n Ran = 2. 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 formula that consists of constants Con (Con C V), variables Var (Var C V, existentially quantified), relation pro- jections R(a, b) denoting a binary function over constants or variables, and logic symbols (3, A, V, -). The answers (g))) to the query q assignments of variables in formula such that the instantiated query formula is a subgraph of the complete, non observable graph G. 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, query Which band member of Dire Straits played guitar? is expressed in (Dire the logical form as ?U: BandMember (Dire Straits, AP)yys - (Guitar, query. Here, U is projected target variable, Dire Straits and Gui tar are constants, BandMember and Plays are relation projections where Plays 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, {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.
P U) as an intersection
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., Gmuin = Gng 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 new graphs at test time.
In the inductive entity (e) setup considered in Galkin et al. [14], the inference graph extends the training graph Girain Imy 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 Gin * Grnai 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 partieularly pronounced in link pre- diction and KG completion tasks. In the presence of such node symmetries (aulomorphismss) 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 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 fiunction 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 provably more powerful [20] than nove-level GNN encoders. In CLQA, only GNN-QE [43] applies NBFNet as 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 CL.QA to arbitrary KGs with any entity and relation vocabulary.

---

inductive parameenic projection
Non-parammetric
Inductive parametric projection operator
First-hop projection: one is labeled with a query vector
intersect, incersect.
graduate
citizen
Inductive parametric projection operator
Tuzzy logics
Next hops projections: several nodes are labeled with weighted query
(product product norm, nogationn
0.8
Figure 3: (a) Example of ip query answering with ULTRAQUERY: the inductive parametric projection operator (Section 4.1) executes relation projections on any graph and returns scalar score for each entity; the scores are aggregated by non-paree te--aarmmerri logical operators (Section 4.2) implemented with fuzzy logics. Intermediate scores are used for weighted initializion of relation projections on the next hop. (b) The multi-source propagation issue with a pre-trained link predictor for relation projection: pre-training on Ip link prediction is done in the single-source labeling mode (top) where only one query node is labeled with a non-zero vector; complex queries at later intermediate hops might have several plausible sources with non-zero initial weights (bottom) where pre-trained operator fails.
Method
We aim at designing single foundation model for CLQQA on any KG in the zero-shot fashion, ie., without training target graph. In the CLQQA 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.
4.1 Inductive Relation Projection
The vast majority of CLQA methods are inherently transductive and implement relation projections as functions over entity and relation embeddings fixed to 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 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 rela- tion interactions, as the backbone of the relation projection operator thanks to its good zero-shot performance on simple KG completion tasks across variety of graphs. ULTRA leverages theoretical findings in multi-relational link prediction [6, 20] and learns relation representations from meta- graph of relation interactions'. The meta-graph includes four learnable edge types or meta-relations (heud-to-tail,, tail-tohhead, 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, ?). ULTRA employs labeling trick GNNs two levels. First. it builds G, of relation interactions (a graph of relations where each node is a unique edge type in 9) and applies 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 rather marginal computational overhead. Running message passing GNN over G. results conditional relation representation which are used as initial edge type features in the second, entity-level GNN. There, starting node h initialized with query vector from the obtained relation representations and running another GNN over the entity graph (with final sigmoid readout) returns scalar score in [0, 1] representing probability of each node be tail of query (h,r,?)
meta-graph
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
Thhe geta-graph be efficiently obtained from any KG.
5

---

multi-relational KG independent of their entity and relation vocabulary. GNN weights are optimized during pre-training. Since the model does not not rely on any KG-specific entity or relation vocabulary, single pre-trained UI.TRA model can be used as zero-shot relation projection operator any KG. Figure 3(a) illustrates the intersection- pnrneecctooorrojcttionn 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 a substantial distribution shift (Figure 3(b)) between KG completion and CLQA. Specifically, KG completion is special case of relation projection where the input always contains 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 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 ULTRAQUERR AQUERY model), or (2) use the frozen pre-trained operator and threshold intermediate scores setting all scores below 0 < k < I to zero (denoted as ULTRAQUERY LP). The insight is to limit the propagation to one or few source nodes, thereby reducing the discrepancy between training and test distributions.
4.2 Inductive Logical Operations
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 con-parametric fuzzy logics [31] that implement logical operators algebraic operations (t-norms for conjunction and t-conorms for disjunction) in a bounded space [0, 1] and are used in several neuro- symbolyymoolic CLQA approaches [3, 43, 4, 5, 36]. ULTRAQUERY employs fuzzy logical operators over fuzzy sets E [0, 1] VI the relation projection operator assigns scalar in range [0, 1] for each entity graph. The choice of 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 æ, y. conjunction is element-wist wise multiplication æ 3 y and disjunction is æ + y x O y. Negation is often implemented as 1 - where is the universe vector of all ones. For second- and later i-th hop projections, we obtain initial node states h, by weighting a query vector r; with their probability score v. from the fuzzy set of previous step: h, T.
4.3 Training
Following existing works [25, 43], ULTRAQUERY is trained complex queries to minimize the binary cross entropy loss
C
Σ READ
logp(ala) - AV
1
log(1 - peg''-(a'lep O'EVIA,
Σ
(I)
Agp
where Ag is the answer to the query g and p(a/g) is the probability of entity a in the final output fuzzy set. ULTTRAQUERY L.P 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 single ULTRAQUERY model perform in the zero-shot inference mode on unseen graphs and queries compared to the base- lines? (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?
5.1 Setup and Datasets
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 (Grain = Tiy) 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 (Gmain C (in)) 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- QAA datasets due to the absence of standard benchmarks evaluating the hardest inductive setup where inference graphs have both new entities and relations (Graii * Gin)). The source graphs were adopted from the WikiTopiee 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 FB I 5k237 dataset with complex queries for 10,000 steps with batch size of 32 on 4 RTX 3090 GPUs for 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, evaluate on all 14 patterns. We employ product f-norm and r-conorm as non- non-parametric fuzzy logic operators to implement conjunction (A) and disjunction (V), respectively, and use simple 1 negation. For the ablation study, ULTRAQUERY I.P uses the same frozen checkpoint (pre-trained on simple /p link prediction) with scores thresholding alleviate the multi-source propagation issue (Section 4.... More details on all hyperparameters are available in Appendix B.
train the model on 10 query types and
Evaluation Protocol. As we train an ULTRAQUERY model only one FB15K237 dataset and run zero-shot inference on other 22 graphs, the inference mode on those is inductive (e,r) 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. Fasy 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 metries.
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 model ranks easy answers higher than hard answers we compute ROC AUC over wnfiltered scores of easy answers 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 CL.AA 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 (FB1 15315,237, FB 15k, and NELL995) and GNN- QE [14] for 9 inductive (e) datasets. While single ULTRAQUERY model has 177k parameters, the baselines are several orders of magnitude larger with parameters count depending on the number of entities and relations, e.g., QTO model on FB15k237 has 30M parameters due to having 2000d entity and relation embeddings, and GNN-QE on 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 B
5.2 Main Experiment: Zero-shot Query Answering
In the main experiment, we measure the zero-shot query answering performance of ULTRAQUERY trained on a fraction of complex queries of one FB15k220 15337 dataset. Figure and Table 2 illustrate the comparison with the best available baselines and ablated ULTRAQUERY LP model on 23 datasets split into three categories (transductive, inductive (c), and inductive (e, r)). For each dataset, we
7

---

Table 2: Zero-shot inference results of ULTRAQUERY and ablated ULTRAQUERY LP on 23 datasets compared to the best reported baselines. ULTRAQUERY was trained on one transductive FB 15k237 dataset, ULTRAQUERY LP was only pre- pre-trained on KG completion and uses scores thresholding. The no thrs. version does not use any thresholding of intermediate scores (Section 1) The best baselines trainable each transductive and inductive (e) dataset, and the non-parametric heuristic baseline
on inductive (e, r) datasets.
Inductive (e.r)
Inductive
Trunsdactive
Total
123 datwees)
Model
EPFO
EPPO
EPFO avg
EPFO
MRR
He
MRR
MRR
11:010
MRR
H0 10
MRR
166:10
MRR
H 10
MRR
H0010
MRR
160:00
Best baselaee
0.014
0,029
0.004
0.007
0.328
0.469
0.176
0.297
0.468
0.603
0.259
0.409
0.196
0.276
0.105
0.173
ULTRAQQURYY B-ahot
0.250
0.380
0.312
0.139
0.362
0.517
0.340
0.309
0.432
ULTRAQUERY
0.268
0.409
0.277
0,988
0.191
0.150
0.279
0.400
ULTRAQUaRY ttrs.
0.227
0.331
0.138
0.246
0.085
0.167
0.251
0.417
0.127
0.242
0.367
0.161
GNN-QE
QUERAUURYY 1.P
ULIRAQURRY
query- EPPO Ang
quisy bog 2Vg
query 1p
Quer 31
0.4
0.2
100
200
300
400
500
100
2.00
2003
100
500
100
200
300
400
100
200
300
500
Tistwett Tustin
Thetentt Rastin
Thanwert Radiin
Thatwert Ration
Figure 4: Mitigation of the multi-source message passing issue (Section 4) with ULTRAQUERY: while ULTRAQUERY LP (pre-trained only on Ip link prediction) does reach higher 1p query performance (center right), it underperforms on negation queries (center left). ULTRAQUERY adapts to the multi- source message passing scheme and trades a fraction of Ip query performance for better averaged EPFO, e.g., on the 3i query (right), and negation queries performance. More results are in Appendix C.
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 re,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 benchmarks, ULTR AQUERY 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 x V x 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 15k with heavy sparsification settings to fit onto a 24 GB GPU. Still, ULTRAQUERY outperforms a much larger QTO model on the FB 15k dataset both EPFO and negation queries. The graph behind the NELL995 dataset is collection of disconnected components which is disadvantagoous for GNNs.
smaller inductive versions. On transductive
We note a decent performance of ULTRAQUERY LP trained only on simple Ip 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.
5.3 Analysis
Here, we study four aspects of model performance: the effeet of the multi-source message passing issue mentioned in Section 4. 1, the ability to recover answers achievable by edge traversal (faith- fullness), the ability 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 IP tailored for singe-source message passing and struggles the CL.QA setup on later hops with several initialized nodes (Table 2). Training ULTRAQUERY on complex queries alleviates this issue as
8

---

Quertes on Cragh (1)
Banking Eayy Answens (Tes (f)
Cardmolry Prodiction Droe (4)
QTO
MAPP
0.9
145
Dumaaauas Le
6.6
A0C
353
100
ROC
302
GXS-QQE
NAPS
100
2.1
3311
430
200
D00
203
300
PUST4227
NELLUCC
3e fiee Dicamet Ratic
Indlative Ditaact Rorio
Tremdixcive Datase
Figure 5: Qualitative analysis on 9 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. all cases, ULTRAQUERY LP is significantly inferior to the main model.
shown Figure 4, ie., while 1p performance of ULTRAQUERY LP is higher, the overall performance on EPFO and negative queries is lacking. In contrast, UUTRA trades a fraction of 1p single- source performance to a much better performance on negative queries (about 2x 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 any graph size even in the zero-shot inference regime in contrast to the best baseline. Simple score thresholding does not help ALLTRAQUERY 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 Figure 5, ULTRAQUERY is comparable baseline on FB 15k237 (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 high score and is not able to deliver a comparable performance.
the larger and trainable QTO
query type cpfo
Varying the number of graphs in training. Figure 6 and Table report the inductive in- ference CLQA performance depending on the number of KGs in the training mixture. The was trained on queries from the FB FB15k237. In order to maintain the zero-shot inductive inference setup on 11 inductive re, and 9 inductive (e) datasets, we trained new model versions on the rest of BetaE datasets, that is. ULTRAQUERY 2G combines FB15k233 and NELL995 queries (trained for 20k steps), ULTRAQUERY 3G com- bines FB1 15223,, NELL995, and FB queries (trained for 30k steps). The most noticeable im- provement of 2G and 3G versions is the increased MRR and Hits @ 10 on EPFO queries (9 query
nog
0.3
0.4
MRR
H
original
0.2
0.3
# graphs
# graphs
Figure 6: Average MRR (left) and Hits 10 (right) of 9 inductive (e) and 11 inductive (e,r) CLQA datasets for EPFO and negation queries depending on the number of graphs in the training mix.

---

Table 3: Zero-shot inference results (on 20 inductive datasets) of ULTRAQUERY trained on 1, 2, and 3 datasets, respectively. The biggest gains of the 2G model are in bold.
Inductive (e,r) (11 datasets)
Inductive (+) (9 datasets)
Total Average (20 datasets)
Model
EPFO avg
nog avg
EPFO avg
nog avg
EPFO avg
nog avg
MRR
H@10
MRR
H6 10
MRR
H@ 10
MRR
H@ 10
MRR
H@10
MRR
H 10
ULTRAQUERY IG
0,280
0.380
0.193
0.288
0.312
0.467
0.139
0.262
0.296
0.423
0.166
0.275
ULTRAQUERY 2G
0.310
0.413
0.187
0.275
0.307
0.463
0.130
0.244
0.308
0.438
0.158
0.260
ULIRAQUERY 3G
0,304
0:402
0.195
0.292
0.292
0.438
0.127
0.239
0.298
0.420
0.161
0.265
types) on 11 inductive (e, r) datasets yielding about 10% gains. On 9 inductive (e) datasets the perfor- mance is either on par with the IG version or a bit lower. Averaged across 20 datasets, the 2G version exhibits the best EPFO performance at the cost of slightly reduced negation query performance.
Discussion and Future Work
L Limitations. The only parameterized component of ULTRRAQURRY 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 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 [1 I. 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.
Acknowledgements
This project is supported by Intel-Mila partnership program, the Natural Sciences and Engineering Research Council (NSERC) Discovery Grant, the Canada CIFAR AI Chair Program, collaboration grants between Microsoft Research and Mila, Samsung Electronics Co., Ltd., Amazon Faculty Research Award, Tencent AI Lab Rhino-Bird Gift Fund and a NRC Collaborative R&D Project (A14D-CORE-06) This project was also partially funded by IVADO Fundamental Research Project grant PRF-2019-3588 139727. The computation resource of this project is supported by Mila", Calcul Québec and the Digital Research Alliance of Canada
This work was funded in part by the National Science Foundation (NSF) awards, CCF-1918483 CAREER I1S-1943364 and CNS-2212160) Amazon Research Award, AnalytiXIN, and the Wabash Heartland Innovation Network (WHIN). Computing infrastructure was supported in part by CNS- 1925001 (CloudBank). Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.
httpae:///mlaauuueeeeeeeee 'httpa://www wwwpw.callooo www.uuueeeec.ccccccooocccmmm...e ca/ 'tttps:/alllaancecan ca/
10

---

References
[1] Dimitrios Alivanistos, Max Berrendorf, Michael Cochez, and Mikhail Galkin. Query embedding on hyper-relational knowledge graphs. In International Conference Learning Representations, 2022.
[2] Alfonso Amayuelas, Shuai Zhang, Xi Susie Rao, and Ce Zhang. Neural methods for logical reasoning over knowledge graphs. International Conference on Learning Representations, 2022.
[3] Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021.
[4] Erik Arakelyan, Pasquale Minervini, Daniel Daza, and Michael Cochez Isabelle Augenstein. Adapting neural link predictors for data-efficient complex query answering. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: /ttpr/vieeee......./ net/forum? 1ttiidd1111ppTT77
[5] Yushi Bai, Xin Lx, Juanzi Li, and Lei Hou. Answering complex logical queries on knowledge graphs via query computation tree optimization. In Proceedings of the 40th International Conference on Machine Learning, pages 1472-1491, 2023. URL httpt:://prroceedinggg mlr. wwwpppeess/v///eeeeeeeee ht///ba1213 chml.
[6] Pablo Barcelo, Mikhail Galkin, Christopher Morris, and Miguel Romero Orth. Weisfeiler and leman go relational. In The First Learning on Graphs Conference, 2022. URL https: //openreview met/fforrmiddd__Thhhhpp
[7] Pablo Barceló, Tamara Cucumides, Floris Geerts, Juan Reutter, and Miguel Romero. A neuro- symbolic framework for answering conjunctive queries. arXiv preprint arXiv:2310.04500 2023.
[8] Mingyang Chen, Wen Zhang, Yuxia Geng, Zezhong Xu, Jeff Z Pan, and Huajun Chen. Gen- eralizing to unseen elements: A survey on knowledge extrapolation for knowledge graphs In Proceedings of the Thirty- International Joint Conference on Artificial Intelligence, IJCAI-23, pages 6574 6582, 2023.
[9] Xuelu Chen, Ziniu Hu, and Yizhou Sun. Fuzzy logic based logical query answering on knowledge graphs. In Thirty-Sithh AAAI Conference Artificial Intelligence, AAAI, pages 3939-3948 AAAI Press, 2022.
[10] Daniel Daza and Michael Cochez. Message passing query embedding. Proceedings of the ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020.
[11) Caglar Demir, Michel Wiebesiek, Renzhong Lu, Axel-Cyrille Ngonga Ngomo, and Stefan Heindorf. LitCQD: Multi-hop reasoning in incomplete knowledge graphs with numeric literals. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 617-633, 2023.
[12] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning Graphs and Manifolds, 2019.
[13] Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L. Hamilton. Nodepiece: Compo- sitional and parameter-efficient representations of large knowledge graphs. In International Conference on Learning Representations, 2022. URL https:// wtw.:eerrriiii..ee/ouuunnn net/forum? id=xMJWDKJnFSW..
[14] Mikhail Galkin, Zhaocheng Zhu, Hongyu Ren, and Jian Tang. Inductive logical query answering in knowledge graphs. In Advances in Neural Information Processing Systems, 2022.
[15] Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. The Twelfih International Conference on Learning Representations, 2024. URL https: https:// //opp//////eeeeveer net test//orumidddjjooooooo
11

---

[16] Jianfei Gao, Yangze Zhou, Jincheng Zhou, and Bruno Ribeiro. Double equivariance for inductive link prediction for both new nodes and new relation types. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
[17] Thomas Gebhart, Jakob Hansen, and Paul Schrater. Knowledge sheaves: A sheaf- theoretic framework for knowledge graph embedding. In Proceedings of The 26th International Con- ference on Artificial Intelligence and Statistics. PMLR, 2023. URL https://proceeddngs mlr. press/v206/ gebhart23a..n ttm..
(18) Yuxia Geng, Jiaoyan Chen, Jeff Z. Pan, Mingyang Chen, Song Jiang, Wen Zhang, and Huajun Chen. Relational message passing for fully inductive knowledge graph completion. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 1221-1233, IEEE, 2023.
[19] Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In Advances in Neural Information Processing Systems, volume 31, 2018.
[20] Xingyue Huang, Miguel Romero Orth, Ismail Ilkan Ceylan, and Pablo Barcelo. theory of link prediction via relational weisfeiler-leman on knowledge graphs. In shirth-seventh Conference on Neural Information Processing Systems, 2023. URL //tpnreve/ppeeevieeee. httppparrevee..eee/forrr.. net/forum? 4d=7hL12Nrkt5.
[21] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017. URL https:
/ //openreview weet/forrmmiddSJJ4ayyl/
[22] Jaejun Lee, Chanyoung Chung, and Joyce Jiyoung Whang. InGram: Inductive knowledge graph embedding via relation graphs. In Proceedings of the 40th International Conference on Machine Learning, pages 18796-18809, PMLR, 2023. URL https: httpp:s/pppoceednng....m mml.. press/v202/lee/ html.
[23] Xueyuan Lin, Haihong E, Chengjin Xu, Gengxian Zhou, Haoran Luo, Tianyi Hu, Fenglong Su, Ningyuan Li, and Mingzhi Sun. TFLEX: Temporal feature-logic embedding framework for complex reasoning over temporal knowledge graph. In Thirty-seventt Conference on Neurul Information Processing Systems, 2023. URL https:://// /ttp///nrvee.nee//feeeeee oaGdsgB18L.
[24] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary DeVito, Martin Raison, Alykham Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances Neural Information Processing Systems 32, NeurlPS 2019, pages 8024 8035, 2019.
[25] Hongyu Ren and Jure Leskovec. Beta embeddings for multi- multi-hop logical reasoning knowledge graphs. In Advances in Neural Information Processing Systems, volume 33, 2020.
[26) Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2020.
[27] Hongyu Ren, Mikhail Galkin, Michael Cochez, Zhaocheng Zhu, and Jure Leskovec. Neural graph reasoning: Complex logical query answering meets graph databases. arXiv preprint arXiv:2303. /4617, 2023.
[28] Haitian Sun, Andrew Arnold, Tania Bedrax Weiss, Fernando Percira, and William W Cohen. Faithful embeddings for knowledge base queries. In Advances in Neural Information Processing Systems, 2020.
[29] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pages 9448-9457. PMLR, 2020.
12

---

[30] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference on machine learning, pages 2071 2071-2080. PMLR, 2016.
[31] Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing differentiable fuzzy logic operators. Artificial Intelligence, 302, 2022. URL sci science/articlne /ttpc///tttaaa///////00002020100
com/
[32] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition-based based multi-relational graph convolutional networks, In International Conference on Learning Repre- sentations, 2020. URL http:p/s//ppeeeerieeeeeetttrorre
C4tPr.
[33] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[34] Zihao Wang. Yangqiu Song, Ginny Y. Wong, and Simon See. Logical message passing networks with one-hop inference on atomic formulas. In The Eleventh International Conference on Learning Representations, ICLR, 2023. URL https: http:///ppeeeeeeeee//eee/e net/ www//ferumniiiieemmmoo SoyDsp7i_1.
[35] Hang Yin, Zihao Wang, Weizhi Fei, and Yangqiu Song. BFOg-cqa: Towards knowledge graph complex query answering beyond set operation. arXiv preprint arXiv:2307.1370. 2023.
[36] 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: //tp:////peeeeeeeeeeeeeee
[37] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In Advances in Neural Information Processing Systems, volume 34, pages 9061-9077 2021.
[38] Yongqi Zhang and Quanming Yao. Knowledge graph reasoning with relational digraph. In Proceedings of the ACM Web Conference 2022, pages 912-924, 2022.
[39] Yongqi Zhang, Zhanke Zhou, Quanming Yao, Xiaowen Chu, and Bo Han. Adaprop: Learning adaptive propagation for graph neural network based knowledge graph reasoning. In KDD, 2023.
[40] Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. Cone: Cone embeddings for multi-hoy hhp reasoning over knowledge graphs. In Advances in Neural Information Processing Systems, 2021.
[41] Jincheng Zhou, Beatrice Bevilacqua, and Bruno Ribeiro. An ood multi-task perspective for link prediction with new relation types and nodes. arXiv preprint arXiv:2307.06046, 2023.
[42] Zhaocheng Zhu, Zuobai Zhang, Kouis-Pascal Xhonneux, and Jian Tang. Neural bellman ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29499, 2021.
[43] Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. Neural-symbolic models for logical queries on knowledge graphs. In International Conference on Machine Learning. PMLR, 2022.
[44] Zhaocheng Zhu, Xinyu Yuan, Mikhail Galkin, Sophie Xhonneux, Ming Zhang, Maxime Gazeau, and Jian Tang. nett scalable path-based reasoning approach for knowledge graphs In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: //openreview.o wttp:/iwww.neeeeteoeeoeeeeeeeeee pttts/forumidddAJrxx000
13

---

A Datasets
A.1 Dataset statistics
First, Table 4, Table 5, and Table provide the necessary details on the graphs behind the CLQA datasets. Then, Table Table 8, and Table list the query statistics. Transductive datasets 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, Viriin In the following Appendix A.2 we provide more details in sampling 11 new inductive (e, r) datasets WikiTopics-CLOA (available under the CC BY 4.0 license).
Table 4: Graph in transductive datasets (3) from Ren and Leskovec [25]. Inverse triples and edge types are included in the splits. Train, Valid, Test denote triples in the respective set.
Dataset
Entities
Rels
Train
Valid
Test
FBI 15k
14,951
2,690
966,284
100,000
118, 142
FB 15k237
14,505
474
544,230
35,052
40,876
NELL99S
63,361
400
228,426
28,648
28,534
Table 5: Graphs in inductive (e) datasets (9) from Galkin et al. [14]. Inverse triples and edge types are included in all graphs. Validation and Test splits contain an inference graph (Vins, Eirg) which a superset of the training graph with new nodes, and missing edges predict (Valid and Test, respectively).
Training Graph
Validation Graph
Test Graph
Ratio,
Rels
Entities
Triples
Entities
Triples
Valid
Entities
Triples
Test
106%
466
13,091
493,425
13,801
551,333
10,219
13,802
538,896
8,023
113%
468
11,601
401,677
13,022
491.518
15,849
13,021
486,068
14,893
122%
466
10,184
298,879
12,314
413,554
20,231
12,314
430,892
23,289
134%
466
8,634
228,729
11,468
373,262
25,477
11,471
367.810
24.529
150%
462
7,232
162,683
10,783
311,462
26,235
10,782
331,352
29,755
175%
436
5,560
102,521
9,801
265,412
28,691
9,781
266,494
28,891
217%
446
4,134
52,455
9,062
227,284
30,809
9,058
212,386
28.177
300%
412
2,650
24,439
8,252
178,680
27,135
8,266
187,156
28,657
550%
312
1,084
5,265
7,247
136,558
22,981
7,275
133,524
22,503
Table 6: Graphs in the newly sampled inductive entity and relation (e,r) WikiTopics-CLL CLQA datasets
(11). Triples denote the number of edges of the graph given training, validation, or test. Valid and
Test denote triples to be predicted in the validation and test sets in the respective validation and test graph.
Training Graph
Validation Graph
Test Graph
Dataset
Entities
Rels
Triples
Entities
Rels
Triples
Valid
Entities
Rels
Triples
Test
Art
10000
65
27262
10000
65
27262
3026
10000
28023
3113
Award
10000
17
23821
10000
13
23821
2646
10000
17
25056
2783
Education
10000
19
14355
10000
19
14355
10000
19
14193
1575
Health
10000
31
15539
10000
31
15539
1725
10000
15337
1703
Infrastructure
10000
37
21990
10000
37
21990
2443
10000
21646
2405
Location
10000
62
85063
10000
62
85063
9451
10000
80269
8917
Organization
10000
34
33325
10000
34
33325
3702
10000
31314
3357
People
10000
40
55698
10000
40
55698
6188
10000
40
58530
6503
Science
10000
66
12576
10000
66
12576
1397
10000
66
12516
1388
Sport
10000
47251
10000
34
47251
5250
10000
34
46717
5190
Taxonomy
10000
18921
10000
59
18921
2102
10000
19416
2157
A.2 WikiTopics-CI.QA
The WikiTopiis dataset introduced by Gao et al. [16] was used to evaluate link prediction model's zero-shot performance in the inductive (e, r) setting, i.e., when the test-time inference graph contains both new entities and new relations unseen in training. It grouped relations into 11 different topics,
14

---

Table 7: Statistics of 3 transductive datasets
Split
Query Type
FBISk
FB115k2237
NEL.9995
1p/2p/3p/2izi Zin/Sinsimplpimmpmi
273,710
149,689
107.982
Train
27.371
14,968
10,798
Valid
1p
59,078
20.094
16,910
Others
8,000
5,000
4,000
1p
66,990
22,804
17,021
Test
Others
8,000
5,000
4,000
Table 8: Statistics of 9 inductive (e) datasets.
Raiio
Gruph
1p
2p
3p
2i
31
pi
ip
2u
up
2in
3im
imp
pin
pei
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
106%
validatiion
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
5,446
10,000
10,000
10,000
10,000
1,000
1,000
1,000
training
115,523
50,000
50,000
50,000
50,000
50,000
50,000
50,000
40.000
50,000
50,000
113%
validatiion
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
9,762
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
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
121%
validationn
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
14,458
10,000
10,000
10,000
5,000
5,000
5,000
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
$0,000
133%
validation
15,511
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
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
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
150%
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
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
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
175%
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
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
training
22,422
30,000
50,000
50,000
50,000
50,000
50,000
50,000
50,000
30,000
30,000
50,000
50,000
50,000
217%
validatiin
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
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
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
$0,000
300%
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
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
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
550%
valiidation
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
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
Table 9: WikiTopics-CLOO
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].
Topics
1p
2p
3p
2i
36
ip
Zin
3in
pin
pni
inp
2n1
Art
3113
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Award
2783
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Education
1575
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Health
1703
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Infrastructure
2405
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Location
8000
8917
4000
8000
8000
8000
8000
1000
1000
1000
1000
1000
8000
8000
Organization
3357
8000
4000
8000
8000
8000
8000
1000
1000
1000
1000
1000
8000
8000
People
6503
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Science
1388
10000
10000
10000
10000
10000
10000
1000
1000
1000
1000
1000
10000
10000
Sport
8000
8000
8000
8000
8000
1000
1000
1000
8000
8000
Thxonomy
2157
8000
8000
8000
8000
8000
8000
1000
1000
1000
1000
1000
8000
8000
domains, such as art, education, health care, and sport. Two graphs, G/T)) and 9:00) along with the
missing triples Eyolid and elT) were provided for each topic T,, which had the same set of relations but different (potentially overlapping) set of entities. The goal was to train models on the training graphs G of some topic T, and test on the inference graph 9 of an unseen topic TV. The model's s validation performance was evaluated on the missing triples c(T) when observing training graph train as imputs, and its test performance was evaluated on e(TT)) when observing the test inference graph (T))) as inputs. Table shows the statisties 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-CLLA.. For each topic T, we generate three sets of queries and answers (training, validation, test), using the training graph g ( for training and validation, and inference graph (\(2) for test queries, respectively.
15

---

Training queries on Goan only have easy answers, validation (test) set easy answers are attained by traversing G (g ) whereas the full set of answers (easy and hard) are attained by traversing the graph Irain merged with ( (g merged with e(T)) ). Hence, the hard answers cannot be found unless the model is capable of imputing missing links. In our experiments, we only use the inference graph U and the test queries and answers for evaluating zero-shot inference performance. Table shows the statistics of the WikiTopics-CI.QA dataset.
B Hyperparameters and Baselines
Both ULTRAQUERY and ULTRAQUERY LP are implemented with PyTorch [24] (BSD-style license) and PyTorch-Goomen [12] (MIT license). Both ULTRAQUERY and ULTRAQUERY LP ini- tialized from the pre-trained ULTRA checkpoint published by the authors and have the same GNN architectures with parameter count (177k). ULTRAQUERR is further trained for 10,000 steps complex queries from the FB15K237 dataset. Hyperparameters of ULTRAQUERY and its training details are listed in Table 10.
ULTRAQUERS 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 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 embed- dings pre-computed for each graph, e.g., taking 30M parameters on the FB15k237 graph with 15k nodes. Further, QTO materializes the whole (V x V x 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 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, egg., 2M for the FB 175% split with 436 unique relations.
Inductive re, (11 datasets): for newly sampled datasets, due to the absence of fully inductive trainable basclines, 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 create a ranking, we randomly shuffle entities in each class. This baseline non-parametric, does not require any training, and represents 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.
C More Results
Table 11 corresponds to Figure and Table and provides MRR and Hits 10 results for ULTRA- QUERY, ULTRAQUERY LP,, and Best Baseline for each dataset averaged across EPFO query types and negation query types. Figure 7 is the full version of Figure 4 and illustrates the performance of all 3 compared models on 9 inductive (c) datasets 14 query types together with their averaged values (EPFO avg and neg avg, respectively).
16

---

Table 10: ULTRAQUERY hyperparameters. GNN, denotes GNN over the graph of relations Gr. GNN, a GNN over the original entity graph G.
Hyperparameter
ULTRAQUERY training
# layers hidden dim
6
64
GNN,
message
DistMult
aggeregation
sum
# layers hidden dim
6
64
GNN
message aggregation 9-))
DistMult
sum
2-layer MLP
optimizer
AdamW
learning rate training steps adv temperature traversal dropout batch size training queries
0.0005
10,000
Learning
0.2
0.25
64
FB15k237
Table 11: Full results (MRR, Hits 10) of ULTRAQUERY LP and ULTRAQUERY in the zero-shot inference regime on transductive, entity-inductio (e), and fully inductive (e,r) datasets compared to the best-reported baselines averaged across EPFO query types (EPFO avg) and negation query types (Negation avg). ULTRAAUERY fine-tuned only on FB15k237 queries. The numbers correspond to Table and Figure 1.
QUERAQUERY LP
ULTRAQUERY
Best Baseline
EPFO avg
Negation avg
EPFO avg
Negation avg
EPFO avg
Negation avg
MRR Hits@ 10
MRR Hits in
MRR
Hits@ 10
MRR
Hits 10
MRR
Hits@ 10
MRR
Hits 10
transductive datasets
FB15k237
0.362
0.082
0.164
0.242
0.378
0.08
0.174
0.335
0.491
0.155
0.295
FB
0.501
0.672
0.291
0.465
0.764
0.834
0.567
0.725
0.740
0.837
0.492
0.664
NELL995
0.395
0.079
0.160
0.226
0.341
0.073
0.159
0.329
0.483
0.129
0.268
inductive (c) datasets
550%
0.518
0.144
0.373
0.186
0.332
0.222
0.331
0.158
FB 300%
0,320
0.496
0.117
0.227
0.359
0.526
0.168
0.312
0.291
0.426
0.125
0.224
217%
0.509
0.133
0.252
0.375
0.186
0.337
0.492
0.301
FB 175%
0.297
0.469
0.110
0.214
0.338
0.499
0.159
0.297
0.351
0.507
0.188
0.336
FB 1,50%
0.445
0.097
0.190
0.316
0.132
0.255
0.493
0.167
0.303
FB 1333%
0,266
0.426
0.087
0.167
0.298
0.451
0.122
0.238
0.353
0.514
0.197
0.341
FB 121%
0.400
0.081
0.164
0.279
0.119
0.232
0.323
0.462
0.173
0.291
FB 113%
0,217
0.362
0.067
0,136
0.240
0,387
0.097
0.192
0.352
0.494
0,214
0.339
106%
0,200
0.340
0.054
0.114
0.226
0.086
0.162
0.373
0.504
0,256
0.377
inductive (e. datasets
Art
0.249
0.389
0.086
0.157
0.248
0.349
0.083
0.137
0.016
0.031
0.006
0.014
Award
0.224
0.413
0.046
0.098
0.227
0.354
0.152
0.274
0.004
0.006
0.002
0.002
Edu
0.142
0.258
0.066
0.122
0.179
0.249
0.119
0.176
0.008
0.014
0.003
0.005
Health
0.317
0.466
0.159
0.231
0.317
0.394
0.419
0.525
0.019
0.040
0.020
Infrastructure
0.392
0.551
0.087
0.170
0.337
0.461
0.235
0.356
0.010
0.018
0.033
0.005
Location
0.508
0.678
0.198
0.371
0.569
0.679
0.402
0.585
0.007
0.017
0.001
0.002
Organization
0.098
0.190
0.023
0.048
0.169
0.270
0.082
0.171
0.005
0.008
0.01
0.002
People
0.373
0.530
0.182
0.332
0.194
0.285
0.005
0.010
0.002
0.033
Science
0.206
0.348
0.048
0.093
0.158
0.255
0.071
0.131
0.041
0.085
0.100
0.020
Sport
0.215
0.357
0.095
0.166
0.252
0.371
0.178
0.269
0.015
0.030
0.005
0.008
Taxonomy
0,230
0.315
0.151
0.255
0.290
0,360
0.183
0.261
0.034
0.066
0.009
0.017
17

---

GNN-QE
QUERAQURRY
UEIRAQUERY
EPPO
query
0.2
0.0
100
2000
300
100
500
2000
300
400
500
100
200
300
400
150
100
2000
300
400
500
QUeryy
QUaryy
31
QUESY 1p
0.6
100
100
500
2.00
300
600
500
200
300
400
100
2000
e/uay
MIRE
0.4
0.22
300
310
000
200
300
100
qjarry
quaey
squncy gei
quaey p4n
0.6
3010
0.0
100
2000
.000
4001
500)
2000
2000
6001
500
3000
2000
2000
4011
500
300
2001
2200
.0001
500
Ditasct Ratio
Dataset Ratio
Dacaset Ratio
Dataect Ratio
Figure 7: Full results on 9 inductive (e) datasets corresponding to Figure 4: albeit ULTRAQUERY LP outperforms the main ULTRAQUERY simple Ip queries, it suffers from the multi- propagation issue on complex queries. ULTRAQUERS trades a fraction Ip query performance for significantly better average performance on EPFO and negation query types with particularly noticeable gains on intersection and 2in, 3in queries.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The paper claims (1) the first inductive CLQA method where a single model is able to generalize to arbitrary KGs with any entity and relation vocabulary; (2) study of the multi-source propagation issue. Experiments in Section 5 support the claims, i.e., single pre-train pre-trained ULTRAQUERY transfers to 23 different query answering datasets with competitive performance (setting state of the art on 15 of those datasets), the ablation study shows that ULTRAQUERY effectively alleviates the multi-source propagation issue.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss limitations in Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
No theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental setup is described in Section more details on implementa- tion and hyperparameters are in Appendix B. The code is available to reviewers.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
The code is available https://github, con/DeepdraphLearniigg ULTRA, the datasets are openly available either. Appendix A.2 explains the creation process of the WikiTopics-CLQA dataset.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ httpsscccppbcccccceeceeeeeeceece http//////ddee//eeeubbbiiiiiiii /ot////oooeeesiseaeee /tt.de/Suummissiiooooo... wwmiiisssssiiiiyo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details are in Section 5 and in Appendices A, B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Zero-shot inference results on ULTRAQUERY are stable and do depend on random seeds. The variance of baselines is negligible (as in most KG reasoning works) and is therefore omitted.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The details are provided Section 5 and Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:: /ttt::://neurps... http:p////errpp..ccppllil////// Cettiiie/eeeeeeeeeeeeeeeeeeeeee itthicseneellleee
Answer: [Yes]
Justification:
The presented research conforms with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe 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 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 best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Appendices A, B.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswi wwweree.tthhoe.... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
23

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We curated a novel WikiTpoics-CLQA dataset for inductive complex query answering, the dataset creation process is described in Appendix A.2.
Guidelines:
The answer NA means that the paper does release assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing was used for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.


Reviews:
[{"review_id": "0kkyVSC7sA", "reviewer": "Reviewer_5vKU", "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.", "questions": "How the model scales as the pretraining data scales up?", "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.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. ULTRA QUERY is the first foundation model for inductive CLQA that can zero-shot generalize to any KG with new entities and relations. This is a significant breakthrough as existing CLQA methods are either transductive or only partially inductive.\n2. The model design is well thought out, combining an inductive projection operator based on ULTRA with non-parametric fuzzy logical operators. The fine-tuning approach on a single dataset is effective in adapting the pre-trained projection operator to the multi-hop query answering framework.\n3. The ability to perform CLQA on any KG without retraining is highly valuable, potentially saving significant compute resources and time. The performance of ULTRA QUERY on various datasets demonstrates its effectiveness and practical impact.", "weaknesses": "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.\n2. The paper does not discuss the model's scalability to very large KGs, which is an important aspect for practical applications.\n3. And the scalability of the model (parameters and performance) can be further discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating our work and helpful comments. \n\n> **W1.** A more in-depth analysis of the model's behavior under different conditions (e.g., varying graph sizes, query complexity) could provide further insights\n\nWe would like to point your attention to Section 5.3 in the main paper and Appendix C. Appendix C provides breakdown of the zero-shot performance w.r.t. different query types and different graph sizes. Section 5.3 includes a qualitative analysis on faithfulness as a function of varying graph sizes, and cardinality prediction.\n\nIn Section 5.3 we study faithfulness (the ability to recover easy answers achievable by graph traversal, visualized as a function of increasing unseen inference graph size from inductive FB datasets) and cardinality prediction (correlation between model outputs and the true number of query answers) and show that UltraQuery performs quite competitively compared to larger transductive SOTA models while being inductive and orders of magnitude smaller. \n\nIn Appendix C we plot per-query-type performance on all 14 query types across 9 increasingly larger inference graphs - showing that UltraQuery performance does not degrade on more complex patterns (such as 3p or inp) when an unseen inference graph becomes larger. In contrast, the performance of baseline GNN-QE degrades quite significantly.\n\n> **W2.** The paper does not discuss the model's scalability to very large KGs, which is an important aspect for practical applications.\n\nThanks for bringing this question up. We will include this discussion into the future work. In this work, we first focused on the general ability to perform CLQA on any KG and scalability is the natural next step. To this end, any scalable path-based GNN like A*Net [1] or AdaProp [2] could be used as an entity-level GNN in the relation projection operator thus making it more of an engineering task. Since those GNNs can scale to graphs with millions of nodes, we are optimistic that UltraQuery could scale to such sizes as well.\n\n> **W3.** Scalability of the model (parameters and performance) can be further discussed.\n\nWhen training from scratch, we found marginal performance improvements beyond a hidden dimension of 64. When using a pre-trained relation projection checkpoint, we attribute most of the performance to the baseline performance of the checkpoint - since available checkpoints of Ultra are of the same parameter size, we only used the available one. \nWe note that most models on knowledge graphs are designed for a single size, including the checkpoint of Ultra we use. There is no consensus in the community on what should be scaled.\n\n> **Q1.** How the model scales as the pretraining data scales up?\n\nWe ran new experiments training UltraQuery on 2 (FB15k237, NELL995) and 3 (FB15k, NELL995, FB15k) CLQA datasets and measuring inductive inference performance on the rest 20 inductive datasets. Please find the charts and discussion in the attached PDF document and in the general response.  \n\nReferences:  \n[1] Zhu et al. A*net: A scalable path-based reasoning approach for knowledge graphs. NeurIPS 2023   \n[2] Zhang et al. AdaProp: Learning adaptive propagation for graph neural network based knowledge graph reasoning. KDD 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zVzaQQaftT", "reviewer": "Reviewer_vHv9", "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.", "questions": "1. How does ULTRAQUERY handle extremely large KGs, and what are the scalability challenges?\n2. Can the authors provide more insights into the decision-making process behind the choice of fuzzy logics for logical operations?", "limitations": "Applications to more general scenarios.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces ULTRAQUERY, a novel foundation model for zero-shot logical query answering on knowledge graphs (KGs), which is a significant advancement in the field of complex logical query answering.\n2. One of the key strengths of ULTRAQUERY is its ability to generalize to new entities and relations in any KG without the need for retraining, which addresses a major limitation of existing CLQA methods.\n3. The paper provides extensive experimental results, demonstrating that ULTRAQUERY outperforms existing baselines on multiple datasets, showcasing its effectiveness across various query types.", "weaknesses": "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.\n2. The paper does not present formal theoretical results or proofs to support the empirical findings, which could have strengthened the contribution.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the constructive feedback, please find our comments below.\n\n> **W1.** 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. The paper could have provided more details on the computational efficiency\n\n> **Q1.** How does ULTRAQUERY handle extremely large KGs, and what are the scalability challenges?\n\nGiven that there haven’t been any inductive models for CLQA, we first focused on the general problem of making zero-shot inductive transfer possible. Scalability, although being somewhat orthogonal to the inductive inference and generalization problems, is a nice bonus for inductive models once inductiveness is achieved and we believe it is an encouraging direction for future work. \n\nHaving said that, compared to the transductive baseline GNN-QE, the complexity overhead induced by the fully-inductive relation projection operator is rather negligible. The fully-inductive relation projection operator runs over the graph of relations and is O(|R|) where |R| is the number of unique relations. Usually |R| is orders of magnitude smaller than the number of nodes, eg, |R|=474 in FB15k237 with 15k nodes, or |R|=400 in NELL995 with 63k nodes. \n\nThe support for very large KGs could be further improved by adopting more scalable entity-level GNN predictors like A*Net [1] or AdaProp [2] which have been shown to scale to graphs of millions of nodes. We are optimistic that UltraQuery could scale to such graphs as well when integrated with those models. We deem it as the next engineering step for future work and will include this discussion into the revised version.\n\n> **W2.** The paper does not present formal theoretical results or proofs to support the empirical findings, which could have strengthened the contribution\n\nWe do not see why it is necessarily a weakness. Our model coincides with the most recent theoretical results in the relational GNN expressivity literature, eg, relational WL [3] and its extension to conditional MPNNs [4] paved the way for generalizable inductive models which are provably more powerful than shallow transductive embedding approaches. The product fuzzy logic we use is identified as the most stable fuzzy logic for backprop in the differentiable fuzzy logic literature [5].\nFinally, theoretical expressivity of the inductive projection operator (Ultra) is still an open question and we are not aware of the formal theoretical results about it in the literature. We believe this an intriguing question for the future work.\n\n> **W3.** The reliance on a pre-trained model could lead to overfitting on the training dataset, potentially affecting the model's performance on unseen data. \n\nCould you please elaborate on your understanding of overfitting in this case? We do not observe strong signs of overfitting on the training dataset as UltraQuery generalizes in the zero-shot manner to 20+ unseen graphs (and queries over those graphs) often better than tailored transductive models trained specifically on each target graph. In that sense, transductive models are extreme cases of overfitting as they are hardcoded to a particular set of entities or relations in a specific KG and cannot generalize to unseen graphs at inference time.\n\nWhat we do observe is the multi-source propagation issue (explained in Section 4.1), which might be understood as a kind of overfitting on 1p queries when using pre-trained KG completion model for CLQA. We have discussed this issue and proposed two solutions: scores thresholding and short fine-tuning.\n\nGenerally, we would expect that a better pre-trained relation projection operator (with better zero-shot generalization capabilities on one-hop link prediction) would likely yield a higher performance in the UltraQuery framework as well (after doctoring the multi-source propagation issue).\n\n> **Q2.** Can the authors provide more insights into the decision-making process behind the choice of fuzzy logics for logical operations?\n\nGood differentiable fuzzy logics must be stable in the gradient-based optimization setup (like backpropagation) and do not vanish the gradient. Van Krieken et al [5] have shown that only product logic satisfies those requirements whereas other options like Gödel and Lukasiewicz t-norms and t-conorms suffer from the vanishing gradient problem. We included the main motivation in Section 4.2 and will elaborate on that in the revised version.\n\nReferences:   \n[1] Zhu et al. A*net: A scalable path-based reasoning approach for knowledge graphs. NeurIPS 2023   \n[2] Zhang et al. AdaProp: Learning adaptive propagation for graph neural network based knowledge graph reasoning. KDD 2023  \n[3] Barcelo et al. Weisfeiler and Leman go relational. LoG 2022   \n[4] Huang et al. A theory of link prediction via relational Weisfeiler-Leman on knowledge graphs. NeurIPS 2023   \n[5] van Krieken et al. Analyzing differentiable fuzzy logic operators. Artificial Intelligence, 302, 2022", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E1aFVrY1ER", "reviewer": "Reviewer_rSrG", "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.", "questions": "Please refer to the weakness part", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper establishes solid work for a unified CLQA foundation model that has strong adaptability to completely new knowledge graphs. I feel this to be an important work that benefits the training of CLQA models under low-resource situations and continuously updating knowledge graphs. The authors also widely conduct experiments to support their claims which show a strong generalization performance.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work and would like to comment on the weaknesses:\n\n> **W1.** 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. \n\nIn order to build a model that zero-shot generalizes to CLQA tasks on any unseen KG we need two main components that do not depend on input entity/relation vocabulary: (1) generalizable logical operators; (2) generalizable relation projection operator. (1) is achieved by using non-parametric fuzzy logics (product logic in our case as being the most stable for gradient-based optimization). (2) is harder and requires an inductive link predictor / KG completion operator that generalizes to any graph. We integrated ULTRA as the projection operator that outputs a single scalar for each node (which is then used by fuzzy operators) that indicates a probability of this node being the answer to the query $(h, q, ?)$. \n\nElaborated in Section 4.1, practically, ULTRA consists of two GNNs – operating on the relation level and on the entity level. First, given a query $(h, q, ?)$, ULTRA builds a graph of relations from the original KG - this graph is small and only has O(|R|) nodes and 4 specific meta-relations. Note that $|R| << |E|$ in any KG so processing this graph introduces a rather marginal computational overhead compared to the entity-level GNN. Since we know the query relation $q$, we label it with the all-ones vector in the graph of relations, run a GNN, and read all final representations as _conditionally_ _dependent_ on the starting query $q$. Those representations are used as initial edge type features in the second, entity-level GNN. Labeling the starting head node $h$ with the vector corresponding to $q$ and running a GNN over the main graph, we read out final node states as probabilities of each node being the answer to the query $(h, q, ?)$. \n\nThe only learnable parameters in ULTRA are 4 meta-relations for the graph of relations and GNN weights. The 4 meta-relations represent structural patterns like “a tail of and edge with relation X is the head of another edge with relation Y” and can be mined from any multi-relational KG independent of their entity/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 for zero-shot inference on any KG.\n\nApplying ULTRA for CLQA in this work, we found the multi-source propagation issue (Section 4.1), that is, ULTRA pre-trained with a single starting node, is not suitable for CLQA where at intermediate stages there might be many non-zero initialized nodes representing intermediate answers. The issue can be alleviated with scores thresholding (underperforming option) or short but effective fine-tuning on a few complex queries (better performing option). Finally, we proposed 11 new inductive CLQA datasets.\n\nThanks for highlighting the lack of a description – we will include this more detailed discussion into the main body of the manuscript in the final version which allows one more extra page of content.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ni8E9ZcTw1", "reviewer": "Reviewer_TgMu", "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.", "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.\n\n2. 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.\n\n\n[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.\n\n[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.\n\n[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": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.This paper introduces a foundation model which can answer the logical queries over unseen KG. The foundation model is trained on the FB15k-237 and achieve the competitive performance comparing with SoTA baseline. This results is quite impressive.\n\n2. This paper is well organized and well written. \n\n3. This discussion  is solid and the experiments well supports the foundation model for logical query answering.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work highlighting the results, paper organization, and discussions. Please find our comments below:\n\n> **W1.** novelty of the proposed methods.\n\nIn this work, we introduced a new setup – a fully-inductive, zero-shot generalization of complex query answering on new, unseen KGs, and UltraQuery, the first model capable of doing that. Directly applying an Ultra model pre-trained on one-hop link prediction does not really work - the 1p query performance would be high but it is much worse on complex queries. This happens due to the multi-source propagation issue (described in Section 4.1), that is, labeling only one node is not suitable for CLQA where at intermediate stages there might be many non-zero initialized nodes representing intermediate answers. The issue can be alleviated with scores thresholding (underperforming option) or short but effective fine-tuning on a few complex queries (better performing option). Besides, we proposed 11 new inductive CLQA datasets.\n\n> **Q1.** 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.\n\nYes, UltraQuery can be extended to support additional node / edge features by concatenating the features with zero/one vectors adhering to the labeling strategy in order to retain the expressive power of conditional MPNNs. However, there is a caveat when including features into the pre-trained model - since the model dimension is fixed, those features have to be homogeneous (having the same feature dimension and coming from the same distribution) while arbitrary datasets that might have textual / numerical / categorical features. So far, this feature alignment is quite non-trivial and there is no common approach for such an alignment in the literature, so we deem it an interesting avenue for the future work and will include this discussion into the relevant section. \n\nHaving said that, the hardest, most fundamental, and widely studied setting in inductive KG reasoning [1,2,3,4,5,6, and others] is generalization without features where models have to leverage the graph structure and graph inductive biases - this is what we focus on in UltraQuery. \n\n> **Q2.** Will you present the results of the setting provided in your further work?\n\nWe will do our best to provide initial results on some of the outlined problems in the final version. Meanwhile, we performed an experiment measuring the inductive performance as a function of several datasets in the training mixture. Please find the results in the attached PDF and in the general response. \n\nReferences:    \n[1] Teru et al. Inductive Relation Prediction by Subgraph Reasoning. ICML 2020.    \n[2] Zhu et al. Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. NeurIPS 2021.   \n[3] Zhang, Yao. Knowledge Graph Reasoning with Relational Digraph. WebConf 2022.   \n[4] Zhu et al. A*net: A scalable path-based reasoning approach for knowledge graphs. NeurIPS 2023     \n[5] Zhang et al. AdaProp: Learning adaptive propagation for graph neural network based knowledge graph reasoning. KDD 2023    \n[6] Galkin et al. Towards foundation models for knowledge graph reasoning. ICLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for appreciating our work and providing valuable feedback. We are delighted to see the work recognized as *“a significant breakthrough”*, *“a significant advancement in the field”* (**5vKU**), *“a groundbreaking model”* (**vHv9**), *“solid and important work”* (**rSrG**) with extensive experimental results (highlighted by all reviewers).

In this general response, we would like to address the common comments and report the requested experiments in the uploaded PDF: 

**Model’s scalability to very large graphs (5vKU, vHv9)**

In this work, we first focused on the general ability to perform CLQA on any unseen KG and scalability is the natural next step (although being somewhat orthogonal to the inductive inference and generalization challenges). To this end, any scalable path-based GNN like A*Net [1] or AdaProp [2] could be used as an entity-level GNN in the relation projection operator thus making it more of an engineering task. Since those GNNs can scale to graphs with millions of nodes, we are optimistic that UltraQuery could scale to such sizes as well. We leave this exploration for future work and will include this discussion in the final version.

**(New experiment) Performance of UltraQuery trained on more datasets (5vKU)**

As per reviewer 5vKU request, we conducted a new experiment measuring the inductive inference CLQA performance depending on the number of KGs in the training mixture. Please find the details and full results in the attached PDF. 

The original model (1G) was trained on queries from the FB15k237 dataset. 
In order to maintain the zero-shot inductive inference setup on 11 inductive $(e,r)$ and 9 inductive $(e)$ datasets (total 20 datasets), we trained new versions on the rest of BetaE datasets: FB15k237 and NELL995 queries (2G), and FB15k273, NELL995, and FB15k queries (3G). A summary table of average EPFO MRR results is provided below:

| Model | Inductive (e,r) (11 datasets) | Indudctive (e) (9 datasets) | Total Avg (20) |
| :---: | :---: | :---: | :---: |
|  | EPFO avg MRR | EPFO avg MRR | EPFO avg MRR |
| UltraQuery 1G | 0.280 | 0.312 | 0.296 |
| UltraQuery 2G | 0.310 | 0.307 | 0.308 |
| UltraQuery 3G | 0.304 | 0.292 | 0.298 |

Generally, training on more graphs increases the performance on EPFO queries on 11 inductive $(e,r)$ datasets and slightly improves the overall performance on 20 datasets. Having said that, we identify several factors that might affect the performance:
* Given a short time for running experiments, the training configuration might be suboptimal and might require more hyperparameter tuning including the sampling ratio from each dataset or adversarial temperature for the loss function;
* Newly included datasets, NELL995 and FB15k, might not be very useful for inductive datasets which are based mostly on Freebase and Wikidata. That is, NELL995 is sparse and combines several disconnected components whereas FB15k is known for test set leakages. We hypothesize that adding a few datasets from inductive $(e)$ and $(e,r)$ benchmarks to the training mixture might yield much better zero-shot performance. We leave the study of the most effective data mixtures for the future work;

We will include this experiment in the final version as well. We would be happy to engage in the discussion in the comments, please let us know if you have any further concerns.

References:   
[1] Zhu et al. A*net: A scalable path-based reasoning approach for knowledge graphs. NeurIPS 2023     
[2] Zhang et al. AdaProp: Learning adaptive propagation for graph neural network based knowledge graph reasoning. KDD 2023.

Meta-review: 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.
Decision: Accept (poster)