Fair Node Representation Learning via Adaptive Data Augmentation
Authors: Oyku Deniz Kose
Yanning Shen
Venue: ICLR 2022 Submitted (2022)
Keywords: Fair node representations
fairness-aware graph data augmentations
unsupervised node representation learning
graph contrastive learning

Abstract: Node representation learning has demonstrated its efficacy for various applications on graphs, which leads to increasing attention towards the area. However, fairness is a largely under-explored territory within the field, which may lead to biased results towards underrepresented groups in ensuing tasks. To this end, this work theoretically explains the sources of bias in node representations obtained via Graph Neural Networks (GNNs). Our analysis reveals that both nodal features and graph structure lead to bias in the obtained representations. Building upon the analysis, fairness-aware data augmentation frameworks on nodal features and graph structure are developed to reduce the intrinsic bias. Our analysis and proposed schemes can be readily employed to enhance the fairness of various GNN-based learning mechanisms. Extensive experiments on node classification and link prediction are carried out over real networks in the context of graph contrastive learning. Comparison with multiple benchmarks demonstrates that the proposed augmentation strategies can improve fairness in terms of statistical parity and equal opportunity, while providing comparable utility to state-of-the-art contrastive methods. 

Under review as a conference paper at ICLR 2022
FAIR NODE REPRESENTATION LEARNING VIA ADAPTIVE DATA AUGMENTATION
Anonymous authors Paper under double-blind review
ABSTRACT
Node representation learning has demonstrated its efficacy for various applica- tions on graphs, which leads to increasing attention towards the area. However, fairness is a largely under-explored territory within the field, which may lead to biased results towards underrepresented groups in ensuing tasks. To this end, this work theoretically explains the sources of bias in node representations obtained via Graph Neural Networks (GNNs). Our analysis reveals that both nodal fea- tures and graph structure lead to bias in the obtained representations. Building upon the analysis, fairesss-aware data augmentation frameworks on nodal fea- tures and graph structure are developed to reduce the intrinsic bias. Our analysis and proposed schemes can readily employed to enhance the fairness of various GNN-based learning mechanisms. Extensive experiments on node classification and link prediction are carried out over real networks the context of graph con- trastive learning- Comparison with multiple benchmarks demonstrates that the proposed augmentation strategies can improve faimess in terms of statistical par- ity and equal opportunity, while providing comparable utility to sfaeeoff-the-ar contrastive methods.
INTRODUCTION
Graphs are widely used in modeling and analyzing complex systems such as biological networks or financial markets, which leads to rise in attention towards various machine learning (MI.) tasks over graphs. Specifically, node representation learning is a field with growing popularity. Node representations are mappings from nodes to vector embeddings containing both structural and at- tributive information. Their applicability on ensuing tasks has enabled various applications such as traffic forecasting (Opolka et al., 2019). and crime forecasting (Jin et al., 2020). Graph neural net- works (GNNs) have been prevalently used for representation learning, where node embeddings are created by repeatedly aggregating information from neighbors for both supervised and unsupervised learning tasks (Kipf & Welling 2017; Veličković et al. 2018 García-Durán & Niepert 2017).
It has been shown that MI models propagate pre-existing bias in training data, which may lead to discriminative results for ensuing applications (Dwork et al., 2012) [Beutel et al.] 2017). Particular ML over graphs, while GNN-based methods achieve state-of-the-art results for graph represen- tation learning, they also amplify already existing biases in training data (Dai & Wang 2020). For example, nodes in social networks tend to connect other nodes with similar attributes, leading to denser connectivity between nodes with same sensitive attributes (e.g., gender) (Hofstra et al., 2017.. Thus, by aggregating information from the neighbors, the representations obtained by GNNs may be highly correlated with the sensitive attributes. This causes discrimination in ensuing tasks even when the sensitive attributes are not directly used training (Hajian Domingo- 2013).
Data augmentation has been widely utilized to improve generalizabilityy in trained models, well as enable learning in unsupervised methods such as contrastive or self-supervised learning, Aug- mentation schemes have been extensively studied in vision (Shorten & Khoshgoftaar 2019 Hjelm et al., 2018) and natural language processing (Zhang et al. 2013; Kafle et al. 2017). ). However, there comparatively limited work in the graph domain due to the complex, non non-Euelidean struc- ture of graphs. To the best of our knowledge. (Agarwal et al. 202T) is the only study that designs fairness-aware graph data augmentation in the contrastive learning framework to reduce bias.

---

Under review as a conference paper at ICLR 2022
This study theoretically investigates the sources of bias in GNN-based learning and in turn improves fairness in node representations by employing fairness-awars graph data augmentation schemes. Proposed schemes corrupt both input graph topology and nodal features adaptively, in order to duce the corresponding terms in the analysis that lead to bias. Although the proposed schemes are presented over their applications using contrastive learning, the introduced augmentation strategies can be flexibly utilized in several GNN-based learning approaches together with other fairness- enhancement methods. Our contributions in this paper can be summarized as follows:
cl) We theoretically analyze the sources of bias that is propagated towards node representations in a GNN-based learning framework.
c2) Based on the analysis, we develop novel fairnes--aware graph data augmentations that can re- duce potential bias in learning node representations. Our approach adaptive to both input graph and sensitive attributes, and to the best of our knowledge, is the first study that tackles fairness en- hancement through adaptive graph augmentation design.
c3) The proposed strategies incur low additional computation complexity compared to non-adaptive counterparts, and are compatible to operate in conjunction with various GNN-based learning frame- works, including other fairness enhancement methods.
c4) Theoretical analysis is provided to corroborate the effectiveness of the proposed feature masking and node sampling augmentation schemes.
c5) Performance of the proposed graph data augmentation schemes is evaluated on real networks for both node classification and link prediction tasks. It is shown that compared to state-of-the-ar graph contrastive learning methods, the novel augmentation schemes improve fairness metrics while providing comparable utility measures.
2 RELATED WORK
Representation learning on graphs. Conventional graph representation learning approaches can be summarized under two categories: factorization-basse and random walk-based approaches. Factorization- methods aim to minimize the difference between the inner product of node representations and a deterministic similarity metric between them (Ahmed et al., 2013 Cao al.) 2015 Ou et al. 2016). Random walk-based approaches, on the other hand, employ stochastic mea- sures of similarity between nodes (Perozzi al. 20144 Grover& & Leskoved 2016 Tang al. 2015
Chen et al., 2018). GNNs have gained copularity in representation learning, for both supervised (Kipf & Welling 2017: VVličković al. 2018: Hu et al. [2019] Wu et al., 2019). and unsupervised
tasks, e.g., (Garcia-Durán & Niepert 2017; Hamilton et a 2017). Specifically, recent success of contrastive learning on visual representation learning (Wu et al. 2018 Ye et al. 2019 Ji et al. 2019) has paved the way for contrastive learning for unsupervised graph representation learning.
Graph data augmentation. Augmentation strategies have been extensively investigated in vision (Shorten& & Khoshgoftaar 2019 Hjelm et al.) 20188) and natural language processing (Zhang et al.) 2015| Kafle et al.] 2017) domains. However, the area is comparatively under-explored in the graph domain due to the complex, non non-Euclidean topology of graphs. Graph augmentation based on graph structure modification has been developed to improve the utility of ensuing tasks (Rong et al. 2019 Zhao et al. 2020 Chen et al., 2020a). Meanwhile, graph data augmentation has been used gen-
erate graph views for unsupervised graph contrastive learning, see, e.g.. (Veličković et al. 2019
Opolka et al. 2019: Zhu et al. 22200 2021). which achieves sate-of-the-an results various learn- ing tasks over graphs such as node classification, regression, and link prediction (Opolka et al. 2019
Veličković et al. 2019; You et al. 2020 Zhu al. 2020 Peng al. 2020 Hassani & Khasahmadi
2020). Among which, (Zhu et al. 2020) is the first study that aims to maximize the agreement of node-level embeddings across two corrupted graph views. Building upon (Zhu et al.) 2020). (Zhu
et al. 2021) develops adaptive augmentation schemes with respect to various node centrality mea- sures and achieves better results. However, none of these studies are fairness-aware.
Fairness-aware learning on graphs. A pioneering study tackling the fairness problem in graph representation learning based on random walks is developed in RRahman et al. 2019). In addi- tion, adversarial regularization is employed to account for faimess of node representations (Dai &
Wang 2020 Bose & Hamilton 2019 Fisher et al.] 2020) where (Dai & Wang 2020) is presented specifically for node classification, and (Fisher al. (020)) works on knowledge graphs. (Buyl &
De Bie 2020) also aims to create fair node representations by utilizing a Bayesian approach where
sensitive information is modeled in the prior distribution. Contrary to these aforementioned works,
2

---

