# R5: RULE DISCOVERY WITH REINFORCED AND RE## CURRENT RELATIONAL REASONING

**Shengyao Lu[1][∗], Bang Liu[2][,][3][∗], Keith G. Mills[1], Shangling Jui[4], Di Niu[1]**

1Department of Electrical and Computer Engineering, University of Alberta
2RALI & Mila, Universit´e de Montr´eal, [3]Canada CIFAR AI Chair
4Huawei Kirin Solution
_{shengyao,kgmills,dniu}@ualberta.ca_
bang.liu@umontreal.ca,jui.shangling@huawei.com

ABSTRACT

Systematicity, i.e., the ability to recombine known parts and rules to form new sequences while reasoning over relational data, is critical to machine intelligence. A
model with strong systematicity is able to train on small-scale tasks and generalize
to large-scale tasks. In this paper, we propose R5, a relational reasoning framework based on reinforcement learning that reasons over relational graph data and
explicitly mines underlying compositional logical rules from observations. R5 has
strong systematicity and being robust to noisy data. It consists of a policy value
network equipped with Monte Carlo Tree Search to perform recurrent relational
prediction and a backtrack rewriting mechanism for rule mining. By alternately
applying the two components, R5 progressively learns a set of explicit rules from
data and performs explainable and generalizable relation prediction. We conduct
extensive evaluations on multiple datasets. Experimental results show that R5 outperforms various embedding-based and rule induction baselines on relation prediction tasks while achieving a high recall rate in discovering ground truth rules.

1 INTRODUCTION

While deep learning has achieved great success in various applications, it was pointed out that
there is a debate over the problem of systematicity in connectionist models (Fodor & Pylyshyn,
1988; Fodor & McLaughlin, 1990; Hadley, 1994; Jansen & Watter, 2012; Dong et al., 2018). To
concretely explain systematicity (Hupkes et al., 2020), let us consider the kinship problem shown
in Figure 1. By training on the small-scale observed examples of family relationships where
the rule paths are short (in Figure 1a&b, both of the rule paths have the length of 2), our objective is to extract the underlying rules as general principles and generalize to large-scale tasks
where the rule paths are long (in Figure 1c, the rule path has the length of 3). The rules in the
training examples are a) Mother(X, Y ) ←− _Mother(X, Z), Sister(Z, Y ), b) Grandma(X, Y ) ←−_
_Mother(X, Z), Father(Z, Y ). And the necessary rule in order to conclude the relation between_
_Mary and Ann is c) Grandma(X, Y ) ←−_ _Mother(X, U_ ), Sister(U, Z), Father(Z, Y ), which does not
explicitly show up in the training examples. Successfully giving prediction in c) shows the ability
of systematicity, i.e., model’s ability to recombine known parts and rules to form new sequences.

Some attempts on the graph relational data grounded in Graph Neural Networks (Schlichtkrull et al.,
2018; Sinha et al., 2020; Pan et al., 2020) rely on learning embedding vectors of entities and relations, and have shown some capability of systematicity, However, since the rules are implicitly
encapsulated in the neural networks, these models are lack of interpretability.

Inductive Logic Programming (ILP) (Muggleton, 1992; Muggleton et al., 1996; Getoor, 2000; Yang
et al., 2017; Evans & Grefenstette, 2018) is a subfield of symbolic rule learning, which naturally
learns symbolic rules and provides interpretable explanations for labels prediction as well as being
able to generalize to other tasks. A traditional ILP system learns a set of rules from a collection of
positive and negative examples, which entails all the positives and none of the negatives. However,

_∗Equal contribution._


-----

**c** **duc** **e e a o** **p ed c o**

**a. Training graph 1** **b. Training graph 2**

**X** **_Grandma_** **A** **B** **X** **_Mother_** **B** **Mary** **?** **Ann**

**Z** **_Grandchild_** **_Father_**

**_Grandma_**

**_Mother_** **Z** **MotherSister** **_Uncle_** **_Child_** **+** **A** **Grandma** **_Father_** **_Sister_** **_ChildD_** ➔ **Jack** **_Mother_** **_Sister_** **PeterHusbandBrother** **John**

**C** **_Brother_** **Y** **Y** **_Brother_** **Sue** **Kate**

**Mother(X,Y) <- Mother(X,Z), Sister(Z,Y)** **Grandma(X,Y) <- Mother(X,Z), Father(Z,Y)** **Mother(Mary,Peter) <- Mother(Mary,Sue), Sister(Sue,Peter)**

**Grandma(Mary,Ann) <- Mother(Mary,Peter), Father(Peter,Ann)**

Figure 1: Illustration of rule extraction and relational reasoning over family relationship graphs.

these methods face the challenge that the search space of the compositional rules is exponentially
large, making it hard to scale beyond small rule sets.

Extending the idea of ILP, Neural-Symbolic Learning (Garcez et al., 2015; Besold et al., 2017)
seeks to integrate principles from neural networks learning and logical reasoning, among which
Neural Logic Machines (Dong et al., 2018; Zimmer et al., 2021) and Theorem Provers (Rockt¨aschel
& Riedel, 2017; Minervini et al., 2020a;b) aim to overcome the problems of systematicity. On one
hand, the Neural Logic Machines approximate the logic predicates using a probabilistic tensor representation, and the conclusion tensors are generated by applying the neural operators over the premise
tensors. These approaches have done a great job in reasoning the decision-making tasks including
sorting tasks, finding the shortest paths, and so on. However, in terms of the relational reasoning
tasks on graphs, Neural Logic Machines reason only the single relation prediction tasks, i.e. determining whether a single relation exists between all the queried entities or entity pairs. On the other
hand, Theorem Provers jointly learn representations and rules from data via backpropagation, given
a pre-defined task-specific rule template and a set of possible rules following the template. Theorem
Provers are able to solve and reason the relation prediction tasks instead of only determining the
existence of a single relation. However, the performance is not satisfying.

In this paper, we focus on model’s systematicity for relational reasoning over graph relational prediction tasks and present a new reasoning framework named R5, i.e., Rule discovery with Reinforced
and Recurrent Relational Reasoning, for rule induction and reasoning on relational data with strong
systematicity. R5 formulates the problem of relational reasoning from the perspective of sequential
decision-making, and performs rule extraction and logical reasoning with deep reinforcement learning equipped with a dynamic rule memory. More concretely, R5 learns the short definite clauses that
are in the form u _pi_ _pj. Since long Horn clauses (Horn, 1951) can be decomposed into short_
represented with a sequence of short definite clauses while performing decision-making, i.e.Horn clauses, a long definite clause ←− _∧_ _outcome ←−_ _p0 ∧_ _p1...pi ∧_ _pj...pk used in prediction tasks is pi_ _pj_
is replaced by u. Specifically, we make the following contributions: _∧_

First, R5 performs explicit reasoning for relation prediction via composition and achieves explainability. Instead of learning embeddings for entities and relations, (Hamilton et al., 2017;
Schlichtkrull et al., 2018; Wang et al., 2019; Pan et al., 2020) and performing implicit reasoning,
we perform explicit relational reasoning by modeling it as sequential decision-making. Specifically,
given a query (usually consists of two queried entities) and the related relationship graph, the agent
recurrently selects a relation pair ri, rj from the input graph to combine into a compound relation
_rk and updates the graph, until the target relation for the query is reached. Trained by reinforcement_
learning, the agent learns to take actions, i.e., which pair of relations to combine, given the state
representations of all possible pairs of relations.

Second, we propose a dynamic rule memory module to maintain and score candidate rules during
the training of the reasoning agent. Each item in the rule memory is a candidate rule in the format
ofmaking, the agent queries the rule memory to re-use already stored rules for reasoning, i.e., deducing rk ←− _ri, rj. ri, rj serve as the key, and rk serves as the value. In each step of decision-_
compound relations, or insert new candidate rules into it if no existing rule matches the agent’s
action. Each rule is associated with a score that indicates the confidence for the rule. The rules and
their scores in the memory are dynamically updated during training. Finally, a set of candidate rules
with scores above a threshold are kept. By recurrently applying the learned rules, R5 demonstrates
strong compositional generalization ability (i.e. systematicity) in relational reasoning tasks.

Third, rather than only taking the observed relations into account, we introduce extra invented relations into the reasoning process. For example, R5 may learn to combine r1 and r2 by a rule
_r_ _r1, r2, where r is an intentionally introduced relation. The invented relations can appear on_
_←_
both the left or right side of a rule clause. Such a design enables our model to learn intermediate
relations that do not explicitly appear in the training data to model underlying complex relations
between entities, which are sometimes necessary to discover complex rules in the relational data.


-----

|Input graph|Col2|Col3|Col4|
|---|---|---|---|
|r5 r3 r1r4 r2r2 r5 r6||||
|X r3 r7||||
||Enumerate or sampl|||
|Paths between query nod||||
|||r1 r r1 r|2 r5 r3 r7 r6 4 r5 r2 r5 r6 r|
|||r1 r r1 r|2 r5 r6 r6 4 r5 r2 r5 r3 r|

|Body 0|Body 1|Head|Score|
|---|---|---|---|
|r1 r5|r2 !"|r3 r21|4.303 -0.197|


Figure 2: Overview of the propose R5 framework for rule-inductive relational reasoning.

**Input graph** **Monte Carlo**

_r1_ _r4_ _rr2r52_ _rr35_ _r6_ _rY6_ _π1_ **tree search** _π2_

X Enumerate or sampler3 _r7_ _r1_ _r2_ _r5_ **Target**

**Paths between query nodesPath 1** r1 r2 r5 r3 r7 r6 (r1, r2) → _r3_ _r3_ _r3_ (r5, r3) → _r!21_ **relation**

... r1 r4 r5 r2 r5 r6 r6r1 r2 r5 r6 r6 r1 r2 r5 r3 r7 r6r1 r4 r5 r2 r5 r6 r6r1 r2 r5 r6 r6r1 r4 r5 r2 r5 r3 r7 r6 r3 r5 r3 r7 r6r3 r5 r6 r6 **Lookup** **Update**

Path L r1 r4 r5 r2 r5 r3 r7 r6 **Dynamic Rule Memory**

_s1_ _s2_ **Body 0 Body 1r1** **r2** **Headr3** **Score4.303** _z_

**Relation pairs to statesknown** _m_ _n_ _fθ(s)_ ... **Policy ValueNetwork** _fθ(s)_ ... **r5r3...** **r21…!"** **r21…r6** **-0.197-1.2390.789…** **Backtrack**

**relations** _m_ **rewriting**

**unknownrelations** _n_ **Remove bad rules**

_k_

**features**

_ρ1 ≈_ _π1_ _ν1 ≈_ _z_ _ρ2 ≈_ _π2_ _ν2 ≈_ _z_

Furthermore, we design a backtrack rewriting mechanism that replaces an invented relation with an
observed one when R5 finds they are actually equivalent. Our goal is to explain the observed data
with rules that are as simple as possible. Backtrack rewriting merges redundant relations and rules
to enforce the principle of Occam’s razor, which prevents overfitting and improves the robustness of
our approach.

We perform extensive evaluations based on two public relation prediction datasets, CLUTRR (Sinha
et al., 2019) and GraphLog (Sinha et al., 2020), and compare R5 with a variety of baseline methods.
The experimental results demonstrate that our approach significantly outperforms state-of-the-art
methods in terms of relation prediction accuracy and recall rate in rule discovery. Moreover, R5
exhibits a strong ability of compositional generalization and robustness to data noise. The imple[mentation is available at https://github.com/sluxsr/r5 graph reasoning.](https://github.com/sluxsr/r5_graph_reasoning)

2 PROPOSED APPROACH

Table 1: Notations

In this section, we introduce our Rule Discovery
with Reinforced and Recurrent Relational Reason- _M_ The set of known relations types
ing framework, namely R5, to solve the inductive _N_ The set of invented relations types
relation prediction problem. We first formally define _r_ a relation type
the relation prediction problem discussed in this pa- _qj_ a query
per. Let pdata(G, q, a) be a training data distribution, _Lj_ actual number of paths for qj
where G is the set of training graphs, q = (X, Y ) is _ai_ The i[th] action in in the sequence
a query, and a = r is the answer. The graphs consist _aB,i_ The i[th] relation in a’s body
of nodes in a settions in a set . X, Y N, which are connected by rela- are nodes, and r _asHi_ _aThe’s head i[th]_ current state in in the sequence
_R_ _∈N_ _∈R_ _zi_ The i[th] reward in in the sequence
is a relation. Given and the query q, the goal is to
_G_ _Drl_ Dictionary of rules
predict the correct answertask is actually program induction, which is a hard a. Relational prediction _Dcrls_ Dictionary of rules scoresan entry in Drls
problem that has been studied for many years in the _Bunkn_ Buffer of unused invented relation types
area of Inductive Logic Programming and Statistical _vi_ a score value
Relational Learning, especially for large-scale tasks

_M_ The set of known relations types
_N_ The set of invented relations types
_r_ a relation type

_qj_ a query
_L_ number of paths to sample for each query
_Lj_ actual number of paths for qj

_ai_ The i[th] action in in the sequence
_aB,i_ The i[th] relation in a’s body
_aH_ _a’s head_
_si_ The i[th] current state in in the sequence
_zi_ The i[th] reward in in the sequence

_Drl_ Dictionary of rules
_Drls_ Dictionary of rules scores
_c_ an entry in Drls
_Bunkn_ Buffer of unused invented relation types
_vi_ a score value

in noisy domains. Figure 2 shows an overview of R5. Our framework takes a relational graph as
input, and outputs the relationship between two queried entities based on extracted rules. R5 first
transforms a relation graph into a set of paths connecting the queried node (entity) pairs. After that,
it recurrently applies learned rules to merge a relation pair in the paths to form a compound relation,
until it outputs a final relation between the two queried nodes. The reasoning agent is trained with
deep reinforcement learning and MCTS, while a dynamic rule memory module is utilized to extract
rules from observations during training. The notations we used in this paper are summarized in Table 1. Note that an action a := aH (aB,0, aB,1) and a rule rl := rlH (rlB,0, rlB,1) share the
same structure, where different a and ← rl are all relations. aH and aB represent the head and body in ←
a rule, respectively. Next we introduce R5 in detail.

2.1 RECURRENT RELATIONAL REASONING

**Path sampling. To predict the relation between two entities in graphs, we preprocess the data by**
sampling paths that connect the two entities from the graph. When the total number of paths is small,
we enumerate all the paths. Otherwise, we randomly sample L paths at maximum. Each path purely


-----

consists of relations. For instance, in Figure 2, given the input graph, we can get 4 paths between
query nodes X and Y, including r1-r2-r5-r3-r7-r6 and so on.

**Reasoning as sequential decision-making. Our method solves the problem of relational reasoning**
in terms of sequential decision-making. Specifically, we train a reasoning agent based on a policy
value network combined with MCTS (Silver et al., 2017a) to recurrently reason over the extracted
relation paths. The policy value network fθ(s) is a neural network with parameters θ. It takes the
current state s as input, and outputs the action probability distribution ρ and a state value ν. MCTS
utilizes the policy network fθ(s) to guide its simulations, and outputs a vector π representing the
improved search probabilities of the available actions. The policy network (ρ, ν) = fθ(s) is then
trained to minimize the error between the predicted state value ν and the reward z received after an
episode, as well as maximize the similarity between two probability distributions ρ and π. The loss
function l is l = (z − _ν)[2]_ _−_ **_π[⊺]_** log ρ + a ∥θ∥[2], where a is a hyper-parameter.

**Action. At each step of an episode, the MCTS outputs an action (aB,0, aB,1), which is a relation**
pair denoted as aB. Furthermore, by looking up the dynamic rule memory, it obtains a : aH
(aB,0, aB,1) that contains a head relation aH to be deducted to, which means that the relation pair ←
(aB,0, aB,1) in the path will be substitute with aH . For example, in Figure 2 at step 1, MCTS outputs
By recurrently applying different actions to a path between the query nodes, it will be transformedan action a : r3 ← (r1, r2), and the path r1-r2-r5-r3-r7-r6 is transformed into r3-r5-r3-r7-r6.
into a single relation at the end of an episode.

**State. Instead of encoding the walking paths between the query nodes as other RL-based rule**
induction methods (Shen et al., 2018; Das et al., 2017; Xiong et al., 2017), we make use of the
features of the possible relations pairs at the current state. As shown in Figure 2, we define the state
_s ∈_ R[(][m][+][n][)][×][(][m][+][n][)][×][k] as the representation of all the possible relations pairs among the current
paths, where m is the number of observed relations, n is the number of invented relations we assumed, and k is the dimension of features of each relation pair. As previously discussed, a relation
pair may be deducted to an invented relation r _N_ . Besides, r can be paired with another re_∗_ _∈_ _∗_
lation r, and maybe further deducted to another invented relation r[′]
_∗_ _[∈]_ _[N]_ [. Our state space design]
enables us to represent such complicated rules with the invented relations that serve as intermediate
predicates, which is essential to model complex relational data. n invented relations are allowed in
our design, where n depends on the complexity of input. An example is presented in Appendix A.4.

Even if sometimes the input data can be explained by rules without invented relation, the invented
relations in our state design can actually help to speed up model training. For example, when we
observe that a relation pair r1 and r2 shows up frequently in the training data, we can sample an
invented relation r∗ as the head, and form a candidate rule r∗ _←_ (r1, r2). In this way, our model
learns to merge r1 and r2 quickly without the need to figure out what exactly r is. The value of
_∗_
_r_ will be inferred by our model with Backtrack Rewriting mechanism, which we will introduce in
_∗_
more detail later. Without these invented relations, a reasoning agent has to infer what exactly r is
_∗_
at an early state, otherwise it cannot proceed to merge the relation pairs in a path correctly. Thus,
the invented relations actually serve as a buffering mechanism to allow an agent to learn “what to
merge” first, rather than inferring the exact rule at an early stage.

The features we utilized to represent each relation pair can be summarized into two groups. The first
group includes the general and statistical features of the pair, such as the number of occurrences, the
index of the most viewed position among the paths, the number of occurrences at the most viewed
position, and the types of the two relations consist the pair. The other group includes the rulesrelated features, such as whether the relation pair is in the obtained rules, whether the relation pair
consists of two known relations, whether the rule head is a known relation if the pair is in the rules
memory, and the score of the corresponding rule if the pair is in the rules memory.

**Reward. During an episode, actions are applied to a relation path recurrently, until the path is**
deducted to a single relation r, and a reward zT 1, 0, +1 will be assigned to all the states in
this episode. If r is an known relation, but is not the target relation, ∈{− _}_ _zT = −1. If r is an invented_
relation, zT = 0. If r is the target relation, zT = 1.

2.2 RULE INDUCTION WITH A DYNAMIC RULE MEMORY

The above recurrent reasoning agent enables us to predict the relation between two queried nodes
more efficiently than only using MCTS. To extract rules from observed data, we further design


-----

a dynamic rule memory module which stores and updates candidate rules and interact with the
reasoning agent during training. Our memory design can be interpreted as two hash tables with the
same keys: one hash table Drl in the form of (rB0, rB1) : rh is used to memorize the candidate
rules, and another hash table Drls in the form of (rB0, rB1) : score to track the rule scores. Note
that in Figure 2, we union the two tables as they share the same keys. A newly added rule will have
an initial score of 0. In Figure 2, a rule (r3) (r1, r2) was stored in the hash tables, where the
_←_
rule body (r1, r2) is the key, and the rule head r3 and score 4.303 are the values in Drl and Drls,
respectively.

We utilize a buffer Bunkn to store the n intermediate invented relations as described in Sec. 2.1.
When an invented relation type r _N is used to complete a rule, it will be removed from Bunkn. If_
_∈_
_r is freed from the rule memory Drl, then it will be added to Bunkn again._

Recall that at each time step the MCTS will return an action body aB. In order to complete the
action, we get the action head aH by

_aH =_ _Drl[aB],_ if aB ∈ _Drl,_ (1)
RandomSample(Bunkn), otherwise.


Then, if aB /∈ _Drl, we update the memory Drl with Drl[aB] = aH_, and compute the score ca by

_v0,_ _aB_ _Drl,_ _r_ _a, r_ _M,_
_∈_ _∀_ _∈_ _∈_
_v1,_ _aB_ _Drl, aH_ _M,_ _r_ _aB, r_ _N,_

 _∈_ _∈_ _∃_ _∈_ _∈_

_ca =_ vv32,, _aaBB / ∈_ _DDrlrl,, aHr_ _∈aN,B, r_ _M,_ (2)

_∈_ _∀_ _∈_ _∈_
_v4,_ _aB /_ _Drl,_ _r_ _aB, r_ _N,_

where v0 > v1 > 0 > v2 > v3 > v4. We can see that an action consisting of three known relations∈ _∃_ _∈_ _∈_
will receive the largest positive score, and an action with an invented relation in the head and at least
an invented relation in the body will receive the smallest negative score. This way we penalize the
usage of invented relations to prevent overfitting.

After extracted candidate rules, at the end of each

**Algorithm 1 Backtrack Rewriting**

training episode, we further utilize Backtrack
Rewriting to consolidate all the candidate rules 1: series Input: Drl, Bunkn, last action aT, target
and replace invented relations in a rule with ob- relation y
served relations if we found they are equivalent. 2: r = Drl[aT B]

3: if r _N then_

Algorithm 1 describes our Backtrack Rewriting _∈_

4: **for aB in Drl do**

mechanism for updating the rule memory Drl. 5: **if Drl[aB] = r then**
Specifically, assume the action sequence we have 6: _Drl[aB] = y_
taken in an episode isthe head relation of the last action {a0, a1, ...at a, ...aT isT } r, and := 7:8: **fora aHB = in D Drlrl[ doaB]**
_aT H = Drl[aT B]. As y is the target relation,_ 9: **if aB,0 = r and aB,1 = r then**
we can backtrack r in Drl, and replace all its oc- 10: _key = (y, y)_
currences with y. Before updating Drl[aT B], we 11: **else if aB,0 = r then**
update the corresponding entries in Drls of the 12: _key = (y, aB,1)_

13: **else if aB,1 = r then**

actions _a0, a1, ...at, ...aT_ in the episode by
_{_ _}_ 14: _key = (aB,0, y)_

_cat + vT pos,_ _r = y,_ 15: **else**

16: _continue_

_Drls[atB] =_ vT neg, _r ∈_ _M, r ̸= y,_ 17: **if key /** _Drl or Drl[key]_ _N then_

cat _,_ otherwise, 18: delete∈ aB from Drl _∈_

(3) 19: _Drl[key] = aH_
where r := Drl[aT B], and vT neg < 0 < vT pos 20: **else**
are the episode end scores. Next, we decay the 21: delete aB from Drl

22: remove r from Bunkn

scoresepisodes by: Drls[aB] of all the rules aH ← _aB over_

_Drls[aB] =_ _DDrlsrls[[aaBB](1](1 + ϵϵ)),,_ _DDrlsrls[[aaBB]] > < 0 0,,_ (4)
 _−_

where ϵ is a small positive decay factor. Thus, the score of a rule that is not accessed over training
episodes will decrease.


-----

Table 2: Results on CLUTRR, trained on stories of
lengths {2, 3} and evaluated on stories of lengths
_{4, ..., 10}._ [[∗]] means the numbers are taken from
CTP’s paper. [s] means fine-tuned on short stories.

**4Hops** **5Hops** **6Hops** **7Hops** **8Hops** **9Hops 10Hops**

R5 .98±.02 .99±.02 .98±.03 .96±.05 .97±.01 .98±.03 .97±.03

CTP[∗]L .98±.02 .98±.03 .97±.05 .96±.04 .94±.05 .89±.07 .89±.07
CTP[∗]A **.99±.02 .99±.01 .99±.02 .96±.04 .94±.05 .89±.08 .90±.07**
CTP[∗]M .97±.03 .97±.03 .96±.06 .95±.06 .93±.05 .90±.06 .89±.06

GNTP[∗] .49±.18 .45±.21 .38±.23 .37±.21 .32±.20 .31±.19 .31±.22
GAT[∗]s .91±.02 .76±.06 .54±.03 .56±.04 .54±.03 .55±.05 .45±.06
GCN[∗]s .84±.03 .68±.02 .53±.03 .47±.04 .42±.03 .45±.03 .39±.02

RNN[∗]s .86±.06 .76±.08 .67±.08 .66±.08 .56±.10 .55±.10 .48±.07
LSTM[∗]s [.98][±][.04 .95][±][.03 .88][±][.05 .87][±][.04 .81][±][.07 .75][±][.10 .75][±][.09]
GRU[∗]s .89±.05 .83±.06 .74±.12 .72±.09 .67±.12 .62±.10 .60±.12

CNNH[∗]s [.90][±][.04 .81][±][.05 .69][±][.10 .64][±][.08 .56][±][.13 .52][±][.12 .50][±][.12]
CNN[∗]s .95±.02 .90±.03 .89±.04 .80±.05 .76±.08 .69±.07 .70±.08
MHA[∗]s .81±.04 .76±.04 .74±.05 .70±.04 .69±.03 .64±.05 .67±.02


Table 3: Results on CLUTRR, trained on stories of
lengths {2, 3, 4} and evaluated on stories of lengths
_{5, ..., 10}._ [[∗]] means the numbers are taken from
CTP’s paper. [s] means fine-tuned on short stories.

**5 Hops** **6 Hops** **7 Hops** **8 Hops** **9 Hops** **10 Hops**

R5 .99±.02 .99±0.4 **.99±.03** **1.0±.02** **.99±.02** **.98±.03**

CTP[∗]L .99±.02 .98±.04 .97±.04 .98±.03 .97±.04 .95±.04
CTP[∗]A .99±.04 .99±.03 .97±.03 .95±.06 .93±.07 .91±.05
CTP[∗]M .98±.04 .97±.06 .95±.06 .94±.08 .93±.08 .90±.09

GNTP[∗] .68±.28 .63±.34 .62±.31 .59±.32 .57±.34 .52±.32

GAT[∗]s .99±.00 .85±.04 .80±.03 .71±.03 .70±.03 .68±.02
GCN[∗]s .94±.03 .79±.02 .61±.03 .53±.04 .53±.04 .41±.04

RNN[∗]s .93±.06 .87±.07 .79±.11 .73±.12 .65±.16 .64±.16
LSTM[∗]s .98±.03 .95±.04 .89±.10 .84±.07 .77±.11 .78±.11
GRU[∗]s .95±.04 .94±.03 .87±.08 .81±.13 .74±.15 .75±.15

CNNH[∗]s .99±.01 .97±.02 .94±.03 .88±.04 .86±.05 .84±.06
CNN[∗]s **1.0±.00** **1.0±.01** .98±.01 .95±.03 .93±.03 .92±.04
MHA[∗]s .88±.03 .83±.05 .76±.04 .72±.04 .74±.05 .70±.03


Finally, when a rule score is less than a negative threshold σ, the corresponding rule will be omitted
from the rule memory. We recursively check the rule memory to remove all the candidate rules
that contain the omitted rule’s head aHbad _N_ . Thus, the bad rules will be gradually removed
from the rule memory. Bunkn and Drls will be updated accordingly. Besides, when the invented ∈
relations buffer Bunkn is empty, we will look up the rules scores hash table Drls to find the rule
_arules inHbad ← Drla that containBbad that has the smallest rule score, where aHbad will be removed, and aHbad aHbad will be added back to ∈_ _N_ . Then all the corresponding Bunkn.

3 EXPERIMENTS

We evaluate R5 on two datasets: CLUTRR (Sinha et al., 2019) and GraphLog (Sinha et al., 2020),
which test the logical generalization capabilities. We compare with embedding-based and rule induction baselines for both CLUTRR and GraphLog.

3.1 SYSTEMATICITY ON CLEAN DATA

We first evaluate R5 on the CLUTRR dataset and demonstrate its Systematicity. In other words, we
test whether R5 can perform reasoning over graphs with more hops than the training data.

**Dataset and Experimental Setup. CLUTRR (Sinha et al., 2019) is a dataset for inductive rea-**
soning over family relations. Paragraphs describing family relationships are encoded as a large set
of graphs, where family members are modeled as nodes, and the relations in between are modeled
as edges. The goal is to infer the relation between two family members, which is not explicitly
mentioned in the paragraph. The train set contains graphs with up to 3 or 4 edges, and the test set
contains graphs with up to 10 edges. The train and test splits do not share the same set of entities.

As baselines, we evaluate several embedding-based models (Veliˇckovi´c et al., 2017; Kipf & Welling,
2017; Schuster & Paliwal, 1997; Hochreiter & Schmidhuber, 1997; Chung et al., 2014; Kim, 2014;
Kim et al., 2015; Vaswani et al., 2017) and several neuro-symbolic models that consists the rule
induction baselines (Minervini et al., 2020a;b). The results of the baselines are taken from Minervini
et al. (2020b). Due to limited space, for the baselines other than CTPs and GNTPs, we only present
the results fine-tuned on short stories. The comparisons with these baselines fine-tuned on long
stories are provided in the Appendix C, and none of them can beat R5.

**Results. Table 10, 11 present the prediction accuracy on two datasets pulished by Sinha et al. (2019).**
We call the two datasets CLUTRRk 2,3 and CLUTRRk 2,3,4, as they train on graphs with 2, 3
_∈{_ _}_ _∈{_ _}_ _{_ _}_
edges while test on graphs with {4, ..., 10} edges, and train on graphs with {2, 3, 4} edges while test
on graphs with {5, ..., 10} edges, respectively. As shown in both tables, R5 either outperforms all
the baselines or reach the best results in both metrics. In particular, R5 has better generalization
capability than CTPs. For both datasets, the prediction accuracy of CTPs goes down when evaluated
on longer stories. In contrast, R5 still predicts successfully on longer stories without significant
performance degradation. This demonstrates the strong compositional generalization ability of R5,
in terms of systematicity, productivity, substitutivity, and localism (Hupkes et al., 2020).

3.2 SYSTEMATICITY ON NOISY DATA

In Section 3.1, we test model performance with no bad cases in data. A bad case is a logically wrong
example. For example, the mother of a sister is a father is a bad case. Apart from the compositional


-----

Table 4: Results of reasoning on the selected GraphLog datasets (worlds). ND: number of distinct relations
sequences that traverse between query nodes; ARL: Average resolution length. [[∗]] means the numbers are
taken from the original papers. [[†]] means we rerun the methods using the released source code.

|World ID ND ARL|E-GAT∗ Accuracy|R-GCN∗ Accuracy|CTP† Accuracy Rules Recall|R5 Accuracy Rules Recall|
|---|---|---|---|---|
|World 2 157 3.21 World 3 189 3.63 World 13 149 3.58 World 17 147 3.16 World 30 177 3.51|0.412 0.473 0.453 0.347 0.426|0.347 0.451 0.347 0.181 0.357|0.685±0.03 0.80±0.05 0.624±0.02 0.85±0.00 0.696±0.01 0.90±0.00 0.789±0.04 0.85±0.00 0.658±0.01 0.80±0.00|0.755±0.02 1.0±0.00 0.791±0.03 1.0±0.00 0.895±0.00 1.0±0.00 0.947±0.02 1.0±0.00 0.853±0.01 0.95±0.00|
|World 6 249 5.06 World 7 288 4.47 World 8 404 5.43 World 11 194 4.29 World 32 287 4.66|0.536 0.613 0.643 0.552 0.700|0.498 0.537 0.569 0.456 0.621|0.533±0.03 0.85±0.00 0.513±0.03 0.75±0.05 0.545±0.02 0.70±0.00 0.553±0.01 0.85±0.00 0.581±0.04 0.95±0.00|0.687±0.05 0.9±0.00 0.749±0.04 0.95±0.00 0.671±0.03 0.95±0.00 0.803±0.01 1.0±0.00 0.841±0.03 1.0±0.00|



generalization ability, it is also important to assess how effectively a model can discover all underlying rules. The existing relational reasoning works only show that they are able to improve relation
prediction with some learned rules, without an evaluation on whether the extracted rules are exhaustive. GraphLog, the dataset we use in this subsection, provides the ground rules used to create each
logical world, so we evaluate this ability by the recall rate of ground truth rules.

**Dataset and Experimental Setup. Graphlog (Sinha et al., 2020) is a benchmark suite designed to**
evaluate systemeticity. It contains logical worlds where each world contains graphs that are created
using a different set of ground rules. Similar to CLUTRR, the goal is to infer the relation between a
queried node pair. However, GraphLog is much more challenging than CLUTRR. Firstly, it contains
more bad examples than CLUTRR does. Secondly, the graphs in both train sets and test sets of
Graphlog contain more edges; it is normal that there are more than 10 edges in a graph. Thirdly, the
underlying compositional rules may not be shared between a train set and its corresponding test set.
The above facts make GraphLog a more challenging dataset for rule induction.

In the evaluations on GraphLog, we consider E-GAT (Sinha et al., 2020) and R-GCN (Schlichtkrull
et al., 2018) as the embedding-based baselines, and CTPs (Minervini et al., 2020b) as the rule induction baseline. For E-GAT and R-GCN, we use the results in (Sinha et al., 2020). For CTPs, we
use the implementation publicly provided by the author with the best configurations. In addition,
we use the core generator provided by (Sinha et al., 2020), which is used to produce the GraphLog
datasets, to generate three new worlds: Re 0, Re 1, Re 2. The new worlds have less training data and
more distinct relations sequences. We aim to test how the rule induction models perform when only
a small amount of training samples are given. We divide the 57 worlds in Graphlog into two groups
in terms of the average resolution length (ARL), where the resolution length is the number of nodes
traversed in the correct path between the queried nodes. Figure 1a,b are instances of resolution
lengths of 2, and Figure 1c is an instance of resolution length of 3. We then randomly pick 5 worlds
with an ARL less than 4, and 5 other worlds with an ARL greater than 4 to conduct experiments on.

**Results. Table 4 shows the results on 10 selected worlds (datasets) published by (Sinha et al.,**
2020). When the ARL is larger, the dataset becomes noisier and contains more bad cases. In terms
of relation prediction accuracy, R5 significantly outperforms both the embedding-based and rule
induction baselines over all 10 datasets. In terms of the ground rule recall rate, R5 also consistently
outperforms CTP, and even reaches full recall rate on some datasets.

At a closer inspection, the two GNN models perform poorly for ARL < 4. A dataset with a smaller
ARL indicates the graphs are very simple, and models that represent the graph structure based on
message-passing have not enough information to learn from. As for datasets with ARL > 4, the
graph structures become more complex, the GNNs are able to aggregate more information to each
node from the neighbors. Thus, the performance of GNNs improves on these datasets. However,
CTP performs worse than GNNs in this case, due to two reasons. On one hand, the increasing
amount of bad cases influences the rule recall rate, making CTP less confident on some correct
rules. On the other hand, it is hard for CTP to generalize to complex data.

Table 5 presents the results for the three new datasets created that have fewer training samples. In
particular, resolution lengths of graphs in Re 0 can be up to 10, while resolution lengths of graphs in
Re 1 can be up to 15. Re 2 requires the models to train on graphs with resolution lengths of {3, ..., 5},
and to test on graphs with resolution lengths of {2, ..., 7}. As shown in the table, R5 achieves better
results than CTP when the amount of training facts is very small. And we can observe from Re 0
and Re 1 that as the resolution length becomes longer, CTP has a sharp performance drop on the
prediction accuracy, whereas R5 maintains relatively high accuracy and full ground rule recall rate.


-----

Table 5: Results on new datasets generated using GraphLog generator. ND: number of distinct relations sequences that traverse between query nodes; ARL: Average resolution length. RL: resolution length. ACC:

|We rerun CTPs using the released source|code.|Col3|
|---|---|---|
|Data set ND ARL Train RL Test RL|CTP ACC Recall|R5 ACC Recall|
|Re 0 631 3.90 2∼10 2∼10 Re 1 736 5.19 2∼15 2∼15 Re 2 725 3.81 3∼5 2∼7|0.425±0.03 0.75±0.00 0.190±0.06 0.75±0.00 0.359±0.02 0.30±0.05|0.665±0.06 1.0±0.00 0.575±0.02 1.0±0.00 0.446±0.04 0.70±0.00|



In the train set of Re 2, there is no simple data. Simple data refers to a sample whose resolution
length is 2, and the ground rules can be naturally collected from such data. However, in Re 2, as we
train on samples of lengths {3, ..., 5} and evaluate on samples of lengths {2, ..., 7}, the models have
to infer the ground rules. As is shown, R5 can still extract most of the ground rules while CTP fails.

3.3 ABLATION STUDIES


**Policy Value Network. As stated earlier, the pol-**
icy value network is trained to sequentially decide which edge pair we should select to do a
deduction. Without training this network, only
MCTS will help us to make the decisions, whose
action distribution is given by the numbers of visits at all possible nodes. From Table 6 we acquire
that although we are still able to recall the ground
rules with rules extraction, the prediction accuracy drastically decreases since the paths are not
deducted in the correct order.


Table 6: Ablation study of R5. PVN: policy value

|network.|Col2|Col3|Col4|
|---|---|---|---|
||World 2 ACC Recall|World 6 ACC Recall|Re 2 ACC Recall|
|R5 R5 w/o PVN R5, n=1|0.755 1.0 0.502 1.0 0.661 1.0|0.687 0.9 0.407 0.9 0.595 0.85|0.446 0.70 0.208 0.60 0.349 0.70|




**Pre-allocated Invented Relations.** We pre- 0.4
allocate n invented relations to allow a relation Test Accuracy0.2 0.3
pair to deduct to an intermediate predicate when 0.1 Rules Recall Rate0.2 R5R5_w/o_PVN
it still is unclear whether the relation pair can give 0.1 R5, n=1
us a correct rule. And the intermediate predicate 0 2 Training Epoch4 6 8 0 2 Training Epoch4 6 8
will be tracked during the training until it is iden- Figure 3: Ablation study of R5 on Re 2 in terms of

Re 2 Test Accuracy vs. epochs Re 2 Rules Recall vs. epochs

0.7

0.4

0.6

0.3 0.5

0.4

0.2 0.3

Test Accuracy

0.1 Rules Recall Rate0.2 R5R5_w/o_PVN

0.1 R5, n=1

0 2 4 6 8 0 2 4 6 8

Training Epoch Training Epoch

tified as a known relation. Refer to Table 6, when test accuracy and rules recall rate.
we only allow a single invented relation, the prediction accuracy will drop, which indicates that the extra hidden relations improve the model’s capability of learning complicated graphs. And in Re 2, where the training samples’ resolution lengths
are greater than 2, the results catastrophically decrease. We evaluate the prediction accuracy and
rules recall each training epoch. As shown in Figure 3, the model loses the induction ability at the
early stage with only one intermediate predicate allowed. Once the first ground rule is extracted,
more will be gradually learned, and finally the R5 with a single hidden predicate reaches the same
rules recall rate as R5 with 50 hidden predicates. This figure proves that a number of pre-allocated
invented relations can not only help to learn complicated graphs, but also speed up the convergence.

4 RELATED WORK

**Graph Neural Networks and General Relation Prediction Tasks. Graph Convolutional Networks**
(GCNs) (Bruna et al., 2014; Li et al., 2016; Defferrard et al., 2016; Kipf & Welling, 2017) is a
family of message-passing neural architectures designed for processing graph data. While most
GCNs operate only with the entities and binary links, some recent works (Schlichtkrull et al., 2018;
Sinha et al., 2020; Pan et al., 2020) are applicable on relational data where the relation types (i.e.,
edge types) between entities (i.e., vertices) matters. The GCN-based models can capture lifted rules
defined on the sets of entities and have presented good results on the node classification tasks (Sinha
et al., 2020). However, since the lifted rules are implicitly encapsulated in the neural networks, these
models are lack of interpretability.

**ILP, Neural-Symbolic Learning and Systematicity. Inductive Logic Programming (ILP) (Mug-**
gleton, 1992; Muggleton et al., 1996; Getoor, 2000; Evans & Grefenstette, 2018) is a subfield of
symbolic rule learning, which learns logic rules derived from a limited and predefined set of rule
templates. A traditional ILP system learns a set of rules from a collection of examples, which entails
all the positives and none of the negatives. Such a system naturally provides interpretable explanations for labels prediction as well as being able to generalize to new tasks but is hard to scale up to


-----

the exponentially large space of compositional rules (Evans & Grefenstette, 2018; Yang et al., 2017)
as the number of relations and entities increases. On the other hand, the relational path assumption
suggests that there usually exist fixed-length paths of relations linking the set of terms (entities) that
satisfy a target concept (Mooney, 1992). Under this assumption, Cropper & Muggleton (2015) reduces the complexity of individual rules with the latent predicates. Statistical unfolded logic (SUL)
(Dai & Zhou, 2016) searches for a relational feature set from relational space and grounded relational paths, such that statistical learning approaches are applied to extract weighted logic rules.
Using a statistical discriminative model, SUL also enables predicate invention.

Neural-Symbolic models (Garcez et al., 2015; Besold et al., 2017) seek to integrate principles from
neural networks learning and logical reasoning, among which Neural Logic Machines (NLMs)
(Dong et al., 2018; Zimmer et al., 2021) and Theorem Provers (Rockt¨aschel & Riedel, 2017; Minervini et al., 2020a;b) attempt to overcome the problems of systematicity. The NLMs successfully
show the systematicity for up to 50 entities on some selected decision-making tasks. However, in
terms of relational reasoning on graphs, NLMs only consider the binary classification tasks. Although the links in the graphs have various types, for each task, NLMs predict the existence of a
single relation type instead of concluding which type the relation is when there is one. When performing general relation prediction, NLMs have to create a number of tasks where each task predicts
for a single relation type, making the total number of tasks grows as the number of relation types
increases. As a result, NLMs are hard to scale up on relation prediction tasks.

Theorem Provers, in particular the Conditional Theorem Provers (CTPs) (Minervini et al., 2020a;b),
are capable of the relation prediction problem without the need to create a number of tasks. CTPs
use templates equipped with a variety of selection modules to reformulate a given goal into subgoals, and jointly learn representations and rules from data. However, the depth of the templates
(refer to hops in their code) is limited, which influences the number of parameters of the model. In
contrast, as explained in Section 2.1, R5 is able to handle the complicated rules where the allowed
rule depth is much larger. That is because the rule depth is only related to the number of steps in an
episode of the sequential decision-making process of R5, which does not touch the number of model
parameters. We have also presented in Section 3.1 and 3.2 that R5 gives better relation prediction
results on the systematicity tasks and shows better performance in terms of the rules recall.

**Relational Reasoning for Knowledge Base Completion. Many recent works propose a variety of**
relational reasoning models for efficient Knowledge Base Completion (KBC), which differs from
what we are focusing on. These works include the embedding-based methods (Sun et al., 2019;
Trouillon et al., 2017; Dettmers et al., 2017; Bordes et al., 2013), GNN-like methods (Teru et al.,
2020; Mai et al., 2020), Neural-Symbolic Methods (Rockt¨aschel & Riedel, 2017; Minervini et al.,
2020a;b; Qu et al., 2021), and RL Path-finding Agents (Xiong et al., 2017; Chen et al., 2018; Das
et al., 2017; Lin et al., 2018; Shen et al., 2018). Most of them are designed for the transductive
aspects instead of systematicity. Moreover, the KBC tasks can be treated as entity sorting problems,
where the objective is ranking the tail entities given a query (h, r, ?) with head entity h and the
relation r are given (Wang et al., 2021). KBC is different from the general relation prediction tasks
investigated in this paper. It is also non-trivial to extend our research to tackle KBC tasks. Since the
relation r is given in the query, rather than deciding the relation type between a head entity h and a
candidate tail t* like what R5 might do, a better choice would be directly determining whether the
single relation r exists between h and t* like what NLMs might be able to do. Therefore, we do not
discuss R5’s performance on KBC tasks in this paper. Although non-trivial, surely it is worth trying
to extend the main structure of R5 to KB. We leave this task to future works.

5 CONCLUSION

We propose R5, a framework that models relational reasoning as sequential decision-making. Our
framework performs explicit and explainable relational reasoning with a design of state and action
spaces based on pairs of relations. Besides, R5 performs rule induction with a dynamic rule memory
module, which is updated during the training of an agent. We further incorporate hidden (invented)
relations in our state and action spaces to help accelerate model training as well as improve rule
mining. R5 exhibits high accuracy for relation prediction and a high recall rate for rule discovery, as
has been demonstrated by extensive experimental results. We also show that R5 has a strong ability
of systematicity and is robust to data noise.


-----

REFERENCES

David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002.
[Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.](http://www.stat.berkeley.edu/$\sim $aldous/RWG/book.html)
[edu/$\sim$aldous/RWG/book.html.](http://www.stat.berkeley.edu/$\sim $aldous/RWG/book.html)

Tarek R Besold, Artur d’Avila Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pascal Hitzler, Kai-Uwe K¨uhnberger, Luis C Lamb, Daniel Lowd, Priscila Machado Vieira Lima,
et al. Neural-symbolic learning and reasoning: A survey and interpretation. _arXiv preprint_
_arXiv:1711.03902, 2017._

Antoine Bordes, Nicolas Usunier, Alberto Garc´ıa-Dur´an, J. Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, 2013.

Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally
connected networks on graphs. In Yoshua Bengio and Yann LeCun (eds.), 2nd International
_Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014,_
_Conference Track Proceedings, 2014._

Wenhu Chen, Wenhan Xiong, Xifeng Yan, and William Yang Wang. Variational knowledge graph
reasoning. Proceedings of the 2018 Conference of the North American Chapter of the Association
_for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), 2018._
[doi: 10.18653/v1/n18-1165. URL http://dx.doi.org/10.18653/v1/N18-1165.](http://dx.doi.org/10.18653/v1/N18-1165)

Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of
gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555, 2014.

Andrew Cropper and Stephen H Muggleton. Logical minimisation of meta-rules within metainterpretive learning. In Inductive Logic Programming, pp. 62–75. Springer, 2015.

Andrew Cropper, Sebastijan Dumanˇci´c, and Stephen H. Muggleton. Turning 30: New ideas in
inductive logic programming. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth Inter_national Joint Conference on Artificial Intelligence, IJCAI-20, pp. 4833–4839. International Joint_
Conferences on Artificial Intelligence Organization, 7 2020. doi: 10.24963/ijcai.2020/673. URL
[https://doi.org/10.24963/ijcai.2020/673. Survey track.](https://doi.org/10.24963/ijcai.2020/673)

Wang-Zhou Dai and Zhi-Hua Zhou. Statistical unfolded logic learning. In Geoffrey Holmes
and Tie-Yan Liu (eds.), Asian Conference on Machine Learning, volume 45 of Proceedings
_of Machine Learning Research, pp. 349–361, Hong Kong, 20–22 Nov 2016. PMLR._ URL
[https://proceedings.mlr.press/v45/Dai15.html.](https://proceedings.mlr.press/v45/Dai15.html)

Zhou Zhihua Dai Wangzhou. A survey on inductive logic programming. _Journal of computer_
_Research and Development, 56(1):138, 2019._

Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for a walk and arrive at the answer: Reasoning
over paths in knowledge bases using reinforcement learning, 2017.

Micha¨el Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on
graphs with fast localized spectral filtering. In Daniel D. Lee, Masashi Sugiyama, Ulrike von
Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing
_Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-_
_10, 2016, Barcelona, Spain, pp. 3837–3845, 2016._

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d
knowledge graph embeddings, 2017.

Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural logic
machines. In International Conference on Learning Representations, 2018.

Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of
_Artificial Intelligence Research, 61:1–64, 2018._


-----

Jerry Fodor and Brian P. McLaughlin. Connectionism and the problem of systematicity: Why
smolensky’s solution doesn’t work. _Cognition, 35(2):183–204, May 1990._ ISSN 00100277. doi: 10.1016/0010-0277(90)90014-b. [URL http://dx.doi.org/10.1016/](http://dx.doi.org/10.1016/0010-0277(90)90014-B)
[0010-0277(90)90014-B.](http://dx.doi.org/10.1016/0010-0277(90)90014-B)

Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-2):3–71, Mar 1988. ISSN 0010-0277. doi: 10.1016/0010-0277(88)90031-5.
[URL http://dx.doi.org/10.1016/0010-0277(88)90031-5.](http://dx.doi.org/10.1016/0010-0277(88)90031-5)

Jianfeng Gao, Michel Galley, and Lihong Li. Neural approaches to conversational ai. In Proceedings
_of the 56th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts,_
pp. 2–7, 2018.

Artur d’Avila Garcez, Tarek R Besold, Luc De Raedt, Peter F¨oldiak, Pascal Hitzler, Thomas Icard,
Kai-Uwe K¨uhnberger, Luis C Lamb, Risto Miikkulainen, and Daniel L Silver. Neural-symbolic
learning and reasoning: contributions and challenges. In 2015 AAAI Spring Symposium Series,
2015.

Lise Getoor. Learning probabilistic relational models. _Abstraction, Reformulation, and Ap-_
_proximation, pp. 322–323, 2000._ ISSN 0302-9743. doi: 10.1007/3-540-44914-0 25. URL
[http://dx.doi.org/10.1007/3-540-44914-0_25.](http://dx.doi.org/10.1007/3-540-44914-0_25)

ROBERT F. Hadley. Systematicity in connectionist language learning. _Mind&Language, 9(3):_
247–272, September 1994. ISSN 1468-0017. doi: 10.1111/j.1468-0017.1994.tb00225.x. URL
[http://dx.doi.org/10.1111/J.1468-0017.1994.TB00225.X.](http://dx.doi.org/10.1111/J.1468-0017.1994.TB00225.X)

William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large
graphs, 2017.

Sepp Hochreiter and J¨urgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735–1780, 1997.

Alfred Horn. On sentences which are true of direct unions of algebras. Journal of Symbolic Logic,
[16(1):14–21, Mar 1951. ISSN 1943-5886. doi: 10.2307/2268661. URL http://dx.doi.](http://dx.doi.org/10.2307/2268661)
[org/10.2307/2268661.](http://dx.doi.org/10.2307/2268661)

Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: how
do neural networks generalise? Journal of Artificial Intelligence Research, 67:757–795, 2020.

Peter A. Jansen and Scott Watter. Strong systematicity through sensorimotor conceptual grounding: an unsupervised, developmental approach to connectionist sentence processing. Connection
_Science, 24(1):25–55, Mar 2012. ISSN 1360-0494. doi: 10.1080/09540091.2012.664121. URL_
[http://dx.doi.org/10.1080/09540091.2012.664121.](http://dx.doi.org/10.1080/09540091.2012.664121)

Yoon Kim. Convolutional neural networks for sentence classification. Proceedings of the 2014
_Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014. doi: 10._
[3115/v1/d14-1181. URL http://dx.doi.org/10.3115/v1/D14-1181.](http://dx.doi.org/10.3115/v1/D14-1181)

Yoon Kim, Yacine Jernite, David Sontag, and Alexander M. Rush. Character-aware neural language
models, 2015.

Thomas N. Kipf and Max 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, 2017._

Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. Gated graph sequence neural
networks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning
_Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceed-_
_ings, 2016._

Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with
reward shaping. Proceedings of the 2018 Conference on Empirical Methods in Natural Language
_[Processing, 2018. doi: 10.18653/v1/d18-1362. URL http://dx.doi.org/10.18653/](http://dx.doi.org/10.18653/v1/D18-1362)_
[v1/D18-1362.](http://dx.doi.org/10.18653/v1/D18-1362)


-----

Sijie Mai, Shuangjia Zheng, Yuedong Yang, and Haifeng Hu. Communicative message passing for
inductive relation reasoning, 2020.

Pasquale Minervini, Matko Boˇsnjak, Tim Rockt¨aschel, Sebastian Riedel, and Edward Grefenstette.
Differentiable reasoning on large knowledge bases and natural language. In Proceedings of the
_AAAI Conference on Artificial Intelligence, volume 34, pp. 5182–5190, 2020a._

Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rockt¨aschel.
Learning reasoning strategies in end-to-end differentiable proving. In ICML, volume 119 of Pro_ceedings of Machine Learning Research, pp. 6938–6949. PMLR, 2020b._

Raymond J Mooney. Learning relations by pathfinding. In AAAI-92: Proceedings, Tenth National
_Conference on Artificial Intelligence; July 12-16, 1992, volume 10, pp. 50. Aaai Press, 1992._

Stephen Muggleton. Inductive logic programming. Number 38. Morgan Kaufmann, 1992.

Stephen Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning of
higher-order dyadic datalog: predicate invention revisited. Machine Learning, 100:49–73, 01
2015.

Stephen Muggleton et al. Stochastic logic programs. Advances in inductive logic programming, 32:
254–264, 1996.

Liangming Pan, Yuxi Xie, Yansong Feng, Tat-Seng Chua, and Min-Yen Kan. Semantic graphs
for generating deep questions. In Proceedings of the 58th Annual Meeting of the Association
_for Computational Linguistics, pp. 1463–1475, Online, July 2020. Association for Computa-_
[tional Linguistics. doi: 10.18653/v1/2020.acl-main.135. URL https://www.aclweb.org/](https://www.aclweb.org/anthology/2020.acl-main.135)
[anthology/2020.acl-main.135.](https://www.aclweb.org/anthology/2020.acl-main.135)

Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. {RNNL}ogic:
Learning logic rules for reasoning on knowledge graphs. In International Conference on Learning
_[Representations, 2021. URL https://openreview.net/forum?id=tGZu6DlbreV.](https://openreview.net/forum?id=tGZu6DlbreV)_

Tim Rockt¨aschel and Sebastian Riedel. End-to-end differentiable proving, 2017.

Eric Salvat and Marie-Laure Mugnier. Sound and complete forward and backward chainings of
graph rules. In International Conference on Conceptual Structures, pp. 248–262. Springer, 1996.

Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max
Welling. Modeling relational data with graph convolutional networks. In European semantic web
_conference, pp. 593–607. Springer, 2018._

Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions
_on Signal Processing, 45(11):2673–2681, 1997._

Prithviraj Sen, Breno W. S. R. Carvalho, Ibrahim Abdelaziz, Pavan Kapanipathi, Francois Luus,
Salim Roukos, and Alexander Gray. Combining rules and embeddings via neuro-symbolic ai for
knowledge base completion, 2021.

Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-walk: learning
to walk over graphs using monte carlo tree search. In Proceedings of the 32nd International
_Conference on Neural Information Processing Systems, pp. 6787–6798, 2018._

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez,
Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm, 2017a.

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez,
Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go
without human knowledge. nature, 550(7676):354–359, 2017b.

Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. Clutrr: A
diagnostic benchmark for inductive reasoning from text. Empirical Methods of Natural Language
_Processing (EMNLP), 2019._


-----

Koustuv Sinha, Shagun Sodhani, Joelle Pineau, and William L. Hamilton. Evaluating logical generalization in graph neural networks. 2020.

Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding
by relational rotation in complex space. arXiv preprint arXiv:1902.10197, 2019.

Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In Hal Daum´e III and Aarti Singh (eds.), Proceedings of the 37th International Con_ference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp._
[9448–9457. PMLR, 13–18 Jul 2020. URL http://proceedings.mlr.press/v119/](http://proceedings.mlr.press/v119/teru20a.html)
[teru20a.html.](http://proceedings.mlr.press/v119/teru20a.html)

Th´eo Trouillon, Christopher R. Dance, Johannes Welbl, Sebastian Riedel, Eric Gaussier, and Guil-[´]
laume Bouchard. Knowledge graph completion via complex tensor factorization, 2017.

Ke Tu, Peng Cui, Xiao Wang, Fei Wang, and Wenwu Zhu. Structural deep embedding for hypernetworks. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez,
Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017.

Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua
Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.

Meihong Wang, Linling Qiu, and Xiaoli Wang. A survey on knowledge graph embeddings for link
prediction. Symmetry, 13(3):485, 2021.

Peifeng Wang, Jialong Han, Chenliang Li, and Rong Pan. Logic attention based neighborhood
aggregation for inductive knowledge graph embedding. Proceedings of the AAAI Conference
_on Artificial Intelligence, 33:7152–7159, Jul 2019. ISSN 2159-5399. doi: 10.1609/aaai.v33i01._
[33017152. URL http://dx.doi.org/10.1609/aaai.v33i01.33017152.](http://dx.doi.org/10.1609/aaai.v33i01.33017152)

Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method
for knowledge graph reasoning, 2017.

Fan Yang, Z. Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge
base reasoning. In NIPS, 2017.

Matthieu Zimmer, Xuening Feng, Claire Glanois, Zhaohui Jiang, Jianyi Zhang, Paul Weng, Li Dong,
Hao Jianye, and Liu Wulong. Differentiable logic machines, 2021.


-----

# SUPPLEMENTARY MATERIALS

A DATASET STATISTICS AND IMPLEMENTATION DETAILS

We have introduced R5 in Section 3. Due to the limited space, some implementation details are not
covered. In this section, we explain the parameterization and implementation details of R5.

A.1 DATASET STATISTICS

The statistics of CLUTRR are summarized in Table 7, and the statistics of GraphLog are summarized
in Table 8.

Table 7: Statistics of CLUTRR datasets.

**Dataset** **#relations** **#Train** **#Test**

CLUTRRk∈{2,3} 22 10,094 900
CLUTRRk∈{2,3,4} 22 15,083 823

Table 8: Statistics of GraphLog datasets. NC: number of classes. AN: average number of nodes. ND: number of
distinct resolution edge sequences (distinct descriptors). ARL: average resolution length. AE: average number
of edges.

**World ID** **NC** **ND** **ARL** **AN** **AE** **#Train** **#Test**

World 2 17 157 3.21 9.8 11.2 5000 1000
World 3 16 189 3.63 11.1 13.3 5000 1000
World 13 16 149 3.58 11.2 13.5 5000 1000
World 17 17 147 3.16 8.16 8.89 5000 1000
World 30 17 177 3.51 10.3 11.8 5000 1000

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

Re 0 12 631 3.91 28.8 72.9 1000 200
Re 1 12 736 5.19 29.3 71.5 1000 200
Re 2 11 725 3.82 29.2 73.0 1000 1000

A.2 HYPERPARAMETERS

We use the following hyperparameters for all the datasets: epochs = 10, learning rate = 0.01, n = 50,
_ϵ = 0.003, v0 = 0.6, v1 = 0.3, v2 = -0.05, v3 = -0.1, v4 = -0.3, vT neg = -1, σ = -1.2, and vT pos = 0.1_
or 0.35 or 0.8 depending on the dataset we investigate. For example, since there is no simple data in
Re 2, we use vT pos = 0.8 instead to encourage R5 to memorize uncertain rules.

A.3 IMPLEMENTATION DETAILS

We have mentioned the scoring scheme in Section 3.2. However, two optional hyperparameters are
introduced, which can make sure the ground truth rules not be omitted due to large noise in datasets.

Recall that simple data are samples with a resolution length of 2, and the ground truth rules can
naturally be collected from such data. To deduct such samples, R5 only needs one step. We give
an extra simple true reward vtrue to the action to consolidate the corresponding rule in the memory.
The other optional hyperparameter is a simple wrong allowance vwrong. It can be applied when the
rule collected from a simple sample is not in accordance with the existing rule in the rule memory.

Besides, to speed up training, we sort all the training samples by their maximum resolution paths,
and train in the ascending order of the maximum resolution path in the first epoch. Thus, some
ground truth rules can be quickly collected from simple data at an early stage.


-----

|Body 0|Body 1|Head|Score|
|---|---|---|---|
|r2|r0|u|4.303|
|u|r1|r0|-0.197|
|||||

|Col1|r0|r1|r2|u|
|---|---|---|---|---|
|r0||1|1||
|r1|||||
|r2|2||||
|u|||||

|Col1|r0|r1|r2|u|
|---|---|---|---|---|
|r0|||||
|r1|||||
|r2|1||||
|u|||||

|Col1|Col2|0r1|r2|u|
|---|---|---|---|---|
|r0|||||
|r1|||||
|r2|||||
|u||1|1||

|Col1|r0|r1|r2|u|
|---|---|---|---|---|
|r0|||||
|r1|||||
|r2|||||
|u||1|||


**Input Graph**

**Rules Hash Table**

r0 r1 Y **Body 0 Body 1** **Head** **Score**

r2 **r2** **r0** **u** **4.303**

r2r2 r0 **u** **r1** **r0** **-0.197**

X

**Paths between query nodes** **Paths between query nodes**

Path 1 r2 r0 r1 Path 1 u r1

Path 2 r2 r0 r2 Path 2 u r2

**Action: (r2,r0) -> u**

**Relation pairs to state** **Relation pairs to state**

**2 features** **2 features**

**Number of occurrence** **Whether in the obtained rules** **Number of occurrence** **Whether in the obtained rules**

r0 r1 r2 u r0 r1 r2 u r0[r1 r2] u r0 r1 r2 u

r0 1 1 r0 r0 r0

r1 r1 r1 r1

r2 2 r2 1 r2 r2

u u u 1 1 u 1


Figure 4: Illustration of the state and the state transition after taking an action.

A.4 AN EXAMPLE OF STATE TRANSITION IN THE DECISION-MAKING PROCESS

Figure 4 gives a trivial example to illustrate how the state is constructed and the state transition after
applying an action. As shown in Figure 2 and Section 2.1, the state represents (m + n)(m + n)
relation pairs and k features. In this trivial example, we consider m = 3, n = 1 and k = 2 for
a reasoning task, which means there are m = 3 known relations, and n = 1 allocated invented
relation, thus in total 4 × 4 = 16 relation pairs. We also consider the two features to be the number
_of occurrences and whether the relation pair is in the obtained rules. Please be noted that we only_
hash table but it is not counted when deciding whether a relation pair is in the obtained rules beforecompute the state features for the relation pairs in the paths. This is why u, r1 → _r0 is in the rules_
taking the action.

A.5 EXTENDING TO COMPLEX DOMAINS

**Handling ˆp ←** **_pi. In Section 2 we explained that R5 realizes Horn clauses by firstly finding paths_**
based on the query, and then omitting the entities and represent the long clauses by the composition
of short clauses u _pi_ _pj. We want to make a note here R5 is also able to represent the very_
short clause ˆp ← _p ←i by adding a dummy relation ∧_ _rdm to the state described in Section 2.1, and the_
corresponding predicates will bebeen implemented in the code. _pdm. Thus, ˆp ←_ _pi can be represented by ˆp ←_ _pi ∧_ _pdm. This has_

**Triadic Relations and Hyper-Networks. In this paper, we assume all rules are using the dyadic**
chain meta-rule template (Muggleton et al., 2015). However, R5 has the potential to handle triadic
relations and hyper-networks. A hyper-network is formed by hyperedges, where a hyperedge refers
to the relationship among data points that could go beyond pairwise, i.e., three or more objects are
involved in each relation or predicate (Tu et al., 2018). Since R5 does not consider entities after paths
are sampled, it naturally has the ability to handle hyperedges. For example, given two hyperedges
_r0(x0, x1, x2) and r1(x1, x2, x7), where xi are entities, part of the path can be r0, r1. However,_
hyperedges and hyper-networks is a different topic, which is not what we focus on in this paper. We
have left this topic as future work.

B AUGMENTING R5 WITH R-GCN

R5 makes predictions relying on the obtained rules. Different from the embedding-based methods,
which can always return a relation type with the least loss, it is possible that R5 cannot give a known


-----

relation as the prediction with its logical knowledge. During testing, R5 may fail to find the body of
a deduction step in the memory, or finally deduce into an invented relation. Neither is able to give
a valid prediction. We define the invalid prediction ratio as the ratio that R5 fails to return a known
relation.


When a human is not able to make decisions based
on logic, he may need the help of intuition. Similarly, we combine R5 with R-GCN, a GNN-based
model, which is not able to explicitly reason to make
predictions (similar to a human’s intuition), to see if
the results can be further improved when R5 is complemented by a GNN. Besides, R-GCN takes node
embeddings into account, which may help to improve the predictions that require node properties.


Table 9: Results of augmenting R5 with R-GCN.

**Re 1** **Re 2** **World 32**

R-GCN 0.250 0.371 0.596
R5 0.590 0.440 0.899
R5 + R-GCN **0.640** **0.652** **0.947**


The R-GCN model is trained with the following hyperparameters: a learning rate of 0.001, a
node/relation embedding dimension of 200, 20 training epochs, 4 layers, and a dropout rate of 0.1.

Table 9 shows the results of augmenting R5 using R-GCN. And in the R5+R-GCN model, when R5
fails to give a valid prediction, we use R-GCN to predict the target relation. The invalid prediction
ratios of R5 for Re 1, Re 2, and World 32 are 0.26, 0.434, and 0.085 respectively. As presented in
the table, the prediction accuracy can further be improved by augmenting R5 with R-GCN, i.e., the
accuracies improve by 0.05, 0.212, and 0.048 on the three datasets, respectively, indicating that the
reasoning provided by R5 and GNN-based approaches are complementary to each other.

C RESULTS ON CLUTRR WITH HYPERPARAMETERS FINE-TUNED ON LONG
STORIES


Table 10: Results on CLUTRR, trained on stories
of lengths {2, 3} and evaluated on stories of lengths
_{4, ..., 10}._ [[∗]] means the numbers are taken from
CTP’s paper. [l] means fine-tuned on long stories.

**4Hops** **5Hops** **6Hops** **7Hops** **8Hops** **9Hops 10Hops**

R5 .98±.02 .99±.02 .98±.03 .96±.05 .97±.01 .98±.03 .97±.03

CTPL∗ .98±.02 .98±.03 .97±.05 .96±.04 .94±.05 .89±.07 .89±.07
CTPA∗ .99±.02 .99±.01 .99±.02 .96±.04 .94±.05 .89±.08 .90±.07
CTPM _∗_ .97±.03 .97±.03 .96±.06 .95±.06 .93±.05 .90±.06 .89±.06

GNTP[∗] .49±.18 .45±.21 .38±.23 .37±.21 .32±.20 .31±.19 .31±.22
GAT[∗]l .92 .01 .73 .04 .56 .04 .55 .04 .54 .03 .55 .04 .50 .04
_±_ _±_ _±_ _±_ _±_ _±_ _±_
GCN[∗]l .84 .04 .61 .03 .51 .02 .48 .02 .45 .03 .47 .05 .41 .04
_±_ _±_ _±_ _±_ _±_ _±_ _±_

RNN[∗]l .93 .03 .91 .03 .79 .08 .82 .06 .75 .11 .68 .07 .64 .07
_±_ _±_ _±_ _±_ _±_ _±_ _±_
LSTM[∗]l 1.0 .00 1.0 .00 .95 .03 .94 .04 .87 .08 .86 .08 .84 .09
_±_ _±_ _±_ _±_ _±_ _±_ _±_
GRU[∗]l .92 .05 .88 .06 .78 .09 .77 .09 .74 .08 .66 .10 .65 .08
_±_ _±_ _±_ _±_ _±_ _±_ _±_

CNNH[∗]l [.94][±][.03 .86][±][.06 .77][±][.08 .72][±][.08 .64][±][.09 .59][±][.10 .59][±][.09]
CNN[∗]l .93 .04 .86 .07 .84 .09 .79 .08 .77 .10 .69 .09 .70 .11
_±_ _±_ _±_ _±_ _±_ _±_ _±_
MHA[∗]l .81 .04 .76 .04 .74 .05 .70 .04 .69 .03 .64 .05 .67 .02
_±_ _±_ _±_ _±_ _±_ _±_ _±_


Table 11: Results on CLUTRR, trained on stories of
lengths {2, 3, 4} and evaluated on stories of lengths
_{5, ..., 10}._ [[∗]] means the numbers are taken from
CTP’s paper. [l] means fine-tuned on long stories.

**5 Hops** **6 Hops** **7 Hops** **8 Hops** **9 Hops** **10 Hops**

R5 .99±.02 .99±.04 **.99±.03** **1.0±.02** **.99±.02** **.98±.03**

CTPL∗ .99±.02 .98±.04 .97±.04 .98±.03 .97±.04 .95±.04
CTPA∗ .99±.04 .99±.03 .97±.03 .95±.06 .93±.07 .91±.05
CTPM _∗_ .98±.04 .97±.06 .95±.06 .94±.08 .93±.08 .90±.09

GNTP[∗] .68±.28 .63±.34 .62±.31 .59±.32 .57±.34 .52±.32

GAT[∗]l .98 .01 .86 .04 .79 .02 .75 .03 .73 .02 .72 .03
_±_ _±_ _±_ _±_ _±_ _±_
GCN[∗]l .88 .01 .78 .02 .60 .02 .57 .02 .59 .04 .51 .02
_±_ _±_ _±_ _±_ _±_ _±_

RNN[∗]l .96 .03 .87 .09 .82 .09 .73 .09 .65 .15 .67 .16
_±_ _±_ _±_ _±_ _±_ _±_
LSTM[∗]l 1.0 .01 .99 .02 .96 .04 .96 .04 .94 .06 .92 .07
_±_ _±_ _±_ _±_ _±_ _±_
GRU[∗]l .96 .02 .88 .03 .84 .04 .79 .06 .75 .08 .78 .04
_±_ _±_ _±_ _±_ _±_ _±_

CNNH[∗]l 1.0 .00 .99 .01 .96 .02 .91 .04 .89 .04 .87 .04
_±_ _±_ _±_ _±_ _±_ _±_
CNN[∗]l 1.0 .00 .98 .01 .97 .02 .92 .03 .89 .03 .87 .04
_±_ _±_ _±_ _±_ _±_ _±_
MHA[∗]l .88 .03 .83 .05 .76 .04 .72 .04 .74 .05 .70 .03
_±_ _±_ _±_ _±_ _±_ _±_


D CASE STUDIES

Table 12 and Table 13 present some examples of the recurrent relational reasoning process by R5
on CLUTRR and GraphLog datasets. For verification, GraphLog provides the ground truth rules
sets used to generate each dataset, and in Tables 13 and 14 we mark such ground truth rules in bold.
As presented, R5 is able to discover the ground truth rules, and learn long compositional rules. In
the second instance in Table 13, we have an invented relation unknown 44. With this intermediate
relation introduced, we can get a clause with three atoms in its body, i.e., r 6←(r 9,r 3,r 9).

Table 14 shows some examples that R5 falsely predicts the queried relations. In the first example,
both rules used are in the set of ground truth rules, leading to a prediction of r 3 between the queried
pair, which is different from the target relation r 13 provided in the test set. Furthermore, we find
that there is no ground truth rule in this world to allow the prediction of r 13 by human deduction.
Neither can R5 deduct r 13.


-----

Table 12: Detailed breakdowns of deduction steps by R5 on CLUTRR.


**Target Relation** **Deduction steps (head ⇐** **body)**

_sister_ (Jason _daughter_ Stephanie) (Jason _wife_ Ruth, Ruth _daughter_ Stephanie)
Jason Evelyn _−sister−−−−−→_ _⇐_ _daughter−−−→_ _−−−−−−→aunt_
_−−−−→_ (Jason _−−−−→_ Evelyn) ⇐ (Jason _−−−−−−→_ Stephanie, Stephanie _−−−→_ Evelyn)

Jeff _−aunt−−→_ Cristina (Jason(Jeff _−mother−sister−−sister−−−−−→→Ruth)Cristina) ⇐_ _⇐(Jeff(Jason−sister−−−→husband−daughter−Gloria, Gloria−−−−→_ Stephanie, Stephanie−mother−−−−sister→ Ruth) _−aunt−−→_ Cristina)

(Jeff(Ruth−aunt−−−−−→−→Cristina)Cristina) ⇐ ⇐(Jeff(Ruth−mother−−−−−−→−−−Ruth, Ruth→ Jason, Jason−sister−−−→−−Cristina)−−→ Cristina)

Carmelita _−son−−−−−in−−−law−→_ Chuck (Carmelita(Carmelita(Carmelita(Carmelita(Mark(Peter _−−sister−sister−−−−−→−−−−→granddaughtergrandsonsondaughter−−−−−−−−Brandi)Brandi)−−−−−−−−−in−−−−−→→−−law−− ⇐Elizabeth)−→ ⇐Mark)−→Chuck)(Peter(MarkBrandi) ⇐_ _⇐−(Carmelita ⇐−brother−brother−−− ⇐−(Carmelita(Carmelita−−−→→(CarmelitaMichael, MichaelPeter, Peter−daughter−−−−−granddaughter−daughter−−−−−−grandson−→−−−−−−−−−Martha, Marthasister−−→−−−−−−→Elizabeth, Elizabeth→−−sister→−Mark, MarkBrandi)−−Brandi, Brandi→_ Brandi)−son−→−sister−Mark)−−→−−aunthusband−−−Brandi)−→−−Elizabeth)→ Chuck)

Table 13: Detailed breakdowns of deduction steps by R5 on GraphLog.

**Target Relation** **Deduction steps**


**r 2 ⇐** **(r 3, r 13)**
**r 1 ⇐** **(r 2, r 20)**
**r 9 ⇐** **(r 3, r 6)**
**r 5 ⇐** **(r 1, r 9)**
**r 7 ⇐** **(r 5, r 6)**
r 16 ⇐ (r 2, r 7)

**r 2 ⇐** **(r 3, r 13)**
**r 1 ⇐** **(r 2, r 20)**
r 3 ⇐ (r 1, r 20)
unknown 44 ⇐ (r 3, r 9)
r 6 ⇐ (r 3, r 3)
**r 9 ⇐** **(r 3, r 6)**
r 6 ⇐ (r 9, unknown 44)


r 16

r 6


Table 14: Wrong relation predictions by R5 on GraphLog.

**Target Relation** **Prediction** **Deduction steps**

**r 6** **(r 20, r 13)**
r 13 r 3 _⇐_
**r 3 ⇐** **(r 16, r 6)**

**r 19 ⇐** **(r 15, r 8)**
r 5 r 18 **r 17 ⇐** **(r 19, r 4)**
**r 18 ⇐** **(r 8, r 17)**

In the second example, all the three rules learned by R5 are ground truth rules, enabling us to
predict r 18 from the resolution path [r 8,r 15,r 8,r 4]. Yet, r 18, although correct, does
not exactly match the target relation r 5 provided by the test set. We note that there is not any
ground truth rule provided by the dataset whose head is r 5.

However, R5 has also learnt an additional rule from the training samples headed to r 5:

r 5←(r 8,r 18), (5)

which is not in the set of ground truth rules. With Rule (5), we have another sequence of deductions
that can lead to r 5 from the resolution path [r 8,r 15,r 8,r 4]:

**r 10←(r 8,r 4),**
**r 18←(r 15,r 10),** (6)
r 5←(r 8,r 18),

where the first two rules in bold are in the ground truth rules, while the third is not.


-----

Since there are two valid relation types r 5 and r 18 between the queried node pair, R5 may not
be able to tell which one should be selected without knowledge of the entities. This is an example
where the entity properties may help with logical inference.

E DISCUSSIONS ON SOME KB REASONING WORKS

As discussed in Section 4, KB reasoning is not what we focus on. However, R5 has some strength
compared with some of the existing KB relational learning works. Yang et al. (2017) learns the rules
in the form query(Y,X) Rn(Y,Zn) R1(Z1, X), where each predicate strictly contains
_←_ _∧· · · ∧_
2 entities. Whereas, R5 is able to consider predicates with any number of entities as explained in
Appendix A.5.

Moreover, many RL Path-finding Agents (Xiong et al., 2017; Chen et al., 2018; Das et al., 2017; Lin
et al., 2018; Shen et al., 2018) are proposed for KB reasoning. The major challenges for these works
include the sparse rewards. For example, at each step of decision-making, Shen et al. (2018) selects
neighbouring edges at the current node, and follows the edges to the next node. Termination occurs
when the agent gives a “STOP” action instead of selecting the next neighbouring edge. The termination criterion is unclear, which is one of the important reasons for the sparse reward. In contrast,
the MCTS in R5 guarantees that only the feasible relation pairs can be selected. Termination occurs
when reduced to a single relation. The criterion is clear.

However, R5 faces some challenges to generalize to KB reasoning. Apart from the ones mentioned
in Section 4, currently, R5 does not generate probabilities or scores for a prediction, which is not
capable of KB Completion since KB Completion is actually a set of ranking tasks. Besides, R5
requires pre-sampling for the paths that entails the query. Since all the triples in a Knowledge Graph
share the same training graph, which is usually very large, it will take a long time to enumerate all
the paths. If we choose not to perform enumeration and sample some paths instead, the sampling
method is also a topic that needs to be investigated. Due to these challenges, we leave the application
to KB as future work.

F COMPARISON WITH NEURAL-LP AND RNNLOGIC

Neural-LP (Yang et al., 2017) is a neural logic programming method and RNNLogic (Qu et al., 2021)
is a principled probabilistic method, where both of the two approaches are designed for Knowledge
Base Completion (KBC) problems. These methods requires enumeration of all possible rules given
a max rule length T . Thus, the complexity of these models grows exponentially as max rule length
increases, which is an outstanding disadvantage for systematicity problems.

Table 15: Comparison with Neural-LP and RNNLogic.

|Model|GraphLog World 17 GraphLog Re 0|
|---|---|


|R5 Neural-LP RNNLogic w/o emb|0.947 0.665 0.057 0.080 0.606 0.348|
|---|---|



We tweaked the code of RNNLogic, which was originally designed for entity ranking, to predict
and rank relation r given (h, ?, t) on GraphLog. The results are shown in Table 15. One issue we
observed was that we were only able to run RNNLogic with max rule length T up to 7 on a powerful
server, beyond which there was out-of-memory issue. (For instance, setting T = 6 for RNNLogic
on GraphLog Re 0 requires more than 130 G memory.) We report its best result in Table 15, which
is achieved when T = 5. It is shown that R5 substantially outperforms RNNLogic, which is in fact
not designed for this task. Similarly we revised NeurlLP to make it work for the relation prediction
prediction task. But unfortunately, it didn’t work well with a relation prediction accuracy of less
than 10%.


-----

EXTRA FEATURES TO RECORD THE MAX/MIN NUMBER OF
OCCURRENCES AMONG PATHS.

Table 16: Comparison with max/min number of occurrences among path added to features.

|Model|GraphLog World 17 GraphLog Re 0|
|---|---|


|R5 R5 with extra features|0.947 0.665 0.941 0.673|
|---|---|



NUMBER OF PRE-ALLOCATED INVENTED RELATIONS


Figure 5: The test accuracy as the number of pre
Performance changes in terms of n on World 17

0.95

0.94

0.93

0.92

est accuracyT 0.91

0.90

0.89

0.88

0 10 20 30 40 50

number of pre-allocated invented relations

allocated invented relations varies for World 17 in
GraphLog.


Figure 6: The test accuracy as the number of

Performance changes in terms of n on Re 0

0.70

0.68

0.66

0.64

est accuracyT 0.62

0.60

0.58

0.56

0 10 20 30 40 50

number of pre-allocated invented relations

pre-allocated invented relations varies for Re 0 in
GraphLog.


In this paper, we have introduced n pre-allocated invented relations to capture the intermediate short
rules during the decision-making procedure. For example, r1, r2, r3 _r can be decomposed into_
(r1, r2 invented0), (invented0, r3 _r). The details can be found in Section 2.2. To choose →_ _n,_
we conduct experiments on two GraphLog datasets, World 17 and Re 0, as → _→_ _n varies. We use the_
parameters listed in Appendix A.2, except that 5 training epochs are used instead of 10 to speed up
training. As presented in Figure 5 and Figure 6, R5 is able to get a near optimal performance even
when n is small. But as n becomes larger, there is a general trend that the performance can be more
stable. Intuitively, a small n makes the dynamic memory replace the invented (unknown) relations
more frequently as new invented relations appear, slowing down the convergence (as we discussed
in Section 3.3). Therefore, in our experiments, as computational resources permit, we set n to be 50
for all the datasets. However, if a small n is required in practice, we can also use a validation set to
select some n that is sufficient for each specific dataset.


-----

