# Model Selection of Anomaly Detectors in the Absence of Labeled Validation
Data

Clement Fung
Carnegie Mellon University
&Chen Qiu
Bosch Center for AI
&Aodong Li
University of California, Irvine
&Maja Rudolph
Bosch Center for AI
Work done during internship at Bosch Center for AI.

###### Abstract

Anomaly detection requires detecting abnormal samples in large unlabeled
datasets. While progress in deep learning and the advent of foundation models
has produced powerful unsupervised anomaly detection methods, their deployment
in practice is often hindered by the lack of labeled data—without it, the
detection accuracy of an anomaly detector cannot be evaluated reliably. In
this work, we propose a general-purpose framework for evaluating image-based
anomaly detectors with synthetically generated validation data. Our method
assumes access to a small support set of normal images which are processed
with a pre-trained diffusion model (our proposed method requires no training
or fine-tuning) to produce synthetic anomalies. When mixed with normal samples
from the support set, the synthetic anomalies create detection tasks that
compose a validation framework for anomaly detection evaluation and model
selection. In an extensive empirical study, ranging from natural images to
industrial applications, we find that our synthetic validation framework
selects the same models and hyper-parameters as selection with a ground-truth
validation set. In addition, we find that prompts selected by our method for
CLIP-based anomaly detection outperforms all other prompt selection
strategies, and leads to the overall best detection accuracy, even on the
challenging MVTec-AD dataset.

##  1 Introduction

Anomaly detection, automatically identifying samples that deviate from normal
behavior, is an important technique for supporting medical diagnosis (Fernando
et al., 2021), safeguarding financial transactions (Ahmed et al., 2016),
bolstering cybersecurity (Mirsky et al., 2018; Siadati & Memon, 2017), and
ensuring smooth industrial operations (Bergmann et al., 2019). There has been
significant progress in data-driven approaches for unsupervised anomaly
detection (Deecke et al., 2021; Liznerski et al., 2022; Jeong et al., 2023b;
Li et al., 2023a; 2021; Reiss et al., 2021). Before an anomaly detection
method can be safely deployed in a new application, one must trust that it
performs as well as expected, but performing such an evaluation is often
hindered by a major barrier: the absence of labeled validation data. In many
applications, validation data is typically absent because anomalies are rare
and the large volume of available data is too expensive to label (Görnitz et
al., 2013; Trittenbach et al., 2021).

Labeled validation data is also beneficial for zero-shot anomaly detection.
With recent developments in foundation models, it has become possible to pre-
train a large model on large-scale data from one domain and then to deploy it
for a new anomaly detection task. Specifically, CLIP-based anomaly detection
approaches (Jeong et al., 2023b; Liznerski et al., 2022; Zhou et al., 2021;
Esmaeilpour et al., 2022) have shown great performance in a variety of
domains. While these approaches provide the exciting possibility to construct
new anomaly detectors for new applications on demand, they could be more
readily deployed in real-world applications if labeled validation data could
aid with prompt selection and model evaluation.

In this work, we study the efficacy of synthetically generated anomalies for
model selection of image-based anomaly detectors. Given a new image-based
anomaly detection task, such as detecting faulty objects in a manufacturing
plant, we assume access to a small set of normal samples (Zhao et al., 2021).
Our approach leverages diffusion models (Ho et al., 2020; Song et al., 2021;
Jeong et al., 2023a) to generate synthetic anomalies from this small set of
examples. The synthetic anomalies are then mixed with the normal examples to
provide a synthetic validation set. In extensive experiments, ranging from
natural images to industrial applications, we show, that the performance on
anomaly detection benchmarks with synthetically generated validation sets
often matches results on a validation set with ground truth labels.

Importantly, we develop a method for anomaly generation, that does not require
training or fine-tuning a new diffusion model for the specialized anomaly
detection task. Instead, we use the available normal samples and a diffusion
model pre-trained on ImageNet (Deng et al., 2009; Dhariwal & Nichol, 2021) to
interpolate between those normal samples (Jeong et al., 2023a). We find that
even for domains that are far from ImageNet, such as the industrial images in
the MVTec-AD dataset (Bergman & Hoshen, 2020), this scheme generates synthetic
anomalies with realistic backgrounds and consistent visual patterns.

Our work makes the following contributions:

  * •

In Sec. 3.1, we present a framework for selecting image-based anomaly
detection models based on synthetically generated anomalies. Figure 1 shows
the outline of our approach.

  * •

We propose a practical technique for generating synthetic anomalies that uses
a general-purpose pre-trained diffusion model—without any fine-tuning or
auxiliary datasets, described in Sec. 3.2.

  * •

We empirically evaluate our method on a wide range of anomaly detection tasks
and demonstrate its success on two use-cases: model selection amongst
candidate anomaly detectors (Sec. 4.2) and prompt selection for anomaly
detection with CLIP (Sec. 4.3).

##  2 Related Work

#### Unsupervised anomaly detection.

Recent advances in anomaly detection models include autoencoder-methods (Chen
& Konukoglu, 2018; Principi et al., 2017), deep one-class classification (Ruff
et al., 2018; 2019), and self-supervised learning-based methods (Bergman &
Hoshen, 2020; Hendrycks et al., 2019b; Qiu et al., 2021; Sohn et al., 2020;
Qiu et al., 2022a; Schneider et al., 2022). While these methods are
unsupervised, their architectures and training frameworks involve various
hyperparameters, which can have a strong impact on detection accuracy (Campos
et al., 2016; Goldstein & Uchida, 2016; Han et al., 2022). While Ding et al.
(2022) propose to circumvent model selection by building an ensemble of
candidate methods, model selection typically requires labeled validation data.

In outlier exposure (Hendrycks et al., 2019a), which has been extended to
anomaly detection with contaminated data (Qiu et al., 2022b) and to meta-
learning (Li et al., 2023b), further improvements in detection accuracy come
from using samples from an auxiliary dataset, usually Tiny-ImageNet. Although
these auxiliary samples provide valuable additional training signal, they are
too dissimilar from normal samples and can be easily detected; therefore, they
are not useful for model evaluation or selection. Work in semi-supervised
anomaly detection (Görnitz et al., 2013; Das et al., 2016; Trittenbach et al.,
2021; Li et al., 2023a) assumes access to a training set with some labeled
anomalies but obtaining such data is unrealistic in most real-world
applications.

#### Anomaly detection with foundation models.

Nowadays, large models can be pre-trained on massive datasets to learn rich
semantic image features which have proven useful for anomaly detectors in
other vision domains—little to no additional training required. Large vision
models such as vision transformers (ViT, Dosovitskiy et al. (2021)) or
residual networks (ResNet, He et al. (2016)) pre-trained on ImageNet (Deng et
al., 2009), can often be used as anomaly detectors in other vision domains,
either without fine-tuning or by fine-tuning an outlier exposure objective
(Deecke et al., 2021; Fort et al., 2021; Mirzaei et al., 2023; Reiss et al.,
2021).

Another powerful class of foundation models are vision-language models like
CLIP (Radford et al., 2021). Esmaeilpour et al. (2022) use a support set of
normal samples to learn a text description generator for CLIP-based out-of-
distribution detection. With hand-crafted text prompts CLIP can be employed on
a new anomaly detection (Liznerski et al., 2022) or anomaly segmentation task
(Jeong et al., 2023b; Zhou et al., 2021) without any training, i.e. in a zero-
shot manner, which means no training data for the new task is required.
However, detection performance depends on several key hyperparameters,
especially the choice of prompts (Liznerski et al., 2022; Jeong et al.,
2023b), which implies that labeled validation data for prompt selection would
be highly beneficial. However, in the age of foundation models, when task-
specific instances of foundation models require little to no data, it does not
make sense to assume access to labeled validation data.

#### Evaluation of tabular and time-series anomaly detection.

Nguyen et al. (2016); Marques et al. (2015; 2020) propose unsupervised model
selection strategies with so called “internal metrics” that can be computed
from predicted anomaly scores on unlabeled data. (See Ma et al. (2023) for a
review.) Meta-training can offer another set of approaches for unsupervised
anomaly detector selection (Schubert et al., 2023; Zhao et al., 2021; 2022).
However, since meta-learning requires a large number of related labeled
datasets, their application has been limited to tabular data, and prior work
on internal metrics has been applied to tabular anomaly detection only (Nguyen
et al., 2016; Marques et al., 2015; 2020; Ma et al., 2023). In contrast, we
exploit recent advances in diffusion models to enable anomaly detection model
selection without labeled validation data in the vision domain. In time-series
anomaly detection, model evaluation is also known to be biased and unreliable
due to poorly labeled test data (Wu & Keogh, 2020; Wagner et al., 2023). Here,
hand-crafted anomalies can be useful (Lai et al., 2021). But for the
evaluation of vision-based anomaly detectors, synthetic anomalies need to go
beyond pixel-wise manipulation and are instead required to reflect abnormal
patterns in a more complex, and often semantic, level of abstraction.

#### Generating images with guidance.

Diffusion models (Ho et al., 2020; Song et al., 2021) have recently been found
to outperform other generative models (Dhariwal & Nichol, 2021). Although
generative models are traditionally used to generate in-distribution data, a
variety of prior work has proposed techniques that guide generative models to
generate new distributions. Specifically, text-guided generation (Kim et al.,
2022; Kwon et al., 2023; Kawar et al., 2023; Mokady et al., 2023; Tumanyan et
al., 2023) with CLIP (Radford et al., 2021) guided the diffusion-based image
generation process with text prompts to generate samples from a distribution
of interest, e.g. “cat with glasses”. Luo et al. (2023) use CLIP embeddings of
the labels of different classes to guide StyleGAN (Karras et al., 2019; 2020)
to generate images for the evaluation of image classifiers. Similarly, Jain et
al. (2023) use CLIP for model diagnosis. These approaches require the target
labels (e.g, gender, glasses, etc.) as inputs, but the nature of anomalies is
typically unknown. Instead, we rely on DiffStyle (Jeong et al., 2023a), which
provides training-free guidance for image generation by interpolating two
images using the reverse DDIM process (Song et al., 2021). We find that
interpolating between two normal samples will typically preserve the dominant
visual features, such as realistic textures and background, while introducing
slight manipulations that make the generated images promising candidates for
synthetic anomalies in our proposed model selection framework.

Figure 1: We propose to use a pretrained diffusion model to turn a small
dataset of normal samples into a synthetic validation set containing both real
normal samples and synthetic anomalies, described in Sec. 3.2. The synthetic
validation set is then used for model selection and validation, as described
in Sec. 3.1. Components in blue are frozen, components in green are real data,
and components in orange are our techniques.

##  3 Method

In this section, we propose to use existing diffusion-based image generation
techniques to generate synthetic anomalies and use them as a _synthetic
validation dataset_ , enabling model selection in domains where such a
validation dataset does not exist. In Sec. 3.1, we describe how synthetic
anomalies can be used for model selection. We then propose a synthetic anomaly
generation approach in Sec. 3.2. Figure 1 demonstrates the overall process
used by our method.

###  3.1 Model Selection with Synthetic Anomalies

The absence of labeled validation data is a major roadblock in the deployment
of anomaly detection methods. However, normal data can usually be obtained.
For this reason, we follow Zhao et al. (2021), and assume access to a set of
normal samples we call the support set $X_{\text{support}}$. In our empirical
study, we show that the support set can have as few as 10 normal samples.
Using this support set, we wish to construct a synthetic validation set that
can aid model selection.

Creating a synthetic validation set and using it for model selection entails
the following steps:

Step 1: Partitioning the support set. The support set $X_{\text{support}}$, is
randomly partitioned into style images $X_{\text{style}}$, content images
$X_{\text{content}}$, and normal validation images $X_{\text{in}}$.
$X_{\text{style}}$ and $X_{\text{content}}$ are used for anomaly generation,
and $X_{\text{in}}$ is held out for evaluation.

Step 2: Generating synthetic anomalies. The style and content images are
processed with DiffStyle (Jeong et al., 2023a) to produce synthetic anomalies
$\tilde{X}_{\text{out}}$. Details will be given in Sec. 3.2.

Step 3: Mixing the synthetic validation set. The normal validation images
$X_{\text{in}}$ are combined with the synthetic anomalies
$\tilde{X}_{\text{out}}$ to produce a labeled synthetic validation set,

$\displaystyle\mathcal{D}=\\{(x,1)|x\in\tilde{X}_{\text{out}}\\}\cup\\{(x,0)|x\in
X_{\text{in}}\\},$ (1)

where the label 1 indicates an anomaly and 0 a normal image.

Step 4: Evaluating detection accuracy of candidate models. In a final step,
candidate models are evaluated in terms of their detection accuracy on the
syntehtic validation set $\mathcal{D}$. Anomaly detection methods are
typically evaluated in terms of AUROC, the area under the receiving operator
characteristic curve (Emmott et al., 2015; Maxion & Tan, 2000).

Since we assume a small support set, training or fine-tuning a generative
(diffusion) model is infeasible. Instead, in Sec. 3.2, we propose to use a
DDIM (Song et al., 2021) pre-trained on ImageNet and DiffStyle, a training-
free method for diffusion-based image-to-image style transfer, and adapt it
for generating synthetic anomalies. Our method does not perform any model
training or fine-tuning and does not require any data outside of the support
set.

###  3.2 Generating Synthetic Anomalies

We use DiffStyle (Jeong et al., 2023a) to generate synthetic anomalies with a
pretrained DDIM. From style images $X_{\text{style}}$, content images
$X_{\text{content}}$, DiffStyle takes any style-context images pair as input—a
“style image” $I^{(1)}$ and a “content image” $I^{(2)}$—and produces a new,
generated image with $I^{(2)}$’s content and $I^{(1)}$’s style. To achieve
this, $I^{(1)}$ and $I^{(2)}$ are mapped into the diffusion model’s latent
space through the forward diffusion process, producing latent vectors
$x_{T}^{(1)}$ and $x_{T}^{(2)}$. We refer to the h-space (i.e., the inner-most
layer of the UNet) of $x_{T}^{(1)}$ and $x_{T}^{(2)}$ as $h^{(1)}$ and
$h^{(2)}$ respectively. The h-space has been shown to be a meaningful semantic
space in the image domain, enabling properties such as linearity and
composition between images and can be manipulated during a diffusion model’s
image generation process to achieve desired properties. We refer readers for
more details related to h-space to Kwon et al. (2023) and Jeong et al.
(2023a).

Given two latent vectors $h^{(1)}$ and $h^{(2)}$, a simple linear
interpolation is performed to style-transfer between two images:
$h^{(\text{gen})}=(1-\gamma)h^{(1)}+\gamma h^{(2)}$ where $\gamma$ represents
the relative strength of the content image during style transfer111The
original DiffStyle work implements a spherical interpolation strategy to
produce higher-quality images, but we found this was not necessary for our use
case. We use $\gamma=0.7$ as the default in our experiments. We then perform
the asymmetric reverse diffusion process using $x_{T}^{(1)}$, replacing the
h-space with $h^{(\text{gen})}$:

$\displaystyle
x_{t-1}=\sqrt{\alpha_{t-1}}\mathbf{P}_{t}(\epsilon^{\theta}_{t}(x_{T}^{(1)}|h^{(\text{gen})}))+\mathbf{D}_{t}(\epsilon^{\theta}_{t}(x_{T}^{(1)})).$
(2)

Once the reverse process is completed (i.e., at $t=0$), the final output
$x_{0}$ is saved as a synthetic anomaly. To generate the full set of synthetic
anomalies $\tilde{X}_{\text{out}}$, we apply all possibilities of
$(I^{(1)},I^{(2)})$ in the cross product of $X_{\text{style}}$ and
$X_{\text{content}}$. Figure 2 shows examples of anomalies generated with this
approach; we find that our generated images have realistic backgrounds and
textures, but can contain various semantic corruptions expected of anomalous
images. Our synthetic anomaly generation method assumes _no knowledge of the
distribution of potential anomalies_ : the general-purpose diffusion model is
not fine-tuned and only images from the support set $X_{\text{support}}$ are
used as inputs.

(a) CUB class 1

(b) MVTec-AD cable

Figure 2: Example pairwise interpolations for CUB class 1 (”Black Footed
Albatross”) (left) and MVTec-AD product ”cable” (right). For each example, the
top row of images (in green) are used as source “style” images, and the left
column of images (in cyan) are used as source “content” images. The inner grid
(in red) shows each pairwise interpolation between the source style and
content image, performed with our modified DiffStyle process. All source
images are drawn from the distribution of class 1 support images; no
validation data or images from other classes are used.

##  4 Empirical Study

To study the efficacy of synthetic anomalies for model selection, we develop
an anomaly detection validation benchmark and investigate whether our
synthetic validation delivers similar results to ground-truth validation sets.
Our evaluation spans various vision domains, including natural and industrial
images. In evaluating our method, we find that our method selects the true
best-performing model in five of six cases (Sec. 4.2) and outperforms all
other strategies for CLIP prompt selection (Sec. 4.3); these results are
achieved without any access to the real validation data. We first describe the
datasets, anomaly detection tasks, and anomaly generation details in Sec. 4.1.
Next, we showcase two use cases of synthetic data in anomaly detection
validation–model selection and CLIP prompt selection–separately in Sec. 4.2
and Sec. 4.3.

###  4.1 Experimental Setup

We present an experimental setup that can be used as a benchmark to evaluate
synthetic validation data. The goal of this benchmark is to be able to
evaluate, how well the results on the synthetic validation data correspond to
results one would obtain with ground-truth validation data. Our benchmark
contains anomaly detectors of varying strength and a battery of anomaly
detection tasks. The tasks vary by difficulty from the easier one-vs-rest to
the more difficult one-vs-one anomaly detection setting and span three
different vision domains. Quantities of interest include predictions of the
absolute detection performance based on the validation sets, the relative
ranking of the detection methods based on the validation sets, and the hyper-
parameters (such as prompts for CLIP-based anomaly detection) that are
selected based on the validation sets.

#### Datasets.

Our benchmark spans three frequently-used image datasets: MVTec Anomaly
Detection dataset (MVTec-AD) (Bergmann et al., 2019), Caltech-UCSD Birds (CUB)
(Wah et al., 2011), and Flowers (Nilsback & Zisserman, 2008). MVTec-AD
contains 15 real industrial product categories; for each category, the
training subset contains images of defect-free products, and the testing
subset contains labeled images of both good and defective products. CUB and
Flowers are multi-class datasets containing 200 bird species and 102 flower
species respectively.

#### Anomaly detection tasks.

Our benchmark contains 317 anomaly detection tasks: 15 from MVTec-AD, 200 from
CUB, and 102 from Flowers, where each class or category is iteratively treated
as normal. Besides considering the usual one-vs-rest anomaly detection setup
for multi-class datasets CUB and Flowers, we also adopt the one-vs-one setup
used in Mirzaei et al. (2023) to simulate more difficult anomaly detection
tasks. Specifically, we individually select each class as the inlier class and
treat all other images as anomalies—both when considering each out-class
individually (one-vs-one) and when considering all out-classes as a single
class (one-vs-rest). For MVTec-AD, we predict images of defective products
from good products for each product; each product contains multiple defect
types, which can be used as different out-classes for one-vs-one measurements
or represented as a single class for one-vs-rest. For all tasks, images from
the in-class training subset are used as the support set, and images from the
relevant in-class and out-class testing subsets are used for constructing the
ground-truth validation set. In summary, for each task, we report three
variants of their resulting AUROC:

  * •

One-Vs-Rest: the AUROC when considering all other classes as a single anomaly
class

  * •

One-Vs-One Average: the average AUROC when considering each out-class
individually

  * •

One-Vs-One Closest: the worst AUROC when considering each out-class
individually

#### Generating synthetic anomalies.

For all three datasets and all 317 anomaly detection tasks, we generate
synthetic anomalies with training examples from the in-class distribution
only. For the CUB and MVTec-AD datasets, we sample 10 images for
$X_{\text{style}}$ and 10 images for $X_{\text{content}}$ images from the
training set, generating 100 synthetic anomalies. For the Flowers dataset,
only 10 images are included in the training set for each class, so we generate
25 synthetic anomalies, using five images for $X_{\text{style}}$ and five
images for $X_{\text{content}}$. Figure 2 shows 15 examples of generated
synthetic anomalies for a single CUB class (left) and a single MYTec-AD
product (right).

Although prior results in Kwon et al. (2023) and Kim et al. (2022) suggest
that using a diffusion model trained on the same dataset is required to
generate high-quality images, we find that using a single, common diffusion
model is sufficient to generate synthetic anomalies. We use the same pre-
trained model (the 256x256 diffusion model trained on ImageNet without class
conditioning from Dhariwal & Nichol (2021)) for all datasets and anomaly
detection tasks.

###  4.2 Model Selection on Synthetic Data

(a) CUB: One-vs-one Closest

(b) Flowers: One-vs-one Closest

(c) CUB: One-vs-one Average

(d) Flowers: One-vs-one Average

(e) CUB: One-vs-rest

(f) Flowers: One-vs-rest

Figure 3: Comparing the real validation AUROC against the AUROC with our
synthetic validation set, for the CUB (left) and Flowers (right) datasets and
for all three benchmarks: one-vs-one closest (top), one-vs-one average
(middle), and one-vs-rest (bottom). When comparing model rankings with real
validation AUROC and model rankings based on synthetic AUROC, we find that our
synthetic anomalies are effective estimates for the one-vs-one average and
one-vs-rest benchmarks. In these four cases, the best-performing model is the
same whether real or synthetic validation data is used.

We first demonstrate the effectiveness of our synthetic validation framework
for model selection. Given a set of candidate models, we show that one can
select the suitable anomaly detection model with the help of our synthetic
anomalies generated with DiffStyle.222We compare with using Tiny-ImageNet as
synthetic anomalies for model selection in Appendix A.1. We found that Tiny-
ImageNet images do not serve as effective anomalies for model selection.

#### Candidate anomaly detection models.

We experiment across five pre-trained ResNet models (ResNet-152, ResNet-101,
ResNet-50, ResNet-34, ResNet-18) and five pre-trained Vision Transformers
(ViT-H-14, ViT-L-32, ViT-L-16, ViT-B-32, ViT-B-16). We use the ImageNet pre-
trained model weights of Dosovitskiy et al. (2021); He et al. (2016). To
perform anomaly detection, we follow the methodology of Mirzaei et al. (2023).
First, a small set of examples are used to establish a feature bank. Then, to
perform detection, each input example is compared to the feature bank: the
total Euclidean distance to the 3-nearest neighbors is used as an anomaly
score.

#### Evaluation setup.

For each task, we vary the number of synthetic anomalies used in the synthetic
validation set—from the full set of 100 synthetic anomalies to as few as three
synthetic anomalies. When reducing the number of synthetic anomalies, we
always eliminate the easiest anomalies with the highest anomaly score at
inference time until the desired number of synthetic anomalies remains. We
compute the AUROC for each task and candidate model. For each dataset, the
AUROCs from each task are averaged to be the overall “synthetic AUROC”. We
then repeat this protocol with the real validation dataset, again averaging
over anomaly detection tasks to compute the “real AUROC”. We finally compare
the real and synthetic AUROCs to investigate if the candidate model rankings
produced by these benchmarks are similar.

#### Evaluation results.

Figure 3 shows the results for the CUB (left) and Flowers (right) datasets. An
ideal method would produce model rankings with synthetic data (along the
y-axis) that closely match the rankings of models with real data (along the
x-axis). As expected, we find that our synthetic validation best approximate
the one-vs-one average and one-vs-rest benchmarks, as they are more robust to
variations between classes. Figures 3(c)–3(f) show that the rankings of models
are consistent: the best-performing model is the same whether real or
synthetic validation data is used, and relative rankings of models are
similar. We find that the one-vs-one closest benchmark, an approximation of
worst-case performance, is more difficult to estimate with synthetic
anomalies. Figures 3(a) and 3(b) show that, although the real and synthetic
AUROCs are relatively aligned for the Flowers dataset, the performance is less
consistent for CUB.

When performing model selection on the MVTec-AD dataset, we found that our
results were noisy at approximating the real AUROC and selecting the true best
models. The results for this experiment are shown in Appendix A.1 and Figure
5. Since our method relies on ImageNet-trained artifacts (the ViT and ResNet
models, CLIP, and our pre-trained diffusion models were all trained with
ImageNet) we expect model selection to improve with foundation models that are
more representative of the close-up images of industrial products found in the
MVTec-AD dataset. However, as shown in the next section, our synthetic
validation is still extremely effective for selecting CLIP prompts for all
datasets, including MVTec-AD.

###  4.3 CLIP Prompt Selection on Synthetic Data

Table 1: Synthetic outliers can effectively select CLIP prompts in the absence of real validation data. We compare five methods for selecting CLIP prompts: (i) our method (described in Sec. 4.3), (ii) a random choice of candidate prompt, (iii) always choosing the default prompt, (iv) our method with Tiny-ImageNet as the synthetic anomalies, and (iv) the single, global best candidate prompt an oracle would provide (grayed out as this cannot be obtained in practice). For each method, we record the tasks where the selected prompt matches the best task-specific prompt, reporting the accuracy and raw count (in parentheses) for the one-vs-one closest and one-vs-one average benchmarks. Across three datasets and two benchmarks, our method outperforms all other strategies, and even outperforms the global best prompt in three out of six cases. |  |  Flowers (102 tasks) |  CUB (200 tasks) |  MVTec-AD (15 tasks)
---|---|---|---|---
One-Vs-One Closest | Random Choice | 10.0% |  | 10.0% |  | 10.0% |
Default Prompt | 0.0% | (1) | 2.5% | (5) | 6.7% | (1)
Tiny-ImageNet Choice | 17.6% | (18) | 17.0% | (34) | 6.7% | (1)
Global Best Prompt (Oracle) | 41.2% | (42) | 18.5% | (37) | 26.7% | (4)
Our Method | 37.2% | (38) | 23.0% | (46) | 40.0% | (6)
One-Vs-One Average | Random Choice | 10.0% |  | 10.0% |  | 10.0% |
Default Prompt | 0.0% | (1) | 0.0% | (0) | 6.7% | (1)
Tiny-ImageNet Choice | 17.6% | (18) | 13.5% | (27) | 6.7% | (1)
Global Best Prompt (Oracle) | 44.1% | (45) | 32.5% | (65) | 40.0% | (6)
Our Method | 40.2% | (41) | 32.0% | (64) | 46.7% | (7)
Table 2: Using our synthetic outliers to select CLIP prompts always results in the best average AUROC, even in the absence of real validation data. We compare our method for selecting CLIP prompts (described in Sec. 4.3) to the default prompt, the prompt choice made with Tiny-ImageNet, the average of prompts, the hypothetical worst-case (always picking the worst prompt), and the hypothetical best-case (always picking the best prompt). Oracle results are grayed out since they cannot be obtained in practice, but we include them for reference.  |  |  Flowers (102 tasks) |  CUB (200 tasks) |  MVTec-AD (15 tasks)
---|---|---|---|---
One-Vs-One Closest | Default Prompt | 0.697 | 0.570 | 0.436
Tiny-ImageNet Choice | 0.718 | 0.582 | 0.438
Average of Prompts | 0.708 | 0.577 | 0.441
Worst Prompt (Oracle) | 0.658 | 0.527 | 0.367
Best Prompt (Oracle) | 0.759 | 0.626 | 0.511
Our Method | 0.729 | 0.590 | 0.463
One-Vs-One Average | Default Prompt | 0.954 | 0.970 | 0.585
Tiny-ImageNet Choice | 0.964 | 0.971 | 0.592
Average of Prompts | 0.957 | 0.971 | 0.582
Worst Prompt (Oracle) | 0.948 | 0.964 | 0.522
Best Prompt (Oracle) | 0.968 | 0.976 | 0.646
Our Method | 0.964 | 0.973 | 0.598

Zero-shot anomaly detection methods (Jeong et al., 2023b; Liznerski et al.,
2022) save the effort on collecting training samples. However, the performance
of CLIP-based anomaly detection models depend on the choice of prompts. Prior
works evaluate across a variety of candidate CLIP prompts for zero-shot image
anomaly detection on real labeled validation data. Validation data might be
also absent in the zero-shot setting. Next, we evaluate the efficacy of our
generated synthetic anomalies for selecting CLIP prompts on our 317 anomaly
detection benchmark tasks.

#### Zero-shot anomaly detection with CLIP.

We perform zero-shot image anomaly detection with CLIP (with the ViT-B/16
backbone) as suggested by Liznerski et al. (2022); Jeong et al. (2023b): given
an input, we submit two text prompts and predict the class with the higher
similarity. We assume that the name of the inlier class is known, and use
“some” or “something” for anomalous classes. For example, for the CUB dataset,
if “red cardinal” is the name of the inlier class, we compare the CLIP
similarities of “a photo of a red cardinal” to “a photo of some bird”. We
select amongst a pool of prompt templates from Jeong et al. (2023b) for our
anomaly detection tasks. A full list of candidate prompts used for each
dataset can be found in Appendix A.4.

#### Evaluation setup.

We consider a set of ten candidate prompt templates shown in Appendix A.4. We
evaluate each candidate prompt for the one-vs-one closest and one-vs-one
average task variants of the 317 anomaly detection tasks and select the prompt
with the best AUROC computed on three validation sets: our proposed synthetic
validation set, an alternative validation set with anomalies sampled from
Tiny-ImageNet, and the ground-truth validation dataset. We measure how often
each strategy’s selected prompt matches the prompt selected with real
validation data. For comparison, we also include two baseline strategies:
Random Choice that randomly selects a candidate prompt and Default Prompt that
always selects the default prompt template (e.g., “a photo of a [class name]
bird” vs “a photo of some bird”). For reference, as an oracle result, we also
report how often a global best prompt matches the task-specific best prompts.

#### Evaluation results.

We report the prompt selection accuracy in Table 1 for all three datasets. We
also report the averaged AUROCs for different prompt-selection strategies in
Table 2. In Table 1, compared to all baselines, our method performs best for
all tasks and improves prompt selection accuracy by 6% to 40%. This suggests
that our generated synthetic anomalies are helpful in selecting the best
prompts for tuning CLIP-based anomaly detectors on various tasks. Furthermore,
our method outperforms the single-best-prompt strategy on in three out of six
settings (two task variants in three datasets shown in Table 1). In these
cases, the prompt selection accuracy difference ranges from -4% to +16%. We
emphasize that selecting the single best-performing prompt relies on access to
the real validation data, whereas our method only uses synthetic anomalies
generated from in-class training sources.

As shown in Table 2, by selecting better prompts with our generated synthetic
anomalies, we improve the zero-shot anomaly detection results in the
challenging one-vs-one closest setting over the popular default choice of
prompt, i.e., “a photo of a [class name]” by 3.4% on Flowers, 2% on CUB, and
2.7% on MVTec-AD. Our proposed prompt selection also provides a consistent
performance improvement over the averaged results of various prompts and the
results of prompts selected with Tiny-ImageNet, showcasing the general
effectiveness of our method.

##  5 Conclusion

In this work, we investigate an approach for anomaly detection model selection
and validation _without any validation data_. To substitute for a validation
dataset, we propose that a general-purpose diffusion model can be used
generate synthetic outliers, using only a small support set of in-class
examples as input. Unlike prior methods for synthetic anomaly generation, we
do not rely on any model training, fine-tuning, or any domain-specific
architectures or techniques. Our empirical study shows that synthetic
validation datasets constructed with this approach can be used effectively in
two ways: for selecting amongst a set of candidate anomaly detection models,
and for selecting hyper-parameters for zero-shot anomaly detection models,
specifically CLIP prompt templates.

## References

  * Ahmed et al. (2016) Mohiuddin Ahmed, Abdun Naser Mahmood, and Md. Rafiqul Islam.  A survey of anomaly detection techniques in financial domain.  _Future Generation Computer Systems_ , 55(C):278–288, 2016.
  * Bergman & Hoshen (2020) Liron Bergman and Yedid Hoshen.  Classification-based anomaly detection for general data.  In _International Conference on Learning Representations_ , 2020.
  * Bergmann et al. (2019) Paul Bergmann, Michael Fauser, David Sattlegger, and Carsten Steger.  MVTec AD — a comprehensive real-world dataset for unsupervised anomaly detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 9584–9592, 2019.
  * Campos et al. (2016) Guilherme O Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, and Michael E Houle.  On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study.  _Data mining and knowledge discovery_ , 30:891–927, 2016\.
  * Chen & Konukoglu (2018) Xiaoran Chen and Ender Konukoglu.  Unsupervised detection of lesions in brain mri using constrained adversarial auto-encoders.  In _MIDL Conference book_. MIDL, 2018.
  * Das et al. (2016) Shubhomoy Das, Weng-Keen Wong, Thomas Dietterich, Alan Fern, and Andrew Emmott.  Incorporating expert feedback into active anomaly discovery.  In _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pp. 853–858. IEEE, 2016.
  * Deecke et al. (2021) Lucas Deecke, Lukas Ruff, Robert A Vandermeulen, and Hakan Bilen.  Transfer-based semantic anomaly detection.  In _International Conference on Machine Learning_ , pp. 2546–2558. PMLR, 2021.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  ImageNet: A large-scale hierarchical image database.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 248–255, 2009.
  * Dhariwal & Nichol (2021) Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat GANs on image synthesis.  _Advances in neural information processing systems_ , 34:8780–8794, 2021.
  * Ding et al. (2022) Xueying Ding, Lingxiao Zhao, and Leman Akoglu.  Hyperparameter sensitivity in deep outlier detection: Analysis and a scalable hyper-ensemble solution.  _Advances in Neural Information Processing Systems_ , 35:9603–9616, 2022.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.
  * Emmott et al. (2015) Andrew Emmott, Shubhomoy Das, Thomas Dietterich, Alan Fern, and Weng-Keen Wong.  A meta-analysis of the anomaly detection problem.  _arXiv preprint arXiv:1503.01158_ , 2015.
  * Esmaeilpour et al. (2022) Sepideh Esmaeilpour, Bing Liu, Eric Robertson, and Lei Shu.  Zero-shot out-of-distribution detection based on the pretrained model CLIP.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2022.
  * Fernando et al. (2021) Tharindu Fernando, Harshala Gammulle, Simon Denman, Sridha Sridharan, and Clinton Fookes.  Deep learning for medical anomaly detection–a survey.  _ACM Computing Surveys_ , 54(7):1–37, 2021.
  * Fort et al. (2021) Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan.  Exploring the limits of out-of-distribution detection.  _Advances in Neural Information Processing Systems_ , 34:7068–7081, 2021.
  * Goldstein & Uchida (2016) Markus Goldstein and Seiichi Uchida.  A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data.  _PloS one_ , 11(4):e0152173, 2016.
  * Görnitz et al. (2013) Nico Görnitz, Marius Kloft, Konrad Rieck, and Ulf Brefeld.  Toward supervised anomaly detection.  _Journal of Artificial Intelligence Research_ , 46:235–262, 2013.
  * Han et al. (2022) Songqiao Han, Xiyang Hu, Hailiang Huang, Minqi Jiang, and Yue Zhao.  Adbench: Anomaly detection benchmark.  _Advances in Neural Information Processing Systems_ , 35:32142–32159, 2022.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , pp. 770–778, 2016.
  * Hendrycks et al. (2019a) Dan Hendrycks, Mantas Mazeika, and Thomas Dietterich.  Deep anomaly detection with outlier exposure.  In _International Conference on Learning Representations_ , 2019a.
  * Hendrycks et al. (2019b) Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song.  Using self-supervised learning can improve model robustness and uncertainty.  _Advances in Neural Information Processing Systems_ , 32:15663–15674, 2019b.
  * Ho et al. (2020) Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems_ , 33:6840–6851, 2020.
  * Jain et al. (2023) Saachi Jain, Hannah Lawrence, Ankur Moitra, and Aleksander Madry.  Distilling model failures as directions in latent space.  In _International Conference on Learning Representations_ , 2023.
  * Jeong et al. (2023a) Jaeseok Jeong, Mingi Kwon, and Youngjung Uh.  Training-free style transfer emerges from h-space in diffusion models.  _arXiv preprint arXiv:2303.15403_ , 2023a.
  * Jeong et al. (2023b) Jongheon Jeong, Yang Zou, Taewan Kim, Dongqing Zhang, Avinash Ravichandran, and Onkar Dabeer.  WinCLIP: Zero-/few-shot anomaly classification and segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 19606–19616, 2023b.
  * Karras et al. (2019) Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 4401–4410, 2019.
  * Karras et al. (2020) Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of StyleGAN.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 8110–8119, 2020.
  * Kawar et al. (2023) Bahjat Kawar, Shiran Zada, Oran Lang, Omer Tov, Huiwen Chang, Tali Dekel, Inbar Mosseri, and Michal Irani.  Imagic: Text-based real image editing with diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 6007–6017, 2023.
  * Kim et al. (2022) Gwanghyun Kim, Taesung Kwon, and Jong Chul Ye.  DiffusionCLIP: Text-guided diffusion models for robust image manipulation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2426–2435, 2022.
  * Kwon et al. (2023) Mingi Kwon, Jaeseok Jeong, and Youngjung Uh.  Diffusion models already have a semantic latent space.  In _International Conference on Learning Representations_ , 2023.
  * Lai et al. (2021) Kwei-Herng Lai, Daochen Zha, Junjie Xu, Yue Zhao, Guanchu Wang, and Xia Hu.  Revisiting time series outlier detection: Definitions and benchmarks.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1)_ , 2021.
  * Li et al. (2023a) Aodong Li, Chen Qiu, Marius Kloft, Padhraic Smyth, Stephan Mandt, and Maja Rudolph.  Deep anomaly detection under labeling budget constraints.  In _International Conference on Machine Learning_ , pp. 19882–19910. PMLR, 2023a.
  * Li et al. (2023b) Aodong Li, Chen Qiu, Marius Kloft, Padhraic Smyth, Maja Rudolph, and Stephan Mandt.  Zero-shot anomaly detection without foundation models.  _arXiv preprint arXiv:2302.07849_ , 2023b.
  * Li et al. (2021) Chun-Liang Li, Kihyuk Sohn, Jinsung Yoon, and Tomas Pfister.  Cutpaste: Self-supervised learning for anomaly detection and localization.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 9664–9674, 2021.
  * Liznerski et al. (2022) Philipp Liznerski, Lukas Ruff, Robert A Vandermeulen, Billy Joe Franks, Klaus Robert Muller, and Marius Kloft.  Exposing outlier exposure: What can be learned from few, one, and zero outlier images.  _Transactions on Machine Learning Research_ , 2022.
  * Luo et al. (2023) Jinqi Luo, Zhaoning Wang, Chen Henry Wu, Dong Huang, and Fernando De la Torre.  Zero-shot model diagnosis.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 11631–11640, 2023.
  * Ma et al. (2023) Martin Q Ma, Yue Zhao, Xiaorong Zhang, and Leman Akoglu.  The need for unsupervised outlier model selection: A review and evaluation of internal evaluation strategies.  _ACM SIGKDD Explorations Newsletter_ , 25(1), 2023.
  * Marques et al. (2015) Henrique O Marques, Ricardo JGB Campello, Arthur Zimek, and Jörg Sander.  On the internal evaluation of unsupervised outlier detection.  In _Proceedings of the 27th international conference on scientific and statistical database management_ , pp. 1–12, 2015.
  * Marques et al. (2020) Henrique O Marques, Ricardo JGB Campello, Jörg Sander, and Arthur Zimek.  Internal evaluation of unsupervised outlier detection.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 14(4):1–42, 2020.
  * Maxion & Tan (2000) R.A. Maxion and K.M.C. Tan.  Benchmarking anomaly-based detection systems.  In _International Conference on Dependable Systems and Networks_ , pp. 623–630, 2000.
  * Mirsky et al. (2018) Yisroel Mirsky, Tomer Doitshman, Yuval Elovici, and Asaf Shabtai.  Kitsune: an ensemble of autoencoders for online network intrusion detection.  In _Network and Distributed System Security Symposium_ , 2018.
  * Mirzaei et al. (2023) Hossein Mirzaei, Mohammadreza Salehi, Sajjad Shahabi, Efstratios Gavves, Cees G. M. Snoek, Mohammad Sabokrou, and Mohammad Hossein Rohban.  Fake it until you make it: Towards accurate near-distribution novelty detection.  In _International Conference on Learning Representations_ , 2023.
  * Mokady et al. (2023) Ron Mokady, Amir Hertz, Kfir Aberman, Yael Pritch, and Daniel Cohen-Or.  Null-text inversion for editing real images using guided diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 6038–6047, 2023.
  * Nguyen et al. (2016) Thanh Trung Nguyen, Uy Quang Nguyen, et al.  An evaluation method for unsupervised anomaly detection algorithms.  _Journal of Computer Science and Cybernetics_ , 32(3):259–272, 2016.
  * Nilsback & Zisserman (2008) Maria-Elena Nilsback and Andrew Zisserman.  Automated flower classification over a large number of classes.  In _Indian Conference on Computer Vision, Graphics and Image Processing_ , 2008.
  * Principi et al. (2017) Emanuele Principi, Fabio Vesperini, Stefano Squartini, and Francesco Piazza.  Acoustic novelty detection with adversarial autoencoders.  In _2017 International Joint Conference on Neural Networks (IJCNN)_ , pp. 3324–3330. IEEE, 2017.
  * Qiu et al. (2021) Chen Qiu, Timo Pfrommer, Marius Kloft, Stephan Mandt, and Maja Rudolph.  Neural transformation learning for deep anomaly detection beyond images.  In _International Conference on Machine Learning_ , pp. 8703–8714. PMLR, 2021.
  * Qiu et al. (2022a) Chen Qiu, Marius Kloft, Stephan Mandt, and Maja Rudolph.  Raising the bar in graph-level anomaly detection.  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_ , pp. 2196–2203, 2022a.
  * Qiu et al. (2022b) Chen Qiu, Aodong Li, Marius Kloft, Maja Rudolph, and Stephan Mandt.  Latent outlier exposure for anomaly detection with contaminated data.  In _International Conference on Machine Learning_ , pp. 18153–18167. PMLR, 2022b.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pp. 8748–8763, 2021.
  * Reiss et al. (2021) Tal Reiss, Niv Cohen, Liron Bergman, and Yedid Hoshen.  Panda: Adapting pretrained features for anomaly detection and segmentation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 2806–2814, 2021.
  * Ruff et al. (2018) Lukas Ruff, Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emmanuel Müller, and Marius Kloft.  Deep one-class classification.  In _International conference on machine learning_ , pp. 4393–4402. PMLR, 2018.
  * Ruff et al. (2019) Lukas Ruff, Robert A Vandermeulen, Nico Görnitz, Alexander Binder, Emmanuel Müller, Klaus-Robert Müller, and Marius Kloft.  Deep semi-supervised anomaly detection.  In _International Conference on Learning Representations_ , 2019.
  * Schneider et al. (2022) Tim Schneider, Chen Qiu, Marius Kloft, Decky Aspandi Latif, Steffen Staab, Stephan Mandt, and Maja Rudolph.  Detecting anomalies within time series using local neural transformations.  _arXiv preprint arXiv:2202.03944_ , 2022.
  * Schubert et al. (2023) David Schubert, Pritha Gupta, and Marcel Wever.  Meta-learning for automated selection of anomaly detectors for semi-supervised datasets.  In _International Symposium on Intelligent Data Analysis_ , pp. 392–405. Springer, 2023.
  * Siadati & Memon (2017) Hossein Siadati and Nasir Memon.  Detecting structurally anomalous logins within enterprise networks.  In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 1273–1284, 2017.
  * Sohn et al. (2020) Kihyuk Sohn, Chun-Liang Li, Jinsung Yoon, Minho Jin, and Tomas Pfister.  Learning and evaluating representations for deep one-class classification.  In _International Conference on Learning Representations_ , 2020.
  * Song et al. (2021) Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  In _International Conference on Learning Representations_ , 2021.
  * Trittenbach et al. (2021) Holger Trittenbach, Adrian Englhardt, and Klemens Böhm.  An overview and a benchmark of active learning for outlier detection with one-class classifiers.  _Expert Systems with Applications_ , 168:114372, 2021.
  * Tumanyan et al. (2023) Narek Tumanyan, Michal Geyer, Shai Bagon, and Tali Dekel.  Plug-and-play diffusion features for text-driven image-to-image translation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 1921–1930, 2023.
  * Wagner et al. (2023) Dennis Wagner, Tobias Michels, Florian C.F. Schulz, Arjun Nair, Maja Rudolph, and Marius Kloft.  TimeseAD: Benchmarking deep multivariate time-series anomaly detection.  _Transactions on Machine Learning Research_ , 2023.  ISSN 2835-8856.
  * Wah et al. (2011) C. Wah, S. Branson, P. Welinder, P. Perona, and S. Belongie.  The Caltech-UCSD Birds-200-2011 Dataset.  Technical Report CNS-TR-2011-001, California Institute of Technology, 2011\.
  * Wu & Keogh (2020) Renjie Wu and Eamonn J Keogh.  Current time series anomaly detection benchmarks are flawed and are creating the illusion of progress.  _arXiv preprint arXiv:2009.13807_ , 2020.
  * Zhao et al. (2021) Yue Zhao, Ryan Rossi, and Leman Akoglu.  Automatic unsupervised outlier model selection.  _Advances in Neural Information Processing Systems_ , 34:4489–4502, 2021.
  * Zhao et al. (2022) Yue Zhao, Sean Zhang, and Leman Akoglu.  Toward unsupervised outlier model selection.  In _2022 IEEE International Conference on Data Mining (ICDM)_ , pp. 773–782. IEEE, 2022.
  * Zhou et al. (2021) Chong Zhou, Chen Change Loy, and Bo Dai.  DenseCLIP: Extract free dense labels from CLIP.  _arXiv preprint arXiv:2112.01071_ , 2021.

##  Appendix A Appendix

###  A.1 Additional Results

(a) CUB: One-vs-one Closest

(b) Flowers: One-vs-one Closest

(c) CUB: One-vs-one Average

(d) Flowers: One-vs-one Average

(e) CUB: One-vs-rest

(f) Flowers: One-vs-rest

Figure 4: We compare the real validation AUROC against the AUROC when Tiny-
Imagenet is used as synthetic anomalies, for the CUB (left) and Flowers
(right) datasets and for all three benchmarks. We find that the performance is
poor: model selection cannot be reliably performed when Tiny-ImageNet examples
as used as synthetic anomalies.

(a) One-vs-One Average

(b) One-vs-Rest

Figure 5: Comparing the real validation AUROC against the synthetic validation
AUROC for the MVTec-AD dataset. For all the one-vs-one average and the one-vs-
rest benchmark, using our synthetic validation dataset is ineffective for
selecting the true, best anomaly detection models.

#### Model selection with Tiny-ImageNet.

Our initial experiments investigated if Tiny-ImageNet could be used
effectively as synthetic anomalies when constructing the synthetic validation
set. For these experiments, the same support set for each anomaly detection
task is the same as the support for the corresponding experiment with our
generated anomalies. When sampling anomalies from Tiny-Imagenet, we sample
uniformly at random to generate a dataset $\tilde{X}_{\text{out}}$ of the same
size: 100 images for tasks with the CUB and MVTec-AD datasets, and 25 images
for tasks with the Flowers dataset. Ultimately, we found that using Tiny-
ImageNet examples were not effective for our chosen tasks; in addition to the
results for CLIP prompt selection in Table 1, the results for model selection
are shown in Figure 4.

#### Additional MVTec-AD results.

Figure 5 shows the results of the model selection experiment with the MVTec-AD
dataset on the one-vs-one average and the one-vs-rest benchmarks (which were
shown to be easier benchmarks to estimate in Figure 3). Unlike the CUB and
Flowers datasets, in which synthetic anomalies could successfully approximate
real validation performance, our synthetic anomalies are less effective for
MVTec-AD.

We also comment on the performance of our method when selecting CLIP prompts
for MVTec-AD. We noticed a disparity in performance between objects in MVTec-
AD (e.g., capsules, cables, or screws) and textures in MVTec-AD (e.g.,
carpets, wood, or tiles). Our method is unable to select the best CLIP prompt
in any of the six textures for MVTec-AD, instead only performing well on the
nine MVTec-AD objects. We therefore identify yet another challenge when using
our approach for MVTec-AD— DiffStyle relies on assumptions of “style” and
“content” in their source images, and these elements are not present in MVTec-
AD textures like carpets or tiles.

###  A.2 Generating Synthetic Outliers with Text-guidance

A directional CLIP loss is defined using CLIP’s image encoder $E_{I}$, CLIP’s
text encoder $E_{T}$, and source-target image and text pairs
($x_{source},x_{target}$) and ($y_{source},y_{target}$) respectively,
StyleGAN-NADA enables text-guided generation of images:

$\displaystyle\centering\Delta T\@add@centering$
$\displaystyle=E_{T}(y_{target})-E_{T}(y_{source})$ $\displaystyle\Delta I$
$\displaystyle=E_{I}(x_{target})-E_{I}(x_{source})$ $\displaystyle L_{dir}$
$\displaystyle=1-\frac{\Delta I\cdot\Delta T}{||\Delta I||||\Delta T||}$

We use the Asyrp process (Kwon et al., 2023) for text-guided anomaly
generation, but modify Asyrp in two ways: (i) using non-domain-specific text-
guidance and (ii) defining the edit-strength of each anomaly. The original
Asyrp process is evaluated on well-defined domains, and assumes that the
source and target text are known (e.g, modifying “face” to “smiling face”). We
instead propose a methox that does not assume a specific domain and does not
require domain-specific texts as input.

First, we find that using a source text is unneeded, and a meaningful
direction for $\Delta T$ can be extracted by using the image encoder $E_{I}$
and the source image $x_{source}$. Second, we find that target texts can be
replaced with auxiliary, out-of-domain texts, which we call $y_{aux}$. We make
these two changes to redefine our directional loss $L_{dir}^{\prime}$.

$\displaystyle\centering\Delta T^{\prime}\@add@centering$
$\displaystyle=E_{T}(y_{aux})-E_{I}(x_{source})$ $\displaystyle\Delta I$
$\displaystyle=E_{I}(x_{target})-E_{I}(x_{source})$ $\displaystyle
L_{dir}^{\prime}$ $\displaystyle=1-\frac{\Delta I\cdot\Delta
T^{\prime}}{||\Delta I||||\Delta T^{\prime}||}$

We follow the training procedure for h-space extractor defined in Kwon et al.
(2023) to extract $\Delta h$, the direction in h-space that creates the
desired change. We then apply Asyrp during the reverse diffusion process, but
use the linear property of h-space and define an edit strength $\alpha$, which
indicates how strongly we modify the image. Referring to the formulation
defined in Sec. 3.2, we modify the reverse DDIM process on the latent vector
$x_{T}^{(1)}$ by adding our h-space term:

$\displaystyle
x_{t-1}=\sqrt{\alpha_{t-1}}\mathbf{P}_{t}(\epsilon^{\theta}_{t}(x_{T}^{(1)}|h^{(1)}+\alpha\Delta
h))+\mathbf{D}_{t}(\epsilon^{\theta}_{t}(x_{T}^{(1)})).$ (3)

###  A.3 Using Synthetic Outliers for Outlier Exposure

In addition to using synthetic outliers for validation, synthetic outliers can
also be used for improving the performance of anomaly detection models through
outlier exposure. Our methodology closely follows that of Fort et al. (2021);
Mirzaei et al. (2023): we use a pre-trained vision transformer model, fine-
tune the vision transformer on a surrogate classification task, and use
distances in the trained embedding space as an anomaly detection.

Mirzaei et al. (2023) use a surrogate classification task for fine-tuning—a
binary classification layer is added to the vision transformer, and the model
is trained on benign in-class examples and synthetic outlier examples. In
addition to the surrogate classification task, we also propose a regression-
based task. We generate a variety of synthetic outliers with text-guidance,
using varying edit strength $\alpha$. When fine-tuning anomaly-detection
models, the surrogate task is a regression that predicts $\alpha$.

After fine-tuning, we remove the prediction head of the vision transformer.
The support set is then converted into the transformer’s embedding space
(i.e., the last layer before the prediction layer) and used as a feature bank
for anomaly detection. At test time, the total Euclidean distance to the
closest three examples in the feature bank is used as the anomaly score.

###  A.4 CLIP prompt templates

For our experiments in Sec. 4.3, we evaluated across set of ten candidate
prompt templates. Our evaluated prompts are general-purpose, and only the term
“bird” or “flower” is added to the template for the CUB and Flowers dataset
respectively. For each dataset, the candidate prompt templates are provided
below:

    % CLIP Templates for Flowers
    [’a photo of a {} flower’, ’a photo of some flower’],
    [’a cropped photo of a {} flower’, ’a cropped photo of some flower’],
    [’a dark photo of a {} flower’, ’a dark photo of some flower’],
    [’a photo of a {} flower for inspection’, ’a photo of some flower for inspection’],
    [’a photo of a {} flower for viewing’, ’a photo of some flower for viewing’],
    [’a bright photo of a {} flower’, ’a bright photo of some flower’],
    [’a close-up photo of a {} flower’, ’a close-up photo of some flower’],
    [’a blurry photo of a {} flower’, ’a blurry photo of some flower’],
    [’a photo of a small {} flower’, ’a photo of a small some flower’],
    [’a photo of a large {} flower’, ’a photo of a large some flower’],

    % CLIP Templates for CUB
    [’a photo of a {} bird’, ’a photo of some bird’],
    [’a cropped photo of a {} bird’, ’a cropped photo of some bird’],
    [’a dark photo of a {} bird’, ’a dark photo of some bird’],
    [’a photo of a {} bird for inspection’, ’a photo of some bird for inspection’],
    [’a photo of a {} bird for viewing’, ’a photo of some bird for viewing’],
    [’a bright photo of a {} bird’, ’a bright photo of some bird’],
    [’a close-up photo of a {} bird’, ’a close-up photo of some bird’],
    [’a blurry photo of a {} bird’, ’a blurry photo of some bird’],
    [’a photo of a small {} bird’, ’a photo of a small some bird’],
    [’a photo of a large {} bird’, ’a photo of a large some bird’],

    % CLIP Templates for MVTec
    [’a photo of a {}’, ’a photo of something’],
    [’a cropped photo of a {}’, ’a cropped photo of something’],
    [’a dark photo of a {}’, ’a dark photo of something’],
    [’a photo of a {} for inspection’, ’a photo of something for inspection’],
    [’a photo of a {} for viewing’, ’a photo of something for viewing’],
    [’a bright photo of a {}’, ’a bright photo of something’],
    [’a close-up photo of a {}’, ’a close-up photo of something’],
    [’a blurry photo of a {}’, ’a blurry photo of something’],
    [’a photo of a small {}’, ’a photo of a small something’],
    [’a photo of a large {}’, ’a photo of a large something’],


exponentially to zero as $d_{T_{3}}(u,v)\to\infty$. Note that due to this
decay of covariances together with Theorem 6.3 we may, and do choose the
process $(X^{(n)}_{v})_{v\in V(G_{n})}$ to be of the form

$X^{(n)}_{v}=\sum_{i=0}^{\lfloor\log\log n\rfloor}\sum_{u\in
V(G_{n}),d_{G_{n}}(u,v)=i}\sigma_{i}Z_{u},$ (8)

where $(Z_{v})_{v\in V(G_{n})}$ is a family of independent standard normal
random variables.

We consider the largest eigenvalue for which the theorems apply, that is,
$\lambda=2\sqrt{2}$, as already done in [32]. The idea is that the
corresponding eigenvector has positive correlation between neighbors in
$T_{3}$ (since $\lambda>0$), and thus the cut between the set of vertices
$\\{v\hskip 1.99997pt|\hskip 1.99997ptY_{v}\geq 0\\}$ and the set of vertices
$\\{v\hskip 1.99997pt|\hskip 1.99997ptY_{v}<0\\}$ has relatively few edges
going across. More formally, consider the Gaussian wave $(Y_{v})_{v\in
V(T_{3})}$ on $T_{3}$ given in Theorem 6.2 associated to the eigenvalue
$\lambda=2\sqrt{2}$. As before, let $(G_{n},\rho_{n})$ be any sequence of
graphs converging locally to $T_{3}$. By Theorem 6.3, there exists a linear
factor of iid process $(X^{(n)}_{v})_{v\in V(G_{n})}$ on $G_{n}$ that
converges in distribution to the Gaussian wave $(Y_{v})_{v\in V(T_{3})}$.
Since a Gaussian wave is centered, by setting, for each vertex $v$ of $T_{3}$,
$\phi_{v}=0$ in case $Y_{v}<0$ and setting $\phi_{v}=1$ in case $Y_{v}\geq 0$,
we see that $\phi_{v}\in\\{0,1\\}$ and
$\mathbb{P}(\phi_{\rho}=0)=\frac{1}{2}$. Hence, $\phi\in\mathcal{F}$, and by
(6)

$\limsup_{n\to\infty}\\{bw(G_{n})/|V(G_{n})|\\}\leq\mathbb{E}(|\\{v\sim\rho:\phi_{v}\neq\phi_{\rho})\\}|)/2.$

Now, consider the sequence $(G_{3}(n),\rho_{n})$. We first explain the
approach of [32] using the linear factor of iid process $(X^{(n)}_{v})_{v\in
V(G_{3}(n))}$ (denoted by $(X^{(n)}_{v})$ in the sequel to simplify notation)
described before. We consider events regarding cherries. Recall that a cherry
$(v_{1},v,v_{2})$ consists of three vertices, $v,v_{1},v_{2}\in V(T_{3})$,
connected by edges $vv_{1}$ and $vv_{2}$. Here $v$ is said to be the center of
the cherry, and $v_{1}$ and $v_{2}$ are its endpoints. We also call a cherry
$(v_{1},v,v_{2})$, for which $X_{v}$ has a sign, different from both the sign
of $X_{v_{1}}$ and the sign of $X_{v_{2}}$, a border cherry.

Consider the event that a given cherry with center at $v$ is such that
$X^{(n)}_{v}$ has the same sign as both $X^{(n)}_{v_{1}}$ and
$X^{(n)}_{v_{2}}$. The probability of this event, in the limit as
$n\to\infty$, is given by (the event $X^{(n)}_{v}\neq 0$ being almost sure for
every vertex $v\in G_{3}(n)$),

$\displaystyle\lim_{n\to+\infty}\mathbb{P}(X^{(n)}_{v}\geq
0,X^{(n)}_{v_{1}}\geq 0,X^{(n)}_{v_{2}}\geq
0)+\mathbb{P}(X^{(n)}_{v}<0,X^{(n)}_{v_{1}}<0,X^{(n)}_{v_{2}}<0)$
$\displaystyle=\hskip 3.00003pt$
$\displaystyle\lim_{n\to+\infty}2\mathbb{P}(X^{(n)}_{v}>0,X^{(n)}_{v_{1}}>0,X^{(n)}_{v_{2}}>0)=2\left(\frac{1}{8}+\frac{1}{4\pi}\left(2\arcsin{r_{1}}+\arcsin{r_{2}}\right)\right),$

with

$r_{1}=\text{Corr}(Y_{v},Y_{v_{1}})=\text{Corr}(Y_{v},Y_{v_{2}})=\text{Cov}(Y_{v},Y_{v_{2}})/\sqrt{\text{Var}(Y_{v})\text{Var}(Y_{v_{2}})}$

and

$r_{2}=\text{Corr}(Y_{v_{1}},Y_{v_{2}})=\text{Cov}(Y_{v_{1}},Y_{v_{2}})/\sqrt{\text{Var}(Y_{v_{1}})\text{Var}(Y_{v_{2}})}.$

Here, we abusively view $(v_{1},v,v_{2})$ as a cherry in $T_{3}$ as well. For
the calculation, see for example (6.22) of [26], or also Subsection 4.1 in
[10]. Plugging in the values of $\sigma_{1}=\frac{2\sqrt{2}}{3}$ and
$\sigma_{2}=\frac{5}{6}$ we get that

$\lim_{n\to+\infty}2\mathbb{P}(X^{(n)}_{v}>0,X^{(n)}_{v_{1}}>0,X^{(n)}_{v_{2}}>0)=2\left(\frac{1}{8}+\frac{1}{4\pi}\left(2\arcsin{\frac{2\sqrt{2}}{3}}+\arcsin{\frac{5}{6}}\right)\right)\approx
0.798611.$

Hence, we may conclude that, as $n\to\infty$, with probability tending to
$0.798611$ none of the edges of a cherry participates in the cut with parts
$\\{v\in G_{3}(n)\hskip 1.99997pt|\hskip 1.99997ptX^{(n)}_{v}\geq 0\\}$ and
$\\{v\in G_{3}(n)\hskip 1.99997pt|\hskip 1.99997ptX^{(n)}_{v}<0\\}$.
Similarly, as $n\to\infty$, the probability of a cherry $(v_{1},v,v_{2})$
having exactly one endpoint with a sign, different from the sign of
$X^{(n)}_{v}$, is given by

$\displaystyle\lim_{n\to+\infty}$ $\displaystyle\mathbb{P}(X^{(n)}_{v}\geq
0,X^{(n)}_{v_{1}}\geq
0,X^{(n)}_{v_{2}}<0)+\mathbb{P}(X^{(n)}_{v}<0,X^{(n)}_{v_{1}}<0,X^{(n)}_{v_{2}}\geq
0)$ $\displaystyle+\hskip 3.00003pt$ $\displaystyle\mathbb{P}(X^{(n)}_{v}\geq
0,X^{(n)}_{v_{1}}<0,X^{(n)}_{v_{2}}\geq
0)+\mathbb{P}(X^{(n)}_{v}<0,X^{(n)}_{v_{1}}\geq 0,X^{(n)}_{v_{2}}<0)$
$\displaystyle=\hskip 3.00003pt\lim_{n\to+\infty}$ $\displaystyle
4\mathbb{P}(X^{(n)}_{v}>0,X^{(n)}_{v_{1}}>0,X^{(n)}_{v_{2}}<0)$
$\displaystyle=\hskip 31.49998pt$ $\displaystyle
4\left(\frac{1}{8}+\frac{1}{4\pi}\left(\arcsin{\frac{2\sqrt{2}}{3}}+\arcsin{\frac{-2\sqrt{2}}{3}}+\arcsin{\frac{-5}{6}}\right)\right)\approx
0.186429.$

By analogy, the probability to obtain a border cherry, as $n\to\infty$, tends
to

$\displaystyle\lim_{n\to+\infty}$ $\displaystyle\mathbb{P}(X^{(n)}_{v}\geq
0,X^{(n)}_{v_{1}}<0,X^{(n)}_{v_{2}}<0)+\mathbb{P}(X^{(n)}_{v}<0,X^{(n)}_{v_{1}}\geq
0,X^{(n)}_{v_{2}}\geq 0)$ $\displaystyle=\hskip 3.00003pt\lim_{n\to+\infty}$
$\displaystyle 2\mathbb{P}(X^{(n)}_{v}>0,X^{(n)}_{v_{1}}<0,X^{(n)}_{v_{2}}<0)$
$\displaystyle=\hskip 31.49998pt$ $\displaystyle
2\left(\frac{1}{8}+\frac{1}{4\pi}\left(\arcsin{\frac{-2\sqrt{2}}{3}}+\arcsin{\frac{-2\sqrt{2}}{3}}+\arcsin{\frac{5}{6}}\right)\right)\approx
0.0149586.$

Consider the partition $(V^{(n)}_{1},V^{(n)}_{2})$ of $V(G_{3}(n))$, where
$V^{(n)}_{1}=\\{v\in V(G_{3}(n))\hskip 1.99997pt|\hskip 1.99997ptX_{v}\geq
0\\}$ and $V^{(n)}_{2}=V(G_{3}(n))\setminus V^{(n)}_{1}$.

######  Observation 6.4 (Theorem 4.1 in [32]).

The minimum bisection in a random $3-$regular graph is of size a.a.s. at most

$(0.186429+2\times 0.0149586)\frac{3n}{4}\approx 0.16226n.$

###### Sketch of proof..

By summing over all $3n$ cherries and taking into account that each edge is
counted in four cherries, we get that, as $n\to\infty$, the expected size of
the cut $(V^{(n)}_{1},V^{(n)}_{2})$ is equal to $(0.186429+2\times
0.0149586)\frac{3n}{4}\approx 0.16226n$. While this cut is not necessarily a
bisection, by (8), $(X^{(n)}_{v})$ is a process depending on the set of
standard normal variables corresponding to vertices at distance at most
$\log\log n$ from $v$ in $G_{3}(n)$ only. Hence, since two uniformly chosen
vertices in $G_{3}(n)$ are at distance $\Omega(\log n)$ from each other (which
follows by a direct computation), by a standard and well-known second moment
argument, a.a.s. $|V^{(n)}_{1}|-|V^{(n)}_{2}|=o(n)$. Concentration of the
number of border cherries, as well as the number of cherries $(v_{1},v,v_{2})$
with $X^{(n)}_{v_{1}}$ and $X^{(n)}_{v_{2}}$ being of different signs, around
their expected values follows also from a similar second moment computation. ∎

We now improve on Lyons’ result of Observation 6.4.

######  Observation 6.5.

The number of vertices $v$ in $G_{3}(n)$, which are centers of three border
cherries, is a.a.s. $o(n)$ as $n\to+\infty$.

###### Proof.

Since the distribution of the process $(X^{(n)}_{v})$ approximates the one of
the Gaussian wave on $T_{3}$ for the eigenvalue $\lambda=2\sqrt{2}$, for a
uniformly random vertex $v$ of $G_{3}(n)$ (of course, $v$ depends on $n$, but
the dependence is not made explicit to simplify notation) with neighbors
$v_{1},v_{2},v_{3}$ we have that a.a.s.

$2\sqrt{2}X^{(n)}_{v}-(X^{(n)}_{v_{1}}+X^{(n)}_{v_{2}}+X^{(n)}_{v_{3}})=o(1).$

This proves the observation since, for any sequence $v_{n}\in G_{3}(n)$, the
sequence of random variables $(X^{(n)}_{v_{n}})$ converges in distribution to
a standard normal random variable and thus

$\mathbb{P}(X^{(n)}_{v_{n}}\in[0,\varepsilon))\underset{\varepsilon\to
0^{+}}{\longrightarrow}0.$

∎

######  Corollary 6.6.

The number of vertices, which are centers of more than one border cherry, is
a.a.s. $o(n)$.∎

###### Proof of the upper bound of Theorem 1.1.

We construct the bipartite graph
$H^{(n)}=(H^{(n)}_{1},H^{(n)}_{2})\subseteq(V^{(n)}_{1},V^{(n)}_{2})$. Its
vertices are the centers of border cherries. Its edges are the ones crossing
the cut $(V^{(n)}_{1},V^{(n)}_{2})$, whose endvertices are both centers of
border cherries (see Figure 19). First, since two uniformly chosen vertices in
$G_{3}(n)$ are at distance $\Omega(\log n)$ from each other (which follows by
a direct computation), by a standard and well-known second moment argument,
a.a.s. $|V^{(n)}_{1}|-|V^{(n)}_{2}|=o(n)$ (see the proof of Observation 6.4).

$v$$v^{\prime}$$u$$u^{\prime}$ Figure 19: The construction of the bipartite
graph $H^{(n)}$. The vertices in black belong to $V^{(n)}_{1}$, and the
vertices in white belong to $V^{(n)}_{2}$. Since $(u^{\prime},v,u)$ is a
cherry with black center and white endpoints, and $(v,u,v^{\prime})$ is a
cherry with white center and black endpoints, the vertex $v$ ($u$,
respectively) is included in $H^{(n)}_{1}$ ($H^{(n)}_{2}$, respectively), and
the edge $uv$ is included in $H^{(n)}$.

Since for a given border cherry the probability to have its center in
$V^{(n)}_{1}$ is $\frac{0.0149595}{2}$, and there are a.a.s. $3n/2+o(n)$
cherries with centers in $V^{(n)}_{1}$, in total there are a.a.s. at least
$0.0149595\cdot\frac{3n}{2}+o(n)\approx 0.022438n+o(n)$ vertices in
$H^{(n)}_{1}$ (concentration around the expected values follows as before).
Notice that here we take into account Corollary 6.6 by saying that, a.a.s.,
$|V(H^{(n)})|$ is, up to $o(n)$, equal to the total number of centers of
border cherries. We conclude by Lemma 5.6 that a.a.s. there exists an
independent set $I_{n}$ having at least
$\xi_{n}=\frac{0.022438n}{2}+o(n)=0.011219n+o(n)$ vertices of $H^{(n)}_{1}$
and $\xi_{n}$ vertices of $H^{(n)}_{2}$. Sending the vertices in $I_{n}\cap
H^{(n)}_{1}$ to $V^{(n)}_{2}$ and sending back the vertices in $I_{n}\cap
H^{(n)}_{2}$ to $V^{(n)}_{1}$ leads a.a.s. to a cut
$(U^{(n)}_{1},U^{(n)}_{2})$ with $|U^{(n)}_{1}|=|V^{(n)}_{1}|=n/2-o(n)$ and
size at most $0.16226n+o(n)-2\xi_{n}=0.139822n+o(n)$. After exchanging another
$o(n)$ vertices, $(U^{(n)}_{1},U^{(n)}_{2})$ may be transformed into a
bisection, which finishes the proof. ∎

We remark that the value obtained is exactly the same as the one given in [20]
for the number of edges not going through a maximum cut of a random
$3-$regular graph (although the authors there prefer to give only two digits
after the decimal point). Their result is a corollary of the paper [10]. It
uses a similar approach to our paper to find a maximum cut based on the
eigenvalue $\lambda_{min}=-2\sqrt{2}$ of the transition operator of the random
$3-$regular graph. The numbers appearing in both calculations are the same.
From a combinatorial point of view, the rough intuitive explanation of this
phenomenon is the following: in [20] the authors pick two maximal independent
sets on both sides of the cut (of equal sizes) and then add the remaining
vertices in greedy order to the part where they have less neighbors. From an
algorithmic point of view, this is equivalent to choosing arbitrarily the part
of every vertex outside of the two initial independent sets and then switch
vertices having at most one neighbor on the other side as long as this is
possible. We pick a minimum bisection given by the largest eigenvector and
switch vertices having at least two neighbors on the other side as long as
this is possible. Despite the fact that this is far from a proof, this
phenomenon was observed before - Zdeborová and Boettcher conjectured in [37]
that the number of edges crossing a minimum bisection in a random $3-$regular
graph is a.a.s. (up to $o(n)$) equal to the number of edges not crossing a
maximum cut in such a graph.

Non-rigorous improvement. The previous argument does not take into account
that vertices of degree zero in the bipartite graph
$(H^{(n)}_{1},H^{(n)}_{2})$ can be freely switched from one side to the other.
Indeed, having once identified the number of these vertices on each side, they
can be switched to reduce the cut, and in the remaining graph consisting of
vertices of degree one or two, Lemma 5.6 can be applied. In order to compute
the probability that one vertex $v_{4}$ in, say, $V^{(n)}_{2}$ with neighbors
$v_{3},v_{5}$ in $V^{(n)}_{1}$ has degree zero in $H^{(n)}$, we must have for
the other two neighbors $v_{1},v_{2}$ of $v_{3}$ and for the other two
neighbors $v_{6},v_{7}$ of $v_{5}$ that $X^{(n)}_{v_{1}}\geq
0,X^{(n)}_{v_{2}}\geq 0,X^{(n)}_{v_{6}}\geq 0$ and $X^{(n)}_{v_{7}}\geq 0$.
See Figure 20. Analogous computations hold if the vertex $v_{4}$ is in
$V^{(n)}_{1}$ and all remaining vertices are in $V^{(n)}_{2}$.

$v_{4}$$v_{5}$$v_{3}$$v_{2}$$v_{1}$$v_{7}$$v_{6}$ Figure 20: The vertices in
black belong to $V^{(n)}_{1}$, and the vertices in white belong to
$V^{(n)}_{2}$. In the figure $v_{4}$ is an isolated vertex in $H^{(n)}$, since
neither $v_{3}$, nor $v_{5}$ participate in a border cherry.

Now, let us compute

$\mathbb{P}(X^{(n)}_{v_{1}}>0,X^{(n)}_{v_{2}}>0,X^{(n)}_{v_{3}}>0,-X^{(n)}_{v_{4}}>0,X^{(n)}_{v_{5}}>0,X^{(n)}_{v_{6}}>0,X^{(n)}_{v_{7}}>0).$
(9)

We proceed as before. Using (7), we obtain that the covariance matrix of the
random vector

$(X^{(n)}_{v_{1}},X^{(n)}_{v_{2}},X^{(n)}_{v_{3}},-X^{(n)}_{v_{4}},X^{(n)}_{v_{5}},X^{(n)}_{v_{6}},X^{(n)}_{v_{7}})^{T}$

converges to the matrix $B$, given by:

$\begin{pmatrix}1&5/6&2\sqrt{2}/3&-5/6&1/\sqrt{2}&7/12&7/12\\\
5/6&1&2\sqrt{2}/3&-5/6&1/\sqrt{2}&7/12&7/12\\\
2\sqrt{2}/3&2\sqrt{2}/3&1&-2\sqrt{2}/3&5/6&1/\sqrt{2}&1/\sqrt{2}\\\
-5/6&-5/6&-2\sqrt{2}/3&1&-2\sqrt{2}/3&-5/6&-5/6\\\
1/\sqrt{2}&1/\sqrt{2}&5/6&-2\sqrt{2}/3&1&2\sqrt{2}/3&2\sqrt{2}/3\\\
7/12&7/12&1/\sqrt{2}&-5/6&2\sqrt{2}/3&1&5/6\\\
7/12&7/12&1/\sqrt{2}&-5/6&2\sqrt{2}/3&5/6&1\end{pmatrix}$

Using the eigenvalue decomposition of $B$, we find the matrix $V$ satisfying
$VV^{T}=B$ with approximate entries

$\begin{pmatrix}0&0&-0.2887&0&-0.4082&0.0676&0.8634\\\
0&0&0.2887&0&-0.4082&0.0676&0.8634\\\ 0&0&0&0&-0.2887&-0.0215&0.9572\\\
0&0&0&0&0&0.1962&-0.9806\\\ 0&0&0&0&0.2887&-0.0215&0.9572\\\
0&0&0&-0.2887&0.4082&0.0676&0.8634\\\
0&0&0&0.2887&0.4082&0.0676&0.8634\end{pmatrix}.$

In particular, applying $V$ on the left to the standard normal vector
$(Z_{v_{1}},Z_{v_{2}},Z_{v_{3}},Z_{v_{4}},Z_{v_{5}},Z_{v_{6}},Z_{v_{7}})^{T}$
gives us the desired joint distribution of the seven-dimensional vector
$(Y_{v_{1}},Y_{v_{2}},Y_{v_{3}},-Y_{v_{4}},Y_{v_{5}},Y_{v_{6}},Y_{v_{7}})^{T}$
(by abuse of notation we assume again that the vertices $(v_{i})_{i\geq 1}$
are included in $G_{3}(n)$ as well as in $T_{3}$). Indeed, recall that the
linear factors of iid $(X^{(n)}_{v})_{v\in V(G_{3}(n))}$ converge in
distribution to the Gaussian wave $(Y_{v})_{v\in V(T_{3})}$. More precisely,
in order for all seven coordinates of this resulting vector to be positive,
the following inequalities must hold:

$\displaystyle Z_{v_{7}}$ $\displaystyle>$
$\displaystyle-(V_{1,3}Z_{v_{3}}+V_{1,5}Z_{v_{5}}+V_{1,6}Z_{v_{6}})/V_{1,7}$
(10) $\displaystyle Z_{v_{7}}$ $\displaystyle>$
$\displaystyle-(V_{2,3}Z_{v_{3}}+V_{2,5}Z_{v_{5}}+V_{2,6}Z_{v_{6}})/V_{2,7}$
(11) $\displaystyle Z_{v_{7}}$ $\displaystyle>$
$\displaystyle-(V_{3,5}Z_{v_{5}}+V_{3,6}Z_{v_{6}})/V_{3,7}$ (12)
$\displaystyle Z_{v_{7}}$ $\displaystyle\leq$ $\displaystyle
V_{4,6}Z_{v_{6}}/(-V_{4,7})$ (13) $\displaystyle Z_{v_{7}}$ $\displaystyle>$
$\displaystyle-(V_{5,5}Z_{v_{5}}+V_{5,6}Z_{v_{6}})/V_{5,7}$ (14)
$\displaystyle Z_{v_{7}}$ $\displaystyle>$
$\displaystyle-(V_{6,4}Z_{v_{4}}+V_{6,5}Z_{v_{5}}+V_{6,6}Z_{v_{6}})/V_{6,7}$
(15) $\displaystyle Z_{v_{7}}$ $\displaystyle>$
$\displaystyle-(V_{7,4}Z_{v_{4}}+V_{7,5}Z_{v_{5}}+V_{7,6}Z_{v_{6}})/V_{7,7}$
(16)

Defining $LB$ to be the maximum of all lower bounds corresponding to
inequalities (10, 11, 12, 14, 15, 16) for $X_{v_{7}}$, and
$UB=\max\\{LB,\mbox{ the right hand side of }(\ref{eq7})\\}$, computing the
desired probability (9) is thus equivalent to computing the following
integral:

$\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}\int_{LB}^{UB}e^{-\frac{x_{3}^{2}}{2}-\frac{x_{4}^{2}}{2}-\frac{x_{5}^{2}}{2}-\frac{x_{6}^{2}}{2}-\frac{x_{7}^{2}}{2}}\frac{1}{(2\pi)^{5/2}}dx_{7}dx_{6}dx_{5}dx_{4}dx_{3}.$

Unfortunately, we are not able to compute this integral (even numerically).
Performing a Monte Carlo simulation with $3\times 10^{7}$ iterations (see the
authors’ wegpages for the corresponding Python code) and checking in each
round whether the new sample of
$Z_{v_{3}},Z_{v_{4}},Z_{v_{5}},Z_{v_{6}},Z_{v_{7}}$ satisfies all
inequalities, we obtain an estimated value of $0.002818666$. Therefore, the
total number of border cherries having their centers in $H^{(n)}_{2}$ and of
degree zero in $H^{(n)}$ is $3\times 0.00281866n=0.008456n+o(n)$ a.a.s.
(concentration around the expected value follows as before). By symmetry, this
clearly holds also for border cherries having their centers in $H^{(n)}_{1}$
and of degree zero in $H^{(n)}$.

We can therefore improve the previous argument in the following way: first
switch the $2\times 0.008456n+o(n)$ centers of border cherries having degree
zero in $H^{(n)}$ ($0.008456n+o(n)$ in both parts of the graph) to the other
side of the cut (that is, change the associated value $\phi_{v}$ from $0$ to
$1$ and vice versa), yielding a total a.a.s. gain of $0.016912n+o(n)$ edges.
These centers of cherries "disappear" as vertices of $H^{(n)}$ since they are
no longer centers of border cherries. We apply Lemma 5.6 to the remaining
bipartite graph with parts of size $0.022438n-0.0084912n+o(n)=0.013982n+o(n)$
to obtain an independent set of size at least
$2\times\frac{0.013982n}{2}+o(n)$. Switching these to the other side gives
another gain of $0.013982+o(n)$, thus yielding a total cut
$(U^{(n)}_{1},U^{(n)}_{2})$ size of at most
$0.16226n-0.016912n-0.013982n+o(n)=0.131366n+o(n)$ with
$|U^{(n)}_{1}|-|U^{(n)}_{2}|=o(n)$ a.a.s. As above, this cut may be
transformed into a bisection by switching the sides of at most $o(n)$ vertices
of $G_{3}(n)$. We remark that this numerical value is also close to the one in
Remark 4.1 given in [10] for numerical calculation of the number of edges, not
included in a maximum cut of $G_{3}(n)$, thus giving another indication for
the conjecture of [37] holding true.

Clearly, taking into account different substructures (such as, for example,
paths $v_{1},v_{2},\dots,v_{k}$ of three or more consecutive vertices, for
which $(X_{v_{i}})_{1\leq i\leq k}$ have all the same sign, and each of
$(v_{i})_{1\leq i\leq k}$ having exactly one neighbor $(u_{i})_{1\leq i\leq
k}$, respectively, such that for every $i\in[k]$, $X_{v_{i}}$ and $X_{u_{i}}$
have different signs, or other structures that were observed in the proof of
the lower bound), we could further improve the previous bound. Since we cannot
evaluate the corresponding integrals numerically, we stopped as this point.

##  7 Acknowledgements

The first author would like to thank Ivailo Hartarsky for a technical remark.

## References

  * [1] N. Alon.  On the edge-expansion of graphs.  Combin. Probab. Comput., 6:145–152, 1997.
  * [2] E. A. Bender and E. R. Canfield.  The asymptotic number of labelled graphs with given degree sequences.  Journal of Combinatorial Theory (A), (24(3)):296–307, 1978.
  * [3] S.L. Bezroukov, R. Elsässer, B. Monien, R. Preis, and J.P. Tillich.  New spectral lower bounds on the bisection width of graphs.  in: U. Brandes, D. Wagner (Eds.), 26th Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 1928, Springer, Berlin, pages 23–34, 2000.
  * [4] B. Bollobás.  The isoperimetric number of random regular graphs.  European J. Combin., 9:241–244, 1984.
  * [5] B. Bollobás.  A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.  Europ. J. Combinatorics, 1(1):311–316, August 1980.
  * [6] B. Bollobás.  Random Graphs.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2001.
  * [7] T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser.  Graph bisection algorithms with good average case behavior.  Combinatorica, 7:171–191, 1987.
  * [8] L. H. Clark and R. C. Entringer.  The bisection width of cubic graphs.  Bull. Austral. Math. Soc., 39:389–396, 1988.
  * [9] A. Coja-Oghlan, O. Cooley, M. Kang, and K. Skubch.  The minimum bisection in the planted bisection model.  Theory of Computing, 13, Article 8:1–22, 2017.
  * [10] E. Csóka, B. Gerencsér, V. Harangi, and B. Virág.  Invariant gaussian processes and independent sets on regular graphs of large girth.  Random Structures and Algorithms, 47(2):284–303, 2015.
  * [11] P. Daniele.  Lagrange multipliers and infinite-dimensional equilibrium problems.  Journal of Global Optimization, 40(1-3):65–70, 2008.
  * [12] A. Dembo, A. Montanari, and S. Sen.  Extremal cuts of sparse random graphs.  Ann. Probab., 45(2):1190–1217, 2017.
  * [13] J. Díaz, N. Do, M. J. Serna, and N. C. Wormald.  Bounds on the max and min bisection of random cubic and random 4-regular graphs.  Theoretical Computer Science, 307:531–547, 2003.
  * [14] J. Díaz, J. Petit, and M. J. Serna.  A survey on graph layout problems.  ACM Comput. Surveys, 34:313–356, 2002.
  * [15] J. Díaz, M. J. Serna, and N. C. Wormald.  Computation of the bisection width for random d-regular graphs.  In LATIN 2004: Theoretical Informatics. Lecture Notes in Computer Science 2976 Springer, Berlin, pages 49–58, 2004.
  * [16] M. B. Donato.  The infinite dimensional lagrange multiplier rule for convex optimization problems.  Journal of Functional Analysis, 261(8):2083–2093, 2011.
  * [17] U. Feige and R. Krauthgamer.  A polylogarithmic approximation of the minimum bisection.  41st IEEE Annu. Symp. on Foundation of Computer Science, pages 23–26, 2000.
  * [18] M. Fiedler.  A property of the eigenvectors of nonnegative symmetric matrices and its application to graph theory.  Czechoslovak. Math. J., 25:619–633, 1974.
  * [19] J. Friedman.  A proof of Alon’s second eigenvalue conjecture and related problems.  Memoirs of the American Mathematical Society, 195(910):100p., 2008\.
  * [20] D. Gamarnik and Q. Li.  On the max-cut of sparse random graphs.  Random Structures and Algorithms, 52:219–262, 2018.
  * [21] M.R. Garey and D.S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  Freeman, San Francisco, 1979.
  * [22] O. Guédon and R. Vershynin.  Community detection in sparse networks via Grothendieck’s inequality.  Probability Theory and Related Fields, pages 1–25, 2015.
  * [23] G. H. Hardy and S. Ramanujan.  Asymptotic formulaæ in combinatory analysis.  Proceedings of the London Mathematical Society, 2(1):75–115, 1918\.
  * [24] K. Jansen, M. Karpinski, A. Lingas, and E. Seidel.  Polynomial time approximation schemes for max-bisection on planar and geometric graphs.  in: A. Ferreira, H. Reichel (Eds.), 18th Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Springer, Berlin, 2010:365–375, 2001.
  * [25] S. Janson.  Random regular graphs: asymptotic distributions and contiguity.  Combin. Probab. Comput., (4):369–405, 1995.
  * [26] M. G. Kendall.  Contributions to the study of oscillatory time-series.  Cambridge University Press, 1946.
  * [27] H. Kesten.  Symmetric random walks on groups.  Tran. Math. Amer. Soc., 92:336–354, 1959.
  * [28] S. Khot.  Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique.  In Foundations of Computer Science, Roma, Italy, pages 136–145, 2004.
  * [29] A.V. Kostochka and L.S. Melnikov.  On bounds of the bisection width of cubic graphs.  Proc. Czechoslovakian Symp. on Comb., Graphs and Complexity, pages 151–154, 1992.
  * [30] A.V. Kostochka and L.S. Melnikov.  On a lower bound for the isoperimetric number of cubic graphs.  Proc. Intl. Conf. Probabilistic Methods in Disc. Math., Progress in Pure and Appl. Disc. Math., 1:251–265, 1993.
  * [31] M. J. Luczak and C. McDiarmid.  Bisecting sparse random graphs.  Random Structures and Algorithms, 18:31–38, 2001.
  * [32] R. Lyons.  Factors of IID on trees.  Comb. Prob. Comp., 26(2):285–300, 2017.
  * [33] B. Monien and R. Preis.  Upper bounds on the bisection width of 3- and 4-regular graphs.  In: A. Pultr J. Sgall, P. Kolman (Eds.), Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 2136, Springer, Berlin, pages 524––536, 2001.
  * [34] S. Sen.  Optimization on sparse random hypergraphs and spin glasses.  Random Structures and Algorithms, 53(3):504–536, 2018.
  * [35] N. C. Wormald.  Some Problems in the Enumeration of Labelled Graphs.  PhD thesis, Newcastle University, 1978.
  * [36] N. C. Wormald.  Models of random regular graphs, volume 267 of London Mathematical Society Lecture Note Series, pages 239–298.  Cambridge University Press, 1999.
  * [37] L. Zdeborová and S. Boettcher.  A conjecture on the maximum cut and bisection width in random regular graphs.  Journal of Statistical Mechanics: Theory and Experiment, (02):P02020, 2010.


# Stability of asymptotically flat (2+1)-dimensional black holes with Gauss-
Bonnet corrections
Prepared for the 25th RAGtime workshop, 27 November – 1 December, Opava

Milena Skvortsova<EMAIL_ADDRESS>Peoples’ Friendship University of Russia
(RUDN University), 6 Miklukho-Maklaya Street, Moscow, 117198, Russia

###### Abstract

Using the integration of wave equation in time-domain we show that scalar
field perturbations around the $(2+1)$-dimensional asymptotically flat black
hole with Gauss-Bonnet corrections is dynamically stable even for the near
extreme values of the coupling constant.

##  I Introduction

Black holes have been observed in the gravitational [1] and electromagnetic
[2, 3] spectra, while ongoing projects promise a great extension of the range
of observations [4]. Quasinormal modes [5, 6, 7, 8] represent the
characteristic oscillations that black holes undergo when perturbed, and they
serve as a valuable tool for probing the black holes’ fundamental properties.
Our study explores the intricate interplay between black hole’s quasinormal
modes and their (in)stability. Usually, the strict mathematical proof of
stability is a very difficult problem (see, for instance, [9]). A clear
evidence of the linear stability or instability is provided by the analysis of
the quasinormal spectrum. If all the quasinormal modes are damped, the black
hole is stable, while if there exists at least one unboundedly growing mode,
it signifies the onset of instability. Therefore, the instability was
extensively studied with the help of quasinormal modes spectra [10, 11, 12,
13].

The particular black hole metric we will study here is the $(2+1)$-dimensional
black hole obtained as a regularization [14] of the Einstein-Gauss-Bonnet
equations of motion in [15] and further studied and generalized in [16, 17].
Although the straightforward regularization in [14] did not form a consistent
theory in four dimensions, the black hole solution obtained within such a
naive approach were also solutions of the well-defined theory formulated in
[18].

Quasinormal modes of three-dimensional asymptotically AdS (BTZ) spacetimes
were extensively studied [19, 20, 21], because of their importance in the
AdS/CFT correspondence [22]. However, no such analysis has been done so far
for the $(2+1)$-dimensional asymptotically flat spacetimes, to the best of our
knowledge. Here we will show that the scalar field perturbations around the
$(2+1)$-dimensional asymptotically flat black holes decay with time even at
the near extreme values of the Gauss-Bonnet coupling.

##  II Black hole metrics and wavelike equations

The metric of the (2+1)-dimensional black hole has the following form

$\mathrm{d}s^{2}=-f(r)\mathrm{d}t^{2}+f(r)^{-1}\mathrm{d}r^{2}+r^{2}\mathrm{d}x^{2},$
(1)

where the metric function is

$f(r)=1-\frac{r^{2}}{2\alpha}\left(-1+\sqrt{\frac{4\alpha\left(\Lambda\left(r^{2}-r_{H}^{2}\right)+\frac{\alpha}{r_{H}^{2}}+1\right)}{r^{2}}+1}\right).$
(2)

Here, $r_{H}$ is the radius of the event horizon, $\Lambda$ is the
cosmological constant, $\alpha$ is the Gauss-Bonnet coupling constant. When
$1+2\alpha/r_{H}^{2}>0$ and the coupling constant $\alpha<0$ at $\Lambda=0$
the metric is asymptotically flat and perturbative in $\alpha$. When the
cosmological constant is negative, the metric is reduced to the BTZ one [23]
up to the redefinition of constants. The general-covariant Klein-Gordon
equation

$\frac{1}{\sqrt{-g}}\partial_{\mu}\left(\sqrt{-g}g^{\mu\nu}\partial_{\nu}\Phi\right)=0$
(3)

can be reduced to the wave-like form

$\dfrac{d^{2}\Psi}{dr_{*}^{2}}+(\omega^{2}-V(r))\Psi=0,$ (4)

where the “tortoise coordinate” $r_{*}$ has the form:

$dr_{*}\equiv\frac{dr}{f(r)},$ (5)

and the effective potential is

$V(r)=f(r)\left(\frac{k^{2}}{r^{2}}+\frac{f^{\prime}(r)}{2r}-\frac{f(r)}{4r^{2}}\right)$
(6)

Here $k$ is the multipole number.

##  III Evolution of perturbations

Quasinormal modes of asymptotically flat black holes are eigenvalues of the
above wave-like equation satisfying particular boundary conditions: the waves
must be purely outgoing at infinity and purely incoming at the event horizon.
For analysis of the evolution of perturbations in time and consideration of
contribution of all the overtones, so that the instability, if any, could be
detected, we use the time-domain integration method [24], which was used in
numerous works (for instance, [25, 26, 27]). It shows a good concordance with
more accurate methods. The essence of this method is integration of the wave
equation in the framework of the null-cone coordinates $u=t-r_{*}$,
$v=t+r_{*}$, using the following discretization [24],

$\Psi\left(N\right)=\Psi\left(W\right)+\Psi\left(E\right)-\Psi\left(S\right)-\Delta^{2}V\left(S\right)\frac{\Psi\left(W\right)+\Psi\left(E\right)}{4}+{\cal
O}\left(\Delta^{4}\right).$ (7)

Here, the points are: $N\equiv\left(u+\Delta,v+\Delta\right)$,
$W\equiv\left(u+\Delta,v\right)$, $E\equiv\left(u,v+\Delta\right)$,
$S\equiv\left(u,v\right)$, and the Gaussian impinging wave package are given
on the null surfaces $u=u_{0}$ and $v=v_{0}$.

For checking the results obtained by the time-domain integration at $k>0$ we
used the 6th order WKB method with Padé approximants [28, 29, 30].

Time-domain profiles show decaying profiles not only for small $\alpha$ (see
Fig. 2), but also for the extreme $\alpha$, as in Fig. 1. If the instability
appeared, it would be governed by the non-oscillatory, i.e. purely imaginary,
growing mode, as was proved in [31] for generic static backgrounds.

---
Figure 1: Left: Effective potential as a function of $r_{*}$. Right: Time-
domain profile of perturbations. Here we have $k=0$, $\Lambda=0$,
$\alpha=-0.49$. The Prony method suggests that the dominant modes are non-
oscillatory $\omega=-0.001899i$
---
Figure 2: Left: Effective potential as a function of $r_{*}$. Right: Time-
domain profile of perturbations. Here we have $k=1$, $\Lambda=0$,
$\alpha=-0.01$. The Prony method gives $\omega=0.050145-0.003598i$, while the
6th order WKB method with Pade approximants gives $\omega=0.050155-0.003579i$

##  IV Conclusions

Here we have shown that asymptotically flat $(2+1)$-dimensional black holes
with Gauss-Bonnet corrections are stable even at the near extreme values of
the Gauss-Bonnet coupling. The full parametric range of stability and the
other types of asymptotics could be studied in further research. Thus,
allowing for a non-zero cosmological constant may bring instabilities to the
system [32, 33].

###### Acknowledgements.

The author acknowledges Dr. R. A. Konoplya for fruitful discussions, and for
careful reading of the manuscript. This work was supported by RUDN University
research project FSSF-2023-0003.

## References

  * Abbott  _et al._ [2016] B. P. Abbott _et al._ (LIGO Scientific, Virgo), Phys. Rev. Lett. 116, 061102 (2016), arXiv:1602.03837 [gr-qc] .
  * Akiyama  _et al._ [2019] K. Akiyama _et al._ (Event Horizon Telescope), Astrophys. J. Lett. 875, L1 (2019), arXiv:1906.11238 [astro-ph.GA] .
  * Goddi  _et al._ [2016] C. Goddi _et al._ , Int. J. Mod. Phys. D 26, 1730001 (2016), arXiv:1606.08879 [astro-ph.HE] .
  * Auclair  _et al._ [2023] P. Auclair _et al._ (LISA Cosmology Working Group), Living Rev. Rel. 26, 5 (2023), arXiv:2204.05434 [astro-ph.CO] .
  * Berti  _et al._ [2009] E. Berti, V. Cardoso, and A. O. Starinets, Class. Quant. Grav. 26, 163001 (2009), arXiv:0905.2975 [gr-qc] .
  * Nollert [1999] H.-P. Nollert, Class. Quant. Grav. 16, R159 (1999).
  * Kokkotas and Schmidt [1999] K. D. Kokkotas and B. G. Schmidt, Living Rev. Rel. 2, 2 (1999), arXiv:gr-qc/9909058 .
  * Konoplya and Zhidenko [2011] R. A. Konoplya and A. Zhidenko, Rev. Mod. Phys. 83, 793 (2011), arXiv:1102.4014 [gr-qc] .
  * Beyer [2011] H. R. Beyer, J. Math. Phys. 52, 102502 (2011), arXiv:1105.4956 [math-ph] .
  * Takahashi and Soda [2010] T. Takahashi and J. Soda, Prog. Theor. Phys. 124, 711 (2010), arXiv:1008.1618 [gr-qc] .
  * Ishihara  _et al._ [2008] H. Ishihara, M. Kimura, R. A. Konoplya, K. Murata, J. Soda, and A. Zhidenko, Phys. Rev. D 77, 084019 (2008), arXiv:0802.0655 [hep-th] .
  * Kodama  _et al._ [2010] H. Kodama, R. A. Konoplya, and A. Zhidenko, Phys. Rev. D 81, 044007 (2010), arXiv:0904.2154 [gr-qc] .
  * Dyatlov [2011] S. Dyatlov, Commun. Math. Phys. 306, 119 (2011), arXiv:1003.6128 [math.AP] .
  * Glavan and Lin [2020] D. Glavan and C. Lin, Phys. Rev. Lett. 124, 081301 (2020), arXiv:1905.03601 [gr-qc] .
  * Konoplya and Zhidenko [2020] R. A. Konoplya and A. Zhidenko, Phys. Rev. D 102, 064004 (2020), arXiv:2003.12171 [gr-qc] .
  * Hennigar  _et al._ [2020] R. A. Hennigar, D. Kubiznak, R. B. Mann, and C. Pollack, Phys. Lett. B 808, 135657 (2020), arXiv:2004.12995 [gr-qc] .
  * Hennigar  _et al._ [2021] R. A. Hennigar, D. Kubiznak, and R. B. Mann, Class. Quant. Grav. 38, 03LT01 (2021), arXiv:2005.13732 [gr-qc] .
  * Aoki  _et al._ [2020] K. Aoki, M. A. Gorji, and S. Mukohyama, Phys. Lett. B 810, 135843 (2020), arXiv:2005.03859 [gr-qc] .
  * Cardoso and Lemos [2001] V. Cardoso and J. P. S. Lemos, Phys. Rev. D 63, 124015 (2001), arXiv:gr-qc/0101052 .
  * Konoplya [2004] R. A. Konoplya, Phys. Rev. D 70, 047503 (2004), arXiv:hep-th/0406100 .
  * Fontana [2023] R. D. B. Fontana, (2023), arXiv:2306.02504 [gr-qc] .
  * Birmingham  _et al._ [2002] D. Birmingham, I. Sachs, and S. N. Solodukhin, Phys. Rev. Lett. 88, 151301 (2002), arXiv:hep-th/0112055 .
  * Banados  _et al._ [1992] M. Banados, C. Teitelboim, and J. Zanelli, Phys. Rev. Lett. 69, 1849 (1992), arXiv:hep-th/9204099 .
  * Gundlach  _et al._ [1994] C. Gundlach, R. H. Price, and J. Pullin, Phys. Rev. D 49, 883 (1994), arXiv:gr-qc/9307009 .
  * Konoplya and Fontana [2008] R. A. Konoplya and R. D. B. Fontana, Phys. Lett. B 659, 375 (2008), arXiv:0707.1156 [hep-th] .
  * Churilova and Stuchlik [2020] M. S. Churilova and Z. Stuchlik, Class. Quant. Grav. 37, 075014 (2020), arXiv:1911.11823 [gr-qc] .
  * Bronnikov and Konoplya [2020] K. A. Bronnikov and R. A. Konoplya, Phys. Rev. D 101, 064004 (2020), arXiv:1912.05315 [gr-qc] .
  * Konoplya  _et al._ [2019] R. A. Konoplya, A. Zhidenko, and A. F. Zinhailo, Class. Quant. Grav. 36, 155002 (2019), arXiv:1904.10333 [gr-qc] .
  * Matyjasek and Opala [2017] J. Matyjasek and M. Opala, Phys. Rev. D 96, 024011 (2017), arXiv:1704.00361 [gr-qc] .
  * Konoplya [2003] R. A. Konoplya, Phys. Rev. D 68, 024018 (2003), arXiv:gr-qc/0303052 .
  * Konoplya  _et al._ [2008] R. A. Konoplya, K. Murata, J. Soda, and A. Zhidenko, Phys. Rev. D 78, 084012 (2008), arXiv:0807.1897 [hep-th] .
  * Zhu  _et al._ [2014] Z. Zhu, S.-J. Zhang, C. E. Pellicer, B. Wang, and E. Abdalla, Phys. Rev. D 90, 044042 (2014), [Addendum: Phys.Rev.D 90, 049904 (2014)], arXiv:1405.4931 [hep-th] .
  * Konoplya and Zhidenko [2014] R. A. Konoplya and A. Zhidenko, Phys. Rev. D 90, 064048 (2014), arXiv:1406.0019 [hep-th] .