# Graph Fairness Learning under Distribution Shifts

Yibo Li  Beijing University of Posts and TelecommunicationsChina
<EMAIL_ADDRESS>,  Xiao Wang† Beihang UniversityChina<EMAIL_ADDRESS>,  Yujie Xing  Beijing University of Posts and TelecommunicationsChina yujie-
<EMAIL_ADDRESS>,  Shaohua Fan  Tsinghua UniversityKey Laboratory of Big Data
& Artificial Intelligence in Transportation, Ministry of Education(Beijing
Jiaotong University)China<EMAIL_ADDRESS>,  Ruijia Wang  Beijing
University of Posts and TelecommunicationsChina<EMAIL_ADDRESS>,
Yaoqi Liu  Beijing University of Posts and TelecommunicationsChina
<EMAIL_ADDRESS>and  Chuan Shi† Beijing University of Posts and
TelecommunicationsyChina<EMAIL_ADDRESS>
###### Abstract.

Graph neural networks (GNNs) have achieved remarkable performance on graph-
structured data. However, GNNs may inherit prejudice from the training data
and make discriminatory predictions based on sensitive attributes, such as
gender and race. Recently, there has been an increasing interest in ensuring
fairness on GNNs, but all of them are under the assumption that the training
and testing data are under the same distribution, i.e., training data and
testing data are from the same graph. Will graph fairness performance decrease
under distribution shifts? How does distribution shifts affect graph fairness
learning? All these open questions are largely unexplored from a theoretical
perspective. To answer these questions, we first theoretically identify the
factors that determine bias on a graph. Subsequently, we explore the factors
influencing fairness on testing graphs, with a noteworthy factor being the
representation distances of certain groups between the training and testing
graph. Motivated by our theoretical analysis, we propose our framework
FatraGNN. Specifically, to guarantee fairness performance on unknown testing
graphs, we propose a graph generator to produce numerous graphs with
significant bias and under different distributions. Then we minimize the
representation distances for each certain group between the training graph and
generated graphs. This empowers our model to achieve high classification and
fairness performance even on generated graphs with significant bias, thereby
effectively handling unknown testing graphs. Experiments on real-world and
semi-synthetic datasets demonstrate the effectiveness of our model in terms of
both accuracy and fairness.

Graph Neural Networks, Fairness, Distribution Shifts

†Corresponding authors.

††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Figure 1. Toy example of fairness under distribution shifts on graphs.

Graph Neural Networks (GNNs) are powerful deep learning algorithms that can be
used to model graph-structured data. In recent years, there have been enormous
successful applications of GNNs on various areas such as social media mining
(Hamilton et al., 2017; Yu et al., 2023a, b; Li et al., 2023; Wang et al.,
2017), drug discovery (Jin et al., 2018), and recommender system (Berg et al.,
2017; Ying et al., 2018). However, despite their success, there is a growing
concern that GNNs may inherit or even amplify discrimination and social bias
from the training data, leading to unfair treatment of sensitive groups with
sensitive attributes such as gender, age, region, and race. This may result in
social and ethical issues, thus limiting the application of GNNs in critical
areas such as job marketing (Johnson et al., 2009), criminal justice (Tolan et
al., 2019), and credit scoring (Feldman et al., 2015).

To mitigate this issue, many fair GNNs (Yao and Huang, 2017; Zeng et al.,
2021; Bose and Hamilton, 2019; Dai and Wang, 2021; Dong et al., 2022; Ling et
al., 2023) have been proposed. They improve graph fairness by adding a
fairness-related regularization term to the optimization objective (Yao and
Huang, 2017; Zeng et al., 2021), adopting adversarial learning to learn fairer
node representations (Bose and Hamilton, 2019; Dai and Wang, 2021), debiasing
the graph itself (Dong et al., 2022; Ling et al., 2023), etc. Despite the
success of fair GNNs, they are all proposed under the common hypothesis that
the training and testing data are under identical distribution, which does not
always hold in reality.

In real-world contexts, distribution shifts frequently occurs (Arjovsky et
al., 2019; Ahmed et al., 2021; Li et al., 2022; Wu et al., 2022) and can
adversely affect the fairness performance of existing fair GNNs. This is
exemplified in Figure 1, where a fair GNN designed for job recommendation is
trained on a social network from one state and subsequently applied to a
network from another state. In both social networks, race serves as the
sensitive attribute, and the label is whether to recommend the job. However,
the two graphs are under different distributions. Specifically in the testing
graph, there are larger feature differences between different sensitive
groups, and nodes within the same sensitive group are more likely to be
connected. After the feature aggregation step, the aggregated features of
nodes within the same sensitive group will be more homophilous, and nodes in
different sensitive groups will be even more distinguishable. As it is easy to
recognize the sensitive attributes of the nodes, the fair GNN relies more on
this information to make predictions on the testing graph, resulting in
discrimination such as disproportionately recommending low-payment jobs to
certain sensitive groups identified by race.

Although distribution shifts can lead to unfairness, previous studies (Wu et
al., 2022; Fan et al., 2022b, 2023, a) mainly aim at keeping stable
classification performance of GNNs under distribution shifts, while largely
ignoring the fairness issue. Why might graph fairness deteriorate under
distribution shifts? How does distribution shifts affect the fairness of GNNs?
The answers from a theoretical and methodological perspective remain largely
unknown.

Recently, the topic of fairness learning under distribution shifts has
received considerable attention (An et al., 2022; Schumann et al., 2019; Jiang
et al., 2023). However, all these works focus on Euclidean data, overlooking
the vital structural information in graphs. Such information helps in making
accurate predictions but runs the risk of amplifying the data bias, therefore
requiring additional careful consideration. In this work, we first
theoretically analyze the relationship between graph data distribution and
graph fairness (Theorem 3.6), and conclude that graph fairness is determined
by a sensitive structure-property and the feature difference between different
sensitive groups. This insight sheds light on the potential deterioration of
graph fairness due to distribution shifts. Then we prove that fairness on the
testing graph depends on two key factors: fairness on the training graph and
the representation distances of certain groups (nodes with the same label and
sensitive attribute) between the training graph and the testing graph (Theorem
3.8). These findings well deepen our understanding of graph fairness learning
under distribution shifts.

Motivated by our theoretical insights, we further propose a novel model called
FatraGNN to handle this issue. Our model employs an adversarial module to
ensure fairness on the training graph. As the testing graphs are unknown, we
draw inspiration from previous research (Wu et al., 2022) that generates
graphs under various distributions, and subsequently trains GNN on them to
bolster the classification performance on unknown testing graphs. Similarly,
we also utilize a graph generation module to generate graphs with significant
bias and under different distributions. Then we utilize an alignment module to
minimize the representation distances of each certain group between the
training graph and the generated graphs. If our model can learn fair
representations for these generated graphs with large bias, it will be more
robust to distribution shifts and effectively deal with specific testing
graphs which usually have smaller bias. In summary, our contributions are
three-fold:

  * •

To the best of our knowledge, this is the first attempt to study graph
fairness learning under distribution shifts from a theoretical perspective. We
theoretically analyze the relationship between graph fairness and graph data
distribution and discover the key factors that affect fairness learning under
distribution shifts.

  * •

Based on the theoretical insights, we propose our FatraGNN, which consists of
an adversarial debiasing module, a graph generation module, and an alignment
module, to ensure fairness on the unknown testing graphs.

  * •

Extensive experiments show that our FatraGNN outperforms state-of-the-art
baselines under distribution shifts in terms of both classification and
fairness performance on real-world and semi-synthetic datasets.

##  2\. Preliminaries and Notations

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ be a graph with $n$
nodes, where $\mathcal{V}=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the node set,
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the edge set.
$\mathbf{X}=[x_{1},x_{2},\dots,x_{n}]\in\mathbb{R}^{n\times\zeta}$ represents
the node feature matrix, where $x_{i}$ is the feature vector of node $v_{i}$
and $\zeta$ is the dimension of node features. Graph structure of
$\mathcal{G}$ can be described by the adjacency matrix
$\mathbf{A}\in\mathbb{R}^{n\times n}$, and $\mathbf{A}_{ij}=1$ iff there
exists an edge between nodes $v_{i}$ and $v_{j}$. The diagonal degree matrix
is denoted as $\mathbf{D}=\operatorname{diag}\left(d_{1},\cdots,d_{n}\right)$,
where $d_{i}=\sum_{j}\mathbf{A}_{ij}$. Node sensitive attributes are specified
by the $t$-th channel of $\mathbf{X}$, i.e.,
$\mathbf{F}=\mathbf{X}_{:,t}=[f_{1},f_{2},\dots,f_{n}]\in\\{0,1\\}^{n}$, where
$f_{i}$ is the sensitive attribute of node $i$. Here we focus on binary
classification tasks, and the binary labels of the nodes are denoted by
$\mathbf{Y}\in\\{0,1\\}^{n}$.

Fairness Metric There exist several different definitions of fairness, such as
group fairness (Mehrabi et al., 2021), individual fairness (Dwork et al.,
2012), counterfactual fairness (Kusner et al., 2017), and degree-related
fairness (Wang et al., 2022a). In this work, we focus on group fairness, and
use two commonly used metrics to measure it: equalized oods (Hardt et al.,
2016) and demographic parity (Calders et al., 2009). Equalized odds seeks to
achieve the same true positive rate and true negative rate between two
sensitive groups, which is defined as
$\Delta_{EO}=\dfrac{1}{2}\sum_{y=0}^{1}|\mathbb{E}_{v_{i}\in\mathcal{V}}(\hat{y}_{i}=y|y_{i}=y,f_{i}=1)-\mathbb{E}_{v_{j}\in\mathcal{V}}(\hat{y}_{j}=y|y_{j}=y,f_{j}=0)|$,
where $\hat{y}_{i}$ is the predicted label of $v_{i}$, and $y_{i}$ is the
ground-truth label of $v_{i}$. Demographic parity measures the acceptance rate
difference between two sensitive groups. For example, in binary classification
tasks such as deciding whether a student should be admitted into a university
or not, demographic parity is considered to be achieved if the model yields
the same acceptance rate for individuals in both sensitive groups. It is
defined as $\Delta_{DP}=|\mathbb{E}_{v_{i}\in\mathcal{V}}(\hat{y}_{i}=1\mid
f_{i}=1)-\mathbb{E}_{v_{j}\in\mathcal{V}}(\hat{y}_{j}=1\mid f_{j}=0)|$.

Fairness on Graph Distribution Shifts Following the definition of previous
study (Wu et al., 2022), we characterize the data generation process as
$\mathbb{P}(\mathbf{A},\mathbf{X},\mathbf{Y}|\mathbf{e})=\mathbb{P}(\mathbf{A},\mathbf{X}|\mathbf{e})\mathbb{P}(\mathbf{Y}|\mathbf{A},\mathbf{X},\mathbf{e})$,
where $\mathbf{e}$ represents a random variable denoting the latent
environmental factors that influence the data distribution. First, the graph
is generated via $\mathbb{P}(\mathbf{A},\mathbf{X}|\mathbf{e})$. Then the
labels are generated via
$\mathbb{P}(\mathbf{Y}|\mathbf{A},\mathbf{X},\mathbf{e})$. We assume that
$\mathbb{P}(\mathbf{Y}|\mathbf{A},\mathbf{X},\mathbf{e})$ is invariant under
different environments. Our aim is to achieve a scenario where the generation
of $\mathbf{Y}$ is not influenced by the features related to sensitive
attributes $\mathbf{F}$ to ensure fairness. We consider training graph from
data distribution
$\mathbb{P}(\mathbf{A}_{\mathcal{J}},\mathbf{X}_{\mathcal{J}}|\mathbf{e}=\mathcal{J})$,
testing graphs from data distribution
$\mathbb{P}(\mathbf{A}_{\mathcal{K}},\mathbf{X}_{\mathcal{K}}|\mathbf{e}=\mathcal{K})$.
This work intends to ensure fairness when $\mathcal{J}\neq\mathcal{K}$.

##  3\. Graph Fairness under Distribution Shifts

In this section, we first establish a relationship between graph fairness and
graph data distribution $\mathbb{P}(\mathbf{A},\mathbf{X}|\mathbf{e})$. Then
we gain insight into why distribution shifts may lead to fairness degradation.

###  3.1. Relationship between Data Distribution and Graph Fairness

We first use aggregated feature distance to establish the connection between
data distribution and graph fairness. Referring to commonly used GNNs, we
define the aggregated features as
$\mathbf{H}=\tilde{\mathbf{D}}^{-1}\tilde{\mathbf{A}}\mathbf{X}$, where
$\tilde{\mathbf{D}}=\mathbf{D}+\mathbf{I}$,
$\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$. For the convenience of expression,
we define sensitive group, EO group, and aggregated feature distance between
EO groups as follows:

###### Definition 3.1.

(Sensitive group) The sensitive group of nodes with sensitive attribute $f$ is
defined as:

(1) $\mathcal{V}_{f}=\\{v_{i}\in\mathcal{V}|f_{i}=f\\}.$

###### Definition 3.2.

(EO group) The EO group of nodes with label $y$ and sensitive attribute $f$ is
defined as:

(2) $\mathcal{V}_{f}^{y}=\\{v_{i}\in\mathcal{V}|(f_{i}=f)\cap(y_{i}=y)\\}.$

###### Definition 3.3.

(Aggregated feature distance between sensitive groups with the same label) The
aggregated feature distance between sensitive groups with label $y$ is defined
as:

(3)
$\eta_{y}=\max_{v_{a}\in\mathcal{V}_{1}^{y}}\min_{v_{b}\in\mathcal{V}_{0}^{y}}||h_{a}-h_{b}||_{2},$

where $h_{a}$ and $h_{b}$ are the aggregated features of nodes $v_{a}$ and
$v_{b}$, respectively.

The aggregated feature distance $\eta_{y}$ defines the maximum shortest path
from a node in $\mathcal{V}_{1}^{y}$ to a node in $\mathcal{V}_{0}^{y}$, thus
can measure the aggregated feature difference between the two sensitive groups
with label $y$. Large $\eta_{y}$ implies that the aggregated features of
different sensitive groups are easy to distinguish, and GNNs may make
predictions based on this sensitive information, resulting in unfairness.

Figure 2. Example of low sensitive homophily.

We then show that $\eta_{y}$ is mainly affected by two factors determined by
$\mathbb{P}(\mathbf{A},\mathbf{X}|\mathbf{e})$. The first factor is the
sensitive structure-property of the graph. Previous fairness studies (Ling et
al., 2023; Wang et al., 2022b) focus on the sensitive homophily of the graph
structure, defined as
$\alpha=\mathbb{E}_{v_{i}\in\mathcal{V}}\dfrac{\sum_{j\in
N_{i}\cup\\{v_{i}\\}}\mathbf{1}_{(f_{i}=f_{j})}}{d_{i}+1}$, where $N_{i}$ is
the neighbors of node $v_{i}$, $\mathbf{1}_{(f_{i}=f_{j})}$ is the indicator
function evaluating to 1 if and only if $f_{i}=f_{j}$. They believe that
higher sensitive homophily will make the aggregated features of two sensitive
groups more distinguishable, resulting in unfairness. However, we find that
lower sensitive homophily will also make aggregated features of sensitive
groups distinguishable. For example, the graph in Figure 2 has very low
sensitive homophily according to $\alpha$. After the aggregation step of GNN,
different sensitive groups may change their features but are still
distinguishable. We further point out that $\eta_{y}$ is determined by whether
the nodes tend to have balanced neighborhoods, i.e., the number of neighbors
belonging to different sensitive groups is nearly the same. To theoretically
analyze the relationship between balanced neighborhoods and $\eta_{y}$, we
define a new sensitive balance degree to quantify the structure property:

###### Definition 3.4.

(Sensitive balance degree) The sensitive balance degree of node $v_{i}$ with
sensitive attribute $f_{i}$ is:

(4) $u_{i}=|p_{i}-q_{i}|,$

where $p_{i}=\dfrac{\sum_{j\in
N_{i}\cup\\{v_{i}\\}}\mathbf{1}_{(f_{i}=f_{j})}}{{d_{i}+1}}$ and
$q_{i}=\dfrac{\sum_{j\in N_{i}\cup\\{v_{i}\\}}\mathbf{1}_{(f_{i}\neq
f_{j})}}{{d_{i}+1}}$ represent the proportions of neighbors with the same and
different sensitive attribute, respectively. The average sensitive balance
degree on a graph is :

(5) $u=\mathbb{E}_{i\in\mathcal{V}}(u_{i}).$

The sensitive balance degree reflects the difference in the number of
neighbors around node $v_{i}$ belonging to different sensitive groups. If a
node has nearly the same number of neighbors with different sensitive
attributes, then it has a more balanced neighborhood and smaller $u_{i}$, and
vice versa.

The second factor that affects $\eta_{y}$ is the feature difference between
different sensitive groups. We assume features of nodes belonging to two
sensitive groups follow Gaussian distribution, i.e., $\mathbb{P}(x_{a}\mid
v_{a}\in\mathcal{V}_{1})\sim\mathcal{N}(\mu_{\mathcal{V}_{1}}\mathbf{I}_{\zeta},\sigma_{\mathcal{V}_{1}}^{2}\mathbf{I}_{\zeta})$
and $\mathbb{P}(x_{b}\mid
v_{b}\in\mathcal{V}_{0})\sim\mathcal{N}(\mu_{\mathcal{V}_{0}}\mathbf{I}_{\zeta},\sigma_{\mathcal{V}_{0}}^{2}\mathbf{I}_{\zeta})$.
With the feature distribution of two sensitive groups and the graph structure
property $u$, we can bound $\eta_{y}$ with the following theorem:

###### Theorem 3.5.

For any $\delta\in(0,1)$, with probability greater than $1-\delta$ and large
enough feature dimension $\zeta$, we have:

(6)
$\displaystyle\eta_{y}^{2}\geq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1-2\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta
u^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2},$
$\displaystyle\eta_{y}^{2}\leq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1+4\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta
u^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2}.$

From the above theorem, we can find out that the upper bound and lower bound
of $\eta_{y}$ are determined by
$(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})$ and $u$. Then we show that the
fairness metric $\Delta_{EO}$ is actually bounded by $\eta_{y}$ as the
following theorem.

###### Theorem 3.6.

Consider an encoder $g:H\rightarrow Z\in\mathbb{R}^{n\times\zeta^{\prime}}$
extracting $\zeta^{\prime}$-dimensional representations $Z$ and an classifier
$\omega:Z\rightarrow C\in\mathbb{R}^{n\times 2}$ predicting the binary labels
of the nodes. Assume that $g$ and $\omega$ have $L_{1}$-Lipschitz and
$L_{2}$-Lipschitz continuity, respectively, then equalized odds is bounded by:

(7) $\Delta_{EO}\leq L_{1}L_{2}\dfrac{\sum_{y=0}^{1}\eta_{y}}{2}.$

Combining Theorem 3.6 and Theorem 3.5, we find out that $\Delta_{EO}$ is
mainly affected by two key factors determined by
$\mathbb{P}(\mathbf{A},\mathbf{X}|\mathbf{e})$: 1) The feature difference
between sensitive groups $\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$. Larger
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ indicates that the features of
the two sensitive groups are easier to distinguish, resulting in larger
$\Delta_{EO}$. 2) The average sensitive balance degree of the graph $u$.
Larger $u$ implies the nodes in the graph tend to have unbalanced neighbors,
resulting in larger $\Delta_{EO}$.

We direct the readers to Appendix A for proofs of all the above theorems.

###  3.2. Bounds on Fairness on the Testing Graph

Given the factors that affect graph fairness, we can gain insight into the
reason why distribution shifts may lead to unfairness.

As $\Delta_{EO}$ is determined by two factors affected by
$\mathbb{P}(\mathbf{A},\mathbf{X}|\mathbf{e})$, suppose the data distribution
differs between the training graph and testing graphs, i.e.,
$\mathbb{P}(\mathbf{A}_{\mathcal{J}},\mathbf{X}_{\mathcal{J}}|\mathbf{e}=\mathcal{J})\neq\mathbb{P}_{\mathcal{K}}(\mathbf{A}_{\mathcal{K}},\mathbf{X}_{\mathcal{K}}|\mathbf{e}=\mathcal{K})$,
then the two factors including $u$ and
$(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})$ will also change, resulting in
fairness deterioration in some cases. For example, if
$(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})$ and $u$ are small in the
training graph but large in the testing graph, then the model is highly fair
on the training graph but highly unfair on the testing graph.

Then we characterize the difference of $\Delta_{EO}$ between the training
graph and the testing graph, denoted as
$\Delta_{EO}^{\mathcal{J}}-\Delta_{EO}^{\mathcal{K}}$, by analyzing the
accuracy difference between the training graph and the testing graph of each
EO group. The EO group in the testing graph with label $y$ and sensitive
attribute $f$ is denoted as
$\mathcal{K}_{f}^{y}=\\{v_{i}\in\mathcal{V}_{\mathcal{K}}|(f_{i}=f)\cap(y_{i}=y)\\}$,
where $\mathcal{V}_{\mathcal{K}}$ is the node set in the testing grah, and we
define the prediction accuracy on $\mathcal{K}_{f}^{y}$ as
$\mathbb{E}_{\mathcal{K}_{f}^{y}}=\mathbb{E}_{v_{i}\in\mathcal{K}_{f}^{y}}(\hat{y_{i}}=y)$.
Similarly, on training graph we have
$\mathbb{E}_{\mathcal{J}_{f}^{y}}=\mathbb{E}_{v_{i}\in\mathcal{J}_{f}^{y}}(\hat{y_{i}}=y)$.
Then we bound the equalized odds difference for data in the training graph and
testing graph as:

(8) $\displaystyle\Delta_{EO}^{\mathcal{K}}-\Delta_{EO}^{\mathcal{J}}$
$\displaystyle\leq\sum_{y,f}|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|.$

We then define EO group representation distance between the training graph and
the testing graph in Definition 9, and build a relationship between the
representation distance and
$|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|$ in
Theorem 3.8.

###### Definition 3.7.

(EO group representation distance between the training graph and the testing
graph) For EO group with label $y$ and sensitive attribute $f$, we define the
representation distance between the training graph and the testing graph as:

(9)
$\epsilon_{f}^{y}=\max_{v_{j}\in\mathcal{K}_{f}^{y}}\min_{v_{i}\in\mathcal{J}_{f}^{y}}||z_{i}-z_{j}||_{2},$

where $z_{i}$ is the representation of node $v_{i}$ learned by the encoder
$g$.

###### Theorem 3.8.

Assume that the nonlinear transformation $\omega(Z)=RELU(ZW_{\omega})$ has
$L_{2}$-Lipschitz continuity, we have:

(10) $|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|\leq
L_{2}\epsilon_{f}^{y}.$

Then equalized odds difference between the training graph and the testing
graph can be bounded as:

(11) $\Delta_{EO}^{\mathcal{K}}-\Delta_{EO}^{\mathcal{J}}\leq
L_{2}\sum_{f,y}\epsilon_{f}^{y}.$

Based on Theorem 3.8, we can see that $\Delta_{EO}^{\mathcal{K}}$ relies on
both $\Delta_{EO}^{\mathcal{J}}$ and EO group representation distance, which
is determined by how much
$\mathbb{P}(\mathbf{A}_{\mathcal{K}},\mathbf{X}_{\mathcal{K}}|\mathbf{e}=\mathcal{K})$
differs from
$\mathbb{P}(\mathbf{A}_{\mathcal{J}},\mathbf{X}_{\mathcal{J}}|\mathbf{e}=\mathcal{J})$.
Please note that our objective is not to achieve a tight bound for equalized
odds on the testing graphs. Instead, our focus is on identifying the
sufficient conditions that ensure fair performance on the testing graphs, and
Theorem 3.8 actually reveals the sufficient conditions.

To alleviate the unfairness issue on the testing graph, i.e., minimize
$\Delta_{EO}^{\mathcal{K}}$, we not only have to minimize
$\Delta_{EO}^{\mathcal{J}}$, but also have to minimize the EO group
representation distance. Also, minimizing the EO group representation distance
leads to the minimization of $\Delta_{DP}^{\mathcal{K}}$. Detailed proofs of
minimization of $\Delta_{DP}^{\mathcal{K}}$, Theorem 3.8, and Eq. (8) are
deferred to Appendix A.

Figure 3. An overview of FatraGNN.

##  4\. Methodology

In order to solve the unfairness under distribution shifts problem, motivated
by the findings in Section 3, we present our framework (shown in Figure 3),
which mainly includes three parts: (a) the generative adversarial debiasing
module to get smaller $\Delta_{EO}^{\mathcal{J}}$ on the training graph, (b)
the graph generation module to generate graphs with large bias and are under
different distributions, (c) the EO group alignment module to minimize the EO
group representation distance.

###  4.1. Adversarial Debiasing on Training Graph

As suggested in Theorem 3.8, to improve fairness on the testing graph, we have
to ensure fairness on the training graph. Combining the aggregation step and
the encoder $g$ discussed in Section 3.1, we use a GNN-based encoder
$\rho_{\theta_{\rho}}:(\mathbf{A},\mathbf{X})\rightarrow
Z\in\mathbb{R}^{n\times\zeta^{\prime}}$ with parameters $\theta_{\rho}$ to
extract the $\zeta^{\prime}$-dimensional representations of the nodes. If the
representations of different sensitive groups are distinguishable, then the
classifier may make predictions based on this information, resulting in
unfairness. In order to make the representations undistinguishable, we use a
sensitive discriminator $\xi_{\theta_{\xi}}:Z\rightarrow F\in\\{0,1\\}^{n}$
with parameters $\theta_{\xi}$ to predict the sensitive attributes of the
nodes given their representations $Z$. And the encoder $\rho_{\theta_{\rho}}$
is trained to learn similar representations between sensitive groups, thus can
fool the discriminator. Leveraging adversarial training, we compute the loss
of the discriminator and encoder as:

(12)
$\displaystyle\min_{\theta_{\rho}}\max_{\theta_{\xi}}\mathcal{L}_{\xi}=\mathbb{E}_{v_{i}\in\mathcal{J}}(f_{i}\log(\xi_{\theta_{\xi}}(\rho_{\theta_{\rho}}(x_{i}))$
$\displaystyle+(1-f_{i})\log(1-\xi_{\theta_{\xi}}(\rho_{\theta_{\rho}}(x_{i})))).$

Besides, we also train the encoder together with an MLP-based classifier
$\omega_{\theta_{\omega}}$ to minimize the classification loss to ensure
accuracy:

(13)
$\min_{\theta_{\rho},\theta_{\omega}}\mathcal{L}_{c}=-\mathbb{E}_{v_{i}\in\mathcal{J}}\left(y_{i}\log(\hat{y_{i}})+(1-y_{i})\log(1-\hat{y_{i}})\right).$

###  4.2. Graph Generation Module

To address the unfairness issue caused by data distribution shifts, we should
also get similar representations between the training graph and the testing
graph for each EO group, as suggested in Theorem 3.8. During the training
process, we consider training $\rho_{\theta_{\rho}}$ to learn similar
representations for graphs under the distribution of
$\mathbb{P}(\mathbf{A}_{\mathcal{K}},\mathbf{X}_{\mathcal{K}}|\mathbf{e}=\mathcal{K})$
and
$\mathbb{P}(\mathbf{A}_{\mathcal{J}},\mathbf{X}_{\mathcal{J}}|\mathbf{e}=\mathcal{J})$.
As
$\mathbb{P}(\mathbf{A}_{\mathcal{K}},\mathbf{X}_{\mathcal{K}}|\mathbf{e}=\mathcal{K})$
is unknown during the training process, it is challenging to generate the
exact testing graphs, so we generate graphs with significant bias and are
under different distributions. If our model can handle graphs that are more
likely to cause unfairness, it will be able to address unfairness issues under
distribution shifts more effectively. The generated graphs follows
distribution
$\mathbb{P}(\mathbf{A}_{\mathcal{K}^{\prime}},\mathbf{X}_{\mathcal{K}^{\prime}}|\mathbf{e}=\mathcal{K}^{\prime})$.
As demonstrated in Theorem 3.6, larger
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ and $u$ will lead to poor
fairness performance. So we propose a graph generation module, including a
structure modification step to generate $\mathbf{A}_{\mathcal{T^{\prime}}}$ by
modifying $\mathbf{A}_{\mathcal{J}}$, and a feature generator to generate
$\mathbf{X}_{\mathcal{T^{\prime}}}$ based on $\mathbf{X}_{\mathcal{J}}$. Thus
we can generate graphs that will lead to unfairness and are under different
distributions.

For the structure modification step, we generate graphs with larger $u$, i.e.,
graphs with significant unbalanced neighborhoods. Two strategies can be
employed: One is randomly adding edges between nodes with the same sensitive
attribute and removing edges between nodes with different sensitive attribute.
The other is the inverse. Both are used to get a bunch of generated
$\mathbf{A}_{\mathcal{T^{\prime}}}$ with larger $u$ before training.

To make our model adapt to various structures, we feed one of the generated
graphs into training during every certain number of epochs, then we use an
MLP-based feature generator
$\Gamma_{\theta_{\Gamma}}:\mathbf{X}_{\mathcal{J}}\rightarrow\mathbf{X}_{\mathcal{T^{\prime}}}$
to generate features with larger
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$. The generated graph with
$\mathbf{A}_{\mathcal{T^{\prime}}}$ and $\mathbf{X}_{\mathcal{T^{\prime}}}$ is
then feed into $\rho$ and $\omega$ to make predictions. We also include a
regularization term to ensure that the feature generator does not produce
features that significantly stray from the features of the training graph. The
feature generator is trained to maximize the fairness loss:

(14)
$\displaystyle\max_{\theta_{\Gamma}}\mathcal{L}_{fair}^{\mathcal{K}^{\prime}}=\dfrac{1}{2}\sum_{y=0}^{1}|\mathbb{E}_{v_{i}\in\mathcal{J}_{1}^{y}}(\hat{y_{i}}=y|\Gamma(x_{i}),\mathbf{A}_{\mathcal{T^{\prime}}})$
$\displaystyle-\mathbb{E}_{v_{j}\in\mathcal{J}_{0}^{y}}(\hat{y_{j}}=y|\Gamma(x_{j}),\mathbf{A}_{\mathcal{T^{\prime}}})|-\tau||\mathbf{X}_{\mathcal{T^{\prime}}}-\mathbf{X}_{\mathcal{J}}||_{F}^{2}.$

where $||\cdot||_{F}^{2}$ is the Frobenius norm of matrix, $\tau$ is the
coefficient.

Thus the feature generator can be trained to explore the features that lead to
poor fairness performance but not deviate too much from the training graph.
After the structure modification step and the feature generation step, we can
generate graphs that lead to unfairness and under different distributions.

###  4.3. EO Group Alignment Module

We can learn from Theorem 3.8 that the unfairness issue on the testing graph
can be alleviated by minimizing the EO group representation distance
$\epsilon_{f}^{y}$. Thus we aim to minimize EO group representation distance
between the training graph and the generated graph.

We utilize a similarity score
$\lambda_{f}^{y}=\mathbb{E}_{i\in\mathcal{J}_{f}^{y},j\in\mathcal{K}_{f}^{{}^{\prime}y}}\dfrac{(z_{i}z_{j})}{||z_{i}||\cdot||z_{j}||}$
to measure the alignment of EO group representation. Higher $\lambda_{f}^{y}$
implies better alignment and lower $\epsilon_{f}^{y}$. Then we maximize the
similarity score of all EO groups:

(15) $\max_{\theta_{\rho}}\mathcal{L}_{align}=\sum_{f,y}\lambda_{f}^{y}.$

In this way, we can get smaller $\epsilon_{f}^{y}$, implying better fairness
performance on the testing graph. Furthermore, the alignment module improves
the classification accuracy on generated graphs by guiding the GNN-based
encoder to acquire similar representations for both the training graph and the
generated graphs.

Meanwhile, the alignment module implicitly aids in preserving the causal
features from disruption. The module forces the shared encoder to learn
similar representations for the generated graphs and the training graph. As
the encoder is shared, it is not possible to learn similar representations for
features with significant differences. This implicitly forces the generator to
learn features that are not significantly different from the original graph
but may cause unfairness. Experimental analysis can be found in Section 5.4.

##  5\. Experiment

Table 1.  Classification and fairness performance (%$\pm\sigma$) on Bail-Bs. $\uparrow$ denotes the larger, the better; $\downarrow$ denotes the opposite. Best ones are in bold. | metric | MLP | GCN | FairVGNN | NIFTY | EDITS | EERM | CAF | SAGM | RFR | FatraGNN (ours)
---|---|---|---|---|---|---|---|---|---|---|---
B1 | ACC$\uparrow$ | 70.53$\pm 1.01$ | 72.93$\pm 4.06$ | 69.76$\pm 2.03$ | 69.54$\pm 7.26$ | 72.69$\pm 1.72$ | 73.25$\pm 1.4$ | 69.39$\pm 2.30$ | 73.08 $\pm 4.25$ | 71.63 $\pm 1.52$ | 74.59$\mathbf{\pm 0.93}$
ROC-AUC$\uparrow$ | 62.76$\pm 1.87$ | 59.41$\pm 14.42$ | 64.82$\pm 4.32$ | 62.65$\pm 5.95$ | 59.91$\pm 0.31$ | 63.98$\pm 1.28$ | 62.84$\pm 1.84$ | 62.76$\pm 3.45$ | 62.39$\pm 1.53$ | 66.0$\mathbf{\pm 0.01}$
$\Delta_{DP}\downarrow$ | 4.83$\pm 9.38$ | 4.58$\pm 0.78$ | 11.05$\pm 4.58$ | 7.21$\pm 4.54$ | 4.35$\pm 1.3$ | 8.85$\pm 2.57$ | 4.46$\pm 2.03$ | 7.33$\pm 4.59$ | 2.57$\pm 1.24$ | 1.14$\mathbf{\pm 2.87}$
$\Delta_{EO}\downarrow$ | 7.48$\pm 7.31$ | 10.19$\pm 2.3$ | 8.35$\pm 4.82$ | 9.57$\pm 2.8$ | 9.22$\pm 0.97$ | 10.93$\pm 2.38$ | 4.97$\pm 2.31$ | 7.35$\pm 4.56$ | 2.63$\pm 0.87$ | 2.38$\mathbf{\pm 3.19}$
B2 | ACC$\uparrow$ | 64.33$\pm 0.63$ | 69.88$\pm 0.45$ | 65.03$\pm 2.4$ | 69.95$\pm 8.3$ | 69.03$\pm 0.16$ | 70.2$\pm 0.12$ | 69.36$\pm 1.37$ | 68.67$\pm 3.24$ | 68.62$\pm 1.42$ | 70.46$\mathbf{\pm 0.44}$
ROC-AUC$\uparrow$ | 59.21$\pm 1.18$ | 68.35$\pm 10.68$ | 70.21$\pm 2.61$ | 65.93$\pm 13.46$ | 74.25$\pm 0.73$ | 72.23$\pm 0.49$ | 71.58$\pm 2.03$ | 70.67$\pm 2.14$ | 70.25$\pm 2.35$ | 73.27$\mathbf{\pm 4.48}$
$\Delta_{DP}\downarrow$ | 8.36$\pm 1.62$ | 6.91$\pm 0.58$ | 5.64$\pm 2.78$ | 3.21$\pm 4.54$ | 3.2$\pm 3.06$ | 8.31$\pm 0.5$ | 2.53$\pm 3.62$ | 5.78$\pm 2.53$ | 2.15$\pm 1.94$ | 0.15$\mathbf{\pm 0.79}$
$\Delta_{EO}\downarrow$ | 6.51$\pm 0.32$ | 8.68$\pm 0.2$ | 3.23$\pm 3.47$ | 3.57$\pm 2.8$ | 2.89$\pm 0.54$ | 6.29$\pm 0.12$ | 3.81$\pm 2.08$ | 6.34$\pm 3.56$ | 2.64$\pm 1.63$ | 0.43$\mathbf{\pm 1.14}$
B3 | ACC$\uparrow$ | 60.76$\pm 0.18$ | 68.56$\pm 4.2$ | 70.63$\pm 0.61$ | 68.8$\pm 9.76$ | 68.56$\pm 1.82$ | 70.69$\pm 5.42$ | 68.97$\pm 2.44$ | 69.50$\pm 2.12$ | 68.36$\pm 1.89$ | 71.65$\mathbf{\pm 4.65}$
ROC-AUC$\uparrow$ | 62.89$\pm 2.87$ | 72.99$\pm 0.68$ | 80.76$\pm 5.01$ | 77.98$\pm 5.5$ | 79.28$\pm 1.48$ | 79.98$\pm 3.61$ | 78.04$\pm 2.67$ | 78.43$\pm 3.90$ | 78.74$\pm 1.95$ | 82.17$\mathbf{\pm 3.63}$
$\Delta_{DP}\downarrow$ | 9.8$\pm 0.38$ | 12.72$\pm 2.44$ | 8.05$\pm 0.45$ | 6.21$\pm 4.54$ | 5.24$\pm 0.03$ | 5.64$\pm 3.49$ | 6.32$\pm 2.45$ | 6.78$\pm 3.23$ | 4.23$\mathbf{\pm 1.72}$ | 5.02$\pm 3.54$
$\Delta_{EO}\downarrow$ | 6.29$\pm 0.36$ | 14.15$\pm 3.09$ | 9.18$\pm 0.36$ | 5.57$\pm 2.8$ | 3.08$\pm 0.27$ | 4.65$\pm 1.21$ | 4.32$\pm 2.67$ | 5.67$\pm 2.84$ | 4.72$\pm 2.17$ | 2.43$\mathbf{\pm 4.94}$
B4 | ACC$\uparrow$ | 63.13$\pm 1.69$ | 69.43$\pm 0.48$ | 68.99$\pm 2.44$ | 57.96$\pm 11.99$ | 68.42$\pm 0.14$ | 70.9$\pm 1.36$ | 67.33$\pm 2.67$ | 70.88$\pm 0.98$ | 69.18$\pm 2.68$ | 72.59$\mathbf{\pm 3.39}$
ROC-AUC$\uparrow$ | 61.57$\pm 0.97$ | 76.4$\pm 0.78$ | 77.23${\pm 1.14}$ | 69.21$\pm 5.39$ | 69.2$\pm 1.41$ | 68.81$\pm 2.27$ | 71.93$\pm 1.64$ | 69.34$\pm 1.89$ | 68.35$\pm 2.52$ | 77.36$\mathbf{\pm 3.79}$
$\Delta_{DP}\downarrow$ | 4.45$\pm 3.15$ | 4.49$\pm 1.13$ | 5.21$\pm 6.03$ | 3.21$\pm 4.54$ | 3.2$\pm 9.1$ | 7.23$\pm 0.26$ | 3.84$\pm 1.41$ | 6.36$\pm 6.32$ | 3.43$\pm 2.45$ | 2.48$\mathbf{\pm 3.09}$
$\Delta_{EO}\downarrow$ | 3.29$\pm 3.54$ | 8.74$\pm 1.62$ | 5.33$\pm 6.18$ | 2.57$\pm 2.8$ | 5.6$\pm 7.86$ | 9.04$\pm 0.86$ | 5.36$\pm 2.19$ | 7.34$\pm 4.67$ | 3.51$\pm 2.39$ | 2.45$\mathbf{\pm 6.67}$
| rank | 10 | 9 | 5 | 8 | 2 | 7 | 3 | 6 | 4 | 1
Table 2.  Quantitative results (%$\pm\sigma$) on Pokecs. (bold: best) | metric | MLP | GCN | FairVGNN | NIFTY | CAF | SAGM | RFR | FatraGNN (ours)
---|---|---|---|---|---|---|---|---|---
Pokec-n | ACC$\uparrow$ | 52.74$\pm 3.67$ | 54.83$\pm 2.34$ | 60.8$\pm 0.54$ | 58.68$\pm 5.54$ | 59.37$\pm 1.45$ | 58.78$\pm 2.33$ | 57.42$\pm 3.68$ | 62.00$\mathbf{\pm 0.24}$
ROC-AUC$\uparrow$ | 65.38$\pm 0.43$ | 63.48$\pm 2.34$ | 65.26$\pm 1.45$ | 67.09$\pm 2.25$ | 66.86$\pm 1.32$ | 65.67$\pm 2.45$ | 65.29$\pm 1.36$ | 67.82$\mathbf{\pm 3.23}$
$\Delta_{DP}\downarrow$ | 4.86$\pm 1.23$ | 7.38$\pm 0.28$ | 5.88$\pm 2.34$ | 4.21$\pm 3.43$ | 5.49$\pm 2.65$ | 5.67$\pm 3.22$ | 4.56$\pm 2.85$ | 1.34$\mathbf{\pm 0.27}$
$\Delta_{EO}\downarrow$ | 4.16$\pm 2.34$ | 6.37$\pm 0.52$ | 6.26$\pm 2.21$ | 3.82$\pm 3.88$ | 5.02$\pm 0.73$ | 4.19$\pm 2.45$ | 3.41$\pm 2.37$ | 1.43$\mathbf{\pm 2.68}$
| rank | 7 | 8 | 6 | 2 | 3 | 5 | 4 | 1

Datasets We use five datasets to evaluate the performance of our model under
distribution shifts. Each dataset comprises at least two graphs: one for
training and validation, and others for testing. The five datasets comprise
three real-world datasets and two semi-synthetic datasets summarized as
follows. 1) Pokecs includes Pokec-z and Pokec-n, which are drawn from the
popular social network in Slovakia (Dai and Wang, 2022) based on the provinces
that users belong to. Both Pokec-z and Pokec-n consist of users belonging to
two major regions of the corresponding provinces. We use Pokec-z for training
and validation, and Pokec-n for testing. We treat "region" as the sensitive
attribute, and the task is to predict the working field of the users. 2) Bail-
Bs is obtained from the commonly used fairness-related graph Bail (Jordan and
Freiburger, 2015), where nodes are defendants released on bail. Utilizing the
modularity-based community detection method (Newman, 2006), we partition Bail
into communities and find that they exhibit different data distributions. Then
we retain five large communities and name them from B0 to B4. We use B0 for
training and validation, and the remaining graphs B1 to B4 for testing. The
task is to decide whether to bail the defendants with "race" being the
sensitive attribute. 3) Credit-Cs is partitioned the same way as Bail-Bs from
Credit (Yeh and Lien, 2009), where nodes represent credit card users. We get
five communities named from C0 to C4. C0 is used for training and validation,
while C1 to C4 are used for testing. The task is to classify the credit risk
of the clients as high or low with "age" being the sensitive attribute. 4)
sync-B1s comprises testing graphs with different $u$ from 0 to 0.6 obtained by
modifying the structure of B1, and a training graph B0. 5) sync-B2s consisits
of testing graphs obtained by modifying B2 the same way as sync-B1s and a
training graph B0. More details such as dataset statistics and the data
distribution of the training graph and testing graphs can be found in Appendix
B.

Baselines We compare our model with nine baselines: 1) Traditional learning
methods: MLP (Pal and Mitra, 1992), GCN (Kipf and Welling, 2017). 2) Fair
GNNs: FairVGNN (Wang et al., 2022b), NIFTY (Agarwal et al., 2021), EDITS (Dong
et al., 2022), CAF (Guo et al., 2023). 3) Out-of-distribution (OOD) GNN: EERM
(Wu et al., 2022). 4) Model-agnostic OOD method: SAGM (Wang et al., 2023). 5)
Fairness under distribution shifts methods: RFR (Jiang et al., 2023).

Performance Evaluation We use accuracy (ACC) and ROC-AUC to evaluate the
predictive performance of the node classification task. To measure fairness,
we use $\Delta_{DP}$ and $\Delta_{EO}$ introduced in Section 2. Note that a
model with lower $\Delta_{DP}$ and $\Delta_{EO}$ implies better fairness
performance. To comprehensively assess the classification and fairness
performance of a model across various testing graphs, we introduce a metric
denoted as $s=\text{ACC}+\text{ROC-AUC}-\Delta_{DP}-\Delta_{EO}$, where
greater values of this metric indicate superior model performance. We
calculate the total score for each method by summing up their scores on all
testing graphs, and then provide the overall rankings for each method.

Experimental Setting We perform a hyperparameter search for our model on all
dataset groups. For other baseline models: GCN, MLP, FairVGNN, NIFTY, EDITS,
and EERM, we carefully fine-tune them to get optimal performance on all the
dataset groups. Note that EDITS and EERM have higher complexity and are hard
to be trained on Pokec-z , so we only report the results of other baselines on
Pokecs. For all methods, we randomly run 5 times and report the mean and
variance of each metric. More details such as the hyperparameter setting can
be found in Appendix B.

###  5.1. Evaluation on Real-world Datasets

We use three real-world datasets for evaluation: Pokecs, Bail-Bs, and Credit-
Cs.

Results Table 1 and Table 2 show the effectiveness of FatraGNN in terms of
classification and fairness performance on all testing graphs in Bail-Bs and
Pokecs. Due to space limitations, we defer the results on Credit-Cs to
Appendix C.

We observe that the proposed FatraGNN outperforms all baselines in most cases.
Additionally, we find that while fairness baselines aim to improve fairness
performance, they cannot perform well on testing graphs when distribution
shifts. Although the graph OOD model EERM achieves better classification
performance than fairness baselines when distribution shifts, it has lower
fairness performance on all the testing graphs because it cannot learn fair
representations.

We also analyze the relationship between accuracy and $\Delta_{EO}$ of the
models, because good fairness performance could be a result of poor
classification performance. For example, if a model misclassifies all samples,
then the accuracy on all EO groups will be 0, resulting in $\Delta_{EO}=0$,
which implies good fairness performance. However, this is not the ideal model.
Fairness models may ensure fairness at the cost of accuracy, so we further
show the Pareto front curves (Teich, 2001), which are generated by a grid
search of hyperparameters, to show this trade-off between accuracy and
$\Delta_{EO}$. As shown in Figure 4, the horizontal axis represents
$\Delta_{EO}$ and the vertical axis represents accuracy. Curves closer to the
upper-left corner imply higher accuracy and lower $\Delta_{EO}$, indicating
better trade-off performance. We can see that FatraGNN achieves better
performance than fairness baselines in terms of this trade-off.

###  5.2. Evaluation on Semi-synthetic Datasets

We further use sync-B1s and sync-B2s to test the performance of each method on
testing graphs with different $u$. Testing graphs with higher $u$ have less
balanced neighbors and may result in unfairness.

Figure 4. Trade-off of ACC and $\Delta_{EO}$ on all testing graphs of Bail-Bs,
Credit-Cs. Upper-left corner (high accuracy, low $\Delta_{EO}$) is preferred.
The first row shows the results on B1 to B4. The second row shows the results
on C1 to C4.

Figure 5. Accuracy and $\Delta_{EO}$ on sync-B1s (left) and sync-B2s (right).

Figure 6. Ablation study on sync-B1s (left) and Bail-Bs (right). Please note
that testing graphs of sync-B1s have continuously varying $u^{\prime}$, so we
utilize a line chart to illustrate the performance change of the model on
graphs with varying $u^{\prime}$.

Results As $u$ is calculated by $|p-q|$, we find that accuracy of the models
have different changing trend when $p-q>0$ and $p-q<0$. In order to
demonstrate the performance of models more clearly, we use $u^{\prime}=p-q$
instead to reflect the average sensitive balance degree of the graphs.

The classification and fairness performance are shown in Figure 5. Overall,
our FatraGNN outperforms other baselines in terms of both accuracy and
$\Delta_{EO}$ on most testing graphs. Moreover, FatraGNN demonstrates low
variance in both classification and fairness performance across different
testing graphs with various $u^{\prime}$, indicating its potential to perform
well when distribution shifts. Additionally, we find that most models achieve
their optimal fairness performance when $u^{\prime}$ is close to 0. When
$u=|u^{\prime}|$ increases, $\Delta_{EO}$ also increases, verifying our
analysis in Section 3.1 that unbalanced neighborhoods will lead to unfairness.
Additionally, we find that baselines tend to achieve better accuracy as
$u^{\prime}$ increases. This is because the nodes with the same sensitive
attribute tend to share the same label, which provides additional information
for the classification task.

Figure 7. The representation difference between sensitive groups, equalized
odds, and accuracy on the generated graph during training.

###  5.3. Ablation Study

To fully understand the effect of each component of FatraGNN on alleviating
unfairness under distribution shifts, we propose several variants of FatraGNN,
including Fatra w/o AD as removing the adversarial module, Fatra w/o GE as
removing the graph generation module, Fatra w/o MD as removing the structure
modification step, and Fatra w/o AL as removing the EO group alignment module.
Results of the ablation study on sync-B1s and Bail-Bs are shown in Figure 6.
We can see that FatraGNN consistently outperforms the other variants. Without
the adversarial module, Fatra w/o AD learns distinguishable representations
for the two sensitive groups, resulting in poor fairness performance. Without
the graph generation module, Fatra w/o GE fails to perform well when
distribution shifts. Without the alignment module, Fatra w/o AL only generates
graphs but is not trained to learn similar representations between the input
graph and the generated graph for each EO group, resulting in similar poor
performance as Fatra w/o GE. Without modification of the structure, Fatra w/o
MD still performs better than Fatra w/o GE and Fatra w/o AL, since it is
trained to adapt to different feature distributions. However, due to the lack
of training graph with different $u^{\prime}$, Fatra w/o MD cannot perform
well on testing graphs with different $u^{\prime}$.

###  5.4. Additional Analysises

Analysis of Generated Graphs We also analyze the generated graphs and find
that the generated graphs have different distributions from the training
graph, and their casual features are maintained.

First, we show that the generated graphs are under different distributions
from the training graph. Usually, graphs with different $u$ and
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ have different distributions
because the structures of the graphs and the feature difference between
different sensitive groups are different. In the generation module, we modify
the structure of the graph to get larger $u$. Also, as we learn feature
representations through an end-to-end method to get graphs that lead to
unfairness, $\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ of the generated
graph will also change during training. We do experiments Bail-Bs. As shown in
Figure 7, as the number of epochs increases,
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ increases, indicating that the
generated graphs are under different distributions from the training graph.

Then we examine if there are potential disruptions in the causal features of
the generated graphs. We conduct experiments on Bail-Bs to observe the changes
in $\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$, $\Delta{EO}$, and accuracy
during the training process. As shown in Figure 7, during training, the
generated graphs have larger $\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ and
poorer fairness (larger $\Delta{EO}$). This suggests that the generated graphs
will lead to unfairness and are under different distributions. Still, the
accuracy hardly decreases, indicating that the key features of the graph are
not disrupted.

Analysis of Representation Distances To demonstrate that by achieving
alignment of representations between the training graph and generated graphs,
our model can ensure alignment between the representations of the training
graph and testing graphs for better fairness and accuracy performance, we plot
the representations of the training graph and testing graphs of Bail-Bs using
t-SNE (Van der Maaten and Hinton, 2008). The implementation details and result
figures can be found in Appendix C.4. We can see that the representations of
nodes belonging to the same EO group on the training graph and testing graphs
are close, indicating that by minimizing the representation difference between
the training graph and the generated graphs, the alignment module of our model
can ensure the proximity of representations of the same EO group between the
training graph and testing graphs, thereby guaranteeing fairness and accuracy
on the testing graphs.

Analysis of Convergence We notice that during training, it is not difficult to
tune the parameters to achieve convergence. Despite that no theory can
guarantee convergence to the saddle point, it functions well in our
experiments, which has also been observed in many other adversarial methods
(Wang et al., 2022b; Goodfellow et al., 2020; Qi et al., 2018). Additional
experiments are provided in Appendix C.3.

Other additional experiment results such as hyperparameter study can be found
in Appendix C.

##  6\. Related Work

Fairness on GNNs There have been a number of works focused on the unfairness
problem on graphs (Agarwal et al., 2021; Dong et al., 2022; Wang et al.,
2022b; Ling et al., 2023). NIFTY (Agarwal et al., 2021) conducts a two-level
strategy to modify GNN to ensure fairness and stability. EDITS (Dong et al.,
2022) proposes to debias the attributed network to achieve fairness by feeding
GNNs with less biased graphs. FairVGNN (Wang et al., 2022b) proposes a
framework to improve fairness by automatically identifying and masking
sensitive-correlated features considering correlation variation after each
feature propagation step. FairAdj (Li et al., 2021) indicates that fairness on
a graph is contingent on both the size of the sensitive groups and the
connected situation of a graph, and proposes FairAdj to learn a fair matrix to
achieve dynamic fairness and prediction utility. More recently, Graphair (Ling
et al., 2023) adopts adversarial learning and contrastive learning to
automatically discover fairness-aware augmentations from input graphs.
However, these works are all under the assumption that training and testing
data are under the same distribution.

Fairness under Distribution Shifts Recently, a number of works intend to study
fairness under distribution shifts (Schumann et al., 2019; Coston et al.,
2019; Farnadi et al., 2018; Mandal et al., 2020; Rezaei et al., 2021; An et
al., 2022). (Coston et al., 2019; Giguere et al., 2022) Reweight the examples
in the training data to approximate the proportions of groups in the testing
data is one of the . (Mandal et al., 2020; Rezaei et al., 2021) consider data
in the testing data as combinations of samples in the training data with
arbitrary weights and ensure fairness of the model under the worst-case shift.
(An et al., 2022) derives a sufficient condition for transferring fairness,
and proposes a self-training algorithm to minimize and balance consistency
loss across groups. However, these works are all focused on Euclidean data and
ignore the special property of graph structure. To the best of our knowledge,
this is the first work that considers fairness under distribution shifts on
graphs.

More related work such as OOD generalization methods on graphs can be found in
Appendix D.

##  7\. Conclusion

In this work, we study the unfairness problem under distribution shifts on
graphs, which is crucial for the real-world applications of fair GNNs. We
theoretically prove that graph fairness is determined by a sensitive structure
property and feature difference between sensitive groups of the graph, and
explain the reason why distribution shifts will lead to unfairness. We then
derive an upper bound for fairness on the testing graph. Based on our
analysis, we further propose a novel FatraGNN framework to alleviate this
problem. Experimental results demonstrate that FatraGNN consistently
outperforms state-of-the-art baselines in terms of fairness-accuracy trade-off
performance under distribution shifts.

###### Acknowledgements.

This work is supported in part by the National Natural Science Foundation of
China (No. U20B2045, 62192784, U22B2038, 62002029, 62172052, 62322203,
62172052). This work is also supported by Foundation of Key Laboratory of Big
Data Artificial Intelligence in Transportation(Beijing Jiaotong University),
Ministry of Education (No.BATLAB202301). This work is also funded by China
Postdoctoral Science Foundation (No. 2023M741946) and China Postdoctoral
Researcher Program (No.GZB20230345).

## References

  * (1)
  * Agarwal et al. (2021) Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. 2021.  Towards a unified framework for fair and stable graph representation learning. In _Uncertainty in Artificial Intelligence_. PMLR, 2114–2124.
  * Ahmed et al. (2021) Faruk Ahmed, Yoshua Bengio, Harm van Seijen, and Aaron C. Courville. 2021.  Systematic generalisation with group invariant predictions. In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.  https://openreview.net/forum?id=b9PoimzZFJ
  * An et al. (2022) Bang An, Zora Che, Mucong Ding, and Furong Huang. 2022.  Transferring Fairness under Distribution Shifts via Fair Consistency Regularization. In _NeurIPS_.  http://papers.nips.cc/paper_files/paper/2022/hash/d1dbaabf454a479ca86309e66592c7f6-Abstract-Conference.html
  * Arjovsky et al. (2019) Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. 2019.  Invariant Risk Minimization.  _CoRR_ abs/1907.02893 (2019).  arXiv:1907.02893 http://arxiv.org/abs/1907.02893
  * Berg et al. (2017) Rianne van den Berg, Thomas N Kipf, and Max Welling. 2017.  Graph convolutional matrix completion.  _arXiv preprint arXiv:1706.02263_ (2017).
  * Bose and Hamilton (2019) Avishek Bose and William Hamilton. 2019.  Compositional fairness constraints for graph embeddings. In _International Conference on Machine Learning_. PMLR, 715–724.
  * Calders et al. (2009) Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. 2009.  Building classifiers with independency constraints. In _2009 IEEE international conference on data mining workshops_. IEEE, 13–18.
  * Coston et al. (2019) Amanda Coston, Karthikeyan Natesan Ramamurthy, Dennis Wei, Kush R Varshney, Skyler Speakman, Zairah Mustahsan, and Supriyo Chakraborty. 2019.  Fair transfer learning with missing protected attributes. In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_. 91–98.
  * Dai and Wang (2021) Enyan Dai and Suhang Wang. 2021.  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_. 680–688.
  * Dai and Wang (2022) Enyan Dai and Suhang Wang. 2022.  Learning fair graph neural networks with limited and private sensitive attribute information.  _IEEE Transactions on Knowledge and Data Engineering_ (2022).
  * Dong et al. (2022) Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. 2022.  Edits: Modeling and mitigating data bias for graph neural networks. In _Proceedings of the ACM Web Conference 2022_. 1259–1269.
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012.  Fairness through awareness. In _Proceedings of the 3rd innovations in theoretical computer science conference_. 214–226.
  * Fan et al. (2022a) Shaohua Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. 2022a.  Debiasing graph neural networks via learning disentangled causal substructure.  _Advances in Neural Information Processing Systems_ 35 (2022), 24934–24946.
  * Fan et al. (2023) Shaohua Fan, Xiao Wang, Chuan Shi, Peng Cui, and Bai Wang. 2023.  Generalizing graph neural networks on out-of-distribution graphs.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2023).
  * Fan et al. (2022b) Shaohua Fan, Xiao Wang, Chuan Shi, Kun Kuang, Nian Liu, and Bai Wang. 2022b.  Debiased graph neural networks with agnostic label selection bias.  _IEEE Transactions on Neural Networks and Learning Systems_ (2022).
  * Farnadi et al. (2018) Golnoosh Farnadi, Pigi Kouki, Spencer K Thompson, Sriram Srinivasan, and Lise Getoor. 2018.  A fairness-aware hybrid recommender system.  _arXiv preprint arXiv:1809.09030_ (2018).
  * Feldman et al. (2015) Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. 2015.  Certifying and removing disparate impact. In _proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining_. 259–268.
  * Giguere et al. (2022) Stephen Giguere, Blossom Metevier, Yuriy Brun, Bruno Castro da Silva, Philip Thomas, and Scott Niekum. 2022.  Fairness guarantees under demographic shift. In _International Conference on Learning Representations_.
  * Goodfellow et al. (2020) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. 2020.  Generative adversarial networks.  _Commun. ACM_ 63, 11 (2020), 139–144.
  * Guo et al. (2023) Zhimeng Guo, Jialiang Li, Teng Xiao, Yao Ma, and Suhang Wang. 2023.  Towards Fair Graph Neural Networks via Graph Counterfactual. In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM 2023, Birmingham, United Kingdom, October 21-25, 2023_ , Ingo Frommholz, Frank Hopfgartner, Mark Lee, Michael Oakes, Mounia Lalmas, Min Zhang, and Rodrygo L. T. Santos (Eds.). ACM, 669–678.  https://doi.org/10.1145/3583780.3615092
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ 30 (2017).
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro. 2016.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ 29 (2016).
  * Jiang et al. (2023) Zhimeng Jiang, Xiaotian Han, Hongye Jin, Guanchu Wang, Rui Chen, Na Zou, and Xia Hu. 2023.  Chasing Fairness Under Distribution Shift: A Model Weight Perturbation Approach. In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Jin et al. (2018) Wengong Jin, Regina Barzilay, and Tommi Jaakkola. 2018.  Junction tree variational autoencoder for molecular graph generation. In _International conference on machine learning_. PMLR, 2323–2332.
  * Johnson et al. (2009) Jeff Johnson, Donald M Truxillo, Berrin Erdogan, Talya N Bauer, and Leslie Hammer. 2009.  Perceptions of overall fairness: are effects on job performance moderated by leader-member exchange?  _Human Performance_ 22, 5 (2009), 432–449.
  * Jordan and Freiburger (2015) Kareem L Jordan and Tina L Freiburger. 2015.  The effect of race/ethnicity on sentencing: Examining sentence type, jail length, and prison length.  _Journal of Ethnicity in Criminal Justice_ 13, 3 (2015), 179–196.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net.  https://openreview.net/forum?id=SJU4ayYgl
  * Kusner et al. (2017) Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual fairness.  _Advances in neural information processing systems_ 30 (2017).
  * Li et al. (2022) Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. 2022.  Ood-gnn: Out-of-distribution generalized graph neural network.  _IEEE Transactions on Knowledge and Data Engineering_ (2022).
  * Li et al. (2021) Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. 2021.  On Dyadic Fairness: Exploring and Mitigating Bias in Graph Connections. In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.  https://openreview.net/forum?id=xgGS6PmzNq6
  * Li et al. (2023) Yibo Li, Xiao Wang, Hongrui Liu, and Chuan Shi. 2023.  A generalized neural diffusion framework on graphs.  _arXiv preprint arXiv:2312.08616_ (2023).
  * Ling et al. (2023) Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou. 2023.  Learning fair graph representations via automated data augmentations. In _The Eleventh International Conference on Learning Representations_.
  * Mandal et al. (2020) Debmalya Mandal, Samuel Deng, Suman Jana, Jeannette Wing, and Daniel J Hsu. 2020.  Ensuring fairness beyond the training data.  _Advances in neural information processing systems_ 33 (2020), 18445–18456.
  * Mehrabi et al. (2021) Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2021.  A survey on bias and fairness in machine learning.  _ACM Computing Surveys (CSUR)_ 54, 6 (2021), 1–35.
  * Newman (2006) Mark EJ Newman. 2006.  Modularity and community structure in networks.  _Proceedings of the national academy of sciences_ 103, 23 (2006), 8577–8582.
  * Pal and Mitra (1992) Sankar K Pal and Sushmita Mitra. 1992.  Multilayer perceptron, fuzzy sets, and classification.  _IEEE Transactions on neural networks_ 3, 5 (1992), 683–697.
  * Qi et al. (2018) Guo-Jun Qi, Liheng Zhang, Hao Hu, Marzieh Edraki, Jingdong Wang, and Xian-Sheng Hua. 2018.  Global versus localized generative adversarial nets. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 1517–1525.
  * Reddi et al. (2018) Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. 2018.  On the Convergence of Adam and Beyond. In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net.  https://openreview.net/forum?id=ryQu7f-RZ
  * Rezaei et al. (2021) Ashkan Rezaei, Anqi Liu, Omid Memarrast, and Brian D Ziebart. 2021.  Robust fairness under covariate shift. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 9419–9427.
  * Schumann et al. (2019) Candice Schumann, Xuezhi Wang, Alex Beutel, Jilin Chen, Hai Qian, and Ed H Chi. 2019.  Transfer of machine learning fairness across domains.  _arXiv preprint arXiv:1906.09688_ (2019).
  * Teich (2001) Jürgen Teich. 2001.  Pareto-front exploration with uncertain objectives. In _Evolutionary Multi-Criterion Optimization: First International Conference, EMO 2001 Zurich, Switzerland, March 7–9, 2001 Proceedings_. Springer, 314–328.
  * Tolan et al. (2019) Songül Tolan, Marius Miron, Emilia Gómez, and Carlos Castillo. 2019.  Why machine learning may lead to unfairness: Evidence from risk assessment for juvenile justice in catalonia. In _Proceedings of the Seventeenth International Conference on Artificial Intelligence and Law_. 83–92.
  * Van der Maaten and Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ 9, 11 (2008).
  * Wang et al. (2023) Pengfei Wang, Zhaoxiang Zhang, Zhen Lei, and Lei Zhang. 2023.  Sharpness-aware gradient matching for domain generalization. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 3769–3778.
  * Wang et al. (2022a) Ruijia Wang, Xiao Wang, Chuan Shi, and Le Song. 2022a.  Uncovering the Structural Fairness in Graph Contrastive Learning.  _Advances in Neural Information Processing Systems_ 35 (2022), 32465–32473.
  * Wang et al. (2017) Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. 2017.  Community preserving network embedding. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 31.
  * Wang et al. (2022b) Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr. 2022b.  Improving fairness in graph neural networks via mitigating sensitive attribute leakage. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 1938–1948.
  * Wu et al. (2022) Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. 2022.  Handling Distribution Shifts on Graphs: An Invariance Perspective. In _The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022_. OpenReview.net.  https://openreview.net/forum?id=FQOC5u-1egI
  * Yao and Huang (2017) Sirui Yao and Bert Huang. 2017.  Beyond parity: Fairness objectives for collaborative filtering.  _Advances in neural information processing systems_ 30 (2017).
  * Yeh and Lien (2009) I-Cheng Yeh and Che-hui Lien. 2009.  The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.  _Expert systems with applications_ 36, 2 (2009), 2473–2480.
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018.  Graph convolutional neural networks for web-scale recommender systems. In _Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining_. 974–983.
  * Yu et al. (2023b) Xingtong Yu, Zhenghao Liu, Yuan Fang, Zemin Liu, Sihong Chen, and Xinming Zhang. 2023b.  Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs.  _arXiv preprint arXiv:2311.15317_ (2023).
  * Yu et al. (2023a) Xingtong Yu, Zemin Liu, Yuan Fang, and Xinming Zhang. 2023a.  Learning to count isomorphisms with graph neural networks.  _arXiv preprint arXiv:2302.03266_ (2023).
  * Zeng et al. (2021) Ziqian Zeng, Rashidul Islam, Kamrun Naher Keya, James Foulds, Yangqiu Song, and Shimei Pan. 2021.  Fair representation learning for heterogeneous information networks. In _Proceedings of the International AAAI Conference on Web and Social Media_ , Vol. 15. 877–887.

##  Appendix A Proofs

###  A.1. Proof of Theorem 3.5

Theorem 3.5. For any $\delta\in(0,1)$, with probability greater than
$1-\delta$ and large enough feature dimension $\zeta$, we have:

(16)
$\displaystyle\eta_{y}^{2}\geq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1-2\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta
u^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2},$
$\displaystyle\eta_{y}^{2}\leq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1+4\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta
u^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2}.$

Proof.

To get the upper bound and lower bound of $\eta_{y}$, we introduce a function
$\eta(a,b)$ describing the aggregated feature difference between any two nodes
belonging to $\mathcal{V}_{1}$ and $\mathcal{V}_{0}$, i.e.,
$\eta(a,b)=||h_{a}-h_{b}||_{2}$, where $h_{a}$ and $h_{b}$ are aggregated
features of node $v_{a}\in\mathcal{V}_{1}$ and $v_{b}\in\mathcal{V}_{0}$,
respectively. So
$\eta_{y}=\max_{v_{a}\in\mathcal{V}_{1}^{y}}\min_{v_{b}\in\mathcal{V}_{0}^{y}}||h_{a}-h_{b}||_{2}$
equals $\eta(a,b)$ with specific $a$ and $b$. Thus we can bound $\eta_{y}$ by
bounding $\eta(a,b)$. As $\eta(a,b)=||h_{a}-h_{b}||_{2}$, we first give the
distribution of $(h_{a}-h_{b})$.

Recall that we assume $\mathbb{P}(x_{a}\mid
v_{a}\in\mathcal{V}_{1})\sim\mathcal{N}(\mu_{\mathcal{V}_{1}}\mathbf{I}_{\zeta},\sigma_{\mathcal{V}_{1}}^{2}\mathbf{I}_{\zeta})$
and $\mathbb{P}(x_{b}\mid
v_{b}\in\mathcal{V}_{0})\sim\mathcal{N}(\mu_{\mathcal{V}_{0}}\mathbf{I}_{\zeta},\sigma_{\mathcal{V}_{0}}^{2}\mathbf{I}_{\zeta})$.
As $h_{a}=\frac{1}{d_{a}+1}\sum_{j\in N_{a}\cup\\{v_{a}\\}}x_{j}$,
$h_{b}=\frac{1}{d_{b}+1}\sum_{j\in N_{b}\cup\\{v_{b}\\}}x_{j}$, $h_{a}$ and
$h_{b}$ follow the Gaussian distribution:

(17) $\displaystyle
h_{a}\sim\mathcal{N}(p_{a}\mu_{\mathcal{V}_{1}}+q_{a}\mu_{\mathcal{V}_{0}},(p_{a}\sigma_{\mathcal{V}_{1}}^{2}+q_{a}\sigma_{\mathcal{V}_{0}}^{2})\mathbf{I}_{\zeta}),$
$\displaystyle
h_{b}\sim\mathcal{N}(p_{b}\mu_{\mathcal{V}_{0}}+q_{b}\mu_{\mathcal{V}_{1}},(p_{b}\sigma_{\mathcal{V}_{0}}^{2}+q_{b}\sigma_{\mathcal{V}_{1}}^{2})\mathbf{I}_{\zeta}),$

where $p_{a}=\sum_{v_{j}\in
N_{a}\cup\\{v_{a}\\}}\frac{\mathbf{1}_{(f_{a}=f_{j})}}{d_{a}+1}$,
$q_{a}=\sum_{v_{j}\in N_{a}\cup\\{v_{a}\\}}\frac{\mathbf{1}_{(f_{a}\neq
f_{j})}}{d_{a}+1}$.

Then we have:

(18)
$h_{a}-h_{b}\sim\mathcal{N}((p-q)(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}),(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\mathbf{I}_{\zeta}).$

where $p=\mathbb{E}_{i\in\mathcal{V}}(p_{i})$,
$q=\mathbb{E}_{i\in\mathcal{V}}(q_{i})$. For the convenience of proof, we
transform the above distribution into the form of a standard Gaussian
distribution
$[h_{a}-h_{b}-(p-q)(\mu_{F_{1}}-\mu_{F_{0}})]\sim\mathcal{N}(0,(\sigma_{F_{1}}^{2}+\sigma_{F_{0}}^{2})\mathbf{I}_{\zeta})$.
Then we give the $l_{2}$ norm of this standard distribution and subsequently
analyze the range of it by Lemma A.1 and Corollary A.2.

$\displaystyle\quad||h_{a}-h_{b}-(p-q)(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})||^{2}_{2}$
$\displaystyle=||h_{a}-h_{b}||_{2}^{2}-2(p-q)(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})$
$\displaystyle\sum_{j}(h_{a}[j]-h_{b}[j])+\zeta(p-q)^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2}$
$\displaystyle=||h_{a}-h_{b}||_{2}^{2}-(p-q)(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})$
$\displaystyle\sum_{j}\left(2(h_{a}[j]-h_{b}[j])-(p-q)(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})\right)$
$\displaystyle\approx||h_{a}-h_{b}||_{2}^{2}-\zeta(p-q)^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2},$

where $h_{a}[j]$ is the $j$-th dimension of $h_{a}$. We then state the
following results on standard Gaussian distribution.

###### Lemma A.1.

(Laurent-Massart $\chi^{2}$ tail bound) Consider a standard Gaussian vector
$\mathbf{z}\sim\mathcal{N}(0,\mathbf{I}_{\zeta})$. For any positive vector
$\mathbf{a}\in\mathbb{R}_{\leq 0}^{\zeta}$, and any $t\leq 0$, the following
concentration holds.

(19)
$\begin{array}[]{r}\mathbb{P}\left[\sum_{i=1}^{\zeta}\mathbf{a}_{i}\mathbf{z}_{i}^{2}\geq\|\mathbf{a}\|_{1}+2\|\mathbf{a}\|_{2}\sqrt{t}+2\|\mathbf{a}\|_{\infty}t)\right]\leq\exp(-t),\\\
\mathbb{P}\left[\sum_{i=1}^{\zeta}\mathbf{a}_{i}\mathbf{z}_{i}^{2}\leq\|\mathbf{a}\|_{1}-2\|\mathbf{a}\|_{2}\sqrt{t}\right]\leq\exp(-t).\end{array}$

The following corollary immediately follows from using $t=\log(2/\delta)$ and
$\mathbf{a}_{i}=1$ in the above lemma.

###### Corollary A.2.

($\ell_{2}$ norm of Gaussian vector). Consider
$\mathbf{z}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{\zeta})$, for any
$\delta\in(0,1)$ and large enough $\xi$, with probability greater than
$1-\delta$, we have:

(20)
$\sigma^{2}\zeta\left(1-2\sqrt{\frac{\log(2/\delta)}{\zeta}}\right)\leq\|\mathbf{z}\|_{2}^{2}\leq\sigma^{2}\zeta\left(1+4\sqrt{\frac{\log(2/\delta)}{\zeta}}\right).$

As
$[h_{a}-h_{b}-(p-q)(\mu_{F_{1}}-\mu_{F_{0}})]\sim\mathcal{N}(0,(\sigma_{F_{1}}^{2}+\sigma_{F_{0}}^{2})\mathbf{I}_{\zeta})$,
with probability greater than $1-\delta$ and large enough $\zeta$, we have:

(21)
$\displaystyle(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1-2\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta(p-q)^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2}\leq||h_{a}-h_{b}||^{2}_{2}$
$\displaystyle\leq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1+4\sqrt{\frac{\log(2/\delta)}{\zeta}})+\zeta(p-q)^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2}.$

With $u=p-q$, we have:

(22)
$\displaystyle\eta_{y}^{2}\geq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1-2\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta
u^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2},$
$\displaystyle\eta_{y}^{2}\leq(\sigma_{\mathcal{V}_{1}}^{2}+\sigma_{\mathcal{V}_{0}}^{2})\zeta(1+4\sqrt{\frac{log(2/\delta)}{\zeta}})+\zeta
u^{2}(\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}})^{2}.$

This concludes the proof of the theorem.

###  A.2. Proof of Eq. (8)

(23) $\displaystyle\Delta_{EO}^{\mathcal{K}}-\Delta_{EO}^{\mathcal{J}}$
$\displaystyle=(|\mathbb{E}_{\mathcal{K}_{0}^{1}}-\mathbb{E}_{\mathcal{K}_{1}^{1}}|+|\mathbb{E}_{\mathcal{K}_{0}^{0}}-\mathbb{E}_{\mathcal{K}_{1}^{0}}|)-(|\mathbb{E}_{\mathcal{J}_{0}^{1}}-\mathbb{E}_{\mathcal{J}_{1}^{1}}|+|\mathbb{E}_{\mathcal{J}_{0}^{0}}-\mathbb{E}_{\mathcal{J}_{1}^{0}}|)$
$\displaystyle=(|\mathbb{E}_{\mathcal{K}_{0}^{1}}-\mathbb{E}_{\mathcal{K}_{1}^{1}}|-|\mathbb{E}_{\mathcal{J}_{0}^{1}}-\mathbb{E}_{\mathcal{J}_{1}^{1}}|)+(|\mathbb{E}_{\mathcal{K}_{0}^{0}}-\mathbb{E}_{\mathcal{K}_{1}^{0}}|-|\mathbb{E}_{\mathcal{J}_{0}^{0}}-\mathbb{E}_{\mathcal{J}_{1}^{0}}|)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left||\mathbb{E}_{\mathcal{K}_{0}^{1}}-\mathbb{E}_{\mathcal{K}_{1}^{1}}|-|\mathbb{E}_{\mathcal{J}_{0}^{1}}-\mathbb{E}_{\mathcal{J}_{1}^{1}}|\right|+\left||\mathbb{E}_{\mathcal{K}_{0}^{0}}-\mathbb{E}_{\mathcal{K}_{1}^{0}}|-|\mathbb{E}_{\mathcal{J}_{0}^{0}}-\mathbb{E}_{\mathcal{J}_{1}^{0}}|\right|$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\sum_{y,f}|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|,$

where inequality (a) and (b) hold due to $a-b\leq|a-b|$ and
$||a-b|-|a^{\prime}-b^{\prime}||\leq\left|a-a^{\prime}\right|+|b-b^{\prime}|$.

###  A.3. Proof of Theorem 3.6

Theorem 3.6. Consider an encoder $g:H\rightarrow
Z\in\mathbb{R}^{n\times\zeta^{\prime}}$ extracting
$\zeta^{\prime}$-dimensional representations $Z$ and an classifier
$\omega:Z\rightarrow C\in\mathbb{R}^{n\times 2}$ predicting the binary labels
of the nodes. Assume that $g$ and $\omega$ have $L_{1}$-Lipschitz and
$L_{2}$-Lipschitz continuity, respectively, then equalized odds is bounded by:

(24) $\Delta_{EO}\leq L_{1}L_{2}\dfrac{\sum_{y=0}^{1}\eta_{y}}{2}.$

Proof.

To characterize the relationship between $\mathcal{V}_{1}^{y}$ and
$\mathcal{V}_{0}^{y}$, we utilize a partition that can separate the nodes in
$\mathcal{V}_{0}^{y}$ into different sets $B_{y}^{(i)}$. Every node $v_{j}$ in
$B_{y}^{(i)}$ is near to a certain node $v_{i}\in\mathcal{V}_{1}^{y}$,
satisfying $||h_{i}-h_{j}||_{2}\leq\eta_{y}$. Obviously,
$\mathcal{V}_{0}^{y}=\cup_{v_{i}\in\mathcal{V}_{1}^{y}}B_{y}^{(i)}$. We have

(25) $\displaystyle\Delta_{EO}$
$\displaystyle=\dfrac{1}{2}\sum_{y=0}^{1}|\mathbb{E}_{i\in\mathcal{V}_{1}^{y}}(\hat{y_{i}}=y_{i})-\mathbb{E}_{j\in\mathcal{V}_{0}^{y}}(\hat{y_{j}}=y_{j})|$
$\displaystyle=\dfrac{1}{2}\sum_{y=0}^{1}|\mathbb{E}_{i\in\mathcal{V}_{1}^{y}}\omega\circ
g(h_{i})[y]-\mathbb{E}_{j\in\mathcal{V}_{0}^{y}}\omega\circ g(h_{j})[y]|$
$\displaystyle=\dfrac{1}{2}\sum_{y=0}^{1}\frac{1}{n_{\mathcal{V}_{1}^{y}}}\sum_{i\in\mathcal{V}_{1}^{y}}|\omega\circ
g(h_{i})[y]-\frac{1}{n_{B_{y}^{(i)}}}\sum_{j\in B_{y}^{(i)}}\omega\circ
g(h_{j})[y]|$
$\displaystyle=\dfrac{1}{2}\sum_{y=0}^{1}\frac{1}{n_{\mathcal{V}_{1}^{y}}}\sum_{i\in\mathcal{V}_{1}^{y}}\frac{1}{n_{B_{y}^{(i)}}}\sum_{j\in
B_{y}^{(i)}}\left|\omega\circ g(h_{i})[y]-\omega\circ g(h_{j})[y]\right|,$

where $\omega\circ g(h_{i})[y]$ is the $y$-th row of the vector $\omega\circ
g(h_{i})$.

As the nonliear transformation $g$ and classifier $\omega$ have
$L_{1}$-Lipschitz and $L_{2}$-Lipschitz continuity, then $|\omega\circ
g(h_{i})[y]-\omega\circ g(h_{j})[y]|=||\omega\circ g(h_{i})-\omega\circ
g(h_{j})||_{\infty}=\dfrac{1}{\sqrt{2}}||\omega\circ g(h_{i})-\omega\circ
g(h_{j})||_{2}\leq\dfrac{L_{2}}{\sqrt{2}}||g(h_{i})-g(h_{j})||_{2}\leq\dfrac{L_{1}L_{2}}{\sqrt{2}}||h_{i}-h_{j}||\leq\dfrac{L_{1}L_{2}}{\sqrt{2}}\eta_{y}$.
So $\Delta_{EO}\leq L_{1}L_{2}\dfrac{\sum_{y=0}^{1}\eta_{y}}{2\sqrt{2}}\leq
L_{1}L_{2}\dfrac{\sum_{y=0}^{1}\eta_{y}}{2}$.

###  A.4. Proof of Theorem 3.8

Theorem 3.8. Assume that the nonlinear transformation
$\omega(Z)=RELU(ZW_{\omega})$ has $L_{2}$-Lipschitz continuity, we have:

(26) $|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|\leq
L_{2}\epsilon_{f}^{y}.$

Then equalized odds difference between the training graph and the testing
graph can be bounded as:

(27) $\Delta_{EO}^{\mathcal{K}}-\Delta_{EO}^{\mathcal{J}}\leq
L_{2}\sum_{f,y}\epsilon_{f}^{y}.$

Proof.

To characterize the relationship between $\mathcal{K}_{f}^{y}$ and
$\mathcal{J}_{f}^{y}$, we utilize a partition that can separate the nodes in
$\mathcal{K}_{f}^{y}$ into different sets $R_{f,y}^{(i)}$. Every node $v_{j}$
in $R_{f,y}^{(i)}$ is near to a certain node $v_{i}\in\mathcal{J}_{f}^{y}$,
satisfying $||z_{i}-z_{j}||_{2}\leq\epsilon_{f}^{y}$. Obviously,
$\mathcal{K}_{f}^{y}=\cup_{v_{i}\in\mathcal{J}_{f}^{y}}R_{f,y}^{(i)}$. As
$\mathbb{E}_{\mathcal{J}_{f}^{y}}=\mathbb{E}_{v_{i}\in\mathcal{J}_{f}^{y}}(\omega(z_{i})[y])$,
$\mathbb{E}_{\mathcal{K}_{f}^{y}}=\mathbb{E}_{v_{i}\in\mathcal{K}_{f}^{y}}(\omega(z_{i})[y])$,
we have:

(28)
$\displaystyle|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|$
$\displaystyle=|\mathbb{E}_{i\in\mathcal{J}_{f}^{y}}(\hat{y_{i}}=y)-\mathbb{E}_{j\in\mathcal{K}_{f}^{y}}(\hat{y_{j}}=y)|$
$\displaystyle=|\mathbb{E}_{i\in\mathcal{J}_{f}^{y}}(\omega(z_{i})[y])-\mathbb{E}_{j\in\mathcal{K}_{f}^{y}}(\omega(z_{j})[y])|$
$\displaystyle=\dfrac{1}{n_{\mathcal{J}_{f}^{y}}}\sum_{i\in\mathcal{J}_{f}^{y}}\mid\omega(z_{i})[y]-\dfrac{1}{n_{R_{f,y}^{(i)}}}\sum_{j\in
R_{f,y}^{(i)}}\omega(z_{j})[y]\mid$
$\displaystyle=\dfrac{1}{n_{\mathcal{J}_{f}^{y}}}\sum_{i\in\mathcal{J}_{f}^{y}}\dfrac{1}{n_{R_{f,y}^{(i)}}}\sum_{j\in
R_{f,y}^{(i)}}|\omega(z_{i})[y]-\omega(z_{j})[y]|.$

As $\omega$ has $L_{2}$-Lipschitz continuity,
$|\omega(z_{i})[y]-\omega(z_{j})[y]|=||\omega(z_{i})-\omega(z_{j})||_{\infty}=\dfrac{1}{\sqrt{2}}||\omega(z_{i})-\omega(z_{j})||_{2}\leq\dfrac{1}{\sqrt{2}}L_{2}||z_{i}-z_{j}||\leq\dfrac{1}{\sqrt{2}}L_{2}\epsilon_{f}^{y}$.
Then

(29)
$|\mathbb{E}_{\mathcal{K}_{f}^{y}}-\mathbb{E}_{\mathcal{J}_{f}^{y}}|\leq\dfrac{1}{\sqrt{2}}L_{2}\epsilon_{f}^{y}\leq
L_{2}\epsilon_{f}^{y}.$

According to Eq. (8) and the above equation, we have:

(30) $\Delta_{EO}^{\mathcal{K}}-\Delta_{EO}^{\mathcal{J}}\leq
L_{2}\sum_{f,y}\epsilon_{f}^{y}.$

###  A.5. Minimization of $\Delta_{DP}^{\mathcal{K}}$

Similar to Theorem 3.8 which indicates that
$\Delta_{EO}^{\mathcal{K}}-\Delta_{EO}^{\mathcal{J}}\leq
L_{2}\sum_{f,y}\epsilon_{f}^{y}$, we can also prove that demographic parity
difference between the training graph and the testing graph can be bounded as:

(31) $\Delta_{DP}^{\mathcal{K}}-\Delta_{DP}^{\mathcal{J}}\leq
L_{2}\sum_{f}\gamma_{f},$

where $\gamma_{f}$ represents the sensitive group representation distance
between the training graph and the testing graphs. The proof is at the end of
A.5.

Figure 8. Illustration of minimization of $\Delta_{DP}^{\mathcal{K}}$.

Thus to minimize $\Delta_{DP}^{\mathcal{K}}-\Delta_{DP}^{\mathcal{J}}$, we
have to minimize $\sum_{f}\gamma_{f}$. FatraGNN utilizes the alignment module
to minimize $\sum_{f,y}\epsilon_{f}^{y}$, then we show that
$\sum_{f}\gamma_{f}$ can also be minimized at the same time. For better
illustration, we draw Figure 8. In Figure 8, all solid circles represent sets
of nodes with a certain sensitive attribute and label, such as
$\mathcal{J}_{0}^{1}$ denoting nodes in the training graph with the sensitive
attribute 0 and label 1, and $\mathcal{K}_{0}^{1}$ denoting nodes in the
testing graphs with the sensitive attribute 0 and label 1. We encircle nodes
with the same sensitive attribute in the training graph and testing graphs
with blue and orange circles, separately. For example, $\mathcal{J}_{0}$
represents nodes with sensitive attribute 0 in the training graph, and
$\mathcal{K}_{0}$ represents nodes with sensitive attribute 0 in the testing
graphs. Assuming that nodes with the same label have more similar
representations, then the representation distance from $\mathcal{J}_{0}^{0}$
to $\mathcal{K}_{0}$ is the same as the distance from $\mathcal{J}_{0}^{0}$ to
$\mathcal{K}_{0}^{0}$ ($\epsilon_{0}^{0}$), and the representation distance
from $\mathcal{J}_{0}^{1}$ to $\mathcal{K}_{0}$ is the same as the distance
from $\mathcal{J}_{0}^{1}$ to $\mathcal{K}_{0}^{1}$ ($\epsilon_{0}^{1}$). Thus
the representation distance from $\mathcal{J}_{0}$ to $\mathcal{K}_{0}$ is
denoted as $\gamma_{0}=\max(\epsilon_{0}^{0},\epsilon_{0}^{1})$. Therefore,
minimizing $\sum_{f,y}\epsilon_{f}^{y}$ can minimize $\sum_{f}\gamma_{f}$ at
the same time.

Proof of Eq. (31):

The proof is similar to the proof of Theorem 3 in the Appendix. First, we
characterize the difference of $\Delta_{DP}$ between the training graph and
testing graphs, denoted as
$\Delta_{DP}^{\mathcal{J}}-\Delta_{DP}^{\mathcal{K}}$, by analyzing the
accuracy difference between the training graph and testing graphs of each
sensitive group.

$\displaystyle\Delta_{DP}^{\mathcal{K}}-\Delta_{DP}^{\mathcal{J}}$
$\displaystyle=|\mathbb{E}_{\mathcal{K}_{0}}-\mathbb{E}_{\mathcal{K}_{1}}|-|\mathbb{E}_{\mathcal{J}_{0}}-\mathbb{E}_{\mathcal{J}_{1}}|$
$\displaystyle\leq||\mathbb{E}_{\mathcal{K}_{0}}-\mathbb{E}_{\mathcal{K}_{1}}|-|\mathbb{E}_{\mathcal{J}_{0}}-\mathbb{E}_{\mathcal{J}_{1}}||$
$\displaystyle\leq|\mathbb{E}_{\mathcal{K}_{0}}-\mathbb{E}_{\mathcal{J}_{0}}|+|\mathbb{E}_{\mathcal{K}_{1}}-\mathbb{E}_{\mathcal{J}_{1}}|$
$\displaystyle=\sum_{f}|\mathbb{E}_{\mathcal{K}_{f}}-\mathbb{E}_{\mathcal{J}_{f}}|.$

We then define sensitive group representation distance between the training
graph and testing graphs in Definition and build a relationship between the
representation distance and
$|\mathbb{E}_{\mathcal{K}_{f}}-\mathbb{E}_{\mathcal{J}_{f}}|$.

$\gamma_{f}=\max_{v_{j}\in\mathcal{K}_{f}}\min_{v_{i}\in\mathcal{J}_{f}}||z_{i}-z_{j}||_{2}$

To characterize the relationship between $\mathcal{K}_{f}$ and
$\mathcal{J}_{f}$, we utilize a partition that can separate the nodes in
$\mathcal{K}_{f}$ into different sets $R_{f}^{(i)}$. Every node $v_{j}$ in
$R_{f}^{(i)}$ is near to a certain node $v_{i}\in\mathcal{J}_{f}$, satisfying
$||z_{i}-z_{j}||_{2}\leq\epsilon_{f}$. Obviously,
$\mathcal{K}_{f}=\cup_{v_{i}\in\mathcal{J}_{f}}R_{f}^{(i)}$. As
$\mathbb{E}_{\mathcal{J}_{f}^{y}}=\mathbb{E}_{v_{i}\in\mathcal{J}_{f}}(\omega(z_{i})[y])$,
$\mathbb{E}_{\mathcal{K}_{f}}=\mathbb{E}_{v_{i}\in\mathcal{K}_{f}}(\omega(z_{i})[y])$,
we have:

$\displaystyle|\mathbb{E}_{\mathcal{K}_{f}}-\mathbb{E}_{\mathcal{J}_{f}}|$
$\displaystyle=|\mathbb{E}_{i\in\mathcal{J}_{f}}(\hat{y_{i}}=y)-\mathbb{E}_{j\in\mathcal{K}_{f}}(\hat{y_{j}}=y)|$
$\displaystyle=|\mathbb{E}_{i\in\mathcal{J}_{f}}(\omega(z_{i})[y])-\mathbb{E}_{j\in\mathcal{K}_{f}}(\omega(z_{j})[y])|$
$\displaystyle=\dfrac{1}{n_{\mathcal{J}_{f}}}\sum_{i\in\mathcal{J}_{f}}\mid\omega(z_{i})[y]-\dfrac{1}{n_{R_{f}^{(i)}}}\sum_{j\in
R_{f}^{(i)}}\omega(z_{j})[y]\mid$
$\displaystyle=\dfrac{1}{n_{\mathcal{J}_{f}}}\sum_{i\in\mathcal{J}_{f}}\dfrac{1}{n_{R_{f}^{(i)}}}\sum_{j\in
R_{f}^{(i)}}|\omega(z_{i})[y]-\omega(z_{j})[y]|.$

As $\omega$ has $L_{2}$-Lipschitz continuity,
$|\omega(z_{i})[y]-\omega(z_{j})[y]|=||\omega(z_{i})-\omega(z_{j})||_{\infty}=\dfrac{1}{\sqrt{2}}||\omega(z_{i})-\omega(z_{j})||_{2}\leq\dfrac{1}{\sqrt{2}}L_{2}||z_{i}-z_{j}||\leq\dfrac{1}{\sqrt{2}}L_{2}\gamma_{f}$.
Then

$|\mathbb{E}_{\mathcal{K}_{f}}-\mathbb{E}_{\mathcal{J}_{f}}|\leq\dfrac{1}{\sqrt{2}}L_{2}\gamma_{f}\leq
L_{2}\gamma_{f},$

we have:

$\Delta_{DP}^{\mathcal{K}}-\Delta_{DP}^{\mathcal{J}}\leq\dfrac{1}{\sqrt{2}}L_{2}\sum_{f}\gamma_{f}.$

##  Appendix B Reproducibility Information

###  B.1. Dataset Statistics

We use Bail-Bs, Credit-Cs, Pokecs, sync-B1s, and sync-B2s to evaluate our
model as described in Section 2. The modularity-based community detection
method we used to partition Bail (Jordan and Freiburger, 2015) and Credit (Yeh
and Lien, 2009) is provided by Gephi. For each training graph in each dataset,
we randomly choose 50% nodes for training and 25% nodes for validation. And we
use all the nodes in all the testing graphs for testing. The statistics of
Bail-Bs, Credit-Cs, Pokecs are shown in Table 3, Table 4, and Table 5.

To observe the data distribution of different datasets, we calculate
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ for each dataset. As indicated
in Theorem 3.6 of our paper, one of the factors influencing $\Delta_{EO}$ is
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$, and graphs with different
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ will lead to different fairness
performances. As we mainly focus on the fairness performance under different
distributions, we utilize $\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ to
capture distribution shifts in terms of fairness. As can be seen in Table 3,
Table 4, and Table 5, the training graph and testing graphs in Bail-Bs,
Credit-Cs, and Pokecs have different values of
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$, indicating that the training
graph and testing graphs are under different data distributions.

As can be seen from the table, the mu values of different datasets vary,
indicating that their data distributions are distinct. We observe nodes in
different communities exhibit some differences.

sync-B1s contains a training graph B0 and thirty testing graphs with different
$u$. sync-B2s contains a training graph B0 and thirty testing graphs with
different $u$.

All the datasets can be found in
https://anonymous.4open.science/r/FatraGNN-118F.

Table 3.  Bail-Bs statistics.  dataset | B0 | B1 | B2 | B3 | B4
---|---|---|---|---|---
Nodes | 4686 | 2214 | 2395 | 1536 | 1193
Edges | 153942 | 49124 | 88091 | 57838 | 30319
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ | 0.1692 | 0.2224 | 0.2055 | 0.0297 | 0.2442
Features | 18
Sensitive attribute | Race
Label | Bail/no bail
Table 4.  Credit-Cs statistics.  dataset | C0 | C1 | C2 | C3 | C4
---|---|---|---|---|---
Nodes | 4184 | 2541 | 3796 | 2068 | 3420
Edges | 45718 | 18949 | 28936 | 15314 | 26048
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ | 0.2611 | 0.2832 | 0.4052 | 0.4413 | 0.4766
Features | 13
Sensitive attribute | Age
Label | High/low risk
Table 5.  Pokecs statistics.  dataset | Pokec-z | Pokec-n
---|---|---
Nodes | 67,796 | 66,569
Edges | 1,303,712 | 1,100,663
$\mu_{\mathcal{V}_{1}}-\mu_{\mathcal{V}_{0}}$ | 1.0942 | 1.2074
Features | 265
Sensitive attribute | Region
Label | Working field

###  B.2. Baselines

The publicly available implementations of Baselines can be found at the
following URLs:

  * •

GCN: (MIT license) https://github.com/tkipf/gcn

  * •

MLP: (MIT license) https://github.com/xmu-xiaoma666/External-Attention-
pytorch/tree/master/model/mlp

  * •

FairVGNN: (MIT license) https://github.com/YuWVandy/FairVGNN

  * •

NIFTY: (MIT license) https://github.com/chirag126/nifty/tree/main

  * •

EDITS: (MIT license) https://github.com/yushundong/EDITS

  * •

EERM: (MIT license) https://github.com/qitianwu/GraphOOD-EERM

###  B.3.  Operating Environment

  * •

Operating system: Linux version 3.10.0-693.el7.x86_64

  * •

CPU information: Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz

  * •

GPU information: GeForce RTX 3090

###  B.4. Inplementation Details

