R5: Rule Discovery with Reinforced and Recurrent Relational Reasoning
Authors: Shengyao Lu
Bang Liu
Keith G. Mills
SHANGLING JUI
Di Niu
Venue: ICLR 2022 Spotlight (2022)
Keywords: systematicity
graph reasoning

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. 

Published as a conference paper at ICLR 2022
R5: RULE DISCOVERY WITH REINFORCED AND RE- CURRENT RELATIONAL REASONING
Shengyao Lu'-, Bang Liu Keith G. Mills', Shangling Jui", Di Niu'
"Department of Electrical and Computer Engineering, University of Alberta
"RALI& & Mila, Université de Montréal, 'Canada CIFAR Al Chair
HHaawei Kirin Solution
(shengyao, kgmi 11s, dni u auaaeuuaueo weeuualeeta..comm ca
bang 1 liuu umont real , ca, jui. shang www.ggggiigghawwe.ccooo
ABSTRACT
Systematicity, i.e., the ability to recombine known parts and rules to form new se- quences 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 large-scale tasks. In this paper, propose R5, a relational reasoning frame- work 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 backtrack rewriting mechanism for rule mining. By alternately applying the two components, R5 progressively learns 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 out- performs various embedding- bbasdd and rule induction baselines on relation pre- diction tasks while achieving a high recall rate in discovering ground truth rules.
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 [012] Dong et al. 2018). To concretely explain systematicity (Hupkes et al., 2020). let us consider the kinship problem shown in Figure [ By training on the small-scale observed examples of family relationships where the rule paths are short (in Figure & both of the rule paths have the length of 2), our ob- jective is to extract the underlying rules as general principles and generalize to large-scale tasks where the rule paths are long (in Figure De. the rule path has the length of 3). The rules in the training examples are a) Mother(X. (X,, Y) & Mother(X. 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. (X, Y) <- Mother(X, U", Sister(U, Z), Father( Z, Y), which does 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.
SisterrUU
Some attempts on the graph relational data grounded in Graph Neural Networks (Schlichtkrull et al.) 2018 Sinha et al. 2020; Pan al. 2020) rely on learning embedding vectors of entities and rela- lions, 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 al.] 2017: Evans Grefenstette 2018) is a subfield of symbolic rule learning, which naturally learns symbolic rules and provides interpretable ex explanations for labels prediction as well as being able to generalize to other tasks. A traditional II.P system learns a set of rules from collection of positive and negative examples, which entails all the positives and none of the negatives. However,
"Equal contribution.

---

Published as a conference paper at ICLR 2022
c. Inductive relation prediction
Training gr graph 1
b. Truining graph
Ane
Pattor
Austor
Utrole
Grandra
Stater
Juck
Mocher
John
(eb
Iedievt.S), Glaterrt. 21
Grundeack, B) Herbbrrk, B), Petbects,
Netberr (Marry, Saa),, Staterr Petuc)
Figure I: 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- -huural-Symboii Learning (Garcez et al. 2013 Besold et al. 2017) secks to integrate principles from neural networks learning and logical reasoning, among which Neural Logie Machines (Dong al., 2018 Zimmer al. 2021) and Theorem Provers (Rocktäschel) & Riedel 2017: Minervini et al.) 2020a by aim to overcome the problems of systematicity. On one hand, the Neural Logie Machines approximate the logic predicates using a probabilistic tensor repre- sentation, and the conclusion tensors are generated by applying the neural operators over the premise tensors. These approaches have done 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. deter- mining whether 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 pre-defined task-specific rule template and 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 single relation. However, the performance is not satisfying.
In this paper, we focus on model's 's systematicity for relational reasoning over graph relational predic- tion tasks and present 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 mecision and performs rule extraction and logical reasoning with deep reinforcement learn- ing equipped with a dynamic rule memory. More concretely, R5 learns the short definite clauses that are in the form u + p; A Pj. Since long Horn clauses (Horn 1951 can be decomposed into short Horn clauses, a long definite clause outcome + Po A P1..PP A Py...Pi: used in prediction tasks is represented with sequence of short definite clauses while performing decision-making i.e. ps A Pj replaced by u. Specifically, we make the following contributions:
First, R5 performs explicit reasoning for relation prediction via composition and achieves ex- plainability. Instead of learning embeddings for entities and relations, (Hamilton et al., 2017 Schlichtkrull et al. 2018 Wang et al. 2019 Pan et al.] (020) and performing implicit reasoning, we perform explicit relational reasoning by modeling as sequential
socision-making Specifically, given a query (usually consists of two queried entities) and the related relationship graph, the agent recurrently selects a relation pair re ry 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 serve as the key, and T%k serves as the value. In each step of decision-
of гœ + Tú, Tj. Ti, making, the agent queries the rule memory to re-use already stored rules for reasoning, i.e., deducing 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.c. systematicity) in relational reasoning tasks.
Third, rather than only taking the observed relations into account, we introduce extra invented re- lations into the reasoning process. For example, R5 may learn to combine and r2 by rule r + 71, T2, where r is an intentionally introduced relation. The invented relations can appear on both the left or right side of rule clause. Such 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 sometimes necessary discover complex rules in the relational data.
2

---

