Robust Explanations of Graph Neural Networks via Graph Curvatures

Thank you for taking the time to review our paper!

Q1: How many times was the algorithm run?

A1: We run the base explanation algorithm only once to get the edge importance scores. Then, we generate the final explanation subgraph using the importance scores, Ricci curvature, and effective resistance. For robustness evaluation, we sample 300 random perturbation subgraphs and compute the robustness metric using Equation (2). For other metrics like fidelity, the algorithm also runs only once.

Q2: Is the improvement significant?

A2: We did not perform formal statistical significance testing in this version of the paper. In our experiments, while some improvements over baselines are consistent, they are not always statistically significant across all datasets. We will consider adding significance analysis in future work.

Q3: why don't we transform the robustness objective function into a tractable loss ? For example, using reparameterization or directly measuring the distance of the multivariate distribution for Eq. (2).

A3: We agree that transforming Eq. (2) into an optimizable loss is an interesting idea. However, it is not straightforward to implement for several reasons. First, it is difficult to define how to generate and update perturbation subgraphs based on the explanation subgraph during training. Second, most existing explanation methods rely on continuous edge/node masks, while the final explanation is discrete. This mismatch can lead to information loss and suboptimal performance. Instead, our method directly selects robust and important edges based on geometric properties of the graph, improving the robustness of the explanation without requiring a new loss function.

Thank you for taking the time to review our paper!

Q1:While the trade-off between robustness and fidelity is managed via a tunable parameter lambda, an elegant and theoretically sound idea, the method does not account for the inherent diversity of graph data. For example, even within node classification tasks, there may be cases where robust edges serve as the primary rationale for predictions, and others where fragile edges are more predictive. Therefore, using a single global lambda to represent this trade-off across an entire graph may be overly simplistic.

A1: Thank you very much for raising this important question. We agree that the trade-off between fidelity and robustness can vary depending on the explanatory target. As the reviewer pointed out, in some cases, fragile edges may be essential for the model’s prediction, while robust edges may contribute less. In such cases, increasing lambda to favor robustness can reduce fidelity. However, even without using lambda, it may still be difficult to find a subgraph that is both robust and faithful using other methods. This may be due to the structure of the graph itself.

On the other hand, in cases where many candidate edges have similar importance scores, using curvature-based robustness can help choose more stable edges and improve robustness without lowering fidelity.

Our current experiments focus on global performance across all the explanation targets. Our results show that, in most cases, robustness can be improved without a significant drop in fidelity. We acknowledge that a more detailed analysis of target-specific trade-offs would be valuable.

Q2: Could you discuss the possibility of determining the trade-off parameter lambda between robustness and fidelity not globally for the entire graph, but locally for each explanatory target?

A2: If it is a single target node, I think a more effective method may be to use grid search to obtain lambda. Using the optuan package in Python can speed up the search process.

Q3: Additionally, the Ricci curvature approximation relies solely on node degrees, which could be problematic. For instance, it is entirely plausible that two high-degree nodes are connected via a single bridge-like edge, and in such cases, the approximation may fail. However, whether this approximation holds in high-dimensional and non-Euclidean graph spaces warrants more careful examination.

A3: We thank the reviewer for this insightful comment. Indeed, as pointed out, our original approximation relies solely on node degrees, neglecting explicit distance information within the graph. This simplification can indeed fail in specific scenarios, such as the one raised by the reviewer, where two high-degree nodes are connected via a single bridge-like edge. However, our experimental results demonstrate the effectiveness of this approximation method.

To address this limitation and strengthen our results, we have further derived the theory using the exact Wasserstein distance, explicitly incorporating graph distances. The theorem 4.4 become as

If ⊕ is the sum operation,
$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( (1 + \beta')^{T-1} \left(2 \beta'(1 - \alpha') + 4 \beta' \right) + \sum_{i=2}^{T} 2 (\beta')^i (1 + \beta')^{T-i} \right)$

If ⊕ is the mean operation,
$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( 2^{T-1} \left(4 \beta' + \frac{3(1 - \alpha')}{\alpha'} \right) + 4(T - 1)\beta' \right)$

When using exact Ricci curvature, Theorem 4.4 changes only in a constant term, and the conclusion remains unchanged. Additionally, we have conducted new experiments based on this precise Ricci curvature. Our updated experiments also support our theoretical claims. Considering Ricci curvature can improve the robustness of the explanation

Table 1: Relative Error (↑) with exact Ricci Curvature (%). The ⊕ in GNN is mean operation. (Best values in bold)

Table 2: $Fidelity_{KL}$ (↓) with exact Ricci Curvature. The ⊕ in GNN is mean operation. (Best values in bold)

Table 3:Relative Error (↑) with exact Ricci Curvature (%). The ⊕ in GNN is sum operation. (Best values in bold)

Table 4: $Fidelity_{KL}$ (↓) with exact Ricci Curvature. The ⊕ in GNN is sum operation. (Best values in bold)

Q1:The proof on Lemma 4.2 is confusing. The lemma 4.2 only has the node pair’s degrees as input without information from the specific structure of the graph.

A1: We thank the reviewer for carefully pointing out the concerns regarding Lemma 4.2. Lemma 4.2 was originally derived based on an approximate view, inspired by the formulation introduced in [1]. To adapt this approach for discrete graph topologies, we implicitly utilized node-degree distributions as a simplified approximation of the underlying graph structure. This approximation does not explicitly incorporate detailed graph distances. However, our results show that this method of selecting explanation subgraphs based on the approximately calculated Ricci curvature can also improve the robustness of the explanation.

The Lemma 4.2 is used in lines 507-508 and 513-514 of our proofs. Motivated by the reviewer’s valuable comment, we revised these proofs by using the exact Ricci curvature, updated Theorem 4.4 accordingly. When we use exact Ricci curvature, theorem 4.4 changes only in a constant term, and the conclusion remains unchanged. The theorem 4.4 become as

If ⊕ is the sum operation,
$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( (1 + \beta')^{T-1} \left(2 \beta'(1 - \alpha') + 4 \beta' \right) + \sum_{i=2}^{T} 2 (\beta')^i (1 + \beta')^{T-i} \right)$

If ⊕ is the mean operation,
$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( 2^{T-1} \left(4 \beta' + \frac{3(1 - \alpha')}{\alpha'} \right) + 4(T - 1)\beta' \right)$

Additionally, we have conducted new experiments based on this precise Ricci curvature. Our updated experiments also support our theoretical claims. Considering Ricci curvature can improve the robustness of the explanation

Table 1: Relative Error (↑) with exact Ricci Curvature (%). The ⊕ in GNN is mean operation. (Best values in bold)

Table 2: $Fidelity_{KL}$ (↓) with exact Ricci Curvature. The ⊕ in GNN is mean operation. (Best values in bold)

Table 3:Relative Error (↑) with exact Ricci Curvature (%). The ⊕ in GNN is sum operation. (Best values in bold)

Table 4: $Fidelity_{KL}$ (↓) with exact Ricci Curvature. The ⊕ in GNN is sum operation. (Best values in bold)

[1] Why the 1-Wasserstein distance is the area between the two marginal CDFs.

Q2:The theoretical proof is not tightly related to the robustness definition.

A2: Thank you for your valuable feedback. We agree that the original theoretical formulation may loosely connected to the formal definition of robustness. To address this, we have revised the theoretical analysis to ensure a tight alignment with the robustness definition. Let $r=1-\frac{|\mathcal{E}_s|}{|\mathcal{E}|}$.

For theorem 4.5,

If ⊕ is the sum operation,
$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( (1 + \beta_{s})^{T-1} \left(2 \beta_{s}(1 - \alpha_{s}) + 4 \beta_{s}+2 \right) + \sum_{i=2}^{T} 2r (\beta_{s})^i (1 + \beta_{s})^{T-i} \right), s.t, \mathcal{E}_s \subseteq \mathcal{E}'.$

If ⊕ is the mean operation,
$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( 2^{T-1} \left(4 \beta_{s} + \frac{3(1 - \alpha_{s})}{\alpha_{s}} +2\right) + 2(T - 1)\beta_{s}+2r(T - 1)\beta_{s} \right), s.t, \mathcal{E}_s \subseteq \mathcal{E}'.$

For theorem 4.9,

$|\Pr_u(\mathcal{G}) - \Pr_u(\mathcal{G}')| \leq \eta \left( 2+2 \beta_{s}^{T} (1-r^T)+\bar{R}_s +\frac{2}{dmin(1-\gamma)}\right), s.t, \mathcal{E}_s \subseteq \mathcal{E}'.$

Q3: The author could add some adversarial attack methods and test the performance after attack.

A3: Our work focuses on the robustness of graph model explanations, not on defending against graph attacks. So we do not compare with defense-related baselines, and to our knowledge, no such defense baselines exist for robust explanations.

However, we do evaluate the robustness of explanations under graph perturbations (attack). For a given explanation subgraph, we randomly add and remove 10% of the edges that are not part of the explanation to create a perturbed graph G′. We repeat this process 300 times and compute the robustness score as defined in Definition 4.1. To provide a baseline, we also randomly sample some edges as explanation subgraphs, and apply the same process to get their robustness scores. We then compare the relative error between explanation method and the random baseline. The results show that our method clearly improves explanation robustness.

Q4: How the explanation subgraphs are chosen in original base explainers?

A4: To ensure a fair and consistent comparison across methods, we fixed the fraction of selected edges for all explainers. Specifically, both the original base explainers and our proposed method select 10% of the total edges as the explanation subgraph. For the original explainers, the top 10% of edges are chosen based on their importance scores F(u,v) in descending order.

Thank you for taking the time to review our paper!

Q1: what is the size of the explanation sub-edges E_s

A1: Thank you for the question. In our experiments, the size of the explanation subgraph E_s is set to 10% of the total number of edges in the input graph. This fixed ratio allows for fair comparison across different methods and ensures the explanation remains concise.

Q2: Is there any connection between Ricci curvature and effective resistance, can we combine both of the score in the final objective to further boost performance?

A2: Thank you for the insightful suggestion. We conduct a statistical analysis on three datasets using both Spearman and Pearson correlation coefficients, and find no significant correlation between Ricci curvature and effective resistance. The results are shown in the table.

Table 1: The correlation coefficient and p-value

In the theory section, we analyze how Ricci curvature and effective resistance are individually related to model robustness and explanation robustness. However, we do not analyze their joint effect on robustness. Therefore, in our final objective, we treat these two metrics separately.

We think that combining both scores into a unified objective does not always lead to better performance. For example, in some cases, selecting edges A, B, and C based on effective resistance provides more robust explanations, while in the same cases, Ricci curvature favors edges D, E, and F. These conflicting preferences may reduce overall robustness. We acknowledge this as an interesting direction, and plan to explore it further in future work.

Q3:The baseline only includes the basic GNN-explaining methods, it is better to evaluate the performance on methods like ensemble method and retraining method.

A3: Thank you for the helpful suggestion. Regarding the robustness of graph model explanations, few works use ensemble or retraining methods to improve explanation robustness. In other fields, such as computer vision, such methods have been used to improve robustness, but they are not commonly applied in the graph domain.

In this work, our proposed method is both model-agnostic and explanation-method-agnostic. It identifies robust edges based on the geometric properties of the graph data. For this reason, we focus our evaluation on standard GNN explanation methods and show that our approach can enhance basic GNN-explaining methods robustness. We appreciate the suggestion and consider evaluating the performance on methods like ensemble method and retraining method for future work.

Q4: What does the “+Curvature” mean in the effective resistance based results on Table 3 and 4, is that a typo? And the base result (e.g. GNNExplainer) in Table 1 cannot align with Table 3, what are the differences here?

A4: Thank you for pointing this out. The “+Curvature” in Tables 3 and 4 is indeed a typo. We apologize for the confusion and the poor reading experience it may have caused. Regarding the base results, although the same dataset and method are used in Table 1 and Table 3, the target nodes/edges/subgraphs to be explained are different. As a result, the reported results are not directly aligned.