# Logical Expressiveness of Graph Neural Network
for Knowledge Graph Reasoning

Haiquan Qiu  Yongqi Zhang  Yong Li  Quanming Yao

###### Abstract

Graph Neural Networks (GNNs) have been recently introduced to learn from
knowledge graph (KG) and achieved state-of-the-art performance in KG
reasoning. However, a theoretical certification for their good empirical
performance is still absent. Besides, while logic in KG is important for
inductive and interpretable inference, existing GNN-based methods are just
designed to fit data distributions with limited knowledge of their logical
expressiveness. We propose to fill the above gap in this paper. Specifically,
we theoretically analyze GNN from logical expressiveness and find out what
kind of logical rules can be captured from KG. Our results first show that GNN
can capture logical rules from graded modal logic, providing a new theoretical
tool for analyzing the expressiveness of GNN for KG reasoning; and a query
labeling trick makes it easier for GNN to capture logical rules, explaining
why SOTA methods are mainly based on labeling trick. Finally, insights from
our theory motivate the development of an entity labeling method for capturing
difficult logical rules. Experimental results are consistent with our
theoretical results and verify the effectiveness of our proposed method.

##  1 Introduction

Knowledge graph (KG) is graph-structured data that connects artificial
intelligence with human knowledge by representing real-world entities and
their relationships in a structured way. By encapsulating the interactions
among entities, KGs provide a way for machines to understand and process
complex information. In this paper, we focus on KG reasoning which deduces new
facts from the existing facts in KG. KG reasoning has led to the widespread
use of KGs in a variety of applications, e.g., drug discovery (Mohamed et al.,
2019), personalized recommendation (Cao et al., 2019), and question answering
(Abujabal et al., 2018), etc.

There are many methods proposed for KG reasoning over the last decade, which
can be grouped into three categories: embedding-based methods (Bordes et al.,
2013; Trouillon et al., 2016), rule-based methods (Richardson & Domingos,
2006; Yang et al., 2017; Sadeghian et al., 2019), and GNN-based methods
(Schlichtkrull et al., 2018; Zhu et al., 2021; Zhang & Yao, 2022). Among them,
GNN-based methods have superior performance over the other methods due to its
ability of automatically extracting important features from graphs. According
to Zhang et al. (2021), GNN methods for KG reasoning can be mainly divided
into two categories: entity-representation-aggregation GNN (Schlichtkrull et
al., 2018; Vashishth et al., 2020) and labeling-trick GNN (Teru et al., 2020;
Zhu et al., 2021; Zhang & Yao, 2022). However, the good empirical performance
of GNNs is not well understood theoretically. While there has been some
progress in understanding the expressiveness (Xu et al., 2019; Li et al.,
2020; Zhang et al., 2021) of GNN to justify its good performance, most of
these works are based on either strong assumptions (e.g., isomorphism nodes or
links in graph (Xu et al., 2019; Zhang et al., 2021)) or toy examples (e.g.,
regular graph (Li et al., 2020)). Therefore, it is difficult to analyze GNN
for KG reasoning with the results from these works.

Meanwhile, logic in KG is a powerful tool for both inductive and interpretable
KG reasoning (Lavrac & Dzeroski, 1994; Richardson & Domingos, 2006; Yang et
al., 2017; Sadeghian et al., 2019; Qu & Tang, 2019). With entities and
relationships represented by logic, it is possible to reason and draw
conclusions based on existing facts in KG and bring knowledge to machines.
Rule-based methods for KG reasoning are based on logic, which either utilize
predefined rules (Lavrac & Dzeroski, 1994; Richardson & Domingos, 2006; Qu &
Tang, 2019) or learn a logical rule based on predefined structures (Yang et
al., 2017; Sadeghian et al., 2019). Although logic is a powerful tool for KG
reasoning, most existing GNN-based methods do not take it into account, and
they instead rely on techniques from graph isomorphism testing to improve
expressiveness. However, the analysis based on graph isomorphism testing is
not well-suited for fine-grained rule structure analysis of GNN for KG
reasoning since it relies on automorphism links or regular graphs. On the
other hand, due to the close connection between logic and KG reasoning,
analyzing the expressiveness of GNN from the logical perspective could provide
valuable tools for evaluating existing GNNs for KG reasoning and improving
their empirical performance.

In this paper, we fill the gap between GNN and logic in KG by theoretically
analyzing logical expressiveness of GNN for KG reasoning. We aim to find out
what kind of logical rules can be captured by GNN for KG reasoning. The
analysis helps better understand existing methods and motivates future design
directions on GNN for KG reasoning.

First, we show that logical rules from graded modal logic (De Rijke, 2000;
Otto, 2019) can be encoded into GNN representations, which serves as the
fundamental theory for analyzing the logical expressiveness of GNN for KG
reasoning. Then, we analyze the logical expressiveness of two categories of
GNNs for KG reasoning. For Entity-Representation-Aggregation GNN (ERA-GNN),
our theory shows that it has limited logical expressiveness because the
logical rules, where head and tail entities are connected in their rule
structures, cannot be captured. For labeling-trick GNN, we identify an
important subclass of GNN that assigns label to the query entity. This
subclass of GNN is called Query-Labeling GNN (QL-GNN) in our paper, which
includes existing state-of-the-art methods, e.g., NBFNet (Zhu et al., 2021)
and RED-GNN (Zhang & Yao, 2022). Our theory shows that the query labeling
trick in QL-GNN makes it easier to capture logical rules and provides insights
about why NBFNet and RED-GNN are particularly effective at KG reasoning.
Finally, for rules that cannot be captured by QL-GNN, we propose an entity
labeling method to transform these rules to be capturable with special initial
features of GNN. In summary, our paper has the following contributions:

  * •

Our work is the first to introduce logical expressiveness into GNNs for KG
reasoning, which provides new theoretical tools for analyzing their
expressiveness.

  * •

We answer the question of what kind of logical rules can be captured by two
classes of GNNs respectively, and give insights into why NBFNet and RED-GNN
are good at KG reasoning.

  * •

Our theory provides a way for transforming difficult logical rules to be
capturable. Based on our theory, we propose an entity labeling method to
improve the performance of learning difficult logical rules.

  * •

Synthetic datasets are generated to evaluate various GNNs, whose experimental
results are consistent with our theory. Also, results of the proposed labeling
method show improved performance on both synthetic and real datasets.

##  2 Related Works

###  2.1 Graph Neural Network (GNN)

Let $G=(\mathcal{V},\mathcal{E},\mathcal{R})$ be a heterogeneous graph where
$\mathcal{V},\mathcal{E},\mathcal{R}$ are sets of nodes, edges and relations
of graph respectively, and $\mathbf{e}_{v}^{0}$ be node feature vectors for
$v\in\mathcal{V}$. Graph neural network (GNN) (Kipf & Welling, 2016; Gilmer et
al., 2017) with $L$ layers is a type of neural network that uses graph $G$ and
node features $\mathbf{e}_{v}^{0}$ to learn node representations
$\mathbf{e}_{v}^{L},v\in\mathcal{V}$. GNN uses message-passing mechanisms to
propagate information between nodes in a graph. The $k$-th layer of GNN
updates the node representation via the following message-passing formula

$\displaystyle\mathbf{e}_{v}^{k}=\delta\Big{(}\mathbf{e}_{v}^{k-1},\phi\left(\\{\\{\psi(\mathbf{e}_{u}^{k-1},R),u\in\mathcal{N}_{R}(v)\\}\\}\right)\Big{)},$
(1)

where $\delta$ and $\phi$ are combination and aggregation functions
respectively, $\psi$ is the message function encoding the relation $R$ and
node $u$ neighboring to $v$, $\\{\\{\cdots\\}\\}$ is a multiset, and
$\mathcal{N}_{R}(v)$ is the entity set $\\{u|(u,R,v)\in\mathcal{F}\\}$.

Since GNN has shown good performance on a wide range of tasks involving graph-
structured data, many existing work try to analyze the expressiveness of GNN.
Most of these works analyze the expressiveness with tools from graph
isomorphism testing. A well-known result (Xu et al., 2019) shows that the
expressiveness of vanilla GNN is limited to Weisfeiler-Lehman (WL) test. To
improve the expressiveness of GNNs, most of the existing works either utilize
GNNs motivated by high-order WL test (Morris et al., 2019, 2020) or apply
special initial features to improve the expressiveness of GNN (Abboud et al.,
2021; You et al., 2021; Sato et al., 2021; Zhang et al., 2021).

Except for using graph isomorphism testing, Barceló et al. (2020) analyzes the
expressiveness of GNN with logic and identifies that the logical rules from
graded modal logic can be captured by vanilla GNN. However, their analysis is
limited to node classification on the homogenous graph.

Figure 1: Examples of three relations investigated in our paper. “Logical
rule” shows the logical formula of the corresponding relation, i.e., new facts
about a relation in the figure can be predicted by the corresponding logical
rules. “Rule structure” is the topology structure in KG which can help deduce
new facts about the corresponding relation. “Example” shows the instantiation
of rule structure in the figure and corresponding new fact.

###  2.2 GNN for knowledge graph reasoning

Knowledge graph (KG) reasoning uses KG, i.e.,
$\mathcal{K}=(\mathcal{V},\mathcal{F},\mathcal{R})$ where
$\mathcal{V},\mathcal{F},\mathcal{R}$ are the sets of entities, triplets and
relations respectively, to predict new facts based on known ones. Facts in KG
are represented as interactions or relationships between entities. These
interactions 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
$R$. KG reasoning can be modeled as the process of predicting the tail entity
$t$ of a query in the form $(h,R,?)$. Existing methods for KG reasoning can be
roughly divided into three classes: embedding-based methods (Bordes et al.,
2013), rule-based methods (Lavrac & Dzeroski, 1994; Sadeghian et al., 2019),
and GNN-based methods (Schlichtkrull et al., 2018; Zhu et al., 2021). Among
the above methods, GNN-based ones achieve the state-of-the-art performance.

