# Systematic Reasoning About Relational Domains
With Graph Neural Networks

Irtaza Khalid and Steven Schockaert
School of Computer Science & Informatics
Cardiff University, UK
<EMAIL_ADDRESS>

###### 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 [43] or require
longer inference chains [33]. This behaviour has been observed for different
types of reasoning problems and different types of architectures, including
Language Models [43, 39] and Graph Neural Networks [33]. A common solution is
to rely on some kind of neuro-symbolic approach. For instance, Neural Theorem
Provers (NTPs [29, 25]) 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 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}$.

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 [46] 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 [27]. 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 [32]), 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
online111github.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 [35] or recurrent [12] models, to more recent approaches based on
GNNs [44, 46, 45], pre-trained language models [9, 19, 10] or tailor-made
architectures for relational reasoning [30, 5]. 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, [9] showed that a fine-tuned
BERT [13] model can reason about (natural language descriptions of)
propositional Horn rules with a remarkable accuracy. However, a follow-up
analysis in [43] 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 [14, 36].

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) [26] and are
also close to the widely studied problem of link prediction in knowledge
graphs [6]. Intuitively, GNNs should be well-suited for solving such reasoning
tasks. However, [33] 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, [34] 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 [29, 25])
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
[22, 7]. 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 [40]. Similar to our proposed model, Edge Transformers [5] also
aim to align the model with the problem of relational reasoning. Their model
essentially modifies the attention mechanism from the Transformer model [37]
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 [22] and NCRL [7]. Neural theorem provers [29]
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).

###  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 [1,
27].

######  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 [28].

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).

##  4 A GNN for systematic reasoning

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.

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 [46], 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 [32]. 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 [18]. We consider two existing benchmarks designed to
test systematic generalisation for relational reasoning: CLUTRR [33] and
GraphLog [34]. 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 [25], those with † from [22] and those with 2 from [7]. 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
NCRL2 | 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 [22] and those with † from [7]. 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 [7] and R5 [22]. 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 [22], 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 [42] 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.

## References

  * [1] J. F. Allen.  Maintaining knowledge about temporal intervals.  Commun. ACM, 26(11):832–843, 1983.
  * [2] J. F. Allen.  Maintaining knowledge about temporal intervals.  Communications of the ACM, 26(11):832–843, 1983.
  * [3] N. Amaneddine, J. Condotta, and M. Sioutis.  Efficient approach to solve the minimal labeling problem of temporal and spatial qualitative constraints.  In F. Rossi, editor, IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 696–702. IJCAI/AAAI, 2013.
  * [4] D. Bahdanau, S. Murty, M. Noukhovitch, T. H. Nguyen, H. d. Vries, and A. Courville.  Systematic generalization: What is required and can it be learned?  In International Conference on Learning Representations, 2019.
  * [5] L. Bergen, T. J. O’Donnell, and D. Bahdanau.  Systematic generalization with edge transformers.  In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 1390–1402, 2021.
  * [6] A. Bordes, J. Weston, R. Collobert, and Y. Bengio.  Learning structured embeddings of knowledge bases.  In W. Burgard and D. Roth, editors, Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011, pages 301–306. AAAI Press, 2011\.
  * [7] K. Cheng, N. K. Ahmed, and Y. Sun.  Neural compositional rule learning for knowledge graph reasoning.  In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023\.
  * [8] K. Cho, B. van Merrienboer, Ç. Gülçehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio.  Learning phrase representations using RNN encoder-decoder for statistical machine translation.  In A. Moschitti, B. Pang, and W. Daelemans, editors, Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL, pages 1724–1734. ACL, 2014.
  * [9] P. Clark, O. Tafjord, and K. Richardson.  Transformers as soft reasoners over language.  In C. Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3882–3890. ijcai.org, 2020.
  * [10] A. Creswell, M. Shanahan, and I. Higgins.  Selection-inference: Exploiting large language models for interpretable logical reasoning.  In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023\.
  * [11] Z. Cui, A. G. Cohn, and D. A. Randell.  Qualitative and topological relationships in spatial databases.  In D. J. Abel and B. C. Ooi, editors, Advances in Spatial Databases, Third International Symposium, SSD’93, Singapore, June 23-25, 1993, Proceedings, volume 692 of Lecture Notes in Computer Science, pages 296–315. Springer, 1993.
  * [12] A. S. d’Avila Garcez and G. Zaverucha.  The connectionist inductive learning and logic programming system.  Appl. Intell., 11(1):59–77, 1999.
  * [13] J. Devlin, M. Chang, K. Lee, and K. Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In J. Burstein, C. Doran, and T. Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pages 4171–4186. Association for Computational Linguistics, 2019.
  * [14] N. Dziri, X. Lu, M. Sclar, X. L. Li, L. Jiang, B. Y. Lin, S. Welleck, P. West, C. Bhagavatula, R. L. Bras, J. D. Hwang, S. Sanyal, X. Ren, A. Ettinger, Z. Harchaoui, and Y. Choi.  Faith and fate: Limits of transformers on compositionality.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023.
  * [15] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  Neural Comput., 9(8):1735–1780, 1997.
  * [16] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [17] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [18] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga, R. L. Phillips, I. Gao, T. Lee, E. David, I. Stavness, W. Guo, B. Earnshaw, I. Haque, S. M. Beery, J. Leskovec, A. Kundaje, E. Pierson, S. Levine, C. Finn, and P. Liang.  Wilds: A benchmark of in-the-wild distribution shifts.  In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5637–5664. PMLR, 18–24 Jul 2021.
  * [19] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa.  Large language models are zero-shot reasoners.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.
  * [20] S. Li, Z. Long, W. Liu, M. Duckham, and A. Both.  On redundant topological constraints.  Artificial Intelligence, 225:51–76, 2015.
  * [21] Z. Long, M. Sioutis, and S. Li.  Efficient path consistency algorithm for large qualitative constraint networks.  In IJCAI International Joint Conference on Artificial Intelligence, 2016.
  * [22] S. Lu, B. Liu, K. G. Mills, S. Jui, and D. Niu.  R5: rule discovery with reinforced and recurrent relational reasoning.  In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
  * [23] A. H. Miller, A. Fisch, J. Dodge, A. Karimi, A. Bordes, and J. Weston.  Key-value memory networks for directly reading documents.  In J. Su, X. Carreras, and K. Duh, editors, Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pages 1400–1409. The Association for Computational Linguistics, 2016.
  * [24] P. Minervini, M. Bosnjak, T. Rocktäschel, S. Riedel, and E. Grefenstette.  Differentiable reasoning on large knowledge bases and natural language.  In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 5182–5190. AAAI Press, 2020.
  * [25] P. Minervini, S. Riedel, P. Stenetorp, E. Grefenstette, and T. Rocktäschel.  Learning reasoning strategies in end-to-end differentiable proving.  In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6938–6949. PMLR, 2020.
  * [26] S. H. Muggleton.  Inductive logic programming.  New Gener. Comput., 8(4):295–318, 1991.
  * [27] D. A. Randell, Z. Cui, and A. G. Cohn.  A spatial logic based on regions and connection.  In B. Nebel, C. Rich, and W. R. Swartout, editors, Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92). Cambridge, MA, USA, October 25-29, 1992, pages 165–176. Morgan Kaufmann, 1992.
  * [28] J. Renz and G. Ligozat.  Weak composition for qualitative spatial and temporal reasoning.  In P. van Beek, editor, Principles and Practice of Constraint Programming - CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005, Proceedings, volume 3709 of Lecture Notes in Computer Science, pages 534–548. Springer, 2005.
  * [29] T. Rocktäschel and S. Riedel.  End-to-end differentiable proving.  In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3788–3800, 2017.
  * [30] A. Santoro, D. Raposo, D. G. T. Barrett, M. Malinowski, R. Pascanu, P. W. Battaglia, and T. Lillicrap.  A simple neural network module for relational reasoning.  In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4967–4976, 2017.
  * [31] M. S. Schlichtkrull, T. N. Kipf, P. Bloem, R. van den Berg, I. Titov, and M. Welling.  Modeling relational data with graph convolutional networks.  In A. Gangemi, R. Navigli, M. Vidal, P. Hitzler, R. Troncy, L. Hollink, A. Tordai, and M. Alam, editors, The Semantic Web - 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings, volume 10843 of Lecture Notes in Computer Science, pages 593–607. Springer, 2018.
  * [32] S. Schockaert.  Embeddings as epistemic states: Limitations on the use of pooling operators for accumulating knowledge.  CoRR, abs/2210.05723, 2022.
  * [33] K. Sinha, S. Sodhani, J. Dong, J. Pineau, and W. L. Hamilton.  CLUTRR: A diagnostic benchmark for inductive reasoning from text.  In K. Inui, J. Jiang, V. Ng, and X. Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pages 4505–4514. Association for Computational Linguistics, 2019.
  * [34] K. Sinha, S. Sodhani, J. Pineau, and W. L. Hamilton.  Evaluating logical generalization in graph neural networks.  CoRR, abs/2003.06560, 2020.
  * [35] G. G. Towell and J. W. Shavlik.  Knowledge-based artificial neural networks.  Artif. Intell., 70(1-2):119–165, 1994.
  * [36] K. Valmeekam, M. Marquez, A. O. Hernandez, S. Sreedharan, and S. Kambhampati.  Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change.  In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023.
  * [37] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998–6008, 2017.
  * [38] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph attention networks.  In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
  * [39] S. Welleck, X. Lu, P. West, F. Brahman, T. Shen, D. Khashabi, and Y. Choi.  Generating sequences by learning to self-correct.  In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023\.
  * [40] K. Xu, J. Li, M. Zhang, S. S. Du, K. Kawarabayashi, and S. Jegelka.  What can neural networks reason about?  In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
  * [41] K. Xu, M. Zhang, J. Li, S. S. Du, K.-I. Kawarabayashi, and S. Jegelka.  How neural networks extrapolate: From feedforward to graph neural networks.  In International Conference on Learning Representations, 2021.
  * [42] B. Yang, W. tau Yih, X. He, J. Gao, and L. Deng.  Embedding entities and relations for learning and inference in knowledge bases, 2015.
  * [43] H. Zhang, L. H. Li, T. Meng, K. Chang, and G. V. den Broeck.  On the paradox of learning to reason from data.  In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 3365–3373. ijcai.org, 2023.
  * [44] Y. Zhang, X. Chen, Y. Yang, A. Ramamurthy, B. Li, Y. Qi, and L. Song.  Efficient probabilistic logic reasoning with graph neural networks.  In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
  * [45] Y. Zhang and Q. Yao.  Knowledge graph reasoning with relational digraph.  In F. Laforest, R. Troncy, E. Simperl, D. Agarwal, A. Gionis, I. Herman, and L. Médini, editors, WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 912–924. ACM, 2022.
  * [46] Z. Zhu, Z. Zhang, L. A. C. Xhonneux, and J. Tang.  Neural bellman-ford networks: A general graph neural network framework for link prediction.  In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 29476–29490, 2021.

##  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}}$.

###  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$. ∎

###  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 [3]). 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)$. ∎

###  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)}$

###  A.5 RCC-8 Dataset

Table 5: RCC-8 composition table [11] (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 [27] 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 [33] and GraphLog [34]:

  * •

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 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.

####  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. 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. 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. 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. 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. 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.

(a) $k=2,b=1$

(b) $k=2,b=2$

(c) $k=2,b=3$

(d) $k=4,b=1$

(e) $k=4,b=2$

(f) $k=4,b=3$

(g) $k=6,b=1$

(h) $k=6,b=3$

Figure 4: Some graph instances for the RCC-8 dataset generated using the
procedure described in A.5.1. The graph topology becomes more diverse for the
test instances when sub-graphs are embedded within a single path, as shown in
(g) for path length $k-6$ and number of paths $b=1$. In this particular case,
there are two sub-graphs that have been embedded in the graph by replacing two
edges. Instances of the type shown in (a), (b), (c), (d), (e), (f) are used in
the training set and the graph topology is fixed in this case. The target edge
label between the source node and the tail node that needs to be predicted by
the model is indicated by the dotted line.

####  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 [21]. 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 [20].

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

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

$<$ $>$ $\mathsf{d}$ $\mathsf{di}$ $\mathsf{o}$ $\mathsf{oi}$ $\mathsf{m}$
$\mathsf{mi}$ $\mathsf{s}$ $\mathsf{si}$ $\mathsf{f}$ $\mathsf{fi}$ $<$ $<$
$<,\mathsf{o}$, $\mathsf{m}$, $\mathsf{d}$, $\mathsf{s}$ $<$ $<$
$<,\mathsf{o}$, $\mathsf{m}$, $\mathsf{d}$, $\mathsf{s}$ $<$ $<,\mathsf{o}$,
$\mathsf{m}$, $\mathsf{d}$, $\mathsf{s}$ $<$ $<$ $<,\mathsf{o}$, $\mathsf{m}$,
$\mathsf{d}$, $\mathsf{s}$ $<$ $>$ $>$ $>$, $\mathsf{oi}$, $\mathsf{mi}$,
$\mathsf{d}$, $\mathsf{f}$ $>$ $>$, $\mathsf{oi}$, $\mathsf{mi}$,
$\mathsf{d}$, $\mathsf{f}$ $>$ $>$, $\mathsf{oi}$, $\mathsf{mi}$,
$\mathsf{d}$, $\mathsf{f}$ $>$ $>$, $\mathsf{oi}$, $\mathsf{mi}$,
$\mathsf{d}$, $\mathsf{f}$ $>$ $>$ $>$ $\mathsf{d}$ $<$ $>$ $\mathsf{d}$ $<$,
$\mathsf{o}$, $\mathsf{m}$, $\mathsf{d}$, $\mathsf{s}$ $>$, $\mathsf{oi}$,
$\mathsf{mi}$, $\mathsf{d}$, $\mathsf{f}$ $<$ $>$ $\mathsf{d}$ $>$,
$\mathsf{oi}$, $\mathsf{mi}$, $\mathsf{d}$, $\mathsf{f}$ $\mathsf{d}$ $<$,
$\mathsf{o}$, $\mathsf{m}$, $\mathsf{d}$, $\mathsf{s}$ $\mathsf{di}$ $<$,
$\mathsf{o}$, $\mathsf{m}$, $\mathsf{di}$, $\mathsf{fi}$ $>$, $\mathsf{oi}$,
$\mathsf{di}$, $\mathsf{mi}$, $\mathsf{si}$ $\mathsf{o}$, $\mathsf{oi}$,
$\mathsf{d}$, $\mathsf{s}$, $\mathsf{f}$, $\mathsf{di}$, $\mathsf{si}$,
$\mathsf{fi}$, $=$ $\mathsf{di}$ $\mathsf{o}$, $\mathsf{di}$, $\mathsf{fi}$
$\mathsf{oi}$, $\mathsf{di}$, $\mathsf{si}$ $\mathsf{o}$, $\mathsf{di}$,
$\mathsf{fi}$ $\mathsf{oi}$, $\mathsf{di}$, $\mathsf{si}$ $\mathsf{o}$,
$\mathsf{di}$, $\mathsf{fi}$ $\mathsf{di}$ $\mathsf{oi}$, $\mathsf{di}$,
$\mathsf{si}$ $\mathsf{di}$ $\mathsf{o}$ $<$ $>$, $\mathsf{oi}$,
$\mathsf{di}$, $\mathsf{mi}$, $\mathsf{si}$ $\mathsf{o}$, $\mathsf{d}$,
$\mathsf{s}$ $<$, $\mathsf{o}$, $\mathsf{m}$, $\mathsf{di}$, $\mathsf{fi}$
$<$, $\mathsf{o}$, $\mathsf{m}$ $\mathsf{o}$, $\mathsf{oi}$, $\mathsf{d}$,
$\mathsf{s}$, $\mathsf{f}$, $\mathsf{di}$, $\mathsf{si}$, $\mathsf{fi}$, $=$
$<$ $\mathsf{oi}$, $\mathsf{di}$, $\mathsf{si}$ $\mathsf{o}$ $\mathsf{o}$,
$\mathsf{di}$, $\mathsf{fi}$ $\mathsf{o}$, $\mathsf{d}$, $\mathsf{s}$ $<$,
$\mathsf{o}$, $\mathsf{m}$ $\mathsf{oi}$ $<$, $\mathsf{o}$, $\mathsf{m}$,
$\mathsf{di}$, $\mathsf{fi}$ $>$ $\mathsf{oi}$, $\mathsf{d}$, $\mathsf{f}$
$>$, $\mathsf{oi}$, $\mathsf{mi}$, $\mathsf{di}$, $\mathsf{si}$ $\mathsf{o}$,
$\mathsf{oi}$, $\mathsf{d}$, $\mathsf{di}$, $\mathsf{s}$, $\mathsf{si}$,
$\mathsf{f}$, $\mathsf{fi}$, $=$ $>$, $\mathsf{oi}$, $\mathsf{mi}$
$\mathsf{o}$, $\mathsf{di}$, $\mathsf{fi}$ $>$ $\mathsf{oi}$, $\mathsf{d}$,
$\mathsf{f}$ $\mathsf{oi}$, $>$, $\mathsf{mi}$ $\mathsf{oi}$ $\mathsf{oi}$,
$\mathsf{di}$, $\mathsf{si}$ $\mathsf{m}$ $<$ $>$, $\mathsf{oi}$,
$\mathsf{di}$, $\mathsf{mi}$, $\mathsf{si}$ $\mathsf{o}$, $\mathsf{d}$,
$\mathsf{s}$ $<$ $<$ $\mathsf{o}$, $\mathsf{d}$, $\mathsf{s}$ $<$
$\mathsf{f}$, $\mathsf{fi}$, $=$ $\mathsf{m}$ $\mathsf{m}$ $\mathsf{d}$,
$\mathsf{s}$, $\mathsf{o}$ $<$ $\mathsf{mi}$ $<$, $\mathsf{o}$, $\mathsf{m}$,
$\mathsf{di}$, $\mathsf{fi}$ $>$ $\mathsf{oi}$, $\mathsf{d}$, $\mathsf{f}$ $>$
$\mathsf{oi}$, $\mathsf{d}$, $\mathsf{f}$ $>$ $\mathsf{s}$, $\mathsf{si}$, $=$
$>$ $\mathsf{d}$, $\mathsf{f}$, $\mathsf{oi}$ $>$ $\mathsf{mi}$ $\mathsf{mi}$
$\mathsf{s}$ $<$ $>$ $\mathsf{d}$ $<$, $\mathsf{o}$, $\mathsf{m}$,
$\mathsf{di}$, $\mathsf{fi}$ $<$, $\mathsf{o}$, $\mathsf{m}$ $\mathsf{oi}$,
$\mathsf{d}$, $\mathsf{f}$ $<$ $\mathsf{mi}$ $\mathsf{s}$ $\mathsf{s}$,
$\mathsf{si}$, $=$ $\mathsf{d}$ $<$, $\mathsf{m}$, $\mathsf{o}$ $\mathsf{si}$
$<$, $\mathsf{o}$, $\mathsf{m}$, $\mathsf{di}$, $\mathsf{fi}$ $>$
$\mathsf{oi}$, $\mathsf{d}$, $\mathsf{f}$ $\mathsf{di}$ $\mathsf{o}$,
$\mathsf{di}$, $\mathsf{fi}$ $\mathsf{oi}$ $\mathsf{o}$, $\mathsf{di}$,
$\mathsf{fi}$ $\mathsf{mi}$ $\mathsf{s}$, $\mathsf{si}$, $=$ $\mathsf{si}$
$\mathsf{oi}$ $\mathsf{di}$ $\mathsf{f}$ $<$ $>$ $\mathsf{d}$ $>$,
$\mathsf{oi}$, $\mathsf{mi}$, $\mathsf{di}$, $\mathsf{si}$ $\mathsf{o}$,
$\mathsf{d}$, $\mathsf{s}$ $>$, $\mathsf{oi}$, $\mathsf{mi}$ $\mathsf{m}$ $>$
$\mathsf{d}$ $>$, $\mathsf{oi}$, $\mathsf{mi}$ $\mathsf{f}$ $\mathsf{f}$,
$\mathsf{fi}$, $=$ $\mathsf{fi}$ $<$ $>$, $\mathsf{oi}$, $\mathsf{di}$,
$\mathsf{mi}$, $\mathsf{si}$ $\mathsf{o}$, $\mathsf{d}$, $\mathsf{s}$
$\mathsf{di}$ $\mathsf{o}$ $\mathsf{oi}$, $\mathsf{di}$, $\mathsf{si}$
$\mathsf{m}$ $\mathsf{si}$, $\mathsf{oi}$, $\mathsf{di}$ $\mathsf{o}$
$\mathsf{di}$ $\mathsf{f}$, $\mathsf{fi}$, $=$ $\mathsf{fi}$

(a) $k=2,b=1$

(b) $k=2,b=2$

(c) $k=2,b=3$

(d) $k=4,b=1$

(e) $k=4,b=2$

(f) $k=4,b=3$

(g) $k=6,b=1$

(h) $k=6,b=3$

Figure 5: Graph instances for the interval dataset generated using the
procedure described in A.5.1. We highlight the rich variation in the topology
of the graph instance for path length $k=6$ and number of paths $b=3$ in (h)
by contrasting it with a similar graph instance for the RCC-8 dataset shown in
Figure 4(h). The target edge label between the source node and the tail node
that needs to be predicted by the model is indicated by the dotted line.

To complement the experiments in the main paper, we also introduce a dataset
based on Allen’s interval algebra [2]. 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

CLUTRR222https://github.com/facebookresearch/clutrr [33] 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 [13] 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.

GraphLog333https://github.com/facebookresearch/graphlog [34] 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:

CTP

Conditional Theorem Provers [25] are a more efficient version of Neural
Theorem Provers (NTPs [29]). 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 [23] (CTPM).
We were not able to reproduce the results from the original paper, hence we
report the results from [25] for the CLUTRR benchmark.

GNTP

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

R5

This model [22] 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.

NCRL

Neural Compositional Rule Learning [7] 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 [37] variant is also a natural baseline:

ET

Edge Transformers [5] 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:

GCN

Graph Convolutional Networks [17] 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 [33]. 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.

R-GCN

Relational GCNs [31] 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.

GAT

Graph Attention Networks [38] 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.

E-GAT

Edge-based Graph Attention Networks [34] 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.

NBFNet

Neural Bellman-Ford Networks [46] 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 [25], 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 [15] and GRUs [8].

Table 10: Optimal hyperparameters of the full (forward-backward) model on all benchmarks. |  Batch size |  Embedding dim | Epochs | Facets |  Learning 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 [25] and those with † from [22]. The results from [25] and [22] 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 [16]. 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 [41, 4].

Table 12: Results for all combinations of the individual ablations from Table 4. Facet Ablation |  Probability Ablation |  Composition Ablation |  FB Ablation |  CLUTRR Avg |  CLUTRR $k=10$ |  RCC-8 Avg |  RCC-8 $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 6: Schematic visualisation of the learned relation vectors for the
RCC-8 benchmark.

Figure 7: Schematic visualisation of the learned relation vectors for the
CLUTRR benchmark.

Figure 8: Schematic visualisation of the learned relation vectors for the
Graph-Log benchmark.

###  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 [5], to evaluate our model
as well as the baselines that were evaluated by us. The reported baseline
results that were obtained from [25] and [22] 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 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.