# TransFusion – A Transparency-Based Diffusion Model for Anomaly Detection

Matic Fučka, Vitjan Zavrtanik, Danijel Skočaj
University of Ljubljana, Faculty of Computer and Information Science
{matic.fucka, vitjan.zavrtanik<EMAIL_ADDRESS>
###### Abstract

Surface anomaly detection is a vital component in manufacturing inspection.
Reconstructive anomaly detection methods restore the normal appearance of an
object, ideally modifying only the anomalous regions. Due to the limitations
of commonly used reconstruction architectures, the produced reconstructions
are often poor and either still contain anomalies or lack details in anomaly-
free regions. Recent reconstructive methods adopt diffusion models, however
with the standard diffusion process the problems are not adequately addressed.
We propose a novel transparency-based diffusion process, where the
transparency of anomalous regions is progressively increased, restoring their
normal appearance accurately and maintaining the appearance of anomaly-free
regions without loss of detail. We propose TRANSparency DifFUSION
(TransFusion), a discriminative anomaly detection method that implements the
proposed diffusion process, enabling accurate downstream anomaly detection.
TransFusion achieves state-of-the-art performance on both the VisA and the
MVTec AD datasets, with an image-level AUROC of 98.5% and 99.2%, respectively.

##  1 Introduction

Figure 1: The reformulated diffusion model iteratively erases the anomalous
regions during the backwards diffusion process. Training on synthetic
anomalies (top) generalizes well to real anomalies (marked with red circles)
seen at inference (bottom), leading to accurate output masks $M_{final}$ that
closely match the ground truth $M_{true}$.

The primary objective of surface anomaly detection is the identification and
localization of anomalies in images. In the standard problem setup only
anomaly-free (normal) images are used to learn a normal appearance model and
any deviations from the learned model are classified as anomalies. Surface
anomaly detection is commonly used in various industrial domains [8, 45, 9]
where the limited availability of abnormal images along with their
considerable diversity makes training supervised models impractical.

Many of the recent surface anomaly detection methods follow the reconstructive
[41, 37, 30, 1] or the discriminative [42, 40] paradigms. Reconstructive
methods train an autoencoder-like network on anomaly-free images and assume
that the autoencoder will not generalize well to anomalous regions, since they
were not seen during training, making them distinguishable by reconstruction
error. Discriminative methods are trained to segment synthetic anomalies [40,
38, 44] and learn a normal-appearance model to generalize to real-world cases.
A reconstructive network is commonly used as the normal-appearance model in
discriminative methods.

Discriminative and reconstructive methods exhibit two core issues. First,
reconstructive methods may overgeneralize which causes them to reconstruct
even anomalous regions leading to false negative detections. Second, due to
the limited image generation capabilities of the commonly used reconstructive
architectures, finegrained details in normal regions tend to be erased leading
to loss of detail in normal regions, causing false positive detections. Both
issues contribute to a poor downstream anomaly detection performance.
Recently, standard diffusion models [14, 31, 5] have been used in place of
reconstruction models in anomaly detection [37, 22, 43]. Due to their addition
of the standard Gaussian noise to images all these methods suffer from the
loss of detail in the normal regions. Additionally, most diffusion-based
methods perform only partial image reconstruction, retaining some anomalous
region information, leading to overgeneralization.

To simultaneously address both problems of reconstructive methods, we propose
a novel transparency-based diffusion process reformulated explicitly for
surface anomaly detection. Through the proposed diffusion process, the
transparency of anomalies is iteratively increased so that they are gradually
replaced with the corresponding normal appearance (Figure 1), effectively
erasing the anomalies. Increasing the transparency as the objective of the
diffusion process enables a precise anomaly-free reconstruction of the
anomalous regions – addressing overgeneralization, whilst leaving the normal
regions intact – addressing the loss of detail problem. To implement the
transparency-based diffusion process, we propose TransFusion (TRANSparency
DifFUSION), a surface anomaly detection method that integrates the powerful
appearance modelling capabilities of diffusion models in the discriminative
anomaly detection paradigm. Compared to the previously used reconstructive
networks that attempted to implicitly detect and restore the anomaly-free
appearance of anomalous regions in a single step [40, 42, 44], TransFusion can
maintain more accurate restorations of anomalous regions without the
overgeneralization problem and without loss-of-detail in the anomaly-free
regions. Due to the iterative nature of the reformulated diffusion process,
TransFusion is able to focus on various visual characteristics of anomalies at
various time-steps, even potentially addressing the regions previous
iterations may have missed. This enables high-fidelity anomaly-free
reconstructions, improving the downstream anomaly detection performance.

The main contributions of our work are as follows:

  * •

We propose a novel transparency-based diffusion process reformulated
explicitly for the problem of surface anomaly detection. It directly addresses
the overgeneralization and loss-of-detail problems of recent reconstructive
anomaly detection methods.

  * •

We propose TransFusion - A strong discriminative anomaly detection model that
implements the transparency-based diffusion process. TransFusion iteratively
increases the transparency of anomalies and simultaneously provides their
explicit localization, leading to a strong anomaly detection performance even
in difficult near-in-distribution scenarios.

  * •

We perform extensive experiments on two challenging datasets and show that
TransFusion achieves state-of-the-art results in anomaly detection on two
standard challenging datasets – VisA [45] and MVTec AD [8], with an AUROC of
98.5% and 99.2%, respectively. TransFusion sets a new state-of-the-art in
anomaly detection in terms of the mean across both datasets, achieving a 98.9%
AUROC, surpassing the previous state-of-the-art by a significant margin of 1.6
percentage points, thus demonstrating its versatility across various
scenarios.

##  2 Related Work

Surface anomaly detection has been a subject of intense research in recent
years, and various approaches have been proposed to address this task. Methods
can be divided into three main paradigms: reconstructive, embedding-based, and
discriminative.

Reconstructive methods train an autoencoder-like network [6, 28, 41] or a
generative model [1, 30, 37, 22] and assume that anomalies will be poorly
reconstructed compared to the normal regions making them distinguishable by
reconstruction error. A solution proposed by Zavrtanik [41] involved masking
parts of the image and reconstructing it using information from neighboring
patches. The poor reconstruction assumption does not always hold, leading to
poor performance.

Embedding-based methods use feature maps [21, 16] extracted with a pretrained
network to learn normality on these maps. Patchcore [25] creates a coreset
memory bank out of the extracted normal features. Several normalizing-flow-
based [13, 26, 39, 33] approaches have been proposed as well. Some methods
utilize a student-teacher [7, 11, 27] network and assume that the student will
not be able to produce meaningful features for the anomalies as it had not
seen them during training. All these methods assume that the distribution of
normal regions will be well represented in the training data and fail on rare
normal regions unseen during training, producing false positives.

Discriminative methods use synthetically generated defects [40, 42, 18, 44,
38, 21] to train their model with the idea that the model can then generalize
on real anomalies. In seminal works of this paradigm such as DRÆM [40], a
reconstructive module is trained to restore the normal appearance and a
discriminative network is trained to segment synthetic anomalies. The normal
appearance can also be modelled using pretrained features [44, 38, 21]. DSR
[42] uses a vector-quantized autoencoder for normal appearance reconstruction,
however it still suffers from loss of detail of normal regions.

Figure 2:  TransFusion’s training and inference pipelines. Training examples
are created from normal images $x$ by generating the anomaly mask $M$ and the
anomaly appearance $\epsilon$ and imposing them on $x$ according to the
transparency schedule $\beta_{t}$. The resulting image $x_{t}$ contains
synthetic anomalies. TransFusion is guided by an augmented mask $M_{a}$.
TransFusion outputs the estimated anomaly mask $M_{t}$, the anomaly appearance
$\epsilon_{t}$, and the normal appearance $n_{t}$. At inference, TransFusion
infers $M_{t}$, $\epsilon_{t}$, and $n_{t}$ from the input image and
constructs the next step image according to Eq. 4. The predicted mask $M_{t}$
and the constructed $x_{t-1}$ are used as the input in the next step.

Diffusion models recently emerged as state-of-the-art in image generation
[14]. They have been extended to various domains, such as audio [17, 15] and
text generation [19, 3]. Methods have also been proposed that tackle problems
such as semantic segmentation [2, 36] and object detection [10]. It has also
been shown that the Gaussian noise-based diffusion process is not necessary
for all problems [4, 10].

Diffusion-based anomaly detection Wyatt et. al. [37] proposed AnoDDPM which is
based on a standard diffusion architecture [14]. AnoDDPM was applied to a
medical image dataset and achieved state-of-the-art results. Lu et. al. [22]
proposed using a DDPM to simultaneously predict the noise and to generate
features that mimic the features extracted from a pretrained convolutional
neural network. DiffAD [43] uses a DRÆM-like [40] network but exchanges the
autoencoder with a latent diffusion model. All recent diffusion approaches
face problems with loss of detail in the normal regions. As a result, they
exhibit a high rate of false positives. This suggests that naively applying
the standard diffusion process is not sufficient for surface anomaly
detection.

##  3 TransFusion

Reconstructive modules of discriminative anomaly detection approaches are
tasked with implicitly localizing anomalies and restoring their normal visual
appearance. To achieve a better detection robustness and reconstruction
capability of such a process, an appropriate diffusion model is defined.
Previous work [4] has established that a variety of iterative processes can be
used to achieve the desired diffusion effect. In the proposed transparency-
based diffusion process reformulation, images are thought of as a composition
of anomalous and normal components, partitioned by the anomaly mask $M$. To
frame the anomaly localization and restoration as an iterative process, the
anomalous regions are expressed as a linear interpolation between the
anomalous and the normal appearance at each step. This equates to the
transparency of the anomalous regions increasing throughout the diffusion
process (Figure 1). In this section, we describe TransFusion in detail.

###  3.1 Transparency-based diffusion model

In the transparency-based diffusion process reformulation, each image $I$ is
expressed as a composition of the normal appearance $N$, the anomaly
appearance $A$, the anomaly mask $M$, and the blending factor between the
anomalous and the normal appearance $\beta$, i.e., the transparency level of
the anomaly:

$I=\overline{M}\odot N+\beta(M\odot A)+(1-\beta)(M\odot N),$ (1)

where $M$ is a binary mask where the anomalous pixels are set to $1$ and
$\overline{M}$ is the inverse of $M$. The anomalous region is an interpolation
between the anomaly appearance $A$ and the normal appearance $N$ in the region
specified by the anomaly mask $M$. The transparency of the anomalous region is
defined by $\beta$. The restoration of the normal appearance from an anomalous
image $I$ can be modelled as an iterative process of gradually increasing the
anomaly transparency until only the normal appearance remains. This is not a
trivial task, since the accurate localization $M$, normal appearance $N$ and
anomaly appearance $A$ must be inferred from the input image $I$.

During training, images containing synthetic anomalies and their corresponding
anomaly masks are used. For each step in the forward process, the value of
$\beta$ is gradually increased, thus decreasing the transparency of anomalies,
and increasing their prominence. Let $x_{t}$ denote the anomalous image $I$ at
time step $t$. The transparency schedule is denoted as
$\beta_{0}<\beta_{1}<...<\beta_{T-1}<\beta_{T}$, where $\beta_{0}=0$ and
$\beta_{T}=1$. Eq. (1) is rewritten to correspond to timestep $t$ by
substituting the variables $A$ with $\epsilon_{t}$, $M$ with $M_{t}$, and $N$
with $n_{t}$:

$\displaystyle\begin{split}x_{t}&=\overline{M}_{t}\odot n_{t}\\\
&+\beta_{t}(M_{t}\odot\epsilon_{t})\\\ &+(1-\beta_{t})(M_{t}\odot
n_{t}).\end{split}$ (2)

The image with more transparent anomalies $x_{t-1}$ at iteration $t-1$ is then
computed:

$\displaystyle\begin{split}x_{t-1}&=\overline{M}_{t-1}\odot n_{t-1}\\\
&+\beta_{t-1}(M_{t-1}\odot\epsilon_{t-1})\\\ &+(1-\beta_{t-1})(M_{t-1}\odot
n_{t-1}).\end{split}$ (3)

$\beta_{t}$ decreases between steps $t$ and $t-1$, while the correct values of
$M_{t}$, $n_{t}$ and $\epsilon_{t}$ are predefined and remain constant
throughout the forward process. We can thus write $M_{t}=M_{t-1}=\ldots=M$,
$\epsilon_{t}=\epsilon_{t-1}=\ldots=A$ and $n_{t}=n_{t-1}=\ldots=N$. After
substituting $M_{t-1}$ for $M_{t}$, $\epsilon_{t-1}$ for $\epsilon_{t}$ and
$n_{t-1}$ for $n_{t}$ in Eq. (3), subtracting it from Eq. (2) and then
rearranging it, the transition between steps $x_{t}$ and $x_{t-1}$ is
computed:

$\displaystyle\begin{split}x_{t-1}&=x_{t}\\\
&-(\beta_{t}-\beta_{t-1})(M_{t}\odot\epsilon_{t})\\\
&+(\beta_{t}-\beta_{t-1})(M_{t}\odot n_{t}).\end{split}$ (4)

At each time step in the reverse process, the value of $x_{t}$ moves towards
the anomaly-free $x_{0}$ by an amount influenced by $\beta_{t}-\beta_{t-1}$.
The anomaly’s transparency is therefore gradually increased, reconstructing
the normal appearance until the final anomaly-free restoration $x_{0}$ is
reached. This requires an accurate estimation of the anomaly mask $M_{t}$, the
normal appearance $n_{t}$ and the anomaly appearance $\epsilon_{t}$ at each
time step.

###  3.2 Architecture

The architecture of TransFusion, depicted in Figure 2, is based on ResUNet
[12] which is commonly used in diffusion models. TransFusion has three
prediction heads, which output the anomaly appearance $\epsilon_{t}$, anomaly
mask $M_{t}$ and the normal appearance $n_{t}$, enabling the generation of the
image in the next reverse step according to Eq. (4). The anomaly and normal
appearance heads consist of a single convolutional layer, while the anomaly
mask head consists of a BatchNorm, SiLU and a convolutional layer.

The input to the diffusion model at each timestep consists of four elements:
the current reconstruction estimate $x_{t}$, the mask estimate $M_{t}$, the 2D
sinusoidal positional encoding $PE$ [34], and the timestep $t$. All the
elements are channel-wise concatenated except for the timestep embedding which
is added to the features. During training, images containing synthetic
anomalies are generated from an anomaly-free image $x$, the anomaly mask $M$,
and the anomaly appearance $\epsilon$. The input image $x_{t}$ is generated
according to Eq. 2, where $n_{t}=x$, $\epsilon_{t}=\epsilon$ and $M_{t}=M$,
and the $\beta$ schedule for the sampled timestep $t$. Losses for the
prediction head outputs $n_{t}$, $M_{t}$ and $\epsilon_{t}$ are calculated
using $x$, $M$ and $\epsilon$ as ground truth values, respectively.

Separate loss functions are used for each prediction head. The normal
appearance prediction head uses the structural similarity (SSIM) loss [35] and
the $\mathcal{L}_{1}$ loss:

$\mathcal{L}_{n}=SSIM(n_{t},x)+\mathcal{L}_{1}(n_{t},x).$ (5)

The anomaly mask head uses the focal loss [20] and the Smooth
$\mathcal{L}_{1}$ loss, commonly used in discriminative anomaly detection [38,
40]:

$\mathcal{L}_{m}=\alpha\mathcal{L}_{foc}(M_{t},M)+\mathcal{L}_{1Smooth}(M_{t},M).$
(6)

The weighting parameter $\alpha$ is set to 5 in all experiments. The anomaly
appearance prediction head employs the standard $\mathcal{L}_{2}$
reconstruction loss:

$\mathcal{L}_{a}=\mathcal{L}_{2}(\epsilon_{t},\epsilon).$ (7)

To ensure the consistency between difusion steps, where $x_{t-1}$ is computed
from the estimated $M_{t}$, $\epsilon_{t}$, $n_{t}$ and the previous step
$x_{t}$ using Eq. (4), an additional consistency loss function
$\mathcal{L}_{c}$ is employed. $\mathcal{L}_{c}$ compares the predicted
$x_{t-1}$ with the ground truth $\tilde{x}_{t-1}$ computed using the ground
truth $M$, $\epsilon$, and $x$:

$\mathcal{L}_{c}=\mathcal{L}_{2}(x_{t-1},\tilde{x}_{t-1}).$ (8)

The complete TransFusion loss is then given as:

$\mathcal{L}=\mathcal{L}_{n}+\mathcal{L}_{m}+\mathcal{L}_{a}+\mathcal{L}_{c}.$
(9)

###  3.3 Synthetic anomaly generation

Following commonly used procedures [40, 38], synthetic anomalies are generated
by pasting out-of-distribution regions on the anomaly-free inputs, outputting
the image containing synthetic anomalies $I$ and the anomaly mask $M$. $M$ is
generated using Perlin noise [24]. Synthetic anomalous examples are shown in
the top part of Figure 1. Depending on the timestep used, anomalies are
generated at different transparency levels.

At inference, the current mask estimate $M_{t}$ used as input may be
inaccurate as it is output by the network at the previous timestep. To address
this uncertainty and improve robustness, $M$ is augmented so that its
anomalous regions become larger or smaller, thus not perfectly fitting the
synthetic anomalies in $I$. The augmented mask $M_{a}$ is obtained by
thresholding the Perlin noise map used for generating $M$ therefore reducing
or expanding the size of anomalies in $M$. $M$ is also dropped during training
in $25\%$ of training samples.

Figure 3: TransFusion inference. For every fourth timestep, the input image
$x_{t}$ and the predictions for the mask $M_{t}$, anomaly appearance
$\epsilon_{t}$ and normal appearance $n_{t}$ are shown. As seen in the top row
TransFusion first reconstructs larger anomalies and inpaints the details near
the end of the reconstruction process.

###  3.4 Inference

At inference, Figure 2, the starting mask estimate is initialized to all zero
values. Then, the reverse process of T time steps is performed. T is set to 20
in all experiments unless stated otherwise. At each time step $t$ the current
approximation of the reconstructed image $x_{t}$ is channel-wise concatenated
with the binarized previous mask estimate $M_{t+1}$ and positional encoding
$PE$. This composite input and the current timestep $t$ are fed into the
diffusion model. The model’s output consists of the current mask estimate
$M_{t}$, an anomaly appearance estimation $\epsilon_{t}$, and a normal
appearance estimation $n_{t}$ (Figure 2, bottom middle). Based on these
outputs, the next step $x_{t-1}$ is predicted using Eq. (4) (Figure 2, bottom
right). Anomaly mask $M_{t}$ is binarized by thresholding and used in the next
step. An example of the inference process is visualized in Figure 3. The
reverse process iteratively reduces the transparency of the anomalous regions,
progressively restoring the anomaly-free appearance of the image. At time step
0, the result is a fully reconstructed anomaly-free image $x_{0}$.

The final anomaly mask $M_{final}$ is derived from $M_{disc}$, the pixel-wise
mean of anomaly masks $M_{t}$, with $t$ going from $1$ to $T$, produced
throughout the reverse process and from $M_{recon}$, the reconstruction error
between the initial image $x$ and the diffusion model output $x_{0}$.

To obtain the final mask $M_{final}$, a weighted combination of $M_{disc}$ and
$M_{recon}$ is performed:

$M_{final}=(\lambda M_{disc}+(1-\lambda)M_{recon})*f_{n},$ (10)

where the influence of $M_{disc}$ and $M_{recon}$ is weighted by $\lambda$
($\lambda$=0.95 in all experiments), $f_{n}$ is a mean filter of size $n\times
n$ (in our case $7\times 7$) and $*$ is the convolution operator. The mean
filter smoothing is performed to aggregate the local anomaly map responses for
a robust image-level score estimation. The image-level anomaly score $AS$ is
obtained by the maximum value of $M_{final}$:

$AS=max(M_{final}).$ (11)

Including both $M_{disc}$ and $M_{recon}$ gives the final mask $M_{final}$ a
balanced anomaly representation allowing it to benefit from both
discriminative and reconstructive cues.

Method | AnoDDPM [37] | AnomDiff [22] | DiffAD [43] | DRÆM [40] | DSR [42] | FastFlow [39] | PatchCore [25] | RD4AD [11] | AST [27] | SimpleNet[21] | TransFusion
---|---|---|---|---|---|---|---|---|---|---|---
Candle | 64.9 | 81.0 | 90.4 | 94.4 |  98.8 | 96.4 | 98.1 | 92.2 |  99.4 | 95.6 |  98.3
Capsules | 76.5 | 80.0 | 87.6 | 76.3 |  99.1 | 89.2 | 85.7 |  90.1 | 85.4 | 76.7 |  99.6
Cashew | 94.4 | 90.9 | 81.4 | 90.7 |  97.6 | 95.2 |  98.5 |  99.6 | 95.1 | 91.7 | 93.7
Chewing gum | 91.3 | 98.1 | 94.0 | 94.2 | 93.8 | 99.4 | 99.0 |  99.7 |  100 | 99.1 |  99.6
Fryum | 81.5 | 89.2 | 87.1 | 97.4 | 82.9 |  98.8 | 97.2 | 96.6 |  99.1 | 95.3 |  98.3
Macaroni1 | 58.8 | 77.8 | 87.6 | 95.0 | 87.3 | 94.5 |  95.7 |  98.4 | 93.9 | 90.8 |  98.4
Macaroni2 | 74.5 | 61.0 | 90.7 |  96.2 | 83.4 | 81.7 | 78.1 |  97.6 | 72.1 | 65.2 |  96.5
PCB1 | 42.1 | 86.7 | 75.0 | 54.8 | 90.5 | 94.7 | 98.3 |  97.6 |  99.2 | 60.1 |  98.9
PCB2 | 90.7 | 76.5 | 94.6 | 77.8 | 96.6 | 96.0 |  97.2 | 91.1 |  98.4 | 93.3 |  99.7
PCB3 | 92.3 | 80.4 | 94.7 | 94.5 | 94.8 | 93.3 |  96.2 | 95.5 |  97.4 | 94.9 |  99.2
PCB4 | 98.3 | 93.8 | 97.7 | 93.4 | 93.5 | 97.8 |  99.0 | 96.5 |  99.6 | 98.2 |  99.6
Pipe fryum | 72.5 | 89.4 | 92.7 |  99.4 | 97.5 | 99.2 | 99.4 | 97.0 |  99.4 | 93.3 |  99.6
Average | 78.2 | 83.7 | 89.5 | 88.7 | 91.6 | 93.9 | 94.3 |  96.0 |  94.9 | 87.9 |  98.5

Table 1: Comparison of TransFusion in anomaly detection (AUROC) with SOTA on
VisA. First, second and third place are marked.

##  4 Experiments

Method | AnoDDPM [37] | AnomDiff [22] | DiffAD [43] | DRÆM [40] | DSR [42] | FastFlow [39] | PatchCore [25] | RD4AD [11] | AST [27] | SimpleNet[21] | TransFusion
---|---|---|---|---|---|---|---|---|---|---|---
Carpet | 93.5 |  99.9 | 98.3 | 97.0 |  100 |  100 | 98.7 | 95.3 | 99.1 | 97.5 | 99.2
Grid | 93.8 | 99.7 |  100 | 99.9 |  100 | 99.7 | 98.2 |  100 | 98.7 | 99.1 |  100
Leather | 99.5 |  100 |  100 |  100 |  100 |  100 |  100 | 97.1 |  100 |  100 |  100
Tile | 99.4 | 98.0 |  100 | 99.6 |  100 |  100 | 98.7 | 99.3 | 99.1 |  100 | 99.8
Wood | 99.0 | 98.1 |  100 | 99.1 | 96.3 |  100 | 99.2 | 99.2 | 99.2 |  100 | 99.4
Bottle | 98.4 | 99.3 |  100 | 99.2 |  100 |  100 |  100 |  100 |  100 |  100 |  100
Cable | 52.7 | 91.2 | 94.6 | 91.8 | 93.8 |  100 |  99.5 | 95.0 | 98.5 |  99.9 | 97.9
Capsule | 89.0 | 84.1 | 97.5 |  98.5 | 98.1 |  100 | 98.1 | 96.3 |  99.7 | 97.7 |  98.5
Hazelnut | 84.5 | 97.9 |  100 |  100 | 95.6 |  100 | 99.9 |  100 |  100 |  100 |  100
Metal nut | 92.8 | 99.2 | 99.5 | 98.7 | 98.5 |  100 |  100 |  100 | 98.5 |  100 |  100
Pill | 80.9 | 64.7 | 97.7 |  98.9 | 97.5 |  99.6 | 96.6 |  96.6 | 99.1 | 99.0 | 98.3
Screw | 20.3 | 89.9 | 97.2 | 93.9 | 96.2 | 97.8 |  98.1 | 97.0 |  99.7 |  98.2 | 97.2
Toothbrush | 86.4 | 96.9 |  100 |  100 | 99.7 | 94.4 |  100 | 90.8 | 96.6 | 99.7 |  100
Transistor | 65.0 | 92.3 | 96.1 | 93.1 | 97.8 | 98.8 |  100 | 96.7 |  99.3 |  100 | 98.3
Zipper | 98.2 | 85.5 |  100 |  100 |  100 | 99.5 | 99.4 | 98.5 | 99.1 | 99.5 |  100
Average | 83.5 | 93.1 | 98.7 | 98.0 | 98.2 |  99.4 | 99.1 | 98.5 |  99.2 |  99.6 |  99.2

Table 2: Comparison of TransFusion in anomaly detection (AUROC) with SOTA on MVTec AD. First, second and third place are marked. Method | Venue | VisA | MVTec AD | Average
---|---|---|---|---
Det. | Loc. | Det. | Loc. | Det. | Loc.
AnoDDPM | CVPRW’22 | 78.2 | 60.5 | 83.5 | 50.7 | 80.9 | 55.6
DRÆM | ICCV’21 | 88.7 | 73.1 | 98.0 | 92.8 | 93.3 | 83.0
SimpleNet | CVPR’23 | 87.9 | 68.9 | 99.6 | 89.6 | 93.8 | 79.3
DiffAD | ICCV’23 | 89.5 | 71.2 | 98.7 | 84.8 | 94.1 | 78.0
DSR | ECCV’22 | 91.6 | 68.1 | 98.2 | 90.8 | 94.9 | 79.5
FastFlow | ArXiv’21 | 93.9 | 86.9 | 99.4 | 92.5 | 96.7 | 89.7
Patchcore | CVPR’22 | 94.3 | 79.7 | 99.1 | 92.7 | 97.0 | 86.2
AST | WACV’23 | 94.9 | 81.5 | 99.2 | 81.2 | 97.1 | 81.4
RD4AD | CVPR’22 | 96.0 | 70.9 | 98.5 | 93.9 | 97.3 | 82.4
TransFusion | - | 98.5 | 88.8 | 99.2 | 94.3 | 98.9 | 91.6
Table 3: Results in anomaly detection (AUROC) and anomaly localization (AUPRO)
on both VisA and MVTec AD. First, second and third place are marked. Figure 4:
Qualitative comparison of the masks produced by TransFusion and three other
state-of-the-art methods. The anomalous images are shown in the first row. The
middle four rows show the anomaly mask generated by RD4AD [11], DRÆM [40],
Patchcore [25] and TransFusion respectively. The last row shows the ground
truth anomaly mask. Figure 5: Qualitative reconstruction results. TransFusion
better restores anomalies to their normal appearance and better preserves the
details in the normal regions than competing methods DRÆM [40] and DiffAD
[43]. A few of the larger differences are highlighted in red.

###  4.1 Datasets

Experiments are performed on two standard anomaly detection datasets: the VisA
dataset [45] and the MVTec AD dataset [8]. The VisA dataset is comprised of
10,821 images distributed across 12 object categories, while the MVTec AD
dataset contains 5,354 images encompassing 5 texture categories and 10 object
categories. Notably, both datasets provide pixel-level annotations for the
test images, enabling accurate evaluation and analysis. Compared to MVTec AD,
the VisA dataset has more near-in-distribution anomalies that have proven
challenging for recent anomaly detection methods. Consequently, this leads to
poorer results by recent methods on the VisA dataset compared to MVTec AD.

###  4.2 Evaluation metrics

Standard anomaly detection evaluation metrics are used. The image-level
anomaly detection performance is evaluated by the Area Under the Receiver
Operator Curve (AUROC), while for the pixel-level anomaly localization the
Area Under the Per Region Overlap (AUPRO) is utilized.

###  4.3 Implementation details

During both training and inference 20 steps ($T=20$) are used in the diffusion
process with a linear transparency ($\beta$) schedule ranging from 0 to 1. The
model was trained for 1500 epochs using the AdamW optimizer with a batch size
of 8. The learning rate was set to $10^{-5}$ and was multiplied by $0.1$ after
800 epochs. Synthetic anomalies were added to half of the training batch.
Rotation augmentation was used following DRÆM [40]. To ensure experimental
consistency, a standard preprocessing approach is employed. Each image is
resized to dimensions of $256\times 256$ and subsequently center-cropped to
$224\times 224$ following recent literature [25, 38, 21]. The image is then
linearly scaled between -1 and 1 following recent diffusion model literature
[14, 31]. Following the standard protocol, a separate model was trained for
each category and the same hyperparameters were set across both datasets and
all categories.

###  4.4 Experimental results

Anomaly detection results on VisA are shown in Table 1. TransFusion achieves
the best results on 6 out of the 12 categories and outperforms the previous
best state-of-the-art method by $2.5$ percentage points in terms of the mean
AUROC performance, reducing the error by $62.5\%$.

On the MVTec AD dataset, TransFusion achieves state-of-the-art results with a
mean anomaly detection AUROC of 99.2%. Results are shown in Table 2. While two
alternative approaches outperform TransFusion on the MVTec AD dataset, it is
noteworthy that the dataset has reached a high level of saturation, rendering
it challenging to display superior methodological improvements based solely on
performance on this dataset.

Due to the significant differences in anomaly types between the VisA and MVTec
AD datasets, very few recent methods exhibit the generalization capability
necessary to achieve top results for both datasets. Table 3 shows results on
both VisA and MVTec AD. Additionally, the average scores across both datasets
are shown. TransFusion outperforms all recent methods in terms of the average
anomaly detection AUROC by a significant margin of $1.6$ percentage points,
reducing the error by $60\%$.

TransFusion also achieves the highest score in anomaly localization when
averaged across both datasets, outperforming competing methods by $1.9$
percentage points. In terms of anomaly detection, TransFusion outpeforms
competing methods significantly on the VisA dataset and achieves state-of-the-
art performance on MVTec AD. TransFusion also outperforms other diffusion-
based methods AnoDDPM [37], DiffAD [43] and AnomDiff [22] by a significant
margin, which suggests that simply relying on a standard diffusion process for
reconstruction may not be sufficient for anomaly detection.

Group | Condition | VisA | MVTec AD
---|---|---|---
Det. | Loc. | Det. | Loc.
| w/o PE | -1.4 | -0.1 | -1.9 | -3.2
Input strategies | w/o Prev. Mask | -1.2 | -8.6 | -2.4 | -6.2
|  w/o $\mathcal{L}_{n}$ | -31.8 | -45.3 | -26.0 | -43.2
|  w/o $\mathcal{L}_{m}$ | -1.5 | -3.2 | -2.2 | -2.7
|  w/o $\mathcal{L}_{a}$ | -1.1 | -1.5 | -1.0 | -1.0
Loss Function |  w/o $\mathcal{L}_{c}$ | -0.9 | -0.3 | -0.7 | -0.8
|  Only $M_{1}$ | -1.5 | -0.3 | -1.4 | -2.6
|  Only $M_{disc}$ | -0.1 | +0.1 | -0.2 | +0.1
Final mask calc. |  Only $M_{recon}$ | -0.9 | -13.5 | -0.7 | -5.9
| 5 steps | -1.0 | -4.3 | -0.7 | -1.2
| 10 steps | -0.5 | -1.1 | -0.7 | -1.0
Diffusion step num. | 50 steps | -0.3 | +0.7 | -0.5 | -0.8
| Quadratic | -2.0 | +1.2 | -2.0 | +0.4
Transparency sched. | Root | -1.7 | -2.7 | -0.7 | -1.6
TransFusion | Linear, 20 steps | 98.5 | 88.8 | 99.2 | 94.3
Table 4: Ablation study results. Detection results are reported in AUROC and
localization results are reported in AUPRO. In each row the difference to the
actual model is shown. The highest discrepancy for each experiment group is
marked in blue.

###  4.5 Qualitative comparisons

A qualitative comparison with the state-of-the-art methods DRÆM [40], RD4AD
[11] and Patchcore [25] can be seen in Figure 4. Note that TransFusion outputs
very precise anomaly masks and does not produce significant false positives in
the background opposed to other state-of-the-art methods (Columns 5, 13, 14).
Due to being a discriminative network, TransFusion outputs masks (Columns
1-14) that are much sharper than those of Patchcore and RD4AD which output a
feature-based distance function and the feature reconstruction error,
respectively. DRÆM is unable to accurately detect small near-in-distribution
anomalies (Columns 3, 5, 6, 14) mostly present in the VisA [45] Dataset. We
hypothesize that this is due to the subpar reconstructive model of DRÆM.

TranFusion exhibits a strong reconstructive ability. A qualitative comparison
can be seen in Figure 5. Compared to DRÆM [40], TransFusion outputs higher-
quality reconstructions and even produces realistic results in difficult
reconstruction cases such as strong deformations, while maintaining fine-
grained details in normal regions. TransFusion better addresses the loss of
detail problem compared to previously proposed method DiffAD [43].

###  4.6 Ablation study

The results of the evaluation of individual components of TransFusion and it’s
training process are shown in Table 4.

Input strategies. In addition to the image $x_{t}$, the Positional Encoding
(PE) and the previous mask estimate are input during training. The impact of
PE and the mask estimate is evaluated by excluding each individually from the
architecture. Excluding PE leads to a $1.4$ percentage points (p. p.) drop on
VisA and a $1.9$ p. p. drop on MVTec AD. Excluding the mask estimate leads to
a $1.2$ p. p. drop on VisA and a $2.4$ p. p. drop on MVTec AD, showing the
benefit of an approximate mask guidance. There is also a significant drop
($8.6$ p. p. on VisA and $6.2$ p. p. on MVTec AD) in localization when
excluding the approximate mask highlighting its importance for precise
localization.

Importance of loss functions. The importance of each loss function was
evaluated by excluding one loss function at a time and training the model.
Removing $L_{a}$, $L_{c}$ or $L_{m}$ reduces the overall anomaly detection
performance by approximately $1$ p. p. on VisA and MVTec AD, demonstrating
their usefulness. Notably, removing $\mathcal{L}_{n}$ leads to a major drop in
performance ($31.8$ p. p. AUROC on VisA, $26$ p. p. AUROC on MVTec AD),
showing the necessity of learning a strong normal appearance model of the
object. Without $\mathcal{L}_{n}$, TransFusion may focus on learning the
synthetic anomaly appearance, leading to poor generalization.

Final mask calculation. The anomaly mask calculation methods using either only
the last mask estimate $M_{1}$, the discriminative mask $M_{disc}$, or the
reconstruction mask $M_{recon}$ are evaluated. Using only $M_{recon}$ leads to
a $0.9$ p. p. drop on VisA and a $0.7$ p. p. MVTec AD in terms of AUROC.
$M_{disc}$ can accurately localize the anomalies even without $M_{recon}$,
leading to only a $0.1$ and $0.2$ p. p. drop on VisA and MVTec AD,
respectively. The impact of mask averaging throughout the diffusion process is
significant, since using only the last estimated mask (Last Mask Est.) causes
a $1.5$ and $1.4$ p. p. drop in anomaly detection performance on the VisA and
MVTec AD, respectively.

Number of diffusion steps. The impact of the number of diffusion steps on the
anomaly detection performance is evaluated. Although a lower number of steps
leads to a poorer normal appearance restoration, TransFusion remains robust
across various time-step settings achieving similar results across both VisA
and MVTec AD, even achieving state-of-the-art results on VisA at only 5
timesteps. A higher number of diffusion steps also increases the result in
localization on VisA.

Transparency schedule. The impact of replacing the linear $\beta$ schedule
with alternative schedules is evaluated. The Root and the Quadratic schedule
are examined, where the $\beta$ values change from $0$ to $1$ using a
quadratic or a square-root function, respectively. Using a Quadratic schedule
causes a $2$ p. p. drop in performance on both VisA and MVTec AD. The Root
schedule leads to a $1.7$ and a $0.7$ p. p. drop on the VisA and the MVTec AD,
respectively. Interestingly, using a quadratic schedule improves anomaly
localization by a $1.2$ p. p. on VisA and a $0.4$ p. p. on MVTec AD.

Inference efficiency. Inference times of various methods can be seen in Table
5. Due to the complexity of diffusion models TransFusion is slower than some
competing methods, however it is faster than other diffusion-based methods.
Additionally, reducing the number of inference steps does not drastically
reduce performance (Table 4). Diffusion distillation is an active field [23,
29, 32] and may be helpful for speeding up diffusion-based anomaly detection
models.

Method | DRÆM [40] | Patchcore [25] | DiffAD [43] | TransFusion
---|---|---|---|---
Inference [s] |  0.05 |  0.22 | 1.00 |  0.34

Table 5: Results for average inference time of a single sample with NVIDIA
A100 GPU. Inference times are reported in seconds.

##  5 Conclusion

A novel, transparency-based diffusion process is proposed, where the
transparency of the anomalous regions is gradually increased, effectively
removing them, and restoring their normal appearance. TransFusion, a novel
discriminative anomaly detection method that implements the transparency-based
diffusion process is proposed. TransFusion is able to produce accurate
anomaly-free reconstructions of anomalies, while maintaining the appearance of
normal regions, thus addressing both the overgeneralization and loss-of-detail
problems of commonly used reconstructive methods. TransFusion achieves state-
of-the-art results in anomaly detection on the standard VisA and MVTec AD
datasets, achieving an AUROC of 98.5% and 99.2% for both datasets,
respectively. The versatility of TransFusion and its robustness to near-in-
distribution anomalies are further validated by the state-of-the-art
performance across both datasets, where TransFusion achieves 98.9% mean AUROC,
surpassing the previous state-of-the-art by a significant margin of 1.6
percentage points. The results indicate that custom diffusion processes
crafted specifically for surface anomaly detection are a promising direction
for future research.

## References

  * Akcay et al. [2018] Samet Akcay, Amir Atapour-Abarghouei, and Toby P Breckon.  GANomaly: Semi-supervised Anomaly Detection via Adversarial Training.  In _Asian conference on computer vision_ , pages 622–637. Springer, 2018.
  * Amit et al. [2021] Tomer Amit, Eliya Nachmani, Tal Shaharbany, and Lior Wolf.  SegDiff: Image Segmentation with Diffusion Probabilistic Models.  _arXiv preprint arXiv:2112.00390_ , 2021.
  * Austin et al. [2021] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg.  Structured denoising diffusion models in discrete state-spaces.  _Advances in Neural Information Processing Systems_ , 34:17981–17993, 2021.
  * Bansal et al. [2022] Arpit Bansal, Eitan Borgnia, Hong-Min Chu, Jie S Li, Hamid Kazemi, Furong Huang, Micah Goldblum, Jonas Geiping, and Tom Goldstein.  Cold diffusion: Inverting arbitrary image transforms without noise.  _arXiv preprint arXiv:2208.09392_ , 2022.
  * Bao et al. [2022] Fan Bao, Chongxuan Li, Yue Cao, and Jun Zhu.  All are Worth Words: a ViT Backbone for Score-based Diffusion Models.  In _NeurIPS 2022 Workshop on Score-Based Methods_ , 2022.
  * Bergmann et al. [2019] Paul Bergmann, Sindy Löwe, Michael Fauser, David Sattlegger, and Carsten Steger.  Improving Unsupervised Defect Segmentation by Applying Structural Similarity to Autoencoders.  In _Proceedings of the 14th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2019) - Volume 5: VISAPP_ , pages 372–380, 2019.
  * Bergmann et al. [2020] Paul Bergmann, Michael Fauser, David Sattlegger, and Carsten Steger.  Uninformed Students: Student-Teacher Anomaly Detection with Discriminative Latent Embeddings.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 4183–4192, 2020.
  * Bergmann et al. [2021] Paul Bergmann, Kilian Batzner, Michael Fauser, David Sattlegger, and Carsten Steger.  The MVTec Anomaly Detection Dataset: A Comprehensive Real-World Dataset for Unsupervised Anomaly Detection.  _International Journal of Computer Vision_ , 129(4):1038–1059, 2021.
  * Bergmann et al. [2022] Paul Bergmann, Kilian Batzner, Michael Fauser, David Sattlegger, and Carsten Steger.  Beyond Dents and Scratches: Logical Constraints in Unsupervised Anomaly Detection and Localization.  _International Journal of Computer Vision_ , 130(4):947–969, 2022.
  * Chen et al. [2022] Shoufa Chen, Peize Sun, Yibing Song, and Ping Luo.  DiffusionDet: Diffusion Model for Object Detection.  _arXiv preprint arXiv:2211.09788_ , 2022.
  * Deng and Li [2022] Hanqiu Deng and Xingyu Li.  Anomaly Detection via Reverse Distillation From One-Class Embedding.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 9737–9746, 2022.
  * Diakogiannis et al. [2020] Foivos I Diakogiannis, François Waldner, Peter Caccetta, and Chen Wu.  ResUNet-a: A deep learning framework for semantic segmentation of remotely sensed data.  _ISPRS Journal of Photogrammetry and Remote Sensing_ , 162:94–114, 2020.
  * Gudovskiy et al. [2022] Denis Gudovskiy, Shun Ishizaka, and Kazuki Kozuka.  CFLOW-AD: Real-Time Unsupervised Anomaly Detection with Localization via Conditional Normalizing Flows.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 98–107, 2022.
  * 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.
  * Huang et al. [2022] Rongjie Huang, Max WY Lam, Jun Wang, Dan Su, Dong Yu, Yi Ren, and Zhou Zhao.  FastDiff: A Fast Conditional Diffusion Model for High-Quality Speech Synthesis.  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22_. International Joint Conferences on Artificial Intelligence Organization, 2022.
  * Jang et al. [2023] JunKyu Jang, Eugene Hwang, and Sung-Hyuk Park.  N-Pad: Neighboring Pixel-Based Industrial Anomaly Detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , pages 4364–4373, 2023.
  * Kong et al. [2021] Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro.  DiffWave: A Versatile Diffusion Model for Audio Synthesis.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_ , 2021.
  * 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_ , pages 9664–9674, 2021.
  * Li et al. [2022] Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto.  Diffusion-LM Improves Controllable Text Generation.  In _Advances in Neural Information Processing Systems_ , pages 4328–4343, 2022.
  * Lin et al. [2020] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal Loss for Dense Object Detection.  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pages 318–327, 2020.
  * Liu et al. [2023] Zhikang Liu, Yiming Zhou, Yuansheng Xu, and Zilei Wang.  SimpleNet: A Simple Network for Image Anomaly Detection and Localization.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 20402–20411, 2023.
  * Lu et al. [2023] Fanbin Lu, Xufeng Yao, Chi-Wing Fu, and Jiaya Jia.  Removing anomalies as noises for industrial defect localization.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 16166–16175, 2023.
  * Meng et al. [2023] Chenlin Meng, Robin Rombach, Ruiqi Gao, Diederik Kingma, Stefano Ermon, Jonathan Ho, and Tim Salimans.  On distillation of guided diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14297–14306, 2023.
  * Perlin [1985] Ken Perlin.  An image synthesizer.  _ACM Siggraph Computer Graphics_ , 19(3):287–296, 1985.
  * Roth et al. [2022] Karsten Roth, Latha Pemula, Joaquin Zepeda, Bernhard Schölkopf, Thomas Brox, and Peter Gehler.  Towards Total Recall in Industrial Anomaly Detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14318–14328, 2022.
  * Rudolph et al. [2022] Marco Rudolph, Tom Wehrbein, Bodo Rosenhahn, and Bastian Wandt.  Fully Convolutional Cross-Scale-Flows for Image-based Defect Detection.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 1088–1097, 2022.
  * Rudolph et al. [2023] Marco Rudolph, Tom Wehrbein, Bodo Rosenhahn, and Bastian Wandt.  Asymmetric student-teacher networks for industrial anomaly detection.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pages 2592–2602, 2023.
  * Sakurada and Yairi [2014] Mayu Sakurada and Takehisa Yairi.  Anomaly Detection Using Autoencoders with Nonlinear Dimensionality Reduction.  In _Proceedings of the MLSDA 2014 2nd workshop on machine learning for sensory data analysis_ , pages 4–11, 2014.
  * Salimans and Ho [2022] Tim Salimans and Jonathan Ho.  Progressive distillation for fast sampling of diffusion models.  In _International Conference on Learning Representations_ , 2022.
  * Schlegl et al. [2019] Thomas Schlegl, Philipp Seeböck, Sebastian M Waldstein, Georg Langs, and Ursula Schmidt-Erfurth.  f-AnoGAN: Fast unsupervised anomaly detection with generative adversarial networks.  _Medical image analysis_ , 54:30–44, 2019.
  * Song et al. [2021] Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising Diffusion Implicit Models.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_ , 2021.
  * Song et al. [2023] Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever.  Consistency models.  In _Proceedings of the 40th International Conference on Machine Learning_. JMLR.org, 2023.
  * Tailanian et al. [2022] Matías Tailanian, Álvaro Pardo, and Pablo Musé.  U-Flow: A U-shaped Normalizing Flow for Anomaly Detection with Unsupervised Threshold.  _arXiv preprint arXiv:2211.12353_ , 2022.
  * Wang and Liu [2021] Zelun Wang and Jyh-Charn Liu.  Translating Math Formula Images to LaTeX Sequences Using Deep Neural Networks with Sequence-level Training.  _International Journal on Document Analysis and Recognition (IJDAR)_ , 24(1–2):63–75, 2021.
  * Wang et al. [2004] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli.  Image quality assessment: from error visibility to structural similarity.  _IEEE transactions on image processing_ , 13(4):600–612, 2004.
  * Wu et al. [2023] Junde Wu, RAO FU, Huihui Fang, Yu Zhang, Yehui Yang, Haoyi Xiong, Huiying Liu, and Yanwu Xu.  MedSegDiff: Medical Image Segmentation with Diffusion Probabilistic Model.  In _Medical Imaging with Deep Learning_ , 2023.
  * Wyatt et al. [2022] Julian Wyatt, Adam Leach, Sebastian M. Schmon, and Chris G. Willcocks.  AnoDDPM: Anomaly Detection With Denoising Diffusion Probabilistic Models Using Simplex Noise.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , pages 650–656, 2022.
  * Yang et al. [2023] Minghui Yang, Peng Wu, and Hui Feng.  MemSeg: A semi-supervised method for image surface defect detection using differences and commonalities.  _Engineering Applications of Artificial Intelligence_ , 119:105835, 2023.
  * Yu et al. [2021] Jiawei Yu, Ye Zheng, Xiang Wang, Wei Li, Yushuang Wu, Rui Zhao, and Liwei Wu.  FastFlow: Unsupervised Anomaly Detection and Localization via 2D Normalizing Flows.  _arXiv preprint arXiv:2111.07677_ , 2021.
  * Zavrtanik et al. [2021a] Vitjan Zavrtanik, Matej Kristan, and Danijel Skočaj.  DRAEM-A discriminatively trained reconstruction embedding for surface anomaly detection.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 8330–8339, 2021a.
  * Zavrtanik et al. [2021b] Vitjan Zavrtanik, Matej Kristan, and Danijel Skočaj.  Reconstruction by inpainting for visual anomaly detection.  _Pattern Recognition_ , 112:107706, 2021b.
  * Zavrtanik et al. [2022] Vitjan Zavrtanik, Matej Kristan, and Danijel Skočaj.  DSR–A dual subspace re-projection network for surface anomaly detection.  In _European Conference on Computer Vision_ , pages 539–554. Springer, 2022.
  * Zhang et al. [2023a] Xinyi Zhang, Naiqi Li, Jiawei Li, Tao Dai, Yong Jiang, and Shu-Tao Xia.  Unsupervised surface anomaly detection with diffusion probabilistic model.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 6782–6791, 2023a.
  * Zhang et al. [2023b] Xuan Zhang, Shiyu Li, Xi Li, Ping Huang, Jiulong Shan, and Ting Chen.  Destseg: Segmentation guided denoising student-teacher for anomaly detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3914–3923, 2023b.
  * Zou et al. [2022] Yang Zou, Jongheon Jeong, Latha Pemula, Dongqing Zhang, and Onkar Dabeer.  SPot-the-Difference Self-supervised Pre-training for Anomaly Detection and Segmentation.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXX_ , pages 392–408. Springer, 2022.


Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

CIKM-PAS’22: PRIVACY ALGORITHMS IN SYSTEMS (PAS) Workshop, Conference on
Information and Knowledge Management, October 21, 2022, CIKM-PAS

<EMAIL_ADDRESS>] [1] [1]<EMAIL_ADDRESS>] [1] [1]

[1]Corresponding author. [1]These authors contributed equally.

#  $k$-Means SubClustering: A Differentially Private Algorithm with Improved
Clustering Quality

Devvrat Joshi  Indian Institute of Technology Gandhinagar, India  Janvi
Thakkar

(2022)

###### Abstract

In today’s data-driven world, the sensitivity of information has been a
significant concern. With this data and additional information on the person’s
background, one can easily infer an individual’s private data. Many
differentially private iterative algorithms have been proposed in interactive
settings to protect an individual’s privacy from these inference attacks. The
existing approaches adapt the method to compute differentially private(DP)
centroids by iterative Llyod’s algorithm and perturbing the centroid with
various DP mechanisms. These DP mechanisms do not guarantee convergence of
differentially private iterative algorithms and degrade the quality of the
cluster. Thus, in this work, we further extend the previous work on
‘Differentially Private $k$-Means Clustering With Convergence Guarantee’ by
taking it as our baseline. The novelty of our approach is to sub-cluster the
clusters and then select the centroid which has a higher probability of moving
in the direction of the future centroid. At every Lloyd’s step, the centroids
are injected with the noise using the exponential DP mechanism. The results of
the experiments indicate that our approach outperforms the current state-of-
the-art method, i.e., the baseline algorithm, in terms of clustering quality
while maintaining the same differential privacy requirements. The clustering
quality significantly improved by 4.13 and 2.83 times than baseline for the
Wine and Breast$\\_$Cancer dataset, respectively.

###### keywords:

differential privacy $k$-means clustering convergence guarantee

##  1 Introduction

Achieving extraordinary results is dependent on the data on which the machine
learning models are trained. Data curators have a responsibility to provide
datasets such that the privacy of data is not compromised. However, attackers
use other public datasets to perform inference and adversarial attacks to get
information about an individual in the dataset. Differential privacy is a
potential technique for giving customers a mathematical guarantee of the
privacy of their data[1]. There are two fundamental settings in which
differential privacy is used on data: in interactive setting data curator
holds the data and returns the response based on the queries requested by
third parties; while in non-interactive setting the curator sanitized the data
before publishing[2].

Iterative clustering algorithms provide important insights about the dataset,
which helps in a large number of applications. They are prone to privacy
threats because they can reveal information about an individual with
additional knowledge. Existing approaches obtain the set of centroids using
Lloyd’s K-means algorithm, then perturb them with a differentially private
mechanism to add privacy [3]. In contrast to Lloyd’s K-means algorithm, which
guarantees convergence, these algorithms do not provide any convergence
guarantee. Getting differentially private centroids might not help in getting
quality inferences because of this non-convergence. We studied an existing
approach that provides this guarantee and converges in twice the number of
iterations to Lloyd’s algorithm while maintaining the same differential
privacy requirements as existing works [4] [5]. Their algorithm perturbs the
centroids in a random direction from the center of the cluster. However, this
lowers the quality of clustering, which is necessary for making inferences.

