Adversarial Attacks on Fairness of Graph Neural Networks
Authors: Binchi Zhang
Yushun Dong
Chen Chen
Yada Zhu
Minnan Luo
Jundong Li
Venue: ICLR 2024 poster (2024)
Keywords: Adversarial Attacks
Algorithmic Fairness
Graph Neural Networks
Primary area: societal considerations including fairness, safety, privacy
TL;DR: This paper proposed G-FairAttack, a gray-box attack to jeopardize the fairness of different types of GNNs with an unnoticeable effect on the utility.

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.

Published as a conference paper at ICLR 2024
ADVERSARIAL ATTACKS ON FAIRNESS OF GRAPH NEURAL NETWORKS
Binchi Zhang', Yushun Dong', Chen Chen', Yada Zhu², Minnan L Li' 'University of Virginia
2BBM Research
" an Jiaotong University
epb6gw@rizginia.edd
ABSTRACT
Tairness-aware graph neural networks (GNNs) have gained surge of attention as they reduce the bias of predictions on any demographic group (c.g.. female) in graph- based applications. Although these methods greatly improve the algorith- mic fairness of GNNs, the faimess can be easily corrupted by carefully designed adversarial attacks. In this paper, we investigate the problem of adversarial attacks fairness of GNNs and propose G-FairAttcck, general framework for attacking various types of fairness-aware GNNs in terms of fairness with an unnoticeable effect on prediction utility. In addition, propose a fast computation technique to reduce the time complexity of G-FairAttack. The experimental study demon- strates 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 fairness-aware GNNs and guides further re- search on the robustness of GNNs in terms of fairness.
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), rec- ommender systems (Ying et al., 2018; Fan et al., 2019; Yu et al., 2021), and healthcare (Choi et al., 2017: Li al., 2022b; Fu et al., 2023). Despite that, many recent studies (Dai & Wang, 2021; Wang et al., 2022b; 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. Con- sequently, 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 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 built-in fairness-enhancing mechanism. For instance, we consider GNN-based recommender system in social networks. In scenarios regarding commercial competition 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 faimess attack model. According to the fairness attack algorithm, the adversary can then modify the attributes and connections of these compromised accounts. As 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 faimess of GNNs in this paper. Despite the importance of investigating the faimess attack of GNNs, most existing studies (Zügner et al., 2018; Zügner & Günnemann, 2019; Bojchevski & Günnemann, 2019; Dai et al., 2018; Xu et al., 2019) only focus on attacking the utility of GNNs (e.g., prediction

---

Published as a conference paper at ICLR 2024
accuracy) and neglect the vulnerability of GNNs in the faimess 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 (Zügner et al., 2018: Zügner & Güinnemann, 2019; Wang & Gong, 2019; Sun et al., 2019) where the attacker cannot access the architecture or parameters of the victim model (Jin et al., 2021; Sun al., 2022). A common strategy in gray- box attacks is to train a surrogate model (Züggnrr et al., 2018: Zügner & Günnemann, 2019) to gain more knowledge on the unseen victim model for the attack. Compared with conventional adversarial attacks, our attack on fairnsss 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.. 2022a). Because the victim model is unknown and can be any type of fairness-an aware GNN, the attacker should find a proper surrogate loss to represent different types of loss functions of fairness-awe 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 (Zügner 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 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: carefully designed surrogate loss function and an op- timization method. To tackle the first challenge, we categorize existing three types based on their fairness loss terms. Then we propose 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 non-gradient attack algorithm to solve the constrained optimization problem, which is verified have a better performance than previous gradient- baseed methods. Moreover, we propose a fast computation strategy to improve the scalabil- ity of G-FairAttack. Our contributions can be summarized follows.
aware GNNs into
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 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 non-gradient attack method. In addition, we propose fast computation approach to reduce its time complexity.
Experimental Evaluation. We conduct extensive experiments three real-world datasets with four types of victim models and verify that our proposed G-FairAttack successfully jeopardizes the fairnsss of various fairness- GNNs with an unnoticeable effect on prediction utility.
2 PROBLEM DEFINITION
Notation and Preliminary. We use bold uppercase letters, e.g., X, to denote matrices, and use X1..j. X and X 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., æ, to denote vectors, and use d to denote the i-th element. We use Px (.) and (-) to denote the probability density function and the cumulative distribution function for a random variable X, respectively. We use & = [V,E,X) X) to denote an undirected attributed graph. V = (UI...., "n and & C V x V denote the node set and the edge set, respectively, where n = |V| is the number of nodes. X E _g denotes the attribute matrix, where d, is the number of node attributes. We use A E {0, 1] to denote the adjacency matrix, where A = 1 when (i.j) E E and A = 0 otherwise. In the node classification task, some nodes are associated with ground truth labels. We use Varin to denote the
labeled (training) set, Viest = Vl Vrain to denote the unlabeled (test) set, and y to denote the set of labels. Most GNNs take the adjacency matrix A and the attribute matrix X as the input, and obtain
2

---

Published as a conference paper at ICLR 2024
the node embeddings used for node classification tasks. Specifically, we use fo {0, 1) x Raxd, + IRaxe to denote a GNN model, where 6 collects all learnable model parameters. We use a (Af(A, to denote soft predictions where a(.) is the softmax function. A conventional way to train a GNN model is minimizing a utility loss function L [Jo, A, Y, Virai) (e.g.. CE loss) over the training set. In human-centered scenarios, each individual is usually associated with sensitive attributes (c.g., gender). We use S = {s1,... },) to denote a sensitive attribute set, where s; is the sensitive attribute of the node v;. Based on the sensitive attributes, we can divide the nodes into different sensitive groups, denoted as Vi...., VK. where V = {uiss; 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., 2023a). Hence, the objective of training fairness-aware GNNs generally contains two aspects; one is minimizing the utility loss, i.e., L (Jo, A, X, Vuain), the other is minimizing the discrimination between the predictions over different sensitive groups, denoted as Cy (fe. X,Y) V,S), S). It is worth
noting that L is the CE loss in most cases, but there various types of C, for training fair GNNs.
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 pertur- bation. this paper, for the simplicity of discussion, we focus on two different sen- sitive 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 Formulation.
S S=0
Allack
S=1
Class
Class
Victim GNN
Vietim GNN
Sey = 0%
0
Aap= 66%
Am- 0%
Aa= 100%
Fair Prediction
Acc 83%
Blased Prediction
Acc 83%
Figure 1: A toy example of fairness attacks of GNNs with unnoticeable effect on prediction utility.
Problem 1. Attacks on Fairness of GNNs with Unnoticeable Effect on Prediction Utility. Let (V,E.) be an attributed graph with the adjacency matrix A. Let Vinain and Vien be the labeled and unlabeled node sets, respectively. y be the label set corresponding to V Vinin and S be the sensitive auribute value set of V. Let go be a surrogate GNN model, Las L. and Lg be the surrogate loss, utility loss, and fairness loss, respectively. Given the attack budget A and the utility variation budget e, the problem of attacks on fairness of GNNs is formulated as follows.
max
f,y (go-, A', N, Vress: S)
A'EF
s.t. 0" = -arg min Cg (90- A.).), I|A' - -AlIe S 2A,, 0 IC(gor, X. Virain) L(go-, N, Virain) SC,
(1)
where F the feasible space of the poisoned graph structure A', ga- is a trained surrogate model.
In this problem, the attacker's objective L (go- A', X, Viea, S) measures the bias of the predic- tions on test nodes. The surrogate model ge- is trained based on a surrogate loss [ge A, X, V)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 at- tack 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 À A, then Problem boils down to the fairness eva- sion attack; and if À = A', then Problem I becomes faimess poisoning attack. In this paper, use demographic parity (Navarin et al., 2020) as the attacker's 's objective Ly, the CE loss as utility loss L, and two-layer linearized GCN (Zügner et al., 2018) as the surrogate model ge. These choices have been verified by many previous works (Zügner et al., 2018: Zügner & Günnemann, 2019; Xu al., 2019) to be effective in attacking the prediction utility of GNNs, while also be changed
3

---

Published as a conference paper at ICLR 2024
flexibly according to the specific task. An illustration of our problem is shown in Figure 1. We leave the detailed explanation of Figure in Appendix B.
METHODOLOGY
In this section, first introduce the design of the surrogate loss L. which is the most critical part in Problem 1. Then, we propose a non- con-gradient optimization method to solve Problem I and propose a fast computation technique to reduce the time complexity of our optimization method.
3.1 SURROGATE LOSS DESIGN
Existing Loss on Fairness. The loss functions of all existing sainess-awaree GNNs can be divided into two parts: utility loss term (CE loss that is shared in common) and faimess loss term (varies from different methods). Correspondingly, our surrogate loss function is designed as L, = Ls, + abos, where L._ is the utility loss term, i.e., the CE loss, Ss, is the faimess loss term aim to study, and a is the weight coefficient. Let Y E [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). Adp (Y,, S) = [Pr(Y 2 = PorPp)PPP'' >
g = =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 Pv.s(e.))
training. (2). I(Ý,S) = -o' EyPryse Sr,ss,(,2 i) log P=(2)Pr(S=7] mutual information of the output and the sensitive attribute (Dai & Wang, 2021; Bose & Hamilton, 2019; Kang al., 2022), that reduces the dependence between the model output and the sensitive attribute during training. (3). W(Ý, So | o
(v) - F-1 vis=i ) (v)ldy: Wasserstein--1 distance of the output on different sensitive groups (Fan et al., 2021; Dong et al., 2022a), 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 fair- ness Ls,, aiming at representing all types of aforementioned fairness loss terms, e.g., (Y, T(Ý,)), and W W(Ý,S)) In particular, idea is to find a common upper bound for these fairness loss terms as Ls,, Therefore, during the training of the surrogate model, Ls, is minimized to a small value, and all types of fairness loss terms become even smaller consequently. In this way, the sur- rogate 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 novel surrogate (=)s=(()))d i.e., the total variation of Ý on different sensitive groups. We can prove that (V) is common upper bound of A Adp(Y ( T(Y,S) ,S) (at certain condition), and W W(Y, (S,S) so it can represent all types of fairness loss functions. Theorem 1. We have (Y, S) and W WYY.S. upper bounded by TV SS. Moreover, assuming (2) 2 I,Pr(S = holds for any E 1], I(Ý,S) is also upper bounded by TV,
loss function faimess TV(Ý, S) -o (P)
The proof of Theorem 1 is shown in Appendix A.I. We also provide a more practical variant of Theorem 1 with a weaker assumption Appendix A.I. Combining C., (total variation loss) and L.,, (CE loss), our surrogate loss function is L. = CE A, X, + aTV A, S). Since the probability density function of the underlying random variable Ý is difficult to calcu- late, we leverage the kernel density estimation (Parzen, 1962) to compute the total variation loss with the output soft predictions go X). The kernel estimation is computed as (²)s=(()) =
A APP Ejen, K( (((=9o(A.X)o) for 0, 1, where K(:) is kernel function and is a positive band- width constant. Then we exploit the numerical integration to compute the total variation loss as
Pris- j - Pyls=1
TV A, S)
2
1=1
where m is the number of intervals in the integration. Consequently, we obtain a practical calculation of our proposed surrogate loss L.--
4

---

Published as a conference paper at ICLR 2024
3.2 OPTIMIZATION
Considering that Problem is a bilevel optimization problem in a discrete domain, it is extremely hard find the exact solution. Hence, we resort the greedy strategy and propose sequential attack method. Our sequential attack flips target edges' sequentially to obtain the optimal poisoned structure A' It is worth noting that many attack methods on model utility find the target edge corresponding to the largest element of the gradient of A, namely gradient-based methods (Zügner & Günnemann, 2019; Xu et al., 2019; Wu al., 2019; Geisler et al., 2021). However, we find the efficacy of gradient-basee based methods is not guaranteed.
Proposition Gradient- bassd methods for optimizing the graph structure are not guaranteed to decrease the objective function.
We leave detailed analysis of the shortcomings of gradient-basee 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 We let A A and train the surrogate model to obtain 09, i.e., solving 0 = arg ming L. (go, A, X. V, S). For t ,,,,..., To. we find the maximum score r' in the t-th iteration as
max r'(u,)) v) SCy (u, v) Ly flip(u,.) A') Cy(gor, (u,D)EC(
(3)
where C is the candidate edge set in the t-th iteration; flip(a.)) A denotes the adjacency matrix after flipping the edge (u, v): flip(u..) A [rJ]] 1 [r,]] if (i, = (u, or (i.j) (u, u), and ARJl otherwise. After solving Equation (3), denote the solution (u', v²). Then we update A' as A++1 flippue, ,² in the t-th iteration. For the faimesss poisoning attack, retrain the surrogate model based A A++1 as 0C+1 arg ming (go, A 1+1) update the surrogate model. After To iterations, we have A = A as the solution of Problem 1.
flip(..))
Next, to handle the first constraint, we let To S A and have AA' S ETe 2 consequently. For the second constraint, we aim to make every flipping unnoticeable in terms of model utility, i.e., making (C(A++) C(A*) as small as possible. We notice that this con- strained optimization problem can be easily solved by projected gradient descent (PGD) (Nocedal & Wright, 2006) in the continuous domain by solving A (-1 argmin ((At) ((A))- || (A''
, IIE, where e; is the budget of the f-th iteration that satisfies Σ S and is the learning rate. To solve this problem, we have the following theorem.
Theorem 2. The optimal poisoned adjacency matrix A in the t - 1-th iteration given by PGD, i.e. the solution of A ++1 argmin -(A))) I| ||A' (A' + (A is
1 V (A') n| V (AC) A' + (AC)(A + Ezt: VAACAA) VAC(A'), otherwise,
A 1+1
(4)
[VAC(A))
where = sign (VAC(A)VVAC(AA")
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 (C, v) (f(lipttu,) A²) (A') and AC v) [(flip(a..)) order estimations (Chen al., 2017: Kariyappa et al., 2021) V VA,,.,) (A) (A') and V ju.n) V..,,,)ff ((A'), and replace them in Equation (4), respectively. Moreover, minimize the utility budget e, 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
L(At) as zeroth-
(p')Tq' (u, 1pp11
F'(u,) v) AC, u)
(5)
for (u,v) E C² where p' E Rlcll and q² E IRlll are denoted as Piu = AC' (Ct,)) and q = ACy(C)))) respectively. Here Cj denotes the i-th edge in C.. Equation (5) can also be seen balanced attacker's objective between maximizing -- (A*) ') and minimizing [C(A++))
((A')) With Fu, v), the pseudocode of our proposed attack algorithm is shown in Appendix C.I.
Flipping the target edge increases the attacker's 's objective the most.
5

---

Published as a conference paper at ICLR 2024
3.3 FAST COMPUTATION
In this subsection, we focus on the efficient implementation of our sequential attack. The most im- portant and costly part of our algorithm is to find the maximum value of 7 (u, v) from C¹. This naturally requires traversing each edge in C", which is costly on a large graph. Hence, we develop a fast computation method reduce the time complexity. Reviewing our model settings, we find that the output of node i, go [A, X)1x. can be computed as (A, {) EJEN; ( 3A XO
1}. and z de- notes 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 (', 2) for specific edge v); and (2) reducing the size of the candidate edge set C². From perspective (I), we compute a incrementally based on Z'. Then we have Io. (f)
R, where d is the node degree vector, A A 1 N. = [رلرزز
A X) = f) Z Consequently, both AC) (u, v) and AL, v) can be ob- tained based on go (flip(u.e) A Next, we discuss the computation of flip(u..) (at into three cases and introduce them separately. We only discuss adding edge (u, v). and leave moving edge (u, v) in Appendix C.1. Case 1: If i E fu,e). flip(n..) Zial
t dip
(2.
A
Afugx+Xui + X where j E (1,)) Case 2: NEENNMM (u, v), (dl +1)²
+1)(d))
(/..1 - TEEN Al.. Afm.xX+(pu.l) TIENY (
Afu. Af..)xXX(a.))
flip( (u.)) [/a
) where
df (d
digdd. (d.
LEN = l E N, and LEN = 0 otherwise; Case 3: if & No UN, flip(a..) 2 [a..g-
From perspective (2), we only choose the influential edges² as C.. Specifically, flipping (u, v) is highly likely to increase L, 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 No U N (case and 2). Hence, we consider (u, v) as influential edge the predictions of nodes in No U are casy to be changed. To this end, we propose an im- portance score p² (u, v) and collect the edges corresponding to the top importance scores into C'. We have p²(u, v) = EieNquNy Mj- ( 0'). where Mj = max; [r..] 0% When the value of M,- | 0 is large, the prediction of node i is easy to be changed. We analyze the time complexity of our fast computation method as follows.
Proposition 2. The overall time complexity of G-FairAttack with the fast computation is O(dn? + dy)m), where d denotes the average degree.
Compared with computing maX(u.)) F(u, v) directly, which has a complexity of O 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 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 follow- ing questions through our experiments: RQI: Can our proposed surrogate loss function represent the victim loss functions of different kinds of victim models? RQ2: Can G- G-FairAttack achieve un- noticeable utility change? RQ3: To what extent does our fast computation approach improve the efficiency of G- G-FairAttack? Due to the space limitation, we provide more experimental results and discussions on the results in Appendix F.
4.1 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 faimess evasion attack, train a test GNN (i.e., victim model) on the clean graph and compare the output of the test GNN
Flipping the influential edges is highly likely increase the attacker's objective.

