Adversarial Attacks on Fairness of Graph Neural Networks
Fairness-aware graph neural networks (GNNs) have gained a surge of attention
as they can reduce the bias of predictions on any demographic group (e.g.,
female) in graph-based applications. Although these methods greatly improve the
algorithmic fairness of GNNs, the fairness can be easily corrupted by carefully
designed adversarial attacks. In this paper, we investigate the problem of
adversarial attacks on fairness of GNNs and propose G-FairAttack, a general
framework for attacking various types of fairness-aware GNNs in terms of
fairness with an unnoticeable effect on prediction utility. In addition, we
propose a fast computation technique to reduce the time complexity of
G-FairAttack. The experimental study demonstrates that G-FairAttack
successfully corrupts the fairness of different types of GNNs while keeping the
attack unnoticeable. Our study on fairness attacks sheds light on potential
vulnerabilities in fairness-aware GNNs and guides further research on the
robustness of GNNs in terms of fairness.
Binchi Zhang, Yushun Dong, Chen Chen, Yada Zhu, Minnan Luo, Jundong Li
# Adversarial Attacks on Fairness of

###### Abstract

Fairness-aware graph neural networks (GNNs) have gained a surge of attention as they can reduce the bias of predictions on any demographic group (e.g., female) in graph-based applications. Although these methods greatly improve the algorithmic fairness of GNNs, the fairness can be easily corrupted by carefully designed adversarial attacks. In this paper, we investigate the problem of adversarial attacks on fairness of GNNs and propose _G-FairAttack_, a general framework for attacking _various types of_ fairness-aware GNNs in terms of fairness with an _unnoticeable effect_ on prediction utility. In addition, we propose a fast computation technique to reduce the time complexity of G-FairAttack. The experimental study demonstrates that G-FairAttack successfully corrupts the fairness of different types of GNNs while keeping the attack unnoticeable. Our study on fairness attacks sheds light on potential vulnerabilities in fairness-aware GNNs and guides further research on the robustness of GNNs in terms of fairness. The open-source code is available at [https://github.com/zhangbinchi/G-FairAttack](https://github.com/zhangbinchi/G-FairAttack).

## 1 Introduction

Graph Neural Networks (GNNs) have achieved remarkable success across various human-centered applications, e.g., social network analysis (Qiu et al., 2018; Lu & Li, 2020; Feng et al., 2022), recommender systems (Ying et al., 2018; Fan et al., 2019; Yu et al., 2021), and healthcare (Choi et al., 2017; Li et al., 2022; Fu et al., 2023). Despite that, many recent studies (Dai & Wang, 2021; Wang et al., 2022; Dong et al., 2022b; 2023b) have shown that GNNs could yield biased predictions for nodes from certain demographic groups (e.g., females). With the increasing significance of GNNs in high-stakes human-centered scenarios, addressing such prediction bias becomes imperative. Consequently, substantial efforts have been devoted to developing fairness-aware GNNs, with the goal of learning fair node representations that can be used to make accurate and fair predictions. Typical strategies to improve the fairness of GNNs include adversarial training (Bose & Hamilton, 2019; Dai & Wang, 2021), regularization (Navarin et al., 2020; Fan et al., 2021; Agarwal et al., 2021; Dong et al., 2023c), and edge rewiring (Spinelli et al., 2021; Li et al., 2021; Dong et al., 2022a).

Although these fairness-aware GNN frameworks can make fair predictions, there remains a high risk of the exhibited fairness being corrupted by malicious attackers (Hussain et al., 2022). Adversarial attacks threaten the fairness of the victim model by perturbing the input graph data, resulting in unfair predictions. Such fairness attacks can severely compromise the reliability of GNNs, even when they have a built-in fairness-enhancing mechanism. For instance, we consider a GNN-based recommender system in social networks. In scenarios regarding commercial competition or personal benefits, a malicious adversary might conduct fairness attacks by hijacking inactive user accounts. The adversary can collect user data from these accounts to train a fairness attack model. According to the fairness attack algorithm, the adversary can then modify the attributes and connections of these compromised accounts. As a result, the GNN-based system is affected by the poisoned input data and makes biased predictions against a specific user group.
To protect the fairness of GNN models from adversarial attacks, we should first fully understand the potential ways to attack fairness. To this end, we investigate the problem of adversarial attacks on fairness of GNNs in this paper. Despite the importance of investigating the fairness attack of GNNs, most existing studies (Zugner et al., 2018; Zugner and Gunnemann, 2019; Bojchevski and Gunnemann, 2019; Dai et al., 2018; Xu et al., 2019) only focus on attacking the utility of GNNs (e.g., prediction accuracy) and neglect the vulnerability of GNNs in the fairness aspect. To study fairness attacks, we follow existing works of attacks on GNNs to formulate the attack as an optimization problem and consider the prevalent gray-box attack setting (Zugner et al., 2018; Zugner and Gunnemann, 2019; Wang and Gong, 2019; Sun et al., 2019) where the attacker cannot access the architecture or parameters of the victim model (Jin et al., 2021; Sun et al., 2022). A common strategy in gray-box attacks is to train a surrogate model (Zugner et al., 2018; Zugner and Gunnemann, 2019) to gain more knowledge on the unseen victim model for the attack. Compared with conventional adversarial attacks, our attack on fairness is more difficult for the following two challenges: **(1) The design of the surrogate loss function**. Previous attacks on prediction utility directly choose the loss function adopted by most victim models, i.e. the cross-entropy (CE) loss as the surrogate loss. However, fairness-aware GNN models are trained based on different loss functions for fairness, e.g., demographic parity loss (Navarin et al., 2020; Zeng et al., 2021; Franco et al., 2022; Jiang et al., 2022), mutual information loss (Kang et al., 2022), and Wasserstein distance loss (Fan et al., 2021; Dong et al., 2022). Because the victim model is unknown and can be any type of fairness-aware GNN, the attacker should find a proper surrogate loss to represent different types of loss functions of fairness-aware GNNs. **(2) The necessity to make such attacks unnoticeable.** If the poisoned graph data exhibits any clues of being manipulated, the model owner could recognize them and then take defensive actions (Zugner et al., 2018), e.g., abandoning the poisoned input data. Conventionally, attackers restrict the perturbation size to make attacks unnoticeable. In fairness attacks, we argue that a distinct change of prediction utility can also be a strong clue of being manipulated. However, none of the existing works on fairness attacks has considered the unnoticeable utility change.

In light of these challenges, we propose a novel fairness attack method on GNNs named **G-FairAttack**, which consists of two parts: a carefully designed surrogate loss function and an optimization method. To tackle the first challenge, we categorize existing fairness-aware GNNs into three types based on their fairness loss terms. Then we propose a novel surrogate loss function to help the surrogate model learn from all types of fairness-aware GNNs with theoretical analysis. To address the second challenge, we propose a novel unnoticeable constraint in utility change to make the fairness attack unnoticeable. Then we propose a non-gradient attack algorithm to solve the constrained optimization problem, which is verified to have a better performance than previous gradient-based methods. Moreover, we propose a fast computation strategy to improve the scalability of G-FairAttack. Our contributions can be summarized as follows.

* [leftmargin=*,noitemsep,topsep=0pt]
* **Attack Setting.** We consider a novel unnoticeable constraint on prediction utility change for unnoticeable fairness attacks of GNNs, which can be extended to general fairness attacks.
* **Objective Design.** We propose a novel surrogate loss to help the surrogate model learn from various types of fairness-aware GNNs with theoretical analysis.
* **Algorithmic Design.** To solve the optimization problem with the unnoticeable constraint, we discuss the deficiency of previous gradient-based optimization methods and design a non-gradient attack method. In addition, we propose a fast computation approach to reduce its time complexity.
* **Experimental Evaluation.** We conduct extensive experiments on three real-world datasets with four types of victim models and verify that our proposed G-FairAttack successfully jeopardizes the fairness of various fairness-aware GNNs with an unnoticeable effect on prediction utility.

## 2 Problem Definition

**Notation and Preliminary.** We use bold uppercase letters, e.g., \(\mathbf{X}\), to denote matrices, and use \(\mathbf{X}_{[i,:]}\), \(\mathbf{X}_{[:,j]}\), and \(\mathbf{X}_{[i,j]}\) to denote the \(i\)-th row, the \(j\)-th column, and the element at the \(i\)-th row and the \(j\)-th column, respectively. We use bold lowercase letters, e.g., \(\mathbf{x}\), to denote vectors, and use \(\mathbf{x}_{[i]}\) to denote the \(i\)-th element. We use \(P_{X}(\cdot)\) and \(F_{X}(\cdot)\) to denote the probability density function and the cumulative distribution function for a random variable \(X\), respectively. We use \(\mathcal{G}=\{\mathcal{V},\mathcal{E},\mathbf{X}\}\) to denote an undirected attributed graph. \(\mathcal{V}=\{v_{1},\dots,v_{n}\}\) and \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) denote the node set and the edge set, respectively, where \(n=|\mathcal{V}|\) is the number of nodes. \(\mathbf{X}\in\mathbb{R}^{n\times d_{x}}\) denotes the
attribute matrix, where \(d_{x}\) is the number of node attributes. We use \(\mathbf{A}\in\{0,1\}^{n\times n}\) to denote the adjacency matrix, where \(\mathbf{A}_{[i,j]}=1\) when \((i,j)\in\mathcal{E}\) and \(\mathbf{A}_{[i,j]}=0\) otherwise. In the node classification task, some nodes are associated with ground truth labels. We use \(\mathcal{V}_{\text{train}}\) to denote the labeled (training) set, \(\mathcal{V}_{\text{test}}=\mathcal{V}\backslash\mathcal{V}_{\text{train}}\) to denote the unlabeled (test) set, and \(\mathcal{Y}\) to denote the set of labels. Most GNNs take the adjacency matrix \(\mathbf{A}\) and the attribute matrix \(\mathbf{X}\) as the input, and obtain the node embeddings used for node classification tasks. Specifically, we use \(f_{\mathbf{\theta}}:\{0,1\}^{n\times n}\times\mathbb{R}^{n\times d_{x}}\to \mathbb{R}^{n\times c}\) to denote a GNN model, where \(\mathbf{\theta}\) collects all learnable model parameters. We use \(\mathbf{\hat{y}}=\sigma\left(f_{\mathbf{\theta}}(\mathbf{A},\mathbf{X})\right)\) to denote soft predictions where \(\sigma(\cdot)\) is the softmax function. A conventional way to train a GNN model is minimizing a utility loss function \(\mathcal{L}\left(f_{\mathbf{\theta}},\mathbf{A},\mathbf{X},\mathcal{Y},\mathcal{V }_{\text{train}}\right)\) (e.g., CE loss) over the training set. In human-centered scenarios, each individual is usually associated with sensitive attributes (e.g., gender). We use \(\mathcal{S}=\{s_{1},\ldots,s_{n}\}\) to denote a sensitive attribute set, where \(s_{i}\) is the sensitive attribute of the node \(v_{i}\). Based on the sensitive attributes, we can divide the nodes into different sensitive groups, denoted as \(\mathcal{V}_{1},\ldots,\mathcal{V}_{K}\), where \(\mathcal{V}_{k}=\{v_{i}|s_{i}=k\}\) and \(K\) is the number of sensitive groups. Compared with vanilla GNNs, fairness-aware GNNs should not yield discriminatory predictions against individuals from any specific sensitive subgroup (Dong et al., 2023). Hence, the objective of training fairness-aware GNNs generally contains two aspects; one is minimizing the utility loss, i.e., \(\mathcal{L}\left(f_{\mathbf{\theta}},\mathbf{A},\mathbf{X},\mathcal{Y},\mathcal{V }_{\text{train}}\right)\), the other is minimizing the discrimination between the predictions over different sensitive groups, denoted as \(\mathcal{L}_{f}\left(f_{\mathbf{\theta}},\mathbf{A},\mathbf{X},\mathcal{Y}, \mathcal{S}\right)\). It is worth noting that \(\mathcal{L}\) is the CE loss in most cases, but there are various types of \(\mathcal{L}_{f}\) for training fair GNNs.

