Towards Enhancing Relational Rules for Knowledge Graph Link Prediction
Authors: Shuhan Wu
Huaiyu Wan
Wei Chen
Yuting Wu
Junfeng Shen
Youfang Lin
Venue: EMNLP 2023 Findings (2023)
Keywords: Knowledge Graph Reasoning
Graph Neural Network
Inductive Reasoning
TL;DR: This paper proposes a relational rule enhanced graph neural network (RUN-GNN) for knowledge graph link prediction.

Abstract: Graph neural networks (GNNs) have shown promising performance for knowledge graph reasoning. A recent variant of GNN called progressive relational graph neural network (PRGNN), utilizes relational rules to infer missing knowledge in relational digraphs and achieves notable results. However, during reasoning with PRGNN, two important properties are often overlooked: (1) the sequentiality of relation composition, where the order of combining different relations affects the semantics of the relational rules, and (2) the lagged entity information propagation, where the transmission speed of required information lags behind the appearance speed of new entities. Ignoring these properties leads to incorrect relational rule learning and decreased reasoning accuracy. To address these issues, we propose a novel knowledge graph reasoning approach, the Relational rUle eNhanced Graph Neural Network (RUN-GNN). Specifically, RUN-GNN employs a query related fusion gate unit to model the sequentiality of relation composition and utilizes a buffering update mechanism to alleviate the negative effect of lagged entity information propagation, resulting in higher-quality relational rule learning. Experimental results on multiple datasets demonstrate the superiority of RUN-GNN is superior on both transductive and inductive link prediction tasks.

Towards Enhancing Relational Rules for Knowledge Graph Link Prediction
Shuhan Wu', Huaiyu Wan 133 Wei Chen', Yuting Wu²; Junfeng Shen' and Youfang Lin 1,3 "School of Computer and Information Technology. Beijing Jiaotong University, Beijing, China School of Software Engineering, Beijing Jiaolong University, Beijing, China Beijjing Key Laboratory of Traffic Data Analysis and Mining, Beijing, China wushuhan, hywan, w_chen, ytwul, jfshen, yflin @bjtu. edu.cc
Abstract
ever, faces the problem of incompleteness, mak- ing difficult to provide effective knowledge ser- vices for downstream applications. As a result, KG reasoning, known as link prediction in KG, is proposed to automatically complete the missing knowledge and has attracted much attention from researchers.
Graph neural networks (GNNs) have shown promising performance for knowledge graph reasoning. A recent variant of GNN called progressive relational graph neural network (PRGNN), utilizes relational rules infer missing knowledge in relational digraphs and achieves notable results. However, during rea- soning with PRGNN, two important proper- ties are often overlooked: (1) the sequentiality of relation composition, where the order of combining different relations affects the seman- ties of the relational rules, and (2) the lagged entity information propagation, where the transmission speed of required information lags behind appearance speed of new en- tities. Ignoring these properties leads to in- correct relational rule learning and decreased reasoning accuracy. To address these issues, we propose a novel knowledge graph reason- ing approach, the Relational rUle eNhanced Graph Neural Network (RUN-GNN) Specifi- cally, RUN-GNN employs query related fu- sion gate unit to model the sequentiality of relation composition and utilizes buffering update mechanism to alleviate the negative ef- feet of lagged entity information propagation. resulting in higher-quality relational rule learn- ing. Experimental results on multiple datasets demonstrate the superiority of RUN-GNN su- perior on both transductive and inductive link prediction tasks.
Various methods for link prediction are explored to facilitate reasoning for missing knowledge. Pre- vious methods such as TransE (Bordes et al., 2013) and ConvE (Dettmers et al., 2018) perform reason- ing by learning and utilizing distributed represen- tations of entities and relations in triples. Since these methods can only capture the features of a single triple, some methods such as MINERVA (Das et al., 2018) and M-walk (Shen et al., 2018), are proposed to mine the path semantic information composed of triples. To further Iearn the semantic association of graph structures, methods such CompGCN (Vashishth et al., 2019) and KE-GCN (Yu et al., 2021) use graph neural networks (GNNs) to aggregate neighbor information.
The recent progressive relational graph neural network (PRGNN) such NBFNet (Zhu et al., 2021) and RED-GNN (Zhang and Yao, 2022), is kind of advanced KG link prediction method that learns relational rules infer missing knowl- edge. Relational rules refer to the Horn Clause that consists only of ordered relations, such as has has_father Bicbberrii____e lawllaaaa, c) + has flas_wifel we(a b) A has has_father(( (b, c). In PRGNN-based methods, the representation of each entity encodes the informa- tion of the specific relational digraph (r-digraph) (Zhang and Yao, 2022). Yet, we observe that the sequentiality of relation composition and lagged entity information propagation would affect the quality of encoded relational rule during inference, and the aforementioned methods lack the ability to deal with these two properties.
1 Introduction
Knowledge graph (KG) such as FreeBase (Bol- lacker et al., 2008), NELL (Carlson et al., 2010) and YAGO (Suchanek et al., 2007), is essentially a semantic network used to store and organize knowl- edge, which is extensively applied in variety of scenarios, such as question answering (Yasunaga al., 2021; Galkin et al., 2022), recommendation systems (Wang al., 2018), semantic search (Be- rant and Liang, 2014), etc. Each of these KGs, how-
The sequentiality of relation composition means that the order of combining differ-
"Coresponning author.

---

X
QuerytAsakessto autler Jin.)-MMia;
Sophia
F
Sophia
Sophia
has uife
Soptin
Andrew
Andrew
Butfer Medule
Andrew
Min
Andrew has jather
Mia
T2
Query head aninty 4
Answer uniity og
hos neighbor
Eihan
Ras viff
Ethan
Fithan
(b)
(c)
(4)
(e)
Unreachable
Reachable
Relation jas wife Piihts neighbor hos futher
Eniry that relational path
relational path
relational path
Figure Figure (a) shows a toy KG. Figures (b), (c), and (d) depict the sequential inference process of the PRGNN- -baeed methods for the query (Andrew, has mather_iiie peatherrin_lass + Mia the toy KG. (e) is the state of the KG after using our buffer module. r2. rí refers to the relational path ra b) A (b, c). The representations entities depicted in Figure (c) are generated by employing the entity representations from Figure (b) and the relations that interconnect them, including Figures (d) and (e).
ent relations affects the semantics of the re- lational rules. For example, both the rela- tional rules has tass_fttheraade 4 has hassssstsrrsaa b) A has (aas_[ahherbbc)) c) and hassawn mas_aunl((a, c) +
however, remains in the old candidate answer en- tity Ethan. Therefore, it becomes challenging to make the correct judgment for the given question. This phenomenon makes the model more prone to learning erroneous relation rules during the training phase and producing incorrect conclusions during the inference phase.
has has__atherr(4 b) A has_siste has_sister(b, c) contain the relations has sisssittrr and has_ father. The combination of two different relations in dif- ferent order can lead different conclusions. How- ever, existing PRGNN-basee methods face limita- tions in encoding such sequential information due to the standard practice of using addition and multi- plication operations to integrate representations of entities and relations. Consequently, these methods are prone misinterpreting the encoded relational rule information, which ultimately restricts their reasoning ability.
To address the properties mentioned above, we propose a novel KG link prediction method called Relational rUle eNhanced Graph Neural Network(RUN-GNNY equipped with two strate- gies for enhancing relational rules. The first en- hancement strategy involves employing query related fusion gate unit to update the representa- tion of relational rules. This allows RUN-GNN better encode various combination patterns among relations and identify the most valuable relational rules from a pool of candidate rules. The second proposed strategy is the utilization of a buffering update mechanism. This involves adding buffer module to the PRGNN encoder, allowing the trans- mission of lagged information to the entities that quire it. By doing so, the candidate answer entities promptly receive the necessary information, thus reducing the risk of the model learning incorrect rules. Both of the above strategics allow the method to learn and utilize enhanced relational rules effec- tively, thereby improving the performance of the method.
The phenomenon of lagged entity information propagation refers to the situation where the trans- mission speed of required information lags behind the appearance speed of new entities. The PRGNN updates entity representations by propagating infor- mation a growing subgraph. with entities in the subgraph considered as candidate answer entities. Consequently, as PRGNN undergoes forward prop- agation, new candidate answer entities continually emerge. However, these new entities often possess limited relational path information, while a substan- tial amount of crucial information remains trapped within the old candidate answer entities without being promptly conveyed to the new entities. Tak- ing Figure 1 as example, suppose want to infer who Andrew's mother-in-law is. The correct answer entity Mia is new candidate answer en- tity in Figure 1 (d) that can only obtain informa- tion about the shortest relational path r2, 71 from Andrew to Mia. The true key information Fı, T3,
Bricfly, the main contributions of this paper are as follows:
To the best of our knowledge, we are the first study the sequentiality of relation compo- sition and the lagged entity information prop- agation in KG link prediction, and novel PRGNN-based KG link prediction framework

---

RUN-GNN is proposed to enhance relational rules.
ods. Path-based methods predict triples by learn- ing and utilizing paths, including MINERVA (Das et al., 2018), M-walk (Shen et al., 2018), CURL (Zhang et al., 2022) etc. The based methods find rules by mining series of paths and employ those paths with high reliability as rules for reason- ing, including RNNLogic (Qu et al., 2020), DRUM (Sadeghian et al., 2019). NeuralLP (Yang et al., 2017), RLogic (Cheng al., 2022). Path infor- mation based methods are well interpretable but challenging to reason with long paths.
query related fusion gate unit (QRFGU) is proposed to orderly fuse different relational rules according to the query relation. Using QRFGU as a passsigg- function can model the sequentiality of relation composi- tion and significantly improve inference per- formance.
A huffering update mechanism is designed to help entities obtain richer reasoning rule information and overcome the problem of the lagged entity information propagation.
2.4
Graph Structure Information based Link Prediction
2.4.1
Graph Neural Network based Link Prediction
Experiments are conducted on multiple datasets under the inductive and transductive settings, and the experimental results show that RUN-GNN obtains substantial improve- ment over ofte-of-the-ar art methods.
After the introduction of Graph Convolutional Net- works (GCN) (Kipf and Welling, 2016) for homo- geneous graphs, the attention of rescarchers was also drawn to the heterogeneous graph. R-GCN (Schlichtkrull et al., 2018), which focuses on the relations between entities, was quickly proposed. Subsequent researchers further developed various graph neural network methods for heterogeneous graph reasoning, such as HAN (Wang et al., 2019b), BA-GNN (lyer et al., 2021), CompGCN (Vashishth et al.. 2019) and KE-GCN (Yu et al., 2021).
2 Related Work
2.1 Inductive Knowledge Graph Reasoning
Inductive KG reasoning methods can perform rea- soning on unseen entities. Some inductive methods aggregate the representations of seen entities to gen- erate representations for unseen entities, Examples of such methods include LAN(Wang et al., 201 9a) and CFAG (Wang et al., 2022). There are also some inductive methods that do not rely representa- tions of seen entities at all, instead relying solely on relational subgraphs for reasoning. Examples of these methods include GralL (Teru et al., 2020) and CoMPILE (Mai et al., 2021), RED-GNN (Zhang and Yao, 2022).
2.4.2 Subgraph- based Link Prediction
In contrast to conventional GNN-based approaches, subgraph-based methods often explicitly sample and encode neighborhood subgraphs of entities for reasoning. Early subgraph-based methods required sampling multi-hop subgraphs for each involved entity during each inference step, resulting in a high time complexity that limited their application to small datasets and relation prediction tasks. Ex- amples of such methods include GralL (Teru et al.. 2020), SNRI (Xu et al., 2022), LogCo (Pan et al., 2022), ConGLR (Lin et al., 2022), CoMPILE (Mai et al., 2021), CFAG (Wang et al., 2022).
2.2 Triple Information based Link Prediction
Methods based on triple information directly rea- triples with the entity and relation repre- sentations, including TransE (Bordes al., 2013), TransR (Lin al., 2015), TransH (Wang et al., 2014), HypE (Fatemi et al., 2021), RotatE (Sun et al., 2018 8), DistMult (Yang et al., 2015), ConvE (Dettmers et al., 2018), HAKE (Zhang et al., 2020), HousE (Li et al., 2022). These methods are simple and efficient, but cannot take advantage of graph structure features and not interpretable.
2.4.3 PRGNN-based Link Prediction
The PRGNN-based reasoning method is an ad- vanced subgraph- based KG link prediction method that performs inference by encoding r-digraph se- quences relational rule representation, including NBFNet (Zhu et al., 2021) and RED-GNN (Zhang and Yao, 2022). Zhu al. (2021) extended the Bellman algorithm using neural networks propose NBFNet, whose best best- persforeronnng instance model follows the reasoning pattern of PRGNN,
2.3 Path Information based Link Prediction
Methods based on path information mainly in- clude based methods and rule-based meth-

---

providing the first validation of the effectiveness of PRGNN. Zhang and Yao (2022) formally proposed the efficient progressive relational graph neural net- work framework RED-GNN for the first time by recursively encoding the r-digraphs. This signifi- cantly improves the problem of high time complex- ity of subgraph-based methods.
of relations and relational rules. It encodes the digraph into rule information representation for link prediction.
Both rule-based methods and PRGNN- based methods use only the combinations of relations for reasoning, but there are some differences in the form of utilization. Rule-based methods search for candidate answer entities in the neighborhood of the query head entity using rules and select the answer entity from the candi- date answer entities based on the matching rules, In contrast, PRGNN-based methods consider all entities in the neighborhood as candidate answer entities and encode the r-digraph as representations for the candidate entities using GNNs. The answer entity is then selected based on the representations of the entities. Therefore, PRGNN-bac based methods perform inference by learning relational rules, in which the entity representations can be considered representations of relational rules.
2.5
Link Prediction with Extra Information
of relational
Most KG reasoning methods typically learn how to perform reasoning from existing factual triplets. However, some methods have also incorporated additional information for reasoning. For instance, methods like JOIE (Hao et al., 2019) and DGS (lyer et al.. 2022) introduce ontology information, while KG-BERT (Yao et al., 2019) and StAR (Wang et al., 2021) incorporate textual information. MKG- former (Chen al., 2022), on the other hand, lever- ages extra multimodal information for reasoning.
3 Methodology
3.3 Model Architecture
3.1 Problem Definition
Figure 2 illustrates the overall structure of our pro- posed method RUN-GNN. The RUN-GNN follows encoder-decoder structure. The encoder con- tains exploration module and a buffer module connected in series.
The knowledge graph is denoted as G = (V,RFF). where V represents entity set, R represents rela- tions set, and JF {(s, r,o)]s, o V,r r E R] represents the fact triples set.
The task of link prediction KG aims to infer the missing entity 0g by giving an incomplete query triple (sq. q, ?). To simplify the process of link prediction, we follow the works (Vashishth et al., 2019; Sadeghian et al., 2019) to augment the KG by adding inverse and identity triples.
The primary objective of the exploration module is to explore more candidate answer entities and to generate entity representations of relational rules for them. The purpose of the buffer module, which operates as the latter component, is to update the information of changed relational rules to the rele- vant entities in timely manner. The decoder is linear layer that provides candidate answer entities with scores.
Depending on whether the entities in the test set appear in the training set, link prediction tasks can be divided into inductive settings and transductive settings. With the inductive setting, entities in the test sets do not appear in the training set. Our proposed method RUN-GNN is capable of both transductive and inductive tasks.
3.4 Query Related Fusion Gate Unit
The query related fusion gate unit (QRFGU), a variant of GRU(Chung et al., 2014), is designed to effectively model the properties of relational rules, specifically to ensure the sequentiality of relation composition. The QRFGU integrates the relation message representation hmeg E RR into the entity's 's rule representation hyute E IRd obtain new query-related relational rule representation h h E Rd where d denotes the size of the embedding dimension.
3.2 Progressive Relational Graph Neural Network
PRGNN is an advanced variant of GNNs, which performs KG link prediction by learning relational rules in KG. Unlike traditional GNNs, which up- date the representations of all entities in the graph during each propagation, the PRGNN-based ap- proach only updates the representations of i-hop neighbors of the query head entity during the i-th propagation. In addition, it does not learn represen- tations of entities, but only learns representations
The structure of QRFGU is shown in Figure 3. QRFGU can be denoted as:
hfase = CEFGUUbrutee Bmsgg hg)
(1)

---

(3)
(3)
KG
Query (g:
QRFGU
QREGU
QREGU
QREGU
G-GAT Layer
G-GAT Layer
G-GAT Layer
G-GAT Layer
Prediction
Exploration Module
Buffer Module
MLP
scores
Figure 2: The overall structure of RUN-GNN. QRFGU: query related fusion gate unit. G the i hop subgraph centered Sq-
in which the i-th G-GAT layer propagates relational information in i-hop subgraphs G. centered the query head entity sq. treating entities in these subgraphs as candidate answer entities and gener- ating corresponding entity representations of rela- tional rules.
Ataal
g
tanh
by
9u
hjuu
hveug
Lincar Layer Activation Function
Copy
Concatate
To better handle the sequentiality of relation composition, the G-GAT layer leverages the QR- FGU fuse the representations of the head entity and relation of each triple (s, r. o) and generates the representation of the corresponding candidate relation rule message ma..ro.g The computation of
Element-wise Calculation Operation
Figure 3: The structure query related fusion gate unit (QRFGU).
Msyag is formalized as follows:
where hy E Ied denotes query relation represen- tation. The QRFGU computes the forget gate 91 E [0, 13d and update gate Iu [0, 1jd based on hrule, hmsgs and hy firstly. And then, the QRFGU computes the candidate hidden state hr E Rd based on 9f. hrale, and hmsg. and subsequently derives the fused state fuse by combining hes hrule. and Ju- The detailed calculation process of QRFGU can be described as:
m srroog QREGU ,,,
(6)
where hs hy C iRd represent the representation of the head entity and relation of the current triple separately, the variable / in h4 denotes the I-th G- GAT layer.
The G-GAT layers compute the attention score d d'roog for each triple (s, r, o) in the subgraph G based hlg m m..rogg The attention score af dg.ro. is calculated by:
Iu oWW (irutts Mmsg- hg] + bu),
(2)
9f = o (WG[ltrute Amag: ltg] + by),
(3)
darog W ReLU ml + W)
(7)
h = tanh Lanh(Wa. (Womg + (hy O hrale)) ) + be),
(4)
hfuse = (1--fol fu) @ hrate fa @ be-
(5)
exp(car.g))
dg E exp( (ap((22,.0)) 3,5.0g
(8)
Among them, represents the sigmoid activate function. [.] denotes the concatenation operation. W., W C Rdx3d W. dRd by, be IRd all denote trainable parameters, O represents the Hadamard product.
where W E Iixd. and Wi, Wi E Bdadd repre- sent trainable weight matrices, d, is the attention space dimension. T! is the set of triples centered on in G So the candidate relational rule represen- tations for entities are calculated by the Equation:
3.5 Enhancing Relational Rules Using Query Related Fusion Gate Unit
RUN-GNN, the exploration module consists of n Gated Graph Attention Netwok (G-GAT) layers,
N1, x Σ (S.T:O)ET
(9)

---

where yp represents the ReLU activation function, tanh activation function or no operation.
from encoder at last, it will be assigned a score that values O.
After that, to further retain the valuable exist- ing relational rules, RUN-GNN utilizes QRFGU to control the updating of representations of entities. The I-th G-GAT layer calculates the representation of any entity in G in by:
The link prediction task can be regarded as a multi- classification problem. To optimize the parameters of the model, we use the multi-class log- loss (Lacroix et al., 2018 8; Zhang and Yao, 2022), i.e.
N/ QRFGU hq)
(10)
L= (Ayrny)EPPrsin
Σ (-((grg)) + log L expl (.0)))
(12)
It is worth emphasizing that the exploration module commences by initializing all entity representations zero vectors.
where (8g. 9, 0g) represents positive triple in train triples Ftrain and (sq: q, o) denotes any triple with the same query (sq. ?)?).
3.6 Enhancing Relational Rules Using Buffering Update Mechanism
Experiments
The generation of representations for candidate an- entities is a key feature of the exploration module. However, incomplete encoding of rela- tional rule information presents a challenge due to lagged entity information propagation. possible solution is to increase the number of G-GAT layers in the exploration module. However, this approach may lead to a larger subgraph during inference, re- sulting in higher resource consumption and larger number of candidate answer entities. Furthermore. new candidate answer entities are still susceptible to lagged entity information propagation.
To demonstrate the effectiveness of RUN-GNN, many experiments under inductive and transduc- tive tasks are conducted for KG link prediction on multiple benchmark datasets.
4.1 Transductive Experiments
4.1.1 Datasets and Baselines
We use four commonly used public datasets conduct our experiments, including WNI SRR (Dettmers et al., 2018), FB15k-237 (Toutanova and Chen, 2015), NELL-995 (Xiong et al., 2017) and YAGO3-10 (Chami et al., 2020). The details of these datasets can be found in Appendix B.I.
In this work, we propose a simple and elegant buffering update mechanism that can alleviate the problem of lagged entity information propagation with relatively low resource consumption, and sig- nificantly improve the performance of the model in queries where the answer entity is far away. In detail, We add a buffer module after the exploration module, which consists of m G-GAT layers, each of which propagates information on the same sub- graph G.a) The buffer module acts as buffer that allows candidate answer entities to wait for important relational rule information retained in dependent entities. This ensures that all candidate answer entities have enough relational rule infor- mation before proceeding with decoding.
To verify the effectiveness of our method, we compare RUN-GNN with various types of KG link prediction methods, including triple informa- tion based methods ConvE. (Dettmers et al., 2018), HousE (Li et al., 2022), HAKE (Zhang et al., 2020) and RotatE (Sun et al., 2018); path informa- tion based methods MINERVA (Das et al., 2018), DRUM (Sadeghian et al., 2019), CURL (Zhang et al., 2022) and RNNLogiC (Qu et al., 2020); nor- mal GNN-based methods CompGCN (Vashishth et al., 2019); existing PRGNN-based methods RED-GNN (Zhang and Yao, 2022) and NBFNet (Zhu et al., 2021). For most baseline methods, the experimental results are derived from related pub- lished papers and (Zhang and Yao, 2022). Since there are problems with the evaluation methodol- ogy of the RED-GNN, we re-evaluate the perfor- mance of the method using the code and hyperpa- rameters published in paper (Zhang and Yao, 2022). We also evaluate the performance of CURL, RNN- Logic, CompGCN, RED-GNN, and NBFNet on YAGO3-10 using publicly available codes and hy- perparameters.
3.7 Model Prediction and Optimization
The score of each entity is calculated based on a representation containing the appropriate relational rules. The score of entity o is given by
score(o) = [( (16g:90 4, o) = W mu+m
(11)
where Wscore E IR 1xd <xd] is the weight matrix. If an entity in RUN-GNN doesn't obtain a representation

---

WN18RR
FB13k-237
NFI.L-995
YAG03-10
Type
Methods
MRR
Hit@1
Hir@
MRR
@it@|
Hir@
MRR
Hit@
H
MRR
Hit@
Hit@ 10
ConvE
0.430
39.0
49.0
0.325
23.7
50.1
0.514
44.2
63.2
0.440
35.0
62.0
QuatE
0.480
44.0
0.350
25.6
53.8
0.533
46.6
64.3
0.495
40.2
67.0
Triple
HousF
0.511
46.5
60.2
0.361
26.6
55.1
0.528
45.8
64.5
0.571
49.1
71.4
HAKE
0.499
45.2
58.2
0.346
25
54.2
0.527
45.9
64.1
0.545
46.2
69.4
Path
MINERVA
0.448
41.3
51.3
0.293
21.7
45.6
0.513
41.3
63.7
DRUM
0.486
42.5
58.6
0,343
25.5
51.6
0.365
30.0
48.8
CURL
0.462
42.9
52.7
0.2902
21.1
45.3
0.442
32.8
56.4
0.499
42.2
63.9
RNNLogiC
0.483
44.6
55.8
0.344
25.2
53.0
0.479
43.1
57.1
0.536
47.1
64.2
CompGCN
0.479
44.3
54.6
0.355
26.4
53.5
0.518
44.6
63.4
0.354
25.7
54.4
Graph
RED-GNN
0.547
50.1
63.5
0.376
28.2
56.0
0.548
48.3
6.577
0.520
44.2
66.1
NBFNet
0.551
49.7
66.6
0.415
32.1
59.9
0.501
41.1
65.6
0.373
27.9
56,9
RUN-GNN (ours)
0.586
53.2
68.8
0.416
31.9
61.0
0.580
51.6
68.4
0.580
50.5
71.5
Table Experimental results on WNISRR, FB 15k-237, NELL-995, YAGO3-10 under transductive settings. H values in percentage. The best scores are in bold and the second-ber scores are with underline. unavailable results.
means
4.1.2 Detailed Settings
WNI8RR
FB15K-237
Methods
V1
V2
V3
V4
V1
V2
V3
V4
To evaluate our proposed method's performance, we utilize the filtered Mcan Reciprocal Rank (MRR), Hit@1, 1, and Hit@ 10 metrics. Our method is implemented using PyTorch (Paszke et al., 2019) and PyG (Fey and Lenssen, 2019). To train the model, we utilize four NVIDIA RTX A4000 GPUs for 80 epochs. The best performance of models is selected based the MRR metric each valida- tion set. Further details on the transductive experi- mental setup, including experimental hyperparam- eters, training time, number of model parameters, and more, can be found in Appendix B.2.
Neural LP
0.649
0.635
0.361
0.628
0.325
0.389
0.400
0.396
DRUM
0.666
0,646
0.380
0.627
0.333
0.395
0.402
0.410
GralL
0.627
0.625 0.323
0.553
0,279
0.276
0,251
0.227
RED-GNN
0.693
0.642
0.341
0.421
NBFNet
0.686
0.662
0.410
0.601
0.270
0.321
0.335
0.288
RUN-GNN
0.699 0.697 0.445 0.654
0.397
0.473
0.468
0.463
Table 2: Experimental results under inductive settings (evaluated with MRR). The best score in bold and the second-best scores are with underline.
Compared to CompGCN, RUN-GNN can represent every possible answer entity related to the current query.
RNNLogie.
Compared to NBFNet and REDGNN, our pro- posed method, RUN-GNN attributes PRGNN's reasoning capability to learning relational rules, and employs two effective strategies address crit- ical properties affecting PRGNN's reasoning capa- bility: sequential relation composition and lagged entity information propagation. These strategies enhance RUN-GNN 's ability to encode relational rules and give it clear advantage over similar methods.
4.1.3 Results and Discussion
Table illustrates the experiment results of dif- ferent methods. Our RUN-GNN model outper- forms baselines based on triple and path informa- tion all datasets by significant margin. RUN- GNN also achieves significant performance im- provements over other PRGNN-basel methods. For instance, RUN-GNN achieves an improvement 6.35% over NBFNet for the MRR metric on the WN18RR dataset. The results show our method currently has the most powerful reasoning ability. Our proposed method, RUN-GNN along with other methods like NBFNet and REDGNN, utilize PRGNN reasoning mode, which gives RUN-GNN a significant advantage over traditional rcasoning methods. Compared to ConvE, RotatE, and MIN- ERVA, RUN-GNN can utilize more graph struc- tural information in KG. Also, RUN-GNN can flex- ibly employ complex rules for link prediction im- plicitly, unlike rule-based methods like DRUM and
4.2 Inductive Experiments
We conduct inductive experiments to evaluate meth- ods' ability to reason about unseen entities.
4.2.1 Datasets and Baselines
We select eight widely used inductive datasets de- rived from WN18RR and FB15k-237 following the settings of previous research (Zhang and Yao. 2022; Teru et al., 2020).
In this work, we compare RUN-GNN with sev- eral other methods that possess inductive link pre- diction ability, including Neural LP (Yang et al.,
Code is available at https::/ //ts::///ttt twu.. com/ Ninggi /as//ONNGGR RUN-GNNNNNNN

---

2017), DRUM (Sadeghian et al., 2019), GralL (Teru al., 2020), RED-GNN (Zhang and Yao, 2022), NBFNet (Zhu et al., 2021). Among them, the experimental results of NeuralLP, DRUM, and Grall. are from the paper (Zhang and Yao, 2022). We re-evaluate the experimental results of RED- GNN and NBFNet using the code and hyperpa- rameters published in their papers (Zhang and Yao,
Methods
MRR
Hir
3
Hit 10
w/ multiplication
0.552
50.5
57.7
64.3
w/ addition
0.561
51.2
58.5
65.2
w/o buffer
0.563
51.4
58.8
65.5
RUN-GNN
0.571
52.5
59.2
66.1
Table 3: Experiment results of different variants.
7
m
H-Hop
2-Hop
3-Hop
4-Hop
5-Hop
6-Hop
ALL
2 0
0.994
0.449
0.001
0.000
0.001
0.000
0.391
2 2
0.995
0.496
0.001
0.001
0.001
0.000
0.394
2022; Zhu al., 2021) due issues with the ex-
3 0
0.995
0.533
0.383
0.000
0.001
0.000
0.480
perimental settings.
3 2 0.995
0.544
0.452
0.000
0.001
0.000
0.496
We evaluate the performance of the methods using the filtered MRR metric. We select the best performance based on the MRR metric on each
4 0 0.996 0.602
0,516
0.103
0.000
0.000
0.524
4 2 0.996 0.604
0.544
0.155
0.000
0.000
0.533
5 0 0.996 0.644
0.612
0.212
0.101
0.000
0.565
5 2 0.996
0.626
0.621
0,244
0.125
0.000
0.570
relevant validation set. The detailed settings are provided in Appendix B.5.
6 0 0.996
0.628
0.614
0.282
0.143
0.029
0.574
6 2 0.996
0.617
0.621
0.298
0. 0.168
0.039
0.579
Count 2192
582
1346
470
556
276
6268
Ratio 34.97
9.29
21.47
7.50
8.87
4,40
100.00
4.2.2 Results and Discussion
Based on the results presented in Table 2, our model RUN-GNN performs well on both sub- datasets of WNISRR and FB15k-237. NeuralLP and DRUM use the mined chain-like rules pre- dict knowledge, so they are able achieve good results. GralL. samples subgraphs between head and tail entities of triples and mines structural and relational information for reasoning, but doesn't 't ef- fectively use intermediate relational rules. PRGNN- based methods, like RED-GNN and NBFNet, are able to encode complex relational rules into entity representations and thus perform well. RUN-GNN utilizes QRFGU to encode more complex rules with greater accuracy, which enhances the model's ability to leverage relational rules and leads to bet- ter performance.
Table 4: The performance comparison of the MRR be- tween RUN-GNN models with different hyperparame- ters on the WN18RR dataset.
feetive component for encoding relational rules, Additionally, variant w/o buffer, which does not use the buffering update mechanism, also performs worse than RUN-GNN, demonstrating how the buffer module can improve entity representation and link prediction.
4.3.2 Does Buffer Update Mechanism Solve Lagged Entity Propagation?
To evaluate the effectiveness the proposed Buffer Update Mechanism in mitigating the negative ef- fects of Lagged Entity Propagation, we classify the test set based on the shortest path length from the head to tail entity of the query triple, varying hyperparameters and n. to assess RUN-GNN 's link prediction performance. Results presented in Table 4 show that increasing the value of m consis- tently improves the model's inference performance, particularly for triples with longer inference paths. This demonstrates the effectiveness of our proposed method in mitigating the negative effects of lagged entity information propagation. Additionally, re- sults also reveal that the number of G-GAT layers in the model's exploration module significantly af- fects performance.
4.3 Analysis
We conduct several experiments in this subsec- tion to validate the effectiveness of our proposed method. For subsequent experiments, we utilize only the transductive setting since it is the most commonly used experimental setting (Vashishth et al., 2019; Yang et al., 2015; Bordes et al., 2013). All methods are tested using the WNISRR dataset, with set to 5, m set to 3, and d set to 64.
4.3.1 Ablation Study
We design several variants of RUN-GNN to evalu- ate the impact of each component. Table 3 presents the results of the experiments. The table shows that variant w/ multiplication and variant w/ addition, which use multiplication or addition to fuse the en- tity and relation representation, perform worse than RUN-GNN which indicates that QRFGU is an ef-
4.3.3 Does Query Related Fusion Gate Unit Deal Well with Sequentiality of Relation Composition?
We designed an experiment to validate the effec- tiveness of QRFGU in encoding the sequentiality

---

and |F is the number of fact triples. More details can be found in the Appendix D.
5 Conclusion
0-
This paper attributes PRGNN's reasoning capabil- ity to learning relational rules and identifies two issues with existing methods. Firstly, we identify the issue of ignoring the sequentiality of relation composition, which causes the model to become confused with different relational rules. To address this issue, we propose QRFGU. Additionally, we identify the issue of lagged entity information prop- agation, which can lead to erroneous rule learn- ing. A buffering update mechanism introduced to mitigate this problem. We then combine these two relation rule enhancement strategies to pro- pose RUN-GNN which achieves state-of-the-art performance on knowledge graph link prediction tasks. In the future, we plan to investigate more efficient link prediction methods based PRGNN to improve their practicality.
-10
wio QRFGU Noraal
weo QREGU
wi QIFGU Match
w/ ORFGU Noraml
QRFGU Inverse
-30
w/ QRFGU Match
-40
20
Figure 4: Similarity image representing relational paths encoded in different ways.
of relation composition.
Firstly, We selected lots of common relational paths from the WN18RR dataset and reversed the order of relations in these paths obtain a of re- versed relational paths. Then these relational paths were separately encoded using the original RUN- GNN (represented as w/ QRFGU) and variant that uses element-wise addition as the MESSAGE func- tion (represented as w/o QRFGU). This resulted in four sets of representations. We mapped these rep- resentations to 2- d-mmensiionl space and plotted the representations using different colored dots in Figure We also connected the representations of the reversed relational paths and their correspond- ing original relational paths using colored lines.
Limitations
There may be some possible limitations in this study.
(1) According to the work of Zhang and Yao (2022), the time complexity of the PRGNN in- ference mode followed by RUN-GNN is higher than conventional methods. As result, the com- putational resource consumption of RUN-GNN is also higher compared these conventional meth- ods. Especially, Using QRFGU and buffering up- date mechanism may increase the computational cost during model inference. Since QRFGU is essentially a small neural network, rather than a parameter-free addition or multiplication operation, using this method may increase the computational cost. Additionally, the buffering update mechanism results in additional caleulations through the use of GNN, which may also contribute to rise in compu- tational cost. More details about time complexity can be found in the Appendix D.
In Figure 4, there are distinct orange lines, indicating that the representations of different or- der combinations of the same relation generated by the variant w/o QRFGU are very close. The model fails to capture the sequentiality compo- sitional relations and cannot distinguish between these representations. On the other hand, there are clear green lines in Figure 4, indicating that the representations generated by RUN-GNN (w/ QRFGU) have significant differences. The model successfully captures the sequentiality of composi- tional relations and can distinguish between these representations.
Despite these limitations, RUN-GNN is an in- ductive reasoning method that does not require sig- nificant resources to retrain the model when new entities are added when facts in the knowledge graph change, unlike traditional methods. Addi- tionally, we believe that pruning the model after training to reduce the number of candidate entities potential future research direction to improve efficiency and reduce resource consumption during
4.4 The Time Complexity Analysis
The overall time complexity of RUN-GNN, which consists of / GNN layers in the exploration module and n GNN layers in the buffer module, can be expressed as ((minnnDD (1+ x)]F)) + (D])d?). where is the dimension of relation representations
in the model, D [nl [ is the average degree of the knowledge graph | is the number of entities,

---

model inference.
References
(2) Our method may have difficulty in reasoning about query triples where the head and tail entities are far apart. Since RUN-GNN can only consider the n-hop neighbors of the query head entity as candidate answer entities and other entities will be considered unlikely to be correct answer entities. Increasing the number of G-GAT layers in the ex- ploration module by n can improve this, but this will come with sharp increase in computational re- source requirements, and Section 4.3.2 also shows that the effect of doing so may be poor. Therefore, it is difficult to provide correct reasoning for triples where the answer entity is far from the query head entity.
Jonathan Berant and Percy Liang. 2014. Semantic pars- ing via paraphrasing. In Proceedings of the 52nd An- nual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1415- 1425, Baltimore, Maryland. Association for Compu- tational Linguistics.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collabo- ratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIG- MOD international conference on Management of data, pages 1247-1250.
Antoine Bordes, Nicolas Usumier, Alberto Garcia- Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi- relational data. Advances in neural information pro- cessing systems, 26.
We believe that this issue can be addressed by allowing the model to conditionally select candi- date answer entities, which can reduce the answer search space and improve the model's ability to learn longer relational rules.
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. 2010. Toward an architecture for never-ending lan- guage learning. In Siventy-Fourth AAAI conference artificial intelligence.
Ethics Statement
This study is conducted with full compliance with the ethical code set out in the ACL Code of Ethics.
Ines Chami, Adva Wolf. Da- Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. 2020. Low- dimensional hyperbolic knowledge graph embed- dings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages
The datasets used in our research are publicly available datasets previously constructed by other researchers. The content of these datasets is sourced from publicly available online knowledge bases (Bollacker et al., 2008), publicly available cognitive linguistics-based English dictionaries (Dettmers et al., 2018; Miller, 1995), and publicly available semantic machine learning systems (Carl- son et al., 2010; Xiong et al., 2017). Other than that, all entities involved in the experiments were anonymized. Other than that, all entities involved in the experiments were anonymized.
Xiang Chen, Ningyu Zhang, Lei Li, Shumin Deng, Chuanqi Tan, Changliang Xu, Fei Huang. Luo Si, and Huajun Chen. 2022. Hybrid transformer with multi- level fusion for multimodal knowledge graph comple- tion. In Proceedings of the 45th International ACM SIGIR Conference Research and Development in Information Retrieval, SIGIR '22, page 904-915, New York, NY, USA. Association for Computing Machinery.
RUN-GNN's s utility extends to the completion and verification of existing knowledge graphs, such as Wikidata. However, like other knowledge graph link prediction methods, the information predicted by our method may be poisonous, biased, or wrong, so an additional safety review of the prediction results may be required. Furthermore, the potential misuse of this tool predict private information from public sources necessitates caution.
Kewei Cheng, Jiahao Liu, Wei Wang, and Yizhou Sun. 2022. Rlogic: knowledge graphs In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 179-189.
Recursive logical rule learning from
Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho. and Yoshua Bengio. 2014. Empirical evaluation of gated recurrent neural networks on sequence mod- eling. In NIPS 2014 Workshop on Deep Learning, December 2014.
Acknowledgements
Rajarshi Das. Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. 2018. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In International Conference on Learning Representa- tions.
This work is supported by the National Key R&D Program of China (No. 2021QY1 1502) and the Talent Fund of Beijing Jiaotong University (No. 2023XKRC032).

---

Tim Dettmers, Pasquale Minervini, Pontus Stenetorp. and Sebastian Riedel. 2018. Convolutional 2d knowl- edge graph embeddings. In Proceedings of the Thirty- Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial In- telligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, /8/AAA/1///AAA
Qika Lin, Jun Liu, Fangzhi Xu, Yudai Pan, Yifan Zhu, Lingling Zhang, and Tianzhe Zhao. 2022. Incorporat- ing context graph with logical reasoning for inductive relation prediction. In Proceedings of the 45th Inter- national ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '22, page 893-903, New York, NY, USA. Association for Computing Machinery.
AAAI Press.
Bahare Fatemi, Perouz Taslakian, David Vazquez, and
Yankai Lin, Zhiyuan Liu, Maosong Sun. Yang Liu, and Xuan Zhu. 2015. Learning entity and relation embed- dings for knowledge graph completion. In Twenty- ninth AAAI conference on artificial intelligence.
David Poole. 2021. Knowledge hypergraphs: Pre- diction beyond binary relations. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IICAI'00.
Sijie Mai, Shuangjia Zheng, Yuedong Yang, and Haifeng Hu. 2021. Communicative message passing for inductive relation reasoning. In Proceedings of the AAAI Conference Artificial Intelligence, vol- ume 35, pages 4294 4302.
Matthias Fey and Jan E. Lenssen. 2019. Fast graph representation learning with PyTorch Geometrie. In ICLR Workshop on Reprexentation Learning on Graphs and Manifolds.
Michael Galkin, Zhaocheng Zhu, Hongyu Ren, and Jian Tang. 2022. Inductive logical query answering in knowledge graphs. Advances in Neural Information Processing Systems, 1533001-152
George A Miller. 1995. Wordnet: a lexical database for english. Communications of the ACM, 38(11):39-14
Yudai Pan, Jun Liu, Lingling Zhang, Tianzhe Zhao, Qika Lin, Xin Hu, and Qianying Wang. 2022. Induc- tive relation prediction with logical reasoning using contrastive representations. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 4261 12244.
Junheng Hao, Muhao Chen, Wenchao Yu, Yizhou Sun,
and Wei Wang. 2019. Universal representation learn- ing of knowledge bases by jointly embedding in- stances and ontological concepts. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1709- 1719.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Te- jani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, Highh-Pefformance Deep Learn- ing Library. In Advances in Neural Information Pro- cessing Systems 32, pages 8024-8035. Curran Asso- ciates, Inc.
Roshni G Iyer. Yunsheng Bai, Wei Wang, and Yizhou Sun. 2022. Dual -hul-geomettric space embedding model for two-view knowledge graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 676-686.
Roshni G Iyer. Wei Wang, and Yizhou Sun. 2021. Bi- level attention graph neural networks. In 2021 IEEE International Conference on Data Mining (ICDM). pages 1126-1131. IEEE.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. 2020. Runlogic: Learning logic rules for reasoning on knowledge graphs. In International Conference on Learning Representations.
Thomas N Kipf and Max Welling. 2016. Semi- supervised classification with graph convolutional networks. arXiv preprint arXiv: (ttl::w600002000
Stanley Kok and Pedro Domingos. 2007. Statistical predicate invention. In Proceedings of the 24th in- ternational conference Machine learning, pages 433-440.
Esteban Real, Sherry Moore, Andrew Selle. Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc Le, and Alexey Kurakin. 2017. Large-scale evolution of image classifiers. In International Conference on Machine Learning, pages 2902-2911. PMLR.
Timothee Lacroix, Nicolas Usunier, and Guillaume Obozinski. 2018 Canonical tensor decomposition for knowledge base completion. In Proceedings of the 35th International Conference on Machine Leam- ing, volume 80 of Proceedings of Machine Learning Research, pages 2863-2872 PMLR.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. 2019. Drum: End-to- end differentiable rule mining on knowledge graphs. Advances in Neural Information Processing Systems, 32.
Rui Li, Jianan Zhao, Chaozhuo Li, Di He, Yiqi Wang. Yuming Liu, Hao Sun, Senzhang Wang, Weiwei Deng, Yanming Shen, et al. 2022. House: Knowl- edge graph embedding with houscholder parameter- ization. In International Conference on Machine Learning, pages 13209-13224. PMLR.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem. Rianne van den Berg. Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolu- tional networks. In European semantic web confer- ence, pages 593-607 Springer.

---

Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. 2018. M-walk: Learning to walk over graphs using monte carlo tree search, In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014. Knowledge graph embedding by trans- lating on hyperplanes. In Proceedings of the AAAI conference on artificial intelligence, volume 28.
Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Nat- ural Language Processing, pages 564-573, Copen- hagen, Denmark. Association for Computational Lin- guistics.
Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007. Yago: a core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pages 697-706.
Zhiqing Sun, Zhi-Hone Deng, Jian- Yun Nic, and Jian Tang. 2018. Rotate: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations.
Xiaohan Xu, Peng Zhang. Yongquan He, Chengpeng Chao, and Chaoyang Yan. 2022. Subgraph neighbor- ing relations infomax for inductive link prediction on knowledge graphs.
Komal Teru, Etienne Denis, and Will Hamilton. 2020. Inductive relation prediction by subgraph reasoning. In International Conference Machine Learning, pages 9448-9457, PMIR.
Bishan Yang. Scott Wen-tau Yih, Xiaodong He, Jian- feng Gao, and Li Deng. 2015. Emhedding entities and relations for learning and inference in knowledge bases. In Proceedings of the International Confer- ence on Learning Representations (ICLR) 2015.
Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Composi- tionality, pages 57-66, Beijing, China. Association for Computational Linguistics.
Fan Yang. Zhilin Yang. and William W Cohen. 2017. Differentiable learning of logical rules for knowledge base reasoning. Advances in neural information pro- cessing systems, 30.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. 2019, Composition- based multi- relational graph convolutional networks. In Interna- tional Conference on Learning Representations.
Liang Yao, Chengsheng Mao, and Yuan Luo. 2019. Kg- bert: Bert for knowledge graph completion. arXiv preprint arXiv: 1909.0399.
Bo Wang, Tao Shen, Guodong Long, Tianyi Zhou, Ying Wang, and Yi Chang. 2021. Structure- auggeente text representation learning for efficient knowledge graph completion. In Proceedings of the Web Confer- ence 2021, WWW 221, page 1737-1748, New York, NY, USA. Association for Computing Machinery.
Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. 2021. QA-GNN: Reasoning with language models and knowledge graphs for question answering. In Proceedings of the 202/ Conference tfe North American Chapter the Association for Computational Linguistics: Hu- man Language Technologies, pages 535-546, Online. Association for Computational Linguistics.
Changjian Wang. Xiaofei Zhou, Shirui Pan, Linhua Dong, Zeliang Song, and Ying Sha. 2022. Exploring relational semantics for inductive knowledge graph completion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4184- 4192.
Donghan Yu, Yiming Yang, Ruohong Zhang, and Yuexin Wu. 2021. Knowledge embedding based graph convolutional network. In Proceedings of the Web Conference 2021, WWW '21, page 1619-1628, New York, NY, USA. Association for Computing Machinery.
Hongwei Wang, Fuzheng Zhang, Jialin Wang, Miao Zhao, Wenjic Li, Xing Xic, and Minyi Guo. 2018 Ripplenet: Propagating user preferences on the knowledge graph for recommender systems. In Pro- ceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 11, page 417-426, New York, NY, USA. Association for Computing Machinery.
Denghui Zhang, Zixuan Yuan, Hao Liu, Hui Xiong, et al. 2022. Learning to walk with dual agents for knowl- edge graph reasoning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5932-5941.
Yongqi Zhang and Quanming Yao. 2022. Knowledge graph reasoning with relational digraph. Proceed- ings of the ACM Web Conference 2022, WWW '22, page 912-9992299999 924, New York, NY, USA. Association for Computing Machinery.
Peifeng Wang, Jialong Han, Chenliang Li, and Rong Pan. 2019a. Logic attention based neighborhood ag- gregation for inductive knowledge graph embedding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7152-7159.
Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. 2020. Learning hierarchy-aware knowledge graph embeddings for link prediction. In Proceed- ings of the AAAI conference on artificial intelligence. volume 34, pages 3072.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. 2019b. Heterogeneous graph attention network. In The world wide web conference, pages 2022-2032.

---

Zhaocheng Zhu, Zuobai Zhang, Louis-Pasee Pascal Xhon- neux, and Jian Tang. 2021. Neural bellman-fort ford net- works: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29490.
WNI8RR FB15K237
NEL.9995
YAGO3-I0
Relation
200
Entity
40943
14541
74,536
123182
Train
86835
272115
149678
1079040
Valid
3034
17535
543
5000
Test
3134
20466
2818
5000
Table 5: Datasets statisties in transductive link predic- tion experiments.
A Complete Algorithm for the Encoder of RUN-GNN
The complete algorithm for the encoder of RUN- GNN is described in Algorithm 1.
Algorithm The encoder of RUN-GNN
Input query head entity Sg. query relation q. the number n of exploration modules and the num- ber m the auxiliary modules.
Output H = (hele E E").
1: initial h = where E V, entity set e
{ triple set T = 0, i = 1, =1
for i <= do
T = {(s, r,o gi11 es, Ei {ols A U
for all E Ed do update he by Equation (6)-(10) end for
7: i+ i-
8: end for
9: for j <= m do
10: for all E E" do
11: update he by Equation (6) (10).
12: end for
13: j+ 1.
14: end for
15: return H (hele e En).
B Experiment Details
B.1 Transductive Datasets Statisties
In the transductive experiments, we mainly used four publicly available datasets: FB15k-237 (Toutanova and Chen, 2015), NELL-995 (Xiong et al., 2017), YAGO3-10 10 (Chami al., 2020) and WN18RR (Dettmers al., 2018). The statistical information of these datasets is shown in Table 5,
B.2 Transductive Experiment Detailed Settings
For the WNISRR, FB15k37, YAGO3-10, and NELL-995 datasets, we empirically select the num-

---

Datasets
WN18RR
FB FB15k-237
Entity Relation
Fact
Prediction
Entity
Relation
Fact
Prediction
train
2746
9
5410
1268
1594
180
4245
981
vl
test
922
1618
373
1093
180
1993
411
train
6954
15262
3706
1608
200
9739
2346
test
5084
4011
852
1660
200
4145
947
train
12078
11
25901
6249
3668
215
17986
4408
v3
test 5084
11
6327
1140
2501
215
7406
1731
train 3861
9
7940
1902
4707
219
27203
6713
v4
test
7084
9
12334
2823
3051
219
11714
2840
Table 6: Datasets statistics in inductive link prediction experiments.
Methods
Family Hit@1
UMLS
other approaches.
MRR
@it
MRR
Hit@1
Hit@
MINERVA
0.885
82.5
96.1
0.825
72.8
96.8
DRUM
0.934
88.1
99.6
0.813
67.4
97.6
B.4 Inductive Datasets Statistics
CompGCN
0.933
88.3
99.1
0.927
86.7
99.4
REDGNN
0.992
98.8
99.7
0.964
94.6
99.0
In our inductive experiments, follow the experi- mental settings of the previous researchers' work (Teru et al., 2020; Zhu et al., 2021) paper and se- lect eight inductive datasets from the WNI 8RR (Dettmers et al., 2018) and FB15k-237 (Toutanova and Chen, 2015) datasets. However, there are some differences in the experimental settings of induc- tive tasks using inductive datasets across different works. To accurately assess our model's perfor- mance, we employ these datasets for link predic- tion tasks in line with the experimental settings of the RED-GNN (Zhang and Yao, 2022) paper. Each inductive dataset comprises distinct training and testing subsets, each consisting of "fact triples" and "predict triples." The inductive methods infer missing entities in the "prediction triples" based on "fact triples" in the set. Notably, the training and testing subsets are entirely separate and utilize the same set of relations but feature different entities. To provide comprehensive overview, we present the statistical information the inductive datasets in Table 6.
RUN-GNN 0.989
98.8
99.1
0.986
98.0
99.5
Table 7: Experimental results on Family and UMLS under transductive settings. Hit@N values are in per- centage. The best scores are in bold and the second-best scores are with underline.
ber n of G-GAT layers in the exploration module to be 8, 6, 4, and 6, respectively, with dimen- sion size d set to 64, 48, 32, and 48, respectively. Additionally,
set the G-GAT layer number m in the buffer module to 2 for YAGO3-10 and 3 for RUN-GNN on other datasets. We use four NVIDIA RTX A4000 GPUs for training for up to 80 epochs, with early stopping based on MRR on the valid dataset. The training time for one epoch using these hyperparameters is 42, 1 117, and 370 minutes for WN18RR, NELL-995,, and FB 15--237, respec- tively. The best performance of models is selected based the MRR metric each valid dataset. Additionally, the RUN-GNN model employed in link prediction across the WNISRR, FB15k-237, and NELL-995 datasets utilizes 231k, 196k, and 223k parameters, respectively.
B.5 Inductive Experiment Detailed Settings
We evaluate the performance of the methods us- ing the filtered MRR metric. For RUN-GNN, we perform hyperparameter tuning of the number n of G-GAT in the exploration module, choosing from (4,5, 6, 7), the number choosing from {0, 1, 3, 4), and d, selecting from {32, 48, 64). Hyperparameter tuning is conducted for 24 hours using the Evolution Algorithm (Real et al., 2017). The model is trained on a single NVIDIA RTX A4000 GPU for 50 epochs. We select the best performance based on the MRR metric on each
B.3 Extra Transductive Experiment results
In addition to classic datasets like WNI8RR, we also conducted experiments on other datasets. Ta- ble 7 presents the performance of our method the Family dataset (Kok and Domingos. 2007) and UMLS dataset(Kok and Domingos, 2007). On the Family dataset, our method performs similarly to the state-of-the-ad RED-GNN, However, on the UMLS dataset, our method clearly outperforms

---

0.60
The time complexity comparison of these mod- els is shown in the table 8. Below is detailed analysis the time complexity of RUN-GNN and other PRGNN methods.
NBF-Net
0.55
RRE-GNN
MRK
0.45
D.1 Theoretical Analysis
0.40
Let [V] be the number of entities and |F] be the number of fact triples. Similar to the NBF-Net(Zhu et al., 2021), we decompose the time complexity the model into the MESSAGE and AGGREGATE parts.
0.35
5
The Hop Coun the Neighhor Subgraph
Figure 5: Comparison of inference capabilities of dif- ferent PRGNN-based methods for message propagation on subgraphs of different sizes.
D.1.1 Time Complexity of NBF-Net
The time complexity of the MESSAGE function in NBF-Net is O(d), and the time complexity of the AGGREGATE function is (dd)). Since each information propagation is performed on the entire knowledge graph, the overall time complexity is ((([FFd++ + [V]d2)).
relevant validation set.
C The Influence of Information Propagation Range in PRGNN
The performance of PRGNN-based methods is highly dependent on the maximum size of sub- graphs that GNN layers can propagate information through. This size is determined by the number of G-GAT Layers in the exploration module of RUN-GNN. In this section, conduct an evalua- tion of the performance of PRGNN-based methods by varying the maximum subgraph size.
D.1.2 Time Complexity of REDGNN
The time complexity of the MESSAGE function in REDGNN(Zhang and Yao, 2022) is O(d), and the time complexity of the AGGREGATE function is (dd). Therefore, the overall time complexity REDGNN is O(min F + [V|d)).
Figure 5 illustrates that our proposed RUN- GNN model achieves the best performance when the maximum subgraph size used for inference is greater than 4 hops. This result suggests that our method is particularly efficient at encoding and exploiting long relational paths. Furthermore, the advantage achieved by RUN-GNN over RED-GNN does not decrease significantly as the subgraph size grows. This finding indicates that our proposed strategy of utilizing buffering update mechanism to enhance relational rules cannot be replaced by simply increasing the number of G-GAT Layers in the exploration module.
D.1.3 Time Complexity of RUN-GNN
RUN-GNN also performs progressive information propagation by sampling series of subgraphs centered around the query entity, from small to large, and performing message passing on these subgraphs sequentially. The buffer update mech- anism in RUN-GNN does not involve additional subgraph sampling after message passing in the GNNs of exploration module. Instead, con- tinues to perform message passing on the largest subgraph used in the current reasoning process. Therefore, this step does not incur additional time cost for subgraph sampling.
D
The Detailed Time Complexity Analysis
Its MESSAGE function is QRFGU, which is essentially variant of GRU function with addi- tional attention, with time complexity of (dP). The AGGREGATE function is simple linear transformation with time complexity of (dP). Therefore, the overall time complexity of RUN- GNN with GNN layers the exploration mod- ule and n GNN layers in the buffer module is O(min(nnD) (I + Fl) + ())dd).
The overall time complexity of RUN-GNN, which consists of / GNN layers in the exploration module and n GNN layers in the buffer module, can be expressed as O(min(nD' (1+ (++))) + (D))d?), where is the dimension of relation representations in the model, D [F
is the average degree of the knowledge graph | is the number of entities, and |F is the number of fact triples.

---

Methods
NBF-Net
REDGNN
RUN-GNN
Subgraph sample
yes
yes
MESSAGE
O(d)
O(d)
O
AGGREGRATE
O(da)
O(d))
O(de)
Basic layer
O [)]]d))) ( [D', (I[[ii IDI|de
O D' .1I(Fii [1]]de
Buffer update
no
no
min (D', II
Total
O [1]
O(min Fl)d [[]]dA)
((min(nDD) n)]l (VI)))
Table 8: Time complexity comparison table for different PRGNN methods.
Methods
Time cost per epoch
MRR
(1)Examiple query (19522, father, '1955)
NBF-Net
3840
0,5439
REDGNN
0,5447
father
19553'
beveher_reversee reverse
REDGNN
4457
0,5646
1952
1955
RUN-GNN
0,5636
RUN-GNN
0,5703
wife reverse
1995
1995
mother
identity
Table 9: Time comparison table for different PRGNN methods trained on the WN18RR dataset. Here, rep- resents the number of GNN layers in the Exploration Module, and n represents the number of GNN layers in the Buffer Module.
Exammli query 2: (2104', husband, '2336)
2104 reverse
2336'
Exammle query nephew reverse, 11984)
1 1986'
'1984'
D.2 Time Measurement and Empirical Analysis
sister
'188''
son, reverse
As shown in the table NBF-Neet has much higher training time for 1 epoch when the number of GNN layers in the exploration module is 5, as it performs message passing directly on the entire KG.
Figure 6: Examples relational paths that are important when RUN-GNN performs inference.
logical and supports the notion that our approach can successfully learn crucial relational rules. This visualization further reinforces the interpretability and reliability of our method.
When the number of GNN layers in the buffer module is O, i.e., without using the buffer update mechanism, the model's performance already sur- passes that of REDGNN and NBF-Net with 5 GNN layers in the exploration module. The performance of FUNN-GNT even approaches that of REDGNN with GNN layers, which takes times longer to train.
When the number of GNN layers in the buffer module is 3, i.e., using the buffer update mecha- nism, the model's reasoning ability is further im- proved with only increase in time cost. It clearly outperforms REDGNN with 8 GNN layers, which requires more computational resources.
E
Case Study
In addition to its improved performance, our method RUN-GNN offers excellent interpretabil- ity. To illustrate this, visualize the r-digraph utilized in the inference process for three queries from the family dataset, following the approach outlined in paper(Zhang and Yao, 2022). Figure showcases the evidence discovered by our method during the inference process, which appears to be


Reviews:
[{"review_id": "txzf8AZL94", "reviewer": "Reviewer_FhXe", "summary": "", "questions": "See weakness.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We will address your concerns and clarify any areas where you have doubts one by one.\n\n### Q1. Why don’t you compare your model with baseline model, PRGNN? Besides, some of the important baselines should be compared, including [1] [2] [3] [4]. For more sota methods, refer to the survey papers [5, 6].\n\nA1:\n\nThank you for your valuable suggestion.\n\nFirstly, we would like to clarify that **PRGNN is a generic term used to refer to a class of methods**, rather than a specific method. **The PRGNN includes NBF-Net and REDGNN. In the experimental section, we have compared our model with NBF-Net and REDGNN.** \n\nSecondly, we will make efforts to include as many baseline methods as possible in the revised version of the paper, as you have suggested. Here, we provide a partial comparison of the experimental results between the baselines you mentioned and our method:\n\n| Methods        |           | WN18RR   |          |           | FB25k-237 |          |\n| -------------- | --------- | -------- | -------- | --------- | --------- | -------- |\n|                | MRR       | Hit@1    | Hit@10   | MRR       | Hit@1     | Hit@10   |\n| CURL[1]        | 0.460     | 42.9     | 52.3     | 0.306     | 22.4      | 47.0     |\n| HAKE[2]        | 0.497     | 45.2     | 58.2     | 0.346     | 25.0      | 54.2     |\n| HousE[3]       | 0.511     | 46.5     | 60.2     | 0.361     | 26.6      | 55.1     |\n| RUN-GNN (ours) | **0.586** | **53.2** | **68.8** | **0.416** | **31.9**  | **61.0** |\n\n**It can be observed that our method still possesses significant advantages in reasoning capability compared to these baseline methods.**\n\nAmong them, LogCo[4] is an inductive method that utilizes subgraph information. It requires collecting neighborhood subgraphs of all entities in the knowledge graph for each triple inference, resulting in a very high time complexity. Performing direct link prediction tasks with LogCo would require an extremely long time. We will continue to experiment with LogCo and include it in the baselines if possible.\n\nAs for the baseline models HAKE and HousE, they have not been experimented on the Nell-995 dataset. CURL, on the other hand, uses a different NELL-995 dataset compared to the one we used. Reproducing the corresponding models and conducting experiments on our NELL-995 dataset will be done in our future work, and we will continue to supplement the experimental results accordingly.\n\n[1] Zhang D, Yuan Z, Liu H, et al. Learning to walk with dual agents for knowledge graph reasoning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(5): 5932-5941.\n\n[2] Zhang Z, Cai J, Zhang Y, et al. Learning hierarchy-aware knowledge graph embeddings for link prediction[C]//Proceedings of the AAAI conference on artificial intelligence. 2020, 34(03): 3065-3072.\n\n[3] Li R, Zhao J, Li C, et al. House: Knowledge graph embedding with householder parameterization[C]//International Conference on Machine Learning. PMLR, 2022: 13209-13224.\n\n[4] Pan Y, Liu J, Zhang L, et al. Inductive relation prediction with logical reasoning using contrastive representations[C]//Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022: 4261-4274.\n\n---\n\n### Q2. The subgraph extraction procedure may take lots of time. The running time should be reported and analysis.\n\nA2:\n\nThank you for your valuable comment and suggestion. We will supplement the analysis of time complexity in the appendix of the revised version. \n\nBelow, we will provide a brief analysis and comparison of the time complexity of RUN-GNN:\n\n#### 2.1 Theoretical Analysis\n\n**The overall time complexity of RUN-GNN, which consists of $L$ GNN layers in the exploration modules and $n$ GNN layers in the buffer modules, can be expressed as $O((\\min(nD^L,(L+n)|\\mathcal{F}|) +|\\mathcal{V}|)d^2)$,** where $d$ is the dimension of relation representations in the model, $D= \\frac{|\\mathcal{F}|}{|\\mathcal{V}|}$ is the average degree of the knowledge graph, $|\\mathcal{V}|$ is the number of entities, and $|\\mathcal{F}|$ is the number of fact triples.\n\nBelow is a more detailed analysis of the time complexity:\n\nRUN-GNN  performs progressive information propagation by sampling a series of subgraphs centered around the queried entity and conducting message passing on these subgraphs in a sequential manner. The buffer update mechanism in RUN-GNN does not incur additional time cost for subgraph sampling after the message passing in the GNN layers of all exploration modules. Instead, it continues to perform message passing on the largest subgraph used in the current inference process.\n\nThe MESSAGE function in RUN-GNN is QRFGU, which is essentially a variant of GRU function with additional attention. It has a time complexity of $O(d^2)$. The AGGREGATE function is a simple linear transformation with a time complexity of $O(d^2)$. Therefore, the overall time complexity of RUN-GNN with L exploration modules in the GNN layers and n buffer modules in the GNN layers is $O((min(nD^L,(L+n)|\\mathcal{F}|) +|\\mathcal{V}|)d^2)$.\n\nBased on the previous analysis, the time complexity comparison of these models is shown in the following table:\n\n| Methods | Subgraph sample | MESSAGE  | AGGREGRATE | Basic layer                                           | Buffer update                  | Total                                                     |\n| ------- | --------------- | -------- | ---------- | ----------------------------------------------------- | ------------------------------ | --------------------------------------------------------- |\n| NBF-Net | no              | $O(d)$   | $O(d^2)$   | $O(L(\\|\\mathcal{F}\\|d+\\|\\mathcal{V}\\|d^2))$           | no                             | $O(L(\\|\\mathcal{F}\\|d+\\|\\mathcal{V}\\|d^2))$               |\n| REDGNN  | yes             | $O(d)$   | $O(d^2)$   | $O(min(D^L,L\\|\\mathcal{F}\\|) d+\\|\\mathcal{V}\\|d^2)$   | no                             | $O(min(D^L,L\\|\\mathcal{F}\\|) d+\\|\\mathcal{V}\\|d^2)$       |\n| RUN-GNN | yes             | $O(d^2)$ | $O(d^2)$   | $O(min(D^L,L\\|\\mathcal{F}\\|) d^2+\\|\\mathcal{V}\\|d^2)$ | $min(D^L,\\|\\mathcal{F}\\|)nd^2$ | $O((min(nD^L,(L+n)\\|\\mathcal{F}\\|) +\\|\\mathcal{V}\\|)d^2)$ |\n\n#### 2.2 Time Measurement and Empirical Analysis\n\nTable : time cost to train 1 epoch on WN18RR dataset with 1 Nvidia A4000 graphic card and final performance.\n\n| Methods     | GNN layers number in Exploration Module | GNN layers number in Buffer Module | Time cost/per epoch | MRR        |\n| ----------- | --------------------------------------- | ---------------------------------- | ------------------- | ---------- |\n| NBF-Net     | 5                                       | 0                                  | 3840s               | 0.5439     |\n| *REDGNN*    | *5*                                     | *0*                                | *218s*              | *0.5447*   |\n| *REDGNN*    | *8*                                     | *0*                                | *4457*s             | *0.5646*   |\n| **RUN-GNN** | **5**                                   | **0**                              | **460**s            | **0.5636** |\n| **RUN-GNN** | **5**                                   | **3**                              | **508s**            | **0.5703** |\n\n\n\nAs shown in the table above, NBF-Net, which directly propagates messages throughout the entire knowledge graph, takes significantly more time to train for one epoch when the number of GNN layers in the exploration module is set to 5 compared to the other models.\n\nWhen the number of GNN layers in the buffer module is set to 0, indicating the absence of buffer update mechanism, the performance of the model already surpasses that of REDGNN and NBF-Net with 5 GNN layers in the exploration module. **In fact, it even approaches the performance of REDGNN with 8 GNN layers, which takes 8 times longer to train.**\n\n---\n\n### Q3. More realistic and larger datasets should be considered, such as YAGO.\n\nA3:\n\nThank you for your valuable suggestion. Currently, our paper has utilized several classic datasets in the research of knowledge graph link prediction based on graph neural networks. Following your suggestion, we have presented the performance of our method on two more realistic datasets below. In the revised version of the paper, we will also supplement the performance of the model on these two datasets as well as on larger datasets.\n\n| Methods |           |  Family  |          |           |   UMLS   |          |\n| :-----: | :-------: | :------: | :------: | :-------: | :------: | :------: |\n|         |    MRR    |  Hit@1   |  Hit@10  |    MRR    |  Hit@1   |  Hit@10  |\n|  QuatE  |   0.941   |   89.6   |   99.1   |   0.944   |   90.5   |   99.3   |\n| MINERVA |   0.885   |   82.5   |   96.1   |   0.825   |   72.8   |   96.8   |\n|  DRUM   |   0.934   |   88.1   |   99.6   |   0.813   |   67.4   |  {97.6}  |\n| CompGCN |   0.933   |   88.3   |   99.1   |   0.927   |   86.7   |   99.4   |\n| REDGNN  | **0.992** | **98.8** | **99.7** |   0.964   |   94.6   |   99.0   |\n| RUN-GNN |   0.989   | **98.8** |   99.1   | **0.986** | **98.0** | **99.5** |\n\n---\n\n### Q4.More ablation studies should be included to illustrate the motivation of two proposed module. We can understand the motivation for why should we leverage the attributes. But can you explain how do you design frameworks of these modules? In other word, why do you come out the idea for the structure of the QRFGU in Figure 3. Why do you know it is effective?\n\nA4:\n\nThank you for your valuable suggestions and insightful comments. We will carefully review the paper and improve the wording in the revised version to enhance readability and ensure that the methods and theories are easily understandable. \n\nIn the following paragraph, we will restate our thought process behind the design of the model, aiming to address any concerns you may have.\n\nMethods based on PRGNN, such as NBF-Net and REDGNN, derive their reasoning capabilities from encoding relational rules in the model.\n\nIn the aforementioned process, **ensuring that the model can encode valid relational rules and correctly encode the semantics of relational rules becomes crucial.** During the analysis of PRGNN's operation, we identified two properties that affect the reasoning ability of PRGNN. \n\n**(1) The sequentiality of relation composition can impact the model's ability to correctly encode semantic information about relational rules.**\n\n**(2)  The lagged entity information propagation makes it difficult for the model to identify the correct relational rules.** \n\nHowever, existing PRGNN methods overlook these two properties. To address these issues, **we propose QRFGU and apply the G-GAT layer to encode relational rules**, which allows for modeling the sequentiality of relation composition. Additionally, **we introduce a buffering update mechanism to tackle the lagged entity information propagation.** \n\nBelow, we provide a more detailed description of the design motivations behind each component.\n\n#### 4.1 QRFGU\n\nThe QRFGU aims to **address the issue of existing PRGNN methods being unable to model the sequentiality of relation composition**. We considered multiple factors when designing QRFGU.\n\n1. Encoding the semantics of relational rules correctly helps the model perform accurate reasoning. The sequentiality of relation composition indicates that the order of relation combinations determines the semantics of relational rules. Therefore, PRGNN requires a MESSAGE function that can model the sequentiality of relation composition.\n\n2. RNN is a classic neural network widely used for sequence modeling, capable of effectively capturing properties such as sequence order.\n\n3. The reasoning capabilities of PRGNN stem from selecting and encoding relational rules from relational paths. Path-based reasoning methods, such as RNNLogic [3], also often use RNN to encode relational paths.\n\n4. GRU in RNN incorporates various gates similar to attention mechanisms and a forget mechanism similar to residual connections, enabling it to model complex sequences effectively.\n\nTherefore, **we chose GRU [4] as the basic structure of QRFGU, ensuring that QRFGU can effectively model the sequentiality.** Furthermore, considering the significant role of the query relation in the selection and encoding of relational rules, **we incorporate the query relation into the computation process of the forget gate and update gate. This allows the model to adjust the encoding of relational rule representations based on the query relation.**\n\n[1] Zhu Z, Zhang Z, Xhonneux L P, et al. Neural bellman-ford networks: A general graph neural network framework for link prediction[J]. Advances in Neural Information Processing Systems, 2021, 34: 29476-29490.\n\n[2] Zhang Y, Yao Q. Knowledge graph reasoning with relational digraph[C]//Proceedings of the ACM web conference 2022. 2022: 912-924.\n\n[3] Qu M, Chen J, Xhonneux L P, et al. RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs[C]//International Conference on Learning Representations. 2020.\n\n[4] Chung J, Gulcehre C, Cho K, et al. Empirical evaluation of gated recurrent neural networks on sequence modeling[C]//NIPS 2014 Workshop on Deep Learning, December 2014. 2014.\n\n#### 4.2 G-GAT layer\n\nWe refer to the neural network layer that encodes messages using QRFGU for knowledge graph as the Gated Graph Attention Network (G-GAT) layer.\n\nThe G-GAT layer is the fundamental unit of the RUN-GNN and consists of the following components:\n\n1. The MESSAGE function combines the representation of the relation rule for the head entity in the triple and the representation of the relation to generate candidate rule representations for the tail entity. Unlike existing methods such as CompGCN [1, 2, 3] that use triplet-based scoring functions as MESSAGE, **we utilize QRFGU, which can model the sequentiality and even more complex properties of relation composition.**\n\n2. The AGGREGATE function selects the most important candidate rule representations from multiple candidate rule representations corresponding to the same tail entity and generates the rule representation for the tail entity. Considering the influence of the query relation on the application of relation rules during reasoning, we incorporate a graph attention mechanism [4] that takes the query relation into account in this part.\n\n[1] Vashishth S, Sanyal S, Nitin V, et al. Composition-based Multi-Relational Graph Convolutional Networks[C]//International Conference on Learning Representations. 2019.\n\n[2] Zhu Z, Zhang Z, Xhonneux L P, et al. Neural bellman-ford networks: A general graph neural network framework for link prediction[J]. Advances in Neural Information Processing Systems, 2021, 34: 29476-29490.\n\n[3] Zhang Y, Yao Q. Knowledge graph reasoning with relational digraph[C]//Proceedings of the ACM web conference 2022. 2022: 912-924.\n\n[4] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.\n\n\n\nIn addition, we have validated the effectiveness of the model structure and components in the ablation experiments of section 4.3.1. Furthermore, in sections 4.3.2 and 4.3.3, we experimentally have verified the effectiveness of our proposed method in addressing the two challenges.\n\n---\n\nIn conclusion, thanks a lot for your comments. I hope this solves your problem and improves the quality of the paper.", "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": "1. Clearly presentation, especially for those nice figures.\n2. The idea is interesting.", "reasons_to_reject": "1. Why don’t you compare your model with baseline model, PRGNN? Besides, some of the important baselines should be compared, including [1] [2] [3] [4]. For more sota methods, refer to the survey papers [5, 6].\n\n[1] D. Zhang, Z. Yuan, H. Liu, H. Xiong et al., “Learning to walk with dual agents for knowledge graph reasoning,” in Proc. of AAAI, 2022.\n\n[2] Z. Zhang, J. Cai, Y. Zhang, and J. Wang, “Learning hierarchy-aware knowledge graph embeddings for link prediction,” in Proc. of AAAI, 2020.\n\n[3] R. Li, J. Zhao, C. Li, D. He, Y. Wang, Y. Liu, H. Sun, S. Wang, W. Deng, Y. Shen et al., “House: Knowledge graph embedding with householder parameterization,” arXiv preprint arXiv:2202.07919, 2022.\n\n[4] Y. Pan, J. Liu, L. Zhang, T. Zhao, Q. Lin, X. Hu, and Q. Wang, “Inductive relation prediction with logical reasoning using contrastive representations,” in Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. Abu Dhabi, United Arab Emirates: Association for Computational Linguistics, Dec. 2022, pp. 4261–4274. [Online]. Available: https://aclanthology.org/2022.emnlp-main.286\n\n[5] Liang K, Meng L, Liu M, et al. A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal[J]. 2022.\n\n[6] Wang J, Wang B, Qiu M, et al. A Survey on Temporal Knowledge Graph Completion: Taxonomy, Progress, and Prospects[J]. arXiv preprint arXiv:2308.02457, 2023.\n\n\n2. More realistic and larger datasets should be considered, such as YAGO.\n3. The subgraph extraction procedure may take lots of time. The running time should be reported and analysis. \n4. More ablation studies should be included to illustrate the motivation of two proposed module. We can understand the motivation for why should we leverage the attributes. But can you explain how do you design frameworks of these modules? In other word, why do you come out the idea for the structure of the QRFGU in Figure 3. Why do you know it is effective?", "questions_to_authors": "See weakness.", "paper_topic_and_main_contributions": "This paper proposes a revised model, RUN-GNN, based on PRGNN, which aims to leverage two attributes, (1) sequentially of relation composition, and (2) lagged entity information propagation. The main idea of RUN-GNN is to employ a query related fusion gate unit to model the first attribute, and buffering update mechanism for the second one.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5t8rKMLtYz", "reviewer": "Reviewer_G1kj", "summary": "", "questions": "The reason to design Query Related Fusion Gate Unit. Is there any theoretical support?", "limitations": "", "rating": 3, "confidence": 5, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We will address each of your concerns and clarify any areas where you have doubts.\n\n### Q1. The writing of the paper needs to be improved. The paper aims to enhance relational rules in GNNs. But the motivation for it is not clearly stated. I suggest it should be improved in the introduction Section and display the learned rules in the experiment Section.\n\nA1:\n\nThank you for your valuable suggestion. We will carefully review the paper and improve the wording in the revised version to enhance readability and ensure that the methods and theories are easily understandable. Due to the progressive propagation of relational information during the inference process, **the relational rules applied by RUN-GNN can be traced back through the attention values of each triplet calculated in the G-GAT computation process.** We will also showcase the learned rules in the revised paper.\n\n\n\n### Q2. The strategy of buffering update mechanism is to add extra GNN layers, which is simple and can significantly increase the calculation overhead of the model.\n\nA2:\n\nThank you for your valuable comment. \n\n**Since the additional GNN computations are performed only on existing subgraphs rather than the entire knowledge graph, the increased time consumption is not unacceptable compared to the overall time consumption.**\n\nIndeed, adding additional GNN layers with the buffer update mechanism does incur extra computational resource consumption. In previous PRGNN methods such as REDGNN, the computational resource consumption increases exponentially with the number of GNN layers because each additional GNN layer requires pre-expanding the subgraph. However, in the buffer update mechanism, we do not sample subgraphs, and the additional GNN layers only propagate information within the existing subgraphs, resulting in linearly increased computational resource consumption. Therefore, **we believe that the additional computational resource consumption is acceptable compared to the improvement in inference capability brought by the buffer update mechanism.**\n\nWe will supplement the analysis of time complexity for RUN-GNN and other PRGNN methods in the appendix of the revised version. Below is a detailed analysis of the time complexity for RUN-GNN and other PRGNN methods.\n\n#### 2.1 Theoretical Analysis\n\nLet $|\\mathcal{V}|$ denote the number of entities and $|\\mathcal{F}|$ denote the number of fact triplets. Similar to the analysis in the NBF-Net paper, we decompose the time complexity of the model into two parts: MESSAGE and AGGREGATE.\n\n**The overall time complexity of RUN-GNN, which consists of $L$ GNN layers in the exploration modules and $n$ GNN layers in the buffer modules, can be expressed as $O((\\min(nD^L,(L+n)|\\mathcal{F}|) +|\\mathcal{V}|)d^2)$,** where $d$ is the dimension of relation representations in the model, $D$ is the average degree of the knowledge graph $\\frac{|\\mathcal{F}|}{|\\mathcal{V}|}$, $|\\mathcal{V}|$ is the number of entities, and $|\\mathcal{F}|$ is the number of fact triples.\n\nThe time complexity comparison of these models is shown in the following table.\n\n| Methods | Subgraph sample | MESSAGE  | AGGREGRATE | Basic layer                                           | Buffer update                  | Total                                                     |\n| ------- | --------------- | -------- | ---------- | ----------------------------------------------------- | ------------------------------ | --------------------------------------------------------- |\n| NBF-Net | no              | $O(d)$   | $O(d^2)$   | $O(L(\\|\\mathcal{F}\\|d+\\|\\mathcal{V}\\|d^2))$           | no                             | $O(L(\\|\\mathcal{F}\\|d+\\|\\mathcal{V}\\|d^2))$               |\n| REDGNN  | yes             | $O(d)$   | $O(d^2)$   | $O(min(D^L,L\\|\\mathcal{F}\\|) d+\\|\\mathcal{V}\\|d^2)$   | no                             | $O(min(D^L,L\\|\\mathcal{F}\\|) d+\\|\\mathcal{V}\\|d^2)$       |\n| RUN-GNN | yes             | $O(d^2)$ | $O(d^2)$   | $O(min(D^L,L\\|\\mathcal{F}\\|) d^2+\\|\\mathcal{V}\\|d^2)$ | $min(D^L,\\|\\mathcal{F}\\|)nd^2$ | $O((min(nD^L,(L+n)\\|\\mathcal{F}\\|) +\\|\\mathcal{V}\\|)d^2)$ |\n\n#### 2.2 Time Measurement and Empirical Analysis\n\n| Methods     | GNN layers number in Exploration Module | GNN layers number in Buffer Module | Time cost/per epoch | MRR        |\n| ----------- | --------------------------------------- | ---------------------------------- | ------------------- | ---------- |\n| NBF-Net     | 5                                       | 0                                  | 3840                | 0.5439     |\n| *REDGNN*    | *5*                                     | *0*                                | *218*               | *0.5447*   |\n| *REDGNN*    | *8*                                     | *0*                                | *4457*              | *0.5646*   |\n| **RUN-GNN** | **5**                                   | **0**                              | **460**             | **0.5636** |\n| **RUN-GNN** | **5**                                   | **3**                              | **508**             | **0.5703** |\n\nAs shown in the table above, NBF-Net incurs much higher training time for 1 epoch when the number of GNN layers in the exploration module is 5, due to its direct message passing on the entire knowledge graph.\n\nWhen the number of GNN layers in the buffer module is 0, i.e., without using the buffer update mechanism, the model's performance already surpasses that of REDGNN and NBF-Net with 5 GNN layers in the exploration module. In fact, it even approaches the performance of REDGNN with 8 GNN layers, which takes 8 times longer to train.\n\n**When the number of GNN layers in the buffer module is 3, i.e., using the buffer update mechanism, the model's inference capability is further improved while only increasing the time cost by $\\frac{1}{9}$. It clearly outperforms REDGNN with 8 GNN layers, which consumes more resources.**\n\n###  Q3.There are missing some references, for example, some recent KG inductive methods.\n\nA3:\n\nThank you for your valuable suggestion. We will incorporate more references in the revised version.\n\nThe additional references we plan to include, but are not limited to, are [1, 2, 3, 4, 5, 6, 7].\n[1] Wang C, Zhou X, Pan S, et al. Exploring Relational Semantics for Inductive Knowledge Graph Completion[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(4): 4184-4192.\n\n[2] Galkin M, Zhu Z, Ren H, et al. Inductive logical query answering in knowledge graphs[J]. Advances in Neural Information Processing Systems, 2022, 35: 15230-15243.\n\n[3] Xu X, Zhang P, He Y, et al. Subgraph neighboring relations infomax for inductive link prediction on knowledge graphs[J]. arXiv preprint arXiv:2208.00850, 2022.\n\n[4] Pan Y, Liu J, Zhang L, et al. Inductive relation prediction with logical reasoning using contrastive representations[C]//Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022: 4261-4274.\n\n[5] Lin Q, Liu J, Xu F, et al. Incorporating context graph with logical reasoning for inductive relation prediction[C]//Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2022: 893-903.\n\n[6] Mai S, Zheng S, Yang Y, et al. Communicative message passing for inductive relation reasoning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(5): 4294-4302.\n\n[7 ]Chen J, He H, Wu F, et al. Topology-aware correlations between relations for inductive link prediction in knowledge graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(7): 6271-6278.\n\n###  Q4. Figure 4 is confusing and hard to follow.\n\nA4:\n\nWe sincerely apologize for the confusion caused by the description of section 4.3.3 and Figure 4. We will carefully review the relevant content and optimize the experimental description to improve the readability of the paper.\n\nSection 4.3.3 aims to validate and demonstrate that our proposed QRFGU can effectively model the sequentiality of compositional relations in PRGNN.\n\nWe select lots of common relational paths from the WN18RR dataset and revers the order of relations in these paths to obtain a set of reversed relational paths. For example, we reverse the order of relations in the path $father(x,y)\\wedge daughter(y,z)$ to obtain $daughter(x,y)\\wedge father(y,z)$. We encode the original relational paths and the reversed relational paths separately using the original RUN-GNN (represented as w/ QRFGU) and a variant using element-wise addition as the MESSAGE function (represented as w/o QRFGU). This result in four sets of representations. We map these representations to a 2-dimensional space and plot the representations of different sets of relational paths using different colored dots in Figure 4. We also connect the representations of the reversed relational paths and their corresponding original order relational paths using colored lines.\n\n**In Figure 4, there are no distinct orange lines, indicating that the representations of different order combinations of the same relation generated by the variant w/o QRFGU are very close.** The model fails to capture the sequentiality of compositional relations and cannot distinguish between these representations.\n\nOn the other hand, **there are clear green lines in Figure 4, indicating that the representations of different order combinations of the same relation generated by RUN-GNN (w/ QRFGU) have significant differences.** The model successfully captures the sequentiality of compositional relations and can distinguish between these representations.\n\nThe table below lists the symbols used in Figure 4 to represent the different sets of representations.\n\n|               | RUN-GNN（w/ QRFGU）    | Variant w/o QRFGU          |\n| ------------- | ---------------------- | -------------------------- |\n| Normal order  | Blue big  solid circle | Pink big  solid circle     |\n| Inverse order | Deep Blue star         | Purple small  solid circle |\n\n### Q5. The reason to design Query Related Fusion Gate Unit. Is there any theoretical support?\n\nMany thanks. We will provide a clearer explanation of the theoretical support for the design of QRFGU in the subsequent revised version.\n\nThe QRFGU aims to address the issue of existing PRGNN methods being unable to model the sequentiality of relation composition. In order for RUN-GNN to correctly encode the semantics of relation rules, we consider several factors when designing QRFGU.\n\n1. Correctly encoding the semantics of relation rules helps the model perform accurate reasoning. The sequentiality of relation composition indicates that the order of relation combinations determines the semantics of relation rules. Therefore, PRGNN requires a MESSAGE function that can model the sequentiality of relation composition.\n\n2. RNN is a classic neural network widely used for sequence modeling, which can effectively capture properties such as the sequentiality of sequences.\n\n3. The reasoning ability of PRGNN comes from selecting and encoding relation rules from relational paths. Path-based reasoning methods, such as RNNLogic [3], also often use RNN to encode relational paths.\n\n4. The GRU in RNN includes various gates similar to attention mechanisms and a forget mechanism similar to residual connections, which can effectively model complex sequences.\n\nTherefore, **we chose GRU [4] as the basic structure of QRFGU, ensuring that QRFGU can effectively model sequentiality.**\n\nFurthermore, considering the importance of query relations in relation rule selection and encoding, **we incorporate query relations into the computation process of the forget gate and update gate. This allows the model to adjust the encoding of relation rule representations based on the query relation.** \n\nIn addition, we have validated the effectiveness of the QRFGU in the ablation experiments of section 4.3.1. Furthermore, in section 4.3.3, we experimentally have verified the effectiveness of QRFGU in modelling the sequentiality of relation composition.\n\n[1] Zhu Z, Zhang Z, Xhonneux L P, et al. Neural bellman-ford networks: A general graph neural network framework for link prediction[J]. Advances in Neural Information Processing Systems, 2021, 34: 29476-29490.\n\n[2] Zhang Y, Yao Q. Knowledge graph reasoning with relational digraph[C]//Proceedings of the ACM web conference 2022. 2022: 912-924.\n\n[3] Qu M, Chen J, Xhonneux L P, et al. RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs[C]//International Conference on Learning Representations. 2020.\n\n[4] Chung J, Gulcehre C, Cho K, et al. Empirical evaluation of gated recurrent neural networks on sequence modeling[C]//NIPS 2014 Workshop on Deep Learning, December 2014. 2014.\n\n### Q6. Missing some inductive reasoning methods, such as: Inductive Relation Prediction with Logical Reasoning Using Contrastive Representations, Incorporating Context Graph with Logical Reasoning for Inductive Relation Prediction.\n\nThank you for your valuable feedback. We have conducted further research on the inductive reasoning method based on your suggestions and will supplement the missing references in the subsequent revised version to enhance the quality of the paper. The following are some of the literature sources [1, 2, 3, 4, 5, 6, 7] we have researched, which will be included in the references section of the revised version. \n\n[1] Wang C, Zhou X, Pan S, et al. Exploring Relational Semantics for Inductive Knowledge Graph Completion[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(4): 4184-4192.\n\n[2] Galkin M, Zhu Z, Ren H, et al. Inductive logical query answering in knowledge graphs[J]. Advances in Neural Information Processing Systems, 2022, 35: 15230-15243.\n\n[3] Xu X, Zhang P, He Y, et al. Subgraph neighboring relations infomax for inductive link prediction on knowledge graphs[J]. arXiv preprint arXiv:2208.00850, 2022.\n\n[4] Pan Y, Liu J, Zhang L, et al. Inductive relation prediction with logical reasoning using contrastive representations[C]//Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022: 4261-4274.\n\n[5] Lin Q, Liu J, Xu F, et al. Incorporating context graph with logical reasoning for inductive relation prediction[C]//Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2022: 893-903.\n\n[6] Mai S, Zheng S, Yang Y, et al. Communicative message passing for inductive relation reasoning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(5): 4294-4302.\n\n[7 ]Chen J, He H, Wu F, et al. Topology-aware correlations between relations for inductive link prediction in knowledge graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(7): 6271-6278.\n\n\n\nTo summarize, I sincerely appreciate your valuable suggestions and  comments. I trust that this solution addresses your concerns and enhances the paper's overall quality.", "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": "(1) Based on RED-GNN and NBFNet, the paper proposes RUN-GNN to enhance relational rules, where a query related fusion gate unit and a buffering update mechanism are proposed.\n(2) extensive experiments are carried out, including the transductive and inductive settings for link prediction. The results demonstrate the effectiveness of the proposed method.", "reasons_to_reject": "(1) The writing of the paper needs to be improved. The paper aims to enhance relational rules in GNNs. But the motivation for it is not clearly stated. I suggest it should be improved in the introduction Section and display the learned rules in the experiment Section.\n(2) The strategy of buffering update mechanism is to add extra GNN layers, which is simple and can significantly increase the calculation overhead of the model.\n(3) There are missing some references, for example, some recent KG inductive methods.\n(4) Figure 4 is confusing and hard to follow.\n", "questions_to_authors": "The reason to design Query Related Fusion Gate Unit. Is there any theoretical support?", "paper_topic_and_main_contributions": "Based on previous works, this paper aims to enhance the relational rules for knowledge graph link prediction. It addresses the issues of the sequentiality of relation composition and the lagged entity information propagation.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "Missing some inductive reasoning methods, such as: Inductive Relation Prediction with Logical Reasoning Using Contrastive Representations, Incorporating Context Graph with Logical Reasoning for Inductive Relation Prediction."}}, {"review_id": "ky3XRvW4QZ", "reviewer": "Reviewer_55BH", "summary": "", "questions": "- Can you more clearly justify the design choice for the components of your architecture e.g., reason for choosing G-GAT layers etc. \n- What is the time complexity of your proposed approach? ", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments. We will address each of your concerns and clarify any areas where you have doubts.\n\n### Q1. In general, I have a concern regarding the novelty of the work, as it appears to simply be a combination of already proposed methods e.g., G-GAT layers, MLP etc.\n\nA1:\n\nWe appreciate your valuable comments.\n\nFirst and foremost, we need to clarify that **the G-GAT layer is an original component designed to enable the model to capture the sequentiality of compositional relations.** \n\nIt is important to note that although we also employ attention mechanisms in graph neural networks, our G-GAT differs from GAT in the following aspects:\n\n1. **Different application scenarios**: GAT is used in regular graphs, while our G-GAT is specifically designed for knowledge graphs. As G-GAT is applied to knowledge graphs, it requires the use of QRFGU to combine the head entities and relationships of the edges, which is not necessary in GAT.\n\n2. **Different factors in computing attention**: GAT computes attention values based on the head and tail entities of the edges, without considering the relationships on the edges. On the other hand, our G-GAT only considers the messages to be propagated on the edges and the query relationship for the entire reasoning process, without considering the tail entities.\n\nBy incorporating the fusion of the representations of the head entities and relationships **using G-GAT, the model is able to better capture the sequentiality of compositional relations and even more complex properties of relational rules.** \n\nOn the other hand, we believe that the innovation of RUN-GNN lies not in the assembly of components, but the followings:\n\nDuring the analysis of PRGNN's operation, we identified two properties that affect the reasoning ability of PRGNN. \n\n**(1) The sequentiality of relation composition can impact the model's ability to correctly encode semantic information about relational rules.**\n\n**(2)  The lagged entity information propagation makes it difficult for the model to identify the correct relational rules.** \n\nHowever, existing PRGNN methods overlook these two properties. To address these issues, **we propose QRFGU and apply the G-GAT layer to encode relational rules**, which allows for modeling the sequentiality of relation composition. Additionally, **we introduce a buffering update mechanism to tackle the lagged entity information propagation.** \n\n---\n\n### Q2. The relation works section is incomplete. Further, regarding the problem definition methodology, the authors also need to describe which view of the knowledge graph is part of the assumption e.g., instance-view, ontology-view, two-view KG etc.\n\nA2:\n\nThank you for your valuable suggestion and comments. \n\nFirstly, our approach is a method that learns and applies relational rules from factual triples in a knowledge graph using neural networks for link prediction. Therefore, it falls under the category of **instance-view methods**. We will clarify this point in the subsequent revised version of the paper.\n\nSecondly, in the related work, **we have followed the mainstream practices in knowledge graph link prediction and categorized previous methods based on how they utilize information from the knowledge graph.** Similar approaches have been adopted in existing studies [1], [2] to classify related work. Furthermore, research on knowledge graph link prediction presents related work from various perspectives based on the thematic needs of the paper. For example, paper [3] categorizes related work into Translational Distance Models, Semantic Matching Models, and GNN-based Models. Paper [4] categorizes related work into Transductive relation prediction and Inductive relation prediction.\n\n[1] Zhu Z, Zhang Z, Xhonneux L P, et al. Neural bellman-ford networks: A general graph neural network framework for link prediction[J]. Advances in Neural Information Processing Systems, 2021, 34: 29476-29490.\n\n[2] Zhang Y, Yao Q. Knowledge graph reasoning with relational digraph[C]//Proceedings of the ACM web conference 2022. 2022: 912-924.\n\n[3] Li R, Cao Y, Zhu Q, et al. How does knowledge graph embedding extrapolate to unseen data: a semantic evidence view[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2022, 36(5): 5781-5791.\n\n[4] Mai S, Zheng S, Yang Y, et al. Communicative message passing for inductive relation reasoning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2021, 35(5): 4294-4302.\n\n---\n\n### Q3. Can you more clearly justify the design choice for the components of your architecture e.g., reason for choosing G-GAT layers etc.\n\nA3:\n\nMany thanks. \n\nWe will clarify the design principles of our method and the factors considered when selecting components in the revised version. Below, we will rephrase some of our considerations in model structure and component design.\n\nMethods based on PRGNN, such as NBF-Net  and REDGNN, derive their reasoning capabilities from encoding relational rules in the model.\n\nIn the aforementioned process, **ensuring that the model can encode valid relational rules and correctly encode the semantics of relational rules becomes crucial.** During the analysis of PRGNN's operation, we identified two properties that affect the reasoning ability of PRGNN. \n\n**(1) The sequentiality of relation composition can impact the model's ability to correctly encode semantic information about relational rules.**\n\n**(2)  The lagged entity information propagation makes it difficult for the model to identify the correct relational rules.** \n\nHowever, existing PRGNN methods overlook these two properties. To address these issues, **we propose QRFGU and apply the G-GAT layer to encode relational rules**, which allows for modeling the sequentiality of relation composition. Additionally, **we introduce a buffering update mechanism to tackle the lagged entity information propagation.** \n\n#### 3.1 QRFGU\n\nThe QRFGU aims to **address the issue of existing PRGNN methods being unable to model the sequentiality of relation composition** We consider multiple factors when designing QRFGU.\n\n1. Encoding the semantics of relation rules correctly helps the model perform accurate reasoning. The sequentiality of relation composition indicates that the order of relation composition determines the semantics of relation rules. Therefore, PRGNN requires a MESSAGE function that can model the sequentiality of relation composition.\n\n2. RNN is a classic neural network widely used for sequence modeling, capable of effectively capturing properties such as sequence order.\n\n3. The reasoning ability of PRGNN comes from selecting and encoding relation rules from relational paths. Path-based reasoning methods, such as RNNLogic [1], often use RNN to encode relational paths.\n\n4. GRU in RNN includes various gates similar to attention mechanisms and a forget mechanism similar to residual connections, making it suitable for modeling complex sequences.\n\nTherefore, **we chose GRU [2] as the basic structure of QRFGU, ensuring that QRFGU can effectively model the sequentiality.**\n\nFurthermore, considering the importance of the query relation in relation rule selection and encoding, we **incorporate the query relation into the computation process of the forget gate and update gate, allowing the model to adjust the encoding of relation rule representation based on the query relation.**\n\n[1] Qu M, Chen J, Xhonneux L P, et al. RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs[C]//International Conference on Learning Representations. 2020.\n\n[2] Chung J, Gulcehre C, Cho K, et al. Empirical evaluation of gated recurrent neural networks on sequence modeling[C]//NIPS 2014 Workshop on Deep Learning, December 2014. 2014.\n\n#### 3.2 G-GAT layer\n\nWe refer to the GNN layer proposed and used in RUN-GNN as the Gated Graph Attention Network (G-GAT) layer.\n\nThe G-GAT layer is the fundamental unit of RUN-GNN and consists of the following components:\n\n1. The MESSAGE function combines the relation rule representation of the head entity in the triple with the representation of the relation to generate the candidate rule representation for the tail entity. Unlike existing methods like CompGCN [1, 2, 3] that use triple-based scoring functions, we use QRFGU, which can model the sequentiality and even more complex properties of relation composition.\n\n2. The AGGREGATE function selects the most important candidate rule representations from multiple candidate rule representations corresponding to the same tail entity and generates the rule representation for the tail entity. Considering the influence of the query relation on the applied relation rules during reasoning, we employ a graph attention mechanism related to the query relation [4].\n\n[1] Vashishth S, Sanyal S, Nitin V, et al. Composition-based Multi-Relational Graph Convolutional Networks[C]//International Conference on Learning Representations. 2019.\n\n[2] Zhu Z, Zhang Z, Xhonneux L P, et al. Neural bellman-ford networks: A general graph neural network framework for link prediction[J]. Advances in Neural Information Processing Systems, 2021, 34: 29476-29490.\n\n[3] Zhang Y, Yao Q. Knowledge graph reasoning with relational digraph[C]//Proceedings of the ACM web conference 2022. 2022: 912-924.\n\n[4] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017.\n\n\n\nIn addition, we have validated the effectiveness of the model structure and components in the ablation experiments of section 4.3.1. Furthermore, in sections 4.3.2 and 4.3.3, we experimentally have verified the effectiveness of our proposed method in addressing the two challenges.6\n\n---\n\n### Q4. What is the time complexity of your proposed approach?\n\nA4:\n\nMany thanks. \n\nThe **overall time complexity of RUN-GNN**, which consists of $L$ GNN layers in the exploration modules and $n$ GNN layers in the buffer modules, can be **expressed as** $O((\\min(nD^L,(L+n)|\\mathcal{F}|) +|\\mathcal{V}|)d^2)$, where $d$ is the dimension of relation representations in the model, $D$ is the average degree of the knowledge graph $\\frac{|\\mathcal{F}|}{|\\mathcal{V}|}$, $|\\mathcal{V}|$ is the number of entities, and $|\\mathcal{F}|$ is the number of fact triples. We will add a description and analysis of the model's time complexity in the appendix in future revisions.\n\nBelow is a detailed analysis of the time complexity of RUN-GNN and other PRGNN methods.\n\n#### 4.1 Theoretical Analysis\n\nLet $|\\mathcal{V}|$ be the number of entities and $|\\mathcal{F}|$ be the number of fact triples. Similar to the analysis in the NBF-Net paper, we decompose the time complexity of the model into the MESSAGE and AGGREGATE parts.\n\n##### 4.1.2 Time Complexity of NBF-Net\n\nThe time complexity of the MESSAGE function in NBF-Net is $O(d)$, and the time complexity of the AGGREGATE function is $O(d^2)$. Since each information propagation is performed on the entire knowledge graph, the overall time complexity is $O(L(|\\mathcal{F}|d+|\\mathcal{V}|d^2))$.\n\n##### 4.1.3 Time Complexity of REDGNN\n\nThe time complexity of the MESSAGE function in REDGNN is $O(d)$, and the time complexity of the AGGREGATE function is $O(d^2)$. Therefore, the overall time complexity of REDGNN is $O(\\min(D^L,L|\\mathcal{F}|) d+|\\mathcal{V}|d^2)$.\n\n##### 4.1.4 Time Complexity of RUN-GNN\n\nRUN-GNN also performs progressive information propagation by sampling a series of subgraphs centered around the query entity, from small to large, and performing message passing on these subgraphs sequentially. The buffer update mechanism in RUN-GNN does not involve additional subgraph sampling after message passing in the GNNs of all exploration modules. Instead, it continues to perform message passing on the largest subgraph used in the current reasoning process. Therefore, this step does not incur additional time cost for subgraph sampling.\n\nIts MESSAGE function is QRFGU, which is essentially a variant of GRU function with additional attention, with a time complexity of $O(d^2)$. The AGGREGATE function is a simple linear transformation with a time complexity of $O(d^2)$. Therefore, the overall time complexity of RUN-GNN with L GNN layers in the exploration modules and n GNN layers in the buffer modules is $O((\\min(nD^L,(L+n)|\\mathcal{F}|) +|\\mathcal{V}|)d^2)$.\n\nBased on the analysis above, the time complexity comparison of these models is shown in the following table.\n\n| Methods | Subgraph sample | MESSAGE  | AGGREGRATE | Basic layer                                           | Buffer update                  | Total                                                     |\n| ------- | --------------- | -------- | ---------- | ----------------------------------------------------- | ------------------------------ | --------------------------------------------------------- |\n| NBF-Net | no              | $O(d)$   | $O(d^2)$   | $O(L(\\|\\mathcal{F}\\|d+\\|\\mathcal{V}\\|d^2))$           | no                             | $O(L(\\|\\mathcal{F}\\|d+\\|\\mathcal{V}\\|d^2))$               |\n| REDGNN  | yes             | $O(d)$   | $O(d^2)$   | $O(min(D^L,L\\|\\mathcal{F}\\|) d+\\|\\mathcal{V}\\|d^2)$   | no                             | $O(min(D^L,L\\|\\mathcal{F}\\|) d+\\|\\mathcal{V}\\|d^2)$       |\n| RUN-GNN | yes             | $O(d^2)$ | $O(d^2)$   | $O(min(D^L,L\\|\\mathcal{F}\\|) d^2+\\|\\mathcal{V}\\|d^2)$ | $min(D^L,\\|\\mathcal{F}\\|)nd^2$ | $O((min(nD^L,(L+n)\\|\\mathcal{F}\\|) +\\|\\mathcal{V}\\|)d^2)$ |\n\n#### 4.2 Time Measurement and Empirical Analysis\n\n| Methods     | GNN layers number in Exploration Module | GNN layers number in Buffer Module | Time cost/per epoch | MRR        |\n| ----------- | --------------------------------------- | ---------------------------------- | ------------------- | ---------- |\n| NBF-Net     | 5                                       | 0                                  | 3840                | 0.5439     |\n| *REDGNN*    | *5*                                     | *0*                                | *218*               | *0.5447*   |\n| *REDGNN*    | *8*                                     | *0*                                | *4457*              | *0.5646*   |\n| **RUN-GNN** | **5**                                   | **0**                              | **460**             | **0.5636** |\n| **RUN-GNN** | **5**                                   | **3**                              | **508**             | **0.5703** |\n\nAs shown in the table above, NBF-Net has a much higher training time for 1 epoch when the number of GNN layers in the exploration module is 5, as it performs message passing directly on the entire knowledge graph.\n\nWhen the number of GNN layers in the buffer module is 0, i.e., without using the buffer update mechanism, the model's performance already surpasses that of REDGNN and NBF-Net with 5 GNN layers in the exploration module. **The performance of RUN-GNN even approaches that of REDGNN with 8 GNN layers, which takes 8 times longer to train.**\n\n**When the number of GNN layers in the buffer module is 3, i.e., using the buffer update mechanism, the model's reasoning ability is further improved with only a $\\frac{1}{9}$ increase in time cost. It clearly outperforms REDGNN with 8 GNN layers, which requires more computational resources.**\n\n---\n\n### Q5. Missing References\n\nA5:\n\nThank you for your valuable suggestion. We will carefully reorganize the relevant sections on related work and incorporate the two types of methods [1,2,3,4] you mentioned.\n\n[1] Hao J, Chen M, Yu W, et al. Universal representation learning of knowledge bases by jointly embedding instances and ontological  concepts[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 1709-1719.\n\n[2] Iyer R G, Bai Y, Wang W, et al. Dual-geometric space embedding model for two-view knowledge graphs[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022: 676-686.\n\n[3] Wang X, Ji H, Shi C, et al. Heterogeneous graph attention network[C]//The world wide web conference. 2019: 2022-2032.\n\n[4] Iyer R G, Wang W, Sun Y. Bi-level attention graph neural networks[C]//2021 IEEE International Conference on Data Mining (ICDM). IEEE, 2021: 1126-1131.\n\n---\n\nTo summarize, I sincerely appreciate your insightful comments. I hope this solution can address your issue and enhance the paper's overall quality.", "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": "- This paper generally motivates the problem of exploration, though some important references are missing in the Related Works section. The contributions of the work are concisely summarized. \n- Architectural visualizations (particularly Figs. 2 & 3) are resourceful and follow well with the accompanied text. \n- The authors use a variety of standard benchmark datasets for KGs. Experiment results also show good performance. \n- Ablation studies visualizing and comparing the relation combination representation are insightful.\n", "reasons_to_reject": "- In general, I have a concern regarding the novelty of the work, as it appears to simply be a combination of already proposed methods e.g., G-GAT layers, MLP etc. \n- The relation works section is incomplete. Further, regarding the problem definition methodology, the authors also need to describe which view of the knowledge graph is part of the assumption e.g., instance-view, ontology-view, two-view KG etc. ", "questions_to_authors": "- Can you more clearly justify the design choice for the components of your architecture e.g., reason for choosing G-GAT layers etc. \n- What is the time complexity of your proposed approach? ", "paper_topic_and_main_contributions": "This paper proposes a knowledge graph reasoning approach, the Relational rUle eNhanced Graph Neural Network (RUN-GNN). RUN-GNN uses a query related fusion gate unit to model the sequentiality of relation composition and uses buffering update to help improve lagged entity information propagation. The authors perform experiments on various KG datasets for link prediction tasks. ", "excitement": 3, "reproducibility": 2, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "KG-based embedding methods and those utilizing non-Euclidean geometric spaces to perform learning updates have also recently been proposed: \n- KDD 2019: Universal Representation Learning of Knowledge Bases by Jointly Embedding Instances and Ontological Concepts. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery &amp; Data Mining (KDD '19). Association for Computing Machinery, New York, NY, USA, 1709–1719. https://doi.org/10.1145/3292500.3330838\n- KDD 2022: Dual-Geometric Space Embedding Model for Two-View Knowledge Graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD '22). Association for Computing Machinery, New York, NY, USA, 676–686. https://doi.org/10.1145/3534678.3539350\n\nFurthermore, SOTA GNN models for large-scale multi-relational heterogeneous graphs using hierarchical attention mechanisms have also been proposed, which are missing: \n- WWW 2019: Heterogeneous Graph Attention Network. In The World Wide Web Conference (WWW '19). Association for Computing Machinery, New York, NY, USA, 2022–2032. https://doi.org/10.1145/3308558.3313562\n- ICDM 2021: \"Bi-Level Attention Graph Neural Networks,\" 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand, 2021, pp. 1126-1131, doi: 10.1109/ICDM51629.2021.00133.\n"}}]

Author rebuttal:

Meta-review: This paper is built on top of the recent progressive relational graph neural network (PRGNN) methods for KG link prediction that has been proven to be quite effective. Specifically, this paper identifies two weaknesses of existing PRGNN methods and propose novel strategies to mitigate those. Experiments on multiple standard datasets with small KGs (WN18RR/FB15k-237/NELL-995) demonstrated the effectiveness of the proposed method, often setting a new state of the art on the datasets.

Strengths:
- The paper is well motivated and well executed. PRGNN is indeed a strong performing family of methods, and further solid improvement is meaningful. 
- The writing and presentation generally make it easy to follow the logical flow and understand the main points
- The experiment results are impressive, considering that the performance on these datasets has largely saturated. 

Weaknesses:
- As several reviewers pointed out, the paper was lacking an efficiency analysis, which is important considering that the proposed method adds new components. The authors are encouraged to incorporate that into the revised version.
- Evaluation on larger KGs such as YAGO and those in the Open Graph Benchmark would significantly strengthen the paper.
- The related work discussion is a bit insufficient for this specific topic (though the most related work seems to have been covered). The authors are encouraged to strengthen this part the revised version.
Decision: Accept-Findings