Temporal Knowledge Graph Completion (TKGC) uses the facts available in a TKG to make it less incomplete. Stateof-the-art Graph Neural Networks (GNNs) for TKGC are black boxes that provide results without explanations. Existing explanation methods for static KGC are dificult to transfer to TKGC as they do not capture the temporal properties and likely generate large explanation graphs. As the chronological order of facts is relevant for TKGC, we infuse this characteristic into the explanation subgraphs. In this work, we (i) propose a regulation method that incentivizes a chronological order in the explanations and (ii) investigate the efect of the chronological regulation on the explanations of two state-of-theart TKGC models. Our results show that in most scenarios, the chronological regulation can improve explanations of TKGCs. For example, we observe an improvement of the fidelity characterization score by up to 2% and significant improvements for small explanations.
Temporal Knowledge Graph Completion
Interpolation Extrapolation
Timestamps Dependent
based Timestamps-specific functions-based Deep Learning-based
Angela Merkel
Consult 2014-05-01
0.7
Consult
path-based explanations used for XAI of static KG approaches [
A Knowledge Graph (KG) stores facts as triples (, , ), where ∈ ℰ is called the subject, ∈ ℛ the relation, and ∈ ℰ the object. ℰ and ℛ are finite sets of entity and relation identifiers, respectively.
A Temporal Knowledge Graph (TKG) is a KG extended by the temporal information about the facts. is a specific point in time (e.g. 05-11-2014) from a finite set of timestamps .
Facts in a TKG are represented as quadruples (, , , ), with ∈ adding time information to the fact.
Temporal Knowledge Graph Completion (TKGC) is about adding missing quadruples to a TKG. TKGC models predict a missing entity of a given query = (, , ?, ) or = (?, , , ), where , , ? ∈ ℰ , ∈ ℛ, and ∈ .
neighborhood. updated node features x^ as
are a type of neural network designed to process graphs as input.
The core concept of a GNN is message-passing, first introduced by Gilmer et al. [
︂)
∈
(1)
where message function and update function are trainable functions and ⊕ denotes a nonparametric
operation such as sum, mean, or maximum [
In a GNN, this message passing scheme is typically repeated layerwise and can include edge features e for each edge connecting node and . Two commonly used GNNs are the Graph Attention Networks (GATs) and the Graph Convolution Networks (GCNs).
We focus on post-hoc explanations, which are generated for a target model ℳ. We utilize a perturbationbased method that modifies the model’s input by masking to identify minimal subgraphs that explain the model’s prediction.
One of the initial and well-known perturbation-based GNN explainer models for non-temporal KGs is
the GNNExplainer [
XAI aims to help humans understand the predictions of neural networks and other AI models, which are normally considered black boxes. Given a target model ℳ, the goal of XAI is to provide a humanunderstandable textual or visual explanation of ℳ’s predictions.
Perturbation-based instance-level explanation methods investigate the behavior of the target model’s predictions on varying inputs to identify a subgraph relevant to the prediction, which then serves as an explanation.
A perturbation-based instance-level explanation should reflect the model’s prediction, i. e., the
explanation graph should only contain information important for the prediction. Similarly, the result
should change if crucial information is removed from the input. At the same time, an explanation
should be suficiently sparse to be interpretable by a human [
The GNNExplainer proposed by Ying et al. [
Recently, path-based explanations for KGC have gained attention [
While TKGC and XAI are well-researched subjects, there is still little literature on using XAI in TKGC.
Some works combine TKGC and TKGC Explainability in a single model, also known as self-interpretable
models. Examples of self-interpretable models are xERTE [
The perturbation-based explainer Temporal Motifs Explainer (TempME) proposed by Chen et al. [
Visits 2024-12-27
Charlie
He et al. [
The existing TKGC explainers fail to incorporate the temporal aspect suficiently, address the unique challenges posed by the TKG graph characteristics, or tailor explanations to meet user requirements for time-based interpretations.
GNN approaches for TKGC learn how information evolves over time to predict new facts. Since the
temporal order of facts conveys information, models process the graph in chronological order rather than
random order to leverage the causal relationships and temporal dependencies [
Inspired by how path-based explanations incorporate connections between query entities in the
explanations [
A chronological path is a path in a graph with chronologically ascending or descending timestamps along its edges. For any two consecutive edges on a chronologically ascending path, the timestamp of the second edge is greater than or equal to the timestamp of the first edge. Chronological descending is defined analogously. Given a TKG and the target models predicted entity ′ for query = (, , ?, ) with entity , relation and timestamp , we denote (,′) as a chronological path from to ′. The set of all chronological paths between and ′ is defined as
() (,′) = {(,′) | ≤ max}, (3) where max is the maximal length of the chronological paths.
We set max = 3 for all experiments as longer paths may be less relevant, and most TKG models only consider a maximum of 3 hops around a query.
Chronological regulation rewards edges on chronological paths between the query’s subject and the target model’s predicted object ′ and might penalize edges that are not. We propose two methods to implement chronological regulation.
⎧
⎪⎪⎩0,
otherwise
Loss Regulation Given all chronological paths (,′) from to the target model’s prediction ′,
chronological regulation can be applied to the edge mask ( ) by defining a regulation loss that
measures the distance between ( ) and the optimal edge mask regarding the chronological paths
(loss_reg) ∈ [
ℓreg( ( ), (loss_reg)) = mean({1, ..., }), = · | ( ) − (loss_reg)| (5) We use a hyperparameter , to scale the strength of the regulation.
Gradient Regulation The second regulation method directly applies the regulation to the gradients. (grad_reg) that rewards or penalizes the gradients The chronological paths are used to create a function of the mask. This function is similar to the one used in Eq. 4, but with hyperparameter scaling the maximum reward and penalty.
⎧ (︂ ⎪ (grad_reg) = ⎨⎪ ⎪⎪⎩− ,
log (||min) )︂ 1 − · log (max) , if (, , , ) ∈ ∈ (,′), otherwise Let Θ be the edge mask parameters and ∇ℓ(Θ) the computed gradients. To regulate the edge mask, before doing gradient descent, the computed gradient is subtracted by (grad_reg). This regulation increases the gradient for edges on a chronological path and decreases it otherwise.
∇ℓ(Θ) = ∇ℓ(Θ) − (grad_reg) Note that we do not need a scaling parameter as in the previous method since we can scale (grad_reg) directly with .
Commonly used real-world benchmark datasets for TKGC are subsets of ICEWS1 and WIKIDATA [
ICEWS14 contains socio-political events. The entities are, for example, countries, institutions, or
persons; the relations are predicates like Consult or Make statement, and the timestamps are the dates
on which the event occurred [
WIKIDATA11K contains entities such as historical figures, places, and artifacts, connected by relations
like Was born in or Founded. The characteristics of both datasets can be found in App. A Tab. 2.
In this work, we use two state-of-the-art TKGC models for predictions. TARGCN [
Following [
Fidelity [
∖ = ), || ∈ − = 1 − 1 ∑︁ 1(^
= )
|| ∈
If fid − is close to 0, the provided explanation is suficient , and if fid + is close to 1, the explanation is
necessary. An explanation should be suficient and necessary. A metric to combine fid + and fid − is the
charact score [
+ + − ℎ = ifd++ + 1− fid− − , with + + − = 1 We give equal weight to fid + and fid .
Sparsity is also an important pro p−erty of explanation graphs to provide human-understandable explanations as TKGs often have a high avg. node degree and high information density due to the additional temporal information compared to static KGs. We define the sparsity of an explanation subgraph as = 1 ∑︁ (︂ =0 1
(| | + 1) )︂ , − (| | + 1) (8) (9) (10) (11) where | | denotes the number of edges in the explanation subgraph and | | the number of edges in the computation graph. Note that we are taking the of the number of edges because we want to focus on explanations that are as small as possible. Reducing an already small explanation has a greater efect on the sparsity than reducing a large explanation.
Sparse-Fidelity Finally, we propose a new combined metric based on the charact score and sparsity. As with the charact score, we calculate the harmonic mean between charact and sparsity.
+ charact + sparsity = , with + = 1 With = = 0.5 we give equal weight to charact and sparsity.
We use the GNNExplainer without temporal edge mask regularization as the baseline to compare the
proposed temporal regulation methods. Although the GNNExplainer was originally developed for
static KGs only, it can be adapted to the temporal setting by extending the edge mask to the temporal
adjacency matrix. The use of this inflated mask ∈ [
This chapter provides the evaluation results of the GNNExplainer w. and w/o. temporal regulation on TKGC. We apply the GNNExplainer to the two target models TARGCN and T-GAP. Details about the hyperparameter-tuning can be found in App. B. Tab. 1 shows an overview of the results using the edge mask and the proposed edge mask regulation methods loss and gradient regulation. We report all metrics with a threshold of 100 edges for each mask.2
We observe that the explanations for the predictions of the target model TARGCN achieve notably better scores compared to those for T-GAP. Using the target model TARGCN, the proposed regulation methods can outperform the edge mask, with loss regulation providing the best results. In contrast, the best results for the target model T-GAP are obtained with gradient regulation, while loss regulation cannot improve upon the baseline. Since the sparsity of the explanations remains constant at a fixed threshold for the edge mask, we observe the same values with and without regulation.
evolution of masks on one randomly selected ICEWS14 quadruple to see how the regulation methods influence edge mask learning.
The mask history using TARGCN as the target model can be seen in Fig. 3. We highlighted two edges for better visualization: one on a chronological path (black) and one that is not (red). When using loss regulation, an initial increase in the mask value can be observed for the edge not on a chronological path, followed by a steep decrease after about 60 epochs. The explainer seems to have found a minimum for the loss after a few epochs. An instant decrease of the edge mask for edges not lying on a chronological path can be observed using the gradient regulation. Since this method does not minimize a loss, the influence of the regulation is immediately apparent, which generally seems to lead to a more precise separation of important and unimportant edges. Please note that this behavior does not apply to all 2The source code and target model checkpoints for our experiments are publicly available at https://anonymous.4open.science/r/ExplainableTKGC-1908/ on chr. path not on chr. path
Loss-Regulation 10 30 50 70 90
Threshold 10 30 50 70 90
Threshold edges on a non-chronological path. If we look at the same sample with the target model T-GAP, which can be found in App. D Fig. 5, we see that using the threshold has already removed all edges that the explainer considers unimportant. It can be seen that, compared to the target model TARGCN, the loss regulation seems not to influence the edge weights. For the gradient regulation, some edges are influenced.
Edge Masks Across Diferent Thresholds: The previous results show explanations with an edge mask threshold of 100. However, since we are not only interested in the fidelity of the explanation but also in achieving a high degree of sparsity, we have also evaluated low thresholds for the masks. The lower part of Tab. 1 reports the results of the GNNExplainer for both target models using the edge mask with and without the two regulations with the best threshold regarding the SparseFid score. We observe that the best threshold for all methods is below 100. For the target model TARGCN on the ICEWS14 dataset, the edge mask can achieve the highest SparseFid score. On the WIKIDATA11K dataset, loss regulation is still the best method. Gradient regulation also remains the best method for the target model T-GAP.
In the following, we look at the results for the target models i) TARGCN and ii) T-GAP in detail. i) TARGCN The comparison of loss and gradient regulation to the baseline on the ICEWS14 dataset in Fig. 4 shows a similar trend of the scores depending on the threshold. However, the baseline can provide better results for lower thresholds. This is also indicated by the smaller optimal threshold of the baseline compared to the regulation methods. Loss and gradient regulation can only improve the baseline with thresholds of 50 or higher. Gradient regulation, in particular, struggles with high fidelity for very small thresholds.
The results on the WIKIDATA11K dataset show a significant improvement of the baseline for small thresholds using loss and gradient regulation, as can be observed in Fig. 6a in the appendix. This results in the optimal threshold being improved from 30 to 20 for both regulation methods. The charact score of the loss regulation is superior to the baseline for every threshold. Thus, the charact score of the loss regulation at a threshold of 30 is already above the baseline score with the maximum threshold of 100. Gradient regulation, on the other hand, can outperform the baseline for small thresholds. Above a threshold of 40, the improvements are minimal. ii) T-GAP Since the results of the GNNExplainer for the target model T-GAP using the loss regulation for diferent thresholds show no diference to the baseline performance, we only report the results of the edge and node mask and the gradient regulation.
We report the results of T-GAP in the appendix in Fig. 6. In comparison to the baseline, the gradient regulation can only achieve very small improvements for a threshold of 100 on ICEWS14, as can be seen in Tab. 1. However, if we look at smaller explanations in Fig. 6b, we see an improvement in the charact score when using the gradient regulation. For a threshold of 30 to 60, a noticeable improvement can be observed compared to the baseline. The optimal threshold can be decreased to 80 using gradient regulation.
A very similar behavior can be found in the results on the WIKIDATA11K dataset in Fig. 6c. The optimal threshold for the edge mask without regulation is 70 but can be reduced to 50 using gradient regulation.
Our results show improvements through temporal regulation for all models on all datasets in most scenarios. Often, we observe improvements through both regulation methods, or at least through one of them.
With an edge mask threshold of 100, the GNNExplainer can obtain the best charact score through loss regulation for TARGCN and gradient regulation for T-GAP. While the GNNExplainer for TARGCN can achieve an improvement with the gradient regulation compared to the edge mask without regulation, the loss regulation for T-GAP had no noticeable influence on the quality of the explanations according to the metrics used.
The explainer uses a significantly smaller edge mask for TARGCN than for T-GAP, which may be easier to optimize. This is because message passing is only performed for a sampled temporal 1-hop neighborhood of the subject node in this model. Since TARGCN limits this neighborhood to a maximum of 100 edges, the edge mask includes, at most, 100 parameters to optimize. In contrast, with T-GAP, message passing is performed for each edge in the graph, which means that the number of parameters in the edge mask is significantly larger than with TARGCN. This might cause the loss regulation to have only a small impact on explanations of T-GAP’s predictions.
We can observe that the explanation quality seems to depend highly on the target model to be explained. Tab. 1 shows that TARGCN explanations are considerably better than explanations for T-GAP. This might be caused by i) the larger neighborhood context of T-GAP and the resulting complex inference of T-GAP compared to TARGCN ; ii) a diference in the TKGC prediction quality as TARGCN performs better than T-GAP on both datasets,3 which makes explanations more dificult.
Furthermore, the optimal size of the edge mask seems to depend heavily on the underlying dataset and target model. The explainer consistently achieves a smaller optimal explanation threshold for TARGCN than for T-GAP. One reason could be that T-GAP considers the 3-hop neighborhood around the query node for its prediction, while TARGCN only considers the direct neighborhood. Therefore, T-GAP generally requires more edges to provide a reliable prediction than TARGCN. This is further 3With the original source code, we reproduced the original experiments and achieved TKGC scores close the ones publications with the models. TARGCN: 0.606 MRR on ICEWS14, 0.715 MRR on WIKIDATA11K; T-GAP: 0.56 MRR on ICEWS14, 0.663 MRR on WIKIDATA11K. supported by the observation of the charact score curve in relation to the threshold shown in Fig. 4 and Fig. 6b in the appendix.
We evaluated the models following common methods and standards in XKGC and introduced a new metric to better reflect the explanations’ size. A human evaluation to verify a model’s capabilities in realworld scenarios is not common in XKGC tue to open challenges, especially with TKGs, as i) the standard KGC benchmark datasets require human experts in the respective domains, ii) no commonly accepted dataset for X(T)KGC exists, iii) existing state-of-the-art TKGC models require large subgraphs to make TKGC predictions. Even though our chronological regulation can reduce the size of explanations, a human evaluation still poses significant challenges and would be an interesting topic for future work.
In this work, we address the explainability of GNN-based TKGC models. We implement a baseline for GNN-based TKGC explanations using non-temporal GNN explainers and report the explanation quality according to established metrics. Furthermore, we proposed a regulation method that incentivizes a chronological order in the explanations to improve explanations over TKCs. We see this in improved explainability scores in most scenarios across models and datasets, e. g., with fidelity characterization scores increased by up to 2% compared to the baselines. We observe that the regulation methods can reduce the size of the explanation graph while maintaining the same explanation quality according to explainability metrics in most scenarios.
This work was supported by the Research Council of Norway through its Centres of Excellence scheme, Integreat – Norwegian Centre for Knowledge-driven Machine Learning, project number 332645.
We used ChatGPT and Grammarly to check grammar and spelling and to make minor rephrasings for improved clarity. All changes were reviewed by us, and we take full responsibility for the content of this publication.
The proposed chronological regulation methods add new hyperparameters to the GNNExplainer.
For all other parameters added for the chronological regulation, we use grid-search hyperparameter tuning with the parameters reported in Tab. 3 on 1000 samples for TARGCN and 500 for T-GAP. Note that it is also possible to optimize the hyperparameters for each sample individually since the GNNExplainer has to be trained separately for each sample by default. The best hyperparameters are determined by the charact score. However, as this can be artificially inflated with a very large explanation, we limit the explanation size to 100 edges. Except for the number of training epochs (200 for TARGCN and 100 for T-GAP), we do not change any default hyperparameters of the GNNExplainer.
GCN layer to aggregate graph neighborhood information. For every query = (, , ?, ), the model samples the temporal neighborhood ¯ (, ) ⊆ (, ) of the query node at time . Then, a GCN layer is used to aggregate information of ¯ (, ) to encode the time-aware representation of entity at time , by combining time-invariant representations of relation , entity and implicit time diference information from the subset of all temporal neighbors.
h(,) = 1
∑︁ ¯ | (,)| (,)∈¯ (,)
W(h(,)||h), where h denotes the time-invariant embedding of relation and h(,) the time-aware entity embedding ¯ h(,) for (, ) ∈ (,).
For each possible candidate object ′, a simplified time-aware representation is compared to using
DistMult decoding [
To apply the edge mask to TARGCN, we need to adjust Eq. 12 as follows: h(,) = 1
∑︁ ¯ | (,)| (,)∈¯ (,)
W((h(,)||h) ⊙ ( )(,)), (12) (13) where ( )(,) is the sigmoid applied edge mask parameter for the edge connecting with at time . masks a feature that is based on the time-aware entity embedding and the time-invariable relation embedding .
Temporal GNN with Attention Propagation (T-GAP)
[
m = W(h + p + |Δ|), embedding. where h denotes the node features, p the relation embedding, and |Δ| a temporal displacement The implementation of the edge mask in T-GAP is similar to TARGCN. The message passing from Eq. 14 is modified as follows: m = W ︁( (h + p + |Δ|) ⊙ ( ) , ︁) (14) (15) where the edge mask is multiplied with each of the messages between node and node .
Fig. 6 shows the performance of the explainer with and without regulation at diferent thresholds. on chr. path
not on chr. path without regulation for a random sample from ICEWS14.
We ran the experiments on our GPU cluster with Nvidia A40 GPUs (older GPUs with less VRAM, e. g., Nvidia Tesla cards, are suficient, too). For both target model training and the hyperparameter tuning, we used approx. 450h GPU hours. Note that our approach does not substantially increase the computation time of the existing GNNExplainer. We evaluated our approaches on existing TKGC datasets for comparability. These datasets were not developed for XAI and, therefore, contain large test sets that cause the runtime of our experiments. Furthermore, the large computation times are related to the target model T-GAP and are thus independent of our proposed approach.
1.0 0.8 k sa0.6 egd0.4 0.2 0.0 M
M
M E
E
E 1.0 0.8 charact fid + 0.78 charact fid + 10 30 charact fid + SparseFid charact 30
50 70 Threshold 90 10 30
50 70 Threshold
90 charact fid + charact {0.05, 0.1, 0.2, 0.4, 0.8} {0.0, 0.33, 0.66, 1.0} 0.8 0.0