Neural-Symbolic Models for Logical Queries on Knowledge Graphs

Introduction

Knowledge graphs (KGs) encapsulate knowledge about the world in a collection of relational edges between entities, and are widely adopted by many domains (Miller, 1998; Vrandečić & Krötzsch, 2014; Himmelstein et al., 2017; Szklarczyk et al., 2019). Reasoning on knowledge graphs has attracted much attention in artificial intelligence, since it can be used to infer new knowledge or answer queries based on existing knowledge. One particular reasoning task we are interested in is answering complex First-Order Logic (FOL) queries on knowledge graphs, which involves logic operations like existential quantifier ($\exists$), conjunction ($\land$), disjunction ($\lor$) and negation ($\neg$). For example, the question “Which universities do the Turing Award winners of deep learning work in?” can be represented as a FOL query, as showed in Fig. 1.

Traditionally, the problem of reasoning is handled by symbolic approaches, such as logic programming (Lloyd, 2012), fuzzy logic (Klir & Yuan, 1995) or probabilistic reasoning (Pearl, 2014). In the same vein, several algorithms (Dalvi & Suciu, 2007; Schmidt et al., 2010; Zou et al., 2011) have been developed for searching the answers to complex queries on graph databases. These methods traverse a graph and extract all possible assignments for intermediate variables, which provides good interpretation for each step. Besides, symbolic methods are guaranteed to produce the correct answer if all facts are given (Stuart & Peter, 2016). However, many real-world knowledge graphs are known to be incomplete (Nickel et al., 2015), which limits the usage of symbolic methods on knowledge graphs.

Recently, neural methods, such as embedding methods (Bordes et al., 2013; Trouillon et al., 2016; Sun et al., 2018) and graph neural networks (GNNs) (Schlichtkrull et al., 2018; Vashishth et al., 2019; Teru et al., 2020; Zhu et al., 2021), have achieved significant progress in knowledge graph completion. Based on the success of these neural methods, many works have been proposed to solve FOL queries on incomplete graphs by learning an embedding for each FOL query (Hamilton et al., 2018; Ren et al., 2019; Ren & Leskovec, 2020; Chen et al., 2021; Zhang et al., 2021b). Typically, these methods translate the logic operations into neural logic operators in the embedding space. Nevertheless, it is hard to interpret what set of entities an intermediate embedding encodes, leaving the reasoning process unknown to users. The only interpretable method is CQD-Beam (Arakelyan et al., 2021), which applies beam search to a pretrained embedding model in the entity space. However, the complexity of exhaustive search prevents CQD-Beam from being trained directly on complex queries.

In this paper, we marry the advantages from both neural and symbolic approaches, and propose Graph Neural Network Query Executor (GNN-QE), a neural-symbolic method for answering FOL queries on incomplete knowledge graphs. Following symbolic methods that output a set of assignments for each intermediate variable, we decompose a complex FOL query into an expression over fuzzy sets (i.e., a continuous relaxation of sets), which attains interpretability for intermediate variables. Each basic operation in the expression is either a relation projection or a logic operation (e.g., conjunction, disjunction and negation). We design the relation projection to be a GNN that predicts the fuzzy set of tail entities given a fuzzy set of head entities and a relation. The logic operations are transformed to the product fuzzy logic operations over fuzzy sets, which satisfy logic laws and enable differentiation of logic operations. We also propose traversal dropout to regularize the model, and batch expression execution to speed up training and inference.

We evaluate our method on 3 standard datasets for FOL queries. Experiments show that GNN-QE achieves new state-of-the-art performance on all datasets, with an average relative gain of 22.3% on existential positive first-order (EPFO) queries and 95.1% on negation queries (Sec. 5.2). By disentangling the contribution of knowledge graph completion and complex query framework, we find that GNN-QE achieves one of the best generalization performances from knowledge graph completion to EPFO queries among different methods. Additionally, the symbolic formulation of our method enables us to predict the number of answers without explicit supervision (Sec. 5.3), and visualize intermediate variables (Sec. 5.4 & App. E). The visualization provided by GNN-QE may help us better understand the reasoning process taken by the model, leading to more interpretable multi-hop reasoning.

Related Work

Knowledge Graph Completion Recent years have witnessed a significant progress in reasoning about missing links on a knowledge graph. Notably, embedding methods (Bordes et al., 2013; Yang et al., 2015; Trouillon et al., 2016; Sun et al., 2018; Amin et al., 2020) learn a low-dimensional vector for each entity and relation, which preserves the structure of the knowledge graph. Reinforcement learning methods (Xiong et al., 2017; Das et al., 2018; Hildebrandt et al., 2020; Zhang et al., 2021a) train an agent to collect necessary paths for predicting the link between entities. Rule learning methods (Yang et al., 2017; Sadeghian et al., 2019; Qu et al., 2021) first extract interpretable logic rules from the knowledge graph, and then use the rules to predict the links. Another stream of works adopts graph neural networks (GNNs) to learn the entity representations (Schlichtkrull et al., 2018; Vashishth et al., 2019), or the pairwise representations (Teru et al., 2020; Zhu et al., 2021) for knowledge graph completion. Our method adapts a GNN from knowledge graph completion (Zhu et al., 2021) to implement the relation projection on knowledge graphs. However, GNN-QE is designed to answer complex logical queries, a more challenging task than KG completion.

Complex Logical Query Complex logical query extends knowledge graph completion to predict answer entities for queries with conjunction, disjunction or negation operators. Guu et al. (2015) proposes compositional training for embedding methods to predict answers for path queries. GQE (Hamilton et al., 2018) learns a geometric intersection operator to answer conjunctive queries ($\land$) in the embedding space, which is later extended by Query2Box (Ren et al., 2019) to EPFO queries ($\exists$, $\land$, $\lor$) and BetaE (Ren & Leskovec, 2020) to FOL queries ($\exists$, $\land$, $\lor$, $\neg$). FuzzQE (Chen et al., 2021) improves embedding methods with t-norm fuzzy logic, which satisfies the axiomatic system of classical logic. Some recent works utilize advanced geometric embeddings to achieve desired properties for operators, e.g., hyperboloid embeddings in HypE (Choudhary et al., 2021) and cone embeddings in ConE (Zhang et al., 2021b). Generally, all these methods compute an embedding for the query, and decode the answers with nearest neighbor search or dot product. However, the interpretability of embedding methods is usually compromised, i.e., there is no simple way to understand intermediate reasoning results.

Some other works combine neural methods with symbolic algorithms to solve the complex query answering problem. EmQL (Sun et al., 2020) ensembles an embedding model and a count-min sketch, and is able to find logically entailed answers. CQD (Arakelyan et al., 2021) extends a pretrained knowledge graph embedding model to infer answers for complex queries, with CQD-CO based on continuous optimization and CQD-Beam based on beam search. Our method shares a similar spirit with CQD-Beam in the sense that both models wrap a knowledge graph completion model with symbolic algorithms. However, CQD-Beam cannot be directly trained on complex query due to the complexity incurred by exhaustive search. By contrast, GNN-QE is trained directly on complex queries without pretrained embedding models.

Preliminary

In this section, we introduce the background knowledge of FOL queries on knowledge graphs and fuzzy sets.

Given a set of entities ${\mathcal{V}}$ and a set of relations ${\mathcal{R}}$, a knowledge graph ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\mathcal{R}})$ is a collection of triplets ${\mathcal{E}}=\{(h_{i},r_{i},t_{i})\}\subseteq{\mathcal{V}}\times{\mathcal{R}}\times{\mathcal{V}}$, where each triplet is a fact from head entity $h_{i}$ to tail entity $t_{i}$ with the relation type $r_{i}$.

A FOL query on a knowledge graph is a formula composed of constants (denoted with English terms), variables (denoted with $a$, $b$, $c$), relation symbols (denoted with $R(a,b)$) and logic symbols ($\exists$, $\land$, $\lor$, $\neg$). In the context of knowledge graphs, each constant or variable is an entity in ${\mathcal{V}}$. A variable is bounded if it is quantified in the expression, and free otherwise. Each relation symbol $R(a,b)$ is a binary function that indicates whether there is a relation $R$ between a pair of constants or variables. For logic symbols, we consider queries that contain conjunction ($\land$), disjunction ($\lor$), negation ($\neg$) and existential quantification ($\exists$)Note universal quantification ($\forall$) is excluded, since none of the entities connects to all entities in a real-world knowledge graph.. Fig. 1 illustrates the FOL query for the natural language question “Which universities do the Turing Award winners of deep learning work in?”. Given a FOL query, the goal is to find answers to the free variables, such that the formula is true.

2 Fuzzy Sets and Fuzzy Logic Operations

Fuzzy sets (Klir & Yuan, 1995) are a continuous relaxation of sets whose elements have degrees of membership. A fuzzy set ${\mathcal{A}}=({\mathcal{U}},x)$ contains a universal set ${\mathcal{U}}$ and a membership function $x:{\mathcal{U}}\to$. For each $u\in{\mathcal{U}}$, the value of $x(u)$ defines the degree of membership (i.e., probability) for $u$ in ${\mathcal{A}}$. Similar to Boolean logic, fuzzy logic defines three logic operations, AND, OR and NOT, over the real-valued degree of membership. There are several alternative definitions for these operations, such as product fuzzy logic, Gödel fuzzy logic and Łukasiewicz fuzzy logic.

In this paper, fuzzy sets are used to represent the assignments of variables in FOL queries, where the universe ${\mathcal{U}}$ is always the set of entities ${\mathcal{V}}$ in the knowledge graph. Since the universe is a finite set, we represent the membership function $x$ as a vector ${\bm{x}}$. We use $x_{u}$ to denote the degree of membership for element $u$. For simplicity, we abbreviate a fuzzy set ${\mathcal{A}}=({\mathcal{U}},x)$ as ${\bm{x}}$ throughout the paper.

Proposed Method

Here we present our model, Graph Neural Network Query Executor (GNN-QE). The high-level idea of GNN-QE is to first decompose a FOL query into an expression of 4 basic operations (relation projection, conjunction, disjunction and negation) over fuzzy sets, then parameterize the relation projection with a GNN adapted from KG completion, and instantiate the logic operations with product fuzzy logic operations. Besides, we introduce traversal dropout to prevent the GNN from converging to a trivial solution, and batched expression execution for speeding up training and inference.

Given a FOL query, the first step is to convert it into an expression of basic operations, so that we can retrieve answers by executing the expression. Previous works define basic operations as either relation projections and logic operations over embeddings (Ren et al., 2019; Ren & Leskovec, 2020; Chen et al., 2021; Zhang et al., 2021b), or a score function over triplets (Arakelyan et al., 2021). To achieve better interpretability for intermediate variables, we explicitly define 4 basic operations over fuzzy sets of entities as follows

Relation Projection: ${\mathcal{P}}_{q}({\bm{x}})$ computes the fuzzy set of tail entities that are reachable by the input fuzzy set of head entities through relation $q$. ${\mathcal{P}}_{q^{-1}}({\bm{x}})$ computes the fuzzy set of head entities that can reach the input fuzzy set of tail entities through relation $q$.

Conjunction: ${\mathcal{C}}({\bm{x}},{\bm{y}})$ computes the logical conjunction for each element in ${\bm{x}}$ and ${\bm{y}}$.

Disjunction: ${\mathcal{D}}({\bm{x}},{\bm{y}})$ computes the logical disjunction for each element in ${\bm{x}}$ and ${\bm{y}}$.

Negation: ${\mathcal{N}}({\bm{x}})$ computes the logical negation for each element in ${\bm{x}}$.

where ${\bm{x}},{\bm{y}}\in^{\mathcal{V}}$ are two vector representations of fuzzy sets. We then decompose a FOL query into an expression of the above operations. For the example in Fig. 1, the corresponding expression is

where {Turing Award} and {Deep Learning} denote singleton sets of Turing Award and Deep Learning, respectively.

2 Neural Relation Projection

In order to solve complex queries on incomplete knowledge graphs, we learn a neural model to perform the relation projection ${\bm{y}}={\mathcal{P}}_{q}({\bm{x}})$. Specifically, the neural relation projection model should predict the fuzzy set of tail entities ${\bm{y}}$ given the fuzzy set of head entities ${\bm{x}}$ and a relation $q$ in the presence of missing links. This is in contrast to the common GNNs (Schlichtkrull et al., 2018; Vashishth et al., 2019) and embedding methods (Bordes et al., 2013; Sun et al., 2018) for knowledge graph completion, which operate on individual entities $x$ and $y$. While it is possible to apply such GNNs or embedding methods for relation projection, it takes at least $O(|{\mathcal{V}}|^{2}d)$ time to compute them for every $x\in{\bm{x}}$ and $y\in{\bm{y}}$, which is not scalable.

Recently, Zhu et al. (2021) introduced a new GNN framework for knowledge graph completion, which can predict the set of tail entities ${\bm{y}}$ given an entity $x$ and a relation $q$ in $O(|{\mathcal{V}}|d^{2}+|{\mathcal{E}}|d)$ time. Inspired by such a framework, we propose a scalable GNN solution for relation projection.

Graph Neural Networks. Our goal is to design a GNN model that predicts a fuzzy set of tail entities given a fuzzy set of head entities and a relation. A special case of the input is a singleton set, where we need to model the probability $p_{q}(y|x)$ for every $y\in{\bm{y}}$. Such a problem can be solved by GNNs in a single-source fashion (You et al., 2021; Zhu et al., 2021). For example, the recent work NBFNet (Zhu et al., 2021) derives a GNN framework based on the generalized Bellman-Ford algorithm for single-source problems on graphs. Given a head entity $u$ and a projection relation $q$, we use the following iteration to compute a representation ${\bm{h}}_{v}$ for each entity $v\in{\mathcal{V}}$ w.r.t. the source entity $u$:

where the Indicator function initializes a relation embedding ${\bm{q}}$ on entity $v$ if $v$ equals to $u$ and a zero embedding otherwise, and ${\mathcal{E}}(v)$ is the set of edges going into $v$. The Message and Aggregate functions can be instantiated with any neural function from popular GNNs. To apply the above framework to a fuzzy set ${\bm{x}}$ of head entities, we propose to replace Eqn. 2 with the following initialization

where $x_{v}$ is the probability of entity $v$ in ${\bm{x}}$. Intuitively, this GNN model initializes an embedding ${\bm{q}}$ for the projection relation $q$ on all entities, where the scale of the initialization on an entity depends on its probability in the fuzzy set. The original Indicator function can be viewed as a special case of Eqn. 4, with the fuzzy set being a singleton set.

For the Aggregate and the Message functions, we follow the design in NBFNet (Zhu et al., 2021) and parameterize the Message function as

where ${\bm{W}}^{(t)}_{r}$ and ${\bm{b}}^{(t)}_{r}$ are the weight matrix and bias vector for relation $r$ in the $t$-th iteration respectively, and $\odot$ is the element-wise multiplication operator. The Aggregate function is parameterized as the principal neighborhood aggregation (PNA) (Corso et al., 2020). Our GNN has the same time complexity as NBFNet, and therefore takes $O(|{\mathcal{V}}|d^{2}+|{\mathcal{E}}|d)$ time for each message passing iteration. Note it is possible to parameterize the framework with other GNN models, such as RGCN (Schlichtkrull et al., 2018) or CompGCN (Vashishth et al., 2019). See Sec. 5.5 for experiments with different GNN models.

To apply the GNN framework for relation projection, we propagate the representations with Eqn. 3 for $T$ layers. Then we take the representations in the last layer, and pass them into a multi-layer perceptron (MLP) $f$ followed by a sigmoid function $\sigma$ to predict the fuzzy set of tail entities.

3 Fuzzy Logic Operations

The logic operations (i.e., ${\mathcal{C}}({\bm{x}},{\bm{y}})$, ${\mathcal{D}}({\bm{x}},{\bm{y}})$, ${\mathcal{N}}({\bm{x}})$) glue multiple relation projection results and generate the input fuzzy set for the next relation projection. Ideally, they should satisfy certain logic laws, such as commutativity, associativity and non-contradiction. Most previous works (Hamilton et al., 2018; Ren et al., 2019; Ren & Leskovec, 2020; Zhang et al., 2021b) propose dedicated geometric operations to learn these logic operations in the embedding space. Nevertheless, these neural operators are not guaranteed to satisfy most logic laws, which may introduce additional error when they are chained together.

Here we model the conjunction, disjunction and negation with product fuzzy logic operations. Given two fuzzy sets ${\bm{x}},{\bm{y}}\in^{\mathcal{V}}$, the operations are defined as follows

where $\odot$ is the element-wise multiplication and $\bm{1}$ is a vector of all ones (i.e., the universe). Compared to geometric operations in previous works, such fuzzy logic operations satisfy many logic laws, e.g., De Morgan’s laws ${\mathcal{N}}({\mathcal{C}}({\bm{x}},{\bm{y}}))={\mathcal{D}}({\mathcal{N}}({\bm{x}}),{\mathcal{N}}({\bm{y}}))$, ${\mathcal{N}}({\mathcal{D}}({\bm{x}},{\bm{y}}))={\mathcal{C}}({\mathcal{N}}({\bm{x}}),{\mathcal{N}}({\bm{y}}))$. Note FuzzQE (Chen et al., 2021) also adopts fuzzy logic operations and satisfies logic laws. However, FuzzQE applies fuzzy logic operations to embeddings. By contrast, our GNN-QE applies fuzzy logic operations to fuzzy sets of entities, which provides better interpretability (See Sec. 5.4).

4 Learning

Following previous works (Ren et al., 2019; Ren & Leskovec, 2020; Zhang et al., 2021b), we train our model to minimize the binary cross entropy loss.

where ${\mathcal{A}}_{Q}$ is the set of answers to the complex query $Q$ and $p(a|Q)$ is the probability of entity $a$ in the final output fuzzy set. Since GNN-QE always outputs the probability for all entities (Eqn. 6), we do not perform negative sampling and compute the loss with all negative answers.

Traversal Dropout. One challenge in training GNN-QE is to let the model generalize to incomplete KGs at test time. This is because all the training queries are generated by assuming the training graph is complete (Ren & Leskovec, 2020). In other words, all the training queries can be perfectly solved by a simple relation traversal model on the training graph, without modeling any missing link. GNN models can easily discover this mode, which does not generalize to incomplete knowledge graphs at test time.

To solve this issue, we introduce traversal dropout to create an incomplete KG at training time. Specifically, we first run a relation traversal model to extract all the edges corresponding to the query. We then randomly mask out the traversed edges in each relation projection with probability $p$. Intuitively, the probability $p$ trades off between a simple relation traversal model and a full reasoning model. If $p$ is small, the GNN model may converge to a trivial relation traversal model, otherwise it is forced to encode non-trivial reasoning features. Since some of the edges in the test queries may be present in the KG, it is not always optimal to use a large $p$ to discourage a relation traversal model. In practice, we treat $p$ as a hyperparameter, and tune it based on the performance on the validation set. See Sec. 5.5 for experiments with different values of $p$.

Batched Expression ExecutionExpression execution is formally known as expression evaluation in computer science. In this paper, we use the term “expression execution” to avoid ambiguity in machine learning contexts.. Modern machine learning relies on batch processing on GPUs to accelerate the computation of neural (or even symbolic) models. However, it is challenging to batch the expressions of FOL queries, since different query structures require different recursive computation steps. Previous works (Hamilton et al., 2018; Ren et al., 2019; Ren & Leskovec, 2020) divide a batch based on the query structure of each sample, and only batch the computation of samples that have the same structure. However, such an implementation needs to enumerate every query structure, and is not scalable when the vocabulary of query structures grows large.

To solve this issue, we need to find a way to execute the expressions without recursion. This can be achieved by converting the expressions into postfix notation. The postfix notation, a.k.a. reverse Polish notation (Lukasiewicz, 1951), writes operators after their operands in an expression. For example, the postfix expression of Eqn. 1 is

The advantage of postfix expressions is that they are unambiguous without parentheses, and therefore can be executed easily without recursion. To execute a postfix expression, we allocate a stack and scan the expression from left to right. When we encounter an operand, we push it into the stack. When we encounter an operator, we pop the corresponding number of operands from the stack, apply the operation and push the result into the stack. Such an algorithm can be easily batched for the same operator even in samples of different query types. Examples and pseudo code for batched expression execution are provided in App. C.

Experiments

In this section, we evaluate GNN-QE by answering FOL queries on 3 standard datasets. Our experiments demonstrate that: (1) GNN-QE outperforms existing methods on both EPFO queries and queries with negation. (2) GNN-QE can predict the number of answers out-of-the-box without any explicit supervision. (3) We can visualize the intermediate variables of GNN-QE and interpret its reasoning process.

We evaluate our method on FB15k (Bordes et al., 2013), FB15k-237 (Toutanova & Chen, 2015) and NELL995 (Xiong et al., 2017) knowledge graphs. To make a fair comparison with baselines, we use the standard train, validation and test FOL queries generated by the BetaE paper (Ren & Leskovec, 2020), which consist of 9 EPFO query types and 5 query types with negation. We follow previous works (Ren & Leskovec, 2020; Chen et al., 2021; Zhang et al., 2021b) and train our model with 10 query types (1p/2p/3p/2i/3i/2in/3in/inp/pni/pin). The model is evaluated on 10 training query types, plus 4 query types (ip/pi/2u/up) that have never been seen during training. A full list of query types and their statistics is provided in App. A.

Evaluation Protocol. Following the evaluation protocol in (Ren et al., 2019), we separate the answers to each query into two sets: easy answers and hard answers. For test (validation) queries, easy answers are the entities that can be reached on the validation (train) graph via a symbolic relation traverse model. Hard answers are those that can only be reached with predicted links. In other words, the model must perform reasoning to get the hard answers. We compute the ranking of each hard answer against all non-answer entities. The performance is measured by mean reciprocal rank (MRR) and HITS at K (H@K) metrics.

Implementation Details. Our work is implemented based on the open-source codebase of GNNs for KG completionhttps://github.com/DeepGraphLearning/NBFNet. Following (Zhu et al., 2021), we augment each triplet with a flipped one of its inverse relation, so that the GNN can propagate information in both directions. The neural relation projection model is set to a 4-layer GNN model. We train the model with the self-adversarial negative sampling (Sun et al., 2018). Note we only instantiate 1 GNN model and share it across all neural relation projections in the query. For query types that contain multiple relation projections in a chain (2p/3p/inp/pni/pin), we observe very noisy gradients for the relation projections early in the chain. Therefore, we zero out the gradients of those relation projections, and only update the GNN with gradients from the last relation projections close to the loss. Our model is trained with Adam optimizer (Kingma & Ba, 2014) on 4 Tesla V100 GPUs. Hyperparameters of GNN-QE are given in App. B.

Baselines. We compare GNN-QE against both embedding methods and neural-symbolic methods. The embedding methods include GQE (Hamilton et al., 2018), Q2B (Ren et al., 2019), BetaE (Ren & Leskovec, 2020), FuzzQE (Chen et al., 2021) and ConE (Zhang et al., 2021b). The neural-symbolic methods include CQD-CO (Arakelyan et al., 2021) and CQD-Beam (Arakelyan et al., 2021). For CQD-CO and CQD-Beam, we obtain their performance using the codebasehttps://github.com/pminervini/KGReasoning provided by the original authors.

2 Complex Query Answering

Tab. 1 shows the MRR results of different models for answering FOL queries. GQE, Q2B, CQD-CO and CQD-Beam do not support queries with negation, so the corresponding entries are empty. We observe that GNN-QE achieves the best result for both EPFO queries and queries with negation on all 3 datasets. Notably, GNN-QE achieves an average relative gain of 22.3% in avgp and 95.1% in avgn compared to previous best model ConE. We attribute this gain to the advantage of fuzzy sets over geometric embeddings. Fuzzy sets can easily model intermediate variables with many possible assignments, while it is hard to embed a large number of entities in a low-dimensional vector. Such an advantage is especially useful for negation operations, since the output of a negation operation usually contains nearly $|{\mathcal{V}}|$ entities.

Intuitively, the performance of complex query models should benefit from better KG completion performance, i.e., 1p queries. Here we disentangle the contribution of KG completion and complex query framework in answering EPFO queries. Fig. 2 plots the performance of EPFO queries w.r.t. the performance of KG completion on all datasets. Methods on the top-left corner of each plot show a better generalization from KG completion to EPFO queries, which implies their complex query frameworks are better. These include GQE, BetaE, FuzzQE, ConE and GNN-QE. By contrast, CQD-CO and CQD-Beam generalize worse than other methods, because they rely on a pretrained embedding model and cannot be trained for complex queries.

3 Answer Set Cardinality Prediction

One advantage of GNN-QE is that it can predict the cardinality of the answer set (i.e., the number of answers) without explicit supervision. Specifically, the cardinality of a fuzzy set is computed as the sum of entity probabilities exceeding a certain threshold. We use 0.5 for the threshold as it is a natural choice for our binary classification loss (Eqn. 10). Tab. 2 shows the mean absolute percentage error (MAPE) between our model prediction and the ground truth. Note none of existing methods can predict the number of answers without explicit supervision. Ren & Leskovec (2020) and Zhang et al. (2021b) observe that the uncertainty of Q2B, BetaE and ConE are positively correlated with the number of answers. We follow their setting and report the Spearman’s rank correlation between our model prediction and the ground truth. As showed in Tab. 3, GNN-QE outperforms existing methods by a large margin on all query types.

4 Intermediate Variables Visualization

Another advantage of GNN-QE is that we can interpret its reasoning process by investigating the intermediate variables. As the intermediate fuzzy sets may contain hundreds of entities, we consider two kinds of visualization to qualitatively analyze the precision and the recall of our model. The first one examines the entities with the top probabilities in each fuzzy set, and checks if they are an easy entity (i.e., those can be traversed on the training graph), a hard entity (i.e., those require reasoning) or a false positive one. For each fuzzy set, we visualize the top-3 easy entities and top-6 hard entities that have a minimum probability of 0.1. The second one draws a random ground truth assignment for each variable, such that the assignments form a valid grounding of the query and lead to a hard answer. We report the filtered ranking for each entity in the grounding.

Tab. 4 shows the visualization of GNN-QE on a 3p query from FB15k-237 test set. Among the top hard entities, GNN-QE correctly predicts most of the intermediate entities, which indicates our method has a good precision for this sample. For the random ground truth assignments, GNN-QE recalls the first two hops (2010 Winter Olympics & ice hockey) perfectly, but fails for the last hop. Such analysis would be beneficial to identify the steps where error occurs.

5 Ablation Study

To provide a more comprehensive understanding of GNN-QE, we conduct three ablation studies on FB15k-237.

Traversal Dropout Probability $p$. Fig. 4 shows the average MRR on EPFO queries of train and validation sets w.r.t. different probability $p$. The model can achieve a perfect training MRR of 1 when $p=0$, which suggests that the model is able to learn the behavior of a relation traversal model. However, a relation traversal model cannot solve queries on incomplete graphs, which is revealed by its low performance on the validation set. With a non-zero probability $p$, traversal dropout makes the training problem more difficult, and enforces the model to learn a reasoning model that predicts the dropped link from its surrounding graph structure. However, it is not optimal to learn a fully reasoning model with $p=1$, since it cannot perform relation traversal and some links in the validation queries can be perfectly solved by a relation traversal model.

Performance w.r.t. Number of Training Samples. Fig. 4 plots the MRR curves of different query types in GNN-QE and BetaE under different number of training samples. It is observed that the performance of GNN-QE is not only better than BetaE, but also less sensitive to the number of training samples. Even with 1% training samples (i.e., only 8,233 training queries for FB15k-237), GNN-QE achieves a comparative $avg_{p}$ and better $avg_{n}$ compared with BetaE trained with the full dataset. We conjecture the reason is that BetaE needs to learn a separate embedding for each entity, while our neural-symbolic method only learns relation embeddings (Eqn. 5) for relation projection, which requires less samples to converge.

GNN Parameterization. Tab. 5 shows the MRR results of GNN-QE w.r.t. different GNN parameterizations. We consider three parameterizations for the Message and Aggregate functions in Eqn. 3, namely RGCN (Schlichtkrull et al., 2018), CompGCN (Vashishth et al., 2019) and NBFNet (Zhu et al., 2021). It is observed that all three parameterizations outperform BetaE with significant improvement on $avg_{n}$, which suggests the advantages of fuzzy sets in modeling negation queries. Besides, GNN-QE benefits from stronger GNN models (NBFNet $>$ CompGCN $>$ RGCN). The performance of GNN-QE might be further improved with better GNN models.

