Fair Anomaly Detection For Imbalanced Groups

## Abstract

Abstract Anomaly detection (AD) has been widely studied for decades in many real-world applications, including fraud detection in finance, and intrusion detection for cybersecurity, etc.
Due to the imbalanced nature between protected and unprotected groups and the imbalanced distributions of normal examples and anomalies, the learning objectives of most existing anomaly detection methods tend to solely concentrate on the dominating unprotected group.
Thus, it has been recognized by many researchers about the significance of ensuring model fairness in anomaly detection.
However, the existing fair anomaly detection methods tend to erroneously label most normal examples from the protected group as anomalies in the imbalanced scenario where the unprotected group is more abundant than the protected group. This phenomenon is caused by the improper design of learning objectives, which statistically focus on learning the frequent patterns (i.e., the unprotected group) while overlooking the under-represented patterns (i.e., the protected group). To address these issues, we propose FairAD , a fairness-aware anomaly detection method targeting the imbalanced scenario. It consists of a fairness-aware contrastive learning module and a rebalancing autoencoder module to ensure fairness and handle the imbalanced data issue, respectively. Moreover, we provide the theoretical analysis that shows our proposed contrastive learning regularization guarantees group fairness. Empirical studies demonstrate the effectiveness and efficiency of FairAD across multiple real-world datasets.

## 1 Introduction

Anomaly detection (AD), a.k.a. outlier detection, is referred to as the process of detecting data instances that significantly deviate from the majority of data instances [].
Anomaly detection finds extensive use in a wide variety of applications including financial fraud detection [, ], pathology analysis in the medical domain [, ] and intrusion detection for cybersecurity [, ]. For example, an anomalous traffic pattern in a computer network suggests that a hacked computer is sending out sensitive data to an unauthorized destination []; anomalies in credit card transaction data could indicate credit card or identity theft [].

Up until now, a large number of deep anomaly detection methods have been introduced, demonstrating significantly better performance than shallow anomaly detection in addressing challenging detection problems in a variety of real-world applications. For instance, [, ] aim to learn a scalar anomaly scoring function in an end-to-end fashion, while  [, , , , ] propose to learn the patterns for the normal examples via a feature extractor.

Recently, there has been widespread recognition within the AI community about the significance of ensuring model fairness and thus it is highly desirable to establish specific parity or preference constraints in the context of anomaly detection. Take racial bias in anomaly detection as an example. Racial bias has been observed in predictive risk modeling systems to predict the likelihood of future adverse outcomes in child welfare [].
Communities in poverty or specific racial or ethnic groups may face disadvantages due to the reliance on government administrative data. The data collected from these communities, often stemming from their economic status and welfare dependence, can inadvertently categorize them as high-risk anomalies, leading to more frequent investigations to these minority groups.
Consequently, disproportionately flagging minority groups as anomalies not only perpetuates biases but also results in an inefficient allocation of government resources.

To mitigate potential bias in anomaly detection tasks, numerous researchers [, , ] advocate for incorporating fairness constraints into their proposed methods.
However, most of these methods tend to erroneously label most normal examples from the protected/minority group as anomalies in an imbalanced data scenario where the unprotected group is more abundant than the protected group.
To better illustrate this issue, we conduct a toy example on the MNIST-USPS dataset[]. Figure 1 and Table 1 show the performance of anomaly detection methods evaluated on the MNIST-USPS dataset, where Recall Diff refers to the absolute value of recall difference between the protected group and the unprotected group. Note that in such an imbalanced scenario, metrics such as accuracy difference [] are not proper choices. We observe that existing methods either compromise performance for fairness (i.e., low recall rate and low recall difference) or exhibit unfair behavior (i.e., high recall difference);
The problem of misclassification arises from models focusing on learning frequent patterns in the more abundant unprotected group, potentially overlooking under-represented patterns in the protected group. The issue of group imbalance results in higher errors for protected groups, thus causing misclassifications. Following [], we refer to this phenomenon as *representation disparity*.

To address these issues, we face the following two major challenges.
C1: Handling imbalanced data. Due to the imbalanced nature between the protected and unprotected groups and the imbalanced distributions of normal examples and anomalies, the learning objectives of most existing anomaly detection methods tend to solely concentrate on the unprotected group. C2: Mitigating the representation disparity. Traditional anomaly detection methods encounter difficulties in dealing with representation disparity issues, which may worsen in the imbalanced data scenario as protected groups are typically less rich than unprotected groups.

Figure: Figure 1: Recall@1200 and absolute Recall difference of the existing methods on MNIST-USPS dataset.
Refer to caption: extracted/5859862/figs/motivation_example_performance.jpg

To tackle these challenges, in this paper, we propose FairAD, a fairness-aware contrastive learning-based anomaly detection method for the imbalanced scenario. FairAD mainly consists of two modules: 1) fairness-aware contrastive learning module; 2) re-balancing autoencoder module. Specifically, the fairness-aware contrastive learning module aims to maximize the similarity between the protected and unprotected groups to ensure fairness and address C2.
In addition, we encourage the uniformity of representations for examples within each group, as ensuring uniformity in contrastive learning can be beneficial for the imbalanced group scenario []. To further address the negative impact of imbalanced data (i.e., C1), we propose the re-balancing autoencoder module utilizing the learnable weight to reweigh the importance of both the protected and unprotected groups. Combining the two modules, we design a simple yet efficient method FairAD with a theoretical guarantee of fairness.
Our contributions are summarized below.

- •
A fairness-aware anomaly detection method FairAD addressing the representation disparity and imbalanced data issues in the anomaly detection task.
- •
Theoretical analysis showing that our proposed fair contrastive regularization term guarantees group fairness.
- •
The re-balancing autoencoder equipped with learnable weight alleviating the negative impact of the imbalanced group.
- •
Empirical studies demonstrating the effectiveness and efficiency of FairAD across multiple real-world datasets.

The rest of this paper is organized as follows. We first provide the preliminaries in Section 2 and then introduce our proposed fair anomaly detection method in Section 3, followed by the theoretical fairness analysis in Section 4. Then, we systematically evaluate the effectiveness and efficiency of FairAD in Section 5.
We finally conclude the paper in Section 6.

## 2 Preliminaries

In this paper, we explore the fairness issue in the unsupervised anomaly detection task. Among the various fairness definitions proposed, there is no consensus about the best one to use. In this work, we focus on the group fairness notion which usually pursues the equity of certain metrics among the groups. For instance, Accuracy Parity [] requires the same task accuracy between groups and Equal Opportunity [] requires the same true positive rate instead. Without loss of generality, we consider the groups here to be the protected group and the unprotected group (e.g., Black and Non-Black in race).
We are given a dataset $D=P\cup U$, where $P=\{x_{i}^{P},y_{i}^{P}\}_{i=1}^{n}$ are examples from the protected group, $U=\{x_{i}^{U},y_{i}^{U}\}_{i=1}^{m}$ from the unprotected group, and $x_{i}^{P},x_{i}^{U}$ are sampled i.i.d from distributions $\mathcal{P}_{P},\mathcal{P}_{U}$ over the input space $\mathbb{R}^{d}$ respectively. The ground-truth labels $y_{i}^{P},y_{i}^{U}\in\mathcal{Y}=\{0,1\}$ represent whether the example is an anomaly $(y=1)$ or not, which are given by deterministic labeling functions $a_{P},a_{U}:\mathbb{R}^{d}\rightarrow\mathcal{Y}$, respectively. Note that we do not have access to the labels during training as we focus on the unsupervised anomaly detection setting.

The task of unsupervised anomaly detection is to find a hypothesis
$h:\mathbb{R}^{d}\rightarrow\mathcal{Y}$ which identifies a subset $\mathcal{A}\subset D$ whose elements deviate significantly from the majority of the data in $D$. This identification is done without the aid of labeled examples, meaning the algorithm must rely on the intrinsic properties of the data, such as distribution, density, or distance metrics, to discern between normal examples and anomalies. The risk of a hypothesis $h$ w.r.t. the true labeling function $a$ under distribution $\mathcal{D}$ using a loss function $\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}_{+}$ is defined as: $R^{\ell}_{\mathcal{D}}(h,a)\coloneqq\mathbb{E}_{x\sim\mathcal{D}}\left[\ell(h(
x),a(x))\right]$. We assume that $\ell$ satisfies the triangle inequality. For notation simplicity, we denote $R^{\ell}_{P}(h)\coloneqq R^{\ell}_{\mathcal{P}_{P}}(h,a_{P})$ and $R^{\ell}_{U}(h)\coloneqq R^{\ell}_{\mathcal{P}_{U}}(h,a_{U})$. The empirical risks over the protected group $P$ and the unprotected group $U$ are denoted by $\hat{R}^{\ell}_{P}$ and $\hat{R}^{\ell}_{U}$.

One direction of unsupervised AD is reconstruction-based autoencoder, such as USAD [] and DAAD []. Assuming the anomalies possess different features than the normal examples, given an autoencoder over the normal examples, it will be hard to compress and reconstruct the anomalies. The anomaly score can then be defined as the reconstruction loss for each test example. Formally, the autoencoder consists of two main components: an encoder $g_{e}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{r}$ and a decoder $g_{d}:\mathbb{R}^{r}\rightarrow\mathbb{R}^{d}$, where $r$ is the dimensionality of the hidden representations. $g_{e}(x)$ encodes the input $x$ to a hidden representation $z$ that preserves the important aspects of the input. Then, $g_{d}(z)$ aims to recover $x^{\prime}\approx x$, a reconstruction of the input from the hidden representation $z$. Overall, the autoencoder can be written as $G=g_{d}\circ g_{e}$, i.e. $G(x)=g_{d}(g_{e}(x))$. For a given autoencoder-based framework, the anomaly score for $x$ is computed using the reconstruction error as:

$$ $s(x)=\lVert x-G(x)\rVert^{2},$ (1) $$

where all norms are $\ell_{2}$ unless otherwise specified. Anomalies tend to exhibit large reconstruction errors because they do not conform to the patterns in the data as coded by the autoencoder. This scoring function is generic in that it applies to many reconstruction-based AD models, which have different parameterizations of the reconstruction function $G$.
Next, we will present our method design based on the autoencoder framework. For quick reference, we summarize the notation used in the paper in Table 7 in Appendix.

## 3 Proposed Method

Our proposed FairAD mainly consists of two modules: a Fairness-aware Contrastive Learning Module and a Re-balancing Autoencoder Module.

Figure: (a) Failure of AD.
Refer to caption: extracted/5859862/figs/failure_case.jpg

### 3.1 Fairness-aware Contrastive Learning

Existing anomaly detection models [, , ] statistically focus on learning the frequent patterns (i.e., the unprotected group), while overlooking the under-represented patterns (i.e., the protected group) within the observed imbalanced data. Due to the lower contribution of protected groups to the overall learning objective (e.g., minimizing expected reconstruction loss), examples from the protected groups may experience systematically higher errors. Thus, they tend to erroneously label most normal examples from the protected group as anomalies, producing unfair outcomes as shown in Figure 2(a).

Recent works [, ] have shown that encouraging uniformity with contrastive learning can alleviate this issue by pushing examples uniformly distributed in the unit hypersphere, as illustrated in Figure 2(b). Therefore, one naive solution is to implement contrastive learning [] to learn representations by distinguishing different views of one example from other examples
as follows:

$$ $\displaystyle\mathcal{L}_{\mathrm{SimCLR}}=-\sum_{z_{j}\in P\cup U}\log\frac{ \text{sim}(z_{j},z_{j}^{+})}{\sum_{z_{k}\in P\cup U}\text{sim}(z_{j},z_{k})},$ (2) $$

where $z_{j}=g_{e}(x_{j})$ is the hidden representation, $U,P$ are slightly abused to denote the empirical distributions of the hidden representations of the unprotected and protected group, $z_{j}^{+}$ is obtained by an augmentation function to form a positive pair with $z_{j}$, and $\text{sim}(a,b)=\exp(\frac{a^{T}b}{|a||b|})$. By minimizing $\mathcal{L}_{\mathrm{SimCLR}}$, we encourage the uniformity of the representations of the two groups.

However, as shown in Figure 2(b), although the protected examples deviate from anomalies after encouraging uniformity, group fairness could not be guaranteed by the traditional contrastive learning loss.
To promote fairness between the protected group and the unprotected group, we further propose to maximize the cosine similarity between the representations of the two groups, as shown in Figure 2(c). Formally, we minimize the following fairness-aware contrastive loss:

$$ $\displaystyle\mathcal{L}_{\mathrm{FAC}}=$ $\displaystyle-\log\frac{\frac{1}{mn}\sum_{j\in[n]}\sum_{k\in[m]}\text{sim} \left(z_{j}^{P},z_{k}^{U}\right)}{\frac{1}{m(m-1)}\sum_{j\neq k}\text{sim} \left(z_{j}^{U},z_{k}^{U}\right)+\frac{1}{n(n-1)}\sum_{j\neq k}\text{sim}\left (z_{j}^{P},z_{k}^{P}\right)}$ (3) $\displaystyle=$ $\displaystyle\underbrace{-\log\left(\frac{\sum_{j}\sum_{k}\text{sim}\left(z_{j }^{P},z_{k}^{U}\right)}{mn}\right)}_{\mathcal{L}_{\mathrm{fair}}}+\underbrace{ \log\left(\frac{\sum_{j\neq k}\text{sim}\left(z_{j}^{U},z_{k}^{U}\right)}{m(m- 1)}+\frac{\sum_{j\neq k}\text{sim}\left(z_{j}^{P},z_{k}^{P}\right)}{n(n-1)} \right)}_{\mathcal{L}_{\mathrm{unif}}}$ $$

Following the interpretation of contrastive loss in [], the numerator (i.e., $\mathcal{L}_{\mathrm{fair}}$) can be interpreted as ensuring the fairness of two groups and the denominator (i.e., $\mathcal{L}_{\mathrm{unif}}$) can be interpreted as encouraging the diversity or uniformity of the representations in the unit hypersphere.
Besides, we show that our proposed fair contrastive regularization term guarantees group fairness with theoretical support in Section 4.

### 3.2 Re-balancing Autoencoder

We then introduce the autoencoder-based module of our method. The existing autoencoder-based AD frameworks [, ] aim to optimize the following reconstruction loss:

$$ $\mathcal{L}_{\mathrm{REC}}=\sum_{x_{i}\in{P\cup U}}\lVert x_{i}-G(x_{i})\rVert ^{2}=\underbrace{\sum_{i=1}^{n}\lVert x_{i}^{P}-G\left(x_{i}^{P}\right)\rVert^ {2}}_{\mathcal{L}_{P}}+\underbrace{\sum_{i=1}^{m}\lVert x_{i}^{U}-G\left(x_{i} ^{U}\right)\rVert^{2}}_{\mathcal{L}_{U}}.$ (4) $$

As these AD approaches fail to consider the data imbalance nature of the protected and unprotected groups, the learning objective in Equation (4) tends to solely concentrate on learning frequent patterns of the unprotected group (i.e., $\mathcal{L}_{U}$), yielding higher reconstruction errors for the examples from the protected group.
Consequently, existing methods usually overly flag the examples from the protected group as anomalies, thus having a higher recall difference, as illustrated in Figure 1.

To address the data imbalance issue between the two groups (i.e., C1 in the introduction), we design a re-balancing autoencoder by minimizing the reweighted reconstruction loss as follows:

$$ $\mathcal{L}_{\mathrm{REC}}=(1-\epsilon)\mathcal{L}_{U}+\epsilon\mathcal{L}_{P},$ (5) $$

A proper weight $\epsilon$ should promote the model fitting on the normal examples in both protected and unprotected groups. Consider the four subgroups of data samples in the task of fair anomaly detection: unprotected/protected normal examples (UN/PN) and unprotected/protected anomalies (UA/PA). Since ideally the model should only fit UN and PN, we assume that the model is capable of fitting two out of the four subgroups. For the design of $\epsilon$ we have the following lemma:

###### Lemma 3.1 .

Let $\mathcal{L}_{0}^{t}$ denote the loss of the unfitted model on the subgroup $t\in$ {UN, PN, UA, PA}, and let $\mathcal{L}_{1}^{t}$ denote the loss of the fitted model on the subgroup $t$, and $\Delta^{t}=\mathcal{L}_{0}^{t}-\mathcal{L}_{1}^{t}>0$ means the difference of loss between the fitted model and the unfitted one on the subgroup $t$. A proper weight that promotes model fitting on normal examples in both protected and unprotected groups should be within the range $\frac{\Delta^{UA}}{\Delta^{UA}+\Delta^{PN}}<\epsilon<\frac{\Delta^{UN}}{\Delta
^{UN}+\Delta^{PA}}$.

Although $\frac{\Delta^{UA}}{\Delta^{UA}+\Delta^{PN}}$ and $\frac{\Delta^{UN}}{\Delta^{UN}+\Delta^{PA}}$ are unknown, we propose a design of $\epsilon$ that provably lies in this range: $\epsilon=\frac{\mathcal{L}_{0}^{U}-\mathcal{L}_{U}}{\mathcal{L}_{0}^{U}-
\mathcal{L}_{U}+\mathcal{L}_{0}^{P}-\mathcal{L}_{P}}$ where $\mathcal{L}^{U}_{0}=\mathcal{L}^{UN}_{0}+\mathcal{L}^{UA}_{0}$ and $\mathcal{L}^{P}_{0}=\mathcal{L}^{PN}_{0}+\mathcal{L}^{PA}_{0}$.
We estimate $\mathcal{L}^{U}_{0}=\sum_{i\in U}\|x_{i}-\overline{G(x)}\|^{2}$
where $\overline{G(x)}=\frac{1}{|U|}\sum_{i\in U}G(x_{i})$, and $\mathcal{L}^{P}_{0}=\sum_{i\in P}\|x_{i}-\overline{G(x)}\|^{2}$ where $\overline{G(x)}=\frac{1}{|P|}\sum_{i\in P}G(x_{i})$.
The proof of Lemma 3.1 and the justification of our design are provided in Appendix E.1.
Finally, the overall training scheme of FairAD is to minimize:

$$ $\mathcal{L}_{\mathrm{overall}}=\mathcal{L}_{\mathrm{REC}}+\alpha\mathcal{L}_{ \mathrm{FAC}},$ $$

where $\alpha$ is a hyperparameter to balance the reconstruction loss and the contrastive loss. During the inference stage, we rank the reconstruction error of each example and pick the top $k$ examples as anomalies.

###### Lemma 3.1 .

## 4 Theoretical Analysis

In this section, we show how our proposed method promotes fairness. We focus on the group fairness notions where the difference in certain performance metrics between the two groups is considered. We first introduce the definition of $f$-divergence to help formulate an upper bound on the performance difference of FairAD:

###### Definition 4.1 .

($f$-divergence [] )
Let $P$ and $Q$ be two distribution functions with densities $p$ and $q$, respectively.
Let $p$ be absolutely continuous w.r.t $q$ and both be absolutely continuous with respect to a base measure $dx$.
Let $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ be a convex, lower semi-continuous function that satisfies $f(1)=0$.
The $f$-divergence $D_{f}$ is defined as:

$$ $D_{f}(P\parallel Q)=\int q(x)f\left(\frac{p(x)}{q(x)}\right)dx.$ (6) $$

Many popular divergences that are heavily used in machine learning are special cases of $f$-divergences, and we include some in Table 8 in Appendix D. [] derived a general variational approach for estimating $f$-divergence from examples by transforming the estimation problem into a variational optimization problem. They show that any $f$-divergence can be written as:

$$ $D_{f}(P\parallel Q)\geq\sup_{T\in\mathcal{T}}\mathbb{E}_{x\sim P}[T(x)]- \mathbb{E}_{x\sim Q}[f^{*}(T(x))]$ (7) $$

where $f^{*}$ is the (Fenchel) conjugate function of $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ defined as $f^{*}(y):=\sup_{x\in\mathbb{R}_{+}}\{xy-f(x)\}$, $T:\mathcal{X}\rightarrow\text{dom}\,f^{*}$, and $\mathcal{T}$ is the set of all measurable functions.

Given that $D_{f}(P\parallel Q)$ involves the supremum over all measurable functions and does not account for the hypothesis class, and that it cannot be estimated from finite examples of arbitrary distributions [], we further consider a discrepancy which helps relieve these issues based on the variational characterization of $f$-divergence in Equation (7):

###### Definition 4.2 .

($D^{f}_{h,\mathcal{H}}$ discrepancy [])
Let $f^{*}$ be the Fenchel conjugate of a convex, lower semi-continuous function $f$ that satisfies $f(1)=0$, and let $\hat{T}$ be a set of measurable functions such that $\hat{T}=\{\ell(h(x),h^{\prime}(x)):h,h^{\prime}\in\mathcal{H}\}$.
We define the discrepancy between the two distributions $P$ and $Q$ as:

$$ $\displaystyle D^{f}_{h,\mathcal{H}}(P\parallel Q):=$ $\displaystyle\sup_{h^{\prime}\in\mathcal{H}}|\mathbb{E}_{x\sim P}[\ell(h(x),h^ {\prime}(x))]-\mathbb{E}_{x\sim Q}[f^{*}(\ell(h(x),h^{\prime}(x)))]|$ $$

From the definition we can easily get $D^{f}_{h,\mathcal{H}}(P\parallel Q)\leq D_{f}(P\parallel Q)$.
We then introduce a useful tool, Rademacher complexity[] (detailed definition provided in Appendix C), and its commonly used property:

###### Lemma 4.3 .

(Property of Rademacher complexity []). For any $\delta\in(0,1)$, with probability at least $1-\delta$ over the draw of an i.i.d. sample $D$ of size $|D|$, the following inequality holds for all $h\in\mathcal{H}$:

$$ $|R^{\ell}_{D}(h)-\hat{R}^{\ell}_{D}(h)|\leq 2\mathfrak{R}_{D}(\ell\circ \mathcal{H})+\sqrt{\frac{\log\frac{1}{\delta}}{2|D|}}$ (8) $$

where $\mathfrak{R}_{D}(\ell\circ\mathcal{H})$ is the Rademacher complexity of the function class $\ell\circ\mathcal{H}$ given data $D$.
With this property, we now show that $D^{f}_{h,\mathcal{H}}$ can be estimated from finite examples:

###### Lemma 4.4 .

Suppose $\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow[0,1]$, $f^{*}$ is L-Lipschitz continuous, and $[0,1]\subseteq\text{dom}\,f^{*}$. Let $U$ and $P$ be two empirical distributions corresponding to datasets containing $m$ and $n$ data points sampled i.i.d. from $P_{U}$ and $P_{P}$, respectively. Let us note $\mathfrak{R}$ the Rademacher complexity of a given hypothesis class, and $\ell\circ\mathcal{H}:=\{x\mapsto\ell(h(x),h^{\prime}(x)):h,h^{\prime}\in
\mathcal{H}\}$. For any $\delta\in(0,1)$, with probability at least $1-\delta$, we have:

$$ $\displaystyle|D^{f}_{h,\mathcal{H}}(P_{U}\|P_{P})-D^{f}_{h,\mathcal{H}}(U\|P)| \leq 2\mathfrak{R}_{P_{U}}(\ell\circ\mathcal{H})+2L\mathfrak{R}_{P_{P}}(\ell \circ\mathcal{H})+\sqrt{\frac{\log\frac{1}{\delta}}{2n}}+\sqrt{\frac{\log\frac {1}{\delta}}{2m}}$ (9) $$

Lemma 4.4 shows that the empirical $D^{f}_{h,\mathcal{H}}$ converges to the true discrepancy, and the gap is bounded by the complexity of the hypothesis class and the number of examples.

###### Definition 4.1 .

###### Definition 4.2 .

###### Lemma 4.3 .

###### Lemma 4.4 .

### 4.1 Fairness Bounds

We now provide a fairness bound to estimate the performance difference between the protected and unprotected groups using the previously defined $D^{f}_{h,\mathcal{H}}$ divergence.

###### Theorem 4.5 .

Let $h^{*}$ be the ideal joint hypothesis, i.e., $h^{*}=\arg\min_{h\in\mathcal{H}}R^{\ell}_{U}(h)+R^{\ell}_{P}(h)$. The risk difference between the two groups is upper bounded by:

$$ $R^{\ell}_{P}(h)-R^{\ell}_{U}(h)\leq D^{f}_{h,\mathcal{H}}(P_{U}\|P_{P})+R^{ \ell}_{U}(h^{*})+R^{\ell}_{P}(h^{*}).$ (10) $$

For the upper bound on the RHS, the first term corresponds to the discrepancy between the marginal distributions, and the remaining two terms measure the ideal joint hypothesis. If $\mathcal{H}$ is expressive enough and the labeling functions are similar, the last two terms could be reduced to a small value.

###### Theorem 4.6 .

(Fairness with Rademacher Complexity) Under the same conditions as in Lemma 4.4, for any $\delta\in(0,1)$, with probability at least $1-\delta$, we have:

$$ $\displaystyle R^{\ell}_{P}(h)-R^{\ell}_{U}(h)\leq D_{f}(U\|P)+\hat{R}^{\ell}_{ U}(h^{*})+\hat{R}^{\ell}_{P}(h^{*})$ (11) $\displaystyle+4\mathfrak{R}_{U}(\ell\circ\mathcal{H})+2(L+1)\mathfrak{R}_{P}( \ell\circ\mathcal{H})+2\sqrt{\frac{\log\frac{1}{\delta}}{2m}}+2\sqrt{\frac{ \log\frac{1}{\delta}}{2n}}$ $$

**Table 2: Characteristics of datasets.**
| Datasets | Unprotected Group | Protected Group | #Features | Sensitive Attribute | Anomaly Definition |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| #Instances | #Anomaly | #Instances | #Anomaly |  |  |  |  |
| MNIST-USPS | 7,785 | 882 | 1,876 | 323 | 1,024 | Source of the digits | Digit 0 or not |
| MNIST-Invert | 7,344 | 441 | 408 | 38 | 1,024 | Color of the digits | Digit 0 or not |
| COMPAS | 1,839 | 325 | 299 | 39 | 8 | Race | Reoffending or not |
| CelebA | 41,919 | 4,008 | 7,300 | 1,142 | 39 | Gender | Attractive or not |

Under the assumption of an ideal joint hypothesis, fairness can be improved by minimizing the discrepancy between the two distributions and regularizing the model to limit the complexity of the hypothesis class. The detailed proofs of the lemma and the theorems are in Appendix E.2 and E.3. We further motivate why minimizing the objective $\mathcal{L}_{\mathrm{FAC}}$ leads to small $D_{f}(U||P)$
for total variation in Appendix E.4.

###### Theorem 4.5 .

###### Theorem 4.6 .

## 5 Experiments

In this section, we experimentally analyze and compare our proposed FairAD with other anomaly detection methods. We try to answer the following research questions:

RQ1: How does FairAD compare with other baselines on imbalanced datasets?

RQ2: How does FairAD perform with different ratios of the two groups?

RQ3: How does each module contribute to FairAD?

### 5.1 Experimental Setup

Datasets: We conduct experiments on two image datasets, MNIST-USPS and MNIST-Invert [], and two tabular datasets, COMPAS [] and CelebA []. The characteristics of the datasets are presented in Table 2.

Baseline Methods:
In our experiments, we compare our proposed framework FairAD with the following fairness-aware anomaly detection baselines:
(1) FairOD [], a fair AD method which incorporates the prescribed criteria into its training;
(2) DCFOD [], a fair deep clustering-based method, which leverages deep clustering to discover the intrinsic cluster structure and out-of-structure instances;
(3) FairSVDD [], an adversarial network to de-correlate the relationships between sensitive attributes and the learned representations.
We also compare with the following fairness-agnostic AD baselines:
(4) MCM [], a masked modeling method to address AD by capturing intrinsic correlations between features in the training set;
(5) NSNMF [], a non-negative matrix factorization method, which incorporates the neighborhood structural similarity information to improve the anomaly detection performance;
(6) ReContrast [], a reconstructive contrastive learning-based method for domain-specific anomaly detection. Notice that as ReContrast is designed for image data, we only evaluate it on MNIST-USPS and MNIST-Invert datasets.

Metrics: To measure the model performance and group fairness, we choose three widely-used metrics [, , ]: (1) Recall@k, which measures the proportion of anomalies found in the top-k recommendations; (2) ROCAUC, which computes the area under the receiver operating characteristic curve;
(3) Rec Diff, which measures the absolute value of the recall difference between two groups.

Training details: For the COMPAS dataset, we use a two-layer MLP with hidden units of [32, 32]. For all the other datasets, we use MLP with one hidden layer of dimension 128. All our experiments were executed using one Tesla V100 SXM2 GPUs, supported by a 12-core CPU operating at 2.2GHz. We provide our implementation in Appendix F.1.

**Table 3: Performance on Image Datasets. The best score is marked in bold.**
| Methods | MNIST-USPS (K=1200) | MNIST-Invert (K=500) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Recall@K | ROCAUC | Rec Diff | Time(s) | Recall@K | ROCAUC | Rec Diff | Time(s) |  |
| FairOD | $12.20{\pm 1.33}$ | $49.96{\pm 0.34}$ | $11.59{\pm 0.78}$ | 28.45 | $7.66{\pm 0.84}$ | $50.46{\pm 0.20}$ | $8.02{\pm 1.43}$ | 20.33 |
| DCFOD | $12.67{\pm 0.39}$ | $50.18{\pm 0.30}$ | $8.99{\pm 1.02}$ | 698.27 | $6.89{\pm 1.11}$ | $50.51{\pm 0.66}$ | $7.24{\pm 2.85}$ | 1287.52 |
| FairSVDD | $15.46{\pm 1.67}$ | $58.28{\pm 1.22}$ | $13.73{\pm 2.64}$ | 766.36 | $12.45{\pm 0.88}$ | $49.69{\pm 4.43}$ | $12.43{\pm 2.16}$ | 846.45 |
| MCM | $39.83{\pm 0.20}$ | $78.84{\pm 1.07}$ | $55.83{\pm 0.83}$ | 416.11 | $25.33{\pm 0.60}$ | $80.95{\pm 0.64}$ | $80.15{\pm 1.45}$ | 750.17 |
| NSNMF | $39.03{\pm 0.99}$ | $65.20{\pm 0.56}$ | $62.64{\pm 4.66}$ | 28.2 | $51.77{\pm 0.75}$ | $74.16{\pm 0.40}$ | $51.43{\pm 2.01}$ | 18.95 |
| Recontrast | $64.80{\pm 3.69}$ | $83.91{\pm 4.49}$ | $40.77{\pm 6.83}$ | 118.99 | $64.45{\pm 1.88}$ | $86.11{\pm 5.89}$ | $55.33{\pm 13.45}$ | 119.54 |
| FairAD | 67.16$\pm$0.37 | 91.27$\pm$0.49 | 3.73$\pm$2.13 | 122.84 | 72.37$\pm$0.32 | 98.03$\pm$0.01 | 6.75$\pm$0.34 | 52.28 |

**Table 4: Performance on Tabular Datasets. The best score is marked in bold.**
| Methods | COMPAS (K=350) | CelebA (K=5000) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Recall@K | ROCAUC | Rec Diff | Time(s) | Recall@K | ROCAUC | Rec Diff | Time(s) |  |
| FairOD | $16.58{\pm 2.60}$ | $50.12{\pm 1.57}$ | $8.29{\pm 1.28}$ | 4.20 | $8.91{\pm 0.16}$ | $49.92{\pm 0.14}$ | 0.67$\pm$0.68 | 78.87 |
| DCFOD | $15.94{\pm 2.35}$ | $49.74{\pm 1.42}$ | $9.75{\pm 2.15}$ | 116.82 | $9.75{\pm 0.82}$ | $49.93{\pm 0.17}$ | $7.51{\pm 1.33}$ | 2523.57 |
| FairSVDD | $15.29{\pm 2.25}$ | $52.60{\pm 5.48}$ | $11.59{\pm 4.28}$ | 6.62 | $10.16{\pm 0.58}$ | $58.40{\pm 1.21}$ | $10.86{\pm 2.02}$ | 248.95 |
| MCM | $20.97{\pm 0.69}$ | $50.56{\pm 0.51}$ | $6.26{\pm 2.90}$ | 38.23 | $11.07{\pm 0.50}$ | $46.08{\pm 3.95}$ | $27.06{\pm 11.99}$ | 632.81 |
| NSNMF | $22.89{\pm 0.27}$ | $57.96{\pm 0.81}$ | $36.04{\pm 0.67}$ | 7.54 | $10.88{\pm 0.66}$ | $50.40{\pm 0.37}$ | $8.05{\pm 1.63}$ | 1870.06 |
| FairAD | 34.43$\pm$0.42 | 61.85$\pm$0.52 | 5.81$\pm$4.36 | 17.94 | 11.94$\pm$0.67 | 59.41$\pm$0.58 | $4.66{\pm 1.72}$ | 52.81 |

### 5.2 Effectiveness and Efficiency of FairAD (RQ1)

We first evaluate the effectiveness and efficiency of FairAD through comparison with baselines across four datasets by three independent runs. The task performance (i.e., Recall@$K$ and ROCAUC), group fairness measure (i.e., Rec Diff), and their average training time are presented in Tables 3 and 4 (See Appendix F.2 for Recall@$K$ with different $K$). We can observe that the fair AD baselines (FairOD, DCFOD, and FairSVDD) typically exhibit low discrepancies in recall. However, they also tend to suffer from reduced recall rates and ROCAUC scores, suggesting a compromise in overall task performance to enhance fairness.
On the other hand, the baselines that do not account for fairness, including MCM, NSNMF, and ReContrast, demonstrate high recall rates and ROCAUC scores but often at the expense of fairness, as evidenced by significant disparities across groups (i.e., a higher Rec Diff).
Our FairAD instead addresses the challenge of imbalance between the groups and the imbalanced distributions of normal examples and anomalies.
Remarkably, FairAD not only excels in task performance but also elevates the level of fairness, underscoring the effectiveness of our design in harmonizing fairness with anomaly detection in scenarios characterized by data imbalance. On the other hand, the training time of FairAD is always among the top 4 fastest methods across different datasets, showing the efficiency of our method.

**Table 5: Performance on MNIST-USPS with different ratios. The best score is marked in bold.**
| Methods | $|U|:|P|=1:1$ (K=650) | $|U|:|P|=2:1$ (K=1000) | $|U|:|P|=4:1$ (K=1200) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Recall@K | ROCAUC | Rec Diff | Recall@K | ROCAUC | Rec Diff | Recall@K | ROCAUC | Rec Diff |  |
| FairOD | $17.52{\pm 1.17}$ | $50.13{\pm 0.64}$ | $2.14{\pm 0.62}$ | $17.30{\pm 1.24}$ | $49.73{\pm 0.74}$ | $5.11{\pm 0.55}$ | $13.61{\pm 0.22}$ | $50.22{\pm 0.13}$ | $10.58{\pm 1.01}$ |
| DCFOD | $17.08{\pm 0.50}$ | $50.09{\pm 0.30}$ | $3.25{\pm 0.94}$ | $16.92{\pm 0.81}$ | $49.54{\pm 0.42}$ | $2.76{\pm 0.51}$ | $14.14{\pm 1.03}$ | $50.44{\pm 0.60}$ | $7.11{\pm 0.83}$ |
| FairSVDD | $24.56{\pm 2.95}$ | $54.87{\pm 3.36}$ | $14.24{\pm 7.90}$ | $18.09{\pm 3.46}$ | $52.77{\pm 1.72}$ | $4.85{\pm 3.75}$ | $21.10{\pm 2.79}$ | $63.46{\pm 9.56}$ | $18.38{\pm 4.91}$ |
| MCM | $52.22{\pm 1.35}$ | $74.62{\pm 1.24}$ | $17.13{\pm 2.73}$ | $53.63{\pm 1.76}$ | $76.80{\pm 1.04}$ | $8.17{\pm 6.36}$ | $41.99{\pm 4.06}$ | $74.09{\pm 0.45}$ | $22.85{\pm 4.60}$ |
| NSNMF | $48.71{\pm 0.39}$ | $68.96{\pm 0.24}$ | $40.25{\pm 2.17}$ | $41.07{\pm 2.77}$ | $64.08{\pm 1.67}$ | $54.18{\pm 3.11}$ | $38.87{\pm 1.09}$ | $64.71{\pm 0.63}$ | $62.98{\pm 1.47}$ |
| Recontrast | $45.92{\pm 1.85}$ | $80.17{\pm 3.08}$ | $42.52{\pm 3.31}$ | $51.39{\pm 1.75}$ | $83.13{\pm 2.94}$ | $26.16{\pm 1.79}$ | $57.69{\pm 2.36}$ | $79.17{\pm 4.09}$ | $20.69{\pm 3.57}$ |
| FairAD | 65.58$\pm$0.47 | 85.38$\pm$0.37 | 0.93$\pm$0.87 | 66.84$\pm$0.83 | 89.17$\pm$0.09 | 2.32$\pm$1.08 | 66.63$\pm$0.72 | 90.15$\pm$0.22 | 1.84$\pm$0.68 |

**Table 6: Performance on COMPAS dataset with different ratios. The best score is marked in bold.**
| Methods | $|U|:|P|=1:1$ (K=80) | $|U|:|P|=2:1$ (K=120) | $|U|:|P|=5:1$ (K=240) |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Recall@K | ROCAUC | Rec Diff | Recall@K | ROCAUC | Rec Diff | Recall@K | ROCAUC | Rec Diff |  |
| FairOD | $13.68{\pm 2.67}$ | $50.10{\pm 0.85}$ | $11.97{\pm 1.48}$ | $13.11{\pm 0.50}$ | $50.11{\pm 0.74}$ | $6.60{\pm 0.97}$ | $12.54{\pm 1.37}$ | $49.58{\pm 0.87}$ | $7.68{\pm 0.72}$ |
| DCFOD | $11.54{\pm 4.62}$ | $48.50{\pm 2.69}$ | $7.69{\pm 4.445}$ | $15.95{\pm 3.00}$ | $53.28{\pm 0.75}$ | $10.68{\pm 2.67}$ | $12.96{\pm 2.02}$ | $49.76{\pm 1.16}$ | $6.36{\pm 0.70}$ |
| FairSVDD | $16.24{\pm 2.18}$ | $52.34{\pm 1.38}$ | $6.84{\pm 3.20}$ | $14.53{\pm 1.84}$ | $51.69{\pm 2.15}$ | $7.69{\pm 3.77}$ | $14.10{\pm 4.53}$ | $50.04{\pm 4.98}$ | $14.87{\pm 7.54}$ |
| MCM | $18.38{\pm 0.60}$ | $40.77{\pm 0.25}$ | $7.69{\pm 3.63}$ | $16.24{\pm 0.01}$ | $40.42{\pm 0.12}$ | $10.26{\pm 4.80}$ | $18.81{\pm 0.60}$ | $44.04{\pm 0.15}$ | $5.76{\pm 2.31}$ |
| NSNMF | $20.08{\pm 0.74}$ | $53.86{\pm 0.42}$ | $14.53{\pm 10.36}$ | $19.09{\pm 1.31}$ | $53.28{\pm 0.75}$ | $10.68{\pm 2.67}$ | $20.09{\pm 2.22}$ | $53.86{\pm 1.28}$ | $10.77{\pm 5.40}$ |
| FairAD | 29.91$\pm$0.74 | 61.87$\pm$1.89 | 3.42$\pm$1.48 | 28.42$\pm$0.43 | 57.39$\pm$2.84 | 1.92$\pm$1.72 | 29.77$\pm$1.31 | 58.05$\pm$1.34 | 4.83$\pm$0.78 |

### 5.3 Data Imbalance Study (RQ2)

To further study the performance of FairAD in handling imbalanced data, we vary the levels of group imbalance within the image dataset MNIST-USPS and the tabular dataset COMPAS. We report the average results of three independent runs in Table 5 and Table 6. The tables demonstrate that FairAD consistently outperforms the baselines in terms of both task efficacy and fairness across different group ratios. The advantages of using FairAD become more pronounced with increasing level of group imbalance. For instance, while the performance of fair AD baselines drops with higher imbalance ratios on the MNIST-USPS dataset, FairAD adeptly sustains superior task performance alongside enhanced fairness levels, showcasing its robustness against data imbalance.

Figure: Figure 3: Ablation Study on MNIST-USPS dataset.
Refer to caption: extracted/5859862/figs/ablation_study_usps_recall.jpg

### 5.4 Ablation Study (RQ3)

To validate the necessity of each module in FairAD, we conduct an ablation study to demonstrate the necessity of each component of FairAD on the MNIST-USPS dataset (more ablation studies can be found in Appendix F.3). The experimental results are presented in Figure 3, where (a) and (b) show the recall@1200 and recall difference, respectively. Specifically, FairAD-R refers to a variant of our method replacing re-balancing autoencoder with $\mathcal{L}_{2}$ in Equation (4); FairAD-N and FairAD-D remove $\mathcal{L}_{\mathrm{fair}}$ and
$\mathcal{L}_{\mathrm{unif}}$ in Equation (3), respectively; FairAD-C substitutes the proposed fair contrastive loss with the traditional contrastive loss (i.e., $\mathcal{L}_{\mathrm{SimCLR}}$). We have the following observations. (1) FairAD greatly outperforms FairAD-D and FairAD-N, which suggests that $\mathcal{L}_{\mathrm{fair}}$ and $\mathcal{L}_{\mathrm{unif}}$ are two essential components in our designed method. (2) FairAD-C has the competitive performance as FairAD with respect to recall@1200, but it has a large recall difference. This suggests that without proper regularization, the results exhibit unfair behaviors. Different from FairAD-C, FairAD achieves a much lower recall difference, which verifies our theoretical analysis that our proposed method could guarantee group fairness. (3) Compared with FairAD, FairAD-R has a lower recall rate but a higher recall difference. This indicates that replacing the re-balancing autoencoder with $\mathcal{L}_{2}$ results in worse performance, which verifies our conjecture that the traditional learning objective tends to mainly focus on learning the frequent patterns of the unprotected group while ignoring the protected group.

## 6 Conclusion

In this paper, we introduce FairAD, a fairness-aware anomaly detection method, designed for handling the imbalanced data scenario in the context of anomaly detection. Specifically, FairAD maximizes the similarity between the protected and unprotected groups to ensure fairness through the fairness-aware contrastive learning based module. To address the negative impact of imbalanced data, the re-balancing autoencoder module is proposed to reweigh the importance of both the protected and unprotected groups with the learnable weight. Theoretically, we provide the upper bound with Rademacher complexity for the discrepancy between two groups and ensure group fairness through the proposed contrastive learning regularization. Empirical studies demonstrate the effectiveness and efficiency of FairAD across multiple real-world datasets.

## Appendix A Notations

**Table 7: Notation Table.**
| Symbol | Description |
| --- | --- |
| $x$ | input feature |
| $\mathcal{P}_{P}$ | Protected group’s distribution |
| $\mathcal{P}_{U}$ | Unprotected group’s distribution |
| $P$ | Protected group’s empirical distribution |
| $U$ | Unprotected group’s empirical distribution |
| $n/m$ | Size of protected/unprotected group |
| $a_{P}/a_{U}$ | labeling functions on protected/unprotected group |
| $\ell$ | Loss function |
| $R^{\ell}_{D}(h)$ | Risk of hypothesis $h$ over data $D$ |
| $\hat{R}^{\ell}_{D}(h)$ | Empirical risk of hypothesis $h$ over data $D$ |
| $s(x)$ | Anomaly score of example $x$ |
| $\mathfrak{R}_{D}(\mathcal{F})$ | Rademacher complexity of $\mathcal{F}$ given data $D$ |

## Appendix B Related Work

Unsupervised Anomaly Detection.
Anomaly detection has been widely studied for decades in many real-world applications, including fraud detection in the finance domain [, ], pathology analysis in the medical domain [, ], intrusion detection for cyber-security [, ], and fault detection in safety-critical systems [], etc. The authors of  [] divide the existing anomaly detection methods into two major branches. The methods [, , , , ] in the first branch aim to learn the patterns for the normal samples by a feature extractor. For instance, [] is an encoder-decoder anomaly detection method, which learns how to amplify the reconstruction error of anomalies with adversarial training; [] proposes a GAN-based autoencoder model to learn the normal pattern of multivariate time series, and detect anomalies by selecting the samples with the higher reconstruction error. The second branch aims at learning scalar anomaly scores in an end-to-end fashion [, , ]. Notably, the authors of [] combine distribution-augmented contrastive regularization with a one-class classifier to detect anomalies;
Different from these methods, this paper tackles the problem of fairness-aware anomaly detection by mitigating the representation disparity with contrastive learning-based regularization.

Fair Machine Learning.
Fair Machine Learning aims to amend the biased machine learning models to be fair or invariant regarding specific variables. A surge of research in fair machine learning has been done in the machine learning community[, , , , ]. For example, [] presents a learning algorithm for fair classification by enforcing group fairness and individual fairness in the obtained data representation; [] proposes approaches to quantify and reduce bias in word embedding vectors that are trained from real-world data; in [], the authors develop a robust optimization framework that minimizes the worst case risk over all distributions and preserves the minority group in an imbalanced data set; in [], the authors present an adversarial-learning based framework for mitigating the undesired bias in modern machine learning models. In the field of fair anomaly detection, [] utilizes the adversarial generative nets to ensure group fairness and use one-class classification to detect the anomalies; [] introduces fairness adversarial training and proposes a novel dynamic weight to reduce the negative impacts from outlier points. The existing fair anomaly detection methods [, , ] tend to suffer from the representation disparity issue in the imbalanced data scenario. To address this issue, this paper aims to alleviate the issue of representation disparity in the imbalanced data scenario by introducing the rebalancing autoencoder module and maximizing the uniformity of the samples in the latent space via contrastive learning regularization.

## Appendix C Rademacher Complexity

The Rademacher complexity for a function class is:

###### Definition C.1 .

(Rademacher Complexity [])
Given a space $\mathcal{X}$, and a set of i.i.d. examples D = $\{x_{1},x_{2},...,x_{|D|}\}\subseteq\mathcal{X}$, for a function class $\mathcal{F}$ where each function $r:\mathcal{X}\rightarrow\mathbb{R}$, the empirical Rademacher complexity of $\mathcal{F}$ is given by:

$$ $\mathfrak{R}_{D}(\mathcal{F})=\mathbb{E}_{\sigma}\left[\sup_{r\in\mathcal{F}} \left(\frac{1}{|D|}\sum_{i=1}^{|D|}\sigma_{i}r(z_{i})\right)\right]$ (12) $$

Here, $\sigma_{1},...,\sigma_{m}$ are independent random variables uniformly drawn from $\{-1,1\}$.

###### Definition C.1 .

## Appendix D Divergences

We include some popular $f$-divergences in Table 8.

**Table 8: Popular $f$-divergences and their conjugate functions.**
| Divergence | $f(x)$ | Conjugate $f^{*}(t)$ | $f^{\prime}(1)$ | Activation func. |
| --- | --- | --- | --- | --- |
| Kullback-Leibler (KL) | $x\log x$ | $\exp(t-1)$ | 1 | $x$ |
| Reverse KL (KL-rev) | $-\log x$ | $-1-\log(-t)$ | -1 | $-\exp x$ |
| Jensen-Shannon (JS) | $-{x+1}\log\frac{1+x}{2}+x\log x$ | $-\log(2-e^{t})$ | 0 | $\log\frac{2}{1+\exp(-x)}$ |
| Pearson $\chi^{2}$ | $(x-1)^{2}$ | $\frac{t^{2}}{4}+t$ | 0 | $x$ |
| Total Variation (TV) | $\frac{1}{2}|x-1|$ | $1_{-1/2\leq t\leq 1/2}$ | $[-1/2,1/2]$ | $\frac{1}{2}\tanh x$ |

## Appendix E Proofs

### E.1 Proof of Lemma 3.1

Let us divide the data into four types: unprotected normal examples (UN), protected normal examples (PN), unprotected anomalies (UA), and protected anomalies (PA). For type $t\in$ {UN, PN, UA, PA},
let $\mathcal{L}_{0}^{t}$ denote the loss of the unfitted model on $t$ and $\mathcal{L}_{1}^{t}$ as the loss of the fitted model on $t$, $\Delta^{t}=\mathcal{L}_{0}^{t}-\mathcal{L}_{1}^{t}>0$. Assuming that the model can only fit two sets of data, to ensure that the model fits the sets of protected normal examples and unprotected normal examples, we need the following 5 inequalities to hold:

$(1-\epsilon)(\mathcal{L}^{UN}_{1}+\mathcal{L}_{0}^{UA})+\epsilon(\mathcal{L}_{
1}^{PN}+\mathcal{L}_{0}^{PA})<$

- 1.
$(1-\epsilon)(\mathcal{L}^{UN}_{0}+\mathcal{L}_{1}^{UA})+\epsilon(\mathcal{L}_{
1}^{PN}+\mathcal{L}_{0}^{PA})$, implied by $\Delta^{UN}>\Delta^{UA}$
which naturally holds;
- 2.
$(1-\epsilon)(\mathcal{L}^{UN}_{1}+\mathcal{L}_{0}^{UA})+\epsilon(\mathcal{L}_{
0}^{PN}+\mathcal{L}_{1}^{PA})$, implied by $\Delta^{PN}>\Delta^{PA}$ which naturally holds;
- 3.
$(1-\epsilon)(\mathcal{L}^{UN}_{0}+\mathcal{L}_{1}^{UA})+\epsilon(\mathcal{L}_{
0}^{PN}+\mathcal{L}_{1}^{PA})$, this case is equivalent to case 1 plus case 2;
- 4.
$(1-\epsilon)(\mathcal{L}^{UN}_{1}+\mathcal{L}_{1}^{UA})+\epsilon(\mathcal{L}_{
0}^{PN}+\mathcal{L}_{0}^{PA})$, we need $\epsilon>\frac{\Delta^{UA}}{\Delta^{UA}+\Delta^{PN}}$;
- 5.
$(1-\epsilon)(\mathcal{L}^{UN}_{0}+\mathcal{L}_{0}^{UA})+\epsilon(\mathcal{L}_{
1}^{PN}+\mathcal{L}_{1}^{PA})$, we need $\epsilon<\frac{\Delta^{UN}}{\Delta^{UN}+\Delta^{PA}}$.

So we have: $\frac{\Delta^{UA}}{\Delta^{UA}+\Delta^{PN}}<\epsilon<\frac{\Delta^{UN}}{\Delta
^{UN}+\Delta^{PA}}$. We design $\epsilon=\frac{\mathcal{L}_{0}^{U}-\mathcal{L}_{U}}{\mathcal{L}_{0}^{U}-
\mathcal{L}_{U}+\mathcal{L}_{0}^{P}-\mathcal{L}_{P}}$, and we discuss the following three cases:

- •
If $\mathcal{L}_{U}=\mathcal{L}_{1}^{UN}+\mathcal{L}_{0}^{UA},\mathcal{L}_{P}=
\mathcal{L}_{1}^{PN}+\mathcal{L}_{0}^{PA}$, then $\epsilon=\frac{\Delta^{UN}}{\Delta^{UN}+\Delta^{PN}}$, which is within the range;
- •
If $\mathcal{L}_{U}=\mathcal{L}_{1}^{UN}+\mathcal{L}_{1}^{UA},\mathcal{L}_{P}=
\mathcal{L}_{0}^{PN}+\mathcal{L}_{0}^{PA}$, then $\epsilon=1$, it encourages to fit $\mathcal{L}_{P}$;
- •
If $\mathcal{L}_{U}=\mathcal{L}_{0}^{UN}+\mathcal{L}_{0}^{UA},\mathcal{L}_{P}=
\mathcal{L}_{1}^{PN}+\mathcal{L}_{1}^{PA}$, then $\epsilon=0$, it encourages to fit $\mathcal{L}_{U}$.

We estimate $\mathcal{L}^{U}_{0}=\sum_{i\in U}\|x_{i}-\overline{G(x)}\|^{2}$
where $\overline{G(x)}=\frac{1}{|U|}\sum_{i\in U}G(x_{i})$, and $\mathcal{L}^{P}_{0}=\sum_{i\in P}\|x_{i}-\overline{G(x)}\|^{2}$ where $\overline{G(x)}=\frac{1}{|P|}\sum_{i\in P}G(x_{i})$. Let us denote this as loss1. We also provide results on real-world datasets with different designs of estimation in Table 9:

- •
loss2: $\mathcal{L}^{U}_{0}=\sum_{i\in U}\|x_{i}\|^{2}$ and $\mathcal{L}^{P}_{0}=\sum_{i\in P}\|x_{i}\|^{2}$
- •
loss3: $\mathcal{L}^{U}_{0}=\sum_{i\in U}\|G(x_{i})-\overline{x}\|^{2}$ and $\mathcal{L}^{P}_{0}=\sum_{i\in P}\|G(x_{i})-\overline{x}\|^{2}$
- •
loss4: $\mathcal{L}^{U}_{0}=\sum_{i\in U}\|x_{i}-\overline{x}\|^{2}$ and $\mathcal{L}^{P}_{0}=\sum_{i\in P}\|x_{i}-\overline{x}\|^{2}$

**Table 9: Performance of FairAD with different designs of $\mathcal{L}_{0}^{U}$ and $\mathcal{L}_{0}^{P}$.**
| Methods | MNIST-USPS (K=1200) | MNIST-Invert (K=500) |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Recall@K | ROCAUC | Rec Diff | Recall@K | ROCAUC | Rec Diff |  |
| loss1 | $67.16{\pm 0.37}$ | $91.27{\pm 0.49}$ | $3.73{\pm 2.13}$ | $72.37{\pm 0.32}$ | $98.03{\pm 0.01}$ | $6.75{\pm 0.34}$ |
| loss2 | $66.47{\pm 1.73}$ | $90.60{\pm 0.52}$ | $4.78{\pm 2.36}$ | $72.44{\pm 0.74}$ | $98.04{\pm 0.03}$ | $7.22{\pm 0.21}$ |
| loss3 | $66.31{\pm 0.65}$ | $91.37{\pm 0.88}$ | $6.32{\pm 1.74}$ | $71.39{\pm 1.96}$ | $97.22{\pm 1.42}$ | $8.95{\pm 0.92}$ |
| loss4 | $66.56{\pm 2.32}$ | $90.88{\pm 1.67}$ | $2.54{\pm 2.11}$ | $71.92{\pm 3.58}$ | $97.01{\pm 1.85}$ | $8.96{\pm 3.23}$ |

And we can see that although the results may vary with different estimation designs, our method always performs better than the baselines in both task performance and fairness.

### E.2 Proof of Lemma 4.4

$$ $\displaystyle D^{f}_{h,\mathcal{H}}(P_{U}\|P_{P})-D^{f}_{h,\mathcal{H}}(U\|P)$ $\displaystyle=\sup_{h^{\prime}\in\mathcal{H}}\{|R^{\ell}_{U}(h,h^{\prime})-R^{ f^{*}\circ\ell}_{P}(h,h^{\prime})|\}$ $\displaystyle\quad-\sup_{h^{\prime}\in\mathcal{H}}\{|\hat{R}^{\ell}_{U}(h,h^{ \prime})-\hat{R}^{f^{*}\circ\ell}_{P}(h,h^{\prime})|\}$ $\displaystyle\leq\sup_{h^{\prime}\in\mathcal{H}}\|R^{\ell}_{U}(h,h^{\prime})-R ^{f^{*}\circ\ell}_{P}(h,h^{\prime})|-|\hat{R}^{\ell}_{U}(h,h^{\prime})-\hat{R} ^{f^{*}\circ\ell}_{P}(h,h^{\prime})\|$ $\displaystyle\leq\sup_{h^{\prime}\in\mathcal{H}}|R^{\ell}_{U}(h,h^{\prime})-R^ {f^{*}\circ\ell}_{P}(h,h^{\prime})-\hat{R}^{\ell}_{U}(h,h^{\prime})+\hat{R}^{f ^{*}\circ\ell}_{P}(h,h^{\prime})|$ $\displaystyle=\sup_{h^{\prime}\in\mathcal{H}}|R^{\ell}_{U}(h,h^{\prime})-\hat{ R}^{\ell}_{U}(h,h^{\prime})|+|{R}^{f^{*}\circ\ell}_{P}(h,h^{\prime})-\hat{R}^{ f^{*}\circ\ell}_{P}(h,h^{\prime})|$ $\displaystyle\leq 2\mathfrak{R}_{P_{U}}(\ell\circ\mathcal{H})+\sqrt{\frac{\log \frac{1}{\delta}}{2m}}+2\mathfrak{R}_{P_{P}}(f^{*}\circ\ell\circ\mathcal{H})+ \sqrt{\frac{\log\frac{1}{\delta}}{2n}}$ $$

where the last inequality comes from the property of Rademacher complexity. Similarly, by Lemma 5.7 and Definition 3.2 of [] we have: $\mathfrak{R}_{P_{P}}(f^{*}\circ\ell\circ\mathcal{H})\leq L\mathfrak{R}_{P_{P}}
(\ell\circ\mathcal{H})$, with $f^{*}\circ\ell\circ\mathcal{H}:=\{x\mapsto\phi(\ell(h(x),h^{\prime}(x))):h,h^{
\prime}\in\mathcal{H}\}$.

### E.3 Proof of Theorem 4.5

$$ $\displaystyle R^{\ell}_{P}(h,a_{P})$ $\displaystyle\leq R^{\ell}_{P}(h,h^{*})+R^{\ell}_{P}(h^{*},a_{P})$ $\displaystyle(\text{triangle inequality }\ell)$ $\displaystyle=R^{\ell}_{P}(h,h^{*})+R^{\ell}_{P}(h^{*},a_{P})-R^{\ell}_{U}(h,h ^{*})+R^{\ell}_{U}(h,h^{*})$ $\displaystyle\leq R^{f^{*}\circ\ell}_{P}(h,h^{*})-R^{\ell}_{U}(h,h^{*})+R^{ \ell}_{U}(h,h^{*})+R^{\ell}_{P}(h^{*},a_{P})$ $\displaystyle\leq|R^{f^{*}\circ\ell}_{P}(h,h^{*})-R^{\ell}_{U}(h,h^{*})|+R^{ \ell}_{U}(h,h^{*})+R^{\ell}_{P}(h^{*},a_{P})$ $\displaystyle\leq D^{f}_{h,\mathcal{H}}(P_{U}\|P_{P})+R^{\ell}_{U}(h,h^{*})+R^ {\ell}_{P}(h^{*},a_{P})$ $\displaystyle\leq D^{f}_{h,\mathcal{H}}(P_{U}\|P_{P})+R^{\ell}_{U}(h,a_{U})+R^ {\ell}_{U}(h^{*},a_{U})+R^{\ell}_{P}(h^{*},a_{P})$ $\displaystyle=D^{f}_{h,\mathcal{H}}(P_{U}\|P_{P})+R^{\ell}_{U}(h)+R^{\ell}_{U} (h^{*})+R^{\ell}_{P}(h^{*})$ $$

### E.4 Proof of Theorem 4.6 and the benefit of our design

Combining Theorem 4.5, Lemma 4.4 and the property of Rademacher Complexity, we can easily get:

$$ $\displaystyle R^{l}_{P}(h)$ $\displaystyle-R^{l}_{U}(h)\leq D^{f}_{h,\mathcal{H}}(U\|P)$ $\displaystyle+\hat{R}^{l}_{U}(h^{*})+4\mathfrak{R}_{U}(\ell\circ\mathcal{H})+2 \sqrt{\frac{\log\frac{1}{\delta}}{2m}}$ $\displaystyle+\hat{R}^{l}_{P}(h^{*})+2(L+1)\mathfrak{R}_{P}(\ell\circ\mathcal{ H})+2\sqrt{\frac{\log\frac{1}{\delta}}{2n}}$ $$

Since by definition we have $D^{f}_{h,\mathcal{H}}(U\|P)\leq D_{f}(U\|P)$, and for $D_{f}(U\|P)=\operatorname{TV}(U\|P)$, we have:

$$ $\displaystyle R^{l}_{P}(h)$ $\displaystyle-R^{l}_{U}(h)\leq\operatorname{TV}(U\|P)$ (13) $\displaystyle+\hat{R}^{l}_{U}(h^{*})+4\mathfrak{R}_{U}(\ell\circ\mathcal{H})+2 \sqrt{\frac{\log\frac{1}{\delta}}{2m}}$ $\displaystyle+\hat{R}^{l}_{P}(h^{*})+2(L+1)\mathfrak{R}_{P}(\ell\circ\mathcal{ H})+2\sqrt{\frac{\log\frac{1}{\delta}}{2n}}.$ $$

Now we motivate why minimizing the objective $\mathcal{L}_{\mathrm{FAC}}$ leads to small $\operatorname{TV}(U\|P)$. Let $U,P$ be the empirical distributions over the common measurable space $\mathcal{X}\coloneqq\{z_{j}^{U}\}_{j=1}^{n}\cup\{z_{k}^{P}\}_{k=1}^{m}$ with densities $\hat{p}_{U},\hat{p}_{P}$ that are $c_{U},c_{P}$-Lipschitz with respect to $\ell_{2}$-norm, respectively. Let $x^{*}\coloneqq\operatorname*{argmin}_{x\in\mathcal{X}}\lvert\hat{p}_{U}(x)-
\hat{p}_{P}(x)\rvert$, $\delta\coloneqq\lvert\hat{p}_{U}(x^{*})-\hat{p}_{P}(x^{*})\rvert$, and

$$ $\sigma\coloneqq\sum_{x\in\mathcal{X}}\lVert x-x^{*}\rVert=\sum_{x\in\mathcal{X }}\sqrt{2-2\log\operatorname{sim}(x,x^{*})},$ $$

where the equality is due to law of cosine (and that $\operatorname{sim}$ normalizes $z_{j}$). We first show how $\operatorname{TV}(U\|P)$ is related to $\delta$ and $\sigma$.

###### Lemma E.1 .

$$ $\operatorname{TV}\left(U\|P\right)\leq\frac{1}{2}\left(\lvert\mathcal{X}\rvert \delta+(c_{U}+c_{P})\sigma\right).$ $$

###### Proof.

$$ $\displaystyle\operatorname{TV}\left(U\|P\right)$ $\displaystyle\coloneqq\frac{1}{2}\sum_{x\in\mathcal{X}}\lvert\hat{p}_{U}(x)- \hat{p}_{P}(x)\rvert$ $\displaystyle\leq\frac{1}{2}\sum_{x\in\mathcal{X}}\lvert\hat{p}_{U}(x)-\hat{p} _{U}(x^{*})\rvert+\lvert\hat{p}_{U}(x^{*})-\hat{p}_{P}(x^{*})\rvert+\lvert\hat {p}_{P}(x^{*})-\hat{p}_{P}(x)\rvert$ (triangle inequality) $\displaystyle=\frac{1}{2}\left(\lvert\mathcal{X}\rvert\delta+\sum_{x\in \mathcal{X}}\lvert\hat{p}_{U}(x)-\hat{p}_{U}(x^{*})\rvert+\lvert\hat{p}_{P}(x) -\hat{p}_{P}(x^{*})\rvert\right)$ $\displaystyle\leq\frac{1}{2}\left(\lvert\mathcal{X}\rvert\delta+(c_{U}+c_{P}) \sum_{x\in\mathcal{X}}\lVert x-x^{*}\rVert\right)$ (Lipschitz conditions) $\displaystyle=\frac{1}{2}\left(\lvert\mathcal{X}\rvert\delta+(c_{U}+c_{P}) \sigma\right).$ $$

∎

Next we motivate why minimizing our objective $\mathcal{L}_{\mathrm{FAC}}$ leads to small $\delta$ and $\sigma$ simultaneously, hence small $\operatorname{TV}(U\|P)$. Recall that our fairness-aware contrastive loss is

$$ $\mathcal{L}_{\mathrm{FAC}}\coloneqq\mathcal{L}_{\mathrm{fair}}+\mathcal{L}_{ \mathrm{unif}},$ $$

where

$$ $\displaystyle\mathcal{L}_{\mathrm{fair}}$ $\displaystyle\coloneqq-\log\left(\sum_{j\in[n]}\sum_{k\in[m]}\operatorname{sim }\left(z_{j}^{U},z_{k}^{P}\right)\right),$ $\displaystyle\mathcal{L}_{\mathrm{unif}}$ $\displaystyle\coloneqq\log\left(\sum_{j\neq k}\operatorname{sim}\left(z_{j}^{U },z_{k}^{U}\right)+\sum_{j\neq k}\operatorname{sim}\left(z_{j}^{P},z_{k}^{P} \right)\right).$ $$

Intuitively, minimizing $\mathcal{L}_{\mathrm{FAC}}$ leads to small $\mathcal{L}_{\mathrm{fair}}$ and $\mathcal{L}_{\mathrm{unif}}$ simultaneously, which correspond to large $\operatorname{sim}(z_{j}^{U},z_{k}^{P})$ and small $\operatorname{sim}(z_{j}^{U},z_{k}^{U}),\operatorname{sim}(z_{j}^{P},z_{k}^{P})$, which in turn correspond to small $\lVert z_{j}^{U}-z_{k}^{P}\rVert$ and large $\lVert z_{j}^{U}-z_{k}^{U}\rVert,\lVert z_{j}^{P}-z_{k}^{P}\rVert$. Hence it is natural to consider the following surrogate losses

$$ $\displaystyle\mathcal{L}_{\mathrm{fair}}^{\prime}$ $\displaystyle\coloneqq\sum_{j,k\in[n]}\lVert z_{j}^{U}-z_{k}^{P}\rVert,$ $\displaystyle\mathcal{L}_{\mathrm{unif}}^{\prime}$ $\displaystyle\coloneqq-(\sum_{j\neq k}\lVert z_{j}^{U}-z_{k}^{U}\rVert+\lVert z _{j}^{P}-z_{k}^{P}\rVert).$ $$

Then it follows immediately that $\sigma\leq\mathcal{L}_{\mathrm{fair}}^{\prime}$, explaining why minimizing our objective $\mathcal{L}_{\mathrm{FAC}}$ (hence $\mathcal{L}_{\mathrm{fair}}^{\prime}$) leads to small $\sigma$.

To see that $\delta\coloneqq\lvert\hat{p}_{U}(x^{*})-\hat{p}_{P}(x^{*})\rvert$ cannot be too large, first consider the extreme case where $\{z_{j}^{U}\}_{j=1}^{n}\cap\{z_{k}^{P}\}_{k=1}^{n}=\emptyset$. Without loss of generality let $\lVert z_{1}^{U}-z_{1}^{P}\rVert=\max_{j,k\in[n]}\lVert z_{j}^{U}-z_{k}^{P}\rVert$. Then adjusting $z_{1}^{U},z_{1}^{P}$ to be the unit vector on their angle bisector clearly decreases $\mathcal{L}_{\mathrm{fair}}^{\prime}$ without affecting $\mathcal{L}_{\mathrm{unif}}^{\prime}$ by much due to high uniformity within $\{z_{j}^{U}\}_{j=1}^{n}$ and $\{z_{k}^{P}\}_{k=1}^{n}$ respectively. Hence we may assume without loss of generality that $z_{1}^{U}=z_{1}^{P}=x^{*}$. Next consider the extreme case where $\hat{p}_{U}(x^{*})=\frac{1}{n}$ and $\hat{p}_{P}(x^{*})=1$. Then adjusting $z_{2}^{P}=\operatorname*{argmax}_{x\neq x^{*}}\sum_{j\in[n]}\lVert x-z_{j}^{U}\rVert$ clearly decreases $\mathcal{L}_{\mathrm{unif}}^{\prime}$ without affecting $\mathcal{L}_{\mathrm{fair}}^{\prime}$ by much due to high uniformity within $\{z_{j}^{U}\}_{j=1}^{n}$. Hence minimizing our objecive $\mathcal{L}_{\mathrm{FAC}}$ leads to small $\delta\coloneqq\lvert\hat{p}_{U}(x^{*})-\hat{p}_{P}(x^{*})\rvert$.

###### Lemma E.1 .

###### Proof.

## Appendix F Additional Experiments

### F.1 Training details and Code

For the COMPAS dataset, we use a two-layer MLP with hidden units of [32, 32]. For all the other datasets, we use MLP with one hidden layer of dimension 128. All our experiments were executed using one Tesla V100 SXM2 GPUs, supported by a 12-core CPU operating at 2.2GHz. For three runs, we choose random seeds in [40,41,42].

### F.2 More effectiveness validation of FairAD under different k

We also conduct experiments on the four datasets with different choices of k, and the results are in Table 10 and Table 11. The AUCROC scores are the same as in the main paper. We can also tell from the tables that accuracy difference is inadequate for measuring group fairness in the imbalanced setting.

**Table 10: Performance on Image Datasets.**
| Methods | MNIST-USPS (K=1000) | MNIST-Invert (K=400) |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Recall@K | Acc Diff | Rec Diff | Recall@K | Acc Diff | Rec Diff |  |
| FairOD | $10.46{\pm 1.16}$ | $4.35{\pm 0.33}$ | $13.21{\pm 1.43}$ | $6.05{\pm 0.21}$ | $2.70{\pm 0.15}$ | $9.99{\pm 1.18}$ |
| DCFOD | $10.24{\pm 0.82}$ | $4.79{\pm 1.12}$ | $8.40{\pm 1.83}$ | $5.57{\pm 1.70}$ | $2.69{\pm 0.37}$ | $8.78{\pm 2.31}$ |
| FairSVDD | $13.75{\pm 1.83}$ | $5.73{\pm 5.64}$ | $13.49{\pm 2.55}$ | $10.57{\pm 0.92}$ | $5.38{\pm 3.12}$ | $14.25{\pm 2.96}$ |
| MCM | $34.38{\pm 0.32}$ | $29.81{\pm 0.84}$ | $52.46{\pm 0.94}$ | $22.48{\pm 0.54}$ | $8.32{\pm 1.10}$ | $64.37{\pm 1.66}$ |
| NSNMF | $33.56{\pm 0.70}$ | $22.26{\pm 0.40}$ | $65.12{\pm 2.36}$ | $43.91{\pm 0.84}$ | $4.54{\pm 0.20}$ | $55.20{\pm 0.92}$ |
| Recontrast | $45.73{\pm 2.74}$ | $10.59{\pm 2.62}$ | $29.62{\pm 2.40}$ | $52.00{\pm 4.86}$ | $13.81{\pm 4.30}$ | $54.96{\pm 13.77}$ |
| FairAD | $61.60{\pm 2.50}$ | $6.50{\pm 0.89}$ | $7.95{\pm 5.94}$ | $62.28{\pm 3.24}$ | $1.62{\pm 1.32}$ | $7.02{\pm 4.48}$ |

**Table 11: Performance on Tabular Datasets**
| Methods | COMPAS (K=300) | CelebA (K=4500) |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Recall@K | Acc Diff | Rec Diff | Recall@K | Acc Diff | Rec Diff |  |
| FairOD | $14.20{\pm 1.83}$ | $3.92{\pm 1.63}$ | $10.75{\pm 0.90}$ | $7.95{\pm 0.21}$ | $4.94{\pm 0.25}$ | $2.26{\pm 1.06}$ |
| DCFOD | $13.10{\pm 1.35}$ | $3.57{\pm 2.29}$ | $7.23{\pm 2.82}$ | $8.64{\pm 0.79}$ | $4.98{\pm 0.40}$ | $9.24{\pm 1.12}$ |
| FairSVDD | $13.02{\pm 1.66}$ | $3.90{\pm 2.43}$ | $9.45{\pm 3.80}$ | $8.82{\pm 0.61}$ | $2.21{\pm 0.40}$ | $10.22{\pm 2.33}$ |
| MCM | $16.87{\pm 1.14}$ | $4.10{\pm 1.98}$ | $10.17{\pm 1.64}$ | $9.26{\pm 0.48}$ | $7.21{\pm 5.98}$ | $28.69{\pm 12.14}$ |
| NSNMF | $17.29{\pm 1.42}$ | $3.60{\pm 1.93}$ | $33.57{\pm 1.22}$ | $8.90{\pm 1.09}$ | $5.66{\pm 0.54}$ | $40.51{\pm 1.54}$ |
| FairAD | $19.14{\pm 2.29}$ | $9.35{\pm 3.00}$ | $4.75{\pm 3.69}$ | $10.56{\pm 1.11}$ | $13.04{\pm 0.30}$ | $5.10{\pm 1.52}$ |

### F.3 More Ablation Study

We conduct the ablation study to demonstrate the necessity of each component of FairAD on the Compas dataset. The experimental results are presented in Figure 4, where (a) and (b) show the recall@350 and recall difference, respectively. Specifically, FairAD-R refers to a variant of our method replacing rebalancing autoencoder with $\mathcal{L}_{2}$ in Equation (4); FairAD-N and FairAD-D remove $\mathcal{L}_{\text{fair}}$ and $\mathcal{L}_{\text{unif}}$ in Equation (3), respectively; FairAD-C substitute the proposed fair contrastive loss with the traditional contrastive loss (i.e., $\mathcal{L}_{1}$). We have the following observations: (1) FairAD greatly outperforms FairAD-D and FairAD-N, which suggests that $\mathcal{L}_{\text{fair}}$ and $\mathcal{L}_{\text{unif}}$ are two essential components in our designed method. (2). FairAD-C has the competitive performance as FairAD with respect to recall rate, while it has a large recall difference. This suggests that without proper regularization, the results exhibit unfair behaviors. Different from FairAD-C, FairAD achieves a much lower recall difference, which further verifies our assumption that our proposed method could guarantee group fairness.

Figure: Figure 4: Ablation Study on Compas dataset.
Refer to caption: extracted/5859862/figs/ablation_study_compas_recall.jpg

## Appendix G Limitations and Broader Impact

This paper proposes a fairness-aware anomaly detection, which aims to provide fair results when the algorithm is applied to detect anomalies. Our method currently focus on the binary group fairness case. We can naturally extend our framework to the multi-attribute case by encouraging the similarity among the groups. Incoporating individual fairness notions would be an interesting future direction. By embedding fairness into anomaly detection algorithms, this work contributes to reducing bias and discrimination in AI applications, ensuring that technologies serve diverse populations equitably. In sectors such as finance, healthcare, and law enforcement, where anomaly detection plays a crucial role in identifying fraud, diseases, and criminal activities, incorporating fairness principles can prevent the perpetuation of historical biases and protect vulnerable groups from unjust outcomes. Furthermore, by advancing fairness in AI, this research aligns with global efforts to promote ethics in technology development, fostering trust between AI systems and their users.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: see weaknesses.
soundness: 3
strengths: 1. The issue of fairness in anomaly detection is a highly important and meaningful problem.
2. The paper provides theoretical guarantees for the proposed method.
3. The method's effectiveness is empirically validated on real datasets.
summary: This paper addresses the challenge of ensuring fairness in anomaly detection (AD), particularly in scenarios with imbalanced data between protected and unprotected groups.  To tackle this, the authors propose FADIG, a fairness-aware anomaly detection method. FADIG integrates a fairness-aware contrastive learning module and a rebalancing autoencoder module to address fairness and data imbalance issues. Theoretical analysis demonstrates that the proposed method ensures group fairness, and empirical studies confirm its effectiveness and efficiency across multiple real-world datasets.
weaknesses: 1. The paper presents two challenges: C1, handling imbalanced data, and C2, mitigating representation disparity. There is a strong coupling between these two challenges, as imbalanced data leads to representation disparity (i.e., group imbalance results in higher errors for protected groups, causing misclassifications). From this perspective, addressing C1 effectively resolves C2, which makes me question the necessity of the fairness-aware contrastive learning module.
2. The paper lacks novelty. The conclusion that group imbalance leads to accuracy parity issues is well-known, and addressing accuracy parity by solving group imbalance has been widely used. From the results presented in this paper, I do not see any specific uniqueness in the context of anomaly detection.
3. The paper lacks a discussion of related work, specifically in two areas:
* The differences between this work and existing work on anomaly detection and imbalanced data.
* The differences between the fair contrastive learning methods used in this paper and other existing methods.
4. The writing is poor. For example, 
* the statement "In this work, we focus on the group fairness notion which usually pursues the equity of certain metrics among the groups. For instance, Accuracy Parity (Zafar et al., 2017) requires the same task accuracy between groups and Equal Opportunity (Hardt et al., 2016) requires the same true positive rate instead." suggests that the authors consider both Accuracy Parity and Equal Opportunity as fairness metrics. However, in the experiments, only Accuracy Parity is used, which is confusing.
* Figure 2 seems confusing.

---

confidence: 5
contribution: 3
initial_rating: 6
presentation: 4
questions: Are there simpler considerations for \epsilon that can be informed from the imbalance factor of groups? How does \epsilon work for multi-valued attributes and multiple protected attributes?
soundness: 3
strengths: 1. Rebalancing autoencoder with learnable weight for reconstruction loss is a simple way to encourage learning patterns from minority groups. I like the analytical calculation of \epsilon. 
2. An elegant extension of contrasive entropy for uniform representation to incorporate fairness criterion as contrastive entropy across majority and minority groups.
3. Paper is easy to read and follow.
summary: The paper focuses on fairness in outlier detection in unsupervised learning specifically addressing imbalance data that naturally arises in presence of minority groups. The paper presents a method for addressing representation disparity due to imbalance by proposing a fairness-aware contrative learning criterion and a reconstruction based network module with weights to account for patterns from minority groups. The work emphasizes the use fairness-aware constrastive loss as the main driver for framework as it leads to small total variation distance between the groups. Empirical results show the effectiveness of the proposed method across multiple real-world datasets when compared to exciting fairness-aware methods.
weaknesses: 1. In most applications we have multi-valued multiple protected attributes. It seems that it is non-trivial to extend the loss function to cater to such datasets. How does the method scale with multi valued multiple protected attribute setup?
2. The choice of \alpha hyperparameter is arbitrary. Why 4 works and not 8? How does one choose the value of this hyperparameter in real world scenario?
3. The paper completely ignores the discussion on hyperparameter settings for the competitors. To ensure fairness to competitors, the detailed hyperparameter settings should be included for each compared method to better illustrate the benefits of the proposed method.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please refer to the weakness section.
soundness: 2
strengths: 1. The proposed technique shows that if it is known what the underrepresented groups are, then we can possibly use that information to improve anomaly detection through fairly straight-forward ways

  2. The ablation experiments help to understand the importance of individual components of the loss function


============

Update after author rebuttals:

Revising my scores after going over other reviewer's comments and being satisfied with most of author responses to my comments.
summary: The paper proposes a technique to introduce weighted/cost-based loss function that pays attention to underrepresented groups in data such that the dominant groups do not have undue influence on the learned model.
weaknesses: Overall, the paper needs to be written more clearly and unambiguously. Main comments are:


1. Section 2: The paper defines protected groups on the basis of a single feature -- this might be rather simplistic. Instead, in real data, there could be a combination of one or more features that defines the protected/unprotected classification. In reality, it might not be easy to identify the underrepresented groups automatically.


2. Why restrict to a single protected group? There might be multiple 'protected' groups that have very distinct characteristics.


3. Wouldn't it be better to have separate anomaly detectors for each (prot/unprot) group? Was that approach considered as a benchmark?


4. Figure 2: It is hard to differentiate between red and pink dots in the figure.


5. Line 194: "... learning can alleviate this issue by pushing examples uniformly distributed in ..." -- Hard to understand this sentence. Maybe there is some grammatical error?


6. Lines 195-196: "... to learn representations by distinguishing different views of one example from other examples as follows:" -- Not clear what this means exactly.


7. Line 208: "... to maximize the cosine similarity between the representations of the two groups, ..." -- This is very ambiguous. It needs to be very clearly stated what the goal is: for example, maximize the similarity among the instances in the protected group? And separately among instances in the unprotected group? It seems that minimizing L_{FAC} in Eqn 3 implies minimizing the intra-group similarity (second term on the right). This has not been clearly stated. If there is more than one protected group, how would that affect the loss function?


8. Line 238, Eqn 5: It is not clear what exact \epsilon values were used in the experiments even though some selection technique is mentioned in the Appendix.


9. Line 354-355: "... improved by minimizing the discrepancy between the two distributions and ..." -- this discrepancy is probably a property of the real-world which is not in our control. Therefore, trying to minimize it should not be an option.


10. Line 375: "... method which incorporates the prescribed criteria into ..." -- Which prescribed criteria? Need to be more clear and specific.


11. Table 3: While the proposed technique (FADIG) is shown to perform well, it has an unfair advantage because it has the extra information about the under-represented groups that is not available to other algorithms.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: - I'm missing a connection of the fairness discussion, and the presence of multiple groups, to the more classical literature on anomaly detection. Specifically anomaly detection in the presence of multiple groups has been studied extensively, and relates to the concept of "local" and "global" anomalies, see for example "LOF: identifying density-based local outliers" by Breunig et al., "LoOP: local outlier probabilities" by Kriegel et al., other work by Kriegel et al. throughout the 00's and 10' as well as a recent examination by Bouman et al. in "Unsupervised Anomaly Detection Algorithms on Real-world Data: How Many Do We Need?". Can the authors elaborate on this connection? 
- Figure 2 is currently hard to understand. What representation is being shown? Why is the data circularly constrained, which dataset is shown, what do the x and y-axis represent? Consider revising this.
- What does the FADIG abbreviation mean? The beginning of section 3 implies an abbreviation due to the capitalization, but it does not match up with the letters and is therefore slightly confusing.
- It currently still eludes me how the model is applied in practice in the unsupervised setting. Specifically, without knowledge of whether a sample belongs to the protected or unprotected group at train time, how is the loss calculated? It seems that we need access to the protected and unprotected loss, but within the unsupervised setting we would never be able to differentiate between the two. Could the authors elaborate further?
- In the characteristics of the datasets, it seems that the number of anomalies for the 4 datasets is 1205, 479, 364, and 5150. Yet, the k-values chosen for the results presented are not at these values, but rather at values close. Where does this difference come from? I would like to remark that this is not in line with other measures such as the r-precision, which are calculated with k being the exact number of anomalies in the dataset.
- Some detectors do not perform well on any dataset. Could the authors elaborate on how this could happen? I've noted here that for example FairOD uses fully different benchmarking datasets, why not include these for this study?
- The chosen architecture for the used autoencoder is fairly shallow, and notable barely compresses the data. How were these architectures chosen, and how did the authors ensure that they did not overfit on the proposed benchmark? Similarly, could more details on other hyperparameters and how they were chosen be provided?
- In the reproducibility section, the authors list the random seeds that were used. These do not seem structured in either a logical, or a random way, which leads me to suspect that some, albeit accidental, cherrypicking may have occured. Could the authors elaborate on this?
soundness: 2
strengths: The paper clearly states its purpose. The mathematics of the paper are fairly easy to follow and clearly substantiate the intuitive reasoning of the method. The proposal of the authors should also be lauded for its relative simplicity which achieves (seeminly) good results.
summary: The authors propose a new fairness-aware anomaly detection method called FADIG. Their method uses contrastive learning and a modified, reweighted, autoencoder in order to detect anomalies in datasets with multiple groups of differing representation.
weaknesses: The points below are given in no particular ordering of importance (within category):

**Major:**
- The authors state in the second paragraph of the introduction that deep anomaly detection methods demonstrate significantly better performance than shallow anomaly detection methods. While this can easily be argued for certain applications such as computer vision, it is certainly not true for tabular data, which is also analyzed within this paper and several of the other methods benchmarked in this study. See for example recent comparisons in ADBench by Han et al. (2022) and Bouman et al. (2024) in "Unsupervised Anomaly Detection Algorithms on Real-world Data: How Many Do We Need?".
- The use of an autoencoder as an anomaly detector relies heavily on an assumption stated by the authors that " Anomalies tend to exhibit large reconstruction errors because they do not conform to the patterns in the data as coded by the autoencoder." This is an assumption which has been heavily questioned in recent studies, such as:
	- Nicholas Merrill and Azim Eskandarian. Modified autoencoder training and scoring for robust unsupervised anomaly detection in deep learning. IEEE Access, 8:101824–101833, 2020.
	- Laura Beggel, Michael Pfeiffer, and Bernd Bischl. Robust anomaly detection in images using adversarial autoencoders. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, W¨urzburg, Germany, September 16–20, 2019, Proceedings, Part I, pp. 206–222. Springer, 2020
	- Marcella Astrid, Muhammad Zaigham Zaheer, Jae-Yeong Lee, and Seung-Ik Lee. Learning not to reconstruct anomalies. arXiv preprint arXiv:2110.09742, 2021.
	- Marcella Astrid, Muhammad Zaigham Zaheer, Djamila Aouada, and Seung-Ik Lee. Exploiting autoencoder’s weakness to generate pseudo anomalies. Neural Computing and Applications, pp. 1–17, 2024
	- Dong Gong, Lingqiao Liu, Vuong Le, Budhaditya Saha, Moussa Reda Mansour, Svetha Venkatesh, and Anton van den Hengel. Memorizing normality to detect anomaly: Memory-augmented deep autoencoder for unsupervised anomaly detection. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 1705–1714, 2019.
	- Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Daeki Cho, and Haifeng Chen. Deep autoencoding gaussian mixture model for unsupervised anomaly detection. In International conference on learning representations, 2018
- The authors assume in section 3.2 that the model is only capable of fitting 2 out of 4 subgroups. Yet this seems like a strong assumption with little theoretical foundation.
- For the CelebA dataset, all detectors perform much worse than should be expected, with almost all detectors being close to random. This indicates that perhaps it is not a well-suited benchmark dataset, or other detectors should be shown which do perform well.



**Minor:**
- The connection to relevant literature is too sparse. Applications and other studies into fairness of anomaly detectors should be elaborated upon in more detail during the introduction.
- The captions of figures are somewhat shorthand. I would advise the authors to rethink the captions so they allow for the figures to be understood more easily as-as, rather than needing the full context of the section or paper.
- The introduction currently contains a preview of the results, which disturbs the flow of the paper. I'd advise to move this to the result section in full.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: Please check my comments above.
soundness: 3
strengths: - This paper targets an important but still under-exploited problem: fair anomaly detection.

- The proposed approach can achieve a better trade-off between utility and fairness.
summary: This paper develops a fair anomaly detection model based on reconstruction-based detection. A fairness-aware contrastive learning and a re-balancing autoencoder are developed to ensure fairness.
weaknesses: - Maybe I am missing something. Section 4 looks incomplete to me. It demonstrates the fairness with Rademacher Complexity, but I am not sure how the proposed approach can minimize the upper bound given in Theorem 4.6. That said, it would be better to provide a more explicit explanation of how the proposed components (the fairness-aware contrastive learning or re-balancing autoencoder) relate to minimizing the terms in the upper bound given in Theorem 4.6.

- Theorem 4.5 states that the *risk difference* between the two groups is upper bounded by Eq 10. Are there any connections between the risk difference in terms of Rademacher complexity and risk difference in terms of fairness metrics, such as the recall-based metrics used in experiments?

    - Please clarify whether there's a theoretical relationship between the risk difference bound and the recall difference metric used in the experiments. 
   

- Overall, Section 4 looks more like a general theoretical analysis. It would be better to explicitly discuss how to leverage the theorems in Sec 4 to analyze the fairness issue in anomaly detection tasks, especially the reconstruction-based anomaly detection models.

Meta-review: I have read all the materials of this paper including the manuscript, appendix, comments, and response. Based on collected information from all reviewers and my personal judgment, I can make the recommendation on this paper, reject. No objection from reviewers who participated in the internal discussion was raised against the reject recommendation.

**Research Question**

This paper considers the fair outlier detection problem. 

**Challenge Analysis**

The authors argue that the learning objectives of most existing anomaly detection methods tend to solely concentrate on the dominating unprotected group. To make this statement more concrete, the authors provide an empirical example in the introduction part. The authors analyze that misclassification arises from models focusing on learning frequent patterns in the more abundant unprotected group (A). Unfortunately, this statement has no rationality. Then, the authors aim to tackle two challenges (B), handling imbalanced data and mitigating the representation parity. Again, I do not see a link between (A) and (B). Moreover, the targeted challenges are the common tasks in fair outlier detection, where all the existing methods also consider these two points. 

Here I would like to share my opinion on challenge analysis. For a newly defined research question, the challenge analysis comes from the difficulty of the research question; for a well-defined one, the challenge analysis comes from the drawbacks of existing solutions. For this paper, the authors seem to mix up the above points. Moreover, the presentation is not logically smooth. 

**Technique**

For the above challenges, the authors propose two modules, fairness-aware contrastive learning module and re-balancing autoencoder. Technically speaking, I do not feel the proposed method is very novel, but it can tackle the research question. 

**Theoretical Analysis**

The analysis in this paper is disconnected with the proposed method. I do not think it is a plus. 

**Experiment**

The experiments seems extensive. However, two reviewers point out the comparisons to other methods and their experimental setup is insufficiently insightful. The authors need to demonstrate where the gain comes from.

Decision: Reject