Deceptive Fairness Attacks on Graphs via Meta Learning
Authors: Jian Kang
Yinglong Xia
Ross Maciejewski
Jiebo Luo
Hanghang Tong
Venue: ICLR 2024 poster (2024)
Keywords: graph learning
fairness
adversarial attacks
Primary area: learning on graphs and other geometries & topologies
TL;DR: We develop a meta learning-based poisoning attack strategy to exacerbate unfairness of graph learning models, while preserving the utility in downstream tasks.

Abstract: We study deceptive fairness attacks on graphs to answer the following question: How can we achieve poisoning attacks on a graph learning model to exacerbate the bias deceptively? We answer this question via a bi-level optimization problem and propose a meta learning-based framework named FATE. FATE is broadly applicable with respect to various fairness definitions and graph learning models, as well as arbitrary choices of manipulation operations. We further instantiate FATE to attack statistical parity or individual fairness on graph neural networks. We conduct extensive experimental evaluations on real-world datasets in the task of semi-supervised node classification. The experimental results demonstrate that FATE could amplify the bias of graph neural networks with or without fairness consideration while maintaining the utility on the downstream task. We hope this paper provides insights into the adversarial robustness of fair graph learning and can shed light on designing robust and fair graph learning in future studies.

Published as a conference paper at ICLR 2024
DECEPTIVE FAIRNESS ATTACKS ON GRAPHS VIA META LEARNING
Jian Kang', Yinglong Xia², Ross Maciejewski", Jiebo Luo', Hanghang Tong*
University of Rochester, (jian. kang@, jluo@ cs. rochester.edu
2 Meta, exia@meta.com
3 Arizona State University, mmacieje @asu.edu University of Illinois Urbana-Champaign, htong @ @illinois.edu
ABSTRACT
We study deceptive fairness attacks on graphs answer the following question: How can we achieve poisoning attacks on graph learning model to exucerbate the bias deceptively? We answer this question via a bi-level optimization problem and propose meta marning-basee framework named FATE. FATE is broadly applicable with respect to various fairness definitions and graph learning models, well as arbitrary choices of manipulation operations. We further instantiate FATE to attack statistical parity or individual fairness on graph neural networks. We conduct extensive experimental evaluations real-world datasets in the task of semi-supervised node classification. The experimental results demonstrate that FATR could amplify the bias of graph neural networks with without fairness consideration while maintaining the utility on the downstream task. We hope this paper provides insights into the adversarial robustness of fair graph learning and can shed light on designing robust and fair graph learning in future studies.
INTRODUCTION
Algorithmic fairness on graphs has received much research attention (Bose & Hamilton 2019 Dai &
Wang] 2021: Kang et al., 20200] Li al., [2021] Kang et al., 2022). Despite its substantial progress, existing studies mostly assume the benevolence of input graphs and aim ensure that the bias would not be perpetuated or amplified in the learning process. However, malicious activities in the real world are commonplace. For example, consider financial fraud detection system which utilizes a transaction network to classify whether bank account is fraudulent or not (Zhang et al., 2017] Wang et al., 2019). An adversary may manipulate the transaction network (e.g., malicious banker with access to the demographic and transaction data), so that the graph-based fraud detection model would exhibit unfair classification results with respect to people of different demographic groups Consequently, biased fraud detection model may infringe civil liberty certain financial activities and impact the well-being of an individual negatively (Bureau) 2022). It would also make the graph learning model fail provide the same quality of service to individual(s) of certain demographic groups, causing the financial institutions to lose business in the communities of the corresponding demographic groups. Thus, it is critical to understand how resilient graph learning model is with respect to adversarial attacks on fairness, which we term as fairness attacks.
Fairness attack has not been well studied, and sporadic literature often follows two strategies. The first strategy is adversarial data point injection, which is often designed for tabular data rather than graphs (Solans et al., 202T; Mchrabi al. 2021 Chhabra et al. 2021| Van al., (022). However, in addition to only inject adversarial node(s), it is crucial to connect the injected adversarial node(s) to nodes in the original graph, which requires non-trivial modifications to existing methods, to effectively attack graph learning models. Another strategy is adversarial edge injection, which to date only attacks the group fairness of graph neural networks (Hussain et al.) (022). It is thus crucial to study how to attack different faimesss definitions for variety of graph learning models.
To achieve this goal, we study deceptive faimess attacks on graphs. We formulate it as a bi-level optimization, where the lower-level problem optimizes task-specific loss function maintain the performance of the downstream learning task and enforces budgeted perturbations to make the fairness attacks deceptive, and the upper-level problem leverages the supervision to modify the input

---

Published as a conference paper at ICLR 2024
graph and maximize the bias function corresponding user-defined faimess definition. To solve the bi-level optimization problem. we propose a meta learning- based solver (FATE), whose key idea is to compute the meta-gradient of the upper-level bias function with respect to the input graph to guide the fairness attacks. Compared with existing works, our proposed FATE framework has two major advantages. First, it is capable of attacking any fairness definition on any graph learning model, as long as the corresponding bias function and the task-specific loss function are differentiable. Second, is equipped with the ability for either continuous or discretized poisoning attacks on the graph topology. We also briefly discuss its ability for poisoning attacks on node features in a later section.
The major contributions of this paper are: (A) Problem definition. We study the problem of deceptive fairness attacks on graphs. Based on the definition, we formulate it as a bi-level optimization problem, whose key idea to maximize bias function in the upper level while minimizing task-specific loss function for graph learning task in the lower level; (B) Attacking framework. We propose an end-to-end attacking framework named FATE. It learns a perturbed graph topology via meta learning, such that the bias with respect to the learning results trained with the perturbed graph will be amplified: (C) Empirical evaluation. We conduct experiments on three benchmark datasets to demonstrate the efficacy of our proposed FATE framework in amplifying the bias while being the most deceptive method (i.e., achieving the highest micro Fl score) on supervipee node classification.
2 PRELIMINARIES AND PROBLEM DEFINITION
A - Notations. We use bold upper-case, bold lower-case, and calligraphic letters for matrix, vector, and set, respectively (e.g., A, x, 9). T denotes matrix/vector transpose (e.g., xf is the transpose of x). Matrix/vector indexing is similar to NumPy in Python, e.g., A [i,j] is the entry of A at the i-th row and j-th column; A [i, and A [: are the i-th row and j-th column of A, respectively.
B- Algorithmic fairness. The general principle of algorithmic faireess is to ensure the learning Among several fairness definitions that follow this principle, group fairness (Feldman et al.) 2015 Hardt et al., (016) and individual fairness (Dwork) et al. 2012) are the most widely studied ones. Group faimess splits the entire population into multiple demographic groups by a sensitive attribute (e.g., gender) and ensure the parity of a statistical property among learning results of those groups. For example, statistical parity, a classic group fairness definition, guarantees the statistical independence between the learning results (e.g.. predicted labels) and the sensitive attribute (Feldman et al.] (013). Individual fairness suggests that similar individuals should be treated similarly. It often formulated as a Lipschitz inequality such that distance between the learning results of two data points should be no larger than the difference between these two data points (Dwork et al., 2012). More details are provided in Appendix H
results would not favor one side or another!| !
C- --Prollem definition. Existing work (Hussain et al. 2022) for fairness attacks on graphs randomly injects adversarial edges so that the disparity between the learning results of two different demographic groups would be amplified. However, it suffers from three major limitations. (1) First, it only attacks statistical parity while overlooking other fairness definitions (c.g., individual fairness (Dwork et al.) 2012)). (2) Second, it only considers adversarial edge injection, excluding other manipulations like edge deletion or reweighting. Hence, it is essential to investigate the possibility to attack other fairness definitions on real-world graphs with an arbitrary choice of manipulation operations. (3) Third, it does not consider the utility of graph learning models when attacking fairness, resulting in performance degradation in the downstream tasks. However, an institution that applies the graph learning models are often maximmzin (Liu et al., 2018 Baumann et al. 2022). Thus, a performance degradation in the utility would make the fairness attacks not deceptive from the perspective of a sullit-maxximzzing institution.
In this paper, we seek to overcome the aforementioned limitations. To be specific, given an input graph, an optimization-basse graph learning model, and user-defined fairness definition, we aim to learn a modified graph such that bias function of the corresponding fairess definition would be maximized for effective fairness attacks, while minimizing the task-specific loss function with respect to the graph learning model for deceptive fairness attacks.
Formally, we define the problem of deceptive fairness attacks on graphs. We are given (1) an undirected graph g = {A,X] (2) a task-specific loss function (g, Ovic, Ovic), where Y is the graph learning model output, Oyic is the set of learnable variables of the victim model targeted for
https:/ /ww. mwwri am webater www.err.coomoeeeeeee www.diii//iioo.cco ct faattttaaryy/aaaaaaa
2

---

Published as a conference paper at ICLR 2024
attacking, and vic is the set of hyperparameters of the vietim model, (3) bias function b (Y, Gr, F), where 6% = arg mine,, (g, Y, Ovie Ovie). and F is the matrix that contains auxiliary faimesss- related information (c.g., sensitive attribute values of all nodes in G for group faimess, pairwise node similarity matrix for individual fairness), and (4) an integer budget B. And our goal is to learn a poisoned graph 0 { such that (1) d ( <
B, where d (G.0) the distance between
the input graph 9 and poisoned graph 9 (e.g., . the total weight of perturbed edges A -
vec A - II, (A-
(2) the bias function b (Y, One F) is maximized for effectiveness, and (3) the task-specific loss function (g, Y, Ovio: Ovie) is minimized for deceptiveness.
3
METHODOLOGGY
In this section, we first formulate the problem of deceptive fairness attacks on graphs as a bi-level optimization problem, followed by generic meta learning- based solver named FATE.
3.1 PROBLEM FORMULATION
Given imput graph G {A, X} with adjacency matrix A and node feature matrix X, an attacker aims to learn poisoned graph 9 = A. } such that the graph learning model will be maximally biased when trained on G. In this work, we consider the following settings for the attacker.
The goal of the attacker. The attacker aims to amplify the bias of the graph learning results output by a victim graph learning model. And the bias to amplified a choice made by the attacker based on which fairness definition the attacker aims to attack.
The knowledge of the attacker. Following similar settings (Hussain et al. 2022), we assume the attacker has access to the adjacency matrix, the feature matrix of the input graph, and the sensitive attribute of all nodes in the graph. For a (semi-) suuerviiue learning problem. we assume that the ground-truth labels of the training nodes for a graph- financial fraud detection problem, the malicious banker may have access to the demographic information (i.e., sensitive attribute) of the account holders and also know whether some bank accounts are fraudulent or not, which are the ground-truth labels for training nodes. Similar (Zügner et al., 2018 Zügner & Günnemann! 2019; Hussain et al. 2022), the attacker has no knowledge about the parameters Ovic and By of the victim model. Instead, the attacker will perform a gray-box attack by attacking a surrogate graph learning model with learnable parameters + and hyperparameters Oarr-
also available the attacker. For example,
The capabilitiy of the attacker. The attacker is able to perturb up to B edges/features in the graph
(i.c., the entry-wise matrix norms A
-
A
1,1 I B and/or
X - X
1.1 B).
Based on that, we formulate our problem bi-level optimization problem as follows.
Ç = arg max (Y, O F) s.t.
sur = arg min (G, Oau, 0 d (G, SB 6..
(I)
9
where the lower-level problem learns an optimal surrogate graph learning model θ by minimizing I (G, Y, @ 0, the upper-level problem finds poisoned graph & that could maximize bias function (Y, O F) for the victim graph learning model and the distance between the input graph, and the poisoned graph ( constrained to satisfy the setting about the budgeted attack. Note that Eq. is applicable to attack any fairness definition any graph learning model, as long the bias function b (Y, O F) and the loss function (g. Y, O Osu)) are differentiable.
A Lower-level optimization problem. A wide spectrum of graph lcarning models essen- tially solving an optimization problem. For example, graph convolutional network (GCN) (Kipf & Welling 2017) learns the node representation by aggregating information from its neighborhood and performing nonlinear transformation with model parameters and an activation function. The lower-level optimization problem for an L-layer GCN aims learn the of model parameters
O* (W 1, 1,... L), where ( is the weight matrix in the i-th layer, that could minimize task-specific loss function (c.g., cross-entropy for node classification). For more examples of graph learning models from the optimization perspective, please refers to Appendix A
3

---

Published as a conference paper at ICLR 2024
B B- -Upper-level optimization problem. To attack the faimess aspect of graph learning model, aim to maximize a differentiable bias function b (Y, @ur. F) with respect to a user-defined fairness definition in the upper-level optimization problem. For example, for statistical parity (Feldman et al., 2015), the faimess-related auxiliary information matrix F can he defined as the one-hot demographic membership matrix, where F(i, J] = 1 if and only if node i belongs to j-th demographic group. Then the statistical parity is equivalent to the statistical independence between the learning results Y and F. Based on that, existing studies propose several differentiable measurements of the statistical dependence between Y and F as the bias function. For example, Bose et al. (Bose & Hamilton 2019) use mutual information I I(;; F) as the bias function: Prost al. (Prost et 2019) define the bias function as the Maximum Mean Discrepancy MMD (3%, V1) between the learning results of two different demographic groups Vo and V/-
3.2 THE FATE FRAMEWORK
To solve Eq. ! we propose a generic attacking framework named FATE (Deceptive Fairesss Attacks on Graphs via Meta Learning) to learn the poisoned graph. The key idea is to view Eq. T as meta learning problem, which aims to find suitable hyperparameter settings for a learning task (Bengio 2000), and treat the graph G as a hyperparameter. With that, we learn the poisoned graph 9 using the meta-gradient of the bias function (Y, G F) with respect G. In the following, we introduce two key parts of FATE, including meta-gradient computation and graph poisoning with meta-gradient.
A Meta-gradient computation. The key term learn the poisoned graph is the meta-gradient of the bias function with respect to the graph G. Before computing the meta- trita-rradiet,, we assume that the lower-level optimization problem converges in T epochs. Thus, we first pre-train the lower-level optimization problem by T epochs to obtain the optimal model O sur = (T)) before computing the meta-gradient. The training of the lower-level optimization problem can also be viewed as a dynamic system with ([++)) (pt((+1) (G, O sar Osur, Y), Vt E .T). where
@ refers to Osur at initialization, and opt (-+))))) is an optimizer that minimizes the lower-level loss function / (g. Y, @ 0) at (t 1)-th epoch. From the perspective of the dynamical system, by applying the chain rule and unrolling the training of lower-level problem, the mhta-ggadieen Vgb can be written as V&b- Vab Y. (
F) + _T= A, ................................ -T Verr YY, O F). where (T)
A,- v and B, = V fe (1+1) However, it is computationally expensive in both time and space to compute the meta- grata-gradient.... To further speed up the computation, we adopt first-order approximation the meta-gradient (Finn et al. (017)) and simplify the meta-gradient as
V R esryy (Y,0!
sur F)
VGO sur
Since the input graph is undirected, the derivative of the symmetric adjacency matrix A can be computed as follows by applying the chain rule of a symmetric matrix (Kang et al. 2020).
Vab + Vab+ + (V^ diag (V
For the feature matrix X, its derivative equals to the partial derivative since X is often asymmetric.
B Graph poisoning with meta-gradient. After computing the meta-gradient of the bias function Vgb, we aim to poison the input graph guided by Vib. We introduce two poisoning strategies: (1) continuous poisoning and (2) discretized poisoning.
Continuous poisoning attack. The continuous poisoning attack is straightforward by reweighting edges the graph. We first compute the meta-gradient the bias function Vad, then use it to poison the input graph in a gradient descent-based updating rule as follows.
A + A- Ab
where 7 is learning rate to control the magnitude of the poisoning attack. Suppose we attack the topology for l attacking steps with budgets 5,, 5₁ and Σ 6, = B. In the i-th attacking step, the learning rate should satisfy I
6, [|V/ll., to ensure that constraint on the budgeted attack
Discretized poisoning attack. The discretized poisoning attack aims to select set of edges to be added/deleted. It is guided by a poisoning preference matrix defined as follows.
VA = (1 - (1-2A) o VAb
(5)
4

---

Published as a conference paper at ICLR 2024
where 1 is all-one matrix with the same dimension A and o denotes the Hadamard product. A large positive VA [i. j] indicates strong preference in adding an edge if nodes and j are not connected (i.c., positive V ji positive (1 2A) [č. (.) deleting edge if nodes and j are
connected (i.e., negative Vab b [i, negative (1 2A) [ jD. Then, one strategy to find the set of edges Eaazc to be added/deleted can be greedy selection.
Eattack = topk (VA. 6:)
(6)
where lopk (VA, 6:) selects ó; entries with highest preference score in VA in the i-th attacking step. Note that, if we only want to add edges without any deletion, all negative entries V VAl should be zeroed out before computing Eq. 5 Likewise, if edges are only expected to be deleted, all positive entries should be zeroed out.
Remarks. Poisoning node feature matrix X follows the same steps poisoning adjacency matrix A without applying Eq. 3 And we briefly discuss an alternative edge selection strategy for discretized poisoning attacks via sampling in Appendix G
C- Overall framework. FATE generally works as follows. (1) We first pre-train the surrogate graph
learning model and get the corresponding learning model O
(7) as well as the learning results Y
and 3 (3) Finally, we (2) Then we compute the meta gradient of the bias function using Eqs. 2
perform the discretized poisoning attack (Eqs. 5 and 6 or continuous poisoning attack (Eq. 4 A detailed pseudo-code of FATE is provided in Appendix
D D- Limitationns Since FATE leverages the meta-gradient to poison the input graph, it requires the to be differentiable in order to calculate the meta-gradiens geta-gradieet Vgb. In Sections and we present two carefully chosen bias functions for FATE. And we leave it for future work on exploring the ability of FATE in attacking other fairness definitions. Moreover, though the meta-gradient can be efficiently computed via nuto-differentiation in modern deep learning packages (c.g..PyToue
bias function b Y
O Jurr F
TensorFlow f) it requires O(n²) space complexity when attacking faimess via edge flipping. It is still a challenging open problem on how to efficiently compute the meta- geta-ggrdieet in terms of space. One possible remedy might be low-rank approximation the perturbation matrix formed by Eatack- Since the difference between the benign graph and poisoned graph are often small and budgeted (d (G.G) S B), is likely that the edge manipulations may be around a few set of nodes, which makes the perturbation matrix to be an (approximately) low-rank matrix.
4 INSTANTIATION #1: STATISTICAL PARITY ON GRAPH NEURAL NETWORKS
Here, we instantiate FATE framework by attacking statistical parity on graph neural networks in a binary node classification problem with a binary sensitive attribute. We briefly discuss how to choose (A) the surrogate graph learning model used by the attacker, (B) the task-specifie loss function the lower-level optimization problem and (C) the bias function in the upper-level optimization problem.
Surrogate graph learning model. We assume that the surrogate model is a 2-layer lincar GCN (Wu et al. 2019) with different hidden dimensions and model parameters at initialization.
- Lower-level loss function. We consider a semi-supervised node classification task for the graph neural network to be attacked. Thus, the lower-level loss function is chosen as the cross entropy between the ground-truth label and the predicted label: 1 [G, Y, 0uur Buur) = Viniel Σievin Σ5= Vi..j In De. where Viaai is the set of training nodes with ground-truth labels with Viranl being its cardinality, e is the number of classes, Yi.j is a binary indicator of whether node i belongs class j and fi.j is the prediction probability of node belonging to class j.
C-Upper-level bias function. We aim to attack statistical parity in the upper-level problem, which asks the predicted label ÿ to follow P j
P 1|s = 1]. Then the bias function is defined as b ( 0z S) = [ = 1] - P ū = 1= 1/. Suppose p (Tr.1 ) is the probability density function (PDF) of T.,1 for any node and p ( 1) is the PDF of Ui,1 for any node i
belong to the demographic group with sensitive attribute value s = 1. We observe that P [ğ =
and P Lύ- 1|s 1] are equivalent to the complementary cumulative distribution functions (CDF)
https://pytorch..o https://ww.tensnt/
5

---

Published as a conference paper at ICLR 2024
of p [1.1 2)) and p (Us.1 2/1s = 1), respectively. For differentiable estimation of P [ÿ and
P P 1|s 1]. we use kernel density estimation (KDE) for p (3r,1 > > and p (ûi.1 > 1 = 1). Definition (Kernel density estimation (Chen 2017) Given a set of n HDD samples {rı,..., In) drawn from a distribution with an unknown probability density function (PDF) f. the kernel density estimation of f at point T is defined as follows.
[(r)
nu
where [ is the estimated PDF, Skk is the kernel function and a is non-negative bandwidth.
Moreover, we assume the kernel function in KDE the Gaussian kernel f& (x) -e
<22 c 222 How-
ever, computing the complementary CDF of a Gaussian distribution is non-trivial. Following (Cho et al. 2020), leverage tractable approximation of the Gaussian Q-function follows.
Q(T) (T) J.
fa(z)dx ee -erar-- -3r-y
(8)
where f& (x) = 2/2m e x² /2 is a Gaussian distribution with zero mean, a = 0.4920, ,3 = 0.2887, ? 1.1893 (Lééez-Benítez & Casadevall 2011). How estimate P [ύ 1] is follows.
For any node i, get its prediction probability Di,1 with respect to class 1;
Estimate the complementary CDF P [ = 1] using a Gaussian KDE with bandwidth a by
[ = 1] = +. E exp -a 0.5 0.5-
2
0.5 0.5- 7). where a 0.4920, | =
0.2887, 7 1.1893 and exp(x) = 6."
Note that P [ū = 1|8 1] can be estimated with a similar procedure with minor modifications. The only modifications needed are: (1) get the prediction probability of nodes with and (2) compute the CDF using the Gaussian Q-function over nodes with = rather than all nodes in the graph.
INSTANTIATION #2: INDIVIDUAL FAIRNESS ON GRAPH NEURAL NETWORKS
We provide another instantiation of FATE framework by attacking individual fairness on graph neural networks. Here, we consider the same surrogate graph learning model (i.e., 2-layer linear GCN) and the same lower-level loss function (i.c., cross entropy) as described in Section 4 To attack individual fairness, we define the upper-level bias function following the principles in (Kang et al.) 2020): the fairness-related auxiliary information matrix F is defined as the oracle symmetric pairwise node similarity matrix S (i.e., F S), where S [i, measures the similarity between node and node j. And the overall individual bias is defined as Tr (Y" Lg Y). where Lg is the Laplacian matrix of S. Assuming that Y is the output of an optimization-bann based graph learning model, Y can be viewed as function with respect to the input graph G, which makes Tr Ly Y) differentiable with respect to G. Thus, the bias function (-) can be naturally defined as the overall individual bias of the input graph G, i.e., b b( O O Tr Ly)
EXPERIMENTS
6.1 ATTACKING STATISTICAL PARITY ON GRAPH NEURAL NETWORKS
Settings. We compare FATE with baseline methods: Random, DICE-S, and FA-GNN. Specifically, Random is heuristic approach that randomly injects edges to the input graph. DICE-S is a variant of DICE (aanick et al. 2018). It randomly deletes edges between nodes from different demographic groups and injects edges between nodes from the same demographic groups. FA-GNN (Hussain et al. 2022) attacks the fairness of a graph neural network by adversarially injecting edges that connect nodes in consideration of both their class labels and sensitive attribute values. We evaluate all methods under the same setting as Section 4 That is, the fairness definition to be attacked is statistical parity; the downstream task is binary semi-supervised node classification with binary sensitive attributes. The experiments are conducted on 3 real-world datasets, i.e., Pokec-n, Pokec-z, sets.
and Bail. Similar existing works, For all methods, the victim models are set to GCN (Kipf & Welling 2017). For each dataset, we use fixed random seed to learn the poisoned graph corresponding each baseline method. Then
the 50%/25%/255 splits for craiiing/valdaation//ee

---

Published as a conference paper at ICLR 2024
Table 1: 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 better (1) for micro F1 score (Micro F1) and Asp (bias). Bold font indicates the most deceptive faimess attack, i.e., increasing Asp and highest micro Fl. Underlined cell indicates the failure of fairness attack, i.e., decreasing Asp after attack.
Dataset
Pth
Micro CT
Randum
Agg (1)
Miero PL())
DICESS
Aar (1)
Micro FTCT
FA-GNN
Agr [T3
Micro FT
FAVE-llip
Axr
Micre F1
FAYE-add
0.00
07.5
+ 0.5
7.1
67.5 10--00 0.5
7.1
07.5 + 0.3
71++0.4 0.0
07.5 0.3
7.1-0.
07.5 17.5+10 0.3
+1
0.05
88.0
0.3
6.2088
67.6
7.1
67.8 1.1
5.4
67.9 0.4
9.2-12
67.9 0.4
9.3112
Pokec-n
0.10
0:15
86.8
I6.7
0.5
0.
6..
67.0 0.5
79=00
7.2
06.0 0.22
0600 0..4
11511:0.
68.2 0.6
08.0=033
11:==0
9-- 1.5
0..
6822 0.6
115==0
9.5
8.++1
7.1-1.2
05.6
18.4+0.7
0822-0.
120-18
08.2+
120-1.8
06-2
0.5+08
6.6
06.6
08.3+0.4
0..
18.4
03:00
68.4
6.
05.12003
6::005
0:000
0.4
0.6
68
5.7
68.1
2.4
08.7
6.7
08.7 0.4
1.7
Polecx
0:15
0:10
68
07.0 0.3
8.0++00 0.0
0.1++0.8
0V.55
07.1
0.5
333
67.7 0-04
13.5
16.9
08.7
09.0 0.8
R.5
7-5-0- 0.7
08.7 0.8
60.0 0.8
0.7
0.20
68.5
1. 0.4
0.0
07.00 0.5
3.9
06.1 1.0.2
25.4 1.3
68.5 0.6
8.8 1.1
68.3 0.6
88111
0:25
18.3
+
0.5
07.4 = 1.C.
3.8
11.
65.6 +-6.6
22.4422..8
68.5 1.1
8.=225
68.5
86+25
0.00
10.1
1: 0.2
93.1
= 0.2
8.0 0.2
R8.1 2.0.2
503302
1551 1052
8.0
051 1.02
0.
11115
92.7
1: 0.2
8.1 0.0
92.3
0 0.2
3.4 0.2
91.7 1.0.1
10.0 1.4
0..1
8.6-2..1
92.5 2.11
0.6
Ball
0.10
0.15
91.9
02.2
1 0.2
= 0.2
T.8.022
0.8
92.2 0.2
921
88=01
8,5 0.3
90.3 1.0.
90.0 0.2
10.3 1.04
92.4 1 0.1
M2.2
+ 0.2
8.9 0.1
8.1
92.3+ 0.1
92.4 0.1
8.110.1
9.1
1.200
91.6
0.1
91.8
9.12022
89.7 6.1
0.4
92.2 0:2
0.3
92.3
0.3
0.25
01.4++0.1
8.3+0.1
91.0 0.2
9.3
808
5.2+0..
92.1 + 0.1
0.1-0.2
02.1+00.1
0.1
train the victim model 5 times with different random seeds. For fair comparison, we only attack the
adjacency matrix. Please refer to Appendix C for detailed experimental settings.
Main results. For FATE, we conduct fairness attacks via both edge flipping (FATE-flip) and edge addition (FATE-add). For all other baseline methods, edges are only added. The effectiveness of fairness attacks on GCN are presented in Table From the table, we have the following key observations: (A) FATE-flip and FATE-add are the only methods that consistently succeed in fairness attacks, while all other baseline methods might fail in some cases (indicated by the underlined Asp) because of the decrease in Asp. Though DICE-S consistently succeeds in fairness attacks on Pokec-n and Bail, its utility is worse than FATE-flip and FATE-add, making it less deceptive. (B) FATE-flip and FATE-add not only amplify Asp consistently, but also achieve the best micro F1 score on node classification, which makes FATE-flip and FATE-add more deceptive than all baseline methods. Notably, FXTE-flip and FATE-add are able to even increase micro Fl score on all datasets, while other baseline methods attack the graph neural networks at the expense of utility (micro F1 score). (C) Though FA-GNN could make the model more biased in some cases, it cannot guarantee consistent success in fairness attacks on all three datasets as shown by the underlined Asp in both tables. All in all, our proposed FATE framework consistently succeeds in fairness attacks while being the most deceptive (i.e., highest micro Fl score).
Effect of the perturbation rate. From Table 1 first, Asp tends to increase when the perturbation rate increases, which demonstrates the effectiveness of FATE-flip and FATE-add for attacking fairness. Though in some cases Asp might have marginal decrease, FATE-flip flip and FATE-add still successfully attack the faimess compared with GCN trained on the benign graph by being larger to the Asp when perturbation rate (Ptb.) is O. Second, FATE-flip and FATE-add are deceptive, meaning that the micro Fl scores is close to or even higher than the micro Fl scores on the benign graph compared with the corresponding metrics trained on the poisoned graphs. In summary, across different perturbation rates, FATE-flip and FATE-add are both effective, i.e., amplifying more bias with higher perturbation rate, and deceptive, i.e., achieving similar or even higher micro Fl score.
same
different
Pokec-n
Pokec-z
Bail
Pokec-n
Pokec-z
Bail
Ratio
Rotio
Ratio
Ratio
Ratio
Iebel
ettr
Isbel
sen, attr.
Istrll
set ettr.
SL
SSA
SL (b)
SSA
SL
SSA
(a)
Figure 1: Attacking statistical parity with FATE-flip. (a) Ratios of flipped edges that connect two nodes with same/different label or sensitive attribute (sens. attr.). (b) SL (abbreviation for same label) refers
to the ratios of flipped edges whose two endpoints are both from the same class. SSA (abbreviation for same sensitive attribute) refers the ratios of manipulated edges whose two endpoints are both from the same demographic group. Majority/minority classes are determined by splitting the training nodes based on their class labels. The protected group is the demographic group with fewer nodes. Analysis on the manipulated edges. Here, we aim to characterize the properties of edges that are flipped by FATE (i.e., FATE-flip) in attacking statistical parity with perturbation rate 25%. The reason
7

---

Published as a conference paper at ICLR 2024
Table 2: Attacking individual fairness 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 better (1) for micro Fl score (Miero FI) and InFoRM bias (Bias). Bold font indicates the most deceptive fairness attack, i.e., increasing bias and highest micro FI. Underlined cell indicates the failure of fairness attack, i.e., decreasing bias after attack.
Dataset
Pth.
Miero PT
Random
Blas [-3
Mikro FT
DICE-S
Blas C1
Micro FT())
FA-GNN
Miaro FTC)
FATE-Blip
Blas C1
Micro FT
FxTE-ada
61.5
11.3
0.2
61.5 0.3
0.9 0.2
6.3
09102
61.5 0.3
1.2
67. 0.3
09102
0.05
1.300.3
68.1 0.2
20-006
0.5
1.9+02
6.38-0.3
1.240..
676+03
15+06
Pokec-n
0.15
07.2 =
1.200.3
1.2
66.0
67.4-63
1.3.0.3
L3402
67410.
861203
121.02
15
67.0104
078404
13:00
12402
677.04
076
161104
11203
0:20
67.3-633
1.5++0.5
65.7+06
1.++03
67.3
1.1+00.3
68.2+10
1.7+00.8
0.25
66.7
1 0.5
13-0.4 0.4
06.6_0.5 0.5
1.3 1.3.0.1
6..2..5
13104
67.8008
1.410.7
6.
1.4107.
0.00
05.4
1: 0.4
2.8 U.Y
08.3
0.4
2.6 20.
05:11:04
261007
05.4 0.4
2.0 0..
2611/7
0.00
03.0 a: 01.4
3.4 11.5
68.9
1 0.5
3.9
88.1 0.4
2.3
68.7=11A 11.5
2.9
0..
3.1 1.0
Pokee-
0.15
0.10
08.7
67.0
+ 0.1
0.3
2.4-0.3 0..
2.5 0.5
60.1
68.1 0.2
0.2
3.5 0.8
3.6 0.4
08 0..3++0.55
0.0
0.7+
13
08.6
69.0
0.5
0.6
2.9 0.6
2.9 1.0
00.0+00.
69.0
30++06
2.04
0.201
0.6
18 (1.
08.8
2.3
2.0+0..7
2.6
S5.1
0.6
55.1
022
1.2
50.1
721006
0.85
02:1
8.0=11
02.3
2.7
0.7
7-8 1,0
929+02
7.7 1.0
Buil
0.15
0.10
91.3
91.0
6:
0.1
6.5
7:3 1-2
019
92.1
92.2
0.2
0.2
7.7
8.0 1.8
2.4
01
89 0.1
5.2 01
93.1
83
101
8.2 0.6
0.0
50.0 0.2
92
791008
78408
0.20
91.2-
0.2
6.6
0.6
91.8
0.1
7.1
+ 1.2
00.5+0011
5.5 0.4
93.1
+.1
7.9 0.6
98.1 + +.1
8.2 0.6
0.25
90.9
0
0.1
0.5
0.5
91.5
01
003
00
5.100
0.5
02.9
0.1
1.6
93.0
11.0100
0.2
7.7
to only analyze FATE-flip is that the majority of edges manipulated by FATE-flip on all datasets is by addition (i.e., flipping from non-existing to existing). Figure Tbj suggests that, if two endpoints of a manipulated edge share the same class label or sensitive attribute value, these two endpoints are most likely from the minority class and protected group. Thus, FATE would significantly increase the number of edges that are incident to nodes in the minority class and/or protected group.
More experimental results. Due to the space limitation, we defer more experimental results on attacking statistical parity on graph neural networks in Appendix More specifically, we present the performance evaluation under Macro Fl and AUC, as well as the effectiveness of FATE with FairGNN (Dai & Wang 2 for statistical parity as the victim model.
6.2 ATTACKING INDIVIDUAL FAIRNESS ON GRAPH NEURAL NETWORKS
Settings. To showease the ability of FATE on attacking the individual fairness (Section 5 we further compare FATE with the same set of baseline methods (Random, DICE-S, FA-GNN) on the same set of datasets (Pokec-n, Pokec-z, Bail). We follow the settings as in Section S We use the 50% splits for train/validation/tes sets with GCN being the victim model. For each dataset, we use fixed random seed to learn the poisoned graph corresponding to each baseline method. Then we train the victim model 5 times with different random seeds. And each entry in the oracle pairwise node similarity matrix computed by the cosine similarity of the corresponding rows in the adjacency matrix. That is, S[ cos (A [ē. :] (..)). where cos () is the function to compute cosine similarity. For a fair comparison, we only attack the adjacency matrix in all experiments. Please refer Appendix C for detailed experimental settings.
Main results. We test FATE with both edge flipping (FATE-flip) and edge addition (FATE-add), while all other baseline methods only add edges. From Table 2 we have two key observations. (A) FATE-flip and FATE-add are effective: they are the only methods that could consistently attack individual fairness whereas all other baseline methods mostly fail to attack individual fairness. (B) FATE-flip and FATE-add are deceptive: they achieve comparable or even better utility on all datasets compared with the utility on the benign graph. Hence, FATE framework is able achieve effective and deceptive attacks to exacerbate individual bias.
Effect of the perturbation rate. From Table 2 we obtain similar observations as in Section 6. for Bail dataset. While for Pokec-n and Pokec-z, z, the correlation between the perturbation rate (Ptb.) and the individual bias is weaker. One possible reason that: for Pokec-n and Pokec-z, the discrepancy between the oracle pairwise node similarity matrix and the benign graph is larger. Since the individual bias is computed using the oracle pairwise node similarity matrix rather than the benign/poisoned adjacency matrix, higher perturbation rate to poison the adjacency matrix may have less impact on the computation of individual bias.
Analysis on the manipulated edges. Since the majority of edges manipulated by FATE-fli is through addition, we only analyze FATE-flip here with perturbation rate 25%. From Figure 2 we can find out that FATE tends to manipulate edges from the same class (especially from the minority class). In this way, FATE would find edges that could increase individual bias and improve the utility of the minority class in order make the faimess attack deceptive.
8

---

Published as a conference paper at ICLR 2024
different
majonity class
minerity class
Pokec-n
Pokec-z
Bail
Bail
Pakec-z (b)
Pokac-n
(a)
Figure 2: Attacking individual fairness with FATE-flip. (a) Ratios of flipped edges that connect two
nodes with same/different label. (b) Ratios of flipped edges whose two endpoints are both from the majority/minonn class. Majority/minority classes are formed by splitting the training nodes based on their class labels.
More experimental results. Due to the space limitation, we defer more experimental results on attacking individual fairness on graph neural networks in Appendix [ More specifically, we present the performance evaluation under Macro Fl and AUC, as well as the effectiveness of FATE with InFoRM-GNN (Kang al. 2020), which mitigates individual bias, as the victim model.
7 RELATED WORK
Algorithmic fairness on graphs aims obtain debiased graph learning results such that pre-detined fairness measure can be satisfied with respect to the nodes/edges in the graph. Several definitions of the fairness have been studied so far. Group fairness in graph embedding can be ensured via several strategies, including ad adversarial learning (Bose & Hamilton 2019: Dai & Wang 202I). biased random walk (Rahman et al., 2019 Khajehnejad et al. (022), bias-free graph generation (Wang et al. 2022), and dropout (Spinelli et al. 2021). Individual fairness on graphs can be ensured via Lipschitz regularization (Kang et al. 2020) and learning-to- toriinnktt--akkk (Dong et al. 2021). Other than the aforementioned two fairness definitions, several other fairness definitions are studied in the context of graph learning, including counterfactual fairness (Agarwal et al. 202 Ma et al., (02T). degree fairness (Tang al. 2020 Kang al.) 2022 Liu et al. (023b), dyadic fairness (Masrour al., 2020 Li et 2021 and max-min fairness (Rahmattalab) et al. [019 T I'snng et al. al.19) For a comprehensive review of related works, please refer to recent surveys (Zhang et al. |0222 Choudhary ct al. 2022 Dong et al. 2022) and tutorials (Kang & Tong 2021 2022). It should be noted that our work aims to attack fairness rather than ensuring fairness as in the aforementioned literature.
Adversarial attacks on graphs aim to exacerbate the utility of graph learning models by perturbing the input graph topology and/or node features. Several approaches have been proposed to attack graph learning models, including reinforcement learning (Dai et al., 2018), bi-level optimization (Zügner al. 2018: Zügner Günnemann 2019), projected gradient descent (Sun al., [2018] Xu al. 2019). spectral distance perturbation (Lin et al.) (2022), and edge haapiiingggiiiggggggggg (Bojchevski & Günnemann 2019: Ma et al. 202T). Other than adversarial attacks that worsen the utility of graph learning model, few efforts have been made to attack the fairness of machine learning model for
IID tabular data via label flipping (Mehrabi et al., 202I). adversarial data injection (Solans et al.
2021 Chhabra et al. 202I). adversarial sampling Van al. 2022). Different from (Solans et al.
2021 Mehrabi et al.] 2021 Chhabra et al. 2021 Van et al.] 2022), we aim to poison the input graph via structural modifications the topology rather than injecting adversarial data sample(s). The most related works to our proposed method are (Hussain et al. 2022) and (Zhang et al. (023). Hussain et al. (2022) degrades the group fairness of graph neural networks by randomly injecting edges for nodes in different demographic groups and with different class labels. In contrast, our proposed method could attack any fairness definition for any graph learning models via arbitrary edge manipulation operations in consideration of the utility of the downstream task, as long as the bias function and the utility loss are differentiable. /Zhang al. (203)) is a concurrent study which utilizes zeroth-order optimization instead of gradient-based solution as FATE to solve similar bi-level problem.
CONCLUSION
We study deceptive fairness attacks on graphs, whose goal is to amplify the bias while maintaining or improving the utility on the downstream task. We formally define the problem as bi-level optimization problem, where the upper-level optimization problem maximizes the bias function with respect to a user-defined fairness definition and the lower-level optimization problem minimizes a task-specific loss function. We then propose meta learning- based framework named FATE to poison the input graph using the meta- trtadggrddenttt of the bias function with respect to the input graph. We instantiate FATE by attacking statistical parity on graph neural networks in a binary node classification problem with binary sensitive attributes. Empirical evaluation demonstrates that FATE is effective (amplifying bias) and deceptive (achieving the highest micro FI score).

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work is partially supported by NSF (2134079, 1939725, 2316233, 2238208), DHS (T7STQAC00001-07-00 I7STQACC0001-06-000) and NIFA 2020-67021-32799) The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of U.S. Department of Homeland Security.
ETHICAL STATEMENT
The goal of this paper is to investigate the possibility of making the graph learning results more biased, in order to raise the awareness of fairess attacks. Meanwhile, our experiments suggest that existing fair graph neural networks suffer from the fairness attacks, which further highlight the importance of designing robust and fair techniques to protect the civil rights of marginalized individuals. We acknowledge that the proposed method FATE, if misused, could impact the integrity and fairness of graph learning models. When used for commercial purpose, FATE might cause civil rights violation(s) and could he harmful to individuals from certain demographic groups. To prevent the negative societal impacts, the code will be publicly released under CC-BY-NC-ND license upon publication, which prohibits the use of FATE for any commercial purposes, and explicitly highlight in the released code that any use of the developed techniques should be consulted with the authors for permission first.
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pp. 2114-2124. PMLR, 2021.
Joachim Baumann, Anikó Hannák, and Christoph Heitz. Enforcing group fairness in algorithmic decision making: Utility maximization under sufficiency. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 2315-2326, 2022.
Yoshua Bengio. Gradient-basee optimization hyperparameters. Neural computation, 12(8):
1889-1900, 2000.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. International Conference on Machine Learning, pp. 695-704. PMLR, 2019.
Avishck Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference on Machine Learning, pp. 715-724. PMLR, 2019.
Consumer Financial Protection Burcau.
CFPB targets unfair discrimination in con- sumer finance. http:::/www..cosuuuuiiinnaeeeee www.://annn....//aaaoaaaooa/o us /neeswwwsree room/ uwf.irn-rurur www.aairaiisseriinaaaaaaaaoiooie line; accessed 13-April-0023).
cfpb-targets betssetssurfaai-ddeee
wwwnnnoonsume---nee consumer--inance 2022. [On-
April Chen, Ryan Rossi, Nedim Lipka, Jane Hoffswell, Gromit Chan, Shunan Guo, Eunyee Koh, Sungchul Kim, and Nesreen K Ahmed. Graph learning with localized neighborhood fairness. arXiv preprint arXiv:2212.12042 2022.
Yen-Chi Chen. A tutorial on kernel density estimation and recent advances. Biostatistics & Epidemi- ology, 1(1):161-877, 2017.
Badr-Eddine Chérief-Abbelladde and Pierre Alquier. Mmd-bayes: Robust bayesian estimation via maximum mean discrepancy. Symposium on Advances Approximate Bayesian Inference, pp- 1-21. PMLR. 2020.
Anshuman Chhabra, Adish Singla, and Prasant Mohapatra. Faimeess degrading adversarial attacks against clustering algorithms. arXiv preprint arXiv:21 12020, 2021.
10

---

Published as a conference paper at ICLR 2024
Jaewoong Cho, Gyeongjo Hwang, and Changho Suh. A fair classifier using kemnel density estimation. Advances in neural information processing systems, 33:15088 15099, 2020.
Manvi Choudhary, Charlotte Laclau, and Christine Largeron. A survey on fairness for machine learning graphs. arXiv preprint arXiv:2205. 2022.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 680-688, 2021.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning, pp. 1115-1124. PMLR, 2018.
Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairness for graph neural networks: ranking based approach. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pp. 300-310, 2021.
Yushun Dong. Jing Ma, Chen Chen, and Jundong Li. Fairesss in graph mining: A survey. arXiv preprint arXiv:2204. 098888, 2022.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faimesss through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259-268, 2015.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning. pp. 1126-1135 PMLR, 2017.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Hussain Hussain, Meng Cao, Sandipan Sikdar, Denis Helic, Elisabeth Lex, Markus Strohmaier, and Roman Kern, Adversarial inter-group link injection degrades the fairness of graph neural networks. arXiv preprini arXiv: arXiv:2209.05957. 2022.
Jian Kang and Hanghang Tong. Fair graph mining. In Proceedings of the 30th ACM International Conference on Information Knowledge Management, pp. 4849 4852, 2021.
Jian Kang and Hanghang Tong. Algorithmic fairness on graphs: Methods and trends In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4798-4799, 2022.
Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. Inform: Individual faimess on graph mining. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 379-389, 2020.
Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. Rawlsgen: Towards rawlsian difference principle on graph convolutional network. In Proceedings of the ACM Web Conference 2022, pp. 1214-1225, 2022.
Ahmad Khajehnejad, Moein Khajehnejad, Mahmoudreza Babaei, Krishna P Gummadi, Adrian Weller, and Baharan Mirzasoleiman. Crosswalk: Fairness-enhanced node representation learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 11963-11970 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Peizhao Li. Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic faimess: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
11

---

Published as a conference paper at ICLR 2024
Lu Lin, Ethan Blaser, and Hongning Wang. Graph structural attack by perturbing spectral distance. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 989-998, 2022.
Xiao Lin, Jian Kang, Weilin Cong, and Hanghang Tong. Bemap: Balanced message passing for fair graph neural network. arXiv preprint arXiv:2306.04107, 2023.
Haoran Liu, Bokun Wang, Jianling Wang, Xiangjue Dong, Tianbao Yang. and James Caverlee. Every- thing perturbed all at once: Enabling differentiable graph attacks. arXiv preprint 11X112230..1514, 2023a.
Lydia T Liu, Sarah Dean, Esther Rolf, Max Simehowitz, and Moritz Hardt. Delayed impact of fair machine learning. In International Conference on Machine Learning, pp. 3150-3158. PMLR, 2018.
Zemin Liu, Trung-Kien Kien Nguyen, and Yuan Fang. On generalized degree faimess in graph neural networks. arXiv preprint 2302:2230.00881, 2023b.
Miguel López-Beníez and Fernando Casadevall. Versatile, accurate, and analytically tractable approximation for the gaussian q-function. IEEE Transactions on Communications, 59 922, 2011.
Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. Graph adversarial attack via rewiring. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1161-1169, 2021.
Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian. Bursting the filter bubble: Faimess-awaar network link prediction. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 841-848, 2020.
Ninarch Mchrabi, Muhammad Naveed, Fred Morstatter, and Aram Galstyan. Exacerbating algorith- mic bias through fairness attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8930-8938, 2021.
Flavien Prost, Hai Qian, Qiuwen Chen, Ed H Chi, Jilin Chen, and Alex Beutel. Toward a better trade-off between performance and fairness with kernel-based distribution matching, arXiv preprint arXiv: 2019.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 3289 02999,329590000 2019.
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic fairness in robust graph covering problems. Advances in Neural Information Processing Systems, 32, 2019.
David Solans, Battista Biggio, and Carlos Castillo. Poisoning attacks algorithmic fairness. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14-18, 2020, Proceedings, Part I, pp. 162-177. Springer, 2021.
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions Artificial Intelligence, 3(3):344-3355 2021.
Mingjie Sun, Jian Tang, Huichen Li, Bo Li, Chaowei Xiao, Yao Chen, and Dawn Song. Data poisoning attack against unsupervised node embedding methods. arXiv preprint arXiv:1810. 2018.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases graph convolutional networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 1435-1444, 2020.
12

---

Published as a conference paper at ICLR 2024
Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-fairen in influence maximization. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 5997-6005, 2019.
Minh-Hao Van, Wei Du, Xintao Wu, and Aidong Lu. Poisoning attacks on fair machine learning. In International Conference on Database Systems for Advanced Applications, pp. 370-386. Springer, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Daixin Wang. Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 598-607. IEEE, 2019.
Nan Wang, Lu Lin, Jundong Li, and Hongning Wang. Unbiased graph embedding with biased graph observations. In Proceedings of the ACM Web Conference 2022, pp. 1123-1433, 2022.
Marein Waniek, Tomasz Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, (2)):139-147, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin- Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topol- ogy attack and defense for graph neural networks: An optimization perspective. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 33939-3996 2019.
Binchi Zhang, Yushun Dong, Chen Chen, Yada Zhu, Minnan Luo, and Jundong Li. Adversarial attacks on fairness of graph neural networks. arXiv preprint arXiv:2310. 13822, 2023.
Si Zhang, Dawei Zhou, Mehmet Yigit Yildiri,, Scott Alcorn, Jingrui He, Hasan Davuleu, and Hanghang Tong. Hidden: Hierarchical dense subgraph detection with application to financial fraud detection. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 570-578. SIAM, 2017.
Wenbin Zhang, Jeremy C Weiss, Shuigeng Zhou, and Toby Walsh. Fairness amidst non-iid graph data: A literature review. arXiv preprint arXiv:2202.07170 2022.
Qi Zhu, Natalia Ponomarcva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data, Advances in Neural Information Processing Systems, 34:27965-27977 27977, 2021.
Qi Zhu, Yizhu Jiao, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi, Explaining and adapting graph conditional shift. arXiv preprint arXiv:2306.03256. 2023.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Representations, 2019.
Daniel Zügner, Amir Akbarnjadd, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847-2856, 2018
13

---

Published as a conference paper at ICLR 2024
ORGANIZATION OF THE APPENDIX
The supplementary material contains the following information.
Appendix A provides additional examples of graph learning models from the optimization perspec- tive.
Appendix presents the pscudocode of FATE.
Appendix offers the detailed parameter settings regarding the reproducibility this paper.
Appendix provides additional experimental results on using FairGNN (Dai Wang. 202T) and evaluating under macro Fl score and AUC score.
Appendix - provides additional experimental results on using InFoRM-GNN (Kang et al. 2020 and evaluating under macro F1 score and AUC score.
Appendix [F] shows the transferability of using FATE to attack the statistical parity individual fairness of the non-convolutional aggregation-bal basedd graph attention network with linear GCN as the surrogate model.
Appendix G provides further discussions (1) the relationship between fairness attacks and the impossibility theorem as well as Metattack (Zigner Günnneaann] 2019), (2) an alternative perturbation set selection strategy via sampling, (3) the potential of FATE on attacking the fairness of a specific demographic group, and (4) justification of applying kernel density estimation on non-IID graph data.
Appendix OppendixHHpreeentt more details of statistical parity and individual fairness.
Code can be found at the following repository:
bttps://github.cm com wwtpo////////a////ac
A GRAPH LEARNING MODELS FROM THE OPTIMIZATION PERSPECTIVE
Here, we discuss four additional non parameterrzzed graph learning models from the optimization perspective, including PageRank, spectral clustering, matrix factorization-based completion and first-order LINE.
Model #1: PageRank. It is one of the most successful random walk based ranking algorithm to measure node importance. Mathematically, PageRank solves the linear system
cP (1 1 e)e
where is the damping factor, P is the propagation matrix and is the teleportation vector. In PageRank, the propagation matrix P is often defined as the row-normalized adjacency matrix of graph & and the teleportation vector Equivalently, given damping factor e and teleportation vector e, the PageRank vector Y can be learned by minimizing the following loss function
uniform distribution 1 with 1 being vector filled with 1.
min
T (I - P)r + (1 c)(lr -
(10)
where (I.T (I- is smoothness term and (1 - c) |r el the fairness of PageRank with FATE, the attacker could attack a surrogate PageRank with different choices of damping factor and/or teleportation vector e.
2 is query-specific term. To attack
Model #2: Spectral clustering. It aims to identify clusters of nodes such that the intra-cluster connectivity maximized while inter-cluster connectivity are minimized. To find & clusters of nodes, spectral clustering finds soft cluster membership matrix Y = C with orthonormal columns by minimizing the following loss function
min
Tr LC
(11)
where L is the (normalized) graph Laplacian of the input graph G. It is worth noting that the columns of learning result C is equivalent the eigenvectors of L associated with smallest & eigenvalues. To
14

---

Published as a conference paper at ICLR 2024
attack the fairness of spectral clustering with FATE, the attacker might attack surrogate spectral clustering with different number of clusters k.
Model #3: Matrix factorization-baase completion. Suppose we have bipartite graph g with ni users, 02 items and m interactions between users and items, Matrix factorization- based completion aims to learn two low-rank matrices n1 matrix U and an n2 x matrix V such that the following loss function will be minimized
min U.V
|| proja (R (R- -V?) 18 A + IVI
(12)
where A
R
10 R /
with On, being an n1 X ni square matrix filled with 0, Q2
((i,)) is observed) is the set of observed interaction between any user and any item projn (Z) [ equals to Z(i,) j] if (i.j) E S and O otherwise, a and Ag are two hyperparameters for regularization. To attack the fairness of matrix factorization-base completion with FATE, the attacker could attack surrogate model with different number of latent factors
skip-gram -oa-grrmm based node embedding model. The key idea of first-order LINE is to map each node into a hi-dimensional space such that the dot product of the embeddings of any two connected nodes will small. To achieve this goal, first-order LINE essentially optimizes the following loss function
Model #4: First-order LINE.
max
Aii (logg (H..))[( + +E (log (H
(13)
where H is the embedding matrix with H [ being the h--dimensional emhedding of node i, g(x) = 1/(1 e-)) is the sigmoid function, is the number of negative samples and P. is the distribution for negative sampling such that the sampling probability for node is proportional to its degree deg,- For victim first-order LINE, the attacker could attack surrogate LINE (Ist) with different dimension h in the embedding space and/or a different number of negative samples g.
Remarks. Note that, for a non-parameterized graph learning model (e.g., PageRank, spectral clustering, matrix completion, first-order LINE), we have θ = (Y} which is the set of learning results. For example, we have = (r) for PageRank, = (C) for spectral clustering, = {U, V) and θ (H) for LINE (Ist). For parameterized graph learning models (e.g., GCN), θ refers to the set of learnable weights, e.g., θ [W(1), W(L) for an L-layer GCN.
B PSEUDOCODE OF FATE
Algorithm D summarizes the detailed steps on fairness attack with FATE. To specific, after initialization (line 1), we pre-train the surrogate graph learning model (lines 4 6) and get the pre-trained surrogate model ( as well as learning results (2)) (line 7). After that, we compute the meta gradient of the bias function (lines - 11) and perform either discretized attack or continuous attack based on the interest of attacker (i.e., discretized poisoning attack in lines 12 15 or continuous poisoning attack lines 18).
C EXPERIMENTAL SETTINGS
In this section, we provide more detailed information about the experimental settings. These include the hardware and software specifications, dataset descriptions, evaluation metrics as well as detailed parameter settings. In all experiments, evaluate proposed FATE in the task of semi-supervised node classification to answer the following questions:
Q1. How effective is FATE exacerbating bias under different perturbation rates?
Q2. How effective is FATE in maintaining node classification accuracy for deceptiveness under different perturbation rates?
Q3. Can characterize the properties of edges perturbed by FATE?
15

---

Published as a conference paper at ICLR 2024
Algorithm 1: FATE
Given :an undirected graph 9 = [A, X). the set training nodes Viain- fairness-relatee
auxiliary information matrix F, total budget B, budget in step dū, the bias function b, number pre-training epochs T;
Find :the poisoned graph S;
poisoned graph 9 マ- G, cumulative budget A <- 0, step counter <- 0;
while A B do
c + 0:
for t 1 to T do
update @ to @ with gradient- based optimizer (e.g., Adam);
end
get ( and (T)
compute meta-gras geetaggradiett Vgb + V Verb Y, OuT (T)
F) V (T),
if attack the adjacency matrix then
compute the derivative V vab+a b (V (Vxb)* diag (Vxb); end
10
11
12
if discretized poisoning attack then
13
compute the poisoning preference matrix V by Eq. equation select the edges poison in V with budget by Eq. equation
update the corresponding entries in G;
15
16
else
update ② by Eq. equation with budget 8,;
17
18
end
A A + 8z:
29
<
i + 1;
21 end
22 return ;;
C.I HARDWARE AND SOFTWARE SPECIFICATIONS
All codes are programmed in Python 3.8.13 and PyTorch 1.12.1. All experiments performed Linux server with 2 Intel Xcon Gold 6240R CPUs and 4 Nvidia Tesla V100 SXM2 GPUs, each of which has 32 GB memory.
C.2 DATASET DESCRIPTIONS
We use three widely- benchmark datasets for fair graph learning: Pokec-z, Pokec-n and Bail. For each dataset, we use fixed random seed to split the dataset into training, validation and test sets with the split ratio being 50%, 25% and 25%, respectively. The statistics of the datasets, including the number of nodes (# Nodes), the number of edges (# Edges), the number of features (# Features), the sensitive attribute (Sensitive Attr.) and the label (Label), are summarized in Table
Pokec-z and Pokec-n two datasets collected from the Slovakian social network Pokec, each of which represents a sub-network of a province. Each node in these datasets is user belonging to two major regions of the corresponding provinces, and each edge is the friendship relationship between two users. The sensitive attribute is the user region, and the label is the working field of user.
Bail is a similarity graph criminal defendants during 1990 2009. Each node is a defendant during this time period. Two nodes are connected if they share similar past criminal records and demographics. The sensitive attribute is the race of the defendant, and the label is whether the defendant is bail or not.
16

---

Published as a conference paper at ICLR 2024
Table 3: Statistics of the datasets.
Dataset
Pokec-z
Pokec-n
Bail
Nodes
7, 659
6, 185
18, 876
Edges
20, 550
15.321 265
311.870
# Features
276
17
Sensitive Attr.
Region Working field
Region Working field
Race
Label
Bail decision
C.3 EVALUATION METRICS
In experiments, we aim to evaluate how effective FATE is in (1) attacking the fairness and (2)
maintaining the utility of node classification.
To evaluate the performance of FATE in attacking the group faimess, evaluate the effectiveness using Asp, which is defined as follows.
SP
P 1 1 - P
=]]
(14)
where is the sensitive attribute value of node and is the ground-truth and predicted class labels of a node. While to evaluate the performance of FATE attacking the individual fairness, we evaluate the effectiveness using the InFoRM bias (Bias) measure (Kang et al. 2020), which is defined as follows.
Bias Σ S 11.
(15)
iEVien jEVieat
where Viest is the set of test nodes and the oracle pairwise node similarity matrix. The intuition of Eq. equation 13 is to measure the squared difference between the learning results of two test nodes, weighted by their pairwise similarity.
To evaluate the performance of FATE in maintaining the utility, we use micro Fl score (Micro F1), macro Fl score (Macro FI) and AUC score.
C.4 DETAILED PARAMETER SETTINGS
Poisoning the input graph. During poisoning attacks, set a fixed random seed to control the randomness. The random seed used for each dataset in attacking group/individual fairness are summarized in Table
Surrogate model training. We run all methods with a perturbation rate from 0.05 to 0.25 with step size of 0.05. For FA-GNN (Hussain a 2022). we follow its official implementation and use the same surrogate 2-layer GCN (Kipf & Welling (017) with 16 hidden dimensions for poisoning attack [ The surrogate GCN in FA-GNN is trained for 500 epochs with learning rate le 2, weight decay 5e - 4, and dropout rate 0.5. For FATE, we use a 2-layer linear GCN (Wu) et al. 2019) with hidden dimensions for poisoning attacks, And the surrogate linear GCN in FATE trained for 500 epochs with a learning rate le 2, weight decay 5e 4, and dropout rate 0.5.
Graph topology manipulation. For Random and DICE, we use the implementations provided in the deeprobust package with the default parameters to add the adversarial edges For FA-GNN GNNN add adversarial edges that connect two nodes with different class labels and different sensitive attributes, which provides the most promising performance as shown in (Hussain et al. (022). For FATE, suppose we poison the input graph in p (p > 1) attacking steps. Then the per-iteration attacking budget in Algorithm I set as &1 = 1 and 6; = r|El-1
p-1 Vi {2.... .p). where r is the
perturbation rate and |g is the number of edges. Detailed choices of for each dataset in attacking group/individual faimess are summarized in Table
Training the victim model. We fixed list of random seed (0,, 1, 42, 100) to train each victim model 5 times and report the mean and standard deviation. Regarding the victim models in
raieess
https://deerrobust. hww.://sws...eeetteccccooooooo
17

---

Published as a conference paper at ICLR 2024
Table 4: Parameter settings on the random seed for all baseline methods in poisoning attacks (Random Seed) and the number of steps for poisoning attacks in FATE (Attacking Steps).
Dataset
Fairness Definition
Attacking Steps
Random Seed
Statistical parity
3
25
Pokec-n
Individual fairness
3
45
Statistical parity
3
25
Pokec-z
Individual fairness
5
15
Statistical parity
3
25
Bail
Individual fairness
3
group fairness attacks, we train 2-layer GCN (Kipf & Welling 2017) for 400 epochs and 2-layer FairGNN (Di & Wang [021] for 2000 epochs to evaluate the efficacy of fairesss attacks. The hidden dimension, learning rate, weight decay and dropout rate of GCN and FairGNN are set to 128, 1e le 5 and 0.5, respectively. The regularization parameters in FairGNN, namely a and B, are set to 100 and for all datasets, respectively. Regarding the victim models in individual fairness attacks. we train a 2-layer GCN (Kipf & Welling (017)) and 2-layer InFoRM-GNT (Kang et al., 2020 Dong ctt al. (021) for 400 epochs. The hidden dimension, learning rate, weight decay and dropout rate of GCN and InFoRM-GNN are set to 128, le 3, le 5 and 0.5, respectively. The regularization parameter in InFoRM-GNY is set to 0.1 for all datasets.
D ADDITIONAL EXPERIMENTAL RESULTS: ATTACKING STATISTICAL PARITY ON GRAPH NEURAL. NETWORKS
A - FATE with FairGNN the victim model. Here, we study how robust FairGNN is in fairness attacks against statistical parity with linear GCN as the surrogate model. Note that FairGNN is a faimess-aware graph neural network that leverages adversarial learning to ensure statistical parity.
Main results. Similar to Section 6.1 for FATE, we conduct fairness attacks via both edge flipping (FATE-flip) and edge addition (FATE-add). For all other baseline methods, edges only added. From Table 5 we have the following key observations: (1) Even though the surrogate model is linear GCN without fairness consideration, FairGNN, which ensures statistical parity on graph neural networks, cannot mitigate the bias caused by fairness attacks and is vulnerable to fairness attack. (2) FATE-flip and FATE-add are effective and the most deceptive method in fairness attacks. (3) DICE-S, FATE-flip, and FATE-add are all capable of successful fairness attacks. But FATE-flip and FATE-add have better utility than DICE-S, making the fairness attacks more deceptive. Both Random and FA-GNN fail in some cases (indicated by the underlined Asp in both tables). In short, even when the victim model is FairGNN (a fair graph neural network), our proposed FATE framework are effective in fairness attacks while being the most deceptive (i.e., highest micro Fl score).
Effect of the perturbation rate. From Table 5 we can find out that: (1) Asp tends to increase when the perturbation rate increases, indicating the effectiveness of FATE-flip and FATE-add for attacking fairness. (2) There no clear correlation between the perturbation rate and the micro Fl scores of FATE-flip and FATE-add, meaning that they deceptive in maintaining the utility. As consequence, FATE is effective and deceptive in attacking fairness of FairGNN across different perturbation rates.
B Performance evaluation under different utility metrics. Here we provide additional evaluation results of utility using macro Fl score and AUC score. From Tables and scores and AUC scores are less impacted by different perturbation rates. Thus, it provide additional evidence that FATE can achieve deceptive fairness attacks by achieving comparable or even better utility the semi-supervised node classification.
77, we can see that macro Fl
18

---

Published as a conference paper at ICLR 2024
Table 5: Attacking statistical parity FairGNN under different perturbation rates (Ptb.). FATE poi- sons 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 (1) for micro F1 score (Micro F1) and Asp (bias). Bold font indicates the most deceptive fairness attack, i.e., increasing Asp and highest micro FI. Underlined cell indicates the failure of fairness attack, i.e., decreasing Asp after fairness attack.
Dafaset
Pth.
Miero
PT
Kanddvaa
Aap (1)
Miero (1)
DICESS
Sar (1)
Miem
FL
PA-GAN
Sar C1
Miero FI (1
FATE-Hlip
Sap (1)
Mierr F1
FATE-add
Aup C
0.4
6.1
2,0
68.2 L
6.7
2,0
68.2
0.4
2.0
6.7
08.2 1.0.
6.7
0.05
67.4 0.5
8.2
66.0 0:
7.4
66.7
1.2
1.5
68.4 0.2
8.0
68.
0.2
8.9 1.8
Pokee-n
10.4+
8.3
67.6
06.6
11.5
68.5
9.5
08.5 0.8
0.4
9.5
10.5-26
9.0
65.2= 0.2
10.7
0.3
7.1
08.7-03
7
0.3
68.
07.3
67.1
L.
0.
Pokoe-x
0.15
08.88 0.8
8.0
8.0
67.8
0.6
66.0
64.0
0.5
68.7
9.112
68.7 0.5
0.5
9.5 2.3
0.20
08.88
8.6
07.4
0.1
61.0
0.8
3. 3.1
68.8 02
10.41:1
68.
0.2
104-1.6
01225
06.4
0.4
7.0
GT.1 = 0.5
8.7
64
1.1
14.0 2.0
68.5
10.3
68.5 0.3
10.3-21
0.00
20.3
0.1
8-4-01 022
913-00 0.1
8.1- 0.2
10.3
8.1=0.2 0.2
50.3- 0.1
5.1+0.2
03.9+101
6:4-02
0.05
50.6
1.2
8.5 0.2
96.5 1.0
8.0 0.5
89.1
2.0
10.8 1181111
93.610.1
9.2
93.6 0.1
9.100.2
Ball
I1.15
0.10
90.1
90.00
2 2.0
2.0
811
8.5 0.6
90.6 1.7
96.1 1.0
8.6
9.5
0.2
S7.3
S7.8
2.0
22
12.2
20.9
93.310.11
934101
9.3
9.2
93.3 0.1
93.4 1::4::00 0.1
9.2
933 0.2
11:00
80.2
2.4
8.4
90.0 177
9.0
05
56,0
2.7
2.4
93.1
9.3
$3.0 0.11
0.2
0.25
88.8
2.5
8.2
88.9 18
9.0 0.5
87.0
1.9
8.0
93.0+00.
9.2
98.0 0.2
0.3
Table 6: Macro F1 score and AUC score of attacking statistical parity on GCN under different perturbation rates (Ptb.). FATE poisons the graph via both edge flipping (FATE--fip) and edge addition (FATE-add) while all other baselines poison the graph via edge addition. Higher is better (f) for macro Fl score (Macro FI) and AUC score (AUC). Bold font indicates the highest macro Fl score or AUC score.
Dutaset
Pth
Mocro PT
AUC
Macro PT
DICE'
ALC
FA-GNK
AUCT)
Macro
AUC
08:3
0.05
1.0
70.4
65.4 0.3
61.9
70.4 0.2
66.00
70.3 1:
06.0 01001:00
10.3 0.6
Pokecn
0.10
0.15
64.6
0.4
0.0.
00:0..00
0:.0-:0.1 6.1
619--003
65.7.:022
00.0 0.5
01:3+00.
0:33
20.0-300 0:1
69.1 0:5
66.11
66.1
70.4 0.6
70.6
06.1 0:011:06
66.1 0:11:02
70.4 0..8
70.6--00
0.20
61.5 +.5
09.1+6.1
6122+003
08.7 0.0.
03.5 03.5+002
66:0+002
68.4 -
70.7-0.4
664+00
70.7 70.7-00.4
0.25
61.5+00.
6.1
032-=02
08.5 0.22
05:0=002
69.5+00.3
66.3 0.5
70.6=0.6
6..5
70.0=000
0.00
(e..2 111
0.
08.2200
76.1 1.0.
76.1 133
151
08.2200
11.1
0.05
68.6 0.4.
0.4
68.7 0:3.3
75.4 05.4
0..9 0.8
63.6.200.4
752220.4
0..4
T6.2
Paluest
0.10
0.15
08.6 0.0.
07.8 1:1.3
0.3
0.8
67.62.0.
0..62:02
74.5 0.333
T4.1 1.1.4
67.5 67.5 0.5
G6.1 0.6
72.7 2:22
78.8 2:33
08.0 2: 0.7
08.0 0.0
75.3 0.2
0.3
68
65
0.3
7..3
0.20
08.2 1:1.4
C.6
00.82:05
TILS 0.3
G6
71.9 11.11:0.11
08.4 0.5
76.1
05
75.1
0.25
1:444
0.
07.12:01
0.33
63-3
71.2 4:23
08.4 1.1
74.4 1.4
1
74.4
12.3 11.2
27.4 3:
12.3 1..2
01
22
0.05
92.0-::00 0.2
0.2
91.12:03
10.1 0.4
908 0.1
94.4 2:00
01.8 6.1.1
UT.1 0.1
91.7 0
1
Dail
6.10
0.15
01.5++:0.2 0.2
01.1 0.2
9.2 0.2
81.7 0.3
91.2
91.1-00
B1.7 0.1
B1.5 0.2
80.5 0.1
8 03
95.5 9
02.5
0.3
91 022
91.6 0.2
96.9 0.1
96.9 0.1
916
91
96.9 0.1
96.9-01 0.1
0.20
00.7 0.2
9.1
90.9 00.9-02
$1.1 +.1
88 0..1=0.1
02.2 + 0.1
0..
96.8 0.1
914+02
96.8=0.1
0.25
40.6:-0.22
0.3
90.6:003
01.5
88.5 0.2
62.0
91.2
96.8
0.1
915
96.8=0.1
Table 7: Macro F1 score and AUC score of attacking statistical parity on FairGNN 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 (f) for macro Fl score (Macro FI) and AUC score (AUC). Bold font indicates the highest macro Fl score or AUC score.
Dataset
Pdb
Macro
FTCT
Random
AUC
PLT!!
DICES
AULTS
Macro MacroFFTT7
EA-GNN
AUCTT
Macro
PTTT
FATE-
AUCT
Macro PTTT)
PATE-Wdd
SUCTO
1.00
0.3
78.4 1:11
10.1 1.
(All 0.3
11..1:2...
155
01. 11.55
0.35
64.3
68.5 2
64.5 =
18.5
0.8
0.7
6
05
70.7 0..4
6..82005
70.7
Poloe-n
0.10
0.15
63.5
61.8
67.5
67.3 2.2.2.111
66.1 0.7
04.3..1..1
02.6 0.4
08.5 0.4
G1D 0.4
63.1 +.0
67.2
68.3
05.+10
0..02277
70.8 0..
70.8+00.5
65
0..02.77
70.++005
0..
0.23
63.1 1
67.5
1.5
07.5 1.1
0.0
66.7
05.7=07
70.4
65
70.4
11:25
02.4
66.5 0.8
1.6
07.22
0.9
02.4 1.4
67.-2
06
70.1
11
70.1
0.00
08.1
75.1 0:5
0.44
0.3
0.11
08
1
08
1
0.05
06.3 0.9
73.5++0.0 0.0
07.2+00.7
73.9 1.5
05.5 1.1
72.6 1.4
084+004
74.7 74.
084+04
747
747++09
Pokeea
0.15
0.10
06.0--0.
06.0 0.8
72.0++1.1
71.
0..9
67.1 0.5
73.4+000
73-1+002
63.1+ 1.6
+..
700 1.8
71.3+11 1.7
08
082+08
76.2+06
75.3+08
68
88
762+00
763++08
0.200
05.6
1..
1.0
71.0000
G8.7 0.11
68.0 1.6
03
06.6
08
76.
0.25
05.0::077
21.241
06
13
69.4
08
15.3-203
680205
7033103
0.00
00.3++0. 0.2
07.1
953-002
074+01
+0.2
97.4+ 0.1
0.
071+00.1
0.
0T4
0.05
88.5
923
2.
1.8
010101
8301011
073101
Tail
0.15
0.10
88.6
92.7
9.5
88. 1.3
1
923
02.8
1.6.22 27
90.
02.101
026101
07.001
07.1101
027101
026100
970101
071101
0.20
$7.8 0
9. 2.5
859
02.
3:30
890
025
07.0..0.
02.31...1
970.001
0.25
$7.5
9.6
887 2.1
00.5 23
23
896
92.3 0.
97.0
92.51002
970
19

---

Published as a conference paper at ICLR 2024
E ADDITIONAL EXPERIMENTAL RESULTS: ATTACKING INDIVIDUAL FAIRNESS ON GRAPH NEURAL NETWORKS
A - FATE with InFoRM-GNN as the victim model. InFoRM-GNN is an individually fair graph neural network that ensures individual faimess through regularizing the individual bias measure defined in S Here, we study how robust RMFORM-GNN is in faimess attacks against individual fairness with linear GCN as the surrogate model.
Main results. We attack individual fairness using FATE via both edge flipping (FATE-flip) and edge addition (FATE-add), whereas edges are only added for all other baseline methods. From Table X we can see that: (1) for Pokec-n and Pokec-z, FATE-flip and FATE-add are effective: they are the only methods that could consistently attack individual fairness across different perturbation rates; FATE-flip and FATE-add are deceptive by achieving comparable or higher micro FI scores compared with the micro Fl score on the benign graph (when perturbation rate is 0.00). (2) For Bail, almost all methods fail the faimess attacks, except for FA-GNN with perturbation rates 0.20 and 0.25. A possible reason is that the adjacency matrix A of Bail is essentially a similarity graph, which causes pairwise node similarity matrix S being close the adjacency matrix A. Even though FATE and other baseline methods add adversarial edges to attack individual fairesss, regularizing the individual bias defined by S (a) not only helps ensure individual fairness (b) but also provide useful supervision signal in learning a representative node representation due to the closeness between S and A. (3) Compared with the results in Table 2 where GCN the victim model, InFoRM- GNN is more robust against fairness attacks against individual faimess due to smaller individual bias in Table
Effect of the perturbation rate. From Table g we can see that FATE can always achieve comparable or even better micro Fl scores across different perturbation rates. In the meanwhile, the correlation between the perturbation rate and the individual bias is relatively weak. One possible reason that the individual bias is computed using the pairwise node similarity matrix, which is not impacted by poisoning the adjacency matrix. Though poisoning the adjacency matrix could affect the learning results, the goal of achieving deceptive fairness attacks (i.e., the lower-level optimization problem in FATE) may not cause the learning results obtained by training on the benign graph to deviate much from the learning results obtained by training on the poisoned graph. Consequently, higher perturbation rate may have less impact on the computation of individual bias.
Table 8: Attacking individual faimess on InFoRM-GNN under different perturbation rates (Ptb.). FATE poisons the graph via both edge flipping (FATE-flip) and edge addition (FATB-add) while all other baselines poison the graph via edge addition. Higher is better (?) for micro Fl score (Micro FI) and InFoRM bias (Bias). Bold font indicates the most deceptive fairness attack. i.e., increasing bias and highest micro F1. Underlined cell indicates the failure of fairness attack, i.e., decreasing bias after fairness attack.
Dataset
Miero (I) (*)
Random
Bias (?)
Miero (1)
DICES
Bias (1)
MicroFlltt
Bias (()
Miero (!)
FATE-dii
Blas (1)
Micro (1)
ExtE-pdl
Bin (f)
0.00
05:0 - 0.4
0.5 0.1
68.0
0.4
0.01
04
U.5+U.1
0.4
0.6
055+0.1
0.05
67.5
L
0.5
0.5 0.0
66.0 0.4
0.5 1.1.1
0..1000
68.40..
0.610.11
6..
0.510.1
Pokee-n
0.15
0.10
67.8
66.7
5 0.5
0122
0.5:0.1
0.5 U.1
67.4 0.4
67.1
0.4
0.5 0.1+0011
0.4+00.1
07
66.1.00
0..0000
0.4+0.
085+006
68.3
06:10..1
0.5
0..4
0.1
06.+0.11
0.20
0.3
0.4-0.1
07.2 0-
0.5 0.110
065102
0.4100
0..9-0.8
0.5
0..1
0.110.
0.0
06.7-00
0.1
05.1+02
0.4+00
08.7+0.3
0.000.0
06.
06+0.
11.01
08.4=
0.0
0..
65.=0.5
05
08.
0.
0.05
08.0
0.2
0.6 0.1
68.0-08 0.5
0.5
68.1 0.7
0.5+-0.1
68.7 0.7
0.7
0.
0.6:0000
Pokeo-z
0.15
0.10
67.9
67.6 = 0.3
0.2
0.6 8.1
0.6
- D.1
09.01011 0.1
68.2
0.6
0.6 0.1
0.6 0.1
85.0.00.
26.8 0.
0.5000
0.5
60.1
68.9
+.0.5
0.6
0.6 0.0
0.6 1 0.0
000007
63.5 0.6
0.6 0..000
06+00.1
0.20
67.7 : 0.5
0.6 0.1
66.5
0.2
0.5 0.0
66.1
1 0.6
0.4.1...
60.1
0.2
0.6 0.0
60
0.6 0.00
0.25
08.88 2 11.6
0.55 1111
08.5 022
0.5 0.0
05.3 0
0.4000
68.9=17 ILT
0.0
69.41
0.6::000
0.00
02.8 - 0.1
1.7 D.T
12.8
0.1
L.7 0.1
1.7 0.
92.8 0.1
1.7 0.1
1.+00
0.05
91.0
0.0
92.1
L7 1.00
9131011
15101
02.8 0.3
L7 1.1
92.1101
161
Bail
01.7
91.5
11:01
1.6 0.T
00.202
1.6
0.
16+00
01.5
0.0
$9.1
1.0 0.0
52.7
0.25
01.1
0.0
1.6 0.0
88.9
0.1
02.0
1.0
92.7
- Performance evaluation under different utility metries. Similar to Appendix DJ we provide additional results evaluating the utility of FATE in attacking individual fairness with macro Fl score and AUC score. From Tables g and 10 we can draw a conclusion that FATE can achieve comparable even better macro Fl scores and AUC scores for both GCN and InFoRM-GNN across different perturbation rates. It furterr proves the ability of FATE on deceptive faimess attacks in the task of semi-supervised node classification.
20

---

Published as a conference paper at ICLR 2024
Table 9: Macro Fl score and AUC score of attacking individual fairness 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 (f) for macro F1 score (Macro F1) and AUC score (AUC). Bold font indicates the highest macro F1 score AUC score.
Dotnset
Pib.
Macen PT
Random
ATICUT
Maccoo
PT
DICR-S
Maceoo FT
FA-GNN
AUCCTF
Maran FTC
FATE-dip
ATC
Marro FTT
FxTE-ndd
AUCUT
1.0
06.1111 0.3
05.3 1.33
0..1100.
05.3111.33
0233 = 00.5
10.3 0.4
1S.d 0.4
00.311133
65.2
0.3
00.11:02
65.7 0.3
7..22.9..2
6..61.0.66
71.1 1 0.2
65.7 1 0.4
70.1:::00
68.5-100.1
70.2:1.0.
Pokue-n
0.5
0.00
65.2
65.4
0.2
0.5
09.6.:05
6.3
64.7 2 0.5
61.9-2-01 0.2
09.9:2.9.2
10.1-200.3
6:6-100.
05.4 3:06
70.2 2 0.3
60.1-:00 0.1
85.8 0 0-4
65.5 2 0.3
70.0 0 0.5
00.2::00.7
65.8 5 0.5
63.4-200.1
70.7 1:07::00.
00.5.:0.7
0:30
64.9 0.2
0..0+03
65.1 0.4
70.2++0.3
65.7 0.5
600 0.1
65.2 0.3
00.1 08.7+00.0
65.8 0.6
70.2+007.
0:25
64.7
0.1
08.1+002
64.1 0..1==0.11
00.1++0.2
65.5++0.5
65.1-00 0.3
65-1=00 06
00.7+0077
65.8 0.8
6
020
08.2..0...
15.11.0
08:21:0:44
75.12:0.
08:21.0.
7 0.
68.1 04
15.1 0.04
08:21:03
75.1
0.00
688 7 0.4
13.0..00
68.7 0.6
75.2
0..4
75.1 2 0.5
05.3 8 0.5
75.4 0044::00
08.5-2-03
75.2.10.44
Pokeca
0.10
0.15
68.5
67.5
0.1
0.4
74.1+.03
15.1
68 00990-02 0.2
67.90 0.5
15.3-89.11
73.8 0.1
0..9
00.5+00.4
720
74.1 0.5
05.1 0.5
05.8 8 0.5
75.5++0..4
15.5-+00.3
68.8 0.7
08.8 0:3
756+03
756002
0:30
67.5
0-4
+4.7++0.
67.7 0.5
74.7+-0.2
66.1 +.0.1
718
05.7 0.5
T5.5++0.3
69.0 0.4
756+03
0:25
67.2 0.5
7..1+003
65.0--00 0.5
7..7=-022
64.6+004
70.5 0.4
65.0 033
76.6.-0..2
69.1 = 0.8
+
0:0
12.3 0.2
9.1161
92.30.2
9.
0233.02
07.1 011
023 02
11.1
0.6
91.2 0.5
0:
0.2
10.0-29.3
90.3::0.2
81. 02
92.3 92332.4 0.4
97.3 17.3000 0.1
90.1 0.03
Bail
0.15
0.00
00.5
00.6 8.1
0.1
942++03
+1.1+02
91. 0.2
0.5
+..++0.
AL.0+0.
88.+002
89.1 +.0.1
92-1-03
03
92.4 00.
92.3 +0
97.3
97.3 0.0
- 0.4
00.3+002
10.2
97
973+011
0:30
00.2
00:2+000 0.0
0..+001
90.0=002
9122+00.
87-++02
91. 018-02
92.4=01
0.0
52:4002
97
8:26
50.9 9:
0.
90.
91. 0.4
876
91
92.2
07.
0.2
97
Table 10: Macro score and AUC score of attacking individual faimess on InFoRM-GNN 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 (t) for macro Fl score (Macro Fl) and AUC score (AUC). Bold font indicates the highest macro F1 score or AUC score.
Dotaset
Pth.
Matro (1())
Kundom
AUC (1)
Macro
FI (1)
DICES
(UC
Macro FT
EL-NNN
AUC
Macro TT(")
FATE-llip
AUCTT
Marro
ETCH
FATE-udA
AUC())
0.00
65.4
0.04
703 0.
55.4 0.1
103:2.0
0.2
70.3
0.8
65-1 2
70.52
65 2
7..SEEU.
0.05
65.1 0:03
600-000 0.2
65.7 0.1
2033=001
65.0
70.8 0.0.1
65.9 = 0.4
65 0.5
70.5+:0.9
Pokre-n
0.15
0.10
6188=00 0.1
01.9-002 0.
80.0 05
0006 0.4
66.1+ 0.5
65.2+00 0.1
200
2.2
61.1+6.1
61.8 0.4
09. 03
69.3 03
65.7 0.6
05.8 0
70
70.3+10
8.4
06.0 00.0+0044
70.5=09
70.9 1.1
0.20
65.1 0.
60.5 03
61.
00.9 0.2
63.12
02
65.5=08
7.
85.6 6
70.5=07
0.25
61.6
0.3
60.6 02
6..
09.1=002
6..62003
686 02
66.0=0..
7.
65.
70.1
0.00
05.3
0.1
752 02
0.1
15-2-019
0.C
752 02
883 0.3
752-002
05
75.2+.0.
0.05
05:0 0.2
75.1 -03
68. 0.4
75.5 + 0.2
07.8 0.0
750 03
65.0 0.7
75.1+00
057 257+041
76.1 0.3
Polecss
0.10
0.15
07.6 0.2
07.2 0.3
71.3 0.1
76.1
689 0.2
67.0
75.3 0.3
711=003
66.7 0.3
07.7 0.0
75. 06
72.3 0.1
68.9 0.4
65.0 0.0
75.6+
754
68.9 0.6
056
754=004
+6.5+00.3
0.20
07.3
7L4=04
08.5 0.1
75.1 1.1=0000
0.55
71.7
6900 2 0.2
06
69.2 0.4
75.4
0.25
66.3
0.4
755-04
68.2 0.5
7L8
0.5
70,
02
68.8 0.7
0..6
0..4
7..8=0.1
0000
01.9 0.1
07.5-00 000
21.0 0.1
07:0-000
0.
073 00
913+61
00.2+00
919+01
91.2+0.0
0.5
01.0 0.1
91.3
01.2+0..1
05.0-0011
00.1+0.11
912--01 0.1
92.0 0.0
97
91
97.0+00.2
Bail
0.10
011
50.5 0.1
90.7 0.2
055
955 03
01.0
0..1
9LT=003
9L1=00
50.1
56.8 0.2
924=
95.3
92.0-10 0.1
92.0=
07
9700
91
919
9700=0.1
970=000
0.20
00.5 0.
05.7
30.8 0.1
0L1202
6.1
91 01
92.0=0.1
06.0
01
26.
0.25
10.1:01
95.4
30.6 0.1
9L0.0011
914=01
918401
961
01.9.0.1
0.0
21

---

Published as a conference paper at ICLR 2024
F TRANFERABILITY OF FAIRNESS ATTACKS BY FATE
For the evaluation results shown in Sections 6.1 and 6.2 as well as Appendices D and both the surrogate model (linear GCN) and the victim models (i.e., GCN, FairGNN, InFoRM-GNN) convolutional aggregation-based graph neural networks. In this section, we aim to test the transferability FATE by generating poisoned graphs on the convolutional aggregation-ban surrogate model (i.e., linear GCN) and testing graph attention network (GAT), which is non- convolutional aggregation based graph neural network (Veličković et al. 2018).
More specifically, train graph attention network (GAT) with 8 attention heads for 400 epochs. The hidden dimension, learning rate, weight decay and dropout rate of GAT are set to 64, le le 5 and 0.5, respectively.
The results on attacking statistical parity or individual fairness with GAT as the victim model shown in Table I Even though the surrogate model used by the attacker is convolutional aggregation-basee linear GCN, from the table, it is clear that FATE can consistently succeed in (1) effective fairness attack by increasing Asp and the individual bias (Bias) and (2) deceptive attack by offering comparable or even better micro Fl score (Micro FI) when the victim model is not convolutional aggregation-basse model. Thus, shows that the adversarial edges flipped/added by FATE is able to transfer to graph neural networks with different type of aggregation function.
Table 11: Transferability of attacking statical parity and individual fairness with FATE on GAT under different perturbation rates (Ptb.). FATE poisons the graph via both edge flipping (FATE-flip) and edge addition (FATE-add). Higher is better (1) for micro score (Micro F1), Asp (bias for statistical parity), and InFoRM bias (Bias, bias for individual fairness).
Attacking Statistical Parity
Pokec-n
Pokec-z
Bail
Dataset
Ptb.
Micro
(1)
Asp (1)
Micro Fl (f)
Asp (?)
Micro F1 (1)
Asp (1)
0.00
63.8 = 5.3
4.0 3.2
68.2 = 0.5
8.1
89.7
0.6
0.05
63.9 = 5.5
6.4:5.1
68.3 = 0.4
10.5
90.1 3.8
8.1
0.10
63.6 = 5.3
7.9 6.7
67.8 0.4
11.2
90.3 3.2
8.5
FATE--lip
0.15
63.7 5,3
6.1
68.2
1.52
2.7
8.8
0.20
64.1 = 5.6
6.7
67.8+0.6
1..1
90.0 -00--.77 2.7
8.7
0.25
63.6 = 5.2
8.5
6.4
11.5+
89.9 3.0
0.5
0.00
63.8 = 5.3
4.0
68.2
8.6
89.7 - 4.2
0.6
0.05
63.9 = 5.5
6.4
6.4
1.3
90.2 3.7
8.1
0.10
63.6 = 5.3
6.7
67.8
1..2
90.3 3.2
0.6
FATE-add
0.15
63.7 5.3
6.1
68.2 0.6
1..2
90.3 2.6
8.8 0.3
0.20
64.1 = 5.6
7.7 6.3
67.8 0.6
1..1
90.1 2.6
8.8 0.5
0.25
63.6 5.2
8.5 7.0
68.0 0.4
11.512
89.9 2.9
8.8 0.5
Attacking Individual Pairness
Pokec-n
Pokec-z
Bail
Dataset
Ptb.
Micro FT
Bias (f)
Micro Fl (f)
Blas (f)
Micro (T)
Blas
0.00
0.4 0.2
68.2 1 0.5
0.500.1 0.1
4.2
2.5 1.2
0.05
63.6 = 5.3
0.5 0.2
68.2 1 0.8
0.6
90.0 4.2
2.7 1.1
2.7
0.10
63.7 = 5.3
0.5
67.8 0.5
0.6
90.0= 4.0
2.8 2.8t1 1.3
FATE-flip
0.15
63.7 5,4
0.2
68.2
0.2
90.
2.8 1.4
0.20
63.5 5.1
0.2
68.5
0.6
90.2=3.1
+.8
0.25
63.5 =
0.2
68.0 0.6
0.1
90.2
2.7 1.2
0.00
63.8 = 5.3
0.2
68.2 0.5
0.5
89.7 4.2
2.+
0.05
63.9 = 5,4
0.5
68.2 0.7
0,6
90.0 4.6
2.7 + 1.4
0.10
63.8 = 5.4
0.5
68.2
0.6 0.6 0.2
90.1 440
2.8 + 1.2
FATE-add
0.15
63.8 = 5.4
0.5
68.3 0.2
0.6
90.1
2.8 2.8
0.20
63.7 -
0.5
0.3
0.6
90.3 3.2
2.8 1.3
0.25
63.7 = 5.3
0.2
68.4 0.3
0.6
90.2=3.1
2.8
22

---

Published as a conference paper at ICLR 2024
G FURTHER DISCUSSIONS ABOUT FATE
A - Relationship between fairness attacks and the impossibility theorem of fairness. The impossibility theorems show that some fairness definitions may not be satisfied at the same time However, this may not always be regarded as fairesss attacks. To our best knowledge, the impossibility theorems prove that two fairness definitions (e.g.. statistical parity and predictive parity) cannot be fully satisfied at the same time, i.e., biases for two faimess definitions are both zero). However, there no formal theoretical guarantees that ensuring one fairness definition will always amplify the bias of another fairness definition. Such formal guarantees might be nontrivial and beyond the scope of our paper. As we pointed out in the abstract, the main goal of this paper is to provide insights into the adversarial robustness of fair graph learning and can shed light for designing robust and fair graph learning in future studies.
B- Relationship between FATE and Metattack. FATE bears subtle differences with Metat- tack (Zügner& & Günnemann 2019), which utilizes meta learning for adversarial attacks on utility. Note that Metattack aims degrade the utility of graph neural network by maximizing the task- specific utility loss (e.g., cross entropy for node classification) in the upper-level optimization problem. Different from Metattack, FATE aims attack the fairness instead of utility by setting the upper-level optimization problem as maximizing bias function rather than a task-specific utility loss.
C- A Alternative edge selection strategy via sampling. Here we introduce an alternative perturbation set selection strategy that is different from the greedy selection described in Section 3.2 The key idea is to view each edge in the graph as a Bernoulii random variable (Lin et al.) 2022 Liu et al.. 2023a). And the general workflow is as follows. First, we follow Eq. to get a poisoning preference matrix V A- Then, we normalize VA to a probability matrix A.. Finally, for the i-th attacking step, we can sample 6; entries without replacement using PA PA& as the set of edges to be manipulated (i.e., added//elcted//tipped).
D The potential of FATE on attacking specific demographic group in group fairness. To attack a specific group, there can be two possible strategies: (1) decreasing the acceptance rate of the corresponding group and (2) increasing the gap between the group to be attacked and another demographic group. For (1), following our strategy of modeling acceptance rate as the CDF of Gaussian KDE,
set the bias function to be maximize the negative of acceptance rate, i.c.,
b (Y, Or F) = - P [ū = 8 = a]. where a is the sensitive attrihute value denoting the demographic group be attacked. For (2), suppose
want to attack the group with sensitive attribute value. We can also attack this demographic group by setting the bias function to be b O = P lī = 1 s = P [ū- = s = 0). In this way, we can increase the acceptance rate of demographic group (s 1) while minimizing the acceptance rate of the group (s 0).
The potential of FATE on attacking the best/worst accuracy group. To attack the best/worst accuracy group, the general idea is to set the bias function to be the loss of the best/worst group. It is worth noting that such attack conceptually similar to adversarial attacks on the utility as shown in Metattack (Zügner& & Günnemann] 2019), but only focusing on subgroup of nodes determined by the sensitive attribute rather than the validation set.
F F- Justification of applying kernel density estimation non-lII graph data. To date, it remains an open problem whether the learned node representations follow IID assumption on the low-dimensional manifold or not. Empirically from the experimental results, using KDE-based bias approximation effectively helps maximize the bias for fairness attacks. Meanwhile, relaxing the IID assumption is common strategy in computing the distributional discrepancy of node representations. For example, MMD is a widely used distributional discrepancy measures, whose accurate approximation also requires IID assumption
Antérief-Abdellatt & Alquier 2020), and recent studies (Zhu et al. [202]] 2023) show that we can also adapt it on non-lID data which shows promising empirical performance.
G - Possible defense strategies against deceptive fairness attacks. FATE demonstrate that it is possible to achieve deceptive fairness attacks on graph learning models by deliberately perturbing the input graph. Given its potential negative socictal impacts, we discuss few possible defense strategies against such deceptive faimess attacks. 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..
rneess
23

---

Published as a conference paper at ICLR 2024
Wang al. (2022) or sampling over the neighborhood (e.g.. (.i.ellppinllii et al. (2021) Chen al. (2022)
; Lin et al. (2023) to control which node representations to aggregate during message passing. The reason for such possible design is that Figure reveals revealss 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 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/probabiissic message passing strategy. Instead, for individual faimesss, 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
H How does FATE maintain the performance for deceptiveness? We assume there is a diver- gence in optimizing the task-specific loss function 1 (G. Y, O 0) and optimizing the bias function b (Y, ,.,'.) F). Thus, maximizing b (Y,O*, F) may not affect (g. Y. O 0) 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, common strategy is to solve a regularized optimization problem, where the objective function to be minimized is often defined as / (G, Y, O, + ob (Y, O², F) with o being the regularization hyperparameter. If there is no divergence between the optimization of I (G. Y, 0) and b (Y, O", F), it would be sufficient would be impossible to
to optimize one of them obtain fair and high-utility learning results, achieve a good trade-off between faimess and utility if they are completely conflicting with each other. All in all, we believe that optimizing the task-specific loss function / (G, Y, O, 0) in the lower-level optimization problem could help maintain deceptiveness both intuitively and empirically as shown in Section 6.1 Section 6.2 Appendix D and Appendix E
H MORE DETAILS ON FAIRNESS DEFINITIONS
We discuss more details about statistical parity and individual fairness here.
A Statistical parity. Mathematically, statistical parity is equivalent to the statistical independence between the learning results (e.g., predicted labels of a classification algorithm) and the sensitive attribute. Consider a classification problem with ÿ being the predicted label, being the sensitive attribute whose attribute value is in the set S. Statistical parity is defined as follows.
[ = P [ū- 1|s = =], Va S
(16)
B Individual fairness. Other than group fairness, individual fairness studies fairness in finer- grained individual level. asks for similar individuals to be treated similarly Dwork et al. (2012).
Such principle is often formulated Lipschitz inequality
di Y [i,:], Y [)+ S (i.j)
(17)
where Y is the learning results, e is the Lipschitz constant, the left hand side d, (Y [i.:]. : Y [j.:]) measures the distance between the learning results Y [ and Y [j,:] of data points and j. respec- tively, and da (i.j) measures the distance between the two data points. Given a graph G = (A, X) with adjacency matrix A and node feature matrix X. Kang et al. Kang et al. (2020) further define dj as the squared Frobenius distance and assume the existence of an oracle pairwise node similarity matrix S. Then, the overall individual bias of G is further defined as Tr L Y) where Lg the graph Laplacian of similarity matrix S.
24


Reviews:
[{"review_id": "372wf7csb8", "reviewer": "Reviewer_CLho", "summary": "The paper first defines deceptive fairness attacks on graphs, which is a new type of threat model that is compatible with many of the existing settings. Then the paper proposes FATE, a framework that models this problem via a bi-level optimization treatment, and offers a solution using meta-learning. Finally, the paper empirically confirmed the effectiveness of their framework on real-world datasets in the task of semi-supervised node classification.", "questions": "What's the intuition behind the method being \"meta-learning\"? It appears that this is not a typical treatment of meta-learning in graph representation learning.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Very clear motivation and problem formulation\n2. Extensive experimental results and clear explanations.\n3. Theoretical analysis is necessary and appears to be correct.", "weaknesses": "The terminology of \"deceptiveness\" may be confusing and is not clearly explained, from an intuitive level, in the manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WY0HrHWbvt", "reviewer": "Reviewer_RLh1", "summary": "In the paper Deceptive Fairness Attacks on Graphs via Meta Learning, the authors delve into the realm of deceptive fairness attacks on graph learning models, aiming to amplify bias while simultaneously maintaining or improving utility in downstream tasks. They formalize this challenge as a bi-level optimization problem, where the upper level seeks to maximize the bias function according to a user-defined fairness definition, and the lower level aims to minimize a task-specific loss function.\n\nTo address this challenge, the authors introduce FATE, a meta-learning based framework designed to poison the input graph using the meta-gradient of the bias function with respect to the input graph. FATE is rigorously evaluated and compared with three baseline methods: Random, DICE-S, and FA-GNN, across three real-world datasets in the context of binary semi-supervised node classification with binary sensitive attributes.\n\nFATE distinguishes itself through two strategies: edge flipping (FATE-flip) and edge addition (FATE-add), as opposed to other baseline methods which only perform edge addition, and consistently outperform the baseline methods in fairness attacks. Unlike some baseline methods that sometimes fail to attack individual fairness, FATE maintains its effectiveness, amplifying bias while achieving the highest micro F1 scores in node classification. This dual success highlights FATE's deceptiveness, as it can increase bias while simultaneously enhancing or maintaining model performance.", "questions": "1. Can more be discussed on the potential other bias functions besides statistical parity? \n2. Do the authors believe this attack scenario is reasonable in real-world settings? Although an example is provided of a banker and has been used in prior work, but it feels somehow contrived and would look forward to perhaps more realistic settings where the attackers have more restricted access (e.g., visibility of the existing graph and only able to construct and connect new nodes, etc.).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. Clear Structure and Argumentation: The paper is well-organized, providing a clear and compelling argument for the importance of studying deceptive fairness attacks in graph learning models. \n2. Robust Experimental Design: The experimental design is of high quality, with all mathematical symbols and notations meticulously explained.\n3. Transparent Results Presentation: Results are presented clearly and concisely, with visual aids and detailed explanations that make the findings accessible and easy to understand, showcasing the effectiveness of the FATE framework.\n4. Problem Novelty: The proposed work focuses on adversarial robustness of fair graph learning, which needs more exploration.", "weaknesses": "It is noted the below are minor weaknesses:\n1. Grammatical Typos: There are minor grammatical errors present, such as in Section 6.1 on page 6, where the phrase \"It randomly deleting edges...\" should be corrected to \"It randomly deletes edges...\". \n2. Incomplete Introduction of Fairness Definitions: In Section 2B, when algorithmic fairness definitions are introduced, the paper provides English definitions but omits corresponding mathematical definitions. Including these mathematical definitions would enhance clarity, especially as the individual fairness definition is important when analyzing results.\n3. Inconsistent Organization: The paper utilizes a letter-based organization in some sections and a numerical organization in others. For instance, in Section 4, ideas are laid out numerically but then referred to using letters (A, B,...).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O7O8VgHv5q", "reviewer": "Reviewer_Jcma", "summary": "This paper investigates deceptive fairness attacks on graph learning, introducing a meta-learning-based framework, FATE. Designed with broad applicability, FATE targets biases in graph neural networks. Using real-world datasets for semi-supervised node classification, the authors demonstrate FATE's ability to amplify biases without compromising downstream task utility. This emphasizes the covert nature of these attacks. The study hopes to spotlight adversarial robustness in fair graph learning, guiding future endeavours towards creating robust and equitable graph models. The paper is a commendable exploration of the crossroads of fairness, adversarial attacks, and graph learning.", "questions": "Refer to the weakness part.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The topic of this paper is attacking the fairness of GNNs by a poisoning attack setting, which is valuable for building trustworthy GNNs. The method in this paper is easy to follow. In the experimental evaluations, the authors attempt to provide deep analysis upon validating the effectiveness of the proposed method, which is great for the audience to obtain insights and understanding of the vulnerability of GNN fairness.", "weaknesses": "1.Limited novelty. The limitation of existing works is weak (section 2-c). For limitation 1, this paper still only attacks one fairness concept when generating the adversarial graph. For limitation 2, the operation space depends on the practicality of the attack. For limitation 3, the specially designed module for maintaining performance is not presented in this paper. Authors are suggested to revise this part to highlight the contribution of this paper.\n\n2.Inaccurate/Unclear statements. For the budget limitation in the “capability of the attacker”, please be aware that the ||.||_{1,1} (according to the common definition of matrix norm) focuses on the maximum number of perturbations among nodes and cannot reflect the number of total perturbations. The definition of d(G,\\tilde G) should also include the changes on X. In the 4-c, the \\hat{y_(i,1)} discussing the sensitive attributes is repeated with that defining the label in 4-B.\n\n3.The design for keeping the performance of GNNs is not presented in the equation (1). Authors are suggested to discuss why the proposed method can achieve the performance goal, as presented at the beginning of this paper.\n\n4.The operation in equation 6 should be explained with more details to show how to handle different connection statuses and gradient statuses. Moreover, the flip and add operations should also be explained to show how they happen.\n\n5.For definition 1, authors are suggested to explain why the conclusion from IID assumption can be used in the graph data, where nodes are non-IID. Moreover, according to the definition of CDF, the integral starts from -infinity. Authors are suggested to revise related symbols or statements in section 4.\n\n6.In section 5, authors are suggested to explain that L_s is the Laplacian matrix of S, avoiding the confusion of audience who are not familiar with fairness.\n\n7.Limited evaluation. It is worth noting that the surrogate model is SGC while the target model is GCN, and they almost have extremely similar architecture. Authors are suggested to evaluate the effectiveness of the proposed method on other target GNN architectures (e.g., GAT, GraphSAGE) to follow the attack setting of this paper (section 3.1, attackers have only access to the graph data).\n\n8.Evaluation metric. It is worth noting that the fairness of GNNs is at the cost of performance. Although it is great to see the fairness deduction with limited performance cost. However, FA-GNN works well in a lot of cases. Considering that both fairness and model performance is the design of this paper, authors are suggested to compare the (\\delta SP)/(\\delta Acc) to evaluate the bias increment on unit acc cost.\n\n9.Confusing analysis on the effect of the perturbation rate. I understand that the authors attempt to show insights on the adversarial graph. However, it is hard to digest the operation (delete or add) on the same/different label/attribute. The discussion in Figure 1-b is also confusing. I suppose that detailed explanations of what exactly happened on each bar will make a more clear discussion. Authors are suggested to revise the paragraphs related to figures 1 and 2.\n\n10.According to the effectiveness table results, authors are suggested to explain why the proposed method can improve the performance of GNNs.\n\n11.On the “Effect of the perturbation rate” in section 6.2. Intuitively, more perturbations will make the learned parameters farther from that learned from the original graph. Thus, the availability scope of the learned adversarial graph will be limited by the perturbations, i.e., the higher budget will result in more unexpected behaviours of GNN trained on the poisoned graph. Authors are suggested to revise and discuss it in this paper, which is the limitation of the gradient-based attack method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I8tEz4iMaK", "reviewer": "Reviewer_5Ww3", "summary": "The paper \"Deceptive Fairness Attacks on Graphs via Meta Learning\" proposes a meta-learning approach for exacerbating demographic bias in the prediction of a given, unknown, victim model operating on the input graph; It is based on the optimization of a surogate model to define edges (or features to modify). It shows that their approach is able to manipulate edges and features  of the graph so that the performance of different victim models remains constant while the bias is increased.", "questions": "1. I wish the paper could have inspected some possible ways to prevent such attacks. The approach announce that the goal is to better understand. Ok, but what can we do, that would be positive, from the outcomes of the model ? Would it be possible to give some insights for good ways to defend from such attacks ? \n\n2. The considered bias is not fully defined in sec 4, for instance for the instantiation 1: you give the way you estimate both pdf but finally what is the score considered ? an mse, a kl, or what ?  Also, would it be possible to consider a targeted attack that would favor a specific population ? \n\n3. Would it be possible to specify more deeply $\\nabla_{\\cal G} \\Theta^{(T)}$ ? is it equal to $ \\epsilon \\nabla_{\\cal G} \\nabla_\\Theta l({\\cal G}, Y,\\Theta,\\theta)|_{\\Theta^{(T-1)}}$, with $\\epsilon$ the step size of update of the surogate ? \n\n4. I have difficulties to well understand the recursive definition of (3) and its connection with (2). Could you clarify please ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "Very interesting approach and results. \n\nLooks theoretically sound.", "weaknesses": "The paper sometimes lacks of carity, with some defintions not given (e.g., Y never defined in sec 2) or only in the appendix. In fact I had to go many times in the appendix to understand the core concepts of the approach, which is not very comfortable for the reader. I feel the formalization of the problem/method should include some separated notation for the victim and the surogate model, cause it was a bit confusing. Maybe what we want is that we are good for any victim model from a given distribution of victims ? Setting the problem like this would made the problem easier to understand from my point of view. Results are very hard to follow as some notation are not specified at all (e.g., Ptb which is the perturbation budget but we have to infer it) and every important details as the evaluation metrics are only given in the appendix (I understand the choice for a lack of space but only give some words on it (e.g. simply say delta sp is the bias) and refer to the corresponding section in the appendix would be helpful. Also please better specify the experimental questions you are inspecting in each section of the experimental part, because we can be a little lost at the first read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)