Certified Defense on the Fairness of Graph Neural Networks

## Abstract

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. Open-source code can be found at https://github.com/yushundong/ELEGANT .

### 1 Introduction

Graph Neural Networks (GNNs) have emerged to be one of the most popular models to handle learning tasks on graphs (Kipf & Welling, ; Veličković et al., ) and made remarkable achievements in various domains (Feng et al., ; Li et al., ; Jin et al., ).
Nevertheless, as GNNs are increasingly deployed in real-world decision-making scenarios, there has been an increasing societal concern on the fairness of GNN predictions. A primary reason is that most traditional GNNs do not consider
fairness, and thus could exhibit bias against certain demographic subgroups. Here the demographic subgroups are usually divided by certain sensitive attributes, such as gender and race.
To prevent GNNs from exhibiting biased predictions, multiple recent studies proposed fairness-aware GNNs (Agarwal et al., ; Dai & Wang, ; Li et al., ; Kang et al., ; Ju et al., ) such that potential bias could be mitigated.

Unfortunately, despite existing efforts towards fair GNNs, it remains difficult to prevent the corruption of their fairness level due to their common vulnerability of lacking adversarial robustness.
Malicious attackers can easily corrupt the fairness level of GNNs by perturbing the node attributes (i.e., changing the values of node attributes) and/or the graph structure (i.e., adding and deleting edges) (Hussain et al., ; Zhang et al., ), which could lead to serious consequences in the test phase (Dai & Wang, ; Hussain et al., ).
For example, GNNs are leveraged to determine the salary of employees over a network based on their relational information.
Yet, by simply injecting adversarial links in such a network of employees, attackers can make GNNs deliver advantaged salary predictions for a subgroup (e.g., employees with a certain nationality) while damaging the interest of others (Hussain et al., ).
Hence achieving defense over the fairness of GNNs is crucial for safe deployment.

It is worth noting that despite the abundant empirical defense strategies for GNNs (Zhang & Zitnik, ; Entezari et al., ; Jin & Zhang, ; Jin et al., ; Wu et al., ), they are always subsequently defeated by novel attacking techniques (Schuchardt et al., ; Carlini & Wagner, ), and the defense over the fairness of GNNs also faces the same problem.
Therefore, an ideal way is to achieve certifiable defense on fairness (i.e., certified fairness defense).
A few recent works aim to certify the fairness for traditional deep learning models (Khedr & Shoukry, ; Kang et al., ; Jin et al., ; Mangold et al., ; Borca-Tasciuc et al., ; Ruoss et al., ).
Nevertheless, most of them require specially designed training strategies (Khedr & Shoukry, ; Jin et al., ; Ruoss et al., ) and thus cannot be directly applied to optimized GNNs ready to be deployed.
More importantly, they mostly rely on assumptions on the optimization results (Khedr & Shoukry, ; Jin et al., ; Borca-Tasciuc et al., ; Ruoss et al., ) or data distributions (Kang et al., ; Mangold et al., ) over a continuous input space.
Hence they can hardly be generalized to GNNs due to the binary nature of the input graph topology.
Several other works propose certifiable GNN defense approaches to achieve theoretical guarantee (Wang et al., ; Bojchevski & Günnemann, ; Bojchevski et al., ; Jin et al., ; Zügner & Günnemann, ; ).
However, they mainly focus on securing the GNN prediction for a certain individual node to ensure model utility, ignoring the fairness defense over the entire population.
Therefore, despite the significance, the study in this field still remains in its infancy.

It is worth noting that achieving certifiable defense on the fairness of GNNs is a daunting task due to the following key challenges:
(1) Generality:
different types of GNNs could be designed and optimized for different real-world applications (Zhou et al., ). Correspondingly, our first challenge is to design a plug-and-play framework that can achieve certified defense on fairness for any optimized GNN models that are ready to be deployed.
(2) Vulnerability: a plethora of existing studies have empirically verified that most GNNs are sensitive to input data perturbations (Zhang & Zitnik, ; Zügner et al., ; Xu et al., ). In other words, small input perturbations may cause significant changes in the GNN output. Hence our second challenge is to properly mitigate the common vulnerabilities of GNNs without changing its structure or re-training.
(3) Multi-Modality: the input data of GNNs naturally bears multiple modalities. For example, there are node attributes and graph topology in the widely studied attributed networks. In practice, both data modalities may be perturbed by malicious attackers. Therefore, our third challenge is to achieve certified defenses of fairness on both data modalities for GNNs at the same time.

As an early attempt to address the aforementioned challenges, in this paper, we propose a principled framework named ELEGANT (cEtifiabLE GNNs over the fAirNess of PredicTions).
Specifically, we focus on the widely studied task of node classification and formulate a novel research problem of Certifying GNN Classifiers on Fairness.
To handle the first challenge, we propose to develop ELEGANT on top of an optimized GNN model without any assumptions over its structure or parameters.
Hence ELEGANT is able to serve as a plug-and-play framework for any optimized GNN model ready to be deployed.
To handle the second challenge, we propose to leverage randomized smoothing (Wang et al., ; Cohen et al., ) to defend against malicious attacks, where most GNNs can then be more robust over the prediction fairness level.
To handle the third challenge, we propose two different strategies working in a concurrent manner, such that certified defense against the attacks on both the node attributes (i.e., add and subtract attribute values) and graph topology (i.e., flip the existence of edges) can be realized.
Finally, we evaluate the effectiveness of ELEGANT on multiple real-world network datasets. In summary, our contributions are three-fold:
(1) Problem Formulation. We formulate and make an initial investigation on a novel research problem of Certifying GNN Classifiers on Fairness.
(2) Algorithm Design. We propose a framework ELEGANT to achieve certified fairness defense against attacks on both node attributes and graph structure without relying on assumptions about any specific GNNs.
(3) Experimental Evaluation. We perform comprehensive experiments on real-world datasets to verify the effectiveness of ELEGANT.

### 2 Problem Definition

Preliminaries.
Let $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ be an undirected attributed network, where $\mathcal{V}=\{v_{1},...,v_{n}\}$ is the set of $n$ nodes; $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges.
Let $\bm{A}\in\{0,1\}^{n\times n}$ and $\bm{X}\in\mathbb{R}^{n\times d}$ be the adjacency matrix and attribute matrix of $\mathcal{G}$, respectively.
Assume each node in $\mathcal{G}$ represents an individual, and sensitive attribute $s$ divides the population into different demographic subgroups. We follow a widely studied setting (Agarwal et al., ; Dai & Wang, ) to assume the sensitive attribute is binary, i.e., $s\in\{0,1\}$. We use $s_{i}$ to denote the value of the sensitive attribute for node $v_{i}$.
In node classification tasks, we use $\mathcal{V}_{\text{trn}}$ and $\mathcal{V}_{\text{tst}}$ ($\mathcal{V}_{\text{trn}},\mathcal{V}_{\text{tst}}\in\mathcal{V}$) to represent the training and test node set, respectively.
We denote the GNN node classifier as $f_{\bm{\theta}}$ parameterized by $\bm{\theta}$. $f_{\bm{\theta}}$ takes $\bm{A}$ and $\bm{X}$ as input, and outputs $\hat{\bm{Y}}$ as the predictions for the nodes in $\mathcal{G}$. Each row in $\hat{\bm{Y}}$ is a one-hot vector flagging the predicted class.
We use $f_{\bm{\theta}^{*}}$ to denote the GNN with optimal parameter $\bm{\theta}^{*}$ after optimization.

Threat Model. We focus on the attacking scenario of model evasion, i.e., the attack happens in the test phase. In particular, we assume that the victim model under attack is an optimized GNN node classifier $f_{\bm{\theta}^{*}}$.
We follow a widely adopted setting (Bojchevski & Günnemann, ; Zügner & Günnemann, ; Ma et al., ; Mu et al., ) to assume that a subset of nodes $\mathcal{V}_{\text{vul}}\in\mathcal{V}_{\text{tst}}$ are vulnerable to attacks.
Specifically, attackers may perturb their links (i.e., flip the edge existence) to other nodes and/or their node attributes (i.e., change their attribute values).
We denote the perturbations on adjacency matrix as $\bm{A}\oplus\bm{\Delta}_{\bm{A}}$. Here $\oplus$ denotes the element-wise XOR operator; $\bm{\Delta}_{\bm{A}}\in\{0,1\}^{n\times n}$ is the matrix representing the perturbations made by the attacker, where 1 only appears in rows and columns associated with the vulnerable nodes while 0 appears elsewhere.
Correspondingly, in $\bm{\Delta}_{\bm{A}}$, 1 entries represent edges that attackers intend to flip, while 0 entries are associated with edges that are not attacked.
Similarly, we denote the perturbations on node attribute matrix as $\bm{X}+\bm{\Delta}_{\bm{X}}$, where $\bm{\Delta}_{\bm{X}}\in\mathbb{R}^{n\times n}$ is the matrix representing the perturbations made by the attacker.
Usually, if the total magnitude of perturbations is within certain budgets (i.e., $\|\bm{\Delta}_{\bm{A}}\|_{0}\leq\epsilon_{\bm{A}}$ for $\bm{A}$ and $\|\bm{\Delta}_{\bm{X}}\|_{2}\leq\epsilon_{\bm{X}}$ for $\bm{X}$), the perturbations are regarded as unnoticeable.
The goal of an attacker is to add unnoticeable perturbations to nodes in $\mathcal{V}_{\text{vul}}$, such that the GNN predictions for nodes in $\mathcal{V}_{\text{tst}}$ based on the perturbed graph exhibit as much bias as possible.
In addition, we assume that the attacker has access to any information about the victim GNN (i.e., a white-box setting). This serves as the worst case in practice, which makes it even more challenging to achieve defense.

To defend against the aforementioned attacks, we aim to establish a node classifier on top of an optimized GNN backbone, such that this classifier, theoretically, will not exhibit more bias than a given threshold no matter what unnoticeable perturbations (i.e., perturbations within budgets) are added.
We formally formulate
the problem of Certifying GNN Classifiers on Fairness below.

###### Problem 1 .

Certifying GNN Classifiers on Fairness. Given an attributed network $\mathcal{G}$, a test node set $\mathcal{V}_{\text{tst}}$, a vulnerable node set $\mathcal{V}_{\text{vul}}\in\mathcal{V}_{\text{tst}}$, a threshold $\eta$ for the exhibited bias, and an optimized GNN classifier $f_{\bm{\theta}^{*}}$, our goal is to achieve a classifier on top of $f_{\bm{\theta}^{*}}$ associated with budgets $\epsilon_{\bm{A}}$ and $\epsilon_{\bm{X}}$, such that this classifier will bear comparable utility with $f_{\bm{\theta}^{*}}$ but provably not exhibit more bias than $\eta$ on the nodes in $\mathcal{V}_{\text{tst}}$, no matter what unnoticeable node attributes and/or graph structure perturbations (i.e., perturbations within budgets) are made over the nodes in $\mathcal{V}_{\text{vul}}$.

###### Problem 1 .

### 3 The Proposed Framework – ELEGANT

Here we first introduce the modeling of attack and defense on the fairness of GNNs, then discuss how we achieve certified defense on node attributes. After that, we propose a strategy to achieve both types of certified defense (i.e., defense on node attributes and graph structure) at the same time.
Finally, we introduce strategies to achieve the designed certified fairness defense for GNNs in practice.

#### 3.1 Bias Indicator Function

We first construct an indicator $g$ to mathematically model the attack and defense on the fairness of GNNs. Our rationale is to use $g$ to indicate whether the predictions of $f_{\bm{\theta}^{*}}$ exhibit a level of bias exceeding a given threshold.
We present the formal definition below.

###### Definition 1 .

(Bias Indicator Function) Given adjacency matrix $\bm{A}$ and node attribute matrix $\bm{X}$, a test node set $\mathcal{V}_{\text{tst}}$, a threshold $\eta$ for the exhibited bias, and an optimized GNN model $f_{\bm{\theta}^{*}}$, the bias indicator function is defined as $g(f_{\bm{\theta}^{*}},\bm{A},\bm{X},\eta,\mathcal{V}_{\text{tst}})=\mathbbm{1}\left(\pi(f_{\bm{\theta}^{*}}(\bm{A},\bm{X}),\mathcal{V}_{\text{tst}})<\eta\right)$,
where function $\mathbbm{1}(\cdot)$ takes an event as input and outputs 1 if the event happens (otherwise 0); function $\pi(\cdot,\cdot)$ denotes any bias metric for GNN predictions (taken as its first parameter) over a set of nodes (taken as its second parameter). Traditional bias metrics include $\Delta_{\text{SP}}$ (Dai & Wang, ; Dwork et al., ) and $\Delta_{\text{EO}}$ (Dai & Wang, ; Hardt et al., ).

Correspondingly, the goal of the attacker is to ensure that the indicator $g$ outputs 0 for an $\eta$ as large as possible, while the goal of certified defense is to ensure for a given threshold $\eta$, the indicator $g$ provably yields 1 as long as the attacks are within certain budgets.
Note that a reasonable $\eta$ should ensure that $g$ outputs 1 based on the clean graph data (i.e., graph data without any attacks).
Below we first discuss the certified fairness defense over node attributes to maintain the output of $g$ as 1.

###### Definition 1 .

#### 3.2 Certified Fairness Defense over Node Attributes

We now introduce how we achieve certified defense over the node attributes for the fairness of the predictions yielded by $f_{\bm{\theta}^{*}}$.
Specifically, we propose to construct a smoothed bias indicator function $\tilde{g}_{\bm{X}}(f_{\bm{\theta}^{*}},\bm{A},\bm{X},\mathcal{V}_{\text{vul}},\eta)$ via adding Gaussian noise over the node attributes of vulnerable nodes in $\mathcal{V}_{\text{vul}}$.
For simplicity, we use $\tilde{g}_{\bm{X}}(\bm{A},\bm{X})$ to represent the smoothed bias indicator function over node attributes by omitting $\mathcal{V}_{\text{vul}}$, $f_{\bm{\theta}^{*}}$ and $\eta$.
We give the formal definition of $\tilde{g}_{\bm{X}}$ below.

###### Definition 2 .

(Bias Indicator with Node Attribute Smoothing) We define the bias indicator with smoothed node attributes over the nodes in $\mathcal{V}_{\text{vul}}$ as

$$ $\displaystyle\tilde{g}_{\bm{X}}(\bm{A},\bm{X})=\mathrm{argmax}_{c\in\{0,1\}}\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}}),\eta,\mathcal{V}_{\text{tst}})=c).$ (1) $$

Here $\bm{\omega}_{\bm{X}}$ is a $(d\cdot|\mathcal{V}_{\text{vul}}|)$-dimensional vector, where each entry is a random variable following a Gaussian Distribution $\mathcal{N}(0,\sigma^{2})$; $\gamma_{\bm{X}}(\cdot,\cdot)$ maps a vector (its first parameter) to an $(n\times d)$-dimensional matrix, where the vector values are assigned to rows whose indices associate with the indices of a set of nodes (its second parameter) while other matrix entries are zeros.

