Learning Fair Graph Representations via Automated Data Augmentations
Authors: Hongyi Ling
Zhimeng Jiang
Youzhi Luo
Shuiwang Ji
Na Zou
Venue: ICLR 2023 notable top 25% (2023)

Abstract: We consider fair graph representation learning via data augmentations. While this direction has been explored previously, existing methods invariably rely on certain assumptions on the properties of fair graph data in order to design fixed strategies on data augmentations. Nevertheless, the exact properties of fair graph data may vary significantly in different scenarios. Hence, heuristically designed augmentations may not always generate fair graph data in different application scenarios. In this work, we propose a method, known as Graphair, to learn fair representations based on automated graph data augmentations. Such fairness-aware augmentations are themselves learned from data. Our Graphair is designed to automatically discover fairness-aware augmentations from input graphs in order to circumvent sensitive information while preserving other useful information. Experimental results demonstrate that our Graphair consistently outperforms many baselines on multiple node classification datasets in terms of fairness-accuracy trade-off performance. In addition, results indicate that Graphair can automatically learn to generate fair graph data without prior knowledge on fairness-relevant graph properties.

Published as a conference paper at ICLR 2023
LEARNING FAIR GRAPH REPRESENTATIONS VIA AUTOMATED DATA AUGMENTATIONS
Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji; Na Zou" Texas A&M University College Station, TX 77843, USA
{hongyi Senyylingg ling, zh zhimeng j, yz luo, $ji, nzoul m @0tam...eeeee.mmm..m.. edu
ABSTRACT
We consider fair graph representation learning via data augmentations. While this direction has been explored previously, existing methods invariably rely on certain assumptions on the properties of fair graph data in order to design fixed strategies on data augmentations. Nevertheless, the exact properties of fair graph data may vary significantly in different scenarios. Hence, heuristically designed augmentations may not always generate fair graph data in different application scenarios. In this work, propose method, known Graphair, learn fair rep- resentations based on automated graph data augmentations. Such fairness-awe aware augmentations are themselves learned from data. Our Graphair is designed au- tomatically discover fairness-aware augmentations from input graphs in order to circumvent sensitive information while preserving other useful information. Ex- perimental results demonstrate that our Graphair consistently outperforms many baselines on multiple node classification datasets terms of fairness-accuracy trade-off performance. In addition, results indicate that Graphair can automati- cally learn to generate fair graph data without prior knowledge on fairness-relevant graph properties. Our code is publicly available as part of the DIG package hittss//gthhub.co////vlllallCC
INTRODUCTION
Recently, graph neural networks (GNNs) attract increasing attentions due to their remarkable perfor-
mance (Gao et al. 2021 Gao & Ji 2019 Liu et al. 2021a Yuan et al.) 2021) in many applications,
such knowledge graphs (Hamaguchi
2017
molecular property prediction (Liu al. [022]
2020 Han et al. 2022a) and social media mining (Hamilton et al. 2017). Despite recent ad vancee in graph representation learning (Grover Leskovec [2016] Kipf & Welling 2017 2016 Gilmer al.,
2017 Han et al. 2022b), these GNN models may inherit or even amplity bias from training data (Dai Wang (021), thereby introducing prediction discrimination against certain groups defined by sensitive attributes, such as race and gender. Such discriminative behavior may lead to serious ethical and societal concerns, thus limiting the applications of GNNs to many real-world high-stake
tasks, such as criminal justice (Suresh & Guttag 2019), job hunting (Mehrabi et al. 202T). health-
care (Rajkomar et al. 2018) and credit scoring (Feldman et al. 2015 Petrasic et al. 2017 Hence,
it is highly desirable to learn fair graph representations without discriminatory biases (Dong et al.
2022 Zhang et al. 2022 Kang et al. 2022 Dai et al. 2022).
A primary issue (Mehrabi et al. 2021 contain biases, which is the source of discriminative behavior of models. Thereby, many existing works (Agarwal al. 2021; Kose & Shen| 2022. Spinelli et al. (02T) propose to learn fair graph representations by modifying training data with fairness-aware graph data augmentations. These methods propose some graph data properties that are beneficial to fair representation learning, and then adopt heuristic graph data augmentation operations, including node feature masking and edge perturbation, refine graph data. However, the proposed graph properties (Spinelli et al. [021] Kose & Shen 2022) may not be appropriate for all graph datasets due to the diverse nature of graph data. For example, balanced inter/intra edges (Kose & Shen 2022) may destroy topology
Olteanu al. 2019) in faimeess is that training data usually
"Equal senior contributions

---

Published as a conference paper at ICLR 2023
structures of social networks, leading to the loss of important information. Even if the proposed graph properties are effective, the best graph properties may vary significantly in different scenarios. Hence, it is highly desirable to automatically discover dataset-specific fairness- augmentation strategies among different datasets with single framework. To this end, a natural question is raised:
Can we achieve fair graph representation learning via automated data augmentations?
In this work, we attempt address this question via proposing Graphair, novel automated graph augmentation method for fair graph representation learning. A primary challenge is how to achieve fairness and informativeness simultaneously in the augmented data. As intentionally avoid suming prior knowledge on what types of graphs are considered fair, we propose to employ an adversary model to predict sensitive attributes from augmented graph data. A fair augmented graph should prevent the adversary model from identifying the sensitive attributes. In addition, we propose to retain useful information from original graphs by using contrastive learning to maxi- mize the agreement between original and augmented graphs. Experimental results demonstrate that Graphair consistently outperforms many baselines on multiple node classification datasets in terms of fairness-accuracy trade-off performance.
BACKGROUND AND RELATED WORK
2.1 FAIR GRAPH REPRESENTATION LEARNING
In this work, study the problem of fair graph representation learning. Let (A, be a graph with n nodes. Here, A E {0, 1 juxn is the adjacency matrix, and Aij = 1 if and only there exists an edge between nodes i and j. X = [x1, _T,'" E Rax is the node feature matrix, where each F; Rd is the d-dimensional feature vector of node i. S {0, 1)" is the vector containing sensitive attributes (c.g.. gender or race) of nodes that should not be captured by machine learning models to make decisions. Our target to learn fair graph representation model f X) + H E Raxd", and the learned representation classification model 0 + Ý E 10" to predict the binary label of nodes in G. Particularly, for an ideal fair model ʃ. the output representation H should result in a prediction Ý that satisfies the fairness criteria. In general, there exist several different definitions of fairness criteria, including group fairness (Dwork et al. [2012] Rahnatalllli et al. 2019 Jiang et al. (0022b). individual fairness Kang al. 2020 Dong et al. [202]] Petersen et al. 2021 and counterfactual fairness (Agarwal Ma et al. 2022). In this work, we focus on group fairesss, which is defined as
= f(A, X) is fed into a
et al. 2021
P(Y = P(P 1), i= ,R.
where Y; is the prediction for node i, and S; is the sensitive attribute of node i. Note that even though the sets of node attributes or features in X and S are disjoint, correlations may exist between (A,X) and S. Hence, even if S is not explicitly exposed to f. f may implicitly infer parts of S from (A, X) and produce biased representation H, thereby making the prediction Y unfair. How to prevent models from intentionally fitting these correlations is the central problem to be solved in achieving fair graph representation learning.
Currently, several studies have proposed different strategies to achieve fair graph representation learning. An early study (Rahman al. 2019) proposes train the model through fair random walks. Some recent studies (Li et al. 2020 Laclau et al., (02T)) propose to reduce prediction dis- crimination through optimizing adjacency matrices, which can improve fairnsss for link prediction tasks. In addition, adversarial learning is another popular strategy to achieve fairness on node rep- resentation learning tasks. Many studies (Fisher et al.) 2020 Dai & Wang. 2021 Bose Hamilton, 2019) adopt adversarial learning to filter out sensitive attribute information from the learned node representations. Overall, most existing methods learn fair representations via altering model train- ing strategy with faimnsss regularization. However, a primary issue in faimess learning lies in the fact that training data usually possess bias. Hence, an alternative and highly desirable solution is to modify data through data augmentations, thus enabling models to learn fair representations easily. In this work, we design a learnalee graph augmentation method to reduce bias in graph data, leading to more effective faimess-aware representation learning graphs.
Laclau
2

---

Published as a conference paper at ICLR 2023
2.2 GRAPH DATA AUGMENTATIONS
Inspired by the success of data augmentations in computer vision and natural language process- ing, graph data augmentation (Zhao et al., 2022) attracts increasing attention in academia. Most studies You et al. 2020; Zhu et al. 2020 Wang et al. [021]] Veličković et al.) 2019; You et al.) 2021 Rong al. 2020) are based on uniformly random modifications of graph adjacency matrices or node features, such as masking node features, dropping edges, or cropping subgraphs. In addi- tion, recent studies (Luo et al., 2023 Zheng et al., 2020. Luo al. 2021 Zhao et al. 2021 Chen et al. 2020) design learnable data augmentation methods to enhance task-relevant information in augmented graphs. Note that none of the above methods are fairness- aware and only a few studies have investigated fairness-aware graph augmentations. (Spinelli et al. (202T) argue that the tendency of nodes with the same sensitive attribute to connect leads to prediction discrimination. Thereby, they propose biased edge drop algorithm to reduce such tendency in graphs, resulting in fairness improvement on prediction tasks. [Agarwal et al. (202T) design a graph data augmentation method in the contrastive learning framework via modifying sensitive attributes. [oose & Shen (2022) study correlations between sensitive attributes and learned node representations, and propose several graph augmentations minimize an upper bound of the correlations achieve fairness. However, these fairness-aware augmentation methods are all based on some strong assumptions or definitions about the properties that fair graph data should have. Such assumptions or definitions may not hold in different scenarios, so in practice, empirical comparisons are needed to find out the best choice. In addition, these heuristic augmentation operations may accidentally remove most of the useful infor- mation from the graph. For instance, both edge drop algorithms proposed by Kose & Shen (2022) and and (Spneelli et al. (202T) may drop most of the edges and destroys the graph structure in some cases. Hence, in practice, these methods do not consistently achieve good performance on all datasets.
3 FAIRNESS VIA AUTOMATED DATA AUGMENTATIONS
While previous fairness-aware graph data augmentations all rely on manually defined and fixed fairness-relevant augmentation strategies, we explore a more adaptive and effective method to dis- cover fairness-aware graph augmentations by automated augmentation models. Note that though automated graph augmentations have been applied to some graph representation tasks (Luo al., 2023 2021: Zhao et al.) 202T), they have not been studied in fair graph representation learning. In this work, we propose Graphair, an automated graph augmentation method for fair graph represen- tation learning. Graphair uses an automated augmentation model to generate new graphs with fair topology structures and node features while preserving the most informative components from input graphs. The augmentation model is trained end-to-end with multiple optimization objectives in or- der to circumvent sensitive information while retaining other useful information simultaneously. To the best of our knowledge, Graphair is the first automated graph augmentation method addressing group fairness with a theoretical guarantee of fairness and informativeness.
3.1 AUTOMATED GRAPH AUGMENTATIONS
We first present the details of the augmentation process. Given an input graph G = (A, SJS, we use the automated augmentation model g to generate a new graph g' = (A', X S as
TA. Tx = x), A'= =A)), X' Txx)x(X).
(2)
Here, Ta is the edge perturbation transformation, which maps to the new adjacency matrix A' by removing existing edges and adding new edges. Tx is the node feature masking transformation, which produces the new node feature matrix X' by setting some values of to zero Ta and Tx contain the exact transformations for each edge and node feature in G. In other words, the augmentation model decides whether there is an edge connecting any two nodes in 9 and whether each value in X should be set to
not.
In the augmentation model g, a GNN-based augmentation encoder gene : (A, + Z E guxdd is first used to extract di-dimensional embeddings Z for nodes in g. We adopt graph convolutional network (GCN) (Kipf & Welling 2017) as the GNN encoder here. Afterward, the exact transforma- tions for each edge and node feature are performed as described below.
Edge perturbation. Given the embedding Z, an multi-layer perceptron (MLP) model MLPA first computes the hidden embeddings ZA E IR nxd, from Z, then inner-product decoder computes the
3

---

Published as a conference paper at ICLR 2023
edge probability matrix A' E I="*" where the value A'i at the i-th row. j-th column of the matrix A' denotes the predicted probability that an edge exists between the nodes and j in G'. Finally, the output adjacency matrix A' is obtained by sampling from the Bernoulli distribution parameterized with the probabilities in A'. Formally, this process can be described as
A = MLP (Z), A' = a (ZaZz), Alj ~ Bernoulli (A's) for i,j = 1, ,, n. (3)
where (-) is the sigmoid function.
Node feature masking. Given the embedding Z, an MLP model MLPx first computes the mask probability matrix M E Rnndd where the value Mij at the i-th row, j-th column of the matrix M denotes the predicted probability that the j-th feature of node i is not set to zero. Afterward, the mask matrix M is sampled from the Bernoulli distribution parameterized with the probabilities in M. and the new feature matrix X' is obtained by multiplying X by M. This process can be formally described as
Zx ML)x M
(Zx), (Z),, Maj Bernoulli
Mis) for i,j 1,, , X MoX, (4)
where O the Hadamard product, and (.) is the sigmoid function.
Note that the Bernoulii sampling for adjacency matrix A' and mask matrix M are non-differentiable. To make the augmentation model g end-to-end trainable, we adopt the commonly trick to ap- proximate the Bernoulli sampling in Eq. (3) and (4). Specifically,
relax the Bernoulli sampling procedure by the Gumbel-SSfftax reparameterization trick (Jang et al.) 2017 Maddison et al.) 2017 2014]. Given probability P computed from parameterized model (o, the relaxed Bernoulli sam- pling calculates continuous approximation P 1+exp(- (xexp(((lo where is temperature
hyperparameter and G Gumbel(0, 1) is a random variable sampled from the standard Gumbel distribution. For the forward propagation, the discrete value P [P + 1J is used as the result sampled from the Bernoulli distribution with the probability P. For the backward propagation, ttraighttthrough gradient estimator (Bengio et al. 2013) is used, which approximates the gradient as V V.P. Re V.P.
3.2 ADVERSARIAL TRAINING
As objective is to generate fair augmentations reduce bias, the ideal augmentation model should satisfy the fairness property. In other words, it should assign low probabilities to graph elements (edges, node features) that cause prediction bias. However, we cannot achieve it via super- vised training because there is no ground truth indicating which graph elements lead to prediction bias and should be modified. To tackle this issue, we propose to use an adversarial learning based method to implicitly optimize the model to learn to mitigate bias in the input graph. Specifically, we use an adversary model k: X') + Š E [0, 1J to predict the sensitive attribute S from the new adjacency matrix A' and new node feature matrix X' generated by the augmentation model g. The adversary model l and the augmentation model g are jointly trained via adversarial fashion. In this process, is optimized to maximize the prediction accuracy of the sensitive attribute, while is optimized mitigate bias in A' and X' so that is difficult for the adversary model k to identify sensitive attribute information from A' and X'. Formally, this adversarial training process can be described as the following optimization problem:
Sllog +1 (1- -5))log (1-8:)}
min max Lady min max g
(5)
where S, is the prediction of the sensitive attribute of node by the adversary model k.
3.3 CONTRASTIVE TRAINING
We note that only using the adversarial training may cause the augmentation model to collapse into trivial solutions. For instance, g may learn always generate complete graph and set all node
Here we use negative binary cross-entropy loss, so the adversary model & aims maximize Tedee
4

---

Published as a conference paper at ICLR 2023
Input Graphç 0
Augmentation Moduleg
Fair Views'
MLP
Sampling
GNN
A'
Sene
MLPX(.)
Bamp
M
M
X
X
Adversary k(+)
GNN S(.)
Shared Weights
GNN f(-)
Sensitive Attribute
Node Feature |
Add & Delete Edge
H
Maximize Agreement
H
Fairness
Mask Node Feature
Informativeness
Figure 1: An overview of our framework.
features to zero, which contains no bias, since all nodes are equivalent. Such augmented graphs are not informative at all because they lose all the information from the input graphs. To make the augmentation model g satisfy the informativeness property, i.e., preserving the most informative components of the input graph in the generated graphs, we additionally use contrastive learning objective during training.
Given the input graph a GNN-based representation encoder f to extract node representations H = f(A, X) and H' f(A',X') from G and G", respectively. Afterward, we optimize the augmentation model g and the representation encoder f jointly by minimizing a contrastive objective, which maximizes the similarity between the representations of the same node in H and H'. Specifically, let h, and hy denote the representation of node i H and H', respectively. For node i, we consider (hi, h)) as a positive pair, and (he, h2) and (h;, ht) for any node j other than negative pairs. We define the representation similarity as sim(h;, KG) c(t(hh),((h()) where is the cosine similarity and is a non-linear projection implemented with a two-layer MLP model. We follow Zhu el al. 2020) to define the contrastive objective for any positive pair (h,, ht)
S, and the augmented graph G' = {A', S), we first use
exp (sim(hu, h/)/T)
1(h,, M)) -log Σn= exp (sim(1,, (5mm(),)))/7)) + ΣØ=1 1 expp (sim(h,, hy)/T)²
where t denotes the temperature parameter, []=]]] {0, 1} is the indicator function whose value is I if and only if a i. The overall contrastive objective is computed over the positive pairs (h4, h!) and (H, hs) for all nodes as
Leon 1
Σ [[hh, + 1(h4. h,))
n
2n
To prevent the augmentation model g from generating graphs that deviate too much from input graphs, we add reconstruction. based regularization term to the overall training objective. Specifi- cally, let TBEE and [.ME denote binary cross-entropy loss and mean squared error loss, respectively, and the regularization term is defined as
7 Teconnst TBCCE( (A, A') + ATMSE(X; X')
Asylog
A11s))
Aij) (1-
(1- (1-A..)) A'r)] |X - -X (8)
where À is hyperparameter, and || || denotes the Frobenius norm of matrix (Golub & Van Loan 1996).
To sum up, the overall training process can be described as the following min-max optimization procedure,
min max L = min max a + Blusm + Tmecomsts
f.g k f.g
5

---

Published as a conference paper at ICLR 2023
where a; y hyperparameters. The parameters of augmentation model g, adversary model k and representation encoder f are jointly optimized with this min-max optimization procedure. In each training step, we first update the parameters of f and g to minimize L while keeping & fixed, then update the parameters of to maximize Lad while keeping f and fixed. See Figure for for an overview of our proposed Graphair method. The training algorithm is summarized in Appendix
3.4 DISCUSSIONS
Graphair learns different fairness-aware augmentation strategies for different graph datasets by the automated augmentation model, thereby climinating the negative effect of fixed renlestt augmentation strategies (Spinelli et al.) 2021 Agarwal et al. [02T Kose & Shen 2022). In addi- tion, Graphair mitigates bias by modifying both graph topology structures and node features, while some existing studies (Spinelli et al.] 2021) only consider one of them. We demonstrate these advan- tages through extensive empirical studies in Section 4.2 and (4.) Furthermore, we show Section 3.5 and 3.6 that the used training objectives can be theoretically proven to help the augmentation model generate new graphs with fair topology structures and node features, and preserve the most informative components from the imput graph simultaneously. Specifically, use adversarial and contrastive learning to optimize the augmentation model to satisfy the fairness and informativeness properties, respectively.
3.5 THEORETICAL ANALYSIS OF FAIRNESS
Following Madras et al. (018)) we quantify the unfairness of a classifier d X'), - [0, 1 using demographic parity distance. Given a graph g' (A', x', let ý = d( x') E [0. 1] denote the prediction of the classifier d and Y; is the prediction of node i. The demographic parity distance is defined as (d) A 50 (Yr) -E s= (Ýz)), where S and S denote the set of nodes whose sensitive attributes are and I, respectively. Note that (D = 0 if Ý 1 i... the group fairness discussed in Section 2.1 is satisfied. The following theorem shows that minimizing the optimal adversarial loss is equivalent to minimizing the unfairness of the classifier d, so minimizing the performance of the adversary model can indeed encourage the augmentation model generate fair graphs.
Theorem 1. Let G', k S be defined above. For any downstream task, we consider a classifier d X") + y E [0, 1]"h predicting label Y {0,, 13" using G' as input. Assume the adversarial loss for each sample bounded, i.e., there exists constant M that [5,log (1 (1-Si)log (1 (1- S: IS M holds for each sample. Then we show that the demographic parity Apr(d) is bounded by the optimal adversarial objective value Ladv", i.e. Ludd" * represents the maximal number of samples with the same sensitive attributes.
n' M mll- (DP(() mlI-e-rr where ri'
n'M
Detailed proof of this theorem is given in Appendix A.I
3.6 THEORETICAL ANALYSIS OF INFORMATIVENES:
We quantify the amount of information obtained about one random variable by observing the other random variable by mutual information. We show in the following theorem that minimizing the contrastive loss Leon is equivalent to maximizing a lower bound of the mutual information g") between the original graph G and the augmented graph G', thus achieving informativeness.
Theorem 2. Let G. G' H and H' be defined as above. Our contrastive objective is a lower bound of mutual information between the input graph G and the augmented graph G'. Formally,
-Lam G'):
(10)
Detailed proof of this theorem is given in Appendix A.2
A.2
3.7 COMPLEXITY ANALYSTS
Graphair shares the same time and space complexity as the GNN architecture of the representation encoder f during inference because only f is used to compute node representations. During training.

---

Published as a conference paper at ICLR 2023
Table 1: Comparisons between our method and baselines on node classification tasks in terms of accuracy and fairness. The best results are shown in bold.
NBA
Pokec-z
Pokec-n
Method
ACC
App 4
Ago
App 4
Ago 4
ACC 1
App 4
Ago 4
FairWalk
64.54 +: 2.35
3,67 4: 1.28
9.12 4 7.06
67.07 +: 0.24
7.12
+: 0.74
8.24 4: 0.75
65.23 4: 0.78
4.45 1.25
4.59 =: 0.86
FairWalk X
69:74 = 1.71
14.61 +: 4,98
12.01 + 5.38
69.01 = 0.38
7.59
+ 0.96
9.69 + 0.09
67.65 +: 0.60
4,46
0.38
6.11 0.54
GRACE
70.14 1.40
4:
7.67 13778
68.25 1: 0.99
+: 0.71
1
67.81 4: 10.77
1:
0.69
GCA
70.43 1.19
18.08
4,80 20.04 4.34
69.34 0.20
6.07
# 0.96
7.39 + 0.82
67.07 = 0.14
7,90 1.10
8.05 1,07
FairDrop
69.01 + 1.11
3:66 # 2.32
7.61 + 2.21
67.78 = 0.60 5.77
1.83 5:48 # 1.32
67.32 # 0.61
4.08 + 1.05
3.77 1.00
NIFTY
69.93 0.09
0.09
+:
4.70 + 1.04
67.15 - 0.43
0.99
+
65.52 - 6.51
0.51
5.14 0.68
FairAug
66.38 +: 0.85
4,99 +: 1.02
6.21 + 1.95
69.17 + 0.18 5.28
+ 0.49 6.77 + 0:45
68.61 + 0.19
5.10 0.69
5.22 = 0.84
Graphair
69.36 + 0.45
2.56 + 0.41
4.64 + 0.17
68.17 = 0.08 2.10 + 0.17 2.76 + 0.19
67.43 = 0.25 2.02 0.40
1.62 0.47
Graphair computes the adjacency matrix A'' and the pairwise similarity in the contrastive loss, thus having a space complexity of Onn"), where n is the number of nodes. Fortunately, we can easily adopt the graph sampling-bar mini-batch training and reduce the space complexity to (m²)), where m is the batch size. More details on mini-batch training are given in Appendix
batch training method proposed by ZZnn et al. (2020) to perform
EXPERIMENTS
In this section, we evaluate Graphair on three real-world datasets, including NBA, Pokec-z and Pokec-n More details datasets are given in Appendix F.1 Experimental results show that Graphair outperforms many baselines on node classification tasks in terms of both fairness and accuracy. To gain insights from Iearned fair graph data, we provide comprehensive analysis on learned fair graph topology structures and fair node features. Our analysis results are consistent
with studies (Spinelli et al. [002 Kose Shen 2022 Jiang al. 2022a Dai & Wang 202T). We
also provide runtime experiments and hyperparameter studies in Appendix D
4.1 EXPERIMENTAL SETTINGS
Evaluation metries. We use accuracy evaluate prediction performance of node classification tasks. To quantify group fairness, we follow studies (Louizos et al.) 2016; Beutel et al. 2017) to
adopt demographic parity ADr = [P( = 1/5 = 0) P(Y = 1|s = 1) and equal opportunity A IP(Y 1|5 O,Y 1) - P(Ý 1|s 1, 1)}. where Y and Y denote ground-truth labels and predictions, respectively. Note that a model with lower DP and EO implies better fairness performance.
Baselines. We compare our methods with the following baseline methods, including (1) Fairwalk (Rahman al. 2019), fairness-aware random walk (Grover & Leskovee, 2016) for unsupervised node representation learning task; (2) GRACE (Zhu et al.) 2020). deep graph contrastive repre- sentation learning with uniform random graph augmentations; (3) GCA (Zhu al. 2021), graph contrastive learning with adaptive augmentations; (4) NIFTY (Agarwal et al. 2021). the first graph contrastive learning method with fairness-aware graph augmentations. Note that only use the un- supervised component of NIFTY to learn node representations; (5) FairDrop (Spinelli et al. 2021), heuristic edge dropping method to enhance fairness in graph representation learning: (6) FairAug (Kose& & Shen 2022). an adaptive data augmentation method for fair node representation learning. We adopt FairDrop and FairAug in the contrastive learning framework of GRACE to learn node representations, since they are both graph augmentation methods. The optimal hyperparameters for all methods are obtained by grid search.
Evaluation protocol. We use evaluation protocol following Veličković et al. (0099) for a fair comparison. Specifically, we first learn the fair representation H in a fully unsupervised manner as described in Section 3.2 and 3.3 Then the representation H is used to train and test a simple
We adopt the graph mini-batch training method proposed by Zeng et al. 2020 on Pokec-z and Pokec-n datascts.
7

---

Published as a conference paper at ICLR 2023
NBA
Pokec
Pokec_n
OUTS FaiDrrpp NIFTY
08.0
ACC
FairDrop
NIFTY
150
PairAug
FarDrop
TarAug
3.5
2.0
2.5
3.0
4.0
4.5
DP
DP
DP
Figure 2: ACC and DP trade-off on three real-world datasets. Upper-left corner (high accuracy, low demographic parity) preferable.
Table Comparisons among different components in the augmentation model.
NBA
Pokee-z
Pokec-n
Models
ACC
App 4
Ago
ACC
A Appl
Ago
ACC
App 4
Ago 4
Gruphair wio
3.99 0.45
Graphair w/o EP
66.67
+ 0.71
4.44 = 2.64 6.74 = 2.13
69,34 = 0.40
5.75 0.63
5.91 0.06
68.59
0.17
3,31
0.57
3,71 0,97
Graphair
69 00.36.3 + 0.45 2.56 = 0.41 4.64 + 0.17
68.17 1: 0.08 2.10 0.17
2.76
0.19
67.43
0.25
2.02
0.40
1.62 = 0.47
classifier. The accuracy and fairness of this classifier are used as the proxy for the quality of the learned representation H.
4.2 EXPERIMENTAL RESULTS
Fairness and accuracy performance. Table [ shows accuracy, demographic parity, and equal opportunity metries of our proposed Graphair, compared with baselines Section 4.1 on the three real-world datasets. From the results, we have the following observations:
Our proposed Graphair consistently achieves the best faimess performance in terms of demo- graphic parity and equal opportunity evaluated datasets. For example, compared with GRACE, our method reduces demographic parity by 65.8%, 67.2% and 81.2% on NBA, Pokec-z, and Pokec-n datasets, respectively, with comparable accuracy performance.
Fairness-aware augmentation methods (e.g., FairDrop, NIFTY, and FairAug) have lower predic- tion bias compared to GRACE and GCA. It is worth noting that these heuristic augmentation methods targeting manually designed fair graph properties may not consistently achieve state-of- the-art performance for all datasets due diverse graph data. Specifically, FairDrop outperforms NIFTY on Pokec-n dataset, while NIFTY outperforms FairDrop on NBA and Pokec-z datasets. To this end, Graphair can automatically learn to discover fairness-aware augmentations on differ- ent graph datasets and thus outperforms all these fairness-aware methods in terms of demographic parity and equal opportunity on all three datasets.
Trade-off between accuracy and fairness. We further compare the accuracy-fairres fairness trade-off performance of Graphair with several baselines. We choose demographic parity the fairness metric. Figure 2 shows the Pareto front curves generated by a grid search of hyperparameters for each method. The upper-left corner point represents the ideal performance, i.e., highest accuracy and lowest prediction bias. The results show that Graphair achieves the best ACC-DP trade-off compared with all fairness-awe aware basclines three datasets.
4.3 ABLATION STUDIES
Graphair considers two graph transformations to mitigate bias in node features and graph topology structures. In this subsection, we conduct ablation studies to investigate the contributions of two graph transformations and demonstrate the advances of Graphair. In other words, we investigate both fair node features and graph topology structures enhance prediction fairness (i.e., lower DP and EO). Specifically. we remove node feature masking, denoted as "Graphair w/o FM". and remove edge perturbation, denoted as "Graphair w/o EP". Table shows that Graphair outperforms both "Graphair w/o FM" and "Graphair w/o EP" in terms of demographic parity and equal opportunity on all three datasets. Experimental results demonstrate that both fair node features and graph topology
8

---

Published as a conference paper at ICLR 2023
NBA
Pokec_
Pokec_1
5.935
0.
Originel
04
Fur
view
0,7
Density
6.73
Density
6.435
0333
3.00
6.20
0.40
6.42
0.50
5.23
0.40
E.54
0.00
64
0.99
0.00
0:23
0.39
0:00
Node sensitive homophily
Node sensitive homophily
Node sensitive homophily
Figure Node sensitive homophily distributions in the original and the fair graph data.
NBA
Pokec z
Pokec n
Spearman correlation
Origina Fair view
RA8-
Original Fair view
Original
0.20
0.07
For view
0.35
0.65
0.08
Spearman
Spearman
8.09
0.00
0.00
Feature index
Feature index
Feature index
Figure 4: Spearman correlation between node features and the sensitive attribute in the original and the fair graph data.
structures are beneficial to mitigating prediction bias. Methods only considering either node features or graph topology (e.g., FairDrop) are not promising due to the limited graph transformation space.
4.4 ANALYSIS OF FAIR VIEW
In this subsection, we study the properties of fair graph data generated by Graphair from graph topology and node features perspectives. Firstly, introduce node-wise sensitive homophily coef- ficient to characterize the distribution of sensitive attributes from the neighborhood. Given graph X,, X, S). node-wist sensitive homophily coefficient for node i, denoted as G₁ represents the
proportion of neighbors with the same sensitive attributes, i.e., G Σ/= As (.pa))) where n is Σn _ Ag
the number of nodes, and [ss==y]] is the indicator function evaluating to I if and only if s; sj-- Subsequently, we analyze the learned fair graph topology via node sensitive homophily distribution compared with the original graph topology. Figure shows that the learned fair graph topology duces average node sensitive homophily compared to the original graph topology. Such observation consistent with several previous studies (Spinelli et al., 2021 Kose & Shen 2022 Jiang al.,
2022a Dai & Wang 2021) that high node sensitive homophily values lead to prediction bias.
Additionally, we analyze the learned fair node features via Spearman correlation (Zwillinger & Kokoska 1999) between the sensitive attribute and non-sensitive features. Note that fair node fea- should have low Spearman correlation values. 4sows the top-10 Spearman correlation values in the original graph data. We can see that the learned fair node features reduce Spearman cor- relation values compared the original node features, thus preventing models from fitting the corre- lations as discussed in Section 1 These analysis results demonstrate that our method Graphair can automatically learn to generate fair graph data without prior knowledge of faimess--releaatt graph properties.
5 CONCLUSIONS
In this work, we propose Graphair, an automated graph augmentation method for fair representation learning. Graphair uses an automated augmentation model to generate new graphs with fair topology structures and node features, while preserving the most informative components from input graphs. We adopt adversarial learning and contrastive learning to achieve fairness and informativeness si- multaneously in the augmented data. Experimental results demonstrate that Graphair consistently outperforms oftte-of-theatt baselines on node classification tasks for real-world graph datasets in terms of faimess-acccrees trade-off performance. In the future, would like improve the effi- ciency of Graphair and extend Graphair to the case where only limited sensitive attribute information available.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work was supported, in part, by NSF (ISS-193976,, IIS-1900990, and IIS-2006861), and Cisco Research, The views and conclusions in this paper are those of the authors and should not be interpreted representing any funding agencies. We would also like to thank the helpful feedback from the anonymous reviewers.
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty Artificial Intelligence, pp. 2114-2124. PMLR, 2021.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 308.3432, 2013.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv:1707.00077 2017.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference Machine Learning, pp. 715-724. PMLR, 2019.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 3438-3445 2020.
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.
Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. A comprehensive survey on trustworthy graph neural networks: Privacy, robust- ness, fairness, and explainability. arXiv preprint arXiv:2204.0m 085500 2022.
Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairness for graph neural networks: A ranking based approach. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 300-310, 2021.
Yushun Dong. Jing Ma, Chen Chen, and Jundong Li. Faimess in graph mining: A survey. arXiv preprint arXiv:2204.0988 09888, 2022.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations theoretical computer science confer- ence, 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 2 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 2589-268,11 2015.
Joseph Fisher, Arpit Mittal, Dave Palfrey, and Christos Christodoollppouls. Debiasing knowledge graph embeddings. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7332-7345, 2020.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. Proceedings of the 36th International Confer- ence on Machine Learning, pp. 2083-2092, 2019.
Hongyang Gao, Yi Liu, and Shuiwang Ji. Topology-aware graph pooling networks. IEEE Transac- fions on Pattern Analysis and Machine Intelligence, 43(12):4512-451 2021.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pp- 1263-1272. PMLR,, 2017.
10

---

Published as a conference paper at ICLR 2023
G. H. Golub and C F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 3rd edition, 1996.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge transfer for out-of-knowledge-bel entities A graph neural network approach. In Proceedings of the Twenfy-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 1802-1808, 2017. doi: 10. 00.24963/jcai.201177773 2017/250. URL httpp:://////ooorrg//// 2111:////////////a2222////3
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference Machine Learning, pp. 8230-8244 PMLR, 2022a.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, Qingquan Song, Jundong Li, and Xia Hu. Geometric graph representation learning via maximizing rate reduction. In Proceedings of the ACM Web Conference 2022, pp. 1226-1237, 2022b.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmax, In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. Fmp: To- ward fair graph message passing against topology bias. arXiv preprint arXiv:2202.041887 2022a.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Fan Yang, Ali Mostafavi, and Xia Hu. Generalized de- mographic parity for group fairness. In International Conference on Learning Representations, 2022b.
Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. Inform: Individual fairness 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.
Thomas N Kipf and Max Welling. 1rXiv:1611.0777 1.1000008 2016.
Variational graph auto-encoders.
arXiv preprint
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
O Deniz Kose and Yanning Shen. Fair node representation learning via adaptive data augmentation. arXiv preprint arXiv:2201.088: 085599, 2022.
Charlotte Laclau, levgen Redko, Manvi Choudhary, and Christine Largeron. All of the faimess for edge prediction with optimal transport. In International Conference on Artificial Intelligence and Statistics, pp. 1782.782. PMLR, 2021.
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic faimess: Exploring and mitigating bias in graph connections. In International Conference Learning Representa- tions, 2020.
Meng Liu, Cong Fu, Xuan Zhang, Limei Wang, Yaochen Xie, Hao Yuan, Youzhi Luo, Zhao Xu, Shenglong Xu, and Shuiwang Ji. Fast quantum property prediction via deeper 2d and 3d graph networks. arXiv preprint arXiv: 106.08511, 2021a. 2021a.

---

Published as a conference paper at ICLR 2023
Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, Keqiang Yan, Haoran Liu, Cong Fu, Bora M Oztekin, Xuan Zhang, and Shuiwang Ji. DIG: A turkkey library for diving into graph deep learning research. Journal of Machine Learning Research, 22(240):1199 3021b. URL
Yi Liu, Hao Yuan, Lei Cai, and Shuiwang Ji. Deep learning of high-order interactions for pro- tein interface prediction. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 679 2020.
Yi Liu, Limei Wang, Meng Liu, Yuchao Lin, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d molecular graphs. In International Conference on Learning Representa- tions, 2022. URL https://ppenreview.neer.
wnwteeerrriii..tne/oouummm wwt.:/rtttf//////// wttp://wwwww///oomoo//////ssssoo Vid=givsRXsOOui
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. In International Conference on Learning Representations, 2016.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 779-787, 2021.
Youzhi Luo, Michael McThrow, Wing Yee Au, Tao Komikado, Kanji Uchino, Koji Maruhash, and Shuiwang Ji. Automated data augmentations for graph classification. In International Conference on Learning Representations, 2023.
Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. Learning fair node representations with graph counterfactual fairness. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 695-703, 2022.
Chris J Maddison, Daniel Tarlow, and Tom Minka. A sampling. Advances in Neural Information Processing Systems, 27, 2014.
Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. In International Conference on Learning Representa- lions, 2017.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In International Conference on Machine Learning, pp. 3384-3393. PMLR, 2018.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
Alexandra Olteanu, Carlos Castillo, Fernando Diaz, and Emre Kıemann Social data: Biases, methodological pitfalls, and ethical boundaries. Frontiers in Big Data, 2:13, 2019.
Felix Petersen, Debarghya Mukherjee. Yuekai Sun, and Mikhail Yurochkin. Post-processing for individual fairness. Advances in Neural Information Processing Systems, 34, 2021.
Kevin Petrasic, Benjamin Saul, James Greig, Matthew Bornfreund, and Katherine Lamberth. Algo- rithms and bias: What lenders need to know. White & Case, 2017.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. Proceedings of the 28th International Joint Conference on Artificial Intelli- gence, IJCAI' 19, pp. 3289-3295, 2019.
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic faimess in robust graph covering problems. Advances in Neural Information Processing Systems, 32, 2019.
Alvin Rajkomar, Michaela Hardt, Michael D Howell, Greg Corrado, and Marshall H Chin. Ensuring fairness in machine learning to advance health equity. Annals of internal medicine, 169(12):866 872, 2018.
12

---

Published as a conference paper at ICLR 2023
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2020.
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop:
Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence, 2021.
Harini Suresh and John V Guttag. framework for understanding unintended consequences of machine learning, arXiv preprint arXiv: /901. 10002, 2, 2019.
Petar Veličkovié, William Fedus, William L. Hamilton, Pietro Liö, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pp. 3663-3674, 2021.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. In International Conference on Machine Learning, pp. 12121-12132. PMLR, 2021.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neu- ral networks via subgraph explorations. In International Conference on Machine Learning, pp. 12241-12252. PMLR, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learn- ing Representations, 2020. URL
Wenbin Zhang, Jeremy C Weiss, Shuigeng Zhou, and Toby Walsh. Fairness amidst non-iid graph data: A literature review. arXiv preprint a7Xi0:220..07170, 2022.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intel- ligence, pp. 1015--1023, 2021.
Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. Graph data augmentation for graph machine learning: A survey, arXiv preprint arXiv:2202.08871, 2022.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 1448-11468. PMLR, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pp. 2069 2080, 2021.
Daniel Zwillinger and Stephen Kokoska. CRC standard probability and statistics tables and formu- lae. Crc Press, 1999.
13

---

Published as a conference paper at ICLR 2023
A PROOFS OF THEOREMS
A.1 PROOF OF THEOREM 1
Proof. Let y d(g") [0, 1] denotes the prediction of the classifier d and Y; is the prediction of
node Suppose without loss of generality that E. [Y]] I Ej~s0 Ey Then, we have
(DP(d)= s [Y] Ey~si [Yg] 50 ( 1] + Ey~s [- +1
(11)
We assume the bounded adversarial loss of each sample, i.e., [log(S:) S M for the sample with sensitive attribute $ 1, and log((1 - S:)1 s M for the sample with sensitive attribute S = 0. Based on the concavity of log(-) function and Jensen's 's inequality, for any E [0, 1] with [lg(<)) s M, have
M
log(x) 2 1 1-e (x
(12)
Note that higher prediction indicates lower sensitive attribute value since Ei [Y] S Ej~ Yyl, consider adversary model i that output the opposite of classifier d, i.e., k(g') d(g'). Let S = k("") denote the prediction the adversary model kt Then, we have
1
Ladv
Is, + (1 S,)log(1 -;)]
n
|
|S
E st [lo(())) + En [log(1 - -S)1
n
|St
E st [log(1 - Yi)1 + |So
Bo log(P())
(4)
n'
S [log(1 Y:)l Es [log(Y:)]
nn'
(- M (TT-e-M); V:) + Ensso [ TM
γ, (1--
M
Binsi
e
= n11 - (111--M) c-M) [ -EAs::(1) + R (&, -1]
n'M
n'M
n'M
n11 m(1---M) M) Apr(d) n11 M)
(13)
where inequality (a) holds since n' max(1S) |S')), |), and inequality (b) holds due equation 12 An optimal adversary model k* should do at least better than any arbitrary choice k. thereby we have Ladv"
2 Ladv
2
m(1 m(1-eMr App(d)
n'M
w'M
A.2 PROOF OF THEOREM 2
Proof. According to (Zuu et al. 2020), the contrastive objective -Lcon is lower bound of the true mutual information between H and H', i.e.
Leon S I(H; H').
(14)
According to the data processing inequality, we have I(U; Z I(U: W) for a Markov chain
U V + W. where U, V, W are random variables. The representations H and H' are extracted from the original graph G and the fair view G', thus H, A, A','', H' satisfying relationship (H'). This relation is Markov equivalent to H (A, X) H X) (H)) since H and (A','') are conditionally independent given (A, X). The Markov (A','")
(A', X')
chain leads to the following incquality,
1(H; H1') < I( X; H1) < I(A,;; < / (AA
(9:9").
(15)
Combining Eq. and 15 we have
- -oom < I(()g'),
(16)
which completes our proof.
14

---

Published as a conference paper at ICLR 2023
Pokec_z
Pokec_1
2004
Rurming bme 029
Rurning tie 209
Running time
3003
1103
Graphair
GCA
GRACE
NITYY
Faieug
Graphair
GLA GRACE
NIFTY
FairAug
Graphair
GLA
GRAGE NIFTY
FairAug
Figure 5: The running time comparison.
B TRAINING ALGORITHM FOR GRAPHAIR
We summarize the training algorithm for Graphair and provide the pseudo codes in Algorithm
Algorithm Training algorithm
Require:
adjacency matrix A, feature matrix X, sensitive attribute S
while not converged
Generate fair view G' using the augmentation model
Obtain node representations H G using the representation encoder f Obtain node representations H' of G' using the representation encoder f Compute L by Eq. (9)
Update and by applying stochastic gradient descent to minimize L Update the adversary by applying stochastic gradient ascent to maximize L end while
C BATCH TRAINING FOR LARGE GRAPHS
Because Graphair has a space complexity of (n²) in the full-batch setting, it expensive to train Graphair large graph datasets. To reduce space complexity, adopt the graph sampling-based batch training method proposed by Zeng et al. (220)) to perform mini-batch training. Specifically, construct subgraph via random walk sampler for each batch. Then the subgraph is used as the input of Graphair, and the augmentation model g generates fair view of the subgraph. Both adversarial training and contrastive training are performed on the subgraph. The normalization techniques in (Zeng et al., (2020) are also used to eliminate biases caused by subgraph sampling.
Note that the generated fair view for each batch might subtly different from the one in the full- batch setting, because the augmentation model can only modify edges inside subgraphs in the mini- batch setting. Nevertheless, such a small difference won't 't make big change when the batch size large enough.
D MORE EXPERIMENTAL RESULTS
D. RUNNING TIME COMPARISON
We provide the rumning time comparison in Figure 5 for our Graphair and baselines. We don't t include FairWalk because the implementation we used doesn't use GPU to accelerate the training process. To achieve fair comparison, we train all models for 500 epochs and report the average running time over 5 runs. When performing batch training on Pokec-z and Pokec-n datasets, we use random walk sampler with 1000 root nodes and walk length 3. Note that FairAug proposes fairness-ave aware graph sampling operation, so we use to sample subgraphs with 3000 nodes instead of using random walk sampler. Figure 5 shows that Graphair has higher time complexity than other baselines. This is not surprising because all the baselines rely on fixed augmentation strategies and don't it need learnable neural network model.
15

---

Published as a conference paper at ICLR 2023
NBA
Pokec_2
Pokec
07
1102
0.
Figure 6: Ablation study hyperparameter J.
Pokec_z
Pokec_n
ACC.
Gamma
Gamma
Gamma
Figure 7: Ablation study hyperparameter 7
D.2 HYPERPARAMETEE STUDIES
In this subsection, we conduct hyperparameter studies for further investigation on the contribution of different components in Graphair. First, we tune hyperparameter among {0.1, 0.5, 1, 5, 10). Note that the contrastive loss is unavoidable in training the representation encoder f. case where 3 = 0. Results in Tigure/6showw that change of /3 leads to a trade-off between fairness and prediction performance. Additionally, tune hyperparameter among {0, 0.5, 1, 5, 10). Results in Figure 7 show that Graphair has a better performance (higher accuracy and lower demo- graphic parity) with the reconstruction based regularization term (7 * () than without it 0)- This is because the reconstruction loss can prevent the augmentation model g from generating graphs that deviate too much from the input graph.
don't consider
VISUALIZATION OF DIFFERENT AUGMENTATION METHODS
this section, we provide case study comparing different fairness-aware augmentation methods. In Figure & show the change of 1-hop ego graph in the NBA dataset. Node 1 is the ego node of this ego graph and other nodes are the I-hop neighbors of Node 1. Results in Figure S show that FairDrop drops most edges in the original ego graph due the high sensitive homophily of the ego node. In contrast, Graphair only drops one edge and preserves the original graph topology. Besides, Graphair reduces the sensitive homophily by connecting the ego node node with different sensitive attribute (node 9).
F MORE DETAILS ON EXPERIMENTAL SETTINGS
F.1 DATASETS
We use three real-world social network datasets, including NBA, Pokec-z, and Pokec-n DDai & Wang 2021), evaluate Graphair on node classification tasks. Pokee-z and Pokec-n are sampled from larger social network Pokec. which is the most popular social network in Slovakia. User features contain gender, age, hobbies, interests, education, working field, etc. Among these features, region is treated the sensitive attribute and working field is used as the predicted label. Since the node representations are learned in an unsupervised manner, we use a small portion of labeled data to train the classifier. In other words, randomly split 10% 110% 110%/8% /80% for training, validating and testing the classifier. NBA is extended from Kaggle dataset with more than 400 NBA basketball players. The player information contains nationality, age, salary, performance statistics in the 2016- 2017 season, etc. Nationality is treated as the sensitive attribute and the task is to predict the salary of the player is over median. We randomly split 20% /35% 45%% for training, validating and
16

---

Published as a conference paper at ICLR 2023
Original
FairAug
FairDrop
Graphair
Sensitive Attribute
Edge
Delete Edge
Figure 8: Comparison of different lairnsss-awar augmentation methods on the NBA dataset.
Table 3: The statistics of datasets.
Dataset
NBA
Pokec-z
Pokec-n
# Nodes
403
67,797
66,569
# Node features
39
59
59
# Edges
16,570
882,765
729,129
# Inter-group edges
4,401
39,804
31,515
# group edges
12,169
842,961
697.614
testing the classifier.
The statistics of the datasets are given in Table Note that we use the mini- batch training discussed in Appendix C on Pokec-z and Pokec-n datasets to reduce computation complexity.
F.2 IMPLEMENTATION DETAILS
For Graphair, we adopt two-layer GCN models as the adversary model A: and augmentation encoder gene, and three-layer GCN model as the representation encoder f. We use 64 the hidden di- mension in all three models. For the augmentation model, we use an MLP model with 2 layers, the hidden size of 64, and ReLU the non-linear activation function for MLPA and MLPx- The hyperparameter ,3 is set to 1, and the hyperparameters a; ? and are determined with grid search use three-layer GCN models for all baselines except
among 10.1, 10). For a fair comparison, FairWalk. The dimension of the node representations is selected as 64 for all datasets. We run the experiments 5 times and report the average performance for each method. We train the models for 500 epochs using Adam optimizer with 1 x 10 learning rate and x 10 weight decay. For the results in [able[] we select the optimal hyperparameters with the highest accuracy. For the classifier used for evaluation, we use an MLP model with 2 layers, the hidden size of 128, and ReLU as the non-linear activation function. The classifier trained for 500 epochs using Adam optimizer with 1 x 10-3 learning rate and 1 10-5 weight decay.
G EXPERIMENTS ON A SYNTHETIC GRAPH DATASET
To further validate the scalability of Graphair on larger graphs, we conduct experiments on large synthetic graph dataset with 1,000,000 nodes. The synthetic dataset is generated as follows. We as- sume that the sensitive attribute a binary value and randomly assign 0 or each node with equal probability. For node features, we use Gaussian Mixture Model to generate biased two-dimensional node features. The distributions of node features of different sensitive groups are different. Specif- ically, we use Gaussian distributions M(,,, 2) and N N(22, 2)) generate node features for nodes
with sensitive attributes 0 and 1, respectively, where μ1 = [0. 1]. = [1,0] and Σ = 1
[ 07
0 2
For the adjacency matrix, we randomly generate edges via a stochastic block model. Since nodes with the same sensitive attributes are more likely to be connected in social networks, we generate edges with lower inter-connection and higher intra-connection probability between sensitive groups. Specifically, we set the probability of connecting two nodes with the same and different sensitive attributes as 10 and x 10 10-4, respectively. For label generation, we intentionally make the labels correlated to the sensitive attributes. Specifically, for the label of each node, we set 0 as the threshold value and create a binary label based on the second dimension of the node features. Then add noise to the labels by randomly flipping 20% of the labels to different class. Since the node
17

---

Published as a conference paper at ICLR 2023
Table 4: Comparisons between method and baselines the synthetic dataset in terms of aceu- racy and fairness. The best results are shown in bold.
Synthetic
Models
ACC
App
A E0 +
GRACE
60.41 0.04
47.06 4.20
47.01 4.25
FairDrop
59.05 9.47
29.62 12.88
29.66 + 11.88
NIFTY
56.38 8.92
29.24 12.16
29.16 12.16
FairAug 60.42 0.02
43.40
1.01
43.33
1.00
Graphair
60.36 0.02 15.56 9.01
15.57 8.99
representations are learned an unsupervised manner, we use a small portion of labeled data train the classifier. In other words, we randomly split 10%/10%/80% for training, validating, and testing the classifier. We use the same hyperparameters for modeling training and the same architecture as discussed in Appendix F.2 We run the experiments times and report the average performance for each method. We use the mini-batch training discussed Appendix Con on this large synthetie graph dataset.
Table 4 shows accuracy, demographic parity, and equal opportunity metrics of our proposed Graphair, compared with GRACE, FairDrop, NIFTY, and FairAug. From the results, fairness-aware augmentation methods have lower prediction bias compared to the uniform random augmentation method (i.e., GRACE). In addition, Graphair achieves the best fairness performance in terms of de- mographic parity and equal opportunity on this large synthetic dataset. These results demonstrate the scalability of our Graphair large graph datasets.
18


Reviews:
[{"review_id": "u8cZB721FS", "reviewer": "Reviewer_QdJb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes Graphair, a new framework for learning fair graph representations. Graphair consists of three major components: (1) automated graph augmentation, (2) adversarial training, (3) contrastive training. Experiments are conducted to show that the proposed framework achieves a better fairness-accuracy trade-off compared to the baseline methods.", "summary_of_the_review": "In sum, this paper studies an important problem of learning fair graph representation, and the proposed framework provides a technically sound and solid solution.\nAlthough the novelty of each proposed component is rather limited, the whole framework seems like an incrementing step forward in this research line. Further, experiment results support the superiority of the proposed framework.", "strength_and_weaknesses": "[Strength]\n\n1. This paper studies an important and practical problem.\n\n2. The proposed solution is sound and solid.\n\n3. The proposed method achieves SOTA performance.\n\n4. The overall presentation is good.\n\n\n[Weakness]\n\nI have no significant concerns about the paper. However, I believe the experiment section can be improved.\n\n1. Some details of experiments are missing. E,g., which model is used for the classifier?\n\n\n2. The baselines can be strengthened by including SOTA method for fairness-aware graph learning, i.e., FairGNN [Dai & Wang, 2021].\nAlthough FairGNN directly uses the class label in its training, I believe it can still be compared with the proposed method.\nAlso, I think that investigating the benefits of augmentation in cases where only a small portion of sensitive attributes is available (as done in [Dai & Wang, 2021]) can better support the significance of the proposed method.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qlNclP7wtCf", "reviewer": "Reviewer_fgyY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes Graphair, an automated graph data augmentation method for fair graph representation learning. Graphair is designed to automatically discover fairness-aware augmentations from input graphs in order to circumvent sensitive information while preserving other informative features. Adversarial learning and contrastive learning are adopted to achieve fairness and informativeness simultaneously in the augmented graphs. Empirical results indicate that Graphair outperforms several recent baselines on node classification tasks in terms of fairness-accuracy trade-off performance.", "summary_of_the_review": "The paper proposes a novel graph augmentation method for fair representation learning which outperforms the state-of-the-art methods on the fairness-accuracy trade-off performance. Although there are limitations on the complexity, the method is generally effective and novel in the field of fair graph representation. The presentation of materials is generally clear and the statements and theorems have been justified. ", "strength_and_weaknesses": "Strengths:\n1. The method proposed in the paper does not require some strong assumptions or definitions about the properties that fair graph data should have, while most existing methods rely on these assumptions which may vary significantly in different scenarios.\n\n2. According to the experiments, the method achieves accuracy comparable to the state-of-the-art methods on node classification tasks on three datasets while significantly improves the fairness, and outperforms several baselines on the fairness-accuracy trade-off performance.\n\nWeaknesses:\n1. There are only limited results on how the method affects the graph topology. Apart from the case study presented in the appendix, more experimental results are expected on the comparison of changes in graph structure after the augmentations.\n\n2. (This limitation has been addressed in the appendix. It would be better to also mention this in the main part.) Because Graphair has a space complexity of O(n^2) in the full-batch setting, it is expensive to train Graphair on large graph datasets, mini-batch is required to reduce space complexity.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "oEd2ij00h8Z", "reviewer": "Reviewer_oCtR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies fair graph representation learning via graph augmentation. Different from other literatures, this work proposed an automated augmentation methodology. Some theories on fairness and informativeness are provided, followed by experiments and ablation studies.", "summary_of_the_review": "A well written paper with enough novelty. The fact that the augmentation method is not via some pre-determined rule is the interesting part. ", "strength_and_weaknesses": "I like this paper. Overall I see a well written paper with thorough theories/experiments provided. The fact that the augmentation method is not via some pre-determined rule is nice. The adoption of adversarial training for fairness property is also interesting (but for this part I'm not sure if similar things have appeared in other literatures or not). \n\nThe proofs of the two theorems are somewhat standard to me. This is not bad because I didn't see the claim on theoretical innovations. For experiments, the datasets used are relatively small. Maybe additional results on larger synthetic data will also be interesting together with discussions on the scalability of the proposed method.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-E3iZkDgH8", "reviewer": "Reviewer_fjjw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposed an automated data augmentation method for fair graph representation learning. This seems to be the first automated graph data augmentation method that focuses on learning fair representations on graph data. The authors designed the Graphair framework with four components: edge augmentation, feature augmentation, adversarial training, and contrastive training. From the experimental results, the proposed method seems able to significantly improve the fairness while not sacrificing too much on accuracy.", "summary_of_the_review": "Based on my opinions above, I recommend boarderline accept.", "strength_and_weaknesses": "s1. This paper is overall clearly written and easy to follow.\n\ns2. Learning fair representations is a very important topic in graph machine learning. And from this paper, data augmentation seems to be a good methodology for it.\n\ns3. From the experimental results (table 1 and figure 2), the proposed method is able to significantly improve on fairness without sacrificing too much on accuracy.\n\nw1. The empirical results are not convincing enough. If no public datasets are available, maybe the authors can consider evaluate on some larger scale synthetic datasets. This would also help showing the scalability of the proposed method, especially considering the current datasets are pretty small with 60k nodes max. \n\nw2. From Figure 5, the proposed method seem to be very low even on not-so-large datasets.\n\nw3. I suggest the authors to use vector graphics for all figures in the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%