DGExplainer: Explaining Dynamic Graph Neural Networks via Relevance Back-propagation

1 Introduction

Dynamic GNNs have achieved significant success in practical applications such as social network analysis [Zhu et al., 2016], transportation forecasting [Gui et al., 2020], and pandemic forecasting [Kapoor et al., 2020]. However, since most of the dynamic GNNs [Ma et al., 2020; Li et al., 2017] are developed without interpretability, they are treated as black-boxes. Without understanding the underlying mechanisms behind their predictions, dynamic GNNs cannot be fully trusted, preventing their use in critical applications. In

→Appendix available at https://github.com/yezil3/DGExplainer IJCAI/blob/main/IJCAI appendix.pdf

Corresponding author.

(a) Traffic flow prediction.

Time

12:00 PM

1

3

15:00 PM

1

3

21:00 PM

1

3

2

2

2

Relevance

|

|

|

1.0

0.0

-1.0

(b) Explaining traffic-flow prediction of dynamic GNNs.

Figure 1: The diagram of the explanation task of dynamic GNNs on traffic flow data.

order to safely and trustworthily employ dynamic GNN models, it is important to provide both accurate predictions and human-understandable explanations.

Recent studies have extensively explored explanation techniques for static GNNs. These techniques include approximation-based methods [Baldassarre and Azizpour, 2019; Pope et al., 2019], which use gradients or surrogate functions to approximate the output of a local model. Perturbation-based approaches [Ying et al., 2019; Luo et al., 2020] explain static GNNs by masking specific features to observe their impact on the model's output. Gradient-based methods [Selvaraju et al., 2017] adopt the additive assumption of feature values or gradients to measure the importance of input features. Further relevant research on explaining static GNNs can be found in Appendix A.13. However, these methods overlook the critical temporal dimension crucial for explaining dynamic GNNs. Applying static-graph explanation frameworks to dynamic graphs yields discrete, snapshotbased explanations that ignore temporal context.

Explaining dynamic GNNs can be challenging. We illustrate this process in Figure 1. The prediction task, shown in Figure 1a, aims to forecast future traffic flows (denoted by dashed lines) at different locations based on historical observations (denoted by solid lines). This spatial-temporal data is modeled as a dynamic graph, represented in Figure 1b, where each graph snapshot records traffic flows at different time steps (e.g., 12:00 PM, 3:00 PM, and 9:00 PM). In each graph snapshot, a dashed line between two nodes indicates a commute between locations, and an arrow represents traffic flows, contributing to the prediction for the target location (denoted by a yellow triangle). The explanation task aims to determine the influence of other locations on the prediction of the target location. The polarity of the influence is denoted by the color of the arrows: blue indicates a positive correlation, while red indicates a negative correlation, with the darkness of the color indicating the strength of the influence. Dynamic graph data involves both temporal and spatial patterns, which dynamic GNNs capture using separate temporal and spatial modules. This makes explanation challenging, as it requires tracing how the input influences the output through these complex components.

To address this challenge, we propose DGExplainer (Dynamic Graph Neural Network Explainer). DGExplainer uses layer-wise relevance propagation (LRP), which was originally introduced for image classifiers [Bach et al., 2015]. LRP can assign relevance scores without the need for a surrogate model or additional optimization. Unlike methods that only consider individual nodes or edges, LRP evaluates sequences of edges or walks, making it especially well-suited for dynamic GNNs. Our framework operates in three main steps. First, DGExplainer decomposes the prediction of a dynamic GNN to determine how time-related modules contribute to that prediction, using relevance back-propagation. Second, it propagates relevance scores through the graph-related modules (e.g., a GCN) layer by layer at each time step to calculate the importance of input features. Finally, DGExplainer aggregates the relevance scores from both steps to produce the final relevance of the node features. The contributions of our work are as follows:

• The proposed method explains the predictions of dynamic graph neural networks, marking one of the pioneering efforts to tackle this challenge.
• This paper is the first to derive LRP for time-varying modules. These hand-derived derivations are essential as they serve as a reference for adjusting or writing code when the provided functions fail, and adaptations are needed.
• Experimental results across six datasets and three quantitative metrics show that DGExplainer provides faithful explanations. Furthermore, qualitative analysis indicates

that DGExplainer outperforms other baseline methods in effectively explaining dynamic GNNs.

2 ProblemDefinition