We denote $\bm{\Gamma}_{\bm{X}}=\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}})$ and $g(\bm{A},\bm{X}+\bm{\Gamma}_{\bm{X}})=g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}}),\eta,\mathcal{V}_{\text{tst}})$ below for simplicity.
We are then able to derive the theoretical certification for the defense on fairness with the defined $\tilde{g}_{\bm{X}}$ in [Definition 2](#Thmdefinition2). We now present the defense certification on fairness below.

###### Theorem 1 .

(Certified Fairness Defense for Node Attributes)
Denote the probability for $g(\bm{A},\bm{X}+\bm{\Gamma}_{\bm{X}})$ to return class $c$ ($c\in\{0,1\}$) as $P(c)$.
Then $\tilde{g}_{\bm{X}}(\bm{A},\bm{X})$ will provably return $\mathrm{argmax}_{c\in\{0,1\}}P(c)$ for any perturbations (over the attributes of vulnerable nodes) within an $l_{2}$ radius $\tilde{\epsilon_{\bm{X}}}=\frac{\sigma}{2}\left(\Phi^{-1}(\max_{c\in\{0,1\}}P(c))-\Phi^{-1}(\min_{c\in\{0,1\}}P(c))\right)$, where $\Phi^{-1}(\cdot)$ is the inverse of the standard Gaussian cumulative distribution function.

Correspondingly, for an $\eta$ that enables $\max_{c\in\{0,1\}}P(c)=1$, it is then safe to say that no matter what perturbations $\bm{\Delta}_{\bm{X}}$ are made on vulnerable nodes, as long as $\|\bm{\Delta}_{\bm{X}}\|_{2}\leq\tilde{\epsilon}_{\bm{X}}$, the constructed $\tilde{g}_{\bm{X}}$ will provably not yield predictions for $\mathcal{V}_{\text{tst}}$ with a level of bias exceeding $\eta$.
Nevertheless, it is worth noting that, in GNNs, perturbations may also be made on the structure of the vulnerable nodes, i.e., adding and/or deleting edges between these vulnerable nodes and any nodes in the graph. Hence it is also necessary to achieve certified defense against such structural attacks. Here we propose to also smooth the constructed $\tilde{g}_{\bm{X}}$ over the graph structure (of the vulnerable nodes) for the purpose of certified fairness defense on the graph structure. However, the adjacency matrix describing the graph structure is naturally binary, and thus should be smoothed in a different way.

###### Definition 2 .

###### Theorem 1 .

#### 3.3 Certified Fairness Defense over Node Attributes and Graph Structure

We then introduce achieving certified fairness defense against attacks on both node attributes and graph structure.
We propose a strategy to leverage noise following Bernoulli distribution to smooth $\tilde{g}_{\bm{X}}$ over the rows and columns (due to symmetricity) associated with the vulnerable nodes in $\bm{A}$.
In this way, we can smooth both the node attributes and graph structure for $g$ in a randomized manner, and we denote the constructed function as $\tilde{g}_{\bm{A},\bm{X}}$.
We present the formal definition below.

###### Definition 3 .

(Bias Indicator with Attribute-Structure Smoothing) We define the bias indicator function with smoothed node attributes and graph structure over the nodes in $\mathcal{V}_{\text{vul}}$ as

$$ $\displaystyle\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X})=\mathrm{argmax}_{c\in\{0,1\}}\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\gamma_{\bm{A}}(\bm{\omega}_{\bm{A}},\mathcal{V}_{\text{vul}}),\bm{X})=c).$ (2) $$

Here $\bm{\omega}_{\bm{A}}$ is an $(n\cdot|\mathcal{V}_{\text{vul}}|)$-dimensional random variable, where each dimension takes 0 and 1 with the probability of $\beta$ ($\beta>0.5$) and $1-\beta$, respectively; function $\gamma_{\bm{A}}(\cdot,\cdot)$ maps a vector (its first parameter) to a symmetric $(n\times n)$-dimensional matrix, where the vector values are assigned to rows whose indices associated with the indices of a set of nodes (its second parameter) and then mirrored to the corresponding columns, while other values are left as zeros.

Figure: Figure 1: An example illustrating how ELEGANT works.
Refer to caption: /html/2311.02757/assets/x1.png

We let $\bm{\Gamma}_{\bm{A}}=\gamma_{\bm{A}}(\bm{\omega}_{\bm{A}},\mathcal{V}_{\text{vul}})$ below for simplicity.
To better illustrate how classifier $\tilde{g}_{\bm{A},\bm{X}}$ achieves certified fairness defense over both data modalities of an attributed network, we provide an exemplary case in [Figure 1](#S3.F1).
Here we assume node $v_{i}\in\mathcal{V}_{\text{vul}}$. Considering the high dimensionality of node attributes and adjacency matrix, we only analyze two entries $\bm{X}_{i,j}$ and $\bm{A}_{i,j}$ and omit other entries after noise for simplicity. Here the superscript $(i,j)$ represents the $i$-th row and $j$-th column of a matrix.
Under binary noise, entry $\bm{A}_{i,j}$ only has two possible values, i.e., $\bm{A}_{i,j}\oplus 0$ and $\bm{A}_{i,j}\oplus 1$. We denote the two cases as Case (1) and Case (2), respectively.
We assume that the area where $g$ returns 1 in the span of the two input random entries of $g$ (i.e., $\bm{X}_{i,j}$ and $\bm{A}_{i,j}$ under random noise) is an ellipse (marked out with green), where the decision boundary is marked out with deep green.
In Case (1), $\bm{X}_{i,j}$ under random noise follows a Gaussian distribution, whose probability density function is marked out as deep red. We assume that, in this case, the integral of the probability density function within the range of the ellipse (marked out with shallow red) is larger than 0.5. Correspondingly, according to [Definition 2](#Thmdefinition2), $\tilde{g}_{\bm{X}}$ returns 1 in this case.
In Case (2), we similarly mark out the probability density function and the area used for integral within the range of the ellipse. We assume that in this case, the integral is smaller than 0.5, and thus $\tilde{g}_{\bm{X}}$ returns 0.
Note that to compute the output of $\tilde{g}_{\bm{A},\bm{X}}$, we need to identify the output of $\tilde{g}_{\bm{X}}$ with the largest probability. Notice that $\beta>0.5$, we have that $\bm{A}_{i,j}\oplus 0$ happens with a larger probability than $\bm{A}_{i,j}\oplus 1$.
Therefore, $\tilde{g}_{\bm{A},\bm{X}}$ outputs 1 in this example. In other words, the bias level of the predictions of $f_{\bm{\theta}^{*}}$ is satisfying (i.e., smaller than $\eta$) based on the classifier $\tilde{g}_{\bm{A},\bm{X}}$.

Below we introduce a desirable property of $\tilde{g}_{\bm{A},\bm{X}}$, i.e., certified fairness defense associated with tractable budgets over node attributes and graph topology can be achieved at the same time.

###### Lemma 1 .

(Perturbation-Invariant Budgets Existence)
There exist tractable budgets $\epsilon_{\bm{A}}$ and $\epsilon_{\bm{X}}$, such that for any perturbations made over the node attributes and graph structure of the vulnerable nodes within $\epsilon_{\bm{A}}$ and $\epsilon_{\bm{X}}$, $\tilde{g}_{\bm{A},\bm{X}}$ provably maintains the same classification results.

Correspondingly, for an $\eta$ that enables $\tilde{g}_{\bm{A},\bm{X}}$ to return 1, we are then able to achieve certified fairness defense over $\tilde{g}_{\bm{A},\bm{X}}$ against perturbations on both node attributes and graph structure.
Below we derive the certified fairness defense budgets over the graph structure $\epsilon_{\bm{A}}$ and node attributes $\epsilon_{\bm{X}}$ for $\tilde{g}_{\bm{A},\bm{X}}$.
We first introduce the derivation of $\epsilon_{\bm{A}}$.
Here, our rationale is: considering that $\tilde{g}_{\bm{A},\bm{X}}$ is a binary classifier, we need to ensure that under structure attacks, the probability of $\tilde{g}_{\bm{X}}$ returning 1 (denoted as $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$) is provably greater than 0.5, such that $\tilde{g}_{\bm{A},\bm{X}}$ will still return 1.
To this end, we propose to derive a lower bound of $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$, which we denote as $\underline{P_{\tilde{g}_{\bm{X}}=1}}$.
Finally, we identify the largest perturbation size that keeps such a lower bound larger than 0.5, and the identified perturbation size is then the graph structure perturbation budget.
We present the lower bound of $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ below.

###### Lemma 2 .

(Positive Probability Bound Under Noises) There exists a tractable $\underline{P_{\tilde{g}_{\bm{X}}=1}}\in(0,1)$, such that $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)\geq\underline{P_{\tilde{g}_{\bm{X}}=1}}$.

To derive the perturbation budget $\epsilon_{\bm{A}}$, we only need to find a $\bm{\Delta}_{\bm{A}}$ with the largest $l_{0}$-norm that still enables $\underline{P_{\tilde{g}_{\bm{X}}=1}}$ to be greater than 0.5 (according to [Definition 3](#Thmdefinition3)).
Correspondingly, we derive the theoretical perturbation-invariant budget $\epsilon_{\bm{A}}$ in [Theorem 2](#Thmtheorem2) below.

###### Theorem 2 .

(Certified Defense Budget for Structure Perturbations)
The certified defense budget over the graph structure $\epsilon_{\bm{A}}$ for $\tilde{g}_{\bm{A},\bm{X}}$ is given as

$$ $\displaystyle\epsilon_{\bm{A}}=\max\tilde{\epsilon_{\bm{A}}},\;\text{s.t.}\;\underline{P_{\tilde{g}_{\bm{X}}=1}}>0.5,\;\forall\;\|\bm{\Delta}_{\bm{A}}\|_{0}\leq\tilde{\epsilon_{\bm{A}}}.$ (3) $$

To solve the optimization problem in [Equation 3](#S3.E3), we introduce [Theorem 3](#Thmtheorem3) to compute $\underline{P_{\tilde{g}_{\bm{X}}=1}}$.

###### Theorem 3 .

(Positive Probability Lower Bound) We have $\underline{P_{\tilde{g}_{\bm{X}}=1}}=\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H})$.
Here $\mathcal{H}=\cup_{i=\mu+1}^{n\cdot|\mathcal{V}_{\text{vul}}|}\mathcal{H}_{i}\cup\mathcal{H}_{\mu}^{\prime}$; $\mathcal{H}_{i}$ and $\mu$ are given by:

$$ $\displaystyle\mathcal{H}_{i}=\left\{\bar{\bm{A}}:\frac{\mathrm{Pr}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}=\bar{\bm{A}})}{\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}=\bar{\bm{A}})}=\left(\frac{\beta}{1-\beta}\right)^{i};\forall v_{i}\in\mathcal{V}\setminus\mathcal{V}_{\text{vul}},\|\bar{\bm{A}}_{i}-\bm{A}_{i}\|_{0}=0\right\};$ $$

$$ $\displaystyle\mu=\mathrm{argmax}_{-n\cdot|\mathcal{V}_{\text{vul}}|\leq j\leq n\cdot|\mathcal{V}_{\text{vul}}|}j\text{, s.t. }\operatorname{Pr}\left(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}\in\cup_{k=j}^{n\cdot|\mathcal{V}_{\text{vul}}|}\mathcal{H}_{j}\right)\geq\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1);$ $$

$\mathcal{H}_{\mu}^{\prime}$ is any subregion of $\mathcal{H}_{\mu}$ that satisfies

$$ $\displaystyle\mathrm{Pr}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{\mu}^{\prime})=\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)-\operatorname{Pr}\left(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}\in\cup_{k=j}^{n\cdot|\mathcal{V}_{\text{vul}}|}\mathcal{H}_{j}\right).$ (4) $$

We provide detailed steps to solve the optimization problem given in [Equation 3](#S3.E3) in Appendix.
Now we introduce the theoretical analysis of how to derive $\epsilon_{\bm{X}}$ in [Theorem 4](#Thmtheorem4).

###### Theorem 4 .

(Certified Defense Budget for Attribute Perturbations)
Denote $\bar{\mathcal{A}}$ as the set of all possible $(n\times n)$-matrices, where entries in rows whose indices associate with those vulnerable nodes may take 1 or 0, while other entries are zeros.
The certified defense budget $\epsilon_{\bm{X}}$ for $\tilde{g}_{\bm{A},\bm{X}}$ is given as

$$ $\displaystyle\epsilon_{\bm{X}}=\min\left\{\tilde{\epsilon_{\bm{X}}}:\tilde{\epsilon_{\bm{X}}}\;\text{is derived with classifier}\;\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})\text{ , where}\;\bm{\Gamma}_{\bm{A}}\in\bar{\mathcal{A}}\right\}.$ (5) $$

###### Definition 3 .

###### Lemma 1 .

###### Lemma 2 .

###### Theorem 2 .

###### Theorem 3 .

###### Theorem 4 .

#### 3.4 Certification in Practice

Estimating the Predicted Label Probabilities.
According to [Definition 3](#Thmdefinition3), it is necessary to obtain $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=c)$ ($c\in\{0,1\}$) to determine the output of classifier $\tilde{g}_{\bm{X}}$.
We propose to leverage a Monte Carlo method to estimate such a probability. Specifically, we first randomly pick $N$ samples of $\bm{\Gamma}_{\bm{A}}$ as $\bar{\mathcal{A}}^{\prime}$ ($\bar{\mathcal{A}}^{\prime}\subset\bar{\mathcal{A}}$). Considering the output of $\tilde{g}_{\bm{X}}$ is binary, we then follow a common strategy (Cohen et al., ) to consider this problem as a parameter estimation of a Binomial distribution:
we first count the number of returned label 1 and 0 under noise as $N_{1}$ and $N_{0}$ ($N_{1}+N_{0}=N$); then we choose a confidence level $1-\alpha$ and take the $\alpha$-th quantile of the beta distribution with parameters $N_{1}$ and $N_{0}$ as the estimated probability lower bound for returning label $c=1$. We proved that all theoretical analysis still holds true for such an estimation in Appendix.
We follow a similar strategy to estimate the probability lower bound of yielding 1 for $g(\bm{A},\bm{X}+\bm{\Gamma}_{\bm{X}})$.

Obtaining Fair Classification Results. After achieving certified fairness defense based on $\tilde{g}_{\bm{A},\bm{X}}$, we also need to obtain the corresponding node classification results (given by $f_{\bm{\theta}^{*}}$) over $\mathcal{V}_{\text{tst}}$. We propose to collect all classification results associated with the sampled $\bm{\Gamma}_{\bm{A}}^{\prime}\in\bar{\mathcal{A}}^{\prime}$ that leads to an estimated lower bound of $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}^{\prime},\bm{X})=1)$ to be larger than 0.5 as $\hat{\mathcal{Y}}^{\prime}$.
Here $\hat{\mathcal{Y}}^{\prime}$ is a set of output matrices of $f_{\bm{\theta}^{*}}$, where each matrix consists of the one-hot output classification results (as each row in the matrix) for all nodes.
We propose to take $\mathrm{argmin}_{\hat{\bm{Y}}^{\prime}}\pi(\hat{\bm{Y}}^{\prime},\mathcal{V}_{\text{tst}}),s.t.\;\hat{\bm{Y}}^{\prime}\in\hat{\mathcal{Y}}^{\prime}$ as the final node classification results.
Correspondingly,
consider $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}^{\prime},\bm{X})=1)$ falls into the confidence interval characterized by $1-\alpha$, we have a neat probabilistic theoretical guarantee below.

