Counterfactual Fairness on Graphs: Augmentations, Hidden Confounders, and Identifiability
Authors: Hongyi Ling
Zhimeng Jiang
Na Zou
Shuiwang Ji
Venue: Accepted by TMLR ()

Abstract: We consider augmenting graph data with counterfactual generation in order to achieve fairness on downstream tasks. While this direction has been explored previously, existing methods invariably consider oversimplified causal relationships. Moreover, they often rely on unidentifiable models to encode causal relationships, making it hard to identify the true joint distribution and thus recover counterfactual graphs. To tackle these challenges, we introduce a causal model with hidden confounders on graphs, which considers the existence of hidden confounders affecting both node features and graph structures. We use an identifiable graph VAE model to simultaneously estimate hidden confounders and learn generation functions of the causal model. By incorporating a Gaussian mixture prior distribution, we improve the identifiability of our model to recover the joint distribution of observed data and hidden confounders. Using the generated counterfactual graphs, we enforce consistency in the predictions of classifiers for different counterfactual graphs, thereby achieving graph counterfactual fairness in these classifiers. Experimental results demonstrate the effectiveness of our method in improving the counterfactual fairness of classifiers on various graph tasks. Moreover, theoretical analysis, coupled with empirical results, illustrates the capability of our method to successfully identify hidden confounders.

Published in Transactions on Machine Learning Research (01/2025)
Counterfactual Fairness on Graphs: Augmentations, Hidden Confounders, and Identifiability
Hongyi Ling
hongpilingStammu.ci edu
Deportment of Computer Science Engineering
Tezas ABM University
Zhimeng Jiang
zhimengjjtaama. edu
Deportment Computer Science & Engineering Texas ABM University
Na Zou"
nzou2@ul. edu
Department of Industrial Engineering University of Houston
Shuiwang Ji
sji Gtamta edu
Department of Computer Science Engincering Texas ABM University
Reviewed OpenReview: https: openreview. net/ forum? id=NJHf7PCuVS
Abstract
We consider augmenting graph data with counterfactual generation in order to achieve fairness on downstream tasks. While this direction has been explored previously, existing methods invariably consider oversimplified causal relationships. Moreover, they often rely unidentifiable models to encode causal relationships, making it hard to identify the true joint distribution and thus recover counterfactual graphs. To tackle these challenges, we introduce causal model with hidden confounders graphs, which considers the existence of hidden confounders affecting both node features and graph structures. We use an identifi- able graph VAE model to simultancously estimate hidden confounders and learn generation functions of the causal model. By incorporating a Gaussian mixture prior distribution, we improve the identifiability of our model recover the joint distribution of observed data and hidden confounders. Using the generated counterfactual graphs, enforce consis- tency in the predictions of classifiers for different counterfactual graphs, thereby achieving graph counterfactual fairness in these classifiers. Experimental results demonstrate the ef- fectiveness of our method in improving the counterfactual fairness of classifiers on various graph tasks. Moreover, theoretical analysis, coupled with empirical results, illustrates the capability of our method to successfully identify hidden confounders.
1
Introduction
Graph neural networks (GNNs) have been used to solve problems across wide range of domains Gao
et al. 2021
Gao & Ji, 2019 Ling al.] 2023a), from social network analysis (Hamilton et al. 2017 Han
ct al.
2022] to drug discovery (Liu et al.] 2022). As with many other machine learning methods, GNNs
sometimes make biased predictions (Dai & Wang 2021 Ling et al. 2023b Jiang et al. 2022a), thus raising cautions in real-world high-stakes tasks, such as healthcare (Rajkomar et al. 2018), finance (Feldman et al.
2015
Petrasic et al. 2017), and criminal justice
(Suresh & Guttag 2019
Traditional statistical fairness
Equal senior authorship

---

Published in Transactions on Machine Learning Research (01/2025)
notions (Kang et al. 2020 Dong et al. 2021 Petersen et al. 2021; Jiang et al. 2022b), such as demographic parity (Doork et. al. 2012 and equalized odds (Hardt et al. 2016). have been proposed to quantify and address prediction bias. However, those fairness notions cannot guarantee fair predictions across various dimensions. For example, when demographic parity is equal or close to O, it may still allow for unfair treatment of individuals within the same 'protected' calegory, who may have different characteristics such as varying oducational backgrounds or personal attributes. In contrast, counterfactual fairness (Kusner let al. 2017 Wu et a 2019a b Nilforoshan et al. 2022) uses causality to present a more comprehensive and intuitive approach to defining fairness. A model is counterfactually fair if its prediction for an individual remains the same in the real world and in a counterfactual world where the individual belongs to different demographic group. This approach allows for the modeling of intricate relationships inherent in real-world data. For instance, in a loan approval scenario, node fealures such as income and employment history, as well as relationships with others (represented as edges in a graph), may be causally influenced by a sensitive attribute like gender. A counterfactual graph adjusts these causally dependent node features and edges to reflect the hypothetical change in the sensitive attribute. The model is counterfaclually fair if its loan decision remains consistent between the real and counterfactual graphs. By considering what would have happened under different conditions, counterfactual fairness offers different understanding of fairness that can potentially tackle such complex scenarios. Given the potential advantages of counterfactual fairness in addressing the limitations of statistical fairness notions, it is desirable to explore the counterfactual fairness of GNNs to mitigate potential biases.
Counterfactual fairness of GNNs presents significant challenges, particularly in inferring counterfactuals from observable data. This difficulty stems from the reliance causal models, which must capture the intricate relationships among sensitive attributes, node features, and graph structures. Existing methods often simplify these causal relationships. For example, NIFTY (Agarwal et al.) (021) assumes that sensitive attributes are independent of both node features and graph structures. On the other hand, GEAR (Ma) ett al. 2022) assumes that the sensitive attribute serves as the sole confounder linking node features and graph structures. However, these oversimplified assumptions fail to account for the complexities of real- world data, where hidden confounders, that influence both node features and graph structures, are likely to exist. Such hidden confounders introduce additional complexity that remains unaddressed in prior work, highlighting the need for methods that can effectively model and mitigate their impact. Moreover, existing studies use unidentifiable variational autoencoders (VAE) to model causal relat colssioss (Madras et al. 2018 8: 2021
Ma et al.) 2022 Louizos et al. 2017 Foster et al.] 2022). Due to their non-identifiability (Roeder et al.
Wang et al. 2021: Kivva et al. 2022 Khemakhem et al.) 2020a; Foster et al.) 2022), it is generally hard to recover the true joint distribution of data. This makes it challenging to accurately recover counterfactual graphs, limiting the effectiveness of these models in achieving counterfactual fairness.
In this work, we introduce GraphCFF, a novel approach designed to address the challenges of counterfac- tual fairness in graph data. We propose causal model that considers the role of sensitive attributes confounders that causally influence both node features and graph structures. Importantly, we also account for the presence of hidden confounders that simultancously affect both node fcatures and graph structures, thereby providing more realistic modeling of the underlying complexities in graph data. A primary challenge is that only graph data is observed, while the hidden confounders and the generation mechanisms of the causal model remain unknown. To tackle these challenges, we use an identifiable graph VAE to estimate hidden confounders and learn the generation functions simullaneously. To enhance the identifiability of the model, incorporate Gaussian mixture model (GMM) a prior distribution, enabling more accurate recovery of the joint distribution of observed data and hidden confounders. This allows to reliably recover counterfactuals We then use the generated counterfactual graphs to enforee consistency in the predictions of classifiers across different counterfact ual graphs, thereby achieving graph counterfactual fairness in these classifiers. Experimental results demonstrate the effectiveness of our method in improving the counterfactual fairness of classifiers on various graph tasks. Furthermore, both theoretical analysis and empirical results highlight the potential of our method to successfully recover hidden confounders.
2

---

Published in Transactions on Machine Learning Research (01/2025)
2 Background and Related Work
We denote a graph with nodes as X, Here, A {0, is the adjacency matrix, and Aij = if and only if there exists edge belween nodes i and j. X [X,,... _x,' _n! R"xp the node feature matrix, where each X; I' is the p-dimensional feature vector of node i. S [s. .nl." {0, 1 is the vector containing binary sensitive attributes of nodes, such as gender or race. Here, 8; denotes the sensitive attribute of node i. Furthermore, we assume that each node i is associated with a latent variable Z; E IR and these variables are included in a matrix = [Z,,... ZnI"" E R=*4, In node classification tasks, the labels of nodes are denoted as Y "y. . .yol", where yi E {0, 1) is the label of node i.
2.1 Causal Models and Counterfactuals
We follow Pearl et al. (2000) to define a causal model as a triple (U, where V denotes the set of obsorvable variables, denotes the set of unobsorvable variables, and F= (Fi,..., Fivi denotes the set of functions that assign values to each variable Vú E V. Any variable U, E u cannot be caused by any variable in V. For each variable V, V, the corresponding function F; expresses how V, is dependent causes as V; = (pa,, Upa,), where pa; S VA {Vi} represents the observed direct causes of Vi, and Upo, u reprosents unobserved variables that directly cause V,
its direct
Causal models enable us to perform counterfactual inferences in order to answer questions about what would have happened in a counterfactual world if certain conditions were altered. For example, for two observable variables Vi and V2, a common counterfactual query is "What would the V1 have been if V22 were V/7 The solution this query, denoted as V((v)=vz)) can be obtained through three steps (Glymour al. 2016) as follows. 1) Abduction: Infer the unobserved variables U from observed data V. 2) Action: Substitute V/2
with Viz. 3) Prediction: Compute the value of remaining element VI using corresponding function F1 and latent variables U.
2.2 Counterfactual Fairness on Graphs
Counterfactual fairness is notion of fairness based on counterfactuals (Kusner et al. 2017 Zuo et al., 2022 Nilforoshan et al.] 2022 Wu et al., 2019b Kilbertus et al.) 2017]. The prediction of a classifier for an individual is counterfactually fair if the prediction remains consistent in both the actual and the counterfac- tual worlds, where the individual belongs to a different demographic group. Recent studies have explored counterfactual fairness on graph data (Agarwal et al., 2021 Ma et al. 2022). These studies aim to develop counterfactually fair encoder to ensure that the learned representations from the original graph and those of the counterfactual graphs the sensitive altributes of nodes while leaving other node feat and graph structures unchanged (Agarwal et al. 2021). A triplet-based based objective is then used to maximize agreement between the original and counter- factual graphs in order to learn counterfactually fair representations. However, à major limitation of NIFTY is its focus on a simplified case, where the sensitive attribute has no causal effect on other node features or graph structures. Instead of ignoring all cansal relationships, GEAR addresses the case where sensitive attributes are the cause of both node features and graph structures (Ma et al., 2022). GEAR uses VAEs to model these causal relationships and generate counterfactual graphs by perturbing sensitive attributes. A Siamese network is then used to minimize discrepancies between representations learned from the original graph and counterfactual graphs, lcading to counterfactually fair representations. Nevertheless, GEAR oper- ales under the assumption that there are no hidden confounders (Pearl) 2009 Greenland et al. 1999 Mickey & Greenland 1989) of node features and graph structures, which could oversimplify the complexities of real-world graph data. Furthermore, VAE models are generally non-identifiable (Khemakhem et al., 20200a]
identical. NIFTY proposes to generate counterfactual graphs by flipping
Kivva et al. 2022: Wang al.) 2021 Foster et al.) 22022), posing challenges in accurately recovering the true latent variables of the causal model and thus generating noisy counterfactual data.
3

