{'fraction_non_alphanumeric': 0.03078378058872207, 'fraction_numerical': 0.010284903652914056, 'mean_word_length': 4.675791733762749, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evaluating Logical Generalization in Graph Neural Networks

Recent research has highlighted the role of relational inductive biases in building learning agents that can generalize and reason in a compositional manner. However, while relational learning algorithms such as graph neural networks (GNNs) show promise, we do not understand how effectively these approaches can adapt to new tasks. In this work, we study the task of logical generalization using 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 logical domains. We use GraphLog to evaluate GNNs in three different setups: single-task supervised learning, multi-task pretraining, and continual learning. Unlike previous benchmarks, our approach allows us to precisely control the logical relationship between the different tasks. We find that the ability for models to generalize and adapt is strongly determined by the diversity of the logical rules they encounter during training, and our results highlight new challenges for the design of GNN models. We publicly release the dataset and code used to generate and interact with the dataset at https://www.cs.mcgill.ca/~ksinha4/graphlog.


Introduction
Relational reasoning, or the ability to reason about the relationship between objects entities in the environment, is considered a fundamental aspect of intelligence (Krawczyk et al., 2011;Halford et al., 2010). Relational reasoning is known to play a critical role in cognitive growth of children (Son et al., 2011;Farrington-Flint et al., 2007;Richland et al., 2010). This ability to infer relations between   Figure 1. GraphLog setup. We define a large set of rules that are grounded in propositional logic. We partition the rule set into overlapping subsets, which we use to define the unique worlds, W k . Finally, within each world W k , we generate several knowledge graphs g k i that are governed by the rule set of W k .
objects/entities/situations, and to compose relations into higher-order relations, is one of the reasons why humans quickly learn how to solve new tasks (Holyoak & Morrison, 2012;Alexander, 2016).
The perceived importance of relational reasoning for generalization capabilities has fueled the development of several neural network architectures that incorporate relational inductive biases (Battaglia et al., 2016;Santoro et al., 2017;Battaglia et al., 2018). Graph neural networks (GNNs), in particular, have emerged as a dominant computational paradigm within this growing area (Scarselli et al., 2008;Hamilton et al., 2017a;Gilmer et al., 2017;Schlichtkrull et al., 2018;Du et al., 2019). However, despite the growing interest in GNNs and their promise for improving the generalization capabilities of neural networks, 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. In particular, we study how GNNs can induce logical rules and generalize by combining these rules in novel ways after training. We propose a benchmark suite, GraphLog, that is grounded in first-order logic. Figure 1 shows the setup of the benchmark. Given a set of logical rules, we create different logical worlds with overlapping rules. For each world arXiv:2003.06560v1 [cs.LG] 14 Mar 2020 Evaluating Logical Generalization in Graph Neural Networks (say W k ), we sample multiple knowledge graphs (say g k i ). 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 a supervised setting by predicting unseen combinations of known rules within a specific logical world. This task that explicitly requires inductive generalization. We further analyze how various GNN architectures perform in the multi-task and the continual learning scenarios, where they have to learn over a set of logical worlds with different underlying logic. Our setup allows us to control the similarity between the different worlds by controlling the overlap in logical rules between different worlds. This enables us to precisely analyze how task similarity impacts performance in the multi-task setting.
Our analysis provides the following useful insights regarding the logical generalization capabilities of GNNs: • Two architecture choices for GNNs have a strong positive impact on the generalization performance: 1) incorporating multi-relational edge features using attention, and 2) explicitly modularising the GNN architecture to include a parametric representation function, which learns representations for the relations based on the knowledge graph structure. • 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 forgetting in the continual learning setting. This indicates that the models are prone to fitting to just the current task at hand and not learning representations and compositions that can transfer across tasks-highlighting the challenge of lifelong learning in the context of logical generalization and GNNs.
Knowledge graph completion. Many knowledge graph datasets are available for the task of relation prediction (also known as knowledge base completion). Prominent examples include Freebase15K (Bordes et al., 2013), Word-Net (Miller, 1995), NELL (Mitchell & Fredkin, 2014), and YAGO (Suchanek et al., 2007;Hoffart et al., 2011;Mahdisoltani et al., 2013). These datasets are derived from realworld knowledge graphs and are useful for empirical evaluation of relation prediction systems. However, these datasets are generally noisy and incomplete, as many facts are not available in the underlying knowledge bases (West et al., 2014;Paulheim, 2017). Moreover, the logical rules underpinning these systems are often opaque and implicit (Guo et al., 2016). All these shortcomings reduce the usefulness of existing knowledge graph datasets for understanding the logical generalization capability of neural networks. Some of these limitations can be overcome by using synthetic datasets, which can provide a high degree of control and flexibility over the data generation process at a low cost. Synthetic datasets are useful for understanding the behavior of different models -especially when the underlying problem can have many factors of variations. We consider using synthetic datasets, as a means and not an end, to understand the logical generalization capability of GNNs.
Our GraphLog benchmark serves as a synthetic complement to the real-world datasets. Instead of sampling from a real-world knowledge base, we create synthetic knowledge graphs that are governed by a known and inspectable set of logical rules. Moreover, the relations in GraphLog are selfcontained and do not require any common-sense knowledge, thus making the tasks self-contained.
Procedurally generated datasets for reasoning. In recent years, several procedurally generated benchmarks have been proposed to study the relational reasoning and compositional generalization properties of neural networks. Some recent and prominent examples are listed in Table 1. These datasets aim to provide a controlled testbed for evaluating the compositional reasoning capabilities of neural networks in isolation. Based on these existing works and their insightful observations, we enumerate the four key desiderata that, we believe, such a benchmark should provide: 1.  (Johnson et al., 2017) Vision CoGenT (Johnson et al., 2017) Vision CLUTRR (Sinha et al., 2019) Text SCAN (Lake & Baroni, 2017) Text SQoOP (Bahdanau et al., 2018) Vision TextWorld (Côté et al., 2018) Text GraphLog (Proposed) Graph the model in different setups, e.g., supervised learning, multitask learning, and continual learning.
As shown in Table 1, GraphLog is unique in satisfying all of these desiderata. We highlight that 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.

Terminology
is a collection of a set of nodes V G and a set of edges E G between the nodes. In this work, we assume that each pair of nodes have at most one edge between them. A relational graph is a graph where the edge between two nodes (say u and v) is assigned a label, denoted r. The labeled edge is denoted as (u → r v) ∈ E G . A relation set R is a set of relations {r 1 , r 2 , ... r K }. A rule set R is a set of rules in first order logic, which we denote in the Datalog format (Evans & Grefenstette, 2017), [r i , r j ] ⇒ r k , and which can be expanded as Horn clauses of the form: where z denotes a variable that can be bound to any entity and ⇒ denotes logical implication. The relations r i , r j form the body while the relation r k forms the head of the rule. Horn clauses of this form represent a well-defined subset of first-order logic, and they encompass the types of logical rules learned by the vast majority of existing rule induction engines for knowledge graphs (Langley & Simon, 1995).
We use p u,v G to denote a path from node u to v in a graph G. We construct graphs according to rules of the form in Equation 1 so that a path between two nodes will always imply a specific relation between these two nodes. In other words, we will always have that Thus, following the path between two nodes, and applying the propositional rules along the edges of the path, we can resolve the relationship between the nodes. Hence, we refer to the paths as resolution paths. The edges of the resolution path are concatenated together to obtain a descriptor. These descriptors are used for quantifying the similarity between different resolution paths, with a higher overlap between the descriptors implying a greater similarity between two resolution paths.

Problem Setup
We formulate the relational reasoning task as predicting relations between the nodes in a relational graph. Given a query (G, u, v) where u, v ∈ V G , the learner has to predict the relation r ? for the edge u → r ? v. Unlike the previous work on knowledge graph completion, we emphasize an inductive problem setup, where the graph G in each query is unique. Rather than reasoning on a single static knowledge graph during training and testing, we consider the setting where the model must learn to generalize to unseen graphs during evaluation.

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 a set R of K relations and use it to sample a rule set R. We impose two constraints on R: (i) No two rules in R can have the same body. This ensures consistency between the rules. (ii) Rules cannot have common relations among the head and body. This ensures the absence of cyclic dependencies in rules (Hamilton et al., 2018). 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 1).
Graph generation. The graph generation process has two steps: In the first step, we recursively sample and use rules in R to generate a relational graph called the WorldGraph (as shown in Figure 1). This sampling procedure enables us to create a diverse set of WorldGraphs by considering only certain subsets (of R) during sampling. By controlling the extent of overlap between the subsets of R (in terms of the number of rules that are common across the subsets), we can precisely control the similarity between the different WorldGraphs. The full algorithm for generating the World-Graph and controlling the similarity between the worlds is given in Appendix (Algorithm 3 and Section A.2).
In the second step, the WorldGraph G W is used to sample a set of graphs G S W = (g 1 , · · · g N ) (shown as Step (a) in Figure 2). A graph g i is sampled from G W by sampling a pair of nodes (u, v) from G W and then by sampling a resolution path p u,v G W . The edge u → ri v between the source and sink node of the path provides the target relation for the learning model to predict. To increase the complexity of the sampled g i graphs (beyond being simple paths), we also add nodes to g i by sampling neighbors of the nodes on p u,v G W , such that no other shortest path exists between u and v. Algorithm 4 (in the Appendix) details our graph sampling approach.

