Inductive Logical Query Answering in Knowledge Graphs
Authors: Mikhail Galkin
Zhaocheng Zhu
Hongyu Ren
Jian Tang
Venue: NeurIPS 2022 Accept (2022)
Keywords: inductive graph reasoning
complex query answering
logical queries
knowledge graphs
graph neural networks
inductive representation learning

Abstract: Formulating and answering logical queries is a standard communication interface for knowledge graphs (KGs). 
Alleviating the notorious incompleteness of real-world KGs, neural methods achieved impressive results in link prediction and complex query answering tasks by learning representations of entities, relations, and queries. Still, most existing query answering methods rely on transductive entity embeddings and cannot generalize to KGs containing new entities without retraining entity embeddings. 
In this work, we study the inductive query answering task where inference is performed on a graph containing new entities with queries over both seen and unseen entities. To this end, we devise two mechanisms leveraging inductive node and relational structure representations powered by graph neural networks (GNNs).
Experimentally, we show that inductive models are able to perform logical reasoning at inference time over unseen nodes generalizing to graphs up to 500% larger than training ones. Exploring the efficiency--effectiveness trade-off, we find the inductive relational structure representation method generally achieves higher performance, while the inductive node representation method is able to answer complex queries in the inference-only regime without any training on queries and scale to graphs of millions of nodes. Code is available at 
https://github.com/DeepGraphLearning/InductiveQE

Inductive Logical Query Answering in Knowledge Graphs
Mikhail Galkin
Zhaocheng Zhu Mila, Université de Montréal zhuzhaoc@mila, queeee
Mila, McGill University
mikhail, galkin@milal la. quebec
Hongyu Ren Stanford University hyren@stanford.com edu
Jian Tang
Mila, HEC Montréal, CIFAR AI Chair jian. tang@hec.ca
Abstract
Formulating and answering logical queries is standard communication interface for knowledge graphs (KGs). Alleviating the notorious incompleteness of real- world KGs, neural methods achieved impressive results in link prediction and com- plex query answering tasks by learning representations of entities, relations, and queries. Still, most existing query answering methods rely on transductive entity embeddings and cannot generalize to KGs containing new entities without retrain- ing the entity embeddings. In this work, we study the inductive query answering task where inference is performed on graph containing over both seen and unseen entities. To this end, we devise two mechanisms lever- aging inductive node and relational structure representations powered by graph neural networks (GNNs). Experimentally. we show that inductive models are able perform logical reasoning at inference time unseen nodes generalizing graphs up to 500% larger than training ones. Exploring the efficiency-effectii trade-off, we find the inductive relational structure representation method generally achieves higher performance, while the inductive node representation method is able answer complex queries in the inference-only regime without any train- ing on queries and scales to graphs of millions of nodes. Code is available at com//eegCraplLLeemnnggg/naaa Iww.aaiiinnnnnniiie........
entities with queries
1 Introduction
Traditionally, querying knowledge graphs (KGs) is performed via databases using structured query languages like SPARQL. Databases can answer complex queries relatively fast under the assumption of completeness, i.e., there no missing information the graph. In practice, however, KGs are notoriously incomplete [32]. Embedding based methods that learn vector representations of entities and relations are known to be effective simple link prediction predicting heads or tails of query patterns (head, relation, ?), e.g., (Finstein, graduate, ?), common in KG completion [1, 17).
Complex queries are graph patterns expressed a subset of first-order logie (FOL) with operators such as intersection (A), union (V), negation (-) and existentially quantified (3) variables! e.g., ?U.3V Vin(NobelPrizee V) A Citizen (USA, V) A Graduate (V, U') (Fig. 1). Complex queries define superset of KG completion. The conventional KG completion (link prediction) task can be viewed as a complex query with single triplet pattern without logical operators, e.g., Citizen(USA, V), which we also denote projection query.
The universal quantifier (V) often discarded in real-world KGs there node connected all others.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Where citizens with Nobel Prize graduate? q v.au: (Nbbeell Prize, u) A Citizen u) Graduate (u, v)
Gerain
Goatial (rest) (new nodes and edges)
win
University of Zurich
Nobel Prize
University of Zurich
Einstein
Einstein
citizen
Nobel Prize
graduate
ETTI Zurich
ETH Zurich
USA
answers
Feynman
Primceton
Figure 1:
Inductive query answering problem: at inference time, the graph is updated with new nodes Feynman and Princeton and edges such that the same query now has more answers.
To tackle complex queries on incomplete knowledge graphs, query embedding methods are proposed to execute logic operations the latent space, including variants that employ geometrie [15, 23, 38), probabilistic [24, 9], neural-symbolic [26, 8, 5], neural [21, 4], and GNN [11, 3] approaches for learning entity, relation, and query representations.
However, this very fact of learning separate embedding for each entity makes those methods inherently transductive i..., they are bound to the space of learned entities and cannot generalize to unseen entities without retraining the whole embedding matrix which can be prohibitively expensive in large graphs. The problem is illustrated in Fig. 1: given a graph about Einstein and a logical query Where did US citizens with Nobel Prize graduate?, transductive QE methods learn to execute logical operators and return the answer set (University of Zurich, ETH Zurich]. Then, the graph is updated with new nodes and edges about Feynman and Princeton, and the same query now has more correct answers (University of Zurich, ETH Zurich, Princeton) as new unseen entities satisfy the query as well.
Such inductive inference is not possible for transductive models as they do not have representations for new Feynman and Princeton nodes. In the extreme case, inference graphs might be disconnected from the training one and only share the set of relations. Therefore, inductive capabilities are key factor to transferring trained query answering models onto updated or entirely new KGs.
In this work, study answering complex queries in the inductive setting, where the model has to deal with unseen entities at inference time. Inspired by recent advancement in inductive Kg completion [42, 13], we devise two solutions for learning inductive representations for complex query: 1) The first solution, NodePiece-QE, extends the inductive node representation model NodePiece [13] to complex query answering. NodePiece-OU QE learns inductive representations of each entity as a function of tokens from fixed-size vocabulary, and answers complex query with a non non-parametric logical query executor [5]. The advantages of NodePiece-QE are that it only needs to be trained on simple link prediction data, answers complex queries in the inference-only mode, and can scale to large KGs. 2) The second solution, GNN-QE [40], extends the inductive KG completion model NBFNet [42] for complex query answering. Originally, GNN-QE was studied only in the transductive setting. Here, we analyze its inductive capabilities. GNN-QE learns inductive representations of the relational structure without entity embeddings. and uses the relational structure between the query constants and the answers to make the prediction. GNN-QE can be trained end-to-end on complex queries, achieves much better performance than NodePiece-QF: but struggles to scale to large KGs.
To the best of our knowledge, this is the first work study complex logical query answering in the inductive setting without any additional features like entity types or textual descriptions. Conducting experiments on a novel benchmarking suite of 10 datasets, we find that 1) both inductive solutions exhibit noi-trivial performance answering logical queries over unseen entities and query patterns; 2) inductive models demonstrate out-of- oi-diitrinttion generalization capabilities to graphs up to 500% larger than training ones; 3) akin to updatable databases, inductive methods can successfully find new correct answers to known training queries after adding new nodes and edges; 4) the inductive node representation method scales to answering logical queries over graph of 2M nodes with 500k new unseen nodes; 5) GNN-based models still exhibit some difficulties [20, 35] generalizing to graphs larger than those they were originally trained on.

---

2 Related Work
Knowledge Graph Completion. Knowledge graph completion, a.k.a. simple link prediction, has been widely studied in the transductive paradigm [6, 33, 27, 37J, i... when training and inference are performed on the same graph with a fixed set of entities. Generally, these methods learn a shallow embedding vector for each entity. We refer the audience to respective surveys [1, 17] covering dozens of transductive embedding methods. The emergence of message passing [14] and graph neural networks (GNNs) has led more advanced, inductive representation learning approaches that model entity or triplet representations as a function of the graph structure in its neighborhood. Grall. [28] learns triplet representations based the subgraph structure surrounding the two entities. NeuralLP [34), DRUM [25] and NBFNet [42] learn the pairwise entity representations based on the set of relation paths between two entities. NodePiece [13] learns entity representations from a fixed-size vocabulary of tokens that can be anchor nodes in a graph or relation types.
Complex Query Answering. In the complex (multi-hop) query answering setup with logical operators, existing models employ different approaches, e.g., geometric [15, 23, 38), probabilistic [24, 9I, neural-symbolic [26, 8, 5]. neural [21, 4]. and GNN [11, 3]. Still, all the approaches are created and evaluated exclusively in the transductive mode where the set of entities does not change at inference time. To the best of our knowledge, there is related work in inductive logical query answering when the inference graph contains new entities. With our work, we aim to bridge this gap and extend inductive representation learning algorithms to logical query answering. In particular, we focus on the inductive setup where an inference graph is a superset of a training graph such that 1) inference queries require reasoning over both seen and new entities; 2) original training queries might have more correct answers at inference time with the addition of new entities.
3 Preliminaries and Problem Definition
Knowledge Graph and Inductive Setup. Given finite set of entities E, finite set of relations R. and a set of triples (edges) T = (E x R x E), a knowledge graph 9 is defined as G = (E, R. T)- Accounting for the inductive setup, we define a training graph Grain = (Eraiia; R. TTuaii) and an inference graph Gmy/ = (Emn, R, Tuy) such that Enain C Eif and Train C Tuf- That is, the inference graph extends the training graph with new entities and edges? The inference graph Ging is an incomplete part of the not observable complete graph Gny (Eng, R, Tim) with Tin = Tay U Tpred whose missing triples Tpred have to be predicted at inference time.
Logic Queries. Applied to KGs, a first-order logic (FOL) query Q is a formula that consists of constants C (C S E), variables V (V S E, existentially quantified), relation projections R(a, b) denoting a binary function over constants or variables, and logic symbols (8, A, V, -). The answers Ag (Q) to the query Q are assignments of variables in formula such that the instantiated query formula is subgraph of the complete graph g.
First-Order
Fig. 1 illustrates the logical form of a query Where did US citizens with Nobel Prize graduate? ? as VU.V Win(XobeePrrize ViAiiiizenUUSS V) ArraduateeV U) where NobelPrize and USA are constants; Win, Citizen, Graduate are relation projections (labeled edges); V, U variables such that V is an existentially quantified free variable and U is the projected bound targel variable of the query. Common for the literature, we aim at predicting assignments of the query targel whereas assignments of intermediate variables might not always be explicitly interpreted depending on the model architecture. In the example, the answer set Ag ( (Q) is binding of a target variable U to constants Uni University of Zurich and ETH Zurich.
Inductive FOL Queries. In the standard transductive query answering setup, query constants and variables at both training and inference time belong the same set of entities, i.e., Cruin Ciny S E, Virain = Ven S E. In the inductive setup covered in this work, query constants and variables at inference time belong to a different and larger set of entities Eng from the inference graph Gmy. i.e.,
Conan C Eyain: Virain C Emain but Cuty C Ein,. Ving C Emg. This also leads to the fact that training queries executed over the inference graph might have more correct answers, i.e., Aç.. (Q) C Ag (Q). For example (cf. Fig. 1), the inference graph is updated with new nodes Feynman, Princetor and their
The set of relation types is fixed.
3 Note that the set of relation types R remains the same
3

---

new respective edges. The same query now has larger set of intermediate variables satisfying the formula (Feynman) and an additional correct answer Princeton. Therefore, inductive generalization is essential for obtaining representations of such new nodes and enabling logical reasoning over both seen and new nodes, i.e., finding more answers to known queries in larger graphs or answering new queries with new constants. In the following section, we describe two approaches for achieving inductive generalization with different parameterization strategies.
4 Method
Inductive Representations of Complex Queries. Given complex query Q = (C, R. 9), the goal to rank all possible entities according to the query. From a representation learning perspective, this requires us to learn a conditional representation function f(e|C, Re, g) for each entity E E. Transductive methods learn shallow embedding for each answer entity e &, and, therefore, cannot generalize to unseen entities. For inductive methods, the function f(e|C, Ro G) should generalize to some unseen answer entity e' (or unseen constant entity d' E C') at inference time. Here, we discuss two solutions for devising such an inductive function.
The first solution is to parameterize the representation of each entity as a function of an invariant vocabulary of tokens that does not change at training and inference. Particularly, the vocabulary might consist of unique relation types R. that are always the same for 9rain and Gin,, and we are able to infer the representation of an unseen answer entity (or an unseen constant entity) as function of its incident relations (cf. Fig. 2 left). The idea has been studied in NodePiece [13] for simple link prediction. Here, we adopt similar idea to learn inductive entity representations for complex query answering. Once we obtain the representations for unseen entities, we can use any off-the-shelf decoding method (e.g.. CQD-Beam [5]) for predicting the answer to the complex query. We denote this strategy as NodePiece-QE.
The second solution is to parameterize f(elC, Ro G) as a function of the relational structure. Intuitively, an answer of complex query can be decided solely based on the relational structure between the query constants and the answer (Fig. 1). Even after anonymizing entity names (and, hence, not learning any explicit entity embedding). we can still infer Princeton as an answer since it forms distinctive relational structure >- with the query constants and conforms to the query structure. Similarly, intermediate nodes will be deemed correct if they follow relational structure >. In other words, we do not need to know the answer node is Princeton, but only need to know the relative position of Princeton w.r.f. the constants like Nobel Prize and USA. Based on this idea, we design [e||C, G) to be relational structure search function. Such an idea has been studied in Neural Bellman-Ford Networks (NBFNet) [42] to search for a single relation in simple link prediction. Applied to complex queries, GNN-QE [40] chains several NBFNet instances with differentiable logic operations to learn inductive complex query in an end-to-end fashion. So far, GNN-QE was evaluated solely transductive tasks. Here we extend it to the inductive setup.
4.1 NodePiece-QE: Inductive Node Representation
Here we aim reconstructing node representations for seen and unseen entities without learning shallow node embedding vectors. To this end, we employ NodePiece [13], a compositional tokeniza- tion approach that learns an invariant vocabulary of tokens shared between training and inference graphs. Formally, given a vocabulary of tokens & E T, each entity is deterministically hashed into a set of representative tokens e; [4,,... {x). An entity vector e; is then obtained as function of token embeddings e; fo((,,,... tu)), , & E Rd where the encoder function fo kxd Rd is parameterized with a neural network 0.
Since the set of relation types R is invariant for training and inference graphs, can learn relation embeddings R E IR. R xd and our vocabulary of learnable tokens T is comprised of distinct relation types such that entities are hashed into a set of unique incident relation types. For example (cf. Fig. left), a middle node from a training graph Grain is hashed with set of relations e; = [4it] that stands for two unique incoming relations 4 and one unique outgoing relation t. Passing the hashes through fe, we can reconstruct the whole entity embedding matrix E R | |xd xd Additionally, is possible to enrich entity and relation embeddings by passing them through relational GNN encoder [31] over a target graph 9: E', R' = GNN( E, R, 9). In both ways, the entity embedding matrix E encodes a joint probability distribution p(h, r, for all triples in graph.

---

prodiction
trained with complex guery
Oth Of
Binary Classiffer
Of
Serats
CQD Beam parmeeeenc decoder)
Hi
O.K
Suntt
node upresentatoons through relation context
Spstia
relation structure W.E. anchors query
(hex)
Groer)
NodePlece-QE:
GNN-QE
Figure 2: Inductive node representation (NodePiece-QE, left) and relational structure (GNN-QE, right) strategies for complex logical query answering. NodePiece-QE, we obtain inductive node representations through the invariant set of tokens (here, through incident relation types). NodePiece- QE is an inference-only approach, pre-trained with simple 1p link prediction and can be directly applied to inductive complex queries with a non -orramemtriic decoder (e.g., CQD Beam). In GNN- QE, we learn the the relative structure of each node w.r.t. the anchor nodes in the query. GNN-QE trainable end-to-end on complex queries.
Having uniform featurization mechanism for both seen and unseen entities, it is now possible to apply any previously-transduetee complex query answering model with learnable entity embeddings and logical operators [23, 11, 24. 8]. Moreover, it recently shown [5] that combination of simple link prediction pre-training and a mon-nnnnaae parammeettric logical executor allows to effectively answer complex FOL queries in the inference-only regime without training any complex query sample. We adopt this Continuous Query Decomposition algorithm with beam search (CQD-Beam) as the main query answering decoder. CQD-Beam relies only entity and relation embeddings E. R pre-trained on simple 1p link prediction task. Then, given a complex query, CQD-Beam applies t-norms and r-conorms [19] that execute conjunctions (A) and disjunctions (V) as non-parametric algebraic operations in the embedding space, respectively.
In our inductive setup (Fig. 2), we train NodePiece encoder So and relation embeddings R (and optionally GNN) on the /p link prediction task over the training graph Grain- We then apply the learned encoder to materialize entity representations of the inference graph E Ed and send them to CQD-Bear Beam that performs non- non-parametric decoding of complex FOL queries over new unseen entities. The inference-only nature of NodePiece- QE is designed to probe the abilities for zero-shot generalization in performing complex logical reasoning over larger graphs.
4.2 GNN-QE: Inductive Relational Structure Representation
The second strategy relies on learning inductive relational structure representations instead of explicit node representations. Having the same set relation types R at training and inference time, we can parameterize each entity based on the relative relational structure between it and the anchor nodes given query. For instance (Fig. 2 right), given a query with a particular relational structure >- and set of anchor nodes, the representation of each node captures its relational structure relative to the anchor nodes. Each neighborhood expansion step is cquivalent to projection step in a complex query. In example, immediate neighboring nodes will capture the intersection pattern and structure
further nodes, in turn, capture the extended intersection-projeet
Therefore, node is likely to be an answer if its captured (or predicted) relational structure conforms with the query relational structure. As long as the set of relations is fixed, relation projection is performed in the same way for training or new unseen nodes. The idea of one-hop (Ip) projection for simple link prediction has been proposed by Neural Bellman-Ford Networks (NBFNet) [42].
In partieular, given relation projection query r, ?), NBFNet assigns unique initial states h to all nodes in graph by applying an indicator function (0) INDICATOR(h. v, i..., head node initialized with learnable relation embedding r and all other nodes are initialized with zeros. Then, NBFNet applies L relational message passing GNN layers where each layer / has its own learnable relation embedding matrix R()) obtained projection (and reshaping) of thein initial relation
5

