Are Your Models Still Fair? Fairness Attacks on Graph Neural Networks via Node Injections

[Concerns about the discussion about node-injection-based attack (W1)]

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

[Concerns about the defense strategies (W1, Q2)]

Thanks for your insightful comments! We hope to address your concerns on the defense strategies with the following responses:

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

[Concerns about the Lemma 1 (W2)]

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

[Concerns about the motivation (W3)]

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

[Concerns about the capability of attackers (Q1)]

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

[Concerns about the the accuracy (Q3)]

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

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

[Concerns about the expandability (L1)]

Thanks for your inspiring question, and we would like to discuss the expandability of NIFA from the following two perspectives:

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

[Concerns about the GCN architectures (L2)]

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

References

[1] Adversarial Attacks on Graph Neural Networks via Meta Learning, ICLR 2019.

[2] A Unified Framework for Data Poisoning Attack to Graph-based Semi-supervised Learning, NeurIPS 2019.

[3] Adversarial Attacks on Fairness of Graph Neural Networks, ICLR 2024.

[4] GNNGUARD: Defending Graph Neural Networks against Adversarial Attacks, NeurIPS 2020.

[5] Elastic Graph Neural Networks, ICML 2021.

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.

[Concerns about the attack scenarios (W1, W2)]

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

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

[Concerns about the perturbation ratio (W3)]

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

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

   	NIPA[1]	TDGIA[2]	MaxiMal[4]	Ours
   Node injection ratios	1%	0.07%-0.30%	1%	0.13%-0.16%

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

[Concerns about the baselines & datasets (W4, W5, W8)]

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

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

[Concerns about the fair budget (W6)]

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. We will enhance the clarity of this part in Appendix G in the future.

[Concerns about the label ratio (W7)]

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

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

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

References

[1] Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learning Approach, WWW 2020.

[2] TDGIA: Effective Injection Attacks on Graph Neural Networks, KDD 2021.

[3] Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning, AAAI 2023.

[4] Maximizing Malicious Influence in Node Injection Attack, WSDM 2024.

[5] EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks, WWW 2022.

[6] Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage, KDD 2022.

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

Thanks for your valuable feedback and reconsideration of scores!

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.

[Question about the Structural Fairness (W1)]

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

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

[Question about the Dynamic Fairness (W1)]

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

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

Reference

[1] Toward Structure Fairness in Dynamic Graph Embedding: A Trend-aware Dual Debiasing Approach. KDD. 2024.

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

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

We sincerely thank the reviewer for the constructive comments, and we aim to address the concerns with the following responses.

[Concerns about the utility (W1)]

We will first analyze the potential reasons for utility decrease, and then provide some solutions for balancing the trade-off between utility and fairness attack.

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

[Concerns about the complexity (W2)]

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

[Concerns about the Lemma 1 (W3)]

As 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:

• 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:

  \

$

\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\} \\
$