###### Proposition 1 .

(Probabilistic Guarantee for the Fairness Level of Node Classification).
For $\hat{\bm{Y}}=\mathrm{argmin}_{\hat{\bm{Y}}^{\prime}}\pi(\hat{\bm{Y}}^{\prime},\mathcal{V}_{\text{tst}}),s.t.\;\hat{\bm{Y}}^{\prime}\in\hat{\mathcal{Y}}^{\prime}$, we have $\mathrm{Pr}(\pi(\hat{\bm{Y}},\mathcal{V}_{\text{tst}})>\eta)<0.5^{|\hat{\mathcal{Y}}^{\prime}|}$.

Note that for a large enough sample size $N$, the cardinality of $\hat{\mathcal{Y}}^{\prime}$ also tends to be large in practice. Hence it is safe to argue that $\mathrm{Pr}(\pi(\hat{\bm{Y}},\mathcal{V}_{\text{tst}})>\eta)$ tends to be small enough. In other words, we have a probability that is large enough to obtain results with a bias level lower than the given threshold $\eta$.

Calculation of Perturbation Budgets.
We calculate $\epsilon_{\bm{A}}$ by solving the optimization problem given in [Equation 3](#S3.E3), and we provide the completed procedure in Appendix. For $\epsilon_{\bm{X}}$, we utilize a Monte Carlo method to estimate its value. More specifically, we leverage $\text{min}\{\tilde{\epsilon_{\bm{X}}}:\tilde{\epsilon_{\bm{X}}}\;\text{is derived with classifier}\;\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}^{\prime},\bm{X})\text{ , where}\;\bm{\Gamma}_{\bm{A}}^{\prime}\in\bar{\mathcal{A}}^{\prime}\}$ to estimate the value of $\epsilon_{\bm{X}}$.

###### Proposition 1 .

### 4 Experimental Evaluations

In this section, we aim to answer three research questions: RQ1: How well does ELEGANT perform in achieving certified fairness defense?
RQ2: How does ELEGANT perform under fairness attacks compared to other popular fairness-aware GNNs?
RQ3: How does ELEGANT perform under different settings of parameters?
We present the main experimental settings and representative results in this section due to space limits. Detailed settings and supplementary experiments are in Appendix.

#### 4.1 Experimental Settings

Downstream Task and Datasets.
We focus on the widely studied node classification task, which is one of the most representative tasks in the domain of learning on graphs.
We adopt three real-world network datasets that are widely used to perform studies on the fairness of GNNs, namely German Credit (Agarwal et al., ; Asuncion & Newman, ), Recidivism (Agarwal et al., ; Jordan & Freiburger, ), and Credit Defaulter (Agarwal et al., ; Yeh & Lien, ).
We provide their basic information, including how these datasets are built and their statistics, in Appendix.

Evaluation Metrics. We perform evaluation from three main perspectives, including model utility, fairness, and certified defense.
To evaluate utility, we adopt the node classification accuracy. To evaluate fairness, we adopt the widely used metrics $\Delta_{\text{SP}}$ (measuring bias under Statistical Parity) and $\Delta_{\text{EO}}$ (measuring bias under Equal Opportunity).
To evaluate certified defense, we extend a traditional metric named Certified Accuracy (Wang et al., ; Cohen et al., ) in our experiments, and we name it as Fairness Certification Rate (FCR).
Specifically, existing GNN certification works mainly focus on a certain individual node, and utilize certified accuracy to measure the ratio of nodes that are correctly classified and also successfully certified out of all test nodes (Wang et al., ). In this paper, however, we perform certified (fairness) defense for individuals over an entire test set (instead of for any specific individual). Accordingly, we propose to sample multiple test sets out of nodes that are not involved in the training and validation set. Then we perform certified fairness defense for all sampled test sets, and utilize the ratio of test sets that are successfully certified over all sampled sets as the metric of certified defense. The rationale of FCR is leveraging a Monte Carlo method to estimate the probability of being successfully certified for a randomly sampled test node set.

GNN Backbones and Baselines. Note that ELEGANT serves as a plug-and-play framework for any optimized GNNs ready to be deployed.
To evaluate the generality of ELEGANT across GNNs, we adopt three of the most representative GNNs spanning across simple and complex ones, namely Graph Sample and Aggregate Networks (Hamilton et al., ) (GraphSAGE), Graph Convolutional Networks (Kipf & Welling, ) (GCN), and Jumping Knowledge Networks (JK).
Note that to the best of our knowledge, existing works on fairness certification cannot certify the attacks over two data modalities (i.e., continuous node attributes and binary graph topology) at the same time, and thus cannot be naively generalized onto GNNs.
Hence we compare the usability of GNNs before and after certification with ELEGANT.
Moreover, we also adopt two popular fairness-aware GNNs as baselines to evaluate bias mitigation, including FairGNN (Dai & Wang, ) and NIFTY (Agarwal et al., ). Specifically, FairGNN utilizes adversarial learning to debias node embeddings, while NIFTY designs regularization terms to debias node embeddings.

Threat Models.
We propose to evaluate the performance of ELEGANT and other fairness-aware GNN models under actual attacks on fairness.
We first introduce the threat model over graph structure. To the best of our knowledge, FA-GNN (Hussain et al., ) is the only work that performs graph structure attacks targeting the fairness of GNNs.
Hence we adopt FA-GNN to attack graph structure.
In terms of node attributes, to the best of our knowledge, no existing work has made any explorations. Hence we directly utilize gradient ascend to perform attacks. Specifically, after structure attacks have been performed, we identify the top-ranked node attribute elements (out of the node attribute matrix) that positively influence the exhibited bias the most via gradient ascend. For any given budget (of attacks) on node attributes, we add perturbations to these elements in proportion to their gradients.

**Table 1: Comparison between vanilla GNNs and certified GNNs under ELEGANT over three popular GNNs across three real-world datasets. Here ACC denotes node classification accuracy, and E- prefix marks out the GNNs under ELEGANT with certification. $\uparrow$ denotes the larger, the better; $\downarrow$ represents the opposite. Numerical values are in percentage, and the best ones are in bold.**
|  | German Credit |  | Recidivism |  | Credit Defaulter |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | ACC ($\uparrow$) | Bias ($\downarrow$) | FCR ($\uparrow$) |  | ACC ($\uparrow$) | Bias ($\downarrow$) | FCR ($\uparrow$) |  | ACC ($\uparrow$) | Bias ($\downarrow$) | FCR ($\uparrow$) |
| SAGE | 67.3 ±2.14 | 50.6 ±15.9 | N/A |  | 89.8 ±0.66 | 9.36 ±3.15 | N/A |  | 75.9 ±2.18 | 13.0 ±4.01 | N/A |
| E-SAGE | 71.0 ±1.27 | 16.3 ±10.9 | 98.7 ±1.89 |  | 89.9 ±0.90 | 6.39 ±2.85 | 94.3 ±6.65 |  | 73.4 ±0.50 | 8.94 ±0.99 | 94.3 ±3.30 |
| GCN | 59.6 ±3.64 | 37.4 ±3.24 | N/A |  | 90.5 ±0.73 | 10.1 ±3.01 | N/A |  | 65.8 ±0.29 | 11.1 ±3.22 | N/A |
| E-GCN | 58.2 ±1.82 | 3.52 ±3.77 | 96.3 ±1.89 |  | 89.6 ±0.74 | 9.56 ±3.22 | 96.0 ±3.56 |  | 65.2 ±0.99 | 7.28 ±1.46 | 92.7 ±5.19 |
| JK | 63.3 ±4.11 | 41.2 ±18.1 | N/A |  | 91.9 ±0.54 | 10.1 ±3.15 | N/A |  | 76.6 ±0.69 | 9.24 ±0.60 | N/A |
| E-JK | 62.3 ±4.07 | 22.4 ±1.95 | 97.0 ±3.00 |  | 89.3 ±0.33 | 6.26 ±2.78 | 89.5 ±10.5 |  | 77.7 ±0.27 | 3.37 ±2.64 | 99.3 ±0.47 |

#### 4.2 RQ1: Fairness Certification Effectiveness

To answer RQ1, we investigate the performance of different GNNs after certification across different real-world attributed network datasets over FCR, utility, and fairness.
We present the experimental results across three GNN backbones and three real-world attributed network datasets in [Table 1](#S4.T1). Here bias is measured with $\Delta_{\text{SP}}$, and we have similar observations on $\Delta_{\text{EO}}$.
We summarize the main observations as follows:
(1) Fairness Certification Rate (FCR).
We observe that ELEGANT realizes values of FCR around or even higher than 90% for all three GNN backbones and three attributed network datasets, especially for the German Credit dataset, where vanilla GNNs tend to exhibit a high level of bias. The corresponding intuition is that, for nodes in any randomly sampled test set, we have a probability around or higher than 90% to successfully certify the fairness level of the predictions yielded by the GNN model with our proposed framework ELEGANT. Hence ELEGANT achieves a satisfying fairness certification rate across all adopted GNN backbones and datasets.
(2) Utility.
We found that compared with those vanilla GNN backbones, certified GNNs with ELEGANT also exhibit comparable and even higher node classification accuracy values in all cases. Hence we conclude that our proposed framework ELEGANT does not significantly jeopardize the utility of the vanilla GNN models, and those certified GNNs with ELEGANT still bear a high level of usability in terms of node classification accuracy.
(3) Fairness.
We also observe that, in all cases, certified GNNs with ELEGANT achieve better performances in terms of algorithmic fairness compared with those vanilla GNNs. This demonstrates that the proposed framework ELEGANT also contributes to bias mitigation. We conjecture that such an advantage of debiasing could be a result of adding random noise on node attributes and graph topology.
In fact, existing works found that the distribution difference in the node attribute values and edge existence across different subgroups is a significant source of bias (Dong et al., ; Dai & Wang, ; Fan et al., ). However, adding noise on both node attributes and graph topology may reduce such distributional divergence and mitigate bias.

Figure: Figure 2: The bias levels of GCN, E-GCN, FairGNN, and NIFTY under fairness attacks on German Credit. The shaded bar indicates that certified budget $\epsilon_{\bm{A}}\leq\|\bm{\Delta}_{\bm{A}}\|_{0}$ or $\epsilon_{\bm{X}}\leq\|\bm{\Delta}_{\bm{X}}\|_{2}$. The y-axis is in logarithmic scale for better visualization purposes.
Refer to caption: /html/2311.02757/assets/x2.png

#### 4.3 RQ2: Fairness Certification under Attacks

To answer RQ2, we perform attacks on the fairness of GCN, E-GCN, FairGNN (with a GCN backbone), and NIFTY (with a GCN backbone). Considering the large size of the quadratic space spanned by the size of perturbations $\bm{\Delta}_{\bm{A}}$ and $\bm{\Delta}_{\bm{X}}$ made by attackers, we present the evaluation under four representative ($\|\bm{\Delta}_{\bm{A}}\|_{0}$, $\|\bm{\Delta}_{\bm{X}}\|_{2}$) pairs. We set the threshold for bias $\eta$ to be 50% higher than the fairness level of the vanilla GCN model on clean data, since it empirically helps to achieve a high certification success rate under large perturbations.

We present the fairness levels of the four models in terms of $\Delta_{\text{EO}}$ in [Figure 2](#S4.F2.5), and we also have similar observations on $\Delta_{\text{SP}}$ and other GNNs/datasets.
We summarize the main observations as follows:
(1) Fairness. We found that the GCN model with the proposed framework ELEGANT achieves the lowest level of bias in all cases of fairness attacks. This observation is consistent with the superiority in fairness found in [Table 1](#S4.T1), which demonstrates that the fairness superiority of ELEGANT maintains even under attacks within a wide range of attacking perturbation sizes.
(2) Certification on Fairness. We now compare the performance of E-GCN across different attacking perturbation sizes. We observed that under relatively small attacking perturbation sizes, i.e., ($2^{0},10^{-1}$), ($2^{1},10^{0}$), and ($2^{2},10^{1}$), ELEGANT successfully achieves certification over fairness, and the bias level increases slowly as the size of attacks increases.
Under relatively large attacking perturbation size, i.e., ($2^{3},10^{2}$), although the attacking budgets go beyond the certified budgets, GCN under ELEGANT still exhibits a fairness level far lower than the given bias threshold $\eta$, and the fairness superiority still maintains.
This corroborates that the adopted estimation strategies are safe in achieving fairness certification.

#### 4.4 RQ3: Parameter Study

To answer RQ3, we propose to perform parameter study focusing on two most critical parameters, $\sigma$ and $\beta$.
To examine how $\sigma$ and $\beta$ influence the effectiveness of ELEGANT in terms of both FCR and certified defense budgets, we set numerical ranges for $\epsilon_{\bm{X}}$ (from 0 to 1e1) and $\epsilon_{\bm{A}}$ (from 0 to $2^{4}$) and divide the two ranges into grids.
In both ranges, we consider the dividing values of the grids as thresholds for certification budgets.
In other words, under each threshold, we only consider the test sets with the corresponding certified defense budget being larger than this threshold as successfully certified ones, and the values of FCR are re-computed accordingly.
Our rationale here is that with the thresholds (for $\epsilon_{\bm{X}}$ and $\epsilon_{\bm{A}}$) increasing, if FCR reduces slowly, this demonstrates that most successfully certified test sets are associated with large certified defense budgets. However, if FCR reduces fast, then most successfully certified test sets only bear small certified defense budgets.

Here we present the experimental results of $\sigma$ and $\beta$ with the most widely used GCN model based on German Credit in [Figure 3(a)](#S4.F3.sf1) and Credit Defaulter in [Figure 3(b)](#S4.F3.sf2), respectively. We also have similar observations on other GNNs and datasets.
We summarize the main observations as follows:
(1) Analysis on $\sigma$.
We observe that most cases with larger $\sigma$ are associated with a larger FCR compared with the cases where $\sigma$ is relatively small. In other words, larger values of $\sigma$ typically make FCR reduce slower w.r.t. the increasing of $\epsilon_{\bm{X}}$ threshold. This indicates that increasing the value of $\sigma$ helps realize larger certified defense budgets on node attributes, i.e., the increase of $\sigma$ dominates the tendency of $\epsilon_{\bm{X}}$ given in [Theorem 4](#Thmtheorem4).
Nevertheless, it is worth mentioning that if $\sigma$ is too large, the information encoded in the node attributes could be swamped by the Gaussian noise and finally corrupt the classification accuracy. Hence moderately large values for $\sigma$, e.g., 5e-1 and 5e0, are recommended.
(2) Analysis on $\beta$.
We found that (1) for cases with relatively large $\beta$ (e.g., 0.8 and 0.9), the FCR also tends to be larger (compared with cases where $\beta$ is smaller) at $\epsilon_{\bm{A}}$ threshold being 0.
Such a tendency is reasonable, since in these cases, the expected magnitude of the added Bernoulli noise is small. Correspondingly, GNNs under ELEGANT perform similarly to vanilla GNNs, and thus an $\eta$ larger than the bias level of vanilla GNNs is easier to be satisfied (compared with cases under smaller values of $\beta$); (2) for cases with relatively large $\beta$, the value of FCR reduces faster (w.r.t. $\epsilon_{\bm{A}}$ threshold) than cases where $\beta$ is smaller.
Therefore, we recommend that for any test set of nodes: (1) if the primary goal is to achieve certification with a high probability, then larger values for $\beta$ (e.g., 0.8 and 0.9) would be preferred; (2) if the goal is to achieve certification with larger certified defense budgets on the graph topology, then smaller values for $\beta$ (e.g., 0.6 and 0.7) should be selected.

Figure: (a) FCR of certification for $\sigma$ over node attributes
Refer to caption: /html/2311.02757/assets/x3.png

### 5 Related Work

Algorithmic Fairness in GNNs.
Existing GNN works on fairness mainly focus on group fairness and individual fairness (Dong et al., ; Wang et al., ; Song et al., ). Specifically, group fairness requires that each demographic subgroup (divided by sensitive attributes such as gender and race) in the graph should have their fair share of interest based on predictions (M. et al., ). Adversarial training is among the most popular strategies (Dai & Wang, ; Dong et al., ).
In addition, regularization (Agarwal et al., ; Fan et al., ; Zhang et al., ), topology modification (Dong et al., ; Spinelli et al., ), and orthogonal projection (Palowitch & Perozzi, ) are also commonly used strategies. On the other hand, individual fairness it requires that similar individuals should be treated similarly (Dwork et al., ), where such similarity may be determined in different ways (Kang et al., ; Dong et al., ). Designing optimization regularization terms to promote individual fairness for GNNs is a common strategy (Fan et al., ; Dong et al., ; Song et al., ).

GNN Defense Against Attacks.
Existing works on GNN defense are categorized into five mainstreams, namely adversarial training (Xu et al., ; Dai et al., ; Wang et al., ), graph data purification (Entezari et al., ; Jin et al., ; Wu et al., ; Kipf & Welling, ), perturbation detection (Xu et al., ; Ioannidis et al., ; Jin et al., ), and certified defense (Schuchardt et al., ; Wang et al., ; Bojchevski & Günnemann, ; Zügner & Günnemann, ; Jia et al., ).
Among them, certified defense is the only approach that secures GNNs theoretically, such that attackers cannot find any adversary to fool the GNNs (Schuchardt et al., ; Wang et al., ; Bojchevski & Günnemann, ; Zügner & Günnemann, ; Jia et al., ).
Note that most certified defense approaches only secure the prediction for a specific data point (e.g., a node in node classification). Different from them, our proposed ELEGANT enables us to secure the level of fairness for GNNs, which are influenced by all predictions in the test set.

### 6 Conclusion

In this paper, we take initial steps to tackle a novel problem of certifying GNN node classifiers on fairness.
To address this problem, we propose a principled framework, ELEGANT, which achieves certification on top of any optimized GNN node classifier associated with certain perturbation budgets, such that it is impossible for attackers to corrupt the fairness level of predictions within such budgets. Notably, ELEGANT is designed to serve as a plug-and-play framework for any optimized GNNs ready to be deployed and does not rely on any assumption over GNN structure or parameters.
Extensive experiments verify the satisfying effectiveness of ELEGANT. In addition, we also found ELEGANT beneficial to GNN debiasing, and explored how its parameters influence the certification performance.
We leave certifying the fairness level of GNNs over other learning tasks on graphs as future works.

## Appendix

### Appendix A Proofs

For better clarity, for a matrix $\bm{X}$, we use $\bm{X}[i,j]$ to denote the element at the $i$-th row and the $j$-th column; for a vector $\bm{x}$, we use $\bm{x}[i]$ to denote its $i$-th component.

#### A.1 Proof of Theorem 1

To prove [Theorem 1](#Thmtheorem1), we formulate the theoretical prerequisite that [Theorem 1](#Thmtheorem1) relies on as [1](#Thmlmma1).
Similarly, the proof of [1](#Thmlmma1) relies on the results in [2](#Thmlmma2), and the proof of [2](#Thmlmma2) is based on [3](#Thmlmma3).

###### Proof.

For simplification, we reshape the matrix $\bm{X}\in\mathbb{R}^{n\times d}$ to the vector $\bm{x}\in\mathbb{R}^{nd}$.
We denote $h_{c}(\bm{x})=\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}}),\eta,\mathcal{V}_{\text{tst}})=c)$ as the function that returns $P(c)$.
Without loss of generality, we assume $\mathrm{argmax}_{c\in\{0,1\}}P(c)=1$, so we have $\mathrm{argmin}_{c\in\{0,1\}}P(c)=0$ consequently.
We use $\bm{\Delta}_{\bm{X}}$ to denote a perturbation on $\bm{X}$ that satisfies $\bm{\Delta}_{\bm{X}}\leq\tilde{\epsilon_{\bm{X}}}$, and $\bm{\Delta}_{\bm{x}}$ to denote the reshaped vector of $\bm{\Delta}_{\bm{X}}$.
Denote $\Phi^{-1}(\cdot)$ as the inverse of the standard Gaussian cumulative distribution function.
According to [1](#Thmlmma1), we have $\Phi^{-1}(h_{c}(\bm{x}))$ as a Lipschitz continuous function with a Lipschitz constant of $\frac{1}{\sigma}$ where $\sigma$ is the standard deviation of the Gaussian noise $\bm{\omega}_{\bm{X}}$.
Based on the property of Lipschitz continuous functions, we have

$$ $|\Phi^{-1}(h_{c}(\bm{x}+\bm{\Delta}_{\bm{x}}))-\Phi^{-1}(h_{c}(\bm{x}))|\leq\frac{\tilde{\epsilon_{\bm{X}}}}{\sigma}.$ $$

Correspondingly, we have the following bounds for the output probabilities of class 0 0 and $1$

$$ $\Phi^{-1}(h_{1}(\bm{x}+\bm{\Delta}_{\bm{x}}))-\Phi^{-1}(h_{1}(\bm{x}))\geq-\frac{\tilde{\epsilon_{\bm{X}}}}{\sigma},$ (6) $$

$$ $\Phi^{-1}(h_{0}(\bm{x}+\bm{\Delta}_{\bm{x}}))-\Phi^{-1}(h_{0}(\bm{x}))\leq\frac{\tilde{\epsilon_{\bm{X}}}}{\sigma}.$ (7) $$

Combine [Equation 6](#A1.E6) and [Equation 7](#A1.E7), and we have

$$ $\Phi^{-1}(h_{1}(\bm{x}+\bm{\Delta}_{\bm{x}}))-\Phi^{-1}(h_{0}(\bm{x}+\bm{\Delta}_{\bm{x}}))\geq\Phi^{-1}(h_{1}(\bm{x}))-\Phi^{-1}(h_{0}(\bm{x}))-\frac{2\tilde{\epsilon_{\bm{X}}}}{\sigma}.$ (8) $$

Recall that $\tilde{\epsilon_{\bm{X}}}=\frac{\sigma}{2}(\Phi^{-1}(\max_{c\in\{0,1\}}P(c))-\Phi^{-1}(\min_{c\in\{0,1\}}P(c)))=\frac{\sigma}{2}(\Phi^{-1}(P(1))-\Phi^{-1}(P(0)))=\frac{\sigma}{2}(\Phi^{-1}(h_{1}(\bm{x}))-\Phi^{-1}(h_{0}(\bm{x})))$, combine this condition with [Equation 8](#A1.E8), we have

$$ $\Phi^{-1}(h_{1}(\bm{x}+\bm{\Delta}_{\bm{x}}))-\Phi^{-1}(h_{0}(\bm{x}+\bm{\Delta}_{\bm{x}}))\geq 0.$ (9) $$

Based on the strictly non-decreasing property of $\Phi(\cdot)$, we have

$$ $h_{1}(\bm{x}+\bm{\Delta}_{\bm{x}})\geq h_{0}(\bm{x}+\bm{\Delta}_{\bm{x}}).$ (10) $$

In [Equation 10](#A1.E10), $h_{1}(\bm{x}+\bm{\Delta}_{\bm{x}})$ and $h_{0}(\bm{x}+\bm{\Delta}_{\bm{x}})$ stand for the output probabilities of class $1$ and 0 0 after the perturbation, correspondingly.
Hence, the output for $\tilde{g}_{\bm{X}}$ will not change after the perturbation (still class $1$).
Noting that the exact probabilities $\max_{c\in\{0,1\}}P(c)$ and $\min_{c\in\{0,1\}}P(c)$ are difficult to calculate in practice, we can use a tractable lower bound $\underline{p_{\text{max}}}$ and upper bound $\overline{p_{\text{min}}}$ such that $\max_{c\in\{0,1\}}P(c)\geq\underline{p_{\text{max}}}\geq\overline{p_{\text{min}}}\geq\min_{c\in\{0,1\}}P(c)$ to replace them in $\tilde{\epsilon_{\bm{X}}}$ as $\tilde{\epsilon_{\bm{X}}}=\frac{\sigma}{2}(\Phi^{-1}(\underline{p_{\text{max}}})-\Phi^{-1}(\overline{p_{\text{min}}}))$.
Because the practical perturbation budget $\tilde{\epsilon_{\bm{X}}}$ derived by tractable bounds is smaller than the true budget, we can still obtain the same result as [Equation 10](#A1.E10).
∎

###### Lemma A 1 .

Denote $h_{c}(\bm{x})=\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}}),\eta,\mathcal{V}_{\text{tst}})=c)$ as the function that returns $P(c)$. Then, the function $\Phi^{-1}(h_{c}(\bm{x}))$ is a Lipschitz continuous function with respect to $\bm{x}$ with a Lipschitz constant $L_{\Phi}=\frac{1}{\sigma}$, where $\Phi^{-1}(\cdot)$ is the inverse of the standard Gaussian cumulative distribution function.

###### Proof.

To prove the Lipschitz continuity of $\Phi^{-1}(h_{c}(\bm{x}))$, we should find an upper bound of the norm of the gradient $\|\nabla_{\bm{x}}\Phi^{-1}(h_{c}(\bm{x}))\|_{2}$, denoted as $L_{\Phi}$. The gradient $\nabla_{\bm{x}}\Phi^{-1}(h_{c}(\bm{x}))$ is computed as

$$ $\displaystyle\nabla_{\bm{x}}\Phi^{-1}(h_{c}(\bm{x}))$ $\displaystyle=\frac{\nabla_{\bm{x}}h_{c}(\bm{x})}{\Phi^{\prime}(\Phi^{-1}(h_{c}(\bm{x})))}$ $\displaystyle=\sqrt{2\pi}\mathrm{exp}(\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2})\nabla_{\bm{x}}h_{c}(\bm{x}).$ $$

Therefore, the norm $\|\nabla_{\bm{x}}\Phi^{-1}(h_{c}(\bm{x}))\|_{2}$ is computed as

$$ $\|\nabla_{\bm{x}}\Phi^{-1}(h_{c}(\bm{x}))\|_{2}=\sqrt{2\pi}\mathrm{exp}(\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2})\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}.$ $$