Conclusion

In this paper, we present a novel neural-symbolic model, namely Graph Neural Network Query Executor (GNN-QE), for answering complex FOL queries on incomplete knowledge graphs. Our method decomposes complex queries into an expression of basic operations over fuzzy sets, and executes the expression with a learned GNN relation projection model and fuzzy logic operations. GNN-QE not only significantly outperforms previous state-of-the-art models on 3 datasets, but also provides interpretability for intermediate variables. Besides, GNN-QE can predict the number of answers without explicit supervision. Future works include combining GNN-QE with a parser to answer logical queries in the natural language form, and scaling up GNN-QE to large-scale knowledge graphs with millions of entities.

Acknowledgements

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-Bird Gift Fund and a NRC Collaborative R&D Project (AI4D-CORE-06). This project was also partially funded by IVADO Fundamental Research Project grant PRF-2019-3583139727. The computation resource of this project is supported by Calcul Québechttps://www.calculquebec.ca/ and Compute Canadahttps://www.computecanada.ca/.

We would like to thank Meng Qu for discussion on research ideas, and Pasquale Minervini for discussion on the CQD model. We also appreciate all anonymous reviewers for their constructive suggestions on this paper.

References

Appendix A Dataset Statistics

We use the complex query datasets generated by (Ren & Leskovec, 2020). There is a total number of 14 query types, as showed in Fig. 5. Statistics of all query types is summarized in Tab. 6.

Appendix B Hyperparameters

Tab. 7 lists the hyperparameter configurations of GNN-QE on different datasets.

Appendix C Batched Expression Execution

Alg. 1 shows the pseudo code for converting expression to postfix notation. The idea is to recursively parse the expression from outside to inside, and construct the postfix notation from inside to outside. We preprocess all query samples in training and evaluation with Alg. 1.

Alg. 2 illustrates the steps of batch execution over postfix expressions. For clarity, we describe the algorithm as one for loop over samples in the pseudo code, while samples that fall into the same case (Line 8, 10, 13, 16 & 19) are executed in parallel. Since the GNN in relation projection takes ($O(|{\mathcal{V}}|d^{2}+|{\mathcal{E}}|d)$ time (see App. C of (Zhu et al., 2021) for proofs), i.e., much more time than fuzzy logic operations ($O(|{\mathcal{V}}|)$ time), we synchronize different samples before neural relation projection (Line 20) to maximize the utilization of GPU. Fig. 6 shows the procedure of Alg. 2 over a batch of two queries.

The overall time complexity of our batched execution is $O(t(|{\mathcal{V}}|d^{2}+|{\mathcal{E}}|d))$, where $t$ is the maximal number of projections in a single query in the batch. Compared to existing implementation (Hamilton et al., 2018; Ren et al., 2019; Ren & Leskovec, 2020) that scales linearly w.r.t. the number of query types, batched expression execution scales independently w.r.t. the number of query types, and can be applied to arbitrary large number of query types without scalability issues.

Appendix D More Experiment Results

Here we provide additional experiment results.

Tab. 8 shows the H@1 results of different models for answering FOL queries. GNN-QE significantly outperforms existing methods in both EPFO queries and negation queries on all datasets.

Tab. 9 compares the Spearman’s rank correlation for answer set cardinality prediction on FB15k and NELL-995. GNN-QE achieves the best rank correlation on all query types.

Appendix E More Visualization Results

We provide more visualization for intermediate variables in Tab. 10. For each of the 14 query types, we randomly draw 3 query samples from the test set of FB15k-237. Therefore, we can observe both successful and failure cases of our method. For all expressions in the visualization, the operations follow the priority $\boldsymbol{\neg}>\boldsymbol{\land}>\boldsymbol{\lor}$.

Note the correctness of some predictions are contradictory to common sense. This is not a failure of our visualization, but is a result of the incomplete knowledge graph. For these contradictory tables, we add a footnote below to illustrate this problem.