Towards Fair Graph Neural Networks via Graph Counterfactual
Graph neural networks have shown great ability in representation (GNNs)
learning on graphs, facilitating various tasks. Despite their great performance
in modeling graphs, recent works show that GNNs tend to inherit and amplify the
bias from training data, causing concerns of the adoption of GNNs in high-stake
scenarios. Hence, many efforts have been taken for fairness-aware GNNs.
However, most existing fair GNNs learn fair node representations by adopting
statistical fairness notions, which may fail to alleviate bias in the presence
of statistical anomalies. Motivated by causal theory, there are several
attempts utilizing graph counterfactual fairness to mitigate root causes of
unfairness. However, these methods suffer from non-realistic counterfactuals
obtained by perturbation or generation. In this paper, we take a causal view on
fair graph learning problem. Guided by the casual analysis, we propose a novel
framework CAF, which can select counterfactuals from training data to avoid
non-realistic counterfactuals and adopt selected counterfactuals to learn fair
node representations for node classification task. Extensive experiments on
synthetic and real-world datasets show the effectiveness of CAF. Our code is
available at https://github.com/TimeLovercc/CAF-GNN.
Zhimeng Guo, Jialiang Li, Teng Xiao, Yao Ma, Suhang Wang
# Towards Fair Graph Neural Networks via Graph Counterfactual

###### Abstract.

Graph neural networks have shown great ability in representation (GNNs) learning on graphs, facilitating various tasks. Despite their great performance in modeling graphs, recent works show that GNNs tend to inherit and amplify the bias from training data, causing concerns of the adoption of GNNs in high-stake scenarios. Hence, many efforts have been taken for fairness-aware GNNs. However, most existing fair GNNs learn fair node representations by adopting statistical fairness notions, which may fail to alleviate bias in the presence of statistical anomalies. Motivated by causal theory, there are several attempts utilizing graph counterfactual fairness to mitigate root causes of unfairness. However, these methods suffer from non-realistic counterfactuals obtained by perturbation or generation. In this paper, we take a causal view on fair graph learning problem. Guided by the casual analysis, we propose a novel framework CAF, which can select counterfactuals from training data to avoid non-realistic counterfactuals and adopt selected counterfactuals to learn fair node representations for node classification task. Extensive experiments on synthetic and real-world datasets show the effectiveness of CAF. Our code is available at [https://github.com/TimeLoverce/CAF-GNN](https://github.com/TimeLoverce/CAF-GNN).

Graph neural networks; Counterfactual fairness; Causal learning +
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
Footnote †: ccs: Computing methodologies Machine learning.

+
+
Footnote †: ccs: Computing methodologies Machine learning.
attributes or generate counterfactuals with GraphVAE, which can easily result in non-realistic counterfactuals. Such non-realistic counterfactuals may disrupt the underlying latent semantic structure, thereby potentially undermining the model's performance. This is because simply flipping sensitive attributes cannot model the influence on other features or graph structure causally caused by sensitive attributes (Beng et al., 2015), and the generative approach lacks supervision of real counterfactuals and could be over-complicated (Zhu et al., 2017).

Motivated by the discussion above, in this paper, we investigate whether one can obtain counterfactuals within the training data. For example, if a female applicant was rejected by a college, we aim to find another male applicant who has a similar background as the counterfactual applicant. Thus, we can get realistic counterfactuals and avoid the ill-supervised generation process. To achieve our goal, we are faced with several challenges: (i) Graph data is quite complex, thus it is infeasible to directly find counterfactuals in the original data space. Besides, some guidance or rules are needed to find the counterfactuals. (ii) To achieve graph counterfactual fairness, learned representation should be invariant to sensitive attributes and information causally influenced by sensitive attributes. It is critical to design proper supervision to help models get rid of sensitive information. To tackle the aforementioned challenges, we propose a casual view of the graph, label and sensitive attribute. The causal interpretation guides us to find counterfactuals and learn disentangled representations, where the disentangled content representations are informative to the labels and invariant to the sensitive attributes. Guided by the causal analysis, we propose a novel framework, Counterfactual **A**ugmented Fair GNN (CAF), to simultaneously learn fair node representations for graph counterfactual fairness and keep the performance on node classification tasks. Specifically, based on the causal interpretation, we derive several constraints to enforce the learned representations being invariant across different sensitive attributes. To obtain proper counterfactuals to guide representation learning, we utilize labels and sensitive attributes as guidance to filter out potential counterfactuals in representation space. Our main contributions are:

* We provide a causal formulation of the fair graph learning process and fair node representation learning task.
* We propose a novel framework CAF to learn node representations for graph counterfactual fairness. Specifically, we find counterfactuals in representation space and design novel constraints to learn the content representations.
* We conduct extensive experiments on real-world datasets and synthetic dataset to show the effectiveness of our model.

## 2. Related Works

**Graph Neural Networks.** Graph neural networks (GNNs) have dominated various tasks on graph-structured data, such as node classification (Beng et al., 2015; Liu et al., 2016; Wang et al., 2017; Wang et al., 2018; Wang et al., 2018), graph classification (Wang et al., 2018) and link prediction (Wang et al., 2018; Wang et al., 2018). Existing GNNs can be categorized into spatial-based GNNs and spectral-based GNNs. Spatial-based GNNs leverage the graph structure directly, focusing on the relationships between nodes and their immediate neighbors to inform feature learning. On the other hand, spectral-based GNNs operate in the spectral domain defined by the graph Laplacian and its eigenvectors, making them better suited to capture global properties of the graph. The superior performance of GNNs has greatly extended their application scenarios (Liu et al., 2016). For example, banks may leverage GNNs to process transaction networks to detect the abnormal behavior of users (Beng et al., 2015). The applications in critical decision-making systems place higher requirements for GNNs, such as being fair and interpretable (Wang et al., 2018). Despite their extensive utility and efficacy, recent studies (Beng et al., 2015; Liu et al., 2016; Wang et al., 2018) show that GNNs can harbor implicit biases on different groups, which can lead to skewed or unfair outcomes. This bias issue is particularly critical when GNNs are deployed in high-stake scenarios, making it necessary to ensure fairness in the modeling process (Zhu et al., 2017). Thus, mitigating bias and promoting fairness in GNNs are active and necessary research areas (Beng et al., 2015). The source of bias in Graph Neural Networks (GNNs) primarily originates from two areas. First, it comes from the inherent bias in the input data, which may contain unequal representation or prejudiced information about nodes or connections in the graph. Second, the bias can stem from the algorithmic design of the GNN itself, which may unintentionally emphasize certain features or connections over others during the learning process. Therefore, there is a trend for the research community to design fairer GNN models to deal with graph-based tasks (Beng et al., 2015; Liu et al., 2016; Wang et al., 2018; Wang et al., 2018).

**Fairness in GNNs.** Fairness is a widely-existed issue of machine learning systems (Zhu et al., 2017; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). Researchers evaluate the fairness of models with many kinds of fairness notions, including group fairness (Liu et al., 2016; Wang et al., 2018), individual fairness (Wang et al., 2018) and counterfactual fairness (Wang et al., 2018). The metrics can also be used to measure the fairness performance of Graph Neural Networks (Beng et al., 2015; Liu et al., 2016). The commonly used fairness notions in GNNs are statistical parity (Wang et al., 2018) and equal opportunity (Liu et al., 2016). FairGNN (Beng et al., 2015) utilizes adversarial training to establish fairness in graph-based models, refining its representation through an adversary tasked with predicting sensitive attributes. EDITS (Beng et al., 2015), on the other hand, is a pre-processing technique that focuses on ensuring fairness in graph learning. It aims to eliminate sensitive information from the graph data by correcting any inherent biases present within the input network. However, these methods and their metrics are developed based on correlation (Zhu et al., 2017), which has been found to be unable to deal with statistical anomalies, such as Simpson's paradox (Simpson, 1966). Based on the causal theory, counterfactual fairness can model the causal relationships and gets rid of the correlation-induced abnormal behavior (Wang et al., 2018; Wang et al., 2018). There is an increasing interest to apply counterfactual fairness on graphs to design fairer GNNs (Beng et al., 2015; Liu et al., 2016). NIFTY (Beng et al., 2015) perturbs sensitive attributes for each node to obtain counterfactuals and omits the causal relationships among variables. GEAR (Zhu et al., 2017) uses GraphVAE (Nissim et al., 2018) to generate the graph structure and node features causally caused by the sensitive attributes. For more details about counterfactual learning on graphs, please refer to the survey (Beng et al., 2015).

Our paper is inherently different from existing work: (i) Unlike existing works that might generate unrealistic counterfactuals, our work avoids the generation process and selects counterfactuals with sensitive attributes and labels as guidance; and (ii) We propose a causal view to understand the source of bias. Based on the causal interpretation, we also design several constraints to help our model learn the fair node representations.
## 3. Preliminaries

In this section, we start by introducing the necessary notation and defining the problem at hand. Following this, we employ the Structural Causal Model to frame the issue, which will then motivate our solution - the disentangled fair representation learning method.

### Notations and Problem Definition

Throughout the paper, we use italicized uppercase letters to represent random variables (e.g., \(S,E\)) and use italicized lowercase letters to denote the specific value of scalars (e.g., \(s\), \(y_{i}\)). Non-italicized bold lowercase and uppercase letters are used to denote specific values of vectors (e.g., \(\mathbf{x}_{i}\)) and matrices (e.g., X), respectively.

Let \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})\) denote an attributed graph, where \(\mathcal{V}=\{v_{1},...,v_{N}\}\) is the set of \(N\) nodes, \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) is the set of edges, \(\mathbf{X}\in\mathbb{R}^{N\times D}\) is the node attribute matrix. The \(i\)-th row of \(\mathbf{X}\), i.e., \(\mathbf{x}_{i}\) is the feature vector of node \(v_{i}\). \(\mathbf{A}\in\{0,1\}^{N\times N}\) is the adjacency matrix of the graph \(\mathcal{G}\), where \(\mathbf{A}_{ij}=1\) if nodes \(v_{i}\) and \(v_{j}\) are connected; otherwise \(\mathbf{A}_{ij}=0\). We use \(\mathbf{s}\in\{0,1\}^{N\times 1}\) to denote the sensitive attributes, where \(s_{i}\) is the sensitive attribute of \(v_{i}\). Following (Kang et al., 2017), we only consider binary sensitive attributes and leave the extension of multi-category sensitive attributes as future work. We use \(\mathbf{y}\in\{1,...,c\}^{N\times 1}\) to denote the ground-truth node labels, where \(y_{i}\) is the label of \(v_{i}\). In this paper, we assume that both target labels and sensitive attributes are binary variables for convenience.

For the semi-supervised node classification task, only part of nodes \(\mathcal{V}_{L}\in\mathcal{V}\) are labeled for training and the remaining nodes \(\mathcal{V}_{U}=\mathcal{V}\backslash\mathcal{V}_{L}\) are unlabeled. The goal is to train a classifier \(f\) to predict the labels of unlabeled nodes, which has satisfied node classification performance and fairness performance simultaneously. Given \(\mathbf{X},\mathbf{A}\) and \(\mathbf{Y}_{L}\), the goal of semi-supervised node classification is to learn a mapping function \(f\) to predict the labels of unlabeled nodes, i.e., \(f:(\mathbf{A},\mathbf{X})\rightarrow\mathcal{Y}_{U}\), where \(\mathcal{Y}_{U}\) the set of predicted labels of unlabeled nodes \(\mathcal{V}_{U}\).

### The Desiderata for Fair Graph Learning

GNNs have shown remarkable capabilities in the realm of semi-supervised node classification. However, they are not immune to bias issues, primarily stemming from imbalanced or prejudiced input data, and potentially from the structural design of the GNNs themselves, which may inadvertently prioritize certain features or connections. Therefore, substantial efforts have been directed towards developing fairness-aware methodologies within GNNs. The majority of these methods strive to ensure correlation-based fairness notions, such as demographic parity or equality of opportunity. However, these correlation-based fairness notions can be inherently flawed, particularly in the presence of statistical anomalies, which calls for more nuanced and robust approaches to achieve fairness in GNNs. Recent advance (Kang et al., 2017) shows that causal-based fairness notions can help resolve this issue. Thus, to help design a fair GNN classifier, we take a deep causal look under the observed graph. Without loss of generality, in this work, we focus on the node classification task and construct a Structural Causal Model (Zhu et al., 2018) in Figure 1. It presents the causal relationships among five variables: sensitive attribute \(S\), ground-truth label \(Y\), environment feature \(E\), content feature \(C\) and ego-graph \(G\) for each node. Each link denotes a deterministic causal relationship between two variables. We list the following explanations for the SCM:

* \(S\to E\). The variable \(E\) denotes latent environment features that are determined by the sensitive attribute \(S\). For example, people of different genders will have different heights or other physical characteristics, where \(S\) is the sensitive attribute of genders and \(E\) is physical characteristics that are causally determined by the sensitive attribute. This relationship will lead to bias in latent feature space, which we will explain shortly.
* \(C\to Y\). The variable \(C\) denotes the content feature that determines ground-truth label \(Y\). Taking the credit scoring as an example, ideally, we assign credit scores using personal information not related to the sensitive attribute, i.e., we use content feature \(C\) instead of \(E\) to assign credit score \(Y\).
* \(E\to G\gets C\). The ego-graph \(G\) is determined by the content feature \(C\) and the environment feature \(E\), which are two disjoint parts. \(E\) and \(C\) are latent features and \(G\) is the observed ego-graph. Considering a one-hop ego-graph, it contains the social connections of center node and the observed feature of center node. The causal relationship indicates environment feature \(E\) and content feature \(C\) can determine one's social connections and personal features (node attributes).

The SCM paves us a way to understand the source of bias and how to design a fair GNN classifier. Next, we give details about source of bias and disentangled learning. Our objective is to approximate the content feature \(C\) with a content representation denoted as \(\hat{C}\), and similarly, approximate the environment feature \(E\) with an environment representation denoted as \(\hat{E}\). To streamline our discussion, we will slightly abuse notation by also employing the symbols \(C\) and \(E\) to signify the corresponding content and environment representations throughout the remainder of the paper.

#### 3.2.1. Source of Bias

From the causal graph, we can observe that the sensitive variable \(S\) and the label variable \(Y\) are independent with each other, i.e., the only path from \(S\) to \(Y\), \(S\to E\to G\gets C\gets Y\) is blocked by the collider \(G\). However, it is worthy noting that \(S\) and \(Y\) are **dependent conditioned on \(G\)**, i.e.,

\[P(Y,S|G)\neq P(Y|G)P(S|G). \tag{1}\]

The conditional dependency of \(Y\) and \(S\) on \(G\) is one major reason that leads to biased prediction. If we directly learn a GNN model that aims to predict \(Y\) based on \(G\), as \(Y\) and \(S\) are dependent given \(G\), the learned label \(Y\) will have correlation with \(S\), resulting in the biased prediction on sensitive attribute \(S\).