GNN-based methods can be divided into two classes, i.e., Entity-
Representation-Aggregation GNN (ERA-GNN) (Schlichtkrull et al., 2018) and
Labeling-Trick GNN (LT-GNN) (Teru et al., 2020; Zhu et al., 2021). ERA-GNN
first applies GNN to transform the initial features of each entity to get the
entity representation $\mathbf{e}_{v}^{L},v\in\mathcal{V}$ and then utilizes
representations $\mathbf{e}_{h}^{L},\mathbf{e}_{t}^{L}$ to calculate the score
of potential new facts $(h,R,t)$. Many GNN methods for KG reasoning belong to
ERA-GNN, such as RGCN (Schlichtkrull et al., 2018) and CompGCN (Vashishth et
al., 2020). For example, CompGCN belongs to ERA-GNN since it calculates the
score of a triplet with
$s(h,R,t)=-\|\mathbf{e}_{h}^{L}+\mathbf{e}_{R}-\mathbf{e}_{t}^{L}\|$ with
relation embedding $\mathbf{e}_{R}$.

LT-GNN first assigns special initial features to entities in KG by the
labeling trick, then applies GNN to get the entity representation
$\mathbf{e}_{v}^{L},v\in\mathcal{V}$ which is used to calculate the score for
each candidate triplet. For example, GraIL (Teru et al., 2020) belongs to LT-
GNN because the entity features is initialized with Distance Encoding (Zhang &
Chen, 2018); the state-of-the-art GNN-based methods, e.g., NBFNet (Zhu et al.,
2021) and RED-GNN (Zhang & Yao, 2022), belong to GNN with partial labeling (a
subclass of LT-GNN), which only assigns special initial feature to the query
entity. LT-GNN achieves the state-of-the-art performance in KG reasoning.
However, there still lacks a theoretical certification for their good
empirical performance.

##  3 Logic of Knowledge Graph

Motivated by previous works on graph theory and logic (Cai et al., 1992;
Barceló et al., 2020), we consider the first-order logic with counting (FOC)
which is an extension of first-order logic by adding the counting quantifier
$\exists^{\geq N}$.

FOC of KG represents and reasons about KG using a formal logic language, where
the entities in KG are represented as logical variables, and the relations are
represented as binary predicates over these variables. The formulas in FOC of
KG can be used to express constraints on the KG structure and to reason about
KG with logical inference.

First, we introduce how entities and relations are modeled in FOC of KG. To
model entities in KG, we use lowercase italic letters $x,y,z$ to denote
logical variables which can represent an entity or a class of entities in KG.
To describe property of entities in KG, the unary predicate $P_{i}(x)$ is
introduced. For example, $\texttt{red}(x)$ is a unary predicate indicating if
an entity is colored with red. In addition, lowercase letters
$\mathsf{h},\mathsf{c}$ with sans serif typestyle are used to denote constants
in KG which are unique identifiers of entities. A constant $\mathsf{c}$ can be
transformed into a unary predicate $P_{c}(x)$ which is called constant
predicate in our paper. In this way, if a constant predicate $P_{c}(x)$ is
satisfied at an entity $v$, it means that $v$ can be uniquely identified by
the constant $\mathsf{c}$.

To model relations in KG, binary predicates $R_{j}(x,y)$ are introduced to
logically model the relation $R_{j}$ between entities. Therefore, an
equivalent logical formula of relation $R_{j}$ can help to predict new facts
in KG reasoning. If the binary predicate $R_{j}(x,y)$ is satisfied at two
entities $h,t$, there must exist a relation $R_{j}$ between entities $h,t$,
i.e., $(h,R_{j},t)\in\mathcal{F}$. For example, a binary predicate
$\texttt{father}(x,y)$ satisfied at two entities $h,t$ shows that $h$ is the
father of $t$. Other symbols in FOC of KG include logical connectives
$\wedge,\neg$ denoting conjunction and negation respectively, symbol $\top$
representing True, universal quantifier $\forall$ representing “for all”, and
counting quantifier $\exists^{\geq N}$ expressing the statements about the
number of objects satisfying a given condition.

In the above definition, the assignment of constants is optional in FOC of KG.
To discriminate FOC with or without constants, we denote
$\text{FOC}[\mathcal{K}]$ as FOC of $\mathcal{K}$ without assignment of
constants, and
$\text{FOC}[\mathcal{K},\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}]$
as FOC of $\mathcal{K}$ assigned with constants
$\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}$. Constants play an
important role in our analysis because they can be combined with predicates.
When combined with a constant $\mathsf{c}$, $P_{i}(\mathsf{c})$ and
$R_{j}(\mathsf{c},x)$ are equivalent to logical formulas $\exists
y,P_{i}(y)\wedge P_{c}(y)$ and $\exists y,R_{j}(y,x)\wedge P_{c}(y)$
respectively. Given a query $(h,R_{j},?)$ in KG reasoning, new facts with
relation $R_{j}$ can be predicted with the equivalent logical formula of
$R_{j}(x,y)$ or $R_{j}(\mathsf{h},x)$. For example, the new fact $(h,C,t)$
with relation $C$ in Figure 1 can be deduced from the logical rule $C(x,y)$
which is a formula in $\text{FOC}[\mathcal{K}]$, or from the logical rule
$C(\mathsf{h},x)$ which is a formula in $\text{FOC}[\mathcal{K},\mathsf{h}]$.
If the triplet $(h,C,t)$ exists in KG, we should have $C(x,y)$ satisfied at
$(h,t)$ or $C(\mathsf{h},x)$ satisfied at $t$.

Compared with previous work (Barceló et al., 2020) on homogenous graphs, FOC
of KG can be seen as FOC defined on heterogeneous graphs, and we consider
constants in FOC of KG which play an important role in the logical
expressiveness of GNN for KG reasoning.

##  4 Logical Analysis of GNN Representation

Before giving the logical results for KG reasoning, we first analyze the
logical expressiveness of entity representations obtained by GNN since GNN for
KG reasoning predicts new facts based on the GNN entity representations. We
will find out what kind of logical rules can be captured 111A logical formula
$\phi(x)$ is captured by GNN representation means that the GNN representation
contains information about whether $\phi(x)$ is satisfied at the entities in
KG.  by entities’ representations from GNNs, i.e., find out what kind of
logical rules can be implicitly encoded into the entities’ representations.

As GNN is not a universal approximator (Xu et al., 2019, 2020; Barceló et al.,
2020), some formulas in FOC cannot be captured by GNNs. For the node
classification on homogenous graph, Barceló et al. (2020) identifies a
subclass of FOC called graded modal logic (De Rijke, 2000; Otto, 2019) which
can be captured by GNN. Thus, for KG (heterogeneous graph), our logical
analysis will also focus on graded modal logic of KG which is the Counting
extension of Modal Logic (CML). The formulas in CML of KG can be recursively
defined in the following sub-formulas

$\displaystyle\begin{split}\top,\;&P_{i}(x),\;\neg\varphi(x),\;\varphi_{1}(x)\wedge\varphi_{2}(x),\\\
&\exists^{\geq N}y\left(R_{j}(y,x)\wedge\varphi(y)\right),\end{split}$ (2)

where $\top$ is satisfied at all entities, $P_{i}(x)$ is atomic unary
predicate, $\varphi(x),\varphi_{1}(x),\varphi_{2}(x)$ are sub-formulas in CML
and $\exists^{\geq N}y\left(R_{j}(y,x)\wedge\varphi(y)\right)$ allows to check
the property of neighbor $y$ of entity variable $x$.

Since CML is a subset of FOC, we have similar notations to represent CML of
KG, namely, $\text{CML}[\mathcal{K}]$ denotes CML of a KG $\mathcal{K}$
without constant, and
$\text{CML}[\mathcal{K},\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}]$
denotes CML of a KG $\mathcal{K}$ with constants
$\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}(k\geq 1)$. Then, we give
the following theorem to connect GNN representation and formulas in CML.

######  Theorem 4.1.

In a knowledge graph, a logical rule $\varphi(x)$ is captured by the
representations of GNN in Eq.(1) on the knowledge graph if and only if the
logical rule $\varphi(x)$ is a formula in CML of the knowledge graph.

The proof of Theorem 4.1 is in Appendix C. Our theorem can be seen as an
extension of Theorem 4.2 in Barceló et al. (2020) to KG (heterogeneous graph).
Similarly, our theorem talks about the ability to implicitly capture logical
rules by the GNN representations rather than explicitly extracting rules,
which is future work. It shows that CML of KG is the tightest subclass of FOC
that GNN can capture. The following two remarks intuitively explain how GNN
can capture formulas in CML.

######  Remark 4.2.

Theorem 4.1 applies to both $\text{CML}[\mathcal{K}]$ and
$\text{CML}[\mathcal{K},\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}]$.
The atomic unary predicate $P_{i}(x)$ in CML of KG is captured by the initial
features $\mathbf{e}_{v}^{0},v\in\mathcal{V}$, which can be achieved by
assigning special vectors to $\mathbf{e}_{v}^{0},v\in\mathcal{V}$. In
particular, the constant predicate $P_{c}(x)$ in
$\text{CML}[\mathcal{K},\mathsf{c}]$ is captured by assigning a unique vector
(e.g., one-hot vector for different entities) as the initial feature of the
entity identified by $\mathsf{c}$. The other sub-formulas
$\neg\varphi(x),\varphi_{1}(x)\wedge\varphi_{2}(x)$ in (2) can be captured by
continuous logical operations (Arakelyan et al., 2021) which are independent
of message-passing mechanisms.

######  Remark 4.3.

Assume the $(i-1)$-th layer representations
$\mathbf{e}_{v}^{i-1},v\in\mathcal{V}$ can capture the formula $\varphi(x)$ in
CML, the $i$-th layer representations $\mathbf{e}_{v}^{i},v\in\mathcal{V}$ of
GNN can capture $\exists^{\geq N}y,R_{j}(y,x)\wedge\varphi(y)$ with specific
aggregation function in (1) because $\mathbf{e}_{v}^{i},v\in\mathcal{V}$ can
aggregate the logical rules in the one-hop neighbor representation
$\mathbf{e}_{v}^{i-1},v\in\mathcal{V}$ (i.e., $\varphi(x)$) with message-
passing mechanisms.

Next, we will use Theorem 4.1 to analyze the logical expressiveness of various
GNN methods for KG reasoning.