According to [2](#Thmlmma2), the upper bound of $\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}$ is $\frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2})$. Consequently, we have

$$ $\|\nabla_{\bm{x}}\Phi^{-1}(h_{c}(\bm{x}))\|_{2}\leq\frac{1}{\sigma}.$ $$

Finally, we have obtained the Lipschitz constant of $\Phi^{-1}(h_{c}(\bm{x}))$ as $L_{\Phi}=\frac{1}{\sigma}$ and verified its Lipschitz continuity.

∎

###### Lemma A 2 .

Denote $h_{c}(\bm{x})=\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}}),\eta,\mathcal{V}_{\text{tst}})=c)$ as the function that returns $P(c)$. Then, the function $h_{c}(\bm{x})$ is a Lipschitz continuous function with respect to $\bm{x}$ with a Lipschitz constant $L_{h}=\frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2})$, where $\Phi^{-1}(\cdot)$ is the inverse of the standard Gaussian cumulative distribution function.

###### Proof.

To prove the Lipschitz continuity of $h_{c}(\bm{x})$, we should prove that the norm of the gradient $\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}$ is bounded by some constant $L_{h}$, i.e. $L_{h}=\mathrm{sup}_{h}\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}$.
Let $\bm{\omega}_{\text{vul}}=\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}})\in\mathbb{R}^{nd}$ where $\bm{\omega}_{\text{vul}}[i]\sim\mathcal{N}(0,\sigma^{2})$ when $i\in\mathcal{V}_{\text{vul}}$ and $\bm{\omega}_{\text{vul}}[i]=0$ otherwise.
Consequently, we have $h_{c}(\bm{x})=\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\bm{\omega}_{\text{vul}},\eta,\mathcal{V}_{\text{tst}})=1)$.
Then, we compute the gradient $\nabla_{\bm{x}}h_{c}(\bm{x})$ as follows.

$$ $\displaystyle\nabla_{\bm{x}}h_{c}(\bm{x})$ $\displaystyle=\nabla_{\bm{x}}\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\bm{\omega}_{\text{vul}},\eta,\mathcal{V}_{\text{tst}})=c)$ $\displaystyle=\nabla_{\bm{x}}\mathbb{E}_{\bm{\omega}_{\text{vul}}}[g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\bm{\omega}_{\text{vul}},\eta,\mathcal{V}_{\text{tst}})]$ $\displaystyle=\nabla_{\bm{x}}\int_{\mathbb{R}^{|\mathcal{V}_{\text{vul}}|}}g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\bm{\omega}_{\text{vul}},\eta,\mathcal{V}_{\text{tst}})(2\pi\sigma^{2})^{-\frac{|\mathcal{V}_{\text{vul}}|}{2}}\mathrm{exp}(-\frac{\|\bm{\omega}_{\text{vul}}\|_{2}^{2}}{2\sigma^{2}})d\bm{\omega}_{\text{vul}}.$ $$

Substituting $\bm{t}=\bm{x}+\bm{\omega}_{\text{vul}}$ into the above integration, we have