In this work, we propose a variant of the existing approach, which provides
better clustering quality while using the same privacy budget. We used the
intuition of Lloyd’s algorithm that the next centroid will move in the
direction where there is a higher number of data points. Finally, we give the
mathematical proof that our approach at any instance gives better clustering
quality than the existing approaches. We have tested our approach on
breat_cancer, wine, iris, and digits datasets. We were able to get a
significant improvement from the previous approach in terms of clustering
quality.

Interactive setting implies that the dataset is not disclosed to the user,
however, the data curator returns the response of each query received from the
user by manipulating it using DP strategy.

Our main contribution includes:

  1. 1.

We proposed SubClustering approach which has better clustering quality than
the baseline (which is the current SOTA in terms of clustering quality). For
the Wine and Breast$\\_$cancer dataset, the clustering quality improved by
4.13 and 2.83 times respectively.

  2. 2.

In addition to improving the clustering quality, our algorithm used same
privacy budget as that of the existing work.

##  2 Related Work

The concept of differential privacy has inspired a plethora of studies,
particularly in the area of differentially private k-means clustering
[6][7][8] in an interactive setting. The important mechanisms of DP in the
literature include: the Laplace mechanisms (LapDP) [9], the exponential
mechanisms (ExpDP) [10], and the sample and aggregate framework [11]. To
achieve differential privacy, many implementations included infusing Laplace
noise into each iteration of Lloyd’s algorithm. The proportion of noise added
was based on a fixed privacy budget. Some of the strategies for allocating
privacy budget included splitting the overall privacy budget uniformly to each
iteration [12]. However, this requires us to calculate the number of
iterations for the convergence, prior to the execution of algorithm, thus
increasing the computational cost. Further, researchers overcome this weakness
by allocating theoretically guaranteed optimal allocation method [6], but the
major assumption taken in this approach was that every cluster has the same
size, which does not align with the real-world datasets. In another work,
Mohan et al. [8] proposed GUPT, which uses Lloyd’s algorithm for local
clustering of each bucket where the items were uniformly sampled to different
buckets. The final result was the mean of locally sampled points in each
bucket with added Laplace noise. But, the clustering quality of GUPT was
unsatisfying because a large amount of noise was added in the aggregation
stage.

Based on the study of past literature on differentially private k-means
clustering, Zhigang et al. [3] concluded that convergence of an iterative
algorithm is important to the clustering quality. To solve this, they
introduced the concept of the convergent zone and orientation controller. With
the help of a convergent zone and orientation controller, they further create
a sampling zone for selecting a potential centroid for the $i^{th}$ iteration.
The approach iteratively adds noise with an exponential mechanism (ExpDP) by
using prior and future knowledge of the potential centroid at every step of
Lloyd’s algorithm. The approach maintains the same DP requirements as existing
literature, with guaranteed convergence and improvement in clustering quality.
However, their algorithm perturbs the centroids in a random direction from the
center of the cluster, degrading the quality of clustering. Thus, in this
work, we further build upon the approach and significantly improve the
clustering quality with the same epsilon privacy.

##  3 Preliminaries

The definitions used in this work are briefly discussed in this section. The
following is a formal definition of Differential Privacy:

Definition 1 ($\epsilon$-DP [9]). A randomised mechanism T is $\epsilon$\-
differentially private if for all neighbouring datasets $X$ and $X^{\prime}$
and for an arbitrary answer $s\in Range(T)$, T satisfies

$Pr[T(X)=s]\leq exp(\epsilon)\cdot Pr[T(X^{\prime})=s],$

where $\epsilon$ is the privacy budget.

Here, $X$ and $X^{\prime}$ differ by only one item. Smaller values of
$\epsilon$ imply a better privacy guarantee. It is because the difference
between the two neighboring datasets is reflected by the privacy budget. In
this work, we use the ExpDP and LapDP. In exponential DP for non-numeric
computation, they introduce the concept of scoring function $q(X,x)$, which
represents the effectiveness of the pair $(X,x)$. Here $X$ is the dataset and
$x$ is the response to the $q(X,x)$ on X.

The formal definition of Exponential DP mechanism is defined as follow:

Definition 2 (Exponential Mechanism [10]). Given a scoring function of a
dataset $X,q(X,x),$ which reflects the quality of query respond x. The
exponential mechanism T provides $\epsilon$-differential privacy, if
$T(X)=\\{Pr[x]\propto exp(\frac{\epsilon\cdot q(X,x)}{2\Delta q})\\},$ where
$\Delta q$ is the sensitivity of scoring function q(X,x), $\epsilon$ is the
privacy budget.

Definition 3 (Convergent & Sampling Zones[3]). A region whose points satisfies
the condition: { Node S:
$\|S-{S_{i}}^{(t)}\|<\|{S_{i}}^{(t-1)}-{S_{i}}^{(t)}\|$} is the convergent
zone. ${S_{i}}^{(t)}$ is defined as the mean of ${C_{i}}^{(t)}$. A sub-region
inside convergent zone is defined as a sampling zone.

Definition 4 (Orientation Controller[3]). ${X_{i}}^{(t)}$ is a direction from
the center of the convergent zone to a point on its circumference. This is the
direction along which the center of the sampling zone will be sampled, defined
as the orientation controller.

##  4 Approach

In this section, we explain our proposed approach and the baseline approach.

###  4.1 Overview - KMeans Guarantee (Baseline)

We took "Differentially Private K-Means Clustering with Convergence Guarantee"
[3] as our baseline and improved the clustering quality by further building on
it. The key concept of the algorithm is to use ExpDP to introduce bounded
noise into centroids at each iteration of Lloyd’s algorithm. The technique is
designed in a way that it ensures the new centroid is different from the
centroid of Lloyd’s algorithm while maintaining constraint given in Lemma 1.
The constraint guarantees that the perturbed centroid will eventually converge
with the centroid of Lloyd’s algorithm.

Their algorithm has four main steps to update the centroids at each Lloyd step
t [3]. The overview of their approach can be seen in (Figure : 1).

  1. 1.

Let the differentially private centroid at iteration $t-1$ for a cluster $i$
be $\hat{S_{i}}^{(t-1)}$. Using this centroid, run one iteration of Lloyd’s
algorithm to get the current Lloyd’s centroid ${S_{i}}^{(t)}$ for each cluster
$i$.

  2. 2.

Using ${S_{i}}^{(t)}$ and ${S_{i}}^{(t-1)}$, generate a convergent zone for
each cluster $i$ as described in $Definition\>3$.

  3. 3.

Generate a sampling zone in the convergence zone and an orientation controller
${X_{i}}^{(t)}$ for each cluster i as defined in $Definition\>3\>and\>4$
respectively.

  4. 4.

Sample a differentially private $\hat{S_{i}}^{(t)}$ with ExpDP in the sampling
zone generated in step 3.

The definition for the convergent zone (for convergence guarantee) and
sampling zone (for centroid updating) is defined in Definition 3.

1

Input: $\textbf{X}=\\{x_{1},x_{2},....,x_{N}\\}$: Dataset with N data points

k: number of clusters

$\epsilon^{exp}$: ExpDP privacy budget

$\epsilon^{lap}$: Laplacian privacy budget for the converged centroids.

$internalK$: number of sub-clusters per cluster

Output: S: Final clustering centroids

2 Select $k$ centroids
$\textbf{S}^{(0)}=({S}^{(0)}_{1},{S}^{(0)}_{2},...,{S}^{(0)}_{k})$ uniformly
from X.

3 $iterationForLloyd$ = number of iterations to run the algorithm.

4 for  _iters i in $iterationForLloyd$_ do

5 for  _each Cluster i at Iteration t_ do

6 ${{C}^{(t)}_{i}}\leftarrow$ assign each $x_{j}$ to its closest centroid
${S_{i}}^{t-1}$;

7 ${S_{i}}^{t}\leftarrow$ centroid of ${C_{i}}^{t}$;

8 ${ConvergentZone_{i}}^{(t)}\leftarrow$ List of data points inside the
spherical region having ${S_{i}}^{t}$ and ${S_{i}}^{t-1}$ as the endpoints of
its radius.

9 ${SamplingZone_{i}}^{(t)}\leftarrow$ run Algorithm 2 using
${ConvergentZone_{i}}^{(t)}$ , $internalK$;

10 $\hat{S_{i}}^{(t)}\leftarrow$ sample from ${SamplingZone_{i}}^{(t)}$ using
ExpDP with $q$ and $\epsilon^{exp}$;

11 ${S_{i}}^{(t)}\leftarrow$ $\hat{S_{i}}^{(t)}$

12

13Publish: ${SamplingZone_{i}}^{(t)}$, $q$, $\epsilon^{exp}$, ${S_{i}}^{(t)}$

14 $\textbf{S}\leftarrow$ add laplace noise with $\epsilon^{lap}$ to
${\textbf{S}}^{(t)}$;

Algorithm 1 Differentially Private $k-$Means SubClustering Algorithm

1

Input: ConvergentZone: Convergent Zone

internalK: Subclustering K

Output: $SamplingZone^{t}_{i}$

2 ${\textbf{S}}^{(t)}$: Mean of ${ConvergentZone_{i}}^{(t)}$

3 $\mathbf{ConvergentZoneClusters}\leftarrow$ Cluster ConvergentZone using
Lloyd’s algorithm and $internalK$

4 $\mathbf{ConvergentZoneProbability}\leftarrow$ Assign probabilities to the
$\mathbf{ConvergentZoneClusters}$ proportional to the number of points inside
each cluster.

5 $\mathbf{{SamplingZone_{i}}^{(t)}}\leftarrow$ Sample a cluster from the
$\mathbf{ConvergentZoneClusters}$ using $\mathbf{ConvergentZoneProbability}$

6

Return: $\mathbf{{SamplingZone_{i}}^{(t)}}$;

Algorithm 2 SubClusterSamplingAlgorithm Figure 1: Overview of KMeans Guarantee
Approach

###  4.2 Overview - SubCluster Guarantee

We build upon the KMeans Guarantee algorithm to achieve better clustering
quality. Our idea differs from the baseline in terms of creating a sampling
zone. For each cluster, we execute Lloyd’s algorithm over its convergent zone
to generate its sub-clustering. Further, we assign each sub-cluster with a
probability linearly proportional to the number of points it contains.
Finally, we sample the sub-cluster based on the assigned probability and
define it as the sampling zone of the convergent zone. Drawing analogy from
the KMeans Guarantee algorithm, our orientation controller is this sub-
clustering and sampling technique. Intuitively, our algorithm ensures that the
sampling zone lies towards the region containing a higher number of data
points in an expected case. With this, we guarantee that our differentially
private centroid moves in the direction where the number of data points is
higher, incorporating the intuition of Lloyd’s algorithm without compromising
on the $\epsilon$-differential privacy. The probability of a differentially
private centroid at $i-1^{th}$ iteration to move in the direction of a more
populated region at the $i^{th}$ step of Lloyd’s algorithm is also high. Thus,
we introduce the concept of sub-clustering in the convergent zone and
consequently sample one sub-cluster as our sampling zone.

Figure 2: Overview of SubCluster Guarantee Approach

We sample the centroid from the sampling zone using the ExpDP mechanism.
Finally, we inject Laplace noise in the centroids of the clustering when our
algorithm converges. It is because the differentially private centroids
obtained are a subset of one of the local minima at which Lloyd’s algorithm
converges. The overview of the proposed approach can be seen in (Figure : 2).
We show that a randomized iterative algorithm satisfies an invariant (given in
the claim of Lemma 1) and always converges (Proof: refer Lemma 1). Finally, we
show that the SubCluster algorithm is a randomized iterative algorithm that
satisfies the invariant(given in Lemma 1) (Proof: Refer Lemma 2).

We have four main steps to update the centroids at each Lloyd step t.

  1. 1.

Let the differentially private centroid at iteration $t-1$ for a cluster $i$
be $\hat{S_{i}}^{(t-1)}$. Using this centroid, run one iteration of Lloyd’s
algorithm to get the current Lloyd’s centroid ${S_{i}}^{(t)}$ for each cluster
$i$.

  2. 2.

Using ${S_{i}}^{(t)}$ and ${S_{i}}^{(t-1)}$, generate a convergent zone for
each cluster $i$ as described in $Definition\>3$.

  3. 3.

SubCluster the convergence zone and sample one of the sub-cluster as our
sampling zone based on the probability assigned to each sub-cluster. The
probability assignment is directly proportional to the number of points in
each sub-cluster.

  4. 4.

Sample a differentially private $\hat{S_{i}}^{(t)}$ with EXpDP in the sampling
zone generated in step 3.

Our approach surpasses the baseline approach in terms of clustering quality
while maintaining the same DP requirements as that of the KMeans Guarantee
approach, which is evident from the results obtained (Figure : 3). The better
clustering quality is a result of our sub-clustering strategy to perturb
centroid with a higher probability than the baseline approach towards the
direction of the actual centroid generated by Lloyd’s algorithm. The pseudo-
code of our approach is shown in the Algorithm 1 and Algorithm 2.

Figure 3: Above figures plots the graph between costGap and epsilon budget for
two approaches, the baseline as KmeansGuarantee and our approach
SubClusterGuarantee. The algorithm was tested on four dataset, Digits (top-
left), Wine (top-right), Breast Cancer (bottom-left), and Iris (bottom-right)
datasets. Figure 4: Above figures plots the graph between costGap and epsilon
budget for different internalK in SubClusterGuarantee Algorithm. The algorithm
was tested for internalK=2,3,4,5 for all the four datasets, Digits (top-left),
Wine (top-right), Breast Cancer (bottom-left), and Iris (bottom-right). Please
note: K and internalK are the same parameter

Lemma 1: [3] A randomised iterative algorithm $\tau$ is convergent if, in
${{C}^{(t)}_{i}}$(Cluster i at iteration t), $\hat{S_{i}}^{(t)}$(sampled
centroid using $\tau$), ${S_{i}}^{(t-1)}$(centroid before recentering) and
${S_{i}}^{(t)}$(centroid of ${{C}^{(t)}_{i}}$) satisfies the invariant,
$||\hat{S_{i}}^{(t)}-{S_{i}}^{(t)}||<||{S_{i}}^{(t)}-{S_{i}}^{(t-1)}||$ in
Euclidean distance, $\forall t$, $i$.

We reproduce this lemma from our baseline approach [3]. Lemma1 and Lemma 2
together provides the completeness and proof for the convergence of our
approach. If the distance between the sampled centroid ${\hat{S}^{(t)}_{i}}$
from the ${{C}^{(t)}_{i}}$ and the new centroid ${{S}^{(t)}_{i}}$ is less than
the distance between the new ${{S}^{(t)}_{i}}$ and the old centroid
${{S}^{(t-1)}_{i}}$, then the random iterative algorithm will always converge.
Intuitively, the loss of ${{C}^{(t)}_{i}}$ is minimum if the mean of
${{C}^{(t)}_{i}}$ is taken as centroid. But, if we slightly shift from the
mean of ${{C}^{(t)}_{i}}$, then the loss will increase. However, if we can
ensure that any sampled point from ${{C}^{(t)}_{i}}$ fulfills the condition:
$||\hat{S_{i}}^{(t)}-{S_{i}}^{(t)}||<||{S_{i}}^{(t)}-{S_{i}}^{(t-1)}||$, it
will lead to a lesser loss than ${{J^{S}}^{(t-1)}_{i}}$, thus, resulting into
convergence of the randomised iterative algorithm. For the mathematical proof,
refer [3].

Lemma 2: Differentially Private $k-$Means SubClustering approach
(SubClustering) is a randomised iterative algorithm that satisfies the
invariant
$||\hat{S_{i}}^{(t)}-{S_{i}}^{(t)}||<||{S_{i}}^{(t)}-{S_{i}}^{(t-1)}||$.
Proof: SubClustering is an iterative algorithm that samples a set of centroids
for each iteration with ExpDP mechanism, thus, making it a randomised
iterative algorithm. It subclusters the points lying inside
${ConvergentZone}^{(t)}_{i}$. After subclustering, it samples one subcluster
(sampling zone) with the assigned probabilities (linearly proportional to the
number of data points in subcluster). Finally, it samples a datapoint from the
sampled subcluster with ExpDP and call it as the centroid of
${ConvergentZone}^{(t)}_{i}$. Thus, our sampling zone always lies inside
${ConvergentZone}^{(t)}_{i}$. Therefore, the sampled point lies inside
${ConvergentZone}^{(t)}_{i}$ and it satisfies the invariant
$||\hat{S_{i}}^{(t)}-{S_{i}}^{(t)}||<||{S_{i}}^{(t)}-{S_{i}}^{(t-1)}||$.

##  5 Experimental Setup

###  5.1 Dataset Used

We used following four datasets to test our work SubCluster Guarantee upon the
baseline:

  1. 1.

Iris [13] dataset comprises total of 150 datapoints with four features and
three classes.

  2. 2.

Wine[13] dataset comprises total of 178 datapoints with 13 features and three
classes.

  3. 3.

Breast Cancer[13] dataset comprises total of 569 datapoints with 30 features
and two classes.

  4. 4.

Digits[13] dataset comprises of 1797 datapoints with 64 dimensions and 10
classes.

###  5.2 Metric for Clustering Quality

To evaluate the clustering quality, we used the following equation to
calculate the normalised difference between the differentially private
algorithms (here, SubCluster Guarantee approach) $(Cost_{DP})$ and Lloyd’s
algorithm $(Cost_{Lloyd})$:

$CostGap=\frac{|Cost_{DP}-Cost_{Lloyd}|}{Cost_{Lloyd}}$ (1)

The smaller CostGap [3] represents the better quality of clustering. In the
experiments, we compare the clustering quality of SubCluster Guarantee with
KMeans Guarantee.

##  6 Results and Discussion

We tested our algorithm on four datasets. All the datasets have different
dimensions ranging from 4 to 64 dimensions and training sets ranging from 150
to 1800. As defined in metric smaller gap represents the better clustering
quality. From the (Figure : 3) we can observe that, cost gap for all the
dataset is smaller or equal to the baseline. Thus, it is evident that our
algorithm has better clustering quality than the existing work for all the
datasets experimented. We varied internalK (parameter for number of sub-
clusters) from 2 to 5.

Each experiment was conducted 30 times in the case of the Iris, Wine, and
Breast cancer dataset and 10 times for digits dataset due to computational
constraints. Finally, for each dataset, we took the average of all the
experiments as our final result for plotting the graphs.

Comparing the SubCluster Guarantee (proposed approach) and K-means Guarantee
approach (baseline) by taking an average of all the cost gaps for varied
epsilon, and finally taking the ratio between K-means and SubCluster approach:

  1. 1.

In case of Iris dataset, the cost gap is 1.1 times smaller than baseline
algorithm.

  2. 2.

In case of Wine dataset, the cost gap is 4.13 times smaller than baseline
algorithm.

  3. 3.

In case of Breast$\\_$Cancer dataset, the cost gap is 2.83 times smaller than
baseline algorithm.

  4. 4.

In case of Digits dataset, the cost gap is almost same as that of baseline
algorithm.

###  6.1 Detailed Analysis

  1. 1.

Iris: Iris dataset has four dimensions and a very small training set of 150
data points. Our algorithm achieves better clustering quality than the
baseline algorithm for smaller epsilon values. Since the number of data points
is less in Iris, the impact of sub-clustering reduces, resulting in its
performance similar to that of the baseline approach. From (Figure : 4), we
can observe that changing the value of intenalK has a small impact on the
costGap due to a small number of points in each sub-cluster. This is because
there is a possibility that a sub-cluster has no data point when internalK is
increased causing zero probability sub-cluster regions.

  2. 2.

Wine: The wine dataset has 13 dimensions and 178 data points in the training
set. Our algorithm performs significantly better than the baseline, as
observed in (Figure : 3). It is because the baseline algorithm is constrained
to choose a theta in any abrupt direction ranging from
$\left[-\pi/2,\pi/2\right]$ as shown in (Figure : 1). In contrast, our
algorithm shifts the centroids in the direction where the future centroid of
Lloyd’s algorithm is more likely to move (in the expected case). From (Figure
: 4), it is evident that internalK=4 for the wine dataset performs better than
the rest of the internalK values. Here, the number of dimensions is more than
Iris. Therefore, the spatial arrangement will be in an n-sphere which allows
better sub-clustering.

  3. 3.

Breast$\\_$Cancer: Breast$\\_$Cancer dataset has 569 data points in its
training set and 30 dimensions. Our algorithm performs exceptionally better
than the baseline, with internalK equal to 4. From (Figure : 3), we can
observe that there is no monotonous trend for the costGap. Trends are visible
in other datasets due to the larger number of classification classes, whereas
this dataset has only two classes. Thus, adding Laplace noise does not have a
relation to the clustering quality. Increasing the internalK improves the
clustering quality, with internalK being 4 having the least loss. It is
because this dataset has a high number of dimensions and a larger number of
training points than other datasets.

  4. 4.

Digits: It has 64 dimensions and 1797 data points in the training dataset.
Although it has a large number of dimensions, our algorithm has a very small
improvement over the baseline algorithm as seen in (Figure : 3). Because of
the higher time complexity of our algorithm, it is hard to tune the internalK
parameter. As the number of samples in a dataset increases, the internalK
should increase because a single cluster can contain a large number of data
points. But, due to limited computational resources, we were not able to
experiment with it further. We took internalK to be 5 for our experiments as
it performed best in the range $\left[2,5\right]$ as in the (Figure : 4). One
of the intriguing findings in the dataset’s results is that the curves based
on the internalK have a clearly evident trend, which is a result of the large
number of training data points.

Our proposed algorithm significantly improves over the baseline in terms of
clustering quality, especially for the wine and breast cancer dataset. In
addition our algorithm maintains the same DP requirements as that of existing
works.

##  7 Conclusion

This work presents a novel method for improving the clustering quality of
differentially private k-means algorithms while ensuring convergence. The
novelty of our approach is the sub-clustering of the cluster to select the
differentially private centroid, which has a higher probability of moving in
the direction of the next centroid. We proved that our work surpasses the
current state-of-the-art algorithms in terms of clustering quality. Especially
for the Wine and Breast$\\_$Cancer dataset, the clustering quality was
significantly improved by 4.13 and 2.83 times than the baseline. In addition,
we maintain the same DP requirements as that of baseline and other existing
approaches.

##  8 Future Work

  * •

In this work, we proved our claim using empirical results. We further plan to
validate the results by providing mathematical bounds for the convergence
degree and rate of the SubClustering Lloyd’s algorithm. In terms of clustering
quality, the proposed algorithm in this work is compared with k-means
guarantee clustering only; to prove the effectiveness of our work, we plan to
experiment with other algorithms in the literature including, PrivGene [14],
GUPT [8] and DWork [7].

  * •

The DP requirements in this work are the same as that of past literature, but
in the future, we plan to explore ways to improve the current DP guarantees
while maintaining the same clustering quality as in this work.

  * •

We used Exponential and Laplace mechanisms of DP in the proposed approach; we
further plan to explore the third mechanisms, i.e., sample and aggregate
framework, by integrating it with the current algorithm.

  * •

In our algorithm, the number of data points inside a cluster is variable. Thus
we plan to choose an internalK, custom to the size of the cluster to improve
the clustering quality.

## Acknowledgement

We would like to thank Prof. Anirban Dasgupta (IIT Gandhinagar) for his
continuous support and guidance throughout the research.

## References

    * Dwork [2008] C. Dwork,  Differential privacy: A survey of results,  in: International conference on theory and applications of models of computation, Springer, 2008, pp. 1–19.
    * Narayanan [2009] A. Narayanan, Data privacy: The non-interactive setting, The University of Texas at Austin, 2009.
    * Lu and Shen [2020] Z. Lu, H. Shen,  Differentially private k-means clustering with convergence guarantee,  IEEE Transactions on Dependable and Secure Computing (2020).
    * Su et al. [2016] D. Su, J. Cao, N. Li, E. Bertino, H. Jin,  Differentially private k-means clustering,  in: Proceedings of the sixth ACM conference on data and application security and privacy, 2016, pp. 26–37.
    * Lei [2011] J. Lei,  Differentially private m-estimators,  Advances in Neural Information Processing Systems 24 (2011).
    * Su et al. [2017] D. Su, J. Cao, N. Li, E. Bertino, M. Lyu, H. Jin,  Differentially private k-means clustering and a hybrid approach to private optimization,  ACM Transactions on Privacy and Security (TOPS) 20 (2017) 1–33.
    * Dwork [2011] C. Dwork,  A firm foundation for private data analysis,  Communications of the ACM 54 (2011) 86–95.
    * Mohan et al. [2012] P. Mohan, A. Thakurta, E. Shi, D. Song, D. Culler,  Gupt: privacy preserving data analysis made easy,  in: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, 2012, pp. 349–360.
    * Dwork et al. [2006] C. Dwork, F. McSherry, K. Nissim, A. Smith,  Calibrating noise to sensitivity in private data analysis,  in: Theory of cryptography conference, Springer, 2006, pp. 265–284.
    * McSherry and Talwar [2007] F. McSherry, K. Talwar,  Mechanism design via differential privacy,  in: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), IEEE, 2007, pp. 94–103.
    * Nissim et al. [2007] K. Nissim, S. Raskhodnikova, A. Smith,  Smooth sensitivity and sampling in private data analysis,  in: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 75–84.
    * Blum et al. [2005] A. Blum, C. Dwork, F. McSherry, K. Nissim,  Practical privacy: the sulq framework,  in: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2005, pp. 128–138.
    * Asuncion [2007] A. Asuncion,  Uci machine learning repository, university of california, irvine, school of information and computer sciences,  http://www. ics. uci. edu/~ mlearn/MLRepository. html (2007).
    * Zhang et al. [2013] J. Zhang, X. Xiao, Y. Yang, Z. Zhang, M. Winslett,  Privgene: differentially private model fitting using genetic algorithms,  in: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013, pp. 665–676.