Certified Defense on the Fairness of Graph Neural Networks

We sincerely appreciate the time and efforts you've dedicated to reviewing and providing invaluable feedback. We provide a point-to-point reply below to clarify the mentioned concerns and questions.

---

Reviewer: The general theoretical results in A.9 could use a clearer introduction earlier in the paper, to make it easier for interested readers to gain details about the theorems.

Authors: We thank you for the suggestion. We will revise the discussion of our theoretical results to bring the audience's attention to Appendix A.9.

---

Reviewer: There’s a mention of constraints on node attributes and graph structure that are supposed to be “unnoticeable,” but it’s not clear why these are necessary.

Authors: We thank you for the feedback. First, we note that the constraint of unnoticeability serves as a common setting for potential attacks [1, 2, 3]. This is because if the attacker injects noticeable changes to the data (i.e., performs noticeable attacks), the owner of the data and the user of the model will be aware of the attacks in time, without letting the corrupted output influence the following decision-making process. This directly fails the attack. Correspondingly, in this paper, we adopt such a common setting (i.e., adding unnoticeable constraints) to formulate the potential attacks.

Second, in terms of defense, the constraint of unnoticeability strengthens the significance of obtaining perturbation-invariant budgets. This is because if the value of the perturbation-invariant budget is greater than the constraint of unnoticeability, the GNN model is then theoretically certain to be safe in practice. This is because in such a case, the attacks will either be aware of by the user/data owner or be successfully defended. We will improve the explanation about the constraint of unnoticeability to provide a better understanding in our next version.

[1] Dai, E., et al. Unnoticeable backdoor attacks on graph neural networks. TheWebConf 2023.

[2] Zügner, D., et al. Adversarial attacks on graph neural networks: Perturbations and their patterns. TKDD 2020.

[3] Zhang, X., et al. Gnnguard: Defending graph neural networks against adversarial attacks. NeurIPS 2020.

---

Reviewer: Are there any assumptions about the types of graphs that the framework applies to? For instance, does it matter if they’re directed or undirected, or weighted or unweighted?

Authors: We thank you for the question. We note that ELEGANT can be applied to graphs with binary and directed edges by removing the constraint of the added noise matrix (given by the function $\gamma_{\boldsymbol{A}}$) to be symmetric. In this case, all theoretical analysis will still hold, since all proofs do not rely on the symmetricity of such a noise matrix. For graphs with weighted edges, ELEGANT can be generalized by replacing the binary noise with a continuous noise (e.g., Gaussian noise). The strategy to calculate the perturbation-invariant budgets will be determined by the specific problem settings.

---

We thank you again for your valuable feedback on our work. With the clarification above, we believe that we have responded to and addressed all your concerns with our point-to-point responses — in light of this, we hope you consider raising your score. Please let us know in case there are any other concerns, and if so, we would be happy to respond.

We sincerely appreciate the time and efforts you've dedicated to reviewing and providing invaluable feedback. We provide a point-to-point reply below to clarify the mentioned concerns and questions.

---

Reviewer: The setting, though well-defined theoretically, may lack practical applicability in real-world scenarios. The assumptions about the perturbation budgets and fairness certification requirements may not always align with practical needs, which could limit the framework’s deployment in real-life applications. The practical feasibility of maintaining certified fairness under realistic conditions could be further substantiated.

Authors: We thank the reviewer for the feedback. We would like to highlight two key perspectives of real-world application scenarios below to further substantiate the realistic use of our study.

First, there are unintentional cases where perturbations (e.g., noise) may be made to the data and finally lead to corrupted fairness levels, e.g., human annotators could systematically make mistakes when assigning labels to images of people of a certain skin color [1]. Such situations can also happen in graph machine learning scenarios and finally collapse the fairness in high-stake decision-making scenarios, e.g., fraud detection in financial transaction networks can favor individuals from certain communities. We note that the strength of noise of these scenarios often falls into a certain range, which can be considered as the budget in our work to achieve protection on the fairness of the GNN models. In such cases, our work can be directly adopted to achieve such certified protection without the need for re-training.

