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_cc_2024_Conference
Published: 2024-05-14 03:13:00

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.

Main paper: 
 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 of GNN models, which greatly restricts their applications in the real world.In fact, studies [5, 42] have found that the biases and prejudices existed in training data would be further 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 recruitment, a 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 unfairness. To address fairness issues in GNNs, researchers have proposed solutions such as adversarial learning [5, 28] , data augmentation [17, 22] and others, which have achieved promising results.However, recent research in the machine learning domain indicates that fairness is actually susceptible to adversarial attacks [3, 26, 29] . Given this, we cannot help but wonder: "Is the fairness of GNN models also highly vulnerable?" For example, in e-commerce, if attackers could exacerbate performance 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 specific user demographics and gradually lose its appeal among these users. Several studies [11, 13, 41] 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 between real users. In contrast, injecting fake nodes into the original graph is a more practical way to launch an attack without manipulating the existing graph [12, 32, 34] , which is still under-explored in the field of GNN fairness attack. To address this gap, we aim to be the first to launch an attack on GNN fairness via node injection, examining their vulnerabilities under such a more realistic setting. Specifically, launching a node injection-based fairness attack on GNNs is non-trivial, whose challenges 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 Injectionbased 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 uncertaintymaximization 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 homophily-increase principle, to connect target nodes with injected nodes. This principle aims to deteriorate GNN fairness by enhancing message propagation within sensitive groups [22, 40] . For the second challenge, multiple novel objective functions are proposed after node injection to guide the optimization of the injected nodes' features, which could further impact the victim GNN's fairness from a 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 injections, 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-based gray-box attack named NIFA. To be concrete, NIFA first designs two novel principles to 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 a 1% perturbation rate and an unnoticeable utility compromise, even including fairness-aware GNN models. Comparisons with other state-of-the-art baselines also verify the superiority of NIFA in achieving fairness attacks. 
related work: 
 Fairness on GNNs. Researchers have discovered various fairness issues of GNNs, which often lead to societal harms [22, 37] and performance deterioration [21, 33] in practical applications. Algorithmic fairness on GNNs can be categorized into two main types based on the definition: individual fairness [1, 6] and group fairness [5, 37, 46] . Individual fairness 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 sensitive attributes. For instance, Dai et al. [5] reduce the identifiability of sensitive attributes in node embeddings through adversarial training to enhance fairness. FairVGNN [38] goes a step further by introducing a feature masking strategy to address the problem of sensitive information leakage during 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 fairness related to sensitive attributes, some researchers also direct attention to fairness related to graph structures, like DegFairGNN [21] 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 remains 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 attacks, 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 vulnerability of GNN fairness. Different from attacks on GNN utility, fairness-targeted attacks aim to deteriorate the fairness without significantly compromising the accuracy. FA-GNN [11] , FATE [13] , and G-FairAttack [41] 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 significantly compromise GNN fairness without affecting its performance [11] . FATE [13] formulates the fairness attacks as a bi-level optimization problem and proposes a meta-learning-based framework. G-FairAttack [41] designs a novel surrogate loss with utility constraints to launch the attacks in a 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. 
preliminary: 
 Here we will introduce some basic notations and concepts, and then give our problem definition.A graph is denoted as G = (V, A, X), where V is the node set, and A ∈ R |V|×|V| represents the adjacency matrix. X ∈ R |V|×D denotes the feature matrix, in which D is the feature dimension. Under the settings of node classification, each node v ∈ V will be assigned with a label y v ∈ Y, and a GNN-based mapping function f θ : {V, G} → {1, 2, ..., |Y|} |V| with parameters θ is learned to leverage the graph signals for label prediction, where Y represents the true label set.In alignment with prior works [5, 7, 17] , we mainly focus on group fairness where each node will be assigned with a binary sensitive attribute s ∈ {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 non-overlapped groups V = {V 0 , V 1 }, and we employ the following two kinds of fairness related definitions:Definition 1. Statistical Parity (SP). The Statistical Parity requires the prediction probability distribution to be independent of sensitive attributes, i.e. for any class y ∈ Y and any node v ∈ V:EQUATIONwhere ŷv denotes the predicted label of node v.Definition 2. Equal Opportunity (EO). The Equal Opportunity requires that the probability of predicting correctly is independent of sensitive attributes, i.e. for any class y ∈ Y and any node v ∈ V, we can have:EQUATIONBased on the above definitions, we can define two kinds of metrics ∆ SP and ∆ EO to quantitatively measure fairness. For both metrics, smaller values indicate better fairness:EQUATIONEQUATIONIn 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 is under the prevalent gray-box setting, where the attackers can obtain the graph G with node labels Y, and the sensitive information s, but can not access the model architecture and parameters θ. Detailed introduction to our attack settings is provided in Appendix B. Specifically, through injecting malicious node set V I into the graph, the original graphG = (V, A, X) is poisoned as G ′ = (V ′ , A ′ , X ′ ),whereEQUATIONEQUATIONBoth V I and A I are matrices for illustrating the connectivity related to injected nodes, and X I is the feature matrix of injected nodes V I . The true label set Y will not be poisoned by injected nodes in our settings, as such information is typically hard to modify in reality. For conciseness, we denote F(•) and M(•) as the evaluation functions on fairness and utility for the learned mapping function f θ , respectively. Then our goal as an injection-based attack on fairness could be formulated as:max G ′ |F(f θ * (V, G ′ ))| (7) s.t. arg max θ * M(f θ * (V, G ′ )), G ′ = (V ′ , A ′ , X ′ ), |V I | ≤ b, deg(v) v∈V I ≤ d.As a poisoning attack, the first constraint in Eq. ( 7) requires to train the victim model f θ * with parameters θ * on the poisoned graph G ′ , so that the predictions of f θ * 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 b1 and the degrees of injected nodes are constrained by a budget d. Our goal is to find a poisoned graph G ′ to deteriorate the fairness of victim models f θ * as severely as possible, i.e. maximize the fairness metrics ∆ SP and ∆ EO introduced previously. 
methodology: 
 In this section, we first give an overview of our attack method NIFA. Then we will elaborate on the details of each module and summarize the implementation algorithms at last.The overall framework of NIFA is illustrated in Figure 1 . As mentioned before, NIFA first employs two principles to guide the node injection operations. For the first uncertainty-maximization principle, 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 homophily-increase principle, NIFA requires each injected node can only establish connections to target nodes from one single sensitive group (b), thus increasing the homophily-ratio and enhancing information propagation within sensitive 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.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 operations, namely Uncertainty-maximization principle and Homophily-increase principle.Original graph G (a) Uncertainty Estimation Uncertainty-maximization principle. Intuitively, nodes with higher model uncertainties are positioned 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 to 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 a GNN with parameters θ B , we obtain different model parameters through T times independent Bernoulli dropout sampling processes, i.e.:EQUATIONwhere M i is the ith sampled binary mask following the Bernoulli distribution with parameter p, and ⊙ denotes the dot production operation. Here we take a two-layer GCN [10] with parameters θ B as the Bayesian GNN for estimating the uncertainty of each node, and θ B is optimized by minimizing the following objective function, which consists of a cross-entropy loss plus a regularization term:EQUATIONwhere Y denotes the true labels, ∥ • ∥ 2 2 denotes the L2 regularization, T is the number of sampling processes and f θ B i (•) is the mapping function with the ith sampled parameters θ Bi . After the training process, model uncertainty can be estimated by calculating the variance of T times predictions with the sampled parameters {θ Bi } T i=1 . Intuitively, nodes with lower variance are more confident in their predictions and vice versa. Thus, the model uncertainty scores U ∈ R |V| are positively correlated with the model prediction variance, and we simply estimate U with the following formulation:EQUATION)Under the guidance of the uncertainty-maximization principle, we will select nodes with the top k% model uncertainty U in each sensitive group as the target nodes, where k is a hyper-parameter.Homophily-increase 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 provided later: the injected nodes V I 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 1 (b), where d is a hyper-parameter. At this stage, the node injection operations are 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 easier to accentuate differences in embeddings between groups and thereby exacerbate unfairness issues [37] . We also provide a brief theoretical analysis to show that such a strategy could lead to the increase of nodelevel homophily ratio. Similar to [8] , we define the node-level homophily-ratio H u as the ratio of neighbors of node u that have the same sensitive attribute as node u, i.e.H u = v∈Nu 1(su=sv) |Nu| ,where N u denotes the neighbors of node u and 1(•) is an indicator function. Then we can have:Lemma 1. For target node u that will connect with injected nodes, our proposed node injection strategy will lead to the increase of node-level homophily-ratio H u .Due to space limitation, the proof for Lemma 1 is provided in Appendix C. It is worth noting that H u 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 attributes 2 . We believe that such characteristics could empower our node injection strategy with stronger capability on fairness attacks.In this part, we will introduce the details of optimizing injected nodes' features X I , 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 a surrogate GNN model S at first for assessing their attacks. To be specific, similar to the training process of victim models as described in Eq. ( 7), the surrogate model S will be trained on the poisoned graph G ′ and optimize its parameter θ S to maximize the utility. Conversely, X I is designed to mislead S, ensuring that even a well-trained surrogate model will still maintain high unfairness under attacks. Instead of employing a pre-trained frozen surrogate model S, NIFA asks two components, i.e. S and X I to be trained iteratively with different objective functions, which avoids the attack being over-fitting to specific model parameters. In detail, the surrogate model S 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 a 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 [11, 13, 41] , thus being unnoticeable for utility-based attack detection.To this end, we set cross-entropy loss as our first objective function, i.e.:EQUATIONwhere V tr denotes the original training node set, and h u 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 ∆ SP and ∆ EO , which are formulated as:EQUATIONEQUATIONwhere h u ∈ R |Y| denotes the raw output of node u, and h u,y ∈ R denotes the raw output of node u on class y. V tr i,y denotes the training nodes with sensitive attribute i and label y. By minimizing L SP and L EO , 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 is distinct during the message propagation process. To this end, we devise the following constraint function on the injected node feature matrix X I :EQUATIONwhere V I,i 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:EQUATIONwhere α and β are two hyper-parameters to control the weights of different objective functions.Training process. Due to space limitation, we summarize the pseudo-code of NIFA in Algorithm 1 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 I 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 I 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 malicious 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. Datasets. 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, one of the largest online social networks in Slovakia, according to the provinces of users [5] . 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 to predict the working fields of users. DBLP is a coauthor network dataset [11] , where each node represents an author and two authors will be connected if they publish at least one paper together. The node features are constructed based on the words selected from the corresponding author's published papers. The final classification task is to predict the research area of the authors. The detailed dataset statistics are summarized in Table 1 .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 conclusions 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , 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 authors 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., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experimental settings: 
 Victim models. As a gray-box attack method, we target multiple classical GNNs as victim models, including GCN [14] , GraphSAGE [10] , APPNP [15] , and SGC [39] . We also include three wellestablished fairness-aware GNNs -FairGNN [5] , FairVGNN [38] , and FairSIN [40] as our selected victim models. The details of these victim models will be elaborated in Appendix E.Baselines. Depending on the attack goals, we mainly consider the following two kinds of graph attack methods as our baselines, including 1) Utility attack: AFGSM [36] , TDGIA [47] , and G 2 A2C[12], and 2) Fairness attack: FA-GNN [11] , FATE [13] , and G-FairAttack [41] . The details of these baselines will be further introduced in Appendix F.Implementation details. As shown in Table 1 , only a 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, [11] , 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. To comprehensively evaluate NIFA's effectiveness, we employ multiple mainstream GNNs including GCN, GraphSAGE, APPNP, and SGC, besides three classical fairness-aware GNNs namely FairGNN, FairVGNN, and FairSIN as our victim models. We record the average accuracy, ∆ SP and ∆ EO before and after conducting our poisoning attack on the victim models five times. The experimental results are reported in Table 2 , and we can have the following observations:• The proposed attack demonstrates consistent effectiveness on all datasets with different mainstream GNNs as victim models. For instance, the ∆ SP and ∆ EO of GCN on Pokec-z increase significantly from 7.13%, 5.10% to 17.36% and 15.59%, respectively. Such observation successfully 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 ∆ EO 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 fairness 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 deceptive nature for administrators.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 [47] , G 2 A2C [12] , FA-GNN [11] , FATE [13] , and G-FairAttack [41] . 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 as ours for a fair comparison. Note that, both FATE and G-FairAttack fail to deploy on Pokec-z and Pokec-n due to scalability issues 3 . Results after repeating five times are shown in Table 3 .It 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 to modify the original graph, such as adding or removing some edges or modifying features of real nodes. For deceptiveness consideration, their modifications are usually constrained by a 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.In this part, we conduct ablation experiments to prove the effectiveness of the uncertaintymaximization principle, homophily-increase principle, and iterative training strategy, respectively. In detail, we consider the following three variants of NIFA. 1) NIFA-U: the uncertaintymaximization 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 homophily-increase principle is removed, i.e. each injected node may connect with targeted nodes from different sensitive groups simultaneously. 3) NIFA-I: we remove the iterative training strategy here, which means that the surrogate model is 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. The results are reported in Figure 2 , where we can have the following observations. Firstly, after removing the uncertainty-maximization principle (NIFA-U), the fairness attack performance consistently decreases on three datasets. This is expected since the concept of uncertainty helps NIFA find more vulnerable nodes, thus improving the attack effectiveness. Secondly, after removing the homophily-increase principle (NIFA-H), the attack performance 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.6 Defense discussion to fairness attacks on GNNs As previously emphasized, our intrinsic aim is to unveil the vulnerabilities of existing GNN models in terms of fairness, thereby inspiring related defense research. In fact, as an 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 NIFA for further careful study:∆ 𝑺𝑷 / ∆ 𝑬𝑶 (%) 𝜼 ACC ∆ !" ∆ #$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.4. In this way, administrators can pay more attention to these nodes and their abnormal neighbors for defense 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 a simple experiment by removing a proportion of nodes (η) with the highest uncertainty U from supervision signals after the attack. Similarly, GCN [10] is employed as the victim model and we gradually tune η from 0 to 0.6 with step 0.1, where η = 0 means no defense is involved. The performance of NIFA on the Pokec-z dataset with different η is illustrated in Figure 3 . 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 (∆ SP =7.13, ∆ EO =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 fairness attack is the guidance of the homophily-increase principle during node injection. The ablation study in Appendix 5.4 also 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-related information will be aggregated and enlarged within the group. Given this, we believe that an effective defensive strategy is to strengthen the information propagation among different sensitive groups, thus preventing the risks of information cocoons [22, 25] and fairness issues.Fairness auditing. At last, we find that a crucial assumption in NIFA and other research [11, 13, 41] is that GNN model administrators will only audit the utility metrics of the models, such as accuracy or F1-scores. Therefore, as long as attackers can ensure that the model utility is not affected excessively, it will be hard for administrators to realize the attack. Consequently, we strongly suggest that model administrators should also incorporate fairness-related 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 demonstrates 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 [5, 23] , individual fairness [6] , etc., and group fairness 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. 
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 fairness 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-based 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 fairnessaware 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 fairness attacks.Limitations. Firstly, NIFA is still under the settings of gray-box attacks, which requires accessibility 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 effective defense measures are still under-explored, calling for more future research efforts. At last, currently we only focus on fairness 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 6 to mitigate potential harmful consequences from our research.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 6 to mitigate potential harmful consequences from our research.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation 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). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [Yes] Justification: We describe the code license that will be released with our model in Appendix A.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?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 a 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.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: In this study, we propose a 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 fairness 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 to 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 4 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 6, which we believe can to some extent mitigate the fairness attacks proposed in our work and hopefully inspire future fairness defenses.In this section, we would like to 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 to make our attack more practical in the real world, which is also consistent with multiple prior research on GNN attacks [11, 32, 41] . 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 Y 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.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 I malicious nodes and poisons the graph G into G ′ to launch an attack, which is 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 injectionbased 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 to set thresholds b and d for the number of injected nodes and their degrees respectively to make NIFA deceptive and unnoticeable.Lemma 1. For target node u that will connect with injected nodes, our proposed node injection strategy will lead to the increase of node-level homophily-ratio H u .Proof. Given a target node u 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 ′ u is: 8) and Eq. ( 9). 3: Estimate the node uncertainty U in the original graph G by Eq. ( 10) and select the target nodes. 4: Connect the injected nodes with target nodes according to the homophily-increase principle. 5: for iter = 1 to max iter do 6:EQUATIONfor step = 1 to max step do 7:Compute cross-entropy loss L CE for S by Eq. ( 11). Compute L by Eq. ( 15). 12:Update injected feature: Clamp X I between min and max of X. X I ← X I + γ F • ∇ X I L.Due to space limitation, here we provide the complete training process of NIFA in Algorithm 1. The training process and evaluation process are also literally described in Section 4.4.In this part, we give an introduction to the victim models used in our experiment.• GCN [10] : Borrowing the concept of convolution from the computer vision domain, GCN employs convolution operation on the graph from a spectral perspective to learn the node embeddings. • GraphSAGE [14] : Given the potential neighborhood explosion issues in GCN, GraphSAGE samples a fixed number of neighbors at each layer during neighborhood aggregation, which greatly improves the training efficiency. • APPNP [15] : 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. • SGC [39] : SGC empirically finds the redundancy of non-linear activation function, and achieves comparable performance with much higher efficiency. • FairGNN [5] : Through proposing a sensitive attribute estimator and an adversarial learning module, FairGNN maintains high classification accuracy while reducing unfairness in scenarios with limited sensitive attribute information. • FairVGNN [38] : FairVGNN discovers the leakage of sensitive information during information propagation of GNN models, and generates fair node features by automatically identifying and masking sensitive-correlated features. • FairSIN [40] : Instead of filtering out sensitive-related information for fairness, FairSIN deploys a novel sensitive information neutralization mechanism. Specifically, FairSIN will learn to introduce additional fairness facilitating features (F3) during message propagation to neutralize sensitive information while providing more non-sensitive information.In this section, we will introduce more details about the baselines used in our experiments.• AFGSM [36] : 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. • G 2 A2C [12] : Similar to NIPA [32] , G 2 A2C also proposes a node injection attack through reinforcement learning -Actor Critic. Specifically, G 2 A2C devises three core modules including Node Generator, Edge Sampler, Value Predictor to model the full process of node injection. • FA-GNN [11] : To the best of our knowledge, FA-GNN is the first work to conduct a 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 a meta-learning-based fairness attack framework for GNNs. To be concrete, FATE formulates the fairness attacks as a bi-level optimization problem, where the lower-level optimization guarantees the deceptiveness of an attack while the upper-level optimization is designed to maximize the bias functions. • G-FairAttack [41] : As a poisoning fairness attack, G-FairAttack consists of two modules, including a surrogate loss function and following constrained optimization for deceptiveness. Like FATE and FA-GNN, G-FairAttack also belongs to graph modification attacks, i.e., the original link structure between existing nodes will be modified during the attack.The implementation details are first provided in Section 5.1 in the original paper. Here we would like to provide more implementation details from the following four aspects:Environment. All experiments are conducted on a server with Intel(R) Xeon(R) Gold 5117 CPU @ 2.00GHz and 32 GB Tesla V100 GPU. The experimental environment is based on Ubuntu 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 is set to 0 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 k is set to 1. For APPNP, following the suggestions in the official paper, the teleport probability α is set as 0.2, and we set the iteration number k as 1 after careful tuning. For FairGNN, we employ the GAT as the backbone model, which shows a better performance in the original paper, and set the dropout ratio as 0.5. The objective weights α and β are set as 4 and 0.01, respectively. For FairVGNN, GCN is set to 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 α is 0.5. The epochs for the generator, discriminator, and classifier are selected from {5, 10} as 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-parameters are set according to the official implementations 5 .Baselines details. For all baselines that involve graph structure manipulation, the numbers of injected 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 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. To be concrete, for the AFGSM, across all datasets, we utilize the direct attack setting and allow the model to perturb node features. For TDGIA, the weights k 1 , and k 2 , which are used for calculating topological vulnerability are set to 0.9 and 0.1, respectively. For G 2 A2C, the temperature of Gumbel-Softmax is set to 1.0, the discount factor is set to 0.95, and the Adam optimizer is 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 implementation6 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 settings in the official repository 7 for other hyper-parameters. It is worth noting that, G-FairAttack can be utilized as either an evasion attack or a poisoning attack according to the original paper, and we follow the poisoning attack settings to be the same with NIFA. As a poisoning attack, it is crucial to ensure that after the attack, the poisoned graph's characteristics should remain similar to 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:Structural analysis. Similar to prior work [2, 32] , we investigate several key graph characteristics in this section, including Gini Coefficient, Assortativity, Power Law Exponent, Triangle Count, Relative Edge Distribution Entropy and Characteristic Path Length, whose definitions and implementations can be found here 8 . The graph statistics under different perturbation rates are shown in 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 |∆| on all graph structure statistics. 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 as the perturbation rate increases. For example, with the increase in attack intensity, the degree assortativity consistently decreases on three datasets, indicating that there are 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 statistics can be potentially utilized for fairness attack defense and auditing. Feature analysis. Besides graph structural analysis, we also conduct experiments to analyze the nodes' features of the poisoned graph. In detail, after conducting fairness attacks through NIFA, for both labeled nodes in the real graph and injected nodes, we illustrate their features' visualization results based on t-SNE [35] in Figure A1 . Note that, 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 are 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 no obvious patterns, and are hard to recognize from the original labeled nodes. Such observation further verifies the feature deceptiveness of NIFA. During the node injection process, NIFA proposes an uncertainty-maximization principle and selects target nodes with the highest model uncertainty score. In fact, besides estimating model uncertainty, there are other alternative methods 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.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 "Uncertainty"), 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.To better understand the different roles of hyper-parameters in NIFA, we study the impact of α, β, b, and k in this part where GCN is employed as the victim model. The impact of node injection budget b. We illustrate the impact of the node injection budget b in Figure A4 , where the x-axis denotes the perturbation rate, i.e. the proportion of b to the number of labeled nodes in the original graph. As expected, the increase of b leads to better fairness attack performance in most cases with more obvious accuracy compromise. Empirically, 0.01 will be a near-optimal choice while being unnoticeable.The impact of uncertainty threshold k. The impact of k is illustrated in Fig- ure A5 , where we tune k% in a set of {0.1, 0.25, 0.5, 0.75}. It can be seen that all datasets show a similar preference for k% with an optimal value of 0.5. Intuitively, with a higher k%, it is hard for NIFA to attack the target nodes with low uncertainty, whereas, with a lower k%, the impact of the attack will be limited by the insufficient number of targeted nodes. To evaluate the efficiency and scalability of NIFA, we would like to compare the attack time cost and memory cost between NIFA and two competitive baselines including FATE [13] and G-FairAttack [41] . 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 deployed 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 Pokecn. As shown in Table 1 , 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.Besides the defense discussions in Section 6, we analyze the effectiveness of conventional defense strategies in this section. In detail, two classic GNN defense models -GNNGuard [44] and Elas-ticGNN [18] are deployed to test their defense capabilities against NIFA. It is worth noting that, both defense models are originally designed for the attacks on prediction utility. We conduct experiments on three datasets, and the victim model is GCN as default. As shown in Table A5 , both defense models only maintain the utility performance and failed to fully eliminate the impact of fairness at- As introduced in Section 5.1, our datasets are all collected from the previous work -FA-GNN [11] , and our train / val / test ratios are set to be consistent with its settings, which is 50% / 25% / 25%, respectively. However, in more realistic scenarios the percentage of labeled training nodes might be significantly smaller due to the heavy cost of annotation. 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 on Pokec-z and Pokec-n is shown in Table A6 . It can be seen that, even with much fewer labeled training nodes, NIFA still consistently demonstrates promising attack performance.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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs 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 complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.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. |VI |/|VL|, where VL denotes the labeled node set.Similar conclusions have been concluded from multiple prior works[22,26,40]. For better a understanding of the relationship between the homophily-ratio and unfairness, one can also refer to[40], which provides the corresponding theoretical analysis from a massage propagation perspective.On 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.https://creativecommons.org/licenses/by-nc-nd/4.0/https://github.com/BUPT-GAMMA/FairSIN/https://github.com/jiank2/FATEhttps://github.com/zhangbinchi/G-FairAttackhttps://github.com/danielzuegner/netgan/tree/master 


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- Complexity analysis is not included in the paper. A succinct discussion (theoretical or empirical) on the computational efficiency of NIFA is encouraged.
- 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}$.
- The overall framework of NIFA is simple but kind of incremental. The technical novelty and provided insights are somewhat limited.
questions: questions: Please see the weaknesses.
limitations: limitations: The limitations including the potential negative societal impact of this work are sufficiently discussed in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

