Enhancing Fairness in Unsupervised Graph Anomaly Detection through Disentanglement
Authors: Wenjing Chang
Kay Liu
Philip S. Yu
Jianjun Yu
Venue: Accepted by TMLR ()

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 fairness problem, which might result in discriminatory decisions
skewed toward certain demographic groups defined on sensitive attributes (e.g., gender). 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 bias inherent in graphrepresentation learning. Besides, to alleviate discriminatory bias in evaluating anomalies, DEFEND adopts a reconstruction-based method, which concentrates solely on node attributes and avoids incorporating biased graph topology. Additionally, given the inherent association between sensitive-relevant and -irrelevant attributes, DEFEND further constrains the correlation between the reconstruction error and predicted sensitive attributes. Empirical evaluations on real-world datasets reveal that DEFEND performs effectively in GAD and significantly enhances fairness compared to state-of-the-art baselines. Our code is available at https://github.com/AhaChang/DEFEND.

Published in Transactions on Machine Learning Research (03/2025)
Enhancing Fairness in Unsupervised Graph Anomaly Detec- tion through Disentanglement
Wenjing Chang
changuenfing@enic..r
Computer Network Information Center, Chinese Academy of Sciences University of Chinese Academy of Sciences
Kay Liu University of Ilimois Chviagoo
zliu294 druic. edu
Philip S. Yu University of Illinois Chicago
psyuuruic.co edu
Jianjun Yu Computer Network Information Center, Chinese Academy of Sciences
yujj@cnic.a.cor
Reviewed on OpenReview: https: openreview. net/ forum? id- 52R534L53C
Abstract
Graph anomaly detection (GAD) is becoming increasingly crucial in various applications, ranging from financial fraud detection to fake news detection. However, current GAD meth- ods largely overlook the fairness problem, which might result in discriminatory decisions skewed toward certain demographic groups defined on sensitive attributes (e.g., gender). This greatly limits the applicability of these methods in real-world scenarios in light of socictal and ethical restrictions. To address this critical gap, make the first attempt devise a novel
to integrate fairness with utility in GAD decision-making, Specifically, DisEntangle-base based FairnEss-wwer aware a aNomaly Detection framework on the attributed graph, named DEFEND. DEFEND first introduces disentanglement GNNs to capture informa- tive yet sensitive-irrelevant node reprosentations, effectively reducing bias inherent in graph representation learning. Besides, to alleviate discriminatory bias evaluating anomalies, DEFEND adopts reconstruction-bent based method, which concentrates solely on node tributes and avoids incorporating biased graph topology. Additionally, given the inherent sociation between emsitive-relevan and -irrelevant attributes, DEFEND further constrains the correlation between the reconstruction error and predicted sensitive attributes. Empiri- cal evaluations on real-world datasets reveal that DEFEND performs effectively in GAD and significantly enhances fairness compared to saate-of-the-at baselines. Our code is available at htttps://githhii com http:///ihtbbct/aaaaaaaann////a/
1 Introduction
Graph Anomaly Detection (GAD), which aims 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 al. 2022 and spammer detection in social networks {Li et al. 2019 Wu et al.
2020). The ad vancement of Graph Neural Networks (GNNs) (Kipf & Welling 2016: Hamilton et al. 2017
Veličković et al.) 2017) has significantly enhanced the ability of GNN-based GAD methods to accurately
identify anomalies Ding et al., 2019 Chai et al., 2022 Kim et al. 2023 He el al. 2023). However, a recent study (Neo et al. 2024) reveal a concerning trend: current GAD methods exhibit substantial bias in decision.
Given the wide-ranging applications of GAD, particularly within high-stakes domains, the fairness problem cannot be overlooked. Unfair decisions that skew toward certain demographic groups associated with sen-

---

Published in Transactions on Machine Learning Research (03/2025)
sitive attributes (e.g., gender, religion, ethnicity, etc.) 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 undergo strict investigation and even per- manent account suspension. In such scenarios, biased decisions could result in unfairly focusing on certain groups while inadvertently neglecting others. This undermines the effectiveness and reliability of anomaly detection systems and raises critical ethical concerns. To balance fairness and utility in anomaly detection, several methods have been proposed (Deepak & Abraham 2020 Song et al., 2021| Zhang & Davidson, 2021; Shekhar et al. 2021). p. These methods strive to optimize the balance between fairness and anomaly detection performance in the absence of ground truth labels, which presents fundamental challenge in unsupervised anomaly detection. Nevertheless, they primarily focus on independent and identically distributed data, thereby overlooking the societal bias in graphs, which manifests in both node attributes and graph lopology.
The bias graphs poses a significant challenge to achieving fairness in graph-related tasks (Dai & Wang, 2021 Zhu et al. 2023). First, sensitive attributes are inherently spread across other attributes (Deepak & Abraham 2020 Oh et al., 2022), so directly removing them is insufficient to ensure fairness (Neo et al., 2024). For example, the geographic location might correlate with religion and ethnicity. Second, since nodes with similar attributes are more likely to form connections, graph topology is also influenced by sensitive attributes (Rahman et al. 2019 Spinelli et al. 2021). Third, biased topology coupled with the message-passing mechanism in GNNs may inherit or even amplify the inherent bias in graphs (Dai & Wang,
2021 Wang et al. 2022 Zhu et al. 2023 Specifically, representations aggregated from neighboring nodes that share identical sensitive attributes may amplify features of the demographic group, thereby potentially affecting the fairness of the decision-making in GNNs.
Many efforts have been made to explore fairness 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 informatinn from the training graph and implementing the debiased graph for target tasks (Spinelli et al. 2021 Rahman et al. 2019 Dong ot al. )022). However, it is non-trivial to concurrently mitigate bias and preserve the integrity of anomalies, considering the overlap between the features of anomalies unrelated to sensitive altribules and the features of demographic groups linked to sensitive attributes. For instance, an edge might indicate that two nodes share the same sensitive attributes while displaying an anomalous connection. Another prevalent strategy involves training fair GNNs to perform the target task independently of sensitive attributes (Dai & Wang 2021 Zhu et al. 2023). These methods are dedicated to end-to-end supervised node classification, where ground-truth labels are available. Thus, applying them to unsupervised GAD is challenging due to the absence of labels for anomaly detection.
In this paper, we propose a novel DisEntaagloe-bsee ass-arrs-aware aNomaly Detection framework on attributed graphs, named DEFEND. In the first stage, to address the societal bias embedded in both node attributes and graph topology, we 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 sensitive-irrelevant representations into independent subspaces with the guidance of a learnable adversary. In the second stage, given the a absence of ground truth labels and the inherent complex bias in graph topology, we implement an additional decoder that reconstructs node attributes from the well-trained disentangled encoder, utilizing the reconstruction error as the anomaly score. To further alleviate discriminatory bias in detecting anomalics, we introduce fairness constraint that enforces invariance of reconstrretton errors across different sensitive attribute groups, effectively mitigating the influence of correlations between sensitive and the rest attributes. Our main contributions are summarized 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 graph encoder for fair anomaly detection on graphs
Extensive experiments on real-world datasets show that DEFEND achieves a competitive perfor- mance and significantly enhances fairness compared with baselines.
2

---

Published in Transactions on Machine Learning Research (03/2025)
2 Preliminaries
2.1 Problem Definition
Let g = A,,,,X,S) be an attributed graph with N nodes and E edges, where V = (vi,..., ... is the set of nodes. y (0, 1) denotes the anomaly labels, where 1 indicates anomalous node, and y denotes the predicted labels. The adjacency matrix is denoted as A (0, NxNN where Aij 1 if there exists an edge between 2/2 and vy, otherwise, A, 0. X Nxd represents the observed node attribute matrix, while S E Nm represents the sensitive attribute matrix (e.g., gender, religion, ethnicity, etc.). e2 and vy belong to the same demographic group s; 55. Here, m is the total number of sensitive attributes. As described in (Deepak & Abraham 2020; Sarhan et al.) 2020: Oh et al. 2022), the sensitive attribute S is correlated with both the observed attribute X and labels y on many real-world datasets. The goal of fair graph anomaly detection is to provide unbiased prediction against sensitive attributes while achieving satisfactory accuracy simullaaeously. To simplify the problem, in this work, we mainly focus on a single binary sensitive altribule, i.., S E {0, 13 Nx1 We can easily extend our method to more complicated settings as previous studies
CCraager al. 2019 Deepak & Abraham 2020
More details are discussed in Seccion 3.3
2.2 Fairness Metrics
Following (Agarwal et al., 2021 Wang al. 2022 Zhu et al., 2023 we utilize two widely used metries evaluate the lairness of models among demographic groups.
Demographic Parity Dwork et al. (2012) dictates the equal predicted probability across demographic groups. It ensures predictions are statistically unbiased to sensitive attributes, e.g., if gender is a sensitive attribute, ApP implies that the probability of individuals from different genders being classified as anomalous should be identical.
App = IP = 1|s - 0) - P(Ù = 1/s = 1]],
(1)
where ÿ E 13 is the predicted node label, and 0s indicates node o; is a predicted anomaly.
Equal Opportunity (Hardt et al. 2016 requires the same true positive rates of identifying anomalics for each demographic group. Considering gender as sensitive attribule, ARO encourages individuals from different genders to have an equal probability of being correctly identified as anomalous. Given the ground- truth label y E (0.1) where y = denotes v is a truc anomaly, Ago can be defined as:
AEO
PP = 1/s = 0, 1) P = 1/s = 1))-
(2)
3 Proposed Method
We now introduce DEFEND, which aims to identify anomalies without skew towards demographic groups defined on sensitive attributes. The disentangled representation lcarning separates sensitivo-rolevant and sensttive-irelevannt representations in the latent space (see Section 3.1). Fair anomaly detection is achieved through constrained reconstruction error using the disentangled representations (see Section 3.2) We then discuss its generalization capability across diverse sensitive attributes in SSction 3.3 We introduce the train- ing and inference processes in Appendix A and provide a computational complexity analysis in Appendix B
Figure I illustrates the overall workflow of DEFEND, which contains two major phases. Firstly, as shown in the left part of [Fiuree the disentangled fair representation learning phase separates sensitive-relevant representations Z, and sensstive--rrelevannt representations Z, in the latent space. Specifically, a disentangled graph encoder fe maps the node attribute X and graph topology A into independent sensitive-relevant and -irrelevant subspaces. Subsequently, fa and fa decode adjacency matrix Å and node attributes X, respec- tively. Ideally, Zz contains no sensitive information with a well-trained fe- To promote the independence of Ze from Z., we include a learnable adversary Iw- Besides minimizing reconstruction error to obtain informative representations, we also endcavor to accurately infer sensitive attributes from Z,- As shown in the right part of Figure I the unsupervised graph anomaly detection phase identifies anomalies based on sensitive-ine veirreeeeiir representations Zy- However, the reconstruction of attributes and structures may lead
3

---

Published in Transactions on Machine Learning Research (03/2025)
Attribute Decoder
Disentangled Graph Enceder
Attribute Decoder
Disentangled Graph Eneoder:
Zx
fx
Z
F
X
fe
naise
Zg
fa
Z
Adversary
Iw
Decoder
Sensitive Attribute
Anomalyy
Normal
Figure 1: An overview of proposed DEFEND framework. (Teft) Disentangled fair representation learning, The disentangled graph encoder fe can separate sensitive-irrelevant representations Z and sensitive-relevant representations Z. in latent space. (Right) Reconstruct-based graph anomaly detection. The constrained reconstruction error between X and X are used to identify anomalies. $ means fixing model parameters.
to biased outcomes in decision decision-making, considering biases inherent in both attributes and structures. As such, the decoder fo only reconstructs node attributes from 2₂ based on Multi-Layer Perceptron (MLP) without involving graph topology. Moreover, node attributes X inherently have potential correlations with sensitive attributes S, we further constrain the correlation between the reconstruction error and the predicted sensitive attributes.
3.1 Disentangled Fair Representation Learning
Informative sensitive-irrelevant representations crucial for fair and accurate decision-making in GAD, which thoroughly considers features of nodes at both node and structural levels. However, since the potential bias in node altributes and graph topology, GNNs might amplify sensitive information when generating node representations with the message-passnng mechanism (Dai & Wang 2021 Zhu et al. 2023 Previous theoretical insights and empirical evidence have highlighted the effectiveness of disentangled representation
learning separating iesitive-irrelevant representations for augmenting fairness in downstream tasks like
image classification (Creager et. al.] 2019 Oh et al. 2022). We posit. that disentangled representation learning is also feasible to provide informative yet conitive-irrelevee node representations for GAD. The details of disentangled fair representation learning graph-structured data in DEFEND are described as follows.
3.1.1 Disentangled Graph Encoder
Based the assumption that the latent space can be decomposed into two independent subspaces (Creager et al. 2019 Oh et al. 2022]: one associated with sensitive attributes and the other devoid of them, the disentangled graph encoder fe strives to capture informative node representations that are irrelevant to sensitive attributes. For graph data, the posterior distribution of node representations g(Z,, Z, X, A) is dcrived from node attributes X and graph topology A. To achieve disentanglement, it is necessary to establish conditional independence between innreleve-irelleannt representations Z, and sensitive-relevant representations Ze given and A. The variational posterior distribution q(Z,, Z, (2 A) can be defined the product of the individual distributions for Z, and Z,:
Z, qZz, Z. X, A) qZZ X. ())
3
As the disentanglement conducted in latent space, it is crucial capture informative node representa- tions from both node attributes and topological structure. Thus, we adopt GNNs as the backbone of the disentangled graph encoder fer In this work, take Graph Convolutional Network (GCN) (Kipf & Welling, 2016) as an example. For the I-th convolutional layer, the node representation H()) is updated by:
H 1 (H (t-1) A) A)
o D AD H ( """"
(4)
where A A+ID E, A, I is the identity matrix of A, W is the weight matrix at the 1-th layer and the initial node representation H is set to X. Next, we the reparameterization trick to estimate
4

---

Published in Transactions on Machine Learning Research (03/2025)
the sensitive-irrelevant representations 2 with GCN:
2 - - E e~ I),,
(5)
where (0, I) is the standard Gaussian distribution with a mean vector of zeros and an identity covariance matrix The mean matrix 4 = Conv (h, (X, A A) and the log standard deviation matrix log
Conv (Convshr (X, A), A) are obtained by GCNs with shared convolutional layer ConVshr- Following
CCreager et al. 2019
estimate the sensitive-relevant representations Zg in deterministic manner:
Z.
(X A),
(6)
where Conv an additional layer for sensitive representations.
3.1.2 Decoders
In the decoding phase of disentangled representation learning, we reconstruct the attribute matrix X, the adjacency matrix A, and sensitive attributes S. Duc to sonsitive-irrelvvant representations Zμ are condition- ally independent of the given sensitive altributes S, the probability p(S) Z.) can be simplified to p(S)Z.). Consequently, the decoding phase can be formulated by:
p X, SZZ. px (Z)
Z.)z.))..)
(7)
We adopt an attribute decoder far based on GNNs to model the distribution of reconstructed node attributes Zm Z.). Besides, we consider an inner product decoder fa for structure reconstruction:
z Z.) Sigmoid(ZZ))
where Z = Concat(Z,, Z.). Next, to model the conditional probability distribution p(S Z.), we employ a binary classifier, where sensitive attributes are assumed to follow Bernoulli distribution parameterized by the Sigmoid function applied to Z The conditional distribution for sensitive attributes is formulated as:
p(S Z.) Bernoulli (SSiilliiSSSSiiiiii(eei Sig)moddZZ.))
3.1.3 Adversary
To encourage the independence between sensitive-irrelevant representations Z, and sensitive-relevant rep- resentations Z,, is imperative that the aggregate postcrior distribution can be factorized as (Zz, Z,) (Zz.)q(22 (Z.). Thus, employ the Kullback-Leibler (KL) divergence between (Z,,, Z.) and (ZZ,) Z., the disentanglement criteria, which can be expressed KL [g( (q( Z.) (Z.))) Following (Kim &
Mnih 2018 Sugiyama et al. 2012 Creager et al.) 2019h, we adopt a binary adversary Iw to encourage the disentanglement by approximating the log density ratio inherent in the KL divergence term:
KL Z.) 11 (1 (Z.) (2, 2,) log g(Zz,
(Zz))q(Z))
(10)
1. llg ( 1|z,, Z.) log p y Z., Z.)).
where ý = 1 denotes "true' samples from the aggregate posterior (Z, Z,) and ý = 0 denotes 'fake' samples from the product of the marginals (Zzz) (Z..). Specifically, we implement an MLP as gw to predict whether the sonsitive-irrelevant representation z and the sonsitive-relevant representation z! are from the same node.
3.1.4 Learning Objective
We optimize the disentangled graph encoder fe, structure decoder fa, and attribute decoder fa from three aspects, including the variational lower bound term, disentanglement term, and predictiveness term. First, the variational lower bound term comprises a reconstruction term and a KL divergence regularization term. The reconstruction term defined as:
Lree Z. (1--)log Z.) clogo( Z.)].
(11)
5

---

Published in Transactions on Machine Learning Research (03/2025)
where the first term is the reconstruction error for node attributes and the second term is for graph topology. Moreover, ox is the weight coefficient for automated balancing the impact of structure and attribute reconstruction (Liu et al. 2022b), where 0 A and ox denotes the standard deviations of A and X, respectively. The KL divergence regularization term (Kingma 2013) is employed to minimize the KL divergence between the posterior distribution (Z 2,|X, A) and the prior distribution p(Z Z.). Thus, the variational lower bound term can be formulated as:
Cuee Cree (Z,, 2, p(Z,, Z.)],
(12)
where p(zz, Z.) ((Z)))(Z..) under the assumption that Zu and Z, are independent. The prior dis- tributions p(Z)) and p(Z)) are modeled by the standard Gaussian distribution and uniform distribution, respectively. Next, the disentanglement term, which encourages the separation of sensitive-relevant and -irrelevant representations as detailed in Eq. (10), is calculated as follows:
Ldi = Ex Ex xt - log p(ū = 1|2 2 - log = 012 z.).
(13)
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 not. Thus, DEFEND incorporates predietiveness term to align the sensitive representation Z. closely with the given sensitive attributes S:
Spre = E,, (X,)) log p (S),.)
(14)
The overall loss for optimizing fe, Ja and Se can be defined as:
Ltotal = L + YLiss + aCpre:
(15)
where a and y are the weight coefficients to control the impact of the predictiveness and disentanglement terms relative to the variational lower bound term, respectively.
To train the binary adversary Jur, the true sample (x x is sampled from the aggregale posterior g(Z,, Zs) while the fake sample (z), z is sampled from the product of marginal posterior distributions q( (Zz))q(Z, (Z.). The adversarial loss is formulated as:
Lado Eaj Z... log = 1|2 zi)) + "t log[1 - p(ū = =0/z 21,]
(16)
where 5 = denotes true samples and 0 denotes fake samples.
The optimizations of fe, fo and fa using Liotal and using Ladv are conducted adversarially. A well- trained disentangled graph encoder fe, which effectively separates sonsitive-irrelevant representations from node attributes and graph topology, can be adeptly employed in downstream tasks for enhancing fairness.
3.2 Graph Anomaly Detection
Next, the primary objective is to detect anomalies unbiased to any demographic groups based on deterministic sensitive-irrelevant representations Z, = μu. Since anomalies typically significantly deviate from the majority of nodes, reconstruction error has been widely used to measure anomaly scores (Ding et al.) 2019 Fan al.
2020 Shekhar et. al. 2021 ). Considering the potential bias in graph topology demonstrated in previous
studies (Rahman al. 2019 Spinelli et al. 2021 Zhu et al.) 2023), we solely reconstruct node attributes and employ MLP as the backbone of the attribute decoder fo to mitigate the impact of biased topology during the message- message-passing process. The anomaly score is evaluated by reconstructing node attributes X from sensitive-irrellvant representations Z,:
O = ||x
11
(17)
where X (Z, 2.) and 2, denotes shuffled variant of Z Additionally, since sensitive attributes are correlated with observed node attributes (Deepak & Abraham 2020 Saahan al. 2020 Oh et al. (2022) and Z, is supposed to be devoid of sensitive information, the reconstruction error inevitably correlates with
6

---

Published in Transactions on Machine Learning Research (03/2025)
sensitive attributes. To mitigate the impact of this correlation and prevent directly leveraging sensitive attributes, we propose correlation constraint term, which measures the absolute correlation between the reconstruction error o, and predicted sensitive attributes z
(Eiev Noo 12ss)
Leorr
(18)
0s0zs
where Mo and Pas are the corresponding means, while on and 2s are the standard deviations of and Z..
3.2.1 Learning Objective
In the anomaly detection phase, the encoder fe is set to be non-trainable, as has already mastered the separation of sensitive-relevant and -irrelevant representations during the disentangled represcntation learning phase. Accordingly, the optimization exclusively concentrated on the decoder Sa- The overall loss consisting of the reconstruction term and the correlation constraints term can be formulated as:
Lad = Cree + 3.oorrs
(19)
where LX Σ. of is the attribute reconstruction loss and 8 is the penalty of sensitive information X.
3.3 Discussion
We analyze the generalization of DEFEND on various types of sensitive attributes. (1) Multiple Bi- nary Sensitive Attributes. Let s [s_,s]_ s'.........."" s"""] denotes the scnsitive attributes for cach node, where s² (0, j < m). The disentanglement between sensitive--rrelevann representations Zg and sensitive-relevant representations Z, E Nx requires that Z, is independent of each sensitive attribute Z!!) Thus, Ze and Zg are disentangled if the aggregate posterior distribution can be factorized as p(Z.. Z.) II, P(Z.))) (2) Single Categorical/ Contriaal//oniuuusss Sensitive Attributes. With single binary scnsi- live altributes, the conditional distribution p(SIZ,) is lypically modeled by a Bernoulli distribution. If with categorical attributes, it shifts to a Multinomial distribution, i.e. p(S]Z.) = (Saiiiommal(SSSftMaaaa(( Similarly, for continuous attributes, p.)) can be modeled by a Gaussian distribution.
4 Experiments
4.1 Experimental Setup
Datasets. We employ three real-world datasets for fair GAD, which provide both real sensitive attributes and ground-truth labels for GAD. In Reddit and Twitter (Neo et al. 2024) datasets, the sensitive attribute is the political leaning of users, while the anomaly label assigned misinformation spreaders. The Credit (Agarwal et al.) 2021 dataset focuses payment default detection, with age the sensitive attribute.
Details of these datasets are summarized in Table 1. More details are rntrodee in Appendix C
Table 1: Statistics of datasets. PG denotes the ratio of the minority and majority group and Pa denotes the ratio of the anomalies and normal nodes,
Dataset # Nodes
# Edless
# Auributes
Poi
PA
Sensitive Attributes
Anomaly Labels
Reddit 9,892
1,211,748
0.1502
0.1584
Political leauing
Misinformation spreader Misinformation spreader
Twitter 47.712
468,697
780
0.1365
0.0713
Political leaning
Credit. 30,000
1,436,858
0.0983
0.2840
Age
Payment default
Basclines. We compare DEFEND with (1) GAD methods, including DOMINANT Ding et al. 2019
CoLA (Liu et al. )021), CONAD (Xu et al. 2022). and VGOD (Huang el al. 2023 (2) GAD mel hods
augmented with Fairness Regularizers like FairOD Shekhar et al. 2021), HIN (Zng et al. 2021 and
Correlation (Shckhar et al. 2021). which incorporate fairness constraints into optimization process; (3)
GAD methods operated on graphs pre-processed by Graph Debiasers, such as FairWalk (Rahman et al.
2019h and EDITS (Dong al. 2022). The details of baselines are introduced in Appendix D)
7

---

Published in Transactions on Machine Learning Research (03/2025)
Table 2: Comparison results of DEFEND against all baseline methods on Twitter. denotes larger values are better, whereas & denotes lower values are preferable. The bost and sccond best performances are highlighted in bold and underlined, respectively.
AUC-ROC 1
AUC-PR
Apr
Ago
Comp.
Avg. Rank
DOMINANT
56.4911.61
8,9240155
4.33::0477
4.51:0.44
-29.36
13.25
CoLA
43.74+1.08
5,23+0.15
2.63+0322
2.47+1008
-2206
18.375
CONAD
56.12+0.73
8.3+0.17
4.08+0.47
4.48+0.35
-2.544
13.25
VGOD
73.59+0.31
16.0240.72
12.56+1.01
11.49+1.84
-20.37
DOMINANT
53.06+0.81
8.17+0.43
1.32+0.27
0.2740.35
-27.29
11.75
CoLA
49.02+0.54
6.34+0.23
0,23+0.14
0.34+0.16
-31.14
10.75
FairWalk
CONAD
03.36:1.70
8.3240.42
1.0000.18
1.3740.39
-20.92
VGOD
60.2110.26
9.14+0.15
9.8420.27
4.9840.37
-31.40
14.25
DOMINANT
53.79
8.7510.06
2.6310.05
2,2110.15
-28.23
12.75
CoLA
1..6
5.70
18410.30
1.030.882 8.2
-36.48
14.25
EDITS
CONAD
53.83+0.24
8.7540.06
2.6240.03
2.1620.13
-28.13
11.875
VGOD
82.06:10.87
25.75:11.40
20. 40.43:11.42
22.32:12455
-20.87
13
DOMINANT
53.69
7
2.50+11551
2.4911.52
-29.42
14.25
CoLA
45.81+7.40
6.29+1.52
1.95
1.23+
-37.01
14.625
FairOD)
CONAD
57.09+0.443
9.08++0.13
4.48-40.45
0.59-
-28.83
13.75
VGOD
76.27:1112
15.56:10.54
9.75
5.61+11667
-9.46
12.5
DOMINANT
54.07+2.22
8.23+0079
1.50
3.51+00.6
-29.64
13
CoLA
48.08+5.31
6.49+11188
2.38+
0.62++0.69
-34.36
12.75
HIN
CONAD
53.7442277
8.124:102
2.59-11.36
3.34
-30.00
14.25
VGOD
81.58+1888
18.86++1.00
12.52+0.911
9.32+
-7.33
12.5
DOMINANT
56.21+0060
8.81+00114
0.22
0.58+0.229
-29.71
14.25
CoLA
28.65=2.88
6,29:0.48
3.32+1118
3.42422.10
-37.73
17.875
Correlation
CONAD
55.94+0.71
8.76+0.17
4.00:0.44
4.52+0.31
-29.75
14.25
VGOD
71.78+0.58
11.80+0.24
5.22+0056
0.76+#0.33
-8.33
8.75
Qurs
DEFEND
75.59:22.00
11.55.0779
0.7240.70
0. 0.7940.61
0
3.75
Evaluation metrics. Following Ding et al. 2019 Liu et al., 2021 Xu el al. 2022 Chai et al. 2022 Neo
et al. 2024), we evaluate the anomaly detection performance with the Area Under the Receiver Operating Characteristic Curve (AUC-ROC) and the Area Under the Precision-Recall Curve (AUC-PR). Higher AUC-ROC and AUC-PR indicate superior anomaly detoction capabilities. Regarding demographic fairness, we adopt Demographic Parity (ADp) and Equal Opportunity (A EO) following (Dai & Wang, 2021 Dong et al. 2022p. The concepts are detailed in [Section 2.2] Lower ADP and AgO suggest better fairness. To quantitatively exhibit the performance tradc-offs, we introduce Average Rank of two accuracy metrics and two fairness metrics (Wang et al. 2022 Guo et al.) 2023) and Composite Score that reflects the combined performance improvement relative to our proposed DEFEND across all metrics.
Implementation details. For DEFEND, we use 2-layer GCN for the disentangled graph encoder Se and attribute decoder fer and 2-layer MLP for the decoder fo in the anomaly detection phase. The hidden dimension of each layer is fixed to be 64. We employ the Adam optimizer with learning rate set to 0.001 for Reddit and Credit datasets and 0.005 for Twitter. 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 fo for 100 epochs. We tune a and y in Equation 15 from f0.1. 0.5, 1.0, 1.5, 2.0, 2,5],, and the weight of correlation constrains 3 in Eqqation 19 from {le- 15, 5e - 15, le 10, 5e 10, le - -9), respectively. We conduct all experiments on one Linux server with an NVIDIA TESLA A800 GPU (80 GB RAM). We run all methods ten times and report the average rosults to prevent extreme cases. More implementation details of basclines are described in Appendix E
4.2
Performance Comparison
4.2.1
Fairness and Utility Performance
Table 2
Table 3 and Table 4 show the fairness (ADp and Ago) and utility (AUC-ROC and AUC-PR) performance of DEFEND and all baselines on Twitter and Reddit, respectively. We have the following ob-
8

---

Published in Transactions on Machine Learning Research (03/2025)
Table 3: Comparison results of DEFEND against all baseline methods on Reddit, f denotes larger values are better, whereas & denotes lower values preferable. The bost and sccond best performances are highlighted in bold and underlined, respectively. OOM indicates out of memory.
AUC-ROC
AUC-PR
App
Ago
Comp.
Avg.
Rank
DOMINANT
60.82.10.09
20.02.10.04
13:20
5.59:1..1
-13.01
10.25
CoLA
45.20=#0.98
17.90=1.54
4.95+1178
4.06=1.85
-20.97
12.5
CONAD
60.81+0.10
20.02=00.05
13.32++0.33
5.70=0.37
11.25
11.5
VGOD
72.0110.93
39.3842.45
6.16
46.7916.09
-52.93
12
DOMINANT
51.26
0.655
2.45+-0.79
1.97+1.25
-13.67
CoLA
51.12:10.3
0..8
0.69:10.37
0.60:0.59
Walk
CONAD
51.26:1.88
14.05 14.68=1.15
2. 2.49=1.28
2.52+1.58
-14.13
11.25
VGOD
67.08.10611
28 5..00.288
31.9910.53
29.80.11.02
-41.33
11.75
DOMINANT
OOM
OOM
OOM
OOM
CoLA
54.41+.662
23.13+3.67
23.74+5.77
21. 21.00+33.38
-2226
14
EDITS
CONAD
OOM
OOM
OOM
OOM
VGOD
OOM
OOM
OOM
OOM
DOMINANT
60.9410.07
19.9711.008
13.0810.21
5.04-0.15
-12.27
9.5
CoLA
45.76+10.23
15.77+5.42
13.26+6624
5.98-5583
-32.77
16.5
FairOD
CONAD
60.5340.11
19. 09.5320.08
12.37-0.11
6.02-0.11
-12.59
11
VGOD
71.65+2..55
30.40#4.98
28.6647.70
37.74+4.28
-39.41
11.5
DOMINANT
60.9110.00
20.10.10.04
13.3810.10
5.6910.22
-13.12
CoLA
45.52+1.44
18.5 18.59-1.68
4.58+2.50
4.43-2.28
19.99
12.25
HIN
CONAD
60 8911..1
20 00
13.3510.21
5.81-0455
-13.27
11.25
VGOD
72.60:3.332
26. 36.18
17.9216.12
30.39199338
-24.53
10.75
DOMINANT
60.38:10.08
19.57
12.27:10.25
4.42:10.20
-11.80
10.25
CoLA
50.94+6.37
15.29=3.50
9.63+7.26
11.6848.23 23
-30.14
15.25
Correlation
CONAD
59.51+0.33
18.86=0.28
10.94=0.74
3.80=0.35
-11.43
10.25
VGOD
75.6813..7
31.09.2..8
32.42.19.53
12.72.19.6
-43.3
Ours
DEFEND
6..67+0042
06.46+0.225
0.94++0.72
1.13+0.81
0
8
DEFEND
COLA+FaIrOD
VGOD+FairOD
DOMINANT+FairOD DOMINANT +HIN
VGOD+HIN
CONAD Correlaton
COLA+Correlation
-Grr-Coorllation
DOMINANT+CCrrelaate
(a) Reddit
(b) Twitter
(c) Credit
85
85
65
875 75
75
&0 60
66
65
055
55
55
50
45
45
45
35
35
109
10
100
10
109
10
10a
4so(%)
Aea(%)
3e)(%)
Figure 2: Fairness- Utility trade-off curves of different methods on three datasets. The upper-left corner is optimal, which has high AUC-ROC and low AzO.
servations: (1) DEFEND demonstrates superior performance in balancing fairness and accuracy trade-offs. To evaluate this trade-off quantitatively, we analyze the average ranks and relative improve- ments across two accuracy metrics and two fairness metrics. The runner-up performing model shows a 7.33% decline in performance compared to DEFEND, with DEFEND achieving average rank of 3.75 versus 8.75 for the runner-up model on Twitter. Figure 2 illustrates the fairness-utility tradc-off curve, which further validates the superiority of DEFEND (detailed analysis provided in Section 4.2.2). (2) Standard GAD methods exhibit clear trade-off between accuracy and fairness. For instance, VGOD with Cor- relation achieves superior detoction performance with AUC-ROC reaching 75.68% and AUC-PR attaining 31.09%, but demonstrates substantial fairness violations with ADP at 32.42% and Ago at 42.72% on Reddit. This observation reveals inherent tension between detection capability and fairness in existing approaches.

---

Published in Transactions on Machine Learning Research (03/2025)
Table 4: Comparison results of DEFEND against all baseline methods on Credit. 1 denotes larger values are better, whereas & denotes lower values preferable. The bost and sccond best performances are highlighted in bold and underlined, respectively.
AUC-ROCT
AUC-PR 1
App 4
Aso
Comp,
Avg. Rank
DOMINANT
52.3114.14
25.28=1.33
1.6==1.00
2.34=1.62
-2.11
8.75
CoLA
46.31+00.4
18.96=0.54
3.04=1.22
1.48=1.26
-15.01
CONAD
53 33.68.15.28
26.02-5.03
3.91=2.77
4.1942.61
-4.16
10.75
VGOD
54.8110.900
26.02-0.86
17.544188
13.5941884
-26.06
14.75
DOMINANT
19.50+0.40
21.78=0.44
0.67=0.74
1.50=0.99
-6.60
11.75
CoLA
50.29.10.17
22.63-0.31
0.32-0028
0.22.10:3
-6.32
WailWalk
CONAD
19.76.10.55
21.91-0.63
1.21=0.83
1,0210.80
-3.38
10.25
VGOD
10.3010.10
22.00=0.06
31.5710.94
29.43:1.17
-65.44
22
DOMINANT
19.19:11.71
22.06-1.85
2.99
2.73+1.59
-10.23
14.5
CoLA
19.82.11001
21781
2.77
2.95.12.40
-13.54
16.25
EDITS
CONAD
1..50
22.36-1.14
5.23
4.31
-12.14
17
VGOD
46.61+3.23
20.52-1.61
1.32++10.38
9.27=9.20
-27.23
21.75
DOMINANT
52.59-+4..0
24.64-4.29
4.37-3.54
3.04+3.67
-7.95
13.5
CoLA
6..43:16.33
21.24
5.99
6.09
-21.18
20.25
FairOD
CONAD
55.03+5.39
27.38=5.14
4.10=3.59
4.02=3.66
-1.48
8.5
VGOD
1..70:13.32
26.87=1.339
16. 1.229
13.52+1.35
-22.98
DOMINANT
51.98
24.88-4.38
1.81-1 1.81-1.28
1.60
-3.11
10
CoLA
46.31:0.94
18.96=0.54
3.06=1.20
1.45=1.28
-15.01
15.5
HIN
CONAD
53.77+3.69
25.40=3.54
2.73=1.48
2.66=1.71
-1.99
8.25
VGOD
57.26+33.19
28.15=2.66
13.54+4.17
11.11+3.78
-15.00
11.5
DOMINANT
52.37114.11
25.33_4.28
1.5_0.99
2.2711662
-1.87
7.75
CoLA
50.5817.66
23.33=5.34
4.92-3.18
6.3224114
-13.10
15.75
Correlation
CONAD
53.0 03.6815.26
26.02=5.03
3.87=2.78
4.13=2.55
-4.07
10.25
VGOD
66.86.11.10
26.85_0.99
12.42.1142
8.2711.90
-13.75
11.75
Ours
DEFEND
55 100
23.70-0.45
1.78=1.12
1.57.1.00
0.00
7.25
(3) The integration of graph debiasers and fairness regularizers typically improves fairness. For example, DOMINANT with Falk achieves better fairness with App of 2.45% and AgO of 1.97%, while DOMINANT with FairOD achieves better fairness with ADP 13.08% and Ago of 5.04% on Reddit. However, these fairness improvements sometimes comes the cost of reduced detection performance, c.g. AUC-ROC of DOMINANT with FairWalk dropping from 60.82% 51.26% Reddit.
4.2.2 Trade-off between Fairness and Utility
We extend analysis comparative evaluation of the fairness-utility trade-off performance of DEFEND with GAD methods incorporating fairness regularizers. We choose A to measure fairness and AUC-ROC for utility 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 coupled with a low Ago. Specifically, a high AUC-ROC signified proficient detection of both normal and anomalous nodes, whereas a low AEO indicates an equivalent probability of correctly identifying anomalies across different demographic groups. In contrast, the upper-right corner represents high performance at the cost of poor fairness, while the lower-left exhibits strong fairness but compromised performance. From Figure 2 can observe the trade-off curve of DEFEND exhibits superior distribution near the optimal point than the baselines.
4.3 Ablation Study
We conduct ablation studies to evaluate the effectiveness of key components of DEFEND. We verify the performance of four variants of DEFEND: (1) DEFEND without correlation constraints term Equa-
tion 19 in anomaly detection (DEFEND-C), (2) DEFEND without the disentangled representation learning (DEFEND-D). (3) DEFEND without the adversary Iu in disentangled representation learning (DEFEND-
10

---

Published in Transactions on Machine Learning Research (03/2025)
Table 5: Comparison results of DEFEND and its variants. 1 denotes larger values are better, whereas & denotes lower values preferable. The best and second best performances are highlighted in bold and underlined, respectively.
Dataset
Method
AUCCROC
AUC-PR f
App
ARO
Comp.
Avg. Rank
DEFEND-D
64.41+1.23
20.50+0.82
14.36+1.23
13.57=1666
-18.08
3
DEFEND-C
64.5410..7
20.43-0.45
13.9511.79
12.31
-16.55
3
Reddit
DEFEND-A
60.4411.06
16.39=0.41
1.64:11.36
2.53:1199
-2.4
3.5
DEFEND+S
54.74+1.02
14.78=0.33
0.90+-0.54
1.5++
-7.94
3.25
DEFEND
60.67+00.2
16.46-0.25
0.94++0.72
1.13+0.81
0.00
2.25
DEFEND-D
87.44.10.14
23.63-0.199
13.5310.22
13.85.1.200
-4.24
3
DEFEND-C
87.58+0.16
23.85++027
15.86=0.47
00.97
-5.67
3
Twitter
DEFEND-
83.29+44.0
18.83=5.34
8.89+7.18
8.37+7.03
-1.07
3
DEFEND+S
50.15:10.74
6.4840.13
1.28:10.19
1.50:1.21
-32.17
3.5
DEFEND
76.5942..0
11.85=0.79
0.72+0.770
0.79:10.61
0.00
2.5
DEFEND-D
67.60
36.12.10.27
18,98
22.04
-13.06
3
DEPEND-C
67.23-11.04
33.83-113
18.4211.07
20.96:11.77
-12.08
3
Credit
DEFEND-A
54.69:11.27
23.47=0.36
1.56:00799
2.55
-1.60
3.25
DEFEND+S
49.08+1.35
21.65-0.75
1.33+1.61
1.66+1.25
-8.03
3.25
DEFEND
55.41+1.800
23.70=0.45
1.78+1.12
1.57+1.00
0.00
2.5
A). (4) DEFEND with dot product decoder to reconstruct the graph structure for anomaly detection (DEFEND+S). The results are shown in Table 5
(1) DEFEND outperforms all variants in fairness, which validates the importance of each component promoting fairness for GAD. Nevertheless, the accuracy of DEFEND is surpassed by several variants, such DEFEND-C and DEFEND-D, likely due to the stringent fairness requirements. As illustrratd in Figure (b), relaxing the fairness constraints can improve utility performance. Specifically, the trade-off curve shows that DEFEND achieves an AUC-ROC of nearly 80% with AEO of about 1.5%. In this case, DEFEND not only exceeds its variants in fairness but also maintains a comparable utility performance to them. (2) The fairness of DEFEND-C is significantly worse than DEFEND, indicating a notable correlation between reconstruction error and sensitive attributes. (3) The fairness performance of DEFEND-D further drops than DEFEND, highlighting the efficacy of disentangled sensitive-irrelevant representations in enhancing fairness in downstream tasks. For example, the Ago of DEFEND-D improves 1% and 12% than that of DEFEND-C and DEFEND on Reddit, respectively. (4) DEFEND-A underscores the effectiveness of the adversary in enhancing fairness, although this comes at cost of accuracy. For instance, the improvement in AUC-ROC from 75.59% to 83.29% is accompanied by a considerable decrease in ADP from 0.72% to 8.89%. In some cases, sacrificing partial accuracy to achieve higher fairness is a justified trade-off. (5) Compared to DEFEND+S, DEFEND not only achieves superior accuracy but also demonstrates enhanced fairness in most cases, which suggests that biased graph topology, negatively impacts the performance of reconstruct-baset GAD method. This finding supports our choice avoid structure reconstruction in the anomaly detection phase.
The following observations can be made from Table 5
4.4 Parameter Analysis
In this section, we investigate the impact of three key parameters within DEFEND on Reddit, including a and y controlling the weight of prediction term and disentanglement term in disentangled representation learning, while controlling the weight of correlation constraints in the anomaly detection phase.
4.4.1 Impact of a and
To investigate the influence of predictiveness and disentanglement terms, We train DEFEND with the values of a and y among {0.1, 0.5, 1.0, 1.5, 2.0, 2.5, 5.0). The results in terms of AUC-ROC and Ago are presented in Figure 3 (a) and Figure 3 (b), respectively. Figure 3 (a) reveals that the anomaly detection efficacy remains substantially stable when a 2 2.0 and 7 1.0, which represents an optimal range for anomaly detection capabilities. When 7 2 1.0, there is marked enhancement in fairness at the expense of rapid decline
11

---

Published in Transactions on Machine Learning Research (03/2025)
in accuracy. This trade-off occurs because larger y forces the model to achieve more similar predictions across demographic groups, potentially compromising its ability to identify true anomalies. Besides, a reduction in a alone significantly decreases both AUC-ROC and Ago. It underscores that without accurate sensitive attribute prediction, the model fails to effectively disentangle the reprosentations, leading to both poor detection performance and unfair predictions. Therefore, selecting appropriate values for a and y is instrumental in navigating the tradcoff between anomaly detection accuracy and fairness.
62
12
60.5
AUC-ROC
58
Acal
60.0
55
AUC-ROC (1)
-4
25
05
0.5
2 2
Aeo ( (4)
1.
2025 hu
20
25
12
20
20
50
30
50
10
10 12 10
10
B
(a) AUC-ROC (%)
(b) (5)
Figure 3: Impacts of varying predictiveness term weight a and disentanglement term weight y in Equation 15 on Reddit dataset in terms of AUC-ROC and Ago-
Figure 4: Impacts of varying correlation con- straints weight 3 in Equation 19 on Reddit.
4.4.2 Impact of? /3
To evaluate the effect of the constraint term, further train DEFEND with different values of among {le 15, 5e 15, le 12, 5e 12, le 10, 5e 10, le 9, 5e - 9} on Reddit. The results are depicted in Figure 4 First, we can observe that the Ago decreases more than 10% while the AUC-ROC witnesses a marginal decline of nearly 4% at 3 around 5e 12. This favorable trade-off demonstrates that our constraint mechanism effectively reduces the model's reliance on sensitive information during anomaly scoring while largely preserving its detection capability.
emphasizes the necessity of integrating constraints within the reconstruction-batt based evaluation of anomalous nodes, considering the interrelation between input and sensitive attributes. Moreover, it is evident that both AUC-ROC and Ago exhibit decrement the weight assigned to correlation constraints increases. It reveals that stronger constraints force the reconstruction process to be more independent of sensitive attributes, leading to fairer but potentially less discriminative representations. The judicious selection of 8 is crucial for the trade-off between utility and fairness.
5 Related Work
5.1 Graph Anomaly Detection
Graph anomaly detection (GAD) has drawn rising interest since graph-structured data becoming increas- ingly prevalent in complex real-world systems. Given the absence of ground truth anomaly labels, many GAD methods focus on an unsupervised manner. Autoencoder a prominent paradigm in this domain, which hypothesizes that the decoder cannot properly reconstruct anomalies deviating significantly from the majority. DOMINANT (Ding et al. 2019) employs GCN-based autoencoder and evaluates anomalies based the reconstruction errors of node attributes and graph topology. AnomalyDAE (Fan et al. 2020) adopts dual autoencoder structure to capture the cross- modality interactions between topology and node attributes. GAD-NR (Roy et al. (023) further incorporates neighborhood reconstruction. Contrastive learning is an- other prevalent self-supervised paradigm in GAD. CoLA (Liu el 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. and GRADATE (Duan et al. 2023) incor- porates subgraph-subgraph contrast to explore multi-level characteristics. Several studies also investigate
anomaly detection across different levels of supervision (Chang al. 2024 Xu et al. 2024 Liu et. al. 2024
12

---

Published in Transactions on Machine Learning Research (03/2025)
2025
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 toward sensitive attributes.
5.2 Fairness on Graphs
Numerous studies have been conducted to mitigate source bias in training data to promote fairness in docision-making for graph learning tasks (Dong et al. 2023 Chen et al. 2023). Graph debiasing methods involve removing bias from the inpul graph before conducling larget lasks. 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 & Wang 2021) integrates an adversary to achieve fair outputs for node classífication 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 Icakage 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 poscs significant challenges. A primary issue is the overlap between anomalous charactoristics and sensitive altributes, which complicates the debiasing process. Besides, these methods are typically designed for or validated supervised tasks, while the lack of ground truth is fundamental issue in anomaly detection.
5.3 Fair Representation Learning
Fair representation learning has shown great success in learning representations free from sensitive infor- mation while maintaining downstream task-related information for decision-making (Zemel et al. 2013 Liu et al., 2022a). Disentangled representation learning provides a novel perspective 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 (Creager et al. 2019 Kim et al. 2021 Oh et al., 2022), its applica- bility on unsupervised GAD is non-trivial. The first challenge involves effectively encoding node attributes and graph topology into disentangled i.i.d. representations while preserving the information essential for anomaly detection. An additional challenge lies in achieving fair GAD based on sensitive-irrelevan repre- sentations. In prior studies, disentangled sensitive-ireelevant representations are directly used for supervised downstream tasks (Creager al., 2019; Oh et al. 2022). However, in unsupervised GAD, where labels effective criterion for mecision-making. Considering
are not available, the reconstruction error serves the correlation between sensitive altributes and other altributes, as well as the connections influenced by sensitive attributes, direct reconstruction of the original graph may result in biased decisions.
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 inreetive-rreleeannt representations, thereby mitigating socictal bias associated with sensitive attributes within the input graph. Furthermore, to alleviate discrimi- nalory decisions in anomaly detection, DEFEND reconstructs input altributes from the sensitive-irrelevanl 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. We discuss limitations and future work in Appendix F
13

---

Published in Transactions on Machine Learning Research (03/2025)
Acknowledgments
This research is supported by a grant from the National Key Research and Development Program of China N5..2022YFF0711000 and the CAS 145 Informatization ion Project CAS- WX2022GC-0301. This work is sup- ported in part by NSF under grants I11-2106758 and POSE-2346158. Jianjun Yu is the corresponding author.
References
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pp. 2114-2124. PMLR, 2021.
Ziwei Chai, Siqi You, Yang Yang, Shiliang Pu, Jiarong Xu, Haoyang Cai, and Weihao Jiang, Can abnormality be detected by graph neural networks. In Proceedings of the T'wetty-Ninth on Artificial Intelligence (IJCAT), Vienna, Austria, pp. 23 23-29, 2022.
Ninth International Joint Conference
Wenjing Chang, Kay Liu, Kaize Ding, Philip S Yu, and Jianjun Yu. Multitask active learning for graph anomaly detection. arXvv preprint Sft:2401.12110 2024.
April Chen, Ryan Rossi, Namyong Park, Puja Trivedi, Yu Wang, Tong Yu, Sungchul Kim, Franck Der- noncourt, and Nesreen K Ahmed. Fairness-aware graph neural networks: A survey, arXiv preprint arXiv:2307.03929, 2023.
Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In JCML, pp. 1436 1445. PMLR, 2019.
Enyan Dai and Suhang Wang. Say to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, 2021.
P Deepak and Savitha Sam Abraham. Fair outlier detection. In 21th International Conference on Web Information Systems Engineering: WISE 2020, pp. 447 462, 2020.
Kaize Ding, Jundong Li, Rohit Bhanushali, and Huan Liu. Deep anomaly detection on attributed networks. In Proceedings of the 2019 SIAM International Conference on Data Mining, pp. 594 602. SIAM, 2019.
Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, pp. 1259- 2022.
Yushum Dong, Jing Ma, Song Wang, Chen Chen, and Jundong Li. Fairness in graph mining: A survey, IEEE Transactions on Knowledge and Data Engineering, 2023.
Jingcan Duan, Siwei Wang, Pei Zhang, En Zhu, Jingtao Hu, Hu Jin, Yue Liu, and Zhibin Dong, Graph anomaly detection via multi-scale contrastive learning networks with augmented view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 7459 7467, 2023.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceediings of the 3rd innovations in theoretical compuler science conference, 2012.
Haoyi Fan, Fengbin Zhang, and Zuoyong Li. Anomalydae: Dual autoencoder for anomaly detection on attributed networks. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2020.
Zhimeng Guo, Jialiang Li, Teng Xiao, Yao Ma, and Suhang Wang. Towards fair graph neural networks via graph counterfactual. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 669 678, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
14

---

Published in Transactions on Machine Learning Research (03/2025)
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Junwei He, Qianqian Xu, Yangbangyan Jiang, Zitai Wang, and Qingming Huang. Ada-gad: Anomaly- denoised autoencoders for graph anomaly detection. arXiv preprint Xiv:2331 14535, 2023.
Xuanwen Huang, Yang Yang, Yang Wang, Chunping Wang, Zhisheng Zhang, Jiarong Xu, Lei Chen, and Michalis Vazirgiannis. Dgraph: large-scale financial dataset for graph anomaly detection. Advances in Newral Information Processing Systems, 35:22765 22777, 2022.
Yihong Huang, Liping Wang, Fan Zhang, and Xuemin Lin. Unsupervised graph outlier detection: Prob- lem revisit, new insight, and superior method. In 2023 IEEE 39th International Conference on Data Engineering (ICDE), IEEE, 2023.
Ming Jin, Yixin Liu, Yu Zheng, Lianhua Chi, Yuan-Fang Li, and Shirui Pan. Anemone: Graph anomaly detection with multi-scale contrastive learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 3122-3126, 2021.
Hyemi Kim, Seungjae Shin, JoonHio Jang, Kyungwoo Song, Weonyoung Joo, Wanmo Kang, and 11-Chul Moon. Counterfactual fairness with disentangled causal effect variational autoencoder. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8128 8136, 2021.
Hyunjik Kim and Andriy Mnih. Disentangling by factorising. In International conference on machine learning, pp. 2649 2658. PMLR, 2018.
Junghoon Kim, Yeonjun In, Kanghoon Yoon, Junmo Lee, and Chanyoung Park. Class label-aware graph anomaly detection. In Proceedings of the 32nd ACM International Conference Information and Knowl- edge Management, 2023.
Minseok Kim, Jinoh Oh, Jaeyoung Do, and Sungjin Lec. Debiasing neighbor aggregation for graph neural network in recommender systems. In Proceedings of the 31st ACM International Conference on Information & Knowledge Monagement, pp. 4128 4132, 2022.
Diederik P Kingma. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 2013.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint rexi::66000 02907, 2016.
Ao Li, Zhou Qin, Runshi Liu, Yiqun Yang, and Dong Li. Spam review detection with graph convolu- tional worksr.s In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 2703 20312771,111 2019.
Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou. Learning fair graph representations via automated data augmentations. In The Eleventh International Conference on Learning Representations, 2022.
Ji Liu, Zenan Li, Yuan Yao, Feng Xu, Xiaoxing Ma, Miao Xu, and Hanghang Tong. Fair representation learning: An alternative to mutual information. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1088-1097, 2022a.
Kay Liu, Yingtong Dou, Yue Zhao, Xueying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, al. Bond: Benchmarking unsupervised outlier node detection on static attributed graphs. Advances in Neural Information Processing Systems, 35:27021-27035, 2022b.
Kay Liu, Yingtong Dou, Yue Zhao, Xucying Ding, Xiyang Hu, Ruitong Zhang, Kaize Ding, Canyu Chen, Hao Peng, Kai Shu, al. Pygod: A python library for graph outlier detection. arXiv preprint Xiw:2204,11099 2022c.
15

---

Published in Transactions on Machine Learning Research (03/2025)
Kay Liu, Hengrui Zhang, Ziqing Hu, Fangxin Wang, and S Yu Philip. Data augmentation for supervised graph outlier detection via latent diffusion models. In The Third Learning Graphs Conference. PMT.R, 2024.
Kay Liu, Jiahao Ding, MohamadAli Torkamani, and Philip S Yu. Tgtod: A global temporal graph trans- former for outlier dctection at scale. In Pacific-Asia Conference Knowledge Discovery and Data Mining. Springer, 2025.
Yixin Liu, Zhao Li, Shirui Pan, Chen Gong, Chuan Zhou, and George Karypis. Anomaly detection on attributed networks via contrastive self-supervised learning. IEFE transactions on neural networks and learning systems, 33(6))2378 2392, 2021.
Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. Learning fair node representations with graph counterfactual fairness. In Proceedings of the Fifleenth ACM International Conference on Web Search and Data Mining, pp. 695-703, 2022.
Neng Kai Nigel Neo, Yeon-Chang Lee, Yiqiao Jin, Sang- Wook Kim, and Srijan Kumar. Towards fair graph anomaly detection: Problem, new datasets, and evaluation. In Proceedings of the 33nd A ACM International Conference on Information and Knowledge Management, 2024.
Changdae Oh, Heeji Won, Junhyuk So, Taero Kim, Yewon Kim, Hosik Choi, and Kyungwoo Song. Learn- ing fair representation via distributional contrastive disentanglement. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1295-1305, 2022.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang, Fairwalk: towards fair graph embed- ding. In Proceedings of the 28th International Joint. Conference on Artificial Intelligence, pp. 128903299) 2019.
Amit Roy, Juan Shu, Jia Li, Carl Yang, Olivier Elshocht, Jeroen Smeets, and Pan Li. Gad-nr: Graph anomaly detection via neighborhood reconstruction. arXiv preprinl arXiv:2306. 01951, 2023.
Mhd Hasan Sarhan, Nassir Navab, Abouzar Eslami, and Shadi Albarqouni. Fairness by learning orthogonal disentangled representations. In Computer Vision-ECC ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIX 16, pp. 746-761. Springer, 2020.
Shubhranshu Shekhar, Neil Shah, and Leman Akoglu. Fairod: Fairness-aware outlier detection. In Proceed- ings of the 2021 AAAT/ACM Conference on AI, Ethics, and Society, pp. 210-220, 2021.
Hanyu Song, Peizhao Li, and Hongfu Liu. Deep clustering based fair outlier detection. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1481 1489, 2021.
Weihao Song, Yushun Dong, Ninghao Liu, and Jundong Li. Guide: Group equality informed individual fairness in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness graph reprosentation learning. IEEE Transactions on Artificial Intelligence, 3()): 344 354, 2021.
Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density-ratio matching under the bregman diver- gence: a unified framework of density-ratio estimation. Annals of the Instilute of Statistical Mathematics, 64:1009-1044 2012.
Petar Veličković, Guillem Cueurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua. Bengio. Graph attention networks. arXiv preprint arXiv 2017.
Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr. Improving fairness graph neural networks via mitigating sensitive attribute leakage. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Dala Mining, pp. 1938-1948, 2022.
16

---

Published in Transactions on Machine Learning Research (03/2025)
Yongji Wu, Defu Lian, Yiheng Xu, Le Wu, and Enhong Chen. Graph convolutional networks with markov random field reasoning for social spammer detection. In Proceedings of the AAAT conference artificial intelligence, volume 34, pp. 1054 1061, 2020.
Haoyan Xu, Kay Liu, Zhengtao Yao, Philip Yu, Kaize Ding, and Yue Zhao. Lego-learn: Label-efficient graph open-set learning. arXiv preprint arXiv:2410.6633 2024.
Zhiming Xu, Xiao Huang, Yue Zhao, Yushun Dong, and Jundong Li. Contrastive attributed network anomaly detection with data augmentation. In Pacific-Aso Asia Conference on Knowledge Discovery and Data Mining, pp. 147- Springer, 2022.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International conference on machine learning, pp. 322-333. PMLR, 2013.
Ziqian Zeng, Rashidul Tslam, Kamrun Naher Keya, James Foulds, Yangqiu Song, and Shimei Pan. Fair representation learning for heterogeneous information networks. In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pp. 877-887, 2021.
Ge Zhang, Zhao Li, Jiaming Huang, Jia Wu, Chuan Zhou, Jian Yang, and Jianliang Gao. efraudcom: An e-commerce fraud detection system via competitive graph neural networks. ACM Transactions Information Systems (TOIS), 40(3):1-20 29,11199,2220 2022.
Hongjing Zhang and lan Davidson. Towards fair deep anomaly detection. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pp. 138-148, 2021.
Yuchang Zhu, Jintang Li, Liang Chen, and Zibin Zheng. The devil is in the data: Learning fair graph neural networks via partial knowledge distillation. arXiv e-prints, pp. arXiv 2311, 2023.
A Pseudo Code
The overall training process of DEFEND is presented in Algorithm Firstly, given an attributed graph G. we aim to Irain a variational graph autoencodes in which the disentangled encoder Sa can separate sensitive- irrelevant representations while maintaining information for reconstructing G by the decoder fa and fo (Line 4-6). We encourage the discntanglement with lcarnable adversary IN optimized by Lade (Line 8-9). The optimization of Se: Sa and fa and that of Iw are conducted adversarially. Next, the frozen Se captures sensitive-irrelevant node representations (Line 14), and the decoder Ss solely reconstructs attributes (Line 15). We utilize reconstruction error as the anomaly score and constrain the correlation between reconstruction error and predicted sensitive attributes (Lines 16-19). Finally, only fo will be updated by Lad in the anomaly detection phase.
B Complexity Analysis
We analyze the time and space computational complexity of DEFEND. Let N, E, d and h denote the number of nodes, edges, attribute dimensions and hidden dimensions, respectively.
In the disentangled representation learning phase, the encoder fe exhibits a complexity of O(Ed), while the decoders fa and fa exhibit a complexity of O(N2) for adjacency matrix reconstruction. The adversary I operates at O(Nh). For loss computations, the variational reconstruction loss Lyne exhibits O(N2) com- plexity for adjacency matrix reconstruction and O(Nd) for attribute reconstruction. The disentanglement loss Ldie, predictive loss Lpre, and adversarial loss Lads each exhibit O(N)) complexity. In the anomaly de- tection phaso, the frozen encoder fe maintains O(Ed) complexity, while the MLP-based decoder fo exhibits O(Nh) complexity. Both the correlation constraint loss Loorr and reconstruction loss LXX exhibit O(Nh) complexity. Thus, the total time complexity is O(N2 +d). The space complexity DEFEND is dominated by the storage of the dense adjacency matrix O(N2), node fcature matrix O(Nd), and model parameters with intermediate results O(Nh), resulting a total space complexity of O(N2 + Nd + Nh).
To enhance scalability, we implement sparse version that computes reconstruction only for existing edges
17

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm DEFEND algorithm
Input: Graph 9 = (V. E), adjacency matrix A, attribute matrix X, sensitive attribute matrix S, GNN encoder fe, attribute decoder fz, structure decoder fax binary adversary Iw, linear attribute decoder fo: training iteration 7;
Output: Anomaly scores
1: // Disentangled representation learning phase;
2: Initialize Ses la Ja. Awi
3: while not converged do
4: Zz Z, A))
A,X t falz, fo Zz):
Calculate Liotal according to Equation 15
Update fa: by gradient descent using Stotali
8: Calculate Lado according to Equation 16;
9: Update by gradient descent using Lade;
10: end while
11: // Anomaly detection phase;
12: Freeze fa and initialize føi
13: for = 1.2...., do
14: Z. L. x AX,
15:
X - (Z,
16: Calculate anomaly score o according to Equation 17
17: Calculate Lad according to Eqqation 19
18: Update fo by gradient descent using Ladi
19: end for
20:
return O:
and approximates the global statistics using row/column means, instead of reconstructing the full adjacency matrix. We also replace dense matrix operations with sparse operalions in loss compulations. This optimiza- tion reduces the complexity of the decoder fo to O(Eh) for structure reconstruction. Besides, the complexity of Feae decrcases to OEE) for structure and maintains O(Nd) for attribute reconstruction. Thus, the overall time complexity is reduced O(Ed+ Nd). The space complexity decreases significantly to by utilizing sparse matrix representations and eliminating dense adjacency matrices.
C Datasets
We employ three real-world datasets for fair GAD, which provide both real sensitive attributes and ground- truth labels for GAD. Reddit and Twitter datasets, the sensitive attribute is the political leaning of users, while the anomaly label assigned misinformation spreaders. The Credit dataset focuses on payment default detection, with age as the sensitive attribute. Details of these datasets summarized in Table 1
Reddit Neo al. 2024] 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 (Noo et al. 2024) is conducted on 47,712 users with 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. The network structure was established based on follower relationships between users.
Credit AAgawal et al., 2021 contains 30,000 individuals with features like education, credit history, age, and features derived from their spending and payment patterns. Two nodes are connected if their similarity exceeds 70% of the maximum similarity between all node pairs, measured using Minkowski distance.
18

---

Published in Transactions on Machine Learning Research (03/2025)
D Baselines
In this subscction, we introduce the basclines employed in experiments, including GAD methods (i.e., DOMINANT, CoLA, CONAD, and VGOD), 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 reconstruct- ing node attributes and graph structure. The attribute decoder the reverse structure of the encoder and the structure decoder is applied by dot product. Anomalous nodes evaluated by reconstruction errors.
CoLA Liu ct al. 2021 is contrastive self-supervised lcarning framework for anomaly detection. It conducts node-subgraph contrast lo 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. employs a Siamese graph neural network with a contrastive loss encode both the modeled knowledge and the original attributed networks. Anomalous nodes are evaluated by reconstruction errors.
VGOD (Huang et al., 2023) proposes a variance-based framework that combines variance-based model for structural outlier detection with attribute reconstruction model for contextual outlier detection. It achieves balanced detection performance between structural and contextual outliers while addressing data leakage issues present in existing injection- injection-based based approaches.
FairOD (Shekhar et al. 2021 is a fairness-awan aware outlier detector on independent and identically dis- tributed (i..d.) data. It devises regularization term to prompt the fairness of demographic parity by minimizing the reconstruction errors o and the sensitive attributes S.
(E - 1o) (E 8; - 14)
FairO L DP
(20)
0
where Mo and Me represent the means, while da and 0, denote the corresponding standard deviations of o and S, respectively. Besides, it utilizes an approximation of Discounted Cumulative Gain (DCG) to enforce the group fidelity.
20hm -1
FairOD
Σ
Σ (u:s;=s)
(21)
DNM,
+E(U.1}
where DNM,
log2 (1 (1 (1510)=s) (0, - o.)
IDCG, and IDCG,
Efforesyzall (20)am 1/logg (1 + j)) Here, Jasse is the reconstruction error of U in the base model and al-) is the Sigmoid function. The overall loss of the model equipped with FairOD regularizer can be calculated by = Lrase ACDP
FairOD ACCG where À and y are weight parameters.
Correlation Shekhar et al. 2021 is implementation of FairOD, which measures the correlation between sensitive attributes S and reconstruction errors using the cosine similarity.
S
Coor
(22)
Vl V) (S.
where (-) represents the dot product of two vectors. The overall loss of the model equipped with the Correlation regularizer can be calculated by L Lrase Core
19

---

Published in Transactions on Machine Learning Research (03/2025)
HIN
focuses on fair representation learning for heterogeneous information networks. The demographic parity-based lairness-aware loss function is calculated by:
ZZegg et al. 2021
E Elesoo=1 P(u. =
Σ Ejoss P(u: = k) 2 Ke :4 8 = 00
CHIN DP
Σ
(23)
Ke; 8
1}
kEf0,11
where P(ú: 1) 1) denotes the predicted probability of us be identified anomalous node. The equal opportunity-basee fairness-awar loss is calculated by:
Σ (1iss - 1, Pr(m = k)
E(mos, 0. Pr k) Ke 0, kH
BO
Σ (0
(24)
(us :8::8:1 8, 1, K)
As the calculation of LEO requires task-related labels and anomaly detection tasks typically lack ground truth labels, we use C CFarOD ADCC 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:
= Lrase + ACHIN + ADCG
(25)
Fair (Rahman et al. 2019 introduces fairness-aware embedding method that generates node embeddings by considering sensitive attributes and the topology of the graph. Tt enhances the gen- eral 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 lopology and node features. It minimizes the approximated Wasserstein distance bet ween the distributions of different groups for any attribute dimension to enhance group fairness.
E Implementation Details
For DOMINANT, CoLA, CONAD and VGOD, we use the code and default hyper-paramoters provided by PyGOn (Liu et al. 2022cb. For FairWall and EDITS we implement them using the code published by their authors. For FairOD, HIN, and Correlation, we implement the code provided by FairGAD
F Limitations and Future Work
First, DEFEND encounters difficulties when protected attributes are highly correlated with other features, potentially resulting in information loss during disentanglement. Additionally, DEFEND relics on adversarial learning approximate the Total Correlation penalty used for disentanglement. This dependency introduces potential convergence instability issues that might compromise the robustness of learned representations (Oh et al. 2022). We plan to extend the framework to handle multiple and continuous sensitive attributes sirnultaneussly which would enhance its practical applicability.
httpps:/pygod..o
http://gghhaa.co//rrstbllgggg/rr
http:///thhu..cc/yahnnnd//////
http://ggtthb.cco//nggmm///////
20


Reviews:
[{"review_id": "jRv8Ex6n1H", "reviewer": "Reviewer_qUcw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "_Strengths_: \n\n- This is one of the first works focusing on an important research problem.\n- The proposed framework is built upon well-established bias mitigation algorithms, where the proposed regularizer, $ L_{corr} $, helps these existing methods to be used for graph anomaly detection. Thus, the overall algorithm is easy to follow.\n- Experimental evaluation is thorough in terms of the selection of baselines, ablation study, and sensitivity analyses. \n\n_Weaknesses_:\n\n- Overall, the justification for not using the reconstruction loss for graph topology is not clear to me. The Authors suggest that \"Given the inherent bias in graph topology, anomaly detection relies solely on node attributes\". However, it is also well-known that the node attributes carry sensitive information too. Thus, the justification for this design choice must be improved. \n\n- The ablation study for the use of reconstruction loss for graph topology (DEFEND+S) can be designed better. Similar to the employment of $ L_{corr} $ for nodal feature reconstruction, for graph topology reconstruction, the effect of sensitive attributes on the reconstruction quality can be reduced by working on a debiased version of the graph topology. \n\n- The overall algorithm design is built upon the assumption that $Z_{x}$ and $Z_{s}$ are independent. Providing some analytical results on real-world data for this assumption can improve the submission. \n\n- Experimental evaluation can be improved by including scalability analyses.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a fairness-aware graph anomaly detection framework, which is built upon representation disentanglement. The contributions of the submission follow as:\n\n- This work proposes the first fairness-aware strategy that is specifically designed for graph anomaly detection.\n- The proposed correlation-based regularizer is straightforward, yet effective. \n- Experimental evaluation is thorough demonstrating utility-fairness trade-off clearly.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the Weaknesses.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sVFwHhB1av", "reviewer": "Reviewer_6KZ6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. Novelty: DEFEND introduces a first-of-its-kind framework for fair unsupervised GAD, combining ideas from disentangled representation learning and fairness-aware anomaly detection.\n2. Theoretical Rigor: The method is built on a strong mathematical foundation, with detailed formulations for disentanglement and fairness constraints.\n3. Comprehensive Evaluation: The paper provides extensive empirical results, including ablation studies and parameter sensitivity analysis, highlighting the importance of each component in DEFEND.\n4. Practical Relevance: The proposed method is relevant for high-stakes applications like fraud detection, where fairness is critical.\n5. Discussion of Generalization: The paper includes a thoughtful discussion on extending DEFEND to handle more complex sensitive attributes, such as categorical or continuous variables.\n\n**Weaknesses**\n\n1. Dataset Limitation: The experimental evaluation is conducted on only two real-world datasets (Reddit and Twitter), limiting the generalizability of findings across diverse graph structures.\n2. Baseline Comparisons: Some baselines are adaptations of methods not originally designed for fair GAD, which could lead to less direct comparisons.\n3. Efficiency Analysis: Limited discussion on computational efficiency and scalability to larger graphs or denser datasets.\n4. Fairness Metrics: The evaluation focuses on demographic parity and equal opportunity but does not consider other fairness measures, such as individual fairness or subgroup-specific biases.\n5. Lack of Qualitative Insights: The paper does not include qualitative analyses of specific cases where DEFEND improves fairness, which would help interpretability.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the critical and underexplored issue of fairness in graph anomaly detection (GAD), proposing a comprehensive framework, DEFEND, to mitigate bias while maintaining strong anomaly detection capabilities. The key contributions include:\n\n- Theoretically grounded disentangled representation learning for graphs\n- Reconstruction-based anomaly detection that intentionally avoids biased graph topology\n- Novel correlation constraints between reconstruction errors and sensitive attributes\n- Computationally efficient implementation with strategies for reducing matrix reconstruction complexity", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical Changes**\n1. Scalability Analysis: Provide runtime and scalability experiments on larger or denser graphs to assess DEFEND’s computational feasibility.\n2. Hyperparameter Selection: Elaborate on the hyperparameter tuning process and its influence on performance, particularly for fairness-related terms.\n3. Discussion of Limitations: Include a section addressing potential failure modes or limitations, such as scenarios where disentanglement might not be effective.\n\n**Suggested Improvements**\n\n1. Expand Fairness Metrics: Consider evaluating DEFEND using additional fairness criteria, such as individual fairness or measures specific to subgroup disparities.\n2. Broaden Dataset Scope: If feasible, extend experiments to include more diverse datasets with varying graph structures and sensitive attributes.\n3. Visual Representation: Include visualizations of disentangled representations to better demonstrate how sensitive-relevant and sensitive-irrelevant information is separated.\n4. Qualitative Examples: Provide qualitative insights into specific cases where DEFEND outperforms baselines in terms of fairness.\n5. Algorithmic Transparency: Add pseudocode for key components of the DEFEND framework to enhance reproducibility.\n6. Detailed Discussion of Extensions: Offer more concrete insights into adapting DEFEND for multiple or continuous sensitive attributes, potentially with experimental validation.", "broader_impact_concerns": "NAN.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TzcliFYvdx", "reviewer": "Reviewer_pyYs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The authors conduct extensive experiments on 2 datasets with a very comprehensive overview of competing methods and frameworks.\n- This work is transparent about the tradeoff between performance and fairness, and it strongly argues for the overall optimality of DEFEND given this context.\n- Using disentanglement to combat entangled features for fairness is a fairly straightforward and intuitive idea, and it is good to see that it shows promise.\n\n**Weaknesses**\n\n- DEFEND achieves its effectiveness through several loss functions. While the authors delve into time complexity of the backbone architecture in Appendix C, the efficiency impact of each of thse loss terms is unclear.\n- DEFEND claims to effectively disentangle sensitive-relevant and sensitive-relevant attributes, but there is no feature analysis to quantiatively assess its disentanglement abilities.\n- The baseline methods are not based on disentanglement. DEFEND would be stronger if it also demonstrates superiority over some basic disentangelement-based methods.\n- DEFEND+S exhibits worse performance overall when including a graph structure decoder. However, a method like EDITS could help with debiasing the graph itself before DEFEND is applied. Have the authors tried a variety of methods with eliminating graph structure bias?\n- DEFEND acknowledges the existence of bias in graph topology, but no module seems tailored to combat this. In fact, its encoder backbone is a GCN, which leverages the graph topology.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce DEFEND, a GNN-based anomaly detection framework using disentangelement and reconstruction-based objectives to fairly detect anomolous nodes. DEFEND is based on the observation that sensitive attributes are often associated with other sensitive and sensitive-irrelevant as well as benign attributes, making fair training difficult. To combat, this, DEFEND disentangles node representations in order to separate sensitive-relevant and sensitive-irrelevant features which in turn benefits fair graph anomaly detection.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the above weaknesses. Also, the reconstruction loss and KL loss in Equations 11 and 12 as well as labeling the variational lower bound term as $\\L_{vae}$ seems greatly inspired with the variational autoencoder from the popular [1], but it is not cited.\n\n[1] Kingma and Welling. Auto-Encoding Variational Bayes. ICLR 2014.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KYs2rt9yAv", "reviewer": "Reviewer_niAE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Considering fairness in unsupervised graph anomaly detection is quite interesting and holds practical significance.\n2. The method is clear and easy to follow.\n\nWeakness:\n1. The organization of the paper needs improvement. \n   - In particular, the Introduction lacks a clear, logical flow, resulting in an unconvincing presentation of the shortcomings of existing methods for incorporating fairness into graph anomaly detection and the motivations for the proposed approach.\n   - The method follows an encoder-decoder framework, but Fig. 1 does not clearly reflect this structure. It should be revised to better align with and illustrate the proposed method.\n\n2. The paper relies on the key assumption that the latent space can be decomposed into two independent subspaces. However, it does not provide sufficient theoretical analysis or detailed justification for the independence between sensitive-irrelevant and sensitive-relevant representations, which, in my opinion, are likely to be highly dependent. This assumption should be addressed and substantiated more carefully.\n\n3. In the experiments, while the authors explore different hyperparameters, they fail to provide deeper insights into how their method works, limiting the understanding of its underlying mechanisms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes DEFEND, a framework for fair graph anomaly detection (GAD) that reduces bias by learning sensitive-irrelevant representations and using attribute-focused reconstruction to enhance both fairness and utility.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides addressing the above weaknesses, here are some suggestions:\n1. Add a pseudo code of the whole algorithm for better understanding.\n2. Please add a computational analysis of the proposed method.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a novel framework to enhance the fairness in unsupervised graph anomaly detection. Reviewers recognized the technical contributions of this work and also provided many suggestions regarding technical details, experiments, paper writing, etc. During the revision and discussion stage, the authors have provided very detailed responses as well as additional experimental results, which have been incorporated into the revised paper. Reviewers found that their previous concerns have been sufficiently addressed.
Decision: Accept (poster)