Learning Rule-Induced Subgraph Representations for Inductive Relation Prediction
Authors: Tianyu Liu
Qitan Lv
Jie Wang
Shuling Yang
Hanzhu Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: inductive relation prediction
knowledge graph completion
knowledge graph reasoning

Abstract: Inductive relation prediction (IRP)---where entities can be different during training and inference---has shown great power for completing evolving knowledge graphs. Existing works mainly focus on using graph neural networks (GNNs) to learn the representation of the subgraph induced from the target link, which can be seen as an implicit rule-mining process to measure the plausibility of the target link. However, these methods are not able to differentiate the target link and other links during message passing, hence the final subgraph representation will contain irrelevant rule information to the target link, which reduces the reasoning performance and severely hinders the applications for real-world scenarios. To tackle this problem, we propose a novel $\textit{single-source edge-wise}$ GNN model to learn the $\textbf{R}$ule-induc$\textbf{E}$d $\textbf{S}$ubgraph represen$\textbf{T}$ations $(\textbf{REST}$), which encodes relevant rules and eliminates irrelevant rules within the subgraph. Specifically, we propose a $\textit{single-source}$ initialization approach to initialize edge features only for the target link, which guarantees the relevance of mined rules and target link. Then we propose several RNN-based functions for $\textit{edge-wise}$ message passing to model the sequential property of mined rules. REST is a simple and effective approach with theoretical support to learn the $\textit{rule-induced subgraph representation}$. Moreover, REST does not need node labeling, which significantly accelerates the subgraph preprocessing time by up to $\textbf{11.66}\times$. Experiments on inductive relation prediction benchmarks demonstrate the effectiveness of our REST.

Learning Rule-Induced Subgraph Representations for Inductive Relation Prediction
Tianyu Liu'
Qitan Lv' Jie Wang Shuling Yang'
Hanzhu Chen'
University of Science and Technology of China Institute of Artificial Intelligence, Hefei Comprehensive National Science Center {tianyu_liu liu, qitanlv, slyang0916, chenhz)@mail, uste. edu, {jiewangx)@ustc. edu.cn
Abstract
Inductive relation prediction wheee entities can be different during training and inference- has shown great power for completing evolving knowledge graphs Existing works mainly focus using graph neural networks (GNNs) learn the representation of the subgraph induced from the target link, which can seen implicit rule rule-mining process measure the plausibility of the target link. However, these methods cannot differentiate the target link and other links during message passing, hence the final subgraph representation will contain irrelevant rule information to the target link, which reduces the reasoning performance and severely hinders the applications for real-world scenarios. To tackle this problem, we propose a novel single-source edge-wise GNN model to learn the Rule-induc Subgraph represenTTations (REST), which encodes relevant rules and eliminates irrelevant rules within the subgraph. Specifically, we propose a single-source initialization approach initialize edge features only for the target link, which guarantees the relevance of mined rules and target link. Then we propose several RNN-based functions for edge-wise message passing to model the sequential property of mined rules. REST is simple and effective approach with theoretical support to learn the rule-induced subgraph representation. Moreover, REST does not need node labeling, which significantly accelerates the subgraph preprocessing time by up to 11.66x. Experiments on inductive relation prediction benchmarks demonstrate the effectiveness of our REST
Introduction
Knowledge graphs are collection of factual triples about human knowledge. In recent years, knowl- edge graphs have been successfully applied in various fileds, such as natural language processing [.] question answering [2) and recommendation systems B].
However, due to issues such as privacy concerns or data collection costs, many real-world knowledge graphs are far from completion. Moreover, knowledge graphs are continuously evolving with new entities or triples emerging. This dynamic change causes even the large-scale knowledge graphs, e.g., Freebase [4), Wikidata (5) and YAGO3 6 still suffer from incompleteness. Most existing knowledge graph completion models, e.g., RotatE [7], R-GCN [8), suffer from handling emerging new entities as they require test entities be observed in training time. Therefore, inductive relation prediction, which aims at predicting missing links in evolving knowledge graphs, has attracted extensive attention [0].
"The Corresponding Author.
2 Our code is available at https: htpp::///ghhubb www./oom//r...eee http//marttttyy/ee
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The key idea of inductive relation prediction on knowledge graphs is to learn logical rules, which can capture co-occurrence patterns between relations in an
manner and can thus
naturally generalize to unseen entities [1 12] Some existing models, e.g., AMIE+ [3] Neural [PP[4], explicitly mine logical rules for inductive relation prediction with good interpretability 14] while their performances are limited due to the large searching space and discrete optimization [5] 16] Recently, some subgraph-bas based methods, e.g., GraIL[[I], TACT(22), CoMPILE have been proposed to implicitly mine logical rules by reasoning over the subgraph induced from the target link.
However, there are still some irrelevant rules [8 within the subgraph. Considering the rule body and the rule head as a cycle [1], the relevant rules are cycles that pass the target link. As illustrated in Figure I u - + + u and u - e > C2 > e1 -> are relevant rules as they pass the target link, while e1 - -> e2 el are irrelevant rules as they do not contain the target link. Existing methods cannot differentiate the target link and other links during message passing. Thus, they will mine plenty of irrelevant rules and encode them into the final subgraph representation, which makes the model prone to over-fitting and severely hinders reasoning performance.
Irvelvann Ruies
C2
Relevan Rules
target link
u
v
Relevant
In this paper. we propose a novel single-souree edge-wise GNN model to learn the Rule-inducEd Subgraph repre- senTations (REST), which encodes relevant rules and eliminates irrelevant rules within the subgraph. Specif- ically, we observe that the information flow originating from unique edge and returning to this edge will form cycle automatically, Consequently, the information flow originating from the target link can encode the relevant logical rules. Inspired by this observation, propose single-source initialization approach to assign nonzero initial embedding for the target link according to its relation and zero embeddings for other links. Then we propose several RNN-based functions for edge-wise message passing to model the sequential property of mined rules. Finally, we use the representation of the target link as the final subgraph representation.
C4
Figure Relevant and irrelevant rules.
We theoretically show that with appropriate message passing functions, REST can learn the rule- induced subgraph representation for reasoning. Notably, REST avoids the heavy burden of node labeling in subgraph preprocessing, which significantly accelerates the time of subgraph preprocess- ing by up to 11.66x. Experiments on inductive relation prediction benchmarks demonstrate the effectiveness of our REST.
2 Related Work
Existing works for IRP can be mainly categorized into rule-based methods and subgraph-based methods. While rule-based methods explicitly learn logical rules in knowledge graphs, subgraph- based methods implicitly mine logical rules by learning the representation subgraphs. Moreover, we discuss some graph neural network methods that reason over the whole graph.
Rule-based methods. Rule-based approaches mine logical rules that independent of entities and describe co-occurrence patterns of relations to predict missing factual triples. Such a rule consists of head and body, where head is single atom, i.e., fact in the form of Relation head entity, tail entity), and body is a set of atoms. Given a head R(y. .)) and a body { [B B2. ... B,, }. there is a Bn. The rule-based methods have been studied for a long time in Inductive Logic Programming (20). yet traditional approaches face the challenges of optimization and scalability, Recently, Neural LP 14] presents an end-to-end differentiable framework that enables modern gradient- based optimization techniques to learn the structure and parameters of logical rules. DRUM analyzes Neural LP from the perspective of low-rank tensor approximation and uses bidirectional RNNs to mine more accurate rules. Moreover, for automatically learning rules from large knowledge graphs, RLvLR [22 proposes an effective rule searching and pruning strategy, which shows promising results on both scalability and accuracy for link prediction. However, these explicit rule-based methods lack expressive power due rule-based nature, and cannot scale to large knowledge graphs as well.
rule R(y, 2) < B, A B2

---

Subgraph-based methods. Subgraph-based methods extract a local subgraph around the target link and use GNNs to learn subgraph representation to predict link existence. Such a subgraph is usually induced by the neighbor nodes of the target link, which encodes the rules related to the target link. Grall- [1 is the first subgraph-basd -hasd inductive relation prediction model. It deñines the enclosing subgraph as the graph induced by all the nodes in the paths between two target nodes. After labeling all the nodes with double radius vertex labeling [23]. it employs R-GCNs to learn subgraph representation. COMPILE[11 extracts directed enclosing subgraphs to handle the asymmetric / anti-symmetric patterns the target link. T2CT converts the original enclosing subgraph into relational correlation graph, and proposes relational correlation network model different correlation patterns between relations. More recently, SNRI 24) extracts enclosing subgraphs with complete neighboring relations consider neighboring relations for reasoning. ConGLR [5] converts the original enclosing subgraph into a context graph to model relational paths. However, these methods cannot differentiate the target link and other links during message passing. Therefore, the GNNs will mine plenty of irrelevant rules for other links and encode them into subgraph representation, which reduces the accuracy of reasoning.
Graph neural network for link prediction. Some methods use GNNs to reason over the whole graph rather than subgraph for inductive relation prediction. INDIGO 26 converts the KG into a aone-annotated graph and fully encodes it into a GNN. NBFNet 27 generalizes Bellman- algorithm and proposes general GNN framework to learn path representation for link prediction. MorsE [28] considers transferring entity- independent meta- meta--nowledde by GNNs. While these methods share some spirit with subgraph-based methods, they essentially different with subgraph- based methods. These methods need to reason over the whole graph for a test example, while subgraph-based methods only need to reason over subgraph. Meanwhile, these methods tend to predict entities rather than relations for a query, while subgraph-ban based methods tend to predict relations, the subgraph only needs to be extracted once for relation prediction. As these methods benefit from a larger number of negative sampling, we do not take them into comparison.
3 Problem Definition
We define a training graph as = Rer, ERtr,Th, Tir), where Eir, Rar, and Tir C X Rir x Eer are the set of entities, relations and triples during training, respectively. We aim to train a model such that for any graph G (E', R', T') whose relations
all seen during training (i.e., R' C Ru), the model can predict missing triples in G', ie.. (?, rt, v), (u, ?, v), (u, re, ?), where u, U E E' and T; E R'. We denote the set of any possible entities as {E} and the set of knowledge graphs whose relation set R are subset of Rr as (9]r.. The model we would like to train is a score function f ( {E} Rir x {ε} -> R, (G', v)) f('' u. v), where g' (E', R', T",, R' Ru and u, V E El. For query triple (u, re, ?). we enumerate valid candidate tail entities of and use the model get the score s' of this triple (2, v'). We call the query triple (u, Ft, v) target link and u, as targel nodes, respectively.
4 Methodology
In this section, we describe the architecture of the proposed REST in detail. Following existing subgraph-ban based methods, we first extract a subgraph for each query triple. Then we apply single- source initialization and edge-wise message passing to update edge features iteratively. Finally, the representation of the target link is used for scoring. REST organizes the two methods in a unified framework to perform inductive relation prediction. Figure 2 ggives overview of REST.
4.1 Subgraph Extraction
For query triple rt. v), the subgraph around it contains the logical rules to infer this query, thus we extract a local subgraph SG implicitly learn logical rules for reasoning. Specifically, we first compute the k-hop neighbors (u) and Ne(e) of the target nodes u and v. Then we define enclosing subgraph as the graph induced by A& (u) (1) and unclosing subgruph as the graph induced by (u) U UNa(()) Note that the subgraph extraction process of our REST omits the node labeling, as node features are unnecessary edge-wise message passing, which significantly reduces the time cost of subgraph preprocessing.
3

---

T4
0
0
1 Tt
F7
%
1. Extracted local subgraph for the target link (u, v).
Single- source initialization for all edges within the subgraph.
3. Edge-wise message passing to update edge representations. Finally, output the representation of the target link e ex, to calculate its plausibility.
Figure 2: An overview of REST. REST organizes the single-source initialization method and the edge-wise message passing method in unified framework to learn relevant rules representations within the subgraph for the target link. Different relevant rules are shown in different colors part
4.2 Single-source Initialization
Single-source initialization is simple and effective initialization approach, which initializes a nonzero embedding the query triple according to and zero embeddings for other triples. Specifically, the embeddings of links and nodes within SGu,ry are initialized as follows:
Ty:
if (I, v. = (u, Te, v) if (x, v, + (u, v)
(u,r,)) (x, 10
(I)
h for Vu E
where c..y, and h. are the initial representation of edge (x, y. 2) and node respectively. 1 is the indicator function differentiate the target link and other links. Hadamard product. Note that the representation of nodes is used as temporary variables in edge-wise message passing. With this initialization approach, we ensure the relevance between mined rules and the target link.
Edge-wise Message Passing
After initializing all the edges and nodes, we perform edge-wise message passing to encode all relevant rules into the final subgraph representation. Specifically, each iteration of edge-wise message passing consists of three parts, (1) upplying message function to every link, (2) updating node features by aggregating message and (3) updating edge features by temporary node features, which are described as follows:
m m MESSAGE(H R- (....rr,) (h @ ryy) (eryle 8 ry)
(2)
h AGGRAGATE (m. =
m R.9.2
(2.HA)ET
(T.
D. UPDATE(H (.))) h
Here, W,, (D, o, 00 2 binary operators which denote function to parameterize. + denotes the large size operator of @ h and ex ex..: respectively represent the feature of node and link (x, y, 2) after & iterations of edge-wise message passing. We visualize the comparison between conventional message passing framework developed by Grall. [T] and proposed edge-wise wise message passing framework in Figure

---

Hode Labiios
Initializer
Ralenia
Initializer
Aupel Ausove
RS
Layer
Layer
(a) Original Graph
Initialization
Layer 2
Layer
Message Function
Aggregate Function
Update Function
Readout Function
Subgraph Representation
Subgraph Repersemaation
(b) Conventional Message Passing Framework
(c) Edge-wise Message Passing Framework
Figure 3: Comparison between conventional message passing framework developed by GralL and our REST. First, REST initializes node and edge features with single-source initialization. Then, REST employs UPDATE function to update edge features. Finally, REST directly uses the embedding of the target link the final subgraph representation, rather than the pooling of all node embeddings.
4.4 RNN-based Functions
Message passing functions existing works use order-indeppedent binary operators such as ADD and MUL, which cannot model the sequential property of rules and lead to incorrect rules (1]. To tackle this problem, we introduce several RNN-base methods as message passing functions.
Message Functions. For the edge-wise message passing process, each iteration REST takes in h - and ry to form message. We modify GRU as message function as follows:
2,9.e
6₁ 0g W T @
k-1
W R- + by)
z.g.
7/k 0g W
W W h b
7.1
(5)
C = O &W
W O h )
c.
k m m 6 ck
8x) h
Here, ô5 is the update gate vector, N is the reset gate vector and is the candidate activation vector. The operator @ denotes the Hadamard product, 0g denotes Sigmoid activation function and o% denotes Tanh activation function. During each iteration of message passing, we only use GRU once, therefore k-layer message passing includes GRUs, which can model sequence with length I S k.
Aggregate Functions. The aggregate function aggregates messages for each node from its neighbor- ing edges. Here, use simplified PNA 30) consider different types of aggregation.
h
(m (m:), h (m.v.)ET
(m "p.2))
(R.g.a)TT
h min (n.
(m* 2) h = std (a.g.=)ET
(m* (
(6)
h
W Wgg
h h hh h [11
Here, [:] denotes the concatenation vectors, W agg denotes the linear transformation matrix in the k-th layer.
Update Functions.
The update function is used to update the edge feature. We propose to update the edge feature with LSTM(31). Specifically, LSTM needs three inputs: hidden vector, current
5

---

input vector and a cell vector. We use h the hidden vector and k=1 ez.32 as the current input vector. Moreover, expect that each edge can differentiate the target link during message passing, which requires each edge to specify the query information. Therefore, we initialize each edge with another query feature as the cell vector. All the edges are initialized with the same query embedding ră related to the query relation
Lm = r
(7)
Then the update function can be described as follows:
g. gz
LSTM( R-1 2,0.21 Gz.g h
(8)
After updating the edge feature by iterations of edge-wise message passing, we output e as subgraph representation. Then we use linear transformation and activation function get the score the target link.
f(u, T1, v) = (W,e + b.)
Analysis
In this section, we theoretically analyze the effectiveness of our REST. We first define the rule-induced subgraph representation, which utilizes encoded relevant rules infer the plausibility of the target link. Then we show that our REST is able to learn such a rule-induced subgraph representation for reasoning.
5.1 Rule-induced Subgraph Representation Formulation
Our rule-induced subgraph representation aims to encode all relevant rules into the subgraph repre- sentation for reasoning. Therefore, we can define the rule-induced subgraph representation as the aggregation of these relevant rules:
Surii
Pe CEC
(10)
where C' denotes the set of all possible relevant rules within SQu.r,, and p.: is the representation of relevant rule c. Following the idea of Neural LP associate each relation in the rule with weight, we model the representation of a rule as function of its relation set. Therefore, we give the definition of rule-induced subgraph representation.
Definition (Rule-induced subgraph representation.) Given subgraph Sguri its rule- induced subgraph representation is defined as follows:
Suree
Ontrr X 0,2 8 @ a
(11)
1=1 (u.re.a) (a.) (2,- 9-1---1---- 2,03)
where i denotes the length of the cycle, Ty, is the representation of relation yo (Ii, Vi. is an existing triple in SGu. {lu Tt, v), (v,30, yo. To),.., (Zi-3, 2i- u)} is a cycle at length i.
Note that and & denote binary aggregation functions. Intuitively, rule-induced subgraph represen- tation captures all relevant rules within the subgraph and is expressive enough for reasoning.
5.2 Rule-induced Subgraph Representation Learning
Here, we show that our REST can learn such rule-induced subgraph representation. First, we show this in a simple case.
Theorem Single-source edge-wise GNN can learn rule-induced subgraph representation if +,0= @¹ = =x, 2 = X, i.e., there exists nonzero oi.j such that
+, C
ek earre
Σ (M. (0.00.20)
Σ (21-9-h-2:0)
anlrr X Q42 X Cityn-2
(12)
1=1

---

We prove this in Appendix A This theorem states that our REST can learn the rule- rule-induced subgraph representation in the basic condition. Then we generalize this theorem to a general version.
Theorem Single-source edge-wise GNN can learn rule-induced subgraph representation if B.0 L o @ @0 = 8, 8 = 8, where @ and @ are binary operators that satisfy 0 @ a a. 2 a = 0. i.e, there exists nonzero 04, such that
oarr, @ yo 1 8 2
(13)
1=1
(u,P),0) (v.g0.ar))
We prove this in Appendix Intuitively, we can get this theorem by replacing +, with @ @. The key step to learn rule-induced subgraph representation is to ensure Ex,y. * 0 if and only if (x, y, = (u, ft, v). Existing models 11 12] do not satisfy this requirement, as they initialize both the target link and the other links with nonzero embeddings. Therefore, their final subgraph representations contain irrelevant rule terms, which leads to suboptimal results. On the contrary, we show that with appropriate message passing functions, REST learns rule-induced subgraph representation. As the rule-induced subgraph representation encodes all relevant rules within the subgraph, REST is expressive enough to infer the plausibility of any reasonable triple, while eliminates the negative influence of irrelevant rules.
Our analysis gives some insight of IRP methods. First, eliminating noises within the extracted subgraph crucial for subgraph-based methods. While existing methods focus on data level to extract ad-hoc subgraphs, single-source edge-wise message passing. Second, labeling tricks such as single-source initialization can effectively improve the model performance. Last but least, the idea of learning links is especially important in IRP task, as links play a vital role in reasoning.
model proposes simple way for denoising at the model level, i.e.,
6 Experiments
In this section, we first introduce the experiment setup including datasets and implementation details. Then show the main results of REST on several benchmark datasets. Finally, we conduct ablation studies, case studies and further experiments.
6.1 Experiment Setup
Datasets and Implementation Details We conduct experiments on three inductive benchmark datasets proposed by GralL[II). which are dervied from WN18RR FB (B15K-237 33), and NELL- 995(34] For inductive relation prediction, the training set and testing set should have no overlapping entities. Details of the datasets are summarized in Appendix B We use Py PyTorch(33 (35) and DGL to implement our REST. Implementation Details of REST are summarized in Appendix
6.2 Main Results
We follow Gra to rank each test triple among 50 other randomly sampled negative triples. We report the Hits@ metric on the benchmark datasets. Following the standard procedure in prior work (37], we use the filtered setting, which does not take any existing valid triples into account at ranking. We demonstrate the effectiveness of the proposed REST by comparing its performance with both rulc-based methods including Neural LP 14), DRUM (21 and RuleN [38] and subgraph-based methods including GralL [T]. COMPILE I7]. [2CT[2] SNRI 24 and ConGLR (25). We run each experiment five times with different random seeds and report the mean results in Table I
From the @its@ 10 results in Table we make the observation that our model REST significantly outperforms existing methods on 12 versions of 3 datasets. Specifically, our REST can outperform rule-based baselines, including Neural LP, DRUM and RuleN by a large margin. And compared with existing subgraph-based methods, e.g., GralL,, COMPILE, TACT, SNRI and ConGLR, REST has achieved average improvements of 17.89% 9.35%, 13. 13.76%; 16.23% 388, 13.04%; 13.58% 8.06%, 8.96%; 10.89%, 4.55%, s_" and 5.58%, 5.82%, 5.1% on three datasets respectively. As REST
7

---

Table 1: Hits 10 results the inductive benchmark datasets extracted from WNI8RR, FB15k-237 and NELL-995. The results of Neural LP, DURM, RuleN, GralL, CoMPILE and ConGLR are taken from the paper 25
WNISRR
FB15k-237
NELL:995
v1
v2
v3
v4
v3
v1
v2
v3
v4
55. 55.88
40.78
78.73
82.77
Rule-Based
DRUM
74.37
68.93
46.18
67.13
52.92
58.73
52.90
55.
19.42
78.55
82.71
80,58
80.85
53.50
81.75
77.26
61.35
Grall.
82.45
78.68
58.43
73.41
64.15
81.80
82.83
89.29
59.50
93.25
91.41
73.19
CeMPILE
83.60
79.82
60.69
75.49
67.64
82.98
84.67
87.44
58.38
93.87
92.77
75.19
Subgraph-Based
TACT
84.04
81.63
67.97
76.56
65.76
83.56
85,20
88,
79.80
88.91
94.02
73.78
SNRI
87.23
83.10
67.31
83,32
71.79
86.50
89.59
89.39
ConGLR
85.64
92.93
70.74
92.90
68.29
85.98
88.61
89.31
81.07
94,92
94.36
81.61
(oST()
96.28
94.56
79.50
94.19
75.12
91.21
93.06
96.06
88.00
94,96
96.79
92.61
only assigns the embedding of the target link, these improvements demonstrate the effectiveness of our REST via distilling all relevant rules within the subgraph.
6.3 Ablation Study
We conduct ablation studies validate the effectiveness of proposed single-source initialization and edge-wise message passing. We show the main results of ablation studies in Table
Table 2: Hits @1 10 ablation results the inductive benchmark datasets. The SUM and MUL functions are the ablation for the message function GRU. The MLP function is the ablation for the update function LSTM. A denotes the performance decrease.
WNISRR
FB15k-237
NELL-995
v2
v3
v4
v1
v3
v4
v2
v4
REST
96.28
94.56
79.50
94.19
75.12
91.21
93.06
96.06
88.00
94.96
96.79
92.61
Full Initialization
92.55
90.70
68.76
79.49
71.71
79.29
89.25
91.22
83.00
86.13
94.54
68 26
A
-373
-3.86
10.74
14470
-3.41
-11.92
-3.81
-4.84
-5.00
8.83
-2.25
24.35
SUM
93.08
85.03
69.59
91.39
64.88
84.30
89.48
89.96
81.00
91.39
96.17
64.57
A
-3.20
-9.53
-9.91
-2.80
100.44
6.91
-3.58
-6.10
-7.00
-3.57
-0.62
28.04
MUL
85.64
93.19
56.03
81.04
63.90
78.24
85.20
90.66
69.00
79.20
93.70
36.
A
-10.64
-1.37
-23.47
-13.15
-11.22
-12.97
-7.86
-5.40
-1.00
-15.76
-3.09
-56.50
MLP
93.65
90.69
71.07
90.25
92.60
94.94
83.00
94.12
96.41
91.38
A
-0.54
-0.91
-0.66
-3.50
4.05
-0.96
-0.46
-112
-5.00
00884
00.38
-1.23
Single-source source initialization is vital for learning rule- anluuiddeeed subgraph representation. To demonstrate the effectiveness of single-soure source initialization, we perform another full initialization method as a comparison, which initializes all edges according to their relations. As illustrated in Table 2 we can find that single-source initialization is significant for capturing relevant rules for reasoning. Without single-source initialization, the performance of REST will exhibit significant decrease, e.g., from 92.61 to 68.26 in NELL-9955 v4. This result exhibits the effectiveness of single-source initialization.
Single-source initialization. Single-
Edge-wise message passing. To demonstrate the necessity of proposed RNN-based functions, we conduct ablation studies on various combinations of message functions, including SUM, MUL, and GRU, as well as update functions, including LSTM and MLP. These functions are defined as follows:
SUM m² 2,8.2 ha-1
C.y. +ry R-1
MUL m z,z = h o e.y.= 3 ry
(14)
MLP 2,y. W. Wo 2 h
Wy w. - h
g.g.
In general, REST benefits from RNN-based functions, as they can capture the sequential properties of rules. Using order-independent binary operators, such as ADD and MUI,, leads to a decline in performance across all datasets, they cannot differentiate correct and incorrect rules.

---

6.4 Further Experiments
Case Study One appealing feature of our single-source initialization and edge-wise message passing approach is the ability to interpret the significance of each relevant cycle. This interpretation provides insight into the contribution of each cycle towards the plausibility of the target link (u, re: v). We generate all relevant rule cycles for each relation with length of no more than 4, and input them to the REST model to obtain a score for each relevant rule cycle. We normalize these scores using sigmoid function and select the top-3 cycles with the highest scores visualized in Table 7
Table Some relations and their top-3 relevant relations. The relations are taken from WN18RR.
Rule Head
Rule Body
Scores
similar to -> Jypernyym
0.89
hypernym
also see-> Jyperrgmm
0.84
hypernym -> s___a_l________a_ see->_eere___eeeeeeeeeeeee
0.67
derivationally related
related_form-> form-> also
0.82
derivationally_retttddd
has fias_part---- >_lssoseer
0.76
derivationally_ret relallyeellldddrteecee pagomm>_llooseee _lsso_se->> _hasahhaaan
0.66
has part-> _synset
_yyser_ddomain, domomn sopiie_opppppppp of
0.77
member memberr_meooyym
has has_part-> synset domain domain_topic_nnee
derivaiionallyeebbae peelttedeeeeedde_eeeeeeeleeedd faaittedformm- form
0.76
has part-> derivationally related form
0.71
has purt-> _also_see
0,95
_syser__ doreedddmiinn_aoe topic_of
synset domain dowain_toppcc topic_of _similar__tt 10
0.91
has part-> -synset_donmaeeeeee topic_of
0.81
The results demonstrate that REST is able to learn the degree of correlation between relevant rule cycles and the target relation. As evidence for predicting the rule head, the cycle containing the _ssimilar___ to -> _hypeernemmm 1 rule body received the highest score among all cycles that include the "'hypernyym"" relationship. This indicates that REST can effectively infer strong correlation between " _sslimar_to + hypernym -1 and " "Jeperremm" " Notably, this cycle is also human- understandable, which highlights the practical interpretability of REST.
Subgraph Extraction Efficiency Different from the subgraph-bast methods mentioned above 12 17]. REST eliminates the need for node labeling within the subgraph, which substantially improves time efficiency. We assess the time consumption involved in extracting both enclosing and unenclosing subgraphs for Grall. and REST, and present the running time results in Table 4 All the experiments are conducted on the same CPU with only single process. Our observations indicate a significant improvement of time efficiency over 11 x when extracting unenclosing subgraphs from the FB 15k-237 dataset and over 6x across inductive datasets. This improvement demonstrates the efficiency of our REST on subgraph extraction.
Table 4: The comparison of subgraph extraction time between Grall and REST. (Unit: Second)
WN18RR
FB15
v3
v3
537.42
1127.14
2933.00
8423.59
15089.74
126.55
6112.77
1303.97
Enclosing Subgraph
REST
54001
251.977
617.16
91.76
111.34
338.24
868.79
1/66.77
61.19
213.45
688.14
219.33
Fliiceecyy
2.15x
2.13x
1.83%
2.12
8.53x
8.67%
9.70
2.23%
5.61
8.88
5.95K
Grall.
69
517.94
1194.18
199.00
1287.5 35
4166 63
11490
21738 29
167.06
[61197
1542.82
Unclosing Subgraph
REST
56.27
260.20
631.71
95.23
123.36
336.55
985.81
1890.54
64.72
245.41
858.23
248.00
Emiciency
2.27%
1.99
1.89%
2,09
10.44%
10.78%
11,66x
11.50%
2.58%
6.57%
0.37X
6.22%
Conclusion and Future Work
Limitations. Our REST shares the same limitation as subgraph- based methods. While subgraph- based methods are theoretically more expressive, they incur high computational costs both training and inference. Alleviating this issue is crucial for scalability.
Conclusion. In this paper, we propose a novel single-source edge-wise graph neural network model called REST, which effectively mines relevant rules within subgraphs for inductive reasoning. REST consists of single-source initialization and edge-wise message passing, which simple, effective and provable to learn rule-induced subgraph representation. Notably, REST accelerates subgraph

---

extraction by up to 11.66x, which significantly decreases the time cost of subgraph extraction. Experiments demonstrate that our proposed REST outperforms existing state-of-the-an oh-the-art methods on inductive relation prediction benchmarks.
Future Work. For future work, we target enhancing the scalability of our REST conduct reasoning on large-scale knowledge graphs. Moreover, REST can serve as complementary reasoning model to help large language models conduct reasoning with promising and interpretable results. Hopefully, REST will facilitate the future development of reasoning ability.
Acknowledgements
The authors would like to thank all the anonymous reviewers for their insightful comments. This work was supported in part by National Key R&D Program of China under contract 1002200119801 National Nature Science Foundations of China grants U19B2026, U19B2044, 61836011, 62021001, and 61836006.
References
[1] Zhengyan Zhang, Xu Han, Zhiyuan Liu, Xin Jiang, Maosong Sun, and Qun Liu. ERNIE: Enhanced language representation with informative entities. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, July 2019.
[2] Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. Knowledge graph embedding based question answering. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 105-113, 2019.
[3] Hongwei Wang, Fuzheng Zhang, Jialin Wang, Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. Ripplenet: Propagating user preferences on the knowledge graph for recommender systems. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 417-426, 2018.
[4] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collaboratively created graph database for structuring human knowledge. Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247-1250, 2008.
[5] Denny Vrandečić and Markus Krötzsch. Wikidata: a free collaborative knowledgebase. Com- munications of the ACM, 57(10):78-85, 2014.
[6] Farzaneh Mahdisoltani, Joanna Biega, and Fabian Suchanek. Yago3: A knowledge base from multilingual wikipedias. In 7th biennial conference on innovative data systems research. CIDR Conference, 2014.
[7] Zhiqing Sun, Zhi-Hong Deng. Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embed- ding by relational rotation in complex space. arXiv preprint 1rXiv:1902.10197 2019.
[8] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607, Springer, 2018
[9] Mikhail Galkin, Max Berrendorf, and Charles Tapley Hoyt. An open challenge for inductive link prediction on knowledge graphs. arXiv preprint arXiv:2203.01522 2022.
[10] Zijie Geng, Shufang Xie, Yingce Xia, Lijun Wu, Tao Qin, Jie Wang. Yongdong Zhang, Feng Wu, and Tie- Yan Liu. De novo molecular generation via connection-awant motif mining. In The Eleventh International Conference on Learning Representations, 2023.
[11] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pages 9448 9457. PMLR, 2020.
[12] Jiajun Chen, Huarui Hc, Feng Wu, and Jie Wang. Topology-awarr correlations between relations for inductive link prediction in knowledge graphs. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 6271-6278, 2021.
[13] Luis Galárraga, Christina Teflioudi, Katja Hose, and Fabian M Suchanek. Fast rule mining in ontological knowledge bases with amic+. The VLDB Journal, 24(6))707-730, 2015.
[14] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning, arXiv preprint
10

---

[15] Stanley Kok and Pedro Domingos, Statistical predicate invention. In Proceedings of the 24th international conference on Machine learning, pages 433 2007.
[16] William Yang Wang, Kathryn Mazaitis, and William W Cohen. Structure learning via parameter learning. In Proceedings the 23rd ACM international conference on conference on information and knowledge management, pages 199-1208, 2014.
[17] Sijie Mai, Shuangjia Zheng, Yuedong Yang. and Haifeng Hu. Communicative message passing for inductive relation reasoning. In AAAI, pages 4294-4302, 2021.
[18] K Rameshkumar, M Sambath, and S Ravi. Relevant association rule mining from medical dataset using new irrelevant rule elimination technique. In 2013 International Conference on Information Communication and Embedded Systems (ICICES), pages 300-304. IEEE, 2013,
[19] Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Cycle representation learning for inductive relation prediction. In International Conference on Machine Learning, pages 24895-24910. PMLR, 2022.
[20] Stephen Muggleton and Luc De Raedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19:629-679, 1994.
[21] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining knowledge graphs Advances in Neural Information Processing Systems, 32, 2019.
[22] Pouya Ghiasnezhad Omran, Kewen Wang, and Zhe Wang. An embedding based approach to rule learning in knowledge graphs. IEEE Transactions on Knowledge and Data Engineering, 2019.
[23] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
[24] Xiaohan Xu, Peng Zhang, Yongquan He, Chengpeng Chao, and Chaoyang Yan. Subgraph neighhoring relations infomax for inductive link prediction on knowledge graphs. arXiv preprint arXiv:2208.000 00850, 2022.
[25] Qika Lin, Jun Liu, Fangzhi Xu, Yudai Pan, Yifan Zhu, Lingling Zhang, and Tianzhe Zhao. Incorporating context graph with logical reasoning for inductive relation prediction. In Pro- ceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 893-903, 2022.
[26] Shuwen Liu, Bernardo Grau, Ian Horrocks, and Egor Kostylev. Indigo: Gnn-based inductive knowledge graph completion using pair-wise encoding. Advances in Neural Information Processing Systems, 34:2034-2045, 2021.
[27] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-fort networks: A general graph neural network framework for link prediction. Advances Neural Information Processing Systems, 14:29476-22490, 2021.
[28] Mingyang Chen, Wen Zhang, Yushan Zhu, Hongting Zhou, Zonggang Yuan, Changliang Xu. and Huajun Chen. Meta-Knowledge transfer for inductive knowledge graph embedding. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 927-937, 2022.
[29] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder- decoder for statistical machine translation. arXiv preprint 100. 1078, 2014.
[30] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:0--13-3, 2020.
[31] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98)) 1735-1780, 1997.
[32] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In The Workshop on CVSC, 2015.
[33] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, 2018.

---

[34]
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP. 2017.
[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[36] Minjie Yu Wang. Deep graph library: Towards efficient and scalable deep learning on graphs. In ICLR workshop representation learning graphs and manifolds, 2019.
[37] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances neural information processing systems, 26, 2013.
[38] Christian Meilicke, Manuel Fink, Yanjie Wang. Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule-and embedding- baasdd systems for knowledge graph completion. In The Semantic Web-ISWC 2018: 17th International Semantic Web Conference, Monterey, CA, USA, October 8-12, 2018, Proceedings, Part 17, pages 3-20. Springer, 2018.
[39] Diederick P Kingma and Jimmy Ba. Adam: method for stochastic optimization. In JCLR, 2015.
[40] Yuxia Geng, Jiaoyan Chen, Jeff Z. Pan, Mingyang Chen, Song Jiang, Wen Zhang, and Huajun Chen. Relational message passing for fully inductive knowledge graph completion, 2022.
[41] Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L. Hamilton. Nodepiece: Composi- tional and earfmeter-efficient representations of large knowledge graphs, 2022.
12

---

A Proof of Theorem 1 and 2
Theorem Single-source edge-wise GNN can learn rule-induced subgraph representation if +, A +,0 +, 60 x, 60 x. iee, there exists nonzero Oi.j such that
E
On x 04 x ... X Oril
(15)
(1,72,0) (M-30-F0)
(2, 2.2)
Proof In this case, the rule-induced subgraph representation
k
Sumr.
Σ
oarr,
X 0:2t x ... X Ogt 21-2
(16)
(u.Fe.0) (e.
(31-3)
Then we will show that single-source edse GNN can learn this rule-induced sugraph representa- tion in induction.
1. we have
e.r..v by Ir. Fr.
Σ
(h. + + ryo
ET
Note that e uu * O if and only if (wo, yo. u) = (u, ru, v). However, this is impossible as u # Thus c o,rr, satisfies the definition of rule-induced subgraph representation.
we have:
C. h
o
Σ
(h)
c2 22 X Tyo + Fre
2h
x yo + Iri
(No ET
(17)
Σ
Σ
2(h2, e .o) x Fyi
X ryo + Ire
(No (Ro.8o.a) (21.8) .P)
Σ
Σ
2c
rg x rgo + Fr.
20
(s0.800.s) (21.81,,00)
We can find that e 22..9..0 * if and only if (z1, V/, xo) = (u, rt, v), i.c there exists both (u, Pts v) and (v. Tr, u). Obviously, o u satisfies the definition rule-induced subgraph representation. Assume that this conclusion exists for < k -- 1. Now we check the k-th term.
Eurcv h +
k
Σ
Σ
Qiirr & a.gTy.-> @ .... X a vo (18)
(o.))o.)) u) (#t 1e
(M.h-2220))
13

---

First, we consider h.
h
Σ
(héo + @00.000.)) Yyo
(20.80.24 u4)
Σ
(h
+
e k-2
21.81
Fys X ryo
+
e k-1
20.
X yyo
(2):Wo, (at (0))
(20.8o.
Σ
Σ
x r U
X r Ua-2
X
X F
(20.00.1) (a1
(st-1 -10--
(19)
Σ
Eye X Ngo
(1) (21.2 mn)
(mr 2-11 2
+
Σ
k-1
20.90.. Tgo
(o))
Notice that Σ
Σ
X Tye- X Ty X goo * 0 if
1
(52-1- 1
and only if (Ix-1: 1. yk (k-1) (u, Te, v). In this situation, this term is exactly the k-th term in the expression of ct o. Now want prove that:
Σ
Σ
Σ
2
22-2.8hh 22
Fy ... Kyo
(3) (21-911-70)
2:9h 2. a)
k-1
(20)
+
Σ
--1
X Tyo
can be fused in top 1 term of Equation.
16
Let's check the j-th term of Equation. 20
14

---

Σ
Σ
k-j
-18
Kng x ... x Tyo
(20.30, u) (01-yn .ro)
(ey 1.35 2)
Σ
Σ
Σ
(2))
k-j-1
h 1) Tys 1 ... 1eo
1:85
1,25 2
(ng 1:l5 1:
Σ
Σ
(c
+ 2 + + +hb 1 Tys-1 x... X Fgo
k-j
188
(30.300.))) (mi (ta)
(my A.ll 1:25-2)
Σ
Σ
Σ
22
1
X F x x yoo
(50.80. (mi.an
(11-1-1)11-55-11
Σ
Σ
Σ
(50)NO..) (#1:01:20)
(0y (33-1:83-1 f (13-))
j+1
(h 8 + nng
k-j-1
+ + 0 m3,0bing .) x Tzg-1 x.. X Yyo
(21)
Note that e 12 -1- * 0 if and only if ( Uj 11 = (u, re, v), thus the term can be can be fused into the (j + 1)-th term and on. e وز
fused into the j-th term of Equation. 16 Therefore, have:
Σ (P (o) (a))
Σ
k-j 1
X Fys-1 X ... Eyo
(#3- 1ill -1
(22)
Σ
Σ (x, 9.39 2.0)
Ontrr X 0:2 ... 0arly--2
(u.re,) (v.yo,z0)
There, we prove that single-soures source edge-wise GNN can learn rule-induced subgraph representation in this case.
Theorem Single-source edge-wise GNN can learn rale-induced subgraph representation if 4 4 = θ = C @0 = 8, 82 = 8, where ( and (9 are binary operators that satisfy 0 @ a 0 69 O. ie., there exists nonzero Ois such that
anIrr @ 0:22 @ ... a.Tgi22
(23)
U.TA.U
(w.Ft.0) (v.20. (81-318t-2.1
Proof Without loss of generality, operator, then we directly get this theorem. Note that we should ensure that e and & satisfy 0 a, 8 0, which use in the process of proof.
replace + with @ and x with & represent binary
B Details of Datasets
We summarize the details of inductive relation prediction benchmark datasets in Table 5
15

---

Table 5: Statistics of three inductive datasets, which contain four different versions individually. We use #E and #R and #TR to denote the number of entities, relations, and triples.
WN18RR
FB15k-237
NELL-995
#R
#E
#TR
#R
#E
#TR
#R
#TR
train
9
2746
6678
183
2000
5226
14
10915
5540
vl
test
922
1991
146
1500
2404
225
1034
train
10
6954
18968
203
3000
12085
88
2564
10109
v2
test
10
2923
4863
176
2000
5092
79
4937
5521
train
11
12078
32150
218
4000
22394
142
4647
20117
v3
test
11
5084
7470
187
3000
9137
122
4921
9668
train
3861
9842
222
5000
33916
77
2092
9289
v4
test
9
7208
15157
204
3500
14554
61
3294
8520
C Implementation Details
In general, our proposed method is implemented in DGL[36) and PyTorch 35 and trained single GPU of NVIDIA GeForce RTX 3090. We apply Adam optimizer 33 with an initial learning rate of 0.0005. Observing that batch size has little effect the performance of the model, We adjust batch size as large as possible for different datasets to accelerate training. We use the binary cross The The maximum number of training epochs is edges to fully capture relevant rules. The number of hop l is set to 3 which is consistent with existing subgraph-base methods. We conduct grid search obtain optimal hyperparameters, where search subgraph types in fenclosing, unclosing), embedding dimensions in ( [16, 32). number of GNN layers in 13, 6) and dropout {0, 0.1, 0.2]. Configuration for the best performance of each dataset is given within the code.
entropy loss.
10. During training, add reversed
D Transductive Results
The transductive results, as discussed Section 6.2 were obtained using the same methodology as the aforementioned evaluations. Specifically, REST trained on the training graph and tested in similar manner. We randomly selected 10% of the links from the training graph as test links. As we can senn in Table 6
REST outperforms GralL and RuleN significantly across all benchmarks.
Table 6: Experiments of the transductive versions of the current benchmarks.
Model
wn vl
wn v2
wn wn_v3
wn
fb_vl vl
v2
fb
fb.
nell vI
nell v2
nell
nell v4
GralL.
65.59
69.36
64.63
67.28
71.93
86.30
88,95
91.55
64.08
86.88
84.
82.33
RuleN
63.42
68.09
63.05
65.55
67.53
88.00
91.47
92.35
62.82
82.82
80.72
58.84
REST
92.02
90.90
91.59
91.63
88.01
93.98
96.43
97.71
93.62
95.76
92.79
92.47
16

---

E More Results of Case Study
To gain more insight of the proposed RNN-based function and single-source initialization, We conduct more experiments to obtain the rule scores on WNI&RR with the ablated model without single-source and other ablated models. In the revised paper, we will include the comprehensive results, allowing readers compare and analyze the impact of removing "irrelevant" rules on the overall performance of our proposed model. We can see from Table 7 that the model without single-source initialization assigns relatively lower scores to rules, and there are still some less precise rules present in the Top-k rules (denoted in bold). Similarly, other ablated models exhibit less precise rules in the top-k results Tables and This serves as evidence of the effectiveness of the full-version model.
Table 7:
Some relations and their top-3 relevant relations in the full initialization REST. The relations are taken from WN18RR.
Rule Head
Body
Scores
hypemmy
_lso__ee->> _synsee__dmmainttooe
Derivationallly_elaeeed. form
0.66
verb__gouup>> _similar__e to
0.59
memberr meronym-> _iimllar to
0.45
derivationally related form
also see-s iinstance hypernym
0.74
derivationally related form-> also see
0.68
_has_part>> __aaspprrt
0.62
member_meronyn
has_part->> _hyperny
0.62
has part-> instance hypernym hystance_hypemyym
0.55
has part-> member meronym-> similar
0.50
_yynset_domain_topi..oo
lit_dddmmmamiiii..c_o_ __memmeer_meronyntttt _similar_to
0.88
synset domain lopic_opppopp_oe -f similar
0.84
mmmberr_meronym- synset_domaii_topic..
0.81
Table Some relations and their top-3 relevant relations when using SUM message function. The relations are taken from WNISRR.
Rule Head
Rule Body
Score
hhypemym
similar to-> Jhpernym"
0.93
similar_to->>
_____mmmmmmeeee memmerr_meronym
0.90
_hypenym-">>aallo___ ___lss___seeee
0.88
derivationally_eelaee..oo
_ha_part->> -itis-sssmilaooooo
0.89
__lls__sseeeeeee
0.88
domain paaee_ddmmin_topi___f-_3 coppc_of>__eemerr_mmg
0.88
member meronym
member_meronym
member mactecr__monmmm>>> -imilllr to
0.90
hhs has_pprrt>> _ynsse_doominnnn_.teteeee___eenL synnee_domman__oppp_ooff
0.85
instance instance_hypemneeee hypernym- seerrivatiinalll_eeeeee pecplllyyyeeeeeeeeeeeeeeee form-> _emmberrmeeer____ ____mmmer_mroonyyn
0.85
dynset_domain_ooo
_has_ part
0.95
Jypernym- topic of also see
synset domain
0.95
form->_allo_sseee _aeso_see
0.92
Table Some relations and their top-3 relevant relations when using MUL, message function. The relations are taken from WN18RR.
Rule Head
Rule Body
Score
_hypemym
similar _hppemymm
0.93
instance _aaennce__herrymm-m _iistancce hypemym _jnstancc_hypemyy
0.91
instance__yyl instance_hypermym=>> hypernym->>---.. .hyperym
0.91
derivationally related form
similar dddrrivationallyy.... related form
0.94
derivationally relatellldddcc.e form-> similar
0.93
has_part->>
deerivationally_relteed formf
0.93
member meronym
_emberr_meronym
__eemmr_mmeeeee saanber_mmernyym>aaom Laatt>>>_allssss_ee _also_scee
0.93
.hyperymm>> similar_to
0.90
similar_to- to _ecloo-___ss__dd_e__
pyynset_dmmainttople ddd.aannnnniii.oodddddiiiiaaaaaa dderivationally_reette__oo
0.87
synset domain topic_ot
also allso_see->> __rbb_rrb___ _verb_groupppppppppppp group
0.92
_sysstt_sssooss dwwpaoontopiicoo___oooooo 1f ->_immllar_too L>__mmila__ss
0.86
has Bacs_part>>___ __yynset_am domain topic of
_synset_domain
0.84
17

---

Sensitivity Analysis
We further conduct sensitivity analysis of the subgraph hop n, where different n represents the maximum number of neighbors extracted by REST within the subgraphs. We conduct experiments on both the same distribution (transductive setting) and different distribution benchmarks (inductive setting). As Tables 10.
12 and 13 show, REST exhibit great robustness across different n.
Table 10: Experiments in the transductive setting with 2, 3, 4, where training and inference are in the same KG.
Hop Number
wn v1
wn
wn v3
wn v4
th 11_v1
v1
1b v2
v4
nell vl
nell v2
nell v3
nell v4
2hop
84.65
87.66
85.73
84.35
91.78
93.67
92.48
96.59
93.73
93.89
Shop
92.02
90.90
91.59
91.63
88.01
93.98
96.43
97.71
93.62
95.76
92.79
92.47
4hop
89.97
89.96
90.19
89.68
88.74
93.12
96.16
97.44
94.99
96.64
96.26
94.35
Table 11: Experiments in the inductive setting on WNI8RR benchmark with n = =2, 3, 4, where training and inference in the different KGs.
Hop Number
wn v1 _i_ind
wn v2_ind
wn v3 ind
wn v4 ind
2 hop Neighbors
92.55
89.58
76.27
89.67
3 hop Neighbors
96.28
94.56
79.50
94.19
4 hop Neighbors 94.70
93.17
77.19
92.68
Table 12: Experiments in the inductive setting on FB15k237 with n 2, 3, 4, where training and inference are in the different KGs.
Hop Number
fb vl ___ind
fb_v2_inn ind
fb_v3_ind ind
fb_ 10_4__ind
hop Neighbors
69.53
87.47
90.55
93.68
3 hop Neighbors
75.12
91.21
93.06
96.06
4 hop Neighbors 70.44
90.12
93.45
94.59
G More fine-grained metrics on the inductive benchmarks.
As Hits @ 10 scores reach a fairly high level, we provide the experimental results on more difficult and comprehensive metrics than Hits @ 10. Tables 14 [5 and [6 summarize the results of GralL and our REST on MRR, Hits @ I, and Hits@5. These representative metrics suggest that there is still large room for improvement.
H More Baseline Results and Analysis
We provide additional baselines and our REST for comparison to obtain comprehensive explanation. These baselines include NBFNET (27). RMPI (40), and NODEPIECE [41]. The comparative results presented in the following Table 17 REST also outperforms RMPI in large margin and achieves competitive results compared with NodePiece and NBFNet. This implies the great potential for the subgraph-based methods to achieve superior results than the shole-grapph-ased methods. And we will focus on this point as our furture work.
18

---

Table 13: Experiments in the inductive setting on NELL995 with = 2, 3, 4, where training and inference are in the different KGs.
Hop Number nell vI _ind
nell ________d ind
nell v3 ind
nell 1y4_ind
2 hop Neighbors
83.00
90.18
93.18
90.81
3 hop Neighbors
88.00
94.96
92.61 96.79
4 hop Neighbors
89.00
94.94
95.67
91.54
Table 14: MRR results on inductive benchmarks.
Model
wn_vl
wn_v2
wn_v3
wn_ye v4
fb_vl
fb_v2 v2
fb_v3
fb_v4
nell_v]
nell_v2 v2
nell_ _ell_v3
nell_v4
GralL
74.09
79.32
54,25
73.34
45.91
61.78
62.79
65.09
44.82
64.49
70.73
60.45
REST
81.08
87.06
62.66
88.14
49.71
65.74
68.75
72.41
55.99
69.65
74.99
69.63
Table 15: H@@ results on inductive benchmarks.
Model
wn.vl
wBLv2
w3
wn v4
lb_vl
fb_v2
1b_v3
1b_v4
v4
nell_v
nell v2
nell v3
nell v4
Grall.
68.89
71.46
51.24
70.59
37.31
50.94
52.89
34.04
39.00
54.98
58.71
49.27
REST
71.28
82.54
54.88
84.89
39.05
53.14
56.42
60.39
43.00
56.72
$7.59
Table 16: H@5 results on inductive benchmarks.
Model
wn_vl
wn_v2
wn. v3
wn wn_v4 v4
lb_vl
fb_v2
1b_v3
1b_v4
v4
nell_v
nell_ v2
nell_v3
nell
GralL
80.78
75.63
55.74
72.37
53.91
75.21
73.70
78.06
47.50
81.41
87.08
39.39
REST
92.55
90.02
69.59
89.99
60.49
80.75
84.28
87.64
57.00
86.97
92.21
86.32
Table 17: More inductive baseline results on the inductive benchmark.
Model
WB_vi
WIL v2
W3LV3
wn
16.vl
16_v2
1b_v3
nell.v
nell
nelL
nell v4
RMPI
89.63
83.22
73.14
81.42
71.71
83.37
86.01
88.69
60.50
94.01
93.36
87.62
NBFNet
94,80
90.50
89.30
89.00
83.40
94.90
95.10
96.00
NodePiece
83.00
88.60
78.50
80.70
87.30
93.90
94.40
94,90
89.00
90.10
93.60
89.30
REST(ours)
96.28
94.56
79.50
94.19
75.12
91.21
93.06
96.06
88.00
94,96
96.79
92.61
19


Reviews:
[{"review_id": "0qIe9UVIzg", "reviewer": "Reviewer_UyGM", "summary": "This work proposes a single-source edge-wise GNN model for the inductive relation prediction task, called REST. The method includes a single-source initialization approach that reduce the irrelevant rules during learning and an RNN-based edge-wise message passing mechanism to model the sequential property of mined rules. Authors experiments REST on three inductive relation prediction benchmarks and REST achieves  good results. And without node labeling, the subgraph extraction is significantly faster than GraIL. ", "questions": "1. During experiment, is the binary operators in Equation (2) set the same as Theorem 1? \n2. As shown in Table 2, replacing the GRU massage function to SUM and MUL significantly downgrade the performance which is more significant than change the single initialization to full initialization. Is there any reason? ", "limitations": "See weakness and limitations. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and easy to follow. The proposed method is well-motivated and is easy to understand. The experiments proves the effectiveness of the REST, especially the ablation study proves the effectiveness of the main novelty in the method, the single-source initialization and RNN-based edge-wise massage passing. ", "weaknesses": "Some of the recent proposed inductive relation prediction methods are missing, such as \n* Mingyang Chen, Wen Zhang, Yushan Zhu, Hongting Zhou, Zonggang Yuan, Changliang Xu, Huajun Chen: Meta-Knowledge Transfer for Inductive Knowledge Graph Embedding. SIGIR 2022: 927-937\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**1. Missing related works in paper.**\n\nThank you for your valuable suggestions. We appreciate your insightful comments on our paper.\nIn the revised manuscript, we have included the missing reference to the work by Mingyang Chen et al. [1], titled \"Meta-Knowledge Transfer for Inductive Knowledge Graph Embedding.\"\nThe reference to the mentioned paper has been added in the related work section to provide readers with a more comprehensive overview of recent advancements in inductive relation prediction methods.\n\n**2.  During experiment, is the binary operators in Equation (2) set the same as Theorem 1?**\n\nRegarding the binary operators in Equation (2) and Theorem 1, we apologize for any confusion in the original manuscript. In Equation (2), the binary operators are described as generalized operators, which can be replaced with various alternatives.\nDuring the experiment, we replaced the binary operators with the RNN-based functions we proposed. \n\n**3.  As shown in Table 2, replacing the GRU massage function to SUM and MUL significantly downgrade the performance which is more significant than change the single initialization to full initialization. Is there any reason?**\n\nThe significant performance downgradation when using SUM and MUL instead of the GRU message function lies in the importance of position information in our edge-wise message passing framework. Unlike some previous works like GraIL, where node labeling implicitly encodes the position information, our approach learns position information explicitly through the GRU message function.\nWe conducted case studies in the ablation experiments for SUM and MUL to further investigate the impact. Our findings reveal that the model captures some less precise cycles(denoted in **bold**) without the position information, leading to suboptimal results.\n\nTable 6: Some relations and their top-3 relevant relations when using SUM as message function. The relations are taken from WN18RR.\n|Rule Head|Rule Body|Score|\n|----------------------------|------------------------------------------------------------|--------|\n|_hypernym|_similar_to->_hypernym$^{-1}$|0.93|\n||**_similar_to->_member_meronym**|**0.90**|\n||_hypernym$^{-1}$->_also_see|0.88|\n|_derivationally_related_form|_has_part->_similar_to|0.89|\n||_derivationally_related_form$^{-1}$->_also_see|0.88|\n||**_synset_domain_topic_of->_member_meronym->_similar_to**|**0.88**|\n|_member_meronym|_member_meronym->_similar_to|0.90|\n||_has_part->_synset_domain_topic_of|0.85|\n||_instance_hypernym->_derivationally_related_form->_member_meronym|0.85|\n|_synset_domain_topic_of|_also_see->_has_part|0.95|\n||_synset_domain_topic_of$^{-1}$->_also_see|0.95|\n||_hypernym->_derivationally_related_form->_also_see|0.92|\n\nTable 7: Some relations and their top-3 relevant relations when using MUL as message function. The relations are taken from WN18RR.\n|Rule Head|Rule Body|Score|\n|----------------------------|------------------------------------------------------------|--------|\n|_hypernym|_similar_to->_hypernym$^{-1}$|0.93|\n||**_instance_hypernym->_instance_hypernym**|**0.91**|\n||**_instance_hypernym->_hypernym**|**0.91**|\n|_derivationally_related_form|**_similar_to->_derivationally_related_form**|**0.94**|\n||_derivationally_related_form->_similar_to|0.93|\n||_has_part->_derivationally_related_form$^{-1}$|0.93|\n|_member_meronym|_member_meronym->_also_see|0.93|\n||**_hypernym->_similar_to**|**0.90**|\n||_similar_to->_synset_domain_topic_of->_derivationally_related_form|0.87|\n|_synset_domain_topic_of|_also_see->_verb_group|0.92|\n||_synset_domain_topic_of$^{-1}$->_similar_to|0.86|\n||_has_part->_synset_domain_topic_of$^{-1}$|0.84|\n\n[1] Mingyang Chen, Wen Zhang, Yushan Zhu, Hongting Zhou, Zonggang Yuan, Changliang Xu,\nHuajun Chen: Meta-Knowledge Transfer for Inductive Knowledge Graph Embedding. SIGIR\n2022: 927-937"}, {"review_id": "DJh1ErHZrx", "reviewer": "Reviewer_r6aB", "summary": " This paper tackles a problem in the sub-area of machine learning on graphs. It looks at approaches for inductive reasoning (i.e. ones the generalize to unseen vertices), identifies a problem with those approaches and suggests a novel manner to tackle is problem, exploiting the recurrant nature of message-passing (via a GRU and LSTM).\n\nThere where theorems, along with proofs, that analized the potential effectiveness of the model. Moreover, the model was trained on multiple data sets and compared to multiple strong baselines. Finally, ablation studies where performed to empirically show the effect of the GRU and LSTM components.\n\nThe paper is overall clear to read.  Section 3 however could be easier to read through if the mathematical expressions where better separated from the text.\n\nThe field of inductive reasoning over graphs itself tackles a very relevant problem for machine learning on graphs. This paper identifies a problem with current approaches and introduces a fairly novel, effective and scalable approach taking this problem into account. While this is likely not be interesting to everyone in the world of machine learning, it should be interesting to many people in the machine learning on graphs community.\n\n", "questions": "With some scores being higher than 95%, do you think research in this direction should look into a more difficult task instead?\n", "limitations": "The reported hits@10 are fairly high (typically 90%-95%). It would have been nice if hits at a lower k would have been reported as well.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is sound. To applies to its analysis of the problem at hand, but also to its experimental setup, which incluedes good baselines and ablation studies.\n", "weaknesses": "The mathematical nature of the paper, combined with a reliance on an understanding of several other things (e.g. subgraph representation, LSTMs and GRUs) could make this a difficult paper to get into for people from other sub-areas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**1. Section 3 could be easier to read if the mathematical expressions were better separated from the text.**\n\nThanks for the detailed suggestion. We will reorganize Section 3 (i.e., problem definition) accordingly to improve the presentation of mathematical expressions in the revised paper.\n\n**2. The mathematical nature, with a reliance on an understanding of subgraph representation, LSTM and GRUs could make it difficult to get into for people from other sub-areas.**\n\nWe will add annotations and improve the notations to make it easier to understand the math and core concepts, such as the subgraph representation of the model. \n\n**3. With some scores being higher than 95%, research in this direction should look into a more difficult task instead.  Hits at a lower k would have been reported as well.**\n\nAs Hits@10 scores reach a fairly high level, we provide the experimental results on more difficult and comprehensive metrics than Hits@10. Tables 8, 9, and 10 summarize the results of GraIL and our REST on MRR, Hits@1, and Hits@5. These representative metrics suggest that there is still a large room for improvement. The evaluations on three datasets show that the proposed model significantly outperforms GraIL on all metrics. This demonstrates the effectiveness of our REST. \n\nTable 8: MRR results on inductive benchmarks.\n|Model|wn_v1|wn_v2|wn_v3|wn_v4|fb_v1|fb_v2|fb_v3|fb_v4|nell_v1|nell_v2|nell_v3|nell_v4|\n|-----|-----|-----|-----|-----|-----|-----|-----|-----|-------|-------|-------|-------|\n|GraIL|74.09|79.32|54.25|73.34|45.91|61.78|62.79|65.09|44.82|64.49|70.73|60.45|\n|REST|81.08|87.06|62.66|88.14|49.71|65.74|68.75|72.41|55.99|69.65|74.99|69.63|\n\nTable 9: H@1 results on inductive benchmarks.\n|Model|wn_v1|wn_v2|wn_v3|wn_v4|fb_v1|fb_v2|fb_v3|fb_v4|nell_v1|nell_v2|nell_v3|nell_v4|\n|-----|-----|-----|-----|-----|-----|-----|-----|-----|-------|-------|-------|-------|\n|GraIL|68.89|71.46|51.24|70.59|37.31|50.94|52.89|54.04|39.00|54.98|58.71|49.27|\n|REST|71.28|82.54|54.88|84.89|39.05|53.14|56.42|60.39|43.00|56.72|61.80|57.59|\n\nTable 10: H@5 results on inductive benchmarks.\n|Model|wn_v1|wn_v2|wn_v3|wn_v4|fb_v1|fb_v2|fb_v3|fb_v4|nell_v1|nell_v2|nell_v3|nell_v4|\n|-----|-----|-----|-----|-----|-----|-----|-----|-----|-------|-------|-------|-------|\n|GraIL|80.78|75.63|55.74|72.37|53.91|75.21|73.70|78.06|47.50|81.41|87.08|59.39|\n|REST|92.55|90.02|69.59|89.99|60.49|80.75|84.28|87.64|57.00|86.97|92.21|86.32|"}, {"review_id": "g8qNm7FDjF", "reviewer": "Reviewer_eBJJ", "summary": "This paper proposes a subgraph-based method to address the inductive relation prediction task, where the model learns to predict links by learning implicit rules from subgraphs. Models proposed in previous works lack the ability to differentiable the relevant and irrelevant paths. To address this, the authors propose several modifications including single-source initialization, edge-wise message passing, and modified activation functions. In the experiments, these modifications are shown to be effective which leads to superior performance compared to several subgraph-based and rule-based methods.", "questions": "None", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed single-source initialization and edge-wise message passing are well-motivated and well-presented.\n- The paper is well-written and easy to read.\n", "weaknesses": "## Novelty\n\n\nThe authors propose several modifications to the standard message passing algorithm to better support inductive rule learning. This includes single-source initialization, edge-wise message passing, and modified activation functions. While these modifications are well-motivated and sensible, they are straightforward and mostly incremental changes to the standard protocol. That said the intellectual novelty is limited.\n\nSection 5 provides an interesting theoretical analysis of the proposed model. While it is always nice to have a solid analysis, it does not contribute to any theoretical findings nor does it reveal novel properties of the proposed method other than proving it will work, which is already empirically proven in many previous works.\n\nIn summary, this paper proposes several incremental modifications to GNN-based inductive reasoning methods. While the modifications are rather straightforward, it does seem to lead to better empirical results.\n\n\n## Quality\n\n\nThe proposed single-source initialization and edge-wise message passing are well-motivated and well-presented.\n\nMy main concern is more about the subgraph-based methods as a whole. This class of methods requires first extracting the subgraphs from the KG before they can be learned by the GNN models. And what concerns me the most is that the extraction step is not learnable: one has to pick a magic n-hop number beforehand and proceed to extract the subgraphs and finally train the models on them. This leads to several limitations: (1) it cannot generalize to KGs that have longer relational path than those seen in the training set; (2) the n-hop number are typically small, as the complexity of running GNN grows quickly with respect to the size of the graph. These limitations are non-existent for backward-chaining rule-based methods.\n\nI understand this criticism is probably beyond the scope of this work, but I highly recommend the authors step outside of the \"well-established\" zone and challenge themselves to address these limitations. For example, as a first step, one can investigate what is the effect of the number n on the performance of the model on datasets with the same data distribution; and then on ones with different distributions, and if the performance deteriorates, propose solutions to alleviate that.\n\n\n## Clarity\n\nThe paper is well-written and easy to read.\n\n\n## Significance\n\nThe proposed method has some empirical significance as it is shown to outperform all previous baselines. However, as mentioned above, the model largely resembles the ones in prior work and only several incremental changes are proposed. More importantly, this class of methods has a serious limitation that is still left unaddressed in this work, which limits its applications in real-world tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score (\"4: Borderline reject\"). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n### Novelty:\n**1. The intellectual novelty is limited.**\n\nIn this paper, we propose a single-source initialization and an edge-wise message passing, which effectively captures relevant rules and significantly increases the subgraph extraction efficiency. This architecture is well-motivated and intrinsically different from the standard protocol. The key idea behind the proposed method is to learn representations of **links** rather than **nodes**.\n\nLearning node representations brings two limitations in the standard protocol such as GraIL,\n1. they need **node labeling** in the stage of subgraph preprocessing, leading to the major time cost during inference.\n2. they need a **pooling layer** to get final subgraph representations, which incurs information loss and decreases the model performance.\n\nHowever, as shown in Figure 3, REST does not require node labeling and directly learns the representation of the target link as the subgraph representation. This significantly accelerates the subgraph preprocessing and improves the model performance.\n\n**2. The theoretical analysis does not contribute to any theoretical findings.**\n\nWe apologize for any confusion in the original theoretical analysis.\n\nAs stated in Lines 212 to 214, our theorem 2 suggests why the existing baseline GraIL and a series of its following works achieve suboptimal results. This is because massive irrelevant rules within the subgraph will make the model prone to overfitting while misleading the model to incorrect reasoning results. Empirical proof of this conclusion is that GraIL and other subgraph-based methods can get an AUC-PR of over 0.999 during training, while they can only get an AUC-PR of 0.900 during validation.\n\nMeanwhile, our theoretical analysis also provides insights for other IRP methods. \n- First, eliminating noises within the extracted subgraph is crucial for subgraph-based methods. While existing methods focus on data level to extract ad-hoc subgraphs, our model proposes a simple way for denoising at the model level, i.e., single-source edge-wise message passing. \n- Second, labeling tricks such as single-source initialization can effectively improve the model performance. \n- Last but not least, the idea of learning links is especially important in IRP task, as links play a vital role in reasoning.\n\n### Quality:\n1. **Subgraph-based methods cannot generalize to KGs that have longer relational path than those seen in the training set.**\n\nWe admit that the model cannot generalize to KGs that have longer relational path than those in the training set. However, unclosing subgraphs wtih $n=3$ can capture paths at max length $l=6$. As shown in Figure 3 of Neural LP [1], when the number of paths length increases, the model performance decreases rapidly, especially with $l\\geq 6$. Therefore, $n=3$ is enough for most scenarios.\n\n2. **The n-hop number are typically small, as the complexity of running GNN grows quickly with respect to the size of the graph.**\n\nWe agree that this is ubiquitous in existing subgraph-based methods. However, during inference, the largest time cost is subgraph preprocessing, i.e., subgraph extraction. To address this issue, we have attempted to remove node labeling during subgraph extraction and achieve relatively great efficiency. Our future works will continue to focus on handling this problem and making subgraph-based methods more applicable.\n\n3. **One can investigate what is the effect of the number n on the performance of the model on datasets with the same data distribution; and then on ones with different distributions, and if the performance deteriorates, propose solutions to alleviate that.**\n\nThanks for the valuable suggestions. We conduct experiments to further investigate the effect of $n$. \nFor the same data distribution, we conduct experiments on the same KG (transductive setting) as follows:\n\nTable 11: experiments in the transductive setting with n = 2, 3, 4, where training and inference are in the same KG. (Hits@10)\n|Hop Number|wn_v1|wn_v2|wn_v3|wn_v4|fb_v1|fb_v2|fb_v3|fb_v4|nell_v1|nell_v2|nell_v3|nell_v4|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|2hop|84.65|85.40|87.66|85.73|84.35|91.78|95.67|96.97|92.48|96.59|95.73|93.89|\n|3hop|92.02|90.90|91.59|91.63|88.01|93.98|96.43|97.71|93.62|95.76|92.79|92.47|\n|4hop|89.97|89.96|90.19|89.68|88.74|95.12|96.16|97.44|94.99|96.64|96.26|94.35|\n\nFor different data distributions, we conduct experiments on different KGs (inductive setting) as follows:\n\nTable 12: experiments in the inductive setting with n = 2, 3, 4, where training and inference are in the different KGs. (Hits@10)\n|Hop Number|wn_v1_ind|wn_v2_ind|wn_v3_ind|wn_v4_ind|fb_v1_ind|fb_v2_ind|fb_v3_ind|fb_v4_ind|nell_v1_ind|nell_v2_ind|nell_v3_ind|nell_v4_ind|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|2hop|92.55|89.58|76.27|89.67|69.53|87.47|90.55|93.68|83.00|90.18|93.18|90.81|\n|3hop|96.28|94.56|79.50|94.19|75.12|91.21|93.06|96.06|88.00|94.96|96.79|92.61|\n|4hop|94.70|93.17|77.19|92.68|70.44|90.12|93.45|94.59|89.00|94.94|95.67|91.54|\n\nFrom the results, we can find that in both transductive and inductive settings, $n=3$ achieves almost the best results. Increasing the hop number to 4 can only bring marginal improvements (e.g., results on fb_v1 and nell_v2), and usually results in model performance degradation (e.g., wn_v1_ind and fb_v1_ind). These results demonstrate our conclusion that $n=3$ is robust enough for most situations. \n\n[1] Yang, Fan, Zhilin Yang, and William W. Cohen. \"Differentiable learning of logical rules for knowledge base reasoning.\" Advances in neural information processing systems 30 (2017)."}, {"review_id": "Ehn7JBqzdG", "reviewer": "Reviewer_s9SP", "summary": "This paper proposes REST, a method for inductive link prediction over knowledge graphs. Compared to previous techniques that extract subgraphs around the target edge, REST avoids node labelling (thus saving substantial execution time) and only initializes the representation of the target link, setting other edge representations to zero vectors. Moreover, REST introduces edge-wise message passing to update edge representations iteratively, and achieves this through a series of learnable functions and a gated recurrent unit (GRU). Node updates are then computed using a long-short term memory (LSTM) cell, conditioned on the target query. \n\nBy only initializing the target edge representation, the paper shows that REST can focus only on \"relevant\" rules, i.e., rules including the target edge, thus substantially reducing noise. More precisely, REST is shown to learn rule-induced subgraph representations. Finally, on the empirical side, the paper runs experiments on standard baselines for inductive link prediction, achieving strong results, reports ablation studies highlighting the value of its initialization and recurrent components, and discusses further experiments showcasing candidate rule scoring by the learned REST model on WN18RR and efficiency gains versus other baselines.", "questions": "- Could you provide rule scores on WN18RR (similarly to the scores you currently have in the experimental section) with the ablated model without single-source? I think contrasting the scores and/or the different top-k rules across the full version and the ablated version would really help drive the point across regarding ignoring \"irrelevant\" rules. ", "limitations": "The authors adequately discuss model limitations, particularly in terms of relatively poor scalability.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow.\n- The design choices in REST (single-source initialization, message passing setup, etc.) are well-justified  and supported empirically. \n- The paper provides a good overview of the literature in the related work section. \n- The experimental results on inductive datasets are strong and convincing. The ablation studies also demonstrate the value of the REST model. \n- The additional case study is very interesting.", "weaknesses": "- The paper does not report all baseline results in the experimental section (Table 1). For instance, NBFNet is cited in the related work section but not reported in the tables. From a quick glance at that paper, its results would indicate NBFNet has mostly superior performance on FB15k-237. Therefore, it would be important to include these results for completeness and ideally also discuss potential explanations for performance gains/losses.\n\n- I think the experimental section can be improved by including further benchmarks from other link prediction setups. For instance, it would be interesting to see REST's performance on the transductive versions of the current benchmarks, and on OGB [1] benchmarks for link prediction. \n\n[1] Hu et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs, NeurIPS 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**1. Including more baseline and analyze results on FB15k-237 datasets.**\n\nThanks for pointing out this. We have included the baseline in the revised paper accordingly. We analyzed NBFNet's performance on FB15k-237 and understood the concerns raised regarding our model's comparative performance. \n\nOur analysis observed that FB15k-237 is a dataset with diverse relations but relatively smaller nodes. As such, it may contain more complex rules governing entity relationships. We hypothesize that models like NBFNet, which utilize a relatively larger number of negative samples, can better discriminate the correctness of intricate rules. This may potentially lead to improved performance of these models on FB15k-237.\n\nOn the other hand, our model is particularly well-suited for sparse knowledge graphs with larger numbers of nodes. Our state-of-the-art results on datasets like WN18RR and NELL995 demonstrate that subgraph-based models tend to excel in reasoning over such knowledge graphs. \n\n**2. Further benchmarks of REST**\n\nWe agree that evaluating REST's performance on transductive versions of the current benchmarks is crucial for comprehensively assessing its capabilities. As such, we have already conducted experiments in Table 13 on the transductive versions of the benchmarks and included the results in our revised paper.\n\nOn the other hand, we acknowledge that the OGB benchmarks are also essential for evaluating link prediction models, and we regret that we were unable to include them in the initial submission due to time constraints. Nevertheless, we will include results on OGB benchmarks in the revised paper.\n\nTable 13: experiments the transductive versions of the current benchmarks. (Hits@10)\n|Model|wn_v1|wn_v2|wn_v3|wn_v4|fb_v1|fb_v2|fb_v3|fb_v4|nell_v1|nell_v2|nell_v3|nell_v4|\n|-|-|-|-|-|-|-|-|-|-|-|-|-|\n|GraIL|65.59|69.36|64.63|67.28|71.93|86.30|88.95|91.55|64.08|86.88|84.19|82.33|\n|RuleN|63.42|68.09|63.05|65.55|67.53|88.00|91.47|92.35|62.82|82.82|80.72|58.84|\n|REST|92.02|90.90|91.59|91.63|88.01|93.98|96.43|97.71|93.62|95.76|92.79|92.47|\n\n**3. Rule scores on WN18RR with the ablated model without single-source and other ablated models.**\n\nWe have conducted additional experiments to obtain the rule scores on WN18RR with the ablated model without single-source and other ablated models. In the revised paper, we will include the comprehensive results, allowing readers to compare and analyze the impact of removing \"irrelevant\" rules on the overall performance of our proposed model. \n\nWe can see from Table 14, that the model without single-source initialization assigns relatively lower scores to rules, and there are still some less precise rules present in the Top-k rules (denoted in **bold**). Similarly, other ablated models exhibit less precise rules in the top-k results in Tables 15 and 16. This serves as evidence of the effectiveness of the full-version model.\n\nTable 14: Some relations and their top-3 relevant relations when using full initialization method. The relations are taken from WN18RR.\n|Rule Head|Rule Body|Score|\n|-|-|-|\n|_hypernym|**_also_see->_synset_domain_topic_of->_derivationally_related_form**|**0.66**|\n||_verb_group->_similar_to|0.59|\n||**_member_meronym->_similar_to**|**0.45**|\n|_derivationally_related_form|_also_see->_instance_hypernym|0.74|\n||**_derivationally_related_form->_also_see**|**0.68**|\n||_has_part->_has_part|0.62|\n|_member_meronym|**_has_part->_hypernym**|**0.62**|\n||**_has_part->_instance_hypernym**|**0.55**|\n||_has_part->_member_meronym->_similar_to|0.50|\n|_synset_domain_topic_of|_synset_domain_topic_of^{-1}->_member_meronym->_similar_to|0.88|\n||_synset_domain_topic_of^{-1}->_similar_to|0.84|\n||_member_meronym->_synset_domain_topic_of^{-1}|0.81|\n\nTable 15: Some relations and their top-3 relevant relations when using SUM as message function. The relations are taken from WN18RR.\n|Rule Head|Rule Body|Score|\n|-|-|-|\n|_hypernym|_similar_to->_hypernym$^{-1}$|0.93|\n||**_similar_to->_member_meronym**|**0.90**|\n||_hypernym$^{-1}$->_also_see|0.88|\n|_derivationally_related_form|_has_part->_similar_to|0.89|\n||_derivationally_related_form$^{-1}$->_also_see|0.88|\n||**_synset_domain_topic_of->_member_meronym->_similar_to**|**0.88**|\n|_member_meronym|_member_meronym->_similar_to|0.90|\n||_has_part->_synset_domain_topic_of|0.85|\n||_instance_hypernym->_derivationally_related_form->_member_meronym|0.85|\n|_synset_domain_topic_of|_also_see->_has_part|0.95|\n||_synset_domain_topic_of$^{-1}$->_also_see|0.95|\n||_hypernym->_derivationally_related_form->_also_see|0.92|\n\nTable 16: Some relations and their top-3 relevant relations when using MUL as message function. The relations are taken from WN18RR.\n|Rule Head|Rule Body|Score|\n|-|-|-|\n|_hypernym|_similar_to->_hypernym$^{-1}$|0.93|\n||**_instance_hypernym->_instance_hypernym**|**0.91**|\n||**_instance_hypernym->_hypernym**|**0.91**|\n|_derivationally_related_form|**_similar_to->_derivationally_related_form**|**0.94**|\n||_derivationally_related_form->_similar_to|0.93|\n||_has_part->_derivationally_related_form$^{-1}$|0.93|\n|_member_meronym|_member_meronym->_also_see|0.93|\n||**_hypernym->_similar_to**|**0.90**|\n||_similar_to->_synset_domain_topic_of->_derivationally_related_form|0.87|\n|_synset_domain_topic_of|_also_see->_verb_group|0.92|\n||_synset_domain_topic_of$^{-1}$->_similar_to|0.86|\n||_has_part->_synset_domain_topic_of$^{-1}$|0.84|"}]

Author rebuttal:
We thank all the reviewers for the insightful comments and constructive suggestions, which are very helpful for us to strengthen this submission.

We have submitted detailed responses to address the concerns raised by all the reviewers. Besides answering the technical questions,
1. we conduct more case studies for each ablated model, which demonstrates the effectiveness of each component within proposed REST; (for reviewers UyGM and s9SP)
2. we conduct experiments in both transductive and inductive settings while providing more results to show the effect of the hop number $n$; (for reviewers eBJJ and s9SP)
3. we provide more results with other comprehensive metrics, such as MRR, Hits@1, and Hits@5; (for reviewer r6aB)
4. we clarify the advantages of proposed method and give our theoretical findings, which demonstrates the intellectual novelty of our REST. (for reviewer eBJJ)

We would like to know if our responses have properly addressed your concerns. All of your feedback and/or additional comments are warmly welcomed.

Meta-review: Previous  inductive link prediction approaches extract subgraphs around the target edge. They lack the ability to differentiate the relevant and irrelevant paths. This paper proposes to improve previous approaches by single-source initialization, edge-wise message passing, and modified activation functions.

By only initializing the target edge representation, the paper shows that REST can focus only on "relevant" rules, i.e., rules including the target edge, thus substantially reducing noise. More precisely, REST is shown to learn rule-induced subgraph representations. 
Experiments on standard baselines for inductive link prediction shows strong results. Ablation studies highlighting the value of its initialization and recurrent components, and  efficiency gains versus other baselines.

Strengths:
1. The paper is well-written and easy to follow.
2. The design choices (single-source initialization, message passing setup, etc.) are well-justified and supported empirically.
3. The paper provides a good overview of the literature in the related work section.
4. The experimental results on inductive datasets are strong. 
5. The ablation studies are informative

Weaknesses:
1. The paper can be stronger by including other stronger baselines and further benchmarks.
Decision: Accept (poster)