# KGExplainer: Towards Exploring Connected Subgraph Explanations for Knowledge
Graph Completion

Tengfei Ma<EMAIL_ADDRESS>College of Computer Science and Electronic
Engineering, Hunan UniversityChina ,  Xiang Song  AWS AI Research and
EducationUSA<EMAIL_ADDRESS>,  Wen Tao  College of Computer Science and
Electronic Engineering, Hunan UniversityChina<EMAIL_ADDRESS>,  Mufei Li
Georgia Institute of TechnologyUSA<EMAIL_ADDRESS>,  Jiani Zhang  Amazon
Web ServicesUSA<EMAIL_ADDRESS>,  Xiaoqin Pan  College of Computer
Science and Electronic Engineering, Hunan UniversityChina<EMAIL_ADDRESS>,
Jianxin Lin  College of Computer Science and Electronic Engineering, Hunan
UniversityChina<EMAIL_ADDRESS>,  Bosheng Song  College of Computer
Science and Electronic Engineering, Hunan UniversityChina
<EMAIL_ADDRESS>and  Xiangxiang Zeng  College of Computer Science and
Electronic Engineering, Hunan UniversityChina<EMAIL_ADDRESS>
(2018)

###### Abstract.

Knowledge graph completion (KGC) aims to alleviate the inherent incompleteness
of knowledge graphs (KGs), which is a critical task for various applications,
such as recommendations on the web. Although knowledge graph embedding (KGE)
models have demonstrated superior predictive performance on KGC tasks, these
models infer missing links in a black-box manner that lacks transparency and
accountability, preventing researchers from developing accountable models.
Existing KGE-based explanation methods focus on exploring key paths or
isolated edges as explanations, which is information-less to reason target
prediction. Additionally, the missing ground truth leads to these explanation
methods being ineffective in quantitatively evaluating explored explanations.
To overcome these limitations, we propose KGExplainer, a model-agnostic method
that identifies connected subgraph explanations and distills an evaluator to
assess them quantitatively. KGExplainer employs a perturbation-based greedy
search algorithm to find key connected subgraphs as explanations within the
local structure of target predictions. To evaluate the quality of the explored
explanations, KGExplainer distills an evaluator from the target KGE model. By
forwarding the explanations to the evaluator, our method can examine the
fidelity of them. Extensive experiments on benchmark datasets demonstrate that
KGExplainer yields promising improvement and achieves an optimal ratio of
83.3% in human evaluation.

Model Transparency, Model Explanation, Knowledge Graph Embedding, Knowledge
Graph Completion

††copyright: none††journalyear: 2018††doi: XXXXXXX.XXXXXXX††conference: Make
sure to enter the correct conference title from your rights confirmation emai;
June 03–05, 2018; Woodstock, NY††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Figure 1. Here is an example of subgraph- and path-based explanations. When
considering the target prediction (dashed line)
$\left<Alibaba,\mathbf{isCompetitor},JD.com\right>$, the path-based
explanation
$\left<Alibaba,\mathbf{investIn},Retail,\mathbf{isInvestedBy},JD.com\right>$
cannot always conclude the fact
$\left<Alibaba,\mathbf{isCompetitor},JD.com\right>$ due to the location of
them is confusing. In contrast, the subgraph-based explanation introduces an
additional fact: $Alibaba$ and $JD.com$ are both located in $China$. The fact
allows for an accurate deduction of the target prediction.

Knowledge graph completion (KGC) aims to infer missing facts and tackles the
incompleteness of knowledge graphs (KGs) (Akrami et al., 2020), which has been
widely used to support various applications including recommendation (Wang et
al., 2019a; Yang et al., 2022; Wang et al., 2022), sponsored search (Lin et
al., 2022), and drug discovery (Ma et al., 2023; Bang et al., 2023; Pan et
al., 2022). Most KGC models utilize knowledge graph embedding (KGE) methods to
map KG elements into multi-dimensional vectors (Nguyen et al., 2023; Song et
al., 2023). These vectors are commonly used as features for downstream tasks
and input into scoring functions for predicting missing links. KGE methods
have been shown to achieve more powerful predictive performance compared to
traditional models and can be scaled to large graphs (Ali et al., 2021; Zheng
et al., 2020). However, current KGE methods make black-box predictions without
providing explanations , hindering their deployment in risk-sensitive
scenarios (Wang et al., 2022; Zhang et al., 2023).

To address the aforementioned limitation, traditional rule-based methods
leverage the known facts within the KG to extract possible logical rules,
usually represented as paths, to explain the predicted fact for knowledge
graph completion (Zhang et al., 2019; Sadeghian et al., 2019; Arakelyan et
al., 2021). However, the rule mining-based KGC models are limited in their
predictive performance. To achieve comparable performance to embedding-based
KGC models while simultaneously providing explanations, adversarial
modifications are adopted to find the key facts, which identify the facts to
include or exclude from the KG and monitor their prediction score change in
the perturbed KG (Pezeshkpour et al., 2018; Rossi et al., 2022; Betz et al.,
2022). However, these methods focus on providing a single fact or multiple
isolated facts (Zhao et al., 2023; Baltatzis and Costabello, 2023) (i.e.,
discrete subgraph) as explanations for a model prediction , which do not
represent coherent reasoning chains and are insufficient to completely explain
why the model makes such a prediction. Reinforcement learning is adopted to
address the previous issue by directly learning paths as prediction
explanations, which balances the model’s faithfulness and explainability (Xian
et al., 2019; Bhowmik and de Melo, 2020; Jiang et al., 2023). Although this
method can obtain valid explainable paths , they are not expressive enough to
provide explanations in the form of subgraphs, which are essential for
predictions on complex KGs. For example, as shown in Figure 1, Alibaba is
identified as a competitor of JD.com over a complex KG111Alibaba and JD.com
are online retail companies in China.. The path-based explanation
$\left<Alibaba,\mathbf{investIn},Retail,\mathbf{isInvestedBy},JD.com\right>$
cannot always conclude the fact
$\left<Alibaba,\mathbf{isCompetitor},JD.com\right>$ due to the location of
them is confusing. In contrast, the subgraph-based explanation of the target
fact is informative with two additional facts: $Alibaba$ and $JD.com$ both lie
in $China$. These facts can effectively conclude that $Alibaba$ is $JD.com$’s
competitor. Additionally, for the identified explanations, we cannot directly
verify their rationality due to the ground truth is unavailable. Previous
methods focused more on model faithfulness (Pezeshkpour et al., 2018; Xian et
al., 2019) or manual verification of small-scale facts case by case (Zhang et
al., 2021), ignoring the quantitative assessment of model explainability.

Based on the above observations, we propose KGExplainer, a post-hoc
explainability model performed on the trained KGEs, to search for connected
subgraph-level explanations and provide an effective strategy for evaluating
the explanations quantitatively. We first perform a model-agnostic greedy
search approach to identify important subgraphs and distill a subgraph
evaluator from target KGEs to measure the correlation between subgraphs and
predictions. Then we evaluate the fidelity (Wu et al., 2023) of the identified
subgraphs by measuring the performance correlation between the original KGC
model that has access to the whole KG and the evaluator only visible to the
explanation subgraphs.

In summary, the contributions of KGExplainer include:

  * •

We approach the explanations of KGE-based KGC models from a novel perspective
by emphasizing and evaluating connected subgraph explanations.

  * •

We present KGExplainer, a model-agnostic perturbation-based greedy search
algorithm that can extract explanations with critical connected subgraph
patterns for knowledge graph completion in a coherent way.

  * •

We propose an evaluation strategy to quantitatively evaluate the effectiveness
of subgraph-based explanations by distilling an evaluator to examine their
fidelity.

  * •

Extensive experiments and human evaluation on widely used datasets demonstrate
the effectiveness and efficiency of KGExplainer for exploring human-
understandable explanations.

##  2\. Related Works

###  2.1. Knowledge Graph Completion

Knowledge graph completion (KGC) aims to address the invariable incompleteness
of knowledge graphs (KGs) by identifying missing interactions between
entities. Previous rule-based methods (Sadeghian et al., 2019; Arakelyan et
al., 2021) mine logical rules iteratively based on pre-trained embeddings of
KGEs during the training process. These methods are limited to the predictive
performance and scalability of KGC tasks on KGs. Knowledge graph embedding
(KGE) models map KG elements to multi-dimensional vectors and define a scoring
function to infer new facts, which have shown superior performance over rule-
based methods for predicting missing links (Zhang et al., 2022; Wang et al.,
2023; Gregucci et al., 2023). Specifically, the translational models, TransE
(Bordes et al., 2013a) and its extensions (Wang et al., 2014; Lin et al.,
2015), represent relations and entities as embedding vectors and treat the
relation as the translation from head entities to tail entities. In another
aspect, the bilinear models, RESCAL (Nickel et al., 2011) and its variants
(Trouillon et al., 2016; Yang et al., 2015), represent relations with matrices
and combine the head and tail entities by sequentially multiplying head
embedding, relation matrix, and tail embedding. To effectively infer various
relation patterns or properties (e.g., symmetry and inversion) over complex
KGs, RotatE (Sun et al., 2019) represents each relation as a rotation
operation from the source entity to the target entity in the complex vector
space. Although these KGE models are successful in predicting unknown facts,
they are limited in lacking transparency and accountability, which block
researchers from developing trustworthy models. To address the above
limitations, we propose KGExplainer to explore subgraph-based explanations for
KGE-based KGC models.