**Problem Formulation.** In the fairness attack of GNNs, attackers aim to achieve their goals (e.g., to make the predictions of the victim GNN exhibit more bias) via slightly perturbing the input graph data in certain feasible spaces. Here, we focus on structure perturbation because perturbing the graph structure in the discrete domain presents more challenges, and the attack methods based on structure perturbation can be easily adapted to attribute perturbation. In this paper, for the simplicity of discussion, we focus on two different sensitive groups and prediction classes, but our method can be easily adapted to tasks with multiple sensitive groups and classes. More details about our attack settings are discussed in Appendix B. We formulate our problem of fairness attacks of GNNs as follows.

**Problem 1**.: _Attacks on Fairness of GNNs with Unnoticeable Effect on Prediction Utility. Let \(\mathcal{G}=\{\mathcal{V},\mathcal{E},\mathbf{X}\}\) be an attributed graph with the adjacency matrix \(\mathbf{A}\). Let \(\mathcal{V}_{\text{train}}\) and \(\mathcal{V}_{\text{test}}\) be the labeled and unlabeled node sets, respectively, \(\mathcal{Y}\) be the label set corresponding to \(\mathcal{V}_{\text{train}}\), and \(\mathcal{S}\) be the sensitive attribute value set of \(\mathcal{V}\). Let \(g_{\mathbf{\theta}}\) be a surrogate GNN model, \(\mathcal{L}_{\mathcal{S}}\), \(\mathcal{L}\), and \(\mathcal{L}_{f}\) be the surrogate loss, utility loss, and fairness loss, respectively. Given the attack budget \(\Delta\) and the utility variation budget \(\epsilon\), the problem of attacks on fairness of GNNs is formulated as follows._