Summary of the GraphLog Dataset
We use the data generation process described in Section 3.3 to instantiate a dataset suite with 57 distinct logical worlds and 5000 graphs per world ( Figure 1). The dataset is divided into the sets of training, validation, and testing worlds. The graphs within each world are also split into training, validation, and testing sets. The key statistics of the datasets are given in Table 2. Though we instantiate 57 worlds, the GraphLog code can instantiate an arbitrary number of worlds and has been included in the supplementary material.

SETUPS SUPPORTED IN GRAPHLOG
GraphLog enables us to investigate the logical relational reasoning performance of models in the following setups: Supervised learning. In the supervised learning setup, a model is trained on the train split of a single logical world and evaluated on the test split of the same world. The total number of rules grows exponentially with the number of relations K, making it impossible to train on all possible combinations of the relations. However, we expect that a perfectly systematic model generalizes to unseen combinations of relations by training only on a subset of combinations (i.e., via inductive reasoning).
Multi-task learning. GraphLog provides multiple logical worlds, each with its own training and evaluation splits. In the standard multi-task training, the model is trained on the train split of many worlds (W 1 , · · · , W M ) and evaluated on the test split of the same worlds. The complexity of each world and the similarity between the different worlds can be precisely controlled. GraphLog thus enables us to evaluate how model performance varies when the model is trained on similar vs. dissimilar worlds.
GraphLog is also designed to study the effect of pre-training on adaptation. In this setup, the model is first pre-trained on the train split of multiple worlds (W 1 , · · · , W M ) and then adapted (fine-tuned) on the train split of the unseen heldout worlds (W M +1 , · · · , W N ). The model is evaluated on the test split of the novel worlds. Similar to the previous setup, GraphLog provides us an opportunity to investigate the effect of similarity in pre-training. This enables GraphLog to mimic in-distribution and out-of-distribution training and testing scenarios, as well as precisely categorize the effect of multi-task pre-training for adaptation performance.
Continual learning. GraphLog provides access to a large number of worlds, enabling us to evaluate the logical generalization capability of the models in the continual learning setup. In this setup, the model is trained on a sequence of worlds. Before training on a new world, the model is evaluated on all the worlds that the model has trained on so far. Given the several challenges involved in continual learning (Thrun & Pratt, 2012;Parisi et al., 2019;De Lange et al., 2019;Sodhani et al., 2019), we do not expect the models to be able to remember the knowledge from all the previous tasks. Nonetheless, given that we are evaluating the models for relational reasoning and that our datasets share relations, we would expect the models to retain some knowledge of how to solve the previous tasks. In this sense, the performance on the previous tasks can also be seen as an indicator of if the models actually learn to solve the relational reasoning tasks or they just fit to the current dataset distribution.

Representation and Composition
In this section, we describe the graph neural network (GNN) architectures that we evaluate on the GraphLog benchmark. In order to perform well on the benchmark tasks, a model should learn representations that are useful for solving the tasks in the current world while being general enough to be effectively adapted to the new worlds. To this end, we structure the GNN models we analyze around two key modules: • Representation module: This module is represented as a function f r : G W × R → R d , which maps logical relations within a particular world W to d-dimensional vector representations. Intuitively, this function should learn how to encode the semantics of the various relations within a logical world. • Composition module: This module is a function f c : which learns how to compose the relation representations learned by f r to make predictions about queries over a knowledge graph.
Note that though we break down the process into two steps, in practice, the learner does not have access to the correct representations of relations or to R. The learner has to rely only on the target labels to solve the reasoning task. We hypothesize that this separation of concerns between a representation function and a composition function (Dijkstra, 1982) could provide a useful inductive bias for the model.

Representation modules
We first describe the different approaches for learning the representation r i ∈ R d for the relations. These representations will be provided as input to the composition function.
Direct parameterization. The simplest approach to define the representation module is to train unique embeddings for each relation r i . This approach is predominantly used in the previous work on GNNs (Gilmer et al., 2017;Veličković et al., 2017), and we term this approach as the Param representation module. 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 representations that can generalize.
Learning representations from the graph structure. In order to define a more powerful and expressive representation function, we consider an approach that learns relation representations as a function of the WorldGraph underlying a logical world. To do so, we consider an "extended" form of the WorldGraph,Ĝ W , where introduce new nodes (called edge-nodes) corresponding to each edge in the orig- is connected to only those nodes that were incident to it in the original graph (i.e. nodes u and v; see Figure 2, Step (b)). This new graphĜ W 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 a GNN model on the expanded WorldGraph and by averaging the edge-node embeddings corresponding to each relation type r i ∈ R. (Step (c) in Figure 2). For the GNN model, we consider the Graph Convolutional Network (GCN) (Kipf & Welling, 2016) and the Graph Attention Network (GAT) architectures. Since the nodes do not have any features or attributes, we randomly initialize the embeddings in these GNN message passing layers.
The intuition behind creating the extended-graph is that the representation GNN function can learn the relation embeddings based on the structure of the complete relational graph G W . We expect this to provide an inductive bias that can generalize more effectively than the simple Param approach. Finally, note that while the representation function is given access to the WorldGraph to learn representations for relations, the composition module is not able to interface with the WorldGraph in order to make predictions about a query.

Composition modules
We now describe the GNNs used for the composition modules. These models take as input the query (g i , u, v) and the relation embedding r i ∈ R d (Step (d) and (e) in Figure 2).

Relational Graph Convolutional Network (RGCN).
Given that the input to the composition module is a relational graph, the RGCN model (Schlichtkrull et al., 2018) is a natural choice for a baseline architecture. In this approach, Evaluating Logical Generalization in Graph Neural Networks we iterate a series of message passing operations: u ∈ R d denotes the representation for a node u at the t th layer of the model, T ∈ R dr×d×d is a learnable tensor, r ∈ R d is the representation for relation r, and N ri (u) denotes the neighbors of node u by relation r i . We use × i to denote multiplication across a particular mode of the tensor. This RGCN model learns a relation-specific propagation matrix, specified by the interaction between the relation embedding r i and the shared tensor T . 1 Edge-based Graph Attention Network (Edge-GAT). In addition to the RGCN model-which is considered the defacto standard architecture for applying GNNs to multirelational data-we also explore an extension of the Graph Attention Network (GAT) model (Veličković et al., 2017) to handle edge types. 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, where we incorporate gating via an LSTM (Hochreiter & Schmidhuber, 1997) and where the attention is conditioned on both the incoming message (from the other nodes) and the relation embedding (of the other nodes): Following the original GAT model, the attention function α is defined using an dense neural network on the concatenation of the input vectors. We refer to this model as the Edge GAT (E-GAT) model.
Query and node representations. We predict the relation for a given query (g i , u, v) by concatenating h (the final-layer query node embeddings, assuming a K-layer GNN) and applying a two-layer dense neural network (Step (f) in Figure 2). The entire model (i.e., the representation function and the composition function) are trained end-toend using the softmax cross-entropy loss. Since we have no node features, we randomly initialize all the node embeddings in the GNNs (i.e., h u ).

Experiments
We aim to quantify the performance of the different GNN models on the task of logical relation reasoning, in three 1 Note that the shared tensor is equivalent to the basis matrix formulation in Schlichtkrull et al. (2018). . We categorize the datasets in terms of their relative difficulty (see Appendix). We observe that the models using E-GAT as the composition function consistently work well.
contexts: (i) Single Task Supervised Learning, (ii) Multi-Task Training and (iii) Continual Learning. Our experiments use the GraphLog benchmark with distinct 57 worlds or knowledge graph datasets (see Section 3) and 6 different different GNN models (see Section 4). In the main paper, we share the key trends and observations that hold across the different combinations of the models and the datasets, along with some representative results. The full set of results is provided in the Appendix. All the models are implemented using PyTorch 1.3.1 (Paszke et al., 2019). The code has been included with the supplemental material.

