Understanding Expressivity of GNN in Rule Learning
Authors: Haiquan Qiu
Yongqi Zhang
Yong Li
quanming yao
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
KG reasoning
Link prediction
Rule learning
Expressivity
Primary area: learning on graphs and other geometries & topologies
TL;DR: We analyze the expressivity of SOTA GNNs for KG reasoning by deducing the rule strcutures they can learn.

Abstract: Rule learning is critical to improving knowledge graph (KG) reasoning due to their ability to provide logical and interpretable explanations. Recently, Graph Neural Networks (GNNs) with tail entity scoring achieve the state-of-the-art performance on KG reasoning. However, the theoretical understandings for these GNNs are either lacking or focusing on single-relational graphs, leaving what the kind of rules these GNNs can learn an open problem. We propose to fill the above gap in this paper. Specifically, GNNs with tail entity scoring are unified into a common framework. Then, we analyze their expressivity by formally describing the rule structures they can learn and theoretically demonstrating their superiority. These results further inspire us to propose a novel labeling strategy to learn more rules in KG reasoning. Experimental results are consistent with our theoretical findings and verify the effectiveness of our proposed method. The code is publicly available at https://github.com/LARS-research/Rule-learning-expressivity.

Published as a conference paper at ICLR 2024
UNDERSTANDING EXPRESSIVITY OF GNN IN RULE LEARNING
Haiquan Qiu', Yonggi Zhang?, Yong Li', Quamming Yau Department of Flectronic Engineering, Tsinghua University The Hong Kong University of Science and Technology (Guangzhou) qyaoaa inghua. edu. cn
ABSTRACT
Rule learning is critical improving knowledge graph (KG) reasoning due to their ability to provide logical and interpretable explanations. Recently, Graph Neural Networks (GNNs) with tail entity scoring achieve the state-of-the-art performance on KG reasoning. However, the theoretical understandings for these GNNs are either lacking or focusing on single-relational graphs, leaving what the kind of rules these GNNs can learn an open problem. We propose to fill the above gap in this paper. Specifically, GNNs with tail entity scoring are unified into a common frame- work. Then, we analyze their expressivity by formally describing the rule structures they can learn and thcoretically demonstrating their superiority. These results further inspire us propose novel labeling strategy to learn more rules in KG rea- soning. Experimental results are consistent with our theoretical findings and verify the effectiveness of our proposed method. The code publicly available httts //github. com LARS research/Rul. learning wew.pnn-ixxreessiiii.....
INTRODUCTION
A knowledge graph (KG) (Battaglia et al. 2018: Ji et al. 2021) is a type of graph where edges represent multiple types of relationships between entities. These relationships can be of different types, such friend, spouse, coworker, or parent-child, and each type of relationship is represented by a separate edge. By encapsulating the interactions among entities, KGs provide way for machines to understand and process complex information. KG reasoning refers the task of deducing new facts from the existing facts in KG. This task is important because it helps in many real-world applications, such as recommendation systems (Cao al. 2019 and drug discovery (Mohamed et al., 2019)
With the success of graph neural networks (GNNs) in modeling graph-structured data, GNNs have been developed for KG reasoming in recent years. Classical methods such R-GCN (Schlichtkrull et al. 2018) and CompGCN (Vashishth et al., 2020) are proposed for KG reasoning by aggregating the representations of two end entities of triplet. And they are known to fail to distinguish the structural role of different neighbors. GralL (Teru et al. 2020) and RED-GNN (Zhang & Yao 2022) tackle this problem by encoding the subgraph around the target triplet. GralL predicts a new triplet using the subgraph representations, while RED-GNN employs dynamic programming for efficient subgraph encoding. Motivated by the effectiveness of heuristic metrics over paths between a link, NBFNet (Zhu et al.] [202]) proposes neural network based on Bellman-Foo Ford algorithm for KG reasoning. AdaProp (Zhang et al., 2023) and A Net (Zhu et al., 2022) enhance the scalability of RED-GNN and NBFNet respectively by selecting crucial nodes and edges iteratively. Among these methods, NBFNet, RED-GNN and their variants score a triplet with its tail entity representation and achieve state-of-the-art (SOTA) performance on KG reasoning. However, these methods are motivated by different heuristics, e.g., Bellman-FFord algorithm and enclosing subgraph encoding, which make the understanding of their effectiveness for KG reasoning difficult.
In this paper, inspired by the importance of rule learning in KG reasoning, we propose to study expressivity of SOTA GNNs for KG reasoning by analyzing the kind of rules they can learn. First, we unify SOTA GNNs for KG reasoning into a common framework called QL-GNN, based on the
"Quamming Yao is the corresponding author.

---

Published as a conference paper at ICLR 2024
Target Rolations father
EL-GNN
F
Rule Structure Description
friend
teacher
parent
(h, C. Se
father
Exemplar Methods RL-X8FNe, EL-NEISGNN
sisterhood
spouse
parent
brother
D
QL-GNN
E
Structure Description Rhh CML
Target Relations aunt
sisterhood
aun't
Exemplar Methods
D
D
sisterhood
B
parent
brother
E
NDPPier RED GNX A AdaProp
Knowledge Graph
Rule structure
Expressivity
Figure The existence of a triplet in KG is determined by the corresponding rule structure. We investigates the kind of rule structures can be learned by SOTA GNNs for KG reasoning (i.e., QL- GNN), and proposes EL-GNN, which can learn more rule structures compared to QL-GNN.
observation that they score a triplet with its tail entity representation and essentially extract rule structures from subgraphs with same pattern. Then, we analyze the logical expressivity of QL-GNN to study its ability of learning rule structures. The analysis helps us reveal the underneath theoretical reasons that contribute to the empirical success of QL-GNN, elucidating their effectiveness over classical methods. Specifically, our analysis is based on the formal description of rule structures in graph, which differs from previous analysis that relies on graph isomorphism testing (Xu et al.) 2019); Zhang al.) 2021) and focuses on the expressivity of distinguishing various rules. The new analysis tool allows us to understand the rules learned by QL-GNN and reveals the maximum expressivity that QL-GNN can generalize through training. Based on the theory, also uncover the deficiencies of QL-GNN in learning rule structures and we propose EL-GNN based on labeling trick as an improvement upon QL-GNN to improve its learning ability. In summary, our paper has the following contributions:
Our work unifies state-of-the-an GNNs for KG reasoning into a common framework named QL-GNN, and analyzes their logical expressivity study their ability of learning rule structures, explaining their superior performance over classical methods.
The logical expressivity of QL-GNN demonstrates its capability in learning particular class of rule structures. Consequently, based on further theoretical analysis, introduce EL-GNN, a novel
GNN designed to learn rule structures that are beyond the learning capacity of QL-GNN.
Synthetic datasets are generated to evaluate the expressivity of various GNNs, whose experimental results are consistent with our theory. Also, results of the proposed labeling method show improved performance on real datasets.
2 A COMMON FRAMEWORK FOR THE STATE-OF-THE-ART METHODS
To study the foate-of-the-are GNNs for KG reasoning, we find that they (e.g., RED-GNN and NBFNet) essentially learn nule structures from GNN's tail entity representation which encodes subgraphs with the same pattern, i.e., subgraph with the query entity the source node and the tail entity as the sink node. Based on this observation, we are motivated to derive a common framework for these SOTA methods and analyze their ability of learning rule structures with the derived framework.
Given query (h, R, ?). the labeling trick of query entity ensures the SOTA methods to extract rules from a graph with the same pattern because it makes the query entity distinguishable among all entities in graph. Therefore, we unify NBFNet, RED-GN and their variants to a common framework called Query Labeling (QL) GNN (see correspondence in Appdendix
B For query (h, R, ?), QL-GNN
first applies labeling trick by assigning special initial representation (0) to entity h, which make the query entity distinguishable from other entities. Base these initial features, QL-GNN aggregates
2

---

Published as a conference paper at ICLR 2024
entity representations with L-layer message passing neural network (MPNN) for each candidate t E V. MPNN's last layer representation of entity in QL-GNN is denoted as c(4((h [h] indicating its dependency on query entity h. Finally, QL-GNN scores new facts (h, R, t) with tail entity
representation e, ( For example, NBFNet uses the score function s(h, R, 1) FFN(e, (M) (e for
new triplet (h, R, where FFN(-) denotes feed-forward neural network.
Even RED-GNN, NBFNet and their variant may take the different MPNNs to calculate without loss of generality, their MPNNs can take the following form in QL-GNN (omit [h] for simplicity):
e, e [h].
e = -(!! (HHUe!!-)) ( R)ju e NR(O), R}})):
where å and & are combination and aggregation functions respectively, is the message function encoding the relation R and entity u neighboring to v, {(...) is a multiset, and Nu((v) is the neighboring entity set [u, R. E E)
EXPRESSIVITY OF QL-GNN
In this section, we explore the logical expressivity of QL-GNN to analyze the types of rule structures QL-GNN can learn. First, we provide the logic to describe rules in KGs. Then, we analyze logical expressivity of QL-GNN using Theorem 3.2 and Corollary 3.3 formally demonstrating the kind of rule structures it can learn. Finally, we compare QL.-GNN with classical methods and highlight its superior expressivity in KG reasoning.
3.1 EXPRESSIVITY ANALYSIS WITH LOGIC OF RULE STRUCTURES
From previous works of rule mining on KG Yang al. 2017 Sadeghian et al. 2019), rule structures are usually described as a formula first-order logic. We also follow this way formally describe the rule structures in KG. Therefore, we have the following correspondence between the elements in rule structures and logie:
Variable: variables denoted with lowercase italic letters æ, y, z represent entities in KG;
Unary predicate: unary predicate P.(x) is corresponding to the entity property P. in KG, e.g., red(x) denotes the color of an entity is red;
Binary predicate: binary predicate (2 y) is corresponding to the relation R3 in a KG, e.g., father(æ, denotes is the father of y;
Constant: constant denoted with lowercase letters h, with serif typestyle is the unique identifier of some entity in a KG.
Except from the above elements, quantifier 3 expresses existence of entities satisfying condition, V expresses universal quantification, and 32-5 represents the existence of at least N entities satisfying a condition. The logical connective A denotes conjunction, V denotes disjunction, and T and 1 represent true and false, respectively. Using these symbols, rule structures can be represented by describing their elements directly. For example, C3(c, y) == E2 22, R1 (I. 21) A R2 22) A Ra(22, y) in 2 describes chain-like structure between and y with three relations R1, R2, R3- Rule structures can be represented using the rule formula R(x,, y). and the existence of a rule structure for the triplet (h, t) is equivalent the satisfaction of the rule formula R(x, y) the entity pair (h, l). In this paper, logical expressivity of GNN is measurement of the ability of GNN to learn logical formulas and is defined as the of logical formulas that GNN can learn. Therefore, since rule structures can be described by logical formulas, the logical expressivity of QL-GNN can determine their ability learn rule structures in KG reasoning.
3.2
WHAT KIND OF RULE STRUCTURES CAN QL-GNN LEARN?
In this section, analyze the logical expressivity of QL-GNN regarding what kind of rule structure can learn. Given a query (h, R, ?), we first have the following proposition about the rule formula describing rule structure.

---

Published as a conference paper at ICLR 2024
Proposition 3.1. The rule structure for query (h, R,?) can be described with rule rule formula R(x, y) or rule formula R(h, x) where h is the logical constant assigned to query entity h.
QL-GNN applies labeling trick to the query entity h, which can be equivalently seen as assigning constant h to query entity i With Proposition 3.1 (proven in Appendix Aj. the logical expressivity of QL-GNN can be analyzed by the types of rule formula R(h,x;) it can learn. In this case, the rule structure of triplet (h, R, 1) exists if and only if the logical formula R(h, a) is satisfied at entity t.
3.2. EXPRESSIVITY OF QL-GNN
Before presenting the logical expressivity of QL-GNNN we start by explaining how QL-GGNN learns the rule formula R(h, 2).. Following the definition in Barceló et al. (2020), we treat R((h, 2:) as binary classifier. When given a candidate tail entity t, if the triplet (4, R2t) t) exists in a KG, the binary classifier R(h, 22 should output true; otherwise, it should output false. If QL-GNN can learn the rule formula R(h, 2). it implies that QL-GNN can estimate binary classifier R(h, x). Consequently, if the rule formula R(h, x) is satisfied at entity t, the representation [ is mapped to high probability value, indicating the existence of triplet (h, R, t) in KG. Conversely, when the rule formula is not satisfied at i, e, a [h] is mapped to low probability value, indicating the absence of the triplet.
The rule structures that QL-GNN can learn are described by a family of logic called graded modal logic (CML) (De Rijke 2000 Otto 2019). CML is defined by recursion with the base elements T. all unary predicates (.(x), and the recursion rule: if p(x), 9 (Ir), (2( are formulas in CML, -p(x), fo (xx A yo2 (x), 32t y (R(y, A spy)) are also formulas in CML. Since QL-GNN introduces a constant h to the query entity h. we use the notation CML(G, h] to denote the CML recursively built from base elements in G and constant h (equivalent to constant predicate Pa (x)). Then, the following theorem and corollary show the expressivity of QL-GNN for KG reasoning.
Theorem 3.2 (Logical expressivity of QL-GNN). For KG reasoning, given a query (h, R, ?), a rule formula R(,,r) is learned by QL-GNN if and only if R(h, x) is a formula in CMI|G,hi, h).
Corollary 3.3. The rule structures learned by QL-GNN can be constructed with the recursion:
Base case: all unary predicates P((x)) can be learned by QL-GNN; the constant predicate Pa (x) can be learned by QL-GNN;
Recursion rule: if the rule structures Rí (h, R2,,, R(h, y) are learned by QL-GNN, Rg (h, x) A R2(h, v). 32N y (Ra(y, A R(h,y) are learned by QL-GNN.
Theorem 3.2 (proved in Appendix C provides the logical expressivity of QL-GNN with rule formula R(h, in CML[G, hi. which shows that querying labeling transforms R(x, y) to R(h, x:) and enable QL-GNN to learn the corresponding rule structure. To gain a concrete understanding of the rule structures learned by QL-GNN, Corollary provides the recursive definition for these rule structures. Note that Theorem 3.2 cannot be directly applied to analyze the expressivity of QL-GNN when learning more than one rule structures. The ability of learning more than one rule structures relates to the capacity of QL-GNN, which we take as a future direction. Theorem 3.2 also reveals the maximum expressivity that QL-GGN can generalize through training, and its proof also provides some insights about the design QL-GNN with better generalization (more discussions are provided in Appendix [FI.. Besides, our results in this section can be reduced to single relational -aaap by restricting the relation type to a single relation type, and we give these results as corollaries in Appendix E
3.2.2 EXAMPLES
We analyze several rule structures and their corresponding rule formulas in Figure 2 as illustrative examples, demonstrating the application of theory in analyzing the rule structures that QL-GNN can learn The real examples of these rule structures are shown in Figure] In Appdendix [A] we have detailed analysis of rule structures discussed in the paper and present some rules from real datasets.
Chain-like rules, e.g., C2(x, y) in Figure 2 are basic rule structures investigated in many previous works (Sadeghian et al. 2019 Teru et al. 2020 Zhu al. 202T). QL-GNN assigns constant h to
'The rule formula .)) is equivalent A2)(2, Px(2) where (a) denotes the assignment of constant to x and is called constant predicate our paper.
"The initial representation of an entity should be unique among all entities to be regarded constant in logic. The initial representation assigned to query entity are indeed unique in NBFNet, RED-GNN and their variants.
4

---

Published as a conference paper at ICLR 2024
query entity h, thus triplets with relation C3 can be predicted by learning the rule formula C3 xx). Cs(h, 2)) are formulas in CML[G, h] and can be recursively defined with rules in Corollary 3.3 (proven in Corollary A.2 Therefore, our theory gives general proof of QL-GNN's ability to learn chain-like structures.
The second type of rule struc- ture I (h, ) in Figure 2 com- posed of a chain-like structure from query entity to tail entity along with additional entity 22 connected to the chain. (h, x) are formulas in CMI,GG, hj and can be defined with recursive rules in Corollary 3.3 (proven in
Cg(t, :-]a1 Ry(z, Ro(a1
RR(39.8)
R1
R2
R3
Ca(h, =B2122 (j,h, #1) Ro(s)
Rg(2g.
query encity entity
1(b, :- Deg Rg. R: 21) Ro(aa Ro(=1.2)
R₃
R2
Corollary A.3)). which indicates that 1 (h, r) can be learned by QL-GNN. These structures are important in KG reasoning be- cause the entity connected to the chain can bring extra information about property of the entity it connected to (see examples of rule in Appendix A).
Rule structure
Rule formula
Figure 2: Example of rule structures and their corresponding rule formulas QL-GNN can learn.
3.3 COMPARISON WITH CLASSICAL METHODS
Classical methods such as R-GCN and CompGCN perform KG reasoning by first applying MPNN 11 compute the entity representations e . and then scoring the triplct (h, R, t) by shh, R, () = Agg(e), ( with aggregation function Agg(,, +). For simplicity, we take CompGCN as an example analyze the expressivity of the classical methods on learning rule structures.
Since CompGCN scores triplet using its query and tail entity representations without applying labeling trick, the rule structures learned by CompGCN should be in the form of Rxx, y). In CompGCN, the query and tail entities' representations encode different subgraphs. However, the joint subgraph they represent may not necessarily be connected. This suggests that the rule structures learned by CompGCN are non-structural, indicating there is no path between its query and tail entities except for relation R. This observation proven with the following theorem.
Theorem 3.4 (Logical expressivity of CompGCN). For KG reasoning, CompGCN can learn the rule formula R(x, y) fR ((p(x)), {g'(y)) where fR is a formula involving sub-formulas from {s(()) and (yd (y)} which are the sets of formulas in CML.G].
Remark. Theorem 3.4 indicates that representations of two end entities encoding two formulas respectively, and these two formulas are independent. Thus, the rule structures learned by CompGCN should be two disconnected subgraphs surrounding the query and tail entities respectively.
Similar to Theorem 3.2 CompGCN learns rule formula R(x, y) by treating it as a binary classifier. In KG, the binary classifier R(x, y) should output true if the triplet (h, R) exists; otherwise, should output false. If CompGCN can learn the rule formula R(x,, y). it implies that it can estimate the binary classifier Rxx,, y). Consequently, if the rule formula R(x,, v/ is (not) satisfied entity pair (h, t), the score shh, R, t) is high (low) value, indicating the existence (absence) of triplet (h, R, t).
Theorem 3.4 (proven Appendix C) shows that CompGCN can only learn rule formula R(æ, v) for non-structural rules. One important type of relation in this category is the similarity between two entities (experiments in Appendix D.22) like same_co col or y) indicating entities with the same color. However, structural rules are more commonly observed in KG reasoning (Lavrac & Dzeroski 1994 Sadeghian et al. 2019 Srinivasan & Ribeiro 2020). Since Theorem 3.4 indicates CompGCN fails to learn connected rule structures that are not independent, the structural rules in Figure 2 cannot be learned by CompGCN. Such a comparison shows why QL-GNN is more efficient than classical methods, e.g., R-GCN and CompGCN. in real applications. Compared with previous work on single-relational graphs, Zhhang et al. (202T) shows CompGCN cannot distinguish many non-isomorphic links, while our paper derives expressivity of CompGCN for learning rule structures.
5

---

Published as a conference paper at ICLR 2024
4 ENTITY LABELING GNN BASED ON RULE FORMULA TRANSFORMATION
QL-GNN is proven to be able to learn the class of rule structures defined in Corollary 3.3 For rule structures outside this class, we try to learn them with novel labeling trick based GN.. Our general idea is to transform the rule structures outside this class into the rule structures this class by adding constants the graph. The following proposition and corollary show how add constants to rule structure so that it can be described by formulas in CML and how to apply labeling trick to make it learnable for QL-GNN.
Proposition 4.1. Let Ri(, æ)) describe single rule structure G in G. If we assign constants Cı2 C2, ... , Cj. to all k entities with oul-degree larger than one in G, the rule structure can be described with new rule formula R' (h, in CML[G, h, C2, .ck]
Corollary 4.2. Applying labeling trick with unique initial representations to entities assigned with constants C12 C2, Cc Proposition 4.1 the rule structure G can be learned by QL-GNN.
For instance, in Figure the rule structure U cannot be distinguished from the rule structure T by recursive definition Corollary [3.] thus cannot be learned by QL-GNN. In this example, Proposition 4.1 suggests assigning constant с to the entity colored with gray in Figure 3 then new rule formula
U xh == Ri (h, c) A (322, 23, R2(c, x2) A R4(22, x) A Ra(c, z3) A (s(23,z))
in CML(G, h, c] (Corollary A.5) can describe the rule structure of U. Therefore, the rule structure of U can be learned with (h x) by QL-GNN with constant and cannot be learned by classical methods and vanilla QL-GNN.
Algorithm 1 Entity Labeling
Require: query (h, R, ?) knowledge graph G, degree threshold 1: compute the out-degree d, of each entity e in G;
2: for entity v in G do
3: if' dy d then
4: assign unique representation e entity w;
5: end if
6: end for
7: assign initial representation e, to the query entity h;
8: Return: initial representation of all entities.
Based Corollary 4.2 need apply labeling trick to entities other than the query entities in QL-GNN to learn the rule structures outside the scope of Corollary 3.3 The new method called Entity-Labeling (EL. GNN shown in Algorithm and and different from QL-GNN in as- signing constants to all the enti- ties with out-degree larger than d. We choose the degree threshold as a hyperparameter because a
R
R2
T(h == (.(h.a)) Ra(sn, R((aa))) A.ys. (b, ay) Ralay Rologa)
R
Rs
R2
Zz
query crritty
eatit
R₂
U(h, :=3ha, Ry(h, 45) A (3 Re(as, R.(ss.a)) A Rafay Reta.
RR
R2
Rule structure
Rule formula
Figure 3: Two rule structures cannot be distinguished by QL- GNN.
small dl (such as 1) will introduce too many constants KG, which impedes the generalization of GNN (Abboud et al.) 2021) (see an explanation from logical perspective in Appendix F.2). fact, a smaller d makes GNN learn the rule formulas with many constants and results bad generalization. while a larger d may not be able to transform indistinguishable rules into formulas in CML. As result, the degree threshold should be tuned balance the expressivity and generalization of GNN.
Same as the constant h in QL-GNN, we add unique initial representation e, for entities whose out-degree d, > d in steps 3-5. For the query entity h. we assign it with a unique initial representation (0) in step 7. In Algorithm [] it can be seen that the additional time of EL-GNN comes from traversing all entities in the graph. The additional time complexity is linear with respect to the number

---

Published as a conference paper at ICLR 2024
of entities, which is negligible compared to QL-GNN. For convenience, GNN initialized with EL algorithm is denoted as EL-GNN (e.g., EL-NBFNet) in our paper.
Discussion In Figure we visually compare the expressivity of QL-GNN and EL-GNN. Classical methods, e.g., R-GCN and CompGCN, are not compared here because they can solely learn non- structural rules which are not commonly-seen in real applications. QL-GNN, e.g., NBFNet and RED-GNN, excels learning rule structures described by formula R(h, x) in CML(G, h]. The proposed EL-GNN, encompassing QL-GNN as special case, can learn rule structures described by formula R(h, .) in CML[G, h, C1,'1 , which has a larger description scope than CML[G h).
5 RELATED WORKS
5.1 EXPRESSIVITY OF GRAPH NEURAL NETWORK (GNN)
GNN Kipf & Welling 2016: Gilmer et al. 2017 has shown good performance on a wide range of tasks involving graph-structured data, thus many cxisting works try to analyze the expressivity of GNNs. Most of these works analyze the expressivity of GNNs from the perspective of graph isomorphism testing. A well-known result (Xu et al. 2019) shows that the expressivity of vanilla GNN is limited to WL test and the result is extended
KGby [Barcelo et al. (0222. To improve the expressivity of GNNs, most of the existing works either design GNNs motivated by high-order WL test (Morris al. 2019; 2020 Barcelo al. 2022 apply special initial representations (Abboud ct al. [021 You et al. 2021 Sato et al. 2021| Zhang et al. 2021). Except for using graph isomorphism testing, Barceló (ariin,,.rrróó et al. (2020) analyze the logical expressivity of GNNs and identify that the logical rules from graded modal logic can be learned by vanilla GNN. However, their analysis is limited to node classification on the single-relational graph. Except from the expressivity of vanilla GNN, Tena Cucala et al. (2022) propose monotonic GNN whose prediction can be explained by symbolical rules in Datalog and the expressivity of monotonic GNN is further analyzed in Cucala et al. (2023).
Regarding the expressivity of GNNs for link prediction,Srinivaaaan Srinivasan & Ribeiro (2020) demonstrate
that GNNs structural node representations alone are insufficient for accurate link prediction. To overcome this limitation, they introduce method that incorporates Monte Carlo samples of node embeddings obtained from network embedding techniques instead of relying solely on GNNs. However, Zhang et al. (2011) discovered that by leveraging the labeling trick in GNNs, it is indeed possible to learn structural link representations for effective link prediction. This finding provides reassurance regarding the viability of GNNs for this task. Nonetheless, their analysis is confined to single-relational graphs, and their conclusions are limited to the fact that the labeling trick enables distinct representations for some non-isomorphic links, which other approaches cannot achieve. In this paper, we delve into the analysis of GNNs' logical expressivity to study their ability of learning rule structures. By doing so, we aim to gain a comprehensive understanding of the rule structures that SOTA GNNs can learn in graphs. Our analysis encompasses both single-relational graph and KGs, thus broadening the applicability of our findings.
A concurrent work by HHann et al. (2023) analyzes the expressivity of GNNs for NBFNet (a kind of QL-GNN in our paper) with conditional MPNN while our work unifies state-ot-the-ard GNNs into QL-GNN and analyzes the expressivity from different perspective focusing on the understanding of relationship between labeling trick and constants in logic.
5.2 KNOWLEDGE GRAPH REASONING
KG reasoning is the task to predict new facts based on the known facts in a KG G - (V, &, R) where V, E, 'R are sets of entities, edges and relation types in the graph respectively. The facts (or edges, links) are typically expressed as triplets in the form of (h, R, t), where the head entity h and tail entity t are related with the relation type R. KG reasoning can be modeled as the process of predicting the tail entity t of query in the form (h, R, ?) where h is called the query entity in our paper. The head prediction (?, R, f) can be transformed into tail prediction (t, R ?) with inverse relation R-1 Thus, we focus tail prediction in this paper.
Embedding- based methods like TransE (Bordes et al. 2013), ComplEx (Trouillon et al. 2016). RotatE (Sun et al. 2019), and QuatE (Zhang al. 2019) have been developed for KG reasoning.
7

---

Published as a conference paper at ICLR 2024
They learn embeddings for entities and relations, and predict facts by aggregating their representations. To capture local evidence within graphs, Neural LP (Yang et al.] al.] 2211)) and DRUM (Sadeghian et al.
2019 learn logical rules based predefined chain-like structures. However, apart from chain-like
rules, these methods failed to learn more complex structures in KG (Hamilton et al. 2018
Ren et al.
2019). GNNs have also been used for KG reasoning, such R-GCN (Schlichtkrull et al. 2018 and
CompGCN (Vashishth et al. 2020), which aggregate entity and relation representations to calculate scores for new facts. However, these methods struggle differentiate between the structural roles
of different neighbors (Srinivasan & Ribeiro 2020 Zhang et al. 2021). GralL (Teru et al. 2020)
addresses this by extracting enclosing subgraphs to predict new facts, while RED-GNN (Zhang
Yao 2022 employs dynamic programming for efficient subgraph extraction and predicts new facts
based on the tail entity representation. To extract relevant structures from graph, AdaProp ZZhng et al. 2023) improves RED-GNN by employing adaptive propagation to filter out irrelevant entities and retain promising targets. Motivated by the effectiveness of hcuristic path-based metrics for link prediction, NBFNet (Zhu et al. (202T) proposes neural network aligned with Bellman-Food algorithm for KG reasoning. Zhu et al. (022) propose A Net to learn a priority function to select important nodes and edges at each iteration. Specifically, AdaProp and A Net are variants of RED-GNN and NBFNet, respectively, designed to enhance their scalability. Among these methods, RED-GNN, NBFNet, AdaProp, and Net achieve state-of-the-art performance on KG reasoning.
EXPERIMENT
In this section, we validate our theoretical findings from Section and showcase the efficacy of our proposed EL-GNN (Section[4) 4 on synthetic and real datasets through experiments. All experiments were implemented in Python using PyTorch and executed on A100 GPUs with 80GB memory.
6.1 EXPERIMENTS ON SYNTHETIC DATASETS
We generate six KGs based on rule structures in Figure 2 6 validate our theory on expressivity and verify the improved performance of EL-GNN. These rule structures are either analyzed in the previous sections, or representative for evaluating GNN's ability for learning rule structures. We evaluate R- R-GCN, CompGCN, RED-GNN, NBFNet, EL-RED-GNN and EL-NBFNet (using DED.GNNNNBFNet as backbone with Algorithm D. Our evaluation metric is prediction Accuracy which measures how well a rule structure is learned. We report testing accuracy of classical methods, QL-GNN, and EL-GNN on six synthetic graphs. Hyperparameters for all methods are automatically tuned with Ray Liaw et al. 2018 based on the validation accuracy.
Table 1: Accuracy on synthetic data.
Method
Method
Css
C4
I1
T
R-GCN CompGCN
0.016
0.031
0.044 0.053
0.024
0.067
0.014
Classical
0.016
0.021
0.039
0.067
0.027
RED-GNN
1.0
1.0
1.0
1.0
1.0
0.405
QL-GNN
NBFNet
1.0
1.0
1.0
1.0
1.0
0.541
EL-RED-GNN
1.0
1.0
1.0
1.0
1.0
0.797
EL-GNN
EL-NBFNet 1.0
1.0
1.0
1.0
1.0
0.838
Dataset generation Given a target relation, there are three steps to generate a dataset: (1) rule structure generation: generate specific rule structures according to their definition; (2) noisy triplets generation: generate noisy triplcts to avoid GNN from learning naive rule structures; (3) missing triplets completion: generate missing triplets based on the target rule structure because the noisy triplets generation step could add triplets satisfying the target rule structure. We use triplets generated from rule structure and noisy triplets generation steps as known triplets in graph. Triplets with the target relation are separated into training, validation, and testing sets. Our experimental setting differs slightly from previous works as all GNNs in the experiments only perform message passing on the known triplets in the graph. This setup is reasonable and allows for evaluating the performance of GNNs in learning rule structures because the presence of a triplet can be determined based on the known triplets in the graph, following the rule structure generation process.
8

---

Published as a conference paper at ICLR 2024
Results Table I presents the testing accuracy of classical GNN methods, QL-GNN, and EL-GNN on six synthetic datasets (denoted as C3, Ca. I1, 12, T, and U) generated from their corresponding rule structures. The experimental results support our theory. CompGCN performs poorly on all six datasets, as fails to learn the underlying rule structures discussed in examples of Section (refer to Section D.2 for experiments of CompGCN). QL-GNN achieves perfect predictions (100% accuracy) for triplets with relations C₁ 1,, and T, successfully learning the corresponding rule formulas from CML[G, h]. EL-GNN demonstrates improved expressivity, as evidenced by its performance on dataset U, aligning with the analysis in Section 4 Furthermore, EL-GNN effectively learns rule formulas Ch,, x) and / (h, validating its expressivity.
Furthermore, we demonstrate the impact of the degree threshold on EL.-GNN with dataset U. The testing reveall accuracy in F reveals that an excessively small or large out-degree hinders the performance of EL.- GNN. Therefore, it is important to empirically fine-tune the hyperparameter d. To test the robustness of QL- GNN and EL-GNN in learning rules with incomplete structures, we randomly remove triplets in the training set to evaluate the accuracy of learning rule structures. The results can be found in Appendix D.4
2.00
Sut-degree
Figure 4: Accuracy versus out-degree d of EL-GNN on the dataset with relation U.
6.2 EXPERIMENTS ON REAL DATASETS
In this section, we follow the standard setup Zhu et al. [202T) test EL-GNN's effectiveness on four real datasets: Family (Kok& & Domingos 2007). >. Kinship (Hinton et al. 1986). UMLS Kook & Domingos 2007). WN18RR (Dettmers al., 2017), and FB 15k-233 (Toutanova Chen 2015). For fair comparison, we evaluate EI-NBFNet and EL-RED- GNN (applying EL. to NBFNet and RED-GNN) using the same hyperparameters as NBFNet and RED-GNN and handcrafted d. We compare it with embedding-basee methods (RotatE, QuatE), rule-based methods (Neural LP, DRUM), and GNN- methods (CompGCN, NBFNet, RED-GNN). To evaluate performance, we provide testing accuracy and standard deviation obtained from three repetitions for thorough evaluation.
In Table 2 we present our experimental findings. The results first show that NBFNet and RED-GNN (QL-GNN) outperform CompGCN. Furthermore, the proposed EL algorithm improves the accuracy of RED-GNN and NBFNet on real datasets. However, the degree of improvement varies across datasets due to the number and variations of rule types, and the quality of missing triplets in training sets. More experimental results, e.g., time cost and more performance metrics, are Appendix [.5]
Table 2: Accuracy and standard deviation on real datasets. The best (and comparable best) results are in "bold", the second (and comparable second) best are underlined.
Method Class
Methods
Family
Kinship
UMLS
WN18RR
FB15k-237
Embedding-
RotatE QuatE
0.86520.004
0.70440.002
0.860
0.42740.003
0.240+0.00
based
0.89720.001
0,31
0.907+0.002
0.441#0.002
0.255+0.000 004
Neural LP
0.872=0.002 0.481
0.630=0.001
0.369#0.003
0. 0.190000000
Rule-based
DRUM
0.880=0.003
0,459+0.005
0.676#0.004
0,424+0.003
0.252+0.003
CompGCN
0.88320.001
0.751
0.867
0,443+0.00 0.001
0.265+0.00
RED-GNN
0.988=0.002
0.820+0.003
0.946#0.000
0, 0,502+0.00 0011
0.284=0.00 002
GNN-based
NBFNet
0.977=0.001
0.819+0.002
0.946=0..0z
0.496+0.002
0.320+0.00
EL-RED-GNN
0.990=0.002
0.839=0.000
0.952
0.504+0.001
0.322+0.00 002
EL-NBtNet
0.985+0.001
0.842:0.003
0.953*0.002
0.501
0.332+0.001
7 CONCLUSION
In this paper, we analyze the expressivity of the state-of-the-art GNNs for learning rules in KG reasoning, explaining their superior performance over classical methods. Our analysis sheds light on the rule structures that GNNs can learn. Additionally, our theory motivates an effective labeling method to improve GNN's 'ss expressivity. Moving forward, will extend analysis to GNNs with general labeling trick and try to extract explainable rule structures from trained GNN. Limitations and impacts discussed in Appendix G

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Q. Yao was in part supported by National Key Research and Development Program of China under Grant 2023YFB2903904 and NSFC (No. 92270106).
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In International Joint Conference Artificial Intelligence, 2021.
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, 2021.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020.
Pablo Barcelo, Mikhail Galkin, Christopher Morris, and Miguel Romero Orth. Weisfeiler and leman go relational. In The First Learning on Graphs Conference, 2022. URL /tRLitttt/////eeeevviee
net//oorumicee 6phh
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzaez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 2018.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in Neural Information Processing Systems, 2013.
Yixin Cao, Xiang Wang, Xiangnan He, Zikun Hu, and Tat-Seng Chua. Unifying knowledge graph learning and recommendation: Towards a better understanding of user preferences. International World Wide Web Conference, 2019.
David Tena Cucala, Bernardo Cuenca Grau, Boris Motik, and Egor V Kostylev. On the corre- spondence between monotonic max-sum gnns and datalog. arXiv preprint 2xXi:22305.18015 2023.
Maarten De Rijke. note on graded modal logic. Studia Logica, 64(2):271-28) 2000.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2D knowledge graph embeddings. AAAI conference on Artificial Intelligence, 2017.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning, 2017.
Will Hamilton, Payal Bajaj. Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. Advances neural information processing systems, 31, 2018.
Geoffrey E Hinton et al. Learning distributed representations of concepts. In Annual Conference of the Cognitive Science Society, 1986.
Xingyue Huang, Miguel Romero Orth, ismail ilkan Ceylan, and Pablo Barceló. theory of link prediction via relational weisfeiler-leman arXiv preprint arXiv:2302.02209 2023.
Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. A survey knowledge graphs: Representation, acquisition, and applications. IEEE transactions on neural networks and learning systems, 33(2):94-514, 2021.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2016.
10

---

Published as a conference paper at ICLR 2024
Stanley Kok and Pedro Domingos. Statistical predicate invention. In International Conference Machine Learning, 2007.
Nada Lavrac and Saso Dzeroski. Inductive logic programming. In WLP, pp. 146-160. Springer, 1994.
Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and lon Stoica. Tune:
A research platform for distributed model selection and training. arXiv preprint 1rXiv/887.005/66 2018.
Sameh K. Mohamed, Vit Novácek, and Aayah Nounu. Discovering protein drug targets using knowledge graph embeddings. Bioinformatics, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI conference on Artificial Intelligence, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 2020.
Martin Otto. Graded modal logic and counting bisimulation. arXiv preprint arXiv:1990.00000 2019.
Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations. 2019.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. Advances in Neural Information Processing Systems, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In SIAM International Conference on Data Mining, 2021.
Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, 2018.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. ICLR, 2020.
Zhiqing Sun, Zhi-Hong Deng, Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference Learning Representations, 2019.
DJ Tena Cucala, B Cuenca Grau, Egor V Kostylev, and Boris Motik. Explainable gnn-based models over knowledge graphs. 2022.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, 2020.
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 of the 3rd Workshop on Continuous Vector Space Models and their Compositionalityy pp. 57-66, Beijing, China, July 2015. Association for Computational Lin- guistics. doi: 10. 101118853/11/// 5-4007.
URI. hts a/ac///caaa antho loyy. ogy.ooy......................... org//15 4007
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International Conference on Machine Learning. 2016.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi- relational graph convolutional networks, In International Conference on Leamning Representations, 2020.
11

---

Published as a conference paper at ICLR 2024
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. Advances in Neural Information Processing Systems, 2017.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying. and Jure Leskovec. Identity-aware graph neural networks. In AAAI Conference on Artificial Intelligence, 2021.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 2021.
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. Advances in Neural Information Processing Systems, 32, 2019.
Yongqi Zhang and Quanming Yao. Knowledge graph reasoning with relational digraph. In Interna- lional World Wide Web Conference, 2022.
Yongqi Zhang, Zhanke Zhou, Quanming Yao, Xiaowen Chu, and Bo Han. Adaprop: Learning
adaptive propagation for graph neural network based knowledge graph reasoning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3446-3457, 2023.
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 2021.
Zhaocheng Zhu, Xinyu Yuan, Mikhail Galkin, Sophie Xhonneux, Ming Zhang, Maxime Gazeau, and Jian Tang. A nett A scalable path-based reasoning approach for knowledge graphs. arXiv preprint arXiv:2206. 04798, 2022.
12

---

Published as a conference paper at ICLR 2024
A
RULE ANALYSIS
We first give simple proof for Proposition 3.1
proof of Proposition 3.1 Since R(h, z) is equivalent to x) Px(2,, where Pa(z) is the constant predicate only satisfied at entity h. Because R82, æ) can describe the rule structure of (h, R, ?). 32R(2 x) A (z) can describe the rule structure of (h, R, ?) as well.
We use the notation G, v = P. (G, H P.) to represent that the unary predicate Pi(x)) is (not) satisfied at entity v.
Definition A.1 (Definition of graded modal logic). A formula in graded modal logic of KG G is recursively defined as follows:
1. If pxx) G. F y if an entity in KG;
2. If ((x) P.(x), G, J y if and only if e has the property P. or can be uniquely identified by constant c:
3. If p(x) = (x) A (2(2), G o F + if and only if G, c P1 and G, F P2;
4. If (p(x) -x(x), G, == yp if and only if G o;
5. If (1)) 922 y, (y. A dly). G, }= yp if and only if the set of entities {ulu
Nn, (1) and G, Φ) has cardinality at least N.
Corollary A.2. Cz(h, æ) are formulas in CML[G, h].
Proof. Ca(h, x) is a formula in CML[G. h] as it can recursively defined as follows
(I()) = (z)
(2(x)) Ey. R1 x)) A pp((),
Pa(x) Fy. R2(y, A (2((),, C (h, Ey. Ra(y, x) A (pa()).
Corollary A.3. 1 (h, 3) is a formula CML h).
Proof. 1,( (h,,,)) x)) is a formula in CML(G, h] as it can be recursively defined as follows
(1(2) Pr(x),
(2(xx) = Ey, Ri (I A pı((),
(z(2) Ey. R2(y, A AT,
pa(x) = -P((x) A (2))2,,
I [h, x) Ey. (2(,, A pa(v))
Corollary A.4. T(h,x) is a formula in CML(G,
Proof. By Corollary A.2 32,22, Ri 21) A R3(21 22) A Rs(22, x) are formulas in CML h). Thus T(h, x) C (h, A (h, x) is formula in [ML[G, h].
32 Rí (h, 21) A R2(21, x2) A R4 z) and C (h, =
Corollary A.S. (h, x) formula in CMI h,
13

---

Published as a conference paper at ICLR 2024
Proof. (h, 2)) is formula in CML h, as it can be recursively defined as follows
(1(x) (t(z))
Pc(x),
(2(()) = by. (1 A (P()),
Pa(#)) = <2(()) A Pe(
(((x) Fy. R2(u.2) 2) A (P(()),
(b(()) = By. Ry 2) P4(3),
( By. Ry 2) ps(P),
(x(x) = 3y. Rs(y. 2) (1)),)
(" x) = ( (x)
where the constant с ensures that there is only one entity satisfied for unary predicate (a(2))
Example of rules We find some relations in reality corresponding rules in Figure are two examples of C3 and /
Here
Relation nationality (C3): Einstein -bhom_in in
Ulm
boreetown_af
Born
nationality
Germany;
Relation father (h)): A spoouse parent
Cand D sisterhood B.
Rule structures in real datasets To show that the expressivity is meaningful in our paper, we select three rule structures from Family and FB15k-233 in Figure[JJta show the existence of rule structures
in real datasets. With the definition of CML, the rule structure in Figure 5[a) is not formula in CML and rule structures in Figure (b) and 5 ((e) are formulas in CMI.. The real rules shows that rules defined by CML is common in real-world datasets and the rules beyond CML also exist, which highlights the importance our work.
Instie
wtbrloty
Scottish Americans
diescbuttinn
Walter
1482
1432
1249
1480
Oliver Hardy
USA
Allens
Allen Predator
senre
action film
Las Vegas
Allen
presert
Trrat heattrns son
Torae haustone nationality
Telesie ganre
(6)
Figure 5: Some rule structures in real datasets. The rule structure (a) from Family dataset and is not a rule formula in CML(G, h], which cannot not be learned by QL-GNN, The rule structures (b) and (c) are from FB15k-237 dataset and are rule formulas in CML(G h), which can learned by QL-GNN.
Summary Here we give Table to illustrate the correspondence between GNNs for KG reasoning, rule structures, and theories presented in our paper.
Table 3: Whether GNNs investigated in our paper can learn the rule formulas in Figure 2 and S and the exemplar methods of these GNNs. v() mean the corresponding GNN can(not) lean the rule formula.
Rule formula Cs(h,
xh)
T(h
J(h
Theoretical result
Exemplar Methods
Classical
x
x
x
x
Theorem 3.4
R-GCN, CompGCN NBFNet, RED-GNN
QL-GNN
x
Theorem
EL-GNN
Proposition
EL-NBFNc/REE--GN
B RELATION BETWEEN QL-GNN AND NBFNET/RED-GNN
In this part, we show that NBFNet and BED-GNN are special cases of QL-GNN Table 4 and respectively.
14

---

Published as a conference paper at ICLR 2024
Table 4: NBENet is special of QL-GNNN
NBFNet
Query representation Non-query representation
Relation embedding
MPNN
AGGREGATE
({
MESSAGE
hh-11) 10,(a, 1, v)
(2, E EE(r) u {n!"))
Triplct score
Feed-forward network
Table 5: RED-GNN is special case of QL-GNN.
RED-GNN O NULL
Query representation Non-query representation
8( (Elorrteeenneee & (heeten
MPNN
Triplet score
Linear transformation
C
PROOF
We use the notation G, (h, - R2 (G, (h, y R2) to denote Ry (2, y) is (not) satisfied at h,
C.I
BASE THEOREM: WHAT KIND OF LOGICAL FORMULAS CAN MPNN BACKBONE FOR KG LEARN?
In this section, we analyze the expressivity of MPNN backbone ( for learning logical formulas in KG. This section is the extension of Barceló et al. (2020) to KG.
In KG G E, MPNN with layers is type of neural network that applies graph G and initial entity representation e to learn the representations e E V. MPNN employs message- passing mechanisms (Gilmer et al. 2017 to propagate information between entities in graph. The k-th layer of MPNN updates the entity representation via the following message-passing formula
(k) e((((t2))
(1(v(e!
R)ju E NN(v), R RE))))
where 5 and e are combination and aggregation functions respectively, the message function encoding the relation R and entity neighboring to ((..)) }} is a multiset, and Nn(vv) is the neighboring entity set [u, R, v) E E).
To understand how MPNN can learn logical formulas, we regard logical formula po(x) binary classifier indicating whether (p(x) is satisfied at entity x. Then, we commence with the following definition.
Definition C.I. A MPNN captures a logical formula p(x)) if and only if given any graph G, the MPNN representation can be mapped to a binary value, where True indicates that (ox) satisfies on entity z, while False does not satisfy.
According to the above definition, MPNN can learn logical formula in KG by encoding whether these logical formulas is satisfied the representation of the corresponding entity. For example, MPNN
can learn logical formula (xr)) it implies that e can be mapped to a binary value True/Fa a se by a function indicating whether (p(x) satisfied at entity v. Previous work (Barceló et al. 2020) has proven that vanilla GNN for single-relational graph can learn the logical formulas from graded modal logic (De Rijke 2000 Otto| 2019) (a.k.a., Counting extension Modal Logic, CML). this section, will present similar theory of MPNN for KG.
The insight of MPNN's ability to learn formulas in CML lies in the alignment between cer- tain CML formulas and the message-passee passing mechanism. which also holds for KG. Specifically, 32N, (R, (y. æ) A (yy)) is the formula aligned with MPNN's message- message-passing mechanism and allows to check the property of neighbor of entity variable We use notation CML[[G] to denote
15

---

Published as a conference paper at ICLR 2024
CML of a graph G. Then, give the following theorem to find out the kind of logical formula MPNN ( can learn in KG.
Theorem C.2. In a KG G, a logical formula ((x) learned by MPNN from its representations if and only if ((x) is formula in CML[G].
Our theorem can be viewed as an extension of Theorem 4.2 Barceló et al. (020)) to KG and the elementary tool for analyzing the expressivity of GNNs for KG reasoning. The proof of Theorem C.2 in Appendix [ and employs novel techniques that specifically account for relation types. Our theorem shows that CML of KG is the tightest subclass of logic that MPNN can learn. Similarly, our theorem is about the ability to implicitly learn logical formulas by MPNN rather than explicitly extracting them.
C.2 PROOF THEOREM C.2
The backward direction of Theorem is proven by constructing MPNN that can learn any formula
(p(x) in CML. The forward direction relies on the results from recent theoretical results in Otto (2019). Our theorem can be seen as extension of Theorem 4.2 in Barceló et al. (2020) to KG.
first prove the backward direction of Theorem
Lemma C.3. Each formula (0x) in CML can be learned by MPNN ① from its entity representations.
Proof. Let (x)) be formula in CML. We decompose &p into a series of sub-formulas sub (g) (991 92, f1)) where yok is a sub-formula of yp if k S l and & şr. Assume the MPNN representation e, E RRL, v V i = 1 .... L. In this proof, the theoretical analysis will based on the following simple choice of
fi- cf
C+ Σ
Σ
el
e(i-t) AR, +b
WENRR
(0)
with a = min(maxx) x), 1), AR,CC C LXL and b E Rt.
CR,,Ce A n,, C, and b depend on the sub-formulas of y follows:
The entries of the L-th columns of
Case if (p(x)) Pe(x) where Pa is unary predicate, Cit = 1;
Case 1. if (pe(x) = (x) A (x)))) Cje = Cke = and by = -1;
Case 2. if spr = (x), Cke = and by = 1;
Case 3. if (pe(x)) =2²% y (v. (x(()),, (An,) and be -N + +1
with all the other values set to O.
Before the proof, for every entity V. the initial representation e (t1, .tn) has to 1 the sub-formula &Pe = (x(x)) satisfied at v, and te = 0 otherwise.
Let G = EV,E, R) be a KG. We next prove that for every upe E sub(yp and every entity v E V it holds that
(o.)) = if G,v pe. and c
otherwise,
for every L.
Now, we prove this by induction of the number of formulas in sp.
Base case: One sub-formula in yp In this case, the formula an atomic predicate ; = <p((x) = Pa(x).
Because Cæt = and (e (e) 1, (e.")) 0, * L, have (e! )2 if G, } Prr and
(e(") )r = 0 otherwise. For 1, (i) satisfies the same property.
Induction Hypothesis: k sub-formulas in &o with & < é. Assume
(8) e
1 G. += 5s and
ey
= otherwise for & sis < L.
A
16

---

Published as a conference paper at ICLR 2024
Proof: l -uu-ffomulas in yp Let i 2 L. Case 1-3 should be considered.
Case 1. Let (x) = (z) A (x(x). Then Cye = Ckt = and b, = =-1 Then we have
(c!")) ((e!-
(c -1).
By the induction hypothesis, (e: ( و
only G v } 9j and (e. (e = otherwise. if and only if G. F Pp and (e (e!--))) 0 otherwise. Then have
Similarly, (e) (e
(e!") )e = if and only (e " + (eb ( )b - 1 2 1, which means (el D) ) = 1 and (e (f (
(e)
1. Then (e!")) ) if and only if G, 9j and G,v v F Pk. ie., G, yee and (e. 0 otherwise.
Case 2. Let (x) (x). Because of Cke 1 and by 1, have
(o! ) = (- ((((f(-1)) ) + +1)
By the induction hypothesis, (e: (e!- (1-1))
(1-1)) ) 0 otherwise. 1 if and only if G, }=' sPu and (e:
Then we have (e!")) )₂ = and only (o!--1)) + 2 1, which means (e )k = 0. Because
(el (i-1) 1) k 0 if and only if G, u # sp, we have (e ) if and only if G, v / ph., i.e., G, v } 4Pt.
and (e: r otherwise.
Case 3. Let (x(x)) 2Nt y (R)( A px(())). Because of (AR, ue and by -N
have
(el")) =o
(e(1-1)) N - NN+1
WENN, (v)
By the induction hypothesis, (el (el--)))x k if and only if G, -=r (pk and (el (eli-1))) 0 other- wise. Let m = |u/u E NNa, (v) and G, u += xxHl- Then we have (c. )e = 1 if and only
EusNn, (1) (c N + 2 1, which means m 2 N. Because G, F= yk. u is connected
to with relation Ry, and N, have (e! ) 1 if and only if G, v - ye and (e!") otherwise.
To learn logical formula p(x), only apply linear classifier to e v to extract the component of e corresponding to p.. If G, v -= the value of the corresponding extracted component is 1.
Next, we prove the forward direction of Theorem C.2
Theorem C.4. A formula (p() is learned by MPNN 1 if it can be expressed as a formuula in CML.
To prove Theorem we introduce Definition
Lemma C.6 Theorem C.7 and Lemma C.8
Definition C.5 (Unraveling tree). Let G be a KG, v be entity G, and E N. The unravelling of in G at depth L, denoted by Unry is tree composed of
R,, u.) in G with i S L,, edge R2 between (v. R1, u..... R 4-1) and (v, R1, "1, ... R₁ u.) when (w, R4, 1: is a triplet in G' (assume un is v), and
node (v, R1, ",,"",, R4, u4) for each path (v. R1, "1,"
each node (v, R1, ".. RR, u4) has the same properties u, in G.
Lemma C.6. Let G and G' be two KGs, and v' be two entities in G and G' respectively. Then for every L E N, the RWL test Barcelo et al. 2022) assigns the same color/hash to e and at round if and only if there is isomorphism between Unr'g(u) and Unrlg. (v') sending v'.
17

---

Published as a conference paper at ICLR 2024
Proof. Base Case: When L = 1, the result is obvious.
Induction Hypothesis: Relational WL (RWL) test assigns the same color to e and v' at round L - 1 and only if there is an isomorphism between Unry (v) Unrl-1(v)) and Unr sending v'.
Proof: In the L-th round.
Prove "same color = isomorphism".
(u) - hash (e ([(ct-1(u) R.jlu E NR. (v) 1, ,r)...)
(0') hash hassh(c (c); (((cet((u')) R3) E NN, 1 ,
Because (²()) = (v'), we have c² (2) = cd (v'), and there exists an entity pair (u, u(), E (U), uf Nn that
(c) R₂) = (u).
Then we have (u- = c According to induction hypothesis, we have Unrg-t(u) = Unrg-'(vi (u'). Also, because the edge connecting entity pair (e, u) and (v', u') is Rg, so there is an isomorphism between (v) and Unroy (v") sending to
Prove "isomorphism = same color".
Because there exists an isomorphism between (v) and Unray (v") sending to v', assume is an bijective between the neighbors of and v', e.g, u E (u), E (v') and ut o (u:), the relation between entity pair (u, v) and (u', v') is R.
Next we prove cl- = cl-)(n'). Because Unrg(v) and (nr)(v') are isomorphism, and maps (u) to u' E (u),, for the left tree with L - 1 depth, i.e., Unré-t(u) and Unrg-"(u'), can be the isomorphism mapping between (nr and Undl) According to induction hypothesis, we have (u- - (u'). Because (nr = Unro. (v"), also have Unrk-1(w) (u) = Unri-'(un which means (u- cl-)(w'). After running RWL test, have (v() (1))
(u)
Theorem C.7. Let (xx) be a unary formula in the formal description of graph G in Section 3.1 If up(a ()) is not equivalent to a formula CML, there exist two KGs G and G' and two entities v and o' in G' such that Unr(<(v) = Unrta (v') for every L E M and such that G, C vp but G¹, v' sp
Proof. The theorem follows directly from Theorem 2.2 in Otto 2019). Because G, v ~ G.
and Unr 2 Unrkg- are equivalent with the definition of counting bisimulation (i.e., notation x)
Lemma C.8. a formula p(x) is not equivalent to any formula in CML, there is no MPNN 1 that can learn sp(x).
Proof. Assume for contradiction that there exists MPNN that can learn (zx)) Since (p(x) is not
equivalent to any formula in CML, with Theorem C.7 there exists two KGs G and G' and two entities
in G and of in G' such that (v) 2 Unr (o') for every L N and such that G, v F= y0 and
G², o' / sp By Lemma C.6, because (u) S Unr (u') for every L E N, we have c c But this contradicts the assumption that MPNN is supposed to learn (z(z).
Proof of Theorem C.4
Theorem can be obtained directly from Lemma C.8
Proof of Theorem
C.2
Theorem can be obtained directly by combining Lemma C.3 and Theorem C.4
The following two remarks intuitively explain why MPNN can learn formulas in CMI..
18

---

Published as a conference paper at ICLR 2024
Remark C.9. Theorem C.2 applies to both CML[G] and CML|G, C2, C2. .ck] The atomic unary predicate P.(x) in CML of graph is learned by the initial representations e E V, which can be achieved by assigning special vectors to e 2 V. In particular, the constant predicate Po(z) in CML[G, c| is learned by assigning a unique vector (c.g., one-hot vector for different entities) the initial representation of the entity with unique identifier The other sub-formulas ,,(x), (1())) (x) A (2(2)) in Definition A can be learned by continuous logical operations (Arakelyan al. 2021 which are independent of message-passing mechanisms.
learn the formula yp()) in CML, the i-th layer representations e E V of MPNN can learn 32 y, (3. x) A Ap(y) with specific aggregation function in because e!!) u E can aggregate the logical formulas in the one-hop neighbor representation e E V (i.e., c(x)) with message-passing mechanisms.
Remark C.10. Assume the (i- 1)-th layer representations
e (i-1) o
The following remark clarifies the scope of Theorem C.2 and 3.2
Remark C.11. The positive results for theorem (e.g., . a MPNN variant can learn logical formula) hold for MPNNs powerful than the MPNN we construct in (2). while our negative results (e.g.. MPNN variant cannot learn logical formula) hold for any general MPNNs (T). Hence, the backward direction remains valid irrespective of the aggregate and combine operators under consideration. This limitation is inherent to the MPNN architecture represented by ( and not specific to the chosen
representation update functions. On the other hand, the forward direction holds for MPNNs that are more powerful than
C.3 PROOF OF THEOREM
Definition C.12. QL-GNN learns a rule formula R(h, x) and only given any graph G, the QL-GNN's score of new triplet (h, R) can be mapped binary value, where True indicates that R(h, z) satisfies on entity t, while False does not satisfy.
Proof. We the KG G and restrict the unary formulas in CMI h] the form of R(h, ar). This theorem is directly obtained by Theorem because constant can be equivalently transformed to constant predicate (x)).
Base case: Since the unary predicate can be encoded into the initial repre- sentation of the entity according to Section C.1 Then the base case is obvious.
Proof of Corollary 3.3
Recursion rule: Since the rule structures R(h, v). R1 2h) (2, x) are unary predicate and can be learned by QL-GNN, they are formulas in CML h). According to recursive definition of CML, Rí (h, .) A R2 y), 328 (R.(v, A R(h, y)) are also formulas in CML[[,, h). therefore can be learned by QL-GNN.
C.4 PROOF THEOREM 3.4
Definition C.13. CompGCN learns rule formula R(x, y) if and only if given any graph G, the QL-GNN's score of a new triplet (h, R, t) can be mapped to a binary value, where True indicates that R(x, y) satisfies entity pair (h, t), while False does not satisfy.
Proof. According to Theorem C.2 the MPNN representation (L) can represent the formulas in
CML[G). Assume i (xr) and (p2(y) can be represented by the MPNN representation e E V and
there exists two functions gi and g2 that can extract the logical formulas from (!)) i.e., gi (1) if G, v = ii and (e(e 0 if G, I ip; for i 2. We show how the following two logical operators can be learned by s(h, R, t) for candidate triplet (h, R, t):
Conjunction: 4p (x) A (2)). The conjunction of ()(())) (v) can be learned with function s(h, R,t) gi (e) (1) ())
19

---

Published as a conference paper at ICLR 2024
Negation: (x)( The negation of (2((2) can be learned with function s(h, R,t) (e(e
The disjunction V can be obtained by (2-x((()) A -p2(y)). More complex formula involving sub-formulas from (1(()) and (sp (y)) can be learned by combining the score functions above. D
C.5 PROOF OF PROPOSITION 4.1
Lemma C.14. Assume (p() describes a single-connected rule structure G in a KG. If assign constant to entities with out-degree large than 1 in the KG, the structure G can be described with formula op (x) in CML of KG with assigned constants.
assume (ar) with assigned constants is not equivalent formula in CML,, there should exist two rule structures G, G' in KG G, G', and entity in G and entity in G' such that (v) Unro (v') for every L E IN and such that G, v t o but G', v K yp'
Proof. According to Theorem C.7
Since each entity in G (G') with out-degree larger than is assigned with constant, the rule structure (G') can uniquely recovered from its unravelling tree Unr (v) (Unrg (v)) for sufficient large L. Therefore, if (w) = Unra for every N, the corresponding rule structures G and G' should be isomorphism too, which means G, += sp and G', v' - pp. Thus, (x(x)) must be formula in CML.
Proof of Proposition 4.7 on Lemma C.14
The theorem holds by restricting the unary formula the form of R(h,
Proof of Corollary 4.2 By converting new constants Ck to constant predicates
Pey (x), Pay (x),
(2)), the corollary holds by using Theorem 3.2
D EXPERIMENTS
D. MORE RULE STRUCTURES SYNTHETIC DATASETS
In Section 6_1
we also include the following rule structures in the synthetic datasets, i.e., C4 and Ta in Figure for experiments. C4 and I are both formulas from CML(G, h). The proof of C4 is similar to the proof of C3 in Corollary A.2 The proof of Ja is similar to that of I and is Corollary D.I
Ca(,, x) = 32, (h, 21) Ro(21, P2)
R
21
R
Zz
R
Z3
R4
A. Ra(ze, 2)) A (a)
query eniiyy
tall ontity
R
12(h,)) =3 (h, 21) ()) A B2(2). 22) (32N ss, Ri(zs, zx) A R)(22
R₂
Rule structure
Rule formula
Figure 6: In the synthetic experiments, we also compare the performance various GNNs on the synthetic datasets generated from C4 and lz.
Corollary D.I. T2( x: is formula in CMI. h).
20

---

Published as a conference paper at ICLR 2024
Proof. (2, x)) is formula in CML(G, h| as it can be recursively defined follows
(1(2) = (r(x),
(2(22) Ey, Ri (y, x)) (v)),
Pa(x) = Ey, R2(,, x) A x2((),,
(z) = = Ra(y. AT,
Pa(x) (x(x)) A (z(())
[2(h.2) 2) Fy, R3(v, x) A (v()))
D.2 EXPERIMENTS FOR COMPGCN
The classical framework of KG reasoning is inadequate for assessing the expressivity of CompGCN because the query (h, R, ?) assumes that certain logical formula (o(x) are satisfied at the head entity by default. In order to validate the expressivity of CompGCN, it necessary to predict all missing triplets directly based on entity representations without relying on the query (h, R, ?). To accomplish this, we create new dataset called S that adheres the rule formula Sax, y) 4p (x) (v). where the logical formula is defined as:
(x) = (2. A (Ar A (Ry v)))
Here, (x) is represented with parameter reusing (reusing x and y) and is a formula in CML. Therefore, the formula S(z, y) takes the form of R(x, by CompGCN, as indicated by Theorem 3.4 To validate our theorem, we generate a synthetic dataset S using the same steps outlined in Section 6.1 following the rule S(x, y). We then train CompGCN on dataset S. The experimental results demonstrate that CompGCN effectively learns the rule formula S(x, y) with 100% accuracy. Comparing it with QL-GNN is unnecessary since the latter is specifically designed for KG reasoning setting involving the query (h, R,?).
fR({(((=)), {x(())) and can be learned
D.3 STATISTICS OF SYNTHETIC DATASETS
Table 6: Statistics of the synthetic datasets.
Datasets
C2
Ca
I
Iu
T
U
S
known triplets
1514
2013
843
1546
2242
2840
320
training
1358
2265
304
674
83
396
583
validation
86
143
20
43
26
37
testing
254
424
57
126
15
183
109
D.4 RESULTS ON SYNTHETIC WITH MISSING TRIPLETS
We randomly remove 5%, 10%, and 20% edges from synthetic datasets to test the robustness of QL-GNN and EL-GNN for rule structures learning. The results of QL-GNN and EL-GNN are shown respectively. The results show that the completeness of rule structure correlates strongly with the performance of QL-GNN and EL-GNN.
in Table 7 and &
Table 7: The accuracy of QL-GNN on synthetic datasets with missing triplets.
Triplet missing ratio
Cs
Ca
L
T
U
5%
0.899
0.866
0.760
0.783
0.556
0.329
10%
0.837
0.718
0.667
0.685
0.133
0.279
20%
0.523
0.465
0.532
0.468
0.111
0.162
21

---

Published as a conference paper at ICLR 2024
Table 8: The accuracy of EL.-GNN synthetic datasets with missing triplets.
Triplct missing ratio
C3
C4
11
12
T
U
5%
0.878
0.807
0.842
0.857
0.244
0.5
10%
0.766
0.674
0.725
0.661
0.222
0.347
20%
0.499
0,405
0.637
0.458
0.111
0.257
D.5
MORE EXPERIMENTAL DETAILS ON REAL DATASETS
MRR and Hit 10 Here we supplement MRR and Hit @ 10 of NBFNet and EL-NBFNet on real
datasets in Table 9 The improvement of EL-NBFNet MRR and @it@ 10 is not as significant as that on Accuracy because the EL-NBFNet is designed for exactly learning rule formulas and only Accuracy be guaranteed to be improved.
Table MRR and Hit@ 10 of NBENet and EL-NBFNet on real datasets.
Family
Kinship
UMLS
WNISRR
FB15k-237
MRR
Hit@ 10
MRR
Hit@10
MRR
Hit@10
MRR
Hit@
MRR
Hit@
NBFNet
0.983
0.993
0.900
0.997
0.970
0.997
0.548
0.657
0.415
0.599
EL-NBBNett
0.990
0,991
0.905
0.996
0.975
0.993
0.562
0.669
0.424
0.607
We have observed that a larger or smaller d does not necessarily lead to better performance in Figure 4 For real datasets, also observed similar phenomenon in Table I0 For real datasets, we uses d 5, 30, 100, 100, 300 for Family, Kinship, UMLS, WN1SRR, and FBT5k-237, respectively.
Different hyperparameters
Table 10: The accuracy of EL-NBENet on UMLS with different d.
d =
50
100
d = 150
NBFNet
0.948
0.958
0.963
0.961
0.951
Time cost of EL-NBFNet In Table 11 datasets. The time cost is measured by seconds of testing phase. The results show that EL-NBFNet slightly slower than NBFNet. The reason is that EL-NBFNet needs to traverse all entities on KG to assign constants to entities with out-degree larger than degree threshold
show the time cost of EL-NBINet and NBFNet on real
Table 11: Time cost (seconds of testing) of EL-NBFNet on real datasets.
Methods
Family
Kinship
UMLS
WN18RR
FB15k-237
EL-NBFNet 270.3
14.0
6.7
35.6
20.1
NBFNet 269.6
13.5
6.4
34.3
19.8
E THEORY OF GNNS FOR
LINK PREDICTION
Our theory of KG reasoning can be easily extended to the single-relational link prediction. The following two corollaries are the extensions of Theorem 3.2 and Theorem 3.4 to the single-relationll link prediction, respectively.
Corollary E.1 (Theorem 3n on single-relational link prediction). For single-relationa link prediction.
given a query (h, R, ?). a rule formula R(h, x)) is learned by QL-GNN if and only if R(h, x) is a formula in CMI. h).
22

---

Published as a conference paper at ICLR 2024
Corollary E.2 (Theorem 3.4 on single-relatioaal link prediction). For single-relational link prediction, CompGCN can learn the rule formula R(z. y) = =fR (()(())) (v)(1)))) where fR is a logical formula involving sub-formulas from {(p(z)} and {sp (y)} which are the sets of formulas in CML[G] that can be learned by GNN
Corollary and E.2 can be directly proven by restricting the logic of KG to single-relational graph, which means there is only one binary predicate in logic of graph.
F UNDERSTANDING GENERALIZATION BASED ON EXPRESSIVITY
F.1 UNDERSTANDING EXPRESSIVITY VS. GENERALIZATION
In this section, we provide some insights on the relation between expressivity and generalization. Expressivity in deep learning pertains to model's capacity to accurately represent information, whereas the ability of a model to achieve this level of expressivity depends on its generalization. Considering generalization requires not only contemplating the model design but also assessing whether the training algorithm can enable the model to achieve its expressivity. The experiments in this paper also show this relation about expressivity and generalization from two perspective: (1) The experimental results of QL-GNN shows that its expressivity can be achieved with classical deep learning training strategies; (2) In the development of deep learning, consensus is that more expressivity often leads to better generalization. The experimental results of EL-GNN verify this consensus.
In addition, our theory can provide some insights on model design with better generalization. Based on the constructive proof of Lemma C.3 if QL-GNN can learn rule formula R(h, x) with L recursive definition, QL-GNN can learn Rh, x) with layers and hidden dimensions no less than L. Assuming learning r relations with QL-GNN and numbers of recursive definition for these relations are L1. L.. ... L, respectively, QL-GNN can learn these relations with layers no more than mar; L; and hidden dimensions no more than Σ Li. Since these bounds are nearly worst-case scenarios, both the dimensions and layers can be further optimized. Also, in the constructive proof of Lemma C.3 the aggregation function is summation, and it is difficult for mean and max/min aggregation function to capture sub-formula 32 (R, x) A R(h, y)). From the perspective of rule learning, QL-GNN extracts structural information at each layer. Therefore, to learn rule structures, QL-GNN needs an activation function with compression capability for information extraction from inputs. Empirically, QL-GNN with identify activation function fails to learn with rules synthetic dataset.
Moreover, because theory cannot help understand generalization related to network training, the dependence to hyperparameters of network training, e.g., the number of training examples, graph size, number of entities, cannot be revealed from our theory.
F.2 WHY ASSIGNING LOTS OF CONSTANTS HURTS GENERALIZATION
We take the relation C3 as an example to show why assigning lots of constants hurts generalization from logical perspective. We add two different constants and C2 to the rule formula Ca(h, x). which results two different rule formulas (h, y) 3z, Rg (h, æ1) A Rg C1) A R3(c1, x) and (3,,,, y) 3z, R (h, 21) A R2 c2) A Rz(C2, x). Predicting new triplets for relation C3 can now be achieved by learning the rule formulas x)), (h x). or C% x). Among these rule formulas, Cs (h, .r) is the rule with the best generalization, while (h,, and C2 (h, require the rule structure to pass through the entities with identifiers of constants C and C2 respectively. Thus, when adding constants, maintaining performance requires the network to learn both rule formulas (h) C2 (h, ær) simultaneously which may potentially require a network with larger capacity. Even EL-GNN unnecessary learn C2 æ)), C2 (h, x) since C3(h, æ)) is learnable, EL-GNN cannot avoid learning rules with more than one constant in it when the rules are out of CML.
G LIMITATIONS AND IMPACTS
Our work offers fresh perspective understanding GNN's expressivity in KG reasoning. Unlike most existing studies that focus on distinguishing ability, we analyze GNN's expressivity based solely its ability to learn rule structures. Our work has the potential inspire further studies. For
23

---

Published as a conference paper at ICLR 2024
instance, theory analyzes GNN's ability to learn single relation, but in practice, GNNs are often applied to learn multiple relations. Therefore, determining the number of relations that GNNs can effectively learn for KG reasoning remains interesting problem that can help determine the size of GNNs. Furthermore, while our experiments are conducted on synthetic datasets without missing triplets, real datasets are incomplete (e.g., missing triplets in testing sets). Thus, understanding the expressivity of GNNs for KG reasoning on incomplete datasets remains an important challenge.
24


Reviews:
[{"review_id": "qiYdUFjgfs", "reviewer": "Reviewer_NwzR", "summary": "This paper which studies theoretical properties of GNN models includes:\n* Analysis of the expressiveness of GNN models in terms of a rule-learning formalism. \n* Presentation a simple yet effective labeling strategy based on their analysis that yields improvements. \n* Empirical analysis that supplements the theoretical contribution. The proposed approach instantiated with RED-GNN and NBFNet yields positive improvements across real and synthetic datasets.", "questions": "* Can you say more about how to think about generalization and expressivity in regards to the above comments?\n* Can you say more about Theorem 4.4 and \"The structural rules in Figure 2 cannot be learned by CompGCN due to Theorem 4.4.\"?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper leads a technical and thoughtful analysis to what kinds of relationships GNN-based models can effectively represent and effectively predict. Strengths of the paper include:\n* **Formalism** for link prediction in knowledge graphs using CML. This allows the authors to describe which kinds of rule structures each class of model is able to represent. It allows for the generalization of existing methods to represent broader classes of rules.\n* **Empirical Successes** are demonstrated across a wide variety of datasets. These seem to indicate different kinds of graph and entity / relation structures. \n* **Theoretical Analysis** appears to be rigorous and formally describe the different classes of rules and what models are effective for each.", "weaknesses": "My main concern with this paper is the presentation / structure and the way in which that presentation and structure limits the reader from connecting both the clear theoretical advantages of the proposed class of GNN to both the limitations of other classes and the empirical successes. Please correct me if you think I have misinterpreted or misunderstood things or put emphasis points inappropriately. I am mentioning these presentation points because I think the paper has a number of very nice properties that I would like readers to be able to more easily grasp and benefit from.\n\nW1. **Defining Expressivity** I think that the definition of expressivity used in the paper should be defined much earlier in the manuscript. I say this not only for the sake of readers unfamiliar with definitions of expressivity for GNNs but also for the sake of familiar readers understanding differences between the choice of expressivity definition and the choices of past work. The related work section, which appears before definitions of expressivity so far as I understand, provides too high level a comparison between past work to be meaningful (in my opinion) for all but the most familiar readers of these methods (as an aside, I think that the related work section as it is now would be better suited later in the paper, say before experiments). In my opinion, readers would benefit from explicitly talking about the relationship between generalization and representation of graphs immediately. \n\nW2. **Connecting Formalism and Data** While the formalism used is based on past work and as I understand motivated and accepted in those works as a meaningful formalism, I think that paper would be greatly improved with many more motivating examples from real data that express why the rule based formalism is meaningful. For instance, the example in Figure 1 is great. I see how it connects to Figure 3 and Corollary 5.2. However, how often do such patterns appear in the real world empirical datasets? How much of the gains from the given methods correlate with the existence of the kinds of subgraphs described? \n\nW3. **Understanding Generalization** I think my main point of confusion, which I was not able to resolve in my reading of the paper is how to think about generalization vs representation. As I understand it depends on which rules the model can learn. But I am having a hard time understanding how this relates to things like number of parameters, number of training examples, choice of aggregation functions, graph size, number of entities, number of relationships, etc. I am missing something fundamental here? E.g. How do number of examples / graph size / parameters relate to the base theorem C.2? Or do those things not matter in the analysis? It seems it depends only on $L$ is that correct?\n\nW4. **Presentation of some of the theoretical results** As a more minor point, I think readers would take away more from the theoretical results if the authors provided more remarks about the limitations/take aways from the theorem statements. For instance, I was confused about Theorem 4.4. For instance, I think I would have appreciated more handholding as to the result: \"The structural rules in Figure 2 cannot be learned by CompGCN due to Theorem 4.4.\"\n\nMy concern is that I think we need:\n (1) how the proposed formalism allows us to better analyze the generalization capabilities of models to understand why we would expect empirical successes\n (2) how the proposed formalism is reflected in real world datasets (e.g., the kinds of rule patterns indeed show up)\n (3) an understanding of why the proposed formalism and analysis is better than other forms of analysis that one could do. \nThese are certainly addressed by the paper, but I think that they could made significantly more crisp in the way the paper and results are presented.\n\nMinor:\n* I think the first sentence is missing an \"A\", \"A knowledge graph (KG) ...\"\n\nOther related work: \n* [Ego-Splitting Framework: from Non-Overlapping to Overlapping Clusters.](https://dl.acm.org/doi/10.1145/3097983.3098054)\n* [Neighborhood Growth Determines Geometric Priors for Relational Representation Learning](https://proceedings.mlr.press/v108/weber20a.html)\n* [What relations are reliably embeddable in Euclidean space?](https://arxiv.org/abs/1903.05347)", "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": "WOAOZhAF3I", "reviewer": "Reviewer_zRzb", "summary": "This paper proposes a novel perspective to understand the expressivity of recent GNNs for KG reasoning based on rule structure learning. It identifies the types of rule structures that different GNNs can learn and analyzes their advantages and limitations. It also introduces a unified framework, QL-GNN, that encompasses two SOTA GNNs, RED-GNN and NBFNet. Moreover, it presents a new labeling strategy based on QL-GNN, called EL-GNN, that can learn more rule structures. The paper validates the theoretical analysis and the effectiveness of QL-GNN and EL-GNN through experiments on synthetic and real datasets.", "questions": "- What about the performance of the proposed GNNs on FB15K-237?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a novel approach to understanding RED-GNN and NBFNet from a rule-learning perspective.\n\n- The theoretical analysis reveals the advantages and limitations of existing popular GNNs in KG reasoning. The paper also provides experimental results to support the theoretical conclusion. \n\n- Furthermore, the paper proposes two GNNs for KG reasoning, which outperform state-of-the-art models on several datasets.", "weaknesses": "- In my opinion, the datasets used in Section 6.2 appear to be well-suited for rule-based methods. However, the most popular link prediction dataset, FB15K-237, was not included in this experiment. Therefore, I believe that the experimental results of Section 6.2 are insufficient to evaluate the effectiveness of the proposed method.", "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": "YTOFgTKE6E", "reviewer": "Reviewer_S7Jh", "summary": "The paper delves into the domain of Knowledge Graph (KG) reasoning, which involves deducing new facts from existing ones in a KG. While Graph Neural Networks (GNNs) with tail entity scoring have recently achieved state-of-the-art performance in KG reasoning, there's a gap in the theoretical understanding of these GNNs. This work aims to bridge this gap by unifying GNNs with tail entity scoring into a common framework and analyzing their expressivity in terms of the rule structures they can learn. The insights from this analysis lead to the proposal of a novel labeling strategy to further enhance rule structure learning in KG reasoning. Experimental results support the theoretical findings and demonstrate the effectiveness of the proposed method.", "questions": "Q1 Can the models trained on one KG be adapted or fine-tuned for another KG? If so, are there any specific considerations or challenges in doing so?\n\nQ2 How robust are QL-GNN and EL-GNN to noisy or incomplete data in KGs? Have any tests been conducted to assess their performance under such conditions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1 The paper provides a thorough analysis of the expressivity of state-of-the-art GNNs used for KG reasoning. By unifying these GNNs into a common framework (QL-GNN), the authors offer a structured approach to understanding their capabilities and limitations in terms of rule structure learning.\nS2 The introduction of the QL-GNN framework and the subsequent EL-GNN model showcases the authors' innovative approach to addressing the gaps in the current understanding of GNNs for KG reasoning. The EL-GNN, in particular, is designed to learn rule structures beyond the capacity of existing methods, marking a significant advancement in the field.\nS3 The authors don't just rely on theoretical findings; they validate their claims with experiments on synthetic datasets. The consistency between the experimental results and theoretical insights adds credibility to their claims and demonstrates the practical applicability of their proposed methods.", "weaknesses": "W1  While the EL-GNN model is introduced as an improvement over QL-GNN, there's limited discussion on its scalability. How does EL-GNN perform when applied to very large-scale KGs? Are there any computational constraints or challenges that users should be aware of? Moreover, the experiments in the paper employ relatively small datasets. It would greatly benefit the research to include larger datasets to demonstrate the effectiveness of the proposed methods on a more substantial scale.\n\nW2 The paper introduces a novel labeling strategy to enhance rule structure learning. Are there specific scenarios in which this labeling strategy may not yield effective results or encounter limitations?", "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": "8bUNL8msce", "reviewer": "Reviewer_TfWh", "summary": "In this paper, the authors investigate the expressivity of GNN-based KG reasoning methods. The paper provides terminology for rule structure in the KG reasoning task and proves the limitation of current methods in structure rules T(h,x) and U(h,x) in theory. For the method, In algo 1, the initial representation is assigned to the entities whose out-degree is larger than a threshold d. The proposition 5.1 and the empirical results in Table 1 show that the proposed method can help discover structure rules T(h,x) and U(h,x).", "questions": "In page 7, it mentioned \" the additional time complexity introduced by entity labeling is linear with respect to the number of entities in the graph,  which is marginal in comparison to QL-GNN\". I am not sure about why is marginal considering the KG is usually large. Could you provide the numeric value about time cost for the experiments or adding more discussion?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The novelty is great, this paper provides a systematic way for rule structures finding in GNN based KG reasoning task.\n- The theoretical part is sound, and the experimental study supports the theoretical result as well.\n- The method is simple that assigning the initial representation to the entities but effective based on experimental results.", "weaknesses": "n/a", "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)