Table 1: This table shows whether the GNNs investigated in our paper can capture the logical rules in Figure 1 and the exemplar methods of these GNNs. ✓ means the corresponding GNN can capture the logical rule, thus can help predict new facts involving corresponding relation. ✗ means the corresponding GNN cannot capture the logical rule. Relation type | $C$ | $I$ | $U$ | Exemplar Method
---|---|---|---|---
Logical rule | $C(x,y)$ | $C(\mathsf{h},x)$ | $I(\mathsf{h},x)$ | $U(\mathsf{h},x)$ | $U^{\prime}(\mathsf{h},x)$
ERA-GNN | ✗ | ✗ | ✗ | ✗ | ✗ | R-GCN,CompGCN
QL-GNN | ✗ | ✓ | ✓ | ✗ | ✗ | NBFNet,RED-GNN
EL-GNN | ✗ | ✓ | ✓ | ✗ | ✓ | Ours

##  5 Logical expressiveness of GNN for KG Reasoning

Here, we analyze the logical expressiveness of two main types of GNN-based KG
reasoning methods, i.e., ERA-GNN in Section 5.1 and QL-GNN in Section 5.2. In
Section 5.3, we present some logical rules in Figure 1 to analyze the
expressiveness of ERA-GNN and QL-GNN.

###  5.1 Logical expressiveness of ERA-GNN

Given a KG, ERA-GNN (e.g., R-GCN, CompGCN) first applies (1) to compute the
entity representations $\mathbf{e}_{v}^{L},v\in\mathcal{V}$. Then for a query
$(h,R,?)$, the score $s(h,R,t)$ for candidate $(h,R,t)$ with each
$t\in\mathcal{V}$ is calculated by aggregating the entity representations
$\mathbf{e}_{h}^{L},\mathbf{e}_{t}^{L}$. Representative functions for entity
aggregation are TransE (Bordes et al., 2013) and ComplEx (Trouillon et al.,
2016), etc. For example, CompGCN can use the score function
$s(h,R,t)=-\|\mathbf{e}_{h}^{L}+\mathbf{e}_{R}-\mathbf{e}_{t}^{L}\|$ with
relation embedding $\mathbf{e}_{R}$. If the triplet $(h,R,t)$ is in KG, the
value of $s(h,R,t)$ is optimized to be larger than the non-existing triplets.

From Theorem 4.1, the entity representation $\mathbf{e}_{v}^{L}$ can capture
some formula $\phi(x)$ in $\text{CML}[\mathcal{K}]$ at $v$. In KG reasoning,
if ERA-GNN can capture the logical rule $R(x,y)$, the score $s(h,R,t)$ should
be able to determine whether $R(x,y)$ is satisfied at $h,t$ for candidate
triplet $(h,R,t)$. Thus, when calculating the score, the arithmetic operation
between $\mathbf{e}_{h}^{L}$ and $\mathbf{e}_{t}^{L}$ represents some logical
operations connecting the formulas in CML at entities $h$ and $t$. With the
above analysis, we have the following theorem of the logical expressiveness
for ERA-GNN.

######  Theorem 5.1 (Logical expressiveness of ERA-GNN).

For KG reasoning, ERA-GNN can capture the logical rule
$R(x,y)=f_{R}\left(\\{\phi_{i}(x)\\},\\{\psi_{j}(y)\\}\right)$ where $f_{R}$
is a logical formula involving sub-formulas from $\\{\phi_{i}(x)\\}$ and
$\\{\psi_{j}(y)\\}$ which are the sets of formulas in
$\text{CML}[\mathcal{K}]$ that can be captured by GNN representations.

Theorem 5.1 (proved in Appendix C) indicates that ERA-GNN is only capable of
learning logical rules $R(x,y)$ where $x$ and $y$ are independent. An
important class of relation belonging to this kind of logical rule describes
the similarity between two entities, e.g., $\texttt{same\\_color}(x,y)$
describing entities with the same color. However, relations involving
dependent head and tail entities are more commonly seen in KG reasoning
(Lavrac & Dzeroski, 1994; Sadeghian et al., 2019). For example, the relations
shown in Figure 1 involve dependent head and tail entities and cannot be
captured by ERA-GNN due to Theorem 5.1. Previous work on homogenous graph
(Zhang et al., 2021) says that there are many non-isomorphic links that ERA-
GNN cannot distinguish while our paper provides a fine-grained analysis for
heterogeneous graph (KG) which specifies which kind of logical rules can be
captured by ERA-GNN.

###  5.2 Logical expressiveness of QL-GNN

Given a query $(h,R,?)$, QL-GNN (a subclass of LT-GNN, e.g., NBFNet and RED-
GNN) assigns label to the query entity $h$, aggregates entity representations
$\mathbf{e}_{t}^{L}[\mathsf{h}]$ for each candidate $t\in\mathcal{V}$
depending on $h$, and scores a candidate triplet $(h,R,t)$ with tail entity
representation $\mathbf{e}_{t}^{L}[\mathsf{h}]$. For example, NBFNet uses the
score function $s(h,R,t)=\text{FFN}(\mathbf{e}_{t}^{L}[\mathsf{h}])$ where
$\text{FFN}(\cdot)$ denotes a feed-forward neural network.

From the logical perspective, the label assigned to query entity is denoted as
constant $\mathsf{h}$ or equivalently converted to a constant predicate
$P_{h}(x)$ in KG. In QL-GNN, the assigned constant is transformed into a
unique initial feature $\mathbf{e}_{h}^{0}$ to indicate that $h$ is the head
entity of the query. Then, QL-GNN applies GNN (1) to get the representations
$\mathbf{e}_{t}^{L}[\mathsf{h}],t\in\mathcal{V}$. With the constant
$\mathsf{h}$, the logical rule behind $(h,R,?)$ becomes a rule in the form of
$R(\mathsf{h},x)$. Then, we obtain the following theorem immediately from
Theorem 4.1.

######  Theorem 5.2 (Logical expressiveness of QL-GNN).

For KG reasoning, given query $(h,R,?)$, a logical rule $R(\mathsf{h},x)$ is
captured by QL-GNN if and only if the logical rule $R(\mathsf{h},x)$ is a
formula in $\text{CML}[\mathcal{K},\mathsf{h}]$.

From Theorem 5.2(proved in Appendix C), QL-GNN transforms logical rules
$R(x,y)$ to a rule $R(\mathsf{h},x)$ in $\text{CML}[\mathcal{K},\mathsf{h}]$
by introducing the constant $\mathsf{h}$. Then based on Theorem 4.1, the
common logical rules, where $x$ and $y$ are dependent on each other, can be
captured by QL-GNN with constant $\mathsf{h}$ but cannot be captured by ERA-
GNN, meaning that QL-GNN is more powerful than ERA-GNN.

The analysis for GNN-based methods with general labeling trick goes beyond our
theoretical tools. For example, for a candidate triplet $(h,R,t)$, Distance
Encoding (Zhang & Chen, 2018) in GraIL is equivalent to assigning constants
$\mathsf{h},\mathsf{t}$ to entities $h,t$. Thus, GraIL actually learns a
sentence $R(\mathsf{h},\mathsf{t})$ in
$\text{FOC}[\mathcal{K},\mathsf{h},\mathsf{t}]$. However, our analysis shows
that query labeling is an important subclass of labeling trick for KG
reasoning. In Section 6, our work provides a tool for fine-grained analysis
(compared to isomorphism) of the structures of KG reasoned by QL-GNN and gives
insights on how to assign entity labels with labeling trick.

###  5.3 Case analysis

Here, we use representative logical rules in Figure 1 to investigate the
logical expressiveness of GNN for KG reasoning and summarize the results of
case analysis in Table 1.

The chain-like rule is a basic logical rule investigated in many previous
works (Sadeghian et al., 2019; Teru et al., 2020; Zhu et al., 2021). With
Theorem 5.1, $C(x,y)$ in Figure 1(a) cannot be decomposed into two sets of
logical formulas involving $x$ and $y$ separately, and thus cannot be captured
by ERA-GNN. On the other hand, QL-GNN assigns a constant $\mathsf{h}$ to the
query entity $h$, thus the new facts about relation $C$ can be predicted by
learning the logical rule $C(\mathsf{h},x)$ in Figure 1(a). With Theorem 5.2,
$C(\mathsf{h},x)$ is a formula in $\text{CML}[\mathcal{K},\mathsf{h}]$
(Corollary B.2 in Appendix B) and thus can be captured by QL-GNN. Hence, our
theory gives a general theoretical tool to determine if a GNN-based method can
capture the chain-like rule.

Figure 2: The division of different relations $R$ between two entities $h,t$
on KG. It shows the scope of relations that can be handled by various GNN
methods investigated in our paper.

The second logical rule $I(\mathsf{h},x)$ in Figure 1(b) is composed of a
chain-like structure along with two additional entities with variable $z_{3}$
connected to an entity with variable $z_{2}$ and is a formula in
$\text{CML}[\mathcal{K},\mathsf{h}]$ (Corollary B.3 in Appendix B), and thus
can be captured by QL-GNN with Theorem 5.2. $I(\mathsf{h},x)$ has never been
analyzed in any previous work, and we find that similar structures play an
important role in the inductive KG reasoning, i.e., KG reasoning task with
unseen entities in the inference. $I(\mathsf{h},x)$ can improve the
performance of inductive KG reasoning because two edges with relation $R_{4}$
are connected to an entity with variable $z_{2}$ and can help infer the
entity’s property. In fact, using edges to infer the entity property is a
common idea in inductive graph learning tasks, e.g., Galkin et al. (2022)
learns representations of unseen entities based on the edges that are
connected to it. The result in our paper is the first to provide a theoretical
tool to analyze why some GNN-based methods (e.g., NBFNet, RED-GNN) are good at
inductive KG reasoning.

In summary, we visualize the analysis of ERA-GNN and QL-GNN in Figure 2. As we
can see, ERA-GNN (in blue), such as R-GCN and CompGCN, can only handle
relations with independent head and tail entities which are described with the
logical rule in the form of $R(x,y)=f(\\{\phi_{i}(x)\\},\\{\psi_{j}(y)\\})$
with $\phi_{i}(x),\psi_{j}(y)$ in $\text{CML}[\mathcal{K}]$, while QL-GNN (in
green), such as NBFNet and RED-GNN, can learn the relations with dependent
head and tail entities which can be described with formulas in the form of
$R(\mathsf{h},x)$ in $\text{CML}[\mathcal{K},\mathsf{h}]$.