\[\max_{\mathbf{A}^{\prime}\in\mathcal{F}}\mathcal{L}_{f}\left(g_{\mathbf{\theta}^{ \star}},\mathbf{A}^{\prime},\mathbf{X},\mathcal{Y},\mathcal{V}_{\text{test}}, \mathcal{S}\right)\]

\[\mathrm{s.t.}\ \mathbf{\theta}^{\star}=\arg\min_{\mathbf{\theta}}\mathcal{L}_{s} \left(g_{\mathbf{\theta}},\tilde{\mathbf{A}},\mathbf{X},\mathcal{Y},\mathcal{S} \right),\ \|\mathbf{A}^{\prime}-\mathbf{A}\|_{F}\leq 2\Delta, \tag{1}\]

\[|\mathcal{L}(g_{\mathbf{\theta}^{\star}},\mathbf{A},\mathbf{X},\mathcal{Y}, \mathcal{V}_{\text{train}})-\mathcal{L}(g_{\mathbf{\theta}^{\star}},\mathbf{A}^{ \prime},\mathbf{X},\mathcal{Y},\mathcal{V}_{\text{train}})|\leq\epsilon,\]

_where \(\mathcal{F}\) is the feasible space of the poisoned graph structure \(\mathbf{A}^{\prime}\), \(g_{\mathbf{\theta}^{\star}}\) is a trained surrogate model._

In this problem, the attacker's objective \(\mathcal{L}_{f}(g_{\mathbf{\theta}^{\star}},\mathbf{A}^{\prime},\mathbf{X}, \mathcal{Y},\mathcal{V}_{\text{test}},\mathcal{S})\) measures the bias of the predictions on test nodes. The surrogate model \(g_{\mathbf{\theta}^{\star}}\) is trained based on a surrogate loss \(\mathcal{L}_{s}(g_{\mathbf{\theta}},\tilde{\mathbf{A}},\mathbf{X},\mathcal{Y}, \mathcal{S})\). The constraints restrict the number of perturbed edges and the absolute value of the utility change over the training set. In this paper, we consider two types of attack scenarios, _fairness evasion attack_ and _fairness poisoning attack_ (Chakraborty et al., 2018). By perturbing the input graph data, _fairness evasion attack_ jeopardizes the fairness of a well-trained fairness-aware GNN model in the test phase, while _fairness poisoning attack_ makes the fairness-aware GNN model trained on such perturbed data render unfair predictions. If \(\tilde{\mathbf{A}}=\mathbf{A}\), then Problem 1 boils down to the fairness eva

Figure 1: A toy example of fairness attacks of GNNs with unnoticeable effect on prediction utility.
sion attack; and if \(\tilde{\mathbf{A}}=\mathbf{A}^{\prime}\), then Problem 1 becomes fairness poisoning attack. In this paper, we use demographic parity (Navarin et al., 2020) as the attacker's objective \(\mathcal{L}_{f}\), the CE loss as utility loss \(\mathcal{L}\), and a two-layer linearized GCN (Zugner et al., 2018) as the surrogate model \(g_{\mathbf{\theta}}\). These choices have been verified by many previous works (Zugner et al., 2018; Zugner and Gunnemann, 2019; Xu et al., 2019) to be effective in attacking the prediction utility of GNNs, while can also be changed flexibly according to the specific task. An illustration of our problem is shown in Figure 1. We leave the detailed explanation of Figure 1 in Appendix B.

## 3 Methodology

In this section, we first introduce the design of the surrogate loss \(\mathcal{L}_{s}\), which is the most critical part in Problem 1. Then, we propose a non-gradient optimization method to solve Problem 1 and propose a fast computation technique to reduce the time complexity of our optimization method.

### Surrogate Loss Design

**Existing Loss on Fairness.** The loss functions of all existing fairness-aware GNNs can be divided into two parts: utility loss term (CE loss that is shared in common) and fairness loss term (varies from different methods). Correspondingly, our surrogate loss function is designed as \(\mathcal{L}_{s}=\mathcal{L}_{s_{u}}+\alpha\mathcal{L}_{s_{f}}\) where \(\mathcal{L}_{s_{u}}\) is the utility loss term, i.e., the CE loss, \(\mathcal{L}_{s_{f}}\) is the fairness loss term we aim to study, and \(\alpha\) is the weight coefficient. Let \(\hat{Y}\in[0,1]\) be a continuous random variable of the output soft prediction and \(S\) be a discrete random variable of the sensitive attribute. Next, we categorize the fairness loss terms into three types. **(1)**, \(\Delta_{dp}(\hat{Y},S)=|\mathrm{Pr}(\hat{Y}\geq\frac{1}{2}|S=0)-\mathrm{Pr}( \hat{Y}\geq\frac{1}{2}|S=1)|\): demographic parity (Jiang et al., 2022; Navarin et al., 2020; Zeng et al., 2021; Franco et al., 2022), that reduces the difference of positive rate among different sensitive groups during training. **(2).**\(I(\hat{Y},S)=\int_{0}^{1}\sum_{i}P_{\hat{Y},S}(z,i)\log\frac{P_{\hat{Y},S}(z, i)}{P_{\hat{Y}}(z)\mathrm{Pr}(S=ii)}dz\): mutual information of the output and the sensitive attribute (Dai and Wang, 2021; Bose and Hamilton, 2019; Kang et al., 2022), that reduces the dependence between the model output and the sensitive attribute during training. **(3).**\(W(\hat{Y},S)=\int_{0}^{1}|F_{\hat{Y}|S=0}^{-1}(p)-F_{\hat{Y}|S=1}^{-1}(y)|dy\): Wasserstein-1 distance of the output on different sensitive groups (Fan et al., 2021; Dong et al., 2022), that makes the conditional distributions of the model output given different sensitive groups closer during training.

