A Unified Framework for Fair Graph Generation: Theoretical Guarantees and Empirical Advances
Authors: Zichong Wang
Zhipeng Yin
Wenbin Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Fairness
Graph Generation
GNN
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Graph generation models play pivotal roles in many real-world applications, from data augmentation to privacy-preserving. Despite their deployment successes, existing approaches often exhibit fairness issues, limiting their adoption in high-risk decision-making applications. Most existing fair graph generation works are based on autoregressive models that suffer from ordering sensitivity, while primarily addressing structural bias and overlooking the critical issue of feature bias. To this end, we propose FairGEM, a novel one-shot graph generation framework designed to mitigate both graph structural bias and node feature bias simultaneously. Furthermore, our theoretical analysis establishes that FairGEM delivers substantially stronger fairness guarantees than existing models while preserving generation quality. Extensive experiments across multiple real-world datasets demonstrate that FairGEM achieves superior performance in both generation quality and fairness.

A Unified Framework for Fair Graph Generation: Theoretical Guarantees and Empirical Advances
Zichong Wang' Zhipeng Yin' Wenbin Zhang Florida International University, Miami, FL, United States {ziwang, zyin007, wenbin. zhang) &fu.. edu
Abstract
Graph generation models play pivotal roles in many real-world applications, from data augmentation to crivacyprreeervigg Despite their deployment successes, ex- isting approaches often exhibit fairness issues, limiting their adoption in high-risk decision maakin applications. Most existing fair graph generation works are based autoregressive models that suffer from ordering sensitivity, while primarily addressing structural bias and overlooking the critical issue of feature bias. To this end, we propose FairGEM, novel one-shot graph generation framework designed to mitigate both graph structural bias and node feature bias simultaneously. Fur- thermore, our theoretical analysis establishes that FairGEM delivers substantially stronger fairness guarantees than existing models while preserving generation qual- ity. Extensive experiments across multiple real-world datasets demonstrate that FairGEM achieves superior performance in both generation quality and fairness.
Introduction
Graph Icarning has become increasingly important due to the ubiquity of graph-structure data across various domains, such social networks (T). recommendation systems [2], and financial markets [3]. Among the important tasks in graph learning, graph generation stands out for its ability create synthetic graph data that serves crucial purposes such data augmentation [4) anomaly detection (5), and enabling grivacy-preerrving data sharing 6 Essentially, graph generation models aim capture the underlying data distribution and produce novel graph samples that maintain the statistical properties of the original data 77]. For instance, banks may employ graph generation models construct synthetic applicant interaction networks based historical loan approval data, allowing them to share insights with third-party testing agencies without exposing sensitive information [8].
Despite their significant success, existing graph generation models often neglect the crucial issue of fairness, which limits their adoption in high-risk seccision-maknng scenarios, such as healthcare [2], credit scoring [10], and crime prediction [IΤ) where biased graph generation amplify social inequities. Returning to the banking example, the generated graphs may dispropor- tionately create more connections among individuals from the same sensitive subgroup, further segregating the representations nodes belonging to different sensitive subgroups. This leads to an over-association of downstream tasks with sensitive attributes, thereby reinforcing biases and amplifying discrimination in high-risk decisions (e.g., loan decision), raising serious ethical issues.
perpetuate or
There has thus been growing interest in exploring faimess in graph generation tasks, with preliminary efforts primarily focused on mitigating structural bias in graphs [6 aim to address disparities in connection patterns across sensitive subgroups. However, they largely overlook feature bias, disparities that emerge when the generated node features differ systematically across subgroups. For example, the generated graph might show male nodes with higher incomes
12
I3
14 15). These works
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

