Fast&Fair: Training Acceleration and Bias Mitigation for GNNs
Authors: Oyku Deniz Kose
Yanning Shen
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) have been demonstrated to achieve state-of-the-art performance for a number of graph-based learning tasks, which leads to a rise in their employment in various domains. However, it has been shown that GNNs may inherit and even amplify bias within training data, which leads to unfair results towards certain sensitive groups. Meanwhile, training of GNNs introduces additional challenges, such as slow convergence and possible instability. Faced with these limitations, this work proposes FairNorm, a unified normalization-based framework that reduces the bias in GNN-based learning while also providing provably faster convergence. Specifically, FairNorm presents individual normalization operators over different sensitive groups and introduces fairness regularizers on the learnable parameters of normalization layers to reduce the bias in GNNs. The design of the proposed regularizers is built upon analyses that illuminate the sources of bias in graph-based learning. Experiments on node classification over real-world networks demonstrate the efficiency of the proposed scheme in improving fairness in terms of statistical parity and equal opportunity compared to fairness-aware baselines. In addition, it is empirically shown that the proposed framework leads to faster convergence compared to the naive baseline where no normalization is employed.

Published in Transactions on Machine Learning Research (04/2023)
Fair: Training Acceleration and Bias Mitigation for GNNs
O. Deniz Kose
okose @ucci. edu
Department of Electrionl Engineering and Computer Science University of California Iroine
Yanning Shen
yarmnings@uci eduu
Department of Electrical Engineering and Computer Science University of California Iroine
Reviewed on OpenReview: hutpass.//ggeeerreessse//e/////s
Abstract
Graph neural networks (GNNs) have been demonstrated to achieve state-of-the-art performance for number of graph-based learning tasks, which leads to rise in their employment in various domains. However, it has been shown that GNNs may inherit and even amplify bias within training data, which leads to unfair results towards certain sensitive groups. Meanwhile, training GNNs introduces additional challenges, such as slow convergence and possible instability. Faced with these limitations, this work proposes FairNorm, a unified tormaliizaionn-assed framework that reduces the bias in GNN-based learning while also providing provably faster convergence. Specifically, FairNorm presents individual normalization operators over different sensitive groups and introduces fairness regularizers on the learnable parameters of normalization layers to reduce the bias in GNNs. The design of the proposed regularizers is built upon analyses that illuminate the sources of bias in graph-base based learning. Experiments on node classification over real-world networks demonstrate the efficiency of the proposed scheme in improving fairness in terms of statistical parity and equal opportunity compared fairness aware baselines. In addition, is empirically shown that the proposed framework leads faster convergence compared to the naive baseline where normalization is employed.
1 Introduction
Graphs are powerful tools for modeling complex systems and the relations within them. Hence, they are widely employed represent various real-world systems, such as gene networks, traffic networks, and social networks name few. Such expressiveness has led to rising attention towards learning graphs, and it has been shown that graph neural networks (GNNs) achieve the state-of-the-art for several tasks over graphs Gooi et al.) 2005 Scarselli et al. 2008 Hamilton et al. 2017a; Kipf & Welling 2017; Veličković et al, 2018 Xu et al. 2018b). GNNs create node representations by repeatedly aggregating information from the neighbors, which can be employed on ensuing tasks such as traffic forecasting (Opolka et al. 2019 crime forccasting (Jin et al. 2020), and recommender systems (Ying et al. 2018).
Machine learning (ML) models have been widely used in various domains to make critical decisions. Therefore, it is essential to prevent discriminatory behavior in these models towards under-represented groups. However, it has been demonstrated that ML models propagate the potential bias within the training data Dworrk et al.] 2012: Beutel et al. 2017) and lead to discriminatory results in ensuing applications. Particular to GNNs, it has been shown that in addition to propagating the already existing bias, LNNN-bseed
* CCorrespondngg author.

---

Published in Transactions on Machine Learning Research (04/2023)
learning may even amplify it due to the utilization of biased graph topologies DDai & Wang 2021 well-motivates the studies in fairness-aware GNN-based learning.
This
Normalization operations shift and scale the hidden representations created in deep neural networks (DNNs)
in order to accelerate the optimization process in training (Toffe & Szegedy
2015 Ulyanov et al. 2016 Ba
et al. 2016 Salimans& & Kingma 2016 Xiong et al. 2020 Míyato et al. 2018 Wu & He 2018 [aanturar et al.
2018 While the other aspects of GNN-based learning are theoretically investigated, such as generalization
(Scarselli et al. 2018; Xu et al. 2019b) and expressiveness (Xu et al.) 2018a] Loukas
2020 Ying et al. 2021
the optimization of GNNs is analytically an under-explored area. Practically, training GNNs generally has
slow convergence rate and is accompanied by instability issues (Xu et al. 2018a). Inspired by this, Cai
et al. 2021 investigates the effect of a shift operation on a simple GNN-based learning environment and proposes a normalization framework that is suitable for GNNs, The proposed framework in Cai et al. (2021) GraphNorm, is demonstrated to be more effective in improving convergence speed over graphs compared to previously presented normalization strategies in other domains.
It has been shown in Balunovic et al. (2021) that the distributional discrepancy between the representations among different sensitive groups is one of the leading factors to bias in general ML algorithms. For GNNs, fairness analyses have also shown that the distributions of the reprosentations of different sensitive groups are key factors that affect the resulting bias (Li et al. 2020 Kose & Shen 2022). Note that normalization layers learn the parameters that manage the sample mean and variance of these hidden representations. Hence, the normalization can be readily applied to manipulate the related statistics to reduce the bias, while also improving the convergence. Motivated by this, this study proposes a unified GNN-based learning framework, FairNorm, that provides faster convergence through the employment of normalization layer, while also mitigating the bias with novel fairness-aware regularizers normalization layer. Overall, the contributions of the present work can be summarized as follows:
the learnable parameters in the introduced
c1) We propose a framework that can reduce bias while providing a higher convergence speed for a GNN- based learning environment. To the best of our knowledge, FairNorm is the first attempt to improve fairness and convergence speed in a unified framework.
c2) The effect of the proposed shift operations on convergence rate is investigated in a simple GNN-based learning framework. It is analytically shown that the proposed shift operations can improve the convergence rate for node classification compared to the case where no shift is employed.
c3) Fairness-aware regularizers are introduced on the trainable parameters of the normalization layers. The design of the regularizers is based on theoretical understanding regarding the sources of bias in GNNs. c4) Empirical results are obtained over real-world networks in terms of utility and fairness metrics for node classification. It is demonstrated that compared to fairness-aware baselines, FairNorm leads to an improvement in fairness metrics while providing comparable utility. Mcanwhile, it is empirically shown that FairNorm enhances the convergence speed with respect to the no-normalization baseline.
2 Related Work
Fairness- learning over graphs: Rahman et al. (2019) serves as a seminal work for random walk- based fairness-aware learning over graphs. In addition, Dai & Wang 2021); Bose & Hamilton (2019) Fisher
et al. 2020) propose to use adversarial regularizors to reduce bias in GNNs. Another approach is to utilize a Bayesian approach where the sensitive information is modeled in the prior distribution to enhance fairness
over graphs (Buyl& & De Bie, 2020). Furthermore, Ma et al. (2021) performs a PAC-Bayesian analysis and links the notion of subgroup generalization to accuracy disparity, and Zeng al. (2021) proposes several strategies including GNN-based ones to reduce bias for the representations of heterogeneous information networks. Specifically for fairness-awar link prediction, while Buyl & De Bie (2021) introduces regularizer,
Li ct al. (2020): Laclau et al. (2021) propose strategics that alter the adjacency matrix. With a specific consideration of individual fairness over graphs, Dong el al. (2021 proposes a ranking-based framework.
Another research direction in fairnes--awan aware graph- based learning is to modify the graph structure to combat
bias resulted from the graph connectivity (Agarwal et al.,
2021 Spinelli et al. 2002 Kose & Shen] 2022 Köse & Shen 2021). Differing from all previous works, the proposed framework herein proposes unified framework that can mitigate bias in GNN-based learning together with an enhanced convergence speed.
2

---

Published in Transactions on Machine Learning Research (04/2023)
Normalization: Batch Normalization (BatchNorm) [lffee & Szegedy 2015 is the pioncering study that proposes to shift. and scale the hidden representations in batch to accelerate the convergence of training
for DNNs. Following that, several normalization strategies are presented so far for different domains (Huang
ict al.
2020
Toffe & Szegody
2015
Ulyanov et al.) 2016 Ba ot al., 2016; Salimans & Kingma 2016 Xiong
let al.
2020;
Miyato et al.]
2018 Wu & He] 2018: Santurkar et al. 2018 Xu el al. 2019a; Dong el al.
2021a;
Huang et al.] 2022). Specifically, LayerNorm is presented for natural language processing (Ba et al.
2016),
and InstanceNorm Ulynnvv et al., 2016) seeks to improve the optimization for style transfer tasks, Yi et al. 2018)); Sun et al. (2020) target at permutation-equivalle
while
(erenner,CChangggg data processing. Moreover, Chang
ct al. (2019) presents a domain-specifi normalization technique for unsupervised domain adaptation, and Liu et al. (2020) ; Yu et al. 20200 provide normalization--aase solutions for adversarial robustness and image inpainting, respectively.
For GNNs, Xu et al. (2018a) adapts BatchNorm within the framework of graph isomorphism networks, while a prior version of Dwivedi et al. (2020) normalizes node features based on the graph size. By taking the graph structure into account, Chen et. al. (2022) proposes two novel normalization techniques, as well as an attention mechanism that learns weighted combination of multiple graph-aware normalization strategies. A sizo-agnostic normalization for graphs, GraphNorm is proposed in (Cai et al., 2021). which improves InstanceNorm for graphs with learnable shift to prevent degradation in expressiveness. Normalization frameworks are also utilized to combat the over-smoothing issue over GNNs, where Zhou et al. (2000) applies the Normalization independently over clusters that are defined with respect to the class labels, and Zhao & Akoglu (2020) normalizes the total pairwise feature distances. It important to note that the cluster-wiss normalization introduced in Zhou al. (2020) aims to improve the discrimination of the representations from different classes. However, the cluster definition therein differ significantly from the present work. Furthermore, none of the aforementioned normalization schemes consider fairness.
3 Preliminaries
This study develops a unified training scheme for GNNs that can improve fairness while at the same time enhance the convergence speed, given an input graph g := (V.E), where V : {vi, U2, [yy denotes the node set, and & s V V is the edge set. Matrices X E RFN and A {0, 13 are the feature and adjacency matrices, respectively, where Aij if and only if (vs, uj) E E and F is the dimension of features. Degree matrix D NNN is defined to be a diagonal matrix with the nth diagonal entry denoting the degree of node Un.- In this study, the sensitive attributes of the nodes are denoted by E (0, 1),, where the existence of single, binary sensitive attribute is considered. Furthermore, S and 8 denote the set of nodes w whose sensitive altributes are 0 and 1, respectively. Node representations at kth layer are represented by (k) E R FxN, where hy denotes the representation of node vy and hig is the ith feature of hy. Vectors Xj E R and 8j E (0, 1} will be used to denote the feature vector and the sensitive attributc of node Uy. Throughout the paper, max(:....,:) outputs the element-wise maximum vector of its argument vectors, and mean(., mean(.......)) denotes the sample mean operator.
GNNs learn node embeddings by repcatedly aggregating information from neighboring nodes. GNNs with different aggregation schemes have been developed, see in (Kipf & Welling 2017 Veličković et al. 2018 Xu
et al. 2018a). A general formulation of GNNs in the matrix form can be written as:
(Kk)_ Act (W(HH
where W(+) represents the weight matrix of GNN at kth layer and Act denotes activation function. In this formulation, Q matrix specifies the information aggregation process from neighbors, which changes in different GNN frameworks. For example, Q = D ADD å for Graph Convolutional Networks (GCN) (Kipf & Welling, 2017), where A A + IN with IN E (0, 13 NxN denoting the idcntity matrix, and D is the degree matrix corresponding to Å. Finally, the representations created after one aggregation process are denoted by (A) ( Q. Note that the superscript (k) for layer number is dropped in the remaining of the paper, as the proposed framework is applicable to every layer in the same way.
3.1 Normalization for GNNs
3

---

Published in Transactions on Machine Learning Research (04/2023)
While different normalization schemes have been proposed for different domains, there is not universal normalization strategy that suits every domain (Cai et al.
2021). For GNNs, Cai et. al. (2021) demonstrates that mean normalization can degrade the expressiveness of the neural networks, as mean statistics incorporate graph structural information. Motivated by this, Cai et al. (2021) proposes GraphNorm, which employs a learnable shift to preserve the mean statistics to a certain exlent. The study reports that Graph consistently achieves superior convergence speed and training stability on graph classification for GNNs over other normalization strategies. For the input matrix A RNN, GraphNorm can be mathematically described as:
GraphNorm (ai,)) 9/- Aig m
Bi F....F
(1)
0,
Ey (01. and oi, n. Be are the learnable parameters.
where mi
0i. N
N
3.2
Bias in GNNs
ML models can lead to discriminatory results towards certain under-represented groups, as they propagate the bias within the training data (Dwork et al., 2012 Beutel et al., 2017). It has been demonstrated that the utilization of graph structure in GNNs amplifies the already existing bias (Dai & Wang 2021). Thus, understanding the sources of bias in graph structure is crucial to develop remedy for it. Motivated by this, Li et al. (2020) and Kose & Shen (2022) investigate the sources of bias in GNN-based learning. In Li et al. (020), the representation discrepancy between different sensitive groups is examined, whereas in Kose & Shen (2022), the bias analysis is based on the correlation between the aggregated reproscntations and sensitive altributes s. Though through different approaches, both analyses Li et al. (2020 Theorem 4.1)
and Kose & Shen (2022) Theorem 3.1) demonstrate the parallelism between the terms | ( and
bias in GNN-based learning. Here, (0 and yx() are the sample means of node representations respectively
across each sensitive group, where (=)) mean hy U/ E 8"), and A stands for the maximal deviations
of hidden reprosentations, that is A! max, (/ p4 (0) (1 vi = 1, 1,. and A max (0) (1).. The
superscript (n) in hn") is utilized to specify the sensitive group index. Specifically, the hidden representation hr")) (m) corresponds to a node Uj S
As the analyses in et et al. (2020): Kose & Shen 2022 suggest that the distributions of hidden representations corresponding to different sensitive groups influence the resulted bias by GNNs, a tool that can shift these group-wise distributions can effectively decrease bias-related terms, and hence the overall bias.
4 FairNorm: A Fair and Fast Training Framework for GNNs
This section presents the proposed unified framework that achieves fairness improvement together with faster convergence speed for GNN-based lcarning. Herein, we first present group-wise normalization framework (M-Norm),, upon which we develop FairNorm by incorporating two novel fairness regularizers on M-norm for Hirmess-enhancemen
4.1 Group-wise Normalization
It has been demonstrated in Li et al. 20200; Kose & Shen (2022) that decreasing [|x(0) [1( and A can effectively reduce bias in GNN-based learning. Note that both terms are affected by the distributions of representations from different sensitive groups. On the other hand, the mean and standard deviation of the hidden representations, and in turn their distributions, are affected by the lcarnable parameters of a normalization layer. Thus, employing such layer can enable manipulating said distributions, which can be used to improve fairness. Inspired by this, the proposed framework, FairNorm, first applies normalizations different sensitive groups individually, which results in individual Iearnable parameters affecting (0),, and ((),, as well as their difference. For any input matrix A FxN given that the columns of A can be divided into two sensitive groups 8 and S1, the corresponding multiple group-wise normalization operations
4

---

Published in Transactions on Machine Learning Research (04/2023)
be mathematically described as:
A
(n)
(n)
M-Norm (
(m) (n).
m
(n)
(1.) %
+
(2)
(n)
0,
118 (4)
118" ( (a!"))
)
where m, = 2i=1 L2 (0 22
(n) (n) _ are learnable parameters, = and aj +
[St]
1,.... F and - 0, 1. The superscript (n) in A (n)
j specifies that the representation corresponds to node from the sensitive group S Considering that mean normalization can degrade the expressiveness of GNNs (Cai et al. 2021), the proposed framework employs the learnable parameter a that manages the amount of mean normalization.
It demonstrated in Cai al. (2021) that applying a shift operation over the whole graph can speed up the convergence for graph classification. However, as the proposed framework herein applies multiple shift operations individually over subgraphs corresponding to different sensitive groups and considers the node classification task, the effect of the proposed strategy on the convergence speed becomes unclear. Hence, the analysis in Cai et al. 2021)) cannot. be directly applied to this case. Motivated by this, this study analytically examines the influence of group-wise shifts on the convergence speed.
Shift operations over different sensitive groups can be applied in matrix forms via the matrices O and N where N(²) = IN | ((())) for n 0, 1. In this formulation, e(n) E RR is created such that ej if U/ S", and oj (n) 0 otherwise. Therefore, for any vector RVV, c (N()) c (150) Ejsyes (c(n)) Hence, the group-wiss wise shift operations applied hidden representations can be written as:
MShift(W(()) Q) w QN
(3)
The following lemma demonstrates that ((ON() acts preconditioner of Q, whose proof is presented in Appendix
Lemma 1 Let X; and o; denote the ith singular values of Q and QN(()) respectively. It can be shown that QN ()()) has at least two singular values being equal to zero, i.e., IN = "IN-1 = O. Without loss of generalization, assume A1 & ... & AN and 7n & 72 $ 7N-2- Then, the following holds:
\1 & 7
A & 72
:
AN-2 & 7N-2 AN.
(4)
where the equalities hold, i.c., X; 7 or AN 7N-2, only Q has right singular vector for which (=
0 0 and (e())TTo T are satisfied.
In other domains, such as DNNs or iterative algorithms, similar preconditioning is considered to help the training (Kingma & Ba 2014 Axelsson 1985)- Such a preconditioning of the aggregation matrix Q is also demonstrated to accelerate the optimization of GNNs (Cai et al. 2021). In order to theoretically investigate such an effect in our setting, we considered basic linear GNN model for node classification that is optimized via gradient descent, and presented its convergence analysis in Theorem I Appendix B presents
all assumptions and considered learning settings employed in Theorem 1 in detail, as well its proof.
MShift denote the parometers of linear GNN model at time t for the cases where no shift is applied and shift operations (() are applied, respectively. It holds with high probability that.
Theorem Let w. Vanilla and w;
W
MSAaft
.SSeftt | = (pf) and [| Vansilo -w Vanilla 1 12=0 (ph), where P < p2-
(5)
Here, w Vanilla and w concludes that the shift operations applied through N() lead faster convergence with high probability compared to the scheme where no shift is applied.
MShiftt respectively. Thus, it MShift denote the optimal values for w // Vanillo and w w
5

---

Published in Transactions on Machine Learning Research (04/2023)
Theorem demonstrates that the individual shift operations applied over different sensitive groups indeed
improve the convergence rate compared to the naive baseline. While the result of Theorem 1 seems to be
similar to the result Cai et al. (2021] Proposition 3.1), the analysis in Cai et al. (2021) cannot be easily extended to our proof due to the employment of group-wise shifts in this work and the fact that we consider node classification instead of graph classification.
4.2 Fairness-aware Regularizers
As a complementary step to M-Norm, FairNorm introduces two novel fairness-aware regularizers to mitigate bias in GNN-based learning. Consider the conventional case where the normalization is applied after linear transformations (Ioffe Szegedy] 2015 Xiong et al., 2020 Cai al. 2021). For this case, the hidden representations can be expressed in matrix form as:
H Act (M-Norm (n) (WHQ) ()) for 0,
(6)
In equation 6 (WHQ) (n) denotes the submatrix consisting the columns of (WHQ) whose corresponding nodes are in S" Furthermore, as the proposed strategy applics normalizations individually over different sensitive groups, these group-wise normalization layers are differentiated by the superscript n = 0, 1. Let ((0)) IR denote the sample mean of representations after normalization for the sensitive group S",n 0, 1. In the proposed framework, recalling from Subsection 4.1] individual normalization layers are employed to create individual learnable parameters for the distributions of different sensitive groups, so that the bias-related lerms derived in Li et. al. (2020); Kose Shen (2022) can be reduced. However, in order to manipulate ( and ( for possible bias reduction, the relationship between [Ąx()) (((0)-p) (1 and (n())ss should be investigated. To this end, present the following theorem, the proof of which can be found in Appendix
Theorem 2 Let Act(.) be Lipschitz continuous with Lipschitz conslant L,, and let Hm) denole the normalized representations in group S". Then, [| - (1 is bounded above by
l (0) - 1l < L (0) a + 1 A0)))) Vp 2 1.
(7)
Here, (m) is the manimal deviation of (a) from ii(m) (i.e., we have A!") = max, [1(0)) p, Vi = 1, F).
Theorem demonstrates that decreasing (7) |z(10 results in a decreased upper bound for || - 11)
which can possibly reduce the actual value of [ạ( (. Based on this result, as a sccond step after applying group-wise normalization operators, FairNorm proposes the use of a regularizer term C, = | (0)
101 to decrease bias for GNN-bbaed learning. We note that many commonly used activation functions such ReLU, sigmoid, tanh, etc. have a Lipschitz constant equal to L =.
Furthermore, Theorem 2 shows that the upper bound for ( - | can also be decreased by reducing the norms of maximal deviations A (0) and A (1), Inspired by this finding, CA = I (0 + Á ()) is also
introduced as a regularizer to reduce the norms of maximal deviations of the normalized representations. Hence, the overall learning objective for the considered node classification task can be written as:
min La + Khe + TLA BGNN
(8)
where C. is the classification loss, C, (7(0) (m)="aaa0)) + 3()) 1 for M-Norm in equation 2 Ls = A 10) 3 +
(0) -
1 1 = |1 (7:00) m (9) (1-a (0)
6 + +19(0)
and A (m)
(! max, (2) m (n) for M-Norm defined in equation 2 Vi 1.... F, where (m) (m) (WHQ) (m)
(n)
(n) denotes the representations input to the normalization layer and rij is the element in ith row and jth
column of (*) matrix. GNN parameters denoted by OONN, and x and are hyperparameters specifying

---

Published in Transactions on Machine Learning Research (04/2023)
the focus on the fairness regularizers.
Remark 1 (Order of normalization and activation). Although the proposed fairness regularizers Cus LA are designed for the conventional case where the normalization used before nonlinear activation, it can be demonstrated that they can also reduce bias when the normalization is applied after activation, where
H M-Norm (n) (Act (WWHQ)()) for 0,
(9)
In this case, it holds that ū(") (m()) and A [1 | (*) for n 0, Therefore, the employment of the proposed fairness regularizers can naturally be extended to the case where the normalization is utilized after
activation, as the analyses in Li et al. (2020); Kose & Shen 2022) demonstrate that reducing || - 1
and || can help mitigate bias in GNN-based learning.
Remark (Applicability to other normalization methods). Note that the proposed FairNorm framework can be readily utilized together with other normalization techniques where the distribution of the normalized representations depends on learnable parameters, e.g., BatchNorm (loffe & Szegedy 2015 long group-wist normalization is applied over each sensitive group.
Table 1: Dataset statistics
Dataset
|Sul
|S1]
Inter-edges
Intra-edges
Pokeo-z
1851
2808
1140
28336
59
Pokec-n
4040
2145
20901
Recidivism
9317
9559
298098
325642
17
5 Experiments
In this section, experimental results obtained real-world datasets for supervised node classification task are presented. The performance of the proposed framework, FairNorm, is compared with baseline schemes in terms of node classification accuracy and fairness metrics. Furthermore, the influence of the proposed fairness-aware normalization strategy on convergence speed is examined.
5.1 Datasets and Settings
Datasets. In the experiments, three real-world networks are used: Pokec-z, Pokec-n Dai & Wang 2021 and the Recidivism graph (Jordan & Freiburger 2015). Pokec-z and Pokec-n are created by sampling the anonymized, 2012 version of Pokec (Takac & Zabovsky 2012), which is a social network used in Slovakia (Dai & Wang 2021). In Pokec nerworks, the region information is utilized as the sensitive altribule, where the nodes are the users living in two major regions. Labels to be used in node classification are assigned to be the binarized working field of the users. The information of defendants (corresponding to nodes) who got released on bail at the U.S. state courts during 1990-2009 (Jordan & Freiburger 2015) is utilized to build the Recidivism graph, where the edges are formed based on the similarity of past criminal records and demographics. Race is used as the sensitive attribute for this graph, and the node classification task classifies defendants into bail (i.e., the defendant is not likely to commit a violent crime if released) or no bail (i.e., the defendant is likely to commit a violent crime if released) (Agarwal et al., 2021). Table presents further statistical information on the utilized datascts. In the table, [Sp] and [S,] are the cardinalities of the sets of nodes with sensitive attributes 0 and 1, respectively. 'Inter-edges" and 'Intra-edges'' correspond to the number of edges linking nodes from different sensitive groups and the same sensitive group, respectively. F in Table 1 denotes the dimension of nodal features.
Evaluation Metrics. Accuracy is used as the utility measure for node classification. Two quantilative measures of group fairness metrics are reported in terms of statistical parity: Asp = PP = = 0) P(ù = 1 | 1)] and equal opportunity: Ago [P( = 1 y 1, 0) P(ğ 1 lly 1, = 1)},
where y is the ground truth label, and ğ denotes the predicted label. Lower values for Asp and Ago signify
better fairness performance DDai & Wang 2021

---

Published in Transactions on Machine Learning Research (04/2023)
Implementation details. To comparatively evaluate our proposed framework, node classification is utilized in supervised setting. A two-layer GCN (Kipf & Welling, 2017) followed by a linear layer is employed for the classification task, which is identical to the experimental setting used in Dai & Wang (2021). A normalization layer follows after every GNN layer, where the normalization is applied after linear translormations and before the non-linear activation, as suggested in Tofle Szegedy (2015); Cai el al. (2021)
For the hyperparameter selection of the GCN model, see Appendix D This experimental framework is kept the same for all baselines. Furthermore, training of the model executed over 50% of the nodes, while the remaining nodes are equally divided to be used the validation and test sets. For each experiment, results for five random data splits are obtained, and the average of them together with standard deviations are presented. The hyperparameters of the proposed fairness-aware framework and all other baselines are tuned via a grid search on cross-validation sels, see again Appendix D for the utilized hyperparameter values.
Baselines, This work aims to mitigate bias via employing fairness-aware regularizers, as well as to provide a faster convergence through its utilized normalization layers. We note that similar to the proposod regularizers, any other lairness-aware regularizer can be employed logether with a normalization layer, for these same purposes. In order to demonstrate the performance improvement of the proposed regularizers over said alternatives, we compare the proposed framework with other fairness-aware regularizers. To this end, the performance of 4 different baselines is presented. For improving fairness in a supervised setting, FairGNN (Dai & Wang 2021) employs adversarial debiasing and a covariance-based regularizer (the absolute covariance between the sensitive attribute and estimated label y). The results for these regularizers are obtained both individually and together, where the framework that utilizes both regularizers is called FairGNN (Dai & Wang. 2021). Furthermore, hyperbolic tangent relaxation of the difference of demographic parity (HTRDDP) that is proposed in Padh ct al. 2021) is utilized another bascline. Note that, as DDP is not differentiable, its relaxations are used as fairness-aware regularizers for gradient-based optimization. It is worth emphasizing that the fairness regularizers proposed in this study are also applicable to an unsupervised setting, while the covariance-basse (also FairGNN) and HT RDDP regularizers can only be used in a supervised framework.
5.2 Experimental Results
Saterr
Nelker
Raturr Fastiom
Spadte
Practe
(a) Pokec-n (ReLU)
(b) Pokec-z (ReLU)
(c) Recidivism (ReLU)
Nallor
Raturn
Farnioon
Spodte
Spocha
Epache
(d) Pokec-n (Sigmoid)
(e) Pokec-z (Sigmoid)
(f) Recidivism (Sigmoid)
Figure Convergence for different graph data sets when the normalization is not applied (Nonorm) and applied hiih/whthutt fairness consideration (FairNorm/ /oraoorommr.......m....
The results of node classification are presented in Table 2 in terms of fairness and utility metrics for both the proposed framework and baselines. The results are obtained for two commonly utilized activation functions: ReLU and sigmoid, in order to demonstrate the efficacy of the proposed framework over different activations. In Table [ "NoNorm" denotes the scheme where no normalization layer employed. "M-Norm" stands for the proposed framework where only individual normalizations are applied to the nodes belonging to different
8

---

Published in Transactions on Machine Learning Research (04/2023)
Table 2: Comparative Results with Baselines for Different Activation Function Selections
ReLU
Sigmoid
Pokec-z
Ace (%)
Asp (%)
Ago (%)
Ace (%)
Asp (%)
(%)
NoNorm
70.24 1.0
6.77
6.18
2.5
70.25 + 0.8
7.40
6.04 t 3.1
M-Norm
70.71 + 0.8
5.37 : 1.3
5.00
2.0
69.81 1.1100 0.7
6.21 = 1.4
4.11 11112 2.1
Covariance
70.66 1 0.8
5.31
1.4
4.56
1.9
69.77
0.6
5.63
+ 1.9
4.04 1 2.1
Adversarial
70.35 1: 0.9
2.41
1.0
2.16
1 0.6
70.01
1 0.9
3.08
1 2.8
3.00
1: 2.4
PairGNN
2.73
1.0
69.93
2.2
2.7
HTRDEP
70.38
1 0.9
2.12
1 2.0
3.38
1.5
69.74
1. 0.7
1.85
1.1
2.27
1.8
FairNorm
70.67 + 1.0
1.35
1.2
1.90 + 1.8
69.73 + 0.9
1.71 0.3
1,48 + 1.1
Pakee-n
Acc (%)
Asp (%)
Ago (%)
Ace (%)
ASp (%)
(8)
NoNorm
0.8
2.19
1.8
68.73
2.68
2.27
2.4
M-Norm
69.25 1 0.5
2.48 1 1.2
2.91 1 1.7
68.59 1 0.9
1.78 1. 2.1
2.88
1.8
Covariance
69.47
0.6
2.06
1.3
2.42
1.5
68,40
1.1
1.70
2.2
2.26
1.8
Adversarial
69.30
0.4
2.09
1 1.9
2.21
1.9
68.47
1 0.7
1.56
1.8
2.25
1.5
FairGNN
69.21
0.4
2.03
1.9
2.29
2.1
68.42
0.7
1.61
1.7
1.71
2.0
HTRpEP
69.51 + 0.5
1.85 + 1.4
2.03
1.5
68.37 + 0.9
1.04 = 1.6
2.53
1.7
FairNorm
69.38 + 0.7
1.26 1.2
1.22 + 1.3
68.88 + 1.1
1.44
1.2
1.74 + 1.7
Recidivism
Acc (%)
Asp (%)
Ago (%)
Ace (%)
Asp (%)
A (Bo(%)
NoNorm
94.32 0.2
1.17 0.9
92.69 0.2
1.31 0.6
M-Norm
95.00 1 0.3
8.87 1 1.2
1.71 1 0.7
94.45 1 0.3
8.94 L 1.2
2.06 1.0
Covariance
95.07 + 0.2
8.82 + 1.1
1.43 + 0.6
92.87 + 1.0
8.44 + 0.6
1.64 + 1.0
Adversurial
94.14 1: 0.1
8.58
1.0
1.26
0.7
93.82
1 0.2
8.72
0.9
1.59
1 1.1
PairGNN
95.14
0.2
8.73 + 1.0
1.33
0.8
94.11
0.2
8.68
1.2
1.51
0.5
HTRDEP
95.16 + 0.2
8.74 + 0.8
1.05
+ 0.4
93.34 + 0.4
8.20 = 0.9
1.04 + 1.0
FairNorm
95.11 + 0.2
8.45 : 1.0
0.90 : 0.5
94.32 + 0.2
7.28 1.1
0.80 : 0.9
sensitive groups, without using the proposed fairness regularizers. Furthermore, "Covariance" is for the covariance- based regularizer (Dai & Wang 2021 "Adversarial" stands for the adversarial regularizer (Dai & Wang] 2021), and *HTRpD"" denotes hyperbolic tangent relaxation the difference of demographie parity (Padh et al. 2021). It should be noted that the results for baselines are obtained with the best performing normalization layer framework (individual normalizations over different sensitive groups vs. normalization over all nodes in the graph) in terms of fairness measures.
The results in Table demonstrate that FairNorm achieves superior fairness performance, together with similar utility, compared to all baselines on all datasets for both of the utilized activations. As M-Norm is the first step of FairNorm without fairness regularizers, the significant improvements in all fairness measures compared to M-Norm signify the efficiency of the designed regularizers. Furthermore, on the Rocidivism fairness metrics is accompanied by a decrease
graph with sigmoid activation, while the improvement in accuracy for the baselines, FairNorm achieves better fairness performance without. deterioration utility. Overall, the results in Table 2 show the efficacy of the proposed fairness regularizers in reducing bias while providing similar utility different real-world networks. Note that, in addition to their superior fairness performance, the proposed regularizers of FairNorm can be flexibly applied to both supervised and unsupervised settings, whereas some of the baselines ("Covariance", "FairGNN", "HTRDpr") require predicted labels for their regularizer designs.
The proposed framework herein aims to mitigate bias by also providing a faster convergence speed. The results in Table / confirm that the proposod fairness regularizers within FairNorm do provide said bias reduction. In order evaluate the convergence speed of FairNorm's group-wise normalizations, Figure [ is presented. The baselines in Figure I consist of GraphNorm (Cai et al., 2021), and the framework where no normalization is applied. We note that in Figure [ Fairnorm is employed with both its individual normalizations as well as its fairness regularizers.
The results on both Pokec datasets and the Recidivism network confirm that the employed normalization can indeed lead a faster convergence in training compared to NoNorm. Figure [ also demonstrates that compared to GraphNorm, the convergence improvement of FairNorm is slightly less on Pokec-z, whereas it provides approximately the same improvement Pokec-n and Recidivism.
9

---

Published in Transactions on Machine Learning Research (04/2023)
5.3 Sensitivity Analysis
Table 3: Sensitivity Analysis for Pokec Networks
Pokec-2
Pokec-u
ReLU
(%)
Asp (%)
Ago (%)
(%)
Agp (%)
Ago (%)
M-Norm
70.71 0.8
5.37 1.3
5.00 1 2.0
69.25 1. 0.5
2.48 1.2
2.91 1 1.7
10 9, 10
70.26
0.9
1.52
1.0
2.19 + 1.2
69.45 + 0.6
2.23 1.3
2.65 + 1.6
10 K- 100
70.48
0.9
1.40
1: 1.0
2:20
1 1.2
69.53
1 0.8
2.07
1.0
1.98
1: 0.8
7- 10" 1000
70.37
1.1
3:20
1 0.9
3.18 1 2.0
69.38 1 0.8
1.55
1.4
1.48
1.7
100, 10
70.67
1.0
1.35
1.2
1.90
1.8
69.56 0.8
2.10 0.9
2.09
+ 0.5
100,
10
70.48
0.9
1.40
1.0
2.20
1 1.7
69.53
1 0.8
2.07
1.0
1.98
1: 0.8
X 100, 10-0
70.55 0.9
1.48 1.2
1.99
1 1.8
69.54 1. 0.7
2.15 1.1
1.84
1 0.9
Pokec-z
Pokec-u
Sigmold
Acc (%)
Asp (%)
Ago (%6
Acc (%)
Asp (%)
AEo (%
M-Norm
69.84 0.7
6.21 1.4
4.44 + 2.1
68.59 + 0.9
1.78 2.1
2.88 + 1.8
10 R 10
69.71 = 0.9
1.36 1 0.4
1.72 1.1
68.97 1 0.8
2.23 1.3
2.49 1 1.8
10-8 9
1.19
2.53 4:
1 1.1
1.2
10 5. 1000
70.06
1.17 0.7
2.47 +
68.37 + 0.7
2.21 1.1
3.47
1.8
x 100.
10-7
70.06 1.2
1.28 0.8
2.39 1.2
68.87 1 1.1
1.45
1.2
1.85
1 1.6
100,
1.19 0.8
1.2
100,
1.28
2.33
Table 4: Sensitivity Analysis for Recidivism Network
ReLU
Sigmoid
Recidivism
Ace (%)
Asp (%)
AEo (%)
Acc (%)
ASp (%)
Ago(%)
M-Norm
95.00 0.3
8.87
1.71 0.7
94.45 +
8.91
2.06 1.0
T 10-10 x=
95.01 i 0.2
8.76 1.2
1.66 +: 0.6
94.38 i 0.2
7.27 1.0
0.95 i 1.0
== 10-10 0.1
95.02 + 0.3
8.02
1.43 + 0.5
94.27
0.3
7.29 +
0.89 + 1.0
10-10 0.01
1.0
0.5
91.32
0.2
1.1
x 0.1,7 10-8
94.99 + 0.2
6.50 1.1
1.17 + 0.6
94.33 + 0.3
7.39 + 1.1
1.12 + 1.0
0.1,7
10
95.02
8.62 1
1.43 0.5
94.27
+ 0.3
7.29
0.89 + 1.0
0.1,7 10
0.1
1811.11
1.0
91.38
0.2
1.0
In order to examine the effects of hyperparameter selection, the sensitivity analysis for the proposod framework is execuled. The results for changing and т values are presented in Tables 3 and for Pokec networks and Recidivism network, respectively. Overall, the results demonstrate that the proposed strategy, FairNorm, typically loads to better fairness mcasures compared to the natural bascline (M-Norm) within a wide range of hyperparameter selection.
5.4 Ablation Study
In order investigate the influences of different fairness regularizers introduced in this study, we carry over an ablation study. The results of this study are presented in Table Table demonstrates that while the employment of Cn seems to have a greater effect in fairness performance improvement, utilization of both C, and LA (FairNorm) leads to better fairness results compared to the cases where only of the regularizers is used with ReLU activation. For the case where sigmoid is used as the nonlincar activation, use of both regularizers again results in better AEO values compared to the cases where only one of the regularizers is employed. However, the same cannot be always claimed for Asp, which can be explained by the fact that sigmoid already limits the maximal deviation some extend after the first layer roducing the effect of Ls. Overall, Table shows that the utilization of both En and La generally achieves the best fairness performance, while L, appears to be more influential component. compared to LA for the bias reduction.
10

---

Published in Transactions on Machine Learning Research (04/2023)
Table 5: Ablation study for the proposed regularizers
ReLU
Sigmoid
Pokec-z
Accuracy (%)
Asp (%)
Ago (%)
Accuracy (%)
ASp (%)
(%)
M-Norm
70.71 0.8
5.00 2.0
69.84 0.7
1.4
4.44 + 2.1
Cp
70.65 0.8
1.50 + 1.0
2.19
# 1.3
69.71 = 0.9
1.36 + 0.4
1.72 + 1.1
LA
70.62 0.9
5.15 1.4
4.55
2.2
69.73 0.5
5.67 2.0
4.29 1 2.3
FairNorm
70.67 1 1.0
1.35 1.2
1.90 1 1.8
69.73 0.9
1.71 1 0.3
1.48 1.1
RcLU
Sigmoid
Pokec-n
Accuracy (%)
Asp (%)
Ago (%)
Accuracy (%)
Asp (%)
A (g)(%)
M-Norm
69.25 0.5
2.48 1.2
2.91 1.7
68.59 0.9
1.78 2.1
2.88 i 1.8
69.30 0.7
1.51 1.4
1.1
1.65
1.80
1.8
LA
69.40 1 0.5
2.55 1 1.1
2.54 :: 1.6
68. 1 0.9
1.78 2.1
2.88 i 1.8
FairNorm
69.38
68.88
ReLU
Sigmoid
Recidivism
Accuracy (%)
Asp (%)
Ago (%)
Accuracy (%)
Asp (%)
Ago(%)
M-Norm
95.00 1: 0.3
8.87 i 1.2
1.71 :: 0.7
94.45 i 0.3
8.94 1.2
2.06 1 1.0
Cp
95.08 + 0.2
8.67 + 1.0
1.35 = 0.5
91.33
0.2
7.18 1.2
1.05 + 1.1
CA
95.12 1 0.2
8.97 i 1.1
1.42 1 0.6
94.39 1 0.3
8.81 1.1
1.92 1 0.9
FairNorm
95.11 0.2
8.45 1.0
0.90 1 0.5
94.32 0.2
7.28 1.1
0.80 0.9
6 Conclusions and Limitations
This study proposes unified framework, FairNorm, that mitigates bias in GNN-based learning and provides laster convergence in training. FairNorm applies group-wise normalizations, and employs two novel fairness regularizers that manipulate the parameters of these normalizations. The designs these regularizers are basod on thcoretical fairness analyscs on GNNs. Experimental results on real-world networks show the fairness improvement of FairNorm over fairness-aware baselines in terms of statistical parity and equal opportunity, well as its similar utility performance in node classification. Furthermore, it is demonstrated that FairNorm improves the convergence speed of the naive baseline where no normalization is used.
The present framework considers only a single sensitive attribute in its design of normalization layers and fairness regularizers. One possible future direction of this study is the extension of the design to a case with multiple sensitive attributes, which may be essential in certain applications.
7 Acknowledgements
We thank the anonymous reviewers for their valuable time in helping us improve our manuscript. Part of this work is supported by the Google Research Scholar Award and NSF ECCS 2207457.
References
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertointy in Artificial Intelligence (UAI), pp. 2114 2124, August 2021.
Owe Axelsson. A survey of preconditioned iterative methods for linear systems of algebraic equations. BIT Numerical Mathematics, 25(1):165 187, 1985.
Jimmy Lei Ba, Jamic Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXio preprint wxXiv:1607.06460 2016.
Mislav Balunovic, Anian Ruoss, and Martin Vechev. Fair normalizing flows. In Proc. International Conference Leurving Representations (ICLR), April 2021.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed Chi. Data decisions and theoretical implications when adversarially learning fair representations. Xiv preprint arXiv: 107.00077 June 2017.
11

---

Published in Transactions on Machine Learning Research (04/2023)
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In Proc.
International Conference on Machine Learning (ICML); pp- 715-724, July 2019.
Maarten Buyl and Tijl De Bie. Debayes: bayesian method for debiasing network embeddings. In Proc. International Conference on Machine Learning (ICML), pp. 1220-1223) July 2020.
Maarten Buyl and Tijl De Bie. The kl-divergence between graph model and its fair i-projection as a fairness regularizer. Xrviv preprint arXiv:2103.010 01846, 2021.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yan Liu, and Liwei Wang. Graphnorm: principled approach accelerating graph neural network training. In Proc. International Conference on Machine Learning (ICML), pp. 1204 1215, July 2021.
Woong- Gi Chang, Tackgeun You, Seonguk Seo, Suha Kwak, and Bohyung Han. Domain-specifie batch normalization for unsupervised domain adaptation. In Proceedings of the IEEE/CVE conference on Computer Vision and Pattern Recognition, pp. 7354-7362, 2019.
Yihao Chen, Xin Tang, Xianbiao Qi, Chun-Guang Li, and Rong Xiao. Learning graph normalization for graph neural networks. Neurocompuling, 493:613 625, 2022.
Wei Cui, Xu Zhang, and Yulong Liu. Covariance matrix estimation from linearly-correlateed gaussian samples. IEFE Transactions on Signal Processing, 67 67(8):2187-211) 2195, 2019.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proc. 14th ACM International Conference on Web Search and Data Mining (WSDM), pp. 680-688, March 2021.
Minjing Dong, Yunhe Wang, Xinghao Chen, and Chang Xu. Towards stable and robust addernets. Advances in Neural Information Processing Systems, 34:13255-13266 2021a.
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 & Dala Mining (SICKDD), pp. 300-310, July 2021b.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXi::2003.0988, 2020.
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.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 249-256, May 2010.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. Proc. IEEE International Joint. Conference on Neural Networks (IJCNN) volume 2, pp. 729 00-,7334-- 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems (NeurIPS), 30, December 2017a.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017b.
Roger A Horn and Charles R Johnson. Matrir analysis. Cambridge university press, 2012.
Lei Huang, Jie Qin, Yi Zhou, Fan Zhu, Li Liu, and Ling Shao. Normalization techniques in training dnns: Methodology, analysis and application. Xiu preprint arxi::0009 12836, 2020.
12

---

Published in Transactions on Machine Learning Research (04/2023)
Lei Huang, Yi Zhou, Tian Wang, Jie Luo, and Xianglong Liu. Delving into the estimation shift of batch normalization in network. In Proceedings of the IERE/CVF Conference on Computer Vision and Pattern Recognition, pp. 763 772, 2022.
Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proc. International Conference on Machine Learning (ICML), pp. 448 456, July 2015.
Guangyin Jin, Qi Wang, Cunchao Zhu, Yanghe Feng, Jincai Huang, and Jiangping Zhou. Addressing crime situation forecasting task with temporal graph convolutional neural network approach. In Proc. International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), pp- 474- 478, February 2020. doi: 10.100/CCMTINAA5542200000
Karcem L. Jordan and Tina L Freiburger. The effect of race/cthnicity sentencing: Examining sentence type, jail length, and prison length. Journal of Ethnicity in Criminal Justice, 13(3):179 196, 2015.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900 19800 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Proc. International Conference on Leurning Represenlations (ICLR), April 2017.
O Deniz Kose and Yanning Shen. Fair node representation learning via adaptive data augmentation. arXiv preprinl ar Nio:2201.085/42 2022.
Öykü Deniz Köse and Yanning Shen. Fairness-aware node representation learning. arXiv preprint arXiv:2106.0533 2021.
Charlotte Laclau, levgen Redko, Manvi Choudhary, and Christine Largeron. All of the fairness for edge prediction with optimal transport. In Proc. International Conference Artificial Intelligence and Statistics (AISTATS), pp. 1774 1782, April 2021.
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In Proc. International Conference on Learning Representations (ICLR, April 2020.
Aishan Liu, Shiyu Tang, Xianglong Liu, Xinyun Chen, Lei Huang, Zhuozhuo Tu, Dawn Song, and Dacheng Tao. Towards defending multiple adversarial perturbations via gated batch normalization. arXiv preprint arXiv:2012.016:: 2020.
Andreas Loukas. How hard is to distinguish graphs with graph neural networks? Advances in Neural Information Processing Systems (NeurIPS), 33:3465 3476, December 2020.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks.
arXiv preprinl Xic:222006. 15535, 2021.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In Proc. International Conference on Learning Representations (ICLR), April 2018.
Felix L Opolka, Aaron Solomon, Cätälina Cangea, Petar Veličković, Pietro Liò, and R Devon Hj elm. Spatio- temporal deep graph infomax. arXiv preprint arXiv:1904.06316 April 2019.
Kirtan Padh, Diego Antognini, Emma Lejal-Glaude, Boi Faltings, and Claudiu Musat. Addressing fairness in classification with model-agnostic multi-objective algorithm. In Uncertainty in Artificial Intelligence (UAI), pp. 600-609, August 2021.
Tahleen Rahman, Bartlomicj Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), pp. 3289 3289-3295, August 2019.
13

---

Published in Transactions on Machine Learning Research (04/2023)
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances in Neural Information Processing Systems (NeurIPS), 29, December 2016.
Shibani Santurkar, Dimitris Tsipras, Andrew Tlyas, and Alcksander Madry. How does batch normalization help oplimization? Advances in Neural Information Processing Systems (NeurIPS), 31, December 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik chervonenkis dimension of graph and recursive neural networks. Newral Networks, 108:248-250, 2018.
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence, 2021.
Weiwei Sun, Wei Jiang, Eduard Trulls, Andrea Tagliasacchi, and Kwang Moo Yi. Acne: Attentive context normalization for robust cetnunttaioo-qquvvaiii learning. In Proc. IEEE/CVE Conference on Computer Vision and Pultern Recognition (CVPR), pp. 11286 11295, June 2020.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International Scientific Conference and International Workshop. 'Present Day Trends of Inmovations', volume 1, May 2012.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint (.Xi::6677080000 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proc. International Conference on Learning Representations (ICLR), April 2018.
Yuxin Wu and Kaiming He. Group normalization. In Proc. European conference on computer vision (ECCV), pp. 3-19, October 2018.
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization the transformer architecture. In Proc. International Conference on Machine Learning (ICML), pp. 10524 10533, July 2020.
Jingjing Xu, Xu Sun, Zhiyuan Zhang, Guangxiang Zhao, and Junyang Lin. Understanding and improving layer normalization. Advances in Neural Information Processing Systems, 32, 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. International Conference on Learning Representations (ICLR), April 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka, Representation learning on graphs with jumping knowledge networks. In Proc. International Conference on Machine Learning (ICML), pp. 5453 5462, July 2018b.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In Proc. International Conference on Learning Representations (ICLR), April 2019b.
Kwang Moo Yi, Eduard Trulls, Yuki Ono, Vincent Lepetit, Mathicu Salzmann, and Pascal Fua. Learning to find good correspondences. In Proc. IEEE Conference on Computer Vision and Patlern Recogration (CVPR), pp. 1666-2674, June 2018.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shen, and Tic- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems (NeurIPS), 34, December 2021.
14

---

Published in Transactions on Machine Learning Research (04/2023)
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proc. ACM International Conference on Knowledge Discovery & Data Mining (SIGKDD), pp. 974 983, July 2018.
Tao Yu, Zongyu Guo, Xin Jin, Shilin Wu, Zhibo Chen, Weiping Li, Zhizheng Zhang, and Sen Liu. Region normalization for image inpainting. In Proceedings of the AAAT conference on artificial intelligence, volume 34, pp. 12733 12740, 2020.
Ziqian Zeng, Rashidul Islam, Kamrun Naher Keya, James Foulds, Yanggiu Song, and Shimei Pan. Fair representation learning for heterogeneous information networks. ar preprint arXiv:2104, 018762004008769, 2021.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. International Conference on Learning Represenlations (ICLR), 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. Advances in newral information processing systems, 33: 4917-4928, 2020.
A Proof of Lemma 1
First, we present the following Lemma, as it will be utilized in the proof of Lemma
1
Lemma 2 (Cauchy Interlace Theorem, (Horn & Johnson, 2012)). Let A be Hermitian matrir of order N, and let. B be principal submatris of A of order N 1, such that A
B y RNNN If
y
AN & AN-1 ... & >2 m d lists the eigenvalues of A and YN & 7N-1 ... & & 12 the eigenvalues of
B, then:
AN EN & AN-1 & 7 A
(10)
where X; "/ only when there nonzero R N-1 such that Bz 7i and yT 0; is h; - then there is nonzero ze N-1 such that Bz 7-1Z, y 0.
The shift operations over different sensitive groups are defined to be:
MShift(W ( H) w (N
(11)
where N(n) = In 1S e (e) for n = 0,1. Let & À & & An be the singular values of Q Then, eigenvalues of (Q) Q are ((D))(((())) (Q) Q(()(()) NO (Q) (N("(()) Vi I.
Let of denote the eigenvalues of (N()) is projection matrix, for which the following holds:
A & & X
NO1)2 NON NONNNN NO)
(12)
as both (0) and N()) are symmetric projection matrices onto the orthogonal complement spaces of the subspaces spanned by ( and e(!), respectively, and (N(N()) commutes. Then, the following decompasition can be written: (N()))() U ddiag(1, I...., 1,,,,,,, where U
V Note that diag(a) creates diagonal matrix D e NNN with ith diagonal entry being equal to a, Va R. This decomposition implies that the eigenvalues corresponding to the
U Usudy ViSaT
(0)
15

---

Published in Transactions on Machine Learning Research (04/2023)
eigenvectors
(0)
are zero, which can be shown e
v
visi
N N(U) (0)
(IN
)
c ( (c
+ | | e (cl0)) To (o )c
|
|
[IN
1
())
SSs (c (c(1)) )o c ( and ell) are orthogonal,
1
|
(0)
(0))
(0)
| ( TT
(13)
|
S c
(e e0)) |S by definition,
[
(0)
The same analysis also holds for e()) Let TV and タ denote eigenvalues, and 0 7 hold. Based on the decomposition of (N N()), the following can written:
$75-2
(QQ) TQ(() N N T)
U diagg 1, 1, l........................... .,,. 1,0.0)U QU diag( 1, 1, .,.................... 1,0,0)UT
(14)
~ diag(1,
1,0,0) (Q) QU diag(1, 1, 1,000,
where A ~ B, if the cigenvalues of A and B are the same. Furthermore, denote diag 1, 1, 1....... 1,0,0) by
De NNNN
IN-2 [0]-2x2 [0]2x~22
(15)
[0]2x2
'
where (0 denotes an all-zeros matrix with dimensions i Let C denote Q QUQ. Q.
T (
DU CUD
U zub
(T
C C Unub
Viso (e
Visy (e()) JD
D
Visy (o(D)T
(16)
UT
sub CU sub
S UT
sub C(e
UT sub C(e
S
S0 (e CCUTTTCCAA
CU
(e T (o
Visi|s (e()) T Tell)
100
(c(1) TCU
sub sub
| (c())Te Cc
(c Ccl!)
1
U sub
CU sub
0 -222 0 2x
[0 2x N
As, (N() T (N(O)) C has the eigenvalues 0 -/ ... < </ and 7 = 7/ 0, equation
shows that T CU sud
sub E N-2N- has the eigenvalues < 77 & .... & 7:
Let R denote UT CU, then R has the eigenvalues 0 & X
& , R C.
sub CU aub
S UT sub (()
Vis sub C(e(t)
Visu (el0)) (UO))CUURI sub
SU (e(0) ()
(e(0)) (C
R
Vis
(17)
Visi (e (C))TCCC.. CU
SS () (o
(e (C
1
Further, define matrix A E --N-NN-- such that:
UT CU sub
SS UT C(e
A
Visy (e(0)
CU
100 (e(0) TC ())
(18)
16

---

Published in Transactions on Machine Learning Research (04/2023)
together with eigenvalues 7/1 ... & 1/N-1- Then, utilizing Lemma equation 17 and equation 18 conclude that
X < m < X2 < 722 & 1N < X
(19)
where = = the Xa 1 if and only if there is right singular vector of such that (c(1) 0.
The proof of the condition for X = T% or X2 7/ is presented below in italic.
Proof: Cauchy interlace theorem states that inequalities in equation 10 become equalities if there is nonzero z E RR-1 such that Bz 7i2 and y z = 0 or if there is a nonzero 2 E IR such that Bz = 74-12 and y z = 0. Therefore, for the result in equation E N-N-1 such that:
inequalities become equalities, if there is a nonzero
Az = 172 and
1 Visi (cl))
(Cl
CU sub
(
/
(c
Ce(o)
| |z= 0.
(20)
Note that dropped the subscript of n in equation the 1788 to turn one of the inequalities into equality in equation 19
20
it is enough to hold these conditions for anyy of
A
(e
C U
sub
(())
(21)
V |8q
Su
Let U1 =
Usub
(0)
where U1 forms an orthogonal basis for ell). Therefore, A = U.
Visu
The conditions presented in equation 20 can be rewritten based on this definition:
UTCU, and 1 T - VIS
(22)
The second condition in equation demonstrates that for inequalities in equation 19 become equalities, CU2 should lie the orthogonal complement space of e(t, which is spanned by U1. Therefore, if the second condition in equalion 22 is salisfied, there exists a vector b E RN-1 such that:
cU =
(23)
In this case, the first condition in equation 22
becomes:
U U, Llab-IN--i IN-ib
(24)
Therefore, the following equality should hold to meet both criterion in equation 20
CU U,b=-
(25)
equation 25 demonstrales that the conditions in equation 20 are mel, if U1Z is the eigenveclor of C Q Q associated with eigenvalue n7 This eigenvector Uiz lies in the orthogonal complement space of (0) and the eigenvector of C Q Q is the right singular vector of Q. Therefore, inequalities in equation 19 become a= = 0, which concludes the proof.
equalities, if there is a right singular vector a of Q such that (e(1))a a
A is created the following way:
sub U sub CU
UT sub C(e(())
So (e(0)) (e
A
Visyi (e(o) CU CuD
(26)
together with cigenvalues 171 & ... & NN-11 Furthermore, equation 16 shows that UT CU sub N-2NN22 has the eigenvalues 0 & 7 & ... & Rh- Again, we can apply Cauchy interlace theorem presented in Lemma 2 which concludes that:
m
12 & 1 . =
& IN-1,
(27)
where π7 72 or 1/ = 7, if and only if there is right singular vector a of Q such that (e(0)) a 0 and (e())Ta= For these conditions leading equalities πソ 7 or n, 72-10 the proof follows in the same manner as the previous one.
17

---

Published in Transactions on Machine Learning Research (04/2023)
Finally, by unifying the results of equation 19 and equation 27
the Theorem 1 can be proved, such that:
A < 71
(28)
X2 < 7/
(29)
AN-2 & 7N-2 & An
(30)
where X; N Av 7 only if Q have right singular vector such that (e!")) 0 and
(el)))a a = 0. Note that as and 7s are defined to be non-negative, thus we can omit the powers of 2 in the final result.
B Learning Environment and Proof for Theorem 1
We first introduce the following Lemma that will be utilized in the proof.
Lemma 3 (Theorem 1, (Cui et al. 2019)) Let ......, ~ E) be independent Gaussian vectors, where E is an F x F real posilive definile malrix. Let B be fixed symmelrii real N x N matria. Consider the compound Wishart matrix W -BXX /N with X = [T1...... event
[II....,NN]] xN]. Then for any d 2 0, the following
32 r + B 28
W EW
|
N
holds with probability at most 2 exp (-2 + 2F log 3), where for 8 /2,n
I- || denotes the Frobenius norm. Specifically,
32 p + 64
B
22
W EW
N
holds with probability at most 2 exxp (-82).
Model: For the node classification task over graph 9, linear onc-layer GNN-basod model is considered, where the models without and with individual shifts for different sensitive groups are denoted by feansila XX Q) w XQ and MMShift(X Q) w XQN(ON() respectively for Rx11 X e FRN and E GER.NA NNN
Training loss: Let vannilla e FxN and Z MShift e RPN denote XQ and XQN respectively. The training loss for both the models without and with individual shifts for different sensitive groups follows as:
I Z [(w) 2
(31)
where RV denotes the labels of the nodes. Note that this loss is applicable to both Z Zennlllo and Z MShift and Z used interchangeably with zeanilla for the ease of notation.
Optimization: Gradient descent is utilized for the optimization by initializing wo = 0, where an optimization step can be written as:
Wi+1 W. 7ZZZ w. Zy) (Ir r/ZZ w. + n2
(32)
Note that in Equation equation 32 denotes the learning rate.
In this setting, converges to optimal solution w* = (ZZ Zy according to the solution of least squares
problem Horn & Johnson 2012) where superscript denotes Moore-Penroe inverse. The residual of w follows as:
W *
(I, 7Z )w: + + - W
(IF 1/ZZ )w, + (ZZ ((ZZZ Zy w
(ZZ
(33)
(IF -1/ZZ' )w, (IF -7iZZ )w" as w ''y
(I, -1/Z )ww - w*).
18

---

Published in Transactions on Machine Learning Research (04/2023)
Assumption 1: Wo 0.
Based on Assumption and equation 33 following inequality can be written:
ww: w*1 < |[(I= n/ZZ [|]]
(34)
For the learning rate 77 = (ZZ ) the following convergence rate can be guaranteed for this problem:
w. w"1 $
(1
[ZZ 0 maz [ZZT)
0 min
||w"||
(35)
Note that Omin and men output the minimum and maximum positíve eigenvalues of the input matrix, respectively. The same result can also be derived for MShift following the same steps, such as:
minn (Z MShift T
Oman MSSafe ZZ MSHISE)T) ||: w²1 &
||w*/.
(36)
Equations equation 35 and equation 36 demonstrate that the convergence rates of the defined node classification problem for without and with shifts depend on the terms 1
Cmin (ZZ and
Tmna (ZZ
Cmin (Z (2
Omaz (2 (2 (2801111)) respectively. Therefore, the next step examines these factors together with the
following assumptions.
Assumption 2: x E R is a centered Gaussian random variable with covariance matrix Σ [x[xx ]. The features of nodes Xi....,XM, are independent realizations of x, where xx X = X1 xv]. XQ and Z MShift XQN(NN()
Assumption 3: E[XQ] := Y.
Assumption 0 < [QQ Y)
(XQ T
& 1
VN
VN
Assumption
XQ Y
N(W) (QQ Y)
J 8
VN
VN
Assumption 6: Defined Y matrix is full rank.
We will analyze the eigenvalues of N zz as multiplying with a constant does not change the ratio wetw the minimum and maximum eigenvalues.
N
Zz
T
Σ
z,z
(37)
N
N
For the analysis of Zz", will first focus E
zz
which equals to:
NV
ZZ T
XQ
XQ
N
VN
N
(38)
YYT
XQ
Y) [QQ Y) T
E
VN
VN
based on the Assumption 3. inequalities can be written:
By utilizing Weyl's inequality and the provided assumptions, following
YYT
ZZ
YYT
Omazl
E oman (E
E Omaal
+ 81
N
(39)
YYT
ZZ
YYT
T Omin
& Ominn (E
& o min
+ 8
N
N
19

---

Published in Transactions on Machine Learning Research (04/2023)
Similarly:
Z
M (SMSH
XQN( (XQNONU)
E
N
VN
V
XQ
(XQ)
as O O commutes,
E
VN
(40)
XQ
(XQ)
as N (()) a projection matrix
VN
N
N XQQ Y) (XQ
N
VN
VN
Again, by utilizing Weyl's incquality and the provided assumptions, following incqualities can be written for the shifted case:
N
Z MShift IZ MShifteT
YN
Y
O mma
E mma (E
0 Omaa!
N
N
N ( YT
(41)
YNO
N
Y
Z ZASSifft (ZM))i)))
min
Uiin (E
minl
+
N
N
Next step in the proof is bounding the errors ||
TZT
E
zz N
|12 and I MMSS (ZMSSiiIT
(rsseey 2a. Based on Lemma 3 and assumption
E
the following inequality holds with
probability 1 6, where 2 for errors | ZZ
E
zz N
I|l and || 1/ (7
Mahil (ZMShingT
E
12:
ZZ
log(2/e)
ZZ T
E
(42)
N
N
where the constants QQQ F. QQQ 1g and EE|₂ are hidden in O(-) notation for focus N similar to the approach taken in Cai et al. (202)). Similarly, the following bound holds for | (Shift MShiftt (2 Mahhffy
E
2 with probability e, where 3:
Z MShift ( MShifttT - Z MShift Z M
(og((/c)
S
(43)
N
N
Based on Lemma can be ro-organized. Following incqualities hold with probability where 2.
Equations equation 42 and equation 43
the inequalities in equation 39 and equation
YYT
(og(2/e) N
ZZ
YYT
log(22ee)
Omaz
o
Tmaz
T mmaz
+ o1 +
N
N
(44)
YYT
(log(2/e)
ZZ T
YYT
(og((2/e)
Tmin
& Omin
& o Omin
+ + + +
N
N
N
20

---

Published in Transactions on Machine Learning Research (04/2023)
Y
(log(2/e)
man
O
& maall
Z
M M.Safft (M (MMShifttT)
N
N
N
YNO Y
(lgg(2/c)
maax!
+1
N
N
(45)
N
(og((2/))
M MShift (Z (Z
mmin
< Omin
N
N
YNO N
(og(2//))
$ Omin
51 O
N
N
By the same method that proves Theorem and is presented in Appendix A it can be shown that positive eigenvalues of NOOT are interlaced between the positive eigenvalues of YYT:
min (YYT)= & min (YN & man (YN(O & maz (YYT)
(46)
where inequalities become equalities, only there is a right singular vector a of Y that is orthogonal both e( and e11)
Assumption 7: None of the right singular vector of Y is orthogonal to both e and e
Based on Assumption 7 and result in equation 46
following holds:
YN
(1)) Y
YN Y
YY
mmin
N
mmin
N
o maaa
N
max
N
(47)
Finally, for small enough ò1 and large enough N with probability 1-e with e² the following inequalities be written:
YYT
+ 61 + ( (0g((2/))
Omin
zZ N
& a mina
N
N
YNON
- (o0((/c))
mmin
N
N
M (ZMSHiSTT)
MShift
mmin
o mea
Z
MSRiSt ( MSNiS)T
(48)
YNONUYT
(10((/()
mmax
) ) 81 +
N
N
YYT
[og((//c)
Tmax
N
N
E T mma
ZZ
N
Therefore, equation 48 proves that 1- Ommnn (ZZ"
1 Gmann MShsf1 (2 MSsMsfty
Omaux 7 Mrsh (2
with probability 1-
(Frcozz
Unifying this result: with Equations equation 35 and equation 36 concludes that shifted model by matrices
NG) converges faster compared to the vanilla model with high probability the considered learning environment for node classification.
C Proof of Theorem 2
Define the sample mean after normalization layer by (m) RF 0. 1. Then,
21

---

Published in Transactions on Machine Learning Research (04/2023)
at [0) - -1 = |
Σ
h
(0)
Σ
h 1
|S
JESP
JES
(49)
[1x10) - 1 10 = ||
Σ
Act(
(0))
Σ
Act(h) ( 1112
|S
|S
JES0
JESt
We can write b/ (0 + , Vj = 1.....111111 1.1 and 6n" v()) + 85 Vj 11...18') If the activation
function Act() Lipschitz continuous with Lipschitz constant I. (applies to several nonlinear activations, such as rectified linear unit (ReLU), sigmoid), the following holds:
) | & ) = Act(a, (0) + 610))
< Act( ) + 1 |, Vi I.... Act(H (0) + )
(50)
) > {cc(()))
x Act(pi (0) L 11 V. 10
where ||| takes the element-wiss absolute value of the input. The same inequalities can also be written for St:
))) - < (ht - Act( + ) & Act(z(()) + 1,5
(51)
= 1..-
Based on Equations equation 49
equation 50
and equation 51
following holds:
Σ
Act((z(0) (0)) 1118511)
Σ
(Act(z(4)) + 1155"1) < (0) 22
|
SS
jesa
jeSt
(52)
(c) + 1/1500)
Σ
(Act(T²)) - I115111
|q
|S
jESO
JESL
Act( (ct(z((1)
1
1
< <x (1()
50
S1
jES
jESI
(53)
x (0)
Act((p
1
L
(0)
1
Σ L(5
S0
|S
jESO
jESt
Define a == ()) - (1)
EjEso 410
Σ jes 4(85") and = (c)( (Ac((((()) +
J
S
E Jo | + [TT Yjes Z15/11. Equation equation
53
leads to:
1n (
m 11 max([a;),1b1))) Vi I,... F.
(54)
If we consider the case, |a,| > |b,]. Then:
1m(0) - 11 < Act(H(() - Act(H(")
1
Σ
Σ 410911
SU
SS
jESD
JES
< )c)( - AcI(T("))
1
Σ
Σ
(55)
+
100
|
JESO
JESt
< ))) - AcI(TT
| (0)
+ L A (1)
+
22

---

Published in Transactions on Machine Learning Research (04/2023)
where 4.00 : max; 16), and A.T == max, 10
Consider the term Act(zt") Act((ig)):
) Act(a!!) Act(RE (0) (1) - -m Act(a(").
(56)
Utilizzin Equations equation 50 and equation 51 Act(Mi (0) + +m (1) ) -AAct(a)))) can be bounded by below and above:
Act(p(") T.1 p. 1 Act(T! Ac (0)
+ (1) -m(()) - Act(T(
(57)
< Act( (11) + Li Lipi (0) - - - -Act(ze
- -1/ 1 < Act( (0)
+ (1) p - Act((u (1) & LI (0) -m!"))
(58)
Ac((T - (
& -| m 1
(59)
Therefore:
|mg 1 L 11 T. A (0)
+ I. | vi such that |ay| lbd]-
(60)
Next step is to consider the case, |a:1 < |b:/. For this case, following inequalities hold:
10,0) 1110 )ct((( Act(x(") +
1,
1
ا
S
jESD
jES
< ) Ac((T(
1
Σ
Σ
(61)
S0
|
JE
JESL
Ac (z( ()(
+ L
A (0)
L
T (0) - /ل + T. A
+ T.
A (1)
vi such that |ad| > 1b/].
Combining Equations equation 60 and equation 61
the following inequality can be written:
1
(0)
(1) L nt + L A (0)
A Vi = I.....F. F.
L
(62)
which concludes:
( (0) - 1| < L (1 - 1 + +IĀ (0)
+ IA
(63)
D Hyperparameters
We provide the selected hyperparameter values for the GNN model and the proposed framework for the reproducibility of the presented results. In the GaNebased classifier, weights are initialized utilizing Glorot initialization (Glorot & Bengio 2010). All models are trained for 1000 epochs by employing Adam optimizer [Kingma Ba [014g together with a learning rate of 10-3 and l weight decay factor of 10-5, A 2-layer GCN network followed by linear layer employed for node classification. Hidden dimension of the node representations is selected as 64 on all datasets.
The results for bascline schemes, covariance, adversarial, HTRDDP regularizers, and FairGNN (Dai & Wang 2021) are obtained by choosing corresponding hyperparameters (the multiplying factors for these regularizers in the overall loss) via grid search on vrossvvaliaation sets with 5 different data splits. Specifically, a grid search on the values 10", 1010 10t is exccuted for covariance-based regularizer. Furthermore, the values 0.01, 0.1, 1.10 are examined as the multiplier for adversarial regularizer. FairGNN employs both covariance- based and adversarial regularizers, therefore its parameter selection is the unification of the previous two
23

---

Published in Transactions on Machine Learning Research (04/2023)
hyperparameter selection methods. Finally, the parameters 0.01, 0,1, are examined for the HTRDDP regularizer.
Hyperparameter values for the proposed FairNorm whose results are presented in Section 5.2 can be found in Table 6 Note that the candidate hyperparameter values for T and K are selected to balance the significance of Le Lu. and LA in equation g in terms of order of magnitude, so that each component has non-negligible yet non-dominant effect. These parameters are selected via grid search on cross- valss-aaliotioon sets over different data splits. The range of the parameters are selected based on the corresponding loss terms. Specifically, the values 10, 100, 1000 values examined for in Pokec networks, and the values 0.01, 0.1, 1 values are examined for k in Recidivism network. After the sclection of best и value, the T is selected together with the fixed, best value. While the values 10-7, 10-*, 10-9, 10-10 values are examined for т in Pokec networks, the values 10 8 10 10100-0 10 10 values are examined for x. in Recidivism network
Table 6: Utilized wn and values for the presented results in Table
ReLU
Pokeo-z
Pokec-n
Recidivism
k/T
100/10-7
1000/10-9
0.01/10-10
Sigmoid
Pokeo-z
Pokec-n
Recidivism
8/T 10/10-7
100/10-8
0.01 0.01/10-10
E Experimental Results for GraphSAGE
In order to demonstrate the flexibility of the proposed scheme for different GNN models, we provide further experimental results herein for GraphSAGE operators proposed in Hamilton et al. (201b)) together with mean aggregation. The obtained results for node classification on Pokec networks and the Recidivism graph with ReLU activation are presented in Table 7 The results in Table Tablei/onfirmm the efficacy of FairNorm also for the GraphSAGEE-aase to other fairness-awer aware baselines together with similar utility. Note that the hyperparameters for this set of experiments are selected in the same way that is described in Appendix D
experimert
GNN, since FairNorm still achieves better or similar fairness measures compared
Table 7: Comparative Results for GraphSAGE with ReLU activation
Polec-z
Pokec-n
Recidivism
(%)
Asp (%)
Ago (%)
(%t
Agp (%)
Ag)(%)
(%)
Agp (%)
Ago (%)
NoNorm
0.8
5.32 1 1.1
0.6
2.60
1.76 1.6
97.93 : 0.1
9.37
M-Norm
69.94 i 0.5
2.82 + 1.7
3.52 + 1.6
68.96 1 0.9
2.45
1.8
1.82 1 1.5
99.01 1 0.1
9.26 1 0.7
0.56 0.2
Covariance
69.95 :: 0.7
3.30 2.0 2.0
3.41
+: 2.2
69.61
0.6
3.26
1.7
2.16 1.4
98.68
= 0.2
9.21 + 0.9
0.74 4 0.5
Adversarial
68.99 1.0
1.94 1.6
1.97
1.6
68.94
1 1.0
3.24 1
2.43
1 2.0
98.85
0.1
9.1
0.73
1 0.6
FsieGNN
68.92 t 1.1
2.79 1.4
2.12
1.5
68.99
1 0.9
2.96
1 2.3
2.12 1.4
98.5
0.1
9.36 0.6
0.66 0.5
HTROOP
70.16
0.5
2.51 + 1.7
2.90 + 1.8
69.35
+ 1.9
2.94
1.66 + 1.2
98.98 98
0.1
0.36
0.56 0.1
FairNorm
69.50 1 0.5
1.37 i 1.5
2.00 :: 1.9
69.05 1
2.38 1.3
1.30 0.6
98.96 = 0.1
9.01 0.8
0.55 0.6
F Validation Accuracy Curves
Figure has already shown that FairNorm can achieve faster convergence in training compared to the framework where no normalization is employed. Figure 2 is provided hercin to demonstrate the validation accuracy over 1000 epochs for the case where normalization is not employed, Graph Cai et al. (2021), and our framework FairNorm. Note that models that achieve the best validation accuracy are utilized obtain the test set performances listed in Table 2 The curves in Figure further signify that FairNorm and GraphNorm can converge to the model with the best validation set accuracy faster compared to the scheme that does not use normalization.
24

---

Published in Transactions on Machine Learning Research (04/2023)
Cres
Graphlorm
CrasWamm
(a) Pokec-n (ReLU)
(b) Pokec-z (ReLU)
(c) Recidivism (ReLU)
Grophterr
(d) Pokec-n (Sigmoid)
(e) Pokec-z (Sigmoid)
(f) Recidivism (Sigmoid)
Figure 2: Validation curves for different graph data sets when the normalization is not applied (Nonorm)
and applied with with/without fairness considcration HaanNorm/GraphNonyyn
25


Reviews:
[{"review_id": "nYG1AOMiYI", "reviewer": "Reviewer_njwj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The idea of the paper is clear and novel. Based on the normalization structure which improves the convergence and stability of GNNs, this paper further introduces the fairness concern into the problem. The paper is well-organized. \nWeaknesses: Although the author claimed that the proposed framework is the first attempt to improve fairness and convergence speed in a unified framework, the work seems to simply combine normalization and fairness together. The regularizer is not related to any well-known fairness metrics, e.g. demographic parity or equalized opportunity. In my opinion, proposing a new fairness measure and using it as a regularizer in the objective function is not novel enough without demonstrating the relationship between this measure and other well-known fairness metrics. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "A new framework is proposed to reduce bias while providing a higher convergence speed in the GNN-based learning scheme. To achieve the fairness guarantee based on the normalization framework, a fairness-aware regularizer is introduced on the trainable parameters of the normalization layers. Empirical results are provided. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the following questions: \n1. In the objective function (8), why do you introduce two trade-off parameters with respect to $\\mathcal{L}_{\\mu}$ and $\\mathcal{L}_{\\Delta}$ respectively? Is there any theoretical reason? I am curious about this formulation because according to the results in Theorem 2, the mean bias term and the deviation term seem to have the same importance for bounding the distance between sample means of two groups. \n2. As mentioned at the beginning of Section 4.1,  Li et al. (2020); Kose & Shen (2022) demonstrate that decreasing $\\|\\mu^{0}-\\mu^{1}\\|$ and $\\Delta$ can effectively reduce bias in GNN-based learning, the results in the paper only analyze the term about mean sample difference ($\\|\\mu^{0}-\\mu^{1}\\|$). Then what about $\\Delta$? How can we reduce $\\Delta$ in the framework? Will reducing $\\|\\mu^{0}-\\mu^{1}\\|$ cause a smaller $\\Delta$? ", "broader_impact_concerns": "No concern on the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yFNxS1BpKr", "reviewer": "Reviewer_5jyf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The group-wise normalization over different sensitive groups is novel and seems promising.\n- The authors provide solid theoretical analyses to support their proposal.\n- Remark 1 and 2 shows the flexibility and applicability of their regularizers.\n\nWeaknesses:\n- Fig. 1 only show the training accuracy curves. It would be better to also include validation/test curves to show there is no overfitting.\n- In Tab. 3 and 4, $\\tau$ is set to very small values (1e-7 to 1e-9), and adjusting it has marginal impacts. Could the authors explain why does $L_\\Delta$ has such small weights? And is it really significant to the result?\n- In Tab. 3 and 4, the value $\\kappa$ varies a lot when using different network. This is also a minor drawback, because when generalizing the proposed method to other networks, a lot of fine-tuning of hyper-parameters may be demanded.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes FairNorm, which introduces individual normalization operators and fairness regularizers into their framework for GNN-based graph learning. It aims to reduce bias and improve the speed of convergence. Experiments are performed on node classification tasks to empirically evaluate the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please fix issues mentioned in “weaknesses”.", "broader_impact_concerns": "No concern on the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bX6ypG7k4p", "reviewer": "Reviewer_jZmj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper is well-organized and well-written.\n* Sufficient theoretical analysis based on proposed method\n* The evaluation is conducted on various datasets, and the proposed method shows better performance than other baselines.\n\nWeakness:\n\n* The theoretical analysis in Theorem 1 is similar to the one in [a]. Since the shift operation in GNNs is proposed in [a] which leads to the convergence advantage, it would be better for the authors to compare or discuss the relationship between group-wise shifts and the one in [a] instead of the one without shift in Theorem 1.\n* The proposed method is evaluated on a tiny GCN model. It would be better for the authors to provide more evaluation results on different GNN models.\n\n\n[a]. GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training. ICML 2021.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims at the bias problem in Graph Neural Networks (GNNs) and introduce a group-wise normalization to improve the fairness. Specifically, the authors propose to apply normalizations to different sensitive groups individually and include shift operations in groups to improve convergence speed. To further improve fairness, the authors introduce fairness-aware regularizers via the upper bound of difference between mean representations of different sensitive groups. Additionally, the authors provide theoretical analysis on the convergence and regularizers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions:\n\n1. Please discuss the relationship between graph norm and fair norm in Theorem 1.\n2. Please provide more results on different GNN models.\n\nMinors：\n1. Some definitions of notations are missing, e.g., F in the feature matrices.\n2. Add bold to highlight the best results and settings in Table 3 and Table 4.\n\nMissing reference:\n\nThere exists relevant works which discuss the normalization layers and stability.\n\n[1]. Understanding and Improving Layer Normalization.\n\n[2]. Towards Stable and Robust AdderNets.\n\n[3]. Delving Into the Estimation Shift of Batch Normalization in a Network.\n\n[4]. Learning graph normalization for graph neural networks.\n", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XMQlX4VADz", "reviewer": "Reviewer_YEuY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**  \n1. The motivation of this paper is very clear. Based on the previous research progresses that normalization can improve the convergence and stability of GNNs, this paper further addresses the fairness scenarios of GNNs, and designs FairNorm to improve the training stability and fairness of GNNs. It is clear that the proposed method can obtain good performance.   \n2. This paper is well written and I am glad to read it. \n\n**Weaknesses:**  \n\n1. The techniqual contribution of this paper is somewhat incremental. This paper is a typic A+B paper，where A is that normalization can accelerate the convergence (and preventing the over-smooth problem of GNN) and B is that the fairness-aware regularization can improve the fairness of the GNN. This paper thus proposes the framework that combining normalization and fairness.  I recognize that this paper extends Cai et al (2021) by using group-wise normalization, and extends Li et al (2020); Kose&Shen (2022) by considering the normalization operation. However, the following points make me feel the contributions are incremental and should be further amplified:  \n(1)\tThe Lemma 1 and Theorem 1 is a straightforward extension from Li et al 2020. Furthermore, when I compare the corresponding content of Li et al (2020) and this paper, I find over-much overlap in description between them. I think it is better to re-organize/reword (even just only cite Li et al (2020)) this part (Lemma 1 and Theorem 1).   \n(2)\tThe main extension of this paper over Li et al (2020) is that it normalizes different sensitive attributions independently. The similar idea using normalization has been proposed extensively in previous work for different scenarios (See weakness 2), I think this paper should discuss these papers in “related work” section.\n\n2. This paper misses some closely related papers [1][2][3][4][5]. In terms of the normalization for GNN, there exists at least two related work [1]and [2]; In terms of normalizing over different groups (e.g, domains), there are a bunch of papers, e.g., for domain adaptation[3], for adversarial robust[4], for image inpainting[5]. I suggest the authors refer to the normalization survey paper [6] for an overall picture. \n\n3. I think section 3.1 is somewhat redundant to the “Normalization” paragraph in Section 2. I believe section 3.1 should provide the technical details of the main normalization for GNNs (including the mathematical notation and main formulation). \n\nOther minor:  What is $r_{i,j}^{(n)}$ in page 6?\n\n\nCitation:  \n[1]Towards Deeper Graph Neural Networks with Differentiable Group Normalization, Neurips 2020  \n[2]PairNorm: Tackling Oversmoothing in GNNs. ICLR, 2020  \n[3] Domain-Specific Batch Normalization for Unsupervised Domain Adaptation. CVPR, 2019  \n[4] Towards Defending Multiple Adversarial Perturbations via Gated Batch Normalization. arXiv:2012.01654, 2020  \n[5] Region Normalization for Image Inpainting. AAAI, 2020  \n[6] Normalization Techniques in Training DNNs: Methodology, Analysis and Application. arXiv:2009.12836, 2020.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes FairNorm for reducing the bias in GNN-based learning while simultaneously providing faster convergence. FairNorm addresses to normalize each different sensitive group individually and introduces fairness regularizes on the learnable parameters of normalization layers to reduce the bias in GNNs. The technical properties of FairNorm for improving the convergence and reducing the bias are derived, based on the previous research progress in normalization and fairness learning of GNNs. Experimental results also empirically support the effectiveness of the proposed method for improving fairness and convergence speed of GNNs. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.More discussion to related works  \n2.Better to re-organize/reword Lemma 1 and Theorem 1, in case of over-much overlap in description, compared to Cai et al (2021)", "broader_impact_concerns": "No impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel method called FairNorm, which addresses the bias problem in GNN-based learning and simultaneously provides faster convergence. FairNorm introduces group-wise normalization to normalize each different sensitive group individually and proposes fairness-aware regularizers via the upper bound of the difference between mean representations of different sensitive groups.  The authors have addressed all the reviewer's concerns during the review process. 
Decision: Accept (poster)