# Logical Reasoning with Relation Network for Inductive Knowledge Graph
Completion

Qinggang Zhang  The Hong Kong Polytechnic UniversityHung Hom, Hong Kong SAR
<EMAIL_ADDRESS>,  Keyu Duan  National University of
SingaporeSingapore<EMAIL_ADDRESS>,  Junnan Dong  The Hong Kong Polytechnic
UniversityHung Hom, Hong Kong SAR<EMAIL_ADDRESS>,  Pai Zheng
The Hong Kong Polytechnic UniversityHung Hom, Hong Kong SAR
<EMAIL_ADDRESS>and  Xiao Huang  The Hong Kong Polytechnic
UniversityHung Hom, Hong Kong SAR<EMAIL_ADDRESS>
(2018)

###### Abstract.

Inductive knowledge graph completion (KGC) aims to infer the missing relation
for a set of newly-coming entities that never appeared in the training set.
Such a setting is more in line with reality, as real-world KGs are constantly
evolving and introducing new knowledge. Recent studies have shown promising
results using message passing over subgraphs to embed newly-coming entities
for inductive KGC. However, the inductive capability of these methods is
usually limited by two key issues. $(i)$ KGC always suffers from data
sparsity, and the situation is even exacerbated in inductive KGC where new
entities often have few or no connections to the original KG. $(ii)$ Cold-
start problem. It is over coarse-grained for accurate KG reasoning to generate
representations for new entities by gathering the local information from few
neighbors. To this end, we propose a novel iNfOmax RelAtion Network, namely
NORAN, for inductive KG completion. It aims to mine latent relation patterns
for inductive KG completion. Specifically, by centering on relations, NORAN
provides a hyper view towards KG modeling, where the correlations between
relations can be naturally captured as entity-independent logical evidence to
conduct inductive KGC. Extensive experiment results on five benchmarks show
that our framework substantially outperforms the state-of-the-art KGC methods.

Knowledge graph; message passing; logical reasoning

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Knowledge graphs (KGs) are a collection of factual information to describe a
certain field of the real world (Bollacker-etal07Freebase, ; Lehmann-
etal15DBpedia, ; Mahdisoltani-etal15YAGO, ; li2022kcube, ; li2022constructing,
; dong2023hierarchy, ), which are often formulated as $\\{(h,r,t)\\}$
indicating there is a relation $r$ between the head entity $h$ and tail entity
$t$. Since KGs are usually incomplete (zhang2022contrastive, ; dong2023active,
), as well as the expensive costs to collect facts manually, how to
automatically perform knowledge graph completion (KGC) has been a widely-
studied topic in the KG community (chen2020review, ; zhang2023integrating, ;
ji2021survey, ). Currently, embedding-based methods (bordes2013translating, ;
yang2014embedding, ; lin2015learning, ; trouillon2016complex, ;
kazemi2018simple, ) play a dominant role in the KGC problem. In general, the
typical methods embed the entities and relations into a low-dimensional space
with various objectives and then predict the relation between any two
entities, i.e., $p(r|h,t)$. However, most embedding-based methods are merely
applicable under transductive settings, where KGC models predict the missing
relations among entities that are already present in the training set. When
some unseen entities are newly added during testing, they have to retrain the
whole KG embeddings for accurate inference, which is not feasible in practice
due to the high update frequency and large sizes of many real-world KGs.

Recently, there has been increasing interest on KGC under inductive setting
(wang2019logic, ; wang2021relational, ), where KGC models are used to infer
the relations for newly-coming entities that have never appeared in the
training set. The inductive KGC is more reflective of real-world scenarios, as
KGs always keep introducing new information, such as new users and products in
e-commerce KGs and new molecules in biomedical KGs. Some efforts have been
made to obtain the inductive embeddings for new entities using external
resources, such as entity attributes (hao2020inductive, ; qin2020generative,
), textual descriptions (shi2018open, ; tang2019knowledge, ) and ontological
schema (geng2021ontozsl, ). But these supplemental sources are often
prohibitive to acquire, impeding their success in practice. An alternative
solution is to induce entity-independent rules from the KG in either
statistical (galarraga2013amie, ; meilicke2018fine, ) or differentiable
manners (yang2014embedding, ; yang2017differentiable, ; sadeghian2019drum, ).
It regards inductive KGC as a rule mining problem, i.e. predicting the
relationship $r$ for any entity pair $(h,t)$ based on predefined or adaptively
learned rules. However, these methods often suffer from scalability issue and
lack the capability of learning expressive representations for real-world
datasets since different KGs have distinct rules with domain knowledge
involved.

As the prosperity of graph neural networks (GNNs) and their strong inductive
bias (zhou2023interest, ; chen2022neighbor, ; chen2020label, ; chen2020graph,
), many works extend message-passing (MP) strategy used in GNNs to multi-
relational graphs for inductive KGC (schlichtkrull2018modeling, ;
teru2020inductive, ; wang2021relational, ; wang2022exploring, ). GraIL
(teru2020inductive, ) is one of the pioneer work, which implicitly learns
logical rules by reasoning over enclosing subgraphs. Specifically, GraIL first
extracts an enclosing subgraph surrounding the target triple, and then
generate the representations of entities by aggregating the structural
information of its neighbors in the extracted subgraph. GraIL and its follow-
up methods (chen2021topology, ; liu2021indigo, ; ontologyschema, ;
lee2023ingram, ; jininductive, ; cui2022inductive, ; zhang2018link, ;
zhang2020revisiting, ) have shown promising results using message passing over
subgraphs for inductive KGC. However, the inductive capability of these
methods is usually limited by two key issues. $(i)$ Entity representations
generated by gathering the local information within the subgraph are over
coarse-grained for accurate KG reasoning. It is because KGC always suffers
from data sparsity, and the situation is even more difficult in inductive KGC,
where the new emerging entities usually have few or even no connections to the
original KG. $(ii)$ Existing message passing methods assume that messages are
associated with nodes (entities) and are passed from nodes to nodes
iteratively (xu2018powerful, ). Such entity-oriented message passing strategy
weakens the role of relation semantics (wang2021relational, ), which violates
the nature of inductive KGC since the learned logical evidence should be
entity-independent.

In real-world scenarios, the enclosing subgraph of a particular triple in the
KG contains the logical evidence needed to deduce the relation between the
target nodes (Teru2020InductiveRP, ). Taking Figure 1 $(i)$ as an example,
learning the relation pattern among Elon Musk, TESLA, and California State can
help the KGC model make a confident prediction of (Martin Eberhard, :Livein,
California State) since “:LiveIn $\simeq$ :WorkAt $\land$ :LocatedIn”. To this
end, we propose a novel message passing neural framework, i.e., NORAN, which
aims to mine relation semantics for inductive KG completion. Specifically, we
first provide a deep insight of formulating the problem to bridge the gap
between embedding-based paradigm and inductive setting. Inspired by the
findings, we propose relation network, a novel relation-induced graph derived
from the original KG. The reconstructed relation network provides a hyper view
towards KG modeling by centering relations. More concretely, its topological
structure clearly reflects the distribution of relations, i.e., each node in
the relation network represents a relational instance and the links among the
nodes reflect the relation correlation. Thus, modeling the relation network
via message-passing networks can naturally capture relation patterns as
entity-independent context information to conduct inductive KGC. In this
paper, we formally define such context information as logic evidence and
reveal its correlations with our relation network. Our main contribution is
summarized as follows:

Table 1. Unified notations for crucial terms. Notation | Description
---|---
$\mathcal{G}$ | a knowledge graph
$(h,r,t)$ | (head entity, relation, tail entity)
$\widetilde{\mathcal{G}}$ | a relation network
$\Gamma(\cdot)$ | the combination function in relation network
$\Psi^{k}$, $\Omega^{k}$ |  $k$-layer GNN models

  * •

We propose a novel message-passing framework, i.e., NORAN, which aims to mine
latent relation semantics for inductive KG completion.

  * •

Centering on relations, we propose a hyper view towards KG modeling, i.e.,
relation network, and formally define the inductive KGC as k-hop logic
reasoning over the hypergraph.

  * •

We propose a informax training objective to implicitly capture logic evidence
from relation network for effective KGC.

  * •

We conduct a detailed theoretical analysis to explore which kind of message-
passing strategy is more effective and provide guidelines for model selection
to enable inductive reasoning over the reconstructed relation network.

  * •

Extensive experiments on five real-world KG benchmarks demonstrate the
superiority of our proposed NORAN over state-of-the-art competitors.

##  2\. Preliminaries

###  2.1. Transductive KG Completion

Given any pair of entities $(h,t)$, traditional KG completion model aims to
predict the probability of relation $r$ linking $h$ and $t$, i.e. $p(r|h,t)$.
The relation type with the highest probability will be the output after
ranking. Some related work also equally formalizes the problem as a relation
classification problem, which predicts the relation type with
${Softmax}_{r}(p(r|h,t))$.

Currently, the embedding-based paradigm dominates the transductive KGC
problem. TransE (bordes2013translating, ), DistMult (yang2014embedding, ),
TransR (lin2015learning, ), ComplEx (trouillon2016complex, ), and SimplE
(kazemi2018simple, ) are the representative embedding-based methods, which
embed entity and relations into RHS space with carefully designed modeling
strategy. Embedding-based methods encompass two branches: $(i)$ translating-
based methods, which interpret relations as translation operations on the low-
dimensional embeddings of entities; $(ii)$ semantic matching methods, which
compute the similarity between relations and entities with their semantic
information instantiated by their low-dimensional representations. Despite its
capability to learn expressive representations, the embedding-based paradigm
is not applicable under inductive settings since they have to retrain the
whole KG embeddings when some unseen entities are newly added during testing.

Figure 1. (i) A toy example of inductive knowledge graph completion, i.e.
predicting the relationship (“?”) for unseen entities, e.g. “Martin Eberhard”,
provided with a few links, e.g. (Martin, :WorkAt, TESLA); (ii) Illustration of
the corresponding relation network for knowledge graph, which regards each
triple as a relational node and thus could aggregate context information for
inductive inference without expensive retraining look-up embedding tables as
embedding-based paradigm.

###  2.2. Inductive KG Completion

Different from transductive KGC, inductive KGC tries to predict the missing
relations for a set of new entities that are not present in the training set.
Given a knowledge graph $\mathcal{G}=\\{\mathcal{E},\mathcal{R}\\}$ and a set
of incoming entities $\mathcal{E}_{u}=\\{e\ |\ e\notin\mathcal{E}\\}$, our
goal is to predict the missing relations among $\mathcal{E}$ and
$\mathcal{E}_{u}$. The prediction task contains two scenarios: $(i)$ predict
relations between $e_{1}\in\mathcal{E}$ and $e_{2}\notin\mathcal{E}$ with
$P(r|e1,e2)$, namely inductive relation prediction; $(ii)$ predict relations
within unseen entities ($e\notin\mathcal{E}$), namely fully-inductive relation
prediction. Both two tasks emphasize on learning entity-independent logic
evidence and typical representations of relations. In this work, we focus on
the former setting, inductive relation prediction, since the latter is within
the scope of transfer learning that leverages the information from one KG to
the others.

Under inductive settings, most of the previous effective works can be
summarized as rule-induction based paradigm (yang2014embedding, ;
yang2017differentiable, ; sadeghian2019drum, ; shengyuan2024differentiable, ),
which follows explicit or implicit logic evidence for knowledge graph
reasoning. It is worth noting that this paradigm is compatible with embedding-
based strategy, and most rule-induction-based methods are on the branch of the
aforementioned semantic matching methods. More recently, with the prosperity
of GNNs, many works (wang2021relational, ; teru2020inductive, ;
schlichtkrull2018modeling, ; yan2022cycle, ) extend the MP strategy to
knowledge graphs. R-GCN (schlichtkrull2018modeling, ) firstly proposed a graph
convolution operation for relational data. GraIL (teru2020inductive, ) and its
follow-up methods (cui2022inductive, ; zhang2018link, ; ontologyschema, ;
lee2023ingram, ; jininductive, ; zhang2020revisiting, ; geng2023relational, ;
lin2022incorporating, ) applied the linking prediction techniques, i.e.
subgraph extraction and labeling trick, to tackle the inductive KGC problem.
MP-based methods benefit from their inductive bias but still require dedicated
efforts to design the relational message-passing strategy with various options
of combination and aggregation functions. By contrast, provided with extensive
existing SOTA GNN architectures, our proposed framework is model-agnostic to
take full advantage of them. Furthermore, the significance of relation
semantics has been concurrently acknowledged in several recent studies
(ontologyschema, ; lee2023ingram, ; jininductive, ). Notably, the relation
network in our research diverges substantially from the relation graph used in
these work. They introduced relation schema to quantify the interconnectivity
among various types of relations for inductive KGC with new relations, while
our proposed relation network aims to capture the contextual semantics between
every pair of relational triples for KGC with previously unseen entities.

##  3\. Problem Formulation

We unify the main notations used in this work and provide a brief view in
Table 1. We provide an insight into the gap between embedding-based paradigms
and inductive settings. Given a KG $\mathcal{G}=\\{(h,r,t)\ |\
h,t\in\mathcal{E},r\in\mathcal{R}\\}$, the embedding-based paradigms formalize
their model as $p(r|h,t)$, where predict the relationship $r$ with the prior
knowledge of entities $h$ and $t$. However, under inductive setting, the new
entities trigger non-trivial perturbation to the distribution of the prior
knowledge graph, thus biasing the model $p(r|h,t)$ from the prior ground truth
$p(h,t)$. To this end, we propose a new formulation for the general KGC
problem:

(1) $\small p(h,r,t)=p(r|h,t)\cdot p(h,t),$

where we predict triple existence, i.e. $p(h,r,t)$, rather than the
conditional probability $p(r|h,t)$. Such a formulation has several profits.
Firstly, $p(h,r,t)$ is capable of capturing the evolving distribution of
$p(h,t)$ under inductive setting since no prior distribution is required.
Meanwhile, for transductive setting, where $p(h,t)$ is static, $p(h,r,t)$ can
be collapsed to the previous modeling $p(r|h,t)$. From another perspective,
$p(h,r,t)$ encompasses two crucial terms, relation type $p(r|h,t)$ and
relation existence $p(h,t)$. Previous modeling $p(r|h,t)$ predicts the
relation type $r$ between an entity pair $(h,t)$, which is identical to a
classification problem. However, an ideal KGC model should not only predict
the relation type but also induce the incomplete entity pairs $(h,t)$, while
the latter one is unfortunately ignored in previous modeling. To this end, we
propose relation network, a novel view towards knowledge graph modeling. It
augments the target KG into hyper-views by regarding each relational triple as
nodes. Following this, the link prediction task, i.e., $p(r|h,t)$, can be
naturally transformed into predicting the existence of the corresponding node
in the reconstructed relation network, i.e., $p(h,r,t)$.

##  4\. Methodology

In this section, we propose NORAN to mine latent pattern among relational
instances for inductive KG completion. As shown in Figure 1, our proposed
NORAN consists of three key components: $(i)$ Relation network construction.
It provides a new modeling of KGs by centering on relations. $(ii)$ Relational
message passing, a relational message passing framework is defined to
implicitly capture entity-independent logical evidence from the reconstructed
relation network. $(iii)$ Training scheme and KG inference. Furthermore, we
also provide a detailed theoretical analysis to explore which kind of MP
strategy is more effective and provide guidelines for model selection to
enable inductive reasoning over the reconstructed relation network.

###  4.1. Relation Network Construction

Traditional KG representation learning methods usually model the KG as a
heterogeneous graph by centering on the entities and regarding relations as
semantic edges. However, it is hard to capture complex semantics from KG
relations and further learn expressive representations for inductive KGC. To
fill the gap between traditional KG representation learning paradigm and
inductive KGC, in this work, we value the correlations between relations,
accordingly provide a novel hyper view towards KG modeling with relations, and
formally define the inductive KG completion as k-hop logic reasoning over an
entity-independent network.

Table 2. The general description framework for MP layers

MP layer | Motivation | Convolutional Matrix $\mathcal{C}$ | Feature Transformation $f$ | Category of $\mathcal{C}$
---|---|---|---|---
GCN (kipf2016semi, ) | Spatial Convolution | $\mathcal{C}=\widetilde{\bm{D}}^{1/2}{(\bm{A}+\bm{I})}\widetilde{\bm{D}}^{1/2}$ | $f=\bm{W}\in\mathbb{R}^{d_{k}\times d_{k+1}}$ | Fixed
GraphSAGE (hamilton2017inductive, ) | Inductive Learning | $\mathcal{C}=\widetilde{\bm{D}}^{-1}(\bm{A}+\bm{I})$ | $f=\bm{W}\in\mathbb{R}^{d_{k}\times d_{k+1}}$ | Fixed
GIN (xu2018powerful, ) | WL-Test | $\mathcal{C}=\bm{A}+\bm{I}$ |  $f$ is a two-layer MLP | Fixed
SGC (wu2019simplifying, ) | Scalability | $\mathcal{C}=\widetilde{\bm{D}}^{1/2}{(\bm{A}+\bm{I})}\widetilde{\bm{D}}^{1/2}$ | $f=lambda\ x:x$ | Fixed
GAT (velivckovic2017graph, ) | Self Attention | $\begin{cases}\mathcal{C}=(\bm{A}+\bm{I})\cdot\mathcal{T}\\\ \mathcal{T}_{(i,j)}=\frac{exp([\Theta\bm{x}_{i}||\Theta\bm{x}_{j}]\cdot\bm{a})}{\sum_{k\in\mathcal{N}(i)\cup i}exp([\Theta\bm{x}_{i}||\Theta\bm{x}_{j}]\cdot\bm{a})}\end{cases}$ | $f=\Theta\in\mathbb{R}^{d_{k}\times d_{k+1}}$ | Learnable
a $\widetilde{\bm{D}}$ is the diagonal matrix of $(\bm{A}+\bm{I})$

