Provably Robust Explainable Graph Neural Networks against Graph Perturbation Attacks

We thank the reviewer for appreciating that the contributions are clearly stated, the paper is well-structured, and the attacks, defense, and theoretical guarantees are detailed.

W1. Only one type of GNN classifier and GNN explainer.

This may be a misunderstanding. In Table 1-2, Figures 3-5, and Figures 6-11 in Appendix, we showed our result on three GNN classifiers (GCN, GAT and GSAGE), and three GNN explainers (PGExplainer, GSAT and Refine).

W2. parameter analysis combined as an ablation study

Sections 4.2.1 and 4.2.2 examine different aspects of our XGNNCert, making it challenging to combine their analyses. Specifically, Section 4.2.1 focuses on the normal classification and explanation accuracy of XGNNCert, while Section 4.2.2 investigates its certified explanation accuracy.

W3. XGNNCert shows a large explanation gap on Benzene with GSAT

We highlight that the normal explanation accuracy under no attack is often larger than the robust explanation accuracy under the attack on GNN explainers. Especially, our XGNNCert defends against the worst-case attack and it shows promising performance in most of the settings, except on Benzene and FC with GSAT. The reason may be due to Benzene and FC being the difficult datasets for explanation (note all the three explainers have relatively low performance on them), which largely affects XGNNCert’s predictions and hence explanations.

W4. Text in Figure 2 be more visible

Thanks for the suggestion! See Figure 2 in the revised version.

Q1. How can an attacker access the data in realistic applications?

There are various scenarios in which an attacker can gain access to the data. For example, one scenario involves an insider attacker with full access to the data, while another scenario involves an attacker uploading their own data (e.g., a graph) to a system, such as the Drug Explorer system mentioned in the introduction.

Q2. Can GNN classifier and explainer be combined into one model to defend against the attack

Indeed, our XGNNCert integrates the GNN classifier and GNN explainer to defend against graph perturbation attacks, as illustrated in the overview Figure 2.

Q3. XGNNCert against more empirical attacks.

We test the most recent attack (Li et al. ICML’24) on XGNN and adopt its powerful induction-based attack. We allow an attacker to perturb two edges, and take the explanation edge change rate (i.e., fraction of explanation edges not in the groundtruth after the attack) as the metric to evaluate the defense effectiveness. A smaller value implies better defense performance. We use the PGExplainer as the baseline GNN explainer. In our method, we set T=70 and p=0.3. The results are shown below, where our XGNNCert shows promising defense performance against the attack.

We thank the reviewer for appreciating that the paper: 1) is well-written; 2) has a reasonable motivation to the study; and 3) provides certified robustness guarantees

1. Will there be a high risk that the graph data is perturbed by an attacker. A GNN builder could easily identify a perturbation operation.

If a GNN builder locally and privately builds its own GNN classifier or explainer with its own private and guaranteed-to-be-clean data, then there will not be a risk. However, this is not the case in various real-world scenarios, where the data, the GNN classifier, and the GNN explainer are from different parties. As the example shown in the paper, an user can upload a drug graph to the Drug Explorer system for drug repurposing (Wang et a, 2023b).

Under those scenarios, it is challenging for the GNN builder to identify the perturbation. In fact, various existing studies [See “Adversarial Attack on GNN Classifiers and Explainers” in Section 5] show an attacker can achieve its goal with an unnoticeably perturbation. For instance, [Zügner et al., 2018, Li et al. 2024] show an attacker can fool a GNN classifier or explainer by perturbing a graph such that the structural similarity between the perturbed graph and the clean graph is more than 99%. Also, all perturbation detection based methods fail as shown in, e.g., [a].

[a] Mujkanovic et al, Are defenses for graph neural networks robust. In NeurIPS 2022

2. Tightness of the derived bound.

We appreciate the reviewer's insightful question regarding the tightness of our bound. This is indeed an important aspect to consider in understanding the theoretical implications of our work. At present, we do not have formal evidence to confirm whether the bound is tight or not. This is a challenging problem as we need to consider both GNN classification and GNN explanation in the theoretical proof. We acknowledge that determining the exact tightness of the bound is an interesting and challenging open question that we aim to explore in future research.

Dear Reviewer Z8ry,

We thank you again for your appreciation on the paper's strengths and your constructive comments on the problem setting and the tightness concern. As the discussion period comes to the close, we would be grateful if you could confirm whether our responses address your concerns or if more clarifications are needed within the limited time. We believe your further feedback would help us to improve our paper.

Thank you once again for your precious input.

Best,

Authors

We thank the reviewer for appreciating that the paper is: 1) well-organized and well-written; 2) the first certified defense for GNN explainers against the graph attacks; and 3) is reliable in real-world scenarios thanks to deterministic guarantees

W1. Performance decrease compared with original GNN

We acknowledge that in some cases, there is a non-negligible decrease in clean accuracy due to global information corruption. However, we emphasize two key points:

• There is an inherent tradeoff between clean accuracy and provable robustness in trustworthy (explainable) AI, as the latter accounts for the worst-case attack scenarios;
• Besides the GNN explainer, we also provide guarantees for GNN classifiers, which makes the robustness certification more difficult.

Hence, this decrease in clean accuracy is reasonable and acceptable in the context of our work. We acknowledge it is interesting future work to design certified robust XGNN with better accuracy-robustness tradeoff.

W2. How to ensure subgraph size is uniform? p dependent on each graph?

We calculate the statistics of the subgraph sizes: we first compute the ave and std #edges on the $T$ subgraphs of each graph, and then compute the ave and std #edges of all graphs. Results are shown below:

Our observations indicate that the subgraph sizes do not vary significantly. Hence, for simplicity, we use the same $p$ for all graphs. We also emphasize that, regardless of the choice of $p$, the GNN explainer in XGNNCert identifies only the important explanatory edges in the clean graph. We will leave it as a future work to customize $p$ for individual graphs.

W3. Memory cost/scalability of XGNNCert.

Thanks for the comment! For a test graph, we generate T subgraphs with each having (p* #nodes$^2$) edges, so the extra memory cost per graph is O(T* p * #nodes$^2$). Note that an edge is represented as a pair of node indexes in the implementation, which is memory efficient. In addition, we focus on the graph classification task in this paper, where the graph sizes are usually small, e.g., the average #nodes in the used 5 benchmark graph datasets are between 10 and 22). We admit it is important future work to generalize the proposed certified defense mechanism to large-scale graphs such as social networks.

We add discussions on memory overhead in Line 482-484 in Section 4.2.4 in the revised version.

W4. Challenges on hyperparameter tuning of XGNNCert

We acknowledge that determining the optimal hyperparameters for an AI algorithm without studying their range of values remains a long-standing and challenging problem. Thus, we conduct experiments to analyze the impact of hyperparameters on our XGNNCert and provide insights into their effects. While the performance of XGNNCert is influenced by hyperparameter values, our results demonstrate stability within specific ranges, such as $\gamma \in [0.2, 0.4]$ and $T = 50,70$. Notably, we highlight that complex AI methods all require hyperparameter tuning.

I appreciate the detailed responses provided by the authors. Most of my concerns are addressed. Hence, I will keep my positive suggestion.

We sincerely thank the reviewer for recognizing that the paper is well-written, the problem is novel, and the robustness certification is non-trivial. We also greatly appreciate the constructive and insightful comments.

W1. Experimental details on (i) training strategy; (ii) network architecture; and (iii) code link for reproducibility.

(i) and (ii): Please see Appendix C.1 in the revised submission.

(iii) Please see the anonymous code link: https://anonymous.4open.science/r/XGNNCert-0B1F

W2. Relationship between $M_{\lambda}$ and $\lambda$; and $M^\star$.

Sorry for the confusion! We guess the confusion may arise from two aspects:

• We use $M_\lambda$ to denote both the certified perturbation size and the maximal certified perturbation size (as shown on y-axis in Figures 3-11);

• We use the same notation $M^*$ without explicitly indicating its dependence on $\lambda$, although it is actually $\lambda$-dependent. Below, we provide more clarifications.

In our setup and description, $M_{\lambda}$ depends on $\lambda$. To be specific, given a graph $G$ with $k$ groundtruth explanatory edges and a $\lambda$, we aim to ensure that the groundtruth explanatory edges and the outputted explanatory edges from a robust XGNN have at least $\lambda$ overlapped edges, under any attack with $M_{\lambda}$ perturbed edges (referred to as the certified perturbation size in the submission). Clearly, for different $\lambda$ values, the allowed number of perturbed edges could be different. Thus, we introduce $M_{\lambda}$ to correspond to a specific $\lambda$. Our goal is to determine the maximal $M_{\lambda}$ for each given $\lambda$.

Additionally, we note that $M^*$ in Theorem 3 is also $\lambda$-dependent. That is, for each $\lambda$, we re-run Eqns (7)-(8) to compute $M^*$.

To address this confusion, in the revised version, we will consistently use $M_{\lambda}$ to indicate the maximal allowed number of perturbed edges (which we still call certified perturbation size) for a specific $\lambda$.

We also included pseudo code for XGNNCert (see Algorithm 1 in Appendix B) to enhance clarity and understanding.

W3: Remove Eq.1 as the problem tackled by the paper is already very well motivated and formulated before providing this very different goal description.

Good suggestion! We have removed Eq.1 in the revised version.

W4. 1) Make clear the hashing is used in Xia et al. (2024); 2) Cite Wang et al. (2022) and correct the statement

