GraphLog: A Benchmark for Measuring Logical Generalization in Graph Neural Networks
Authors: Koustuv Sinha
Shagun Sodhani
Joelle Pineau
William L. Hamilton
Venue:  (2021)
Keywords: graph neural networks
dataset
benchmark
logic

Abstract: Relational inductive biases have a key role in building learning agents that can generalize and reason in a compositional manner. While relational learning algorithms such as graph neural networks (GNNs) show promise, we do not understand their effectiveness to adapt to new tasks. In this work, we study the logical generalization capabilities of GNNs by designing a benchmark suite grounded in first-order logic. Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics, represented as knowledge graphs. 
GraphLog consists of relation prediction tasks on 57 distinct procedurally generated logical worlds. We use GraphLog to evaluate GNNs in three different setups: single-task supervised learning, multi-task (with pretraining), and continual learning. Unlike previous benchmarks, GraphLog enables us to precisely control the logical relationship between the different worlds by controlling the underlying first-order logic rules. We find that models' ability to generalize and adapt strongly correlates to the availability of diverse sets of logical rules during multi-task training. We also find the severe catastrophic forgetting effect in continual learning scenarios, and GraphLog provides a precise mechanism to control the distribution shift. Overall, our results highlight new challenges for the design of GNN models, opening up an exciting area of research in generalization using graph-structured data.

Under review as a conference paper at ICLR 2021
GRAPHLOG:
A BENCHMARK FOR MEASURING LOG- ICAL GENERALIZATION IN GRAPH NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Relational inductive biases have a key role in building learning agents that can gen- eralize and reason in compositional manner. While relational learning algorithms such as graph neural networks (GNNs) show promise, we do not understand their effectiveness to adapt to new tasks. In this work, we study the logical generalization capabilities of GNNs by designing benchmark suite grounded in first-order logic. Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics, represented as knowledge graphs. GraphLog consists of relation prediction tasks on 57 distinct procedurally generated logical worlds. We GraphLog Log to evaluate GNNs in three different setups: single-task supervised learning, multi-task (with pre-training), and continual learning. Unlike previous benchmarks. GraphLog enables us to precisely control the logical rela- tionship between the different worlds by controlling the underlying first-order logic rules. We find that models' ability to generalize and adapt strongly correlates the availability of diverse sets of logical rules during multi-task training. We also find the severe catastrophic forgetting effect in continual learning scenarios, and GraphLog provides precise mechanism to control the distribution shift. Overall, our results highlight new challenges for the design of GNN models, opening up an exciting area of research in generalization using graph-structure, data.
INTRODUCTION
Relational reasoning, or the ability to reason about the relationship between objects and entities, is considered one of the fundamental aspects of intelligence (Krawezyk et all]|[10111 2011 Halford et al. | 20100. and is known to play critical role in cognitive growth of children (Son et al. 2011] Farrington- jet al. 2007 Richland et al. 2010). This ability to infer relations between objject/ennttiiesstttaaiion and to compose relations into higher-order relations, is one of the reasons why humans quickly learn how to solve new tasks (Holyoak and Morrison 2012 Alexander 2016). The perceived importance of relational reasoning for generalization has fueled the development of several neural network architectures that incorporate relational inductive biases (Battaglia et al. [016 [Santoro et al. 2017] Battaglia et al. 2018). Graph neural networks (GNNs), in particular, have emerged
dominant
computational paradigm within this growing area (Scarselli et al.) 2008; Hamilton et al. 2017a
Gilmer al., 2017; Schlichtkrull al. 2018 Du al. 2019). However, despite the growing interest in GNNs and their promise of relational generalization, we currently lack an understanding of how effectively these models can adapt and generalize across distinct tasks.
In this work, we study the task of logical generalization in the context of relational reasoning using GNNs. One example of such a reasoning task (from everyday life) can be in the context of a family- graph where the nodes are family members, and edges represent the relationships (brother, father, etc). specific form, such as "the son of
The objective to learn logical rules, which are compositions my son is my grandson".. As new compositions of existing relations are discovered during the lifetime of learner, (e.g.. the son of my daughter is my grandson). it should remember the old compositions, even it learns new compositions (just like humans do). This simplistic example can be extended to the more complex (and yet practical) scenarios like identifying novel chemical compositions, or recommender systems, where agents have learn and retain compositions of existing relations.

---

Under review as a conference paper at ICLR 2021
Dalasel
IR
D
CG
M
Me
Mu
CL
CLEVR Johnson al 2013
X
Vision
X
Number of relations
20
CoGenT Donnsoo
X
X
Total number WorldGrupis Total number unique rules Training Query graphs per WorldGroph
57
CLU/RR Simia of ar amy
X
Text
X
X
X
76
SCAN (Lakg Barem 201
K
Text
K
5000
SQuOI (Binhim
Validation Quety gruphs per WorldGruph
Textarr Cole & a. 2015
V
Text
Testing Query graphs per WorldGruph
1000
GraphLog (Proposed)
V
Graph
Average number nodes per Query graph
14:55
Average number of adges per Query graph
17.94
Average number of triangles per Query gruph
11.27
Number of rules per WorldGrrph
20
Table 1: Features of related datasets that: 1) test com- positional generalization and reasoning, and 2) are pro- cedurally gnerated. We compare the datasets along the following axis: Inspectable Rules (IR), Diversity, Com- positional Generalization (CG), Modality and the fol- lowing training setups are supported: Supervised, Meta- learning, Multitask & Continual learning (CL).
Maximum length of resolution path Minimum length resolution path
10
Table 2:
Aggregate statistics of the worlds in GraphLog. Statistics for each individual world are in the Appendix.
We study the effect of such generalization by analyzing the ability of GNNs in learning new relation compositions, leveraging first-order logic. In particular, study how GNNs can induce logical rules and generalize by combining such rules in novel ways after training. We propose benchmark suite, GraphLog, that is grounded in first-order logic. Figure shows the setup of the benchmark. Given set of logical rules, we create a diverse set of logical worlds with a different subset of rules. For each world (say Wa), we sample multiple knowledge graphs (say ),), The learning agent should learn to induce the logical rules for predicting the missing facts in these knowledge graphs.
Using our benchmark, we evaluate the generalization capabilities of GNNs in the supervised setting by predicting inductively unseen combinations of known rules within specific logical world. We further analyze how various GNN architectures perform in the multi-task and continual learning scenarios, where they have to learn over a set of logical worlds with different underlying logics. Our setup allows us to control the distribution shift by controlling the similarity between the different worlds, in terms of the overlap in logical rules between different worlds.
Our analysis provides the following insights about log- ical generalization capabilities of GNNs:
W
Two architecture choices for GNNs strongly (and pos- itively) impact generalization: 1) incorporating multi- relational edge features using attention, and 2) mod- ularising GNN architecture to include parametric representation function, to learn representations for the relations using knowledge graph structure.
GA5
In the multi-task setting, training a model on a more diverse set of logical worlds improves generalization and adaptation performance.
All the evaluated models exhibit catastrophic forget- ting. This indicates that the models are not learn- ing transferable representations and compositions and just overfitting to the current task highlighting the challenge of lifelong learning context of logical generalization and GNNs.
Figure 1: GraphLog setup: A set of rules (grounded in propositional logic) is par- titioned into overlapping subsets. It is used to define unique worlds. Within each world WE, several knowledge graphs g (governed by rule set of W are generated.
2 BACKGROUND AND RELATED WORK
GNNs. Several GNN architectures have been proposed to learn representations of the graph inputs
(Scarselli et al. 2008; Duvenaud et al. 2015 Defferrard et al. 2016 Kipf and Welling 2016 Gilmer
et al.) 2017; Hamilton et al.) 2017b] Schlichtkrull et al., 2018). Previous works have focused on evaluating GNNs in terms of their expressive power (Barceló et al. 2019 Morris et al. 2019 Xu
et al. 2018), usefulness of features (Chen et al. 2019). and explaining their predictions (Ying et al.
2019 Complementing these works, we evaluate GNN models the task of logical generalization.
2

---

Under review as a conference paper at ICLR 2021
Knowledge graph completion. Many knowledge graph datasets are available for relation prediction tasks (also known as knowledge base completion). Prominent examples include Freebase 15K (Bordes 2013), WordNet (Miller (995). NELL (Mitchell and Fredkin 2014), and YAGO (Suchanek et al. 2007; |offart et al. 2011 Mahdisoltani et al., 2013). Since these datasets are derived from real-world knowledge graphs, they are generally noisy and incomplete, and many facts are not available in the underlying knowledge bases (West et al., 2014 Paulheimm (017). Moreover, the underlying logical rules are often opaque and implicit (Guo al. 2016), thus reducing the utility of these datasets for understanding the logical generalization capability of neural networks.
et al.
Procedurally generated datasets for reasoning. Several procedurally generated benchmarks have been proposed to study the relational reasoning and compositional generalization properties of neural networks (Table(T). These datasets provide a controlled testbed for evaluating compositional reasoning capabilities of neural networks in isolation. Based on these insightful works, we enumerate the four key desiderata that, we believe, such a benchmark should provide:
1. Human interpretable rules should be used generate the dataset. 2. The datasets should be diverse, and the compositional rules used to solve different tasks should be distinct, so that adaptation on a new task is not trivial. The degree of similarity across the tasks should be configurable to evaluate the role of diversity in generalization.
3. The benchmark should test for compositional generalization, which is the ability to solve unseen combinations of existing rules, thus generalizing through the composition of known concepts. The benchmark should support creating a large number of tasks and enable a more fine-grained inspection of the generalization capabilities of the model in different setups, e.g., supervised learning, multi-task learning, and continual learning.
As shown in Table I GraphLog is unique in satisfying all of these desiderata. We highlight that unlike previous works which have been largely focused on the image and text modalities, GraphLog one of the unique attempts to test logical generalization on graph-structured data using Graph Neural Networks. CLUTRR (Sinha et al., 2019) also provides similar underlying graphs in the text corpus, although GraphLog log is different based on the following properties:
CLUTRR consists of single rule world which in turn contains only 15 rules. GraphLog extends the concept to more general framework where a user can define how many rules can occur a single world, as well as define multiple such worlds.
GraphLog allows building multiple worlds consisting of either the same, overlapping, or distinct set of rules which allows practitioners to test multi-task and continual learning scenarios in minute detail by controlling the distribution shift, which is a key difference with CLUTRR.
CLUTRR is built on a static set of relations (22 family relations) while GraphLog can contain any number of such relations since it's flexible generator along with dataset.
Synthetic Graph Generation. Synthetic graph generation is extensively studied using various neural generative approaches for scale-free random graphs YYou et al. 2018 Liao et al.) 2019). Unlike these
approaches. GraphLog built using a procedural graph generator. which allows us to control the
logical validity of the query graphs, which is defined in Section 3 Control over logical validity is
easier in synthetically generated datasets, which are used extensively Inductive Logic Programming (ILP) Rule Learning context (Cornelio and Thost 2019) [| towards Graph Neural Network evaluation, which also supports for richer distribution shift evaluation through Multi-task learning and Continual learning scenarios.
GraphLog on the other hand, is targeted
3 GRAPHLOG
Background and Terminology. We leverage terminology and definitions from both knowledge graph and logic programming literature. A graph G = (Va, FG) is a collection of a set of nodes Va and a set of edges EG between the nodes. We assume that the graphs are relational, meaning that each edge between two nodes (say u and v) is assigned a label, and can be denoted as ri(u, v) E Eg. A relation set Ri is a set of relations {r1, T2, ... TK).
3

---

Under review as a conference paper at ICLR 2021
In logic programming terms, nodes in the graph correspond constants, and edges correspond to ground atoms. Thus, as a slight abuse and mixture of notations, existence of an edge in the graph, i.e., (u, v) Eg, is equivalent to background assumption that ground atom is true (i.c., that (u, u) t-).
We define a rule set R. as set of dyadic definite Datalog clauses (Abiteboul et al. 1995) of form:
Tk(U.V) - r(( A (Z.
(1)
Note that Equation is also termed as chain-rule in logic literature. Following standard convention, we use upper-case to denote variables (e.g., the variables in Equation [I can be substituted for nodes) and lower-case for constants (e.g. to denote nodes v E VG). The relations r. form the body while the relation r'e forms the head of the rule. Path-based Horn clauses of this form represent limited and well-defined subset of first-order logic. They encompass the types of logical rules learned by state-of-the-art rule induction systems for knowledge graph completion (Das al. 2017; Evans and
Grefenstette 2017: Meilicke et al., 2018; Sadeghian et al. 2019 Teru et al. 2020 Yang ct al. 2017
Zhang et al.
2019 and are thus a useful synthetic test-bed.
We use Pg to denote a path from node to e in a graph G (i.e., a sequence unique nodes connected by edges). In logical terms, u.." corresponds to the conjunction of all the edge predicates in the path. We construct graphs according to rules of the form in [quation[] so that path between two nodes will always imply a specific relation between these two nodes. In other words, if we let Par denote the set of all finite paths in the graph G. then we have that
v.v
u. E Pa 3r; E :. (Po - ri(u, v)) A (Vr, E R (r:) -(P"" (r)(u,)))) VpG
Thus, by following the path between two nodes, and applying rules of the form of Equation according to the edges of the path, we can always resolve the relationship between the nodes.
Problem Setup. Given this setup, the task is to predict the relation between a pair of nodes. In particular, we define query (g. u, v) as follows: (i) the query subgraph g C G is a subgraph of the full graph G; (ii) the query nodes are present in the query subgraph (i.e., u, u E Vg); (iii) the edge between the query nodes is not present in the query subgraph, but the edge is present in the underlying graph (i.e.. ru(u, v) E Eg. ru(u, v) & Eg). The goal is to infer the missing edge between query nodes re(u, v). We assume that the learning agent has access to a set of training queries I1.... In C G to optimize prediction model before being tested on set of held-out queries In+1, - Intn' C G.
In knowledge graph terms, this is a form of link or relation prediction, as our goal is to infer the missing edge between two nodes. Unlike most work knowledge graph completion, we emphasize an inductive problem setup, where the query graph in each training and testing example is unique, requiring generalization unseen graphs (Teru al. 2020).
Finally, note that we will sometimes refer to the full graphs G as world graphs, in order to distinguish them from the query graphs g G. We make this distinction because GraphLog involves link prediction over several different logical worlds, denoted W = (Gw, Rw), with each defined with by its own underlying world graph Gw and rule set Rw. Our setup enables controlling the overlap between the rules in these different logical worlds, allowing for a unique ability to quantify the logical generalization capabilities of a learning agent.
3.1 DATASET GENERATION
As discussed in Section 2 we want our proposed benchmark to provide four key desiderata: (i) interpretable rules, (ii) diversity, (iii) compositional generalization and (iv) large number of tasks. We describe how our dataset generation process ensures all four aspects.
Rule generation. We create set R of possible relations and use it to create a randomly generated rule set R. such two key constraints are satisfied: (i) No two rules R can have the same body, ensuring that Equation satisfied. (ii) Rules cannot have common relations among the head and body, ensuring the absence of cyclic dependencies in rules. Generating the dataset using a consistent and well-defined rule set ensures interpretability in the resulting dataset. The full algorithm for rule generation is given in Appendix (Algorithm D
Graph generation. The graph generation process has two steps: In the first step, we sample overlapping subsets of Rw C R to create individual worlds (as shown in Figure IT. In each world, recursively sample and use rules in Rw to generate the world graph Gw for that world. This
4

---

Under review as a conference paper at ICLR 2021
sampling procedure creates diverse set of world graphs by considering only certain subsets of R. By controlling the extent of overlap between the subsets of R (in terms of the number of common rules), can preciscly control the similarity between the different worlds. The full algorithm for generating the world graphs and controlling the similarity between the worlds is given in Appendix (Algorithm and Section A.2)
In the second step, the world graph Gw in each world is used to sample a set of query graphs G. (g),,-. ..N) for that specific world (shown as Step (a) in Figure 2). A query graph 9i is sampled from Gw by sampling a pair of nodes (u, v) from Gw and then by sampling a path Pow The edge (u, v) between the source and sink node of the path provides the target relation for the learning model predict. To increase the complexity of the sampled gi graphs (beyond being simple paths), we also add nodes to Ji by sampling neighbors of the nodes on PGw such that no other shorter path exists between u and v. Algorithm 4 (in the Appendix) details our graph sampling approach. Note that this sampling process leads to rich and complex graph structures, including cycles and motifs (see Figure 7(a) in Appendix for example of graphs).
v,0
u.e
GraphLog ogg Dataset Suite. We use the above data generation process to instantiate dataset suite with 57 distinct logical worlds with 5000 query graphs per world (Figure []. The dataset is split into train, validation, and test worlds. The query graphs within each world are also split into train, validation, and test sets (Table 2). Though we instantiate 57 worlds, the GraphLog generator can instantiate an arbitrary number of worlds and has been included in the supplementary material.
3.2 SETUPS SUPPORTED IN GRAPHLOG
Supervised learning. A model is trained (and evaluated) on the train (and test split) of a world. The number of rules grows exponentially with the number of relations K, making impossible to train on all possible combinations of the relations. We expect that perfectly systematic model inductively generalizes to unseen combinations of relations by training only on subset of combinations.
Multi-task learning. GraphLog provides multiple logical worlds, with their training and evalua- tion splits, A model is trained on (and evaluated on) the train (and test) splits of several worlds GraphLog enables us to control the complexity of each world and similarity between the worlds to evaluate how model performance varies across similar vs. dissimilar worlds. GraphLog is designed to study the effect of pre- training on adaptation. In this setup, the model is pre- pre-trained on the train split of multiple worlds (Wi.... War and fine-tuned on the train split of the unseen heldout worlds (War (Ws+1;'... W.). The model is evaluated the test split of the heldout worlds. GraphL.gg enables mimicking in-distribution and out-of-dis -attr--diittiibttion train (and test) scenarios and quantify the effect of multi-task pre-training for adaptation performance.
Was). (W,,...,
Continual learning. The model is trained on a sequence of worlds. Before training on a new world, is evaluated on all the worlds that has trained on so far. Given the challenges involved in continual learning Thrun and Prati 2012: Parisi et al., 2019 De Lange et al., 2019; Sodhani et al.) 2019), we do not expect the models to perform well on the previous tasks. Nonetheless, given that we are evaluating the models for relational reasoning and our datasets share relations, we expect the models to retain some knowledge of previous tasks. We use the performance on the previous tasks to infer the models learn to solve the relational reasoning tasks or just fir to the current dataset distribution.
Controlling similarity. An unique feature of GraphLog is it allows practitioners to control the distribution shift when evaluating multi-task and continual learning baselines. In GraphLog the diversity of worlds can be controlled via similarity. Concretely, the similarity between two worlds W and W is defined Sim(W' Wi) |R' n RR,, where W. and W, are the graph worlds and RR and R2 are the set of rules associated with them. Thus GraphLog enables various training scenarios training on highly similar worlds or training on mix of similar and dissimilar worlds. This fine grained control allows GraphLog to mimic both in-distribution and out-of-distribution scenarios during training and testing. It also enables us to precisely categorize the effect of multi-task pre-training when the model needs to adapt to novel worlds.
2 DDue to the current formulation (Equation 2 GraphLog is restricted to have at most a single edge between a task simpler in order to analyze the effects of generalization
pair of nodes. This formulation is chosen to make the in detail. In future work, we will be exploring the effect of multiple edges using this benchmark, which is characteristic of many real-world knowledge graphs
5

---

Under review as a conference paper at ICLR 2021
4 MODELS
In this section, describe the message passing graph neural networks that we evaluate on GraphLog benchmark. These models take as input the query (gi, v) and a learnable relation embedding Fy E R (Step (d) and (e) in Figure 2) and output the relation as k-way softmax (Step (f) in Figure 2) We use both uttention-based and non non-attention based models.
Relational Graph Convolutional Network (RGCN). For relational graph, the RGCN model (Schlichtkrul et al. 2018) is natural choice for a baseline architecture. In this approach, we iter-
ate a series of message passing operations: ha ReLU (Er,er DUNE,R, (w) H4 X1 T X3 h ")
where h E Rd denotes representation of node u at the tth layer of the model, T R xdxd is a learnable tensor, E IR is relation representation, and Nr, (u) denotes the neighbors of u (related by rz). j = 1, 2, 3 denotes multiplication across the modes of the tensor. RGCN model learns a relation-specifie propagation matrix, specified by the interaction between relation embedding and shared tensor T,
Edge-based Graph Attention Network (Edge-GAT). Many recent works have highlighted the importance of the attention mechanism, especially in the context of relational reasoning (Vaswani et al. 2017 Santoro et al. 2018 Schlag et al. 2019). Motivated by this observation, we investigate an extended version of the GAT (Veličković et al., 2017), in order to handle the edge types. We complement GAT by incorporating gating via LSTM (Hochreiter and Schmidhuber [997) and where the attention is conditioned on both the incoming message (from the other nodes) and the re-
lation embedding (of the other nodes): my( Em.R EvEN,, (a) a (h!!-)), h ((-1),)), .r) ,h!''
LSTM(mM(2)) b () Following the original GAT model, the attention function uses concate- nated input vectors. We refer to this model as the Edge GAT (E-GAT) model.
Query and node representations. We predict the relation for query (gi, u) by concatenating (K) h Figure D. In absence of node features, randomly initialize all the node embeddings in the GNNs.
(K) (final-layer query node embeddings) and applying a feedforward network (Step (f) in
Representation functions GNN models described above expect to learn d-dimensional relation repre- sentations. We can further re-structure them notation- wise into two modules: a) Representation module which is represented as function fr : Gw x R + Rdd that maps logical relations within a particular world W to d-dimensional vector representations, and b) Composition module, which is function fe Gw VGw X VGw x [dd + R. that learns to compose the relation representations learned by Jr and answer queries over knowledge graph. In this formulation, the relation embedding matrix r; E Rd used in RGCN and Edge-GAT can be thought of the output of a direct parameterization module (Pa ram). which is devoid of any input and simply returns the embeddings from a lookup table. Thus these two baselines can be redefined as Param RGGNNRGGG and Param-B-CAT models, where RGCN and E-GAT T are the composition modules. A major limitation of this approach is that the relation representations are optimized specifically for each logical world, and there is no inductive bias towards learning represen- tations that can generalize.
G
(a)
(b)
G
(c)
fc
Gg
(4)
(g.
fe
S
Figure 2: Overview of training process: (a): Sample multiple graphs from Gw. (b): Con- vert the relational graph into extended graph Gw- Note that edges of different color (denot- ing different types of relations) are replaced by node of same type in Gw. (c): Learn rep- resentations of the relations (r) using fr (ex- tended graph as the input). In case of Param models, the relation representations are pa- rameterized via an embedding layer and the extended graph not created. (d, e): The composition function takes as input the query gs, u, e and the relational representation r. (f): The composition function predicts the relation between the nodes u and t.
Learning representations from the graph struc- ture. To define a more powerful representation func- tion, consider learning relation representations as a function of the graph Gw underlying a logical world W. We consider an "extended" form of Gw:

---

Under review as a conference paper at ICLR 2021
0.8-
CAT-E-GAT
GCN
Param-E-GAT
GAT-RGON
L-
Jr.
Accuracy
Accuracy
Test Accuracy
RCN-RGEN
GAT
E-GAT
0.534 +0.11
0.534
#0.09
0.6-
Param-RGCN
GAT
RGCN
0.474 10.11
0.502 10.09
GCN
E-GAT
0.522 10.1
0.533
20.09
GCN
RGCN
0.448 40.09
0.476 +0.09
Param
E-GAT
0.507 #0.09
#0.09
Param
RGCN
0.416
0.449 +0.07
Easy World Medium World Hard World World diffiultty
Table 3: Multitask evaluation performance when trained on different data distributions (catego- rized based on their similarity of rules: Similar (S) containing similar worlds and a mix of simi- lar and dissimilar worlds (D))
Figure We categorize the datasets terms of their relative difficulty (see Appendix). We ob- serve that the models using E-GAT as the com- position function consistently work well.
denoted Gw, which introduces new nodes (called edge-nodes) corresponding to each edge in the orig- inal world graph Gw. For an edge r(u, v) EG. the corresponding edge-node [u v) is connected to only those nodes that were incident to it in the original graph (i.c. nodes u and u; see Figure 2 Step (b)). This new graph Gw only has one type of edge and comprises of nodes from both the original graph and from the set of edge-nodes. We learn the relation representations by training GNN model on Gw and by averaging the edge-node embeddings corresponding to each relation type E R. (Step (c) in Figure 2). For the GNN model, we consider the Graph Convolutional Network (GCN) (Kipf and Welling 2016) and the Graph Attention Network (GAT) architectures. The intuition behind creating the extended -raph is that the representation GNN function can learn the relation embeddings based on the structure the complete relational graph Gw. Both the representation module and the composition modules are trained end-to-end to predict the relations. Thus, we end up with four more models to evaluate GraphLog, namely CCN-RGCN, GCN-E- EAAT, GAT-RGCK and GAT-E-GAT.
EXPERIMENTS
We aim to quantify the performance of the different GNN models on the task of logical relation reasoning, in three setups: (i) Single Task Learning, (ii) Multi-Task Training and (iii) Continual Learning. Our experiments use the GraphLog benchmark with distinct 57 worlds (Section 3 and different GNN models (Section 4. In the main paper, highlight the key results and provide the full results in the Appendix. The code is included with the supplemental material.
5.1 SINGLE TASK SUPERVISED LEARNING
We evaluate the models on all the 57 worlds, one model-world pair at a time (342 combinations). With GraphLog it is difficult for one model outperform others all the 57 datasets just by exploiting dataset-specific bias, thereby making the conclusions more robust. We categorize the worlds in three categories of difficulty- easy, moderate and difficult based on the relative test performance of the models on each world and present the results in Figure 3 (A complimentary formulation of difficulty explained in Appendix A.4).. We observe that the models using E-GAT composition function always outperform the models using RGCN. This confirms our hypothesis about leveraging attention to improve the performance on relational reasoning tasks. Interestingly, the relative ordering among the worlds, in terms of the test accuracy of the different models, is consistent irrespective of the model we use, highlighting the intrinsic ordering difficulty the different worlds in GraphLog.
5.2 MULTI-TASK TRAINING
Standard multi-task training. First, we evaluate how changing similarity among training worlds affects test performance in the multi-task setup. We train model on eight worlds and test on
7

---

Under review as a conference paper at ICLR 2021
GAT GAT
GCN GAT
0.60
6.61
Accursoy
0.35
Accuraty
6.--
0.45
Accracy
6.64
6.4-
0.40
30
Number worlds
70ro
Com
Zero
Cont
Zero Com
GAT-E-GAT
GUN-E-GAT
Param- BGGN
RGCN
Figure 5: We evaluate the effect of changing the similarity between the training and the eval- uation datasets. The colors of the bars depicts how similar the two distributions are while the y-axis shows the mean accuracy of the model on the test split of the evaluation world. We re- port both the zero-shot adaptation performance and performance after convergence.
Figure 4: We run multitask experiments over an increasing number of worlds to stress the capac- ity of the models. We report the average of test set performance across the worlds that the model has trained on so far. All the models reach their optimal performance 20 worlds, beyond which their performance starts to degrade.
three distinct worlds. In Table we observe that mix of similar and dissimilar worlds improves generalization capabilities of all the models. Similar to the trends observed in the single task setup, the GAT-EGAT model consistently performs either as good as or better than other models. The models using EGAT for the composition function perform better than the ones using the RGCN model. Figure shows how the models' performance changes when we perform multi-task training on an increasingly large set of worlds. Interestingly, we see that model performance improves as the number of worlds increased from 10 20 but then begins to decline, indicating model capacity saturation in the presence of too many diverse worlds.
Multi-task pre-training. In this setup, we pre-train the model on multiple worldy and adapt on a heldout world. We study how the models' adaption capabilities vary as the similarity between the training and the evaluation distributions changes. [igure:]conside and adaptation till convergence. As we move along the x-axis, the zero-shot performance (shown with solid colors) decreases in all the setups. This expected as the similarity between the training and the evaluation distributions also decreases. An interesting trend is that the model's performance, after adaptation, increases as the similarity between the two distributions decreases. This suggests that training over a diverse of distributions improves adaptation capability.
the case zero-shot adaptation
5.3 CONTINUAL LEARNING SETUP
We evaluate knowledge retention capability by training GNNs on sequence of worlds (arranged by relative similarity). After convergence on any world, we report average of model's performance on all previous worlds. (igure(b(a)) shows the rapid degradation in model's performance the previous worlds as it trains on new worlds, highlighting the limitation of current models for continual learning.
The role of the representation function. We also investigate the model's performance in continual learning setup where the model Icarns only a world-specific representation function or a world- specific composition function, and where the other module is shared across the worlds. In Figure/6(b) we observe that sharing the representation function reduces the effect of catastrophic forgetting. but sharing the composition function does not have the same effect. This suggests that the representation function learns representations that are useful across the worlds.
DISCUSSION & CONCLUSION
In this work, we propose GraphLog, a benchmark suite for evaluating the logical generalization capabilities of GNNs. GraphLog is grounded in first-order logic and provides access to large number of diverse tasks that require compositional generalization solve, including single task supervised learning, multi-task learning, and continual learning. Our results highlight the importance of attention
8

---

Under review as a conference paper at ICLR 2021
GAT-E-GAT
Param-E-GAT
GAT-E-GAT
Param-E-GAT
0.4
Accuracy
0.6
Accuracy
0.3
0.1
GON-E-GAT
GAT-RGON
GCN-E-GAT
GAT-RGON
0.4
Accuracy
0.4
0.2
Param-RGCN
GCN-AGCH
RGNN
0.5
0.8
Accuracy
Recurei
0.6
0.3
0.1
0.2
Worlds
Worlds
Worlds
Composttion Representation Representation Unique Camposition Shared Composition Unique Representation
Current Accuracy
Mean past accuracy
(a)
(b)
Figure 6: Evaluation of models continual learning setup. In Figure 6(a) the blue curve shows the accuracy the current world and the orange curve shows the mean of accuracy all previously seen worlds. Training on new worlds, degrades model's performance on the past worlds (catastrophic forgetting). In Figure 6(b) sharing representation function reduces catastrophic forgetting.
mechanisms and modularity to achieve logical generalization, while also highlighting open challenges related to multi-task and continual learning in the context of GNNs. A natural direction for future work leveraging GraphLog for studying fast adaptation and meta-learning the context of logical reasoning (e.g., via gradient-based meta-learning), as well as integrating state-of-the-an methods (e.g., regularization techniques) to combat catastrophic forgetting the context of GNNs.
REFERENCES
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases, volume 8. Addison- Wesley Reading, 1995.
Patricia A Alexander.
Relational thinking and relational reasoning: harnessing the power of patterning. NPJ science of learning, 1(1):1-7, 2016.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: what is required and can it be learned? arXiv preprint arXiv: 12889, 2018
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pages 4502-4510, 2016.

---

Under review as a conference paper at ICLR 2021
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01266 2018.
Yoshua Bengio. Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41-48, 2009.
Antoine Bordes, Nicolas Usunier, Alberto Garcia Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pages 2787-2795, 2013.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint arXiv:1905.04577 2019.
Cristina Cornelio and Veronika Thost. Rudas: Synthetic datasets for rule learning and evaluation tools, 2019.
Mlre-Alexandre Côté, Ákos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore. Matthew Hausknecht, Layla EI Asri, Mahmoud Adada, et al. Textworld: A learning environment for text-based games. In Workshop on Computer Games, pages 41-75. Springer, 2018.
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 with reinforcement learning. In NIPS-17 Workshop on Automatic Knowledge Base Construction, 2017.
Matthias De Lange, Rahaf Aljundi, Marc Masana, Sarah Parisot, Xu Jia, Ales Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. Continual learning: A comparative study how to defy forgetting in classification tasks. arXiv preprint arXiv: 1909. 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pages 3844 3852, 2016.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pages 5724-5734, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224-2232, 2015.
Richard Evans and Edward Grefenstette. Learning Explanatory Rules from Noisy Data. November 2017.
Lee Farrington-Fling Flint, Katherine Canobi, Clare Wood, and Dorothy Faulkner. The role of relational reasoning in children's is addition concepts. British Journal of Developmental Psychology. 25(2): 227-246, 2007.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine BooninngVollume 70, pages 1263-1272. JMLR. org, 2017.
Michelle Guo, Albert Haque, De-An Huang, Serena Yeung, and Li Fei-Fei. Dynamic task prioriti- zation for multitask learning. In Proceedings of the European Conference Computer Vision (ECCV), pages 270-287, 2018.
Shu Guo, Quan Wang, Lihong Wang, Bin Wang, and Li Guo. Jointly embedding knowledge graphs and logical rules. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 192-202, 2016.
10

---

Under review as a conference paper at ICLR 2021
Graeme S Halford, William H Wilson, and Steven Phillips. Relational knowledge: the foundation of higher cognition. Trends cognitive sciences, 14(11):497-505. 2010.
W. Hamilton, R. Ying, and J. Leskovec. Representation learning graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017a.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017b.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
Johannes Hoffart, Fabian M Suchanck, Klaus Berberich, Edwin Lewis-Kelhane Gerard De Melo, and Gerhard Weikum. Yago2: exploring and querying world knowledge in time, space, context, and many languages. In Proceedings of the 20th international conference companion on World wide web, pages 229-232. 2011.
Keith James Holyoak and Robert G Morrison. The Oxford handbook of thinking and reasoning. Oxford University Press, 2012.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 2901-2910, 2017.
Thomas Kipf and Max Welling. Semi- semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (ett:::699000000 2016.
Daniel C Krawezyk, M Michelle McClelland, and Colin M Donovan. A hierarchy for relational reasoning in the prefrontal cortex. Cortex, 4765),588-597, 2011.
Brenden M Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-see to-seqeence recurrent networks. arXiv preprint arXiv: 17000000 2017.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang. Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems, pages 4255-4265, 2019.
Farzaneh Mahdisoltani, Joanna Biega, and Fabian M Suchanek. Yago3: A knowledge base from multilingual wikipedias. 2013.
Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt, Fine-grained evaluation of rule-and embedding based systems for knowledge graph completion. International Semantic Web Conference, pages 3-20. Springer, 2018.
George A Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(1):: 39-41, 1995.
Tom Mitchell and Fredkin. Never ending language learning. In Big Data (Big Data), 2014 IEEE International Conference on, pages 1-1, 2014.
C. Morris, M. Ritzert, M. Fey, W.I. Hamilton, J. Lenssen, Rattan, and M. Grohe, Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI, 2019.
German Parisi, Ronald Kemker, Jose Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 2019.
Heiko Paulheim. Knowledge graph refinement: A survey of approaches and evaluation methods. Semantic web, 8(3):489-508 2017.
Lindsey Engle Richland, Tsz-Kit Chan, Robert G Morrison, and Terry Kit-Fong Au. Young children's analogical reasoning across cultures: Similarities and differences. Journal of Experimental Child Psychology, 105(1-2):146-1555 2010.
11

---

Under review as a conference paper at ICLR 2021
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. In Advances in Neural Information Processing Systems, pages 15321-15331, 2019.
Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap. simple neural network module for relational reasoning. In Advances in neural information processing systems, pages 4967-4976, 2017.
Adam Santoro, Ryan Faulkner, David Raposo, Jack Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy Lillicrap. Relational recurrent neural networks. In Advances in neural information processing systems, pages 7299-7310, 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Imanol Schlag, Paul Smolensky, Roland Fernandez. Nebojsa Jojic. Jürgen Schmidhuber, and Jianfeng Gao. Enhancing the transformer with explicit relational encoding for math problem solving. arXiv preprint arXiv:/910. .6.006611 2019.
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, pages 593-607. Springer, 2018.
Koustuy Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L Hamilton. Clutrr: A diagnostic benchmark for inductive reasoning from text. arXiv preprint arXiv:1908.0 21111198801777 2019.
Shagun Sodhani, Sarath Chandar, and Yoshua Bengio. On training recurrent neural networks for lifelong learning. 2019.
Ji Y Son, Linda B Smith, and Robert Goldstone. Connecting instances promote children's relational reasoning. Journal of experimental child psychology, 108(2):200-277, 2011.
Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. Yago: a core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pages 697-706, 2007.
Komal K Teru, Etienne Denis, and William Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-60999 1998-6088,40 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 171001003,. 2017.
Robert West, Evgeniy Gabrilovich, Kevin Murphy, Shaohua Sun, Rahul Gupta, and Dekang Lin. Knowledge base completion via search-based question answering. In Proceedings of the 23rd international conference on World wide web, pages 515-526, 2014.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0000 1810000866 2018
Fan Yang. Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances in Neural Information Processing Systems, pages 2319-2328, 2017.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems, pages 9240 9240-9251, 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint WrXXiv1802.0877. 2018
Wen Zhang, Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhu, Wei Zhang, Abraham Bernstein, and Huajun Chen. Iteratively learning embeddings and rules for knowledge graph reasoning. In The World Wide Web Conference, pages 2366-2377. 2019.
12

---

Under review as a conference paper at ICLR 2021
A GRAPHLOG
A.1 EXTENDED TERMINOLOGY
In this section, we extend the terminology introduced in Section 3 to introduce the term descriptor. A descriptor of query graph g is computed by concatenating the relations occurring on the shortest path from the source and sink in the query (u, v). For example, if query graph is described in the form of list of edges such as g - (0, 1,r),, ). (1,2, (1, ra). (2, 4, r.),, where r3 are the relations, then the descriptor of this graph given the query (0, 4) would be Dg 11, r2, 74. In all our train, validation and test splits, we split graphs based on the unique set of descriptors, such as to maintain inductive reasoning aspect of the task.
A.2 DATASET GENERATION
This section follows up on the discussion in Section 3.1 We describe all the steps involved in the dataset generation process.
Rule Generation. In Algorithm[] we describe the complete process of generating rules in GraphLog We require the set of K relations, which
to sample the rule set R. Then, we iterate through all possible combinations of relations in Datal.g format to sample possible candidate rules. We impose two constraints on the candidate rule: (i) No two rules in R can have the same body. This ensures consistency between the rules. (ii) Candidate rules cannot have common relations among the head and body. This ensures absence of cycles. We also add the inverse rule of our sampled candidate rule and check the same consistencies again. We employ two types of unary Horn clauses to perform the closure of the available rules and to check the consistency of the different rules in R. Using this process, we ensure that all generated rules are sound and consistent with respect to R.
World Sampling. From the set of rules in R. we partition rules into buckets for different worlds (Algorithm 2) We use simple policy of bucketing via a sliding window of width w with stride s, to classify rules pertaining to each world. For example, two such consecutive worlds can be generated as Re [R.... Ritw] and R RRi.s... Ritw+s]. (Algorithm 2 We randomly permute R before bucketing in-order.
Graph Generation. This is a two-step process where first we sample a world graph (Algorithm) 3 and then we sample individual graphs from the world graph (Algorithm ). Given a set of rules Rs- in the first step, recursively sample and apply rules in Rgg generate relation graph called world graph. This sampling procedure enables us to create a diverse set of world graphs by considering only certain subsets (of R) during sampling. By controlling the extent of overlap between the subsets of RR (in terms of the number of rules that are common across the subsets), we can precisely control the similarity between the different world graphs. By selecting subsets which have higher dissimilarity between each other, we introduce more diversity in terms of logical rules.
In the second step (Algorithm 4). the world graph is used sample set of query graphs G (91.....0 ".a....-900 9N ). A query graph gi is sampled from Gw by sampling a pair of nodes (u. v) from Gw and then by sampling a resolution path PGW The edge ru, v) provides the target relation that the learning model has to predict. Since the relation for the edge (u, v) can be resolved by composing the relations along the resolution path, the relation prediction task tests for the compositional generalization abilities of the models. We first sample all possible resolution paths and get their individual descriptors Dg:- which we split in training, validation and test splits. We then construct the training, validation and testing graphs by first adding all edges of an individual Dg: to the corresponding query graph gs. and then sampling neighbors of Pg. Concretely, we use Breadth First Search (BFS) to sample the neighboring subgraph of each node u E Ps. with decaying selection probability "y. This allows to create diverse input graphs while having precise control over its resolution by its descriptor Dg.- Splitting the dataset over these descriptor paths ensures inductive generalization.
A.3 COMPUTING SIMILARITY
GraphLog provides precise control for categorizing the similarity between different worlds by computing the overlap of the underlying rules. Concretely, the similarity between two worlds W and
13

---

Under review as a conference paper at ICLR 2021
Degree Histogram,, W: GraphLong
30:00
20:00
10200
10
Degiee
(a)
(b)
Figure 7: Figure ((a) represents graphs drawn at random from different worlds available in GraphLog Nodes in red denote the query nodes, and the nodes in blue denote the shortest path among the query nodes. Figure 7(b) represents the degree distribution of all graphs from all worlds in GraphLog..
Algorithm 1 Rule Generator
Input: Set of K relations (ri) K Define an empty rule set R
for all r; (rx K do
for all r, E {ri do
for all ræ (ri) do
Define candidate rule :: [r.. = Tk
if Cyclical rule, ie. r; Tk OR ry r. then Reject rule end if if [[body] & R then
Add to
end if end for
end for end for
Check and remove any further eyclical rules.
W is defined as Sim(W W5) |R where W. and W, are the graph worlds and R and R are the set rules associated with them. Thus GraphLog enables various training scenarios training on highly similar worlds training control allows GraphLogg to mimic both in-distribution and out-of-distribution scenarios during training and testing. It also enables to precisely categorize the effect of multi-task pre-training when the model needs to adapt to novel worlds.
mix of similar and dissimilar worlds. This fine grained
Algorithm 2 Partition rules into overlapping sets
Require: Rule Set R.s
Require: Number of worlds The >
Require: Number of rules per world 0
Require: Overlapping increment stride > 0
for i 0: < [Rsl w; do
R, = Rs f + w]
i +
end for
14

---

Under review as a conference paper at ICLR 2021
Algorithm 3 World Graph Generator
Require: Set of rellatioss fre)k: k. K 0
Require: Set of rules derived from {r.} |R| >
Require: Set rule selection probability gamma 7 0.8
Set rule selection probability P[R[{]] 1, E [R]
Require: Maximum number of expansions 2 2
Require: Set of available nodes N, s.t. |N] 2 0
Require: Number of cycles of generation 2 0
Set WorldGraph set of edges G. = V)
while N or >
Randomly choose expansion number for this cycle: steps rand 8) Set added edges for this cycle E. =
for all step in steps do if step = then
With uniform probability, either:
Sample ry from Rs [head] and sample u, v E N without replacement, OR Sample an edge (u, Tr, 1)) from Gm
Add (u, Tz, v) to E. and Gm
else
Sample an edge (u, Fe, v) from Ee end if
Sample rule R R from R following s.t. [r..ry] = P[R[i]] = P [ x
Sample new node y N without replacement Add edge (u, Ti 3) to Ee and Gm
Add edge (y.rz, v) E, and Gm end for
if All rules in R used atleast once then Increment c by 1
Reset rule selection probability P[R[i]] Vi e [ end if end while
A.4 COMPUTING DIFFICULTY
Recent research multitask learning has shown evidence that models prioritize selection of difficult tasks over easy tasks while learning to boost the overall performance (Guo et al., 2018). Thus, GraphLog also provides a method to examine how pretraining on tasks of different difficulty level affects the adaptation performance. Due to the stochastic effect of partitioning of the rules, GraphLog consists of datasets with varying range of difficulty. We use the supervised learning scores (Table (6) as proxy to determine the the relative difficulty of different datasets. We cluster the datasets such that tasks with prediction accuracy greater than or above 70% are labeled as easy difficulty, 50-70% labeled as medium difficulty and below 50% labeled as hard difficulty dataset. We find that the labels obtained by this criteria are consistent across the different models (Figure 3).
Graph properties affecting difficulty. While compute difficulty based on the proxy of super- vised learning scores, we observe that the relative difficulty of the tasks are highly correlated with the number of descriptors (Section A. available for each task. We can control the distribution of the dataset by explicitly requiring diversity in the descriptors. Worlds having less number of descriptors are prone to be more difficult for the task. This is due to the fact that will less available descriptors with respect to the budget of data samples, our generation module samples the same set of descriptors while adding variable noise. Thus, datasets with low descriptor count ends up with more relative noise. This shows that for learner, dataset with enough variety among the resolution paths of the graphs with less noise is relatively easier to learn compared to the datasets which has less variation and more noise.
15

---

Under review as a conference paper at ICLR 2021
Algorithm 4 Graph Sampler
Require: Rule Set R.s
Require: World Graph G. = (Vm; Em)
Require: Maximum Expansion length >> 2
Set Descriptor set 5 for all u, Em do
Get all walks Yu,,o) E G. such that () S
Get all descriptors Dy(...) for all walks V(u,v)
Add DY...) 5
end for
Set train graph set Gtrain
Set test graph set Grest
Split descriptors in train and test split, Strain and Steet for all D, Strain or Stest do
[0 and sink node D;(-1) Set prediction target = Em [u,][[]]]]] Set graph edges gi 0 Add all edges from D, to for all V D; do
Set source node
Sample Breadth First Search connected nodes from u and e with decaying probability ?
Add the sampled edges to Si end for
Remove edges in 9: which create shorter paths between u, and U, Add (gi, Us, t) to either Gtrain or Great end for
B SUPERVISED LEARNING ON GRAPHLOG
We perform extensive experiments over all the datasets available in GraphLog (statistics given in T). We observe that in general, for the entire set of 57 worlds, the GAT E-GAT model performs the best.
C MULTITASK LEARNING
C.I MULTITASK LEARNING ON DIFFERENT DATA SPLITS BY DIFFICULTY
Easy
Medium
Diffieult
Fr
F
Accuracy
Accuracy
Accuracy
GAT
E-GAT
10.05
20.05
0.414 =0.07
Param
E:GAT
0.728 +-0.5
0.574 +0.06
0.379 +0.06
GCN
E-GAT
0.713
1:0.55
0.55 10.06
0.396 10.05
RGCN
+0.03
+0.06
Param
RGCN
0.551 1:0.8
0.457 10.05
0.362 00.0
GCN
RGCN
0.673 10.05
0.514 =0.04
0.396 20.06
Table 4: Inductive performance data splits marked by difficulty
In Section A.4 we introduced the notion of difficulty among the tasks available in GraphLog, Here, we consider set of experiments where we perform multitask training and inductive testing on the worlds bucketized by their relative difficulty (Table 4. We sample equal number of worlds from each difficulty bucket, and separately perform multitask training and testing. We evaluate the average prediction accuracy on the datasets within each bucket. We observe that the average multitask performance also mimics the relative task difficulty distribution. We find GAT-E-CAT model outperforms other baselines in Easy and Medium setup, but is outperformed by GAT-RGCN model in the Difficult setup. For each model, we used the same architecture and hyperparameter settings across the buckets. Optimizing individually for each bucket may improve the relative performance.
16

---

Under review as a conference paper at ICLR 2021
group = 0.0
group 1.0
0.4
Accuracy
0.2
10
Gradient updates
Gradient updates
GAT E-GAT
GCN E-GAT
Param_ E-GAT
RGCN
GCN RGCN
Figure 8: We perform fine-grane fine-grained analysis of few shot adaptation capabilities in Multitask setting. Group 0.0 and 1.0 corresponds to 0% and 100% similarity respectively.
Fasy
Medium
Difficult
F.
Accuracy
Accuracy
Accuracy
GAT
E-GAT
0.531 1:0.03
0.569 10.01
0.555 00.04
Param
E-GAT
0.520 +0.02
0.548 =0.01
0,540 =0.01
GCN
E-GAT
0.555 +0001
0,561 =0.02
0,558 =0.01
GAT
RGCN
0.502 +0.02
0.532
=0.01
0.532 =0.01
Puram
RGCN
0.535
+:001
0.506
+0.04
0.539 -0.04
GCN
RGCN
0.481 +:0.02
0.516 +0002
0.520 00.01
Mean
0.521
0.540
0.539
Table 5: Convergence performance on 3 held out datasets when pre-trained on easy, medium and
hard training datasets
C.2 MULTITASK PRE-TRAINING BY TASK SIMILARITY
In the main paper (Section 5.2) we introduce the setup of performing multitask pre-training on GraphLog datasets and adaptation on the datasets based on relative similarity. Here, we perform fine-grained analysis of few-shot adapatation capabilities of the models. We analyze the adaptation performance in two settings when the adaptation dataset has complete overlap of rules with the training datasets (group=1.0) and when the adaptation dataset has zero overlap with the training datasets (group=0.0). We find RGCN family of models with graph based representation function has faster adaptation on the dissimilar dataset, with GCN-RGCN showing the fastest improvement. However the similar dataset the models follow the ranking of the supervised learning experiments, with GAT-EGAT model adapting comparitively better.
EGAT
C.3 MULTITASK PRE-TRAINING BY TASK DIFFICULTY
Using the notion of difficulty introduced in Section A.4 we perform the suite of experiments to evaluate the effect of pre-training on Easy, Medium and Difficult datasets. Interestingly, we find the performance on convergence is better on Medium and Hard datasets on pre-training, compared the Easy dataset (Table 5) This behaviour is also mirrored in k-shot adaptation performance (Figure 9 where pre-training on Hard dataset provides faster adaptation performance on 4/6 models.
D CONTINUAL LEARNING
natural question arises following our continual learning experiments in Section 5.3 of difficulty of the worlds matter? Thus, we perform an experiment following Curriculum Learning (Bengio al. 2009) setup, where the order of the worlds being trained is determined by their relative difficulty (which is determined by the performance of models in supervised learning setup, Table ie., we order the worlds from easier worlds to harder worlds). We observe that while the current task accuracy follows the trend of the difficulty of the worlds (O(a). the mean of past accuracy is significantly worse. This suggests that a curriculum learning strategy might not be optimal to learn graph representations in continual learning setting. We also performed the same experiment with sharing only the composition and representation functions (Figure [0bb), and observe similar trends where sharing the representation function reduces the effect of catastrophic forgetting.
does the order
17

---

Under review as a conference paper at ICLR 2021
World
NC
ND
Split
AN
AE
M1
M2
M3
M4
M5
M6
rule 0
17
286
train
4.49
15.487
19.295
Hard
0.481
0,500
0.494
0.486
0.462
0.462
nile_
15
239
4.10
11.565
13.615
Hand
0.432
0,411
0.428
0.406
0,400
0,408
r
17
157
train
5:21
9.809
11.165
Hard
0.412
0,357
0.373
D:347
0,347
0,319
3ile_3
16
189
trnin
3.63
11.137
13.273
Hard
0.429
0.404
0478
0:873
0-401
D.451
1ule.4
16
189
train
3.94
12,622
15.501
Medium
0.624
0,606
0.619
0.475
1
0.595
rule
14.545
18.872
0.526
0.539
0.548
0.429
0,461
0.455
6
16
249
Irnin
5.06
16.257
20.164
Hard
0.528
0.514
0.536
0.498
0.495
0.476
rule.7
17
288
Irain
4.47
13,161
16.333
Medium
0.613
0.558
0.598
0.487
0.486
D.537
nile_
15
15-997
19.134
Medium
0.627
0.643
0.629
0.525
0.563
D.566
rulc.9
19
1011
train
7.22
24.151
32,668
Easy
0.758
0.744
0.739
0.683
0.651
0.623
rule 10
18
524
Irain
5.87
18.011
22.202
Medium
0.656
0.654
0.663
0.596
0,563
0.605
nil__11
17
4.29
11,459
13.037
Medium
0.552
0.525
0.533
0.445
0.456
D.419
rulc.12
15
306
train
4.14
11,238
12.919
Easy
0.771
0.726
0.603
0.511
0.561
D.523
15
16
149
train
3.58
11,238
15.549
Hard
0.453
01402
0419
0:347
0.298
D.344
14
16
224
train
4.14
11.371
13:403
Hard
0.418
0.157
0.401
0.314
0.318
0.332
rule
12,661
15.105
0.494
0.501
0.402
0.397
0.435
nil_16
16
205
trnin
3.59
11.345
13.293
Hard
0.318
0.332
0.292
0.328
0. 0.306
0.291
rulc_17
17
147
train
3.16
8,163
8.894
Hard
0.347
0.308
0.274
0.164
0.161
0.181
rule_18
25.035
33,080
0,700
0.680
0.713
0.650
0.641
D618
rule 19
16
416
train
6.10
17.180
20.818
Easy
0.790
0.774
0.777
0.731
0.729
0,702
nule 20
20
2024
Irain
8.63
34.059
45:985
Easy
0.830
0.799
0.854
0.756
0.741
0.750
nile_1
10.559
11.754
Medium
0.621
0.610
0632
D.531
0.516
D.500
rule-22
17
422
train
5.21
16.540
20.681
Medium
0.586
0.593
0.628
0.530
0.506
0.573
10le:225
1.
383
Irain
4.97
17.067
21.111
Hard
0,508
0.522
0.493
0:455
0.473
D.476
rule 24
18
S79
6.33
21.402
26.152
Easy
0,706
0,704
0.743
0.656
0.641
0.638
nile_25
15
3.84
11,093
12.775
0.424
0.419
0.382
0.358
0.345
0.412
nile_26
1.5
352
train
4.71
14.157
17.115
Medium
0.565
0.534
0.532
D. 0.466
0.461
0.499
16
393
train
4.98
14.296
16:199
Easy
0.713
0,714
0.722
0.632
0.601
0.617
rule_28
17.551
Medium
0.575
0.364
0.571
0.503
0.409
0.552
rule 29
16
144
train
3.87
10.193
11.774
Hard
0.468
0.445
0.475
0.325
0.336
0.389
nile_00
17
177
Irain
3,51
10.270
11.764
Hard
0.381
0.426
0.382
0.357
0.316
D.336
rule_31
20.147
26.562
0,788
0.789
0.770
0.669
0.674
0.641
rule_32
16
287
train
4.66
16.270
20.929
Medium
0.674
0.671
0.700
0.621
0.591
0.615
1ulc.35
18
312
Irain
4.50
14.738
18.266
Medium
0.695
0.660
0.709
0.710
0.679
0.668
rule 34
18
504
train
5.00
15.345
18.614
Easy
0.908
0.868
0.906
0.768
0.762
0.811
35le_3
19
train
21.867
28.266
Easy
0.831
0,750
0.782
0.680
0,700
B,622
nul:336
19
252
train
4.66
13,900
16.613
Easy
0.742
0.698
0.698
0.659
0.627
B.651
37
17
260
train
4,00
11.956
14,010
Easy
0.843
0.826
0.826
0.673
0.698
0.716
rulo
15.305
20.075
0.748
0.762
0.733
0.614
0.630
0.719
rule 39
15
182
train
3.98
12.552
14,800
Easy
0.737
0.642
0.635
0.592
0,603
0.587
nile_40
17
181
triin
3.69
11,556
14.437
Medium
0.552
0.584
0.575
0.525
0.472
D.479
rulc.41
10,162
11.553
Medium
0.619
0.601
0.626
0.490
0.468
D.470
rule.42
14
95
train
2.96
8.939
9.751
Hard
0.511
0.472
0.483
0.386
0.393
0.395
rulc 43
16
162
train
3.36
11.077
13.337
Medium
0.622
0.567
0.579
0.173
0.182
0.137
mile
18
705
4.75
15.310
18.172
Hard
0.538
0.561
0.603
0.498
0.519
0.450
mile_45
15
taiin
3.39
9.127
10.001
Medium
0.569
0,580
0.592
0.535
0,524
D.524
16
19
2704
train
7.94
31.1588
43-189
Easy
0.850
0.820
0.828
0.773
0.762
0.749
nule.47
18
647
6.66
22.139
27.789
Easy
0.723
0.667
0.708
0.620
0.649
06611
17,802
21.674
Easy
0.812
0.798
0.812
0.772
0.763
0.753
nile 49
14
169
train
3.41
9.983
11.177
Easy
0.714
0.734
0.700
D.511
0.491
0.615
nile_00
16
286
train
3.99
12.274
16.117
Medium
0.651
0.653
0.656
D.555
0,583
D.570
rulc
valid
16.381
21.817
Easy
0.746
0.742
0.738
0.667
0.657
0.689
52
17
351
valid
4.81
16.231
20.613
Medium
0.697
0.716
0.754
0.653
0.655
0.670
rule 53
15
165
valid
3.65
10.838
12.378
Hard
0.458
0.464
0.525
0.334
0.364
0,373
m4
13
303
lest
5.25
13.503
15.567
Medium
0.638
0.623
0.603
0.587
0.586
0.555
nile_55
16
293
lest
4.83
16.444
21.944
Medium
0.625
0.582
0.578
0.561
0,578
D.571
rule 56
15
241
lest
4.40
14,010
16.702
Medium
0.653
0.681
0.692
0.522
0.513
0.550
AGG
16.33
428.94
4.70
14.89
18.37
0.618
0.603
0.611/20
0.530/1
0.526/0
0.539/0
Table 6: Results on Single-task supervised setup for all datasets in GraphLog. Abbreviations: NC: Number of Classes, ND: Number of Descriptors, ARL: Average Resolution Length, AN: Average number of nodes, AE: Average number of edges
D: Difficulty, AGG: Aggregate Statistics. List of models considered M1: GATE M2: GCN-E-GAT, M3: Param-E-GAT, M4: GAT-RGCN, M5: GCN-RGCN and M6: Param-RGCN, Difficulty calculated by taking the scores of the model (M1) and partitioning the worlds according to their accuracy (2 0.7 Easy, 2 0.54 and < 0.7 = Medium, and < 0.54 Hard). We provide both the mean of the raw accuracy scores for all models, as well as the number of times the model is ranked first in all the tasks.
18

---

Under review as a conference paper at ICLR 2021
Param-E-GAT
0.5
0.4
Accursty
0.3
GCN-E-GAT
GAT-RGON
0.4
Accuracy
0.3
0.2
0.1
Param-RGCN
GCN-RGCN
Accuracy
10
updates
updeltes
world
easy
Figure 9: We evaluate the effect of k-shot adaptation on held out datasets when pre-trained on easy, medium and hard training datasets, among the different model architectures. Here, A ranges from to 40.
E HYPERPARAMETERS AND EXPERIMENTAL SETUP
In this section, we provide detailed hyperparameter settings for both models and dataset generation for the purposes of reproducibility. The codebase and dataset used in the experiments are attached with the Supplementary materials, and will be made public on acceptance.
E. DATASET HYPERPARAMS
We generate GraphLog with 20 relations classes (K), which results in 76 rules in Rg after consistency checks. For unary rules, we specify half of the relations to be symmetric and other half to have their invertible relations. To split the rules for individual worlds, we choose the number of rules for each world w 20 and stride 1, and end with 57 worlds Ry... Rs6. For each world R4, we generate 5000 training, 1000 testing and 1000 validation graphs.
E.2 MODEL HYPERPARAMS
For all models, we perform hyper- hyper-parameter sweep (grid search) to find the optimal values based on the validation accuracy. For all models, we use the relation embedding and node embedding to be 200 dimensions. Since the nodes in GraphLog does not have any features or attributes, we randomly initialize the embeddings in the GNN message passing layers for each epoch for all experiments. We train all models with Adam optimizer with learning rate 0.001 and weight decay of 0.0001. For supervised setting, we train models for 500 epochs, and we add scheduler for learning rate to decay it by 0.8 whenever the validation loss is stagnant for 10 epochs. In multitask setting, sample a new task every epoch from the list of available tasks. Here, we run all models for 2000 epochs when we have the number of tasks < 10. For larger number of tasks (Figure 4 train by proportionally increasing the number of epochs compared to the number tasks. (2k epochs for 10 tasks, 4k epochs for 20 tasks, 6k epochs for 30 tasks, 8k epochs for 40 tasks and 10k epochs for
19

---

Under review as a conference paper at ICLR 2021
GAT-E-GAT
Param-E-GAT
GAT-E-GAT
Param-E-GAT
0.8
Accuracy
0.6
Accuracy
0.4
0.4
0.2
GCN-E-GAT
GAT-RGCN
GON-E-GAT
GAT-RGGN
0.8
Accuracy
0.6
Accuracy
0.4
0.2
Param-RGCN
GCN-RGCN
Param-RGCN
GCN-RGON
0.8
0.6
Accuracy
Accuracy
0.6
0.2
Worlds
Worlds
Worlds
Worlds
Shared Composition and Representation
Current Accuracy
Shared Representation Unique Composition
Mean past accuracy
Shared Composition Unique Representation
Curriculum Learning strategy in Continual Learning setup of GraphLog. Figure 10(a) presents the current task accuracy (blue) and mean of all previous task accuracy (orange). Figure 10(b) presents the mean of previous task accuracy when either the composition function or the representation function is shared for all worlds.
Figure 10:
20

---

Under review as a conference paper at ICLR 2021
50 tasks). For continual learning experiment, train each task for 100 epochs for all models. No learning rate scheduling is used for either multitask or continual learning experiments. Individual model hyper-paanee pper-paaaeeters follows:
Representation functions:
GAT Number of layers = 2. Number of attention heads = 2, Dropout 0.4 GCN Number of layers 2, with symmetric normalization and bias, dropout
Composition functions:
E-GAT: Number of layers = 6, Number of attention heads = 2, Dropout = 0.4 RGCN: Number of layers 2. dropout, with bias.
21


Reviews:
[{"review_id": "wh0Pa6G5PcK", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I liked the idea of GraphLog; it seems like an interesting and potentially very useful dataset. The \"results\" seemed little to do with the dataset (apart from being enabled by the dataset), but were comparing some models that were neither the current state-of-the-art or particularly novel. I could imagine a paper that does a comprehensive reevaluation the state-of-the-art algorithms (unchanged!) using the new data set and then reports on which ones work well for different tasks. Such reproducibility in science is important. However, this is not was done.\n\nI would like to see more discussion about why doing well on the benchmark would translate into doing well on real-world problems. I would hypothesize that the real-world does not consist of a few simple rules chained together, but the underlying dynamics is much more complicated, and agents are trying to concoct a story to get some signal out of the noise. All of your tests assume there is a clean signal -- constructed by your rules (perhaps corrupted by random noise(?)).  You just assume that this will form a good testbed, but it isn't obvious to me.\n\nThe rules all seem overly simplistic. I was expecting your rule generator to generate more complex rules from simpler ones. But it doesn't; they all seem to be just the same complexity.  Here are some things I'm wondering:   By sharing subset of rules, the worlds are structurally similar? Are the entities shared in any meaningful way? I think they are just meaningless names, and so there is no commonalities between the worlds. I think they share relations. Is there any notion that a relation learned in one world are like the relation with the same name in other worlds? You are not learning about relations using diverse populations, or are you?\n\nMinor comments\n\nIn RGCN, $\\times_i$ what is $i$?\n\nFigure 3, I thought was weird. If we divide the datasets into easy medium and hard, don't we always have a nice straight lines when plotted with difficulty? I think it is just trying to say that the E-GAT models work better across difficulties.\n\nIn figure 5, I can't see how/why \"The colors of the bars depict how similar two distributions are\"\n\n\n\nAfter rebuttal:\n\n\nComment:\nI am suspicious of your argument on \"complex due to multiple resolution pathways\".\n\nSurely there is always a (unique) canonical deviation. For example, one could imagine extending Prolog to allow for any literal to be resolved; not just the left one. However that just adds extra complexity. Because we have to resolve all literals, we might as well do in a left-to-right order. Surely in your case, we can always do the leftmost (for example) one. Or the rules can be defined so that we can resolve them left to right.\n\nOne counter to my argument might be (parent, ancestor) -> ancestor parent -> ancestor.\n\nHere we cannot go left-to-right, but need to go right to left. We do not need to search over orderings.\n\nThis issue is faced daily by Prolog programmers; we choose whichever one of (using your notation): (parent, ancestor) -> ancestor (ancestor, parent) -> ancestor works with your engine. I don't see why they get around it without problem and you claim it is not possible. The rules may depend on the order used, but what is the problem with that if it drastically reduces the search space? You don't have to search for all proofs; just one.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "a3n5hP_ZZg2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a synthetic graph generator to evaluate graph neural networks. The generation process starts with defining rules, subset of rules are used to define a world, each world is then used to sample a graph. Test queries are generated by picking a pair of vertices u, v and generating a path connecting them via the rules. There are some biases in the generation process. For instance, the rules are exclusively open path or chain rules. And as noted above, the test queries mostly stick to a path (the authors allow some variations by adding nodes to vertices already on the path but the path seems to form the backbone of the test query). The remainder of the paper takes a few well known graph neural networks and evaluates them on data generated using GraphLog. Based on these results, the authors claim that E-GAT outperforms RGCNs.\n\nThis reviewer acknowledges the need for a benchmark for knowledge base completion. However, GraphLog seems to have one too many biases baked into it for it to form a definitive benchmark. The first bias is the adherence to open path or chain rules. I don't understand the need for this. I can think of two different property nodes p1, p2 hanging off a vertex u leading to an edge with another vertex v. Can this be captured by a chain rule? In section 3, the paper states \"Path-based Horn clauses of this form ... encompass the types of logical rules learned by state-of-the-art rule induction systems\" and then goes on to cite \\partial ILP and NeuralLP. \\partial ILP captures more than just chain rules, it tries to capture recursive logic programs, and NeuralLP is based on TensorLog which is much more general than this. If you are going to cite related work then might as well cite it properly. Another bias baked into GraphLog is how it generates its test queries which is mostly a path between two vertices. I found myself wondering whether these biases are what's causing RGCNs to underperform on GraphLog generated data. Such doubts lead me to believe there's some gap in GraphLog that needs bridging. Please don't get me wrong, I'm sure GraphLog will still be used to evaluate KBC approaches but I remain unconvinced that it is general enough to warrant a full conference research paper. \n\nWriting quality wise, the presentation is clear enough with details delegated to the appendices. Related work about graph neural networks and knowledge base completion seems to be well covered. One aspect of related work that seems missing is previously proposed synthetic graph generators. For instance, did the authors try to look for generative approaches for scale-free random graphs? Are these not of interest to the KBC and graph neural networks communities for some reason?", "extra_scores": {}, "extra_text": {}}, {"review_id": "QvLIOScP5Q", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a method for generating synthetic datasets for testing path-based (knowledge) graph completion. Until recently, there were not many good benchmarks for evaluating reasoning with learned rules or learned knowledge, but there has been a fair amount of work on developing benchmarks for this lately. The synthetic datasets generated here are distinguished by the ability to produce datasets that share a controllable amount of rules. This permits the benchmarks to be used to evaluate multitask learning, robustness to distribution shift, etc. As an illustration of this, the paper includes experiments with a variety of baseline methods showing how (a) the generalization ability of various methods grows and then declines as the number of tasks is increased and (b) fine-tuning on diverse tasks improves accuracy. They also show that in a continual learning setting, the baseline methods all exhibit catastrophic forgetting.\n\nThere is value in being able to control the \"relatedness\" of these synthetic tasks in a principled way (the experiments are a good illustration of how this may be used), so I am leaning towards acceptance. My hesitation is that it's a bit on the incremental side, and seems oversold in a few places, as follows:\n\nThe work suggests that the proposed benchmarks examine the \"compositional generalization\" abilities of models, but it is not clear to me how this is so. The relations are drawn from a fixed set of types. It's true that the rules may examine new combinations of relations, but the end result is just that one of the existing relations is inferred to hold between the start and end of the path. The fact that those rules hold for all bindings is a kind of generalization, but I would not call it \"compositional.\" Compositional generalization would mean something more like learning how to map a grammatical structure to the logical form correctly, irrespective of what was in the constituent phrases.\n\nAlso, the work says \"GraphLog is the only dataset specifically designed to test logical generalization capabilities on graph data.\" That seems a little bit of a stretch. CLUTTR seems to feature a very similar set of synthetic benchmarks, the only difference is that CLUTTR *additionally* produces some text, but the abstract focus of the task was an essentially similar knowledge graph completion task. Placing this work side-by-side with CLUTTR, the difference is really (just) in being able to tune the degree of shared structure between multiple datasets. That's valuable, I agree. But this one difference is only discussed by a table featuring four X's for each of the variants of the task setup that this feature enables. The lack of a proper discussion of related work obscures the actual extent of the contribution.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QZ3oEXNdXgE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a benchmark for evaluating to which extend GNNs are able to reason in terms of logical/symbolic rules. The results show that standard GNNs are mostly lacking this capability (what is not really surprising). The paper is fairly understandable and the idea is interesting. The design of the benchmark makes sense to me. Since the writing could be more clear/thorough and I have issues with related work/systems that are not considered (details below), I however do not vote for acceptance.\n\n(+) The benchmark consists of various datasets, interesting settings (e.g., multi-task training and continual learning), and proposes a small extension of GAT which improves performance.\n\n(-) Logic Part: \n- There's a mix of first-order logic (FOL) terminology (constants, relations) and Semantic Web terminology (entities, relations). I suggest to use either constant and predicate or entity and relation. In FOL, a relation (the notion the paper uses for predicates) is the interpretation of a predicate.\n-  Rule (1) is in the most typical format considered in rule learning and called a \"chain rule\". You should mention this at least besides dyadic definite datalog, since the latter seems to be not fully covered. Also, other parts of the paper mention unary rules, which are not covered by (1).\n- I do not think assumption (2) is realistic and wonder in how far it helps with the evaluation.\n\n(-) Related Work: The paper mentions several related works, especially benchmarks. However, I do not understand why the authors completely ignore the entire field of rule learning/ILP. While this area is not solely based on deep learning approaches, the research and insights (esp. how to evaluate logical generalization) are relevant. There are even existing rule learning approaches based on deep learning. The paper compares to benchmarks considering image/text data but does not even mention rule-based benchmarks such as the ILP competition or Rudas (see below links). I would not support the paper's claim as it is written: \"GraphLog is the only dataset specifically designed to test logical generalization capabilities on graph data, whereas previous works have largely focused on the image and text modalities.\" The similarities and differences to existing benchmarks (I agree that there are some, e.g., support for continual learning) need to be pointed out.\n- http://ilp16.doc.ic.ac.uk/competition\n- https://github.com/IBM/RuDaS\n\n(-) Experiments: While it is ok to generally focus on GNNs, the evaluation should consider established rule-learning approaches to set the context (e.g., the recently published Open Graph Benchmark also considers standard baselines), in particular, given that the GNNs perform so disappointing. There are competitive rule learning systems such as AMIE and also deep-learning based systems which could serve as baselines. \n\n----------------------------------------------\nSmaller Comments:\n- p.2 What is the difference between generalization and adaptation?\n- I think it might be good to define the notion of \"compositional generalization\" more clearly.\n- Table. 3 caption: I think the definition of rule similarity is important enough to come in the main paper.\n- p.17 ?? Fig ref\n- A.2 \"we ensure that all generated rules are sound and consistent with respect to R.\" - why should a rule not be sound or consistent w.r.t R? \n\n----------------------------------------------\nUpdate after Rebuttal: I have read the other reviews and authors' responses but do no change my scores.\n\nI still share the impression of Reviewer 3 that several choices in the design of the benchmark seem to be very restricted and arbitrary (e.g., the single possible derivation sequence).\n\nRelated work in terms of rule learning has been incorporated partly now, but there is no proper comparison -- especially in terms of the dimensions mentioned in the previous item. Also, there have been proposals similar to the E-GAT model the authors introduce which are completely ignored in the paper (e.g., MEMORY-BASED GRAPH NETWORKS, ICLR 2020; Graph Neural Networks for Social Recommendation, WWW 2019).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers point out several important issues to be addressed, including comparing to other methods that can address the "combinatorial generalization" problems studied (one reviewer points out the crucial difference from "compositional generalization" studied before), addressing the gap between the proposed dataset (simple and has the value of diagnosing/model debug/research algorithm development) and real datasets/problem settings.   

As such the AC recommends Reject and encourages the authors to take the constructive feedback to improve. 
Decision: Reject