####  4.1.1. Relation network

To better capture the latent logic evidence for effective reasoning, we first
propose a novel view towards knowledge graph modeling that augments the target
KG into hyper-views by compressing each triple into a relational node.
Concretely, we perform a relation-induced construction process to build the
_relation network_. In essence, we follow one strategical criterion: regard
each triple as relational nodes and link them in the relational graph if they
share the same entity in the original KG.

###### Definition 0.

Relation network. Given a knowledge graph
$\mathcal{G}=\\{(h,r,t)|h,t\in\mathcal{E},r\in\mathcal{R}\\}$, the
corresponding relation network is the triple-level graph
$\mathcal{G}_{r}=(\widetilde{\mathcal{V}},\widetilde{\mathcal{A}},\widetilde{\mathcal{X}_{r}})$,
where $\widetilde{\mathcal{V}}$ and $\widetilde{\mathcal{A}}$ are the set of
relational nodes and adjacency metric respectively.
$\widetilde{\mathcal{X}_{r}}=\\{\Gamma(h,r,t)\ |\ (h,r,t)\in\mathcal{G}\\}$
represents the feature matrix of $\widetilde{\mathcal{V}}$, where
$\Gamma(\cdot)$ is the concatenation function that transforms each relational
triple into a node, i.e., $v=\Gamma(h,r,t)$.
$\widetilde{\mathcal{A}}(v,u|v,u\in\widetilde{\mathcal{V}})=1$, if $v$ and $u$
share the same entity in the original KG.

According to this criterion, there are two latent construction particulars
corresponding to two construction issues: $(i)$ the semantics of various
‘entity sharing’ patterns (Remark 1 in Section 5.3) and $(ii)$ the semantics
of the ‘linking direction’ (Remark 2 in Section 5.3). We conduct a detailed
ablation study in Section 5.3 to explore different ways to construct the
relation network.

####  4.1.2. Interpretation with logic reasoning

The topological graph structure of the relation network clearly reflects the
distribution of relations and the link between different nodes reflects the
relation correlations. Thus, modeling the relation network via a k-layer
message-passing network can naturally capture relation patterns as entity-
independent context information to conduct inductive KGC. In this paper, we
formally define such context information as the k-hop logic evidence over the
relation network.

###### Definition 0.

K-hop logic evidence. Let
$\widetilde{\mathcal{G}}=(\widetilde{\mathbf{V}},\widetilde{\mathcal{A}})$ be
the relation network of a knowledge graph
$\mathcal{G}=(\mathcal{E},\mathcal{R})$. Given any center node
$v_{i}\in\widetilde{\mathbf{V}}$, the k-hop ego graph
$\widetilde{\mathcal{G}_{i}}=(\widetilde{\mathbf{V}}_{i},\widetilde{\mathbf{A}}_{i})$
centering at $v_{i}$ contains the relational contextual information for
logical reasoning. In this paper, we model such contextual information as
$\Lambda^{k}(v_{i})$ via a k-layer message-passing network $\Omega$. Thus, the
overall logic evidence of knowledge graph $\mathcal{G}$ can be modeled by
traversing all k-hop ego graphs, i.e.,
$\Lambda(\mathcal{G})=\Omega_{GNN}(\Lambda^{k}(v)\ |\
v\in\widetilde{\mathcal{G}})$.

Taking a logic evidence “:Livein = :WorkAt $\land$ :Locatedin” in Fig. 1 $(i)$
as an instance, the relation pattern among Elon Musk, TESLA, and California
State is a typical instantiation of the logic evidence and the triple (Martin
Eberhard, :LiveIn, California State) can be predicted with relative certainty.
Mapping to relation network of Fig. 1 $(ii)$, according to Definition 2, such
logic evidences are transformed into $k$-hop ego graphs centering on target
nodes, which describe the relational context information for reasoning.

Generally, there are two crucial benefits of constructing relation network:
$(i)$ Relation network provides a novel view towards KG modeling, from which
entity-independent logic evidence can be naturally modeled via $k$-hop ego
graphs that sampled from the relation network to conduct inductive KGC,
without fine-grained embeddings for unseen entities. $(ii)$ Compared with
original KG, the relation network shows a more dense structure and is
compatible with any GNN models.

###  4.2. Relational Message Passing

To capture entity-independent contextual information as logical evidence, we
propose a novel relational message-passing framework to conduct inductive KGC.

####  4.2.1. Feature initialization

Since every instance in the relation network is transformed from a
corresponding triple $(h,r,t)$ in the original KG, we first randomly
initialize the embedding of entities and relations in the original KG, and
then adopt a local information modeling layer, i.e, a set of Bi-LSTM units, to
learn the local relational structure within each triple:

(2)
$\small\small\bm{x}_{i}=\Gamma(h,r,t)=concat(\Phi(\bm{e}_{h},\bm{e}_{r},\bm{e}_{t})),$

where $\Phi(\cdot)$ is a Bi-LSTM unit, and $\bm{e}_{h},\bm{e}_{r},\bm{e}_{t}$
are the initial embeddings of $h$, $r$, and $t$. The output triple embedding
$\bm{x}_{i}$ could well capture the relational structure within the input
triple. Thus, we used it as the initial node embedding in the relation
network. Note that entity embeddings are fixed during the training and
inference.

####  4.2.2. Message passing

Message-passing layer is formulated as:

(3) $\small\bm{X}^{(k+1)}=\sigma\big{(}\mathcal{C}^{(k)}\bm{X}^{(k)}\circ
f^{(k)}\big{)},$

where $\bm{X}^{(k)}$ is the relational embedding at the k-th layer;
$\mathcal{C}^{(k)}$ is the convolutional matrix for $k$-th layer;
$f^{(k)}:\mathbb{R}^{d_{k}}\rightarrow\mathbb{R}^{d_{k+1}}$ is the linear
transformation matrix; and $\sigma$ is the activation function. The
reformulation of MP layers can be found on Table 2. Message passing over the
relational instances enables the natural capture of relation patterns as
entity-independent context information, which is crucial for conducting
inductive KGC.

In this paper, we train two message-passing GNNs, i.e., $\Omega$ and $\Psi$:
$\Omega$ is applied on the k-hop ego graph to extract logical evidence, while
$\Psi$ is applied on relation network to learn relational embedding for
inductive inference.

####  4.2.3. Mutual information maximization

Reasoning with logical evidence is crucial for inductive KGC, which imitates
the inference process of human beings. However, as aforementioned, logic
evidence is notoriously sophisticated for representation learning and is
usually utilized to regularize reasoning in previous practice. In light of
this, we propose Logic Evidence Information Maximization (LEIM). At a high
level, it is a training objective that tries to maximally preserve mutual
information between logic evidence learned from k-hop ego graphs and
relational semantics of center node.

(4)
$\small\small\mathcal{L}_{\omega,\psi}=-\mathcal{I}_{\omega}(\Lambda(\mathcal{G}),\Psi^{k}(\widetilde{\mathcal{G}})),$

where $\Lambda(\mathcal{G})=\Omega_{GNN}(\Lambda^{k}(v)\ |\
v\in\widetilde{\mathcal{G}})$ is the learned logic evidence,
$\mathcal{I}(\cdot,\cdot)$ is the mutual information; $\Psi^{k}(\cdot)$ is a
$k$-layer GNN; and $\omega,\psi$ are the trainable parameters for
$\mathcal{I}$ and $\Psi$, respectively. The loss is minimized to find the
optimal parameters $\hat{\psi}$ that maximally preserve the mutual information
between logic evidence $\Lambda(\mathcal{G})$ and the relational embedding of
target node $v$ learned with $\Psi^{k}(\widetilde{\mathcal{G}})$. In practice,
we adopt a Jensen-Shannon MI estimator (JSD) (hjelm2018learning, ;
nowozin2016f, ; zhu2020transfer, ):

(5)
$\mathcal{I}^{JSD}_{\omega,\psi}(\Lambda,\Psi)=\mathbb{E}_{\mathbb{P}}\Big{(}-sp(-T_{\omega,\psi}(\Lambda^{k}(v),\Psi^{k}(v)))\Big{)}\\\
-\mathbb{E}_{\mathbb{P}\times\mathbb{P}^{\prime}}\Big{(}-sp(T_{\omega,\psi}(\Lambda^{k}(v^{\prime}),\Psi^{k}(v)))\Big{)},$

where $v$ is the target node sampled from the relation network according to
distribution $\mathbb{P}$, $v^{\prime}$ is sampled from negative distribution
$\mathbb{P}^{\prime}=\mathbb{P}$, and $sp$ denotes softplus activation
function. To encourage positive pairs, e.g. $(\Lambda(v),\Psi(v))$, and
distinguishes negative pairs, e.g. $(\Lambda(v^{\prime}),\Psi(v))$, where
$v\neq v^{\prime}$, we introduce $T_{\omega,\psi}(\Lambda,\Psi)$ to predict
the correlation between $\Lambda$ and $\Psi$ inspired by GNN pretraining
(zhu2020transfer, ; hu2020gpt, ), formulated as:

(6) $\small
T_{\omega,\psi}(\Lambda^{k}(v),\bm{x}_{v})=\sum_{(p,q)\in\Lambda^{k}(v)}\log(f_{\omega}([\bm{h}_{p}||\bm{h}_{q}||\bm{x}_{v}])),$

where $\bm{h}_{p}$ and $\bm{h}_{q}$ are the output features of the source node
$p$ and the target node $q$ generated from the k-hop logical ego graph
$\Lambda^{k}(\mathcal{G})$, $\bm{x}_{v}=\Psi^{k}(v)$ is the relatioinal
embedding of node $v$.
$f:\mathbb{R}^{|\bm{h}|+|\bm{h}|+|\bm{x}|}\to\mathbb{R}^{(0,1)}$ is a fully-
connected discriminator to distinguish the positive pairs and negative pairs.

// All notations are consistent with Table 1

Input: a Knowledge Graph $\mathcal{G}$

Output: a combination function $\Gamma$ and a GNN model $\Psi$

Init: create the relation network $\widetilde{\mathcal{G}}$

while  _not convergence_ do

foreach  _batch
$\mathcal{B}=(\mathcal{V}_{\mathcal{B}},\mathcal{E}_{\mathcal{B}})$ from
$\mathcal{\widetilde{G}}$_ do

$\bm{X}_{\mathcal{B}}:=\Gamma(\mathcal{V}_{\mathcal{B}})$ ;

// Eq.(2)

$\bm{X}_{\mathcal{B}}:=\Psi(\bm{X}_{\mathcal{B}},\mathcal{E}_{\mathcal{B}})$

$\mathcal{L}=-\mathcal{I}_{\omega}(\Lambda^{k}(\mathcal{G}),\bm{X}_{\mathcal{B}})$
;

// Eq.(5)

$\mathcal{L}$.optimize()

end foreach

end while

Algorithm 1 Logical Reasoning with Relation Network

###  4.3. Training Scheme and KG Inference

####  4.3.1. Training objective

In this section, we briefly introduce our complete algorithm of NORAN and
present the training scheme in Algorithm 1. After this, we obtain the model
$\Psi\circ\Gamma$ to infer expressive representations of inductive triples.
Given the final relational embedding for an inductive triple learned from
model $\Psi\circ\Gamma$, we conduct the link prediction with a classifier
using logistic regression, i.e. $p(\bm{x})=Sigmoid(\bm{w}^{T}\bm{x}+b)$.

####  4.3.2. Inductive inference and complexity analysis

For inductive inference, given any triple $t=(h,r,t)$ with an unseen entity
$h$ or $t$, we first create a new node $v=\Gamma(h,r,t)$ and update the
original relation network $\widetilde{\mathcal{G}}$ by adding node $v$ to it.
Then we predict the probability of triple existence with
$p\circ\Psi\circ\Gamma$.

In contrast with the Embedding-based Paradigm, which requires retraining for
inductive inference, our proposed framework only needs updating the relation
network and then inferring with the trained model $p\circ\Psi\circ\Gamma$.
Formally, the inference time complexity of our proposed framework is:

$\mathcal{O}(\underbrace{3bf^{2}}_{\Gamma}+\underbrace{bd^{L}f+bLf^{2}}_{\Psi}),$

where $b$ is the number of inductive triples; $f$ is the hidden dimension
assuming all embeddings (relation, entity, and triple) have the same
dimension; $d$ is the averaged node degree in relation network
$\widetilde{\mathcal{G}}$; and $L$ is the number of layers of $\Psi$. Notably,
we omit the time complexity of $p$ and relation network renewal, since both of
which are smaller than the others by magnitudes. Therefore, the main inference
time overhead lies on the message passing operation of $\Psi$, which could
exponentially grow with $L$. However, based on our empirical results, a two-
layer GNN could generally achieve the on-par performance given the naturality
of the local view for GNNs. This is also consistent with the argument for
deepening GNNs (chen2021bag, ).

###  4.4. GNN Instantiations Selection

Our proposed framework is model-agnostic and compatible with all GNN
frameworks. One can select the most effective GNN model by performing an
exhausting search. However, it is expensive in terms of computing resources
and not the focus of this work. In this section, we provide a valid conjecture
on the selection of GNN models via a comprehensive theoretical analysis.
Please note that our evaluation space focuses on intrinsic MP layers,
regardless of other training tricks like residual connections and
normalization (chen2021bag, ).

####  4.4.1. General framework of MP layer

Typically, based on the convolution matrix, there are two categories for
representative MP layers: $(i)$ Fixed MP: GCN (kipf2016semi, ), GraphSAGE
(hamilton2017inductive, ), GIN (xu2018powerful, ), SGC (wu2019simplifying, );
$(ii)$ Learnable MP: GAT (velivckovic2017graph, ). The reformulation of
typical MP layers can be found on Table 2. Recall that we actually train two
GNN models during our training process: one is $\Psi$ that applied on relation
network for inductive inference; and the other is $\Omega$ that applied on
logic evidence for discriminating negative samples. We unify exactly the same
architecture in our implementation for simplification.

####  4.4.2. Influence distribution

Our conjecture for model selection is motivated by a general question: what
type of GNNs is capable of capturing the proper logic evidence for inductive
inference? Taking Fig. 1 $(2)$ as an example, when we try to inference the
relationship between Martin Eberhard and California (i.e. Node $8$), some
existing logic evidence, Elon Musk $\xrightarrow{\text{:WorkIn}}$ TESLA
$\xrightarrow{\text{:LocatedIn}}$ California and Martin Eberhard
$\xrightarrow{\text{:WorkIn}}$ TESLA (i.e. Node $4$, $5$, and $7$) are more
proper than the others. Therefore, in better MP strategies, node $4$, $5$, and
$7$ would have more influence on the inference. Related to ideas of
sensitivity analysis and influence functions in statistics
(xu2018representation, ), we measure the sensitivity of node x to node y, or
the influence of y on x with the concept of influence distribution.

###### Definition 0.

Influence Distribution: Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
let $\bm{h}_{v}^{(i)}$ be the hidden features of node $v$ at $i$-th layer of a
$k$-layer GNN model $\Psi$. The influence score of node $u$ on node $v$ is
defined as
$\mathcal{S}(u,v)=\sum_{i,j}\Bigg{[}\frac{\partial\bm{h}_{u}^{(k)}}{\partial\bm{h}_{v}^{(0)}}\Bigg{]}_{(i,j)}$.
Then the influence distribution is defined as
$\mathcal{S}_{v}(u)=\mathcal{S}(u,v)/\sum_{i\in\mathcal{V}}\mathcal{S}(i,v)$,
which is the normalization of the corresponding influence score over all
nodes.

####  4.4.3. Theoretical analysis

Previous studies have verified that influence distributions of common
aggregation schemes are closely connected to random walk distributions
(xu2018representation, ). Extending the theorem to general MP frameworks, we
can get a corollary as follows.

###### Corollary 0.

Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, let $\bm{h}_{v}^{(i)}$
be the hidden features of node $v$ at $i$-th layer of a $k$-layer GNN model
$\Psi$ whose MP can be rewritten as
$\bm{X}^{(i+1)}=\sigma\big{(}\mathcal{C}^{(i)}\bm{X}^{(i)}\circ
f^{(k)}\big{)}$. If the convolution matrix is pre-fixed, i.e.
$\frac{\partial\mathcal{C}}{\partial\bm{X}^{(i)}}=\bm{0}$, the influence
distribution of any node $v$ is in expectation equal to a biased $k$-step
random walk distribution, where the transition matrix is $\mathcal{T}$.
$\mathcal{C}=(\bm{A}+\bm{I})\cdot\mathcal{T}$.

###### Proof.

Let $f^{(l)}(\bm{x})=f_{m}^{(l)}\circ f_{m-1}^{(l)}\circ\cdots\circ
f_{1}^{(l)}$ be a $m$-layer MLP without learnable bias, where
$f_{m}^{(l)}(\bm{x})=\sigma(\bm{W}_{m}^{(l)}\bm{x})$. let
$\mathcal{C}=(\bm{A}+\bm{I})\cdot\mathcal{T}$, where $\mathcal{T}$ is a pre-
fixed weighted matrix. For any layer, by chain rule, we have

$\frac{\partial\bm{h}_{u}^{(l)}}{\partial\bm{h}_{v}^{(0)}}=\frac{\partial
f_{m}^{(l)}}{\partial f_{m-1}^{(l)}}\cdot\frac{\partial
f_{m-1}^{(l)}}{\partial f_{m-2}^{(l)}}\cdots\frac{\partial
f_{2}^{(l)}}{\partial
f_{1}^{(l)}}\cdot\sum_{i\in\widetilde{\mathcal{N}}(\bm{u})}\mathcal{T}_{u,i}\frac{\partial\bm{h}_{i}^{(l-1)}}{\partial\bm{h}_{v}^{(0)}},$

where $\frac{\partial f_{m}^{(l)}}{\partial
f_{m-1}^{(l)}}=\text{diag}\big{(}\bm{1}_{f_{m-1}^{(l)}>0}\big{)}\cdot\bm{W}_{m-1}^{(l)}$.
Further more, according to chain rule and the message passing strategy, we get

$\frac{\partial\bm{h}_{u}^{(k)}}{\partial\bm{h}_{v}^{(0)}}=\sum_{p\in\mathcal{P}}^{|\mathcal{P}|}\prod_{l=k}^{1}\mathcal{T}_{v_{p}^{l},v_{p}^{l-1}}\frac{\partial
f_{m}^{(l)}}{\partial f_{1}^{(l)}},$

where $\mathcal{P}$ is the set of paths of length $k+1$ from node $u$ to node
$v$. We can express an entry of the derivative for path $p$ as:

$\bigg{[}\frac{\partial\bm{h}_{u}^{(k)}}{\partial\bm{h}_{v}^{(0)}}\bigg{]}^{(i,j)}_{p}=\bigg{(}\prod_{l=k}^{1}\mathcal{T}_{v_{p}^{l},v_{p-1}^{l}}\bigg{)}\bigg{(}\sum_{q}^{\mathcal{Q}}z_{q}\prod_{l=k}^{1}\prod_{t=m}^{1}w_{q,t}^{(l)}\bigg{)},$

where $\mathcal{Q}$ is the set of paths $q$ from the input neuron $i$ to the
output neuron $j$. $w_{q,t}^{(l)}$ denotes the neuron of $\bm{W}_{m}^{(l)}$ on
path $q$. $z_{q}\in\\{0,1\\}$ denotes whether the path is activated. Under the
assumption that all $z_{q}$s obeys the same Bernoulli distribution, i.e.
$P(z_{q}=1)=\beta$, we have:

$\mathbb{E}\bigg{[}\frac{\partial\bm{h}_{u}^{(k)}}{\partial\bm{h}_{v}^{(0)}}\bigg{]}=\underbrace{\beta\cdot\prod_{l=k}^{1}\prod_{t=m}^{1}\bm{W}_{t}^{(l)}}_{u,v\text{
irrelevant}}\cdot\bigg{(}\sum_{p\in\mathcal{P}}^{|\mathcal{P}|}\prod_{l=k}^{1}\mathcal{T}_{v_{p}^{l},v_{p-1}^{l}}\bigg{)}.$

As the former term is $u,v$ irrelevant, after normalization, the influence
distribution of $\mathcal{S}_{v}(u)$ is
$\sum_{p\in\mathcal{P}}^{|\mathcal{P}|}\prod_{l=k}^{1}\mathcal{T}_{v_{p}^{l},v_{p-1}^{l}}$,
which is exactly a bias random walk distribution whose transition matrix is
$\mathcal{T}$. ∎

It indicates that for those MP layers whose convolution matrix is pre-fixed,
the influence distribution for nodes is only structure-relevant and
irrespective to node features. For graphs that lay stress on the topological
structures, such MP strategies are beneficial. However, for our relation
network whose node contains rich relational semantics is of vital importance
for inductive KGC, a pre-fixed convolution matrix is not desired. In other
words, MP layers with a learnable convolution matrix are probable to capture
the logic evidence and learn more expressive representations for inductive
KGC. We evaluate such conjecture in Section 5.2 by comparing several
representative convolution matrices, $(i)$ learnable: GAT
(velivckovic2017graph, ); $(ii)$ fixed: GraphSAGE (hamilton2017inductive, ),
GIN (xu2018powerful, ). The empirical results further demonstrate our
conjecture to some extent.

##  5\. Experiments

This section empirically evaluates the proposed framework and presents its
performance on five KG datasets. Our empirical study is motivated by the
following questions:

  * •

Q1 (5.2): How does our proposed framework perform in comparison with the
strongest baselines, including traditional embedding-based, rule-based methods
and other MP-based methods?

  * •

Q2 (5.3): W.r.t. Remark 1 and Remark 2, is our proposed relation network a
valid and effective modeling for inductive KG completion?

  * •

Q3 (5.4). Is our proposed logic evidence information maximization a more
effective training objective than standard negative sampling for inductive
KGC?

###  5.1. Experimental Setup

####  5.1.1. Datasets

We conduct experiments on five standard KG benchmarks: $(i)$ FB15K-237 that is
a subset of FB15K where inverse relations are removed; $(ii)$WN18RR that is a
subset of WN18 where inverse relations are removed; $(iii)$ NELL995 that is
extracted from the $995$-th iteration of the NELL system containing general
knowledge; $(iv)$ OGBL-WIKIKG2 that is extracted from the Wikidata knowledge
base; and $(v)$ OGBL-BIOKG that is created using data from a large number of
biomedical repositories.

Table 3. Main results of inductive KGC on five benchmark datasets. We
underline the best results within each of the three categories and bold
NORAN’s results that are better than all baselines.

Categories | Datasets | FB15K-237 | WN18RR | NELL995 | OGBL-WIKIKG2 | OGBL-BIOKG
---|---|---|---|---|---|---
Metrics | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3
Emb. Based | TransE (bordes2013translating, ) | 0.289 | 0.198 | 0.324 | 0.265 | 0.058 | 0.445 | 0.254 | 0.169 | 0.271 | 0.213 | 0.122 | 0.229 | 0.317 | 0.26 | 0.345
DistMult (yang2014embedding, ) | 0.241 | 0.155 | 0.263 | 0.430 | 0.390 | 0.440 | 0.267 | 0.174 | 0.295 | 0.199 | 0.115 | 0.210 | 0.341 | 0.278 | 0.363
ComplEx (trouillon2016complex, ) | 0.247 | 0.158 | 0.275 | 0.440 | 0.410 | 0.460 | 0.227 | 0.149 | 0.249 | 0.236 | 0.136 | 0.254 | 0.322 | 0.257 | 0.360
SimplE (kazemi2018simple, ) | 0.338 | 0.241 | 0.375 | 0.476 | 0.428 | 0.492 | 0.291 | 0.198 | 0.314 | 0.220 | 0.131 | 0.239 | 0.319 | 0.246 | 0.358
QuatE (zhang2019Quaternion, ) | 0.319 | 0.241 | 0.358 | 0.446 | 0.382 | 0.478 | 0.285 | 0.201 | 0.307 | 0.248 | 0.139 | 0.262 | 0.363 | 0.294 | 0.382
Rule Based | RuleN (meilicke2018fine, ) | 0.453 | 0.387 | 0.491 | 0.514 | 0.461 | 0.532 | 0.346 | 0.279 | 0.366 | - | - | - | - | - | -
DRUM (sadeghian2019drum, ) | 0.447 | 0.373 | 0.478 | 0.521 | 0.458 | 0.549 | 0.340 | 0.261 | 0.363 | - | - | - | - | - | -
MP based | RGCN (schlichtkrull2018modeling, ) | 0.427 | 0.367 | 0.451 | 0.501 | 0.458 | 0.519 | 0.329 | 0.256 | 0.348 | 0.285 | 0.176 | 0.324 | 0.381 | 0.319 | 0.399
RGHAT (zhang2020relational, ) | 0.440 | 0.361 | 0.483 | 0.518 | 0.460 | 0.540 | 0.337 | 0.274 | 0.351 | 0.301 | 0.192 | 0.329 | 0.395 | 0.334 | 0.418
GraIL (teru2020inductive, ) | 0.465 | 0.389 | 0.482 | 0.512 | 0.453 | 0.539 | 0.355 | 0.282 | 0.367 | 0.327 | 0.201 | 0.336 | 0.434 | 0.379 | 0.451
ConGLR (lin2022incorporating, ) | 0.463 | 0.402 | 0.483 | 0.512 | 0.452 | 0.541 | 0.352 | 0.276 | 0.366 | 0.318 | 0.219 | 0.338 | 0.422 | 0.365 | 0.431
PATHCON (wang2021relational, ) | 0.483 | 0.425 | 0.499 | 0.522 | 0.462 | 0.546 | 0.349 | 0.276 | 0.369 | 0.339 | 0.243 | 0.347 | 0.457 | 0.395 | 0.472
RMPI (geng2023relational, ) | 0.459 | 0.396 | 0.480 | 0.514 | 0.454 | 0.544 | 0.339 | 0.277 | 0.365 | 0.313 | 0.213 | 0.336 | 0.414 | 0.358 | 0.421
MBE (cui2022inductive, ) | 0.477 | 0.410 | 0.495 | 0.519 | 0.451 | 0.549 | 0.344 | 0.270 | 0.359 | 0.331 | 0.234 | 0.345 | 0.452 | 0.380 | 0.470
Oursa | NORAN(GS) | 0.483 | 0.440 | 0.504 | 0.535 | 0.471 | 0.564 | 0.364 | 0.298 | 0.381 | 0.349 | 0.237 | 0.361 | 0.454 | 0.395 | 0.479
NORAN(GIN) | 0.499 | 0.451 | 0.519 | 0.530 | 0.467 | 0.560 | 0.370 | 0.308 | 0.379 | 0.353 | 0.251 | 0.367 | 0.469 | 0.407 | 0.492
NORAN(GAT) | 0.468 | 0.422 | 0.489 | 0.540 | 0.499 | 0.575 | 0.374 | 0.310 | 0.392 | 0.358 | 0.260 | 0.371 | 0.475 | 0.411 | 0.495
NORAN - Emb.b | +2.2% (Avg.) | +1.6% | +2.6% | +2.0% | +1.8% | +3.7% | +2.9% | +1.9% | +2.8% | +2.3% | +1.9% | +1.7% | +2.4% | +1.8% | +1.6% | +2.3%
NORAN - GNNb | +11.2% (Avg.) | +16.1% | +21.0 % | +14.4% | +6.4% | +7.1% | +8.3% | +8.3% | +10.9% | +7.8% | +11.0 % | +12.1% | +10.9% | +11.2% | +11.7% | +11.5%
a We test our NORAN with three backbones: GraphSAGE, GIN, and GAT, denoted as NORAN(GS), NORAN(GIN), NORAN(GAT), respectively. |  |  |
b We show the margin between the best results of NORAN and the ones of the two branches of baselines methods. |  |  |

####  5.1.2. Baselines

To valid the effectiveness of NORAN, we compare it with the state-of-art
baselines according to our best knowledge. Following the taxonomy
aforementioned in Section 2, we divide all baselines into three categories:
$(i)$ embedding-based: TransE (bordes2013translating, ), DistMult
(yang2014embedding, ), ComplEx (trouillon2016complex, ), SimplE
(kazemi2018simple, ), and QuatE (zhang2019Quaternion, ); $(ii)$ Rule-based:
RuleN (meilicke2018fine, ) and DRUM (sadeghian2019drum, ); $(iii)$ MP-based:
RGCN (schlichtkrull2018modeling, ), RGHAT (zhang2020relational, ), GraIL
(teru2020inductive, ), ConGLR (lin2022incorporating, ), PATHCON
(wang2021relational, ), RMPI (geng2023relational, ) and MBE (cui2022inductive,
). Particularly, the five embedding based methods are not naturally inductive
and we retrain the embedding table for inductive inference. For MP-based
methods, we have selected the most effective ones for KGC in the same setting.
Notably, we did not include several related works (ontologyschema, ;
lee2023ingram, ; jininductive, ) in our experiments since their original
source codes were written only for KGC with unseen relations, while our model
is designed for KGC with unseen entities.

####  5.1.3. Implimentation details

The aforementioned five benchmark datasets were originally developed for the
transductive setting. In other words, the entities of the standard test splits
are a subset of the entities in the training splits. In order to facilitate
inductive testing, we create new inductive benchmark datasets by sampling
disjoint subgraphs from the KGs in these datasets. Specifically, we first
sample a subset of entities from the test set at random, then remove them and
their associated edges from the training set. The remaining training set is
used to train the models, and the removed edges are added back in during
evaluation. We use MRR (mean reciprocal rank) and Hit@1, 3 as evaluation
metrics.

###  5.2. Main Results: Q1

To answer Q1, we perform extensive experiments to compare NORAN with the
strongest baselines best to our knowledge. The comparison results are placed
in Table 3. We summarize our experimental observations as follows.

Obs. 1. NORAN significantly outperforms SOTA KGC baselines. We compare NORAN
(ours) with $5$ representative embedding-based methods, $2$ rule-based methods
and $7$ SOTA MP-based methods on $5$ KG datasets. As shown in Table 3, NORAN
significantly outperforms all other baselines in all evaluation metrics (i.e.,
MRR, Hit@1, Hit@3). Particularly, we bold NORAN’s results that are better than
all baseline. We evaluate NORAN with three commonly-used backbones, and the
bold results notably take the vast majority, indicating the effectiveness of
our proposed NORAN. Besides, we compute the margin between the best results
(underlined) of NORAN and the two branches of baselines by column. Notably,
NORAN outperforms the best embedding-based (MP-based) baseline with a large
margin, averaging $11.2\%$ ($2.2\%$).

Obs. 2. NORAN integrating GAT (learnable convolution matrix) generally
outperforms the MP layers with pre-fixed convolution matrices. We test NORAN
with three backbones: GAT, GraphSAGE, and GIN, where the first one’s
convolution matrix is learnable and the last two pre-fix their convolution
matrices. As shown in Table 3, GAT achieves the best results (underlined) on
four datasets while GraphSAGE and GIN have an on-par performance.

Table 4. Results of ablation study for relation network construction rules on
three benchmark datasets.

Construction Rule | Datasets | WN18RR | NELL995 | OGBL-WIKIKG2
---|---|---|---|---
Metrics | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3
Default | NORAN(GAT) | 0.540 | 0.499 | 0.575 | 0.374 | 0.310 | 0.392 | 0.358 | 0.260 | 0.371
w.o. head-head | NORAN(GAT) | 0.521 | 0.457 | 0.558 | 0.348 | 0.273 | 0.375 | 0.329 | 0.230 | 0.341
w.o. tail-tail | NORAN(GAT) | 0.517 | 0.454 | 0.549 | 0.351 | 0.288 | 0.364 | 0.327 | 0.224 | 0.342
w.o. head-tail | NORAN(GAT) | 0.501 | 0.446 | 0.532 | 0.339 | 0.275 | 0.359 | 0.314 | 0.212 | 0.319

Table 5. Ablation study of training objective, i.e., Logic Evidence
Information Maximization (LEIM)

Training Objective | Datasets | WN18RR | NELL995 | OGBL-WIKIKG2
---|---|---|---|---
Metrics | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3 | MRR | Hit@1 | Hit@3
Naive Negative Sampling | NORAN(GS) | 0.529 | 0.469 | 0.554 | 0.351 | 0.290 | 0.357 | 0.324 | 0.215 | 0.322
NORAN(GIN) | 0.537 | 0.490 | 0.567 | 0.357 | 0.291 | 0.374 | 0.335 | 0.231 | 0.349
NORAN(GAT) | 0.534 | 0.481 | 0.562 | 0.361 | 0.299 | 0.377 | 0.342 | 0.238 | 0.355
LEIM (JSD) | NORAN(GS) | 0.535 | 0.471 | 0.564 | 0.364 | 0.298 | 0.381 | 0.349 | 0.237 | 0.361
NORAN(GIN) | 0.530 | 0.467 | 0.560 | 0.370 | 0.308 | 0.379 | 0.353 | 0.251 | 0.367
NORAN(GAT) | 0.540 | 0.499 | 0.575 | 0.374 | 0.310 | 0.392 | 0.358 | 0.260 | 0.371
LEIM (InfoNCE) | NORAN(GS) | 0.532 | 0.476 | 0.558 | 0.358 | 0.294 | 0.369 | 0.331 | 0.220 | 0.343
NORAN(GIN) | 0.541 | 0.495 | 0.583 | 0.365 | 0.301 | 0.376 | 0.339 | 0.231 | 0.359
NORAN(GAT) | 0.544 | 0.506 | 0.581 | 0.367 | 0.306 | 0.383 | 0.337 | 0.232 | 0.352