Single Task Supervised Learning
In our first setup, we train and evaluate all of the models on all the 57 worlds, one model, and one world pair at a time. This experiment provides several important results. Previous works considered only a handful of datasets when evaluating the different models on the task of relational reasoning. As such, it is possible to design a model that can exploit the biases present in the few datasets that the model is being evaluated over. In our case, we consider over 50 datasets, with different characteristics (Table 2). It is difficult for one model to outperform the other models on all the datasets just by exploiting some dataset-specific bias, thereby making the conclusions more robust.
In Figure 3, we present the results for the different models.
We categorize the worlds in three categories of difficultyeasy, moderate and difficult -based on relative test performance of the models on each world.  Table 3. Multitask evaluation performance when trained on different data distributions. We categorize the training distribution on basis of their similarity of rules: Similar (S) containing similar worlds and a mix of similar and dissimilar worlds (D) ual worlds. We observe that the models using E-GAT as the composition functions always outperform their counterparts using the RGCN models. This confirms our hypothesis about the usefulness of combining relational reasoning and attention for improving the performance on relational reasoning tasks. An interesting observation is that 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 difficulty of the different worlds in GraphLog.

Multi-Task Training
We now turn to the setting of multi-task learning where we train the same model on multiple logical worlds.  . We run multitask experiments over an increasing number of worlds to stretch the capacity of the models. Evaluation performance is reported as the average of test set performance across the worlds that the model has trained on so far. All the models reach their optimal performance at 20 worlds, beyond which their performance starts to degrade.
Basic multi-task training. First, we evaluate a how changing the similarity among the training worlds affects the test performance in the multi-task setup, where a model is trained jointly on eight and tested on three distinct worlds.
In Table 3, we observe that considering a mix of similar and dissimilar worlds improves the generalization capabilities of all the models when evaluated on the test split. Another important observation is that just like the supervised learning setup, the GAT-EGAT model consistently performs either as good as or better than other models and the models using EGAT for the composition function perform better than the ones using the RGCN model. Figure 4 shows how the performance of the various models 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 is increased from 10 to 20 but then begins to decline, indicating capacity saturation in the presence of too many diverse worlds.
Multi-task pre-training. In this setup, we pre-train the model on multiple worlds 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. Figure 5 considers the case of zero-shot adaptation 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 is 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 set of distributions improves adaptation capability. The results for adaptation with 5, 10, ... 30 steps are provided in the Appendix (Figure 8).

Continual Learning Setup
In the continual learning setup, we evaluate the knowledge retention capabilities of the GNN models. We train the model on a sequence of overlapping worlds, and after converging on every world, we report the average of model's  Figure 6. We evaluate the performance of all the models in a continual learning setup. The blue curve shows the accuracy on the current world and the orange curve shows the mean accuracy on all the previously seen worlds. As the model trains on new worlds, its performance on the previously seen worlds degrades rapidly. This is the forgetting effect commonly encountered in continual learning setups.
performance on all the previous worlds. In Figure 6 we observe that as the model is trained on different worlds, the performance on the previous worlds degrades rapidly. This highlights that the current reasoning models are not suitable for continual learning.
The role of the representation function. We also investigate the model's performance in a continual learning setup where the model learns only a world-specific representation function or a world-specific composition function, and where the other module is shared across the worlds. In Figure 7, 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.  Figure 7. We evaluate the performance in a continual learning setup where we share either the representation function or the composition function or both. We observe that sharing the representation function reduces the effect of catastrophic forgetting as compared to the other setups.

Discussion & Conclusion
In this work, we propose GraphLog, a benchmark suite for evaluating the logical generalization capabilities of Graph Neural Networks. GraphLog is grounded in first-order logic and provides access to a large number of diverse tasks that require compositional generalization to solve, including single task supervised learning, multi-task learning, and continual learning. Our results highlight the importance of attention 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 is leveraging GraphLog for studies of fast adaptation and meta-learning in the context of logical reasoning (e.g., via gradient-based meta learning), as well as integrating state-of-the-art methods (e.g., regularization techniques) to combat catastrophic forgetting in the context of GNNs.

A.1. Extended Terminology
In this section, we extend the terminology introduced in Section 3.1. A set of relations is said to be Invertible if i.e. for all relations in R, there exists a relation in R such that for all node pairs (u, v) in the graph, if there exists an edge u → ri v then there exists another edge v → rj u. Invertible relations are useful in determining the inverse of a clause, where the directionality of the clause is flipped along with the ordering of the elements in the conjunctive clause. For example, the inverse of Equation 1 will be of the form:

A.2. Dataset Generation
This section follows up on the discussion in Section 3.3. We describe all the steps involved in the dataset generation process.
Rule Generation. In Algorithm 1, we describe the complete process of generating rules in GraphLog . We require the set of K relations, which we use to sample the rule set R. We mark some rules as being Invertible Rules (Section A.1). Then, we iterate through all possible combinations of relations in DataLog 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 a 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 (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 4). Given a set of rules R S , in the first step, we recursively sample and apply rules in R S to generate a 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 R (in terms of the number of rules that are common across the subsets), we can precisely control the similarity between the different world graphs.
In the second step (Algorithm 4), the world graph is used to sample a set of graphs G S W = {g 1 , · · · g N }. A graph g i is sampled from G W by sampling a pair of nodes (u, v) from G W and then by sampling a resolution path p u,v G W . The edge u → ri v provides the target relation that the learning model has to predict. Since the relation for the edge u → ri 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 D i , 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 D i to the corresponding graph g i , and then sampling neighbors of p gi . Concretely, we use Breadth First Search (BFS) to sample the neighboring subgraph of each node u ∈ p gi with a decaying selection probability γ. This allows us to create diverse input graphs while having precise control over its resolution by its descriptor D i . Splitting dataset over these descriptor paths ensures inductive generalization.

Algorithm 1 Rule Generator
Input: Set of K relations {r i } K , K > 0 Define an empty rule set R Populate Invertible Rules, r i =⇒r i , add to R for all Remove rule having body t inv [body] from R end if end if end for end for end for Check and remove any further cyclical rules.
Algorithm 2 Partition rules into overlapping sets Require: Rule Set R S Require: Number of worlds n w > 0 Require: Number of rules per world w > 0 Require: Overlapping increment stride s > 0

. 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 i and W j is defined as Sim(W i , W j ) = |R i ∩ R j |, where W i and W j are the graph worlds and R i and R j are the set of rules associated with them. Thus GraphLog enables various training scenarios -training on highly similar worlds or training on a 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.
Sample a new node y ∈ N without replacement Add edge (u, r i , y) to E c and G m Add edge (y, r j , v) t E c and G m end for if All rules in R is used atleast once then Increment c by 1 Reset rule selection probability P [R[i]] = 1, ∀i ∈ |R| end if end while

A.4. Computing difficulty
Recent research in 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 a 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% are labeled as medium difficulty and below 50% are labeled as hard difficulty dataset. We find that the labels obtained Table 4. Inductive performance on data splits marked by difficulty 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-GAT 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. 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 a graph based representation function has faster adaptation on the dissimilar dataset, with GCN-RGCN showing the fastest improvement. However  Table 5. Convergence performance on 3 held out datasets when pre-trained on easy, medium and hard training datasets on the similar dataset the models follow the ranking of the supervised learning experiments, with GAT-EGAT model adapting comparitively better.

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 to 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
A natural question arises following our continual learning experiments in Section 5.3 : does the order of difficulty of the worlds matter? Thus, we perform an experiment following Curriculum Learning (Bengio et 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 6, i.e., 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 (Figure 10), the mean of past accuracy is significantly worse. This suggests that a curriculum learning strategy might not be optimal to learn graph representations in a continual learning setting. We also performed the same experiment with sharing only the composition and representation functions (Figure 11), and observe similar trends where sharing the representation function reduces the effect of catastrophic forgetting.

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    Evaluating Logical Generalization in Graph Neural Networks experiments are attached with the Supplementary materials, and will be made public on acceptance.

E.1. Dataset Hyperparams
We generate GraphLog with 20 relations or classes (K), which results in 76 rules in R S 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 s = 1, and end up with 57 worlds R 0 . . . R 56 . For each world R i , we generate 5000 training, 1000 testing and 1000 validation graphs.

E.2. Model Hyperparams
For all models, we perform 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. We train all models with Adam optimizer with learning rate 0.001 and weight decay of 0.0001. For supervised setting, we train all models for 500 epochs, and we add a scheduler for learning rate to decay it by 0.8 whenever the validation loss is stagnant for 10 epochs. In multitask setting, we 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), we train by proportionally increasing the number of epochs compared to the number of 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 50 tasks). For continual learning experiment, we 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-parameters are as 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, no dropout • Composition functions: -E-GAT: Number of layers = 6, Number of attention heads = 2, Dropout = 0.4 -RGCN: Number of layers = 2, no dropout, with bias.