---

Published in Transactions on Machine Learning Research (01/2025)
S
S
A
X
A
x
A
(a) NIFTY
(b) GEAR
(c) Our causal model
Figure 1: Comparison of different approaches for modeling the causal relations among sensitive attributes S, node features X, and graph structures A. Grey and white nodes represent observed and unobserved variables, respectively. (a) NIFTY (Agarwal et al. 2021) assumes that sensitive attribute has no causal effect on other node features or graph structures. (b) GEAR (Ma al. 2022) models sensitive attributes S the sole confounder of node features X and graph structures A without any hidden confounders. (c) GraphCFF (ours) explicitly models hidden confounders Z for both node features X and graph structures A.
3 Methodology
Existing methods typically adopt two-stage approach to achieve counterfactual fairness. They first learn counterfactually fair graph representations and then train downstream classifier using these representations as input (Ma et al.] 2022 Agarwal et al. 2021). In contrast, We propose GraphCFF, a novel method that directly achicves counterfactual fairness by augmenting graph data through counterfactual gencration. This approach enables a more direct solution to counterfactina fairness in graph data. In this section, we first conceptualize and describe our proposed causal model, which takes into account the existence of hidden confounders. We then introduce how use variational inference learn both generative model, which approximates the functions of the causal model, and inference model, which estimates hidden confounders. We next explain how generate counterfactual graphs by flipping the sensitive attributes of nodes. Using these generated counterfactual graphs, we are able to train classifier that achieves counterfactual fairness.
We provide a formal definition of graph counterfactual fairness as follows:
Definition 1 (Graph Counterfactual Fairness). Given a graph G = (, the prediction ý of classifier is counterfactually fair if, for any node i,
PÍYAA = 59)
(1)
where
8/ =
8j+
i 189 i=
for 1,.
and Y; is the prediction for node i.
In other words, the prediction of a classifier for a node is counterfactually fair if it remains the same in both the actual world and the counterfactual world where the sensitive attribute this node is assigned to a different demographic group. Note that obtaining counterfactual data in the real world is almost impossible. Morcover, the causal relationships between the sensitive attribute S, node features X, and adjacency matrix A remain unknown, making it hard to perform counterfactual inference directly. Therefore, how to obtain counterfactuals is one of the primary challenges to be addressed in counterfactual fairness graphs.
3.1 Causal Model with Hidden Confounders
In this soction, we present our proposed causal model, accounting for the presence of hidden confounders in graph data such as social networks. We first introduce independent latent factors Z, which generate the observed graph data. The latent factors of different nodes are independent, and identically distributed. We
4

---

Published in Transactions on Machine Learning Research (01/2025)
assume that the latent factors Z serve as hidden confounders for both node features X and adjacency matrix A. For example, an individual's 'personality' could influence his/her 'health' and his/her social relationships with others. Since Z does not necessarily correspond to tangible objects in the world, it is reasonable to consider hidden confounders as independent of sensitive attributes in our model. Morcover, we assume sensitive attributes have no parent variables in the causal graph, implying that they can only be the cause of other variables. Specifically, sensitive attributes S are not caused by Z, while they are the cause of both node features X and adjacency matrix A. In fairness problems, sensitive attributes are typically determined at birth, making it reasonable to treat them root nodes in causal graph. For example, the sensitive attribute 'gender' cannot be caused by other features like 'height', while 'gender' can cause. 'height:. This
assumption has been widely adopted in recent studies (Kusner et al. 2017 Zuo et al. 2022 Ma et al. 2022
Madras et al. 2019).
To model the topological structures of graphs, we assume that the edge between node i and node j only depends on the factors of these two nodes and is independent of other nodes. We also explicitly account for sensitive homophily in graphs, indicating that nodes with the same sensitive altribule are more likely to connect than nodes with different sensitive attributes. other words, our causal model is similar to stochastic block models with higher intra-connection and lower inter-connection probabilities. This is consistent with
recent studies (Jiang et al. 2022a Dong et al. 2022 Kose & Shen 2022 Dai & Wang 2021 Formally, the process of generating the adjacency matrix A = FA (2 can be expressed as
1, if s + sy and sim sim, > 1 Pinter
Ai
1, if 8, sj and sim Zi, 2j) > 1 - Pintra for i,j = 1,,.., ,n,
(2)
0, otherwise
where sim(-) computes the similarity between two nodes. Pinter and Puntra represent thresholds for the intra-connection and inter-connection respectively, with Pinter < Pmntra
Furthermore, one of the most significant challenges in graph data is the non-independence of nodes, which mcans altering one node could affect another node. For example, if all friends of an individual adopt a dict, it is likely that, the individual will also start a diet. Instead of treating each node as an independent data point (Agarwal al.) 2021), we explicitly consider the causal relationship between nodes, meaning that the node features of node i can be influenced by its neighbors. We rely on a widely accepted local-dependence assumption for graph-structured data (Wu et al. 2020); that is, given daia related to neighbors within a certain number of hops of node i, the data in the rest of the graph is independent of node i. In other words, a node depends on its k-hop neighbors but is independent of nodes outside its k-hop neighborhood. In this work, we consider cases where k = 1, which should provide a good approximation of real-world scenarios. Formally, the generation process of node features X Fx Fx A, S) can be expressed as
(3) where N₁ denotes the set of the nodes comnected to the node i in the graph, and AGG(-) denotes an aggregation function that maps the messages from all neighboring nodes to a single vector. Fx, and Fx, are two piecewise affine transformation functions, such as multilayer perceptrons with leaky ReLU activations. In summary, our proposed causal model can be formally defined as follows:
= Fx, (Z,, 8)) + AGG
j N.)). for iori= 1........ n.
Definition 2 (Causal Model with Hidden Confounders on Graphs). A causal model on graphs with hidden confounders can be represented as tuple (U, V,F), where V = {A, X.S) and u = (Z). F = (FA, corresponds to the generating mechanism of A and X, defined as A- = (2, and X = (2. A, Remark 1. Different from the simple scenario (Ma et. al. 2022 where S is the only confounder of A and X, and no hidden confounders exist, we consider a more realistic scenario where hidden confounders of AA and X exist, which has been overlooked in the literature. Soe Figure D for a comparison between our proposod causal model with the causal models in existing works. More discussions are given in Appendix C
3.2 Learning Method
A primary challenge in performing counterfactual inferences on our causal model lies in the fact that only graph data g = (, is observed, while the hidden confounders Z are unobserved and generation
5

---

Published in Transactions on Machine Learning Research (01/2025)
functions F are unknown. As demonstrated by Louizos et al 2017 ): Madras et al 2019 counterfactuals can be recovered if we can recover the joint distribution P Z, A, X, S) among node features X, graph structures A, sensitive attributes S, and the hidden confounders Z. Therefore, we need to learn two models; namely (1) a generative model approximating the gencration functions F, and (2) an inference model approximating the distribution of Z given A, S.S.
We use variational inference parameterized by deep neural networks to learn the parameters of both models jointly. In variational inference, aim to learn approximation of the joint distribution P(Z, X, S), by maximizing a variational lower bound on the log- pae-bbbability of the observed graph data (A, S). Specifi- cally, we introduce a variational distribution A, X, S) which uses parametric family of distributions to approximate the intractable posterior distribution P(Z X, The parameters of both the generative model and the inference model are learned simultaneously by maximizing the evidence lower bound (ELBO) of the marginal data likelihood.
To learn a generative model that is consistent with our proposed causal model, we model the joint probability using the following factorization:
A) P
(4)
where P(A|Z,S) and P(X S) correspond to the generation functions FA and Fx, respectively. To learn the parameters of both the generative model and the inference model, maximize the ELBO as
log P(A.XIS) 2 Z s) log P(A|Z,S) + log P(X)A,Z.S)
log Q X, S) + log P(Z)).
We provide detailed derivations of ELBO in Appendix The ELBO can be maximized using the Stochastic Gradient Variational Bayes estimator and the reparamcterization trick (Kingma & Welling 2014).
3.3 Gaussian Mixture as Prior Distribution
It is important to note that the conclusion by Louizos al.
(2017);
;; Madras el. al. (2019) is based on the
assumption that learning with VAËs can recover the true joint distribution P(Z. A, X)S). S). However, due to the non-identifisbility of VAE models (Khemakhem et al.
2020a Wang et al. 2021 Foster et al. 2022
Z. A, X, S). This non non-identifiable issue (2019). To address this issue, we follow Kivva et al. (0222 to incorporate a Gaussian mixture model (GMM) prior in our framework. We use the same GMM to model the prior distribution of hidden confounders Z, for any node Specifically, we model the prior distribution of the hidden confounders Zi as a weighted sum of K different Gaussian components, where each component has a mixture weight ne R+ These mixture weights are themselves probabilities that 0. Thus, the probabilities of the components can be modeled
it is generally impossible to recover the true joint distribution P undermines the conclusion by Louizos et al. (2017); Madras et al.
satisly the constraints ΣK Te 1 and using a categorical distribution as P(c) ~ Cat(T]....,.. a mean vector Me E Ra and a covariance matrix Σ. E 1284, The covariance matrix Σ. is a diagonal matrix with diagonal elements 02 P2,.,,, GoG Formally, the prior distribution of the hidden confounders Z; can be described as Zi Ee ToN Ee), where Nuue, Ee) denotes Gaussian distribution with mean He and covariance matrix Eg- Let C denote the vector containing the component values of all nodes in the graph. The updated ELBO of our framework can be formally described
Each Gaussian component is parameterized by
log P(A, 2EQ(Z.CIA.x.5) Dog P(A
+ log P(X (.JAA,,5. S) + log P(C) + +log P(ZC) - log A
(6)
log Q(CIA,X,S))
Note that we assume the variational distribution Q Q, can be factorized as Q(Z,CIA, Q(Z A, S)(C),,
This assumption is also used in VaDE (Jiang et al.) 2016). By incorporating the GMM prior, we enhance the ability of our model to recover the distribution of the hidden confounders, resulting in accurate counterfactual inferences on our model. Besides, we provide theoretical support for identifying the true distribution of the hidden confounders in Section
6

---

Published in Transactions on Machine Learning Research (01/2025)
3.4 Counterfactual Generation
In this section, we discuss the process of generating counterfactual graphs using well-trained generative and inference models, enabling the learning of counterfactually fair downstream classifiers. Once the learning process is complete, the gencrative model can generate new graph data consistent with the generation mech- anism as our proposed causal model. Meanwhile, the inference model can estimate the hidden confounders given the observed graph data. The process of generating a counterfactual graph, in which the sensitive attribute of node is assigned to a different group, consists of three main steps. Given the observed graph data G {A, S),, we first estimate the hidden confounders Z using the inference model. Next, we swap the sensitive attribute of node i to create new vector 5", where
i it j for j -;,..,, 1-88, 8jz i=
8j:
8/
With the obtained hidden confounders Z and the new sensitive attribute vector S', use the generative model to generate the counterfactual graph (( (A(st ;) ()) where A(s- = (Z) and ((S-S* = (x, ((s+)); S*).
The generated counterfactual graphs can then be used to train counterfactually fair downstream classifiers. Intuitively, we augment the observed graph dataset with counterfactual graphs while keeping the labels the same, ensuring that downstream classifiers make consistent predictions for different counterfactual graphs. This encourages the graph counterfactual fairness in the downstream classifiers. In practice, during each training step, we randomly select a node i and generate counterfactual graph where the sensitive attribute of node i is flipped. Along with the node labels Y, the generated counterfactual graph G(s+s') is used to train the downstream classifiers.
4 Identifiability Analysis
As we mentioned in Section 3.3. one primary issue of learning with VAE models is that they are non- identifiable. In other words, multiple parameter sets can result in models having identical marginal data and prior distributions, but entirely different latent factors Z. This makes it hard to recover the true joint distribution P(Z, A, S) and, in turn, makes difficult to recover counterfactuals. Therefore, ensuring the identifiability of our model becomes important for recovering counterfactuals. A model is considered identifiable if there is only one unique set of parameter values corresponding to the true data-generating process. Nevertheless, this strict definition of identifiability may be overly restrictive in practical applications. Instead, we consider a relaxed notion of identifiability. Following Kivva et al. (2022). we provide a formal definition of identifiability as follows:
Definition 3 (Identifiabilityy. Let P be family of probability distributions on the latent factors and 7 be a family of the generation functions. We use FpP to denote the pushforward mcasure of P by F. For a pair (P,F) E 2 x 8, we say that the distribution P identifiable from F,P up to an affine transformation if for any (P', F') E & such that F,P P'P' there exists an invertible affine transformation h such that p' w--ha -h
This ifiabiiiyyility definition can be easily extended to other invertible transformations, such as permutations and translations. See Khemakhem et al. (2020a b): Roeder et al. (2021) for different notions of identifiability in deep latent variable models. To show the identifiaiility of our model, we make a mild assumption on the generating function F, defined as follows.
Definition 4 (Weakly Injective Function). Let B(x,8) denote ball centered at point and with a radius of 5. We say that a function F S + T is weakly injective if (i) there exists xo E T and > 0 s.t. ([x)( = 1 for every x E B(Io, 5) n F(S), and (ii) {a: [[=((()]] = oo} C F(S) has measure zero with respect to the Lebesgue measure on F(S).
Remark 2. The assumption that functions are weakly injective indcod a weaker condition than the as- sumption that functions are injective. Note that ReLU network networks are generically weakly injective under simple assumptions on their architecture. See Appendix H of Kivva et al. 2022) for more details.
7

---

Published in Transactions on Machine Learning Research (01/2025)
With mild assumption that the generation function F is weakly injective, show the identifiability of our model as the following Theorem.
Theorem 1. Let F be the generation function of our proposed causal model with hidden confounders
graphs, defined F) (A, (FA(Z, Fx, (), Suppose F is weakly injective and the hidden confounders follow GMM prior distribution. Additionally, we assume that within the GMM, there erist at least two components, and such that das * o2
Z Sgué for j, = L, .9- Under these assumplions, C) is identifaable from P(A,X,5, up to permulation, scaling, and/or translation.
We first show that identifying the joint distribution P(Z, C) from P(A,X, can be reduced to identifying P(Z) from P(A, x, S). Then we show that P(Z) is identifiable from P(A, XXS) S) up to permutation, scaling, and/or translation of Z. The complete proof of this theorem is given in Appendix A Theorem I establishes that incorporating a GMM as the prior distribution ensures that the learned hidden confounders recover the true ones to a certain extent. This implies that we can better recover the ground truth of the joint distribution P(Z,A, A, X.5) among node features X, graph structures A, sensitive attributes S, and the hidden confounders Z, enabling to recover the true counterfactual graphs. See Section 5.3 for empirical studies.
Remark 3. Kivva et al. 2022 delves into the decoders of VAE models, primarily addressing tabular data. In contrast, our approach uses a conditional graph VAE consistent with our proposed causal model, enabling the generation of counterfactual graph data conditioned on sensitive attributes. The non-iid nature of graph data, combined with the need for conditioning on sensitive altributes, introduces significant challenges to the existing identifiability theories, making it non-trivial to extend to our case. We provide theoretical evidence demonstrating that GMM can enhance the identifiability of conditional VAEs when applied to graph data.
5 Experiments
In this section, we evaluate the proposed method both synthetic and real-world graphs. Experimental results show that method outperforms many baselines node classification tasks in terms of both fairness and accuracy. Furthermore, we conduct experiments on synthetic datascts to verify the identifiability of our model. More experimental results are given in Appendix E
5.1 Experimental Settings
Setup. To compare our method with other baselines, we train GCN (Kipf & Welling 2017 based classification model with different augmentations. We evaluate the performance of our method and other baselines by the averaged testing accuracy and counterfactual fairness of the classification model over five runs. For a fair comparison, we use the same architecture of the classification model. See more experimental details Appendix [
Evaluation Metrics. We use accuracy evaluate the prediction performance of the classification model node classification tasks. To quantify counterfactual fairness, we define the metric
1 Σ P ACF = ni
where 5(i) denotes the vector obtained by flipping the sensitive attribute of node i, and Y, is the prediction for node See more evaluation metries in Appendix E.1
Baselines. We compare method with the following baseline methods, including (1) No augmentation,
which only uses the original graph to train the downstream classifier; (2) NIFTY (Agarwal et al. 2021]. which creates counterfactual graphs by flipping the sensitive attribute while leaving other node features and graph structures unchanged; (3) GEAR (Ma et al., 2022), which uses a graph auto-encoder trained with fairness constraints to generate counterfactuals. Note that both NIFTY and GEAR use contrastive objectives to ensure counterfactual fairness of the learned representations, but we only use the counterfactual generation part of both approaches to augment datasets and train the downstream classifier.
8

---

Published in Transactions on Machine Learning Research (01/2025)
Table 1: Comparisons between our method and baselines on node classification tasks in terms of accuracy and counterfactual fairness. The best results are shown in bold.
No auginentation
NIFTY
GEAR
GraphCFF
Dataset
ACC f
ACF 4
ACC 1
ACF 4
ACC
ACF 4
ACC 1
ACp $
Synthetic Linear
90.00 + 1.41
9.63 + 0.61
88,20 = 0.17 6.63 = 0.46
85.60 = 2.05
4.00 # 1.56
88.20 = 0.47
3.47 = 0.19
Synthetic NonLinear
89.00
0.82
14.27 1 0.98
89.30 à 0.47 6.37 1 0.29
86.20 1: 1.41
6.70 1 1.81
90.00 1 0.82
2.60 1 0.43
Synthetic Noise
92.60 + 0.94
7.17 +: 1.35
91.6
0.47 6.40 0.64
86.40 = 4.03
4.33 + 1.71
90.40 - 1:25
2.47 = 0.90
German
68.00
18.93 = 1.75
67.00 0.82
67.60 = 1.89
6.60 + 2/11
68.30 1.70
= 0.70
Credit
0.24
25.31 + 17.88
79.60 0.30
79:27 = 0.21
8:49
1.16
77.48 0.37
1.76 = 0.32
Bail
94.67 0.11 65.05
0.12
91.17 # 0.20 65.38 + 0.22
88.31 = 0.10
55.72 + 15.61
82.73 + 4.84
38.01 + 1.84
Synthetic Datasets. We use our proposed causal model to create three synthetic datasets, namely Syn- thetic Linear, Synthetic NonLinear, and Synthetic Noise. The value of hidden confounders Z, sensitive attribute S, the adjacency matrix A and node feature X are computed by ancestral sampling. In Synthetic Linear, Fx, and Fx, are full-rank linear transformations created by repeatedly initializing a matrix with elements sampled from standard normal distribution until a non-singular matrix with a non-zero deter- minant is obtained. For Synthetic NonLinear, we use random initialized multi-layer perceptrons (MLPs) for Fx, and Fx,. Synthetic Noise is generated by randomly flipping adjacency matrix entries and adding exponential noise to node features. Each datasot is randomly partitioned into training, validation, and test sets, at proportions of 80%, 10,, and 10%, respectively. In the syuthetic datasets, we can fully manipulate the data generation process and thus easily generate the counterfactual graphs. For each node, we flip its sensitive attribute to get new sensitive attribute vector S Counterfactual graphs are then generated ((s-5)) = {A (S+S"): X ((s)))): S"), where A(s = FA(Z.S)) and X ((SeS)) = Fx (Z, (r)) See Appendix D.1 for more details.
Real-world Datasets. We further demonstrate the advance of our method using three real-world datasets (Agarwal et al. 2021), including German, Credit, and Bail. The German dataset contains 1000 nodes, with each node representing client of German bank. The edges between these nodes represent similarities between their corresponding credit accounts. The dataset uses gender the sensitive attribute, and the lask is to predict the credit risk status of clients, categorizing them either good or bad risks. Next, the Credit dataset consists of 30,000 nodes, with each node representing an individual with features such as oducation, credit history, and age. The edges between these nodes represent the similaritios in spending and payment patterns among these individuals. Age is treated as the sensitive attribute in this dataset, and the task is to predict whether an individual is likely to default on a credit card payment. Finally, the Bail dataset includes 18,876 nodes, with each node representing a defendant who was released on bail from U.S. state courts between 1990 and 2009. The edges between these nodes represent the similarities in their criminal histories and demographics. In this dataset, race is the sensitive attribute, and the task is to predict whether defendants will bail, i.e., the individuals who are less likely to commit a violent crime if released. For all three datasets, we randomly split 80% 10t///1%///0 for training, validation, and test datasets. See more details in Appendix D.1
5.2 Experimental Results
Fairness and Accuracy Performance. Table 1 shows accuracy and counterfactual fairness metrics of our method, compared with baselines in Section 5.1 on both the synthetic datasets and the real-world datasets. Our method consistently achieves the best counterfactual fairness performance all six datasets. For example, compared to only using the observed graph data without any augmentations, reduces counterfactual fairness by 63.9%, 81.8%, and 65.6% on Synthetic Lincar, Synthetic NonLincar, and Synthetic Noise, ively,ively, with comparable accuracy performance. It is worth noting that in some cases, our method can improve counterfactual fairness with little sacrifice to accuracy performance, or even enhance the accuracy performance. For example, compared to no augmentations, our method can achieve a higher accuracy performance on Synthetic NonLienar and German datasets. Such observations demonstrate the advance of our proposed method.
method
9

---

Published in Transactions on Machine Learning Research (01/2025)
Synthetic Linear
Synthetic NonLinear
Synthetic Noise
00
90-
03
69-
ACC
0
ACC
67
68
NIFTY
NIFTY
NIFTY
08
GEAR
GEAR
66-
GEAR
05
Baseline
Baseline
Baseline
CF
CF
CF
German
Credit
Bail
55
ours
OUTS
NIFTY
NIFTY
70
GFAR
GEAR
ACC
Baseline
ACC
ACC
Baseline
1
curs
NIFTY
GEAR
67
10
74
30
CF
CF
Figure 2: Accuracy and counterfactual fairness trade-off on the six datascts. A better trade-off is achieved when the performance appears in the upper left corner where higher accuracy and lower prediction bias are obtained simultaneously.
Fairness and Accuracy Trade-off. We further compare the fairness and accuracy trade-off performance of our method with baselines on both the synthetic datasets and the real-world datasets. As shown in Figure 2 we create Pareto front curves by assigning different weights to the counterfactual graphs generated by each method during the training process of the classifier model. The upper-left corner point represents the idcal performance, i.c., the highest accuracy and lowest prediction bias. The results show that our method achieves a good fairness and accuracy trade-off on the datasets.
5.3 Identifiability Evaluation
In this section, we investigate the identifiabliiyy of our model. We conduct experiments sup- port thcoretical analysis in Section To quantify iddenifiiabllly, we use the mean corre- lation coefficient (MCC) metric, as in previous studics [Khemahhem et al. 2020b Kivva et al.) 2022 Khemakhem et al.] 2020a). Given two
Table 2: Identifiability study of our model.
GraphCFF w/o GMM
Graph
Dataset
MCC₂
MCC,at
MCC₂
MCC..t
Syuthetic Linear
0.66
0.68
0.88
0.92
Synthotlc NonLinear
0.55
0.56
0.85
multivariate random variables, the MCC met- ric calculates the maximum linear correlations up to permutation of components. We compute two types of MCC values. The first, denoted MCCgt. measures the MCC value between the learned and ground truth hidden confounders Z. We report the average MCC value of ten different runs. A high MCCgt value indicates successful recovery of the true hidden confounders. The second, denoted as MCCaolf, involves training the same model multiple times and calculating the MCC for every pair of learned hidden confounders. Specifically, let (1), ... ZNN) be the learned hidden confounders of different runs. We compute the MCC value for every pair 2 z and re- port the average MCC value. A high MCCself value indicates that the learned hidden confounders converge to unique solution. We evaluate our identifiable model, 'GraphCFF", with non-identifiable variant, 'GraphCFF w/o GMM; In this variant, we replace the GMM prior with a standard Gaussian distribution, so the identifiability of 'GraphCFF w/o GMM' is not guaranteed. The results in Table 2 demonstrate that our model achieves MCC.af over 0.85 for all three datasets, indicating stable learned hidden confounders. On the synthetic linear dataset, our model achieves an MCCgt value of 0.88, showing its capability to accurately recover hidden confounders. Furthermore, GraphCFF outperforms CGraphCFF w/o GMM' terms of both MCCgt and MCC values, indicating the importance of GMM prior.
Syuthetic Noise
0.88
model's identifiability using three synthetic datasets. We compare
10

---

Published in Transactions on Machine Learning Research (01/2025)
5.4 Runtime Analysis
In this subsection, provide the complexity analysis and running time comparison of GraphCFF against bascline methods. During the counterfactual gener- ation step, GraphCFF computes the counterfactual graph, thus having space complexity of O(n² +n p) where n is the number of nodes in the graph, and p is the dimension of node features. The time complexity of GraphCFF depends on the choice of the generative model and the inference model. In our experiments, the inference model uses two GraphSAGE layers and the generative model uses one GraphSAGE layer to generate node features, thus having the time complexity of O(3(e+n) +n²), where n and e are the number of nodes and edges in the graph, respectively. The running time results are shown in Table 3 It's worth noting that both GraphCFF and GEAR require pre- are-training for the augmentation model, whereas NIFTY does not. We measure the time taken to train GraphCFF and GEAR over 20,000 steps. The evaluation time in the following table refers to the time needed train a downstream classifier with counterfactual augmentations. For all methods, this involves 50,000 training steps of the downstream classifier. As shown in the table below, while GraphCFF incurs higher computational cost than NIFTY, it has a comparable cost to GEAR.
Table 3: Runtime comparison between our method and basclines on the Synthotic Linear datasct.
Runtime Training Evaluating 750
NIFTY
GEAR
GraphCFF
0
1436
852
2515
2400
6 Conclusions
In this work, we propose a method, known as GraphCFF, to address the fairness issue of GNNs by augmenting graph data with counterfactual generation. We introduce a causal model with hidden confounders on graphs, which considers the existence hidden confounders affecting both node features and graph structures. We use an identifiable graph VAE model with Gaussian mixture prior distribution to recover counterfactuals, enabling the learning of counterfactually fair downstreem classifiers. Through experimental results, demonstrate that our method can significantly improve counterfactual fairness while not sacrificing much accuracy. Furthermore, theoretical analysis and empirical results provide convincing evidence for the ability of our mothod to accurately identify hidden confounding factors.
Acknowledgements
We gratefully acknowledge the insightful discussions with Yang Shen. This work supported in part by National Institutes of Health under grant U01AG070112 and National Science Foundation under grants IIS-2239257 and IIS-2431515.
References
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pp. 2114 2124. PMLR, 2021.
Kartik Ahuja, Jason Hartford, and Yoshua Bengio. Properties from mechanisms: an equivariance perspective on identifiable representation learning. arXie preprint arXiv:2110.1 15796, 2021.
Kartik Ahuja, Jason S Hartford, and Yoshua Bengio. Weakly supervised representation learning with sparse perturbations. Advances in Neural Information Processing Systems, 35:15516-15528, 2022.
Miguel A. Poureira-Perpinase Mode-finding for mixtures of gaussian distributions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(11):1318-13 1323, 2000.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 680-688 2021.
11

---

Published in Transactions on Machine Learning Research (01/2025)
Yushum Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairness for graph neural networks: A ranking based approach. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 300 310, 2021.
Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, pp. 1259-1266 2022.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramaniin. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international con- ference knowledge discovery and dota mining, pp. 259 2015.
Adam Foster, Árpi Vezér, Craig A Glastonbury, Páidí Creed, Samer Abujudeh, and Aaron Sim. Contrastive mixture posteriors for counterfactual inference, data integration and fairness. In International Confer- ence on Machine Learning, pp. 6578 6621. PMLR, 2022.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. In Proceedings of the 36th International Conference Machine Learning, pp. 2083-2092, 2019.
Hongyang Gao, Yi Liu, and Shuiwang Ji. Topology-aware graph pooling networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(1))44512 45188481-1441 2021.
Madelyn Glymour, Judea Pearl, and Nicholas P Jewell. Causal inference in statistics: primer. John Wiley & Sons, 2016.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Sander Greenland, Judea Pearl, and James M Robins. Confounding and collapsibility in causal inference. Slatistical science, 14(1):29 46, 1999.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in nearal information processing systems, 30, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, Qingquan Song, Jundong Li, and Xia Hu. Geometric graph representation learning via maximizing rate reduction. In Proceedings of the ACM Web Conference 2022, pp. 1226-1237, 1237, 2022.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advonces in neural information processing systems, 29, 2016.
Aapo Hyvärinen and Petteri Pajunen. Nonlinear independent component analysis: Existence and uniqueness results. Neural networks, 12(3):429-433) 1999.
Zhimong Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. Fmp: Toward fair graph message passing against lopology bias. arXiv preprint Xr::::2202.00 187, 2022a.
Zhimeng Jiang, Xiaotian Han, Chao Fan, Fan Yang, Ali Mostafavi, and Xia Hu. Generalized demographic parity for group fairness. In International Conference on Learning Representations, 2022b.
Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou. Variational deep embedding: An unsupervised and generative approach to clustering. arXiv preprint arXie: 1atrr161..05111 1.05148, 2016.
Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong. Inform: Individual fairness on graph mining. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 379 389, 2020.
12

---

Published in Transactions on Machine Learning Research (01/2025)
Ilyes Khemakhem, Diederik Kingma, Ricardo Monti, and Aapo Hyvarinen. Variational autoencoders and nonlinear iea: A unifying framework. In International Conference on Artificial Intelligence and Stalistics, pp. 2207 2217. PMLR, 2020a.
Tyes Khemakhem, Ricardo Monti, Diederik Kingma, and Aapo Hyvarinen. Ice-beem: Identifiable conditional energy-based deep models based on nonlinear ica. Advances in Newral Information Processing Systems, 11112768-12778 2020b.
Niki Kilbertus, Mateo Rojas Carulla, Giambattista Parascandolo, Moritz Hardt, Dominik Janzing, and Bernhard Schölkopf. Avoiding discrimination through causal reasoning. Advances in neural information processing systems, 30, 2017.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Con- ference on Learning Representations (ICLR), 2015.
Diederik Kingma and Max Welling. Auto-Encoding Variational Bayes. In 2nd International Confer- ence on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Bohdan Kivva, Goutham Rajendran, Pradeep Ravikumar, and Bryon Aragam. Identifiability of deep gener- alive models without auxiliary information. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 15687-15701. Curran Associates, Inc., 2022.
O Deniz Kose and Yanning Shen. Fair node representation learning via adaptive data augmentation. arXiv preprint arX:::2201.082 08549,, 2022.
Abhishek Kumar and Ben Poole. On implicit regularization in f-vaes. In International Conference Machine Learning, pp. 5480-5490. PMLR, 2020.
Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
Shen Li, Bryan Hooi, and Gim Hee Lee. Identifying through flows for recovering latent representations. arXiv preprint Xic: 10009..... 12555, 2019.
Hongyi Ling, Zhimeng Jiang, Meng Liu, Shuiwang Ji, and Na Zou. Graph mixup with soft alignments. Proceedings of the 40th International Conference on Machine Learning, 2023a.
Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou. Learning fair graph representations via
automated data augmentations. In The Eleventh International Conference on Learning Representations, 2023b. URL htttps://openreeee
net/forunmidieaeeeooooo 7id=1 Seeprrummddd1_0WGPPPPL1
Meng Liu, Youzhi Luo, Kanji Uchino, Koji Maruhashi, and Shuiwang Ji. Generating 3D molecules for target protein binding, In Proceedings of The 39th International Conference on Machine Learning, pp. 13924, 2022.
Christos Louizos, Uri Shalit, Joris M Mooij, David Sontag, Richard Zemel, and Max Welling. Causal effect inference with deep latent-variable models. Advances neural information processing systems, 30, 2017.
Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. Learning fair node representations with graph counterfactual fairness. In Proceedings of the Fifteenth ACM International Conference on Web Search and Dala Mining, pp. 695 695-703, 2022.
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Fairness through causal awareness: Learning latent-variable models for biased data. aixiv preprint arx: 1001000990211 2018.
13

---

Published in Transactions on Machine Learning Research (01/2025)
David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Fairness through causal awareness: Learning causal latent-variable models for biased data. In Proceedings of the conference on fairness, accountability, and transperency, pp. 349 358, 2019.
Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1 35, 2021.
Ruth M Mickey and Sander Greenland. The impact of confounder selection criteria on effect estimation. American journal of epidemiology, (1) 127, 1989.
Graziano Mita, Maurizio Filippone, and Pietro Michiardi. An identifiable double vae for disentangled rep- resentations. In International Conference Machine Learning, pp. 7769-7779. PMLR, 2021.
Hamed Nilforoshan, Johann D Gaebler, Ravi Shroff, and Sharad Goel. Causal conceptions of fairness and their consequences. In International Conference on Machine Learning, pp. 16848 16887. PMLR, 2022.
Alexandra Olteanu, Carlos Castillo, Fernando Diaz, and Emre Kıemman. Social data: Biases, methodological pitfalls, and ethical boundaries. Frontiers in Big Data, 2:13, 2019.
Judea Pearl. Simpson's paradox, confounding, and collapibility. Cousality: models, reasoning and inference, pp. 173 200, 2009.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: Cambridge UniversilyPress, 19(2), 2000.
Felix Petersen, Debarghya Mukherjee, Yuckai Sun, and Mikhail Yurochkin. Post-proccssing for individual fairness. Advances Neural Information Processing Systems, 34, 2021.
Kevin Petrasic, Benjamin Saul, James Greig, Matthew Bornfreund, and Katherine Lamberth. Algorithms and bias: What lenders need to know. White & Case, 2017.
Alvin Rajkomar, Michaela Hardt, Michael D Howell, Greg Corrado, and Marshall H Chin. Ensuring fairness in machine learning to advance health equity. Annals of internal medicine, 169(12):866-877) 2018
Joseph D Ramscy, Kun Zhang, Madelyn Glymour, Ruben Sanchez Romero, Biwci Huang, Imme Ebert- Upholf, Savini Samarasinghe, Elizabeth A Barnes, and Clark Glymour. Tetrad a toolbox for causal discovery. In 8th international workshop on climate informatics, 2018.
Geoffrey Roeder, Luke Metz, and Durk Kingma. On linear identifiabiliy of learned representations. Tn International Conference on Machine Learning, pp. 9030 9039. PMLR, 2021.
David W Scott. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 2015.
Peter Sorrenson, Carsten Rother, and Ullrich Köthe. Disentanglement by nonlinear ica with general incompressible-flow nelworks (gin). In International Conference on Learning Represenlations (ICLR), 2020.
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence, 2021.
Harini Suresh and John V Guttag. A framework for understanding unintended consequences of machine learning. Xix preprint
2, 2019.
Henry Teicher. Identifiability of finite mixtures. The annals of Mathematical statistics, pp. 1265 1269, 1963.
Yixin Wang, David Blei, and John P Cunningham. Posterior collapse and latent variable non-identifiability Advances in Neural Information Processing Systems, 34:5443 5455, 2021.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovee. Graph information bottleneck. Advances in Neural Information Processing Systems, 33:20437-2044 204488, 2020.
14

---

Published in Transactions on Machine Learning Research (01/2025)
Yongkai Wu, Lu Zhang, and Xintao Wu. Counterfactual fairness: Unidentification, bound and algorithm. In Proceedings of the Twenly- Fighth International Joinl Conference on Arlificial Intellignnce, 2019a.
Yongkai Wu, Lu Zhang, Xintao Wu, and Hanghang Tong. Pe-fairness: A unified framework for measuring causality-based fairness. Advances in neural information processing systems, 32, 2019b.
Sidney J Yakowitz and John D Spragins. On the identifiability of finite mixtures. The Annals of Mathemalical Statistics, 39(1)2209 214, 1968.
Mengyue Yang, Furui Liu, Zhitang Chen, Xinwei Shen, Jianye Hao, and Jun Wang. Causalvae: Disentangled representation learning via neural structural causal models. In Proceedings of the IEEE/CVF Conference on Compuler Vision and Pallern Recognition (CVPR), pp. 9593 9602, June 2021.
Aoqi Zuo, Susan Wei, Tongliang Liu, Bo Han, Kun Zhang, and Mingming Gong. Counterfactual fairness with partially known causal graph. arXiv preprint arXiv:2205. 189972,,..1199, 2022.
A Proof of Identifiability
Theorem 2. Let F be the generation function of proposed causal model with hidden confounders graphs, defined F), (A,X) (FA(2,S), Fx S), Suppose F is weakly injective and the hidden confounders follow GMM prior distribution. Additionally, we assume that within the GMM, there crist at least two components, and such that
2 Lg.k for j, = -.... . Under these 2as * o22
assumptions, P)Z,C) is identifiable from P(A,X,5) to permutation, scaling, and/or translation.
Proof. The proof of this Theorem is done in the following three steps.
In the first step, we aim to show that the problem of identifying the joint distribution P(Z,C, C)) from P(A,X, S) can be reduced to identifying P(Z) from P(A,X,5) This reduction is based on the well- known fact that finite Gaussian mixture distributions are identifiable up to permutations of the Gaussian components (Yakowitz & Spragins 1968 Teicher 1963). Specifically, since finite mixtures of Gaussian dis- tributions are identifiable up to permutation of the Gaussian components, we can recover both the mixture weights P(C') and the corresponding Gaussian components P(Z This implies that P(Z, C) can be identified from P(Z). Therefore, it is sulficient to prove that P(Z) is identifiable from ((A,X,S up to permutation, scaling, and/or translation.
In the second step, we show that P(Z) is identifiable from P(A,X,5) up to an affine transformation of Z. It proved by Theorem
In the third step, we show that using the assumption that are independent latent factors, then P(Z) is identifiable from P(A,X, S) up to permutation, scaling, and/or translation of Z. Since P(Z) is identifiable up to an affine transformation by the second step, the claim follows from Theroem S
A.1 Identifiability of Latent Factors
Lemma 3. Let Z 12,, Z2........ Zn] _2xx be the matris of latent factors, where each Zi E R9, The latent factors of different nodes are independent of each other. Suppose that for each Zs, the probability distribution follows the same Gaussian Misture Model (GMM) with K components and diagonal covariance motrices:
K
P(Z,) = Σ T& TZN(ua Et),
(8)
where Tk is the mixture weight for the k-th Gaussian distribution, μi the mean vector, and Σx ding( 2 o is the diagonal covariance matria.
15

---

Published in Transactions on Machine Learning Research (01/2025)
Then, when consider the whole matriz Z vector of size 9 (reshaped from the matriz), the joint distribution P(vec(Z)) cnn be expressed as Gaussian Mixhure Distribulion.
Proof. Consider the reshaped matrix Zvec = 129,2 -3. ... , Let's compute the joint probability P(Zvec):
P(Zvec) P(Z ... 2n) II P(Z))
(9)
Since Eg is diagonal, express the Gaussian distribution product of univariate Gaussian distri- butions:
MZ. Σx)
II
Ni (y5. Rgg).
(10)
5=1
Now, substituting this expression for P(Z.):
P(Zve) II
Th II N 10ng
(11)
1=1
Now, let's look at one entry of Zves say Zuws which is the element in the u-th row and w-th column of Z. Its probability distribution can be written as:
P(Zuw)= Σ TZN(Zuw okw). R=1
(12)
Since each entry Zum is independent, the joint distribution of Zver is indeed product of Gaussian Mixture Distributions, and each term is mixture of univariate Gaussian distributions:
K Σ
P(Zeec)
P(Z,)) i=1==1
(Zyylly ozg)
(13)
Thus, when the covariance matrices are diagonal, the joint distribution of the reshaped matrix Zveo can be expressed single Gaussian mixture distribution.
Lemma 4. Let F be the generation function of our proposed causal model with hidden confounders gruphs, defined as F) = (A, X) = (AZ. We have F is a piecewise offine function.
Proof. When extra inputs are used combine piecewise affine functions, the resulting function remains a piecewise affine function. These additional inputs be used to determine which linear segment piece to use for particular input value. In other words, if F is piecewise affine function for every fixed S, then F is indeed piecewise affine function. Therefore, it is sufficient to show that, when S is fixed, F is piecewise affine function.
We first consider the output A. Recall that A is computed as
1, if s: # s, and sim(Z,, (Z, 1 Pauter
Aij = 1, if s; 9, and sim Z2, 2,) > 1 Pitra otherwise
for i,j =1," 1,.r,,..
(14)
16

---

Published in Transactions on Machine Learning Research (01/2025)
where sim(-) computes the similarity between latent factors of two nodes. Pinter and Pintra are two constants that represent the intra-connection and inter-connection thresholds, respectively. For fixed S, A is deter- mined by applying comparison operation to the similarity measure sim{ (2, 2,) against thresholds 1- Piter and 1 - -iitra- Within each piece of the domain, defined by the conditions, the output As is constant. Therefore, A is a piecewise constant function with respect to Z when S is held constant, which can be considered special case of a piecewise affine function.
Next, consider the output X. Recall that X is computed as
X, = Fx, s,) + AGG((Fx : J N.)) for i = 1, ,
(15)
where N, denotes the set of the nodes connected to the node in the graph, AGG(.) denotes an aggregation function, and Fx, and Fx, are two piecewise affine transformation functions. Then Fx, and Fx, divide the input space to multiple intervals 71: 22. .... In the interval 11, Fx, and Fx, are affine functions and can be denoted as Fx, s2 = Wi Z + Bis + B1 and (2, = W2Z + B2s B/ respectively, where W1 and W2 are some matrices, and B1, Bi, B2, and B2 are some vectors. Then we have X; = Wiz; + Bıs; + B' + AGG + B28, + B²)= j E N;}). If we consider each possible configuration of A as defining a different 'piece' of the domain, then within each piece, the aggregation function, such as mean operation, is a linear function. Therefore, each element of X can be considered as the result of a piecewise affine function, implying that the generation of matrix X as a whole can be considered piecewise affine process.
Therefore, we conclude that the overall function F can be considered a piecewise affine function.
Lemma 5. Consider a pair of finite GMMs
J P Σ (, and p'= - (,,
J
(16)
Assume that there exists a boll B(zo, 5) such that P and P induce the same measure on B(xo: 8). Then P= P', i.e., J= J' and for some permutation T we have X; = Xr(9 and (m4, E,)= = (1) Ey (1))
Proof. We first show that the GMMs are real analytic functions. This step is straightforward. It is well known that the multivariate Gaussian density function is a real analytic function, and finite sum of real analytic functions is also real analytic. Therefore, both P and P' are real analytic functions.
Next, we use the identity theorem for real analytic functions in our case. The identity theorem for real analytic functions states that if a real analytic function is equal to another real analytic function on an open subset of its domain, then the two functions are equal everywhere on their common domain. In our case, P and P are equal on the ball B(xo, 5). By the identity theorem, we conclude that P=P"
In the last step, we need to show that the Gaussian components are the samne between P and Pr. First, we argue that J = J'. Since P and P' are equal everywhere, the mumber of Gaussian components must be the same, because each component contributes uniquely to the overall shape of the GMM. Next, assume without loss of genorality that A 2 X2 2 ... 2 X and X; 2 X/ 2 2 Xy. We arguc that X3- = XX for all j. Suppose for contradiction that there exists some j such that > * Then there must exist + j such that
jusch AR A Xye because these mixture weights are themselves probabilities that satisfy the constraints E/e =1 and A O. Without loss of generality, assume that X Xy. Then we have X₁ > Av- However, in the neighborhood of the mode of the k-th Gaussian component, p' should be greater than P, which contradicts the fact that P = p' everywhere. Finally, we show that for each j, (1y, E,) = (nlz Σ)). This is due to the fact that the mean and covariance completely characterize a Gaussian distribution, and two Gaussians that are equal everywhere must have the same mean and covariance.
This completes the proof. We have shown that if two GMMs induce the same measure on ball, then they must be identical, up to permutation of the components.
17

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 6. Kivva et al. 2022 Let f.g be two piecewise offine functions that weakly injective. Let Z N E,) and Z' Σ XjN Ey)) be pair of GMMs. Suppose that f() and g(Z)) are equally
distributed. Then there exists an invertible offine transformation h such that h(Z) = Z', i.e., J = J' and for some permutation 5 E SJ we have X; = Xx()) and hyN Σ,) = (N F(())
Here, we outlinc the key idea the proof. Initially, given that both piccewisc affine functions f and g demonstrate are weak injective, it can be inferred that. f and g are invertible neighborhood of specific point. Following this, based on Lemma 5 can be demonstrated that there exists an invertible affine transformation between Z and Z'. See complcte proof of this thcorem in Appendix A of Kivva et al. (2022). Theorem
@ implics that mixture model whose components are piecewise affine transformations of Gaussian is identifiable.
Theorem 7. Assume that (Z, A, X,S) are distribuled according to our proposed causal model with hidden confounders on graphs. If the generation function F is weakly injective, then P(Z) is identifiable from P(A,X,5) up to on affine transformation.
Proof. Assume we have two models, including (1) (Z, A,X, and a geneartion function F, and (2) (Z', A', X', S*) and a geneartion function F". If two models are well trained, then we have P(A', X' P(A,X S) and P(S) P(S'). In other words, F(Z) and F'(Z') have the same distribution. According to
Jemma 3 we know Z and Z' are pair of GMMs. Moreover, by lemma 4 F and F" are piecewise affine functions. Therefore, by Theorem i there exists an invertible affine transformation h such that h(Z) Z'. In other words, P(Z) is identifiable up to an invertible affine transformation.
A.2 Identifiability up to Permutation, Scaling, and Translation
Theorem 8. Kivva et al. 2022 Let 2 2, and d > 0 for ls = 1,... J. Let Z be given by
7 ~
NwN( Ex)
(17)
Assume that E5 is diagonal for = 1......... Let Y WZ + for some matrix W and some vector B. Moreover, assume that there exist indices i,, [J], such that all numbers ((Er, a (Eig):: ht. | E [ml) are distinct. Given Y, one recover invertible linear map W such that (W") W QD, where Q is permatation matria and D is diagonal matriz with positive entries.
See the complete proof of this Theorem in Appendix E of Kivva et al. 2022
Consider h as an invertible afline transformation, and let Z' be defined as Z' = (2). By Theorem we have that Z can be recovered from Z' up to a permutation, scaling, and translation. In other words, given that every covariance matrix Σ, is diagonal, we can extend the conclusion that Z can be recovered up an affine transformation a more refined conclusion where can be recovered subject permutation, scaling, and translation.
18

---

Published in Transactions on Machine Learning Research (01/2025)
B ELBO
In this section, we provide detailed derivations of ELBO.
log P(A, Ø
log P(A. =BQ(ZIA,X15)
P(Z)A,
log P(A,X, P
-BQ(ZIA.X.5)
P(A,X,
2BQ(ZIAXX.S)
log Q(Z]A,
log S()
-BQ(ZIA,X,S)
Q(Z|A,X,5
1 (Q(ZIAXX
S)A(Z A, (
log
Q,
=BQ(ZIA,X flog P(A|Z,5) log P(X A, Z,S) + log P(Z(S) log Q(Z]A,X,S))
BQ(ZIA.X.S)) llog P(A Z, S) + log P + log P(Z) log ( A,
Equation (a) holds because of the factorization of joint probability A, P(Z,S) ((X Z, S), and Equation (b) holds due to the independence between sensitive attribute and latent factors Z.
PIA.X,2,CI33
log P(A, XIS) -BQ(Z.CIAXX.S)
log X(Z,CIA,X,5)
log P[A.X.,2.C19)Q12,CCA, S)
-EQ(Z.CIAXx.5
PIA.CIAAX,,912224CAAA.... log P(A.X;2,C155
2BQ(Z.CIA.X.9)
Q(Z,CIA,X,5) P(A.XIZ,SSC)PP(ZCCISS
-EQIZCCIAX
log
Q(Z,CIA.X,9)
P(A.XIZ,SSP((2CCIS)
-EQ(Z.CIAX..)
log
Q(Z,CIA.X,,)
-EQIZ.CIAXx.)
log
Q(Z,CIA,X,S)
=EQ(Z,CIA,X,, 3) log P(A 8) log P(X A, Z,S) log PIZ,CIS)
-log Q X. log ((CIA,X,S)
= -EQíZ,CIA. .) log P(A S) + log P(X A, 2, log P(Z,C)
-log Q( A, X, S) - llo QCI|A, X, S)]
-EQiz.CIA, [lo P(A 8) + log P X A, Z,5) log P(Z(C)
+log P(C) log Q 4, X S) log QCC|A, X)]
C More Discussions
C.1 Fairness-aware Graph Augmentations
Fairness-aware graph data augmentation is an essential strategy mitigating bias graph neural networks (GNNs). A primary issue in fairness that the bias training datasets significant source of discrimina- tive behavior in models (Mehrabi et al. 2021 Olteanu et al. 2019 GNN models may inherit, or amplify
19

---

Published in Transactions on Machine Learning Research (01/2025)
bias from training data (Dai & Wang 2021 adversely impacting groups defined by sensitive attributes such as race and gender. Hence, Fairness-aware graph data augmentation, which reduces bias in the training data, emerges as a highly effective strategy for enabling models to Iearn fair representations. Spinelli et al.] (2021) propose that the existence of edges connecting nodes with identical sensitive autributes can lead to prediction discrimination. To lackle this issue, they propose a biased edge drop algorithm that mitigates this tendency in graphs, thereby enhancing fairness in prediction tasks. Kose & Shen (2022) study correlations between sensitive attributes and learned node representations. They propose a series of graph augmentations aimed at minimizing the upper bounds of these correlations, resulting in improving fairness in GNNs. While previous methods rely on manually dis- covered properties of fair graph data in order to design fixed strategies, Ling et al. (2023b) propose learning fair representations via automated graph data augmentations. Their proposed Graphair can aulomatically identify and implement fairness-awan aware angmentations from input graphs, circumventing sensitive informa- tion while preserving other useful information. However, a significant shortcoming of these fairness-aware augmentation methods is that they ignore causal relationships in the augmented data. This omission could lead to situation where the augmented data does not adhere to realistic scenarios. For instance, in order to achieve fair prediction outcomes for both females and males, these methods may generate a lot of tall and heavy female samples, a distribution that does not accurately reflect real-world demographics. This prob- lem highlights the importance of incorporating causality into fairness-aware data augmentation strategies to ensure the creation of realistic and representative datasets for training GNNs.
This process can result in potentially discriminatory predictions,
C.2 Identifiability of Latent-variable Models
Deep latent-variable models, such as VAEs, have been extensively used for unsupervised learning of latent roprosentations. However, traditional results from nonlincar Independent Component Analysis (ICA) reveal fundamental issue in VAEs, namely the lack of identifiability, where different latent. variables can generate the same observed variables (Hyvärinen & Pajunen 1999). This issue hinders the approximation of the true joint distribution over observed and latent variables. A recent breakthrough by Khemakhem et al.] (2020a) demonstrates that the identifiability of VAES can be achieved up to certain nonlinear equivalences when side information is available. Building upon this idea, several hods have been proposed to achieve identifiability with some form of auxiliary information (Khemakhem et al.] 2020b Mita et al. 2021 Yang
ct al. 2021 Li al., 2019 Sorrenson et al.) (2020). For example, Yang et al. (2021) proposes to incorporate a Structural Causal Model (SCM) into a VAE model. During training, the true causal variables are used labels, which guide the learning process to disentangle the latent representations and encourage the model to learn meaningful and identifiable latent representation. Furthermore, [Ahuja et al. (2022 2021 propose methods that reduce the reliance on additional information. They show that if the underlying mechanisms guiding the evolution of latent variables are known, the latent variables can be identified up to the oquivariances of these mechanisms. In contrast, some approaches avoid using additional forms of supervision and aim to enforce identifiability in a purely unsupervised setting (Kivva el al., 2022: Wang el al.] 2021). These works demoustrate that identifiability is achievable under commonly adopted assumptions, indicating that auxiliary information may not be necessary. Another line of research focuses on restricting the selection of the variational family and prior distribution to improve identifiability [Kumar & Poole 2020).
While we follow Kivva et al. 2022 to incorporate a GMM prior in our framework to solve the non-identiffable issue of VAE, we would like to highlight the difference between Kivva et al. (2022) and our work. The fundamental difference between Kivva et al. (002)) and our work is that the identifiability problem in deep latent variable models is different from identifying the hidden confounders. Given that a VAE is a generative model, its latent variable can follow any prior distribution, as long as we can sample the latent variable from the prior distribution to generate new data. Kivva et al. (2022) aims to improve stability, consistency, and robustness of deep generative models. However, in our work, the latent factors are hidden confounders, which are integral to the ground truth data generation process of observed graph data. To address this challenge, our goal is to identify these hidden confounders, thereby facilitating a more reliable recovery of counterfactuals. In other words, we aim to recover the cansal model generating the observed graph data to improve counterfactual fairness, while Kivva et al. (2022) focus on lcarning a stable and robust deep generative model. From a technical perspective, Kivva et al. (2022) delves into deep latent variable generative models with particular focus the decoders of VAE models. In contrast, our approach uses
20

---

Published in Transactions on Machine Learning Research (01/2025)
conditional graph VAE which is consistent with our proposed causal model, generating counterfactual graph data conditioned on sensitive attributes. This focus differs from the theoretical foundation of Kivva et al. (2022), which primarily addresses tabular data. The inherent non-iid nature of graph data and the conditioning on sensitive attributes present challenges to the identifiability theory posited by Kivva et al. (2022), making it non-trivial to extend to our case. We provide theoretical evidence that GMM can facilitate the identifiability of conditional VAEs when applied to graph data, marking a theoretical advancement
the field.
C.3 Relation with Previous Studies about Counterfactual Fairness on Graphs
In comparison to prior research on counterfactual fairness in graphs, our causal model is more general. For example, NIFTY (Agarwal et al. 2021) considers a simple scenario where sensitive attributes are independent of both node features and the adjacency matrix. This situation merely a special case within our broader setting. Specifically, if both functions Fx and FA remain unchanged with respect to S, then sensitive attributes will not influence node features the adjacency matrix. Similarly, GEAR (Ma et al. (022) considers the scenario where S is the only confounder for both A and X. This is also a special case within our broader setting. Specifically, if both functions Fx and FA are invariant with respect to Z, then our causal model is equivalent to GEAR's scenario.
Moreover, we consider one of the significant challenges in graph data, namely the non-independence of nodes. This implies that modifications to one node could potentially impact another. In contrast, prior studies assume node features cannot be influenced by their neighbors. This more simplistic view is yet another specific instance within our broader framework. Specifically, if Fx, in Eq. (3) consistently returns zero, then the node features remain unafeectd by their neighbors. To further validate our approach, we provide experimental results, detailed in Appendix E.2 which demonstrate its effectiveness even in this specific scenario.
C.4 Assumption about Independence Between Hidden Confounders and Sensitive Attributes
Our primary objective is to derive trustworthy counterfactuals Importantly, can obtain accurate coun- terfactuals without the explicit computation of latent factors influenced by S. This means that we can produce consistent counterfactuals using just S and Z. Let Z' denote those latent factors influenced by S. Two causal relationships need to be considered.
1. In the causal graph, Z' is solely child of sensitive attribute S, meaning Z' is only causally affected by S. In this case, the value of Z' can be expressed Z' Fz (S), where Fz (.) describes how Z' is dependent on S. The generation process of observed graph data can be expressed as (A,X) = F(S, Z, Z'), where F corresponds to the generating mechanism from S, Z, Z' Given Z' = (S), we have (A, () = F, Z') = F(S, Z, (Z)) = FS, Z), where F' is an alternative function. This implies that the gencration process can be expressed only using and Z. Therefore, our proposed mothod can generate identical counterfactuals, as F(S', Z, Fz (S)) = F''
In the causal graph, Z' is the child of both sensitive attribute S and other latent factors independent of S. This implies Z' is causally affected by both S and Z. The value of Z' can be expressed as Z' Fz Z where (-) describes how Z' dependent on both S and Z. The generation process of observed graph F(S, Z, Z'), where F corresponds to the generating mechanism of
data can be expressed as (A, graph data from S, Z. Z'. Given Z' Fz (S, Z), we have (A,X) = F(S, Z, Z') F(S, Z, Fz (S, Z))
F'(S, Z), where F' is an alternative function. In this scenario well, our proposed method can generate the same counterfactuals, as F(S', Z, Fz Z)) = (S
In summary, even though there exist latent factors that can be affected by sensitive attributes, independence between Z and S is reasonable. This assumption suffices to recover reliable counterfactuals.
21

---

Published in Transactions on Machine Learning Research (01/2025)
C.5 Assumption about Gaussian Mixture Prior of Hidden Confounders
While existing works (Madras et al. 2018 Ma el al. 2022 Louizos et al. 2017 Foster et al. 2022) use a normal distribution as the prior distribution of latent factors, we use GMM as the prior distribution of hidden confounders. It's essential to note that a GMM with a single Gaussian component is equivalent to a normal distribution. This makes the normal distribution a special case of GMM. Therefore, our framework offers a more generalized approach compared to existing works. Moreover, GMM is a universal approximator of densities (Goodfellow et al., 2016 Parreira-Perpinan 2000; /Soott, 2015), meaning it can represent a wide variety of continuous density functions. With enough mixture components, any smooth density can be approximated by GMM to a specific nonzero level of accuracy. This highlights the adaptability of GMM in capturing various density distributions. In other words, our model can recover hidden confounders with diverse distributions, implying its superior applicability in real-world scenarios compared to existing works.
D
More Details on Experimental Settings
D.1 Datasets
We create three synthetic datasets, including Synthetic Linear, Synthetic NonLinear, and Synthetic Noise. For all three datasets, we generate a graph with n = 1000 nodes. We use a Gaussian mixture model with K = 5 components to generate the hidden confounders Z. For cach Gaussian component, cach component of mean vector μ4 take a value between -10 and 10, and covariance matrix Σς is a diagonal matrix with diagonal values equal to 0.1. The sensitive attribute for each node is sampled from a Bernoulli distribution as S. ~ Bernoullípp), where Pa = 0.5 is the probability of S: = 1. Afterwards, we generate the adjacency matrix A and node feature X using Eqs. (2) and (3) respectively. Node labels are generated in the same way as node features and then mapped to binary values. To be more specific, we generate the adjacency
matrix as follows,
1, if 8 F 8j and sim( Zz, > 1 -Putter
Aú =
L. if st = s, and sim(Z,,2,) > 1 - Pintra for i,j = 1,. ,,, n,
otherwise
where we use cosine similarity as the sim(-) function and set Pinter 5 x 10 Pitra 5 10-3, We use mean pooling the aggregation function in all three datasets. In Synthetic Linear, we set functions Fx, and Fx, two linear transformations. To create linear transfornation, we generate full-rank matrix. Specifically, we initialize matrix, denoted W, wherein each element is independently sampled from a standard normal distribution (0,, 1). Then we check the determinant of the matrix W. If the determinant is zero, indicating that the matrix is singular, we repeat the previous step to generate a new matrix until a non-singular matrix is obtained. The resulting matrix W represents the desired linear transformation. In Synthetic NonLinear, we set Fx, and Fx, as two non-linear transformations. These transformations are achieved by using randomly initialized MLPs. Specifically, we use threc-layer MLPs with Leaky-ReLD the activation function. In Synthetic Noise, we introduce randomness to the adjacency matrix entries and add exponential noise to node features. Specifically, we use Bernoulli distribution with a probability of 0.05 to decide whether each entry in the adjacency matrix should be flipped. Furthermore, we add noise e to each node's feature, where & is sampled from the exponential distribution as 6, ~ (> (0.().
For the real-world datasets, we use German, Credit, and Bail. The German dataset contains 1000 nodes, with each node representing client of a German bank. The edges between these nodes represent similarities between their corresponding credit accounts. The Credit dataset consists of 30, 000 nodes, with each node representing an individual with features such as education, credit history, and age. The edges between these nodes represent the similaritics in spending and payment patterns among these individuals. Bail dataset includes 18, 876 nodes, with each node representing a defendant who was released on bail from U.S. state courts between 1990 and 2009. The edges between these nodes represent the similarities in their criminal historics and demographics. For the ground-truth counterfactual, we use causal discovery methods implemented in Tetrad (Ramsey et al., 2018) generate the counterfactual data. To be more specific, generating ground-truth counterfactuals involves two main steps: generating the node attributes
22

---

Published in Transactions on Machine Learning Research (01/2025)
Table 4: Comparisons between our method and baselines on node classification tasks terms of ROC AUC, F1 score, DP, and EO. The best results are shown in bold.
Dataset
Mothod
ROC AUC f
f
DP 4
EO 4
No augmentation
95.96 0.39
88.75
2.09
10.55 + 0.94
12.02 3.49
NIFTY
96.26 1.62
89.14 0.79
11.18 = 1.89
15.72
1.75
Synthetic Linear
GEAR
94.20 1.82
86.61
2.05
5.90 2.85
13.26
5.01
GraphCFF
95.02 + 0.76
0.44 85.40
2.05 1.70
13.29 + 3.11
No augmentation
93.27 +: 1.18
90.76 1.02
20.21
2.05
9.72 1.96
NIFTY
92.51 + 0.90
91.86 0.56
14.20
1.80
5.56 1.36
Synthetic NonLinear
GEAR
86.30 + 3.86
87.62 + 1.57
7.76 + 3.04
3.89 + 2.75
GraphCFF
88.17 = 1.60
92.58 = 0.57
5.77 = 1.98
3.89 + 1.42
No augmentation
97.35 + 0.43
93.45 = 1.41
4.43 + 2.18
5.56 + 1.57
NIFTY
96.47 + 0.55
93.18 + 0.74
1.82 + 1.14
3.33 + 1.70
Synthetic Noise
GEAR
91.35 + 6.02
87.91 + 4.15
2.83 - 1.22
2.22 - 1.57
GraphCFF
95.40 0.96
91.55 0.46
3.21 0.95
1.11 1.36
No augmentation
64.68 2.26
78.52 1.41
16.96 = 6.58
14.18 6.88
NIFTY
63.79 3.40
78.54 1.79
6.19 = 2.06
7.25 5.67
German
GEAR
63.81 + 1.38
81.67 1.57
6.56 + 2.77
5.83 + 2.03
GraphCFF
61.56 + 2.22
82.35 + 1.81
2.15 + 2.04
1.45 + 2.05
No augmentation
75.93 + 1.27
87.97 1.13
1.91 + 1.60
1.03 + 2.20
NIFTY
75.91 + 0.67
88.13 + 0.78
1.36 - 0.49
1.27 + 0.49
Credit
GEAR
73.42 + 2.13
88.03 + 2.43
0.75 + 0.89
0.74 + 0.44
GraphCFF
72.36 1.12
87.20 + 0.73
0.24 = 0.34
0.41 + 0.58
No augmentation
96.45 1.18
91.54 = 1.32
6.76 + 1.51
2.26 1.02
NIFTY
96.19 0.50
91.53 0.70
6.15 0.34
1.49 1.33
Bail
GEAR
89.05 1.09
83.35
1.01
6.69 = 0.74
2.54 1.02
GraphCFF
88.97 + 1.38
82.83 1 1.85
5.53 + 1.23
2.07 + 0.77
and constructing the adjacency matrix. For the node attributes, we use the Peter- Clark algorithm to identify causal relationships among the attributes. We then flip the sensitive attribute and leverage these causal relationships to compute the counterfactual node attributes. For the adjacency matrix, the datasets (German, Credit, and Bail) use the Minkowski distance as the similarity measure to determine connections between nodes. Specifically, two nodes are connected if their similarity exceeds certain threshold. The thresholds are set as follows: for German, 80% of the maximum similarity between all nodes; for Bail, 60%; and for Credit, 60%. We follow the same procedure to generate edges in the counterfactual graphs.
D.2 Implementation Details
the same classification model to evaluate all methods. For the classification model, use GCN model. The number of GCN layers is two, and use global mean pooling the readout function. We set the hidden size 16. The activation function is ReLU. We use the Adam optimizer (Kingna & Ba 2015) lo Irain the classification model with x 10-4 learning rate and x 10-4 weight decay. We use NVIDIA RTX A6000 GPUs for all our experiments. datascts, we set the dimensionality of the hidden confounders and the number of components match the data generation process's ground truth. For real-world datasets, we align the dimensionality of the hidden confounders with that of the node features, setting the number of components to eight.
For fair comparison,
our experiments on synthetic
23

---

Published in Transactions on Machine Learning Research (01/2025)
Table 5: Comparisons between our method and baselines on Synthetic O-hop dataset. The best results are shown in bold.
Syuthetic O-hop
ACC 1
ROC AUC 1
CF +
No augmentation
73.67
2.05
77.84 + 3.11
16.20 + 2.56
NIFTY
70.67 1.25
75.65 + 0.63
13.13 + 1.54
GEAR
72.67
2.05
76.46
0.63
7.60
2.66
GraphCFF
72.00 + 1.41
79.21 + 1.21
5.33 + 1.35
E More Experimental Results
E.1 More Evaluation Metrics
In this section, we provide experimental results with more evaluation metrics. Beyond merely assessing accuracy, we incorporate the F1 score and ROC AUC as additional performance evaluation metrics, offering a more comprchensive evaluation of model performance. To provide a comprchensive evaluation of fairness, we also include two metrics that are commonly used in statistical fairness, namely demographic parity (DP) and equal opportunity (EO). DP quantifies the disparity in positive prediction rates between two distinct groups and is mathematically expressed as Apr JP(Ý 1|S 0) - P(Ý 1|S 1)]- On the other hand, EO focuses on fairness concerning true positive rates and is defined as Ago = 1 0,Y = 1) P = 1|S 1, = 1)]. It's worth noting that group fairness is different from counterfact ual fairness. While group fairness metrics, such as DP and EO, provide valuable insights into potential group-level biases, they don't directly measure counterfactual fairness.
We conduct experiments on all six datasets using performance metrics ROC AUC and F1 score, well fairness metrics DP and EO. Results in Table 4 show that our proposed GraphCFF has comparable performance compared to 'No augmentation" in terms of both ROC AUC and F1 score in the majority of scenarios. Furthermore, even though DP and EO don't. directly measure counterfactual fairness, our GraphCFF generally demonstrates a reduction in prediction bias in terms of DP and EO. Overall, our GraphCFF can significantly improve fairness while not sacrificing much performance of the model. It is worth noting that in some cases, our approach not only enhances fairness but also improves performance. For example, in the Synthetic NonLinear dataset, our GraphCFF outperforms the 'No augmentation' with higher Fl score and lower DP and EO.
E.2 More Experiments on Synthetic Datasets
To verify our discussion Appendix C.3 we conduct additional experiments to demonstrate the effectiveness of our method in the specific scenario that node features cannot be influenced by their neighbors. As we mentioned in Appendix C.3 the independence between node features can be achieved by setting Fx, to zero functions. Specifically, we generate a new synthetic datasct, namely Synthetic 0-hop. The generation process of Synthetic 0-hop is the same as Synthelic Linear, except that. Fx, is a zero function rather than a full-rank linear transformation in this case. The results in Table show that our GraphCFF outperforms all baselines in terms of counterfactual fairness and ROC AUC. This means that scenarios, where node features remain uninfluenced by their neighbors, are specific cases within our broader setting. Consequently, our proposed GraphCFF proves to be adept at handling these special cases.
24


Reviews:
[{"review_id": "EAie0PpYlI", "reviewer": "Reviewer_fbSk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This papers tackle the counterfactual fairness issue.\n\n2. The experimental results suggest the method graphCFF can improve counterfactual fairness without sacrificing much accuracy.\n\nWeakness:\n\n1. The introduction can be improved. Readers may not clearly understand counterfactual fairness in the Introduction. Some examples and graph illustrations might be helpful. What is the motivation, and what/why are the challenges important enough for us to use graphCFF to solve them?\n\n2. It is not very clear to me what the challenge this paper aims to solve is and why the proposed method can solve the challenge. In the Introduction, the authors argue that they aim to solve counterfactual fairness. In the Abstract, the authors argue that they aim to solve complex causal graphs with hidden confounders. In Section 3, the authors argue that they aim to solve the counterfactual fairness of classifiers.\n\nQuestions:\n\n1. You mentioned \"more realistic\" in the third paragraph of the Introduction. What does it mean?\n\n2. Theorem 1 is the only theorem in this paper, and it seems it is very important. It would be good to differ this theoretical contribution from the previous papers, e.g., papers using VAE to infer hidden confounders - how your theoretical results differ from them? These papers also provide theoretical results demonstrating that hidden confounders can be recovered from observed distributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a graphCFF method to address counterfactual fairness with hidden confounders. The authors use identifiable graph VAE model to infer hidden confounders and recover counterfactual distributions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the biggest problem is that, the revised papers need to clearly state the motivations and contributions, though the method and experimental results are interesting. Therefore, I think the authors can make a major revision to improve this current version.", "broader_impact_concerns": "Not required.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JlCwXCzQKm", "reviewer": "Reviewer_4e8x", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors considered the latent confounding between the structure and node features which was not addressed in the literature. Therefore, the setup is more general than previous work.\n- By utilizing the identifiability result (Kivva et al., 2022) in deep generative models, the authors argued that the latent confounders can be identified up to permutation, scaling, and/or translation.\n- The experimental results on synthetic/real data showed an improvement in fairness in comparison with previous work.\n\nWeaknesses:\n\n- It is not elaborated on why ensuring identifiability of latent confounding is necessary in generating counterfactual data. The discussion on the identifiability results in (Kivva et al., 2022) is also required. Moreover, there might be some inconsistency between the identifiability results in (Kivva et al., 2022) and Theorem 1.\n- It seems that the approach is limited to binary attributes given the equation in 3.4.\n- In the experiment Section, for real data, the explanation about generating the ground counterfactual is very short (only one sentence in the appendix).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors considered the problem of generating augmented graph data to improve fairness in downstream tasks. In particular, they considered latent confounding which affects both the structure among the nodes and also their features. They utilized a VAE model with a Gaussian mixture prior and argued that the latent confounders are identifiable up to permutation, scaling, and/or translation. Experimental results showed an improvement in fairness using the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In (Kivva et al., 2022), in order to identify the latent sources up to permutation, scaling, and/or translation, additional assumptions on the distribution of the sources are needed (see Assumption P2 and P3). It is good to mention why such assumptions are not required here.\n- It is good to elaborate more on why it is good to have a guarantee on the identifiability of latent confounders. Please note that in Pearl’s counterfactual definition, it is not required to identify the latent variables to compute the counterfactual quantities.\n- Please provide more detail on how the ground counterfactuals for the real datasets are generated. \n- Can be the current approach extended to non-binary attributes?", "broader_impact_concerns": "Nothing specific to be mentioned.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "C1cl2n8M1z", "reviewer": "Reviewer_aLAh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is clearly written and motivated\n2. The work explores the fairness/accuracy tradeoff fig. 2, which I've never seen before but was very interesting, and graphCCF is significantly better.\n3. The choice of VAE is well motivated and interesting\n\nWeaknesses:\n1. It's hard for me to understand why a GMM is an reasonable choice for their priors, when a GMM is not identifiable. If it doesn't matter, what guarantees does theorem 1 provide? If it does matter, how does the use of a GMM influence the results? Or am I missing something?\n2. The setup of the experiments in table 2 is unclear -- how is graphCCF without a GMM structured? Would another, more identifiable, model work well?\n3. What is the computational runtime of this model? It seems heavy. It might be worth adding in a table that describes this.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work explores the topic of counter-factual fairness in graph neural networks. They do this by constructing a counterfactually fair GNN termed graphCFF, which is a VAE based framework for estimating latent distributions in the presence of unobserved confounders. They present experiments to justify the performance of their model, and find that graphCCF performs better than similar baselines, owing to the importance of capturing hidden confounders.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Changes to address my weaknesses would be great", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers more general graphs that contain hidden confounders in the graph for achieving counterfactual fairness. Theoretical results on identifiability of the joint distribution from observational data is established. Also, a computational method based on identifiable VAE is developed to learn the model from data. The paper makes a solid contribution towards making counterfactual fairness operable in real-world scenarios.
Decision: Accept (poster)