Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections
Authors: Zihan Luo
Hong Huang
Yongkang Zhou
Jiping Zhang
Nuo Chen
Hai Jin
Venue: NeurIPS 2024 poster (2024)
Keywords: Fairness
Graph Neural Network
Attack
Primary area: graph_neural_networks

Abstract: Despite the remarkable capabilities demonstrated by Graph Neural Networks (GNNs) in graph-related tasks, recent research has revealed the fairness vulnerabilities in GNNs when facing malicious adversarial attacks. However, all existing fairness attacks require manipulating the connectivity between existing nodes, which may be prohibited in reality. To this end, we introduce a Node Injection-based Fairness Attack (NIFA), exploring the vulnerabilities of GNN fairness in such a more realistic setting. In detail, NIFA first designs two insightful principles for node injection operations, namely the uncertainty-maximization principle and homophily-increase principle, and then optimizes injected nodes’ feature matrix to further ensure the effectiveness of fairness attacks. Comprehensive experiments on three real-world datasets consistently demonstrate that NIFA can significantly undermine the fairness of mainstream GNNs, even including fairness-aware GNNs, by injecting merely 1% of nodes. We sincerely hope that our work can stimulate increasing attention from researchers on the vulnerability of GNN fairness, and encourage the development of corresponding defense mechanisms. Our code and data are released at: https://github.com/CGCL-codes/NIFA.

Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections
Zihan Luo, Hong Huang", Yongkang Zhou, Jiping Zhang, Nuo Chen, Hai Jin
Huazhong University of Science and Technology, China [zihanluo, honghuang, yongkangzhou, hongggungggggggggggggogoooooooo jipingz, nuo_chen, hjin Seuuttthhut.... edu.
Abstract
Despite the remarkable capabilities demonstrated by Graph Neural Networks (GNNs) in graph-related tasks, recent research has revealed the fairness vulner- abilities in GNNs when facing malicious adversarial attacks. However, all exist- ing fairness attacks require manipulating the connectivity between existing nodes, which may be prohibited in reality. To this end, we introduce a Node Injection- based Fairness Attack (NIFA), exploring the vulnerabilities of GNN fairness in such a more realistic setting. In detail, NIFA first designs two insightful princi- maantaantymmaiimzzatiinn principle
ples for node injection operations, namely the and homophily-increass principle, and then optimizes injected nodes' feature ma- trix further ensure the effectiveness of faimess attacks. Comprehensive exper- iments on three real-world datasets consistently demonstrate that NIFA can sig- nificantly undermine the fairness of mainstream GNNs, even including fairness- aware GNNs, by injecting merely 1% of nodes. We sincerely hope that our work can stimulate increasing attention from researchers on the vulnerability of GNN fairness. and encourage the development of corresponding defense mechanisms. Our code and data are released at: https///ggibbbooom///C-o-ooo///
Introduction
Due to the strong capability in understanding graph structure, Graph Neural Networks (GNNs) have achieved much progress in graph-related domains such as social recommendation [30,31] and bioinformatics 4 (27. Nevertheless, despite the impressive capabilities demonstrated by GNNs, more and more in-depth research has revealed shortcomings in the fairness GNN models, which greatly restricts their applications in the real world.
In fact, studies S have found that the biases and prejudices existed training data would be fur- ther amplified through the message propagation mechanism of GNNs, leading to model predictions being correlated with certain sensitive attributes, such as gender and race. Such correlations are usually undesired and can result in fairness issues and societal harm. For instance, in online recruit- ment, recommender based on GNNs may be associated with the gender of applicants, leading to differential treatments towards different demographics and consequently giving rise to group unfair- ness. To address fairness issues in GNNs, researchers have proposed solutions such as adversarial learning [5] 28 data augmentation [7 22 and others, which have achieved promising results.
However, recent research in the machine learning domain indicates that fairness is actually suscepti- ble to adversarial attacks 3 26 29 Given this, we cannot help but wonder: "Is the fairness of GNN
Hong Huang the corresponding author. Zihan Luo, Hong Huang. Yongkang Zhou, Jiping Zhang and Jin are affiliated with the National Engineering Research Center for Big Data Technology and System, Ser- vice Computing Technology and Systems Laboratory, Cluster and Grid Computing Lab, School of Computer Science and Technology. Huazhong University of Science and Technology.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

models also highly vulnerable?" For example, in e-commerce, if attackers could exacerbate perfor- mance disparities between male and female user groups by attacking GNN-based recommendation models, they could ultimately cause the e-commerce platform to provoke dissatisfaction from spe- cific user demographies and gradually lose its appeal among these users. Several studies [ 13
have explored the vulnerability of GNN fairness and proposed effective attack strategies. Unlike conventional attacks, these fairness attacks aim to undermine GNN fairness without excessively compromising its utility. However, all these works require altering connectivity between existing nodes, whose authority is typically limited in the real world, such as modifying the relationship be- tween real users. In contrast, injecting fake nodes into the original graph is more practical way to launch an attack without manipulating the existing graph [12 32 B4], which is still under-explored in the field of GNN fairness attack. To address this gap. aim to be the first to launch attack on GNN fairness via node injection, examining their vulnerabilities under such a more realistic setting.
Specifically, launching node injection-basee fairness attack on GNNs is non-trivial, whose chal- lenges can be summarized as follows: RQ1: How to determine the node injection strategy? The node injection can be decomposed into two steps, including selecting appropriate target nodes and connecting the injected nodes with them, both will impact the effectiveness of the attack. RQ2: How to determine the features of the injected nodes after node injection? ? Like the real nodes, injected nodes will also participate in the message propagation process of GNNs, thereby affecting their neighbors and even the whole graph. Given the key role of massage propagation in GNN fairness [40 (45,, proposing suitable strategies to determine the features of injected nodes is also important.
To address these challenges, we propose a gray-box poisoning attack method namely Node Injection- based Fairness Attack (NIFA) during the GNN training phase. In detail, for the two steps in the first challenge, NIFA innovatively designs two corresponding principles. The first is the uncertainty- maximization principle, which asks to select real nodes with the highest model uncertainty as target nodes for injection. The idea is that nodes with higher uncertainty are typically more susceptible to attacks, thereby ensuring the attack's effectiveness. After selecting target nodes, NIFA follows the second principle, the humophily-imee -increeee- principle, to connect target nodes with injected nodes. This principle aims to deteriorate GNN fairness by enhancing message propagation within sensitive groups (22 [4)] For the second challenge, multiple novel objective functions proposed after node injection to guide the optimization of the injected nodes' features, which could further impact the victim GNN's fairness from feature perspective. In summary, our contributions are as follows:
To the best of our knowledge, we are the first to conduct fairness attacks on GNNs via node injec- tions, and our work successfully highlights the vulnerability of GNN fairness. We also summarize several key insights for the future defense of GNNs' fairness attacks from the success of NIFA.
We propose a node injection-basee gray-box attack named NIFA. To be concrete, NIFA first de- signs two novel principles guide the node injection operations from a structure perspective, and then proposes multiple objective functions for the injected nodes' feature optimization.
We conduct extensive experiments on three real-world datasets, which consistently show that NIFA can effectively attack existing GNN models with only 1 1% perturbation rate and an un- noticeable utility compromise, even including fairness-wwaee GNN models. Comparisons with other staatt-f-thhe-eeeee baselines also verify the superiority of NIFA in achieving fairness attacks.
2 Related work
Fairness on GNNs. Researchers have discovered various fairness issues of GNNs, which often lead to societal harms (2 and performance deterioration (1133 in practical applications. Algorith- mic fairness on GNNs can be categorized into two main types based on the definition: individual fairness [1 6 and group fairness (5) 37 466.. Individual faimess requires that similar individuals should receive similar treatment, while group fairness aims to protect specific disadvantaged groups [16. In detail, many researchers have delved into studies focusing on fairness grounded in sensi- tive attributes. For instance, Dai et al. [5] reduce the identifiability of sensitive attributes in node embeddings through adversarial training to enhance fairness. Fair VGNN (38] goes a step further by introducing a feature masking strategy to address the problem of sensitive information leakage dur- ing the feature propagation process in GNNs. Graphair
[17] achieves fairness through an automated data augmentation method and FairSIN [40] designs a novel sensitive information neutralization method for fairness. Beyond faimess related to sensitive attributes, some researchers also direct
2

---

attention to fairness related to graph structures, like DegFairGNN [2 and Ada-GNN (23]. In this work, we mainly focus on attacks on the group fairness of GNNs based on sensitive attributes.
Attacks on GNNs. Finding out potential vulnerabilities thus improving the security of GNNs re- mains a pivotal concern in the field of trustworthy GNNs 42 From the perspective of attackers, they aim to compromise the GNNs' performance on graph data via manipulating graph structures [24 32 47 node attributes 48). or node labels [19]. Among these methods, node injection at-
lacks, given the attackers' limited authority to manipulate the connectivity between existing nodes, emerge as one of the most prevalent methods 32
34 43. However, existing attacks, including node injection attacks, mainly focus on undermining GNN's utility, with little attention to the vul- nerability of GNN fairness. Different from attacks on GNN utility, fairness-targeted attacks aim to deteriorate the fairness without significantly compromising the accuracy. FA-GNN [T]. FATE [13], and G-FairAttack [4]] stand out as the few ones that we are aware of to explore attacks on GNN fairness. FA-GNN's empirical findings suggest that adding edges with certain strategies can signifi- cantly compromise GNN fairness without affecting its performance [I]. FATE [3] formulates the fairness attacks bi-level optimization problem and proposes a meta-learning based framework. G-FairAttack [4]] designs a novel surrogate loss with utility constraints to launch the attacks non-gradient manner. Nevertheless, all these works require modifying the link structure between existing nodes, which may be prohibited in reality due to the lack of authority.
3 Preliminary
Here we will introduce some basic notations and concepts, and then give our problem definition.
3.1 Notations
A graph is denoted as G = (V,A,)), where V is the node set, and A E R | adjacency matrix. E RIV xD denotes the feature matrix, in which D is the feature dimension. Under the settings of node classification, each node v E V will be assigned with label yo E V, and GNN-based mapping function f& (V.g) - 21,2, ..., (D with parameters 0 is learned to leverage the graph signals for label prediction, where y represents the true label set.
represents the
3.2 Fairness-related concepts
In alignment with prior works 5 17. we mainly focus on group fairness where each node will be assigned with a binary sensitive attribute s E {0,1), although our attack could also be generalized to the settings of multi-sensitive groups and we leave this as our future work. Based on the sensitive attributes, the nodes can be divided into two overllapdp groups V (Vo, V1}. and we employ the following two kinds of fairness related definitions:
Definition 1. Statistical Parity (SP), The Statistical Parity requires the prediction probability dis- tribution to be independent of sensitive attributes, i.e. for any class y E y and any node v E V:
P(g. y|s = 0) = P(ù. u|s =1),
(1)
where dy denotes the predicted label of node v.
Definition Equal Opportunity (EO). The Equal Opportunity requires that the probability of
predicting correctly is independent of sensitive attributes, i.e. for any class E y and any node v E V, we can have:
P(o. = ylve- = =- = P(u- = vlue = =- = 1).
(2)
Based on the above definitions, we can define two kinds of metrics Asp and A to quantitatively measure fairness. For both metrics, smaller values indicate better fairness:
Asp
E P(O = y|s 0) P(ù = yls 1)/-
(3)
Ago P(j = v|v y,8 0) P(ù = y 8-8 1)|-
(4)
3

---

3.3 Problem definition
In this paper, our goal is to launch fairness-targeted attacks on GNN models through the application of node injection during the training phase, i.e. poisoning attack. Following the line of previous attacks on GNNs [32 41), our attack under the prevalent gray-box setting, where the attackers obtain the graph G with node labels J/ and the sensitive information but can not access the model architecture and parameters 9. Detailed introduction to our attack settings is provided in Appendix B Specifically, through injecting malicious node set V into the graph, the original graph = (V, A, X) is poisoned as g' = (V", A X'), where
V = -UV, X= X,
X
X, ERIMIDD
(5)
A' A'=
A V A, J.
V RMNIII Ar RMMINE
(6)
V
Both V, and Ay are matrices for illustrating the connectivity related injected nodes, and X, the feature matrix of injected nodes Vı. The true label set y will not be poisoned by injected nodes in our settings, as such information is typically hard to modify reality. For conciseness, we denote F()) and M(-) the evaluation functions on fairness and utility for the learned mapping function Sa, respectively. Then our goal as an injection-basee -based attack on fairness could formulated as:
max (F 3'
arg max ((fo g' = (V,A', M/ S b, deg(v)oev, d. 8-
As a poisoning attack, the first constraint in Eq. 7 requires to train the victim model fa- with parameters 0 on the poisoned graph G", so that the predictions of fa. are as correct as possible before evaluating the attack performance. The following constraints in Eq. 7 make sure that the proposed attack is unnoticeable and deceptive to the defenders, i.e. the number of injected nodes is below a predefined budget e and the degrees of injected nodes are constrained by budget d. Our goal is to find poisoned graph G' to deteriorate the faimess of victim models fo- as severely as possible, i.e, maximize the fairness metrics Agp and AgO introduced previously.
4 Methodology
In this section, we first give an overview of our attack method NIFA. Then we will claborate on the details of each module and summarize the implementation algorithms at last.
4.1 Framework overview
The overall framework of NIFA is illustrated in Figure 1 two principles to guide the node injection operations. For the first uncertainy-mmxiiizaiiie maximization princi- ple, NIFA utilizes the Bayesian GNN for model uncertainty estimation of each node, and then selects target nodes with the highest uncertainty (a). As for the second nomophily-inereass principle, NIFA requires each injected node can only establish connections to target nodes from one single sensitive group (b), thus increasing the tomophily-ratie and enhancing information propagation within sensi- tive groups After node injection, multiple objective functions are designed to guide the optimization of injected nodes' feature matrix, where we introduce an iterative optimization strategy for avoiding over-fitting issues (c). The details of each part will be introduced later.
As mentioned before, NIFA first employs
4.2
Node injection with principles
The first step of NIFA is conducting node injections, which aims to ensure the effectiveness of NIFA from a structure perspective. In detail, we propose two novel principles to guide the node injection maxiiiiiatnmmiiiiiaaiiiioo principle and Homophily-increan principle.
operations, namely
Same as the prior work (32). we define the perturbation rate as the ratio of injected nodes to the labeled nodes in the original graph, i.e. [Vrl/VV/,, where Vi denotes the labeled node set.

---

Original graph
Injected
Legend:
Clasiil liatioo Looc
Nedoo of dic ferent
Group
Surregate Model
Nodes with high unostainst Original olge
Injestal modex Injectel ofges
Poisoned graph G¹
Iterative training
Injected Fecture
Constraint of Feature
Faimess Loss
Loss
(a) Uncertainty Estimation
(b) Node Injection
(c) Feature Optimization
The overall framework NIFA: (a) Utilizing uncertainty estimation, nodes exhibiting high uncer- tainty (depicted as shaded nodes) are designated as targeted nodes. (b) Injected nodes are equally assigned to each sensitive group, and only connect targeted nodes with the same sensitive attribute. (c) After node injection, the injected feature matrix and surrogate model are optimized iteratively by diverse objective functions.
Figure I:
maximization principle. Intuitively, nodes with higher model uncertainties are posi- tioned closer to the decision boundary, which means their predicted labels are more vulnerable and easier to flip when facing adversarial attacks. We acknowledge that the model uncertainty may not be the only method measure the vulnerability of nodes, and we will discuss potential alternative approaches in Appendix H.2 Inspired by [20), we utilize a Bayesian GNN to estimate the model uncertainty of each node, where we employ the Monte Carlo dropout approach (9] to approximate the distributions of the sampled model parameters. Given GNN with parameters Oz, we obtain dif- ferent model parameters through times independent Bernoulli dropout sampling processes, i.e.:
Uncertainty-maxiiizatio
P(M,) ~ Bernoulli(p) dg. M₁ O 0g
, (1,
(8)
where M; is the ith sampled binary mask following the Bernoulli distribution with parameter p. and @ denotes the dot production operation. Here we take two-layer GCN (TO] with parameters 0g as the Bayesian GNN for estimating the uncertainty of each node, and 0g is optimized by minimizing the following objective function, which consists of a cross-entropy loss plus regularization term:
1 T Σ y log(See, (V,9))
1 1-P 1 2T
L(0g)
where denotes the true labels, || denotes the L2 regularization, T' is the number of sampling processes and fee, (-) is the mapping function with the ith sampled parameters 0s.. After the training process, model uncertainty can be estimated by calculating the variance of T times predictions with the sampled parameters {0s, |T Intuitively, nodes with lower variance are more confident in their predictions and vice versa. Thus, the model uncertainty scores U E IR [V] are positively correlated with the model prediction variance, and we simply estimate U with the following formulation:
U = Var(fee, (V,9)). 1-1
(10)
Under the guidance of the uncertainty-maximiaatiin principle, we will select nodes with the top 1: model uncertainty U in each sensitive group the target nodes, where & is saper--arammttr.
Homophily hoomophly--nerreaee innrrease principle. After selecting target nodes, the next step is to connect the injected nodes with them. In particular, we first present our strategy in this step, with more rationales pro- vided later: the injected nodes V/ are first equally assigned to each sensitive group in the graph, then each injected node will exclusively connect to d random target nodes with the same sensitive attribute, as illustrated in Figure bb), where is hyper-parameter. parameter. At this stage, the node injection operations completed, with the structure of the original graph G manipulated.
Intuitively, compared with random node injection, our strategy prevents information propagation between nodes of different sensitive groups through the injected nodes, making it casier to accentuate
5

---

differences in embeddings between groups and thereby exacerbate unfairesss issues [3. We also provide a brief theoretical analysis show that such strategy could lead to the increase of node- level homophily ratio. Similar to [ we define the node-level homophily-ratio Hy as the ratio of
neighbors of node u that have the same sensitive attribute as node u, i.e. Hr Lvea, ( where No. denotes the neighbors of node and 1(-) is indicator function. Then W.
have:
Lemma 1. For target node that will connect with injected nodes, proposed node injection strategy will lead to the increase of node-level homophily- Hu-
Due to space limitation, the proof for Lemma I provided in Appendix C It is worth noting that H., is also equivalent to the probability of choosing neighbors with the same sensitive attribute for node u. From the perspective of message propagation, higher node-level homophily-ratio indicates that more sensitive-related information will be aggregated to the target node, thus leading to more severe unfairness issues on sensitive attribute: We believe that such characteristics could empower our node injection strategy with stronger capability fairness attacks.
4.3 Feature optimization
In this part, we will introduce the details of optimizing injected nodes' features X,, which helps further advance the effectiveness of NIFA. Generally, under a gray-box attack setting, there is no visible information about the victim models for the attackers, thus requiring attackers to propose surrogate GNN model at first for assessing their attacks. To be specific, similar to the training pro- cess of victim models described in Eq. ? the surrogate model S will be trained on the poisoned graph G' and optimize its parameter Og to maximize the utility. Conversely, X, is designed to mis- lead S, ensuring that even well-trained surrogate model will still maintain high unfairness under attacks. Instead of employing pre-trained frozen surrogate model S, NIFA asks two components, i.e and X, to be trained iteratively with different objective functions, which avoids the attack be- ing over-fitting to specific model parameters. In detail, the surrogate model & follows the common training procedure of a GNN classifier with cross-entropy loss, while for the injected nodes' feature optimization, we devise multiple effective objective functions as follows:
Classification loss. Although our primary goal is to maximize the unfairness of GNN model, it is crucial to ensure that the utility of the victim model will not experience a significant decrease after training on a poisoned graph [3] 41), thus being unnoticeable for utility- attack detection. To this end, we set cross-entropy loss as our first objective function, i.e.:
LCE = D
Σ nEpir
Yu log hu:
(11)
where yo denotes the original training node set, and h2 denotes the output logits of node u.
Fairness loss. Aiming at enlarging the unfairness on GNNs, we then design two kinds of fairness loss based on the definitions of Agp and A AOO, which are formulated as:
LSP
1
Σ
h
Σ WEVI
h hull2.
(12)
D
D
WEV!!
LEO = -11 Σ
Σ
(13)
Der 1.y
yEY
0.8
NEVI
WEVEY
where li,, E |R! denotes the raw output of node u, and Au.y E R denotes the raw output of node on class y. Ver denotes the training nodes with sensitive attribute and label y. By minimizing LSP and LEO, the gap in output between different groups increases, leading to high unfairness.
Constraint of feature. To further accentuate the differences between different sensitive groups, it is important to ensure that the information introduced by injected nodes for different sensitive groups
"Similar conclusions have been concluded from multiple prior works 22 of the relationship between the homophily-raie ratioo and unfairness, one can also refer to 40 which provides the corresponding theoretical analysis from massage propagation perspective.
26 40
For better a understanding

---

is distinct during the message propagation process, To this end, we devise the following constraint function on the injected node feature matrix X,:
LCF - -11
11.ol
Σ XI.u veVi,o
|r,1
Σ
Xr.
(14)
WEVi,
where Vr, is the injected node set linking to the ith sensitive group during the node injection.
Overall loss. By combining the aforementioned objective terms, the overall loss L for injected nodes' features optimization can be formulated as:
L = LCE + LCF + B (LsP + Lgo),
(15)
where a and are two hyper-parameters to control the weights of different objective functions.
4.4 Implementation algorithm
Training process. Due space limitation, we summarize the pseudo-code of NIFA Algorithm in Appendix [D] Initially, we perform node injection operations based on two proposed principles (lines 2-4). Subsequently, an iterative training strategy is utilized to optimize the surrogate model and injected nodes' feature (lines 5-15). Specifically, after each inner loop for X, training, it is clamped to fit the range of the original feature X (line 14) so that the defenders cannot filter out the injected nodes easily through abnormal feature detection. For datasets with discrete features, X, is rounded to the nearest integer at the end of the training process (lines 16-18).
Inference process. As a poisoning attack, the original clean graph G is poisoned as g' after mali- cious node injection and feature optimization. The victim models will re-train on the poisoned graph g' normally, and we take the predictions from the poisoned victim model for final evaluation.
5 Experiments
5.1 Experimental settings
Experiments are conducted on three real-world datasets namely Pokec-z, Pokec-n, and DBLP. Both Pokec-z and Pokec-n are subgraphs sampled from Pokec,
Datasets.
Table I:
Dataset statisties
of the largest online social networks in Slovakia, according to the provinces of users (3). Each node in these graphs represents a user, while each edge represents an unidirectional following relationship. The datasets provide node attributes including age, gender, and hobbies, and the classification task is predict the working fields of users. DBLP is coauthor network dataset (II), where each node represents an author and two authors will be connected if they publish least one paper together. The node features are constructed based on the words se- lected from the corresponding author's 's published papers. The final classification task is to predict the research area of the authors. The detailed dataset statistics are summarized in Table
Dataset
Pokec-z
Pokec-n
DBLP
nodes # of edges
67,796
66,569
20,111
617.958
517,047
57,508
feature dim.
276
265
2,530
# of labeled nodes
10.262
8,797
3,196
Victim models. As a gray-box attack method, we target multiple classical GNNs as victim models, including GCN [4, GraphSAGE [10], APPNP [1],, and SGC [39]. We also include three well- established fairness-aware GNNs - FairGNN (5) Fair VGNN (38], and FairSIN 40 as our selected
victim models. The details of these victim models will be elaborated in Appendix
Baselines.
Depending on the attack goals, we mainly consider the following two kinds of graph at- tack methods our baselines, including 1) Utility attack: AFGSM (36), TDGIA (7) and G² A2C
[2]. and 2) Fairness attack: FA-GNN [1I, FATE 133, and G-FairAttack [41). The details of these baselines will be further introduced in Appendix
Implementation details. As shown in Table T only part of the nodes have the label information, and we randomly select 50%, 25%, and 25% labeled nodes as the training set, validation set, and test set, respectively. In line with the prior work, [II, we choose region as the sensitive attribute for Pokec-z. and Pokec-n, and gender for DBLP. For all victim models, we employ a two-layer GCN model as the surrogate model. Due to space limitations, please refer to Appendix G for more reproducibility details.
7

---

Table 2: Attack performance of NIFA different victim GNN models. The results are reported in percentage (%)). We bold the results when NIFA successfully deteriorates the faimesss of victim GNN models (smaller ASp and A no indicate better faimess, and we aim to maximize the fairness metrics for a fairesss attack).
Pakee-a
Pokee-n
DBLP
Accuracy
Agr
Ayo
Accuracy
Agr
Ago
Accuncy
Age
Ago
GCN
beiure
70.50a0.30
71.22.10:28
17.36:1.16
7.13.1121
15,59:1.08
5,1011.28
70.9210..6
20.1260.37
10.10:2.10
0.88.00.2
2.4.11.37
9,85=197
93,3741.48
95.88.1.61
13,49:283
3.84.0.34
382
191.00.75
GraphSAGE
before
60.79:00:2
8.29:0084
34611.12
68.7780.34
165=133
2.34:1004
96.5810029
1.27::100
2.78:091
anter
7000++1.25
6,20+1.63
4,20++,77
68.93-1199
3.22-188
3.56+1.91
93.92+0.74
10.16+2.24
16,65-330
APPNP
before
69,7910.42
6.83.1.22
5,0711.226
68.7310.61
3.391022
3.711025
96.5810.38
1.98
2.2011.08
after
69.12:0.70
18,4+1141
16.85=1.50
67.0=0076
1344-33.2
13.52=3.56
92,46+0.94
13.88+3.00
20.30=4.25
SGC
befure
69.0910.999
7.28.1.50
5451144
66.9511.69
2.74..0.55
3.21
96.5310.48
1.7011.26
3.111124
atter
67.83:50.70
17.65+11001
16.09:1.006
66.7261.21
10.59:2.40
10.672261
92.56+1.09
13,88-3.37
20.25:-4.44
FairGNN
before 68/75&1.12
1.5140.47
09.41:0.06
144:0035
2.5240.57
98.1281.23
1.9520.99
1.91
after
69.38+22.07
5.71+2.52
4.22+1.89
09:97-00.22
6.13-5881
6.33+55.77
92,56++149
5.89-2.52
10.48-382
FaiN
before
after 67.65.1.38
68.5710.45
11.01:22.79
3.79.00.51
9.28122.87
2.59100.59
67.77.11000
65.7411.42
1.1:
1.90.1223
3.6811.56
3.10.1.20
91,5611.13
95.1810.54
7.961
1,9010,52
1357
2.9
FairSIN
before
after
67.33:20:22
66 66.55-+0.44
9,48+22.62
1.73+11499
10.39+1.06
2.61#1.44
66 20-00-1112
67. 08:3000030
11,82
0.39=0089
14.58-0.25
2.40+1.02
94.72+0.62
92.46++0.32
10.90+2.122
0:23:00155
2365+7.77
0.45=0.16
Table 3: Accuracy and Fairness performance of attack launched by the different attackers. The results are reported in percentage (%). The best attack performance on fairness is bolded.
Pokec-z
Pokec-n
DBLP
Accuracy
Agp
Ago
Accuracy
Asp
A,o
Accuracy
Asp
Ago
Clean
71,2240.28
7,13+1.31
5,10+1,228
70:92=0066
0,88+0062
2,44-1.37
95 18-6111.61
3,84+00.34
1.91+0075
Unility attacks on GNVs
AFGSM
67.0110.24
3,07=1667
3,4520,22
68.21:20.33
5,35:20.15
5.6800114
95.38=0030
5,4413.44
2.78:00.41
TDGIA
62:20:0.04
1.66=0.16
0.77+0.10
63.57+0.08
7.28++0.35
695-0.34
93:42=0.29
0.93++0.00
182+0087
GPA2C 39.4140.94
6.89=091
6.11::0.48
14.30+11,71
2,23++1140 1.0
3,76 1.04
86.28
4.21
3,80=00.42
Fairess atiocks on GNNNss
FA-GNN
6.62+1.21
8.7+11228
70.80+0.77
2.64+0.776
3,45-0.54
95.48-0048
3.32+1166
8,74+1.22 1,
FATE
94.87-0.41
3.62.:1.49
2.12:1101
G-FairAttack
95.12:10.38
6.80.10.599
1.
NIFA
70.50+0.30
17.36+1166
15.59-1.08
70:1240.77
10.10+2.10
9.85 1.97
93.37-1.48
13.49+2.83
20.33++3.82
5.2
Main attack performance
To comprehensively evaluate NIFA's effectiveness, we employ multiple mainstream GNNs includ- ing GCN, GraphSAGE, APPNP, and SGC, besides three classical faimess- GNNs namely FairGNN, FairVGNN, and FairSIN as our victim models. We record the average accuracy, AsP and AgO before and after conducting our poisoning attack on the victim models five times. The experimental results are reported in Table and we can have the following observations:
The proposed attack demonstrates consistent effectiveness on all datasets with different main- stream GNNs as victim models. For instance, the Asp and AEO of GCN on Pokec-z increase significantly from 7.13%, 5.10% to 17.36% and 15.59% respectively. Such observation success- fully reveals the vulnerability of GNN fairness under our node injection- based attacks.
On three fairness-aware models, FairGNN, FairVGNN, and FairSIN, NIFA still causes noticeable fairness impacts. For example, the AgO of FairVGNN on Pokec-z increases from 2.59% to 9.28%, a nearly fourfold increase. It indicates that even fairness-aware GNN models are also vulnerable to our attack, highlighting the urgency of proposing more robust fairness mechanisms.
Instead of sacrificing the utility of victim GNNs for better faimess attack results, all victim models' accuracy is only slightly impacted on all datasets, which illustrates the distinction between fairness attacks and utility attacks, and underscores NIFA's 's deceptive nature for administrators.
5.3 Comparison with other attack Models
In this section, we aim to compare NIFA with several competitors on graph attacks. Specifically, we choose six well-established attackers on either utility or fairness as our baselines, including
AFGSM (36], TDGIA [7). A2C [12), FA-GNN [I], FATE [3), and G-FairAttack [1]] For
all baselines, the victim model is set as GCN, and the numbers of injected nodes or modified edges
are set to be the same ours for fair comparison. Note that, both FATE and G-FairAttack fail
8

---

to deploy on Pokec-z and Pokec-n due to scalability issue Results after repeating five times are shown in T
can be seen that NIFA consistently achieves the state-of-the-art fairness attack performance on three datasets. The reasons might be two-fold: 1) the utility attack methods are mainly designed to impact the accuracy of victim models, while overlooking the fairness objectives. 2) As pioneering works in fairness attacks on GNNs, all baselines on fairness attacks need modify the original graph, such as adding or removing some edges or modifying features of real nodes. For deceptive- ness consideration, their modifications are usually constrained by small budget. However, NIFA introduces new nodes into the original graph through node injection and can optimize the injected nodes in a relatively larger feature space. Such superiority of node injection attack helps NIFA have a greater impact on the original graph from the feature perspectives.
5.4 Ablation study
In this part, we conduct ablation experiments to prove the effectiveness of the uncertainty- maximization principle, homophily-increeae principle, and iterative training strategy, respec- tively. In detail, we consider the following three variants of NIFA. 1) NIFA-U: the uncertainty- maximization principle is removed, and we randomly choose targeted nodes from the labeled nodes. 2) NIFA-H: we still choose real nodes with the top k% model uncertainty as the targeted nodes, but the nomophily-incresn nodes from different sensitive groups simultaneously. 3) NIFA-I: we remove the iterative training strategy here, which means that the surrogate model trained on the clean graph in advance, and the feature optimization process will only involve the training process of injected feature matrix. For all variants, we set GCN as the victim model.
principle is removed, i.e. each injected node may connect with targeted
The results are reported in Figure where we can have the following servations. Firstly, after removing the umcertanty-mmximizatiin maximization prin- ciple (NIFA-U), the fairness attack performance consistently decreases on three datasets. This is ex- pected since the concept of uncer- tainty helps NIFA find more vulnera- ble nodes, thus improving the attack effectiveness. Secondly, after removing the homophily- -nnereas principle (NIFA-H), the attack per- formance drops obviously, which verifies the homophily- -ratio is crucial in GNN fairness. Finally, without iterative training during feature optimization (NIFA-I), the attack performance decreases slightly on all datasets. The main reason is that the iterative training strategy could help NIFA to have better robustness to dynamic victim models.
Clea
NEFA-U
NIA-H
NIV-I
NIAA
20
Acanncy (%)
10.
Poknes
Pokoon
DRI
Pokcoet Pokase
DREP
Prlcoosr
Pokass
DRI
(a)
Accuracy
(6) Agp
(c) Ago
Figure 2: Ablation study of each madule in NIFA
Defense discussion to fairness attacks on GNNs
As previously emphasized, our intrinsic aim is to unveil the vulnerabilitties of existing GNN models in terms of faireess, thereby inspiring related defense research. In fact, as an
ACC
Ayo
80
Accuracy (%)
Agr 4no (%)
emerging field that is just beginning to be explored, defense strategies against GNN fairness attacks are relatively scarce. However, we still can summarize several key insights from
50
NIFA for further careful study:
Reliable training nodes. One key assumption in NIFA is that the nodes with high model uncertainty will be much easier to be attacked, which can also be supported by the ablation study in Section 5.44 In this way, administrators can pay more atten- tion to these nodes and their abnormal neighbors for defense
0.0
0.1
0.2
0.3
0.4
0.5
0.6
Figure 3: Defense performance on Pokec-z with masking y training nodes with the highest uncertainty
OOn Pokec-z and Pokec-n datasets, FATE reports OOM errors and G-FairAttack fails to complete the attack within three days. More scalability analysis will be given in Appendix H.4

---

purposes. For example, engineers can pre-train a model to detect the abnormal nodes or edges in advance, especially those that emerged recently in the training data, and weaken their impacts on the model by randomly masking these nodes or edges in the input graph or decreasing their weights in the message propagation during the training of GNNs.
To verify our assumption, we conduct simple experiment by removing a proportion of nodes (17) with the highest uncertainty U from supervision signals after the attack. Similarly, GCN [I0] is employed as the victim model and we gradually tune 1) from O to 0.6 with step 0.1, where 7/ 0 means no defense is involved. The performance of NIFA on the Pokec-z dataset with different n is illustrated in Figure [ It can be seen that, since NIFA mainly focuses on attacking nodes with high uncertainty, after masking a part of these nodes during the training stage, the fairness attack performance of NIFA gradually decreases with a small fluctuation in accuracy. However, it is worth noting that although such an intuitive strategy can defend the attack from NIFA to some extent, there is still obvious fairness deterioration compared with the performance of clean GCN in Table 2 (Agr=7.13, A Ag)=5.10). More dedicated and effective defense mechanisms in the future are still in demand.
Strengthen the connections among groups. One main reason behind the success of NIFA in fair- ness attack is the guidance of the homophily-inerease principle during node injection. The ablation study in Appendix(5.4]am
provides empirical evidence for this claim. As we analyze in Section 4.2 NIFA will lead to the increase of node-level homophily-ratio which means more sensitive-relater information will be aggregated and enlarged within the group. Given this, we believe that an effee- tive defensive strategy is to strengthen the information propagation among different sensitive groups, and fairness issues.
thus preventing the risks of information cocoons 22 25
Fairness auditing. last, we find that a crucial assumption in NIFA and other research [3 that GNN model administrators will only audit the utility metries of the models, such as accuracy or Fl-scores. Therefore, as long as attackers can ensure that the model utility is not affected exces- sively, it will be hard for administrators to realize the attack. Consequently, we strongly suggest that model administrators should also incorporate fairness-relates metrics into their monitoring scopes, especially before model deployment or during the beta testing phase, thus, mitigating the potential broader negative impacts and social risks. For instance, if an updated GNN model suddenly demon- strates obvious fairness deterioration compared with the previous versions, the model administrators should be careful about the potential fairness attacks. However, the challenge of this approach mainly lies in the diverse definitions of fairness, such as group fairness
23 individual fairness
(6). etc., and group faimess based on different sensitive attributes (5) 38 or structures [21 22) may further lead to different definitions. Therefore, model administrators might need prior knowledge or expertise to determine what kinds of fairness metrics to be included in their monitoring scopes.
7 Conclusion
In this work, we aim to examine the vulnerability of GNN fairness under adversarial attacks, thus mitigating the potential risks when applying GNNs in the real world. All existing fairesss attacks on GNNs require modifying the connectivity or features of existing nodes, which is typically infeasible in reality. To this end, we propose a node injection- poisoning attack namely NIFA. In detail, NIFA first proposes two novel principles for node injection operations and then designs multiple objective functions to guide the feature optimization of injected nodes. Extensive experiments on three datasets demonstrate that NIFA can effectively attack most mainstream GNNs and fairness- aware GNNs with an unnoticeable perturbation rate and utility degradation. Our work highlights the vulnerabilities of GNNs to node injection- based fairness attacks and sheds light on future research about robust fair GNNs and defensive mechanisms for potential faimeess attacks.
Limitations. Firstly, NIFA is still under the settings of gray-box attacks, which requires accessibil- ity to the labels and sensitive attributes. We acknowledge that such information may not always be available and we leave the extensions to the more realistic black-box attack settings as future work. Moreover, although we present some insights on the defense strategies of GNN fairness, more ef- fective defense measures are still under-explored. calling for more future research efforts. At last, currently we only focus on fairnsss based on sensitive attributes, while neglecting the fairness based on graph structures. Since different fairness may stem from different sources, we leave this as our future work.
10

---

Acknowledgement
The work is supported by the National Natural Science Foundation of China (No.62172174). The authors would also like to thank Xiran Song and Jianxun Lian for their suggestions and contributions.
References
[1] C. Agarwal, H. Lakkaraju. and M. Zitnik. Towards a unified framework for fair and stable graph representation learning. In Proceedings of the Thirty-eeventh Conference on Uncer- tainty in Artificial Intelligence, UAI 2021, Virtual Event, July 27-30, 2021, volume 161 of Proceedings of Machine Learning Research, pages 2114-2124. AUAI Press, 2021.
[2] A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann. Netgan: Generating graphs via ran- dom walks. In Proceedings of the Thirty-fiith International Conference on Machine Learning, 2018, pages 610-619. PMLR, 2018.
[3] A. Chhabra, P. Li, P. Mohapatra, and H. Liu. Robust fair clustering: novel fairness attack and defense framework. In Proceedings of the Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net 2023.
[4] M. Coşkun and M. Koyutürk. Node similarity-based graph convolution for link prediction in biological networks. Bioinformatics. 37(23):4501-4500 2021.
[5] E. Dai and Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the Fourteenth ACM International Conference on Web Search and Data Mining, WSDM 2021, Virtual Event, Israel, March 8-12, 2021, pages
ACM, 2021.
[6] Y. Dong, Kang, H. Tong, and J. Li. Individual fairness for graph neural networks: A ranking based approach. In Proceedings of the Twenty-seventh ACM SIGKDD Conference Knowl- edge Discovery and Data Mining, KDD 2021, Virtual Event, Singapore, August 14-18, 2021, page 300-310, New York, NY, USA, 2021. ACM.
[7] Y. Dong, N. Liu, B. Jalaian, and J. Li. EDITS: modeling and mitigating data bias for graph neural networks. In Proceedings of the Thirty-first ACM Web Conference, WWW 2022, Virtual Event, Lyon, France, April 25-29, 2022, pages 1259-1269, ACM, 2022.
[8] L. Du, X. Shi, Q. Fu, X. Ma, H. Liu, S. Han, and D. Zhang. Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceedings of the Thirty- first ACM Web Conference, WWW 2022, Virtual Event, Lyon, France, April 25-29, 2022, page ACM, 2022.
[9] Y. Gal and Z. Ghahramani. Dropout as bayesian approximation: Representing model un- certainty in deep learning. In Proceedings of the Thirty-third International Conference on Machine Learning, ICML 2016, pages 1050-1059. PMLR, 2016
[10] W. L. Hamilton, Z. Ying, and Leskovec. Inductive representation learning on large graphs. In Proceedings of Advances in Neural Information Processing Systems 30: Annual Confer- ence on Neural Information Processing Systems 2017, NeurIPS 2017, Long Beuch, CA, USA, December 4-9, 2017, pages 1034-1034, 2017.
[11] H. Hussain, M. Cao, S. Sikdar, D. Helic, E. Lex, M. Strohmaier, and R. Kern. Adversarial inter-group link injection degrades the fairness of graph neural networks. In Proceedings of the 2022 IEEE International Conference on Data Mining, ICDM 2022, Orlando, FL, USA, November 28- Dec. 1, 2022, pages 975-980. IEEE, 2022.
[12] M. Ju, Y. Fan, C. Zhang, and Y. Ye. Let graph be the go board: gradient-free node injection at- tack for graph neural networks via reinforcement learning. Proceedings of the Thirty-seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Washington, DC, USA, February 7-14, 2023, pages
AAAI Press, 2023.
[13] J. Kang, Y. Xia, R. Maciejewski, J. Luo, and H. Tong. Deceptive faimess attacks on graphs via meta learning. In Proceedings of the Twelfth International Conference on Learning Represen- tations, ICLR 2024, Vienna Austria, May 7-11, 2024. OpenReview.net, 2024.
[14] T. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the Fifth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017. OpenReview.net, 2017.
11

---

[15] J. Klicpera, A. Bojchevski, and S. Günnemann. Predict then propagate: Graph neural net- works meet personalized pagerank. In Proceedings of the Seventh International Conference on Learning Representations, ICLR 2019, New Orleans, IA, USA, May 6-9, 2019. OpenRe- view.net, 2019.
[16] Y. Li, H. Chen. Z. Fu, Y. Ge, and Y. Zhang, User-oriented faireess in recommendation. In Proceedings of the Thirtieth ACM Web Conference, WWW 2021, Virtual Event, Ljubljana, Slovenia, April 19-23, 2021, pages 624 632. ACM, 2021.
[17] H. Ling, Z. Jiang, Y. Luo, S. Ji, and N. Zou. Learning fair graph representations via automated data augmentations. In Proceedings of the Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[18] X. Liu, W. Jin, Y. Ma. Y. Li, H. Liu, Y. Wang, M. Yan, and Tang. Elastic graph neural networks. In Proceedings of the Thirty-eigth International Conference on Machine Learning, ICML 2021, Virtual Event, July 18-24, 2021, pages 6837-6849, PMLR, 2021.
[19] X. Liu, S. Si, J. Zhu, Y. Li, and C. Hsich. A unified framework for data poisoning attack to graph-based semi-supervised learning. In Proceedings of Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, Vancouver, BC, Canada, December 8-14, 2019, pages 9777-9787, 2019.
[20] Y. Liu, X. Ao, F. Feng, and Q. He. UD-GNN: uncer debiased training on semi- homophilous graphs. In Proceedings of the Twenty-eighth ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022, Washington, DC, USA, August 14-18, 2022, pages 1131-1140. ACM, 2022.
[21] Z. Liu, T. Nguyen, and Y. Fang. On generalized degree fairness in graph neural networks. In Proceedings of the Thirty-Sevntth AAAI Conference on Artificial Intelligence, AAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 4525-4533. AAAI Press, 2023.
[22] Z. Luo, H. Huang, J. Lian, X. Song, X. Xie, and H. Jin. Cross-links matter for link prediction: Rethinking the debiased gnn from a data perspective. In Proceedings of Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10-16, 2023, 2023.
[23] Z. Luo, J. Lian, H. Huang, H. Jin, and X. Xie. Ada-gnn: Adapting to local patterns for improv- ing graph neural networks. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM 2022, Virtual Event / Tempe, AZ, USA, February 21-25, 2022, pages 638-647, ACM, 2022.
[24] Y. Ma. S. Wang, T. Derr, L. Wu, and J. Tang. Graph adversarial attack via rewiring. In Proceedings of the Twenty-seventh ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD 2021. Virtual Event, Singapore, August 14-18, 2021, pages 1161-1169. ACM, 2021.
[25] F. Masrour, T. Wilson, H. Yan, P. Tan, and A. Esfahanian. Bursting the filter bubble: Fairness- aware network link prediction. In Proceedings of the fhirty-fourth AAAI Conference Artifi- cial Intelligence, AAAI 2020, New York, NY, USA, February 7-12, 2020, pages 841-848. AAAI Press, 2020.
[26] N. Mchrabi, M. Naveed, F. Morstatter, and A. Galstyan. Exacerbating algorithmic bias through fairness attacks. In Proceedings of the Thirty-fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 8930-8933 AAAI Press, 2021.
[27] B. Rozemberezki, C. T. Hoyt, A. Gogleva, P. Grabowski, K. Karis, A. Lamov, A. Nikolov, Nilsson, M. Ughetto, Y. Wang, T. Derr, and B. M. Gyori. Chemicalx: A deep learning library for drug pair scoring. In Proceedings of the Twenty-eighth ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022, Washington, DC. USA, August 14-18, 2022, pages 3819-3828. ACM, 2022.
[28] U. Singer and K. Radinsky. Eqgan: Equalized node opportunity in graphs. In Proceedings of the Thirty-sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Virtual Event, Febru- ary 22- March 1, 2022, pages 8333-8341. AAAI Press, 2022.
[29] D. Solans, B. Biggio, and C. Castillo. Poisoning attacks on algorithmic fairness. In Proceed- ings of the Machine Learning and Knowledge Discovery in Databases- - EEuropean Conference, ECML. PKDD 2020, Ghent, Belgium, September 14-18, 18, 2020, pages 162-177. Springer, 2020
12

---

[30] X. Song, J. Lian, H. Huang. Z. Luo, W. Zhou, X. Lin, M. Wu, C. Li, X. Xie, and H. Jin. xgen: An extreme graph convolutional network for large-scale social link prediction. In Proceedings of the Thirty-second ACM Web Conference, WWW 2023, Austin, Texas, USA, April 30 May 4, 2023, pages 349-359. ACM, 2023.
[31] X. Song, J. Lian, H. Huang, M. Wu, H. Jin, and X. Xie. Friend recommendations with self- rescaling graph neural networks. In Proceedings of the Twenty-eighth ACM SIGKDD Confer- ence on Knowledge Discovery and Data Mining, KDD 2022, Washington, DC, USA, August 14-18, 2022, pages 3909-3919, 2022.
[32] Y. Sun, S. Wang, X. Tang, T. Hsieh, and V. G. Honavar. Adversarial attacks graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of the Twenty-ninth ACM Web Conference, WWW 2020, Taipei, Taiwan, April 20-24, 2020, pages 673-683. ACM / IW3C2, 2020.
[33] X. Tang, H. Yao, Y. Sun, Y. Wang, J. Tang, C. C. Aggarwal, P. Mitra, and S. Wang. Investigat- ing and mitigating degree-related biases in graph convoltuional networks. In Proceedings of the Twenty-ninth ACM International Conference on Information and Knowledge Management, CIKM 2020, Virtual Event, Ireland, October 19-23, 2020, pages 1435-1444. ACM, 2020.
[34] S. Tao, Q. Cao, H. Shen, J. Huang, Y. Wu, and X. Cheng. Single node injection attack against graph neural networks. In Proceedings of the Thirtieth ACM International Conference on Information and Knowledge Management, CIKM 2021, Virtual Event, Queensland, Australia, November 1-5, 2021, pages 1794-1803. ACM, 2021.
[35] L. Van der Maaten and G. Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(1), 2008
[36] J. Wang, M. Luo, F. Suya, J. Li, Z. Yang, and Q Zheng. Scalable attack on graph data by injecting vicious nodes. Data Min. Knowl. Discov., 3465):363--1389, 2020.
[37] N. Wang, L. Lin, J. Li, and H. Wang. Unbiased graph embedding with biased graph obser- vations. In Proceedings of the Thirty-first ACM Web Conference, WWW 2022, Virtual Event, Lyon, France, April 25-29, 2022, pages 1423-1433. ACM, 2022.
[38] Y. Wang, Y. Zhao, Y. Dong, H. Chen, J. Li, and T. Derr. Improving faimess in graph neural networks via mitigating sensitive attribute leakage. In Proceedings of the Twenty-eighth ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2022, Washington, DC, USA, August 14-18, 2022, pages 1938-1948. ACM, 2022.
[39] F. Wu, A. H. S. Jr., T. Zhang, C. Fifty, T. Yu, and K. Q. Weinberger. Simplifying graph convolutional networks. Proceedings of the Thirty-sixth International Conference on Ma- chine Learning, ICML 2019, Long Beach, California, USA, Jun 9-15, 2019, pages 6861-6871. PMLR, 2019.
[40] C. Yang, J. Liu,, Y. Yan, and C. Shi. Fairsin: Achieving fairness in graph neural networks through sensitive information neutralization. In Proceedings of the Thirly-eighth AAAI Confer- ence on Artificial Intelligence, AAAI 2024, Vancouver, Canada, February 20-27, 2024, pages 9241-9249. AAAI Press, 2024.
[41] B. Zhang, Y. Dong, C. Chen, Y. Zhu, M. Luo, and J. Li. Adversarial attacks on fairness of graph neural networks. In Proceedings of the Twelfth International Conference on Learning Representations, ICLR 2024, Vienna Austria, May 7-11, 2024. OpenReview.net, 2024.
[42] H. Zhang, B. Wu, X. Yuan, S. Pan, H. Tong, and J. Pei. Trustworthy graph neural networks: Aspects, methods, and trends. Proc. IEEE, 11( 2024.
[43] X. Zhang, P. Bao, and S. Pan. Maximizing malicious influence in node injection attack. In Pro- ceedings of the Seventeenth ACM International Conference on Web Search and Data Mining, WSDM 2024, Merida, Mexico, March 4-8, 2024, pages 958-966. ACM, 2024.
[44] X. Zhang and M. Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. Proceedings of Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, Virtual, Decem- ber 6-12, 2020, 2020.
[45] H. 7hu, G. Fu, 7. Guo, Z. Zhang, T. Xiao, and S. Wang. Fairness-aware message passing for graph neural networks. CoRR, abs/2306.1 1132, 2023.
13

---

[46] Y. Zhu, J. Li, L. Chen, and Z. Zheng. The devil is in the data: Learning fair graph neural net- works via partial knowledge distillation. In Proceedings of the Seventeenth ACM International Conference Web Search and Data Mining, WSDM 2024, Merida, Mexico, March 4-8, 2024, pages 1012-1021. ACM, 2024.
[47] X. 7ou, Q. Zheng. Y. Dong, X. Guan, E. Kharlamov, J. Lu, and J. Tang. TDGIA: effective in- jection attacks on graph neural networks. In Proceedings of the Twenty-seventh ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021, Virtual Event, Singapore, August 14-18, 2021, pages 2461-2471. ACM, 2021.
[48] D. Zügner, A. Akbarnejad, and S. Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the Twenty-fourth ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 2847-2856. ACM, 2018.
14

---

A Ethical consideration
In this study, propose fairness attack towards GNN models via node injections. It is worth noting that the main purpose of this work is to reveal the vulnerability of current GNN models to faimess attacks, thereby inspiring and motivating both industrial and academic researchers to pay more attention to future potential attacks and enhancing the robustness of GNN fairness. We acknowledge the potential for our research be misused or exploited by malicious hackers and to have real-world implications or even harm. Therefore, we will open-source our code under the CC-BY-NC-ND license" in the future, which means that the associated code cannot be used for any commercial purposes, and no derivatives or adaptations of the work are permitted. Additionally, we discuss some feasible defense mechanisms in Section [ which we believe can some extent mitigate the fairness attacks proposed in our work and hopefully inspire future faimess defenses.
B Attack settings
In this section, we would like explicitly introduce our attack settings from the following aspects:
Attack stage. Attacks can be categorized into two types according to the time when the attacks take place [42]: poisoning attack and evasion attack. Poisoning attacks occur at the training phase of victim models, which will lead to poisoned models. In contrast, evasion attacks target the inference phase, and can not affect the model parameters. In this work, NIFA belongs to the poisoning attacks.
Attacker's knowledge. Generally, according to the knowledge of attackers, the attack methods can be categorized into three types including white-box attack, black-box attack and gray-box attack 42]. As we introduced in Section 3 we propose NIFA within the gray-box attack settings make our attack more practical in the real world, which is also consistent with multiple prior research Different from white-box attacks and black-box attacks, gray-box attacks mean that attackers can only access the training data, including the input graph G, the labels 2 and the sensitive attribute s of each node. Note that, the model architecture and parameters are invisible to attackers under the gray-box attack settings, which leads to that the attackers need to train a surrogate model in advance to assess the effectiveness of their proposed attacks.
on GNN attacks [T] 32
Attacker's capability, One merit of NIFA is that there is no need for the attackers to have the authority to modify the existing graph structure, such as adding or deleting edges between existing real nodes, or modifying the existing real nodes' features. In contrast, NIFA injects V malicious nodes and poisons the graph G into G' to launch an attack, which much more practical for the attackers in the real world. For example, in social networks the attackers only need to sign up multiple zombie accounts and interact with real accounts. Note that, different from some injection- based attack [12 32). NIFA will not modify the training set and true node label set y, as such operations are typically infeasible in the real world. The intrinsic idea of NIFA is to impact the GNN training process through massage propagation on a poisoned graph.
Within the gray-box attack settings, we also assume that the attackers have sufficient computational resources and budget to train a surrogate model and have access to the real graph as input. Similar to prior attack methods (32] attackers are also required injected nodes and their degrees respectively to make NIFA deceptive and unnoticeable.
thresholds b and d for the number of
C Proof
Lemma 1. For target node u that will connect with injected nodes, proposed node injection strategy will lead to the increase of node-level homophily-ratio H..
Proof. Given target node with k neighbors that have the same sensitive attribute with u, we simply assume it will connect with n injected nodes after node injection. Since all injected nodes in our proposed node injection belong to the same sensitive attribute as target node u, then the node-level homophily-ratio after node injection H', is:
k + n
k
H'd
H..
(16)
W +n
W
nd/4.0/
15

---

Algorithm Trriiiin process of NIFA
Input: Graph G. Hyper-parameters: node budget b, edge budget d, and [3, learning rates 7 ?.
Output: Poisoned graph G Initialize Bayesian GNN's parameter 0g. surrogate model's parameter 0g and injected nodes'
feature matrix x,.
2: Train the Bayesian GNN by Eq. (8) and Eq.
3: Estimate the node uncertainty U in the original graph & by Eq. (1O) and select the target nodes.
4: Connect the injected nodes with target nodes according to the homophily- inccresee principle.
5: for iter = 1 to mar iter do
6: for slep = to mar slep do
7: Compute cross-entropy loss ICc for S by Eq. 11
8: Update surrogate model: 0g + Os + 7 Vog LCE- end for
9:
10: for step= = to mar _step
mar_step do
11:
Compute L by Eq. (55
12: Update injected feature: X, + X tg VX
13: end for
14: Clamp X, between min and max of X.
15: end for
16: if X is discrete then
17: Round X, into integer.
18: end if
return G'
Such inequality holds true when [Wa]] 2 k.
D
Implementation algorithm
Due to space limitation, here we provide the complete training process of NIFA in Algorithm The training process and evaluation process are also literally described in Section 4.4
E
Additional descriptions on victim models
In this part, we give introduction the victim models used in experiment.
GCN 10 Borrowing the concept of convolution from the computer vision domain, GCN em- ploys convolution operation on the graph from spectral perspective to learn the node embeddings.
Given the potential neighborhood explosion issues in GCN, GraphS sam- ples a fixed number of neighbors at each layer during neighborhood aggregation, which greatly improves the training efficiency.
GraphSAGE 14
Inspired by PageRank, APPNP decouples the prediction and propagation in the training process, which resolves inherent limited-range issues in message-passing models without introducing any additional parameters.
APPNP 15
SGC B3: SGC empirically finds the redundancy of non lon-linear activation function, and achieves comparable performance with much higher efficiency.
FairGNN [5] Through proposing sensitive attribute estimator and an adversarial learning mod- ule, FairGNN maintains high classification accuracy while reducing unfairness scenarios with limited sensitive attribute information.
FGNN 38 FairVGNN discovers the leakage of sensitive information during information propagation of GNN models, and generates fair node features by automatically identifying and features.
masking
Instead filtering out sensitive-related information for fairness, FairSIN deploys a novel sensitive information neutralization mechanism. Specifically, FairSIN will learn to intro- duce additional fairness facilitating features (F3) during message propagation to neutralize sensi- tive information while providing more non-sensitive information.
FairSIN 40
16

---

F Additional descriptions on baselines
In this section, we will introduce more details about the baselines used in our experiments.
AFGSM [3]] As a node injection-based attack, AFGSM designs an approximation strategy to linearize the victim model and then generates adversarial perturbation efficiently. In general, AFGSM is scalable to much larger graphs.
TDGIA 47
Aiming at attacking the model performance, TDGIA first introduces a topological edge selection strategy to select targeted nodes for node injection, and then generate injected features through smooth feature optimization.
Similar NIPA (32, A2A2C also proposes a node injection attack through inforcement learning- - Actor Critic. Specifically, G² A2C devises three core modules including Node Generator, Edge Sampler, Value Predictor to model the full process of node injection.
G2 [2]:
FA-GNN [II: To the best of our knowledge, FA-GNN is the first work to conduct fairness attack on GNNs. In detail, FA-GNN empirically discovers several edge injection strategies, which could impact the GNN fairness with slight utility compromise.
FATE 13: FATE is meta-learming- baase fairness attack framework for GNNs. To be concrete, FATE formulates the fairness attacks as bi-level optimization problem, where the lower-level op- timization guarantees the deceptiveness of an attack while the upper-level optimization is designed maximize the bias functions.
G-FairAttack 4 As poisoning fairness attack, G-FairAttack consists of two modules, in- cluding surrogate loss function and following constrained optimization for deceptiveness. Like FATE and FA-GNN, G-FairAttack also belongs graph modification attacks, i.e., the original link structure between existing nodes will be modified during the attack.
G Reproducibility details
The implementation details are first provided in Section 5. in the original paper. Here would like to provide more implementation details from the following four aspects:
Environment. All experiments are conducted on server with Intel(R) Xeon(R) Gold 5117 CPU @ 2.00GHz and 32 GB Tesla V100 GPU. The experimental environment based on Ubuntu 1 18.04 with CUDA 11.0, and our implementation is based on Python 3.8 with PyTorch 1.12.1 and Deep Graph Library (DGL.) 1.1.0.
Victim models. For all victim models, we set the learning rate as 0,001, and the hidden dimension as 128 after careful tuning. For most victim models, the dropout ratio set to by default. Specifically, for GCN and GraphSAGE, the layer number is set to 2, and we employ mean pooling aggregation for GraphSAGE. For SGC, the hop-number & is set to 1. For APPNP, following the suggestions in the official paper, the teleport probability a is set as 0.2, and we set the iteration number is as 1 after careful tuning. For FairGNN, we employ the GAT as the backbone model, which shows better performance in the original paper, and set the dropout ratio as 0.5. The objective weights and B3 are set as 4 and 0.01, respectively. For FairVGNN, GCN is set be the backbone model, and we set the dropout ratio as 0.5. The prefix cutting threshold is searched from (0.01, 0.1, 1}. and the mask density a is 0.5. The epochs for the generator, discriminator, and classifier are selected from (5, 10) suggested in the official implementation. For FairSIN, we also utilize GCN as the backbone model, and we set the weight of neutralized feature å as 4 after tuning, and set the hidden dimension as 128 for a fair comparison. All learning rates involved in FairSIN are set to 0.001 after careful fine-tuning and other hyper-parameten are set according to the official implementations
Baselines details. For all baselines that involve graph structure manipulation, the numbers of in- jected nodes and edges on three datasets are made identical to the settings of our model for a fair comparison. For methods that only inject new nodes, such AFGSM, TDGIA and G2A2C, we require the number of injected nodes and average degree of injected nodes to the same as ours. For methods that require to modify the graph structure, such as FA-GNN, FATE and G-FairAttack, we set the number of modified edges to be the same with our injected edges, i.c. the added edges between injected nodes and original nodes. To be concrete, for the AFGSM, across all datasets,
17

---

we utilize the direct attack setting and allow the model to perturb node features. For TDGIA, the weights kn, and k2, which are used for calculating topological vulnerability are set to 0.9 and 0.1, respectively. For G2 A2C, the temperature of Gumbel-Softman is set to 1.0, the discount factor is set to 0.95, and the Adam optimizer utilized with a learning rate of 10 4 Furthermore, we adopt early stopping with a patience of three epochs. For FA-GNN, we utilize the DD strategy, which has the best attack performance in the original paper. For FATE, the perturbation mode is filp and the attack step is set to 3 as the official implementation suggested. For G-FairAttack, the proportion of candidate edges is set to 0.0001 for fast computation on our datasets, and we follow the default ppper-parameters. It is worth noting that,
settings in the official repository for other can be utilized as either an evasion attack or a poisoning attack according to the original paper, and follow the poisoning attack settings to be the same with NIFA.
Details for implementing NIFA. We employ a two- layer GCN model as the surrogate model, whose hid- den dimension is set to 128, and the dropout ratio set
Table Al: Hyper- paramee-sr statistics
to O. The learning rates for optimizing the surrogate model and injected features are both set to 0.001 after tuning. The sampling times T of the Bayesian Network is 20. The objective weights a and 3 for all datasets are searched from {0.005, 0.01, 0.02, 0.05, 0.1, 0.2) and {2, 4, 8, 16). respectively. The number of injected nodes is set to 1% of the number of labeled nodes in the original graph, and the degree of injected nodes d is set to be 50, 50, and 24 three datasets, respectively, which are the average node degrees in the original graph. As for the uncertainty threshold 1%, we search in a range of {0.1, 0.25, 0.5, 0.753. The hyper-parameter analysis will be further elaborated in Appendix H.3 The mar__ter and maz max__tep in Algorithm I and other proposed hyper-parameters for each dataset are summarized in Table Al
Notations
Pokee-z
Pokec-n
DBLP
0.01
0.01
0.1
4
4
8
b
102
87
32
50
50
24
0.5
0.5
0.5
maw step
50
50
50
max_iter
20
20
10
Table A2: Comparison of the statistics on the clean graph (Perturbation rate is 0.00) and the graphs poisoned by NIFA with different perturbation rates. For better illustration, we also provide the relative rate of change (AA) in the table.
Rel. Edge
Characteristic
Perturbation
Gini Coefficient
Assortativity
Power Law Exp.
Triangle Count
Distr. Entropy
Path Length
Rate
valuee
[A]
value
[A]
value
[4]]
value
[A]
value
[4]
value
[A]
0.00
0.5719
0,2108
1.6152
767,688
0
0.0259
4.5208
0.01
0.5696
0.41%
0,2100
0.40%
166103
0.30%
767,787
0.01%
0.0259
0.13%
4,5062
0.32%
Pokec-
0.02
0.5677
0.75%
0,2093
0.74%
1.6064
0.54%
767,917
0.03%
0.0259
0.24%
4,4951
0.57%
0.05
0.5627
1.61%
0.2071
1.79%
1.5967
1.15%
768,287
0.08%
0.0260
0.42%
4,4732
1.05%
0.00
0.5634
0.1978
0
1,6609
$31,590
0
0.0296
4.6365
0.01
0.5613
0.37%
0.1958
0.96%
1.6557
0.31%
531 311,695
0.02%
0.0296
0.08%
4.6215
0.32%
Pokeo-n
0.02
0.5595
0.68%
0.1939
1.96%
1.6513
0.58%
531,776
0.03%
0.0296
0.13%
4.6103
0.56%
0.05
0.5555
1.39%
0,1895
4.15%
1.6409
1.20%
$32,089
0.09%
0.0297
0.20%
4,5902
1.00%
0.00
0.4137
0.1335
2,0730
73,739
0
0.0820
6.4867
0.01
0.4137
0.01%
0.1316
1.44%
2.0618
0.54%
73.744
0.01%
0.0818
0.27%
6.3627
1.87%
DBLP
0.02
0.4148
0.27%
0.1304
2.32%
2.0528
0.98%
73.751
0.02%
0.0815
0.69%
6,2886
3.02%
0.05
0.4208
1.71%
0.1311
1.83%
2.0307
2.04%
73,774
0.05%
0.0801
2.34%
6.1789
4.72%
H
Additional experiments
H.1 In-depth analysis of the poisoned graph
As poisoning attack, it is crucial to ensure that after the attack, the poisoned graph's characteristics should remain similar that of the clean graph. Otherwise, administrators can easily notice the attack through abnormal graph structures or node features. To this end, we conduct an in-depth analysis of the poisoned graph by NIFA from the following two perspectives:
hhttss//eittub.com//iaa////EE
hutps///gthhbbcco//aaannnnnnciii FairtteehhhhhaaaaAtttttteaee
18

---

Structural analysis. Similar to prior work [2]22), we investigate several key graph characteristies in this section, including Gini Coefficient, Assortativity. Power Law Exponent, Triangle Count, Relative Edge Distribution Entropy and Characteristic Path Length, whose definitions and inplementations can be found h The graph statisties under different perturbation rates are shown Table A2 It can be concluded that: (1) Thanks to the low perturbation rate required by NIFA, the poisoned graphs share quite similar characteristics with clean graphs. Under most cases, the relative rate of change | is smaller than 1%, especially when the perturbation rate is small, (2) With the increase of perturbation rate, the poisoning attack becomes more obvious, which can be verified by the increased |A| on all graph structure statisties. This observation further supports the necessity of requesting a low perturbation rate for an attack. (3) Several key statistics showcase a consistent trend across the three datasets the perturbation rate increases. For example, with the increase in attack intensity, the degree assortativity consistently decreases on three datasets, indicating that there more connections between nodes with significantly different degrees due to the injection of malicious nodes. Similar observations can also be found in key statistics like Triangle Count, Gini Coefficient and Characteristic Path Length, which implies that these statisties can be potentially utilized for fairness attack defense and auditing.
Feature analysis. Besides graph struc- tural analysis, we also conduct experi- ments to analyze the nodes' features of the poisoned graph. In detail, after con- ducting fairness attacks through NIFA, for both labeled nodes in the real graph and injected nodes, we illustrate their features' visualization results based on I-SNE [35] in Figure AT Note that,
Pokes
Pokec
DBLP
Figure Al: T-SNE visualization of poisoned graph's node fea- tures
since the number of injected nodes is much smaller than that of the original labeled nodes, we slightly increase the scatter size of injected nodes for better visualization.
It can be seen that, 1) the feature layouts of Pokec-z and Pokec-n quite similar, since both datasets are sampled from the same social graph. 2) On all three datasets, the distributions of injected nodes by NIFA are relatively diverse, which have obvious patterns, and are hard to recognize from the original labeled nodes. Such observation further verifies the feature deceptiveness of NIFA.
H.2 Alternative analysis in node selection
During the node injection process, NIFA proposes an incertainty-maximizatte principle and selects target nodes with the highest model uncertainty score. In fact, besides estimating model uncer- tainty, there are other alternative meth- ods for finding vulnerable nodes. For example, TDGIA [47] introduces the concept of "topological vulnerability". and selects nodes with low degrees as target nodes. In this part. we also conduct experiments with selecting target nodes with the lowest degree as a variant of NIFA. The victim model is GCN.
Table A3: Attack performance (%) with different target node selection strategies. The best attack performance is bolded.
Pokec-z
Pokec-n
DELP
Agp
Ago
Asp
Axo
Agp
Ago
Clean
71.22
7.13
5.10
70.92
0.88
2.44
95.88
3.84
1.91
Degree
70:50
15.76
14.01
69.77
12.39
11.93
94.72
6.30
15.10
Uncortainty
70:50
15.59
20.33
The results are shown in Table A3 It can be seen that, degree-based node selection (denoted as "Degree") also achieves promising attack performance compared with NIFA (denoted as "Uncer- tainty"), which indicates that model uncertainty is not the only feasible criterion for target node selection. However, the degree-based selection may be ineffective when the graph is extremely dense and has few low-degree nodes, which deserves more careful study in the future.
H.3 Hyper-parameee analysis
To better understand the different roles of hyper-parameter in NIFA, we study the impact of o, 9, b, and & in this part where GCN is employed as the victim model.
19

---

The impact of a and B. As the weights of objective functions in Eq. ([5). the impacts of and / are illustrated in Fig- ure [A2 and Figure A33 respectively. For three datasets, they perform best at dif- ferent a and 3 values, indicating that the appropriate values of a and B depend on the datasets. In contrast, the accuracy remains relatively stable with changes in a and 8, which indicates that our attack is ffillty--riendly.
6 6
12
50
Figure A2: The impact of a on three datasets
a0c
Agp
6
70
45
20
The impact of node injection budget h. We illustrate the impact of the node injection budget in Figure A4] where the x-axis denotes the perturbation rate, ie. the proportion of 6 to the number of labeled nodes in the original graph. As expected, the increase of leads to bet- ter fairness attack performance in most cases with more obvious accuracy com- promise. Empirically, 0.01 will be near-optimal choice while being unno- ticeable.
Figure A3: The impact of B on three datasets
Age Polece
Priezea
80
30
DRIPP
202
10
16 001
0:2
2.00"
5.03
0.00
0:2
6.00
0.88
00L
0.22
Figure A4: The impact of perturbation rate three datasets
002
Age
App
95
The impact of uncertainty threshold
50
90
k. The impact of k is illustrated in Fig- ure AS where we tune k%
025
6.75
set {0.1, 0.25, 0.5, 0.75). It can be seen that all datasets show a similar preference for A% with an optimal value of 0.5. Intuitively, with a higher 1%, it hard for NIFA to attack the target nodes with low uncertainty, whereas, with lower k%, the impact of the attack will be limited by the insufficient number of targeted nodes.
Figure A5: The impact of k% on three datascts
H.4 Efficiency analysis
To evaluate the efficiency and scalabil- ity of NIFA, would like to pare the attack time cost and memory cost between NIFA and two competitive baselines including FATE [33 and G- FairAttack [1). To be fair, the attack budgets for the three models are set to be the same in advance. We report their memory cost and time cost for finishing poisoning attacks on Pokec-z, Pokec-n and DBLP in Table A4 The environment configurations for our experiments are introduced in Section G It can be seen that, NIFA can be successfully de- ployed on three datasets with acceptable time cost and memory cost. In contrast, both FATE and G-FairAttack face scalability issues, especially when facing large graphs such as Pokec-z and Pokec- As shown Table I both Pokec-z and Pokec-n have much more edges compared with DBLP, which causes FATE to report OOM errors and G-FairAttack to fail to finish the attack within 72 hours.
Table A4: Efficiency Analysis of NIFA
Pokee-z
Pokee-n
DELP
Time
Memury
Time
Memury
Time
Memocy
00M
0OM
87.13
32258
G-FairAttack
>-2h
7865
>-2h
7329 MB
93048
2445 MB
NIFA
137.04
4319 MB
167.07s
4213 MB
127.52
$829 MB
H.S Robustness to defense strategies
Besides the defense discussions in Section we analyze the effectiveness of conventional defense strategies in this section. In detail, two classic GNN defense models - GNNGuard [4] and Elas- ticGNN [18 are deployed to test their defense capabilities against NIFA. It worth noting that, both defense models are originally designed for the attacks prediction utility. We conduct experiments on three datasets, and the victim model is GCN as default. As shown Table A5 both defense models only maintain the utility performance and failed to fully eliminate the impact of fairness at-
20

---

Table A5: The performance of defense strategies against NIFA.
Pokec-z
Pokec-n
DBLP
Asp
Ago
Asp
Ago
Agp
Apo
Clean
71.22:0:28
7.13+1.21
5.10s1.28
70,92:0.66
0.88s0.62
2.44:1.37
95.88s1611
3.8420.34
1,9180.75
NIFA
70,50:0.30
17.36E1.16
15.5921.08
70.12:0.37
10.1022.80
9.85+1.77
93.37:0.28
13,4912.83
20.33:3.82
GNNGuard
71.5040.35
18.13+2.31
16.32e1.44
70.55e0.43
13.82s1.76
13,38
95.73a0.28
7.42+1882
14.9221.58
ElastiGNN
71.3610.00
13.53a0.92
11.3621.23
70.3210.28
6.90=1.02
6.4111.32
94.2240.37
9.7611.65
17.01z2.01
tacks. For example, compared with the performance after the attack, although ElasticGNN reduces the Asp from 17.36% to 13.53%, the fairesss is still worse than that before the attack 7.13%. We believe that the main reason behind such observation is that all these defense methods are de- signed for utility-tageetted attacks, whose objectives are totally different from fairness attacks like NIFA. Such observations also indicate that more effective defense mechanisms are still in demand for fairness attacks on GNNs.
H.6 Performance with limited training ratio
As introduced in Section 5.1 our
datasets are all collected from the previ- work - FA-GNN [II. and our train / val test ratios are set to be consis- tent with its settings, which is 50% 25% / 25%, respectively. However, more realistic scenarios the percentage of labeled training nodes might sig- nificantly smaller due to the heavy cost of annotation. To evaluate the effective- ness of NIFA under such settings, we decrease the training ratio from 50% to 25%, 10% and 5%, respectively. The attack performance of NIFA on Pokec-z and Pokec-n shown in Table A6 It can be seen that, even with much fewer labeled training nodes, NIFA still consistently demonstrates promising attack performance.
Table A6: The performance of NIFA with more limited training nodes. The victim model GCN.
Pokec-
Polue-n
25%
41:47:0.50
6.2611.3
4.3
1610444
1.040.70
after
40.4540.4
15.161
13.18e1.77
69.4960.31
9.792202
9.52e1.84
10%
20.000..5
6.3912.7
4.531.44
702550.37
2.5611332
20:1499266
18226342
13,363306
092256062
11,96.1788
12,0011.55
5%
before
7000560554
4.9921.98
3.7521.01
08.6111155
3.7922.30
4.21+1.94
69 8960165
14.362285
12.426.04
08056163
10.115588
104065.04
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Please refer to the abstract and Section I
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to Section for our discussions on the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
22

---

Justification:
Please refer to Section 4.2 and Appendix C for the complete proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer to Section 5.1 and Appendix G for reproducibility details. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
Justification: The url of our code and data is released in the Abstract. Section and
Appendix Galso describe reproducibility details.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (bttps:/nnips.c/ppbblic/ guides/CodeSubmissoonPoo
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https: for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer Section 5.1 and Appendix G experimental details. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the standard deviations of our experiments after repeating each experiment five times, which is also explained in the text. Please refer to Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory. time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the computer resources and environment in Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We thoroughly discuss the ethical consideration in Appendix A in which the potential social harms are acknowledged and the code license are provided to avoid malicious use. We also discuss the feasible defensive measures Section mitigate potential harmful consequences from our research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We thoroughly discuss the ethical consideration in Appendix A in which the potential social harms are acknowledged and the code license are provided to avoid malicious use. We also discuss the feasible defensive measures in Section to mitigate potential harmful consequences from our research.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
25

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: We describe the code license that will be released with our model in Ap-
pendix A
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All models and baselines from existing assets are properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
26

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswitheode peeeswwtthodd.cccm/dattattttt has cu- rated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: We thoroughly discuss the training details, license, and limitations of our proposed model in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can cither create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
27

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "718TxLf1yo", "reviewer": "Reviewer_ZRPp", "summary": "This paper proposes NIFA, a novel fairness attack method via node injection. In particular, the authors use the uncertainty maximization principle to select the target node to attack and randomly connect the injected nodes to the target nodes in the same sensitive group to increase the overall homophily. Finally, the authors use direct optimization to tune the features of the injected nodes to maximize the unfairness and minimize the predictive loss. Experimental results show the effectiveness of NIFA in reducing the fairness of GNNs.", "questions": "Please see the weaknesses.", "limitations": "The limitations including the potential negative societal impact of this work are sufficiently discussed in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper delivers the first node injection attacks on fairness for GNNs.\n- The paper is overall well-organized and easy to follow.\n- The methodology is basically well-motivated and verified by empirical studies.", "weaknesses": "- Although experiments show that NIFA distinctly increases the bias level of GNNs, the accuracy decreases as well, especially for DBLP. It can be helpful if more discussions on the tradeoff between accuracy and bias level are provided.\n- Complexity analysis is not included in the paper. A succinct discussion (theoretical or empirical) on the computational efficiency of NIFA is encouraged.\n- There exists a gap between Lemma 1 and the goal of the homophily-increase principle. Increased homophily cannot guarantee the increase of $\\Delta_{sp}$ and $\\Delta_{eo}$.\n- The overall framework of NIFA is simple but kind of incremental. The technical novelty and provided insights are somewhat limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for the constructive comments, and we aim to address the concerns with the following responses.\n\n------\n\n**[Concerns about the utility (W1)]**\n\nWe will first analyze the potential reasons for utility decrease, and then provide some solutions for balancing the trade-off between utility and fairness attack.\n\n- **Potential reasons:** Compared with evasion attacks, where only input data is modified and the victim model remains unchanged, poisoning attacks naturally result in a larger utility change due to the change of victim model. \n- **Mitigation solutions:** There are some potential methods to control the trade-off between utility and fairness of NIFA, **such as controlling the number of target nodes**, i.e. the nodes with the top $k$ highest uncertainty. Intuitively, with more nodes connected with injected nodes, the utility will be more likely to be influenced. To support our claims, we tune the $k$ in a range of {0.10, 0.25, 0.50, 0.75} in DBLP, and the attack performance on GCN and GraphSAGE is shown **in Table R1 in the uploaded PDF**. It can be seen that, after decreasing $k$, the utility after the attack can be effectively preserved.\n\n------\n\n**[Concerns about the complexity (W2)]**\n\nWe have included an efficiency analysis for NIFA **in Appendix H.5**. The results indicate that NIFA demonstrates much higher efficiency compared with other fairness attacks on GNNs. \n\n------\n\n**[Concerns about the Lemma 1 (W3)]**\n\nAs we claimed in footnote 2, the relationship between homophily ratio and fairness is widely discussed in previous work. For a better understanding of the role of homophily ratio in GNN fairness and to mitigate the gap, we provide the following theoretical analysis:\n\n- **Theoritical analysis:** Denote $P(s|x)$ as a predictor that estimates the sensitive attributes $s$ given node features $x$. Inspiring by [1], we utilize a linear intensity function $\\mathcal{D} _{\\theta}(s|x)$ with parameter $\\theta$ to define its predictive capability, where $\\mathcal{D} _{\\theta}(s|x) \\sim \\mathcal{N}(\\mu, \\sigma^2)$ and $\\mathcal{D} _{\\theta}(\\overline{s}|x) \\sim \\mathcal{N}(\\overline{\\mu}, \\sigma^2)$, where $\\overline{s}$ is the false sensitive attribute and $\\mathcal{N}(\\cdot, \\cdot)$ is the Gausssian distribution. In this way, $\\mu > \\overline{\\mu}$ indicates that $\\mathcal{D} _{\\theta}$ prefers to provide a higher intensity score for the true sensitive attribute given the node embeddings $x$, and the larger $\\mu-\\overline{\\mu}$ is, the stronger inference capability of $\\mathcal{D} _{\\theta}$ and more biased node embeddings $x$ are.\n\n  ​    We further formulate the message propagation process in GNN as $x_i^{\\prime}=x _i+x _i^{neigh}$, where $x _i^{neigh}$ denotes the average neighbor embeddings for node $i$, and $x _i^{neigh}=P _i^{same}x _i^{same}+P _i^{diff}x _i^{diff}$. $P _i^{same}$ denotes the probability of selecting a neighbor with the same sensitive attribute with node $i$, i.e. homophily ratio, and $P _i^{same} + P _i^{diff}=1$. $x _i^{same}$ denotes the average neighbor embeddings with the same sensitive attribute with node $i$.\n\n  ​    In this way, we can have the following derivation of the equations:\n  $$\n  \\\\begin{align*}\n  \\\\mathbb{E}\\\\left\\\\{ \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i') - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i') \\\\right\\\\} \n  &= \\\\mathbb{E}\\\\left\\\\{ \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i) + \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i^{\\\\text{neigh}}) - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i) - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i^{\\\\text{neigh}}) \\\\right\\\\} \\\\\\\\\n  &= \\\\mathbb{E}\\\\left\\\\{ \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i) - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i) + P_i^{\\\\text{same}} \\\\mathbb{E}\\\\left\\\\{ \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i^{\\\\text{same}}) - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i^{\\\\text{same}}) \\\\right\\\\} \\\\right. \\\\\\\\\n  &\\\\quad \\\\left. - P _i^{\\\\text{diff}} \\\\mathbb{E}\\\\left\\\\{ \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i^{\\\\text{diff}}) - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i^{\\\\text{diff}}) \\\\right\\\\} \\\\right\\\\} \\\\\\\\\n  &= \\\\mathbb{E}\\\\left\\\\{ \\\\mathcal{D} _{\\\\theta}(s _i \\\\mid x _i) - \\\\mathcal{D} _{\\\\theta}(\\\\overline{s _i} \\\\mid x _i) + \\\\left( P _i^{\\\\text{same}} - P _i^{\\\\text{diff}} \\\\right) (\\\\mu - \\\\overline{\\\\mu}) \\\\right\\\\} \\\\\\\\\n  \\\\end{align*}\n  $$\n\n  ​    It can be seen that, the second term $\\\\left( P _i^{\\\\text{same}} - P _i^{\\\\text{diff}} \\\\right) (\\\\mu - \\\\overline{\\\\mu})$  $= ( 2*P _i^{\\\\text{same}}- 1) (\\\\mu - \\\\overline{\\\\mu})$ **is positively correlated to the homophily ratio**, and with the increase of homophily ratio as we introduced in Lemma1, the message propagation process will result in larger unfairness.\n\n------\n\n**[Concerns about the contributions (W4)]**\n\nThe major contributions of this paper are three-fold:  \n\n1. We are the first to launch a node-injection-based fairness attack on GNNs to the best of our knowledge, and highlight the vulnerability of GNN fairness. \n2. We design a simple yet effective method NIFA, which consists of two novel and insightful principles for guiding node injection operations. Extensive experiments verify the effectiveness, deceptiveness and efficiency of NIFA, which can effectively deteriorate GNN fairness, even including fair GNNs with merely 1% injected nodes. \n3. From the perspective of responsible AI, we summarize several key insights from the success of NIFA, which we believe can inspire more in-depth research on robust GNN fairness.\n\n------\n\nWe sincerely hope that our responses can effectively address your concerns and contribute to a better version of our research. If you have any further questions or confusion, please do not hesitate to reach out to us. We would be more than willing to assist and provide further clarification.\n\n**Reference**\n\n[1] FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization, AAAI 2024.", "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": "hHy1tdtPds", "reviewer": "Reviewer_L3XD", "summary": "This paper examines the vulnerability of GNN fairness under adversarial attacks.  A gray-box node injection-based poisoning attack method, namely NIFA, is proposed. NIFA follows the newly designed uncertainty maximization principle and homophily-increase principle. Then,  multiple novel objective functions are proposed to guide the optimization of the injected nodes’ features, impacting the victim GNN’s fairness from a feature perspective. The experiment is extensive and solid.", "questions": "Please see the weakness.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1: The problem of the vulnerability of GNN fairness is interesting and very important. This paper is well-motivated.\n\nS2: The proposed method is technically sound.\n\nS3: The experiment is solid and extensive. Very comprehensive experimental results are reported in the appendix including hyper-parameter testing, ablation studies, analysis of poisoned graph, etc.\n\nS4: The paper is well-written and very easy to follow.", "weaknesses": "W1: Node injection will change the topological structure of a graph. However, several existing studies work on structural fairness in GNN. I am wondering whether the proposed fairness attacks are applicable to those works. What if the graph structure changes over time and becomes dynamic? Is the proposed attack applicable to dynamic fairness GNN methods?\n\nSome references:\n\n[1] Uncovering the Structural Fairness in Graph Contrastive Learning. NeurPIS 2022.\n\n[2] Tail-GNN: Tail-Node Graph Neural Networks. KDD. 2021.\n\n[3] On Generalized Degree Fairness in Graph Neural Networks. AAAI. 2023.\n\n[4] Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing Approach. KDD. 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for these insightful comments. Specifically, we aim to address the concerns of the reviewer with the following responses.\n\n------\n\n**[Question about the Structural Fairness (W1)]**\n\nThanks for your inspiring question! According to prior research, structural fairness and attribute fairness stem from different reasons [3]. The structural fairness (such as degree fairness in TailGNN [2] and DegFairGNN [3]) may be caused by the limited neighborhood information, while attribute fairness mainly comes from the \"homophily principle\" in GNN message propagation and the correlation between sensitive attributes and other attributes. In this way, the rationale behind NIFA such as the \"homophily-increase principle\" may be more suitable for attribute fairness instead of structural fairness.\n\nHowever, we highly agree that the adversarial attacks on structural fairness would be another inspiring research direction in the future, and we would like to add this to our discussion in the next version.\n\n------\n\n**[Question about the Dynamic Fairness (W1)]**\n\nTo the best of our knowledge, the dynamic fairness in GNN is still under-explored, and the only related work is based on structural fairness [1], which is not suitable for NIFA as we discussed before. We extend our best gratitude for your insightful feedback, and we believe that more efforts are still in demand for a more detailed definition of dynamic fairness based on the sensitive attributes before launching a corresponding fairness attack.\n\n------\n\nWe sincerely thank the reviewer for the encouraging comments and thoughtful feedback. We sincerely hope that our responses can effectively address your concerns and contribute to a better version of our research. If you have any further questions or confusion, please do not hesitate to reach out to us. We would be more than willing to assist and provide further clarification.\n\n**Reference**\n\n[1] Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing Approach. KDD. 2024.\n\n[2] Tail-GNN: Tail-Node Graph Neural Networks. KDD. 2021.\n\n[3] On Generalized Degree Fairness in Graph Neural Networks. AAAI. 2023.", "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": "mdPQt3gUXG", "reviewer": "Reviewer_U6JX", "summary": "The authors propose a Fairness GNN Attack method called Node Injection-based Fairness Attack (NIFA). The proposed method aims to increase the bias of GNN models by injecting nodes into the graph. NIFA identifies nodes with high uncertainty to target them, then connects the injected nodes in such a way increasing the homophily of the graph. The features of the injected nodes are then optimized to balance utility with fairness. NIFA is evaluated on multiple benchmark datasets and compared with Fairness GNN attack methods.", "questions": "Please refer to the Weaknesses section.", "limitations": "The authors adequately discuss the limitations of their proposed method.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "- The paper is very well written and easy to follow. \n- The proposed method seems to be technically sound.\n- The fairness of GNN models and Fairness attack methods are both important and well motivated problems.", "weaknesses": "- The proposed attack method is not well motivated, could the authors provide concrete application domains/cases where it is not possible to modify/attack the existing edges between nodes in the graph but it is possible to inject nodes into it and connect such nodes to the rest of the graph? \n\n- Furthermore, if modifying the edges in graph is considered unrealistic, how is this different from the part in the proposed method where injected nodes are connected to the nodes in the graph ? The limitation of previous works claimed by the authors seem rather arbitrary and inconsistent. If the ability to modify the graph structure is not a realistic assumption, then connecting the injected nodes to the real nodes in the graph should similarly be considered unrealistic. Basically, if connecting injected nodes to the real nodes in the graph is permissible, then it should be permissible for previous fairness attack methods to modify the graph structure by adding edges to it (without deleting existing edges). \n\n- The utilized 1% perturbation rate is rather high, in real-world large graph datasets consisting of millions of nodes, this is equivalent to injecting the graph with tens of thousands of nodes which can hardly be considered unnoticeable. The authors should experiment with significantly smaller perturbation rates and compare the corresponding results against the relevant baselines in the literature. \n\n- It is not possible to evaluate the effectiveness of proposed method against the relevant fairness attack methods using a single dataset only as 2 out of the 3 fairness attack methods are reported without results on 2 datasets. The authors should include additional datasets and/or additional Fairness attack methods. \n\n- All 3 fairness GNN Attack methods [11, 13, 40] report results on one or both Pokec datasets. Therefore, if the author do not have access to the computational resources required to run the aforementioned baselines, they should run their proposed method on the setups of those 3 baselines and report the results of the 3 baselines  [11, 13, 40] from the corresponding works. In this manner, we would be able to properly evaluate the effectiveness of the proposed method against the relevant Fairness Attack baselines in the literature.  \n\n- It is unclear how the authors ensure a fair budget across all attack methods given the different nature of the attacks where some methods modify the graph structure and node features, while other methods inject the graph with additional nodes. Could the authors please elaborate on this point and how they ensured fairness across budgets of different types of attack methods ? \n\n- The train/val/test split utilized assigns half of the nodes to labeled training nodes. However, in most realistic scenarios a significantly smaller percentage of the nodes are assigned to labeled training nodes. How does the proposed method perform when the number of training nodes in the graph is limited ? This is specially important given that targeted nodes with high uncertainty in this work are a subset of the training nodes. The authors should conduct experiments with limited labeled nodes and evaluate the effectiveness of the proposed method under this more realistic scenario. \n\n- The authors should evaluate their proposed method on additional common benchmark datasets for Fair GNN learning task such as Credit, Bail and NBA datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for these insightful comments. Specifically, we aim to address the concerns of the reviewer with the following responses.\n\n------\n\n**[Concerns about the attack scenarios (W1, W2)]**\n\nTake a social graph like Twitter as an example, where each node denotes a user and each link represents a following relationship. In this case, modifying the edges between existing nodes means alternating the following relationship between real users. **Such operations usually ask the attackers to hack the user accounts, which is hard and time-consuming.** However, with the node-injection-based attack, the attackers only need to **create several zombie accounts (node-injection) and follow several real users**, which is much easier. \n\nIn fact, compared with attacks modifying existing edges, **the superiority of node-injection-based attacks has been widely verified in multiple prior works [1-4]**. However, all these works only focus on attacking GNNs utility, while neglecting the fairness vulnerability of GNNs.\n\n------\n\n**[Concerns about the perturbation ratio (W3)]**\n\n1. It seems that there are some misunderstanding about the perturbation ratio. In our work, the perturbation ratio **is based on the labeled nodes** in the graph instead of all nodes in the graph. Specifically, as we introduced in Appendix G, the injected nodes for Pokec-z, Poker-n and DBLP are only 102, 87 and 32 respectively, which is around **0.15%**, **0.13%** and **0.16%** of all nodes in the original graph.\n\n2. In fact, the proportion of node injections in our work is comparable to or even lower than that of other related node-injection-based attacks. To support our claim, we statistics the default node injection ratios (relative to the total number of nodes in the graph) of several node-injection-based attacks below:\n\n   |                           | NIPA[1] |  TDGIA[2]   | MaxiMal[4] |    Ours     |\n   | :-----------------------: | :-----: | :---------: | :--------: | :---------: |\n   | **Node injection ratios** |   1%    | 0.07%-0.30% |     1%     | 0.13%-0.16% |\n\n3. **We also conduct experiments by decreasing the perturbation ratio to 0.08%** (relative to the total number of nodes) on DBLP, i.e. 16 injected nodes. The attack performance on GCN is shown **in Table R2 in the uploaded PDF.** It can be seen that, even with a more limited perturbation rate, NIFA still achieves the best fairness attack performance compared with other baselines. \n\n------\n\n**[Concerns about the baselines & datasets (W4, W5, W8)]**\n\n- **Baselines:** Thanks for your constructive feedback. To the best of our knowledge, **FA-GNN, FATE and G-FairAttack are the only three attack methods on GNN fairness.** We would be more than happy to provide additional comparisons if the reviewer can clarify other missing baselines on GNN fairness attacks. \n\n- **Datasets:** In fact, our datasets are consistent with FA-GNN, the first fairness attacks on GNNs. We agree that comparisons on more datasets could better verify the effectiveness of NIFA. In detail, we further conduct experiments on the setup of FATE and G-FairAttack, i.e. Pokec datasets with fewer nodes. We also examine the effectiveness of NIFA on the German benchmark, which is widely used in previous GNN fairness studies [5-7]. The experimental results are shown **in Table R4 in the uploaded PDF**, where NIFA still achieves competitive fairness attack performance.\n\n------\n\n**[Concerns about the fair budget (W6)]**\n\nFor methods that only inject new nodes, such as AFGSM, TDGIA and G2A2C, we require the number of injected nodes and average degree of injected nodes to be the same as ours. For methods that require to modify the graph structure, such as FA-GNN, FATE and G-FairAttack, **we set the number of modified edges to be the same with our injected edges**, i.e. the added edges between injected nodes and original nodes. We will enhance the clarity of this part in Appendix G in the future.\n\n------\n\n**[Concerns about the label ratio (W7)]**\n\nThanks for your comments! In fact, our datasets are collected from the previous work -- FA-GNN, and our train/val/test ratios are set to be consistent with its settings. \n\nWe agree that there might be fewer labeled nodes in more realistic scenarios. To evaluate the effectiveness of NIFA under such settings, we decrease the training ratio from 50% to 25%, 10% and 5%, respectively. The attack performance of NIFA is shown **in Table R3 in the uploaded PDF**. It can be seen that, even with much fewer labeled training nodes, NIFA still consistently demonstrates promising attack performance.\n\n------\n\nWe sincerely thank the reviewer for the thoughtful comments and constructive feedback. We sincerely hope that our responses can effectively address your concerns and contribute to a better version of our research. If you have any further questions or confusion, please do not hesitate to reach out to us. We would be more than willing to assist and provide further clarification.\n\n------\n**References**\n\n[1] Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learning Approach, WWW 2020.\n\n[2] TDGIA: Effective Injection Attacks on Graph Neural Networks, KDD 2021.\n\n[3] Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning, AAAI 2023.\n\n[4] Maximizing Malicious Influence in Node Injection Attack, WSDM 2024.\n\n[5] EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks, WWW 2022.\n\n[6] Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage, KDD 2022.\n\n[7] FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization, AAAI 2024.", "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": "DarDWjrQlI", "reviewer": "Reviewer_wXHX", "summary": "The authors propose a fairness attack on GNN through node injection. They propose two node injection principles, the uncertainty-maximization and homophily-increase principle, to make fake node injections lead to a more significant fairness compromise.", "questions": "In addition to the weaknesses listed above, my questions for the authors include:\n\n1. The injected node features require the attacker to perform local training on a given training node set. Can the attacker  obtain the training node set, especially when it contains private information?\n\n2. In the discussion of mitigation methods, such as Reliable Training Nodes and Strengthening Connections Among Groups, the authors focus on general mitigation strategies. These strategies are also suitable for defending against accuracy-targeted node-injection attacks and lack a discussion on the specifics of fairness-targeted attacks. This raises the question of whether existing defenses against accuracy-targeted attacks are sufficient to defend against fairness-targeted attacks.\n\n3. The experimental results in Table 2 show that fairness is compromised while accuracy also decreases, which contradicts the expected trade-off between fairness and accuracy. The authors should explain the reason for this occurrence. In principle, when fairness is compromised with the goal of minimizing accuracy loss, accuracy should improve.\n\nAs the topic is interesting, I am willing to adjust my score based on the authors' responses.", "limitations": "1. The proposed method is designed for binary classification with two sensitive attributes. It should be considered whether and how the proposed method can be extended to multi-class classification and multiple sensitive attributes.\n\n2. The experiments were conducted on a two-layer GCN, which is consistent with the baseline [10]. However, a discussion is expected about the feasibility of the attack  on GCNs with different architectures.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This article is well-written and highly readable.\n\nThe focus on attacking fairness is interesting.\n\nThe author’s discussion on potential extensions of the method, such as different approaches to measure node vulnerability and potential mitigation methods, is encouraging.\n\nThe choice of datasets and baselines for validating attack performance is representative, demonstrating the significant effectiveness of the proposed method.", "weaknesses": "1. The main concern is that the proposed node-injection-based fairness attack could potentially be mitigated by existing defenses designed for accuracy-based node-injection attacks. The distinction between fairness-targeted and accuracy-targeted attacks is not discussed, and there is a lack of an in-depth discussion on related work concerning node-injection attacks aimed at accuracy.\n\n2. Another concern is that the theoretical effectiveness of \"the node injection strategy is evaluated by an increase in the node-level homophily ratio\". This homophily ratio does not clearly establish a connection with fairness metrics, i.e., DP/EO.  Providing a theoretical guarantee that the proposed node injection strategy results in more significant improvements in DP/EO compared to random node injection will enhance the validity.\n\n3. Additionally, the motivation of attackers to undermine fairness is not clearly discussed. Adding some real-world examples to demonstrate the motivation of such attacks will be better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**[Concerns about the discussion about node-injection-based attack (W1)]**\n\nThe main distinction between fairness-targeted and accuracy-targeted attacks is the different attack objectives. The accuracy-targeted attacks aim to undermine the model accuracy, while fairness-targeted attacks aim to deteriorate the model fairness without significantly compromising the model accuracy. The results in Table 3 in our manuscript also support this claim. Although we introduce several node-injection-based attacks in Section 2, we agree that an in-depth review of corresponding related work would be better, and we will add more discussion on node-injection-based attacks to our manuscript in the future.\n\n------\n\n**[Concerns about the defense strategies (W1, Q2)]**\n\nThanks for your insightful comments! We hope to address your concerns on the defense strategies with the following responses:\n\n1. While selecting more reliable training nodes might help resist accuracy-targeted adversarial attacks, our experiments in Figure 2 actually show that this approach **does not completely mitigate** the fairness attacks posed by NIFA. More effective methods are still in demand.\n2. We further test the defense capabilities of two classic GNN defense models—GNNGuard [4] and ElasticGNN [5]—against NIFA. The results are shown **in Table R5 in the uploaded PDF**. As shown in the results, **both defense models only maintain the utility performance and failed to fully eliminate the impact of fairness attacks.**\n\n------\n\n**[Concerns about the Lemma 1 (W2)]**\n\nAs we claimed in footnote 2, the relationship between homophily ratio and fairness is widely discussed in previous work. To better understand the role of homophily ratio in GNN fairness and mitigate the gap, we would like to provide more theoretical analysis. **Due to space limitation, we place the complete theoretical analysis in the global rebuttal box**.\n\n------\n\n**[Concerns about the motivation (W3)]**\n\nIn fact, fairness attacks on GNNs have numerous potential applications. Besides the example of GNN-based recommendation in the introduction, professional social networks like LinkedIn also face some potential risks. Specifically, when GNNs are used to identify high-potential candidates, attackers might use fake accounts to manipulate the model into predicting high potential for their group with a much higher probability, securing better job offers while harming other demographic groups. \n\n------\n\n**[Concerns about the capability of attackers (Q1)]**\n\nAs we introduced in Appendix B, NIFA is under the gray-box attack settings, which is realistic and widely studied in previous utility attacks of GNNs [1-3]. In gray-box attack settings, the attackers have access to the training data, including graph, node attributes and training labels, but cannot see the model architecture and parameters. In fact, the training data including node attributes and ground truth labels are not hard to get in the real world. For example, some user attributes like gender, region are actually public on some social platforms like Weibo, LinkedIn or Twitter.\n\n------\n\n**[Concerns about the the accuracy (Q3)]**\n\nAlthough many studies in pursuing GNN fairness suggest a trade-off between utility and fairness—where better fairness often results in lower utility—we believe this trade-off does not fully hold in the context of fairness attacks. For instance, if a GNN model's predictions are entirely aligned with sensitive attributes, resulting in a 100% SP (Statistical Parity), its accuracy would inevitably suffer. \n\nAdditionally, we would like to further discuss some **potential methods to better alleviate the utility decrease introduced by NIFA**, such as controlling the number of target nodes, i.e. the nodes with the top $k$ highest uncertainty. Intuitively, with more nodes connected with injected nodes, the utility will be more likely to be influenced. To support our claims, we tune the $k$ in a range of {0.10, 0.25, 0.50, 0.75} in DBLP, and the attack performance on GCN and GraphSAGE is shown **in Table R1 in the uploaded PDF**. It can be seen that, after decreasing $k$, the utility after the attack can be better preserved.\n\n------\n\n**[Concerns about the expandability (L1)]**\n\nThanks for your inspiring question, and we would like to discuss the expandability of NIFA from the following two perspectives:\n\n- **Multi-class classification**: In fact, our method can naturally fit the multi-label classification scenarios, since there is no specific requirement on the number of categories in our framework, which can also be verified by the problem definitions in Section 3.  Since our datasets are collected from the prior work -- FA-GNN, we mainly focus on binary classification tasks to be consistent.\n- **Multiple sensitive attributes**: As we claimed in Section 3, NIFA can be easily extended to multiple sensitive attributes. The only distinction is that the attackers need to equally partition the injected nodes into multiple groups instead of two groups during the node injection process, and make sure each injected node will only connect to real nodes with the same sensitive attribute.\n\n------\n\n**[Concerns about the GCN architectures (L2)]**\n\nThanks for your suggestions. We further conduct model architecture analysis for GCN by modifying the model layer and hidden dimension, and the attack results on Pokec-z and Pokec-n are shown **in Table R6 in the uploaded PDF**. It can be seen that, NIFA demonstrates promising robustness towards the GCN models with different model layers and hidden dimensions.\n\n\n**References**\n\n[1] Adversarial Attacks on Graph Neural Networks via Meta Learning, ICLR 2019.\n\n[2] A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning, NeurIPS 2019.\n\n[3] Adversarial Attacks on Fairness of Graph Neural Networks, ICLR 2024.\n\n[4] GNNGUARD: Defending Graph Neural Networks against Adversarial Attacks, NeurIPS 2020.\n\n[5] Elastic Graph Neural Networks, ICML 2021.", "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:
## To all reviewers:

We sincerely thank all reviewers for their valuable feedback and encouraging comments on our paper. All four reviewers consistently approve of the topic: **“interesting”**, **“well-motivated”**, and **“encouraging”**, and the presentation of our work: **"well-written"**, **"very easy to follow"** and **"highly readable"**. Also, most of the reviewers agree that our experimental results:**“significant effectiveness”**, **“solid and extensive”**, and **“comprehensive”**.

We also notice that there are some misunderstanding and concerns about our paper. **Due to space limitations, we have included most of the experimental results (figures and tables) in the attached PDF, with corresponding references provided in the rebuttal.** We sincerely hope that our responses have effectively addressed your concerns and contributed to a deeper understanding of our research. If you have additional questions or confusion, please feel free to contact us without hesitation. We would sincerely like to provide more information and clarification if necessary.

------

## To reviewer #wXHX:

Due to space limitations, we place the theoretical analysis for the relationship between homophily ratio and fairness here.

**Theoritical analysis:** Denote $P(s|x)$ as a predictor that estimates the sensitive attributes $s$ given node features $x$. Inspiring by [1], we utilize a linear intensity function $\mathcal{D} _{\theta}(s|x)$ with parameter $\theta$ to define its predictive capability, where $\mathcal{D} _{\theta}(s|x) \sim \mathcal{N}(\mu, \sigma^2)$ and $\mathcal{D} _{\theta}(\overline{s}|x) \sim \mathcal{N}(\overline{\mu}, \sigma^2)$, where $\overline{s}$ is the false sensitive attribute and $\mathcal{N}(\cdot, \cdot)$ is the Gausssian distribution. In this way, $\mu > \overline{\mu}$ indicates that $\mathcal{D} _{\theta}$ prefers to provide a higher intensity score for the true sensitive attribute given the node embeddings $x$, and the larger $\mu-\overline{\mu}$ is, the stronger inference capability of $\mathcal{D} _{\theta}$ and more biased node embeddings $x$ are.

We further formulate the message propagation process in GNN as $x_i^{\prime}=x _i+x _i^{neigh}$, where $x _i^{neigh}$ denotes the average neighbor embeddings for node $i$, and $x _i^{neigh}=P _i^{same}x _i^{same}+P _i^{diff}x _i^{diff}$. $P _i^{same}$ denotes the probability of selecting a neighbor with the same sensitive attribute with node $i$, i.e. homophily ratio, and $P _i^{same} + P _i^{diff}=1$. $x _i^{same}$ denotes the average neighbor embeddings with the same sensitive attribute with node $i$.

In this way, we can have the following derivation of the equations:
$$
\\begin{align*}
\\mathbb{E}\\left\\{ \\mathcal{D} _{\\theta}(s _i \\mid x _i') - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i') \\right\\} 
&= \\mathbb{E}\\left\\{ \\mathcal{D} _{\\theta}(s _i \\mid x _i) + \\mathcal{D} _{\\theta}(s _i \\mid x _i^{\\text{neigh}}) - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i) - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i^{\\text{neigh}}) \\right\\} \\\\
&= \\mathbb{E}\\left\\{ \\mathcal{D} _{\\theta}(s _i \\mid x _i) - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i) + P_i^{\\text{same}} \\mathbb{E}\\left\\{ \\mathcal{D} _{\\theta}(s _i \\mid x _i^{\\text{same}}) - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i^{\\text{same}}) \\right\\} \\right. \\\\
&\\quad \\left. - P _i^{\\text{diff}} \\mathbb{E}\\left\\{ \\mathcal{D} _{\\theta}(s _i \\mid x _i^{\\text{diff}}) - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i^{\\text{diff}}) \\right\\} \\right\\} \\\\
&= \\mathbb{E}\\left\\{ \\mathcal{D} _{\\theta}(s _i \\mid x _i) - \\mathcal{D} _{\\theta}(\\overline{s _i} \\mid x _i) + \\left( P _i^{\\text{same}} - P _i^{\\text{diff}} \\right) (\\mu - \\overline{\\mu}) \\right\\} \\\\
\\end{align*}
$$

It can be seen that, the second term $\\left( P _i^{\\text{same}} - P _i^{\\text{diff}} \\right) (\\mu - \\overline{\\mu})$  $= ( 2*P _i^{\\text{same}}- 1) (\\mu - \\overline{\\mu})$ is positively correlated to the homophily ratio, and with the increase of homophily ratio as we introduced in Lemma1, the message propagation process will result in larger unfairness.

**Reference**

[1] FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization, AAAI 2024.

Meta-review: This paper proposes NIFA, a Node Injection-based Fairness Attack that reveals vulnerabilities in Graph Neural Networks (GNNs) by injecting new nodes instead of altering existing connections. NIFA utilizes principles of uncertainty maximization and homophily increase, combined with optimized node features, to effectively compromise GNN fairness. Experiments on real-world datasets show that NIFA can significantly undermine the fairness of GNNs, including fairness-aware models, with the injection of just 1% of nodes. Reviewers generally agreed that the problem of using node injection to compromise GNN fairness is compelling, and the proposed method has clear merits. In their rebuttal, the authors addressed most of the reviewers' concerns and provided additional experiments. I suggest the authors incorporate these changes into the final version if the paper is accepted at NeurIPS.
Decision: Accept (poster)