Under review as a conference paper at ICLR 2022
framework is built on a theoretical analysis (developed within this paper). Similar to the works mentioned above, the proposed methods can be utilized within the learning process to mitigate bias by modifying the learned model (i.e., in processsgn faimess strategy). In addition, the proposed schemes can also be regarded as "pre-processing" tools, implying their compatibility to a wide array of GNN-based learning schemes in versatile manner. Furthermore, (Ma al.
202T) carries out PAC-Bayesian analysis and connects the concept of subgroup generalization to accuracy disparity, and (Zeng et al. 202I introduces several methods including GNN- ones decrease the bias for the representations of heterogeneous information networks. While (Li et al. 2021 Laclau et al., 2021 modify udjacency to improve different fairness measures specifically for link prediction, [Buyl & De Bie 2021 designs regularizer for the same purpose. With specific interest on individual fairness over graphs, (Dong et al. 202T) employs a ranking-based strategy. A biased edge dropout scheme is proposed in (Spinelli et al. 2 to improve fairness. However, the scheme therein is not adaptive to the graph structure (the parameters of the framework are independent of the input graph topology). Fairness-awe awwre graph contrastive learning is first studied in (Agarwal et al. 202T), where a layer-wise weight normalization scheme along with graph augmentations is introduced. However, the farmesss-wwar augmentation utilized therein is designed primarily for counterfactual fairness.
3 FAIRNESS IN GNN-BASED REPRESENTATION LEARNING
GNN-based approaches are the ofate-of-the-art for node representation learning. However, it has been demonstrated that the utilization of graph structure in the learning process not just propagates but also amplifies a possible bias towards certain sensitive groups (Dai & Wang 2020). To this end, this section investigates the sources of bias in the generated representations via GNN-based learning. It carries out an analysis revealing that both nodal features and graph structure lead to bias, for which several graph data augmentation frameworks are introduced.
3.1 PRELIMINARIES
This study aims to learn fairness- aware nodal representations for a given graph G := (V. E) where V := {UI, u1.-.. 3 denotes the node set, and & C V x V represents the edge set. X RNF and A E 1J. 1J are used to denote the feature and adjacency matrices, respectively, with the (i, entry dij = if and only if eij == (vi, E E. Degree matrix D E NxN is defined to be diagonal matrix with the nth diagonal entry d, denoting the degree of Un. For the fairness examination, sensitive attributes of the nodes are represented with s E {0, 1] NX1, where the existence of single, binary sensitive attribute is considered. In this work, unsupervised methods are chosen as enabling schemes for the representation generation where given the imputs A, X, and the main purpose is to learn mapping / RNNN x NxF x RR - N x that generates FL. dimensional (generally FL < F) unbiased nodal representations H f(A, X,s) E N through an L-layer GNN, which can be used in an ensuing task such as node classification. x; E B.,, by E F and 8, E 1} denote the feature vector, representation at layer 1 and the sensitive attribute of node Us. Furthermore, Sp and S, denote the set of nodes whose sensitive attributes are 0 and 1, respectively. Define inter-edge set EX {eig |u; E Uy Sp, a + 6). while intra-edge set is defined as 0- := -eiyl b; E Sa. Dy E Sy, a = b} Similarly, the set of nodes having at least one inter edge is denoted by Sx, while S" defines the set of nodes that have no inter-edges. The intersection of the sets So, Sx is denoted as Sy. Additionally, d. and di' denote the numbers of inter-edges and intra-edges adjacent to Us respectively. Finally, denotes the entry-wise absolute value for scalar or vector inputs, while it is used for the cardinality when the input is a set.
3.2 ANALYSIS FOR BIAS IN GNN REPRESENTATIONS
This subsection presents an analysis to find out the sources of bias in node representations generated by GNNs. Analysis is developed for the mean aggregation scheme in which aggregated representa- tions at layer 1, z E N are generated such that 2 = ,, Σrjev()) h for i (1,.... N). where z! is the ith row of Z' corresponding to node u, de denotes the degree of node v;, (i() refers to the neighbor set of node v; (including itself). The recursive relation in GNN layer in which left normalization is applied for feature smoothing is H = oD '(A + I H' -1 HW') where W' is the weight matrix in layer 1, and I E RNNN denotes identity matrix. With these definitions, the
3

---

Under review as a conference paper at ICLR 2022
relation between the aggregated information Z' and node representations H' becomes equivalent to H' = ('' at the ith GNN layer. As the provided analysis is applicable to every layer, I superscript is dropped in the following to keep the notation simple.
has been demonstrated that features that are correlated with the sensitive attribute result in bias even when the sensitive attribute is not utilized in the learning process (Hajian & Domingo-Ferrer 2013). This work provides an analysis on the correlation of s with Z, and aims to reduce it. Note that, the reduction of correlation can still allow the generation of discriminable representations for different class labels, if the discriminability is provided by non-sensitive attributes. The (sample) correlation between the sensitive attributes s and aggregated representations can be written as
Σn (3 Ex Ex)) - N Ex=1 8k) N
P: = (o
VE (2ji - E 2nd )2 -
+ 8x)²
where i i=
.......ii. i' the ith column of Z. In the analysis, following assumptions are made: A1: Node representations have sample means o40 and μu respectively across each group, where
= 1....
44 = (hy By E St). Throughout the paper, mcan(-) denotes the sample mean operation.
A2: Node representations have finite maximal deviations Ag and A That is, |[h, 1oll.o A..
du, E S; with i E {0, 13.
Based on these assumptions, the following theorem shows that || can be bounded from above, which will serve as a guideline to design a faimess-aware graph data augmentation scheme.
Theorem 1.
The total correlation between the sensitive attributes s and representations that are obtained after mean aggregation over graph G, ||ell1, can be bounded above by
|llll S ||c||| (1ló)) max(n1 (2) + 2N
(1)
where q == y |S
with de == V N E (On (O,
3/2 N 0,),, YO E R.N. 5 4o
No
p1,
m
1
S
S
S1
72 2 min (mean( de +d
d%
Imm E So), mean dx dd
Un E
E.))].
A = max Ao. AI).
The proof is given in Appendix A.
The upper bound in equation I can be lowered by i) utilizing feature masking which has an effect on the term ||400 milli at the first layer, ii) node sampling that can change the value of 71, iii) edge augmentations that can reduce the value of 72-
3.3 FAIR GRAPH DATA AUGMENTATIONS
Data augmentation has been studied extensively in order to enable certain unsupervised learning schemes such as contrastive learning, self-supervised learning or as a general framework to improve the generalizability of the trained models over unseen data. However, the design of graph data augmentations is still a developing research area due to the challenges introduced by complex, non- Euclidean graph structure. Several augmentation schemes over the graph structure are proposed in order to enhance the generalizability of GNNs (Rong et al.) 2019 Zhao et al., 2020). while both topological (e.g.. edge/node deletion) and attributive (e.g.. feature shufiling/masking corruption schemes have been developed in the context of contrastive learning (Veličković al. 2019 You jet al., 2020) Zhu et al.) [202T] 2020). However, none of these works are fairness-aware. Hence, in this work, novel data augmentation schemes that are adaptive to the sensitive attributes, as well as the input graph structure are introduced with Theorem I as guidelines.
3.3.1 FEATURE MASKING
In this subsection, an augmentation framework on nodal features H X is presented in order to mitigate possible intrinsic bias propagated by them. Note that ||0|] in equation I is minimized when all nodal features are the same (i.c., all nodal features masked/zeroed out). However, this would result in the loss of all information in nodal features. Motivated by this, the proposed scheme aims to improve uniform feature masking in terms of reducing ||ō]| for a given masking budger (a total amount of nodal features to be masked in expectation). Specifically, the random feature masking scheme used in (You et al. 2020; Zhu et al., (020) where each feature has the same masking probability is modified assign higher masking probabilities the features varying more across
4

---

Under review as a conference paper at ICLR 2022
different sensitive groups. Thus, masking probabilities are generated based the term [8]. Let 8 := min((6) max mi]( denote the normalized [6], the feature masking probability can then be designed as
(mm) min
(2)
> F
02
where a is a hyperparameter. The feature mask m E 13 is then generated as a random binary vector, with the i-th entry of drawn independently from Bernoulli distribution with pt (1 (m)) for i = =..... F. The augmented feature matrix is obtained via
X [m x m m
(3)
where [: is the concatenation operator, and is the Hadamard product. Since the proposed feature masking scheme is probabilistic in nature, the resulting 8 is random vector with entry ö; having
[6%.] 10,
with probability p.:
with probability P-p:
(m) is the probability that the 7th feature is not masked in the graph view. The
where p: := 1 P; following proposition shows that the novel, adaptive feature masking approach can decrease || compared to random feature masking, the proof of which can be found in Appendix
Proposition 1. In expectation, the proposed adaptive feature masking scheme results in a lower [|ôl] value compared to uniform feature masking, meaning
1p S Eall)ö111]
(5)
where q corresponds uniform masking with masking probability 1 qr. and qi Ej=ı
3.3.2 NODE SAMPLING
In this subsection, adaptive node sampling framework is introduced to decrease the term ?1 in equation of Theorem and hence to reduce the intrinsic bias that the graph topology can create. A small 7/ suggests a more balanced population distribution with respect to |Sx] and (S*]. Specifically, a subset of nodes selected at every epoch and the training is carried over the subgraph induced by the sampled nodes. This augmentation mainly aims reducing the bias by selecting a subset of more balanced groups, meanwhile also helps reduee the computational and memory complexity in training.
(1- S ( |1 -
S
+ 1ST
The proposed node sampling is adaptive to the input graph, that is, depends on the cardinalities of the sets S SN Sy and Sp. The developed scheme copes with the case |Sx] < |8 In algorithm design, is assumed that if |S*| < SS then S s |S and |S < |ST] (same for S*), which holds for all real graphs in our experiments, but our design principles different settings as well.
be readily extended to
Given input graph G, the augmented graph 9 can be obtained as an induced subgraph from a subset of nodes V. All nodes in S are retained, (Š) = S and S = S²), while subsets nodes Sp and Sr are randomly sampled from Sy and Si with sample sizes |S |S and |S |S respectively. See also Algorithm iin Appendix A.3 The cardinalities of node sets in the resulting graph augmentation 9 satisfy 71 = O. (See Appendix A.3 for details.)
Remark 1. Note that the resulting graph 9 yields m = 0 as long as S = 1/2 & and
| = 1/2 Φ is satisfied for any -1/2 < o < 1/2. The presented scheme here simply sets 0, which results in a balanced ratio across groups, but the performance can be improved if selected carefully for specific datasets.
3.3.3 AUGMENTATION ON GRAPH CONNECTIVITY
Minimizing 1/2 to zero in Theorem suggests a graph topology where all nodes in the network have the same number of neighbors from each sensitive group, i.e., dy = dx, Ves E V. Since, for this
5

---

Under review as a conference paper at ICLR 2022
scenario, 122 = |1- 2 min (mean
0. Note that this finding is parallel to the main design idea of Fairwalk (Rahman et al. 2019 in which the transition probabilities are equalized for different sensitive groups in random walks in order to reduce bias in random walk-based representations.
+d Oe E &So). mean du
4%
dx
Un E S1))
This finding suggests that an ideal augmented graph 9 could be generated by deleting edges from or adding edges to G such that each node has exactly the same number of neighbors from each sensitive group. However, such a per-node sampling scheme is computationally complex and may not be ideal for large-scale graphs. To this end, propose global probabilistic edge augmentation schemes such that in the augmented graph,
[ [[ = B|
Here the expectation is taken with respect to the randomness in the augmentation design. is shown in our experiments that the global approach can indeed help to reduce the value of 72 (see Appendix A.8 Note that even though the strategy is presented for the case where | S | (which holds for all datasets considered herein), the scheme can be easily generalized the case where |EX] |84).
In social networks, users connect to other users that are similar to themselves with higher proba- bilities (Mislove al. 2010), hence the graph connectivity naturally inherits bias towards potential minority groups. Mouivated by the reduction of 72, the present subsection introduces augmentation schemes over edges to provide balanced graph structure that can mitigate such bias.
Adaptive Edge Deletion. To obtain a balanced graph structure, we first develop adaptive edge deletion scheme where edges are removed with certain deletion probabilities. Based on the graph structure and sensitive attributes, the probabilities are assigned as
if s + 8j
(e(g)
2 nT,
if s; 8,
if 8, =1
2
where p(t)(e))) is the removal probability of the edge connecting nodes u, and Uj. π is hyper- parameter, and ES, denotes the set of intra-edges connecting the nodes in St. Note that ı is chosen be in this work, but it can be selected by schemes such as grid search to improve performance. While this graph-level edge deletion scheme does not not directly minimize Y2, it provides bal- Ep ||Ex|] henceforth equation
anced global structure such that Ept [1 l| = E Ep [1Es, s
holds in the augmented graph G, see Appendix A.4 for more details.
Adaptive Edge Addition. For graphs that are very sparse, edge deletion may not be an ideal graph augmentation as may lead to unstable results. In this case, an adaptive edge addition framework is developed to obtain more balanced graph structure. Specifically, for graphs where | S |E*] holds, |8-| - | pairs of the nodes are sampled uniformly from S and S with replacement. Then, edge is created to connect each sampled pair of nodes, in order to obtain an augmented graph & for which equation 6 holds. Note that experimental results in Section also show that edge addition may become better alternative over edge deletion for graphs that are sparse in inter-edges.
Remark 2. Overall, while subset of these augmentation schemes can be employed based on the input graph properties (sparse/dense, large/small), all schemes can also be employed on the input graph sequentially. The framework where node sampling, edge deletion, edge addition are employed sequentially together with feature masking is called 'FairAug'. is worth emphasizing that edge augmentation schemes should always follow node sampling, as performing node sampling changes the distribution of edges. Since the cardinalities of different sets will be calculated only once (in pre-pro prepprocessing)... we note that the proposed augmentations will not incur significant additional cost.
EXPERIMENTS
In this section, experiments are carried out on real-world datasets for node classification and link prediction tasks. Performances of our proposed adaptive augmentations are compared with baseline schemes in terms of utility and faimess metrics.

---

Under review as a conference paper at ICLR 2022
4.1 DATASETS AND SETTINGS
Datasets.
Experiments are conducted real-world social and citation networks consisting of Pokec-7, Pokec-n (Dai & Wang, 2020), UCSD34, Berkeley13 13 (Red et al. 2011), Cora, Citeseer, Pubmed. Pokec-z and Pokec-n sampled from larger social network, Pokec TTkaa & Zabovsky 2012), are used in node classification experiments where Pokec is a Facebook-like, social network used Slovakia. While the original network includes millions of users, Pokec-z and Pokec-n are generated by collecting the information of users from two major regions (Dai & Wang 2020). The region information is treated as the sensitive attribute, while the working field of the users is the label to be predicted in classification. Both attributes are binarized, see also (Di & Wang (020). UCSD34 and Berkeley13 are Facebook networks where edges are created based on the friendship information in social media. Each user (node) has 7 dimensional nodal features including stu- dent/faculty status, gender, major, etc. Gender is utilized as the sensitive attribute in UCSD34 and Berkeley 13. Cora, Citeseer, and Pubmed are citation networks that consider articles as nodes and deseriptions of articles as their nodal attributes. In these datasets, the category of the articles is used as the sensitive attribute. Statistics for datasets are presented in Tables Maales/aanddii and Appendix A.55
Evaluation Metrics, Performance of the node classification task is evaluated in terms of accuracy. Two quantitative group fairness metrics are used to assess the effectiveness of fairness aware strate- gies in terms of statistical parity: Asp = Plù = y 1,8 = 0) Púj = 0) Ply = = 1) and equal 1,8 1)}, where y and ÿ denote the ground-truth and the predicted labels, respectively. Lower values for AsP and AgO imply better fairness performance (Dai & Wang 2020). For the link prediction task, both accu- racy and Area Under the Curve (AUC) are employed as utility metrics. As the faimess metrics, the definitions of statistical parity and equal opportunity are modified for link prediction such that - Asp = Pp = 1 E e P(j = 1 E Ed] and A = IP 1 y = 1, E 1 e, E E.)]. where e denotes the edges and ý is the decision for whether the edge exists.
opportunity: AgO = [P
Implementation details. The proposed augmentation scheme is tested on social networks with node representations generated through an unsupervised contrastive learning framework. Node classifica- tion and link prediction are employed ensuing tasks that evaluate the performances of generated node representations. In addition, we also provide link prediction results obtained via an end-to-end graph convolutional network (GCN) model on citation networks. Further details on the implemen- tation of the experiments are provided in Appendix [A.7] Contrastive learning is utilized to demon- strate the effects of the proposed augmentation schemes, as augmentations are inherently utilized in its original design YYou et al. 2020). Specifically, GRACE (Zhu et al. 2020) is employed as our baseline framework. GRACE constructs two different graph views using random, non-adaptive aug- mentation schemes, which we replaced by augmentations obtained via FairAug in the experiments. For more details on the employed contrastive learning framework, see Appendix AA.6
Baselines. We present the performances on total of 7 baseline studies. As we examine our pro- posed augmentations in the context of contrastive learning, graph contrastive learning schemes are employed as the natural baselines. Said schemes are Deep Graph Infomax (DGI) (Veličković et al., 2019, Deep Graph Contrastive Representation Learning (GRACE) (Zhu et al. 2020), Graph Con- trastive Learning with Adaptive Augmentations (GCA) (Zhu et al. (021), and Fair and Stable Graph Representation Learning (NIFTY) (Agarwal et al., 2021). We note that the objective function of NIFTY (Agarwal et al. 2021) consists of both supervised and unsupervised components, and its results for the unsupervised setting are provided here given the scope of this paper. In addition, as another family of unsupervised approaches, random walk-based methods for unsupervised node rep- resentation generation are also considered. Such schemes include DeepWalk (Perozzi el al. 2014). Vece2Vec (Grover& & Leskovec 2016), and FairWalk (Rahman et al. 2019). Lastly, for end-to-end link prediction, we present results for the random edge dropout scheme (Rong et al. 2019).
4.2 EXPERIMENTAL RESULTS
The comparison between baselines and our proposed framework FairAug is presented in Table D
Note that FFiirAug wo ED' in Table [ refers to FairAug where edge deletion (ED) is removed from the chain, but all node sampling (NS), edge addition (EA), and feature masking (FM) are still employed. Firstly, the results of Table [ show that FairAug provides roughly 45% reduction in faimess metrics over GRACE, the strategy it is built upon, while providing similar accuracy
7

---

Under review as a conference paper at ICLR 2022
Table 1: Comparative Results with Baselines Node Classification
Pokce-z
Pokoo-n
Accuracy (%)
Age (%)
ArO (%)
Accuracy (%)
Agp (%)
A Ax)(
DeopWalk
60,82 + 0.77
9.79 = 3.43
8.51 + 1.67
59.66 + 1.02
20.19 + 3.38
22 22.96-
+ 3.44
Node2Vee
61.56
16.18 12.40
14.88 12.31
60.31
20.76
1.64
20.32
1.36
FairWalk
57.48 1 0.11
12.03 1 10.19
10.95 =: 8.82
57.44 1 0.73
15.00
1.40
15.72 1 1.80
DGI
65.56 + 1.29
4.82 1.89
5.81 0.97
65.71 0.24
5.18 + 2.15
7.16
2.444
GRACE
67.09 1: 0.47
6.20 2:22
6.18 1. 2.46
67.90
1: 0.13
8.85 1: 1.39
10:13
2.11
GCA
66.85 0.71
7.40 4.14
7.46 4.09
67.02 0.43
5.31 + 0.62
7.75 +: 1.49
NIFTY
66.09 = 0.40
5.86 + 1.97
6.19 + 1.72
66.44 0.17
5.18 # 2.80
5.78 3.18
FairAng
67.04 :: 0.69
3.29 1.66
3.04 + 1.37
67.88 0.45
4.81 + 0.59
6.52 0.99
FairAug wo
67.38 0.31
2.66 + 3.22
4.26 2.92
07.57 0.18
3.37 = 0.62
5.13 + 1.12
Table 2: Ablation Study on Node Classification
Pokeo-z
Pokec-n
Accuracy (%)
Agp (%)
A BO (%)
Accuracy (%)
Agp (%)
A Ago (%)
GRACE
67.09 = 0.47
6.20 +: 2.22
6.18 = 2.46
67.90 + 0.13
8.85 + 1.39
10.13 + 2.11
FairAug
67.04 1 0.69
3.29
1: 1.66
3.04
1 1.37
67.88 1: 0.45
4.81
i 0.59
6.52 1 0.99
FairAng wo
66.88 + 0.42
4.64
+: 1.91
5.50
1.80
66. + 0.75
7.61
9.28 + 1.06
FaizAug wo NS
67.01 1 0.41
6.05
1: 2.63
6.83
2.88
66.33
1 0.20
6.26
1: 0.26
9.16 1 0.63
Fair/ug wo ED
67.38 1 0.31
2.66
4: 3:22
4.26
2.92
67.57
1 0.18
3.37
+: 0.62
5.13
: 1.12
FairAug EA
66.96
= 1.08
2.86
+ 1.79
3.22
1.29
67.96
0.19
7.13 0.29
9.40 + 0.81
values. Second, note that similar to our framework, GCA is built upon GRACE through adaptive augmentations as well. However, the adaptive augmentations utilized in GCA are not fairness-awe aware, and the results of Table I demonstrate that the effect of such augmentations is unpredictable. Third, the results indicate that all contrastive learning methods provide better fairness performance than random walk-baser methods
the fairness metrics
evaluated datasets, including Fairwalk, which is a fairness-aware study. Since the sole information source of random walk-based studies is the graph structure, obtained results confirm that the graph topology indeed propagates bias, which is consistent with the motivation of our graph data augmentation design. Finally, the results of Table T demonstrate that the closest competitor scheme to FairAug is NIFTY (Agarwal et al., (02T) in terms of fairness measures. For Agr, FairAug outperforms NIFTY on both datasets, whereas in terms of A EO. FairAug and NIFTY outperform each other on Pokec-z and Pokec-n, respectively. Table 1 shows that the EDDrremoved version of FairAug, "FairAug wo ED', outperforms NIFTY on Pokee-n as well, suggesting that at least one of the proposed strategies outperform all considered benchmark schemes in both Asp and Ago. This fairness performance improvement achieved by ED removal motivated us to conduct an ablation study on the building blocks of FairAug, which we present in the sequel.
Table lists the results of an ablation study for FairAug, where the last four rows demonstrate the effects of the removal of FM, NS, ED, and EA, respectively. Pokec-z and Pokec-n are highly unbalanced datasets (E-1 x 20(EX)) with a considerable sparsity in inter-edges (see Table of (ope).ix(A.S).. For such networks, the exact probabilities presented in equation for edge deletion as it would result in the deletion of a significantly large portion of the edges, damaging the graph structure. We employ an upper limit on the deletion probabilities to avoid this (see Appendix A.7). However, with such a limit, the proposed ED framework alone cannot sufficiently balance 8- and | At this point, we note that since |S-| > |S*], node sampling also provides way of decreasing | by excluding nodes from the set S when generating the
be utilized
subgraph. As the graph was already sparse initially inter-edges (i.e., small (EX)), employing both NS and ED causes similar over-deletion of intra-edges and creates unstable results due to the significantly distorted graph structure. Overall, combining this phenomenon with the results of Table in order to balance the input graphs Pokec networks consistently (which have |E4| >> | and inter-edge sparsity), node sampling is observed to be a better choice than edge manipulations.
Table presents the obtained results for link prediction in the framework of contrastive learning. Results demonstrate that 'FairAug wo NS' consistently improves the fairness metrics of the frame- work it is built upon (GRACE), together with similar utility measures. In addition, comparing GCA
8

---

Under review as a conference paper at ICLR 2022
Table 3: Link prediction results obtained node representations
UCSD34
Berkeke113
(U)
Age (%6
A no (%)
AUC(%%
Agp (%)
A (R)
GCA
71.59 + 0.29
0.70 + 0.27
1.92 = 0.45
69.69 0.38
0.50 + 0.36
6.52 + 0,99
GRACE
71.57
0.49 0.28
1.48 0.70
69.35
0.76 4: 0.44
4.34 1.20
FairAug
71:46
0.30
0.71 + 0.38
1.62 = 0.62
09.48 0.29
0.70 + 0.43
4.21 0.90
FairAug NS
71.50 + 0.31
0.41 + 0.32
1.16 + 0.65
69.65 0.33
0.68 4 0.34
4.22 + 0.97
Table Employment of fair edge deletion as an edge dropout method
Accuracy (%)
AUC (%)
Agr (%)
ARo (%)
Cora
Edge Dropout
82.79 + 0.83
90.52 + 0.52
57.22 = 2.19
+ 4.53 27.79
36 18
Fair
1.14
87.95 1.22
2.58
3.89
Citeseer
Edge Dropout Fair FD
78.30 1: 1.17
87.93 1: 1.05
43.05
2.39
25.45 1 3.69
77.26 +: 1,80
86.79 1.39
39.90
3.57
25.02 + 6.93
Pubmed
Edge Dropout Fair ED
88.63 = 0.34
95.14
0.16
45.59
0.78
15.81 + 0.92
87.48 + 0.51
94.15 0.36
40.90 = 1.10
11.70 + 0.68
and GRACE, obtained results confirm our previous assessment regarding the unpredictable effect of GCA's augmentations on the fairness metrics. Finally, comparing FairAug with and without NS, the results of Table show that in UCSD34 and Berkeley13, the employment of node sampling can be ineffective in improving fairness metrics, or even have |Sx] >> | (see Table Appendix A.5). Therefore, for NS on these datasets, half of the nodes are sampled randomly from the sets S and S (as the limit on the minimum node sampling budget is half of the initial group size to avoid a possible over-sampling, see Appendix A.7). Since [Sx] >> |S*1, such a sampling framework coincides with random sampling, which makes the ef- fects of the proposed node sampling scheme unpredictable on the fairness metrics. Furthermore, while ?1 suggests that the cardinality of the set [Sx] should be reduced when |S S | 7 ac- tually appears in the upper bound and not in the exact || expression. The removal of nodes with inter-edges actually counter-intuitive, as inter-edges generally help to reduce bias in graphs where |841 2 | (which holds for all datasets considered herein). Therefore, the proposed node sam- pling becomes effective for graph structures providing [S-] 2 |SX]. The effect node sampling on Facebook networks is further investigated through "/1 and 7/2 in Appendix [A.8] which corroborates the explanations on the random//ettimmntal effect node sampling for these datasets.
them. In UCSD34 and Berkeley 13,
As also noted in Section 1 even though FairAug is presented through its application on graph strastive learning in this section, the proposed approach can be fully or partially used in conjunction to other learning frameworks end-to-end link prediction task with a two-layer GCN where the proposed fair edge deletion scheme is employed as an edge dropout method. As the benchmark, random edge dropout (Rong et al. 2019) is considered, which is a scheme originally proposed to improve the generalizability of the model on unseen data (Rong et al.) (201)). In the experiments, the number of deleted edges is the same for both strategies. The results demonstrate that our method "Fair ED' can indeed enhance the fairness of the learning framework employed in while it slightly reduces the utility measures.
well. To exemplify such
case, Table 4 lists the results for an
CONCLUSIONS
In this study, the source of bias in aggregated representations GNN-based framework has been theoretically analyzed. Based on the analysis, several fairness-aware augmentation schemes have been introduced on both graph structure and nodal features. The proposed augmentations can be flexibly utilized together with several GNN-based learning methods. In addition, they can readily be employed in unsupervised node representation learning schemes such as graph contrastive learning. Experimental results on real-worid graphs demonstrate that the proposed adaptive augmentations can improve faimess metrics with comparable utilities to of-e--o-thheann in node classification and link prediction.

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
The proofs for Theorem and Proposition are presented together with all assumptions made for them in Appendix A. and Appendix A.2 respectively. Implementation details and hyperparameter values are presented in Appendix A.7 for the clarification of experimental settings. All codes that are needed to regenerate the presented results in Tables [ 2 and are provided within the sup- plementary material together with a README file. Finally, the details the utilized data sets are provided in Appendix A.55 where all datasets are publicly available.
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju*, and Marinka Zitnik*. Towards unified framework for fair and stable graph representation learning, arXiv preprint arXiv:2102.33188 February 2021.
Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander J Smola. Distributed large-scale natural graph factorization. In Proc. International Conference on World Wide Web (WWW). pp. 37-48, May 2013.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint vrXiv:/707.0000 June 2017.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference Machine Learning (ICML, pp. 715-724. PMLR, 2019.
Maarten Buyl and Tijl De Bie. Debayes: a bayesian method for debiasing network embeddings. In International Conference Machine Learning (ICML., pp. 1220-1229. PMLR, 2020.
Maarten Buyl and Tijl De Bie. The kl-divergence between a graph model and its fair i-projection as fairness regularizer. arXiv preprint arXiv:2103.01186, 2021.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proc. ACM International Conference on Information and Knowledge Management (CIKM), pp. 891-900, October 2015.
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 Artificial Intelligence, volume 34, pp. 3438-3445, 2020a.
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. Harp: Hierarchical representation learning for networks. In Proc. AAAI Conference on Artificial Intelligence, volume 32, February 2018.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proc. International Conference Machine Learning (ICML), pp. 1597-1607, July 2020b.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. arXiv preprint urXiv:2009.0145: 01454, September 2020.
Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairness for graph neural networks: A ranking based approach. In Proc ACM Conference Knowledge Discovery & Data Mining (SIGKDD), pp. 300-310,10 2021.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proc. Innovations in Theoretical Computer Science (ITCS), pp. 214-226, January 2012.
Joseph Fisher, Arpit Mittal, Dave Palfrey, and Christos Christodoulopoulos. Debiasing knowledge graph embeddings. In Proc. Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7332-7345, 2020.
10

---

Under review as a conference paper at ICLR 2022
Alberto Carcía-Duráae and Mathias Niepert. Learning graph representations with embedding propa- gation. In Proc. International Conference on Neural Information Processing Systems (NeurIPS), pp. 5125-5136, December 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proc. International Conference Artificial Intelligence and Statistics (AISTATS), pp. 249-2566 May 2010.
Ignacio S Gomez, Bruno da Costa, and Maike AF Dos Santos. Majorization and dynamics of continuous distributions. Entropy, 21(6):590, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proc. ACM International Conference Knowledge Discovery and Data Mining (SIGKDD), August 2016.
Sara Hajian and Josep Domingo-Ferrer A methodology for direct and indirect discrimination pre- vention data mining. IEEE Transactions on Knowledge and Data Engineering, 24(7):1445- 1459, July 2013. doi: 10.1 (0.1109/KKDE.2012....
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proc. International Conference on Neural Information Processing Systems (NeurIPS), pp. 1025-1035, December 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In Proc. International Conference on Machine Learning (ICML), pp. 4116-4126, July 2020.
Devon Hjelm, Alex Fedorov, Samuel Marchildn,, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In Proc. International Conference on Learning Representations (ICLR), April 2018.
Bas Hofstra, Rense Corten, Frank Van Tubergen, and Nicole B Ellison. Sources of segregation in social networks: A novel approach using facebook. American Sociological Review, 82(3): 625-656, May 2017.
Fenyu Hu, Yanqiao Zhu, Shu Wu, Liang Wang, and Tieniu Tan. Hierarchical graph convolutional networks for semi-supervised node classification. In Proc. International Joint Conference on Artificial Intelligence, (IJCAT), August 2019.
Xu Ji, João F Henriques, and Andrea Vedaldi. Invariant information clustering for unsupervised image classification and segmentation. In Proc. IEEE International Conference on Computer Vision (ICCV), pp. 9865-9874, October 2019.
Guangyin Jin, Qi Wang, Cunchao Zhu, Yanghe Feng, Jincai Huang, and Jiangping Zhou. Ad- dressing crime situation forecasting task with temporal graph convolutional neural network ap- proach. In Proc. International Conference on Measuring Technology and Mechatronics Automa- tion (ICMTMA), pp. 474-478, February 2020. doi: 10.1009/CMMM55054.0000 2000000000..000000000.
Kushal Kafle, Mohammed Yousefhussien, and Christopher Kanan. Data augmentation for visual question answering. Proceedings of the 10th International Conference on Natural Language Generation, pp. 198-202, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412..941.69 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proc. International Conference on Learning Representations (ICLR), April 2017.
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 Statisties, pp. 1774-1782. PMLR, 2021.

---

Under review as a conference paper at ICLR 2022
Peizhao Li, Yifei Wang. Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Explor- ing and mitigating bias in graph connections. In Proc. International Conference on Learning Representations (ICLR), April 2021.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. arXiv preprint urXiv:2106. 15535, 2021.
Albert W Marshall, Ingram Olkin, and Barry C Armol. Inequalities: theory of majorization and its applications, volume 143. Springer, 1979.
Alan Mislove, Bimal Viswanath, Krishna P Gummadi, and Peter Druschel. You are who you know: inferring user profiles in online social networks. In Proc. ACM International Conference on Web Search and Data Mining (WSDM), pp. 251-260) February 2010.
Felix L Opolka, Aaron Solomon, Cătălina Cangea, Petar Veličkovic, Pietro Liò, and R Devon Hj elm. Spatio-temporal deep graph infomax. arXiv preprint arXiv: 06116, April 2019.
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity pre- serving graph embedding. In Proc. ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 1105-1114, August 2016.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proc. Web Conference (WWW), pp. 250-270, April 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social rep- resentations. In Proc. ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 701-710, August 2014. URL http:://dd:: http::/doo.aac...omm acm. att..///0.oo//1.115555555
2623330. 2623732
Tahleen A Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: graph embedding. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), pp- 3289-3295, August 2019.
Towards fair
Veronica Red, Eric D Kelsic, Peter Mucha, and Mason A Porter. Comparing community structure to characteristics in online collegiate social networks. SIAM review, 53(3): 543,, 2011.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903 2019.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6(1):1-48, 2019.
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Biased edge dropout for enhancing faimess in graph representation learning. arXiv preprint arXiv:2 142/0, 2021.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International Sci- entific Conference and International Workshop. 'Present Day Trends of Innovations', volume 1, May 2012.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proc. International Conference on World Wide Web (WWW), pp. 1067-1077, May 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. Proc. International Conference on Learning Representations (ICLR), April 2018
Petar Veličkovié, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In Proc. International Conference on Learning Representations (ICLR), May 2019. httpst/:: wwwpeeeeweeeeeeeeeeeeeeeeee..e.m net forr//ormmmta weerrkl22iiicc
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proc. International Conference on Machine Learning (ICML), pp. 6861-6871, July 2019.
12

---

Under review as a conference paper at ICLR 2022
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4733-3742, June 2018.
Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via invariant and spreading instance feature. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6210-6219, June 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Proc. International Conference Neural Information Processing Systems (NeurIPS), 33, December 2020.
Ziqian Zeng, Rashidul Islam, Kamrun Naher Keya, James Foulds, Yangqiu Song, and Shimei Pan. Fair representation learning for heterogeneous information networks. arXiv preprint arXiv:2104.08769, 2021.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. Advances neural information processing systems, 28:649 657, 2015.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. arXiv preprint arXiv:2006.06833) 06830, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Con- trastive Representation Learning. In Proc. International Conference on Machine Learning (ICML) Workshop Graph Representation Learning and Beyond, July 2020. URL http:
7/axxiv. 2ttp:///abb//000103333
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. Proc. Web Conference (WWW), April 2021.
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF OF THEOREM 1
Let N Ei= 8;
N |S1l Hence, the elements of centered sensitive attribute vector can be written
as
Pi No.
E (0 (2m 2,)
Σ (1 - 10_,)(2nn - -E:)),
(8)
Un Un
where 2,
N ش 8 becomes
Eji and 2zi is the element matrix Z at row j. column
Using 8 values, the
equation
SSil
So
Pi
Nog
N
(Zm,t
24)
+
Σ
N
(Zn
2;)),
Um ESo
E,
1
Soll|Sl
Σ
|1
|
S
Sol
+
2m,
2
zn,i);
No.02...
N
N
N
N
Mm ESo
2 ES
(9)
Sol
Sil
No
N
Zn
Σ
N
Zm,zis
Un
Um ESo
|S
Σ
1
Zn,
2m,3
N2
S1
|o
ES
Mm ESo
Similarly analysis for a follows
S
S
0x
8)2
N
N2
N2
ESo
S
N2
N2
(10)
((So)
|S|l)
[So||S||
N
([Sol + [S
V|SaISS
N
Define C = V/So/|S.1 No
and c F denote the vector whose elements are c,s. Then p equals to
p c-
2
Zm
(11)
S
S
Uy,
E1
Umn ESo
where o represents the Hadamard product. Therefore,
||ell follows as
|| = co
Zn
Zm
(12)
S
So
Uim E
We first consider the terms
Exnes,
Zn and
Σ
Um ESp Zm individually
[
[Sg
1
no dn Σ 11) +A,
Zn
[
S1
dn
S
U, E,
(EN(m)
bEN(m)
dxp + di
E
S
d%
d"
+
(13)
dx
(mo m11 +A.
S
dx + du
14

---

Under review as a conference paper at ICLR 2022
Similarly, the expression for the term
Lvm ES,
2m can also be derived.
[Sa]
1
d
Zmm
E
M4 +
(mn
Ho)
+ A.
(14)
So
Spl
dm
di
Um
ESu
ESa
Define 6 =
[5 Σ
ESt
on
So
E
ESo
Zmn the following can be written by equation 13 and
equation
14
c E (M1 mo)
1
+ 22A
(15)
S1
d% +
di
Sol
dm
+
di
Ni, E.
ESo
is bounded below, which follows
1
dx
Σ
m
S
d
So
dm
di
U/ ES.
ES0
1
dx
dx
(16)
[S]
di +
dx
|So
dx
+
dia
Vr, EST
Vea ESO
|
S
(17)
S
S
equation follows as d2 = 0 for Vu E Sw. The upper bound equation 17 holdds since for Yu, G.
S
The upper bound for follows as
dx
(18)
S1
d + du
SS
dx +
d
Up ES:
Um ESu
dx
dx
1 mcan
Immm
So
mcaa
In Es
(19)
dx.
+
du
dx + d
d2
dx
5.)))
< 1 - 2 min
mcan
So
meaan
Up
S1
d,
du
dx + dy
(20)
where mean(-) denotes the sample mean operation. The main purpose is to generate upper bound for ||p]], for which the first step is to derive the following bound
|| S ||c||///c||a
(21)
equation 21 can be written, ||x o y/ ||x|| |yy|| || for arbitrary vectors and y R (wyy + +.. NNNN| S ([ral + +... ...
- ....... [yw I) due to additional non-negative cross-terms [ [gg i * ÿ). The next step is bound the é1 norm of the difference term e:
||]|]] < ||
1 maxl (71, 72) + 2N
(22)
using the derived bounds in equation 17 equation 20 and the equality 2A
||1||
| | and 72 =
2N4 A, where 1 denotes an N x vector of ones, 71 =
[S
[Sil
- 2 min mean
d +-d Iim E So mean 2h
dx
Un E ES.))
Using equation 21 and equa-
tion 22 the final upper bound can be derived:
||p|| < ||c|] (1)
Moll mllm)m))()))))) 22NA
(23)
15

---

Under review as a conference paper at ICLR 2022
A.2 PROOF OF PROPOSITION |
The expected ||o]| can be written as:
F
Ep|||8111]
10:l
(24)
F Σ
prloal-
==1
Similarly, the expected |00[| for the uniform masking scheme is
Eq Egll Σ a:16%l.
(25)
For fair comparison, set uniform keeping probability of the nodal features qi - - + Without loss of generality, assume, jóys are ordered such that [61| S I 55|. With the ordered |6: is. assigned probabilities to keep the nodal features by our method will also be ordered such that Pi 2 ... 2 pr. Defining dummy variable 16p1 == equation 24 can be rewritten as:
pol6,1 (1611 - (Po + pF) + (162) 1611)(p2 + +FF) +
...4 (18F-11 - 100--))(p=-11- PF) + (10pl - 10==11)(PF)
(26)
(1511 181-1)) Pr-
Following the definition in (Marshall et al. 1979), sequence
{I1, 22. .F
majorizes
another sequence y {811 92..... VF J. if the following holds:
1/ 5
k
1
F F-1.
1=1
(27)
Σ
94 Z4-
Since the uniform sequence is majorized by any other non-increasing ordered sequence with the
same (see (Gomez al. 2019, Equation 3)), the sequence p (p1,72,'. "",""","" ,Ppr majorizes
... the sequence q {91 ... }F} where qi P. Vi fl.....F), Defining Σ Pt 0, equation 26 can be re- re-written as
F Σ
Epll
[1]
(186 - 101-1)) Σ
ps
1m1
2m/
F
(1011 - 10:11))(F
pi)
1=1
(a)
(28)
Σ (16:1 18
9i)
F
F - (6)-1))
(106
Σ
Fg (11))
'From equation 25 can obtained that Fg [| Σ.
1. ||0]]]] the probabil-
itics ge E [0, 1]. Here, ||]|| corresponds to the distribution difference with no feature masking (g. = 1, Vi). This implies that feature masking upper bounds 5 [1], which is obtained via stochastic feature masking.
16

---

Under review as a conference paper at ICLR 2022
where inequality (a) follows from the definition of majorization in equation 27
A.3
NODE SAMPLING AND ITS EFFECTS
Algorithm 1: Node Sampling
Data: 9 = (V, X B
Result: G,
Split into sets (S ST S0,
if |S 2 | then
Sample | nodes from So uniformly to obtain S
Sample | nodes from Si uniformly to obtain Sy
V = {SXx S6 S
end
[rSs 2 | then
Sample [Sg] nodes from S uniformly obtain S
Sample [S nodes from S uniformly obtain S
= (5 SK ):):
end
Obtain subgraph & induced by V along with the nodal features X and sensitive attributes š
The overall node sampling scheme is presented in Algorithm
Assuming |S-| > | all nodes in Sx are retained, meaning S S and Š = S While subsets of nodes Sy and Sy are randomly sampled from Sø and Sj respectively with sample size |S S and [S |.
Therefore, in the resulting graph G, we have
| = 1 |
(29)
SS = ST
= S
(30)
therefore
8x
S
(31)
[S +
|
S + |
SX
ISM
(32)
|8X
SS11
S +
which leads to 711 = 0 for the obtained g.
A.4 EFFECTS OF GLOBAL EDGE DELETION SCHEME IN EQUATION 7
Given the edge deletion scheme equation 7
we have
E
px()
[
=
XXI
(33)
[xX]
T x|Xx
E
(m)
|10%]
(34)
2 E
||0%]
[
E
p(e)
X
(35)
2 |
Therefore, Ep(o)
[8 = E (e))
[
[[xx]
and equation holds.
17

---

Under review as a conference paper at ICLR 2022
A.5
DATASET STATISTICS
Dataset statistics are provided in Tables 5 and 6
Table 5:
Dataset statistics for social networks
Dataset
|
|5%
|
[S;]
|8*1
16%
[eg,
Pokec-z
1730
Pokec-n
423
3617
479
1666
1422
18548
10672
UCSD34
2246
71
51607
36787
19989
Berkeley13
1619
80
14188
77
27542
19550
13582
Table 6: Dataset statistics for citation networks
Dataset
[V]
sensitive altr.
|EX|
|E"|
Cora
2708
1428
5964
Citeseer
3327
1628
4746
Puhmed
19717
12254
49802
A.6 CONTRASTIVE LEARNING OVER GRAPHS
The main goal of contrastive learning to learn discriminable representations by contrasting the em- beddings of positive and negative examples, through minimizing a specific contrastive loss (Opolka itt al. 2019 Veličković et al. 2019 Zhu et al. 2021 2020). The contrastive loss in the present work designed to maximize node-level agreement, meaning that the representations of the same node generated from different graph views can be discriminated from the embeddings of other nodes. Let H = -( X1) and H = [(A² X²) denote the nodal embeddings generated with graph views T and G2, where A', and X are the adjacency and feature matrices of Go, which are corrupted versions the matrices A and X. Let ha and h² denote the embeddings for uy: They should be more similar to each other than to the embeddings of all other nodes. Hence, the representations of all other nodes are used as negative samples. The contrastive loss for generating embeddings h/ and hy (considering hy as the anchor representation) can be written
(bt.b2))
é (h), h2) log
(36)
e (b) EN 1 bE)/ E (e (b/.
where 8 (h] h?) = e (g(h)) (ontt.gg(()))) (h?)), with .).,.) denoting the cosine similarity between the in- put vectors, and g(-) representing nonlinear learnable transform executed by utilizing 2-layer multi-layer perceptron (MLP), see also, (Zhu et al. 2021 2020 Chen et al.) (020b).. 7 denotes the temperature parameter, and I [R=z]] E (0. T) is the indicator function which takes the value when k + i. This objective can also be written in the symmetric form, when the generated representation h is considered as the anchor example. Therefore, considering nodes in the given graph, the final loss can be expressed
N Σ h()
(37)
2N
A.7 HYPERPARAMETERS AND IMPLEMENTATION DETAILS
Contrastive Learning: All experimental settings are kept unaltered as presented in our baseline study GRACE (Zhu et al. 2020 for fair comparison, where in the GNN-based encoder, weights are initialized utilizing Glorot initialization (Glorot & Bengio 2010) and ReLU activation is used after each GCN layer. All models are trained for 400 epochs by employing Adam optimizer (Kingma &
Ba 2014) together with a learning rate of 5 x 10 and lg weight decay factor of 10 The tempera- ture parameter in contrastive loss is chosen to be 0.4 and the dimension of the node representations selected as 256 for all datasets.
18

---

Under review as a conference paper at ICLR 2022
End-to-end training: All models are trained for 100 epochs by employing Adam optimizer (Kingma & Ba 2014) together with learning rate of x 10 10-3. The dimension of the node repre- sentations is selected as 128 for all datasets.
Implementation details: Node representations are obtained using a two-layer GCN (Kipl & Welling, 2017) for all contrastive learning baselines, which is kept the same as the one used in (Zhu et al. 2021] 2020) to ensure fair comparison. After obtaining node embeddings from differ- schemes, a linear classifier based on @z-regularized logistic regression applied for the node classification and link prediction tasks, which is again the same as the scheme used in (Veličkovid al. 2019; Zhu al., 2021] 2020). In node classification, the classifier is trained on 90% of the nodes selected through random split, and the remaining nodes constitute the test set. For each experiment, results for three random data splits are obtained, and the average together with standard deviations are presented. In link prediction, 90% of the edges are utilized in the training of GCN encoder and linear classifier. For each edge, the input to the linear classifier is the concatenated representations of the nodes that the edge connects. Results for link prediction are obtained for five different edge splits, the resulting average metries and standard deviations are provided. Finally, in the end-to-end link prediction experiments, two-layer GCN is trained, and results are obtained for 6 different random data splits.
Note that if the sizes of the sets é and á are highly unbalanced, we put a limit on the minimum of sampling budgets in node sampling to prevent any excessive corruption of the input graph. If Sx 2 S", the minimum limit for each set is the 50% of the initial group size, otherwise the limit is the 25% of the initial group size. Furthermore, avoid overly down sampling the edges, minimum value for pl)) (eig). P Pminn is set for the edge deletion scheme. In the feature masking scheme, a in equation is set to Ó and 0.1 for different graph views used in the contrastive loss (i.e., default parameter values provided for GCA are used directly). In the edge deletion framework, ग 1, and p 3 0.5 are used in the experiments of both Pokec datasets and citation networks. Such a selection is utilized to present the scheme with the most "natural" hyperparameter value, in the sense that only intra-edges note that this selection is naturally a good choice for unbalanced data sets in terms of inter- and intra-edges. For Facebook networks where intra- and inter-edges are balanced for certain sensitive groups, x = 0.8, and Prii is set as for all experiments.
deleted, where the already sparse inter-edges are left unchanged. We
Proposed augmentation frameworks have only two hyperparameters: a in feature masking and n in adaptive edge deletion. While we note the value of a is kept the same for all baselines that utilize a feature masking scheme (default hyperparameters provided by GCA (Zhu et al.. (02Th) ). and 1 is the most natural choice for x in Pokec datasets and citation networks, we carry out a sensitivity analysis for these two hyperparameters in this appendix. In the analysis. for a, the values [0.1, 0.2, 0.3] are examined for the first graph view, where the a value for the second view is assigned to be higher than the value of the first one by 0.1. Overall, sensitivity analyses for Pokec and Facebook networks
on the FairAug algorithm are presented in Tables 7 and g respectively. In Tables and 8 the first column shows the a values of the first and second view, respectively.
The sensitivity analysis for a on Pokec networks in Table f demonstrates that increased a values can both improve or degrade the fairness performance together with similar classification accuracies. However, the resulted fairness performances are observed to be consistently better than our baseline, GRACE. Furthermore, the results of Table TubleBshoor show that fairness performances for the link prediction task can generally be improved with increased values, and the performance is quite stable over different a selections.
Table 7: Sensitivity analysis for a on Pokec networks for FairAug.
Pokco-z
Pokce-n
Accuracy (%)
Agp (%)
Ago (%)
Accuracy (%)
Age (%)
ANo (%)
0.0/0.1
67.01 4 0.69
3.29 + 1.66
3.01 + L.37
67.88 + 0.45
4.81 = 0.59
6.52 + 0.99
0.1/0.2
67.90
3.95
+: 2.09
4.20
2.41
67.60
0.48
4.38 0.45
1.44
0.2/0.3
67.68
0.71
1.42
+ 1.48
1.16
+ 2.25
68.01
= 0.36
4.95
0.39
6.44
+ 1.36
0.3/0.4
67.71 0.64
2.99 + 1.89
3,20
+ 2.57
67.50 = 0.11
3.38
= 0.90
4.41
1.12
19

---

Under review as a conference paper at ICLR 2022
Table 8: Sensitivity analysis for Facebook networks for FairAug
UCSD34
Berkeley13
AUC
Agp (%6
Aeo (%)
AUC (%)
Age (%)
Aeo (%)
0.0/0.1
71,46 0.30
0.71 + 0.38
1.62
+ 0.62
69.18 = 0.29
0.70 = 0.43
1.24 = 0.90
0.1/0.2
71.54 0.33
0.65
1.76
0.38
0.55
0.22
0.2/0.3
71.51 1. 0.30
0.58
1 0.26
1.50
1 0.66
69.57
1 0.46
0.55 a 0.35
4.15 1. 0.79
0.3/0.4
71.35
0.41
0.49 + 0.14
1.65
+ 0.50
69.41
0.35
0.97 = 0.19
4.47 1.10
The sensitivity analysis for [0.75, 0.80, 0.85, 0.90, 0.95, 1.00] for FairAug algorithm for both views. The sensitivity anal- yses for Pokec and Facebook networks on FairAug algorithm are presented in Tables g and [T] respectively. In Tables g and T0 = 1 is the parameter choice utilized to generate the results in
is carried
by examining the values
Table 2 and π 0.8 the selection for the results in Table
Table 9: Sensitivity analysis for π on Pokec networks for FairAug.
Pokec-z
Pokec-n
Accuracy (%)
Asp (%)
Ago (%)
Accuracy (%)
Asp (%)
Ago (%)
1.00
67.04 + 0.69
3.29
1.66
3.04
1.37
67.88 + 0.45
4.81 + 0.59
6.52
0.99
0.95
67.60 = 0.57
1.00 = 1.76
1.37
1.82
68.01 + 0.53
5.66 + 1.27
7.00 0.72
0.90
0.85
66.96
= 0.77
3.49 2.28
3.52
15
08.00 + 0.29
5.66
0.22
7.77
+ 1.01
0.80
67.87 + 0.35
3.59 2.33
1.30
1.95
68.17
+ 0.28
5.61 0.73
7.82
1.24
0.75
67.74 0.28
3.94 2.48
4.58
1.91
67.95
1 0.10
5.69 4 0.27
7.44
1.08
Table 10: Sensitivity analysis for æ on Facebook networks for FairAug
UCSD34
Berkeley13
(%)
Agp (%)
ABo (%)
AUC (%)
Agr (%)
Ano(%)
0.80
71.46 = 0.30
0.71
0.38
1.02
0.62
09.48 + 0.29
0.70
0.43
4.24
1.00
71.30 + 0.41
0.56 = 0.47
1.41
0.37
69.70 + 0.32
0.74
0.74
4.35 1.11
4.35
0.95
71.37
1 0.41
0.60
0.30
1.48
0.69
69.52 1 0.42
0.66
0.16
3.99
0.884
0.90
71.40
+ 0.38
0.59
0.34
1.45
0.44
69.48
1: 0.31
0.86 0.77
4.64 1.37
4.64
0.85
71.39
0.36
0.05
0.28
1.38
0.54
0.41
0.70 0.400
0.88
0.75
71.47
1: 0.23
0.63
0.37
1.55
0.65
69.52
0.443
0.74
0.448
4.31 1 1.19
The sensitivity analysis for æ on Pokec networks shows that π = 1 results in the best performances in terms of fairness. However, we note that the fairness results for the remaining values also outperform our baseline, GRACE, together with similar node classification accuracies. Furthermore, the results of Table I0 demonstrate that the presented results for link prediction in Table B can indeed be improved with a grid search, as better faimess performances can be obtained with π / 0.8. Moreover, the results for different values vary less for link prediction compared to node classification.
A.8 EFFECTS OF PROPOSED AUGMENTATIONS ON 71 AND 72
Table 11: Effects of proposed augmentations on 2/2
Original
Node Sampling
Edge Deletion
Edge Addition
Pokoc-z
0.90
0.59
0.87
0.77
Pokee-n
0.91
0.62
0.89
0.81
UCSD34
0.18
0.45
0.03
0.11
Berkeley13
0.18
0.43
0.03
0.06
Tables 11 and 12 present the effects of the proposed framework y values for different datasets. In Table I the effect each augmentation step on ?/2 is considered independently. Table 12 demon- strates the effect of augmentations sequentially in the overall algorithm in cumulative manner (c.g.. the "Edge Deletion" " column implies both Node Sampling and Edge Deletion are applied). Both Tables 11 and 12 demonstrate that though the edge deletion/addiiton schemes are not
20

---

Under review as a conference paper at ICLR 2022
Table 12: Effects of each step in FairAug
Original Graph
Node Sampling
Edge Deletion
Edge Addition
Pokec-7
0.66
0.11
0.11
0.11
72
0.90
0.59
0.50
0.43
Pokeo-n
71
0.91
0.62
0.55
0.50
UCSD34
0.91
0.86
0.86
0.86
0.18
0.45
0.17
0.17
Barkeley
0.90
0.83
0.83
0.83
72
0.43
0.17
directly designed based on 72, the proposed approaches indeed reduce the values it. In addition, presented values also help explain the ineffectiveness of edge deletion Pokec networks. Due to the inter-edge sparsity and overly unbalanced structure these datasets in terms of | and |8"1 (presented in Table 5 of Appendix A..5), node sampling becomes better choice than edge deletion/addition to reduce the bias via an augmentation on the graph topology. Table [1 also shows the better effectiveness of node sampling strategy in reducing 7/2 compared edge dele- tion/addition frameworks, which also supports the findings of Table 2 that is, node sampling is an essential step of FairAug on the Pokec networks. Furthermore, 7 values can also help explain the random/detrimental effect of node sampling for Facebook networks, which is presented in Table 3 TT and s2wwow that while node sampling is not very effective in reducing "/, it is observed to increase 7/2 for these networks. This effect results from the graph topologies of Facebook networks having |S >> |S Note that 7I values are not after node sampling due to the limit on the minimum of sampling budgets, Appendix A.7
A.9 CASE STUDIES FOR THE EFFECTS OF PROPOSED AUGMENTATIONS
To demonstrate the effects of the proposed augmentation schemes in a more intuitive manner on different graph structures, consider two small toy examples. The topology in Figure Ta is inspired by the topology of the Pokec networks (few inter-edges, many more intra-edges, i..., whereas Figure Tb is motivated by the Facebook networks (few nodes with inter-edges, many more that have at least one, i.e., [SX| > |S*)). For demonstrative purposes, assume the nodes in both graphs share the same nodal features, with the corresponding feature matrix X equal to
[ D.
0.0
0.1
-0.3
0.1
-0.1
0.2
0.2
-0.2
0.1
0.1
0.1
0.2
0.0
0.2
0.0
0.2
0.1
-0.2
0.1
0.2
X
0.1
-0.1
-0.1
0.1
-0.2
-0.1
-0.1
0.3
-0.2
0.3
0.2
0.1
0.4
-0.1
-0.1
0.3
0.1
0.1
0.3
-02
Feature masking: For the given X. 8 utilized in adaptive feature masking equals to [0.74, 0.12, 1.00, 0.74, 0.00]. Therefore, feature masking scheme where 40% of the features are masked, the most probable augmented X become
0.0
0.2
0.0
0.0
-0.17
0.0
0.1
0.0
0.1
-0.1
0.0
-0.2
0.0
0.1
0.1
0.0
0.2
0.0
0.2
0.0
X
0.0
0.1
0.0
0.1
0.2
0.0
-0.1
0.0
0.1
-0.2
0.0
-0.1
0.0
-0.2
0.3
0.0
0.1
0.0
-0.1
-0.1
0.0
0.1
0.0
0.3
-.2
Note that the feature masking process is stochastic. We present the mask with the largest probability of occurrence, for demonstrative purposes.
21

---

Under review as a conference paper at ICLR 2022
11
22
s=
intra-edges inter-edges
s=0
intra-edges inter-edges
5=1
s=1
(a) Casc onc.
(b) Case two.
Figure I: Toy examples
(a) Case one after NS.
(b) Case two after NS.
Figure 2: Augmented graphs via node sampling
For X. (M) - (4) in equation 15 becomes [0, -0.00. 0, 00.32, 0] where was 10.32,-0.000 0.43, -0.32, 0) for the original graph. Note that this is the best case scenario given the 40% masking budget, with the maximal decrease in || #oll1. As also mentioned in Footnote - the actual feature masking process is stochastic. By assigning larger masking probabilities to the features with high deviations betweeen Sp and SJ, the non-uniform masking strategy proposed herein increases the chances of obtaining the "better" cases with larger reductions in (11 Ma).
Node sampling:
The results in Table demonstrate that node sampling becomes effective in graphs |Sx|. Here, visualize this finding through the toy examples presented in Figures Note that the two toy graphs differ in their sets Sw and Sx Specifically, we have for Figure La and |S 8x for Figure lb
where S
Ta and
1b
181
En..ss 2m/11 values are calculated before and after node sampling for two different graph examples G₁ and Gz. Note that z, d; Ev,EN() Xy, and the original nodal features X are utilized to calculate the Z, vectors.
Here, the exact ||=|]] TTs Σn,es, Zn 180
and SS 2. Therefore, the proposed node sampling scheme selects 2 nodes from the set St: and node from the set St A possible augmented graph is presented in Figure 2a which the examination is carried over. While the original ||<|/2 equals to 0.865 for G,, ||<|| becomes 0.771 for the output topology of the node sampling provided in Figure 2a which shows the efficacy of the proposed framework.
Case 1: In the first example graph G,, | 2, |Sh 3. |S
Case 2: For Gg, | 4, S = 1, S = 2, and SS = Therefore. the proposed node sampling scheme selects nodes from the set St (minimum limit for each set is the 50% of the
22

---

Under review as a conference paper at ICLR 2022
(a) Case one.
(b) Case two.
Figure 3: Augmented graphs via edge deletion
initial group size), and node from the set S Therefore, the presented example in Figure 2b is potential augmented topology obtained after the proposed node sampling framework. For this case, the original ||e|la 0.558 which becomes 0.892 for the augmented graph presented in Figure 2b This case study clearly illustrates that the proposed node sampling scheme mainly effective for graphs where |8*] [8x].
Edge deletion:
Results Table 2 show that node sampling better choice than edge manipu-
lations for graphs with inter-edge sparsity and |8"1 >> [EX]. Again, two studies based on the graphs provided in Figure D are utilized to demonstrate the effects of the proposed adaptive edge
deletion scheme. Specifically, the resulted ||||| प.. Σx,es Zn [oo] Σ Ee,,, ES 2m || value is
examined before and after the application of edge deletion.
Case 1: In the first example graph G1, | 2, 15% 6, and EE 3. Therefore, edge deletion probability of the adaptive edge deletion framework 0.5 for the edges in Eg,, and Eg with the
hyperparameter selections π 1, and (c) graph is presented in Figure for demonstrative purposes. While the value of |e||] is reduced from 0.865 to 0.792 with the application of adaptive edge deletion, the graph in Figure also becomes disconnected. For certain real networks, such the Pokec networks considered in this paper, the imbalance between intra- and inter-edges is considerably larger than the imbalance the graph in Figure Therefore, the sparsity resulting from the adaptive edge deletion be even more severe for such graphs than this toy example. Thus, this case study also confirms that node sampling can indeed be better choice than edge deletion for graphs with inter-edge sparsity and | >>>>>>>>>>>>>>>>> |EX].
0.5. For such scheme, possible augmented
Case 2: For G2, we have |gX] = 4, Eg 4, and |S = 2, which shows more balanced structure than the graph utilized in Case 1. For the given graph connectivity, edge deletion probability of adaptive edge deletion scheme is 0.5 for the edges in E and 0 for the edges in ES, together with
the hyperparameter selections т 1, and P = 0.5. The presented example Figure 3b potential resulting augmented topology obtained with the proposed edge deletion framework, presented for demonstrative purposes. For this outcome, the original ||e|| is decreased from 0.558 to 0.497 for the augmented graph presented in Figure 3b which demonstrates the effectiveness of the proposed augmentation for the input graph in Case
Edge Addition: We also present the effects of the proposed edge addition scheme the toy amples for a better illustration of the augmentation. Again, the exact ||=|]] = | Ex, ES Zn
Sol Evnes, Zm ll values are calculated before and after edge addition for two different graph ex- amples G, and Gg.
Case 1: For G1, as |8-1 and |gX] = 2, seven artificial inter-edges generated for the proposed edge addition scheme. For such a scheme, a possible augmented graph is presented in Figure 4a where ||||| is reduced from 0.865 to 0.111 with the application of edge addition.
Case 2: For G2. as | = and |gx] = 4. therefore two artificial inter-edges should be created for the proposed edge addition scheme. A possible augmented graph resulting from the proposed edge
23

---

Under review as a conference paper at ICLR 2022
(a) Case one.
(b) Case two.
Figure 4: Augmented graphs via edge addition
addition is presented in Figure 4b For the presented example Figure edge addition can lower the value of <|la from 0.558 to 0.293.
A.10 OPTIMAL TOPOLOGY AUGMENTATION SCHIEMES FOR 71 AND 722
While Algorithm can make 71 = O for graphs satisfying S 2 | | as Table 12 demonstrates, the obtained Ti values after node sampling are exactly zero due the limit the number of nodes that can be sampled. If [Sx] 2 SW), the minimum number of nodes that will be sampled for each set is 50% of the initial group size, otherwise the limit is 25% of the initial group size. Such limits are employed to prevent the generation of excessively small subgraphs, which can pre- vent proper learning and create stability issues. Furthermore, proposed global edge deletion/addition frameworks cannot directly make "/2 zero, as the reduction of "2 to zero requires node-wise consid- eration. Since such an independent consideration of each node can incur significant computational complexity for large graphs, stay within the realm of global schemes that can still help to reduce value 72. However, the examination of optimal schemes that can make 71 72 zero helps provide important insights and justification for the proposed augmentations.
Motivated by this, we examined "optimal" strategies which can drive Yr or "/2 to zero. The corre- sponding node sampling strategy copes with each node independently by deleting/adding edges so that d:' d,,, Yu; E V. Different from the proposed global edge manipulation scheme Scction 3.3.3 such node-level edge deletion/addition frameworks can change the value of ?/ and henceforth Interfere with the effects of the node sampling step. Additionally, the employment of edge deletion for the graph makes the utilization of edge addition unnecessary and vice versa, both schemes seek to achieve the same goal, i.e., di = d,', Ve; E V. Therefore, only the "optimal" edge dele- tion or addition scheme is employed. We would like note that the investigation is carried out for Pokec networks, as |S-] < { for Facebook networks, which makes the design of an optimal node sampling scheme challenging due to the unpredictable increase in S and the unpredictable decrease in SX, when sampling from the set Sx (some of the excluded nodes and edges may be the only inter-edges for the nodes the sampled graph, resulting in further increase Sw and further decrease in Sx).
Table 13: Effects of optimal augmentations on
Original 0.66
Node Sampling
Edge Deletion
Edge Addition
Pokes- Pokce-n
0.00
0.67
1.00
0.67
0.00
0.67
1.00
Table 14: Effects of optimal augmentations on 72
Original 0.90
Node Sampling
Edge Deletion
Edge Addition
Pokee-z Pokce-n
0.48
0.00
0.91
0.46
0.00
0.00
24

---

Under review as a conference paper at ICLR 2022
Table 15: Effects of each step in Node Sampling Edge Deletion
Original Graph
Node Sampling
Edge Deletion
Pokec-7 71
0.66
0.00
0.08
72
0.90
0-48
0.00
Pokoo-n 71
0.91
0.46
0,00
Table 16: Effects of each step in Node Sampling + Edge Addition
Original Graph
Node Sampling
Edge Addition
Pokec
0.66
0.00
0.73
72
0.48
Pokec 71 0.67
0.00
0.70
72
0.91
0.46
0.00
Tables 13 16 demonstrate that the utilized node sampling, edge deletion/addition frameworks are optimal in the sense that they reduce "1 and 72 to zero, respectively. However, presented 71 and 72 values also show the interference of optimal edge manipulations on V/. increases after the application of edge deletion/addition following node sampling. Specifically, edge addition has great impact on it.
25


Reviews:
[{"review_id": "h4XJPQ6XYnC", "reviewer": "Reviewer_LHQM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "I want to preface my review by stating that I am not very familiar with graph neural networks, and will thus be mostly evaluating the “fairness aspect” of the paper.\n\n**Strengths**\n- `The problem setting is relevant.` Fair representation learning for tabular data has been studied extensively in the literature. However, fair representation learning has not been considered yet for graphs, which is the problem that this paper investigates. As the paper empirically demonstrates, prior work on graph representation learning typically incurs group fairness violations, which need to be addressed. \n- `The method is novel and well-motivated.` The paper theoretically analyses the correlation between sensitive attributes and the graph representation and uses the analysis to propose different graph augmentation methods to reduce (intrinsic) bias of the representations.\n- `The paper is clearly written.` Even as an outsider of the field of graph neural networks I was able to follow the paper as the ideas are well-motivated and clearly presented.\n\n**Weaknesses**\n- `The ablation study yields inconclusive results.` Depending on the task, different ablated versions of the proposed method (e.g., without edge deletion) significantly outperform the full method, which is not ideal. In my opinion, it would be better to tailor the approach to the different tasks (e.g., by removing the obsolete parts), rather than leaving the tuning to the practitioners interested in applying the method in practice.  \n\n**Questions**\n- How do the different graph augmentation strategies interact? The paper conducts an ablation study to compare the performance of different augmentation strategies, but it would be interesting to see if any theoretical conclusions can be made.\n- The equation for $\\gamma_2$ in theorem 1 and section 3.3.3 are inconsistent. Which is the correct one?\n- Proposition 1 shows that in expectation, the proposed adaptive feature masking scheme results in a lower distribution difference compared to uniform feature masking. However, the uniform feature masking is not the baseline we care about (I think). Instead, we would like to know how the proposed masking scheme affects the distributions compared to no masking at all. Do you have any insight on this?\n", "summary_of_the_paper": "The paper considers the problem of learning fair representations via graph neural networks. Concretely, the paper derives an upper bound on the correlation between sensitive attributes and representations and uses this bound to propose various graph augmentations that increase different group fairness metrics (e.g., statistical parity). The proposed augmentations are feature masking, node sampling, and connectivity augmentation. An experimental evaluation on different node classification, link prediction, and edge deletion tasks shows that the proposed method learns representations with higher group fairness while incurring minimal utility decreases.", "summary_of_the_review": "The relevance of the problem setting, technical and empirical novelty, good presentation, and significant results warrant acceptance of the paper in my opinion.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "d7cLpfLitaF", "reviewer": "Reviewer_FSrq", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "\nStrengths:\n1. The proposed method improves fairness metrics on node classification and link prediction while maintaining decent performance on accuracy.\n2. The proposed method is simple to implement and justified by the theoretical analysis on the upper bound.\n\nWeaknesses:\n1. The hyperparameters for data augmentation provided in appendix (A.7) seem to be a bit like magic numbers. How do the author determine to use these values rather than other values? Also, the sensitivity of the proposed methods w.r.t the hyperparameters should be investigated.\n2. The effect of each data augmentation technique might interfere with each other. How to specify the right amount of augmentation for each type is not well studied.\n3. Some case study on the real-world dataset or even toy dataset can be helpful for readers to better understand these data augmentation techniques in a more intuitive manner.\n\n", "summary_of_the_paper": "This paper studies the bias issue in the representation learned by GNN-based models. Some theoretical analysis is presented, and based on this analysis they propose several data augmentation techniques, such as feature masking, edge addition/deletion and node sampling. Experimental results demonstrate the effectiveness of these augmentation on multiple real-world graphs.", "summary_of_the_review": "Overall the proposed technique following the analysis on the theoretical upper bound, is simple and effective in improving fairness metrics. Experiments could be made stronger though, such as by including sensitivity analysis on the hyperparameters.", "strength_and_weaknesses": "", "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": "GEoUvf20db", "reviewer": "Reviewer_gszv", "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": "Strengths:\n\n(1) This paper studies an interesting and important problem of GNN fairness. \n\n(2) The proposed method demonstrates effective empirical performance on several benchmark datasets.\n\n(3) The proposed data augmentation tricks are easy to implement and potentially broadly applicable.\n\nWeakness:\n\n(1) The presentation of the analysis can be greatly improved.\n\n    (1.1) The assumptions for Theorem 1 should be stated explicitly in the form of Assumptions. The current writing makes it difficult to check what exactly are being assumed in order to prove Theorem 1.\n\n    (1.2) Some of the assumptions are questionable. For example, it seems that the GNN hidden representations $h_i$'s follow a uniform distribution. How is that possible? And how much does Theorem 1 rely on this assumption?\n\n    (1.3) The intuitions of the analysis should be better explained. For example, $\\gamma_2$ takes a very complicated form. What is the intuition of this term?\n\n(2) The connection between the proposed augmentation tricks and the three terms in the upper bound is ambiguous. If the three terms are really important, why don't we directly augment the data by optimizing for those terms? For example, based on the definition of $\\gamma_1$, it seems very easy to reduce it to 0 by rewiring the graph. What are the potential trade-offs for not fully optimizing those terms?\n\n(3) In the appendix, it is shown that the proposed tricks can reduce the $\\gamma$ values. Could you include an ablation study testing methods that directly optimize for these terms, as mentioned in (2).\n\n(4) Quite a few missing literatures on GNN fairness:\n\n1. A. Bose and W. Hamilton. Compositional fairness constraints for graph embeddings. \n2. M. Buyl and T. Bie. The kl-divergence between a graph model and its fair i-projection as a fairness regularizer.\n3. Y. Dong, J. Kang, H. Tong, and J. Li. Individual fairness for graph neural networks: a ranking based approach.\n4. C. Laclau, I. Redko, M. Choudhary, and C. Largeron. All of the fairness for edge prediction with optimal transport.\n5. J. Ma, J. Deng, and Q. Mei. Subgroup generalization and fairness of graph neural networks.\n6. Z. Zeng, R. Islam, K. Keya, J. Foulds, Y. Song, and S. Pan. Fair representation learning for heterogeneous information networks.\n\n\n\n----------Post Author Response-----------------\nI appreciate the author response and revision, which resolved most of my concerns. I therefore raise my evaluation to 6. The proposed method still seems somewhat ad-hoc but overall this work would be an interesting addition to the GNN fairness literature.", "summary_of_the_paper": "This paper proposes a set of data augmentation approach to improve the fairness of GNNs. It first provides an upper bound on the correlation between the GNN node representations and a given sensitive attribute. Then it proposes three data augmentation tricks to respectively reduce three terms of the upper bound. The proposed method is evaluated on several benchmark datasets to show the effectiveness.", "summary_of_the_review": "This paper proposes a set of data augmentation tricks that demonstrate empirical gain on GNN fairness. However, the presentation of analysis and motivation is not convincing and can be largely improved. ", "strength_and_weaknesses": "", "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": "Ayrttzl4fr", "reviewer": "Reviewer_xMz4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Several main concerns should be well-addressed by the authors.\n\n1. In the Introduction, the motivation is not clear.\nWhy the \"augmentation method\" can well address this problem? It seems that the authors find that \"augmentation has not been employed for fairness learning on graph, so we do\".\nBesides, many related studies have been proposed for fair node representations. Can they deal with this problem? The authors do not illustrate how and why the proposed model is better than theirs.\n\n2. In the section of Related Work, the related studies are not sufficiently surveyed, and several recent related studies such as [1,2,3] are missed. \nBesides, in the last sentence of page 2, the authors claim \"it is not adaptive to the graph structure\". What does it mean? And why? The authors should give more explanations.\nFurthermore, the authors do not provide the drawbacks of these related studies compared to the proposed model.\n\n3. At the end of page 3, the authors give an equation to depict the calculation of correlation between the sensitive attributes and the aggregated representations. \nHowever, this equation is a bit confusing. In particular, in the numerator of this equation, what does \"n\" in the sum operator mean? \nBesides, in the following paragraph, why \"it is assumed that these distributions have the same maximal deviation ∆\"? \n\n4. In the first paragraph of section 3.3.1, the authors claim that \"for the first layer of GNN without losing significant information that the features provide\". However, there is no content to demonstrate the proposed model can fulfill the goal of \"without losing significant information\". Both the features and the structures are modified to train the GNN model (such as by feature mask, as well as edge addition and deletion), thus much important information could be lost. So how to guarantee this claim?\n\n5. In the first paragraph of section 3.3.3, there are two confusing equations |E_x|<=|E_o| and |E_x|>=|E_o|.\n\n6. With the proposed model, some augmented graphs can be achieved. However, the authors do not give the details that how to use these graphs for contrastive training. To maximize their agreement?\nGenerally, contrastive learning usually aims to learn representations with better generalizability, transferability and robustness. So why this kind of contrastive learning, though with the proposed augmentations, can address the fairness issue?\n\n7. In experiments, the authors employ citation networks Cora, Citeseer and Pubmed for fairness evaluation, and utilize the category of the articles as their sensitive attributes. However, this kind of utilization is not reasonable. Sensitive attributes are the inherent attributes of instances, and can involve some kind of discrimination. However, here the category of articles is not an inherent attribute but is summarized by humans. Would they involve any discrimination in the articles? I don't think so.\nFor the fairness evaluation of node representations, the authors employ two widely used metrics, namely statistical parity and equal opportunity. For example, for nodes with different genders, the gender might influence their labels. However, for the fairness evaluation of edges, the proposed metrics are not well-motivated. In particular, for edges belonging to different groups (E^X or E^W), do this kind of sensitive attributes (i.e., the groups) influence their existence? Besides, why the generation of fair node representations, can generate fair edges?\n\n8. In experiments, most of the fairness learning approaches are not employed as the baselines for comparison, such as the related studies in section 2, as well as [1,2]. Thus, the experiments are not convincing.\n\n\n[1] Compositional fairness constraints for graph embeddings. ICML 2019\n\n[2] Debayes: a bayesian method for debiasing network embeddings. ICML 2020\n\n[3] Debiasing knowledge graph embeddings. EMNLP 2020", "summary_of_the_paper": "This paper investigates the problem of fairness learning on graphs. To address this, the authors first give a theoretical analysis on the sources of bias in node representations achieved by GNNs, then propose several data augmentation methods for fair node representation learning. Experiments on several datasets demonstrate the effectiveness of the proposed model.", "summary_of_the_review": "1. The motivation of the paper is not clear enough.\n2. Several claims are not well-demonstrated.\n3. The experimental settings are not quite reasonable, and the experiments are not convincing enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Meta-review: This paper studies augmentation-based methods to improve GNN fairness. 
Specifically, based on upper bounds, they propose augmentation tricks to reduce such bounds, empirically validated from benchmark datasets.

Before rebuttal, there was a negative consensus that evaluation results are inconclusive and important state-of-the-arts are not discussed. 
Authors have significantly revised to address the concerns of some reviewers (gszb and LHQM), though some concerns still remain that the scheme is rather ad-hoc. 
Meanwhile, reviewer xMz4 did not find rebuttal sufficient, as some valid comments were not fully discussed.
First, datasets where sensitive attributes are the inherent attributes of instances are more suitable for evaluation, which has not been properly addressed by authors.
Second, important baselines were mentioned by xMz4, but they were only mentioned briefly in the new section of related work in the revised work.
For example, (Agarwal et al 2021) is mentioned as dealing with counterfactual fairness only, but statistic parity studied in this paper is highly related to this concept.
Similarly, this work can be viewed as an ad-hoc extension for fairness of GCA, without in-depth discussions to compare/contrast with these work, and to better highlight novelty/distinction.

Summing up reviewer discussions, we conclude this paper is not ready yet as an ICLR publication.
Decision: Reject