$$ $\displaystyle\nabla_{\bm{x}}h_{c}(\bm{x})$ $\displaystyle=\nabla_{\bm{x}}\int_{\mathbb{R}^{|\mathcal{V}_{\text{vul}}|}}g(f_{\bm{\theta}^{*}},\bm{A},\bm{t},\eta,\mathcal{V}_{\text{tst}})(2\pi\sigma^{2})^{-\frac{|\mathcal{V}_{\text{vul}}|}{2}}\mathrm{exp}(-\frac{\|\bm{t}-\bm{x}\|_{2}^{2}}{2\sigma^{2}})d\bm{t}$ $\displaystyle=\int_{\mathbb{R}^{|\mathcal{V}_{\text{vul}}|}}g(f_{\bm{\theta}^{*}},\bm{A},\bm{t},\eta,\mathcal{V}_{\text{tst}})(2\pi\sigma^{2})^{-\frac{|\mathcal{V}_{\text{vul}}|}{2}}\nabla_{\bm{x}}\mathrm{exp}(-\frac{\|\bm{t}-\bm{x}\|_{2}^{2}}{2\sigma^{2}})d\bm{t}$ $\displaystyle=\int_{\mathbb{R}^{|\mathcal{V}_{\text{vul}}|}}g(f_{\bm{\theta}^{*}},\bm{A},\bm{t},\eta,\mathcal{V}_{\text{tst}})(2\pi\sigma^{2})^{-\frac{|\mathcal{V}_{\text{vul}}|}{2}}\mathrm{exp}(-\frac{\|\bm{t}-\bm{x}\|_{2}^{2}}{2\sigma^{2}})\frac{\bm{t}-\bm{x}}{\sigma^{2}}d\bm{t}$ $\displaystyle=\int_{\mathbb{R}^{|\mathcal{V}_{\text{vul}}|}}g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\bm{\omega}_{\text{vul}},\eta,\mathcal{V}_{\text{tst}})(2\pi\sigma^{2})^{-\frac{|\mathcal{V}_{\text{vul}}|}{2}}\mathrm{exp}(-\frac{\|\bm{\omega}_{\text{vul}}\|_{2}^{2}}{2\sigma^{2}})\frac{\bm{\omega}_{\text{vul}}}{\sigma^{2}}d\bm{\omega}_{\text{vul}}$ $\displaystyle=\frac{1}{\sigma^{2}}\mathbb{E}_{\bm{\omega}_{\text{vul}}}[\bm{\omega}_{\text{vul}}g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\bm{\omega}_{\text{vul}},\eta,\mathcal{V}_{\text{tst}})]$ $\displaystyle=\frac{1}{\sigma}\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{\omega}_{\text{vul}}^{\prime}g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\sigma\bm{\omega}_{\text{vul}}^{\prime},\eta,\mathcal{V}_{\text{tst}})].$ $$

Here, $\bm{\omega}_{\text{vul}}^{\prime}$ is a normalized random vector that $\bm{\omega}_{\text{vul}}^{\prime}[i]\sim\mathcal{N}(0,1)$ when $i\in\mathcal{V}_{\text{vul}}$ and $\bm{\omega}_{\text{vul}}^{\prime}[i]=0$ otherwise. Next, we compute the norm of the gradient $\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}$ as

$$ $\displaystyle\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}$ $\displaystyle=\mathrm{sup}_{\|\bm{v}\|_{2}=1}\bm{v}^{\top}\nabla_{\bm{x}}h_{c}(\bm{x})$ (11) $\displaystyle=\frac{1}{\sigma}\mathrm{sup}_{\|\bm{v}\|_{2}=1}\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\sigma\bm{\omega}_{\text{vul}}^{\prime},\eta,\mathcal{V}_{\text{tst}})].$ $$

To find $L_{h}$, we should consider the worst case (with the largest Lipschitz constant) among all possible classifiers. We let $\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=g(f_{\bm{\theta}^{*}},\bm{A},\bm{x}+\sigma\bm{\omega}_{\text{vul}}^{\prime},\eta,\mathcal{V}_{\text{tst}})$. Then, we have the following optimization problem for solving $L_{h}$

$$ $\displaystyle\mathrm{sup}_{\tilde{g}}\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]$ (12) $\displaystyle s.t.\quad\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})$ $\displaystyle\in[0,1],\ \|\bm{v}\|_{2}=1,\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]=h_{c}(\bm{x}).$ $$

The rationale of this optimization problem is that we aim to find the function with the largest Lipschitz constant (objective) among all possible classifiers $\tilde{g}$ with the same smoothing output $h_{c}(\bm{x})$ (constraints) when fixing the variable $\bm{v}$. After solving this problem, we can find the largest objective among all possible $\bm{v}$ as $L_{h}$. To solve this problem, we have the following lemma.

Based on [3](#Thmlmma3), we have $\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=\mathbbm{1}(\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))$ as the solution of the optimization problem in [Equation 12](#A1.E12). Next, we can compute the maximal objective when fixing the variable $\bm{v}$ as

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\cdot\mathbbm{1}(\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))]$ (13) $\displaystyle=$ $\displaystyle\mathbb{E}_{\omega\sim\mathcal{N}(0,\varepsilon_{\bm{v}}^{2})}[\omega\cdot\mathbbm{1}(\omega\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{\omega^{\prime}\sim\mathcal{N}(0,1)}[\varepsilon_{\bm{v}}\omega^{\prime}\cdot\mathbbm{1}(\omega^{\prime}\geq-\Phi^{-1}(h_{c}(\bm{x})))]\;(\text{let}\;\omega=\varepsilon_{\bm{v}}\omega^{\prime})$ $\displaystyle=$ $\displaystyle\frac{\varepsilon_{\bm{v}}}{\sqrt{2\pi}}\int_{-\Phi^{-1}(h_{c}(\bm{x}))}^{+\infty}\omega\mathrm{exp}(-\frac{\omega}{2})d\omega$ $\displaystyle=$ $\displaystyle\frac{\varepsilon_{\bm{v}}}{\sqrt{2\pi}}\mathrm{exp}(-\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2}).$ $$

Therefore, we have $\mathrm{sup}_{\tilde{g}}\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]=\frac{\varepsilon_{\bm{v}}}{\sqrt{2\pi}}\mathrm{exp}(-\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2})$. Combining this result with [Equation 11](#A1.E11), we have

$$ $\displaystyle L_{h}=$ $\displaystyle\mathrm{sup}_{h}\|\nabla_{\bm{x}}h_{c}(\bm{x})\|_{2}$ $\displaystyle=$ $\displaystyle\mathrm{sup}_{\tilde{g},\|\bm{v}\|_{2}=1}\frac{1}{\sigma}\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]$ $\displaystyle=$ $\displaystyle\mathrm{sup}_{\|\bm{v}\|_{2}=1}\frac{\varepsilon_{\bm{v}}}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2})$ $\displaystyle=$ $\displaystyle\frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{1}{2}\Phi^{-1}(h_{c}(\bm{x}))^{2}).$ $$

Finally, we have proved that the function $h_{c}(\bm{x})=\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\gamma_{\bm{X}}(\bm{\omega}_{\bm{X}},\mathcal{V}_{\text{vul}}),\eta,\mathcal{V}_{\text{tst}})=c)$ is a Lipschitz continuous function with respect to variable $\bm{x}$.
∎

###### Lemma A 3 .

The solution to the optimization problem in [Equation 12](#A1.E12) is $\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=\mathbbm{1}(\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))$, where $\varepsilon_{\bm{v}}^{2}=\sum_{i\in\mathcal{V}_{\text{vul}}}\bm{v}[i]^{2}$.

###### Proof.

First, we clarify the rationale for solving this problem. We note that $\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\sim\mathcal{N}(0,\varepsilon_{\bm{v}}^{2})$ (based on the property of independent and identically distributed Gaussian), this optimization problem can be regarded as the reweighting of a Gaussian distribution where the range of the weight function $\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})$ is $[0,1]$ and the constraint of the weight function is given by $\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]=h_{c}(\bm{x})$.
A straightforward solution here is to let the weight function at a large value of $\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}$ as large as possible. We let $\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=1$ where $\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x}))(\bm{\omega}_{\text{vul}}^{\prime})$ and $\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=0$ otherwise. Here $\Phi(\cdot)$ is the cumulative distribution function of $\mathcal{N}(0,1)$.

Next, we prove that $\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=\mathbbm{1}(\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))$ is the exact solution of the optimization problem in [Equation 12](#A1.E12).
We first verify that $\tilde{g}^{*}$ is a solution. It is obvious that $\tilde{g}^{*}$ suffices the first two constraints because the range of the indicator function is $\{0,1\}$. For the last constraint, $\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\mathbbm{1}(\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))]$ is actually the probability of $\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}$ being larger than $-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x}))$, which equals to $(h_{c}(\bm{x})$ apparently because $\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}/\varepsilon_{\bm{v}}\sim\mathcal{N}(0,1)$. Therefore, $\tilde{g}^{*}$ satisfies all three constraints.
We then prove that $\tilde{g}^{*}$ is the optimal solution. We assume $\tilde{g}\neq\tilde{g}^{*}$ is another classifier that also suffices the constraints in the optimization problem in [Equation 12](#A1.E12). We use $\mathcal{S}$ to denote the support set $\{s\ |\ \tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})\neq 0\}$. Based on the final constraint in the optimization problem in [Equation 12](#A1.E12), we have

$$ $\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]=0.$ $$

We divide this equation into two parts as

$$ $\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[(\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime}))\mathbbm{1}(\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S})]+\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[(\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime}))\mathbbm{1}(\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S}^{\complement})]=0,$ (14) $$

where $\mathcal{S}^{\complement}$ denotes the complement set of $\mathcal{S}$.
We know that $\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})\equiv 1$ for $\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S}$. We also know that $\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})\leq 1$ and $\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})$ cannot always equal to $1$ for $\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S}$ because $\tilde{g}\neq\tilde{g}^{*}$. Therefore, we have

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[(\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime}))\mathbbm{1}(\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S})]>0,$ (15) $\displaystyle\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[(\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime}))\mathbbm{1}(\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S}^{\complement})]<0.$ $$

Moreover, we have $\bm{v}^{\top}\bm{\omega}_{1}>\bm{v}^{\top}\bm{\omega}_{0}$ for any $\bm{\omega}_{1}\in\mathcal{S}$ and $\bm{\omega}_{0}\in\mathcal{S}^{\complement}$. Finally, combine this result with [Equation 14](#A1.E14) and [Equation 15](#A1.E15), we have

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}(\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})$ $\displaystyle-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime}))\mathbbm{1}(\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S})]$ $\displaystyle+\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}(\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})-\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime}))\mathbbm{1}(\bm{\omega}_{\text{vul}}^{\prime}\in\mathcal{S}^{\complement})]>0.$ $$

Consequently, we have $\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]-\mathbb{E}_{\bm{\omega}_{\text{vul}}^{\prime}}[\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\tilde{g}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})]>0$. Therefore, we have proved that $\tilde{g}^{*}(\bm{A},\bm{\omega}_{\text{vul}}^{\prime})=\mathbbm{1}(\bm{v}^{\top}\bm{\omega}_{\text{vul}}^{\prime}\geq-\varepsilon_{\bm{v}}\Phi^{-1}(h_{c}(\bm{x})))$ is the exact optimal solution of the optimization problem in [Equation 12](#A1.E12).
∎

###### Proof.

###### Lemma A 1 .

###### Proof.

###### Lemma A 2 .

###### Proof.

###### Lemma A 3 .

###### Proof.

#### A.2 Proof of Lemma 1

###### Proof.

The tractable perturbation budgets $\epsilon_{\bm{A}}$ and $\epsilon_{\bm{X}}$ can be obtained according to [Theorem 2](#Thmtheorem2) and [Theorem 4](#Thmtheorem4), correspondingly.
∎

###### Proof.

#### A.3 Proof of Lemma 2

###### Proof.

The tractable probability lower bound $\underline{P_{\tilde{g}_{\bm{X}}=1}}$ can be obtained according to [Theorem 3](#Thmtheorem3).
∎

###### Proof.

#### A.4 Proof of Theorem 2

###### Proof.

To certify the fairness level, we assume that $\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X})=1$.
Refer to [Lemma 2](#Thmlemma2), we have $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)\geq\underline{P_{\tilde{g}_{\bm{X}}=1}}$. For any structure perturbation $\|\bm{\Delta}_{\bm{A}}\|_{0}\leq\tilde{\epsilon_{\bm{A}}}$, we combine this result with [Equation 3](#S3.E3) and obtain that

$$ $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)\geq\underline{P_{\tilde{g}_{\bm{X}}=1}}>0.5,$ (16) $$

As a consequence, we have $\tilde{g}_{\bm{A},\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}},\bm{X})=\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X})$ for any structure perturbation $\|\bm{\Delta}_{\bm{A}}\|_{0}\leq\tilde{\epsilon_{\bm{A}}}$.
∎

###### Proof.

#### A.5 Proof of Theorem 3

###### Proof.

To prove [Theorem 3](#Thmtheorem3), we formulate the theoretical prerequisite that [Theorem 3](#Thmtheorem3) relies on as [4](#Thmlmma4).
The following [4](#Thmlmma4) indicates the relation between $\bm{A}\oplus\bm{\Gamma}_{\bm{A}}$ and $\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}$.

###### Lemma A 4 .

Let $\bm{X}$ and $\bm{Y}$ be two random vectors in the discrete space $\{0,1\}^{n}$ with prabability distributions $\mathrm{Pr}(\bm{X})$ and $\mathrm{Pr}(\bm{Y})$, correspondingly. Let $h:\{0,1\}^{n}\rightarrow\{0,1\}$ be a random or deterministic function. Let $\mathcal{S}_{1}=\{\bm{z}\in\{0,1\}^{n}:\frac{\mathrm{Pr}(\bm{X}=\bm{z})}{\mathrm{Pr}(\bm{Y}=\bm{z})}>r\}$ and $\mathcal{S}_{2}=\{\bm{z}\in\{0,1\}^{n}:\frac{\mathrm{Pr}(\bm{X}=\bm{z})}{\mathrm{Pr}(\bm{Y}=\bm{z})}=r\}$ for some $r>0$. Assume $\mathcal{S}_{3}\subseteq\mathcal{S}_{2}$ and $\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{3}$. If $\mathrm{Pr}(h(\bm{X})=1)\geq\mathrm{Pr}(\bm{X}\in\mathcal{S})$, then $\mathrm{Pr}(h(\bm{Y})=1)\geq\mathrm{Pr}(\bm{Y}\in\mathcal{S})$.

###### Proof.

Note that we have $\frac{\mathrm{Pr}(\bm{X}=\bm{z})}{\mathrm{Pr}(\bm{Y}=\bm{z})}\geq r$ for any $\bm{z}\in\mathcal{S}$ and $\frac{\mathrm{Pr}(\bm{X}=\bm{z})}{\mathrm{Pr}(\bm{Y}=\bm{z})}\leq r$ for any $\bm{z}\in\mathcal{S}^{\complement}$. Assuming $h$ is random, we have

$$ $\displaystyle\mathrm{Pr}(h(\bm{Y})=1)-\mathrm{Pr}(\bm{Y}\in\mathcal{S})$ $\displaystyle=$ $\displaystyle\sum_{\bm{z}\in\{0,1\}^{n}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{Y}=\bm{z})-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(\bm{Y}=\bm{z})$ $\displaystyle=$ $\displaystyle\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{Y}=\bm{z})+\sum_{\bm{z}\in\mathcal{S}^{\complement}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{Y}=\bm{z})$ $\displaystyle\quad\quad-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{Y}=\bm{z})-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=0)\mathrm{Pr}(\bm{Y}=\bm{z})$ $\displaystyle=$ $\displaystyle\sum_{\bm{z}\in\mathcal{S}^{\complement}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{Y}=\bm{z})-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=0)\mathrm{Pr}(\bm{Y}=\bm{z})$ $\displaystyle\geq$ $\displaystyle\frac{1}{r}(\sum_{\bm{z}\in\mathcal{S}^{\complement}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{X}=\bm{z})-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=0)\mathrm{Pr}(\bm{X}=\bm{z}))$ $\displaystyle=$ $\displaystyle\frac{1}{r}(\sum_{\bm{z}\in\mathcal{S}^{\complement}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{X}=\bm{z})+\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{X}=\bm{z})$ $\displaystyle\quad\quad-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=0)\mathrm{Pr}(\bm{X}=\bm{z})-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{X}=\bm{z}))$ $\displaystyle=$ $\displaystyle\frac{1}{r}(\sum_{\bm{z}\in\{0,1\}^{n}}\mathrm{Pr}(h(\bm{z})=1)\mathrm{Pr}(\bm{X}=\bm{z})-\sum_{\bm{z}\in\mathcal{S}}\mathrm{Pr}(\bm{X}=\bm{z}))$ $\displaystyle=$ $\displaystyle\frac{1}{r}(\mathrm{Pr}(h(\bm{X})=1)-\mathrm{Pr}(\bm{X}\in\mathcal{S}))$ $\displaystyle\geq$ $\displaystyle 0.$ $$

