GSE: Group-wise Sparse and Explainable Adversarial Attacks

## 1 Introduction

Deep neural networks (DNNs) have exhibited vulnerability to adversarial attacks [, , , ]. These attacks involve the deliberate introduction of perturbations into their inputs, effectively deceiving the network into generating incorrect predictions. Adversarial attacks raise significant security concerns for real-world systems and prompt inquiries into the generalization capabilities of neural classifiers []. Simultaneously, investigating and harnessing adversarial attacks can serve as a valuable tool for diagnosing and ultimately fortifying the vulnerabilities of a DNN, notably through techniques such as adversarial training [] or randomized smoothing [].
While many methods for crafting adversarial examples focus on $\ell_{p}$ neighbourhoods with $p\geq 1$, recent research has explored the intriguing case of $p=0$, leading to sparse adversarial attacks. The prevailing approaches for generating sparse adversarial attacks involve solving $\ell_{0}$-formulated problems, employing greedy

Figure: Figure 1: Adversarial examples generated by our algorithm. The first row depicts a targeted attack with the target label ‘‘water bottle’’, and the second row depicts an untargeted attack.
Refer to caption: /html/2311.17434/assets/1_original.png

single-pixel selection [], local search techniques [], utilizing evolutionary algorithms [], or relaxing $\ell_{0}$ via the $\ell_{1}$ ball and applying various algorithms to handle these structures [, ]. However, most of these methods only minimize the number of modified pixels and do not constrain the magnitude of the changed pixels. The perturbed pixels can thus exhibit substantial variations in intensity or colour compared to their surroundings, rendering them easily visible []. This has motivated the generation of adversarial attacks that are simultaneously sparse and imperceptible [, ]. Moreover, [] and [] pinpoint the necessity of imposing structure to sparse adversarial attacks by generating group-wise sparse perturbations that are targeted to the main objective in the image. This way the generated perturbations are also explainable, i.e., they perturb semantically meaningful pixels in the images. [Fig. 1](#S1.F1) illustrates successful group-wise sparse adversarial examples generated by our proposed algorithm (GSE). In summary, the exploration of group-wise sparse and explainable adversarial attacks has evolved into a highly practical and relevant area of research. This line of research illuminates an even more significant vulnerability of DNNs than conventionally conceived, while also offering valuable insights for interpreting DNN failures, as discussed in [].
Our main contributions are the following.

- 1.
We establish a novel optimization framework that combines non-convex regularization with Nesterov’s accelerated gradient descent (NAG) procedure to craft adversarial attacks that are group-wise sparse.
Our algorithmic foundation stems from an inventive fusion of the proximal gradient method outlined in [] with a novel technique to increase the likelihood of perturbing pixels that are close to the already perturbed pixels.
- 2.
Experiments conducted on the CIFAR-10 and NIPS2017 datasets underscore the superiority of our GSE (Group-wise Sparse and Explainable) attacks. In both targeted and untargeted attack scenarios, we surpass state-of-the-art methods, by requiring significantly fewer perturbations. For instance, we achieve a group-wise sparsity increase of $48.12\%$ on CIFAR-10 and an impressive $40.78\%$ increase on NIPS2017 (average case, targeted attack), all while maintaining smaller perturbation magnitudes and a remarkable $100\%$ attack success rate.
- 3.
Through a quantitative assessment of the alignment between perturbations and salient image regions, we underscore the value of GSE for interpretability analysis.

### 1.1 Related Work

Recent works have introduced methods for generating group-wise sparse and explainable adversarial attacks. StrAttack [] represents a structured sparse and explainable adversarial attack, relying on the alternating direction method of multipliers (ADMM). It enforces group-wise sparsity through a dynamic sliding mask designed to extract spatial structures from the image. FWnucl-group [], which we will abbreviate as FWnucl, is another structured sparse adversarial attack. It quantifies the perturbation’s proximity to benign images by utilizing the nuclear group norm, capitalizing on the convexity of nuclear group norm balls through the application of a Frank-Wolfe optimization scheme []. Homotopy-Attack [] is a sparse adversarial attack that operates based on the non-monotone accelerated proximal gradient algorithm (nmAPG) []. It can be extended to incorporate group-wise sparsity regularization by segmenting the image pixels using the SLIC superpixel algorithm and applying regularization using the resulting 2,0-‘‘norm’’. SAIF [] is an attack method that achieves sparsity and explainability. It employs the Frank-Wolfe algorithm [] for the joint optimization of the perturbation and a sparsity mask. We empirically compare our approach to the aforementioned attacks.

##### Interpretability.

A recent research area involves the integration of adversarial examples and model explanations, emphasizing the convergence of fundamental concepts in both domains. On simple datasets like MNIST, [] illustrates a hitting set duality between model explanations and adversarial examples. Another study shows the correspondence of attack perturbations with discriminative image features []. Our attack strategy involves perturbing regions neighbouring already perturbed pixels. Since we start with very sparse perturbations this results in a change of the most susceptible pixels of an image. In addition, we conduct empirical analysis to examine the overlap between our attacks and salient image regions. For the quantitative interpretability analysis we make use of the adversarial saliency map [, ] while for the visual analysis, we employ a class activation map as proposed in [].

## 2 Method

### 2.1 Problem Formulation

Consider $\mathcal{X}=[I_{\textnormal{min}},I_{\textnormal{max}}]^{M\times N\times C}$, which represents a set of feasible images. Here, $M$ and $N$ stand for the height and width of the image, while $C$ denotes the number of colour channels. Let $\mathbf{x}\in\mathcal{X}$ be a benign image with label $l\in\mathbb{N}$, and $t\in\mathbb{N}$ be a target label, where $t\neq l$. Additionally, let $\mathcal{L}:\mathcal{X}\times\mathbb{N}\rightarrow\mathbb{R}$ be a classification loss function, such as the cross-entropy loss, tailored for a given classifier $\mathcal{C}$. For the sake of simplicity, we assume $\mathbf{x}$ is vectorized.
Moreover, we introduce a distortion function $\mathcal{D}:\mathbb{R}^{M\times N\times C}\rightarrow\mathbb{R}_{\geq 0}$. The goal of a *targeted adversarial attack* is to find an image $\mathbf{x}_{\textnormal{adv}}$ to which $\mathcal{C}$ assigns the target label $t$ and that is in close proximity to $\mathbf{x}$ according to the function $\mathcal{D}$. In summary, the task of formulating a targeted adversarial example for the input $\mathbf{x}$ can be framed as

$$ $\displaystyle\min_{\mathbf{w}\in\mathbb{R}^{M\times N\times C}}\$ $\displaystyle\mathcal{L}(\mathbf{x}+\mathbf{w},t)+\lambda\mathcal{D}(\mathbf{w}),$ (1) $$

where $\lambda>0$. The targeted formulation of [Eq. 1](#S2.E1) can be adapted to generate *untargeted adversarial attacks* by maximizing the loss with respect to the true label $l$. Thus, in the untargeted scenario, we encounter the following problem

$$ $\displaystyle\min_{\mathbf{w}\in\mathbb{R}^{M\times N\times C}}\$ $\displaystyle-\mathcal{L}(\mathbf{x}+\mathbf{w},l)+\lambda\mathcal{D}(\mathbf{w}).$ $$

However, in the subsequent section, we focus on the targeted attack setting.

### 2.2 Quasinorm Regularizaton

Targeted sparse adversarial examples can be crafted by solving the quasinorm-regularized problem []

$$ $\displaystyle\min_{\mathbf{w}\in\mathbb{R}^{M\times N\times C}}\mathcal{L}(\mathbf{x}+\mathbf{w},t)+\lambda\|\mathbf{w}\|^{p}_{p},$ (2) $$

for $0<p<1$. Here $\|\mathbf{w}\|_{p}=\left(\sum_{i}|w_{i}|^{p}\right)^{\frac{1}{p}}$ is only a quasinorm since subadditivity is not satisfied for $p<1$. After successfully solving [Eq. 2](#S2.E2) and obtaining $\hat{\mathbf{w}}\in\operatorname*{\mathrm{arg\,min}}_{\mathbf{w}\in\mathbb{R}^{M\times N\times C}}\mathcal{L}(\mathbf{x}+\mathbf{w},t)+\lambda\|\mathbf{w}\|^{p}_{p}$, the resulting adversarial example can be expressed as

$$ $\displaystyle\mathbf{x}_{\textnormal{adv}}=\text{clip}_{\mathcal{X}}(\mathbf{x}+\hat{\mathbf{w}}).$ $$

To obtain $\hat{\mathbf{w}}$, we apply the forward-backward splitting algorithm, as detailed in [Algorithm 1](#alg1). In their work, [] derive a closed-form solution for the proximal operator of $\|\cdot\|_{p}^{p}$

$$ $\displaystyle\text{prox}_{\lambda\|\cdot\|_{p}^{p}}(\mathbf{w}):=\operatorname*{\mathrm{arg\,min}}_{\mathbf{y}\in\mathbb{R}^{M\times N\times C}}\frac{1}{2\lambda}\|\mathbf{y}-\mathbf{w}\|_{2}^{2}+\|\mathbf{y}\|_{p}^{p},$ (3) $$

for $p=\frac{1}{2}$. Given that $\|\cdot\|_{p}^{p}$ is separable, by [, Theorem 6.6] it is sufficient to deduce the characterization of $\text{prox}_{\lambda\|\cdot\|_{p}^{p}}$ in [Eq. 3](#S2.E3) when $MNC=1$. Each component is thus given by

$$ $\displaystyle\left[\text{prox}_{\lambda\|\cdot\|_{p}^{p}}(\mathbf{z})\right]_{i}=\frac{2}{3}z_{i}\left(1+\cos\left(\frac{2\pi}{3}-\frac{2\phi_{2\lambda}z_{i}}{3}\right)\right)\mathbbm{1}_{S}(i),$ (4) $$

where

$$ $\begin{gathered}\phi_{2\lambda}=\arccos\left(\frac{2\lambda}{8}\left(\frac{|z_{i}|}{3}\right)^{-\frac{3}{2}}\right),\\ g(2\lambda)=\frac{\sqrt[3]{54}}{4}(2\lambda)^{\frac{2}{3}},\ S=\{i\ :\ |z_{i}|>g(2\lambda)\}.\end{gathered}$ $$

Figure: Algorithm 1 Forward-Backward Splitting Attack

### 2.3 Group-wise Sparsity

In this section, we propose a method for generating group-wise sparse adversarial examples while ensuring a small perturbation magnitude, with $\mathcal{D}=\|\cdot\|_{2}$ in [Eq. 1](#S2.E1). To induce group-wise sparsity in the perturbation vector $\mathbf{w}$, we apply the $1/2$-quasinorm regularization to compute a subspace $V$ within $\mathbb{R}^{M\times N\times C}$, which enforces group-wise sparsity as a constraint. To identify such a subspace, we use a vector of tradeoff parameters $\mathbf{\lambda}\in\mathbb{R}_{\geq 0}^{M\times N\times C}$ for the $1/2$-quasinorm regularization term, allowing us to adjust each entry individually. We reduce $\lambda_{i,j,:}$ for pixels located in proximity to already perturbed pixels, thereby making them more amenable to perturbation. This operation is denoted as $\text{prox}_{\lambda\|\cdot\|_{p}^{p}}(\mathbf{z})$. Due to [Eq. 4](#S2.E4), we can formally define

$$ $\displaystyle\left[\text{prox}_{\lambda\|\cdot\|_{p}^{p}}(\mathbf{z})\right]_{i}:=\left[\text{prox}_{\lambda_{i}\|\cdot\|_{p}^{p}}(\mathbf{z})\right]_{i},$ $$

for $\mathbf{\lambda}\in\mathbb{R}_{\geq 0}^{M\times N\times C}$. Having computed an iterate $\mathbf{w}^{(k)}$ by forward-backward splitting with Nesterov momentum as shown in [Algorithm 2](#alg2), we adjust $\mathbf{\lambda}^{(k)}$ as follows (AdjustLambda in [Algorithm 2](#alg2)). First, we build a mask

$$ $\displaystyle\mathbf{m}=\text{sign}\left(\sum_{c=1}^{C}|\mathbf{w}^{(k)}|_{:,:,c}\right)\in\{0,1\}^{M\times N},$ (5) $$

to identify perturbed pixels. Next, we perform a 2D convolution on $\mathbf{m}$ using a square Gaussian blur kernel $\mathbf{K}\in\mathbb{R}^{n\times n}$ with appropriate padding, yielding a matrix

$$ $\displaystyle\mathbf{M}=\mathbf{m}**\mathbf{K}\in[0,1]^{M\times N},$ $$

where entries with indices close to non-zero entries in $\mathbf{m}$ are non-zero. Assuming $n$ is odd and setting $\hat{n}=\lfloor\frac{n}{2}\rfloor$ the convolution is defined as

$$ $\displaystyle\left[\mathbf{m}**\mathbf{K}\right]_{i,j}=\sum_{k=-\hat{n}}^{\hat{n}}\sum_{l=-\hat{n}}^{\hat{n}}\mathbf{K}_{k+\hat{n}+1,l+\hat{n}+1}\cdot\mathbf{m}_{i+k,j+l}.$ $$

Our next step involves the build of a matrix $\overline{\mathbf{M}}\in\mathbb{R}^{M\times N}$ with

$$ $\displaystyle\overline{\mathbf{M}}_{ij}=\begin{cases}\mathbf{M}_{ij}+1,\ \ &\text{if}\ \mathbf{M}_{ij}\neq 0,\\ q,\ \ &\text{else},\end{cases}$ $$

where $0<q\leq 1$. When $q<1$, we increase the tradeoff parameters for pixels situated at a distance from those previously perturbed. Next, we compute the tradeoff parameters for the following iteration

$$ $\displaystyle\lambda^{(k+1)}_{i,j,:}=\frac{\lambda^{(k)}_{i,j,:}}{\overline{\mathbf{M}}_{i,j}}.$ $$

In this manner, we expand regions with lower tradeoff parameters over a specified $\hat{k}$ iterations. It is crucial to highlight that our method operates independently of predefined structures, such as pixel partitions. In all subsequent iterations, we employ projected NAG to approximate a solution to a simplified problem

$$ $\displaystyle\min_{\mathbf{w}\in V}\mathcal{L}(\mathbf{x}+\mathbf{w},t)+\mu\|\mathbf{w}\|_{2},$ (6) $$

where $\mu>0$ serves as a tradeoff parameter and

$$ $\displaystyle V:=\text{span}(\{e_{i,j,c}\ |\ \lambda_{i,j,c}^{(\hat{k})}<\lambda_{i,j,c}^{(0)}\})\subseteq\mathbb{R}^{M\times N\times C},$ $$

is a subspace spanned by standard unit vectors $e_{i,j,c}$. As $V$ is spanned by these standard unit vectors, we can express the projection onto $V$ as

$$ $\displaystyle\left[P_{V}(\mathbf{w})\right]_{i,j,c}=\begin{cases}\mathbf{w}_{i,j,c},\ \ &\text{if}\ e_{i,j,c}\in V,\\ 0,\ \ &\text{otherwise}.\end{cases}$ $$

In the following iterations, perturbations will only affect pixels at coordinates $(i,j)$ with tradeoff parameters $\lambda_{i,j,:}^{(\hat{k})}$ below the initial $\lambda$. Due to [Eq. 5](#S2.E5), it follows that $e_{i,j,c}\in V$ for all channels $c$ of a perturbed pixel at $(i,j)$, meaning most often all channels of the pixel will be perturbed. This process is succinctly outlined in [Algorithm 2](#alg2), where we introduce the sequence $\alpha_{k}$ as described in []

$$ $\displaystyle\beta_{0}=0,\ \beta_{k}=\frac{1+\sqrt{1+4\beta^{2}_{k-1}}}{2},\ \alpha_{k}=\frac{1-\beta_{k}}{\beta_{k+1}}.$ $$

In our tests, we initially perform a section search to find the maximum $\lambda$ where $\tilde{\mathbf{w}}^{(1)}\neq\mathbf{0}$. Subsequently, we conduct another section search to determine the appropriate $\lambda$ at which the attack succeeds.

Figure: Algorithm 2 Group-Wise Sparse Attack

### 2.4 Equivalence to NAG of unconstrained problems

Consider $d=MNC$, where our image $\mathbf{x}\in[I_{\textnormal{min}},I_{\textnormal{max}}]^{d}$ is vectorized. Let $\mathcal{I}$ denote the set that encompasses indices corresponding to entries with $\lambda_{i,j,c}^{(\hat{k})}\geq\lambda_{i,j,c}^{(0)}$ after $\hat{k}$ iterations. Also, let $m:=|\mathcal{I}|<d$. With these considerations, we can formulate the optimization problem in [Eq. 6](#S2.E6), which arises following iteration $\hat{k}$, as

$$ $\displaystyle\min_{\mathbf{w}}$ $\displaystyle\mathcal{L}(\mathbf{x}+\mathbf{w},t)+\mu\|\mathbf{w}\|_{2}$ (7) s.t. $\displaystyle A\mathbf{w}=0,$ $$

where $A\in\{0,1\}^{m\times d}$ has rows

$$ $\displaystyle(\underbrace{0,...,0,}_{i-1\ \text{times}}1,\underbrace{0,...,0}_{d-i\ \text{times}}),\quad\forall i\in\mathcal{I}.$ (8) $$

We can eliminate the equality constraints using the nullspace method. Let $H\in\mathbb{R}^{d\times d}$ be an orthogonal matrix and $R\in\mathbb{R}^{m\times m}$ an upper triangular matrix, obtained by QR-decomposition of $A^{\top}$, i.e.,

$$ $\displaystyle HA^{\top}=\begin{pmatrix}R\\ 0\end{pmatrix}.$ (9) $$

Further let $H=(Y,Z)^{\top}$, where $Y^{\top}\in\mathbb{R}^{m\times d}$ contains the first $m$ rows of $H$ and $Z\in\mathbb{R}^{d\times d-m}$. Because an orthogonal matrix $H$ possesses full rank, both $Y$ and $Z$ also exhibit full rank. Hence we can uniquely write any $\mathbf{w}\in\mathbb{R}^{d}$ as

$$ $\displaystyle\mathbf{w}=Y\mathbf{w}_{y}+Z\mathbf{w}_{z}=H^{\top}\begin{pmatrix}\mathbf{w}_{y}\\ \mathbf{w}_{z}\end{pmatrix},$ $$

with $\mathbf{w}_{y}\in\mathbb{R}^{m},\mathbf{w}_{z}\in\mathbb{R}^{d-m}$. In particular, for any $\mathbf{w}\in\ker A$ we have

$$ $\displaystyle 0=A\mathbf{w}=AH^{\top}\begin{pmatrix}\mathbf{w}_{y}\\ \mathbf{w}_{z}\end{pmatrix}=(R^{\top},0)\begin{pmatrix}\mathbf{w}_{y}\\ \mathbf{w}_{z}\end{pmatrix}=R^{\top}\mathbf{w}_{y}.$ $$

Given [Eqs. 8](#S2.E8) and [9](#S2.E9), we can establish that both $A$ and $R$ possess rank $m$. Consequently, we can represent any $\mathbf{w}\in\ker A$ as $Z\mathbf{w}_{z}$, where $\mathbf{w}_{z}\in\mathbb{R}^{d-m}$. This allows us to formulate an unconstrained problem equivalent to [Eq. 7](#S2.E7)

$$ $\displaystyle\min_{\mathbf{z}\in\mathbb{R}^{d-m}}\ \$ $\displaystyle\mathcal{L}(\mathbf{x}+Z\mathbf{z},t)+\mu\|Z\mathbf{z}\|_{2}.$ (10) $$

Setting $f(\mathbf{w})=\mathcal{L}(\mathbf{x}+\mathbf{w},t)+\mu\|\mathbf{w}\|_{2}$ and $F(\mathbf{z})=f(Z\mathbf{z})$ we get from the update step of NAG

$$ $\displaystyle\mathbf{w}_{k+1}$ $\displaystyle=Z\mathbf{z}_{k+1}$ $\displaystyle=Z\Big{(}(1-\alpha_{k})\left(\mathbf{z}^{(k)}-\sigma\nabla F(\mathbf{z}^{(k)})\right)+\alpha_{k}\left(\mathbf{z}^{(k-1)}-\sigma\nabla F(\mathbf{z}^{(k-1)})\right)\Big{)}$ $\displaystyle=(1-\alpha_{k})\left(\mathbf{w}^{(k)}-\sigma ZZ^{\top}\nabla f(\mathbf{w}^{(k)})\right)+\alpha_{k}\left(\mathbf{w}^{(k-1)}-\sigma ZZ^{\top}\nabla f(\mathbf{w}^{(k-1)})\right)$ $\displaystyle=(1-\alpha_{k})\left(\mathbf{w}^{(k)}-\sigma P_{V}(\nabla f(\mathbf{w}^{(k)}))\right)+\alpha_{k}\left(\mathbf{w}^{(k-1)}-\sigma P_{V}(\nabla f(\mathbf{w}^{(k-1)}))\right)$ $\displaystyle=P_{V}\Big{(}(1-\alpha_{k})\left(\mathbf{w}^{(k)}-\sigma\nabla f(\mathbf{w}^{(k)})\right)+\alpha_{k}\left(\mathbf{w}^{(k-1)}-\sigma\nabla f(\mathbf{w}^{(k-1)})\right)\Big{)},$ $$

where the last equality holds since $\mathbf{w}^{(k)},\mathbf{w}^{(k-1)}\in V$. Hence the projected NAG in [Algorithm 2](#alg2) has the same properties as NAG solving the unconstrained problem in [Eq. 10](#S2.E10), and thus converges as such.

## 3 Experiments

We now demonstrate the effectiveness of our proposed GSE attack for crafting group-wise sparse adversarial attacks. [Secs. 3.1](#S3.SS1) and [3.2](#S3.SS2) outline our experimental setups and define the relevant comparing metrics, while [Secs. 3.3.1](#S3.SS3.SSS1) and [3.3.2](#S3.SS3.SSS2) systematically compare our approach with multiple previous state-of-the-art (SOTA) group-wise sparse adversarial attacks, including FWnucl [], Homotopy-Attack [], and StrAttack []. Additionally, [Secs. 3.3.3](#S3.SS3.SSS3), [3.3.4](#S3.SS3.SSS4) and [3.3.5](#S3.SS3.SSS5) cover ablation studies regarding the explainability of our group-wise sparse attacks, visualizations, and empirical time costs.

### 3.1 Setup

We run comprehensive experiments on the NIPS2017(^*^**[https://www.kaggle.com/competitions/nips-2017-defense-against-adversarial-attack/data](https://www.kaggle.com/competitions/nips-2017-defense-against-adversarial-attack/data)) and CIFAR-10 [] datasets. NIPS2017 consists of $1,000$ images of size $299\times 299\times 3$ on which we test the attacks against a ResNet50 [] and a VGG19 [] ImageNet classifier. CIFAR-10 comprises images of size $32\times 32\times 3$ and is split into a training set consisting of 50,000 images, where we train a ResNet20 classifier []. Additionally, there is a test set comprising 10,000 images on which we perform our experiments. In our attack configuration, we fix the Gaussian blur kernel size at $5$ for both datasets. Specifically, for CIFAR-10, we set $q=0.25$, $\sigma=0.0025$, $\mu=1$, and $\hat{k}=30$, while for NIPS2017, we configure it with $q=0.9$, $\sigma=0.025$, $\mu=0.1$, and $\hat{k}=50$. Regarding StrAttack, we modify the authors’ implementation to be compatible with the PyTorch framework, employing the parameters recommended in [], specifically those from Appendix F. For FWnucl, we develop an implementation for the nuclear group norm attack using PyTorch, setting $\varepsilon=5$. We run all three attacks for a total of 200 iterations. For the Homotopy-Attack, we adjust the authors’ implementation to support group-wise sparsity, as outlined in [], and we follow their recommended parameter settings. All tests are run on a machine with an NVIDIA Tesla T4 GPU. Our codes are available at [https://github.com/wagnermoritz/GSE](https://github.com/wagnermoritz/GSE).

### 3.2 Evaluation

Consider a set of $n$ images $(\mathbf{x}^{(i)})_{0<i\leq n}$ and the corresponding perturbations $(\delta^{(i)})_{0<i\leq n}$, where $\mathbf{x}^{(i)},\mathbf{x}^{(i)}+\delta^{(i)}\in\mathcal{X}$. Among these, let $m\leq n$ denote the number of successfully generated adversarial examples $\mathbf{x}^{(i)}+\delta^{(i)}$. We define the attack success rate (ASR) as

$$ $\displaystyle\text{ASR}=\frac{m}{n},$ $$

and the average number of changed pixels (ACP) via

$$ $\displaystyle\text{ACP}=\frac{1}{n}\sum_{i=1}^{n}\frac{\|\Delta^{(i)}\|_{0}}{MN},\ \ \ \Delta^{(i)}=\sum_{c=1}^{C}|\delta^{(i)}_{[:,:,c]}|\in\mathbb{R}^{M\times N}.$ $$

We determine the number of perturbed pixel clusters in $\mathbf{x}^{(i)}+\delta^{(i)}$ by creating a mask

$$ $\displaystyle\mathbf{m}^{(i)}=\text{sign}\left(\sum_{c=1}^{C}|\delta^{(i)}_{[:,:,c]}|\right)\in\{0,1\}^{M\times N},$ $$

and then running depth-first search (DFS) on that mask, treating adjacent 1-entries as neighbouring nodes. We rerun DFS starting from every 1-entry that another DFS run has not yet discovered. The number of DFS runs until all 1-entries are discovered is the number of clusters. Finally, we compute the average number of clusters (ANC) for our $m$ adversarial examples.
Now, consider $\mathbf{x}\in\mathbb{[}I_{\textnormal{min}},I_{\textnormal{max}}]^{d}$ as a vectorized image and let $Z(\mathbf{x})$ represent the logits of a classifier. The *adversarial saliency map (ASM)* [, ] is defined as follows

$$ $\begin{gathered}\text{ASM}(\mathbf{x},t)[i]=\left(\frac{\partial Z(\mathbf{x})_{t}}{\partial\mathbf{x}_{i}}\right)\left|\frac{\partial Z(\mathbf{x})_{l}}{\partial\mathbf{x}_{i}}\right|\mathbbm{1}_{S}(i),\\ S=\left\{i\in\{1,...,d\}\ \bigg{|}\ \frac{\partial Z(\mathbf{x})_{t}}{\partial\mathbf{x}_{i}}\geq 0\ \text{or}\ \frac{\partial Z(\mathbf{x})_{l}}{\partial\mathbf{x}_{i}}\leq 0\right\}.\end{gathered}$ $$

The metric $\text{ASM}(\mathbf{x},t)\in\mathbb{R}_{\geq 0}^{d}$ provides a measure of importance for each pixel. It is worth noting that a higher ASM value signifies greater pixel significance. We compute a binary mask $\mathbf{B}_{ASM}\in\{0,1\}^{d}$ by

$$ $\displaystyle\mathbf{B}_{ASM}[i]=\begin{cases}1,\ \ &\text{if}\ \text{ASM}(\mathbf{x},t)[i]>\nu,\\ 0,\ \ &\text{otherwise},\end{cases}$ $$

where $\nu$ is some percentile of the entries of $\text{ASM}(\mathbf{x},t)$. Given an adversarial perturbation $\mathbf{\delta}\in\mathbb{R}^{d}$, we can now compute the interpretability score (IS) as

$$ $\displaystyle\text{IS}(\mathbf{\delta})=\frac{\|\mathbf{B}_{ASM}\odot\mathbf{\delta}\|_{2}}{\|\mathbf{\delta}\|_{2}}.$ $$

Note that when $\text{IS}(\mathbf{\delta})$ approaches $1$, the perturbation primarily targets pixels crucial for the class prediction of the model. Conversely, IS scores nearing zero do not lend themselves to meaningful interpretation based on ASM scores. Let $\mathcal{C}$ be a convolutional neural network classifier and $f_{k}[i,j]$ be the activation of the unit $k$ at the coordinates $(i,j)$ in the last convolutional layer of $\mathcal{C}$ evaluated at $\mathbf{x}$. Then, using global average pooling after the last convolutional layer, the input to the softmax corresponding to label $l$ is

$$ $\displaystyle\sum_{k}w_{k}^{l}\sum_{i,j}f_{k}[i,j]=\sum_{i,j}\sum_{k}w_{k}^{l}f_{k}[i,j],$ $$

where $w_{k}^{l}$ are the weights corresponding to the label ${l}$ for unit $k$. Since $w_{k}^{l}$ indicate the importance of $\sum_{i,j}f_{k}[i,j]$ for class $l$, the *class activation map (CAM)* [] is defined by

$$ $\displaystyle\text{CAM}_{l}[i,j]=\sum_{k}w_{k}^{l}f_{k}[i,j],$ $$

and directly indicates the importance of activation at $(i,j)$ for the classification of $\mathbf{x}$ as class ${l}$.
To make the comparison of $\text{CAM}_{l}$ and $\mathbf{x}$ easier, the resulting class activation map is upscaled to the size of $\mathbf{x}$ using bicubic interpolation.
The value $\|\delta\|_{2,0}$ for a perturbation $\delta$, as proposed in [], heavily depends on the pixel partitioning method. To measure the group-wise sparsity of a perturbation, we propose a function that considers all $n$ by $n$ pixel patches of an image instead of only a subset that results in a partition. In our experiments, we set $n=8$. Let $\delta\in\mathbb{R}^{M\times N\times C}$, $n<M,N$, and let $\mathcal{G}=\{G_{1},...,G_{k}\}$ be a set containing the index sets of all overlapping $n$ by $n$ patches in $\delta$. Then we define

$$ $\displaystyle d_{2,0}(\delta):=\left|\left\{i\ :\ \|\delta_{G_{i}}\|_{2}\neq 0,\ i=1,...,k\right\}\right|.$ $$

We evaluate all attacks on these metrics in the untargeted and in the targeted setting. For CIFAR-10, the targeted attacks are performed with respect to each wrong label. For the evaluation of the attacks on ImageNet models, we choose ten target labels for each image by randomly choosing ten distinct numbers $a_{1},...,a_{10}\in\{1,...,999\}$ and defining the target labels $t_{i}$ for an image with the true label $l$ by $t_{i}=l+a_{i}\mod 1000$. In the targeted setting, as suggested in [], we give three versions of each metric: best, average, and worst case. For the best and worst case, we take the best and worst results, respectively, obtained from the targeted attacks for each image. For the average case, we take the mean of all results.

### 3.3 Results

**Table 1: Comparison of our attack and the Homotopy-Attack on a ResNet20 classifier for CIFAR-10. The perturbations for both attacks were computed for all images sequentially. Due to the extensive computation time required by the Homotopy-Attack, we tested on a limited sample size of 100.**
|  | Attack | ASR | ACP | ANC | $\ell_{2}$ | $d_{2,0}$ | Time |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Untargeted | GSE (Ours) | 100% | 38.0 | 1.6 | 0.71 | 178 | 9.9s |
| Homotopy | 100% | 72.5 | 2.5 | 0.64 | 253 | 1751s |  |
| Targeted | GSE (Ours) | 100% | 96.9 | 2.4 | 1.28 | 300 | 11.8s |
| Homotopy | 100% | 104 | 3.7 | 1.22 | 371 | 1812s |  |

**Table 2: Untargeted attacks performed on a ResNet20 classifier for CIFAR-10, a VGG19 and a ResNet50 classifier for ImageNet/NIPS2017. Tested on 1,000 samples from each dataset.**
|  | Attack | ASR | ACP | ANC | $\ell_{2}$ | $d_{2,0}$ |
| --- | --- | --- | --- | --- | --- | --- |
| CIFAR-10<br>ResNet20 | GSE (Ours) | 100% | 36.8 | 1.5 | 0.75 | 177 |
| StrAttack | 100% | 117 | 4.7 | 1.07 | 419 |  |
| FWnucl | 95.1% | 456 | 1.3 | 2.00 | 592 |  |
| NIPS2017<br>VGG19 | GSE (Ours) | 100% | 968 | 6.7 | 1.25 | 2596 |
| StrAttack | 100% | 4021 | 7.4 | 1.92 | 7058 |  |
| FWnucl | 89.1% | 7225 | 2.1 | 2.40 | 7985 |  |
| NIPS2017<br>ResNet50 | GSE (Ours) | 100% | 1270 | 8.2 | 1.47 | 2922 |
| StrAttack | 100% | 8669 | 12.9 | 2.51 | 13963 |  |
| FWnucl | 48.6% | 14953 | 3.7 | 1.82 | 17083 |  |

As evidenced in [Tab. 1](#S3.T1), our method significantly outperforms the Homotopy-Attack [] in both targeted and untargeted attacks on CIFAR-10. It is worth noting that the only metric where Homotopy-Attack surpasses our method is the $2$-norm perturbation magnitude. However, this metric is of secondary importance in the group-wise sparse attack setting.
In contrast, our method excels in achieving an increase in overall sparsity and group-wise sparsity, all while substantially reducing the cluster count and the computation time by two orders of magnitude. Hence, we will exclude Homotopy-Attack from our subsequent experiments.

**Table 3: Targeted attacks performed on a ResNet20 classifier for CIFAR-10, a VGG19 and a ResNet50 classifier for ImageNet/NIPS2017. Tested on 1,000 samples from each dataset.**
|  |  | Best case | Average case | Worst case |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Dataset | Attack | ASR | ACP | ANC | $\ell_{2}$ | $d_{2,0}$ | ASR | ACP | ANC | $\ell_{2}$ | $d_{2,0}$ | ASR | ACP | ANC | $\ell_{2}$ | $d_{2,0}$ |
| CIFAR-10<br>ResNet20 | GSE (Ours) | 100% | 29.6 | 1.2 | 0.69 | 151 | 100% | 80.1 | 2.1 | 1.17 | 276 | 100% | 148 | 3.5 | 1.62 | 413 |
| StrAttack | 100% | 75.4 | 2.2 | 0.79 | 336 | 100% | 232 | 5.4 | 1.96 | 532 | 100% | 430 | 9.0 | 4.72 | 620 |  |
| FWnucl | 100% | 276 | 1.0 | 1.44 | 504 | 82.8% | 384 | 1.6 | 2.32 | 567 | 35.0% | 471 | 2.8 | 3.78 | 602 |  |
| NIPS2017<br>VGG19 | GSE (Ours) | 100% | 1974 | 4.9 | 2.72 | 3695 | 100% | 6025 | 10.5 | 3.58 | 9704 | 100% | 15996 | 17.2 | 4.39 | 21489 |
| StrAttack | 100% | 3616 | 3.6 | 2.85 | 5863 | 100% | 10940 | 11.0 | 3.70 | 16545 | 100% | 23245 | 19.9 | 5.48 | 32193 |  |
| FWnucl | 56.1% | 4489 | 1.3 | 2.91 | 5783 | 18.3% | 7133 | 1.9 | 3.92 | 11639 | 0.0% | N/A | N/A | N/A | N/A |  |
| NIPS2017<br>ResNet50 | GSE (Ours) | 100% | 2090 | 3.8 | 2.51 | 3498 | 100% | 7311 | 9.5 | 3.15 | 10734 | 100% | 16284 | 15.9 | 3.65 | 21872 |
| StrAttack | 100% | 6117 | 4.0 | 2.73 | 9246 | 100% | 15308 | 12.1 | 4.17 | 21182 | 100% | 26569 | 20.5 | 7.88 | 33297 |  |
| FWnucl | 32.4% | 9897 | 3.4 | 2.82 | 11134 | 12.6% | 11735 | 6.3 | 3.96 | 18126 | 0.0% | N/A | N/A | N/A | N/A |  |

Figure: Figure 2: Visual comparison of successful untargeted adversarial instances generated by our attack, StrAttack, and FWnucl. Adversarial examples are shown in the top row, perturbed pixels highlighted in red in the middle row, and the perturbations in the bottom row. The target model is a ResNet50. The perturbations are enhanced for visibility.
Refer to caption: /html/2311.17434/assets/original.png

Figure: Figure 3: Targeted adversarial examples generated by GSE. The target is ‘‘airship’’ for the first two rows, and ‘‘golf cart’’ for the last two rows. The attacked model is a VGG19. The perturbations are enhanced for visibility.
Refer to caption: /html/2311.17434/assets/snail_original.png

#### 3.3.1 Untargeted Attack

[Tab. 2](#S3.T2) displays the results of untargeted attacks on CIFAR-10 and NIPS2017 datasets. Notably, our method and StrAttack attain a 100% ASR in both cases. Furthermore, our algorithm significantly outperforms other attacks in terms of ACP. Specifically, on average, our algorithm achieves $3.6\%$ sparsity on CIFAR-10 images and $1.5\%$ on NIPS2017 images when attacking a VGG19 classifier. The only metric where other SOTA methods outperform GSE is
the ANC. Nevertheless, this advantage remains insignificant when considering the considerably lower values of ACP achieved by our method. Furthermore, as observed from the $d_{2,0}$ metric, our method attains an exceptionally high level of group-wise sparsity. To be precise, we attain a remarkable increase of group-wise sparsity by $57.76\%$ on CIFAR-10 and $63.22\%$ on NIPS2017 when attacking a VGG19 classifier, in comparison to the SOTA. Notably, we accomplish this while preserving the minimal magnitude of attacks, as measured by the $2$-norm. To further substantiate the effectiveness of our method on the NIPS2017 dataset, we replicate the previous experiments with a stronger backbone classifier - ResNet50. The results in [Tab. 2](#S3.T2) demonstrate that our algorithm surpasses SOTA by a substantial margin. Specifically, our algorithm achieves a remarkable increase of $85.35\%$ in sparsity and $79.08\%$ in group-wise sparsity, while also attaining the lowest perturbation norm.

#### 3.3.2 Targeted Attack

The results for targeted attacks on CIFAR-10 and NIPS2017 datasets are presented in [Tab. 3](#S3.T3). While our method and StrAttack attain a perfect ASR in both cases, FWnucl results in a $0\%$ worst-case ASR on the NIPS2017 dataset. This implies that for every tested NIPS2017 image, the worst-case target label results in an unsuccessful FWnucl attack, consequently yielding no values for FWnucl’s worst-case metrics. When examining the ACP, it becomes evident that our algorithm yields the sparsest perturbations, changing on average only $7.8\%$ of the pixels in the CIFAR-10 images and a mere $9.2\%$ $(11.2\%)$ of the pixels in the NIPS2017 images when attacking a VGG10 (ResNet50) classifier. Moreover, it is clear from the $d_{2,0}$ metric that our method achieves a remarkable group-wise sparsity. On average, we demonstrate a significant decrease of $d_{2,0}$ by $48.13\%$ on CIFAR-10 and $16.63\%$ $(40.78\%)$ on NIPS2017 when attacking a VGG19 (ResNet50) classifier, while still having the lowest magnitude of the attacks, measured by the $2$-norm. Similarly to [Sec. 3.3.1](#S3.SS3.SSS1), the only metric other SOTA methods outperform GSE is the number of clusters. However, this is still insignificant considering, amongst others, the high ACP as well as the low ASR compared to our method.

#### 3.3.3 Visualization

We display the visualizations for untargeted group-wise sparse adversarial examples in [Fig. 2](#S3.F2), while [Fig. 3](#S3.F3) presents those for targeted group-wise sparse adversarial examples. Using the CAM technique [], we demonstrate the alignment between our algorithm’s perturbations and localized, class-specific discriminative regions within the images. Clearly, the generated perturbations effectively encompass the most discriminative areas of the objects, a testament to our algorithm’s impressive achievement of interpretability.

#### 3.3.4 Interpretability Evaluation

[Fig. 4](#S3.F4) illustrates the IS metric for the targeted attacks across various percentiles of ASM scores for samples from the CIFAR-10 and NIPS2017 datasets. Notably, the figure highlights that our method consistently achieves higher IS scores compared to other group-wise sparse attacks, especially for higher percentiles $\nu$. This shows that the perturbations generated by GSE are more focused on the most salient regions of the image. In addition, we have incorporated the recently proposed SAIF method [], which aims to establish a strong correlation between the generated perturbations and the salient regions within an image. SAIF surpasses our attack on the NIPS2017 dataset, specifically for percentiles at or above the 80th. This advantage may be attributed, in part, to SAIF’s lack of group-wise sparsity, allowing it to have greater overlap with the non-group-wise sparse ASM at higher percentiles. We omitted SAIF from our previous tables due to its poor group-wise sparse nature.

Figure: Figure 4: IS vs. percentile $\nu$ for targeted versions of our attack, StrAttack, FWnucl, and SAIF. Evaluated on a CIFAR-10 ResNet20 classifier (a), and an ImageNet VGG19 classifier (b).

#### 3.3.5 Speed Comparison

In this section, we conduct a runtime comparison between our algorithm and SOTA methods, with the results summarized in [Tab. 4](#S3.T4). Notably, our algorithm demonstrates significantly faster performance compared to FWnucl [] and StrAttack []. This speed advantage stems partially from the method used to enforce group-wise sparsity. StrAttack calculates the Euclidean norm of each group of pixels in every iteration and integrates this outcome as regularization using ADMM. FWnucl, on the other hand, computes a solution for a nuclear group-norm LMO in each iteration. In contrast, our attack initially computes a solution for the $1/2$-quasinorm proximal operator in the first $\hat{k}$ iterations. Subsequently, the attack transitions to projected NAG with 2-norm regularization, which is less computationally costly than the methods employed by both StrAttack and FWnucl.

**Table 4: Comparison of empirical attack computation time per image. In every experiment, all attacks utilize the same batch size.**
|  | Untargeted | Targeted |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | CIFAR-10 | ImageNet | CIFAR-10 | ImageNet |  |  |
| Attack | ResNet20 | ResNet50 | VGG19 | ResNet20 | ResNet50 | VGG19 |
| GSE (Ours) | 0.39s | 23.8s | 38.9s | 0.39s | 20.1s | 40.8s |
| StrAttack | 1.33s | 48.9s | 78.2s | 1.28s | 49.2s | 75.5s |
| FWnucl | 0.80s | 32.4s | 67.1s | 0.82s | 31.9s | 65.8s |

## 4 Conclusion

In this paper, we introduced ‘‘GSE’’, a novel algorithm for generating group-wise sparse and explainable adversarial attacks. Our approach is rooted in proximal gradient methods for non-convex programming, featuring additional control over changed pixels, and the use of projected NAG technique to solve optimization problems. Extensive experiments validate that GSE excels in producing group-wise sparse and explainable adversarial perturbations, all while simultaneously exhibiting the highest level of sparsity and the shortest computation time. Moreover, GSE excels over existing approaches in terms of quantitative metrics for interpretability and offers transparency for visualizing the vulnerabilities inherent in DNNs.

### 4.1 Social Impact

Adversarial attacks lay bare the vulnerability of DNNs. Our goal is to showcase the feasibility of crafting group-wise sparse and explainable adversarial attacks for natural images. This endeavour not only establishes a new benchmark for the research community to evaluate the robustness of deep learning algorithms but also suggests a simple defense strategy: employing the adversarial examples generated by GSE in adversarial training. For more sophisticated solutions, we advocate further exploration.

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. How does the proposed coefficient tuning strategy perform in terms of attack effectiveness when combined with different sparsity-inducing regularizations, such as L0-norm, L1-norm, and 1/2-quasinorm?

2. Could the authors provide additional details on how Eq. 4 is derived from Eq. 3? Additionally, could the authors explain why the Lp-norm (p=1/2) is considered a separable function?

3. Compared to other sparse attacks (e.g., StrAttack, Homotopy-Attack) that provide a clear mathematical formulation of group sparsity, could the authors offer additional details on how sparse pixels in the adversarial example are grouped during the two-phase perturbation training process?

4. How does the performance of other sparse attacks, using their default iteration settings, compare to that of the proposed GSE attack in this paper? 

5. What is the transferability performance of different sparse attacks in the black-box setting? Does the proposed GSE attack still achieve a higher ASR?
soundness: 2
strengths: 1. Compared to existing methods that use L0 or L1 regularization, this paper presents a sparse adversarial attack based on 1/2-quasinorm regularization. Building on this, an effective heuristic approach for tuning the regularization hyperparameter is introduced to select the most important pixels.

2. For the selected pixels, a projected Nesterov’s accelerated gradient descent algorithm is introduced to solve the L2-norm constrained problem, thereby ensuring low-magnitude sparse adversarial examples.

3. Experimental results conducted on multiple white-box models in both targeted and untargeted attack settings demonstrate that the proposed GSE method achieves better attack effectiveness and efficiency compared to other sparse attack methods.
summary: In this paper, the authors propose a two-stage approach for generating group-wise sparse and explainable adversarial examples. To enhance the attack performance, they introduce 1/2-quasinorm regularization and sparse hyperparameter tuning methods to select key group-wise sparse pixels. After that, the coordinate and magnitude of these selected pixels are further refined using Nesterov’s Accelerated Gradient Descent (NAG) to produce the sparse adversarial example. Experiments on multiple CNN and ViT networks using the CIFAR and ImageNet benchmark datasets demonstrate the effectiveness and efficiency of the proposed group-wise sparse and explainable attack compared to baseline sparse attack methods.
weaknesses: 1. The motivation behind the proposed 1/2-quasinorm regularization is not clearly explained. Compared to existing L0- or L1-norm based sparse attacks, what advantages does 1/2-quasinorm regularization offer for crafting sparse adversarial examples? Additionally, why not consider combining L0- or L1-norm based regularization with the proposed coefficient tuning strategy?

2. The derivation between Eq. 3 and Eq. 4 appears problematic, as it should rely on separable proximal functions. However, unlike the L1-norm, the Lp-norm is not a separable function, particularly when p=1/2. 

3. The authors claim to introduce a group-wise sparse attack. However, Sections 2.1-2.2 lack a clear mathematical description of how the selected sparse pixels are grouped, resulting in ambiguity regarding the concept of group-wise sparse attack.

4. The evaluation of attack performance lacks comprehensiveness. For example, while sparse attacks are applied to white-box models, their transferability in a black-box attack setting is not considered, which is arguably a more practical scenario. Additionally, all attacks are performed using 200 iterations, which is inconsistent with the settings used in previous sparse attack methods.

5. The evaluation metrics are not clearly explained. First, since different sparse attack methods may generate distinct sets of successful adversarial examples when ASR is below 100%, the ACP metric defined in Eq. 15 becomes difficult to compare across methods. Second, while Eq. 16 introduces the d_{2,0} metric, the definition of “overlapped patches” is not provided, adding to the ambiguity.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 2
questions: 1. Why is it necessary for adversarial attacks to be explainable? More specifically, why should the attacks follow a particular structure? Insights from the shortcut-learning paper suggest that DNNs may learn features differently than humans. Is the structure of group-based attacks intended to align more closely with human interpretation?
2. What are the benefits of explainable attacks compared to non- or less-explainable ones?
3. Could the authors explain in greater detail why the proposed method outperforms previous attacks in terms of speed (Table 1)? Were consistent parameter settings used across methods, such as the number of iterations \(\hat{k}\) and \(K\)? In my opinion, the most time-intensive steps are the gradient calculations in lines 3 and 8 of Algorithm 2, which would likely be similar in duration to other methods if using the same number of iterations.
4. The authors compare their method with four baselines (Homotopy, SAPF, StrAttack, FWnucl) but only provide results for Homotopy and SAPF in Table 1. Could the authors explain this choice?
5. In lines 149–152, the authors mention, “this approach does not guarantee that the perturbations will affect the most critical pixels in the image.” How do they define or identify these “most critical pixels”? Based on which metric?
6. I am interested in the interpretability score of Grad-CAM or CAM techniques.
soundness: 2
strengths: •	The proposed method appears to be faster than previous approaches.

•	The number of perturbed pixels is also fewer compared to prior work, which, as the authors claim, might contribute to better explainability.
summary: This paper presents a novel sparse attack method named GSE (Group-wise Sparse and Explainable), designed to generate structured adversarial attacks against deep neural networks (DNNs).

The GSE algorithm emphasizes group-wise sparse attacks, meaning the perturbations are strategically grouped within semantically meaningful regions of the image, rather than being scattered randomly.

**Limitations in Previous Work:** Prior methods primarily focus on minimizing the number of altered pixels without imposing constraints on their location or intensity. Consequently, these modified pixels often show considerable variations in color or intensity relative to their surroundings, making the alterations more noticeable. This highlights the need for structured, group-wise sparse perturbations that better target key areas of the image. However, I feel this motivation is somewhat broad, as it applies to all group-based adversarial attacks.

**Two-Phase Approach to Solving the Optimization Problem:**
- **Step 1:** This phase identifies the pixels most vulnerable to perturbation. It employs a non-convex regularization approach using the 1/2-quasinorm, allowing for individual tuning of tradeoff parameters (\(\lambda\)) for each pixel. The algorithm iteratively reduces these parameters for pixels close to those already perturbed, making them more susceptible to further modification. I believe this strategy prevents further updates on perturbed pixels, effectively addressing issues with high-intensity or conspicuous changes. However, the authors assert that this step primarily reduces the number of pixels that need alteration—a claim that seems misaligned with the method’s description, in my view.
   - This step can be achieved through a heuristic adjustment of \(\lambda\), with individualized settings for each pixel.
  
- **Step 2:** This phase constructs a low-magnitude adversarial attack by optimizing an objective function over the pixels chosen in Step 1. The objective includes the classification loss and a penalty term to control the magnitude of perturbation. The algorithm employs projected Nesterov's Accelerated Gradient (NAG) descent to efficiently solve this refined problem.

The authors claim that the proposed method achieves both effective attack performance and, importantly, enhanced explainability.
weaknesses: - **Writing Quality:** Several areas need improvement.
  - **Flow of the Paper:** Despite multiple readings, the main limitations of previous work that this paper aims to address remain unclear. Specifically, the introduction (lines 45-53) outlines the motivation for group-wise sparse attacks in general, but it doesn't clearly articulate the specific issue that this paper seeks to tackle.
  - **Detail in Section 2.2:** This section is overly detailed but lacks sufficient explanation to help readers understand how (1) it identifies a smaller set of suitable pixels and (2) achieves lower perturbation magnitudes. Additionally, the AdjustLambda algorithm would benefit from a standalone paragraph with clear notation to help readers follow the paper more easily.
  - **Confusing Notations:** Some notations are inconsistent and confusing. For instance, in Section 3.2, `n` represents both the number of images and the size of a patch (n by n pixels), while `m` refers to both the mask and the first `m` adversarial examples (line 256).

- **Evaluation Metrics:** The evaluation metrics are somewhat questionable. Specifically, in Section 3.2, the authors propose using Attack Success Rate (ASR) = m/n, where `n` is the total number of images. However, it would be more appropriate for `n` to represent the number of correctly classified images by a classifier. The use of the IS score is also questionable. More specifically, the IS score show the alignment between the Adversarial Saliency MAP (ASM) and the perturbation w, generated by attacks. However, the ASM is calculated based on the gradient of the prediction loss w.r.t. true label. Therefore, based on insight from the Short-cut learning paper, if the model based on the imperceptible (and non-sensible feature) to make the prediction, the ASM map is align with this feature instead of the human perspective or human explainability. 
- **Interpretability Technique:** Grad-CAM is generally a more advanced method than CAM, raising questions about its suitability for comparison.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See weakness
soundness: 3
strengths: 1. The paper is well-organized and written. The problem setup, objectives, and contributions are articulated in a way that is accessible to readers.
2. The GSE framework achieves high levels of sparsity and group-wise organization in perturbations, making it a valuable tool for evaluating and improving the robustness of DNNs.
summary: This paper introduces a novel approach for generating sparse adversarial perturbations targeting deep neural networks (DNNs). GSE achieves higher group-wise sparsity than state-of-the-art (SOTA) methods, allowing for fewer, yet targeted pixel modifications. This results in minimal visible changes while effectively fooling the DNNs.
weaknesses: 1. The GSE method’s effectiveness seems sensitive to specific hyperparameters.
2. The authors search the hyperparameters only for their method. This may not be fair to other methods. I think the authors should search the hyperparameters for all methods.
3. An ablation study on $\hat{k}$ should be given since the first phase will highly affect the performance.
4. The experiments only have two datasets. The performance on more datasets is required.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. In Phase Two, why did you choose to use gradient computation instead of applying a proximal operator update for the $\ell_2$ norm? Would using a proximal operator provide any computational or optimization benefits, especially regarding convergence and perturbation magnitude control?

2. The paper mentions that a grid search was used to select hyperparameters. How sensitive are the results to these hyperparameters? Could slight variations in the hyperparameters significantly impact the effectiveness, sparsity, or explainability of the adversarial attacks?

3. I noticed that in Equation 9 and 10, the update for the blurred perturbation mask causes the tradeoff parameters to decrease more slowly than they increase. Could you explain the rationale behind this design choice? How does the asymmetry in the speed of adjustment affect the performance and explainability of the generated adversarial examples?
soundness: 2
strengths: 1. The methodology is well-formulated, and the proposed two-phase approach is sound. Rigorous experiments demonstrate the efficacy of the method, comparing it with SOTA adversarial attacks.

2. The paper is well-structured, with clear explanations of the algorithms.
summary: The paper introduces GSE (Group-wise Sparse and Explainable Adversarial Attacks), a novel method for generating sparse adversarial attacks on Deep Neural Networks (DNNs). These attacks aim to perturb semantically meaningful regions of an image, making the attacks more explainable. The authors propose a two-phase algorithm to generate such group-wise sparse adversarial examples: The first phase utilizes 1/2-quasinorm regularization to select the most critical pixels for perturbation using a proximal operator. The second phase applies a projected Nesterov’s accelerated gradient descent to fine-tune perturbations in targeted regions, minimizing their magnitude while maintaining effectiveness. The approach is evaluated on CIFAR-10 and ImageNet datasets, demonstrating significant improvements in group-wise sparsity and explainability while achieving a high attack success rate and reduced time consumption.
weaknesses: 1. The paper relies on grid search for selecting hyperparameters, but there is no detailed analysis of how sensitive the method’s performance is to these choices.

2. The rationale for the specific update mechanism in Equation 9, where tradeoff parameters decrease slower than they increase, is not fully explained. It would be helpful to understand how this impacts the selection of critical regions for perturbation and whether a more symmetric adjustment could improve results.

Meta-review: This work develops adversarial attacks for group-sparse perturbations that align with semantic structures in the input. The algorithm developed is a two-part heuristic: first, the optimization via PGD of a $\ell_p$-pseudonorm (with $p=0.5$) by means of a proximal operator and, second, an optimization over the selected pixels with Nesterov accelerated gradient descent. The experiments and evaluation verify the claims and objectives of the paper.

**Strengths**

* The obtained attacks are sparser and more aligned with the semantic content of the regions that appear important, as reflected by CAM.
* Faster than other methods.
* The devise method provides an effective solution for the problem.

**Weaknesses**
* It is still not completely clear why the authors deem such attacks "interpretable", or why such a qualifier is needed.

**Summary** 

In all, and while the numerical reviews reflect a borderline paper, I believe the strengths outweigh the weaknesses, and I'm recommending acceptance.

Decision: Accept (Poster)