Topology Matters in Fair Graph Learning: a Theoretical Pilot Study
Authors: Zhimeng Jiang
Xiaotian Han
Chao Fan
Zirui Liu
Xiao Huang
Na Zou
Ali Mostafavi
Xia Hu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Fairness
Topology

Abstract: Recent advances in fair graph learning observe that graph neural networks (GNNs) further amplify prediction bias compared with multilayer perception (MLP), while the reason behind this is unknown. In this paper, we conduct a theoretical analysis of the bias amplification mechanism in GNNs. This is a challenging task since GNNs are difficult to be interpreted, and real-world networks are complex. To bridge the gap, we theoretically and experimentally demonstrate that aggregation operation in representative GNNs accumulates bias in node representation due to topology bias induced by graph topology. We provide a sufficient condition identifying the statistical information of graph data, so that graph aggregation enhances prediction bias in GNNs. 
 Motivated by this data-centric finding, we propose a fair graph refinement algorithm, named \textit{FairGR}, to rewire graph topology to reduce sensitive homophily coefficient while preserving useful graph topology. Experiments on node classification tasks demonstrate that \textit{FairGR} can mitigate the prediction bias with comparable performance on three real-world datasets. Additionally, \textit{FairGR} is compatible with many state-of-the-art methods, such as adding regularization, adversarial debiasing, and Fair mixup via refining graph topology. Therefore, \textit{FairGR} is a plug-in fairness method and can be adapted to improve existing fair graph learning strategies. 

Recent advances in fair graph learning observe that graph neural networks (GNNs) further amplify prediction bias compared with multilayer perception (MLP), while the reason behind this is unknown. In this paper, we conduct a theoretical analysis of the bias amplification mechanism in GNNs. This is a challenging task since Under review as a conference paper at ICLR 2023
TOPOLOGY MATTERS IN FAIR GRAPH LEARNING: A THEORETICAL PILOT STUDY
Anonymous authors Paper under double-blind review
ABSTRACT
GNNs are difficult to be interpreted, and real-world networks are complex. To bridge the gap, we theoretically and experimentally demonstrate that aggregation operation in representative GNNs accumulates bias in node representation due to topology bias induced by graph topology. We provide a sufficient condition identifying the statistical information of graph data, that graph aggregation enhances prediction bias in GNNs. Motivated by this data-centric finding, we propose fair graph refinement algorithm, named FairGR, to rewire graph topology to reduce sensitive homophily coefficient while preserving useful graph topology. Experiments on node classification tasks demonstrate that FairGR can mitigate the prediction bias with comparable performance on three real-world datasets. Additionally, FairGR is compatible with many vate-of-the-an methods, such as adding regularization, adversarial debiasing, and Fair mixup via refining graph topology. Therefore, FairGR is plug-in fairness method and can be adapted improve existing fair graph learning strategies.
INTRODUCTION
Graph neural networks (GNNs) Kipf & Welling. 2017 Veličković et al. 2018 Wu et al. 2019) are widely adopted in various domains, such as social media mining (Hamilton et al. 2017). knowledge graph (Hamaguchi et al. 2017) and recommender system (Ying et al.) 2018), due to remarkable performance in learning representations. Graph learning, a topic with growing popularity, aims to learn node representation containing both topological and attribute information in given graph. Despite the outstanding performance in various tasks, GNNs still inherit or even amplify societal bias from input graph data (Dai & Wang (02I). The biased node representation largely limits the application of GNNs in many high-stake tasks, such as job hunting (Mehrabi et al. (022)) and crime ratio prediction (Suresh & Guttag, 2019). Hence, bias mitigation that facilitates the research fair GNNs is in urgent need.
In many real-world graphs, nodes with the same sensitive attribute (e.g., ages) are more likely to connect. For example, young people mainly make friends with people of similar ages (Dong et al. 2016). We call this phenomenon "topology bias". Even worse, in GNNs, the representation of each node is learned by aggregating the representations of its neighbors. Thus, nodes with the same sensitive attributes will be more similar after the aggregation. To get sense, we visualize the topology bias for three real-world datasets (Pokec-n, Pokec-z, and NBA) in Figure where different edge types are highlighted with different colors for the top-3 largest connected components original graphs. Such topology bias leads to more similar node representation for those nodes with the same sensitive attribute, which is a major source the graph representation bias.
Existing bias mitigation work for GNNs is empirical via adding regularization. adversarial debiasing, or contrastive learning. These works are motivated by the fact that graph neural networks trained on graphs may inherit the societal bias in data, and the topology of graphs and the message passing in GNNs could even magnify the bias compared with multilayer perception (MLP) (Dai & Wang 2021). However, even though fair prediction in GNN be achieved via fair training strategy,

---

Under review as a conference paper at ICLR 2023
Pokec
Pokec
NBA
Different
Same
Visualization of topology bias in three real-world datasets, where black edges - and red edges -- represent the edge with the same or different sensitive attributes for the connected node pair, respectively. We visualize the largest three connected components for each dataset. It is obvious that the sensitive homophily coefficients (the ratio of homo edges) are high in practice, i.e., 95.30%, 95.06%. and 72.37% for Pokec-n, Pokec-z, and NBA dataset, respectively.
Figure 1:
fundamental understanding of why large topology bias and message passing algorithm amplifying the bias happens still missing. A natural question raised:
Can we theoretically understand why large topology bias and message passing algorithm amplify the bias from a graph data perspective?
In this work, we move the first step to understand why large topology bias and message passing algorithm amplify the bias. Specifically, first define the sensitive homophily coefficient to describe how likely the connected nodes are with the same sensitive attributes. Subsequently, we theoretically prove that the GCN-liK Like aggregation message passing inevitably accumulates representation bias for graphs with large sensitive homophily coefficients. Second, motivated by our theoretical analysis, we develop fair graph refinement algorithm, named FairGR, achieve fair GNN prediction via revising graph topology. More importantly. FairGR is plug-in data refinement method and compatible with many fair training strategies, such as regularization, adversarial debiasing, and Fair mixup. In short, the contributions can be summarized as follows:
To best of our knowledge, it is the first paper to theoretically investigate why GCN-like message passing scheme amplifies representation bias for large topology bias. Specifically, we provide a sufficient condition of graph data to show that GCN-like message passing amplifies representation bias.
Motivated by our theoretical analysis, we propose a graph topology refinement method, named FairGR, to achieve fair prediction.
We empirically show that the prediction bias of GNNs is larger than that of MLP real-world datasets. Additionally, the effectiveness of FairGR is experimentally evaluated on three real-world datasets. The results show that compared the state-of-the-art, our FairGR exhibits a superior trade-off between prediction performance and fairesss and is compatible with many fair training strategies, such as regularization, adversarial debiasing, and Fair mixup.
PRELIMINARIES
2.1 NOTATIONS
We adopt bold upper-case letters to denote matrices such as X, bold lower-case letters such as x to denote vectors or random variables, and calligraphic font such X' to denote set. Given matrix X E I the i-th row and j-th column are denoted as X; and X and the element in i-th row and j-th column is Xi.j. We use I norm of matrix X as |X|||
Eis |Xij) Let G = [V.E}
be graph with the node set V {v1,"* ... vn} and the undirected edge set E (-,, em) em
2

---

Under review as a conference paper at ICLR 2023
where n, represent the number of node and edge. respectively. The graph structure can be represented as an adjacent matrix A E R=X*, where A.j = if existing edge between node i, and node uy. (i) denotes the neighbors of node v, and (i)) = (i)) U {vi} denotes the self-inclusive neighbors. Suppose that each node associated with a d-dimensional feature vector and a (binary) sensitive attribute, the feature for all nodes and sensitive attribute is denoted as Xori = Rnxd and
s E {-1, 1)". [(s, represents the mutual information between the sensitive attribute and node
features. A @ B represents Hadamard product for matrix element-wise multiplication.
2.2 LABEL AND SENSITIVE HOMOPHILY COEFFICIENT IN GRAPHS
The behaviors of graph neural networks have been investigated in the context of label homophily for connected node pairs in graphs (Ma et al. 2021). Label homophily in graphs is typically defined to characterize the similarity of connected node labels in graphs. Here, similar node pair means that the connected nodes share the same label. From the perspective of fairness, we also define the sensitive homophily coefficient to represent the sensitive attribute similarity among connected node pairs. Informally, the coefficients for label homophily and sensitive homophily are defined as the fraction of the edges connecting the nodes of the same class label and sensitive attributes in graph Ma et al. 2021) I. We also provide the formal definition as follows:
(Zhu al. 2020
Definition (Label and Sensitive Homophily Coefficient) Given a graph G = ( E with node label vector y. node sensitive attribute vector the label and sensitive attribute homophily coefficients are defined as the fraction of edges that connect nodes with the same labels or sensitive altributes éjabet y) उी E(i.)ee 11 (y: = =Yj), and (s = TET Eiisee 1(s =s)), where {ε| is
the number of edges and 1() is the indicator function.
Recent works (Ma al., 202T Chien al. 2021 et 2020) aim understand the relation between the message passing in GNNs and label homophily from the interactions between GNNs (model) and graph topology (data). For graph data with high label homophily coefficient, existing works (Ma et al. 202T Tang et al. 2020) have demonstrated, either provably or empirically, that the nodes with higher node degree obtain more prediction benefits in GCN, compared to the benefits that peripheral nodes obtain. As for graph data with a low label homophily coefficient, GNNs do not necessarily lead to better prediction performance compared with MLP since the node features of neighbors with different labels contaminate the node features during feature aggregation. However, although work (Dai & Wang (02T)) empirically points out that graph data with a large sensitive homophily coefficient may enhance bias in GNNs, the fundamental understanding of message passing and graph data properties, such as sensitive homophily coefficient, is still missing. We provide the theoretical analysis in Section
3 RELATED WORK
We briefly review the existing work on graph neural networks and fairness-aware learning graphs. (Please refer to Appendix [ for a more comprehensive discussion.). Existing GNNs can be roughly divided into spectral-based and spatial-based GNNs. Spectral-based GNNs provide graph convolution definition based on graph theory (Bruna et al.] 2013 Defferrard et al. 2016 Henaff et al.) 2015). Spatial-based GNNs variant are popular due to explicit neighbors' information aggregation, inc including Graph convolutional networks (GCN) (Kipf & Welling 2017). graph attention network (GAT) (Veličković et al. 2018). As for fairness in graph data, many works have been developed to achieve fairness in machine learning community (Chuang & Mrouch 2020). including fair walk (Rahman et al. 2019) adversarial debiasing (Dai & Wang 2021), Bayesian approach (Buyl & De Bie 2020), and contrastive learning (Agarwal et al. 2001). Much literature empirically shows that GNN or message passing may enhance prediction bias compared with MLP. However, the theoretical understanding of why such phenomenon happens is still unclear. In this work, we take initial step toward theoretically understanding why message passing enhances bias from a data perspective. Based on this understanding, we develop a simple yet effective fair graph refinement method to achieve better tradeoff performance. More importantly, the proposed FairGR is compatible with many fair training strategies.
3

---

Under review as a conference paper at ICLR 2023
4 TOPOLOGY ENHANCES BIAS IN GNNS AGGREGATION
For each node, GNNs aggregate their neighbors' features to Iearn their representation. In real-world datasets, we observe high sensitive homophily coefficient (which is even higher than the label homophily coefficient). However, existing features from their neighbors with the same sensitive attributes. Thus, the common belief is that the message passing renders node representations with the same sensitive attribute more similar. However, this common belief is heuristic and the quantifiable relationship between the topology bias and representation bias is still missing. In this section, (1) we rectify such common belief and guantitatively reveal that only sufficient high sensitive homophily coefficient would lead to bias enbancement; (2) we analyze the influence of other graphs statistical information, such as the number of nodes n, the edge density pa, and sensitive group ratio c, in term of bias enhancement.
schemes tend to aggregate the node
4.1 SYNTHETIC GRAPH
we consider the synthetic random graph generation using contextual stochastic block model (CSBM) (Fortunato Hrie| 2016), including graph topology and node features generation with Gaussian mixture distribution. As pilot study, we choose the most common-used graph topology with stochastic block model (SBM) and node feature with Gaussian mixture distributions in the analysis.
The rationale for the choice is due to the fact that SBM is widely used to model and analyze most complex networks (e.g., social networks, World Wide Web, and biological networks) Van
Der Hofstad 2016
Graph Topology Throughout our analysis, we mainly focus on 4 characteristics of graph topology: the number of nodes n, the edge density Pa. sensitive homophily coefficient <sens, and sensitive group ratio c. Specifically, we consider the synthetic random graph generation, including graph topology and node features generation follows:
Definition (n, Pd, Ezene, Caene, c)rppp)) The synthetic random graph G sampled from (n. Pd: Eeeney e)- graph satisfies the following properties: 1) the graph node number is n; 2) the adjacency matrix A satisfies Aij E [0,1} and E.y (P(j = 1)] = Pad 3) given connected node pair Ai = 1, the probability of connected nodes with the same sensitive attribute satisfies P(s, s Sj = Csensi
4) the binary sensitive attribute 8; E [11, satisfies E, [P(s: = 1)] = c; 5) independent edge generation.
Node Features. We assume that node attributes in synthetic graph follow Gaussian Mixture Model GMM Ul. E1, Ez). For the node with sensitive attribute s 1 (sj = 1), the node attributes X; follow Gaussian distribution Pi = Ni,,, )) (P2 = Nuu,, , E2)), )). where the node attributes with the same sensitive attribute are independent and identically distributed, and μr, Eg (i 1,2)
represent the mean vector and covariance matrix.
4.2 REPRESENTATION BIAS MEASUREMENT
To measure the node representations bias, we adopt the mutual information between sensitive attribute and node attributes [ss, X). Note that the exact mutual information I(s, X) is intractable to estimate, an upper bound on the exact mutual information developed as a surrogate metric in the following Theorem
Theorem Suppose the synthetic graph node attribute X generated based on Gaussian Mixture Model GM (c, pl. Σ1, Σ2), i.e., the probability density function of node attributes for the nodes
of different sensitive attribute
{-1, follows fx(X;; x/s; = =1) ~ N(1n. Σ,) - P1 and
fx x/s; = 1) N(p2, Σ₂) _ Ps, and the sensitive attribute ratio satisfies E, (P(s 1)]
then the mutual information between sensitive attribute and node attributes I(s, X) satisfies
I(s,X) S (1 - c) In (1 c) cexp ( -Dx((P)1PP)))
-chn c (1- exp ( D (P:(PP))))) _ Bias(s, X). We leave the analysis of other random graph models feature distributions in future work.
4

---

Under review as a conference paper at ICLR 2023
Based Theorem I we observe that lower distribution distance (xz(Pi (Pe(Pa)(PR) beneficial for reducing (ias(s, X) and [ss, X) since the sensitive attribute less distinguishable based on node representations.
4.3 WHEN AGGREGATION ENHANCES THE BIAS?
We focus the role of message passing in terms of fairness. Suppose the graph adjacency matrix A sampled for (n, Pd: Ceene, -)-graph and we adopt the GCN-like message passing X AX, where A is normalized adjacency matrix with self-loop. We define the bias difference for such message passing as ABias Bias(s, X) (ias(s, X) to measure the role of graph topology. Subsequently, we derive intra-connect and inter-connect probability in Lemma]
Lemma 1 Suppose the synthetic graph is generated (n,, Pd, Esens: e)-grahh, then we obtain the intra-connect and inter-connect probability as follows:
PdEsens
Pd(1 Esens)
Poonn
c² + c1-c)2-
Jconn
2c(1 c)
Subsequently, provide sufficient condition to specify the case that graph topology enhances bias in Theorem 2
Theorem Suppose the synthetic graph node attribute X generated based on Gaussian Mixture Model GMM(c, μ1, Σ, E), and the graph adjacency matrix A is generated from (n., Pd: Czens e)- graph. If adopting GCN-like messuge passing X = AX, bias will be enhanced, i.e., A Bias >> 0 if the bias-enhance condition holds: (V1 - v2) min {2} > 1, where 1/1 V/2 < represents the reduction coefficient of the distance between the mean node attributes of the two sensitive attributes groups, Ç1, S2 mean the connection degree of two sensitive groups; the mathematical formulation is given by
(nl 1)Prmn +
[nl 1)
11
1/2
C
where Ç1 Tronn + (n1 1)pomn + 1, Co = Proonn + (m1 1) + 1, the node number with the same sensitive attribute n-1 = n(1- c). n1 = nc, Iutra-conned probability Poonn =E [ij(P((ii)ss: s,)), and inter-connect probability 4conn E.j [P( s, -)].
Based on Theorem 2. we can provide more discussion on the influence of 4 graph data in- formmattion of graph:the number of nodes n, the edge density Pa. sensitive homophily coefficient Csens, and sensitive group ratio for bias enhancement as follows:
Node representation bias enhanced by message passing for sufficient large sensitive ho- mophily 6sena. According to Lemma T for large sensitive homophily coefficient evens 1, the inter-connect probability fconn - O and intra-connect probability Pconn keeps the maximal value. In this case, based Theorem it is casy to obtain that / 1, 122 0 and the distance for the mean aggregated node representation will keep the same, i.c., A1 - A2 = (21 12) (22) = μ4 μ22- Additionally, the covariance will be diminished after aggregation since Çi and (2 strictly larger than 1. Therefore, for sufficient large sensitive homophily coefficient Csens, the bias-enhance condition (n) )² min {2) holds.
The bias enhancement implicitly depends on node representation geometric differentiation, in- cluding the distance between the mean node representation within the same sensitive attribute and the scale covariance matrix. Theorem implies that low mean representation distance and concentrated representation (low covariance matrix) lead to fair representation. However, GCN-like message passing renders the mean node representation distance reduction V - 1/2 and concentrated for each sensitive attribute group, which is an "adversarial" effect for faimness and the mean distance and covariance reduction is controlled by sensitive homophily coefficient.
The bias is enlarged as node number n being increased. For large node number n., the mean CPeann.
distance almost keeps constant since #1 R [1-c)groon -Cpanns 1/2 RJ [I-c]Peonn +Cg-om=" and Ç1. C2 are almost proportional to node number n. Therefore, the bias-en enwancemeneet condition can more easily satisfied and A Bias would be higher for large graph data. The intuition is that, given graph
Cyeann
5

---

Under review as a conference paper at ICLR 2023
0.10
DP Difference
1-100
DP Difference
0.05
Difference
0.0
0.00
0.00
-0.05
-0.05
Co02
-0.2
-0.10
-0.15
-0.15
0.70
0.75 0.85 0,90 0.95 1.00 Sensitive Hamaphily
0.70
0.75
0.85 0,90 0.95 1.00 Sensitive Homaphily
0.70 0.75 0.80 0.85 0,90 0.95 1.00 Sensitive Homophily
Figure 2: The difference of demographic parity for message passing. Left: DP difference for different graph connection density Pa with sensitive attribute ratio e = 0.5 and number of nodes n = 10 Middle: DP difference for different number of nodes n with sensitive attribute ratio 0.5 and graph connection density Pa = 10 Right: DP difference for different sensitive attribute ratio c with graph connection density Pa 10 and number of nodes 104;
density ratio, large graph data represents higher average degree node. Hence, each aggregated node representation adopts more neighbor's 's information with the same sensitive attribute, and thus leads to lower covariance matrix value and higher representation bias.
The bias is enlarged as graph connection density being increased. Based on Lemma || inter- connection probability and conerccnnnntion probability are both proportional to graph connection density Pd- Therefore,
and v2 almost keep constant and the distance of mean node representation is constant as well. As for the covariance matrix, message passing leads to more concentrated node representation since Çi and are larger for higher graph connection density Pa- The rationale similar to the graph node number: given node number, higher graph connection density Pa means higher average node degree and each aggregated node representation adopts more neighbor's information with the same sensitive attribute.
When the sensitive attribute is more balanced (i.e..) the bias will be enlarged. Based on Lemma D it is easy to obtain that, given graph connection density Pa and graph node number n, the intra-connection probability Peonn would be high, while being low for inter-comeection probability Jconn, if the balanced sensitive attribute. In other words, intra- connectonn probability Peonn (inter-connection probability (conn) monotonically decreases (increases) with respect to
5 LEARNING FAIR GRAPH TOPOLOGY
The above section provides a data-centric perspective (graph topology) to understanding why message passing may enhance representation bias. In other words, graph topology refinement may assist GNNs model in achieving fair and accurate prediction. However, searching for the optimal graph topology for GNNs is non-trivial problem due to large-scale discrete optimization. In this section, motivated by the theoretical analysis, we propose Fair Graph Refinement method, named FairGR, to achieve fair prediction via learning the optimal graph topology. Specifically, we formulate functions into three parts, including low sensitive homophily coefficient, high label homophily coefficient, and small topology perturbation. In this way, FairGR can explicitly reduce the topology bias while preserving useful topology information for prediction.
objective
Problem Formulation. Considering binary sensitive attribute s; E 1-1,1} and binary classifica- tion task with label y; E 1- for i-th node, we aim to modify the graph topology to achieve low sensitive homophily coefficient Ezens, high label homophily coefficient elabei, and small topology perturbation. For sensitive homophily coefficient with the binary sensitive attribute, the determination of any two nodes with the same sensitive attribute can be obtained via H (ss"",, where H(-) ()) is Heaviside (unit) step function, sensitive attribute vector s E (-1, 13 1 Based on Definition
[[][] It easy rewrite sensitive homophily coefficient esens [[s"' AoAll where @ represents Hadamard product, and ||- |l1 denotes the entry-wise I norms (i.e., the summation over all absolute value of elements). Similarly, label homophily coefficient as Glabel [H[yy""JAAl] JoAl) As for graph topology perturbation, we can use the entry-wise I norms the difference as the measurement. In a nutshell, the objective function reconstruct graph connections given sensitive attribute s, label y.
||
[|
||A||

---

Under review as a conference paper at ICLR 2023
and graph topology A can be formulated as:
(( = [[(s²)) @ All (|H(y)") & All + +1 - -All,
a
(2)
||A||2
||Al|2
Therefore, the rewired graph topology can be obtained via constrained optimization problem min y, E {0, 1), where and / are the hyperparameters for label homophily
A
coefficient and graph topology perturbation. Considering the formulated problem is a large-scale discrete optimization problem, employ heuristic optimization method to obtain the modified graph topology.
Optimization Strategy. To optimize the formulated problem with constraint, we adopt Proximal Gradient Descent (PGD). Specifically, we first adopt gradient descent to update the graph topology
Subsequently, we clip the graph topology Å within {0, 13 in the projection operation of PGD. Such operation will conduct multiple times to obtain the final graph topology. In practice, considering only the sensitive attribute and label for the training set are available, we actually only modify the graph topology within the training nodes. other words, the three objectives, including sensitive homophily coefficient, label homophily coefficient, and graph topology perturbation, are calculated for the subgraph of training nodes. In this way, we can avoid information leakage from the test set and reduce the complexity of the optimization problem.
using gradient @C(Als.y.A)
AA
Evaluation and Computation Complexity Analysis. For algorithmic evaluation of pre- pre-processing FairGR, we compared the prediction performance (including accuracy and fairness) using original graph topology and rewired graph topology across multiple GNN backbones. Denote the number of training nodes and update iterations as N and T, respectively. Then the computation complexity for gradient computation and projection of PGD are both O(nraizz) The total computation complexity to obtain the final rewired graph topology is given by (T'mirain). The memory consumption is O(nevain ) due to the storage of graph topology gradient.
Table 1: The performance Node Classification (GR represents graph topology rewire).
Pokeo-z
Pokec-n
NBA
Models
Acc (%
Anp (%)
ARO (%)
Acc (96 1
App (%)
Ago (%)
Ace (96)
(96)
Anp (%)
Apo (%)
MLP
70.48
0.77
1.61 + 1.29
2:22
1.01
72.48 + 0.26
1,53
0.89
3,39
2.37
65.56 + 1.62
22.37 + 1.87
18.00
3,52
GAT
69.76
1,30
2.39
+ 0.62
2.91
+ 0.97
71.00 + 0.48
3,71
2,15
7,50
= 2.88
57.78
10.65
20.12
16.18
13,00 + 13.37
GAT-GR
56.75
6.32
1.04
0.80
1.14
1.02
61,27
9.34
0.54
0.51
2.27
1.55
53.65
10.31
4.16
5.13
3.67 1. 3.23
GCN
71.78
2.35
2.09
73.09
0:28 3,48
0.47
5.16
1.38
61.90
23.70
17.50 2.63
GCN-GR
71.68
0.58
1.59
0.71
72.68
0.44
0.47
0.39
0.78
61.59
4:
20.24 1: 4.41
::
SGC
71.24
= 0.46
4.81
0.30
4.79
71.46
+: 0.41
2.22
0.29
3.85
1.63
63.17 4: 0.63
23.55 4: 3.94
14.33: 2.16
SGC-GR
70.95 = 0.91
3.32 + 1,31
3.20 4: 1.90
71.91 4: 0.52
0.71
0.65
2.39
0.69
62,54 + 1.62
18.56 :: 2.81
2.50 : 1.1.1.00
EXPERIMENTS
In this section, we conduct experiments validate the effectiveness (see Apppendix for for more de- tails.) of the proposed FairGR. We firstly validate that GCN-like aggregation enhances representation bias for the graph data with large sensitive homophily via synthetic experiments. For real-world datasets, we conduct experiments to show that the prediction bias of GNN is larger than that of MLP. Moreover, we introduce the experimental settings and then evaluate our proposed FairGR compared with several baselines in terms of prediction performance and fairness metrics on real-workd datasets.
6.1 SYNTHETIC EXPERIMENTS
In the synthetic experiments, we demonstrate the relation between DP difference across GCN-like message passing operation and sensitive homophily coefficient Specifically, we investigate the
NNote that we only do theoretical study in GCN-like message passing operation as pilot study. The investigation of other GNN aggregation operations (such as GraghSAGF-lik operation) and GNN models may require different techniques and can he further conducted in future work.
7

---

Under review as a conference paper at ICLR 2023
influence of graph node number graph connection density Pd, sensitive homophily Czene and sensitive attribute ration e for bias enhancement of GCN-like message passing. For evaluation metric, adopt the demographic parity (DP) difference during message passing to measure the bias enhancement. For node attribute generation, we first generate node attribute with Gaussian distribution N (11;; Σ) and N Σ) for node with binary sensitive attribute, respectively, where
1 0
Mi [0, 1). μi
[1 and Σ
For adjacency matrix generation, we randomly
0
generate edges via a stochastic block model based on the intra-connection and inter-connection probability.
Figure shows the DP difference during message passing with respect to the sensitive homophily coefficient. We observe that higher sensitive homophily coefficient generally leads to larger bias enhancement. Additionally, higher graph connection density Pd, larger node number n, and balanced sensitive attribute ratio e correspond to higher bias enhancement, which is consistent with our theoretical analysis in Theorem
6.2 EXPERIMENTS ON WORLD DATASETS
6.2.1
EXPERIMENTAL SETTINGS
Datasets. The experiments are conducted on three real-world datasets, including Pokec-z, Pokec-n, and NBA (Dai & Wang, 2021). Pokec-z and Pokec-n sampled from larger social network Pokec (Takac & Zabovsky|] (012) based on the province Slovakia. We choose region information and the working field of the users the sensitive attribute and the predicted label, respectively. NBA dataset includes around 400 NBA basketball players and is collected from Kaggle dataset and Twitter. The information of players includes age, nationality, and salary in the 2016-2017 season. We choose nationality (U.S. and overseas player) as the binary sensitive attribute, and the prediction label whether the salary is higher than the median.
Evaluation Metrics. For the node classification task, we adopt accuracy to evaluate the classifica- tion performance. As for fairness metric, we adopt two most common-used group fairness metries, including demographic parity and equal opportunity, to measure the prediction bias (Louizos et al.)
2013 Beutel et al. 2017). Specifically, demographic parity is defined as the average prediction dif-
ference over different sensitive attribute groups, i.e., Apr [p 1|s= -1)
Plý 1/s 1)]-
Similarly, equal opportunity is given by Ágo = [T = 1/8 = -1, 1) -1) = 1| 1, 1)),
where y and ý represent the ground-trute truth label and predicted label, respectively.
Baselines. Considering that the proposed FairGR is pre-processing method, we show that our proposed FairGR can improve many representative GNNs, such as GCN (Kipf & Welling (017). GAT (Veličković et al., 2018). SGC (Wu et al.) 2019), in many fairness training strategies, such adding regularization, adversarial debiasing. For all models, we train layers of neural networks with 64 hidden units for 300 epochs.
Implementation Details. For each experiment, we run 5 times and report the average performance for each method. We adopt Adam optimizer with 0.001 learning rate and le weight decay for all models training. In adversarial debiasing setting, we train the classifier and adversary head with 70 and 30 epochs, respectively. The hyperparameters for adversary debiasing tuned in (0.0, 0.5, 1.0, 2.0, 5.0, 8.0, 10.0, 50.0, 100.0). D.. For adding regularization, we adopt the hyperparame- ter {0.0, 1.0, 1.5, 2.0, 5.0, 8.0, 10.0, 15.0, 25.0, 50.0, 80.0, 100.0).
6.2.2 DOES GNNS HAVE A LARGER PREDICTION BIAS THAN MLP?
To validate the effect of bias enhancement of GNNs, compare the performance of many represen- tative GNNs over MLP on various real-world datasets and summarize the results in Table From these results, make the following observations:
Many representative GNNs have a higher prediction bias compared with MLP model on all three datasets in terms of demographic parity and equal opportunities. For demographic parity, the
8

---

Under review as a conference paper at ICLR 2023
Pokec
Pokec_
NBA
Rog
Tack
ACC
ACC
Adv
8
Daath
Lack
Figure 3: DP and Acc trade-off performance on three real-world datasets compared with adding regularization (Top) and adversarial debiasing (Bottom). The trade-off curve closer to the right bottom cornrr represents better trade-off performance.
prediction bias of MLP is lower than that of GAT, GCN, and SGC by 32.64%, 50.46% 66.53% and 72% on Pokec-z dataset. The higher prediction bias comes from the aggregation within the same-sensitive attribute nodes and topology bias in graph data.
FairGR can mitigate bias for GCN and SGC backbone via rewiring graph topology in these three datasets, For GAT backbone, although the bias can be mitigated, the accuracy drop is significant due to the fact that GAT is more sensitive to graph topology rewire.
6.2.3 DOES FAIRGR ACIIEVE BETTER TRADEOFF PERFORMANCE VARIOUS SETTINGS?
Comparison with adversarial debiasing and regularization. To validate that the proposed FairGR is compatible with many fairnsss training strategies, also show the prediction performance and fairness metric trade-off compared with adversarial debiasing (Fisher et al. (0220) and add demographic parity regularization (Chuang & Mrouch 2020). In adversarial debiasing (Louppe et al.) 2017). the output of GNNs is the input of the adversary, and the goal of the adversary is to predict node sensitive attribute. For these two fair training strategies, we adopt GCN, GAT, and SGC as backbones. We randomly split 50% 50%/25%/ /25% 225% for training, validation, and test dataset. Figure shows the Pareto optimality curve for all methods, where the right-bottom corner point represents ideal performance (100% accuracy and 0% prediction bias). From the results, we list the following observations as follows:
For both adversarial debiasing and adding regularization training strategies, our proposed FairGR can achieve a better DP-Ace trade-off compared with that without any graph data refinement for many GNNs. In other words, FairGR can effectively reduce training bias and is compatible with many existing fairness training strategies.
Topology does matter in GNNs. For adding regularization adversarial debiasing, FairGS embrace different tradeoff performance gain on top of different GNNs. Such observation implies that there is complicated interaction between graph topology and message passing algorithms. Additionally, FairGS provide the most tradeoff performance benefit in GAT compared with GCN and SGC. The high capacity of GAT may energize the message passing algorithm to learn from data. Therefore, the tradeoff performance improvement is the highest in adding regularization and adversarial debiasing.
7 CONCLUSION
In this work, we theoretically demonstrate that the message passing amplifies node representation bias under the graph data with large sensitive homophily coefficient, and reveal the role other graphs statistical information in terms of bias amplification. Additionally, motivated by theoretical understanding, we develop a simple yet effective graph refinement method, named FairGR, to reduce the sensitive homophily while preserving useful information. We conduct synthetic experiments to validate theoretical findings. Experimental results on real-world datasets demonstrate the effectiveness of FairGR in many fair training strategies and GNNs backbones in node elassification tasks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. arXiv preprint vrXiv:2102.13//66 2021.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. In ICML, 2021.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv:1707.0007. 000000 2017.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference on Machine Learning, pp- 715-724. PMLR, 2019.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6205 2013.
Maarten Buyl and Tijl De Bie. Debayes: a bayesian method for debiasing network embeddings. In International Conference on Machine Learning, pp. 1220-1229. PMLR, 2020.
Mathieu Carriere, Frédéric Chazal, Marc Glisse, Yuichi Ike, Hariprasad Kannan, and Yuhei Umeda. Optimizing persistent homology based functions. In International conference on machine learning, pp. 1294-1303. PMLR, 2021.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Ching-Yao Chuang and Youssef Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
Ching- Yao Chuang and Youssef Mrouch. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2021.
Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International conference on machine learning, pp. 1436-1445. PMLR, 2019.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 680-688, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, 29:3844-388 3852, 2016.
Yuxiao Dong, Omar Lizardo, and Nitesh V Chawla. Do the young live "smaller world" than the old? age-specific degrees of separation in a large-scale mobile communication network. arXiv preprint arXiv: 070.0056660065 2016.
Mengnan Du, Subhabrata Mukherjee, Guanchu Wang, Ruixiang Tang. Ahmed Hassan Awadallah, and Xia Hu. Fairness via representation neutralization. arXiv preprint arXiv:2106.122 126744 2021.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259-262-- 2015.
Joseph Fisher, Arpit Mittal, Dave Palfrey, and Christos Christodoulopoulos. Debiasing knowledge graph embeddings. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 7332-7345, 2020.
Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 2016.
10

---

Under review as a conference paper at ICLR 2023
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 1416-1424, 2018.
Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto. Knowledge trans- fer for sowlofffnowleege-bbee base entities: A graph neural network approach. arXiv preprint 154.::7706.05674 2017.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp.
2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. 2015.
arXiv preprini arXiv:
Zhimeng Jiang, Xiaotian Han, Chao Fan, Fan Yang, Ali Mostafavi, and Xia Hu. Generalized demographic parity for group fairness. In International Conference Learning Representations, 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education India, 2006.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günneeman. Predict then propagate:
Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Öykü Deniz Köse and Yanning Shen. Fairness-aware node representation learning. arXiv preprint arXiv:2106.05331, 2021.
Solomon Kullback. Information theory and statistics. Courier Corporation, 1997.
Charlotte Laclau, levgen Redko, Manvi Choudhary, and Christine Largeron. All of the faimess for edge prediction with optimal transport. In International Conference on Artificial Intelligence and Statistics, pp. 1774-1782. PMLR, 2021.
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference Learning Representations, 2021.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. arXiv preprint arXiv: 151 1.00800 2015.
Gilles Louppe, Michael Kagan, and Kyle Cranmer. Learning to pivot with adversarial networks. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 982-991, 2017.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? arXiv preprint weXiv:2106.06/:: 2021.
Yao Ma. Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference Learning Representations, 2022.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5115-5124, 2017.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: aeee::900000000 2019.
11

---

Under review as a conference paper at ICLR 2023
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. 2019.
Harini Suresh and John V Guttag. A framework for understanding unintended consequences of machine learning. arXiv preprint arXiv: 1901: 2. 2019.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 1, 2012.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional networks. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, pp. 1435-1444, 2020.
Remco Van Der Hofstad. Random graphs and complex networks, volume 43. Cambridge university press, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference machine learning, pp. 6861-6871. PMLR, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974-983, 2018.
Mikhail Yurochkin and Yuekai Sun. Sensei: Sensitive set invariance for enforcing individual fairness. In International Conference on Learning Representations, 2020.
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pp. 335- 340, 2018
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 2020.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM
We provide more general proof for categorical sensitive attribute (1, . and the prior probability is given by P(s = i) c.. Suppose the conditional node attribute x distribution given node sensitive attribute s = satisfies normal distribution P:(x) _ N(u; Ei), the distribution of node sensitive attribute is the mixed Gaussian distribution f(x) Σ cxP.(x). Based on the definition of mutual information, we have
x Hx)) Σ
(x|s =
where H-) represents Shannon entropy for random variable. Subsequently, focus the entropy of the mixed Gaussian distribution Hx)). We show that such entropy can be upper bounded by the pairwise Kullback-Leibler (KL.) divergence follows:
T(s.x)
Σ Er
In
Σ
Σ
H(( =
K
K
In
Cye
Br, (1n P3(0]]
GH(x|s- i)
1=1
K
K
K
=
C/
In
Cje'
H((P.IP))]
cx =
j=1
K
(
Σ
In
Cge
H(P.)-
Σ (x|sx(s-
j=1
K
K
K
Σ
c:
In
Cee
DKz(PP)1P))
+ Σ cH((P)
Σ cx|s
j=1
K
K
=
Σ
In
Cge
j=l
where KL divergence (KI(P)))P)) & f P.()) In Pix) dx and cross entropy (P.)))))
p)())
P( In (x)dx. The inequality (a) holds based the variational lower bound the expec-
tation of log-sum inequality E In Σ, Z.] 2 In Σ Riin z.] Kullbackk 1997). and quality (2) holds based H)) H(P)) DEL (PI1P)) As special case for binary sensitive attribute,
it is casy to obtain the following results:
[(s, X) -(1-c) (1 c) + cexp (- (-DrI(P1))P))) - eln (e+ (1 - c) exp ( -- -DII(PP))PP))
B PROOF OF THEOREM 2
Before going deeper for our proof, we first introduce two useful lemmas on KL divergence and statistical information of graph.
Lemma 2 For two d-dimensional Gaussian distributions P. N Ep) and Q N En), the KL divergence (Kl(P((Q) is given by
1 in
Eg Ep
(kI(PI1
(Hp mg) Eg " Mg) + Tr(E Ex,)
(4)
where T. matrix transpose operation and Tr(:) is trace of square matrix.
13

---

Under review as a conference paper at ICLR 2023
Proof: Note that the probability density function of multivariate Normal distribution is given by:
P(x)
1
exp (x) 11p))
(2T)4/2|Ep,)
the KL divergence between distributions and Q can given by
DEL (P(()
Ep[In(P P) In())
Ep
h
Σ
x - Up) T 1x 1xp1x (x - Up) + z - n₂g 2n)TZny
3 (x - mn)
Ep
Egg
In
Ep
(x - Up) ">pp" (x - Mp)
+ Ep (x - U₂) Dyy (x Ma)
2 Epl
Using the commutative property of the trace operation, we have
1 ] Ep (x
Hp)p Ep Hp)
(x- } Tr (Ep Ep (x (xp-1p)T6
1
2
2
1 - Tr Ep (xpp) (x-
(xp1)p
1 Tr
(Ip=z")
d
(5)
2
2'
As for the term Iz, note that x - M4 = (x - Ex(x|) + (Er(x) Mg). we can obtain the following equation:
= Ep (x Hby "n (x pb)
12
2 (up mny " ' mg) + Tr(2,'E,))
(6)
Therefore, the KL divergence
D (PI()) ) is given by
1 Egl d (H1 M₂) - Mn) + Tr(E,'E,)) In
(RI(PIIQ)
Σp
Lemma 3 Suppose the synthetic graph is generated from (n, pds Esens c)- graph, then obtain the intra-connect and inter-connect probability as follows:
Pdesens
Pd(1 - Csens)
Peonn
②² + + c)-
Jcorn
2c(1
Proof:
Based Bayes' rule, we have the intra-connect and inter-connect probability follows
=s)s;=;;)=0) Poonn -PAAi = 1|ss = s;) = P(A 1)P(s, s, Aij =1]
Pde
P(s; = =8})
2 (1 c)2
Iconn P((Ag = 1|s,s, = -1) = P(A,; = 1)P(s; 11; Pa(1 (sens)
11s,s;==-111
(8)
IP(8)8y) = --
2c c)
Note that the synthetic graph generated from (n, Pd: Esenss e)-graph. The sensitive attribute is generated to with ratio i.e., the number of node sensitive attribute = -1 and = =1 are n- = n2( - c) and nı = ne. Based on the determined sensitive attribute s, we randomly generate the edge based
parameters Pa and ésens and Lemma I i.e., the edges within and cross the same group are randomly generated based on intra-comnec probability and inter-conned probability. Therefore, the adjacency matrix A; is independent attributes s; and s,. i.c., Ai IL (X;, (s, s,). Similarly, the different node attributes and edges are also dependent each other given sensitive attributes, i.e., Aij II. Aij((s, 8j, 8&) and
node attribute X, and X, given sensitive
14

---

Under review as a conference paper at ICLR 2023
X, TT X,) (s,, sy). Therefore, considering GCN-like message passing X; = =E Xz, we have
the aggregated node attributes expectation given sensitive attribute as follows:
P1 = Ex, X = - =
Σ ==1
E A. x, [ss = -
E Acs Ais)s: = - Ex [ = -1]
(n-1 1)BAA, As [Aiyls = - 1, = - [X, = -1, = =-1
+E +EX, A |s; = =,, = Ex [X 18 = -1]
+n L A. |Ais [s = -1 1 [x)ss = -1, =
(n_ P)pcon + 11p1 + 11 119comm/22 &
11 (1 12)
(9)
nn-1 1)Pcon + 1 + 13 Aconn
where 1
(n - 1)Ponntt1
Similarly, for the node with sensitive attribute have
in. 1 P) +1+71gcomm
32 = Ex X S. = - Σ B X [s. =1
Σ EA A
1/
1| X |s: 1]
7-1 E A. [A 1g [ = L, - 1| X is = 1, -1]
+E A., [Ai (s = -,,i= Ex X S; 1]
+ + 1)E [Ayls = 1, = Ex X x = L, = 1]
Mc + [[11 1)Pconn 11 V2l01 (1 1/2 12
(10)
1h- Goonn + (n1 1)Peonn
1
1) where 1/2 n. 19cann + [1 DPeom As for the covariance matrix of aggregated node attributes X
given node sensitive attribute = -1 and original sensitive attribute, note that we can obtain
Σ
Dx D (2,8;; -1] = A.y X Aij -1]
n
Σ
E A.s [A,y]s: = 1 [y|s;= -1]
j=1
(n_1
1)pcorn E + Σ + n2 Iconn Σ
[[n_1 Pe + n2 Iconn 2
= (n-1 1)Peonn + 1 + 11
2-1 Σ
(11)
where Ci (n-1- D) + 1 + 11gmmnn- Similarly, given node sensitive attribute 1,
we have Σg Dxx [ =
E where (2 n 14omn 1 + (ni Peonn In other words, the covariance matrix of the aggregated node attributes is lower than the original one since the "average" operation will make node representation more concentrated. Note that the summation over several Gaussian random variables is still Gaussian, we define the node attributes distribution for sensitive attribute
Σ
+I
-1 and 1 as P: NN E). P2 -N E), respectively. Similarly, the aggregated node representation distribution follows for sensitive attribute = -1 and s = as P; = (M1, Στ). P2 = ~Ni Σz). Note that the sensitive attribute ratio keeps the same after the aggregation and larger KL divergence for these two sensitive attributes group distribution, the bias enhances A Bias if Dx (P, P2) DRL (P2) and
15

---

Under review as a conference paper at ICLR 2023
DKL (1) Dxz(Pa Therefore, only focus on the KL divergence. According to
Lemma 2
it is easy to obtain KL divergence for original distribution as follows:
DKI(PIlIPs)
d + ( - -2) " E- E -22) + +T((E-1)))
(n p2) E (W1 -22);
(12)
As for KL. divergence for aggregated distribution, similarly, we have
Σ
Dxt(PillPs)
=
2 In
+ (ū1 (12) 13'2''(1 - (12) + Tr((it1E1))
_ - d (p1 - -v2) 62(21 - 12) T E - u2) + S2 Tr(aaa
dln
2
4
S2
No
(u 3 S2 u22) T E Σー ( -12),
(13)
where inequality (c) holds since In < for any x 0. Compared with equations (12 and 13 it seen that DKL (Pil) > (xz(Pi if - 1. Similarly, we can have DKL (PallPi) > (xl(PP))Pt) (11 -11 21 1. In a nutshell, the bias enhances ABias after message passing if (vi 12)² min (2) > 1.
C TOPOLOGY AMPLIFIES BIAS IN ONE-LAYER GCN
Section demonstrates that GCN-like aggregation operation amplifies node representation bias for graph data with large topology bias. However, it is still unclear whether such observation holds for general GNNs not. Generally speaking, this problem is quite fundamental and challenging to understand the role of topology fair graph learning. In this section, we try to move a step toward this problem by considering one-layer GCN. Prior comparing the prediction for one-layer GCN and one-layer MLP, we first provide the connection between demographic parity and mutual information of sensitive attributes and predictions. Then, we theoretically compare the prediction bias of one-layer GCN and one-layer MIP through the lens of mutual information.
C. PREDICTION BIAS AND MUTUAL INFORMATION
Here, we only consider binary sensitive attributes (-1,1} and binary labels y {-1, 1).
Similarly, we can define y E {-1, }} as the binary model predictions. In the faimesss community, demographic parity, defined as the average prediction difference among different sensitive attribute groups, is the most commonly used fairness metric, i.c., ADP- = [P[ýls - -1)] From the mutual information perspective, the correlation between sensitive attributes s and prediction ÿ can be measured by 7 7(s; ÿ). In this subsection, we provide an inherent connection between demographic parity ADP and mutual information yss as follows:
Theorem For binary sensitive altributes s E (-1,1} and binary prediction ý E {-1, demo- graphic parity &DP and mutual information (s: satisfies T(s;)) < 2ADP
Proof: For simplicity, we defined the joint probability auy P(y = i,s j) and condition probability as Oiiy P(ý = i|s = j). Considering the log ratio between joint distribution and margin product probability, have
P(ý- i,s
aij log E, a = j] -log (1+ (ail - -: -PI
log
P(ý = i) =
Σ, a 10sss = =j)
Ip(s = -j)
P(s -s)
(aus ay. agls)) E, Only P(s j)
< <DDP Pi j) (14)
16

---

Under review as a conference paper at ICLR 2023
where inequality (d) holds due to log(1 + x) x for any -1. According the definition of mutual information, we have
Σ P(y = i,8 log PP( = i,s 5) P(ý = i) =)
Oij
[(s:8) -
Oauj log
Eg Oils
IP(s 0:1y
=
P(s -j)
ADP
ONUJ Ej Only P(s =) ADP Σ
P(s -))P(s -)l8 =
ADP E P(s = - P(ss jزy i)] = 2DDP
(15)
where inequality (f) holds due to E, abb S E; a Σ, b, for non-negative and b;.
Theorem shows there is a strong connection between demographic parity and mutual information for binary sensitive attributes and binary labels, i.e., the mutual information upper bounded by demographic parity multiplied by 2.
C.2 PREDICTION BIAS COMPARISON BETWEEN ONE-LAYER GCN AND ONE-LAYER MLP
Considering the strong connection between mutual information and demographic parity, we inves- tigate prediction bias comparison between one-layer GCN and one-layer MLP through the lens of mutual information. For one-layer MLP model, the prediction is given by MLPP (XWWMLL where W MLr is trainable parameter for MIP. Similarly, for one-layer GCN, the prediction is given by YGCN = or (AX it is easy to that one-layer MLP model and one-layer GCN model are almost the same except with different node features. Based Theorem [ presentation bias than that of X. In other words, the bias of input data for one-layer GCN is higher than that of one-layer MLP.
where WeeN is the trainable parameters for GCN. Define X = AX,
the aggregated node features X embrace higher
For the prediction bias, note that sensitive attributes s, node features X, and prediction ý form Markov chain X x- y since P(y is X) = P()[X) for the model with vanilla training. Based on data processing inequality, it is easy to obtain
[(s; = I(s; X) - I(s: X(YMLP),
((s)CCN)) = ((s:X) 1 (ss X (GCN).
(16)
In other words, when I(s: XL) [(s X (GCNN) ), the higher input data bias will lead to higher prediction bias. For lne-l MLP and lae-l GCN, if the condition in Theorem are satisfied, the prediction bias of one-layer GCN is also larger than that of MLP.
C.3 COMPARISON WITH CONCENTRATION PROPERTY IN GNN AND PERSISTENT HOMOLOGY
GNN's s concentration property represents all node presentation convergence after stacking of aggrega- tions (Nt & Maehara 2019 Ma al.) 2022: Baranwal et al. 202T). There are differences between
bias enhancement and concentration property in GNN:
Definition. Concentration property means that the node representation of all nodes convergence after GNN aggregation. Bias enhancement represents the node representation for different sensitive groups that are more distinguished. In fact, such two properties are somehow contrary since perfect concentration leads to zero bias.
Aggregation. For concentration property, only the normal features and topology are involved in the analysis. The high-level interpretation of concentration is that aggregation acts like low-frequency filter and such an "average" effect leads to node representation convergence. In the sensitive homophily coefficient, feature aggregation due to law restrictions. Even though the sensitive attribute is included in GNN aggregation, and all node representations are the same, it does not represent the bias enhancement (actually zero bias.). The bias in GNN represents the highly different node representations or predictions among different sensitive groups (defined by sensitive attributes).
would like to clarify that the sensitive attributes are not included for node
17

---

Under review as a conference paper at ICLR 2023
Comparison. We also provide the connection between concentration property and bias enhancement in GNN. The intuition of why GNN enhances the bias, high sensitive homophily represents that the nodes with the same sensitive attributes are connected with high probability. Considering concentration property, the node representation for the same sensitive attribute is more similar after aggregation, therefore leading to highly different representations for different sensitive attribute groups. Notice that such behavior only happens for high sensitive homophily coefficients and shallow GNN. When the node with different sensitive attribute groups is connected randomly, the bias enhancement would not happen or be insignificant due to random concentration. When adopting deep GNNs, all node representations converge and have no bias enhancement. Unfortunately, due to concentration property, shallow GNNs are mainly used in practice. As for high sensitive homophily coefficient, such a condition usually satisfied in practice due to natural graph data property.
Additionally, there are several differences between our proposed optimization scheme and work (Carriere et al. 202T), including definition, dependence, and optimization:
Definition: Persistent homology is a method for calculating the importance of topological features the simplicial complex. For example, giving a set of points in a point cloud corresponding to a chair, the task is to detect the object from the points. In this case, there is no connection between any pair of points. Persistent homology is a tool to identify the topological feature (or connection patterns) via gradually building up the connection between points. However, for graphs, they are I-simplex with explicit connection patterns defined by the set of edges, thus many properties from persistent homology will degenerate to the field of graph theory. For example, applying the persistent homology on the graph is equivalent to building maximum spanning trees (MSTs) using Kruskal algorithm (Kleinberg & Tardos 2006), which is irrelevant to our proposed optimization scheme.
Dependence. Persistent homology is generally related to sample features, as shown in the example Point cloud optimization of (Carriere et al., [02T). In other words, persistent homology somehow represents the topological features of all samples. Differentially, in the graph data we focused on, there are node normal attributes, sensitive attributes, and adjacency matrix (graph topology). Based on the definition, the sensitive homophily coefficient is related to sensitive attributes and the adjacency matrix. However, the optimized adjacency matrix is generally dependent on sensitive attributes.
Optimization. The main challenge for persistent homology-based optimization generally undiffer- entiable except in some special cases. (Carriere et al.) 2021) develops a general framework to study the differentiability of the persistence of parametrized families of filtrations. In this way, under mild assumptions, stochastic subgradient descent algorithms can be applied to such functions to converge almost surely critical point. For our problem (2), the gradient of loss over topology is differentiable in general. The challenge falls in the constraint of an element value. In our solution, we use a gradient-based method to update the adjacency matrix via variables relaxation and then adopt project operation to satisfy such constraint.
D RELATED WORKS
Graph neural networks. GNNs achieve state-of-the-art performance for various real-world applica- tions. There two categories in GNNs model backhones, including spestral-based and spatial-based
GNNs. Spectral- based GNNs provide graph convolution operation together with feature transfor-
mation (Bruna et al. 2013 Defferrard et al. 2016: Henatf et al. 2015). Many spatial-based GNNs
are also proposed to aggregate the neighbors' information, including graph attention network (GAT)
(Veličković et al. 2018). GraphSAGE (Hamilton et al. 2017). SGC (Wu et al., 2019). APPNP (Klicpera et al. 2019), et al (Gao et al. Monti et al. 2017).
Fairness-aware learning on graphs. Fairness in machine learning has attracted many research efforts to mitigate prediction bias (Chuang & Mroueh| 2020)) Zhang et al. 2018: 8 Du et al. 1021] Yurochkin & Sun 2020 Jiang et 2022 Creager et al.) 2019; Feldman et al. 2015). Fair walk (Rahman et al. 2019) is a fair version of random walk to learn fair node representation via revising neighborhood sampling. From the bias mitigation perspective, adversarial debiasing and contrastive learning also developed for graph data. For example, works (Dai & Wang, 2021 Bose & Hamilton| 20199; Fisher et al.] 2020) also adopt the adversary to predict the sensitive attribute given the node representation. fairnes--wware representation learning is also developed via node
18

---

Under review as a conference paper at ICLR 2023
feature masking, graph topology rewires (Agarwal al. 2021 Köse & Shen 2021 for node classification or link prediction tasks (Laclau et al. 2021: Li et al. 2021). However, the inherent reason behind the observation that GNNs show higher prediction bias than MLP is still missing. In this work, we theoretically and experimentally reveal that many GNNs aggregation schemes boost node representation bias under topology bias. Furthermore, we develop simple yet effective graph refinement method, named FairGR, to achieve fair prediction.
E DATASET STATISTICS
The data statistical information on three real-world datasets, including Pokec-n, Pokec-z, and NBA, provided in Table 2 It is seen that the sensitive homophily is even higher than label homophily coefficient among three real-world datasets, which validates that real-world datasets are usually with large topology bias.
Table Statistical Information on Datasets
Dataset
# Nodes
Node Features
# Edges
# Training Labels
# Training Sens
Label Homop
Sens Homop
Pokec-n
66569
265
1034094
4398
500
73.23%
95.30%
Pokce-z
67796
276
1235916
5131
500
71.16%
95.06%
NBA
21242
156
39.22%
72.37%
F TRAINING ALGORITHMS
We summarize the training algorithm for FairGR and provide the pseudo codes in Algorithm
Algorithm 1: FairGR Algorithm
Input :Graph topology A, label y, and sensitive attribute The total epochs T;; Hyperparameters a and 3.
Output:Thh fair graph topology A.
for epoch 1 to T do
Calculate the gradient (C(A|s.yA),
0Å
Update graph topology À using gradient descent;
Project graph topology A into feasible region;
end
G MORE EXPERIMENTAL RESULTS
G.1 MORE SYNTHETIC EXPERIMENTAL RESULTS
In this subsection, we provide more experimental results on different covariance matrix. Although theory is only derived for the same covariance matrix, still observe similar results for the case of different covariance matrix. For node attribute generation, we generate node attribute with Gaussian distribution A ((1, Σ) and N N( Σ) for node with binary sensitive attribute, respectively,
1 0
where fn [0, 1), in
[1,0] and Σ adjacency matrix generation scheme in Section 6.
We adopt the same evaluation metric and
0 2
Figure 4 shows the DP difference during message passing with respect to sensitive homophily coefficient for different initial covariance matrices. We observe that a higher sensitive homophily coefficient generally leads to larger bias enhancement. Additionally, higher graph connection density Pa. larger node number n, and balanced sensitive attribute ratio c correspond to higher bias enhancement, which is consistent with our theoretical analysis in Theorem 2
19

---

Under review as a conference paper at ICLR 2023
0.15
DP Differance
0.10
Are Low6o
Ain Lindi
Difference
0.10
Difference
0.1
0.05
0.00
0.00
-0.1
-0.05
-0.05
c.03
-0.10
-0.10
-0.3
0.70
0.95 Homophily
1.00
0.70
0.95
1.00
0.70
Homophily 1.00
Sensitive Homophily
Figure 4: The difference of demographic parity for message passing with different initial covariance matrices. Left: DP difference for different graph connection density Pa with sensitive attribute ratio 0.5 and number of nodes 10 Middle: DP difference for different number of nodes n with sensitive attribute ratio 0.5 and graph connection density 10 Right: DP difference for different sensitive attribute ratio with graph connection density pa 10 and number of nodes 10
Pokec
Pokec z
NBA
72.5
65.0
67.5
66
64-
62.5
+2
60
57.5
55.0
56
10
Hyperparameter
Hyperparamttrr
Hyperparameter
5-
4.5
4.0
3.5
8 3-
8 2.5
2
2.0
15
0.5
10
2
10
2
10
Hyperparattelee mweeeeeeeeeeeeeeee
Hyperparamelelt
Hyperparameler
Figure 5:
Ablation study on hyperparameter ar in terms of DP and Acc across different GNN
backbones on three real-world datasets.
G.2 ABLATION STUDY FOR FAIRGR
For investigating the effect of hyperparameters a and B, we conduct experiments with different hy- perparameters chosen from a {0.0, 0.1, 0.5, 1.0, 5.0, 10.0} and (0.0, 0.1, 0.5, 1.0, 5.0, 10.0) while the other one is selected as default. The default value for hyperparameters a and 3 are 0.1 and 0.5, respectively. The results of hyperparamter study with respect to and are shown in Figures and 6 respectively. From these results, we can obtain the following observations:
Hyprparameter a and 3 demonstrate different influences on GNN backbone. For example, for Pokec-n dataset, hyperparameter only shows a negligible influence on the accuracy of GCN and GAT, while significant for GAT. As for DP, the bias metric is more sensitive to a compared with accuracy.
Hyprparameter a and 3 demonstrate different influences on graph dataset. For example, GAT achieves the best accuracy and lowest DP with a 0.1 in NBA dataset, while achieving the lowest accuracy and highest DP in Pokec-n dataset. Such observation indicates the importance of hyperparameter tuning for different datasets.
G.3 VANILLA TRAINING BEHAVIORS FOR GNNS AND MLP
For vanilla training across different GNN backbones, we plot the training curve with respect to epochs investigate the training behaviors for GNNs and ML.. For the training behavior, GNNs,
20

---

Under review as a conference paper at ICLR 2023
Pokec n
Pokec z
NBA
72.5
72.5
68
66
67.5
67.5
62.5
62.5
57.5
57.5
56
Hlyperparameter
Hyperparameter
Hyperparameter
3.5
35
30
25
2.0
20
1.5
15
10
Hyperparameter P
Hyperparameter 8
Hyperparameter
Figure 6: Ablation study on hyperparameter ,3 in terms of DP and Acc across different GNN backbones on three real-world datasets.
Pokec
Pokec
NBA
63-
60
55-
55
55
50
50
150
spachs
spachs
15-
10
50
100
150 spochs
200
250
300
50
100
150
200
250
300
50
1:00
150 epochs
200
250
500
epochs
Figure 7: Accuracy (top) and DP (bottom) training curve w.r.t. epochs for different backbones, including GAT, GCN, SGC, and MLP, on three real-world datasets.
and MLP models both converge in terms of accuracy for the high label homophily dataset Pokec-n and Pokec-z dataset. For high sensitive homophily Pokec-n and Pokec-z dataset, GNNs demonstrate higher prediction than that MLP, while the prediction bias difference is relatively small for the wwsseesiiiveehomophhee dataset NBA.
G.4 FAIRGR RESULTS ON VANILLA TRAINING
For vanilla training, Figure 8 shows the test accuracy and demographic parity curve during training for different GNNs backbones and whether FairGR is adopted for graph topology rewire. From these results, can obtain the following observations:
Different GNNs demonstrate different accuracy and demographic parity performance. For example, for Pokec-n dataset, GCN has the highest accuracy performance and lowest demographic parity, which implies that message passing also matters even for the same graph topology.
Our proposed FairGR consistently achieves lower demographic parity and comparable accuracy performance on all datasets and backbones.
21

---

Under review as a conference paper at ICLR 2023
Pokec
Pokec Z
NBA
70
70
65
65
60
55
Faral Let
50
200
50
50-
45
150
apochs
opachs
35
Reid) EXT
Rx-dh Ext
ALASS
Lanel uc3
25
20
10-
100
150
200
250
300
100
150 opachs
200
250
300
epochs
epochs
Figure Accuracy (top) and DP (bottom) training curve w.r.f. epochs for different backbones, including GAT, GCN, SGC, and MLP,, on three real-world datasets.
Pokec
Pokec z
NBA
10
Figure 9: DP and Accuracy trade-off performance on three real-world datasets, including Poken-n, Pokec-z, and NBA, in (manifold) Fair Mixup setting.
G.5 TRADROFF PERFORMANCE ON FAIR MIXUP
We also demonstrate that FairGR can achieve better tradeoff performance for different GNN back- bones with Fair mixup (Chuang & Mroueh 2021) in Figure Specifically, since input fair mixup requires calculating model prediction for mixed input batch, it is non-trivial to adopt input fair mixup in our experiments on the node classification task. This is because, for GNN aggregations of neigh- borhoods' information, the neighborhood information we adopt manifold fair mixup for the logit layer in our experiments. Experimental results show that FairGR can achieve better accuracy- -airrcc tradeoff performance for many GNNs backbones on three datasets.
the mixed input batch is missing. Instead,
H FUTURE WORK
There are two lines of follow-up research directions. Firstly. The generalization of the theoretical analysis on why aggregation enhances bias in GNN can be further extended. As pilot study, we theoretically investigate why this phenomenon happens for GCN-like aggregation under random graph topology generated by stochastic block model and Gaussian mixture feature distribution. The more general analysis of other aggregation operations, random graph models, and other feature distributions can be extended. The other line focuses on the graph topology rewire algorithmic perspective, including improving the efficiency of FairGR and effectiveness via designing different objectives for graph topology rewire.
22


Reviews:
[{"review_id": "dphyyu9vW3A", "reviewer": "Reviewer_qbDf", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "In this article, the authors propose to study and improve fairness in graph neural networks. More precisely, they provide conditions under which the graph aggregation steps increase prediction biases, and they propose an optimization problem that allows to find an optimal graph topology that reduces biases while preserving topology information. They finally demonstrate the efficiency of their approach on several experiments.", "summary_of_the_review": "Overall, the paper looks good to me, even though I am no expert in graph neural networks.", "strength_and_weaknesses": "Strengths:\n---The paper is overall well written but a bit hard to follow\n---To my knowledge, it addresses an interesting problem about graph neural nets\n---The experiments are convincing\n\nWeaknesses:\n---Some parts of the method have a little bit of a heuristic feeling; for instance, I am wondering if other models could be used (instead of gaussian mixtures) for random graphs? Is there a reason (other than mathematical computations) for using such random models?\n---Similarly, there is no discussion about the optimization properties of (2). Would it be possible to show some kind of convergence results, or to prove anything concerning the limit point?\n---Graph topology is often characterized with persistent homology. Are there links between the proposed optimization scheme and recent papers about topology optimization based on persistence diagrams? (see for instance http://proceedings.mlr.press/v139/carriere21a.html) It would be nice to add some discussion on this point.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cI7CyaGob6", "reviewer": "Reviewer_bTV8", "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": "", "summary_of_the_paper": "This paper proposes a way to solve the problem that GNNs tend to increase Bias. First, the authors give a mathematical interpretation of why GNNs increase Bias. Based on the causes obtained from this interpretation, we propose a method to suppress the increase in bias that occurs during message passing. Experimental results showing the effectiveness of the method are also presented.", "summary_of_the_review": "Issues related to Bias are important issues in AI operations, and the fact that GNNs tend to increase Bias is problematic, and it is a very important task to analyze these factors and then present improvement methods. The analysis of the causes of GNNs increasing Bias seems justified, and the improvement methods are highly convincing.\n\nOn the other hand, since the quality of the structure since the proposal of the methodology is in a low state and the information to evaluate the methodology is unclear, the text should first be refined and the evaluation of the methodology should be clarified. We believe this will result in something that can be made public.\n\n**Conclusion following discussion with the authors**\n\nThe problems with the sentence structure that were hindering my understanding have been largely remedied. As noted before, the value of the methodology itself is positive. For this reason, I am raising the score.", "strength_and_weaknesses": "Weakness\n- The biggest problem is that the content is not complete, especially after Section.4. This makes the evaluation of the proposed methodology difficult. If we try to interpret and understand what is written in a favorable manner, we can assume that the claims are probably correct, but we cannot accept them as being of publishable quality. I think the assignment settings and methods are interesting and should be evaluated carefully after they are completed.\n- Specifically, the major problems are as follows\n\t- I'm not sure what equation (2) means, but since it seems to be an optimization problem, perhaps\n$$\\min L s.t.\\tilde{A}={ij}\\in\\{0,1\\}$$\nwhere $L=H1+\\alpha H2+\\beta H3$?\n\t- Regarding Table 1, it says \"To validate the effect of bias enhancement of GNNs,\" but it is not a comparison with the proposed method. The intent may be to confirm the current status, but in that case the text is confusing, and furthermore, there should be a separate comparison with the proposed method.\n\t- Figure. 6 is reffered, but it is not appropriate to refer the figure in the suppliment. Figure.3 may be correct instead of Figure.6. It seems that a comparison with the proposed method may be more appropriate for the content in one piece. Therefore, it may be appropriate and intended to publish Fig. 6 in the main body. However, even in that Fig. 6, two of the three are compared to the proposed method, but the quality of the remaining one is poor, with no comparison.\n\t- It may not be required, but it is not reader friendly to have RELATED WORK at the end.", "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": "Wb0YDNJVe4", "reviewer": "Reviewer_K1rB", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper studies prediction bias amplification of graph neural networks using contextualized stochastic block model. Specifically, their analysis utilizes a distribution distance as bias measurement and discusses when $\\Delta$ bias is enhanced regarding homophily edge ratio, graph size and density. Based on it, the author proposes a regularization framework FairGR to rewire the graph structure and reduce the representation bias. Experiment shows FairGR achieves both good accuracy and low bias. ", "summary_of_the_review": "Overall, the idea of the paper is clear and proposed method is straightforward. My main concern is around the novelty and experiments. First of all, the representation bias is not that different with other homophily understanding on GNNs. Second, the selected datasets cannot convince that proposed method is significant for fairness learning: (1) GNN is not better than MLP on accuracy (2) I suspect the bias of FairGR is still larger than MLP.", "strength_and_weaknesses": "Strength:\n1. The analysis is theoretically sound with appropriate discussion and remarks.\n2. The proposed FairGR coupled with proposed representation bias closely.\n\nWeakness:\n1. The motivation of FairGR is unclear. From Table 1, we observe GNN is just on par or slight better than MLP while the fairness measure is a lot worse. Does that mean Fair learning on GNN is not necessary on these datasets ? Furthermore, whether the proposed FairGR can reduce $\\Delta_\\text{DP}$ and $\\Delta_\\text{EO}$ to the level of MLP in Table 1.\n2. A lot of notations in the paper are not clear or assuming readers with relevant knowledge. For example, in definition 2, \"random graph sampled from ()\", after reading the whole paper, I realize the generalization process is exact the contextual stochastic block model (CSBM), it is very confusing in this definition about how A and X are generated. \n3. The novelty is limited. Based on my understanding, if we treat sensitive feature as the only node feature, the paper's contribution is not that different from [1][2], which both talks about GNN's concentration property. \n[1] IS HOMOPHILY A NECESSITY FOR GRAPH NEURAL NETWORKS? ICLR 22'\n[2] Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization ICML 21'", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "US9iQcKl4Tw", "reviewer": "Reviewer_SmbS", "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": "", "summary_of_the_paper": "This paper studies the problem of fairness-aware learning on graphs from the perspective of graph topology. According to the authors, this is the first work that theoretically understands the different roles graph statistical information played in the node representation bias amplification during message passing. Then a graph refinement method FairGR is proposed based on the theoretical results to reduce the sensitive homophily accordingly. \nExperiments on both synthetic and real-world datasets show the effectiveness of FairGR by achieving better tradeoff performance over three representative baselines.\n", "summary_of_the_review": "In summary, my concerns are mainly from two aspects:\n* The scalability of FairGR could be further demonstrated through complexity analysis. The sensitivity of hyperparameters should be addressed.\n* The details of experimental setups could be further explained for more convincing empirical support to the theoretical foundations.\n", "strength_and_weaknesses": "Strengths:\n* The investigation of fairness-aware message-passing from the topology view is interesting.\n* The theoretical foundations on node representation bias amplification are concrete with insights. Experiments are carefully designed and are conducted on both synthetic and real-world graph datasets.\n* The paper is generally well-written (though with typos and grammar errors) and almost clear everywhere. \n\nWeaknesses:\n* Some typos appear as I walk through the manuscript. For example, by that fact -> by the fact, the last section on page 1; many enhance -> may enhance, the last section on page 5. I suggest the authors do thorough proofreading during the rebuttal.\n\n* The scalability of the proposed FairGR is not demonstrated and the optimization strategy is briefly described without computational analysis, which is important to employ in practical scenarios for graphs with massive nodes. Meanwhile, the sensitivity analysis of hyperparameters $\\alpha$ and $\\beta$ is suggested to be included for better demonstrating the contributions of label homophily coefficient and graph topology perturbation during learning.\n\n* Synthetic experiments from Figure 2 are somehow vague and confusing. Since it shows the DP difference during message passing with respect to the sensitive homophily coefficient, what is the instantiation of GNNs used here for the message-passing process? Does MLP also show similar behavior regarding DP difference and sensitivity homophily here?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject