Fair Graph Message Passing with Transparency
Authors: Zhimeng Jiang
Xiaotian Han
Chao Fan
Zirui Liu
Na Zou
Ali Mostafavi
Xia Hu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Fairness
Transparency
Graph Neural Networks

Abstract: Recent advanced works achieve fair representations and predictions through regularization, adversarial debiasing, and contrastive learning in graph neural networks (GNNs). These methods \textit{implicitly} encode the sensitive attribute information in the well-trained model weight via \textit{backward propagation}. In practice, we not only pursue a fair machine learning model but also lend such fairness perception to the public. For current fairness methods,
how the sensitive attribute information usage makes the model achieve fair prediction still remains a black box. In this work, we first propose the concept \textit{transparency} to describe \textit{whether} the model embraces the ability of lending fairness perception to the public \textit{or not}. Motivated by the fact that current fairness models lack of transparency, we aim to pursue a fair machine learning model with transparency via \textit{explicitly} rendering sensitive attribute usage for fair prediction in \textit{forward propagation} . Specifically, we develop an effective and transparent \textsf{F}air \textsf{M}essage \textsf{P}assing (FMP) scheme adopting sensitive attribute information in forward propagation. In this way, FMP explicitly uncovers how sensitive attributes influence final prediction. Additionally, FMP scheme can aggregate useful information from neighbors and mitigate bias in a unified framework to simultaneously achieve graph smoothness and fairness objectives. An acceleration approach is also adopted to improve the efficiency of FMP. Experiments on node classification tasks demonstrate that the proposed FMP outperforms the state-of-the-art baselines in terms of fairness and accuracy on three real-world datasets. The code is available in {\color{blue}\url{https://anonymous.4open.science/r/FMP-AD84}}.

Under review as a conference paper at ICLR 2023
FAIR GRAPH MESSAGE PASSING WITH TRANSPARENCY
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent advanced works achieve fair representations and predictions through regu- larization, adversarial debiasing, and contrastive learning in graph neural networks (GNNs). These methods implicitly encode the sensitive attribute information in the well-trained model weight via backward propagation. In practice, we not only pursue a fair machine learning model but also lend such fairness perception to the public. For current faimess methods, how the sensitive attribute information usage makes the model achieve fair prediction still remains black box. this work, we first propose the concept transparency to describe whether the model embraces the ability of lending fairness perception to the public or not. Motivated by the fact that current fairness models lack of transparency, we aim to pursue a fair machine learn- ing model with transparency via explicitly rendering sensitive attribute usage for fair prediction in forward propagation. Specifically, we develop effective and trans- parent Fair Message Passing (FMP) scheme adopting sensitive attribute information in forward propagation. In this way, FMP explicitly uncovers how sensitive tributes influence final prediction. Additionally, FMP scheme can aggregate useful information from neighbors and mitigate bias in a unified framework to simultane- ously achieve graph smoothness and fairness objectives. An acceleration approach is also adopted to improve the efficiency of FMP. Experiments on node classifi- cation tasks demonstrate that the proposed FMP outperforms the state-of-the-an art baselines in terms of fairness and accuracy on three real-world datasets. The code is available in https: /anonyoous 4open. sci ence/ r //MMP- AD84
INTRODUCTION
Graph neural networks (GNNs) (Kipf & Welling 2017 Veličković et al.) 2018: Wu et al. 2019
Han et al. 2022a b) are widely adopted in various domains, such as social media mining (Hamilton et all]|]22 (017). ) 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 often inherit or even amplify societal bias from input graph data (Dai & Wang] [022]) The biased node representation largely limits the application of GNNs many high-stake tasks, such as job hunting (Mehrabi et al.) 2021) and crime ratio prediction (Suresh & Guttag 2019). Hence, bias mitigation that facilitates the research on fair GNNs is an urgent need.
Many existing works achieving fair prediction in graph either rely on regularization (Tiag et al. 2022), adversarial debiasing (Dai & Wang 202I), or contrastive learning (Zhu et al., 2020 2021b
Agarwal et al. 2021 Kose & Shen 2022). These methods adopt sensitive attribute information in
training loss refinement. In this way. such sensitive attribute can be implicitly encoded in well-trained model weight through backward propagation. However, only achieving fair model is insufficient in practice since the fairness should also lend perception to the public (e.g., the auditors, or the maintainers of machine learning systems). In other words, the influence of sensitive attributes should be easily probed for public. We name such property for public probing as transparency. Specifically. we provide the following formal statement on transparency in fairness:
Transparency in fairness: Onlookers can verify the released fair model with
Transparent influence: How and if the sensitive altribute information influence fair model prediction.

---

Under review as a conference paper at ICLR 2023
Less is more: The required resources to obtain the influence of sensitive attributes only includes well-trained model and test data samples
From auditors' perspective, even though the fairness metric for machine learning model low, such fair model is still untrustful if the auditors cannot understand how the sensitive attributes are adopted to achieve fair prediction given the well-trained model. From maintainer's 's perspective, is important to understand how the model provide fair prediction. Such understanding could help maintainers improve models and further convince auditors in terms of fairness. In summary, transparency aims to make fairness implementation understandable. The transparency aims to make the process of achieving fair model via sensitive attribute informations white- box P Therefore, the maintainers and auditors both get benefits from model transparency. More importantly, similar to intrinsic explainability of the model 5 the fairness with transparency property is binary, i.e., the prediction model either embrace the faurness with transparency or not.
Based on the formal statement on transparency in fairness, the key rule to determinate whether a fair model is transparent is that the model prediction difference under the cases with and without sensitive attribute information can be identified given the well-trained fair model and test data samples. Unfortunately, many existing fairness works, including regularization, adversarial debiasing, and contrastive learning, do not satisfy transparency requirements in practice. For example, the fair model trained based on existing works are not with transparent influence. This because the sensitive attribute is implicitly encoded in well-trained model weight. Therefore, it is intractable to infer how sensitive attribute influence the cell-trained model weight without access the dynamic model training process. Additionally, for fair model obtained from existing works, the required resources for transparent influence includes training data and training strategy so that the influence of sensitive attributed can be probed via detecting well-trained model weight difference. In nutshell, the current fair models based on loss refinement lack of transparency. A natural question is raised:
Can we find fair prediction model with transparency?
In this work, we provide a positive answer via chasing transparency and fairness in message passing of GNNs. The key idea of achieving transparency to explicitly adopt sensitive attribute message passing (forward propagation). Specifically, we design an fair and transparent message passing scheme for GNNs, called fair message passing (FMP). First, we formulate an optimization problem that integrates fairness and prediction performance objectives. Then, we solve the formulated problem via Fenchel conjugate and gradient descent to generate fair-and- and-pedddettive representation. We also interpret the gradient descent aggregation first and them debiasing. Finally, we integrate FMP in graph neural networks to achieve fair and accurate prediction for node graph classification task. Further, we demonstrate the superiority of FMP by examining its effectiveness and efficiency, where we adopt the property of softmax function to accelerate the gradient calculation over primal variables.
In short, the contributions can be summarized follows:
We consider fairness problem from a new perspective, named transparency, i.e., the sensitive attribute should be easily probed for public. We point out that many existing fairness method cannot achieve transparency.
We propose FMP to achieve fairness with transparency via using sensitive attribute information in message passing. Specifically, we use gradient descent to chasing graph smoothness and faimess in a unified optimization framework. An acceleration method is proposed to reduce gradient computational complexity with theoretical and empirical validation.
The effectiveness and efficiency of FMP are experimentally evaluated on three real-world datasets. The results show that compared to the state-of-the-art our FMP exhibits superior trade-off between prediction performance and fairness with negligibly computation overhead.
'A naive way for many existing works (e.g.. adding fair regularization, adversarial debiasing. et.al.) obtain the influence of sensitive attribute is to train fair and unfair model with/without the sensitive attribute information, and then get the prediction difference. Therefore, the required resources includes training data and additional (unfair) model training.
Similar with the goal model explainability, only achieving accurate prediction is insufficient, and chasing explainability can help experts understand how the model provide prediction and convince users. Decision tree is intrinsic explainable while deep neural networks is not.
2

---

Under review as a conference paper at ICLR 2023
2 PRELIMINARIES
2.1 NOTATIONS
We adopt bold upper-case letters to denote matrix such as X, bold lower-case letters such as x to denote vectors, calligraphic font such as A' to denote set. Given matrix X R= the i-th row and j-th column are denoted as X, and .. and the clement in i-th row and j-th column is X1.j-
We use the Frobenius norm, 4 norm of matrix X as |X|| = VV X and |X||| Eig [Xigl
respectively. Given two matrices X, Y E Raxd the inner product is defined as (X, Y) tr(X Y), where tr(-) is the trace of square matrix. SF(X) represents softmax function with default normalized column dimension. Let G = {V.E} be a graph with the node set V {uz,... ... } and the undirected edge set {er. .......... ..m ]. where n, represent the number of node and edge, respectively. The graph structure G can be represented
adjacent matrix A R=*n where A. if existing edge between node v; and node vy. (V)) denotes the neighbors of node o; and (1) = (i) U { denotes the self-inclusive neighbors. Suppose that each node is associated with d-dimensional feature vector and a (binary) sensitive attribute, the feature for all nodes and sensitive attribute are denoted as X Rnxd and s E {-1,1}". Define the sensitive attribute
1x)(s) incident vector A₂ { >o normalize each sensitive attribute group, where (s) is an element- wise indicator function.
[=
2.2 GNNS AS GRAPH SIGNAL DENOISING
A GNN model is usually composed of several stacking GNN layers. Given graph G with N nodes, a GNN layer typically contains feature transformation Xtrans (X.rs) and aggregation X agg Sagg (trans (9), where Xori E RRxxd.., Xtrans: Xagg E R represent the input and output features. The feature transformation operation transforms the node feature dimension, and feature aggregation, updates node features based neighbors' features and graph topology. Recent works (Ma et al., 2021b, Zhu et al. 2021a) have established the connections between many feature aggregation operations in representative GNNs and a graph signal denoising problem with Laplacian regularization. Here, we only introduce GCN/SGC as an examples to show the connection from a perspective of graph signal denoising. The more discussions are elaborated in Appendix G Feature aggregation in Graph Convolutional Network (GCN) or Simplifying Graph Convolutional Network (SGC) is given by X Xagg = AXtranss where A = D AD + is normalized self-loop adjacency matrix À A I, and D is degree matrix of Á. Recent works (Ma et al. 2021b Zhu et al. 2021a)) provably demonstrate that such feature aggregation is equivalent to one-step gradient descent to minimize (r (I- F) with initialization F Xtrans-
3 FAIR MESSAGE PASSING
In this section, we propose a new message passing scheme to aggregate useful information from neighbors while debiasing representation bias. Specifically, we formulate fair message passing optimization problem to pursue smoothness and fair node representation simultancously. Together with an effective and efficient optimization algorithm, we derive the closed-form fair message passing. Finally, the proposed FMP is shown to be integrated fair GNNs at three stages, including transformation, aggregation, and debiasing step, shown in Figure 1
3.1 THE OPTIMIZATION FRAMEWORK
To achieve graph smoothness prior and fairness in the same process, a reasonable message passing should be good solution for the following optimization problem:
>a min (F F 2
LF) + 2 IIF - Xtrans 12+
(I)
h.(F)
by (A..F(()))
3

---

Under review as a conference paper at ICLR 2023
where L represents normalized Laplacian matrix, h, and hy)+) denotes the smoothness and faimess objectives respectively, and Xtrans E Raxdaut is the transformed dimeennnnn node features and E R nxx is the aggregated node features of the same matrix size. The first two terms preserve the similarity of connected node representation and thus enforces graph smoothness. The last term enforces fair node representation so that the average predicted probability between groups of different sensitive attributes can remain constant. The regularization coefficients and Ay adaptively control the trade-off' between graph smoothness and fairness.
Smoothness objective h, (.). The adjacent matrix in existing graph message passing schemes is normalized for improving numerical stability and achieving superior performance. Similarly, the graph smoothness term requires normalized Laplacian matrix, i.e., L = I- A = D AD and A A + I. From edge-centric view, smoothness objective enforces connected node representation to be similar since tr (FF'FFFF (i.ee))e the degree of node U...
1.2 where d, Σx A& represents dd,+1
F,
Fairness objective hy(-). The fairness objective measures the bias for node representation after aggregation. Recall sensitive attribute incident vector Ag indicates the sensitive attribute group and group size via the sign and absolute value summation. Recall that the sensitive attribute incident
vector As []soselli []>o(-s)]i
1>a(s)
1>0(-s) and SF(F) represents the predicted probability for node
classification task, where SF(F),; P(y j|X). Furthermore, can show that our fairness
objective is actually equivalent demographic parity, i.c.. (A,FF(F)))
P(y j
X. P(ys jls; X). Please see proof in Appendix B In other words, our faimness objective, norm of (FFF(F) characterizes the predicted probability difference between two groups with different sensitive attribute. Therefore, our proposed optimization framework can pursue graph smoothness and fairness simultancously.
3.2
AL.GORITHM FOR FAIR MESSAGE PASSING
For smoothness objective, many existing popular message passing scheme can be derived based on gradient descent with appropriate step size choice (Ma et al. [021bb Zhu al.) (2021a). However, directly computing the gradient of the fairness term makes the closed-form gradient complicated since the gradient of norm involves the sign of elements the vector.
3.2. BI-LEVEL OPTIMIZATION PROBLEM FORMULATION.
To solve this optimization problem in more effective and efficient manner, Fenchel conjugate (Rockafellar 2015) is introduced to transform the original problem as bi-level optimization problem. Fenchel conjugate (Rockafellar 2015) (a.k.a. convex conjugate) is the key tool transform the original problem into bi-level optimization problem. For the general convex function h(-), its conjugate function is defined as h²( A sup x) - (XX). Based on Fenchel conjugate, the fairness objective can be transformed variational representation hy(p) = sup(p, u) - h2 (u).
where p SF(F( Ixduu is a predicted probability vector for classification. Furthermore, the original optimization problem is equivalent to
min max /tg (F) + (p. u) (T)
where u E IR Ixdout and h,).) ()
is the conjugate function of faimesss objective hy(.).
3.2.2 PROBLEM SOLUTION
Motivated by Proximal Alternating Predictor Correettorrrrr (PAPC) (ooris & Verhoeven 2011 Chen et al. 2013), the min-max optimization problem (2) be solved by the following fixed point
'Such smoothness objetive is the the most common-used one in existing methods (a et al 202 Belkin
& Niyogi 2001 Kalofolias 2016). The various other smoothness objectives could be considered to improve the nerformance of FMP and we leave it for future work.
4

---

Under review as a conference paper at ICLR 2023
equations
Vh, dip.u) F
pr u A OF
where proX;; (u) arg min ly u hf) Similar to "predicttor-correctoo"" algorithm Loris
Verhoeven 2011). we adopt iterative algorithm to find saddle point for min-max optimization problem. Specifically, starting from (F" )²), we adopt a gradient descent step on primal variable F to arrive (F u²) and then followed by a proximal ascent step the dual variable u. Finally, to arrive at (Fk+1, .²). In short, the
gradient descent step primal variable in point (Fk-1, u²)
iteration can be summarized as
F++1 Fk. Vh,,FF 7 ((p.u²) OF u =+1 prox sh;; (u BB..5FF (FFk+11111 Fl+1 = F - -Vh, a(p.u OF
(4)
F
where y and I are the step size for primal and dual variables. Note that the close-form for 0ip.u) Runxdou and proxsh; (-) are still not clear, we will provide the solution one by one.
OF
Proximal Operator. As for the proximal operators, provide the close-form in the following proposition:
Proposition 1 (Proximal Operators) The proximal operators prox (u) satisfies
prox (u), = sign(u)) min (lugl:>y).
(5)
where sign(.) and X3 element-wist sign function and hyperparameter for fairness objective. In other words, such proximal operator element-wise projection onto 1.3 ball with radius Xy.
FMP Scheme. have
Similar to works (Ma et al.
2021b
Liu et al. 2021), choosing I+x, and
F (F*) (1--)) T2,L) F* + Xtann = Xtrans + (1 7)) (6)
Therefore, we can summarize the proposed FMP as two phases, including propagation with skip connection (Step 1 and bias mitigation (Steps @-0). For bias mitigation, Step @ updates the aggregated node features for fairness objective; Steps 2 and O aim to learn and "reshape" perturbation vector in probability space, respectively. Step ① explicitly mitigate the bias of node features based on gradient descent on primal variable. The mathematical formulation is given as follows:
X agg
Xtrans + A
Step
p++1
X k+1 - a(p.u*)
Step
u + (F Pk
agg
oF
b+1
Step
b+1
-iin [ |, As
Step
pb++1 = x 8( 8(p.u
Step 5
where X represents the node features with normal aggregation and skip connection with the transformed input Xtrans-
3.2.3 GRADIENT COMPUTATION ACCELERATION
The softmax property is also adopted accelerate the gradient computation. Note that p SFFFF) and 5F)() represents softmax over column dimension, directly computing the gradient 0ip.ui on chain rule involves the three-dimensional tensor ØF we simplify the gradient computation based on the property of softmax function the following theorem.
OF based
äp with gigantic computation complexity. Instead,
5

---

Under review as a conference paper at ICLR 2023
Input
Prediction
Propagation
Debiasing
Xori
Xtrans
X Xagg
MLP
Male Perturbation
Female Perturbation
Softmax
Fomale
Femals Mcan
pres
Jacobian Transformation
Figure 1: The model pipeline consists of three steps: MLP (feature transformation), propagation with skip connection and debiasing via low-rank perturbation in probability space.
Theorem (Gradient Computation)
The gradient over primal variable 0pp.u) OF
satisfies
@pp. u) OF
U. & SF(F) - Summ (U, SF(F)))F(())
where U. AJu. O represents element-wise product and Sum,(-) represents the summation over column dimension with preserved matrix shape.
3.3 DISCUSSION ON FMP
In this section, provide the interpretation and analyze the transparency, efficiency, and effectiveness of proposed FMP scheme. Specifically, we interprete FMP as two phrases, including conventional aggregation and bias mitigation, and the computation complexity of FMP is lower than backward gradient calculation.
Interpretation Note that the gradient of fairness objective over node features F satisfies a(p.u) a(p.u) aSF(F) OSF(F) OF and a(p.u) Softmax transformation, perturbation in probability space, and debiasing in representation space. Specifcally, we first map the node representation into probability space via softmax transformation. Subsequently, calculate the gradient of faimess objective in probability space. It is that the perturbation J u actually poses low-rank debiasing in probability space, where the nodes with different sensitive attribute embrace opposite perturbation. In other words, the dual variable represents the perturbation direction in probability space. Finally, the perturbation in probability space will be transformed into representation space via Jacobian transformation OSF(F)
OF (SF(F) A, u, such gradient calculation can be interpreted as three steps:
Transparency The proposed FMP explicitly uses the sensitive attribute information in Steps 2-6 during forward propagation. In other words, if aims to identify the influence of sensitive attributes for FMP, it is sufficient to check the difference between the input and output for debiasing step. It is worth mentioning that the required information for identifying the influence of sensitive attributes are naturally from the forward propagation. However, for the fair model from existing works (e.g, adding regularization and adversarial debiasing), note that the sensitive attribute information is implicitly encoded in the well-trained model weight, the sensitive attribute perturbation inevitably lead to variability of well-trained model weight. Therefore. it required to retrain the model for probing the influence of sensitive attribute perturbation. The key drawback of these methods is due encoding the sensitive attributes information into well-trained model weights. From aditors' perspective, is quite hard to identify the influence of sensitive attributes only given well-trained fair model. Instead,

---

Under review as a conference paper at ICLR 2023
Table 1: Comparative Results with Baselines on Node Classification.
Pokee-z
Pokoc-n
NBA
Model
Acc (%)
App (%) 4 Ago (%).
Asc (%)
App (%)
Ago (%) 4
(%6
App (%)
Ago (%)
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
GCN
71.78 1.37
4:
4:
0.28
+:
4:
61.90 4: 1.00
23.70 d: 17.50
2.63
SGC
71.24
0.46
4,81
# 0.30
4.79 + 2.27
71,46
0.41
2.22 + 0.29
3.85 +: 1.63
63.17 : 0.63
22.56
3,94
14.33# 2.16
APPNP
66.91
+ 1.46
3.90
+ 0.69
5.71
# 1.29
69.80
0.89
1.98
= 1,30
4.01 +: 2.36
63.80 + 1.19
26.51
+ 3.33
20.00 4.56
FMP
70.50 0.50 0.81 + 0.40
1.73 + 1.03 72.16 0.33 0.66 + 0.40 1.47 + 0.87
73.33 + 1.85
18.92 +: 2.28
13.33 + 5.89
our designed FMP explicitly adopts the sensitive attribute information in the forward propagation process, which naturally avoid the dilemma that sensitive attributes are encoded into well-traine model weight. In a nutshell, FMP encompasses with higher transparency since (1) the sensitive attribute is explicitly adopted in forward propagation; (2) It is not necessary to retrain model for probing influence of sensitive attribute.
Efficiency FMP is an efficient message passing scheme. The computation complexity for the aggregation (sparse matrix multiplications) (mdoou)) where m is the number of edges in the graph. For FMP, the extra computation mainly focus on the perturbation calculation, as shown Theorem | with the computation complexity O(noou)). The extra computation complexity is negligible in that the number of nodes is far less than the number of edges m in the real-world graph. Additionally, if directly adopting autograd to calculate the gradient via back propagation, we Øp have to calculate the three-dimensional tensor OF with computation complexity Onndout)) ). In other words, thanks to the softmax property, we achieve an efficient fair message passing scheme.
The proposed FMP explicitly achieves graphs smoothness prior and fairness via alternative gradient descent. In other words, the propagation and debiasing forward in a white-box manner and there is not any trainable weight during forwarding phrase. The effectiveness of the proposed FMP is also validated in the experiments on three real-world datasets.
Effectiveness
4 EXPERIMENTS
In this section, we conduct experiments to validate the effectiveness and efficiency of proposed FMP. We firstly validate that graph data with large sensitive homophily enhances bias in GNNs via synthetic experiments. Moreover, for experiments on real-world datasets, we introduce the experimental settings and then evaluate our proposed FMP compared with several baselines in terms of prediction performance and fairness metrics.
4.1 EXPERIMENTAL SETTINGS
Datasets. We conduct experiments on real-world datasets Pokec-z, Pokec-n, and NBA DDai & Wang 202I). Pokec-z and Pokec-n are sampled, based on province information, from a larger Facebook-like social network Pokec (Takac & Zabovsky (012) in Slovakia, where region information is treated as the sensitive attribute and the predicted label is the working field of the users. NBA dataset extended from a Kaggle dataset Cooasiittinnniniinnn of around 400 NBA baskethall players. The information of players includes age, nationality, and salary in the 2016-2017 season. The players' link relationships is from Twitter with the official crawling API. The binary nationality (U.S. and overseas player) is adopted as the sensitive attribute and the prediction label is whether the salary is higher than the median.
Evaluation Metrics. We adopt accuracy to evaluate the performance of node classification task. As for fairness metric, adopt two quantitative group fairness metries measure the prediction bias. According to works (Louizos et al. 2015) Beutel et al. 2017). we adopt demographic parity and equal opportunity A = [P[ 1
ADP [P(j = - Plu

---

Under review as a conference paper at ICLR 2023
Pokec-n
Pokco-Z
NBA
PILAR
Beg Cie
20
000
300
300
Figure 2: DP and Acc trade-off performance three real-world datasets compared with adding regularization (Top) and adversarial debiasing (Bottom). The trade-off curve more close to right bottom corner means better trade-off performance [
-,,y 1) ( 1|s y 1)}, where y and y represent the ground-truth label and predicted label, respectively.
Baselines. We compare our proposed FMP with representative GNNs, such as GCN (Kipf & Welling 2017). GAT /Veličković al., 2018). SGC (Wu et al. 2019). and APPNP (Kliepera et 2019), and MLP. For all models, we train 2 layers neural networks with 64 hidden units for 300 epochs. Additionally, We also compare adversarial debiasing and adding demographic regularization methods to show the effectiveness of the proposed method.
Implementation Details. We run the experiments 5 times and report the average perfor- mance for each method. We adopt Adam optimizer with 0.001 learning rate and 10-5 weight decay for all models. For adversarial debiasing, we adopt train classifier and adver- sary with 70 and 30 epochs, respectively. The hyperparameter for adversary loss is tuned in {0.0, 1.0, 2.0, 5.0, 8.0, 10.0, 20.0, 30.0). For adding regularization, we adopt the hyperparameter set (0.0, 1.0, 2.0, 5.0, 8.0, 10.0, 20.0, 50.0, 80.0, 100.0).
4.2 EXPERIMENTAL RESULTS
Comparison with existng GNNs. The accuracy, demographic parity and equal opportunity metrics of proposed FMP for Pokec-z, Pokec-n, NBA dataset are shown in Table[compares with MLP, GAT, GCN, SGC and APPNP. The detailed statistical information for these three dataset is shown in Table From these results, we can obtain the following observations:
Many existing GNNs underperorm MLP model on all three datasets in terms of fairness metric. For instance, the demographic parity of MI. lower than GAT, GCN, SGC and APPNP by 32.64%. 50.46%, 66.53% and 58.728 58%72% on Pokec-z dataset. The higher prediction bias comes from the aggregation within
nodes and topology bias in graph data.
Our proposed FMP consistently achieve lowest prediction bias in terms of demographic parity and equal opportunity all datasets. Specifically, FMP reduces demographic parity by 49.69%. 56.86 56.86% and 5.97% compared with the lowest bias among all baselines in Pokec-z, Pokec-n, and NBA dataset. Meanwhile, our proposed FMP achieves the best accuracy in NBA dataset, and comparable accuracy in Pokec-z and Pokec-n datasets. In a nutshell, proposed FMP can effectively mitigate prediction bias while preserving the prediction performance.
Comparison with adversarial debiasing and regularization. To validate the effectiveness of proposed FMP, we also show the prediction performance and fairness metric trade-off compared with fairness- fairness-boosting methods, including adversarial debiasing (Fisher et al., 2020) and adding regularization (Chuang & Mrouch, 2020). Similar to (Louppe al.] (017), (017), the output of GNNs is the input of adversary and the goal adversary is to predict the node sensitive attribute. We also adopt several backbones for these two methods, including MI., GCN, GAT and SGC. We randomly split
8

---

Under review as a conference paper at ICLR 2023
10%/25%% 225% for training, validation and test dataset. Figure shows the pareto optimality curve for all methods, where right-bottom corner point represents the ideal performance (highest accuracy and lowest prediction bias). From the results, we list the following observations as follows:
Our proposed FMP can achieve better DP-Acc trade-off compared with adversarial debiasing and adding regularization for many GNNs and MLP. Such observation validates the effectiveness of the key idea in FMP: aggregation first and then debiasing. Additionally, FMP can reduce demographic parity with negligible performance cost due transparent and efficient debiasing.
Message passing in GNNs does matter. For adding regularization or adversarial debiasing, different GNNs embrace huge distinctionwhich implies that appropriate message passing manner potentially leads to better trade-off performance. Additionally, many GNNs underperforms MLP low label homophily coefficient dataset, such as NBA. The rationale is that aggregation may not always bring benefit in terms of accuracy when the neighbors have low probability with the same label.
5 RELATED WORKS
Graph neural networks. GNNs generalizing neural networks for graph data have already been shown great success for various real-world applications. There are two streams in GNNs model design, i.e., spectral-basee based and spatial-based. Spectral brest GNNs provide graph convolution definition based on graph theory, which is utilized in GNN layers together with feature transformation (Bruna et al.] 20133] Defferrard et al. 2016 Henaff et al. 2015). Graph convolutional networks (GCN) (Kipf & Welling, 2017) simplifies spectral-based GNN model into spatial aggregation scheme. Since then, many spatial-based based GNNs variant are developed to update node representation via aggregating its neighbors' information, including graph attention network (GAT) (Veličković et al. 2018), GraphSAGE (Hamilton et al. 2017), SGC (Wu et al. 2019), APPNP (Klicpera al. 2019),,
(Gao et al. 2018 Monti et al. 2017). Graph signal denoising is another perspective to understand GNNs. Recently, there are several works show that GCN equivalent to the first-order approximation
for graph denoising with Laplacian regularization (Henaff et al.) 2013) Zhao & Akoglu 2019). The
unified optimization framework are provided unify many existing message passing schemes (Ma
et al. 2021b Zhu et al. 202
Fairness-aware learning on graphs. Many works have been developed to achieve fairness in
machine learning community (Jiagg al. 2022. Chuang & Mrouch| 2020; Zhang al., [2018 Du
et al. 2021 Yurochkin & Sun 2020 Creager et al. 2019: Feldman et al. 2015). A pilor study on fair
node representation learning is developed based random walk (Rahman al. 2019). Additionally, adversarial debiasing is adopt to learn fair prediction or node representation so that the well- vell-trained adversary can not predict the sensitvie attribute based on node representation or prediction (Dai & Wang] 2021 Bose & Hamilton 2019 Fisher et al. 2020). A Bayesian approach is developed to learn fair node representation via encoding sensitive information in prior distribution in (Buyl & De Bie 2020). Work (Ma et al.] (021a) develops a PAC-Bayesian analysis to connect subgroup generalziation with accuracy parity. (Laclau et al., 2021 Li et al. 202T) aim to mitigate prediction bias for link prediction. Fairness-awarr graph contrastive learning are proposed in (Agarwal et al., [2021] Köse & Shen 202I). However, aforementioned works ignore the requirement of transparency in fairness. In this work, we develop an efficient and transparent fair message passing scheme explicitly rendering sensitive attribute usage.
6 CONCLUSION
In this work, we consider fairness problem from a new perspective, named transparency, i.e., the influence of sensitive attribute should be easily probed to public. We point out that existing fairness model in graph lack of transparency due to implicitly encoding sensitive attribute information in well- trained model weight. Additionally, integrated in unified optimization framework, we develop an efficient, effective and transparent FMP to learn fair node representations while preserving prediction performance. Experimental results on world datasets demonstrate the effectiveness and efficiency compared with ofate-of-the-aad baselines in node classification tasks.
9

---

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 arXiv:2102.13186 2021.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, 14, 2001.
Alex Beutel, Jilin Chen, Zhe Zhao, and Ed H Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint
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 graphs. arXiv preprint 1rXi::13/2.6203 2013.
Maarten Buyl and Tijl De Bic. Debayes: bayesian method for debiasing network embeddings. In International Conference on Machine Learning, pp. 1220-1229. PMLR, 2020.
Peijun Chen, Jianguo Huang, and Xiaoqun Zhang. A primal- fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Problems, 29(211 2013.
Ching-Yan Yao Chuang and Youssef Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
Ching-Yar Yao Chuang and Youssef Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2021.
Elliot Creager, David Madras, Jörn-Herrik 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 graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844-3852, 2016
Mengnan Du, Subhabrata Mukherjee, Guanchu Wang, Ruixiang Tang, Ahmed Hassan Awadallah, and Xia Hu. Fairness via representation neutralization. arXiv preprint arXiv:2106. 2021.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubra- manian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 259 2699226,,11 2015.
Joseph Fisher, Arpit Mittal, Dave Palfrey, and Christos Christodoulopoulos. Debiasing knowledge graph embeddings. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 7332-7345, 2020.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In 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 out-of--nnoledgeebass entities: graph neural network approach. arXiv preprint 2017.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
10

---

Under review as a conference paper at ICLR 2023
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, pp. 1-9. PMLR, 2022a.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, Qingquan Song. Jundong Li, and Xia Hu. Geometric graph representation learning via maximizing rate reduction. In Proceedings of the ACM Web Conference 2022, pp. 1226-1237, 2022b.
Mikacl Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph-structured data. arXiv preprint arXiv: 00006005533,,, 2015.
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.
Vassilis Kalofolias. How to learn graph from smooth signals. In Artificial Intelligence and Statistics, pp. 920-929. PMLR, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Deniz Kose and Yanning Shen. Fair node representation learning via adaptive data augmentation. arXiv preprint 4rX55:2001.08549, 2022.
Öykü Deniz Köse and Yanning Shen. Fairness-aware node representation learning. arXiv preprint vrXi::2/06.05391, 2021.
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 on Learning Representations, 2021.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference Machine Learning, pp. 6839. PMLR, 2021.
Ignace Loris and Caroline Verhoeven. On generalization of the iterative soft theshhhdrsno algorithm for the case of non-separable penalty. Inverse Problems, 27(12)1120007, 2011.
Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel. The variational fair autoencoder. arXiv preprint urXiv:1511.000 2015.
Gilles Louppe, Michael Kagan, and Kyle Cranmer. Learning to pivot with adversarial networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp- 982-99 1222991,22 2017.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34, 2021a.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 1202-1211, 2021b.
Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
11

---

Under review as a conference paper at ICLR 2023
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.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. 2019.
Ralph Tyrell Rockafellar. Convex analysis. Princeton university press, 2015.
Harini Suresh and John V Guttag. A framework for understanding unintended consequences of machine learning. arXiv preprint /rXiv:/901.10000 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.
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 on 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- 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 AI, Ethics, and Society, pp. 335- 340, 2018
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint urXiv:/909 00009./2222... /2223, 2019.
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with optimization framework. In Proceedings of the Web Conference 2021, pp. 1215-1226, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML. Workshop Graph Representation Learning and Beyond, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. Proceedings of the Web Conference 2021, pp. 2069-2080, 2021b.
12

---

Under review as a conference paper at ICLR 2023
A NOTATIONS
Table 2: Table of Notations
Notations
Description
[3]
The number edges The number of nodes
The number of node feature dimensions
dout
The number of node classes
A, E IR Ixn
The sensitive attribute incident vector
Glabel
Label homophily coefficient
Sensitive homophily coefficient
Ceens
Xori E Rxx
The input node attributes matrix
A E R
The adjacency matrix
A E R=xn
The adjacency matrix with self-loop
E Roxn
The normalized adjacency matrix with self-loop
L R
The Laplacian matrix
X trans E RRxxdou
The output node features for feature transformation
F oggg E Ruxduu
The aggregated node features after propagation
F gaxdout
The learned node features considering graph smoothness and fairness
R Lxdout
The permutation direction in feature representation space
(-)
Fenchel conjugate function of f1()
|X
Ir, |X|11
The Frobenius norm and norm matrix X
Xg. X
Hyperparameter for fairness and graph smoothness objectives
B PROOF ON FAIRNESS OBJECTIVE
The fairness objective can be shown as the average prediction probability difference follows:
(A.SF(B)) =
[o)|ll || 1sso(ss)ll (SF(F)),.
1s)(s)
-x P(y: -|X)
-x, Ply: =(
|| ||
||~00(-s]
P(u = j|s; = 1, P(ys = =jss; = -).
C PROOF OF THEOREM
Before providing in-depth analysis on the gradient computation, we first introduce the softmax function derivative property in the following lemma:
Lemma For the softmax function with N-dimensional vector input y SF(x) : IIIN
e3 RIXN, where Yj Et et for Vj E (1,2..... the derivative N N Jocobian matrix is ayy defined by Laxlij Ox,' represents N N identity matrix and denotes the transpose operation for vector or matrix.
oy: Additionally, Jocobian matrix satisfies 8x
By yIN -Ty, where In
0y for arbitrary ij, according to quotient and chain rule of Proof: Considering the gradient 0x, derivatives, we have
0y: x: Ek=ret x 0x (ENTexy exx)
Σ 2x ex
y.(1 -1,),
(8)
Σ exs
Dk=1 exa
Similarly, for arbitrary + j. the gradient is given by
θy:
ex
exx
-y.jj.
(9)
0xj
ΣN
ex
ΣN
Dk=1
exa
13

---

Under review as a conference paper at ICLR 2023
Combining these cases, it is easy verify the Jocobian matrix satisfies dy yIN y yy. y.
Arming with the derivative property of softmax function, we further investigate the gradient a(p.u) where p - (FFF(F) E 1xxdo and (-) and E IR 1dlxs is independent with F E IRuxd
UP
Considering softmax function SF(x) E Raxd is row-wise adopted in node representation matrix, the gradient satisfies aSF(F); Od Xdout for # j. Note that the inner product (p. u) = =>en P&uk (1p.u) OF
OF;
it is easy the obtain the gradient
Σ dous 0pk Ug.
k=1 OF
To simply the current notation, we denote F SF(F). According to chain rule of derivative, we have
0pk OF
doet
Opk
OF
dout
OF (a)
F (M) OF
OF Fi
A 8,1 OF
8,
(o
F.yl.
(10)
where day is Dirac function (equals only if k: j, otherwise 0:), equality (a) holds since softmax function is row-wise operation, and equality (b) is based on Lemma Furthermore, we can obtain the gradient of fairness objective w.r.t node presentation follows:
O(p OF
dasu
0pk OF,
dout
dont
(u(o, F,ylux = Ds, A F
Ug- (11)
1=
kj
Therefore, the matrix formulation is given by
a(p.u. u) OF
U Sum, (U, @ (F(F)))FF().
(12)
where U, A u Raxdout and Sum; represents the summation over column dimension with
preserved matrix shape. Therefore, the computation complexity for gradient Ø(p.u) is (ndoa)).
OF
D PROOF OF PROPOSITION
We firstly show the conjugate function for general norm function f(x) = A/ where x E R Xxdett The conjugate function of [xx satisfies
((y)
-())= +00,
x S A x
(13)
A.
where ||x||+ is dual norm of the original norm ||x|]. defined as ||yl|- = max y Considering the |
conjugate function definition (y) max >||x||| the analysis can be divided the following two cases:
If |y||+ < X, according to the definition of dual norm, we have Tx < |*||||||+ < A||x|| for V |. where the equality holds if and only if ||x|| = 0. Hence, it is easy to obtain f"(y)
max y x A||x|| 0.
If |||||+
X, note that the dual norm ||y||- max y X, there exists variables x so that ||x IS1
| < 1 and
x y < Therefore, for any constant f, we have f*(y 2 y T (tx) - A||tx|| =
t(y x X|| 1 oc.
Based on aforementioned two cases, is easy to get the conjugate function for l norm (the dual norm is 1,,,, i.e., the conjugate function for h >|
x is given by
0,
| 0c < X |
hy(y) = +00,
(14)
0c
> X.
Given the conjugate function h.((), we further investigate the proximal operators prox Note that
prox (u) arg min ||y -ul3 (u) arg min |yll
|yy ull arg min y;
Dow ly
y
VJe(doue]
14

---

Under review as a conference paper at ICLR 2023
uyl the proximal operator problem can be decomposed element-wise sub- sub-problem, i.e., ny (u), arg min [y; - u sign(uj) min([uy]:Ap} Y,
which completes the proof.
E TRAINING ALGORITHMS
We summarize the training algorithm for FMP and provide the pseudo codes in Algorithm
Algorithm 1: FMP Training Algorithm
Input :Graph dataset = (X, A, Y); The total epochs T: Hyperparameters A and Ay- Output: well-trained FMP model.
for epoch from to T do
Conduct feature transformation using MLP:
Conduct propagation and debiasing steps 1-6
Calculate the cross entropy loss for node classification task; Conduct back propagation step update model weight;
end
F DATASET STATISTICS
For fair comparison with previous work, we perform the node classification task on three real- world dataset, including Pokec-n, Pokec-z, and NBA. The data statistical information on three real-world dataset is provided Table [ It is seen that the sensitive homophily are even higher than label homophily coefficient among three real-world dataset, which validates that the real-world dataset usually with large topology bias.
Table Statistical Information on Datasets
Dataset
Nodes
# Node Features
Edges
Training Labels
Training Sens
Pokec-n
66569
265
1034094
4398
500
Pokec-z
67796
276
1235916
500
NBA
403
95
21242
156
246
G
MORE DISCUSSION ON GNNs AS GRAPH SIGNAL DENOISING
In this section, we provide more examples show many existing GNNs can be interpreted as graph signal denoising problem, including GAT and APPNP.
GAT. Feature aggregation in GAT applies the normalized attention coefficient to compute linear combination of neighbor's features as X = Ejev(r)) aty XtraXera...j. where æi = so softmaz,(es) (Es)). eú LeakyReL.U trane, W, + X iranns, wj). and w; and wj learnable column vectors. Prior study (Ma et al., 2021b) demonstrates that one-step gradient descent with adaptive step size Escrialestes) for the following objective problem:
PPNP/APPR (1 (1-1-)0 a) Xirans and X k++1 = (1 a) Ax + aXtrans- It is shown that they are agg
Feature aggregation in PPNP and APPNP adopt the aggregation rules as Xagg
( (I-(1-
equivalent the exact solution and one gradient descent step with stepsize g minimize the following objective problem:
min F X Xtrans 1 a
1)tr A)F)
15

---

Under review as a conference paper at ICLR 2023
Pokec-n
Pokec-Z
NBA
24
Tex
123
715
122
123
726
125
206
705
12.9
715
1200
735
150
30
25
ACC
ACC
ACC
Figure 3: DP and Ace trade-off performance on three real-world datasets compared with (manifold) Fair Mixup.
H MORE EXPERIMENTAL RESULTS
H.1 MORE EXPERIMENTAL SETTING DETAILS
In FMP implementation, first use 2 layers MLP with 64 hidden units and the output dimension for MLP 2. We also stack layers for propagation and debiasing steps, where there is not adopt cross entropy loss function
any trainable model parameters. As for the model training, with 300 epochs. We also adopt Adam optimizer with 0.001 learning rate and x 10 weight decay for all models. The hyperprameters for FMP is A5 50 10, 15, 20, 30, 1003 and X {0, 0.01, 0.1, 0.5, 1.0, 2.0, 3, 5, 10, 15, 20}
H.2 COMPARISON WITH FAIR MIXUP
We also implement Fair mixup CChang & Mroueh 2021 as the additional baseline for different GNN backbones in Figure 3 Note that input fair mixup requires calculating model prediction for mixed input batch, it is non-trivial to adopt input fair mixup forward propagation in GNN aggregates information from neighborhoods while the neighborhood information for the mixed input batch is missing. Therefore, we adopt manifold fair mixup for the logit layer (the previous layers contain aggregation step) in our experiments. Experimental results show that our method can still achieve better accuracy-fairnes tradeoff performance on three datasets.
experiments (node classification task) since
H.3 SENSITIVE ATTRIBUTE INFLUENCE PROBE
As for lending fairness perceptron, represents the influence of sensitive attributes could be identified. For example, our proposed FMP includes three steps, i.e., transformation, aggregation and debiasing, where the sensitive attribute explicitly adopted in debiasing step. If we aims to identify the influence of sensitive attributes for FMP, it is sufficient to check the difference between the input and output for debiasing step. It worth mentioning that the required information for identifying the influence of sensitive attributes naturally from the forward propagation. Additionally, if aim identify the influence of sensitive attributes for existing methods (e.g, adding regularization and adversarial debiasing), the well-trained fair model is insufficient and we need additional vanilla (unfair) model without using any sensitive attribute information. In other words, these methods require model retraining with sensitive attribute removement and thus much more resources for sensitive attributes influence auditing. The key drawback of these methods is due to encoding the sensitive attributes information into well-trained model weights. From auditors' perspective, the influence of sensitive attributes only given well-trained fair model. Instead, our designed FMP explicitly adopts the sensitive attribute information in the forward propagation process, which naturally avoid the dilemma that sensitive attributes encoded into well-trained model weight.
quite hard identify
Figure 4 shows the visualization results for training with/without (left/right) sensitive attribute for FMP and several baselines (with GCN backbones) across three real-world datasets. From the visualization results, we observe that all methods with sensitive attribute information achieve better faimess since the logit layer representation for different sensitive attributes
mixed with each other. Therefore, it is hard to identify the sensitive attribute based on the representation and thus leads to higher fairness results. The key different that the results for training with/without (left/right)
16

---

Under review as a conference paper at ICLR 2023
Pokec
Pokec
NBA
FMP
Reg
Adv
Fair Mixup
Figure 4: The visualization of node representation for training with/without (left/right) sensitive attribute for FMP and several baselines across three real-world dataset. The data point with different colors represents different sensitive attributes.
Vanilla
Regularization
Adversarial Debiasing
Running time (5)
Running time (15
AMM1 PYP
FVF
HPP
Rurning
Felt
Fileca
Figure 5: The running time comparison.
sensitive attribute in FMP can both obtained through the forward propagation, while the other baseline methods requiring model retraining probe the influence of sensitive attributes.
H.4 RUNNING TIME COMPARISON
We provide running time comparison in Figure for our proposed FMP and other baselines, including vanilla, regularization and adversarial debiasing on many backbones (MLP, GCN, GAT, SGC, and APPNP). To achieve fair comparison, we adopt the same Adam optimizer with 200 epochs with 5 running times. We list several observations as follows:
The running time of proposed FMP is very efficient for large-scale dataset. Specifically, for vanilla method, the running time of FMP is higher than most lighten backbone MLP with 46.9 46.97% and 15.03% time overhead on Pokec-n and Poken-z z dataset, respectively. Compared with the most time- consumption APPNP, the running time of FMP lower with 64.07 64.07% and 41.45% time overhead on Pokec-n and Poken-z dataset, respectively.
The regularization method achieves almost the same running time compared with vanilla method on all backhones. For example, GCN with regularization encompasses higher running time with 6.41% time overhead compared with vanilla method. Adversarial debiasing is extremely time-consuming. For example, GCN with adversarial debiasing encompasses higher running time with 88.58% time overhead compared with vanilla method.
17

---

Under review as a conference paper at ICLR 2023
Pokec
Pokec
NBA
72.
700
575
10.5
2
55.
344 bo
Ro bube oo
Sal co
Figure 6: Hyperparameter study on fairness and smoothness hyperparameter for demographic parity and Accuracy.
H.5 HYPERPARAMETER STUDY
We provide hyperparameter study for further investigation on faimess and smoothness hy- perparmeter on prediction and fairness performance on three datasets. Specifically, we tune hyperparameters (0.0, 0.1, 0.5, 1.0, 3.0, 5.0, 10.0, 20.0). From the results in Figure 6 lowing observations:
Xy {0.0. 5.0, 10.0, 15.0, 20.0, 30.0, 100.0, 1000.0) and X we can make the fol-
The accuracy and demographic parity are extremely sensitive to smoothness hyperparameter. It is seen that, for Pokec-n and Pokec-z datasets (NBA), larger smoothness hyperparameter usually leads to higher (lower) accuracy with higher prediction bias. The rationale is that, only for graph data with high label homophily coefficient, GCN-like aggregation with skip connection is beneficial. Otherwise, the neighbor's 's node representation with different label will mislead representation update.
The appropriate fairness hyperparameter leads better fairness and prediction performance tradeoff. The reason is that faimesss hyperparameter determinates the perturbation vector up- date step size in probability space. Only appropriate step size can lead to better perturbation vector update.
I BROADER SOCIAL IMPACT AND LIMITATIONS
Transparency is advanced property in faimess domain and poses huge challenging for research and industrial. Many existing works mainly rely on specific faimesss metric to evaluate the prediction bias. The transparency may stimulates maintainers and auditors of machine learning system rethink the fairness evaluation/auditing. Only achieving fair model with lower bias for specific fairness metric is insufficient. The maintainers should also consider how to leverage the influence of sensitive attribute for auditors. The transparency may lead maintainers pay more effects in improving the transparency of fair model and could helpful to convince the auditors. The limitations of this work are that requests sensitive information in the inference stage.
18


Reviews:
[{"review_id": "uLRO1F8AwHE", "reviewer": "Reviewer_QgmT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper follows two separate trains of thought.\nThe first is on advocating for the idea of transparency w.r.t. how a given model produces fair predictions. The authors define transparency as explicitly using the sensitive attribute in forward propagation.\nThe second, and main point, is the development of a Fair Message Passing (FMP) method. According to the paper's results, FMP seems to outperform the chosen baselines on every point of the fairness-accuracy trade-off.", "summary_of_the_review": "Overall, some non-trivial modifications are needed for the paper to be ready for publication, namely: honing down focus and presentation efforts on the FMP method, adding well-known baselines from the fairness literature, and correcting English writing.", "strength_and_weaknesses": "_Strengths_\n\n- The FMP method outperforms the chosen baselines;\n- Literature on fair representation learning specifically for GNNs is scarce, therefore the paper tackles an arguably under-explored field;\n\n\n_Weaknesses_\n\n- The concept of _transparency_ is somewhat arbitrary and not fully clear. The authors claim a \"formal definition\" in page 1, but what follows is arguably subjective.\n    - Is it just that a model is \"transparent\" if it uses sensitive attribute information in its decision-making process? Usually the opposite condition (not explicitly using the sensitive attribute) is targeted in methods from the literature. It's known that sensitive attribute information is redundantly encoded on any sufficiently-rich real-world dataset. Using this information explicitly or not is not novel, and its not clear which choice is best (it actually depends heavily on the specific real-world task and context). A significative part of the paper is dedicated to this concept of transparency which seems quite trivial.\n    - In the context of deep learning, even by explicitly using sensitive attribute information in the forward pass, this in no way brings us closer to understanding exactly _how_ the sensitive attribute information is used to produce predictions in a human-understandable manner.\n\n- Baselines are limited. Arguably the simplest fairness intervention you can use is that of [Hardt et al. (2016)](https://proceedings.neurips.cc/paper/2016/file/9d2682367c3935defcb1f9e247a97c0d-Paper.pdf). Adding this thresholding-based post-processing step to the GNN baselines would be an easy-to-obtain baseline for comparison with the more complex method presented here.\n    - Usually there is a clear fairness-performance trade-off in every task/dataset. If FMP achieves the best fairness, I find it hard to believe that it would achieve the best performance as well. This signals baselines weren't properly selected (e.g., using a simple GNN + thresholding post-processing or other fairness interventions).\n- Experiments were repeated 5 times and the final results averaged, which is a positive. However variance is not shown in Figure 2, and it is not used to compute whether differences in fairness/performance are statistically significative.\n    - For instance, the NBA dataset is quite small, and large variance between experiment runs is expected;\n\n_Other notes_\n- Table 1, the bold on the FMP method is not correct as it does not achieve the highest performance;\n    - Bold on EO of FMP on the NBA dataset is also not correct;\n- The formula given for DP and EO is the absolute difference in probabilities; as such the y-axis of the plots in Figure 2 should be between 0 and 1; if it is in percentage than this should be explained in the legend or caption;\n- Figure 2 caption has a footnote \"6\" that I cannot find in the paper;", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "n1CXefeLPJz", "reviewer": "Reviewer_RsB6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the fairness problem from a new perspective, named transparency, i.e., the influence of sensitive attribute should be easily probed by the public, and propose a novel method named FMP to achieve fairness with transparency via using sensitive attribute information in message passing. To accelerate the training process, the paper proposed an accelerated method to reduce gradient computational complexity with theoretical and empirical validation.", "summary_of_the_review": "It is good to work with great novelty, but experiments should be more sufficient.", "strength_and_weaknesses": "Strength:\n\n1. Consider the fairness problem from a new perspective, and develop a transparent method named FMP to learn fair node representations while preserving prediction performance, which has generalization.\n\n2. The code is available, and the results can be reproduced.\n\n3. The model is effective according to to reduce gradient computational complexity with theoretical and empirical validation.\n\nWeakness:\n\n1. This paper compares some classic methods such as APPAP, SGC, etc., but lacks some comparisons of SOTA methods.\n\n2. If more general datasets could be compared such as Cora, citeseer, etc. It would be better. \n\n3. The scale of NBA datasets is small, with only 400 nodes. The performance improvement on NBA datasets cannot provide enough experimental support.\n\n4. Limited performance improvement. In table 1, the experimental results of marking black are not the best performance. For example, under datasets pokec-z, although the other two indicators improved, GCN has the best AUC.  If possible, please offer the statistical significance test of your model.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Kz-3B62Pdn", "reviewer": "Reviewer_Sogu", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposes Fair Message Passing (FMP). It builds on Graph Signal Denoising, e.g., as described in (Ma et al., 2021b). The methods described in previous works are extended by adding an additional fairness term ($h_f$ in Eq. (1)) to the optimization problem that governs the feature aggregation step of the GNN. An efficient, iterative algorithm for solving this optimization problem is derived. The main motivation and promise of FMP is to explicitly uncover how sensitive attributes influence the model predictions and explicitly render sensitive attribute usage in the forward computation of the GNN. The authors dub this notion \"transparency in fairness\". FMP is compared to popular (fairness unaware) GNN baselines as well as adversarial debiasing and demographic regularization methods on 3 datasets (also used in prior work): Pokec-n, Pokec-z, and NBA.", "summary_of_the_review": "In summary, it seems to me that the paper presents some technical contributions, but I don't find them very well-motivated and am not sure if the evaluation is convincing and thorough enough. I also have minor concerns about some elements of the paper exposition (esp. in Section 3).", "strength_and_weaknesses": "\n## Strengths\n\n* The paper is clearly written and well-structured, which facilitates its understanding and readability.\n* It concerns fairness in GNNs, which in my opinion is still relatively underexplored topic.\n* The informally proposed \"transparency in fairness\" is conceptually nice and can potentially inspire further studies in the intersection between fairness and explainability.\n* To the best of my understanding, the paper extends prior work in intuitive yet mathematically non-trivial way.\n\n## Weaknesses, Questions and Concerns\n\nMy main concerns are about the motivation of this work and how it relates to the experimental evaluation. I also have questions about some of the technical details.\n\n### Experiments\n\n1. The paper suggests that the main experimental setup is similar to that of (Dai & Wang, 2021). If this is the case, then FairGCN and FairGAT (Table 3, Dai & Wang, 2021) seem to outperform FMP (Table 1 of this work) in terms of fairness while the accuracy stays similar or slightly lower. The difference in the results is especially large for the NBA dataset. This comparison is entirely missing from the current version of the paper. If the experimental setup in (Dai & Wang, 2021) differs from that of FMP, it is not made clear how, in what way and why.\n2. In general, the cited references for the adversarial debiasing (Fisher et al., 2020) and regularization (Chuang & Mroueh, 2020) methods, which FMP is compared to, seem to not consider GNN fairness, i.e., they have been applied to other datasets and domains. I would rather see comparison to fairness aware methods which are more relevant and have been applied to the GNN fairness domain before. Obvious candidates for that are the aforementioned FairGCN and FairGAT from (Dai & Wang, 2021), but the authors also cite other GNN fairness works in the Related Works section.\n3. According to the Introduction, a primary motivation of this work is \"to make the process of achieving fair model via sensitive attribute informations white-box\" such that \"the maintainers and auditors both get benefits from model transparency\". Moreover, the paper claims that \"chasing explainability can help experts understand how the model provide prediction and convince users\". Yet, there is no experimental evaluation how \"transparent\" FMP actually is, what information about the model it elucidates and how useful and convincing FMP is for the users or model designers.\n\n### Motivation\n\n4. The paper provides a \"formal statement on transparency in fairness\" in the Introduction, but to me it is rather high-level and informal. I am not aware of a formal mathematical framework or metric that evaluates how transparent a given model is.\n5. A selling point of FMP is that it \"uncovers how sensitive attributes influence final prediction\" and that this is not possible for prior black-box models which \"implicitly encode the sensitive attribute information in the well-trained model weight via backward propagation\". However, there have been tools such as GNNExplainer (Ying et al., NeurIPS 2019), PGExplainer (Luo et al., NeurIPS 2020), etc., which aim in generating explanations for GNNs. Given the connection to explainability (as mentioned in the paper), I would be interested to know if these tools can be repurposed in the context of \"Transparency in fairness\" proposed by the authors, but discussion of that is also missing.\n6. According to the introduction, \"The biased node representation largely limits the application of GNNs in many high-stake tasks\", but the provided citations (Mehrabi et al., 2021, Suresh & Guttag, 2019) do not make it clear how GNNs are currently being used in such tasks. In particular, it is not clear what kind of bias the authors aim to mitigate until the reader reaches the experimental section. Is it topology bias, is it representation bias, does the bias comes from the fact that the sensitive attributes are encoded/embedded/included in the input features or the learnt representations? I would suggest to make this more explicit and bring it up somewhere earlier in the paper.\n\n### Technical Details\n\n7. Without reading prior works (I referred to (Ma et al., 2021b) for a general background), it is not clear that the model solves the optimization problem in Eq. (1) for every GNN layer (to the best of my understanding). It is not entirely obvious what $\\mathbf{F}$ denotes and at times sections 2 and 3 can be a bit confusing in sense that it is not clear what is plugged when and where in the model.\n8. The authors experiment with GNNs with maximum 2 layers. If my assumption from above is correct that Eq. (1) is solved for every GNN layer, it is not obvious to me why the fairness term $h_f$ should be integrated in every layer of the GNN and not only in the last one which provides the predictions. If we talk about solving Eq. (1) for the intermediate layers, I don't understand why we would take the softmax $SF(\\mathbf{F})$ of them. There seems to be some possible confusion arising here for me.\n9. To the best of my understanding, the FMP method described in Section 3 is only concerned with the _aggregation_ step of the GNN model. However, hypothetically, it should be possible that some bias and unfairness can also arise from the feature transformation steps, but these are not discussed or mentioned in the paper. Thus, it is hard for me to judge the generality and the applicability of FMP.\n10. In particular, the end of Section 3 says that \"the propagation and debiasing forward in a white-box manner and there is not any trainable weight during forwarding phrase\" and I don't understand why this is the case (e.g., if there is feature transformation involved, see $\\mathbf{W}$ in Algorithm 1 of (Ma et al., 2021b)).\n11. Section 3.2 says that \"directly computing the gradient of the fairness term makes the closed-form gradient complicated since the gradient of $l_1$ norm involves the sign of elements in the vector\". The gradient of the $l_1$ norm can be tractably computed and I don't entirely understand why the closed-form is absolutely required. E.g., how does it affect the optimization problem if we also try to optimize it with gradient descent (esp. given that $\\text{sign}(\\mathbf{u})$ is used in Eq. (5))?\n\n### Minor\n\nSome typos, the optimization problem for GAT in App. G seems to be missing and there are some other minor issues related to the paper readability.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H7Gb--KETQN", "reviewer": "Reviewer_hAa7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose to study the problem of fair node classification on graphs through the angle of “transparency”. They characterize transparency as the ability to verify models - (i) by quantifying the influence of the sensitive attribute in model prediction and (ii) obtaining such quantification using the trained model and test data samples. They point out critical flaws in the existing graph fairness methods in that such models encode the fairness property implicitly in the trained model weights and therefore don’t trivially adhere to the second aforementioned property. They propose a two-step framework that accounts for both graph aggregation and debiasing, to optimize for eq 1. To ensure the aggregation procedure over the graph, they leverage the connection between aggregation in certain GNNs and one-step gradient descent to minimize a particular function stated in section 2.2. To ensure fairness, they leverage the Fenchel conjugate of the fairness objective function. Eventually, this converts the problem into a Bi-level optimization which is solved using alternating optimization given by the fixed-point equations in eq 3. A closed-form operation for the proximal operator is provided which finally converts the optimization procedure into the proposed FMP scheme provided on page 5. A gradient acceleration trick is also suggested to compute the partial derivative of $<p,u>$ w.r.t $F$. Experiments on popular graph fairness datasets suggest that the proposed scheme is indeed better as compared to GNN baselines (without any fairness objectives) as well as to previously proposed SOTA graph fairness methods.\n", "summary_of_the_review": "Based on the questions, comments and concerns raised in the previous sections, I lean towards weak acceptance of the work.\n", "strength_and_weaknesses": "1. The results provided in table 1 and figure 2 are indeed strong. The proposed FMP scheme clearly outperforms all the baselines.\n2. The runtime comparison results are quite convincing. The proposed method indeed holds value in that the runtime vs performance tradeoff is good.\n3. There are various typos in the text writeup as well as in some equations. I strongly encourage the authors to thoroughly read the paper again.\n4. If the authors are talking about the proximal operator commonly used in optimization, then the definition of proximal operator in the first paragraph of page 5 is incorrect. It should be ${h^*}_{f}(y)$. Based on this, the proof of proposition 1 seems to have some flaws. Also, the projection in eq 5 seems “into” the ball rather than “onto”.\n5. The authors mention that - “directly computing the gradient of the fairness term makes the closed-form gradient complicated since the gradient of $l_1$ norm involves the sign of elements in the vector”. This is the rationale behind the proposed bi-level optimization framework. Perhaps, some experiment to compare their method against the standard $l_1$ norm gradient computation, will be helpful to verify the efficacy of their method.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject