Deceptive Fairness Attacks on Graphs via Meta Learning

We appreciate your constructive comments and valuable feedback for further improving our work. Please see our point-to-point responses as follows.

Q1. Lack of clarity, including definition of $\mathbf{Y}$, separating victim and surrogate model, reference to Ptb. and bias measures, and experimental questions.

Thank you for your suggestion in further improving the clarity.

• Definition of $\mathbf{Y}$: In the last paragraph of Section 2, we have defined $\mathbf{Y}$ as the output of graph learning model, which is highlighted in blue.

• Separating victim and surrogate model: We would like to clarify that the attacker only have access to the surrogate model, i.e., solving Eq. (1) is solely based on the surrogate model. The victim model is only used when evaluate the performance of FATE in Section 6. Thus, we believe it it not necessary to differentiate the notations for victim model and the surrogate model in Sections 3 -- 5.

• Reference to Ptb. and bias measure: We have revised the table caption to reflect the meaning of Ptb. and $\Delta_{\text{SP}}$ in the revised version, highlighted in blue. For Table 1, the new caption is "Attacking statistical parity on GCN under different perturbation rates (Ptb.). FATE poisons the graph via both edge flipping (FATE-flip) and edge addition (FATE-add) while all other baselines poison the graph via edge addition. Higher is better ($\uparrow$) for micro F1 score (Micro F1) and $\Delta_{\text{SP}}$ (bias). Bold font indicates the most deceptive fairness attack, i.e., increasing $\Delta_{\text{SP}}$ and highest micro F1. Underlined cell indicates the failure of fairness attack, i.e., decreasing $\Delta_{\text{SP}}$ after fairness attack." Similar changes have also been made to Tables 2 and 5 -- 11.

• Add experimental questions: Given the space limitation, we have added the philosophical experimental questions at the beginning of Appendix D, which are (1) How effective is FATE in exacerbating bias under different perturbation rates? (2) How effective is FATE in maintaining node classification accuracy for deceptiveness under different perturbation rates? And (3) can we characterize the properties of edges perturbed by FATE?

Q2. Possible defense strategy.

Thank you for your suggestion in discussing how to defend against fairness attacks. Following our analysis on the manipulated edges in Sections 6.1 and 6.2, we believe possible defense strategies could be as follows. To defend against deceptive fairness attacks for statistical parity, one possible strategy is to preprocess the input graph by either learning a bias-free graph (e.g., [1]) or sampling over the neighborhood (e.g., [2, 3, 4]) to control which node representations to aggregate during message passing. The reason for such possible design is that Figure 1 reveals the properties of injected edges that are likely to be incident to nodes in the minority class and/or protected group. Following similar principles, it is also possible to develop a selective or probabilistic message passing strategy to achieve the same goal during model optimization. To defend against deceptive fairness attacks for individual fairness, we can apply similar neighborhood sampling strategy or selective/probabilistic message passing strategy. Instead, for individual fairness, the neighborhood sampling or selective message passing would consider the class label rather than the sensitive attribute (i.e., sample edges that connect nodes in the minority class as shown in Figure 2). Please note that the aforementioned discussion has been added in our revised version (Appendix H.G).

Q3. Bias measure in Section 4.

Thank you for your suggestion in further improving the clarity. We have added the definition of bias function (i.e., $b\left(\mathbf{Y}, \Theta^*, \mathbf{S}\right) = |\operatorname{P}\left[{\tilde y} = 1\right] = \operatorname{P}\left[{\tilde y} = 1|s = 1\right]|$) in Section 4-C, which is highlighted in blue.

We appreciate your constructive comments and valuable feedback for further improving our work. Please see our point-to-point responses as follows.

Q1. Limited novelty and discussion on three limitations for existing work.

Thank you for your questions.

• For limitation 1, we would like to clarify that we attack two fairness definitions, i.e., statistical parity (Sections 4 and 6.1) and individual fairness (Sections 5 and 6.2), to generate the adversarial graphs.
• For limitation 2, we agree with the reviewer that the operation space would be affected by the practicability of the attack. However, we believe both edge injection, edge deletion, and edge flipping are almost equally practical. For example, in the given malicious banker example, edge injection refers to injecting adversarial transaction record(s) in the transaction network, edge deletion refers to removing transaction record(s), and edge flipping is the combination of two.
• For limitation 3, we implicitly assume there is a divergence in optimizing the task-specific loss function $l(\mathcal{G},\mathbf{Y},\Theta,\theta)$ and optimizing the bias function $b\left(\mathbf{Y},\Theta^*,\mathbf{F}\right)$. Thus, maximizing $b(\mathbf{Y},\Theta^*,\mathbf{F})$ may not affect $l\left(\mathcal{G},\mathbf{Y},\Theta,\theta\right)$ too much. Since we are minimizing the task-specific loss function in the inner loop (i.e., lower-level optimization), it helps to maintain the performance in the downstream task for deceptive fairness attacks. We think such assumption is reasonable for the following reason. In fair machine learning, a common strategy is to solve a regularized optimization problem, where the objective function to be minimized is often defined as $l(\mathcal{G},\mathbf{Y}, \Theta, \theta)+\alpha b(\mathbf{Y},\Theta^*,\mathbf{F})$ with $\alpha$ being the regularization hyperparameter. If there is no divergence between the optimization of $l(\mathcal{G},\mathbf{Y},\Theta,\theta)$ and $b(\mathbf{Y},\Theta^*,\mathbf{F})$, it would be sufficient to optimize one of them to obtain fair and high-utility learning results, or it would be impossible to achieve a good trade-off between fairness and utility if they are completely conflicting with each other. All in all, we believe that optimizing the task-specific loss function $l(\mathcal{G},\mathbf{Y},\Theta,\theta)$ in the lower-level optimization problem could help maintain deceptiveness both intuitively and empirically as shown in Section 6.1, Section 6.2, Appendix E, and Appendix F.

Q2. Inaccurate/unclear statements about matrix norm, definition of distance between graphs, and repeated discussion about $\hat{y}$.

Thank you for your suggestions.

• Regarding the matrix norm: we believe the review is referring to matrix-induced norm. For the induced matrix norms, $\|\mathbf{A}\|_{1,1}$ would refer to the maximum absolute column sum of the matrix difference. However, as we mentioned at the end of Section 2.C, we use the entry-wise matrix norms. It treat the elements of the matrix as one big vector (see here). Following the definition of entry-wise matrix norms, our notation means the absolute sum of each entry as shown at the end of Section 2.C.

• Regarding the definition of distance between graphs: we agree with the reviewer that the distance between two graphs might also consider the distance between feature matrices in some cases. However, we believe how to define the distance is based on the attacker's capability in attacking adjacency matrix and/or feature matrix. If the attacker would only attack the adjacency matrix, it is sufficient to define the distance between two graphs as the distance between two adjacency matrices, because the distance between two feature matrices will always be 0. If the attacker would want to attack both adjacency matrix and feature matrix, the distance between two graphs should consider both the distance between adjacency matrices and the distance between feature matrices. In fact, when we describe the distance between two graphs at the end of Section 2.C, we use e.g. (for example) to provide an example. And when we describe the distance in Section 3.1 ("The capability of attacker"), we use i.e. (in another word) to explain the distance constraints for edges/features.

• Regarding the repeated discussion about $\hat{y}$: we would like to clarify that this is not repeated definition. We acknowledge that the previous descriptions might confuse the reviewer. In the revised version, we use ${\widehat y}\_{i,j}$ to denote the prediction probability of node $i$ belonging to class $j$ and ${\tilde y}$ to denote the predicted label. Then, $P[{\tilde y} = 1]$ refers to the complementary CDF of $p({\widehat y}_{i,1} > \frac{1}{2})$ because we would classify node $i$ to class 1 if the corresponding prediction probability is larger than $\frac{1}{2}$ in a binary classification problem.

In addition, we would like to point out that an absolute unit accuracy cost may be unable to capture whether the accuracy is increased or decreased after attack. Thus, we further provide additional results on unit accuracy bias increase, which is defined as $\text{unit-acc-bias-increase} = \frac{\Delta_{\text{SP}}^{(\text{after})} - \Delta_{\text{SP}}^{(\text{before})}}{\text{Acc}^{(\text{before})} - \text{Acc}^{(\text{after})}}$. The reason for the numerator being $\Delta_{\text{SP}}^{(\text{after})} - \Delta_{\text{SP}}^{(\text{before})}$ is that we want the bias to increase as much as possible after fairness attack, thus measuring the bias increase after attack. While the reason for the denominator being $\text{Acc}^{(\text{before})} - \text{Acc}^{(\text{after})}$ is that we want the accuracy to be decrease as few as possible, thus measuring the accuracy decrease after attack. With this definition, it is clear that (1) a negative unit accuracy bias increase is always better than positive value, because we could increase the bias without costing accuracy; (2) higher is better if unit accuracy bias increase is positive (we increase more bias with a unit decrease in accuracy), and (3) smaller is better if unit accuracy bias increase is negative (i.e., we increase more bias with a unit increase in accuracy). The results for unit accuracy bias increase of FA-GNN, FATE-flip, and FATE-add are as follows (with the same format as the table above). It should be noted that, when the bias decreases and the accuracy increases (i.e., failed fairness attacks), it is also possible to achieve a negative unit accuracy bias increase, which will be denoted by (fail).

From the table above, for Pokec-n, FATE-flip and FATE-add always achieves negative unit accuracy bias increase, which is better than positive values achieved by FA-GNN. For Pokec-z, other than the case when perturbation rate is 0.15, FATE-flip and FATE-add always achieves negative unit accuracy bias increase, which is better than positive values achieved by FA-GNN. For Bail, FATE-flip and FATE-add always achieve a better unit accuracy bias increase than FATE.

We hope this could demonstrate the effectiveness of our proposed method, as we can achieve better absolute unit accuracy cost or unit accuracy bias increase in many cases. In the remaining days, we will calculate both metrics for all experimental settings (statistical parity vs. individual fairness, GCN vs. FairGNN/InFoRM-GNN) and update the manuscript with the additional results.

Again, we sincerely appreciate the reviewer for your kind suggestion on better clarity and new evaluation metric. Should you have any remaining concerns, we are more than happy to discuss with you.

We appreciate the reviewer for your suggestion for better clarity and for further clarification on defining the unit accuracy cost. We have followed your suggestion and have changed "attack statistical parity and individual fairness" to "attack statistical parity or individual fairness" in the updated version (in abstract, organization of Appendix at the beginning of Appendix page, and Appendix G).

Regarding the unit accuracy cost, as the reviewer suggested, we define the absolute unit accuracy cost as $\text{unit-acc-cost} = \frac{|\Delta_{\text{SP}}^{(\text{before})} - \Delta_{\text{SP}}^{(\text{after})}|}{|\text{Acc}^{(\text{before})} - \text{Acc}^{(\text{after})}|}$, which helps measure the absolute change in $\Delta_{\text{SP}}$ with one unit absolute change in accuracy. And higher is better for absolute unit accuracy, because a higher absolute unit accuracy cost means that one unit change in accuracy could cause more bias increase. The unit accuracy costs of FA-GNN, FATE-flip, and FATE-add are as follows. Please note that, in each cell of table below, the absolute unit accuracy costs are reported when the perturbation are from 0.05 to 0.25 with a step size of 0.05 in an ascending order, i.e., the leftmost value indicates the absolute unit accuracy cost when the perturbation rate is 0.05, and the rightmost value indicates the absolute unit accuracy cost when the perturbation rate is 0.25. (fail) means that the absolute unit accuracy cost refers to the case of failed fairness attack (i.e., decreasing bias after attack).

For Pokec-n, FATE-flip and FATE-add achieves higher absolute unit accuracy cost when the perturbation rate is smaller than 0.25 (please note that FA-GNN fails the fairness attack when the perturbation rate is 0.05). For Pokec-z, FATE-flip and FATE-add achieves a much higher absolute unit accuracy cost when the perturbation rates are 0.20 and 0.25. While for Bail, FATE-flip and FATE-add consistently offers higher absolute unit accuracy cost (except for a marginal decrease for FATE-add with the perturbation rate being 0.10).

We appreciate your constructive comments and valuable feedback for further improving our work. Please see our point-to-point responses as follows.

Q1. Grammatical typos.

Thank you for catching the grammatical errors. We have proofread the paper and fixed them in the revised version (highlighted in blue).

Q2. Missing mathematical formulation of fairness definitions.

Thank you for your kind suggestion. Given the space limitation, we have added a new section in Appendix (i.e., Appendix B) for mathematical formulations and formal definitions of statistical parity and individual fairness. A pointer to Appendix B is also added in Section 2-B.

Q3. Inconsistent organization between letter-based indexing and numerical indexing.

Thank you for your suggestion about consistent indexing. We have changed the indexing in Section 4 to letter-based indexing. Meanwhile, for the second-level indexing, we are using numerical indexing to avoid confusion. For example, numerical indexing ((1), (2), ...) are used in Section 2-C. Please let us know if you would like use to change the second-level indexing to other format and we would be more than happy to accommodate it.

Q4. More discussion about other bias function other than statistical parity.

Thank you for your suggestion. We would like to clarify that, in addition to statistical parity, we instantiate our method by attacking individual fairness in Section 5 and discuss strategies on attacking a specific demographic group in statistical parity and the best/worst accuracy group in Appendix H.D and H.E in the original manuscript. More specifically, for attacking individual fairness, we define the bias function as $b\left(\mathbf{Y}, \Theta^*, \mathbf{S}\right) = \operatorname{Tr}\left(\mathbf{Y}^T \mathbf{L}_{\mathbf{S}} \mathbf{Y}\right)$. For attacking a specific demographic group in statical parity (Appendix H.D), we can set the bias function to either $b\left(\mathbf{Y}, \Theta^*, \mathbf{F}\right) = - \operatorname{P}\left[{\tilde y} = 1 \mid s = a\right]$ to decrease the acceptance rate of demographic group with sensitive attribute value $s=a$ or $b\left(\mathbf{Y}, \Theta^*, \mathbf{F}\right) = \operatorname{P}\left[{\tilde y} = 1 \mid s = 1\right] - \operatorname{P}\left[{\tilde y} = 1 \mid s = 0\right]$ to increase the gap of acceptance rate between group $s = 1$ and group $s = 0$. For attacking the best/worst accuracy group (Appendix H.E), we can set the bias function to be the task-specific loss (e.g., cross-entropy) of the demographic of nodes with best/worst accuracy, which is conceptually similar to adversarial attacks on the utility as shown in Metattack [1], but focusing on a subgroup of nodes determined by the sensitive attribute rather than the validation set. We would highly appreciate if the reviewer could clarify the specific bias function that needs to be discussed, and we would be more than happy to provide additional discussion if possible.

We appreciate your constructive comments and valuable feedback for further improving our work. Please see our point-to-point responses as follows.

Q1. Explain the term `deceptiveness' from an intuitive level.

Thank you for your question. In our revised version (Section 1 paragraph 3), we highlight that "the lower-level problem optimizes a task-specific loss function to maintain the performance of the downstream learning task and enforces budgeted perturbations to make the fairness attacks deceptive". Budgeted perturbations (i.e., imperceptible changes) have been widely adopted in existing works on adversarial attacks for graph neural networks. In addition, we believe a deceptive fairness attack is also important in maintaining the performance of downstream learning task, which is mentioned in Section 2-C in the original manuscript "a performance degradation in the utility would make the fairness attacks not deceptive from the perspective of a utility-maximizing institution." The reason is that it is easy for a utility-maximizing institution to detect the abnormal performance of the graph learning model, which is trained on the poisoned data. Such abnormal performance may trigger the auditing toward model behaviors, which may further lead to the investigation on the data used to trained the model. With careful auditing, it is possible to identify fairness attacks as shown in our analysis of manipulated edges due to significantly more edges that have certain properties (e.g., connecting two nodes with a specific sensitive attribute value). Then the institution might take actions (e.g., data cleansing) to avoid the negative consequences caused by fairness attacks.

Q2. Intuition behind the method being `meta learning'.

Thank you for your question. In our work, as we mentioned in the manuscript, we treat the input graph as a hyperparameter to be learned other than model parameters and apply meta learning to find the suitable hyperparameter (i.e., the input graph) that maximizes the bias function. Similar strategy has been adopted in hyperparameter optimization [1] and in adversarial attacks on the utility of graph neural networks [2], as well as in graph structure learning [3, 4]

References

[1] Franceschi, Luca, et al. "Bilevel programming for hyperparameter optimization and meta-learning." International conference on machine learning. PMLR, 2018.

[2] Zügner, Daniel and Stephan Günnemann. “Adversarial Attacks on Graph Neural Networks via Meta Learning.” ArXiv abs/1902.08412 (2019)

[3] Franceschi, Luca, et al. "Learning discrete structures for graph neural networks." International conference on machine learning. PMLR, 2019.

[4] Xu, Zhe, Boxin Du, and Hanghang Tong. "Graph sanitation with application to node classification." Proceedings of the ACM Web Conference 2022. 2022.