###  5.3. Ablation Study on Relation Network: Q2

According to the definition of the relation network, there are two latent
construction particulars corresponding to two construction issues: $(i)$ the
semantics of various ‘entity sharing’ patterns (Remark 1) and $(ii)$ the
semantics of the ‘linking direction’ (Remark 2). We conduct a detailed
ablation study in this section to validate our arguments in Remark 1 and 2.

###### Remark 1.

Linking pattern. For any two triples sharing entities, i.e.
$T_{1}=(h_{1},r_{1},t_{1})\cap T_{2}=(h_{2},r_{2},t_{2})$, we have three
linking patterns: $(i)$ head-head sharing ($h_{1}=h_{2})$, $(ii)$ tail-tail
sharing ($t_{1}=t_{2}$), and $(iii)$ head-tail sharing ($t_{1}=h_{2}\oplus
t_{2}=h_{1}$). For our construction criterion, we build links for any of the
three linking patterns based on the rationale that the three patterns possess
different semantics.

###### Remark 2.

Linking direction. According to Def. 1, for different linking patterns
discussed in Remark 1, we uniformly set the according edges in relation
network as bidirectional edges, omitting the linking directions. The rationale
here is that the semantics of relations in knowledge graphs are not direction-
sensitive. For instance, a typical triple (Elon Musk, :WorkIn, TESLA) in
Figure 1 (i) is semantically identical to (TESLA, :Foundedby, Elon Musk).

To answer Q2, we perform a thorough ablation study for relation network
construction. For remark 1, recalling that relation networks have three
patterns: head-head sharing, head-tail sharing, and tail-tail sharing, we
iteratively ablate each pattern to construct the corresponding relation
network and then use it to train our model. We do this ablation study using
GAT as the backbone. The empirical results are shown on Table 4. As we can
see, ablating any of the three patterns from relation networks would markedly
damage the performance of NORAN, indicating the validness of our construction
rule for relation networks.

Obs. 3. Head-tail pattern weights more than the others for relation network
construction. Particularly, we observe that ablating head-tail patterns would
reduce the performance with a large margin in comparison with the other
ablations. Actually, the head-tail pattern corresponds to the translation-
based logic rules and dominates multi-hop knowledge graph reasoning, while the
other two corresponds, i.e., head-head and tail-tail logically correspond to
the union and intersection operations, respectively, as defined in complex
knowledge graph reasoning (ren2020query2box, ). Admittedly, the experiment
results indicate that the translation-based logic evidence (head-tail pattern)
are crucial for inductive inference, which is actually the same in logic with
multi-hop knowledge graph reasoning. However, according to our results, the
other logic operation (Union and Intersection) can also facilitate KGC, which
is nevertheless ignored by translation-based embedding methods, which, in a
way, explains their relatively worse inductive performance as shown in Table
3.

###  5.4. Ablation Study for Training Objective: Q3

To answer Q3, we perform an ablation study to demonstrate the effectiveness of
LEIM. Specifically, we introduce another InfoNCE estimator (hjelm2018learning,
) which is defined as follows:

(7)
$\small\mathcal{I}^{InfoNCE}_{\omega,\psi}(\Lambda,\Psi)=\mathbb{E}_{\mathbb{P}}\Bigg{(}T_{\omega,\psi}(\Lambda^{k}(v),\Psi^{k}(v))\\\
-\mathbb{E}_{\mathbb{P}^{\prime}}\Big{(}\log\sum_{v^{\prime}\sim\mathbb{P}^{\prime}}e^{T_{\omega,\psi}(\Lambda^{k}(v^{\prime}),\Psi^{k}(v))}\Big{)}\Bigg{)}.$

Then we evaluate LEIM with two MI estimators, i.e., JSD (our default) and
InfoNCE, and compare them to the naive negative sampling (NS) training
objective, which is the common practice in previous works (wang2021relational,
; schlichtkrull2018modeling, ). Selected experiment results are on Table 5. As
shown in Table 5, we bold the best results by column. Obviously, LEIM
generally outperforms Naive NS with a large margin for all three backbones,
demonstrating the effectiveness of our proposed training objective LEIM. The
key difference between JSD and InfoNCE is how negative sampling is performed.
In practice, for JSD, we perform a $1:1$ negative sampling within a batch and
compute the expectation of the data distribution (positive samples) and a
noise distribution (negative samples) separately. For InfoNCE — that is a
typical contrastive learning style — it requires numerous negative samples to
be competitive, where the common practice is utilizing all the other instances
with a batch $\mathcal{B}$ as the negative samples. For a batch size
$|\mathcal{B}|$, it gives $\mathcal{O}(|\mathcal{B}|)$ negative samples per
positive sample. Considering the computing efficiency and our empirical
evaluation in 5.4, we choose the JSD as our default instantiation. In
addition, for the inter-comparison among training objectives, we found one
interesting phenomenon:

Obs. 4. GAT generally benefits the most from LEIM. On three datasets, Through
LEIM, GAT gains a performance increase by an averaging margin of $1.2\%$ in
MRR and $1.5\%$ in Hit@3, which is larger than the other backbones.
Specifically, On WN18RR, GAT performs worst among three training objectives
when Naive NS trains them. However, when applying LEIM, GAT outstandingly
achieves the best result. In contrast, GIN with a prefixed convolution matrix
even has a negative boosting when trained with LEIM.

##  6\. Conclusions and Future work

Inductive KG completion tries to infer relations for newly-coming entities is
more inline with reality as real-world KGs are always evolving and introducing
new knowledge. In this work, we proposed a novel message-passing framework,
i.e., NORAN, which aims to mine latent relation semantics for inductive KG
completion. Initially, we propose a distinctive perspective on KG modeling
termed relation network, which considers relations as indicators of logical
rules. Moreover, to preserve such logical semantics inherent in KGs, we
propose an innovative informax training objective, logic evidence information
maximization (LEIM). The combination of the relation network and LEIM forms
our NORAN framework for inductive KGC. Since our framework is model-agnostic,
we also provide a detailed theoretical analysis to explore which kind of MP
model is more effective for the relation network and provide guidelines for
model selection to enable inductive reasoning. Extensive experiment results on
five KG benchmarks demonstrate the superiority of our proposed NORAN over
state-of-the-art competitors. As part of our future work, we intend to explore
the potential applications of our approach in real-world scenarios, such as
KG-enhanced recommendation systems and question-answering.

## References

  * [1] Kurt D. Bollacker, Robert P. Cook, and Patrick Tufts.  Freebase: A shared database of structured general human knowledge.  In AAAI, 2007.
  * [2] Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer.  Dbpedia - A large-scale, multilingual knowledge base extracted from wikipedia.  Semantic Web, 6(2):167–195, 2015.
  * [3] Farzaneh Mahdisoltani, Joanna Biega, and Fabian M. Suchanek.  YAGO3: A knowledge base from multilingual wikipedias.  In CIDR, 2015.
  * [4] Qing Li, George Baciu, Jiannong Cao, Xiao Huang, Richard Chen Li, Peter HF Ng, Junnan Dong, Qinggang Zhang, Zackary PT Sin, and Yaowei Wang.  Kcube: A knowledge graph university curriculum framework for student advising and career planning.  In International Conference on Blended Learning, pages 358–369. Springer, 2022.
  * [5] Wentao Li, Huachi Zhou, Junnan Dong, Qinggang Zhang, Qing Li, George Baciu, Jiannong Cao, and Xiao Huang.  Constructing low-redundant and high-accuracy knowledge graphs for education.  In International Conference on Web-Based Learning, pages 148–160. Springer, 2022.
  * [6] Junnan Dong, Qinggang Zhang, Xiao Huang, Keyu Duan, Qiaoyu Tan, and Zhimeng Jiang.  Hierarchy-aware multi-hop question answering over knowledge graphs.  In Proceedings of the ACM Web Conference 2023, pages 2519–2527, 2023.
  * [7] Qinggang Zhang, Junnan Dong, Keyu Duan, Xiao Huang, Yezi Liu, and Linchuan Xu.  Contrastive knowledge graph error detection.  In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 2590–2599, 2022.
  * [8] Junnan Dong, Qinggang Zhang, Xiao Huang, Qiaoyu Tan, Daochen Zha, and Zhao Zihao.  Active ensemble learning for knowledge graph error detection.  In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 877–885, 2023.
  * [9] Xiaojun Chen, Shengbin Jia, and Yang Xiang.  A review: Knowledge reasoning over knowledge graph.  Expert Systems with Applications, 141:112948, 2020.
  * [10] Qinggang Zhang, Junnan Dong, Qiaoyu Tan, and Xiao Huang.  Integrating entity attributes for error-aware knowledge graph embedding.  IEEE Transactions on Knowledge and Data Engineering, 2023.
  * [11] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip.  A survey on knowledge graphs: Representation, acquisition, and applications.  IEEE Transactions on Neural Networks and Learning Systems, 33(2):494–514, 2021.
  * [12] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  Advances in neural information processing systems, 26, 2013.
  * [13] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  arXiv preprint arXiv:1412.6575, 2014.
  * [14] Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu.  Learning entity and relation embeddings for knowledge graph completion.  In Twenty-ninth AAAI conference on artificial intelligence, 2015.
  * [15] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard.  Complex embeddings for simple link prediction.  In International conference on machine learning, pages 2071–2080. PMLR, 2016.
  * [16] Seyed Mehran Kazemi and David Poole.  Simple embedding for link prediction in knowledge graphs.  arXiv preprint arXiv:1802.04868, 2018.
  * [17] Peifeng Wang, Jialong Han, Chenliang Li, and Rong Pan.  Logic attention based neighborhood aggregation for inductive knowledge graph embedding.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7152–7159, 2019.
  * [18] Hongwei Wang, Hongyu Ren, and Jure Leskovec.  Relational message passing for knowledge graph completion.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1697–1707, 2021.
  * [19] Yu Hao, Xin Cao, Yixiang Fang, Xike Xie, and Sibo Wang.  Inductive link prediction for nodes having only attribute information.  arXiv preprint arXiv:2007.08053, 2020.
  * [20] Pengda Qin, Xin Wang, Wenhu Chen, Chunyun Zhang, Weiran Xu, and William Yang Wang.  Generative adversarial zero-shot relational learning for knowledge graphs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 8673–8680, 2020.
  * [21] Baoxu Shi and Tim Weninger.  Open-world knowledge graph completion.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * [22] Xing Tang, Ling Chen, Jun Cui, and Baogang Wei.  Knowledge representation learning with entity descriptions, hierarchical types, and textual relations.  Information Processing & Management, 56(3):809–822, 2019.
  * [23] Yuxia Geng, Jiaoyan Chen, Zhuo Chen, Jeff Z Pan, Zhiquan Ye, Zonggang Yuan, Yantao Jia, and Huajun Chen.  Ontozsl: Ontology-enhanced zero-shot learning.  In Proceedings of the Web Conference 2021, pages 3325–3336, 2021.
  * [24] Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek.  Amie: association rule mining under incomplete evidence in ontological knowledge bases.  In Proceedings of the 22nd international conference on World Wide Web, pages 413–422, 2013.
  * [25] Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt.  Fine-grained evaluation of rule-and embedding-based systems for knowledge graph completion.  In International semantic web conference, pages 3–20. Springer, 2018.
  * [26] Fan Yang, Zhilin Yang, and William W Cohen.  Differentiable learning of logical rules for knowledge base reasoning.  Advances in neural information processing systems, 30, 2017.
  * [27] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang.  Drum: End-to-end differentiable rule mining on knowledge graphs.  arXiv preprint arXiv:1911.00055, 2019.
  * [28] Huachi Zhou, Shuang Zhou, Keyu Duan, Xiao Huang, Qiaoyu Tan, and Zailiang Yu.  Interest driven graph structure learning for session-based recommendation.  In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 284–296. Springer, 2023.
  * [29] Hao Chen, Zhong Huang, Yue Xu, Zengde Deng, Feiran Huang, Peng He, and Zhoujun Li.  Neighbor enhanced graph convolutional networks for node classification and recommendation.  Knowledge-Based Systems, 246:108594, 2022.
  * [30] Hao Chen, Yue Xu, Feiran Huang, Zengde Deng, Wenbing Huang, Senzhang Wang, Peng He, and Zhoujun Li.  Label-aware graph convolutional networks.  In Proceedings of the 29th ACM international conference on information & knowledge management, pages 1977–1980, 2020.
  * [31] Hao Chen, Wenbing Huang, Yue Xu, Fuchun Sun, and Zhoujun Li.  Graph unfolding networks.  In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1981–1984, 2020.
  * [32] 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.
  * [33] Komal Teru, Etienne Denis, and Will Hamilton.  Inductive relation prediction by subgraph reasoning.  In International Conference on Machine Learning, pages 9448–9457. PMLR, 2020.
  * [34] Changjian Wang, Xiaofei Zhou, Shirui Pan, Linhua Dong, Zeliang Song, and Ying Sha.  Exploring relational semantics for inductive knowledge graph completion.  2022\.
  * [35] Jiajun Chen, Huarui He, Feng Wu, and Jie Wang.  Topology-aware correlations between relations for inductive link prediction in knowledge graphs.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 6271–6278, 2021.
  * [36] 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.
  * [37] Yuxia Geng, Jiaoyan Chen, Wen Zhang, Jeff Z. Pan, Mingyang Chen, Huajun Chen, and Song Jiang.  Relational message passing for fully inductive knowledge graph completion, 2022.
  * [38] Jaejun Lee, Chanyoung Chung, and Joyce Jiyoung Whang.  Ingram: Inductive knowledge graph embedding via relation graphs.  arXiv preprint arXiv:2305.19987, 2023.
  * [39] Jiarui Jin, Yangkun Wang, Kounianhua Du, Weinan Zhang, Zheng Zhang, David Wipf, Yong Yu, and Quan Gan.  Inductive relation prediction using analogy subgraph embeddings.  In International Conference on Learning Representations.
  * [40] Yuanning Cui, Yuxin Wang, Zequn Sun, Wenqiang Liu, Yiqiao Jiang, Kexin Han, and Wei Hu.  Inductive knowledge graph reasoning for multi-batch emerging entities.  In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 335–344, 2022.
  * [41] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  Advances in Neural Information Processing Systems, 2018.
  * [42] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin.  Revisiting graph neural networks for link prediction.  arXiv preprint arXiv:2010.16103, 2020.
  * [43] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [44] Komal K. Teru, Etienne Denis, and William L. Hamilton.  Inductive relation prediction by subgraph reasoning.  arXiv: Learning, 2020.
  * [45] Chen Shengyuan, Yunfeng Cai, Huang Fang, Xiao Huang, and Mingming Sun.  Differentiable neuro-symbolic reasoning on large-scale knowledge graphs.  Advances in Neural Information Processing Systems, 36, 2024.
  * [46] 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.
  * [47] 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.  In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 1221–1233. IEEE, 2023.
  * [48] 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 Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 893–903, 2022.
  * [49] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [50] William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025–1035, 2017.
  * [51] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger.  Simplifying graph convolutional networks.  In International conference on machine learning, pages 6861–6871. PMLR, 2019.
  * [52] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [53] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  arXiv preprint arXiv:1808.06670, 2018.
  * [54] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka.  f-gan: Training generative neural samplers using variational divergence minimization.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 271–279, 2016.
  * [55] Qi Zhu, Yidan Xu, Haonan Wang, Chao Zhang, Jiawei Han, and Carl Yang.  Transfer learning of graph neural networks with ego-graph information maximization.  arXiv preprint arXiv:2009.05204, 2020.
  * [56] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun.  Gpt-gnn: Generative pre-training of graph neural networks.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1857–1867, 2020.
  * [57] Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang.  Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study.  arXiv preprint arXiv:2108.10521, 2021.
  * [58] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  Representation learning on graphs with jumping knowledge networks.  In International Conference on Machine Learning, pages 5453–5462. PMLR, 2018.
  * [59] Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu.  Quaternion knowledge graph embeddings.  In NeurIPS, 2019.
  * [60] Zhao Zhang, Fuzhen Zhuang, Hengshu Zhu, Zhiping Shi, Hui Xiong, and Qing He.  Relational graph neural network with hierarchical attention for knowledge graph completion.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 9612–9619, 2020.
  * [61] Hongyu Ren, Weihua Hu, and Jure Leskovec.  Query2box: Reasoning over knowledge graphs in vector space using box embeddings.  arXiv preprint arXiv:2002.05969, 2020.