**The Proposed Surrogate Loss.** Next, we introduce our proposed surrogate loss term on fairness \(\mathcal{L}_{S_{f}}\), aiming at representing all types of aforementioned fairness loss terms, e.g., \(\Delta_{dp}(\hat{Y},S)\), \(I(\hat{Y},S)\), and \(W(\hat{Y},S)\). In particular, our idea is to find a common upper bound for these fairness loss terms as \(\mathcal{L}_{S_{f}}\). Therefore, during the training of the surrogate model, \(\mathcal{L}_{S_{f}}\) is minimized to a small value, and all types of fairness loss terms become even smaller consequently. In this way, the surrogate model trained by our surrogate loss will be close to that trained by any unknown victim loss, which is consistent with conventional attacks on model utility. Consequently, we argue that such surrogate loss can represent the unknown victim loss. Accordingly, we propose a novel surrogate loss function on fairness \(TV(\hat{Y},S)=\int_{0}^{1}|P_{\hat{Y}|S=0}(z)-P_{\hat{Y}|S=1}(z)|dz\), i.e., the total variation of \(\hat{Y}\) on different sensitive groups. We can prove that \(TV(\hat{Y},S)\) is a common upper bound of \(\Delta_{dp}(\hat{Y},S)\), \(I(\hat{Y},S)\) (at certain condition), and \(W(\hat{Y},S)\) so it can represent all types of fairness loss functions.

**Theorem 1**.: _We have \(\Delta_{dp}(\hat{Y},S)\) and \(W(\hat{Y},S)\) upper bounded by \(TV(\hat{Y},S)\). Moreover, \(I(\hat{Y},S)\) is also upper bounded by \(TV(\hat{Y},S)\) if \(\forall z\in[0,1]\), \(P_{\hat{Y}}(z)\geq\Pi_{i}\mathrm{Pr}(S=i)\) holds._

The proof of Theorem 1 is shown in Appendix A.1. Combining \(\mathcal{L}_{s_{f}}\) (total variation loss) and \(\mathcal{L}_{s_{u}}\) (CE loss), our surrogate loss function is \(\mathcal{L}_{s}=CE(g_{\mathbf{\theta}},\tilde{\mathbf{A}},\mathbf{X},\mathcal{Y})+ \alpha TV(g_{\mathbf{\theta}},\tilde{\mathbf{A}},\mathbf{X},\mathcal{S})\). Since the probability density function of the underlying random variable \(\hat{Y}\) is difficult to calculate, we leverage the kernel density estimation (Parzen, 1962) to compute the total variation loss with the output soft predictions \(g_{\mathbf{\theta}}(\tilde{\mathbf{A}},\mathbf{X})\). The kernel estimation is computed as \(\hat{P}_{\hat{Y}|S=i}(z)=\frac{1}{h|V_{i}|}\sum_{j\in\mathcal{Y}_{i}}K(\frac{z -g_{\mathbf{\theta}}(\tilde{\mathbf{A}},\mathbf{X})_{[i]}}{h})\) for \(i=0,1\), where \(K(\cdot)\) is a kernel function and \(h\) is a positive band
width constant. Then we exploit the numerical integration to compute the total variation loss as

\[TV(g_{\mathbf{\theta}},\tilde{\mathbf{A}},\mathbf{X},\mathcal{S})=\frac{1}{m}\sum_{j= 1}^{m}\left|\hat{P}_{\hat{Y}|S=0}\left(\frac{j}{m}\right)-\hat{P}_{\hat{Y}|S=1} \left(\frac{j}{m}\right)\right|, \tag{2}\]

where \(m\) is the number of intervals in the integration. Consequently, we obtain a practical calculation of our proposed surrogate loss \(\mathcal{L}_{s}\).

### Optimization

Considering that Problem 1 is a bilevel optimization problem in a discrete domain, it is extremely hard to find the exact solution. Hence, we resort to the greedy strategy and propose a sequential attack method. Our sequential attack flips target edges1 sequentially to obtain the optimal poisoned structure \(\mathbf{A}^{\prime}\). It is worth noting that many attack methods on model utility find the target edge corresponding to the largest element of the gradient of \(\mathbf{A}\), namely gradient-based methods (Zugner and Gunnemann, 2019; Xu et al., 2019; Wu et al., 2019; Geisler et al., 2021). However, we find the efficacy of gradient-based methods is not guaranteed.

Footnote 1: Flipping the target edge increases the attacker’s objective the most.

**Proposition 1**.: _Gradient-based methods for optimizing the graph structure are not guaranteed to decrease the objective function._

We leave a detailed analysis of the shortcomings of gradient-based methods in Appendix D. In contrast, we propose a non-gradient method based on a scoring function that can provably increase the attacker's objective. We first consider the unconstrained version of Problem 1. We let \(\mathbf{A}^{0}=\mathbf{A}\) and train the surrogate model to obtain \(\mathbf{\theta}^{0}\), i.e., solving \(\mathbf{\theta}^{0}=\arg\min_{\mathbf{\ell}}\mathcal{L}_{s}(g_{\mathbf{\theta}},\mathbf{ A},\mathbf{X},\mathcal{Y},\mathcal{S})\). For \(t=1,2,\ldots,T_{0}\), we find the maximum score \(r^{t}\) in the \(t\)-th iteration as

\[\max_{(u,v)\in\mathcal{C}^{t}}r^{t}(u,v)=\Delta\mathcal{L}_{f}^{t}(u,v)= \mathcal{L}_{f}(g_{\mathbf{\theta}^{t}},flip_{(u,v)}\mathbf{A}^{t})-\mathcal{L}_ {f}(g_{\mathbf{\theta}^{t}},\mathbf{A}^{t}), \tag{3}\]

where \(\mathcal{C}^{t}\) is the candidate edge set in the \(t\)-th iteration; \(flip_{(u,v)}\mathbf{A}\) denotes the adjacency matrix after flipping the edge \((u,v)\): \(flip_{(u,v)}\mathbf{A}_{[i,j]}=1-\mathbf{A}_{[i,j]}\) if \((i,j)=(u,v)\) or \((i,j)=(v,u)\), and \(flip_{(u,v)}\mathbf{A}_{[i,j]}=\mathbf{A}_{[i,j]}\) otherwise. After solving Equation (3), we denote the solution as \((u^{t},v^{t})\). Then we update \(\mathbf{A}^{t}\) as \(\mathbf{A}^{t+1}=flip_{(u^{t},v^{t})}\mathbf{A}^{t}\) in the \(t\)-th iteration. For the fairness poisoning attack, we retrain the surrogate model based on \(\mathbf{A}^{t+1}\) as \(\mathbf{\theta}^{t+1}=\arg\min_{\mathbf{\ell}}\mathcal{L}_{s}(g_{\mathbf{\theta}},\mathbf{ A}^{t+1})\) to update the surrogate model. After \(T_{0}\) iterations, we have \(\mathbf{A}^{*}=\mathbf{A}^{T_{0}}\) as the solution of Problem 1.

Next, to handle the first constraint, we let \(T_{0}\leq\Delta\) and have \(\|\mathbf{A}^{*}-\mathbf{A}\|_{F}\leq\sum_{i=1}^{T_{0}}\|\mathbf{A}^{t}- \mathbf{A}^{t-1}\|_{F}\leq 2\Delta\) consequently. For the second constraint, we aim to make every flipping unnoticeable in terms of model utility, i.e., making \(|\mathcal{L}(\mathbf{A}^{t+1})-\mathcal{L}(\mathbf{A}^{t})|\) as small as possible. We notice that this constrained optimization problem can be easily solved by projected gradient descent (PGD) (Nocedal and Wright, 2006) in the continuous domain by solving \(\mathbf{A}^{t+1}=\arg\!\min_{|\mathcal{L}(\mathbf{A}^{t})-\mathcal{L}(\mathbf{ A}^{t})|\leq\epsilon_{t}}\|\mathbf{A}^{\prime}-(\mathbf{A}^{t}+\eta\nabla \mathcal{L}_{f}(\mathbf{A}^{t}))\|_{F}^{2}\), where \(\epsilon_{t}\) is the budget of the \(t\)-th iteration that satisfies \(\sum_{t=1}^{\Delta}\epsilon_{t}\leq\epsilon\) and \(\eta\) is the learning rate. To solve this problem, we have the following theorem.

**Theorem 2**.: _The optimal poisoned adjacency matrix \(\mathbf{A}^{t+1}\) in the \(t+1\)-th iteration given by PGD, i.e., the solution of \(\mathbf{A}^{t+1}=\arg\!\min_{|\mathcal{L}(\mathbf{A}^{t})-\mathcal{L}(\mathbf{A} ^{t})|\leq\epsilon_{t}}\|\mathbf{A}^{\prime}-(\mathbf{A}^{t}+\eta\nabla \mathcal{L}_{f}(\mathbf{A}^{t}))\|_{F}^{2}\) is_

\[\mathbf{A}^{t+1}=\begin{cases}\mathbf{A}^{t}+\eta\nabla_{\mathbf{A}}\mathcal{L} _{f}(\mathbf{A}^{t}),\text{ if }\eta|\nabla_{\mathbf{A}}\mathcal{L}(\mathbf{A}^{t})^{T}\nabla_{ \mathbf{A}}\mathcal{L}_{f}(\mathbf{A}^{t})|\leq\epsilon_{t},\\ \mathbf{A}^{t}+\eta\nabla_{\mathbf{A}}\mathcal{L}_{f}(\mathbf{A}^{t})+\frac{ \epsilon_{t}\epsilon_{t}-\eta\nabla_{\mathbf{A}}\mathcal{L}(\mathbf{A}^{t})^{T} \nabla_{\mathbf{A}}\mathcal{L}_{f}(\mathbf{A}^{t})}{\|\nabla_{\mathbf{A}} \mathcal{L}(\mathbf{A}^{t})\|_{F}^{2}}\nabla_{\mathbf{A}}\mathcal{L}(\mathbf{A} ^{t}),\text{ otherwise},\end{cases} \tag{4}\]

_where \(\epsilon_{t}=\operatorname{sign}\big{(}\nabla_{\mathbf{A}}\mathcal{L}(\mathbf{A} ^{t})^{T}\nabla_{\mathbf{A}}\mathcal{L}_{f}(\mathbf{A}^{t})\big{)}\)._

The proof of Theorem 2 is provided in Appendix A.2. It is worth noting that the solution in Equation (4) cannot be leveraged directly in the discrete domain. Hence, we use the differences \(\Delta\mathcal{L}_{f}^{t}(u,v)=\mathcal{L}_{f}(flip_{(u,v)}\mathbf{A}^{t})- \mathcal{L}_{f}(\mathbf{A}^{t})\) and \(\Delta\mathcal{L}^{t}(u,v)=\mathcal{L}(flip_{(u,v)}\mathbf{A}^{t})-\mathcal{L} (\mathbf{A}^{t})\) as zeroth-order estimations (Chen et al., 2017; Kariyappa et al., 2021) of \(\nabla_{\mathbf{A}_{[i,v]}}\mathcal{L}_{f}(\mathbf{A}^{t})\) and \(\nabla_{\mathbf{A}_{[i,v]}}\mathcal{L}(\mathbf{A}^{t})\), and replace them in Equation (4), respectively. Moreover, we minimize the utility budget as \(\epsilon_{t}=0\)
to constrain the model utility change after the flipping as strictly as possible. Consequently, we adjust the scoring function to find the target edge as

\[\bar{r}^{t}(u,v)=\Delta\mathcal{L}^{t}_{f}(u,v)-\frac{(\mathbf{p}^{t})^{T}\mathbf{q}^{t}}{ \|\mathbf{p}^{t}\|_{2}^{2}}|\Delta\mathcal{L}^{t}(u,v)|, \tag{5}\]

for \((u,v)\in\mathcal{C}^{t}\), where \(\mathbf{p}^{t}\in\mathbb{R}^{|\mathcal{C}^{t}|}\) and \(\mathbf{q}^{t}\in\mathbb{R}^{|\mathcal{C}^{t}|}\) are denoted as \(\mathbf{p}^{t}_{[i]}=\Delta\mathcal{L}^{t}(\mathcal{C}^{t}_{[i]})\) and \(\mathbf{q}^{t}_{[i]}=\Delta\mathcal{C}^{t}_{f}(\mathcal{C}^{t}_{[i]})\), respectively. Here \(\mathcal{C}^{t}_{[i]}\) denotes the \(i\)-th edge in \(\mathcal{C}^{t}\). Equation (5) can also be seen as a balanced attacker's objective between maximizing \(\mathcal{L}_{f}(\mathbf{A}^{t+1})-\mathcal{L}_{f}(\mathbf{A}^{t})\) and minimizing \(|\mathcal{L}(\mathbf{A}^{t+1})-\mathcal{L}(\mathbf{A}^{t})|\). With \(\bar{r}^{t}(u,v)\), the pseudocode of our proposed attack algorithm is shown in Appendix C.1.

