Systematic Relational Reasoning With Epistemic Graph Neural Networks

## Abstract

Abstract Developing models that can learn to reason is a notoriously challenging problem. We focus on reasoning in relational domains, where the use of Graph Neural Networks (GNNs) seems like a natural choice. However, previous work on reasoning with GNNs has shown that such models tend to fail when presented with test examples that require longer inference chains than those seen during training. This suggests that GNNs lack the ability to generalize from training examples in a systematic way, which would fundamentally limit their reasoning abilities. A common solution is to instead rely on neuro-symbolic methods, which are capable of reasoning in a systematic way by design. Unfortunately, the scalability of such methods is often limited and they tend to rely on overly strong assumptions, e.g. that queries can be answered by inspecting a single relational path. In this paper, we revisit the idea of reasoning with GNNs, showing that systematic generalization is possible as long as the right inductive bias is provided. In particular, we argue that node embeddings should be treated as epistemic states and that GNN should be parameterised accordingly. We propose a simple GNN architecture which is based on this view and show that it is capable of achieving state-of-the-art results. We furthermore introduce a benchmark which requires models to aggregate evidence from multiple relational paths. We show that existing neuro-symbolic approaches fail on this benchmark, whereas our considered GNN model learns to reason accurately.

## 1 Introduction

Learning to reason remains a key challenge for neural networks. When standard neural network architectures are trained on reasoning problems, they often perform well on similar problems, but fail to generalize to problems with different characteristics than the ones that were seen during training, e.g. problems that were sampled from a different distribution [] or require longer inference chains []. This behaviour has been observed for different types of reasoning problems and different types of architectures, including Language Models [, ] and Graph Neural Networks []. A common solution is to rely on some kind of neuro-symbolic approach. For instance, Neural Theorem Provers (NTPs [, ]) simulate the backward chaining process of traditional logic programs, using a soft unification mechanism to make this process differentiable. Unfortunately, such approaches are highly inefficient. They also typically rely on strong assumptions about the required reasoning process. Irrespective of any specific implementation issues, there is a fundamental question that has largely remained unanswered: what is it about neuro-symbolic methods that makes them more successful for reasoning tasks? In this paper, we focus on the common problem of reasoning about binary relations. In such cases, the available knowledge can be represented as a labelled multi-graph (i.e. a knowledge graph) and the main reasoning task of interest is

Figure: Figure 1: Left: A (single) relational path reasoning problem over family relations. Right: A multipath reasoning problem over the RCC-8 relations where each path provides partial (disjunctive) information and the target label is obtained by combining information from paths $P_{1}$, $P_{2}$ and $P_{3}$.
Refer to caption: x1.png

to infer whether a given relationship holds or not. Graph Neural Networks (GNNs) intuitively seem well-suited for this task, but in practice they underperform neuro-symbolic methods on examples that require systematic generalization. Crucially, this is true despite the fact that GNNs are expressive enough to encode the required inference process.

We argue that the outperformance of neuro-symbolic methods can be explained by their focus on modelling *relational paths*, as an alternative to local message passing. To predict the relationship between two entities $h$ and $t$, conceptually, neuro-symbolic methods consider all the (exponentially many) paths between these entities, select the most informative path, and make a prediction based on this path (although, in practice, heuristics are used to avoid exhaustively exploring every path). The emphasis on paths provides a useful inductive bias,
while also avoiding the problems with over-smoothing that can arise with local message passing. Compared to GNNs, neuro-symbolic methods also have an advantage in how individual relational paths are modelled. Consider a relational path $h\xrightarrow{r_{1}}x_{1}\xrightarrow{r_{2}}x_{2}\xrightarrow{r_{3}}...
\xrightarrow{r_{k}}t$. When the specific choice of the intermediate entities $x_{1},...,x_{k-1}$ is not important, we will write such a path simply as $r_{1};r_{2};...;r_{k}$. To predict the relationship between $h$ and $t$ based on this path, we need to repeatedly choose two neighbouring relations $r_{i};r_{i+1}$ in the path and replace them by their composition. Crucially, the order in which the neighbouring relations are chosen may determine whether the model is capable of finding the answer: certain orderings may require the model to capture intermediate relationships which it has not seen during training. Neuro-symbolic methods can often avoid such issues by, in principle, considering all possible orderings. In contrast, GNN architectures such as NBFNet [] can only process relational paths sequentially.
Neuro-symbolic methods also have important drawbacks, however.
Most fundamentally, their focus on relational paths fundamentally limits the kinds of reasoning problems that can be tackled. Since these limits are not tested by the most commonly used benchmarks, as a first contribution, we introduce a benchmark based on the RCC-8 calculus for qualitative spatial reasoning []. The considered problems require models to combine evidence from multiple relational paths. Accordingly, we find that existing path-focused neuro-symbolic methods fail for this benchmark. Figure 1 contrasts an example from our benchmark with a relational path based example, as described previously.

As our main contribution, we revisit the question of whether GNNs can be used for systematic reasoning. The central idea is that reasoning involves the manipulation of epistemic states (i.e. states of knowledge). For instance, symbolic methods for reasoning about RCC-8 problems maintain sets of possible relationships between pairs of entities. Reasoning is then a matter of iteratively refining these sets. When designing a GNN model, we thus intuitively need to think of node embeddings as encoding sets of possible relationships. This view affects which pooling operations are meaningful (as analysed in []), how messages should be computed, and how node embeddings should be initialised. We find that when the GNN is designed with these considerations in mind, it can rival neuro-symbolic methods on reasoning problems that require selecting a single relational path, while dramatically outperforming such methods on the proposed RCC-8 benchmark. Surprisingly, this performance is achieved despite our model staying close to standard GNN architectures. Our code and datasets are available online(^1^11[github.com/erg0dic/gnn-sg](github.com/erg0dic/gnn-sg)).

## 2 Related work

There has been a large body of work on learning to reason with neural networks, ranging from traditional approaches based on carefully designed feedforward [] or recurrent [] models, to more recent approaches based on GNNs [, , ], pre-trained language models [, , ] or tailor-made architectures for relational reasoning [, ]. Despite their apparent success in a variety of reasoning tasks, however, neural networks usually do not learn to reason in a *systematic* way. For instance, [] showed that a fine-tuned BERT [] model can reason about (natural language descriptions of) propositional Horn rules with a remarkable accuracy. However, a follow-up analysis in [] revealed that this performance largely comes from learning spurious statistical artefacts of the considered (randomly generated) problem instances. When slightly changing how test instances are generated, the performance was found to drop to random chance in some cases. As another example, large language models have shown impressive reasoning abilities, but this is often due to the presence of similar problem instances in their training data. When exposed to problems that require some form of generalisation of the underlying reasoning principles, their performance also collapses [, ].

We focus on the problem of relational reasoning in this paper. Specifically, given a labelled multi-graph, where the nodes represent entities and edges specify relationships between these entities, we consider the task of inferring relationships that are not directly encoded. For instance, knowing that Bob is the father of Alice, and Alice is the mother of Eve, we may want to infer that Bob is the grandfather of Eve. Such problems have traditionally been studied in the field of Inductive Logic Programming (ILP) [] and are also close to the widely studied problem of link prediction in knowledge graphs []. Intuitively, GNNs should be well-suited for solving such reasoning tasks. However, [] found that GNNs trained to predict family relationships fail to generalise to problem instances that require longer inference chains than those that were seen during training. Similarly, [] also found the logical generalisation abilities of GNNs to be limited.
The apparent limitations of GNNs have inspired a range of neuro-symbolic methods for relational reasoning. For instance, Neural Theorem Provers (NTPs [, ]) take inspiration from the backward chaining mechanism from logic programming, but they represent relations using embeddings and rely on a soft unification mechanism. This allows them to learn differentiable approximations of rules from data, while retaining the ability to apply the learned rules in a systematic way. Essentially, these methods aim to find the most predictive relational path, and then compose the relations along that path. Because NTPs are computationally expensive, more recent methods aim to directly search for predictive relational paths, without attempting to simulate logic programming [, ]. Rather, these methods learn to reduce relational paths to a single relation by repeatedly composing adjacent relations in the path.

Our proposed model is strongly inspired by the idea that the structure of a neural network should be aligned with the reasoning algorithm it is supposed to learn. This intuitive idea was formally studied within the setting of PAC-learning in []. Similar to our proposed model, Edge Transformers [] also aim to align the model with the problem of relational reasoning. Their model essentially modifies the attention mechanism from the Transformer model [] to allow it to capture relational compositions.

## 3 Learning to reason in relational domains

We focus on the problem of reasoning about binary relations. We assume that a set $\mathcal{F}$ of facts is given, referring to a set of relations $\mathcal{R}$ and a set of entities $\mathcal{E}$. Each of these facts is an *atom* of the form $r(a,b)$, with $r\in\mathcal{R}$ and $a,b\in\mathcal{E}$. We furthermore assume that there exists a set of rules $\mathcal{K}$ which can be used to infer relationships between the entities in $\mathcal{E}$. We write $\mathcal{K}\cup\mathcal{F}\models r(a,b)$ to denote that $r(a,b)$ can be inferred from the facts in $\mathcal{F}$ and the rules in $\mathcal{K}$. The problem that we are interested in is to develop a neural network model $f_{\theta}$ which can predict for a given assertion $r(a,b)$ whether $\mathcal{K}\cup\mathcal{F}\models r(a,b)$ holds or not.
Note that the set of rules $\mathcal{K}$ is not given. We instead have access to a number of fact sets $\mathcal{F}_{i}$, together with examples of atoms $r(a,b)$ which can be inferred from these fact graphs and atoms which cannot. To be successful, $f_{\theta}$ must essentially learn the rules from $\mathcal{K}$, and the considered model must be capable of applying the learned rules in a systematic way to new problems.

### 3.1 Learning to reason about simple path rules

The most commonly studied setting concerns rules of the following form ($n\geq 3$):

$$ $\displaystyle r(X_{1},X_{n})\leftarrow r_{1}(X_{1},X_{2})\wedge\ldots\wedge r_ {n-1}(X_{n-1},X_{n})$ (1) $$

We will refer to such rules as *simple path rules*. Note that we used the convention from logic programming to write the head of the rule on the left-hand side, and we use uppercase symbols such as $X_{i}$ to denote variables. We can naturally associate a labelled multi-graph $G_{\mathcal{F}}$ with the given set of facts. The rule (1) expresses that when two entities $a$ and $b$ are connected by a relational path $r_{1};\ldots;r_{n-1}$ in this graph $G_{\mathcal{F}}$, then we can infer that $r(a,b)$ is true. Without loss of generality, we can restrict this setting to rules with two atoms in the body:

$$ $\displaystyle r(X_{1},X_{3})\leftarrow r_{1}(X_{1},X_{2})\wedge r_{2}(X_{2},X_ {3})$ (2) $$

Indeed, a rule with more than two atoms in the body can be straightforwardly simulated by introducing fresh relation symbols. The semantics of entailment are defined in the usual way (see the appendix for details). We can think of the process of showing $\mathcal{K}\cup\mathcal{F}\models r(a,b)$ in terms of operations on relational paths. We say that the path $r_{1};\ldots;r_{i-2};s;r_{i+1};\ldots;r_{k}$ can be derived from $r_{1};\ldots;r_{k}$ in one step if $\mathcal{K}$ contains a rule of the form $s(X,Z)\leftarrow r_{i-1}(X,Y)\wedge r_{i}(Y,Z)$.
We say that $r$ can be derived from $r_{1};\ldots;r_{k}$ if there exists a sequence of $k-1$ such steps that yields $r$. We have the following result.

###### Proposition 1 .

We have that $\mathcal{K}\cup\mathcal{F}\models r(a,b)$ holds iff there exists a relational path $r_{1};\ldots;r_{k}$ connecting $a$ and $b$ in the graph $G_{\mathcal{F}}$ such that $r$ can be derived from $r_{1};\ldots;r_{k}$.

Inferring $r(a,b)$ thus conceptually consists of two distinct steps: (i) selecting a relational path between $a$ and $b$ and (ii) showing that $r$ can be derived from it. Several of the neural network methods that have been proposed in recent years for relational reasoning directly implement these two steps, most notably R5 [] and NCRL []. Neural theorem provers [] implicitly also operate in a similar way, considering all possible paths and all possible derivations for these paths.
However, both steps are problematic for standard GNNs. First, by focusing on local message passing, rather than on selecting individual relational paths, the node representations that are learned by a GNN run the risk of becoming “overloaded”, as they intuitively aggregate information from all the paths that go through a given node. Moreover, even for graphs that consist of a single path, GNNs have a disadvantage: the use of local message passing intuitively means that relational paths have to be processed sequentially. For instance, given a path $h\xrightarrow{r_{1}}x_{1}\xrightarrow{r_{2}}x_{2}\xrightarrow{r_{3}}t$, after the first layer, the GNN might update the representation of $x_{1}$ to capture the fact $r_{1}(h,x_{1})$. After the second layer, the representation of $x_{2}$ might capture the relationship between $h$ and $x_{2}$. This intuitively corresponds to applying a derivation step which combines $r_{1};r_{2}$ into the representation of another relation $s$. Then, after the third layer, the representation of $x_{3}$ might capture the relationship between $h$ and $x_{3}$, etc.

The fact that relational paths can only be processed sequentially by GNNs is an important limitation, at least in theory. For instance, we may have a setting involving the following rules: $\mathcal{K}=s_{1}(X,Z)\leftarrow r_{1}(X,Y)\wedge r_{2}(Y,Z),s_{2}(X,Z)
\leftarrow r_{3}(X,Y)\wedge r_{4}(Y,Z),r(X,Z)\leftarrow s_{1}(X,Y)\wedge s_{2}
(Y,Z)\}$. Then we clearly have that $r$ can be derived from $r_{1};r_{2};r_{3};r_{4}$ but we may not be able to show this by processing the relations in this path from left-to-right. Indeed, after the first step, we end up with the path $s_{1};r_{3};r_{4}$ but the composition of $s_{1}$ and $r_{3}$ may not correspond to a well-defined relationship. In practice, the problem is exacerbated by the fact that some valid rules may not have been learned, as the situations in which they apply may not have been included in the training data. In fact, the model may not even have learned about the existence of some relations. For instance, when modelling family relationships, we may encounter the following relation chain:

$$ $\displaystyle a\xrightarrow{\textit{father}}x_{1}\xrightarrow{\textit{father}} x_{2}\xrightarrow{\textit{brother}}x_{3}\xrightarrow{\textit{daughter}}x_{4} \xrightarrow{\textit{brother}}x_{5}\xrightarrow{\textit{mother}}b$ $$

Suppose the model has never encountered the great-cousin relation during training. Then we cannot expect it to capture the relational path $\textit{father};\textit{father};\textit{brother};\textit{daughter}$. However, if it can first derive $a\xrightarrow{\textit{father}}x_{1}\xrightarrow{\textit{aunt}}x_{5}$ then the problem disappears (assuming it understands the great-aunt relation).

###### Proposition 1 .

### 3.2 Learning to reason about disjunctive rules

The rules that we have considered thus far uniquely determine the relationship between two entities $a$ and $c$, given knowledge about how $a$ relates to $b$ and $b$ relates to $c$. In many settings, however, such knowledge might not be sufficient for completely characterising the relationship between $a$ and $c$. Domain knowledge might then be expressed using disjunctive rules of the following form:

$$ $\displaystyle s_{1}(X,Z)\vee\ldots\vee s_{k}(X,Z)\leftarrow r_{1}(X,Y)\wedge r _{2}(Y,Z)$ (3) $$

In other words, if we know that $r_{1}(a,b)$ and $r_{2}(b,c)$ hold for some entities $a,b,c$, then all we can infer is that one of the relations $s_{1},\ldots,s_{k}$ must hold between $a$ and $c$. We then typically also have constraints of the form $\bot\leftarrow r_{1}(X,Y)\wedge r_{2}(X,Y)$, encoding that $r_{1}$ and $r_{2}$ are disjoint. Many of the calculi that have been developed for temporal and spatial reasoning fall under this setting [, ].

###### Example 1 .

The RCC-8 calculus describes qualitative spatial relations between two regions using eight primitive relations (see Section A.5 for details). The semantics of the RCC-8 relations are governed by disjunctive rules such as:

$$ $\displaystyle\mathsf{po}(X,Z)\vee\mathsf{tpp}(X,Z)\vee\mathsf{ntpp}(X,Z)$ $\displaystyle\leftarrow\mathsf{ec}(X,Y)\wedge\mathsf{ntpp}(Y,Z)$ (4) $\displaystyle\mathsf{po}(X,Z)\vee\mathsf{tppi}(X,Z)\vee\mathsf{ntppi}(X,Z)$ $\displaystyle\leftarrow\mathsf{tppi}(X,Y)\wedge\mathsf{po}(Y,Z)$ (5) $$

as well as constraints encoding that the RCC-8 relations are disjoint.
Let $\mathcal{K}$ contain these rules and constraints, and let $\mathcal{F}=\{\mathsf{ec}(a,b),\mathsf{ntpp}(b,c),\mathsf{tppi}(a,d),\mathsf{
po}(d,c)\}$. Then we have $\mathcal{K}\cup\mathcal{F}\models\mathsf{po}(a,c)$. Indeed, using (4) we can infer $\mathsf{po}(a,c)\vee\mathsf{tpp}(a,c)\vee\mathsf{ntpp}(a,c)$, while using (5) we can infer $\mathsf{po}(a,c)\vee\mathsf{tppi}(a,c)\vee\mathsf{ntppi}(a,c)$. Using the disjointness constraints, we finally infer $\mathsf{po}(a,c)$.

As the example illustrates, in the setting with disjunctive rules, we may need to aggregate evidence from multiple relational paths. This means that methods such as R5 and NCRL, which are directly based on the idea of making predictions from a single path, cannot be used. Neural theorem provers cannot handle disjunctive rules either. We thus need a new approach for dealing with this setting.

Proposition 1 provides a characterisation of entailment for simple rules, which clarifies how neural networks can be designed for deciding entailment. We may now wonder whether a similar characterisation is possible for entailment with disjunctive rules. Unfortunately, as deciding entailment with disjunctive rules is NP-complete, this is not possible with standard GNNs. While neuro-symbolic methods for this task could in principle be designed, such methods would be prohibitively slow. However, for RCC-8, and many other calculi for temporal and spatial reasoning, deciding entailment in polynomial time is possible using the so-called algebraic closure algorithm [].

The main idea is to keep track, for every pair of entities, of which relationships are possible between these entities. This knowledge of possible relationships is then propagated to infer constraints about relationships between other pairs of entities using the rules in $\mathcal{K}$ (details are provided in the appendix).

###### Example 1 .

## 4 A GNN for systematic reasoning

Figure: Figure 2: Overview of the proposed framework. Step 1: the forward and backwards model independently learn entity embeddings through message passing. Step 2: we compose the entity embeddings from the forward and backward model for entities on a path between the head and tail entity. Each of these compositions acts as a prediction of the target relation. Step 3: we aggregate the evidence provided by each of these predictions.
Refer to caption: extracted/5752826/figures/schematic3.png

Section 3 highlighted some challenges with designing GNNs that can learn to reason. We now present a simple GNN model that aims to overcome these challenges. Specifically, we want a model which (i) is more efficient than current neuro-symbolic methods while matching their performance on reasoning with simple path rules and (ii) is also able to reason about disjunctive rules.

We start from the principle that reasoning is fundamentally about manipulating epistemic states (i.e. states of knowledge) and the GNN should reflect this, i.e. there should be a clear correspondence between the node embeddings that are learned by the model and what we can infer about the relationships that may hold between the entities of interest. Inspired by NBFNet [], we use a network which learns the relationships between one designated head entity $h$ and all other entities. Let us write $\mathbf{e}^{(l)}\in\mathbb{R}^{n}$ for the embedding of entity $e$ in layer $l$ of the network. This embedding should intuitively reflect what we have derived about which relationships may possibly hold between $e$ and the designated entity $h$. We think of $\mathbf{e}^{(l)}$ as encoding a probability distribution over possible relationships. Accordingly, the embeddings are initialised as follows:

$$ $\displaystyle\mathbf{e}^{(0)}=\begin{cases}(1,0,\ldots,0)&\text{if $e=h$}\\ (\frac{1}{n},\ldots,\frac{1}{n})&\text{otherwise}\end{cases}$ $$

In other words, we associate the first coordinate with the identity relation. Since we know that $h$ is identical to itself, we define $\mathbf{h}^{(0)}$ as $(1,0,\ldots,0)$. For the other entities, we initially have no knowledge, so we initialise their embeddings as a uniform distribution. Note that the components of the embeddings correspond to abstract primitive relationships, rather than the relations from $\mathcal{R}$. We only require that the relations from $\mathcal{R}$ can be defined in terms of these primitive relationships. This distinction is important, because it allows the model to capture semantic dependencies between the relations from $\mathcal{R}$ (e.g. if we have both the *parent* and *father* relations in $\mathcal{R}$) and because we may need to be able to express relationships which are outside $\mathcal{R}$ when composing relations from $\mathcal{R}$. In other words, in general we should have $n\geq|\mathcal{R}|$. For $l\geq 1$, the embeddings are updated as follows:

$$ $\displaystyle\mathbf{e}^{(l)}=\psi(\{\mathbf{e}^{(l-1)}\}\cup\{\phi(\mathbf{f} ^{(l-1)},\mathbf{r})\,|\,r(f,e)\in\mathcal{F}\})$ $$

where the argument of the pooling operator $\psi$ is treated as a multi-set and $\mathbf{r}\in\mathbb{R}^{n}$ is a learned embedding of relation $r\in\mathcal{R}$. We interpret $\mathbf{r}=(r_{1},\ldots,r_{n})$ as a probability distribution over the primitive relations. Accordingly, we require that $r_{1},\ldots,r_{n}\geq 0$ and $\sum_{i}r_{i}=1$.

##### Message passing

The vector $\phi(\mathbf{f}^{(l-1)},\mathbf{r})$ should capture what are the possible relationships between $h$ and $e$, given the knowledge provided by $\mathbf{f}^{(l-1)}$ about the possible relationships between $h$ and $f$ and the fact $r(f,e)$. Since both $\mathbf{f}^{(l-1)}$ and $\mathbf{r}$ are modelled as probability distributions over primitive relations, $\phi(\mathbf{f}^{(l-1)},\mathbf{r})$ can be naturally defined in terms of compositions of these primitive relations. Specifically, let the vector $\mathbf{a}_{ij}\in\mathbb{R}^{n}$ represent the composition of primitive relations $i$ and $j$, which we treat as a probability distribution, i.e. we require the components of $\mathbf{a}_{ij}$ to be non-negative and to sum to 1. We define:

$$ $\displaystyle\phi((f_{1},\ldots,f_{n}),(r_{1},\ldots,r_{n}))=\sum_{i=1}^{n} \sum_{j=1}^{n}f_{i}r_{j}\mathbf{a}_{ij}$ (6) $$

The initialisation of $\mathbf{h}^{(0)}$ was based on the assumption that the first coordinate of the embeddings corresponds to the identity relation. Accordingly, we want to ensure that $\phi((1,0,\ldots,0),(r_{1},\ldots,r_{n}))=(r_{1},\ldots,r_{n})$. We thus fix $\mathbf{a}_{1j}=\text{one-hot}(j)$, where we write $\text{one-hot}(j)$ to denote the $n$-dimensional vector which is 1 in the $j\textsuperscript{th}$ coordinate and 0 elsewhere. Note that the composition of two primitive relations is thus modelled as a probability distribution over primitive relations. This provides an important inductive bias, as it encodes the assumption that the relationship between any two entities can be described by one of the $n$ considered primitive relations. Rule based methods, including NTP based approaches, also encode this assumption. However, the message passing operations that are used by standard GNNs typically do not. We hypothesise that the lack of this inductive bias partially explains why GNNs fail at systematic generalisation for reasoning in relational domains.

##### Pooling

The pooling operator $\psi$ has to be chosen in accordance with the view of embeddings as epistemic states: if $\mathbf{x_{1}},\ldots,\mathbf{x_{k}}$ capture sets of possible relationships then $\psi\{\mathbf{x_{1}},\ldots,\mathbf{x_{k}}\}$ should intuitively capture the intersection of these sets. This requirement was studied in []. The central result from that paper is that the minimum and component-wise (i.e. Hadamard) product are compatible with this intuitive requirement, but sum pooling is not. In our setting, the embeddings capture probability distributions rather than sets, and this means that $\psi$ also needs to include a normalisation step. We thus consider two possibilities. First, $\psi_{\odot}$ uses the component-wise product to combine the messages and then applies L1 normalisation to ensure the components of the resulting vector sum to 1. Similarly, $\phi_{\min}$ uses min-pooling followed by L1-normalisation.

##### Training

To train the model, we assume we have access to a set of examples of the form $(\mathcal{F}_{i},h_{i},t_{i},r_{i})$ where $h_{i},t_{i}$ are entities appearing in $\mathcal{F}_{i}$ and the atom $r_{i}(h_{i},t_{i})$ can be inferred from $\mathcal{F}$. Different examples will involve a different fact set $\mathcal{F}_{i}$ but the set of relations $\mathcal{R}$ appearing in these fact sets is fixed. The relations are assumed to be pairwise disjoint, meaning that for each positive example $(\mathcal{F}_{i},h_{i},t_{i},r_{i})$ we can consider negative examples of the form $(\mathcal{F}_{i},h_{i},t_{i},r^{\prime})$ with $r^{\prime}\in\mathcal{R}\setminus\{r_{i}\}$.
Let us write $\mathbf{t_{i}}$ for the final-layer embedding of entity $t_{i}$ in the graph $\mathcal{F}_{i}$ (with $h_{i}$ as the designated head entity).
We train the model using a margin loss, imposing that the cross-entropy between $\mathbf{t_{i}}$ and $\mathbf{r}$ is lower for positive examples than for negative examples.

A crucial hyperparameter is the dimensionality $n$ of the embeddings, as it determines the number of primitive relations. We clearly should have $n\geq|\mathcal{R}|$ so that all the relations of interest can be expressed, but choosing $n$ too high may lead to overfitting. To address this, we propose to jointly train several models, each with a relatively low number of dimensions. The idea is that these models can focus on different aspects of the relations, and can thus individually remain relatively simple. In the loss function, we then simply add up the cross-entropies from each of the $m$ models. Note that in this way, we do not require that any two relations can be distinguished in every model. We merely require that this is the case for at least one of the models. We will refer to $m$ as the number of *facets*.

##### Expressivity

The model is capable of simulating an approximation of the algebraic closure algorithm, where we only maintain sets of possible relations between the head entity and the other entities, rather than between any pair of entities. We formally establish this correspondence in the appendix.

##### Forward-backward model

As we noted in Section 3.1, the order in which the relations on a relational path $r_{1};...;r_{k}$ are composed sometimes matters. The model we have constructed thus far always composes such paths from left to right, i.e. we first compose $r_{1}$ and $r_{2}$, then compose the resulting relation with $r_{3}$, etc. To mitigate this limitation, we introduce a backward model. The backward model relies on a designated tail entity. In particular, the embeddings are initialised as follows:

$$ $\displaystyle\mathbf{e}^{(0)}=\begin{cases}(1,0,\ldots,0)&\text{if $e=t$}\\ (\frac{1}{n},\ldots,\frac{1}{n})&\text{otherwise}\end{cases}$ $$

These embeddings are updated as follows:

$$ $\displaystyle\mathbf{e}^{(l)}=\psi(\{\mathbf{e}^{(l-1)}\}\cup\{\phi(\mathbf{r} ,\mathbf{f}^{(l-1)})\,|\,r(e,f)\in\mathcal{F}\})$ (7) $$

Where $\psi$ and $\phi$ are defined as before. Note how the backward model does not introduce any new parameters. We rely on the idea that $\phi$ captures the composition of relation vectors. In the forward model, the embedding of an entity $e$ is interpreted as capturing the relationship between $h$ and $e$. In the backward model, the embedding of $e$ is instead interpreted as capturing the relationship between $e$ and $t$. This is why $\mathbf{r}$ appears as the second argument of $\phi$ in (6) and as the first argument in (7).

Let us write $\mathbf{e}^{\rightarrow}$ for the final-layer embedding of $e$ in the forward model and $\mathbf{e}^{\leftarrow}$ for the final-layer embedding in the backward model. In particular, $\mathbf{t}^{\rightarrow}$ and $\mathbf{t}^{\leftarrow}$ now both capture the relationship between $h$ and $t$. Moreover, for any entity $e$ on a path between $h$ and $t$, the vector $\phi(\mathbf{e}^{\rightarrow},\mathbf{e}^{\leftarrow})$ should also capture this relationship. We take advantage of the aggregation operator $\psi$ to take into account all these predictions. In particular, we construct the following vector:

$$ $\displaystyle\mathbf{\hat{r}}=\psi(\{\mathbf{t}^{\rightarrow},\mathbf{h}^{ \leftarrow}\}\cup\{\phi(\mathbf{e}^{\rightarrow},\mathbf{e}^{\leftarrow})\,|\, e\in\mathcal{E}_{h,t}\})$ (8) $$

where we write $\mathcal{E}_{h,t}$ for the entities that appear on some path from $h$ to $t$. When there are multiple paths between $h$ and $t$, we randomly select one of the shortest paths to define $\mathcal{E}_{h,t}$. The model is then trained as before, using $\mathbf{\hat{r}}$ as the predicted relation vector rather than $\mathbf{t}^{\rightarrow}$. Note that while this approach cannot exhaustively consider all possible compositions, it has the key advantage of remaining highly efficient, in contrast to most neuro-symbolic methods. A schematic of the forward-backward (FB) model that illustrates its learning dynamics is shown in Figure 2.

## 5 Experiments

We use the challenging problem of inductive relational reasoning to evaluate our proposed model against GNN, transformer and neuro-symbolic baselines. We refer to our full (forward-backward) model as FB. We consider two variants of this model, which differ in the choice of the pooling operator: component-wise multiplication (FB-mul) and min-pooling (FB-min). The considered benchmarks involve relation classification queries of the form $(h,?,t)$, asking which relation holds between a given head entity $h$ and tail entity $t$. We focus in particular on systematic generalisation, to assess whether models can deal with large distributional shifts from the training set, which is paramount in many real-world settings []. We consider two existing benchmarks designed to test systematic generalisation for relational reasoning: CLUTRR [] and GraphLog []. We also introduce a new benchmark based on RCC-8 relations, which goes further than the existing benchmarks on two fronts, as illustrated in Example 1: (i) the need to go beyond Horn rules to capture relational compositions and (ii) requiring models to aggregate information multiple relational paths. For CLUTRR and RCC-8, to test for systematic generalisation, models are trained on small graphs and subsequently evaluated on larger graphs. In particular, for CLUTRR, the length $k$ of the considered relational paths is varied, while for RCC-8 we vary both the number of relational paths $b$ and their length $k$. In the case of GraphLog, the size of training and test graphs is similar, but models still need to apply learned rules in novel ways to perform well.