---

R = W + b Final layer representations (D) are passed through an MLP and the sigmoid function a to get probability distribution over all nodes in graph p(t h4, r) = o (MLP(h (f)) As each projection query spawns a uniquely initialized graph and message passing procedure, NBFNet is seen to be applying a labeling trick [36] to model a conditional probability distribution p(t hh r) that provably more expressive than a joint distribution p(h,, r, produced by standard graph encoders.
Applied to complex queries, chaining & NBFNet instances allows us to answer k-hop projection queries, e.g., two instances for 2p queries. GNN-QE employs NBFNet as trainable projection operator and endows it with differentiable, non-parametric product logic for modeling conjunction
(A), disjunction (V): and negation (-) over the fuzzy sets of all entities E [o, 1,8, i.e., after applying a logical operator (discussed in Appendix A), each entity's degree of truth is associated with a sealar
in range [0, 1]. For the i-th hop projection, the indicator function initializes node state h with
(0)
relation vector r; weighted by a scalar probability predicted in the previous hop ze: h = ZeT Differentiable logical operators allow training GNN-QE end-to-end on complex queries.
Experiments
We designed the experimental agenda demonstrate that inductive representation strategies are able to: 1) answer complex logical queries over new, unseen entities at inference time, i.e., when query anchors are new nodes (Section 5.2); 2) predict new correct answers for known training queries when executed over larger inference graphs, i.e., when query anchors come from the training graph but variables and answers belong to the larger inference graph (Section 5.3); 3) generalize to inference graphs of up to 500% larger than training graphs; 4) scale to inductive query answering over graphs of millions of nodes when updated with 500k new nodes and 5M new edges (Section 5.5).
5.1 Setup & Dataset
Dataset. Due the absence of inductive logical query benchmarks, we create novel suite of datasets based on FB15k-237 [29] (open license) and following the query generation process of BetaE [24]. Given source graph with E entities, we sample Emaill r | [0.1, 0.9) nodes to induce a training graph Imain- For validation and test graphs, we split the remaining set of entities into two non-overlapping sets each with - E nodes. We then merge training and unseen nodes into the inference set of nodes Eny and induce inference graphs for validation and test from those sets, respectively, i.e., Eval = Emain U Eval and inf" = Emain U Elest- That is, validation and test inference graphs both extend the training graph but their sets of new entities are disjoint. Finally, we sample and remove 15% of edges Tpred in the inference graphs missing edges for sampling queries with those missing edges. Overall, we sample such datasets based on different choices of r, which result in the ratios of inference graph size to the training graph Eny/ Emain from 106% to 550%.
For each dataset, we employ the query sampler from BetaE [24] to extract 14 typical query types http:////i//p/////////////////
Training queries are sampled from the training graph Gvain. validation and test queries are sampled from their respective inference graphs Gin where at least one edge belongs to Tpead and has to be predicted at inference time.
As inference graphs extend training graphs, training queries are very likely to have new answers when executed over Ging with simple graph traversal and without any link prediction. We create an additional set of true answers for all training queries executed over the test inference graph Gay to measure the entailment capabilities of query answering models. This is designed to be an inference task and extends the faithfullness evaluation of [26]. Dataset statistics can be found in Appendix B.
Evaluation Protocol. Following the literature [24], query answers are separated into two sets: easy answers that only require graph traversal over existing edges, and hard answers that require inferring missing links to achieve the answer node. For the main experiment, evaluation involves ranking of hard answers against all entities having easy ones filtered out. For evaluating training queries on inference graphs, we only have easy answers and rank them against all entities. We report Hits @ 10 as the main performance metric on different query types.
Implementation Details. All NodePiece-based models [13] were pre-trained until convergence on a simple 1p link prediction task with the relations-only vocabulary and entity tokenization, MLP encoder, and ComplEx [30] scoring function. We used a 2-layer CompGCN [31] as an

---

Metric = Hits@ 10 query EPFO
Metric Hils@ 10 query neg
0.5
NodePlece-QEE
0.4
NodePlece-QE w/ GNN
metric
0.3
0.2
GNN-QE
Edge-type Heuristic
0.2
18
00:0..0"
100
200
300
400 500
100
200
300
400
500
Ratio Endin %
End Egatio.
Figure 3: Aggregated Hits 10 performance of test queries (involving unseen entities) executed on inference graphs of different ratios compared to training graphs. NodePiece-bon based models are inference-only and support EPFO queries, GNN-QE is trainable and supports negation queries.
Table I: Test @its@ 10 results (%) on answering inductive FOL queries when / 175%. avgn is the average on EPFO queries (A, V). avgn the average queries with negation.
Model
1p
3p
21
34
1p
2u
2hn
3m
Inp
pin
Transdactive
BetaE
1.3
0.2
2.9
0.4
0.4
2.1
3.3
1.5
0.7
0.2
0.2
0.1
0.2
0.2
0.1
0.1
Inductive Inferenceonll
Edge-type Heuristic
10.1
4.1
17.7
8.2
9.9
10.7
13.0
9.8
5.3
2.6
2.9
8.4
3.8
2.7
NodePiece-QQ QE
11.2
25.5
8.2
8.4
12.4
13.9
9.9
8.7
7.0
6.8
NodePiece- QF w/ GNN
28.6
45.9
19.2
11.5
39.9
48.8
29.4
22.6
25.3
14.6
Inductive Trainable
GNN-QE
50.7
33.6
65.4
36.3
31.6
73.8
84,3
56.5
41,5
39.3
28.0
33.3
46.4
29.2
24.9
34.0
optional message passing encoder on top of NodePiece features. The non-parametric CQD-Beam [5] decoder for answering complex queries is tuned for each query type based on the validation set of queries, most of the setups employ a product t-norm, sigmoid entity score normalization, and beam size of 32. Following the literature, the GNN-QE models [40] were trained on 10 query patterns http://pp/i.////////////////////
where ip/pi/2u/up are only seen inference time. Each model employs a 4- 4-layer NBFNet [42] as a trainable projection operator with DistMult [33] composition function and PNA [10] aggregation. Other logical operators (A, V. -) are executed with the non- parametric product f-norm and t-conorm. Both NodePiece QE and GNN-QE are implemented with PyTorch [22] and trained with the Adam [18] optimizer. NodePiece- QE models were pre-trained and evaluated on a single Tesla V100 32 GB GPU whereas GNN-QE models were trained and evaluated on Tesla V100 16GB. All hyperparameters are listed in Appendix To show that the proposed models are non-trivial, we compare them with an Edge-type Heuristic baseline (Appendix E), which selects all entities that satisfy the relations in the last hop of the query in Ginf-
5.2 Complex Query Answering over Unseen Entities on Differently Sized Inference Graphs
First, we probe inference-onf NodePiece-bars embedding models and trainable GNN-QE in the inductive setup, i.c., query answering over unseen nodes requiring link prediction over unseen nodes. As sanity check, compare them to the Edge-type Heuristic and a transductive BetaE model [24] trained with standard hyperparameters (Appendix D) on the reference dataset (with ratio Einy/Ereann of 175%) with randomly initialized embeddings for unseen nodes inference time. Table summarizes the results on the reference dataset while Fig. 3 illustrates a bigger picture on all datasets (we provide detailed breakdown by query type for all splits in Appendix C). The experiment on the tranductive BetaE confirms that pure transductive models can not generalize to graphs with unseen nodes.
With inductive models, however, observe that even inference-only models pre- mrentrained solely on simple Ip link prediction exhibit non-trivial performance in answering queries with unseen entities. Particularly, the inference-only NodePiece with GNN baseline exhibits better performance over all query types and inference graphs up to 300% larger than training graphs.
*Code and data available ht https: tttp:://gtt /ttp:://gthhb....// hwwp////oorrrghhhaaoorii////ddee
7

---

query = EPFO
query = neg avg
1.0
0.5
meltic
0.6
0.4
0.2
0.
100
200
300
400 500
100
200
300
400
500
Ratio Eagii %
Ratio EnalE %
Model NodePiece-QE NodePicco-QE GNN GNN-QE Edge-type Houristic
Graph
train
Figure 4: Aggregated Hits @ 10 performance of training queries on the original training and extended test inference graphs where queries have new correct answers. NodePiece- Peseecebbaee models are inference- only and support EPFO queries, GNN-QE is trainable and supports negation queries.
The trainable GNN-QE models expectedly outperform non-trainable baselines and can tackle queries with negation (-). Here, we confirm that the labeling trick [36] and conditional p(t],, r) modeling better capture the relation projection problem than joint p(h, r, encoding approaches.
Still, we notice that models with GNNs, i.c., inference-only NodePiece-QE with GNN and trainable GNN-QE, suffer from increasing the size of the inference graph and having more unseen entities. Reaching best results on Eig// Equin ratios around 130%, both approaches steadily deteriorate up until final 550% by 20 absolute Hits @ 10 points on EPFO queries and negation queries. We attribute this deterioration to the known generalization issues [20, 35] of message passing GNNs when performing inference over larger graph than the network has seen during training. Recently, few strategies have been proposed [7, 39] to alleviate this issue and we see it as promising avenue for future work. On the other hand, a simple NodePiece- QE model without message passing retains similar performance independently of the inference graph size.
Lastly, we observe that lower performance of inference-only NodePiece models can be also attributed to underfitting (cf. train graph charts in Fig. 4). Although 1p link predictors were trained until convergence (on the inductive validation set of missing triples), the performance of training queries on training graphs with easy answers that require only relation traversal without predicting missing edges is not yet saturated. This fact suggests that better fitting entity featurization (obtained by NodePiece or other strategies) could further improve the test performance in the inference-only regime. We leave the search of such strategies for future work.
5.3 Predicting New Answers for Training Queries on Larger Inference Graphs
Simulating the incremental addition of new edges in graph databases, we evaluate the performance of our inference-oni and trainable QE models on training queries on the original training graph and extended inference graph (with added test edges). As databases are able to immediately retrieve new answers to known queries after updating the graph, we aim exploring and quantifying this behaviour of neural reasoning models. this experiment, we probe training queries and their easy answers that require performing only graph traversal without predicting missing links in the inference graph. While execution of training queries over the training graph indicates how well the model could fit training data, executing training queries over the bigger inference graph with new entities aims to capture basic reasoning capabilities QE models in the inductive regime.
Particular challenges arising when executing training queries over bigger graph are: (1) the same queries can have more correct answers as more new nodes and edges satisfying the query pattern might have been added (as in Fig. 1); (2) more new entities create a "distractor" setting with more false positives. Generally, evaluation of training queries on the inference graph can be considered as extended version of the faithfullness [26] evaluation that captures how well trained model can answer original training queries, i.e., memorization capacity. In all 9 datasets, most of training queries have least new correct answer in the inference graph (more details in Appendix B).

---

Fig. 4 illustrates the performance of the Edge-type Heuristic baseline, inference-only NodePiece-O1 (without and with GNN) and trainable RNN-QE models. Generally, GNN-QE fits the training query data almost perfectly confirming the original finding [42] that NBFNet performs graph traversal akin to symbolic models. GNN-QE can also find new correct answers on graphs up to 300% larger than training ones. Then, the performance deteriorates which we attribute to the distractor factor with more unseen entities and the mentioned generalization issue on larger inference graphs.
The inference-only NodePiece-QE models, as expected, do not fully fit the training data as they were never trained on complex queries. Still, the inference-only models exhibit non-triviaa performance (compared to the Edge-type Heuristic) in finding more answers on graphs up to 200% larger than training ones with relatively small performance margins compared to training queries. The most surprising observation is that GNN-freee NodePiece- -EE models improve the performance on both training and inference graphs as the graphs (and the Eig!! Emiin ratio) grow larger while GNN-enriched models steadily deteriorate. We attribute this growth to the relation-based NodePiece tokenization and its learned features that tend to be more discriminative in larger inference graphs where new nodes have smaller degree and thus can be better identified by their incident relation types. We provide more experimental results for each dataset ratio with breakdown by query type in Appendix C.
5.4 Ranking of Easy and Hard Answers
In addition to evaluating faithfullness that measures whether a model could recover easy answers, also insightful to measure whether all easy answers can be ranked higher than hard answers. That is, a reliable query answering model would first recover all possible easy answers and would enrich the answer set with highly-probabe hard answers. To this end, we apply a ROC AUC metric over original unfiltered scores. The ROC AUC score measures how many hard answers are ranked after easy answers. Note that the score does not depend on actual values of ranks, that is, the metric will be high when easy answers are ranked, e.g., in between 100-1000 as long as hard answers are ranked 1001 and lower. Therefore, ROC AUC still needs to be paired with MRR to see how easy and hard answers are ranked absolutely.
Table 2: Macro-averaged ROC AUC score over unfiltered predictions on the reference Emaia 175% dataset to measure if all easy answers are ranked higher than hard answers. Higher is better.
Model
2p
21
31
2u
2in
3im
inp
pni
Inductise Infermorr-ooly
NodePiece QE
0.892
0.710
0.654
0.723
NodePloce-QE GNN
0.776
0.783
0.783
0.739
0.758
0.733
0.760
0.801
0.841
0.787
Indlective Praitable
GNN-QF
0,973
0.885
0.998
0.992
0.986
0.969
0.962
0.967
0.969
0.388
0.978
0,879
0.899
0.926
0.914
0.847
We compute ROC AUC for each query and average them over each query type thus making macro-averaged ROC AUC. Our experimental results on all query types using the models reported in Table on the reference 175% dataset are compiled in Table 2.
GNN-QE has nearly perfect ROC AUC scores as it was trained on complex queries. NodePiece-QE models are acceptable for inference-nnly models that were only trained only Ip simple link prediction and have never seen any complex query at training time.
5.5 Scaling to Millions of Nodes on WikiKG-QE
Finally, we perform a scalability experiment evaluating complex query answering in the inductive mode on a new large dataset WikiKG-QE constructed from OGB WikiKG [16] (CCO license). While the original task is transductive link prediction, we split the graph into training graph of 1.5M entities (5.8M edges, 512 unique relation types) and validation (test) graphs of 500k unseen nodes (5M known and 600k missing edges) each. The resulting validation (test) inference graphs are therefore of 2M entities and 1 IIM edges with the Enni/E ratio of 133% (details are in Appendix B).
GNN-QE cannot scale to such sizes, so we only probe NodePiece QE models. Due to the problem size, we only sample 10k EPFO queries of each type from the test inference graph to run in the inference-only regime. Each query has at least one missing edge to be predicted at inference. The answers are ranked against all 2M entities in the filtered setting (in contrast to the OGB task that ranks against 1000 pre-computed negative samples) and Hits @ 100 as the target metric.

---

We pre-train NodePiece encoder (in addition to relation types, we tokenize nodes with a vocabulary of 20k nodes, total 3M parameters in the encoder) with the ComplEx decoder on Ip link prediction over the training graph for IM steps (see Appendix D for hyperparameters). Then, the graph is extended with 500k new nodes and 5M new edges forming the inference graph. Then, using the pre-trained encoder, we materialize representations of entities (both seen and new) and relations from this inference graph. Finally, CQD- Beam executes the queries against the bigger inference graph extended with 500k new nodes and 5M new edges.
Table 3: Test Hits
@ 100 of NodePiece- QE on WikiKG-QE (2M nodes, 11M edges including 500k new nodes and 5M new edges) in the inference-only regime. avgp is the average on EPFO queries.
Model
avgp
1p
2p
3p
2i
3i
pi
ip
2u
up
Edge-type Heuristic
3.1
10.0
1.0
0.9
3.7
8.1
1.8
0.9
0.7
0.5
NodePiece-QE QE
9.2
22.6
5.2
3.9
11.6
17.4
7.0
4.5
7.4
3.2
NodePicce-QE w/ GNN
10.1
66.6
0.9
0.6
5,4
8.2
2.3
0.8
5.2
0.5
As shown in Table 3, we find a non-trivial performance of the inference-only model on EPFO queries demonstrating that inductive node representation QE models are able to scale to graphs with hundreds of thousands of new nodes and millions of new edges in the zero-shot fashion. That is, answering complex queries over unseen entities is available right upon updating the graph without the need to retrain a model. This fact paves the way for the concept of neural graph databases capable of performing zero-shot inference over updatable graphs without expensive retraining.
Limitations and Future Work
Limitations. With the two proposed inductive query answering strategies, we observe a common trade-off between the performance and computational complexity. That is, inductive node repre- sentation models like NodePiece-QU QE are fast, scalable, and can be executed in the inference-only regime but underperform compared to the inductive relational structure representation models like GNN-QE. On the other hand, GNN-QE incurs high computational costs due to executing each query on uniquely initialized graph instance. Alleviating this issue is key to scalability.
Societal Impact. The inductive setup assumes running inference on (partly) unseen data, that is, the nature of this unseen data might be out-of dfist--distttttion. unknown and potentially malicious. This fact has to be taken into account when evaluating predictions and overall system trustworthiness.
Conclusion and Future Work. In this work, we defined the problem of inductive complex logical query answering and proposed two possible parameterization strategies based node and relational structure representations to deal with new, unseen entities at inference time. Experiments demon- strated that both strategies are able to answer complex logical queries over unseen entities as well as identify new answers on larger inference graphs. In the future work, we plan to extend the inductive setup completely disjoint training and inference graphs, expand the set of supported logical query patterns aligned with popular queries over real-world KGs, enable reasoning over continuous features like texts and numbers, support more KG modalities like hypergraphs and hyper-relational graphs. and further explore the concept of neural graph databases.
Acknowledgments and Disclosure of Funding
This project is supported by 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-Bine Gift Fund and a NRC Collaborative R&D Project MA14DCORRE-0 This project was also partially funded by IVADO Fundamental Research Project grant PRF-2019-35831399 The computation resource of this project is supported by Calcul Québee" and Compute C We would like to thank anonymous reviewers for the comments that helped to improve the manuscript.
"httpp://www.calll www.caauueeee...cccm.mm ca/ httrpp://ww..cppptteaadaaaa ca/
10

---

References
[1] Mchdi Ali, Max Berrendorf, Charles Tapley Hoyt. Laurent Vermue, Mikhail Galkin, Sahand Sharifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework. IEEE Transactions Pattern Analysis and Machine Intelligence, 2021.
[2] Mchdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Sahand Sharifzadeh, Volker Tresp, and Jens Lehmann. PyKEEN 1.0: A Python Library for Training and Evaluating Knowledge Graph Embeddings. Journal of Machine Learning Research, 22(82): 2021.
[3] Dimitrios Alivanistos, Max Berrendorf, Michael Cochez, and Mikhail Galkin. Query embedding on hyper-relational knowledge graphs. International Conference on Learning Representations, 2022.
[4] Alfonso Amayuelas, Shuai Zhang, Xi Susie Rao, and Ce Zhang. Neural methods for logical reasoning over knowledge graphs. In International Conference on Learning Representations, 2022.
[5] Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021.
[6] Antoine Bordes, Nicolas Usunier, Alberto Garefa-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems
2013, pages 2787-2795, 2013.
[7] Davide Buffelli, Pietro Liò, and Fabio Vandin. SizeShiftRee: regularization method for improving size-generalization in graph neural networks. In Advances in Neural Information Processing Systems, 2022.
[8] Xuelu Chen, Ziniu Hu, and Yizhou Sun. Fuzzy logic based logical query answering on knowledge graph. In International Conference on Machine Learning. PMLR, 2021.
[9] Nurendra Choudhary, Nikhil Rao. Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy. Probabilistic entity representation model for reasoning over knowledge graphs. In Thirty-Fifth Conference Neural Information Processing Systems, 2021.
[10) Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1333 13271, 2020.
[11] Daniel Daza and Michael Cochez. Message passing query embedding, arXiv preprint arXiv:200..02406, 2020.
[12] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PoTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[13] Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L. Hamilton. Nodepiece: Compo- sitional and parameter-effiiient representations of large knowledge graphs. In International Conference on Learning Representations, 2022.
[14] Justin Gilmer, Samuel S. Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, volume 70 of Proceedings of Machine Learning Research, pages
PMLR, 2017.
[15) Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries knowledge graphs. Advances Neural Information Processing Systems, 31, 2018.
[16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020.
[17] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and Philip S. Yu. A survey on knowledge graphs: Representation, acquisition and applications. IEEE Transactions on Neural Networks and Learning Systems, 33(2):494-514, 2022.

---

[18] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
[19] Erich-Peter Klement, Radko Mesiar, and Endre Pap. Triangular norms. position paper I: basic analytical and algebraic properties. Fuzzy Sets Syst., 143(1):5-26, 2004.
[20] Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, pages
4204-4214, 2019.
[21] Bhushan Kotnis, Carolin Lawrence, and Mathias Niepert. Answering complex queries in knowledge graphs with bidirectional sequence encoders. CoRR, abs/2004.025% 2020.
[22] 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 De Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, pages 8024-8035, 2019.
[23] Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Reprexentations, 2019.
[24] Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. Advances in Neural Information Processing Systems, 33, 2020.
[25] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining knowledge graphs. Advances in Neural Information Processing Systems, 32, 2019.
[26] Haitian Sun, Andrew O. Amoll, Tania Bedrax- Weiss, Fernando Pereira, and William W. Cohen. Faithful embeddings for knowledge base queries. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[27] Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph em- bedding by relational rotation in complex space. In 7th International Conference on Learning Representations, ICLR 2019, OpenReview.net, 2019.
[28] Komal K. Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, volume 119 of Proceedings of Machine Learning Research, pages 9448-9457, PMLR. 2020.
[29] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, pages 57 57-66, Beijing, China, July 2015. Association for Computational Linguistics.
[30] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. International conference on machine learning, pages 2071-2080. PMLR, 2016.
[31] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi-relational graph convolutional networks. In International Conference on Learning Repre- sentations, 2020.
[32] Robert West, Evgeniy Gabrilovich, Kevin Murphy, Shaohua Sun, Rahul Gupta, and Dekang Lin. Knowledge base completion via search-based question answering. In 23rd International World Wide Web Conference, WWW 74, pages 515-526. ACM, 2014.
[33] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference knowledge bases. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
12

---

[34] Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems 30: Annaal Conference Neural Information Processing Systems 2017, pages 2319-2328, 2017.
[35] Gilad Yehudai, Ethan Fetaya, Eli A. Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In Proceedings of the 38th Interna- tional Conference on Machine Learning. ICML 2021, volume 139 of Proceedings of Machine Learning Research, pages 11975-11986, PMLR, 2021.
[36] 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-9073, Curran Associates, Inc., 2021.
[37] Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. In Ad- vances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, pages 2731-27411 2019.
[38] Zhanqiu Zhang, Jie Wang, Jiajun Chen, Shuiwang Ji, and Feng Wu. Cone: Cone embeddings for multi-hop reasoning over knowledge graphs. Advances in Neural Information Processing Systems, 34, 2021.
[39] Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. Ood link prediction generalization capabilities of pressage-passingg gnns in larger test graphs. In Advances in Neural Information Processing Systems, 2022.
[40] Zhaocheng Zhu, Mikhail Galkin, Zuobai Zhang, and Jian Tang. Neural-symbolic models for logical queries knowledge graphs. In International Conference Machine Learning. 1CML 2022, Proceedings of Machine Learning Research. PMLR, 2022.
[41] Zhaocheng Zhu, Chence Shi, Zuobai Zhang, Shengchao Liu, Minghao Xu, Xinyu Yuan, Yang- tian Zhang, Junkun Chen, Huiyu Cai, Jiarui Lu, Chang Ma, Runcheng Liu, Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Torchdrug: powerful and flexible machine learning platform for drug discovery, 2022.
[42] Zhaocheng Zhu, Zuobai Zhang, Louis- Pascal Xhonneux, and Jian Tang. Neural bellman- ford networks: A general graph neural network framework for link prediction. Advances Neural Information Processing Systems, 34, 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] Code and sample data are included the supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Dataset creation process is described in Section 5.1 with more details in Appendix B. Hyperparameters are specified in Appendix D.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No] We observe negligible variance w.r.t. random seeds
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] Training details specified in Section 5.1 and Appendix D.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL?
[Yes] Due to the overall size, include sample of the benchmarking suite in the supplemental material and will openly publish the whole dataset.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] No personal data involved
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] The datasets anonymized, discuss it in Appendix B.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "skRJ9zJA4J", "reviewer": "Reviewer_YzXG", "summary": "This work proposes the task of Inductive Logical Query Answering which is the natural next step after past work on:\n* KG Completion: Predicting new triples in a knowledge graph (KG) with a fixed set of entities\n* Inductive KG Completion: Predicting triples for new entities (and some of their triples) added to an existing KG\n* Logical Query Answering: Executing First-Order Logic (FOL) queries on a KG where we assume that the KG is incomplete and the set of answers contains more entities than those that can be predicted from just FOL query execution\n\nInductive Logical Query Answering is then executing FOL queries in a KG where new entities are added at inference time. The inductive settings are motivated by real-world scenarios where KGs are constantly being updated with new information and new entities.\n\nThe authors then propose two approaches (each with its own strengths and weaknesses) to solve the task.", "questions": "* Line 208: Can you flesh out how the mechanism of NBFNet is a *labeling trick*?\n* This is somewhat implied from the text. Are the validation and test queries guaranteed to require missing edges to find the full answer set? Does the query sampling ensure this?\n* How do you explain the initial increase in performance as the graph grows (e.g. in Fig 3)?\n* Line 347: Performance in Table 2 on the large 2M node graph shows the accuracy of <10%. Why is this considered non-trivial? Is trivial just considered random guessing performance? There should be better baseline estimates that can scale to this graph size with graph neighborhood sampling.\n* Following up on the discussion of better evaluation metrics, how many times does the system predict a \"hard\" answer higher than an \"easy\" answer? Is this a strict constraint that should be applied when evaluating systems on these tasks?", "limitations": "The weakness section highlights a missing discussion on the evaluation of systems in the inductive setting. This is a limitation of the query answering task in general and not just of this work. However, given that this work adds an additional component of inductive KG growth, this discussion seems relevant and necessary for completeness.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n[+] Inductive query answering is well-motivated as an extension of past work. This work is also well-placed with respect to related work.\n\n[+] The paper is well-presented and descriptions are mostly sufficient to understand the work.\n\n[+] The baseline approaches described are suitable for the task and have complementary strengths and weaknesses.\n\nWeaknesses\n\n[-] There should be more discussion on evaluating FOL execution systems in the inductive setting and what the right metric for the task is. \n\nReporting accuracy of the systems on train queries at inference is an important first step toward establishing \"faithfulness\". Can we trust a system that does not achieve 100% accuracy on \"easy\" answers?\n\nSimilarly, just reporting Hits@10 (after filtering out \"Easy\" answers) hides under the rug what it means to predict a \"hard\" answer at a higher rank than an \"easy\" answer (before filtering). Personally, I am of the opinion that the evaluation metric should penalize any entity being predicted as an answer before all the \"easy\" answers are enumerated. This ensures trust in the system to first execute the FOL query when possible and only then resort to \"guessing\" more answers by filling in missing edges.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bOmJy3B1Zrf", "reviewer": "Reviewer_PdEh", "summary": "This work studies the inductive query answering task where inference is performed on a graph containing new entities with queries over both seen and unseen entities. Which is a sound contribution to the field of query answering and knowledge graph completion.\n\nThe authors argue that several existing studies on complex query answering with logical operators have been conducted in transductive mode where the set of entities does not change at inference time.\n\nThe aim of this study is to extend the complex logical query answering to inductive representation learning algorithms. Focusing on the inductive setup where an inference graph is a superset of a training graph such that:\n- Inference queries require reasoning over both seen and new entities; \n- Original training queries might have more correct answers at inference time with  the addition of new entities.\n\nIn this work;\n- They show that inductive models are able to perform logical reasoning at inference time over unseen nodes generalizing to graphs up to 500% larger than training ones. \n- They also explore the efficiency-effectiveness trade-off, and the findings indicate that the inductive relational structure method generally achieves higher performance.\n- Also the inductive node representation method is able to answer complex queries in the inference regime only without any training on queries and scale to graphs of millions of nodes.\n", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper extends the idea of inductive representation learning algorithms to logical query answering where inference queries require reasoning over both seen and new entities which is a sound contribution to the field of query answering and knowledge graph completion. \n- The authors also cite/explain the related works in both knowledge graph completion and complex query answering. The paper also makes a good differentiation between the proposed approach and the existing work.\n\n- The paper is well written, with elaborative figures and experimental results support the proposed method.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V7wszp_QQHJ", "reviewer": "Reviewer_YfZT", "summary": "In this paper, the authors studied the problem of logical query answering over knowledge graphs under an inductive setting. Existing methods usually focus on the transductive setting where all nodes and edges are seen during the training stage. This work goes beyond and investigates the scenario where there are unseen nodes in the validation and testing stages. To tackle this problem, they proposed two methods and demonstrated their effectiveness via extensive experiments.", "questions": "- Since the node representation is learned using the edge structural patterns. I am wondering if the model will output the same representations for different nodes (which I think is not ideal). \n- Is there any way to marry the benefits of both models?\n", "limitations": "Although the NBFNet-QE can achieve good performance, it is not scalable, and no results are reported for the WikiKG dataset. However, the more efficient NodePiece-QE performs rather worse. This limitation makes me doubt the usability of the proposed two approaches.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength\n- The studied problem is novel and interesting. The inductive setting is novel and more generalized.\n- They set up new benchmarks for the inductive logical query task by constructing two new datasets, one using FB15K-237 and a large one using OBG WikiKG.\n- The proposed NBFNet-QE performs well on the new FB15K-237 dataset (The numbers are relatively higher compared to the transductive setting) and outperforms NodePiece-QE by a large margin. This finding is interesting and may provide directions for future improvement.\n- The presentation is clear and easy to follow.\n\n### Weakness\n- The contribution to the model design is rather incremental. Both models (NodePiece and NBFNET) are based on existing works on link prediction (a simpler yet closely related task). The query answering part is also based on existing transductive logical query answering models  (e.g., CQD) on KG. \n- The proposed framework is only applicable to unseen nodes as the node representation learning process heavily depends on the edges (relations). It cannot deal with unseen relations.\n- The discussion on the efficiency-effectiveness trade-off between NodePiece-QEand NBFNet-QE is a bit trivial. Solutions/insights that can address this trade-off are expected.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QlQyyvwltlM", "reviewer": "Reviewer_tzzT", "summary": "The paper proposed a graph-based reasoning task in an inductive setting. Different from previously studied transductive reasoning task, a reasoning task contains unseen entities at inference time. Previous QE methods are unable to handle unseen entities.", "questions": "1. For both methods, do you make the assumption that \"anchor\" entities are seen at training time?\n\n2. Could you please provide more information about the CQD-Beam method for decoding? How are the entity embeddings used in CQD-Beam? CQD-Beam is not a widely known methods so it may be confusing to readers.\n\n3. In the NBFNet-QE method, the authors made an assumption that all edges (KB triples) that are required for prediction are present in the graph. How will your model be affected by an incomplete KB?\n", "limitations": "The authors claim the most important limitation of this work is the tradeoff between performance and computation complexity. While this is true, the authors should consider discussing more general limitations of this work, e.g. to what extent will this model work with unseen relations, sparse graphs with very few edges for nodes, types of supported reasoning operations, etc. More importantly, please compare your model with external baselines to justify your experiment results.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper discussed two methods to handle unseen entities at inference time, NodePiece-QE and NBFNet-QE. In NodePiece-QE, the model computes embeddings for unseen entities from the relations of their neighbors. In NBFNet-QE, the model does not explicitly compute entity embeddings, but instead matching the graph structures locally. Both methods are plausible in solving the problem of novel entities. Experiment results show that the proposed methods achieve reasonable results. \n\nHowever, I am a bit concern about the soundness of experiments. The authors experimented their models on a modified datasets to test models' ability in handle novel entities. They did not compare the performance of their model to any other external baselines, so it's not clear how well the proposed models perform. The reported metric, i.e. Hits@10, is highly dependent on the incoming / outgoing degree of the \"anchor\" nodes. Please consider carefully compare your models with other external baselines.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept