Systematic Relational Reasoning With Epistemic Graph Neural Networks
Authors: Irtaza Khalid
Steven Schockaert
Venue: ICLR 2025 Poster (2025)
Keywords: Reasoning
Graph Neural Networks
Neuro-Symbolic methods
Systematic Generalization
Compositionality
Primary area: learning on graphs and other geometries & topologies
TL;DR: NNs are typically poor at systematic reasoning due to a lack of an epistemic inductive bias for OOD generalization but GNNs adapted with it rival neuro-symbolic methods on standard systematic relational reasoning tasks.

Abstract: Developing models that can learn to reason is a notoriously challenging problem. We focus on reasoning in relational domains, where the use of Graph Neural Networks (GNNs) seems like a natural choice. However, previous work has shown that regular GNNs lack the ability to systematically generalize from training examples on test graphs requiring longer inference chains, which fundamentally limits their reasoning abilities. A common solution relies on neuro-symbolic methods that systematically reason by learning rules, but their scalability is often limited and they tend to make unrealistically strong assumptions, e.g.\ that the answer can always be inferred from a single relational path. We propose the Epistemic GNN (EpiGNN), a novel parameter-efficient and scalable GNN architecture with an epistemic inductive bias for systematic reasoning. Node embeddings in EpiGNNs are treated as epistemic states, and message passing  is implemented accordingly. We show that EpiGNNs achieve state-of-the-art results on link prediction tasks that require systematic reasoning. Furthermore, for inductive knowledge graph completion, EpiGNNs rival the performance of state-of-the-art specialized approaches. Finally, we introduce two new benchmarks that go beyond standard relational reasoning by requiring the aggregation of information from multiple paths. Here, existing neuro-symbolic approaches fail, yet EpiGNNs learn to reason accurately.  Code and datasets are available at https://github.com/erg0dic/gnn-sg.

Published as a conference paper at ICLR 2025
SYSTEMATIC RELATIONAL REASONING WITH EPIS- TEMIC GRAPH NEURAL NETWORKS
Irtaza Khalid & Steven Schockaert Cardiff University, UK (khal i fdmi, schockaerts @ecrrd .k
ABSTRACT
Developing models that can learn reason is a notoriously challenging problem. We focus on reasoning in relational domains, where the use of Graph Neural Net- works (GNNs) seems like a natural choice. However, previous work has shown that regular GNNs lack the ability to systematically generalize from training examples on test graphs requiring longer inference chains, which fundamentally limits their reasoning abilities. A common solution relies neuro-symbolic methods that systematically reason by learning rules, but their scalability is often limited and they tend make unrealistically strong assumptions, e.g. that the answer always be inferred from a single relational path. We propose the Epistemic GNN (EpiGNN), novel parameter-efficient and scalable GNN architecture with epistemic in- ductive bias for systematic reasoning. Node embeddings in FpiGNNN are treated as epistemic states, and message passing implemented accordingly. We show that EpiGNNs achieve sate-oof-the-ar results on link prediction tasks that require systematic reasoning. Furthermore, for inductive knowledge graph completion, EpiGNNs rival the performance of state-of-the thet specialized approaches. Finally, we introduce two new benchmarks that go beyond standard relational reasoning by requiring the aggregation of information from multiple paths. Here, existing neuro-symbolic approaches fail, yet EpiGNNs learn to reason accurately. Code and datasets available at https:/ /tt///gittt /ggtthbb com wwtmm/ergodic.. /gn///nn-/ sg
INTRODUCTION
Learning to reason remains key challenge for neural networks. When standard neural network architectures are trained on reasoning problems, they often perform well on similar problems but fail to generalize to problems with different characteristics than the ones that were seen during training, e.g. problems that were sampled from a different distribution (Zhang et al., 2023a). This behaviour has been observed for different types of reasoning problems and different types of architectures, including pretrained transformers (Zhang et al. 2023a Welleck et al. (023), transformer variants (Bergen al. 202T Kazemnejad al. 2023) and Graph Neural Networks (Snha et al. 2019).
In this paper, we focus on the problem of systematic generalization (SG), and on systematic reasoning about binary relations in particular. This refers the ability of a model to solve test instances by applying knowledge obtained from training instances, where the combination of inference steps that is needed is different from what has been seen during training (Hupkes al. 2020). It is an essential ingredient for machines and humans to generalize from a limited amount of data (Lake) al. 2017). For relational systematic reasoning, problem instances can be represented as a labelled multi-graph (i.e. a knowledge graph) and the main reasoning task is to systematically infer the relationship between a head entity and target entity f. Typically, the training data consists of instances that only require relatively short inference chains, where trained models are then evaluated on increasingly larger test graphs. Graph Neural Networks (GNNs) intuitively seem well-suited for relational reasoning (Zhu et al., 2021 Schlichtkrull et al., 2018). but in practice they underperform neuro-symee siirr--ymmolic methods on SG (Rocktäschel & Riedel 2017; Minervini et al.) (2220)). Crucially, this is true despite the fact that GNNs expressive enough encode the required inference process.
Conceptually, there is fundamental question that has largely remained unanswered: What makes Seural-theorrm-pmee type methods successful for systematic reasoning? We argue that the outper-

---

Published as a conference paper at ICLR 2025
Single-path reasoning
Multi-path disjunctive reasoning
Fax mother
Hos brother.
PO
Has
PO
TEP
EQ
(DC, BC, PC, (TPP))
Pr: (Ilas mnele
Has daughter
las father
Py (ITPPI, ac, ac, TPP1,P0)
Pye (IPPL PO)
Hos undte
PO
P1 Pu (PO)
BQ
10
Figure 1: Left: A (single) relational path reasoning problem over family relations from CLUTRR (Sinha et al., 2019), where the path P1 allows to infer the correct relation. Right: A multi-path reasoning problem over RCC-8 relations where each path provides partial (disjunctive) information and the target label is obtained by combining information from paths Pt, P2 and P3.
formance of such methods can be explained by their focus on modeling single relational paths, as an alternative to local message passing. To predict the relationship between and t, conceptually, these methods consider all the (exponentially many) paths between them, select the most informative path, and make a prediction based on this path, although in practice heuristics are used to avoid exhaustive exploration (Minervini al. 2020b). The emphasis single paths provides a useful inductive bias, while also avoiding problems with local message passing such as over-smoothing. Compared to GNNs, neuro-symbolic methods also have an advantage in how individual relational paths mod- eled. Consider relational path " 21 "3 ... I t. or simply r1; r2: T% if the entities æ; are unimportant. To predict the relationship between h and i, most methods essentially proceed by repeat- edly choosing two neighboring relations ri; r and replace them by their composition. Crucially, the order in which these relations are chosen may determine whether the model finds the answer, as certain orderings may require knowledge of unseen intermediate relationships. Neuro-symbolli methods can often avoid such issues by, in principle, considering all possible orderings.
However, neuro-symbolic methods also have important drawbacks, including scalability, and most fundamentally, their focus simple rules and single relational paths. Since these limitations not tested by existing benchmarks, as a first contribution, we introduce a multi-path, disjunctive systematic reasoning benchmark based on qualitative spatial (RCC-8) and temporal (Interval Algebra) calculi (Randell et al. 1992 Allen 1983b). The considered problems require models to combine partial (disjunctive) information from multiple relational paths, which are also present in real-world story understanding problems (Cain et al. 200T). Figure FigureTillane Tillustrates the difference between single and multi-pati -ath relational reasoning.
In this paper, we propose the Epistemic GNN (EpiGNN), novel, scalable and parameter-efficient GNN for systematic relational reasoning. Motivated by the fact that aligning the model's 's architecture with an algorithm that approximately solves the given problem aids generalization (Xu et al.) 2020 Bahdanau et al., 2019), the EpiGNN designed to simulate an approximation of the Algebraic Closure Algorithm (ACA) (Renz & Ligozai 2005), which solves multi-path reasoning on RCC-8 and
IA. This translates to the following inductive biases in the EpiGNN's s structure: (1) having a message passing function that explicitly simulates the composition of discrete relations in ACA (rather than general relation vector composition)
(2) having epistemic (probabilistic) embeddings that can encode unions of base relations in ACA (3) having pooling operation that simulates the intersection operator in ACA. Below is a summary of our main contributions:
We propose a novel GNN model, the EpiGNN, based on ACA, which rivals SOTA neuro- symbolic methods on simple single-path base systematic reasoning while being highly efficient, and at least two orders of magnitude more purameter-efficion in practice.
We introduce two multi-path, disjunctive relational reasoning benchmarks that are challeng- ing for various SOTA models, but where EpiGNNs still perform well.
Despite being designed for SG-type link prediction, show that EpiGNNS rival SOTA specialized approaches for standard inductive knowledge graph completion.
We theoretically link EpiGNNs to an approximation of the algebraic closure algorithm, which we term directional algebraic closure.
2

---

Published as a conference paper at ICLR 2025
2 LEARNING TO REASON IN RELATIONAL DOMAINS
We focus on the problem of reasoning about binary relations. We assume that a set F of facts is given, referring to a set of relations R and a set of entities E. Each of these facts is an atom of the form r(a, b), with r E R and a, E E. We furthermore assume that there exists a set of rules which can be used to infer relationships between the entities in E. We write K. KU JFF } r(a, b) to denote that r(a, b) can be inferred from the facts in F and the rules in K.. The problem that we are interested in is to develop a neural network model fo which can predict for given assertion r(a, b) whether KUF.F = r(a, b) holds or not. Note that the set of rules K. is not given. We instead have access to a number of fact sets F;, together with examples of atoms r(a, b) which can be inferred from these fact graphs and atoms which cannot. To be successful, Se must essentially learn the rules from K, and the considered model must be capable of applying the learned rules in a systematic way to new problems.
2.1 LEARNING TO REASON ABOUT SIMPLE PATH RULES
The most commonly studied setting concerns Horn rules of the following form (n 2 3):
r(X,, + ( A... (X--1XX-1, We will refer such rules as simple path rules. Note that used the convention from logic programming to write the head of the rule on the left-hand side, and we use uppercase symbols such as X, to denote variables. We can naturally associate a labelled multi-graph G5 with the given set of facts. The rule ( expresses that when two entities a and b are connected by a relational path rii...i7n-1 in this graph Gy, then we can infer that r(a, 6) is true. Without loss of generality, we can restrict this setting to rules with two atoms in the body: ((x,X,,) + (X1 (2) A r2 (X2, Xs). Indeed, a rule with more than two atoms the body can be straightforwardly simulated by introducing fresh relation symbols. The semantics of entailment are defined in the usual way (see Appendix for details). We can think of the process of showing IC CUF }= r(a, b) in terms of operations on relational paths. We say that the path rii.... TT-2; 8; rs+1: ... .R can be derived from rii...; T in one step if IC contains a rule of the form s(x, Z) < - (X,Y) A rY,YY 2). We say that r can be derived from Tii... if there exists sequence of k 1 such steps that yields r.
(1)
Proposition 1. We have that KC UUZ F } r(a, b) holds iff there exists a relational path r15...:7A connecting a and b in the graph G such that r can be derived from : T.k
Inferring r r(a, b) thus conceptually consists of two distinct steps: (i) selecting a relational path between a and and (ii) showing that r can be derived from it. Several of the neural network methods that have been proposed in recent years for relational reasoning directly implement these two steps, most notably R5 (Lu et al. 2022) and NCRL (Cheng et al.] (023). Neural theorem provers (Rocktäschel & Riedel 2017) implicitly also operate in similar way, considering all possible paths and all possible derivations for these paths. However, both steps are problematic for standard GNNs. First, by focusing local message passing, rather than on selecting individual relational paths, the node representations that are learned by a GNN run the risk of becoming "overloaded", as they intuitively aggregate information from all the paths that go through a given node. Moreover, even for graphs that consist of a single path, GNNs have disadvantage: the use of local message passing intuitively means that relational paths have be processed sequentially. For example, for r1; 72: T3, models such as NBFNet (Zhu et al. 2021) can only process r1;72 the first valid composition and not 73.
The fact that relational paths can only be processed sequentially by GNNs is an important limitation, as this might require the model to apply rules, or even capture types of relations, that were not present in the training data, For instance, we may encounter the following chain of family relationships: has-father
has-father
has-brother, 33 has-daughter
has-brother, 355
has-mother b
I
JAA
Suppose the model has never encountered the great-cousin relation during training. Then we cannot expect it to capture the relational path has-father; has-father; has-brother; has-daughter. However, a has-father
if can first derive
b then the problem disappears (assuming the model understands the great-aunt relation).
In hass-uunt,
2.2 LEARNING TO REASON ABOUT DISJUNCTIVE RULES
The rules that we have considered thus far uniquely determine the relationship between two entities a and e, given knowledge about how a relates to b and b relates to c. In many settings, however, such
3

---

Published as a conference paper at ICLR 2025
knowledge might not be sufficient for completely characterising the relationship between and Domain knowledge might then be expressed using disjunctive rules the following form:
81 (X, 2) ... V 5R (x(,, 2) ri (x, A r2, Z)
In other words, if we know that r1 (a, 6) and (2(b, c) hold for some entities b, then we can only infer that one of the relations $1, .1....... ....... Sk must hold between a and c. We then typically also have constraints of the form 1 + (X,, [X, Y) (x, Y), encoding that 71 and 12 are disjoint. Many popular calculi for spatial and temporal reasoning fall under this setting, including the Region Connection Calculus (RCC-8) and the Interval Algebra (IA) (Allen) 1983a: Randell et al. 1992). RCC-8 uses eight relations to qualitatively describe spatial relations, as shown in Fig. 2 For instance, ntpp(a, (a, b) means that is proper part of the interior of b. IA is defined similarly (sec A).
Existing benchmarks for systematic relational reasoning do not consider disjunctive rules, and thus only test the reasoning abil- ities of models to a limited extent. We therefore introduce two new relational reasoning benchmarks, based RCC-8 and IA respectively. An example RCC-8 problem is shown in Figure illustrating how we may need to aggregate evidence from mul- tiple relational paths, as a single path does not always yield unique relation. For instance, from path P's can only infer that one of the relations tppi, ntppi, po holds between nodes O and 10. Full details of the proposed benchmarks are provided in Appendix E Methods such as R5 and NCRL, which rely on a single path to make predictions, cannot be used this setting. Neural theorem provers cannot handle disjunctive rules either, and cannot be generalized a scalable way. We thus need new approach for for learning to reason about disjunctive rules.
do(a.))
po(a.b)
ec(a,)
eq(a,b)
bb
tpp(a.b)
tppi(a.b)
ntpp(a,b)
n=ppi(s.b)
Figure 2: RCC-8 relations.
The characterization in Proposition cxplains how models can be designed for deciding entailment with simple rules. A similar characterization for entailment with disjunctive rules is unfortunately not possible, as deciding entailment with such rules is NP-complete general. However, for RCC-8 and IA, and many other calculi, deciding entailment in polynomial time is possible using the algebraic closure algorithm (Renz & Ligozat 2005). The main idea is to keep track, for every pair of entities, of which relationships are possible between these entities. This knowledge of possible relationships is then propagated to infer constraints about relationships between other entities using the rules in K (details are provided in the App. C As we will see next, our proposed epistemic GNN model is based on the same idea, and can be viewed as an approximate differentiable algebraic closure method.
3 AN EPISTEMIC GNN FOR SYSTEMATIC REASONING
We now present the Epistemic GNN (EpiGNN), a GNN which aims to overcome a number of key limitations of existing models for systematic relational reasoning, Specifically, EpiGNNs are more efficient than current neuro-symbolic methods while, as we will see in Section matching their performance reasoning with simple path rules. Moreover, they are also able to reason about disjunctive rules, which has not been previously considered for neuro-symbolic methods.
We start from the principle that reasoning is fundamentally about manipulating epistemic states (i.e. states knowledge) and the GNN should reflect this: there should be a clear correspondence between the node embeddings that are learned by the model and what that may hold between the entities of interest. Inspired by NBFNet (Zhu et al., (021). a GNN that models path-based representations by anchoring node embeddings which learns the relationships between one designated head entity h and all other entities. Let us write (!) E RR for the embedding of entity in layer of the network. This embedding reflects which relationships may hold between and the designated entity h. We think e(") as a probability distribution over possible relationships. Accordingly, the embeddings are initialized as:
infer about the relationships
source, also use network
(1,0 (1,0......0 0) i
( .
otherwise
We associate the first coordinate with the identity relation. Since h is identical itself, we define (0) 01,0,... .,.,,....), 0). For the other entities, since have knowledge, their embeddings
4

---

denote the n-dimensional Published as a conference paper at ICLR 2025
Messagge passing
2. FIB composition simple walh
3. Final aggregation
fonward fow
Eadkward
di PLORyOR
Ju Fo
BI
Pi TIO
V
BREI
In
w/o
#ggingete
Fa
Figure 3: Overview of the EpiGNN. Step I: Independently Iearn the forward and backward entity embeddings through epistemic message passing. Step 2: Compose the entity embeddings path between the head (blue) and target (red) entity from the forward and backward model. Each composition predicts the target relation. Step Aggregate the evidence provided by each prediction.
initialized as a uniform distribution. Note that the entity components correspond to abstract primitive relations, rather than the relations from R. We only require that the relations from R can be defined in terms of these primitive relations. This distinction is important, because it allows us capture semantic dependencies between relations (e.g. both parent and father may exist in R) and to express (composed) relationships which are outside R. For / 2 1, the embeddings updated as:
( = (f(( 1) u
E FF)
where the argument of the pooling operator & is a multi-set and r E R" is learned embedding of relation E R, where r = (ri,..., .n) encodes probability distribution, i.e. r; 2 0 and Σ, r 1.
Message passing The vector ((((l-1),r) r) should capture the possible relationships between h and e, given the knowledge provided by f(l-1) about the possible relationships between h and f and the fact r rff, e). Since both f(!-1) and are modeled as probability distributions over primitive relations, ((f(1 1)) can be defined in terms of compositions of primitive relations. Specifically, let the vector a.j E RR represent the composition of primitive relations and j, which we treat as a probability distribution, i.e. require the components of ai to be non-negative and to sum to 1. We define:
70
o(Uh,.... ... fn), (ri,...,, rn))
firaai
4
The initialization of (0) was based on the assumption that the first coordinate of the embeddings cor- responds to the identity relation. Accordingly, we want to ensure that 6(11, 0,..., O), (ri,..., rw)) = (riy...;"" rn). We thus fix aij one-hot(j), where we write one-hot(j) vector which is 1 in the ,th coordinate and O elsewhere. Note that the composition of two primitive re- lations is also a probability distribution over primitive relations. This provides an important inductive bias, as it encodes that the relationship between any two entities can be described by one of the n considered primitive relations. Rule based methods, including NTP based approaches, also encode this assumption. However, the message passing operations that are used by standard GNNs typically do not. We hypothesise that the lack of this inductive bias partially explains why standard GNNs fail systematic generalization for reasoning in relational domains.
Pooling The pooling operator & has to be chosen in accordance with the view of embeddings as epistemic states: if x,...., Xg capture sets of possible relationships then ((x X1, should intuitively capture the intersection of these sets. This requirement was studied by (Schockaert) [024] whose central result is that the minimum and component-wise (i.e. Hadamard) product are compatible with this view, but sum pooling is not. In our setting, since the embeddings capture probability distributions rather than sets, e is L1 normallizdd after applying the minimum or product.
Training To train the model, we assume that we have access to a set of examples of the form hi,,ht,,, r.), where h, are entities appearing in F, and the atom r,(h, tt) can be inferred from F. Different examples will involve a different fact set F, but the set of relations R appearing in these fact sets is fixed. We train the model via contrastive learning. This means that for each
5

---

Published as a conference paper at ICLR 2025
positive example (F,, (4, rt)) we can consider negative examples of the form (Fi, h, t,, r') with r' E R \ (r:). Let us write t; for the final-layer embedding of entity t, in the graph associated with Fi (with h2 as the designated head entity). We train the model using margin loss, imposing that the cross-entropy between i; and r should be lower for positive examples than for negative examples.
Facets A crucial hyperparameter is the dimensionality n of the embedding r, as it determines the number of primitive relations. A large n is essential to express all the relations of interest, but choosing n too high may lead to overfitting. To address this, we propose to jointly train m different models, each with relatively low dimensionality. The underlying intuition is that each model focuses on a different facer of the relations. Because these facets are easier to model than the target relations themselves, each of the models can individually remain relatively simple. In the loss function, we simply add up the cross-entropies from these m models (see Appendix for details).
Expressivity The algebraic closure algorithm maintains set of possible relations for each pair of entities. Simulating this algorithm thus requires a number of vectors which is quadratic in the number of entities. As this limits scalability, we instead consider an approximation, which we call directional algebraic closure, where we only maintain sets of possible relations between the head entity and the other entities (see Appendix [o details). EpiGNNs can be seen as differentiable counterpart of directional algebraic closure, where standard directional algebraic closure emerges as special case.
Proposition (informal). There exists a parameterisation of the vectors r and a, such that the predictions of the EpiGNN exactly capture what can be inferred using directional algebraic closure.
Forward-backward model As we noted in Section 2.1 the order in which the relations on a relational path "i;---?7 r3 are composed sometimes matters. The model have constructed thus far always composes such paths from left to right, i.c. we first compose and r2, then compose the resulting relation with r3, etc. To mitigate this limitation, we introduce backward model, which relies on designated tail entity. Similar as before, we initialise the embeddings t()) O1,
and (0) (1/n,-.-. 1/n) for * I. These embeddings are updated follows:
1 "(fell113 fØ(r, | [r(e,)) E F))
(5)
where to and é are defined as before. Note that the backward model does not introduce any new parameters. We rely on the idea that á captures the composition of relation vectors. In the forward model, the embedding of an entity e is interpreted and in the backward model, it captures the relationship between e and t. This is why r appears as the second argument of á in (4) and as the first argument in (5). Let e and ex be the final-layer embedding of in the forward and backward model. In particular, t and h now both capture the relationship between h and f. Moreover, for any entity b(e=",e* should also capture this relationship. We take advantage of the aggregation operator vù to take into account all these predictions. In particular, we construct the following vector:
capturing the relationship between h and
path between h and the vector
s= "(((t",h" ( IE E En,rh)
(6)
where we write E for the entities that appear on some path from paths between h and f, we randomly select one of the shortest paths to define εn,t- The model is then trained as before, using s as the predicted relation vector rather than t Note that while this
When there are multiple
approach cannot exhaustively consider all possible derivations, it has the key advantage of remaining highly efficient. A schematic of the EpiGNN learning dynamics is shown in Figure
EXPERIMENTS
We use the challenging problem of inductive relational reasoning to evaluate our proposed model against GNN, transformer and neuro-symbolic baselines. We consider two variants of the EpiGNN, which differ in the choice of the pooling operator: component-wis multiplication (EpiGNN-mul) and min-pooling (EpiGNN-minn). Most of the considered benchmarks involve relation classification queries of the form (h. ?, t), asking which relation holds between given head entity h and tail entity t. We focus in particular on systematic generalization, to assess whether models can deal with large distributional shifts from the training set, which is paramount in many real-world settings (Koh et al., 2021). We consider existing benchmarks designed to test systematic generalization for relational

---

Published as a conference paper at ICLR 2025
Table 1: Results (accuracy) on CLUTRR after training on problems with (2,3, 4} and then evaluating problems with & f5..... .......100 10). Results marked with were taken from (Minervini al., (0200)), those with from (Lu et al. 2022) and those with from (Cheng et al. 2023). The best performance for each k is highlighted in bold.
Hops
Hops
Hops
Hops
Hops
Hops
EpiGNN-mul (ours)
0.99 01
0.99-.01
0.99:.02
0.99
0.96# 03
0.98:102
EpiGiN-miin (ours)
0.99::011
0.98
0.98#.03 03
0.974.06
0.95
0.934.077
NCRL
100:.01
0.99:101
0 02
0.984: 03
0.98
0.97:.022 02
0.9911.02 02
0.99 0.991..04
0.99.1
1.01.02
0.99 0.99
0.981..01
CTP*
0.99
0.98
0.97
0.98:1.03
0.97 04
0.954.04
CTP
0.99 04
0.99 03
0,97#.03
0.95#:06
0.93 07
0.91
CIP
0.98:.04
0,97
0,95#.06
0.94-1.08
0.93+.00
0,90:1.09
GNTP
0.68.1.28
0.63.1.34
0.62.1:31
0.59.1.32
0.57
0.52.1..32
FT
0.99.1:01
0.98.1.02
0.99:1.02
0.96.1.04
0.92.1.07
0.9211.07
0.99-.000
0.85+.04
0.80
0.714.03
0.70
0.684.02.
GCN
0.94
0.79
0.61
0.53+t.04
0.
0,41
NBENet
0.83::111
0.68
0.
0.53::.07
0.50
0.534.08
R GCN
0.97.1.03
0.82.1.11
0.60.1.13
0.52.1.11
0.50.1.09
0.45.1.99
RNN
0.932:006
0.874.07
0.79
0.7344.12
0.65 16
0.64
LSTM
0.98=.03
0.95+.04
0.89 10
0.84
0.77
0,78
GRU
0.95
0.94-2.03
0.872.08
0.814:13
0.74
0.75
4.
R-GCN
- ET -
NBFNet
+
NCRL
+ R5
4 CTP
EpiGNN-min
EpiGNN-mul
rcc8 1=1
rcc8 b=
rcc8 =
1.0
1.0
1.
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
Accuracy
0.0
2
3
7
0.0
8
0.0
4
5
interval algebra
interval algebra b
interval algebra b
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
2
3
7
4
4
5
9
k-hops
Figure 4: RCC-8 and Interval Algebra benchmark results (accuracy). R5 and CTP results for 5+ hops set zero since the model took longer than 30 minutes for inference. Models are trained on graphs with E {1,2, 3} paths of length l: E (2, 3, 4}. The best model for all cases is EpiGNN-min
reasoning: CLUTRR (Sinha al. 2019) and Graphlog (Sinha al. 2020). We also evaluate two novel benchmarks: one involving RCC-8 relations and one based on IA. These go beyond existing benchmarks on two fronts, illustrated in Figure [ (i) the need to go beyond Horn rules to capture relational compositions and (ii) requiring models to aggregate information multiple relational paths. For CLUTRR. RCC-8 and IA. test for systematic generalization, models are trained on small graphs and subsequently evaluated on larger graphs. In particular, for CLUTRR, the length k of the considered relational paths varied, while for RCC-8 and we vary both the number of relational paths b and their length k. In the case of Graphlog, the size of training and test graphs is similar, but models still need to apply learned rules in novel ways to perform well. We complement these experiments with an evaluation on the popular task of inductive knowledge graph completion. Here, the need for systematic generalization be used. The main purpose of this analysis is to analyze how well EpiGNNs perform compared to domain- speccaliied models in a more general setting. Finally, we also analyze the parameter and time complexity of EpiGNNs.
less obvious and a much broader family of methods can
7

---

Published as a conference paper at ICLR 2025
Table Results on Graphlog (accuracy). For each world, we report the number of distinct relation
sequences between head and tail (ND) and the Average resolution length (AR)). Results marked
with were taken from (Lu al. 2022) and those with from (Cheng et al. 2023). The best and second-best performance across all the models are highlighted in bold or underlined.
World ID
ND
ARL
E-GAT"
R-GCN"
CTP
RS*
NCRL
ET
EpiGNN-mu1
World 6
249
5,06
0.536
0.498
0.533+-0.03
0.687-+0005
0.702+20.02
0.496 + 0.087
0.648 + 0.012
World 7
288
4.47
0.613
0.537
0.513++0.03
0.749:+0.04
0.487 0.056
0.611+0.026
World
404
5.43
0.643
0.569
0.545:10.2
0.671:1:003
0.687:100022
0.55 1 0.092
0..49
World 11
194
4.29
0.552
0.456
0.553:+:0001
0.803=:0.01
0.637 + 0.091
0.758 + 0.037
World 32
0.700
0.581:00004
0.841=00003
0.914:10.026
Table 3: Hits@ 10 results the inductive benchmark datasets extracted from WNI8RR, FB 15k--233
with 50 negative samples. The results of other baselines except NBFNet are obtained from (Liu al. 2026) and the former from (Zhu et al. 2021). The best and second-bes, performance across all models are highlighted in bold or underlined.
WNISRR
FBI5K-237
v2
v3
Neural LP
74.37
68.93
46.18
67.13
52.92
58.94
$2,90
55.88
Rule Based
DRUM
74.37
68.93
46.18
67.13
52.92
58.73
52.90
55.88
RuleN
80.85
78.23
53.39
71.59
49.76
77.82
87.69
85.60
Grall
82,45
78.68
58.43
73.41
64.15
$1.80
82.83
89.29
COMPILE
83,60
79.82
60.69
75.49
67.64
82.98
84.67
87.44
TACT
84.04
81.63
67.97
76.56
65.76
83.56
85.20
69
SNRI
87.23
83.10
67.31
83.32
71.79
86.50
89,59
89.39
Graph-Based
ConGLR
92.93
70.74
92.90
68.29
REST
96.28
94.56
79.50
94.19
75.12
91.21
93.06
96.06
NBFNet
94.80
90.50
89.30
89.00
83.40
95.10
96.00
EpiGNN-mit min
92.45
85.99
84.18
85.77
91.67
95.54
93.74
93.45
Main results Results for CLUTRR, RCC-8, IA and Graphlog are shown in Table | Figure and Table 2 We report the average accuracy and 2o errors across 10 seeds for CLUTRR and seeds for RCC-8, IA and Graphlog. For CLUTRR, both variants of our model outperform all GNN and RNN methods, as well as edge transformers (ET). The EpiGNN-mui mmml model also on par with the SOTA neuro-symbolic methods NCRL (Cheng et al. 2023) and R5 (Lu et al. 2022). For RCC-8 and IA, as expected, the neuro-symbolic methods are largely ineffective, being substantially outperformed by our method as well as by ET. This highlights the fact that neuro- ceuro-symbolic methods are not capable of modeling disjunctive rules. Our model with min-pooling achieves the best results. Edge transformers also perform well, especially for RCC-8, but they underperform on the most challenging configurations (e.g. k = 9 and b = 3). Comparing the mull and min variants of our model, we find that mul performs better on single-pane pagle-pathhhaee problems (CLUTRR and Graphlog), while min leads to better results when paths need to be aggregated (RCC-8 and IA). For Graphlog, we only consider worlds that are characterized as 'hard' by Lu et al. (2022) with Average Resolution Length (ARL) > 4. Graphlog is amenable to path-based reasoning but is noisier than the other datasets. We find that EpiGNN-mul is outperformed by R5 and NCRL in most cases, thanks to their stronger inductive bias. However, OpiGNN-mul] clearly improves the SOTA for World 32. Moreover, EpiGNN-mu1 outperforms CTPs and the GNN baselines.
The results for inductive knowledge graph completion (KGC) are summarized in Table 3 This task involves link prediction queries of the form (h, r, ?). asking for tail entities that are relation r with some head entity h. We use the inductive splits of FB 15k-237 (Toutanova & Chen 2015) and WN18RR (Dettmers et al., 2018b) from by Teru al. (020) and the evaluation protocol of Bordes et al. (2013). In inductive KGC, models are evaluated on test graph which is disjoint from the training graph. Models thus need to learn inference patterns, but they may not need to systematically generalize them. Note in particular that the inference chains that are needed for the training and test graphs come from the same distribution and have the same length. Since all entities need to be scored, we use the forward-on only EpiGNN to efficiently score all entities in the knowledge graph with respect to the query relation r. The results show that EpiGNNs perform well, being competitive with SOTA models, and even achieving the best results in two cases, despite not being designed for this task.
8

---

Published as a conference paper at ICLR 2025
Ablations We confirm the importance of key archi- tectural components of our model through an ablation study on CLUTRR and RCC-8. To show the impor- tance of jointly training multiple lower-dimensional models, we show results for for variant with only m = 1 facet. To show the importance of modeling embeddings as epistemic states, we test variant in which we remove the requirement that embedding components are non-negative and sum 1. To show the importance of the bilinear composition function ø
Table 4: Ablation study results. We show the average accuracy across all configurations (i.e. 4-10 hops for CLUTRR, and h E {2.... 9} and b E (1,2,3) for RCC-8), and the accu- racy for the hardest setting (i.e. 10 hops for CLUTRR, and 3, k 9 for RCC-8).
CLUTRR
RCC-8
Avg
Hard
Avg
Hard
in ( we test a variant where the composition func-
EPiGNN
0.99
0.99
0.96
0.80
With facets=1
0.94
0.85
0.92
0.68
tion replaced by distmul (Yang et al.] (015) after
Unconstrained embeddings
0.30
0.21
applying a 4-layer MLP with ReLU activation to both inputs of (with the MLP being added to ensure the model is not underparameterised). To show the im- portance of the soward-backwatt nature of the model, we test a variant in which only the forward embeddings t are used. The results in Table B confirm the importance of all these components, with the use of embeddings epistemic states and the bilinear form of e being particularly important.
MLP+distmul composition
0.29
0.31
0.13
0.13
Forward model only
0.82
0.51
Parameter and time complexity Writing n. for the total dimensionality of the relation vectors and m for the number
CLUTRR
RCC-8
IA
Graphlog
a² of facets, the number of parameters is exactly [R] + m namely [R|n parameters for encoding the relation vectors and mn parameters for encoding the anj vectors in each of the m facets. In practice, we use a large number of facets, which allows us to keep n small. In particular, when comparing our model with existing neuro-symbolic models, after hyperparameter tuning each of the models, find that EpiGNNs are least two orders of magnitude smaller, as shown in Figure 5) The time complexity of
Parameters (mviltion))
10
10
10
ET
NCRL
R5
EpiGNN
Figure 5: Parameter complexity across the relation prediction benchmarks.
the EpiGNN is O((E'n + [Fl m ), and thus highly efficient
given that 2 is small in practice. A comparison with the main baselines is shown in Appendix G.5
RELATED WORK
Neuro-symbolic methods Neuro-symbolic methods such as DeepProbLog (Manhaeve et al. 2018)
and NTPs (Rocktäschel & Riedell (017) are essentially differentiable formulations of inductive logic programming. where the latter is concerned with learning symbolic rule bases from sets of examples (Muggleton, 1997 Muggietnn & De Raedi] 1994 Nienhuys-Cheng de Wolf] 1997 Evans & Grefenstette) 2018). Although these methods are capable of systematic reasoning, scalability is a key concern. For instance, by generalizing logic programming. NTPs and DeepProbLog rely on the exploration of a potentially exponential number of proof paths. Another challenge to scalability comes from the fact that the space of candidate rules grows exponentially with the number of relations (Evans& & Grefenstette 2018). More recent methods, including R5 (Lu al. 2022), CTPs (Minervini ctt al. (020b) and NCRL (Cheng et al., 2023) are somewhat more efficient than NTPs. R5 uses Monte Carlo Tree search with a dynamic rule memory network, CTPs use learned heuristic filter function on top of NTPs to reduce the number of explored paths during backward chaining, and NCRL focuses on learning how to iteratively collapse relational paths. These methods can systematically reason but only NCRL scales to knowledge graphs such as FB15k. Moreover, both R5 and NCRL are limited by their over-reliance on single path sampling and cannot deal with disjunctive rules. CTPs cannot handle benchmarks such as RCC-8 and IA either, as they cannot model the constraint that the different relations are pairwise disjoint and jointly exhaustive. Some approaches, such as Logic Tensor Networks (Badreddine et al. 2022) and Lifted Relational Neural Networks (Sourek et al.) 2018) rely on fuzzy logic connectives to enable more efficient differentiable logic programming. These frameworks are typically quite general, e.g. being capable of encoding GNNs special C case (Sourek et al. (02T). As such, they should be viewed as modeling frameworks rather than specific models. We are not aware of work that uses these frameworks for systematic generalization.
9

---

Published as a conference paper at ICLR 2025
More generally, within the context of statistical relational learning, methods such as Markov Logic Networks (Richardson & Domingos] (006) have been studied, which can learn weighted sets of arbitrary propositional formulas, but suffer from limited scalability, limitation which is inherited by differentiable versions of such methods (Marra & Kuželka 202T
Systematic reasoning There has been large body of work on learning to reason with neural
networks, including recent approaches based on GNNs (Zhang et al. 2020; Zhu et al. [202] Zhang &
Yao 2022), pre-trained language models (Clark et al. 2020; Kojima et al. [2222]Creswell et al. (002))
or tadeor-made architectures for relational reasoning (Santoro et al., 2017 Bergen et al. 2022 Most of these methods, however, fail at tasks that require systematic generalization (Sinha et al. 2019 2020)
and are prone learning reasoning shorteuts (Marconato et al., 2023 Zhang al. (023a). NBFNet
(Zhu et al., (02T)) R-GCN (Schlichtkrull et al. (018). and graph-convolution methods (Dettmers) et al. 20188]] Vashishth al. 2020) are examples of scalable and (mostly) parameter-efficient methods designed for knowledge graph completion. Such methods typically leverage knowledge
graph embedding methods (Bordes al., 2013 Trouillon et al., 2017 Yang et al., 2013) in the
message passing step. NBFNet uses such methods to compose relations and anchors the embeddings to head entity develop path- based relational representations. GNNs for logical reasoning have also been proposed, including R2N (Marra et al. 2023) and LERP (Han et al. 2023), but their focus again on knowledge graphs and not systematic reasoning. For instance, R2N uses multi-layer perceptrons (MLPs) for information composition and sum aggregation. This increases the capacity of the model, which can be beneficial for learning statistical regularities from knowledge graphs, but which at the same time also hurts GNN's systematic reasoning ability, we have seen in ablation analysis. EpiGNNs are inspired by the idea of algorithmic alignment (Xu et al. (2020), ie. aligning the neural architecture with the desired reasoning algorithm. Edge Transformers (Bergen let al., 2021) also rely on this idea to some extent, aligning the model with relational reasoning by using triangular variant of attention (Vaswani al. (017) 7) to capture relational compositions. However, compared to EpiGNNs, edge transformers are less scalable, as they cannot operate on sparse graphs, less parameter-efficientt, and less successful at systematic generalization, as we have seen in our experiments. Finally, the problem of systematic generalization has also been studied beyond relational reasoning. For instance, there is existing work on benchmarking length generalization for sequence based methods such pretrained transformers and recurrent networks, including SCAN (Lake& & Baroni 2018), LEGO (Zhang et al. 2023b) and Addition (Nye et al. 2021).
6 CONCLUSIONS
We have challenged the view that Graph Neural Networks are not capable of systematic generalization in relational reasoning problems, by introducing the EpiGNN, a principled GNN architecture for this setting. To impose an appropriate inductive bias, node embeddings in our framework are treated as epistemic states, intuitively capturing sets of possible relationships, which are iteratively refined by the EpiGNN. In this way, EpiGNNs are closely aligned with the algebraic closure algorithm, which used for relational reasoning by symbolic methods, and formal connection with this algorithm They rival neuro-symbolic
has been established. EpiGNNs are scalable and parameter-effiiien methods on standard systematic reasoning benchmarks such as CLUTRR and Graphlog, while clearly outperforming existing GNN and transformer based methods. Moreover, we have highlighted that existing neuro-symbolic methods have an important weakness, which arises from an implicit assumption that relations can be predicted from single relational path. To explore this issuc, we have introduced two new benchmarks based on spatio-temport calculi, finding that ncuro-symbolic methods indeed fail on them, while EpiGNNs still performs well in this more challenging setting. Finally, despite being designed for systematic reasoning, our experiments show that EpiGNNs rival SOTA specialized methods for inductive knowledge graph completion.
Limitations The EpiGNN is limited by its statistical nature, where the parameters of the model will inevitably be biased by training data artefacts. While we have shown that our model can perform well in settings where existing neuro-symbolic methods fail (i.e. spatio-temporal benchmarks), the much stronger inductive bias imposed by the latter puts them at an advantage in severely limited settings. This can be seen in some of the Graphlog results. For variant of CLUTRR where the model is only trained on problems of size k E (2, 3}. our model is also outperformed by the best neuro-symbolic methods (shown in Appendix G
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was supported by the EPSRC grant EP/W003309/L
REFERENCES
James F. Allen. Maintaining knowledge about temporal intervals. Commun, ACM, 26(11)8832-83,, 1983a. doi: 10.1145/182.358444 URL https::///oooo org./o......... 1145/182 358444
James F Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26 (11):832-843, 1983b.
Nouhad Amaneddine, FranFoinssis Condotta, and Michael Sioutis. Efficient approach to solve the minimal labeling problem of temporal and spatial qualitative constraints. In Francesca Rossi (ed.), IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pp. 696-702. UCAL/AAAL, 2013. URL http:// aaai org/ htt//oc/inndee http://CCAA//AAAA//aaaaaaaaa
6642
Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. Artificial Intelligence, 303:103649, 2022.
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? In International Conference on Learning Representations, 2019, URL http:/ttt//opereeeessss net poet/forune (alorrummd--Heeeeee
Leon Bergen, Timothy J. O'Donnell, and Dzmitry Bahdanau. Systematic generalization with edge transformers. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Perey Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 1390-1402, 2021. URL /tt//tttps///prrceeiingggg neurips cc/ ccppaper///aa 202
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL
newrips cttpsper.cppppppppeeceee es/ppppp/20113 / Ei File/ Fil1:/eeccaa1128aa11312226683333
Mathias Broxvall, Peter Jonsson, and Jochen Renz. Disjunctions, independence, refinements. Artif. Intell., 140(1/2):153-173, 2002. doi: 10. 00.1016//00044372200222200 0og//90.106/500000 3702 (02) 00224-2
URL h/tps://doi
Kate Cain, Jane V Oakhill, Marcia A Barnes, and Peter E Bryant. Comprehension skill, inference- making ability, and their relation to knowledge. Memory cognition, 296):850-859, 2001.
Kewei Cheng, Nesreen Ahmed, and Yizhou Sun. Neural compositional rule learning for knowledge graph reasoning. In The Eleventh International Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL net/ 2id FBVFFYVVVVYR
Kyunghyun Cho, Bart van Merrienboer, Çaglar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Alessandro Moschitti, Bo Pang, and Walter Daclemans (eds.), Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, Special Interest Group of the ACL, pp. 1724-1734, ACL, 2014. doi: 10.3115/V1/D14-1177 URL https 0..0i.org/10.3115/111/1...2
11

---

Published as a conference paper at ICLR 2025
Peter Clark, Oyvind Tafjord, and Kyle Richardson. Transformers soft reasoners language. In Christian Bessiere (ed.), Proceedings of the Twenty-Nine Ninth Interaational Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 3882-3890, ojcai.org. 2020. doi: 1022496//JCAA2222055333
URL htl..htps://// http:://oooooorgg//// /wtp://r/......3////// caa 2220//302/33
Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inffrence: Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-3, 2023. OpenReview.net, 2023.
URL https::/
net /pdf ? d= F3wg50-A4
Zhan Cui, Anthony Cohn, and David A. Randell. Qualitative and topological relationships in spatial databases. In David J. Abel and Beng Chin Ooi (eds.), Advances in Spatial Databases, Third International Symposium, SSD 93, Singapore, June 23-25, 1993, Proceedings, volume 692 of Lecture Notes in Computer Science, pp. 296-315. Springer, 1993. doi: 10.1007/3-540-5666) -_11
URL /
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. Proceedings of the AAAI Conference on Artificial Intelligence, 32 (1), Apr. 2018a.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. Proceedings of the AAAI Conference on Artificial Intelligence. 32(1), Apr. 2018b. doi: 10. wtw.//9/wwa.......1111. URL https: aaai. org/ index
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics. 2019. doi: 10.18653/V1/N19-0 1423. URL
https:://dii.rr/// httpr//...11653/11/mmo 1423
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61:1-64, 2018.
Chi Han, Qizheng He, Charles Yu, Xinya Du, Hanghang Tong, and Heng Ji. Logical entity rep- resentation in knowledge soowledge-graphs for differentiable rule learning. In The Eleventh International Conference Learning Representations, 2023. htR.:ttss: /tlpttssss//pereee/// /wtp///eeevvveeeeeeeeeeeeeeeeeee ew net. forum?
id=Jdgo-ht TuTN
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory, Neural Comput.. 98): 1780, 1997. doi: 10. 1.1126EEE...199.999 1735. URL 1997. 9.8 1735
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 24892-24928. Curran Asso- ciates, Inc., 2023. URL htt.:hcpp..//poceecinn...errrree F023/file/4e550 20224f/1eee855222222226666533333
filess/aperrrrr/ Conteerrrooofeeecc
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. 2017.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference Learning Representations, ICLR 2017, Toulon. France, April 24. 26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: //op/r/eeee//ewe net.
12

---

Published as a conference paper at ICLR 2025
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo. Berton Earnshaw, Imran Haque, Sara M Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang. Wilds: A benchmark of in-the-wild distribution shifts. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5637-5664. PMLR, 18-24 Jul 2021. URL https://proceee//
mlr. press / v 39/ kohl1a.a.............. http//hhhhhaaamllllla... html
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwa- sawa. Large language models are zero-shot reasoners. In Sanmi Koyejo, S. Mo- hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December nips http:///aaapreeieee///p///////// haahh/ ottpaa/eeeeoeaaataaaatooooorerre
2022, 2022. URL
html
Andrei A. Krokhin, Peter Jeavons, and Peter Jonsson. Reasoning about temporal relations: The tractable subalgebras of allen's ' interval algebra. J. ACM, 50(5):591-66) 640, 2003. doi: 10.1145/
776638.876633 URL httpp:: otg/10 1145/ 87 668..66666686 876639
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-fo--sqqeeece recurrent networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 Proceedings of Machine Learning Research, pp. mlr. www.ppres//vei
PMLR, 10-15 Jul 2018. URL httt::tt/pooceeeeeeeee html
Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40:e253, 2017.
Sanjiang Li, Zhiguo Long, Weiming Liu, Matt Duckham, and Alan Both. On redundant topological constraints. Artificial Intelligence, 225:51-76, 2015. ISSN 0004-3702. doi: https://doi.org/10..00 1016/ j.artint 2..tiit.2015.03.000 URL httpt:
pi1 031/8000437021500033
Tianyu Liu, Qitan Lv. Jie Wang, Shuling Yang, and Hanzhu Chen. Learning rule- induced subgraph representations for inductive relation prediction. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neu- ral Information Processing Systems, volume 36, pp. 3517-3535. Curran Associates, Inc., http://n....ooooss.../epeeeeeeee
2023. URL htttps::/pproceeediini neurips wwwpaper.ppp.....eeee. saappperrffiesspeeeee fttpprrrrflleeeepee//2223// File 7tll://0066777eeee555ee666677763 Sor.ra/eeeeetttteeeeeeeeeeeeeeee www.--Canoeeeecceeeeeeee pdf
Zhiguo Long, Michael Sioutis, and Sanjiang Li. Efficient path consistency algorithm for large qualitative constraint networks. In IJCAI International Joint Conference on Artificial Intelligence, 2016.
Shengyao Lu, Bang Liu, Keith G. Mills, Shangling Jui, and Di Niu. R5: rule discovery with reinforced and recurrent relational reasoning. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL net foorumm1d-22xxNNieeee
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Gareet (eds.), Ad- vances in Neural Information Processing Systems, volume 31. Curran Associates. Inc.. 2018. URL https::/ http::ssssssisrsseeeeeeeeeeeeeee fi lessepper//2011 weee//ddd333 11700/5///2b60222236666666666333
neurips
Emanuele Marconato, Gianpaolo Bontempo, Elisa Ficarra, Simone Calderara. Andrea Passerini, and Stefano Teso. Neuro-symbolic continual learning: Knowledge, reasoning shortcuts and concept rehearsal. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine
13

---

Published as a conference paper at ICLR 2025
Learning. volume 202 of Proceedings of Machine Learning Research, pp. 23915-23936. PMLR, 23-29 Jul 2023.
Giuseppe Marra and Ondřej Kuželka. Neural markov logic networks. In Cassio de Campos and Marloes H. Maathuis (eds.), Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Reseurch, pp. 908-917. PMLR, 27-30 Jul 2021.
Giuseppe Marra, Michelangelo Diligenti, and Francesco Giannini. Relational reasoning networks, 2023. URL httpt://aaaxiii. org. 221022166226 06. 0039933333333333
Alexander H. Miller, Adam Fisch, Jesse Dodge,
Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. In Jian Su, Xavier Carreras, and Kevin Duh (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pp. 1400-1409. The Association for Computational Linguistics, 2016. doi: 10. (0.18653/V1/D16-11 1147. URL https 7/doi. org/ 10. 18653/v1/616-1111
Pasquale Minervini, Matko Bosnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In The Thirty- Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 5182-5190. AAAI Press, 2020a. doi: 111669//AAALV31100 70.1609/aaai v34104.5962
uttpttps: http:/dooi.ooo org/
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 6938 6949. PMLR, 2020b. URL http:://proceedingg ngs www.m..rrssss....mmmmmmmmmmmmmme
http//mnnevinnn220m html
Stephen Muggleton and Luc De Raedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19:629-679, 1994.
Stephen H. Muggleton. Inductive logic programming, New Gener. Comput., 8(4):295-318, 1991. doi: 10.1007/BFF0003009,
Shan Nienhuys-Cheng and Roland de Wolf. What is inductive logic programming? Springer, 1997.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski. Jacob Austin, David Bieber, David Dohan, Aitor Lewkowyez, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: Scratchpads for intermediate computation with language models, 2021. httts::::///axt
org abtgg//bs///0 2b12 00114
David A. Randell, Zhan Cui, and Anthony G. Cohn. A spatial logic based on regions and connection. In Bernhard Nebel, Charles Rich, and William R. Swartout (eds.), Proceedings of the 3rd Interna- tional Conference on Principles of Knowledge Representation and Reasoning (KR 192). Cambridge, MA, USA, October 25-29, 1992 pp. 165-176 Morgan Kaufmann, 1992.
Jochen Renz Maximal tractable fragments of the region connection calculus: A complete analysis. In Thomas Dean (ed.), Proceedings of the Sixteenth International Joint Conference Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July 31 August 6, 1999. 2 Volumes, 1450 pages, pp. 448 455. Morgan Kaufmann, 1999. URL 2apers/065...pdr
wtt.://o///ooceeigg///////// 1/
Jochen Renz and Gérard Ligozat. Weak composition for qualitative spatial and temporal reasoning.
In Peter van Beek (ed.), Principles and Practice of Constraint Programming CP 2005, 11th International Conference, CP 2005, Sitges, Spain, October 1-5, 2005, Proceedings, volume 3709 of Lecture Notes in Computer Science pp. 534 548. Springer, 2005, doi: 10. 1007/0 15647511 40. URL htllhttps:// : orgg Ttt.//1000000000000
40
14

---

Published as a conference paper at ICLR 2025
Matthew Richardson and Pedro M. Domingos. Markov logic networks. Mach. Learn., 62(1-2):
107-136, 2006. doi: 10. 10.1007/5109994000-888833 URL
019994-006-583--11
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Prucessing Systems 2017, December 4-9, 2017, 1 Long Beach, CA, USA, pp. neurips wwtppppppppp.....ccpcccc 2017 hash/
3788-3800, 2017. URL httpppt:/pppopeeettpttt 12250010016660000522200666686883 -bttsccce--bbttaaae .html
Adam Santoro, David Raposo, David G. T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter W. Battaglia, and Tim Lillicrap. A simple neural network module for relational reasoning. In Isabelle Guyon, Ulrike von Luxburg. Samy Bengio, Hanna M. Wallach, Rob Fergus, V. N.
Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neurul Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 4967 2017. URL paper 221/22117//22 hww.//aa//aaaae
www.:iinnnn....rr..e... oc/ wtw.:9955aaaaaa-a-aaaaaaaaa .ttraattttmmmll
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Aldo Gangemi, Roberto Navigli. -arrarEsther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mehwish Alam (eds.), The Semantic Web 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings, volume 10843 of Lecture Notes in Computer Science pp. 593-6073777 Springer, 2018 doi: 100/9977 1----9949-1--9-- 38. URL https://doi. org/ 10. 3 319 93417 __ 38
Steven Schockaert. Embeddings as epistemic states: Limitations on the use of pooling operators for accumulating knowledge. Int. J. Approx. Reason., 171:108981, 2024. doi: 10. 10.1016/1.ARR.222. 108981. URL httpt::ttt:/o/o org/ 1tte:/11..1111..1...
2023. 108981
Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. CLUTRR:
A diagnostic benchmark for inductive reasoning from text. In Kentaro Inui, Jing Jiang, Vincent
Ng. and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empirical Methods in
Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pp. 1505-4514 Association for Computational Linguistics, 2019. doi: (0.11865//1/DD1-145555 1/589-1458 URL https: //doi. 11653/v1/D133
Koustuv Sinha, Shagun Sodhani, Joelle Pineau, and William L. Hamilton. Evaluating logical generalization in graph neural networks. CoRR, abs/2003.06560, 2020. httLhs:s::///ar
org/abs/ 2003. 06560
Gustav Sourek, Vojtech Aschenbrenner, Filip Zelezný, Steven Schockaert, and Ondrej Kuzelka. Lifted relational neural networks: Efficient learning of latent relational structures. J. Artif. Intell. Res,, 62:69-100, 2018.
doi: 1.6.3/JIRR.1112200 httphts/////oi..r///.....1
jair.1.11200
Gustav Sourek, Filip Zelezný. and Ondrej Kuzelka. Beyond graph neural networks with lifted relational neural networks. Mach. Learn. 11077):695--138, 2021. doi: 10.1007/
URL /tt.//////////.....///000000/110
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 9448 9457. PMLR, 13-18 Jul 2020. URL https: https:://proceedings www.rrppessssse wttps///v9/tttttutee html
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text in- ference. In Alexandre Allauzen, Edward Grefenstette, Karl Moritz Hermann, Hugo Larochelle, and Scott Wen-tau Yih (eds.), Proceedings the 3rd Workshop Continuous Vector Space Models and their Compasitionalityy pp. 57-66. Beijing, China, July 2015. Association for Computational Lin- guistics. doi: 10.18653/v1/W1.. 5-007-
httpttts:::// acl antho oog..oo......................... wat.oorgg/550000 4007
15

---

Published as a conference paper at ICLR 2025
Théo Trouillon, Christopher R. Dance, Éric Gaussier, Johannes Welbi, Sebastian Riedel, and Guil- laume Bouchard. Knowledge graph completion via complex tensor factorization. J. Mach, Learn. Res., 18(1):4735-4772, January 2017. ISSN 1532-4435.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition baaeed multi- relational graph convolutional networks, In International Conference on Learning Representations, 2020.
ew net/ forum? S A__4ttPr
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4.9, 2017, Long Beach, CA, USA, pp. 2017. URL httpp:://roceceigggggg hew.oocccednnnn...u........ neurips CC cc/ppcppocoocc pappp/pppppeeeeeaaaeeeeeaeeaaaea 2017 / Abstract html
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. net /
OpenReview.net, 2018. URL https: www.oppeeee.....
Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In The Eleventh International Conference on Learning Representattins, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. U htt.:ttppp...................... http:////ppeeeeeieeeee net / d= 6Je@ZDDD
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S. Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
httts:://ppenreviie net. htte:/ooommmlldxxxeeeeee.ee
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference on Learning Representations, 2021. URL http:::t/ /tttps://operrevieww net/ forummid-UH cmocLJC
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In 3rd International Conference Learning Representations. ICLR 2015, San Diego. CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Honghua Zhang. Liunian Harold Li, Tao Meng, Kai-Wei Wei Chang, and Guy Van den Broeck. On the paradox of learning to reason from data. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pp. 3365-3373, org. 2023a. doi: 10.24966/UCAA12222357555 URL 24963/1jca11 2023/375
Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: a synthetic reasoning task, 2023b. httptttt////attt
org/abs/220s 2206. 04301
Yongqi Zhang and Quanming Yao. Knowledge graph reasoning with relational digraph. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel Médini (eds.), WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pp. 912-924, ACM, 2022. doi: 10.1145/945544..5522000 URL https: /ow::///o...o org 10 1. 114. wwt..1111//4444.4.1 351200
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httttttts/:::oeteeeeee ew. net. pest/forumin www.moormddiiommm 76kkttt
16

---

Published as a conference paper at ICLR 2025
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascii A. C. Xhonneux, and Jian Tang. Neural bellman- ford networks: A general graph neural network framework for link prediction. In Marc Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 29476-29490, 2021, URL URtttpp:://ppoeeeeeene neurips. CC wwwpppppp/////./ /hash/ ffa wbw.ratttttttttttttt.....t.
17

---

Published as a conference paper at ICLR 2025
A SEMANTICS OF ENTAILMENT
For simple path rules of the form (I). the semantics of entailment can be defined in terms of the immediate consequence operator. Let KF= be the grounding of w.r.t. F. i.c. for each rule of the form r(X,, Z) & (x, Y) A r2(Y, Z) in K. K5 contains all the possible rules of the form r(a. c) - 71 (a, b) A r2 c) that can be obtained by substituting the variables for entities that appear in F. Since assume that both F and KC are finite, we have that K is finite as well. Let Fo F and for i 2
define:
Fi=F,1 U (r(a,c) 3b E E. .),(a,b), E Fi-1 and (r(a, +- ri(a,)) cr)(b.)) E Kc}}
Since there are finitely many atoms r(a, c) that can be constructed using the entities and relations appearing in KC,, this process reaches a fixpoint after a finite number of steps, i.e. for some & E N we have F, Fe+1. Let us write FF" for this fixpoint. Then define FUK F r(a, b) iff r(a, b) E F'. Example 1. The canonical example for this setting concerns reasoning about family relationships. In this case, KC contains rules such as:
grandfather(X, Z) + father(X,t)) A mother(Y, Z)
If F |father(bob, alice), mother(alice, eve)} then Ky contains rules such as:
grandfather (bob, eve) father(bob, alice) mother(alice, eve) grandfather bob, alice) + (aoteer(oob.rr alice) A mother(alice alice) grandfather (bob, bob) father(bob, alice) mother(alice bob)) grandfather (bout, eve) + father(bob, eve) A mother(eve,, eve)
We have Fi = |father(bob, alice), mother (alcher eve), grandfather(bob, eve) with Fi F2= We thus find: K. U F F grandfather bob, eve).
For the more general setting with disjunctive rules and constraints, entailment in terms of Herbrand models. Given a set of disjunctive rules and constraints I. and a set of facts F, the Herbrand universe MK. is the set of all atoms of the form r(a, b) which can be constructed from a relation and entities a, 6 appearing in KUF. A Herbrand interpretation w is a subset of UKK.F- The interpretation satisfies ground disjunctive rule of the form 8 (a, e..... (sy(a, VVy......aaa, c) < r-ri(a, (a. b)Λ r2 (b,b, c) iff' either (ri b), (b c)} & or w n sss (a, c).... sa c) * 0. The interpretation w satisfies ground constraint of the form + ri b) A (2(a, b) iff {ri (a, b), b),r2 (a(
define the semantics of
w. We say that w is a model of the grounding KCy iff w satisfies all the ground rules and constraints in KCr. Finally, we have that KU F == r(a, b) iff r(a, b) is contained in every model of K,p.
B SIMPLE PATH ENTAILMENT: PROOF OF PROPOSITION 1
The correctness of Proposition immediately follows from Lemmas 1 and 2 below.
Lemma 1. Suppose there exists relational path ri;...;;7 Tk connecting and b in Gy such that can be derived from T1;...; Tk- Then it holds that CFF.F F r(a, b).
Proof. Let r....;; l'k be a relational path connecting a and b, such that r can be derived from ri;...; Tk- Then contains facts of the form ri (a, æ1), derivation from Fi;...:; to After the first derivation step, we have relational path of the form Tii...i; 2; S; Ti+ii... TR. In this case, K. contains rule of the form s(X, Z) + T (X, Y) A ri(Y, Z). This means that K. U F - s(x;-,, 2;)) v.). We thus have relational path of the form rr;...; s; Ti+1i Tk, where each relation is associated with an atom that entailed by K. KU F. Each derivation step introduces such an atom (while reducing the length of the relational path by 1). After k: - steps, we thus obtain the atom r(a, b), from which it follows that KUF r(a, b). O
b). Let us now consider the
Lemma 2. Suppose that KU F + ra, b). Then it holds that there exists a relational path ri;...: connecting and b in Gy such that can be derived from rı; ii....? Tk-
18

---

Published as a conference paper at ICLR 2025
Proof. Recall from Appendix A that KU = iff r(a.b) FF. It thus suffices to show by induction that r(a, b) E Fi implies that there exists a relational path r1:...;7 connecting a and in GT such that can be derived from ri:....kk First, if r(a, b) E Fo then by definition there is relational path r connecting a and b in Gr, meaning that the result is trivially satisfied. Now suppose that the result has already been shown for - Let r(a, b) Fi \ Fi Then there must exist facts ri (a, r) and r2 6) in F such that K contains a rule of the form r(X, 2) + ri(,, AT2 Z). By induction, we have that there is relational path s1; si; ... St, connecting a and x such that r1 can be derived from this path, and a relational path f ...; tt, connecting x and b from which can be derived. We then have that $1; St, ti;.... ...; tt, a path connecting a and Furthermore, we have that r2 can be derived from this path, and thus also
C REASONING ABOUT DISJUNCTIVE RULES USING ALGEBRAIC CLOSURE
We consider knowledge bases with three types of rules. First, we have disjunctive rules that encode relational compositions:
$1 (X, V... V (), (i A (2,
(7)
Second, we have constraints of the following form:
Le (x)
(8)
meaning that r1 and 12 are disjoint. Finally, we consider knowledge about inverse relations, expressed using rules of the following form:
(Y, < (X,))
We now deseribe the algebraic closure algorithm, which can be used to decide entailment for calculi such as RCC-8 and IA. We also describe an approximation of this algorithm, which we call directional algebraic closure.
Full algebraic closure Let us make the following assumptions:
The knowledge base IC contains rules of the form encoding the composition relations T1 and r2-
We also have that IC contains the rule VrER r(X,Y) < T, expressing that the set of relations is exhaustive.
For all distinct relations r1,72 E R, * 12, K. contains constraint of the form 8 expressing that the relations are pairwise disjoint.
For every r E there is some relation R, such that K. contains the rules r(Y,X) F(X, Y) and XXY < r(X,Y) Y), expressing that f is the inverse of r.
IC contains no other rules.
Let us write or2 for the set of relations that appears in the head of the rule defining the composition of r, and 72 in K. no such rule exists in K. for r, and 72 then we define r o r2 = R. Let & be the set of entities that appear in F. Let assume that F is consistent with K., i.e. KC KUFK 1.
The main idea of the algebraic closure algorithm is that we iteratively refine our knowledge of what relationships possible between different entities. Specifically, for all entities e, f E, we define the initial set of possible relationships as follows:
(r)
f) ifr(f.e) EF
x x
(f)
R otherwise
where f is the unique relation that is asserted to be the inverse of r in K. Note that because we assumed F to be consistent, if r(e, F and (f(re) e) e F it must be the case that r' === f. We now ef. Specifically. for 2 1, we define the refinement step:
iteratively refine the sets (i)
x of = x(i=1) n (i-1) o of ((i-1)
1g E
(10)
19

---

Published as a conference paper at ICLR 2025
where, for X, S R, we define:
XoY=Urro|rex,seW
Since each of the sets ( only contains finitely many elements, and there are only finitely many such sets, this process must clearly converge after a finite number of steps. Let us write Xef of the sets of relations that are obtained upon convergence. For many spatial and temporal calculi, we have that r E Xey f iff KUFU })} / L. In other words, Xes encodes everything that can be inferred about the relationship between e and f. In particular, we have have K. KUFF FuFFF(e.f iff X-/ = {r]- Note that this equivalence only holds for particular calculi: in general, KUFF r(e, f) does not imply Xas = {r). Furthermore, even for RCC-8 and IA, this equivalence only holds because the initial set of facts F is disjunction-free. We refer to (Renz. 1999. Krokhin et al. 2003 2002) for more details on when algebraic closure decides entailment.
Broxvall et al.
Directional algebraic closure The algebraic closure algorithm relies on sets x(() for every pair of entities, which limits its scalability (although more efficient special cases have been studied (Amaneddine et al. 2013)). Any simulation of this algorithm using neural network would thus be unlikely to scale to large graphs. For this reason, we study an approximation, which we refer to as directional algebruic closure. This approximation essentially aims to infer the possible relationships between a fixed head entity ht and all the other entities from the graph. The relationship between h and given entity e is determined based on the paths in & connecting to e. For this approximation, we furthermore omit rules about inverse relations. Other than this, make the same assumptions about as before. We now learn sets _ which capture the possible relationships between and e. These sets are initialized as follows:
{r} if ef) F R
X
otherwise
We define for i 2 I, the refinement step:
x(() = x(( 1)
(x os(
(11)
with
x x 1) os- =s= Urossr
where T1 o 72 is defined as before. We write Xe to denote the sets (1) that are obtained upon convergence. Clearly, after finite number of iterations we have x! (+1+ Note how the directional closure algorithm essentially limits the full algebraic closure algorithm to compositions of the form Xhe o Xee, for entities e and f such that there a fact of the form r(e, f) in F. As the following result shows, the algorithm is still sound, although it may infer less knowledge than the full algebraic closure algorithm.
For a rule of the form (7). we write head(p) to denote the set {si,..., 85} of relations appearing in the head of the rule and body(p) to denote the pair (21, of relations appearing the body.
Proposition 3. Assume that K. consists of (i) rules of the form 77. (ii) for each pair of distinct relations Tı. 12 the disjoinmess constraint 88, and (iii) the rule V VreR rXX, (X,Y)= + Let e E E.
holds that K. J.F }= Vrex, r(h,e). e).
Vrex!") r(h,e). e). Indeed, either x= (r(h, }}} with r(h, e) E F, in which case the claim clearly holds, or x( = R. in which case the claim holds because X contains the rule VrER r(X, + T. Now suppose we have already established KC F + VrexçeDD r(h,e) e) for every E To show that KU F +
Proof. We show this result by induction. First note that we have IC KUJ }
VrEX. r(h,e) e), it is sufficient to show that IC UF -= -r(h, e) for every r E x(i-1), x(() Let r E (((-1), x(() Then there must exist some s(S,e) E F such that r $ x((i1)) 8. In that case, for every t xfii") we have & This means that for every t E x(i-)) there exists some rule Pt in K. such that body(pt) s) and heads(pt). We have for every i E X x((-1) that
20

---

Published as a conference paper at ICLR 2025
tth,f - V Vuchnads (p)) (h, e). Moreover, because of our assumption that K. encodes that all relations are pairwise disjoint, for # we have K. = a(h, e) -h, e). We thus find for every i x/i-1) that KUF + ((h, 1) r(h, e). By induction we also have KCFFF } ViexfED l(t, e).
Together we find KC KUFF el(,,e).
D EXPRESSIVITY: PROOF OF PROPOSITION 2
In this section, we provide a proof for Proposition 2 which we first restate formally in Proposition 4 We will show that the base EpiGNN model (i.e. the forward model) already capable of simulating the directional algebraic closure algorithm. The proof associates the embeddings e(*) from the GNN with the sets x!" We show the result for the min min-pooling operator t'min defined as follows:
min X1 , Xk)
Mmin (X1, Xk) (iim(x1...... X1el11
(12)
Proposition 4. Let be a set facts and K. knowledge base satisfying the conditions of Proposition 3 Furthermore assume that K F is consistent, i.e. KFF / L. Let x!!) be sets of relations that are constructed using the directional algebraic closure algorithm, and let e) denote the j coordinate of e Let the pooling operation be chosen as to Mmin- There exists a parameterisation of the vectors r and aij such that the following refinement condition for (17 holds:
_ 2 (ry (rsseett 0,2 0,25 2x (+11)
(13)
Proof. Let Ti, I' be an enumeration of the relations in R U {id}, where we fix T1 id. Let aij = (a] ... a ) be defined for as follows (i E (I,...,.})
in
Irioryl
otherwise
where define id o ry Ty for every j {1...., n). Note that a, indeed satisfies the requirements of the model: the coordinates of a, are non-negative and sum to I, while a1, = one-hor(j) follows from the fact that id o ry = rj. Furthermore,
define rj one-hot(j).
We show the result by induction. For = 0, if F contains a fact of the form rı e). we have x {ri). We show that (!)) is non-zero in the 1th coordinate and zero everywhere else. We have:
@(h r1) EENree Eraay= = =neehoo() one-hot(I)
This already shows that (!)) is zero in all coordinates apart from the th Now let f # h and rp be such that e) e) E F. We have
(())) rp) DE
12 Σ ΣΣ r =
Σ aip
17.
We need to show that the thh coordinate of the latter vector non-zero. Since U U.Fi consistent and F contains both (h, e) and e)) it has to be the case there there is some g E {1, (1,..., n) such that
E rg Tp- There thus exists some 4 E (1....n) n.) such that the 1th coordinate of agp is non-zero. Since all vectors of the aip vectors have non non-negative coordinates, it follows that the 1" coordinate of
1 Σ. aip is non-zero. We have thus shown that {r, le) > 0,2 = < n) (m) x!") 2 x!!).
If F does not contain any facts of the form rı (h, e), then x!!) R. We need show for each I T {2...., n that either e/ is non-zero or & X! We have that el is non-zero if the 1th component
of (((()) .rp) is non-zero for every fact of the form (f, in F. where f * h. Consider such have f()) (t.-...)) (.....).. 2). The 1th component of (((()) rp)) n Σ. aip thus only be 0 if the th
fact (f( and assume the th component of ((P(0) .rp) is actually O. Since f +
21

---

Published as a conference paper at ICLR 2025
component of asp is 0 for every i. This implies that 71 & r, e rp for any i E (1,..., n). from which it follows that rı & x!!).
2 x holds for every entity e. We show that (13) must then hold as well. We first show x!") 2 fry ej 1-1 > 0,2 2 s j S n). To this end, we need to show that for each ry E x!(-1) x it holds that ejt 0. If E x! x(") means that there is some ry(f,e) E F such that rj $ x Tp. This is the case if $ rg rr for every rq E x/- This, in turn, means that the j"h component of Bgp is 0 for every g such that "q x Furthermore, by the induction hypothesis, we know that gg $ xx(-1) means f4 O. In other words, for each q we have that either fÿ = 0 or that the jth component of agp is O. It follows that the j"h component of (f(() ,rp) is O, and thus also that ef =0 0.
Now suppose that Xa (1111) 2 try >
i+1 = 0. We need We now show (ry lestt > 0,2 S n) 2 x ((+11) Let j be such that ef > ej
to show that ry $ Xe ((+1) If > i+1 = 0 there needs to be some (p(S,e) E F such that the 5th component of (f rp) is O. We have
o( rpp
ΣΣ
firfar Itaa
So when the jth component of ((P(1), ) is O we must have for each that either f = 0 or that dpp- = 0. By the induction hypothesis, fi = implies rı & x Furthermore dip means that
Ty & ri rp. When the jth component of ((F(),,) r,)) is O, we thus have that either rı & xx ( or
ry $ rı Tp for each 1, which implies ry & (1(1))
Another possibility is to use the component-wise product for pooling embeddings:
(x1 3 [x ② .... x1
xk)
Vo
where we write @ for the Hadamard product. Using the same argument as in the proof of Proposition we can show that the same result holds for this pooling operator. In practice, however, for numerical stability, we evaluate the as follows:
(x1 O
① xk) + z
Vo X1, XK) =
(14)
(x C
xk) + 1
where z = (e...., for some small constant > O. As long as is sufficiently small, this does not affect the ability of the GNN model to simulate the directional closure algorithm. In particular, in the GNN with yimi we can ensure that this coordinate is arbitrarily small in the
whenever et GNN with V0 o (choosing the aıj and ry vectors in the proof of Proposition 4. by selecting & small enough. In particular, there exists some 8 > 0 such that
X 2 (r, (rylettt > 2 x((+1)
E DISJUNCTIVE REASONING BENCHMARKS
We introduce two new benchmarks: one based on RCC-8 and one based in IA. Both benchmarks are similar to CLUTRR and Graphlog in their focus on assessing inductive relational reasoning via relation classification queries of the form (h, ?, where we need to predict which relation holds between a given head entity h and tail entity t. The available knowledge is provided as a set of facts F. which can again think of graph. The inductive part refers the fact that the model is trained and tested on distinct graphs. The main difficulty comes from the fact that only small graphs available for training, while some of the test graphs are considerably larger.
However, different from existing benchmarks, our benchmarks require reasoning about disjunctive rules, which is particularly challenging for many methods. The kind of knowledge that has to be
22

---

Published as a conference paper at ICLR 2025
EC
NTPP IPP
NTPP
NTPP
NTPP
1
3
9
11
EQ
NTPP EQ
NTPP
DC
2
10
12
TPP
EQ
IPPI
EQ
EQ
TPP
Figure 6: An example from the RCC-8 benchmark with b 6 paths from the source node 0 to the target node 17. Each path has a length of = 3 where & is the number of hops or edges from the node O to node 17. The graph has to be collapsed into the single relation ntpp(0, 17) using information from all the paths.
learned thus more expressive than the Horn rules which are considered most existing benchmarks. As illustrated in Example 2 this means that models need process different relational paths and aggregate the resulting information. We vary the difficulty of problem instances based on the number b of such paths and their length Frrurelpprovides an example where there are 6 paths length k 3. Each path is partially informative, in the sense that it allows to exclude certain candidate relations, but is not sufficiently informative pinpoint the exact relation. The model thus needs to rely on the different paths to be able to exclude all but one of the eight possible relations.
In summary, within the context benchmarks for systematic generalization, our RCC-8 and IA benchmarks are novel on two fronts compared to existing benchmarks such CLUTRR (Sinha et al. 2019) and Graphlog (Sinha al. 2020):
Going beyond Horn rules for relation composition: The composition of some RCC-8 relations is disjunction of several RCC-8 relations, and similar for IA.
2. Multi-path information aggregation: Models need to reason about multiple relational paths (for the case where >>>>>>>>> 1) to infer the correct answer.
3. Rich graph topologies: The graph generation process recursively expands an edge in the base graph with valid subgraphs and leads significantly diverse graph topolgies
E.1 RCC-8
Region Connection Calculus (RCC-8) (Randell et al. 1992) uses eight primitive relations to describe qualitative spatial relationships between regions: ntpp(a, a, b) means that is proper part of the interior of 6, tpp(a, b) means that a is a proper part of b and shares a boundary point with 6, po(a, b) means that a and are overlapping (but neither included in the other), dc(a, b) means that a and b are disjoint, ec(a, b) means that and b are adjacent (i.e. sharing a boundary point but no interior points), eq(a, (a, b) means that and are equal, and ntppi and tppi are the inverses of ntpp and tpp.
Example The RCC-8 calculus describes qualitative spatial relations between two regions using eight primitive relations. The semantics of the RCC-8 relations are governed by disjunctive rules such as:
po(X, Z) tpp(X, Z) intpp(X; X, Z) + ec(X, Y) nYpp(Y, Z) po(X, Z) V tppi(X,, Z) ntppi(X Z) tppi(X, Y) A po
(15)
(16)
23

---

Published as a conference paper at ICLR 2025
Table 5: RCC-8 composition table (Cui et al.
1993 (excluding eq).
dc
ec
po
tpp
ntpp
tppi
ntppi
dc
Rs
po.
de. ec. po. tpp. ntpp
po. tpp,
dc. po, tpp. ntpp
dc
tpp. ntpp
ec
de, ec, po. tppi. ntppi
dc, ec. po.
tpp. tppi.
dc. ec, po.
ntpp
ntpp
ec, po. tpp.
po. tpp. ntpp
dc, ec
dc
po
de, ec, po. tppi. ntppi
de. ec, po. tppi. ntppi
Rs
po. tpp.
po. tpp, ntpp
dc. ec. po. ntpi. ntppi
dc. ec. po. tppi, ntppi
de, ec, po.
dc. po. tpp. tppi, eq dc. ec. po.
dc. po.
tpp
tpp. ntpp
tpp, ntpp
ntpp
tppi, ntppi
de. ec, po.
ntpp
dc
de
tpp, ntpp
ntpp
ntpp
tpp. ntpp
Rg
tppi
de, ec, po. tppi. ntppi de, oc, po, tppi, ntppi
ec. po, tppl,
ntppi po. tppi,
ntppi pa. ntppi
po.
tppi.
tppi
po. eq. tpp.
pa, tpp. ntpp
tppi, ntppi
ntppi
ntppi
tppi.
po.
tppi.
po, tppi. tpp.
ntppi
ntppi
ntppi
ntppi
ntpp. ntppi, eq
as well as constraints encoding that the RCC-8 relations are disjoint. Let K. contain these rules and constraints, and let F = {ec(a, b), ntpp c), tppi(a, d). bo(d,))3: Then we have KUFF F po(a, c). Indeed, using (15) we can infer po(a, c) V tpp(a, c) V ntpp(a, c), while using (66) can infer po(a,c) c) V tppi a, c) V ntpppi(a, c). Using the disjoinmess constraints, we finally infer po(a, c).
The RCC-8 semantics is governed by the so-called composition table, which describes the composition mapping between two relations. This is shown in Table 5 where the trivial composition with the identity element eq being itself is dropped. Each entry in this table corresponds to a rule of the form (15), specifying the possible relations that may hold between two regions and c, when we know the RCC-8 relation that holds between a and some region as well as the relation that holds between b and c. For instance, the composition of and tppi is given by the set {dc, ec), which means that from {ec(a, 6), tppi(b, } we can infer dc(a, c) V ec(a, c). In the table, we write Rg to denote that any RCC-8 relation possible.
E.2 ALLEN INTERVAL ALGEBRA
We also introduce benchmark based on Allen's interval algebra (Allen 1983b) for qualitative temporal reasoning. The interval algebra (IA) uses 13 primitive relations to describe qualitative temporal relationships. IA captures all possible relationships between two time intervals, as follows: <(a,b) b) means that the time interval completely precedes the time interval b; d(a, b) means that occurs during while not sharing any boundary points; o(a, b) means that a overlaps with & m(a, b) means that meets b (i.e. ends exactly when b starts); s(a, b) means that starts b (i.e. b start at the same time while a finishes strictly before b); f(a, b) means that a finishes b (a and b finish at the same time, while b starts strictly before a); =(a, b) means that equals b; and finally >, di, oi, mi, si, fi are the inverses of the respective operations defined previously. The composition table for all the primitive interval relations is shown in Table 6 with the exception of the trivial composition of primitive elements with the identity element
and
E.3 DATASET GENERATION PROCESS
We now explain how the dataset was created. All sampling in the discussion below is uniform random. Each problem instance has to be constructed such that after aggregating the information provided by all the relational paths, we need to be able to infer a singleton label. In other words, problem instances need to be consistent (i.e. the information provided by different paths cannot be conflicting) and together all the paths need to be informative enough to uniquely determine which relation holds between the head and tail entity. This makes brute-force sampling of problem instances prohibitive. Instead, to create a problem instance involving b paths of length k we first sample base graph, which has shorter paths, with a length in (2, 3, 4). This is done by pre-computing relational compositions for large number of paths and then selecting b paths whose intersection is singleton. Then repeatedly increase the length of the paths by selecting an edge and replacing it by a short path whose composition is equal to the corresponding relation.
Finally, to add further diversity to the graph topology. for each of the paths, we allow edge from the base graph be replaced by subgraph (rather than path), where this subgraph is generated
24

---

Published as a conference paper at ICLR 2025
Table 6: Allen's interval algebra composition table (Allen 1983b) excluding the trivial composition with
5,
<,
5, O.
<, O,
m.
2, Ol,
2, Ol.
>. ol.
2, oi
mi,
<, o.
>. 01.
>, O0
o,
d.
mi.
mi,
d
5
oi,
9. o1.
d. f,
di
oi. di.
di,
oi. di.
di.
oi.
di
di
fi
Si.
si
si
fi,
ol. di, mi,
0,
ol.
o. d
m,
di,
si.
fi
0.
o.
>,
oi
di.
ol, d.
mi, di.
ol.
0. di.
ol.
d.
oi,
ol.
di.
>, oi, mi, si
f..
9,
d.
d,
mi
<,
di.
oi, d.
oi. d.
5.
si.
d.
f.
mi
mi
<,
oi.
mi
d
<
m.
si
m.
di,
ol,
di
oi
0,
di
mi
si
oi
di
mi, di,
d.
>.
>,
mi
mi
2. oi. mi,
di.
si.
f.
d
si
di
using the same procedure. Note that the final path count & then includes the paths from this subgraph as well.
The process is described in more detail below:
1. Sample short paths: Randomly sample = 100 000 paths of length & 3,, and compute their composition. Note that this sampling is done with replacement to avoid uniqueness upper bounds for small graphs.
2. Generate base graphs: Generate the desired number b-path base graphs, by selecting paths that were generated in step 1. Each individual path typically composes set of relations, but the graphs are constructed such that the intersection of these sets, across all paths, produces singleton target label.
3. Recursive edge expansion: Randomly pick an edge from a path that does not yet have the required length k. Select path from step which composes to a singleton, corresponding to the relation that is associated with the chosen edge. Replace the edge with this path.
4. Recursive subgraph expansion: Rather than replacing edge with path, we can also replace it with subgraph. As candidate subgraphs, we use the base graphs from step 2 with at most [ paths.
5. Keep repeating steps and until we have the desired number paths with the desired length of k, with the restriction that step 3 is applied most once each path from the initial base graph.
Some example graphs generated via this procedure for the RCC-8 dataset are displayed in Figure 7 For higher k;, there is greater diversity in the graph topology and complexity of the graph. To create
25

---

Published as a conference paper at ICLR 2025
dataset for reasoning about interval algebra problems, we follow the same process for the RCC-8 dataset. Example graphs generated via this procedure for IA are displayed in Figure g
2,6
(b) 2,6
(c) 2, =3
TPPI
EQ
VIPP
R0
EC
20
NTPP
TPP
20
bc
=
(e) 4,6
k0) 4
TPPLEQQ
TPP!
TPR
NIPE
2Q
TPP BP
TP
TPNRO
TPP
TPP
36
ge
DC Morner
80
THP
(g) 6
(h) k: 6,
Figure 7: Some graph instances for the RCC-8 dataset generated using the procedure described in E.3 The graph topology becomes more diverse for the test instances when sub-graphs within single path, as shown in (g) for path length & 6 and number of paths b = 1. In this particular case, there edges. Instances of the type shown in (a), (b), (c), (d), (e), (f) are used in the training set and the graph topology is fixed in this case. The target edge label between the source node and the tail node that needs to be predicted by the model is indicated by the dotted line.
embedded
sub-graphs that have been embedded in the graph by replacing two
26

---

Published as a conference paper at ICLR 2025
(a) k= 2,b =1
(b) 2,b
(c) 2,6 =
kd) 4
(e) 4,6=2
(g) k= 6,b=1
(h) 6,b
Figure 8: Graph instances for the interval dataset generated using the procedure described in E.3 highlight the rich variation in the topology of the graph instance for path length
We
and number of paths b = 3 in (h) by contrasting it with similar graph instance for the RCC-8 dataset shown Figure Ih). The target edge label between the source node and the tail node that needs to be predicted by the model is indicated by the dotted line.
E.4 ENSURING PATH CONSISTENCY WITHIN THE DATASET
We ensure that all relational paths in a problem instance in the generated dataset do not informationally conflict with each other by using the DPC+ algorithm (Long et al.) 2016). It efficiently computes directional path consistency, i.e. X,J C Xxx Vi, < k, for qualitative constraint networks that transform graph instances to. Note that this takes advantages of the fact that directional
27

---

Published as a conference paper at ICLR 2025
path consistency is sufficient as test for global path consistency for networks with singleton edge labels (Li et al. 2013).
F ADDITIONAL EXPERIMENTAL DETAILS
We now present further details of the experimental set-up, including details of the loss function that was used for training the model, the considered benchmarks and baselines, and training details such as hyperparameter optimisation.
F.1 LOss FUNCTION
We first consider the base setting, where single forward model is used. Let set of training instances of the form (Fi, hi, li r;) be given, where we write t; (fi,1).... fi,.) for the final-layer embedding of entity t; in the graph associated with Fr Let r = (ri,..., Tn) denote the
Forward model
embedding of relation We write:
CE(t,, = Σ ry tig
(17)
clearly want CE(t,, r2) ) to be low, while for each negative example r' E R \ {ri} we want CE(t,, r') to be high. We implement this with margin loss, where for each i we let 7. R (r.} be corresponding negative example:
Since r; represents the correct label for training instance
Σ
max(0, Ci) CE(t,, + +A)
(18)
where the margin A > is hyperparameter.
Full model In general, we use different models, each intuitively capturing different aspect of the relations. Furthermore, instead of the tail node embedding ti we use the prediction obtained by the forward-backwart model, computed in (5). Let write Xy denote the prediction that is obtained by the j model for training example i, and let rij denote the embedding of relation in the jth model. We write r'y to denote some negative example, i.e. rij Tpj for some rp E R \ {ri). The overall loss function becomes:
L
Σ max (0,
CE(Xij, ru) CE(Xi), r'1)) + A)
(19)
Ø=1
F.2 INFERENCE
Relation classification For the relation classification datasets, where we need to answer queries of type (h, ?, (), at test time, we predict the target relation for which the cross-entropy with the predicted embedding is minimal. More precisely, let us write Xj for the embedding predicted by the jth model, computed as in 45). Let be the embedding of relation r in the jth model. We predict the relation defined as follows
f = arg max PER
Σ CE(
(20)
Link prediction For link prediction datasets, where we need to answer queries of type (h, r, ?), the forward-only model, the knowledge graph. This is possible with one pass of the forward model, whereas with the full (forward-backwanl model we would have to do one pass for each candidate entity. Let tj be the final-layer embedding of entity / in the jth model. Let us again write rj for the embedding of relation r in the jth model. The score of entity 1. is then given by:
need to efficiently compute score for all the entities in
score (t)
CE(t, rj)
(21)
J=1
Finally, to answer the link prediction query, we rank the set of all candidate entities based on this score.
28

---

Published as a conference paper at ICLR 2025
Table Data statistics for different versions of the CLUTRR dataset, with varying training regimes and different numbers training and testing graphs.
Training regime
Unique Hash
No. of relations
# Train
# Test
Test regime
(2.3)
089937E6
22
10,094
900
{4,
10
1 E (2,3)
data_9b2 17 f
22
35,394
39825
k 14.
10
(2,3, 4)
data_db9699004
15,083
823
(5, ....... 10)
Table 8: Data statistics of the Spatio-temporal reasoning datasets
Dataset
Training regime
No. of relations
Train
Test
Test regime
RCC-8
b (1,2,3, k E (2.3) b (1,2,3,, (2,3)
57,600
153,600
6 (1,2,3) f2..... 9}
(1,2,3), (2....,
F.3 BENCHMARKS
CLUTRR (Sinha et al. 2019) is dataset which involves reasoning about family relationships. The original version of the dataset involved narratives describing the fact graph in natural language. It was, among others, aimed at testing the ability of language models such BERT (Devlin al. (019) to solve such reasoning tasks. However, the original paper also considered number of baselines which were given access to the fact graph itself, especially GNNs and sequence classification models. A crucial finding was that such models fail to learn to reason in systematic way: models trained on short inference chains perform poorly when tested on examples involving longer inference chains. This has inspired a line of work which has introduced number of neuro-symbolic methods for addressing this issue. The CLUTRR dataset was released under a CC-BY-NC 4.0 license.
Graphlog (Sinha et al. 2020) involves examples for 57 different worlds, where each world is characterised by a set of logical rules. For each world, a number of corresponding knowledge graphs learn the underlying rules. The model is then tested on
provided, which the model can previously unseen knowledge graphs for the same world. The aim of this benchmark is to test the ability of models systematically generalise from the reasoning patterns that have been observed during training, i.e. to apply the rules that have been learned from the training data in novel ways. This dataset released under CC-BY-NC 4.0 license.
RCC-8 and IA are the benchmarks that we introduce in this paper, as described in Section We release these benchmarks under CC-BY 4.0 license.
Inductive Knowledge Graph Completion Teru et al. 2020) is focused on link prediction queries of the form (h, rr ?) which are evaluated against given knowledge graph. Different from the more commonly used transductive setting, in the case of inductive knowledge graph completion, the training and test knowledge graphs are disjoint. Teru al. (2020) proposed number of benchmarks for this inductive setting by sampling disjoint training and test graphs from standard knowledge graph completion datasets. In this way, they obtained four different benchmarks from FB15k 15k-237 and four benchmarks from WN18RR.
Dataset statistics for CLUTRR, Graphlog, RCC-8 and IA, and the Inductive KGC benchmarks are I0
reported in tables 7
We use a standard 80-20 split for training and validation for CLUTRR and RCC-8. For Graphlog, we use the validation set that is provided separately from the test set.
9
8
F,4 BASELINES
We compare method against the following neuro-symbolic methods:
CTP Conditional Theorem Provers (Minervini et al.) 2020b) are a more efficient version Neural
Theorem Provers (NTPs (Rocktäschel Riedel 2017)). Like NTPs, they learn a differ-
sttas//gitthbb.co///tte////gg/
29

---

Published as a conference paper at ICLR 2025
Table 9;
Data statistics for the 'hard' Graphlog worlds, showing for each world the number of classes (NC), the number of distinct resolution sequences (ND), the average resolution length (ARL), the average number of nodes (AN), the average number of edges (AE), and the number of training and testing graphs.
World ID
NC
ND
ARL
AN
AE
# TTrain
#lestt
World 7
17
288
4.47
13.2
16.3
5000
1000
16.0
19.1
5000
1000
World 11 17
194
4.29
11.5
13.0
5000
1000
World 32
16
287
4.66
16.3
20.9
5000
1000
Table 10: Dataset statistics for inductive knowledge graph completion. Queries and facts are (h, t) triplets and are used labels and inputs respectively. The goal is predict the query targets t once trained on fact triplets. Note that for the training sets, queries are treated as facts i.e. training data.
Train #Qucry
Validation #Qucry
Test #Qucry
Dataset
#Relation
#Entity
#Fact
#Eatity
#Fact
#Entity
#Fact
v1
180
1594
4245
4245
1594
489
4245
1093
205
1993
PB15k-237
v2
200
2608
9739
9739
2608
1166
9739
1660
478
4145
v3
215
3668
17986
17986
3668
2194
17986
2501
865
7406
v-4
219
4707
27203
27203
4707
3352
27203
3051
1424
11714
v1
2746
5410
5410
2746
630
5410
922
188
1618
WNISRR
Y2
10
6954
15262
15262
6954
1838
15262
2757
441
4011
v3
12078
25901
25901
12078
3097
25901
5084
605
6327
144
3861
79400
7940
3861
934
7940
7084
1429
12334
entiable logic program, but rather than exhaustively considering all derivations, at each step of proof, CTPs learn a filter function that selects the most promising rules to apply, thereby speeding up Dackwards-chaining procedure of NTP. Three variants of this model were proposed, which differ in how this selection step is done, i.e. using linear mapping (CTPL), using an attention mechanism (CTPx), and using method inspired by key-value memory networks (Miller al.] 20166 (CTPM). We were not able to reproduce the results from the original paper, hence we report the results from (Minervini et al., 2020b) for the CLUTRR benchmark.
GNTP Greedy NTPs (Minervini et al. 2020a) are another approximation of NTPs, which select the top-k best matches during each inference step.
RS This model (Lu et al. 2022) learns symbolic rules of the form r(X, 2) (X, A r2 Z). with the possibility of using invented predicates in the head. To make prediction, the method then samples (or enumerates) simple paths between the head and tail entities and iteratively applics the learned rules to reduce these paths to a single relation. The order in which relations composed is determined by Monte Carlo Tree Search.
NCRL
Neural Compositional Rule Learning (Cheng et al. 2023) also samples relational paths between the head and tail entities, and iteratively reduces them by composing relations at a time, similar to R5. However, in this case, the choice of the two relations to compose in each step are determined by a Recurrent Neural Network. Moreover, rather than learning symbolic rules, the rules are learned implicitly by using attention mechanism to compose relations. Both R5 and NCRL implicitly make the assumption that the relational reasoning problem is about predicting the target relation from single relational path, and that this prediction can be done by repeatedly applying Horn rules.
The following transformer Vaswani et al. 2017) variant is also natural baseline:
ET Edge Transformers (Bergen et al. 1021 modify the transformer architecture by using an attention
mechanism that is designed simulate relational composition. In particular, the embeddings are interpreted as representations of edges a graph. To update the representation of an edge (a, c) the model selects pairs of edges (a, (a, (x, b) and composes their embeddings. These compositions are aggregated using an attention mechanism, similar as in the standard transformer architecture.
30

---

Published as a conference paper at ICLR 2025
We also compare against several GNN models:
GCN
Graph Convolutional Networks (Kipf & Welling 2017) are standard graph neural network architecture, which use sum pooling and rely on a linear layer followed by a non non-linearity such as ReI.U or sigmoid to compute messages. While standard GCNs do not take into account edge types, for the experiments we concatenate edge types to node embeddings during message passing, following (Sinha et 2019). GCNs learn node embeddings and can thus not directly be used for relation classification. To make the final prediction, we combine the final-layer embeddings of the head and tail entities with encoding of the target relation, and make the final prediction using a softmax classification layer.
R-GCN Relational GCNs (Schlichtkrull et al. 2018 are a variant GCNs which messages are computed using relation-specifee linear transformation. This is similar in spirit to how we compute messages in our framework, but without the inductive bias that comes from treating embeddings probability distributions over primitive relation types.
GAT Graph Attention Networks (Velickovic al. 2018) are variant of GCNs, which use pooling mechanism based on attention. Similar as for GCNs, we concatenate the edge types to node embeddings to take into account the edge types.
E-GAT Edge-based Graph Attention Networks (Sinha et al. 2020) are a variant of GATs which take edge types into account. In particular, an LSTM module is used to combine the embedding of neighboring node with embedding of the edge type. The resulting vectors are then aggregated as in the GAT architecture.
NBFNet Neural Bellman-Food Networks (Zhu et al. 2021) model the relationship between desig- nated head entity and the other entities from given graph. Our model employs essentially the same strategy to use GNNs for relation classification, which is to learn entity embeddings that capture the relationship with the head entity rather than the entities themselves. The main difference between NBet and our model comes from the additional inductive bias that our model is adding.
In (Minervini et al. 2020b), number of sequence classifiers were also used as baselines, and we also report these results. These methods sample path between the head and the tail, encode the path using recurrent neural network, and then make prediction with softmax classification layer. We report results for three types architectures: vanilla RNNs, LSTMs (Hochreiter Schmidhuber 1997) and GRUs (Cho al. 2014).
F,5 TRAINING DETAILS
F.5.1 INITIALIZATION AND COMPUTE
The relation vectors and the vectors aij defining the composition function uniformly initialized. All baseline results that were obtained by us were hyperparameter-tunee using grid search, as detailed below. Some baseline results were obtained from their corresponding papers and reported verbatim (as indicated in the results tables). All experiments were conducted using RTX 4090 and V100 NVIDIA GPUs. single experiment using the GNN based methods in the paper can be conducted within 30 minutes to an hour on single GPU. This includes training and testing a single model on any benchmark of the following relation prediction benchmarks: CLUTRR, Graphlog, RCC-8, IA (also see Figure 16 for train/test times on the spatiotemporal datasets). A single hyperparameter set evaluation would take the same time as an individual experiment. For the inductive knowledge graph completion setting, training and inference times for a single run are reported in Figure [5]
F.5.2 HYPERPARAMETER SETTINGS
We use the Adam optimizer (Kingma & Ba 2017). The number of layers of the EpiGNN model is fixed to and the number of negative examples per instance fixed as 1. The other hyperparameters of the EpiGNN model are tuned using grid search. The optimal values that were obtained are mentioned in Table II For inductive knowledge graph completion, the classification task requires predicting tail entities we cannot backward flow in model. The optimal hyperparameters for the forward only version of the EpiGNN for this setting are summarized in Table [2] For this 6 message passing rounds similarly with NBFNet /hhu et al. (2021) setting,
31

---

Published as a conference paper at ICLR 2025
Table 11: Optimal hyperparameters of the full (forward-backward) model all benchmarks.
Batch size
Embeddiing
Learning rate
dim
Epochs
Facets
Margin
CLUTRR
128
64
100
0.01
1.0
Graphlog
RCC-8
128
32
40
0.01
1.0
128
40
0.01
1.0
Table 12: Optimal hyperparameters of the forward only EpiGNN model on inductive knowledge graph completion benchmarks.
Batch size
Embedding
Learning rate
Epochs
Facets
Margin
FB15K-237 vl
64
64
15
16
0.01
0.2
64
FB15K 237 v3
64
64
15
16
0.01
0.1
75-35-237
WNISRR v1
64
16
15
0.01
0.5
WNISRR v2
64
15
0.01
0.4
WNISRR v3
64
64
15
0.01
1.1
WNISRR v-
64
16
13
0,01
0.7
We conduct the following hyperparameter sweeps: learning rate in {0.00001, 0.001, 0.1), batch size in {16, 32, 64, 128}, number of facets in {1, 2, 4, 8, 16, 32} and embedding dimen- sion size in {8, 16, 32, 64, 128, 256). We also tune the margin A in the loss function over 1.0, 0.9, .........1.... 0.1. 0.013. All model parameters are shared across the different message passing layers of our model.
The choice of the pooling operator has an important impact on the systematic generalization abilities of the model. our experiments, we found that the pooling operator has to be specified as part the inductive bias and cannot be learned from the training or validation data, which is in accordance with findings from the literature on systematic generalization (Xu et al. 2021 Bahdanau et al.) 2019).
G ADDITIONAL ANALYSIS
G.1 ADDITIONAL CLUTRR RESULTS
In the main paper, we presented the results for the standard CLUTRR benchmark, where problems of size & E 3, 3, 4} are used for training. In the literature, models sometimes also evaluated on an even harder setting, where only problems of size k E {2,3} are available for training. We be seen, model clearly outperforms both
show the results for this setting in Table 13 As Edge Transformers (ET) and the GNN and RNN baselines. In this more challenging setting, the difference performance between our model and ET is much more pronounced. However, R5, as the best-performing neuro-symbolic method, consistently outperforms our method in this case. We hypothesise that this is largely due the inevitably small size of the training set (as the number of distinct paths of length 3 is necessarily limited). Rule learners can still perform well in such cases, which is something that R5 is able exploit. To achieve similar results with our model, stronger inductive bias would have to be imposed. One possibility would be to impose sparsity prior on the relation embeddings and the vectors a;y defining the composition function. We leave detailed investigation of this possibility for future work.
In the literature, two different variants of the dataset have been used: db db_ 9b2113cfccff and aaaa_08990755
In Table [3 we the CLUTRR dataset sbb_bb2173cs which was in- troduced in the ET paper (Bergen et al. 202T), to evaluate our model as well as the baselines that evaluated by us. The reported baseline results that were obtained from (Minervini et al.) (020bb) and (Lu et al. 2022) are based on the smaller a 089907 7 78 variant, and are thus not directly comparable.
32

---

Published as a conference paper at ICLR 2025
Table 13: Results on CLUTRR (accuracy) after training on problems with k {2,3} and then evaluating problems with & E (4..... 10). The best performance for each k is highlighted in bold. Results marked with were taken from (Minervini al. 2020b) and those with t from (Lu
et al., 2022). The results from (Minervini et al. (020b) and (Lu et al. 2022) were evaluated on different variant of the dataset and may thus not be directly comparable.
4 Hops
Hops
Hops
7 Hops
Hops
9 Hops
10 Hops
EpiGNN-mull (ours)
0.96+.02
0.96= 03
0,94 05
0.92+.07
0.90 10
0.88
0.85#
EpiGiNN-minn (ours)
0.96
0.95=.05
0.91#:08
0.872.11
0.82
0.79
0.74
0.981.02
0,99=.02
0.98:.003
0.96:1.05
0,971.01
0,981.03
0.97:1.03
CTP2
0.98+.02
0,98= 03
0
0.96 .4
05
0.89#.07 07
0.89+.07
CIP
0,99:.02
0.99=.01
0,9911022
0.962..0
0.94
0.894.00 00
0.90:1:07
CTP Af
0.97.1.03
0.97:1.05
0.96.1.06
0.95.1.06
0,93 1.05
0.90.1.06
0.89.1.06
GNTP"
0.4911.18
0.45
0.38
0.372.21
0.32
0.31
0.31
ET
0.90+t04
0.84 02
0.78
0.69#.08
0.63#.05
0.58# 06
0.55+.08
GAT
0.91-1.2
0.76 06
0,54.1.03
0.5611.4
0.54
0.55.105
0.45:1.06
GCN"
0.842.03
0.68 02
0,53d: 03
0.47+
0.424:03
0.45
0.39:t.02
NBENK
0.53+.08
0.39
0.37+.06
0,34
0.32#.05
0.31#:055
R-GCN
0.80+2.99
0.63= 08
0.52 11
0.46
0.41
0.39#.06
0.38
RNN
0.86.1.06
0.76.1.08 00
0.67-1.08
0.66.1.08
0.
0.55.1.00
0.48.1.07
LSTM"
0.981.04
0.95 03
0.88 05
0.87.:04
0.81
0.75
0.75#
GRU
0.89+.05
0.83=
0.74::112
0.72:
0.67
0.62#.10
0.60
G.2 EXTENDED ABLATION ANALYSIS
In the main paper, we considered four separate ablations. Table 14 results for all combinations of these ablations. Facet ablation refers to the configurations where probability ablation refers to the configuration where embeddings are unconstrained, composition ablation refers to the configuration where distmult in combination with MLP is used the composition function d and backward ablation refers to the configuration where we only have the forward model. We can clearly see that the probability and composition function ablation cause ablation.
extends this analysis by showing
significantly stronger performance degradation compared to the facet and
Table 14: Results for all combinations of the individual ablations from Table
Probability Ablation
Composition Ablation
Backward Ablation
CLUTRR
CLUTRR
RCC-8
Ablation
Avg
10
Avg
3, 9
True
True
True
True
0.06
0.04
0.12
0.12
True
Truc
True
False
0.10
0.15
0.12
0.12
Truc
True
False
False
0.20
0.16
0.25
0.14
True
False
True
True
0.06
0.04
0.12
0.12
True
False
True
False
0.11
0.20
0.12
0.12
True
False
False
True
0.92
0.73
0.81
0.49
True
False
False
False
0.94
0.68
False
True
True
Thue
0.06
0.04
0.22
0.18
True
False
True
False
Thue
0.29
0.25
0.60
0.27
False
True
False
False
0.36
0.30
0.38
0.21
False
False
True
Thue
0.08
0.12
False
False
True
False
0.29
0.31
0.12
0.12
False
False
False
0.94
0.51
False
False
False
False
0.99
0.99
0.96
0.80
G.3 LEARNED SPARSENESS OF RELATION VECTORS
We visualize the learned relation vectors for each benchmark studied in this paper in Figures 10 12 It can be seen that the vectors mostly one-hot. despite the fact that no explicit sparsity constraints were used in the model. Also, we note that different facets are capturing different parts of relation and there is shared structure between different relations if the semantic meaning is similar
33

---

Published as a conference paper at ICLR 2025
e.g. contrast the vector for grandfather and grandmother husband and wife in Figure 11 and similarly, the vectors for si, s share structure each being the other's inverse in Figure 10
Note that for the relation prediction task, there are entities each node but rather intermediate compositions of relations.
RCC8 learned relation vectors
0.8
DC
0.6
TPP
0.2
EQ
Figure 9: Schematic visualisation of the learned relation vectors with 4 facets with hidden dimension of 8 for the RCC-8 benchmark. Notice that the eq relation learned to one-hot at the first index for every facet as it corresponds to the identiy composition in Eq. (4)
Interval Algebra learned relation vectors
0.8
Figure 10: Schematic visualisation of the learned relation vectors for the Interval Algebra benchmark with facets, each with a hidden dimension of 8. Again, the learned identity relation representation corresponds the identity composition.
34

---

Published as a conference paper at ICLR 2025
cuu mi ismmed reletion vectors
unde
Intherin--ow-
gr grandcaughter
caughter
sister
matherin-luw
son-in-law
grandson
mether
wife
brother
nephew
grandmether
granefather
nicce
hustand
coughterin-tow
father
Figure 11: Schematic visualisation of the learned relation vectors for the CLUTRR benchmark.
G.4 EFFECT OF THE NUMBER OF MESSAGE PASSING ROUNDS
We study the effect of varying the number of message passing rounds on the accuracy for varying values of k and b 3, for the EpiGNN-min and EpiGNN-mul models the RCC-8 and IA datasets. These models are trained ab initio with the same training data and configuration as before but with a different number of message passing rounds (from 5 15) for each instance. The results are displayed in Figure 13] There are three pertinent observations that can be made. Firstly, the maximum attained k-hop accuracy decreases with k. which makes sense as it confirms that the problem complexity increases with k. Secondly, there is a jump in the k-hop accuracy when the number of message passing rounds matches & after which the accuracy saturates. This rightly suggests that the number of message passing rounds should at least be equal to the final k-hop in the dataset to ensure that all information propagates from head entity to tail within the model. Thirdly, these observations are shared across the dataset types and aggregation functions.
G.5 ADDITIONAL ANALYSIS OF PARAMETER AND TIME COMPLEXITY
Knowledge graph completion The empirical parameter complexity of the EpiGNN on all splits (Teru et al., 2020) of the inductive knowledge graph completion benchmarks for FB 15k- 237 (Toutanova & Chen 2015) and WNISRR (Dettmers et al. 2018b) is shown in Figure 14 The parameter estimates of the best performing GNN baselines in Table namely NBFNet (Zhu et al.) 202T) and REST (Liu et al. 2023) are also shown. It can be observed that the EpiGNN is the most parameter efficient model out of all by at least on order of magnitude complexity with respect to NBFNet is shown in Figure [5 where the EpiGNN is slightly slower than NBFNet on FB 15k-237 for both training and inference but faster for both in WN18RR
all the splits. The time
35

---

Published as a conference paper at ICLR 2025
Craphtog World 5z heamed relstion vectors
R.9_
R.7_
R
R
R.4.-
R
RUB.
R.5.
R.7.
R
Figure 12: Schematic visualisation of the learned relation vectors for the Graphlog benchmark.
Spatio-temporal reasoning The training and inference times of the EpiGNN with respect to the edge transformers (Bergen al. 2021) (cf. the best baseline Figure are shown in Figure 16
G.6 RESULTS ON THE EXPANDED VERSIONS RCC-8 AND INTERVAL ÁLGEBRA DATASETS
The RCC-8 and Inverval algebra datasets presented in the main can be made more challenging by increasing the number of paths b and the maximum number of inference hops k. In this section, we provide results for the expanded RCC-8 and IA datasets for the EpiGNN and Edge Transformers (being the best baseline in Figure 4).
The Edge transformer not able to fit graphs in memory on an RTX 4090 GPU with 9 and b 2 6 so we need to restrict the comparison in Figure The EpiGNN is able to handle much larger graphs since is more compute and parameter efficient so we provide the results for up to A = 15 and 6 8 in Figure 18 Note that our model holds its performance fairly steady on this significantly expanded dataset with an average accuracy of 0.74 on RCC-8 and 0.77 on the IA dataset for the hardest setting: I 15 and b 8. Edge Transformers significantly deteriorate on LA and only achieve an average accuracy of 0.19 at = 9, = On RCC-8, the Edge transformer has an average accuracy of 0.7 for 9, 6 versus 0.85 for our model.
36

---

Published as a conference paper at ICLR 2025
Accuracy
Accuracy k- b-3
Accuracy k-9, b-3
Accuracy k=6, b=3
Accuracy k=8, b=3
Interval Algebra, EpiGNN-min
Interval Algebra, EpiGNN-mul
1.0
1.0
0.9
0.9
0.8
Accuracy
0.7
0.7
0.5
0.5
0.4
0.3
0.3
5
6
9
10
11
12
13
14
15
6
7
8
10
11
12
13
14
15
RCC-8, EpiGNN-min
RCC-8, EpiGNN-mul
1.0
0.9
0.9
0.8
Accuracy
0.7
0.7
0.5
0.5
0.4
0.3
0.3
5
6
10 11 12
13
14
15
5
6
7
8
10
11
12
13 14
15
Message passing rounds
# Message passing rounds
Figure 13: Effect of the number of message passing rounds the k-hop accuracy for the EpiGNN model on the IA and RCC-8 datasets. There a sharp jump in performance when k equals the number of message passing rounds.
NBFNet
REST
EpiGNN
# Parameters (mhill (m)llioos)
100
10
10
10
v1
V2
v3
V4
v1
V2
V3
V4
FB15K-233
WN18RR
Figure 14: Parameter complexity on all the inductive versions of FB15k-237 and WN18RR.
37

---

Published as a conference paper at ICLR 2025
Train (NBFNet)
Infer (NBFNet) Infer (EpiGNN)
Train (EpiGNN)
10
10a
Time (s)
10
10
10
V2
v3
v4
v1
v2
v3
V4
FB15K-237
WN18RR
Figure 15: Time complexity of the EpiGNN against the NBFNet on all the inductive versions of FB 5k-237 and WNISRR. Results are obtained on single Nvidia RTX 4090 GPU.
Infer
Train (EpiGNN)
Infer (EpiGNN)
1200
1000
800
Time (M)
200
RCC-8
Interval Algebra (IA)
Figure 16: Time complexity of the EpiGNN against the best baseline spatio-temporal systematic reasoning. Results are obtained on single Nvidia RTX 4090 GPU.
Edge Transformers
EpiGNNi-min RCC. 8 bb=
ACC-8 b=1
RCC 8 b
RCC 8
RCC 5
RCC. 8
1.0
1.0
1.0
10-
1.0
1.0
0.9
0.9
0.9
0.5
0.7
0.5
0.6
0.6
0.6
0.5
0.6
0.5
0.3
0.3
0.3
0.2
0.2
0.2
0.00
3
2
3 4
2
3 4
4 8
Interval Algebra b= Interval Algebra b 2Interval Algebra b 3interval Algebra b 4 Interval Algebra b 5interval Algebra
1.0
1.0
1.0
1.0
1.0
1.0
0.9
0.9
0.5
0.7
0.5
0.6
0.6
0.6
0.6
0.6
0.3
0.3
0.3
0.2
0.2
4
k-hops
Figure 17: Performance of EpiGNN-min and Edge Transformers on the expanded version of the RCC-8 and Interval Algebra datasets. The performance of Edge Transformers deteriorates as the number of paths increased compared to EpiGNNs and this effect can be more significantly observed on the Interval Algebra dataset. We restrict the comparison to 6 < 6, k < 9 since Edge transformers cannot fit graphs for the other settings in memory on an RTX 4090 GPU.
38

---

Published as a conference paper at ICLR 2025
EpiGNN-min
RCC-8 b = 1
Interval Algebra b = =1
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.5
0.5
2
3
4
7
8
9
10
11
12
13
14
15
3
4
8
9
10
11
12
13
14
15
RCC-8 b
2
Interval Algebra b =
1.0
1.0
0.8
0.8
0.7
0.7
0.6
0.6
3
8
12 13
3
8
12
13
RCC-8 b
Interval Algebra
1.0
1.0
0.9
0.9
0.7
0.7
0.6
0.6
0.5
0.5
8
12 13
12
13
14
RCC-8 b
Interval Algebra
1.0
1.0
0.9
0.9
0.8
0.8
0.6
0.6
Accuracy
0.5
0.5
2
3
4
7
8
9
10
11
12
13
14
15
3
4
7
8
9
10
11
12
13
14
15
RCC-8 b
Interval Algebra b
=5
1.0
1.0
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.5
0.5
2
3
7
8
9
10
11
12
13
14
3
8 9
10
11
12
13
14
RCC-8 8 b
=
6
Interval Algebra b =
6
1.0
1.0
0.9
0.9
0.7
0.7
0.6
0.6
0.5
0.5
RCC-8 b
Interval Algebra
1.0
1.0
0.9
0.9
0.8
0.8
0.6
0.6
0.5
0.5
2
3
4
7
8
9
10
11
12
13
14
15
3
4
8
9
10
11
12
13
14
15
RCC-8 b
8
Interval Algebra b
8
1.0
1.0
0.9
0.9
0.8
0.8
0.7
0.7
0.5
0.5
2
3
4
7
8
9
10
11
12
13
14
15
3
4
7
8
9 10
11
12
13
14
15
k-hops
Figure 18: Performance of EpiGNN-min on the complete expanded version of the RCC-8 and Interval Algebra datasets with maximum values scalable and is fairly steady for the hardest setting: 8, k 15 highlighting its inductive bias for systematic generalization.
8, k: 15. The model's performance
39


Reviews:
[{"review_id": "LoWzQ4bLmX", "reviewer": "Reviewer_X3MA", "summary": "This work presents a representation-based method for predicting relationships between entities within a knowledge graph. The approach leverages Graph Neural Networks (GNNs) and incorporates epistemic states as node representations. The proposed method is benchmarked against various rule-based and graph-based approaches, demonstrating superior performance.", "questions": "See above weakness", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The method introduced here demonstrates significantly higher efficiency compared to other baselines, as clearly illustrated in Figure 5.\n2. The proposed method is compared against various baselines, including both rule-based and graph-based approaches, and consistently shows superior performance.\n3. New synthetic datasets are provided in this work.", "weaknesses": "1. In my opinion, representing each node/entity as a distribution over relations is unconventional. Despite its parameter efficiency and superior performance, this embedding/representation method has notable drawbacks: (1) The learned embeddings are non-transferable across datasets, as different datasets may have varying numbers of relations. (2) It completely ignores the semantic information of entities, making the semantic interpretation of these representations difficult.\n2. The notations in Section 3 are somewhat challenging to follow. For instance, what does 𝑓 represent in Eq. 4 and the equation preceding it? Additionally, why is 𝑓 not illustrated in Figure 3? Furthermore, in Eq. 4, how is a_ij ​ defined? Providing an example of this variable or illustrating it within the message passing subplot in Figure 3 could enhance interpretability.\n3. I am not an expert in this field, but I wonder if this method can be applied to entity prediction. From my perspective, entity prediction is more interesting and challenging in knowledge graphs (KG) and temporal knowledge graphs (tKG) [1, 2]. It seems that relation prediction is relatively simpler, as the number of potential relations to predict is usually limited to a few hundred. Can the method proposed in this work be generalized to entity prediction, or is it restricted to relation prediction?\n\n[1] Anytime Bottom-Up Rule Learning for Knowledge Graph Completion\n[2] TLogic: Temporal Logical Rules for Explainable Link Forecasting on Temporal Knowledge Graphs", "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": "", "extra_scores": {}}, {"review_id": "w5StwyFSmB", "reviewer": "Reviewer_C39j", "summary": "This paper focuses on a challenge on current knowledge graph inference study that learned model fails to generalize to test cases with longer logical inference path. This paper modifies the state-of-the-art NBFNet design, and proposes EpiGNN, a scalable model which is proved to be same expressive as multi-path disjunctive reasoning that is enough to solve the relation inference of any length. They proposes two benchmarks CLUTRR and GraphLog to evaluate longer relational path inference, and empirically showcase that their method can achieve same good performance as state-of-the-art methods but with better efficiency. They also empirically shows that their model can achieve close-to-best performance on real-world benchmarks where longer logic inference may not be necessary.", "questions": "1. line 113: Shouldn't $\\mathcal{K} \\circ \\mathcal{F}$ (applies on) better than $\\mathcal{K} \\cup \\mathcal{F}$ (union). Since $\\mathcal{K}$ are rule set like $r_1 \\wedge r_2 = r_3$ while $\\mathcal{F}$ are facts like $r_1(a, b), r_1(b, c), r_2(c, d)$?\n2. Equation 3: Based on your reasoning, this initialization hints the probability of some primitive relations. Then, it seems that the first one is if or not it is the anchor node (zero-one init as NBFNet). If that undertstanding is correct, shouldn't the second be $(0, 1/(n-1), \\dots)$?\n3. line 236: This equation is slightly different from tradition GNN update rule in the sense that node embedding itself is considered as a message (self-loop edge), and update function is removed, any hint behind doing that?\n4. line 244: It will be better to use $\\mathbf{A}$ instread of $\\emph{\\mathbf{a}}$ since it is a 3D tensor rather than a vector.\n5. line 269: Is the relation being pairwise disjoint is the assumption only on your dataset? I don't think this is true for most real-world knowledge graphs.\n6. line 275-280: If we add multi facet only at loss function, we are training them independently, shouldn't be better to add a pooling at final output of each layer, just as multi-head attention?\n7. Equation 6: You are only merging bidirections on both ends, but won't it be possible that we have to merge relations in the middle first? If so, shouldn't we merge at the output of every layer?\n8. An overall concern: Your design eventually is the same as message passing on query anchored graph (except the final bidrection aggregation), which is proposed in NBFNet (except initialization and message passing function). My question is which unique design makes it more capable than NBFNet, thus can solve problem it can not handle?\n9. Table 1: Why NBFNet is worse than GCN, GAT and RGCN in many cases? Does that mean that NBFNet is extremely poor in true logic reasoning? One more thing, it seems that you are only picking samples that relations must exist which is slightly different from NBFNet purpose for link prediction. Can you also add unrelated samples in the test? Indeed, in Table 3 where such negative samples exist, your method is not performing such better, thus this may mean your method fails to handle unrelated node pairs which I believe could be a big risk in real-world applications.\n10. Table 1 and 2: It is claimed before than NCRL and R5, as single-path method, is not capable to solve the studying problem (line 183), however, they are mostly the best on two proposed benchmarks, doesn't that means your benchmarks are not the best fit for evaluation? Shouldn't you additionally propose a synthetic benchmark, that truly justify your method can handle multi-path reasoning? \n11. Based on overall experiment result, the advantage of your proposal is more efficient in longer relation path generation, thus can you provide the real runtime (training and inference) comparison with NCRL and R5 (which achieves best performance on same scenarios).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- This paper focuses on longer logic inference with requirement of multi-path disjunctive reasoning, which are critical problems in knowledge graph.\n- This paper's solution is based on scalable framework, making it useful in giant knowledge graphs in real world.\n- This paper has prove of expressivity in the sense of logical reasoning, promising its power to handle focusing problems.", "weaknesses": "- Some design details have potentially alternatives, but is lack of reasoning, leaving concerns that if the implementation is the best design under proposed framework.\n- The empirical evidence is not strong enough to showcase their claims:\n   - The studying problem is claimed to be unsolvable for existing methods, while baselines can achieve the best performance.\n   - The method is claimed to be more scalable than related baselines, however, there is runtime or memory cost comparison in main content.\n   - In real-world benchmarks, their method is not such close to state-of-the-art as they claimed. I think adding confidence interval will better defend their point here.\n- Their design does not significantly differ from related work NBFNet, but is lack of theoretical justification why their method can be more powerful than this related work.", "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": "", "extra_scores": {}}, {"review_id": "j8dZtSUiT4", "reviewer": "Reviewer_JqVR", "summary": "This paper aims to solve systematic generalization in relational reasoning problems. Existing GNNs lack the ability to generalize systematically, while existing neuro-symbolic methods can generalize but tend to make strong assumptions. The authors propose Epistemic GNNs (EpiGNNs), which not only solves systematic generalization but is also scalable and parameter efficient. Technically, EpiGNNs modify the NBFNet architecture to represent representations between entities as distributions over primitive relationships. The messages are then defined as learnable weighted compositions of these primitive relations. Besides, the authors also propose a few tricks to augment EpiGNNs, including jointly training several models and two forward & backward models. The authors introduce two new datasets for benchmarking the ability of handling disjunctive relational paths. Empirically, EpiGNNs surpass all methods on the two new datasets. EpiGNNs also achieve competitive performance against existing methods on systematic generalization and inductive knowledge graph completion datasets.", "questions": "- Line 50 & 53: It is more precise to say neural theorem provers rather than neuro-symbolic methods. Neuro-symbolic methods are a very broad family, and not all of them focus on modeling single relational paths.\n- Proposition 1: I guess there exist scenarios where the count of a certain relational path matters, right? Maybe you can take this into consideration.\n- Line 154-155: This statement is not true for representation learning methods like NBFNet and EpiGNNs. If the reduction of relations follows the associative property (i.e. $(a\\times b)\\times c=a\\times (b\\times c)$), representation learning methods can deal with intermediate relations that are not present in the training data.\n- Can you include a few references for epistemic states if this concept is not invented by this paper?\n- Line 269-271: The pairwise disjoint assumption only holds for CLUTRR and Graphlog. It doesn’t hold for knowledge graph datasets in general.\n- Typo: Line 100: single-path base → single-path-based", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- This paper introduce two new datasets for benchmarking systematic generalization. The two new datasets consider multi-path disjunctive rules, which is challenging for most existing methods.\n- EpiGNNs achieve state-of-the-art performance on the two new datasets. EpiGNNs also achieve competitive performance against existing methods on systematic generalization datasets, while being more efficient.\n- EpiGNNs have theoretical connection with the algebraic closure algorithm, though this point is not illustrated much in the main paper.\n- This paper is well-written and easy to comprehend.", "weaknesses": "- EpiGNNs are variants of NBFNet[1] with some engineering modifications: 1) hidden representations are replaced by probability distributions; 2) DistMult message function is replaced by Tucker decomposition[2] (Equation 4); 3) pooling function has an additional L1 normalization; 4) joint training of multiple models and forward-backward models. While I am not saying that EpiGNNs are incremental, the authors need to show how these modifications contribute to systematic generalization and provide experimental evidence for Line 257-258.\n- The authors miss an important baseline for systematic generalization: EdgeTransformer[3]. EdgeTransformer aggregates multiple relational paths like EpiGNNs and NBFNet. It can solve the sequential problem (Line 146-148) in arbitrary reduction order, which is even better than EpiGNNs. EdgeTransformer is likely to be a strong baseline for the two new datasets.\n- If I understand correctly, EpiGNNs use the same parameter matrix $\\bf{a}_{ij}$ across all layers. The original NBFNet uses different parameters for different layers and is not ideal for systematic generalization. Can you try a stronger NBFNet baseline with parameters shared across all layers? You might need to add dropout in each layer of NBFNet, similar to the design of EdgeTransformer.\n- It is trivial for EpiGNNs to achieve competitive performance against NBFNet on inductive knowledge graph completion, since EpiGNNs are just variants of NBFNet. This is not a contribution.\n\n[1] Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. Zhu et al. NeurIPS 2021.\n\n[2] TuckER: Tensor Factorization for Knowledge Graph Completion. Balažević et al. arXiv 2019.\n\n[3] Systematic Generalization with Edge Transformers. Bergen et al. NeurIPS 2021.", "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": "", "extra_scores": {}}, {"review_id": "ugYGR4nXie", "reviewer": "Reviewer_tM14", "summary": "The paper studies systematic generalization in the domain of multi-relational graphs. First, the authors identified that existing neuro-symbolic baselines capture only conjunctive rules and cannot capture disjunctive rules often present in spatial and temporal reasoning settings (such as Region Connected Calculus or Interval Algebra). Then, the paper introduced EpistemicGNN, which is able to learn disjunctive rules thanks to the theoretical alignment with algebraic closure. Practically, EpistemicGNN extends Neural Bellman-Ford Nets (NBFNet) with a new node labeling strategy, constrained node representations, changes to message passing and aggregation. For experiments, the authors introduced two new datasets for relation classification (RCC-8 and IA) and showed that EpiGNN is competitive with neuro-symbolic methods while being more parameter-efficient.", "questions": "I’d be willing to increase the score if the authors could address the following questions:\n\nQ1. Is there a link to the Relational WL test [1] when estimating the expressiveness of EpiGNNs?\n\nQ2. KG completion evals on GraIL datasets should be executed in the full-ranking setup, not against 50 random negatives.\n\nQ3. The new benchmarks should be future-proof for a few years ahead whereas RCC-8 and IA already seem to be saturating with models delivering 80%+ accuracy on hardest cases. Would it be possible to design more complex versions of the datasets where all compared models including EpiGNN would be challenged?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**S1.** Theoretical findings are quite interesting: a link between path-based GNNs and algebraic closure and how to learn disjunctive rules with such GNNs. Since EpiGNN is based on NBFNets, it would make the theoretical expressiveness claims even stronger if there is a connection to the relational WL test [1] which was derived for simple relational GNNs (eg, R-GCN) and labeling trick GNNs (like NBFNet).\n\n**S2.** Two new benchmarks for measuring systematic generalization with disjunctive reasoning patterns are nice to have for the community. However, there is a caveat that those benchmarks seem to be already saturated given that EpiGNN yields 90+% accuracy on them.\n\n[1] Huang et al. A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs. NeurIPS 2023.", "weaknesses": "**W1.** Despite the variety of benchmarks, the experimental performance of EpiGNNs is somewhat underwhelming: CLUTTR is already a saturated benchmark that does not provide much useful signal, Edge Transformers are as good on two newly introduced benchmarks (which seem to be saturating already), and EpiGNN underperforms other baselines on GraphLOG and inductive KG completion benchmarks. \n\nIt would make KG completion experiments much more compelling if EpiGNN is evaluated in the setup when predictions are ranked against _all_ nodes in the graph, not just against 50 random samples (there are many studies indicating that such ranking overestimates the results and is not indicative of the real performance). Since the backbone of EpiGNN is NBFNet, it should be possible to rank against all entities right out of the box without modifications and compare against stronger baselines that were evaluated on the full ranking task (for instance, NBFNet, A*Net, RED-GNN, AdaProp).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)