**Table 1: Results (accuracy) on CLUTRR after training on problems with $k\in\{2,3,4\}$ and then evaluating on problems with $k\in\{5,\ldots,10\}$. Results marked with ^∗ were taken from [], those with ^† from [] and those with ^2 from []. The best performance for each $k$ is highlighted in bold.**
|  | 5 Hops | 6 Hops | 7 Hops | 8 Hops | 9 Hops | 10 Hops |
| --- | --- | --- | --- | --- | --- | --- |
| FB-mul (ours) | 0.99$\pm$.01 | 0.99$\pm$.01 | 0.99$\pm$.02 | 0.99$\pm$.03 | 0.96$\pm$.03 | 0.98$\pm$.02 |
| FB-min (ours) | 0.99$\pm$.01 | 0.98$\pm$.02 | 0.98$\pm$.03 | 0.97$\pm$.06 | 0.95$\pm$.04 | 0.93$\pm$.07 |
| NCRL^2 | 1.0$\pm$.01 | 0.99$\pm$.01 | 0.98$\pm$.02 | 0.98$\pm$.03 | 0.98$\pm$.03 | 0.97$\pm$.02 |
| R5^† | 0.99$\pm$.02 | 0.99$\pm$.04 | 0.99$\pm$.03 | 1.0$\pm$.02 | 0.99$\pm$.02 | 0.98$\pm$.03 |
| $\mbox{CTP}_{L}^{*}$ | 0.99$\pm$.02 | 0.98$\pm$.04 | 0.97$\pm$.04 | 0.98$\pm$.03 | 0.97$\pm$.04 | 0.95$\pm$.04 |
| $\mbox{CTP}_{A}^{*}$ | 0.99$\pm$.04 | 0.99$\pm$.03 | 0.97$\pm$.03 | 0.95$\pm$.06 | 0.93$\pm$.07 | 0.91$\pm$.05 |
| $\mbox{CTP}_{M}^{*}$ | 0.98$\pm$.04 | 0.97$\pm$.06 | 0.95$\pm$.06 | 0.94$\pm$.08 | 0.93$\pm$.08 | 0.90$\pm$.09 |
| GNTP^∗ | 0.68$\pm$.28 | 0.63$\pm$.34 | 0.62$\pm$.31 | 0.59$\pm$.32 | 0.57$\pm$.34 | 0.52$\pm$.32 |
| ET | 0.99$\pm$.01 | 0.98$\pm$.02 | 0.99$\pm$.02 | 0.96$\pm$.04 | 0.92$\pm$.07 | 0.92$\pm$.07 |
| GAT^∗ | 0.99$\pm$.00 | 0.85$\pm$.04 | 0.80$\pm$.03 | 0.71$\pm$.03 | 0.70$\pm$.03 | 0.68$\pm$.02 |
| GCN^∗ | 0.94$\pm$.03 | 0.79$\pm$.02 | 0.61$\pm$.03 | 0.53$\pm$.04 | 0.53$\pm$.04 | 0.41$\pm$.04 |
| NBFNet | 0.83$\pm$.11 | 0.68$\pm$.09 | 0.58$\pm$.10 | 0.53$\pm$.07 | 0.50$\pm$.11 | 0.53$\pm$.08 |
| R-GCN | 0.97$\pm$.03 | 0.82$\pm$.11 | 0.60$\pm$.13 | 0.52$\pm$.11 | 0.50$\pm$.09 | 0.45$\pm$.09 |
| RNN^∗ | 0.93$\pm$.06 | 0.87$\pm$.07 | 0.79$\pm$.11 | 0.73$\pm$.12 | 0.65$\pm$.16 | 0.64$\pm$.16 |
| LSTM^∗ | 0.98$\pm$.03 | 0.95$\pm$.04 | 0.89$\pm$.10 | 0.84$\pm$.07 | 0.77$\pm$.11 | 0.78$\pm$.11 |
| GRU^∗ | 0.95$\pm$.04 | 0.94$\pm$.03 | 0.87$\pm$.08 | 0.81$\pm$.13 | 0.74$\pm$.15 | 0.75$\pm$.15 |

**Table 2: RCC-8 benchmark results (accuracy). Timeout refers to the model taking longer than 30 minutes for inference. Models are trained on graphs with $b\in\{1,2,3\}$ paths of length $k\in\{2,3,4\}$. For each $k$ and $b$, the best performance across all the models is highlighted in bold.**
|  |  | 2 Hops | 3 Hops | 4 Hops | 5 Hops | 6 Hops | 7 Hops | 8 Hops | 9 Hops |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| FB-min (ours) | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.99$\pm$0.01 | 0.99$\pm$0.01 | 0.97$\pm$0.02 | 0.97$\pm$0.02 | 0.95$\pm$0.03 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.97$\pm$0.02 | 0.97$\pm$0.02 | 0.94$\pm$0.04 | 0.94$\pm$0.04 | 0.91$\pm$0.04 |  |
| FB-mul (ours) | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.99$\pm$0.01 | 0.99$\pm$0.0 | 0.98$\pm$0.01 | 0.98$\pm$0.01 | 0.97$\pm$0.01 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.88$\pm$0.04 | 0.87$\pm$0.04 | 0.80$\pm$0.05 | 0.79$\pm$0.04 | 0.75$\pm$0.05 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.78$\pm$0.07 | 0.76$\pm$0.06 | 0.70$\pm$0.06 | 0.69$\pm$0.06 | 0.65$\pm$0.05 |  |
| ET | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.99$\pm$0.0 | 1.0$\pm$0.0 | 0.99$\pm$0.01 | 0.99$\pm$0.01 | 0.98$\pm$0.02 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.97$\pm$0.01 | 0.98$\pm$0.01 | 0.96$\pm$0.03 | 0.96$\pm$0.03 | 0.91$\pm$0.05 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.95$\pm$0.03 | 0.96$\pm$0.03 | 0.93$\pm$0.03 | 0.91$\pm$0.04 | 0.81$\pm$0.09 |  |
| NCRL | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.65$\pm$0.01 | 0.67$\pm$0.01 | 0.61$\pm$0.01 | 0.64$\pm$0.0 | 0.59$\pm$0.02 |
| $b=2$ | 0.68$\pm$0.0 | 0.68$\pm$0.01 | 0.69$\pm$0.0 | 0.43$\pm$0.0 | 0.45$\pm$0.01 | 0.40$\pm$0.0 | 0.41$\pm$0.0 | 0.38$\pm$0.02 |  |
| $b=3$ | 0.57$\pm$0.01 | 0.58$\pm$0.0 | 0.58$\pm$0.0 | 0.36$\pm$0.0 | 0.39$\pm$0.0 | 0.34$\pm$0.02 | 0.35$\pm$0.01 | 0.32$\pm$0.02 |  |
| R5 | $b=1$ | 0.56$\pm$0.01 | 1.0$\pm$0.01 | 1.0$\pm$0.01 | 0.41$\pm$0.01 | 0.39$\pm$0.01 | 0.38$\pm$0.01 | timeout | timeout |
| $b=2$ | 0.52$\pm$0.01 | 0.47$\pm$0.01 | 0.43$\pm$0.01 | 0.41$\pm$0.01 | 0.40$\pm$0.01 | 0.38$\pm$0.01 | timeout | timeout |  |
| $b=3$ | 0.50$\pm$0.01 | 0.46$\pm$0.01 | 0.44$\pm$0.01 | 0.39$\pm$0.01 | 0.37$\pm$0.01 | 0.36$\pm$0.01 | timeout | timeout |  |
| NBFNet | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.88$\pm$0.12 | 0.75$\pm$0.04 | 0.61$\pm$0.07 | 0.57$\pm$0.09 | 0.52$\pm$0.07 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.83$\pm$0.09 | 0.66$\pm$0.05 | 0.51$\pm$0.07 | 0.45$\pm$0.04 | 0.41$\pm$0.03 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.79$\pm$0.06 | 0.59$\pm$0.08 | 0.44$\pm$0.08 | 0.38$\pm$0.06 | 0.34$\pm$0.04 |  |
| R-GCN | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.91$\pm$0.15 | 0.60$\pm$0.21 | 0.50$\pm$0.05 | 0.46$\pm$0.06 | 0.42$\pm$0.05 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.87$\pm$0.16 | 0.52$\pm$0.10 | 0.47$\pm$0.08 | 0.43$\pm$0.07 | 0.36$\pm$0.03 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.82$\pm$0.16 | 0.49$\pm$0.12 | 0.42$\pm$0.05 | 0.38$\pm$0.05 | 0.33$\pm$0.04 |  |

**Table 3: Results on GraphLog (accuracy). For each world, we report the number of distinct relation sequences between head and tail (ND) and the Average resolution length (ARL). Results marked with ^∗ were taken from [] and those with ^† from []. The best performance across all the models is highlighted in bold.**
| World ID | ND | ARL | E-GAT^∗ | R-GCN^∗ | CTP^∗ | R5^∗ | NCRL^† | FB-mul |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| World 6 | 249 | 5.06 | 0.536 | 0.498 | 0.533$\pm$0.03 | 0.687$\pm$0.05 | 0.702$\pm$0.02 | 0.563 $\pm$ 0.016 |
| World 7 | 288 | 4.47 | 0.613 | 0.537 | 0.513$\pm$0.03 | 0.749$\pm$0.04 | - | 0.521$\pm$0.04 |
| World 8 | 404 | 5.43 | 0.643 | 0.569 | 0.545$\pm$0.02 | 0.671$\pm$0.03 | 0.687$\pm$0.02 | 0.547$\pm$0.032 |
| World 11 | 194 | 4.29 | 0.552 | 0.456 | 0.553$\pm$0.01 | 0.803$\pm$0.01 | - | 0.698 $\pm$ 0.019 |
| World 32 | 287 | 4.66 | 0.700 | 0.621 | 0.581$\pm$0.04 | 0.841$\pm$0.03 | - | 0.914$\pm$0.026 |

**Table 4: Ablation study on the best FB model for CLUTRR and RCC-8. For both benchmarks, we show the average accuracy across all configurations (i.e. 4-10 hops for CLUTRR, and $k\in\{2,...,9\}$ and $b\in\{1,2,3\}$ for RCC-8), as well as the accuracy for the hardest setting (i.e. 10 hops for CLUTRR, and $k=9$ and $b=3$ for RCC-8).**
|  | CLUTRR | RCC-8 |  |  |
| --- | --- | --- | --- | --- |
|  | Avg | $k=10$ | Avg | $b=3,k=9$ |
| FB Model | 0.99 | 0.99 | 0.96 | 0.80 |
| With facets=1 | 0.94 | 0.85 | 0.92 | 0.68 |
| Unconstrained embeddings | 0.36 | 0.30 | 0.38 | 0.21 |
| MLP+distmul composition | 0.29 | 0.31 | 0.13 | 0.13 |
| Forward model only | 0.94 | 0.82 | 0.84 | 0.51 |

##### Main results

Results for CLUTRR, RCC-8 and GraphLog are shown in Tables 1, 2 and 3, respectively. We report the average accuracy and $2\sigma$ errors across 10 seeds for CLUTRR and 3 seeds for RCC-8 and GraphLog. For CLUTRR, both variants of our model outperform all GNN and RNN methods, as well as edge transformers (ET). The FB-mul model is also on par with the SoTA neuro-symbolic methods NCRL [] and R5 []. For RCC-8, as expected, the neuro-symbolic methods are largely ineffective, being substantially outperformed by our method as well as by ET. This highlights the fact that neuro-symbolic methods are not capable of modelling disjunctive rules. Our model with min-pooling achieves the best results. Edge transformers also perform well in general, but they underperform on the most challenging configurations (e.g. $k=9$ and $b=3$).
Comparing the mul and min variants of our model, we find that mul performs better on single-path problems (e.g. CLUTRR and GraphLog), while min leads to better results when paths need to be aggregated (e.g. RCC-8). For GraphLog, we only consider worlds that are characterized as ‘hard’ by the authors in [], with an Average Resolution Length (ARL) $>4$. GraphLog is more challenging and noisier than the previous two datasets and is amenable to path-based reasoning. Accordingly, we find that FB-mul is outperformed by R5 and NCRL in most cases, although FB-mul clearly improves the SoTA for World 32. Moreover, FB-mul outperforms CTPs and the GNN baselines.

##### Ablations

We confirm the importance of key architectural components of our model through an ablation study on CLUTRR and RCC-8, namely: a) the joint training of multiple lower-dimensional models focusing on different facets, b) modelling embeddings as epistemic states by requiring $\mathbf{r}$ and $\mathbf{a}_{ij}$ to be probability distributions, c) the use of a bilinear composition function $\phi$ in Eq (6), and d) the forward and backward nature of our model encapsulated by Eq. (8). We ablate over all in the following way ceteris paribus: a) by setting the number of facets $m$ to 1, b) removing the requirement that embedding components are non-negative and sum to 1, c) replacing the composition function by distmul [] after applying a 4-layer MLP with ReLU activation to both inputs of $\phi$. and d) considering only the forward embeddings $\mathbf{e}^{\rightarrow}$ in Eq. (8). The results in Table 4 confirm the importance of all these components, with the use of embeddings as epistemic states and the bilinear form of $\phi$ being particularly important. For c) the MLP is to ensure the model is not underparameterised. We see a similar performance degradation when distmul is used without the MLP (not shown). Further analysis is presented in the appendix.

## 6 Conclusions

We have challenged the view that Graph Neural Networks are not capable of systematic generalisation in relational reasoning problems, by introducing a principled GNN architecture for this setting. To impose an appropriate inductive bias, node embeddings in our framework are treated as epistemic states, intuitively capturing sets of possible relationships. These epistemic states are iteratively refined by the GNN. In this way, the design of the GNN is closely aligned with the algebraic closure algorithm, which is used for relational reasoning by symbolic methods, and a formal connection with this algorithm has been established. Furthermore, to ensure that the composition function which is implemented by the network is sufficiently expressive, while at the same time avoiding overfitting, we jointly train multiple lower-dimensional models, which intuitively each capture different facets of the considered relationships. Finally, by considering both a forward and a backward model, our method can mitigate the problems that may arise when relational paths can only be processed sequentially. While the resulting architecture stays close to standard GNNs, we have shown that our model can rival neuro-symbolic methods on standard benchmarks such as CLUTRR and GraphLog, while clearly outperforming existing GNN and transformer based methods. Moreover, we have highlighted that existing neuro-symbolic methods also have an important weakness, which arises from an implicit assumption that relations can be predicted from a single relational path. To explore this issue, we have introduced a new benchmark based on the RCC-8 calculus, finding that neuro-symbolic methods indeed fail on this benchmark, while our model still performs well in this more challenging setting.

Limitations: Our proposed framework is limited by its statistical nature, where the parameters of the model will inevitably be biased by training data artefacts. While we have shown that our model can perform well in settings where existing neuro-symbolic methods fail (i.e. on the RCC-8 benchmark), the much stronger inductive bias imposed by the latter puts them at an advantage in severely data-limited settings. This can be seen in some of the GraphLog results. For a variant of CLUTRR where the model is only trained on problems of size $k\in\{2,3\}$, our model is also outperformed by the best neuro-symbolic methods (shown in Section A.8 of the appendix).

##### Acknowledgments

This work was supported by EPSRC grant EP/W003309/1.

## Appendix A Supplemental material

### A.1 Semantics of entailment

For simple path rules of the form (2), the semantics of entailment can be defined in terms of the immediate consequence operator.
Let $\mathcal{R}_{\mathcal{F}}$ be the grounding of $\mathcal{R}$ w.r.t. $\mathcal{F}$, i.e. for each rule of the form $r(X,Z)\leftarrow r_{1}(X,Y)\wedge r_{2}(Y,Z)$ in $\mathcal{R}$, $\mathcal{R}_{\mathcal{F}}$ contains all the possible rules of the form $r(a,c)\leftarrow r_{1}(a,b)\wedge r_{2}(b,c)$ that can be obtained by substituting the variables for entities that appear in $\mathcal{F}$. Since we assume that both $\mathcal{F}$ and $\mathcal{R}$ are finite, we have that $\mathcal{R}_{\mathcal{F}}$ is finite as well. Let $\mathcal{F}_{0}=\mathcal{F}$ and for $i\geq 1$ define:

$$ $\displaystyle\mathcal{F}_{i}\,{=}\,\mathcal{F}_{i-1}\cup\{r(a,c)\,|\,\exists b \in\mathcal{E}\,.\,r_{1}(a,b),r_{2}(b,c)\in\mathcal{F}_{i-1}\text{ and }(r(a,c )\leftarrow r_{1}(a,b)\wedge r_{2}(b,c))\in\mathcal{R}_{\mathcal{F}}\}$ $$

Since there are finitely many atoms $r(a,c)$ that can be constructed using the entities and relations appearing in $\mathcal{R}_{\mathcal{F}}$, this process reaches a fixpoint after a finite number of steps, i.e. for some $\ell\in\mathbb{N}$ we have $\mathcal{F}_{\ell}=\mathcal{F}_{\ell+1}$. Let us write $\mathcal{F}^{*}$ for this fixpoint. Then we define $\mathcal{F}\cup\mathcal{R}\models r(a,b)$ iff $r(a,b)\in\mathcal{F}^{*}$.

###### Example 2 .

The canonical example for this setting concerns reasoning about family relationships. In this case, $\mathcal{K}$ contains rules such as:

$$ $\displaystyle\textit{grandfather}(X,Z)\leftarrow\textit{father}(X,Y)\wedge \textit{mother}(Y,Z)$ $$

If $\mathcal{F}=\{\textit{father}(\textit{bob},\textit{alice}),\textit{mother}(
\textit{alice},\textit{eve})\}$ then $\mathcal{R}_{\mathcal{F}}$ contains rules such as:

$$ $\displaystyle\textit{grandfather}(\textit{bob},\textit{eve})$ $\displaystyle\leftarrow\textit{father}(\textit{bob},\textit{alice})\wedge \textit{mother}(\textit{alice},\textit{eve})$ $\displaystyle\textit{grandfather}(\textit{bob},\textit{alice})$ $\displaystyle\leftarrow\textit{father}(\textit{bob},\textit{alice})\wedge \textit{mother}(\textit{alice},\textit{alice})$ $\displaystyle\textit{grandfather}(\textit{bob},\textit{bob})$ $\displaystyle\leftarrow\textit{father}(\textit{bob},\textit{alice})\wedge \textit{mother}(\textit{alice},\textit{bob})$ $\displaystyle\textit{grandfather}(\textit{bob},\textit{eve})$ $\displaystyle\leftarrow\textit{father}(\textit{bob},\textit{eve})\wedge\textit {mother}(\textit{eve},\textit{eve})$ $\displaystyle\dots$ $$

We have $\mathcal{F}_{1}=\{\textit{father}(\textit{bob},\textit{alice}),\textit{mother}
(\textit{alice},\textit{eve}),\textit{grandfather}(\textit{bob},\textit{eve})\}$, with $\mathcal{F}_{1}=\mathcal{F}_{2}=\mathcal{F}^{*}$. We thus find: $\mathcal{K}\cup\mathcal{F}\models\textit{grandfather}(\textit{bob},\textit{eve})$.

For the more general setting with disjunctive rules and constraints, we can define the semantics of entailment in terms of Herbrand models. Given a set of disjunctive rules and constraints $\mathcal{R}$ and a set of facts $\mathcal{F}$, the Herbrand universe $\mathcal{U}_{\mathcal{R},\mathcal{F}}$ is the set of all atoms of the form $r(a,b)$ which can be constructed from a relation $r$ and entities $a,b$ appearing in $\mathcal{R}\cup\mathcal{F}$. A Herbrand interpretation $\omega$ is a subset of $\mathcal{U}_{\mathcal{R},\mathcal{F}}$. The interpretation $\omega$ satisfies a ground disjunctive rule of the form $s_{1}(a,c)\vee\ldots\vee s_{k}(a,c)\leftarrow r_{1}(a,b)\wedge r_{2}(b,c)$ iff either $\{r_{1}(a,b),r_{2}(b,c)\}\not\subseteq\omega$ or $\omega\cap\{s_{1}(a,c),\ldots,s_{k}(a,c)\}\neq\emptyset$. The interpretation $\omega$ satisfies a ground constraint of the form $\bot\leftarrow r_{1}(a,b)\wedge r_{2}(a,b)$ iff $\{r_{1}(a,b),r_{2}(a,b)\}\not\subseteq\omega$. We say that $\omega$ is a model of the grounding $\mathcal{R}_{\mathcal{F}}$ iff $\omega$ satisfies all the ground rules and constraints in $\mathcal{R}_{\mathcal{F}}$. Finally, we have that $\mathcal{R}\cup\mathcal{F}\models r(a,b)$ iff $r(a,b)$ is contained in every model of $\mathcal{R}_{\mathcal{F}}$.

###### Example 2 .

### A.2 Proof of Proposition 1

The correctness of Proposition 1 immediately follows from Lemmas 1 and 2 below.

###### Lemma 1 .

Suppose there exists a relational path $r_{1};...;r_{k}$ connecting $a$ and $b$ in $G_{\mathcal{F}}$ such that $r$ can be derived from $r_{1};...;r_{k}$. Then it holds that $\mathcal{K}\cup\mathcal{F}\models r(a,b)$.

###### Proof.

Let $r_{1};...;r_{k}$ be a relational path connecting $a$ and $b$, such that $r$ can be derived from $r_{1};...;r_{k}$. Then $\mathcal{F}$ contains facts of the form $r_{1}(a,x_{1}),r_{2}(x_{1},x_{2}),...,r_{k}(x_{k-1},b)$. Let us now consider the derivation from $r_{1};...;r_{k}$ to $r$. After the first derivation step, we have a relational path of the form $r_{1};...;r_{i-2};s;r_{i+1};...;r_{k}$. In this case, $\mathcal{K}$ contains a rule of the form $s(X,Z)\leftarrow r_{i-1}(X,Y)\wedge r_{i}(Y,Z)$. This means that
$\mathcal{K}\cup\mathcal{F}\models s(x_{i-2},x_{i})$.
We thus have a relational path of the form $r_{1};...;r_{i-2};s;r_{i+1};...;r_{k}$, where each relation is associated with an atom that is entailed by $\mathcal{K}\cup\mathcal{F}$. Each derivation step introduces such an atom (while reducing the length of the relational path by 1). After $k-1$ steps, we thus obtain the atom $r(a,b)$, from which it follows that $\mathcal{K}\cup\mathcal{F}\models r(a,b)$.
∎

###### Lemma 2 .

Suppose that $\mathcal{K}\cup\mathcal{F}\models r(a,b)$.
Then it holds that there exists a relational path $r_{1};...;r_{k}$ connecting $a$ and $b$ in $G_{\mathcal{F}}$ such that $r$ can be derived from $r_{1};...;r_{k}$.

###### Proof.

Recall from Section A.1 that $\mathcal{K}\cup\mathcal{F}\models r(a,b)$ iff $r(a,b)\in\mathcal{F}^{*}$. It thus suffices to show by induction that $r(a,b)\in\mathcal{F}_{i}$ implies that there exists a relational path $r_{1};...;r_{k}$ connecting $a$ and $b$ in $G_{\mathcal{F}}$ such that $r$ can be derived from $r_{1};...;r_{k}$.
First, if $r(a,b)\in\mathcal{F}_{0}$ then by definition there is a relational path $r$ connecting $a$ and $b$ in $G_{\mathcal{F}}$, meaning that the result is trivially satisfied. Now suppose that the result has already been shown for $\mathcal{F}_{i-1}$. Let $r(a,b)\in\mathcal{F}_{i}\setminus\mathcal{F}_{i-1}$. Then there must exist facts
$r_{1}(a,x)$ and $r_{2}(x,b)$ in $\mathcal{F}_{i-1}$ such that $\mathcal{K}$ contains a rule of the form $r(X,Z)\leftarrow r_{1}(X,Y)\wedge r_{2}(Y,Z)$. By induction, we have that there is a relational path $s_{1};...;s_{\ell_{1}}$ connecting $a$ and $x$ such that $r_{1}$ can be derived from this path, and a relational path $t_{1};...;t_{\ell_{2}}$ connecting $x$ and $b$ from which $r_{2}$ can be derived. We then have that $s_{1};...s_{\ell_{1}};t_{1};...;t_{\ell_{2}}$ is a path connecting $a$ and $b$. Furthermore, we have that $r_{1};r_{2}$ can be derived from this path, and thus also $r$.
∎

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

### A.3 Reasoning about disjunctive rules using algebraic closure

We consider knowledge bases with three types of rules. First, we have disjunctive rules that encode relational compositions:

$$ $\displaystyle s_{1}(X,Z)\vee\ldots\vee s_{k}(X,Z)\leftarrow r_{1}(X,Y)\wedge r _{2}(Y,Z)$ (9) $$

Second, we have constraints of the following form:

$$ $\displaystyle\bot\leftarrow r_{1}(X,Y)\wedge r_{2}(X,Y)$ (10) $$

meaning that $r_{1}$ and $r_{2}$ are disjoint. Finally, we consider knowledge about inverse relations, expressed using rules of the following form:

$$ $\displaystyle r_{2}(Y,X)\leftarrow r_{1}(X,Y)$ (11) $$

We now describe the algebraic closure algorithm, which can be used to decide entailment for calculi such as RCC-8. We also describe an approximation of this algorithm, which we call *directional algebraic closure*. This approximation closely corresponds to how GNN models can reason in this setting, as will be made clear below.

##### Full algebraic closure

Let us make the following assumptions:

- •
The knowledge base $\mathcal{K}$ contains rules of the form (9), encoding the composition of relations $r_{1}$ and $r_{2}$.
- •
We also have that $\mathcal{K}$ contains the rule $\bigvee_{r\in\mathcal{R}}r(X,Y)\leftarrow\top$, expressing that the set of relations is exhaustive.
- •
For all distinct relations $r_{1},r_{2}\in\mathcal{R}$, $r_{1}\neq r_{2}$, $\mathcal{K}$ contains a constraint of the form (10), expressing that the relations are pairwise disjoint.
- •
For every $r\in\mathcal{R}$ there is some relation $\hat{r}\in\mathcal{R}$, such that $\mathcal{K}$ contains the rules $r(Y,X)\leftarrow\hat{r}(X,Y)$ and $\hat{r}(Y,X)\leftarrow r(X,Y)$, expressing that $\hat{r}$ is the inverse of $r$.
- •
$\mathcal{K}$ contains no other rules.

Let us write $r_{1}\circ r_{2}$ for the set of relations that appears in the head of the rule defining the composition of $r_{1}$ and $r_{2}$ in $\mathcal{K}$. If no such rule exists in $\mathcal{K}$ for $r_{1}$ and $r_{2}$ then we define $r_{1}\circ r_{2}=\mathcal{R}$. Let $\mathcal{E}$ be the set of entities that appear in $\mathcal{F}$. Let us assume that $\mathcal{F}$ is consistent with $\mathcal{K}$, i.e. $\mathcal{K}\cup\mathcal{F}\not\models\bot$.

The main idea of the algebraic closure algorithm is that we iteratively refine our knowledge of what relationships are possible between different entities. Specifically, for all entities $e,f\in\mathcal{E}$, we define the initial set of possible relationships as follows:

$$ $\displaystyle X^{(0)}_{ef}=\begin{cases}\{r\}&\text{if $r(e,f)\in\mathcal{F}$} \\ \{\hat{r}\}&\text{if $r(f,e)\in\mathcal{F}$}\\ \mathcal{R}&\text{otherwise}\\ \end{cases}$ $$

where $\hat{r}$ is the unique relation that is asserted to be the inverse of $r$ in $\mathcal{K}$. Note that because we assumed $\mathcal{F}$ to be consistent, if $r(e,f)\in\mathcal{F}$ and $r^{\prime}(f,e)\in\mathcal{F}$ it must be the case that $r^{\prime}=\hat{r}$.
We now iteratively refine the sets $X^{(i)}_{ef}$. Specifically, for $i\geq 1$, we define:

$$ $\displaystyle X^{(i)}_{ef}=X^{(i-1)}_{ef}\cap\bigcap\{X^{(i-1)}_{eg}\diamond X ^{(i-1)}_{gf}\,|\,g\in\mathcal{E}\}$ $$

where, for $X,Y\subseteq\mathcal{R}$, we define:

$$ $\displaystyle X\diamond Y$ $\displaystyle=\bigcup\{r\circ s\,|\,r\in X,s\in Y\}$ $$

Since each of the sets $X^{(i)}_{ef}$ only contains finitely many elements, and there are only finitely many such sets, this process must clearly converge after a finite number of steps. Let us write $X_{ef}$ of the sets of relations that are obtained upon convergence. For many spatial and temporal calculi, we have that $r\in X_{ef}$ iff $\mathcal{K}\cup\mathcal{F}\cup\{r(e,f)\}\not\models\bot$. In other words, $X_{ef}$ encodes everything that can be inferred about the relationship between $e$ and $f$. In particular, we have have $\mathcal{K}\cup\mathcal{F}\models r(e,f)$ iff $X_{ef}=\{r\}$. Note that this equivalence only holds for particular calculi: in general, $\mathcal{K}\cup\mathcal{F}\models r(e,f)$ does not imply $X_{ef}=\{r\}$.

##### Directional algebraic closure

The algebraic closure algorithm relies on sets $X_{ef}^{(i)}$ for every pair of entities, which limits its scalability (although more efficient special cases have been studied []). Any simulation of this algorithm using a neural network would thus be unlikely to scale to large graphs. For this reason, we study an approximation, which we refer to as *directional algebraic closure*. This approximation essentially aims to infer the possible relationships between a fixed head entity $h$ and all the other entities from the graph. The relationship between $h$ and a given entity $e$ is determined based on the paths in $\mathcal{G}$ connecting $h$ to $e$. For this approximation, we furthermore omit rules about inverse relations. Other than this, we make the same assumptions about $\mathcal{K}$ as before. We now learn sets $X_{e}^{(0)}$ which capture the possible relationships between $h$ and $e$. These sets are initialised as follows:

$$ $\displaystyle X^{(0)}_{e}=\begin{cases}\{r\}&\text{if $r(h,e)\in\mathcal{F}$} \\ \mathcal{R}&\text{otherwise}\end{cases}$ $$

We define for $i\geq 1$:

$$ $\displaystyle X^{(i)}_{e}=X^{(i-1)}_{e}\cap\bigcap\{X^{(i-1)}_{f}\diamond s\,| \,s(f,e)\in\mathcal{F}\}$ $$

with

$$ $\displaystyle X^{(i-1)}_{f}\diamond s$ $\displaystyle=\bigcup\{r\circ s\,|\,r\in X^{(i-1)}_{f}\}$ $$

where $r_{1}\circ r_{2}$ is defined as before. We write $X_{e}$ to denote the sets $X_{e}^{(i)}$ that are obtained upon convergence.
Clearly, after a finite number of iterations $i$ we have $X^{(i)}_{e}=X^{(i+1)}_{e}$. Note how the directional closure algorithm essentially limits the full algebraic closure algorithm to compositions of the form $X_{he}\diamond X_{ef}$, for entities $e$ and $f$ such that there is a fact of the form $r(e,f)$ in $\mathcal{F}$. As the following result shows, the algorithm is still sound, although it may infer less knowledge than the full algebraic closure algorithm.

For a rule $\rho$ of the form (9), we write $\textit{head}(\rho)$ to denote the set $\{s_{1},...,s_{k}\}$ of relations appearing in the head of the rule and $\textit{body}(\rho)$ to denote the pair $(r_{1},r_{2})$ of relations appearing in the body.

###### Proposition 2 .

Assume that $\mathcal{K}$ consists of (i) rules of the form (9), (ii) for each pair of distinct relations $r_{1},r_{2}$ the disjointness constraint (10), and (iii) the rule $\bigvee_{r\in\mathcal{R}}r(X,Y)\leftarrow\top$. Let $e\in\mathcal{E}$. It holds that $\mathcal{K}\cup\mathcal{F}\models\bigvee_{r\in X_{e}}r(h,e)$.

###### Proof.

We show this result by induction. First note that we have $\mathcal{K}\cup\mathcal{F}\models\bigvee_{r\in X_{e}^{(0)}}r(h,e)$. Indeed, either $X_{e}^{(0)}=\{r(h,e)\}$ with $r(h,e)\in\mathcal{F}$, in which case the claim clearly holds, or $X_{e}^{(0)}=\mathcal{R}$, in which case the claim holds because $\mathcal{K}$ contains the rule $\bigvee_{r\in\mathcal{R}}r(X,Y)\leftarrow\top$. Now suppose we have already established $\mathcal{K}\cup\mathcal{F}\models\bigvee_{r\in X_{e}^{(i-1)}}r(h,e)$ for every $e\in\mathcal{E}$. To show that $\mathcal{K}\cup\mathcal{F}\models\bigvee_{r\in X_{e}^{(i)}}r(h,e)$, it is sufficient to show that $\mathcal{K}\cup\mathcal{F}\models\neg r(h,e)$ for every $r\in X_{e}^{(i-1)}\setminus X_{e}^{(i)}$. Let $r\in X_{e}^{(i-1)}\setminus X_{e}^{(i)}$. Then there must exist some $s(f,e)\in\mathcal{F}$ such that $r\notin X_{f}^{(i-1)}\diamond s$. In that case, for every $t\in X_{f}^{(i-1)}$ we have $r\notin t\circ s$. This means that for every $t\in X_{f}^{(i-1)}$ there exists some rule $\rho_{t}$ in $\mathcal{K}$ such that $\textit{body}(\rho_{t})=(t,s)$ and $r\notin\textit{heads}(\rho_{t})$.
We have for every $t\in X_{f}^{(i-1)}$ that $\mathcal{K}\cup\mathcal{F}\models t(h,f)\rightarrow\vee_{u\in\textit{heads}(
\rho_{t})}u(h,e)$. Moreover, because of our assumption that $\mathcal{K}$ encodes that all relations are pairwise disjoint, for $u\neq r$ we have $\mathcal{K}\models u(h,e)\rightarrow\neg r(h,e)$. We thus find for every $t\in X_{f}^{(i-1)}$ that $\mathcal{K}\cup\mathcal{F}\models t(h,f)\rightarrow\neg r(h,e)$. By induction we also have $\mathcal{K}\cup\mathcal{F}\models\bigvee_{t\in X_{f}^{(i-1)}}t(h,e)$. Together we find
$\mathcal{K}\cup\mathcal{F}\models\neg r(h,e)$.
∎

###### Proposition 2 .

###### Proof.

### A.4 Expressivity

We now show that the base GNN model, corresponding to (15), is capable of simulating the directional algebraic closure algorithm. Specifically, we show the following result, which associates the embeddings $\mathbf{e}^{(i)}$ from the GNN with the sets $X_{e}^{(i)}$. We show the following result for the min-pooling operator $\psi_{\min}$ defined as follows:

$$ $\displaystyle\psi_{\min}(\mathbf{x_{1}},\dots,\mathbf{x_{k}})=\frac{\min( \mathbf{x_{1}},\dots,\mathbf{x_{k}})}{\|\min(\mathbf{x_{1}},\dots,\mathbf{x_{k }})\|_{1}}$ (12) $$

###### Proposition 3 .

Let $\mathcal{F}$ be a set of facts and $\mathcal{K}$ a knowledge base satisfying the conditions of Proposition 2. Furthermore assume that $\mathcal{K}\cup\mathcal{F}$ is consistent, i.e. $\mathcal{K}\cup\mathcal{F}\not\models\bot$. Let $X_{e}^{(i)}$ be sets of relations that are constructed using the directional algebraic closure algorithm, and let $e^{i}_{j}$ denote the $j\textsuperscript{th}$ coordinate of $\mathbf{e}^{(i)}$. Let the pooling operation be chosen as $\psi=\psi_{\min}$.
There exists a parameterisation of the vectors $\mathbf{r}_{i}$ and $\mathbf{a}_{ij}$ such that:

$$ $\displaystyle X_{e}^{(i)}\supseteq\{r_{j}\,|\,e^{i+1}_{j}>0,2\leq j\leq n\} \supseteq X_{e}^{(i+1)}$ (13) $$

###### Proof.

Let $r_{1},...,r_{n}$ be an enumeration of the relations in $\mathcal{R}\cup\{\textit{id}\}$, where we fix $r_{1}=\textit{id}$. Let $\mathbf{a}_{ij}=(a^{ij}_{1},...,a^{ij}_{n})$ be defined for as follows ($i\in\{1,...,n\}$):

$$ $\displaystyle a^{ij}_{l}=\begin{cases}\frac{1}{|r_{i}\circ r_{j}|}&\text{if $r _{l}\in r_{i}\circ r_{j}$}\\ 0&\text{otherwise}\end{cases}$ $$

where we define $\textit{id}\circ r_{j}=r_{j}$ for every $j\in\{1,...,n\}$.
Note that $\mathbf{a}_{ij}$ indeed satisfies the requirements of the model: the coordinates of $\mathbf{a}_{ij}$ are non-negative and sum to 1, while $\mathbf{a}_{1j}=\textit{one-hot}(j)$ follows from the fact that $\textit{id}\circ r_{j}=r_{j}$. Furthermore, we define $\mathbf{r}_{j}=\text{one-hot}(j)$.

We show the result by induction. For $i=0$, if $\mathcal{F}$ contains a fact of the form $r_{l}(h,e)$, we have $X_{e}^{(0)}=\{r_{l}\}$. We show that $\mathbf{e}^{(1)}$ is non-zero in the $l\textsuperscript{th}$ coordinate and zero everywhere else. We have:

$$ $\displaystyle\phi(\mathbf{h}^{(0)},\mathbf{r}_{l})=\sum_{i}\sum_{l}h_{i}^{0}r^ {l}_{j}\mathbf{a}_{ij}=\sum_{j}r^{l}_{j}\mathbf{a}_{1j}=\mathbf{r}_{l}=\text{ one-hot}(l)$ $$

This already shows that $\mathbf{e}^{(1)}$ is zero in all coordinates apart from the $l\textsuperscript{th}$. Now let $f\neq h$ and $r_{p}$ be such that $r_{p}(f,e)\in\mathcal{F}$. We have

$$ $\displaystyle\phi(\mathbf{f}^{(0)},\mathbf{r}_{p})=\sum_{i}\sum_{j}f_{i}^{0}r^ {p}_{j}\mathbf{a}_{ij}=\frac{1}{n}\sum_{i}\sum_{j}r^{p}_{j}\mathbf{a}_{ij}= \frac{1}{n}\sum_{i}\mathbf{a}_{ip}$ $$

We need to show that the $l\textsuperscript{th}$ coordinate of the latter vector is non-zero.
Since $\mathcal{K}\cup\mathcal{F}$ is consistent and $\mathcal{F}$ contains both $r_{l}(h,e)$ and $r_{p}(f,e)$, it has to be the case there there is some $q\in\{1,...,n\}$ such that $r_{l}\in r_{q}\circ r_{p}$. There thus exists some $q\in\{1,...,n\}$ such that the $l\textsuperscript{th}$ coordinate of $\mathbf{a}_{qp}$ is non-zero. Since all vectors of the $\mathbf{a}_{ip}$ vectors have non-negative coordinates, it follows that the $l\textsuperscript{th}$ coordinate of $\frac{1}{n}\sum_{i}\mathbf{a}_{ip}$ is non-zero. We have thus shown that $\{r_{j}\,|\,e^{0}_{j}>0,2\leq j\leq n\}=\{r_{l}\}=X^{(0)}_{e}\supseteq X^{(1)}
_{e}$.

If $\mathcal{F}$ does not contain any facts of the form $r_{l}(h,e)$, then $X_{e}^{(0)}=\mathcal{R}$. We need to show for each $l\in\{2,...,n\}$ that either $e^{1}_{l}$ is non-zero or $r_{l}\notin X^{1}_{e}$. We have that $e^{1}_{l}$ is non-zero if the $l\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(0)},\mathbf{r}_{p})$ is non-zero for every fact of the form $r_{p}(f,e)$ in $\mathcal{F}$, where $f\neq h$. Consider such a fact $r_{p}(f,e)$ and assume the $l\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(0)},\mathbf{r}_{p})$ is actually 0. Since $f\neq h$ we have $\mathbf{f}^{(0)}=(\frac{1}{n},...,\frac{1}{n})$. The $l\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(0)},\mathbf{r}_{p})=\frac{1}{n}\sum_{i}\mathbf{a}_{ip}$ can thus only be 0 if the $l\textsuperscript{th}$ component of $\mathbf{a}_{ip}$ is 0 for every $i$. This implies that $r_{l}\notin r_{i}\circ r_{p}$ for any $i\in\{1,...,n\}$, from which it follows that $r_{l}\notin X_{e}^{(1)}$.

Now suppose that $X_{e}^{(i-1)}\supseteq\{r_{j}\,|\,e^{i}_{j}>0,2\leq j\leq n\}\supseteq X_{e}^{
(i)}$ holds for every entity $e$. We show that (13) must then hold as well. We first show $X_{e}^{(i)}\supseteq\{r_{j}\,|\,e^{i+1}_{j}>0,2\leq j\leq n\}$. To this end, we need to show that for each $r_{j}\in X_{e}^{(i-1)}\setminus X_{e}^{(i)}$ it holds that $e^{i+1}_{j}=0$. If $r_{j}\in X_{e}^{(i-1)}\setminus X_{e}^{(i)}$ it means that there is some $r_{p}(f,e)\in\mathcal{F}$ such that $r_{j}\notin X_{f}^{(i-1)}\diamond r_{p}$. This is the case if $r_{j}\notin r_{q}\diamond r_{p}$ for every $r_{q}\in X_{f}^{(i-1)}$. This, in turn, means that the $j\textsuperscript{th}$ component of $\mathbf{a}_{qp}$ is 0 for every $q$ such that $r_{q}\in X_{f}^{(i-1)}$. Furthermore, by the induction hypothesis, we know that $r_{q}\notin X_{f}^{(i-1)}$ means $f^{i}_{q}=0$. In other words, for each $q$ we have that either $f_{q}^{i}=0$ or that the $j\textsuperscript{th}$ component of $\mathbf{a}_{qp}$ is 0. It follows that the $j\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(i)},\mathbf{r}_{p})$ is 0, and thus also that $e_{j}^{i+1}=0$.

We now show $\{r_{j}\,|\,e^{i+1}_{j}>0,2\leq j\leq n\}\supseteq X_{e}^{(i+1)}$. Let $j$ be such that $e^{i}_{j}>e^{i+1}_{j}=0$. We need to show that $r_{j}\notin X_{e}^{(i+1)}$. If $e^{i}_{j}>e^{i+1}_{j}=0$ there needs to be some $r_{p}(f,e)\in\mathcal{F}$ such that the $j\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(i)},\mathbf{r}_{p})$ is 0. We have

$$ $\displaystyle\phi(\mathbf{f}^{(i)},\mathbf{r}_{p})=\sum_{l}\sum_{j}f_{l}^{i}r^ {p}_{j}\mathbf{a}_{lj}=\sum_{l}f_{l}^{i}\mathbf{a}_{lp}$ $$

So when the $j\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(i)},\mathbf{r}_{p})$ is 0 we must have for each $l$ that either $f_{l}^{i}=0$ or that $a^{j}_{lp}=0$. By the induction hypothesis, $f_{l}^{i}=0$ implies $r_{l}\notin X^{(i)}_{f}$. Furthermore $a^{j}_{lp}=0$ means that $r_{j}\notin r_{l}\circ r_{p}$. When the $j\textsuperscript{th}$ component of $\phi(\mathbf{f}^{(i)},\mathbf{r}_{p})$ is 0, we thus have that either $r_{l}\notin X^{(i)}_{f}$ or $r_{j}\notin r_{l}\circ r_{p}$ for each $l$, which implies $r_{j}\notin X^{(i+1)}_{e}$.
∎

When $\psi_{\odot}$ is used instead of $\psi_{\min}$, a similar result holds. If $\psi_{\odot}$ simply uses the component-wise product, then the same argument as in the proof of Proposition 3 still holds. In practice, however, for numerical stability, we evaluate $\psi_{\odot}$ as follows:

$$ $\displaystyle\psi_{\odot}(\mathbf{x_{1}},\ldots,\mathbf{x_{k}})=\frac{(\mathbf {x_{1}}\odot\ldots\odot\mathbf{x_{k}})+\mathbf{z}}{\|(\mathbf{x_{1}}\odot \ldots\odot\mathbf{x_{k}})+\mathbf{z}\|_{1}}$ (14) $$

where we write $\odot$ for the Hadamard product and $\mathbf{z}=(\varepsilon,\ldots,\varepsilon)$ for some small constant $\varepsilon>0$. As long as $\varepsilon$ is sufficiently small, this does not affect the ability of the GNN model to simulate the directional closure algorithm. In particular, whenever $e_{j}^{i}=0$ in the GNN with $\psi_{\min}$ we can ensure that this coordinate is arbitrarily small in the GNN with $\Psi_{\odot}$ (choosing the $\mathbf{a}_{ij}$ and $\mathbf{r}_{j}$ vectors as in the proof of Proposition 3), by selecting $\varepsilon$ small enough. In particular, there exists some $\delta>0$ such that

$$ $\displaystyle X_{e}^{(i)}\supseteq\{r_{j}\,|\,e^{i+1}_{j}>\delta,2\leq j\leq n \}\supseteq X_{e}^{(i+1)}$ $$

###### Proposition 3 .

###### Proof.

### A.5 RCC-8 Dataset

**Table 5: RCC-8 composition table [] (excluding $\mathsf{eq}$).**
|  | $\mathsf{dc}$ | $\mathsf{ec}$ | $\mathsf{po}$ | $\mathsf{tpp}$ | $\mathsf{ntpp}$ | $\mathsf{tppi}$ | $\mathsf{ntppi}$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\mathsf{dc}$ | $\mathcal{R}_{8}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{dc}$ | $\mathsf{dc}$ |
| $\mathsf{ec}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{tppi}$, $\mathsf{eq}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$ | $\mathsf{dc}$ |
| $\mathsf{po}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathcal{R}_{8}$ | $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ |
| $\mathsf{tpp}$ | $\mathsf{dc}$ | $\mathsf{dc}$, $\mathsf{ec}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{tppi}$, $\mathsf{eq}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ |
| $\mathsf{ntpp}$ | $\mathsf{dc}$ | $\mathsf{dc}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{ntpp}$ | $\mathsf{ntpp}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathcal{R}_{8}$ |
| $\mathsf{tppi}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{po}$, $\mathsf{eq}$, $\mathsf{tpp}$, $\mathsf{tppi}$ | $\mathsf{po}$, $\mathsf{tpp}$, $\mathsf{ntpp}$ | $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{ntppi}$ |
| $\mathsf{ntppi}$ | $\mathsf{dc}$, $\mathsf{ec}$, $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{ntppi}$ | $\mathsf{po}$, $\mathsf{tppi}$, $\mathsf{tpp}$, $\mathsf{ntpp}$, $\mathsf{ntppi}$, $\mathsf{eq}$ | $\mathsf{ntppi}$ | $\mathsf{ntppi}$ |