###  2.2. Explainability in Knowledge Graph Completion

To increase the transparency of models in KGC tasks, researchers have
developed various explanation models (Wang et al., 2022; Huang et al., 2022;
Zhang et al., 2023; Yao et al., 2023). Most explanation models for KGC can be
categorized into rule-based, fact-based, and path-based methods. Learning
rules as the explanations from KGs has been studied extensively in inductive
logic programming (Galárraga et al., 2013; Qu et al., 2021). RuLES (Ho et al.,
2018) extended rule learning by exploiting probabilistic representations of
missing facts computed by a pre-trained KGE model. DRUM (Sadeghian et al.,
2019) proposed a scalable and differentiable approach to mine first-order
logical rules from KGs for unseen entities. The mining rules are human-
understandable and can be used to deduce predicted facts and provide logical
explanations (Zhang et al., 2019). While rule-based models are native
explainability, they often fall short in achieving excellent predictive
performance and scaling to complex KGs. To improve the explainability of high-
accuracy KGE methods, CRIAGE (Pezeshkpour et al., 2018), Kelpie (Rossi et al.,
2022), and KE-X (Zhao et al., 2023) search for the most important edges (i.e.,
isolated facts) to explain the target prediction by approximately evaluating
the impact of removing an existing fact from the KG on prediction score.
However, these methods only provide a single fact or multiple discrete facts
as explanations, thus lacking enough information to completely explain a model
prediction. To explore more effective explanations, PGPR (Xian et al., 2019)
and ELEP (Bhowmik and de Melo, 2020) have adopted a reinforcement learning
approach to predict tail entities and take the reasoning path between the head
and tail entities as the explanation. PaGE-Link (Zhang et al., 2023) proposed
a path-based graph neural network explanation for the KGC tasks, providing
human-understandable explanations in a learnable way. As shown in Figure 1,
although these methods can reason explanatory paths, they are invalid in
explaining predictions over complex KGs. Additionally, the explainable ground
truth is unavailable, leading to it being difficult for previous methods to
evaluate the explanations quantitatively. To address these limitations, we
propose KGExplainer to find subgraph-based explanations that most influence
the target prediction and distill an evaluator to assess the explored
explanations quantitatively.

##  3\. Preliminary

###  3.1. KGE-based Knowledge Graph Completion

We define a knowledge graph (KG) as a labeled directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{R},\mathcal{E})=\\{(h,t,t)|h,r\in\mathcal{V},r\in\mathcal{R},(h,t)\in\mathcal{E}\\}$
where each triple represents a relation $r$ between the head entity $h$ and
tail entity $t$. Most KGs are incomplete and many unknown interactions are
undiscovered. Knowledge graph completion (KGC) leverages existing facts in the
KG to infer missing ones, which alleviates the incompleteness of the KG.
Currently, the most popular KGC method adopts deep learning techniques to
learn the embeddings of KG elements (i.e., vectorized representations of
entities and relations). Intuitively, knowledge graph embeddings (KGEs)
contain the semantic information of the original KG and can be used to predict
new links. Generally, the KGE-based models define a score function $\phi$ to
estimate the plausibility of triples and optimize the vectorized embeddings by
maximizing the scores of existing facts. For the incomplete triple
$\left<h,r,?\right>$, the KGE models find the missing tail entity $t$ with
best scores as follows:

(1) $t=\operatorname*{argmax}_{v\in\mathcal{V}}\phi(h,r,v).$

The head entity prediction for the unknown links like $\left<?,r,t\right>$ can
be defined analogously. In the following sections, we mostly refer to tail
entity prediction for simplicity. All our methods can be applied to head
entity prediction.

###  3.2. Enclosing Subgraph of Target Prediction

Based on GraIL (Teru et al., 2020), when given a KG $\mathcal{G}$ and a link
$\left<h,r,t\right>$ for tail prediction, we extract an enclosing subgraph
surrounding the target link to represent the relevant patterns for model’s
decision. Initially, we obtain the $k$-hop neighboring entities
$\mathcal{N}_{k}(h)=\\{s|d(h,s)\leq k\\}$ and
$\mathcal{N}_{k}(t)=\\{s|d(t,s)\leq k\\}$ for both $h$ and $t$, where
$d(\cdot,\cdot)$ represents the shortest path distance between the entity pair
on $\mathcal{G}$. We then obtain the set of entities
$V=\\{s|s\in\mathcal{N}_{k}(h)\cap\mathcal{N}_{k}(t)\\}$ as vertices of the
enclosing subgraph. Finally, we extract the edges $E$ linked by the set of
entities $V$ from $\mathcal{G}$ as the $k$-hop enclosing subgraph $g=(V,E)$.

##  4\. The KGExplainer Framework

Figure 2. The KGExplainer framework comprises three modules: (1) Pre-training
KGE models on the target KG ; (2) Exploring subgraph-based explanations for
pre-trained KGE models by greedy search ; (3) Distilling a subgraph structure
evaluator from pre-trained KGE to assess the explored explanations
quantitatively.

###  4.1. Problem Formulation

Given a fact $\left<h,r,t\right>$, KGExplainer investigates the explanation
that intuitively consists of the most critical subgraph patterns featuring $h$
that allow KGE models to predict tail $t$. For instance, when explaining why
the top ranking tail for the missing fact
$\left<Donald\\_Trump,nationality,?\right>$ is $USA$, KGExplainer searches for
the smallest key subgraph between Donald_Trump and USA, allowing the model to
predict the same ranking of USA based on the key subgraph. Specifically,
KGExplainer aims to find a subgraph $g_{key}$ that is most influential to the
target prediction $\left<h,r,t\right>$, and removing the other irrelevant
facts have no effect on the model’s prediction. We can define this process as
follows:

(2) $g_{key}=\operatorname*{argmin}_{\tilde{g}\in
g_{sub}}\Delta(f(g),f^{\prime}(\tilde{g})),$

where $g$ is the original enclosing subgraph $g$ , $g_{sub}$ denotes the all
possible connected subgraphs from $h$ to $t$ within $g$, and $f(\cdot)$ and
$f^{\prime}(\cdot)$ represent the original and retrained KGC models.

###  4.2. Overview of KGExplainer

KGExplainer is a model-agnostic and post-hoc framework that can be designed
for explaining and evaluating KGE-based KGC models. Given a prediction from
the pre-trained KGE models, KGExplainer identifies the smallest subgraph to
preserve the prediction performance. As illustrated in Figure 2, KGExplainer
comprises three main components: KGE Pre-training, Explanation Exploration and
Subgraph Evaluator Distillation. Specifically, KGExplainer first pre-trained a
KGE (e.g., RotatE) as the embedding-based KGC model for the subsequent
exploration and evaluation as presented in Section 4.3. When given a pre-
trained KGE model, KGExplainer uses a greedy search algorithm based on the
enclosing subgraph of the target fact to find the key subgraph as an
explanation as shown in Section 4.4. Meanwhile, KGExplainer distills a
subgraph neural network to model the semantic and structural topology of
enclosing subgraphs surrounding the predicted links by target KGE as explained
in Section 4.5. The distilled subgraph representation model provides insights
into evaluating the relevance between a target fact and a subgraph. Therefore,
we use the subgraph neural network as an evaluator to assess whether the
identified key patterns can preserve the target prediction by forwarding it
into the distilled model.

###  4.3. Pre-training KGE

In this paper, we developed the KGExplainer as a post-hoc explanation method
for KGE-based KGC models by exploring complex subgraph patterns. To
effectively learn semantic knowledge within the complex KG, we adopt the
state-of-the-art RotatE (Sun et al., 2019) as the target KGE. Specifically,
given a triple $\left<h,r,t\right>$, we adopt a score function and expect that
the embedding of head entity $h$ is similar to the embedding of tail entity
$t$ by rotating it over the relation $r$. By maximizing the scores of positive
triples and minimizing the scores of negative ones, we can obtain the pre-
trained entity and relation embeddings. Theoretically, KGExplainer is model-
agnostic and can be applied to any KGE-based model with a score function. We
designed experiments to verify the effectiveness of KGExplainer on various KGE
models, the details can be found in Section 5.5.2.

Figure 3. The details of exploring explanations. KGExplainer searches top
$n=2$ key entities per hop from the source to target entities greedy within
the enclosing subgraph, and then extracts the key subgraph by the identified
entities.

###  4.4. Explanation Exploration

Input : Target prediction $\left<h,r,t\right>$; Enclosing subgraph $g$;
Prediction score $s$; Subgraph extracting function $F_{sub}$; Score function
$\phi$; Number of entities retrieved per hop $n$;

Output : A key subgraph $g_{key}$ that is most critical to the target
prediction $\left<h,r,t\right>$.

Initialize a set of visited entities $S_{visit}$ as $\\{h\\}$;

Initialize a set of key entities $S_{key}$ as $\\{h\\}$;

Initialize a queue of searching entities $S_{search}$ as $\\{h\\}$;

while  _$S_{search}$ is not empty_ do

Initialize $H$ as an empty max-Heap;

$e_{searching}\leftarrow S_{search}.pop()$;

if  _$t\in\mathcal{N}(e_{searching})$_ then

$S_{key}\leftarrow S_{key}\cup\\{t\\}$ ;

break;