We use Pytorch to implement FatraGNN, for other baselines, we utilize the
original codes from their authors and train the models in an end-to-end way.
For all the models, we first train each model on the training graph with
careful finetune, and then we test the performance of classification and
fairness on the testing graphs. In each training iteration, we performed five
training steps, including training the discriminator to discriminate the
sensitive attribute, training the encoder to deceive the discriminator,
training the encoder and classifier to ensure accuracy, training the feature
generator to generate features, and training the encoder to obtain similar
representations. The respective numbers of iterations for these steps were
denoted as T1, T2, T3, T4, and T5. For the proposed FatraGNN, we search on
epoch number T ranging from {400, 600}. For T1, T2, T3, T4, and T5, we test
them ranging from {2, 5}, {8, 10, 12}, {5, 8}, {2, 5, 8}, {2, 5},
respectively. For the learning rate of the feature generator, discriminator,
classifier, and encoder, we test them from {0.001, 0.005, 0.01, 0.05}. In
order to get a bunch of modified graphs, we modify the structure of the
training graph by randomly removing and adding the same number of edges. Every
10 epochs we choose one modified graph for training. For fair comparisons, we
randomly run 5 times and report the average results for all methods. The code
of FatraGNN can be found in https://anonymous.4open.science/r/FatraGNN-118F.

###  B.5. Hyperparameter Setting

We implement FatraGNN in PyTorch, and list some important parameter values in
our model in Table 6. We use Adam (Reddi et al., 2018) as the optimizer for
encoder $\rho$, discriminator $\xi$, feature generator $\Gamma$, and
classifier $\omega$ with different learning rates.

Table 6. Hyperparameter Setting | T | T1 | T2 | T3 | T4 | T5 |  $\Gamma$ lr |  $\xi$ lr |  $\omega$ lr |  $\rho$ lr
---|---|---|---|---|---|---|---|---|---|---
credit | 600 | 5 | 5 | 12 | 5 | 2 | 0.05 | 0.001 | 0.01 | 0.005
bail | 400 | 5 | 5 | 12 | 8 | 5 | 0.05 | 0.001 | 0.005 | 0.005
pokec | 400 | 2 | 5 | 10 | 2 | 5 | 0.05 | 0.001 | 0.01 | 0.01

##  Appendix C Additional Results

Figure 9. Loss versus epoch curve of the feature generator, the discriminator,
and the classifier on Credit with five different sets of randomly chosen
hyperparameters and random seeds.

###  C.1. Results on Credit-Cs

Table 7 shows classification and fairness performance on Credit-Cs.

Table 7.  Classification and fairness performance (%$\pm\sigma$) on Credit-Cs. $\uparrow$ denotes the larger, the better; $\downarrow$ denotes the opposite. Best ones are in bold. | metric | MLP | GCN | FairVGNN | NIFTY | EDITS | EERM | CAF | SAGM | RFR | FatraGNN (ours)
---|---|---|---|---|---|---|---|---|---|---|---
C1 | ACC$\uparrow$ | 75.69$\pm 5.64$ | 76.69$\pm 2.48$ | 77.45$\pm 0.31$ | 77.51$\mathbf{\pm 0.03}$ | 77.06$\pm 0.03$ | 77.04$\pm 0.09$ | 76.54$\pm 0.81$ | 77.16 $\pm 0.45$ | 76.83$\pm 1.26$ | 77.31$\pm 0.1$
ROC-AUC$\uparrow$ | 64.38$\pm 0.47$ | 65.54$\pm 1.43$ | 67.07$\pm 0.4$ | 68.43$\mathbf{\pm 0.25}$ | 65.25$\pm 1.29$ | 66.54$\pm 1.37$ | 67.58$\pm 1.36$ | 65.35$\pm 1.03$ | 66.08$\pm 0.81$ | 65.41$\pm 1.28$
$\Delta_{DP}\downarrow$ | 5.2$\pm 14.92$ | 7.4$\pm 6.69$ | 1$\pm 0.63$ | 4.34$\pm 0.03$ | 2.43$\pm 0.03$ | 5.46$\pm 0.38$ | 5.61$\pm 0.84$ | 5.21$\pm 0.76$ | 3.46$\pm 0.98$ | 0.5$\mathbf{\pm 0.21}$
$\Delta_{EO}\downarrow$ | 7.92$\pm 15.86$ | 6.31$\pm 6$ | 0.85$\pm 0.2$ | 2.73$\pm 0.04$ | 3.24$\pm 0.03$ | 6.47$\pm 0.26$ | 5.03$\pm 1.49$ | 4.58$\pm 0.68$ | 3.19$\pm 0.73$ | 0.71$\mathbf{\pm 0.03}$
C2 | ACC$\uparrow$ | 72.05$\pm 2.6$ | 75.42 $\pm 0.44$ | 75.49$\pm 1.7$ | 74.44$\pm 0.47$ | 77.07$\pm 0.22$ | 76.16$\pm 0.91$ | 75.49$\pm 0.82$ | 76.38$\pm 0.91$ | 75.24$\pm 0.68$ | 77.12$\mathbf{\pm 0.28}$
ROC-AUC$\uparrow$ | 62.36$\pm 6.29$ | 63.76$\pm 3.07$ | 63.8$\pm 0.25$ | 60.63$\pm 10.06$ | 62.5$\pm 3.27$ | 65.49$\pm 2.39$ | 62.36$\pm 1.18$ | 62.65$\pm 0.89$ | 61.35$\pm 0.92$ | 64.16$\mathbf{\pm 0.69}$
$\Delta_{DP}\downarrow$ | 8.14$\pm 4.39$ | 8.74$\pm 3.6$ | 3.54$\pm 0.42$ | 3.54$\pm 1.6$ | 2.98$\pm 0.01$ | 4.22$\pm 1.38$ | 3.61$\pm 0.74$ | 5.34$\pm 0.67$ | 2.35$\pm 0.39$ | 1.64$\mathbf{\pm 1.06}$
$\Delta_{EO}\downarrow$ | 6.7$\pm 4.3$ | 7.35$\pm 2.64$ | 2.63$\pm 0.61$ | 2.34$\pm 0.63$ | 3.65$\pm 0.16$ | 5.71$\pm 1.1$ | 3.57$\pm 0.89$ | 4.37$\pm 0.98$ | 2.96$\pm 0.81$ | 0.95$\mathbf{\pm 0.7}$
C3 | ACC$\uparrow$ | 68.15$\pm 0.16$ | 70.31$\pm 1.79$ | 71.49$\pm 0.56$ | 70.11$\pm 0.04$ | 70.89$\pm 0.96$ | 71.43$\pm 1.24$ | 71.28$\pm 1.35$ | 70.83$\pm 0.65$ | 70.03$\pm 0.48$ | 71.81$\mathbf{\pm 0.39}$
ROC-AUC$\uparrow$ | 64.64$\pm 4.49$ | 65.90$\pm 1.72$ | 65.96$\mathbf{\pm 0.19}$ | 64.75$\pm 0.14$ | 63.18$\pm 2.53$ | 65.36$\pm 1.03$ | 64.37$\pm 1.06$ | 64.52$\pm 0.91$ | 63.59$\pm 0.63$ | 65.7$\pm 0.91$
$\Delta_{DP}\downarrow$ | 8.7$\pm 0.12$ | 9.46$\pm 10.06$ | 3.05$\pm 1.76$ | 3.54$\pm 0.07$ | 3.22$\pm 0.45$ | 5.63$\pm 9.43$ | 5.28$\pm 0.94$ | 5.12$\pm 1.36$ | 2.86$\pm 1.25$ | 0.25$\mathbf{\pm 0.2}$
$\Delta_{EO}\downarrow$ | 9.47$\pm 0.03$ | 9.71$\pm 8.29$ | 3.35$\pm 2.46$ | 2.23$\pm 0.08$ | 1.87$\pm 0.36$ | 5.34$\pm 4.62$ | 4.82$\pm 1.33$ | 5.57$\pm 0.79$ | 3.41$\pm 0.89$ | 0.81$\mathbf{\pm 0.56}$
C4 | ACC$\uparrow$ | 68.26$\pm 3.09$ | 70.89$\pm 5.38$ | 71.74$\pm 0.45$ | 71.84$\pm 6.36$ | 71.28$\pm 0.2$ | 71.35$\pm 4.28$ | 71.48$\pm 0.81$ | 71.22$\pm 0.29$ | 71.47$\pm 0.92$ | 72.15$\mathbf{\pm 0.42}$
ROC-AUC$\uparrow$ | 65.32$\pm 4.42$ | 64.28$\pm 3.45$ | 66.45$\pm 1.61$ | 66.98$\pm 2.3$ | 63.45$\pm 0.6$ | 64.04$\pm 0.67$ | 66.59$\pm 1.24$ | 63.45$\pm 0.88$ | 65.27$\pm 0.68$ | 67.66$\mathbf{\pm 0.87}$
$\Delta_{DP}\downarrow$ | 7.46$\pm 12.08$ | 6.13$\pm 4.08$ | 3.46$\pm 0.05$ | 7.84$\pm 9.64$ | 3.42$\pm 0.47$ | 4.35$\pm 0.85$ | 3.73$\pm 0.92$ | 5.46$\pm 1.18$ | 3.59$\pm 0.41$ | 0.61$\mathbf{\pm 0.08}$
$\Delta_{EO}\downarrow$ | 6.61$\pm 11.22$ | 8.16$\pm 2.38$ | 2.82$\pm 0.19$ | 2.18$\pm 9.91$ | 3.22$\pm 0$ | 5.07$\pm 0.74$ | 4.18$\pm 0.85$ | 5.34$\pm 0.22$ | 2.46$\pm 0.87$ | 1.16$\mathbf{\pm 0.13}$
| rank | 10 | 9 | 2 | 4 | 3 | 7 | 6 | 8 | 5 | 1

###  C.2. Trade-off on Pokecs

The accuracy-fairness trade-off of fairness baselines and FatraGNN on Pokec is
shown in Figure 10.

Figure 10. Trade-off of ACC and $\Delta_{EO}$ on the testing graph of Pokec.
Upper-left corner (high accuracy, low $\Delta_{EO}$) is preferred. Figure 11.
The hyperparameter sensitivity of FatraGNN with varying generated graph
numbers.

###  C.3. Analysis of the Adversarial Module

We do experiments on Credit-Cs with five different sets of randomly chosen
hyperparameters and random seeds and plot the loss versus epoch curve of the
feature generator, the discriminator, and the classifier on Credit-Cs. As
shown in Figure 9, the amplitude of loss gradually decreases as the number of
epochs rises, indicating that it is actually not difficult to tune the
parameters to achieve convergence and FatraGNN is not that susceptible to
instability under varying random seeds.

###  C.4. Analysis of the Representation Differences between the Training
Graph and Testing Graphs

In order to plot the representations of the training graph and testing graphs
of Bail-Bs using t-SNE (Van der Maaten and Hinton, 2008), we first obtain the
representation matrices of the training graph and testing graphs. Then we
concatenate them into a single matrix and apply the same transformation to
obtain a new two-dimensional matrix. Then, we separate these matrices
corresponding to the original graphs. For each graph, we plot the node
representations in one figure, with different colors indicating nodes
belonging to different EO groups. As shown in Figure 12, the representations
of nodes belonging to the same EO group on the training graph and testing
graphs are close. This indicates that by minimizing the representation
difference between the training graph and the testing graphs, the alignment
module of our model can ensure the proximity of representations of the same EO
group between the training graph and testing graphs, thereby guaranteeing
fairness and accuracy on the testing graphs. We also propose an alignment
score
$\sum_{f,y}\mathbb{E}_{i\in\mathcal{J}_{f}^{y},j\in\mathcal{K}_{f}^{y}}\dfrac{(z_{i}z_{j})}{||z_{i}||\cdot||z_{j}||}$
to measure the alignment of the training graph and the testing graphs. The
alignment scores between B0 and B1, B2, B3, and B4 are 3.89, 3.88, 3.81, and
3.86, respectively. However, when the generation module and alignment module
are excluded, the alignment scores experience a decrease, measuring 3.85,
3.85, 3.73, and 3.83. This demonstrates the capacity of the generation and
alignment modules to facilitate the encoder in learning similar
representations for the same EO group between the training and testing graphs.

Figure 12. Visualization of the representations of the training graph and
testing graphs.

###  C.5. Hyperparameter Study

We investigate the impact of epochs used in each training step. Figure 13
shows the overall score of FatraGNN on the Bail-Bs dataset. We can see that
the performance benefits from an applicable selection of each epoch.
Specifically, when T1 and T2 are set to small values, the adversarial module
fails to guide the encoder in learning indistinguishable representations for
sensitive groups. Similarly, a small T3 hinders the classifier’s ability to
effectively classify the nodes. In addition, a small T4 limits the generator’s
capacity to generate features that may lead to unfairness. Lastly, a small T5
prevents the alignment module from facilitating the encoder in learning
similar representations for the initial graph and the generated graph,
resulting in unfairness.

As we modify the graph structure to get graphs with different $u$ by adding
and removing the edges of the graph, we also explore the impact of the edge
modification ratio. As shown in Figure 14, we observe that FatraGNN achieves
better performance when the ratio is around 0.5. Conversely, when the edge
modification ratio is either too small or too large, FatraGNN’s performance
deteriorates. A small edge modification ratio results in little structural
change in the generated graph, making it challenging for FatraGNN to adapt to
testing graphs with different $u$. On the other hand, a large edge
modification ratio leads to substantial changes in the graph structure and may
disrupt the original information, making it difficult for FatraGNN to learn
meaningful patterns.

Additionally, to investigate the optimal number of generated graphs, we keep
other parameters fixed and vary the number of generated graphs utilized during
training on Bail-Bs. As shown in Figure 11, the training process yields better
results when the number of generated graphs reaches 40.

Figure 13. The hyperparameter sensitivity of FatraGNN with varying epoch
numbers of each training step. Figure 14. The hyperparameter sensitivity of
FatraGNN with varying modification rates.

##  Appendix D Related Work

OOD Generalization on Graphs (Li et al., 2022) proposes a novel out-of-
distribution generalized graph neural network to solve the problem of
generalization of GNNs under complex and heterogeneous distribution shifts.
(Wu et al., 2022) focuses on out-of-distribution generalization for node-level
problems and aims GNNs to minimize the mean and variance of risks from data
with different distributions simulated by adversarial context generators.
Although these works can release the problem of classification performance
deterioration under distribution shifts, they may lead to unfairness.