### Fast Computation

In this subsection, we focus on the efficient implementation of our sequential attack. The most important and costly part of our algorithm is to find the maximum value of \(\bar{r}^{t}(u,v)\) from \(\mathcal{C}^{t}\). This naturally requires traversing each edge in \(\mathcal{C}^{t}\), which is costly on a large graph. Hence, we develop a fast computation method to reduce the time complexity. Reviewing our model settings, we find that the output of node \(i\), \(g_{\mathbf{\theta}}(\mathbf{A},\mathbf{X})_{[i]}\), can be computed as \(g_{\mathbf{\theta}}(\mathbf{A},\mathbf{X})_{[i]}=\sum_{j\in\mathcal{N}_{i}}( \hat{\mathbf{d}}_{[i]}\hat{\mathbf{d}}_{[j]})^{-1}\hat{\mathbf{A}}_{[j,:]}\mathbf{ \mathbf{\theta}}=\mathbf{Z}_{[i,:]}\mathbf{\theta}\), where \(\hat{\mathbf{d}}\) is the node degree vector, \(\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}\), \(\mathcal{N}_{i}=\{j|\hat{\mathbf{A}}_{[i,j]}=1\}\), and \(\mathbf{Z}\) denotes the aggregated feature matrix which is crucial to the fast computation. We aim to reduce the time complexity from two perspectives: **(1)** reducing the time complexity of computing the score \(\bar{r}^{t}(u,v)\) for a specific edge \((u,v)\); and **(2)** reducing the size of the candidate edge set \(\mathcal{C}^{t}\). From perspective **(1)**, we compute \(flip_{(u,v)}\mathbf{Z}^{t}\) incrementally based on \(\mathbf{Z}^{t}\). Then we have \(g_{\mathbf{\theta}^{t}}(flip_{(u,v)}\mathbf{A}^{t},\mathbf{X})=flip_{(u,v)} \mathbf{Z}^{t}\mathbf{\theta}^{t}\). Consequently, both \(\Delta\mathcal{L}^{t}_{f}(u,v)\) and \(\Delta\mathcal{L}^{t}(u,v)\) can be obtained based on \(g_{\mathbf{\theta}^{t}}(flip_{(u,v)}\mathbf{A}^{t},\mathbf{X})\). Next, we discuss the computation of \(flip_{(u,v)}\mathbf{Z}^{t}_{[i,:]}\) into three cases and introduce them separately. We only discuss adding edge \((u,v)\), and leave removing edge \((u,v)\) in Appendix C.1. **Case 1**: If \(i\in\{u,v\}\), \(flip_{(u,v)}\mathbf{Z}^{t}_{[i,:]}=\frac{\hat{\mathbf{d}}_{[i]}}{d^{t}_{[i]} +1}(\mathbf{Z}^{t}_{[i,:]}-\frac{\hat{\mathbf{A}}_{[i,:]}\mathbf{X}\mathbf{X} +\mathbf{X}_{[i,:]}}{(\hat{\mathbf{d}}^{t}_{[i]}+1)^{2}}+\frac{\hat{\mathbf{A }}_{[i,:]}\mathbf{X}+\mathbf{X}_{[i,:]}}{(\hat{\mathbf{d}}^{t}_{[i]}+1)^{2}}\), where \(j\in\{u,v\}\backslash\{i\}\); **Case 2**: If \(i\in\mathcal{N}^{t}_{u}\cup\mathcal{N}^{t}_{v}\backslash\{u,v\}\), \(flip_{(u,v)}\mathbf{Z}^{t}_{[i,:]}=\mathbf{Z}^{t}_{[i,:]}-\mathbb{I}_{i\in \mathcal{N}^{t}_{u}}\cdot(\frac{\hat{\mathbf{A}}^{t}_{[i,:]}\mathbf{X}}{d^{t }_{[i]}d^{t}_{[i]}}-\frac{\hat{\mathbf{A}}^{t}_{[i,:]}\mathbf{X}+\mathbf{X}_{[ i,:]}}{d^{t}_{[i]}d^{t}_{[i]}+1})-\mathbb{I}_{i\in\mathcal{N}^{t}_{u}}\cdot( \frac{\hat{\mathbf{A}}^{t}_{[i,:]}\mathbf{X}}{d^{t}_{[i]}d^{t}_{[i]}}-\frac{ \hat{\mathbf{A}}^{t}_{[i,:]}\mathbf{X}}{d^{t}_{[i]}d^{t}_{[i]}}-\frac{\hat{ \mathbf{A}}^{t}_{[i,:]}\mathbf{X}+\mathbf{X}_{[i,:]}}{d^{t}_{[i]}d^{t}_{[i]}} )\), where \(\mathbb{I}_{i\in\mathcal{N}}=1\) if \(i\in\mathcal{N}\), and \(\mathbb{I}_{i\in\mathcal{N}}=0\) otherwise; **Case 3**: If \(i\not\in\mathcal{N}^{t}_{u}\cup\mathcal{N}^{t}_{v}\), \(flip_{(u,v)}\mathbf{Z}^{t}_{[i,:]}=\mathbf{Z}^{t}_{[i,:]}\). From perspective **(2)**, we only choose the influential edges2 as \(\mathcal{C}^{t}\). Finally, flipping \((u,v)\) is highly likely to increase \(\mathcal{L}_{f}\) only if it results in significant changes to the predictions of a large number of nodes. Based on the aforementioned discussions, flipping \((u,v)\) can only affect the soft prediction of nodes in \(\mathcal{N}^{t}_{u}\cup\mathcal{N}^{t}_{v}\) (case 1 and 2). Hence, we consider \((u,v)\) as an influential edge if the predictions of nodes in \(\mathcal{N}^{t}_{u}\cup\mathcal{N}^{t}_{u}\) are easy to be changed. To this end, we propose an importance score \(\rho^{t}(u,v)\) and collect the edges corresponding to the top \(a\) importance scores into \(\mathcal{C}^{t}\). We have \(\rho^{t}(u,v)=\sum_{i\in\mathcal{N}^{t}_{u}\cup\mathcal{N}^{t}_{v}}M_{t}-| \mathbf{Z}^{t}_{[i,:]}\mathbf{\theta}^{t}|\), where \(M_{t}=\max_{i}|\mathbf{Z}^{t}_{[i,:]}\mathbf{\theta}^{t}|\). When the value of \(M_{t}-|\mathbf{Z}^{t}_{[i,:]}\mathbf{\theta}^{t}|\) is large, the prediction of node \(i\) is easy to be changed. We analyze the time complexity of our fast computation method as follows.

Footnote 2: Flipping the influential edges is very likely to increase the attacker’s objective.

**Proposition 2**.: _The overall time complexity of G-FairAttack with the fast computation is \(O(\bar{d}n^{2}+d_{x}an),\) where \(\bar{d}\) denotes the average degree._

Compared with computing \(\max_{(u,v)\in\mathcal{C}^{t}}\bar{r}^{t}(u,v)\) directly, which has a complexity of \(O(n^{4})\), our fast computation approach distinctly improves the efficiency of the attack. Note that the time complexity of G-FairAttack can be further improved in practice by parallel computation and simpler ranking strategies. The proof of Proposition 2, detailed complexity analysis, and ways of further improving the complexity are provided in Appendix C.2.

## 4 Experiments

In this section, we evaluate our proposed G-FairAttack. Specifically, we aim to answer the following questions through our experiments: **RQ1:** Can our proposed surrogate loss function represent
the victim loss functions of different kinds of victim models? **RQ2:** Can G-FairAttack achieve unnoticeable utility change? **RQ3:** To what extent does our fast computation approach improve the efficiency of G-FairAttack? Due to the space limitation, we provide more experimental results and discussions on the results in Appendix F.

### Experimental Settings

The evaluation of attack methods includes two stages. In the first stage, we use an attack method to obtain the perturbed graph structure. In the second stage, for the fairness evasion attack, we train a test GNN (i.e., victim model) on the clean graph and compare the output of the test GNN on the clean graph and on the perturbed graph; for the fairness poisoning attack, we train the test GNN on the clean graph to obtain the normal model and train the test GNN on the perturbed graph to obtain the victim model; then, we compare the output of the normal model on the clean graph and the output of the victim model on the perturbed graph. We adopt three prevalent real-world datasets, i.e., Facebook (Leskovec and Mcauley, 2012), Credit (Agarwal et al., 2021), and Pokec (Dai and Wang, 2021; Dong et al., 2022) to test the effectiveness of G-FairAttack. For attack baselines, we choose a random attack method (Hussain et al., 2022; Zugner et al., 2018), a state-of-the-art fairness attack method FA-GNN (Hussain et al., 2022), and two gradient-based methods Gradient Ascent and Metattack (Zugner and Gunnemann, 2019) (adapted from utility attacks). For test GNNs, we adopt a vanilla graph convolutional network (Kipf and Welling, 2017) and three different types of fairness-aware GNNs, Regularization (Zeng et al., 2021) (Reg) for \(\Delta_{dp}(\hat{Y},S)\), FairGNN (Dai and Wang, 2021) for \(I(\hat{Y},S)\), and EDITS (Dong et al., 2022) for \(W(\hat{Y},S)\). More details about baselines and datasets are provided in Appendices E.1 and E.2. We choose two mostly adopted fairness metrics, demographic parity \(\Delta_{dp}\)(Dwork et al., 2012) and equal opportunity \(\Delta_{eo}\)(Hardt et al., 2016), to measure the fairness of test GNNs. Larger values of fairness metrics denote more bias. In addition, we also report the accuracy and AUC score to show the utility of test GNNs.
degradation of fairness metric values after being attacked. The attack budget \(\Delta\) for Facebook and Pokec is \(5\%\), i.e., we can flip \(5\%\cdot|\mathcal{E}|\) edges at most; for Credit, the budget is \(1\%\). We ran each experiment three times with different random seeds and reported the mean value and the standard deviation. The experimental results are shown in Table 1 and Appendix. We can observe that **(1)**. G-FairAttack is the most effective attack method that jeopardizes the fairness of all types of victim GNN models, especially for fairness-aware GNNs. **(2)**. Compared with Gradient Ascent, G-FairAttack adds a fairness loss term (total variation loss) in the surrogate loss. Consequently, G-FairAttack outperforms them in attacking different types of fairness-aware GNNs, which demonstrates that our proposed surrogate loss helps our surrogate model learn from different types of fairness-aware victim models (**RQ1**). **(3)**. Some baselines outperform G-FairAttack in attacking vanilla GCN because the surrogate model of G-FairAttack is trained with the surrogate loss, including a fairness loss term, while the victim GCN is trained without fairness consideration. This problem can be addressed by choosing a smaller value of \(\alpha\) (weight of \(\mathcal{L}_{f}\)). Despite that, G-FairAttack successfully reduces the fairness of GCN on most benchmarks. **(4)**. Compared with gradient-based attacks (Gradient Ascent), G-FairAttack has less space complexity as it does not need to store a dense adjacency matrix.

### Ablation Study

**Effectiveness of Surrogate Loss.** To further answer **RQ1**, we compare G-FairAttack with two variants with different surrogate losses to demonstrate the effectiveness of our proposed surrogate loss. Our proposed surrogate loss function \(\mathcal{L}_{s}\) consists of two parts: utility loss term \(\mathcal{L}_{s_{g}}\) (CE loss) and fairness loss term \(\mathcal{L}_{s_{f}}\) (total variation loss). For the first baseline, we remove the fairness loss term from the surrogate loss and name it G-FairAttack-None. For the second baseline, we substitute the total variation loss with \(\Delta_{dp}\) loss, named as G-FairAttack-\(\Delta_{dp}\). In our problem, if the surrogate loss is the same as the victim loss (like white-box attacks), the attack method would definitely perform well. However, we show that G-FairAttack (with our proposed total variation surrogate loss) has the most desirable performance even with a **different victim loss from the surrogate loss**, which verifies the effectiveness of our surrogate loss. Hence, we choose FairGNN and EDITS as the victim models because their victim loss functions differ from the surrogate loss functions of G-FairAttack-None and G-FairAttack-\(\Delta_{dp}\). We conduct the experiment on Credit dataset in the fairness poisoning attack setting. The results are shown in Table 2. It is demonstrated that all three attack methods successfully increase the value of fairness metrics. Among all three attack methods, G-FairAttack achieves the best performance, which demonstrates that our proposed surrogate loss helps the surrogate model learn knowledge from various types of fairness-aware GNNs.

**Effectiveness of Unnoticeable Constraints.** To answer **RQ2**, we investigate the impact of utility constraints on G-FairAttack. We remove the discrete projected update strategy and the utility constraint in G-FairAttack as G-FairAttack-C. We compare the variation of \(\Delta_{dp}\) and the utility loss on the training set after the attack by G-FairAttack, G-FairAttack-C, and FA-GNN. We chose two mostly adopted victim models, i.e., GCN and regularization, to test the attack methods on Facebook. We set the utility budget at 5% of the utility loss on clean data. The results are shown in Figure 2. It demonstrates that **(1)**. Our G-FairAttack distinctly deteriorates the fairness of two victim models while keeping the variation of utility loss unnoticeable (\(<0.5\%\)). Therefore, G-FairAttack can attack the victim model with unnoticeable utility variation. **(2)**. Removing the utility constraint and the discrete projected update strategy from G-FairAttack, the variation of utility loss becomes much larger as the attack budget increases. The re

\begin{table}
\begin{tabular}{l|c|c} \hline Attack & FairGNN & EDITS \\ \cline{2-3}  & \(\Delta_{dp}\) (\%) & \(\Delta_{co}\) (\%) & \(\Delta_{dp}\) (\%) & \(\Delta_{co}\) (\%) \\ \hline Clean & 6.70 \(\pm\) 1.60 4.52 \(\pm\) 1.79 & 6.43 \(\pm\) 0.95 & 5.77 \(\pm\) 1.06 \\ G-FA-None & 7.87 \(\pm\) 1.31 5.68 \(\pm\) 1.42 & 10.47 \(\pm\) 1.91 & 9.95 \(\pm\) 1.71 \\ G-FA-\(\Delta_{dp}\) & 7.82 \(\pm\) 1.17 5.82 \(\pm\) 1.58 & 10.77 \(\pm\) 1.19 10.39 \(\pm\) 1.17 \\ G-FA & 8.06 \(\pm\) 1.90 6.10 \(\pm\) 2.03 & 11.26 \(\pm\) 1.50 10.87 \(\pm\) 1.56 \\ \hline \end{tabular}
\end{table}
Table 2: Results of G-FairAttack on Credit while replacing the total variation loss with other loss terms.

Figure 2: The changes of \(\Delta_{dp}\) and the utility loss function \(\mathcal{L}\) under different attack budgets.
sults of G-FairAttack-C verify the effectiveness of the fairness constraint and the discrete projected update strategy. **(3)**. G-FairAttack and G-FairAttack-C deteriorate the fairness of victim models to a larger extent than FA-GNN. Because G-FairAttack is a sequential greedy method, it becomes more effective as the attack budget increases. Hence, G-FairAttack is more flexible than FA-GNN.

### Parameter Study

In this subsection, we aim to answer **RQ3** and show the impact of the parameter \(a\) (the threshold for fast computation) on the time cost for the attack and the test results for victim models. We conduct experiments under different choices of \(a\). For the simplicity of the following discussion, we take \(a\) as the proportion of edges considered in \(\mathcal{C}^{t}\) (e.g., \(a=1e^{-3}\) means we only consider the top 0.1% edges with the highest important score). We record the attacker's objective \(\mathcal{L}_{f}\) under different thresholds during the optimization process as Figure3(a) to show the impact of \(a\) of the surrogate model.

We also record the fairness metrics of regularization-based victim models attacked by G-FairAttack and the average time of G-FairAttack in each iteration while choosing different values of \(a\) (in Figure3(b)) to show the impact of \(a\) on the attack performance and efficiency. Figure3(b) demonstrates the trade-off between effectiveness and efficiency exists but is very tolerant on the effectiveness side. In the range \([5e^{-4},1e^{-2}]\), the performances of G-FairAttack on the victim model are similar, while the time cost decreases distinctly when \(a\) gets smaller (the time cost of \(a=5e^{-4}\) is 95% lower than \(a=1e^{-2}\)). Therefore, in practice, we can flexibly choose a proper threshold to fit the efficiency requirement. In conclusion, our fast computation distinctly reduces G-FairAttack's time cost without compromising the performance.

## 5 Related Works

**Adversarial Attack of GNNs.** To improve the robustness of GNNs, we should first fully understand how to attack GNNs. Consequently, various attacking strategies of GNNs have been proposed in recent years. Zugner et al. (2018) first formulated the poisoning attack problem on graph data as a bilevel optimization in the discrete domain and proposed the first poisoning attack method of GNNs with respect to a single target node in a gray-box setting based on the greedy strategy. Following the problem formulation in (Zugner et al., 2018), researchers proposed many effective adversarial attack methods in different settings. Zugner and Gunnemann (2019) proposed the first untargeted poisoning attack method in a gray-box setting based on MAML (Finn et al., 2017). Chang et al. (2020) proposed an untargeted evasion attack method in a black-box setting by attacking the low-rank approximation of the spectral graph filter. Wu et al. (2019) proposed an untargeted evasion attack method in a white-box setting and a corresponding defense method based on integrated gradients.

**Adversarial Attacks on Fairness.** Many recent studies investigated the fairness attack problem on tabular data. Van et al. (2022) proposed an online poisoning attack framework on fairness based on gradient ascent. They adopted the convex relaxation (Zafar et al., 2017; Donini et al., 2018) to make the loss function differentiable. Mehrabi et al. (2021) proposed two types of poisoning attacks on fairness. One incorporates demographic information into the influence attack (Koh et al., 2022) by updating the poisoning set with PGD. The other generates poisoning samples within the vicinity of a chosen anchor based on the decision boundary. Solans et al. (2021) proposed a fairness poisoning attack method in both white-box and black-box settings. They formulated the poisoning attack problem as a bilevel optimization and adopted the KKT relaxation and a carefully designed initialization strategy for optimization. Chhabra et al. (2023) proposed a black-box attack and defense method for fair clustering. So far, only Hussain et al. (2022) investigated the fairness attack problem on graph data. They proposed a link injection method named FA-GNN that links nodes in different sensitive groups randomly to degrade the demographic parity metric.

Figure 3: The optimization curves, training time cost, and test fairness on regularization-based victim model corresponding to different values of \(a\).
## 6 Conclusion

Fairness-aware GNNs play a significant role in various human-centered applications. To protect GNNs from fairness attacks, we should fully understand potential ways to attack the fairness of GNNs. In this paper, we study adversarial attacks on fairness of GNNs as a bilevel optimization problem. We propose the first unnoticeable requirement for fairness attacks. We design a novel surrogate loss function to target various types of fairness-aware GNNs. We then propose a sequential attack algorithm to solve the problem, and a fast computation approach to reduce the time complexity. Extensive experiments on three real-world datasets verify the efficacy of our method.
