Aligning Relational Learning with Lipschitz Fairness
Authors: Yaning Jia
Chunhui Zhang
Soroush Vosoughi
Venue: ICLR 2024 poster (2024)
Keywords: Fairness Alignment
Relational Learning
Primary area: societal considerations including fairness, safety, privacy
TL;DR: Discuss the behavior of the relational learning while input contains irrelevant factors, then align its output changes with Lipschitz fairness.

Abstract: Relational learning has gained significant attention, led by the expressiveness of Graph Neural Networks (GNNs) on graph data. While the inherent biases in common graph data are involved in GNN training, it poses a serious challenge to constraining the GNN output perturbations induced by input biases, thereby safeguarding fairness during training. The Lipschitz bound, a technique from robust statistics, can limit the maximum changes in the output concerning the input, taking into account associated irrelevant biased factors. It is an efficient and provable method to examine the output stability of machine learning models without incurring additional computational costs. Recently, its use in controlling the stability of Euclidean neural networks, the calculation of the precise Lipschitz bound remains elusive for non-Euclidean neural networks like GNNs, especially within fairness contexts. However, no existing research has investigated Lipschitz bounds to shed light on stabilizing the GNN outputs, especially when working on graph data with implicit biases. To narrow this gap, we begin with the general GNNs operating on relational data, and formulate a Lipschitz bound to limit the changes in the output regarding biases associated with the input. Additionally, we theoretically analyze how the Lipschitz bound of a GNN model could constrain the output perturbations induced by biases learned from data for fairness training. We experimentally validate the Lipschitz bound's effectiveness in limiting biases of the model output. Finally, from a training dynamics perspective, we demonstrate why the theoretical Lipschitz bound can effectively guide the GNN training to better trade-off between accuracy and fairness.

Published as a conference paper at ICLR 2024
ALIGNING RELATIONAL LEARNING WITH LIPSCHITZ FAIRNESS
Yaning Jia!, Chunhui Zhang', Soroush Vosoughi" Dartmouth College, Hanover, NH, USA HUST, Hubei, China
ABSTRACT
Relational learning has gained significant attention, led by the expressiveness of Graph Neural Networks (GNNs) on graph data. While the inherent biases in common graph data are involved in GNN training, poses a serious challenge to constraining the GNN output perturbations induced by input biases, thereby safeguarding fairness during training. The Lipschitz bound, technique from robust statistics, can limit the maximum changes in the output concerning the input, taking into account associated irrelevant biased factors. It is an efficient and provable method to examine the output stability of machine learning models without incurring additional computational costs. Recently, its use in controlling the stability of Euclidean neural networks, the calculation of the precise Lipschitz bound remains elusive for non-Euclidean neural networks like GNNs, especially within fairnsss contexts. However, no existing research has investigated Lipschitz bounds to shed light on stabilizing the GNN outputs, especially when working on graph data with implicit biases. To narrow this gap, we begin with the general GNNs operating on relational data, and formulate a Lipschitz bound to limit the changes in the output regarding biases associated with the input. Additionally, we theoretically analyze how the Lipschitz bound of a GNN model could constrain the output perturbations induced by biases learned from data for fairness training. We experimentally validate the Lipschitz bound's s effectiveness in limiting biases of the model output. Finally, from a training dynamics perspective, we demonstrate why the theoretical Lipschitz bound can effectively guide the GNN training to better trade-off between accuracy and fairness.
INTRODUCTION
Relational learning on network data has become ubiquitous in range of real-world applications, such as social media (Vosoughi et al., 2016; Shalaby et al., 2017; Huang et al., 202 Li et al., 2021; Tian al., 2023a; Ouyang et al., 2024), drug discovery (Takigawa Mamitsuka, 2013; Li al., 2017), and knowledge engineering (Rizun, 2019; Wang et al., 2018). This surge in the use of graph data has catalyzed advances in learning algorithms that incorporate Graph Neural Networks (GNNs) with deep learning techniques (Gori et al., 2005; Scarselli et al., 2005; Li et al., 2016; Hamilton et al., 2017; Xu et al., 2019; Zhang al., 2022, 2023a,b,c; Liu et al., 2023; Yuan et al., 2024). Among GNN architectures, Graph Convolutional Networks (GCNs) (Kipf& & Welling, 2017; Zhang & Chen, 2018; Fan et al., 2019) stand out due to their use of convolutional layers and message- saassagg-pssingggg mechanisms to enable effective learning graphs.
Amidst the widespread success of GNNs diverse applications, there has been growing societal concern for developing ethical and prosocial learning algorithms for networks (Vosoughi et al., 2017, 2018; Dong et al., 2021; Lahoti et al., 2019; Kang et al., 2020; Mujkanovic et al., 2022). Many existing approaches, however, fall short of explicating the interactions between the GNN model and its graph-based training data. This opacity hampers the model's parameter tunability, failing to adequately address latent biases in the graph data, thereby undermining model reliability post-training. In this context, our objective is to deepen our understanding of the input-output dynamics of GNNs
" *Corresponding to soroush. voscught edartmouth edu. YJ and CZ contributed equally and are listed alphahetically by last name. YJ, from HUST, was mentored by CZ and SV from Dartmouth College.

---

