Towards Synergistic Path-based Explanations for Knowledge Graph Completion: Exploration and Evaluation
Authors: Tengfei Ma
Xiang song
Wen Tao
Mufei Li
Jiani Zhang
Xiaoqin Pan
Yijun Wang
Bosheng Song
xiangxiang Zeng
Venue: ICLR 2025 Poster (2025)
Keywords: Knowledge Graph Completion
Model Explainability
Knowledge Graph Embedding
Link Prediction
Primary area: interpretability and explainable AI
TL;DR: KGExplainer explore and evaluate multiple synergistic path-based explanations to promote the transparency of KGE-based KGC models.

Abstract: Knowledge graph completion (KGC) aims to alleviate the inherent incompleteness of knowledge graphs (KGs), a crucial task for numerous applications such as recommendation systems and drug repurposing. The success of knowledge graph embedding (KGE) models provokes the question about the explainability: ``\textit{Which the patterns of the input KG are most determinant to the prediction}?'' Particularly, path-based explainers prevail in existing methods because of their strong capability for human understanding. In this paper, based on the observation that a fact is usually determined by the synergy of multiple reasoning chains, we propose a novel explainable framework, dubbed KGExplainer, to explore synergistic pathways. KGExplainer is a model-agnostic approach that employs a perturbation-based greedy search algorithm to identify the most crucial synergistic paths as explanations within the local structure of target predictions. To evaluate the quality of these explanations, KGExplainer distills an evaluator from the target KGE model, allowing for the examination of their fidelity. We experimentally demonstrate that the distilled evaluator has comparable predictive performance to the target KGE. Experimental results on benchmark datasets demonstrate the effectiveness of KGExplainer, achieving a human evaluation accuracy of 83.3\% and showing promising improvements in explainability. Code is available at \url{https://github.com/xiaomingaaa/KGExplainer}

Published as a conference paper at ICLR 2025
TOWARDS SYNERGISTIC PATH-BASED EXPLANATIONS FOR KNOWLEDGE GRAPH COMPLETION: EXPLO- RATION AND EVALUATION
Wen Tao Bosheng Songb Xiangxiang Zengl.*
Tengfei Ma¹
Xiang Song²
Mufei Li
Jiani Zhang"
Xiaoqin Pan"
Yijun Wang*
!College of Computer Science and Electronic Engineering, Hunan University
2 Ammazon AWS AI
*Georgia Institute of Technology
t Lma @hnu. edu. xiangsxé ama zon. com
xzengehnu.edue edu. on
ABSTRACT
Knowledge graph completion (KGC) aims alleviate the inherent incomplete- ness of knowledge graphs (KGs), a crucial task for numerous applications such as recommendation systems and drug repurposing. The success of knowledge graph embedding (KGE) models provokes the question about the explainability: "Which the patterns of the input KG are most determinant to the prediction?" Particularly, path-based explainers prevail in existing methods because of their strong capability for human understanding. In this paper, based on the observa- tion that fact is usually determined by the synergy of multiple reasoning chains, we propose a novel explainable framework, called KGExplainer, to explore syn- ergistic pathways. KGExplainer is model model-agnostic approach that employs perturbation-
greedy search algorithm to identify the most crucial syner- gistic paths explanations within the local structure of target predictions. To evaluate the quality of these explanations, KGExplainer distills an evaluator from the target KGE model, allowing for the examination of their fidelity. We exper- imentally demonstrate that the distilled evaluator has comparable predictive per- formance to the target KGE. Experimental results on benchmark datasets demon- strate the effectiveness of KGFExpaiiner achieving human evaluation accuracy of 83.3% and showing promising improvements in explainability. Code available at ptttpss://gtiiiii com/ xi http://xiammaaaaaaaaaaaaa Kat.gaaaa/KExppaaneeee
INTRODUCTION
Knowledge graph completion (KGC) aims to infer missing facts and tackles the incompleteness of knowledge graphs (KGs) (Akrami 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 al.) 2022), and drug discovery (Ma al. 2023 Bang et al. [023] Pan al., 2022]. Most KGC models utilize knowledge graph embedding (KGE) methods to map KG elements into dilteiiiimnsi vectors (Nguyen et al. 2023 Song et al., 2023). These vectors are commonly used features for downstream tasks and input into scoring functions for predicting missing links. KGE methods have been shown to achieve more powerful predictive performance than traditional models and can be easily scaled to large graphs (Ali et al. 2021 Zheng al.) 2020). However, current KGE methods make black box predictions without providing explanations, hindering their deployment in iisk-sensitive scenarios (Wang et al. 2022 Zhang et al. (223)).
To address the aforementioned limitation, the idea of adversarial modifications is adopted to find the key facts, which identify the facts to include exclude from the KG and monitor their prediction score change in the perturbed KG (Pezeshkpour et al. (0188) Rossi et al. [202] Betz et al.] (002)). These methods can provide discrete evidence, which insufficient to completely explain why the model makes such a prediction (Zhang et al.) 2023). To capture the coherent reasoning chains for target predictions, some researchers extract possible logical rules by leveraging the known facts
"Corresponding Author

---