Published as a conference paper at ICLR 2022
Monte Carto
tree search
Frumentl
Target
Patto betwoian nodes
(Sir)) F31
Puth
Lookup
Update
Pash
Dynamio
Seapue
known 1/L
fa(e)
Polloy Value
Natwork
fo(*)
Backtrack rewntting
50 Vy R
Figure 2: Overview of the propose RS framework for rule-inductive relational reasoning. Furthermore, we design 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 '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 ict 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 strong ability of compositional generalization and robustness to data noise. The imple- mentation is available at
cwm/s sluxsr/rsS r
2 PROPOSED APPROACH
Table 1: Notations
In this section, we introduce our Rule Discovery with Reinforced and Recurrent Relational Reason- ing framework, namely R5, to solve the inductive relation prediction problem. We first formally define the relation prediction problem discussed in this pa- per. Let PaamlG q, a)
The set of known relations types M
N
The set of invented relations types
a relation type
a query number paths to sample each query actual number of paths for ?
training data distribution, where G is the set of training graphs, q (X, Y) is a query, and a = r is the answer. The graphs consist of nodes in set N. which are connected by rela- tions in a set R. X,Y E N are nodes, and r E R is relation. Given G and the query q, the goal is to predict the correct answer a. Relational prediction task is actually program induction, which is a hard problem that has been studied for many years in the area of Inductive Logic Programming and Statistical Relational Learning, especially for large-scale tasks in noisy domains. Figure shows an overview of R5. Our framework takes relational graph as input, and outputs the relationship between two queried entities based on extracted rules. RS 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 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 Ta- ble 1 Note that an action a a < (an,0, a2,1) and rule rl == rla <- (rIn,o, rln.1 share the same structure, where different a and rl are all relations. az and 0g represent the head and body in rule, respectively. Next we introduce R5 in detail.
Tgg
a2
The 8dh action in in the sequence
The 1d relation in a's body
0p.
a's head
The 8th current state in in the sequence The 2th reward in the sequence
Zi
D.i
Dictionary rules
Det
Dictionary of rules scores an entry in D,ta
Buna
Buffer of unused invented relation types a score value
02
2.1 RECURRENT RELATIONAL REASONING
Path sampling. To predict the relation between two entities in graphs, preprocess the data by sampling paths that connect the two entities from the graph. When the total number of paths is small, enumerate all the paths. Otherwise, we randomly sample I. paths at maximum. Each path purely
3

---

Published as a conference paper at ICLR 2022
consists of relations. For instance, in Figure 2 given the input graph, we can get 4 paths between query nodes X and Y, inccuuding 11 71-12-15 - and so on.
Reasoning as sequential decision-making. Our method solves the problem of relational reasoning in terms of sequential decision 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 {s) is a neural network with parameters 8. It takes the current state s as input, and outputs the action probability distribution p and a state value v. MCTS utilizes the policy network ss() to guide its simulations, and outputs a vector т representing the improved search probabilities of the available actions. The policy network (p.v)
fs(s is then trained to minimize the error between the predicted state value 1/ and the reward received after an episode, as well as maximize the similarity between two probability distributions p and æ. The loss function / = (z - v)² I log p + a |10]", where a is a haper-parameter.
Action. At each step of an episode, the MCTS outputs an action (a I which is a relation pair denoted as ag. Furthermore, by looking up the dynamic rule memory, it obtains a an < (ag,o, dB.1) that contains head relation az to be deducted to, which means that the relation pair (ag, 0. (B,1) ) in the path will be substitute with ag. For example, in Figure aat step 1, MCTS outputs an action r3 < (ri,72) f2). and the path ""a""""" is transformed into r3 -3---=-"-->>> -ra--r---- By recurrently applying different actions to a path between the query nodes, it will be transformed 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 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 8 E (m)++)) x (m+n))* as the representation of all the possible relations pairs among the current paths, where is the number of observed relations, n is the number of invented relations we sumed, 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.. E 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. 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 Ti and r22 shows up frequently in the training data, we can sample an invented relation r. as the head, and form a candidate rule r. + (ri, 72). In this way, our model learns to merge F1 and r2 quickly without the need to figure out what exactly т, is. The value of Tx will be inferred by our model with Backtrack Rewriting mechanism, which we will introduce in more detail later. Without these invented relations, 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 buffering mechanism to allow an agent 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 rules- related 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 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 relation path recurrently, until the path is deducted to a single relation r, and a reward 27 E {-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, 2т = 1. If is an invented relation, 2T = O. If r is the target relation, 2T 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
4

---

Published as a conference paper at ICLR 2022
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 D, in the form of (r (Too- PB1) Th is used to memorize the candidate rules, and another hash table Dyts in the form of (TBO, FB1) score to track the rule scores. Note that in Figure [ we union the two tables they share the same keys. A newly added rule will have an initial score of O. In Figure 2 a rule (r3) < (T1,72) r2) was stored in the hash tables, where the rule body (r1, r2) the key, and the rule head r3 and score 4.303 are the values in D2 and D,t.. respectively.
We utilize buffer Bunkn to store the n intermediate invented relations as described Sec. 2.1 When an invented relation type E N is used to complete rule, it will be removed from Bunkn. If r is freed from the rule memory Drt, then it will be added to Bunkn again.
Recall that at each time step the MCTS will return action body ag- In order to complete the action, we get the action head aи by
if ag Drt, RandomSample Bunka), otherwise.
Dr(ag)
0
Then, if ag & Drt. we update the memory Dr with Dri[a = aæ, and compute the score Ca by
to. ag E Dri, Vr E Ea, M,
U1, Drs, E M, 3r E aB, N,
Ca
U2, ag Dri, E N,
V3.
ag Dei, Vr E EB.,E M,
U4. ag & Dr E aB. N,
where 0o U1 0/ > U3 U4. 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, the end of each training episode, we further utilize Backtrack Rewriting to consolidate all the candidate rules and replace invented relations in rule with ob- served relations if we found they are equivalent. Algorithm [ describes mechanism for updating the rule memory Dr Specifically, assume the action sequence have taken in an episode is {Øo, "i.......... J. and the head relation of the last action ar r == атн pl As y is the target relation,
Algorithm 1 Backtrack Rewriting
1: series Input: Dri, Buizi last action or, target relation y Dajarn]
Backtrack Rewriting
3: if r N then
4:
for ag in D. do if Dri Dri[a]] then Dalaag] =
5:
7:
for aB in DR do
8:
a = Dr(aa]
9:
if a and aB,1 =r then
we can backtrack D,t, and replace all its oc- currences with Before updating Drr jargl. we update the corresponding entries in Dris of the actions { @1, (I..........T) in the episode by
10:
key (v.
11:
else if a8,0 then key = (v. (2.1
12:
13:
else if az.1 then
14:
key (ap.0,
Co, + UT
T= r rE M,r V, otherwise,
15:
else
Dria(uen]
16:
continue
UTng
17:
key & D. or Dw E N then delete ag from Dz
Corr
18:
19:
Dri[key] az
where r = Driaar gl and Di'ng < <0 0T pos
20:
else
are the episode end scores. Next, we decay the
21:
delete ag from D
scores [rts(an] of all the rules an + an over episodes by:
22:
remove from Buniz
Drs [asl = [ +
[ria[an] < 0, Drts > 0,
(4)
( -
where e a small positive decay factor. Thus, the score rule that is not accessed over training episodes will decrease.

---

Published as a conference paper at ICLR 2022
Table 2: Results on CLUTRR, trained on stories of Table 3: Results on CLUTRR, trained on stories of
lengths {2.3} and evaluated on stories of lengths lengths {2,3. 4} and evaluated on stories of lengths
(4. 10). ['] means the numbers are taken from {5, ..,, 10}. []] means the numbers are taken from CTP's paper. [.] means fine-tuned short stories.
CTP's paper. [.] means fine-tuned on short stories.
4Hops
SHops
6Hops
?Hops
SHops
9Hops
10Hops
&Hops
Hops
Hops
Hope
Hops
10 Hops
RS
922.00
99=02
982.03
961.06
9972001
985.003
97:1.03
R5
99:..02
991004
99:1.0
102.02
99::.02
93:2.03
CTP1
981.02
98
974.05
961.01 01 .912005
.9.1.07
08
CTP:
991.02
98.1.01
974.01
98.1.03
974..11
.951.01
CTP)
99:.02
99=01
99:..2
964
94::05
89.1.08
90
CTP,
99::04
99:2.0
97:
95-2.06
93-2.07
91
CTP1
97+.03
97=05
964.06
95th
93
90+-06
0694006
CTP
984-04
9974.06
95:400
94+-08
93++008
90++009
GNTP
49
45-
21
38...2
.37+
21
.32
20
31
33+-22
GNTP
68++78
63++.34
62#-31
.59+t.32
-57+-34
-2++33
GAT;
02
76 06
$4:..0
56:t
.5:
554..05
45:
GAT;
99:.00
85:1.004
80:2.03
71:2:03
70:2:03
68:2002
GCN: 831.03
68:002
53:1.03
A71.00
.122.03
A54.03
0391:02
GCN;
911.03
.791.02
.61:1.03
.3341.04
.53...04
A11:001
RNN; 861.06
.762008
674.08
08
156...0
554.10
07
RNN:
93:1.06
.87..07
.79.1.11
.73
.6:11.16
.641.16
LSTM; 944.004
95=003
884..0
187
04
88:
75
75:
LSTM;
984.03
95:2.04
89:4.10
84:1.07
77:4.11
.78t-11
GRU; 89+.05
83- 06
74
72++00
.67
12.
6624.10
.60+-12
GRU;
954.04
94+-00
87++00
81-+-13
.74+.11
.75+-15
CNNH; 901
01=05
664
56-t.13
52:4.12
50t:-12
CNNH; 59::01
97:4.02
94-t.03
88:2.04
86-2.05
84+
CNN; 95+.02
90=005
894..0
880+.05
.762.08
.094.07 .704:08
CNN; 1.0:.00
1.0.001
98.4.01
.9:4.03
93:2.03
.24.04
MHA; S1+ 04 76-044 744.00
770H 04 000+003 64 -67+002
MHA; 88+.03
83++00
776+t.04
.72+.04
.74+:05
.70+.03
Finally, when rule score is less than 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 0H bad E N. Thus, the bad rules will be gradually removed from the rule memory. Bunkn and Drts will be updated accordingly. Besides, when the invented relations buffer Bunkn is empty, we will look up the rules scores hash table Dris to find the rule H bad < Bbad that has the smallest rule score, where de E N. Then all the corresponding rules in Drt that contain a bad will be removed, and bad will be added back Bunza.
3 EXPERIMENTS
We evaluate RS on two datasets: CLUTRR (Sinha et al. 2019) and GraphLog (Sinha et al. 2020), which test the logical generalization capabilities. We compare with embedding- baatd and rule in- duction 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 al. 2019) is 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 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-banl bbased models (Veličković et 2017 Kipf & Welling 2017 Schuster& & Paliwal 1997, Hochreiter & Schmidhuber 1997 Chung et al. 2014 Kim 2014]] Kim al. 2015] Vaswani et al. 2017) and several neuro- couro-symmolic models that consists the rule induction baselines (Minervini et al. [2020a b). The results of the baselines are taken from Minervini 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 [ and none of them can beat R5.
Results. Table TO I1 present the prediction accuracy on two datasets pulished by Sinha et al. (2019) We call the two datasets CLUTRR and CLUTRR (e (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, 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 gemeralization 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 we test model performance with no bad cases in data. A bad case is a logically wrong example. For example, the mother of sister is a father is a bad case. Apart from the compositional
6

---

Published as a conference paper at ICLR 2022
Table 4: Results of reasoning on the selected GraphL.og datasets (worlds). ND: number of distinct relations sequences that traverse between query nodes; ARI.: 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
R5
Accuracy
Rules Recall
Accuracy
Rules Recall
World 2
157
3.21
0,412
0.347
0.685=00.03
0.80=0.05
0.755=0.02
1.0=0.00
World 3
189
3,63
0.473
0.451
0.624:10.02
0.85=0.00
0.791=0.03
1.0=0.00
World 13
149
3.58
0.453
0.347
0.696:10.01
0.90=0.00
0.895=0.00
1,0=0.00
World 17
147
3,16
0.347
0,181
0,789:10.04
0.85=0.00
0.947=0.02
1.0=0.00
World 30
177
3.51
0.426
0.357
0.658:10.01
0.80:10.00
0.853 0.01
0.95:10.00
World 6
249
5,06
0,536
0.498
0.533:1:000
0.85=0.000
0.687=0.05
0.9:0000
World 7
288
4.47
0.613
0.537
0:513:+0.03
0.75==0.05
0.74
0.95+0.00
World 8
404
5.43
0,643
0.569
0,545:
0.70=00000
0.671=0.03
0,95
World
194
4.29
0.552
0.456
0.553:1:0.01
0.85::0.00
0.803=0.01
1.0:0.00
World 32
287
4.66
0.700
0.621
0,581=00.04
0.95=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 under- lying 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 exhaus- tive. 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- R-GCN (Shhichttrull eet al. (2088) the embedding-haased baselines, and CTPs (Minervini et al. 2020b) the rule in- duction baseline. For E-GAT and R-GCN, we use the results in (Sinha et al. use the implementation publicly provided by the author with the best configurations. In addition, we use the core generator provided by (Sinha et al. (020), which is used to produce the GraphLog datasets, to generate three new worlds: Re O, Re I, 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 the correct path between the queried nodes. Figure b are instances of resolution lengths of 2, and Figure I 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.
2020). For CTPs, we
Results Table 4 shows the results 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 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 O can be up to 10, while resolution lengths of graphs in Re 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. (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 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.
7

---

Published as a conference paper at ICLR 2022
Table 5: Results on new datasets generated using Graphl og generator. ND: number distinct relations se- quences that traverse hetween query nodes; ARI: Average resolution length. RL:: resolution length. ACC: Accuracy. We rerun CTPs using the released source code.
CTP
R5
Data set
ND
ARL
Truin RL
Test RL
ACC
Recall
ACC
Recall
Re 0
631
3,90
2~100
2~110
0.425+00003
0.75=+0.00
0.66
1.0+0.00
Re
736
5.19
2-115
2-155
0.190:10.06
0.75+0.00
0.575:10.02
10:00.00
Re 2
725
3,81
3-5
2-7
0,359+00.22
0.30=+0.05
0,446:10.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, 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 sequentially de- cide 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 vis- its at all possible nodes. From 6 we acquire that although we are still able to recall the ground rules with rules extraction, the prediction accu- racy drastically decreases since the paths are not deducted in the correct order.
Table 6: Ablation study of RS. PVN: policy value network.
World ACC
World 6 ACC:
Re 2
Recall
Recall
ACC
Recall
R5
0.755
1.0
0.687
0.9
0,446
0.70
R5 w/o PVN R5, nml
0.502
1.0
0.407
0,9
0.208
0.60
0.661
1.0
0.595
0.85
0.349
0.70
Re Test Accuracy vs. epocts
Re 2 Rules Recall vs, epochs
Test Accurnte
Pre-allocated Invented Relations. We pre- allocate invented relations allow a relation pair to deduct to an intermediate predicate when still unclear whether the relation pair can give us a correct rule. And the intermediate predicate will be tracked during the training until is iden- tified as a known relation. Refer to Table when we only allow a single invented relation, the pre- diction accuracy will drop, which indicates that the extra hidden relations improve the model's ca- pability of learning complicated graphs. And in Re 2, where the training samples' resolution lengths 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 R5 with 50 hidden predicates. This figure proves that number of pre-allocated invented relations can not only help to learn complicated graphs, but also speed up the convergence.
RB win PWN
R5. n
Trining Tpoch Ablation study R5 on terms of test accuracy and rules recall rate.
Towining Footh
Figure 3:
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 (017) is 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 (Schlichkkull 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 (Sinhal jtt al. 2020). However, since the lifted rules are implicitly encapsulated in the neural networks, these models are lack of interpretability.
ILP, SymbollSymoolic Learning and Systematicity. Inductive Logic Programming (ILP) (Mug- gleton 1992, Muggleton et al.) 1996; Getoor 2000 Evans & Grefenstette 2018) is subfield of symbolic rule learning, which learns logic rules derived from a limited and predefined set of rule templates. A traditional ILP system learns set of rules from collection of examples, which entails all the positives and none of the negatives. Such a system naturally provides interpretable explana- tions for labels prediction as well as being able generalize to new tasks but is hard scale up to
8

---

Published as a conference paper at ICLR 2022
the exponentially large space of compositional rules (Evans & Grefenstette 2018 Yang 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, [ropper & Muggleton (2015) re- duces 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 rela- tional paths, such that statistical learning approaches are applied extract weighted logic rules. Using a statistical discriminative model, SUL also enables predicate invention.
Neural- -hural-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., 202T) and Theorem Provers (Rocktäschel Riedel| 2017: Min- ervini 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. Al- though 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 per- forming 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 al. 2020a 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 sub- goals, 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. RS is able to handle the complicated rules where the allowed rule depth is much larger. That is because the rule depth 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-basee methods (Sun et al., 2019 Trouillon et al.]
2017 Dettmers et al. 2017 Bordes et al., 2013), GNN-like methods (Teru al.
2020 Mai et al. 2020 Neural-Symbolic Methods (Rocktäschel & Riedel 2017] Minervinn et al,,
2020a b Qu et al. (22TT) and RL Path-finding Agents (Xiong et al.) 2017 Chen et al.) [018] Das it 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 query (h, r, ?) with head entity h and the relation r are given (Wang et al.) (02T). KBC is different from the general relation prediction tasks investigated in this paper. 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 1* like what R5 might do, a better choice would be directly determining whether the single relation r exists between h and 2* 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- Our framework performs explicit and explainable relational reasoning with 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 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 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.

---

Published as a conference paper at ICLR 2022
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. stat.berkeley
html
Tarek R Besold, Artur d' Avila Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pas- cal Hitzler, Kai-Uwe Kühnberger, Luis C Lamb, Daniel Lowd, Priscila Machado Vieira Lima, et al. Neural-symbolic learning and reasoning: survey and interpretation. arXiv preprint arXiv:1711.03902. 2017.
Antoine Bordes, Nicolas Usunier, Alberto García-Durán, J. Weston, and Oksana Yakhnenko. Trans- lating embeddings for modeling multi-relational data. In NIPS, 2013.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks 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 (Long Papers), 2018.
doi: 10.18653/v1/n18- 1165. URL.ttp:: /xx www.dxxooo..ooooo wwtp:/oiiooooggo.oooooooo wot./oogg/......... 111.311..111111111111 8116
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. arXiv preprint arXiv:1412.3355, 2014.
Andrew Cropper and Stephen H Muggleton. Logical minimisation of meta-rules within meta- interpretive learning. In Inductive Logic Programming, pp. 62-75. Springer. 2015.
Andrew Cropper, Sebastijan Dumančić, 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,, 2020. doi: (0.24963/ijcai22200777 URL hittps://dot orgg / 10. 24963/ /jaiiicaai.. 2020/ Survey track.
Wang-Zhou Dai and Zui-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 -611, Hong Kong, 20-22 Nov 2016. PMLR. URL https:// prwceedingeeesesooooeeee.p mlr wrw.srrssseeeeeee
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 Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning, 2017.
Michaël 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 S- 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 Learning Representations, 2018.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
10

---

Published as a conference paper at ICLR 2022
Jerry Fodor and Brian P. McLaughlin. Connectionism and the problem of systematicity: Why
smolensky's 's solution doesn't 't work. Cognition, 35(2):183 204, May 1990. ISSN 0010-
0277. doi: 10.0016/011--27779999901444 0010- (90) 90014-B
URL http://dx: /ttp://.....111111111111111
Jerry A. Fodor and Zenon W. Pylyshyn. Connectionism and cognitive architecture: A critical analy- sis. Cognition, 28(1-2)33-71, Mar 1988. ISSN 0010-0277. doi: 10.101 10.1166001000277888900001
9030003
Jianfeng Gao, Michel Galley, and Lihong Li. Neural approaches to conversational ai. 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öldiak, Pascal Hitzler, Thomas Icard, Kai-Uwe Kühnberger, Luis C Lamb, Risto Mikkullinenn, 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-4414400 25. URL
http://dx. doi. wwt.:ddii...rg..1. 1007010..000----111
ROBERT F. Hadley. Systematicity in connectionist language learning. & 9(3):
247-272, September 1994. ISSN 1468-0017. doi: 10.111 1468-1668000 1997..999..b00222... URL http://dxx
htttp:/ddx.do..oom doi. wtt.:oioo.....111111111...
1468 0017 1994. T300225.X
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large
graphs, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Alfred Horn On sentences which are of direct unions algebras. Journal of Symbolic Logic, 16(1):14-21, Mar 1951. ISSN 1943-5886. doi: 10.2307/2268661. URL
20g/10.2307/26665
Dicuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionalliyy 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 ground- ing: an unsupervised, developmental approach to connectionist sentence processing. Connection Science, 24(1):25-55, Mar 2012. ISSN 1360-0494. doi: 10.
URL
http://dxx doi. dwt.: 0000000000000000000 00091 2012. 2012.664121 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/v//614-181. URL /ttp:://tdss doi 10. 11tp//10.111///11411111111
Yoon Kim, Yacine Jernite, David Sontag, and Alexander M. Rush. Character-awan neural language models, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Yujia Li, Daniel Tarlow, Mare 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 Empirical Methods in Natural Language Processing, 2018. doi: 10.18653/v 1/d18- 1362. URL http:: //tp://xxx..m doi. woo.orgggl0... 20rg/10.10 18653/ v1 1
11

---

Published as a conference paper at ICLR 2022
Sijie Mai, Shuangjia Zheng, Yuedong Yang, and Haifeng Hu. Communicative message passing for inductive relation reasoning, 2020.
Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning 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äschel. Learning reasoning strategies in end-to-end differentiable proving. In ICML, volume 119 of Pro- ceedings of Machine Learning Research, pp. 1938-6949, PMLR, 2020b.
Raymond 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-interpretivee 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 progranming, 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-14135 1475, Online, July 2020. Association for Computa- tional Linguistics. doi: 10. 1001186661112022.aclmmm 135. URLhttps: http://wwwwwllll..cccccco aclweb. org/
anthology hotoollyyy22020/
main.... 135
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. (RNNLJogic: Learning logic rules for reasoming on knowledge graphs. In International Conference on Learning Representations, 2021. |
Tim Rocktäschel 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. 607. Springer, 2018.
Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, 45(1 1):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, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Si- monyan, and Demis Hassabis. Mastering chess and shogi by self-play with general reinforce- ment learning algorithm, 2017a.
David Silver, Julian Schritwieserr, 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)3354-355 2017b.
Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. Clutr: A diagnostic benchmark for inductive reasoning from text. Empirical Methods of Natural Language Processing (EMNLP), 2019.
12

---

Published as a conference paper at ICLR 2022
Koustuv Sinha, Shagun Sodhani, Joelle Pineau, and William L. Hamilton. Evaluating logical gen- eralization in graph neural networks. 2020.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yur 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 rea- soning. In Hal Daumé 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::/proceeiings..u http:ceeeinngg.....prss/s/////se pre.s//99e///
teru20a. html
Théo Trouillon, Christopher R. Dance, Johannes Welbl, Sebastian Riedel, Éric 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 hyper- networks. 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 all you need, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 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-71555 Jul 2019. ISSN 2159-5399, doi: (aa116699aaai//300
33017152. URL/http: /x doi. www.oogg//....o..... 160.1...............11 6099 aaai 20000//aaa..33111.....1 330113311100
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.
13

---

Published as a conference paper at ICLR 2022
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 summarized in Table and the statistics of GraphLog are summarized in Table g
Table Statistics of CLUTRR datasets.
Dataset
#relations
#Train
#Test
CLUTRR
22
10,094
900
C
22
15,083
823
Table Statistics GraphLog datasets. NC: number classes. AN: average number of nodes. number 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
147
3.16
8.16
8.89
5000
1000
World
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
194
4.29
11.5
13.0
5000
1000
World
4.66
16.3
20.9
5000
1000
Re 0
12
631
3.91
28.8
72.9
1000
200
Re
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, e 0.003, 60 = 0.6, 11 = 0.3, V/2 -0.05, v3 -0. 04 -0.3, UTneg -1, = -1.2, and UT 0.1 or 0.35 or 0.8 depending the dataset we investigate. For example, since there is no simple data in Re 2, we use pos = 0.8 instead to encourage R5 memorize uncertain rules.
A.3 IMPLEMENTATION DETAILS
We have mentioned the scoring scheme 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, RS only needs one step. We give an extra simple true reward Utrue to the action to consolidate the corresponding rule in the memory. The other optional hyperparameter is simple wrong allowance Uwreng- It can be applied when the rule collected from simple sample is not accordance with the existing rule in the rule memory.
Besides. speed up training, sort all the training samples by their maximum resolution paths, and train the ascending order of the maximum resolution path in the first epoch. Thus, some ground truth rules be quickly collected from simple data at early stage.
14

---

formed by hyperedges, where hyperedge refers Published as a conference paper at ICLR 2022
Input Graph
Hash
Body Dody:1
Head
Scom
(0
4.000
-0.197
Paths between query nodes
quory nodes
Path
Path
Action: (r2,00)
pairs state
features
Number
Whether the obtained rules
Number of occurrence
Whether the obtained rules
Figure 4: Illustration of the state and the state tramsition after taking an action.
A.4 AN EXAMPLE OF STATE TRANSITION IN THE DECISION-ME MAKKING PROCESS
Figure 4 gigeess a trivial example to illustrate how the state constructed and the state transition after applying action. As shown in Figure 2 and Section 2.1 the state represents (m n)(m + n) relation pairs and features.
this trivial example, we consider m 3, n = and & = for 1 allocated invented
reasoning task, which means there relation, thus in total 4 x 4 = 16 relation pairs. We also consider the two features to the number of occurrences and whether the relation pair is the obtained rules. Please be noted that we only compute the state features for the relation pairs in the paths. This is why U1 + To is in the rules hash table but it is not counted when deciding whether relation pair is in the obtained rules before taking the action.
3 known relations, and
A.5 EXTENDING TO COMPLEX DOMAINS
Handling P + In Section we explained that R5 realizes Horn clauses by firstly finding paths based on query, and then omitting the entities and represent the long clauses by the composition of short clauses u pi A Pj- We want to make note here R5 is also able to represent the very short clause <- p: by adding a dummy relation Tdm to the state described Section 2.1 and the corresponding predicates will be Pdm Thus, pi can be represented by P p Pdm This has been implemented in the code.
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, RS has the potential to handle triadic relations and netwoks. A typerr-etwort
to the relationship among data points that could go beyond pairwise, i.c., three or more objects are involved in each relation predicate (Tu 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 ro(2o, Ii, .22) and ri (2 I2, I7). where x; entities, part of the path can be To, 7'1. 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- baaeddding-baeedd methods, which can always return relation type with the least loss, it possible that R5 cannot give known
15

---

Published as a conference paper at ICLR 2022
relation 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 valid prediction. We define the invalid prediction ratio as the ratio that R5 fails to return a known relation.
When human is not able to make decisions based on logic, he may need the help of intuition. Sim- ilarly, we combine R5 with R-GCN, GNN-based model, which is not able to explicitly reason to make predictions (similar the results can be further improved when R5 is com- plemented by a GNN. Besides, R-GCN takes node embeddings into account, which may help to im- prove the predictions that require node properties.
Table Results of augmenting R5 with R-GCN.
Re 1
Re 2
World 32
R-GCN
0,250
0.371
0,596
human's 's intuition). see if
RS
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, node/relation embedding dimension of 200, 20 training epochs, 4 layers, and a dropout rate of 0.1.
Thole|Sshows 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.c., 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 Table 11: Results on CLUTRR, trained on stories of of lengths {2 and evaluated stories of lengths lengths {2, 3, 4} and evaluated on stories of lengths
{4,..., 10). [*] means the numbers are taken from {5, ..., 10}. ['] means the numbers are taken from
CTP's paper. [1] means fine-tuned on long stories.
CTP's paper. [t] means fine-tuned on long stories.
4Hops
SHops
6Hops
THops
SHops 9Hops
10Hops
5 Hops
6 Hops
Hops
8 Hops
9 Hops
10 Hops
02
02
98: 03
06 .77-001
.98-.03
.974.03
R5
99=-02
99H:00
99:9.03
10:.00
.99:-02
.98-03
CTP,
984.02
984.03
97:2.05
96dt
94:::05
891:00
89:5.07
CTP,
992.02
964.04
97th 04
984.00
974:004
95=.04
CTP."
991.02
991.01
.9:202
9612.
941:00
.89:
08
990..07
CTP,"
992.04
994.03
97:h 03
95:..06
931-07
.1==00
CTPx
97+
974.03
96:-06
98
93 05
900+
06
.9++.06
CTP
98--04
04
97+
98 06
94--08
93+ 08
.90=09
GNTP'
1911188
451.21
33:1.23
.374:21
.32. 20 331..19
.314.22
GNIP"
688.28
.3.1.34
.621.31
.5911.3
.71.33
.2==.32
GAT;
921.01
.734.04
.56.1.44
.551..04
541.00
.55..0
04
.50.1.01
GAT
982.01
86.1.04
.7911
.75...0
.731:02
.72
GCN;
84:1.04
61::00
.51::02
AW::
A5::05
474
05
.41:.04
GUN; 882
78:t.02
60::: 012
.57:2.02
599: 014
.1==:02
RNNI
934.03
91:.03
7792.08
82::.06
.75
07
64.1.07
RNN; 96:203
.874.09
.82 00
7334.09
65t..15
.67=.16
LSTM;
1.02:00
1.0..00
.5:2.3
912.04
881..08
08 841109
LSTM; 1.0::01
.991.02
.9:1
.961.01
9411:06
.922007
GRU?
921.05
88.1.06
.78.109
27..09 .741.08
6611.
651.08
GRU?
962.02
.58.1.03
.8111:04
.791.06
.751.08
.782.04
CNNH;
941.03
86.1.6
.77..08
724.08 .611.09
.9.1.
5911.09
CNNH
1.01:000
.991.01
.961
.111.04
.891.00 04
.872.04
CNN
934.00
86.1.7
84...9
79..08
177..10
.6.1.09
11
CNN 1.0::00
.98.1.01
.9.1.02
.924.03
891.00
.87.004
MHA:
.11.00
.761.04 .742005
70:.04
.912.03
641.00
66.1.02
MHA
88:
.83:.005
.76
72:..04
.741:05
.70:003
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 [3] we have an invented relation unknown-44. With this intermediate relation introduced, we can get a clause with three atoms in its body, i.c., r_6+- (r_9, r_3, x_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 find
pair, which is different from the target relation r_13 provided in the test set. Furthermore, that there is no ground truth rule in this world to allow the prediction of x 13 by human deduction. Neither can R5 deduct 1 13.
16

---

Published as a conference paper at ICLR 2022
Table 12: Detailed breakdowns of deduction steps by RS CLUTRR.
Target Relation
Deduction steps (head
body)
(Jason daugkter, Stephanie) == (Jason wife, Ruth, Ruth
denghter, Stephanic)
Jason
Evelyn
(Jason
Evelyn) (Jason dowphierr, Stephanie, Stephanie zann, Evelyn)
(Jeff' mother
Ruth) 4= (Jeff Atster, Gloria, Gloria mother, Ruth)
Jeff sont, Cristina
(Jason
Cristina) (Jason desigtter, Stephanie, Stephanie andd, Cristina)
(Ruth
Cristina) (Ruth huzzand,, Jason, Jason
Cristina)
(Jeff aunt
Cristina) 4u (Jeff' mother, Ruth, Ruth sister Cristina)
(Peter stator
Brundi) <= (Peter Arother, Michael, Michael abater, Brandi)
(Mark stater
Brundi) 6- (Mark Seother, Peter, Peter
stater, Brandi)
Carmelita
Chuck (Carmelita
grandeon Mark) (Carmelita deughter, Martha. Martha 20m, Mark)
(Carmelita sranddesphiter, Brandi) (Carmelita grandaon, Mark, Mark eueer Brandi)
(Carmelita daughter, Elizabeth) * (Carmelita granddaughter, Brandi, Brandi _ Elizabeth)
(Carmelita
Chuck) (Carmelita daaghter, Elizabeth, Elizabeth Chuck)
Table 13: Detailed breakdowns of deduction steps by R5 on Graphl.og.
Target Relation
Deduction steps
r.2 + r.13,
r.1 r.22,
4=9 + (r.3,r.6)
r_16
=r
r 16
r (r 13)
r r1 (r 20)
13 < (r.
r.6
unknown.44 (t33,19)
r.6 < (r.3.
r_ + rr.3,
r.6 + (r.9, unknown.44)
Table 14: Wrong relation predictions by on GraphL.gg.
Target Relation
Prediction
Deduction steps
(r.20, r.13) (r.16, r.6)
r_13
r3
1.19 <= (r 15,
r.5
r_18
r_17 4= (r_19, r.4)
r-18 < r.17)
In the second example, 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]. J. Yet, r-18, although correct, does not exactly match the target relation 5 provided by the test set. We note that there is not any ground truth rule provided by the dataset whose head is 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 r from the resolution path [r.8, 15, 8, 4]:
r.10 (r.8, r. 11 x5
r.5+ (r.8,r.18).
where the first two rules in bold are in the ground truth rules, while the third is not.
17

---

Published as a conference paper at ICLR 2022
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 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, 2. A ... Ri (21,X), where each predicate strictly contains entities. Whereas, R5 able to consider predicates with any number of entities as explained in
Appendix A..5
Moreover, many RL Path- Path-finding Agents (Xiong et al. 2017 Chen ct al. 2018: Das et al. 2017 Lin et al. 2018 Shen 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 termi- nation 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 single relation. The criterion clear.
However, R5 faces some challenges to generalize to KB reasoning. Apart from the ones mentioned in Section currently, R5 does not generate probabilities or scores for 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 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 topic that needs to be investigated. Due to these challenges, leave the application to KB as future work.
Knowledge Graph
F COMPARISON WITH NEURAL-LP AND RNNLOGIC
Neural-LP Yang et 2017) a neural logic programming method and RNNLogic (Qu 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 an outstanding disadvantage for systematicity problems.
Table 15: Comparison with Neural-LP and RNNLogic.
Model
GraphLog World 17
GraphLog Re
R5
0.947
0.665
Neural-L.P
0.057
0.080
RNNLogic w/o emb
0.606
0.348
We tweaked the code of RNNLogic, which was originally designed for entity ranking, to predict and rank relation 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 powerful server, beyond which there was mee-oo-mmmory issue. (For instance, setting T for RNNLogic on GraphLog Re 0 requires more than 130 G memory.) We report its best result in Table 15 which achieved when = 5. It shown that R5 substantially outperforms RNNLogiC, which is fact not designed for this task. Similarly 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%.
18

---

Published as a conference paper at ICLR 2022
G EXTRA FEATURES TO RECORD THE MAX/MIN NUMBER OF OCCURRENCES AMONG PATHS.
Table 16: Comparison with max/min number of occurrences among path added features.
Model
GraphLog World
GraphLog Re
R5
0.947
0.665
R5 with extra features
0.941
0.673
H
NUMBER OF PRE- ALLOCAATA INVENTED RELATIONS
Parformance changes terms of World
Perfomance changes in terms of an Re.
VVVVVV
0.68
0.94
0.92
0.62
0.30
0.5
0.58
Figure The test accuracy as the number of pre- Figure 6: The test accuracy as the number of allocated invented relations varies for World 17 in pre- allocatd invented relations varies for Re 0 in GraphLog.
GraphLog.
In this paper, we have introduced pre-allocated invented relations to capture the intermediate short rules during the Dacision-making procedure. For example, r1, r2, 72, F3 r can be decomposed into (r1,72 + inventedo). (inventedo, T3 r). The details can be found in Section 2.2 To choose n, we conduct experiments on two GraphLog datasets, World and Re O, as n varies. We use the parameters listed in Appendix A.2 except that 5 training epochs
used instead of 10 to speed up training. As presented Figure and Figure 6 R5 is able to get near optimal performance even when is small. But becomes larger, there general trend that the performance can be more stable. Intuitively, a small n makes the dynamic memory replace the invented (unknown) relations more frequently
invented relations appear, slowing down the convergence (as 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 small is required practice, can also use validation set select some n that is sufficient for each specific dataset.
19


Reviews:
[{"review_id": "f9Wj_Eu2TL", "reviewer": "Reviewer_Mm5p", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general the proposed approach is reasonable and effective for the targeted 2 tasks. The introduction of new relations, and application of RL are interesting. However, the task and model design seem to be very specific to a type of task where the relevant part of a graph (to the prediction) is restricted to a path, which can be recursively derived from the target relation. The separation of path finding and reasoning also seems to be an artifact from the specific task assumption.\n\n\nClarity related questions: \nIt would be helpful to formally define the relation prediction task.\n\nIt would be helpful to describe the path sampling procedure.\n\nHow is the model updated given the loss function l?\n\nThe state representation has one entry per relation pair. Will that lead to information loss when a relation pair appears multiple times in the path?\n\n\"recurrent reasoning agent enables us to predict ... efficiently\" -- it is more efficient than what approach? and why?\n\nTable 4 and 5: given that the rule recalls of R5 are almost 100% why the accuracy much lower than 100%?\n\n", "summary_of_the_paper": "This work explores a rule learning approach (R5) for 2 relation prediction tasks (CLUTRR and GraphLog). The proposed approach starts by finding connecting paths between the two query entities. Then it recursively merge relation pairs until it consists of a single relation output. The merging process is controlled by a policy/value network trained with episodic rewards. The rules are induced whenever the output relation matches the gold relation -- in a fashion similar to that of curriculum learning. \n\nExperiments show that R5 generalizes better than previous approaches such as Graph Attention Networks (GAN) and Conditional Theorem Provers (CTPs) especially when generalizing to paths longer than those from the training set.\n", "summary_of_the_review": "An interesting approach with good results for a limited task setup.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "crJ7Br_JVP", "reviewer": "Reviewer_dUTD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Program induction is a hard problem, especially for large-scale tasks in noisy\ndomains. This problem can be formulated as a Relational Pathfinding task [1], which\nhas been studied for many years in the area of Inductive Logic Programming. In\nStatistical Relational Learning there is also a missing related work that\nsearches for grounded relational paths first and then applies machine learning\nto extract first-order logical rules [2].\n\nCompared to previous works in this direction, the main contribution of this\nwork is applying reinforcement learning in the relational pathfinding problem. The\nproposed approach works surprisingly well in the experiments, and the combination of \nneural-guided heuristic learning for MCTS and the symbolic rewarding method perform good\nin the relational pathfinding problem.\n\nThe main weakness of relational pathfinding is the grounding problem, i.e., for\neach training example, the algorithm needs to search for ground paths before\ntraining. Besides, the pathfinding algorithm may suffer from incompleteness if\nthe hypothesis has some complex structures, e.g., if there are some useful\nrelations do not showing in a path (node \"z\" in p(x,y)<-q(x,y),r(x,z)), or if\nthere exists higher-order primitive predicates or triadic predicates. Another\npossible weakness is that reinforcement learning usually requires large numbers\nof training epochs, especially when learning the heuristics for program\ninduction.\n\n### Some minor issues:\n- \"unknown relations\" should be called \"invented predicates/relations\", following the\n  convention in the area of program induction;\n- The algorithm implicitly assumes all rules are using the same template, which\n  is a dyadic chain meta-rule [3], which could result in incompleteness [4]\n  (i.e., some hypotheses can never be learned), I think this should be made\n  clear in this paper.\n- Following my last point, the proposed method seems can only learn dyadic chain\n  rules in datalog (e.g., every rule in the target hypothesis have the form of\n  \"p(x,y)<-q(x,z), r(z,y)\", and the language is function-free). Is it possible to extend it to complex domains?\n- The learned policy can not be transferred to other tasks (e.g., adapt from one\n  task to another task, or from one target relation to another one).\n\n### References:\n1. Bradley L. Richards and Raymond J. Mooney. Learning relations by pathfinding.\n   In Proceedings of the 10th National Conference on Artificial Intelligence,\n   pages 50–55, San Jose, CA, July 1992.\n2. Wang-Zhou Dai and Zhi-Hua Zhou. Statistical unfolded logic learning. In:\n   Proceedings of the 7th Asian Conference on Machine Learning (ACML’15), Hong\n   Kong, 2015, JMLR: W&CP 45, pp. 349-361.\n3. S.H. Muggleton, D. Lin, N. Pahlavi, and A. Tamaddoni-Nezhad.\n   Meta-interpretive learning: application to grammatical inference. Machine\n   Learning, 94:25-49, 2014.\n4. Andrew Cropper and Stephen H. Muggleton. Logical minimisation of meta-rules\n   within meta-interpretive learning. In Proceedings of the 24th International\n   Conference on Inductive Logic Programming, pages 65-78.\n   Springer-Verlag, 2015. LNAI 9046.\n", "summary_of_the_paper": "This paper presents a novel method for rule induction. The main idea is to apply\nreinforcement learning in the task of relational pathfinding within a finite\nHerbrand base. The reinforcement learner uses MCTS to find the best routes to\nestablish the path in between the two arguments of training examples, while the\nuseful actions (which are length-two relational paths) are maintained in a hash\ntable as the induced ruleset. Experimental results has shown the effectiveness\nof the proposed method.", "summary_of_the_review": "This paper presents a novel algorithm to solve program induction formulated as a\nrelational pathfinding problem. The proposed approach outperforms existing rule\ninduction methods in several benchmark datasets. It has missed several important\nreferences and needs further clarification, so I would like to recommend to\naccept if the authors can fix those problems.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7rBSXHpWMfo", "reviewer": "Reviewer_TLJz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths  \n\nS1 The dynamic rule memory module is interesting.\n\nS2 Detailed ablation study and case study.\n\nS2 The paper is well written and well organized.\n\nWeaknesses\n\nW1 RL agent aims to seek long-term and maximum overall reward to achieve an optimal solution. However, this paper aims to divide the long-term decision into independent short-term decision. Therefore, I don’t see why RL should be used in this scenario.\n\nW2 Too much reliance on heuristics. For example, it utilizes statistical features, such as the number of occurrences to represent relation pairs. \n\nW3 How to recover the logical rule is unclear to me. Should we enumerate over the whole rule space to select the rules with the highest score?\n\nW4 How do the authors handle uncertainty during the deduction is unclear. It is possible for a two relation sequence to have multi heads. For example, given two relation sequences hasAunt and hasSister, both hasMother and HasAunt can be the head. How can the proposed solution solve the multi head scenario?\n\nW5 The author should discuss more about how to choose the value of n (number of unknown relations). Intuitively, a small n may reduce the expressiveness of the model while a big n may cause computational inefficiency. Choosing the value of n could be a tricky problem.\n\nW6 Lack of some representative baselines. For example, NeuralLP, RNNLogic are missing.\n\nW7 Datasets include too few relations.To show the scalability of the proposed model, it will be better to conduct experiments on datasets with more relations e.g., FB15k.", "summary_of_the_paper": "The author investigates the rule learning problem and  proposes R5, a reinforcement learning  based framework to reason over relational graph data and explicitly mines underlying compositional logical rules from observations. It mainly contains two components: RL agent to model rule learning as a sequential decision-making problem and a dynamic rule memory module to maintain and score candidate rules during the training of the reasoning agent.\n", "summary_of_the_review": "The author investigates an interesting problem, logical rule learning. It also proposes an interesting idea to decompose the long path into small pieces to recurrently learn rules. Although the idea is interesting, the model and the experiments are less convincing as pointed out in the weaknesses. It will be better for the author to clearly illustrate the reasoning why they choose the  RL model to learn rules and how they handle uncertainty during the deduction. They also need to include more baselines and larger datasets to make the experiments more convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: A novel method is described that uses RL to search for a rule set which predicts multiple relations at once for KBC-like problems.  The rules can include latent predicates, which reduces the complexity of individual rules, similar to Cropper & Muggleton's (2015) meta-interpretive learning framework, which is usual for rule-learning systems.  Another novel aspect is use of a cache memory for rules.

Pros
 - the idea of using RL instead of carefully-designed discrete search for symbolic learning systems is a very nice novel idea
 - the experimental results are strong

Cons
 - the benchmarks are synthetic (although GraphLog does at least include noise)
 - although the Cropper and Muggleton work is cited the relationship between the search spaces of the two systems is not discussed - this should be corrected in the final version.
Decision: Accept (Spotlight)