Stable Fair Graph Representation Learning with Lipschitz Constraint
Authors: Qiang Chen
Zhongze Wu
Xiu Su
Xi Lin
Zhe Qu
Shan You
Shuo Yang
Chang Xu
Venue: ICML 2025 poster (2025)
Keywords: graph neural network
fairness
stability
Primary area: deep_learning->graph_neural_networks
TL;DR: We address training instability in fair GNNs by introducing Lipschitz constraint and distributionally robust optimization, leading to more stable and reliable model performance.

Abstract: Group fairness based on adversarial training has gained significant attention on graph data, which was implemented by masking sensitive attributes to generate fair feature views. However, existing models suffer from training instability due to uncertainty of the generated masks and the trade-off between fairness and utility. In this work, we propose a stable fair Graph Neural Network (SFG) to maintain training stability while preserving accuracy and fairness performance. Specifically, we first theoretically derive a tight upper Lipschitz bound to control the stability of existing adversarial-based models and employ a stochastic projected subgradient algorithm to constrain the bound, which operates in a block-coordinate manner. Additionally, we construct the uncertainty set to train the model, which can prevent unstable training by dropping some overfitting nodes caused by chasing fairness. Extensive experiments conducted on three real-world datasets demonstrate that SFG is stable and outperforms other state-of-the-art adversarial-based methods in terms of both fairness and utility performance. Codes are available at https://github.com/sh-qiangchen/SFG.