##  6 A Labeling Method for Difficult Rules

The logical expressiveness in Section 5.2 shows that QL-GNN can capture the
logical rule $R(\mathsf{h},x)$ in $\text{CML}[\mathcal{K},\mathsf{h}]$ for KG
reasoning, e.g., $C(\mathsf{h},x)$ and $I(\mathsf{h},x)$. However, it is well-
known that CML has limited expressiveness for describing graphs. Specifically,
any formula in CML cannot distinguish the counting bisimilar graph structures
(Blackburn et al., 2001; Otto, 2019), which means the counting bisimilar graph
structures cannot be distinguished by QL-GNN. For example, the rule structure
of relation $U$ in Figure 1(c) and the rule structure in Figure 3 are counting
bisimilar, thus can not be distinguished by QL-GNN. Furthermore, the logical
rule $U(\mathsf{h},x)$ is a formula in $\text{FOC}[\mathcal{K},\mathsf{h}]$
rather than $\text{CML}[\mathcal{K},\mathsf{h}]$, meaning that
$U(\mathsf{h},x)$ cannot be captured by QL-GNN based on Theorem 5.2. To
resolve this limitation, we propose a labeling method to improve the empirical
performance of QL-GNN when learning difficult rules.

Figure 3: An exemplar rule structure that is counting bisimilar to the rule
structure of relation $U$ in Figure 1(c).

The motivation behind our method is to transform difficult rules into formulas
in CML by adding constants to KG. Basically, assigning constants to entities
with an out-degree large than one is enough to achieve this purpose due to the
following theorem.

######  Theorem 6.1.

Assume $R(\mathsf{h},x)$ in $\text{FOC}[\mathcal{K},\mathsf{h}]$ describes a
single-connected rule structure $\mathsf{G}$ in $\mathcal{K}$. If we assign
constants $\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}$ to entities
with out-degree larger than 1 in $\mathcal{K}$, the rule structure
$\mathsf{G}$ can be described with $R^{\prime}(\mathsf{h},x)$ in
$\text{CML}[\mathcal{K},\mathsf{h},\mathsf{c}_{1},\mathsf{c}_{2},\cdots,\mathsf{c}_{k}]$.

With Theorem 6.1, when encoding the constants into the initial features of
GNN, the logical rule $R^{\prime}(\mathsf{h},x)$ can be captured by QL-GNN
along with the assigned constants due to Theorem 4.1. For example, when
assigning constant $\mathsf{c}$ to the entity colored with gray in the rule
structure of relation $U$ in Figure 1(c), a new logical rule

$\displaystyle U^{\prime}(\mathsf{h},x):=$ $\displaystyle
R_{1}(\mathsf{h},\mathsf{c})\wedge\big{(}\exists
z_{2},z_{3},R_{2}(\mathsf{c},z_{2})$ $\displaystyle\wedge R_{4}(z_{2},x)\wedge
R_{3}(\mathsf{c},z_{3})\wedge R_{5}(z_{3},x)\big{)}$

in $\text{CML}[\mathcal{K},\mathsf{h},\mathsf{c}]$ (Corollary B.4 in Appendix
B) can describe the rule structure in Figure 1(c). Thus the logical rule
$U^{\prime}(\mathsf{h},x)$ can be captured by QL-GNN with constant
$\mathsf{c}$ and cannot be captured by ERA-GNN and vanilla QL-GNN as shown in
Table 1.

However, assigning constants to all the entities with an out-degree larger
than one will introduce lots of constants in KG, impeding the generalization
of GNN (Abboud et al., 2021). Instead, we propose a heuristic labeling method
called Entity Labeling GNN (EL-GNN) in Algorithm 1 that assigns constants to
all the entities with out-degree larger than $d$, whose value is a hyper-
parameter to be tuned. A smaller $d$ makes GNN learn the logical rules with
many constants with bad generalization, while a larger $d$ may not be able to
transform difficult logical rules into formulas in CML. Same as the constant
$\mathsf{h}$ in QL-GNN, we add a unique feature $\mathbf{e}_{v}^{0}$ for
entities $v$ whose out-degree $d_{v}>d$ in steps 2-6. For the query entity
$h$, we assign it with a unique initial feature $\mathbf{e}_{h}^{0}$ in step
7.

Algorithm 1 Entity Labeling GNN (EL-GNN)

0: query $(h,R,?)$, knowledge graph $\mathcal{K}$, degree threshold $d$.

1: compute the out-degree $d_{v}$ of each entity $v$ in $\mathcal{K}$;

2: for entity $v$ in $\mathcal{K}$ do

3: if $d_{v}>d$ then

4: assign a unique feature $\mathbf{e}_{v}^{0}$ to entity $v$;

5: end if

6: end for

7: assign initial feature $\mathbf{e}_{h}^{0}$ to the query entity $h$;

8: Return: initial feature of all entities

In summary, EL-GNN can learn relations with dependent head and tail entities
which can be described with formulas in the form of $R(\mathsf{h},x)$ in
$\text{CML}[\mathcal{K},\mathsf{h},\mathsf{c}_{1},\cdots,\mathsf{c}_{k}]$,
including QL-GNN as a special case as shown in Figure 2 (green and yellow
ellipses).

##  7 Experiment

In this section, we conduct experiments on synthetic datasets to validate our
theoretical findings in Section 5 and demonstrate the effectiveness of the
proposed EL-GNN on both synthetic and real datasets. All the experiments are
written in Python with PyTorch run on RTX 3090 GPUs with 24GB memory.

Table 2: Hit@1 on synthetic data. | $C$ | $I$ | $U$
---|---|---|---
CompGCN | 0.016 | 0.039 | 0.027
NBFNet | 1.0 | 1.0 | 0.541
EL-GNN | 1.0 | 1.0 | 0.838
Table 3: Results of KG reasoning on real datasets. The best result is in “bold”. Method Class | Methods | Family | Kinship | ULMS | WN18RR
---|---|---|---|---|---
MRR | Hit@1 | Hit@10 | MRR | Hit@1 | Hit@10 | MRR | Hit@1 | Hit@10 | MRR | Hit@1 | Hit@10
Embedding-based | RotatE | 0.921 | 0.866 | 0.988 | 0.807 | 0.703 | 0.975 | 0.925 | 0.863 | 0.993 | 0.477 | 0.428 | 0.571
QuatE | 0.941 | 0.896 | 0.991 | 0.479 | 0.310 | 0.831 | 0.944 | 0.905 | 0.993 | 0.480 | 0.440 | 0.551
Rule-based | Neural LP | 0.924 | 0.871 | 0.994 | 0.620 | 0.480 | 0.910 | 0.745 | 0.627 | 0.918 | 0.435 | 0.371 | 0.566
DRUM | 0.934 | 0.881 | 0.996 | 0.61 | 0.460 | 0.910 | 0.813 | 0.674 | 0.976 | 0.486 | 0.425 | 0.586
GNN-based | CompGCN | 0.933 | 0.883 | 0.991 | 0.840 | 0.751 | 0.979 | 0.927 | 0.867 | 0.994 | 0.479 | 0.443 | 0.546
NBFNet | 0.989 | 0.987 | 0.989 | 0.887 | 0.806 | 0.995 | 0.948 | 0.920 | 0.992 | 0.551 | 0.497 | 0.666
EL-GNN | 0.989 | 0.988 | 0.990 | 0.888 | 0.815 | 0.990 | 0.957 | 0.937 | 0.990 | 0.556 | 0.501 | 0.670

###  7.1 Experiments on synthetic datasets

We generate three KGs based on the relations in Figure 1 to validate our
theory on logical expressiveness and verify that EL-GNN can improve the
empirical performance of KG reasoning. In this section, we use CompGCN, NBFNet
and NBFNet with Algorithm 1 to evaluate ERA-GNN, QL-GNN and EL-GNN,
respectively. Similar to Sadeghian et al. (2019); Zhu et al. (2021), we use
the filtered ranking metric Hit@1 for evaluation. This metric measures the
proportion of correctly predicting the target tail entity, with larger values
indicating better performance. We report the testing Hit@1 performance of ERA-
GNN, QL-GNN and EL-GNN on three synthetic KGs. The hyperparameters of all
methods in this section are automatically tuned with the hyperparameter tuning
library Ray (Liaw et al., 2018) by validation Hit@1 performance.

#### Dataset generation

Given a target relation, there are three steps to generate a dataset:

  1. 1.

rule structure generation: generate specific rule structures according to
those in Figure 1;

  2. 2.

noisy structure generation: generate noisy structures to avoid GNN from
learning naive logical rules;

  3. 3.

triplet completion: generate missing triplets according to the target rule
structures.

The triplets generated from target rule structures and noisy structures are
used as known facts in KG, and the triplets with target relation are separated
as training, validation and testing sets.

#### Results

The empirical Hit@1 results of ERA-GNN, QL-GNN and EL-GNN on the three
synthetic datasets, which are generated according to the relations in Figure
1, are reported in Table 2. For simplicity, we denote these three datasets as
$C$, $I$ and $U$ according to the type of rule structures. The experimental
results here are consistent with our theory. First, ERA-GNN shows poor results
in all the three datasets since ERA-GNN cannot capture any logical rules
behind the relations of these synthetic datasets as discussed in Section 5.1.
Second, facts with relations $C$ and $I$ are perfectly predicted by QL-GNN
with<EMAIL_ADDRESS>since QL-GNN can capture the logical rules
$C(\mathsf{h},x)$ and $I(\mathsf{h},x)$ as discussed in Section 5.3. Third, we
observe that EL-GNN can indeed improve the empirical performance of learning
the difficult logical rule from the experimental results on dataset $U$, which
is consistent with our analysis in Section 6. Finally, EL-GNN can also well
capture the logical rules $C(\mathsf{h},x)$ and $I(\mathsf{h},x)$, verifying
its logical expressiveness.

In addition, we show the influence of degree threshold value $d$ on EL-GNN
with dataset $U$. The testing Hit@1 performance plotted in Figure 4 shows that
the out-degree $d$ with a too small or too large value impedes the
generalization of EL-GNN. Hence, the hyperparameter $d$ should be empirically
tuned according to the validation performance.

Figure 4: Hit@1 versus out-degree $d$ of EL-GNN on the dataset with relation
$U$. This figure shows that a too small or too large out-degree $d$ impedes
the generalization of EL-GNN.

###  7.2 Experiments on real datasets

We perform experiments to verify the effectiveness of EL-GNN on four real
datasets: Family (Kok & Domingos, 2007), Kinship (Hinton et al., 1986), UMLS
(Kok & Domingos, 2007) and WN18RR (Dettmers et al., 2017). For a fair
comparison, we evaluate EL-GNN (NBFNet with Algorithm 1) with the same set of
hyperparameters as NBFNet and handcrafted $d$. The experiment involves
embedding-based methods (RotatE (Sun et al., 2019), QuatE (Zhang et al.,
2019)), rule-based methods (Neural LP (Yang et al., 2017), DRUM (Sadeghian et
al., 2019)) and GNN-based methods (CompGCN (Vashishth et al., 2020), NBFNet
(Zhu et al., 2021)) for comparison. To evaluate the performance, we use the
filtered ranking metrics MRR (Mean Reciprocal Rank), Hit@1 and Hit@10 which
are commonly used for evaluating models for KG reasoning (Sadeghian et al.,
2019; Zhang & Yao, 2022). Larger values for these metrics indicate better
performance.

We report the testing MRR, Hit@1 and Hit@10 (Bordes et al., 2013) in Table 3.
Our experimental results demonstrate that GNN-based methods, particularly
NBFNet (QL-GNN), outperform both embedding-based and rule-based methods.
Additionally, our proposed EL-GNN improves the empirical performance of KG
reasoning on real datasets. However, the improvement performance varies on
different datasets as the difficult rules in different datasets are distinct.

##  8 Conclusion

In this paper, we analyze the logical expressiveness of GNN for KG reasoning.
Our paper answers the question of what kind of logical rules can be captured
by GNN in KG reasoning, which provides insights into why NBFNet and RED-GNN
are good at inductive KG reasoning. Furthermore, our theory motivates an
effective labeling method for improving GNN’s empirical performance in
learning difficult logical rules. In addition, the results in our paper can be
directly extended to link prediction on the heterogeneous graph because KG is
equivalent to the heterogeneous graph. As a future work, we will extend the
logical expressiveness to GNNs with general labeling trick, apply our theory
and proposed method for scientific KG reasoning, and try to extract
explainable logical rules from the parameters of GNN.

## References

  * Abboud et al. (2021) Abboud, R., Ceylan, I. I., Grohe, M., and Lukasiewicz, T.  The surprising power of graph neural networks with random node initialization.  In _International Joint Conference on Artificial Intelligence_ , 2021\.
  * Abujabal et al. (2018) Abujabal, A., Saha Roy, R., Yahya, M., and Weikum, G.  Never-ending learning for open-domain question answering over knowledge bases.  In _International World Wide Web Conference_ , 2018.
  * Arakelyan et al. (2021) Arakelyan, E., Daza, D., Minervini, P., and Cochez, M.  Complex query answering with neural link predictors.  In _International Conference on Learning Representations_ , 2021.
  * Barceló et al. (2020) Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., and Silva, J.-P.  The logical expressiveness of graph neural networks.  In _International Conference on Learning Representations_ , 2020.
  * Blackburn et al. (2001) Blackburn, P., Rijke, M. d., and Venema, Y.  _Modal Logic_.  Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2001.  doi: 10.1017/CBO9781107050884.
  * Bordes et al. (2013) Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O.  Translating embeddings for modeling multi-relational data.  _Advances in Neural Information Processing Systems_ , 2013.
  * Cai et al. (1992) Cai, J.-Y., Fürer, M., and Immerman, N.  An optimal lower bound on the number of variables for graph identification.  _Combinatorica_ , 12(4):389–410, 1992.
  * Cao et al. (2019) Cao, Y., Wang, X., He, X., Hu, Z., and Chua, T.-S.  Unifying knowledge graph learning and recommendation: Towards a better understanding of user preferences.  In _International World Wide Web Conference_ , 2019.
  * De Rijke (2000) De Rijke, M.  A note on graded modal logic.  _Studia Logica_ , 64(2):271–283, 2000.
  * Dettmers et al. (2017) Dettmers, T., Minervini, P., Stenetorp, P., and Riedel, S.  Convolutional 2D knowledge graph embeddings.  In _AAAI conference on Artificial Intelligence_ , 2017.
  * Galkin et al. (2022) Galkin, M., Zhu, Z., Ren, H., and Tang, J.  Inductive logical query answering in knowledge graphs.  _Advances in Neural Information Processing Systems_ , 2022.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _International Conference on Machine Learning_ , 2017.
  * Hinton et al. (1986) Hinton, G. E. et al.  Learning distributed representations of concepts.  In _Annual Conference of the Cognitive Science Society_ , 1986.
  * Kipf & Welling (2016) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2016.
  * Kok & Domingos (2007) Kok, S. and Domingos, P.  Statistical predicate invention.  In _International Conference on Machine Learning_ , 2007.
  * Lavrac & Dzeroski (1994) Lavrac, N. and Dzeroski, S.  Inductive logic programming.  In _WLP_ , pp. 146–160. Springer, 1994.
  * Li et al. (2020) Li, P., Wang, Y., Wang, H., and Leskovec, J.  Distance encoding–design provably more powerful gnns for structural representation learning.  _Advances in Neural Information Processing Systems_ , 2020.
  * Liaw et al. (2018) Liaw, R., Liang, E., Nishihara, R., Moritz, P., Gonzalez, J. E., and Stoica, I.  Tune: A research platform for distributed model selection and training.  _arXiv preprint arXiv:1807.05118_ , 2018.
  * Mohamed et al. (2019) Mohamed, S. K., Novácek, V., and Nounu, A.  Discovering protein drug targets using knowledge graph embeddings.  _Bioinformatics_ , 2019.
  * Morris et al. (2019) Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In _AAAI conference on Artificial Intelligence_ , 2019.
  * Morris et al. (2020) Morris, C., Rattan, G., and Mutzel, P.  Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.  _Advances in Neural Information Processing Systems_ , 2020.
  * Otto (2019) Otto, M.  Graded modal logic and counting bisimulation.  _arXiv preprint arXiv:1910.00039_ , 2019.
  * Qu & Tang (2019) Qu, M. and Tang, J.  Probabilistic logic neural networks for reasoning.  _Advances in Neural Information Processing Systems_ , 2019.
  * Richardson & Domingos (2006) Richardson, M. and Domingos, P.  Markov logic networks.  _Machine learning_ , 62(1):107–136, 2006.
  * Sadeghian et al. (2019) Sadeghian, A., Armandpour, M., Ding, P., and Wang, D. Z.  Drum: End-to-end differentiable rule mining on knowledge graphs.  _Advances in Neural Information Processing Systems_ , 2019.
  * Sato et al. (2021) Sato, R., Yamada, M., and Kashima, H.  Random features strengthen graph neural networks.  In _SIAM International Conference on Data Mining_ , 2021.
  * Schlichtkrull et al. (2018) Schlichtkrull, M., Kipf, T. N., Bloem, P., Berg, R. v. d., Titov, I., and Welling, M.  Modeling relational data with graph convolutional networks.  In _European Semantic Web Conference_ , 2018.
  * Sun et al. (2019) Sun, Z., Deng, Z.-H., Nie, J.-Y., and Tang, J.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In _International Conference on Learning Representations_ , 2019.
  * Teru et al. (2020) Teru, K., Denis, E., and Hamilton, W.  Inductive relation prediction by subgraph reasoning.  In _International Conference on Machine Learning_ , 2020.
  * Trouillon et al. (2016) Trouillon, T., Welbl, J., Riedel, S., Gaussier, É., and Bouchard, G.  Complex embeddings for simple link prediction.  In _International Conference on Machine Learning_ , 2016.
  * Vashishth et al. (2020) Vashishth, S., Sanyal, S., Nitin, V., and Talukdar, P.  Composition-based multi-relational graph convolutional networks.  In _International Conference on Learning Representations_ , 2020.
  * Xu et al. (2019) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  In _International Conference on Learning Representations_ , 2019.
  * Xu et al. (2020) Xu, K., Li, J., Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, S.  What can neural networks reason about?  In _International Conference on Learning Representations_ , 2020.
  * Yang et al. (2017) Yang, F., Yang, Z., and Cohen, W. W.  Differentiable learning of logical rules for knowledge base reasoning.  _Advances in Neural Information Processing Systems_ , 2017.
  * You et al. (2021) You, J., Gomes-Selman, J. M., Ying, R., and Leskovec, J.  Identity-aware graph neural networks.  In _AAAI Conference on Artificial Intelligence_ , 2021.
  * Zhang & Chen (2018) Zhang, M. and Chen, Y.  Link prediction based on graph neural networks.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Zhang et al. (2021) Zhang, M., Li, P., Xia, Y., Wang, K., and Jin, L.  Labeling trick: A theory of using graph neural networks for multi-node representation learning.  _Advances in Neural Information Processing Systems_ , 2021.
  * Zhang et al. (2019) Zhang, S., Tay, Y., Yao, L., and Liu, Q.  Quaternion knowledge graph embeddings.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Zhang & Yao (2022) Zhang, Y. and Yao, Q.  Knowledge graph reasoning with relational digraph.  In _International World Wide Web Conference_ , 2022.
  * Zhu et al. (2021) Zhu, Z., Zhang, Z., Xhonneux, L.-P., and Tang, J.  Neural bellman-ford networks: A general graph neural network framework for link prediction.  _Advances in Neural Information Processing Systems_ , 2021.

##  Appendix A Related work

GNN-based methods for KG reasoning have been introduced in Section 2.2. In the
appendix, we will introduce the other two classes of methods for KG reasoning,
i.e., embedding-based methods and rule-based methods.

Embedding-based methods, such as TransE (Bordes et al., 2013), ComplEx
(Trouillon et al., 2016), RotatE (Sun et al., 2019) and QuatE (Zhang et al.,
2019), directly calculate the score based on the embeddings
$\mathbf{e}_{h},\mathbf{e}_{R},\mathbf{e}_{t}$ of the query entity $h$, query
relation $R$ and candidate entity $t$. For example, the score function of
TransE is $s(h,R,t)=-\|\mathbf{e}_{h}+\mathbf{e}_{R}-\mathbf{e}_{t}\|$.

Rule-based methods are generally divided into two main categories for
incorporating logic into KG reasoning: rule-composition methods and rule-
mining methods. Rule-composition methods involve the combination of a set of
predefined logical rules to deduce new facts based on known ones in KG. These
methods are often based on first-order logic, and they can be effective at
making precise and accurate inferences. Classical rule-composition methods
include ILP (Lavrac & Dzeroski, 1994) and MLN (Richardson & Domingos, 2006).
Rule-mining methods, on the other hand, involve the use of machine learning to
learn the logical rule of some relations in KG based on given rule structures
and make inferences based on the learned logical rule. Classical rule-mining
methods include Neural LP (Yang et al., 2017), DRUM (Sadeghian et al., 2019).
These methods are powerful for discovering new logical rules in a KG and
enable machines to reason in a way similar to humans in KG.

In summary, GNN-based methods achieve state-of-the-art performance in KG
reasoning but lack a theoretical certification for their good empirical
performance. While embedding-based methods are effective for KG reasoning,
they are not suitable for inductive KG reasoning and lack a theoretical
foundation for their good performance. Rule-based methods are effective for
solving inductive KG reasoning and offer good interpretability, but the
predefined rules or rule structures that they used to predict new facts can be
time-consuming and difficult to obtain. In addition, the predefined rules and
rule structures may not be flexible enough to capture the full complexity of
the relationships in KG, which can limit the accuracy and effectiveness of the
rule-based methods.

##  Appendix B Rule analysis

We use the notation $\mathcal{K},v\models P_{i}$ ($\mathcal{K},v\nvDash
P_{i}$) to represent that the unary predicate $P_{i}(x)$ is (not) satisfied at
entity $v$.

######  Definition B.1 (Definition of graded modal logic).

A formula in graded modal logic of knowledge graph $\mathcal{K}$ is
recursively defined as follows:

  1. 1.

If $\varphi(x)=\top$, $\mathcal{K},v\models\varphi$ if $v$ is an entity in
knowledge graph;

  2. 2.

If $\varphi(x)=P_{c}(x)$, $\mathcal{K},v\models\varphi$ if and only if $v$ has
the property $c$ or can be uniquely identified by constant $\mathsf{c}$;

  3. 3.

If $\varphi(x)=\varphi_{1}(x)\wedge\varphi_{2}(x)$,
$\mathcal{K},v\models\varphi$ if and only if $\mathcal{K},v\models\varphi_{1}$
and $\mathcal{K},v\models\varphi_{2}$;

  4. 4.

If $\varphi(x)=\neg\phi(x)$, $\mathcal{K},v\models\varphi$ if and only if
$\mathcal{K},v\nvDash\phi$;

  5. 5.

If $\varphi(x)=\exists^{\geq N}y,R_{j}(y,x)\wedge\phi(y)$,
$\mathcal{K},v\models\varphi$ if and only if the set of entities
$\\{u|u\in\mathcal{N}_{R_{j}}(v)\text{ and }\mathcal{K},u\models\phi\\}$ has
cardinality at least $N$.

######  Corollary B.2.

$C(\mathsf{h},x)$ is a formula in $\text{CML}[\mathcal{K},\mathsf{h}]$.

###### Proof.

$C(\mathsf{h},x)$ is a formula in $\text{CML}[\mathcal{K},\mathsf{h}]$ as it
can be recursively defined as follows

$\displaystyle\varphi_{1}(x)$ $\displaystyle=P_{h}(x),$
$\displaystyle\varphi_{2}(x)$ $\displaystyle=\exists
y,R_{1}(y,x)\wedge\varphi_{1}(y),$ $\displaystyle\varphi_{3}(x)$
$\displaystyle=\exists y,R_{2}(y,x)\wedge\varphi_{2}(y),$ $\displaystyle
C(\mathsf{h},x)$ $\displaystyle=\exists y,R_{3}(y,x)\wedge\varphi_{3}(y).$

∎

######  Corollary B.3.

$I(\mathsf{h},x)$ is a formula in $\text{CML}[\mathcal{K},\mathsf{h}]$.

###### Proof.

$I(\mathsf{h},x)$ is a formula in $\text{CML}[\mathcal{K},\mathsf{h}]$ as it
can be recursively defined as follows

$\displaystyle\varphi_{1}(x)$ $\displaystyle=P_{h}(x),$
$\displaystyle\varphi_{2}(x)$ $\displaystyle=\exists
y,R_{1}(y,x)\wedge\varphi_{1}(y),$ $\displaystyle\varphi_{3}(x)$
$\displaystyle=\exists y,R_{2}(y,x)\wedge\varphi_{2}(y),$
$\displaystyle\varphi_{s}(x)$ $\displaystyle=\exists^{\geq
2}y,R_{4}(y,x)\wedge\top,$ $\displaystyle\varphi_{4}(x)$
$\displaystyle=\varphi_{s}(x)\wedge\varphi_{3}(x),$ $\displaystyle
I(\mathsf{h},x)$ $\displaystyle=\exists y,R_{3}(y,x)\wedge\varphi_{4}(y).$

∎

######  Corollary B.4.

$U^{\prime}(\mathsf{h},x)$ is a formula in
$\text{CML}[\mathcal{K},\mathsf{h},\mathsf{c}]$.

###### Proof.

$U^{\prime}(\mathsf{h},x)$ is a formula in
$\text{CML}[\mathcal{K},\mathsf{h},\mathsf{c}]$ as it can be recursively
defined as follows

$\displaystyle\varphi_{1}(x)$
$\displaystyle=P_{h}(x),\varphi_{c}(x)=P_{c}(x),$
$\displaystyle\varphi_{2}(x)$ $\displaystyle=\exists
y,R_{1}(y,x)\wedge\varphi_{1}(y),$ $\displaystyle\varphi_{3}(x)$
$\displaystyle=\varphi_{2}(x)\wedge\varphi_{c}(x),$
$\displaystyle\varphi^{\prime}_{4}(x)$ $\displaystyle=\exists
y,R_{2}(y,x)\wedge\varphi_{3}(y),$ $\displaystyle\varphi^{\prime}_{5}(x)$
$\displaystyle=\exists y,R_{4}(y,x)\wedge\varphi^{\prime}_{4}(y),$
$\displaystyle\varphi^{\prime\prime}_{4}(x)$ $\displaystyle=\exists
y,R_{3}(y,x)\wedge\varphi_{3}(y),$
$\displaystyle\varphi^{\prime\prime}_{5}(x)$ $\displaystyle=\exists
y,R_{5}(y,x)\wedge\varphi^{\prime\prime}_{4}(y),$ $\displaystyle
U^{\prime}(\mathsf{h},x)$
$\displaystyle=\varphi^{\prime}_{5}(x)\wedge\varphi^{\prime\prime}_{5}(x)$

where the constant $\mathsf{c}$ ensures that there is only one entity
satisfied for unary predicate $\varphi_{3}(x)$. ∎

##  Appendix C Proof

We use the notation $\mathcal{K},(h,t)\models R_{j}$
($\mathcal{K},(h,t)\nvDash R_{j}$) to denote $R_{j}(x,y)$ is (not) satisfied
at $h,t$.

###  C.1 Proof of Theorem 4.1

The backward direction of Theorem 4.1 is proved by constructing a GNN that can
capture any formula $\varphi(x)$ in CML. The forward direction relies on the
results from recent theoretical results in Otto (2019). Our theorem can be
seen as an extension of Theorem 4.2 in Barceló et al. (2020) to heterogeneous
graph (KG).

We first prove the backward direction of Theorem 4.1.

######  Lemma C.1.

Each formula $\varphi(x)$ in CML can be captured by GNN (1) from its
representations.

###### Proof.

Let $\varphi(x)$ be a formula in CML. We decompose $\varphi$ into a series of
sub-formulas
$\text{sub}[\varphi]=(\varphi_{1},\varphi_{2},\cdots,\varphi_{L})$ where
$\varphi_{k}$ is a sub-formula of $\varphi_{\ell}$ if $k\leq\ell$ and
$\varphi=\varphi_{L}$. Assume the GNN representation
$\mathbf{e}_{v}^{i}\in\mathbb{R}^{L},v\in\mathcal{V},i=1\cdots L$. In our
paper, the theoretical analysis will based on the following simple choice of
(1)222Results for our paper hold for (1) that is at least as powerful as (3),
while negative results for (3) holds for general (1).

$\displaystyle\mathbf{e}_{v}^{i}=\sigma\left(\mathbf{e}_{v}^{i-1}\mathbf{C}+\sum_{j=1}^{r}\sum_{u\in\mathcal{N}_{R_{j}}(v)}\mathbf{e}_{u}^{i-1}\mathbf{A}_{R_{j}}+\mathbf{b}\right)$
(3)

with $\sigma=\min(\max(0,x),1)$,
$\mathbf{A}_{R_{j}},\mathbf{C}\in\mathbb{R}^{L\times L}$ and
$\mathbf{b}\in\mathbb{R}^{L}$. The entries of the $\ell$-th columns of
$\mathbf{A}_{R_{j}},\mathbf{C}$, and $\mathbf{b}$ depend on the sub-formulas
of $\varphi$ as follows:

  * •

Case 0. if $\varphi_{\ell}(x)=P_{\ell}(x)$ where $P_{\ell}$ is a unary
predicate, $\mathbf{C}_{\ell\ell}=1$;

  * •

Case 1. if $\varphi_{\ell}(x)=\varphi_{j}(x)\wedge\varphi_{k}(x)$,
$\mathbf{C}_{j\ell}=\mathbf{C}_{k\ell}=1$ and $\mathbf{b}_{\ell}=-1$;

  * •

Case 2. if $\varphi_{\ell}=\neg\varphi_{k}(x)$, $\mathbf{C}_{k\ell}=-1$ and
$\mathbf{b}_{\ell}=1$;

  * •

Case 3. if $\varphi_{\ell}(x)=\exists^{\geq
N}y\left(R_{j}(y,x)\wedge\varphi_{k}(y)\right)$,
$\left(\mathbf{A}_{R_{j}}\right)_{k\ell}=1$ and $\mathbf{b}_{\ell}=-N+1$.

with all the other values set to 0.

Before the proof, for every entity $v\in\mathcal{V}$, the initial feature
$\mathbf{e}_{v}^{0}=(t_{1},t_{2},\cdots,t_{n})$ has $t_{\ell}=1$ if the sub-
formula $\varphi_{\ell}=P_{\ell}(x)$ is satisfied at $v$, and $t_{\ell}=0$
otherwise.

Let $\mathcal{K}=(\mathcal{V},\mathcal{F},\mathcal{R})$ be a knowledge graph.
We next prove that for every $\varphi_{\ell}\in\text{sub}[\varphi]$ and every
entity $v\in\mathcal{V}$ it holds that

$\left(\mathbf{e}_{v}^{i}\right)_{\ell}=1\quad\text{if}\quad\mathcal{K},v\models\varphi_{\ell},\quad\text{and}\quad\left(\mathbf{e}_{v}^{i}\right)_{\ell}=0\quad\text{otherwise},$

for every $\ell\leq i\leq L$.

Now, we prove this by induction of the number of formulas in $\varphi$.

Base case: One sub-formula in $\varphi$. In this case, the formula is an
atomic predicate $\varphi=\varphi_{\ell}(x)=P_{\ell}(x)$. Because
$\mathbf{C}_{\ell\ell}=1$ and
$(\mathbf{e}_{v}^{0})_{\ell}=1,(\mathbf{e}_{v}^{0})_{i}=0,i\neq\ell$, we have
$(\mathbf{e}_{v}^{1})_{\ell}=1$ if $\mathcal{K},v\models\varphi_{\ell}$ and
$(\mathbf{e}_{v}^{1})_{\ell}=0$ otherwise. For $i\geq 1$, $\mathbf{e}_{v}^{i}$
satisfies the same property.

Induction Hypothesis: $k$ sub-formulas in $\varphi$ with $k<\ell$. Assume
$\left(\mathbf{e}_{v}^{i}\right)_{k}=1$ if $\mathcal{K},v\models\varphi_{k}$
and $\left(\mathbf{e}_{v}^{i}\right)_{k}=0$ otherwise for $k\leq i\leq L$.

Proof: $\ell$ sub-formulas in $\varphi$. Let $i\geq\ell$. Case 1-3 should be
considered.

Case 1. Let $\varphi_{\ell}(x)=\varphi_{j}(x)\wedge\varphi_{k}(x)$. Then
$\mathbf{C}_{j\ell}=\mathbf{C}_{k\ell}=1$ and $\mathbf{b}_{\ell}=-1$. Then we
have

$\displaystyle(\mathbf{e}_{v}^{i})_{\ell}=\sigma\left((\mathbf{e}_{v}^{i-1})_{j}+(\mathbf{e}_{v}^{i-1})_{k}-1\right).$

By the induction hypothesis, $(\mathbf{e}_{v}^{i-1})_{j}=1$ if only if
$\mathcal{K},v\models\varphi_{j}$ and $(\mathbf{e}_{v}^{i-1})_{j}=0$
otherwise. Similarly, $(\mathbf{e}_{v}^{i-1})_{k}=1$ if and only if
$\mathcal{K},v\models\varphi_{k}$ and $(\mathbf{e}_{v}^{i-1})_{k}=0$
otherwise. Then we have $(\mathbf{e}_{v}^{i})_{\ell}=1$ if and only if
$(\mathbf{e}_{v}^{i-1})_{j}+\mathbf{e}_{v}^{i-1})_{k}-1\geq 1$, which means
$(\mathbf{e}_{v}^{i-1})_{j}=1$ and $(\mathbf{e}_{v}^{i-1})_{k}=1$. Then
$(\mathbf{e}_{v}^{i})_{\ell}=1$ if and only if
$\mathcal{K},v\models\varphi_{j}$ and $\mathcal{K},v\models\varphi_{k}$, i.e.,
$\mathcal{K},v\models\varphi_{\ell}$, and $(\mathbf{e}_{v}^{i})_{\ell}=0$
otherwise.

Case 2. Let $\varphi_{\ell}(x)=\neg\varphi_{k}(x)$. Because of
$\mathbf{C}_{k\ell}=-1$ and $\mathbf{b}_{\ell}=1$, we have

$\displaystyle(\mathbf{e}_{v}^{i})_{\ell}=\sigma\left(-(\mathbf{e}_{v}^{i-1})_{k}+1\right).$

By the induction hypothesis, $(\mathbf{e}_{v}^{i-1})_{k}=1$ if and only if
$\mathcal{K},v\models\varphi_{k}$ and $(\mathbf{e}_{v}^{i-1})_{k}=0$
otherwise. Then we have $(\mathbf{e}_{v}^{i})_{\ell}=1$ if and only if
$-(\mathbf{e}_{v}^{i-1})_{k}+1\geq 1$, which means
$(\mathbf{e}_{v}^{i-1})_{k}=0$. Because $(\mathbf{e}_{v}^{i-1})_{k}=0$ if and
only if $\mathcal{K},v\nvDash\varphi_{k}$, we have
$(\mathbf{e}_{v}^{i})_{\ell}=1$ if and only if
$\mathcal{K},v\nvDash\varphi_{k}$, i.e., $\mathcal{K},v\models\varphi_{\ell}$,
and $(\mathbf{e}_{v}^{i})_{\ell}=0$ otherwise.

Case 3. Let $\varphi_{\ell}(x)=\exists^{\geq
N}y\left(R_{j}(y,x)\wedge\varphi_{k}(y)\right)$. Because of
$\left(\mathbf{A}_{R_{j}}\right)_{k\ell}=1$ and $\mathbf{b}_{\ell}=-N+1$, we
have

$\displaystyle(\mathbf{e}_{v}^{i})_{\ell}=\sigma\left(\sum_{u\in\mathcal{N}_{R_{j}}(v)}(\mathbf{e}_{u}^{i-1})_{k}-N+1\right).$

By the induction hypothesis, $(\mathbf{e}_{u}^{i-1})_{k}=1$ if and only if
$\mathcal{K},u\models\varphi_{k}$ and $(\mathbf{e}_{u}^{i-1})_{k}=0$
otherwise. Let $m=|\\{u|u\in\mathcal{N}_{R_{j}}(v)\text{ and
}\mathcal{K},u\models\varphi_{k}\\}|$. Then we have
$(\mathbf{e}_{v}^{i})_{\ell}=1$ if and only if
$\sum_{u\in\mathcal{N}_{R_{j}}(v)}(\mathbf{e}_{u}^{i-1})_{k}-N+1\geq 1$, which
means $m\geq N$. Because $\mathcal{K},u\models\varphi_{k}$, $u$ is connected
to $v$ with relation $R_{j}$, and $m\geq N$, we have
$(\mathbf{e}_{v}^{i})_{\ell}=1$ if and only if
$\mathcal{K},v\models\varphi_{\ell}$ and $(\mathbf{e}_{v}^{i})_{\ell}=0$
otherwise.

To capture a logical rule $\varphi(x)$, we only apply a linear classifier to
$\mathbf{e}_{v}^{L},v\in\mathcal{V}$ to extract the component of
$\mathbf{e}_{v}^{L}$ corresponding to $\varphi$. If
$\mathcal{K},v\models\varphi$, the value of the corresponding extracted
component is 1.

∎

Next, we prove the forward direction of Theorem 4.1.

######  Theorem C.2.

A formula $\varphi(x)$ is captured by GNN (1) if it can be expressed as a
formula in CML.

To prove Theorem C.2, we introduce Definition C.3, Lemma C.4, Theorem C.5, and
Lemma C.6.

######  Definition C.3 (Unraveling tree).

Let $\mathcal{K}$ be a knowledge graph, $v$ be entity in $\mathcal{K}$, and
$L\in\mathbb{N}$. The unravelling of $v$ in $\mathcal{K}$ at depth $L$,
denoted by $\text{Unr}_{\mathcal{K}}^{L}(v)$, is a tree composed of

  * •

a node $(v,R_{1},u_{1},\cdots,R_{i},u_{i})$ for each path
$(v,R_{1},u_{1},\cdots,R_{i},u_{i})$ in $\mathcal{K}$ with $i\leq L$,

  * •

an edge $R_{i}$ between $(v,R_{1},u_{1},\cdots,R_{i-1},u_{i-1})$ and
$(v,R_{1},u_{1},\cdots,R_{i},u_{i})$ when $(u_{i},R_{i},u_{i-1})$ is a triplet
in $\mathcal{K}$ (assume $u_{0}$ is $v$), and

  * •

each node $(v,R_{1},u_{1},\cdots,R_{i},u_{i})$ has the same properties as
$u_{i}$ in $\mathcal{K}$.

######  Lemma C.4.

Let $\mathcal{K}$ and $\mathcal{K}^{\prime}$ be two knowledge graphs, $v$ and
$v^{\prime}$ be two entities in $\mathcal{K}$ and $\mathcal{K}^{\prime}$
respectively. Then for every $L\in\mathbb{N}$, the WL test assigns the same
color/hash to $v$ and $v^{\prime}$ at round $L$ if and only if there is an
isomorphism between $\text{Unr}_{\mathcal{K}}^{L}(v)$ and
$\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$ sending $v$ to
$v^{\prime}$.

###### Proof.

Base Case: When $L=1$, the result is obvious.

Induction Hypothesis: WL test assigns the same color to $v$ and $v^{\prime}$
at round $L-1$ if and only if there is an isomorphism between
$\text{Unr}_{\mathcal{K}}^{L-1}(v)$ and
$\text{Unr}_{\mathcal{K}^{\prime}}^{L-1}(v^{\prime})$ sending $v$ to
$v^{\prime}$.

Proof: In the $L$-th round,

$\bullet$ Prove “same color $\Rightarrow$ isomorphism”.

$\displaystyle c^{L}(v)=$
$\displaystyle\text{hash}(c^{L-1}(v),\big{\\{}\big{\\{}(c^{L-1}(u),R_{i})|u\in\mathcal{N}_{R_{i}}(v),i=1,\cdots,r\big{\\}}\big{\\}}),$
$\displaystyle c^{L}(v^{\prime})=$
$\displaystyle\text{hash}(c^{L-1}(v^{\prime}),\big{\\{}\big{\\{}(c^{L-1}(u^{\prime}),R_{i})|u\in\mathcal{N}_{R_{i}}(v^{\prime}),i=1,\cdots,r\big{\\}}\big{\\}}).$

Because $c^{L}(v)=c^{L}(v^{\prime})$, we have
$c^{L-1}(v)=c^{L-1}(v^{\prime})$, and there exists an entity pair
$(u,u^{\prime}),u\in\mathcal{N}_{R_{i}}(v),u^{\prime}\in\mathcal{N}_{R_{i}}(v^{\prime})$
that

$\displaystyle(c^{L-1}(u),R_{i})=(c^{L-1}(u^{\prime}),R_{i}).$

Then we have $c^{L-1}(u)=c^{L-1}(u^{\prime})$. According to induction
hypothesis, we have
$\text{Unr}_{\mathcal{K}}^{L-1}(u)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L-1}(u^{\prime})$.
Also, because the edge connecting entity pair $(v,u)$ and
$(v^{\prime},u^{\prime})$ is $R_{i}$, so there is an isomorphism between
$\text{Unr}_{\mathcal{K}}^{L}(v)$ and
$\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$ sending $v$ to
$v^{\prime}$.

$\bullet$ Prove “isomorphism $\Rightarrow$ same color”.

Because there exists an isomorphism $\pi$ between
$\text{Unr}_{\mathcal{K}}^{L}(v)$ and
$\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$ sending $v$ to
$v^{\prime}$, assume $\pi$ is an bijective between the neighbors of $v$ and
$v^{\prime}$, e.g,
$u\in\mathcal{N}_{R_{i}}(v),u^{\prime}\in\mathcal{N}_{R_{i}}(v^{\prime})$ and
$u_{i}^{\prime}=\pi(u_{i})$, the relation between entity pair $(u,v)$ and
$(u^{\prime},v^{\prime})$ is $R_{i}$.

Next we prove $c^{L-1}(u)=c^{L-1}(u^{\prime})$. Because
$\text{Unr}_{\mathcal{K}}^{L}(v)$ and
$\text{Unr}_{\mathcal{K}}^{L}(v^{\prime})$ are isomorphism, and $\pi$ maps
$u\in\mathcal{N}_{R_{i}}(v)$ to
$u^{\prime}\in\mathcal{N}_{R_{i}}(v^{\prime})$, for the left tree with $L-1$
depth, i.e., $\text{Unr}_{\mathcal{K}}^{L-1}(u)$ and
$\text{Unr}_{\mathcal{K}^{\prime}}^{L-1}(u^{\prime})$, $\pi$ can be the
isomorphism mapping between $\text{Unr}_{\mathcal{K}}^{L-1}(u)$ and
$\text{Unr}_{\mathcal{K}^{\prime}}^{L-1}(u^{\prime})$. According to induction
hypothesis, we have $c^{L-1}(u)=c^{L-1}(u^{\prime})$. Because
$\text{Unr}_{\mathcal{K}}^{L}(v)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$,
we also have
$\text{Unr}_{\mathcal{K}}^{L-1}(u)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L-1}(u^{\prime})$
which means $c^{L-1}(u)=c^{L-1}(u^{\prime})$. After running WL test, we have
$c^{L}(v)=c^{L}(v^{\prime})$. ∎

######  Theorem C.5.

Let $\varphi(x)$ be a unary formula in FOC of KG. If $\varphi(x)$ is not
equivalent to a formula in CML, there exist two knowledge graphs $\mathcal{K}$
and $\mathcal{K}^{\prime}$ and two entities $v$ in $\mathcal{K}$ and
$v^{\prime}$ in $\mathcal{K}^{\prime}$ such that
$\text{Unr}_{\mathcal{K}}^{L}(v)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$
for every $L\in\mathbb{N}$ and such that $\mathcal{K},v\models\varphi$ but
$\mathcal{K}^{\prime},v^{\prime}\nvDash\varphi$.

###### Proof.

The theorem follows directly from Theorem 2.2 in Otto (2019). Because
$\mathcal{K},v\sim_{\\#}\mathcal{K}^{\prime},v^{\prime}$ and
$\text{Unr}_{\mathcal{K}}^{L}(v)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$
are equivalent with the definition of counting bisimulation (i.e., notation
$\sim_{\\#}$). ∎

######  Lemma C.6.

If a formula $\varphi(x)$ is not equivalent to any formula in CML, there is no
GNN (1) that can capture $\varphi(x)$.

###### Proof.

Assume for a contradiction that there exists a GNN that can captures
$\varphi(x)$. Since $\varphi(x)$ is not equivalent to any formula in CML, with
Theorem C.5, there exists two knowledge graphs $\mathcal{K}$ and
$\mathcal{K}^{\prime}$ and two entities $v$ in $\mathcal{K}$ and $v^{\prime}$
in $\mathcal{K}^{\prime}$ such that
$\text{Unr}_{\mathcal{K}}^{L}(v)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$
for every $L\in\mathbb{N}$ and such that $\mathcal{K},v\models\varphi$ and
$\mathcal{K}^{\prime},v^{\prime}\nvDash\varphi$. By Lemma C.4, because
$\text{Unr}_{\mathcal{K}}^{L}(v)\cong\text{Unr}_{\mathcal{K}^{\prime}}^{L}(v^{\prime})$
for every $L\in\mathbb{N}$, we have
$\mathbf{e}_{v}^{L}=\mathbf{e}_{v^{\prime}}^{L}$. But this contradicts the
assumption that GNN is supposed to capture $\varphi(x)$. ∎

###### Proof of Theorem C.2.

Theorem can be obtained directly from Lemma C.6. ∎

###### Proof of Theorem 4.1.

Theorem can be obtained directly by combining Lemma C.1 and Theorem C.2. ∎

###  C.2 Proof of Theorem 5.1

###### Proof.

According to Theorem 4.1, the GNN representation $\mathbf{e}_{v}^{L}$ can
capture the formulas in $\text{CML}[\mathcal{K}]$. Assume $\varphi_{1}(x)$ and
$\varphi_{2}(y)$ can be captured by the GNN representation
$\mathbf{e}_{v}^{L},v\in\mathcal{V}$ and there exists two functions $g_{1}$
and $g_{2}$ that can extract the logical rules from $\mathbf{e}_{v}^{L}$,
i.e., $g_{i}(\mathbf{e}_{v}^{L})=1$ if $\mathcal{K},v\models\varphi_{i}$ and
$g_{i}(\mathbf{e}_{v}^{L})=0$ if $\mathcal{K},v\nvDash\varphi_{i}$ for
$i=1,2$. We show how the following two logical operators can be captured by
$s(h,R,t)$ for candidate triplet $(h,R,t)$:

  * •

Conjunction: $\varphi_{1}(x)\wedge\varphi_{2}(y)$. The conjunction of
$\varphi_{1}(x),\varphi_{2}(y)$ can be captured with function
$s(h,R,t)=g_{1}(\mathbf{e}_{h}^{L})\cdot g_{2}(\mathbf{e}_{t}^{L})$.

  * •

Negation: $\neg\varphi_{1}(x)$. The negation of $\varphi_{1}(x)$ can be
captured with function $s(h,R,t)=1-g_{1}(\mathbf{e}_{h}^{L})$.

The disjunction $\vee$ can be obtained by
$\neg(\neg\varphi_{1}(x)\wedge\neg\varphi_{2}(y))$. More complex formula
involving sub-formulas from $\\{\phi_{i}(x)\\}$ and $\\{\psi_{j}(y)\\}$ can be
captured by combining the score functions above. ∎

###  C.3 Proof of Theorem 5.2

###### Proof.

We set the knowledge graph as $\mathcal{K}$ and restrict the unary formulas in
$\text{CML}[\mathcal{K},\mathsf{h}]$ to the form of $R(\mathsf{h},x)$. This
theorem is directly obtained by Theorem 4.1. ∎

###  C.4 Proof of Theorem 6.1

######  Lemma C.7.

Assume $\varphi(x)$ describes a single-connected rule structure $\mathsf{G}$
in a knowledge graph. If assign constant to entities with out-degree large
than 1 in the knowledge graph, the structure $\mathsf{G}$ can be described
with formula $\varphi^{\prime}(x)$ in CML of knowledge graph with assigned
constants.

###### Proof.

According to Theorem C.5, assume $\varphi^{\prime}(x)$ with assigned constants
is not equivalent to a formula in CML, there should exist two rule structures
$\mathsf{G},\mathsf{G}^{\prime}$ in knowledge graphs
$\mathcal{K},\mathcal{K}^{\prime}$, and entity $v$ in $\mathsf{G}$ and entity
$v^{\prime}$ in $\mathsf{G}^{\prime}$ such that
$\text{Unr}_{\mathsf{G}}^{L}(v)\cong\text{Unr}_{\mathsf{G}^{\prime}}^{L}(v^{\prime})$
for every $L\in\mathbb{N}$ and such that $\mathsf{G},v\models\varphi^{\prime}$
but $\mathsf{G}^{\prime},v^{\prime}\nvDash\varphi^{\prime}$.

Since each entity in $\mathsf{G}$ ($\mathsf{G}^{\prime}$) with out-degree
larger than 1 is assigned with a constant, the rule structure $\mathsf{G}$
($\mathsf{G}^{\prime}$) can be uniquely recovered from its unravelling tree
$\text{Unr}_{\mathsf{G}}^{L}(v)$ ($\text{Unr}_{\mathsf{G}^{\prime}}^{L}(v)$)
for sufficient large $L$. Therefore, if
$\text{Unr}_{\mathsf{G}}^{L}(v)\cong\text{Unr}_{\mathsf{G}^{\prime}}^{L}(v^{\prime})$
for every $L\in\mathbb{N}$, the corresponding rule structures $\mathsf{G}$ and
$\mathsf{G}^{\prime}$ should be isomorphism too, which means
$\mathsf{G},v\models\varphi^{\prime}$ and
$\mathsf{G}^{\prime},v^{\prime}\models\varphi^{\prime}$. Thus,
$\varphi^{\prime}(x)$ must be a formula in CML. ∎

###### Proof of Theorem 6.1.

The theorem holds by restricting the unary formula to the form of
$R(\mathsf{h},x)$ on Lemma C.7. ∎