than female nodes, leading to biased downstream applications where models trained on this synthetic data learn to expect higher incomes from male applicants. Furthermore, existing fair graph generation models typically belong to autoregressive models that construct graphs incrementally [14]. These autoregressive models exhibit inherent limitations, including ordering sensitivity, where the generated graphs heavily depend on arbitrary node orderings, and difficulty capturing comprehensive global structural patterns efficiently [[6].
To address these drawbacks, this paper explores fair one-shot graph generation models that treat graph components holistically, generating entire graphs simultaneously with inherent node permutation invariance, enabling better representation of global graph structures [7], while tackling both structural and feature biases. To achieve this, several challenges need to be addressed: i) Difficulty in preserving natural attribute differences while removing unfair disparities. When generating node features, certain attributes should naturally vary across sensitive groups, while others should not show group- based disparities. The fundamental challenge lies in developing methods that can reliably distinguish between these two types of features from the data. Without robust techniques for this identification, one-shot generation models will either inappropriately flatten natural variations or perpetuate unfair disparities, compromising either data realism or fairness. ii) Difficulty in coordinating fairness across interconnected graph components. One-shot models generate node features and structural patterns simultaneously, creating complex dependencies. Without coordinated faimesss mechanisms, addressing bias in one component can inadvertently exacerbate bias in another. This interdependence can lead to models that appear fair in isolated metrics but still produce systematically biased results when evaluated holistically. (iii) Difficulty in formulating and proving theoretical guarantees. In one-shot graph generation, the entire structure and node features emerge from random noise in single pass, which requires any faimess constraint to be incorporated from the outset and remain valid through the entire noise-to-grapp transformation. As a result, proving formal fairness bounds under such one-shot framework requires carefully designed regularizers and rigorous analysis that can guarantee fairness in the final generated graph.
To tackle the above challenges, this paper introduces a novel framework, Fair Graph gEnerative Modeling (FairGEM), which achieves fair graph generation through specialized regularization of both structural and feature components in spectral diffusion models. To the best of our knowledge, this is the first work that theoretically grounds fair graph generation to simultaneously address both structural and feature biases while avoiding node ordering dependencies. Specifically, we mitigate graph structural bias by developing a fairness regularizer that quantifies and minimizes discrepancies between intra-group and inter-group edge reconstructions, while addressing node feature bias through a disentanglemer wonnggleeet-guieeddd strategy and a fairness regularizer that selectively enforces fairness on cunsitive-irrelevaa features. Furthermore, we establish theoretical guarantees for our framework, providing upper bounds on bias propagation and demonstrating how our method directly improves fairness downstream tasks. Our main contributions can be summarized as follows:
Theoretical analysis. We establish the first theoretical foundation for fairness- graph generation that works without sequential node ordering constraints. Our analysis provides upper bounds on both structural and feature bias propagation, demonstrating how these biases impact downstream task disparities.
Novel Framework. We establish a general framework for fair graph generation through FairGEM, which introduces two specialized regularizers: that minimizes discrepancies between intra-group and inter-group edge reconstructions, and another that disentangles and selectively regularizes sensitive-unrelated features.
Extensive Experiment Evaluation. We conduct extensive experiments to evaluate by comparing it with the state-of-the- methods across four real-world datasets, achieving a significant improvement in fairness metries while maintaining generation quality.
2
Related Works
Graph Generation Models. Generating synthetic graphs has been extensively explored through deep generative models, categorized mainly into autoregressive and one-shot methods 17]. Specifically,
autoregressive methods, including those based on recurrent neural networks [88 19. and reinforce-
ment learning (20 21, construct graphs incrementally by adding nodes and edges sequence. While these approaches can capture complex structural patterns, they suffer from inherent limitations such

---

as sensitivity to node ordering and difficulty in modeling global graph properties efficiently. To
address these limitations, one-shot graph generative models construct edges simultaneously, typically
employing Variational Autoencoders 22
23 24 Generative Adversarial Networks [25] 26 27
and spectral diffusion models 28 29], offering advantages such as node permutation invariance and
holistic representation of graph structures. Despite these advances in synthetic graph generation quality across both paradigms, fairness concerns remain largely unexplored in the literature, which severely limits their applicability in high-risk decision-make scenarios, thus creating urgent need to develop fairer graph generation methods.
Fairness- aware Graph Generation. There is growing effort in the research community to develop
36 37], however, most existing fairness-awe aware methods primarily focus on classification tasks, leaving the faimess chal-
fair graph learning models addressing biases in applications [30] 31 [3] [3 34 35]
lenges in graph generation largely unexplored [38]. Recently, a small number of works [2 39 40)
have begun to investigate fairness specifically within graph generation, primarily adopting autoregres-
sive methods for tasks such as fair link prediction and fair structural generation. Fair link prediction
methods aim at unbiased inference of edges between nodes; for instance, FAIRLP [3] adjusts the training graph to balance intra-group and inter-group link distributions, enhancing representation fairness. Fair graph structural generation methods, on the other hand, address fairness at the struc- tural level by reducing distributional disparities between generated graphs and the original graph across demographic subgroups. For instance, FairGen [4]] introduces parity constraints minimize subgroup reconstruction differences. However, these existing approaches focus on structural fairness, neglecting biases in node feature generation, highlighting the need for comprehensive fairness solu- tions in synthetic graph generation tasks. In addition, these autoregressive models inherently suffer from ordering sensitivity, meaning generated outcomes can vary significantly with different node orderings, inadvertently causing biases
In contrast to existing work, this paper proposes a fair one-shot graph generation model that addresses both graph structural bias and feature bias, with its design informed by theoretical analysis. By leveraging the holistic nature of one-shot generation, our approach can simultaneously optimize fairness without the ordering sensitivity that plagues sequential methods. Additionally, our bias mitigation approach is flexible, allowing it to be applied in training both link prediction models and generative models to create fair synthetic graphs.
Notation
Given an attributed graph G (V,E,)) where V= {1i, ,,, Un) represents the set of nodes and & S v(,, Vs 1J E V} denotes the set of undirected edges. The node feature information associated with the graph represented by a feature matrix X E Raad where each node U corresponds to a d-dimensional feature vector
E Rdd Graph connectivity is captured by the adjacency matrix A {0, 13 where Ai, = indicates that nodes v and V are connected by an edge, and A., 0 otherwise. We assume each node is associated with a binary sensitive attribute st, represented by the vector S E (0, 1|nx1, where denotes the sensitive attribute for node u, The node set can thus be partitioned into two groups based on these sensitive attributes: the deprived (e.g.,
group S₂; = {ir E V = 0} (e.g., female), and the favored group Sn [uy E V male). Additionally, each node i; carries a binary ground-truth label yı E {0. 1} representing the outcome of interest, such as approval (y:= = 1) or rejection (y,- 0). Predicted outcomes from the model are indicated as '..
4 Methodology
This section introduces FairGEM, a novel framework designed to achieve fair graph generation by mitigating biases that emerge during the diffusion process. Specifically, Section 4.1 we review
the standard score- based graph diffusion model and identify two key sources of bias: structural bias in graph structural generation and feature bias in node feature generation. Section 4.2 presents our method for addressing graph structural bias by introducing a fair graph structure generation regularizer. Section (.3tionn433 describss our approach for tackling node feature bias using a disentanglement- guided method, which separates sensitive-related from sensitive-irrelevant features, enabling targeted fairness regularization. addition, we provide theoretical insights and guarantees regarding the effectiveness of our approach in mitigating bias in graph generation.
3

---

4.1 Inspection Biases in Graph Generation Process
We begin by examining the root causes of bias graph generation, establishing a clear foundation for developing fair graph generative models. Understanding these causes requires a closer look at how such models are typically constructed, most aim to learn the joint distribution of node features (X) and graph structure (A). To effectively capture this joint distribution, recent work has increasingly adopted score-based diffusion modeling, a powerful strategy that transforms complex data distributions into simpler ones through the controlled addition of noise [4]] Specifically, diffusion models leverage stochastic differential equations (SDEs) to systematically perturb the original data distribution over continuous timesteps until it approximates a simple prior distribution, then learn to reverse this process. Mathematically, this graph diffusion process can be expressed as:
dx. = (Xe, l)dl + dA. = PA aA
where the drift functions (- t) and (-,t) control the deterministic transformations of node features and graph structures, respectively. X, and A, denote the random states of node features and the adjacency matrix at time t. The stochastic terms governed by ox,t and ΛA, determine the intensity of random noise introduced via Brownian motions (Bx)) and (B-A).
To reverse this diffusion process and generate realistic graph samples from noisy data, score-based models estimate the score function, which represents the gradient of the log probability density at various noise levels. This function is approximated using neural network trained via the denoising score matching objective:
{ (x( A EG-Uni( G X, A.) - V log (X, [X)]] LA (Ø) E E X,,, Ar) V log (A, Ao)
(2)
where G Uni represents uniform sampling from the training set; t (1,0, 1) indicates sampling a timestep from [0, 1]; (X, (x)) and (A,(Ao) denote noisy versions at time t; Zg and as are neural networks predicting conditional scores; VX VXllog logp(X,((o)) and V log ((,, (A)) are the true conditional scores; and || is the Frobenius norm.
However, this diffusion- based generation inherently propagates and amplifies existing biases present in the original data distributions 42 Specifically. in the forward SDE for A,, biased patterns such as denser connections among nodes sharing sensitive attributes (e.g., gender) remain largely intact because the noise addition step (ax,t, aA,)) does not alter the relative densities of these structures, which continue dominate the evolving distribution. Similarly, the SDE for X,, feature biases, manifested as distributional disparities across sensitive groups, persist through the forward diffusion stage, since added noise minimally shifts those underlying imbalances. Subsequently, during the reverse diffusion process, the score function V log p( Xt, Ar) (learned via mean-squared error minimization) directs generated samples toward regions of higher data density. Because these regions correspond precisely to biased modes, the generative model inherently intensifies structural and feature biases. In summary, the optimization process the score function, typically guided by mean- -quared error loss, inherently prioritizes more frequent and dominant biased patterns in the training data. This weighting implicitly assigns greater importance and thus greater accuracy to these biased modes. In turn, this amplifies existing disparities, with minority groups and less frequent patterns disproportionately neglected.
4.2 Mitigation Graph Structural Bias in Graph Generation Process
Guided by the bias analysis, two fairness regularizers are proposed to explicitly address biases in graph structure and node features. The first, structural faimess regularizer, is designed to mitigate structural bias. It does so by quantifying the discrepancy between reconstruction errors on intra-group versus inter-group edges, as formally defined in Definition 4.1
Definition 4.1 (Graph Structure Information Generation Bias) Given G with and S, the bias in graph structure information generation is defined by the disparity in how generative model reconstructs connections beiween nodes from the same subgroup defined by sensitive attrbmute versus connections between nodes from different subgroups. Specific spectral diffusion framework, where

---

fixed initial eigenvector matrix Un guides the evolution of the adjacency matrix as A, U through a Gaussian process, this bias at diffusion time can be formally quantified as:
S (Aee (Eraroo (De) Einter (Nt))²
where Emnrra (Ag) and Eineer (Ne) represent the reconstruction errors for intra-group and inter-group edges, respectively:
Fintr(Ae)) = IP intra @ (A, - P) (An) P Pinter ① (A, -A)
(4)
where A represents the reconstructed adjaceney matrix time denotes the Hadamard (element- wise) product, and P intro and P Piner are binary masks identifying edges between nodes with the same and different sensitive attributes.
Building on Definition 4.1 FairGEM proceeds three steps. First, the emergence of disparities in graph structural information during generation is analyzed, and upper bound is established to understand their propagation. Second, it is proven that these structural differences inherently introduce bias into downstream tasks, demonstrating that reducing disparities in structural information within generated graphs improves fairness outcomes. Finally, guided by these thcoretical insights, a fairness regularizer is proposed mitigate differences between intra-group and inter-group edges, effectively addressing graph structural bias.
We begin with the first step of analyzing how graph structural information bias manifests and propagates during the generation process. Theorem 4.2 establishes an upper bound on the graph structural bias that emerges in graph generation (proof (A)
The expected gruph structural bias that emerges during the graph generation process, measured by the disparity adjacency patterns, can be upper bounded by:
Theorem 4,2
E EI IP= S (1731 K)E(Ø) (1+nK So expp exp nK St 22 dt
(5)
where M is a conslant determined by various factors (e.g.. noise schedule, model architecture, and gradient bounds). Meanwhile, X serves as a time-accumulated noise or variance factor, capturing how stochastic perturbations build up over the diffusion process.
Building on Theorem we next analyze how graph structural bias influences the downstream task. Theorem 4.3 demonstrates that by minimizing graph structural bias, we can effectively reduce group disparity the downstream task (e.g., node classification), with detailed proof in Appendix B
Theorem 4.3 The structural bias introduced during the graph generation process propagates downstream tasks, and can be upper bounded by:
h S --
1149 -12ll +0
Σ
1010-1), bg-1))
N PIEES
F.EES
(6)
2
Σ KOLS-..n 1 PESE
-1 - + (1-
CIAA L Bapee
NoN,
where L is the Lipschitz constant of the activation function, and C' is constant. In addition, denotes the mean representation of a subgroup of nodes.
Based on Theorem 4.3 we impose an explicit fairness regularizer on the spectral diffusion process to reduce structural bias. Specifically. we combine & with the standard score-matching objective to obtain the fair graph structural generation loss:
Lst
Lycore
+ Eg suuu (At)]
(7)
During reverse-time sampling, modify the drift term of the SDE by adding VA (
5

---

dA. (- ( + Vf @ Patmall (R.) di + P.dW;
(8)
By doing so, each reverse-time step not only follows the learned score to move toward high-density regions but also corrects for structural bias by minimizing the discrepancy between intra-group and inter-group edges.
4.3 Mitigation Feature Bias in Graph Generation Process
FairGEM now proceeds to address feature bias, an important yet largely overlooked aspect in existing fair generative models. Unlike structural bias, however, feature bias demands more nuanced measurement. Specifically, existing methods typically directly measure the differences between all generated node features in deprived and favored groups 43 While this approach captures the overall differences between subgroups, it ignores the inherent differences of sensitive attributes, leading to downgrade in generation quality. In other words, fair node feature generation should not erase the inherent differences of sensitive attributes, such as the physiological differences between males and females. To this end, we aim disentangle node features into sensitive-related features Xs and sensitive-irrelevant features Xg. This separation enables more nuanced approach: minimizing the disparities in the sensitive-irrelevan features (Xs), while maintaining appropriate differences the sensitive-related features (Xs), thereby reducing bias while preserving essential group characteristics.
We formalize this concept in Definition 4.4
Definition 4.4 (Node Feature Generation Bias) Given G with X and S, we define the node feature generation bias as the distributional discrepancy between subgroups over the sensifive-irrelevant features dimensions. Mathematically, the discrepancy between Xg, of node on during the generative process is measured using Maximum Mean Discrepancy (MMD) [44] as follows:
XgD0 WegT En,yyEVs, AxS.. Xs.) + 1ES Ennogevs, 1(Xg. Xs.) VegliVsy Eneve,
H Xs.))
nyEVa,
(9)
where k(,,-) ) is desitive-definte kernel (e.g., RBF). A larger MMD value indicates that the generated distributions of unrelated features differ more between subgroups, implying a higher level of node feature generation bias.
Building upon this foundation, we introduce disentangglemet-guuiee diffusion strategy to effec- tively address biases in node feature generation. Our proposed method employs a generator-refiner framework wherein we initially leverage Variational Autoencoder (VAE) to separate node features into two distinct components: sensitive-related (Xs) and sensitive-irreleve separation stage helps identify the feature dimensions that should remain unaffected by sensitive information, establishing the groundwork for fair node feature generation. To operationalize this, introduce two latent variables, Us and Ug. representing sensitive-related and mussiivv-iirelevaan information, respectively. Mathematically, we express this probabilistic framework as follows:
(Xg) attributes. This
P(S, Xss Y) = (UU))() U(X S,S, S.
(10)
P(A | S.U, P(X P( U,U
where P(Us) and P(U2) denote prior distributions typically modeled as standard normal distribu- tions. The terms P(Xs A. S, Us) and P(X3 A, Uz) are responsible for accurately reconstructing sensitive-related and sensitive-irrelate node features, respectively.
To ensure effective disentanglement, we need enforce independence between the latent variables Us and Uz. For this purpose, we adopt the Seebfeeld-Geeeeinn tion (45), which generalizes Pearson correlation to capture any non-linear relationship between random variables. Our optimization approach employs an adversarial training mechanism, illustrated in Figure I During training, the encoder-decoder parameters are iteratively updated via gradient descent to minimize both the reconstruction loss and the latent dependence, while adversarial net- works parameterized by w/, and W/2 work in opposition through gradient ascent to detect and amplify remaining latent dependencies. This dynamic interplay of minimization and maximization ensures
(HGR) maximal correla-

---

T Height
Sensitive-ellaee (Xş)
& Gender
O0 Weight
O Height Gender
Us
Sensitive-irrleeant (Xg)
00 Weight
Encoder
Us
Education
Income
Income
Xy
XT
Education
p(x
X
Xos
Figure 1: The overview of FairGEM.
thorough and effective disentanglement of sensitive and insensitive feature representations. Finally, we optimize the VAE parameters by maximizing the evidence lower bound (ELBO), formulated as:
log X(s 2 B U log Us) + log P(A) S)
P(Xs Us. 4) log P(X, 4g log P(Y Us. Uy.
Q(Us Xs) Q(Us 5, A. + log P(Us) + log P(Uz)
+ A.D
(11)
where HGR-based penalization term (Ln) is formally defined as: ((
Ln
suP " (Us)))())3(( where fi and fz are measurable functions with positive and finite variance and sup(-) denotes supremum.
Armed with disentangled X5 and Xg. we apply a two-stage generator-refiner approach to ensure fairness in node features generation. The VAE's outputs (X
serve as the initial signals for diffusion process that further refines these features. We then enforce the proposed fair node feature generation regularizer to minimize distributional discrepancies between sensitive subgroups in the sensitive-irrelevant features.
X 5
As we introduced in Definition 4.4 we formalize our fair node feature generation regularizer as:
Piest.nd 55,))
X
A(X 3. Xz.1.)
Vsp
K(X5,1. Xz.i))
Vs 12
(12)
Masty
Vip liVe,
VEVV eyEVs
where X 5,1 denotes the sensitive-irreles features for node at time t.
We integrate this fairness regularizer into diffusion refiner that evolves the features from time down to 0. Let (X₂) represent the set of node feature vectors under noise. The modified reverse-time SDE that incorporates our fairness constraint can be written as:
ax. (xx))..)) x X. + ox Vx Diat (x di + ox. cB
(13)
where =0(+) approximates Vx log
(0) and the gradient term VX ns (X, (,s
actively pushes the sensitive-irrelevant features toward smaller cross-group discrepancies.

---

To learn 2e and consistently enforce faimess on X3. we augment the standard mcore-matching objective:
modde (0) (x - V Vlogpoo(X, xi)]l - E feest, (X,,)]
(14)
where & is a hyperparameter that balances the contribution the fairness constraint. During reverse diffusion, each step updates node features with both the learned score and the fairesss gradient, gradually correcting the unrelated dimensions toward unbiased distributions across subgroups.
In summary, our approach to fair node feature generation proceeds through two complementary stages. First, in the Generator Stage, the VAE disentangles features by sampling latent codes to
reconstruct an initial partition X [0)
x
ensuring legitimate group-specific variation in Xg with S
minimal entanglement in gg. Next, during the Refiner Stage, our diffusion model corrupts X()) with noise and learns to reverse this process while imposing the MMD-based fairness penalty on X5,r*
This designed process yields final denoised ( that maintains meaningful differences in sensitive features yet achieves unbiased distributions in unrelated features. By leveraging disentangled VAE representations preserve necessary group distinctions while using fairness-awan diffusion refiner to align unrelated node features across subgroups, our approach enables achieving fair node feature generation while maintaining better generation quality.
Experiments
5.1 Experiment Setting
We conduct our experiments using four real-world datasets: Cora and Citeseer [46]: These widely-used citation network datasets comprise academic papers represented as nodes. Edges indicate citation relationships between papers. Each node's 's feature vector is generated using bag-of-words model applied to paper keywords, and the labels denote distinct research areas (topics). Photo [47]: This dataset is subset derived from the Amazon co-purchase network, where nodes represent products and edges represent frequent co-purchasing relationships. Node features consist of bag- of-words vectors extracted from user- seer-genertted product reviews. The labels correspond to specific product categories such as cameras, accessories, and lenses. Pokec-z [48]: This dataset originates from Pokec, prominent social networking platform in Slovakia. Nodes represent individual users characterized by detailed attributes including gender, age, geographical location, and personal interests. Edges represent friendship relations among users. The dataset is widely utilized for studying social network dynamics, including community detection and user classification tasks. We 80% of the graphs in each dataset for training and 20% for testing. Detailed statistical summaries of these datasets are available in Table [
Datasets.
Table I: Summary of the datasets used in the experiments.
Dataset
# Nodes
# Edges
# Features
Avgrage Degree
Sensitive Attribute
Cora
2,708
10,556
1,433
3.89
Topic
Citeseer
3,327
9,228
3,703
2.77
Topic
Photo
7,650
238,163
745
31.13
Product Categories
pokco-z 67.797
882,765
59
10
Region
Baselines. We compare FairGEM with several state-of-the-ar baseline methods across multiple categories: GRAPHARM [49]: An autoregressive diffusion--ased model that sequentially masks nodes and edges, employing a learned node-ordering strategy for efficient and accurate discrete graph generation. GSDM [9]: A framework for graph generation based on spectral diffusion. Using low-rank stochastic differential equations (SDEs) restricted to the space of eigenvalues of the adjacency matrix, the quality of graph topology generation is improved while reducing the computational effort. FairAdj [50]: Adjusts the adjacency matrix to achieve dyadic fairness by reducing dependency between link predictions and node sensitive attributes, balancing fairness with predictive accuracy. FG2 AN [39]: Utilizes adversarial training to jointly optimize node-level and structural fairness, incorporating tailored metrics and strategies to efficiently handle multiple biases
8

---

during graph generation. FairGen [40] guidance with fairness constraints, leveraging self-paced learning to effectively model protected and u groups from limited labeled data. Fair [6]: Employs inffusion-based techniques with novel fairness regularizer to mitigate structural bias, effectively preserving fairness in synthetic graph creation without compromising sensitive data. For fair and consistent comparison, we adapt each baseline method using the original implementations provided by their respective authors. Hyperparameters for these baselines are set according to recommendations from their original papers.
A deep generative framework that combines label-driven
Evaluation Metrics. We evaluated FairGEM in two perspectives: i) Quality of Generated Graphs: Building on [4], we employ Maximum Mean Discrepancy (MMD) to compare generated and original graphs in terms of degree distributions (DD), clustering coefficients (Clus), and node features (NFea), with smaller MMD sigmifying closer fidelity. To further evaluate structural fairness, we introduce three metrics: Fair Degree Distribution (Fair-DD)) Fair Clustering Coefficient (Fair-Clus), and Fair Node Feature (Fair-NFea), each capturing cross-subgroup disparities. These metrics take the form f (Gs. ( f Gs, ), where Gs. and 9s. refer to the induced subgraphs of the real and generated data on subgroup S,, and [()) denotes the MMD calculated function, with small value reflecting a fairer outcomes. ii) Node Classification Performance: We measure the utility in node classification tasks using Aceuracy and Fl scores, while quantifying the fairness of these results with ADP 51] and AEO [22 where smaller values indicate fairer outcomes.
5.2 Experiment Results
Quality of generated graphs. SableeSsmmariii the generation performance of all methods across each dataset, evaluating models in terms of both quality and faimess, with additional results included in Appendix C.2 As the results indicate, FairGEM demonstrates competitive or superior generation quality compared to the baseline approaches, consistently showing smaller discrepancies in key graph statistics such as degree distributions and clustering coefficients. At the same time, it substantially improves faimess metries, suggesting that its generated node features and structural patterns do not disproportionately favor any subgroup. The strong performance can be attributed to two key factors. i) By disentangling node features into sensitive-related and sensitive-unrelated components, FairGEM preserves meaningful group-specific differences without introducing unintended biases. ii) FairGEM incorporates explicit fairness regularizer within the generative diffusion process, actively penalizing biases in sensitive subpopulations. Hence, FairGEM not only produces realistic and coherent graph samples but also ensures equitable treatment of different groups
Table 2: Graph generation results on Cora and Pokee-z datasets.
Cora
Pokeo-z
Method
DD
Clus
NTea
Fair. DD
Fair. Fair-Clus
NFea
DD
Clus
NFea
Fair-DD
Fair Clus
Fair-NTea
GRAPHARM
0,238
0.135
0.312
0.077
0.083
0.049
0.348
0.150
0.253
0.078
0.067
0,038
GSDM
0.211
0.128
0.280
0.064
0.069
0.051
0.331
0.142
0.231
0.073
0,060
0,031
FairAdj
0.258
0.157
0.321
0.035
0.013
0,032
0.358
0.168
0.281
0.055
0.039
0.023
FG AN
0.263
0.1
0.335
0.038
0.047
0.036
0.374
0.178
0.295
0.059
0.046
0.028
FairGen
0.275
0.173
0.348
0.027
0.045
0.031
0.383
0.185
0.311
0.053
0.038
0.037
FairWire
0.259
0.161
0.332
0.031
0.013
0.038
0.370
0.170
0.281
0.015
0.032
0.031
FairGEM
0.233
142
0.307
0.020
0.035
0.019
0.357
0.161
0.250
0.040
0.023
0.017
Downstream task performance evaluation. To evaluate the impact of our graph generative model on downstream tasks, we evaluated its performance and faimnsss on node classification using generated graphs. We conducted experiments on four datasets, with detailed results for Cora and Citeseer presented in Table 3 and the remaining results included in the Appendix C.2 due space constraints. For each dataset, we trained a standard GCN model [53] on graphs generated by different methods and assessed both accuracy and fairness metrics. All experiments were repeated five times with the average results reported. The results demonstrate that graphs generated by FairGEM consistently enhance both the accuracy and fairness of node classification outcomes compared to other graph generation model baselines. For instance, on the Cora dataset, FairGEM generated graphs achieved a 21. 1.% improvement in App, while maintaining comparable accuracy to the original graph. This improvement can be attributed to FairGEM's comprehensive approach in mitigating both graph structural and feature biases during the graph generation process, effectively limiting the propagation of these biases into downstream tasks.

---

Table 3: Node classification results on Cora and Pokec-z datasets.
Cora
Pokec-a
Method
(1c
Fl-scoce (96)
App (96)
Ago (%)
Acc (98)
Fl-score (%)
Apr (98)
Ago
Osiginal-GCN
82.43 0.34
84.40
3.60
27.01
25.21
76.31 1.34
68.47 1:28
20.11 1.67
0.58
GRAPHARM-GON
81.03 = 0.23
62,70
2.31
25.21 1.38
21.31 1.43
73.25
2.01
65.21 1:211:1161
16.98
1.21
18.64 1.36
GSDM-GON
81.31=
83.91
25.47
23.78
0.77
76.88
0.79
67.71
19.58
FairAdj-GNN
77.77
78.32 1.88
17.13 6.36
13.06 1: 2.24
70.03 1: 1.50
60:32:1:::25
14.25 :: 1.51
15.48
FGAAN-GON
78 10 0.81
18.88
18.66
14.05
71,82
60:48
16.16 1:27
16.35
FaiGGm-OCN
79.54
1.56
2.16 80.54
14.16
0.89
13:35
1.24
73.43
1.77
63.71
12.11 =: 1.19
12.81 1: 1.54
FaiWWre-GGN
78.21
79.67
14.76
13.65
0.51
74.09
2.10
RarGEM-GCN
79.75 0.98
80.36 1.16
11.71
1,24
10:15
1.07
75.25 1.81
65.39
9.23 0.59 11.46 1,12
Ablation study. We conduct ablation studies to gain insights into the effect of each faireess regularizer in FairGEM on improving fairness and graph generation quality. Specifically, create three ablated versions: 1) FairGEM-WS WS removes the fair graph structure regularizer, 2) FairGEM- WF removes the fair node feature regularizer, and 3) FairGEM-WD removes the disentanglement component and directly applies fairness constraints to all node features indiscriminately. Figure presents ablation results across the Cora and Pokec-z datasets, with additional results included in Appendix C.2 revealing several key findings. First, compared to FairGEM and TairGEM-WS, FarGGEM-WD shows decreased generation quality because applying fairness constraints to all node features leads to unrealistic consistency, thereby reducing generation quality, Second, FairGEM-WS exhibits stronger intra-group connectivity compared to other models, highlighting the critical role of fair graph structure regularizer in reducing graph structural bias. Third, FaiGGEM-WT shows only slightly improved node feature faimnss compared to FairGEM- indicating that foreing consistency across all features may introduce additional bias that counteracts fairness improvements. Finally, the full FairGEM model consistently outperforms all ablated versions in terms of fairness metrics, validating the necessity and complementarity of each component in our design.
Cora
Pakec-z
0.45
0.45
0.30
0.30
0.25
0.25
0.15
0.15
0.10
0.10
0.05
DD
Clus
NFea
FDir-DD
Fair-Clus Fair-NFea
D0
Clus
NFea
FainDD
Rain-Clus Fair-NFea
FairGEM
FairGEM-WS
FairGEM-WD
FairGEM-WF
Figure 2: Ablation study results for FairGEM, GSSSG FairGEM-WD and FairGEM-WF in Cora and Pokec-z datasets.
6 Conclusion
Generating synthetic graphs that reflect real-world structural properties has emerged as a promising solution for scalability and privacy needs in real-world networks. However, fairness remains largely unexplored in graph generation models. To bridge this gap, this paper proposes FairGEM, a one-shot generative framework designed to mitigate both structural and feature-level biases. By departing from the autoregressive model that suffers from ordering sensitivities, FairGEM transforms random noise directly into a final, bias-corrected graph, avoiding the pitfalls of node or edge ordering dependencies. FairGEM incorporates a theoretically grounded faimess regularizer into the diffusion process, effectively identifying and reducing real bias factors. Comprehensive experiments on real datasets confirm that FairGEM outperforms state-of-the-are baselines, offering superior bias mitigation without compromising generative quality. These results establish a solid foundation for future work one-shot fair graph generation.
10

---

Acknowledgements
This work supported in part by the National Science Foundation (NSF) under Grant No. 2404039.
References
[1] Alex Davies and Nirav Ajmeri. Realistic synthetic social networks with graph neural networks. arXiv preprint arXiv:22/2.07843, 2022.
[2] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: a survey. ACM Computing Surveys, 55(5):1-37, 2022.
[3] Si Zhang, Dawei Zhou, Mehmet Yigit Yildirim, Scott Alcorn, Jingrui He, Hasan Davulcu, and Hanghang Tong. Hidden: hierarchical dense subgraph detection with application to financial fraud detection. In Proceedings of the 2017 SIAM international conference on data mining, pages 570- 578. SIAM, 2017.
[4] Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1):2-es, 2006.
[5] Leman Akoglu, Mary McGlohon, and Christos Faloutsos. Rum: Laws and a recursive generator for weighted time-evolving graphs. In 2008 Eighth IEEE International Conference Data Mining, pages 701-706. IEEE, 2008.
[6] O Deniz Kose and Yanning Shen. ar arXiv:2402.03383 2024.
Fairwire: Fair graph generation. arXiv preprint
[7] Kushagra Pandey, Avideep Mukherjee, Piyush Rai, and Abhishek Kumar. Diffusevae: Effi cient, controllable and high-fidelity generation from low-dimensional latents. arXiv preprini arXiv:2201.00300 2022.
[8] Tucker Balch, Vamsi Potluru, Deepak Paramanand, and Manuela Veloso. Six levels of privacy:
A framework for financial synthetic data. arXiv preprint 2rXiv:2403.14724, 2024.
[9] Hao Yu, Xu Sun, Wei Deng Solvang, and Xu Zhao. Reverse logistics network design for effective management of medical waste in epidemic outbreaks: Insights from the coronavirus disease 2019 (covid-19) outbreak in wuhan (china). International journal of environmental research and public health, 17(5):1770, 2020.
[10] Valentina Shumovskaia, Kirill Fedyanin, Ivan Sukharev, Dmitry Berestnev, and Maxim Panov. Linking bank clients using graph neural networks powered by rich transactional data: Extended abstract. 2020 JEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pages 787-788, 2020.
[11] Chenyu Wang, Zongyu Lin, Xiaochen Yang, Jiao Sun, Mingxuan Yue, and Cyrus Shahabi. Hagen: Homophily-awee aware graph convolutional recurrent network for crime forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4193-4200, 2022.
[12] Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. 2019.
[13] Yanying Li, Xiuling Wang. Yue Ning, and Hui Wang. Fairlp: Towards fair link prediction on social network graphs In Proceedings of the international AAAI conference web and social media, volume 16, pages 028-639,200 2022.
[14] Zichong Wang and Wenbin Zhang. Fdgen: A fairness- aware graph generation model. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Pro- ceedings of Machine Learning Research, pages 65412-65428, PMLR, 13-19 Jul 2025.
[15] Zichong Wang, Zhipeng Yin, Roland H. Yap, and Wenbin Zhang. Ai fairness beyond complete demographies: Current achievements and future directions. In Proceedings of the 27th European Conference on Artificial Intelligence, volume 413 of Frontiers Artificial Intelligence and Applications, pages 975-984, IOS Press, 2025.
11

---

[16] Xiaojie Guo and Liang Zhao. A systematic survey on deep generative models for graph generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):5370-5390, 2022.
[17] Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. In Learming on Graphs Conference, pages 47-1 PMLR, 2022.
[18) Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International conference on machine learning, pages 2312-2312. PMLR, 2020.
[19] Xiaojie Guo, Yuanqi Du, and Liang Zhao. Deep generative models for spatial networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 505-515, 2021.
[20] Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. Advances in neural information processing systems, 31, 2018.
[21] Chengyi Liu, Wenqi Fan, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: Methods and applications. arXiv preprint arXiv:2302.02591, 2023.
[22] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning- 2018: 27th International Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pages 412-422. Springer, 2018.
[23] Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Gareett, and Yixin Chen. D-vae: A variational autoencoder for directed acyclic graphs. Advances in neural information processing systems, 32, 2019.
[24] Jia Li, Jianwei Yu, Jiajin Li, Honglei Zhang, Kangfei Zhao, Yu Rong. Hong Cheng, and Junzhou Huang. Dirichlet graph variational autoencoder. Advances in Neural Information Processing Systems, 33:5274-5283, 2020.
[25] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint 188.v:1805. 2018.
[26] Eukasz Maziarka, Agnieszka Pocha, Jan Kaczmarczyk, Krzysztof Rataj, Tomasz Danel, and Michat Warchol. Mol-cyclegan: a generative model for molecular optimization. Journal of Cheminformatics, 12(1):2, 2020.
[27] Pengda Wang, Zhaowei Liu, Zhanyu Wang, Zongxing Zhao, Dong Yang, and Weiqing Yan. Graph generative adversarial networks with evolutionary algorithm. Applied Soft Computing. page 111981, 2024.
[28] Angus Phillips, Thomas Seror, Michael Hutchinson, Valentin De Bortoli, Amaud Doucet, and Emile Mathieu. Spectral diffusion processes. arXiv preprint arXiv:2209. 2.n.:2299..41.5. 2022.
[29] Tianze Luo, Zhanfeng Mo, and Sinno Jialin Pan. Fast graph generation via spectral diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(5):3496-3500 2023.
[30] Guixian Zhang, Debo Cheng, Guan Yuan, and Shichao Zhang. Learning fair representations via rebalancing graph structure. Information Processing & Managemeni, 61(1):00357, 2024.
[31] Yuchang Zhu, Jintang Li, Yatao Bian, Zibin Zheng, and Liang Chen. One fits all: Learning fair graph neural networks for various sensitive attributes. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4688-4699, 2024.
[32] Zichong Wang, Zhibo Chu, Thang Viet Doan, Shaowei Wang, Yongkai Wu, Vasile Palade, and Wenbin Zhang. Fair graph u-net: A fair graph learning framework integrating group and individual awareness. In proceedings of the AAAI conference on artificial intelligence, volume 39, pages 28485-28495 2025.
12

---

[33] Zichong Wang, Fang Liu, Shimei Pan, Jun Liu, Fahad Saeed, Meikang Qiu, and Wenbin Zhang. fairgnn-wod: Fair graph learning without demographics. In Proceedings of the Thirty-Fourty International Joint Conference on Artificial Intelligence, IJCAI-25, pages 564. International Joint Conferences on Artificial Intelligence Organization, 8 2025.
[34] Zichong Wang, Anqi Wu, Nuno Moniz, Shu Hu, Bart Knijnenburg, Xingquan Zhu, and Wenbin Zhang. Towards fairness with limited demographics via disentangled learning. In Proceedings of the ThirttyFourthh International Joint Conference on Artificial Intelligence, IJCAI-25, pages 663. International Joint Conferences on Artificial Intelligence Organization, 8 2025.
[35] Zichong Wang, Zhipeng Yin, Liping Yang. Jun Zhuang, Rui Yu, Qingzhao Kong, and Wenbin Zhang. chimesss-wwree graph representation learning with limited demographic information. In Machine Learning and Knowledge Discovery in Databases, pages 354 371. Springer Nature Switzerland, 2025.
[36] Zichong Wang, Jie Yang, Jun Zhuang, Puqing Jiang, Mingzhe Chen, Ye Hu, and Wenbin Zhang. Fair graph learning with limited sensitive attribute information. In Proceedings of the AAAI Conference on Artificial Intelligence, 2026.
[37] Zichong Wang. Tongliang Liu, and Wenbin Zhang. Guic: Certified graph unlearning with individual faimess guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, 2026.
[38] Wenbin Zhang, Shuigeng Zhou, Toby Walsh, and Jeremy C Weiss. Fairness amidst non-iid graph data: A literature review. Al Magazine, 46(1)xe12212 2025.
[39] Zichong Wang, Charles Wallace, Albert Bifet, Xin Yao, and Wenbin Zhang. Fg²an: Faimess-- aware graph generative adversarial networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 259-275. Springer Nature Switzerland, 2023.
[40] Lecheng Zheng, Dawei Zhou, Hanghang Tong, Jiejun Xu, Yada Zhu, and Jingrui He. Fair- gen: Towards fair graph generation. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pages 2285-2297. IEEE, 2024.
[41] Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International conference on machine learning, pages 10362-10383, PMLR, 2022.
[42] Zichong Wang, Giri Narasimhan, Xin Yao, and Wenbin Zhang. Mitigating multisource biases in graph neural networks via real counterfactual samples. In 2023 IEEE International Conference on Data Mining (ICDM), pages 638 647. IEEE, 2023.
[43] Zichong Wang, Nripsuta Saxena, Tongjia Yu, Sneha Karki, Tyler Zetty, Israat Haque, Shan Zhou, Dukka Kc, Ian Stockwell, Albert Bifet, al. Preventing discriminatory decision-making in evolving data streams. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2023.
[44] Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. A kernel method for the two-sample- proble......mm...mmmm Advances neural information processing systems, 19, 2006.
[45] Hans Gebelein. Das statistische problem der korrelation als variations-umi eigenwertproblem und sein zusammenhang mit der ausgleichsrechnung. ZAMM-Journal of Applied Mathematics and Mechanics/ZZitschriff für Angewandte Mathematik und Mechanik, 21(6))364-3)) 1941.
[46] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-95 2008.
[47] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05888, 2018.
13

---

[48] Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 2012.
[49] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. In International conference on machine learning, pages 17391-17408. PMLR, 2023.
[50] Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic faimess: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
[51] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[52] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
[53] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02007 2016.
[54] Sangwon Jung, Donggyu Lee, Taeeon Park, and Taesup Moon. Fair feature distillation for visual recognition. In Proceedingy of the IEEE/CVF conference computer vision and paltern recognition, pages 12115-12124, 2021.
[55] Junghyun Lee, Gwangsu Kim, Mahbod Olfat, Mark Hasegawa-Johnson, and Chang D Yoo. Fast and efficient aund-based fair pea via optimization over stiefel manifold. In Proceedings of the AAAI conference artificial intelligence, volume 36, pages 7363-7371, 2022.
[56] Hao Yang, Xian Wu, Zhaopeng Qiu, Yefeng Zheng, and Xu Chen. Distributional fairness-aware recommendation. ACM Transactions on Information Systems, 42( 2024.
[57] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[58] O Deniz Kose and Yamning Shen. Fairgat: Fairness-awaee graph attention networks. ACM Transactions on Knowledge Discovery from Data, 18(7):1-20, 2024.
14

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer:[Yes
Justification: [TODO]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [TODO]
15

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: [TODO]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.cc/pbllc/guideeee http://oeeubiiiisioooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
17

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
18

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps//beerrpp..ccoubbbii/iiiie
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses such risks.
19

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
20

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ttp::////errrpsccccooofrrrree/p for what should or should not be described.
21

---

A Proof of Theorem 4.2
Without loss of generality, will focus on providing the reconstruction disparity bounds for adjacency matrix generation. Consider a fairness-aware spectral diffusion model reconstructing an adjacency matrix A from the original graph & with adjacency matrix A. Let P Pinta and iittr denote binary masks for intra-ge intra-group and inter-group edges respectively. We define the disparity between intra- and inter-group as follows:
E, A E.
E
(15)
where E, A. A denotes the reconstruction error. In addition, the term Ei
P Pinter
+ E, and
E & P mina 3 E,.
Building this, can defined the disparity between intra- and inter- inter-group at time t as follows:
(P
iinner
P Pintra
O d.A. = dAm inter dAi...
intra
(16)
Hence, have:
1 o7 (- - oz t) + A
dÂ, =
Ssmua(Ae) dt + ordWe.
(17)
Given the spectral decomposition A UAU the reverse-time spectral diffusion SDE for A, with fairnsss regularization 4 (stru(()) is:
dÂ: = (-2 -
(An,t) + -- PraVA + o,dM,
of
(18)
Therefore, the d'Aimee inter and d'A intra are:
d'ijmier
o PfP Pinter O 20 ZA(A t) + of inter
UVV ^ street UT] df o.P inter C dM,
d'i
2al ( () + oiP intra O UVV A $ struet UT]) dl + opP mtra C dM, 1 A of intra
(19)
To bound disparity, observe that the supports of P inter and Pim intra are disjoint, hence:
E I/
||
Eintra 2
E
pinter
2
Binta 1|
[[
inter
Pintra) E, E (20)
Taking expectation at and applying the spectral-noise variant gives. Hence, the disparity between the two subgroups satisfies:
E
E <
Eoll < (n)
(21)
Building this, the final disparity between the inter- and intra- edges is:
Bspec (n) = (M K) E(Φ) (1+nk nk //' x-² x nk f: E-² dz dl
dis 1 <
(22)
where A 2ML/E| 1222 M, are absolute constants, E - exp - 1o o7 oz and E(.) is the expected score and defined
E()) EEW
(xl - (z,))(z;))1
(23)
22

---

This result demonstrates that the fairnss-- spectral diffusion model effectively controls recon- struction disparity between intra- and inter-group connections. The disparity measure guaranteed to be bounded in terms of the spectral reconstruction bound (n), indicating controlled fairness in graph structure generation.
This completes the proof.
B Proof of Theorem 4.3
For binary node classification, the group disparity such statistical group parity is defined as: Asp = [ 1|s = d) Plğ 1|s = f) To analyze how structural bias propagates to this fairness metric, we examine the properties of the Softmax function, which generates the prediction probabilities Pi and P2 for classes e₁ and c2, respectively. A key analytical property of Softmax is its Lipschitz continuity with constant L, which guarantees that differences in output probabilities bounded proportionally to differences in input vectors.
ll: - [(z))l & L1 - 2/ll2 S I. [. [lb]
h2
(24)
where = Wh and 2, = W'' this formulation, hy represents the node embedding for some E Sa and hy, represents the node embedding for some dy Sy, where Sa and S the two sensitive groups. Without loss of generality, we focus on the 1th GNN layer to illustrate this propagation mechanism, where the input representations are denoted by h' and the corresponding output representations are denoted by 4+1
Hence, we can rewrite the statistical parity as follows:
ADP
1 No
1(4), SE
1 N1
(25)
jES:
Building on this, we can conclude that disparities in node classification outcomes directly stem from discrepancies in node representations. To quantify node representation discrepancies
on the
1th GNN layer, we adopt Maximum Mean Discrepancy (MMD) 44 our measurement framework.
MMD offers superior transfer learning capabilities compared to alternative metrics [54] 55 [6]]
making particularly well-suited for addressing fairness challenges in graph learning contexts. Hence, the node representation discrepancies are defined as:
b S.D MMD AMDD(1b,) (h's, I 1u Vssl. (h's us E Vsi,t)
1
Σ
M( (nt, n2zs) + "Vs,
Σ M( Int,s)
VVsa?
vinyEVs,
2
M(n's. k2s..)
(26)
Vsal
|ss
EVVS eyEVs
where k(x, y) = exp (->|1a 12) is RBF kernel function.
Building on this, and given that Graph Attention Networks [57] (GAT) adopt the message passing by assigning different weights to neighbor nodes as:
(-11)
cxp
Σ ())
1- (--) dg
with a
(27)
Σ E exp
Cif
(1-1)
Here, we further distinguish between neighbor information from the inter-group and neighbor information from the intra-group, detailed as follows:
23

---

1
Σ
Anjainaa h3
(1-1)
11
E
a-1) 111) jygiter hj
(28)
My My
1y (
where a
((-1) ig.intra
and a (1-1)
inter are defined as:
(1-1) ijjimira
(1-1) exp
(1-1) inninia
exp
(1-1)
&j.inter
(29)
11-1] inkiinira
(1-1)
exp
exp
dhe (Nimaai)
#/ P (4)
Hence, we can rewrite the node representation as follows:
h, h
1111))
Σ
aig
(1-1)
A
(1-1) bias
SEN(E)
h (1-1) + iinte
(1-1)
(1-1)
aig,inra 1j
(ENum
W (1-1)
Σ
(1-1) (1-1) LC
h3
Σ
R(h (-1) h (
(t-1)) - h(-1))
initer
N
(ENine()
uESa
Σ
k(h (1-1) h (h h b
(1-1)
(30)
NaN
eES,
where h ((-1)
(1-1) (-1) (1-1) h (1-1)
( iuriintra u,intra in,iiete u,inter
and similarly for others.
For nodes belonging to the sensitive group Sa, the representation ( at layer / is constrained (d)
within hypercube centered the group mean Pi with boundaries defined by deviation vector A',
expressed as 14) (d) A = (1) = Hi + A 588. This constraint implies that each dimension m of
(d) representation vector exists within a specific interval [m A Mi. + A.m... Analogously,
representations nodes from group Sy are bounded within their own characteristic region (u( +A'].
h
E
11-1
(d) +
wi
i,intra
11-1)
Σ
(1-1) h 11 1) + Wi iun
(1-1)
Σ
a iu, ha
(1-1 (1-1)
(31)
u.Num.))
LC
Wh b 11) (1-1) -ho-1)
N2
Σ
(b) (1-1) ng-1)) khh (1-1) h (1
(32)
NoN, DES,
+ [LA + 2V A.
Therefore, the node representation discrepancy is:
24

---

19 Σ 1.
En h
Σ
11-1)
1 Σ
|1
(1) -1iill
Na iES
Nj jESy
Na. SeSa
N5
jES,
C
NoN7
1
+ N4N;
N2
Mh 11) hn 11 +
N Σ
Mh bn
P.gESa
JreeS,
2
Σ PESa rES,
Σ
Khg
+
--| +
2VN
N
(33)
Building on this, we define the upper bound of the consequent node representation discrepancy on node representation between two sensitive subgroups as follows:
hn
h
Σ JES,
h
Nd
N
iES
(1-1))
Σ
((1-1)
|| -1
Nd iESa
N jES,
+ +C( 1
1
Σ
Wh.
Wh!l!) by (1-1)) + N2 Σ
NaN;
N
N2
p.geS..
2
b/(-11) + (| 110 + -| +
Σ
Σ
Wh.l
NaN, PES. rES
(34)
Building on this theoretical foundation, we analyze how graph generation models introduce disparity between node representations, i.e., graph structure information generation bias. Mathematically, this bias can be represented as:
A gen
(f) Miggel
|l
||m4
14
(1)
(35)
Based the GNN layer's aggregation and activation functions having bounded Lipschitz constants with respect to the inputs, then any changes in the adjacency matrix propagate through the network in controlled way, Le., the discrepancy in final-layer node representations is also bounded by proportional factor 58)
A < L E||oo S L Bspc
(36)
Given that the graph structure information generation bias between the inter- and intra- edges in Equation 22 Therefore, the final result for node representation discrepancy can be bounded by:
25

---

h
Σ
h
N
iESs
JES1
S IM
|| 1-112
+C
k(h h
1 Σ ((nf-",n
(37)
N2
Nj
P.qESu
r,sESs
Σ
E
k(h
Na
PESu rES,
+ +11100-11 1000112 + [1
C / + I (app
which concludes the proof.
C
Experiments
C.1 Implementation Details
Models trained for (500, 500, 500, 200) epochs Cora, Citeseer, Photo, and Pokec, respectively, using the Adam optimizer with betas = (0.9, 0.999), learning rate = 1 x 10-3 and weight decay = 1 x 10-3 For node features X, adjacency matrix A, and latent codes u, we adopt identical seriance-presevving stochastic differential equations with 3.in = 0.1, mmax = 1.0, and 1000 discrete time steps. During inference, chain for all 1000 steps. include final deterministic noise-removal step, and stop at e = 1 x 10-4. We use mini-batches of size 32, early stopping with patience of 30 epochs, and retain weights from the best epoch. Our VAE architecture consists of GCN layers with ReLU activation for encoding and decoding, and the discriminator employs fully connected layers with LeakyReLU activation. For the downstream GCN task, we use l-layer GCN with 16 hidden units and a linear classifier. All experiments are implemented PyTorch.
start from standard Gaussian noise, run the predictor-corrector
C.2 Additional Experimental Results
Additional results for quality of generated graphs. Table 4 presents additional results on the Photo and Citeseer datasets. The results demonstrating that FairGEM consistently achieves competitive or superior generation quality compared to baseline methods. Specifically, FairGEM maintains smaller discrepancies in important graph statistics, such as degree distributions and clustering coefficients, across both datasets. Furthermore, it continues to exhibit significant improvements in fairness metrics, indicating that the generated node features and structural patterns effectively avoid disproportionate favoring of any subgroup. This consistently strong performance further supports the effectiveness of FairGEM's approach, emphasizing its ability to generate realistic, and unbiased synthetic graph.
Table 4: Graph generation results on Photo and Citeseer datasets.
Photo
Citeseer
Method
DD
Clus
NFea
Fair-DD
Fair-Clus
Fair-NFea
DD
Clus
NFca
Fair-DD Fair-Clus Fair-NFea
GRAPHARM
0.317
0.235
0.327
0.063
0.084
0.068
0.265
0.193
0.163
0.098
0.054
0.058
GSDM
0.293
0.229
0.314
0.055
0.079
0.063
0.271
0.187
0.152
0.084
0.047
0.042
FairAdj
0.301
0.231
0.320
0.036
0.055
0.051
0.337
0.204
0.158
0.067
0.026
0.035
FG' AN
0.357
0.253
0.345
0.042
0.060
0.050
0.358
0.221
0.167
0.071
0.035
0.051
FairGen
0.378
0.294
0.368
0.038
0.058
0.041
0.377
0.237
0.181
0.068
0.025
0.036
FairWire
0.347
0.287
0.354
0.029
0.048
0.049
0.349
0.218
0.173
0.062
0.023
0.039
FairGEM
0.318
0.245
0.331
0.018
0.033
0.037
0.311
0.187
0.160
0.05
0.013
0.028
26

---

Additional results for downstream task performance evaluation. Table presents these sup- plementary results. Specifically, across these datasets, synthetic graphs generated by FairGEM consistently led to improved fairness in node classification tasks when compared to baseline genera- tion methods. These consistent improvements underline FairGEM's s effectiveness limiting bias propagation from generated graphs into downstream applications, thereby enhancing fairness in node classification task.
Table 5: Node classification results on Photo and Citeseer datasets.
Photo
Citeseer
Acc(S))
Fl-soore (%)
Ape (96)
Apo
Acc (S))
Fl-soore (5)
Anp (8)
Axo
Original
74.83 1 2.18
62.36 1.84
13.21 1 0.82
14.50 1. 1.56
76.31 1 1.34
68.47 + 1.28
20.11 1677
22,31 1 0.98
TRAPHARM-GON
70:38
82.71
12.25
12.53 4:
73.25 2.01
65.21 1.61
16.98
18.64
GSDM-GCN
11.23
PairAdj-GCN
66.23 1.12
76.67
1.54
9.87 0.56
10.21 + 1.81
70.33 + 1.59
00.52+11.2 1.23
14.25 + 1.51
15.48 + 1.09
FGAAN-GON
07.23=1477
1.32 74.88
10.84 0.83
11.75 1.39
71,82 1.79
29.48200.35
16.16 1.27
16,36 # 1.50
FairGan-GCN
00.32 1.87
17.31
12.11
FaiWire GCN
70,81 1.73
75.36
9.71 0.88
10.30 1.65
74.98 4: 1.01
61.11:1:000
12.98
1.96
16.01 2.10
GSDM-GCN
71.21 = 0.98
1.08 T8.67
10.02 1.11
1.21 11.87
74.98
1.01
61.11
1.09
12.98
1.36
16.01 1: 2.10
BarGREM-GCN
72.25
1.33
78.41
1.46
7.38
1.04
8.61
1.28
76.25 1.81
66.30 + 1.03
9.28 = 0.59
11.48 = 1.12
supplementary ablation study results on additional datasets. These results consistently show that each component of FairGEM plays crucial role achieving both high generation quality and fairness. Specifically, removing either the fair graph structure regularizer, the fair node feature regularizer, or the disentanglement component leads to noticeable degradation in performance and faimess. These findings confirm the necessity and complementarity of each component within FairGEM for effectively generating high-quality, unbiased synthetic graph.
Additional results for ablation study.
Photo
Citeseer
0.45
0.45
0.35
0.30
0.30
0.25
0.25
0.30
0.10
0.05
0.05
D0
Clus
NFea
FairDD
Fain-Clus Fair-Nieea
0.00
NFca
Fair
Fair Clus NFea
FairGEM
FairGEM-WS
FairGEM-WD
FairGEM-WF
Figure 3: Ablation study results for FairGEM, FairGEM-WS. FairGEM-WD and FairGEM-Wi WF in Photo and citeseer datasets.
27


Reviews:
[{"review_id": "nu5xotBvhJ", "reviewer": "Reviewer_PA1S", "summary": "This paper proposes a one-shot spectral diffusion framework with two fairness regularizers, (1) Structural regularizer that minimizes intra- vs inter-group edge-reconstruction disparity and (2) Feature regularizer that first disentangles sensitive-related vs sensitive-irrelevant attributes (via a VAE + HGR penalty) and then enforces MMD fairness only on the insensitive part. Theory insights", "questions": "1. What is the computational cost compared to GSDM? Spectral diffusion on Pokec-z (68k nodes) could be heavy. \n2. Many fairness improvements are small (e.g., Fair-DD 0.020 vs 0.027). Are these differences statistically significant at p < 0.05?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. This paper addresses an under-explored but important fairness problem in graph generation, which is a interesting problem\n2. This paper novelly integrates recent spectral diffusion methods, avoiding node-ordering issues.\n3. The theoretical link between bias in eigen-value diffusion and downstream ΔDP is novel.\n\nWeakness:\n\n1. There is proof gaps: Theorem 4.2/4.3 rely on undefined constants (M, K, C, Σt) and assume Lipschitz/non-expansive GNN layers without verification.\n2. Datasets are small/medium, method might struggle scaling to graphs with >100k nodes or multiple sensitive attributes.\n3. Only binary sensitive variable considered; real-world use often needs multi-class or intersectional fairness.", "was_revised": true, "final_justification": "I would recommend this paper as the authors addressed my questions.", "rebuttal": "We sincerely thank Reviewer PA1S for the detailed review and constructive feedback. Our responses to each point are provided below.\n\n**There is proof gaps: Theorem 4.2/4.3 rely on undefined constants (M, K, C, $\\Sigma_t$) and assume Lipschitz/non-expansive GNN layers without verification.**\n\nThe constants $M$, $K$, $C$, $\\Sigma_t$ are defined in lines 208–210 and 535–536 of the manuscript. Specifically, $C$ is a fixed absolute constant that appears in the derivation, $\\||\\sigma\\_{\\cdot}\\||\\_{\\infty} := \\max\\_{t \\in [0,1]} \\sigma_t$ is the supremum of the noise schedule, and $\\Sigma\\_t^2 = 1 - \\exp \\bigl(\\int\\_0^t \\sigma\\_z^2 dz\\bigr)$ quantifies the accumulated variance of the forward diffusion up to time $t$. We first set $M = C^2 \\||\\sigma_{\\cdot}\\||_{\\infty}^4$, and then determine $K$ self-consistently via $K = \\frac{2ML}{\\mathbb{E}[\\||\\mathbf{A}_0\\||_2]}$, where $L$ is the Lipschitz constant of the GNN layer. Spectral normalization can enforce $\\||W\\||_2 \\leq 1$ for every weight matrix, so $L \\leq 1$ is verified in practice. Because $\\||\\sigma\\_{\\cdot}\\||\\_{\\infty}$, $L$, and $\\mathbb{E}[\\||\\mathbf{A}_0\\||_2] $ are all either preset or directly measurable, this two‑step definition yields unique and numerically computable values of $M$ and $K$. Hence, every constant appearing in Theorems 4.2 and 4.3 can be instantiated from observable quantities, removing any ambiguity in the theoretical bounds.\n\n\n**Only binary sensitive variable considered.** Most existing studies on fairness-aware learning focus on binary classification with a single sensitive attribute, as this setting enables clearer fairness definitions and more tractable algorithm design. Our work follows this established convention. Extending to multi-class and multi-attribute settings introduces distinct problem formulations with new fairness notions and evaluation complexities. While beyond our current scope, we agree this represents an important direction for future work.\n\n**Computational cost compared to GSDM.** Both FairGEM and GSDM rely on a diffusion-based generative process with a fixed number of steps $T$, and they have same-level time complexity. To compare them fairly, we break down the training complexity into three components, feature generation, graph structure generation, and fairness regularization, using the notation: $n$ (number of nodes), $d$ (feature dimension), $k$ (truncated spectral components), and $T$ (diffusion steps). \n\nFor feature generation, both models handle node features via a reverse diffusion on an $n \\times d$ feature matrix. At each diffusion step, the model updates each node’s feature vector of dimension $d$, which takes $O(d)$ work per node. Across all $n$ nodes, this amounts to $O(T n d)$ for $T$ steps. This feature generation component is linear in the number of nodes and features, and for typical settings, it is much smaller than the structural cost.\n\nIn parallel with feature generation, graph structure generation, both methods begin by performing a truncated eigendecomposition of the graph’s adjacency matrix. This initial spectral computation costs on the order of $O(nk^2)$ time. After obtaining the eigenvectors ($\\mathbf{U}_0$) and eigenvalues, both FairGEM and GSDM evolve only these $k$ spectral components through $T$ diffusion steps. In each diffusion step, the algorithms update the vector of $k$ eigenvalues (an $O(k)$ operation) and then reconstruct the full adjacency matrix from the spectral components. This reconstruction involves multiplying the $n \\times k$ eigenvector matrix by its $k \\times n$ transpose with the updated eigenvalues in between (essentially computing $\\mathbf{U}_0\\boldsymbol{\\Lambda}_t\\mathbf{U}_0^T$ at each time $t$). The matrix multiplication costs $O(n^2 k)$ per step. Because $O(n^2 k)$ grows quadratically with the number of nodes, this operation dominates the runtime for both methods.\n\nThe main difference between FairGEM and GSDM is the additional computations FairGEM performs at each step to enforce fairness constraints. FairGEM augments the reverse diffusion with extra gradient calculations for its fairness regularizers, i.e., computing $\\nabla_{\\Lambda}\\Phi_{\\text{struct}}$ for structure-based fairness (acting on the eigenvalues $\\Lambda_t$) and $\\nabla_{X}\\Phi_{\\text{feat,ns}}$ for feature fairness (acting on the node features $X$). These calculations introduce an overhead in each diffusion step. In the worst case, if FairGEM computes a fairness-related statistic for every node (or every feature of every node), this overhead would scale as $O(n)$ per step, it remains well below the $O(n^2 k)$ cost of reconstructing the graph structure. In other words, FairGEM’s fairness module adds only a modest constant-factor overhead to each diffusion step. It increases the runtime slightly (making FairGEM somewhat slower in practice than GSDM by a constant factor), but it does not change the overall asymptotic complexity since no new higher-order terms in $n$ are introduced.\n\n**Statistical significance.** Regarding the inquired result, we conducted all experiments 5 times with different random seeds and performed paired t-tests to assess statistical significance. Specifically, for the Fair-DD comparison mentioned (FairGen 0.027 vs FairGEM 0.020), our detailed results across 5 runs were: FairGen [0.026, 0.026, 0.027, 0.029, 0.027] and FairGEM [0.021, 0.018, 0.021, 0.019, 0.021]. The paired t-test yields p = 0.00144 (p < 0.05), indicating the improvement is highly statistically significant, which demonstrates that the observed differences are not due to random variation but represent genuine algorithmic improvements. \n\nIn addition, please find below all statistically significant results comparing our model with the baselines:\n\n**cora:**\n| Baseline | DD      | Clus    | NFea    | Fair-DD | Fair-Clus | Fair-NFea |\n|----------|---------|---------|---------|---------|-----------|-----------|\n| GRAPHARM | 0.00321 | 0.01154 | 0.02263 | 0.00362 | 0.00287   | 0.00176   |\n| GSDM     | 0.00518 | 0.01642 | 0.02857 | 0.00185 | 0.00432   | 0.00309   |\n| FairAdj  | 0.01834 | 0.03678 | 0.02468 | 0.00745 | 0.01012   | 0.00928   |\n| FG2AN    | 0.01245 | 0.02511 | 0.03150 | 0.00563 | 0.00754   | 0.00631   |\n| FairGen  | 0.02633 | 0.02977 | 0.02745 | 0.00144 | 0.01543   | 0.01164   |\n| FairWire | 0.02311 | 0.03529 | 0.02894 | 0.00976 | 0.01398   | 0.01053   |\n\n\n**Pokec:**\n| Baseline | DD      | Clus    | NFea    | Fair-DD | Fair-Clus | Fair-NFea |\n|----------|---------|---------|---------|---------|-----------|-----------|\n| GRAPHARM | 0.00678 | 0.01845 | 0.02567 | 0.00273 | 0.00398   | 0.00255   |\n| GSDM     | 0.00932 | 0.02214 | 0.02944 | 0.00381 | 0.00544   | 0.00417   |\n| FairAdj  | 0.03087 | 0.03854 | 0.03689 | 0.01165 | 0.01734   | 0.01476   |\n| FG2AN    | 0.01998 | 0.03321 | 0.02987 | 0.00891 | 0.01254   | 0.00987   |\n| FairGen  | 0.02987 | 0.03765 | 0.03876 | 0.01432 | 0.02011   | 0.01655   |\n| FairWire | 0.03744 | 0.03244 | 0.02833 | 0.01222 | 0.01765   | 0.01344   |\n\n\n   \n\n**photo:**\n| Baseline | DD      | Clus    | NFea    | Fair-DD | Fair-Clus | Fair-NFea |\n|----------|---------|---------|---------|---------|-----------|-----------|\n| GRAPHARM | 0.00311 | 0.01145 | 0.02067 | 0.00432 | 0.00254   | 0.00183   |\n| GSDM     | 0.00423 | 0.01588 | 0.02456 | 0.00177 | 0.00392   | 0.00268   |\n| FairAdj  | 0.01814 | 0.02976 | 0.03552 | 0.00698 | 0.00941   | 0.00806   |\n| FG2AN    | 0.01123 | 0.02435 | 0.02897 | 0.00487 | 0.00675   | 0.00543   |\n| FairGen  | 0.02545 | 0.03212 | 0.02788 | 0.01222 | 0.01511   | 0.01276   |\n| FairWire | 0.01978 | 0.02763 | 0.03145 | 0.00933 | 0.01288   | 0.00997   |\n\n\n**citeseer:**\n| Baseline | DD      | Clus    | NFea    | Fair-DD | Fair-Clus | Fair-NFea |\n|----------|---------|---------|---------|---------|-----------|-----------|\n| GRAPHARM | 0.00451 | 0.01268 | 0.01899 | 0.00232 | 0.00294   | 0.00207   |\n| GSDM     | 0.00567 | 0.01645 | 0.02234 | 0.00195 | 0.00436   | 0.00321   |\n| FairAdj  | 0.02044 | 0.03321 | 0.03788 | 0.00789 | 0.01126   | 0.00951   |\n| FG2AN    | 0.01332 | 0.02654 | 0.03077 | 0.00545 | 0.00817   | 0.00674   |\n| FairGen  | 0.02834 | 0.03876 | 0.04155 | 0.01478 | 0.01823   | 0.01412   |\n| FairWire | 0.02411 | 0.03146 | 0.03569 | 0.01056 | 0.01467   | 0.01149   |"}, {"review_id": "CKGVdAKJVB", "reviewer": "Reviewer_YyAy", "summary": "This paper presents FairGEM, a framework for generating synthetic graphs that aim to be both realistic and fair with respect to sensitive attributes. It introduces fairness-aware regularizers on both graph structure and node features, combines them with a disentanglement-based encoder using a VAE and HGR criterion, and provides theoretical guarantees relating fairness at generation time with downstream task bias. Experimental results show improved fairness across several benchmarks and metrics, including node classification accuracy and fairness gaps (ΔDP, ΔEO).", "questions": "* In what way is your proposal a meaningful contribution, given that its performance is very similar to existing state-of-the-art methods?\n\n* What are the concrete benefits of using diffusion models over autoregressive ones, especially when no performance improvements are demonstrated?\n\n* Why does the paper omit implementation details of your model, including training setup and reproducibility information?", "limitations": "No. Author do not mention any limitations on their approach.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength\n\n* The paper tackles an important and timely problem: how bias in graph generation can influence downstream tasks, such as node classification.\n\n* It introduces a novel framework that adds fairness-aware regularizers to control both structural and feature-based biases.\n\n* The authors include theoretical results (Theorems 4.2 and 4.3) that support their claims (and proper theoretical proof in apendices), showing how bias in the generated graphs can affect performance in downstream models.\n\n* A key technical contribution is the use of Variational Autoencoders (VAEs) to separate sensitive-related features from unrelated ones. The approach also leverages diffusion models, which are claimed to avoid node ordering issues seen in autoregressive methods.\n\n* The method is evaluated on real-world datasets, and shows that it can improve fairness (lower ΔDP and ΔEO) while maintaining comparable accuracy to existing baselines.\n\nWeaknesses: \n* While the paper reads well, it does not clearly refer to figures or tables when making key arguments, which hurts clarity and traceability.\n\n* There are inconsistencies in the numbering of definitions and theorems: Definitions 4.2 and 4.3 are missing, while Theorems 4.2 and 4.3 are present. Since all of this occurs within Sections 4.1 to 4.3, it makes the structure harder to follow and disrupts the logical flow of the paper.\n\n* The ablation study is weakly developed. There’s little discussion, and it’s unclear how the conclusions connect to Figure 2.\n\n* The reported performance differences with other models are often small and lack statistical validation (e.g., no error bars, confidence intervals, or significance testing).\n\n* The study doesn’t clearly isolate the contribution of individual components (e.g., feature fairness vs. disentanglement). For example, although the paper promotes the use of diffusion models as a major strength, this aspect isn’t clearly reflected in the results or conclusions.\n\n* There is no qualitative or visual analysis to help the reader understand how the generated graphs differ in terms of fairness or structure.\n\n* Reproducibility is lacking: the paper does not provide implementation details, training configuration, or hyperparameter tuning strategies. There is no mention of code availability, runtime, or resource usage, which makes it hard to compare with other models in terms of practicality.\n\n* While ΔDP and ΔEO are standard metrics for fairness, the paper does not fully explain their relevance in the context of downstream node classification, or why they are appropriate indicators for this task.", "was_revised": true, "final_justification": "The paper addresses a significant problem of bias in graph generation, proposing a novel framework that incorporates fairness-aware regularizers to mitigate both structural and feature-based biases. The approach leverages Variational Autoencoders (VAEs) to disentangle sensitive features from non-sensitive ones, and employs diffusion models to overcome node ordering limitations inherent in autoregressive methods.\n\nWhile the contribution is clear and relevant, some critical technical details and reproducibility components were omitted from the submission. These elements are essential to fully establish the impact of the work. The rebuttal clarified that these details exist but were excluded due to page constraints. I strongly encourage the authors to incorporate these details in the final camera-ready version, as discussed previously.\nThat being said, I am raising my score, while expecting the discussed changes to appear in the final manuscript.", "rebuttal": "We sincerely appreciate Reviewer YyAy's thorough review and have provided detailed responses below.\n\n**Our contributions.** We note that our method explores underexamined sources of bias and offers theoretical foundations to guide future research, leading not only to a superior fairness-utility trade-off but also to deeper insights into fairness mechanisms. Specifically,\n\nFirst, we are the first to systematically address feature bias in fair graph generation. Existing methods have focused exclusively on structural bias (connectivity patterns), but we identify and tackle feature bias, systematic differences in generated node attributes across demographic groups, which can lead to discriminatory downstream applications even when structural patterns appear fair. This represents a novel problem formulation that expands the scope of fairness considerations in graph generation.\n\nSecond, our work introduces rigorous mathematical analyses which formally quantify how bias propagates during the spectral diffusion process and provide principled upper bounds on this propagation. These theoretical contributions go beyond existing heuristic methods by offering a mathematical framework to understand why fairness interventions work and how to design them systematically. The derivations uncover the mechanisms of bias amplification in spectral space and establish provable guarantees for bias control during generation.\n\nThis theoretical foundation enables practitioners to move beyond trial-and-error approaches to fairness-aware graph generation. Our framework provides principled guidance for hyperparameter selection, offers interpretable bounds on worst-case bias scenarios, and establishes a mathematical basis for future algorithmic development in this area. The practical fairness improvements (*e.g.*, 10.3\\% in demographic parity, 8.0\\% in equalized opportunity compared with the best baselines) also substantiate the theory’s practical utility. \n\nIn sum, the value of this work extends beyond immediate performance gains by equipping the research community with fundamental tools for understanding and controlling bias in graph diffusion models. This theoretical groundwork not only opens new research directions but also introduces principled fairness approaches that were previously unavailable, marking a significant advancement in the field’s theoretical foundations.\n\n\n**Benefits of using diffusion models over autoregressive ones.** The advantages of diffusion models over autoregressive approaches are particularly pronounced in the context of fair graph generation, leading to our demonstrated fairness improvements. First, diffusion models update the entire adjacency matrix simultaneously, making the generation process independent of node ordering, whereas autoregressive models require arbitrary node orderings or BFS heuristics that systematically skew fair-edge statistics in sparse graphs. This ordering dependency in autoregressive models creates inherent bias: nodes processed earlier in the sequence tend to receive more connections, and if the ordering correlates with sensitive attributes, this amplifies structural discrimination. Second, autoregressive models struggle to capture comprehensive global structural patterns efficiently, as they construct graphs incrementally without full visibility of the final structure. In contrast, diffusion models can incorporate global fairness constraints throughout the entire generation process via our spectral manipulation approach, ensuring that fairness considerations influence the entire network structure rather than just local neighborhoods. These fundamental advantages directly translate to our verified fairness improvements. For instance, we achieve 10.3\\% better demographic parity and 8.0\\% better equalized opportunity compared to autoregressive baselines, while maintaining comparable utility. The ordering independence and global optimization capability of diffusion models are essential for achieving these fairness gains, as they eliminate the systematic biases inherent in sequential generation approaches. Thus, the architectural advantages of diffusion models enable substantial fairness improvements that autoregressive methods cannot achieve.\n\n**Implementation details.** Models are trained for {500, 500, 500, 200} epochs on Cora, Citeseer, Photo, and Pokec, respectively, using the Adam optimiser with betas = (0.9, 0.999), learning rate = $1 \\times 10^{-3}$, and weight decay = $1 \\times 10^{-5}$. For node features $X$, adjacency matrix $A$, and latent codes $u$, we adopt identical variance-preserving stochastic differential equations with $\\beta_{min} = 0.1$, $\\beta_{max} = 1.0$, and 1000 discrete time steps. During inference we start from standard Gaussian noise, run the predictor–corrector chain for all 1000 steps, include a final deterministic noise-removal step, and stop at $\\varepsilon = 1 \\times 10^{-4}$. We use minibatches of size 32. If the validation loss does not fall for 30 consecutive epochs, training stops early and the weights from the best epoch are kept. Our VAE architecture consists of GCN layers with ReLU activation for encoding and decoding. The discriminator consists of fully connected layers with LeakyReLU activation. For the downstream task used GCN, we use a 1-layer GCN with 16 hidden dimensions and use a linear layer as the classifier. All experiments were conducted in PyTorch.\n\n**There are inconsistencies in the numbering of definitions and theorems.** The “inconsistency” arises from LaTeX treating definitions and theorems as the same numbering category in our document class. We will adjust this in the next version by separating the numbering environments to ensure clear sequential numbering for each mathematical statement type respectively."}, {"review_id": "GB6BUpcQFX", "reviewer": "Reviewer_dYrj", "summary": "In this paper, the authors propose a novel graph generation framework named FairGEM, which can mitigate both graph structural bias and node feature bias simultaneously. Both theoretical analysis and empirical experiments verify the effectiveness of FairGEM.", "questions": "please refer to the weakness", "limitations": "The authors do not discuss the limitations of their work. However, as mentioned in the weakness, I believe that including experiments or empirical analysis on link prediction tasks can greatly improve the quality of this paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**strength**\n\n1. Overall, this paper is well-written and easy to follow.\n\n2. The proposed FairGEM is guaranteed with theoretical foundation.\n\n3. Extensive experiments verify the effectiveness of FairGEM in fairness metrics.\n\n**weakness**\n\n1. The definitions of $\\Delta _{DP}$ and $\\Delta _{EO}$ are missing, which should be given in the appendix for better clarity.\n\n2. What about the comparisons with some powerful fair GNN methods trained on the original graphs? Such as FairSIN [1], EDITS [2] and others.\n\n3. Currently, the authors mainly focus on node classification in the downstream tasks. Taking link prediction tasks (like dyadic fairness) into considerations can better enhance the contributions of FairGEM compared with other fair GNN methods.\n\n[1] FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization. AAAI 2024.\n\n[2] EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks. WWW 2022.", "was_revised": true, "final_justification": "My main concerns about the insufficient comparison are addressed by the rebuttal. I would like to maintain acceptance for this paper after considering both the response and the reviews from other reviewers.", "rebuttal": "We sincerely appreciate Reviewer dYrj's thoughtful feedback and have provided detailed responses below.\n\n**The definitions of $\\boldsymbol{\\Delta_{\\rm{DP}}}$ and $\\boldsymbol{\\Delta_{\\rm{EO}}}$.** $\\Delta_{\\rm{DP}}$ = $|P(\\hat{Y}=1|S=0) - P(\\hat{Y}=1|S=1)|$ measures the difference in positive prediction rates between demographic groups, while $\\Delta_{\\rm{EO}}$ = $|P(\\hat{Y}=1|Y=1,S=0) - P(\\hat{Y}=1|Y=1,S=1)|$ measures the difference in true positive rates between groups.\n\n**Additional experiments.** We appreciate the reviewer's suggestion regarding comparisons with FairSIN, EDITS, and other fair GNN methods. However, there is a fundamental distinction between our work and these methods that makes direct comparison inappropriate. Our paper focuses on the graph generation task, where the objective is to synthesize new, fair graph structures and node features from scratch. In contrast, FairSIN, EDITS, and similar fair GNN methods address the node classification task, where the goal is to make predictions on the input graph while ensuring fairness in those predictions.  Fair graph generation methods (like ours) need to learn to create realistic graph topologies and node attributes that preserve statistical properties while ensuring fairness, whereas fair GNN classification methods take existing graphs as input and focus on learning fair representations for downstream prediction tasks."}, {"review_id": "LeHH9FQ6Yg", "reviewer": "Reviewer_wwvV", "summary": "This paper proposes a new method for fair graph generation. Starting with an existing graph, the goal is to produce a statistically similar one. Existing methods often emphasize irrelevant disparities between nodes, a phenomenon this approach aims to avoid.\n\nThe authors focus on a graph diffusion process to achieve fairness in both the graph's structure and its node features. The core idea is to apply penalties to two separate diffusion processes: one for the adjacency matrix (A) and another for the node features (F).\n\nThe structural fairness regularizer quantifies the discrepancy in reconstruction errors between intra-group and inter-group edges. For fair diffusion of node features, the regularization occurs in two steps. First, a Variational Autoencoder (VAE) disentangles legitimate group disparities from irrelevant ones. This partition is then used to construct a Maximum Mean Discrepancy (MMD) regularizer.\n\nSeveral experiments were conducted to assess the accuracy and fairness of the generated graph. The proposed method was compared to six other methods across four datasets. It systematically offered the best fairness performance while maintaining an accuracy similar to the other models. Experiments on a downstream task also demonstrated good fairness and accuracy. Finally, further experiments confirmed that all three steps of the regularization method are necessary to achieve these strong results.", "questions": "Equation (5): The term $\\hat{A}^{dis}_0$ does not appear to be defined in the text.\n\nLine 219: It would be helpful to specify which groups are used to evaluate the structural fairness metric, $\\phi_{struct}$.\n\nLines 285 and 287: It seems there is a typo. s_theta should likely be z_theta.\n\nLine 406: The journal is missing from this reference.\n\nLine 499 (and Bibliography): The formatting for ICLR references is inconsistent throughout the bibliography.\n\n\nMy other questions and comments are detailed in the \"Weaknesses\" section above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe paper offers strong theoretical guarantees and presents compelling experiments that validate the soundness and relevance of the proposed method. The subject of fair graph generation, especially in a setup that addresses fairness in both graph structure and node features, appears to be a relatively new and unexplored area.\n\n**Weaknesses**\n\nCertain sections of the paper could benefit from rewriting. The authors never formally define what they mean by \"fair,\" relying instead on examples. I would recommend adding a precise explanation when the sensitive attributes are introduced. Additionally, the paper's focus on spectral diffusion models is not emphasized enough, in my opinion.\n\nFinally, while the experiments are convincing, the code is not available, and neither the paper nor the appendix seems to provide enough detail to reproduce the results. For instance, I would not be able to reproduce the downstream task performance evaluation because no information on the GCN's characteristics is provided. For these reasons, the answers to questions 6 and 8 of the checklist should have been \"No,\" and a justification would have been welcome.", "was_revised": true, "final_justification": "I am pleased to recommend this paper for acceptance. The authors' rebuttal resolved all of my concerns regarding clarity, on the condition that they update their manuscript to include these additional details. While my concern about reproducibility was not fully addressed in their response to me, I see that another reviewer received a more convincing answer. Overall, the paper is solid and deserves to be accepted.", "rebuttal": "We thank reviewer wwvV for the time and thorough review. Below are our detailed responses:\n\n**Fair Graph Generation Definition.** In the context of graph generation, we define fairness as the property that generated graphs do not exhibit systematic bias in their graph structural or node feature with respect to sensitive attributes (*e.g.*, race, gender, age). Formally, a graph generator is fair if: 1) graph structural fairness: the connectivity patterns within and across sensitive groups reflect the underlying data distribution rather than amplified biases, and 2) node feature fairness: the generated node features do not differ systematically across demographic subgroups in ways that could lead to discriminatory outcomes. This ensures that downstream tasks trained on generated graphs do not exhibit disparate impact across demographic groups as measured by standard fairness metrics such as demographic parity and equalized opportunity.\n\nWe emphasize that existing fair graph generation efforts have primarily focused on mitigating graph structural bias while largely overlooking node feature bias. Node feature bias occurs when generated node features differ systematically across subgroups (*e.g.*, male nodes having higher incomes than female nodes), leading to biased downstream applications where models learn to associate sensitive attributes with specific feature patterns. Our work addresses both types of bias through spectral manipulation of the diffusion process.\n\n**Spectral Diffusion.** Our approach leverages the spectral properties of graphs through eigendecomposition of the graph Laplacian, enabling principled manipulation of both structural and feature bias in the frequency domain. While existing fairness methods primarily operate in the spatial domain and are limited to autoregressive models with inherent ordering sensitivity, our spectral approach provides a more fundamental way to control bias by directly modifying the eigenvalues and eigenvectors that encode graph structure and feature propagation. This spectral perspective allows us to provide theoretical guarantees on fairness preservation during the diffusion process and overcomes the limitations of incremental graph construction, distinguishing our work from prior fair graph generation methods.\n\n**Clarification of the notation $\\hat{\\mathbf{A}}_0^{\\text{dis}}$.** At the end of the reverse‑diffusion process ($t = 0$), we obtain a reconstructed adjacency matrix $\\\\hat{\\\\mathbf{A}}\\_0 \\\\in \\\\mathbb{R}^{n \\\\times n}$. To quantify structural bias, we partition its entries into $\\\\hat{\\\\mathbf{A}}\\_0^{\\\\mathrm{intra}} = \\\\mathbf{P}\\_{\\\\mathrm{intra}} \\\\odot \\\\hat{\\\\mathbf{A}}\\_0\n\\\\quad\\\\text{and}\\\\quad\n\\\\hat{\\\\mathbf{A}}\\_0^{\\\\mathrm{inter}} = \\\\mathbf{P}\\_{\\\\mathrm{inter}} \\\\odot \\\\hat{\\\\mathbf{A}}\\_0 $ where \\\\(\\\\mathbf{P}\\_{\\\\mathrm{intra}}(i,j) = 1\\\\) if nodes \\\\(v\\_i, v\\_j\\\\) belong to the same sensitive group (otherwise 0), and \\\\(\\\\mathbf{P}_{\\\\mathrm{inter}}(i,j) = 1\\\\) if the two nodes belong to different groups. The disparity matrix $\\\\hat{\\\\mathbf{A}}_0^{\\\\mathrm{dis}}$ captures the difference between cross‑group and within‑group in the generated graph.  A large Frobenius norm $\\\\|\\\\hat{\\\\mathbf{A}}_0^{\\\\mathrm{dis}}\\\\|_F^2$ means that the reconstruction process systematically favors one type of connection over the other, indicating strong structural bias.\n\n**The definitions of $\\Phi_{\\text{struct}}$.** The $\\Phi_{\\text{struct}}$ evaluates fairness by comparing reconstruction errors between two types of edge groups: \"within-group\" edges (where both endpoints belong to the same sensitive group) against \"between-group\" edges (which connect nodes from different sensitive groups). Specifically, the metric measures whether the diffusion model systematically reconstructs edges within demographic groups more accurately than edges across groups, or vice versa. This comparison reveals structural bias in the generation process by quantifying disparities in how well the model preserves connectivity patterns for same-group versus cross-group relationships.\n\n**Minor errors.** We will correct all these formatting and typographical errors in the next version of the manuscript."}]

Author rebuttal:

Meta-review: This paper presents FairGEM, a novel graph generation framework, focused on graph structural and node feature bias. The main idea is to apply regularizers to two separate processes: one for the adjacency matrix and another for the node features. The structural fairness regularizer quantifies the discrepancy in reconstruction errors between intra-group and inter-group edges based on the adjacency matrix. For the node features, the regularization is based on the distributional discrepancy between subgroups. Several experiments were conducted over four datasets and compared among six baselines. An ablation study also shows that both regularization processes are necessary to achieve the best results. 


Strengths
The paper addresses an important problem: fairness in graph generation. 
The paper proposes a new graph generation method considering structural and feature characteristics.
The paper presents interesting and important theoretical results. 
Extensive experiments, including four real-world datasets, show the importance of the proposed method. 

Weaknesses
The datasets are small to medium in size, which could be due to the method having some issues with larger graphs.
The evaluation of the method focuses on node classification in downstream tasks, instead of other problems such as edge classification. 
The ablation study is weakly developed. The paper does not clearly isolate the contribution of individual components (e.g., feature fairness vs. disentanglement). 
The reported performance differences with other models are often small and lack statistical validation (e.g., no error bars, confidence intervals, or significance testing). Moreover, the model is better in specific metrics for which the method was specifically created, which could lead to biased results.
Low reproducibility. The paper lacks code and does not provide implementation details, training configuration, or hyperparameter tuning strategies.
The writing can be largely improved, including: references to figures and tables (especially in cases when the analysis of these figures is important), and the number of definitions and theorems. Also, some definitions can be added in the appendix. 

The paper is accepted mainly for the discussion process. In this process, the authors address most of the weaknesses raised by the reviewers and propose several changes that should be observed in the final version.

In the discussion, the authors were able to answer most of the weaknesses mentioned by the reviewers, for example, issues with the theoretical demonstrations or time complexity. However, there are still important weaknesses that must be considered. First, the time complexity of the proposed method is O(N^2k). Second, the ablation study. Third, the low reproducibility. Fourth, the biased results.
Decision: Accept (poster)