Towards Synergistic Path-based Explanations for Knowledge Graph Completion: Exploration and Evaluation

Thank you for your thoughtful and encouraging review. The point-to-point answer is provided below.

Q1. Provide more experiments to assess the quality of the proposed evaluator.

Response: We evaluate the quality of the proposed evaluator from two perspectives: (1) the fidelity of its predictive performance for potential facts, and (2) its recovery effectiveness compared to base KGEs. As shown in Table 1, KGExplainer demonstrates comparable predictive accuracy and strong recovery performance relative to target KGEs. These results provide experimental evidence that KGExplainer effectively captures the decision-making process of the KGE model.

Table 1. The predictive performance and recovery rate of the distilled evaluator.

Q2. How does the architectures of the evaluator affect the performance and robustness of evaluation? Will the evaluation results be consistent across different evaluators?

Response: The evaluators built on different architectures demonstrate robustness. And the evaluation results of evaluators distilled from different base KGEs exist 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-rr dataset, and then assess these explanations using evaluators distilled from different teacher KGEs. Table 2 reveals two key findings:

1. The evaluator distilled from RotatE achieves the best performance, with differences among evaluators due to variations in their predictive abilities.
2. Evaluators based on R-GAT and GraiL (which applies R-GCN on subgraphs) 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 2. The explainable performance of various evaluators on the Family-rr dataset.

Q3. How is the predictive performance of the "distilled model" evaluated? What is the input to the evaluator?

Response:

1. To assess the evaluator’s predictive performance, we use tail entity prediction for queries of the form <$h, r, ?$>. Specifically, for each candidate entity $c$, we input the local structure surrounding the query <$h, r, c$> into the evaluator to obtain a score. This allows us to rank the correct tail entity and compute the hit-rate performance across test samples.
2. During both the distillation and evaluation phases, we rely solely on local graph structures with semantic relations as input for the evaluator to avoid potential data leakage from embeddings pre-initialized with KGE models.

We appreciate your detailed review and constructive suggestions. We address the concerns and questions below.

Q1. Formalizing the concept of path synergy and providing empirical evidence or analysis showing what percentage of predictions actually require multiple paths.

Response: (1) Formalizing the concept of synergistic paths from an information-theoretic perspective.

Let:

• <$h, r, t$> denotes a triple, respectively, forming the target prediction.
• $\mathcal{P}=\{p_1,p_2,\ldots,p_n \}$ be a set of paths between $h$ and $t$.

Two variables are considered synergic if their combined effect is greater than the sum of their individual effects [1]. We aim to quantify the synergy among paths in $\mathcal{P}$.

1. Quantifies the information a single path $p_i$ contributes to the prediction $t$:$I(t; p_i) = H(t) - H(t | p_i),$ where $H(t)$ is the entropy of $t$, and $H(t|p_i)$ is the conditional entropy of $t$ given $p_i$.
2. Measures the information provided by a subset of paths $\mathcal{P}\_{synergy} \subset \mathcal{P}$: $I(t; \mathcal{P}\_{synergy}) = H(t) - H(t | \mathcal{P}\_{synergy}).$
3. The paths in $\mathcal{P}\_{synergy}$ are synergistic if: $I(t;\mathcal{P}\_{synergy}) > \sum_{p_i \in \mathcal{P}\_{synergy}}I(t; p_i),$ meaning the collective information from $\mathcal{P}\_{synergy}$ exceeds the sum of individual contributions.
4. The optimal subset $\mathcal{P}\_{synergy}^\*$ maximizes the synergistic mutual information gain: $\mathcal{P}\_{synergy}^\* = \arg\max_{\mathcal{P}' \subseteq \mathcal{P}} \left( I(t; \mathcal{P}')-\sum_{p_i \in \mathcal{P}'} I(t; p_i) \right).$

(2) Quantifying mutual information among synergistic paths in KGs is often complex and highly context-dependent, making it challenging to determine the proportion of predictions requiring multiple paths. In human evaluations of Family-rr, KGExplainer demonstrated superior performance in approximately 80% of cases compared to single-path exploration methods, suggesting experimental evidence of the importance of multiple paths. Overall, this is an intriguing topic for further investigation, which we plan to explore in greater depth.

[1] Barrera, N. P. (2005). Principles: mechanisms and modeling of synergism in cellular responses. Trends in Pharmacological Sciences.

Q2. Explain the significant runtime differences between datasets and provide more details about what factors dominate the practical runtime.

Response: The substantial differences in runtime across datasets can largely be attributed to variations in these local parameters. Table 1 presents an analysis of the average node degree, path length, and path number within the enclosing subgraphs. Our results show a strong positive correlation between the number of paths and computation time, which aligns closely with our theoretical analysis.

Table 1. The distribution of degree, path length, and path number over various KGs.

Specifically, 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$. We have discussed the complexity of the greedy search is largely determined by local parameters. The complexity of the re-training stage for different base KGEs, which is dominated by the size of subgraph $g$ (i.e., $O(\frac{LN|\mathcal{V}|}{|\mathcal{E}|})$ discussed in Section 4.4), the embedding dimension $d$, and the size of negative samples $n$. We can analyze the efficiency of base KGEs as follows:

• In TransE, DistMult, and RotatE, the computational efficiency of each fact within $g$ is $O((n+1)\*d)$. Therefore, the overall complexity is $O(\frac{LN|\mathcal{V}|}{|\mathcal{E}|}\*(n+1)\*d)$, where $L$ is the maximum path length, $N$ denotes the path number.

In conclusion, the practical runtime largely depends on the local parameters of the knowledge graphs.

Q3. Provide more details about the human evaluation.

Response: Let us address your concerns point by point:

a) We give two bases for judgment as a 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.

b) The results from different models are presented to the participants simultaneously.

c) We randomly selected 20 samples from the test set of Family-rr for participants to evaluate.

Once again, we appreciate your detailed feedback and suggestions, which have strengthened the presentation and robustness of our work.

Thank you for your detailed review and constructive suggestions. We provide a detailed discussion of the reviewer's concerns.

1. Limited discussion on how the framework scales with increasing graph size and complexity.

Response: To improve scalability for larger KGs, we can adjust the local enclosing subgraph size (e.g., reducing from a 2-hop to a 1-hop subgraph) to decrease path length and path count. Table 1 presents the distribution of node degree, path length, path number, and computation time across different subgraph scales over OGB-biokg, revealing a strong positive correlation between them, consistent with our theoretical analysis.

Table 1. The distribution of average degree, path length, path number, and computation time over various subgraph scales.

Specifically, 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 (such as the maximum length of paths $L$). The re-training cost, on the other hand, depends on the underlying KGE model, which is dominated by the size of subgraph $g$ (i.e., $O(\frac{LN|\mathcal{V}|}{|\mathcal{E}|})$ discussed in Section 4.4), the embedding dimension $d$, and the size of negative samples $n$. Thus we can analyze the efficiency of base KGEs as follows:

• In TransE, DistMult, and RotatE, the computational efficiency of each fact within $g$ is $O((n+1)\*d)$. Therefore, the overall complexity is $O(\frac{LN|\mathcal{V}|}{|\mathcal{E}|}\*(n+1)\*d)$, where $L$ is the maximum path length, $N$ denotes the path number.

In conclusion, the complexity of KGExplainer is driven primarily by local parameters—such as path length $L$, path number $N$, and average degree—rather than the overall size of the knowledge graph (KG).

Thank you again for your valuable insights, which will help us further strengthen the presentation and impact of our work.