∎

Based on the definition of $\mathcal{H}$, we have $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}},\bm{X})=1)\geq\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\in\mathcal{H})$ distinctly.
According to [4](#Thmlmma4) (let $\bm{Y}=\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}$, $\bm{X}=\bm{A}\oplus\bm{\Delta}_{\bm{A}}$, $\mathcal{S}=\mathcal{H}$, and $h=\tilde{g}_{\bm{X}}$), we have $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)\geq\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H})$ ($\bm{X}$ can be seen as a constant here), correspondingly.
Noting that the exact probability $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ is difficult to calculate, we use a practical lower bound $\underline{P_{\tilde{g}_{\bm{X}}=1}}^{*}\leq\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ to replace it in practice. Because we also have $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Delta}_{\bm{A}},\bm{X})=1)\geq\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\in\mathcal{H})$ for $\mathcal{H}$ derived by $\underline{P_{\tilde{g}_{\bm{X}}=1}}^{*}$, the proof still holds.

∎

###### Proof.

###### Lemma A 4 .

###### Proof.

#### A.6 Solving the Optimization Problem in Theorem 2

We can compute $\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H})$ as

$$ $\displaystyle\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H})=\sum_{j=\mu+1}^{n|\mathcal{V}_{\text{vul}}|}$ $\displaystyle\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{j})$ (17) $\displaystyle+(\underline{P_{\tilde{g}_{\bm{X}}=1}}^{*}-\sum_{j=\mu+1}^{n|\mathcal{V}_{\text{vul}}|}\mathrm{Pr}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{j}))/(\frac{\beta}{1-\beta})^{\mu}.$ $$

To compute [Equation 17](#A1.E17), we calculate the probability $\mathrm{Pr}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{m})$ and $\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{m})$ as

$$ $\mathrm{Pr}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{m})=\sum_{j=\max\{0,m\}}^{\min\{n|\mathcal{V}_{\text{vul}}|,n|\mathcal{V}_{\text{vul}}|+m\}}\beta_{n|\mathcal{V}_{\text{vul}}|-(j-m)}(1-\beta)^{(j-m)}t(m,j),$ (18) $$

$$ $\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H}_{m})=\sum_{j=\max\{0,m\}}^{\min\{n|\mathcal{V}_{\text{vul}}|,n|\mathcal{V}_{\text{vul}}|+m\}}\beta_{n|\mathcal{V}_{\text{vul}}|-j}(1-\beta)^{j}t(m,j),$ (19) $$

where $-n|\mathcal{V}_{\text{vul}}|\leq m\leq n|\mathcal{V}_{\text{vul}}|$, $\|\bm{\Delta}_{\bm{A}}\|_{0}\leq k$, and $t(m,j)$ is defined as

$$ $t(m,j)=\left\{\begin{array}[]{ll}0,&\text{if}\;(m+k)\;\mathrm{mod}\;2\neq 0,\\ 0,&\text{if}\;2j-m<k,\\ \tbinom{n|\mathcal{V}_{\text{vul}}|-k}{\frac{2j-m-k}{2}}\tbinom{k}{\frac{k-m}{2}},&\text{otherwise}.\end{array}\right.$ (20) $$

With [Equation 17](#A1.E17), we can traverse the perturbation budget $\|\bm{\Delta}_{\bm{A}}\|_{0}$ over $1,2,\dots$ until $\mathrm{Pr}(\bm{A}\oplus\bm{\Delta}_{\bm{A}}\oplus\bm{\Gamma}_{\bm{A}}\in\mathcal{H})<0.5$.

#### A.7 Proof of Theorem 4

###### Proof.

Recall that $\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X})=\mathrm{argmax}_{c\in\{0,1\}}\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=c)$ and $\tilde{g}_{\bm{X}}(\bm{A},\bm{X})=\mathrm{argmax}_{c\in\{0,1\}}\mathrm{Pr}(g(f_{\bm{\theta}^{*}},\bm{A},\bm{X}+\bm{\Gamma}_{\bm{X}},\eta,\mathcal{V}_{\text{tst}})=c)$. To certify the fairness level, we assume that $\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X})=1$, which means that

$$ $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)>0.5.$ (21) $$

For any perturbation $\|\bm{\Delta}_{\bm{X}}\|_{2}\leq\epsilon_{\bm{X}}\leq\tilde{\epsilon_{\bm{X}}}$, we have $\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X}+\bm{\Delta}_{\bm{X}})=\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})$ for any $\bm{\Gamma}_{\bm{A}}\in\bar{\mathcal{A}}$ where $\tilde{\epsilon_{\bm{X}}}$ is derived with classifier $\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})$.
Regarding the randomness of $\bm{\Gamma}_{\bm{A}}$, we have

$$ $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X}+\bm{\Delta}_{\bm{X}})=1)=\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)>0.5.$ (22) $$

Hence we obtain that $\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X}+\bm{\Delta}_{\bm{X}})=\tilde{g}_{\bm{A},\bm{X}}(\bm{A},\bm{X})$ for any perturbation $\|\bm{\Delta}_{\bm{X}}\|_{2}\leq\epsilon_{\bm{X}}$.
∎

###### Proof.

#### A.8 Proof of Proposition 1

###### Proof.

For the practical certification, we add perturbations within certified budgets and derive independent identically distributed output samples $\hat{\mathcal{Y}}^{\prime}$ by Monte Carlo. For each sample $\hat{\bm{Y}}^{\prime}\in\hat{\mathcal{Y}}^{\prime}$, we have $\mathrm{Pr}(\pi(\hat{\bm{Y}}^{\prime},\mathcal{V}_{\text{tst}})>\eta)<0.5$ according to [Theorem 4](#Thmtheorem4) and [Theorem 2](#Thmtheorem2). $\pi(\hat{\bm{Y}},\mathcal{V}_{\text{tst}})>\eta$ indicates that $\pi(\hat{\bm{Y}}^{\prime},\mathcal{V}_{\text{tst}})>\eta$ for any $\hat{\bm{Y}}^{\prime}\in\hat{\mathcal{Y}}^{\prime}$. Consequently, we have

$$ $\mathrm{Pr}(\pi(\hat{\bm{Y}},\mathcal{V}_{\text{tst}})>\eta)=\Pi_{\hat{\bm{Y}}^{\prime}\in\hat{\mathcal{Y}}^{\prime}}\mathrm{Pr}(\pi(\hat{\bm{Y}}^{\prime},\mathcal{V}_{\text{tst}})>\eta)<0.5^{|\hat{\mathcal{Y}}^{\prime}|}.$ (23) $$

∎

###### Proof.

#### A.9 Rationale of Each Theoretical Result

Here we provide an explanation below about the rationale of each theoretical result in this paper.

Theorem 1. (Certified Fairness Defense for Node Attributes): This theorem gives a way to compute the perturbation-invariant budget (i.e., the budget within which the fairness level will not reduce under a certain threshold) of node attributes. However, since we consider both input data modalities could be attacked, we still need to extend the analysis over the span of node attributes and graph topology (see Theorem 4).

Theorem 2. (Certified Defense Budget for Structure Perturbations): This theorem formulates an optimization problem, whose solution is the perturbation-invariant budget (i.e., the budget within which the fairness level will not reduce under a certain threshold) of graph topology under the smoothed node attributes. However, to solve this optimization problem, we need to explicitly compute $\underline{P_{\tilde{g}_{\bm{X}}=1}}$ (see Theorem 3).

Theorem 3. (Positive Probability Lower Bound): This theorem provides a way to explicitly compute $\underline{P_{\tilde{g}_{\bm{X}}=1}}$, which directly enables us to solve the optimization problem in Theorem 2.

Theorem 4. (Certified Defense Budget for Attribute Perturbations): This theorem is built upon Theorem 1 and provides a way to explicitly compute the perturbation-invariant budget of node attributes over the span of node attributes and graph topology.

Lemma 1. (Perturbation-Invariant Budgets Existence): This lemma claims the existence and tractability of the perturbation-invariant budgets on both data modalities, which is further detailed by Theorem 2 and Theorem 4.

Lemma 2. (Positive Probability Bound Under Noises): This lemma claims the existence and tractability of $\underline{P_{\tilde{g}_{\bm{X}}=1}}$, which is further detailed by Theorem 3.

Proposition 1. (Probabilistic Guarantee for the Fairness Level of Node Classification): This proposition provides a neat probabilistic theoretical guarantee — we have a probability that is large enough to successfully achieve certified defense on fairness.

### Appendix B Reproducibility and Supplementary Analysis

In this section, we provide more details for the replicability of our experiments, which serves as an extension to Section 4. To begin with, we offer a comprehensive introduction of the three real-world datasets adopted in our experiments. Subsequently, we introduce the detailed experimental settings, as well as the implementation details of our proposed framework, ELEGANT, alongside GNNs and baseline models. Moreover, we outline those essential packages, including their versions, that were utilized in our experiments. Lastly, we elaborate on the supplementary analysis on the time complexity of ELEGANT.

#### B.1 Datasets

In our experiments, we adopt three real-world network datasets that are widely used to perform studies on the fairness of GNNs, namely German Credit (Asuncion & Newman, ; Agarwal et al., ), Recidivism (Jordan & Freiburger, ; Agarwal et al., ), and Credit Defaulter (Yeh & Lien, ; Agarwal et al., ).
We introduce their basic information below.

(1) German Credit. Each node is a client in a German bank (Asuncion & Newman, ), while each edge between any two clients represents that they bear similar credit accounts. Here the gender of bank clients is considered as the sensitive attribute, and the task is to classify the credit risk of the clients as high or low.

(2) Recidivism. Each node denotes a defendant released on bail at the U.S state courts during 1990-2009 (Jordan & Freiburger, ), and defendants are connected based on the similarity of their past criminal records and demographics. Here the race of defendants is considered as the sensitive attribute, and the task is to classify defendants into more likely vs. less likely to commit a violent crime after being released.

(3) Credit Defaulter. This dataset contains credit card users collected from financial agencies (Yeh & Lien, ). Specifically, each node in this network denotes a credit card user, and users are connected based on their spending and payment patterns. The sensitive attribute is the age period of users, and the task is to predict the future default of credit card for these users. We present the statistics pf the three datasets above in [Table 2](#A2.T2).

For the three real-world datasets used in this paper, we adopt the split rate for the training set and validation set as 0.4 and 0.55, respectively. The input node features are normalized before they are fed into the GNNs and the corresponding explanation models. For the downstream task node classification, only the labels of the nodes in the training set is available for all models during the training process.
The trained GNN models with the best performance on the validation set are preserved for test and explanation.

**Table 2: The statistics and basic information about the six real-world datasets adopted for experimental evaluation. Sens. represents the semantic meaning of sensitive attribute.**
| Dataset | German Credit | Recidivism | Credit Defaulter |
| --- | --- | --- | --- |
| # Nodes | 1,000 | 18,876 | 30,000 |
| # Edges | 22,242 | 321,308 | 1,436,858 |
| # Attributes | 27 | 18 | 13 |
| Avg. degree | 44.5 | 34.0 | 95.8 |
| Sens. | Gender | Race | Age |
| Label | Credit status | Bail decision | Future default |

#### B.2 Detailed Experimental Settings

Implementation of GNN Models.
In our experiments, all GNN models are implemented in PyTorch (Paszke et al., ) with PyG (PyTorch Geometric) (Fey & Lenssen, ).
For the corresponding hyper-parameters, we set the value of weight decay as 5e-4, with the hidden dimension number and dropout rate being 64 and 0.6, respectively.
In addition, we set the learning rate and epoch number as 5e-2 and 200 for training.

Implementation of ELEGANT.
ELEGANT is implemented in PyTorch (Paszke et al., ) and all GNNs under ELEGANT are optimized through Adam optimizer (Kingma & Ba, ). In our experiments, the sampling sizes of Gaussian noise and Bernoulli noise are 150 and 200, respectively.
All hyper-parameters for GNNs under ELEGANT are set as the same values as the hyper-parameters adopted for vanilla GNNs.
We propose to add Gaussian and Bernoulli noise (to node attributes and graph topology) during training, which empirically leads to better certification performance, i.e., larger certification budgets over both node attributes and graph topology. Specifically, we set the entry-wise probability of flipping the existence of an edge and the standard deviation of the added Gaussian noise as 2e-4 and 2e-5, respectively.
In addition, we set the confidence level as 0.7 for estimation, since a lower confidence level helps exhibit a clearer tendency of the change of certified budgets w.r.t. other parameters under a limited number of sampling size, considering the computational costs.
In the test phase, we set the sampled ratio for certification (from the nodes out of training and validation set) to be 0.9 to make the sampled size relatively large, in which way we include more nodes in the set of nodes to be certified.
In each run, we sample 100 times, and the value of FCR is averaged across three runs with different seeds.
Finally, considering the sizes of the three datasets, we set the nodes that are vulnerable to be 5% for German Credit and 1% for others.

Selection of $\epsilon$ and $\beta$.
There are two critical parameters, $\epsilon$ and $\beta$, that could affect the effectiveness of ELEGANT. These two parameters control the level of randomness for the added Gaussian and Bernoulli noise, respectively.
Intuitively, larger $\epsilon$ and $\beta$ will induce more randomness in the node attributes and graph structure, which could make ELEGANT more robust to perturbations with larger sizes and thus achieve larger $\epsilon_{\bm{X}}$ and $\epsilon_{\bm{A}}$. However, if $\epsilon_{\bm{X}}$ and $\epsilon_{\bm{A}}$ are too large, the randomness could go beyond what the GNN classifier can manage and could finally cause failure in certification. Hence it is necessary to first determine appropriate values of $\epsilon_{\bm{X}}$ and $\epsilon_{\bm{A}}$ for ELEGANT.
Here we propose a strategy for parameter selection to realize as large certified defense budgets as possible.
Specifically, we first set an empirical $\eta$ to be 25% higher than the fairness level of the corresponding vanilla GNN model. Such a threshold calibrates across different GNNs and can be considered as a reasonable threshold for the exhibited bias.
Then we determine two wide search spaces for $\sigma$ and $\beta$, respectively, and compute the averaged $\epsilon_{\bm{X}}$ and $\epsilon_{\bm{A}}$ from multiple runs over each pair of $\sigma$ and $\beta$ values.
We now rank $(\sigma,\beta)$ pairs based on the averaged $\epsilon_{\bm{X}}$ and $\epsilon_{\bm{A}}$ in a descending order, respectively.
Finally, we truncate the obtained two rankings from their most top-ranked $(\sigma,\beta)$ pair to the tail, until the two truncated rankings have the first overlapped $(\sigma,\beta)$ pair.
Such an identified $(\sigma,\beta)$ pair can achieve large and balanced certification budgets over both $\bm{A}$ and $\bm{X}$, and hence they are recommended.

Implementation of Baseline Models.
In this paper, we include two fairness-aware GNNs as the baselines for comparison, namely FairGNN and NIFTY. We introduce the details below.
(1) FairGNN. For FairGNN, we adopt the official implementations from (Dai & Wang, ). Hyper-parameters corresponding to the GNN model structure (such as the number of hidden dimensions) are ensured to be the same as the vanilla GNNs for a fair comparison. Other parameters are carefully tuned under the guidance of the recommended training settings.
(2) NIFTY.
For NIFTY, we use the official implementations provided from (Agarwal et al., ). We ensured that the parameters related to the GNN model structure stay the same as the original GNNs for a fair comparison. We also adjust other parameters based on the suggested training settings for better performance.

Packages Required for Implementations.
We list those key packages and their corresponding versions adopted in our experiments below.

- •
Python == 3.8.8
- •
torch == 1.10.1
- •
torch-geometric == 2.1.0
- •
torch-scatter == 2.0.9
- •
torch-sparse == 0.6.13
- •
cuda == 11.1
- •
numpy == 1.20.1
- •
tensorboard == 2.10.0
- •
networkx == 2.5
- •
scikit-learn == 0.24.2
- •
pandas==1.2.4
- •
scipy==1.6.2

Figure: Figure 4: The utility of GCN, E-GCN, FairGNN, and NIFTY under fairness attacks on German Credit. The shaded bar indicates that certified budget $\epsilon_{\bm{A}}\leq\|\bm{\Delta}_{\bm{A}}\|_{0}$ or $\epsilon_{\bm{X}}\leq\|\bm{\Delta}_{\bm{X}}\|_{2}$.
Refer to caption: /html/2311.02757/assets/x5.png

#### B.3 Algorithmic Routine

Now we introduce the pipeline of the proposed framework ELEGANT to obtain the node classification results in facing of the graph data that could have been perturbed by malicious attackers. We present the algorithmic routine in [Algorithm 1](#alg1). Note that ABSTAIN refers to the case where certification fails. Correspondingly, FCR measures the ratio of not returning ABSTAIN for the proposed framework ELEGANT, which generally reflects the usability of the certification defense.

#### B.4 Evaluation of Model Utility

In Section 4.3, we present the comparison between ELEGANT and baseline models over the fairness level under attacks. We now present the comparison over the utility under attacks. Specifically, we utilize node classification accuracy as the indicator of model utility, and we present the results in [Figure 4](#A2.F4.5). The fairness-aware GNNs are found to exhibit better utility compared with the vanilla GNNs, which is a common observation consistent with a series of existing works (Agarwal et al., ; Dong et al., ). More importantly, we observe that the ELEGANT does not jeopardize the performance of GNN compared with the utility of the vanilla GNN. This demonstrate a high level of usability for ELEGANT in real-world applications.

#### B.5 Certification under Different Fairness Metrics

In Section 4.2, we present the experimental results based on the fairness metric of $\Delta_{\text{SP}}$, which measures the exhibited bias under the fairness notion of Statistical Parity. We also perform the experiments based on $\Delta_{\text{EO}}$, which measures the exhibited bias under the fairness notion of Equal Opportunity. We present the experimental results in [Table 3](#A2.T3). We summarize the observations below.
(1) Fairness Certification Rate (FCR).
We observe that ELEGANT realizes large values of FCR (larger than 80%) for all three GNN backbones and three attributed network datasets. Similar to our discussion in Section 4.2, this demonstrate that for nodes in any randomly sampled test set, we have a probability around or larger than 80% to successfully certify the fairness level of the predictions yielded by the GNN model with our proposed framework ELEGANT. As a consequence, we argue that ELEGANT also achieves a satisfying fairness certification rate across all adopted GNN backbones and datasets on the basis of $\Delta_{\text{EO}}$.
In addition, we also observe that the German Credit dataset bears relatively larger values of FCR, while the values of FCR are relatively smaller with relatively larger standard deviation values on Recidivism and Credit Defaulter datasets.
A possible reason is that we set the threshold (i.e., $\eta$) as a value 25% higher than the bias exhibited by the vanilla GNNs. Consequently, if the vanilla GNNs already exhibit a low level of bias, the threshold determined with such a strategy could be hard to satisfy under the added noise. This evidence indicates that the proposed framework ELEGANT tends to deliver better performance under scenarios where vanilla GNNs exhibit a high level of bias with the proposed strategy.
(2) Utility.
Compared with vanilla GNNs, certified GNNs with ELEGANT exhibit comparable and even higher node classification accuracy values in all cases. Therefore, we argue that the proposed framework ELEGANT does not significantly jeopardize the utility of the vanilla GNN models in certifying the fairness level of node classification.
(3) Fairness.
We observe that certified GNNs with ELEGANT are able to achieve better performances in terms of algorithmic fairness compared with those vanilla GNNs. This evidence indicates that the proposed framework ELEGANT also helps to mitigate the exhibited bias (by the backbone GNN models). We conjecture that such bias mitigation should be attributed to the same reason discussed in Section 4.2.

**Table 3: Comparison between vanilla GNNs and certified GNNs under ELEGANT over three popular GNNs across three real-world datasets. Here ACC is node classification accuracy, and E- prefix marks out the GNNs under ELEGANT with certification. $\uparrow$ denotes the larger, the better; $\downarrow$ denotes the opposite. Different from the table in Section 4.2 (where the bias is measured with $\Delta_{\text{SP}}$), the bias is measured with $\Delta_{\text{EO}}$ here. Numerical values are in percentage, and the best ones are in bold.**
|  | German Credit |  | Recidivism |  | Credit Defaulter |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | ACC ($\uparrow$) | Bias ($\downarrow$) | FCR ($\uparrow$) |  | ACC ($\uparrow$) | Bias ($\downarrow$) | FCR ($\uparrow$) |  | ACC ($\uparrow$) | Bias ($\downarrow$) | FCR ($\uparrow$) |
| SAGE | 67.3 ±2.14 | 41.8 ±11.0 | N/A |  | 89.8 ±0.66 | 6.09 ±3.10 | N/A |  | 75.9 ±2.18 | 10.4 ±1.59 | N/A |
| E-SAGE | 72.2 ±1.26 | 8.63 ±6.15 | 100 ±0.00 |  | 90.8 ±0.97 | 3.12 ±3.64 | 81.0 ±13.0 |  | 73.4 ±0.61 | 7.18 ±1.06 | 88.7 ±6.02 |
| GCN | 59.6 ±3.64 | 35.0 ±4.77 | N/A |  | 90.5 ±0.73 | 6.35 ±1.65 | N/A |  | 65.8 ±0.29 | 13.5 ±4.23 | N/A |
| E-GCN | 58.8 ±3.74 | 29.8 ±6.82 | 93.3 ±8.73 |  | 89.3 ±0.92 | 3.93 ±3.12 | 96.0 ±4.97 |  | 63.5 ±0.37 | 9.12 ±0.95 | 80.5 ±14.5 |
| JK | 63.3 ±4.11 | 37.7 ±15.9 | N/A |  | 91.9 ±0.54 | 5.26 ±3.25 | N/A |  | 76.6 ±0.69 | 8.04 ±0.57 | N/A |
| E-JK | 63.4 ±3.68 | 31.2 ±15.5 | 93.7 ±8.96 |  | 90.1 ±0.55 | 2.54 ±1.62 | 83.7 ±8.96 |  | 76.9 ±0.86 | 2.90 ±2.04 | 95.7 ±4.80 |

Figure: Algorithm 1 Certified Defense on the Fairness of GNNs

#### B.6 Ordering the Inner and Outer Defense

We first review the general pipeline to achieve certified fairness defense. Specifically, we first model the fairness attack and defense by formulating the bias indicator function $g$. Then, we achieve certified defense over the node attributes for $g$, which leads to classifier $\tilde{g}_{\bm{X}}$. Finally, we realize certified defense for $\tilde{g}_{\bm{X}}$ over the graph topology, which leads to classifier $\tilde{g}_{\bm{A},\bm{X}}$. In general, we may consider the certified defense over node attributes and graph topology as the inner certified classifier and outer certified classifier, respectively.
Now, a natural question is: is it possible to achieve certified defense in a different order, i.e., first achieve certified defense over the graph topology (as the inner classifier), and then realize certified defense over the node attributes (as the outer classifier)? Note that this is not the research focus of this paper, but we will provide insights about this question.
In fact, it is also feasible to achieve certified defense in the reversed order compared with the approach presented in our paper. We provide an illustration in [Figure 5](#A2.F5).
We follow a similar setting to plot this figure as in Section 3.3. Specifically, in case (1), both $\bm{A}_{i,j}\oplus 0$ and $\bm{A}_{i,j}\oplus 1$ lead to a positive outcome for $g$; in case (2), both $\bm{A}_{i,j}\oplus 0$ and $\bm{A}_{i,j}\oplus 1$ lead to a negative outcome. However, considering the Gaussian distribution around $\bm{X}_{i,j}$, samples will fall around case (1) with a much higher number compared with case (2).

Figure: Figure 5: An example illustrating how ELEGANT works with a different order of realizing certification defense.
Refer to caption: /html/2311.02757/assets/x6.png

Hence, in this example, it would be reasonable to assume that the classifier with Bernoulli noise over graph topology (the inner certified classifier) will return 1 with a higher probability. This example thus illustrates how certification following a different order returns 1.

However, such a formulation bears higher computational costs in calculating the certified budgets. The reason is that we are able to utilize a closed-form solution to calculate $\epsilon_{\bm{X}}$ based on a set of Gaussian noise and the corresponding output from the bias indicator function.
However, based on a set of Bernoulli noise and the corresponding output from the bias indicator function, we will need to solve the optimization problem given in [Theorem 2](#Thmtheorem2) to calculate $\epsilon_{\bm{A}}$, which bears a higher time complexity than calculating $\epsilon_{\bm{X}}$.
If we follow the strategy provided in Section 3.4 to calculate the inner and outer certification budgets, the certified budget of the inner certification will always be calculated multiple times, while the certified budget of the outer certification will only be calculated once.
Considering the high computational cost of calculating $\epsilon_{\bm{A}}$, we thus argue that it is more efficient to realize the certification over graph topology as the outer certified classifier.

#### B.7 Certification with Estimated Probabilities

In Section 3.4, we proposed to utilize estimated lower bounds of the probabilities (including $P(c)$ in Theorem 1 and $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ in Theorem 3) to perform certification in practice, considering the exact probability values are difficult to compute.
In [Section A.1](#A1.SS1) and [Section A.5](#A1.SS5), we have discussed that both theorems hold no matter exact probability values or estimated lower bounds (of the probabilities above) are used. Now we present a brief review of other theoretical analysis to show that they also hold.
(1) for Lemma 2, note that taking a lower bound estimation to replace the exact $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ reduces the total size of $\mathcal{H}$ in Theorem 3. Correspondingly, the formulated $\underline{P_{\tilde{g}_{\bm{X}}=1}}$ based on the estimated $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ is smaller than that based on the exact $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$. Hence Lemma 2 still holds when $\underline{P_{\tilde{g}_{\bm{X}}=1}}$ is replaced with one calculated based on the estimated $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$.
(2) For Theorem 2, it holds no matter how $P(c)$ in Theorem 1 and $\mathrm{Pr}(\tilde{g}_{\bm{X}}(\bm{A}\oplus\bm{\Gamma}_{\bm{A}},\bm{X})=1)$ in Theorem 3 are obtained.
(3) For Theorem 4, according to [Section A.7](#A1.SS7), it still holds as long as Theorem 1 holds.
(4) For Proposition 1, in all cases where $\mathrm{Pr}(g(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}^{\prime},\bm{X}+\bm{\Gamma}_{\bm{X}})=1)$ is identified to be larger than 0.5 with an estimated lower bound, the (underlying) exact $\mathrm{Pr}(g(\bm{A}\oplus\bm{\Gamma}_{\bm{A}}^{\prime},\bm{X}+\bm{\Gamma}_{\bm{X}})=1)$ will be larger than the estimated probability value under the given confidence level, and thus will also be larger than 0.5.
Here $\bm{\Gamma}_{\bm{A}}^{\prime}$ is a sampled Bernoulli noise, i.e., $\bm{\Gamma}_{\bm{A}}^{\prime}\in\bar{\mathcal{A}}^{\prime}$.
According to [Section A.8](#A1.SS8), Proposition 1 still holds in this case.
(5) Finally, we conclude that Lemma 1 still holds since Theorem 1, Lemma 2, Theorem 3, and Theorem 4 hold.

#### B.8 Time Complexity Analysis

We now present a comprehensive analysis on the time complexity of ELEGANT. We present the analysis from both theoretical and experimental perspectives.

Theoretical. The time complexity is linear w.r.t. the total number of the random perturbations $N$, i.e., $\mathcal{O}(N)$. We perform 30,000 random perturbations over the span of node attributes and graph structure. We note that the actual running time is acceptable since the certification does not require re-training (which is the most costly process). In addition, all runnings do not rely on the prediction results from each other. Hence they can be paralleled altogether theoretically to further reduce the running time.

Experimental. We perform a study of running time, and we present the results in [Table 4](#A2.T4). Specifically, we compare the running time of a successful certification under 30,000 random noise samples and a regular training-inference cycle with vanilla GCN. We observe that (1) although ELEGANT improves the computational cost compared with the vanilla GNN backbones, the running time remains acceptable; and (2) ELEGANT has less running time growth rate on larger datasets. For example, E-SAGE has around 10x running time on German Credit (a smaller dataset) while only around 4x on Credit Default (a larger dataset) compared to vanilla SAGE. Hence we argue that ELEGANT bears a high level of usability in terms of complexity and running time.

#### B.9 Additional Results on Different GNN Backbones & Baselines

We perform additional experiments over two popular GNNs, including APPNP (Klicpera et al., ) and GCNII (Chen et al., ), to evaluate the generalization ability of ELEGANT onto different backbones. We present all numerical results in [Table 5](#A2.T5) (in terms of accuracy), [Table 6](#A2.T6) (in terms of fairness), and [Table 7](#A2.T7) (in terms of FCR). We observe that ELEGANT achieves comparable utility, a superior level of fairness, and a large percentage of FCR. This verifies the satisfying usability of ELEGANT, which remains consistent with the paper.

In addition, we provide a detailed fairness comparison between ELEGANT and robust GNNs from (Jin et al., ) and (Wu et al., ) in [Table 8](#A2.T8). We observe that the best performances still come from the GNNs equipped with ELEGANT on all datasets. Hence we argue that ELEGANT exhibits satisfying performance in usability, which remains consistent with the discussion in the paper.

Why ELEGANT Improves Fairness? We note that improving fairness is a byproduct of ELEGANT, and our focus is to achieve certification over the fairness level of the prediction results. We now provide a detailed discussion about why fairness is improved here.
As mentioned in [Section 3.4](#S3.SS4), the proposed strategy to obtain the output predictions in ELEGANT is to select the fairest result among the output set $\hat{\mathcal{Y}}^{\prime}$, where each output is derived based on a sample $\bm{\Gamma}_{\bm{A}}^{\prime}\in\bar{\mathcal{A}}^{\prime}$ (i.e., $\mathrm{argmin}_{\hat{\bm{Y}}^{\prime}}\pi(\hat{\bm{Y}}^{\prime},\mathcal{V}_{\text{tst}})\;\;s.t.\;\hat{\bm{Y}}^{\prime}\in\hat{\mathcal{Y}}^{\prime}$). Such a strategy provides a large enough probability to achieve certification in light of Proposition 1. Meanwhile, we point out that such a strategy also helps to significantly improve fairness since highly biased outputs are excluded.

#### B.10 Complementary Results

We provide the results in terms of $\Delta_{EO}$ for [Table 1](#S4.T1) and the results in terms of $\Delta_{SP}$ for [Figure 2](#S4.F2.5) in [Table 9](#A2.T9) and [Table 10](#A2.T10), respectively. For [Table 9](#A2.T9), we observe that ELEGANT does not constantly show a lower value of $\Delta_{EO}$. This is because the certification goal in [Table 1](#S4.T1) is $\Delta_{SP}$ instead of $\Delta_{EO}$. In addition, we note that debiasing existing GNN models is not the goal of this paper. For [Table 10](#A2.T10), we also note that the certification goal here is $\Delta_{EO}$ instead of $\Delta_{SP}$. However, we note that ELEGANT still shows consistent debiasing performance as on the GCN backbone. Considering the competitive results given by ELEGANT over both $\Delta_{SP}$ and $\Delta_{EO}$, we argue that they are considered satisfying in terms of usability, which remains consistent with the discussion in the paper.

In addition, we provide the corresponding results in terms of accuracy for [Figure 3](#S4.F3) in [Table 11](#A2.T11) and [Table 12](#A2.T12). We observe that although most performance remains stable, a stronger noise (i.e., larger $\sigma$ and smaller $\beta$) generally leads to worse but still comparable performance. This is consistent with the discussion in [Section 4.4](#S4.SS4), and this has been taken into consideration in the discussion of the parameter selection strategy in [Section 4.4](#S4.SS4).

**Table 4: Comparison of running time (in seconds) on different datasets using different methods.**
|  | German | Recidivism | Credit |
| --- | --- | --- | --- |
| SAGE | 5.27 $\pm$ 0.38 | 34.14 $\pm$ 1.08 | 40.11 $\pm$ 0.36 |
| E-SAGE | 53.23 $\pm$ 1.31 | 137.12 $\pm$ 58.66 | 157.51 $\pm$ 37.21 |
| GCN | 5.59 $\pm$ 0.37 | 34.94 $\pm$ 1.16 | 40.59 $\pm$ 0.32 |
| E-GCN | 53.79 $\pm$ 30.19 | 212.94 $\pm$ 10.38 | 214.11 $\pm$ 10.31 |
| JK | 5.78 $\pm$ 0.43 | 34.68 $\pm$ 0.88 | 39.44 $\pm$ 1.56 |
| E-JK | 59.99 $\pm$ 25.01 | 238.37 $\pm$ 1.81 | 252.99 $\pm$ 17.03 |

**Table 5: Performance comparison of classification accuracy. Numbers are in percentage.**
|  | German | Recidivism | Credit |
| --- | --- | --- | --- |
| SAGE | 67.3 $\pm$ 2.14 | 89.8 $\pm$ 0.66 | 75.9 $\pm$ 2.18 |
| E-SAGE | 71.0 $\pm$ 1.27 | 89.9 $\pm$ 0.90 | 73.4 $\pm$ 0.50 |
| GCN | 59.6 $\pm$ 3.64 | 90.5 $\pm$ 0.73 | 65.8 $\pm$ 0.29 |
| E-GCN | 58.2 $\pm$ 1.82 | 89.6 $\pm$ 0.74 | 65.2 $\pm$ 0.99 |
| JK | 63.3 $\pm$ 4.11 | 91.9 $\pm$ 0.54 | 76.6 $\pm$ 0.69 |
| E-JK | 62.3 $\pm$ 4.07 | 89.3 $\pm$ 0.33 | 77.7 $\pm$ 0.27 |
| APPNP | 69.9 $\pm$ 2.17 | 95.3 $\pm$ 0.78 | 74.4 $\pm$ 3.05 |
| E-APPNP | 69.4 $\pm$ 0.83 | 95.9 $\pm$ 0.02 | 74.6 $\pm$ 0.32 |
| GCNII | 60.9 $\pm$ 1.00 | 90.4 $\pm$ 0.95 | 77.7 $\pm$ 0.22 |
| E-GCNII | 60.4 $\pm$ 4.45 | 88.8 $\pm$ 0.24 | 77.6 $\pm$ 0.02 |

**Table 6: Comparison of fairness (measured with $\Delta_{SP}$). Numbers are in percentage.**
|  | German | Recidivism | Credit |
| --- | --- | --- | --- |
| SAGE | 50.6 $\pm$ 15.9 | 9.36 $\pm$ 3.15 | 13.0 $\pm$ 4.01 |
| E-SAGE | 16.3 $\pm$ 10.9 | 6.39 $\pm$ 2.85 | 8.94 $\pm$ 0.99 |
| GCN | 37.4 $\pm$ 3.24 | 10.1 $\pm$ 3.01 | 11.1 $\pm$ 3.22 |
| E-GCN | 3.52 $\pm$ 3.77 | 9.56 $\pm$ 3.22 | 7.28 $\pm$ 1.46 |
| JK | 41.2 $\pm$ 18.1 | 10.1 $\pm$ 3.15 | 9.24 $\pm$ 0.60 |
| E-JK | 22.4 $\pm$ 1.95 | 6.26 $\pm$ 2.78 | 3.37 $\pm$ 2.64 |
| APPNP | 27.4 $\pm$ 4.81 | 9.71 $\pm$ 3.57 | 12.3 $\pm$ 3.14 |
| E-APPNP | 13.1 $\pm$ 5.97 | 2.23 $\pm$ 0.04 | 10.8 $\pm$ 0.07 |
| GCNII | 51.4 $\pm$ 0.36 | 9.70 $\pm$ 3.37 | 7.62 $\pm$ 0.29 |
| E-GCNII | 24.9 $\pm$ 0.47 | 3.78 $\pm$ 0.93 | 1.72 $\pm$ 0.81 |

**Table 7: Performance in FCR on different datasets and backbone GNNs. Numbers are in percentage.**
|  | German | Recidivism | Credit |
| --- | --- | --- | --- |
| E-SAGE | 98.7 $\pm$ 1.89 | 94.3 $\pm$ 6.65 | 94.3 $\pm$ 3.3 |
| E-GCN | 96.3 $\pm$ 1.89 | 96.0 $\pm$ 3.56 | 92.7 $\pm$ 5.19 |
| E-JK | 97.0 $\pm$ 3.00 | 89.5 $\pm$ 10.5 | 99.3 $\pm$ 0.47 |
| E-APPNP | 97.8 $\pm$ 3.14 | 87.1 $\pm$ 3.79 | 95.5 $\pm$ 6.43 |
| E-GCNII | 94.7 $\pm$ 5.27 | 92.9 $\pm$ 9.93 | 99.0 $\pm$ 1.41 |

**Table 8: Comparison of fairness (measured with $\Delta_{SP}$). Numbers are in percentage.**
|  | German | Recidivism | Credit |
| --- | --- | --- | --- |
| SAGE | 50.6 $\pm$ 15.9 | 9.36 $\pm$ 3.15 | 13.0 $\pm$ 4.01 |
| E-SAGE | 16.3 $\pm$ 10.9 | 6.39 $\pm$ 2.85 | 8.94 $\pm$ 0.99 |
| GCN | 37.4 $\pm$ 3.24 | 10.1 $\pm$ 3.01 | 11.1 $\pm$ 3.22 |
| E-GCN | 3.52 $\pm$ 3.77 | 9.56 $\pm$ 3.22 | 7.28 $\pm$ 1.46 |
| JK | 41.2 $\pm$ 18.1 | 10.1 $\pm$ 3.15 | 9.24 $\pm$ 0.60 |
| E-JK | 22.4 $\pm$ 1.95 | 6.26 $\pm$ 2.78 | 3.37 $\pm$ 2.64 |
| (Jin et al., ) | 14.8 $\pm$ 18.3 | 9.59 $\pm$ 0.65 | 3.84 $\pm$ 0.17 |
| (Wu et al., ) | 3.66 $\pm$ 0.52 | 8.04 $\pm$ 2.97 | 7.10 $\pm$ 5.10 |

**Table 9: The $\Delta_{EO}$ of [Table 1](#S4.T1) in the paper. All numerical numbers are in percentage.**
|  | German | Recidivism | Credit |
| --- | --- | --- | --- |
| SAGE | 30.43 $\pm$ 0.07 | 3.71 $\pm$ 0.01 | 5.56 $\pm$ 0.03 |
| E-SAGE | 12.21 $\pm$ 0.04 | 6.95 $\pm$ 0.02 | 7.18 $\pm$ 0.01 |
| GCN | 35.19 $\pm$ 0.07 | 5.06 $\pm$ 0.01 | 11.9 $\pm$ 0.02 |
| E-GCN | 8.32 $\pm$ 0.03 | 1.39 $\pm$ 0.01 | 6.24 $\pm$ 0.02 |
| JK | 18.10 $\pm$ 0.13 | 3.02 $\pm$ 0.01 | 9.47 $\pm$ 0.02 |
| E-JK | 23.68 $\pm$ 0.02 | 2.74 $\pm$ 0.01 | 2.55 $\pm$ 0.01 |

**Table 10: The results in terms of $\Delta_{SP}$ for [Figure 2](#S4.F2.5). All numerical numbers are in percentage.**
|  | (2^0, 10^-1) | (2^1, 10^0) | (2^2, 10^1) | (2^3, 10^2) |
| --- | --- | --- | --- | --- |
| GCN | 41.4 $\pm$ 8.8 | 41.4 $\pm$ 8.8 | 41.4 $\pm$ 9.4 | 42.6 $\pm$ 5.9 |
| NIFTY | 33.9 $\pm$ 3.3 | 36.1 $\pm$ 9.8 | 42.1 $\pm$ 4.9 | 44.5 $\pm$ 12 |
| FairGNN | 16.4 $\pm$ 6.4 | 16.8 $\pm$ 6.4 | 16.0 $\pm$ 6.0 | 16.9 $\pm$ 5.6 |
| E-GCN | 10.8 $\pm$ 0.1 | 10.8 $\pm$ 0.7 | 10.8 $\pm$ 0.5 | 13.9 $\pm$ 4.0 |

**Table 11: Classification accuracy in [Figure 3(a)](#S4.F3.sf1) with different settings. Numbers are in percentage.**
|  | 5e-3 | 5e-2 | 5e-1 | 5e0 |
| --- | --- | --- | --- | --- |
| 0 | 57.50 $\pm$ 1.50 | 57.51 $\pm$ 1.63 | 57.50 $\pm$ 1.58 | 55.67 $\pm$ 2.00 |
| 1e-3 | 57.50 $\pm$ 1.51 | 57.51 $\pm$ 1.63 | 57.50 $\pm$ 1.58 | 55.67 $\pm$ 2.00 |
| 5e-3 | 57.49 $\pm$ 1.52 | 57.50 $\pm$ 1.64 | 57.50 $\pm$ 1.58 | 55.67 $\pm$ 2.00 |
| 1e-2 | 57.55 $\pm$ 1.50 | 57.51 $\pm$ 1.65 | 57.50 $\pm$ 1.58 | 55.67 $\pm$ 2.00 |
| 5e-2 | N/A | 57.57 $\pm$ 1.59 | 57.50 $\pm$ 1.58 | 55.67 $\pm$ 2.00 |
| 1e-1 | N/A | 57.53 $\pm$ 1.57 | 57.50 $\pm$ 1.59 | 55.67 $\pm$ 2.00 |
| 5e-1 | N/A | N/A | 57.49 $\pm$ 1.60 | 55.67 $\pm$ 2.00 |
| 1e0 | N/A | N/A | 57.40 $\pm$ 1.58 | 55.67 $\pm$ 2.00 |
| 5e0 | N/A | N/A | N/A | 55.76 $\pm$ 1.86 |

**Table 12: Classification accuracy in [Figure 3(b)](#S4.F3.sf2) with different settings. Numbers are in percentage.**
|  | 0.6 | 0.7 | 0.8 | 0.9 |
| --- | --- | --- | --- | --- |
| 0 | 63.71 $\pm$ 0.64 | 64.03 $\pm$ 0.66 | 65.87 $\pm$ 0.49 | 64.88 $\pm$ 0.46 |
| 2^0 | 63.71 $\pm$ 0.64 | 64.03 $\pm$ 0.66 | 65.87 $\pm$ 0.49 | 64.88 $\pm$ 0.46 |
| 2^1 | 63.67 $\pm$ 0.64 | 64.04 $\pm$ 0.67 | N/A | N/A |
| 2^2 | 63.69 $\pm$ 0.67 | N/A | N/A | N/A |
| 2^3 | N/A | N/A | N/A | N/A |
| 2^4 | N/A | N/A | N/A | N/A |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 8
presentation: 3
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?
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: Please refer to the weakness.
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 1
initial_rating: 5
presentation: 3
questions: Please see weaknesses.
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See weaknesses.
soundness: 3
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.
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.
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?

Meta-review: 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"

Decision: Reject