Second, there has been plenty of works focusing on the fairness attack and defense problems of machine learning algorithms over traditional i.i.d. data, e.g., [1, 2, 3, 4, 5]. Such a problem has been widely acknowledged to be critical in real-world applications. For example, the developer of a criminal recidivism prediction model could manipulate the data in a discriminatory manner to bias the decision against a certain group of people [1, 6]; in credit or loan applications, adversaries can even profit from such attacks by biasing decisions for their own benefit or depreciating the value and credibility of government and agencies [2]. Especially, graph data has become a key format of data to characterize the complex relationship between data points in these applications, and thus achieving certification for graph machine learning bears critical practical significance under these realistic conditions. Our work can also be directly adopted in these applications to protect fairness, which helps enhance the authority of decision-making agencies and protect the benefit of underrepresented communities.

We thank you again for bringing this up, and we will revise our paper to emphasize the practical significance of our study by adding the discussion presented above. We hope our supplementary discussion addressed your concerns.

[1] Solans, D., Biggio, B., & Castillo, C. (2020). Poisoning attacks on algorithmic fairness. In ECML-PKDD.

[2] Mehrabi, N., Naveed, M., Morstatter, F., & Galstyan, A. (2021). Exacerbating algorithmic bias through fairness attacks. In AAAI.

[3] Van, M. H., Du, W., Wu, X., & Lu, A. (2022). Poisoning attacks on fair machine learning. In DASFAA.

[4] Chhabra, A., Singla, A., & Mohapatra, P. (2021). Fairness degrading adversarial attacks against clustering algorithms. arXiv preprint arXiv:2110.12020.

[5] Jo, C., Sohn, J. Y., & Lee, K. (2022). Breaking fair binary classification with optimal flipping attacks. In ISIT.

[6] Angwin, J., Larson, J., Mattu, S., & Kirchner, L. (2022). Machine bias. In Ethics of data and analytics (pp. 254-264). Auerbach Publications.

---

Reviewer: The Monte Carlo estimation and probabilistic guarantee calculation introduce added complexity to the certification process. While theoretically sound, this approach could pose challenges in implementation, especially in large-scale networks. Further simplification or performance analysis would strengthen the practical value of the proposed solution.

Authors: We thank the reviewer for the feedback. We agree with the reviewer that Monte Carlo estimation can bring concerns about time complexity. Therefore, we have integrated a carefully designed method to reduce the time complexity as introduced in Appendix B.6, which significantly reduces the actual running time in our experiments. Meanwhile, since the proposed approach does not involve any re-training process (which is actually the most costly part), the actual running time is satisfying according to the empirical results shown in Appendix B.8. Finally, we have also elaborated on the discussion of the scalability of the proposed method in Appendix C.7.

We thank you again for bringing this up, and we will elaborate on the discussion about time complexity reduction and running time performance in our paper. We hope our supplementary discussion addressed your concerns.

---

We thank you again for your valuable feedback on our work. With the clarification above, we believe that we have responded to and addressed all your concerns with our point-to-point responses — in light of this, we hope you consider raising your score. Please let us know in case there are any other concerns, and if so, we would be happy to respond.

Dear Reviewer zaDM,

Thank you for your valuable feedback on our work. We have prepared a thorough response to address your concerns. We believe that we have responded to and addressed all your concerns with our responses — in light of this, we hope you consider raising your score.

Notably, given that we are approaching the deadline for the rebuttal phase, we hope we can receive your feedback soon. We thank you again for your efforts and suggestions!

---

Reviewer: As also explained in the paper, fairness improvements observed in the Experimental Results and Conclusions are probably just a by-product of the applied noise, thus there is not of sufficient contribution from the bias mitigation aspect.

Authors: We thank the reviewer for pointing this out, while we feel it is necessary to point out a misunderstanding here: the main focus of this study is to achieve certification over the fairness level of the GNN prediction results. Specifically, we emphasize that the main contribution of this paper is establishing an approach for joint certification over the span of both continuous and discrete input graph data. To the best of our knowledge, this serves as the first work that (1) achieves certified defense for the fairness of GNNs and (2) achieves joint certification against attacks on both node attributes and graph topology. Hence we argue that bringing additional benefits in bias mitigation does not jeopardize the contribution of our paper. We hope our clarification above helps address your concern.

---

Reviewer: The proposed scheme cannot be directly used with fairness metrics that require ground-truth labels. However, the Authors claim that "Here bias is measured with $\Delta_{SP}$ and we have similar observations on $\Delta_{EO}$" without explaining how they used ELEGANT for the certification of $\Delta_{EO}$ (this metric requires ground-truth label information). Also, throughout the paper they never mention this limitation.

Authors: We thank the reviewer for the feedback. We agree with the reviewer that our introduction here is not clear enough and may lead to confusion. We note that experiments based on $\Delta_{EO}$ are conducted according to the predicted labels of a surrogate GNN model that is separately trained on the same dataset with the same training set. We thank you again for pointing this out, and we will elaborate on the experimental setting differences under the two metrics in Section 4 to avoid confusion.

---

We thank you again for your valuable feedback on our work. With the clarification above, we believe that we have responded to and addressed all your concerns with our point-to-point responses — in light of this, we hope you consider raising your score. Please let us know in case there are any other concerns, and if so, we would be happy to respond.

We sincerely appreciate the time and efforts you've dedicated to reviewing and providing invaluable feedback. We provide a point-to-point reply below to clarify the mentioned concerns and questions.

---

Reviewer: The analysis in this paper is developed on existing randomized smoothing works, where certified evaluation has already been studied for both discrete and continuous data. This paper combines such works and reframes the problem from fairness aspect, which I believe limits its novelty in terms of analysis strategy.

Authors: We thank the reviewer for the feedback. We note that our work is fundamentally different from existing works that explore certification on accuracy, and existing techniques cannot be directly adopted to handle the studied problem. We provide a detailed discussion about the differences between ELEGANT and existing works on certified defense below.

Difference 1: Most existing works (e.g., [1, 2, 3]) on certified defense for robustness are only able to achieve robustness certification over each single data point. Nevertheless, in our studied problem, certification over fairness naturally requires achieving certification over a group of nodes at the same time. This is because the level of fairness cannot be determined by the output corresponding to any single node. Such a difference necessitates the indicator function and the formulation of smoothing noise over a set of nodes in our proposed strategy.

Difference 2: Existing works on certified defense for robustness mainly focus on i.i.d. data (e.g., images [1, 4]), while only limited works can be applied to GNNs to properly achieve certification over graph data. The links between nodes and the information propagation mechanism in GNNs make it possible for attackers to influence a large group of nodes by only attacking a few nodes in the graph. Such a difference necessitates formulating the proposed strategy based on a set of vulnerable nodes instead of only focusing on the attack over every single node.

Difference 3: In graphs, most existing works for robustness certification (e.g., [5, 6, 7]) can only defend against attacks on either node attributes or graph structure. Due to the multi-modal input data of GNNs, existing works usually fail to handle the attacks over node attributes and graph structure at the same time. However, ELEGANT is able to defend against attacks over both data modalities. This necessitates using both continuous and discrete noises for smoothing and the certification analysis in the span of the two modalities (as shown in Figure 1).

To summarize, compared with most existing works on certified defense for robustness, ELEGANT differs from other certification works on accuracy in certification goal (Difference 1), the type of data to perform certification on (Difference 2), and the number of data modalities supported (Difference 3). We will add a more detailed discussion about the differences in our next version as suggested. We have further clarified the key novelty and contribution of our study compared with other existing works in Appendix C.5, and we hope our supplementary discussion helps address your concerns.

[1] Cohen, J., Rosenfeld, E., & Kolter, Z. (2019, May). Certified adversarial robustness via randomized smoothing. In international conference on machine learning (pp. 1310-1320). PMLR.

[2] Xiao, C., Chen, Z., Jin, K., Wang, J., Nie, W., Liu, M., ... & Song, D. (2022, September). Densepure: Understanding diffusion models for adversarial robustness. In ICLR.

[3] Li, B., Chen, C., Wang, W., & Carin, L. (2019). Certified adversarial robustness with additive noise. NeurIPS.

[4] Fischer, M., Baader, M., & Vechev, M. (2020). Certified defense to image transformations via randomized smoothing. NeurIPS.

[5] Wang, B., Jia, J., Cao, X., & Gong, N. Z. (2021, August). Certified robustness of graph neural networks against adversarial structural perturbation. In SIGKDD.

[6] Scholten, Y., Schuchardt, J., Geisler, S., Bojchevski, A., & Günnemann, S. (2022). Randomized message-interception smoothing: Gray-box certificates for graph neural networks. NeurIPS.

[7] Geisler, S., Zügner, D., & Günnemann, S. (2020). Reliable graph neural networks via robust aggregation. NeurIPS.

Dear Reviewer XZ95,

Thank you for your valuable feedback on our work. We have prepared a thorough response to address your concerns. We believe that we have responded to and addressed all your concerns with our responses — in light of this, we hope you consider raising your score.

Notably, given that we are approaching the deadline for the rebuttal phase, we hope we can receive your feedback soon. We thank you again for your efforts and suggestions!

We are glad to share that we have achieved a consensus with all other three reviewers on their positive ratings, and we also appreciate your highly positive feedback on our soundness and presentation!

However, considering that you have not replied to our carefully formulated point-to-point responses, we kindly reach out to request your feedback. We believe that we have responded to and addressed all your concerns, and hence we hope you consider raising your score.

We thank you again for your efforts and suggestions, and we look forward to your feedback!

We sincerely thank you for your efforts in helping us improve our paper! With only two days remaining and no response yet to our carefully formulated point-to-point replies, we are kindly reaching out to request your feedback. We believe we have thoroughly addressed all your concerns and respectfully hope you consider raising your score.

Once again, we deeply appreciate your efforts and valuable suggestions, and we look forward to your feedback!

---

Reviewer: For certified robustness methods, they improve the robustness because of the adversarial training stage of the trained model. For this proposed method, bias is decreased without explicit way to improve the fairness. It is highly suggested to conduct some further theoretical analysis for this interesting phenomenon.

Authors: We thank the reviewer for pointing this out, and we agree with the reviewer that this is an important phenomenon our audience can be interested in. We note that achieving better fairness levels is a byproduct of our proposed method. To clarify this, we showed analysis in Appendix B.9. A key reason is that the distribution difference in the node attribute values and edge existence across different subgroups is a significant source of bias [1]. Adding noise on both node attributes and graph topology can reduce distributional divergence and thus mitigate bias. As suggested, we will conduct further theoretical analysis to investigate this phenomenon and add the corresponding discussion to our work. We thank you again for the feedback, and we hope the discussion above addressed your concerns.

[1] Fan, W., et al. Fair graph auto-encoder for unbiased graph representations with Wasserstein distance. ICDM 2021.

---

Reviewer: Experiments on large graphs with non-synthetic edges are suggested.

Authors: We thank the reviewer for the feedback. We agree with the reviewer that conducting experiments based on larger graphs with non-synthetic edges will further validate the effectiveness of the proposed method and enhance our conclusions. Therefore, we have presented comprehensive experimental results on two larger datasets with real-world connections, including Pokec-z and Pokes-n, under multiple popular GNN backbones, and we have presented these supplementary results in Appendix C, including the discussion on the scalability of the proposed method in Appendix C.7. According to the experimental results, we found that the conclusions remain consistent with those introduced in our Section 4, and we hope these additional experiments addressed your concerns.

---

Reviewer: In addition. for certified adversarial robustness methods, they generally are only applicable to the evasion attack, where the perturbations are only conducted on the test samples. For the proposed method, can it defend the poisoning attack?

Authors: We thank the reviewer for the feedback. We note that the main goal of this work is to certifiably defend any optimized GNNs against perturbations that may compromise fairness (as defined in Problem 1), ensuring broad applicability such that the proposed approach can be directly adopted by researchers and practitioners without re-training. This consideration aligns with a widely acknowledged consensus in this line of research. Thus, addressing poisoning attacks is not the focus of our proposed defense method, nor is it the focus of most other existing works on certified defense.

Although the setting of poisoning attacks is not involved in the formulation of Problem 1, we agree with the reviewer that achieving certified defense against poisoning attacks is interesting and worth exploring in our future works.

---

We thank you again for your valuable feedback on our work. With the clarification above, we believe that we have responded to and addressed all your concerns with our point-to-point responses — in light of this, we hope you consider raising your score. Please let us know in case there are any other concerns, and if so, we would be happy to respond.

We sincerely appreciate the time and efforts you've dedicated to reviewing and providing invaluable feedback. We provide a point-to-point reply below to clarify the mentioned concerns and questions.

---

Reviewer: The certified fairness defense is an application of certified robustness by changing the accuracy metric to the fairness metric in the analysis. This is quite straightforward. Hence, the contributions in theoretical analysis is somewhat limited.

Authors: We thank the reviewer for the feedback. We note that our work is fundamentally different from existing works that explore certification on accuracy, and existing techniques cannot be directly adopted to handle the studied problem. We provide a detailed discussion about the differences between ELEGANT and existing works on certified defense below.

Difference 1: Most existing works (e.g., [1, 2, 3]) on certified defense for robustness are only able to achieve robustness certification over each single data point. Nevertheless, in our studied problem, certification over fairness naturally requires achieving certification over a group of nodes at the same time. This is because the level of fairness cannot be determined by the output corresponding to any single node. Such a difference necessitates the indicator function and the formulation of smoothing noise over a set of nodes in our proposed strategy.

Difference 2: Existing works on certified defense for robustness mainly focus on i.i.d. data (e.g., images [1, 4]), while only limited works can be applied to GNNs to properly achieve certification over graph data. The links between nodes and the information propagation mechanism in GNNs make it possible for attackers to influence a large group of nodes by only attacking a few nodes in the graph. Such a difference necessitates formulating the proposed strategy based on a set of vulnerable nodes instead of only focusing on the attack over every single node.

Difference 3: In graphs, most existing works for robustness certification (e.g., [5, 6, 7]) can only defend against attacks on either node attributes or graph structure. Due to the multi-modal input data of GNNs, existing works usually fail to handle the attacks over node attributes and graph structure at the same time. However, ELEGANT is able to defend against attacks over both data modalities. This necessitates using both continuous and discrete noises for smoothing and the certification analysis in the span of the two modalities (as shown in Figure 1).

To summarize, compared with most existing works on certified defense for robustness, our study differs from other certification works on accuracy in certification goal (Difference 1), the type of data to perform certification on (Difference 2), and the number of data modalities supported (Difference 3). We will add a more detailed discussion about the differences in our next version as suggested. We have further clarified the key novelty and contribution of our study compared with other existing works in Appendix C.5, and we hope our supplementary discussion helps address your concerns.

[1] Cohen, J., Rosenfeld, E., & Kolter, Z. (2019, May). Certified adversarial robustness via randomized smoothing. In international conference on machine learning (pp. 1310-1320). PMLR.

[2] Xiao, C., Chen, Z., Jin, K., Wang, J., Nie, W., Liu, M., ... & Song, D. (2022, September). Densepure: Understanding diffusion models for adversarial robustness. In ICLR.

[3] Li, B., Chen, C., Wang, W., & Carin, L. (2019). Certified adversarial robustness with additive noise. NeurIPS.

[4] Fischer, M., Baader, M., & Vechev, M. (2020). Certified defense to image transformations via randomized smoothing. NeurIPS.

[5] Wang, B., Jia, J., Cao, X., & Gong, N. Z. (2021, August). Certified robustness of graph neural networks against adversarial structural perturbation. In SIGKDD.

[6] Scholten, Y., Schuchardt, J., Geisler, S., Bojchevski, A., & Günnemann, S. (2022). Randomized message-interception smoothing: Gray-box certificates for graph neural networks. NeurIPS.

[7] Geisler, S., Zügner, D., & Günnemann, S. (2020). Reliable graph neural networks via robust aggregation. NeurIPS.

Dear Reviewer zjmd,

Thank you for your valuable feedback on our work. We have prepared a thorough response to address your concerns. We believe that we have responded to and addressed all your concerns with our responses — in light of this, we hope you consider raising your score.

Notably, given that we are approaching the deadline for the rebuttal phase, we hope we can receive your feedback soon. We thank you again for your efforts and suggestions!