Published as a conference paper at ICLR 2025
within the KG (Zhang et al. 2019 Sadeghian et al. 2019: Arakelyan al. 2021). The mined rules are usually represented as paths, which can give the basis of decision decision-making and enhance the trans- parency of the prediction model. Besides, line of work adopts reinforcement learning to identify the next node step-by-step and form a reasoning chain by designing a reward model (Xian et al.,
2019 Bhowmik & de Melo 2020 Tiang al. (023). Apart from them, more recent approaches prefer relying on graph neural networks and introducing pruning mechanisms, learning an edge scorer search for valid paths as explanations (Zhang al. 2023 Chang et al. (024)..
Despite the fruitful progress and the popular trend toward path-based explainers, generat- ing multiple synergistic paths for complex queries has not been discussed. For example, as shown in Figure L Alibaba can be identified as a competitor of JD.com over com- plex KGJJ when given the synergistie facts: both Alibaba and JD.com invest in retail in China. In addition, for the prediction that the drug Acetaminophen decreases the serum con- centration of drug Warfarin (Figure [Tp), the explainers need to provide multiple synergistic paths simultaneously to describe the facts: Acetaminophen inhibits the activity of the enzymes that metabolize Warfarin, thus bringing decrease in the serum concentration of Warfarin. Additionally, for the identified explanations, cannot directly verify their rationality due to the
Why Alibaba and JD.com are in competition?
b. Why do adverse reactions occur when taking Warfarin Acelaminophen.
ground truth is unavailable. Previous methods focused more on model faithful-
locato in
Alibaba
levert in
metabolites
inhibit
incrense
ness (Pezeshkpour et al. 2018 Xian et al., (2019) or manual verification of small-scale facts case by case (Zhang et al., (021). ignoring the quantitative assessment of model explainability.
China
DST Global
Retail
metabolites
metabolitts
invested. byy
increase
inhibit
Warfarin
D.com
Acetaminophen
Explainable Path
Predicted Fact
CYP3A4
CYP2C9
CYP2C19
Figure 1: (a) Multiple paths (blue) explain the competition relation- ship between Alibaba and JID.com; (b) Identifying the adverse reac- tions between Warfarin and Acetaminophen needs the synergy of mul- tiple paths explain the interaction mechanism.
Based on the above obser- vations, we propose KGEx- plainer explore synergis- tic path-based explanations for KGC tasks and provide an effective evaluation. KGExplainer is a post-hoc explainable model performed on the trained KGEs, which searches for single or multiple path-based reasoning chains. We first perform a model- agnostic greedy search approach to identify important paths and distill an explanation evaluator from target KGEs to measure the correlation between explanations and predictions. Then we evaluate the fidelity (Wu et al. 2023) of the identified synergistic paths by measuring whether the original pre- diction can be maintained based on the explored explanations.
To the best of our knowledge, we are the first to approach the explanations of KGE-based KGC models from a novel perspective by emphasizing and evaluating synergistic paths. Besides, we propose evaluation strategy to quantitatively assess the effectiivneess of synergistic path-based explanations by distilling an evaluator to examine their fidelity. Extensive experiments and human evaluation on benchmarks demonstrate the effectiveness and efficiency of KGExplainer.
RELATED WORKS
Knowledge Graph Completion. KGC aims address the invariable incompleteness of knowl- edge graphs (KGs) by identifying missing interactions between entities. Previous rule-based meth- ods (Sadeghian et al. 2019 Arakelyan et al. 202T) mine logical rules iteratively based on pre- trained embeddings of KGEs during the training process. These methods provide reasoning chains for prediction, which enhance the model's transparency. Knowledge graph embedding (KGE) mod- els map KG elements to multi-dimmensiona vectors and define a scoring function to infer new
Alibaba and JDccmm are online retail companies in China.
2

---

Published as a conference paper at ICLR 2025
facts, showing superior performance and scalability over rule-based methods for predicting miss- ing links (Zhang et al. 2022; Wang et al.] 2023; Gregucei et al. (023). Specifically, the translational
models, TransE (Bordes et a (013a) and its extensions (Wang al. 2014: Lin et al. 2013). rep- resent 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 (Touillon 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 embed- ding. 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 suc- cessful predicting unknown facts, they are limited in lacking transparency, blocking researchers from developing trustworthy models. To address the above limitations, we propose KGExplainer to enhance the explainability of KGE-based KGC models.
Explainability in KGC. To increase the transparency of models in KGC tasks, researchers have developed various explainable models (Wang et al, 2022; Huang et al. 2022 Zhang et al. 2023 Yao et al. 2023). Learning rules the explanations from KGs has been studied extensively in inductive logic programming (Galárraga et al. [013)] Qu et al.] 2021 Ho et al. 2018). To improve the explainability of KGE methods, CRIAGE (Pezeshkpour al. 2018), Kelpie (Rossi al. 2022).
and KE-X (Zhao et al., (202)) search for the isolated key edges to explain the target prediction by approximately evaluating the impact of removing an existing fact from the KG on prediction score. However, discrete edges can not form complete reasoning chain. To explore path-based
explanations, PGPR (Xian al. 2019 and ELEP (Bhowmik & de Melo 2020) have adopted reinforcement learning approach to predict tail entities and take the reasoning path between the head and tail entities as the evidence. PaGE-Link (Zhang et al., (023) proposed a path- bath- explainable method for the graph neural network-based KGC tasks, providing valid reasoning chains. To provide enough evidence for the decision-making complex scenario, we propose KGExplainer to explore synergistic paths and form a connected subgraph as an explanation.
3 PRELIMINARY
KGE-based KGC, We define a knowledge graph (KG) as a labeled directed graph G = (V, E) (h,, 1h, E V,r E R. th, E} where each triple represents a relation r between the head entity h and tail entity f. Most KGs are incomplete. Knowledge graph completion (KGC) leverages existing facts in the KG to infer missing ones. Currently, the KGC method adopts deep learning techniques to learn the embeddings of KG elements. 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 score function optimize the vectorized embeddings by maximizing the scores of existing facts. For the incomplete triple (h,r, r, ?), the KGE models find the missing tail entity / with best scores as follows:
estimate the plausibility of triples and
= argmax (h, v).
vEV
The head entity prediction for the unknown links like (?, r,,)) 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.
Enclosing Subgraph. Based on GralL Teru et al. 2020), when given a KG & and a link (h, r, t) 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 (h) = {s d(h, s) < k} and (t)( = {s|d(t, s) S k} for both h and where d(-.-) is the shortest path distance between the entity pair on G. We then obtain the set of entities V = {s|s E (Na as vertices of the enclosing subgraph. Finally, we extract the edges E linked by the set of entities V from G as the k-hop enclosing subgraph g = E).
4 THE KGEXPLAINER FRAMEWORK
Problem Formulation. Given a fact (h, r)t, KGExplainer investigates the explanation that in- tuitively consists of the most critical synergistic path patterns featuring h that allow KGE mod-
3

---

Published as a conference paper at ICLR 2025
Trcinable Recco
Kanskeige Cruch
Che-sopp
Two-hop Search
Krondadge
Explocation
Kanskine Usgg
Stang
b. Exploring Synergistic Paths
KGB
Subgraph Breractie
Explanation
Evahator
Alplonaiia Laeelhaaee
Prosimined KGF
(he-amp Aocusiing
Oseecive a. Training base KGE
Sahgreh
Explainahic Pañta
Distilling Explanation Evalustor
Figure 2: The KGExplainer framework comprises three modules: (a) Pre-training KGE models on the target KG; ; (b) Exploring synergistic path-based explanations for pre-trained KGE models by greedy search ; (c) Distilling evaluator from pre-trained KGE to assess the fidelity of explored explanations quantitatively.
els to predict tail t. For instance, when explaining why the top ranking tail for the missing fact (Donald_Trump, nationality, is USA, KGExplainer searches for the smallest key paths be- tween Donald Trump and USA, allowing the model to predict the same ranking of USA. Specifically, KGExplainer aims to find a connected subgraph (i.e., multiple synergistic paths) Okey that is most influential to the target prediction (h, r)t), and removing the other irrelevant facts do not affect the model's 's prediction. We can define this process follows:
Jkey = argmax Dgg. g)
(2)
fER.us
subject to A(f f()))
min A(f(g). gen.
(3)
where g is the original enclosing subgraph, Jsub denotes the all possible connected subgraphs from to & within g. f()) and f-() represent the original and retrained KGE models. D(g g) represents the structure similarity between and g. and also indicates the sparsity explanations (see Section
4.1 PRE-TRAINE TRAINING KGE.
In this paper, developed the KGExplainer a post-hoc explanation method for KGE-based KGC models by exploring synergistic paths (i.e., connected subgraph). To effectively learn seman- tic knowledge within the complex KG, we adopt the state-of-the-ard RotatE (Sun et 2019) as the target KGE. Specifically, given triple (h, r, t). we adopt score function and expect that the embedding of head entity h similar the embedding of tail entity t by rotating it over the relation By maximizing the scores of positive triples and minimizing the scores of negative ones, we can obtain the pre-trained entity and relation embeddings (Figure [p). Theoretically, KGExplainer 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.3
4.2 EXPLANATION EXPLORATION.
Greedy Search for Key Synergistic Paths. As shown in Figure 2b, given a predicted link (h, r, () for the prediction of tail entity I, we developed greedy search algorithm based a perturbation mechanism to search for crucial paths as the explanations. We first extract the enclosing subgraph around the target link, which contains informative interactions for such prediction. To identify the most important paths influencing the prediction within 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 retrair the target KGE the perturbed subgraph g'. Then we measure the score change of
Retraining KGE over the entire KG is way too costly and we discuss efficient strategy to tackle this issue in Section 422
4

---

Published as a conference paper at ICLR 2025
the target link using the original and retrained embedding 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 single connected component, we search the key entities from the head h. and tail t. hop by hop. We first remove each 1-hop neighhor entity of h and measure their importance to identify the top important entities. After getting the top-n important entities vf from I-hop neighbor entities, we then search the one-hop neighboring entities of vi analogously for important two-hop neighbors vžz We repeat this one-hop search process until reaching the tail entity t of the target link. As result, we capture a set of the k-hop key neighboring entities v [vi..... v and construct a connected subgraph for multiple synergistic paths as the explanation. We provide a detailed Algorithm in Appendix A.
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 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 (h, r, t) and expand g by including the 1-hop neighbors Neutend of the existing entities, which constructs new subgraph Gestend- Then we retrain the embeddings of the KG elements on Geztend to make the calculation of score changes effective. To keep the overall entity and relation embeddings of within the same representation space of G. we alleviate the following constraints: (1) We initialize the embeddings of the entities in Gextend with the pre-trained embeddings from G: (2) We fix the
relation embeddings in gextend as the same as those in G: (3) We fix the embeddings of entities E Neztend By using the retraining strategy, KGExplainer can effectively capture the target fact's s score change and efficiently search for key subgraphs. More details can be found in Appendix A.2
4.3 EVALUATOR DISTILLATION
Why Subgraph Evaluator? Evaluating the quality of identified synergistic paths is essential. How- ever, the ground truth explanations are unavailable, making it difficult to achieve that objective. To evaluate the quality of explanations, retain the key context of target prediction and can still maintain the predicted score (Wu et al. 2023). Thus, an effective idea is to verify that the explored explanations can still obtain the target prediction. However, the base KGEs implicitly have access to the entire graph and only score one triple, which can not compute the prediction based on multiple synergistic paths. To address this limitation, we design a subgraph evaluator by distilling a relational graph neural network (GNN) from pre-trained KGEs for KGC. Given pre-trained KGE-based KGC model r, t). we aim to train a subgraph evaluator to replicate the predictive performance of the target KGE and evaluate the subgraph structures of explanations. During training, the GNN is optimized from their complete enclosing subgraphs. Once trained, the explored explanations as connected sub- graphs can be fed into the evaluator and evaluate the fidelity of multiple synergistic paths (i.e., the connected subgraph).
introduce hypothesis that perfect explanation should
predict the facts
How to get Subgraph Evaluator? Given link (h, r, l), we develop a score function Z(h, r, 1) with L-layer relational graph attention neural network (R-GAT) on its enclosing subgraph y to score it based on the local substructure representation. The update function of the entities in the 1-th layer is defined as:
(inn) W xx)-'),
PER. (E)
(4)
((ir..j) = sigmoid (Wi [x] o Øx + et 2
where e/. and x/ represent the 1-th layer embeddings of relation and entity i. a(s.n)) and (V)(i) denote the weight and neighbors of entity i under the relation r, respectively. 4 is the concatenation operation. W represents the transformation matrix of relation r, and & is the aggregation operation to fuse the hidden features of entities and relations. Finally, we obtain the global representation X Xaub of the subgraph g as follows:
X sub
Σ f(x+), JEV
(5)
V
5

---

Published as a conference paper at ICLR 2025
where V. is the entity set of the enclosing subgraph g. After obtaining the global representation Xaub, we define a linear layer to score the target link as follows:
Z(,, r2t) w X
(6)
where W is transform matrix.
To optimize the subgraph evaluator, inspired by Gou et al. (021), adopt the insights of knowl- edge distillation and consider the predictions of the pre-trained KGE-based KGC model as soft labels. Meanwhile, enhance the model's ability to rank candidate entities, introduce a regu- larization 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:
min Σ 11o r, Zhh, r, t)ll + AL(h,
(7)
(hrr,f)E
where the first term is a score alignment objective. The second term is a pair-wise loss, which is defined by negative sampling:
1 N Σ Z(,,r,u,),
-
where N denotes the number negative samples and Un, is uniformly drawn from V. By minimizing the above optimization objective, we can obtain effective subgraph scoring function with powerful predictive performance and evaluation capabilities for synergistic path-based based explanations.
4.4 SCALABILITY OF KGEXPLAINER
The computation complexity of finding explanations using KGExplainer is related to two parts: 1) the size of enclosing subgraph 9 and 2) the number of entities that require importance evaluation.
Proposition! 1 Given G = (V, R. E), a predicted fact (h, (), the maximum length of paths L,, and the number of paths N, the size of g O LNNVV]
and the size of Nextend O(LN).
[8]
Given h and the maximum number edges within paths is I. N. The probability of entity E V in an edge E E is number of entities in Nextend
2|2| Thus, the size of is bounded by LN 2111 TET
i.e, O [ The
T&T
2LNI E8
2 i.e., O(LN).
TVT
Proposition 2 Given G (V, R. E), predicted fact (h,, 1), 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 K) 21 [D
Following Algorithm inn Appendix A.I the average number of entities to evaluate in the first hop, O in the last hop, and K d in the intermediate hops, where d 2| is the average degree of TV
entity. Thus, the total number of entities to evaluate is (1 (I. 2) (16)).
Here, we conclude that the average computation complexity of finding the explanation for pre- dicted fact (h, is only related to the maximum length of paths L, the maximum number of paths N, and the average degree of entity KG, which is not related to the size of G. Thus, in theory, KGExplainer can balance the computational complexity by adjusting the size of enclosing subgraphs. Besides, KGExplainer can scale to large KGs with a small average degree. More details refer to Appendix A.3
5 EXPERIMENT
In this section, we evaluate the proposed KGExplainer by considering the following key research questions: Q1 Can KGExplainer perform comparable faithfulness and explore informative expla- nations? Q2 Can KGExplainer work well with different sizable explainable subgraphs and various KGE methods? Q3 Is KGExplainer efficient in exploring explanations? We provide more imple- mentation details of KGExplainer and baselines in Appendix B. More additional experiments are shown in Appendix C

---

Published as a conference paper at ICLR 2025
5.1 EXPERIMENTAL SETTINGS
Datasets. We conduct experiments on three widely used datasets for the KGC task. Specifically, OGB-biokg is large-scale KG from OGB project (Hu et al. 2021), which contains millions of facts and is created from a large number of biomedical data repositories. 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 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 detailed statistics of all datasets are shown Appendix B.I.I
Faithful Metries. The evaluation of KGC models is performed by running head and tail predictions on each triple in the test set. For each prediction, the ground truth ranked against all the other entities V. Without loss of generality, for tail prediction, this corresponds to:
tailRank(h, r, t) = Hu E Vlo(h, r, >= @(h, r, t)H-
(9)
Following Kadlec et al. (2017) we adopt @its@N to quantify the predictive performance of KGE and distilled models. HilsON N is the fraction of ranks Srank with value S N:
Hits@N = [ss E S, 8.:85.
(10)
S+
where s; is the ranking of i-th candidate entity and S. is a of rankings for all candidate entities. Following the method proposed by Kadlec et al. (2017). we focus on the Hits@l metric to better highlight model differences. Based on the designed metrics, we report the mean and variance for five runs.
Explainable Metries. As the ground truth explanations of KGC tasks are usually missing, is not easy to quantitatively evaluate the quality of explanations. We consider explanations to be suffi- cient if they allow preserving the KGC performance (Akrami et al.) 2020) Wang et al. [202]] Wu ett al. 2023). Thus we define the Recoll@N and FI@@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 predic- tive rankings. Given the rankings of tested facts by forwarding their explanations to the distilled evaluator, calculate the Recall@N as follows:
Recall@N 18s Sy 55:80 84 S N) E SEUP :8 $ SN
(11)
where SEEP is the ranking set of explanations and S, denotes the original predictive rankings of them. We can assess the trustworthiness of explanations by calculating the recovery rate of the rankings Sr. Meanwhile, the synergistic path-based explanations are critical in the precision of rankings (i.e., Hits@N), to comprehensively evaluate the explainability of KGExplainer, we define FI@N to balance the recall and precision of the explored explanations:
Hits@N = Kss E SpaP
S NH1
Recall@N - Hits@N
FI@N = Recall@N + Hits@N
(12)
|St
Finally, we consider N E {1,3, 10) for the qualitative metries emphasize the performance dis- crepancy.
Baselines. To verify the performance of KG- Explainer in exploring explanations, we com- pare it against subgraph-based (i.e., a batch of discrete facts) methods CRIAGE (Pezeshkpour
Table 1: The predictive performance of KGE and the distilled models on @ts@ 1 (7)) metric.
Methods
OGB-biokg
Family-rr
FB15k-237
et al. al. 2018) and Kelpie (Rossi et al.) 2022]] and base- DRUM (Sadeghian et al. 2019),
TransE
11.32 (0.22)
12.63 (0.09)
41.86 (0.43)
KGExp- TransE
10.40 (0.25)
15.77 (0.11)
40.99 (0.31)
ELEP (Bhowmik & de Melo 2020). and
DistMult
16.11 (0.06)
8.680 (0.27)
10.26 (0.21)
PaGE-Link (Zhang et al. 2023) The sources of subgraph- models KGEx (Baltttiis & Costabello 2024) and KE-X (Zhao et al. 2023)
KGExp-DistMult
14.04
9.881 (0.14)
13.09 (0.32)
RotatE
17.12 (0.19)
39.08 (0.45)
42.10 (0.51)
KGExp-RotutE
17.33 (0.12)
35.79 (0.06)
39.28 (0.29)
are unavailable now, so we exclude them as our baselines.
7

---

Published as a conference paper at ICLR 2025
Furthermore, we design variants of KGExplainer: KGExp-Rand randomly selected some connec- tive paths between head and tail entities to construct an explainable subgraph, which allows an ablation study. KG Trans,, MGEx and KGExp-RotatE are variants of KGEx- plainer that consider TransF (Bordes et al. 2013b), DistMult (Yang et al.. 2015). and RotatE((Sun et al. 2019) as the base KGE, respectively. For convenience, we denote KGExplainer as KGExp.
5.2 PERFORMANCE OF FAITHFULNESS AND EXPLAINABILITY
In response to Q1, we analyze the performance of KGExplainer from faithfulness and explainability. Besides, we provide a human evaluation on Family-rr dataset.
Faithfulness Evaluation. An important goal of explainability models is to accurately and comprchensively represent the local decision- making structure of the target model. Specif- ically, in the context of KGE models, KGEx- plainer should strive replicate their behav- ior as closely as possible (Zhang et al., 2021). Thus, answer Q1, we compare the predic- tive performance of KGExplainer and the target KGE models. As shown in Table 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-TranSE and TransE on FB15k-237 observe that RotatE
Table 2: The F1@1 (%) performance of explana- tions over various datasets. The boldface denotes the highest score and the underline indicates the best baseline.
Methods
OGB-biokg
Family-rr
FB15k-237
CRIAGE
50.03 (0.09)
20.75 (0.32)
40.99 (0.21)
Kelpie
49.32 (0.16)
20.33 (0.23)
36.64 (0.13)
DRUM
62.56 (0.23)
21.26 (0.09)
65.53 (0.19)
ELEP
63.44 (0.21)
22.75 (0.17)
70.11 (0.21)
PaGE-Link
68,29 (0.19)
21.89 (0.13)
66.12 (0.14)
KGExp-Rand
54.32 (0.43)
19.16 (0.26)
55.17 (0.23)
KGExp-TransE
81.97 (0.13)
30.47 (0.25)
82.04 (0.33)
KGHHs--DstMMll
82.33 (0.03)
30.49 (0.24)
84.29 (0.17)
dataset). Furthermore, overall achieves the best performance for KGC and similarly KGExp-RotatE shows superior predictive performance and the best recovery rate 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 powerful evaluator based on the sub- graph substructure around the target link to as- sess the explainability. In Table [ we can see that KGExplainer benefits the base model for some datasets. We observe the same behav- ior in (Deng & 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
KGExp-RotatE
85.21 (0.11)
29.52 (0.12)
83.65 (0.14)
Table 3:
The Recall@1 (%) performance of expla- nations over various datasets. We mark the best score with bold font and mark the best baseline with underline.
Methods
OGB-biokg
Family-rr
FB15K-237
CRIAGE
58.75 (0.07)
28.57 (0.33)
68.23 (0.43)
Kelpic
60.32 (0.22)
27.62 (0.39)
60.01 (0.27)
DRUM
69.87 (0.14)
16.20 (0.21)
87.88 (0.22)
ELEP
76,23 (0.25)
29.84 (0.18)
85.58 (0.29)
PaGE-Link
77.69 (0.15)
27.14 (0.31)
85.13 (0.09)
KGExp-Rand
54.61 (0.55)
26.98 (0.49)
50.37 (0.19)
CGrnspTTranSE
88.37 (0.21)
34,61 (0.43)
92.07 (0.33)
KGFxp- KGFSs-DissMull
89.77 (0.11)
34.60 (0.13)
91.67 (0.11)
KGExp-RotatE
88.65 (0.08)
33.02 (0.11)
91.45 (0.09)
KGExplainer more robust and having better generalization ability, which leads to KGExplainer per- forming better than base KGEs to some extent. Based on these observations. the effectiveness of the distilled evaluator is demonstrated empirically.
Explainability Evaluation. It is essential to assess objectively how good an explanation is for KGExplainer. Unfortunately, similar other explanation methods, evaluating explanations made difficult by the impossibility of collecting ground truth explanations. To fairly evaluate explanations without ground truth and answer Q1, we distill an evaluator and design two metrics F1 @1@ 1 and Recall@1 to quantify how trusty an explanation is. As shown in Table 2 and Table 3 we reported
the F1 @1 and Recall@1 results compared with baselines on three wide-used datasets (F1 @ (3, 10) and R 3, 10] are reported in Appendix C.2). Specifically, KGExplainer improves the Fl@l and Recall@ by at least 16.92% and 12.08% respectively on the OGB-biokg dataset and achieves 7. 7.74% and 4.77% absolute increase over the best baseline the Family-rr dataset. Meanwhile, the performance of KGExplainer on the FB 15--237 dataset has yielded 13.54% and 4.19% gains in F101 and Recall@1 compared with the baselines.
Furthermore, we have the following observations: (1) Compared with the subgraph- based meth- ods CRIAGE and Kelpie, the path-based explainability methods DRUM, ELEP, and PaGE-link that
8

---

Published as a conference paper at ICLR 2025
utilize reasonable paths between source and target entities achieve better performance, which in- dicates that the comnecting paths are important for the model explanation. (2) Compared with the path-based explainability models ELEP and PaGE-Link, synergistic path-based KGExplainer (e.g., KGFxp-RotatE) performs better than them on all datasets, demonstrating that the multi- ple synergistic path-based patterns 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 ex- planations, yields significantly inferior perfor- mance compared with other KGExplainer vari- ants. This demonstrates that KGExplainer in- deed identifies semantically meaningful con- nected subgraph explanations for model pre- dictions, which are superior to randomly sam- pled subgraphs by a large margin. This may be because the KGExplainer based on target KGBs can explore synergistic reasonable paths 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 per- formance compared with the baselines demon- strates that KGExplainer effectively explores and evaluates informative explanations.
Please seleet the best explanation Why the model predicts relationship between source turget nodes?"
LaFedler
id:6
SNerter
id:6
id:4
id:A
atinek
id:29
id:29
ieftrothet
Kelpie
DRUM
id:2
id:2
Lefilllor
id:5
ieBoether
LsReether
id.6
inNeshiro
Allade
id:4
id:4
(sBecther
1.29
idDeather
Id:39
id:39
PaGE-Link
KGExplainer
Human Evaluation Following [Zhang et al. (2023), we conduct a human evaluation by ran- domly picking 20 predicted links from the test set of Family-rr and generating explanations for each link using subgraph-based model (i.e., Kelpie), two path-based methods (i.e., DRUM and PaGE-Link), and KGExplainer. We de- signed 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 infor- mation, similarly as in Figure 3 but excluding method names. We sent the survey to peo- ple across graduate students, PhD students, and professors, including people with and without background knowledge about KGs. We ask re- spondents 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 the best. The survey demon- strates that KGExplainer is more effective in searching for human comman-undered understandable explanations than other methods. More details refer Appendix B.2
Figure 3: The explanations explored by Kelpic, DRUM, PaGE-Link, and KGExplainer on the fact (id 2, is asFather, id 5).
Various Sizable Explanations
Performance on Varions KGEs
Metries
Metrics
0.2
0.0
0.0
n=1
n=2
n=3
MGEAD Rund:
KGEEs RohatE
F101
Bualig)
Figure 4: The explainable performance of KG- Explainer with different hyper-parameters over Family-rr dataset.
5.3 ROBUSTNESS OF KGEXPLAINER (Q2)
In this section, to answer Q2, we conduct the robustness analysis on the Family-rr dataset to study the impact of different sizable explored subgraphs and various KGE-based KGC models.
Size of Synergistic Path-based explanations. To investigate the influence of different sizable path- based explanations, we conduct experiments based on KGExp-RotatE by varying n to 1, 2, and 3. The KGExplainer explored synergistic paths with 1 is equal to exploring single explainable path. As illustrated in the left of Figure we observe the best performance on F1@1 and Recall metrics when utilizing the explainable paths with ferent sizes collapsed into a hunchback shape. The reason could be that the explored synergistic paths with are inefficient in recovering the original predictions and the subgraph patterns
2. Meanwhile, the performance across dif-

---

Published as a conference paper at ICLR 2025
with n may contain many irrelevant facts, which introduce much noise and reduce the perfor- mance of KGExplainer. This suggests that KGExplainer maintains comparable performance under different sizable synergistic paths.
KGExplainer over various KGE-based KGC models. We investigate the impact of different tar- get 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 @1@1 and Recal|1 for different variants. This 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 ex- planations for embedding based models and is model-agnostie, as demonstrated by its performance across various KGEs.
5.4 EFFICIENCY ANALYSIS (Q3)
Inference Time. We trained KGExplainer and baselines using a server with 12 virtual Intel(R) Xe) Platinum 8255C CPU and one RTX 2080 Ti GPU. To verify the effectiveness of KG- Explainer in searching for explanations, we designed an experiment to evaluate KGExplainer. As illustrated Table g we show the average cost time of exploring explanations over the test sets of all datasets from different methods. We find that KGExplainer has similar cost to CRIAGE and more efficient than PaGF-Link and Kelpie, which indicates that KGExplainer can be effectively extended to complex KGs in searching synergistic path- path-based explanations. This is because KGEx- plainer 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 explor- ing process. Overall, KGExplainer has superiority in exploring synergistic path-bau aath-based explanations with complex patterns, which can scale to large knowledge graphs.
Sparsity of Explanations
We discuss the sparsity of the explanations from various explainers. For KGExplainer and baseline methods, we adopt the aver- age number of edges (i.e., #edge) as the size of explanations. For KGExplainer, the users can adjust the sparsity of explana- tion subgraphs by selecting different top- nodes per hop (Refer to Section 4.2p. As shown in Table[5] we observe that the path- based method (e.g.. PaGE-Link) explor- ing a coherent reasoning chain with fewer facts is more efficient than the subgraph- based method (e.g., Keplie). Additionally, KGExplainer exploring multiple synergis- tic paths can achieve superior performance on comparable sparse explanations than the path- based method. The phenomenon in Table [ shows that KGExplainer can yield better explainability on explanations with low information density.
Table 4: The average cost time (s) of exploring expla- nations for various methods. Ours shows comparable efficiency.
CRIAGE
Kelpie
PaGE-Link
Ours
Family-rr OGB-biokg FB15k-237
1.65
4.84
1.74
1.32
121.67
183. 24
257.35
157.28
15.13
28.51
16.93
16.81
Table 5: The sparsity and corresponding performance different explainers. Ours indicates KGExplainer shows superior sparsity.
Family-rr #edge
OGB-biokg #edge
FB15k-237
Methods
F1@1
F1@1
#edge
F1@1
Keplie PaGI--Link
8.297
20.33
37.58
49.32
11.19
36.64
3.085
21.89
12.87
68.29
4.993
66.
Ours (n
3.182
28.77
9.751
79.28
5.142
75.67
Ours (n
9.782
30.47
45,27
81.97
13,66
82.04
Ours (n 3)
15.13
30.49
112.3
80.33
26.14
83.21
CONCLUSION
In this work, we proposed a KGExplainer to identify synergistic paths as explanations over com- plex 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 paths. Extensive ex- periments 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 Al for chemical and biological applications.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
The work was supported by the National Natural Science Foundation of China (U22A2037, 62272151, 62122025, 62425204, 62450002 and 62432011), the National Science and Technol- ogy Major Project (2033ZD0120002 (2022I120016), The science and technology innovation Program of Hunan Province (2022RC1099), and the Beijing Natural Science Foundation (L248013).
Hunan Provincial Natural Science Foundation of China
REFERENCES
Farahnaz Akrami, Mohammed Samiul Saeef, Qingheng Zhang, Wei Hu, and Chengkai Li. Realistic re-evaluation of knowledge graph completion methods: An experimental study. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1995-2010, 2020.
Mehdi Ali, Max Berrendorf, Charles Tapley Hoyt, Laurent Vermue, Mikhail Galkin, Sahand Shar- ifzadeh, Asja Fischer, Volker Tresp, and Jens Lehmann. Bringing light into the dark: A large-scale evaluation of knowledge graph embedding models under unified framework. IEEE Transactions on Pattern Analysis and Machine Intelligence, (4(12):8825-884) 2021.
Erik Arakelyan, Daniel Daza, Pasquale Minervini, and Michael Cochez. Complex query answering with neural link predictors. In International Conference on Learning Representations, pp. 1-14,
2021.
Vasileios Baltatzis and Luca Costabello. Kgex: Explaining knowledge graph embeddings via sub- graph sampling and knowledge distillation. In Learning on Graphs Conference, pp. 27-1.PMLR 2024.
Dongmin Bang. Sangsoo Lim, Sangseon Lee, and Sun Kim. Biomedical knowledge graph learning for drug repurposing by extending lions, 14(1) 1411)33570, 2023.
to multiple layers. Nature Communica-
Patrick Betz, Christian Meilicke, and Heiner Stuckenschmidt. Adversarial explanations for knowl- edge graph embeddings. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2820-2826, 2022.
Rajarshi Bhowmik and Gerard de Melo. Explainable link prediction for emerging entities in knowl- edge graphs. In The Semantic Web-ISWC 2020: 19th International Semantic Web Conference, pp. 39-55, 2020.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collab- oratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 1247-1250, 2008 ISBN 9781605581026.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in Neural Information Pro- cessing Systems, 26:1 2013a.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Durán, Jason Weston, and Oksana Yakhnenko.
Translating embeddings for modeling multi-relational data. In Proceedings of the 26th Interna- tional Conference on Neural Information Processing Systems, pp. 2787-2795, 2013b.
Heng Chang, Jiangnan Ye, Alejo Lopez Avila, Jinhua Du and Jia Li. Path-based explanation for knowledge graph completion. arXiv preprint arXiv:2401.02220 2024.
Xiang Deng and Zhongfei Zhang. Can students outperform teachers in knowledge distillation based model compression? 2020.
Luis Antonio Galárrga,, Christina Teffioudi, Katja Hose, and Fabian Suchanek. Amie: association rule mining under incomplete evidence in ontological knowledge bases. Proceedings of the 22nd international conference on World Wide Web, pp. 413-422, 2013.
11

---

Published as a conference paper at ICLR 2025
Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129:1789-1819 2021.
Cosimo Gregucci, Mojtaba Nayyeri, Daniel Hernández, and Steffen Staab. Link prediction with attention applied on multiple knowledge graph embedding models. In Proceedings of the ACM Web Conference 2023, pp. 2600-2610, 2023.
Zhen Han, Peng Chen, Yunpu Ma, and Volker Tresp. Explainable subgraph reasoning for forecasting on temporal knowledge graphs. In International Conference Learning Representations, 2020.
Vinh Thinh Ho, Daria Stepanova, Mohamed Gad-Elrab, Evgeny Kharlamov, and Gerhard Weikum. Rule learning from knowledge graphs guided by embedding models. In The Semantic Web-ISWC 2018: 17th International Semantic Web Conference, pp. 72-90, 2018.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB- LSC: A large-scale challenge for machine learning on graphs. In Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL
Jiacheng Huang, Yao Zhao, Wei Hu, Zhen Ning, Qijin Chen, Xiaoxia Qiu, Chengfu Huo, and Weijun Ren. Trustworthy knowledge graph completion based on multi-sourced noisy data. In Proceed- ings of the ACM Web Conference 2022, pp. 956-965, 2022.
Hao Jiang, Chuanzhen Li, Juanjuan Cai, and Jingling Wang. Reenr: 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, pp. 1710-1720, 2023.
Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. Tinybert: Distilling bert for natural language understanding. International Conference Machine Learning and Natural Language Processing, 2019.
Unmesh Joshi and Jacopo Urbani Searching for embeddings in haystack: link prediction knowledge graphs with subgraph pruning. In Proceedings of The Web Conference 2020, pp- 2817-2822 2020.
Rudolf Kadlec, Ondrej Bajgar, and Jan Kleindienst. Knowledge base completion: Baselines strike back. In Proceedings of the 2nd Workshop Representation Learning for NLP, pp. 69-74,
August 2017.
Su-Chin Lin, Kai- Kai-Hsiang Chou, Yen Chen, Hsu-Chun Hsiao, Darion Cassel, Lujo Bauer, and Limin Jia. Investigating advertisers' domain domain-changing behaviors and their impacts on ad- ad-blocker filter lists. In Proceedings of the ACM Web Conference 2022, pp. 576-587, 2022.
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation em- beddings for knowledge graph completion. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, pp. 1-7, 2015.
Tengfei Ma, Xuan Lin, Bosheng Song, Philip S. Yu, and Xiangxiang Zeng. Kg-mtl: Knowledge graph enhanced multi-task learning for molecular interaction. IEEE Transactions on Knowledge and Data Engineering, 35(7):7068-700 2023.
Trung- Kien Nguyen, Zemin Liu, and Yuan Fang. Link prediction on latent heterogeneous graphs. In Proceedings of the ACM Web Conference 2023, pp. 263-273, 2023.
Maximilian Nickel, Volker Tresp, Hans- Kriegel, et al. A three-way model for collective learn- ing multi-relational data. In International Conference Machine Learning, volume 11, pp- 01044482-30458-4 2011.
Xiaoqin Pan, Xuan Lin, Dongsheng Cao, Xiangxiang Zeng, Philip S Yu. Lifang He, Ruth Nussinov, and Feixiong Cheng. Deep learning for drug repurposing: Methods, databases, and applications. Wiley Interdisciplinary Reviews: Computational Molecular Science, 12(4):e157, 2022.
12

---

Published as a conference paper at ICLR 2025
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitio, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Pouya Pezeshkpour, Yifan Tian, and Sameer Singh. Investigating robustness and interpretability of link prediction via adversarial modifications. In North American Chapter of the Association for Computational Linguistics, pp. 1-12, 2018.
Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogie: Learn- ing logic rules for reasoning on knowledge graphs. International Conference on Learning Repre- sentations, pp. 1 1-20, 2021.
Andrea Rossi, Donatella Firmani, Paolo Merialdo, and Tommaso Teofili. Explaining link predic- tion systems based on knowledge graph embeddings. In Proceedings of the 2022 International Conference on Management of Data, pp. 2062-2075, 2022.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to- end differentiable rule mining knowledge graphs. Advances in Neural Information Processing Systems, 32:1-13, 2019.
Xiran Song, Jianxun Lian, Hong Huang. Zihan Luo, Wei Zhou, Xue Lin, Minggi Wu, Chaozhuo Li, Xing Xie, and Hai Jin. xgen: An extreme graph convolutional network for large-scale social link prediction. In Proceedings of the ACM Web Conference 2023, pp. 349-359, 2023.
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, pp. 1-18, 2019.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Learning Representations, pp. 9448 9457, 2020.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, éèric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In International Conference on Machine Learning, pp. 2071-2080, 2016.
Chenxu Wang, Xin Wang, Zhao Li, Zirui Chen, and Jianxin Li. Hyconve: A novel embedding model for knowledge hypergraph link prediction with convolutional neural networks. In Proceedings of the ACM Web Conference 2023, pp. 188-198, 2023.
Hongwei Wang, Miao Zhao, Xing Xie, Wenjie Li, and Minyi Guo. Knowledge graph convolutional networks for recommender systems. The World Wide Web Conference, pp. 3307-3313, 2019a.
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. Deep graph library: graph-centrie, highly-performant package for graph neural networks. arXiv 2019b.
preprint 1909.0190000130
Peng Wang, Renqin Cai, and Hongning Wang. Graph-based extractive explainer for recommenda- tions. In Proceedings of the ACM Web Conference 2022, pp. 2163-2171, 2022.
Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained explainability for graph neural networks. Advances in Neural Information Processing Systems, 34:18446- 18458. 2021.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by trans- lating on hyperplanes.
Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 28, pp. 1119, 2014.
Fang Wu, Siyuan Li, Lirong Wu, Dragomir Radev, Yinghui Jiang, Xurui Jin, Zhangming Niu, and Stan 7. Li. Explaining graph neural networks via non-parametric subgraph matching. Interna- tional Conference on Machine Learning, pp. 1-13, 2023.
Yikun Xian, Zuohui Fu, Shan Muthukrishnan, Gerard De Melo, and Yongfeng Zhang. Reinforce- ment knowledge graph reasoning for explainable recommendation. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 285-294, 2019.
13

---

Published as a conference paper at ICLR 2025
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. International Conference on Learning Representations, pp. 1-12, 2015.
Yuhao Yang. Chao Huang, Lianghao Xia, and Chenliang Li. Knowledge graph contrastive learn- ing for recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1434-1443, 2022.
Liuyi Yao, Yaliang Li, Bolin Ding, Jingren Zhou, Jinduo Liu, Mengdi Huai, and Jing Gao. Path- specific causal fair prediction via auxiliary graph structure learning. In Proceedings of the ACM Web Conference 2023, pp. 3680-3688, 2023.
Shichang Zhang, Jiani Zhang. Xiang Song, Soji Adeshina, Da Zheng, Christos Faloutsos, and Yizhou Sun. Page-link: Path-based graph neural network explanation for heterogeneous link prediction. In Proceedings of the ACM Web Conference 2023, pp. 3784-3793, 2023.
Wen Zhang, Bibek Paudel, Liang Wang, Jiaoyan Chen, Hai Zhu, Wei Zhang, Abraham Bernstein, and Huajun Chen. Iteratively learning embeddings and rules for knowledge graph reasoning. In 2019.
The World Wide Web Conference, pp.
Wen Zhang, Mingyang Chen, Zezhong Xu, Yushan Zhu, and Huajun Chen. Explaining knowledge graph embedding via latent rule learning. OpenReview.Net, 26:1-14, 2021.
Zhanqiu Zhang, Jie Wang. Jieping Ye, and Feng Wu. Rethinking graph convolutional networks in knowledge graph completion. In Proceedings of the ACM Web Conference 2022, pp. 798-807, 2022.
Dong Zhao, Guojia Wan, Yibing Zhan, Zengmao Wang, Liang Ding, Zhigao Zheng, and Bo Du. Ke-x: Towards subgraph explanations of knowledge graph embedding based on knowledge infor- mation gain. Knowledge-Basse Based Systems, 278: 10772, 2023.
Da Zheng, Xiang Song, Chao Ma, Zeyuan Tan, Zihao Ye, Jin Dong, Hao Xiong, Zheng Zhang, and George Karypis. Dgl-ke: Training knowledge graph embeddings at scale. In Proceedings of the 43rd International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 739-748, 2020.
14

---

Published as a conference paper at ICLR 2025
Algorithm 1: Greedy search for subgraph explanation
Input Target prediction (h, r, t); Enclosing subgraph gi Prediction score s; Subgraph
extracting function F Score function Φ; Number of entities retrieved per hop Output: key subgraph Jkey that is most critical to the target prediction (h, t)-
Initialize set of visited entities Suisit as {h};
Initialize a set of key entities Skey as {h};
Initialize queue of searching entities Seearch as {b}:
while Searchh is not empry do Initialize H as an empty nex-Heepp;
escarching + :ppp:)
i E (esearching) then E
Skey <- Skey U {t};
break;
for v E (esearching) do
if u & Swisit then
Smisit + Spisit U {
Create of by removing from and finetune the KG embeddings of g'; Get new embeddings h, r, f as h r', t':
s' 6-h'rrrr" rt);;
6. 6- 8 8':
Put into H with its corresponding value 5.;
for i 4- 1 to do
Pop e with the maximum 6, from H and put into Skey and Seearchi
Jkey F (u Skay);
return Jkey
Table 6: 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
OGB-biokg
93,773
51
4,762,678
3000
A KGEXPLAINER
A.1 THE ALGORITHM OF GREEDY SEARCH
For easier understanding, we show detailed algorithm to describe how KGExplainer provides key explanations in Algorithm T
A.2 RETRAINING STRATEGY
Retraing the embeddings over the entire KG is infeasible due removing one entity and its facts have little impact on the embedding of KG elements. To reduce the overhead of retraining, we de- veloped subgraph-basee
retraining strategy as shown in Figure We extract 2-hop enclosing subgraph g around the target fact (h, r.)... We argue that the subgraph contains the key informa- tion that leads to the target prediction. Thus the retraining process is only visible to the subgraph. Figure 5 shows an example of how is extracted. Meanwhile, to ensure that the retrained entity representation space consistent with the original knowledge graph, we expand g by including the 1-hop neighbors Neztend of the existing entities and fixed their embeddings. In Figure we show the learnable and fixed entities in the fine-tuning process. Specifically, we adopt the following con- straints: (a) fixed the relation embeddings in g as the same as those in 9; and (c) we fixed the embedding of E Nartend-
the embeddings of the entities in to initialize the embeddings of g: (b)
15

---

Published as a conference paper at ICLR 2025
Icarnable
K-hop
Sampling
Pre-trained
Subgraph
Figure 5: An example of creating subgraph from 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 g. Then it was expanded by including the 1-hop neighbors NeighborsNNeztend of existing entities (the gray vertices).
Family-rr
0.32
0.30
0.975
F1@1
FI@I
0.970
0.965
0.24
0.22
0.960
1-hop
2-hop
3-hop
1-hop
2-hop
3-hop
KCilssp
KGDxp
KGlisp Rotatl
Figure 6: The F1@1 performance of KGExplainer on Family-rr and WN-18 various sizable enclosing subgraphs.
A.3 THE COMPUTATIONAL EFFICIENCY
The computational complexity of KGExplainer primarily arises from two factors: (1) the greedy search within g. and (2) the re-training cost associated with g. As discussed in Section 4.4, the complexity of the greedy search is largely determined by local parameters. The re-training cost, on the other hand, depends on the underlying KGE model The computational complexity of the re- training stage for different base KGEs, which is dominated by the size of subgraph 9 (i.e., O LNDV)) discussed in Section 4.4), the embedding dimension d, and the size of negative samples n. Thus can analyze the efficiency of base KGEs as follows:
In TransE, DistMult, and RotatE, the computational efficiency of each fact within g is (( 1)d). Therefore, the overall complexity is O LNV maximum path length, N denotes the path number.
[ (n 1)d), where L is the
In conclusion, the practical runtime largely depends on the local parameters the knowledge graphs. The results in Table show strong positive correlation between the number of paths and computation time, which aligns closely with our theoretical analysis. Therefore, we can improve the scalability of large knowledge graphs by adjusting these local parameters.
Table 7: The distribution of degree, path length, and path number various KGs. Note that the analysis is conducted within local subgraphs (2-hop) test set.
Datasets
avg. degree
avg. path length avg. path number
avg. time
Family-rr
3.902
2.828
4.1
1.32
FB 537
9.357
4.195
50.054
16.81
OGB-biokg
101.579
3.982
457.234
157.28
16

---

Published as a conference paper at ICLR 2025
A.4 FORMALIZING THE CONCEPT OF PATH SYNERGY
We can formalize the concept of synergistic paths from an information-fheerriicc perspective. Let:
(G (V E)) be KG with entities V, relations R, and edges E.
h,, denote the head entity, relation, and tail entity, respectively, forming the target prediction.
P = P2........ P be a set of paths between h and t, where each represents a se- quence of edges from
We aim quantify the synergy among paths in P by evaluating how much additional information these paths provide collectively toward the prediction i, compared to the information provided by each path individually.
1. Mutual Information of Individual Paths: Define [[t; p.) as the mutual information between the target prediction and a path p; from h to t. This quantifies the amount of information that ps alone contributes to the prediction of t:
[(t:p.) (t) - Ht(pp.),
where (t)) is the entropy of the target prediction t, and Httpp; is the conditional entropy of t given information from path pi.
2. Joint Mutual Information of Path Set: Let [(1; (Xynerg)) represent the mutual information between and the subset of paths Psynergy C P, which includes multiple paths that contribute to the prediction. This joint mutual information measures the information provided by the paths in P Peynergy when considered together.
[(t P Peynergu) = (t) Peynergr))
The paths in Payneray are considered synergistic the joint mutual infor- mation [tt; synergg) is greater than the sum of individual mutual informations I(t: p.) for each
Synergy Condition:
Pi E P
I(t: Pe Peynergu)
Σ
I(t:p.).
PVEPagnerg
This incquality implics that the paths in P Peynergy provide *additional predictive information* about t when considered together, beyond what each path contributes individually. This excess information captures the synergy among paths.
4. Interpretation and Optimization:
The set Paynergy can be identified the subset of paths P from h to that maximizes the synergistic mutual information [11; P Pxynergy) - Ep.EP Poyeery p(1;p)).
Formally, we can define the optimal synergistic path set Pt Psynergy
P Peynrrg = arg max
[(1:P)) Σ I(l:p))
PCC
PLEPY
B EXPERIMENTAL SETTINGS
B.I IMPLEMENTATION DETAILS
B. DATASETS
We show detailed statistics of all datasets Table 6 #train and #test are the number of triples on the training and testing sets.
17

---

Published as a conference paper at ICLR 2025
Table 8: The hyperparameters of KGExplainer during distillation phase.
Family-rr
WN-18
FB15k-237
OGB-biokg
embedding dim
64
64
64
64
learning rate
0.0015
0.001
0.001
0.001
weight of pair-wise loss
0.5
0.5
0.5
0.5
Epochs
50
50
50
100
R-GAT layers
3
Optimizer
Adam
Adam
Adam
Adam
Batch size
1024
4096
4096
4096
#entity per hop n
2
2
2
2
enclosing subgraph size
2
target KGB
TransE
RotatE
RotatE
RotatE
B.1.2 DETAILS OF KGEXPLAINER
The experiments contain (1) Generating subgraph-based explanations, and (2) Distilling the sub- graph evaluator for assessment.
In the explanation phase, we extract key subgraphs from the 2-hop enclosing subgraph surrounding the target prediction. We set 2 to determine the number of selected entities per hop during greedy searching. To achieve the hest evaluation capability, we distill an evaluator from RotatE (Snn et al. (2019) to assess explainability (See Section 5.2). More settings of hyperparameters
shown in Table g In the distilling phase, to ensure sufficient expressive power for the model to distill, tune the hyperparameters to get the optimal distilled model. The details of hyperparameters
depicted in Table 8
B.1.3 DETAILS OF BASELINES
We implement our KGExplainer and baseline models in Pytorch/Paszke et al. (2017) and DGL Wang al. (2019h) library
RTX 2080Ti GPU with 11GB memory. For the implementation of baselines, we use the source code of Kelpie Roosi et al. (2022) to reproduce the faithful results and explore explanations of fact-based methods CRIAGE Pezeshkpour al. (20T8) 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
B.2 DETAILS OF HUMAN EVALUATION
For valuable human evaluations, we consider the following guidance for participants:
We give two bases for judgment as guide when asking participants questions. 1. In Family-rr, for predicting the kinship between two individuals, the explanation should be based on the known family memberships, marital relationships, etc. reasonably derived. 2. Encourage testers to choose more concise and clear explanations, while maintaining completeness. Avoid overly complex explanations so that key information can be presented clearly.
The results from different models are presented the participants simultaneously
We randomly selected 20 samples from the test set of Family-rr rr for participants to evaluate.
C ADDITIONAL EXPERIMENTS
C.I PERFORMANCE ON VARIOUS SIZABLE ENCLOSING SUBGRAPHS
Similar to the experiments in Section 5.3 (i.c., Hyper-parameter Sensitivity Analysis), we conduct
another experiment study the model's explainability various sizable enclosing subgraphs. We
18

---

Published as a conference paper at ICLR 2025
Table 9: The F1@N(() performance of explanations over various datasets. The boldface denotes the highest score.
Family-rr
WN-18
FB15k-237
OGB-biokg
FI@3
FI 10
FI@3
FI @ 10
FI @3
Fl @ 10
FI@3
FI@ 10
CRIAGE
27.22
36.44
72.91
77.78
48.81
53.26
54.27
61.62
Keplie
27.18
36.25
73.58
79.39
40.77
48.01
52.59
61.21
DRUM
25.23
30.73
75.58
77.80
67.34
71.03
65.87
72.54
ELPE
75.69
79.27
78.35
83.21
29.71
40.40
67.41
71.65
PaGE-Link
28.42
38.49
70.99
75.21
70.77
76.51
71.32
77.58
KGExp-rand
27.55
41.48
37.43
40.46
61.03
66.58
56.47
59.39
XGExp-TransE
45.89
62.96
98.57
99.58
85.41
89.97
84.22
88.37
KGExp
44.08
57.47
97.89
99.41
86.74
90.17
84.35
89.73
KGExp-RotatF: 39.56
57.25
98.58
99.57
87.41
92.97
86.97
90.04
Table 10: The Recall@ (%)) performance of explanations over various datasets. The boldface denotes the highest score.
Family-rr
WN-18
FB15k-237
OGB-biokg
Recall@3
Recall 10
Recall@ Recall@3
Recall@3
Recall
Recall@3
Recull @ 10
CRIAGE
32.02
36.95
95,45
99. 99.34
76.87
82.11
65.95
70.44
Keplic
31.87
36.55
93.69
99.51
66.91
75.52
67.26
75.34
DRUM
22.09
30.92
93.69
94,93
89.01
91.12
76,23
81.07
ELPE
35.17
41.34
93.11
95.23
89.76
93.21
80.21
83.15
PaGE-Link
31.77
38.13
88.32
92.20
87.32
89.04
78.65
83.26
KGExp-rand
33.44
43.97
92.47
94.61
57.12
64.31
58.37
62.59
KGiHxp/TTranst:
46.85
61.61
99.47
99. 84
93.41
94.57
90.48
93.51
XGExp-DistMull
43.05
56.26
99.31
99.71
92.01
93.89
91.66
93.05
KGiExpRRotat
41.48
99.47
99.84
94.69
select top-n entities per hop and vary the size of k-hop enclosing subgraph to 2,2 The F1@1 performance of KGExplainer over various sizable subgraphs is depicted in Figure 6 Theoretically, the larger the subgraph to searched, the more sufficient key information it contains, so that more effective explanatory subgraphs can be retrieved. We can observe that KGExp-Rotath performs better as the size of subgraphs increases on both Family-rr and WN-18 datasets, which indicates that KGExplaiinr based on RotatE has generalization and stability. However, KGExplainer over TransE and DistMult only fits this phenomenon on one the datasets, showing they are limited in generalizing to other data distributions. Thus to achieve fair comparison, we consider the KGExp- RotatE as the subgraph evaluator and assess other baseline methods.
C.2
THE FULL RESULTS OF EXPLANATIONS
The full results (i.e., F1 @ 10) and Recall@ (3, 10)) of the explanations are shown in Table 9 and Table 10 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 subgraph- and path-based methods, we directly adopt the edges and paths for further evaluation. Therefore the size of ex- planations depends on the number of edges and path lengths they explore. For KGExplainer, the users can adjust the sparsity multiple synergistic paths 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 without retraining. For various explainers, We present the average number edges (i.e., Avg, #edges) and corresponding F1@1 performance all datasets in Table II] We see that the path-based method (c.g.. PaGE-Link) with a complete reasoning chain is more effective than the fact-based method (e.g., Keplie) on fewer visible facts. Moreover, observe that KGExplainer can dynamically ad-
19

---

Published as a conference paper at ICLR 2025
Table 11: The sparsity and corresponding performance of different explainers.
Family-rr Avg. Redges
WN-18
FR15K-237
OGB-biokg Avg. #edges
Methods
F1@1
Avg. #edges
FI@1
Avg. #edges
FI@1
Fl
Keplic
8.297
20.33
4.794
66.37
11.19
36.64
37.58
49.32
Page-Link
3.085
21.89
3.64
67.7
4.993
66.12
12.87
68.29
KGExp-TransE (n=1)
3.182
28.77
2.263
96.4
5.142
75.67
9.75
79.28
KGEXp-TransE (n=2)
9.782
30.47
4.772
97.1
13.661
82.04
45.27
81.97
KGExp-TransE (n=3)
15.132
30.49
9.223
96.91
26.146
83.21
112.37
80.33
just the size of the explanations and achieve superior performance compared with subgraph- and path-based methods.
C.4 PERFORMANCE KGEXPLAINER ON VARIOUS ARCHITECTURES
The evaluators built different architectures demonstrate robustness. The evaluation results of evaluators distilled from different base KGEs have minor differences. Specifically, we evaluate KGExplainer's performance using different evaluator architectures across various KGEs. We use RotatE as the base KGE to generate explanations for the Family-Ir dataset, and then assess these explanations using evaluators distilled from different teacher KGEs, Table 12 reveals two key find- ings:
The evaluator distilled from RotatE: achieves the best performance, with differences among evaluators due variations in their predictive abilities.
Evaluators based on R-GAT and Grail. Teru et al. (2020) (which applies R-GCN on sub- graphs) show similar performance across different KGEs. This may be because that the architectural differences between R-GAT and R-GCN are minor.
These results highlight that an evaluator with strong predictive capability is essential for high-quality evaluations. Accordingly, we primarily select RotatE as the teacher KGE for distilling evaluators.
Table 12: The explainable performance of various evaluators on the Family-rr dataset.
teacher KGEs
KGExplainer (R-GAT)
KGExplainer (GraiL)
TransE 27.39
28.51
DistMult
23.43
21.15
RotatE 30.47
28.26
C.5 COMPUTATIONAL TIME OF KGEXPLAINER ON DIFFERENT LOCAL PARAMETERS
To improve scalability for larger KGs, we can adjust the local enclosing subgraph size (e.g., reduc- ing from a 2-hop to 1-hop subgraph) decrease path length and path count. Table 13 presents the distribution of node degree, path length, path number, and computation time across different sub- graph scales over OGB OGB-biokg, revealing strong positive correlation between them, consistent with our theoretical analysis. In conclusion, the complexity of KGExplainer is driven primarily by local parameters- such as path length I., path number N, and average degree- rather than the overall size of the knowledge graph (KG).
Table 13: The distribution of average degree, path length, path number, and computation time over various subgraph scales.
Scale avg. degree
avg. lenghh
avg. path number avg. time
1-hop
97.265
2.573
346.331
103.245 157.28
2-hop
101.579
3.982
457.234
20

---

Published as a conference paper at ICLR 2025
D DISCUSSION
D.1 NOVELTY
Some related works Han et al. (2020): Joshi Urbani 2020) mainly focus on pruning subgraphs to eliminate irrelevant facts and to improve the performance of link prediction on either temporal or static KGs. To some extent, the pruned subgraphs can be considered key information for predicted links. However, the pruned subgraphs are not connected but rather collection of facts, which are fact-based explainable methods. Similarly, KE-X Zhao et al. (2023) and KGEx [Baltatzis & Costabello (024) post-hoc explainable methods that identify key triples explanations. The identified key triples are discrete facts and can not form a reasoning chain. Additionally. PaGE- Link Zhang et al. (2023) and Power-Link Chang et al. (2024) are path-based explainable methods that focus on exploring a single path and rely on selecting multiple discrete paths manually for complex scenes. In contrast, KGExplainer emphasizes exploring multiple synergistic paths globally to form connected subgraphs, which is novel and more expressive than previous models.
D.2 DISCUSSION OF DISTILLED RESULTS
In Table 1 we can see that KGExplainer benefits the base model for some datasets. We observe
the same behavior in Deng & Zhang (2020); Jiao al. (211)) 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 KG- Explainer performing better than base KGEs to some extent.
21


Reviews:
[{"review_id": "jEoBLtK1GU", "reviewer": "Reviewer_PA5a", "summary": "The paper presents KGExplainer, a model-agnostic framework designed to provide path-based explanations for knowledge graph completion. The approach leverages a perturbation-based greedy search algorithm to identify the most important synergistic paths that contribute to the prediction of facts within a knowledge graph. The method is grounded in the insight that predictions are often supported by multiple interconnected reasoning chains. To evaluate these explanations, KGExplainer uses a distilled evaluator derived from the target knowledge graph embedding model, ensuring the explanations maintain high fidelity.", "questions": "Please see weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Model-Agnostic Approach. KGExplainer is designed to work with different KGE models, making it a versatile tool for enhancing explainability across various KGC tasks.\n- Theoretical Justification. The paper provides a solid theoretical foundation for the proposed framework, in terms of the scalability of KGExplainer.", "weaknesses": "- Limited Scalability Experiments and Discussion. While the paper mentions that KGExplainer can handle large KGs with small average degrees, there is limited discussion on how the framework scales with increasing graph size and complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IgKOR3LZ25", "reviewer": "Reviewer_wvH8", "summary": "This paper presents KGExplainer, a framework for generating explanations for knowledge graph completion (KGC) predictions by identifying synergistic paths. The work introduces a method to identify multiple synergistic paths for explaining KGC model predictions, moving beyond single-path approaches used in prior work. The authors develop a distillation-based evaluator for assessing explanation quality, providing a quantitative way to measure the effectiveness of the generated explanations. The technical core of the approach is a greedy search algorithm for finding explanatory paths within local subgraph structures. While the framework shows promise in generating more comprehensive explanations than existing methods, there are several aspects that warrant further investigation and improvement.", "questions": "1. You state that 'a fact is usually determined by the synergy of multiple reasoning chains', could you provide empirical evidence or analysis showing what percentage of predictions actually require multiple paths versus being explainable by a single path?\n2. In Section 4.4 you provide theoretical complexity analysis showing the method scales with path length L and number N rather than graph size. However, the empirical results in Table 4 show significant runtime differences between datasets. Could you explain this apparent discrepancy and provide more details about what factors dominate the practical runtime?\n3. Regarding the human evaluation showing 83.3% accuracy, could you provide more details about a) The criteria given to participants for judging explanation quality; b) Whether participants were shown the explanations simultaneously or sequentially; and c) If the 20 test cases were randomly selected or curated?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper demonstrates the importance of explanations in knowledge graph completion through concrete examples, such as competitor analysis (Alibaba-JD.com case) and drug interaction prediction (Acetaminophen-Warfarin case) shown in Figure 1. These examples clearly illustrate why single-path explanations are insufficient for complex predictions.\n2. The paper introduces a novel distillation-based evaluator that achieves comparable performance to the original KGE models, as evidenced by the results in Table 1. For instance, KGExp-RotatE achieves 17.33% Hits@1 on OGB-biokg compared to RotatE's 17.12%, showing the evaluator's reliability.\n3. The proposed method shows consistent improvements across multiple datasets, and the method is theoretically proven scalable (in Section 4.4, computation complexity is shown depend mainly on local parameters such as path length and number of paths rather than total graph size.)", "weaknesses": "1. While the paper introduces the concept of \"synergistic paths\" as a key contribution, it lacks rigorous theoretical analysis of what constitutes meaningful synergy between paths. The paper never formally defines what makes paths truly synergistic versus simply having multiple independent supporting paths. Besides, the greedy search strategy for finding synergistic paths lacks theoretical guarantees about its optimality. I recommend that the authors should formalize the concept of path synergy, perhaps through information theoretic measures that capture the mutual information between paths, or through formal analysis of how different path combinations contribute to prediction confidence. This would strengthen the theoretical foundation of the work beyond just empirical results.\n2. The experimental evaluation doesn't sufficiently demonstrate real-world usefulness of the explanations. The human evaluation, while showing 83.3% accuracy, involved only academic participants (students/professors) rather than domain experts or real end users who would actually use such systems. The experiments lack evaluation of how these explanations help in practical tasks like error analysis or model debugging. There are no case studies demonstrating how synergistic paths provide better insights than single paths in real applications. To properly validate the method's practical value, the authors may conduct user studies with domain experts (like biomedical researchers for OGB-biokg), include case studies showing how the explanations help debug model errors, analyze explanation patterns for both correct and incorrect predictions, and demonstrate benefits through concrete application scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sU4q3gY1pf", "reviewer": "Reviewer_c8rP", "summary": "The paper introduces KGExplainer, a novel model-agnostic framework for generating explainable knowledge graph completion (KGC) by identifying synergistic path-based explanations. This approach leverages a perturbation-based greedy search to identify influential paths and an evaluator distilled from the target knowledge graph embedding (KGE) model to assess the fidelity of explanations. KGExplainer is evaluated against state-of-the-art explainability baselines, demonstrating significant improvements in both faithfulness and explainability metrics. Experimental results on multiple benchmark datasets reveal KGExplainer's strong human-interpretability and competitive performance in preserving predictive accuracy.", "questions": "1. How to assess the quality of the proposed evaluator? Can you provide some experiments to demonstrate its effectiveness in evaluating the fidelity of explanations? \n\nMoreover, how does the architectures of the evaluator, like other subgraph-based method: Grail [1], affect the performance and robustness of evaluation? Will the evaluation results be consistent across different evaluators?\n\nLast, what is the input to the evaluator? Is it purely the graph structures or the embeddings are initialized with the pre-trained KGE models?\n\n2. How the re-training stage of the KGE model affects the overall efficiency of the proposed method? It should be discussed in the complexity analysis section and also included in the cost time analysis of Table 4.\n\n3. In experiments, how is the predictive performance of the \"distilled model\" evaluated? Is it predicted by the embeddings from re-trained KGE model or inputting subgraphs into the evaluator?\n\n4. How does the hop of enclosed subgraphs affect the performance of the proposed method? The author only set the hop to 2. However, in FB15k-237, the average length of the shortest path connecting head and tail is around 3, which means the hop of 2 might not be enough to capture the long-range dependencies.\n\n[1] Teru, K., Denis, E., & Hamilton, W. (2020, November). Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning (pp. 9448-9457). PMLR.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. KGExplainer introduces a model-agnostic approach to generate explainable paths for KGE-based models, which can be applied to various KGC models and datasets.\n2. The paper proposes a distilled evaluator to quantitatively assess explanation fidelity, ensuring that the explanations are not only accurate but also reflective of the underlying KGE model's decision-making process.\n3. The framework is evaluated on various KGC models and datasets, showing competitive results across different setups and substantial improvements in both F1@1 and Recall@1 metrics, particularly outperforming other path-based methods.", "weaknesses": "1. Limited scopes: The proposed method only focuses on the KGE-based methods, while many advanced KGC methods are based on graph neural networks (GNNs) [1] or other deep learning architectures. It would be beneficial to extend the evaluation to these models to provide a more comprehensive comparison. Besides, it only focuses on path-based explanations, while other high-order structures like subgraph patterns or graph motifs could also be considered.\n\n2. Efficiency concerns: The proposed method requires retraining the KGE model to identify the key paths, which could be computationally expensive. Even though the greedy search is efficient, the overall complexity of the method might hinder its scalability to large-scale knowledge graphs.\n\n3. Evaluation metrics: The paper proposes a novel evaluator to assess the fidelity of explanations. However, the quality of the evaluator is not dissected in detail, making it questionable whether the evaluator can accurately capture the KGE model's decision-making process. A more in-depth analysis of the evaluator's performance and its robustness to different KGE models would strengthen the paper's claims.\n\n4. Some experiment settings are not clearly described.\n\n[1] Galkin, M., Yuan, X., Mostafa, H., Tang, J., & Zhu, Z. Towards Foundation Models for Knowledge Graph Reasoning. In The Twelfth International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)