# Enhancing Fairness in Unsupervised Graph Anomaly Detection through
Disentanglement

Wenjing Chang  Computer Network Information Center, CAS and University of
Chinese Academy of SciencesBeijingChina<EMAIL_ADDRESS>,  Kay Liu
University of Illinois Chicago801 S Morgan StChicagoIllinoisUSA60607
<EMAIL_ADDRESS>,  Philip S. Yu  University of Illinois Chicago801 S Morgan
StChicagoIllinoisUSA60607<EMAIL_ADDRESS>and  Jianjun Yu  Computer Network
Information Center, CASBeijingChina<EMAIL_ADDRESS>
(2024)

###### Abstract.

Graph anomaly detection (GAD) is becoming increasingly crucial in various
applications, ranging from financial fraud detection to fake news detection.
However, current GAD methods largely overlook the issue of fairness, which
might result in discriminatory decisions skewed toward certain demographic
groups defined on sensitive attributes (e.g., gender, religion, ethnicity,
etc.). This greatly limits the applicability of these methods in real-world
scenarios in light of societal and ethical restrictions. To address this
critical gap, we make the first attempt to integrate fairness with utility in
GAD decision-making. Specifically, we devise a novel DisEntangle-based
FairnEss-aware aNomaly Detection framework on the attributed graph, named
DEFEND. DEFEND first introduces disentanglement in GNNs to capture informative
yet sensitive-irrelevant node representations, effectively reducing societal
bias inherent in graph representation learning. Besides, to alleviate
discriminatory bias in evaluating anomalous nodes, DEFEND adopts a
reconstruction-based anomaly detection, which concentrates solely on node
attributes without incorporating any graph structure. Additionally, given the
inherent association between input and sensitive attributes, DEFEND constrains
the correlation between the reconstruction error and the predicted sensitive
attributes. Our empirical evaluations on real-world datasets reveal that
DEFEND performs effectively in GAD and significantly enhances fairness
compared to state-of-the-art baselines. To foster reproducibility, our code is
available at https://github.com/AhaChang/DEFEND.

Graph Anomaly Detection, Fairness, Graph Neural Networks

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXX††isbn:
978-1-4503-XXXX-X/18/06††ccs: Mathematics of computing Graph algorithms††ccs:
Security and privacy Software and application security

##  1\. Introduction

Graph Anomaly Detection (GAD), which aims to identify nodes that deviate
significantly from the majority of nodes, has attracted wide attention in
various domains, including fraudster detection in financial networks (Zhang et
al., 2022; Huang et al., 2022) and spammer detection in social networks (Li et
al., 2019; Wu et al., 2020). The advancement of Graph Neural Networks (GNNs)
(Kipf and Welling, 2016; Hamilton et al., 2017; Veličković et al., 2017) has
significantly propelled the development of GNN-based GAD methods (Ding et al.,
2019; Chai et al., 2022; Kim et al., 2023; He et al., 2023), enhancing their
ability to accurately identify anomalies on graphs.

Given the wide-ranging applications of graph anomaly detection, particularly
within high-stakes domains, its fairness cannot be overlooked. Specifically,
unfair decisions that skew toward certain demographic groups associated with
sensitive attributes (e.g., gender, religion, and ethnicity) might cause
profound societal and ethical concerns. For example, in the realm of social
networks (e.g., Reddit and Twitter), anomalous users (e.g., spreading
misinformation or engaging in fake account interactions) might be subjected to
strict investigation and even permanent account suspension. In such scenarios,
biased decisions could result in disproportionately targeting certain groups
while inadvertently neglecting others. This undermines the effectiveness and
reliability of anomaly detection systems and raises critical ethical concerns.
To address the issues above, several fairness-aware anomaly detection methods
have been proposed (Deepak and Abraham, 2020; Song et al., 2021; Zhang and
Davidson, 2021; Shekhar et al., 2021), aiming to balance fairness and utility
in anomaly detection. However, these methods predominantly focus on
independent and identically distributed (i.i.d.) data, failing to account for
the societal bias in graph data.

Societal bias within graph data poses a significant challenge to achieving
fairness in graph learning tasks (Dai and Wang, 2021; Zhu et al., 2023). The
bias manifests not only in node attributes but also in the topological
structure of the graph. From one aspect, sensitive attributes are likely
inherently spread across other attributes (e.g., the geographic location might
be correlated with religion and ethnicity) (Deepak and Abraham, 2020).
Moreover, since nodes with similar attributes are more likely to form
connections, the graph topology is actually influenced by sensitive attributes
(Rahman et al., 2019; Spinelli et al., 2021). Additionally, recent studies
(Dai and Wang, 2021; Wang et al., 2022; Zhu et al., 2023) have demonstrated
that the biased topology coupled with the message-passing mechanism in GNNs
may inherit or even amplify the inherent societal bias in graphs. More
specifically, aggregating features from neighboring nodes that share identical
sensitive attributes may result in representations that amplify the features
of the demographic group. Consequently, such homogeneous representations can
potentially affect the fairness of the decision-making process in GNNs.

Over the past years, many existing works have explored fairness in graphs for
GNN-based methods (Li et al., 2021; Ma et al., 2022; Kim et al., 2022; Song et
al., 2022). A common strategy involves eliminating sensitive information from
the training graph and implementing the debiased graph for the target tasks
(Spinelli et al., 2021; Rahman et al., 2019; Dong et al., 2022). In this
manner, the debiased graph is expected to retain less potentially sensitive
information while preserving all non-sensitive characteristics. However, the
efficacy of such debiasing techniques in GAD tasks is not yet fully
established. A primary concern is the potential overlap between
characteristics of anomalies associated with nonsensitive attributes and those
of demographic groups linked to sensitive attributes. For instance, an edge
might indicate that nodes share the same sensitive attributes while displaying
anomalous behavior. This overlap poses a challenge in concurrently mitigating
bias and preserving the integrity of anomalies. Another prevalent strategy
involves training fair GNNs to perform the target tasks in a way that is
independent of sensitive attributes (Dai and Wang, 2021; Zhu et al., 2023).
These methods are dedicated to end-to-end supervised node classification,
where target labels are available during training. Therefore, directly
applying them to unsupervised graph anomaly detection is challenging,
primarily due to the absence of ground truth labels that indicate whether a
node is anomalous.

As an alternative, fair representation learning has been proposed to learn
representations free from sensitive attributes while maintaining essential
information for decision-making in downstream tasks (Zemel et al., 2013; Liu
et al., 2022b). Disentangled representation learning provides a novel
perspective in fair representation learning, enabling the simultaneous
maintenance of sensitive-relevant and irrelevant information, which are
separated into independent subspaces. While disentangled fair representation
learning has shown promise in benefiting fairness in image classification
tasks (Creager et al., 2019; Kim et al., 2021; Oh et al., 2022), its
applicability on unsupervised graph anomaly detection is non-trivial.
Different from the i.i.d. image data, graph data contains complex
interrelations between nodes, which are represented in the graph topology. The
first challenge involves effectively encoding both the attributes of nodes and
the topology of the graph into a disentangled i.i.d. node representation while
preserving the information essential for anomaly detection. Furthermore, an
additional challenge lies in achieving fair anomaly detection with obtained
fair representation. In prior studies, disentangled fair representation is
used for supervised downstream tasks. However, we focus on unsupervised
anomaly detection, which relies on reconstruction error to make the decision.
Considering the correlation between sensitive attributes and other attributes,
as well as the connections influenced by sensitive attributes, direct
reconstruction of the original graph may result in biased decisions.

In this paper, we propose a novel DisEntangle-based FairnEss-aware aNomaly
Detection framework on the attributed graph, named DEFEND. We first introduce
disentangled fair representation learning on graphs to capture node
representations that are both informative and independent of sensitive
attributes. Specifically, the disentangled graph encoder can effectively
separate sensitive-relevant and -irrelevant node representations into
independent subspaces with the guidance of a learnable adversary. To alleviate
discriminatory bias in detecting anomalous nodes, we deploy an additional
decoder that reconstructs node attributes from the well-trained disentangled
encoder. Given the inherent bias in graph topology, anomaly detection relies
solely on node attributes. Furthermore, to mitigate the effect of the
interrelation between raw node attributes and sensitive attributes, we
introduce a fairness constraint, ensuring the reconstruction error remains
invariant to the predicted sensitive attributes.

In summary, the main contributions of this paper are as follows:

  * •

To the best of our knowledge, we proposed the first method DEFEND for fair
unsupervised graph anomaly detection, which reduces discriminatory bias in
anomaly detection.

  * •

DEFEND employs constrained reconstruction error coupled with a disentangled
encoder for fair anomaly detection.

  * •

Extensive experiments on real-world datasets show that DEFEND achieves a
competitive performance and significantly enhances fairness compared with
baselines.

Figure 1. An overview of proposed DEFEND framework. (Left) Disentangled fair
representation learning. The disentangled graph encoder $f_{e}$ can separate
sensitive-irrelevant representations $\mathbf{Z}_{x}$ and sensitive-relevant
representations $\mathbf{Z}_{s}$ in latent space. (Right) Reconstruct-based
graph anomaly detection. The constrained reconstruction error between
$\mathbf{X}$ and $\tilde{\mathbf{X}}$ are used to identify anomalies. ❄ means
fixing model parameters.

##  2\. Preliminaries

###  2.1. Problem Definition

Let $\mathcal{G}=(\mathcal{V},\mathbf{A},\mathbf{X},\mathbf{S})$ be an
attributed graph with $N$ nodes and $E$ edges, where
$\mathcal{V}=\\{v_{1},\dots,v_{N}\\}$ is the set of nodes. The adjacency
matrix is denoted as $\mathbf{A}\in{\\{0,1\\}}^{N\times N}$, where
$\mathbf{A}_{ij}=1$ if there exists an edge between $v_{i}$ and $v_{j}$,
otherwise, $\mathbf{A}_{ij}=0$. $\mathbf{X}\in\mathbb{R}^{N\times d}$
represents the node attribute matrix, while $\mathbf{S}\in\mathbb{R}^{N\times
m}$ represents the sensitive attribute matrix (e.g., age, gender, religion,
ethnicity, etc.). Here, $m$ denotes the total number of sensitive attributes.
To simplify the problem, in this work, we mainly focus on a single binary
sensitive attribute, denoted as $\mathbf{S}\in{\\{0,1\\}}^{N\times 1}$. We can
easily extend our method to more complicated settings (Creager et al., 2019;
Deepak and Abraham, 2020). We discuss more details in Section 3.5. Node
$v_{i}$ and $v_{j}$ belong to the same demographic group if $s_{i}=s_{j}$. The
goal of fair graph anomaly detection is to provide unbiased prediction against
sensitive attributes while achieving satisfactory accuracy simultaneously.

###  2.2. Fairness Metrics

Following (Agarwal et al., 2021; Wang et al., 2022; Zhu et al., 2023), we
utilize two extensively used metrics to evaluate the fairness of the model
among demographic groups, including Demographic Parity (Dwork et al., 2012)
and Equal Opportunity (Hardt et al., 2016). Notably, a lower value in
Demographic Parity and Equal Opportunity reflects a higher level of fairness
achieved by the model.

####  2.2.1. Demographic parity.

Demographic parity (DP) dictates the equal predicted probability across
demographic groups. In GAD tasks, it indicates a consistent rate of anomaly
detection across all demographic groups. It can be formulated as:

(1) $\Delta_{DP}=|P(\hat{y}=1|s=0)-P(\hat{y}=1|s=1)|,$

where $\hat{y}\in\\{0,1\\}$ is the predicted node label, and $\hat{y}_{i}=1$
indicates node $v_{i}$ is a predicted anomaly.

####  2.2.2. Equal Opportunity.

Equal Opportunity (EO) requires the same true positive rates of identifying
anomalies for each demographic group. Specifically, it implies that each
demographic group should have an equivalent probability of correctly
identifying true anomalies. It can be defined as:

(2) $\Delta_{EO}=|P(\hat{y}=1|s=0,y=1)-P(\hat{y}=1|s=1,y=1)|,$

where $y\in\\{0,1\\}$ is the ground truth anomaly label, and $y_{i}=1$ denotes
node $v_{i}$ is a true anomaly.

##  3\. Proposed Method

In this section, we describe the proposed DEFEND in detail. Initially, we
provide an overview of DEFEND in Section 3.1. Then, we describe the
disentangled representation learning phase in Section 3.2, and the anomaly
detection phase in Section 3.3. Next, the training and inference processes of
DEFEND are elaborated upon, alongside an analysis of its computational
complexity in Section 3.4. Finally, we explore the generalization capabilities
of DEFEND across diverse sensitive attributes in Section 3.5.

###  3.1. Overview

We provide an overview of DEFEND, which aims to identify anomalies without
skewed towards any demographic groups defined on the given sensitive
attributes. As depicted in Figure 1, there are two major phases in DEFEND.
Firstly, as shown in the left part of Figure 1, the fair disentangled
representation learning phase separates sensitive-relevant and sensitive-
irrelevant representations in the latent space. Different from the i.i.d.
data, nodes in a graph are connected by edges. To effectively encode these
dependencies, we propose to learn the node representations by a variational
graph autoencoder. Specifically, a GNN encoder $f_{e}$ maps the node attribute
$\mathbf{X}$ and graph topology $\mathbf{A}$ of the input graph $\mathcal{G}$
into independent subspaces, i.e., sensitive-relevant and sensitive-irrelevant
subspaces. Subsequently, two decoders $f_{a}$ and $f_{x}$ are employed to
generate the adjacency matrix $\hat{\mathbf{A}}$ and the node attributes
$\hat{\mathbf{X}}$, respectively. This reconstruction enables node
representations to further learn the topological dependencies from self-
supervision signals. To promote the independence of sensitive-irrelevant
representations $\mathbf{Z}_{x}$ from sensitive-relevant representations
$\mathbf{Z}_{s}$, we include a learnable adversary $g_{\omega}$. Besides
minimizing reconstruction error to obtain informative representations, we also
endeavor to accurately infer sensitive attributes $\mathbf{S}$ from
$\mathbf{Z}_{s}$. Ideally, $\mathbf{Z}_{x}$ contains nearly no sensitive
information with a well-trained $f_{e}$. Secondly, the unsupervised graph
anomaly detection phase aims to identify anomalies according to the sensitive-
irrelevant representations, as shown in the right part of Figure 1. However,
the reconstruction-based anomaly detection can incur bias from the
reconstruction target. As such, the decoder $f_{\phi}$ only reconstructs node
attributes from sensitive-irrelevant representations $\mathbf{Z}_{x}$ through
Multi-Layer Perceptron (MLP) without the involvement of graph topology.
Moreover, as node attributes $\mathbf{X}$ inherently have potential
correlations with sensitive attributes $\mathbf{S}$, we propose to further
constrain the correlation in the loss function.

###  3.2. Disentangled Fair Representation Learning

Due to the potential bias existing in node attributes and graph topology, GNNs
might amplify sensitive information when generating node representations with
the message-passing process (Dai and Wang, 2021; Zhu et al., 2023).
Informative sensitive-irrelevant representations are essential for fair and
accurate decision-making in downstream tasks, which thoroughly considers all
information pertinent to each node in terms of node and structure levels.
Previous theoretical insights and empirical evidence have highlighted the
effectiveness of disentanglement in generating sensitive-irrelevant
representations and augmenting fairness in downstream tasks like image
classification (Creager et al., 2019; Oh et al., 2022). We posit that
disentangling sensitive and non-sensitive representations for graph data is
also feasible to obtain informative yet sensitive-irrelevant node
representations, which can be used for graph anomaly detection. The details of
disentangled representation learning in DEFEND are described as follows.

####  3.2.1. Disentangled Graph Encoder.

The encoder $f_{e}$ is designed to learn disentangled node representations,
premised on the assumption that the latent space can be decomposed into two
independent subspaces: one associated with sensitive attributes and the other
independent of sensitive attributes. For the graph data, the posterior
distribution of node representation
$q(\mathbf{Z}_{x},\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})$ is based on the node
attributes $\mathbf{X}$ and graph topology $\mathbf{A}$. To ensure
disentanglement on graphs, it is essential to establish conditional
independence between sensitive-irrelevant representations $\mathbf{Z}_{x}$ and
sensitive-relevant representations $\mathbf{Z}_{s}$, given $\mathbf{X}$ and
$\mathbf{A}$. Under the assumption of conditional independence, the
variational posterior distribution
$q(\mathbf{Z}_{x},\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})$ can be defined as the
product of the individual distributions for $\mathbf{Z}_{x}$ and
$\mathbf{Z}_{s}$:

(3)
$q(\mathbf{Z}_{x},\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})=q(\mathbf{Z}_{x}|\mathbf{X},\mathbf{A})q(\mathbf{Z}_{s}|\mathbf{X},\mathbf{A}).$

As the disentanglement is conducted in the latent space, it is crucial to
capture informative node representations from both node attributes
$\mathbf{X}$ and topological structure $\mathbf{A}$. Thus, we adopt a GNN as
the backbone of the encoder $f_{e}$. In this work, we take Graph Convolutional
Network (GCN) (Kipf and Welling, 2016) as an example. For the $l$-th
convolutional layer, the node representation $\mathbf{H}^{(l)}$ is updated by:

(4)
$\mathbf{H}^{(l)}=\text{Conv}(\mathbf{H}^{(l-1)},\mathbf{A})=\phi\left(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}^{(l-1)}\mathbf{W}^{l}\right),$

where $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$,
$\tilde{\mathbf{D}}_{ii}=\sum_{j}\tilde{\mathbf{A}}_{ij}$, $\mathbf{I}$ is the
identity matrix of $\mathbf{A}$, $\mathbf{W}^{l}$ is the weight matrix at the
$l$-th layer and the initial node representation $\mathbf{H}^{(0)}$ is set to
$\mathbf{X}$. Next, we use the reparameterization trick to estimate the
sensitive-irrelevant representations $\mathbf{Z}_{x}$ with GCN:

(5) $\mathbf{Z}_{x}=\bm{\mu}+\bm{\sigma}\cdot\bm{\varepsilon},\
\bm{\varepsilon}\sim\mathcal{N}(\mathcal{\mathbf{0},\mathbf{I}}),$

where $\mathcal{N}(\mathcal{\mathbf{0},\mathbf{I}})$ is the standard Gaussian
distribution with a mean vector of zeros $\mathbf{0}$ and an identity
covariance matrix $\mathbf{I}$. Here, the mean matrix
$\bm{\mu}=\text{Conv}_{\bm{\mu}}(\text{Conv}_{\text{shr}}(\mathbf{X},\mathbf{A}),\mathbf{A})$
and the log standard deviation matrix
$\log\bm{\sigma}=\text{Conv}_{\bm{\sigma}}(\text{Conv}_{\text{shr}}(\mathbf{X},\mathbf{A}),\mathbf{A})$
are obtained by GCNs with a shared convolutional layer
$\text{Conv}_{\text{shr}}$. On the other hand, we estimate the sensitive-
relevant representations $\mathbf{Z}_{s}$ in a deterministic manner:

(6)
$\mathbf{Z}_{s}=\text{Conv}_{\bm{\varphi}}(\text{Conv}_{\text{shr}}(\mathbf{X},\mathbf{A}),\mathbf{A}),$

where $\text{Conv}_{\bm{\varphi}}$ is an additional layer for sensitive
representations.

####  3.2.2. Decoders.

In the decoding phase of disentangled representation learning, we reconstruct
the attribute matrix $\mathbf{X}$, the adjacency matrix $\mathbf{A}$, and
sensitive attributes $\mathbf{S}$ from the latent space. Due to sensitive-
irrelevant representations $\mathbf{Z}_{x}$ are conditionally independent of
the given sensitive attributes $\mathbf{S}$, the probability
$p(\mathbf{S}|\mathbf{Z}_{x},\mathbf{Z}_{s})$ can be simplified to
$p(\mathbf{S}|\mathbf{Z}_{s})$. Thus, the reconstruction phase in DEFEND can
be formulated by:

(7)
$p(\mathbf{X},\mathbf{A},\mathbf{S}|\mathbf{Z}_{x},\mathbf{Z}_{s})=p(\mathbf{X}|\mathbf{Z}_{x},\mathbf{Z}_{s})p(\mathbf{A}|\mathbf{Z}_{x},\mathbf{Z}_{s})p(\mathbf{S}|\mathbf{Z}_{s}).$

To model the distribution of reconstructed node attributes
$p(\mathbf{X}|\mathbf{Z}_{x},\mathbf{Z}_{s})$, we adopt an attribute decoder
$f_{x}$, which has the reverse structure of the encoder $f_{e}$. Furthermore,
we consider an inner product decoder $f_{a}$ for structure reconstruction as
follows:

(8)
$p(\mathbf{A}|\mathbf{Z}_{x},\mathbf{Z}_{s})=\text{Sigmoid}(\mathbf{Z}\mathbf{Z}^{\top}),$

where $\mathbf{Z}=\text{Concat}(\mathbf{Z}_{x},\mathbf{Z}_{s})$. Next, to
model the conditional probability distribution $p(\mathbf{S}|\mathbf{Z}_{s})$,
we adopt a binary classifier, where sensitive attribute $\mathbf{S}$ is
assumed to follow a Bernoulli distribution parameterized by the Sigmoid
function applied to $\mathbf{Z}_{s}$. The conditional distribution for the
sensitive attributes is formulated as:

(9)
$p(\mathbf{S}|\mathbf{Z}_{s})=\text{Bernoulli}(\mathbf{S}|\text{Sigmoid}(\mathbf{Z}_{s})).$

####  3.2.3. Adversary.

To encourage the independence between sensitive-irrelevant representations
$\mathbf{Z}_{x}$ and sensitive-relevant representations $\mathbf{Z}_{s}$, it
is imperative that the aggregate posterior distribution can be factorized as
$q(\mathbf{Z}_{x},\mathbf{Z}_{s})=q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})$. Thus,
we employ the Kullback-Leibler (KL) divergence between
$q(\mathbf{Z}_{x},\mathbf{Z}_{s})$ and $q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})$ as
the disentanglement criteria, which can be expressed as
${KL}\big{[}q(\mathbf{Z}_{x},\mathbf{Z}_{s})\,\|\,q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})\big{]}$.
Following previous studies (Kim and Mnih, 2018; Sugiyama et al., 2012; Creager
et al., 2019), we adopt a binary adversary to encourage the disentanglement by
approximating the log density ratio inherent in the KL divergence term:

(10)
$\displaystyle{KL}\big{[}q(\mathbf{Z}_{x},\mathbf{Z}_{s})\,\|\,q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})\big{]}=\mathbb{E}_{q(\mathbf{Z}_{x},\mathbf{Z}_{s})}\log\frac{q(\mathbf{Z}_{x},\mathbf{Z}_{s})}{q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})}$
$\displaystyle\approx\mathbb{E}_{q(\mathbf{Z}_{x},\mathbf{Z}_{s})}[\log
g_{\omega}(\tilde{\mathbf{y}}=1|\mathbf{Z}_{x},\mathbf{Z}_{s})-\log
g_{\omega}(\tilde{\mathbf{y}}=0|\mathbf{Z}_{x},\mathbf{Z}_{s})],$

where $\tilde{\mathbf{y}}=1$ denotes ”true” samples from the aggregate
posterior $q(\mathbf{Z}_{x},\mathbf{Z}_{s})$ and $\tilde{\mathbf{y}}=0$
denotes ”fake” samples from the product of the marginals
$q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})$. Specifically, we implement an MLP as the
binary adversary $g_{\omega}$ to predict whether $\mathbf{z}_{x}^{i}$, the
sensitive-irrelevant representation of node $v_{i}$, and $\mathbf{z}_{s}^{j}$,
the sensitive-relevant of node $v_{j}$, are from the same node.

####  3.2.4. Learning Objective.

In the disentangled representation learning phase, we optimize the
disentangled graph encoder $f_{e}$, structure decoder $f_{a}$, and attribute
decoder $f_{x}$ from three aspects, including the variational lower bound
term, the disentanglement term, and the predictiveness term. First, the
variational lower bound term comprises a reconstruction term and a KL
divergence regularization term. The reconstruction term, addressing both node
attributes and topological structure, can be formulated as:

(11)
$\mathcal{L}_{rec}=\mathbb{E}_{q(\mathbf{Z}_{x},\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})}\left[(1-\epsilon)\log
p(\mathbf{X}|\mathbf{Z}_{x},\mathbf{Z}_{s})+\epsilon\log
p(\mathbf{A}|\mathbf{Z}_{x},\mathbf{Z}_{s})\right]$

where the first term is the reconstruction error for node attribute and the
second term is the reconstruction error for graph topology. Moreover,
$\epsilon=\frac{\sigma_{\mathbf{X}}}{\sigma_{\mathbf{X}}+\sigma_{\mathbf{A}}}$
is the weight coefficient for balancing the impact of structure and attribute
reconstruction, where $\sigma_{\mathbf{A}}$ and $\sigma_{\mathbf{X}}$ denotes
the standard deviations of $\mathbf{A}$ and $\mathbf{X}$, respectively. The KL
divergence regularization term is employed to minimize the KL divergence
between the posterior distribution
$q(\mathbf{Z}_{x},\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})$ and the prior
distribution $p(\mathbf{Z}_{x},\mathbf{Z}_{s})$. The overall objective within
the variational lower bound can be formulated as:

(12)
$\mathcal{L}_{vae}=\mathcal{L}_{rec}-KL[q(\mathbf{Z}_{x},\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})\parallel
p(\mathbf{Z}_{x},\mathbf{Z}_{s})],$

where $p(\mathbf{Z}_{x},\mathbf{Z}_{s})=p(\mathbf{Z}_{x})p(\mathbf{Z}_{s})$
under the assumption that $\mathbf{Z}_{x}$ and $\mathbf{Z}_{s}$ are
independent. The prior distributions $p(\mathbf{Z}_{x})$ and
$p(\mathbf{Z}_{s})$ are modeled by the standard Gaussian distribution and
uniform distribution, respectively. Next, the disentanglement term, which is
crucial for separating sensitive-relevant and sensitive-irrelevant
representations, is calculated by the binary adversary $g_{\omega}$:

(13) $\mathcal{L}_{dis}=\mathbb{E}_{\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i}\sim
q(\mathbf{Z}_{x},\mathbf{Z}_{s})}\log
p(\tilde{y}=1|\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i})-\log
p(\tilde{y}=0|\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i}),$

where $(\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i})$ is a true sample for which
$\tilde{y}=1$. Moreover, DEFEND incorporates a predictiveness term to align
the sensitive representation $\mathbf{Z}_{s}$ closely with the given sensitive
attributes $\mathbf{S}$. Intuitively, accurate prediction of sensitive
attributes can enhance the comprehensive understanding of node attributes in
latent space and facilitate a clearer distinction between representations
associated with sensitive attributes and those that are not. The
predictiveness loss term can be expressed as:

(14)
$\mathcal{L}_{pre}=\mathbb{E}_{q(\mathbf{Z}_{s}|\mathbf{X},\mathbf{A})}\log
p(\mathbf{S}|\mathbf{Z}_{s}).$

The overall loss for optimizing $f_{e}$, $f_{a}$ and $f_{x}$ can be defined
as:

(15)
$\mathcal{L}_{total}=\mathcal{L}_{vae}+\gamma\mathcal{L}_{dis}+\alpha\mathcal{L}_{pre},$

where $\alpha$ and $\gamma$ are the weight coefficients to control the impact
of the predictiveness and disentanglement terms relative to the variational
lower bound term, respectively.

During the training phase of the binary adversary $g_{\omega}$, the true
sample $(\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i})$ is sampled from the aggregate
posterior $q(\mathbf{Z}_{x},\mathbf{Z}_{s})$ while the fake sample
$(\mathbf{z}_{x}^{j},\mathbf{z}_{s}^{k})$ is sampled from the product of
marginal posterior distributions $q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})$. The
adversarial loss can be formulated as:

(16) $\displaystyle\mathcal{L}_{adv}$
$\displaystyle=\mathbb{E}_{\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i}\sim
q(\mathbf{Z}_{x},\mathbf{Z}_{s})}\log
p(\tilde{y}=1|\mathbf{z}_{x}^{i},\mathbf{z}_{s}^{i})$
$\displaystyle+\mathbb{E}_{\mathbf{z}_{x}^{j},\mathbf{z}_{s}^{k}\sim
q(\mathbf{Z}_{x})q(\mathbf{Z}_{s})}\log[1-p(\tilde{y}=0|\mathbf{z}_{x}^{j},\mathbf{z}_{s}^{k})].$

In DEFEND, the optimization of $f_{e}$, $f_{a}$ and $f_{x}$ and that of
$g_{\omega}$ are conducted adversarially. A well-trained encoder $f_{e}$,
which can effectively encode node attributes and its local topology into
latent space, and obtain sensitive-irrelevant representations, can be adeptly
employed in downstream tasks for enhancing fairness.

###  3.3. Graph Anomaly Detection

In this phase, the primary objective is to detect anomalies unbiased to any
demographic groups based on deterministic sensitive-irrelevant representations
$\bar{\mathbf{Z}}_{x}=\bm{\mu}$. Due to anomalies typically significantly
deviate the majority of samples, the reconstruction error is widely used to
measure anomaly scores in prior studies (Ding et al., 2019; Fan et al., 2020;
Shekhar et al., 2021). Thus, we introduce an additional decoder $f_{\phi}$ to
evaluate anomalous node by reconstructing the input attributes $\mathbf{X}$
from sensitive-irrelevant representations $\bar{\mathbf{Z}}_{x}$. The anomaly
score ${o}_{i}$ for node $v_{i}$ is defined as the corresponding
reconstruction error:

(17) ${o}_{i}={||\mathbf{x}_{i}-\tilde{\mathbf{x}}_{i}||}_{F}^{2},$

where
$\tilde{\mathbf{X}}=f_{\phi}(\bar{\mathbf{Z}}_{x},\tilde{\mathbf{Z}}_{s})$ and
$\tilde{\mathbf{Z}}_{s}$ denotes a shuffled variant of $\mathbf{Z}_{s}$.
Considering the potential bias in graph topology, we solely reconstruct node
attributes to evaluate anomalies and employ MLP as the backbone of $f_{\phi}$
to mitigate the impact of biased topology during the message-passing process.

Additionally, given that input attributes are likely to be relevant to
sensitive attributes (Deepak and Abraham, 2020) while $\bar{\mathbf{Z}}_{x}$
is designed to be devoid of sensitive information, the reconstruction error
inherently correlates with sensitive attributes. To mitigate the impact of
this correlation and prevent directly leveraging sensitive attributes, we
propose a correlation constraint term, which measures the absolute correlation
between the reconstruction error ${o}_{i}$ and predicted sensitive attributes
$\mathbf{z}_{s}^{i}$ as follows:

(18)
$\mathcal{L}_{corr}=\left|\frac{(\sum_{i\in\mathcal{V}}{{o}_{i}-\mu_{o}})(\sum_{i\in\mathcal{V}}{\mathbf{z}_{s}^{i}-\mu_{zs}}))}{\sigma_{o}\sigma_{zs}}\right|,$

where $\mu_{o}$ and $\mu_{zs}$ represent the means, while $\sigma_{o}$ and
$\sigma_{zs}$ denote the corresponding standard deviations of $\mathbf{o}$ and
$\mathbf{Z}_{s}$, respectively.

####  3.3.1. Learning Objective.

In the anomaly detection phase, the encoder $f_{e}$ is set to be non-
trainable, as it has already mastered the separation of sensitive-relevant and
sensitive-irrelevant representations during the disentangled representation
learning phase. Accordingly, the optimization is exclusively concentrated on
the decoder $f_{\phi}$. The overall learning objective in the anomaly
detection phase, consisting of the reconstruction term and the correlation
constraints term can be formulated as:

(19) $\mathcal{L}_{ad}=\mathcal{L}_{rec}^{X}+\beta\mathcal{L}_{corr},$

where $\mathcal{L}_{rec}^{X}=\sum_{i}^{n}{o}_{i}$ denotes the reconstruction
loss for node attributes $\mathbf{X}$ and $\beta$ is the penalty of sensitive
information in $\mathbf{X}$.

###  3.4. Training and Inference

The overall training process of DEFEND is presented in Algorithm 1. In the
disentangled representation learning phase, given an attributed graph
$\mathcal{G}$, we aim to train a variational graph autoencoder, in which the
disentangled encoder $f_{e}$ can separate nonsensitive representations while
maintaining information for reconstructing $\mathcal{G}$ by the decoder
$f_{a}$ and $f_{x}$. We encourage the disentanglement with a learnable
adversary $g_{\omega}$, which is optimized with $\mathcal{L}_{adv}$. The
optimization of $f_{e}$, $f_{a}$ and $f_{x}$ and the optimization of
$g_{\omega}$ are conducted adversarially. For anomaly detection, we freeze the
encoder $f_{e}$ to obtain sensitive-irrelevant node representations and
reconstruct attributes solely with the decoder $f_{\phi}$. We utilize
reconstruction error as the anomaly score and constrain the correlation
between reconstruction error and predicted sensitive attributes.

We analyze the computational complexity of DEFEND as follows. In the
disentangled representation learning phase, the encoder $f_{e}$ processes with
a complexity of $O(E\times(d+m))$, where $E$ denotes the number of edges and
$d+m$ denotes the attribute dimensionality. The decoders $f_{a}$ and $f_{x}$
exhibit a complexity of approximately $O(N^{2})$ due to adjacency matrix
reconstruction. The adversary operates at $O(D_{0})$ with $D_{0}$ neurons in
the MLP. In the anomaly detection phase, the complexity for the frozen encoder
remains $O(E\times(d+m))$, whereas the MLP-based decoder $f_{\phi}$ exhibits a
complexity of $O(D_{1})$ with $D_{1}$ neurons in the MLP. Given that
$D_{0}\leq d$ and $D_{1}\leq d$ in most cases, the overall computational
complexity is estimated as $O(N^{2}+E\times(d+m))$. Notably, in practical
applications, the quadratic complexity associated with the matrix
reconstruction is effectively reduced using sparse matrix techniques, which
are well-suited for the sparse graphs commonly encountered in real-world
scenarios.

Algorithm 1 DEFEND algorithm

0: Graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, adjacency matrix
$\mathbf{A}$, attribute matrix $\mathbf{X}$, sensitive attribute matrix
$\mathbf{S}$, GNN encoder $f_{e}$, attribute decoder $f_{x}$, structure
decoder $f_{a}$, binary adversary $g_{\omega}$, linear attribute decoder
$f_{\phi}$, training iteration $T$;

0: Anomaly scores $\mathbf{o}$

1: // Disentangled representation learning phase;

2: Initialize $f_{e},f_{a},f_{x},g_{\omega}$;

3: while not converged do

4: $\mathbf{Z}_{x},\mathbf{Z}_{s}\leftarrow f_{e}(\mathbf{X},\mathbf{A})$;

5: $\hat{\mathbf{A}},\hat{\mathbf{X}}\leftarrow
f_{a}(\mathbf{Z}_{x},\mathbf{Z}_{s}),f_{x}(\mathbf{Z}_{x},\mathbf{Z}_{s})$;

6: Calculate $\mathcal{L}_{total}$ according to Eq. (missing) 15;

7: Update $f_{e},f_{a},f_{x}$ by gradient descent using $\mathcal{L}_{total}$;

8: Calculate $\mathcal{L}_{adv}$ according to Eq. (missing) 16;

9: Update $g_{\omega}$ by gradient descent using $\mathcal{L}_{adv}$;

10: end while

11:

12: // Anomaly detection phase;

13: Freeze $f_{e}$ and initialize $f_{\phi}$;

14: for $t=1,2,\dots,T$ do

15: $\bar{\mathbf{Z}}_{x},\mathbf{Z}_{s}\leftarrow
f_{e}(\mathbf{X},\mathbf{A})$;

16: $\tilde{\mathbf{X}}\leftarrow
f_{\phi}(\bar{\mathbf{Z}}_{x},\tilde{\mathbf{Z}}_{s})$;

17: Calculate anomaly score $\mathbf{o}$ according to Eq. (missing) 17;

18: Calculate $\mathcal{L}_{corr}$ according to Eq. (missing) 18;

19: Calculate $\mathcal{L}_{ad}$ according to Eq. (missing) 19;

20: Update $f_{\phi}$ by gradient descent using $\mathcal{L}_{ad}$;

21: end for

22: return $\mathbf{o}$;

###  3.5. Discussion

We analyze the generalization of DEFEND on various types of sensitive
attributes. (1) Multiple Binary Sensitive Attributes. Let
$\mathbf{s}=\left[{s^{0}},{s^{1}},\ldots,{s^{m}}\right]$ denotes the sensitive
attributes for each node, where $s^{j}\in\\{0,1\\}(0\leq j<m)$. The
disentanglement between sensitive-irrelevant representations $\mathbf{Z}_{x}$
and sensitive-relevant representations $\mathbf{Z}_{s}\in\mathbb{R}^{N\times
m}$ requires that $\mathbf{Z}_{x}$ is independent of each sensitive attribute
$\mathbf{Z}_{s}^{(j)}$. Thus, $\mathbf{Z}_{x}$ and $\mathbf{Z}_{s}$ is
disentangled if the aggregate posterior distribution can be factorized as
$p(\mathbf{Z}_{x},\mathbf{Z}_{s})=p(\mathbf{Z}_{x})\prod_{j}p(\mathbf{Z}_{s}^{(j)})$.
(2) Single Categorical/Continuous Sensitive Attributes. With single binary
sensitive attributes, the conditional distribution
$p(\mathbf{S}|\mathbf{Z}_{s})$ is typically modeled using a Bernoulli
distribution. However, with categorical attributes, this shifts to a
Multinomial distribution, i.e.,
$p(\mathbf{S}|\mathbf{Z}_{s})=\text{Multinomial}(\mathbf{S}|\text{SoftMax}(\mathbf{Z}_{s})).$
Similarly, for continuous attributes, $p(\mathbf{S}|\mathbf{Z}_{s})$ can be
modeled using a Gaussian distribution.

##  4\. Experiments

###  4.1. Experimental Setup

####  4.1.1. Datasets.

We employ two real-world datasets for fair graph anomaly detection in our
experiments, including Reddit and Twitter (Neo et al., 2024). Details of these
datasets are summarized in Table 1.

  * •

Reddit: The Reddit dataset contains 110 politically oriented subreddits,
encompassing all historical postings within these forums. It also includes all
historical posts from several active discussion participants. A relational
graph was constructed by linking users who posted in the same subreddit within
24 hours.

  * •

Twitter: The Twitter dataset is conducted on 47,712 users with their
historical posts, user profiles, and follower relationships. The user
information, such as the organization status, was inferred using the M3 System
from user profiles and tweets. The key account metrics and averaged post
embeddings were combined to form node features.

Both Reddit and Twitter datasets contain real sensitive attributes and ground-
truth labels for graph anomaly detection (Neo et al., 2024). Specifically, in
the case of both datasets, the sensitive attribute is the political leaning of
users, while the anomaly label is assigned to users identified as
misinformation spreaders.

####  4.1.2. Baselines.

We compare DEFEND with three types of baselines: (1) GAD methods, including
DOMINANT (Ding et al., 2019), CoLA (Liu et al., 2021), and CONAD (Xu et al.,
2022); (2) GAD methods augmented with Fairness Regularizers like FairOD
(Shekhar et al., 2021), HIN (Zeng et al., 2021), and Correlation (Shekhar et
al., 2021), which incorporate fairness constraints into the optimization
process; (3) GAD methods that operate on graphs pre-processed by Graph
Debiasers, such as FairWalk (Rahman et al., 2019) and EDITS (Dong et al.,
2022), where the debiased graph rather than the raw graph serves as input. The
details of baselines are introduced in Appendix A.1.

Table 1. Statistics of datasets. $\gamma_{G}$ denotes the ratio of the
majority and minority group and $\gamma_{A}$ denotes the ratio of the
anomalies and normal nodes.

Dataset | # Nodes | # Edges | # Attributes | $\gamma_{G}$ | $\gamma_{A}$
---|---|---|---|---|---
Reddit | 9,892 | 1,211,748 | 385 | 0.1502 | 0.1584
Twitter | 47,712 | 468,697 | 780 | 0.1365 | 0.0713

Table 2. Comparison results of DEFEND against all baseline methods. $\uparrow$
denotes larger values are better, whereas $\downarrow$ denotes lower values
are preferable. The best and second best performances are highlighted in bold
and underlined, respectively. OOM indicates out of memory.

|  | Reddit | Twitter
---|---|---|---
|  | AUC-ROC $\uparrow$ | AUC-PR $\uparrow$ | $\Delta_{DP}\downarrow$ | $\Delta_{EO}\downarrow$ | AUC-ROC $\uparrow$ | AUC-PR $\uparrow$ | $\Delta_{DP}\downarrow$ | $\Delta_{EO}\downarrow$
- | DOMINANT | 60.82$\pm$0.09 | 20.02$\pm$0.04 | 13.20$\pm$0.08 | 5.59$\pm$0.19 | 56.49$\pm$0.61 | 8.92$\pm$0.15 | 4.33$\pm$0.47 | 4.51$\pm$0.44
CoLA | 45.20$\pm$0.98 | 17.90$\pm$1.54 | 4.95$\pm$1.78 | 4.06$\pm$1.85 | 43.74$\pm$1.08 | 5.23$\pm$0.15 | 2.63$\pm$0.32 | 2.47$\pm$1.08
CONAD | 60.81$\pm$0.10 | 20.02$\pm$0.05 | 13.32$\pm$0.33 | 5.70$\pm$0.37 | 56.12$\pm$0.73 | 8.83$\pm$0.17 | 4.08$\pm$0.47 | 4.48$\pm$0.35
FairWalk | DOMINANT | 51.26$\pm$1.08 | 14.55$\pm$0.65 | 2.45$\pm$0.79 | 1.97$\pm$1.25 | 53.06$\pm$0.81 | 8.17$\pm$0.43 | 1.32$\pm$0.27 | 1.27$\pm$0.35
CoLA | 51.12$\pm$0.83 | 14.83$\pm$0.85 | 0.69$\pm$0.37 | 0.60$\pm$0.59 | 49.02$\pm$0.54 | 6.34$\pm$0.23 | 0.23$\pm$0.14 | 0.34$\pm$0.16
CONAD | 51.26$\pm$1.88 | 14.68$\pm$1.15 | 2.49$\pm$1.28 | 2.52$\pm$1.58 | 53.36$\pm$0.70 | 8.32$\pm$0.42 | 1.30$\pm$0.18 | 1.37$\pm$0.39
EDITS | DOMINANT | OOM | OOM | OOM | OOM | 53.79$\pm$0.25 | 8.75$\pm$0.06 | 2.63$\pm$0.05 | 2.21$\pm$0.15
CoLA | 54.41$\pm$1.62 | 23.13$\pm$3.67 | 23.74$\pm$5.76 | 21.00$\pm$5.38 | 46.62$\pm$1.35 | 5.70$\pm$0.30 | 1.84$\pm$0.39 | 1.03$\pm$0.82
CONAD | OOM | OOM | OOM | OOM | 53.83$\pm$0.24 | 8.75$\pm$0.06 | 2.62$\pm$0.03 | 2.16$\pm$0.13
FairOD | DOMINANT | 60.94$\pm$0.07 | 19.97$\pm$0.08 | 13.08$\pm$0.21 | 5.04$\pm$0.15 | 53.69$\pm$3.63 | 7.87$\pm$1.10 | 2.56$\pm$1.51 | 2.49$\pm$1.52
CoLA | 45.76$\pm$10.23 | 15.77$\pm$5.42 | 13.26$\pm$6.24 | 5.98$\pm$5.83 | 45.81$\pm$7.40 | 6.29$\pm$1.52 | 1.95$\pm$1.82 | 1.23$\pm$0.77
CONAD | 60.53$\pm$0.11 | 19.53$\pm$0.08 | 12.57$\pm$0.11 | 5.02$\pm$0.11 | 57.09$\pm$0.43 | 9.08$\pm$0.13 | 4.48$\pm$0.45 | 4.59$\pm$0.56
HIN | DOMINANT | 60.91$\pm$0.06 | 20.10$\pm$0.04 | 13.38$\pm$0.10 | 5.69$\pm$0.22 | 54.07$\pm$2.22 | 8.23$\pm$0.79 | 2.50$\pm$1.24 | 3.51$\pm$0.96
CoLA | 45.52$\pm$1.47 | 18.59$\pm$1.68 | 4.58$\pm$2.50 | 4.43$\pm$2.28 | 48.08$\pm$5.31 | 6.49$\pm$1.18 | 2.38$\pm$1.23 | 0.62$\pm$0.69
CONAD | 60.89$\pm$0.18 | 20.06$\pm$0.10 | 13.35$\pm$0.21 | 5.81$\pm$0.45 | 53.74$\pm$2.74 | 8.12$\pm$1.02 | 2.59$\pm$1.36 | 3.34$\pm$1.04
Correlation | DOMINANT | 60.38$\pm$0.08 | 19.57$\pm$0.06 | 12.27$\pm$0.25 | 4.42$\pm$0.20 | 56.21$\pm$0.60 | 8.81$\pm$0.14 | 4.22$\pm$0.38 | 4.58$\pm$0.29
CoLA | 50.94$\pm$6.37 | 15.29$\pm$3.50 | 9.63$\pm$7.26 | 11.68$\pm$8.23 | 48.65$\pm$2.89 | 6.29$\pm$0.48 | 3.32$\pm$1.18 | 3.42$\pm$2.10
CONAD | 59.51$\pm$0.33 | 18.86$\pm$0.28 | 10.94$\pm$0.74 | 3.80$\pm$0.35 | 55.94$\pm$0.71 | 8.76$\pm$0.17 | 4.00$\pm$0.44 | 4.52$\pm$0.31
Ours | DEFEND | 60.67$\pm$0.42 | 16.46$\pm$0.25 | 0.94$\pm$0.72 | 1.13$\pm$0.81 | 75.59$\pm$2.00 | 11.85$\pm$0.79 | 0.72$\pm$0.70 | 0.79$\pm$0.61

####  4.1.3. Evaluation metrics.

We follow previous studies (Ding et al., 2019; Liu et al., 2021; Xu et al.,
2022; Chai et al., 2022; Neo et al., 2024) to evaluate the anomaly detection
performance with two widely used metrics: the Area Under the Receiver
Operating Characteristic Curve (AUC-ROC) and the Area Under the Precision-
Recall Curve (AUC-PR). AUC-ROC quantifies the model’s ability to distinguish
between classes by measuring the area beneath the curve plotted with the False
Positive Rate against the True Positive Rate. Additionally, AUC-PR captures
the precision-recall trade-off at various thresholds, providing insights into
the model’s performance in identifying anomalous nodes. Higher AUC-ROC and
AUC-PR indicate superior anomaly detection capabilities. Regarding demographic
fairness, we adopt Demographic Parity ($\Delta_{DP}$) and Equal Opportunity
($\Delta_{EO}$) following prior studies (Dai and Wang, 2021; Dong et al.,
2022). The concepts are elaborated upon in Section 2.2. A lower $\Delta_{DP}$
and $\Delta_{EO}$ suggest better performance in fairness.

####  4.1.4. Implementation details.

For DEFEND, we use 2-layer GCN for the encoder $f_{e}$ and attribute decoder
$f_{x}$, and 2-layer MLP for the decoder $f_{\phi}$. The hidden dimension of
each layer is fixed to be 64. We employ the Adam optimizer with a learning
rate set to 0.001 and 0.005 for Reddit and Twitter, respectively. We set the
maximum training epoch in disentangled representation learning as 100, and
adopt an early stopping strategy when the loss does not decrease for 20
epochs. In the anomaly detection phase, we train the decoder $f_{\phi}$ for
100 epochs. For each dataset, we tune $\alpha$ and $\gamma$ in Eq. (missing)
15 from $\\{0.1,0.5,1.0,1.5,2.0,2.5\\}$, and the weight of correlation
constrains $\beta$ in Eq. (missing) 19 from
$\\{1e-15,5e-15,1e-10,5e-10,1e-9\\}$, respectively. For DOMINANT, CoLA, and
CONAD, we use the code and default hyper-parameters provided by
PyGOD111https://pygod.org (Liu et al., 2022a). For
FairWalk222https://github.com/urielsinger/fairwalk and
EDITS333https://github.com/yushundong/EDITS, we implement them using the code
published by their authors. For FairOD, HIN, and Correlation, we implement the
code provided by FairGAD444https://github.com/nigelnnk/FairGAD. We conduct all
experiments on one Linux server with an NVIDIA TESLA A800 GPU (80 GB RAM). We
run DEFEND and all baselines ten times and report the average results to
prevent extreme cases.

###  4.2. Performance Comparison

To evaluate our proposed DEFEND in terms of fairness and utility performance,
we compare it with all baselines mentioned above on Reddit and Twitter for
graph anomaly detection. The results are shown in Table 2 and Figure 2.

####  4.2.1. Fairness and Utility Performance.

Table 2 shows the fairness ($\Delta_{DP}$ and $\Delta_{EO}$ ) and utility
(AUC-ROC and AUC-PR) performance of DEFEND and all baselines. From Table 2, we
have the following observations: (1) The proposed DEFEND improves fairness
while maintaining accuracy across all datasets, which underscores the efficacy
of DEFEND in managing the trade-off between fairness and accuracy in graph
anomaly detection. Illustratively, in comparison with CONAD incorporated with
FairOD on Reddit, DEFEND achieves nearly 11.6% improvement in demographic
parity and a 3.8% improvement in equal opportunity metric, while sustaining
comparable AUC-ROC and AUC-PR. Such achievements reveal the potential of
DEFEND as a reliable solution for fair and precise GAD. Furthermore, we
observe that DEFEND is surpassed in terms of accuracy on the Reddit dataset by
several baseline methods, such as CoLA with HIN as a regularizer and DOMINANT
with FairOD as a regularizer. However, it’s noteworthy that the fairness
metrics for these methods are significantly inferior to DEFEND, being 5 to 10
times worse. We argue that in certain scenarios, this trade-off is justified
because improvements in fairness, even at a marginal cost to accuracy, are
considered acceptable (Dong et al., 2022; Wang et al., 2022; Zhu et al.,
2023). Prioritizing fairness, especially in contexts where decisions have
substantial social or ethical implications, can be more critical than
achieving marginally higher accuracy. Additionally, we presents an evaluation
of the fairness-accuracy trade-off for DEFEND compared with other GAD methods
that incorporate fairness regularizers. This detailed analysis is depicted in
the following subsection. (2) Compared with standard GAD methods, the
integration of graph debiasers and fairness regularizers typically improves
fairness in most cases. Nevertheless, such improvements can sometimes come at
a substantial compromise in terms of utility, particularly when debiasers are
employed. For example, on Reddit, augmenting DOMINANT with the FairWalk
debiaser results in a reduction exceeding 9% in AUC-ROC, while yielding a
marginal gain of 4% in $\Delta_{EO}$. This can be attributed to the loss of
critical features for anomaly detection during the process of bias mitigation
in graphs. In the case of GAD methods incorporating fair regularizers, a minor
decline in accuracy is observed, alongside a slight improvement in fairness.
For example, augmenting the DOMINANT with the Correlation regularizer on
Twitter data leads to a subtle trade-off between performance and fairness: a
decrease of 0.2% in AUC-ROC, alongside a slight improvement of 0.03% in
$\Delta_{EO}$. This indicates merely enforcing a direct constraint on the
correlation between anomaly scores and sensitive attributes is insufficient
for fair anomaly detection. Consequently, it is necessary to devise a
dedicated method that effectively balances utility and fairness in graph
anomaly detection.

Table 3. Comparison results of DEFEND and its variants. $\uparrow$ denotes
larger values are better, whereas $\downarrow$ denotes lower values are
preferable. The best and second best performances are highlighted in bold and
underlined, respectively.

| Reddit | Twitter
---|---|---
| AUC-ROC $\uparrow$ | AUC-PR $\uparrow$ | $\Delta_{DP}\downarrow$ | $\Delta_{EO}\downarrow$ | AUC-ROC $\uparrow$ | AUC-PR $\uparrow$ | $\Delta_{DP}\downarrow$ | $\Delta_{EO}\downarrow$
DEFEND-D | 64.41$\pm$1.23 | 20.50$\pm$0.82 | 14.36$\pm$1.23 | 13.57$\pm$1.66 | 87.44$\pm$0.14 | 23.63$\pm$0.19 | 15.53$\pm$0.22 | 13.85$\pm$1.20
DEFEND-C | 64.54$\pm$0.75 | 20.43$\pm$0.45 | 13.95$\pm$1.79 | 12.51$\pm$3.03 | 87.58$\pm$0.16 | 23.85$\pm$0.27 | 15.86$\pm$0.47 | 15.31$\pm$0.97
DEFEND-A | 60.44$\pm$1.06 | 16.39$\pm$0.41 | 1.64$\pm$1.36 | 2.53$\pm$1.99 | 83.29$\pm$4.70 | 18.83$\pm$5.34 | 8.89$\pm$7.18 | 8.37$\pm$7.03
DEFEND-S | 54.74$\pm$1.02 | 14.78$\pm$0.33 | 0.90$\pm$0.54 | 1.50$\pm$1.39 | 50.15$\pm$0.74 | 6.48$\pm$0.13 | 1.28$\pm$0.19 | 1.59$\pm$1.21
DEFEND | 60.67$\pm$0.42 | 16.46$\pm$0.25 | 0.94$\pm$0.72 | 1.13$\pm$0.81 | 75.59$\pm$2.00 | 11.85$\pm$0.79 | 0.72$\pm$0.70 | 0.79$\pm$0.61

Figure 2. Fairness-accuracy tradeoff curves on Reddit and Twitter. The upper-
left corner is preferable, which has high AUC-ROC and low Equal Opportunity
($\Delta_{EO}$).

####  4.2.2. Trade-off between Fairness and Utility.

We extend our analysis to a comparative evaluation of the fairness-accuracy
trade-off performance of DEFEND with several GAD methods incorporating
fairness regularizers. We choose Equal Opportunity to measure fairness and
AUC-ROC for accuracy assessment. Each method is trained on a range of
hyperparameters and the resulting Pareto front curves are presented in Figure
2. Notably, the optimal point is at the upper-left corner, which has perfect
accuracy and fairness, reflected by a high AUC-ROC score coupled with a low
Equal Opportunity score. Specifically, a high AUC-ROC signified proficient
detection of both normal and anomalous nodes, whereas a low Equal Opportunity
score indicates an equivalent probability of correctly identifying anomalies
across different demographic groups. From Figure 2, we can observe the trade-
off curve of DEFEND exhibits a superior distribution near the optimal point
than the baselines. Consequently, we conclude that DEFEND outperforms the
compared GAD methods with fairness regularizers in achieving a superior
balance between accuracy and fairness.

(a) AUC-ROC (%)

(b) $\Delta_{EO}$(%)

Figure 3. Impacts of varying predictiveness term weight $\alpha$ and
disentanglement term weight $\gamma$ in Eq. (missing) 15 on Reddit dataset in
terms of AUC-ROC and $\Delta_{EO}$.

###  4.3. Ablation Study

In this subsection, we conduct ablation studies to evaluate the effectiveness
of each key component for the accuracy and fairness performance of DEFEND. The
results are shown in Table 3.

Firstly, to verify the impact of correlation constraints, we eliminate the
correlation constraints term in Eq. (missing) 19 in the anomaly detection
phase, resulting in a variant referred to as DEFEND-C. We can observe that the
$\Delta_{DP}$ and $\Delta_{EO}$ of DEFEND-C is significantly higher than that
of DEFEND. It indicates a notable correlation between reconstruction error and
sensitive attributes, despite the input attributes being reconstructed from
the sensitive-irrelevant representations. We infer that the input attribute is
inherently dependent on the given sensitive attribute. Therefore, a further
constraint for reconstruction-based anomaly evaluation is necessary.

Secondly, to demonstrate the effectiveness of the disentangled representation
learning, we replace it with a vanilla VGAE that does not separate sensitive-
relevant and -irrelevant representations in latent space. Consequently, in the
absence of predicted sensitive attributes, soft correlation constraints in Eq.
(missing) 19 are removed during the anomaly detection phase, resulting in a
variant termed DEFEND-D. As shown in Table 3, when eliminating disentangled
representation learning, the fairness performance further drops. For example,
the $\Delta_{EO}$ of DEFEND-D improves 1% and 12% than that of DEFEND-C and
DEFEND on Reddit, respectively. We argue the reason is that the disentangled
representation can learn to infer sensitive attributes accurately and provide
sensitive-irrelevant representations for enhancing fairness in downstream
tasks.

Thirdly, to verify the effect of the adversary, we remove the adversary in
disentangled representation learning, termed DEFEND-A. The comparison between
DEFEND and DEFEND-A highlights the effectiveness of the adversary in enhancing
fairness, i.e., $\Delta_{DP}$ and $\Delta_{EO}$. This improvements underscores
its ability to effectively encourage the independence between sensitive-
relevant and sensitive-irrelevant representations. Besides, the removal of the
adversary increases AUC-ROC and AUC-PR scores but at the cost of significantly
reduced fairness. For instance, the improvement in AUC-ROC from 75.59% to
83.29% is accompanied by a considerable decrease in $\Delta_{DP}$ from 0.72%
to 8.89%. It is worth sacrificing accuracy to achieve greater fairness in some
scenarios.

Fourthly, we explore the impact of structure reconstruction in the anomaly
detection phase by adding a dot product decoder to reconstruct the structure,
termed DEFEND-S. When contrasting DEFEND with DEFEND-S, DEFEND not only
exhibits superior accuracy but also demonstrates enhanced fairness in most
cases. The observed reduction in accuracy for DEFEND-S suggests that the
biased topological patterns, inherent in the reconstruction-based anomaly
detection approach, adversely affect the model’s performance. This finding
supports our design choice to prioritize adversarial disentanglement over
structure reconstruction to mitigate the influence of biased patterns on
anomaly detection accuracy.

Furthermore, a significant reduction in AUC-ROC was observed in comparison to
DEFEND-D and DEFEND-C. This is attributed to the stringent fairness
requirements. A relaxation of fairness requirements may potentially lead to an
improvement in the performance of utility. As illustrated in Figure 2 (b), the
trade-off curve shows that DEFEND can achieve an AUC-ROC of nearly 80%,
coupled with a $\Delta_{EO}$ of about 1.5%. In such case, DEFEND not only
surpasses its variants in terms of fairness but also retains a utility
performance that is on par with them.

###  4.4. Parameter Analysis

In this section, we investigate the impact of three key parameters within the
proposed DEFEND on Reddit, including $\alpha$ and $\gamma$ controlling the
weight of prediction term and disentanglement term in the disentangled
representation learning phase, while $\beta$ controlling the weight of
correlation constraints in the anomaly detection phase.

####  4.4.1. Impact of $\alpha$ and $\gamma$

We train DEFEND with the values of $\alpha$ and $\gamma$ among
$\\{0.1,0.5,1.0,1.5,2.0,2.5,5.0\\}$. The results in terms of AUC-ROC and
$\Delta_{EO}$ are presented in Figure 3 (a) and Figure 3 (b), respectively.
Figure 3 (a) reveals that the anomaly detection efficacy remains substantially
stable when $\alpha\geq 2.0$ and $\gamma\leq 1.0$, which represents an optimal
range for anomaly detection capabilities. When $\gamma\geq 1.0$, there is a
marked enhancement in fairness at the expense of a rapid decline in accuracy,
emphasizing the importance of $\gamma$ in enhancing fairness without
excessively compromising accuracy. Besides, a reduction in $\alpha$ alone
significantly decreases both AUC-ROC and $\Delta_{EO}$. It underscores the
critical role of accurate sensitive label prediction in representation
learning and sensitive-irrelevant representation separation. Therefore,
selecting appropriate values for $\alpha$ and $\gamma$ is instrumental in
navigating the tradeoff between anomaly detection accuracy and fairness.

Figure 4. Impacts of varying correlation constraints weight $\beta$ in Eq.
(missing) 19 in anomaly detection phase on Reddit dataset.

####  4.4.2. Impact of $\beta$

We further train DEFEND with the values of $\beta$ among
$\\{1e-15,5e-15,1e-12,5e-12,1e-10,5e-10,1e-9,5e-9\\}$. The results are
depicted in Figure 4. First, we can observe that the $\Delta_{EO}$ decreases
more than 10% while the AUC-ROC witnesses a marginal decline of nearly 4% at
$\beta$ around $5e-12$. It emphasizes the necessity of integrating constraints
within the reconstruction-based evaluation of anomalous nodes, considering the
interrelation between input and sensitive attributes. The judicious selection
of $\beta$ is crucial for the trade-off between utility and fairness.
Moreover, it is evident that both AUC-ROC and $\Delta_{EO}$ exhibit a
decrement as the weight assigned to correlation constraints increases. This
trend can be attributed to that a higher weight strengthens the constraints
between the reconstruction error and the predicted sensitive labels, which
diminishes the potential bias in detection while also reducing the
effectiveness of the reconstruction.

##  5\. Related Work

###  5.1. Graph Anomaly Detection

Graph anomaly detection has drawn rising interest, particularly as graph data
becomes increasingly prevalent in complex real-world systems. Given the
absence of ground truth anomaly labels, lots of research for GAD focuses on an
unsupervised manner. Autoencoder has become a prominent paradigm in this
domain, which hypothesizes that anomalies deviating significantly from the
majority cannot be properly reconstructed by the decoder. DOMINANT (Ding et
al., 2019) employs GCN as the backbone of the autoencoder and evaluates
anomalies based on the reconstruction errors of node attributes and graph
topology. Furthermore, AnomalyDAE (Fan et al., 2020) adopts a dual autoencoder
structure to capture the cross-modality interactions between topology and node
attributes. GAD-NR (Roy et al., 2023) innovates by introducing neighborhood
reconstruction to improve anomaly detection. In addition, contrastive learning
is another prevalent self-supervised paradigm in graph anomaly detection. CoLA
(Liu et al., 2021) firstly introduces node-subgraph contrast to identify
anomalies based on the relation between nodes and their neighbors. Building
upon this, ANEMONE (Jin et al., 2021) incorporates node-node contrast to
capture node-level anomalies. GRADATE (Duan et al., 2023) further incorporates
subgraph-subgraph contrast to explore subgraph characteristics. Despite the
efficacy of these methods in anomaly detection, they are prone to biased
decisions due to the neglect of sensitive attributes. To bridge this gap, we
explore a novel problem of fair graph anomaly detection, aiming to detect
anomalies impartially, without bias towards sensitive attributes, while
maintaining accuracy comparable to existing anomaly detectors.

###  5.2. Fairness on Graphs

Numerous studies have been conducted to mitigate source bias in training data
to promote fairness in decision-making for graph learning tasks (Dong et al.,
2023; Chen et al., 2023). Graph debiasing methods involve removing bias from
the input graph before conducting target tasks. For example, FairWalk (Rahman
et al., 2019) enhances the general random walk algorithm to capture more
diverse neighborhoods, thereby producing embeddings that exhibit reduced bias,
while FairDrop (Spinelli et al., 2021) alters graph topology to reduce
homophily related to sensitive attributes. EDITS (Dong et al., 2022) goes
further by adjusting both graph topology and node attributes based on the
distance among demographic groups. In-processing methods represent another
pipeline that revises the model training process to achieve more fair
outcomes. For instance, FairGNN (Dai and Wang, 2021) integrates an adversary
to achieve fair outputs for node classification with limited sensitive
attributes, while Graphair (Ling et al., 2022) seeks to learn fair
representations by automated graph data augmentations. FairVGNN (Wang et al.,
2022) tackles the sensitive attribute leakage caused by feature propagation in
GNNs by automatically learning from fair views. Additionally, FairGKD (Zhu et
al., 2023) investigates the fairness performance in different training
strategies and uses distilled knowledge from partial data training to enhance
model fairness. However, directly applying the above methods for GAD poses
significant challenges. A primary issue is the overlap between anomalous
characteristics and sensitive attributes, which complicates the debiasing
process in graphs or node representations. Besides, these methods are
typically designed for or validated on supervised tasks, while the lack of
ground truth is a fundamental issue in anomaly detection. Hence, we propose a
fairness-aware unsupervised GAD method that learns sensitive-irrelevant
representations and detects anomalous nodes within a reconstruct-based
framework.

##  6\. Conclusion

In this paper, we propose DEFEND, a novel disentangle-based framework for fair
graph anomaly detection, aiming to balance fairness and utility in decision-
making. To the best of our knowledge, DEFEND is the first method in enhancing
fairness in the task of graph anomaly detection. DEFEND first introduces
disentangled representation learning to capture informativeness yet sensitive-
irrelevant representations, thereby mitigating societal bias associated with
sensitive attributes within the input graph. Furthermore, to alleviate
discriminatory decisions in anomaly detection, DEFEND reconstructs input
attributes from the sensitive-irrelevant representations and implements a
constraint on the correlation between reconstruction error and predicted
sensitive attributes. The effectiveness of DEFEND has been substantiated
through extensive experiments on real-world datasets, demonstrating its
superiority over several baselines regarding accuracy and fairness.

## 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.
  * Chai et al. (2022) Ziwei Chai, Siqi You, Yang Yang, Shiliang Pu, Jiarong Xu, Haoyang Cai, and Weihao Jiang. 2022.  Can Abnormality be Detected by Graph Neural Networks. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), Vienna, Austria_. 23–29.
  * Chen et al. (2023) April Chen, Ryan A Rossi, Namyong Park, Puja Trivedi, Yu Wang, Tong Yu, Sungchul Kim, Franck Dernoncourt, and Nesreen K Ahmed. 2023.  Fairness-aware graph neural networks: A survey.  _arXiv preprint arXiv:2307.03929_ (2023).
  * Creager et al. (2019) Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. 2019.  Flexibly fair representation learning by disentanglement. In _ICML_. PMLR, 1436–1445.
  * 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_.
  * Deepak and Abraham (2020) P Deepak and Savitha Sam Abraham. 2020.  Fair outlier detection. In _21th International Conference on Web Information Systems Engineering: WISE 2020_. 447–462.
  * Ding et al. (2019) Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. 2019.  Deep anomaly detection on attributed networks. In _Proceedings of the 2019 SIAM International Conference on Data Mining_. SIAM, 594–602.
  * 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.
  * Dong et al. (2023) Yushun Dong, Jing Ma, Song Wang, Chen Chen, and Jundong Li. 2023.  Fairness in graph mining: A survey.  _IEEE Transactions on Knowledge and Data Engineering_ (2023).
  * Duan et al. (2023) Jingcan Duan, Siwei Wang, Pei Zhang, En Zhu, Jingtao Hu, Hu Jin, Yue Liu, and Zhibin Dong. 2023.  Graph anomaly detection via multi-scale contrastive learning networks with augmented view. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 37. 7459–7467.
  * 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. (2020) Haoyi Fan, Fengbin Zhang, and Zuoyong Li. 2020.  Anomalydae: Dual autoencoder for anomaly detection on attributed networks. In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_.
  * 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).
  * He et al. (2023) Junwei He, Qianqian Xu, Yangbangyan Jiang, Zitai Wang, and Qingming Huang. 2023.  ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection.  _arXiv preprint arXiv:2312.14535_ (2023).
  * Huang et al. (2022) Xuanwen Huang, Yang Yang, Yang Wang, Chunping Wang, Zhisheng Zhang, Jiarong Xu, Lei Chen, and Michalis Vazirgiannis. 2022.  Dgraph: A large-scale financial dataset for graph anomaly detection.  _Advances in Neural Information Processing Systems_ 35 (2022), 22765–22777.
  * Jin et al. (2021) Ming Jin, Yixin Liu, Yu Zheng, Lianhua Chi, Yuan-Fang Li, and Shirui Pan. 2021.  Anemone: Graph anomaly detection with multi-scale contrastive learning. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 3122–3126.
  * Kim and Mnih (2018) Hyunjik Kim and Andriy Mnih. 2018.  Disentangling by factorising. In _International conference on machine learning_. PMLR, 2649–2658.
  * Kim et al. (2021) Hyemi Kim, Seungjae Shin, JoonHo Jang, Kyungwoo Song, Weonyoung Joo, Wanmo Kang, and Il-Chul Moon. 2021.  Counterfactual fairness with disentangled causal effect variational autoencoder. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 8128–8136.
  * Kim et al. (2023) Junghoon Kim, Yeonjun In, Kanghoon Yoon, Junmo Lee, and Chanyoung Park. 2023.  Class Label-aware Graph Anomaly Detection. In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management_.
  * Kim et al. (2022) Minseok Kim, Jinoh Oh, Jaeyoung Do, and Sungjin Lee. 2022.  Debiasing Neighbor Aggregation for Graph Neural Network in Recommender Systems. In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_. 4128–4132.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Li et al. (2019) Ao Li, Zhou Qin, Runshi Liu, Yiqun Yang, and Dong Li. 2019.  Spam review detection with graph convolutional networks. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_. 2703–2711.
  * 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 _International Conference on Learning Representations_.
  * Ling et al. (2022) Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou. 2022.  Learning fair graph representations via automated data augmentations. In _The Eleventh International Conference on Learning Representations_.
  * Liu et al. (2022b) Ji Liu, Zenan Li, Yuan Yao, Feng Xu, Xiaoxing Ma, Miao Xu, and Hanghang Tong. 2022b.  Fair representation learning: An alternative to mutual information. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 1088–1097.
  * Liu et al. (2022a) Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, et al. 2022a.  Pygod: A python library for graph outlier detection.  _arXiv preprint arXiv:2204.12095_ (2022).
  * Liu et al. (2021) Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. 2021.  Anomaly detection on attributed networks via contrastive self-supervised learning.  _IEEE transactions on neural networks and learning systems_ 33, 6 (2021), 2378–2392.
  * Ma et al. (2022) Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. 2022.  Learning fair node representations with graph counterfactual fairness. In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_. 695–703.
  * Neo et al. (2024) Neng Kai Nigel Neo, Yeon-Chang Lee, Yiqiao Jin, Sang-Wook Kim, and Srijan Kumar. 2024.  Towards Fair Graph Anomaly Detection: Problem, New Datasets, and Evaluation.  _arXiv preprint arXiv:2402.15988_ (2024).
  * Oh et al. (2022) Changdae Oh, Heeji Won, Junhyuk So, Taero Kim, Yewon Kim, Hosik Choi, and Kyungwoo Song. 2022.  Learning fair representation via distributional contrastive disentanglement. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 1295–1305.
  * Rahman et al. (2019) Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. 2019.  Fairwalk: towards fair graph embedding. In _Proceedings of the 28th International Joint Conference on Artificial Intelligence_. 3289–3295.
  * Roy et al. (2023) Amit Roy, Juan Shu, Jia Li, Carl Yang, Olivier Elshocht, Jeroen Smeets, and Pan Li. 2023.  GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction.  _arXiv preprint arXiv:2306.01951_ (2023).
  * Shekhar et al. (2021) Shubhranshu Shekhar, Neil Shah, and Leman Akoglu. 2021.  Fairod: Fairness-aware outlier detection. In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_. 210–220.
  * Song et al. (2021) Hanyu Song, Peizhao Li, and Hongfu Liu. 2021.  Deep clustering based fair outlier detection. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 1481–1489.
  * Song et al. (2022) Weihao Song, Yushun Dong, Ninghao Liu, and Jundong Li. 2022.  Guide: Group equality informed individual fairness in graph neural networks. In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_.
  * Spinelli et al. (2021) Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. 2021.  Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning.  _IEEE Transactions on Artificial Intelligence_ 3, 3 (2021), 344–354.
  * Sugiyama et al. (2012) Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. 2012.  Density-ratio matching under the Bregman divergence: a unified framework of density-ratio estimation.  _Annals of the Institute of Statistical Mathematics_ 64 (2012), 1009–1044.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Wang et al. (2022) Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr. 2022.  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. (2020) Yongji Wu, Defu Lian, Yiheng Xu, Le Wu, and Enhong Chen. 2020.  Graph convolutional networks with markov random field reasoning for social spammer detection. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 34. 1054–1061.
  * Xu et al. (2022) Zhiming Xu, Xiao Huang, Yue Zhao, Yushun Dong, and Jundong Li. 2022.  Contrastive attributed network anomaly detection with data augmentation. In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_. Springer, 444–457.
  * Zemel et al. (2013) Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. 2013.  Learning fair representations. In _International conference on machine learning_. PMLR, 325–333.
  * 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.
  * Zhang et al. (2022) Ge Zhang, Zhao Li, Jiaming Huang, Jia Wu, Chuan Zhou, Jian Yang, and Jianliang Gao. 2022.  efraudcom: An e-commerce fraud detection system via competitive graph neural networks.  _ACM Transactions on Information Systems (TOIS)_ 40, 3 (2022), 1–29.
  * Zhang and Davidson (2021) Hongjing Zhang and Ian Davidson. 2021.  Towards fair deep anomaly detection. In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_. 138–148.
  * Zhu et al. (2023) Yuchang Zhu, Jintang Li, Liang Chen, and Zibin Zheng. 2023.  The Devil is in the Data: Learning Fair Graph Neural Networks via Partial Knowledge Distillation.  _arXiv e-prints_ (2023), arXiv–2311.

##  Appendix A Details of Experimental Settings

###  A.1. Baselines

In this subsection, we introduce the baselines employed in our experiments,
including GAD methods (i.e., DOMINANT, CoLA, and CONAD), Fairness Regularizers
(i.e., FairOD, Correlation, and HIN), and Graph Debiasers(i.e., FairWalk and
EDITS).

  * •

DOMINANT (Ding et al., 2019) devises a GCN-based autoencoder to detect
anomalies by reconstructing node attributes and graph structure. The node
attribute decoder is the reverse structure of the encoder and the structure
decoder is applied by the dot product. Anomalous nodes are evaluated by
reconstruction errors.

  * •

CoLA (Liu et al., 2021) is a contrastive self-supervised learning framework
for anomaly detection. It conducts a node-subgraph contrast to capture
anomalies that are dissimilar from their local neighbors. Anomalous nodes are
evaluated by the agreement between each node and its neighboring subgraph with
a GNN-based model.

  * •

CONAD (Xu et al., 2022) introduces a contrastive learning framework that
leverages human knowledge through data augmentation to enhance anomaly
detection capabilities. It employs a Siamese graph neural network with a
contrastive loss to encode both the modeled knowledge and the original
attributed networks. Anomalous nodes are evaluated by reconstruction errors.

  * •

FairOD (Shekhar et al., 2021) is a fairness-aware outlier detector on
independent and identically distributed (i.i.d.) data. It devises a
regularization term to prompt the fairness of demographic parity by minimizing
the reconstruction errors $\mathbf{o}$ and the sensitive attributes
$\mathbf{S}$.

(20)
$\mathcal{L}_{DP}^{FairOD}=\left|\frac{\left(\sum_{i=1}^{n}{o}_{i}-\mu_{o}\right)\left(\sum_{i=1}^{n}{s}_{i}-\mu_{s}\right)}{\sigma_{o}\sigma_{S}}\right|$

where $\mu_{o}$ and $\mu_{s}$ represent the means, while $\sigma_{o}$ and
$\sigma_{s}$ denote the corresponding standard deviations of $\mathbf{o}$ and
$\mathbf{S}$, respectively. Besides, it utilizes an approximation of
Discounted Cumulative Gain (DCG) to enforce the group fidelity.

(21)
$\mathcal{L}_{ADCG}^{FairOD}=\sum_{s\in\\{0,1\\}}\left(1-\sum_{\\{v_{i}:s_{i}=s\\}}\frac{2^{{o}_{i}^{base}}-1}{\mathrm{DNM}_{s}}\right),$

where
$\mathrm{DNM}_{s}=\log_{2}\left(1+\sum_{\\{v_{j}:s_{j}=s\\}}\sigma({o}_{j}-{o}_{i})\right)\cdot
IDCG_{s}$ and
${IDCG}_{s}=\sum_{j}^{|\\{v_{j}:s_{j}=s\\}|}\left({2^{{o}_{j}^{base}}-1}/{\log_{2}(1+j)}\right)$.
Here, ${o}_{i}^{base}$ is the reconstruction error of $v_{i}$ in the base
model and $\sigma(\cdot)$ is the Sigmoid function. The overall loss of the
model equipped with FairOD regularizer can be calculated by
$\mathcal{L}=\mathcal{L}_{base}+\lambda\mathcal{L}_{DP}^{FairOD}+\gamma\mathcal{L}_{ADCG}^{FairOD}$,
where $\lambda$ and $\gamma$ are weight parameters.

  * •

Correlation (Shekhar et al., 2021) is an implementation of FairOD, which
measures the correlation between sensitive attributes $\mathbf{S}$ and
reconstruction errors $\mathbf{o}$ using the cosine similarity.

(22)
$\mathcal{L}^{Corr}=\left|\frac{\mathbf{o}\cdot\mathbf{S}}{\sqrt{(\mathbf{o}\cdot\mathbf{o})(\mathbf{S}\cdot\mathbf{S})}}\right|,$

where $(\cdot)$ represents the dot product of two vectors. The overall loss of
the model equipped with the Correlation regularizer can be calculated by
$\mathcal{L}=\mathcal{L}_{base}+\lambda\mathcal{L}^{Corr}$.

  * •

HIN (Zeng et al., 2021) focuses on fair representation learning for
heterogeneous information networks. The demographic parity-based fairness-
aware loss function is calculated by:

(23)
$\mathcal{L}_{DP}^{HIN}=\sum_{k\in\\{0,1\\}}\Bigg{(}\frac{\sum_{\\{v_{i}:s_{i}=1\\}}P(\hat{y}_{i}=k)}{|{\\{v_{i}:s_{i}=1\\}}|}-\frac{\sum_{\\{v_{i}:s_{i}=0\\}}P(\hat{y}_{i}=k)}{|{\\{v_{i}:s_{i}=0\\}}|}\Bigg{)}^{2},$

where $P(\hat{y}_{i}=1)$ denotes the predicted probability of $v_{i}$ to be
identified as an anomalous node. The equal opportunity-based fairness-aware
loss is calculated by:

(24)
$\begin{split}\mathcal{L}_{EO}^{HIN}=\sum_{k\in\\{0,1\\}}\Bigg{(}&\frac{\sum_{\\{v_{i}:s_{i}=1,y=k\\}}Pr(\hat{y}_{i}=k)}{|{\\{v_{i}:s_{i}=1,y=k\\}}|}\\\
&-\frac{\sum_{\\{v_{i}:s_{i}=0,y=k\\}}Pr(\hat{y}_{i}=k)}{|{\\{v_{i}:s_{i}=0,y=k\\}}|}\Bigg{)}^{2}.\end{split}$

As the calculation of $\mathcal{L}_{EO}^{HIN}$ requires task-related labels
and anomaly detection tasks typically lack ground truth labels, we use
$\mathcal{L}_{ADCG}^{FairOD}$ as a replacement to enhance the fairness in
equal opportunity. Thus, the modified overall loss of the model equipped with
HIN regularizer can be calculated by:

(25)
$\mathcal{L}=\mathcal{L}_{base}+\lambda\mathcal{L}_{DP}^{HIN}+\gamma\mathcal{L}_{ADCG}^{FairOD}.$

  * •

FairWalk (Rahman et al., 2019) introduces a fairness-aware embedding method
that generates node embeddings by considering sensitive attributes and the
topology of the graph. It enhances the general random walk algorithm to
capture more diverse neighborhoods, thereby producing embeddings that exhibit
reduced bias.

  * •

EDITS (Dong et al., 2022) is a graph debiasing method for attributed graphs,
mitigating bias present in both graph topology and node features. It minimizes
the approximated Wasserstein distance between the distributions of different
groups for any attribute dimension to enhance group fairness.