This paper solves the problem of explaining dynamic GNNs by computing the relevances of input features. The proposed method first redistributes the prediction from the last layer to the relevance of hidden representations. Then, we use LRP to back-propagate the relevances through time-related and graph-related modules, finally reaching the input layer to obtain the relevances of input features of each node.

We study a series of input graphs G = ¶Xt↪ At♦Tt=1 , where T is the length of the sequence. Each graph at time t, Gt = ¶Xt↪At♦, consists of a feature matrix Xt ↑ RN→D and an adjacency matrix At ↑ RN→N . Here, N = ♣Vt♣ denotes the number of nodes, and D is the feature dimension. The feature vector for node i at time t is xit = (X(i↪:) t )↑ ↑ RD , which corresponds to the i-th row of Xt. Without loss of generality, A(i↪j) denotes the entry at the i-th row and j-th column of the adjacency matrix A, and x(i) denotes the i-th entry of the vector x. The relevance of an element k, which can be a node, an edge, a feature, etc., is represented by Rk. Additionally, Rk1↓k2 denotes the relevance of k1 distributed from k2. The problem of explaining dynamic GNNs involves identifying the subgraph within G, which consists of nodes and edges that are most important at a specific time step t, given a dynamic GNN model f(G).

3 Preliminaries

In this section, we present the preliminaries relevant to our proposed method. We begin with an overview of dynamic GNNs in Section 3.1, followed by an introduction to layerwise relevance propagation in Section 3.3.

3.1 Dynamic Graph Neural Networks

Dynamic GNNs [Skarding et al., 2021; Zhang et al., 2022] take a sequence of graphs as input and output representations of topology, nodes, and/or edges. A notable approach involves co-training a GNN with a recurrent neural network (RNN), referred to as a GNN-RNN model. Examples include GCN-GRU [Zhao et al., 2019], ChebNet-LSTM [Seo et al., 2018], and GCN-RNN [Pareja et al., 2020]. Detailed related work about dynamic GNNs can be found in Appendix A.13. Despite the introduction of various methods, recent approaches still do not consistently outperform the GCN-GRU model [Pareja et al., 2020]. Therefore, in this work, we choose to use the GCN-GRU model as the basis for elaborating our method. In addition to explaining the GCN-GRU model, we also apply DGExplainer to other dynamic GNNs that utilize different GNN or RNN architectures. Detailed results of these experiments can be found in Appendix A.7.

3.2 The GCN-GRUModel-Forward Pass

In the GCN-GRU model, the GCN module first encodes input features of the current time step, capturing dependencies between nodes. These encoded features are then passed to the GRU module, which captures temporal dependencies across different time steps. Below, we outline the forward process of the GCN-GRU.

(a) The Graph Convolutional Network (GCN) module: GCNs represent a node using local information from its surrounding neighbors [Kipf and Welling, 2016]. This graph convolution process is formulated as follows:

Here, Vt := ˜D↔ 12 t ˜At ˜D↔ 12 t is the normalized adjacency matrix, where ˜At =At+IN and ˜Dt =Dt+IN. ThematrixDt is the degree matrix, defined as D(i↪i) t = ∑j A(i↪j) t , and IN is an identity matrix of size N. The output at the l-th layer is denoted as F(l) t , with the initial layer output F(0) t = Xt. Assuming the GCN has L layers, the final node representation at time step t, which contains the graph structural information, is denoted as ˆXt = F(L) t . The GCN-encoded features from all time steps ¶ ˆXt♦Tt=1 are then fed into a GRU.

(b) The Gated Recurrent Unit (GRU) module: GRU is a variant of the RNN designed to learn long-term dependencies using two selective gates [Cho et al., 2014]. In the GRU, each cell processes an input ˆxt = ( ˆX(i↪:) t )↑ and a hidden state ht = (H(i↪:) t )↑. The update rule for a GRU cell is as follows:

where Wir, Whr, Whz, Win, Whn, bir, bhr, bhz, bin, and bhn are learnable parameters in GRU, ω(·) is an activation function, and ↓ is an element-wise product operation.

3.3 Layer-wise Relevance Propagation

In this paper, we consider neural networks consisting of layers of neurons. The output xk2 of a neuron k2 is a non-linear activation function g as given by:

Assume that we know the relevance R(l+1) k2 of a neuron k2 at network layer (l + 1) for the classification decision f(x), then we like to decompose this relevance into messages R(l↪l+1) k1↓k2 sent to those neurons k1 at the layer l which provide inputs to neuron k2 such that eq. (4) holds.

We can then define the relevance of a neuron k1 at layer l by summing all messages from neurons at layer (l + 1) as in eq. (5):

The relevance of the output neuron at layer M is R(M) 1 = f(x). The pixel-wise scores are the resulting relevances of the input neurons R(1) d .

4 The Proposed DGExplainer

This section introduces the proposed DGExplainer framework (summarized in Figure 2), which explains dynamic GNN predictions by back-propagating relevance through both time-varying and message-passing reverse paths. By accounting for the structural and temporal information in dynamic graphs, DGExplainer computes the relevance of each input feature, offering deeper insights into how the model arrives at its predictions.

DGExplainer operates in two stages: Stage 1: Compute Relevance in the GRU Module. In this stage, relevance scores are back-propagated through the time-related module (GRU) along its reversed time paths. As a result, we obtain the relevance scores for the GCN-encoded features at every time step. Stage 2: Back-Propagate Relevance in the GCN Module. Next, the relevance scores from Stage 1 are taken as input and back-propagated through the graph-related module (e.g., GCN) along the inverse of its message-passing path. This allows us to determine the relevance of the original input features across all time steps, providing an explanation for the dynamic graphs.

4.1 Stage 1: Relevance Back-Propagation in GRU

Stage 1 focuses on deriving the relevance of each GRU cell's inputs by propagating the output relevance backward in time. Specifically, DGExplainer first obtains the relevance of the output from the final GRU cell. Then, at each time step t, it uses the current cell's output relevance to compute the relevances of the two inputs: (1) the GCN-encoded feature and (2) the hidden state. The detailed process is illustrated below.

Given the final hidden state for a node, RhT , where hT = (H(i↪:) T )↑, the objective is to compute the relevances of the inputs, Rht→1 and Rˆxt→1 , from the relevance of the output, Rht , for each GRU cell at time t. As described in Section 3.3, relevance back-propagation redistributes the activation of a descendant neuron to its predecessor neurons, with the relevance being proportional to the weighted activation value. Based on the dependencies among different components in the final step of the GRU, as shown in Equation (2d), we derive the relevance back-propagation for this step as follows:

Note that neurons r and z only receive messages from neuron ht↔1, as shown in Equations (2a) and (2b). Consequently, their contribution to ht can be merged into the contribution from ht↔1, and their relevances can be regarded as constants. Notice that ht↔1 is used to compute both n in Equation (2c) and ht in Equation (2d). This reveals that the relevance Rht→1 has two sources: n and ht. Based on the contributions from Rht→1↓n and Rht→1↓ht , we can define Rht as follows:

Given that the relevance of a neuron is proportional to its activation at the same layer, i.e., Rk↓k1 : Rk↓k2 = a(l) k1 : a(l) k2 , we can derive the following based on Equation (2d):

We can conclude that if we derive Rht→1↓ht and Rht→1↓n, we can then obtain Rht . Therefore, we break down this problem into three steps: computing Rht→1↓ht , Rht→1↓n, and Rht→1 , as formulated below: (a) Compute Rht→1↓ht : Solving for Equations (7) and (8) obtains:

where ε > 0 is a constant introduced to keep the denominator non-zero. Notice that the only ancestor neuron of n is ht, so here Rn↓ht is actually Rn, so in the following left of section, we use Rn for simplicity.

(b) Compute Rht→1↓n: From Equation (2c) we obtain:

Then, their relevance satisfies:

Hence, Rn1 and Rn2 can be obtained.

Since ht↔1 influences only n2 among the three components of n, we compute Rht→1↓n using the ε-rule (see appendix A.6 for details) based on Equation (13):

(c) Compute Rht→1 : Rht→1 can be computed by adding Equations (10) and (15) together: Rht→1 = Rht→1↓ht + ∑j R(j) ht→1↓n▷ Notice that Rˆxt is the relevance of a node feature ˆxt, which is a row in ˆXt. By computing the set of relevances ¶Rˆxit ♦Ni=1 for all nodes, we can obtain the overall relevance matrix RˆXt , by concatenating the individual node relevances, i.e., RˆXt = [Rˆx1t ;Rˆx2t ; ▷ ▷ ▷ ;RˆxNt ].

4.2 Stage 2: Relevance Back-Propagation in GCN

To find the relevance of the input data in a GCN, we start with the relevance of the output and backtrack through the network layers. We calculate the relevance of each layer's nodes using specific equations that distribute relevance from one layer to the previous. By repeating this process, we determine the relevance of the original input features. Finally, we average the absolute values of these relevances across all features to identify the importance of each node at a specific time. In the following, we show the concrete process in algorithm 1.

Then we backtrack in the GCN to get RXt from RˆXt . Note that the RˆXt is the relevance of the output ˆX of the GCN at t and RF(L) t = RˆXt . We rewrite Equation (1) as:

Let (F(l+1) t )(k↪:) , (P(l) t )(k↪:) , (P(l) t )(:↪k) , (F(l) t )(:↪k) denote the k-th row of F(l+1) t , the k-th row of P(l) t , the k-th column of P(l) t , the k-th column of F(l) t , respectively. We have

Leveraging the ε rule, we assign the relevance by:

where (W(l) t )(j↪k) represents the entry at the j-th row and kth column of W(l) t , and V(b↪j) t denotes the entry at the b-th row and j-th column of V(k↪j) t . And the R(P(l) t )(k↪j) can be obtained similarly as R(F(l) t )(j↪k) . The relevance RF(l) t can be obtained from RF(l+1) t using equation Equation (19), and R(P(l) t )(k↪j) . Finally, the relevance RF(0) t can be determined. Notice that RF(0) t = RXt , so we have RF(0) t = RXt , thus completing the backward process for obtaining relevance in the GCN. To further identify important nodes at a specific time step, we take the absolute values of the relevances and average them along the feature dimension to get the relevance of a node at time t: Rxit = ∑Dj=1 ♣(Rxit )(j) ♣◁D.

Figure 3 illustrates the LRP process for a time step of these two states. Specifically, DGExplainer redistributes the relevance of the output hidden state, RHt , to 1) the relevance of the input hidden state, RHt→1 , and 2) the relevance of the GCN-encoded feature, RˆXt . It then back-propagates the latter through the GCN and finally obtains the relevance of the input feature at this time step, RXit→1 . The entire algorithm is summarized in Appendix A.1.

5 Experiments

We conduct quantitative and qualitative experiments on six real-world graphs to answer the following research questions: RQ1: Can the proposed DGExplainer learn high-quality explanations for the GCN-GRU model?

RQ2: What are the benefits of DGExplainer in explaining dynamic GNNs compared to static methods?

RQ3: How do the hyperparameters affect DGExplainer?

Implementation details are provided in Appendix A.4. Unless otherwise specified, we present the performance of DGExplainer on the GCN-GRU model in our experiments. Additionally, in Appendix A.7, we demonstrate the performance of DGExplainer across various other dynamic GNN models.

5.1 Experiment Settings

Datasets. We evaluate the proposed framework on six realworld datasets. For the link prediction tasks, we use four datasets: Reddit Hyperlink (Reddit) [Kumar et al., 2018], Enron [Klimt and Yang, 2004], Facebook (FB) [Trivedi et al., 2019], and COLAB [Rahman and Al Hasan, 2016]. For the node regression tasks, we use two datasets: PeMS04 and PeMS08 [Guo et al., 2019] 1 . The statistics of these datasets and the initial performance of GCN-GRU on them are presented in Appendix A.2.

Baselines. We assess our proposed method against eight baseline explanation methods. These include two general explanation methods: Sensitivity Analysis (SA) [Baldassarre and Azizpour, 2019] and GradCAM [Pope et al., 2019]. Additionally, we compare our method with six GNN explanation methods: GNN-GI [Schnake et al., 2020], GNNExplainer, PGExplainer, SubgraphX, GCN-SE, T-GNNExplainer, and DyExplainer. Detailed descriptions of these baseline methods are provided in Appendix A.3.

Evaluation. We compare the quality of each explanation baseline and our method using four quantitative metrics: confidence, sparsity, stability, and fidelity. Following the experimental setup of a previous work [Pareja et al., 2020], we conduct experiments on link prediction and node classification. Detailed introduction of evaluation is in Appendix A.5.

5.2 Prediction and Explanation Performance

To address RQ1, we conducted a comprehensive comparison of our proposed method, DGExplainer, against several baseline methods. Our evaluation focused on two key aspects: prediction accuracy and the quality of explanations in identifying important nodes. The results demonstrate that DGExplainer outperforms the baselines in terms of fidelity and sparsity, providing more accurate and concise explanations. Additionally, our method exhibits good stability, ensuring consistent explanations even in the presence of minor perturbations, although on some datasets, it slightly underperforms SA and GradCAM. These results establish the effectiveness and reliability of our proposed method in capturing important nodes and providing reliable explanations in the context of link prediction and node regression tasks. Traditional explanation baselines also demonstrate competitive performance. For example, SA and GradCAM achieve strong sparsity, even surpassing some graph-specific explanation methods.