---

Published as a conference paper at ICLR 2024
Table 1: Experiment results of fairness evasion attack, where '.' means the out-of-memory case. To test the effectiveness of attack methods, we compare the fairesss metric (Adp) of the results of attack methods and the clean input data (larger value means less fair). We highlight the two most effective attack methods (with the largest fairness drop) with bold and underline for each victim model.
Facebook
Pokec z
Credit
Vietim
Attack
ACC(%)
(%)
ACC(%)
(%)
ACC(%)
Adp(%)
Clean
80.89 0.00 5
67.09 0.13
7.13 1.17
70.75
0.45
13.30 1.89
Random
80.68 = 0.18 5.04 1 0.27
67.09
0.20
7.11 + 1.48
71.35
1: 0.36
13.53
2.12
GCN
FA-GNN
80.46 0.18 8.73 = 0.29
66.16
0.14
1.57 1 0.50
71.02 0.54
15.02 + 2.25
Gradient Ascent
80.68 = 0.49
6.46 0.79
67.17 0.17
3.59 0.66
G-FairAttack
81.00 = 0.37
8.13 0.74
67.24 0.29
5.08 + 1.38
71.00 + 0.52
13.64 + 1.86
Clean
80.36 0.18
3.06
= 0.58
66.75 0.11
2.41 0.29
71.60 + 2.09
0.63 0.52
Random
80.15 = 0.18
0.22 0.11
66.36
2.00 0.00
71.66
2.66
0.65 0.68
Reg
FA-GNN
79.73 0.18
4.67
1 0.58
66.16 0.09
5.83
1 0.33
71.81
4: 2.75
1,25 1: 0.33
Gradient Ascent
80.36 0.18
3.99
= 0.58
66.89 +:28
3.66 0:46
G-FairAttack
81.00 = 0.37
6.84
- 0.31
65.97
6.03
+ 0.54
71.32
2.83
3.01 + 1.23
Clcan
79.94 0.64
2.00 = 1.77
65.42 0.52
1.37 0.83
71.98 + 1.81
2.65 + 0,98
Random
79.14 0.32 0.37
0.38
64.96
1.35 0.71
72.00
1.80
2.72 0.95
FaiGGNN
FA-GNN
79.14 = 0.32
3.00
1 2.31
64.86 0.64
3,27 - 0.75
71.98
1.79
1.98 1: 1.15
Gradient Ascent
79.86 0.54
2.32
1: 2.41
65.01 1 0.53
1.40 1: 0.77
G-FairAttack
79.46 0.61
3.23
= 2.03
65.33 0.55
2.63 0.75
72.01 1.82
2.79 + 1.52
Clean
79.30 = 0.00
0.27 = 0.00
64.68 + 0.35
1.89 + 0.83
70.99 + 1.63
7.49 + 1.64
Random
77.39 0.64
4.65
= 0.94
64.68 + 0.35
1.89 + 0.83
69.88 + 1.40
7.56
+ 2.30
EDITS
FA-GNN
78.77 = 0.18
0.60
0.35
64.68
1: 0.35
1.89 0.83
70.99 1.63
7.50 1.63
Gradient Ascent
77.07 = 0.00
3.25
1 0.94
64.68
1 0.35
1.89
1 0.83
G-FairAttack
78.24 = 0.36
5.55 + 0.47
64.91 + 0.63
4.25 + 0.77
69.88 + 1.40
7.56 + 2.30
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 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 & Mcauley, 2012), Credit (Agarwal et al., 2021), and Pokec (Dai & Wang, 2021; Dong et al., 2022a) to test the effectiveness of G-FairAttack. For attack baselines, we choose a random attack method (Hussain et al., 2022: Zügner et al., 2018), state-of-the-an -o-tte--rt fairness attack method FA-GNN (Hussain et al., 2022), and two gradient- based methods Gradient Ascent and Metattack (Zügner & Günnemann, 2019) (adapted from utility attacks). For test GNNs, we adopt a vanilla graph convolutional network (Kipf & Welling, 2017) and three different types of fairness-aware GNNs, Regularization (Zeng et al., 2021) (Reg) for (Y, FairGNN (Dai & Wang. 2021) for I(Y, S). and EDITS (Dong et al., 2022a) for W(Y, S). More details about baselines and datasets are provided in Appendices E.1 and E.2. We choose two mostly adopted fairness metries, demographic parity Adp (Dwork et al., 2012) and equal opportunity Aeo (Hardt et al., 2016), to measure the fairness of test GNNs. Larger values of faimess metrics denote more bias. In addition, we also report the accuracy and AUC score to show the utility of test GNNs.
4.2 EFFECTIVENESS OF ATTACK
We compare G-FairAttack with three attack baselines in the fairness evasion attack and fairness poisoning attack (in Appendix F.l) settings on three prevalent real-world datasets. Specifically, to test the effectiveness of attack methods, we choose four different kinds of victim GNN models to test the degradation of fairness metric values after being attacked. The attack budget A for Face- book and Pokec is 5%, i.e., we can flip 5% [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 F. We can ob- serve that: (I), 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-FaarAttack adds a faimess loss term (total variation loss) in the surrogate loss. Conse- quently, G-FairAttack outperforms them in attacking different types of fairness- GNNs, which demonstrates that our proposed surrogate loss helps our surrogate model learn from different types of faimess-awan victim models (RQ1). (3). Some baselines outperform G-FairAttacd in attacking
7

---

Published as a conference paper at ICLR 2024
vanilla GCN because the surrogate model of GG-FairAttae is trained with the surrogate loss, includ- ing a fairness loss term, while the victim GCN is trained without fairness consideration. This prob- lem can be addressed by choosing smaller value of (weight of Lj). Despite that, G-FairAttack successfully reduces the fairesss 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 dense adjacency matrix.
4.3 ABLATION STUDY
Effectiveness of Surrogate Loss. To further answer RQI, we compare G- FairAttack with two variants with dif- ferent surrogate losses to demonstrate the effectiveness of our proposed sur- rogate loss. Our proposed surrogate loss function C. consists of two parts:
Table 2: Results of G-FairAttack on Credit while replacing
the total variation loss with other loss terms.
FairGNN
EDITS
Attack
Ap (%)
Ao (%)
A (%)
Aeo (%)
Clean
6.70 1.60 4
6,43
5.77 = 1.06
G-FA-None
7.87 + 1.31 5.68
1.42
10.47
9,95 - 1.71
G-FA-Adp
7.82 + 1.17 5.82
1.58
10.77
1.19 10.39 1.17
G-FA
8.06 + 1.90 6.10 2.03 11,26 + 1.50 10.87 + 1.56
utility loss term L.,. (CE loss) and
fairness loss term C., (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, substitute the total variation loss with Adp loss, named as G-FairAttack-AAu In our problem, if the surro- gate 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 vietim loss functions differ from the surrogate loss functions of G-FairAttack-None and G-FairAttackk-A ness 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.
We conduct the experiment on Credit dataset in the fair-
Effectiveness Unnoticeable Constraints. To answer RQ2, we investigate the impact of utility constraints on G-FairAttack. We re- move the discrete projected update strategy and the utility constraint G-FairAttack as G- FairAttack-C. We compare the variation of Adp and the utility loss on the training set after the attack by Attacr, 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
GCN
Reg
Ado Change 1%
EA GNN
GNN
50
G.A-C
G-FACC
GBA
G
25-
Change 1%
FA-GNN
FA-GNN G-FACC
10-
G-FA-C
G-FA
G-FA
5
budget 5% of the utility loss on clean data.
The results are shown in Figure 2. It demon- strates that: (1). Our G-FairAttack distinctly deteriorates the fairness of two victim models while keeping the variation utility loss unno- ticeable (< 0.5%). Therefore, G-FairAttack can attack the vietim 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 the attack budget increases. The sults of G-FairAttack-C verify the effectiveness of the faimess constraint and the discrete projected update strategy. (3), G-FairAttack and G-FairAttack- deteriorate the fairness of victim models to larger extent than FA-GNN, Because G-FairAttack is a sequential greedy method, it becomes more effective the attack budget increases. Hence, G-FairAttack is more flexible than FA-GNN.
1%
2%
5%
10%
1%
2%
5%
10%
Flipped Edges / %
Flipped Edges %
Figure 2: The changes of Dap and the utility loss function L under different attack budgets.
4.4 PARAMETER STUDY
In this subsection, we aim to answer RQ3 and show the impact of the parameter a (the threshold for fast computation) the time cost for the attack and the test results for vietim models. We conduct
8

---

Published as a conference paper at ICLR 2024
experiments under different choices of a. For the simplicity of the following discussion, we take as the proportion of edges considered in C' (e.g., a = le 1 means we only consider the top 0. % edges with the highest important score). We record the attacker's 's objective 4 under different thresholds during the optimization process as Figure 3(a) to show the impact of a of the surrogate model.
We also record the fairnsss metries of regularization-baat victim models attacked by G-FairAttack and the average time of G- FairAttack in each iteration while choosing dif- ferent values of a (in Figure 3(b)) to show the impact of a on the attack performance and ef- ficiency. Figure 3(b) demonstrates the trade- off between effectiveness and efficiency exists but is very tolerant on the effectiveness side. In the range [5e_,, 2I, the performances of G-FairAttack on the victim model are similar, while the time cost decreases distinctly when gets smaller (the time cost of a = 5e is 95% lower than a 1) Therefore, in practice,
40
lo4
Spd
Time is Fummss Metric
30
led
20
40
10
20
1000
Iterations
The
(a) Curves of attacker's 's ob- (b) Test fairness metrics jective.
and training time cost.
The optimization curves, training time cost, and test fairness on regularization- tim model corresponding to different values of a. we can flexibly choose a proper threshold to fit the efficiency requirement. In conclusion, our fast computation distinetly reduces G-FairAttack's 's time cost without compromising the performance.
Figure 3:
vic-
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. Zügner 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 gray-box setting based on the greedy strategy. Following the problem formulation in (Zügner et al., 2018), researchers proposed many effective adversarial attack methods in different settings. Zügner& & Günnemann (2019) proposed the first untargeted poisoning attack method in gray-box setting based on MAML (Finn et al., 2017). Chang et al. (2020a) 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) 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), and the other generates poisoned samples within the vicinity of a chosen anchor to skew the decision boundary. Solans et al. (2021) studied the faimees poisoning attack as a bilevel optimization and solved it by KKT relaxation with a novel initialization strategy. Chhabra et al. (2023) proposed a black-box attack and defense method for fair clustering- For graph data, Hussain et al. (2022) is the first to investigate the faimess attack problem, proposing FA-GNN that randomly injects links among different sensitive groups to promote demographic parity. In a concurrent study, Kang et al. (2023) investigated the fairness attack problem as a bilevel optimization and proposed FATE, meta- learning-based fairness attack framework that targets both group fairness and individual fairness.
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 faimess of GNNs. In this paper, we propose the first unnoticeable requirement for fairness attacks. We design novel surrogate loss function attack various types of faimess-aat aware GNNs. We also propose sequential attack algorithm to solve the problem, and fast computation approach to reduce the time complexity. Extensive experiments on three real-world datasets verify the efficacy of method.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Binchi Zhang and Jundong Li are supported by the Commonwealth Cyber Initiative award HV- 2Q23-003, JP Morgan Chase Faculty Research Award, and Cisco Faculty Research Award. Yada Zhu is supported in part by MIT-IBM Watson Al Lab research collaboration as part of the IBM Al Horizons Network.
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence. 2021.
Inayat Ali, Sonia Sabir, and Zahid Ullah. Internet of things security, device authentication and access control: review. International Journal of Computer Science and Information Security (ICCSIS), 2016.
Aleksandar Bojchevski and Stephan Günneeann. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning, 2019.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference Machine Learning, 2019.
Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopad- hyay. Adversarial attacks and defences: A survey, arXiv preprint arXiv:1810.0m 1a1.110000000,,,1 2018.
Heng Chang, Yu Rong. Tingyang Xu, Wenbing Huang. Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box adversarial framework towards attacking graph embed- ding models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020a.
Hongyan Chang, Ta Duy Nguyen, Sasi Kumar Murakonda, Ehsan Kazemi, and Reza Shokri. On adversarial bias and the robustness fair machine learning. arXiv preprint arXiv:2006.0888 20206.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, 2017.
Anshuman Chhabra, Peizhao Li, Prasant Mohapatra, and Hongfu Liu. Robust fair clustering: A novel fairness attack and defense framework. In International Conference on Learning Represen- tations (ICLR), 2023.
Edward Choi, Mohammad Taha Bahadori, Le Song, Walter F Stewart, and Jimeng Sun. Gram: graph-based attention model for healthcare representation learning- Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, 2017.
Enyan Dai and Suhang Wang. Say no the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang. Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning. 2018.
Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, 2022a.
Yushun Dong, Song Wang. Yu Wang, Tyler Denr, and Jundong Li. On structural explanation of bias in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022b.
Yushun Dong, Jing Ma. Song Wang, Chen Chen, and Jundong Li. Fairness in graph mining: A survey. IEEE Transactions Knowledge and Data Engineering, 2023a.
10

---

Published as a conference paper at ICLR 2024
Yushun Dong, Song Wang. Jing Ma, Ninghao Liu, and Jundong Li. Interpreting unfaimess in graph neural networks via training node attribution. Proceedings of the AAAI Conference on Artificial Intelligence, 2023b.
Yushun Dong, Binchi Zhang, Yiling Yuan, Na Zou, Qi Wang, and Jundong Li. Reliant: Fair knowl- edge distillation for graph neural networks. In Proceedings of the 2023 SIAM International Con- ference on Data Mining (SDM), 2023c.
Michele Donini, Luca Oneto, Shai Ben Nen-David, John S Shawe-Taylon Taylor, and Massimiliano Pontil. Em- pirical risk minimization under fairness constraints. Advances in Neural Information Processing Systems, 2018.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science confer- ence, 2012.
Wei Fan, Kunpeng Liu, Rui Xie, Hao Liu, Hui Xiong, and Yanjie Fu. Fair graph auto-encoder for unbiased graph representations with wasserstein distance. In 2021 IEEE International Conference on Data Mining (ICDM), 2021.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, 2019.
Shangbin Feng, Zhaoxuan Tan, Herun Wan, Ningnan Wang, Zilong Chen, Binchi Zhang, Qinghua Zheng, Wenqian Zhang, Zhenyu Lei, Shujie Yang, al. Twibot-22: Towards graph-based twitter bot detection. Advances in Neural Information Processing Systems, 2022.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta- veta-learning for fast adaptation of deep networks. In International conference on machine learning, 2017.
Danilo Franco, Nicolò Navarin, Michele Donini, Davide Anguita, and Luca Oneto. Deep fair models for complex data: Graphs labeling and explainable face recognition. Neurocomputing, 2022.
Xingbo Fu, Chen Chen, Yushun Dong, Anil Vullikanti, Eili Klein, Gregory Madden, and Jundong Li. Spatial-temporal networks for antibiogram pattern prediction. arXiv preprint arXiv:2305.0/ 2023.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojehevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs Advances in neural information processing systems, 2017.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 2016.
Hussain Hussain, Meng Cao, Sandipan Sikdar, Denis Helic, Elisabeth Lex, Markus Strohmaier, and Roman Kern. Adversarial inter-group link injection degrades the fairness of graph neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), 2022.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi. and Xia Hu, Fmp: Toward fair graph message passing against topology bias. arXiv preprint arXiv:2202.04413 042800011177.. 2022.
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adver- sarial attacks and defenses on graphs. ACM SIGKDD Explorations Newsletter, 2021.
Jian Kang, Tiankai Xie, Xintao Wu, Ross Maciejewski, and Hanghang Tong. Infofair: Information- theoretic intersectional faimess. In 2022 IEEE International Conference on Big Data (Big Data), 2022.
Jian Kang, Yinglong Xia, Ross Macicjewski, Jiebo Luo, and Hanghang Tong. Deceptive fairness attacks on graphs via meta learning. arXiv preprint arXiv:2310. 155553,, 2023.
11

---

Published as a conference paper at ICLR 2024
Sanjay Kariyappa, Atul Prakash, and Moinuddin K Qureshi. Maze: Data-free model stealing attack using zeroth-order gradient estimation. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning. 2022.
Jure Leskovec and Julian Mcauley, Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems, 2012.
Haoyang Li, Shimin Di, Zijian Li, Lei Chen, and Jiannong Cao. Black-box adversarial attack and defense on graph neural networks. 2022 IEEE 38th International Conference on Data Engi- neering (ICDE), 2022a.
Michelle M Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healthcare. Nature Biomedical Engineering, 2022b.
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference Learning Representa- tions (ICLR), 2021.
Lu Lin, Ethan Blaser, and Hongning Wang. Graph structural attack by perturbing spectral distance. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2022.
Yi-Ju Lu and Cheng-Te Li. GCAN: Graph-aware co-attention networks for explainable fake news detection social media. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pp. 505-514, 2020.
Jiaqi Ma. Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. Advances in neural information processing systems, 2020.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Adversarial attack graph neural networks an influence maximization problem. In Proceedings of the Fifreenth ACM International Conference Web Search and Data Mining, 2022.
Ninareh Mehrabi, Muhammad Naveed, Fred Morstatter, and Aram Galstyan. Exacerbating algo- rithmic bias through fairness attacks. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2021.
Nicolo Navarin, Luca Oneto, and Michele Donini. Learning deep fair graph neural networks. In European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 2020.
Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer, 2006.
Emanuel Parzen. On estimation of probability density function and mode. The annals of mathe- matical statistics, 1962.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 2019.
Jiezhong Qiu, Jian Tang, Hao Ma. Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social
influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018.
David Solans, Battista Biggio, and Carlos Castillo. Poisoning attacks on algorithmic faimess. In
Joint European Conference Machine Learning and Knowledge Discovery in Databases, 2021.
12

---

Published as a conference paper at ICLR 2024
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence, 2021.
Lichao Sun, Yingtong Dou, Carl Yang, Kai Zhang, Ji Wang, Yu Philip, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey, IEEE Transactions on Knowledge and Data Engineering, 2022.
Yiwei Sun, Suhang Wang. Xianfeng Tang, Tsung- Yu Hsieh, and Vasant Honavar. Node injection attacks on graphs via reinforcement learning. arXiv preprint arXiv:1909.066: 2019.
Minh-Hao Van, Wei Du, Xintao Wu, and Aidong Lu. Poisoning attacks on fair machine learning. In International Conference on Database Systems for Advanced Applications, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Binghui Wang and Neil Zhenqiang Gong, Attacking graph- classification via manipulating the graph structure. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019.
Nan Wang, Lu Lin, Jundong Li, and Hongning Wang. Unbiased graph embedding with biased graph observations. In Proceedings of the Web Conference 2022, 2022a.
Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr. Improving fairesss in graph neural networks via mitigating sensitive attribute leakage. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022b.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversar- ial examples for graph data: deep insights into attack and defense. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019.
Yinhao Xiao, Yizhen Jia, Chunchi Liu, Xiuzhen Cheng, Jiguo Yu, and Weifeng Lv. Edge computing security: State of the art and challenges. Proceedings of the IEEE, 2019.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui- Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: optimization perspective. In Proceed- ings of the 28th International Joint Conference on Artificial Intelligence, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018.
Junliang Yu, Hongzhi Yin, Jundong Li, Qinyong Wang, Nguyen Quoc Viet Hung, and Xiangliang Zhang. Self-supervised multi-channel hypergraph convolutional network for social recommenda- tion. In Proceedings of the Web Conference 2021, 2021.
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fair- ness constraints: Mechanisms for fair classification. In Artificial intelligence and statistics, 2017.
Ziqian Zeng, Rashidul Islam, Kamrun Naher Keya, James Foulds, Yangqiu Song, and Shimei Pan. Fair representation learning for heterogeneous information networks. In Proceedings of the Inter- national AAAI Conference on Weblogs and Social Media, 2021.
He Zhang, Xingliang Yuan, Chuan Zhou, and Shirui Pan. Projective ranking-based gnn evasion attacks. IEEE Transactions on Knowledge and Data Engineering, 2022.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Representations (ICLR), 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günneemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, 2018
13

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Proof
A.1 Proof of Theorem
15
Proof Theorem
B Attack Settings
18
C Fast Computation
19
C.I Fast Computation Sketch
19
C.2 Complexity Analysis
21
G-FairAttack vs Gradient-based Methods
E
Implementation Details
24
E.1 Datasets
24
E.2 Basclines B
24
E.3 Experimental Settings
25
E,4 Required Packages...
26
F Supplementary Experiments
27
E1 Effectiveness Attack
27
F2 Effectiveness of Surrogate Loss
27
E3 Attack Patterns..
28
E4 Attack Generalization
29
F55 Advanced Attack Baselines
31
G Defense Against Fairness Attacks of GNNs
32
H Broader Impact
34
14

---

Published as a conference paper at ICLR 2024
A PROOF
A. PROOF OF THEOREM 1
Theorem 1. We have Ddp 8) and W WYY, (S) upper bounded by TV (Ý,, S). Moreover, I(Y, ()) is also upper bounded by TV(Y; (Y, 5) if vz E [0, Pz(2) 2 I1,Pr(S = i) holds.
W(Y,)) .), and TV(Y, are all non-negative. We first prove that 4Yp(Y,S) is upper bounded by TV(Y,)) Recall that TV(Y,S) = So (P Pr]s=1 (z) we have
Proof. Adp(Y, SY, I(Y,
(8, Pr Y 2 1 1 S -00 Pr y
1 s s--11 =1)
2
J Pris=o(2) - (z)
$ / |PrIs=o())
(2) (p(8))-yppp s=1( sp)) dz
- L. |Pyiszo() - Py s=1 s de
-TV(Y,S).
Next, we prove that W(Ý,S) S) is also upper bounded by TV S).
W(Ý,S) = in Fris (v) F Fris= (v) dy
(6)
-/'' (r)s=o(=) (z) pr]s=1 (2) dz.
This equation holds because we know that ( F (1) = according to the property of cumulative distribution function and the fact that Y E [0. Hence y (y)s=o(=) and y ())s=1() form closed curve in [0, x [0, 1] in z-y plane. Consequently, Equation (6) could be seen computing the area of the closed curve from the y-axis and z-axis separately. Consequently, we have
(0) = Fyls=1() (0) = and or =
w( = L/ Frys=o(s) Fr)s=(()) dz
1.¹ 1." (z)s= - 1'" x (z)d= do
P - (x) dadx I.
| - PrIs=1 dz, I' E [0,1]
< [ |Pris=(>)d2 (2)s=1(z) dz
=TV("'.))
Finally, we prove that 7(8, ( upper bounded by TV S) E I,Pr(S = i). First, we have
I( = 1'' Σ (2, 1o
Pz,s(z,0) Px(2)Pr(S =)
dz
15

---

Published as a conference paper at ICLR 2024
.. Σ Pr(S = rss log
(r(s=i(>) Py (2) dz.
Let P. Pr(S 1) for i 0, then have Po P1 and Pz(z) 1 +
Pi (2)) According to the fact that log S 1 for E (0. 1], we let (-))-(()) and Py([2]
have
log Pris=(())
() =[ Σ P.P
(x(x) d2
(r))s=(())
< Σ P. Pg(2)
P:Pris=
(2))=
(2) de
P.
(2(2)
(7)
PoPiPr Pr)s=o(=) P s=)
+ ())))=1(2)
PoPiPy (2) (p]s==12) (2) - -P)(s=o(z)
dz
PoPr PoPris=o(2) + P3 P2P p)))==((2)
Po (Pris-(2)) - Pris=1(2 (2)
dz.
Po PoPris=0 (z) PiP PiPpls==
Given that Py(z) 2 PT,rr( = i) V2 E [0, 1), we have Po Po v PiPriss (2) PPo
Pi) PoP.. Consequently, have
I(YS)) S) $ S. (PrIs-o(() - P (=))= dz.
Considering that the training of fairness-aware GNNs makes the distributions Pris=o(2) and Pr)s=1(2) closer, assume that (Pr)==((>) (=)) < for [0. To verify this sumption, we conduct numerical experiments all three adopted datasets. Following our method- ology, we use the kernel density estimation to estimate the distribution functions Py)s=o(z) and Pris=I (2) and compute the value of Prisso( value of (2)) - Pyls=1(2) (2)] for 2 [0. 1] and obtain the results 0.1372 0.0425 for Facebook, 0.0999 0.0310 for Pokec z, and 0.0356 + 0.0074 for Credit (mean value and standard deviation under 5 random seeds), which are all far less than 1. Then, we come to
P (z) consequently. We record the largest
I () S (Piiso(()) Pris=1 (z) (V
(8)
In conclusion, we have proved that (Ý, and W(Y,S) are upper bounded by TV(Ý, S). Moreover, S)) is also upper bounded by TV(Ý, S) if V2 E Pp(x) Z 11,Pr(S i)
holds.
Remarks on Theorem 1. It is worth noting that I(Ý,S) S) < TV(Ý, S) stems from the condition of (x) Z 11,Pr(S = i), Vz [0, 1]. Although we are not able to always ensure the correctness of the condition in practice, we can still obtain from Theorem I that (1) the probability of the condition holds grows larger when the number of sensitive groups increases; (2) even in the binary case, the
condition is highly likely to hold in practice, considering that Pr(S 0) Pr(S 1) < (In
a binary case, we have Pr(s = 0) + Pr(s = 1) = 1: hence, Pr(s = 0)Pr(s = 1) = Pr(s
()(1 Pr(s 0)) & 1/4).
16

---

Published as a conference paper at ICLR 2024
To further improve the soundness of our theoretical analysis, can slightly loosen the condition (x( N I1,Pr(S = 2) vz
[0, 1] and obtain new condition
So PaPy P (i=aa()) PV Pris=1(2) de 1. Consider the last step of Equation (7). According to the Mauchy-Schwarn inequality, we have
Po
PoPl (Pr)s=(2)) - (z)
() < ! PoPris=0 (z) + +PPPy dz
PoP
Pa- dz L'' (Pris=ult) Pr|s= (2)
dz
PoPrls=u(=) + Pi p/ (2)
7
(Pris=o(t) - Sy|s=11?) (z) dz
V SV.
Consequently, we obtain variant of Theorem as follows.
Theorem A 1. I(Y,S) ,S) is upper bounded by TV(YY,)) 1f if
(P )²
PoP
2
dz
1 holds.
According to Theorem A 1, we find a looser upper bound for _(Y, S) (still dependent on TV(Ý, (V(Y)))) based on weaker condition. addition, Theorem is able support our total variation loss as well, since we still have I(Y, S) approaches 0 when TV SS) approaches 0 after training. Similar as the assumption [=) - p (=)] < 1, we conduct numerical experiments with kernel density estimation for estimating Pris=o (z) and (=))=(() and numerical integral for computing
dz. We obtain the results the integral as 0.8621 + 0.1110 for Facebook, 0.4568 0.0666 for Pokec_z, and 0.5934 0.0763 for Credit (mean value and standard deviation under 5 random seeds). Experimental results verify the feasibility of the condition Theorem
the value of So' (1) (=]
P.P.
2
A.2 PROOF OF THROREM
Theorem 2. The optimal poisoned adjacency matrix A f++1 in the + 1-th iteration given by PGD, i.e. the solution of A [+1 ((a) A' (A' + ( is
( A' (A + ELE: VVACIA) VAL(A'), otherwise,
A' " V (A')
A
(9)
A
where = sign (VAC(A)VVAC((A"))
Proof. First, we know that A' A' is a feasible solution because L(A') L(A') 0 ex- Hence we assume that A' is close to A'. Consequently, we use the first-order Taylor expansion to substitute the constraint [[(A') L(A') I as (V((A')(AA' A') S <t. For simplicity, vectorize the adjacency matrices A' and A' here such that A', A' E R
Next, we let A' A' WV,, and convert the optimization problem as follows.
argmin A (
(10)
Then discuss the new constraint in Equation (10) IV VE different conditions.
(1). When 1n VZ ct, easily obtain the optimal solution 0.
17

---

Published as a conference paper at ICLR 2024
(2). When VVCAA) c,, then we have
- -- (V-VVEIA)VVLA(A" VC(AA) -
Because V [V](A')]2 |
cos 0, where 0 is the angle of VL(A)) and &. To
minimize [E we minimize cos as cos = -1, i.e., & = -|E VL(A9)/IVV((A and then have
El + (V
I |EI12 S 4 (LCI
(V((A') 2
Therefore, the solution of Equation (10) is
(C VC(AY) IVC(A
(3). When /VC(A)) ctD also have - VVVVCA))VVV
Different from condition (2), the left-hand side and right-hand side here are both positive. Similarly, we cos and obtain the solution of Equation (10) as
{ Et V VL (A*) VL(AA). VC((A))
Combine the aforementioned three conditions into A' A (V) &, then have the solution as follows
A + (AC)(A if / V
A ++|
A' V'C ELEr - VACIIA) V PAA(A)) otherwise,
[AA(()))
where é, = sign (VACIA))
B ATTACK SETTINGS
In this section, we introduce our attack settings in detail from three perspectives, the attacker's goal, the attacker's knowledge, and the attacker's capability.
Attacker's Goal. There are two different settings of our problem, the fairness evasion attack, and the fairness poisoning attack. In the fairness evasion attack, the attacker's goal is let the victim model make unfair predictions on test nodes, where the victim model is trained with fairness consideration on clean graph. Note that is possible for real-world attackers to attack access control of the databases to modify the input graph data, especially for edge computing systems with a suuse-grained access control (Ali et al., 2016; Xiao et al., 2019). In addition, once the model is deployed, the attacker launch evasion attacks at any time, which increases the difficulty and cost of defending against evasion attacks (Zhang et al., 2022). Considering the severe impact of evasion attacks, many prevalent existing works Dai et al. (2018); Zügner et al. (2018); Zügner & Günnemann (2019); Zhang et al. (2022) make great efforts to study evasion attacks. In the fairness poisoning attack, the attacker's goal is let the victim model make unfair predictions on test nodes, where the victim model is trained with faimess consideration on the poisoned graph. For both settings, we use commonly used fairness metrics, e.g., demographic parity (Dwork et al., 2012) and equal opportunity (Hardt et al., 2016) to measure the fairness of predictions.
Attacker's Knowledge. To make our attack practical in the real world, we set several limitations on the attacker's knowledge and formulate the attack within gray-box setting. It is worth noting that our attacker's 's knowledge basically follows previous attacks on prediction utility GNNs (Wu et al., 2019; Xu et al., 2019; Zügner& & Günnemann, 2019; Chang al., 2020a; Ma et al., 2020; Li et al., 2022a; Ma et al., 2022; Lin et al., 2022). Specifically, the attacker is able to observe the node attributes X, graph structure A, ground truth labels V, and sensitive attribute value set S. but cannot
18

---

Published as a conference paper at ICLR 2024
observe the victim GNN model fe. Therefore, the attackers need to exploit surrogate model go to achieve their goal.
It is worth noting that method can be directly adapted to white-box setting by replacing the trained surrogate model in the attacker's objective with the true victim model in Problem 1. In con- trast, designing fairesss attacks in black-hox attack setting can be extremely challenging. The difference between gray-box attacks and black-box attacks is black-box attackers are not allowed to access the ground truth labels. Different from node embeddings which can be obtained in an unsu- pervised way, group faimess metrics have to rely on the ground truth labels, which makes existing black-bor attacks on graphs difficult adapt fairness attacks. Despite the difficulty of black-box fairmess attacks, we provide an initial step toward potential way to extend our framework to black-box setting. First, the attacker can collect some data following similar distribution, i.e., the original graph is Citeseer citation network, the attacker can collect data from Arxiv; if the orig- inal graph a Facebook social network, the attacker can collect data from Twitter (X). During the data collection (preprocessing), the dimension of collected node features should be aligned with the original graph. Then, the attacker can train a Mate-of-theear inductive GNN model on the collected graph data and obtain the predicted labels on the original graph. Finally, the attacker can use the predicted labels as a pseudo label to implement our G-FairAttack on the original graph.
Attacker's Capability. Between attacking the graph structure and the node attributes, we only consider the structure attack the structure perturbation in the discrete domain is more challenging to solve and the structure attack can be easily adapted to obtain the attribute attack. Hence, we consider that attackers can only modify the graph structure A, i.e., adding new edges or cutting existing edges, consistent with many previous attacks on prediction utility of GNNs (Dai et al., 2018; Xu et al., 2019; Zügner& & Günnemann, 2019; Wang & Gong, 2019; Bojehevski 2019; Chang et al., 2020a). In addition, the structure perturbation should be unnoticeable. Existing attacks of GNNs (Zügner et al., 2018; Zügner Günnemann, 2019; Dai et al., 2018; Bojehevski & Günnemann, 2019) proposed the following unnoticeable constraints: A edges are changed at most; there are no singleton nodes, i.e., nodes without neighbors after the attack; the degree distributions before and after the attack should be the same with high confidence. We follow these works to ensure the unnoticeability of our attack. More importantly, we propose an extra unnoticeable constraint to ensure the difference of the utility losses before and after the attack is less than This unnoticeable utility constraint makes attacks on faireess difficult to recognize.
Günnemann,
After clarifying detailed attack settings, use Figure I to illustrate toy example of our proposed attack problem. In Figure 1, We use squares to denote the sensitive group 0 and triangles to denote the sensitive group 1. We use blue to label class-O nodes and orange to label class- 1 nodes. We compute the demographic parity and the equal opportunity metrics (larger value means less fair) evaluate the fairness of the model prediction. By modifying two edges (from left to right), the attacker can let the fairness-aware GNN make unfair predictions while preserving the accuracy.
C FAST COMPUTATION
C.1 FAST COMPUTATION SKETCH
The goal of fast computation is to solve the problem v") &- arg (u.) 7 (u, v) efficiently.
According to the definition of 7* ('(,,) v), the computation of (u, v) depends on two loss functions: the attacker's objective Ly and the utility loss L. Between them, Ly can be formulated as
Σ kzTlzo (go- (A, (A,X) iEVin
C (go V, Vies. S) =
(11)
where k; - 1/ n Miell if E Vo and k; = - / D n Vieua if E V1. T2o(-) denotes an indicator function where [20 = 1 if x 2 0 and I I2o(x) 0 otherwise. The other L can be formulated as
L(go-, A, X, Virain)
1
Σ
ye log (a (A, x)))
Virsial
E Visin
(12)
+ log (1 (go- (A, (A,))()))
19

---

Published as a conference paper at ICLR 2024
Algorithm 1 G-FairAttack: A Sequential Attack Fairness of GNNs.
Input: Clean adjacency matrix A, attribute matrix X, attack budget A, utility budget Output: The solution of Problem 1: A
t 0, C + &, A < A
2: 0 < arg ming L. (go. A. A.X.Y.S)
3: while & & A and [(gor, A - [ A S e do
4:
(u', v²) t arg (u,)) (u, v), according to Algorithm 2.
5: A++1_ - flip
6: @ s0'
Evasion Poisoning
lag ming L. (go, Attl, ,x,,,,))
7:
CH+ - C*vllu,, wt), (v',
8:
1+1+1
9: end while
A
where a-) denotes the sigmoid function. In the 1-th iteration of our sequential attack, to com- pute the score function ((,, v) efficiently, should reduce the complexity of computing both AC* (u, v) and AC; (u, v). Specifically, our solution is to compute flip(u..) Zt incrementally and obtain 90 (flip(u, A X) flipp Z Then we can compute y v) and AL v) ac- cording to Equation (1I) and Equation (12). We first review the computation of flip(u,o) Z when new edge (u, u) is added.
Case 1: If {u, U), we can compute flip(u..) [..a) as
d'
A
A
X + [
ba x
[lip(n.))
di +1 (Z
R4
(13)
(di + 1)2
(dl + 1)(d
+1)
where j = == if u and j = u otherwise;
Case 2: if N UN Mu can compute flip(u, [/..1]
1 X P (dj(d 1)
A
X
X [in.]] 1.dl -IbiEN
A A X
A X X
flip(u.e) 4/a - LiEN
di
(d + 1)
(14)
where LEE = lifi N, and LeN = 0 otherwise;
Case 3: If & NC U we have flip(u,.) [u, [
Next, we introduce the computation of flip(...) Z' when an existing edge (u, v) removed. Simi- larly, divide the computation into three cases follows.
Case 1: i {u, v). we can compute flip( Z as
d'
X
X
1 1--ppp X
flip(u, Zia =
b.
(15)
d
R..)
d.dd
d'
di
(d:)- - 1)2
[i)
where j j= v-v viiii and = otherwise;
Case 2: if Ng. U.N (u,
compute flip(a,)) Zio.j]
A [id X [i,d]
A (u.
X Aloo) x --X
X|u.1]
flip(u.)) B/g Zi. LENs
--IIEN
d [u]
(dit 1)
df
(d 1)
(16)
where TiEN = lif OffiEN N, and liEN = 0 otherwise;
Case 3: if Ng Ng, we have flip Z.. Z
The overall fast computation algorithm is shown in Algorithm 2, where argmax p² (u, , v) is denoted the of (u, v) corresponding to the top-a elements of p²(u, (u, v).
20

---

Published as a conference paper at ICLR 2024
Algorithm The fast computation algorithm of (u', u²)..
Input:
Adjacency matrix A', attribute matrix X, output matrix Zz, degree vector d', product ma- trix A'X, model parameter 0
Output: Target edge (w', o²) in Algorithm 1.
1: C + argmax aal'(n v).
(a.0)EE*
2: k 0, t 0, q" 0.
3: for (u, E C do
4:
flip(u,)) Z' +- Z' for P P U do
5:
6:
if i f u) then
7:
Update flip(u..) Qua
according to Equation (13) or Equation (15),
8:
else Update flip(u..) (aa) according to Equation (14) or Equation (16).
9:
10:
end
11:
end for
12:
go (flip(..o) A X) + flip( Z' Z'''
13:
Compute ((flip(u.)) A' X) and f (flip((a,)) A', X) according to Equation (11) and Equa-
tion
(12).
14:
PiM - [(flip(u.r) A X) - C(A",X,
15:
qin < Ly(flip(u.)) A', A (X),
kt k+1
17: end for
(x')² of
18: Ff + g¹
l p²
19: kmax f arg ma..
20: (u', v²) ((mma))
C.2 COMPLEXITY ANALYSIS
Based on Algorithm provide detailed complexity analysis for our proposed G-FairAttack.
Proposition 2. The overall time complexity of G-FairAttack with the fast computation is O(dn² + dzan), where d denotes the average degree.
Proof. First, to compute Ct compute Z' Z' and find the maximum M, in (dd.)). Then compute (' v) = EVENgUNT M, | for (u, v) E E Odn?), and find the top-a elements as (t in O log a). Then, the computation of p' and g' can be divided into the following steps for each edge (u, v) C..
1. The computation of flip( Z [..) for E E U.: We can store and update A'x, d', and Z for each iteration. Hence, the computation of Equation (13), Equation (14), Equation (15), and Equation (16) only requires O(1). Consequently, the total time complexity of this step O(d).
The computation of gø (flip(u.)) A',X) flip( Z requires O(nd,)-
According to Equation (11) and Equation (12), the computation of the loss functions requires O(n).
L(flip A and (f A X) based go (flip
Considering all edges from Ct, the computation of p' and g' requires Old,am). Finally, we can compute f and find (w', v²) in O(a). Combining these steps, the complexity of Algorithm is O(dn² + d.an) in total.
With our fast computation method, the total time complexity of G-FairAttack is O( ad) Here, the retraining of the surrogate model *++1 arg ming L, (go. A ++I X,Y,S) in the fairness poisoning attack neglected because the convergence is not controllable. The overall G-FairAttacl
21

---

Published as a conference paper at ICLR 2024
algorithm is shown in Algorithm 1. We can obtain the space complexity of G-FairAttack as O((E) + dz
Next, we show that our complexity can be further reduced in practice. We list two potential ways as follows.
1. The first approach is to implement our fast computation algorithm in parallel. As the proof of Proposition 2 shows, the main part of G-FairAttack's complexity is the computation of (u, v) for (u, v) E E. which has Oddn²) complexity. It is distinct that this computation can be imple- mented in parallel where Eº is partitioned into p subsets, and each subset is fed into one process. By exploiting parallel computation, the overall complexity can be reduced to (dd2/pp)
Instead of ranking all of the edges in E by p' r)), we can just randomly sample a edges from Ex as C². By using random sampling instead of ranking, the overall complexity can be reduced to a(d However, the error of the fast computation might increase without a careful choice of the sampling distribution.
Note that most existing adversarial attack approaches (Zügner et al., 2018: Züggerr& & Günnemann, 2019; Bojchevski & Günnemann, 2019; Lin et al., 2022) do not have a lower complexity (less than O(n²)) than our proposed G-FairAttack. The adversarial attacks with an O(n²) complexity can already fit most commonly used graph datasets. In general, our method is practical for most graph datasets as the existing literature. For extremely large datasets, we can also use the aforementioned strategies to reduce further the time complexity.
Finally, we would like to make more detailed comparison of the time complexity with adopted attacking baselines. The random sampling- -ased basclines, i.c., random and FA-GNN, definitely have lower time complexity (O()), Á is the attack budget) because they are based on random sampling. Although their complexity is Iow, the effectiveness of random sampling-based attacks is very limited. For the rest muddient-based attack baselines, i.e., Gradient Ascent and Metattack, their time complexities O(n²) (Zügner& & Günnemann, 2019), the same G-FairAttack. However, gradient-based methods have larger space complexity compared with G-FairAttack (O(n²) vs. Od (&l)).
D G-FAIRATTACK VS GRADIENT-BASED METHODS
The fairness attack of GNNs is discrete optimization problem, which is highly challenging to solve. Most of the existing adversarial attacks that focus on the prediction utility of GNNs adopt gradient-based meth- ods (Zügner & Günnemann, 2019; Wu et al., 2019; Xu et al., 2019; Geisler et al., 2021) find the maximum of the attacker's 's objective. As structure attacks flip the edges sequentially. In the f-th it- eration (1 - 1, 1,2, the gradient-based optimization al- gorithm finds a target edge (u', w²) based on the gradient of the adjacency matrix V V where L is the objective function of the attacker, and flips this target edge to ob- tain the update adjacency matrix A ++1, which is expected to increase the attacker's objective. In particular, to obtain V VA.C, gradient-basee methods extend the discrete adja- cency matrix A' E {0, | to a continuous domain Raxx and compute V R= Specifically, for poi- soning attacks where the problem becomes a bilevel opti- mization, existing methods exploit the meta-learning (Zügner & Günnemann, 2019) or the convex relaxation (Xu et al., 2019) techniques to remove the inner optimization. After obtaining A C, the gradient-based methods should update A' in the discrete domain instcad of using gradient ascent directly. Specifically, gradient- based methods choose the target edge corresponding the largest element or use random sampling to find a target element A [u,e]*
Discrete Updattes
X2
gr
(0.0) (1,0)
f=1
gradient-basee based
0
P00
0
X1
1
1
7.0
Figure 4: The limitation of the gradient- based optimization method. The blue ellipses are isolines of the loss function.
Although existing attacks of GNNs based on gradient- methods successfully decrease the pre- diction utility of victim models, they have two main limitations.
22

---

Published as a conference paper at ICLR 2024
The first limitation is that cannot ensure the loss function after flipping the target edge will increase because the update in the discrete domain brings an uncontrollable error. The intuition of the gradient-based method is that we cannot update the adjaceney matrix with gradient ascent because the adjacency matrix is binary and only one edge can be flipped in each time. Hence, we expect that flipping the target edge corresponding the largest gradient component can lead the largest increment of the attacker's ' objective L(A, X). However, this expectation can be false since the update of the adjacency matrix (flipping one target edge) has a fixed length. Next, we prove Proposition 1.
Gradient-bart based methods for optimizing the graph structure are not guaranteed to decrease the objective function.
Proposition
Proof. Consider the loss function C(A, X) near a specific point Ao where A E RR² is vectorized adjacency matrix. Based on Taylor's Theorem, we have
X)A.X) [(Ao, X) + VAC(Ao. () Ao) RA),),
where R3 (A) h1 (A)IIA Aoll the Peano remainder and we have limA-AA, h1 For gradient-based methods, we have A An + ex where e₁ is the basis vector at the k-th dimension. Then, we have
X) = [(Ao, X) VAL(Ao, X)ІI + (A1).
Here, we know that VAC(Ao, X) the largest positive element of V VAC(Au, X), which is a fixed value. Then, we expect that choosing A can lead to the fact that L(A X) > L(A., X), i.e., VAL( Ao.
[k] + h1 (A1) > However, this inequality is not true without further assumptions
when A Aollo = Ao
In comparison, we also show that the error can be controlled in the continuous domain by a careful selection of the learning rate. In the continuous domain, the situation is different because we can make the value of ||A - Aall arbitrarily small by tuning the learning rate 1) where A Ag +
V C(A. [k]ee Note that we have lim Ao h1 (A) 0 and the value of V L(A.. X)(k] is
fixed. Hence we can choose proper 7) which makes || - -All small enough to ensure (A1) <
V VAC(Ao, [k). Finally, we have V C(Ao X) [k] + h1 (A1) > 0 and L(A,,X) > L(Ao, X) consequently. We also provide a two-dimensional case in Figure 4. In the iteration, the optimization starts at (0, 0). The gradient at (0, is [1 0] According
the gradient- based methods, the next
point should be at (1, However, the loss after updating does not increase S(1,0) = 5(0, 0).
Instead, (0, 1) is a better update for [(0, 1) f(0 0) in this iteration.
The second limitation is the large space complexity. The computation of A L requires storing a dense adjacency matrix with O(n²) space complexity, which is costly at a large scale.
In contrast, our proposed G-Fair successfully addresses these limitations. First, G-FairAttack can ensure the increase of the attacker's objective after flipping the target edge since G-FairAttack exploits a ranking-basee
method to choose the target edge in each iteration. In particular, we fl) A') (ger,, which en-
choose the target edge as max(u. r'(u, 1) sures that flipping the target edge can maximize the increment of attacker's 's objective. Second, unlike gradient-based methods, G-FairAttack does not require storing a dense adjacency matrix as no gradient computations are involved. Referring to the discussion in Appendix C.2, the space complexity of G-FairAttack is [((E) + dyn.). much lower than gradient-based methods (O(n²)) Moreover, we conduct experiment to demonstrate the superiority of G-FairAttack compared with gradient-basee based optimization methods. Specifically, we compare the effectiveness of G- FtiirAttack with two gradient-based optimization methods in both faimess evasion attack and faimess poi- soning attack settings. If an optimization algorithm leads to a larger increase in the attacker's objective, it is more effective. For the fairess evasion attack, we choose Gradient Ascent as the baseline method. Given the attack budget A = 0.5%|E), we record the value of the at- tacker objective Cy (ge-, A²), i.e., demographic parity based on a surrogate model in the t-th it- eration, for = 0....,A. A. The result is shown in Figure 5(a). We observe that the attacker objective keeps increasing during our non-gradient optimization (adopted by G-FairAttack) pro- cess and reaches an optimum rapidly, while the gradient-based optimization method (adopted by Gradient Ascent) cannot ensure the increment of the attacker objective during the optimization.
23

---

Published as a conference paper at ICLR 2024
Table 3: Dataset statistics.
Dataset
#Nodes
#Edges
#Attributes
#Train/%
#Validation/$/
#Test/%
Sensitive
Facebook
1,045
53,498
574
50%
20%
30%
Gender
Pokec
7,659
41,100
277
13%
25%
25%
Region
Credit 30,000
200,526
13
20%
20%
30%
Age
For the fairness poisoning attack, we choose Metattack as the base- line method. During the optimiza- tion process, the surrogate model go. is retrained in each iteration. The convergence of the surrogate model during the retraining is not control- lable. To make fair compari- son, should ensure both optimiza- tion methods compute the attacker objective based on the same surro- gate model. Hence we fix A' and Ge- for both methods and record the increment of the attacker objective (gor, A Ly A') ) the t-th iteration, for O,..., A, where A (+1 is obtained based on different optimization methods. In conclusion, we compare the increment of the attacker's objec- tive caused by a single optimization step of different optimization methods in this case. The result shown in Figure 5(b). For G-FairAttack, the attacker's objective increases in 28 iterations, i.c., pos- itive Adp variation, and decreases in iteration. For Metattack, the attacker objective increases in only 5 iterations and decreases in iterations well. Therefore, single step of G-FairAttack leads to a larger increase the attacker's objective than Metattack given the same initial point A'. In con- clusion, proposed FairAttack leads to better solution in the optimization process compared with gradient-base methods in both fairness evasion attacks and fairness poisoning attacks.
G-FairAltack
Adp %
10
Aap Increment
Metattack
G-FairAtaak Gradient Ascent
50
100
50
100
Iterations
Iterations
(a) Fairness evasion attack.
(b) Fairness poisoning attack.
Figure The variation of attacker's 's objective during the optimization process Facebook, comparing non non-gradient methods (G-FairAttack) with gradient-based methods (Gra- dient Ascent, Metattack).
E IMPLEMENTATION DETAILS
E DATASETS
The statistics of these datasets are shown Table 3. the Facebook graph (Leskovec & Mcauley, 2012), the nodes represent user accounts of Facebook, and the edges represent the friendship lations between users. Node attributes are collected from user profiles. The sensitive attributes of user nodes are their genders. The task of Facebook is to predict the education type of the users. In the Credit defaulter graph (Dai & Wang, 2021), the nodes represent credit card users, and the edges represent whether users similar not according
their spending and payment patterns. The sensitive attributes of user nodes are their ages. The task of Credit is to predict whether user will default the credit card payment not. In the Pokec graph (Agarwal et al., 2021), the nodes represent user accounts of a prevalent social network in Slovakia, and the edges represent the friend- ship relations between users. The sensitive attributes of user nodes are their regions. The task of Pokec is to predict the working fields of the users. It is worth noting that we use subgraph of Pokec in (Dong et al., 2022a) instead of the original version in (Dai Wang, 2021). In our experiment implementation, we adopt the PyGDebias library (Dong et al., 2023a) to load these datasets.
E.2 BASELINES
We first introduce the detailed settings of the attack baselines in the first stage of evaluation.
Random (Zügner et al., 2018; Hussain et al., 2022): Given the attack budget A, we randomly flip A edges (removing existing edges adding new edges) and obtain the attacked graph. It is random method that fits both the fairness evasion attack setting and the faimness poisoning attack setting.
24

---

Given the attack budget A, we flip A edges sequentially in A iterations. In each iteration, we compute the gradient V V A') and flip one edge corresponding to the largest element of the gradient, where 0 = arg ming L. (ge, A). To make C, differentiable, we use the soft predictions to substitute the prediction labels f as (Zeng et al., 2021). Here, we choose a two-layer graph convolutional network (Kipf & Welling, 2017) as the surrogate model go. and method that Published as a conference paper at ICLR 2024
FA-GNN (Hussain al., 2022): Given the attack budget A, randomly link A pairs of nodes that belong to different classes and different sensitive groups. Specifically, we choose the most effective link strategy, "DD", in our experiments. It is also random method that fits both attack settings.
Gradient Ascent:
CE loss as the surrogate loss function L.. Gradient Ascent an optimization- only fits the fairness evasion attack setting.
Metattack (Zügner & Günnemann, 2019): Given the attack budget A, we sequentially flip A edges in A iterations. In each iteration, we compute the meta gradient F (A'). A') by MAML (Finn et al., 2017) and flip one edge corresponding to the largest element of the meta gradient, where 0 = arg ming [g0 A'). To make L differentiable, we implement the same adaption of Ly Gradient Ascent. Here, we also choose two-layer GCN as the surrogate model ge and CE loss as the surrogate loss function L.. Metattack is also an optimization- method, while it only fits the fairesss poisoning attack.
It is worth noting that for both Gradient Ascent and Metattack, should flip the sign of the gradient components for connected node pairs as this yields the gradient for a change in the negative direction (i.e., removing the edge) (Zügner & Günnemann, 2019). Hence, we flip the edge corresponding to the largest score V (u..) fy (-2 A [u..]] + 1) for (u, v) E & for Gradient Ascent and Metattack.
Next, we introduce our adopted test GNNs in the second stage. We choose four types of GNNs, including a vanilla GNN and three types of fairness-aware GNNs.
Vanilla: We choose a two-layer GCN (Kipf& & Welling, 2017), which is a mostly adopted GNN model in existing works.
Adp: We choose the output-based regularization method (Navarin al., 2020: Zeng et al., 2021; Wang et al., 2022a; Dong et al., 2023c). Specifically, we choose a two-layer GCN as the backbone and add a regularization term Adp to the loss function. Moreover, to make the regularization term differentiable, we use the soft prediction to substitute the prediction label in Adp as (Zeng et al., 2021).
S): For mutual information loss, except for directly decreasing the mutual information, the adversarial training (Bose& Hamilton, 2019; Dai & Wang, 2021) could also be seen as a specific case of exploiting the mutual information loss according to (Kang et al., 2022). In an adversarial training framework, an adversary is trained to predict S based on Y. If the prediction is more accurate, it demonstrates that the output Ý of the GNN contains more information about the sensitive attribute S, i.e., the GNN model is less fair. We choose FairGNN (Dai & Wang, 2021) the baseline in the mutual information type. FairGNN contains discriminator to predict the sensitive attribute based on the output of a GNN backbone. The GNN backbone is trained to fool the discriminator for predicting the sensitive attribute. Specifically, we choose single-layer GCN as the GNN backbone.
W S): We choose EDITS (Dong et al., 2022a), a model agnostic debiasing framework for GNNs. EDITS finds a debiased adjacency matrix and a debiased node attribute matrix by min- imizing the Wasserstein distance of the distributions of node embeddings on different sensitive groups. With the debiased input graph data, the faimess of the GNN backbone is improved. Specifically, we choose a two-layer GCN as the GNN backbone.
E.3 EXPERIMENTAL SETTINGS
The implementation of our experiments could be divided into two parts, faireess attack methods, and the test GNN models. For attack methods, we use the source code of FA-GNN (Hussain et al., 2022) and Metattack (Zügner& & Günnemann, 2019). Other attack methods including G-FairAttack are implemented in PyTorch (Paszke et al., 2019). For test GNN models, we use the source code of GCN (Kipf & Welling, 2017), FairGNN (Dai & Wang, 2021), and EDITS (Dong et al., 2022a).
25

---

Published as a conference paper at ICLR 2024
Table 4: The hyperparameter settings of four different types of test GNNs three benchmarks in fairness evasion attack and fairness poisoning attack settings. The detailed definition and description of parameters a, B, p1, p2, p3, p4, and refers (Dai & Wang, 2021; Dong al., 2022a).
Fairness Evasion Attack
Fairness Poisoning Attack
Test GNN
Hyperparameter
Facebook Pokec
Credit
Facebook
Pokec
Credit
learning rate
le
le
le ?
le
le
le
weight decay dropout
le-s
le-2
le-s
le-s
le-5
le-5
GCN
0.5
0.2
0.5
0.5
0.5
0.5
epochs
2,000
1,000
1,000
1,000
500
200
learning rate
le
le-3
5e
le-1
le-3
5e
weight decay
1e-5
le-b
le-5
1e-5
le-b
le le-5
Reg
dropout
0.5
0.2
0.2
0.5
0.5
0.5
epochs
2,000
10,000
2,000
1,000
1,000
500
fairness loss weight
150
1
80
learning rate weight decay
le
5e-3
le
1e-1
5e-3
le-3
1e-5
le-5
1e-5
1e-5
le-5
1e-5
dropout
0.5
0.5
0.2
0.5
0.5
0.5
FairGNN
epochs covariance constraint weight a
2,000
5,000
1,000
1,500
5,000
1,000
2
100
30
adversarial debiasing weight B
10
500
10
3
1,000
learning rate weight decay
le
le-1
5e
le-3
le-1
le
1e-5
le-5
1e-5
1e-5
le-5
1e
dropout
5e 52-
5e-2
5e
56 56-2
5e-2
5e
epochs
1,000
500
500
2,000
1,000
200
EDITS
H1
le
3e-
5e
le
3e-2
5e
μ2
0.8
70
0.1
0.8
70
0.1
μ43
0.1
0.1
1
μ4
20
15
15
20
15
15
edge binarization threshold
le
0.3
5e
le
0.2
2e
We exploit Adam optimizer (Kingma & Ba, 2015) to optimize the surrogate model, gradient-based attacks, and the test GNNs. All experiments are implemented on an Nvidia RTX A6000 GPU. We provide the hyperparameter settings of G-FairAttack Table and the hyperparameter settings of test GNNs in Table 4.
E.4 REQUIRED PACKAGES
We list some key packages in Python required for implementing G-FairAttack as follows.
Python == 3.9.13
torch 1.11.0
torch-geometric 2.0.4
numpy = 1.21.5
numba 0.56.3
networkx = 2.8.4
scikit-learn 1.1.1
scipy = 1.9.1
dgl = 0.9.1
deeprobust 0.2.5
'The open-source code is available httppe://ggtibb..cm///eennghhii FG
26

---

Published as a conference paper at ICLR 2024
F SUPPLEMENTARY EXPERIMENTS
F.1 ERFECTIVENESS OF ATTACK
In Section 4.2, we discussed the ef- fectiveness of G-FairAttack in attack- ing the fairess of different types of GNNs, Here, we provide more re- sults of the same experiment as Sec- tion 4.2 but in different attack set- tings and more faimess metries. Ta- ble 6 shows the experimental results of fairnsss evasion attacks in A fairness metric, Table shows the ex- perimental results of fairness poison- ing attacks in Adp faimess metric, and Table 8 shows the experimental results of fairness poisoning attacks in A.e fairness metric. From the re- sults, we can find that the overall performance of G-FairAttack is better than any other baselines, addition, we can find that G-FairAttack
Table 5: The hyperparameter settings of G-FairAttack on three benchmarks. The "(s)" denotes that the correspond- ing hyperparameter is related to the training of the surrogate model.
Hyperparameterr attack budget A utility budget threshold a
Facebook
Pokec
Credit
5%
5%
1%
5%
5%
5%
0.1
5e
1e
learning rate (s)
1e-3
1e-3
5e-
weight decay (s)
le
1e-5
1e-5
epochs (8)
2,000
2,000
1,000
dropout (s)
0.5
0.5
0.5
faireess loss weight a (s)
1
1
bandwidth h (s)
0.1
0.1
0.1
number of intervals m (S)
10,000
10,000
1,000
which highlights the clear superiority of G-FairAttack. seems less desirable in the cases where vanilla GCN serves the victim model. The reason for this phenomenon is our surrogate loss contains two parts, utility loss term L and fairness loss term Ly, while the real victim loss of vanilla GCN only contains the utilityy loss term L. However, in the general case (without knowing the type of the victim model), G-FairAttack can outperform all other baselines when the surrogate loss differs from the victim loss (when attacking fairness-aware GNNs). Despite that, the shortage in attacking vanilla GNNs can be solved easily by choosing a smaller hyperparameter a (the weight of Ly). As Table 5 shows, we fix the hyperparameter setting (also fix a) for all attack methods when attacking different types of victim models because the at- tacker cannot choose different hyperparameters based on the specific type of the victim model in the gray-box attack setting. By fixing the hyperparameter settings for different victim models, the experimental results demonstrate that our G-FairAttack victim model-agnostic and easy use (in terms of hyperparameter tuning). In addition, we can also find that the fairness poisoning attack a more challenging task (easier to fail), while effective fairness poisoning attack methods induce more serious deterioration in the fairness of the victim model. Furthermore, obtain that edge rewiring based methods (EDITS) can effectively defend against some fairesss attacks (more details about this conclusion discussed in Appendix G).
F.2 EFFECTIVENESS OF SURROGATE LOSS
In Section 4.3, we discussed the effectiveness of our proposed surrogate loss in representing dif- ferent types of fairness loss in different victim models. Here, we provide more results of the same experiment as Section 4.3 but in different attack settings and datasets. Table 9 shows the experimental results of fairness evasion attacks on the Facebook dataset. As mentioned in Sec- tion 4.3, the surrogate loss function in the attack method and the victim loss function in the victim model are different in our attack setting. The attacker does not know the form of the victim loss function due to the gray-box setting. If the surrogate loss is the same the vic- tim loss, the attack method naturally can have a desirable performance (as white-box attacks). However, this experiment, we demonstrate that G-FairAttack (with our proposed surrogate loss) has the most desirable performance when at- tacking different victim models with different victim loss from the sur- rogate loss. Consequently, our exper- iment verifies that surrogate loss function is adaptable to attacking dif- ferent types of victim models.
Table 9: Results of G-FairAttack on Facebook while replac- ing the total variation loss with other loss terms.
N
EDITS
Attack
Aap (%) Aeo (%)
A (%) Aco (%)
Clean
6.23 1 0.69 4.78 + 0.98
1.15 + 0.25
2.31 + 0.58
G-FA-None
6.35 0.83 4.78 + 0.98
4.19
0.29
2.88
+ 0.33
G-FA-Aup
6,35 4 0.83 4.78 + 0.98
3.86
+ 0.29
2.88
+ 0.33
G-FA
8.62 + 0.91
5.70 0.64
4.19 + 0.29
2.88 + 0.33
27

---

Published as a conference paper at ICLR 2024
Table 6: Experiment results of fairesss evasion attack, where AUC and Deo are adopted as the prediction utility metric and the fairness metric, correspondingly.
Facehook
Pokec
Credit
Victim
Attack
AUC(%)
AUC(%)
A00 (%)
AUC(%)
A.a(%)
Clean
64.53 = 0.05
0.52
0.41
72.87 1. 1.200
8.75 0.94
70.48 0.14
12.29
2.14
Random
65.05 = 0.10 1.55
= 0.00
72.56
0.20
8.71 + 2.50
70.53
0.13
12.57
2.29
GCN
FA-GNN
63.00 0.06
2.12
0.58
72.12
1.31
L0s
70.44
0.12
14.39
+ 2.65
Gradient Ascent
64.77 = 0.11
1.93
= 0.33
72.88
# 0.18
5,93 + 1.74
G-FairAttack
64.20 0.03
2.38
- 0.68
72.91 0.20
6.69
1.63
70.44 0.11
12.75
2.12
Clean
64.09 = 0.16
0.00
71.08
1: 0.35
1.73
1.15
70.26
0.34
0.66
0.84
Random
64.49 0.26
0.77 = 0.33
70.86 + 0.30
1.34 + 1.12
70.31 + 0,34
0.82 + 0.98
Reg
FA-GNN
62.28 = 0.23
0.90
0.78
70.12 0.25
5.23 0.38
70.34
0.36
0.32 0.27
Gradient Ascent
64.40 = 0.12
0.20 + 0.00
71.21 + 0.49
2.25 1.19
G-FairAttack
63.30 0.14
1.74 0.33
71.11 0.26
7.14 + 1.26
70.21 + 0.37
2.08 1.20
Clean
65.24 = 0.49
0.97 = 0.77
69.71 0.09
0.81 + 0.09
67.32 + 0.46
0.94 +: 0.67
Random
64.88 0.52
0.44 = 0.29
69.36 0.20
0,48
0.40
67.32 + 0.44
0,92 + 0.69
FairGNN
FA-GNN
59.78 = 0.96
1.01 + 1.29
69.57 0.28
2.58 0.58
67.26 0.49
0.95 + 0.42
Gradient Ascent
65.19 = 0.47
1.01 + 1.29
69.21 0.16
1.25 + 0.43
G-FairAttack
64.34 0.45
1.79 + 1.30
69.83 0.14
2.30
0.49
67.30 0.47
1.12 + 1.04
Clean
70.95 = 0.28
0.38
= 0.00
70,89 + 0.44
5.15
+ 0.51
69.11 + 0.50
6,15 + 1.67
Random
68.13 0.20
0.97
0.68
70.89 1 0.44
5.15
0.51
69.04 0.06
6.93 + 2.13
EDITS
FA-GNN
70.72 = 0.27
0.38
0.00
70.89
+ 0:44
5.15
0.51
69.11 0.50
6.16 1.66
Gradient Ascent
68.36 0.24
0.57 +: 0.56
70.89
1 0.44
5.15 + 0.51
G-FairAttack
68.12 1.23
70.99
6.18
1.23
69.04 0.06
6.93 2.13
Table 7: Experiment results of fairness poisoning attack, where ACC and Adp are adopted as the prediction utility metric and the fairness metric, correspondingly.
Facebook
Pokec_7
Credit
Victim
Attack
ACC(%)
(%)(%)
ACC(%)
(%)
ACC(%)
(%)
Clean
80.25 1: 0.64
6.33 + 0.54
61.51 +:2 0.54
8.39
1.25
69.77 0.36
10.61 0.73
Random
80.15 + 1.02
4.17 1.58
60.98 + 0.29
7.76 0.93
69.71 0.55
10.96
1.35
GCN
FA-GNN
79.41 4: n.67
5.84 : 0.32
59.97 + 0.90
2.46
1.18
69.56 +: 0.81
18.58 +: 1.78
Metattack
79.30 1.15
33.33 + 5.97
60.14 +
44.90
0.10
G-FairAttack
78.55 1: 0.18
14.99 +: 2.08
61.81 +: 0.21
6.15
1.52
69.57 1.13
10.87
0.96
Clean
80.41 1: 0.18
4.63 :: 1.18
65.20 1: 1,26
1.55
0.82
68.22
0.73
1.48 1 0.28
Random
80.18 1: 0.30
1.41 1: 1,23
63.00 1: 1.50
2.01
1.98
68.62
0.48
1.58
0.64
Reg
FA- FA-GNN
79.38 0.31
1.42 = 0.89
64.02 0.47
0.81 0.76
69.29
0.63
0.79 0.41
Metattack
80.81 1.
9.45 0.96
62.89 1:
4.88
G-FairAttack
77.95 0.16
15.65 + 0.69
65.45 + 0.55
7.76 + 0.08
67.80 1.34
2.32 + 0.51
Clean
80.36 + 0.18
2.71 0.50
60.87 3.00
0.80 0.62
75.57
+ 0.65
4.78
Random
78.66 1. 0.00
0.18 1 0.31
54.21 5.10
1.79 0.93
75.42 1 0.57
1 1.71
FairGNN
FA-GNN
78.77 0.18
0.33 = 0,58
60.54
1.24 + 0.77
75.38 + 0.88
4.89 0.56
Metaltack
78,66 1. 0.84
3.86
55.16 6.70
6.08
3.64
G- A-FairAttack
77.92 + 0.18
10.64 + 0.97
59,36 + 1.19
3.91
3.07
75.47 0.56
5.85 + 1.66
Clean
79,62
1.36 1.54
62.33 0.84
3.32
0.64
67.73
7.23
0.33
Random
81.21 + 0.32
3.86 = 2.7
62,49 - 0.69
4.62
+ 0.97
69. 19 0.86
7.91 - 0.91
EDITS
FA-GNN
79.83 1: 0.18
3.04 = 0.50
63.38 0.18
2.47
1.38
67.55 0.89
7.30 :: 0.19
Metattack
81.95 +
62.72 + 0.19
2.83
0.80
G-FairAttack
81.95 1: 0.48
6.15 + 0.77
62.65 1 0.81
4.85 +: 0.44
69.01 +: 0.79
8.14 + 0.41
F.3 ATTACK PATTERNS
In this experiment, we compare the patterns of G-FairAttack with FA-GNN (Hussain et al., 2022). FA-GNN divides edges into four different groups, 'EE', 'ED', 'DE', and 'DD', where edges in EE link two nodes with the same label and the same sensitive attribute, edges in ED link two nodes with the same label and different sensitive attributes, edges in DE link two nodes with different labels and the same sensitive attribute, edges in DD link two nodes with different labels and different sensitive attributes In particular, record the proportion of poisoned edges in these four groups yielded by
28

---

Published as a conference paper at ICLR 2024
Table 8: Experiment results of fairness poisoning attack, where AUC and Aoo adopted as the prediction utility metric and the fairness metric, correspondingly.
Facebook
Pokec_z
Credit
Victim
Attack
AUC(%)
(%)
AUC(%)
(%)
AUC(%)
Aco(%)
Clean
64.53 1 0.05
1.16 1 0.78
67.53 1 0.25
10.16 1: 1.20
69.36 0.08
9.83 1: 0.76
Random
65,49 0.37
1.29 = 0.87
66,97 0.11
8.81
1.07
69.45 + 0.06
10.18 # 1.62
GCN
FA-GNN
64.45 1: 0.68
2.51
0.33
65.77 0.33
1.78 0.66
69.16
0.11
18.55
2.02
Metattack
65.02 0.17
24.84 + 6.37
64.33 + 0.33
43.71
+ 1.18
G-FairAttack
62.41 0.07
9.53 a 1,56
67.26 0.26
9.71
1.84
69.37
0.14
10.23
1.29
Clean
64.57 0.21
1.02 1: 0.91
68,93 1: 1.25
1.39
0.85
69.70
0.49
1.01 :: 1.40
Random
64,45 0.36
1.40 = 0.62
66.41 + 2.23
1.22
0.41
69.79 + 0.46
0.86 = 1.00
Reg
FA-GNN
61.67 0.53
0.29 = 0.58
66.65 + 0.66
3.05
2.29
69.67 0.76
1.42 + 0.79
Metattack
64.31 0.17
4.88 = 1.43
65.94 2.99
6.23 0.38
G-FairAttack
61,69 0.14
9.80 + 0.91
68.06 + 1.58
6.88 2.35
69.76 0.49
2.36 1.50
Clean
65,57 0.40
0.65 = 0.78
65.22 +: 2.04
0.94 0.83
65.95
0.46
3.04 = 1.35
Random
64.66 0.75
0.19 = 0.33
59,56 1.92
2,46 2.43
65.48 0.55
3.35 1.41
FairGNN
FA-GNN
63.54 0.14
0.00 0.00
64.73 2.79
2.13
65.13 0.60
3.19
Metattack
65.10 +: 0.42
3.60 = 4.13
57.99 + 8.86
7.13 + 3.07
G-FairAttack
62.99 + 0.29
4.70 + 1.44
65.79 + 2.64
2.78 1.51
65.89 0.53
3,83 = 1.64
Clean
79.00 2.49
0.19 = 0.33
67.00 + 0.59
3.19
0.84
69.83 0.13
6,81 = 0:49
Random
71.58 0.36
1.03 0.95
68.23 0.62
6.79
1.00
69.55 0.27
6.91 1.05
EDITS
FA-GNN
77.06 + 2.13
0.58 = 0.58
67.55 + 0.32
2.86 2.67
69.82 0.17
6.83 = 0.52
Metattack
71,60 +: 0.40
0.52 - 0.44
67.51
+: 0.56
3.15 1.23
G-FairAttack
70.33
1.61 + 0.59
68.26 + 6.98 0.29
69.62 0.20
7.29 0.53
Table 10: Attack patterns (statistics of poisoned edges in different groups) of G-FairAttack. Fairness Evasion Attack
Fairness Poisoning Attack
Dataset
EE/%
ED/%
DE/%
DD/%
EE/%
ED/%
DE/%
DD/%
Facebook
43.46
28.42
14.44
13.96
31.86
28.72
19.07
20.34
Pokec
25.51
23.47
26.39
24.63
26.58
24.73
22.01
26.68
Credit
74.89
7.37
16.06
1.68
38.63
22.59
24.78
13.99
G-FairAttack and FA-GNN. The results of attack patterns of G-FairAttack shown in Table 10. According to the study in (Hussain et al., 2022), injecting edges in DD and EE can increase the statistical parity difference. Based this guidance, FA-GNN randomly injects edges that belong to group DD to attack the faimess GNNs. Hence, the attack patterns of FA-GNN for all datasets and attack settings all the same, i.e., 100% for the DD group and 0% for the other groups However, our proposed G-FairAttack has different patterns of poisoned edges. For the Facebook and the Credit dataset, G-FairAttack poisons more EE edges than other groups. For the Pokec dataset, the proportion of poisoned edges in four groups is balanced. Although we cannot analyze the reason for the apparent difference in this paper, we can argue that G-FairAttack is much harder defend because it does not have a fixed pattern for all cases, unlike FA-GNN.
F.4 ATTACK GENERALIZATION
Although the generalization capability of adversarial attacks on GNNs with a linearized surrogate model has been verified by previous works (Zügner al., 2018: Zügner & Günnemann, 2019), we conduct numerical experiments to verify the generalization capability of G-FairAttack to other GNN architectures. In the experiments, G-FairAttack still trained with a two-layer linearized GCN the surrogate model, while we choose two different GNN architectures, GraphS (Hamilton et al., 2017) and GAT (Veličković et al., 2018), as the backbone of adopted victim models. Experimental results shown in Tables 11 to 14. From the results, we can observe that G-FairAttack still success- fully reduces the fairness of victim models with different GNN backbones, and AttaakAttack still has the most desirable performance verify the generality of G-FairAttack, we conduct experiments on the German Credit dataset (Agar- wal et al., 2021). In the German dataset, nodes represent customers of German bank, and edges
attacking different types of faimess- GNNs. In addition, to
29

---

Published as a conference paper at ICLR 2024
Table 11: Experiment results of fairness evasion attack the Facebook dataset. All victim models adopt GraphSAGE as the GNN backbone.
Attack
ACC(%)
AUC(%)
Adp(% (6)
Clean
93.20 + 0.15
93.78 = 0.08
14.00 = 0.72
7.08 = 0.64
Random
93.95 +: 0.26
94.32 1 0.11
15.14 -
7.21 1:
SAGE
FA-GNN
93.31 + 0.26
93.83 0.07 0.07
13.14
5.28 = 0.64
Gradient Ascent
92.99 0.26
94.00
14.67
1.66
G-FairAttack
+.30
0.09
7.53 1..3
Clean
91.93 0.15
0.12
0.72
1,93
Random
92.78 0.15
9.13
6.44
2.32 1 0.00
Reg
FA-GNN
92.04 0.26
93.91
1.32
0.58 = 0.27
Gradient Ascent
91.83 1 0.15
93.89 1..8910.110
3.67
1.55 1 0.55
G-FairAttack
92.15 1 0.30
93.72
5.46
2.38 1 0.91
Clean
87.26 0.94
93.74
0.91 0.56
0.90 + 0.64
Random
87.16 0.91
93.83
1.83
0.45 - 0.64
FairGNN
FA-GNN
87.37 1.17
93.07
1.91
0.45 1 0.64
Gradient Ascent
87.48 0.84
93.58
+.14
0.90 - 0.64
G-FairAttack
87.26 +: 1.30
93.66 0.48 0.48
2.16 0.96
0.90 = 0.64
Clean
93.42 0.15
93.62 +
+
1,22 + 0.64
Random
92.60
0
11.57 0.20
6.76 = 0.00
EDITS
FA-GNN
93.39 0.14
93.67
9.07 + 0.42
1.45 + 0.68
Gradient Ascent
92.83 0.27
93.80
12.29
5.75 = 0.58
AttakiAAttack
92.57 + 0.15
93.74
11.61 + 0.22
6.76 + 0.00
Table 12: Experiment results of fairness poisoning attack on the Facebook dataset. All victim models adopt GraphSAGE as the GNN backbone.
Attack
ACC(%)
AUC(%)
(%)
A%)(%)
Clean
91.83 0.18
94.05
0.11
16.78 1 0.58
9,40 1: 0.78
Random
92.99 0.32
94.09
1.09 0.03
0.52 15.91
8.56 + 0.45
SAGE
FA-GNN
93.10 + 0.48
94.83
11.09
5.22 122+:000 0.00
Metattack
92.15 0.18
9.15
19.16
11.84 =
G-FairAttack
90.66 + 0.18
93.83 0.04
18.89
12.94 + 0.33
Clean
83.86 0.48
93.08 0.22
4.03
0.45 0.78
Random
82.69 + 0.37
0.15
3.96
0.00 = 0.00
Reg
FA-GNN
83.33 0.37
93.06
5.38 0.54
0.00 + 0.00
Metattack
84.39 0.00
2.00 0.17
0.00 0.00
G-FairAttack
84.50 + 0.48
90.73 0.37
6.19 + 0.29
2.70 + 0.00
Clean
88.96 2.05
2.74 0.19
1.35 = 0.00
Random
86.73 +
94.06 0.33
2.89 2.32
0.00 1: 0.00
FairGNN
FA-GNN
86.09 4.42
94.48
1.71
0.00 0.00
Metattack
86.41 2.89
93.75
3.23
0.90
G-FairAttack
86.41 + 0.80
92.90 0.30
5.03 + 0.48
3.15 + 0.78
Clean
91.08 0.00
0.228
4.57
1,36 - 0.33
Random
92.25 0.18
93.83 1.09
16.74 1.14
9.72 1 1.26
EDITS
FA-GNN
89.17 0.32
91.23
5.46
0.75
7.41 1 1.45
Metattack
91.83 0.49
93.65 +.11
17.27 - 0.72
10.04 = 0.89
G-FairAttack
92.04 1 0.32
93.55 0.13
17.58 1 0.47
10.43 1 0.58
generated based on the similarity between credit accounts. The task is to predict whether cus- tomer has a high credit risk or low, with gender as the sensitive attribute. In this experiment, we choose GraphSAGE (Hamilton et al., 2017) as the backbone of the victim models and adopt both fairness evasion and poisoning settings. Experimental results are shown in Tables 16 and 17. We observe that the superiority of G-FairAttack is preserved on the German dataset. In conclusion, supplementary experiments verify the generalization capability of G-FairAttack attacking victim models with various GNN architectures and consolidate the universality of G-Fair Attack..ck.
30

---

Published as a conference paper at ICLR 2024
Table 13: Experiment results of fairness evasion attack the Facebook dataset. All victim models adopt GAT as the GNN backbone.
Attack
ACC(%)
AUC(%)
Adp (6)
Aeo
Clean
79,93 1.39
66.97 = 2.36
2.84 = 1.34
0.71 + 0.44
Random
79.30 0.55
67.33 + 0.50
1.11 0.47
0.51 0.48
GAT
FA-GNN
80.15 0.48
67.45 2.45
4.62 + 1.60
0.26 + 0.44
Gradient Ascent
80.25 1.40
4.24 2.110
1.35 1.00
G-PairAttack
79.09 1.21
6.55
4.35
1.73
Clean
80.15 0.36
66.50
4.88 0.60
0.52 # 0.48
Random
1
1
2.10
0,45 0.49
Reg
FA-GNN
80.15 0.36
6
5.64 0.96
1.10 0.95
Gradient Ascent
80.36 0.18
65.89 1 1.27 1.27
5.19 1.22
0.52 1 0.59
G-FairAttack
78.77 0.37
66.74 1 1.09
5.48 1 1.66
1.09 1 0.29
Clean
79.19
66.17 1.75
2.47 : 2.94
0.64 1 0.29
Random
79.62
62.54
1.49 +
0.26 + 0.44
FairGNN
FA-GNN
79.19
64.29:1:35
1.84
0.90 + 0.62
Gradient Ascent
78.98 0.32
64.03 1.73
2.73
0.39 0.33
G-FairAttack
78.45 0.80
63.94 + 2.30
3.69 + 2.41
2.13 + 0.78
Clean
79.30 0.96
68.59 3.81
0.66 0.60
3.27 + 2.19
Random
76.01 =:1::11 1.76
63.08
0.81 + 0.65
4.74 + 2.04
EDITS
FA-GNN
79.30 0.96
68.58 3.87
0.66 + 0.60
3.27 + 2.19
Gradient Ascent
77.50 1.50
61.28 2.44
0.81 0.20
2.95 3.62
G-tairAttack
76.01 + 1.94
63.08 + 1.92
1.04 0.59
4.74 + 2.61
Table 14: Experiment results of fairness poisoning attack on the Facebook dataset. All victim models adopt GAT as the GNN backbone.
Attack
ACC(%)
AUC(%)
A%)(%)
A%)
Clean
69.21 0.80
60.03
0.52
8.09 + 3.17
4.34 1: 4.09
Random
71.76 0.48
57.17
1.87
3.81 + 3.36
4.23 4.39
GAT
FA-GNN
80.68 + 0.49
73.64 1:4410 1.66
2.97 +: 1.22
3.27 :: 2.33
Metattack
69.11 0.85
63.29 1.80
74.62 3.79
70.30 + 2.58
G-FairAttack
73.35 1.33
9.85 + 1.62
5.30 - 3.20
Clean
79.09 0.81
64.86
0.71 0.11
Random
78.98 0.32
67.50
1.00 1.00
0.00
Reg
FA-GNN
78.66 + 0.00
2.44
0.00 0.00
0.00
Metattack
76.85 1.29
63.39 1.12
8.60 7.05
7.40
G-FairAttack
78.77 + 0.37
59.78 1.00
10,99 1.47
7.28 - 0.99
Clean
78.56 + 0.48
4.118
1.09 + 1.50
0.77 + 1.33
Random
78.66 1.15
52.88 + 1.68
1.00:0.69
1.15 + 0.70
FairGNN
FA-GNN
77.17 2.57
49.37 + 4.58
1.29 + 2.23
1.23 + 2.12
Metattack
79.30
52.19 +.22
0.62 = 0.68
0.84 1.13
G-FairAttack
77.60 - 0.97
$7.90 + 5.65
3,20 + 2.88
4.12 + 3.65
Clean
73.89 1.99
61.19
4.36 2.94
3.59 4.22
Random
78.88 0.97
62.58 3.75
1.83 0.88
3.02 1 1.12
EDITS
FA-GNN
78.66 1.6600000
+
0.00
0.00
Metattack
78.77 2.35
69.58 1.19
2.77 0.94
0.84 0.77
G-FairAttack
75.58 + 5.61
64.60 + 8.87
1.96#.0
5.19 7.07
F.5 ADVANCED ATTACK BASELINES
We supplement experiments on more previous attacks with -taress- adaptations. We choose two more recent adversarial attacks for GNNs in terms of prediction utility, namely MinMax (Wu et al., 2019) and PRBCD (Geisler et al., 2021). To satisfy our fairness attack settings, we modify the attacker's objective with the demographic parity loss term (in the same way as adapting gradient ascent attack and Metattack). We implement with the same budget (5%). We compare the performance of these attacks with G-FairAttack based on four different victim models with GraphSAGE as the GNN backbone on the Facebook dataset. Results shown in Table 15. From the experimental results, observe that (1) G-FairAttad
attack baselines a fairness evasion attack setting
31

---

Published as a conference paper at ICLR 2024
Table 15: Experiment results of fairness evasion attack the Facebook dataset compared with more advanced attack baselines. All victim models adopt GraphSAGE as the GNN backbone.
Attack
ACC(%)
AUC(%)
(%)
Aeo(%) (%)
Train ACC(%)
Clean
92.36 0.32
94.06 + 0.14
16.71 = 0.79
10.10 = 0.41
100.00 0.00
PRBCD
92.68 0.00
94.26 +: 0.10
15.23
0.31
8.11 0.33
99.62 + 0.00
SAGE
MinMax
92.99 = 0.00
94.32
15.69 + 0,31
8.69 + 0.33
98.66 - 0.19
G-FairAttack
92.15 0.37
93.89 0.15
18.71 + 0.74
11.91 0.97
100.00 0.00
Clean
91.29 1 0.49
93.69 0.13
0.86 1 0.83
1.79 1.87
98.66 1 0.33
PRBCD
91.72 = 0.85
94.00 0.07
1.33 = 2.00
1,73 + 0.33
98.08 = 0.51
Reg
MinMax
91.61 0.49
94.01 0.08
0.41 0.77 1 0.41
1.73 1.73-10.. 0.33
97.19 0.11
G-FairAttack
91.19 0.37
93.66 0.12
1.80 = 0.60
2.12 + 1.20
98.53 + 0.29
Clean
92.57
93.97 0.20
3.38 1 1.44
2.02 0.58
98.98 0.55
PRBCD
92,46 0.26
94.03 + 0.26
0.26
3.36 + 1.05
1,93 + 0.33
98.53 + 0.29
FairGNN
MinMax
92.67 0.55
9..12
3.53 + 1.60
1.93 0.33
97.57 1 0.29
G-FairAttack
92.57 0.18
93.80
4.40 + 1.14
2.05 1.25
98.98 + 0.55
Clean
93.42
93.66
9.12 + 0.58
1.67 + 0.78
98.34 + 0.11
PRBCD
93.10 0.73
93.88
10.78 + 1.15
5.41 2.34
97.89 + 0.19
EDITS
MinMax
93.20 = 0.37
93.88
10.94 + 1.70
4.31 + 1.90
97.45 + 0.29
G-FairAttack
93.10 0.15
93.88 0.15
10.78 1.15
5,41 2.34
97.95 0.22
Table 16: Experiment results of fairness evasion attack on the German dataset. All victim models adopt GraphSAGE as the GNN backbone.
Atlack
ACC(%)
AUC(%)
(ap(%) (%)
Ac,(%)
Clean
58.80 1.06
66.56
58.02
5.05
56.20 5.76
Random
58.80 + 1.06
66.44 + 1.02
56.32 + 2.70
53.57 = 3.01
SAGE
FA-GNN
59.60 +: 0.80
68.44 1 0.96
0.96
1.90
52.66 - 4.88
Gradient Ascent
58.13 + 1.51
66.14 1.00
59.52 4.58
57.99 = 4.93
G-FairAttack
58,00 1: 1.74
65.75 1.21
58.73 + 4.81
56.83 = 4.95
Clean
61.87 + 2.41
61.40
+
4.34 + 1.76
Random
61.33 + 2.01
61.44
3,90 1.35
5.18 = 1.08
Reg
FA-GNN
62.00 3.02
61.79
3.69 2.11
5.22 2.05
Gradient Ascent
61.20 +: 2.40
60.53
3.97 4.11
4.62 1 2.99
G-FairAttack
61.33 2.27
41.49
+
6.65 + 2.53
Clean
64.40 + 3.12
4.26 3.99
5.36 = 2.32
Random
64.53 +: 3.11
59.71 338.3
4.61 2.80
5.67 3.63
FairGNN
FA-GNN
64.67 2.89
60.03
4.40
5.95 = 3.22
Gradient Ascent
64.80 3.17
59.40 4.662
4
5.64 + 2.35
G- G-FairAttack
4.827
59.66 3.57
5.46
5.92 2.33
Clean
68.27 + 1.97
57.48 2.13
2.17
3.12 1.77
Random
68.13 1.22
58.90 1.62
2.81
3.41 + 2.13
EDITS
FA-GNN
68.27 : 1.97
57.48 2.144
2.17
3.12 = 1.77
Gradient Ascent
68.13 +: 1.22
58.90 1.62
2,81 4 2.14
3.41 + 2.13
G-FairAttack
68.13 + 1.22
58.90
2.81 + 2.14
3.41 + 2.13
has the most desirable performance in attacking different types of (faimess--aware) victim models and (2) G-FairAttack best preserves the prediction utility of victim models over the training set. In conclusion, we obtain that proposed surrogate loss and constrained optimization technique help G-FairAttack address the two proposed challenges of fairness attacks while a simple adaptation of previous attacks is not effective in solving these challenges.
G DEFENSE AGAINST FAIRNESS ATTACKS OF GNNS
In this paper, the purpose of investigating the faimess attack problem GNNs is to highlight the vulnerability of GNNs on faimess and to inspire further research on the fairesss defense of GNNs. Hence, would like to discuss the defense against faimess attacks of GNNs. Considering the difficulty in faimesss defense, this topic deserves careful further study, and we only provide some simple insights defending against fairness attacks of GNNs in this section.
32

---

Published as a conference paper at ICLR 2024
Table 17: Experiment results of fairess poisoning attack on the German dataset. All victim models adopt GraphSAGE as the GNN backbone.
Attack
ACC(%)
AUC(%)
Adp(%)
(%)
Clean
59.60 + 1.06
63.87 + 1.30
41.29 = 7.36
36.94 = 7,94
Random
62.13 1.97
65.48
0.57
41.52 + 8.40
38.34 :: 5.29
SAGE
FA-GNN
64.67 + 1.01
71,22 2.08
43,99 = 0.63
42.79 = 2.16
Metattack
58.13 3.63
64.03
46.31 1
43.87 = 3.49
G-FairAttack
63.87 2.34
66.10 1.68
47.98 = 4.99
43.56 = 5.48
Clean
58.00 2.50
60.70
0.80 + 0.28
1.37 = 1.55
Random
60.13 +: 2.84
61.83
0.13
3.15
Reg
FA-GNN
60.80 + 1.74
64,42
0.72 0.7200880 0.88
4.83 + 1.37
Metattack
58.67 1.01
60.21 0.25
0.42 1 0.33 0.33
2.59 1 0.52
G-FairAttack
57.87 3.72
60.42 1 1.48
3.38 1 1.86
7.77 1 3.48
Clean
60.91 2.58
02.15
1.87 + 1.93
1.48 1 1.50
Random
66.33 2.98
6.77
4,50 + 3.57
6,33 + 4.44
FairGNN
FA-GNN
68.22 3.36
63.07 5,19
2.59 1 2.73
1.86 + 1.10
Metattack
67.78 + 4.92
63.04 4.35
2.06 + 2.09
1.98 1.07
G-FairAttack
65.34 4.70
64.32 1 6.83
7.86 + 1.68
10.64 - 2.54
Clean
64.01 1.83
65.59 + 0.92
12.74 1.44
6.66 + 3.28
Random
61.90 + 1.16
66.18
10.02 + 3.78
7.84 + 5.78
EDITS
FA-GNN
63.45 + 2.51
19.45 + 2.53
13.62 + 3.63
Metattack
62.24 + 0.51
63.46
15.92 8.11
10.77 = 3.41
G-FairAttack
65.34 + 1.02
65.31 + 1.49
20.43 + 5.37
15,30 + 5.53
(1). According to the study in (Hussain et al., 2022), injecting edges that belong DD and EE groups can increase the statistical parity difference. Hence, a simple fairness defense strategy is to delete edges DD and EE groups randomly. This strategy makes possible to remove some poi- soned edges in the input graph. However, this method cannot defend against G-FairAttack because G-FairAttack can poison the edges in all groups (EE, ED, DE, and DD).
(2). In our opinion, preprocessing debiasing frameworks such EDITS can be a promising paradigm for faimess defense. Next, we explain the reasons in detail. We first review the pro- cesses of EDITS framework. EDITS is preprocessing framework for GNNs (Dong et al., 2022a). First, we feed the clean graph into EDITS framework and obtain a debiased graph by reconnect- ing some edges and changing the node attributes where we modify the debiasing extent with threshold. Then, EDITS runs a vanilla GNN model (without fairness consideration), such as GCN, on the debiased graph. Finally, we find that the output of GCN on the debiased graph is less biased than the output of GCN on the clean graph. As a preprocessing framework, EDITS would flip the edges again to obtain debiased graph for training after poison the graph structure by attacking methods. Consequently, we can obtain that EDITS can obtain very similar debiased graphs for any two different poisoned graphs with a strict debiasing threshold, while the accuracy will also decrease as the debiasing threshold becomes stricter because the graph structure has been changed too much. In conclusion, EDITS has tradeoff between the debiasing effect and the prediction utility. EDITS can be strong fairness defense method for GNNs by sacrificing the prediction utility.
(3). possible defense strategy against fairness attacks of GNNs is solve similar optimization problem as Problem 1 while minimizing the attacker's ' objective as
min Cj (go-, A', A'EF
X, Viest: S)
s.t. 0" = arg min L. (go. A X.Y. |A' - AlI S 2A,
(17)
0 L(go- A. X, Vinan) L(go A', X,Y, Vurin) S.
The meaning of this optimization problem is to find the rewired graph structure that minimizes the prediction bias. The prediction bias is computed based the model trained on the rewired graph. It can be seen as an inverse process of t-FairAttack. As a result, we can rewire the problematic edges that hurt the faimess of the model trained on the rewired graph.
33

---

Published as a conference paper at ICLR 2024
H BROADER IMPACT
Adversarial attacks on fairness can make a significant impact real-world scenarios (Solans et al., 2021; Mehrabi et al., 2021; Hussain al., 2022). In particular, fairness attacks can exist in many different real-world scenarios.
For personal benefits, malicious attackers can exploit the fairness attack to affect a GNN model (for determining the salary of employer or the credit/loan of user account) into favoring specific demographic groups by predicting higher values of money while disadvantaging other groups.
For commercial competitions, malicious competitor can attack the fairness of GNN-based recommender system deployed by a tech company and make its users unsatisfied, especially when defending techniques of GNNs' utility have been widely studied while defending techniques of GNNs' fairness remain undeveloped.
For governmental credibility, malicious adversaries can attack models used by a government agency with the goal of making them appear unfair in order to depreciate their value and cred- ibility.
In addition, adversarial attack on fairness is widely studied on independent and identically dis- tributed data. Extensive works (Chang et al., 2020b; Solans et al., 2021; Mehrabi et al., 2021; Van al., 2022; Chhabra al., 2023) have verified the vulnerability of algorithmic fairness of machine learning models. In this paper, we find the vulnerability of algorithmic faireess also exists in GNNs by proposing a novel adversarial attack on fairness GNNs. has the potential risk of being lever- aged by malicious attackers with access to the input data of deployed GNN model. Despite that, our research has a larger positive influence compared with the potential risk. Considering the lack of defense methods fairness of GNNs, our study highlights the vulnerability of GNNs in terms of fairness and inspires further research on the fairness defense of GNNs. Moreover, we also provide discussions attack patterns and simple ways to defend against fairness attacks.
34


Reviews:
[{"review_id": "2YcprlNCTf", "reviewer": "Reviewer_B8qV", "summary": "- The paper studies the problem of adversarial attacks on fairness of GNNs. The authors propose a general framework called G-FairAttack to attack various types of fairness-aware GNNs from the perspective of fairness, with an unnoticeable impact on prediction utility. The authors employ a greedy strategy and propose a non-gradient sequential attack method. In addition, the authors introduce a fast computation technique to reduce the time complexity of G-FairAttack.", "questions": "- In Table 1, when the victim is EDITS, and the dataset is Pokec_z, did any issues arise with the baseline, or were the results of all four baselines identical?\n- Regarding the invisibility of fairness attacks, should consideration extend to structural modifications that are not easily noticeable, apart from merely constraining them through budget limitations?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is well written and easy to read.\n- The proposed unnoticeable fairness attacks of GNNs are novel and interesting.\n- The theoretical analysis demonstrates that the designed surrogate loss function serves as a common upper bound for three fairness loss functions.", "weaknesses": "- Grey-box attack scenarios are relatively uncommon in real-world applications. I believe it would be more interesting if it could be extended to black-box attack settings.\n- In terms of the utility metrics, G-FairAttack and the baseline seem to have a relatively small difference. I believe this does not fully reflect the authors' claim of making attacks unnoticeable. In other words, the issue mentioned by the authors in the introduction, \"no existing work considers unnoticeable utility change in fairness attacks,\" does not appear to be very pressing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ydXNQtVfCb", "reviewer": "Reviewer_qWJG", "summary": "The paper investigates adversarial attacks on the fairness of Graph Neural Networks (GNNs). The authors introduce an attack framework, G-FairAttack, designed to corrupt the fairness of various types of fairness-aware GNNs subtly, without noticeably affecting prediction utility.  G-FairAttack is formulated as an optimization problem, considering a gray-box attack setting where the attacker has limited knowledge of the model. The authors propose a surrogate loss function and a non-gradient attack algorithm to solve the optimization problem, ensuring that the attacks are unnoticeable and effectively compromise the fairness of the GNNs.", "questions": "Would it be possible to apply the G-FairAttack framework to a broader range of datasets, such as those utilized in EDITS paper you referenced, rather than limiting the evaluation to only three datasets?\n\nHow much computational time is required to execute G-FairAttack?\n\nWhy do all the attack methods seem to have minimal influence on the utility score? Is there a trade-off between utility and fairness scores? How is the attack budget determined for fairness attacks, and under what circumstances would the utility score significantly decrease?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The introduction of G-FairAttack brings a new perspective to the understanding of adversarial attacks in the context of fairness-aware models.\n\nBy uncovering vulnerabilities related to fairness, the paper contributes valuable insights that can guide the development of more robust and ethical AI systems.\n\nThe paper includes extensive experiments that validate the effectiveness of the proposed attacks. This empirical evaluation strengthens the credibility of the findings and their relevance to practical scenarios involving fairness-aware GNNs.", "weaknesses": "The assumptions about the attacker's knowledge might not cover all possible real-world scenarios. The gray-box setting is a middle ground, but exploring both black-box and white-box attacks could provide a fuller picture of the vulnerabilities.\n\nThe performance of  G-FairAttack is worse than random attack under some scenarios in Table 1, 6 and 7.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "32Ym5vaHvb", "reviewer": "Reviewer_dSr8", "summary": "The paper discusses the growing importance of fairness-aware Graph Neural Networks (GNNs) and their vulnerability to adversarial attacks. The authors introduce the G-FairAttack framework as a tool to compromise the fairness of GNNs without significantly affecting prediction utility. They also present a fast computation technique to enhance the efficiency of G-FairAttack.", "questions": "Refer to the weakness part.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.Relevance of Topic: The paper addresses the crucial and timely subject of fairness in GNNs, a significant area in AI research.\n2.Innovative Framework: The introduction of the G-FairAttack framework, complemented by a fast computation technique, offers a novel perspective on understanding vulnerabilities in fairness-aware GNNs.", "weaknesses": "1． Unpractical attack setting. The proposed evasion attack is not practical as there is no motivation for the model owner to replace data in a transductive learning setting, as shown by equation 1.\n\n2． Overclaimed contribution. The evidence is needed when presenting “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.” \n\n3． Untenable theoretical analysis. The theorem 1 is proved by unconvincing assumptions, e.g., $P_{\\hat{Y}}(z) \\geq \\Pi_i \\operatorname{Pr}(S=i)$ and other assumptions. Please be aware there is a difference between assumption and proof. The remarks for theorem 1 indicate its unconvincing nature. A lot of logical error exists in the proof part. For example, it is hard to say Pr(s=0)Pr(s=1)<=1/4 without evidence. In the paragraph above eq (8), |P_{s=0}(z)- P_{s=0}(z)|<=1 always hold according to the definition of fairness, what is the meaning to prove it, as it cannot support the whole analysis pipeline. Authors are strongly suggested to revise it to avoid analysis mistakes in the proof. \n\n4． Unclear experimental setting. What is the target GNN architecture when discussing the effectiveness? This point should be clarified to avoid attackers having knowledge of the target GNN architecture. E.g., using surrogate GCN to attack target GCN. \n\n5． Missed baselines. According to an existing study, “Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks”, a baseline method in this paper is injecting inter-group links. This is practical in the proposed setting where attackers have knowledge of the training graph.\n\n6. Metrics.  In table 7, It looks like the metattack achieves better attack performance than the proposed method when considering the the metric $\\Delta dp / \\Delta Acc$, which should be an effective metric to evaluate the efficiency of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)