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

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.

Strengths

This article is well-written and highly readable. The focus on attacking fairness is interesting. The author’s discussion on potential extensions of the method, such as different approaches to measure node vulnerability and potential mitigation methods, is encouraging. The choice of datasets and baselines for validating attack performance is representative, demonstrating the significant effectiveness of the proposed method.

Weaknesses

1. The main concern is that the proposed node-injection-based fairness attack could potentially be mitigated by existing defenses designed for accuracy-based node-injection attacks. The distinction between fairness-targeted and accuracy-targeted attacks is not discussed, and there is a lack of an in-depth discussion on related work concerning node-injection attacks aimed at accuracy. 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

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.

Rating

5

Confidence

5

Soundness

3

Presentation

3

Contribution

2

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.

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.

Strengths

- The paper is very well written and easy to follow. - The proposed method seems to be technically sound. - The fairness of GNN models and Fairness attack methods are both important and well motivated problems.

Weaknesses

- The proposed attack method is not well motivated, could the authors provide concrete application domains/cases where it is not possible to modify/attack the existing edges between nodes in the graph but it is possible to inject nodes into it and connect such nodes to the rest of the graph? - 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

Please refer to the Weaknesses section.

Rating

4

Confidence

5

Soundness

2

Presentation

3

Contribution

1

Limitations

The authors adequately discuss the limitations of their proposed method.

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.

Strengths

S1: The problem of the vulnerability of GNN fairness is interesting and very important. This paper is well-motivated. S2: The proposed method is technically sound. S3: The experiment is solid and extensive. Very comprehensive experimental results are reported in the appendix including hyper-parameter testing, ablation studies, analysis of poisoned graph, etc. S4: The paper is well-written and very easy to follow.

Weaknesses

W1: Node injection will change the topological structure of a graph. However, several existing studies work on structural fairness in GNN. I am wondering whether the proposed fairness attacks are applicable to those works. What if the graph structure changes over time and becomes dynamic? Is the proposed attack applicable to dynamic fairness GNN methods? 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

Please see the weakness.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The authors have adequately addressed the limitations.

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.

Strengths

- This paper delivers the first node injection attacks on fairness for GNNs. - The paper is overall well-organized and easy to follow. - The methodology is basically well-motivated and verified by empirical studies.

Weaknesses

- Although experiments show that NIFA distinctly increases the bias level of GNNs, the accuracy decreases as well, especially for DBLP. It can be helpful if more discussions on the tradeoff between accuracy and bias level are provided. - 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

Please see the weaknesses.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The limitations including the potential negative societal impact of this work are sufficiently discussed in the paper.

Rebuttal

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