Published as a conference paper at ICLR 2024
in relation to model parameters. Specifically, confront the following pivotal question: How can we minimize unintended shifts in GNN output, especially when the graph training data encompasses implicit, learnable biases, without resorting to computationally intensive methods?
This question is crucial in scenarios where the training graph data may contain spurious statistics that result in unfair or inappropriate correlations. Our work aims to provide mechanism that curtails such fluctuations in the GNN model's predictions during training, ensuring they are not disproportionately influenced by unfair factors. The implications of this work extend to enhancing GNN generalization, debiasing GNNs, and safeguarding against data perturbations by regularizing output changes. Although existing GNN training methodologies have yielded impressive results, they often lack interpretability, particularly in understanding how layer-by-layer learned biases affect output stability or fairness (Dong et al., 2021; Kang al., 2020; Liao et al., 2021; Li et al., 2021; Yue et al., 2022).
In robust statistics, Lipschitz bounds serve as valuable tools for assessing maximal output changes in response to input biases (Virmaux & Scaman, 2018; Fazlyab et al., 2019; Jordan & Dimakis, 2020; Latorre et al., 2020; Huang et al., 2021b). Prior work (Dwork et al., 2012; Shi et al., 2022; Agarwal et al., 2021) has mainly focused on fairness and robustness in MLPs, CNN, or statistical models, often relying on explicitly labeled sensitive attributes, such as gender, race, and age.
Our research distinguishes itself by extending fairess considerations specifically to the realm of relational learning on graphs. We achieve this by constructing a fairness framework that does not necessitate manual annotation of sensitive attributes. Instead, approach is designed to identify and mitigate biases inherent in node features and connectivity patterns within real-world graph data. Our methodology aligns closely with the principles of ranking-based individual fairness as articulated by Dong et al. (2021). In this framework, fairness is guaranteed if the relative ordering of instances, characterized by ranking lists based on the similarity between instance and other instances, remains consistent in both input and output spaces. Importantly, this ordering should not be distorted by irrelevant or hidden biases in the input data. When these conditions are met, the model output will inherently satisfy individual fairness criteria. To operationalize these principles. we introduce computational strategy that leverages the Jacobian matrix for the efficient calculation of the Lipschitz bound. Our computational approach utilizes intermediate tensors specifically, the gradients of the model's outputs with respect to its inputs - in Py Torch, facilitating practical and scalable implementations. This is particularly advantageous for large-scale graph datasets. area where existing methods often falter in terms of scalability. Our contributions can be summarized as:
We introduce a Lipschitz bound specifically tailored for GNNs to align with rank-based individual fairness. This allows to characterize and constrain the perturbations in GNN predictions induced by input biases.
We develop an efficient method for computing the Lipschitz bound of GNNs by leveraging the Jacobian matrix, thereby accommodating the complex topology of graph structures for practical implementation.
Through theoretical and empirical validation, we demonstrate that our approach is both versatile and effective, serving as plug-and-play solution that can enhance existing fairness-oriented graph learning methods.
2 PRELIMINARIES
I. Lipschitz Bound A function f: RRa - Rmm is said to be Lipschitz continuous on input set X C TR there exists a bound K 2 such that for all x. y E X, satisfies:
fxx) f(yl S K | all Vx, y E X.
The smallest possible K in Equation (1) is the Lipschitz constant of f. denoted Lip(f):
[lf( f(y)l
Lip(J)
sup
2.yEX -0
In this context, f is referred to as a K- K-Lipschitz function. The Lipschitz bound essentially quantifies the maximum change in the output of a function corresponding unit-norm perturbation in its
2

---

Published as a conference paper at ICLR 2024
imput. This makes the Lipschitz bound an important measure of neural network's stability with respect to its imput features. However, determining the exact Lipschitz bound can be computationally challenging. As discussed in Virmaux & Scaman (2018), finding the exact Lipschitz bound is shown to be NP-hard for deep models. Consequently, an upper bound is often sought as a practical alternative, and this upper bound is also referred as the Lipschitz bound.
Graph Neural Networks We assume given graph G = G(V, where V denotes the set of nodes and E denotes the set of edges. We will use X { { æ2. ,Ny Rº to denote the N node features in R", as the input of any layer of GNN. By abuse of notation, when there is no confusion, we also follow GNN literature and consider X as the RR matrix whose i-th row is given by x i = 1, N, though it unnecessarily imposes an ordering of the graph nodes.
GNNs are functions that operate on the adjacency matrix A E RNNN of a graph G. Specifically, an pm IR x post that depends A. Formally, have: L-layer GNN can be defined f RRN x
Definition 1. An I-layer GNN is a function f that can be expressed as a composition of message- passing layers h and T. 1 activation functions p', as follows:
f f= = o pl-1o....
h²
where h :R + FR is the I-th message-passing layer, p² RFF - FR is the non-linear activation function in the I-th layer, and F²11 and F¹ denote the input and output feature dimensions for the 1-th message- passagg-passing layer h',, respectively. In addition, we set 1,
Rank-based Individual Fairness of GNNs Rank-based Individual Fairness on GNNs (Dong et al., 2021) focuses on the relative order of instances rather than their absolute predictions. It ensures that similar instances, as measured by the similarity measure S(;, receive consistent rankings or predictions. The criterion requires that if instance is more similar to instance than to instance k. then the predicted ranking of j should be higher than that of k, consistently. This can be expressed as:
if S(x,, 2;i) > S(x,, æx), then Yıj Y.k.
(4)
where Yi and Yú2 denote the predicted rankings or predictions for instances æ; and æys respectively, based on the input instance æ; The criterion ensures that the predicted rankings or predictions align with the relative similarities between instances, promoting fairness and preventing discriminatory predictions based on irrelevant factors.
3 ESTIMATING LIPSCHITZ BOUNDS ON GNNS FOR FAIRNESS
We estimate the Lipschitz bounds for GNNs, which is crucial for analyzing output perturbations induced by input biases: Initially, in $ 3.1, we establish Lipschitz bounds for GNNs and provide closed-form formulas for these bounds. Next, in $ 3.2, we derive the model's Jacobian matrix to facilitate Lipschitz bounds' efficient calculation for practical training feasibility. Lastly, 3.3, we use these bounds to explore individual fairness, demonstrating how model stability can ensure output consistency, aligning with based individual fairness definition.
3.1 STABILITY OF THE MODEL OUTPUT
To analyze the stability of the model's output, we examine the Lipschitz bound of the Jacobian matrix of the GNN model. In this regard, we introduce the following lemma:
Lemma Given function g 1. + R² with components gs for i [n]], the Lipschitz bound of g. denoted by Lip(g), is bounded above by the norm of the vector of the Lipschitz bounds of its components, that is:
Lip(g) - [[ii((:))]
(5)
where || represents the norm of vector.
Lemma 1 provides inequality that relates the norm of the difference between two vector- vector-valued functions, (2x) and g to the norm of a vector composed of the component-wiss differences of the functions evaluated and y. Based on Lemma
now present the following theorem:
3

---

Published as a conference paper at ICLR 2024
Theorem Let Y the output of an L-layer GNN (denoted as f()) with as the input.
Assuming the activation function (represented in p(-)) is ReLU with Lipschitz bound of Lip(p) 1. then the cumulative Lipschitz bound of the entire GNN, Lip(f), satisfies:
Lip(F) & max II F"
(6)
1=1
where Fd represents the oulput dimension of the 1-th message-pussing layer, 3 is the index of the [ (h')l] Notably, J:(h') denotes the i-th row of the Jacobian matrix of the 1-th layer's input and output, and [J(H]], is the vector corresponding to the j-th node in the 1-th layer h' (.).
node (e.g.. j-th), and the vector [J [ + [[]2(t))]
Proof Sketch: We initiate with investigating the Lipschitz property of GNNs, considering 1 1-Lipschitz activation functions (e.g.. the widely- ReLU (Nair & Hinton, 2010). The hidden states of node feature 21 and 22 are represented as 2 and 22 respectively. The Lipschitz bound between these hidden states is calculated
[l - [[(h(2)) (((()))A((2a)ll Using the triangle inequality, this equation
25 22
1 22
is further bounded by
[[2--22l
||>-=||||
<
h(a1))-(())))) [1
The Lipschitz bound of individual elements
also analyzed, again using the triangle inequality. The proof then proceeds to analyze the Lipschitz bound of the individual elements using the operation of the I-th layer in f(-). Finally, the Lipschitz bound for the GNN is established as Lip(f) max, II F" [ 0],
It establishes that the difference in the output Y is controlled by the Lipschitz bound of the GNN, Lip(f), and the difference in the input X. The above analysis assesses the model output stability with respect to irrelevant biases learned layer-by-layer from the input, during the forward.
The aforementioned Theorem provides the cumulative Lipschitz bound of the entire GNN based on the layer outputs and the corresponding Jacobian matrices. It establishes that the Lipschitz bound of a GNN regulates the magnitude of changes the output induced by input biases, consequently guaranteeing the model output stability and faimess against irrelevant factors.
3.2 SIMPLIFFYNG LIPSCHITZ CALCULATION OF THE GNN VIA JACOBIAN MATRIX
The approach presented in Theorem for estimating the Lipschitz bounds Lip(f) across different layers in the GNN f(-) requires unique explicit expressions for each component. This makes the process somewhat challenging. Nevertheless, this difficulty can be mitigated by computing the corresponding Jacobian matrices, as shown in Equation (6). By leveraging the values of each component in the Jacobian matrix, we can approximate the Lipschitz bounds in straightforward
manner. Additionally, the expression I F" [ (M')) from Equation (6) provides valuable insights into the factors that influence the Lipschitz bounds, such as the dimensions of the output layer and the depth of the GNN layers.
However, considering the potential for multiple hierarchical layers in the network, their cumulative effect could lead significant deviation from the original bounds. Therefore, is beneficial to consider the entire network single model and directly derive the Lipschitz bound from the input and output. this subsection, we provide a simplified method to derive the Lipschitz bound in Equation (6) for facilitating fairness training. To achieve this, then introduce the Jacobian matrix. Let [].] denote the Jacobian matrix of the i-th node, which can be calculated as:
aY
8Ya
BY,
axa
ax
OX
8Y
8Y:2
8Xa
ax,3
8x pprnn
[J)] panx
HY 8Xn
YY (PoR
8Y you
8Xaa
8X pxp
por x pin
Please refer Appendix B for the complete proof due space constraints.
4

---

Published as a conference paper at ICLR 2024
We can define [Jilpmyyp" [ 12:
where Jij
aY: 8x 8x
aY
0Y,
8x
capturing the local interactions of node i, rather than relational dynamics within the entire graph." Then we let J, [||all| [| .... I1 [I]", J [JT "T", ,". [N
To analyze the Lipschitz bounds of the Jacobian matrix of output features for N nodes, we define LB(J):
Fu
F12
J
J21
Jn
J2pu
LB(J)-
(8)
INN
IN2
IN
N
where Tig = || ||- Based on the definition of [B[(), we can further establish the Lipschitz bound of the entire GNN model during training in the next subsection. To measure the scale of LB(J) of GNN f()), we define a Lip(f) that satisfies
Lip(f) LB(J)
This calculation involves taking the 12-norm for each row of [[B((])) and then taking the infinite norm for the entire [LB(JJ)loo,2 Now we have proposed an easy solution as Equation (9) to approximate I F' [ for facilitating its feasible computation in practical training.
3.3 ILLUMINATING GNN FAIRNESS: A RANK-BASED PERSPECTIVE
Regularizing GNNs for input-output rank consis- tency, particularly in the context of rank-based individual fairness, is made possible by leverag- ing the Lipschitz bounds of GNNs. Specifically, we denote this Lipschitz bound as Lip(f)
Algorithm 1 JacoLip: Simplified PyTorch-style Pscu- docode for Lipschitz Bounds in Fairness-Orie Oriented GNN Training
max, I F" [(h)),
We aim to mit-
graph noural network model Train model for N epochs for x, A, target datalesder:
modol:
igate inherent biases in the training data and to advance individual fairness. We accomplish this by enforcing Lipschitz constraints on the model's output, thereby guarding against biases that are incrementally learned from the input dur- ing the forward pass. This ensures consistency between the ranking lists based on the similarity matrix of each node in the input graph Sc and the similarity matrix of the predicted outcome space Sy, as outlined in $ 2.
pred - model (X, A)
Loas CrossEntzopyLoss (pred, target)
Compute Liyschitz bound for inpus jacobian Jaco (X, pred) model_ift ip = (jacobiaaa 8q. (8) cum norm (model_
Eg. (9)
Optinize model with Lipashitz bound less ce lass Tess. backbaackardd) optimizer. (tep()
cum_lip
We propose plug-and-play solution, termed Ju- coLip, that integrates effortlessly with existing bairness-focuse GNN training pipelines. Algorithm 1 provides a detailed Py PyTorch-style pseudocode for this approach. The method involves training the GNN model for predefined number of epochs, while computing the Lipschitz bound for the model output using gradients and norms of the input features. This Lipschitz bound is then incorporated as regularization term in the loss function to keep the model's output within constrained boundaries. Our approach efficiently mitigates individual biases and enhances the fairnsss of GNNs without incurring significant computational overhead. This "nearly-free" fairness regularization is facilitated by PyTorch 's built-in gradient functions, thereby achieving the benefits of Lipschitz regularization without substantial additional computational burden.
4 EXPERIMENTS
Here, we perform two major experiments to validate the Lipschitz bounds discussed the previous section: (1) We use Lipschitz bounds to constrain the output consistency of GNNs, aiming to enhance rank-based individual fairness in node classification and link prediction tasks; (2) We examine the effects of Lipschitz bounds the gradients and weights of GNNs, particularly concerning biases induced through training dynamics. Additional experiments can be found in Appendix C.
Pleasee refer Appendix B.4 for more discussions.
5

---

Published as a conference paper at ICLR 2024
4.1 SETUP
Datasets We conduct experiments on six real-world datasets commonly used in prior work on rank-based individual fairnsss (Dong al., 2021). These include one citation network (ACM (Tang et al., 2008)) and two co-authorship networks (Co-author-Ch, and Co to--author-hhy (Shchur et al., 2018)) for node classification, and three social networks (BlogCatal SegCatalog (Tang & Liu, 2009), Flicks (Huang et al., 2017), and Facebook (Leskovec & Mcauley, 2012)) for link prediction. We adhere to the public train/val/test splits from Dong et al. (2021). Dataset statistics and details are in Appendix E.
Backbones We use two widely-adopted GNN architectures for each downstream learning task: Graph Convolutional Network (GCN) (Kipf Welling, 2017) and Simplifying Graph Convolutional Network (SGC) (Wu et al., 2019) for node classification, and GCN and Variational Graph Auto- Encoders (GAE) (Kipf& & Welling, 2016) for link prediction. Model details are in Appendix D.
Baselines In contrast prior research on group faimess in graph embeddings (e.g.. (Bose & Hamilton, 2019; Rahman et al., 2019)), which often focuses on fairness for subgroups defined by specific protected attributes, our work centers on individual fairness (Dong al., 2021) without reliance on such attributes. Therefore, methods for group fairness are beyond the scope of our comparison. To assess the efficacy of our approach in achieving individual fairness, we benchmark against three significant baselines tailored specifically for rank-based individual fairness:
Redress (Dong et al., 2021): This method proposes rank-based framework to enhance the individual fairness of GNNs, integrating both utility maximization and faimess promotion into joint end-to-end training framework.
InFoRM (Kang et al., 2020): Originally designed for conventional graph mining tasks such as PageRank and Spectral Clustering, InFoRM is based on the Lipschitz condition. We adapt it to GNNs by combining its individual fairness loss with the unity loss of the GNN backbone for end-to-end optimization.
PFR (Lahoti et al., 2019): PFR focuses learning fair representations for individual faimess and outperforms traditional approaches in this regard. As PFR is more of a pre-processing strategy and not tailored for graph data, we apply it to the input node features.
Evaluation Metries We employ two key metrics for evaluating rank-based individual faimess: classification accuracy (Acc.) for node classification tasks, and the area under the receiver operating characteristic curve (AUC) for link prediction tasks. For assessing individual fairness, we use the widely adopted ranking metric NDCG@K k (Järvelin & Kekäläinen, 2002), which measures the similarity between the rankings generated from Sy (result similarity matrix) and Sa (oracle similarity matrix). Average NDCG@k values are reported across all nodes, with & = 10.
Implementation Details The learning rate set at 0.01 for all tasks. For models based on GCN and SGC, we use two layers with 16 hidden units each. For GAE-based models, we employ three graph convolutional layers, with the first two layers having 32 and 16 hidden units, respectively. Adam is used the optimizer (Kingma & Ba, 2015). Further details, including code, dataset splits, and hyperparameter settings, are available in Appendix D. Our code has been released at fairness.
https: / thu.......... com/ http/cchunuuiiaaa zng wwwpsn////ppcchhc
4.2 EFFECT OF LIPSCHITZ BOUNDS ON RANK-BASED INDIVIDUAL FAIRNESS IN GRAPIS
The experiments validate the efficacy of Lipschitz bounds for enhancing individual fairness in GNNs, specifically from ranking perspective. Results are consolidated in Tables 1 and 2 for the node classification and link prediction tasks, respectively.
In Table 1, our method, JacoLip, yields promising results, outperforming the baselines in achieving
a superior trade-off between accuracy and fairness: (i) When applied to Vanilla models such as GCN or SGC, JacoLip enhances faimess performance (measured by NDCG@ 10) while maintaining comparable accuracy. This result substantiates that the plug-and-play nature of Lipschitz bound regularization effectively mitigates bias during the training of standard GNN backbones, thereby fostering a balanced trade-off between accuracy and fairness; (ii) Additionally, when integrated with the existing citrness-centrie algorithm Redress, JacoLip further constrains irrelevant biased factors during training and marginally improves the trade-off between accuracy and fairness across all datasets and backbones.

---

Published as a conference paper at ICLR 2024
Table 1: Evaluation on node classification task: comparing under accuracy and NDCG. Higher performance in both metrics indicates a better trade-off. Results are in percentages, and averaged values and standard deviations are computed from five runs. The improvement is within brackets. We bold the best result and underline the runner-up.
Feature Similarity
Structural Similarity
Data
Model
Fair Alg.
utility: Acc.
faimess: NDCG@ 101
utility: Acc.7
faimess: NDCG 10;
Vanilla (ipp Wetlon 2113)
-2.49-0.6
47.331:100
72.49-1.6
25.42:10.6
InFoRM (Kay 2029)
68.03=0.3((
66.15%
-
69.13+0.35 5( 1.645))
12.02=0 6( 6(-52 7%6
GCN
PFR ad
67.68+11.1 6.30%)
31.20+00.2 1%
09.00++0.7
-4.81981
23.86+1.333
-6.18%
Redress (Degg a a01
71.75-10.4(
1.02%)
49.13:10.4; (33.80%)
72.03:-0.9i
0.6398)
29.00-00.4;
144.4%
JacoLip ton Vanilla)
72.3740.33
-0.16%)
49.80:10.33
71.9710.31 -0.7156)
27.9110
+99.99%)
JacoLip Redress)
71.92200.21
-0.7788))
53.62=0006+13333%
31.80=0.44+5511%
ACM
Vanilla ata 2019)
68.10=100
55.75#1.1
68. 08.10=1.0
37. 18:2..6
InFoRM (Kouget 2009
06.81++0.0(+00000
48.25=00.5( 13.5%)
06.71+0.01
-2447788
28.33=0.6 -
SGC
PFR (uaven arat 9019
67.97+00.7( 0.82%)
34.71-1..1
37.7%)
67.78:+0.16 i4 0.915%
37.15+0.6.
0.08%)
Redress (oer
97.16100.2(11.881
58.6110.4
67.7710.4 -0..9955))
38.9510.1 +44.7%)))
JacoLip ion Vanilla)
73.84=0.2447.95%%
22.00=0.((+11222
38.36
1(+3.17%)
JacoLLip (on Redress)
72.36610.4(
69.22
72.52....(++6.12%%
41.07
Vanilla (Rly Welling 201)
90.50-0.3
30.84+1.2
90.59-0.3
18 08
InFoRM (Kong aat 200
88.66+11.1
2.13%)
53.38++100
5500%%
87.55++0.9(
3.36%%
19.18 10188+0.9, 9 (4.87%)
GCN
Redress (Deuz et 2020)
PFR (Laton 2019
90.70==0..(+0.122%
87.5110.77(
3.40%)
37.12.10.9/
55.01=1
27%0%
86.1610.21
89 16110.3 -1.889)
4.8996)
21.28 3/ +1. 1%6)
11.98 11 34.5%)
Lip (on Vanilla)
90.6810.3( + 0.900%
55.35.10.2
8.87%)
89 23.051 1.50%6
21.8210.2 19.33%)
Jacol.ip (on Redress)
90.63200.3 +0.0056
68.20==0.4(+44.999
89.21 1.5256)
31.82:0.04444.11
Cs
Vanilla
87.48-0.3 0.8
74.00+0.1
87,48-0.8
02.36-0033
InFoRM (Kan std 2009
25.007=0111-000000
+1,20=0.1(+0030000 30%)
32.37=0
4( (3.0%)
SGC Redress (llng at a01
PFR (1abor 2019
88.31-00. 0.99.9)%
- 34.6%)
84 84.34+0.3i
3.50%%
28.87+0.91
10.8%)
90.01 + 2.80%)
76.60.10.1/ 1.3551%)
80.35.10.11
+2.14%)
34.2410.2
15.81%)
JacoLip ton Vanilla)
90.23::0.2(+31149)
89.531006 -2-32345)
12
JacoLip Redress)
90.12=003((33.
77:01=0.1(-4.0779
34.89=0.5(+7.825%
Vanilla (oppe Waiing 2013
94.81 0,2
34.83.11.1
94.81 0.2
1.57-0.1
InFoRM (aa atd, 2029)
89.3320.88(
5.788%)
31.25:10.00
91. -0.35%)
1.77
12.7%%
GCN
PER (1aven arat 2019
89.74110.5(
5.35%)
24.16.10.
30.8%)
87. $7.2610.2( 7.96%)
1.20:0.1(
23.6%
Redress (oer
91.6310.7
-0.195))
43.61110.5
+22.9%%
1.93
JacoLip (om Vanilla)
61.6000.21 -0.2255
37.33=
18.)
93 99+0 0686)
2(
JacoLip (on Redress)
94. 14.50+00.2 -0.322%)
49.37=0034441.75%%
33 86+00.9
111009----00000 1.002
0.72:30.(443.366)
phy
Vanilla ow (010)
94,45-0.2
49 63+0.1
94.45-0.2
3.61=0.1
InFoRM (kong any
92.01
2.58%)
43.87 11.8%)
94.27+-0.3 0.19%)
3.64 i 0.83%)
SGC Redress (Dou sl, 2020)
(Labon anal, 2019
39.74.10.3(
4.999%)
28.54.10.1 (2.5%)
89.7310.31
5.0006]
2.6210.11 27.
91.302 1[ 00.16%)
13.400:001((77.6600
93 93.91+0.2
-055445)
L.03000((11666
Lip (om Vanillai
94.20=0033
00.06%5
30.70:=0 16%
93. 03.58+0.22 0.92981
3.80=0.06 20%)
Jacol.ip (oe Redress)
93.28+-0.1
1.24%)
39.20- 19.3%)
93.90+ 1.1 0.40%%
4.30
Similar trends are observed for the link prediction task, as seen in Table 2. Here, the performance of Vanilla models (GCN or GAE), InFoRM, PFR, Redress, and JacoLip is evaluated based on AUC for utility and NDCG@ 10 for fairness. Across both tasks, JacoLip consistently shows either competitive or superior performance when compared to the baselines. These improvements minimal computational overhead, as JacoLip efficiently calculates Lipschitz bounds using Py Torch's 's built-in gradient functionality, further detailed in 3.3 and Table 5.
achieved with
4.3 IMPACT OF LIPSCHITZ BOUNDS ON TRAINING DYNAMICS
We further analyze the impact of Lipschitz bounds through the optimization process and explore its dynamical interactions with weight parameters, gradient, fairness, and accuracy in Figure 1:
For the nonlinear GCN model, our proposed method, JacoLip, imposes beneficial regularizations on gradients. Specifically, during the initial epochs, JacoLip effectively stabilizes gradient magnitudes, resulting in higher accuracy (e.g., approximately 20% improvement in feature similarity and around 40% in structural similarity) compared to the Redress baseline. Concurrently. JacoLip maintains superior fairness metrics (NDCG), exceeding the baseline Redress; For the linear SGC model, JacoLip similarly achieves favorable trade-off between fairness and accuracy relative to the Redress baseline. Initially, Jaco ip on SGC shows better fairness (e.g., approximately 0.2 NDCG on feature similarity) than the Redress baseline, with only minor decrease in accuracy. As training progresses, the accuracy of JacoLip on SGC tends to match or even surpass that of Redress.
In summary, the observed trade-off between accuracy and faimess during the training phase can be attributed to the constraining effect of Lipschitz bounds on gradient optimization. The higher expressivity of the nonlinear GCN model renders it more susceptible to loss of consistency in input- output similarity ranking, crucial for fairness. Conversely, the simpler linear model more readily preserves this consistency, and here, Jacol prioritizes accuracy. These insights elucidate the
7

---

Published as a conference paper at ICLR 2024
Table 2: Evaluation on link prediction tasks: comparing under AUC and NDCG.
Data
Model
Fair Alg.
Feature Similarity
Structural Similarity
unility: AUC1
farness: NDCG@101 10
utility: AUC1
faimess: NDCG@ 101
Vanilla (Gge Weliag. 330ty
85.8710..1 1
16.73:..1
85,8710.11
12.17:0.55
InFoRM (K
T9.8520.66
-7.01%)
15.57=0.21 -6.93%)
81.0020.11
26.1840.3( 31-69.331-195555
GCN
PFR (uace asi, 2005:
$4.25.00.2(
8.9%
16.37
2.11%)
81.88.00000
- -2.32%)
29.60.10.4( -8..84))
Redress (beeg 2001
$6.40+00.8
10.72%
17.66+0.2(
15.36%)
86.25+00.3
(0.44%))
34.62+0.7(
6.62%)
JacoL.p Ap (on Vanillaa
N6.51
17.70=006(45 45.779%
86.90:0.5(+116675
35-000044--779985
JucoLip (on Redress)
85.91220.2((
+0.0415)
18.0210.0(7777997
80.8110.50
+3.1
35.85 1.N55004+000447
Blog
Vanilla (Kipf Weliag, InFoRM (kargerat, 2030
85.7240.1
17.13:0.1
85,72:0.11
41:99:0..4
90.01=00.2
6.86%%
16. 12:002 5.90%)
82.86.00.00
3..4%%
27.29400.3(
35.0%)
GAE PHR di 2019
83.83+0.1(
-2 20%)
16 16.64+0.00-2
83.8++011
16%)
06.91+000((1445586
Redress (Deeg 2922
8167=009 - 2.229%
18. 19:00.0 166.0.1166.999.
%
35.1140.7(336626
JacoLLip (on Vanilla)
85.75:10.4:+0003%)
17.96:00.(11 (-88%)
85.8610.5( +0. 10.18%)
42.2010:31 0.500%
Jacol.pp Ap (on Redras))
86.70+0..4 0.02%)
18.34++..(
86.31+0.54 +0.69%))
43.60 0.3(+3.83%
Vanilla (Kgtf Wetiag,
92,20:1.33
13.10:1.22
92,20:1.33
22 22.35::0.3
InFaRM (targerat, 2030
91 01.00-0.0(( 0.88%)
11.95:0.1( 8.78%
91.73+0.1( 0.51%%
23.28 4.16%)
GCN Redress 2922
PHR dusceiie 2019
91 11.91=00(--003111
12 12:940000 1222
91 06+ - -3.5%%
19.80+0-0(111 11.446)
91 01.3820.1( -0 89%
13.58 +33.66%
92 2.22 51%%
28. 51 3%6)
JacoLLip (on Vanilla)
92.75.0.3:+05599
13.74 4 1-89%)
Jacol.ip Ap (on Redras))
82 53-00.0. (0.55%
14.377+0.4
92.69 0. (...00))))
0.42+28.2%) 28.65
Flickr
Vanilla (igt
89,9810.1 1
12.7710.0
89,9810.1
28.58.00.2
InFoRM (largerat, 2030
88. 06.77. 1.36%)
12.07=0.1( 5.48%
0..11-0.0
15.7840.3
1%6)
GAE Redress
PER du 2019
90.30=
12 12.12=0.1(-64000
90 10-00-0.11 39%)
20.660 3( 256)
89. 45:05.5 -0 58%%
1121=0.1(+11.3
50.2100. 51.1
29.83 2 556)
JacoLip (on Vasilla)
80.88.10.3) 0..11%)
14.37.0.11 +
80.95.10.2( 0.000%
25.7410M
Jacol Ap (on Redras))
80
99.92-0.33( 0.06%)
14.85-0.1(+16.2995
89.56+0.21 -0.46%)
30.0 (.5..8..7)
Vanilla oxpra Wollig 2017)
06,60+1.7
23.07+0.2
96.60+1.7
16.16+1.1
InFoRM (Kang stageral. el. 2029
90 00.26=00.1(- -5 50%)
23 23:2300.3 3 3/40
96.6610.66+11199 %)
15.18
GCN
Redress (Deeg
PFR asd, 2019:
96.49:1.6
17.1111.. 8.86%)
29 29.60+0.1( 28.3%)
21 -
94.87 1.9( - 0..7%%
92.66+0.4| 3.08%%
17.
19.53
18.00%
67.5%)
Jacol.ip up (on Vinilla)
96 06.21=0.20 +0 63%)
29 19:47:0.3 3 + 7%)
95-46=0.55
-4.14
10 7%6)
LacoLip (on Redress)
Fe. 16.0122021 +0.533%
30.07 3/+ 33%)
92.7620099
2.997%
28.64_0.1-73.111
Facebook
Vanilla poyra Wollig, 3009
98.54+0.0
26. 75.71
98,54-0.0
27.03+0.1
InFoRM (Kang 2009
90.50=0.11
16%)
22.77:0.22 -(14.9%)
95.03:0.11
-3.56%)
25
GAE
PFR tLate 2019;
96.9120.1(-
-1.65%
23.5220.11 (-12.1%)
98. 98.28.10.0
-0.20%
22.89.10.3 15.3%%
Redress (Deeg atat,
95.98+1.54
2.60%%
28.43-003
6.22%%
94.07+ 1.7
4.34%%
33.53
0.533-0.2++440055
Jacol up (on Vanillio
97 07.00=00111 16.66%
27.4
97.02 1.1( -1.54%
30.90 5(-111
JacoLip (oo Redress)
96. 10100.11
-2 15%]
26.46:0..((+63995)
91.221 1.1( -138%%
31.62.0.35 -1771166
dynamic behavior of model training under Lipschitz bound constraints, illustrating how JacoLip can enhance fairness while retaining competitive accuracy.
RELATED WORKS
Lipschitz Bounds in Deep Models. Prior research on Lipschitz bounds has primarily focused on specific types of neural networks incorporating convolutional or attention layers (Zou et al., 2019; Terris et al., 2020; Kim et al., 2021; Araujo et al., 2021). In the context of GNNs, (Dasoulas et al., 2021) introduced a Lipschitz normalization method for self-attention layers in GATs. More recently, (Gama & Sojoudi, 2022) estimated the filter Lipschitz bound using the infinite norm of a matrix. In contrast, the Lipschitz matrix in our study follows distinct definition and employs different choices of norm types. Additionally, our objective is to enhance the stability of GNNs against unfair biases, which is not clearly addressed in the aforementioned works. We refer to Appendix A for vital details.
Fair Graph Learning. Fair graph learning is a relatively open field (Wu et al., 2021; Dai & Wang, 2021; Buyl & De Bie, 2020). Some existing approaches address fairness concerns through fairnes--aware augmentations or adversarial training. For instance, Fairwalk (Rahman et al., 2019) a random walk-based algorithm that aims to mitigate fairness issues in graph node embeddings. Adversarial training is employed in approaches like Compositional Faimess (Bose & Hamilton, 2019) to disentangle learned embeddings from sensitive features. Information Regularization (Liao et al., 2021) utilizes adversarial training to minimize the marginal difference between vertex representations. In addition, (Palowitch & Perozzi, 2020) improves group fairness by ensuring that node embeddings lie on a hyperplane orthogonal to sensitive features. However, there remains ample room for further exploration in rank-based individual fairness (Dong et al., 2021), which is the focus of our work.
Understanding Learning on Graphs. Various approaches have emerged to understand the under- lying patterns in the graph data and its components. Explanatory models for relational/graph learning (Ying et al., 2019; Huang et al., 2022; Yuan et al., 2021; Chen et al., 2023) provide insights into the relationship between a model's predictions and elements in graphs. These works shed light how
8

---

Published as a conference paper at ICLR 2024
0.55
Redress (GCN)
Jacolip (GCN)
0.45
0.8
NDCG-810
Accuracy
NormtW)
W Grad
0.35
0.5
0.10
Feature similarity
0.25
Redress (GCN)
0.2
Redress (GCN)
Redress (GCM)
0.05
jacoLip (SCN)
JacaLip (GCN)
JacaLip (GCN)
0.15
160
320
480
640
0.0g
150
320
450
640
180
220
480
540
0.00
160
320
480
540
Epoch
Epoch
Epoch
Epoch
0.60
1.00
200
0.016
0.57
0.35
150
0.012
NDCG-910
Accuracy
Norm(WW)
W Grad
0.54
0.50
100
0.008
0.51
Redress (SGC)
0.85
Redress (SGC)
50-
Redress (5GC)
0.004
Redress (SGC)
JacoLip (SGC)
JacoLip (SGC)
JacoLip (SGC)
jacoLip (SGC)
0.40
18
32
0.50
0
18
32
16
0.000
0
18 Epoch
24
Epoch
Epoch
Epoch
1.00
0.20
Redress (GCN)
JacoLip (GCN)
0 027
0.25
0.1
NDCG 810
Accuracy
NormEW)
W Grad
0.014
5.50
12
0.10-
Structural similarity
0.007
Redresss (GCN)
0.25
Redress (GCN)
Redress (GCN)
0:05
JacoLip (GCN)
JacoLip (GCN)
JacoLip (GCN)
0.000
0
360
320
480
640
2.00
160
320
450
660
%
360
320 Epoch
483
640
0.00
0
165
320
480
660
Epoch
Epoch
Epoch
0.048
1.00
200
0 00.000
0.036
0.95
150-
0.0075
NDCG-810
Accuracy
Norm(W)
W. Grad
0.024
0.30
200
0.0050
0.012
Redress
0.85
50
0,0025
Redrass (SGC)
JacoLip (SGC)
JacoLip (SGC)
JacoLp (SGC)
JacoLip (SGC)
0.000
6
39
0
39
26
26
Epoch
Epoch
Epoch
Epoch
Figure 1: Study the Lipschitz bounds" impact on model training for rank-based individual fairness. We perform experiments the co-author-Physic dataset using both nonlinear (GCN) and linear (SGC) models. The training dynamics are assessed by monitoring the NDCG, accuracy, weight norm, and weight gradient the number of epochs increases. Upper two rows: Metrics under feature similarity; Lower two rows: Metrics under structural similarity.
local elements or node characteristics influence the eecision-making process of GNNs. However, our work differs in that we investigate the impact of Lipschitz bounds on practical training dynamics. rather than focusing on trained/fixed pained/fied--prrmetter model inference or the influence of local features on GNN decision-making processes.
CONCLUSIONS
We have investigated the use of Lipschitz bounds for promoting individual fairness in GNNs from a ranking perspective. We conducted a thorough analysis of the theoretical properties of Lipschitz bounds and their relation rank-based individual fairness. Building on this analysis, we introduced JacoLip, a fairness solution that incorporates Lipschitz bound regularization into the GNN training process. To assess the efficacy of JacoLip, we conducted extensive experiments on real-world datasets for both node classification and link prediction tasks. The results consistently demonstrate that JacoLip effectively constrains bias during training, thereby enhancing fairness performance while preserving accuracy.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
Our research on Lipschitz bounds for GNNs carries societal implications. On the positive side, our work enhances the stability and interpretability of GNNs, contributing to safer Al systems across various domains. Improved fairness and interpretability can help mitigate biases and ensure more equitable decision-making outcomes. On the other hand, the advancement of GNNs also brings forth concerns about potential misuse and unintended consequences. Like any deep learning technology, GNNs have the potential unfairly impact certain groups or perpetuate existing biases.
We underscore the importance of fair training procedures, stringent privacy safeguards, and respon- sible deployment and monitoring of GNNs. this manner, our work serves as a foundational contribution to GNN research, emphasizing the need to consider broader impacts and potential harms while implementing suitable mitigation strategies.
REFERENCES
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, 2021. 2, 15, 20, 22
Alexandre Araujo, Benjamin Negrevergne, Yann Chevaleyre, and Jamal Atif. On Lipschitz regu- larization of convolutional layers using toeplitz matrix theory. In AAAI Conference Artificial Intelligence, 2021. 8, 15
Avishck Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference on Machine Learning, 2019. 6,
Maarten Buyl and Tijl De Bie. Debayes: a bayesian method for debiasing network embeddings. In International Conference Machine Learning, 2020. 8
Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. In International Conference on Learning Representations, 2023. 8
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In ACM International Conference Web Search and Data Mining, 2021. 8
George Dasoulas, Kevin Scaman, and Aladin Virmaux. Lipschitz normalization for self-attention layers with application to graph neural networks. In International Conference Machine Learning, 2021. 8, 15
Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairness for graph neural networks: ranking based approach. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2021. 1, 2, 3, 6, 7, 8, 19, 20, 21, 24, 25
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations Theoretical Computer Science Conference, 2012. 2, 15, 20, 22
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In International World Wide Web Conference, 2019.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, 2019. 2, 15
Fernando Gama and Somayeh Sojoudi. Graph neural networks for distributed linear-quadratic control. In Learning for Dynamics and Control, pp. 111-124. PMLR, 2021. 15
Fernando Gama and Somaych Sojoudi. Distributed lincar-quadratic control with graph neural networks. Signal Processing, 2022.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference Neural Networks, 2005. 1
10

---

Published as a conference paper at ICLR 2024
Zhichun Guo, Chunhui Zhang. Yujie Fan, Yijun Tian, Chuxu Zhang, and Nitesh V. Chawla. Boosting graph neural networks via adaptive knowledge distillation. In AAAI Conference on Artificial Intelligence, 2023. 16
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Chao Huang, Jiahui Chen, Lianghao Xia, Yong Xu, Peng Dai, Yanqing Chen, Liefeng Bo. Jiashu Zhao, and Jimmy Xiangji Huang. Graph-enhanced multi-task learning of multi-level transition dynamics for gession-based recommendation. In AAAI Conference on Artificial Intelligence, 2021 a.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering. 2022.
Xiao Huang, Jundong Li, and Xia Hu. Label informed attributed network embedding. In ACM International Conference on Web Search and Data Mining, 2017. 6
Yujia Huang. Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar. Training certifiably robust neural networks with efficient local lipschitz bounds. In Advances in Neural Information Processing Systems, 2021b. 2, 15
Kalervo Järvelin and Jaana Kekäläinen, Cumulated gain-based evaluation of techniques. ACM Transactions on Information Systems, 2002. 6
Yaning Jia, Dongmian Zou, Hongfei Wang, and Hai Jin. Enhancing node-level adversarial defenses by lipschitz regularization of graph neural networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023. 23
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. In Advances in Neural Information Processing Systems, 2020. 2, 15
Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. Inform: Individual fairness on graph mining. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020. 1, 2, 6, 7, 8, 20, 21
Hyunjik Kim, George Papamakarios, and Andriy Mnih. The Lipschitz constant of self-attention. In International Conference on Machine Learning, 2021. 8, 15
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International
Conference on Learning Representations, 2015. 6
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian
Deep Learning, 2016. 6,8
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. 1, 6, 7, 8, 21
Precthi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. Operationalizing individual fairness with pairwise fair representations. In VLDB Endowment, 2019. 1, 6, 7, 21
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Representations, 2020. 2, 15
Jure Leskovec and Julian Mcauley. Learning discover social circles in ego networks. In Advances in Neural Information Processing Systems, 2012. 6
Jiazheng Li, Chunhui Zhang, and Chuxu Zhang. Heterogencous temporal graph neural network explainer. In ACM International Conference Information and Knowledge Management, 2023. 16
Junying Li, Deng Cai, and Xiaofei He, Learning graph-level representationn for drug discovery. arXiv preprint 1709 2017.
11

---

Published as a conference paper at ICLR 2024
Peizhao Li, Yifei Wang. Han Zhao, Pengyu Hong. and Hongfu Liu. On dyadic faimess: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations. 2021. 2
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference on Learning Representations, 2016.
Peiyuan Liao, Han Zhao, Keyulu Xu, Tommi Jaakkola, Geoffrey J Gordon, Stefanie Jegelka, and Ruslan Salakhutdinov. Information obfuscation of graph neural networks. International Conference on Machine Learning, 2021. 2,8
Zheyuan Liu, Chunhui Zhang, Yijun Tian, Erchi Zhang, Chao Huang, Yanfang Ye, and Chuxu Zhang. Fair graph representation learning via diverse mixture-of-experts. In The ACM Web Conference, 2023. 1, 16
Zheyuan Liu, Guangyao Dou, Yijun Tian, Chunhui Zhang, Eli Chien, and Ziwei Zhu. Breaking the trilemma of privacy, utility, and efficiency via controllable machine unlearning. In The ACM Web Conference, 2024. 16
Felix Mujkanovic, Simon Geisler, Stephan Günnemann, and Aleksandar Bojehevski. Are defenses for graph neural networks robust? In Advances in Neural Information Processing Systems, 2022. 1
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In International Conference on Machine Learning, 2010.
Zhongyu Ouyang, Shifu Hou, Shang Ma, Chaoran Chen, Chunhui Zhang, Toby Li, Xusheng Xiao, Chuxu Zhang, and Yanfang Ye. Prompt learning unlocked for app promotion in the wild. In NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023. 16
Zhongyu Ouyang, Chunhui Zhang, Shifu Hou, Chuxu Zhang, and Yanfang Ye. How to improve representation alignment and uniformity in graph-based collaborative filtering? In International AAAI Conference on Web and Social Media, 2024.
John Joseph Palowitch and Bryan Perozzi. Debiasing graph embeddings with methdataa training. In Advances in Social Network Analysis and Mining, 2020.
Yiyue Qian, Chunhui Zhang, Yiming Zhang, Qianlong Wen, Yanfang Ye, and Chuxu Zhang. Co- modality graph contrastive learning for imbalanced node classification. In Advances in Neural Information Processing Systems, 2022. 16
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. In International Joint Conference on Artificial Intelligence, 2019.
Mariia Rizun. Knowledge graph application in education: a literature review. Acta Universitatis Lodziensis. Folia Oeconomica, 2019.
F. Scarselli, S. L. Yong, M. Gori, M. Hagenbuchner, A. C. Tsoi, and M. Maggini. Graph neural networks for ranking web pages. In International Conference on Web Intelligence, 2005. 1
Walid Shalaby, BahaaEddin AlAila, Mohammed Korayem, Layla Pournajaf, Khalifeh AlJadda, Shannon Quinn, and Wlodek Zadrozny. Help me find job: A graph-based approach for job recommendation at scale. In JEEE International Conference on Big Data, 2017.
Oleksandr Shchur. Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Relational Representation Learning Workshop, NeurIPS. 2018. 6
Zhouxing Shi, Yihan Wang, Huan Zhang. J Zico Kolter, and Cho-Jui Hsieh. Efficiently computing local lipschitz constants of neural networks via bound propagation. In Advances in Neural Information Processing Systems, 2022. 2, 15, 20, 21, 22, 23
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014. 15
12

---

Published as a conference paper at ICLR 2024
Ichigaku Takigawa and Hiroshi Mamitsuka. Graph mining: procedure, application drug discovery and recent advances. Drug Discovery Today, 2013.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008.
Lei Tang and Huan Liu. Relational learning via latent social dimensions. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009. 6
Matthieu Terris, Audrey Repetti, San-Christoppe Pesquet, and Yves Wiaux. Building firmly nonex- pansive convolutional neural networks. In IEEE International Conference Acoustics, Speech and Signal Processing, 2020. 8, 15
Yijun Tian, Kaiwen Dong, Chunhui Zhang, Chuxu Zhang, and Nitesh V. Chawla. Heterogeneous graph masked autoencoders. In AAAI Conference on Artificial Intelligence, 2023a. 1
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh Chawla. Learning MLPs on graphs: A unified view of effectivenesss, robustness, and efficiency. In International Conference on Learning Representations, 2023b. 16
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances in Neural Information Processing Systems, 2018. 2, 3, 15
Soroush Vosoughi, Prashanth Vijayaraghavan, and Deb Roy. Tweet2vec: Learning tweet embeddings using character-level enn-lstm mncoder-decode. In Proceedings of the International ACM SIGIR Conference Research and Development in Information Retrieval, 2016. 1
Soroush Vosoughi, Mostafa 'Neo' Mohsenvand, and Deb Roy. Rumor gauge: Predicting the veracity of rumors on twitter. ACM Transactions on Knowledge Discovery from Data, 2017.
Soroush Vosoughi, Deb Roy, and Sinan Aral. The spread of true and false news online. Science, 2018.
Ruijie Wang, Yuchen Yan, Jialu Wang, Yuting Jia, Ye Zhang, Weinan Zhang, and Xinbing Wang. Acekg: A large-scale knowledge graph for academic data mining. In ACM International Conference on Information and Knowledge Management, 2018.
Qianlong Wen, Zhongyu Ouyang, Chunhui Zhang, Yiyue Qian, Yanfang Ye, and Chuxu Zhang. Graph contrastive learning with cross-view reconstruction. In NeurlPS 2022 Workshop: New Frontiers in Graph Learning, 2022a. 16
Qianlong Wen, Zhongyu Ouyang, Jianfei Zhang, Yiyue Qian, Yanfang Ye, and Chuxu Zhang Disentangled dynamic heterogeneous graph learning for opioid overdose prediction. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022b. 16
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In International Conference on Machine Learning, 2019, 6, 7, 21
Jiele Wu, Chunhui Zhang, Zheyuan Liu, Erchi Zhang, Steven Wilson, and Chuxu Zhang. Graphbert: Bridging graph and text for malicious behavior detection on social media. In IEEE International Conference on Data Mining, 2022. 16
Le Wu, Lei Chen, Pengyang Shao, Richang Hong. Xiting Wang, and Meng Wang. Learning fair representations for recommendation: A graph-based based perspective. In International World Wide Web Conference, 2021. 8
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference Learning Representations, 2019. 1
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems, 2019. 8
13

---

Published as a conference paper at ICLR 2024
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International Conference on Machine Learning, 2021. 8
Xiangchi Yuan, Chunhui Zhang, Yijun Tian, Yanfang Ye, and Chuxu Zhang. Mitigating severe robustness degradation on graphs. In International Conference on Learning Representations, 2024.
Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi- supervised graph classification. In Advances in Neural Information Processing Systems, 2022.
2
Chunhui Zhang, Chao Huang, Youhuan Li, Xiangliang Zhang, Yanfang Ye, and Chuxu Zhang. Look twice as much as you say: Scene graph contrastive learning for self-supervised image caption generation. In ACM International Conference on Information & Knowledge Management, 2022.
Chunhui Zhang, Chao Huang, Yijun Tian, Qianlong Wen, Zhongyu Ouyang, Youhuan Li, Yanfang Ye, and Chuxu Zhang. When sparsity meets contrastive models: Less graph data can bring better class-balanced representations. In International Conference on Machine Learning, 2023a.
Chunhui Zhang, Hongfu Liu, Jundong Li, Yanfang Ye, and Chuxu Zhang. Mind the gap: Mitigating the distribution gap in graph few-shot learning. Transactions on Machine Learning Research, 2023b.
Chunhui Zhang, Yijun Tian, Mingxuan Ju, Zheyuan Liu, Yanfang Ye, Nitesh Chawla, and Chuxu Zhang. Chasing all-round graph representation robustness: Model, training, and optimization, In International Conference on Learning Representations, 2023c.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, 2018.
Dongmian Zou, Radu Balan, and Maneesh Singh. On lipschitz bounds general convolutional neural networks. IEEE Transactions on Information Theory, 2019. 8, 15
14

---

Published as a conference paper at ICLR 2024
A DETAILED RELATED WORK
In the field of Lipschitz Bounds in Neural Networks, the stability of neural networks in relation to Lipschitz bounds was initially spotlighted by Szegedy et al. (2014), which postulated that larger Lipschitz bounds could cause network instability. An insightful proposition was the use of the product of the spectral norms across layers to upper bound the Lipschitz bound. Following this foundation, a slew of research (Virmaux & Scaman, 2018; Fazlyab et al., 2019; Jordan & Dimakis, 2020; Latorre et al., 2020; Huang et al., 2021b) fine-tuned the estimation of Lipschitz bounds, ushering in optimized frameworks for tighter bounds. Delving into particular network architectures, studies have explored the Lipschitz properties of convolutional layers and attention mechanisms (Zou et al., 2019; Terris et al., 2020; Araujo al., 2021; Kim et al., 2021).
For Lipschitz Bounds in GNNs, the exploration of Lipschitz bounds took specific turns. Dasoulas al. (2021) pioncered normalization technique rooted in Lipschitz bounds for self-attention layers in Graph Attention Networks (GAT). This innovative method proved instrumental in training deeper GAT models by curbing gradient explosion issues. On another front, Gama & Sojoudi (2021) paved a new path by estimating the Lipschitz bound of filters through the infinite norm of matrices, with each matrix element epitomizing the Lipschitz bound for a respective position filter.
About Lipschitz, Fairness, and GNNs, A significant stride in the context of Lipschitz bounds and fairness was the introduction of linear bound propagation method (Shi et al., 2022). This methodology adeptly estimates Lipschitz bounds across different network sections. However, it's imperative to underscore its primary design catering to Euclidean datasets, making its direct applica- tion to non-Euclidean graph data and specific fairness issues challenge. Notably, a linkage between fairness and stability in GNNs was etched by Agarwal et al. (2021), which presented an innovative framework enabling GNNs to learn fair and stable graph representations. However, it primarily focuses on attribute group fairness, emphasizing fairness for explicitly labeled sensitive attributes. This fundamentally differs from our focus individual fairess and no requirements on explicitly labeled sensitive attributes (e.g., gender, race), making direct comparisons infeasible. Dwork et al. (2012) conducted an in-depth investigation into the realm of fairness within classification, presenting a comprehensive framework that encompassed a task-specific metric as well as an algorithm used to optimize utility while retaining fairness constraints. However, it centered on conventional statistical learning models, and did not extend to deep models or graph models.
Our Distinction in Context: (i) while the aforementioned studies about Lipschitz, we address the notable gap in integrating Lipschitz bounds within GNN training, particularly focusing on individual fairness on graph structures; (ii) furthermore, our emphasis on, facilitating the efficient calculation of Lipschitz bounds for practical training feasibility by deriving the Jacobian matrix of the model for practical training and the interpretability aspects, sets our method apart.
A.1 COMPARISON BETWEEN INDIVIDUAL FAIRNESS AND GROUP FAIRNESS
The concepts of individual and group fairness are fundamental in the domain of machine learning ethics, particularly when designing and evaluating algorithms for fair decision-makinn Both concepts aim to address fairness concerns, but they do so from different perspectives and with distinct implications. While group fairness relies on annotated sensitive attributes, individual fairness does not. The distinction between individual and group fairness in terms of reliance on annotated attributes highlights fundamental difference in how these fairness paradigms conceptualize and address fairness.
Individual Fairness This concept is centered around the notion of treating similar individuals similarly. In a machine learning context, it implies that if two individuals are similar with respect to the attributes relevant to decision-making makiin process (e.g., loan approval, job recruitment), they should be treated in a comparable manner by the algorithm. Operationalizing individual fairness often involves defining a suitable metric of similarity between individuals, which can be challenging. This metric should capture all the relevant aspects that justify similar treatment. One of the main challenges is the subjective nature of defining similarity. What constitutes "similar" in one context or for one set of stakcholders might not be agreed upon universally. There's also a computational challenge in ensuring this kind of fairness at scale, as it may require pairwise comparisons among individuals.
15

---

Published as a conference paper at ICLR 2024
Individual fairness has (1) No Need for Annotated Attributes: Individual fairness typically does not rely on explicitly annotated attributes, especially sensitive attributes like race, gender, or age. Instead, it focuses the idea of treating similar individuals similarly, where similarity is often defined in the context of the specific task or decision process. Instead, it relies on (2) Implicit Attributes: The concept of similarity in individual faimess is based on implicit attributes derived from the context or the nature of the task. These attributes are usually not explicitly labeled but are inferred from the data or the specific decision-making scenario.
Group Fairness This approach focuses on ensuring fairness across predefined groups, typically defined by explicit sensitive attributes like race, gender, or age. Group faimess is concerned with statistical measures and often aims for equal treatment or outcomes across these groups. Common criteria include demographic parity, equal opportunity, and equalized odds. Group fairness is easier to quantify and implement than individual fairness as it relies on statistical measures (e.g., ensuring that selection rates for job are equal across different gender groups). Group faimess is often applied in large-scale decision decision-making scenarios where societal or policy-level fairness concerns are paramount, such in credit scoring or hiring processes. A significant challenge with group fairness is the risk of oversimplification. By focusing on broad groups, it might overlook nuances and individual-leve disparities within these groups. Additionally, it can sometimes lead to unfair outcomes for individuals when trying to balance statistics at the group level.
Group fairesss (1) Relies on Annotated Attributes: Group faimess explicitly relies on annotated attributes, often focusing on sensitive or protected attributes. These are explicit labels in the dataset, such as race, gender. or other demographic information. It uses (2) Explicit Categories: fairness, individuals are categorized based on these explicit attributes, and fairness is measured by evaluating the outcomes or treatments across these predefined groups. This approach simplifies the fairness problem by reducing it to series of statistical measures (like demographic parity, equal opportunity, etc.) across these groups. While this simplification aids in quantification and implementation, it may overlook individual-level disparities and nuanced differences within groups.
group
A.2 GNN AND FAIRNESS A SIMPLIFIED, EASY-TO-UNDERSTAND OVERVIEW
Graph Neural Networks (GNNs) GNNs are designed process graph relational data. Unlike conventional data structures, graphs consist of nodes and edges, which represent entities and their relationships. GNNs excel in capturing complex patterns in such data by aggregating information from neighboring nodes, making them useful for tasks like classification, prediction, and clustering. popularly used on diverse real-world applications, such as social media modeling (Wu et al., 2022; Qian et al., 2022; Tian et al., 2023b; Guo et al., 2023; Li et al., 2023; Wen et al., 2022a), from which the platform also derives societal concerns such as public safety, fairness, and privacy (Wen et al., 2022b; Liu et al., 2023; Ouyang et al., 2023; Liu et al., 2024).
Ranking-basee based Individual Fairness The concept of individual fairness in the context of ranking is centered around the principle that individuals who are similar, based on defined attributes, should be accorded comparable rankings. This principle is particularly pertinent in the domain of GNNs, where the objective often involves ranking nodes - such as users, items, or entities - based on a blend of their intrinsic features and the nature of their interconnections within the graph.
In this approach, the focus is on the relative positioning of individuals or nodes within the ranking order. The key is not the absolute scores or ratings assigned to each individual, but rather ensuring that the rank order is fair and equitable. This means that if two nodes are deemed similar in terms of their attributes or their roles within the network, this similarity should be reflected in how they are ranked. Whether it's i' in generating search results, recommendations, or categorizing items, the ranking-based fairness approach strives to preserve the integrity of this relative ordering, maintaining consistency across various representations or subsets of the data. It's about upholding fair and justifiable hierarchy that resonates with the underlying similarity and relationship patterns among the nodes in the graph.
Lipschitz Condition and Individual Fairness in our work The Lipschitz condition is mathe- matical concept that, in this context, can be used to enforce a form of individual faimesss. A function is said to be Lipschitz continuous if there exists a bound L such that for any two points x: and y, the
16

---

Published as a conference paper at ICLR 2024
difference in the function's outputs is most L times the distance between and y. In simpler terms, similar inputs lead to similar outputs with bound on how different the outputs can be.
When applied to ranking, Lipschitz condition ensure that if two nodes similar (close in the graph structure or feature space), their differences in ranking (output of the GNN) are limited. This prevents wildly different rankings for similar nodes, which contributes to individual faimesss.
B
PROOFS
B.1 NOTATIONS
We use the following notations throughout the paper. Sets are denoted by 0 and vectors by (). For N, we denote [n] (1, .n.. Scalars are denoted by regular letters, lowercase bold letters denote vectors, and uppercase bold letters denote matrices. For instance, a = (#1.-.. .T,) IR" and X = [X))) E I= For any vector E RR,, we use ||>|| to denote its norrm::
| = (-i= = For any matrix X Raxm, denote its k-th column. The (oo, -nom of X is denoted by | = maXie[m] | Given graph G G(V, E3) with ordered nodes, we denote its adjacency matrix by A such that A. 1 if {i,j} E E and As 0 otherwise. When it is clear from the context, we use X E RNxF to denote a feature matrix whose i-th row corresponds to features of the i-th node, and the j-th column represents the features across all nodes for the j-th attribute. We denote the output of the GNN as Y N where N is the number of nodes and C' is the number of output classes.
Xi,: to denote its i-th row and X to
B.2 PROOF OF LEMMA IN $ 3.1
Lemma 1. Given function R - R" with components g. for i [ni], the Lipschitz bound of g. denoted by Lip(g), bounded above by the norm of the vector of the Lipschitz bounds of its components, that is:
Lip(g) & [[(=i(g)))]=
(10)
where ||-I1 represents the norm of a vector, and [Lip(g:)] represents vector whose components are the Lipsehitz bounds of the functions gs-
Proof. We begin by observing that
(l s(y)l
[x(()) go (y)) | y
x all
(11)
1gs (x) 9: (: v) a y/
Furthermore, for each i E [n]. [9:(z) (v())
Tip(g.). Therefore, we can write
x la
(l((z) g(y))l
Lip(g) = sup
x yll
(g)(z) (1)
(12)
sup
| - yl
a /
< sup
[Lip(g))]
[[ip
this completes the proof.
In the above proof Lemma 1, we start by rewriting the norm of the difference between g()) and g(y) divided by the norm of y norm of vector containing the component-wist wise differences of (z) and (v) divided by the norm of x absolute value of (x) gi (y) divided by the norm of y is bounded by the Lipschitz bound Lip(g.). Hence, the Lipschitz bound of is bounded by the norm of the vector (Láp(g:)]l This establishes the inequality in Lemma
for each i. We then observe that for each i, the
17

---

Published as a conference paper at ICLR 2024
B.3 PROOF OF THEOREM 1 IN 3.1
Theorem 1. Let Y be the output of an L-layer GNN (represented in f()) with X as the imput. Assuming the activation function (represented in p(-)) is ReLU with Lipschitz bound of Lip(p) = 1, then the cumulative Lipschitz bound of the entire GNN, denoted as Lip(f), satisfies the following inequality:
L. Lip(f) & max II F"
|[
(13)
3
where F" represents the output dimension of the 1-th message-passingg layer, j is the index of the node (e.g., j-th), and the vector [J(h']] = [ (h']l [22( [ J.h))) denotes the i-th row of the Jacobian matrix of the 1-th layer's input and output, and [J(1'] is the vector corresponding to the j-th node in the 1-th layer h! (-).
ppp(hh) (h')ll] Notably,
The inequality in Theorem 1 constrains the cumulative Lipschitz bound of the entire GNN based on the layer outputs and Jacobian matrices. It is derived as follows:
Proof. We begin by examining the Lipschitz property of the GNN. Let Y denote the output of an L-layer GNN with input X. Assuming the commonly used ReLU activation function as the non-linear layer p(-), we have Lip(ø) = 1. First, we consider the Lipschitz bound between the hidden states of two nodes output by any message- message-passing layer h(-) in f(.). Let and 22 represent the hidden states of node features i and ø2, respectively. The Lipschitz bound between these hidden
states is given by:
21
22
|| (h(#1) h(x2))
(14)
[ 22
|211 x2
By applying the triangle inequality, we obtain:
| 22
[h(x)); h(22)) x - x2
(15)
Ø 22
Next, we consider the Lipschitz bound between individual elements the hidden states. Let (a and (x22 represent the hidden state matrices for inputs and 12, respectively. By again applying the triangle inequality, we have:
22
F" max M(x1): - h(22);
(16)
Ji x2
[x] - -
let's focus on the Lipschitz bound of the individual elements, M(=n)-W(ea) here, f(x); denotes the |
i-th column of the matrix fx). We denote (-()) as the operation of the 1-th ceessge-passsngg layer in f()), then by applying the triangle inequality and leveraging the Lipschitz property of the ReLU activation function, we have:
[l((x)).1 f(22)
< II pd [[(bb]]]lo
I.
(17)
|| T222
where æj,1 and 2y,11 denote features of j-th node's in æn and æ2, respectively, and [J(N']] represents the j-th node's the Jacobian matrix of the I-th message-passing layer. Therefore, the Lipschitz bound for the GNN can be expressed as:
Lip(f) max II FL |[(())] 1=1
(18)
In summary, we have shown that for any two input samples 2 and x2, the Lipschitz bound of the GNN, denoted as Lip(J), satisfies:
Y Y2l & Lip(S) |X, X2ll.
(19)
18

---

Published as a conference paper at ICLR 2024
where Y denotes the output of the GNN for inputs X. This inequality implies that the Lipschitz bound Lip(f) controls the magnitude of changes in the output based on input biases/perturbations.. Therefore, have established the following result:
I. Y - Y2ll < II F"
||x X21l
(20)
This inequality demonstrates that the Lipschitz bound of the GNN, Lip(.). controls the magnitude of the difference in the output Y based on the difference in the input X. It allows us analyze the stability of the model's output with respect to input perturbations.
B.4 THE LOCALITY IN LIPSCHITZ COMPUTATION
For local Lipschitz bound computation on graph data, we clarify that the Jacobian matrix is a 2D tensor, and we don't 't consider the case of Equation (7) where i + j:
If aYn where + j. then the computed Lipschitz bound will be local Lipschitz bound Xx.,
(as in our paper with OX.1 but rather global Lipschitz bound, which considers the Lipschitz relationships for all nodes. However, as discussed in $3 of Dong et al. (2021): solving for the global Lipschitz bounds of 2-layer MLP an NP-Hard problem. Therefore, even considering this facet for simple models (like GCN and SGC) would lead to significant increase in running time, rendering the computation of Lipschitz bounds impractical.
However, we contend that global Lipschitz bounds do not align with graph individual fairness (we enable similar individuals in the input space to maintain their similarity in the output space, ensuring individual fairness. is achieved by that: we constrain the expansion of data in the input space to the output space, thereby minimizing the impact of variations in input data on the output space, which is shaped as a Lipschitz constraint problem): First, if * j. the equations are considering the Lipschitz bound for the entire relational network. In this case, the Lipschitz bound takes into account each pair of nodes within the network (i.e., each single one node must consider its interactions with all other nodes). This doesn't consider minor perturbations; rather, the perturbation can be understood as the difference between different nodes. For example, the dimension of each node takes into account the impact of all other nodes (again, in this scenario, the complexity is extremely high because the dimension of each node needs to account for all dimensions of all other nodes, leading to an astonishing amount of computation). Under these circumstances, it is the global Lipschitz. bound, which doesn't 't consider the locality of our GCN's local message passing (unlike our local Lipschitz bound) on graph data; Second, in Dong et al. (2021), the ranking- based individual fairness computes similarity based on the nearest k neighbors, which is a local similarity measure and more aligned with our local Lipschitz.
this context, when = j. the local Lipschitz bounds are more aligned with the objective, as there is no need to maintain pairwise similarity between all nodes in the output space: node is solely influenced by its neighboring nodes. When nodes are similar, meaning they have a high degree of similarity, the difference in features between two nodes can be approximated by a small perturbation. We only need to consider how this perturbation affects the output, which can be quantified using gradients. If the gradient is steep, even small perturbation can lead to significant impact.
Moreover, the Jacobian matrix serves suitable measure for the Lipschitz bounds on each node and dimension, and frameworks like PyTorch provide mechanisms to expedite its computation. This approach reduces algorithmic complexity, making it more adaptable, while also aligning with the principles of individual fairness.
B.5 How LIPSCHITZ BOUNDS CAN GUARANTEE RANKING-BASEE INDIVIDUAL FAIRNESS?
In the context of individual faimnsss on graphs, the relationship between ranking- based individual fairness and Lipschitz continuity is established through Lipschitz constraints the GNN model. The Lipschitz continuity ensures that the model's 's predictions are not overly sensitive to small changes in node embeddings. Let's define the two concepts and their relationship mathematically:
19

---

Published as a conference paper at ICLR 2024
Lipschitz Property In the GNN model f R., Lipschitz continuity constrains the change in model output concerning small changes/biases in input (node embeddings). A function f is Lipschitz continuous if there exists bound K such that:
[I((=) f(2))) S K| - =اار,
(21)
for any two input points 2 and 2j. Here, bound.
denotes a norm (c.g., L2 norm), and K is the Lipschitz
Ranking- Cansed based Individual Fairness Based prior work (Dong et al., 2021; Kang et al., 2020),
this concept in GNNs focuses on maintaining the rank-ordering of pairwise node similarities pre and post-training. This is achieved by a ranking loss function L(-) that penalizes discrepancies between predicted pairwise distances and original similarities as:
Ranking Loss: Lrank
Σ (u:.9))P
())
(22)
where P the set of all node pairs, and L(-) measures the discrepancy between predicted pairwise distance (z 2z) and original similarity S(v,, uy).
The Exact Relationship By imposing Lipschitz constraint on the GNN, the model's 's output be- comes less sensitive minor variations (i.e.. minor biases ) node embeddings, thereby reinforcing ranking-based individual fairness. The mathematical connection can be expressed as:
RankLoss (1 uz), D(z;, zz)) x L(f(z), f(z)),
(23)
where RankLoss(S 1j), (2, 2))) is the ranking loss function, measuring the discrepancy be- tween predicted pairwise distances (22, 2z) and original similarities S(1,, U2) in the output space.
Enforcing a Lipsehitz constraint on the GNN's model parameters or architecture inherently promotes the preservation of the rank- orderind of node similarities during training. This approach drives the GNN to uphold individual fairness by ensuring that nodes with similar attributes receive comparable rankings the output space, resulting in fair and unbiased predictions for each node.
In summary, the principle of Lipschitz continuity in GNNs is directly related to the concept of ranking- based individual fairness. It achieves this by moderating the model's response to small variations in the embeddings of nodes.
C ADDITIONAL EXPERIMENTS
C.1 NODE CLASSIFICATION TASK: EVALUATED UNDER ACCURACY AND ERROR
According to Table 3, on node classification tasks, JacoLip consistently shows a competitive or im- proved trade-off between accuracy and error compared the baselines, highlighting the effectiveness of the Lipschitz bound in promoting individual fairness on graphs.
C.2 CONTRASTING WITH LIPSCHITZ METHODS TAILORED FOR OTHER DOMAINS
Although there are dozens of Lipschitz methods of fundamental statistical models (Dwork al., 2012) deep models Shi et al. (2022); Agarwal et al. (2021), it is essential to acknowledge their distinctiveness, making comparisons less straightforward.
C.2.1 CONSIDERATION ON LIPSCHITZ METHODS FOR CNN/MLP
When contrasting our approach with previous Lipschitz regularization studies for general CNN/MPP, use Shi et al. (2022) as example, and highlight the following points:
First, the approach in Shi et al. (2022) does not directly use existing Jacobian matrices. introduces concept called Clarke Jacobian, leading to explicit expressions of the bounds. This method requires utilizing the neural network's 's forward pass, necessitating computations of input and output at each step of the network, making the process complex. It primarily focuses computing the Lipschitz
20

---

Published as a conference paper at ICLR 2024
Table 3: Evaluation on node classification tasks: comparing under accuracy and error.
Feature Similarity
Structural Similarity
Data
Model
Fair Alg.
utility: Acc.f
Faimess: Err. 101
utility: Acc.1
fairness: Erc, 6 101
Vanilla pcen wennng 2017)
72.49.10.6
75.70.10.6
72.49-0.6
37.551004
InFoRM (Karge 2000
67.
1.0. (.0( (6.68%%
T3. 13.19900.5c ((-9.99%)
65.9140.21
-9.07%)
19.9620.6| (66885))
PFR (tabatie 2019
08..48=0.66---
(3.5%)
76 18: (0.7
70:22+0.74
-33.33%)
36.54+0.45
GCN
Redress (thee it m.81)
73.46 0.24---0.2 1.34%)
82,27+0.11 8.66%)
71887-0.4(
00.6%%
43.74+0.00
16.5%)
JacuLiip (on Vanilla)
72.80.10.2( (.00011.2((4427777 4-227%)
12.8800.1++9,488
72.3010.41
-0.26%)
30:2810::1
+461%)]
ACM
JacoLip (on Redress)
71.05:0.00 ((20044+2+0)))
62.21
71.9240.3
-0.79%)
46.13=9..3-22.855)
Vanilla (Wee 2019,
10:100
80.0620011
68. 08.10:1.0
15.95=10.3
InFoRM Karge al. 300m
67. 67
75.03
-5.56)
66.16+0.61
-3.27%)
39.
11-
PFR (rabotimaal 2019
67. 07.69+0044; 1.04%)
76.80+
4.00%%
66.89+0031
2.50%%
46.99+0.51 - 2.2267)
SGC Redress (tleeg i at., 2001)
66.5110.3) 2.76%)
0..32.0.3 +2.82%)
67.101.0.7(
1.90%)
49.0210.21 +4.76%
JacoLip (on Vanilla)
74.04:00.(++.2555)
52.78
72.91
48.6120.2 -5,55)
JacoLip (on Redress)
86:22:00.4(666555%
T1.27=0.3(
42.01=0/4++3:239)
Vanilla (keet watneg, 2017
90.59
80..1..0..1
_0.39.00.3
26.69
InFoRM (Kagg a., 3000
88. 88.37:0.9((
15%)
80.63
+0.27))
87.10 -3.85%)
29. 29.6820.6 -11.25
GCN PFR (Labetic al, 2019
87 17.62:2022 2[ 282%
76.26=
1
35.6620.77 7 54.44)
19 -
Redress (hieg
90.06+0.55
0.59%)
83.24+0.22
+-3.52%)
30.91+0.22 0.86%
32.42+
-
JucolLip (on Vanilla)
90.41.10.4 0.20%%
82.57..0.1 (.669))
89.1210.110 11 1.62%)
32 82..00
22.74%
CB
JacoLip (on Redress)
90.300:0.35
0.32%)
89.93 -0.755))
42.50
Vanilla (Were a., 2019)
47.18200.8
911 90.58:101
87, 08:
13,282112
InFoRM (Kag 30.0000
87.31+0055
19%%
(M,0=001(+00.07%)
88, 06.21=0.00
(0.886)
44.37
(10221%))
SGC
Redress (tteg 2001)
PFR (Taboti al, 2019
90.48.10.2
87.95-+0.22
+-0.54%))
(33%)
70.85+0.22
02.03:0.1( 1.60%
-1
90.39 11 +.333%
86.93+0.
00.63%
45.81 10.00 +5.85%
38 03. 10.3%%
JacoLip (on Vanilla)
901.7110.3
0..75.0 +0.19%)
90.34110
+3227%)
01.0210.31
JacoLip (on Redress)
92.22=002::5:4255
92.22:004441.811
%)
90.5420.34+3500
46.39=0.5(+7.199)
Vanilla (Kuf& Wellig, 2017)
94,81=0,2
73, 75.25.0.3
94,81=0.2
2.58+0.1
InFoRM (Karger al, 200m
88.6
-6-448
73.80 000=0.06(440 7.%%)%
94.08+0.21
0.14%%
2.45++0.1(- 6.04%)
GCN
Redress (Ubee a a., m111)
PER
93.71.10.1 -1.16%
88.79:10.2
6.35%)
0. 10%)
80.231001
+9.53%%
89.6911.00 1.0 5.40%)
93.91 4 0.95%)
3.22.1.33
1.67
22.9%)
35.3%)
JacoLip (on Vanilla)
93.71=20.2
16%)
78.61=11(477.00 36+733
91.75 30 -0.06%
2.75:20.6 80%)
phy
JacoLip (cm Redross)
93.79++0.8 8, 18 1.00%
82.00==0.34+22..05
03.96+0.30 31 -0.88%
4.0:0.1(4555435
Vanilla
2009
91.4510.22
77.48.10.
94.45-022
4.5010.1
InFoRM (Kag 2000)
92.
02.06:2022 53%)
75.13=0.4(
91 91.27 I[ -0.19%)
4.41:0.0f ( -1.33%
PTR (Labot al, 2019
37.39.11.2(-7.4777
73.42.0.2
5.24%%
89.161:0.31 55.60%)
3.41:10.2(
24.2%
SGC
Redress (Doea a 2001)
94.31=02(++0.38%)
79.57= 2/
94.5420.1(00100)
1.9820
JacoLip (on Vanilla)
91144=+0.77
78. 78:820000
94.00=0.60 -0.38%)
2.76:20.2 56%)
JacoTip Redress)
94.78-+0.1++03555)
62.21-0.2(+6.10%)
93.00+1.33 1.54%)
1.45-0..(e...0%)
bounds of the network, striving to find a tight bound. However, the paper does not provide specific application results for fairness, leaving doubts about its effectiveness in fairness-related contexts.
Second, in contrast, our method is simpler and leverages PyTorch's built-in automatic differentiation mechanism for all computations, requiring no additional computational cost. Furthermore, our approach treats the entire network model as whole, disregarding the internal computation flow of the network. It only requires the model's 's inputs and outputs, making it easy and convenient to use. Importantly, our Lipschitz method is designed to cater to the application context of individual fairness. Our goal is not solely to find a tight bound, but rather to integrate the Lipschitz bound as regularization term into the training process. By continuously constraining the Lipschitz bound during training, we ensure individual fairness. The underlying objectives of the two methods are distinct: while the approach in Shi et al. (2022) aims for tight bounds, our Lipschitz bound serves the purpose of ensuring individual fairness. In the context of fairness, achieving a tight bound is not the primary concern. Instead, our focus is on preserving fairness in the predictions, where the exact tightness of the bound is less crucial to GNN fairness training.
Third, extending our investigation to GNNs using the code provided by Shi et al. (2022), we computed local Lipschitz bounds. Our experimental results are tabulated at Table 4, revealing the utility and fairness performances of both methods. Notably, the accuracy-fairness tradeoff in Shi et al. (2022) is lower than our approach. This observation echoes the carlier speculation of application mismatch, as outlined in the preceding points. Moreover, we also infer that the graph structure's 's (adjacency matrix) influence on GNN's 's forward pass necessitates specialized treatment during Jacobian bound calculations. This realization prompts a more profound inquiry- one that should be taken into account when contemplating potential applications of Shi et al. (2022) to graph individual faimesss.
Finally, beyond the performance benefits from our fairness design's 's alignment with graph structures (as Equation (8)'s consideration graphs), our methodology also champions the efficient com-
21

---

Published as a conference paper at ICLR 2024
Table 4: Comparisons on the FB dataset with the GAE backbone.
Struct. Simi.
utilty: AUC1
faimew: NDCG@ 10?
utility: AUCT
faimess: NDCG@ 10?
(2022)
94,40
27.40 27.44
96.28 97.02
22.90
JacoLip (Ours)
97.40
30.90
putation of Lipschitz bounds for non-Euclidean models. While Dwork et al. (2012) pioneered the regularization of Lipschitz bounds for fairness, could not cater to graph data as efficiently as our research, since it proposed on traditional (relatively) simple statistical models. Similarly, although Shi et al. (2022) does compute a tight Lipschitz bound for CNN/MLP, our method emphasizes empirical sediiidual-faiiness predictions over theoretical tightness. This is evidenced by our prior experiments and this preliminary time-per-ie per-iteraation comparison with Shi et al. (2022) at Table 5;
Table 5: Time-per ver-iterttion comparisons on the FB dataset.
Practical Training Feasibility
Method
Time/Iter.
Graph Structure
Efficiency
GCN without Lipschitz
N.A.
N.A.
0.2841s
Ours
Yes
Yes
0.2972s
Shi et al. (2022)
No
No
3.2407s
C.2.2 CONSIDERATION ON LIPSCHITZ METHODS ON ATTRIBUTED GRAPHS
Furthermore, Agarwal al. (2021) established link between fairness and stability, introducing novel framework for GNNs to acquire both fair and stable graph representations. However, it pursued group fairness to enhance attribute fairness for explicitly labeled sensitive attributes, resulting in distinct definition from our emphasis on individual fairness within regular graphs with no explicitly labeled sensitive attributes. Consequently, our research and that of Agarwal al. (2021) cannot be appropriately compared in the same experimental scenarios due to fundamental differences in motivation and application contexts.
C.3 SENSITIVITY OF THE μ FOR THE LIPSCHITZ REGULARIZZTION TERM
To provide comprchensive analysis for understanding how varying hyperparameters impact the Lipschitz bound of the GNN, we experimented with different values the hyperparameter μ., which directly influences the Lipschitz bound of the model. A larger value of μ correlates with smaller Lipschitz bound, making it pivotal factor in our approach. Below are Table 6 and Table 7 illustrating the effects of varying μ on the GCN model applied to the Node Classification task on the Co-author-CS dataset. These tables present the outcomes in terms of AUC and NDCG metrics:
Table 6: Feature Similarity: GCN on Co-author- CS dataset with varying μ
/ NDCG@ 10t
0
0.1
0.01
0.001
0.0001
0.00001
0.000001
50.84
37.67
48.98
63.56
68.32
67.91
66.26
AUC1
90.59
60.18
89.96
90.96
90.20
90.23
90.18
The results from these tables clearly show that both AUC and NDCG metrics are sensitive to variations in the Lipschitz bound, which is controlled by μ. Notably, when μ relatively large, resulting in smaller Lipschitz bound, there is significant impact on both performance and fairness metrics. As μ decreases, allowing the Lipschitz bound of the model to approach that of the original model, we observe convergence of both performance and fairness metrics towards those of the original model.
This analysis highlights the delicate balance that must be maintained between fairness and perfor- mance in approach. The data reveals that the metric of fairness is more responsive to changes in μ compared to performance. Therefore, identifying an optimal Lipschitz bound that adequately meets both fairness and performance criteria becomes paramount in methodology.
22

---

Published as a conference paper at ICLR 2024
Table Structure Similarity: GCN on Co-author-CSS dataset with varying μ
0
0.1
0.01
0.001
0.0001
0.00001
0.000001
NDCG@ 101
18.29
4.11
10.66
19.62
31.82
26.82
19.42
AUCT
90.34
33,46
86.98
89.25
89.12
89.18
89.51
C.4 COMPUTATIONAL OVERHEAD
We provide detailed computational comparison using the FB dataset. This dataset comprises 4,039 nodes, 88,234 edges, and 1,406 attributes, making it representative choice for our analysis. Table below presents a comparative analysis of time and GPU memory usage for various methods applied to the FB dataset. The results from this comparison demonstrate that our proposed method incurs no additional computational overhead when contrasted with the standard training procedures. These findings offer a more concrete empirical evidence to support it.
Table 8: Time and GPU memory usage of different methods on FB dataset.
Lipechitz Tightness
Graph Structure
EMfliency
Timeltter
Memory-U luage
GCN (standand)
N.A. Resinictive Restactive Redrictive
N.A.
N.A.
0.244s
414.8 MiB
Lipschic unginally for CNNMMP Shi et al. (2022)
No
No
3.2407s
2130.1 MiB
Layered Lipschitz Computing for GNN Jin et (2025)
Yes
No
3.854s
3280,7 MiB
Our (GCN + Incol
Yos
Yes
0.2972
430.0 MIR
C.5 How JACOLIP AVOIDS MEMORY AND COMPUTE-INTENSIVY OPERATIONS?
key our approach is the mitigation of the memory and computational challenges commonly associated with computing the norms of the Jacobian matrix. We achieve this efficiency by avoiding the direct computation of the Jacobian matrix and consequently, the need for second-order derivative calculations.
Specifically, our method capitalizes on the capability to compute the norm the Jacobian matrix without the necessity to explicitly form the Jacobian itself. This approach eliminates the requirement for gradient of gradients computation. The key segment our code Listing 1:
for: 1 in range fout shape (11):
Directicnal derivative vectors are initialized as zero vectors
torch. peroh.zeros__kke (out)
v(:, 1]
Computie gradients with respect to the inputs, the model parameters gradients grad (ousputsouu,, inputs-imput, grad putputtsy,
sreate_graph-Tuue, retain_graph-Trus, enly_inputs-True) [9]
We only compute the norm of these gradients, which is Firet-order operation grad_norm woo.chnoommggaaieee............e lip_mat appand (qrad_normom
dim-1) unaqueeze (din-1)
Listing I: Python code for computing gradients and norms
This code snippet demonstrates the computation of the gradient concerning the inputs, which is first-order derivative. While we set the create_ create_grappiieeeeeeeeee graph-True parameter, which allows for higher- order derivative computations, our method only utilizes this for first-order derivative calculations. The rationale is that our Lipschitz bound approximation demands only the norms of these gradients, not the gradients of these norms. Consequently, the computational complexity of our method remains at the first-order derivative level, with only marginal increase compared to standard training procedures.
Furthermore, we implement efficient batching of gradient norm computations and do not retain the computational graph of these norms. This approach ensures that the memory footprint does not scale with the size of the Jacobian, but increases linearly with the output size. Given that the output size in relational datasets typically corresponds to a small dimension (i.c., the number of classes), the increase in memory requirement is minimal and manageable.
23

---

Published as a conference paper at ICLR 2024
Additionally, method leverages the inherent efficiencies of PyTorch's autograd system. This system dynamically allocates and deallocates memory during the training process, optimizing gradient computations and ensuring minimal memory usage by retaining only necessary gradients.
In summary, our approach computes the Lipschitz bound without incurring the significant computa- tional overhead associated with second-order derivatives. Our empirical results, supported by the provided code, affirm that our method does not result in substantial increases training time or GPU memory usage when compared with standard training procedures.
D MODEL CARD
The hyper-parameters for method across all datasets listed in Table 9. For fair comparisons, we follow the default settings of Redress (Dong et al., 2021).
Table Hyperparameters used in our experiments.
Node Classification
Link Prediction
Hyperparameters
ACM
Coauthor-CS
Coauthor-Phy
Blog
Flickr
Facebook
Hyperparameters w.r.t the GCN model
Layers
Hidden Dimension
[16,9] 9]
[16, 15]
[16, 5]
32, 16]
[32, 16)
[32, 16)
Activation
ReLU used for all datasets
Dropout
0.03
0.03
0.03
0.00
0.00
0.00
Oplimizer
AdamW with le 5 weight decay
Pretrain Steps
300
300
300
200
200
200
Training Steps
150
200
200
60
100
50
Learning Rate
0.01
0.01
0.01
0.01
0.01
0.01
Hyperparameters w.r.t the SGC model
# Layers
1
N.A.
N.A.
N.A.
Hidden Dimension
N.A.
N.A.
N.A.
N.A.
N.A.
N.A.
Dropout
N.A.
N.A.
N.A.
N.A.
N.A.
N.A.
Optimizer
AdamW with le
5 weight decay
Pretrain Steps
300
500
500
N.A.
N.A.
N.A.
Training Steps
15
40
30
N.A.
N.A.
N.A.
Learning Rate
0.01
0.01
0.01
N.A.
N.A.
N.A.
Hyperparameters w.r.t. GAE model
# Layers
N.A.
N.A.
N.A.
2
2
Hidden Dimension
N.A.
N.A.
N.A.
[32, 16]
[32, 1G N.A.
322 16
Activation
N.A.
N.A.
N.A.
N.A.
N.A.
Dropout
0.0
0.0
0.0
0.0
0.0
0.0
Optimizer
AdamW with le weight decay
Pretrain Steps
N.A.
N.A.
N.A.
200
200
200
Training Steps
N.A.
N.A.
N.A.
60
100
50
Learning Rate
N.A.
N.A.
N.A.
0.01
0.01
0.01
E DATASET DESCRIPTIONS
We provide additional details about the datasets utilized in our work, as discussed in & 4.1:
Each node corresponds to paper, and an edge between two nodes represents the citation relationship between the respective papers. The node attributes in these networks are generated using the bag-of-words model based on the abstract sections of the published papers.
Citation Networks:
Co-author Networks: It consist of nodes representing authors, where edge between two nodes
indicates that the corresponding authors have collaborated on a paper. The node attributes in these networks are constructed based on the bag-of-words model using the authors' profiles.
Social Networks: Each node represents a user, and the links between nodes represent interactions between users. The attributes associated with these nodes are derived from user profiles.
24

---

Published as a conference paper at ICLR 2024
The datasets used in work are referred to CS and Phy, which are abbreviations for the Co- author-CS CS and Co-author-Phis Phy datasets, respectively. A comprehensive overview of the datasets, including their detailed statistics, is presented in Table 10.
Table 10:
Detailed statistics of the datasets used for node classification and link prediction. We follow the default settings of Redress (Dong et al., 2021) fair comparisons.
Task
Dataset
Nodes
Edges
Features
Classes
ACM
16, 484
71,980
8, 9,337
9
node classification
Coauthor-CS
18, 333
891
805
15
Coauther-Phy
34, 493
247,962
8, 8.415
5
H1 olCata 1
5. 196
171, 743
8. 189
N.A.
link prodiction
Flickr
7,575
239, 738
12,047
N.A.
Facebook
4,039
88, 23-
406
N.A.
F RANKING-BASED INDIVIDUAL FAIRNESS IN REAL WORLDS
Ranking list from Sq
Ranking list from Sg
U
U
U
u
Us
U
U
U
U
Us
Node pairs
Node pairs
u2
U3
U
U2
U2
U
U2
u
u2
U
U2
U
U
U
U1
U
U1
11
Us
U4
U
U
U
Inconsistent node pairs
Consistent node pairs
Figure 2: An example figure motivating individual fairness in graphs: taken from Dong et al. (2021).
Motivating Example Consider job recommendation platform utilizing GNN rank candidates for employers. In this scenario. nodes symbolize individuals, while edges represent connections or similarities (such as shared skills, experience, or educational background). Figure by Dong et al. 12021) as our motivating example, showcases two distinct ranking lists for different candidate subsets, Sy and Sy. based on their profiles and network connections.
In an ideally fair system, candidates possessing comparable qualifications and experiences should receive consistent rankings across various subsets. However, our example reveals disparities (indicated by red dotted lines) that arise without the implementation of our proposed framework. These disparities manifest as inconsistent rankings for similar candidates, resulting in potential unfairness. For instance, the ranking of candidate u2 is higher than 24 in the list from Sy, but this order reverses in the list from Sy. Such inconsistency can lead to overlooking qualified candidates based on the subset they belong to, challenging the notion of individual fairness.
Our framework employs the Lipschitz condition to establish boundary, ensuring that the output differences (rankings) for any pair of similar candidates remain within the limits set by their feature- space distances. This mechanism acts as a safeguard, preserving ranking consistency across different scenarios and thereby maintaining individual fairness.
25

