# Improving Faithfulness for Vision Transformers

Lijie Hu  , 1, 6, Yixin Liu *, 2, Ninghao Liu 3, Mengdi Huai 4, Lichao Sun2,
and Di Wang 1, 5, 6
1 King Abdullah University of Science and Technology, 2 Lehigh University
3 University of Georgia, 4 Iowa State University, 5 Computational Bioscience
Research Center
6 SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence
{lijie.hu<EMAIL_ADDRESS>{yila22<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>The first two authors contributed
equally to this work.

###### Abstract

Vision Transformers (ViTs) have achieved state-of-the-art performance for
various vision tasks. One reason behind the success lies in their ability to
provide plausible innate explanations for the behavior of neural
architectures. However, ViTs suffer from issues with explanation faithfulness,
as their focal points are fragile to adversarial attacks and can be easily
changed with even slight perturbations on the input image. In this paper, we
propose a rigorous approach to mitigate these issues by introducing Faithful
ViTs (FViTs). Briefly speaking, an FViT should have the following two
properties: (1) The top-$k$ indices of its self-attention vector should remain
mostly unchanged under input perturbation, indicating stable explanations; (2)
The prediction distribution should be robust to perturbations. To achieve
this, we propose a new method called Denoised Diffusion Smoothing (DDS), which
adopts randomized smoothing and diffusion-based denoising. We theoretically
prove that processing ViTs directly with DDS can turn them into FViTs. We also
show that Gaussian noise is nearly optimal for both $\ell_{2}$ and
$\ell_{\infty}$-norm cases. Finally, we demonstrate the effectiveness of our
approach through comprehensive experiments and evaluations. Specifically, we
compare our FViTs with other baselines through visual interpretation and
robustness accuracy under adversarial attacks. Results show that FViTs are
more robust against adversarial attacks while maintaining the explainability
of attention, indicating higher faithfulness.

##  1 Introduction

Transformers and attention-based frameworks have been widely adopted as
benchmarks for natural language processing tasks Kenton and Toutanova (2019);
Radford et al. (2019). Recently, their ideas also have been borrowed in many
computer vision tasks such as image recognition Dosovitskiy et al. (2021),
objective detection Zhu et al. (2021), image processing Chen et al. (2021) and
semantic segmentation Zheng et al. (2021). Among them, the most successful
variant is the vision transformer (ViT) Dosovitskiy et al. (2021), which uses
self-attention modules. Similar to tokens in the text domain, ViTs divide each
image into a sequence of patches (visual tokens), and then feed them into
self-attention layers to produce representations of correlations between
visual tokens. The success of these attention-based modules is not only
because of their good performance but also due to their “self-explanation”
characteristics. Unlike post-hoc interpretation methods Du et al. (2019),
attention weights can intrinsically provide the “inner-workings” of models
Meng et al. (2019), i.e., the entries in attention vector could point us to
the most relevant features of the input image for its prediction, and can also
provide visualization for “where” and “what” the attention focuses on Xu et
al. (2015).

As a crucial characteristic for explanation methods, faithfulness requires
that the explanation method reflects its reasoning process Jacovi and Goldberg
(2020). Therefore, for ViTs, their attention feature vectors should reveal
what is essential to their prediction. Furthermore, faithfulness encompasses
two properties: completeness and stability. Completeness means that the
explanation should cover all relevant factors or patches related to its
corresponding prediction Sundararajan et al. (2017), while stability ensures
that the explanation is consistent with humans understanding and robust to
slight perturbations. Based on these properties, we can conclude that
“faithful ViTs" (FViTs) should have the good robustness performance, and
certified explainability of attention maps which are robust against
perturbations.

Corrupted Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
|  |  |  |  |  |
|  |  |  |  |  |
Figure 1: Visualization results of the attention map on corrupted input for
different methods.

While the self-attention module in ViTs already possesses the property of
completeness, it often suffers from stability issues. For example, in language
tasks, Wiegreffe and Pinter (2019); Hu et al. (2022) have shown that attention
is not robust, as a slight perturbation on the embedding vector can cause the
attention vector distribution to change drastically. Similarly, for vision
tasks, we find that such a phenomenon is not uncommon for ViTs, where
attention modules are sensitive to perturbations on input images. For
instance, in Fig. 1, we can see that a slight perturbation on the input image
can cause the attention vector to focus on the wrong region for the image
class, leading to an incorrect interpretation heat map and, consequently,
confusing predictions. Actually, interpretation instability has also been
identified as a pervasive issue in deep learning Ghorbani et al. (2019), where
carefully-crafted small perturbations on the input can significantly change
the interpretation result. Thus, stability has become an important factor for
faithful interpretations. First, an unstable interpretation is prone to noise
interference, hindering users’ understanding of the underlying reasoning
behind model predictions. Second, instability undermines the reliability of
interpretation as a diagnostic tool for models Ghorbani et al. (2019);
Dombrowski et al. (2019); Yeh et al. (2019); Hu et al. (2022). Therefore, it
is crucial to mitigate the issue of unstable explanations in ViTs.

Although ViTs have shown to be more robust in predictions than convolutional
neural networks (CNNs) Bai et al. (2021); Paul and Chen (2022); Naseer et al.
(2021), whether they can provide faithful interpretations remains uncertain.
Compared to adversarial machine learning, which aims to enhance the robustness
of classification accuracy, mitigating the unstable explanation issue in ViTs
is more challenging. Here, we not only aim to improve the robustness of
prediction performance but also, more importantly, make the attention heat map
robust to perturbations. Therefore, a natural question arises: can we develop
provable and faithful variants of ViTs whose attention vectors and predictions
are robust to perturbations? In this paper, we provide an affirmative answer
to this question. Specifically, our contributions can be summarized as
follows.

1\. We propose a formal and mathematical definition for FViTs. Specifically,
an FViT must satisfy the following two properties for any input image: (1) It
must ensure that the top-$k$ indices of its attention feature vector remain
relatively stable with perturbations, indicating interpretability stability.
(2) However, attention vector stability alone cannot guarantee prediction
robustness for FViTs. Therefore, an FViT must also ensure that its prediction
distribution remains relatively stable under perturbations.

2\. We propose a method called Denoised Diffusion Smoothing (DDS) to obtain
FViTs. Surprisingly, we demonstrate that our DDS can directly transform ViTs
into FViTs. Briefly speaking, DDS involves two main components: (1) the
standard randomized smoothing with Gaussian noise and (2) a denoising
diffusion probabilistic model. It is worth noting that prior work on
randomized smoothing has focused on enhancing prediction robustness. In
contrast, we demonstrate that randomized smoothing can also enhance the
faithfulness of attention vectors in ViTs. Additionally, we demonstrate that
Gaussian noise is near-optimal for our method in both the $\ell_{2}$-norm and
$\ell_{\infty}$-norm cases.

3\. We conducted extensive experiments on three benchmark datasets using ViT,
DeiT, and Swin models to verify the above two properties of the FViTs as
claimed by our theories. Firstly, we demonstrate that our FViTs are more
robust to different types of perturbations than other baselines. Secondly, we
show the interpretability faithfulness of FViTs through visualization. Lastly,
we verify our certified faithful region as claimed by our theories. The
results reveal that our FViTs can provide provable faithful interpretations.

Due to space limitations, we have included details on theoretical proofs and
additional experimental results in the Appendix section.

##  2 Related Work

#### Interpretability for computer vision tasks.

Interpretation approaches in computer vision can be broadly categorized into
two classes according to the part of models they participated in: post-hoc
interpretation and self-explaining interpretation. Post-hoc interpretation
methods require post-processing the model after training to explain the
behaviors of black-box models. Typically, these methods either use surrogate
models to explain local predictions Ribeiro et al. (2016), or adopt gradient
perturbation methods Zeiler and Fergus (2014); Lundberg and Lee (2017) or
feature importance methods Ross et al. (2017); Selvaraju et al. (2017). While
post-hoc approaches require additional post-processing steps after the
training process, self-explaining interpretation methods could be considered
as integral parts of models, and they can generate explanations and make
predictions simultaneously Li et al. (2018); Abnar and Zuidema (2020). From
this view, ViTs can be considered as self-explaining interpretation
approaches, as they use attention feature vectors to quantify the
contributions of different tokens to their predictions.

#### Faithfulness in explainable methods.

Faithfulness is a crucial property that explanation models should satisfy,
ensuring that the explanation accurately reflects the true reasoning process
of the model Wiegreffe and Pinter (2019); Herman (2017); Jacovi and Goldberg
(2020); Lyu et al. (2022). Faithfulness is also related to other principles
such as sensitivity, implementation invariance, input invariance, and
completeness Yeh et al. (2019). Completeness refers to the explanation
comprehensively covering all relevant factors to the prediction Sundararajan
et al. (2017), while the other three terms are all related to the stability of
different kinds of perturbations. The explanation should change if heavily
perturbing the important features that influence the prediction Adebayo et al.
(2018), but be stable to small perturbations Yin et al. (2022). Thus,
stability is crucial to explanation faithfulness. Some preliminary work has
been proposed to obtain stable interpretations. For example, Yeh et al. (2019)
theoretically analyzes the stability of post-hoc interpretation and proposes
the use of smoothing to improve interpretation stability. Yin et al. (2022)
designs an iterative gradient descent algorithm to get a counterfactual
interpretation, which shows desirable stability. However, these techniques are
designed for post-hoc interpretation and cannot be directly applied to
attention-based mechanisms like ViTs.

#### Robustness for ViTs.

There is also a substantial body of work on achieving robustness for ViTs,
including studies such as Mahmood et al. (2021); Salman et al. (2022);
Aldahdooh et al. (2021); Naseer et al. (2021); Paul and Chen (2022); Mao et
al. (2022). However, these studies exclusively focus on improving the model’s
robustness in terms of its prediction, without considering the stability of
its interpretation (i.e., attention feature vector distribution). While we do
employ the randomized smoothing approach commonly used in adversarial machine
learning, our primary objective is to maintain the top-$k$ indices unchanged
under perturbations. And we introduce DDS, which leverages a smoothing-
diffusion process to obtain faithful ViTs while also enhancing prediction
performance.

##  3 Vanilla Vision Transformers

In this paper, we adopt the notation introduced in Zhou et al. (2022) to
describe ViTs. ViTs process an input image $x$ by first dividing it into $n$
uniform patches. Each patch is then represented as a token embedding, denoted
as $x_{i}\in\mathbb{R}^{q}$ for $i=1,\cdots,n$. The token embeddings are then
fed into a stack of transformer blocks, which use self-attention for token
mixing and MLPs for channel-wise feature transformation.

Token mixing. A ViT makes use of the self-attention mechanism to aggregate
global information. Given an input token embedding tensor
$X=[x_{1},\cdots,x_{n}]\in\mathbb{R}^{q\times n}$, self-attention applies
linear transformations with parameters $W_{K}$, $W_{Q}$, to embed $X$ into a
key $K=W_{K}X\in\mathbb{R}^{q\times n}$ and a query
$Q=W_{Q}X\in\mathbb{R}^{q\times n}$ respectively. The self-attention module
then calculates the attention matrix and aggregates the token features as
follows:

$Z^{\top}=\text{self-
attention}(X)=\text{softmax}(\frac{Q^{\top}K}{\sqrt{q}})V^{\top}W_{L},$ (1)

where $Z=[z_{1},\cdots,z_{n}]$ is the aggregated token feature,
$W_{L}\in\mathbb{R}^{q\times q}$ is a linear transformation, and $\sqrt{q}$ is
a scaling factor. The output of the self-attention is normalized with Layer-
norm and fed into an MLP to generate the input for the next block. At the
final layer, the ViT outputs a prediction vector. It is worth highlighting
that the self-attention mechanism can be viewed as a function that maps each
image $X\in\mathbb{R}^{q\times n}$ to an attention feature vector
$Z(X)\in\mathbb{R}^{n}$.

##  4 Towards Faithful Vision Transformers

As mentioned in the introduction, improving the stability and robustness of
the self-attention modules in ViTs is crucial for making them more faithful.
However, when it comes to explanation methods, it is not only important to
consider the robustness of the model’s prediction under perturbations but also
the sensitivity and stability of its explanation modules. Specifically, the
explanation modules should be sensitive enough to important token
perturbations while remaining stable under noise perturbations. As the
attention mechanism in ViTs outputs a vector indicating the importance of each
visual token, it is necessary to reconsider the robustness of both the
attention module and ViTs. In general, a faithful ViT should satisfy the
following two properties:

1\. The magnitude of each entry in the attention vector indicates the
importance of its associated patch. To ensure interpretability robustness, it
is sufficient to maintain the order of leading entries. We measure
interpretability robustness by computing the overlap of the top-$k$ indices
between the attention vector of the original input and the perturbed input,
where $k$ is a hyperparameter.

2\. The attention vector is fed to an MLP for prediction. In addition to the
robustness for top-$k$ indices, a robust attention vector should also preserve
the final model prediction. Specifically, we aim for the prediction
distribution based on the robust attention under perturbations is almost the
same as the distribution without perturbation. We measure the similarity or
closeness between these distributions using different divergences.

###  4.1 Motivation and Challenges

Motivation. Although some literature has addressed methods to improve the
robustness of ViTs, to the best of our knowledge, this is the first paper to
propose a solution that enhances the faithfulness of ViTs while providing
provable FViTs. Our work fills a gap in addressing both the robustness and
interpretability of ViTs, as demonstrated through both theoretical analysis
and empirical experiments.

Why stability of attention vectors’ top-k indices cannot imply the robustness
of prediction? While ensuring the stability of the top-$k$ indices of the
attention vectors is crucial for interpretability, it does not necessarily
guarantee the robustness of the final prediction. This is because the
stability of the prediction is also dependent on the magnitude of the entries
associated with the top-$k$ indices. For instance, consider the vectors
$v_{1}=(0.1,0.2,0.5,0.7)$ and $v_{2}=(0.2,0.8,0.9,2)$, which have the same top
indices. However, the difference in their magnitudes can significantly affect
the final prediction. Therefore, in addition to ensuring the stability of the
top-$k$ indices, an FViT should also meet the requirement that its prediction
distribution remains relatively unchanged under perturbations to achieve
robustness.

Technical Challenges. The technical challenges of this paper are twofold.
First, we need to give a definition of FViTs which contains the conditions
that can quantify the stability of both the attention vectors and the model
prediction under perturbations. This is challenging because we need to balance
the sensitivity and stability of the explanation modules, and also consider
the trade-off between interpretability and utility. Addressing these technical
challenges is critical to achieving the main objective of this paper, which is
to provide faithful ViTs. Second, we need to design an efficient and effective
algorithm to generate noise to preserve the robustness and interpretability of
ViTs. This is challenging because standard noise methods may cause significant
changes to the attention maps, which could lead to inaccurate and misleading
explanations. To tackle this challenge, we introduce a mathematically-proven
approach for noise generation and leverage denoised diffusion to balance the
utility and interpretability trade-off, which is non-trivial and provable.
Also, this study is the first to demonstrate its effectiveness in enhancing
explanation faithfulness, providing rigorous proof, and certifying the
faithfulness of ViTs.

###  4.2 Definition of FViTs

In the following, we will mathematically formulate our above intuitions.
Before that, we first give the definition of the top-$k$ overlap ratio for two
vectors.

######  Definition 4.1.

For vector $x\in\mathbb{R}^{n}$, we define the set of top-$k$ component
$T_{k}(\cdot)$ as

$T_{k}(x)=\\{i:i\in[d]\text{ and }\\{|\\{x_{j}\geq x_{i}:j\in[n]\\}|\leq
k\\}\\}.$

And for two vectors $x$, $x^{\prime}$, their top-$k$ overlap ratio
$V_{k}(x,x^{\prime})$ is defined as
$V_{k}(x,x^{\prime})=\frac{1}{k}|T_{k}(x)\cap T_{k}(x^{\prime})|.$

######  Definition 4.2 (Faithful ViTs).

We call a function $f:\mathbb{R}^{q\times n}\mapsto\mathbb{R}^{n}$ is an
$(R,D,\gamma,\beta,k,\|\cdot\|)$- faithful attention module for ViTs if for
any given input data $\bm{x}$ and for all $x^{\prime}\in\mathbb{R}^{q\times
n}$ such that $\|x-x^{\prime}\|\leq R$, $f(x^{\prime})$ satisfies

1\. (Top-$k$ Robustness) $V_{k}(f(x^{\prime}),f(x))\geq\beta$.

2\. (Prediction Robustness) $D(\bar{y}(x),\bar{y}(x^{\prime}))\leq\gamma$,
where $\bar{y}(x),\bar{y}(x^{\prime})$ are the prediction distribution of ViTs
based on $f(x),f(x^{\prime})$ respectively.

We also call the vector $f(x)$ as an $(R,D,\gamma,\beta,k,\|\cdot\|)$-
faithful attention for $x$, and the models of ViTs based on $f$ as  faithful
ViTs (FViTs).

We can see there are several terms in the above definition. Specifically, $R$
represents the faithful radius which measures the faithful region; $D$ is a
metric of the similarity between two distributions which could be a distance
or a divergence; $\gamma$ measures the closeness of the two prediction
distributions; $0<\beta<1$ is the robustness of top-$k$ indices; $\|\cdot\|$
is some norm. When $\gamma$ is smaller or $\beta$ is larger, then the
attention module will be more robust, and thus will be more faithful. In this
paper, we will focus on the case where divergence $D$ is the Rényi divergence
and $\|\cdot\|$ is either the $\ell_{2}$-norm or the $\ell_{\infty}$-norm (if
we consider $x$ as a $d=q\times n$ dimensional vector), as we can show if the
prediction distribution is robust under Rényi divergence, then the prediction
will be unchanged with perturbations on input Li et al. (2019).

######  Definition 4.3.

Given two probability distributions $P$ and $Q$, and $\alpha\in(1,\infty)$,
the $\alpha$-Rényi divergence $D_{\alpha}(P||Q)$ is defined as
$D_{\alpha}(P||Q)=\frac{1}{\alpha-1}\log\mathbb{E}_{x\sim
Q}(\frac{P(x)}{Q(x)})^{\alpha}$.

######  Theorem 4.4.

If a function is a $(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|)$-faithful
attention module for ViTs, then if

$\gamma\leq-\log(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}}),$

we have for all $x^{\prime}$ such that where $\|x-x^{\prime}\|\leq R$,
$\arg\max_{g\in\mathcal{G}}\mathbb{P}(\bar{y}(x)=g)=\arg\max_{g\in\mathcal{G}}\mathbb{P}(\bar{y}(x^{\prime})=g)$,
where $\mathcal{G}$ is the set of classes, $p_{(1)}$ and $p_{(2)}$ refer to
the largest and the second largest probabilities in $\\{p_{i}\\}$, where
$p_{i}$ is the probability that $\bar{y}(x)$ returns the $i$-th class.

##  5 Finding Faithful Vision Transformers

###  5.1 $\ell_{2}$-norm Case

In the previous section, we introduced faithful attention and FViTs, now we
want to design algorithms to find such a faithful attention module. We notice
that in faithful attention, the condition of prediction robustness is quite
close to adversarial machine training which aims to design classifiers that
are robust against perturbations on inputs. Thus, a natural idea is to borrow
the approaches in adversarial machine training to see whether they can get
faithful attention modules. Surprisingly, we find that using randomized
smoothing to the vanilla ViT, which is a standard method for certified
robustness Cohen et al. (2019), and then applying a denoised diffusion
probabilistic model Ho et al. (2020) to the perturbed input can adjust it to
an FViT. And its corresponding attention module becomes a faithful attention
module. Specifically, for a given input image $x$, we preprocess it by adding
some randomized Gaussian noise, i.e., $\tilde{x}=x+z$ with
$z\sim\mathcal{N}(0,\sigma^{2}I_{q\times n})$. Then we will denoise
$\tilde{x}$ via some denoised diffusion model to get $\hat{x}$, and feed the
perturbed-then-denoised $\hat{x}$ to the self-attention module $Z$ in (1) and
process to later parts of the original ViT to get the prediction. Thus, in
total, we can represent the attention module as $\tilde{w}(x)=Z(T(x+z))$,
where $T$ represents the denoised diffusion method. Here we mainly adopt the
denoising diffusion probabilistic model in Nichol and Dhariwal (2021); Ho et
al. (2020); Carlini et al. (2023), which leverages off-the-shelf diffusion
models as image denoiser. Specifically, it has the following steps after we
add Gaussian noise to $x$ and get $\tilde{x}$.

In the first step, we establish a connection between the noise models utilized
in randomized smoothing and diffusion models. Specifically, while randomized
smoothing augments data points with additive Gaussian noise i.e.,
$x_{\mathrm{rs}}\sim\mathcal{N}(x,\sigma^{2}\mathbf{I})$, diffusion models
rely on a noise model of the form
$x_{t}\sim\mathcal{N}(\sqrt{\alpha_{t}}x,(1-\alpha_{t})\mathbf{I})$, where the
factor $\alpha_{t}$ is a constant derived from the timestamp $t$. To employ a
diffusion model for randomized smoothing, DDS scales $x_{\mathrm{rs}}$ by
$\sqrt{\alpha_{t}}$ and adjusts the variances to obtain the relationship
$\sigma^{2}=\frac{1-\alpha_{t}}{\alpha_{t}}$. The formula for this equation
may vary depending on the schedule of the $\alpha_{t}$ terms employed by the
diffusion model, but it can be calculated in closed form.

Using this calculated timestep, we can then compute
$x_{t^{\star}}=\sqrt{\alpha_{t^{\star}}}(x+\delta)$, where
$\delta\sim\mathcal{N}(0,\sigma^{2}\mathbf{I})$, and apply a diffusion
denoiser on $x_{t^{\star}}$ to obtain an estimate of the denoised sample,
$\hat{x}=\texttt{denoise}(x_{t^{\star}};t^{\star})$. To further enhance the
robustness, we repeat this denoising process multiple times (e.g., 100,000).
The details of our method, namely Denoised Diffusion Smoothing (DDS), are
shown in Algorithm 1 in Appendix.

In the following, we will show $\tilde{w}$ is a faithful attention module.
Before showing the results, we first provide some notations. For input image
$x$, we denote $\tilde{w}_{i^{*}}$ as the $i$-th largest component in
$\tilde{w}(x)$. Let $k_{0}=\lfloor(1-\beta)k\rfloor+1$ as the minimum number
of changes on $\tilde{w}(x)$ to make it violet the $\beta$-top-$k$ overlapping
ratio with $\tilde{w}(x)$. Let $\mathcal{S}$ denote the set of last $k_{0}$
components in top-$k$ indices and the top $k_{0}$ components out of top-$k$
indices.

######  Theorem 5.1.

Consider the function $\tilde{w}$ where $\tilde{w}(x)=Z(T(x+z))$ with $Z$ in
(1), $T$ as the denoised diffusion model and
$z\sim\mathcal{N}(0,\sigma^{2}I_{q\times n})$. Then it is an
$(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|_{2})$-faithful attention module for
ViTs for any $\alpha>1$ if for any input image $x$ we have

$\displaystyle\sigma^{2}$ $\displaystyle\geq\max\\{{\alpha
R^{2}}/2(\frac{\alpha}{\alpha-1}\ln(2k_{0}(\sum_{i\in\mathcal{S}}\tilde{w}^{\alpha}_{i^{*}})^{\frac{1}{\alpha}}+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i^{*}})-\frac{1}{\alpha-1}\ln(2k_{0})),{\alpha
R^{2}}/2\gamma\\}.$

Theorem 5.1 indicates that $\tilde{w}(x)$ will be faithful attention for input
$x$ when $\sigma^{2}$ is large enough. Equivalently, based on Theorem 5.1 and
4.4 we can also find a faithful region given $\beta$ and $k$. Note that in
practice it is hard to determine the specific $\alpha$ in Rényi divergence.
Thus, we can take the supreme w.r.t all $\alpha>1$ in finding the faithful
region. See Algorithm 2 in Appendix for details.

We have shown that adding some Gaussian noise to the original data could get
faithful attention through the original attention module. A natural question
is whether adding Gaussian noise can be further improved by using other kinds
of noise. Below we show that Gaussian noise is already near optimal for
certifying a faithful attention module via randomized smoothing.

######  Theorem 5.2.

Consider any function $\tilde{w}:\mathbb{R}^{q\times n}\mapsto\mathbb{R}^{n}$
where $\tilde{w}(x)=Z(T(x+z))$ with some random noise $z$, $T$ as the denoised
diffusion model and $Z$ in (1). Then if it is an
$(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|_{2})$-faithful attention module for
ViTs with sufficiently large $\alpha$ and $\mathbb{E}[\|z\|_{\max}]\leq\tau$
holds for sufficiently small $\tau=O(1)$. Then it must be true that
$\tau\geq\Omega(\frac{\sqrt{\alpha}R}{\sqrt{\gamma}})$. Here for an matrix
$z\in\mathbb{R}^{q\times n}$, $\|z\|_{\max}$ is defined as
$\max_{i\in[q],j\in[n]}\|z_{i,j}\|$ is the maximal magnitude among all the
entries in $z$.

Note that in Theorem 5.1 we can see when $\gamma$ is small enough then
$\tilde{w}$ will be a $(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|_{2})$-faithful
attention module if $z\sim\mathcal{N}(0,\sigma^{2}I_{q\times n})$ with
$\sigma=\frac{\alpha R^{2}}{2\gamma}$. In this case we can see
$\mathbb{E}\|z\|_{\max}=O(\frac{\log{(q\cdot
n)}\sqrt{\alpha}R}{\sqrt{\gamma}})$. Thus, the Gaussian noise is optimal up to
some logarithmic factors.

###  5.2 $\ell_{\infty}$-norm Case

Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
Cat: clean$\rightarrow$ Cat: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Dog: clean$\rightarrow$ Dog: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Figure 2:  Class-specific explanation heat map visualizations under
adversarial corruption. For each image, we present results for two different
classes. Other baselines either give inconsistent interpretations or show
wrong focus class regions under adversarial perturbations. While our method
gives a consistent interpretation map and is robust against adversarial
attacks.

In this section we consider the $\ell_{\infty}$-norm instead of the
$\ell_{2}$-norm. Surprisingly, we show that using the same method as above, we
can still get a faithful attention module. Moreover, the Gaussian noise is
still near-optimal.

######  Theorem 5.3.

Consider the function $\tilde{w}$ where $\tilde{w}(x)=Z(T(x+z))$ with $Z$ in
(1), $T$ as the denoised diffusion model and
$z\sim\mathcal{N}(0,\sigma^{2}I_{q\times n})$. Then it is an
$(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|_{\infty})$-faithful attention module
for ViTs for $\alpha>1$ if for any input image $x$ we have the following,
where $d=q\cdot n$.

$\displaystyle\sigma^{2}$ $\displaystyle\geq\max\\{{d\alpha
R^{2}}/2(\frac{\alpha}{\alpha-1}\ln(2k_{0}(\sum_{i\in\mathcal{S}}\tilde{w}^{\alpha}_{i^{*}})^{\frac{1}{\alpha}}+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i^{*}})-\frac{1}{\alpha-1}\ln(2k_{0})),{d\alpha
R^{2}}/2\gamma\\}.$

Compared with the result in Theorem 5.1 for the $\ell_{2}$-norm case, we can
see there is the additional factor of $d$ in the bound of the noise. This
means if we aim to achieve the same faithful level as in the $\ell_{2}$-norm
case, then in the $\ell_{\infty}$-norm case we need to enlarge the noise by a
factor of $d$. Equivalently, if we add the same scale of noise, then the
faithful region for $\ell_{\infty}$-norm will be shrunk by a factor of $d$ of
the region for $\ell_{2}$-norm. See Algorithm 2 for details.

######  Theorem 5.4.

Consider any function $\tilde{w}:\mathbb{R}^{q\times n}\mapsto\mathbb{R}^{n}$
where $\tilde{w}(x)=Z(T(x+z))$ with some random noise $z$ and $Z$ in (1). Then
if it is an $(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|_{\infty})$-faithful
attention module for ViTs with sufficiently large $\alpha$ and
$\mathbb{E}[\|z\|_{\max}]\leq\tau$ holds for sufficiently small $\tau\leq
O(1)$. Then it must be true that
$\tau\geq\Omega(\frac{\sqrt{\alpha}R}{\sqrt{d\gamma}})$.

Theorem 5.1 we can see when $\gamma$ is small enough then $\tilde{w}$ will an
$(R,D_{\alpha},\gamma,\beta,k,\|\cdot\|_{\infty})$-faithful attention module
if $z\sim\mathcal{N}(0,\sigma^{2}I_{q\times n})$ with $\sigma=\frac{d\alpha
R^{2}}{2\gamma}$. In this case we can see
$\mathbb{E}\|z\|_{\max}=O(\frac{\log{(q\cdot
n)}\sqrt{d\alpha}R}{\sqrt{\gamma}})$. Thus, the Gaussian noise is optimal up
to some logarithmic factors.

Model | Method | ImageNet | Cityscape | COCO
---|---|---|---|---
Cla. Acc. | Pix. Acc. | mIoU | mAP | Pix. Acc. | mIoU | Pix. Acc. | mIoU
ViT | Raw Attention | 0.78 | 0.65 | 0.54 | 0.82 | 0.72 | 0.62 | 0.8 | 0.7
Rollout | 0.79 | 0.67 | 0.56 | 0.84 | 0.74 | 0.64 | 0.82 | 0.72
GradCAM | 0.8 | 0.69 | 0.58 | 0.86 | 0.76 | 0.66 | 0.84 | 0.74
LRP | 0.81 | 0.71 | 0.6 | 0.88 | 0.78 | 0.68 | 0.86 | 0.76
VTA | 0.82 | 0.73 | 0.62 | 0.9 | 0.8 | 0.7 | 0.88 | 0.78
Ours | 0.85 | 0.76 | 0.65 | 0.93 | 0.83 | 0.73 | 0.91 | 0.81
DeiT | Raw Attention | 0.79 | 0.66 | 0.55 | 0.83 | 0.73 | 0.63 | 0.81 | 0.71
Rollout | 0.8 | 0.68 | 0.57 | 0.85 | 0.75 | 0.65 | 0.83 | 0.73
GradCAM | 0.81 | 0.7 | 0.59 | 0.87 | 0.77 | 0.67 | 0.85 | 0.75
LRP | 0.82 | 0.72 | 0.61 | 0.89 | 0.79 | 0.69 | 0.87 | 0.77
VTA | 0.83 | 0.74 | 0.63 | 0.91 | 0.81 | 0.71 | 0.89 | 0.79
Ours | 0.86 | 0.77 | 0.66 | 0.94 | 0.84 | 0.74 | 0.89 | 0.79
Swin | Raw Attention | 0.8 | 0.67 | 0.56 | 0.84 | 0.74 | 0.64 | 0.82 | 0.72
Rollout | 0.81 | 0.69 | 0.58 | 0.86 | 0.76 | 0.66 | 0.84 | 0.74
GradCAM | 0.82 | 0.71 | 0.6 | 0.88 | 0.78 | 0.68 | 0.86 | 0.76
LRP | 0.83 | 0.73 | 0.62 | 0.9 | 0.8 | 0.7 | 0.88 | 0.78
VTA | 0.84 | 0.75 | 0.64 | 0.92 | 0.82 | 0.72 | 0.9 | 0.8
Ours | 0.87 | 0.78 | 0.67 | 0.95 | 0.85 | 0.75 | 0.93 | 0.83

Table 1:  Performance comparison of different methods on ImageNet, Cityscape,
and COCO using three different ViT-based models under the default attack.

##  6 Experiments

In this section, we present experimental results on evaluating the
interpretability and utility of our FViTs on various datasets and tasks. More
detailed implementation setup and additional experiments are in Appendix.

###  6.1 Experimental Setup

Datasets, tasks and network architectures. We consider two different tasks:
classification and segmentation. For the classification task, we use
ILSVRC-2012 ImageNet. And for segmentation, we use ImageNet-segmentation
subset Guillaumin et al. (2014), COCO Lin et al. (2014), and Cityscape Cordts
et al. (2016). To demonstrate our method is architectures-agnostic, we use
three different ViT-based models, including Vanilla ViT Dosovitskiy et al.
(2021), DeiT Touvron et al. (2021), and Swin ViT Liu et al. (2021).

Threat model. We focus on $l_{2}$-norm bounded and $l_{\infty}$-norm bounded
noises under a white-box threat model assumption for adversarial
perturbations. The radius of adversarial noise $\rho_{u}$ was set as $8/255$
by default. We employ the PGD Madry et al. (2017) algorithm to craft
adversarial examples with a step size of $2/255$ and a total of $10$ steps.

Baselines and attention map backbone. Since our DDS method can be used as a
plugin to provide certified faithfulness for interpretability under
adversarial attacks, regardless of the method used to generate attention maps.
We set the standard deviation $\delta=8/255$ for the Gaussian noise in our
method as default. In this paper, we leverage Trans. Att. Chefer et al. (2021)
as our explanation tool, which is a state-of-the-art method for generating
class-aware interpretable attention maps. Several methods aim to improve the
interpretability of attention maps, we include five baselines for comparison,
including Raw Attention Vaswani et al. (2017), Rollout Abnar and Zuidema
(2020), GradCAM Selvaraju et al. (2017), LRP Binder et al. (2016), and Vanilla
Trans. Att. (VTA) Chefer et al. (2021).

Evaluation metrics. To demonstrate the utility of our approach, we report the
classification accuracy on test data for classification tasks. As for the
interpretability of our approach, we seek to evaluate the explanation map by
leveraging the label of segmentation task as ‘ground truth’ following Chefer
et al. (2021). To be specific, we compare the explanation map with the ground
truth segmentation map. We measure the interpretability using pixel accuracy,
mean intersection over union (mIoU) Varghese et al. (2020), and mean average
precision (mAP) Henderson and Ferrari (2017). Note that pixel accuracy is
calculated by thresholding the visualization by the mean value, while mAP uses
the soft-segmentation to generate a score that is not affected by the
threshold. Following conventional practices, we also report the results for
negative and positive perturbation (pixels-erasing) tests Chefer et al.
(2021). The area-under-the-curve (AUC) measured by erasing between $10\%-90\%$
of the pixels is used to indicate the performance of explanation methods for
both perturbations. For negative perturbation, a higher AUC indicates a more
faithful interpretation since a good explanation should maintain accuracy
after removing unrelated pixels (also referred to as input invariance
Kindermans et al. (2019)). On the other hand, for positive perturbations, we
expect to see a steep decrease in performance after removing the pixels that
are identified as important, where a lower AUC indicates the interpretation is
better. We term the AUC of such perturbation tests as P-AUC. Furthermore, to
ensure fair comparisons, we plot the P-AUC-radius curve under adversarial
perturbations with a wide range of radii.

(a) Pos. Perturbation

(b) Neg. Perturbation

(c) Sens. Diff. Radius

Figure 3: (a) and (b) are results of the perturbation test. (c) is the
sensitivity analysis results.

###  6.2 Evaluating Interpretability and Utility

Classification and segmentation results. Based on the results shown in Table
1, it is obvious that our method is more robust and effective for all three
datasets. Moreover, across all metrics, our method consistently outperforms
other methods for all model architectures. For example, on ImageNet, our
method achieves the highest classification accuracy (0.85) and pixel accuracy
(0.76) for the ViT model and the highest mean IoU (0.66) and mean AP (0.94)
for the DeiT model. These results suggest that our method could even
outperform the previous methods on accuracy, and it is more faithful in
identifying the most relevant features for image classification under
malicious adversarial attacks compared to other methods. Please refer to Table
4 and 7 in the Appendix for complete results across different levels of
perturbation.

Additionally, Figure 4,6, and7 in Appendix demonstrate visual comparisons of
our method with baselines under adversarial attacks. It is clear that the
baseline methods produce inconsistent results, while our method produces more
consistent and clear visualizations even under data corruption. Moreover, as
shown in Figure 2 (more results are in Appendix Figure 5 and 9), when
analyzing images with two objects from different classes under adversarial
perturbations, all previous methods produce similar but worse visualizations
for each class. Surprisingly, our method is able to provide accurate and
distinct visualization maps for each class despite adversarial perturbations.
This indicates that our method is more faithful which is robust class-aware
under attacks.

Perturbation tests. The results on Pos. perturbation in Figure 3(a) show that
the P-AUC of our method consistently achieves the lowest value when we perform
attacks with a radius ranging from $0/255$ to $32/255$, which suggests that
our method are more faithful and interpretable. Similarly, as for Neg.
perturbation, the results in Figure 3(b) also suggest that our method is more
robust than other baselines when removing unrelated pixels, and indicate that
our method can identify important pixels under corruptions.

Ablation study. The results are shown in Table 2 of the Appendix highlighting
the crucial role that the denoising diffusion model and randomized smoothing
play in the effectiveness of DDS. As we can see from the table, removing
either of the components leads to a significant decrease in performance (under
adversarial attacks) across all three evaluation metrics: classification
accuracy, segmentation accuracy, and P-AUC. In particular, the classification
and segmentation accuracy will decrease by 3.1% when the denoising step is
removed, and by 1.3% and 1.5%, respectively when the randomized smoothing is
eliminated. Moreover, we visualized the ablated version of our method in
Figure 8. It is noteworthy that the performance degradation becomes more
pronounced when both components are removed, compared to when only a single
component is removed. This suggests that these two components are highly
effective in improving the faithfulness of model prediction and explanation.

Sensitivity analysis. To evaluate the sensitivity of standard deviation
$\delta$ of the added Gaussian noise, we conduct adversarial attacks on the
ImageNet dataset with different $\delta$ for a certain number of data samples.
We conduct testing under
$\delta\in\left\\{4/255,6/255,8/255,10/255,12/255\right\\}$ and attack radius
$\rho_{a}\in\left\\{0,2/255,4/255,6/255,8/255,10/255\right\\}$. The results in
Figure 3(c) suggest that, for the cases of $\delta=4/255$ and $\delta=6/255$,
compared to the vanilla baseline, i.e., without any processing of images, our
method is able to prevent the testing accuracy from dropping significantly as
the attack radius increase. However, we find that larger $\delta$ does not
significantly decrease test accuracy when $\delta$ exceeds some threshold
($\delta=8/255-12/255$). These results suggest that our method is sensitive to
the selection of $\delta$ when $\delta$ is small, and it becomes insensitive
when $\delta$ is larger. Nevertheless, across different $\delta$, our method
outperforms the baseline in terms of utility.

| Classification | Segementation | Perturbation Tests
---|---|---|---
Rob. Acc. (%) | Rob. Acc. (%) | mIOU | Pos. P-AUC | Neg. P-AUC
Ours | 99.5 | 97.8 | 0.985 | 15.29 | 63.23
$-$smoothing | 98.2 | 96.3 | 0.977 | 18.51 | 54.65
$-$denosing | 96.4 | 94.7 | 0.965 | 21.36 | 50.53
$-$both | 92.1 | 90.5 | 0.947 | 38.13 | 48.58

Table 2: Results of the ablation study on classification, segmentation, and
perturbation tests.

Verifying faithful region. To verify the proposed faithful region estimation
in Algorithm 2, we conduct an adversarial attack using projected gradient
descent on our denoised smoothing classifier following Cohen et al. (2019).
Given the faithful region radius $R(\delta)=\min\\{P(\delta),Q(\delta)\\}$
obtained in Algorithm 2, we attempt to find an adversarial example for our
denoised smoothing classifier within radii of $1.5R$ or $2R$, under the
condition that the example has been correctly classified within faithful
region $R$. We succeed in finding such adversarial examples 23% of the time at
a radius $1.5R$ and 64% of the time in a radius $2R$ on the ImageNet. These
results empirically demonstrate the tightness of our proposed faithful bound.

###  6.3 Computational Cost

Our denoising algorithm is actually quite fast, for example, under the noise
level of $\frac{8}{255}$, in each denoising trail, it only requires one
forward step in adding a random Gaussian noise and $t^{*}=45$ backward steps
for denoising, which empirically takes about 0.32 seconds per images (256x256)
on ImageNet 3. This shows that our methods are efficient and promising for
real-world applications with large-scale data.

$||\delta||_{\infty}$ | 2/255 | 4/255 | 8/255 | 12/255 | 16/255
---|---|---|---|---|---
$t^{*}$ | 0 | 8 | 45 | 107 | 193
Total Time(s) | 0.60 | 3.18 | 3.20 | 3.25 | 3.33
Per Sample(s) | 0.060 | 0.318 | 0.320 | 0.325 | 0.333

Table 3: The time cost of denoising under different noise levels with a total
sample size of 10.

##  7 Conclusion

We proposed Faithful Vision Transformers (FViTs) to certify faithfulness in
vanilla ViTs. We first gave a rigorous definition for FViTs. Then we proposed
a method namely DDS, and theoretically proved that DDS can achieve robustness
for both explainability and prediction. And this study is the first to
demonstrate its effectiveness in enhancing explanation faithfulness, providing
rigorous proofs, and certifying the faithfulness of ViTs. Finally, we showed
faithfulness in FViTs via comprehensive experiments.

## References

  * Kenton and Toutanova (2019) Kenton, J. D. M.-W. C.; Toutanova, L. K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. Proceedings of NAACL-HLT. 2019; pp 4171–4186.
  * Radford et al. (2019) Radford, A.; Wu, J.; Child, R.; Luan, D.; Amodei, D.; Sutskever, I.; others Language models are unsupervised multitask learners. _OpenAI blog_ 2019, _1_ , 9.
  * Dosovitskiy et al. (2021) Dosovitskiy, A.; Beyer, L.; Kolesnikov, A.; Weissenborn, D.; Zhai, X.; Unterthiner, T.; Dehghani, M.; Minderer, M.; Heigold, G.; Gelly, S.; Uszkoreit, J.; Houlsby, N. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. International Conference on Learning Representations. 2021.
  * Zhu et al. (2021) Zhu, X.; Su, W.; Lu, L.; Li, B.; Wang, X.; Dai J F, D. D. Deformable transformers for end-to-end object detection. Proceedings of the 9th International Conference on Learning Representations. Virtual Event, Austria: OpenReview. net. 2021.
  * Chen et al. (2021) Chen, H.; Wang, Y.; Guo, T.; Xu, C.; Deng, Y.; Liu, Z.; Ma, S.; Xu, C.; Xu, C.; Gao, W. Pre-trained image processing transformer. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021; pp 12299–12310.
  * Zheng et al. (2021) Zheng, S.; Lu, J.; Zhao, H.; Zhu, X.; Luo, Z.; Wang, Y.; Fu, Y.; Feng, J.; Xiang, T.; Torr, P. H.; others Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021; pp 6881–6890.
  * Du et al. (2019) Du, M.; Liu, N.; Hu, X. Techniques for interpretable machine learning. _Communications of the ACM_ 2019, _63_ , 68–77.
  * Meng et al. (2019) Meng, L.; Zhao, B.; Chang, B.; Huang, G.; Sun, W.; Tung, F.; Sigal, L. Interpretable spatio-temporal attention for video action recognition. Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops. 2019; pp 0–0.
  * Xu et al. (2015) Xu, K.; Ba, J.; Kiros, R.; Cho, K.; Courville, A.; Salakhudinov, R.; Zemel, R.; Bengio, Y. Show, attend and tell: Neural image caption generation with visual attention. International conference on machine learning. 2015; pp 2048–2057.
  * Jacovi and Goldberg (2020) Jacovi, A.; Goldberg, Y. Towards Faithfully Interpretable NLP Systems: How Should We Define and Evaluate Faithfulness? Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020; pp 4198–4205.
  * Sundararajan et al. (2017) Sundararajan, M.; Taly, A.; Yan, Q. Axiomatic attribution for deep networks. International conference on machine learning. 2017; pp 3319–3328.
  * Wiegreffe and Pinter (2019) Wiegreffe, S.; Pinter, Y. Attention is not not Explanation. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019; pp 11–20.
  * Hu et al. (2022) Hu, L.; Liu, Y.; Liu, N.; Huai, M.; Sun, L.; Wang, D. SEAT: Stable and Explainable Attention. _arXiv preprint arXiv:2211.13290_ 2022,
  * Ghorbani et al. (2019) Ghorbani, A.; Abid, A.; Zou, J. Interpretation of neural networks is fragile. Proceedings of the AAAI conference on artificial intelligence. 2019; pp 3681–3688.
  * Dombrowski et al. (2019) Dombrowski, A.-K.; Alber, M.; Anders, C.; Ackermann, M.; Müller, K.-R.; Kessel, P. Explanations can be manipulated and geometry is to blame. _Advances in Neural Information Processing Systems_ 2019, _32_.
  * Yeh et al. (2019) Yeh, C.-K.; Hsieh, C.-Y.; Suggala, A.; Inouye, D. I.; Ravikumar, P. K. On the (in) fidelity and sensitivity of explanations. _Advances in Neural Information Processing Systems_ 2019, _32_.
  * Bai et al. (2021) Bai, Y.; Mei, J.; Yuille, A. L.; Xie, C. Are Transformers more robust than CNNs? _Advances in Neural Information Processing Systems_ 2021, _34_ , 26831–26843.
  * Paul and Chen (2022) Paul, S.; Chen, P.-Y. Vision transformers are robust learners. Proceedings of the AAAI Conference on Artificial Intelligence. 2022; pp 2071–2081.
  * Naseer et al. (2021) Naseer, M. M.; Ranasinghe, K.; Khan, S. H.; Hayat, M.; Shahbaz Khan, F.; Yang, M.-H. Intriguing properties of vision transformers. _Advances in Neural Information Processing Systems_ 2021, _34_ , 23296–23308.
  * Ribeiro et al. (2016) Ribeiro, M. T.; Singh, S.; Guestrin, C. " Why should i trust you?" Explaining the predictions of any classifier. Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 2016; pp 1135–1144.
  * Zeiler and Fergus (2014) Zeiler, M. D.; Fergus, R. Visualizing and understanding convolutional networks. European conference on computer vision. 2014; pp 818–833.
  * Lundberg and Lee (2017) Lundberg, S. M.; Lee, S.-I. A unified approach to interpreting model predictions. _Advances in neural information processing systems_ 2017, _30_.
  * Ross et al. (2017) Ross, A. S.; Hughes, M. C.; Doshi-Velez, F. Right for the Right Reasons: Training Differentiable Models by Constraining their Explanations. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17. 2017; pp 2662–2670.
  * Selvaraju et al. (2017) Selvaraju, R. R.; Cogswell, M.; Das, A.; Vedantam, R.; Parikh, D.; Batra, D. Grad-cam: Visual explanations from deep networks via gradient-based localization. Proceedings of the IEEE international conference on computer vision. 2017; pp 618–626.
  * Li et al. (2018) Li, K.; Wu, Z.; Peng, K.-C.; Ernst, J.; Fu, Y. Tell me where to look: Guided attention inference network. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018; pp 9215–9223.
  * Abnar and Zuidema (2020) Abnar, S.; Zuidema, W. Quantifying attention flow in transformers. _arXiv preprint arXiv:2005.00928_ 2020,
  * Herman (2017) Herman, B. The promise and peril of human evaluation for model interpretability. _arXiv preprint arXiv:1711.07414_ 2017,
  * Lyu et al. (2022) Lyu, Q.; Apidianaki, M.; Callison-Burch, C. Towards Faithful Model Explanation in NLP: A Survey. _arXiv preprint arXiv:2209.11326_ 2022,
  * Adebayo et al. (2018) Adebayo, J.; Gilmer, J.; Muelly, M.; Goodfellow, I.; Hardt, M.; Kim, B. Sanity checks for saliency maps. _Advances in neural information processing systems_ 2018, _31_.
  * Yin et al. (2022) Yin, F.; Shi, Z.; Hsieh, C.-J.; Chang, K.-W. On the Sensitivity and Stability of Model Interpretations in NLP. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022; pp 2631–2647.
  * Mahmood et al. (2021) Mahmood, K.; Mahmood, R.; Van Dijk, M. On the robustness of vision transformers to adversarial examples. Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021; pp 7838–7847.
  * Salman et al. (2022) Salman, H.; Jain, S.; Wong, E.; Madry, A. Certified patch robustness via smoothed vision transformers. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022; pp 15137–15147.
  * Aldahdooh et al. (2021) Aldahdooh, A.; Hamidouche, W.; Deforges, O. Reveal of vision transformers robustness against adversarial attacks. _arXiv preprint arXiv:2106.03734_ 2021,
  * Mao et al. (2022) Mao, X.; Qi, G.; Chen, Y.; Li, X.; Duan, R.; Ye, S.; He, Y.; Xue, H. Towards robust vision transformer. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022; pp 12042–12051.
  * Zhou et al. (2022) Zhou, D.; Yu, Z.; Xie, E.; Xiao, C.; Anandkumar, A.; Feng, J.; Alvarez, J. M. Understanding the robustness in vision transformers. International Conference on Machine Learning. 2022; pp 27378–27394.
  * Li et al. (2019) Li, B.; Chen, C.; Wang, W.; Carin, L. Certified Adversarial Robustness with Additive Noise. Advances in Neural Information Processing Systems. 2019; pp 9459–9469.
  * Cohen et al. (2019) Cohen, J.; Rosenfeld, E.; Kolter, Z. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning. 2019; pp 1310–1320.
  * Ho et al. (2020) Ho, J.; Jain, A.; Abbeel, P. Denoising diffusion probabilistic models. _Advances in Neural Information Processing Systems_ 2020, _33_ , 6840–6851.
  * Nichol and Dhariwal (2021) Nichol, A. Q.; Dhariwal, P. Improved denoising diffusion probabilistic models. International Conference on Machine Learning. 2021; pp 8162–8171.
  * Carlini et al. (2023) Carlini, N.; Tramer, F.; Dvijotham, K. D.; Rice, L.; Sun, M.; Kolter, J. Z. (Certified!!) Adversarial Robustness for Free! The Eleventh International Conference on Learning Representations. 2023.
  * Guillaumin et al. (2014) Guillaumin, M.; Küttel, D.; Ferrari, V. Imagenet auto-annotation with segmentation propagation. _International Journal of Computer Vision_ 2014, _110_ , 328–348.
  * Lin et al. (2014) Lin, T.-Y.; Maire, M.; Belongie, S.; Hays, J.; Perona, P.; Ramanan, D.; Dollár, P.; Zitnick, C. L. Microsoft coco: Common objects in context. European conference on computer vision. 2014; pp 740–755.
  * Cordts et al. (2016) Cordts, M.; Omran, M.; Ramos, S.; Rehfeld, T.; Enzweiler, M.; Benenson, R.; Franke, U.; Roth, S.; Schiele, B. The cityscapes dataset for semantic urban scene understanding. Proceedings of the IEEE conference on computer vision and pattern recognition. 2016; pp 3213–3223.
  * Touvron et al. (2021) Touvron, H.; Cord, M.; Douze, M.; Massa, F.; Sablayrolles, A.; Jégou, H. Training data-efficient image transformers & distillation through attention. International Conference on Machine Learning. 2021; pp 10347–10357.
  * Liu et al. (2021) Liu, Z.; Lin, Y.; Cao, Y.; Hu, H.; Wei, Y.; Zhang, Z.; Lin, S.; Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021; pp 10012–10022.
  * Madry et al. (2017) Madry, A.; Makelov, A.; Schmidt, L.; Tsipras, D.; Vladu, A. Towards deep learning models resistant to adversarial attacks. _arXiv preprint arXiv:1706.06083_ 2017,
  * Chefer et al. (2021) Chefer, H.; Gur, S.; Wolf, L. Transformer interpretability beyond attention visualization. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021; pp 782–791.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; Polosukhin, I. Attention is all you need. _Advances in neural information processing systems_ 2017, _30_.
  * Binder et al. (2016) Binder, A.; Montavon, G.; Lapuschkin, S.; Müller, K.-R.; Samek, W. Layer-wise relevance propagation for neural networks with local renormalization layers. International Conference on Artificial Neural Networks. 2016; pp 63–71.
  * Varghese et al. (2020) Varghese, S.; Bayzidi, Y.; Bar, A.; Kapoor, N.; Lahiri, S.; Schneider, J. D.; Schmidt, N. M.; Schlicht, P.; Huger, F.; Fingscheidt, T. Unsupervised temporal consistency metric for video segmentation in highly-automated driving. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. 2020; pp 336–337.
  * Henderson and Ferrari (2017) Henderson, P.; Ferrari, V. End-to-end training of object class detectors for mean average precision. Asian conference on computer vision. 2017; pp 198–213.
  * Kindermans et al. (2019) Kindermans, P.-J.; Hooker, S.; Adebayo, J.; Alber, M.; Schütt, K. T.; Dähne, S.; Erhan, D.; Kim, B. _Explainable AI: Interpreting, Explaining and Visualizing Deep Learning_ ; Springer, 2019; pp 267–280.
  * Liu et al. (2021) Liu, A.; Chen, X.; Liu, S.; Xia, L.; Gan, C. Certifiably Robust Interpretation via Renyi Differential Privacy. _arXiv preprint arXiv:2107.01561_ 2021,
  * Dwork et al. (2006) Dwork, C.; McSherry, F.; Nissim, K.; Smith, A. Calibrating noise to sensitivity in private data analysis. Theory of cryptography conference. 2006; pp 265–284.
  * Mironov (2017) Mironov, I. Rényi differential privacy. 2017 IEEE 30th computer security foundations symposium (CSF). 2017; pp 263–275.
  * Steinke and Ullman (2016) Steinke, T.; Ullman, J. Between Pure and Approximate Differential Privacy. _Journal of Privacy and Confidentiality_ 2016, _7_.
  * Chen et al. (2018) Chen, J.; Song, L.; Wainwright, M. J.; Jordan, M. I. L-shapley and c-shapley: Efficient model interpretation for structured data. _arXiv preprint arXiv:1808.02610_ 2018,
  * Lee-Thorp et al. (2021) Lee-Thorp, J.; Ainslie, J.; Eckstein, I.; Ontanon, S. Fnet: Mixing tokens with fourier transforms. _arXiv preprint arXiv:2105.03824_ 2021,
  * Bach et al. (2015) Bach, S.; Binder, A.; Montavon, G.; Klauschen, F.; Müller, K.-R.; Samek, W. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. _PloS one_ 2015, _10_ , e0130140.
  * Montavon et al. (2017) Montavon, G.; Lapuschkin, S.; Binder, A.; Samek, W.; Müller, K.-R. Explaining nonlinear classification decisions with deep taylor decomposition. _Pattern recognition_ 2017, _65_ , 211–222.
  * (61) Jacobgil Jacobgil/VIT-explain: Explainability for Vision Transformers. https://github.com/jacobgil/vit-explain.

##  Appendix A Algorithms

Algorithm 1 FViTs via Denoised Diffusion Smoothing

1: Input: $x$; A standard deviation $\sigma>0$.

2: $t^{*}$, find $t$ s.t. $\frac{1-\alpha_{t}}{\alpha_{t}}=\sigma^{2}$.

3:
$x_{t^{*}}=\sqrt{\alpha_{t^{*}}}(\tilde{x}+\mathcal{N}(0,\sigma^{2}\textbf{I}))$.

4: $\hat{x}=\text{denoise}(x_{t^{*}};t^{*})$.

5: $w=\text{self-attention}(\hat{x})$.

6: Return: attention weight $w$.

Algorithm 2 Finding the Faithfulness Region in FViTs

1: Input: Original self-attention module $Z$; the standard deviation
$\sigma>0$; classifier of the original ViT $\bar{y}$; Number of repetitions
$m$. Input image $x$.

2: for $i\in[m]$ do

3: Sample a Gaussian noise $z_{i}\sim\mathcal{N}({0},\sigma^{2}I_{q\times n})$
and add it to the input image $x$. Then get an attention vector
$\tilde{w}_{i}=Z(T(x+z_{i}))$ via Algorithm 1 and feed it to the original ViT
and get the prediction $c_{i}=\arg\max_{g\in\mathcal{G}}\bar{y}(x+z_{i}).$

4: end for

5: Estimate the distribution of the output as
$p_{j}=\frac{\\#\\{c_{i}=j;i=1,...,m\\}}{m}$. Compute the average of
$\tilde{w}_{i}$: $\tilde{w}=\frac{1}{m}\sum_{i=1}^{m}\tilde{w}_{m}$.

6: For the $\ell_{2}$-norm case: Calculate the upper bound $P$ as the
following:
$\sup_{\alpha>1}[-\frac{2\sigma^{2}}{\alpha}\ln(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}})]^{1/2}$
where $p_{(1)}$ and $p_{(2)}$ are the first and the second largest values in
$\\{p_{i}\\}$. Then calculate the upper bound $Q$ as
$\sup_{\alpha>1}[\frac{2\sigma^{2}}{\alpha}(\frac{\alpha}{\alpha-1}\ln(2k_{0}(\sum_{i\in\mathcal{S}}\tilde{w}^{\alpha}_{i^{*}})^{\frac{1}{\alpha}}+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i^{*}})-\frac{1}{\alpha-1}\ln(2k_{0}))]^{1/2},$
where $\tilde{w}_{i^{*}}$ is the $i$-th largest component in $\tilde{w}$,
$k_{0}=\lfloor(1-\beta)k\rfloor+1$, and $\mathcal{S}$ denotes the set of last
$k_{0}$ components in top-$k$ indices and the top $k_{0}$ components out of
top-$k$ indices.

7: For the $\ell_{\infty}$-norm case: Calculate $P=\frac{\tilde{P}}{d}$ and
$Q=\frac{\tilde{Q}}{d}$, where $\tilde{P}$ and $\tilde{Q}$ is equivalent to
$P$ and $Q$ in the $\ell_{2}$-norm case respectively, $d=q\times n$.

8: Return: The tolerable size of the attack $\min\\{P,Q\\}$.

##  Appendix B Proof of Theorem 5.1

###### Proof.

Firstly, we know that the $\alpha$-Rényi divergence between two Gaussian
distributions $\mathcal{N}(0,\sigma^{2}I_{d})$ and
$\mathcal{N}(\mu,\sigma^{2}I_{d})$ is bounded by
$\frac{\alpha\|\mu\|_{2}^{2}}{2\sigma^{2}}$. Thus by the postprocessing
property of Rényi divergence we have

$\displaystyle
D_{\alpha}(\tilde{w}(x),\tilde{w}(x^{\prime}))=D_{\alpha}(Z(T(x+z)),Z(T(x^{\prime})))\leq
D_{\alpha}(x+z,x^{\prime}+z)$
$\displaystyle\leq\frac{\alpha\|x-x^{\prime}\|_{F}^{2}}{2\sigma^{2}}\leq\frac{\alpha
R^{2}}{2\sigma^{2}}.$

Thus, when $\frac{\alpha R^{2}}{2\sigma^{2}}\leq\gamma$ it satisfies the
utility robustness.

Second, we show it satisfies the prediction robustness. We first the recall
the following lemma which shows an lower bound between the Rényi divergence of
two discrete distributions:

######  Lemma B.1 (Rényi Divergence Lemma Li et al. (2019)).

Let $P=(p_{1},p_{2},...,p_{k})$ and $Q=(q_{1},q_{2},...,q_{k})$ be two
multinomial distributions. If the indices of the largest probabilities do not
match on $P$ and $Q$, then the Rényi divergence between $P$ and $Q$, i.e.,
$D_{\alpha}(P||Q)$111For $\alpha\in(1,\infty)$, $D_{\alpha}(P||Q)$ is defined
as $D_{\alpha}(P||Q)=\frac{1}{\alpha-1}\log\mathbb{E}_{x\sim
Q}(\frac{P(x)}{Q(x)})^{\alpha}$., satisfies

$\displaystyle
D_{\alpha}(P||Q)\geq-\log(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}}).$

where $p_{(1)}$ and $p_{(2)}$ refer to the largest and the second largest
probabilities in $\\{p_{i}\\}$, respectively.

By Lemma B.1 we can see that as long as
$D_{\alpha}(\tilde{w}(x),\tilde{w}(x^{\prime}))\leq-\log(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}})$
we must have the prediction robustness. Thus, if $\frac{\alpha
R^{2}}{2\sigma^{2}}\leq-\log(1-p_{(1)}-p_{(2)}+2(\frac{1}{2}(p_{(1)}^{1-\alpha}+p_{(2)}^{1-\alpha}))^{\frac{1}{1-\alpha}})$
we have the condition.

Finally we proof the Top-$K$ robustness. The idea of the proof follows Liu et
al. (2021). We proof the following lemma first

######  Lemma B.2.

Consider the set of all vectors with unit $\ell_{1}$-norm in $\mathbb{R}^{T}$,
$\mathcal{Q}$. Then we have

$\displaystyle\min_{q\in\mathcal{Q},V_{k}(\hat{w},q)\geq\beta}$ $\displaystyle
D_{\alpha}(\hat{w},q)=\frac{\alpha}{\alpha-1}\ln(2k_{0}(\sum_{i\in\mathcal{S}}\tilde{w}^{\alpha}_{i})^{\frac{1}{\alpha}}$
$\displaystyle+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i})-\frac{1}{\alpha-1}\ln(2k_{0}),$

where $D_{\alpha}(\hat{w},q)$ is the $\alpha$-divergence of the distributions
whose probability vectors are $\hat{w}$ and $q$.

Now we back to the proof, we know that
$D_{\alpha}(x+z,x^{\prime}+z)\leq\frac{\alpha R^{2}}{2\sigma^{2}}$. And
$D_{\alpha}(Z(T(x+z)),Z(T((x^{\prime}+z)))\leq D_{\alpha}(x+z,x^{\prime}+z)$.
Thus, if $\frac{\alpha
R^{2}}{2\sigma^{2}}\leq\frac{\alpha}{\alpha-1}\ln(2k_{0}(\sum_{i\in\mathcal{S}}\tilde{w}^{\alpha}_{i})^{\frac{1}{\alpha}}+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i})-\frac{1}{\alpha-1}\ln(2k_{0})$
we must have $V_{k}(g(x+z),g(x^{\prime}+z))\geq\beta$.

∎

###### Proof of Lemma B.2.

We denote $m^{T}=(m_{1},m_{2},\cdots,m_{T})$ and $q^{T}=(q_{1},\cdots,q_{T})$.
W.l.o.g we assume that $m_{1}\geq\cdots\geq m_{T}$. Then, to reach the minimum
of Rényi divergence we show that the minimizer $q$ must satisfies
$q_{1}\geq\cdots\geq q_{k-k_{0}-1}\geq q_{k-k_{0}}=\cdots=q_{k+k_{0}+1}\geq
q_{k+k_{0}+2}\geq q_{T}$. We need the following statements for the proof.

######  Lemma B.3.

We have the following statements:

  1. 1.

To reach the minimum, there are exactly $k_{0}$ different components in the
top-k of $\tilde{w}$ and $q$.

  2. 2.

To reach the minimum, $q_{k-k_{0}+1},\cdots,q_{k}$ are not in the top-k of
$q$.

  3. 3.

To reach the minimum, $q_{k+1},\cdots,q_{k+k_{0}}$ must appear in the top-k of
$q$.

  4. 4.

Li et al. (2019) To reach the minimum, we must have $q_{i}\geq q_{j}$ for all
$i\leq j$.

Thus, based on Lemma B.3, we only need to solve the following optimization
problem to find a minimizer $q$:

$\displaystyle\min_{q_{1},\cdots,q_{T}}=\sum_{i=1}^{T}q_{i}(\frac{\tilde{w}_{i}}{q_{i}})^{\alpha}$
$\displaystyle\textbf{s.t. }\sum_{i=1}^{T}q_{i}=1$ $\displaystyle\textbf{s.t.
}q_{i}\leq q_{j},i\geq j$ $\displaystyle\textbf{s.t. }q_{i}\geq 0$
$\displaystyle\textbf{s.t. }q_{i}-q_{j}=0,\forall
i,j\in\mathcal{S}=\\{k-k_{0}+1,\cdots,k+k_{0}\\}$

Solve the above optimization by using Lagrangian method we can get

$q_{i}=\frac{s}{2k_{0}s+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i}},\forall
i\in\mathcal{S},$ (2)
$q_{i}=\frac{(2k_{0})^{\frac{1}{\alpha}}\tilde{w}_{i}}{2k_{0}s+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i}},\forall
i\not\in\mathcal{S}$ (3)

where $s=(\sum_{i\in\mathcal{S}}\tilde{w}^{\alpha}_{i})^{\frac{1}{\alpha}}$.
We can get in this case
$D_{\alpha}(\tilde{w},q)=\frac{\alpha}{\alpha-1}\ln(2k_{0}s+(2k_{0})^{\frac{1}{\alpha}}\sum_{i\not\in\mathcal{S}}\tilde{w}_{i})-\frac{1}{\alpha-1}\ln(2k_{0})$.

∎

###### Proof of Lemma B.3.

We first proof the first item:

Assume that $i_{1},\cdots,i_{k_{0}+j}$ are the $j$ components in the top-k of
$\tilde{w}$ but not in the top-k of $q$, and
$i^{\prime}_{1},\cdots,i^{\prime}_{k_{0}+j}$ are the components in the top-k
of q but not in the top-k of $\tilde{w}$. Consider we have another vector
$q^{1}$ with the same value with $q$ while replace $q_{i_{k_{0}+j}}$ with
$q_{i^{\prime}_{k_{0}+j}}$. Thus we have

$\displaystyle
e^{(\alpha-1)D_{\alpha}(\tilde{w},q^{1})}-e^{(\alpha-1)D_{\alpha}(\tilde{w},q)}$
$\displaystyle=(\frac{\tilde{w}^{\alpha}_{i_{k_{0}+j}}}{q^{\alpha-1}_{i^{\prime}_{k_{0}+j}}}+\frac{\tilde{w}^{\alpha}_{i^{\prime}_{k_{0}+j}}}{q^{\alpha-1}_{i_{k_{0}+j}}})-(\frac{\tilde{w}^{\alpha}_{i_{k_{0}+j}}}{q^{\alpha-1}_{i_{k_{0}+j}}}+\frac{\tilde{w}^{\alpha}_{i^{\prime}_{k_{0}+j}}}{q^{\alpha-1}_{i^{\prime}_{k_{0}+j}}})$
$\displaystyle=(\tilde{w}^{\alpha}_{i_{k_{0}+j}}-\tilde{w}^{\alpha}_{i^{\prime}_{k_{0}+j}})(\frac{1}{q^{\alpha-1}_{i^{\prime}_{k_{0}+j}}}-\frac{1}{q^{\alpha-1}_{i_{k_{0}+j}}})<0,$

since $\tilde{w}_{i_{k_{0}+j}}\geq\tilde{w}_{i^{\prime}_{k_{0}+j}}$ and
$q_{i^{\prime}_{k_{0}+j}}\geq q_{i_{k_{0}+j}}$. Thus, we know reducing the
number of misplacement in top-k can reduce the value $D_{\alpha}(\tilde{w},q)$
which contradict to $q$ achieves the minimal. Thus we must have $j=0$.

We then proof the second statement.

Assume that $i_{1},\cdots,i_{k_{0}}$ are the $k_{0}$ components in the top-k
of $\tilde{w}$ but not in the top-k of $q$, and
$i^{\prime}_{1},\cdots,i^{\prime}_{k_{0}}$ are the components in the top-k of
q but not in the top-k of $\tilde{w}$. Consider we have another unit
$\ell_{1}$-norm vector $q^{2}$ with the same value with $q$ while $q_{i_{j}}$
is replaced by $q_{j^{\prime}}$ where
$\tilde{w}_{j^{\prime}}\geq\tilde{w}_{i_{j}}$ and $j^{\prime}$ is in the top-k
component of $q$ (there must exists such index $j^{\prime}$). Now we can see
that $q^{2}_{j^{\prime}}$ is no longer a top-k component of $q^{2}$ and
$q^{2}_{i_{j}}$ is a top-k component. Thus we have

$\displaystyle
e^{(\alpha-1)D_{\alpha}(\tilde{w},q^{2})}-e^{(\alpha-1)D_{\alpha}(\tilde{w},q)}$
$\displaystyle=(\frac{\tilde{w}^{\alpha}_{i_{j}}}{q^{\alpha-1}_{j^{\prime}}}+\frac{\tilde{w}^{\alpha}_{j^{\prime}}}{q^{\alpha-1}_{i_{j}}})-(\frac{\tilde{w}^{\alpha}_{i_{j}}}{q^{\alpha-1}_{i_{j}}}+\frac{\tilde{w}^{\alpha}_{j^{\prime}}}{q^{\alpha-1}_{j^{\prime}}})$
$\displaystyle=(\tilde{w}^{\alpha}_{i_{j}}-\tilde{w}^{\alpha}_{j^{\prime}})(\frac{1}{q^{\alpha-1}_{j^{\prime}}}-\frac{1}{q^{\alpha-1}_{i_{j}}})\geq
0.$

Now we back to the proof of the statement. We first proof $q_{k}$ is not in
the top-k of $q$. If not, that is $k\not\in\\{i_{1},\cdots,i_{k_{0}}\\}$ and
all $i_{j}<k$. Then we can always find an $i_{j}<k$ such that
$\tilde{w}_{k}\leq\tilde{w}_{i_{j}}$, we can find a vector $\tilde{q}$ by
replacing $q_{i_{j}}$ with $q_{k}$. And we can see that
$D_{\alpha}(\tilde{w},\tilde{q})-D_{\alpha}(\tilde{w},q)\leq 0$, which
contradict to that $q$ is the minimizer.

We then proof $q_{k-1}$ is not in the top-k of $q$. If not we can construct
$\tilde{q}$ by replacing $q_{k}$ with $q_{k-1}$. Since $q_{k}$ is not in top-k
and $\tilde{w}_{k}\leq\tilde{w}_{k-1}$. By the previous statement we have
$D_{\alpha}(\tilde{w},\tilde{q})-D_{\alpha}(\tilde{w},q)\leq 0$, which
contradict to that $q$ is the minimizer. Thus, $q_{k-1}$ is not in the top-k
of $q$. We can thus use induction to proof statement 2.

Finally we proof statement 3. We can easily show that $q_{i}\geq q_{k+1}$ for
$i\leq k$, and $q_{i}\leq q_{k+1}$ for $i\geq k+2$. Thus, $q_{1},\cdots,q_{k}$
are greater than the left entries. Since by Statement 2 we have
$q_{k-k_{0}},\cdots q_{k}$ are not top $k$. Thus we must have $q_{k+1},\cdots
q_{k+k_{0}}$ must be top-k of $q$.

∎

##  Appendix C Proof of Theorem 5.2

###### Proof.

For simplicity in the following we think the data $x$ as a $d$-dimensional
vector and thus the Frobenious norm now becomes to the $\ell_{2}$-norm of the
vector and the max norm becomes to the $\ell_{\infty}$-norm of the vector.

We first show that, in order to prove Theorem 5.2, we only need to prove
Theorem C.1. Then we show that, to prove Theorem C.1, we only need to prove
Theorem C.2. Finally, we give a formal proof of Theorem C.2.

######  Theorem C.1.

For any $\gamma\leq O(1)$, if a randomized (smoothing) mechanism
$\mathcal{M}(x)=x+z:\\{0,\frac{R}{2\sqrt{d}}\\}^{d}\mapsto\mathbb{R}^{d}$ that
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{2}\leq R$. Moreover, if we have for any
$x\in\\{0,\frac{R}{2\sqrt{d}}\\}^{d}$,

$\mathbb{E}[\|z\|_{\infty}]=\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\tau$

for some $\tau\leq O(1)$. Then it must be true that
$\tau\geq\Omega(\frac{\sqrt{\alpha}R}{\sqrt{\gamma}})$.

For any $\mathcal{M}(x)=x+z:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$, in Theorem
C.1, we only consider the expected $\ell_{\infty}$-norm of the noise added by
$\mathcal{M}(x)$ on $x\in\\{0,\frac{R}{2\sqrt{d}}\\}^{d}$. Thus, the $\tau$ in
Theorem C.1 should be less than or equal to the $\tau$ in Theorem 5.2 (on
$x\in\mathbb{R}^{d}$). Therefore, the lower bound for the $\tau$ in Theorem
C.1 (i.e., $\Omega(\frac{\sqrt{\alpha}R}{\sqrt{\gamma}})$) is also a lower
bound for the $\tau$ in Theorem 5.2. That is to say, if Theorem C.1 holds,
then Theorem 5.2 also holds true.

Next, we show that if Theorem C.2 holds, then Theorem C.1 also holds.

######  Theorem C.2.

For any $\gamma\leq O(1)$, if a randomized (smoothing) mechanism
$\mathcal{M}(x):\\{0,\frac{R}{2\sqrt{d}}\\}^{d}\mapsto[0,\frac{R}{2\sqrt{d}}]^{d}$222This
mechanism might not be simply $x+z$ since it must involve operations to clip
the output into $[0,\frac{R}{2\sqrt{d}}]^{d}$ that
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{2}\leq R$. Moreover, if for any
$x\in\\{0,\frac{R}{2\sqrt{d}}\\}^{d}$

$\mathbb{E}[\|z\|_{\infty}]=\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\tau$

for some $\tau\leq O(1)$. Then it must be true that
$\tau\geq\Omega(\frac{\sqrt{\alpha}R}{\sqrt{\gamma}})$.

#### Proof of Theorem C.1

For any
$\mathcal{M}(x)=x+z:\\{0,\frac{R}{2\sqrt{d}}\\}^{d}\mapsto\mathbb{R}^{d}$
considered in Theorem C.1 that
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{2}\leq R$, there randomized mechanism
$\mathcal{M}^{\prime\prime}(x):\\{0,\frac{R}{2\sqrt{d}}\\}^{d}\mapsto[0,\frac{R}{2\sqrt{d}}]^{d}$
considered in Theorem C.2 such that for all
$x\in\\{0,\frac{R}{2\sqrt{d}}\\}^{d}$

$\mathbb{E}[\|\mathcal{M}^{\prime\prime}(x)-x\|_{\infty}]\leq\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}].$

To prove the above statement, we first let $a=\frac{R}{2\sqrt{d}}$ and
$\mathcal{M}^{\prime}(x)=\min\\{\mathcal{M}(x),a\\}$, where $\min$ is a
coordinate-wise operator. Now we fix the randomness of $\mathcal{M}(x)$ (that
is $\mathcal{M}(x)$ is deterministic), and we assume that
$\|\mathcal{M}(x)-x\|_{\infty}=|\mathcal{M}_{j}(x)-x_{j}|$,
$\|\mathcal{M}^{\prime}(x)-x\|_{\infty}=|\mathcal{M}_{i}^{\prime}(x)-x_{i}|$.
If $\mathcal{M}_{i}(x)<a$, then by the definitions, we have
$\|\mathcal{M}^{\prime}(x)-x\|_{\infty}=|\mathcal{M}_{i}^{\prime}(x)-x_{i}|=|\mathcal{M}_{i}(x)-x_{i}|\leq\|\mathcal{M}(x)-x\|_{\infty}$.
If $\mathcal{M}_{i}(x)\geq a$, then we have
$|\mathcal{M}_{i}^{\prime}(x)-x_{i}|=|a-x_{i}|$. Since $x_{i}\in\\{0,a\\}$ and
$\mathcal{M}_{i}(x)\geq a$, $|\mathcal{M}_{i}(x)-x_{i}|\geq|a-x_{i}|$.
$\|\mathcal{M}(x)-x\|_{\infty}\geq|\mathcal{M}_{i}(x)-x_{i}|\geq|a-x_{i}|$.
Thus,
$\mathbb{E}[\|\mathcal{M}^{\prime}(x)-x\|_{\infty}]\leq\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]$.

Then, we let
$\mathcal{M}^{\prime\prime}(x)=\max\\{\mathcal{M}^{\prime}(x),0\\}$ where
$\max$ is also a coordinate-wise operator. We can use a similar method to
prove that
$\mathbb{E}[\|\mathcal{M}^{\prime\prime}(x)-x\|_{\infty}]\leq\mathbb{E}[\|\mathcal{M}^{\prime}(x)-x\|_{\infty}]\leq\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]$.
Also, we can see that
$\mathcal{M}^{\prime\prime}(x)=\max\\{0,\min\\{\mathcal{M}(x),a\\}\\}$, which
means $\mathcal{M}^{\prime\prime}$ satisfies
$D_{\alpha}(\mathcal{M}^{\prime\prime}(x),\mathcal{M}^{\prime\prime}(x^{\prime}))\leq\gamma$
for all $\|x-x^{\prime}\|_{2}\leq R$ due to the postprocessing property.

Since
$\mathbb{E}[\|\mathcal{M}^{\prime\prime}(x)-x\|_{\infty}]\leq\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]$,
and $\mathcal{M}^{\prime\prime}(x)$ is a randomized mechanism satisfying the
conditions in Theorem C.2, the $\tau$ in Theorem C.2 should be less than or
equal to the $\tau$ in Theorem C.1. Therefore, the lower bound for the $\tau$
in Theorem C.2 is also a lower bound for the $\tau$ in Theorem C.1. That is to
say, if Theorem C.2 holds, then Theorem C.1 also holds.

Finally, we give a proof of Theorem C.2. Before that we need to review some
definitions of Differnetial Privacy Dwork et al. (2006).

######  Definition C.3.

Given a data universe $X$, we say that two datasets $D,D^{\prime}\subset X$
are neighbors if they differ by only one entry, which is denoted by $D\sim
D^{\prime}$. A randomized algorithm $\mathcal{M}$ is
$(\epsilon,\delta)$-differentially private (DP) if for all neighboring
datasets $D,D^{\prime}$ and all events $S$ the following holds

$P(\mathcal{M}(D)\in S)\leq e^{\epsilon}P(\mathcal{M}(D^{\prime})\in
S)+\delta.$

######  Definition C.4.

A randomized algorithm $\mathcal{M}$ is $(\alpha,\epsilon)$-Rényi
differentially private (DP) if for all neighboring datasets $D,D^{\prime}$ the
following holds

$D_{\alpha}(\mathcal{M}(D)\|\mathcal{M}(D^{\prime}))\leq\epsilon.$

######  Lemma C.5 (From RDP to DP Mironov (2017)).

If a mechanism is $(\alpha,\epsilon)$-RDP, then it also satifies
$(\epsilon+\frac{\log\frac{1}{\delta}}{\alpha-1},\delta)$-DP.

#### Proof of Theorem C.2

Since $\mathcal{M}$ satisfies
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{2}\leq R$ on $\\{0,\frac{r}{2\sqrt{d}}\\}^{d}$, and for any
$x_{i},x_{j}\in\\{0,\frac{R}{2\sqrt{d}}\\}^{d}$, $\|x_{i}-x_{j}\|_{2}\leq R$
(i.e., $x_{j}\in\mathbb{B}_{2}(x_{i},R)$), we can see $\mathcal{M}$ is
$(\alpha,\gamma)$-RDP on $\\{0,\frac{r}{2\sqrt{d}}\\}^{d}$. Thus by Lemma C.5
we can see $\mathcal{M}$ is
$(\gamma+2\frac{\log\frac{1}{\delta}}{\alpha-1},\delta)$-DP on
$\\{0,\frac{r}{2\sqrt{d}}\\}^{d}$.

Then let us take use of the above condition by connecting the lower bound of
the sample complexity to estimate one-way marginals (i.e., mean estimation)
for DP mechanisms with the lower bound studied in Theorem C.2. Suppose an
$n$-size dataset $X\in\mathbb{R}^{n\times d}$, the one-way marginal is
$h(D)=\frac{1}{n}\sum_{i=1}^{n}{X_{i}}$, where $X_{i}$ is the $i$-th row of
$X$. In particular, when $n=1$, one-way marginal is just the data point
itself, and thus, the condition in Theorem C.2 can be rewritten as

$\mathbb{E}[\|\mathcal{M}(D)-h(D)\|_{\infty}]\leq\alpha.$ (4)

Based on this connection, we first prove the case where $r=2\sqrt{d}$, and
then generalize it to any $r$. For $r=2\sqrt{d}$, the conclusion reduces to
$\tau\geq\Omega(\sqrt{\frac{d}{\epsilon}})$. To prove this, we employ the
following lemma, which provides a one-way margin estimation for all DP
mechanisms.

######  Lemma C.6 (Theorem 1.1 in Steinke and Ullman (2016)).

For any $\epsilon\leq O(1)$, every
$2^{-\Omega(n)}\leq\delta\leq\frac{1}{n^{1+\Omega(1)}}$ and every
$\alpha\leq\frac{1}{10}$, if $\mathcal{M}:(\\{0,1\\}^{d})^{n}\mapsto[0,1]^{d}$
is $(\epsilon,\delta)$-DP and
$\mathbb{E}[\|\mathcal{M}(D)-h(D)\|_{\infty}]\leq\tau$, then we have
$n\geq\Omega(\frac{\sqrt{d\log\frac{1}{\delta}}}{\epsilon\tau}).$

Setting $n=1,\epsilon=\gamma+2\frac{\log\frac{1}{\delta}}{\alpha-1}$ in Lemma
C.6, we can see that if $\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\tau$,
then we must have

$1\geq\Omega(\frac{\sqrt{d\log\frac{1}{\delta}}}{(\gamma+2\frac{\log\frac{1}{\delta}}{\alpha-1})\tau})\geq\Omega(\frac{\sqrt{\alpha}\sqrt{d}}{\sqrt{\gamma}\tau}),$