Some references:

[1] Uncovering the Structural Fairness in Graph Contrastive Learning. NeurPIS 2022.

[2] Tail-GNN: Tail-Node Graph Neural Networks. KDD. 2021.

[3] On Generalized Degree Fairness in Graph Neural Networks. AAAI. 2023.

[4] Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing Approach. KDD. 2024.
questions: questions: Please see the weakness.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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? 

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

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

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

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

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

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

- The authors should evaluate their proposed method on additional common benchmark datasets for Fair GNN learning task such as Credit, Bail and NBA datasets.
questions: questions: Please refer to the Weaknesses section.
limitations: limitations: The authors adequately discuss the limitations of their proposed method.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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

3. 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.
questions: questions: In addition to the weaknesses listed above, my questions for the authors include:

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

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

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

As the topic is interesting, I am willing to adjust my score based on the authors' responses.
limitations: 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.

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

Comments: title: Thank you for the reply
Rebuttal
Thank you for the comments
comment: Thank you very much for your responses which address my concerns well. I will keep my score.
Thanks for your valuable feedback and reconsideration of scores!
Thanks again for your valuable comments and reconsideration of scores! To better understand the relationship between the homophily ratio and fairness, we would like to provide a more thorough discussion and summarization of previous related work in the final version.
I thank the authors for providing a detailed response. The provided analysis of the connection between homophily ratio and bias seems to rely on strong assumptions, but it would be fine if this has been verified empirically by previous works. Most of my concerns are well addressed. Hence, I am happy to raise my score.
Thank you to the authors for their response. After carefully reviewing it, I have updated my original score.
Dear Reviewers,

I kindly ask you to review the authors' rebuttals and provide feedback on whether they have adequately addressed your concerns or if further clarifications are needed. Please note that the discussion deadline is fast approaching on August 13th.

Thank you for your attention to this matter.

Best regards,
AC
Thank you again for your valuable review and reconsideration of scores!
I would like to thank the authors for their response and clarifications. At this point, I have no further questions. Although the current work still relies on a gray-box attack model and lacks an effective defense mechanism against fairness attacks, I acknowledge these are existing challenges and appreciate the authors' clarification of these limitations. I increased my score based on new experiments and explanations of convincing motivation, better robustness compared to accuracy attacks, theoretically supported proxy metric, and generalizability.