Causality-Inspired Spatial-Temporal Explanations for Dynamic Graph Neural Networks

We appreciate your overall positive assessment of our contributions and are grateful for your suggestion. We have already updated the new revision based on your suggestions.

---

Q1: Generative model

W1: Thanks for your question. Our dynamic graph interpretability task lies in providing spatial-temporal explanations (dynamic subgraph set) for dynamic graph structures. Consequently, our ultimate objective is to define a generative model, not a representational model. We make this more clear in Section 2.1.

---

Q2: Logical derivation of Equation 1

W2: In Equation 1, we merge the estimation of $P(\mathcal{Y}|do(\mathcal{C}))$ with that of $P(\mathcal{Y}|do(\mathcal{D}))$. The detailed derivation process of backdoor adjustment can be shown as:

$

\begin{aligned} P(\mathcal{Y}|do(\mathcal{D})) &= \sum P(\mathcal{Y}|do(\mathcal{D}), \mathcal{S})P(\mathcal{S}|do(\mathcal{D})) \ &= \sum P(\mathcal{Y}|do(\mathcal{C}))P(\mathcal{S})\ &= \sum P(\mathcal{S})\sum P(\mathcal{Y}|do(\mathcal{C}),\mathcal{T})P(\mathcal{T}|do(\mathcal{C})\ &= \sum P(\mathcal{S})\sum P(\mathcal{Y}|\mathcal{G})P(\mathcal{T}). \end{aligned}.

$

We add this in Appendix A.4 in the revision.

---

Q3: Interpretability issue of DyGNNs

W3: Sorry for our unclear expression, all our experiments are conducted on dynamic datasets. In essence, our case study is conducted on DBA-Shapes to provide a more vivid demonstration of DyGNNExplainer's interpretability. We visually represent both the original graph and the top six weighted edges of the generated causal subgraph across all time steps using DyGNNExplainer.

Regarding temporal interpretability, the scrutiny of variable $t_p$ reveals that DyGNNExplainer adeptly pinpoints the most critical time steps that significantly influence the target node label within the original graph.

In terms of spatial interpretability, DyGNNExplainer proficiently discerns the presence of the 'house' motif within the original graph's concluding time step, offering a compelling explanation for the target node label.

---

Q4: Static datasets

W4: Since our method is the first study on dynamic graph interpretability, there are no directly available datasets suitable for the task of dynamic graph interpretability. So we dynamically transformed some commonly used static graph interpretability datasets. We add this in Section 3.1 in the revision.

---

Q5: Missing important literature

W5: You recommend some benchmarks for graph representation and graph generalization. But it is hard to compare our method with them since the task in our model is totally different from theirs. Graph representation and graph generalization models are the target models we want to explain. For interpretable methods, the target model is model-agnostic. The interpretability task is to provide good explanations for these models. We make this more clear in Section 3.1.

Additionally, our methods of decoupling dynamic and static relationships are also different from CaST. To disentangle the static relationship and the dynamic relationship, we propose the constraint that dynamic relationships evolve over time steps but static relationships are independent across each time step. Consequently, we leverage the pre-trained target DyGNN model to guarantee the essential temporal correlation between neighboring subgraphs for the dynamic relationships and identify the rest independent causal information to the static relationships.

---

Q6: Implementation of Equation 7

W6: We utilize contrastive learning to ensure the semantic similarity between the causal embedding $\mathbf{e}^{\mathcal{C}}_t$ and the original embedding $\mathbf{e}_t$ while enlarging the semantic distance between the causal embedding $\mathbf{e}^{\mathcal{C}}_t$ and the trivial embedding $\mathbf{e}^{\mathcal{T}}_t$. $s(\cdot,\cdot)$ measures the similarity, we utilize the dot product here. We add the implementation in Section 2.5 in the revision.

---

Q7: Implementation of Equation 14

W7: $\left\|\mathbf{A}^{\mathcal{C}}_t\right\|_1$ and $\left\|\mathbf{A}^{\mathcal{D}}_t\right\|_1$ are $l_1$ norm of the causal graph set and the dynamic causal graph set, respectively. We sum up all elements here. The $\left\|\mathbf{A}^{\mathcal{S}}_t\right\|_1$ in Equation 14 should be replaced by $\left\|\mathbf{A}^{\mathcal{D}}_t\right\|_1$ , we have corrected it in revision.

---

Q8: Typo in Table 2 and Equation 15

W8: We are sorry that one of the data in Table 2 was filled in incorrectly. The best performance in DTree-Grid is obtained by DyGNNExplainer. We have corrected the typo in Table 2 in the revision. And we have corrected $\Theta$ with $\Psi$ in the last line of Section 2.

---

Thank you again for your constructive reviews. Hope that our response can address your concerns. We feel grateful for your appreciation.

We appreciate your overall positive assessment of our contributions and are grateful for your suggestion. We have already updated the new revision based on your suggestions.

---

Q1: Problems in introduction section

W2: Thanks for your valuable questions and suggestions.

Spatial interpretability and temporal interpretability:

The investigation of spatial interpretability critically relies on the extraction of subgraphs that can represent the characteristics of the complete graph in spatial dimension and elucidate outcomes in subsequent tasks. In essence, these subgraphs serve as substitutes for the original graphs, enabling the attainment of analogous results in downstream tasks.

Temporal interpretability relies on the importance of representative sub-graphs over the time slots. In essence, it's essential to elucidate the significance of each time step concerning its impact on the outcomes of subsequent tasks. We add this in Section 1.

Challenges for implementing the SCM:

The first challenge lies in the approach to disentangling the complex causal relationships as no explicit information is available for the identification of trivial, dynamic, and static relationships. The dynamic graph encapsulates intricate spatial-temporal relationships and dependencies, posing a challenge in directly conducting interventions on the confounder. This makes decoupling the trivial, dynamic, and static relationships very difficult.

The second challenge is the way to construct the SCM to fit the task of discovering spatial-temporal interpretability due to the lack of existing models for dynamic graphs. As pioneers in the realm of dynamic graph interpretability, we encounter the challenge of lacking a causal model that can offer interpretive insights into intricate spatial-temporal relationships.

How the proposed approach addresses the challenges:

We propose two constraints to disentangle the trivial relationship, the static relationship, and the dynamic relationship, respectively.

First, to disentangle the trivial relationship and the causal relationship, we propose that the causal relationship determines the downstream task results. Thus, we propose a contrastive learning module to ensure the semantic similarity between the causal relationship and the original graph while enlarging the semantic distance between the causal relationship and the trivial relationship.

Second, to disentangle the static relationship and the dynamic relationship, we propose that dynamic relationships evolve over time steps but static relationships are independent across each time step. Consequently, we leverage the pre-trained target DyGNN model to guarantee the essential temporal correlation between neighboring subgraphs for the dynamic relationships and identify the rest independent causal information to the static relationships.

Thank you again for your questions. It is also our goal to clean up our motivations and solutions. We aspire that through our explanations, you gain a more clear understanding of our work.

---

Q2: Static datasets

W2: Since our method is the first study on dynamic graph interpretability, there are no directly available datasets suitable for the task of dynamic graph interpretability. So we dynamically transformed some commonly used static graph interpretability datasets. We add this in Section 3.1 in the revision.

---

Q3: Baselines

W3: Since our method is the first study on dynamic graph interpretability, we can only utilize the baselines from static graph interpretability tasks. To achieve a relatively fair comparison, we add the time factor into baselines so as to make them suitable for dynamic graph interpretability. Dynamic graphs are much more complex than static graphs due to their spatial-temporal correlations. It is meaningless if we compare our method with baselines on static graphs.

---

Q4: Typo in Table 2

W4: We are sorry that one of the data in Table 2 was filled in incorrectly. The best performance in DTree-Grid is obtained by DyGNNExplainer. We have corrected the typo in Table 2 in the revision.

---

We appreciate your overall positive assessment of our contributions and are grateful for your suggestion. We have already updated the new revision based on your suggestions.

---

Q1: Text in Figure 1

W2: We have enlarged the text in Figure 1in the new version.

---

Q2: Typo in Table 2

W2: We are sorry that one of the data in Table 2 was filled in incorrectly. The best performance in DTree-Grid is obtained by DyGNNExplainer. We have corrected the typo in Table 2 in the revision.

---

Thank you again for your constructive reviews. Hope that our response can address your concerns. We feel grateful for your appreciation.

We appreciate your overall positive assessment of our contributions and are grateful for your suggestion. We have already updated the new revision based on your suggestions.

---

Q1: Derivation process and complexity descriptions

A1: In Equation 1, we merge the estimation of $P(\mathcal{Y}|do(\mathcal{C}))$ with that of $P(\mathcal{Y}|do(\mathcal{D}))$. The detailed derivation process of backdoor adjustment can be shown as:

$$P(\mathcal{Y}|do(\mathcal{D})) = \sum P(\mathcal{Y}|do(\mathcal{D}), \mathcal{S})P(\mathcal{S}|do(\mathcal{D})) \\ = \sum P(\mathcal{Y}|do(\mathcal{C}))P(\mathcal{S})\\ = \sum P(\mathcal{S})\sum P(\mathcal{Y}|do(\mathcal{C}),\mathcal{T})P(\mathcal{T}|do(\mathcal{C})\\ = \sum P(\mathcal{S})\sum P(\mathcal{Y}|\mathcal{G})P(\mathcal{T}).$$

VGAE-based encoder is the most time consuming component in our method. In the dynamic VGAE-based encoder, we generate the causal soft mask matrix $\mathbf{M}^{\mathcal{C}}$ and the dynamic soft mask matric $\mathbf{M}^{\mathcal{D}}$ with $O(d*|V|^2)$ complexity for T unique time steps, where d is the embedding size. The contrastive learning part also costs lots of time and has time complexity O(|V|d$T^2$). Then, the total time complexity is O($|V|^2$dT + |V|d$T^2$). Note that $T << |V|$, then we can ignore the time of contrastive learning and obtain the total time complexity as O(|V|^2dT).

We add this in Appendix A.4 in the new version.

---

Q2: Loss function hyperparameters

A2: Thank you for your valuable suggestions. In graph interpretation tasks, they usually have many constraints and require different types of loss functions to satisfy these constraints, e.g., OrphicX has 4 loss functions for the static graph interpretation. We supplement the parameter search range and optimal parameter selection of the four constraints of the loss function to help improve the reliability and reproducibility of the results.

In the final optimization objects, the loss function weight parameters $\lambda_1$, $\lambda_2$, $\lambda_3$, and $\lambda_4$ are set from [0.2, 0.4, 0.6, 0.8, 1]. And the best performance is obtained where $\lambda_1=1$, $\lambda_2=0.4$, $\lambda_3=0.2$, and $\lambda_4=0.2$. We add this in Appendix A.2.

Once again, I extend my gratitude for your invaluable suggestions. It remains our primary objective to deliver trustworthy interpretive results.

---

Q3: Shortage of benchmarks and ablation study

A3: Thank you for your valuable questions. Although there have been some works on static graph interpretability, to the best of our knowledge, we are the first to study dynamic graph interpretability. Therefore, we have no existing dynamic graph interpretability benchmarks for comparison, and can only compare with currently competitive static interpretability methods.

On the other hand, you recommend some benchmarks for graph representation and graph generalization. But it is hard to compare our method with them since the task in our model is totally different from theirs. Graph representation and graph generalization models are the target models we want to explain. For interpretable methods, the target model is model-agnostic. The interpretability task is to provide good explanations for these models. We make this more clear in Section 3.1.

Given the novelty of our study on dynamic graph interpretability, there is a dearth of readily available synthetic datasets suitable for this purpose. Consequently, we've undertaken dynamic transformations of commonly used synthetic static graph interpretability datasets such as BA-Shapes. We also use two real-world dynamic graph datasets, Elliptic for node classification and MemeTracker for graph classification. The Ogbn-Arxiv dataset is a real-world data set but a static graph dataset. If we dynamically transform it, it will lose its real meaning. We make this more clear in Section 3.1.

For ablation study, we provide a DyGNNExplainer version without VGAE ('w/o. VGAE'). In this version, we replace the encoder with a simple GCN layer. DyGNNExplainer outperforms the `w/o. VGAE' version. This is primarily due to the superior capabilities of VGAE in harnessing spatial graph information to generate soft masks. We provide this ablation study in Section 3.2.

---

Q4: Related work

A4: Thank you for your valuable suggestions. Although our interpretability task is totally different from the graph generalization task, their method is the model we want to explain and is helpful in our work. Additionally, the spatial-temporal method and the causal method are directly related to our tasks. We add these related works in Section 4 and Appendix 4.3.

---

Thank you again for your constructive reviews. Hope that our response can address your concerns. We will feel grateful if you could boost our paper.