where the last inequality holds if $\alpha$ is sufficiently large and $\gamma$
is sufficiently small. Therefore, we have the following theorem,

######  Theorem C.7.

For all $\mathcal{M}$ satisfies
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{2}\leq 2\sqrt{d}$ on $\\{0,1\\}^{d}$ such that

$\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\tau,$ (5)

for some $\tau\leq O(1)$. Then $\tau\geq\Omega(\frac{\sqrt{\alpha
d}}{\sqrt{\gamma}})$.

Apparently, Theorem C.7 is special case of Theorem C.2 where $R=2\sqrt{d}$.
Now we come back to the proof for any
$\mathcal{M}(x):\\{0,\frac{r}{2\sqrt{d}}\\}^{d}\mapsto[0,\frac{r}{2\sqrt{d}}]^{d}$
satisfies $D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for
all $\|x-x^{\prime}\|_{2}\leq R$. We substitute $\frac{2\sqrt{d}}{R}x$ with
$\tilde{x}\in\\{0,1\\}^{d}$ and construct $\tilde{\mathcal{M}}$ as
$\tilde{\mathcal{M}}(\tilde{x})=\frac{2\sqrt{d}}{R}\mathcal{M}(x)\in[0,1]^{d}$.
Since $\mathcal{M}(x)$ satisfies

$\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\tau,$

then we have

$\mathbb{E}[\|\tilde{\mathcal{M}}(\tilde{x})-\tilde{x}\|_{\infty}]=\mathbb{E}[\|\frac{2\sqrt{d}}{R}\mathcal{M}(x)-\frac{2\sqrt{d}}{R}x\|_{\infty}]\leq\frac{2\sqrt{d}}{R}\alpha.$

By the postprocessing property of Rényi divergence we can see
$D_{\alpha}(\tilde{\mathcal{M}}(x),\tilde{\mathcal{M}}(x^{\prime}))\leq\gamma$
for all $\|x-x^{\prime}\|_{2}\leq 2\sqrt{d}$.

Considering $\tilde{\mathcal{M}}:\\{0,1\\}^{d}\mapsto[0,1]^{d}$ in Theorem C.7
with $\tau=\frac{2\sqrt{d}}{r}\tau\leq O(1)$ (because
$\mathbb{E}[\|\tilde{\mathcal{M}}(\tilde{x})-\tilde{x}\|_{\infty}]\leq\frac{2\sqrt{d}}{R}\tau$),
we have

$\frac{2\sqrt{d}}{R}\tau\geq\Omega(\frac{\sqrt{\alpha d}}{\sqrt{\gamma}}).$
(6)

Therefore, Theorem C.2 holds true, thus, Theorem C.1 also holds true, and
Theorem 5.2 is proved. ∎

##  Appendix D Proof of Theorem 5.3

###### Proof.

We can see the dataset as a $d$-dimensional vector by unfolding it. Thus, now
the max norm of a matrix becomes to the $\ell_{\infty}$-norm of a vector.
Firstly, we know that the $\alpha$-Rényi divergence between two Gaussian
distributions $\mathcal{N}(0,\sigma^{2}I_{d})$ and
$\mathcal{N}(\mu,\sigma^{2}I_{d})$ is bounded by
$\frac{\alpha\|\mu\|_{2}^{2}}{2\sigma^{2}}\leq\frac{\alpha
dR^{2}}{2\sigma^{2}}$. Thus by the postprocessing property of Rényi divergence
we have

$\displaystyle
D_{\alpha}(\tilde{w}(x),\tilde{w}(x^{\prime}))=D_{\alpha}(Z(T(x+z)),Z(T(x^{\prime})))\leq
D_{\alpha}(x+z,x^{\prime}+z)$
$\displaystyle\leq\frac{\alpha\|x-x^{\prime}\|_{F}^{2}}{2\sigma^{2}}\leq\frac{\alpha
dR^{2}}{2\sigma^{2}}.$

Thus, when $\frac{d\alpha R^{2}}{2\sigma^{2}}\leq\gamma$ it satisfies the
utility robustness. For the prediction and top-$k$ robustness we can use the
similar proof as in Theorem 5.1. We omit it here for simplicity.

∎

##  Appendix E Proof of Theorem 5.4

###### Proof.

Similar to the proof of Theorem 5.2, in order to prove Theorem 5.4, we only
need to prove the following theorem:

######  Theorem E.1.

If there is a randomized (smoothing) mechanism
$\mathcal{M}(x):\\{0,\frac{r}{2}\\}^{d}\mapsto[0,\frac{r}{2}]^{d}$ such that
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{\infty}\leq R$ for any $x\in\\{0,\frac{r}{2}\\}^{d}$, the
following holds

$\mathbb{E}[\|z\|_{\infty}]=\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\gamma$

for some $\gamma\leq O(1)$. Then it must be true that
$\gamma\geq\Omega(\frac{\sqrt{\alpha d}}{\sqrt{\gamma}})$.

Since $\mathcal{M}$ satisfies
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{\infty}\leq R$ on $\\{0,\frac{r}{2}\\}^{d}$, and for any
$x_{i},x_{j}\in\\{0,\frac{R}{2}\\}^{d}$, $\|x_{i}-x_{j}\|_{2}\leq R$ (i.e.,
$x_{j}\in\mathbb{B}_{2}(x_{i},R)$), we can see $\mathcal{M}$ is
$(\alpha,\gamma)$-RDP on $\\{0,\frac{r}{2}\\}^{d}$. Thus by Lemma C.5 we can
see $\mathcal{M}$ is
$(\gamma+2\frac{\log\frac{1}{\delta}}{\alpha-1},\delta)$-DP on
$\\{0,\frac{r}{2}\\}^{d}$.

We first consider the case where $r=2$. By setting $n=1$ and
$\gamma=\gamma+2\frac{\log\frac{1}{\delta}}{\alpha-1}$ in Lemma C.6, we have a
similar result as in Theorem C.7:

######  Theorem E.2.

For all $\mathcal{M}$ satisfies
$D_{\alpha}(\mathcal{M}(x),\mathcal{M}(x^{\prime}))\leq\gamma$ for all
$\|x-x^{\prime}\|_{\infty}\leq 2$ on $\\{0,1\\}^{d}$ such that

$\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\tau,$ (7)

for some $\tau\leq O(1)$. Then $\tau\geq\Omega(\frac{\sqrt{\alpha
d}}{\sqrt{\gamma}})$.

For general $R$, similar to the proof of Theorem C.2, we substitute
$\frac{2}{R}x$ with $\tilde{x}\in\\{0,1\\}^{d}$ and construct
$\tilde{\mathcal{M}}$ as
$\tilde{\mathcal{M}}(\tilde{x})=\frac{2}{R}\mathcal{M}(x)\in[0,1]^{d}$. Since
$\mathcal{M}(x)$ satisfies

$\mathbb{E}[\|\mathcal{M}(x)-x\|_{\infty}]\leq\alpha,$

then we have

$\mathbb{E}[\|\tilde{\mathcal{M}}(\tilde{x})-\tilde{x}\|_{\infty}]=\mathbb{E}[\|\frac{2}{R}\mathcal{M}(x)-\frac{2}{R}x\|_{\infty}]\leq\frac{2}{R}\alpha.$

Also, $\tilde{\mathcal{M}}:\\{0,1\\}^{d}\mapsto[0,1]^{d}$ satisfies
$D_{\alpha}(\tilde{\mathcal{M}}(x),\tilde{\mathcal{M}}(x^{\prime}))\leq\gamma$
for all $\|x-x^{\prime}\|_{\infty}\leq R$ on $\\{0,\frac{R}{2}\\}^{d}$. Thus
by Theorem E.2 with $\alpha=\frac{2}{R}\alpha$ we have

$\alpha\geq\Omega(\frac{R\sqrt{\alpha d}}{\sqrt{\gamma}}),$

thus we have Theorem E.1. ∎

##  Appendix F Baseline Methods

Five baseline methods are considered in this paper. The implementation and
parameter setting of each method is based on the corresponding official code.
Note that in this paper, we did not involve compression with Shapely-value
methods Lundberg and Lee (2017) due to the large computational complexity and
sub-optimal performance Chen et al. (2018).

  1. 1.

Raw Attention Vaswani et al. (2017). It is common practice to consider the raw
attention value as a relevancy score for a single attention layer in both
visual and language domains Xu et al. (2015). However, for the case of
multiple layers, the attention score in deeper layers may be unreliable for
explaining the importance of each token due to the token mixing property Lee-
Thorp et al. (2021) of the self-attention mechanism. Based on observations in
Chefer et al. (2021), we consider the raw attention in the first layer since
they are more faithful in explanation compared to deeper layers.

  2. 2.

Rollout Abnar and Zuidema (2020). To compute the attention weights from
positions in layer $l_{i}$ to positions in layer $l_{j}$ in a Transformer with
$L$ layers, we multiply the attention weights matrices in all the layers below
the layer $l_{i}$. If $i>j$, we multiply by the attention weights matrix in
the layer $l_{i-1}$, and if $i=j$, we do not multiply by any additional
matrices. This process can be represented by the following equation:

$\tilde{A}(l_{i})=\left\\{\begin{array}[]{@{}ll@{}}A(l_{i})\tilde{A}(l_{i-1})&\mbox{if}~{}i>j\\\
A(l_{i})&\mbox{if}~{}i=j\end{array}\right.$

  3. 3.

GradCAM Selvaraju et al. (2017). The main motivation of the Class Activation
Mapping (CAM) approach is to obtain a weighted map based on the feature
channels in one layer. The derived map can explain the importance of each
pixel of the input image based on the intuition that non-related features are
filtered in the channels of the deep layer. GradCAM Selvaraju et al. (2017)
proposes to leverage the gradient information by globally averaging the
gradient score as the weight. To be more specific, the weight of channel $k$
with respect to class $c$ is calculated using

$\alpha_{k}^{c}=\frac{1}{Z}\sum_{i}\sum_{j}\quad\frac{\partial y^{c}}{\partial
A_{ij}^{k}},$

where $\alpha_{k}^{c}$ is the attention weight for feature map $k$ of the
final convolutional layer, for class $c$. $y^{c}$ is the output class score
for class $c$, and $A_{ij}^{k}$ is the activation at location $(i,j)$ in
feature map $k$. The summation over $i$ and $j$ indicates that the gradient is
computed over all locations in the feature map. The normalization factor $Z$
is the sum of all the attention weights for the feature maps in the final
convolutional layer.

  4. 4.

LRP Bach et al. (2015). Layer-wise Relevance Propagation (LRP) method
propagates relevance from the predicated score in the final layer to the input
image based on the Deep Taylor Decomposition (DTD) Montavon et al. (2017)
framework. Specifically, to compute the relevance of each neuron in the
network, we iteratively perform backward propagation using the following
equation:

$R_{j}=\sum_{k}\frac{u_{j}w_{jk}}{\sum_{j}a_{j}w_{jk}+\epsilon\cdot\text{sign}(a_{j}w_{jk})}R_{k},$

where $R_{j}$ and $R_{k}$ are the relevance scores of neurons $j$ and $k$,
respectively, in consecutive layers of the network. $a$ represents the
activation of neuron $j$, $w_{j,k}$ is the weight between neurons $j$ and $k$,
and $\epsilon$ is a small constant used as a stabilizer to prevent numerical
degeneration. For more information on this technique, please see the original
paper.

  5. 5.

VTA Chefer et al. (2021). Vanilla Trans. Att. (VTA) uses a LRP-based relevance
score to evaluate the importance of each attention head in each layer. These
scores are then integrated throughout the attention graph by combining
relevancy and gradient information in an iterative process that eliminates
negative values.

##  Appendix G Implementation details

Diffusion Denoiser Implementation. For COCO and CitySpace, we trained the
diffusion models from scratch following Ho et al. (2020). For ImageNet, we
leverage the pre-trained diffusion model released in the guided-diffusion.
Spcificly, the 256x256_diffusion_uncond is used as a denoiser. To resolve the
size mismatch, we resize the images each time of their inputs and outputs from
the diffusion model. The diffusion model we adopted uses a linear noise
schedule with $\beta_{1}=0.0001$ and $\beta_{N}=0.02$. The sampling steps $N$
are set to 1000. We clip the optimal $t^{*}$ when it falls outside the range
of $[0,N-1]$.

Max-fuse with lowest pixels drop. After obtaining explanation maps with a
number of sampled noisy images, instead of fusing these maps with mean
operation, we leverage the approach of max fusing with the lowest pixels drop
following Jacobgil . Specifically, we drop the lowest $10\%$ unimportant
pixels for each map and apply element-wise maximum on the set of modified
maps. The element of the final map is re-scaled to $[0,1]$ using min-max
normalization.

Model Training Details. We use the pre-trained backbones in the timm library
for feature extractor of classification and segmentation. As for different
ViT, we both leverage the base version with a patch size of 16 and an image
size of 224. For the downstream dataset, we then fine-tuned these models using
the Adam optimizer with a learning rate of 0.001 for a total of 50 epochs,
with a batch size of 128. To prevent overfitting, we implemented early
stopping with a criterion of 20 epochs. For data augmentation, we follow the
common practice: Resize(256) $\rightarrow$ CenterCrop(224) $\rightarrow$
ToTensor $\rightarrow$ Normalization. And the mean and stand deviation of
normalization are both $[0.5,0.5,0.5]$.

Adversarial Perturbation. The perturbation radius is denoted by $\rho_{u}$ and
is set to $8/255$ unless otherwise stated. For CIFAR-10, ImageNet, and COCO,
the step size is set to $\rho_{u}/5$, and the total number of steps is set to
$10$. For the Cityscape dataset, the step size was set to $\rho_{u}/125$, and
the total number of steps was set to $250$.

##  Appendix H More Results

In this section, we provide more results to demonstrate the performance of our
methods in terms of both model prediction and explainability. First, we aim to
evaluate whether our method will affect utility when no attack is presented.
We evaluate this on the ImageNet classification dataset using three different
kinds of model architectures. Then we ablate the component proposed in our
method to study their individual contributions.

Clean Utility. As we can see from Table 4, our method outperforms the Vanilla
approach under a relatively small smoothing radius, $\delta=2/255$. This
result suggests that our method is able to enhance the classification utility
with appropriate $\delta$. However, we also find that, as $\delta$ increases
to $\delta=5/255$, there is a slight performance drop. And as the $\delta$
increases to $\delta=10/255$, the testing accuracy drops more, which indicates
the necessity of choosing the right $\delta$. Since too large $\delta$ might
lead to the smoothed images being overwhelmed with noise, which will lead to
lower classification confidence. In a word, the results show that our method
can even improve clean utility with appropriate small $\delta$.

Method | $\delta$ | Model
---|---|---
ViT | DeiT | Swin
Vanilla | - | 85.22 | 85.80 | 86.40
Ours | $2/255$ | 86.35 | 86.50 | 87.20
$5/255$ | 84.83 | 84.51 | 85.84
$10/255$ | 79.59 | 80.89 | 81.25
Table 4: The testing accuracy of our method and vanilla approach on ImageNet
using three different ViT-based models under no attack.

More Experiments of Attacks. We test more adversarial attacks, including PGD,
FGSM and AutoAttack in Tab. 5. The results show that our FViT performs well in
explanation for the perturbed image across different adversarial attacks and
the AutoAttack is the strongest one in degrading the explanation faithfulness
among considered baselines. Moreover, our FViT still successfully explains the
correct region for the given class. We define a faithfulness score. The
details are as follows.

Given the heap map $M_{gt}$ yield on a clean image and perturbed one $M_{p}$
on a poisoned image, we define faithfulness score $S_{Faith}$ as the
reciprocal to the average of the absolute difference between the two heat
maps:

$S_{Faith}=\frac{N}{\sum|M_{gt}-M_{p}|+\epsilon},$ (8)

where $N$ is the pixel number and $\epsilon=0.01$ is a small constant for
numerical stability.

Input | Clean | PGD | FGSM | AutoAttack
---|---|---|---|---
|  |  |  |
$S_{Faith}$ | - | 4.60 | 4.45 | 4.22

Table 5: Faithfulness score $S_{Faith}$ and visualization results of FViT
under additional adversarial attack methods with $\ell_{\infty}$-norm threat
model and $\rho_{u}=\frac{8}{255}$. $S_{Faith}$ is reciprocal to the average
of the absolute difference between the ground-truth heat map and the predicted
one. The higher the score, the more faithful the explanation.

Results of $l_{2}$-norm. Mathematically, with the same noise level,
$l_{\infty}$-norm ball $B_{\infty}$ is a superset of the $l_{2}$-norm ball
$B_{2}$. Thus, it will lead to more powerful attacks. Thus, by showing the
effectiveness under $l_{\infty}$-norm threat model, we can also bound the
performance of FViT under $l_{2}$-norm threat model. We additionally present
more results in Tab. 6, which demonstrates this statement since the
faithfulness score yield from $l_{2}$-norm threat model is consistently higher
than that from $l_{\infty}$-norm threat model.

Norm type | $2/255$ | $4/255$ | $6/255$ | $8/255$ | $10/255$
---|---|---|---|---|---
$\ell_{2}$ | 29.16 | 12.63 | 10.56 | 5.62 | 6.30
$\ell_{\infty}$ | 3.27 | 11.90 | 8.79 | 4.74 | 4.70
Table 6:  Faithfulness score of FViT under $\ell_{\infty}$ and
$\ell_{2}$-norm.

Ablation Study. As shown in Table 7, it suggests that our method outperforms
all other baselines on all three datasets under adversarial attacks with
different budgets. In particular, On the ImageNet dataset, the ViT model with
our method has the highest pixel accuracy at 64%, while the DeiT model with
our method had the highest mIoU at 46%. On the Cityscape dataset, the ViT
model with Ours had the highest mIoU at 59%. On the COCO dataset, the ViT
model with Ours had the highest pixel accuracy at 74% and the highest mIoU at
76%. Moreover, we visualized the ablated version of our method in Figure 8.
Overall, our method consistently outperforms all other methods, indicating its
superiority in accuracy and robustness.

Noise Radius | Model | Method | ImageNet | Cityscape | COCO
---|---|---|---|---|---
Cla. Acc. (%) | Pix. Acc. (%) | mIoU | mAP | Cla. Acc. (%) | Pix. Acc. (%) | mIoU | mAP | Cla. Acc. (%) | Pix. Acc. (%) | mIoU | mAP
$\rho_{u}=9/255$ | VIT | Raw Attention | 0.6 | 0.5 | 0.42 | 0.77 | 0.66 | 0.62 | 0.46 | 0.75 | 0.78 | 0.65 | 0.63 | 0.81
Rollout | 0.72 | 0.56 | 0.42 | 0.76 | 0.79 | 0.55 | 0.51 | 0.76 | 0.82 | 0.64 | 0.53 | 0.85
GradCAM | 0.64 | 0.49 | 0.5 | 0.78 | 0.79 | 0.64 | 0.5 | 0.75 | 0.74 | 0.78 | 0.67 | 0.91
LRP | 0.7 | 0.54 | 0.43 | 0.78 | 0.68 | 0.68 | 0.52 | 0.86 | 0.82 | 0.69 | 0.7 | 0.81
VTA | 0.64 | 0.56 | 0.43 | 0.77 | 0.7 | 0.74 | 0.58 | 0.89 | 0.8 | 0.82 | 0.67 | 0.88
Ours | 0.69 | 0.64 | 0.48 | 0.73 | 0.74 | 0.71 | 0.59 | 0.9 | 0.88 | 0.74 | 0.76 | 0.97
DeiT | Raw Attention | 0.63 | 0.6 | 0.42 | 0.68 | 0.75 | 0.56 | 0.49 | 0.71 | 0.83 | 0.64 | 0.57 | 0.79
Rollout | 0.7 | 0.57 | 0.38 | 0.66 | 0.69 | 0.64 | 0.53 | 0.76 | 0.82 | 0.76 | 0.57 | 0.76
GradCAM | 0.67 | 0.52 | 0.46 | 0.81 | 0.81 | 0.66 | 0.55 | 0.83 | 0.76 | 0.71 | 0.57 | 0.91
LRP | 0.63 | 0.63 | 0.46 | 0.78 | 0.81 | 0.66 | 0.63 | 0.79 | 0.78 | 0.73 | 0.66 | 0.86
VTA | 0.77 | 0.68 | 0.54 | 0.72 | 0.71 | 0.71 | 0.58 | 0.79 | 0.82 | 0.71 | 0.61 | 0.86
Ours | 0.8 | 0.64 | 0.5 | 0.81 | 0.83 | 0.72 | 0.67 | 0.83 | 0.81 | 0.72 | 0.72 | 0.84
Swin | Raw Attention | 0.65 | 0.49 | 0.41 | 0.76 | 0.69 | 0.67 | 0.44 | 0.79 | 0.85 | 0.72 | 0.58 | 0.82
Rollout | 0.62 | 0.56 | 0.4 | 0.81 | 0.72 | 0.56 | 0.52 | 0.84 | 0.76 | 0.69 | 0.62 | 0.81
GradCAM | 0.77 | 0.58 | 0.4 | 0.8 | 0.68 | 0.68 | 0.51 | 0.88 | 0.87 | 0.76 | 0.65 | 0.86
LRP | 0.67 | 0.58 | 0.48 | 0.74 | 0.72 | 0.63 | 0.52 | 0.84 | 0.84 | 0.79 | 0.66 | 0.82
VTA | 0.7 | 0.59 | 0.56 | 0.83 | 0.85 | 0.65 | 0.62 | 0.88 | 0.87 | 0.74 | 0.72 | 0.83
Ours | 0.78 | 0.63 | 0.49 | 0.9 | 0.74 | 0.78 | 0.56 | 0.81 | 0.86 | 0.74 | 0.75 | 0.93
$\rho_{u}=10/255$ | VIT | Raw Attention | 0.57 | 0.38 | 0.34 | 0.53 | 0.57 | 0.46 | 0.38 | 0.67 | 0.74 | 0.62 | 0.45 | 0.66
Rollout | 0.58 | 0.43 | 0.38 | 0.67 | 0.6 | 0.55 | 0.36 | 0.7 | 0.66 | 0.6 | 0.48 | 0.69
GradCAM | 0.52 | 0.39 | 0.3 | 0.6 | 0.57 | 0.57 | 0.46 | 0.63 | 0.65 | 0.63 | 0.45 | 0.8
LRP | 0.62 | 0.5 | 0.38 | 0.6 | 0.66 | 0.57 | 0.51 | 0.77 | 0.65 | 0.57 | 0.55 | 0.71
VTA | 0.52 | 0.5 | 0.34 | 0.68 | 0.63 | 0.6 | 0.46 | 0.75 | 0.7 | 0.69 | 0.57 | 0.75
Ours | 0.59 | 0.54 | 0.36 | 0.78 | 0.74 | 0.59 | 0.45 | 0.72 | 0.76 | 0.73 | 0.63 | 0.74
DeiT | Raw Attention | 0.53 | 0.46 | 0.25 | 0.62 | 0.55 | 0.5 | 0.39 | 0.6 | 0.68 | 0.63 | 0.44 | 0.75
Rollout | 0.6 | 0.42 | 0.33 | 0.66 | 0.67 | 0.5 | 0.44 | 0.63 | 0.73 | 0.55 | 0.47 | 0.72
GradCAM | 0.64 | 0.52 | 0.37 | 0.69 | 0.63 | 0.54 | 0.46 | 0.75 | 0.67 | 0.58 | 0.54 | 0.72
LRP | 0.65 | 0.55 | 0.4 | 0.73 | 0.58 | 0.51 | 0.53 | 0.66 | 0.74 | 0.65 | 0.52 | 0.74
VTA | 0.58 | 0.54 | 0.42 | 0.66 | 0.64 | 0.61 | 0.44 | 0.68 | 0.69 | 0.59 | 0.5 | 0.75
Ours | 0.65 | 0.48 | 0.47 | 0.73 | 0.69 | 0.66 | 0.49 | 0.85 | 0.76 | 0.72 | 0.51 | 0.85
Swin | Raw Attention | 0.6 | 0.41 | 0.3 | 0.55 | 0.7 | 0.54 | 0.37 | 0.64 | 0.63 | 0.65 | 0.47 | 0.72
Rollout | 0.57 | 0.43 | 0.36 | 0.66 | 0.63 | 0.51 | 0.47 | 0.64 | 0.64 | 0.66 | 0.49 | 0.7
GradCAM | 0.6 | 0.47 | 0.31 | 0.58 | 0.58 | 0.54 | 0.5 | 0.67 | 0.7 | 0.68 | 0.48 | 0.76
LRP | 0.53 | 0.53 | 0.32 | 0.63 | 0.67 | 0.6 | 0.52 | 0.69 | 0.72 | 0.64 | 0.59 | 0.84
VTA | 0.59 | 0.6 | 0.48 | 0.68 | 0.75 | 0.54 | 0.51 | 0.73 | 0.71 | 0.61 | 0.63 | 0.74
Ours | 0.63 | 0.54 | 0.41 | 0.77 | 0.78 | 0.63 | 0.49 | 0.79 | 0.7 | 0.65 | 0.62 | 0.83

Table 7: Comparison of different explanation methods on multiple datasets using VIT, DeiT, and Swin models Corrupted Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
|  |  |  |  |  |
Figure 4: Visualization results of the attention map on corrupted input for different methods.  Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
Dog: clean$\rightarrow$ Dog: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Cat: clean$\rightarrow$ Cat: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Elephant: clean$\rightarrow$ Elephant: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Zebra: clean$\rightarrow$ Zebra: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Figure 5:  Class-specific visualizations under adversarial corruption.  Corrupted Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
Clean$\rightarrow$ |  |  |  |  |  |
Poisoned$\rightarrow 1/255$ |  |  |  |  |  |
Poisoned$\rightarrow 2/255$ |  |  |  |  |  |
Poisoned$\rightarrow 3/255$ |  |  |  |  |  |
Poisoned$\rightarrow 4/255$ |  |  |  |  |  |
Poisoned$\rightarrow 5/255$ |  |  |  |  |  |
Figure 6: Visualization results of the attention map on corrupted input for different methods under different attack radii.  Corrupted Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
Clean$\rightarrow$ |  |  |  |  |  |
Poisoned$\rightarrow 6/255$ |  |  |  |  |  |
Poisoned$\rightarrow 7/255$ |  |  |  |  |  |
Poisoned$\rightarrow 8/255$ |  |  |  |  |  |
Poisoned$\rightarrow 9/255$ |  |  |  |  |  |
Poisoned$\rightarrow 10/255$ |  |  |  |  |  |
Figure 7: Visualization results of the attention map on corrupted input for different methods under different attack radii.  Corrupted Input | Ours | Our w/o Denoising | Our w/o Guassian smoothing
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |
Figure 8: Visualization results of the attention map on corrupted input for the ablated version of our method.  Input | Raw Attention | Rollout | GradCAM | LRP | VTA | Ours
---|---|---|---|---|---|---
Wolf: clean$\rightarrow$ Wolf: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Deer: clean$\rightarrow$ Deer: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Tiger: clean$\rightarrow$ Tiger: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Zebra: clean$\rightarrow$ Zebra: poisoned$\rightarrow$ $7/255$ |  |  |  |  |  |
|  |  |  |  |
Figure 9:  Class-specific visualizations under adversarial corruption. For
each image, we present results for two different classes.