Stable Fair Graph Representation Learning with Lipschitz Constraint
Qiang Chen Zhongze Wu Xiu Su
Xi Lin
Zhe Qu
Shan You
Shuo Yang*
Chang Xu
Abstract
Group fairness based on adversarial training has gained significant attention on graph data, which was implemented by masking sensitive attributes to generate fair feature views. However, exist- ing models suffer from training instability due to uncertainty of the generated masks and the trade-off between fairness and utility. In this work, we propose stable fair Graph Neural Network (SFG) to maintain training stability while preserving accuracy and fairesss perfor- mance. Specifically, we first theoretically de- rive a tight upper Lipschitz bound to control the stability of existing adversarial-bais based mod- els and employ stochastic projected subgradi- ent algorithm to constrain the bound, which op- erates in a block-coordinate manner. Addition- ally, we construct the uncertainty set to train the model, which can prevent unstable training by dropping some overfitting nodes caused by chas- ing fairness. Extensive experiments conducted on three real-world datasets demonstrate that SFG is stable and outperforms other state-of-the-ar adversarial- -ased methods in terms of both fair- ness and utility performance. Codes are available at https//gtthbbccom//-jjaagggeeet
Coec
Owen
Epach
Epoch
(a) Training accuracy curve (b) Accuracy near the optimum
Figure I. Instability the existing adversarial -based model utility German/Bail/Ceeee dataset. (a) visualizes the accuracy curve
in the convergence phase. (b) visualizes the accuracy near the optimal model.
GNNs can suffer from fairness issues that can be divided mainly into individual fairness(Dong et al., 2021) and group fairnes(DDai & Wang, 2021). Group fairness highlights mit- igating bias in the demographic groups defined by sensitive attributes, e.g., gender, race(Agarwal al., 2021). In other words, group fairness concentrates ensuring that the out- puts of GNNs are independent of the sensitive attribute.
Recent studies(Dai & Wang, 2021; Wang et al., 2022; Zhu et al., 2024; et al., 2024) have revealed that the removal of sensitive attribute-related information can force GNNs to make decisions independently of the sensitive attribute. The idea behind most of these approaches is masking sensitive-relevant features by a learnable mask and adopting adversarial learning(Ling et al., 2023) to learn fair node representations. However, in our empirical investigations, we observed that when employing learnable masks and adversarial methods to optimize the framework for both model fairness and utility on real datasets, the training process suffers from significant instability. This instabil- ity results in the selection of an optimal model becoming largely accidental and not trustworthy(Zhang et al., 2024; Jing et al., 2024). As shown in Figure 1, we see that the ac- curacy curve in the convergence phase still very unstable, and the accuracy near the optimal model fluctuates greatly.
1. Introduction
Graph Neural Networks (Kipf)(Kipf & Welling, 2017; Hamilton & Ying, 2017) have recently emerged as cru- cial tool for modeling and representing graph-structured data, which are widely used in various applications such as recommendation systems(Gao et al., 2022) and drug discov- ery(Rozemberezki et al., 2022). Despite significant success,
"Equal contribution 'Central South University, Chang- sha, Hunan, China "Shanghai Jiaotong University, Shanghai, China "SenseTime Research, Shanghai, China "Harbin Insti- tute of Technology (Shenzhen), Shenzhen, China Universitty of Sydney, Sydncy, Australia. Correspondence to: Xiu Su <xiusu
To ensure the reliability of the model in the trade-off be- tween model utility and fairness, maintain the stability of the training process. Most exist- ing methods(Scaman & Virmaux, 2018 8; Zhao et al., 2021; Agarwal et al., 2021; Jia et al., 2024) maintain stability by constraining the Lipschitz bound of the model, which is a separable accumulation form of each component parameter, or using the Jacobian matrix to approximate. These forms
urgently needed
Xi Lin <linxi234@sjtu.cduucom
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
are loose and need tight Lipschitz bound. In the context of GNNs, the Lipschitz constraint is mainly used to control the stability of the GNN encoder(Jia et al., 2023; Juvina et al., 2024; Su et al., 2024), and is not suitable when there are other modules, such as generator in adversarial methods.
between the node and u, and Aue 0 otherwise. For every node v, define its neighborhood (w) the set of nodes such that there exists an edge going from to v. The goal of graph node classification is to learn a representation vector lip of v such that v's label can be predicted as ye = f(h,) E {l,...,C) C). In this work, we focus on the node classification task while learning fair node representations.
In this work, we propose Stable Fair GNN(SFG), a sta- ble graph representation learning framework for preserving fairness while maintaining training stability. We first the- oretically derive an easy-to-compute non-separable upper Lipschitz bound based on GNN message passing mechanism and graph spectral theory for fair graph representation learn- ing. The derived bound can control the overall stability of the GNN encoder and mask generator of adversarial-bases methods, and it's tight compared to separable bound.
Graph Neural Network. Modern GNNs follow the mes- sage passing mechanism (Gilmer et al., 2017), which itera- tively updates the representation of a node by aggregating representations of its neighbors. Formally, node u E V at the i-th layer of a GNN is updated by:
(6) h = ReLu(ug (3) ((-11) + w
Σ MEN(v)
Po.uh(i-1),, (I)
Motivated by our theoretical insights, use a stochas- tic projected subgradient strategy that operates in block- coordinate manner to constrain the weights of adversarial- based fair graph model. This method can convert non-covex problems into multi-convex ones. Additionally, we con- struet the uncertainty set within the chi-squared divergence ball surrounding the generated fair view distribution to enhance encoder robustness, which can prevent unstable training of the encoder by dropping some overfitting nodes caused by chasing fairness. Our contributions are as follows:
where he E R. is the embedding vector of node v at the i-th layer, (f) and w/() are weight matrices in N The activation function for all layers is Relu, which is 1- Lipschitz, except for the last layer. Equation (1) can be expressed under the vector form:
10 = =ReLu(Wo H- + + (1-1)),
(2)
where H( E ERK,, O and w( are matrices with dimensions KN, x KN and the total amount of param- eters remains the same, except that they are tiled K x K times. Thus, we can have follow expression:
To the best of our knowledge, this is the first attempt to study the stability of graph faimess learning with generator. We theoretically derive an easy-to-computt tight upper Lipschitz bound to control the stability of the framework, which is suitable for fair graph model with generator. Based on theoretical insights, we use the block coordinate approach to operate layerwise.
0 Idx 8 w W(") = M & w
(1)
(3)
where @ denotes the standard matrix Kronecker product. It is easy to see that M is graph shift operator(Gama et al., 2020; Jing et al., 2023), such as a normalized I Laplacians matrix, and it is closely related to stable representations.
To further enhance robustness, we construct the uncer- tainty set within the chi-squared divergence ball sur- rounding the generated fair view distribution to avoid overfitting caused by chasing fairness and instability caused by distribution shifts due to generated mask.
Lipschitz Constant. A function f E + R" is said be Lipschitz continuous on an input set X C ER" if there exists bound L 2 0 such that for all 6, X, and 8 is small perturbation of xr satisfies:
We conducted extensive experiments three real- world datasets, demonstrating the superior stability of SFG over the existing adversarial based model FaiVGNN, which outperformed other state-of-the-art fairness models in fairnsss and accuracy performance.
|| f + - ((x) Il L (a +5 - x 1I,
(4)
where || is the distance norm and L is Lipschitz con- stant of the function, denoted as Lip(f). The Lipschitz constant essentially quantifies the maximum change in the output of a function corresponding to a small perturbation in its input. In adversarial-basee fair models, softly masking node features is equivalent imposing a perturbation on the features, the difference of masks can be viewed as 8. Due to the fact that an exact Lipschitz bound is com- putationally expensive Virmaux & Scaman, 2018), recent worksySzegedy et al., 2014; Juvina et al., 2024; Jia et al., 2024) propose some approximate bounds. However, these bounds are loose and only suitable for the GNN encoder.
2. Preliminary
Let G (V, EX denote undirected attributed graph, comprised of a set of [V| = K nodes V = {ur,..,, Ux) and a set of EE'l edges E. X E I represents the nodes features matrix, where No is the dimension of the node feature. A E {0, 1 is the adjacency matrix where Age = 1 indicates that there an edge Eae E E.
2

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
[w,, Ara
(1, 1,,== l|wslll I T Io0 (AWe D- (v6 (A)a
Tight Lipschitz Bound
Hsta()) = Σ.., (((C),,)000)))))))-)))))))))))))
AR Hoghh Race Gunder
EV)
Channel Mask Weight
Multi-view DRO
Chi-squared of Generated Fair View Distribution
Step I
Step II
Step III
Fair Distribution
Lipschitz Constraint
Generator
GNN Encoder
Shrink Distribution Discrepancy
Step IV
Classifter
Discriminator
Lete Lanky
channels
view
Less Lose
view I
view
view
made labet
stochastic projected subgradient
scnsidive attributes
Node label prediction
Adversarial truining
Multi-comvex
view jr
Sensitive attributes prediction
Generate sensitive channel mask
fair node representation
III. stable representation
IV. WdAverrsriial training
Figure 2. The framework of the Stable Fair Graph Neural Net Work(SFG). Compared to Fair FGNN(Waa et al., 2022), our model uses two methods maintain stability. (I) tight Lipschitz bound is derived control fluctuations the representation learned by the encoder and generator. (2) DRO makes the encoder robust to different fair views.
3. Method
of nodes fluctuate dramatically. Obviously, controlling Lipschitz bound is promising direction to keep the model training process stable. Compared to weight climbs of FairVGNN, Lipschitz bound constraint does not lead to suboptimal solutions. Truncating large weights element- wise can weaken the influence of features with significant weights and alter the update direction of parameters(Su al., 2021b), lb), which causes the optimization path to deviate from the true direction guided by the gradients, and these would lead to suboptimal solutions.
In Section 3.1, we theoretically derive tight upper Lips- chitz bound control the stability of a fair graph model. In Section 3.2, employ stochastic projected subgradient algorithm to control the Lipschitz bound in the presence of mask generator, which operates in block-coordinate manner. In Section 3.3, we propose to train the worst-case distribution within the chi-squared divergence ball surround- ing the generated fair view distribution further enhance stability.
Theorem 3.1. Let Y be the output of a mask generator and an m-layer GNN encoder (denoted as f(-)) with X as input. Assuming that the matrix M in Equation (3) symmetric with nonnegative elements and the weights of the mask generator and GNN encoder are also nonnegative, and the activation function (represented in p(-)) is ReLU with a Lipschitz bound of Lip(p) = 1, then the cumulative Lipschitz bound of the mask generator and the GNN encoder, Lip(f), f), satisfies the following:
3.1. Estimating Lipschitz Constant
To analyze the stability the output of the fair graph model, we check the details of these models. As shown in Figure 2, these models typically use generator to create sensitive channel mask, an encoder for learning fair node representa- tion, discriminator for sensitive attribute prediction and classifier for node label prediction. All components above consistently employ the Binary Cross-Entropy (BCE) loss function(Su Su et al., 2021c;d) for optimization. For detailed implementation of these fundamental components in this work, refer Appendix D.5.
(m) Lip(S) =11 (wo (m)
+ Imma (A)w) (m))
(5)
... (1) + Almaa(A)ul (1) Wy lls.
where || Ils denotes the spectral norm, c represents element-wise product supporting broadcast, Wy denotes the weights of mask generator, w and w (i E m....,m)
The uncertainty of generator and the trade-off between model faimesss and utility may lead learned the embeddings
3

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
with just restricting the encoder, SFG can comprehensively consider the uncertainty of the generated mask that the encoder can be robust to different masks. Additionally, our non-separable upper Lipschitz bound is tighter than the separable counterpart. Figure illustrates how the Lips- chitz bound controls the size of the weight variation space, thereby enabling the learning of stable representations.
[|,, oe(" haalden)) D t Reaelile XM
Falmess Objecthro
Fairness Onjectivve
Tight Upschitz Bound Constraint
Vies
Udillt Objective
Mask Uxcertiinty
Unile Objectiv
For detailed proof processes, please refer to Appendix B.2. According to Theorem 3.1, for the low-pass graph filter, h(() = - E [-1, 1] due to the eigenvalue of sym- metric normalized Laplacians matrices À E [0, 2], which corresponds to M = 111 AD 1/2, 2, it is actually Graph- SAGE graph convolution operator using the mean aggrega- tor function. For the high-pass graph filter, l((A) E [0, 2]
Figure 3. Comparison of weights variation space.
are the weights of the GNN encoder, and hyaa (X) is the maximal frequency response of the graph filter from graph spectral theory perspectives, and X is the eigenvalue of symmetric normalized applciann matrix.
and uh 0 for all i E 1..... m. For band-pase pass filter like BernNet(He et al., 2021), h(A) E [o, 1] and w(6) O. Another interesting point is that this approach can somewhat bridge the gap between GNN spatial and spectral domains.
Proof Sketch: The weights of generator and encoder at layer i are represented as Wgg E R and W w(( w(()) respectively. W(t) (U @ (Idx & w h(A) & wi ( (UT @ Id); which is obtained on the basis of the distributive and associative laws of the Kronecker products. Since the dimensions of generator's 's weights do not match encoder's, we cannot multiply them directly. We first form it into a diagonal matrix W,, W E R Nox No, Then we tile it along the diagonal K times and get a matrix Wg E R No K No, which is also a diagonal matrix. This is the most critical step. Finally, we get the following expression:
3.2. Controlling Lipschitz Constant
To control the stability of the output of the fair graph model, we consider maintaining the stability of the GNN encoder with the participation of the mask generator. Specifically, we use a gradient descent algorithm to optimize the generator parameters W2 and the GNN encoder parameters wo(() and ton (x) for all Then after each epoch, consider controlling the Lipschitz bounds of the GNN encoder in the presence of the generated mask. In this work, we study the most widely used GNN, namely GraphSAGE, it satisfies:
W(m) ... ...,,
(U & IdN (Idx @ (m) + M(A) @ w ((m)
... ..ddk & wo (1) + h(A) wi (1) YUT IdNo)W; (6)
(m) + (m)) (wo + w()) O Wy IIsST, (8) (w1g
-U @ IdN (ldx @ w/th (m) + h(A) & w(()))
.I.dkk @ wnd
(1) + h(A) @ w/ W, (U" & IdN.).
where 7 is manually-set thresholds.
Equation (6) showns that k-th block diagonal matrix of eigenvalue matrix of W(m) ... w is (w)r) (m) +
The bound on the product in Equation (8) is a non-convex function, we use a projected stochastic subgradient algo- rithm to optimize the weights, which converts non-convex problem into a multi-convex problem. The detailed pro- cess of parameter constraint is described as follows. At epoch t >> O, we use the layer-wise operating block coor- dinate approach to control the weights, and denote w (1.4) and w: (i.1) as the unconstrained weight matrices for layer at epoch and wa (t) are the mask generator weights and (7) define W(it)) = [w] (6.t) w/ wff. Therefore, Equation (8) can re-express as:
hy (A)w("") (w. + (A)oo So we get our result:
Lip(f) =|| W(m)... ... wWW lls
=I| (m) (m²)
+ +mman (A)er(mi) (mi)
... ...(w))) + hmma (d) W lls
=Il (w) (m) + hhmaw (A)a (m))
... .-(ww) (1) Nimaz (2) @ Wy lls
<| Wy Ils II w (i) + An)an()) lls
A (1.) w(1,)) Blid) I|sS T,
99)
where matrices (1.t) and (lild) represent the product of the cumulative weights for the next and previous layers,
The result shows the Lipsehitz bound of the encoder with the participation of the mask generator weight. Compared
4

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Algorithm 1 The accelerated DFB algorithm with mask
training instability. To further enhance the stability of the fair graph model, we use DRO minimizes the worst-case risk over uncertainty set Q by solving:
generator
Input: ( (6,4) Blett Yo E R (6.0) Initialize: y= 1/(ll =1/(ll A old
llall BRew [1a),, a (2)
min (idoRd = sup ((G....) vell. JE
for i 1 to nit do
QEP(P)
(12)
Ç Ç- 1/(i++++a)
Here the uncertainty set Q approximates potential fair fea- ture view distributions, which is usually formulated as a di- vergence ball with a radius of surrounding the training dis- tribution P(P) = (Q : D(Q, P(Y[G)) Sr} limited with distance metric D(.-)) such as f-divergence(Namkoong et al., 2018). Unless otherwise specified, P or P(Y [G' denotes the dis- tribution of a generated view. In this work, we use x²- divergence as instance of D(-,)), which given by:
Z = Yi + -(-1)
V projo(W - A Ald Z, Z,B "
(1.1)²
y = Zi + (11) ViBliehd (t.1)²
1/ = 9-- - -1pro)ji0o:)0--11
Duchi, 2016) or Wasserstein
end for Return: V/2
respectively:
dQ -pp
(x -
(13)
B(bt) [IN,-1 IN. -. ... (NNo INol O wit) new
Lemma 3.2 (See (Duchi & Namkoong. 2021)). Let Ormin be the ratio between the size of the smallest domain and the size of the training (ataa, is equal to the following expression:
A (5.1) = [IN Iw... W(m.)) w(++1.0 (T:: IN.]
(10)
Accordingly, for the first layer with i 1, we have B B [TN,, No] @ wg
= inf - -.) + +n), (14)
The weights set is closed convex set based on Equation (9) and the non-negativity assumption. We utilize an instance of the accelerated iterative dual forward-backward (DFB) algorithm, as proposed by (Neacşu et al., 2024), to update W((,)), The projection algorithm is detailed in Algorithm 1.
HER
where C= (2(1/0min 1)2 + 1)1/2.
Denoting by ny the optimal dual variable in Equation (14), it is easy to see that large losses above 17" are upweighted due to the squared term.
Here, projp represents the projection onto the cone of non- negative weights, whereas projs(a.F) represents the projec- tion onto the spectral ball of radius T >
Lemma 3.3 (See (Zhai et al., 2021)). Let Rmaz (f) denotes the worst-case risk on P, then we have:
Rmaz (f) S Ravo(s) S F(J,)).
(15)
3.3. Fair View Distributional Robust Optimization
Proposition 3.4. Let the distribution of the fair feature view generated be denoted by P,, i I......P p.. Minimizing the worst-case risk on all views, is equal minimize the following expression:
To enhance the model's adaptability to mask variations, we employ Distributionally Robust Optimization (DRO) to bolster the robustness of the encoder. We use G. as a random variable of node v vego-graphs whose realization is Gv = (A,, E., X C G, and a whole graph can be frag- mented as set of instances (Gv: Uv) Ve) Therefore, the conditional distribution PYY can be decomposed as a product of [V] independent and identical marginal distribu- tions/ pzyl G. Typically, adversarial based fair graph mod- els employ ERM find a optimal model ff that minimizes the average risk under the training distribution P(Y G): (11)
a
Ruff(() = Σ vs (C(EP, -n]]))//22 + n)
(16) where C= (2(1 - 1)2 + 1)1/2, and Omin is the smallest size of the entire group among all views. v E A.. Au is a (p (p-1)) -iimeeniinsi probability simplex, and v; rep- resents distance between the true mask and i-th generated mask.
min Reemm (f) == ([ FEF
For detailed proof processes, please refer to Appendix C. We can see from Proposition 3.4 that our proposed robust model actually ignores some views and the nodes that cause overfitting during fairness training. This overfitting would cause the accuracy performance to deteriorate dramatically, leading to an unstable graph fair model. For simplicity, we choose uniform in our work, and we use Brent's (ernod,Brent, 1971) to find the 17".
The use of mask generator in the fair graph model will cause the distribution shifts for P(y G..). i.e., different fair feature view will be used as input to the GNN encoder. However, models trained through ERM are highly based on spurious correlations that do not always hold under distri- butional shifts (ArjovsArykkky al., 2019), which would cause
5

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Training Accurscy on Gemman
Taining Accurag on Credit
0.7
Training Accuracy on Ball
0.6
0.8
0.66
0.7
0.4
FaIr/NNN
RaivE
RaNNVNN
170
175
180
185 Epoch
190
195
200
130
135
140
145
150
155
160
170
175
180
185
1.0
195
200
Epoch
Epoch
(a) German
(b) Bail
(c) Credit
German, Bail and Credit datasets. The shaded area represents the rolling standard deviation with window size of 5, which can used to measure the stability between epochs.
Figure 4. Training accuracy
Table Comparison results of SFG with baseline faimess methods. In each the best result is indicated in bold, while the runner-up result marked with an underline.
Dataset
Metric
GCN
Nifty
FairGNN
FaiVVGNN
FairAAD
SFG
Acc
68.72 + 2.38
69.92 + 0.81
71.32 + 0.16
69.84 + 0.74
68.29 + 2.80
70.32 + 0.46
AUC
67.64 6.49
72.05 + 2.15
69.30 8.60
66.74 + 4.08
72.20 + 3.42
69.38 + 4.77
German
DP
12.24
1 2.51
7.12 1 8.25
2.54 1.75
0.00 0.00
1.36 1
B0
11.01 +: 11.16
2.66 2.17
5.67 1 5.16
3.06 L 1.50
0.00 + 0.00
0.54 1: 0.74
Acc
82.01 0.24
77.38 + 1.65
83.59 0.86
$9.24
83.73 + 1.22
89.49 + 1.74
AUC
85.91 + 0.12
80.43 + 0.39
87.55 1 0.60
91.99 0.34
88.46 1 0.81
93.98 + 1.41
Bail
App
9.21 + 0.16
5.74 : 0.38
6.51 + 0.76
4.39 + 0.96
2.08 + 1.24
3.55 + 0.58
A
6.29 + 0.04
1.07 +: 1.28
1.50 + 1.09
2.49 + 1.06
2.14 1.18
1.11 + 0.43
Acc
73.67 + 0.03
69.63 + 0.75
76.16 1.82
80.13 + 0.32
77.41 0.78
80.34 + 0.11
AUC
73.87 0.02
69.08 + 0.15
74.62 0.87
74.17 0.54
71.72 + 0.51
74.37 + 0.37
Credit
APP
12.86 0.09
10.34 1.15
6.87 + 5.01
5.74 1.44
2.39 2.43
5.44 1.04
BO
10.63 0.13
9.36 + 1.23
5.14 5.35
3.18 + 1.02
1.39 1.66
2.71 + 0.58
4. Experiments
2022), representative adversarial-based model, the foun- dation for our proposed SFG. Subsequently, compare the accuracy and fairness performance of SFG with several state-of ffate-of-the-art fair graph learning models. Specifically, we compare the performance of SFG with five baseline meth- ods, i.c., GCN, NIFTY(Agarwal et al., 2021), FairGNN(Dai & Wang. 2021), (WaaV et al., 2022), FairSAD(Li et al., 2024). For evaluation of stability, we only compared with adversarial-basee model FairVGNN.
4.1. Settings
Datasets. We conduct experiments on three commonly used datasets(Dong al., 2022), including German, Bail, and Credit. The statistics of datasets shown Table 2.
Table 2. Statistic information of three waal-world datasets.
Dataset
German
Bail
Credit
Implementation Details. We conduct all experiments 5 times and reported average value and variance. For fair comparison, we tuned the hyperparameters for all methods according to metric = ACC + AUC + F1 ADP EO on the validation set. For SFG, we use a 2-layer GraphSAGE encoder with hidden dimensions 16 and set the number of generated fair feature views μ 10 for all datasets. We set the range of the Lipschitz constant is 2,, 6, 20, 50), which should not be larger than the unconstrained counterpart, for German, Bail, Credit.
#Nodes
1,000
18,876
30,000
#Edges
22,242
321,308
1,436.858
#Attr.
27
18
13
Sens. Gender
Race
Age
We use accuracy and AUC-ROC to evaluate the utility performance the model, and the sta- bility measured by the curve of accuracy changes. To evaluate fairness, we use commonly used fairness met- rics, that is, ADP P(g = 1 and AEO = Plù ly = 1,
Evaluation Metrics.
P 1|s 1)] 1, = 1)]- and denote the prediction of node embedding and label. For ADP and AEO, a smaller value indicates a better fairness.
4.2. Overall Results
We compare the stability of the improved Fair VGNN, en- hanced with a tighter Lipschitz bound and DRO, against
Baselines. In our work, we utilize Fair PairaGnN(Wang al.,
6

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Table 3. Ablation results for performance on German, Bail, and Credit. Reults indicate the DRO module needs to he used together with the Lipschitz constraint module to improve accuracy.
925
Datasct
Metric
SFG w/o ct
SFG w/o dro
SFG
2.0
Acc
69.76 + 0.32
70.24 0.32
70.32 0.46 69.38 + 4.77
-4.2
AUC
70.36 + 2.79
67.67 = 3.49
019
German
ADP
2.68 + 2.89
1.82 2.73
1.36
(a) FaiN
A EO
2.96 + 2.53
1.47 0.54 2.50
Acc
88.76 0.76
89.06 1.20
89.49 + 1.74
AUC
91.78
+ 0.59
93.98 + 1.41
Bail
A Apr
3.10
1.42
3.74 774+0.90 0.95
3.55 + 0.58
SEC
34
0:00
A
1.50 + 0.98
1.27 + 0.90
1.11 + 0.43
DRV
BAY
Acc
80.37 + 0.05
80.20 0.23
80.34 - 0.11
089
-3
Credit
AUC
74.27
+ 0.49
73.74 0.15
73.88 + 0.12
ADP
6.71
+ 0.90
5.48 + 0.54
5.44
+095 549
606
600
010
364 509
8:22
012
000
A RO
3.81
0.65
2.97 + 0.52
2.71 + 0.58
-08
(b) SEG
FaivGNN
SFG
1.00
Figure 5. The weight patch of encoder for FairVGNN and SFG on German datasct.
0.80
0.00
its original counterpart. For the utility and fairness of the model, we compare the performance of SFG with four base- line methods and vanilla GCN on the node classification task. As illustrated in Figure 4, the training curve is sta- ble compared to FaiN during the convergence stage. Specifically, the amplitude and frequency of fluctuations are better, and the accuracy is generally better than the orig- inal model. Table 1 summarizes the results of the SFG comparison against all the baseline methods for rerl-world datasets. is evident that SFG outperforms all baseline methods across most evaluation metrics, which indicates the superiority of SFG in achieving better stability and trade-off between model utility and fairness. Compared to FairSAD, our model achieves 5.76% and 2.93% improvement in accu- racy for Bail and Credit dataset. FairSAD excels in handling fairness because it utilizes disentangled layers with multi- plicatively increasing parameters in the encoder and incor- porates an additional neighbor assigner. More experiments results can be found in Appendix D.I.
0.20
0.00
Sens
Feat!
Feat2
Feet3
Fea44
FeatS
Feats
Fest?
FeatS
Fearh Featt0 Featf1 Feat12
Figure 6. The learned mask of the generator on Credit dataset.
lent to removing the nodes that caused the overfitting, so the stability of the worst-case can be improved. In summary, the experimental results demonstrate the effectiveness of SFG in enhancing stability fairness while preserving trade-off between fairness and utility.
In order to verify whether the Lipschitz bound limits the range of weight changes and leads to the stability of the model, we compared the weight changes of each epoch. As shown in Figure 5, we compared the optimal model weights with the counterpart of the previous epoch, and the German dataset is used. The results indicate that SFG does con- strain the fluctuation of weights and can clearly distinguish different features. Specifically, compared to the weight range of [-1, O. 0.75] VGNN)) in Figure 5(a), the range of [0, 0. OOrr SFG) in 5(b) exhibits smaller overall fluctu- (ttions(33% of FaiNYGNN). From a micro perspective, the relative weight change
Notably, SFG not only reduces the frequency of fluctuations, but also significantly reduces the magnitude of fluctuations. In Bail datasets, we can see that the SFG dramatically im- proved worst accuracy, which may be caused by the gen- eration of a mask that leads overfitting during fairness training. This enhanced stability and fairness can be at- tributed to two reasons:(1) (1) By constraining the Lipschitz bound of the generator and encoder during training, we minimize changes of the learned embeddings in trade-off between fairness and utility, thereby enhancing the overall stability of the training process and making it more reliable and trustworthy. (2) Our proposed DRO objective equiva-
7.64%, 3FG::.00%% in the red boxes calculated as the weight difference between two epochs divided by the total range of variation. This av- erage comparison also reflect that our SFG exhibits smaller fluctuations( 14% of Fair between two epochs. De- tailed comparison can be seen in the Appendix D.6.
As shown in Figure 6, we can see that the mask value (prob- ability of keep the channel) of the sensitive attribute (Age)
7

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
close which means that the sensitive attribute is ef- fectively masked. In addition, most of the features' masks consistent with the previous models.
0.8
Training Accuracy en Credit
0.6
4.3. Ablation Study
0.5
We perform ablation study to evaluate the impact of each SFG component enhancing stability and preserving ac- curacy and fairness. Concretely, we denote SFG w/o ct as removing the Lipschitz bound constraint of the generator and encoder, SFG w/o dro as removing the proposed opti- mization objective, and SFG w/o ct& as removing both of these two modules, i.e., FairVGNN. The training curve of there variants is presented in Figure 7, and the utility and fairness performance are summarized in Table 3.
T-0
0.3
0.2
170
175
180
185
190
195
200
Epochs
Figure Hyperparameter analysis w.r.t. 7 on Credit.
performance gains slight improvement. (2) When the value of is small, the stability and performance of SFG is worse compared to scenarios where the value of 7 is relatively large.
0.7
Wainingg Rccrscy on Geman
This observation highlights that Lipschitz bound constraint T has a great positive effect on improving the stability of the model and can improve the performance of the model.
Figure 9 presents the stability results of the parameter O'min analysis of the sensitivity on Bail dataset, and the accuracy and fairness performance details can be found in the Ap- pendix D.3. The results indicate the dro has significantly improved the stability the abnormal epoch, which im- plemented by removing overfitting nodes.
ct&dro
0.4
w/o dro w/o ct
with ct&ddro
0.3
1.00 1.90
Sporhs
Figure Ablation results stability on German.
We observe that SFG w/o et is just as bad the original model in stability, which validates the effectiveness of Lips- chitz bound constraint for learning fair node representations stably. Furthermore, SFG with ct&droo perform better than SFG w/o dro, indicating that the proposed DRO module needs to be used with Lipschitz bound constraint, and has played great role in mitigating extremely unstable anoma-
Training Accuracy on Bail
0.86
0.84
0.82
w/o
lies. For fairness performance, SFG with et&droo is better, except for the German dataset. The accuracy metrics are essentially equivalent.
0-0.5
0.80
130
145
150
155
Epachs
4.4. Parameters Sensitivity Study
Figure 9, Hyperparameter analysis w.r.t. Omen on Bail.
The sensitivity of two parameters, i.c. 7 in Equation (9) and Omin in Equation (16), was studied mainly. In SFG, the Lip- schitz bound v controls the contribution of training stability. Specifically, we vary the values of t as (50, 20,5,2) 2) in the German data and vary the values of 7 as (6, 4, 1} in the Bail and Credit datasets. Figure presents the sta- bility results of the parameter 7 analysis of the sensitivity on Credit dataset, the details of the accuracy and fairness performance can be found in the Appendix D.2.
4.5. Time and Space Complexity
Table 4 outlines the time space complexity et al., 2019; Wu al., 2020) of the GNN encoder for SFG compared to other baseline fairness methods. We assume N₂ F for layer i f1.... m. and F & K. E denotes the number of all edges in graph and represents the number of independent channels in the disentangled layers of FairSAD. We observe that: (1) Compared to Fair VGNN, our model introduces only a marginal amount additional computa- tional and storage overhead during the forward propagation
We make the following observation: (1) The SFG remains stable across a wide range of variations in 7, and the overall
8

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Table 4. Time and space complexity analysis of SFG with baseline faimess methods.
Model
Forward Time
Forward Space
Backward Time
Backward Space
Parameter Count
FairVGNN FairSAD SFG
mEF + mKKF 1 u((EEF + mKFF) mEF + +mKF2 + mF3
E + mI + mKF w(E + mFF 4 mKFF E + mF + mKF + mF
mEF + mK Fra m(mEF mKFF) mEF + +mKFF
E + mF + mKF n(E mF mKKF) E ++ mF + +mK
mF
mm
mF2
process, which is attributed to the decoupling of the derived bound from the number of nodes K. The increased overhead stems from the complexity associated with performing sin- gular value decomposition (SVD) on the weight matrices. (2) In contrast FairSAD, we achieve reduction in the parameter count and computational and storage costs by factor of the number of independent channels n.
D. Invariant risk minimization. arXiv: 0eei119977.99. 2019.
In arXiv preprint
Brent, R. P. An algorithm with guaranteed convergence for finding a zero of a function. In the Computer Journal, 1971.
Chen, Z., Chen, F,, Zhang, I.,, Ji, T., Fu, K., Zhao, L.,
Chen, F., Wu, L.,, Aggarwal, C., and Lu, C. T. Bridging the gap between spatial and spectral domains: unified framework for graph neural networks. In Association for Computing Machinery, 2023.
5. Conclusion
In this paper, we first theoretically derive an easy-to- compute tight upper Lipschitz bound control the stability of generator and encoder, and use the block coordinate approach which operates in a cooc-ccood manner to control weights. Additionally, we use multi-view DRO ob- jective to further enhance the robustness of GNN encoder. Experiments on three real-world datasets demonstrate supe- rior stability and performance of our model.
Dai, E. and Wang, S. Say no the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In ACM WSDM, 2021.
Derrick, B., Jack, L., and Yanjun, Q. Time and space complexity of graph convolutional networks. 2019. URL https: //tpi/apppppp semant cscholar. org/ :ttp/CorpuSI:::000 :21.11::2229915500
Acknowledgements
This research is funded by National Natural Science Foun- dation of China (No. 62406347).
Dong, Y., Kang, J., Tong, H., and Li, J. Individual fairness for graph neural networks: A ranking based approach. In ACM SIGKDD, 2021.
Impact Statement
Dong, Y., Liu, N., Jalaian, B., and Li, J. Edits: Modeling and mitigating data bias for graph neural networks. In www, 2022.
This paper presents work whose goal advance the field of Machine Learning. All the work and data based on existing public datasets and methods, thus there are potential adverse societal consequences.
Duchi, J. C. and Namkoong, H. Learning models with uni- form performance via distributionally robust optimization. In The Annals of Statistics, 2021.
References
Abadeh, S. S., Nguyen, V. A., and Esfahani, P. M. M. Wasserstein distributionally robust kalman filtering. In NeurlPS, 2018.
Gama, F,, Bruna, J., and Ribeiro, A. Stability properties of graph neural networks. IEEE Transactions on Signal Processing, 2020.
Agarwal, C., Lakkaraju, H., and Zitnik, M. Towards a unified framework for fair and stable graph representation learning. In UAI, PMLR, pp. 2114-2124, 2021.
Gao, C., Wang, X., He, X., and Li, Y. Graph neural networks for recommender system. In ACM WSDM, 2022.
Gilmer, J., Schoenholz, S. S., Riley, P. A., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In ICML, 2017.
Arghal, R., Lei, E., and Bidokhti, S. S. Robust graph neural networks via probabilistic lipschitz constraints. In Learning for Dynamics and Control Conference, 1073-1085, 2022.
Hamilton, W. and Ying, Z. Inductive representation learning on large graphs. In NeurlPS, 2017.
Arjovsky, M., Bottou, L.,, Guirajani, I., and Lopez-Paz,

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
He, M., Wei, Z., Huang, Z., and Xu, H. Bernnet: learning ar- bitrary graph spectral filters via bernstein approximation. In NeurIPS, 2021.
Rozemberezki, B., Hoyt, C. T., Gogleva, A., Grabowski, P.,
Karis, K., Lamov, A., Nikolov, A., Nilsson, S., Ughetto, M., Wang, Y., Derr, T.,, and Gyori, B. M. Chemicalx: A deep learning library for drug pair scoring. In ACM SIGKDD, 2022.
Jia, Y., Zou, D., Wang, H., and Jin, H. Enhancing node-level adversarial defenses by lipschitz regularization of graph neural networks. In ACM SIGKDD, 2023.
Scaman, K. and Virmaux, A. Lipschitz regularity of deep neural networks: analysis and efficient. NeurlPS, 2018.
Jia, Y., Zhang, C., and Vosoughi, Aligning relational learning with lipschitz fairness. international conference on learning representations. In ICLR, 2024.
Su, J., Zou, D., and Wu, C. Pres: Toward scalable memory- based dynamic graph neural networks. In ICLR, 2024.
Jing, Y., Yuan, C., Ju, L., Yang, Y., Wang, X., and Tao, D. Deep graph reprogramming. In CVPR, pp. 24345-2432 2023.
Su, X.. Huang, T., Li, Y., You, S., Wang, F., Qian, C., Zhang, C., and Xu, C. Prioritized architecture sampling with monto-carlo tree search. In CVPR, pp. 10968-10977, 2021a
Jing, Y., Hong. S.-H., and Tao, D. Deep graph mating. NeurlPS, 37:9753-9772, 2024.
Su, X., You, S., Huang, T., Wang. F., Qian, C., Zhang, C., and Xu, C. Locally free weight sharing for network width search. arXiv preprint Miii:2002.0025:: 2021b.
Juvina, S., Neacşu, A. A., Pesquet, J. C., Corneliu, B., Rony, J., and Ayed, B. Training graph neural networks subject to tight lipschitz constraint. In Transactions on Machine Learning Research Journal, 2024.
Su, X., You, S., Wang, F., Qian, C., Zhang, C., and Xu, C. Benet: Searching for network width with bilaterally coupled network. In CVPR, pp. 2175-2184 2021c
Kang, J., He, J., Maciejewski, R., and Tong, H. Inform: Individual fairness graph mining. In ACM SIGKDD, 2020.
Su, X., You, S., Zheng, M., Wang, F., Qian, C., Zhang, C., and Xu, C. K-shot nas: Learnable weight-sharing for nas with k-shot supernets. In ICMI., pp. 9880-9890. PMLR, 2021d.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Su, X., You, S., Xie, J., Wang, F., Qian, C., Zhang, C., and Xu, C. Searching for network width with bilaterally coupled network. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(7):893688953, 2022a.
Li, Y., Wang, X., Xing, Y., Fan, S., Wang, R., Liu, Y., and Shi, C. Graph fairness learning under distribution shifts. In WWW, pp. 676-6844 684, 2024.
Su, X., You, S., Xie, J., Zheng, M., Wang, F., Qian, C., Zhang, C., Wang, X., and Xu, C. Vitas: Vision trans- former architecture search. In European Conference on Computer Vision, pp. 139-157. Springer, 2022b.
Liao, N., Liu, H., Zhu, Z., Luo. S., and Lakshmanan, L. V. Benchmarking spectral graph neural networks: A com- prehensive study on effectiveness and efficiency. In arXiv preprint arXiv:2406.090) 2024.
Szegedy, C.,, Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. In ICLR, 2014.
Ling, H., Jiang, Z., Luo, Y., Ji, S., and ZHou, N. Learning fair graph representations via automated data augmenta- tions. In ICLR, 2023.
Virmaux, A. and Scaman, K. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In NeurlPS, 2018.
Mandal, D., Deng, S., Jana, S., Wing, J., and Hsu, D. J. Ensuring fairness beyond the training data. In NeurlPS, 2020.
Wang. Y., Zhao, Y., Dong. Y., Chen, H., Li, J., and Derr, T. Improving fairness in graph neural networks via miti- gating sensitive attribute leakage. In ACM SIGKDD, pp. 1938-1948, 2022.
Namkoong, H. and Duchi, J. C. Stochastic gradient methods for distributionally robust optimization with f- divergences. In NeurlPS, 2016.
Neacşu, A., Pesquet, J. C., and Burileanu, C. based automatic gesture recognition using lipschitz-regularized neural networks. In ACM Transactions on Intelligent Systems and Technology, 2024.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2020.
10

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Zhai, R., Dan, C., Kolter, Z., and Ravikumar, P. Doro: Distributional and outlier robust optimization. In ICMI., 2021.
Zhang, H., Wu, B., Yuan, X., Pan, S., Tong, H., and Pei, Trustworthy graph neural networks: Aspects, methods, and trends. Proceedings of the IEEE, 11(22)9771339 2024.
Zhao, X., Zhang, Z., Zhang. Z.,, Wu, I.., Jin, J., Zhou, Y., Jin, R., Dou, D., and Yan, D. Expressive 1-lipschitz neural networks for robust multiple graph learning against adversarial attacks. In ICML, pp. 12719-12735, 2021.
Zheng, M., Su, X., You, S., Wang, F., Qian, C., Xu, C., and Albanie, S. Can gpt-4 perform neural architecture search? arXiv preprint arXiv:2304. 10970, 2023.
Zhu, Y., Li, J., Zheng, Z., and Chen, L. Fair graph represen- tation learning via sensitive attribute disentanglement. wWw, 2024.

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
A. Related Work
Fairness in Graph. Fairness in graph can be mainly divided into two categories, i.e., group Mainness(Mandal et al., 2020) and individual (aann al., 2020). Group fairesss, which emphasizes model's prediction neither favor nor harm certain groups defined by the sensitive attribute, is investigated in this work. As a crucial issue in the field of graph learning, several recent otate-of-the-art fair graph models have been proposed to solve faimess. We divide them into two categories: augmentationn-ased models and adversarial-baat models. Augmentation-basee models mitigate discrimination through graph augmentation, where sensitive-related information is removed by altering the graph topology or node features, such as NIFTY et al., 2021) and EDITS(Dong et al., 2022). The adversarial-based models force the fairness of node representations by alternatively training the generator and encoder to fool the discriminator and the discriminator to predict the sensitive attributes, and the classifier is used to guarantee the model utility. These models include FairGNN((Dai & Wang, 2021), FatraGNN(Li et al., 2024) and FainnG al., 2022), which is the main object of our study of stability, Compared to NIFTY, Our model achieves fairesss through adversarial training, rather than by learning fair representations via specific objective function. Additionally, the bound of NIFTY is loose.
Lipschitz constant. To the best of our knowledge, there is relative paucity of literature on the Lipschitz bounds of GNNs, especially for fairness. Pioneering workeSz et al., 2014) points out that the Lipschitz constant of the neural network can be derived as the accumulation of parameters at each layer. Arghal et al. (2022) focused on controlling the Lipschitz constant of GNN filters in the frequency domain, Zhao et al. (2021) proposed separable Lipschitz bound for GNNs, constraining both the weight and gradient norms of each layer 1, and Jia al. (2024) investigated the approximation of the Lipschitz bound via the Jacobian matrix to enhance individual fairness in GNNs from ranking perspective. There bounds are loose, and have not yet been applied to the stability of graph fairness. Additionally, these bounds are only used to constrain the stability of the encoder and do not take into account other modules associated with the encoder, such as the generator.
B. Proof of Theorem 1
B.1. Preliminary Results
Define L as the normalized Laplace matrix, U as the orthogonal matrix after spectral decomposition, where the column vectors are unit eigenvectors and A as the diagonal matrix of the eigenvalue. In spectral graph theory, graph convolution can be expressed by:
y = (Uo x),
(17)
where (:o) is graph filter with learned parameters, and is activation function. To represent the above convolution kernel using a k-th order polynomial, we have the following expression:
K
y - y= Σ 0AAUUT
k=U
(n(UAAUT)z)
k=
(18)
(((UAUT)
K
O&L*x).
k=
Expanding matrix form, have:
= =<<(MLL)XW)
(19)
where h(L) is a polynomial function of L, and W is learned parameter matrix. Let Relu, and the node v's embedding layer is
K
H!C Rolu Σ ff
(20)
where 1!0 E RRINN neighbor node's embedding of after mapping, and enu element of h (.T.).
12

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
In the spatial domain, the expression of the graph convolution is Equation (2). Then
H (e ((ii1) + W/' H(-1)) Relu((Idx @ wb " )H1 + (M @ w (((1))
(21)
the node v's embedding at layer is If spectral domain graph convolution is equivalent to spatial domain graph convolution, then we have:
H Relu( (()
Σ
Poulf
(22)
uEN(u)
where 1! is the embedding of node v after mapping, and Peu is element of M in Equation (3).
H Relu(fe
Σ
PuuJu
((0)
wEN(u)
= Relul
Σ
PouJa.)) (()))
(23)
uEN(u)u(U)
K
= Relu
Σ EouJu fouf("))
f(()).
u=1
Equation (18) indicates (L) contains self-loop. Expanding to matrix form, have,
M + T= ((D),
(24)
where the parameters of mapping are assumed to be same. This is only suitable for the GraphSAGE.
For a more general expression, wo is O for every E 1,...: m, and M contains a self-loop, then M = h(L.). This consistent with previous work(Gama et al., 2020) where can be considered graph shift operator(GSOO.
According to Liao al. (2024) and Chen et al. (2023), h(L) can cover low-pass, high- figh-pass,am and band-pase podd-pass graph filters. Taking BernNet as an example,
K Σ
K
M(L)
0$
(2I - L)
(25)
2k
k
k=U
When K//2 and other 0₂ = 0, ((L) = z (1)2) (2I k)2 1/2 k2/2 2 an impulse bandpass filter, and h(A) E [0, 1] is the element of the diagonal matrix (AA).. Therefore, we have:
h(L)= - if model is GraphSAGE, ((L)) otherwise,
M
(26)
and the graph frequency response of the filter is h(A) - and h(A) respectively.
B.2. Proof of Theorem
Since M is equivalent to the graph filter h(L), the M is symmetric with non-negative elements. For GraphSAGE, M D-1/2 D-1/2ADD-1 = I L = h(L) 7, so h(L)) = 2T - L, and h(A) - E (), This implies that its trace is zero, and it has negative and positive eigenvalues. For the sake of clarity, we use I(A) as the frequency response function of the graph filter. By performing spectral decomposition on M. we obtain the following expression:
M = h(L) Uh(AJUT
(27)
where h(A) is a diagonal matrix eigenvalues, and ((A) is a element the diagonal matrix. For example, h(A) is in range of 0-2 when h(T.) L., and it a high-pass graph filter.
13

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Suppose that M satisfies the above conditions. According Equation (2) and Equation (3), have:
W = w + W
Idk @ wh + h(L) & w(t)
(UU*) 2 w (4) (UN(A)U²) wf
(28)
-U @ [Idk @ up (0" IdN + @U& Idx.) w uf")(U" @ IdN..)
(U @ Idy, (Idk @ u h(A) @ un yUT & IdN_.).
The fourth equality above is obtained based the distributive and associative laws of Kronecker products, i.e., (A @ (C & D) = (AC) @ (BD), and the matrices have compatible dimensions for multiplication. Additionally, we get following expression:
(U (U @ Idv,) (UU*) @ (Idx.IdN.)
ldx @ IdN.
(29)
IdKN.
Finally, we get the accumulation of all parameters when the fair graph model is equipped with generator of mask, it's
W(m) WWW (U @ (Idx & wi (m) + h(AA)
) ... (ldx wa + h(A) wi wf XUT IdN.)
(30)
where We E RRIX
R is the parameter of generator, and we first form into diagonal matrix W,, E R NoN No. Then we tile along the diagonal K times and Wg K is also a diagonal matrix.
Let us analyze the interchangeability of (UT IdNo) and Wg. (UT & IdNa) can be seen as IdN, being tiled K times. Since the product of two diagonal matrices is commutative,
have
IdN, 51 Wg, IdNo
(31)
For (U2 & IdN,) W. its each block is U INN, W and U.j is the element of U position (i.j). Therefore, (U W, is commutative, i.e.
(UT IdN,) (UT s IdN,)-
(32)
times For every E l.... m. Id w/) + h(A) w(") is block diagonal matrix of size (KN,) (KN,-1) having block diagonal elements, and Its k-th diagonal block is expressed as w/ (i) + hg (A)
In summary, k-th diagonal block of eigenvalue matrix of W(m) (imm)...(()))))
W W, is expressed as:
(wo (m) + hu (A)w(m)) ... (w) (1) + hx ) (1) + (x)w) (2) Wg.
(33)
= (w) (m)) + (")))) ... (w))
where O represents element-wise product supporting broad-cast.
Acording to the Perron-Frobenius theorem, we have
(x) I (A), (Ak E sI.....). K),
(34)
where hmaz (A) is the maximal frequency response of the graph filter. So we get the Theorem 1:
Lip(f) =|| ((m)... ... W lls
(35)
=I (w/ (m) + Amaa (A) (m)) (w) + hmas (N) o wg lls
14

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
C. Proof of Proposition 4
Define Pk as distribution of the k-th domain group, Pau is the distribution of views, of is the k-th group's size of i-th view and V, is the represents distance between the true mask and i-th generated mask. We set:
Patl Σ v:
Pz j=1
(36)
Then, wee have:
Px(x)
(Pa(PalPaat)
Pati(X X)
(x(x)
Pau((dd
V; プ a (x)())
(37)
Pa(x)
1)²Pau
V:a Pk(x)
D Pace
For simplicity, we assume that v; follows uniform distribution, then:
Dxe(PallPart < ((((tt) (a+)min 1)2Pa Paul (x)
(38)
where (a*) is the smallest size of the k-th group among all views, and where ты (1/(a*)m) min 1)2 is the robustness radius. Therefore, Tmaa : (1/Omin - 1)2 where Omin is the smallest size of the entire group among all views. It is easy to see that the distribution v is not uniform, and this conclusion still holds.
We proved P& E B(Pau. rk). Since the sup is over all Q E B(Pau, rk), the upper bound is consistent.
According to Lemma 3.2 and Lemma 3.3, we can get the following proposition.
Let the distribution of the fair feature view generated be denoted by P., ,,. Minimizing the worst-case risk on all views, is equal to minimize the following expression:
Rofg(f) Σ (CEEA, - 12 + +n).
(39)
where C' (2(1/amán 1) and ammnn is the smallest size of the entire group among all views. V A,, A is (n dimeennsil probability simplex, and v, represents distance between the true mask and i-th generated mask.
D. Additional Results
D.1. Effect of Each Component for Stability and Performance
provide detailed training stability for different components on all datasets.
15

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
0.85
Taining Accurcy
0.65
w/o ctódro
0.60
w/o dro
with ctádro
Epochs
Figure 10. Training accuracy curve of the convergence phase on Bail
As shown in Figure 10, we observe that SFG w/o ct is just as bad as the original model in stability for Bail dataset, which validates the effectiveness of Lipschitz bound constraint for learning fair node representations stably. Furthermore, SFG with ct&rdro perform better than SFG without dro, indicating that the proposed DRO module needs to be used with the Lipschitz bound constraint and has played an important role in mitigating extremely unstable anomalies.
0.8
Taining Accuracy on Credit
0.5
0.4
03
WVD ct6ddo
with c2ádro
170
180
105
190
195
200
Epochs
Figure 11. Training accuracy curve of the convergence phase on Bail
As shown in Figure 11, We observe that SFG w/o ct is just bad the original model in stability for Credit dataset, which validates the effectiveness of Lipschitz bound constraint for learning fair node representations stably. Furthermore, SFG with ct& perform better than SFG w/o dro, indicating that the proposed DRO module needs to be used with Lipschitz bound constraint, and it has played a great role in mitigating extremely unstable anomalies.
In summary, the Lipschitz module is to improve the overall stability, and the DRO module to improve the stability of a few abnormal epochs.
16

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
D.2. Effect of the Lipschitz Constraint for Stability and Performance We provide detailed training stability and performance for different the Lipschitz constraint on all datasets.
86-2
#2-3
4
12
de de
a5o
Spada
Apecio
(a) Complete training accuracy curve on German
(b) Training accuracy curve the convergence phase on German
Figure 12. Stability of SFG on German. (a) visualizes complete the accuracy curve. (h) visualizes the accuracy curve in the convergence phase.
Table Detailed result parameter sensitivity analysis for performance on German.
Dataset Metric
SFG w/o
20
50
Acc
70.00
70.80
70.00
70.40
69.60
AUC
71.81
70.60
70.29
69.18
66.34
German
Apr
5.95
3.60
1.06
B0
0
3.68
0
0.21
1.79
In Figure 12, we plot the complete accuracy curve of VGNN and SFG with the Lipschitz constraint against epochs, and the accuracy curve in the convergence phase. SFG with the Lipschitz constraint is significantly more stable than FaiN on German dataset, and the best stability is achieved when the r is in the range of 20-50. As decreases, the stability gains diminish. As summarized in Table 5, all ranges of T, the accuracy is comparable to the original model, and the fairness slightly reduced.
0.20
0.7
1parss
(a) Complete training accuracy curve on Bail
(b) Training accuracy curve of convergence phase on
Figure Stability of SFG Bail. (a) visualizes complete the accuracy curve. (b) visualizes the accuracy curve the convergence phase.
17

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Table 6. Detailed result of parameter sensitivity analysis for performance Bail.
Dataset
Metric
SFG w/o ct
2
4
6
Acc
89.43
89.26
90.36
89.34
89.09
AUC
92.23
93.94
94.21
93.46
92.81
Bail
ADP
5.26
4.49
5.08
4.83
4.73
A BO
4.21
2.55
1.96
1.06
1.25
In Figure 13, we plot the complete accuracy curve FariVGNN and SEG with the Lipschitz constraint against epochs, and the accuracy curve in the convergence phase. SFG with the Lipschitz constraint is significantly more stable than FairVGNN on Bail dataset, and the best stability is achieved when the is in the range of 4-6. As 7 changes, the stability generally unchanged. As summarized in Table in all ranges of т, both accuracy and fairness have been improved, especially Aeo.
50 no
02-
150
152
279
3.5
200
(a) Complete training accuracy Credit
(b) Training accuracy of the convergence phase Credit
Figure 14. Stability of SFG Credit. (a) visualizes complete the accuracy curve. (b) visualizes the accuracy curve in the convergence phase.
Table Detailed result of parameter sensitivity analysis for performance on Credit.
Dataset
Metric
SFG w/o et
7
Acc
80.35
80.03
80.19
79.83
80.29
AUC
74.37
72.09
74.07
73.85
73.59
Credit
App
6.00
4.30
4.81
4.58
4.61
Ágo
3.48
1.61
2.63
1.95
1.94
In Figure 14, we plot the complete accuracy curve of FariVGNN and SFG with the Lipschitz constraint against epochs, and the accuracy curve in the convergence phase. SFG with the Lipschitz constraint is significantly more stable than FaiN on Credit dataset, and the best stability achieved when the unchanged. As summarized Table ranges r, both accuracy and fairness have been improved, especially Aeo.
the range 4-6. As 7 changes, the stability is generally
D.3. Effect of the DRO Objective amin for Stability and Performance
We provide detailed training stability and performance for different hyper-parameter Osain on all datasets.
Table 8. Detailed result of parameter Obrin sensitivity analysis for performance on German.
Dataset Metric
SFG with et ammin 0.4
0.5
0.6
Acc
70.00
69.19
69.60
69.60
AUC
70.84
70.50
71.18
71.80
German
App 0
1.26
1.06
1.06
Ago 0
1.89
1.78
18

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
0.7
0.6
Taining Accuracy
0.5
w/o a
Q-0.6
0-0.4
0.3
170
175
180
185
190
195
200
Epochs
Figure 15. Training accuracy curve of the convergence phase German
In Figure 15, we plot the accuracy curve of SFG with different amin in the convergence phase, and SFG is controlled by the Lipschitz constraint(7 20). SFG has positive effect alleviating the stability of few abnormal epochs, which may be implemented by dropping some overfitting nodes in chasing fairness. The best stability is achieved when the O'mnn is 0.5, and 0.6 is an inappropriate value and the result is also bad. As summarized in Table 8, the accuracy is comparable to SFG w/o ct, and the fairness is slightly reduced. In summary, the use of DRO objective can alleviate abnormal fluctuations caused by very few epochs and make the model more stable. Notably, the anomalies in the last few epochs are likely due to overfitting, a problem exacerbated by the exceptionally small size of the dataset.
0.90
0.88
0.86
Taining Accuracy
0.84
0.82
g-0
0.80
Q-0.6
130
135
150
155
Epochs
Figure 16. Training accuracy curve of the convergence phase on Bail
19

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Table 9. Detailed result of parameter Olyni sensitivity analysis for performance Bail.
Dataset
Metric
SPG with et Omin 0.4
Omnn
0.5
Omnn 0.6
Acc
89.65
88.76
89.31
89.46
AUC
93.55
94.05
94.87
93.81
Bail
ADp 4.49
1.26
4.20
4.73
ABo 2.03
1.89
1.70
2.79
In Figure 16, we plot the accuracy curve of SFG with different Otmin in the convergence phase, and SFG is controlled by the Lipschitz constraint(r = 4). SFG has a positive effect on alleviating the stability of few abnormal epochs, and the best stability is achieved when the Omin is in the range of 0.4-0.5. As summarized in Table 9, the accuracy and fairness are comparable SFG with ct, and even slightly improved when min 0.5. In summary, the use of DRO objective can alleviate abnormal fluctuations caused by very few epochs and make the model more stable.
0.8
0.7
0.6
Taining Accuracy
Q=0.4
0-0.5
0.2
170
175
180
185
190
195
200
Epochs
Figure 17. Training accuracy curve of the convergence phase Credit
Table 10. Detailed result of parameter Osiin sensitivity analysis for performance Credit.
Dataset Metric
SFG with ct O'min 0.4
0.5
0.6
Acc
80.32
80.53
80.36
80.62
AUC
73.71
73.50
73.64
73.87
Credit
App 4.76
5.85
5.40
5.10
Ago
2.16
3.02
2.73
2.59
In Figure 17, we plot the accuracy curve of SFG with different Omin in the convergence phase, and SFG is controlled by the Lipschitz constraint(r = 2). SFG has a positive effect on alleviating the stability of a few abnormal epochs, and the best stability is achieved when the amin is in the range of 0.4-0.5. As summarized Table 10, the accuracy and fairness are comparable SFG with
D.4. Accuracy Near the Optimal Model
We provide the accuracy near the optimal model on all datasets.
20

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
100
80
70
60
50
40
20
10
Bail
German
Credit
Figure Training accuracy near the optimal model
We observe that accuracy near the optimal model is stable in Figure 18, which validates the effectiveness of proposed model.
D.5. Model Implementation Details
Fairness- view generator aims mask sensitive features by learning mask weight(ge,, ) for each feature channel, and it has learnable sampling score s, which denotes the probability of keeping channel To make the network differentiable, we use the Gumbel-Softmax trick to approximate the categorical Bernoulli distribution. Therefore, the generated mask value is:
p; = <
5; 8 ( + + (
(0--g)1 /))) 1,.....
(40)
where g:: ot ~ GumbellO, 1), and a is the sigmoid activation, and s a parameter that controls the smoothness of samples. Then, we could directly multiply the feature channelX,; by the mask weight p; to get the fair nodes features, i.c.,
X X m
(41)
where m = [po. Pi...., 1 is the learned mask.
In order to learn from both the topology structure and nodes features, we use 2-layer GraphSAGE, as our encoder, i.e., GNN Encoder. In our work, we focus on constraining the weights of GNN Encoder to get stable node representation. To make encoder robust to different fair views, employ a multi-view DRO objective to chase fairness.
The Classifier and Discriminator are designed to predict node labels and sensitive attributes, and both consist of single-layer MLP (dey: C. The objective of these two modules are BCE loss, can be expressed by:
La Ev (S,log( + (1 - S.)log(1 - -S,)
(42)
and
L = - Ev (y)loo())) + - y:)log(1 - -;)))
(43)
where yi and S; denote the labels for nodes and sensitive attributes, respectively. H!!) = eo. (G,, m) learned embedding of node after generator and encoder. S, = de, (H( is sensitive attribute prediction and o = ce. (H(1)) is the node label prediction.
The goal of adversarial training is to learn fair view representation by generator and encoder, which masks as much sensitive-relevant information as possible. This work focuses on optimizing the model using adversarial training while also emphasizing fairness and utility. other words, after encoding by the encoder, the stable representations should consider both fairness and utility. The optimization objective of adversarial training can be expressed by:
max La Ev,vv ev,,evSS,aee (Sylog( S.) + (1 S.)log(1 5.)), 8,
(44)
21

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
and
min Lg = Em,ev 0.5)+ ||
La
(45)
where (e, (X) is the mask weights of all channel generated by generator.
D.6. Weights Comparison Between VaNN and SFG
We list the absolute weight changes between epochs in following table(both uniformly rescaled the range [0, 1J). and the results reflect that our method can indeed limit the fluctuation range of the weights.
Table 11, Red box in the weight patch
Model
FaiN
SFG
epoch optimal
0.697
0.783
0,566
0.709
0.703
147
0.000
0.000
0.013
0.253
epoch optimal
0.760
0.846
0.714
0.737
0.623
120
0.000
0.000
0.000
0.267
absolute change
0.063
0.063
0.148
0.028
0.080
0.027
0.000
0.000
0.013
0.014
Table 12, Red box in the weight patch
Model
FairVGNN
SFG
epoch optimal
0.663
0.703
0.863
0.320
0.080
0.293
epoch optimal
0.754
0.777
0.790
0.293
0.093
0.307
absolute change
0.091
0.074
0.073
0.027
0.013
0.014
D.7. Baseline with Smaller Learning Rate
We added a baseline with smaller learning rate (ee-, FairVGNN), the three nearly unchanged weights in Figure 19 demonstrate that a smaller learning rate can cause the optimization process to get stuck at saddle points, preventing effective learning of weights. Moreover, in the gradient descent algorithm(Su al., 2022a: 2021a; 2022b; Zheng et al., 2023) Wi n/w, large gradients can still lead significant weight changes such as Figure 20. This is also the reason why propose the Lipschitz Constraint. Additionally, smaller learning rate also reduces utility performancele.g. 4.17% on Credit) of baseline.
Three Weights of Encoder Over Epochs
02
Weight
1-th weight from patch Figure
weight from patch Figure
3-th weight from patch Figure
.01
-02
Epachs
Figure 19, Training weights with smaller lcarning rate
22

---

Stable Fair Graph Representation Learning with Lipschitz Constraint
Weight/ACC Over Epochs
Weight
ACC
Weight/ACC WMMMNM
M
0.-
25
50
100
125
150
375
220
Epochs
Figure 20. Training accuracy/weights with smaller learning rate
D.8. The Consistent Performance
Table 13 demonstrates that increasing parameters(PairSAD encoder has four times the parameters SFG) helps improve performance on small dataset, which fails on large dataset such as Bail and Credit. When FairSAD uses the same number(1 x) of parameters as SFG on German, SFG outperforms FairSAD by 27% for AUC. The following table also demonstrates that SFG outperforms FairSAD(2x) and FaixSAD(3x), which uses two and three times the number of parameters, by 9.04% and 8.25%, respectively.
Table 13. Model Performance with Different Numbers of Parameters
Model
AUC
SFG(1x)
69.38 + 4.77
FairSAD(Ix)
54.32 + 2.55
ADi25
63.63 + 6.99
FairSAD(3x)
64.09 + 3.19
23


Reviews:
[{"review_id": "TPKZudQrJF", "reviewer": "Reviewer_rmL1", "summary": "This paper presents a novel approach \"Stable Fair Graph Neural Network (SFG)\" that addresses the issue of instability in adversarial-based fair graph representation learning. The main contributions and findings are as follows (1) The authors derive a tight, easy-to-compute upper Lipschitz bound for the composite model that includes both the sensitive attribute mask generator and the GNN encoder. (2) the paper introduces a stochastic projected subgradient algorithm that employs a block-coordinate update mechanism.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your valuable suggestion and insightful comment.\n> CE. The indicator of weight fluctuation    \n> the absolute of weight changes would be more suitable.\n\nWe list **the absolute weight changes(FairVGNN: 0.079, SFG:0.018)** between two epochs in following table(both are uniformly rescaled to the range [0, 1]), and it will be supplemented in the revised version to facilitate readers' understanding. Figure 5 also illustrates from both macro and micro perspectives that SFG can constrain weight fluctuations. From a macro perspective, compared to the weight range of **[-1, 0.75]**(FairVGNN) in Figure 5(a), the range of **[0, 0.75]**(Our SFG) in 5(b) exhibits **smaller overall fluctuations(43% of FairVGNN)**.  From a micro perspective, the relative weight change(FairVGNN: **7.64%**, SFG:**1.08%**) in the red boxes is calculated as the weight difference between two epochs **divided by the total range** of variation. This average comparison also reflect that our SFG **exhibits smaller fluctuations(14% of FairVGNN) between two epochs**. \n* The weight changes in red box 2\n\n$$\n\\\\begin{array}{|c|c|c|}\n\\\\hline\n\\\\text{Model} & \\\\text{FairVGNN} & \\\\text{SFG} \\\\\\\\ \\\\hline\n\\\\text{epoch 119} & 0.663, 0.703, 0.863 & 0.320, 0.080, 0.293 \\\\\\\\ \\\\hline\n\\\\text{epoch 120} & 0.754, 0.777, 0.790 & 0.293, 0.093, 0.307 \\\\\\\\ \\\\hline\n\\\\text{absolute change} & 0.091, 0.074, 0.073 & \\\\mathbf{0.027}, \\\\mathbf{0.013}, \\\\mathbf{0.014} \\\\\\\\ \\\\hline\n\\\\end{array}\n$$\n\n\n\n> ED. Baseline with smaller learning rate\n\nWe added a baseline with a smaller learning rate(**1e-4**, FairVGNN), the three **nearly unchanged weights** in the figure(https://anonymous.4open.science/r/SFG-559B/small-lr.pdf) demonstrate that **a smaller learning rate can cause the optimization process to get stuck at saddle points**, preventing effective learning of weights. Moreover, in the gradient descent algorithm $w=w_0-\\eta \\Delta w$ , **large gradients can still lead to significant weight changes**(Please refer to figure https://anonymous.4open.science/r/SFG-559B/small-lr-2.pdf). This is also the reason why we propose the Lipschitz Constraint. Additionally, a smaller learning rate also reduces utility performance(e.g., **4.17% on Credit**) of baseline. Thank you for your suggestion enriched our discussion on training stability, and would be incorporated into the revised version.\n\n\n> W1. The Ablations Performance    \n> The Ablations in Table 3 show that SFG did not consistently achieve the best performance in AUC.\n\nCompared to our ablation model **SFG w/o ct**, SFG is the result of a comprehensive consideration of stability, utility, and fairness. As shown in  Figure 7, SFG significantly outperforms SFG w/o ct in terms of training stability, which can inspire further research for training stability of adversarial-based fair models, leading to more reliable and trustworthy models.\n\n\n> Q1. The architecture of the GNN\n\nAs elaborated in line 180 and 1080, the architecture of the GNN is **GraphSAGE** in our implementation. The result using **GCN** as backbone in follwing table also proved the effectiveness of our method(SFG outperforms the baseline by **118%** on Bail and 90% **on** Credit for $\\Delta EO$). Our tight upper bound(Eq. 5) of SFG is derived based on **the general message-passing framework**(Eq. 1) and is therefore applicable to most GNN backbones, such as GCN, GraphSAGE. Additionally, since the calculation of GAT coefficients involves node representations, it is not applicable to our bound. \n\n$$\n\\\\begin{array}{|c|c|c|c|c|c|}\n\\\\hline\n\\\\text{Dataset} & \\\\text{Model} & \\\\text{Acc} & \\\\text{AUC} & \\\\Delta_{DP} & \\\\Delta_{EO} \\\\\\\\ \\\\hline\n\\\\text{Bail} & \\\\text{FairVGNN} & 84.76 & 85.62 & 6.45 & 4.89 \\\\\\\\ \\\\hline\n\\\\text{Bail} & \\\\text{SFG} & 86.43 & 85.93 & 4.98 & 2.24 \\\\\\\\ \\\\hline\n\\\\text{Credit} & \\\\text{FairVGNN} & 78.06 & 71.36 & 6.21 & 4.67 \\\\\\\\ \\\\hline\n\\\\text{Credit} & \\\\text{SFG} & 79.74 & 72.06 & 4.54 & 2.45 \\\\\\\\ \\\\hline\n\\\\end{array}\n\\$$\n\n\n> W2/Q2.  The Consistent Performance    \n> In table 1, the proposed SFG did not constantly achieve the best performance across the dataset, what 's the reason for why it performs worse on German dataset?\n\nThe reason is that increasing parameters(FairSAG's encoder has **four times** the parameters of SFG) helps improve performance on **small dataset**, which fails on **large dataset** such as Bail and Credit. When FairSAD uses the same number(1$\\times$) of parameters as SFG on German, SFG outperforms FairSAD by 27% for AUC. The following table also demonstrates that SFG outperforms FairSAD(2$\\times$) and FairSAD(3$\\times$), which uses two and three times the number of parameters, by 9.04% and 8.25%, respectively.\n\n$$\n\\\\begin{array}{|c|c|}\n\\\\hline\n\\\\text{Model} & \\\\text{AUC} \\\\\\\\ \\\\hline\n\\\\text{SFG}(1\\\\times) & 69.38 \\\\pm 4.77 \\\\\\\\ \\\\hline\n\\\\text{FairSAD}(1\\\\times) & 54.32 \\\\pm 2.55 \\\\\\\\ \\\\hline\n\\\\text{FairSAD}(2\\\\times) & 63.63 \\\\pm 6.99 \\\\\\\\ \\\\hline\n\\\\text{FairSAD}(3\\\\times) & 64.09 \\\\pm 3.19 \\\\\\\\ \\\\hline\n\\\\end{array}\n$$", "claims_and_evidence": "The tight upper Lipschitz bound, which ensures the stability of the framework, is well supported by the developed theorems (Proposition 3.4). However, the claim that SFG effectively constrains weight fluctuations is not convincingly demonstrated in Figure 5. It is difficult to determine which case exhibits lower fluctuation since subfigures (a) and (b) use different legend scales. Additionally, using the absolute change in weights as an indicator of fluctuation would be a more reasonable approach.", "methods_and_evaluation_criteria": "The chosen dataset and metric are appropriate for the evaluation. However, the use of weight changes in Figure5 to reflect the function may not be entirely suitable instead the absolute of weight changes would be more suitable.", "theoretical_claims": "Didnt comprehensively evaluate the correctness of the proofs.", "experimental_designs_or_analyses": "This paper claims that Lipschitz bound limits the range of weight changes and leads to the stability of the model. Then, it might be important to include an important baseline: training the model with a smaller learning rate that could also lead to small weight changes.", "relation_to_broader_scientific_literature": "https://arxiv.org/pdf/2005.02929", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n(1) This paper developed a theorem to justify the method.\n\n(2) The paper is generally well written.\n\nWeakness:\n\n(1) The Ablations in Figure 3 show that SFG did not consistently achieve the best performance in AUC such as in German and Credit datasets.\n\n(2) The main results in Table 1 show that SFG can not consistently achieve the best performance across the datasets and the improvements is not significant as well.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "(1) what is the architecture of the GNN used for SFG? Can this method also work well for other Graph neural networks? such as graphsage or GAT?\n\n(2) In table 1, the proposed SFG did not constantly achieve the best performance across the dataset, what 's the reason for why it performs worse on German dataset?", "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": "", "extra_scores": {}}, {"review_id": "j3rtx8S9wv", "reviewer": "Reviewer_BuAy", "summary": "This paper focuses on addressing the challenge of training instability in adversarial-based fair GNN models. To mitigate this issue, it establishes a tight upper Lipschitz bound to regulate stability and leverages Distributionally Robust Optimization (DRO) to improve the encoder’s robustness across different fairness views. The key novelty lies in deriving a precise upper Lipschitz bound for a fair graph model with a generator and incorporating DRO to prevent fairness overfitting, ultimately ensuring stable training.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "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": "> W1/Q1    \n> The training process could be explained more clearly.\n\nThank you for your valuable suggestion. We provide the following clear description of the training process:\n\nWe train SFG in an alternating manner throughout the entire process. In each epoch, we first train discriminator(i.e., $L_d$ in Eq. 42) to recognize the sensitive attributes by generated mask, then we train encoder and classifier using BCE loss(i.e., $L_c$ in Eq. 43). Finally, we train generator(i.e., $L_g$ in Eq. 45) and encoder to achieve fairness. This process is repeated for all epochs. Therefore, SFG used Lipschitz Constraint with mask weights and DRO can enhance stability.\n\n\n\n> W1/Q2\n>\n> The meaning of the circles between Step 3 and Step 4 in Figure 1 is not sufficiently detailed.\n\nThank you for your insightful comment. Our purpose of using DRO is to narrow the gap(i.e., Shrink Distribution Discrepancy) with the real data distribution by finding the worst-case distribution of the training data, thereby improving the robustness and stability with the mask weight. The circles between Step 3 and Step 4 in Figure 1 **indeed represent an expansion of the potential distribution range to better approximate the real data distribution**.\n\n\n\n> OCS\n>\n> The Lipschitz constant range should remain consistent throughout the paper\n\nThank you for your careful review. We update the range of constant $\\tau$ as {1,2,4,5,6,20,50}.", "claims_and_evidence": "The claims presented in this paper are generally clear and straightforward. Additionally, the proof process is structured well and effectively communicated.", "methods_and_evaluation_criteria": "I believe that enforcing a Lipschitz constraint is essential for ensuring the stability of fair GNNs, and deriving a tight upper bound in the presence of a generator is a novel contribution. Moreover, applying DRO offers an innovative approach to improving the stability of fair models. The datasets utilized in this paper are widely recognized within the fair graph research community. Regarding evaluation criteria, the paper assesses performance from the perspectives of stability, utility, and fairness, which I find to be a reasonable approach.", "theoretical_claims": "I have reviewed the paper’s key theoretical derivations, including Theorem 3.1 and Proposition 3.4, and did not find any issues with them.", "experimental_designs_or_analyses": "I reviewed the descriptions provided in the experimental settings, including the selection of the Lipschitz constant and the model’s key hyperparameters. The paper presents these details clearly, and the chosen hyperparameters are commonly used. In the experimental analysis, the paper examines the improvement margins in stability and utility and also analyzes a specific case, which I find to be a reasonable approach.", "relation_to_broader_scientific_literature": "This paper addresses the challenge of training stability in fair GNNs, a critical yet often overlooked issue in the fair graph research community. In the introduction and related work sections, the authors compare SFG with other fairness models, including those involving Lipschitz bounds, providing a well-reasoned discussion. Moreover, these concerns are relevant to a broader range of graph learning tasks.", "essential_references_not_discussed": "none.", "other_strengths_and_weaknesses": "Strengths:\n\nThis paper is the first to recognize the instability issue in adversarial-based fair GNN models and introduces a tight Lipschitz bound to enhance stability. The derivation of the upper Lipschitz bound is both theoretically sound and practically justified, with a clear and well-structured explanation. SFG significantly improves stability while maintaining accuracy and fairness in fair graph models. Additionally, this work presents the first empirical study on applying DRO to graph fairness, strengthening the encoder’s robustness across different fair views. A thorough complexity comparison is also provided.\n\nWeaknesses:\n\nThe training process could be explained more clearly. The meaning of the circles between Step 3 and Step 4 in Figure 1 is not sufficiently detailed.", "other_comments_or_suggestions": "The Lipschitz constant range should remain consistent throughout the paper. In Section 4.4, the constant range for the German dataset should be integrated into the experimental settings outlined in Section 4.1.", "questions_for_authors": "Is Step 4 of SFG trained alternately or in a unified manner?\n\nDo the circles between Step 3 and Step 4 represent an expansion of the potential distribution range to better approximate the true distribution?", "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": "", "extra_scores": {"ethical_review_concerns": "n/a"}}, {"review_id": "08QSZshVh1", "reviewer": "Reviewer_v1yW", "summary": "The paper introduces a tight upper bound and distributionally robust optimization to address the challenges of training instability that have been ignored by most previous methods for fair graph representation learning. SFG’s novel upper bound is tight and considers the changes of masks, enhancing training stability while preserving model utility and fairness. The use of a projected stochastic subgradient algorithm makes the non-convex problem convert into a multi-convex problem, facilitating the optimization process.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "> W1/Q1     \n> The update of the weight in Eq (9) has not been explained, and the Multi-convex component in Figure 1 is unclear. \n\nThank you for your valuable comment. We provide the following clear description for the weight update:\n\nWe update the weights layer by layer, and $B_{new}^{(i,t)}$ always uses the updated weights at each step. As shown in the Multi-convex component of Figure 1, the Non-convex optimization is transformed into Multi-convex optimization through a layer-by-layer update approach. The green background indicates that only the i-th layer is updated in the current step, while the light gray indicates that the layer is not updated in the current step. It can also be seen that this approach takes into account the presence of mask weight( $w_g$ \\).\n\n\n\n> W2/Q3\n>\n> the analysis of the GNN complexity is unclear.\n\nThank you for your careful review. We provide the following clear description for the analysis of GNN complexity:\n\nWe adopted the approach used by most GNNs[1,2] to calculate the GNN complexity. We analyze the complexity by decomposing MPNN(i.e., Eq. (2)) into three high-level operations:(1) $Z^l=X^lW^l$(feature transformation);(2) $X^{l+1}=AZ^l$(neighborhood aggregation); (3) $\\sigma(\\cdot)$(activation). We calculate the time and space complexity for each part, and adopt a sparse form based on MPNN. As shown in Table 4, the complexity consists of multiple parts and is detailed.\n\n\n\n> Q3/OCS\n>\n> Please provide the relationship of Rmax in Eq. (15) and Rsfg in Eq. (16). \n\nThank you for your valuable suggestion. $R_{max}(f)$ denotes the worst-case risk, $R_{sfg}(f)$ is an extension of $F(f, \\eta)$ in the multi-view setting. Therefore, optimizing $R_{sfg}(f)$ is equivalent to optimize the loss on the worst-case distribution $R_{max}(f)$, which can improve the robustness and stability across different views.\n\n\n**References**     \n[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S. Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems 32, 1 (2020), 4–24.\n\n[2] Blakely Derrick, Lanchantin Jack, and Qi Yanjun. 2019. Time and Space Complexity of Graph Convolutional Networks. (2019). https://api.semanticscholar.org/CorpusID:269411067", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Theoretical derivations are detailed and easy to follow.", "experimental_designs_or_analyses": "The manuscript describes the experimental settings and designs, and some hyperparameters are detailed. The experimental results and analysis are sufficient. The stability improvement is obvious, and preserving fairness and utility is also improved in most metrics.", "relation_to_broader_scientific_literature": "The paper analyzes the differences between proposed tight bound and current research. The paper describes the differences between SFG and other models.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths: \nThe paper proposes a novel tight bound that controls the weights of the model to achieve training stability and innovatively combines the generator with the graph model’s Lipschitz bound for adversarial-based fair GNN. This method addresses the stability-performance (utility and fairness) trade-off in learning fair graph representation, a challenge that has been ignored in prior works. Additionally, the paper proposed Distributionally Robust Optimization to avoid over-fitting when chasing fairness, and it’s a novel way to enhance stability and robustness. The paper clearly articulates the problem being addressed, the proposed solutions, and the derivation process.\n\nWeaknesses:\nThe update of the weight in Eq (9) has not been explained, and the Multi-convex component in Figure 1 is unclear. Also, the analysis of the GNN complexity is unclear.", "other_comments_or_suggestions": "The relationship of $R_{max}$ Eq. (15) and $R_{sfg}$ in Eq. (16) has not been clearly analyzed.", "questions_for_authors": "Please provide an explanation for the weight update in Eq (9) and the Multi-convex component in Figure 1. Please provide the relationship of $R_{max}$ in Eq. (15) and $R_{sfg}$ in Eq. (16). What is the computational method used to calculate the GNN complexity?", "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": "", "extra_scores": {}}, {"review_id": "F475O4OEPq", "reviewer": "Reviewer_skyV", "summary": "This paper proposes a Stable Fair Graph Neural Network (SFG) to address training instability in fairness-aware graph representation learning by introducing a Lipschitz constraint for stability and employing a stochastic optimization algorithm. Extensive experiments demonstrate that SFG outperforms existing methods in both fairness and utility on real-world datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "> Q. The reason for significant accuracy fluctuations observed during the optimization process in Figure 1 \n\nThank you for your insightful comment. The significant accuracy fluctuations(even though we have used a small learning rate) observed in Figure 1 are caused by **the addition** of weight fluctuations **in the encoder and mask**, which result from the conflict in optimization objectives. First, adversarial learning would leads to **significant weight fluctuations in the GNN encoder**, such as LECI[1]. Second, current adversarial-based graph models **generate a mask to shield sensitive attributes**, which conflicts with the optimization objective of $\\parallel \\textbf{m} - \\textbf{1}_d \\parallel_2^2$, as show in Eq. (45), thereby causing significant fluctuations in the mask weight($w_g$) during the optimization process. We also demonstrate this point through experiment, please refer to the figure(https://anonymous.4open.science/r/SFG-559B/mask.pdf).  The message-passing mechanism of GNN is also a possible reason for the **amplification of weight changes**.  To solve training instability of such graph fair models, we theoretically propose DRO and tight Lipschitz Constraint with mask weight to control weight fluctuations. \n\n\n**References**    \n[1] Shurui Gui, Meng Liu, Xiner Li, Youzhi Luo, and Shuiwang Ji. 2023. Joint learning of label and environment causal independence for graph out-of-distribution generalization. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NIPS '23). Curran Associates Inc., Red Hook, NY, USA, Article 174, 3945–3978.", "claims_and_evidence": "NA", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "NA", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths：\n1. The paper is well-written with a clear and logical structure, making it easy to follow.\n2. It is grounded in solid theoretical foundations, providing a rigorous basis for the proposed approach.\n\nWeaknesses:\n1. The significant accuracy fluctuations observed during the optimization process in Figure 1 leave me puzzled, as they contradict prior research findings. While adversarial learning is known to be inherently unstable, the extent of this instability in the presented results is particularly surprising. Could you clarify the reasons behind this behavior?", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "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": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: The paper presents a novel approach, Stable Fair Graph Neural Network (SFG), addressing training instability in adversarial-based fair graph representation learning. Key contributions include the derivation of a tight upper Lipschitz bound ensuring stability, and the integration of DRO to enhance model robustness across fairness perspectives.

All reviewers highlight the paper's solid theoretical foundation, particularly appreciating the clearly articulated and rigorous derivations of the Lipschitz bound and the innovative application of DRO. Experimental results convincingly demonstrate improved stability, fairness, and utility over baseline methods.

While some reviewers pointed out minor weaknesses—such as inconsistent performance across certain datasets and initial clarity issues regarding the training procedure—the authors provided thorough, detailed rebuttals addressing all concerns effectively, notably clarifying training procedures, algorithmic components, and complexity analyses.

Overall, reviewers agree the contributions are substantial and novel, and the concerns raised were comprehensively resolved in the rebuttal. Therefore, I recommend acceptance of this submission.
Decision: Accept (poster)