1 pems.dot.ca.gov

Results on Fidelity, Fidelity+ and Sparsity. Fidelity measures a method's ability to accurately capture important nodes. A high-fidelity explanation method is desirable. Fidelity+ is a surrogate version of fidelity, where a graph is sampled from the explanation subgraph by retaining each edge with probability ϑ and erasing it with probability 1 ↔ ϑ. To assess fidelity, we ranked the nodes based on their importance and conducted occlusion experiments by selectively occluding a fraction of the top nodes while keeping 80% of the nodes unchanged (ϖ1 = 0▷8). For fidelity+, we define the explanation subgraph as the subgraph consisting of nodes with relevance greater than ϖ1. The proposed method consistently outperformed the baselines in terms of both fidelity and fidelity+, and sparsity across most datasets, as shown in Table 1. In the remaining datasets, our method achieved comparable results. The Fidelity+ gap between the proposed method and the baselines is larger than the Fidelity gap, further demonstrating DGExplainer's effectiveness in assigning higher relevance to important nodes.

Results on Stability. A stability evaluation was conducted to assess how well the explanation method handles perturbations in the input graph. We introduced random perturbations by adding additional edges to the original graph at a ratio of r = 20% and evaluated the resulting changes in the relevances generated by the model. A stable explanation method should provide consistent explanations when the input undergoes minor perturbations, resulting in lower stability scores. As presented in Table 1, our proposed method generally exhibited good stability, although it did not outperform SA and GNNExplainer. These findings indicate that our method demonstrates relative robustness to small perturbations in the input graph.

5.3 Qualitative Analysis

To address RQ2, we conducted quantitative experiments and visualizations of the generated explanations using DGExplainer and baseline methods on the PeMS04 dataset, which represents traffic flow on a highway network. The results, presented in Figure 4, indicate that DGExplainer generates the most reasonable and detailed explanations compared to the GNN-GI and GNNExplainer approaches. Our analysis revealed several key findings: (a) GNN-GI tends to assign equally extreme relevances to every individual node, suggesting that each node has a strong correlation with the prediction. In contrast, GNNExplainer generates average scores for all the identified nodes. (b) GNN-GI identifies nearly all nodes as important, while GNNExplainer only identifies a few nodes as significant, disregarding the correlations of other nodes with the target variable.

These disparities in the visualization results are due to the fact that the comparison methods fail to capture the temporal patterns of dynamic graphs, treating each time step independently and considering only spatial information. In contrast, DGExplainer excels in generating comprehensive and context-aware explanations by effectively incorporating temporal dynamics into the analysis. By considering both spatial and temporal information, DGExplainer provides a more accurate understanding of the underlying relationships within the dynamic GNNs.

5.4 Parameter Sensitivity Analysis

To address (RQ3), we investigate fidelity across various threshold values, denoted as ϖ1 = ¶0▷5↪ 0▷6↪ 0▷7↪ 0▷8↪ 0▷9♦. The fidelity analysis is presented in Figure 5. Our observations are as follows: (a) With smaller ϖ1 values, the fidelity is high. This is because a larger number of nodes are occluded when their relevance surpasses the threshold, resulting in a substantial change in accuracy. (b) As ϖ1 increases, the fidelity gradually decreases, with a steeper decline observed in the range of [0▷8↪ 0▷9]. Overall, our proposed method consistently achieves the highest fidelity across all thresholds and datasets, affirming the robustness of our framework. These findings provide substantial insights into the relationship between fidelity and the chosen threshold values, reinforcing the efficacy of our approach.

6 Conclusion

In this paper, we present DGExplainer, a novel and efficient framework that utilizes both layer-wise and timewise relevance back-propagation to explain the predictions of dynamic Graph Neural Networks (GNNs). To evaluate DGExplainer's performance, we conduct both quantitative and qualitative experiments. The results demonstrate the framework's effectiveness in identifying crucial nodes for link prediction and node regression tasks, outperforming existing explanation methods. This research pioneers the exploration of dynamic GNNs, offering insights into their intricate structures, which is a significant challenge due to the complexity of inference in time-varying modules. Unlike existing static GNN explainers, DGExplainer does not require learning a surrogate function or executing any optimization procedures. Additionally, it can be extended to other advanced dynamic GNNs.

Acknowledgements

Work in the paper is supported by NSF ECCS 2412484 and NSF RISE 2425748.