DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
Authors: Yifan Wang
Hourun Li
Yue Ling
Zhiping Xiao
Jia Yang
Changling Zhou
Wei Ju
Ming Zhang
Xiao Luo
Venue: ICML 2025 poster (2025)
Keywords: graph fairness
graph neural networks
Primary area: general_machine_learning->representation_learning

Abstract: Graph neural networks (GNNs) have shown strong performance in graph fairness learning, which aims to ensure that predictions are unbiased with respect to sensitive attributes. However, existing approaches usually assume that training and test data share the same distribution, which rarely holds in the real world. To tackle this challenge, we propose a novel approach named Dual Unbiased Expansion with Group-acquired Alignment (DANCE) for graph fairness learning under distribution shifts. The core idea of our DANCE is to synthesize challenging yet unbiased virtual graph data in both graph and hidden spaces, simulating distribution shifts from a data-centric view. Specifically, we introduce the unbiased Mixup in the hidden space, prioritizing minor groups to address the potential imbalance of sensitive attributes. Simultaneously, we conduct fairness-aware adversarial learning in the graph space to focus on challenging samples and improve model robustness. To further bridge the domain gap, we propose a group-acquired alignment objective that prioritizes negative pair groups with identical sensitive labels. Additionally, a representation disentanglement objective is adopted to decorrelate sensitive attributes and target representations for enhanced fairness. Extensive experiments demonstrate the superior effectiveness of the proposed DANCE.

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
Yifan Wang' Hourun Li
Ling Yue
Zhiping Xiao 4# Jia Yang?
Changling Zhou
Wei Ju
Ming Zhang?* 2# Xiao Luo
Abstract
Graph neural networks (GNNs) have shown strong performance in graph faimess learning, which aims ensure that predictions are unbi- ased with respect to sensitive attributes. However, existing approaches usually assume that training and test data share the same distribution, which rarely holds the real world. To tackle this challenge, we propose a novel approach named Dual Unbiased Expansion with Group-acquired Alignment (DANCE) for graph fairness learning under distribution shifts. The core idea of our DANCE is to synthesize challenging yet unbi- ased virtual graph data both graph and hidden spaces, simulating distribution shifts from a data- centric view. Specifically, we introduce the unbi- ased Mixup in the hidden space, prioritizing mi- nor groups to address the potential imbalance of sensitive attributes. Simultaneously, we conduct fairness-awarr adversarial learning in the graph space to focus on challenging samples and im- prove model robustness. To further bridge the do- main gap, we propose group-acquires alignment objective that prioritizes negative pair groups with identical sensitive labels. Additionally, repre- sentation disentanglement objective is adopted to decorrelate sensitive attributes and target repre- sentations for enhanced fairness. Extensive exper- iments demonstrate the superior effectiveness of the proposed DANCE.
Forulo
Male
Taak relited and seesiivee informaiice
Fenule
Tran
Tel Falmess Method
Y-
Y-u
High
Y=
High
Low
Inceme
Incumm
Text
(a)
(b)
Figure f. An illustration of sensitive group imbalance (Gender and Income as sensitive attributes) and inevitably removing task-related information challenges under distribution shifts.
1. Introduction
Graph-based machine learning methods, especially Graph Neural Networks (GNNs), have been adopted as the de facto approach for prediction tasks on graph-structured data (Wu et al., 2020; Ju et al., 2024). Among these tasks, node clas- sification (Kipf & Welling, 2017) is fundamental, which endeavors predict the category of cach node within graph and has been widely applied in various applications, i.e., community detection (Ren et al., 2025), molecular prop- erty prediction (Zhuang et al., 2023) and cross-modal re- trieval (Li et al., 2024a). However, graph learning often suf- fers from fairness issues due to inherent biases in the training data, with the message-passing mechanism in GNNs further amplifying these biases (Dong et al., 2023).
Equal contribution "ccooo of Information Technology & Man- agement, University of International Business and Economics, Bei- jing, China Statte Key Laboratory for Multimedia Information Processing, School of Computer Science, PKU-Anker L.LM Lab, Peking University. Beijing, China 'Peking University, Beijing, China Paal G. Allen School of Computer Science and Engineer- ing, University of Washington, Seattle, WA. USA Department of Computer Science, University of Californi.. Los Angeles, USA. Correspondence to: Zhiping Xiao Spatxiao@uu.cdee Wei Ju <juwei@ www.edu.cn>. Ming Zhang <mzhang.cs wkw.cdu.cn..
To mitigate this issue, significant efforts have been devoted in recent years to achieving fair graph representation learn- ing. Depending on the stage at which fairness interventions are applied, these efforts are typically grouped into pre-, and post-processing strategies. Pre-processing strategies address biases prior the model training stage by modify- ing the input graph data, such by applying node feature masking (Köse & Shen, 2021; Wang et al., 2024), edge per- turbation (Li et al., 2021: Spinelli et al., 2021), mixup (Li et al., 2024c) or distribution alignment (Dong et al., 2022). In contrast, in tr-percessing strategies incorporate fairness con- straints during the training stage by modifying learning ob-
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distributioo Graph Fairness Learning
jectives, such as through regularization (Bose& & Hamilton, 2019), contrastive learning (Zhang et al., 2025) and adver- sarial training (Ling et al., 2023). Finally, post-processing strategies modify the model's output after training to miti- gate bias and enhance fairness (Dai & Wang, 2021).
graph with significant bias. Based on the expanded graph, we introduce group-acquired aligament to ensure fair node representations, which prioritizes sample pairs with identi- cal sensitive labels as negatives, In addition, we explicitly disentangle sensitive and task-related information to ensure that task-related information remains invariant across distri- bution shifts. Experimental results on multiple real-world datasets show that our DANCE achieves superior fairness and performance compared to state-of- of-thee-rt methods.
However, most existing fairness-aware learning works are built on the assumption that training and test nodes in the graph are independently and identically distributed (i.i.d.), which rarely holds in real-world scenarios. In practice,
nodes often belong to multiple environments, leading to distribution shifts caused by complex data generation pro- cesses (Bengio et al., 2019; Li et al., 2023a). Therefore, these approaches often suffer from poor performance and unstable predictions (Li et al., 2022a; Zhang et al., 2024b) when adapting to new environments (groups) (Pham al., 2023; Li et al., 2024b). To address these challenges, signifi- cant efforts have been devoted to graph out-o--distribution (OOD) generalization under distribution shifts. Recent advancements include techniques such as data augmenta- tion (Han et al., 2022: Sui et al., 2023), (causal) invariant learning (L.i et al., 2022b; Yu et al., 2023) and model archi- tecture designs ( (Yang et al., 2023).
In summary, the primary contributions of the paper are as follows: New Perspective. We study an underexplored yet practical problem of out-of-distribution graph fairness learning and propose a data-centric view to solve the prob- lem. @ Novel Methodology, Our DANCE not only gener- ales challenging but unbiased virtual graph data to simulate the distribution shift, but also introduces a group-acquired alignment to minimize the domain gap with fairness con- sidered. @ Extensive Experiments. We conduct comprehen- sive experiments on multiple real-world datasets to evaluate the framework. The results demonstrate that the proposed DANCE achieves superior performance and fairness un- der distribution shifts. The code is available https: //github. com /owoo//ooouniii..cooo DDNCEE ICCCCF__IIIM__222 2025.
Despite significant progress, we argue that achieving fair graph learning under the distribution shift remains chal- lenging due to the following two key issues: O Sensitive group imbalance arising from diverse graph distributions. Sensitive groups are often imbalanced in the graph, with the generalization process under the distribution shift in the graph being highly skewed. This imbalance forces the model to focus primarily on the majority group, which re- sults in insufficient learning of the minority group extract fair representation. @ Inevitably removing task-related in- formation across environments. Graph distribution shift often introduces unintended correlation between the target and sensitive information in practice. For example, prior studies have observed that fair income prediction model trained in one state may lose its faimess when applied to another state (Ding et al., 2021). When this correlation is entangled, it will lead to a conflict between the fairness and performance objectives of the task.
2. Preliminaries & Problem Definition
in which V- = =V11..... uN} denotes the node set containing N nodes, and & E V Vss the edge set. We use the adjacency matrix A {0, 1J to describe the connectivity and structural dependencies of nodes in the graph, where Aue if (u, v) E E, otherwise Aun = O. The node feature matrix can be represented as X E R- where row X, E Rd denote the feature vector of the node u with dimension d. The sensitive attributes of the node set are specified by the 1-th dimension of X, i.e., S = X = {.1....,8N E {0, 11A,, where sy is the sensitive attribute associated with node We consider the binary node classification task, with the node label matrix denoted as Y E {0, 1).V.
Notations. Let a graph be represented as 9 =
Definition 2.1 (Sensitive Group). The sensitive group de- notes the node set divided by the sensitive attribute:
To this end, we propose a novel approach in this paper, named Dual Unbiased Expansion with Group-agquired Alignment (DANCE), which aims to address the challenges of sensitive group imbalance and the thtrness-performaat conflict under graph distribution shifts. Specifically, since the test graph distribution is unknown, we investigate graph data expansion in both graph structural and feature space, generating OOD graph data to expand the training distribu- tion and enhance generalization. We first synthesize harder minor samples from the structural aspect to enlarge the squeezed sensitive group. Then, we focus on the feature aspect and employ an adversarial module to generate the
V3 = (v E Vls,- s}.
(1)
Definition 2.2 (EO Group). The Equality Odds (EO) group of the graph is divided by sensitive attribute s and label y:
VV = {0 E Vl(s, = =) n (y. = =
Definition 2.3 (Demographic Parity). Demographic par-
ity (Calders et al., 2009) stipulates that different demo- graphic groups should have equal positive prediction proba- bilities. Accordingly, ADP can be defined as:
Apr E (f.- 1/s = 1) (Wo =
=1 1/8, -0), (3)
2

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
Different Classes
Node/Edge
Boundary
Lts
Synthesized Node/Edge
GNN Target Encoder
Target
Aligmmen
Target
Latign
Classifier
prob
Vanc
Source Graph
Sample
L syn cls
Vanc
(0000
1
Vaux
OOOOO
Enlargor
Vanc
Ad Adversarial
Disentangle
1-6 Vaux
8 Naynt
Lais
Mixup
CCCOO
Adversarial (CCO0
aux
Sensitive Encoder
Sensitive Classifier
goal min Cair -aas
Augmented Graph
Sensitive
Figure 2. Illustration of DANCE, which contains three modules: (1) Graph Expansion for Distribution Shifts:
Generate unbiased virtual graph in both graph and hidden space. (2) Group-acquired Alignment: We introduce group alignment to prioritize negative pair groups with identical sensitive labels. (3) Representation Disentanglement: We decorrelate sensitive attributes for enhanced faimesss.
where the predicted and ground-truth labels for the node o are in and yu- The independence between predictions ÿ and sensitive qualities namely ý L.s.s is quantified by Apr.
3. Methodology
This paper studies the problem of out-of-distribution graph fairness learning and novel framework DANCE is pro- posed to solve this problem. The high-level idea of DANCE is to expand the graph data in both graph and fea- ture space, which can simulate the distribution shifts in data-centric view. On the one hand, we utilize unbiased Mixup to enhance the attribute balance in the expanded dataset. On the other hand, we adopt fairness-aware adver- sarial learning generate challenging samples for robust- ness. These generated virtual data incorporated into group-acquires alignment framework to emphasize negative pairs with identical sensitive labels for enhanced fairness. We also leverage representation disentanglement to facilitate the decorrelation of sensitive and target information. An overview of our proposed DANCE is illustrated Figure 2. More details of the framework are introduced below.
Definition 2.4 (Equalized Odds). Equal odds (Hardt et al., 2016) seeks to enforce that both the True Positive Rate (TPR) and False Positive Rate (FPR) should equal in various demographic groups And A go can be written as:
1 1
Ago 2 8=0
Σ
EuEv f0 yluu = 11
EvEv( - -,,
where the independence between the ý and conditions on the ground-truit y. namely j_sly, is quantified by Ago.
Problem Definition. We denote the generation process of a graph as P(A,X: X, Y|e) = P() x, e), where e represents the environment the whole envi- ronment set E. The structure and feature of graph is gen- erated by P(A,Xle, and node labels are determined by P(Y|A, X, e). The distribution shifts of the graph in- + (A. X.), i.e., the graph
3.1. Dual Graph Expansion for Simulating Distribution Shifts
duce that P.. (A., distributions generating the ego-graphs G, = and labels Y, for the training and test nodes are different. For example, the diverse communities that are partitioned within the graph. The objective learn powerful GNN fz(-) h" (-) that achieves both good performance and fairness over all environments for node classification task:
Unbiased Mixup for Balanced Sensitive Attributes. Since the sensitive groups of nodes in the graph are often imbal- anced, we motivated to enlarge the minor group bound- ary. Specifically, we employ the confidence (Wang et al., 2021) to calculate the node hardness in the minor sensitive group, which can be defined as:
C, = aByo Do). Or = f==ffaf (AA,,.)).
(6)
f arg min sup R(fle),
(5)
So eEE
where (Nv, Dv) = you. + (1 y1 Do), Ve and g denote the ground-truth and predicted label of node re- spectively, and we calculate 9. from the previous epoch in practice. Then, we can identify the minor anchor node Vanc from a multinomial distribution with the node hard-
where f-) is decomposed into two parts, with graph en- coder g(-) and classifier it()). And R(fle) represents the empirical risk that ensures both good performance and fair- ness for the nodes within environment
3

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
ness c E RR- as the input to calculate probability. Then, sample from another multinomial distribution to iden- tify auxiliary node Vauz based on the confidence in class yoane, i.e. = 1 - Ofeeane De). We aim to enlarge the boundary of the minor sensitive group while avoiding de- generating the other groups in the graph. Thus, we employ a simple Mixup (Zhang et al., 2018) strategy to generate the synthesized node feature, which can be defined as:
contribute to poor fairness performance. By leveraging adversarial training (Volpi al., 2018; Liao al., 2021), the feature generator is optimized to simultaneously maximize both the faimess loss and the classification loss:
max CCats Jfiir - A||X' - -xpli))
1
1
Ljuir
E BuE (Bu = (op((e))AA))
(II)
2
y=0
X syn 8aane ane + (1 6) X auz:
(7)
Buevy (bu = vl
where ô is the trade-off parameter, and as ô decreases, the generated synthesized node features become more simi- lar to the auxiliary node, thereby expanding the boundary of the minor sensitive group. Note that edges dominate the messagee-passing procedures during GNN propagation. Here, we aim for additional synthesized edges for message passing beyond the minority group boundary while blocking propagation to the other groups, preserving the degenera- tion of the sensitive groups. Instead of connecting Usyn to both Sane and Jauz. we only connect with meaningful neighborhoods in Janc- Specifically, we define the graph diffusion (Gasteiger et al., 2019) process on the graph:
where V denote the EO groups in graph g'. Note that we additionally incorporate regularization term to guarantee that the generated features do not deviate significantly from those of the training graph.
3.2. Group-acquired Alignment for Graph Heterogeneity Reduction
To ensure the model generates consistent and fair repre- sentation under graphs with significant biases, we disentan- gle the node similarities into fine-grained types for demo- graphic group alignment, explicitly penalizing the model that learns unwanted information. Specifically, we treat the input and generated graphs as two views and encode them obtain the node representations, i.e., Z Nxd' (* {1, 2), with dimension d'. We adopt different types of similarities between the anchor node v and other nodes in the graph to construct the sample set, which can help us distinguish positive (negative) pairs with different re- lationships of sensitive labels (Park et al., 2022; Zhang et al., 2024a). There are four groups with the following definition. 1 Intra-Group (IG): The similarity is defined within the EO group, and the node set can be defined as (v) (Zig E Z*| tive Inter-Group (SG): The similarity is defined between an anchor and nodes from the same target class but with different sensitive attributes, and the node set can be written as Zig = {Eeg E Z |aag # Sy n yay = yr @ Target Inter- Inter-Group Group (TG): We focus on the similarity between an anchor and nodes from the same sensitive attribute, which are labeled with different target classes, and the node set can be defined as Z (v) {z E Z" |$tg = 8, O Utg # yo e Target & Sensitive Inter-Group (TSG): The similarity is defined between an anchor and nodes that differ in both sen- sitive attributes and target classes. The node set is defined as Zisg (v) { (Ztag E Z" |Stag + Sy O yeag # yo
Sanc- Σ 1=
0,Tr anc Tano- Aane D anc!
(8)
where 0, = a(1 - a)" for Personalized PageRank (PPR) and 0, = e e- G. for Heat Kernel (HK) examples. Dane denote the degree matrix of ego- ego-graph. We can utilize the sparse output of Sanc to form multinomial distribution for sampling neighbors of Usgn, with the number of neighbors determined based on the entire graph to preserve the degree statistics (Li et al., 2023b). The synthesized edges and labels of the synthesized node can be defined as:
Sy n 3kg = yo
Sensi-
Nayn ~ P pdiff Thop (Vone); Ysym = yanes
where pdkff (Vanc) is the I-hop neighbors distribution. Note that we generate the synthesized node in the graph w.r.t. ratio r, namely, we add the synthesized minor nodes from Nmi to (1 --7))= * Nmmn + N Nman, where Nmin and Nmax denote the number of nodes in two sensitive groups
Adversarial Learning for Challenging Graph Data. To further expand the graph in the feature space, we consider the worst-case shift near the training graph data. Given the synthesized graph G' (A', X'), we feed it into f(-) to get the predicted label i/.- The classification loss can be:
Based on this, encourage the similarity in IG and SG are larger than TG and TSG between two views for alignment:
C =
Σ BCE Ka)),
VEVA-
(10)
Latign
Σ
7
Σ
Σ
7
1
(w)
Vy.8
2.
Vs
p.a
where BCE(.) denotes the binary cross-entropy loss. At regular intervals during training, we utilize an MLP-based
(12)
Σ
log
generator pp(+): : X' - Xx to identify node features that
E E (v)
Σ
kig E Zi,(1)
0ig
4

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
where Z ( Z -,,,,,,,,,,, (v) = (2p E T (b) 2g (t)]sp s). and Gigy exp(2, (2y- 2tg/T). Note that since the number of anchors and positive samples is im- balanced across sensitive groups, we follow prior work (Park et al., 2022) and apply group-wise normalization to mitigate the unfairness caused by these disparities.
To begin, we introduce the following notations. Let Va and V- = V V3 be the set of minority and non-minority group nodes, respectively. The adjacency matrix of the graph with synthetic edges is Aanc. and the corresponding degree matrix is Danc, where Dane, ΣE Aanc,ij. Let H E glVlxd be the representation matrix of all nodes in the 1-th layer, where Z = H (H()) denotes the concatenated representation output from all L layers. The information propagation rule is:
3.3. Representation Disentanglement for Enhanced Fairness
To further prevent the conflict between fairness and perfor- mance during graph distribution shifts, we employ another GNN extract node representation Z of the augmented graph and cast it as the additional sensitive-aware negative view. Toward this end, we use sensitive discriminator 5(-) : Z - S and the classification loss can be:
H Σ
(T T
0
W + B()) )(). (17)
where o denotes the activation function. W and B refers the learnable weight and bias matrix for the I-th layer. Let be the model parameter, which can represent either the classifier parameter 0 or the generator parameter tb Define the loss function such that when w = 0,
Cass
Σ (CE(ss.E(2,) VEV...
(13)
Based on the negative view, we utilize a node representa- tion disentanglement loss to explicitly decorrelate sensitive information (Park& Byun, 2024), defined as follows:
F(w) = Li(0) = Lets + Lits + Lals + 3( + &Ldis) (18)
When w 1/.
Lais Σ
Σ
F(w) C2( -Lyn Lsair A|| -X (19)
Z
Z sg.5
(v)
Vy.a
E,EZ,
(14) Theorem 3.1. Given the above notations, for any i V..
Σ
log
Öp
there exists j E V-, such that
Σ 2.g (v)( Vig
2, 2 (. (v)
Σ 0 OT H
# 0;
(20)
where Z (b) Zig/T). Here, we encourage the augmented graph and its negative view to contain distinct information by reducing the similarity within the IG group between Z and Z
(zp (u) Z (u)lsp s and Gig = exp(z.
anc
For any i V-s, for all j V.. have
0 (T anc (Tan
= 0.
(21)
3.4. Overall Optimization
We also train the GNN model f() on the input graph to ensure the node classification accuracy, defined as:
Theorem 3.1 indicates that the graph diffusion method can precisely control the information propagation between dif- ferent groups, which is crucial for improving the fairness and performance of the model when dealing with data from different groups.
Lets
Σ vEVAr
BCE(y,, 0,)),
(15)
where to is the predicted label. The overall optimizing process of DANCE can be formulated as:
Theorem 3.2. Suppose that the loss function Flw) is dif- ferentiable with respect to the parameter w, and there ex- ists a constant M > such that the gradient of the loss function is M M-Lischhitz continuous. We adopt the SGD algorithm to update the parameter. When appropriate learning rate a is chosen such that 0 < < M. we have lim F(w:))ll = O and lime- F(ur) exists, which means the loss function F(w) converges.
ming Loss + Led. L + B(Calign Ladis); ming - -Lag - Ljair + X||X' 2p
(16)
where À denotes the weight of the regularization term.
3.5. Theoretical Analysis
Here, we prove that the graph diffusion process we put forward can precisely control the information propagation between different groups Additionally, the convergence proof of the loss function is shown.
The Lipschitz continuity assumption limits the rate of change of the gradient of the loss function, which is a com- mon condition for the convergence proof of existing opti- mization algorithms (Meng et al., 2024).
5

---

DANCE:
Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distributioo Graph Fairness Learning
Table 1. Classification and faimess metries (%to) on Credit-Cs. f indicates that higher values are better, while & indicating the opposite. We highlight the best results in bold.
Dataset
Metric
MLP
GCN
FairVNNN
NIFTY
EDITS
EERM
CAF
SAGM
RFR
FatraGNN
DANCE
ACC1
55.6
76.69:12.48
77.4540.11
77.51=0.03
77.06:0.03
77.0441..0
76.54:0.88
77.1610.45
76.83.1
77.3111..1
78.58.0.44
ROC-AUCH
64
05,511:143
67.0740.4
68.43=0.22
65.25+1.29
66.5111377
07.5841.36
65.35=1.03
66.08:0.81
65.41:11228
72.1810.08
C1
App 4
5.2-14.92
7.4.6.69
120.63
4.3410..33
2.43100.03
5,46.10.38
5.611.084
5.21110.6
3.46.10.98
0.50:00.1
0.74.10.56
Ago 4
15.86
6.3126
0.8520.2
2.7340.04
3.24:0.00
6.47:00.26
5.03+1.49
4.5840.88
3.19:0.73
0.71:0.03
0.70=0049
ACC1
72.05:2.6
75.4240..4
76.49117
74.44=0.47
77,07:0.22
76.16:1.91
75.49:10.82
78.1810.91
76.24110.68
77.12:10228
78.4::062
ROC-ALIC
62.36:6.29
63.7643107
03.81.225
60.63110:06
62.51.3.27 27
65.49-1..39
62.3611.18
62.65.00.89
61.35-10.92
64.16:10.99
0.25::0.2
C2
App 1.
8.144:439
8.7443.6
3.54+0.42
3.54=1.6
2.98+0.01
4.22+
3.61=0.74
6.344:0.77
2.35++0.39
164+1106
1.62= 1.53
ABc 4
6.714.3 2.35.12.4
2.6310.61
2.341.0.33
3.65:10.16
5.711111
3.57
4.37
2.96.10.81
0.93.10.7
0.40 0.08
ACC1
68.15:0016
70.3111.77
71449-0.56
70.11=0.04
70.99+0.96
71.43+1..2 24
7..28411.35
70.8310.65
70.03+0.48
:1.81
72.77
ROC-AUCH
64.64414449 65.90:11.72
65.96:1.19
64.75-0.14
63.1812.53
65.36.11.03
6..3741.06
64.52.0.91
63.5910.63
06.710.91
75.6310.12
C3
App 1.
8.740.12 9.46110.06
3.05
0.54:10.07
3.221:045
5.60.19.3
0,28:0.94
5.1211.36
2.86::.25
0.25-10.2
1.18
Ago 4
9.47+0003
9.71=8.29
3.35+2246
2:23+0.08
1.87+0.36
6.3444.62
4.82+1.33
5.87:40.99
3.41+0.89
0.81+0.06
0.31=0.04
ACC1
68.26.13.09
70.8915.33
71.7410.45
6..84.6.36
71.28.1022
71.35.14.28
71.48.1.811
71.22:0.29
71.4710.92
72.15.10.42
72.1910.71
ROC-AtIC
65.32:14.42
64.284:3.45
6.61
06.98:2.3
63.45:00.6
64.044..67
0.2594:..4
63.45-0.88
65.27::0.68
07.06-0.87
77.56-10.02
C4
App L.
1.46+12.08 6.13=4.08
3. 0.4
7.8499664
3.42+0.47
4.35=:0.85
3.73=0.92
5.4611118
3.59+0.41
0.61=0.08
1.24=1125
Ago 4
6.61111.22
8.16:2238
2.8210.19
2.1819991
3.2240
5.07::074
4.18
5.3411.22
2.4610.87
1.16:0.13
0.36:0020
Rank
11
10
5
7
Table Classification and fairness metrics (%) on Pokecs. t indicates that higher values are better, while J indicating the opposite. We highlight the best results in bold.
Dataset
Metric
MLP
GCN
FairVONN
NIFTY
CAF
SAGM
RTR
FairaGNN
DANCE
ACC1
52.74
54.8341.334
60.810.54
58.68-5.554
19.37:1..45
58.7842.88
57.4213.68
62. 62.00:10.24 66.58:10.2 20
ROC-AUCT
65.38=0.43
63.4842.34
65.26=1445
67.09+2.25
66.86+1.32
65.67+2.4
63.29+1.36
67 3243.3
02.88:0..1
Pokee-n
ADP 4
4.86111.23
7.3820.28
5.8811.34
4.2113.43
5.4912.65
5.67
4.58
1.3410.27
0.83110.22
Ago 4
1.1642.31
0.37+0.52
6.2642.21
3.8243.88
5.02+0.73
4.1942.45
3. 3.11-2.37
1.432.668
0.29:+012
Rank
8
9
7
3
2
4. Experiments
beled BO through B4. BO is used for training and validation. while B1- B4 serve the test set.
4.1. Experimental Setup
Baselines. We compare DANCE with four baseline groups: (A) Traditional learning methods: Foundational represen- tation learning approaches, including MLP (Pal & Mitra, 1992). GCN (Kipf & Welling, 2016). (B) Fair GNNs: GNNs designed to improve fairness, including FairVGNN (Wang et al., 2022), NIFTY (Agarwal al., 2021), EDITS (Dong et al., 2022), CAF (Guo et al., 2023). (C) -iitt--disttibuttinn (OOD) methods: Approaches for learning robust represen- tations that generalize under distribution shifts, including EERM (Wu et al., 2022). SAGM (Wang et al., 2023). (D) Fairness under distribution shifts methods: Methods ad- dressing distribution shifts while preserving fairness across training and test distributions, such as RFR (Jiang et al., 2023), FatraGNN (Li et al., 2024b).
Datasets. We evaluate the performance of DANCE under distribution shifts using three real-world datasets, described as follows: 1) Credit-Cs is derived from the Credit dataset (Yeh & Lien, 2009), where nodes represent credit card users. The task involves classifying users' credit risk as either high or low, with "age" designated as the sensitive attribute. To explore the data structure, we apply a modularity-based community detection method (Newman, 2006), partition- ing Credit-Cs into five communities labeled CO through C4. These partitions reveal different data distributions across the communities. Community CO is utilized for training and validation, and the remaining communities (CI to C4) serve as the test set. 2) Pokecs is constructed from the Slo- vakian social network (Dai & Wang, 2022), where users are grouped by province. The task is to predict users' work- ing fields, with "region" serving as the sensitive attribute. Pokecs consists of two graphs, Pokec-z and Pokec-n, nn, each containing users from two different regions. Pokec-z is used for training and validation, while Pokec-n serves as the test set. 3) Bail-Bs is derived from fairness-oriented graph Bail, in which the nodes represent defendants released on bail (Jordan& & Freiburger, 2015). The task aims to determine whether a defendant should be granted bail, with "race" as the sensitive attribute. Following the approach used for Credit-Cs, Bail-Bs is partitioned into five communities, la-
Performance Evaluation. We evaluate node classification performance using two key metrics: accuracy (ACC) and ROC-AUC. Fairness is measured with ADP and Ago, as detailed in Section 2, where lower values indicate better fair- ness. To comprehensively assess both classification and fair- ness, we adopt the combined metric proposed in FatraGNN (Li et al., 2024b), denoted c = ACC ROCLAUC APP AEO. where higher values indicate better overall performance. The final score of each method is calculated by summing its scores across all test graphs, based on which the overall rankings are provided for comparison.
6

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distributioo Graph Fairness Learning
Experimental Setting. In the experiments, we perform hy- perparameter tuning via grid search across all dataset groups to ensure fair and comprehensive evaluation. For DANCE, the embedding dimension is set to 256. We explore the num- ber of graph encoder layers in the range of [1, 5). dropout rates between [0, 0.5), and learning rates in [o, 0.005]. Ad- ditionally, the trade-off parameter in the Mixup strategy adaptively tuned. To ensure robustness, each method is evaluated over five independent runs with different random seeds, with the mean and variance of each metric reported.
Table 3. Ablation studies on the variants of DANCE
Danisse
Metric
Varl
Var2
Vir3
Var4
DANCE
ACC1
78.50_0.15
78.5110.32
79.52.0.22
21
78.3010013
78.58.10.41
ROC-AUIC
71 00:00-001
71.05+0.01
7201+40.01
71.88+0.66
72.18+0.08 08
Bar
1.1110.71
8.5010.69
6.331143
2.7110.90
0.74_.0.6
Axo
1,15+0 28
0.72+0.00
1.30+1.11
0.38+0.05
0:70-0.40
ACC1
79 79.65_00.0 80
19.5810.34
80.3810001 01
79.4210.42
78.120.62
ROC-AUCY
82:0.05
76.71+0.04
76.79=0.01
76.30=0.35
75:5=0.21
Bor 1
3.08.0.57
4.5424.02
8.63.0024
4.3042.00
1.62-155
Ago
2,00+0.38
2.03+0.77
4.10=0.05
1.00#0:21
0.40=0.08 08
ACC1
72:90=0:37
12.4811.52
72:66:00002
T3.06:
72.77:00775
ROC-ALICY
76.61-0.07
75.95+0.08
75.91+0.01
75.71+0.00
76-6--0112
Sor
2:33.10.20 29
0.50110118
0.43:10011
1.4110.118
1.38__1.18
Axo
1.9122.16
2.4824451
3.9120.3
2.00:33300
0.31-0004
ACC1
72.92_0.337
12.3510,766
73.0210.00 02
12.70.10.01
72.19.0.71
4.2. Performance Analysis
C4 Apr 1.02+0.21
ROC-AUCI
77 77:63=0033
17.5200.11
77.42=0.01
11.2440.00
07.5620.02
1:37+0:46
1.71+00.6
2.56+1.05
1.24-1.25
Ago 2.0000.31
1.29+0226
1.38-0.19
1.24#0.13
0.36=0.20
Table and 2 report the best average performance of all methods across two real-world datasets (Results for Bail- Bs are in Appendix A. Several key observations can be drawn: (1) When comparing traditional learning methods with Fair GNNs, we observe that fairness baselines improve fairness performance at the expense of classification accu- racy. (2) While fairness baselines aim to improve fairness, they struggle with classification under distribution shifts.
73.0
Accuracy
66
Accuracy
72.5
65
72.0
71.5
0.2
0.2
63
U.4
71
U.A
In contrast, OOD methods achieve better classification but exhibit lower fairness across all test graphs due to their inability to learn fair representations. This highlights the need for aaire modules to ensure fairness across varying distributions. (3) DANCE outperforms all other baselines in most cases, demonstrating the effectiveness of disentanglement in filtering out sensitive information and the ad verrsariil module in handling distribution shifts. These results validate the importance of explicitly modeling both fairness constraints and distributional robustness to achieve a trade-off between fairness and classification performance.
0.6
0.8
B
0.6
0.8
0.8
B
(a) Bail-B1
(b) Bail-B BB
Figure 3. Comparison of performance w.r.t. different values of X and 8 for the overall objective.
with Variant 4 confirms that the representation disentan- glement module effectively separates sensitive information from learned representations, thereby enhancing faireess.
4.4. Parameter Analysis
4.3. Ablation Study
We analyze the impact of three hyperparameter groups in DANCE: the loss weights À as well as 3 in the objective function (Equation 16), the ratio y of synthesized nodes, and the trade-off parameter 5 in Mixup Strategy (Equation 7). Our key findings are as follows: (1) As depicted in Figure 3, excessively high values of X and /3 negatively impact ac- curacy. The optimal values, approximately À = 0.6 and 3 = 0.4, effectively balance accuracy and fairness. (2) As shown in Figure 4, the optimal ratio 7 depends on the dataset and its distribution. However, an effective synthesized node ratio typically falls within the range of 0.5 to 0.6, leading to improved fairness performance. (3) When the trade-off parameter ó is fixed, Figure 5 shows that the optimal 5 for both equal odds and demographic parity typically falls be- tween 0.3 to 0.7. However, as no single value is optimal for all datasets, adaptive tuning is still required.
To assess the effectiveness of the various modules in DANCE and gain insight into their contributions, we com- pare DANCE against four variants (Extended ablation stud- ies are provided in Appendix A.2): (1) Variant 1: It re- moves the Mixup module. (2) Variant 2: It removes the adversarial learning module. (3) Variant 3: It removes the group arou-racuieedd alignment module. (4) Variant 4: It removes the representation disentanglement module. The results of DANCE and its variants are presented in Table 3, with key observations as follows: (1) Compared to Variant 1, remov- ing the Mixup module significantly affects performance, as extending an accurate classification boundary relies on properly synthesizing features for generated nodes. (2) The comparison with Variant 2 reveals that adversarial learning effectively mitigates distribution shifts, improving both fair- ness and classification performance. (3) The comparison with Variant 3 demonstrates that the group- acquirec align- ment module is essential for aligning adversarial learning representations with original representations, significantly enhancing fair representation learning. (4) The comparison
4.5. Visualization
We present an intuitive visualization of learned represen- tations in both the training and test graphs on the Pokec dataset via t-SNE (Van der Maaten & Hinton, 2008). As
7

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distributioo Graph Fairness Learning
10
10
Demoorrpphic Parity
1.8
0.8
1.4
0.6
06-
066
Equal
1.0
0.4
0.6
0.2
02
022
0.2
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
The ratio of synihesized nodes y
The ratio of synihesized nodes
00
02
04
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.5
10
(a) DP (Credit)
(b) EO (Credit)
(a) pokec_
(b) pokec_n
Figure 4. Comparison of fairness w.r.t. different ratios y for sya- thesized minor nodes.
Figure 6. Visualizations of representations learned from the train- ing and test graphs on the Pokec dataset.
4.0
Demographin Parity
SHat
6-077 5:03
5H1
5-0.3
5-0.3
$-0.3
rates an adversarial task for predictiong sensitive attributes, ensuring the GNN's predictions are independent of these attributes. However, these approaches all assume that the training and test graphs follow the same distribution.
S-0.5
Equal Ordds
$-0.5
2.0
1,0
1,0
0.0
C1
C2
C3
C4
0.0
C1
C2
C3
C4
Fairness under Distribution Shifts. Distribution shifts re- fer situations where the test data distribution differs from that of the training data (Liu et al., 2021). Several studies have explored faimesss under distribution shifts (Rezaei et al., 2021: Giguere et al., 2022; Lin et al., 2024). Shifty (An et al., 2022) reweights the training samples to match the group proportions present in the test samples. The algorithm (Man- dal et al., 2020) treats test data as weighted combinations of training samples and focuses on ensuring fairness un- der the worst-case distribution shift. Additionally, some works (An et al., 2022) establish sufficient conditions for fairness transfer and propose self-training to balance and minimize consistency losses across different groups. Never- theless, most of these methods are restricted to Euclidean data. Recently, FatraGNN (Li al., 2024b) tackled fairness under distribution shifts in graphs. However, it overlooks the problem of group imbalance and unintentionally ignores task-related information during distribution shifts.
The trade panameter of Mixup
The trade off parameter Mixup
(a) DP (Credit)
(b) EO (Credit)
Figure 5. Comparison faimess w.r.t. different trade-off parame- ter 5 for unbiased Mixup.
shown in Figure 6, nodes are color-coded by target and sen- sitive labels in the latent space. The representations of nodes within the same EO group remain closely aligned across training and test graphs, demonstrating that DANCE pre- serves representation consistency under distribution shifts. This suggests that DANCE mitigates data distribution shift, enhancing both fairness and classification generalization.
5. Related Work
Fairness in GNNs. Recent studies show that graph rep- resentation learning, particularly GNNs, tends to inherit biases from the training graph, with the message-passing mechanism in GNNs further amplifying these biases (Dai & Wang, 2021; Dong et al., 2023). Our work primarily addresses group fairness, which can be grouped into pre-, in-, and post-processing strategies according the stage at which they applied. Specifically, pre-processing strate- gies aim to modify the graph data to ensure fairness before the model is trained. EDITS (Dong et al., 2022) mitigate both graph attribute and structural bias with Wasserstein distance minimization between group pairs. In-processing strategies aim to adjust the learning process itself to pro- mote fairness during model training. NIFTY (Agarwal et al., 2021) introduces new multiple-objectiee force the fairness and stability of the GNN. Graphhair (Ling et al., 2023) employs automated augmentation to achieve fairness and informativeness in the generated graph. Post- processing strategies focus on adjusting the model's 's output to ensure fairness. FairGNN (Dai & Wang, 2021) incorpo-
6. Conclusion
In this paper, we propose DANCE, a novel approach for graph fairness learning under distribution shifts. Unlike traditional methods that the training and test graphs share the same distribution, DANCE explicitly addresses graph distribution shifts commonly encountered in real-world sce- narios. Specifically, we generate challenging yet unbiased virtual graph data in both graph and hidden spaces by in- corporating unbiased mixup and fairness-aware adversarial learning to simulate distribution shifts from data-centric view. Building on this, group-acquire alignment objective and representation disentanglement objective are further proposed to enhance the fairness in the model. Extensive experiments on several real-world datasets demonstrate that our DANCE effectively improves both faimness and model performance under distribution shifts, making it a promising solution for real-world graph learning tasks.
function to
8

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
Impact Statement
lernational Conference on Data Mining Workshops, pp. 13-18, 2009.
The proposed DANCE framework advances fairness-aware graph learning under distribution shifts by integrating dual unbiased data expansion and group-acquired alignment. By generating challenging yet unbiased virtual graph data in both graph and feature spaces, DANCE simulates distri- bution shifts from a data-centric perspective. It leverages mixup-based minority group expansion and adversarial per- turbation to enhance robustness, while explicitly disentan- gling sensitive and task-related information to improve fair- ness. Furthermore, the group-acquired alignment mecha- nism promotes consistency of representations across sen- sitive groups. This dual expansion and alignment strategy enables DANCE to achieve superior generalization and fair- ness on out-o--distribution graphs. The framework holds broad potential for wolld applications where demo- graphic disparities and distribution shifts are prevalent, such as financial risk prediction, social network analysis, and criminal justice modeling.
Dai, E. and Wang, S. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the International ACM Conference on Web Search & Data Mining, pp. 680-688, 2021.
Dai, E. and Wang, S. Learning fair graph neural networks with limited and private sensitive attribute information. IEEE Transactions on Knowledge and Data Engineering. 35(7):7133-7117. 2022.
Ding, F., Hardt, M., Miller, J., and Schmidt, Retiring adult: New datasets for fair machine learning. In Proceed- ings of the Conference on Neural Information Processing 2021.
Systems, pp.
Dong. Y., Liu, N., Jalaian, B., and Li, J. Edits: Model- ing and mitigating data bias for graph neural networks. In Proceedings of the Web Conference, pp. 1259-1269, 2022.
Acknowledgement
This paper is partially supported by the National Key Re- search and Development Program of China with Grant No. 2023YFC3341203 and the National Natural Science Foundation of China (NSFC Grant Number 62276002 and 62306014) well the Fundamental Research Funds for the Central Universities in UIBE (Grant No. 23QN02).
Dong. Y., Ma, J., Wang, S., Chen, C., and Li, J. Fairness in graph mining: A survey. IEEE Trunsactions on Knowl- edge and Data Engineering. 35110))10583-1002, 2023.
Gasteiger, J., Weißenbbegger, S., and Günnemann, S. Dif- fusion improves graph learning. In Proceedings of the Conference on Neural Information Processing Systems, 2019.
References
Giguere, S., Metevier, B., Brun, Y., Da Silva, B. C., Thomas, P. S., and Niekum, S. Fairness guarantees under demo- graphic shift. In Proceedings of the International Confer- ence on Learning Representations, 2022.
Agarwal, C., Lakkaraju, H., and Zitnik, M. Towards unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pp. 2124.1124. PMLR, 2021.
Guo, Z., Li, Xiao, T., Ma, Y., and Wang, S. Towards fair graph neural networks via graph counterfactual. In Pro- ceedings of the International Conference on Information and Knowledge Management, pp. 669,678,77 2023.
An, B., Che, Z., Ding, M., and Huang, F. Transferring fairness under distribution shifts via fair consistency reg- ularization. In Proceedings of the Conference on Neural Information Processing Systems, pp. 32582-32597, 2022.
Han, X., Jiang, Z., Liu, N., and Hu, X. G-mixup: Graph data augmentation for graph classification. In Proceedings of the International Conference on Machine Learning, pp. 8230-8248, 8248, 2022.
Bengio, Y., Deleu, T., Rahaman, N., Ke, R., Lachapelle, S., Bilaniuk, O., Goyal, A., and Pal, C. A meta-transfer ob- jective for learning to disentangle causal mechanisms. In Proceedings of the International Conference on Learning Representations. 2019.
Hardt, M., Price, E.,, and Srebro, N. Equality of opportunity in supervised learning. In Proceedings of the Conference on Neural Information Processing Systems, pp. 3323-33, 2016.
Bose, A. and Hamilton, W. Compositional fairness con- straints for graph embeddings. In Proceedings of the International Conference on Machine Learning, pp. 715- 724, 2019.
Jiang, Z., Han, X., Jin, H., Wang, G., Chen, R., Zou, N., and Hu, X. Chasing fairness under distribution shift: A model weight perturbation approach. In Proceedings of the Conference on Neural Information Processing Systems, pp. 63931-63944, 2023.
Calders. T., Kamiran, F., and Pechenizkiy, M. Building classifiers with independency constraints. In IEEE In-

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
Jordan, K. L. and Freiburger, T. L. The effect of
Li, Z.,, Dong, Y., Liu, Q., and Yu, J. X. Rethinking fair graph neural networks from re- re-balancing. In Proceedings of the International ACM SIGKDD Conference Knowledge Discovery & Data Mining, pp. 1736-1745, 2024c.
race/ethnicity on sentencing: Examining sentence type, jail length, and prison length. Journal of Ethnicity in Criminal Justice, 13(3):179-199) 2015.
Ju, W., Fang, Z., Gu, Y., Liu, Z., Long, Q. Qiao, Z., Qin, Y., Shen, J., Sun, F., Xiao, Z., et al. A comprehensive survey on deep graph representation learning. Neural Networks, pp. 106207, 2024.
Liao, P., Zhao, H., Xu, K., Jaakkola, T., Gordon, G. J., Jegelka, S., and Salakhutdinov, R. Information obfus- cation of graph neural networks. Proceedings of the International Conference on Machine Learning, pp. 6600~ 6610, 2021.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: /609.02907, 2016.
Lin, Y., Zhao, C., Shao, M., Meng, B., Zhao, X., and Chen, H. Towards counterfactual fairness-awaae domain gener- alization in changing environments. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 4560 4568, 2024.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. Proceedings of the International Conference on Learning Representations, 2017.
Ling, H., Jiang, Z., Luo, Y., Ji, S., and Zou, N. Learning fair graph representations via automated data augmenta- tions. In Proceedings of the International Conference on Learning Representations, 2023.
Köse, Ö. D. and Shen, Y. Fairness-aware node representa- tion learning, arXiv preprint arXiv:2106.05331, 2021.
Li, F.. Wang, B., Zhu, L., Li, J., Zhang. Z., and Chang, X. Cross-domain transfer hashing for efficient gross-modal retrieval. IEEE Transactions Circuits and Systems for Video Technology, 2024a.
Liu, J., Shen, Z., He, Y., Zhang, X., Xu, R., Yu, H., and Cui, P. Towards out-of -f-triiiiitittoioon generalization: A survey, arXiv preprint arXiv:2108. 13624, 2021.
Mandal, D., Deng, S., Jana, S., Wing. J., and Hsu, D. J. Ensuring faimess beyond the training data. In Proceed- ings of the Conference on Neural Information Processing Systems, pp. 18445-18456, 2020.
Li, H., Wang, X., Zhang, Z.,, and Zhu, W. Out-of-distribution generalization graphs: A survey, arXiv preprint 0rXiv:22022.0988,222222 2022a.
Meng, K., Wu, P., and Yang, X. Lipschitz continuity of solution multifunctions of extended \ell_1 regularization problems. arXiv preprint arXiv:2406. 16053, 2024.
Li, H., Zhang, 7., Wang, X., and Zhu, W. Learning invariant graph representations for out-of-distribution generaliza- tion. In Proceedings of the Conference on Neural Infor- 2022b.
mation Processing Systems, pp.
Newman, M. E. Modularity and community structure in net- works. Proceedings of the national academy of sciences, 103((3):8577-88822 2006.
Li, H., Zhang, Z., Wang. X., and Zhu, W. Invariant node representation learning under distribution shifts with mul- tiple latent environments. ACM Trunsactions on Informa- tion Systems, 42(1):1-30, 2023a.
Pal, S. K. and Mitra, S. Multilayer perceptron, fuzzy sets, classifiaction. 1992.
Li, P., Wang, Y., Zhao, H., Hong, P., and Liu, H. On dyadic fairness: Exploring and mitigating bias in graph connec- tions. In Proceedings of the International Conference Learning Representations, 2021.
Park, S. and Byun, H. Fair-vpt: Fair visual prompt tuning for image classification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1 12278, 2024.
Li, W.-Z., Wang, C.-D., Xiong, H., and Lai, J.-H. Graphsha: Synthesizing harder samples for muss-imbalanced node classification. In Proceedings of the International ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1328-1340, 2023b.
Park, S., Lee, J., Lee, P., Hwang, S., Kim, D., and Byun, H. Fair contrastive learning for facial attribute classification. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 10389-10398, 2022.
Li, Y., Wang, X., Xing, Y., Fan, S., Wang, R., Liu, Y., and Shi, C. Graph fairesss learning under distribution shifts. In Proceedings of the Web Conference, pp. 676- 684, 2024b.
Pham, T.-H., Zhang, X., and Zhang, P. Fairness and accu- racy under domain generalization. In Proceedings of the International Conference on Learning Representations, 2023.
10

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribation Graph Fairness Learning
Ren, T., Zhang, H., Wang, Y., Ju, W., Liu, C., Meng, F,, Yi, S., and Luo, X. Mhge: Multi-scale hard sample mining for contrastive deep graph clustering. Information Processing & Management, 62(4):104084 2025.
Yang, C., Wu, Q.. Wang. J., and Yan, J. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. In Proceedings of the Interna- tional Conference on Learning Representations, 2023.
Rezaci, A., Liu, A., Memarrast, O., and Ziebart, B. D. Ro- bust fairness under covariate shift. In Proceedings of the AAA/ Conference on Artificial Intelligence, pp. 9419- 9427, 2021.
Yeh, I.-. and Lien, C.-h. The comparisons of data min- ing techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2):2473 24800, 2009.
Spinelli, I., Scardapane, S., Hussain, A., and Uncini, A. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence, 3(3):344-354, 2021.
Yu, J.. Liang J., and He, R. Mind the label shift of augmentation-basee graph ood generalization. In Pro- ceedings of the IEEE/CVF Conference on Computer Vi- sion and Pattern Recognition, pp. 11620-11630, 2023.
Sui, Y., Wu, Q. Wu, J., Cui, Q., Li, L., Zhou, J., Wang, X., and He, X. Unleashing the power of graph data augmenta- tion on covariate distribution shift. In Proceedings of the Conference on Neural Information Processing Systems, pp. 18 1810--18131, 2023.
Zhang, F., Chen, C.,, Hua, X.-S., and Luo, X. Fate: Learning effective binary descriptors with group fairness. IEEE Transactions Image Processing, 2024a.
Zhang, G., Yuan, G., Cheng, D., Liu, L.,, Li, J., and Zhang, S. Disentangled contrastive learning for fair graph repre- sentations. Neural Networks, 181: 181:106781, 2025.
Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Zhang, H., Cissé, M., Dauphin, Y., and Lopez-Paz, D. mixup: Beyond empirical risk minimization.; iz iclr//i, In Proceedings of the International Conference on Learn- ing Representations, 2018
Volpi, R., Namkoong, H., Sener, O., Duchi, J. C., Murino, V., and Savarese, S. Generalizing to unseen domains via adversarial data augmentation. In Proceedings of the Conference on Neural Information Processing Systems, pp. 5339-5349, 2018.
Zhang, K., Liu, S., Wang, S., Shi, W., Chen, C., Li, P., Li, S.,
Li, J., and Ding, K. A survey of deep graph learning under distribution shifts: from graph duitt--distribution gener- alization to adaptation. arXiv preprint arXiv:2410.19266 2024b.
Wang, P., Zhang, Z., Lei, Z., and Zhang. Sharpness- aware gradient matching for domain generalization. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 3769-3778, 2023.
Zhuang, X., Zhang, Q.. Wu, B., Ding. K., Fang, Y., and Chen, H. Graph sampling-bass based meta-learning for molec- ular property prediction. In Proceedings of the Inter- national Joint Conference on Artificial Intelligence, pp. 4729-4737,2000
Wang, X., Liu, H., Shi, C., and Yang, C. Be confident! towards trustworthy graph neural networks via confidence calibration. In Proceedings of the Conference on Neural Information Processing Systems, pp. 23768-23777 2021.
Wang, Y., Zhao, Y., Dong, Y., Chen, H., Li, J., and Derr, T. Improving fairness in graph neural networks via miti- gating sensitive attribute leakage. Proceedings of the International ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1938-1948, 2022.
Wang, Z., Qiu, M., Chen, M., Salem, M. B., Yao, X., and Zhang, W. Toward fair graph neural networks via real counterfactual samples. Knowledge and Information Sys- tems, 66(1 1):6617-6666 6641, 2024.
Wu, Q., Zhang. H., Yan, J., and Wipf, D. Handling distribu- tion shifts on graphs: An invariance perspective. arXiv preprint arXiv:2202.02444
2022.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-244 2020.

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribbtiion Graph Fairness Learning
Table 4. Performance comparison (%
Bail-Bs.
Datiset
Matric
GCN
FairVGNN
NIFTY
EDITS
BERM
FittaGNN
DANCE
ACCT
70.53:1.011
72. 72.83144000
69.7642.03
68 20
72.0011.72
73.25=1.4 69.39-12.30
73.0814.22
71 13:63:11.5
1.52 86.64:0.93
95. 154:12 94
ROC-AUCT
6.876+1.87
19.41+14.42
64.8244.32
62.6525.95
00.9140.31
63.9841.28
6.884+1.84
62.7643.46
02.39=1.63
80.9240.01
99.76+0.00
B1
App 4
4.83=9.38
4.5840.78
11.06:4.58
7.2144.54
4.35+1.3
8.86+2267
4.46=2.03
7.33+4.50
2.57
8.45=2.87
3.89217.19
Ago 4
7.48#7.31
10.19-2.3
8.36244882
9.5742.8
9/2240.97
23
4.97=2331
7.30+4.56
2.63340.88 87
4.79=3.19
1.41=
ACCC
64.33:40.33
09.8840.45
65.03+24
69.9548.3
09.0340.11
70.240.12
69.36+1.37
68.67:43.24
G8
18.62=1.42
90.48:40.44
09.50=0.00
ROC-AUCT
59.2141.18
68.35110.68
70.2142261
65.93113.46
74.2540.73
72.2310.49
71.5812.03
70.6742.14
20.25=2235
90.88:14455
09,8110.00
B2
Apr 1
8.36#1.62
6.91
6.61=2.75
3.21
3.243.08
8.31
2.03#3.02
6.78+22.3
2.154:194
0.15=0.79
0.07=0.00
ABo 4
6.5120032
8.681:02
3.23:13477
3.5722.8
2.89:10.54
6.2910.12
3.8112.08
6.31133.56 56
2.6111163
0.43=1.14
0.26-0.12
ACCC
60.76:10.18
68.58 4.2
70.6311..11
08.819.76
1.
70. 70.0915.44
08.9T
69.50
68
18:361118
91.57:14.65
91.46:0.55
ROC-AUCT
62.89:42.87
72.9910.08
80.7645.01
77.9845.5
19.2841.44
79.
79.9843.61
78.0142.07
78.43433.90
90
78.74=1
995
94.42:33.63
99.0610.15
B3
ADp 4
9.810.388
12.7242.4 44
6.05=0.45
6.21
6.2110.03
5.6413.19
6.32
45
6.7813.22
4.23
5.02=3.54
2. 2.88=0.06
Ago 4
6.20#0.36
14.1543.00
9.18=0.36
5.67#2.8
3.08+0.27
4.65+1.21
4.32=2.67
6.6742.84
4.7242.17
2. 2.48=4.94
3.17=0.25
ACCP
63.13:11669
09.4310.48
08.994
37.96111.99
68 08.4240.114
70.9
67.33
70.88
69 09.18
30.95:13.39
98.6 0.06
ROC-AUCT
61.57:0.97
76.41:0.78
17.
60.21:5.39
69. 69.241.41
68.81
71.9341.11
69.3411.88
68
2555522252
91.4233.79
000001
B4
App 4
4.45=3.15
4.4
6.21=6603
3.21
3. 3.249.1
7.23+0.26
3.84
6.3626.32
3.43+2245
2.48=3.09
0.41=0.04
ARO 4
3.29#3.54
8.74
6,33=66.18
2.67#2.88
5.687.88
9.04
5.36
7.34+4.67
3.5142239
2.45=6.67
0.76-0.01
Rank
10
6
3
8
4
A. Additional Results
A.1. Results on Bail-Bs
Table 4 shows classification and fairness performance on Bail-Bs.
A.2. Extended Ablation Study on Mixup and the Adversarial Module
To evaluate the effectiveness of the various modules in DANCE and understand their functions, we compare DANCE with six variants: (I) Variant I: selects anchor nodes through random sampling rather than hard sampling. (2) Variant 2: It removes the mixup module. (3) Variant It configures the adversarial function to maximize only the classification component, excluding the faimesss term. (4) Variant 4: It configures the adversarial function to maximize only the faimess component, excluding the classification term. (5) Variant 5: It eliminates the group-acquired alignment module. (6) Variant 6: It eliminates the representation disentanglement module.
The results of DANCE and its variants are presented in Table 3. Our key observations are as follows: (1) Impact of hard sampling and mixup. Compared to Variant 1, random sampling alone has a limited effect on final performance. Instead, constructing sufficiently challenging samples essential for improving model performance. Compared to Variant 2, removing the mixup module has a more significant impact on final performance, as extending an accurate classification boundary relies on appropriately synthesizing features for the generated nodes. (2) Effect of adversarial learning components. The comparison with Variant 3 and Variant 4 reveals that the max component of the adversarial function enhances generalization to dittoo--distrbbtiinn data for target classification, whereas the min component focuses on fairness optimization in such settings. Consequently, Variant 3 achieves better performance in target label classification, while Variant 4 excels in fairness representation. (3) Role of group-acquired aligmment. The comparison with Variant 5 demonstrates that the contrastive aligmment module plays a crucial role in aligning adversarial learning representations with the original representations. This alignment significantly enhances fair representation learning. (4) Effectiveness of representation disentanglement. The comparison with Variant 6 confirms that the disentanglement contrast module effectively separates sensitive information from the representation learning process, thereby facilitating the learning of fairer representations.
B. Theorem Proof
Theorem 3.1: For any i e Vs, there exists j E V_, such that
8
Σ
0 (TT (Thn
#0;
is
12

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribbtioo Graph Fairness Learning
Table 5. Extended ablation studies on the variants of DANCE
metric
Varl
Var2
Var3
Var4
Var5
Varó
DANCE
ACC1
78.21+0.31
78.01+0.12
78.90=00.19
78.51+0.32
79.52+0.21
78.30+0.13
78.58+0.41
ROC-AUCT
71.15+0.03
71.46+0.02
71.57+0.01
72.01=0.01 71.55+0.011
71.48+0.06
72.18+0.08
C1
Apr 4
1.21+0.43
2.88+0.67
3.55+2288
3.54=0.69
6.33+1.43
2.71+0.90
0.74+0.56
Ago 4
0.52+0.12
0.74++0.0
0.49+00.5
0.72-0.00
1.30+1.11
0.38+0.05
0.70+0.49
ACC1
79.21+0.31
79.33++0.9
80.02=0.002
79.5
80.58+0.01
72.42+0.42
78.4+0.62
ROC-AUCT
75.9=0.28
74.6+0.11
76.74+0.02
76.71+0.04
76.79+0.01
76.30+0.35
75.5+0.21
C2
App 4 Ago
2.24+0.57
3.11+0.73
5.76+0.73
4.54=4.02
8.63++024
4.30+2.05
1.62+1.53
0.87+0.62
1.87+0.33
2.49+0039
2.03-0.77
4.10+0.05
1.99+0.21
0.40+0.08
ACC1
72.7910.42
12.62:1..1
72.0610.79
1..4811.52
72.66=0.02
78.0610.13
72.7710.73
ROC-AUCT
75.2810.20
75.3010.12
70.06
75.9510.00
7.091=0.01
75.7110.03
7..6310.12
C3
ADP J 1.18=0.07 2.1810.15
1.0010.58
0.50=0.18
0.4310.01
1.44
1.18
AgO
0.81
0.9110.10
2.4813.62
2.13-4.51
3.94.0.03
2.031:3.00
0.31-10.4
ACC1
72.2110.37
72.33:0.57
72.78:0.11
0..3510.76
73.02:10.02
72.7610.01
72.1910.71
C4 ROC-AUCT
77.0111.01
77.0310.03
77.5110.04
77.5210.01
07.42-0.01
77.2410.09
77 57.0020.02
ADP 1.60-0117
1.3110.29 0.9010.07
1.37=0.46
1.7110.06
2.55
1.2411.25
AsO!
0.5520335
1.3510.19
0.9510.14
1.29=0.26
1.3840.19
1.2410.13
0.3610.20
For any i E V-a, for all j E Va. we have
TT ((-
= =0.
Theorem One indicates that the graph diffusion method can precisely control the information propagation between different groups, which is crucial for improving the fairness and performance of the model when dealing with data from different groups
Remark:
Proof:
First, we consider the propagation within and out of the minority group. Let E Vg- According to matrix multiplication, we have
Tanels = dig.
(Tl (Ta [A D = A D Danc.jj.
Since when constructing Aane, for i E V. exists j $ Vo such that Annoii + O, and Er= 10 converges. We have
Σ r TT Tanat r=0
H (-)
0r
Ty. Tanclit H (H1)))
k=1
Hence, for a specific j & V., Er Or) propagated to nodes j & V..
TH Tindii (H [
* O, which means that information from i E V, can be
Then, we show how this method blocks the propagation to the non-minority group. Let i E V for all j Vs. A Aane,s O. Suppose that for all j E V, and s 1,...,r,
T = 0.
We have
[V] Tin [Ti Tameleg-
onc 1ag =
k=
Since [Tincks 0 (for k.j V2) and TT
0 (for A Vo), we have [T ly 0 (for j E V.). Therefore,
8
Σ
o" (T (Tnn (11)
-0 (.V.).
13

---

DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning
Theorem 3.2: Suppose that the loss function F(w) is differentiable with respect the parameter w, and there exists constant M 0 such that the gradient of the loss function is M M-Lipschitz continuous. We adopt the SGD algorithm to update the parameter. When appropriate learning rate is chosen such that 0 < a < M lim F(w) exists, which means the loss function F(w) converges.
2 we have lim, [| 0 and
Remark: The Lipschitz continuity assumption limits the rate of change of the gradient of the loss function, which is a common condition for the convergence proof of many optimization algorithms.
Proof: Based on the M -iLisschitz continuity, we have
M llwe w1ll?
F(w2) S F(w1) + V.F(wi) (w2 w1) + 2
Let W2 = Wh+1 and wt, then we have
F(w++1) & F(wi) a(1 Ma
When 0 < a < 2 convergence theorem, lim, F(wr) exists.
N we have 1(w(+1) I F(wi). Moreover, since F(w) has lower bound, according to the monotone
Next, we prove that lim [VF(w))]] = O. From the analysis above, we can get
Ma )1 |[ S F(w)) F(w1+1)-
a(1
Sum both sides of the inequality from t T -
Ma a(1
[V[(m)] F(Ww) F(WT).
Since lim Flws)) exists, Ei= || [VF((w))]) converges. According to the necessary condition for the convergence of a series, we have lim ||VF(w>)]] 0.
14


Reviews:
[{"review_id": "hRc70uGATe", "reviewer": "Reviewer_wtqC", "summary": "This paper proposes the DANCE method, which aims to address the problem of fair learning of graph neural networks (GNNs) under distributional bias. Traditional methods assume that training and testing data are identically distributed, whereas distribution bias is prevalent in real-world scenarios, leading to degradation of model fairness and performance.The core idea of DANCE is to generate unbiased and challenging virtual graph data in structural and feature space to simulate distributional bias and enhance model robustness through a data-centric perspective.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper and your insightful review. Here we address your comments in the following.\n\n>Q1. Why Theorem 3.1 can show that the graph diffusion method can precisely control the propagation of information between different groups?\n\nTo clarify the intuition behind the assumption in Theorem 3.1, we rewrite it as follows: \n\nFirst, we prove that for any $i \\in \\mathcal{V} _ s$, there exists $j \\in \\mathcal{V} _ {-s}$ such that: \n$$\n\\left[\\sum _ {r=0}^{\\infty} \\theta^r ({T} _ {\\text{anc}}^r {H}^{(l-1)})\\right] _ {ij} \\neq 0.  \n$$  \n\nBy the definition of $A _ {anc}$, for any $i \\in \\mathcal{V} _ s$ we can get $A _ {anc,ik} > 0$, where $k \\in \\mathcal{V} _ s \\cup \\{v _ {syn}\\}$. And there exists $j \\in \\mathcal{V} _ {-s}$ satisfying $A _ {anc,v _ {syn}j} > 0$. This implies that for any $i \\in \\mathcal{V} _ s$, there exists a path $i \\to v _ {syn} \\to j$ with $j \\in\\mathcal{V} _ {-s}$, where $A _ {anc,iv _ {syn}} > 0$ and $A _ {anc,v _ {syn}j} > 0$. For path length $r _ 0 = 2$, we can get $[T _ {anc}^2] _ {ij} = \\sum _ {k \\in V} [T _ {anc}] _ {ik}[T _ {anc}] _ {kj} \\\\  \n\\geq \\frac{A _ {anc,iv _ {syn}}}{D _ {anc,i}} \\cdot \\frac{A _ {anc,v _ {syn}j}}{D _ {anc,v _ {syn}}} > 0$. Similarly, for $r _ 0 > 2$ with the path $i = k _ 0 \\to k _ 1 \\to \\cdots \\to k _ {r _ 0} = j$, we have  $[T _ {anc}^{r _ 0}] _ {ij} \\geq \\prod _ {s=1}^{r _ 0} \\frac{A _ {anc,k _ {s-1}k _ s}}{D _ {anc,k _ {s-1}}} > 0$. Therefore, we can get $\\left[\\sum _ {r=0}^\\infty \\theta _ r (T _ {anc}^r H^{(l-1)})\\right] _ {ij} > 0$.  \n\nThen, we prove by mathematical induction that $\\forall i \\in \\mathcal{V} _ {-s}, j \\in \\mathcal{V} _ s$, we have: \n$$\n\\left[\\sum_{r=0}^\\infty \\theta_r (T_{anc}^r H^{(l-1)})\\right]_{ij} = 0.  \n$$  \n\n**Base case ($r=0$)**: For $i \\in \\mathcal{V} _ {-s}$ and $j \\in \\mathcal{V} _ s$, the identity matrix satisfies $[T _ {anc}^0] _ {ij} = \\delta _ {ij} = 0.$\n\n**Inductive step**: Assume $\\forall r \\leq n$ and $\\forall i \\in \\mathcal{V} _ {-s}$, $j \\in \\mathcal{V} _ {s}$, $[T _ {anc}^r] _ {ij} = 0$. For $r = n+1$, we have  $[T _ {anc}^{n+1}] _ {ij} = \\sum _ {k \\in \\mathcal{V} _ s} [T _ {anc}^n] _ {ik}[T _ {anc}] _ {kj} + \\sum _ {k \\in \\mathcal{V} _ {-s}} [T _ {anc}^n] _ {ik}[T _ {anc}] _ {kj}$.\n\n$ \\forall k \\in \\mathcal{V} _ {s} $, the inductive hypothesis implies $ [T _ {anc}^n] _ {ik} = 0 $. $ \\forall k \\in \\mathcal{V} _ {-s}$, by the definition of $A _ {anc}$, $A _ {anc,kj}=0$. Therefore, we can get $[T _ {anc}^{n+1}] _ {ij} = 0$.  \n\nBy mathematical induction, $ \\forall r \\geq 0 $, $[T _ {anc}^r] _ {ij} = 0$, which leads to $\\left[\\sum _ {r=0}^\\infty \\theta _ r (T _ {anc}^r H^{(l-1)})\\right] _ {ij} = 0$.  \n\nThis assumption reflects that **the graph diffusion method in DANCE can shield minority groups from majority interference while permitting essential cross-group feature learning**. This distinction justifies the assumption and highlights the geometric intuition behind Theorem 3.1.\n\n>Q2. Some essential references are not included.\n\nWe will include the following discussion into our revised version:\n\n```\nAdditionally, FairGB [1] introduces a counterfactual node mixup strategy, generating synthetic samples by interpolating node features and labels across different demographic groups to address demographic group imbalances. Similarly, FDGNN [2] and RFCGNN+ [3] design counterfactual augmentations by varying sensitive or label values while preserving the original adjacency matrices to learn fairer representations. In comparison with these methods, our method specifically focuses on mixing minor sensitive group nodes with those of different sensitive attributes to generate challenging samples that extend decision boundaries, thereby enhancing generalization and fairness.\n```\n\n>Q3. What is to be understood by ‘challenging’ in this context?\n\nIn our context, we use the term “challenging” samples to refer to those that are difficult to classify but strategically designed to improve generalization and fairness. Specifically:\n- **Synthesized nodes located near class decision boundaries are generated via Mixup** (Eq. 7) between minor group nodes and auxiliary nodes. These samples **exhibit higher prediction uncertainty and encourage the model to refine its classification boundaries [4]**. \n- **Adversarial learning (Sec. 3.2) introduces perturbations that further amplify this uncertainty**, thereby enhancing the model’s robustness and fairness under distribution shifts. \n\nIn summary, “challenging” refers to samples that are difficult to classify but strategically beneficial for improving both generalization and fairness.\n\n[1] Rethinking fair graph neural networks from re-balancing. KDD 2024\n\n[2] Disentangled contrastive learning for fair graph representations. Neural Networks, 2025\n\n[3] Toward fair graph neural networks via real counterfactual samples. KAIS, 2024\n\n[4] Self-supervised graph-level representation learning with adversarial contrastive learning, TKDD, 2023", "claims_and_evidence": "Experiments on real-world datasets  demonstrate that DANCE outperforms baseline methods in both ​classification performance and ​fairness metrics .", "methods_and_evaluation_criteria": "The OOD issue is really a common problem in reality.", "theoretical_claims": "I am not really sure why Theorem 3.1 can show that the graph diffusion method can precisely control the propagation of information between different groups, could the authors explain this in further detail?", "experimental_designs_or_analyses": "The experimental design is sound.", "relation_to_broader_scientific_literature": "This has implications for the de-biasing of graph representation learning.", "essential_references_not_discussed": "Some of the work on fair graph learning [1,2,3] also involves data reconstruction, which the authors should include.\n\n[1]\"Rethinking fair graph neural networks from re-balancing.\" Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.\n[2] \"Disentangled contrastive learning for fair graph representations.\" Neural Networks 181 (2025): 106781.\n[3]\"Toward fair graph neural networks via real counterfactual samples.\" Knowledge and Information Systems 66.11 (2024): 6617-6641.", "other_strengths_and_weaknesses": "Strengths:\nThis paper provides a principled basis for linking graph diffusion theory to fairness, which is an inspiration for the fair graph learning community.\n\n\nWeaknesses:\nThe author claims ‘The core idea of our DANCE is to generate challenging yet unbiased virtual graph data in both graph\nand hidden spaces...’ but does not define ‘challenging’. What is to be understood by  ‘challenging’ in this context?", "other_comments_or_suggestions": "None", "questions_for_authors": "Please refer to previous comments.", "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": "tDsQhHhpVV", "reviewer": "Reviewer_qutC", "summary": "The paper proposes a method to improve fairness in graph neural networks (GNNs) under distribution shifts. It introduces dual graph expansion to generate unbiased virtual graph data, group-acquired alignment to prioritize negative pairs with identical sensitive labels, and representation disentanglement to separate sensitive attributes from task-related information. Experiments show that DANCE improves both fairness and classification performance compared to existing methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.\n\n> Q1. The performance under the same distribution.\n\nThank you for your comment. We have added the performance of our model and several baselines under the same distribution setting as below. From the results, our method achieves better performance compared with baselines. We will add these results to our revised version. \n\n|Dataset|Metric|FatraGNN|DANCE|Dataset|Metric|FatraGNN|DANCE|\n|-|-|-|-|-|-|-|-|\n|**c1**| ACC↑|78.11| 80.43|**c2**| ACC↑| 77.81|80.05|\n||ROC-AUC↑| 65.59| 74.69 || ROC-AUC↑|68.92|81.23|\n||△DP ↓| 6.88| 4.49 ||△DP ↓| 1.04|1.83|\n||△EO ↓| 4.56| 3.76 ||△EO ↓|1.64|1.91|\n| **c3**  | ACC↑|72.39|80.77|**c4**| ACC↑| 72.98| 76.38 |\n||ROC-AUC↑ | 71.24| 83.21 || ROC-AUC↑ | 71.76| 76.80 |\n||△DP ↓|1.80| 2.64||△DP ↓| 3.09| 3.47|\n||△EO ↓|1.48| 6.00||△EO ↓|2.07| 2.60|\n\n> Q2. Does it mean every component, even the mixup, will contribute to the fairness results?\n\nThank you for the comment. In our framework, each component is designed to address a specific challenge in out-of-distribution (OOD) graph fairness learning, and our ablation results demonstrate that each module makes a meaningful contribution to the final fairness performance.\n\nSpecifically, we expand the graph data in **both the structural space and the feature space**. The **unbiased Mixup** module enlarges the decision boundary of minority groups, helping to rebalance representation across sensitive attributes. The **adversarial learning** module simulates worst-case distribution shifts by introducing challenging perturbations in feature space, enhancing the model's robustness. Building on this expanded data, the **group-acquired alignment** module aligns representations across groups while discouraging the use of sensitive attributes, and the **representation disentanglement** module explicitly separates sensitive and target information to further reduce bias.\n\nTogether, these components form a cohesive design, and the degradation observed in fairness metrics upon removing any one of them confirms that each module plays a critical role in achieving fairness under distribution shifts.\n\n> Q3. In Table 3, while the C3-Var3 cell has better  $ \\Delta DP $ performance, other cells (C-Var3) show significantly lower performance\n\nThank you for the comment. We have provided the following explanation:\n- **Complicated Graph Data**. Real-world graph datasets (such as Credit-Cs) exhibit considerable variability in their structural properties—such as homophily and sensitive group imbalance. \nAs shown in the table below, these graph datasets have different and complicated characteristics, which could result in performance fluctuation. Overall, our full model shows better performance in comparison with the model variant in most cases, which validates the effectiveness of the proposed method. \n\n|Dataset|Sensitive Homophily|s0 Internal Edge Ratio|s1 Internal Edge Ratio|Cross-group Edge Ratio|\n|-|-|-|-|-|\n|C1|0.821| 0.777|0.044|0.179|\n|C2|0.807| 0.774|0.033|0.193|\n|C3|0.755| 0.702|0.053|0.245|\n|C4|0.737| 0.681|0.057|0.262|\n\n- **Previous Observations**. Similar cross-dataset variations have been observed in prior studies. For instance, [2] observes that fairness improvements can vary significantly across different datasets when evaluating fairness-aware GNN methods. \nAs shown in Table 1 of [2], RFR exhibits large fluctuations in $\\Delta$DP between the Adult (1.0, 2.0) and Adult (3.0, 6.0) subsets, while its $\\Delta$DP performance remains relatively stable across the ACS-E (1.0, 2.0) and ACS-E (3.0, 6.0) subsets. This illustrates that the underlying data distribution plays a crucial role, and that fairness improvements achieved on one subset may not generalize consistently across others. \n\n> Q4. Novelty of DANCE\n\nThanks for your comment. The innovations of this work include:\n\n- **Data-centric perspective**. We explore an underexplored yet important OOD graph fairness learning problem from a data-centric perspective, achieving better performance compared to baselines.\n\n- **A unified graph fairness learning framework**. Our framework is a unified approach that combines dual unbiased graph expansion and group-acquired alignment to minimize the domain gap while ensuring fairness.\n\n- **Theoretical analysis**. We provide a theoretical analysis demonstrating that our framework can control information propagation between different groups for fairness learning and ensure the convergence of the loss function.\n\n[1] Laclau C, et al. A survey on fairness for machine learning on graphs. arXiv, 2022.\n\n[2] Jiang et al., Chasing fairness under distribution shift: A model weight perturbation approach, NeurIPS 2023.\n\nThanks again for appreciating our work and for your constructive suggestions.", "claims_and_evidence": "Yes. The claims are reasonable and convincing.", "methods_and_evaluation_criteria": "Yes, the methods and evaluation make sense.", "theoretical_claims": "Yes. The proofs seems correct.", "experimental_designs_or_analyses": "I have some concerns about the experiments.\n1. Although the paper focus on the distribution shift situation, it is worthwhile to see the performance under the same distribution.\n2. The ablation study is very confusing. For example, all Var1 to Var4 (in table 3) have significant degrade with respect to the fairness metrics. Does it means every component, even the mixup, will contribute to the fairness results? I doubt it.\n3. There are some contradict results, for example, in table 3, while C3-Var3 cell has better $\\Delta DP$ performance, other cells (C-Var3) show significant lower performance. The authors did not explain that in the paper.", "relation_to_broader_scientific_literature": "The key contributions of the DANCE framework build upon and extend several lines of research in fair graph learning, out-of-distribution (OOD) generalization, and adversarial learning for fairness. FatraGNN also deals with a similar problem, but this work achieves better performance.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The topic and problem is realistic and interesting.\n2. The experiments are extensive.\n\nWeakness:\n1. Please refer to the concerns in Experiment above.\n2. The methods have limited novelty. The Graph Expansion and Attributes Disentanglement are studied in existing IID fair graph learning, although transferring it to OOD graph learning is novel.", "other_comments_or_suggestions": "Please use the same precision in the table.", "questions_for_authors": "Please refer to the weakness.", "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": "6ICLtSBESQ", "reviewer": "Reviewer_9miH", "summary": "This paper proposes DANCE, a novel framework for enhancing graph neural network fairness learning under distribution shifts by generating unbiased virtual graph data through dual expansion (structural and feature-based) and aligning node representations. It specifically tackles sensitive group imbalance and fairness-performance conflicts by synthesizing challenging yet unbiased virtual graphs and disentangling sensitive attributes. Experiments demonstrate the method's superiority in fairness and generalization performance over existing fairness-aware GNNs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.\n\n>Q1. The framework involves multiple sophisticated modules, potentially increasing the difficulty of implementation and complexity. Also, the author did not discuss the time complexity for the proposed method: how expensive it is to adopt it in practice? Generally the discussions on computational cost, scalability, and efficiency is limited. What are the computational overheads introduced by the proposed approach, particularly in comparison to simpler fairness-aware methods?\n\nThanks for your comment. We have included the efficiency analysis and comparison as follows. From the result, we can observe that our method has a competitive computation cost. In particular, we provide the following analysis:\n\n- **Complexity analysis.** The computing complexity of our framework mainly depends on (a) **Dual graph expansion**, (b) **Group-acquired alignment** and (c) **Representation disentanglement**. Let $N_{syn}$ be the number of synthesized nodes. Then, since logits can be obtained from the previous epoch, for (a), we need $\\mathcal{O}(N^2_{syn})$ extra time for anchor and auxiliary nodes sampling, $\\mathcal{O}(N_{syn}d)$ for feature mixup and $\\mathcal{O}(N_{syn}/N\\cdot|\\mathcal{E}|)$ for generating synthesized edges. Meanwhile, adversarial learning on synthesized data takes $\\mathcal{O}((N+N_{syn})d^2)$. For (b) and (c), the complexity for the target and sensitive encoder is $\\mathcal{O}(2L|\\mathcal{E}|d+2Nd^2)$ with $L$ layers while the view alignment takes $\\mathcal{O}(N|\\mathcal{B}|d)$ with total $|\\mathcal{B}|$ positive and negative pairs. Compared with FatraGNN [1], the additional complexity is $\\mathcal{O}({N}^2_{syn}+(N_{syn}+N|\\mathcal{B}|)d+N_{syn}/N\\cdot|\\mathcal{E}|)$, mainly from the dual graph augmentation and contrastive learning modules, which are carefully controlled in our implementation.\n\n- **Practical training overhead.** From a practical standpoint, we have provided the time complexity and training time of our DANCE to further demonstrate its computational efficiency in comparison to other baselines. The results indicate that our framework maintains a competitive computation cost compared with baselines.\n\n|Model| Params (M) |Training Time (s/epoch on Credit)|\n|-|-|-|\n|FatraGNN |0.140| 0.263 |\n|DANCE |0.536| 0.340 |\n\nIn summary,  our method has a **competitive computation cost** in comparison with the baseline. We will include the above discussion in our revised version. \n\n>Q2. The rationale behind prioritizing negative pairs with identical sensitive labels.\n\nThanks for your comment. Below we provide both the rationale analysis and empirical evidence to support prioritizing negative pairs with identical sensitive attributes in the group-acquired alignment objective.\n\n- **Rationale Analysis.** The rationale behind prioritizing the negative pairs is to mitigate the encoder’s reliance on sensitive attribute information during representation learning. When $ z _ p\\in\\mathbf{Z} _ {ig} $, both **the positive and negative samples share the same sensitive attributes as the anchor node**. Therefore, the encoder no longer considers sensitive attribute information a valuable feature for fairness learning. When $ z _ p\\in\\mathbf{Z} _ {sg} $, the **positive samples have different sensitive attributes from both the anchor and the negative samples**. If the encoder learns sensitive attribute information, the similarity between the positive samples and the anchor will decrease, while the similarity between the negative samples and the anchor will increase, which is contrary to the objective of the loss function. \n\n\n- **Empirical Evidence.** To validate this design, we performed a comparative experiment where **negative pairs were sampled solely based on differing target labels, without considering sensitive attributes** (denoted Var 1 in the following table). The results are summarized below:\n\n| Dataset | Metric |Var1|DANCE|| Dataset | Metric| Var1 | DANCE|\n|-|-|-|-|-|-|-|-|-|\n|**Pokec_z**| ACC↑|71.8|70.09||**Pokec_n**| ACC↑|67.49|66.58|\n|| ROC-AUC↑|78.16|77.42|||ROC-AUC↑|74.32|72.88|\n||△DP ↓| 5.71|3.74|||△DP ↓|1.77|0.83|\n||△EO ↓| 3.33 |2.70|||△EO ↓|1.57|0.29|\n\nFrom the result, we can find DANCE significantly outperforms Var 1 on fairness metrics. This indicates that **prioritizing negative pairs with identical sensitive attributes** plays a key role in learning representations that are both fair and robust under distribution shifts.\n\n**Reference**\n\n[1] Li Y, Wang X, Xing Y, et al. Graph fairness learning under distribution shifts, Proceedings of the ACM Web Conference 2024. 2024: 676-684.\n\nThanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "They appear to be generally correct and the intuition makes sense to me as well.", "experimental_designs_or_analyses": "They appear to be carefully designed and I do not have major complaints about the experimental designs and analyses.", "relation_to_broader_scientific_literature": "This paper is properly positioned as a part of the broader scientific literature with clarifications about the relationship between itself and other works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1 - This paper Introduces dual unbiased expansion strategies in both graph and hidden spaces to address distribution shifts.\n\n2 - The idea of group-acquired alignment explicitly focusing on fairness is interesting, particularly handling minority-sensitive groups.\n\n3 - Comprehensive framework including both adversarial modules and representation disentanglement strategies.\n\n4 - Strong empirical validation across multiple benchmark datasets showcasing clear improvements over baselines.\n\n5 - Addresses a realistic and underexplored challenge in graph fairness research by focusing on distribution shifts.\n\nWeaknesses:\n\n1 - The framework involves multiple sophisticated modules, potentially increasing the difficulty of implementation and complexity. Also, the author did not discuss the time complexity for the proposed method: how expensive it is to adopt it in practice? Generally the discussions on computational cost, scalability, and efficiency is limited.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "What are the computational overheads introduced by the proposed approach, particularly in comparison to simpler fairness-aware methods?\n\nI would be interested in the details about the rationale behind prioritizing negative pairs with identical sensitive labels in the group-acquired alignment objective. Plus, how significantly does this choice affect fairness outcomes?", "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": "IAjfNUwhzU", "reviewer": "Reviewer_fyy9", "summary": "This paper propose DANCE to improve fairness performance of GNNs under distribution shifts. DANCE addresses two key challenges: sensitive group imbalance and the trade-off between fairness and model performance. DANCE uses unbiased mixup to balance sensitive attributes, fairness-aware adversarial learning to improve robustness, and a group-acquired alignment strategy to prioritize fair representations by considering sensitive attributes. Extensive experimental results show the effectiveness of DANCE.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.\n\n> Q1. High computational cost. DANCE use multiple modules (graph expansion, adversarial learning, alignment, and disentanglement), which increase computational costs. \n\nThanks for your comment. We have included the efficiency analysis and comparison as follows. From the result, we can observe that our method has a competitive computation cost. In particular, we provide the following analysis:\n\n- **Complexity analysis.** The computing complexity of our framework mainly depends on (a) **Dual graph expansion**, (b) **Group-acquired alignment** and (c) **Representation disentanglement**. Let $N_{syn}$ be the number of synthesized nodes. Then, since logits can be obtained from the previous epoch, for (a), we need $\\mathcal{O}(N^2_{syn})$ extra time for anchor and auxiliary nodes sampling, $\\mathcal{O}(N_{syn}d)$ for feature mixup and $\\mathcal{O}(N_{syn}/N\\cdot|\\mathcal{E}|)$ for generating synthesized edges. Meanwhile, adversarial learning on synthesized data takes $\\mathcal{O}((N+N_{syn})d^2)$. For (b) and (c), the complexity for the target and sensitive encoder is $\\mathcal{O}(2L|\\mathcal{E}|d+2Nd^2)$ with $L$ layers while the view alignment takes $\\mathcal{O}(N|\\mathcal{B}|d)$ with total $|\\mathcal{B}|$ positive and negative pairs. Compared with FatraGNN [1], the additional complexity is $\\mathcal{O}({N}^2_{syn}+(N_{syn}+N|\\mathcal{B}|)d+N_{syn}/N\\cdot|\\mathcal{E}|)$, mainly from the dual graph augmentation and contrastive learning modules, which are carefully controlled in our implementation.\n\n- **Practical training overhead.** From a practical standpoint, we have provided the time complexity and training time of our DANCE to further demonstrate its computational efficiency in comparison to other baselines. The results indicate that our framework maintains a competitive computation cost compared with baselines.\n\n|Model| Params (M) |Training Time (s/epoch on Credit)|\n|-|-|-|\n|FatraGNN |0.140| 0.263 |\n|DANCE |0.536| 0.340 |\n\nIn summary,  our method has a **competitive computation cost** in comparison with the baseline. We will include the above discussion in our revised version. \n\n> Q2.  The authors do not provide case studies that illustrate why DANCE is superior than other methods. \n\nThank you for the insightful comment! We have provided **t-SNE visualizations that offer a qualitative comparison of the learned representations** between DANCE and the benchmark model (FatraGNN). These visualizations help illustrate how DANCE better achieves fair and discriminative representations.\n\nThe colors in the plots represent different combinations of sensitive attributes and target labels:\n\n- **Pink**: sensitive = 1, y = 0\n- **Green**: sensitive = 0, y = 0\n- **Grey**: sensitive = 1, y = 1\n- **Blue**: sensitive = 0, y = 1\n\n**FatraGNN [1] (Benchmark) t-SNE Results**:\n\nPokec_z: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/Fatra_pokec_z_tsne.png\n\nPokec_n: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/Fatra_pokec_n_tsne.png\n\n**DANCE  t-SNE Results**:\n\nPokec_z: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/DANCE_pokec_z_tsne.png\n\nPokec_n: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/DANCE_pokec_n_tsne.png\n\nCompared to FatraGNN, **DANCE exhibits a much clearer separation between target labels** (i.e., the blue/grey cluster vs. the pink/green cluster), **while sensitive attributes are not clustered, indicating reduced sensitive information leakage**. In contrast, the benchmark method (FatraGNN)  shows all four colors more uniformly mixed,  with no clear separation based on target labels,  suggesting entanglement of sensitive and target information.\n\nThis case study provides intuitive evidence that DANCE achieves better separation of semantic information while mitigating bias from sensitive attributes, thereby demonstrating its superiority over existing methods.\n\n**Reference**\n\n[1] Li Y, Wang X, Xing Y, et al. Graph fairness learning under distribution shifts, Proceedings of the ACM Web Conference 2024. 2024: 676-684.\n\nThanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "Graph neural networks (GNNs), fairness in machine learning, and out-of-distribution (OOD) generalization.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\n1. This paper addresses graph fairness under distribution shifts, a problem that remains largely unexplored.\n\n2. DANCE expands the training distribution in both graph structure and feature space, generating challenging yet unbiased virtual data.\n\n3. Extensive experiments demonstrate the effectiveness of DANCE\n\n4. This paper provides a theoretical analysis of the graph diffusion process, showing how it controls information propagation across different sensitive groups.\n\nWeaknesses:\n\n1. High computational cost. DANCE use multiple modules (graph expansion, adversarial learning, alignment, and disentanglement), which increase computational costs.\n\n2. The authors do not provide case studies that illustrate why DANCE is superior than other methods.", "other_comments_or_suggestions": "1. The authors should provide theoretical analysis or case studies to show why DANCE is superior than other methods.\n\n2. The authors should provide complexity analysis.", "questions_for_authors": "Please refer to the suggestions", "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:

Meta-review: This paper studies the problem of ensuring different notions of group fairness in graph neural networks (GNNs), under the potential presence of distribution shifts. The main idea is to use dual graph expansion to simulate the distribution shift, and then use fairness-aware adversarial training to ensure group fairness. The application of adversarial training is not new, even in the context of GNNs [1]. The authors are encouraged to provide a more thorough discussion of the novelty of their approach and how it compares to existing work. The main technical contribution is the idea of using dual graph expansion to generate unbiased graph data, which I also find interesting. 

Overall, the reviewers are positive about the paper, particularly the strong empirical results. Multiple reviewers have pointed out the lack of computational complexity analysis, and the authors have provided a brief response in the rebuttal. I would encourage the authors to expand the discussion on this point in the final version of the paper. 

[1].    Information obfuscation of graph neural networks, Liao et al., ICML'21
Decision: Accept (poster)