Thanks for the suggestion!

1. We revised the texts as suggested. Please see Line 186 in Section 3.1.

2. Please refer to Lines 521–524 in Related Work. We acknowledge that there was a mistake in our previous statement, which has now been corrected in the revised version.

W5. 1) Link discussion on permutation invariant vs variant in Appendix C in the main draft; 2) Show XGNNCert’s classification / explanation performance to different node permutations.

1. See Lines 270-279 the discussion and link to Appendix D.

2. We show the results below under the default setting on the two real-world datasets (Table 9 in the revised version) where we randomly permute the input graph 5 times and report XGNNCert’s averaged classification and performance across the 5 times.

Though XGNNCert is not inherently permutation invariant, we see its classification and explanation performance remain relatively stable to node permutations. (Also see more explanations in Line 1059-1066 in Appendix).

W6: Linking the discussion of generalizing XGNNCert on node-classification tasks in Appendix C to the main body (e.g., background or method)

Please see Lines 145-148 in Section 2 Background in the revised version.

W7: Is $|\bar{\mathcal{E}}_{M}| \leq M$ or $= M$?

It is equal to $M$. We use the exact $M$ (non-existent) edges with top-M scores for our certification by considering that the attacker is allowed to perturb $M$ edges. In the worst-case attack, the M edges $\bar{\mathcal{E}}_{M}$ would be chosen to compete with the true explanatory edges. We also clarify this in the revised version (line 288-289).

W8. Show the figures on the impact of $\rho$ and $\gamma$ in the main paper

Thanks for your suggestions! See the new Figures 4-5 in the revised version.

I thank the authors for their response and clarifications. Most of my concerns are well addressed, except for one important point I will detail below. I increase my score to accept (8) under the assumption that this point will be further addressed.

The $(M_\lambda, \lambda)$-robustness definition is still unclear. Changing the first sentence to "We say an XGNN is $(M_\lambda, \lambda)$−certifiably robust, if, for any graph perturbation attack with a maximal number of $M_\lambda$ perturbed edges on a graph $G$ [...]" does not address this issue, as it did not change the semantic meaning of the definition. The authors admitted to using $M_\lambda$ to denote both, the certified perturbation size (of which there can be many for one $\lambda$) and the maximal certified perturbation size (which is unique). This is one of the main reasons I find the current definition confusing and I do think it is not helping understanding to overload such a critical symbol (and definition) for this work.

I think this can be resolved by e.g. introducing an explicit symbol $M_\lambda^*$ (or similar) to denote the maximal certified perturbation size directly below the $(M_\lambda, \lambda)$-robustness definition by adding a sentence similar in meaning to:

"With $M_\lambda^*$ we denote the maximal $M_\lambda$ associated to a $\lambda$ for which a given XGNN is still certifiable robust."

and make clear in the following text, when what is used. This is one suggestion and I am open to other ideas by the authors.

Dear Reviewer,

Thank you again for your constructive and insightful comments. We have tried our best effort to address all the concerns you raised in your review, and we truly appreciate how your feedback has significantly strengthened our paper.

As the interaction period nears its conclusion, we would greatly value your response. If you have any further concerns or require additional clarifications, please do not hesitate to let us know. We would be happy to address them promptly.

Best regards,

Authors

Thank you for the response, my last concern is now addressed and I'm happy to support acceptance.

I have one comment regarding your newly added footnote 7. You state "We leave it as future work to prove whether the derived certification is tight or not." However, the proof for Thm. 3 assumes that if a poisoned datapoint is in a relevant training set partition that the base classifier associated to that partition should be counted as "having turned". This is the reason of the $\frac{n_y-n_b+I(y<b)-1}{2}$ term in the proof, or? However, a poisoned data point may actually not be able to change the prediction of the relevant base classifier and thus, the certificate is overly pessimistic and hence, not tight, or?