Certified Defense on the Fairness of Graph Neural Networks

Authors: Yushun Dong, Binchi Zhang, Hanghang Tong, Jundong Li
Primary area: learning on graphs and other geometries & topologies
Keywords: Algorithmic Fairness, Graph Neural Networks, Attack and Defense

Abstract:
Graph Neural Networks (GNNs) have emerged as a prominent graph learning model in various graph-based tasks over the years. Nevertheless, due to the vulnerabilities of GNNs, it has been empirically proved that malicious attackers could easily corrupt the fairness level of their predictions by adding perturbations to the input graph data. In this paper, we take crucial steps to study a novel problem of certifiable defense on the fairness level of GNNs. Specifically, we propose a principled framework named ELEGANT and present a detailed theoretical certification analysis for the fairness of GNNs. ELEGANT takes any GNNs as its backbone, and the fairness level of such a backbone is theoretically impossible to be corrupted under certain perturbation budgets for attackers. Notably, ELEGANT does not have any assumption over the GNN structure or parameters, and does not require re-training the GNNs to realize certification. Hence it can serve as a plug-and-play framework for any optimized GNNs ready to be deployed. We verify the satisfactory effectiveness of ELEGANT in practice through extensive experiments on real-world datasets across different backbones of GNNs, where ELEGANT is also demonstrated to be beneficial for GNN debiasing.

Decision: reject
Reviewer scores: 8, 6, 5, 8

Reviews and discussion:
<thread>
creation date:
1730473038656

thread_type:
official_review

<thread_object>
creator: reviewer_x8pw

<content>
summary:
This paper proposes a framework called ELEGANT, which is designed to guarantee GNNs to be fair, even if they’re under attack within certain limits of budgets. What’s appealing about this framework ELEGANT is that it works with any GNN model as a plug-and-play method, meaning it doesn’t require re-training or making assumptions about the structure of the GNNs. This kind of flexibility and ease of use might make it a valuable tool, and it has the potential to inspire others in the field to build on its ideas.

strengths:
(1) The theoretical analysis is laid out in a detailed and step-by-step manner, walking through the certification on node attributes and graphs with rigor. This could be helpful for readers trying to follow along. 

(2) Unlike most existing certification methods, which don’t address fairness in GNNs, this framework is specifically aimed at fairness issues. This should be considered a significant step for the field, where fairness is a major concern but often gets sidelined. 

(3) Since ELEGANT is a re-training-free, drop-in solution for GNNs, it could be easy for researchers to try it out and see the impact. Its flexibility and practicality make it stand out, and it might encourage more work along these lines. 

(4) The authors evaluated the proposed framework on a solid selection of datasets and GNN models. Their experiments are thorough and show strong evidence of the effectiveness of this proposed approach.

weaknesses:
(1) 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.

(2) 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.

(3) 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?

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730582016482

thread_type:
official_review

<thread_object>
creator: reviewer_xz95

<content>
summary:
This paper proposes a fairness certification framework for Graph Neural Networks (GNNs) based on randomized smoothing. The corresponding framework, ELEGANT, provides a certain level of fairness guarantee for node classification under certain perturbation budgets.

strengths:
- Paper is well-written and fluent.

- The considered research problem is a novel and important one.

- The paper provides theoretical guarantees for fairness certification.

weaknesses:
- 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.

- 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. 

- 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.

questions:
Please see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730611789361

thread_type:
official_review

<thread_object>
creator: reviewer_zadm

<content>
summary:
This paper introduces ELEGANT, a framework for certifiable defense on the fairness of GNNs against adversarial perturbations in node attributes and graph topology. ELEGANT aims to serve as a plug-and-play module that can be applied to any optimized GNN model without altering the underlying structure or requiring retraining. The paper's contributions include a formal problem formulation, algorithmic design leveraging randomized smoothing, and extensive experiments to validate the approach across real-world datasets.

strengths:
- The authors provide comprehensive experimental validation across multiple real-world datasets, demonstrating the generalizability and effectiveness of ELEGANT across different GNN architectures.
- The paper is well-written, with clear explanations of the methodology and experimental setup.

weaknesses:
- 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.
- 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.

questions:
Please refer to the weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730746884087

thread_type:
official_review

<thread_object>
creator: reviewer_zjmd

<content>
summary:
This works aims to formulate the problem of certified defense on the fairness. To achieve this goal, the certified robustness analysis is applied to the certified fairness against input perturbations. More specifically, the analysis about certified fairness defense is conducted on node attributes and graph structures. Experiments are conducted on three real-world datasets.

strengths:
1. This work focuses on an important problem of fairness on graph-structured data. Many real-world applications such as financial analysis and social network analysis requires the fairness to be guaranteed.
2. The authors propose a novel problem of certified fairness defense to avoid the attacks on the fairness. 
3. The analysis in certified fairness defense is solid. And surprisingly, the certified fairness method empirically improve the fairness.

weaknesses:
Overall, the reviewer feel the strengths outweigh the weaknesses. However, several concerns would be highly suggested to be addressed.
1. 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.
2. 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. 
3. Experiments on large graphs with none-synthetic edges are suggested.

questions:
Please refer to the weakness. 

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732786878275

thread_type:
official_comment

<thread_object>
creator: area_chair_6wvn

<content>
comment:
I would like to encourage the reviewers to engage with the author's replies if they have not already done so. At the very least, please 
acknowledge that you have read the rebuttal.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper provide a certificate whether a given fairness metric (e.g. SP or EO) is below some specified threshold. It combines Gaussian smoothing for continuous data and discrete smoothing for the graph structure.

The biggest weakness of the paper is that prior work is not properly credited. Theorem 1 is a direct application of Theorem 1 in [1] (see Eq. 3) for a new classifier where the output in an. indicator function w.r.t. the bias threshold. The core result has been proven not only in [1] but also several times in follow-up papers and does not need to be re-proven! Of course, for a solid theoretical analysis one can prove that Theorem 1 from [1] is applicable, but e.g. Lemma A1 and Lemma A2 are already known. Similarly, Theorem 2 and Theorem 3 can be derived as a simple application of theorems in prior work (see [2] and the generalisation in [3]) under the new fairness setting. The fact that you can arrive at the results in this paper by applying existing theorems from prior work is not a downside, however, omitting or ignoring the contributions of prior work verges on scientific misconduct. The authors should be aware of this issue since it has been pointed out to them during the reviewing process in a prior submission of the same paper, yet they have not updated their work to reflect this.

Similarly, Reviewer zjmd also points out that "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." The "differences" provided by the authors in response are not convincing (see next paragraph). The major contribution of the paper in my opinion is deriving certificates that can handle both continuous and discrete smoothing.

In the rebuttal the authors state "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." Collective certificates are precisely dealing with "certification over a group of nodes". Yet, the paper on collective certificates (Schuchardt et al., 2020) is only cited in passing and the there is no discussion on the differences between the two approaches, and importantly, no comparison to the collective certificates approach which can (in theory) be adapted as a baseline to certify fairness. Similar to before, this again shows a lack of proper discussion of prior work.

As pointed out by Reviewer XZ95, another weakness is that "The proposed scheme cannot be directly used with fairness metrics that require ground-truth labels." In reply, the authors state that they use predicted labels of a surrogate GNN model, however, this is no longer certifying EO but rather some surrogate metric. 

I can only recommend acceptance if the authors update the paper to fix the above issues. To be clear, I think the method itself is worth publishing but the paper in its current form is highly misleading about its contributions.

References:
1. Cohen et al. "Certified adversarial robustness via randomized smoothing"
2. Lee et al. "Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers"
3. Bojchevski et al. "Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more"