---

Published as a conference paper at ICLR 2024
The real- wolld significance of our approach is its capacity to generate fair and consistent outcomes in various applications where GNNs are used for critical decision makiing. This includes domains like credit scoring, social media content ranking, and personalized medicine, where inconsistent results can significantly affect individuals' opportunities and well-heing. Our objective cultivate fairness and trust in Al systems, ensuring they adhere societal and ethical standards.
Practical Value
In conclusion, our approach not only theoretically robust but also holds substantial practical merit. It provides significant benefit both individuals impacted by GNN-based decisions and the organizations implementing these models. We believe the provided motivating example effectively demonstrates the potential influence and real- world relevance of our research.
26


Reviews:
[{"review_id": "Mmrr6QN3VM", "reviewer": "Reviewer_7Erc", "summary": "This paper addresses the problem of individual fairness in the relational learning task (graph datasets). The measure of fairness in this work fairness is based on the notion that similar inputs must have similar outputs. The authors argue that to ensure fairness, Lipschitz's constant of GNN must be small. To this end, they characterize the lipschitz's constant in Jacobian and optimize it along with the loss function to achieve fairness. Empirical results show improved individual fairness at competitive or better utility.", "questions": "- In the introduction, the authors mention, \"... computational approach utilizes intermediate tensors extracted...\" What intermediate tensors are being referred to here?\n- Eq 7 describes the jacobian of the i-th node. Shouldn't it be a 3D tensor? $Y_{jk}$ (output of node-j) depends on $X_i$ (node i) due to message passing. Are $\\frac{dY_{j1}}{dX_{i1}}$ $i\\neq j$ and such terms ignored? I think the discussion about the computation of the Lipschitz constant could be more elaborate, with a clear indication of the dimension of the tensors. \n\nI think the paper shows good empirical results. Still, it would help to make the section about the Lipschitz constant more straightforward and compare training time and memory usage to support computational efficiency claims.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Characterizing fairness in terms of the Lipschitz constant and optimizing this constant is an interesting approach to achieving individual fairness in GNNs. \n- The proposed approach, JacoLip, outperforms other fair learning methods --- JacoLip achieves a better fairness score while having the best or close to the best utility. Further, the authors show that it can even improve an existing fair learning method to some extent. These observations, coupled with the evaluation over several datasets, increase confidence in the proposed idea.", "weaknesses": "### Computational Efficiency\n- At several places in the paper, the authors have emphasized that their method has no computational overhead. However, no empirical evidence is provided for this. For example, comparing training time and memory usage of different approaches could be a way to support this argument. \n- The proposed approach involves computing norms of the Jacobian matrix in the loss function. This could lead to computing gradient of gradient during backpropagation (implicitly by PyTorch), which can be memory and compute-intensive. How the authors got around this is unclear.", "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": "", "extra_scores": {}}, {"review_id": "KwzjR4mkZO", "reviewer": "Reviewer_uCQA", "summary": "The paper focus on individual fairness in GNNs by constraining the output perturbations induced by input biases. The authors propose a Lipschitz constant-based approach to examine the output stability of GNNs and demonstrate its effectiveness in limiting biases in the model output. They also introduce a computational strategy using the Jacobian matrix to efficiently compute the Lipschitz constant. The paper includes experiments on real-world datasets and comparisons with existing methods.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses an important and timely problem of fairness in GNNs, which has gained significant attention in recent years.\n\n2. The use of Lipschitz constants to control the stability of GNN outputs provides a provable method for examining output stability without additional computational costs.\n\n3. The theoretical analysis and formulation of the Lipschitz constant for GNNs operating on graph data is well-structured.", "weaknesses": "1. The proposed method does not need manual annotation of sensitive attributes. However, lack of information would surely compromise the guarantee of ensuring fairness. Discussions on the drawback compared to other fairness methods that explicitly use sensitive attributes should be included.\n\n2. The methodology in sec 3 does not appear to be specifically tailored for fairness problems. Is there any guarantee on how fairness regarding sensitive attributes is ensured for the proposed JacoLip algorithm?\n\n3. The experimental results are not organized clearly. For example, in Table 1 JacoLip isn’t always achieving the best performance, but best results are not in bold or otherwise marked, making it difficult to compare across methods and datasets.", "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": "", "extra_scores": {}}, {"review_id": "TI0WL4fyb9", "reviewer": "Reviewer_ANH8", "summary": "This paper designs an approach to estimate the Lipschitz constant for GNNs efficiently. Adding such an estimation as a regularization to limit output changes induced by input biases helps align the model with principles of rank-based individual fairness. The authors validate the proposed method through experiments on node classification and link prediction tasks. Results show the approach effectively improves fairness while maintaining accuracy. In particular, this paper provides insights into how constraining the Lipschitz constant influences training dynamics and the trade-off between accuracy and fairness.", "questions": "(1) What is the motivation of the proposed approach? The practical value would be much clearer if any motivating example could be provided.\n\n(2) What is the time complexity of the proposed approach? It would be desired if any time complexity analysis / running time comparison could be provided.\n\n(3) Is the proposed framework sensitive to the value of $u$ (i.e., the weight assigned for the regularization term) in Algorithm 1?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper is generally well-organized and easy to follow. Plus, a comprehensive theoretical analysis is provided.\n\n(2) Extensive experiments are performed and presented. The superiority exhibited by the experimental results in most cases seems promising.\n\n(3) The efficient computation of the Lipschitz constant via the Jacobian matrix makes the proposed approach scalable.", "weaknesses": "(1) This paper lacks a motivating example to deliver the significance of the proposed approach in applications.\n\n(2) No time complexity / running time comparison is provided. This undermines the claimed advantage in efficiency.\n\n(3) While experiments validate the effectiveness of the proposed approach, more analysis could be provided on the sensitivity of the method to different hyperparameters.", "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": "", "extra_scores": {}}, {"review_id": "v9lFVGYPOv", "reviewer": "Reviewer_kSfC", "summary": "I’m not an expert in the GNN, fairness community but has some experience on the estimation of Lipschitz constant. \nAccordingly, my reviews are purely based on reading the paper without comparison to the related literature on GNN and fairness.\n\nIn my understanding, this paper studies the use of Lipschitz constant of graph neural networks for fairness. To derive the Lipschitz constant, the Jacobian based approach is proposed and verified by several experiments on classification and prediction tasks.", "questions": "See the above.", "limitations": "", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Estimate the Lipschitz constant of GNNs via Jacobian matrix\n- Comprehensive experiments on GNNs for the bias", "weaknesses": "Since I’m not familiar with GNN and fairness, it appears difficult to evaluate the contribution. \n\nFor the estimation of the Lipchitz constant, the approach is based on the Jacobian matrix, which is loose. In this community, there are several advanced and promising approaches for the Lipschitz constant estimation on DNNs. So I’m wondering how this can be extended to the GNN setting, and what’s the difficulty issue behind this?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)