for  _$v\in\mathcal{N}(e_{searching})$_ do

if  _$u\notin S_{visit}$_ then

$S_{visit}\leftarrow S_{visit}\cup\\{u\\}$ ;

Create $g^{\prime}$ by removing $u$ from $g$ and finetune the KG embeddings of
$g^{\prime}$;

Get new embeddings of $h$, $r$, $t$ as $\mathbf{h^{\prime}}$,
$\mathbf{r^{\prime}}$, $\mathbf{t^{\prime}}$;

$s^{\prime}\leftarrow\phi(\mathbf{h^{\prime}},\mathbf{r^{\prime}},\mathbf{t^{\prime}})$;

$\delta_{v}\leftarrow s-s^{\prime}$;

Put $v$ into $H$ with its corresponding value $\delta_{v}$;

for  _$i\leftarrow 1$ to $n$_ do

Pop $v$ with the maximum $\delta_{v}$ from $H$ and put it into $S_{key}$ and
$S_{search}$;

$g_{key}\leftarrow F_{sub}(g,S_{key})$;

return $g_{key}$;

Algorithm 1 Greedy search for subgraph explanation

####  4.4.1. Greedy Search for Key Subgraph.

As shown in Figure 3, given a predicted link $\left<h,r,t\right>$ for the
prediction of tail entity $t$, we developed a greedy search algorithm based on
a perturbation mechanism to search for crucial subgraph patterns as the
explanation. We first extract the enclosing subgraph $g$ around the target
link, which contains informative interactions for such prediction. To identify
the most important subgraph influencing the prediction within $g$, we search
all entities in $g$ and measure their importance to capture key ones.
Specifically, we remove each entity and its adjacent from $g$ and
retrain222Retraining KGE over the entire KG is way too costly and we discuss
an efficient strategy to tackle this issue in Section 4.4.2 the target KGE on
the perturbed subgraph $g^{\prime}$. Then we measure the score change of the
target link using the original and retrained embedding as the entity
importance. The more the score changes, the more critical an entity is. To
ensure that the key entities obtained from the $k$-hop enclosing subgraph $g$
lead to a single connected component, we search the key entities from the head
$h$ and tail $t$ hop by hop. We first remove each 1-hop neighbor entity of $h$
and measure their importance to identify the top important entities. After
getting the top-$n$ important entities $\mathrm{v}_{1}^{n}$ from 1-hop
neighbor entities, we then search the one-hop neighboring entities of
$\mathrm{v}_{1}^{n}$ analogously for important $2$-hop neighbors
$\mathrm{v}_{2}^{n}$. We repeat this one-hop search process until reaching the
tail entity $t$ of the target link. As a result, we capture a set of the
$k$-hop key neighboring entities
$\mathrm{v}^{n}=\\{\mathrm{v}_{1}^{n},\cdots,\mathrm{v}_{k}^{n}\\}$ and
construct a connected subgraph as the explanation for the target prediction.
Algorithm 1 formally describes the process.

####  4.4.2. Retraining Strategy for Importance Assessment.

To effectively obtain the score changes of target facts based on the KGE
models, we designed a retraining strategy to capture the new embedding on the
perturbed KG. Since each entity perturbation only makes minor changes over the
entire KG, retraining the embeddings over the revised KG is infeasible when
$\mathcal{G}$ has millions of entities and facts. To focus on the relevant
patterns and reduce the overhead of the retraining, we introduce a subgraph-
based retraining strategy. We extract the enclosing subgraph $g$ of the target
fact $\left<h,r,t\right>$ and expand $g$ by including the 1-hop neighbors
$\mathcal{N}_{extend}$ of the existing entities, which constructs a new
subgraph $g_{extend}$. Then we retrain the embeddings of the KG elements on
$g_{extend}$ to make the calculation of score changes effective. To keep the
overall entity and relation embeddings of $g$ within the same representation
space of $\mathcal{G}$, we alleviate the following constraints: (1) We
initialize the embeddings of the entities in $g_{extend}$ with the pre-trained
embeddings from $\mathcal{G}$; (2) We fix the relation embeddings in
$g_{extend}$ as the same as those in $\mathcal{G}$; (3) We fix the embeddings
of entities $v\in\mathcal{N}_{extend}$. By using the retraining strategy,
KGExplainer can effectively capture the target fact’s score change and
efficiently search for key subgraphs. More details can be found in Appendix A.

###  4.5. Subgraph Evaluator Distillation

####  4.5.1. Why Subgraph Evaluator?

Evaluating the quality of identified explanation subgraphs is essential.
However, the ground truth explanations are unavailable, making it difficult to
achieve that objective. Following (Chen et al., 2018), the explanatory
subgraphs can be viewed as the discriminative information coherent in the
model knowledge. Thus we propose a post-hoc evaluation strategy to assess the
performance of the original KGC model only visible to the explanation
subgraphs. That is, we feed the explanation subgraphs to the model and examine
how well they recover the target predictive rankings. However, pre-trained
KGEs implicitly have access to the entire graph and we cannot restrict the
prediction of a KGE-based KGC model to a subgraph. To address this limitation,
we design a subgraph evaluator by distilling a relational graph neural network
(GNN) from pre-trained KGEs for KGC. During training, the GNN is optimized to
predict the facts from their complete enclosing subgraphs. Once trained, it
can be used to evaluate the degree of performance preservation with subgraph
explanations. Given a pre-trained KGE-based KGC model $\phi(h,r,t)$, we aim at
training a subgraph evaluator to replicate the predictive performance of the
target KGE and evaluate the subgraph structure of explanation.

####  4.5.2. How to get Subgraph Evaluator?

Given a link $\left<h,r,t\right>$, we develop a score function $Z(h,r,t)$ with
a $L$-layer relational graph attention neural network (R-GAT) on its enclosing
subgraph $g$ to score it based on the local substructure representation. The
update function of the entities in the $l$-th layer is defined as:

(3) $\displaystyle\mathbf{x}_{i}^{l}$
$\displaystyle=\sum_{r\in\mathcal{R}}\sum_{j\in\mathcal{N}_{r}(i)}\alpha_{(i,r,j)}\mathbf{W}_{r}^{l}\Phi(\mathbf{e}_{r}^{l-1},\mathbf{x}_{j}^{l-1}),$
$\displaystyle\alpha_{(i,r,j)}$
$\displaystyle=\mathrm{sigmoid}\left(\mathbf{W}_{1}\left[\mathbf{x}_{i}^{l-1}\oplus\mathbf{x}_{j}^{l-1}\oplus\mathbf{e}_{r}^{l-1}\right]\right),$

where $\mathbf{e}_{r}^{l}$ and $\mathbf{x}_{i}^{l}$ represent the $l$-th layer
embeddings of relation $r$ and entity $i$. $\alpha_{(i,r,j)}$ and
$\mathcal{N}_{r}(i)$ denote the weight and neighbors of entity $i$ under the
relation $r$, respectively. $\oplus$ is the concatenation operation.
$\mathbf{W}_{r}^{l}$ represents the transformation matrix of relation $r$, and
$\Phi$ is the aggregation operation to fuse the hidden features of entities
and relations. Finally, we obtain the global representation $\mathbf{X}_{sub}$
of the subgraph $g$ as follows:

(4) $\mathbf{X}_{sub}=\frac{1}{|V|}\sum_{i\in V}f(\mathbf{x}_{i}^{L}),$

where $V$ is the entity set of the enclosing subgraph $g$. After obtaining the
global representation $\mathbf{X}_{sub}$, we define a linear layer to score
the target link as follows:

(5) $Z(h,r,t)=\mathbf{W}^{T}\mathbf{X}_{sub},$

where $\mathbf{W}^{T}$ is a transform matrix.

To optimize the subgraph evaluator, inspired by (Gou et al., 2021), we adopt
the insights of knowledge distillation and consider the predictions of the
pre-trained KGE-based KGC model as soft labels. Meanwhile, to enhance the
model’s ability to rank candidate entities, we introduce a regularization term
that encourages maximizing the margin between the scores for positive and
negative samples. The objective for the optimization of this evaluator is
defined as follows:

(6) $\min\sum_{(h,r,t)\in\mathcal{G}}\|\phi(h,r,t)-Z(h,r,t)\|^{2}+\lambda
L(h,r,t),$

where the first term is a score alignment objective. The second term is a
pair-wise loss , which is defined by negative sampling:

(7) $L(h,r,t)=-Z(h,r,t)+\frac{1}{N}\sum_{n=1}^{N}Z(h,r,v_{n}),$

where $N$ denotes the number of negative samples and $v_{n}$ is uniformly
drawn from $V$. By minimizing the above optimization objective, we can obtain
an effective subgraph scoring function with powerful predictive performance
and evaluation capabilities for subgraph-based explanations.

###  4.6. Computation Complexity of KGExplainer

The computation complexity of finding explanations using KGExplainer is
related to two parts: 1) the size of enclosing subgraph $g$ and 2) the number
of entities that require importance evaluation.

###### Proposition 1.

Given $\mathcal{G}=(\mathcal{V},\mathcal{R},\mathcal{E})$, a predicted fact
$\left<h,r,t\right>$, the maximum length of paths $L$, and the number of paths
$N$, the size of $g$ is $O(\frac{LN|\mathcal{V}|}{|\mathcal{E}|})$ and the
size of $\mathcal{N}_{extend}$ is $O(LN)$.

Given $h$ and $t$, the maximum number of edges within paths is $L*N$. The
probability of an entity $v\in\mathcal{V}$ in an edge $e\in\mathcal{E}$ is
$\frac{2|\mathcal{V}|}{|\mathcal{E}|}$. Thus, the size of $g$ is bounded by
$LN*\frac{2|\mathcal{V}|}{|\mathcal{E}|}$, i.e.,
$O(\frac{LN|\mathcal{V}|}{|\mathcal{E}|})$. The number of entities in
$\mathcal{N}_{extend}$ is
$\frac{2LN|\mathcal{V}|}{|\mathcal{E}|}*\frac{2|\mathcal{E}|}{|\mathcal{V}|}$,
i.e., $O(LN)$.

###### Proposition 2.

Given $\mathcal{G}=(\mathcal{V},\mathcal{R},\mathcal{E})$, a predicted fact
$\left<h,r,t\right>$, the maximum length of paths $L$ and the maximum number
of entities per hop in an explanation $K$. The maximum number of entities to
evaluate is $(1+(L-2)K)(\frac{2|\mathcal{E}|}{|\mathcal{V}|})$.

Following Algorithm 1, the average number of entities to evaluate is $d$ in
the first hop, $0$ in the last hop, and $K*d$ in the intermediate hops, where
$d=\frac{2|\mathcal{E}|}{|\mathcal{V}|}$ is the average degree of an entity.
Thus, the total number of entities to evaluate is
$(1+(L-2)K)(\frac{2|\mathcal{E}|}{|\mathcal{V}|})$.

Here, we conclude that the average computation complexity of finding the
explanation for a predicted fact $\left<h,r,t\right>$ is only related to the
maximum length of paths $L$, the maximum number of paths $N$, and the average
degree of an entity in KG, which is not related to the size of $\mathcal{G}$.
Thus, in theory, KGExplainer can easily scale to large KGs.

##  5\. Experiment

In this section, we evaluate the proposed KGExplainer333Sources are available
at xxx by considering the following key research questions.

  * •

Q1 Does KGExplainer have similar predictive performance with the target KGE
models?

  * •

Q2 Is KGExplainer more effective than other fact- and path-based methods for
exploring explanations?

  * •

Q3 Can KGExplainer work well with different sizable explainable subgraphs and
various KGE methods?

  * •

Q4 Does KGExplainer produce sensible explanations?

  * •

Q5 Is KGExplainer efficient in exploring explanations?

###  5.1. Datasets

Similar to (Sadeghian et al., 2019), we conduct experiments on three widely
used datasets444https://github.com/alisadeghian/DRUM/tree/master/datasets for
the KGC task. Specifically, WN-18 (Bordes et al., 2013b) is a database with
complex patterns featuring lexical relations between words extracted from
WordNet (Miller, 1995). The Family-rr (Sadeghian et al., 2019) is a dataset
that contains the bloodline relationships between individuals of various
families. FB15k-237 (Bordes et al., 2013b) is a subset of Freebase (Bollacker
et al., 2008), which is a large-scale knowledge graph containing general
facts. For every dataset, we split it into training and test subsets for the
following evaluations of faithfulness and explainability. The statistics of
all datasets are shown in Table 1. #train and #test are the number of triples
on the training and testing sets.

###  5.2. Evaluation Settings

Table 1. The statistics of datasets. Dataset | #entity | #relation | #train | #test
---|---|---|---|---
WN-18 | 40,943 | 18 | 35,354 | 2,250
Family-rr | 3,007 | 12 | 5,868 | 2,835
FB15k-237 | 14,541 | 237 | 68,028 | 9,209

####  5.2.1. Faithful Metrics.

The evaluation of KGC models is performed by running head and tail prediction
on each triple in the test set. For each prediction, the ground truth is
ranked against all the other entities $\mathcal{V}$. Without loss of
generality, for tail prediction, this corresponds to:

(8) $tailRank(h,r,t)=|\\{v\in\mathcal{V}|\phi(h,r,v)>=\phi(h,r,t)\\}|.$

Following (Kadlec et al., 2017), we adopt $Hits@N$ to quantify the predictive
performance of KGE and distilled models. $Hits@N$ is the fraction of ranks
$S_{rank}$ with value $\leq N$:

(9) $Hits@N=\frac{|\\{s_{i}\in S_{r}:s_{i}\leq N\\}|}{|S_{r}|},$

where $s_{i}$ is the ranking of $i$-th candidate entity and $S_{r}$ is a set
of rankings for all candidate entities. Following the method proposed by
Kadlec et al., we focus on the $Hits@1$ metric to better highlight model
differences.

####  5.2.2. Explanation Metrics.

As the ground truth explanations of KGC tasks are usually missing, it is not
easy to quantitatively evaluate the quality of explanations. We consider
explanations to be sufficient if they allow preserving the KGC performance
(Akrami et al., 2020; Wang et al., 2021; Wu et al., 2023). Thus we define the
$Recall@N$ and $F1@N$ as the metrics to evaluate the effectiveness of explored
explanations. Specifically, $Recall@N$ measures the fidelity of explanatory
subgraphs by feeding them into the distilled model and examining how well they
recover the target predictive rankings. Given the rankings of tested facts by
forwarding their explanations to the distilled evaluator, we calculate the
$Recall@N$ as follows:

(10) $Recall@N=\frac{|\\{s_{i}\in S_{r}:s_{i}\leq N\\}\cap\\{s_{j}\in
S_{r}^{exp}:s_{j}\leq N\\}|}{|\\{s_{i}\in S_{r}:s_{i}\leq N\\}|},$

where $S_{r}^{exp}$ is the ranking set of explanations and $S_{r}$ denotes the
original predictive rankings of them. We can assess the trustworthiness of
explanations by calculating the recovery rate of the rankings $S_{r}$.
Meanwhile, the subgraph-based explanations are critical in the precision of
rankings (i.e., $Hits@N$), to comprehensively evaluate the explainability of
KGExplainer, we define $F1@N$ to balance the recall and precision of the
explored explanations:

(11) $\displaystyle Hits@N=\frac{|\\{s_{j}\in S_{r}^{exp}:s_{j}\leq
N\\}|}{|S_{r}^{exp}|},$ $\displaystyle F1@N=\frac{2\cdot Recall@N\cdot
Hits@N}{Recall<EMAIL_ADDRESS>
Similar to the evaluation of faithfulness, we consider $Recall@1$ and $F1@1$
for the qualitative metrics to emphasize the performance discrepancy.

Table 2. The predictive performance of KGE and the distilled models on $Hits@1(\%)$ metric over the three datasets. Methods | WN-18 | Family-rr | FB15k-237
---|---|---|---
TransE | 29.50 (0.32) | 12.63 (0.09) | 41.86 (0.43)
KGExp-TransE | 27.40 (0.23) | 15.77 (0.11) | 40.99 (0.31)
DistMult | 9.450 (0.15) | 8.680 (0.27) | 10.26 (0.21)
KGExp-DistMult | 16.65 (0.16) | 9.881 (0.14) | 13.09 (0.32)
RotatE | 29.38 (0.19) | 39.08 (0.45) | 42.10 (0.51)
KGExp-RotatE | 29.47 (0.22) | 35.79 (0.06) | 39.28 (0.29)

###  5.3. Baselines

To verify the performance of KGExplainer in exploring explanations, we compare
it against various baselines as follows:

  * •

Fact-based Methods: CRIAGE (Pezeshkpour et al., 2018) identified the most
important fact to explain a prediction by approximating the impact of removing
an existing fact from the KG. Kelpie (Rossi et al., 2022) identified multiple
isolated facts as the reasoning evidence and can be applied to any embedding-
based KGC models.

  * •

Rule- or Path-based Methods: DRUM (Sadeghian et al., 2019) is a scalable and
differentiable model for mining logical rules as path-based explanations from
KGs while predicting unknown links. ELEP (Bhowmik and de Melo, 2020) utilized
a reinforcement learning approach to find reasoning paths between the head and
tail entities of the target prediction. PaGE-Link (Zhang et al., 2023) can
generate explanations as paths connecting the entity pair based on subgraphs
in a learnable way.

Furthermore, we design variants of KGExplainer to verify its effectiveness on
different embedding-based KGC models. For convenience, we denote KGExplainer
as KGExp in tables.

  * •

KGExp-Rand randomly selected some connective paths between head and tail
entities to construct an explainable subgraph, which allows an ablation study.

  * •

KGExp-TransE, KGExp-DistMult, and KGExp-RotatE are variants of KGExplainer
that consider TransE (Bordes et al., 2013b), DistMult (Yang et al., 2015), and
RotatE(Sun et al., 2019) as the base KGE, respectively.

More implementation details of baselines refer to Appendix C.1.

###  5.4. Performance and Comparison

In this section, we analyze the performance of KGExplainer from two aspects,
faithfulness and explainability. The average performance and standard
deviation over five runs are reported in Table 3 and Table 4. We show more
details in Appendix C.2.

####  5.4.1. Faithfulness Evaluation (Q1).

An important goal of explainability models is to accurately and
comprehensively represent the local decision-making structure of the target
model. Specifically, in the context of KGE models, KGExplainer should strive
to replicate their behavior as closely as possible (Zhang et al., 2021). Thus,
to answer Q1, we compare the predictive performance of KGExplainer and the
target KGE models. As shown in Table 2, we observe that KGExplainer achieves
nearly the same performance on the KGC task compared with the target KGE
models (e.g., the performance of KGExp-RotatE and RotatE on WN-18 dataset).
Furthermore, we observe that RotatE overall achieves the best performance for
KGC and similarly KGExp-RotatE shows superior predictive performance among the
distilled models, which brings greater credibility than others, supporting
that KGExplainer is faithful to target KGE and is reliable in replicating the
target KGE. Thus, we chose the RotatE as the target KGE model and distilled a
powerful evaluator based on the subgraph substructure around the target link
to assess the explainability.

####  5.4.2. Explainability Evaluation (Q2).

Table 3. The $F1@1(\%)$ performance of explanations over various datasets. The boldface denotes the highest score and the underline indicates the best baseline. Methods | WN-18 | Family-rr | FB15k-237
---|---|---|---
CRIAGE | 63.78 (0.13) | 20.75 (0.32) | 40.99 (0.21)
Kelpie | 66.36 (0.19) | 20.33 (0.23) | 36.64 (0.13)
DRUM | 71.41 (0.41) | 21.26 (0.09) | 65.53 (0.19)
ELEP |  75.87 (0.22) |  22.75 (0.17) |  70.11 (0.21)
PaGE-Link | 67.70 (0.31) | 21.89 (0.13) | 66.12 (0.14)
KGExp-Rand | 31.22 (0.53) | 19.16 (0.26) | 55.17 (0.23)
KGExp-TransE | 97.10 (0.17) | 30.47 (0.25) | 82.04 (0.33)
KGExp-DistMult | 96.87 (0.08) |  30.49 (0.24) | 84.29 (0.17)
KGExp-RotatE |  97.10 (0.11) | 29.52 (0.12) |  83.65 (0.14)

It is essential to assess objectively how good an explanation is for
KGExplainer. Unfortunately, similar to other explanation methods, evaluating
explanations is made difficult by the impossibility of collecting ground truth
explanations. To fairly evaluate explanations without ground truth and answer
Q2, we distill an evaluator and design two metrics $F1@1$ and $Recall@1$ to
quantify how trusty an explanation is. As shown in Table 3 and Table 4, we
reported the $F1@1$ and $Recall@1$ results compared with baselines on three
wide-used datasets, and more results can be found in Appendix C. Specifically,
KGExplainer improves the $F1@1$ and $Recall@1$ by at least $21.23\%$ and
$7.67\%$ respectively on the WN-18 dataset and achieves $7.74\%$ and $4.77\%$
absolute increase over the best baseline on the Family-rr dataset. Meanwhile,
the performance of KGExplainer on the FB15k-237 dataset has yielded $13.54\%$
and $4.19\%$ gains in $F1@1$ and $Recall@1$ compared with the baselines.

Furthermore, we have the following observations: (1) Compared with the fact-
based methods CRIAGE and Kelpie, the path-based explainability methods DRUM,
ELEP, and PaGE-link that utilize reasonable paths between source and target
entities achieve better performance, which indicates that the connecting paths
are important for the model explanation. (2) Compared with the path-based
explainability models ELEP and PaGE-Link, subgraph-based KGExplainer (e.g.,
KGExp-RotatE) performs better than them on all datasets, demonstrating that
the subgraph-based explanations are more effective than paths and multiple
disconnected facts. (3) For an ablation study, KGExp-Rand, which adopts
randomly sampled subgraphs connected to the source and target entities as the
explanations, yields significantly inferior performance compared with other
KGExplainer variants. This demonstrates that KGExplainer indeed identifies
semantically meaningful subgraph explanations for model predictions, which are
superior to randomly sampled subgraphs by a large margin. This may be because
the KGExplainer based on target KGEs can explore reasonable subgraph patterns
that are crucial to predicting the corresponding facts, and the randomly
sampled subgraph may contain irrelevant information with missing key patterns
to the predicted facts. The overall performance compared with the baselines
demonstrates that KGExplainer is effective in exploring informative
explanations and evaluating them.

Table 4. The $Recall@1(\%)$ performance of explanations over various datasets. We mark the best score with bold font and mark the best baseline with underline. Methods | WN-18 | Family-rr | FB15k-237
---|---|---|---
CRIAGE | 86.69 (0.10) | 28.57 (0.33) | 68.23 (0.43)
Kelpie | 88.31 (0.28) | 27.62 (0.39) | 60.01 (0.27)
DRUM |  91.12 (0.15) | 16.20 (0.21) |  87.88 (0.22)
ELEP | 89.97 (0.11) |  29.84 (0.18) | 85.58 (0.29)
PaGE-Link | 85.36 (0.25) | 27.14 (0.31) | 85.13 (0.09)
KGExp-Rand | 86.09 (0.68) | 26.98 (0.49) | 50.37 (0.19)
KGExp-TransE |  98.79 (0.22) |  34.61 (0.43) |  92.07 (0.33)
KGExp-DistMult | 98.14 (0.19) | 34.60 (0.13) | 91.67 (0.11)
KGExp-RotatE | 98.75 (0.15) | 33.02 (0.11) | 91.45 (0.09)
Figure 4. The explainable performance of KGExplainer with different hyper-
parameters over Family-rr dataset.

###  5.5. Hyper-parameter Sensitivity Analysis (Q3)

In this section, to answer Q3, we conduct hyper-parameter sensitivity analysis
on the Family-rr dataset to study the impact of different sizable explored
subgraphs and various KGE-based KGC models.

####  5.5.1. Size of subgraph-based explanation

To investigate the influence of different sizable explanation subgraphs, we
conduct experiments based on KGExp-RotatE by varying $n$ to 1, 2, and 3. The
KGExplainer explored subgraphs with $n=1$ is equal to exploring the
explainable paths. As illustrated in the left of Figure 4, we observe the best
performance on $F1@1$ and $Recall@1$ metrics when utilizing the explainable
subgraphs with $n=2$. Meanwhile, the performance across different sizes
collapsed into a hunchback shape. The reason could be that the explored
subgraphs with $n=1$ are inefficient in recovering the original predictions
and the subgraph patterns with $n=3$ may contain many irrelevant facts, which
introduce much noise and reduce the performance of KGExplainer.

####  5.5.2. KGExplainer over various KGE-based KGC models

We investigate the impact of different target KGEs, including TransE,
DistMult, and RotatE. As shown on the right side of Figure 4, the results
indicate that KGExplainer achieves similar levels of explanation performance
across $F1@1$ and $Recall@1$ for different variants. This is because
KGExplainer selects key entities by perturbing neighboring entities and
evaluating their influence on the prediction score, which is independent of
the KGE-based KGC models. Our findings show that KGExplainer is effective in
searching explanations for embedding-based models and is model-agnostic, as
demonstrated by its performance across various KGEs.

Figure 5. The explanations explored by Kelpie, DRUM, PaGE-Link, and
KGExplainer on the fact $\left<id:2,isFather,id:5\right>$.

###  5.6. Human Evaluation (Q4)

Following (Zhang et al., 2023), we conduct a human evaluation by randomly
picking 20 predicted links from the test set of Family-rr and generating
explanations for each link using a fact-based model (i.e., Kelpie), two path-
based methods (i.e., DRUM and PaGE-Link), and KGExplainer. We designed a
survey with single-choice questions. In each question, we represent the
predicted link and those four explanations with both the graph structure and
the node/edge type information, similarly as in Figure 5 but excluding method
names. We sent the survey to people across graduate students, PhD students,
and professors, including people with and without background knowledge about
KGs. We ask respondents to “please select the best explanation of Why the
model predicts this relationship between source and target nodes?”. At least
three answers from different people are collected for each question. In total
78 evaluations were collected and 83.3% (65/78) of them selected explanations
by KGExplainer as the best. The survey demonstrates that KGExplainer is more
effective in searching the human-understandable explanations than fact- and
path-based methods.

###  5.7. Efficiency Analysis (Q5)

####  5.7.1. Inference Time

We trained KGExplainer and baselines using a server with 12 virtual Intel(R)
Xeon(R) Platinum 8255C CPU and one RTX 2080 Ti GPU. To verify the
effectiveness of KGExplainer in searching for explanations, we designed an
experiment to evaluate KGExplainer. As illustrated in Table 5, we show the
average cost time of exploring explanations over the test sets of all datasets
from different methods. We find that KGExplainer has a similar cost to CRIAGE
and is more efficient than PaGE-Link and Kelpie, which indicates that
KGExplainer can be effectively extended to complex KGs in searching subgraph-
based explanations. This is because KGExplainer searches explanations within
the enclosing subgraph and the number of calculations for each hop is only
related to the average degree, which reduces the computational complexity of
the exploring process. Overall, KGExplainer has superiority in exploring
subgraph-based explanations with complex patterns, which can scale to large
knowledge graphs.

Table 5. The average cost time (s) of fact-based, path-based methods, and KGExplainer (i.e., KGExp-RotatE) to explore explanations on the test set of different datasets. | CRIAGE | Kelpie | PaGE-Link | Ours
---|---|---|---|---
Family-rr | 1.652 | 4.849 | 1.747 | 1.321
WN-18 | 1.554 | 4.698 | 1.744 | 1.587
FB15k-237 | 15.13 | 28.51 | 16.93 | 16.81
Table 6. The size and $F1@1$ performance of explanation subgraphs of different explainers on Family-rr. KGExplainer is equivalent to the path-based methods when $n=1$. Methods | Avg #edges | F1@1
---|---|---
Keplie (Fact-based) | 8.297 | 20.33
PaGE-Link (Path-based) | 3.085 | 21.89
KGExp-TransE ($n=1$) | 3.182 | 28.77
KGExp-TransE ($n=2$) | 9.782 | 30.47
KGExp-TransE ($n=3$) | 15.132 | 30.43

####  5.7.2. Sparsity of Explanations

We discuss the sparsity of the explanations from various explainers. For
KGExplainer and baseline methods, we adopt the average number of edges (i.e.,
Avg. #edges) as the size of explanations. For KGExplainer, the users can
adjust the sparsity of explanation subgraphs by selecting different top-$n$
nodes per hop (Refer to Section 4.4.1). As shown in Table 6, we observe that
the path-based method (e.g., PaGE-Link) exploring a coherent reasoning chain
with fewer facts is more efficient than the fact-based method (e.g., Keplie).
Additionally, KGExplainer exploring connected subgraphs can achieve superior
performance on comparable sparse explanations than the path-based method. The
phenomenon in Table 6 shows that KGExplainer can yield better explainability
on explanations with low information density than baselines. More details can
be found in Appendix C.3.

##  6\. Conclusion and future work

In this work, we proposed a KGExplainer to identify connected subgraphs as
explanations over complex KGs and design two quantitative metrics for
evaluating them. Specifically, KGExplainer used a greedy search algorithm and
distilled an evaluator to find and assess key subgraphs. Extensive experiments
demonstrate that KGExplainer is effective in providing meaningful
explanations. In the future, we will generalize our framework into multiple
domains, including but not limited to vision- and text-based applications.

## References

  * (1)
  * Akrami et al. (2020) Farahnaz Akrami, Mohammed Samiul Saeef, Qingheng Zhang, Wei Hu, and Chengkai Li. 2020.  Realistic re-evaluation of knowledge graph completion methods: An experimental study. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_. 1995–2010.
  * Ali et al. (2021) Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Sharifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. 2021.  Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under a unified framework.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ 44, 12 (2021), 8825–8845.
  * Arakelyan et al. (2021) Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. 2021.  Complex Query Answering with Neural Link Predictors. In _International Conference on Learning Representations_. 1–14.
  * Baltatzis and Costabello (2023) Vasileios Baltatzis and Luca Costabello. 2023.  KGEx: Explaining Knowledge Graph Embeddings via Subgraph Sampling and Knowledge Distillation.  _arXiv preprint arXiv:2310.01065_ (2023).
  * Bang et al. (2023) Dongmin Bang, Sangsoo Lim, Sangseon Lee, and Sun Kim. 2023.  Biomedical knowledge graph learning for drug repurposing by extending guilt-by-association to multiple layers.  _Nature Communications_ 14, 1 (2023), 3570.
  * Betz et al. (2022) Patrick Betz, Christian Meilicke, and Heiner Stuckenschmidt. 2022.  Adversarial explanations for knowledge graph embeddings. In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_. 2820–2826.
  * Bhowmik and de Melo (2020) Rajarshi Bhowmik and Gerard de Melo. 2020.  Explainable link prediction for emerging entities in knowledge graphs. In _The Semantic Web–ISWC 2020: 19th International Semantic Web Conference_. 39–55.
  * Bollacker et al. (2008) Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008.  Freebase: A Collaboratively Created Graph Database for Structuring Human Knowledge. In _Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data_. 1247–1250.
  * Bordes et al. (2013a) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013a.  Translating embeddings for modeling multi-relational data.  _Advances in Neural Information Processing Systems_ 26 (2013), 1–9.
  * Bordes et al. (2013b) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston, and Oksana Yakhnenko. 2013b.  Translating Embeddings for Modeling Multi-Relational Data. In _Proceedings of the 26th International Conference on Neural Information Processing Systems_. 2787–2795.
  * Chen et al. (2018) Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. 2018.  Learning to explain: An information-theoretic perspective on model interpretation. In _International conference on machine learning_. 883–892.
  * Deng and Zhang (2020) Xiang Deng and Zhongfei Zhang. 2020.  Can students outperform teachers in knowledge distillation based model compression?  (2020).
  * Galárraga et al. (2013) Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek. 2013.  AMIE: association rule mining under incomplete evidence in ontological knowledge bases. In _Proceedings of the 22nd international conference on World Wide Web_. 413–422.
  * Gou et al. (2021) Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. 2021.  Knowledge distillation: A survey.  _International Journal of Computer Vision_ 129 (2021), 1789–1819.
  * Gregucci et al. (2023) Cosimo Gregucci, Mojtaba Nayyeri, Daniel Hernández, and Steffen Staab. 2023.  Link prediction with attention applied on multiple knowledge graph embedding models. In _Proceedings of the ACM Web Conference 2023_. 2600–2610.
  * Han et al. (2020) Zhen Han, Peng Chen, Yunpu Ma, and Volker Tresp. 2020.  Explainable subgraph reasoning for forecasting on temporal knowledge graphs. In _International Conference on Learning Representations_.
  * Ho et al. (2018) Vinh Thinh Ho, Daria Stepanova, Mohamed H Gad-Elrab, Evgeny Kharlamov, and Gerhard Weikum. 2018.  Rule learning from knowledge graphs guided by embedding models. In _The Semantic Web–ISWC 2018: 17th International Semantic Web Conference_. 72–90.
  * Huang et al. (2022) Jiacheng Huang, Yao Zhao, Wei Hu, Zhen Ning, Qijin Chen, Xiaoxia Qiu, Chengfu Huo, and Weijun Ren. 2022.  Trustworthy knowledge graph completion based on multi-sourced noisy data. In _Proceedings of the ACM Web Conference 2022_. 956–965.
  * Jiang et al. (2023) Hao Jiang, Chuanzhen Li, Juanjuan Cai, and Jingling Wang. 2023.  RCENR: A Reinforced and Contrastive Heterogeneous Network Reasoning Model for Explainable News Recommendation. In _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 1710–1720.
  * Jiao et al. (2019) Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2019.  Tinybert: Distilling bert for natural language understanding.  _International Conference on Machine Learning and Natural Language Processing_ (2019).
  * Joshi and Urbani (2020) Unmesh Joshi and Jacopo Urbani. 2020.  Searching for embeddings in a haystack: link prediction on knowledge graphs with subgraph pruning. In _Proceedings of The Web Conference 2020_. 2817–2823.
  * Kadlec et al. (2017) Rudolf Kadlec, Ondrej Bajgar, and Jan Kleindienst. 2017.  Knowledge Base Completion: Baselines Strike Back. In _Proceedings of the 2nd Workshop on Representation Learning for NLP_. 69–74.
  * Lin et al. (2018) Peng Lin, Qi Song, and Yinghui Wu. 2018.  Fact checking in knowledge graphs with ontological subgraph patterns.  _Data Science and Engineering_ 3, 4 (2018), 341–358.
  * Lin et al. (2022) Su-Chin Lin, Kai-Hsiang Chou, Yen Chen, Hsu-Chun Hsiao, Darion Cassel, Lujo Bauer, and Limin Jia. 2022.  Investigating Advertisers’ Domain-changing Behaviors and Their Impacts on Ad-blocker Filter Lists. In _Proceedings of the ACM Web Conference 2022_. 576–587.
  * Lin et al. (2015) Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. 2015.  Learning entity and relation embeddings for knowledge graph completion. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 29. 1–7.
  * Ma et al. (2023) Tengfei Ma, Xuan Lin, Bosheng Song, Philip S. Yu, and Xiangxiang Zeng. 2023.  KG-MTL: Knowledge Graph Enhanced Multi-Task Learning for Molecular Interaction.  _IEEE Transactions on Knowledge and Data Engineering_ 35, 7 (2023), 7068–7081.
  * Miller (1995) George A. Miller. 1995.  WordNet: A Lexical Database for English.  _Commun. ACM_ 38, 11 (nov 1995), 39–41.
  * Nguyen et al. (2023) Trung-Kien Nguyen, Zemin Liu, and Yuan Fang. 2023.  Link Prediction on Latent Heterogeneous Graphs. In _Proceedings of the ACM Web Conference 2023_. 263–273.
  * Nickel et al. (2011) Maximilian Nickel, Volker Tresp, Hans-Peter Kriegel, et al. 2011\.  A three-way model for collective learning on multi-relational data.. In _International Conference on Machine Learning_ , Vol. 11. 3104482–3104584.
  * Pan et al. (2022) Xiaoqin Pan, Xuan Lin, Dongsheng Cao, Xiangxiang Zeng, Philip S Yu, Lifang He, Ruth Nussinov, and Feixiong Cheng. 2022.  Deep learning for drug repurposing: Methods, databases, and applications.  _Wiley Interdisciplinary Reviews: Computational Molecular Science_ 12, 4 (2022), e1597.
  * Paszke et al. (2017) Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017.  Automatic differentiation in pytorch.  (2017).
  * Pezeshkpour et al. (2018) Pouya Pezeshkpour, Yifan Tian, and Sameer Singh. 2018.  Investigating Robustness and Interpretability of Link Prediction via Adversarial Modifications. In _North American Chapter of the Association for Computational Linguistics_. 1–12.
  * Qu et al. (2021) Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. 2021.  Rnnlogic: Learning logic rules for reasoning on knowledge graphs.  _International Conference on Learning Representations_ (2021), 1–20.
  * Rossi et al. (2022) Andrea Rossi, Donatella Firmani, Paolo Merialdo, and Tommaso Teofili. 2022.  Explaining link prediction systems based on knowledge graph embeddings. In _Proceedings of the 2022 International Conference on Management of Data_. 2062–2075.
  * Sadeghian et al. (2019) Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. 2019.  Drum: End-to-end differentiable rule mining on knowledge graphs.  _Advances in Neural Information Processing Systems_ 32 (2019), 1–13.
  * Song et al. (2023) Xiran Song, Jianxun Lian, Hong Huang, Zihan Luo, Wei Zhou, Xue Lin, Mingqi Wu, Chaozhuo Li, Xing Xie, and Hai Jin. 2023.  xGCN: An Extreme Graph Convolutional Network for Large-scale Social Link Prediction. In _Proceedings of the ACM Web Conference 2023_. 349–359.
  * Sun et al. (2019) Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019.  Rotate: Knowledge graph embedding by relational rotation in complex space. In _ICLR_. 1–18.
  * Teru et al. (2020) Komal Teru, Etienne Denis, and Will Hamilton. 2020.  Inductive relation prediction by subgraph reasoning. In _International Conference on Learning Representations_. 9448–9457.
  * Trouillon et al. (2016) Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016.  Complex embeddings for simple link prediction. In _International Conference on Machine Learning_. 2071–2080.
  * Wang et al. (2023) Chenxu Wang, Xin Wang, Zhao Li, Zirui Chen, and Jianxin Li. 2023.  HyConvE: A Novel Embedding Model for Knowledge Hypergraph Link Prediction with Convolutional Neural Networks. In _Proceedings of the ACM Web Conference 2023_. 188–198.
  * Wang et al. (2019a) Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. 2019a.  Knowledge graph convolutional networks for recommender systems. In _The World Wide Web Conference_. 3307–3313.
  * Wang et al. (2019b) Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. 2019b.  Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks.  _arXiv preprint arXiv:1909.01315_ (2019).
  * Wang et al. (2022) Peng Wang, Renqin Cai, and Hongning Wang. 2022.  Graph-based extractive explainer for recommendations. In _Proceedings of the ACM Web Conference 2022_. 2163–2171.
  * Wang et al. (2021) Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. 2021.  Towards multi-grained explainability for graph neural networks.  _Advances in Neural Information Processing Systems_ 34 (2021), 18446–18458.
  * Wang et al. (2014) Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. 2014.  Knowledge graph embedding by translating on hyperplanes. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 28. 1112–1119.
  * Wu et al. (2023) Fang Wu, Siyuan Li, Lirong Wu, Dragomir Radev, Yinghui Jiang, Xurui Jin, Zhangming Niu, and Stan Z Li. 2023.  Explaining Graph Neural Networks via Non-parametric Subgraph Matching.  _International Conference on Machine Learning_ (2023), 1–13.
  * Xian et al. (2019) Yikun Xian, Zuohui Fu, Shan Muthukrishnan, Gerard De Melo, and Yongfeng Zhang. 2019.  Reinforcement knowledge graph reasoning for explainable recommendation. In _Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 285–294.
  * Yang et al. (2015) Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. 2015.  Embedding entities and relations for learning and inference in knowledge bases.  _International Conference on Learning Representations_ (2015), 1–12.
  * Yang et al. (2022) Yuhao Yang, Chao Huang, Lianghao Xia, and Chenliang Li. 2022.  Knowledge graph contrastive learning for recommendation. In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_. 1434–1443.
  * Yao et al. (2023) Liuyi Yao, Yaliang Li, Bolin Ding, Jingren Zhou, Jinduo Liu, Mengdi Huai, and Jing Gao. 2023.  Path-specific Causal Fair Prediction via Auxiliary Graph Structure Learning. In _Proceedings of the ACM Web Conference 2023_. 3680–3688.
  * Zhang et al. (2023) Shichang Zhang, Jiani Zhang, Xiang Song, Soji Adeshina, Da Zheng, Christos Faloutsos, and Yizhou Sun. 2023.  PaGE-Link: Path-based graph neural network explanation for heterogeneous link prediction. In _Proceedings of the ACM Web Conference 2023_. 3784–3793.
  * Zhang et al. (2021) Wen Zhang, Mingyang Chen, Zezhong Xu, Yushan Zhu, and Huajun Chen. 2021.  Explaining Knowledge Graph Embedding via Latent Rule Learning.  _OpenReview.Net_ 26 (2021), 1–14.
  * Zhang et al. (2019) Wen Zhang, Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhu, Wei Zhang, Abraham Bernstein, and Huajun Chen. 2019.  Iteratively learning embeddings and rules for knowledge graph reasoning. In _The World Wide Web Conference_. 2366–2377.
  * Zhang et al. (2022) Zhanqiu Zhang, Jie Wang, Jieping Ye, and Feng Wu. 2022.  Rethinking graph convolutional networks in knowledge graph completion. In _Proceedings of the ACM Web Conference 2022_. 798–807.
  * Zhao et al. (2023) Dong Zhao, Guojia Wan, Yibing Zhan, Zengmao Wang, Liang Ding, Zhigao Zheng, and Bo Du. 2023.  KE-X: Towards subgraph explanations of knowledge graph embedding based on knowledge information gain.  _Knowledge-Based Systems_ 278 (2023), 110772.
  * Zheng et al. (2020) Da Zheng, Xiang Song, Chao Ma, Zeyuan Tan, Zihao Ye, Jin Dong, Hao Xiong, Zheng Zhang, and George Karypis. 2020.  Dgl-ke: Training knowledge graph embeddings at scale. In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_. 739–748.

##  Appendix A Retraining Strategy

Retraing the embeddings over the entire KG $\mathcal{G}$ is infeasible due to
removing one entity and its facts have little impact on the embedding of KG
elements. To reduce the overhead of retraining, we developed a subgraph-based
retraining strategy as shown in Figure 6. We extract a 2-hop enclosing
subgraph $g$ around the target fact $\left<h,r,t\right>$. We argue that the
subgraph $g$ contains the key information that leads to the target prediction.
Thus the retraining process is only visible to the subgraph. Figure 6 shows an
example of how $g$ is extracted. Meanwhile, to ensure that the retrained
entity representation space is consistent with the original knowledge graph,
we expand $g$ by including the 1-hop neighbors $\mathcal{N}_{extend}$ of the
existing entities and fixed their embeddings. In Figure 6, we show the
learnable and fixed entities in the fine-tuning process. Specifically, we
adopt the following constraints: (a) we use the embeddings of the entities in
$\mathcal{G}$ to initialize the embeddings of $g$; (b) we fixed the relation
embeddings in $g$ as the same as those in $\mathcal{G}$; and (c) we fixed the
embedding of $v\in\mathcal{N}_{extend}$.

Figure 6. An example of creating a subgraph from $\mathcal{G}$. On the left,
two entities (the orange vertices) were predicted to be connected. A subgraph
was created on the right. We first initialized $g$ with all the entities (the
orange and green vertices) within $\mathcal{G}$. Then it was expanded by
including the 1-hop neighbors $\mathcal{N}_{extend}$ of existing entities (the
gray vertices). Figure 7. The $F1@1$ performance of KGExplainer on Family-rr
and WN-18 over various sizable enclosing subgraphs.

##  Appendix B Performance on Various Sizable Enclosing Subgraphs

Similar to the experiments in Section 5.5 (i.e., Hyper-parameter Sensitivity
Analysis), we conduct another experiment to study the model’s explainability
on various sizable enclosing subgraphs. We select top-$n=2$ entities per hop
and vary the size of $k$-hop enclosing subgraph to $k=1,2,3$. The $F1@1$
performance of KGExplainer over various sizable subgraphs is depicted in
Figure 7. Theoretically, the larger the subgraph to be searched, the more
sufficient key information it contains, so that more effective explanatory
subgraphs can be retrieved. We can observe that KGExp-RotatE performs better
as the size of subgraphs increases on both Family-rr and WN-18 datasets, which
indicates that KGExplainer based on RotatE has generalization and stability.
However, KGExplainer over TransE and DistMult only fits this phenomenon on one
of the datasets, showing they are limited in generalizing to other data
distributions. Thus to achieve a fair comparison, we consider the KGExp-RotatE
as the subgraph evaluator and assess other baseline methods.

##  Appendix C Extend Experiment

###  C.1. Experiment Settings

Table 7. Hyperparameters of KGExplainer in explanation phase. Hyper parameter | WN18 | Family-rr | FB15k-237
---|---|---|---
#entity per hop $n$ | 2 | 2 | 2
enclosing subgraph size $k$ | 2 | 2 | 1
target KGE | RotatE | TransE | RotatE
Table 8. The $F1@N$(%) performance of explanations over various datasets. The boldface denotes the highest score. Methods | Family-rr | WN-18 | FB15k-237
---|---|---|---
F1@1 | F1@3 | F1@10 | F1@1 | F1@3 | F1@10 | F1@1 | F1@3 | F1@10
CRIAGE | 20.75 | 27.22 | 36.44 | 63.78 | 72.91 | 77.78 | 40.99 | 48.81 | 53.26
Keplie | 20.33 | 27.18 | 36.25 | 66.36 | 73.58 | 79.39 | 36.64 | 40.77 | 48.01
DRUM | 21.26 | 25.23 | 30.73 | 71.41 | 75.58 | 77.80 | 65.53 | 67.34 | 71.03
ELPE | 22.75 | 29.71 | 40.40 | 75.87 | 78.35 | 83.21 | 70.11 | 29.71 | 40.40
PaGE-Link | 21.89 | 28.42 | 38.49 | 67.70 | 70.99 | 75.21 | 66.12 | 70.77 | 76.51
KGExp-rand | 19.16 | 27.55 | 41.48 | 31.22 | 37.43 | 40.46 | 55.17 | 61.03 | 66.58
KGExp-TransE | 30.47 | 45.89 | 62.96 | 97.10 | 98.57 | 99.58 | 82.04 | 85.41 | 89.97
KGExp-DistMult | 30.49 | 44.08 | 57.47 | 96.87 | 97.89 | 99.41 | 84.29 | 86.74 | 90.17
KGExp-RotatE | 29.52 | 39.56 | 57.25 | 97.10 | 98.58 | 99.57 | 83.65 | 87.41 | 92.97
Table 9. The $Recall@N$(%) performance of explanations over various datasets. The boldface denotes the highest score. Methods | Family-rr | WN-18 | FB15k-237
---|---|---|---
Recall@1 | Recall@3 | Recall@10 | Recall@1 | Recall@3 | Recall@10 | Recall@1 | Recall@3 | Recall@10
CRIAGE | 28.57 | 32.02 | 36.95 | 86.69 | 95.45 | 99.34 | 68.23 | 76.87 | 82.11
Keplie | 27.62 | 31.87 | 36.55 | 88.31 | 93.69 | 99.51 | 60.01 | 66.91 | 75.52
DRUM | 16.20 | 22.09 | 30.92 | 91.12 | 93.69 | 94.93 | 87.88 | 89.01 | 91.12
ELPE | 29.84 | 35.17 | 41.34 | 89.97 | 93.11 | 95.23 | 85.58 | 89.76 | 93.21
PaGE-Link | 27.14 | 31.77 | 38.13 | 85.36 | 88.32 | 92.20 | 85.13 | 87.32 | 89.04
KGExp-rand | 26.98 | 33.44 | 43.97 | 86.09 | 92.47 | 94.61 | 50.37 | 57.12 | 64.31
KGExp-TransE | 34.61 | 46.85 | 61.61 | 98.79 | 99.47 | 99.84 | 92.07 | 93.41 | 94.57
KGExp-DistMult | 34.60 | 43.05 | 56.26 | 98.14 | 99.31 | 99.71 | 91.67 | 92.01 | 93.89
KGExp-RotatE | 33.02 | 41.48 | 56.26 | 98.75 | 99.47 | 99.84 | 91.45 | 93.01 | 94.69
Table 10. Hyperparameters of KGExplainer in distillation phase. Hyper parameter | WN18 | Family-rr | FB15k-237
---|---|---|---
embedding dim | 64 | 64 | 64
learning rate | 0.001 | 0.0015 | 0.001
weight of pair-wis loss | 0.5 | 0.5 | 0.5
epochs | 20 | 20 | 20
R-GAT layers | 3 | 2 | 3
optimizer | Adam | Adam | Adam
batch size | 2048 | 1024 | 4096

####  C.1.1. Settings of KGExplainer

The experiments have two phases: (1) Generating subgraph-based explanations;
and (2) Distilling the subgraph evaluator for inference. The details of hyper-
parameter settings are reported in Table 7 and Table 10.

In the explanation phase, we mainly focus on the size of enclosing subgraphs,
the complexity of explanation subgraphs, and the target KGE models. For
different datasets, we set various parameters and published them in Table 7.
In the distilling phase, we are mainly concerned with the efficiency of
training or inference and the prediction performance of the distilled subgraph
evaluator on the KGC task. Specifically, we try different parameters over
various datasets on model architecture and optimization for distilling an
effective evaluator. The details of the parameter settings are shown in Table
10

####  C.1.2. Implementation details

The experiments have two phases: (1) Generating subgraph-based explanations;
and (2) Distilling the subgraph evaluator for inference.

In the explanation phase, to efficiently search for informative facts, we
extract key patterns from the 2-hop enclosing subgraph surrounding the target
prediction. We set the parameter $n=2$ to determine the number of selected
entities per hop during greedy searching. To achieve the best evaluation
capability, we use RotatE (Sun et al., 2019) as the target KGE and distill an
evaluator to assess explainability. In the distilling phase, we adopt an R-GAT
with three layers for all datasets and KGE models. To ensure sufficient
expressive power for the model to distill, the hidden dimension is set to 64
for both pre-trained KG embeddings and subgraph representations of the
distilled model. To balance the alignment and ranking objective, we set the
weight of ranking loss to $\lambda=0.5$. During training for all datasets, we
use a learning rate of 0.001. We model explanation methods based on the
distilled model from RotatE, to ensure a fair and effective evaluation of
explainability.

Table 11. The sparsity and corresponding performance of different explainers. | Family-rr | WN-18 | FB15k-237
---|---|---|---
Methods | Avg. #edges | F1@1 | Avg. #edges | F1@1 | Avg. #edges | F1@1
Keplie (fact-based) | 8.297 | 20.33 | 4.794 | 66.37 | 11.190 | 36.64
PaGE-Link (path-based) | 3.085 | 21.89 | 3.640 | 67.70 | 4.993 | 66.12
KGExp-TransE ($n=1$) | 3.182 | 28.77 | 2.263 | 96.40 | 5.142 | 75.67
KGExp-TransE ($n=2$) | 9.782 | 30.47 | 4.772 | 97.10 | 13.661 | 82.04
KGExp-TransE ($n=3$) | 15.132 | 30.49 | 9.223 | 96.91 | 26.146 | 83.21

####  C.1.3. Details of baselines

We implement our KGExplainer and baseline models in Pytorch (Paszke et al.,
2017) and DGL (Wang et al., 2019b) library on an RTX 2080Ti GPU with 11GB
memory. For the implementation of baselines, we use the source code of Kelpie
(Rossi et al., 2022) to reproduce the faithful results and explore
explanations of fact-based methods CRIAGE (Pezeshkpour et al., 2018) and
Kelpie. For other baselines, we adopt the source code reported by their
original paper and use their pre-defined parameters to produce explanations.
In addition to comparing against baselines with no parameter settings for
certain datasets, we also examine the parameters used in a similar scale
dataset. We report the average results and their standard deviation by five
runs in Section 5.

###  C.2. The Full Results of Explanations

The full results (i.e., $F1@[1,3,10]$ and $Recall@[1,3,10]$) of the
explanations are shown in Table 8 and Table 9. We can observe that KGExplainer
is also the best.

###  C.3. Sparisity of Explainers

We discuss the sparsity of the explanations from various explainers. For Fact-
and Path-based methods, we directly adopt the edges and paths for further
evaluation. Therefore the size of explanations depends on the number of edges
and path lengths they explore. For KGExplainer, the users can adjust the
sparsity of explanation subgraphs by selecting different top-$n$ nodes per hop
(See Section 4.4.1). Once the model is trained, the user can directly adjust
the value of $n$ without retraining. For various explainers, We present the
average number of edges (i.e., Avg. #edges) and corresponding $F1@1$
performance on all datasets in Table 11. We see that the path-based method
(e.g., PaGE-Link) with a complete reasoning chain is more effective than the
fact-based method (e.g., Keplie) on fewer visible facts. Moreover, we observe
that KGExplainer can dynamically adjust the size of the explanation subgraphs
and achieve superior performance compared with Fact- and Path-based methods.

##  Appendix D Discussion

###  D.1. Discussion with Related Works

In this section, we further discuss the novelty of KGExplainer compared with
recent related methods. The works (Han et al., 2020; Joshi and Urbani, 2020)
mainly focus on pruning subgraphs to eliminate irrelevant facts and to improve
the performance of link prediction on either temporal or static knowledge
graphs. To some extent, the pruned subgraphs can be considered key information
for predicted links. However, the pruned subgraphs are not connected but
rather a collection of facts, which are referred to as Fact-based explanation
methods. On the other hand, the paper (Lin et al., 2018) uses rule-based
methods to detect fixed patterns and check specific facts, which is different
from KG-based explanation methods for knowledge graph completion tasks.
Similarly, the methods presented in (Zhao et al., 2023; Baltatzis and
Costabello, 2023) are post-hoc explanation methods that identify key triples
as explanations. The identified key triples are discrete facts and can not
form a reasoning chain. These two methods can be classified as Fact-based
models. For the KGC task, the connected subgraphs can form a reasoning chain,
which can better explain target prediction (Zhang et al., 2023). We proposed
KGExplainer to focus on exploring connected subgraphs are different from
previous models. In summary, our method can contribute to the knowledge graph
reasoning community and promote the KG-based explanation methods.

###  D.2. Discussion of Distilled Results

In Table 2, we can see that KGExplainer benefits the base model for some
datasets. We observe the same behavior in (Deng and Zhang, 2020; Jiao et al.,
2019). From their insights, we think the KGExplainer distilled from KGEs may
remove some noise and irrelevant information to the KGC task, making
KGExplainer more robust and having better generalization ability, which leads
to KGExplainer performing better than base KGEs to some extent.