Alternatively, we can understand the bias by treating existing GNNs as composed of a feature extractor \(g\) and a classifier \(c\). The feature extractor \(g\) takes the subgraph centered at a node as input and learns node representation as \(\mathbf{z}=g(G)\). Then the classifier

Figure 1. Structural Causal Model for model prediction. We use white color to denote latent variables and use gray color to denote the observed variables.
\(c\) uses the representation \(\mathbf{z}\) to predict the label as \(\hat{y}=c(\mathbf{z})\). As \(G\) is dependent on \(E\) and \(C\), the learned representation \(\mathbf{z}\) is likely to contain mixed information of both \(E\) and \(C\). Hence, the predicted label \(\hat{y}\) is also likely to have correlation with \(S\).

#### 3.2.2. Disentangled Fair Representation Learning

From the above analysis motivates, we can observe that in order to have fair prediction, we need to learn disentangled representation \(E\) and \(C\) to block the path from \(S\) to \(Y\) conditioned on \(G\), and only use the content information \(C\) to predict \(Y\), i.e., \(P(Y|C)\). As \(C\) determines \(Y\), it contains all the label information to predict \(Y\). Meanwhile, observing \(E\) and \(C\) can block the conditional path from \(S\) to \(Y\), i.e., \(P(Y,S|E,C,G)=P(Y|C,E,G)P(S|C,E,G)\). Note that observing \(C\) blocks the path from \(E\) to \(Y\) and the path from \(G\) to \(Y\). Hence, we have \(P(Y|C,E,G)=P(Y|C)\). Observing \(E\) blocks the path from \(S\) to \(G\) and the path from \(S\) to \(C\), thus, we have \(P(S|C,E,G)=P(S|E)\). This gives us

\[P(Y,S|E,C,G)=P(Y|C)P(S|E). \tag{2}\]

The above equation shows that observing \(E\) and \(C\) would make \(Y\) and \(S\) independent and \(P(Y|C)\) is unbiased.

Hence, if we can learn disentangled latent representation \(E\) and \(C\), we would be able to use \(C\) for fair classification. However, the main challenge is we do not have ground-truth \(E\) and \(C\) to help us train a model that can learn disentangled representation. With a slight abuse of notation, we also use \(C\) to denote the learned content representation and use \(E\) to denote the learned environment representation. Fortunately, we can use the SCM to derive several properties of the optimal representation, which would be used to help learn the latent representation of \(C\) and \(E\):

* _Invariance:_\(C\perp\!\!\!\perp E\). This property can be understood in two perspectives. That is, the content representations should be independent to the sensitive attributes and the environment representation induced by the sensitive attribute. Meanwhile, the environment representations should be independent to the labels and the content representation which is informative to the labels.
* _Sufficiency:_\((C,E)\to G\). The combined representation can used to reconstruct the observed graph.
* _Informativeness:_\(C\to Y\). The content representations should have the capacity to give accurate predictions of labels \(Y\).

## 4. Methodology

The causal view suggests us to learn disentangled representation \(\mathbf{c}\) and \(\mathbf{e}\) for node \(v\), with \(\mathbf{c}\) capturing the content information that is useful for label prediction and irrelevant to sensitive attributes, and \(\mathbf{e}\) capturing the environment information depends on sensitive attribute only. With the disentanglement, \(\mathbf{c}\) can be used to give fair predictions. However, how to effectively disentangle \(\mathbf{c}\) and \(\mathbf{e}\) remains a question given that we do not have ground-truth of disentangled representation. Intuitively, for a node \(v\) with sensitive attribute \(s\), its content representation \(\mathbf{c}\) should remain the same when the sensitive attribute is flipped to \(1-s\) while its environment representation \(\mathbf{e}\) should change correspondingly. Hence, if we know the counterfactual of node \(v\), we will be able to utilize the counterfactual to help learn disentangled representation for fair classification; while the counterfactual is not observed. To address the challenges, we propose a novel framework CAF as shown in Figure 2 (a), which is composed of: (i) a GNN encoder that takes ego-graph \(\mathcal{G}\) of node \(v\) to learn disentangled representation \(\mathbf{c}\) and \(\mathbf{e}\); (ii) the counterfactual augmentation module, which aims to discover counterfactual for each factual observation and utilize the counterfactual to help learn disentangled representation; (iii) a fair classifier which takes \(\mathbf{c}\) as input for fair classification. Next, we give the details of each component.

### Disentangled Representation Learning

For each node \(v_{i}\), the content representation \(\mathbf{c}_{i}\) should capture the important node attribute and neighborhood information for predicting the label while the environment representation \(\mathbf{e}_{i}\) should capture all important information relevant to sensitive attribute. As GNNs have shown great ability in modeling graph structured data, we adopt GNNs to learn \(\mathbf{c}_{i}\) and \(\mathbf{e}_{i}\). Instead of adopting two GNNs to learn \(\mathbf{c}_{i}\) and \(\mathbf{e}_{i}\) separately, to reduce the number of parameters, we adopt one GNN to learn \(\mathbf{c}_{i}\) and \(\mathbf{e}_{i}\). We empirically found that using two GNNs and one GNN have similar performance due to constraints we designed to disentangle \(\mathbf{c}_{i}\) and \(\mathbf{e}_{i}\), which will be introduced later. Specifically, the GNN \(f_{\theta}\) parameterized by \(\theta\) takes \(\mathcal{G}\) as input and learns representation as:

\[[\mathbf{C},\mathbf{E}]=\mathbf{H}=f_{\theta}(\mathbf{A},\mathbf{X}), \tag{3}\]

where \(\mathbf{H}\in\mathbb{R}^{N\times d}\) is the learned representation matrix with the \(i\)-th row, i.e., \(\mathbf{h}_{i}\), as the representation of node \(v_{i}\). We treat the first \(d_{\mathbf{c}}\) columns as the content representation matrix \(\mathbf{C}\) and use the next \(d_{\mathbf{c}}\) columns as the environment representation matrix \(\mathbf{E}\). Note that \(d=d_{\mathbf{c}}+d_{\mathbf{e}}\). In our implementation, we set \(d_{\mathbf{c}}=d_{\mathbf{c}}\). \(\mathbf{C}\in\mathbb{R}^{N\times d_{\mathbf{c}}}\) is the content representation matrix with the \(i\)-th row, i.e., \(\mathbf{c}_{i}\), as the content representation of node \(v_{i}\). Similarly, \(\mathbf{E}\in\mathbb{R}^{N\times d_{\mathbf{c}}}\) is the environment representation matrix with the \(i\)-th row, i.e., \(\mathbf{c}_{i}\) as the environment representation matrix with the \(i\)-th row, i.e., \(\mathbf{c}_{i}\) as the environment representation of node \(v_{i}\). \(f_{\theta}\) is flexible to be various GNNs such as GCN (Gori et al., 2017) and GraphSAGE (Gori et al., 2017).

To make sure \(\mathbf{c}_{i}\) captures the content information for fair label prediction, and \(\mathbf{e}_{i}\) and \(\mathbf{c}_{i}\) are disentangled, based on the causal analysis in Section 3, we add following constraints:

**Informativeness Constraint.** First, the content representation \(\mathbf{c}_{i}\) should be informative to the downstream tasks, i.e., \(C\to Y\). Hence, for node \(v_{i}\), we should be able to get accurate label prediction from \(\mathbf{c}_{i}\). Thus, we introduce a classifier \(f_{\phi}\) with model parameter \(\phi\). It takes \(\mathbf{c}_{i}\) as input and predicts the class distribution of \(v_{i}\) as:

\[\hat{\mathbf{y}}_{i}=f_{\phi}(\mathbf{c}_{i}). \tag{4}\]

The loss function for training the classifier is given as:

\[\mathcal{L}_{\text{pred}}=\frac{1}{|\mathcal{V}_{L}|}\sum_{v_{i}\in\mathcal{V}_ {L}}\ell(\hat{\mathbf{y}}_{i},\mathbf{y}_{i}), \tag{5}\]

where \(\mathbf{y}_{i}\) is the one-hot encoding of ground-truth label of \(v_{i}\). \(\ell(\hat{\mathbf{y}}_{i},\mathbf{y}_{i})\) denotes the cross entropy between \(\hat{\mathbf{y}}_{i}\) and \(\mathbf{y}_{i}\).

**Sufficiency Constraint.** As shown in our causal view, the representation (\(\mathbf{c}_{i}\) and \(\mathbf{e}_{i}\)) should be sufficient to reconstruct the observed factual graph \(\mathcal{G}_{i}\). In disentangled representation learning research, the reconstruction supervision is usually adopted to guide the learning process (Gori et al., 2017; Zhang et al., 2018). However, existing graph counterfactual fairness approaches (Gori et al., 2017; Zhang et al., 2018) fail to provide supervision to preserve graph information in the representations. Thus, they put their models at a risk of being stuck in trivial solutions to merely get spurious
information in the representations, which contradicts the SCM and is not sufficient to reconstruct the observed graph \(\mathbf{\mathcal{G}}_{i}\). In our model, we formalize the sufficiency constraint as a reconstruction of the graph structure. Specifically, for a pair of nodes \((v_{i},v_{j})\), we predict the link existence probability as \(p_{ij}=\sigma(\mathbf{h}_{i}\mathbf{h}_{j}^{T})\), where \(\mathbf{h}_{i}=[\mathbf{c}_{i},\mathbf{c}_{i}]\) is the node representation of node \(v_{i}\). The sufficiency constraint is

\[\mathcal{L}_{\text{suf}}=\frac{1}{|\mathcal{E}|+|\mathcal{E}^{-}|}\sum_{(v_{i },v_{j})\in\mathcal{E}\cup\mathcal{E}^{-}}-e_{ij}\log p_{ij}-(1-e_{ij})\log p_{ ij}, \tag{6}\]

where \(\mathcal{E}^{-}\) is the set of sampled negative edges. \(e_{ij}=1\) if node \(v_{i}\) and \(v_{j}\) are connected; otherwise \(e_{ij}=0\).

**Orthogonal Constraint.** The above model can help to learn \(\mathbf{c}_{i}\) that captures graph information for label prediction, however, it doesn't guarantee that \(\mathbf{c}_{i}\) doesn't contain sensitive attribute information. To make sure that \(\mathbf{c}_{i}\) and \(\mathbf{c}_{i}\) are disentangled, i.e., \(\mathbf{c}_{i}\) doesn't contain any environment information relevant to sensitive attribute, we further impose the orthogonal constraint, i.e., \(\mathbf{c}_{i}^{T}\mathbf{e}_{i}=0\).

### Counterfactual Augmented Learning

As we do not have ground-truth of \(\mathbf{c}_{i}\) and \(\mathbf{c}_{i}\), we used several constraints to implicitly superoise the learning of \(\mathbf{c}_{i}\) and \(\mathbf{c}_{i}\). To fully learn disentangled \(\mathbf{c}_{i}\) and \(\mathbf{c}_{i}\), we propose to learn better \(\mathbf{c}_{i}\) and \(\mathbf{c}_{i}\) that follows the counterfactual constraints. As shown in Figure 2 (b), generally, for a node \(v_{i}\) with observe the factual sensitive attribute \(s_{i}\) and label \(y_{i}\), its content representation \(\mathbf{c}_{i}\) should remain similar when the sensitive attribute is flipped to \(1-s_{i}\) but its environment representation \(\mathbf{c}_{i}\) should change correspondingly, which forms the counterfactual subgraph \(\mathbf{\mathcal{G}}_{i}^{e}\). Similarly, when flip label \(y_{i}\) but keep the sensitive attribute \(s_{i}\) unchanged, then \(v_{i}\)'s environment representation \(\mathbf{c}_{i}\) remain the same, while its content representation should change accordingly, leading to the counterfactual subgraph \(\mathbf{\mathcal{G}}_{i}^{c}\). Thus, if we know \(\mathbf{\mathcal{G}}_{i}^{e}\) and \(\mathbf{\mathcal{G}}_{i}^{c}\), we would be able to use these counterfactual graphs together with factual graph \(\mathbf{\mathcal{G}}_{i}\) to guide the learning of \(\mathbf{c}_{i}\) and \(\mathbf{c}_{i}\). However, in real-world, we can only observe factual graphs. To solve this challenge, we propose to find potential candidate counterfactuals with the observed factual graphs.

The sensitive attribute and label are used to find counterfactuals in our model. Considering the fair credit scoring problem, when someone was assigned a low score, straightforward thinking is to know the results of people who have a similar background to her but of a different gender. For example, Sarah, a female, got a low credit score. Then she may ask, what if I were a male, what will my credit score be? This thinking inspires us to directly find counterfactuals from the observed node samples instead of performing perturbation or generating (Beng et al., 2017; Chen et al., 2018). The advantages of selecting counterfactuals from the observed node samples are twofold: (1) It avoids making assumptions about the graph generation process with sensitive attributes. (2) It does not need additional supervision signal.

Another problem comes: selecting counterfactuals from the original data space is also challenging due to the complexity of graph distance calculation. To get counterfactual \(\mathbf{\mathcal{G}}_{i}^{e}\), we need to find some nodes which have different sensitive attribute and the same label. Similarly, we find some nodes with the same sensitive attribute and different labels as counterfactual \(\mathbf{\mathcal{G}}_{i}^{c}\). The task can be formalized as:

\[\mathbf{\mathcal{G}}_{i}^{c} =\operatorname*{arg\,min}_{\mathbf{\mathcal{G}}_{i}\in\mathbb{G}}\{m( \mathbf{\mathcal{G}}_{i},\mathbf{\mathcal{G}}_{j})\mid y_{i}\neq y_{j},s_{i}=s_{j}\}, \tag{8}\] \[\mathbf{\mathcal{G}}_{i}^{e} =\operatorname*{arg\,min}_{\mathbf{\mathcal{G}}_{j}\in\mathbb{G}}\{m( \mathbf{\mathcal{G}}_{i},\mathbf{\mathcal{G}}_{j})\mid y_{i}=y_{j},s_{i}\neq s_{j}\}, \tag{7}\]

where \(\mathbb{G}=\{\mathbf{\mathcal{G}}_{i}|v_{i}\in\mathcal{V}\}\)) and \(m(\cdot,\cdot)\) is a metric of measuring the distance between a pair of subgraphs. Nevertheless, the problem of computing the distance of pairs of graphs is inefficient and infeasible due to the complex graph structure and large search space (Zhu et al., 2019). As we already have node representations \(\mathbf{h}_{i}=[\mathbf{c}_{i},\mathbf{c}_{i}]\) that capture the graph structure and node attribute information, we propose to measure the distance in the latent space, which can greatly reduce the computation burden. Then the counterfactual graph searching problem in Eq. (7) and Eq. (8) is converted to the problem below:

\[\mathbf{h}_{i}^{c} =\operatorname*{arg\,min}_{\mathbf{h}_{j}\in\mathbb{H}}\{\left\| \mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2}^{2}\mid y_{i}\neq y_{j},s_{i}=s_{j}\}, \tag{10}\] \[\mathbf{h}_{i}^{e} =\operatorname*{arg\,min}_{\mathbf{h}_{j}\in\mathbb{H}}\{\left\| \mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2}^{2}\mid y_{i}=y_{j},s_{i}\neq s_{j}\}, \tag{9}\]

where \(\mathbb{H}=\{\mathbf{h}_{i}|v_{i}\in\mathcal{V}\}\) and we use L2 distance to find counterfactuals. A problem is that we only have limited labels in the training set. So we first pre-train the backbone model. With pre-trained model, we can obtain the prediction for unlabeled nodes as pseudo-labels. The pseudo-labels work as the guidance of the

Figure 2. An illustration of (a) our proposed framework; (b) intuition of counterfactual augmented learning.
counterfactual searching problem. Note that for each factual input we can also get multiple counterfactuals by selecting a set of counterfactuals in Eq. (9) and Eq. (10) instead of one. Thus, the counterfactual \(\mathbf{G}^{e}_{i}\) can be naturally extended to a set of \(K\) counterfactuals \(\{\mathbf{g}^{e_{k}}_{i}|k=1,...,K\}\) and \(\mathbf{G}^{e}_{i}\) can be extended to \(\{\mathbf{g}^{e_{k}}_{i}|k=1,...,K\}\). We fix \(K\) to 10 in our implementation.

We can utilize the counterfactuals to supervise the disentanglement of \(\mathbf{e}_{i}\) and \(\mathbf{e}_{i}\). Specifically, as shown in Figure 2 (b), counterfactual \(\mathbf{g}^{e_{k}}_{i}\) shares the same content information with factual graph \(\mathbf{G}_{i}\) and has different environment information. Without supervision, the factual content representation \(\mathbf{c}_{i}\) and the counterfactual content representation \(\mathbf{c}^{e_{k}}_{i}\) may contain both the content information and environment information. When we minimize the discrepancy of the learned representations with \(\text{dis}(\mathbf{c}_{i},\mathbf{c}^{e_{k}}_{i})\), \(f_{\theta}\) will tend to merely keep the content information and squeeze the sensitive information out of learned representations. In a similar manner, we can use \(\text{dis}(\mathbf{e}_{i},\mathbf{c}^{e_{k}}_{i})\) to make the environment representation \(\mathbf{e}_{i}\) be invariant to the content information stored in \(\mathbf{c}_{i}\). Also, we put the orthogonal constraint here to encourage \(\mathbf{c}_{i}\) and \(\mathbf{e}_{i}\) to store different information in representation space. The invariance constraint is given as:

\[\begin{split}\mathcal{L}_{\text{inv}}=\frac{1}{|\mathbf{V}|\cdot K }\sum_{\mathbf{v}_{i}\in\mathcal{V}}\sum_{k=1}^{K}\Big{[}&\ \text{dis}(\mathbf{c}_{i},\mathbf{c}^{e_{k}}_{i})+\text{dis}(\mathbf{c}_{i},\mathbf{c}^{e_{k}} _{i})\\ &+\gamma K\cdot|\cos(\mathbf{c}_{i},\mathbf{c}_{i})|\Big{]},\end{split} \tag{11}\]

where \(\text{dis}(\cdot,\cdot)\) is a distance metric, such as the cosine distance and L2 distance in our implementation. \(|\cos(\cdot,\cdot)|\) is the absolute value of cosine similarity and we optimize this term to approximate \(\mathbf{c}^{T}_{i}\mathbf{e}_{i}=0\). \(\gamma\) is the hyper-parameter to control the orthogonal constraint.

### Final Objective Function of CAF

Putting the disentangled representation learning module and the counterfactual selection module together, the final objective function of the proposed CAF framework is:

\[\min_{\theta,\phi}\mathcal{L}=\mathcal{L}_{\text{pred}}\,+\alpha\mathcal{L}_{ \text{inv}}\,+\beta\mathcal{L}_{\text{suf}}\,, \tag{12}\]

where \(\theta\) and \(\phi\) are parameters for the GNN encoder and the prediction head, respectively. \(\alpha\) and \(\beta\) are hyper-parameters controlling the invariance constraint and the sufficiency constraint.

### Training Algorithm

The whole process of CAF is summarized in Algorithm 1. Our method relies on the counterfactuals in the representation space to guide the disentanglement. However, the randomly initialized representation at the first several epochs may degrade the performance of our model. Therefore, we first pre-train a plain node representation learning model \(\mathbf{Y}=g_{\Theta,\Phi}(\mathbf{A},\mathbf{X})\) only with \(\mathcal{L}_{\text{pred}}\). Then we use the optimized parameters \(\Theta^{*},\Phi^{*}=\min_{\Theta,\Phi}\mathcal{L}_{\text{pred}}\) to initialize the parameters \(\theta\) and \(\phi\) of our model and use the aforementioned framework to get the desired disentangled representations. We do not necessarily update the counterfactuals for each epoch. We update the counterfactuals once for \(t\) epochs and \(t=10\) in our implementation. As shown in Algorithm 1, we first pre-train \(g_{\Theta,\Phi}\) and use the optimized parameter to initialize \(f_{\theta}\) and \(\phi\) from line 1 to line 1. Then we iteratively optimize \(f_{\theta}\) and \(\phi\) from line 1 to line 1. In each iteration, we first perform forward propagation to get node representations in line 1. And then for each \(t\) epoch we update the selected counterfactuals once from line 1 to line 1. Afterwards, we compute the overall objective and perform backpropagation to optimize the parameters \(\theta\) and \(\phi\) from line 1 to line 1. After training, we obtain the desired fair model \(f_{\theta}\) and \(f_{\phi}\) in line 1.

```
1:\(g=(\mathcal{V},\mathcal{E},\mathbf{X})\), \(\mathbf{Y}_{L}\), \(t\), \(\alpha\), \(\beta\), \(\gamma\), \(K\) and num_epoch
2:\(f_{\theta}\) and \(f_{\phi}\)
3: Pre-train \(g_{\Theta,\Phi}\) based on \(\mathcal{L}_{\text{pred}}\) with Eq. (5)
4: Use the optimized \(\Theta^{*}\) and \(\Phi^{*}\) to initialize \(f_{\theta}\) and \(f_{\phi}\)
5:for epoch in range(num_epoch)do
6: Compute representations \(\mathbf{H}\) and predicted labels \(\hat{\mathbf{Y}}\) with \(f_{\theta}\) and \(f_{\phi}\) by Eq. (3) and Eq. (4)
7:if\(num\_epoch\) % \(t=0\)then
8: Obtain two sets of counterfactuals \(\left\{\mathbf{g}^{e_{k}}_{i}\mid k=1,\dots,K\right\}\) and \(\left\{\mathbf{g}^{e_{k}}_{i}\mid k=1,\dots,K\right\}\) with Eq. (9) and (10).
9:endif
10: Compute the overall objective \(\mathcal{L}\) with Eq. (12)
11: Update \(\theta\) and \(\phi\) according to the objective \(\mathcal{L}\)
12:endfor
13:return\(f_{\theta}\) and \(f_{\phi}\)
```

**Algorithm 1**Training Algorithm of CAF.

## 5. Experiments

In this section, we conduct experiments to evaluate the effectiveness of the proposed method and compare it with state-of-the-art fair GNNs. Specifically, we aim to answer the following questions:

* **(RQ 1)** How effective is the proposed CAF for fair node classification task on both synthetic datasets and real-world datasets?
* **(RQ 2)** Can the proposed CAF find appropriate counterfactuals?
* **(RQ 3)** How do the proposed modules work? How can each regularization term affect the model performance?

### Experiment Settings

#### 5.1.1. Real-World Datasets

We conduct experiments on three widely used real-world datasets, namely German Credit (Cheng et al., 2017), Credit Defaulter (Zi et al., 2018), Bai (Zi et al., 2018). The statistics of the datasets can be found in Table 2. The details of the datasets are as follows:

* **German Credit**(Cheng et al., 2017): the nodes in the dataset are clients and two nodes are connected if they have high similarity of the credit accounts. The task is to classify the credit risk level as high or low with the sensitive attribute "gender".
* **Credit Defaulter**(Zi et al., 2018): the nodes in the dataset are used to represent the credit card users and the edges are formed based on the similarity of the payments information. The task is to classify the default payment method with sensitive attribute "age".
* **Bail**(Zi et al., 2018): these datasets contain defendants released on bail during 1990-2009 as nodes. The edges between two nodes are connected based on the similarity of past criminal records and demographics. The task is to classify whether defendants are on bail or not with the sensitive attribute "race".

#### 5.1.2. Synthetic Dataset

Real-world datasets do not offer ground-truth counterfactuals, prompting us to construct a synthetic dataset
based on the Structural Causal Model (SCM) as depicted in Figure 1. The primary advantage of a synthetic dataset is that it provides us with ground-truth counterfactuals for each node, which enables us to assess the quality of the obtained counterfactuals. In our approach, we consider settings with binary sensitive attributes and binary labels. A graph with 2000 nodes is sampled in our implementation. To generate the desired counterfactuals, we maintain the same sampled value of noise variables and use consistent causal relationships for each node. The sensitive attributes and labels are sampled from two different Bernoulli distributions, with \(s_{i}\sim\mathcal{B}(p)\) and \(y_{i}\sim\mathcal{B}(q)\), respectively. This results in generating vectors \(\mathbf{s}_{i}=[(s_{i})_{\times N}]\) and \(\mathbf{y}_{i}=[(y_{i})_{\times N}]\). Next, environment and content features, \(\mathbf{e}_{i}\) and \(\mathbf{e}_{i}\), are sampled from normal distributions \(\mathbf{e}_{i}\sim\mathcal{N}(s_{i},\mathbf{I})\) and \(\mathbf{e}_{i}\sim\mathcal{N}(s_{i},\mathbf{I})\), respectively. These features are combined to form the overall latent feature \(\mathbf{z}_{i}=[\mathbf{e}_{i},\mathbf{e}_{i}]\). The observed feature for each node \(v_{i}\), denoted as \(\mathbf{x}_{i}\), is computed as \(\mathbf{x}_{i}=\mathbf{W}\mathbf{z}_{i}+\mathbf{b}_{i}\), where \(\mathbf{W}_{ij}\sim\mathcal{N}(1,1)\), and \(\mathbf{W}\in\mathbb{R}^{d_{2}\times 2d_{1}}\), with \(\mathbf{b}_{i}\sim\mathcal{N}(0,\mathbf{I})\in\mathbb{R}^{d_{2}}\). The adjacency matrix \(\mathbf{A}\) is defined such that \(\mathbf{A}_{ij}=1\) if \(\sigma(\cos(\mathbf{z}_{i},\mathbf{z}_{j})+\epsilon_{ij})\geq\alpha\) and \(i\neq j\), with \(\epsilon_{ij}\sim\mathcal{N}(0,1)\), and \(\mathbf{A}_{ij}=0\) otherwise. Here, \(\sigma(\cdot)\) denotes the Sigmoid function, and the threshold \(\alpha\) controls the edge number. We have the freedom to set sensitive attribute probability \(p\), label probability \(q\), latent feature dimension \(2d_{1}\), observed feature dimension \(d_{2}\), node number \(N\), and threshold \(\alpha\) to control the biased graph generation process. Note that in the SCM we have \(C\to Y\) instead of \(Y\to C\), thus a better way is to first generate content features and then assign labels to the features. Intuitively, we argue that when using an optimal classifier to deal with content features with different means will assign the same label in our generation process. Therefore, to simplify the generation process, we use \(C\to Y\) in our dataset design.

The synthetic dataset comes with notable advantages. Firstly, it gives us access to exact counterfactuals. After generating the initial graph, we keep all noise variables and unrelated variables unchanged, then adjust the sensitive attribute \(s_{i}\) or label \(y_{i}\) to calculate the precise counterfactual through the same graph generation procedure. Secondly, the synthetic dataset enables adjustable bias levels, providing us control over the extent of bias in our models. As a result, we can undertake a comprehensive and detailed evaluation of our model's fairness and prediction quality.

#### 5.1.3. Baselines

To evaluate the effectiveness of CAF, we include representative and state-of-the-art methods, which can be categorized into three categories: (1) _plain node classification methods_: GCN (Ghezani et al., 2017), GraphSAGE (Ghezani et al., 2017) and GIN (Zhou et al., 2017); (2) _fair node classification methods_: FairGNN (Ghezani et al., 2017), EDITS (Ghezani et al., 2017); (3) _graph counterfactual fairness methods_: NIFTY (Ghezani et al., 2017) and GEAR (Zhou et al., 2017). Unless otherwise specified, we use GraphSAGE as the model backbone except for baseline GCN and GIN. We use SAGE to denote GraphSAGE. The detailed descriptions about the datasets are as follows:

* GCN (Ghezani et al., 2017): GCN is a popular spectral GNN, which adopts a localized first-order approximation of spectral graph convolutions.
* GraphSAGE (Ghezani et al., 2017): GraphSAGE is a method for inductive learning that leverages node feature information to generate unsupervised embeddings for nodes in large graphs, even if they were not included in the initial training.
* GIN (Zhou et al., 2017): Graph Isomorphism Network (GIN) is a graph-based neural network that can capture different topological structures by injecting the node's identity into its aggregation function.
* FairGNN (Ghezani et al., 2017): FairGNN uses adversarial training to achieve fairness on graphs. It trains the learned representation via an adversary which is optimized to predict the sensitive attribute.
* EDITS (Ghezani et al., 2017): EDITS is a pre-processing method for fair graph learning. It aims to delbias the input network to remove the sensitive information in the graph data.
* NIFTY (Ghezani et al., 2017): It simply performs a flipping on the sensitive attributes to get counterfactual data. It regularizes the model to be invariant to both factual and counterfactual data samples.
* GEAR (Zhou et al., 2017): GEAR is a method for counterfactual fairness on graphs. It utilizes a variational auto-encoder to synthesize counterfactual samples to achieve counterfactual fairness for graphs.

#### 5.1.4. Evaluation Metrics

We evaluate the model performance from three perspectives: classification performance, group fairness and

\begin{table}
\begin{tabular}{c|c c c c|c c|c c|c} \hline
**Dataset** & **Metrics** & **GCN** & **GraphSAGE** & **GIN** & **FairGNN** & **EDITS** & **NIFTY** & **GEAR** & **CAF** \\ \hline \multirow{8}{*}{**German**} & AUC (\(\uparrow\)) & 74.00\({}_{\pm 1.51}\) & **74.54\({}_{\pm 0.86}\)** & 72.69\({}_{\pm 1.02}\) & 65.85\({}_{\pm 9.49}\) & 69.76\({}_{\pm 5.46}\) & 72.05\({}_{\pm 2.15}\) & 65.80\({}_{\pm 3.00}\) & 71.87\({}_{\pm 1.33}\) \\  & F1 (\(\uparrow\)) & 80.05\({}_{\pm 1.20}\) & 81.15\({}_{\pm 0.97}\) & **82.62\({}_{\pm 1.55}\)** & 82.29\({}_{\pm 0.32}\) & 81.04\({}_{\pm 1.09}\) & 79.20\({}_{\pm 1.19}\) & 78.04\({}_{\pm 2.07}\) & 82.16\({}_{\pm 0.22}\) \\  & \(\Delta_{SP}\) (\(\downarrow\)) & 41.94\({}_{\pm 5.52}\) & 23.79\({}_{\pm 6.70}\) & 14.85\({}_{\pm 4.64}\) & 7.65\({}_{\pm 8.07}\) & 8.42\({}_{\pm 7.35}\) & 7.74\({}_{\pm 7.80}\) & 8.60\({}_{\pm 3.47}\) & **6.60\({}_{\pm 1.66}\)** \\  & \(\Delta_{EO}\) (\(\downarrow\)) & 31.11\({}_{\pm 4.40}\) & 15.13\({}_{\pm 5.74}\) & 8.26\({}_{\pm 6.72}\) & 4.18\({}_{\pm 8.36}\) & 5.69\({}_{\pm 1.60}\) & 5.17\({}_{\pm 2.38}\) & 6.34\({}_{\pm 2.31}\) & **1.58\({}_{\pm 1.14}\)** \\ \hline \multirow{8}{*}{**Bail**} & AUC (\(\uparrow\)) & 88.50\({}_{\pm 1.30}\) & 90.50\({}_{\pm 2.10}\) & 77.30\({}_{\pm 6.90}\) & 88.20\({}_{\pm 3.50}\) & 89.07\({}_{\pm 2.26}\) & **92.04\({}_{\pm 0.89}\)** & 89.60\({}_{\pm 1.60}\) & 91.39\({}_{\pm 0.34}\) \\  & F1 (\(\uparrow\)) & 78.20\({}_{\pm 2.30}\) & 80.40\({}_{\pm 3.20}\) & 6.50\({}_{\pm 8.04}\) & 78.40\({}_{\pm 2.12}\) & 77.83\({}_{\pm 3.79}\) & 77.81\({}_{\pm 6.06}\) & 80.00\({}_{\pm 3.10}\) & **80.00\({}_{\pm 9.08}\)** \\  & \(\Delta_{SP}\) (\(\downarrow\)) & 7.50\({}_{\pm 1.40}\) & 8.60\({}_{\pm 3.90}\) & 6.50\({}_{\pm 3.40}\) & 7.40\({}_{\pm 2.02}\) & 3.74\({}_{\pm 3.43}\) & 5.74\({}_{\pm 3.50}\) & 5.70\({}_{\pm 3.50}\) & **7.29\({}_{\pm 1.06}\)** \\  & \(\Delta_{EO}\) (\(\downarrow\)) & 2.30\({}_{\pm 1.90}\) & 3.90\({}_{\pm 2.20}\) & 4.10\({}_{\pm 2.30}\) & 4.60\({}_{\pm 1.30}\) & 4.46\({}_{\pm 3.50}\) & 4.07\({}_{\pm 1.28}\) & 1.90\({}_{\pm 2.30}\) & **1.17\({}_{\pm 3.22}\)** \\ \hline \multirow{8}{*}{**Credit**} & AUC (\(\uparrow\)) & 68.40\({}_{\pm 1.90}\) & **75.60\({}_{\pm 1.10}\)** & 70
counterfactual fairness. **(i)** For _classification performance_, we use AUC and the F1 score to measure node classification performance. **(ii)** For _fairness_, following (Bang et al., 2018), we adopt two commonly used group fairness metrics, i.e., statistical parity (SP) \(\Delta_{SP}\) and equal opportunity (EO) \(\Delta_{EO}\), which are computed as \(\Delta_{SP}=|P(\hat{y}_{u}=1\mid s=0)-P(\hat{y}_{u}=1\mid s=1)|\) and \(\Delta_{EO}=|P(\hat{y}_{u}=1\mid y_{u}=1,s=0)-P(\hat{y}_{u}=1\mid y_{u}=1,s=1)|\). The smaller \(\Delta_{SP}\) and \(\Delta_{EO}\) are, the fairer the model is. **(iii)** For _counterfactual fairness_, as we have the ground-truth counterfactuals on the synthetic dataset, Following (Bang et al., 2018), we use the counterfactual fairness metric \(\delta_{CF}\), i.e., \(\delta_{CF}=|P\left((\hat{y}_{i})_{S\leftarrow s}\mid X,\mathbf{A}\right)-P \left((\hat{y}_{i})_{S\leftarrow s^{\prime}}\mid X,\mathbf{A}\right)|\), where \(s,s^{\prime}\in\{0,1\}^{N}\) are the sensitive attributes and \(s^{\prime}=1-s\). \((\hat{y}_{i})_{S\leftarrow s^{\prime}}\) is the computed ground-truth counterfactual label with the same data generation process as shown in Figure 1. We use subscript \(S\gets s^{\prime}\) to denote counterfactual computation (Zhu et al., 2017), i.e., keeping the same data generation process and values of random noise variable. Counterfactual fairness of the graph is only measured on synthetic dataset.

#### 5.1.5. Setup

For German Credit, Credit Defaulter and Bail, we follow train/valid/test split in (Bang et al., 2018). For the constructed synthetic dataset, we use a 50/25/25 split for training/validation/testing data. We randomly initialize the parameters. For each combination of the hyper-parameters configuration, we run the experiments with 10 random seeds and grid search for the best configuration.

### Performance Comparison

To answer RQ1, we conduct experiments on real-world datasets and synthetic dataset with comparison to baselines.

#### 5.2.1. Performance on Real-World Datasets

Table 1 shows the average performance with standard deviation of ten runs on real-world datasets. The best results are highlighted in **bold** and the runner-up results are underlined. From Table 1, we observe:

* CAF can improve the group fairness performance. Across three datasets, Table 1 shows CAF can make fairer predictions than other baseline methods. CAF beats all the baselines with respect to the group fairness metrics.
* There exists a trade-off between group fairness and prediction performance. Plain node classification methods, such as GCN, GraphSAGE and GIN, tend to have better prediction performance and worse group fairness performance. Fair node classification methods, including FairGNN, EDITS, NIFTY, GEAR and CAF, tend to suffer from a prediction performance drop and the group fairness performance is better.
* CAF achieves best performance on the prediction-fairness trade-off. We use the average rank of two prediction metrics and two group fairness metrics to know the performance of the trade-off. Our model ranks 1.75 and the runner-up model ranks 3.83. Our model outperforms the state-of-the-art node representation learning methods, which shows the effectiveness of our model.
* Graph counterfactual fairness methods, such as NIFTY, GEAR and CAF, achieved better performance than other baselines. Correlation-based counterfactual notions can capture the causal relationships and help to boost the group fairness performance.

#### 5.2.2. Performance on Synthetic Dataset

Figure 3 reports the performance on the synthetic dataset. On the synthetic dataset, we have the desired ground-truth counterfactuals, which can be used to measure the performance of graph counterfactual fairness. We compare our model with plain node classification models and counterfactual fairness models. The observations are as follows:

* CAF beats all the models with respect to the prediction, group fairness and counterfactual fairness metrics. We argue that in our assumed biased generation process, our model can effectively find invariant, sufficient and informative representations to make accurate and fair predictions.
* Other graph counterfactual fairness-based methods, including NIFTY and GEAR, cannot consistently outperform other methods. These methods design their model without considering meaningful causal relationships. NIFTY simply perturbs the sensitive attribute and omits the further influence on features and graph structure. GEAR adopts an GraphVAE to model the causal relationships, which may fail to generate meaningful counterfactuals.

### Flexibility of CAF for Various Backbones

To show the flexibility of CAF in improving the fairness of various backbones while maintaining high classification accuracy, other than GraphSAGE, we also plug our model in GCN and GIN. Figure 4 shows the classification performance and fairness performance on Bail and Credit. From Figure 4, we observe that compared with the backbones, CAF can significantly improve the fairness with no or marginal decrease in classification performance. For example, on Bail dataset, the prediction performance with GIN backbone drops by 0.54% on AUROC but the \(\Delta_{SP}\) drops by 1.37% and the \(\Delta_{EO}\) drops by 0.86%, which is an improvement on fairness performance. This demonstrates the flexibility of CAF in benefiting various backbones.

### Quality of Counterfactuals

To answer RQ2, we compare the counterfactuals obtained by CAF with ground-truth counterfactuals to investigate whether we can

Figure 4. Comparison of the prediction performance and fairness performance of different backbones.

Figure 3. Node classification performance and group fairness performance on synthetic datasets.
obtain the desired counterfactuals. We conduct experiments on the synthetic dataset which has ground-truth counterfactuals. We first use CAF to obtain counterfactuals. To measure the discrepancy of the obtained counterfactuals with respect to the feature and structure in the ego graph, we compare the learned counterfactual representations and the ground-truth counterfactual representations. We compare our model with two graph counterfactual fairness baselines, i.e., NIFTY (Bengio et al., 2017) and GEAR (Zhu et al., 2017). NIFTY simply flips the sensitive attributes to get their counterfactuals. GEAR uses a GraphVAE to generate the counterfactuals based on self-perturbation and neighbor-perturbation. Figure 5 shows the average result for all the nodes on the synthetic dataset. We show that CAF can find better counterfactuals than other graph counterfactual fairness models, i.e., smaller discrepancy to ground-truth counterfactuals. The result also shows there is still space for existing methods to improve the performance of getting appropriate counterfactuals.

### Ablation Study

In our model, the pre-trained model can provide pseudo-labels for the nodes in the unlabeled set. Thus, we can select counterfactuals from the entire dataset. The model trained from scratch, without any pre-training, is denoted as CAF-NP. Without pseudo-labels, we can only select counterfactuals from the training set, which is denoted as the variant CAF-NS. We evaluate the performance on synthetic dataset. The results are reported in Table 3. We find the model CAF-NS performs worse than the CAF but better than CAF-NP. The result shows the pseudo-labels can also boost the performance of our model. Usually, the training set is small and the model may not obtain desired counterfactuals from the limited data points. Although pseudo-labels may contain some noisy information, they can also help improve the our model performance.

We further delve into how the constraints impact performance. When merely setting \(\alpha=0\) or \(\beta=0\), we denote the model as CAF-NA and CAF-NB, respectively. The models CAF-NA and CAF-NB outperform SAGE, yet fall short when compared to CAF. This indicates that both the sufficiency and invariance constraints collectively contribute to the superior performance of our model.

### Hyper-Parameter Sensitivity Analysis

There are two important hyperparameters in CAF, i.e., \(\alpha\) and \(\beta\). \(\alpha\) controls the contribution of the invariance regularization \(\mathcal{L}_{\text{inv}}\) and \(\beta\) controls the contribution of the sufficiency regularization. To understand the impact of \(\alpha\) and \(\beta\) on CAF, we fix \(\beta\) as 5 and vary \(\alpha\) as \(\{0,1,\dots,18\}\). Similarly, we fix \(\alpha\) as 1 and vary \(\beta\) as \(\{0,1,\dots,18\}\). We report the result on German dataset in Figure 6. From Figure 6, we have the following observations: there exists a trade-off between prediction performance and fairness performance. The trend is that when we increase the \(\alpha\) and \(\beta\), we will get worse prediction performance and better fairness performance. We argue that without these regularizations, the model may rely on sensitive information. When we decrease the regularization budget, we can disentangle content representations. Thus, the prediction performance will get worse and the fairness performance will be better.

## 6. Conclusion and Future Work

In this paper, we study the problem of learning fair node representations with GNNs. We first formalize the biased graph generation process with an SCM. Motivated by causal theory, we propose a novel framework CAF to learn fair node presentations which meet graph counterfactual fairness criteria and can achieve good prediction-fairness performance. Specifically, we align the model design with the data generation process and convert the problem to learn content representations. We derive several properties of the optimal content representation from the causal graph, i.e., invariance, sufficiency and informativeness. To get appropriate supervision for the invariance regularization, we design a counterfactual selection module. Extensive experiments demonstrate that CAF can achieve state-of-the-art performance on synthetic dataset and real-world datasets with respect to the prediction-fairness trade-off.

There are several interesting directions worth exploring. First, in this paper, we mainly focus on binary classification and binary sensitive attribute. We will extend the work to multi-class classification and multi-category sensitive attributes. Second, in this paper, we focus on static graphs while there are many different kinds of graphs in real-world. Thus, we aim to extend our model to more complex graph learning settings, such as dynamic graphs, multi-value sensitive attributes and labels.

## Acknowledgments

This material is based upon work supported by, or in part by the National Science Foundation (NSF) under grants number IIS-1909702, IIS-2153326, and IIS-2212145, Army Research Office (ARO) under grant number W911NF-21-1-0198, Department of Homeland Security (DHS) CINA under grant number E205949D, and Cisco Faculty Research Award.

Figure 5. Discrepancy between learned counterfactual representation and ground-truth counterfactual representation.

Figure 6. Hyper-parameter study on German dataset.

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline \multirow{2}{*}{**Models**} & \multicolumn{5}{c}{**Synthetic Dataset**} \\ \cline{2-7}  & **AUROC \(\uparrow\)** & **F1 \(\uparrow\)** & \(\delta_{\text{CP}}\downarrow\) & \(\Delta_{\text{DP}}\downarrow\) & \(\Delta_{\text{BD}}\downarrow\) \\ \hline SAGE & 98.40\(\pm\)0.31 & 86.89\(\pm\)5.59 & 11.76\(\pm\)2.92 & 1.87\(\pm\)0.82 & 1.85\(\pm\)1.41 \\ CAF & 99.57\(\pm\)0.06 & 94.58\(\pm\)0.58 & 7.21\(\pm\)0.61 & 0.65\(\pm\)0.41 & 1.66\(\pm\)0.57 \\ CAF-NA & 99.33\(\pm\)2.92 & 94.72\(\pm\)2.15 & 10.42\(\pm\)1.98 & 1.63\(\pm\)0.41 & 1.83\(\pm\)0.74 \\ CAF-NB & 98.67\(\pm\)1.02 & 88.64\(\pm\)4.31 & 8.31\(\pm\)1.22 & 9.91\(\pm\)0.28 & 1.63\(\pm\)0.51 \\ CAF-NP & 98.36\(\pm\)3.99 & 87.42\(\pm\)2.07 & 13.47\(\pm\)2.62 & 1.37\(\pm\)0.55 & 1.96\(\pm\)1.78 \\ CAF-NS & 98.81\(\pm\)0.73 & 91.98\(\pm\)3.25 & 9.72\(\pm\)2.65 & 1.35\(\pm\)0.18 & 1.73\(\pm\)0.55 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Ablation study.