# fdgen_a_fairnessaware_graph_generation_model__7565f1da.pdf FDGen: A Fairness-Aware Graph Generation Model Zichong Wang 1 Wenbin Zhang 1 Graph generation models have shown significant potential across various domains. However, despite their success, these models often inherit societal biases, limiting their adoption in real-world applications. Existing research on fairness in graph generation primarily addresses structural bias, overlooking the critical issue of feature bias. To address this gap, we propose FDGen, a novel approach that defines and mitigates both feature and structural biases in graph generation models. Furthermore, we provide a theoretical analysis of how bias sources in graph data contribute to disparities in graph generation tasks. Experimental results on four real-world datasets demonstrate that FDGen outperforms state-of-the-art methods, achieving notable improvements in fairness while maintaining competitive generation performance. 1. Introduction Graphs naturally appear in many real-world scenarios, from social network analysis (Grover et al., 2019), financial markets (Wang et al., 2023a), and recommendation systems (Wang et al., 2019) to the Internet of Things (Kong et al., 2023). In this context, deep learning on graph-structured data has attracted increasing attention and inspired many graph learning frameworks in recent years (Kang et al., 2022; Wang et al., 2024c; 2025h). Among them, graph generation models have become crucial components of the graph machine learning framework, serving purposes such as data augmentation (Chakrabarti & Faloutsos, 2006), anomaly detection (Akoglu et al., 2008), and enabling privacy-preserving data sharing (Kose & Shen, 2024b). Thus, creating synthetic graphs with graph generative models becomes instrumental in applications over interconnected systems. 1Knight Foundation School of Computing and Information Sciences, Florida International University, Miami, USA. Correspondence to: Wenbin Zhang . Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s). Despite showing promising results, most graph generation models suffer from fairness issues (Wang et al., 2023c), raising ethical and societal concerns, particularly in high-stake decision-making scenarios such as healthcare (Yu et al., 2020), credit scoring (Shumovskaia et al., 2020), and crime prediction (Wang et al., 2025b). Consider a credit scoring scenario where financial institutions need synthetic data for partner collaboration. While graph generation models can protect individual privacy by creating synthetic graphs from real data, they may amplify existing biases (Wang & Zhang, 2024). For example, if the original data shows ethnic clustering in financial relationships, the generated graphs often strengthen these patterns, creating denser connections between people of the same ethnicity. These amplified structural biases then affect downstream financial decisions (Wang et al., 2025a). To this end, preliminary efforts have been made to explore fairness within graph generation models. For instance, Fair Wire (Kose & Shen, 2024b) designs a fairness regularizer and leverages the proposed fair regularizer in a generative model to mitigate graph structure bias. However, Fair Wire, like existing fair graph generation models (Zheng et al., 2024), focuses solely on addressing structural bias, where nodes connect predominantly with neighboring nodes sharing the same sensitive attributes. For example, in the generated graph shown in Figure 1 (b), the central male node v1, compared with the original graph in Figure 1(a), maintains connections with male nodes v2 and v3, adds a new connection with male node v4, and loses its original connections with female nodes v5 and v6, leading to significantly higher recommendation rates within sensitive groups, potentially causing social segregation (Hofstra et al., 2017). However, all existing methods overlook feature bias, which arises when the generated non-sensitive attributes exhibit distributional disparities across subgroups. Still in Figure 1, the original graph in Figure 1 (a) depicts equal incomes across gender groups, whereas the generated graph in Figure 1 (b) shows male nodes with higher incomes than female nodes ($370,000 vs. $250,000), leading to biased downstream applications where models trained on this synthetic data learn to expect higher incomes from male applicants. In addition, feature bias is closely intertwined with structural bias, as node features propagate through the network structure. Therefore, it cannot be overlooked when aiming for FDGen: A Fairness-Aware Graph Generation Model truly fair graph structure generation. It is therefore of social importance to account for multiple biases to generate fair graphs, as shown in Figure 1 (c). Specifically, v1 maintains balanced connections with both male (v2, v3) and female neighbors (v5, v6), demonstrating equal connectivity across gender groups. Additionally, while preserving inherent group-specific characteristics, the node attributes, such as income, show similar distributions across different groups, eliminating feature bias. To achieve such fair graph generation, several challenges need to be addressed: i) Difficulty in measuring feature bias: Existing fair graph generation models primarily address structural bias by using statistical comparisons of inter-group connectivity. However, measuring node feature bias presents a critical challenge, as real-world graphs contain diverse types of node features (e.g., categorical zip codes, continuous income values) with different scales and distributions that cannot be directly compared using simple statistical measures. ii) Difficulty in mitigating multiple types of bias during generation: Unlike independent and identically distributed (IID) data, graph generation requires ensuring fairness in both node features and graph structure. Furthermore, node features influence the formation of graph structure, and the graph structure affects the generation of node features. This interdependence makes it challenging to design universal fairness constraints that can effectively reduce both types of bias simultaneously. iii) Difficulty in distinguishing group identity information: While we aim to mitigate unfair differences between groups, we need to preserve legitimate group-specific characteristics. For instance, while we seek equal treatment in non-sensitive attributes like income or credit scores, we should maintain natural group differences in physical characteristics (e.g., facial hair in males). The key challenge is to distinguish between biases that require mitigation and inherent group characteristics that should be maintained, thereby ensuring generated graphs that are both fair and realistic. To tackle the aforementioned challenges, we propose a novel framework, FDGen (short for Fair Diffusion for Graph Generation) to ensure the fairness of the graph generation model. To the best of our knowledge, this is the first work to simultaneously mitigate multisource biases arising from sensitive attributes in graph generation models. Specifically, we first carry out a theoretical analysis investigating the sources of bias in the graph generation model. Guided by the theoretical findings, we proposed a novel fairness regularizer, which can be interpreted as encouraging each node to weightily aggregate representations of other nodes with different sensitive attributes of the central node and weightily subtract representations of other nodes with the same sensitive attribute, which can alleviate overassociation of the learned representation with sensitive attributes, resulting in fair representations with good utility ensured by smoothness. Based on this, we design a new diffusion-based fair graph generation framework that leverages the proposed regularizer to achieve fair graph generation. Our main contributions can be summarized as follows: i) Problem. We formalize the fair graph generation problem and identify unique challenges motivated by real applications. ii) Framework. We proposed a novel fairness-aware graph generation model to mitigate structural bias and feature bias during the graph generation while guaranteeing graph quality and enhancing fairness. iii) Experimental Evaluation. We conduct extensive experiments on four realworld datasets, demonstrating the superior performance of the proposed method over other state-of-the-art fairness methods. 2. Related Work Synthetic Graph Generation. Generating synthetic graphs has been a longstanding research topic (Bojchevski et al., 2018; Kong et al., 2023), with deep generative models proving particularly successful (Li et al., 2019). Existing approaches include one-shot methods, often based on VAEs (Simonovsky & Komodakis, 2018; Liu et al., 2018) or GANs (De Cao & Kipf, 2018; Bojchevski et al., 2018), which generate all edges simultaneously from latent embeddings but may degrade structural fidelity due to independence assumptions. In contrast, autoregressive models generate graphs by sequentially adding nodes and edges. These approaches, implemented through recurrent networks (Dai et al., 2020) or reinforcement learning (You et al., 2018), capture complex structural patterns and allow constraints during generation, but remain sensitive to node ordering (Huang et al., 2022). More recently, diffusionbased methods have emerged (Liu et al., 2019; Niu et al., 2020; Chen et al., 2023; Li et al., 2023), defining a Markov chain of diffusion steps that gradually add noise to data, then learn to reverse the inference path to generate data from noise (Sohl-Dickstein et al., 2015). However, fairness remains unexplored in synthetic graph generation, limiting these models use in high-stakes scenarios. This has created a need to develop fairer graph generation methods. Fairness-aware Graph Generation Model. Fairness is a widely-existing issue of graph learning systems and has received increasing research attention in recent years (Wang et al., 2025d;c; 2024a; Wang & Zhang, 2024; Zhang et al., 2024; Zhu et al., 2024). Despite these advances, most existing methods focus on classification tasks, leaving the domain of graph generation models largely unexplored (Zhang et al., 2025). To this end, a small number of works (Rahman et al., 2019; Wang et al., 2023c; Zheng et al., 2024) have started to investigate fairness in graph generation models, which can be divided into two categories: i) Fair link prediction and ii) Fair graph structural generation. Specif- FDGen: A Fairness-Aware Graph Generation Model Figure 1. A toy example of biases in graph generation is shown, where black lines represent original edges, gray dashed lines indicate removed inter-group edges, and orange lines denote newly added intra-group edges. ically, fair link prediction focuses on achieving unbiased predictions of dyadic relationships among graph nodes. For instance, FAIRLP (Li et al., 2022) was designed to modify the training graph to balance the distribution of intra-group and inter-group links while preserving the network characteristics of the graph. This enhancement improves the representation of underrepresented groups to achieve fair link prediction. Unlike fair link prediction, fair graph structural generation measures graph structural bias at the graph level and aims to reduce the distribution difference between the generated graph and the original graph s interand intragroup edges. For instance, Fair Gen (Zheng et al., 2024) achieves fair graph structural generation by incorporating parity constraints to minimize the difference in reconstruction loss between the generated graph and the original graph across different subgroups. However, these methods, focus solely on ensuring fairness in graph structure generation, neglecting potential biases in node information generation, which are crucial for achieving truly fair graph generation. In contrast to existing work, this paper proposes a fair graph generation model that addresses both graph structural bias and feature bias, with its design informed by theoretical analysis. In addition, the bias mitigation approach is flexible, allowing it to be applied in both link prediction models and generative models. 3. Notation In this paper, we formalize the graph generation problem in the context of an undirected graph G = (V, E, X), it would contain |V| nodes and |E| edges. The feature matrix for the graph is denoted as X R|V| d, where i-th row represents a d-dimensional feature vector of the i-th node vi. A {0, 1}n n is the adjacency matrix where Ai,j = 1 indi- cates that there exists edge ei,j E between node vi and vj, and Ai,j = 0 otherwise. In this paper, we assume that both ground-truth labels and sensitive attributes are binary variables for convenience. We let S {0, 1}n 1 to denote the binary sensitive attributes, where si is the sensitive attribute of vi. We use Sd = { vi V|si = 0} denotes the deprived group (e.g., female) and Sf = { vi V|si = 1} denotes the favored group (e.g., male). For node classification, each node is also associated with a one-hot ground-truth node label yi where ˆyi is the label of vi. We also assume yi = 1 denotes the granted label and yi = 0 denotes the rejected label. In addition, we let Gvi represent the ego graph of center node vi, which includes important neighbor nodes of the central node. 4. The Proposed Framework: FDGen This section introduces FDGen, a framework built upon the graph diffusion model (Kong et al., 2023) to mitigate both structural and feature bias for fair graph generation. Given the correlation between these biases, FDGen is developed to adaptively mitigate them during generation, leveraging the flexibility and tractable probability distributions of diffusion models. Specifically, bias types in graph generation are first defined, along with theoretical foundations for fairness regularizers (Section 4.1). Next, we describe how FDGen isolates sensitive information into independent components to measure generation discrepancies and apply fairness constraints (Section 4.2). Finally, the FDGen model and its training objectives are presented (Section 4.3). 4.1. Fair Graph Generation Regularizer We first examine the root causes of biases in graph generation, laying the groundwork for a fairness regularization FDGen: A Fairness-Aware Graph Generation Model strategy to mitigate them. Specifically, graph generation models are vulnerable to bias through two main mechanisms: i) nodes with the same sensitive attributes tend to form denser connections, creating structural bias, and ii) the node feature distributions often show systematic differences across demographic groups, leading to feature bias. In addition, these biases can be mutually reinforcing, as nodes with similar features are more likely to connect, and connected nodes influence each other s feature representations. Specific to graph diffusion models, these biases can be further amplified during generation. Specifically, a diffusion-based graph generation model defines a forward Markov transition kernel q xt | xt 1 to gradually corrupt the training data into a simple noise distribution. The model then learns a reverse denoising transition pθ xt 1 | xt using a neural network. During this reverse process, GNN-style message passing aggregates information from neighboring nodes to preserve both topological structure and node features. However, this message-passing mechanism can exacerbate existing biases through two effects: First, by smoothing representations of connected nodes, it strengthens segregation between different sensitive groups, amplifying graph structural bias. Second, it reinforces the association between node representations and sensitive attributes, exacerbating feature bias in the generated graphs. To this end, a theoretically grounded fairness regularizer is proposed to mitigate both structural and feature bias simultaneously. Starting with node representation differences (hl D), the commonly used approach is to measure them between groups as hl D = hl Sd hl Sf (hl Sd and hl Sf denote the node representations for deprived and favored groups, respectively). However, while this captures overall representation differences between subgroups, it fails to account for the distinct roles of sensitive information, as nodes with different sensitive attributes should have different sensitive-related components while maintaining similar sensitive-irrelevant components. To this end, we separate node representations into sensitive-related representations hl,S i and sensitive-irrelevant representations hl,S i . This separation allows us to minimize the differences in sensitiveirrelevant components (hl,S i ) while maintaining appropriate differences in sensitive-related components (hl,S i ), thereby preserving group identity while mitigating bias, as detailed in Definition 4.1. Definition 4.1 (Sensitive-irrelated Representation Discrepancy). Let VSd and VSf be two subgroups corresponding to distinct values Sd, Sf S of a sensitive attribute, with Sd = Sf. Suppose each node vi has a non-sensitive repre- sentation hl,S i at layer l, intended to be independent of the sensitive attribute S. We quantify any unintended discrepancy in this non-sensitive space via the Maximum Mean Discrepancy (MMD): h S (l) D = 1 |VSd|2 X vi,vj VSd k h S (l) i , h S (l) j + 1 |VSf |2 X vi,vj VSf k h S (l) i , h S (l) j 2 |VSd| |VSf | vi VSd vj VSd k h S (l) i , h S (l) j where k( , ) is a kernel function (e.g., RBF kernel). A large h S (l) D indicates substantial divergence between VS0 and VS1 the non-sensitive channel (i.e., sub node representation). Conversely, a small MMD implies a better alignment of non-sensitive embeddings, reducing unfair discrimination risk in downstream tasks. In addition, this measure can be simplified to a direct Euclidean distance between mean embeddings, and extends naturally to multiple sensitive attributes. Building on this representation separation measurement, FDGen proceeds in three steps. First, we analyze how representation discrepancy emerges during GNN-based aggregation, establishing an upper bound to understand its propagation through network layers (Theorem 4.2). Second, we demonstrate how this representation discrepancy directly influences group disparity, showing that reducing representation differences leads to improved demographic parity (Theorem 4.3). Finally, guided by these theoretical insights, we propose a fairness regularizer that simultaneously addresses both structural and feature bias by aligning non-sensitive representations while maintaining appropriate group-specific differences. We begin with the first step of analyzing representation discrepancy. During GNN message-passing, node representations are influenced by both their neighbors and the network structure. Theorem 4.2 quantifies this influence by providing an upper bound on the representation discrepancy between sensitive groups, revealing how bias can accumulate across layers (proof in Appendix). Theorem 4.2. The discrepancy h S (l) D between the representations of nodes in a sensitive group Sd and the rest of the nodes at the lth GNN layer can be upper bounded by: h S (l) D 3 1 |VSd| |VSf |2 + 1 |VSd|2 |VSf | i Sd, j Sf k h S l 1 i , h S l 1 j µ(d) l 1 µ(f) l 1 + µ(d) µ(f) N W(l) l + µ(d) l µ(f) l i where µ denotes the mean representation of a subgroup of nodes. Building on Theorem 4.2, we next analyze how representation disparity influences group fairness. Theorem 4.3 FDGen: A Fairness-Aware Graph Generation Model demonstrates that by minimizing sensitive-irrelevant representation discrepancy, we can effectively reduce group disparity in model predictions (detailed proof in Appendix). Theorem 4.3. For a classification task, minimizing the sensitive representation discrepancy between two sensitive groups upper-bounds the group disparities: DP = 1 |VSd| X 1 1 |VSf | X f(zµ(d))1 f(zµ(f))1 i=1 W(l) h S (l) D + 1 |VSf | j=1 W(l) h S (l) D Based on these theoretical results, we propose a fair regularizer LT that reduces MMD in sensitive-irrelevant node representations while adjusting interand intra-group connections: LT = a Lf + b Lg = a 1 |VSd|2 X vi,vj VSd k(h(l),S i , h(l),S j ) + 1 |VSf |2 X vi,vj VSf k(h(l),S i , h(l),S j ) 2 |VSd| |VSf | X vi VSd, vj VSf k(h(l),S i , h(l),S j ) + b Einter Ainter 2 F + Eintra Aintra 2 F where Lf denotes the node-level fairness term that aligns h(l) S across sensitive subgroups, and Lg captures the difference in modeling performance between interand intragroup edges, with a and b as hyperparameters that balance their contributions. In addition, Einter and Eintra denote predicted interand intra-group connections, while Ainter and Aintra indicate their ground-truth adjacency. In summary, LT aims to align non-sensitive representations across different groups, while pushing the predicted graph edges to better match intra-group and inter-group statistics. LT , integrated into FDGen, thus functions to mitigate both structural and feature biases in the generated graphs. 4.2. Identifying Sensitive-irrelevant Representations Equipped with the proposed fairness regularizer (Section 4.1), we now present how to disentangle node representations so as to isolate the components independent of sensitive attributes, thus enabling us to measure graph generation discrepancies and enforce fair graph generation regularizers. This process involves two main tasks: i) Decomposing each node representation into multiple components, where each component corresponds to a latent factor (e.g., age , occupation ), and ii) Identifying which components capture sensitive attribute-related information and which are largely free from it. In the first task, we aim to decompose the node embedding into multiple components, each representing a latent factor. When performing this task, using all neighbors to reconstruct the node component should be avoided, as only a subset carries useful information for the specific channel. For instance, if the latent factor is family , neighbors denoting close family members should have higher weight, while unrelated neighbors should be down-weighted. To achieve such selective neighbor usage, we extend GAT-like attention into a multi-channel setting via a neighbor-assigner mechanism. Specifically, we assume that if two nodes vi and vj exhibit higher similarity in the cth component space, then factor c is more likely to be responsible for their connection. For each channel c {1, 2, . . . , Nc}, we compute the edge weight (ωc vi,vj) between nodes vi and vj using dot-product attention to measure their similarity in channel c: ωc vi,vj = exp((hc vi)T hc vj) P vj N(vi) exp((hcvi)T hcvj) (4) where N(vi) denote the neighbors of vi. Using these edge weights (ωc vi,vj), we adaptively aggregate information from relevant neighbors for each component. The aggregation process to obtain hl+1 vi,c (the cth channel representation of node vi at layer l + 1) is defined as follows: hl+1 vi,c = σ X (vj) ˆ N(vi) ωc (vi,vj) ϕ hl vj,c, hl vi,c (5) where σ( ) is a non-linear activation. By focusing on relevant neighbors in each channel, the aggregation in Equation (5) encourages hl+1 vi,c to cluster nodes that share similar characteristics under factor c. However, although the above mechanism decomposes the node embedding into multiple channels, it does not guarantee that these channels themselves are mutually independent. For instance, channel c1 = age might still be correlated with channel c2 = nursing home . To address this, a disentangled constraint which adopts a distance covariance regularizer (Matteson & Tsay, 2017) that penalizes interchannel correlations is proposed as follows: d Cov2 Zc1, Zc2 d Cov2 Zc1, Zc1 d Cov2 Zc2, Zc2 FDGen: A Fairness-Aware Graph Generation Model where Nc denote the number of channels and Zk denotes the set of node embeddings in channel c (e.g., Zc1 = {h(c1,1), h(c1,2), . . . , h(c1,Nc1)}) and cov( ) is the distance covariance. With the decomposed channels, the second task identifies which channel captures sensitive attribute information. Theorem 4.4 demonstrates that in fully disentangled representations, only one channel can be associated with each sensitive attribute. Theorem 4.4. Suppose we have m channel representations {hc1, hc2, . . . , hc Nc } that are fully disentangled, meaning each channel is strictly independent from every other. Formally, I hci; hcj = 0, i = j. Then, at most one channel can capture the sensitive attribute. Hence, once we identify which channel is sensitive-related, the remaining channels can be treated as sensitive-attributeindependent. To this end, we train a channel-level discriminator that tries to predict a node s sensitive label ysi from each channel embedding. Specifically, for channel k, we feed hk vi into a classifier to produce the predicted probability ˆysi,k of the sensitive label, and define the classification loss as follows: ysi log ˆysi,c + 1 ysi log 1 ˆysi,c where ysi is the ground truth sensitive attribute label for node vi, and ˆysi,c is the prediction sensitive attribute. Channels that yield high classification accuracy for ysi are deemed sensitive-related, while those with low accuracy are considered non-sensitive. Consequently, the fairness regularizer (Section 4.1) can be applied specifically to the sensitive-irrelevant components, ensuring minimal distributional discrepancy across different groups in the generated graphs. 4.3. Fair Graph Generative Process This section presents the proposed fair graph generative model, FDGen, which incorporates both the fairness regularization constraint and the disentangled conditioning mechanism. The overall process is divided into two stages: i) the forward diffusion process, where the graph is gradually corrupted to obtain noisy samples, and ii) the reverse diffusion process, where we reconstruct the graph in a fairness-aware and disentangled manner. We will then describe each part in detail: Forward diffusion process. During the forward diffusion process, FDGen constructs noisy versions of the input graph by successively absorbing (masking) individual nodes and their edges according to a Markov chain. Specifically, rather than merely masking edges, FDGen learns a node ordering network that, at each diffusion step t, selects a node vi to absorb. In an autoregressive fashion, the node decay ordering σ is sampled from qϕ(σ | G0 = {X0, A0}), where qϕ( | G0) is a conditional probability distribution over possible node orderings σ. Here, X0 and A0 denote the initial node features and graph structure at time step 0. At subsequent time steps, t, Xt, and At represent the node features and graph structure after absorbing one node. This process continues iteratively until the entire graph is absorbed. To systematically select which nodes to absorb at each step, the diffusion ordering network follows a recurrent structure: qϕ(σ | G0) = Y t qϕ σt | G0, σ(t) σt | Gt+1 where t is drawn uniformly from {1, . . . , n} and Oπ(>t) σt indicates the node vσt and its edges with any previously unmasked nodes {σt+1, . . . , σn}. While Equation 11 guides the model to learn a generative process that reconstructs node features and edges, it does not explicitly address bias nor disentanglement. To ensure fairness across different groups and decompose node representations into multiple channels (Section 4.2), for a node vi, the node embedding at the lth layer follows Equation 5. Building on this, we integrate the proposed fairness constraint into the denoising network pθ(Gt | Gt+1). Specifically, we use Lf to reduce feature discrepancies among different sensitive groups and Lg to constrain inter-group and intra-group edge biases. Hence, we augment the likelihood term in Equation 11 with these fairness and disentanglement losses. During each reverse diffusion step, the aggregator (Equation 5) updates node embeddings split by channel, and we measure fairness and disentanglement on the resulting representations. Thus, the final training objective is: Ltotal = LP + λ1 Lf + λ2 Lg + λ3 Ld + λ4 LD (12) where Ltrain ensures node and edge reconstruction, Lf and Lg mitigate bias in node features and topology, and Ld with LD enforces disentangled channels and isolates the sensitive attribute. Note that FDGen preserves S throughout training and sampling (i.e., S is initialized according to its original distribution at inference time) so that FDGen can capture how sensitive attributes correlate with graph structure without amplifying undesirable biases. 5. Experiment Datasets. Four real-world fairness datasets, namely Cora, Citeseer, Photo, and Computer, are used in our experiments. We provide a short overview of these datasets as follows: In the Cora and Citeseer datasets (Sen et al., 2008), nodes represent papers, edges capture citation relationships between papers, node features are bag-of-words vectors of keywords, and labels indicate the research field of the papers. The Photo and Computer datasets (Shchur et al., 2018) are segments of the Amazon co-purchase graph, where nodes represent products, edges show that two products are frequently purchased together, node features are bag-of-words vectors derived from product reviews, and labels correspond to the product category. Table 1 summarizes the statistics of these datasets. Table 1. Summary of the datasets used in the experiments. Dataset Cora Citeseer Photo Computer # Nodes 2,708 3,327 7,650 13,752 # Edges 10,556 9,228 238,163 491,722 # Features 1,433 3,703 745 767 # Average Degree 3.89 2.77 31.13 35.75 Sensitive Attribute Topic Topic Product Categories Product Categories Baselines. We compare the proposed method with the following baselines: GRAPHARM (Kong et al., 2023), Fair Adj (Li et al., 2021), FG2AN (Wang et al., 2023c), Fair Gen (Zheng et al., 2024) and Fair Wire (Kose & Shen, 2024b). Evaluation Metrics. We evaluate FDGen s performance across two aspects: 1) Node Classification Performance: We use accuracy and F1 scores to evaluate node classification utility, along with DP (Dwork et al., 2012) and EO (Hardt et al., 2016) to assess prediction fairness. 2) Generated Graph Quality: Following (Kong et al., 2023), we measure generation quality using maximum mean discrepancy (MMD) between generated and input graphs, specifically computing MMD for degree distribution and clustering coefficient. To evaluate graph structural fairness, we propose metrics, fair degree distribution and fair clustering coefficient, that measure disparity between subgroups. These are computed as: f(GSd, GSd) f(GSf , GSf ), where f( ) denotes the MMD value for degree distribution or clustering coefficient, and G represents the generated graph. 5.1. Experiment Results Graph Generation Results. We evaluate our generative models in terms of both quality and fairness, with results shown in Figure 2. FDGen demonstrates strong performance in graph generation, achieving comparable or better quality than baseline methods while significantly improving fairness metrics. The strong performance can be attributed to two key factors. First, FDGen maintains group identity information through decomposition learning while reducing differences in sensitive-irrelevant attributes. This approach enables FDGen to achieve fairness with minimal compromise to synthetic graph quality compared to other fairnessaware baselines. Second, by simultaneously addressing both structural and feature bias, FDGen better mitigates group differences in generated graphs compared to existing methods that focus solely on structural bias. Overall, these experi- FDGen: A Fairness-Aware Graph Generation Model Figure 2. Graph generation results on Cora, Citeseer, Photo and Computer datasets. mental results demonstrate that FDGen effectively improves fairness while maintaining graph generation quality. Table 2. Node classification results on the Cora dataset. Cora dataset ACC (%) DP (%) EO(%) Original-GCN 82.43 0.34 27.01 1.38 25.21 1.13 GRAPHARM-GCN 81.03 0.23 25.21 1.38 21.31 1.43 Fair Adj-GCN 77.77 1.64 17.13 6.36 13.96 2.24 FG2AN-GCN 78.10 0.81 18.66 4.30 14.05 0.32 Fair Gen-GCN 79.54 1.56 14.16 0.89 13.35 1.24 Fair Wire-GCN 78.21 1.03 14.76 0.24 13.65 0.51 FDGen-GCN 80.05 1.03 13.88 0.24 11.95 0.37 Node Classification Results. We evaluate both the accuracy and fairness of node classification using generated graphs. For this evaluation, we use GCN as our base model, training it on generated graphs and testing its predictive performance. Using the Cora dataset as a case study, Table 2 shows the comparison between FDGen and baseline methods on the node classification task. The results demonstrate that graphs generated by FDGen consistently lead to better classifier performance in terms of both accuracy and fairness. This improvement stems from FDGen s ability to mitigate both structural and feature bias during graph generation, thus reducing bias propagation from raw graph data to downstream tasks. Ablation Study. To verify the effectiveness of our proposed modules, we conduct an ablation study examining two variants of FDGen. First, we analyze the impact of identifying sensitive-irrelevant representations by creating FDGen-WD, which applies fair regularization directly to complete node representations. As shown in Figure 3, FDGen-WD shows Figure 3. Ablation study results for FDGen, FDGen-WD, and FDGen-WS. reduced graph generation quality compared to the complete FDGen model. This decline in performance occurs because eliminating group identity information reduces the authenticity of generated graphs. Second, we study the effect of mitigating only feature bias by creating FDGen-WS. Results in Figure 3 show that FDGen-WS achieves worse fairness compared to the complete FDGen model. While nodes may have similar sensitive-irrelevant attributes, their connections remain influenced by sensitive-related information, leading to increased connectivity between nodes sharing sensitive attributes and introducing structural bias. However, FDGen-WS maintains better graph generation quality than FDGen-WD. Overall, these findings underscore the necessity of our design choices. 6. Conclusion Generating synthetic graphs that capture structural characteristics of real data has gained increasing attention as a solution to scalability and privacy challenges in real-world networks. However, fairness in graph generation models remains an important yet understudied problem. This work addresses this gap by investigating bias in graph data and proposing FDGen, a framework that mitigates both structural and feature bias. Our theoretically grounded fairness regularizer effectively reduces identified bias factors, as demonstrated through extensive experiments comparing FDGen with both fairness-agnostic and fairness-aware baselines on real and synthetic graphs. These results establish a foundation for developing fair graph generation models and open possibilities for future work on a comprehensive study of graph learning. FDGen: A Fairness-Aware Graph Generation Model Acknowledgements This work was supported in part by the National Science Foundation (NSF) under Grant No. 2404039. Impact Statement Graph generation models are increasingly used in real-world applications spanning from social networks to financial systems. When these models inherit and amplify societal biases, they can perpetuate discrimination and unfair treatment of disadvantaged groups. Our work advances fairness in artificial intelligence by developing methods to identify and mitigate both structural and feature bias in generated graphs. This research has particular significance for high-stakes applications such as credit scoring and healthcare, where biased graph generation could disproportionately affect vulnerable populations. By enabling fairer graph generation while maintaining data utility, our work contributes to more equitable AI systems and provides a foundation for future research on structural fairness in graph learning. Akoglu, L., Mc Glohon, M., and Faloutsos, C. Rtm: Laws and a recursive generator for weighted time-evolving graphs. In 2008 Eighth IEEE International Conference on Data Mining, pp. 701 706. IEEE, 2008. Bojchevski, A., Shchur, O., Z ugner, D., and G unnemann, S. Netgan: Generating graphs via random walks. In International conference on machine learning, pp. 610 619. PMLR, 2018. Chakrabarti, D. and Faloutsos, C. Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1):2 es, 2006. Chen, X., He, J., Han, X., and Liu, L.-P. Efficient and degreeguided graph generation via discrete diffusion modeling. ar Xiv preprint ar Xiv:2305.04111, 2023. Dai, H., Nazi, A., Li, Y., Dai, B., and Schuurmans, D. Scalable deep generative modeling for sparse graphs. In International conference on machine learning, pp. 2302 2312. PMLR, 2020. De Cao, N. and Kipf, T. Molgan: An implicit generative model for small molecular graphs. ar Xiv preprint ar Xiv:1805.11973, 2018. Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214 226, 2012. Grover, A., Zweig, A., and Ermon, S. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pp. 2434 2444. PMLR, 2019. Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016. Hofstra, B., Corten, R., Van Tubergen, F., and Ellison, N. B. Sources of segregation in social networks: A novel approach using facebook. American Sociological Review, 82(3):625 656, 2017. Huang, H., Sun, L., Du, B., Fu, Y., and Lv, W. Graphgdp: Generative diffusion processes for permutation invariant graph generation. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 201 210. IEEE, 2022. Kang, J., Zhu, Y., Xia, Y., Luo, J., and Tong, H. Rawlsgcn: Towards rawlsian difference principle on graph convolutional network. In Proceedings of the ACM Web Conference 2022, pp. 1214 1225, 2022. Kong, L., Cui, J., Sun, H., Zhuang, Y., Prakash, B. A., and Zhang, C. Autoregressive diffusion model for graph generation. In International conference on machine learning, pp. 17391 17408. PMLR, 2023. Kose, O. D. and Shen, Y. Fairgat: Fairness-aware graph attention networks. ACM Transactions on Knowledge Discovery from Data, 18(7):1 20, 2024a. Kose, O. D. and Shen, Y. Fairwire: Fair graph generation. ar Xiv preprint ar Xiv:2402.04383, 2024b. Li, M., Kreaˇci c, E., Potluru, V. K., and Li, P. Graphmaker: Can diffusion models generate large attributed graphs? ar Xiv preprint ar Xiv:2310.13833, 2023. Li, P., Chien, I., and Milenkovic, O. Optimizing generalized pagerank methods for seed-expansion community detection. Advances in Neural Information Processing Systems, 32, 2019. Li, P., Wang, Y., Zhao, H., Hong, P., and Liu, H. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021. Li, Y., Wang, X., Ning, Y., and Wang, H. Fairlp: Towards fair link prediction on social network graphs. In Proceedings of the international AAAI conference on web and social media, volume 16, pp. 628 639, 2022. Liu, J., Kumar, A., Ba, J., Kiros, J., and Swersky, K. Graph normalizing flows. Advances in Neural Information Processing Systems, 32, 2019. FDGen: A Fairness-Aware Graph Generation Model Liu, Q., Allamanis, M., Brockschmidt, M., and Gaunt, A. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, 31, 2018. Matteson, D. S. and Tsay, R. S. Independent component analysis via distance covariance. Journal of the American Statistical Association, 112(518):623 637, 2017. Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020. Rahman, T., Surma, B., Backes, M., and Zhang, Y. Fairwalk: Towards fair graph embedding. 2019. Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T. Collective classification in network data. AI magazine, 29(3):93 93, 2008. Shchur, O., Mumme, M., Bojchevski, A., and G unnemann, S. Pitfalls of graph neural network evaluation. ar Xiv preprint ar Xiv:1811.05868, 2018. Shumovskaia, V., Fedyanin, K., Sukharev, I., Berestnev, D., and Panov, M. Linking bank clients using graph neural networks powered by rich transactional data: Extended abstract. In 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pp. 787 788, 2020. Simonovsky, M. and Komodakis, N. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pp. 412 422. Springer, 2018. Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pp. 2256 2265. PMLR, 2015. Wang, X., He, X., Wang, M., Feng, F., and Chua, T.-S. Neural graph collaborative filtering. In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pp. 165 174, 2019. Wang, Z. and Zhang, W. Group fairness with individual and censorship constraints. In 27th European Conference on Artificial Intelligence, 2024. Wang, Z., Narasimhan, G., Yao, X., and Zhang, W. Mitigating multisource biases in graph neural networks via real counterfactual samples. In 2023 IEEE International Conference on Data Mining (ICDM), pp. 638 647. IEEE, 2023a. Wang, Z., Saxena, N., Yu, T., Karki, S., Zetty, T., Haque, I., Zhou, S., Kc, D., Stockwell, I., Bifet, A., et al. Preventing discriminatory decision-making in evolving data streams. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency (FAcc T), 2023b. Wang, Z., Wallace, C., Bifet, A., Yao, X., and Zhang, W. Fg2an: Fairness-aware graph generative adversarial networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 259 275. Springer Nature Switzerland, 2023c. Wang, Z., Chu, Z., Blanco, R., Chen, Z., Chen, S.-C., and Zhang, W. Advancing graph counterfactual fairness through fair representation learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 40 58. Springer Nature Switzerland, 2024a. Wang, Z., Qiu, M., Chen, M., Salem, M. B., Yao, X., and Zhang, W. Toward fair graph neural networks via real counterfactual samples. Knowledge and Information Systems, pp. 1 25, 2024b. Wang, Z., Ulloa, D., Yu, T., Rangaswami, R., Yap, R., and Zhang, W. Individual fairness with group constraints in graph neural networks. In 27th European Conference on Artificial Intelligence, 2024c. Wang, Z., Chu, Z., Viet Doan, T., Wang, S., Wu, Y., Palade, V., and Zhang, W. 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, pp. 28485 28493, 2025a. Wang, Z., Hoang, N., Zhang, X., Bello, K., Zhang, X., Iyengar, S. S., and Zhang, W. Towards fair graph learning without demographic information. In The 28th International Conference on Artificial Intelligence and Statistics, 2025b. Wang, Z., Liu, F., Pan, S., Liu, J., Saeed, F., Qiu, M., and Zhang, W. fairgnn-wod: Fair graph learning without complete demographics. In Proceedings of the 34th International Joint Conference on Artificial Intelligence, 2025c. Wang, Z., Wu, A., Moniz, N., Hu, S., Knijnenburg, B., Zhu, X., and Zhang, W. Towards fairness with limited demographics via disentangled learning. In Proceedings of the 34th International Joint Conference on Artificial Intelligence, 2025d. FDGen: A Fairness-Aware Graph Generation Model Wang, Z., Yin, Z., Yang, L., Zhuang, J., Yu, R., Kong, Q., and Zhang, W. Fairness-aware graph representation learning without complete demographic information. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer Nature Switzerland, 2025e. Wang, Z., Yin, Z., Yap, R., and Zhang, W. Ai fairness beyond complete demographics: Current achievements and future directions. In 28th European Conference on Artificial Intelligence, 2025f. Wang, Z., Yin, Z., Yap, R., Zhang, X., Hu, S., and Zhang, W. Redefining fairness: A multi-dimensional perspective and integrated evaluation framework. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer Nature Switzerland, 2025g. Wang, Z., Yin, Z., Zhang, Y., Yang, L., Zhang, T., Pissinou, N., Cai, Y., Hu, S., Li, Y., Zhao, L., et al. Fg-smote: Towards fair node classification with graph neural network. ACM SIGKDD Explorations Newsletter, 26(2):99 108, 2025h. You, J., Liu, B., Ying, Z., Pande, V., and Leskovec, J. Graph convolutional policy network for goal-directed molecular graph generation. Advances in neural information processing systems, 31, 2018. Yu, H., Sun, X., Solvang, W. D., and Zhao, X. 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. Zhang, G., Cheng, D., Yuan, G., and Zhang, S. Learning fair representations via rebalancing graph structure. Information Processing & Management, 61(1):103570, 2024. Zhang, W. Ai fairness in practice: Paradigm, challenges, and prospects. Ai Magazine, 45(3):386 395, 2024. Zhang, W. and Ntoutsi, E. Faht: an adaptive fairness-aware decision tree classifier. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 1480 1486, 2019. Zhang, W. and Weiss, J. C. Longitudinal fairness with censorship. In proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 12235 12243, 2022. Zhang, W., Hernandez-Boussard, T., and Weiss, J. Censored fairness through awareness. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 14611 14619, 2023a. Zhang, W., Wang, Z., Kim, J., Cheng, C., Oommen, T., Ravikumar, P., and Weiss, J. Individual fairness under uncertainty. In 26th European Conference on Artificial Intelligence, pp. 3042 3049, 2023b. Zhang, W., Zhou, S., Walsh, T., and Weiss, J. C. Fairness amidst non-iid graph data: A literature review. AI Magazine, 46(1):e12212, 2025. Zheng, L., Zhou, D., Tong, H., Xu, J., Zhu, Y., and He, J. Fairgen: Towards fair graph generation. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 2285 2297. IEEE, 2024. Zhu, Y., Li, J., Bian, Y., Zheng, Z., and Chen, L. 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, pp. 4688 4699, 2024. FDGen: A Fairness-Aware Graph Generation Model A. Proof of Theorem 4.2 To simplify the notation, we use hl to denote the input representations, and hl+1 to denote the output representations. The considered disparity measure follows as: h S (l) D = MMD {h S l i | vi VSd}, {h S l i | vi VSf } (13) Expand under the RBF kernel function: k(x, y) = exp γ x y 2 , we can get: h S (l) D = 1 |VSd|2 X vi,vj VSd k hl + 1 |VSf |2 X vi,vj VSf k hl 2 |VSd| |VSf | vi VSd vj VSf Building on this, and given that Graph Attention Networks (GAT) adopt the message passing by assigning different weights to neighbor nodes as: vj N(i) a(l 1) ij h(l 1) j with a(l 1) ij = exp e(l 1) ij vj N(i) exp e(l 1) ij (15) Hence, we can re-write the disparity as follows: h(l) i = Xi + X u Ni Sd a(l 1) iu h(l 1) u + X u Ni Sf a(l 1) iu h(l 1) u u Sd k h(l 1) u , h(l 1) i h(l 1) u + 1 Nd Nf u Sf k h(l 1) u , h(l 1) i h(l 1) u u Sd k h(l 1) u , h(l 1) i 1 Nd Nf u Sf k h(l 1) u , h(l 1) i h(l 1) i Given that each node u Sd, the node representation h(l) u subject to µ(d) i l h(l) u µ(d) i + l (Kose & Shen, 2024a), where the parameter l serves as a per-layer tolerance indicating how far the representation is allowed to deviate from µ(d) i along each coordinate. If u instead belongs to Sf, a parallel condition applies with µ(f) i l, anchoring h(l) u around the group mean µ(f) i . Building on this, we assume the node representation within a controlled region near its respective group s mean. Hence, we can define the h(l) i as: u Ni Sd a(l 1) iu h(l 1) u + X u Ni Sf a(l 1) iu h(l 1) u u Sd k h(l 1) u , h(l 1) i h(l 1) u + 1 Nd Nf u Sf k h(l 1) u , h(l 1) i µ(f) l 1 u Sd k h(l 1) u , h(l 1) i h(l 1) i 1 Nd Nf u Sf k h(l 1) u , h(l 1) i µ(d) l 1 N W(l) l + µ(d) l µ(f) l i# Building on this, for nodes vi Sd, we have: FDGen: A Fairness-Aware Graph Generation Model i Sd h(l) i µ(d) + µ(d) l 1 + 1 Nd i Sd α(l 1) i µ(f) l 1 µ(d) l 1 + 1 N 2 d Nf u Sf k h(l 1) u , h(l 1) i µ(f) l 1 µ(d) l 1 h 2 N W(l) l + µ(d) l µ(f) l i# We can do similar for Sf. j Sf h(l) j µ(f) + µ(f) l 1 + 1 Nf j Sf α(l 1) j µ(d) l 1 µ(f) l 1 + 1 Nd N 2 f u Sd k h(l 1) u , h(l 1) j µ(d) l 1 µ(f) l 1 h 2 N W(l) l + µ(d) l µ(f) l i# We define the upper bound of the consequent representation discrepancy on node representation between two sensitive groups as follows: i Sd h(l) i 1 Nf X j Sf h(l) j u Ni Sopp(vi) a(l 1) iu + 1 Nf X u Nj Sopp(vj) a(l 1) ju 1 Nd N2 f + 1 N2 d Nf j Sf k h(l 1) i , h(l 1) j µ(d) l 1 µ(f) l 1 + µ(d) µ(f) + h 2 N W(l) l + µ(d) l µ(f) l i u Ni Sopp(vi) a(l 1) iu + 1 Nf X u Nj Sopp(vj) a(l 1) ju + 1 1 Nd N2 f + 1 N2 d Nf j Sf k h(l 1) i , h(l 1) j µ(d) l 1 µ(f) l 1 + µ(d) µ(f) + h 2 N W(l) l + µ(d) l µ(f) l i 3 1 Nd N 2 f + 1 N 2 d Nf j Sf k h(l 1) i , h(l 1) j µ(d) l 1 µ(f) l 1 + µ(d) µ(f) + h 2 N W(l) l + µ(d) l µ(f) l i Noting that each node representation hi can be decomposed as hi = hi S h Si (sensitive vs. non-sensitive part), we obtain the analogous upper bound for the sensitive-irrelevant representation h(l) S,D. Hence, the representation discrepancy between different sensitive groups in the non-sensitive subspace is also bounded by: S,D 3 1 |VSd| |VSf |2 + 1 |VSd|2 |VSf | X i Sd, j Sf k(hl 1 S,j ) µ(d) l 1 µ(f) l 1 + µ(d) µ(f) N W(l) l + µ(d) l µ(f) l i (20) which concludes the proof. FDGen: A Fairness-Aware Graph Generation Model B. Proof of Theorem 4.3 For binary classification, statistical parity is defined as: SP = |P(ˆy = 1|s = 0) P(ˆy = 1|s = 1)|. We consider the binary classification task and examine the properties of the Softmax function in this context. Let P1 and P2 represent the probabilities of class 1 (c1) and class 2 (c2), respectively. The function Softmax( ) is Lipschitz continuous with a Lipschitz constant L. Due to this Lipschitz continuity, the difference in output probabilities can be bounded by the difference in input vectors: f(hi) f(hj) = |P1 P2| + |(1 P1) (1 P2)| = 2|P1 P2| L hi hj (21) where hi is the node representation for vi Sd and hj is the node representation for vj Sf. Building on this, we can rewrite the statistical parity as follows: where zi = W lh(l) i , and W (l) is the weight matrix at layer l. As we discuss above, from Equation 21 and using node vi from the group Sd as an example, we can get: 2 f(zi)1 f(zµ(d))1 L zi zµ(d) (23) Therefore, we can rewrite it as: 2 zi zµ(d) f zi 2 zi zµ(d) (24) Let zi = W(l)h(l) i for node i, and zµ(d) = W(l)µ(d) l , zµ(f) = W(l)µ(f) l be the group means in logits space. f(zµ(d))1 f(zµ(f))1 1 Nd 2 zi zµ(d) 1 Nf i Sd f(zi)1 1 Nf X j Sf f(zj)1 f(zµ(d))1 f(zµ(f))1 + 1 Nd 2 zi zµ(d) + 1 Nf Consider the h D we obtained: zi zµ(d) = W(l)(h(l) i µ(d) i ) " 3 1 Nd N 2 f + 1 N 2 d Nf q Sf k(h(l 1) p , h(l 1) q ) µ(d) l 1 µ(f) l 1 + µ(d) µ(f) + h 2 N l + µ(d) l µ(f) l i# (25) and we can get similiar for zi zµ(f) . FDGen: A Fairness-Aware Graph Generation Model Building on this, we re-express the upper bound. i Sd f(zi)1 1 Nf j Sf f(zj)1 f(zµ(d))1 f(zµ(f))1 i=1 zi zµ(d) + 1 j=1 zj zµ(f) (26) Here we have combined the group center difference f(zµ(d))1 f(zµ(f))1 with the Lipschitz offset 1 Nd P zi zµ(d) + 1 Nf P zj zµ(f) , factoring out L We note that zi zµ(d) = W(l)(h(l) i µ(d) l ) W(l) h(l) i µ(d) l (27) Similarly for zj zµ(f). According to (1), we know h(l) i µ(d) l 3 1 Nd N2 f + 1 N2 d Nf q Sf k h(l 1) p , h(l 1) q µ(d) l 1 µ(f) l 1 (28) + µ(d) µ(f) + h 2 N W(l) l + µ(d) l µ(f) l i By Theorem 4.2, h(l) i µ(d) l is itself bounded by a term involving µ(d) l 1 µ(f) l 1 , plus L (l 1) and C z . Thus, zi zµ(d) W(l) h 3 1 Nd N2 f + 1 N2 d Nf q Sf k h(l 1) p , h(l 1) q µ(d) l 1 µ(f) l 1 (29) + µ(d) µ(f) + h 2 N l + µ(d) l µ(f) l i Similarly for zj zµ(f) . Plugging these bounds into (24) and summing over vi Sd, vj Sf yields: DP f(zµ(d))1 f(zµ(f))1 3 1 Nd N2 f + 1 N2 d Nf p,q k(h(l 1) p , h(l 1) q ) µ(d) l 1 µ(f) l 1 + µ(d) µ(f) + h 2 N l + µ(d) l µ(f) l i 3 1 Nd N2 f + 1 N2 d Nf p,q k(h(l 1) p , h(l 1) q ) µ(d) l 1 µ(f) l 1 + µ(d) µ(f) + h 2 N l + µ(d) l µ(f) l i i We can rewrite it as: FDGen: A Fairness-Aware Graph Generation Model i Sd f(zi)1 1 Nf X j Sf f(zj)1 f(zµ(d))1 f(zµ(f))1 + L i=1 zi zµ(d) + 1 Nf j=1 zj zµ(f) f(zµ(d))1 f(zµ(f))1 + L i=1 W(l) h S (l) D + 1 Nf j=1 W(l) h S (l) D = f(zµ(d))1 f(zµ(f))1 + L 2 W(l) h S (l) D Nd Nd + Nf = f(zµ(d))1 f(zµ(f))1 + L W(l) h S (l) D Building on this analysis, we can derive an upper bound for the bias caused by sensitive-irrelevant node representations disparity. DP = 1 |VSd| X 1 1 |VSf | X f(zµ(d))1 f(zµ(f))1 i=1 W(l) h S (l) D + 1 |VSf | j=1 W(l) h S (l) D This completes the proof. C. Proof of Theorem 4.4 Assume there exist two distinct channels hci and hcj (i = j) that both encode the sensitive attribute S. That is, I(hci; S) > 0 and I(hcj; S) > 0. Hence, we can write hci = fi(S) + εi, hcj = fj(S) + εj (33) for some non-trivial functions fi( ), fj( ) and noise terms εi, εj. Because both channels depend on S, we have I hci; hcj = I fi(S) + εi; fj(S) + εj I fi(S); fj(S) > 0 (34) which contradicts the independence assumption I(hci; hcj) = 0. Therefore, under the requirement that all channels remain mutually independent, at most one channel can capture S. D. Experimental Settings We compare FDGen with five state-of-the-art methods: performance-driven GRAPHARM (Kong et al., 2023) and fairnessaware models including Fair Adj (Li et al., 2021), FG2AN (Wang et al., 2023c), Fair Gen (Zheng et al., 2024), and Fair Wire (Kose & Shen, 2024b). A brief overview of these baselines is as follows: GRAPHARM: GRAPHARM is an autoregressive diffusion-based model for graph generation that directly operates in the discrete graph space by sequentially masking one node and its edges until the graph is empty. It employs a learned FDGen: A Fairness-Aware Graph Generation Model node ordering strategy for more accurate likelihood approximation and achieves faster generation than existing graph diffusion models by limiting the number of diffusion steps to the number of nodes in the graph. Fair Adj: Fair Adj updates the normalized adjacency matrix to better satisfy dyadic fairness, which requires that link predictions be independent of the sensitive attributes from both vertices. This approach lessens the statistical gap between intra-group and inter-group link predictions while preserving as much predictive accuracy as possible. FG2AN: FG2AN is a fair graph generative model that addresses both node-level and structural fairness in creating synthetic graphs through adversarial training. It introduces tailored fairness metrics and a meta-strategy that reduces computational costs while handling multiple types of bias in the data. Fair Gen: FAIRGEN is a deep generative model that integrates label guidance and fairness objectives to produce synthetic graphs under limited labeled data. It uses a self-paced learning strategy and a novel context sampling approach to progressively learn the behaviors of protected and unprotected groups while preserving class memberships. Fair Wire: Fair Wire is a diffusion-based fair graph generation framework that uses a new fairness regularizer, to reduce structural bias in link prediction and synthetic graph creation. It captures the connections between synthetic sensitive attributes and the graph topology, allowing fair model training without revealing real sensitive data.