Learning Counterfactual Fairness from Authentic Generation

1 Introduction

Graph Neural Networks (GNNs) have demonstrated effectiveness across various graph tasks [Kipf and Welling, 2016; Zhao et al., 2022; Wu et al., 2020], leading to their successful application in high-risk decision-making systems such as social media analysis [Leonelli et al., 2021], and criminal justice [Berk et al., 2021]. For example, GNNs can assist financial institutions in critical functions like evaluating credit card applications or making loan approval decisions [Wang et al., 2021]. Despite their success, there is a growing concern that GNNs may inherit or even amplify discrimination and social bias present in the training data, leading to unfair treatment of subgroups defined by sensitive attributes such as gender, age, region, and race [Liang et al., 2022]. For instance, a hiring system powered by GNNs unfairly disadvantaged applicants from certain ethnic groups, raising serious ethical risks about the deployment of these models in real-world decision-making scenarios [Chen et al., 2024a; Wang et al., 2025g].

∗Corresponding author.

To this end, many efforts have recently been devoted to ensuring fairness in graph-based prediction models [Wang et al., 2026b; Wang et al., 2026a; Wang et al., 2026d; Wang et al., 2025b]. Among these efforts, counterfactual fairness stands out by explicitly leveraging causal mechanisms, enabling the modeling and elimination of discrimination at the individual level using Pearl's structural causal models [Pearl, 2009]. The core idea behind the counterfactual fairness is that predictions for an individual should remain consistent across hypothetical scenarios where their sensitive attributes are altered [Kusner et al., 2017]. For example, consider a scenario in which a loan application from an applicant belonging to a minority group is rejected. To evaluate counterfactual fairness, one would need to generate a realistic "what-if" scenario (a counterfactual instance) by altering only the sensitive attribute (such as ethnicity) while keeping all other relevant factors fixed, and verify whether the decision remains unchanged [Zhang and Weiss, 2022]. To operationalize this concept in graph data, most existing methods generate these counterfactual instances either by directly flipping sensitive attributes or by employing graph-generation models [Wang et al., 2023a]. For instance, NIFTY [Agarwal et al., 2021] creates counterfactual samples by perturbing sensitive attributes and maximizing the similarity between original and perturbed representations to achieve invariance concerning sensitive attributes.

Despite their valuable contributions, these existing approaches often rely on an unrealistic assumption, that all observed factors are directly influenced by sensitive attributes, potentially leading to unrealistic counterfactual instances in practical scenarios. As illustrated in Figure 1, existing methods typically assume a simplistic scenario where the sensitive attribute (S) directly affects all node features (X) and graph structures (A). For example, consider gender as a sensitive attribute in a hiring scenario: it can directly influence sensitive-related node features (XS) such as physical characteristics) and sensitive-related graph structure (AS) such as gender-based social connections, but it does not causally affect sensitive-irrelevant node features (XS ) and sensitiveirrelevant graph structure (AS ), like professional skills and classmate relationship. Consequently, altering gender without accurately identifying and isolating sensitive-related information could unintentionally modify irrelevant features, leading to unrealistic counterfactual instances.

Despite the importance of learning counterfactual fairness through authentic generation, this area remains significantly underexplored and presents substantial challenges: i) Difficulty in accurately identifying which information should be modified when generating counterfactuals. In real-world graph data, sensitive attributes typically influence only a subset of node features and structural patterns, while many other factors are unrelated or only spuriously correlated. Without explicitly distinguishing sensitive-related information from sensitive-irrelevant information, counterfactual generation may unintentionally alter factors that should remain unchanged, resulting in implausible or invalid counterfactual instances. Accurately determining what to change and what to preserve is, therefore, a core challenge for authentic counterfactual generation. ii) Difficulty in handling complex interactions between node features and graph structures during counterfactual generation. Even with accurate identification of sensitive-related and sensitiveirrelevant information, generating realistic counterfactual instances remains challenging due to the complex interdependencies between node attributes and graph structure. Node features and graph connectivity mutually influence each other, making it difficult to alter one aspect without inadvertently disrupting coherence in the other. This interconnected nature requires an integrated approach to maintain consistency and realism in counterfactual instances. iii) Ensuring coherent and realistic counterfactual generation through integrated graph structural and feature-level disentanglement. Effective counterfactual fairness requires simultaneous interventions on sensitive-related information of both node features and graph connectivity, while preserving sensitive-irrelevant aspects. Achieving this balance is inherently challenging, as it demands coordinated inference and precise alignment between structural and feature-level disentanglement mechanisms to ensure causal consistency and realism in generated counterfactual instances.

To address the above challenges, we introduce a novel causal framework for graph counterfactual fairness, named GCFair, which explicitly addresses the critical problem of accurately generating authentic counterfactual instances by jointly disentangling sensitive-related from sensitiveirrelevant information in node features and graph structures. To the best of our knowledge, this is the first work that simultaneously achieves structural and feature-level disentanglement within graph neural networks for authentic counterfactual fairness. Specifically, GCFair utilizes a causal-effect variational autoencoder framework to explicitly encode and separate sensitive-related from sensitive-irrelevant latent factors in node features, guided by dedicated inference networks and an adversarial correlation regularizer. In parallel, we introduce an information bottleneck objective designed to isolate sensitive-related graph structural patterns within the observed graph, effectively disentangling them from sensitiveirrelevant structural information. Through this coordinated approach, GCFair ensures that counterfactual interventions selectively modify only the latent factors and structural components directly influenced by sensitive attributes, preserving causal consistency and realism in generated counterfactual instances. The major contributions of this paper are summarized as follows: i) We introduce a principled disentanglement strategy that accurately identifies and isolates sensitive-related information within both node features and graph structures. ii) We propose GCFair, a novel framework for graph counterfactual fairness, which builds on our proposed disentanglement strategy to generate authentic counterfactual graphs by selectively modifying only sensitive-related information. iii) We validate the effectiveness of our model on three real-world datasets, and results indicate our model outperforms a variety of state-of-the-art baselines.

2 RelatedWork

Counterfactual Fairness in Graph Learning. Fairness in graph learning has attracted increasing attention, with numerous studies addressing this challenge in recent years [Wang et al., 2025f; Wang et al., 2022; Wang et al., 2025c]. Among them, counterfactual fairness has attracted a surge of attentions because of its strong capability of modeling how discrimination arises and is exhibited [Zhang et al., 2025]. Most existing counterfactual fairness studies [Ma et al., 2022; Chen et al., 2024b] focus on generating counterfactual instances either by directly modifying sensitive attributes or by employing graph-generation methods. However, these methods commonly assume that all observed factors are directly influenced by sensitive attributes, an unrealistic assumption that can lead to the generation of implausible counterfactual instances. In addition, a few studies [Wang et al., 2023a; Wang et al., 2025a] aim to identify potential counterfactual instances within the input dataset itself, rather than generating new ones. However, unlike theoretically-defined counterfactual instances, identifying appropriate real-world counterfactual examples from observational graph data lacks a clear consensus. Hence, these methods cannot guarantee that suitable counterfactuals will be found or that identified instances truly satisfy the intended fairness properties.

Graph Learning with Disentanglement. Learning disentangled representations, where latent factors underlying observed data are explicitly separated, has gained superior performance in recent graph learning research [Yang et al., 2024]. Existing works have demonstrated the benefits of disentanglement by enhancing interpretability and performance across diverse graph-based tasks. For example, DisenGCN [Ma et al., 2019] pioneered graph disentanglement through a neighborhood routing mechanism, explicitly capturing distinct latent factors influencing node interactions. Further advancing this line of inquiry, IPGDN [Liu et al., 2020] incorporated independence regularization between latent factors, enhancing the clarity and independence of the learned representations. Recently, some studies [Wang and Zhang, 2025] have explored leveraging disentangled learning specifically to enforce fairness constraints more accurately, aiming primarily to minimize performance degradation commonly associated with fairness optimization. However, these methods focus predominantly on sustaining predictive performance rather than directly improving fairness outcomes. To explicitly enhance model fairness in graph learning contexts, there is a need to design fundamentally different disentanglement approaches that account for the inherent relational structures and neighborhood dependencies unique to graph data.

Different from the above works, our work explicitly designs a disentanglement-based framework to achieve graph counterfactual fairness. By jointly disentangling sensitiverelated information from both node features and graph structures, our method precisely intervenes on sensitive attributes, selectively modifying sensitive-related components while preserving sensitive-irrelevant information. By doing so, our approach generates authentic counterfactual graphs that directly enhance model fairness, rather than merely preserving predictive performance.

3 Notations

We consider a node classification task on a graph G = (V, E,X), where V denotes the node set with |V| = n nodes and E denotes the edge set with |E| = m edges. The node feature matrix is X ∈ Rn×d , where the ith row xi represents the d-dimensional feature vector of node vi ∈ V. The graph structure is represented by an adjacency matrix A ∈ {0, 1}n×n , where Ai,j = 1 indicates the existence of an edge ei,j ∈ E between nodes vi and vj, and Ai,j = 0 otherwise. For simplicity, we assume that both node labels and the sensitive attribute are binary. Let S ∈ {0, 1}n×1 denote the sensitive attribute vector, where si is the sensitive attribute value associated with node vi; we define Sd = {vi ∈ V | si = 0} as the deprived group and Sf = {vi ∈ V | si = 1} as the favored group. Each node vi is associated with a ground-truth label yi ∈ {0, 1}, where yi = 1 denotes a granted label and yi = 0 denotes a rejected label, and ˆ yi denotes the predicted label of node vi.

4 Methodology

4.1 Causal Model

To explicitly identify sensitive-related information and distinguish it from unrelated components, the proposed causal model treats sensitive attributes as direct causes that influence both node features and graph structure. This integrated design enables targeted interventions on sensitive-related features and structural information while preserving components that are independent of sensitive attributes. By isolating the causal effects of sensitive attributes, the framework facilitates the generation of realistic counterfactual samples, thereby supporting fair decision-making in graph-based tasks. In the causal graph, each directed edge represents a direct causal influence, explicitly capturing how sensitive attributes affect features and connectivity. Below, we detail the rationale behind each causal relationship.

• AS ← S → XS: The sensitive attribute S directly influences both a subset of node features (XS) and the graph structure (AS). For instance, if gender is the sensitive attribute, sensitive-related features could include height, while AS capture network connections preferentially formed among individuals of the same gender.
• XS ⊥ S ⊥ AS : Node features unrelated to the sensitive attribute (XS ) and the corresponding sensitive-irrelevant graph structure (AS ) are explicitly independent of the sensitive attribute S.
• XS ← AS ; AS → XS: The graph structure directly influences both sensitive-related and sensitive-irrelevant node features, capturing how individuals' connections can shape attributes both independently and dependently of direct sensitive-related graph structure causation.
• X → Y ← A: Both node feature and graph structure, contain essential information influencing the outcome label, but the sensitive attribute S should not exert a direct causal effect on Y .

4.2 Latent Disentanglement of Sensitive Attribute Dependencies

Building on our proposed causal model, we introduce a latent disentanglement framework designed to explicitly separate the causal dependencies arising from sensitive attributes in both node features and graph structure. Specifically, our approach involves two complementary parts: i) disentangling node features into sensitive-related and sensitive-irrelevant features; ii) disentangling the graph structural dependencies within the graph influenced by sensitive attributes. For the first part, we leverage a causal-effect variational autoencoder to encode observed features into latent factors that explicitly separate variations causally driven by sensitive attributes from those unrelated to them, enabling targeted feature-level interventions. On the other hand, the second part focuses on graph structure, where sensitive-related relational mechanisms are inferred from the observed graph and isolated from task-relevant structural patterns using an information bottleneck objective, allowing counterfactual graphs to be generated by intervening only on sensitive-related structural components while preserving the remaining structure.

Node Features Disentanglement. We model node features through a causal-effect variational autoencoder that explicitly separates sensitive-related and sensitive-irrelevant factors in the latent space. Specifically, observed node features are encoded into two distinct sets of latent variables: sensitive-related latent variables (ZS), which capture feature variations directly influenced by the sensitive attribute (S), and sensitive-irrelevant latent variables (ZS ), which represent feature information unaffected by S. Inference over these latent factors is performed using variational Bayesian inference with two dedicated inference networks, qϕ(ZS | XS,AS, S, Y ) and qθ(ZS | XS ,AS , Y ), each aligned with the causal separation between sensitive-related and sensitiveirrelevant features. This ensures that the learned representations are consistent with the assumed causal structure, enabling reliable counterfactual interventions on node features.

However, relying on architectural design is insufficient for true independence and disentanglement between latent representations, due to the inherent complexity of node features, which exhibit indirect interactions and intricate relational patterns [Xiao et al., 2022]. In addition, conventional metrics relying solely on linear correlations or observable attributes often fail to capture the subtle, non-linear dependencies within latent spaces, making traditional independence measures insufficient for reliably assessing disentanglement quality [Eastwood and Williams, 2018]. To this end, we propose the Hirschfeld-Gebelein-R´enyi (HGR) based correlation measure, defined formally in Definition 4.2.1, as a principled way to precisely quantify the independence between sensitive-related and sensitive-irrelevant latent variables. With the ZS-ZS correlation measure established as the foundational metric for evaluating independence, we then integrate it into our optimization framework by introducing a structured min-max adversarial training strategy to rigorously ensure disentanglement between sensitive-related and sensitive-irrelevant latent representations. Starting with the correlation measure, the formal definition is given below,

Definition 4.2.1 ZS-ZS correlation. Given any two jointly distributed random latent variables ZS and ZS , the maximal HGR correlation between them is defined as:

where ρ denotes the Pearson correlation coefficient, while ψ1 and ψ2 are measurable functions with finite positive variances. To eliminate arbitrary shifts and scaling differences between ψ1 and ψ2, we normalize these functions such that E[f1(ZS)] = E[f2(ZS )] = 0 and E[f 2 1 (ZS)] = E[f 2 2 (ZS )] = 1. This normalization is essential, as it ensures comparability and stability across correlation measurements by standardizing the scale, thereby enabling consistent and meaningful quantification of the dependence between latent variables. Under this normalization, a ZS-ZS correlation of zero indicates perfect independence, whereas a correlation value of one indicates a deterministic relationship.

With the established ZS-ZS correlation, we structure a min-max adversarial optimization framework to ensure effective and precise disentanglement. Specifically, this framework consists of two adversarial subnets parameterized by ηψ1 and ηψ2 . These subnetworks actively estimate and attempt to strengthen the dependency between the latent variables ZS and ZS . During training, the subnetworks aim to maximize the ZS-ZS correlation through gradient ascent, thereby identifying potential residual dependencies between sensitive-related and sensitive-irrelevant representations. Simultaneously, the primary inference networks, responsible for encoding the latent representations ZS and ZS , are trained to minimize this estimated dependency via gradient descent. This min-max procedure ensures maximal independence between the latent factors, resulting in rigorously disentangled latent representations. By training the model adversarially, we enforce the maximum independence between ZS and ZS , achieving precise disentanglement. Overall, this approach establishes a foundation for authentic and precise counterfactual instance generation at the node-feature level by ensuring strong independence between sensitive-related (ZS) and sensitive-irrelevant (ZS ) latent representations. Such explicit disentanglement allows subsequent counterfactual interventions to selectively modify only causally relevant latent factors, while reliably preserving unrelated feature information.

Graph Structure Disentanglement. Beyond node-feature disentanglement, we explicitly address sensitive attribute dependencies embedded within the graph structure information. In other words, even if sensitive-related and sensitiveirrelevant node features are successfully separated, sensitive attributes may still influence the graph structure through connectivity biases such as homophily. These biases manifest as multi-hop relational patterns rather than direct node-level features, making node feature-based disentanglement alone insufficient for fully capturing relational influences. To this end, we propose a graph structural disentanglement strategy leveraging an information bottleneck objective to identify and disentanglement the structural component driven by the S from sensitive attribute-related and sensitive-irrelevant structural patterns. By explicitly modeling and extracting these sensitive-related relational dependencies, our framework ensures that counterfactual graph generation can selectively intervene only on sensitive-related structural patterns, while keeping all remaining structural information unchanged. Specifically, we introduce a latent decomposition of the graph G into two complementary structural views: the sensitive-related subgraph GS = (VS,AS,XS) and the sensitive-irrelevant structure GS = (VS ,AS ,XS ), where edges satisfy AS + AS = A and AS ⊙ AS = ∅. In other words, each edge is assigned to exactly one structural component. Our goal is to learn GS such that it captures the relational patterns induced by S (the part we should modify under counterfactual intervention), while GS contains the remaining structure and should be as insensitive to S as possible.

To learn this disentanglement, we parameterize the extraction of GS by a stochastic structural extractor Pψ(GS | G), where ψ are trainable parameters. Hence, Pψ outputs candidate sensitive-related structural views from the input graph, using a stochastic extractor avoids brittle hard decisions early in training and allows end-to-end optimization. To achieve this, the structural information bottleneck is used to guide what kind of structure should be captured by GS: the extracted structure is encouraged to be concise rather than a direct copy of the original graph, while still retaining the structural patterns that are relevant for predicting the sensitive attribute S. This trade-off is enforced by an information bottleneck objective that penalizes redundant structural information from G while encourage sensitivity-related structural in GS, as formalized in Definition 4.2.2.

Definition 4.2.2 Sensitive-related structural information bottleneck. Given a jointly distributed graph random variable G and sensitive attribute S, and a stochastic structural view GS ∼ Pψ(GS | G), we define the sensitive-related graph structural bottleneck objective as:

where I(·, ·) denotes mutual information and α > 0 controls the trade-off. In addition, the compression term I(G,GS) penalizes copying the entire structure into GS, while the sensitive-information term I(S, GS) encourages GS to retain the structural patterns that are predictive of S.

Building on this, the optimal sensitive-related graph structure is obtained via:

where GS(ψ∗ ) is the sensitive-related graph structural component produced by the optimal extractor. As a result, this optimization leads to a structural disentanglement in which counterfactual graph generation interventions modify only sensitive-related relational structures, producing realistic and causally consistent structural adjustments.

4.3 Counterfactual Generation via Disentangled Learning

Building upon the disentangled latent representations that clearly separate sensitive-related from sensitive-irrelevant information in both node features and graph structure, GCFair generates counterfactual graph instances via a structured three-stage causal inference procedure. The core idea is that counterfactual interventions on S should exclusively modify components directly influenced by the sensitive attribute, specifically sensitive-related node features and graph structure, while preserving all sensitive-irrelevant information to maintain coherence and causal consistency. To realize this principle, GCFair adopts the canonical three-stage counterfactual inference pipeline, explicitly augmented with disentangled representations for node features and structural information. Specifically, these stages include: i) Abduction, where the model infers latent variables from the observed graph data. Different from existing work, GCFair infers disentangled latent variables (ZS, ZS ) for node features, and additionally extracts a sensitive-related structural component from the observed adjacency via the learned structural disentangler. Concretely, given an observed graph G = (V, A, X), we obtain a sensitive-related structural view GS = (V,AS,X) through the trained extractor Pψ(GS | G), and define the residual structure as AS = A-AS; ii) Action, where the sensitive attribute is intervened upon by assigning it a counterfactual value (s → s′ ). In this stage, the inferred latent factors are held fixed, and only the sensitive-related components, both structural and feature-based, are re-sampled under the new sensitive attribute value; and iii) Generation, where the decoder reconstructs a realistic counterfactual instance (Acf ,Xcf , Y cf ) by integrating the re-sampled sensitive-related components with the preserved sensitiveirrelevant residual information. This structured inference procedure is underpinned by a foundational causal assumption, explicitly defining the permissible causal pathways within the proposed framework.

Assumption 4.3 The sensitive attribute S does not directly affect the ground-truth label Y ; its influence on Y is mediated only through sensitive-related node features XS and the sensitive-related structural component of the graph. In addition, S has no causal influence on sensitive-irrelevant node features XS and no causal influence on the sensitiveirrelevant residual structure AS .

Formally, under this assumption, our model characterizes the full counterfactual generation process through the following joint distribution factorization:

where P(ZS) and P(ZS ) represent prior distributions for sensitive-related and sensitive-irrelevant latent variables, respectively; P(S | ZS) ensures that latent variables sufficiently encode sensitive attribute information. Structural mechanisms P(AS | S,ZS) and P(AS | ZS ) explicitly model graph structure information, ensuring that structural changes under intervention (i.e., do(S)) affect only the sensitive-related graph structural information, while preserving the residual structure. Similarly, the feature mechanisms P(XS | AS, S,ZS) and P(XS | AS ,ZS ) control node feature modifications, guaranteeing that counterfactual interventions selectively alter only sensitive-related features and leave sensitive-irrelevant features intact.

However, maximizing the joint likelihood of the observed graph variables is computationally difficult, mainly because it requires integrating over high-dimensional latent factors and also over the latent structural decomposition that separates sensitive-related from residual connectivity. To this end, we adopt variational Bayesian inference and approximate the true posterior P (ZS , ZS | S, G, Y ) by a factorized variational family qϕ(ZS | AS,XS, S, Y ), qθ(ZS | AS ,XS , Y ), and a stochastic structural extractor qψ(GS | G), as detailed:

Under this approximation, we maximize an evidence lower bound (ELBO) associated with our feature-structure generative factorization:

where KL(·) denotes the Kullback-Leibler divergence of the posterior distributions qϕ(ZS) and qθ(ZS ) from their respective priors P(ZS) and P(ZS ), which regularizes the latent space for reliable counterfactual generation.

To further ensure that our learned latent representations accurately reflect the intended causal disentanglement between sensitive-related and sensitive-irrelevant features, we explicitly integrate the previously established ZS-ZS independence constraint into the optimization objective. Specifically, while the ELBO encourages effective latent representation learning, it does not inherently guarantee sufficient independence between ZS and ZS . By combining the ELBO with the explicit independence constraint (formalized by the ZS-ZS correlation measure), we rigorously enforce the targeted disentanglement established in the previous subsection. This integrated optimization framework simultaneously ensures highquality latent representation learning and precise feature disentanglement, significantly enhancing the authenticity and precision of generated counterfactual instances. Formally, this joint optimization is defined as follows:

In addition, the ELBO alone does not guarantee that the extracted structural component GS concentrates on sensitiverelated relational patterns, nor that the residual structure GS is minimally predictive of S. This is because there exist many decompositions of the observed adjacency that can achieve similar reconstruction likelihood, including degenerate cases where GS collapses to the full graph or becomes empty. Directly optimizing mutual information terms such as I(G, GS) and I(S,GS) is intractable for graph-structured variables, so we incorporate a variational information bottleneck regularizer based on standard bounds. Specifically, we impose two complementary constraints: i) we enforce compression of the extracted structural view by penalizing its divergence from a simple reference distribution (R(GS)), initially defined as an edge-independent Bernoulli prior with a low edge-inclusion probability; and ii) we ensure that (GS) maintains predictive power regarding the sensitive attribute, while simultaneously reducing sensitive attribute leakage from the residual structure (GS ), by introducing variational discriminators:

where β, α, λ control the strengths of structural compression, sensitive-related information preservation, and reduction of residual sensitive-related information leakage, respectively.

With the generated counterfactual instances, we introduce a counterfactual fairness constraint explicitly designed to penalize prediction changes resulting from interventions on the sensitive attribute S, while maintaining the inferred latent factors constant. Formally, this constraint is defined as:

Building on this, our final training objective augments the ELBO with i) a feature-level independence constraint, ii) a counterfactual fairness regularizer, and iii) a structural information bottleneck regularizer:

where λD, λF , and λIB control the strengths of the feature disentanglement, counterfactual fairness, and structural disentanglement regularizers, respectively.

5 Experiments

5.1 Experiment Settings

Datasets and Baselines. Our experiments are conducted on three datasets: the Credit dataset [Yeh and Lien, 2009], Bail dataset [Agarwal et al., 2021], and Pokec-z dataset [Takac and Zabovsky, 2012]. In addition, we compare GCFair with the following baseline methods: i) Vanilla Graph Model: GCN [Kipf and Welling, 2016], ii) Graph Counterfactual Fairness Methods: NIFTY [Agarwal et al., 2021], GEAR [Ma et al., 2022], CAF [Guo et al., 2023], AGCG [Wang et al., 2025d] and Fairwos [Wang et al., 2025a]. The details are provided in the appendix.

Evaluation Metrics. We use AUC and F1-score to evaluate the model performance. To evaluate fairness, we use two commonly used fairness metrics, i.e., Statistical Parity Differences (SPD) [Dwork et al., 2012] and Equal Opportunity Differences (EOD) [Hardt et al., 2016], with values close to zero indicating better fairness.

5.2 Experiment Results

Performance Comparison. Table 1 presents the results comparing GCFair with six baselines on three datasets. Overall, GCFair achieves the best fairness results on all datasets, while keeping competitive predictive performance. Specifically, i) Fairness improvement: GCFair consistently yields the lowest SPD and EOD across the benchmarks primarily due to its capability to generate authentic counterfactual graphs. By explicitly disentangling sensitive-related information from sensitive-irrelevant components in both node features and graph structures, our method accurately identifies and modifies sensitive-related information, ensuring precise adjustments aligned with counterfactual interventions. Hence, by generating authentic counterfactual instances, we can more effectively enforce fairness constraints, significantly enhancing fairness outcomes. ii) Predictive performance: GCFair maintains competitive AUC and F1-scores because it preserves sensitive-irrelevant information. The selective modification of only causally-linked sensitive components avoids unnecessary removal of task-related information, thus mitigating the accuracy degradation associated with enforcing fairness constraints. Overall, these results demonstrate that GCFair effectively achieve fairness improvements with comparable performance, highlighting its practical utility in graph-based applications.

Ablation Study. To evaluate the effectiveness of each constraint in our method, we provide ablation study with the following variants: i) w/o Feature Disentanglement: we remove the feature-level disentanglement constraint by dropping the ZS-ZS correlation regularization which allows sensitive and sensitive-irrelevant information to mix in the latent space; ii) w/o Structural Disentanglement: we remove the structural information bottleneck regularizer and learn the model without explicitly isolating sensitive-related structural patterns, so sensitive-related information can remain in the graph structure; and iii) w/o Disentanglement: we remove both the feature-level disentanglement constraint and the structural bottleneck regularizer, keeping the remaining training objective unchanged. The results on the Credit dataset is illustrated in Figure 2 (a), and additional results are provided in the appendix. Overall, we observe consistent fairness degradation once any disentanglement constraint is removed. Specifically, removing feature disentanglement allows sensitive information to leak into the inferred latent space, making counterfactual interventions on S imprecise. Similarly, removing structural disentanglement causes residual sensitive information to remain within graph structure, limiting the authenticity of generated counterfactual graphs. Therefore, the counterfactual instances become less reliable for fairness training, negatively impacting both fairness metrics and predictive performance. Finally, the removal of both disentanglement components leads to the largest fairness drop, clearly indicating that both feature-level and structurallevel disentanglement are complementary and essential for authentic counterfactuals generation.

Parameters Study. To investigate the effect of λD, λIB, and λF on the performance of GCFair, we vary the hyperparameters within the set {10-4 , 10-3 , 10-2 , 10-1 , 1, 10, 102 , 103 , 104 }. We compare GCFair's performance in terms of predictive and fairness under the different settings. The results in the Credit dataset are illustrated in Figure 2 (b), and additional results are provided in the appendix. We observe that increasing λF and λIB generally improves fairness but may reduce predictive performance when set too large, while increasing λD strengthens feature disentanglement but can also introduce an accuracy drop if overly constrained. Overall, the parameter study confirms that GCFair is stable over a broad range of hyperparameters and achieves consistent fairness gains with moderate regularization strengths.

6 Conclusion

Given the observed gap between assumptions underlying existing counterfactual fairness methods and their inability to generate authentic counterfactuals in graph-structured data, we introduced GCFair, a novel causal and variational framework explicitly designed for genuine counterfactual fairness. Our method leverages a causal model that effectively disentangles sensitive-related information from sensitive-irrelevant components in both node features and graph structures. Through novel disentanglement strategies explicitly designed to enhance model fairness, our approach ensures accurate and meaningful structural decomposition. Extensive evaluations demonstrated that GCFair effectively generates authentic counterfactual graphs, significantly improving fairness without sacrificing model performance. This work provides a practical solution, establishing a strong foundation for future research on counterfactual fairness in graph learning.

Acknowledgements

This work was supported in part by the National Science Foundation (NSF) under Grant No. 2404039.