RCC-8 [] uses eight primitive relations to describe qualitative spatial relationships between regions: $\mathsf{ntpp}(a,b)$ means that $a$ is a proper part of the interior of $b$, $\mathsf{tpp}(a,b)$ means that $a$ is a proper part of $b$ and shares a boundary point with $b$, $\mathsf{po}(a,b)$ means that $a$ and $b$ are overlapping (but neither is included in the other), $\mathsf{dc}(a,b)$ means that $a$ and $b$ are disjoint, $\mathsf{ec}(a,b)$ means that $a$ and $b$ are adjacent (i.e. sharing a boundary point but no interior points), $\mathsf{eq}(a,b)$ means that $a$ and $b$ are equal, and $\mathsf{ntppi}$ and $\mathsf{tppi}$ are the inverses of $\mathsf{ntpp}$ and $\mathsf{tpp}$.
The RCC-8 semantics is governed by the so-called composition table, which describes the composition mapping between two relations. This is shown in Table 5 where the trivial composition with the identity element $\mathsf{eq}$ being itself is dropped. Each entry in this table corresponds to a rule of the form (4), specifying the possible relations that may hold between two regions $a$ and $c$, when we know the RCC-8 relation that holds between $a$ and some region $b$ as well as the relation that holds between $b$ and $c$. For instance, the composition of $\mathsf{ec}$ and $\mathsf{tppi}$ is given by the set $\{\mathsf{dc},\mathsf{ec}\}$, which means that from $\{\mathsf{ec}(a,b),\mathsf{tppi}(b,c)\}$ we can infer $\mathsf{dc}(a,c)\vee\mathsf{ec}(a,c)$. In the table, we write $\mathcal{R}_{8}$ to denote that any RCC-8 relation is possible.

Our proposed RCC-8 benchmark is similar to CLUTRR and GraphLog in its focus on assessing inductive relational reasoning via relation classification queries of the form $(h,?,t)$, where we need to predict which relation holds between a given head entity $h$ and tail entity $t$. The available knowledge is provided as a set of facts $\mathcal{F}$, which we can again think of as a graph. The inductive part refers to the fact that the model is trained and tested on distinct graphs. The main difficulty comes from the fact that only small graphs are available for training, while some of the test graphs are considerably larger.

However, different from existing benchmarks, our RCC-8 dataset requires reasoning about disjunctive rules, which is particularly challenging for many methods. The kind of knowledge that has to be learned is thus more expressive than the Horn rules which are considered in most existing benchmarks. As illustrated in Example 1, this means that models need to process different relational paths and aggregate the resulting information. We vary the difficulty of problem instances based on the number $b$ of such paths and their length $k$. Figure 3 provides an example where there are $b=6$ paths of length $k=3$. Each path is partially informative, in the sense that it allows to exclude certain candidate relations, but is not sufficiently informative to pinpoint the exact relation. The model thus needs to rely on the different paths to be able to exclude all but one of the eight possible relations.

In summary, within the context of benchmarks for systematic generalisation, our RCC-8 benchmark is novel on two fronts compared to existing benchmarks such as CLUTRR [] and GraphLog []:

- •
Going beyond Horn rules for relation composition: The composition of some RCC-8 relations is a disjunction of several RCC-8 relations.
- •
Multi-path information aggregation: Models need to reason about multiple relational paths (for the case where $b>1$) to infer the correct answer.

Figure: Figure 3: An example from the RCC-8 benchmark with $b=6$ paths from the source node 0 to the target node 17. Each path has a length of $k=3$ where $k$ is the number of hops or edges from the node 0 to node 17. The graph has to be collapsed into the single relation $\mathsf{ntpp}(0,17)$ using information from all the paths.
Refer to caption: x2.png

#### A.5.1 Dataset Generation

We now explain how the dataset was created. All sampling in the discussion below is uniform random. Each problem instance has to be constructed such that after aggregating the information provided by all the relational paths, we need to be able to infer a singleton label. In other words, problem instances need to be consistent (i.e. the information provided by different paths cannot be conflicting) and together all the paths need to be informative enough to uniquely determine which relation holds between the head and tail entity. This makes brute-force sampling of problem instances prohibitive. Instead, to create a problem instance involving $b$ paths of length $k$, we first sample a base graph, which has $b$ shorter paths, with a length in $\{2,3,4\}$. This is done by pre-computing relational compositions for a large number of paths and then selecting $b$ paths whose intersection is a singleton. Then we repeatedly increase the length of the paths by selecting an edge and replacing it by a short path whose composition is equal to the corresponding relation.

Finally, to add further diversity to the graph topology, for each of the $b$ paths, we allow 1 edge from the base graph to be replaced by a subgraph (rather than a path), where this subgraph is generated using the same procedure. Note that the final path count $b$ then includes the paths from this subgraph as well.

The process is described in more detail below:

- 1.
Sample short paths: Randomly sample $n=100\,000$ paths of length $k\in\{2,3,4\}$ and compute their composition. Note that this sampling is done with replacement to avoid uniqueness upper bounds for small graphs.
- 2.
Generate base graphs: Generate the desired number of $b$-path base graphs, by selecting paths that were generated in step 1. Each individual path typically composes to a set of relations, but the graphs are constructed such that the intersection of these sets, across all $b$ paths, produces a singleton target label.
- 3.
Recursive edge expansion: Randomly pick an edge from a path that does not yet have the required length $k$. Select a path from step 1 which composes to a singleton, corresponding to the relation that is associated with the chosen edge. Replace the edge with this path.
- 4.
Recursive subgraph expansion: Rather than replacing an edge with a path, we can also replace it with a subgraph. As candidate subgraphs, we use the base graphs from step 2 with at most $\lfloor\frac{b}{2}\rfloor$ paths.
- 5.
Keep repeating steps 2 and 3 until we have the desired number paths $b$ with the desired length of $k$, with the restriction that step 3 is applied at most once to each path from the initial base graph.

Some example graphs generated via this procedure for the RCC-8 dataset are displayed in Figure 4. For higher $k$, there is greater diversity in the graph topology and complexity of the graph.

Figure: (a) $k=2,b=1$
Refer to caption: x3.png

#### A.5.2 Ensuring path consistency within the dataset

We ensure that all relational paths in a problem instance in the generated dataset do not informationally conflict with each other by using the DPC+ algorithm []. It efficiently computes directional path consistency, i.e. $X_{ij}\subseteq X_{ik}\diamond X_{kj}\forall i,j\leq k$, for qualitative constraint networks that we can transform our graph instances to. Directional path consistency is sufficient as a test for global path consistency for networks with singleton edge labels [].

### A.6 Allen’s interval algebra dataset

Table: Table 6: Allen’s interval algebra composition table [] excluding the trivial composition with $=$.

Figure: (a) $k=2,b=1$
Refer to caption: x11.png

To complement the experiments in the main paper, we also introduce a dataset based on
Allen’s interval algebra []. Similar to RCC-8, the interval algebra uses 13 primitive relations to describe qualitative temporal relationships. The interval algebra captures all possible relationships between two time intervals. Similar to the RCC-8 relations, these are binary relations defined as follows: $<$$(a,b)$ means that the time interval $a$ precedes the time interval $b$; $\mathsf{d}(a,b)$ means that $a$ occurs during $b$; $\mathsf{o}(a,b)$ means that $a$ overlaps with $b$; $\mathsf{m}(a,b)$ means that $a$ meets $b$ ($a$ ends exactly before $b$ starts); $\mathsf{s}(a,b)$ means that $a$ starts $b$ ($a$ and $b$ share a starting time); $\mathsf{f}(a,b)$ means that $a$ finishes $b$ ($a$ and $b$ share a finishing time); $=$$(a,b)$ means that $a$ equals $b$ (the starting and finishing times for both are the same implying the intervals are the same); and finally $>,\mathsf{di},\mathsf{oi},\mathsf{mi},\mathsf{si},\mathsf{fi}$ are the inverses of the respective operations defined previously.
The composition table for all the primitive interval relations is shown in Table 6 with the exception of the trivial composition of primitive elements with the identity element $=$.

To create a dataset for reasoning about interval algebra problems, we follow the same process as for the RCC-8 dataset. Some example graphs generated via this procedure for the are displayed in Figure 5.

### A.7 Additional experimental details

We now present further details of the experimental set-up, including details of the loss function that was used for training the model, the considered benchmarks and baselines, and training details such as hyperparameter optimisation.

#### A.7.1 Loss function

Let us write $\mathbf{t_{i}}=(t_{i,1},\ldots,t_{i,n})$ for the final-layer embedding of entity $t_{i}$ in the graph $\mathcal{F}_{i}$, and let $\mathbf{r}=(r_{1},\ldots,r_{n})$ denote the embedding of relation $r$. Let us write:

$$ $\displaystyle\text{CE}(\mathbf{t_{i}},\mathbf{r})=-\sum_{j=1}^{n}r_{j}\log t_{ i,j}$ $$

For each training example $i$, we write $\mathbf{t_{i}}$ for the corresponding tail embedding and we let $r_{i}\in\mathcal{R}$ denote the correct label.
Then clearly, we want $\text{CE}(\mathbf{t_{i}},\mathbf{r_{i}})$ to be low, while for each negative example $r^{\prime}\in\mathcal{R}\setminus\{r_{i}\}$ we want $\text{CE}(\mathbf{t_{i}},\mathbf{r^{\prime}})$ to be high. In the base model, we implement this with a margin loss, where for each $i$ we let $r_{i}^{\prime}\in\mathcal{R}\setminus\{r_{i}\}$ be a corresponding negative example:

$$ $\displaystyle\mathcal{L}=\sum_{i}\max(0,\text{CE}(\mathbf{t_{i}},\mathbf{r_{i} })-\text{CE}(\mathbf{t_{i}},\mathbf{r_{i}^{\prime}})+\Delta)$ (15) $$

where the margin $\Delta>0$ is a hyperparameter.
In general, we use $m$ different models, each intuitively capturing a different aspect of the relations. Let $\text{CE}_{j}(t_{i},r)$ denote the cross-entropy associated with the embeddings of the $j\textsuperscript{th}$ model. Then the overall loss function becomes:

$$ $\displaystyle\mathcal{L}=\sum_{i}\max\Big{(}0,\Big{(}\sum_{j=1}^{m}\text{CE}_{ j}(\mathbf{t_{i}},\mathbf{r_{i}})-\text{CE}_{j}(\mathbf{t_{i}},\mathbf{r^{ \prime}_{i}})\Big{)}+\Delta\Big{)}$ (16) $$

#### A.7.2 Benchmarks

**Table 7: Data statistics for different versions of the CLUTRR dataset, with varying training regimes and different numbers training and testing graphs.**
| Training regime | Unique Hash | No. of relations | # Train | # Test | Test regime |
| --- | --- | --- | --- | --- | --- |
| $k\in\{2,3\}$ | data_089907f8 | 22 | 10,094 | 900 | $k\in\{4,\dots,10\}$ |
| $k\in\{2,3\}$ | data_9b2173cf | 22 | 35,394 | 39825 | $k\in\{4,\dots,10\}$ |
| $k\in\{2,3,4\}$ | data_db9b8f04 | 22 | 15,083 | 823 | $k\in\{5,\dots,10\}$ |

**Table 8: Data statistics of the RCC-8 dataset**
| Training regime | No. of relations | # Train | # Test | Test regime |
| --- | --- | --- | --- | --- |
| $b\in\{1,2,3\},k\in\{2,3\}$ | 8 | 57,600 | 153,600 | $b\in\{1,2,3\},k\in\{2,\dots,9\}$ |

**Table 9: Data statistics for the ‘hard’ GraphLog worlds, showing for each world the number of classes (NC), the number of distinct resolution sequences (ND), the average resolution length (ARL), the average number of nodes (AN), the average number of edges (AE), and the number of training and testing graphs.**
| World ID | NC | ND | ARL | AN | AE | # Train | #Test |
| --- | --- | --- | --- | --- | --- | --- | --- |
| World 6 | 16 | 249 | 5.06 | 16.3 | 20.2 | 5000 | 1000 |
| World 7 | 17 | 288 | 4.47 | 13.2 | 16.3 | 5000 | 1000 |
| World 8 | 15 | 404 | 5.43 | 16.0 | 19.1 | 5000 | 1000 |
| World 11 | 17 | 194 | 4.29 | 11.5 | 13.0 | 5000 | 1000 |
| World 32 | 16 | 287 | 4.66 | 16.3 | 20.9 | 5000 | 1000 |

CLUTRR(^2^22[https://github.com/facebookresearch/clutrr](https://github.com/facebookresearch/clutrr)) [] is a dataset which involves reasoning about family relationships. The original version of the dataset involved narratives describing the fact graph in natural language. It was, among others, aimed at testing the ability of language models such as BERT [] to solve such reasoning tasks. However, the original paper also considered a number of baselines which were given access to the fact graph itself, especially GNNs and sequence classification models. A crucial finding was that such models fail to learn to reason in a systematic way: models trained on short inference chains perform poorly when tested on examples involving longer inference chains. This has inspired a line of work which has introduced a number of neuro-symbolic methods for addressing this issue. The CLUTRR dataset was released under a CC-BY-NC 4.0 license.

GraphLog(^3^33[https://github.com/facebookresearch/graphlog](https://github.com/facebookresearch/graphlog)) [] involves examples for 57 different *worlds*, where each world is characterised by a set of logical rules. For each world, a number of corresponding knowledge graphs are provided, which the model can use to learn the underlying rules. The model is then tested on previously unseen knowledge graphs for the same world. The aim of this benchmark is to test the ability of models to systematically generalise from the reasoning patterns that have been observed during training, i.e. to apply the rules that have been learned from the training data in novel ways. This dataset is released under a CC-BY-NC 4.0 license.

RCC-8 is the benchmark that we introduce in this paper, as described in Section A.5. We release this benchmark under a CC-BY 4.0 license.

Dataset statistics for CLUTRR, GraphLog and RCC-8 are reported in tables 7, 9, 8. We use a standard 80-20 split for training and validation for CLUTRR and RCC-8. For GraphLog, we use the validation set that is provided separately from the test set.

#### A.7.3 Baselines

We compare our method against the following neuro-symbolic methods:

Conditional Theorem Provers [] are a more efficient version of Neural Theorem Provers (NTPs []). Like NTPs, they learn a differentiable logic program, but rather than exhaustively considering all derivations, at each step of a proof, CTPs learn a filter function that selects the most promising rules to apply, thereby speeding up backwards-chaining procedure of NTP. Three variants of this model were proposed, which differ in how this selection step is done, i.e. using a linear mapping (CTPL), using an attention mechanism (CTPA), and using a method inspired by key-value memory networks [] (CTPM). We were not able to reproduce the results from the original paper, hence we report the results from [] for the CLUTRR benchmark.

Greedy NTPs [] are another approximation of NTPs, which select the top-$k$ best matches during each inference step.

This model [] learns symbolic rules of the form $r(X,Z)\leftarrow r_{1}(X,Y)\wedge r_{2}(Y,Z)$, with the possibility of using invented predicates in the head. To make a prediction, the method then samples (or enumerates) simple paths between the head and tail entities and iteratively applies the learned rules to reduce these paths to a single relation. The order in which relations are composed is determined by Monte Carlo Tree Search.

Neural Compositional Rule Learning [] also samples relational paths between the head and tail entities, and iteratively reduces them by composing 2 relations at a time, similar to R5. However, in this case, the choice of the two relations to compose in each step are determined by a Recurrent Neural Network. Moreover, rather than learning symbolic rules, the rules are learned implicitly by using an attention mechanism to compose relations. Both R5 and NCRL implicitly make the assumption that the relational reasoning problem is about predicting the target relation from a single relational path, and that this prediction can be done by repeatedly applying Horn rules.

The following transformer [] variant is also a natural baseline:

Edge Transformers [] modify the transformer architecture by using an attention mechanism that is designed to simulate relational composition. In particular, the embeddings are interpreted as representations of edges in a graph. To update the representation of an edge $(a,c)$ the model selects pairs of edges $(a,x),(x,b)$ and composes their embeddings. These compositions are aggregated using an attention mechanism, similar as in the standard transformer architecture.

We also compare against several GNN models:

Graph Convolutional Networks [] are a standard graph neural network architecture, which use sum pooling and rely on a linear layer followed by a non-linearity such as ReLU or sigmoid to compute messages. While standard GCNs do not take into account edge types, for the experiments we concatenate edge types to node embeddings during message passing, following []. GCNs learn node embeddings and can thus not directly be used for relation classification. To make the final prediction, we combine the final-layer embeddings of the head and tail entities with an encoding of the target relation, and make the final prediction using a softmax classification layer.

Relational GCNs [] are a variant of GCNs in which messages are computed using a relation-specific linear transformation. This is similar in spirit to how we compute messages in our framework, but without the inductive bias that comes from treating embeddings as probability distributions over primitive relation types.

Graph Attention Networks [] are a variant of GCNs, which use a pooling mechanism based on attention. Similar as for GCNs, we concatenate the edge types to node embeddings to take into account the edge types.

Edge-based Graph Attention Networks [] are a variant of GATs which take edge types into account. In particular, an LSTM module is used to combine the embedding of a neighbouring node with an embedding of the edge type. The resulting vectors are then aggregated as in the GAT architecture.

Neural Bellman-Ford Networks [] model the relationship between a designated head entity and the other entities from a given graph. Our model employs essentially the same strategy to use GNNs for relation classification, which is to learn entity embeddings that capture the relationship with the head entity rather than the entities themselves. The main difference between NBFnet and our model comes from the additional inductive bias that our model is adding.

In [], a number of sequence classifiers were also used as baselines, and we also report these results. These methods sample a path between the head and the tail, encode the path using a recurrent neural network, and then make a prediction with a softmax classification layer. We report results for three types of architectures: vanilla RNNs, LSTMs [] and GRUs [].

**Table 10: Optimal hyperparameters of the full (forward-backward) model on all benchmarks.**
|  | Batch<br>size | Embedding<br>dim | Epochs | Facets | Learning<br>rate | Margin |
| --- | --- | --- | --- | --- | --- | --- |
| CLUTRR | 128 | 64 | 100 | 8 | 0.01 | 1.0 |
| GraphLog | 64 | 64 | 150 | 1 | 0.01 | 1.0 |
| RCC-8 | 64 | 32 | 40 | 4 | 0.01 | 1.0 |

**Table 11: Results on CLUTRR (accuracy) after training on problems with $k\in\{2,3\}$ and then evaluating on problems with $k\in\{4,\ldots,10\}$. The best performance for each $k$ is highlighted in bold. Results marked with ^∗ were taken from [] and those with ^† from []. The results from [] and [] were evaluated on a different variant of the dataset and may thus not be directly comparable.**
|  | 4 Hops | 5 Hops | 6 Hops | 7 Hops | 8 Hops | 9 Hops | 10 Hops |
| --- | --- | --- | --- | --- | --- | --- | --- |
| FB-mul (ours) | 0.96$\pm$.02 | 0.96$\pm$.03 | 0.94$\pm$.05 | 0.92$\pm$.07 | 0.90$\pm$.10 | 0.88$\pm$.11 | 0.85$\pm$.13 |
| FB-min (ours) | 0.96$\pm$.02 | 0.95$\pm$.05 | 0.91$\pm$.08 | 0.87$\pm$.11 | 0.82$\pm$.13 | 0.79$\pm$.14 | 0.74$\pm$.15 |
| R5^† | 0.98$\pm$.02 | 0.99$\pm$.02 | 0.98$\pm$.03 | 0.96$\pm$.05 | 0.97$\pm$.01 | 0.98$\pm$.03 | 0.97$\pm$.03 |
| $\mbox{CTP}_{L}^{*}$ | 0.98$\pm$.02 | 0.98$\pm$.03 | 0.97$\pm$.05 | 0.96$\pm$.04 | 0.94$\pm$.05 | 0.89$\pm$.07 | 0.89$\pm$.07 |
| $\mbox{CTP}_{A}^{*}$ | 0.99$\pm$.02 | 0.99$\pm$.01 | 0.99$\pm$.02 | 0.96$\pm$.04 | 0.94$\pm$.05 | 0.89$\pm$.08 | 0.90$\pm$.07 |
| $\mbox{CTP}_{M}^{*}$ | 0.97$\pm$.03 | 0.97$\pm$.03 | 0.96$\pm$.06 | 0.95$\pm$.06 | 0.93$\pm$.05 | 0.90$\pm$.06 | 0.89$\pm$.06 |
| GNTP^∗ | 0.49$\pm$.18 | 0.45$\pm$.21 | 0.38$\pm$.23 | 0.37$\pm$.21 | 0.32$\pm$.20 | 0.31$\pm$.19 | 0.31$\pm$.22 |
| ET | 0.90$\pm$.04 | 0.84$\pm$.02 | 0.78$\pm$.02 | 0.69$\pm$.03 | 0.63$\pm$.05 | 0.58$\pm$.06 | 0.55$\pm$.08 |
| GAT^∗ | 0.91$\pm$.02 | 0.76$\pm$.06 | 0.54$\pm$.03 | 0.56$\pm$.04 | 0.54$\pm$.03 | 0.55$\pm$.05 | 0.45$\pm$.06 |
| GCN^∗ | 0.84$\pm$.03 | 0.68$\pm$.02 | 0.53$\pm$.03 | 0.47$\pm$.04 | 0.42$\pm$.03 | 0.45$\pm$.03 | 0.39$\pm$.02 |
| NBFNet | 0.55$\pm$.08 | 0.44$\pm$.07 | 0.39$\pm$.07 | 0.37$\pm$.06 | 0.34$\pm$.04 | 0.32$\pm$.05 | 0.31$\pm$.05 |
| R-GCN | 0.80$\pm$.09 | 0.63$\pm$.08 | 0.52$\pm$.11 | 0.46$\pm$.07 | 0.41$\pm$.05 | 0.39$\pm$.06 | 0.38$\pm$.05 |
| RNN^∗ | 0.86$\pm$.06 | 0.76$\pm$.08 | 0.67$\pm$.08 | 0.66$\pm$.08 | 0.56$\pm$.10 | 0.55$\pm$.10 | 0.48$\pm$.07 |
| LSTM^∗ | 0.98$\pm$.04 | 0.95$\pm$.03 | 0.88$\pm$.05 | 0.87$\pm$.04 | 0.81$\pm$.07 | 0.75$\pm$.10 | 0.75$\pm$.09 |
| GRU^∗ | 0.89$\pm$.05 | 0.83$\pm$.06 | 0.74$\pm$.12 | 0.72$\pm$.09 | 0.67$\pm$.12 | 0.62$\pm$.10 | 0.60$\pm$.12 |

#### A.7.4 Training details

The relation vectors $\mathbf{r}$ and the vectors $\mathbf{a}_{ij}$ defining the composition function are uniformly initialised. All baseline results that were obtained by us were hyperparameter-tuned using grid search, as detailed below. Some baseline results were obtained from their corresponding papers and reported verbatim (as indicated in the results tables). All experiments were conducted using a single RTX 4090 NVIDIA GPU. A single experiment using the GNN based methods in the paper can be conducted within 30 minutes to an hour on a similar machine. This includes training and testing a single model on any benchmark (CLUTRR, GraphLog, RCC-8). A single hyperparameter set evaluation would take the same time as an individual experiment.

##### Hyperparameter settings

We use the Adam optimizer []. The number of layers of the FB model is fixed to 9 and the number of negative examples per instance is fixed as 1. The other hyperparameters of the FB model are tuned using grid search. The optimal values that were obtained are mentioned in Table 10.

We conduct the following hyperparameter sweeps: learning rate in $\{0.00001,0.001,0.01,0.1\}$, batch size in $\{16,32,64,128\}$, number of facets $m$ in $\{1,2,4,8,16,32\}$ and embedding dimension size in $\{8,16,32,64,128,256\}$. We also tune the margin $\Delta$ in the loss function over $\{10,1,0.1,0.01\}$. All model parameters are shared across the different message passing layers of our model.

The choice of the pooling operator has an important impact on the systematic generalisation abilities of the model. In our experiments, we found that the pooling operator has to be specified as part of the inductive bias and cannot be learned from the training or validation data, which is in accordance with findings from the literature on systematic generalisation [, ].

**Table 12: Results for all combinations of the individual ablations from Table 4.**
| Facet<br>Ablation | Probability<br>Ablation | Composition<br>Ablation | FB<br>Ablation | CLUTRR<br>Avg | CLUTRR<br>$k=10$ | RCC-8<br>Avg | RCC-8<br>$b=3,k=9$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| True | True | True | True | 0.06 | 0.04 | 0.12 | 0.12 |
| True | True | True | False | 0.10 | 0.15 | 0.12 | 0.12 |
| True | True | False | True | 0.27 | 0.24 | 0.25 | 0.17 |
| True | True | False | False | 0.20 | 0.16 | 0.25 | 0.14 |
| True | False | True | True | 0.06 | 0.04 | 0.12 | 0.12 |
| True | False | True | False | 0.11 | 0.20 | 0.12 | 0.12 |
| True | False | False | True | 0.92 | 0.73 | 0.81 | 0.49 |
| True | False | False | False | 0.94 | 0.85 | 0.92 | 0.68 |
| False | True | True | True | 0.06 | 0.04 | 0.22 | 0.18 |
| False | True | True | False | 0.11 | 0.15 | 0.12 | 0.12 |
| False | True | False | True | 0.29 | 0.25 | 0.60 | 0.27 |
| False | True | False | False | 0.36 | 0.30 | 0.38 | 0.21 |
| False | False | True | True | 0.08 | 0.10 | 0.12 | 0.12 |
| False | False | True | False | 0.29 | 0.31 | 0.12 | 0.12 |
| False | False | False | True | 0.94 | 0.82 | 0.84 | 0.51 |
| False | False | False | False | 0.99 | 0.99 | 0.96 | 0.80 |

Figure: Figure 6: Schematic visualisation of the learned relation vectors for the RCC-8 benchmark.
Refer to caption: x19.png

Figure: Figure 7: Schematic visualisation of the learned relation vectors for the CLUTRR benchmark.
Refer to caption: x20.png

Figure: Figure 8: Schematic visualisation of the learned relation vectors for the Graph-Log benchmark.
Refer to caption: x21.png

### A.8 Additional analysis

##### Additional CLUTRR results

In the main paper, we presented the results for the standard CLUTRR benchmark, where problems of size $k\in\{2,3,4\}$ are used for training. In the literature, models are sometimes also evaluated on an even harder setting, where only problems of size $k\in\{2,3\}$ are available for training. We show the results for this setting in Table 11. As can be seen, our model clearly outperforms both Edge Transformers (ET) and the GNN and RNN baselines. In this more challenging setting, the difference in performance between our model and ET is much more pronounced. However, R5, as the best-performing neuro-symbolic method, consistently outperforms our method in this case. We hypothesise that this is largely due to the inevitably small size of the training set (as the number of distinct paths of length 3 is necessarily limited). Rule learners can still perform well in such cases, which is something that R5 is able to exploit. To achieve similar results with our model, a stronger inductive bias would have to be imposed. One possibility would be to impose a sparsity prior on the relation embeddings $\mathbf{r}$ and the vectors $\mathbf{a}_{ij}$ defining the composition function. We leave a detailed investigation of this possibility for future work.

In the literature, two different variants of the dataset have been used: db_9b2173cf and data_089907f8.
In Table 11, we use the CLUTRR dataset db_9b2173cf, which was introduced in the ET paper [], to evaluate our model as well as the baselines that were evaluated by us. The reported baseline results that were obtained from [] and [] are based on the smaller data_089907f8 variant, and are thus not directly comparable.

##### Allen’s Interval algebra benchmark results

**Table 13: Allen’s interval algebra benchmark results (accuracy). Timeout refers to the model taking longer than 30 minutes for inference. Models are trained on graphs with $b\in\{1,2,3\}$ paths of length $k\in\{2,3,4\}$. For each $k$ and $b$, the best performance across all the models is highlighted in bold.**
|  |  | 2 Hops | 3 Hops | 4 Hops | 5 Hops | 6 Hops | 7 Hops | 8 Hops | 9 Hops |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| FB-min (ours) | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.99$\pm$0.0 | 0.99$\pm$0.0 | 0.98$\pm$0.0 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.97$\pm$0.01 | 0.97$\pm$0.01 | 0.94$\pm$0.01 | 0.93$\pm$0.01 | 0.89$\pm$0.01 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.97$\pm$0.01 | 0.95$\pm$0.01 | 0.92$\pm$0.01 | 0.91$\pm$0.01 | 0.88$\pm$0.02 |  |
| FB-mul (ours) | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.99$\pm$0.0 | 0.99$\pm$0.01 | 0.98$\pm$0.01 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.91$\pm$0.01 | 0.88$\pm$0.01 | 0.83$\pm$0.01 | 0.81$\pm$0.01 | 0.77$\pm$0.01 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.84$\pm$0.02 | 0.83$\pm$0.01 | 0.78$\pm$0.01 | 0.76$\pm$0.0 | 0.72$\pm$0.0 |  |
| ET | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.92$\pm$0.01 | 0.9$\pm$0.01 | 0.87$\pm$0.01 | 0.85$\pm$0.01 | 0.81$\pm$0.01 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.86$\pm$0.01 | 0.85$\pm$0.02 | 0.8$\pm$0.02 | 0.77$\pm$0.02 | 0.7$\pm$0.02 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.85$\pm$0.01 | 0.84$\pm$0.02 | 0.78$\pm$0.02 | 0.73$\pm$0.03 | 0.64$\pm$0.03 |  |
| NCRL | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.48$\pm$0.0 | 0.49$\pm$0.0 | 0.46$\pm$0.03 | 0.47$\pm$0.02 | 0.45$\pm$0.03 |
| $b=2$ | 0.6$\pm$0.0 | 0.59$\pm$0.0 | 0.59$\pm$0.01 | 0.32$\pm$0.01 | 0.33$\pm$0.01 | 0.3$\pm$0.01 | 0.3$\pm$0.01 | 0.29$\pm$0.01 |  |
| $b=3$ | 0.53$\pm$0.01 | 0.52$\pm$0.0 | 0.53$\pm$0.01 | 0.28$\pm$0.01 | 0.29$\pm$0.02 | 0.27$\pm$0.02 | 0.27$\pm$0.02 | 0.26$\pm$0.02 |  |
| R5 | $b=1$ | 0.26$\pm$0.01 | 0.25$\pm$0.01 | 0.24$\pm$0.01 | 0.09$\pm$0.01 | 0.08$\pm$0.01 | 0.07$\pm$0.01 | timeout | timeout |
| $b=2$ | 0.2$\pm$0.01 | 0.16$\pm$0.01 | 0.15$\pm$0.01 | 0.08$\pm$0.01 | 0.08$\pm$0.01 | timeout | timeout | timeout |  |
| $b=3$ | 0.19$\pm$0.01 | 0.15$\pm$0.01 | 0.14$\pm$0.01 | 0.11$\pm$0.01 | 0.1$\pm$0.01 | timeout | timeout | timeout |  |
| NBFNet | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.78$\pm$0.19 | 0.61$\pm$0.26 | 0.5$\pm$0.21 | 0.47$\pm$0.2 | 0.45$\pm$0.18 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.67$\pm$0.23 | 0.49$\pm$0.21 | 0.37$\pm$0.13 | 0.34$\pm$0.11 | 0.31$\pm$0.09 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.61$\pm$0.29 | 0.42$\pm$0.2 | 0.29$\pm$0.11 | 0.26$\pm$0.08 | 0.23$\pm$0.06 |  |
| R-GCN | $b=1$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.77$\pm$0.09 | 0.33$\pm$0.07 | 0.39$\pm$0.04 | 0.38$\pm$0.02 | 0.32$\pm$0.03 |
| $b=2$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.72$\pm$0.08 | 0.29$\pm$0.08 | 0.36$\pm$0.06 | 0.33$\pm$0.04 | 0.28$\pm$0.02 |  |
| $b=3$ | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 1.0$\pm$0.0 | 0.7$\pm$0.06 | 0.3$\pm$0.06 | 0.35$\pm$0.03 | 0.31$\pm$0.03 | 0.27$\pm$0.02 |  |

Results are shown in Table 13. The best model is again FB-min just like in the case for RCC-8 followed by FB-mul and then ET. Results are in line with those obtained for RCC-8 in Table 2. However, we also note that since the interval algebra has more primitive relations and therefore a larger composition table, the benchmark is more challenging than RCC-8. This results in smaller final hop accuracies for all models for $k=9,b=3$.

##### Extended ablation analysis

In the main paper, we considered four separate ablations. Table 12 extends this analysis by showing results for all combinations of these ablations.
Facet ablation refers to the configurations where $m=1$; probability ablation refers to the configuration where embeddings are unconstrained; composition ablation refers to the configuration where distmult in combination with an MLP is used as the composition function $\psi$; and FB ablation refers to the configuration where we only have the forward model. We can clearly see that the probability and composition function ablation cause a significantly stronger performance degradation compared to the facet and forward-backward ablation.

##### Learned sparseness of relation vectors

We visualise the learned relation vectors for each benchmark studied in this paper in Figures 6, 7 and 8. It can be seen that the vectors are mostly one-hot, despite the fact that no explicit sparsity constraints were used in the model.

##### Effect of the number of message passing rounds on final-hop accuracy

We study the effect of varying the number of message passing rounds on the final $k$-hop accuracy at $b=3$ for the FB-min and FB-mul models on the RCC-8 and Interval datasets. These models are trained ab initio with the same training data and configuration as before but with a different number of message passing rounds (from 5 to 15) for each instance. The results are displayed in Figure 9. There are three pertinent observations that can be made. Firstly, the maximum attained final $k$-hop accuracy decreases with $k$, which makes sense as it confirms that the problem complexity increases with $k$. Secondly, there is a jump in the final $k$-hop accuracy when the number of message passing rounds matches $k$ and the accuracies saturate in the number of message passing rounds after that. This rightly suggests that the number of message passing rounds should at least be equal to the final $k$-hop in the dataset to ensure that all information propagates from source to sink within the model. Thirdly, these observations are shared across the dataset types and aggregation functions.

Figure: Figure 9: Effect of the number of message passing rounds on the final $k$-hop accuracy for the FB model on the Interval and RCC-8 datasets. There is a sharp jump in performance when $k$ equals the number of message passing rounds.
Refer to caption: x22.png

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: See above weakness
soundness: 3
strengths: 1. The method introduced here demonstrates significantly higher efficiency compared to other baselines, as clearly illustrated in Figure 5.
2. The proposed method is compared against various baselines, including both rule-based and graph-based approaches, and consistently shows superior performance.
3. New synthetic datasets are provided in this work.
summary: This work presents a representation-based method for predicting relationships between entities within a knowledge graph. The approach leverages Graph Neural Networks (GNNs) and incorporates epistemic states as node representations. The proposed method is benchmarked against various rule-based and graph-based approaches, demonstrating superior performance.
weaknesses: 1. In my opinion, representing each node/entity as a distribution over relations is unconventional. Despite its parameter efficiency and superior performance, this embedding/representation method has notable drawbacks: (1) The learned embeddings are non-transferable across datasets, as different datasets may have varying numbers of relations. (2) It completely ignores the semantic information of entities, making the semantic interpretation of these representations difficult.
2. The notations in Section 3 are somewhat challenging to follow. For instance, what does 𝑓 represent in Eq. 4 and the equation preceding it? Additionally, why is 𝑓 not illustrated in Figure 3? Furthermore, in Eq. 4, how is a_ij ​ defined? Providing an example of this variable or illustrating it within the message passing subplot in Figure 3 could enhance interpretability.
3. I am not an expert in this field, but I wonder if this method can be applied to entity prediction. From my perspective, entity prediction is more interesting and challenging in knowledge graphs (KG) and temporal knowledge graphs (tKG) [1, 2]. It seems that relation prediction is relatively simpler, as the number of potential relations to predict is usually limited to a few hundred. Can the method proposed in this work be generalized to entity prediction, or is it restricted to relation prediction?

[1] Anytime Bottom-Up Rule Learning for Knowledge Graph Completion
[2] TLogic: Temporal Logical Rules for Explainable Link Forecasting on Temporal Knowledge Graphs

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. line 113: Shouldn't $\mathcal{K} \circ \mathcal{F}$ (applies on) better than $\mathcal{K} \cup \mathcal{F}$ (union). Since $\mathcal{K}$ are rule set like $r_1 \wedge r_2 = r_3$ while $\mathcal{F}$ are facts like $r_1(a, b), r_1(b, c), r_2(c, d)$?
2. Equation 3: Based on your reasoning, this initialization hints the probability of some primitive relations. Then, it seems that the first one is if or not it is the anchor node (zero-one init as NBFNet). If that undertstanding is correct, shouldn't the second be $(0, 1/(n-1), \dots)$?
3. line 236: This equation is slightly different from tradition GNN update rule in the sense that node embedding itself is considered as a message (self-loop edge), and update function is removed, any hint behind doing that?
4. line 244: It will be better to use $\mathbf{A}$ instread of $\emph{\mathbf{a}}$ since it is a 3D tensor rather than a vector.
5. line 269: Is the relation being pairwise disjoint is the assumption only on your dataset? I don't think this is true for most real-world knowledge graphs.
6. line 275-280: If we add multi facet only at loss function, we are training them independently, shouldn't be better to add a pooling at final output of each layer, just as multi-head attention?
7. Equation 6: You are only merging bidirections on both ends, but won't it be possible that we have to merge relations in the middle first? If so, shouldn't we merge at the output of every layer?
8. An overall concern: Your design eventually is the same as message passing on query anchored graph (except the final bidrection aggregation), which is proposed in NBFNet (except initialization and message passing function). My question is which unique design makes it more capable than NBFNet, thus can solve problem it can not handle?
9. Table 1: Why NBFNet is worse than GCN, GAT and RGCN in many cases? Does that mean that NBFNet is extremely poor in true logic reasoning? One more thing, it seems that you are only picking samples that relations must exist which is slightly different from NBFNet purpose for link prediction. Can you also add unrelated samples in the test? Indeed, in Table 3 where such negative samples exist, your method is not performing such better, thus this may mean your method fails to handle unrelated node pairs which I believe could be a big risk in real-world applications.
10. Table 1 and 2: It is claimed before than NCRL and R5, as single-path method, is not capable to solve the studying problem (line 183), however, they are mostly the best on two proposed benchmarks, doesn't that means your benchmarks are not the best fit for evaluation? Shouldn't you additionally propose a synthetic benchmark, that truly justify your method can handle multi-path reasoning? 
11. Based on overall experiment result, the advantage of your proposal is more efficient in longer relation path generation, thus can you provide the real runtime (training and inference) comparison with NCRL and R5 (which achieves best performance on same scenarios).
soundness: 2
strengths: - This paper focuses on longer logic inference with requirement of multi-path disjunctive reasoning, which are critical problems in knowledge graph.
- This paper's solution is based on scalable framework, making it useful in giant knowledge graphs in real world.
- This paper has prove of expressivity in the sense of logical reasoning, promising its power to handle focusing problems.
summary: This paper focuses on a challenge on current knowledge graph inference study that learned model fails to generalize to test cases with longer logical inference path. This paper modifies the state-of-the-art NBFNet design, and proposes EpiGNN, a scalable model which is proved to be same expressive as multi-path disjunctive reasoning that is enough to solve the relation inference of any length. They proposes two benchmarks CLUTRR and GraphLog to evaluate longer relational path inference, and empirically showcase that their method can achieve same good performance as state-of-the-art methods but with better efficiency. They also empirically shows that their model can achieve close-to-best performance on real-world benchmarks where longer logic inference may not be necessary.
weaknesses: - Some design details have potentially alternatives, but is lack of reasoning, leaving concerns that if the implementation is the best design under proposed framework.
- The empirical evidence is not strong enough to showcase their claims:
   - The studying problem is claimed to be unsolvable for existing methods, while baselines can achieve the best performance.
   - The method is claimed to be more scalable than related baselines, however, there is runtime or memory cost comparison in main content.
   - In real-world benchmarks, their method is not such close to state-of-the-art as they claimed. I think adding confidence interval will better defend their point here.
- Their design does not significantly differ from related work NBFNet, but is lack of theoretical justification why their method can be more powerful than this related work.

---

confidence: 5
contribution: 2
initial_rating: 6
presentation: 4
questions: - Line 50 & 53: It is more precise to say neural theorem provers rather than neuro-symbolic methods. Neuro-symbolic methods are a very broad family, and not all of them focus on modeling single relational paths.
- Proposition 1: I guess there exist scenarios where the count of a certain relational path matters, right? Maybe you can take this into consideration.
- Line 154-155: This statement is not true for representation learning methods like NBFNet and EpiGNNs. If the reduction of relations follows the associative property (i.e. $(a\times b)\times c=a\times (b\times c)$), representation learning methods can deal with intermediate relations that are not present in the training data.
- Can you include a few references for epistemic states if this concept is not invented by this paper?
- Line 269-271: The pairwise disjoint assumption only holds for CLUTRR and Graphlog. It doesn’t hold for knowledge graph datasets in general.
- Typo: Line 100: single-path base → single-path-based
soundness: 3
strengths: - This paper introduce two new datasets for benchmarking systematic generalization. The two new datasets consider multi-path disjunctive rules, which is challenging for most existing methods.
- EpiGNNs achieve state-of-the-art performance on the two new datasets. EpiGNNs also achieve competitive performance against existing methods on systematic generalization datasets, while being more efficient.
- EpiGNNs have theoretical connection with the algebraic closure algorithm, though this point is not illustrated much in the main paper.
- This paper is well-written and easy to comprehend.
summary: This paper aims to solve systematic generalization in relational reasoning problems. Existing GNNs lack the ability to generalize systematically, while existing neuro-symbolic methods can generalize but tend to make strong assumptions. The authors propose Epistemic GNNs (EpiGNNs), which not only solves systematic generalization but is also scalable and parameter efficient. Technically, EpiGNNs modify the NBFNet architecture to represent representations between entities as distributions over primitive relationships. The messages are then defined as learnable weighted compositions of these primitive relations. Besides, the authors also propose a few tricks to augment EpiGNNs, including jointly training several models and two forward & backward models. The authors introduce two new datasets for benchmarking the ability of handling disjunctive relational paths. Empirically, EpiGNNs surpass all methods on the two new datasets. EpiGNNs also achieve competitive performance against existing methods on systematic generalization and inductive knowledge graph completion datasets.
weaknesses: - EpiGNNs are variants of NBFNet[1] with some engineering modifications: 1) hidden representations are replaced by probability distributions; 2) DistMult message function is replaced by Tucker decomposition[2] (Equation 4); 3) pooling function has an additional L1 normalization; 4) joint training of multiple models and forward-backward models. While I am not saying that EpiGNNs are incremental, the authors need to show how these modifications contribute to systematic generalization and provide experimental evidence for Line 257-258.
- The authors miss an important baseline for systematic generalization: EdgeTransformer[3]. EdgeTransformer aggregates multiple relational paths like EpiGNNs and NBFNet. It can solve the sequential problem (Line 146-148) in arbitrary reduction order, which is even better than EpiGNNs. EdgeTransformer is likely to be a strong baseline for the two new datasets.
- If I understand correctly, EpiGNNs use the same parameter matrix $\bf{a}_{ij}$ across all layers. The original NBFNet uses different parameters for different layers and is not ideal for systematic generalization. Can you try a stronger NBFNet baseline with parameters shared across all layers? You might need to add dropout in each layer of NBFNet, similar to the design of EdgeTransformer.
- It is trivial for EpiGNNs to achieve competitive performance against NBFNet on inductive knowledge graph completion, since EpiGNNs are just variants of NBFNet. This is not a contribution.

[1] Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. Zhu et al. NeurIPS 2021.

[2] TuckER: Tensor Factorization for Knowledge Graph Completion. Balažević et al. arXiv 2019.

[3] Systematic Generalization with Edge Transformers. Bergen et al. NeurIPS 2021.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: I’d be willing to increase the score if the authors could address the following questions:

Q1. Is there a link to the Relational WL test [1] when estimating the expressiveness of EpiGNNs?

Q2. KG completion evals on GraIL datasets should be executed in the full-ranking setup, not against 50 random negatives.

Q3. The new benchmarks should be future-proof for a few years ahead whereas RCC-8 and IA already seem to be saturating with models delivering 80%+ accuracy on hardest cases. Would it be possible to design more complex versions of the datasets where all compared models including EpiGNN would be challenged?
soundness: 3
strengths: **S1.** Theoretical findings are quite interesting: a link between path-based GNNs and algebraic closure and how to learn disjunctive rules with such GNNs. Since EpiGNN is based on NBFNets, it would make the theoretical expressiveness claims even stronger if there is a connection to the relational WL test [1] which was derived for simple relational GNNs (eg, R-GCN) and labeling trick GNNs (like NBFNet).

**S2.** Two new benchmarks for measuring systematic generalization with disjunctive reasoning patterns are nice to have for the community. However, there is a caveat that those benchmarks seem to be already saturated given that EpiGNN yields 90+% accuracy on them.

[1] Huang et al. A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs. NeurIPS 2023.
summary: The paper studies systematic generalization in the domain of multi-relational graphs. First, the authors identified that existing neuro-symbolic baselines capture only conjunctive rules and cannot capture disjunctive rules often present in spatial and temporal reasoning settings (such as Region Connected Calculus or Interval Algebra). Then, the paper introduced EpistemicGNN, which is able to learn disjunctive rules thanks to the theoretical alignment with algebraic closure. Practically, EpistemicGNN extends Neural Bellman-Ford Nets (NBFNet) with a new node labeling strategy, constrained node representations, changes to message passing and aggregation. For experiments, the authors introduced two new datasets for relation classification (RCC-8 and IA) and showed that EpiGNN is competitive with neuro-symbolic methods while being more parameter-efficient.
weaknesses: **W1.** Despite the variety of benchmarks, the experimental performance of EpiGNNs is somewhat underwhelming: CLUTTR is already a saturated benchmark that does not provide much useful signal, Edge Transformers are as good on two newly introduced benchmarks (which seem to be saturating already), and EpiGNN underperforms other baselines on GraphLOG and inductive KG completion benchmarks. 

It would make KG completion experiments much more compelling if EpiGNN is evaluated in the setup when predictions are ranked against _all_ nodes in the graph, not just against 50 random samples (there are many studies indicating that such ranking overestimates the results and is not indicative of the real performance). Since the backbone of EpiGNN is NBFNet, it should be possible to rank against all entities right out of the box without modifications and compare against stronger baselines that were evaluated on the full ranking task (for instance, NBFNet, A*Net, RED-GNN, AdaProp).

Meta-review: This paper introduces Epistemic GNN (EpiGNN), a novel GNN architecture designed for systematic reasoning in relational domains. EpiGNN overcomes the limitations of regular GNNs by treating node embeddings as epistemic states and using specialized message passing. It achieves state-of-the-art results in link prediction and knowledge graph completion tasks, and outperforms existing methods in new benchmarks that require aggregating information from multiple paths. 

This paper is well-written and easy to comprehend. Two new benchmarks for measuring systematic generalization with disjunctive reasoning patterns are nice to have for the community.

Decision: Accept (Poster)