Towards a Unified Game-Theoretic View of Adversarial Perturbations and Robustness
Authors: Jie Ren
Die Zhang
Yisen Wang
Lu Chen
Zhanpeng Zhou
Yiting Chen
Xu Cheng
Xin Wang
Meng Zhou
Jie Shi
Quanshi Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Adversarial robustness
deep learning
game-theoretic interaction

Abstract: This paper provides a unified view to explain different adversarial attacks and defense methods, i.e. the view of multi-order interactions between input variables of DNNs. Based on the multi-order interaction, we discover that adversarial attacks mainly affect high-order interactions to fool the DNN. Furthermore, we find that the robustness of adversarially trained DNNs comes from category-specific low-order interactions. Our findings provide a potential method to unify adversarial perturbations and robustness, which can explain the existing robustness-boosting methods in a principle way. Besides, our findings also make a revision of previous inaccurate understanding of the shape bias of adversarially learned features. Our code is available online at https://github.com/Jie-Ren/A-Unified-Game-Theoretic-Interpretation-of-Adversarial-Robustness.

A Unified Game-Theoreti Interpretation of Adversarial Robustness
Jie Ren"*, Die Zhang" Yisen Wang" Lu Chen", Zhanpeng Zhou", Yiting Chen", Xu Cheng", Xin Wang", Meng Zhou Jii Shi", Quanshi Zhang
Shanghai Jiao Tong University
Key Lab. of Machine Perception, School of Artificial Intelligence, Peking University Institute for Artificial Intelligence, Peking University
Camegie Mellon University Huawei technologies Inc.
Abstract
This paper provides unified view to explain different adversarial attacks and defense methods, i.e. the view of multi-order interactions between input variables of DNNs. Based on the multi-order interaction, we discover that adversarial attacks mainly affect high-order interactions to fool the DNN. Furthermore, we find that the robustness of adversarially trained DNNs comes from category-specifie low-order interactions. Our findings provide a potential method to unify adversarial perturbations and robustness, which explain the existing defense methods in a principle way. Besides, our findings also make a revision of previous inaccurate understanding of the shape bias of adversarially learned features. Our code is available online at https: //tttt com Joe/Jie-Ren o
www.enneeteeeeon--ee--e of Adversarial att.://raaaaaoooorrrrrrrrraaaaaa intersarrial-Roouutteeeeee.
Introduction
Adversarial robustness of deep neural networks (DNNs) has received increasing attention in recent years. Related studies include adversarial defense and attacks 48 21] In terms of defense, adversarial 60]. In spite their fast development, the essential mechanism of the adversarial robustness still unclear. Thus, the understanding of adversarial attacks and defense an emerging direction in recent years. Ilyas al. 29 demonstrated adversarial examples could be attributed to the presence of non-robust yet discriminative features. Some methods [20] 588) explored the mathematical bound for the model robustness. Zhang and Zhu 773), Tsipras et al. (50) found adversarial training helped DNNs learn more interpretable (more shape-biased) representation. Besides the feature interpretability. Tsipras al. [50] further showed an inherent tension between the adversarial robustness and the generalization power.
training an effective and the most widely-used method [4 72 54 55
Unlike above perspectives for explanations, aim to propose unified view to explain the essential reason why and how adversarial examples emerge, as well as essential mechanisms of various adversarial defense methods. We rethink the adversarial robustness from the novel perspective of
'qqual contribution
This work was done when Meng Zhou was undergraduate at Shanghai Jiao Tong University. QQannshi Zhang is the corresponding author. zqa10220s edu, en. This work supervised by Dr. Quanshi Zhang. He is with the John Hoperoft Center and the MoE Key Lab of Artificial Intelligence, Al Institute, at the Shanghai Jiao Tong University, China.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Highorder meracione lusuall gooal shapes)
Low-order interccione
High-oddrr Interactons
Sandir DWN
Eh 10
ond
Clf
order
Advenatelly
onder
urdor
Low ordor interoctions (usually loal shapes)
Interaction
Advarsarial offects
Intoractions
Attacking model output
Pheels with intrrcciinn
Pixels with stoong interactions
samples
interactions
ecamples
Figure 1: (Left) Adversarial attacks mainly affect high-order interactions in input samples. High-order interactions in adversarially trained DNNs are more robust than those in standard DNNs. (Right) Regions with strong low-order and high-order interactions, which are visualized by the method extended from 770]
interactions between input variables of a DNN. It is because in an adversarial example, adversarial perturbations on different pixels do not attack the DNN independently. Instead, perturbation pixels usually interact with each other to form a specific pattern for attacking. Surprisingly, we find that such interactions can explain various aspects of adversarial robustness. Specifically, this study aims to answer the following three questions.
How disentangle feature representations that are sensitive to adversarial perturbations. Based on the game-theoretie interactions, we aim to summarize the distinct property of feature repre- sentations, which are sensitive adversarial perturbations, among overall feature representations.
How to explain the effectiveness of the adversarial training. The above summarized property of sensitive feature representations also provides a new perspective explain the utility of the adversarial training, ie. why and how the adversarial training penalizes such sensitive feature representations.
How to unify various adversarial defense methods in single theoretic system. Our research provides a unified understanding for the success adversarial defense methods [65 30
As prerequisite of analyzing the adversarial robustness, let us first revisit the interaction between input variables in DNNs. Let set of input variables collaborate with each other to form an inference pattern, the Shapley interaction index [22] is a standard metric to measure the numerical benefits to the inference from their collaborations. This metric can be further extended to the multi-order interaction [70]. For the interaction between two input variables (i,j), the interaction order measures the number of contextual variables that influence the significance of the interaction between i and j. In other words, low-order interactions represent simple collaborations between input variables with small contexts, while high-order interactions indicate complex collaborations over large contexts (see Figure [ (right)).
We further prove that the network output can be decomposed into the sum of multi-order interactions between different pairs of input variables. Thus, the overall effects of adversarial perturbations on the network output can be decomposed into elementary effects on different interaction components. Therefore, we can explain adversarial robustness using such elementary interaction components.
(1) We discover and partially prove that adversarial perturbations mainly affect high-order interactions, rather than low-order interactions (see Figure (left). In comparison, low-order interactions are naturally robust to attacks. In other words, adversarial attacks mainly affect the complex and large-scale collaborations among most pixels in the image. Based on this, we can successfully disentangle sensitive feature representations, i.e. high-order interactions.
Interaction vs. frequency & rank. Some studies explained adversarial examples as figh-frequency features 66 51 23 and high-rank features [30]] We have conducted experiments to show that
high-order interactions can better explain the essential property of attacking-sensitii representations, f.e. the complex and large-scale visual concepts.
(2) A clear difference between standard DNNs and adversarially trained DNNs is as follows. Adver- sarial training significantly increases the robustness of high-order interactions. In other words, attacks mainly affect complex collaborations standard DNNs, while for adversarially trained DNNs, complex collaborations not vulnerable w.z.t simple collaborations.

---

Then, we further explain the reason for the high robustness of adversarially trained DNNs. For interactions of each order, we define the disentanglement metric to identify whether interactions of this order are discriminative for the classification of specific category, represent common knowledge shared by different categories. For example, F (left), interactions representing the blue water may be shared by different categories, while interactions corresponding to the head of the red-breasted merganser are discriminative for this category. Based on the disentanglement metric, we discover that compared with standard DNNs, adversarially trained DNNs usually encode more discriminative low-order interactions. Discriminative low-order interactions make high-order interactions of ad adversarially trained DNNs robust to attacks, because contexts of high-order interactions are composed of many small contexts of low-order interactions. For example, if the simple (low-order) interactions for the red-breasted merganser are learned to be discriminative, instead of being shared by the bicycle category, then it is difficult to attack this image towards the bicycle category. It is because it is difficult use the low-order interactions of the red-breasted merganser's ' head to construct high-order interactions of bicycles.
(3) Our research provides unified understanding for the success of several existing adver- sarial defense methods, including the attribution- -based detection of adversarial examples [65], the recoverability of adversarial examples to normal samples, the cutout method [13, and the rank-based
method 30 (which is proved by 30 to be related to frequency-bad based methods [66 31 61).
Above findings also slightly revise the previous explanation of ad adversarially learned features [2] 55 16 [3]. They claimed that adversarial training learned more information about foreground shapes. We discover that these adversarially learned features are actually low-order interactions (usually local shapes), instead of modeling the global shape of the foreground.
Explainable Al system based on pame-theorede interactions. In fact, our research group led by Dr. Quanshi Zhang have proposed game-theoretic interactions, including interactions of different orders [69] and multivariate interactions (71). The interaction can be used as an typical metric to explain signal processing in DNNs from different perspectives. For example, the game-theoretic metric can be used to guide the learning of baseline values of Shapley values [1]. Furthermore, we have built up tree structure to explain the hierarchical interactions between words encoded by NLP models [68]. We have also used interactions to explain the generalization power of DNNs [70]. The interaction can also explain how adversarial perturbations contribute to the attacking task (53] and explain the transferability of adversarial perturbations (52] Furthermore, we have also used the interaction to formulate the visual aesthetics 12] and processin properties of different types of visual concepts (II in DNNs. As an extension of the system of game-theoretic interactions, in this study, we explain the adversarial robustness based on interactions.
2 Related work
Attacking methods can be roughly summarized into white-box attacks [48 21 31 38 g
and black- 4). For defense, adversarial training is one of the most effective
box attacks [32 39 10
6 28
59
and widely-used defense methods [34
72
55 60). Other defense methods include masking 13 and applying pre-processing on input images for
54]
gradients 39 36), modifying networks
testing 14 35 62 3)
Explanations for adversarial examples. Some previous studies focused on the reason for the existence of adversarial examples. Goodfellow et al. [21] explained adversarial examples result of the high linearity of feature representations. Gilmer et al. 20) Ma et al. [3 proved that the existence of adversarial examples was due to the geometry of the high-dimensional manifold. Xie et al. (62. Xu
et al. (63, 64), Bai et al. (5) discovered that adversarial perturbations usually activated substantial "noise" and semantically irrelevant fcatures. Engstrom et al. [17] investigated the vulnerability of DNNs to rotations and translations. Tsipras et al. [50], Ilyas et al. [29] demonstrated that adversarial examples were attributed to non-robust yet discriminative features.
Understandings of adversarial training. Athalye et al. (2 suggested that adversarial training did not cause the obfuscated gradients phenomenon, which boosted the robustness. Goodfellow et al. (1], Dong et al. (16), Tsipras et al. [50). Zhang and Zhu 73 found that adversarially trained DNNs learned more shape-biased biased features than standard DNNs. Chalasani et al. [9] proved that adversarially trained DNNs w.r.f. the fox attack exhibited more sparse attributions. Tian et al. [49] showed that
there is robustness imbalance among classes in adversarial training. Song al. [46] considered the
3

---

adversarial training as the enumeration of all potential adversarial perturbations. Wang et al. [54] explained adversarial training from the perspective of min-max optimization. Yin et al. [66], Wang et al. (56), Harder et al. 23 discovered adversarial training pushed DNNs to utilize low-frequency components in inputs.
Understanding of the robustness. Szegedy et al. [48], Hein and Andriushchenko 22 computed Lipschitz constant to explain the robustness. Ignatiev al. [27], Boopathy et al. 7 investigated the connection between network interpretability and adversarial robustness. Tsipras et al. (50] proved
the inherent tension between adversarial robustness and standard generalization power. Fawzi et al.
18] Gilmer et al. [20), Weng et al. [58] proved lower/upper bounds on the robustness. Pal and Vidal
37 proposed a theorete framework understand the adversarial robustness, by formulating the game between attackers and defenders w.t.. a trained DNN, Under the sume-theoretic framework, Pal and Vidal 37 theoretically proved that the FGM attack and the random smoothing defense formed Nash Equilibrium under some assumptions.
Unlike previous explanations of the existence of adversarial examples and adversarial robustness, we explain adversarial examples and adversarial training from a new perspective, i.e. the complexity of visual concepts that are learned by DNN.
3 Decomposing attacking utility into interactions of multiple orders
Preliminaries: using Shapley values [44 and the Shapley interaction index [22] to explain DNN. The Shapley value 44] in game theory is widely considered as an unbiased estimation for the importance or contribution of each player in a game. Given a trained DNN and the input with
n variables (e.g. an image with pixels, a sentence with n words) N {1.... ,n), we can take input variables as players, and consider the network output as the reward. Shapley values can fairly divide and assign numerical effects on the network output to each input variable. More specifically,
let 2N def {S|S S N) denote all potential subsets of N, and each subset S represents specific context (e.g. a set of pixels in an image). x(S) E R represents the scalar network output when we keep variables in S unchanged and mask variables in N \ S by following settings in [ (i.e. setting masked variable to the average value over different input samples)
[l In particular, e(N) refers to the
network output w.z.f the entire input N (e.g. the whole image), and e(f) denotes the output when mask all variables. In this way, the Shapley value (()) unbiasedly measures the importance of the variable i the network output.
(n2
|S|
1)!!!!
o(i)=
P(S) (USS c(S],
P(S)
(1)
n!!
In this way, the network output can be considered as the sum of elementary importances of input (00). The Shapley value has been proved to satisfy four desirable properties, iee. linearity, nullity, symmetry and efficiency properties, thereby being regarded as fair method to allocate the network output to each input variable [57].
variables, iee. =(N)= EiE (01)
=
Input variables of a DNN do not contribute to the network output independently. Instead, different variables collaborate with each other to affect the network output, and we use the interaction to quantify the numerical utility of such collaborations. To this end, the Shapley interaction index [22 measures the utility of the collaboration between two input variables (i,j) by examining whether the absence/pressenee of an input variable will change the importance of the other variable i.
Their interaction is defined as [(i,j) 2(i); presen! *(i); always absent, where o(i); always present and ((); always absent denote the importance of the variable when j is always present and when is always absent, respectively (please see 22 for more details about T(i.j))-
present
Decomposition of the existing Shapley interaction index into multiple orders. Zhang et al. (70) further decomposes the Shapley interaction index [(i.j) [22] into interactions of different orders.
[(i.j) 1
Σ
(m)
(m) BBSg (A (At(i,
m=o
where Ao S) = vsS U (v.1)) (S
(SSU))++(5)
classification, we set = log ply = clgiven an input with variables in N \ S masked). where is selected as either the ground- -ruth category of the input, the incorrectly classified category after attacks.
*For
the
DNN trained for multi catti-yategory
((S)

---

Suppase v(x) = X1 Xz
K627 +..
mn0.3n
m=0.4n
mn0.5n
7( 60)=0
v (1)=0
vO)=
(2)
Figure 2: (Left) Computation of the m-order interaction between two input variables (m = 2).
(Right) Contexts of the m-order interaction r/ Variables (i. are indicated by red boxes. We extend the visualization method in 77), which visualized contexts of the Shapley interaction index, to show contexts of multi-order interactions (details in the supplementary material). Red (blue) colors indicate pixels that frequently (infrequently) appear in contexts which cause significant interactions.
Proof of decomposing network output into multi-order interactions to explain adversarial attacks. In this study, we successfully prove that the network output can be decomposed as the weighted sum of multi-order interactions. This enables us to use such interactions to explain adversarial attacks. Before the decomposition, let us first use interactions to understand the attack. As Figure 2 (left) shows, the interaction component of each order 7/ represents collaborations between two input variables (i, with a specific contextual complexity. Let us consider input variables i, and an arbitrary set of m contextual variables. If r(m) > 0, it indicates that the presence of the variable j will increase the importance of the variable i. Thus, we consider variables (i,j) have positive interaction. If 1g < 0, it indicates negative interaction.
The m-order interaction between two input variables (i,j) measures the average interaction between (i,j) when we consider their collaborations with m contextual variables (m pixels). From another perspective, the order m measures the number of contextual variables that influence the interaction between and j. For a low order m, I[(h) reflects the interaction between i and j w.r.t. simple contexts of a few variables. For high order m, 1i corresponds to the interaction w.r.f. complex contexts with massive variables. Figure 2 (right) visualizes the contexts S corresponding to strong low-order interactions and strong high-order interactions, respectively. Cheng et al. [ has also proven that low-order interactions (local collaborations) mainly reflect simple and common concepts (features), and high-order interactions (global collaborations) usually represent complex and global features.
(right)
Properties of multi-order interactions. We have proven that (m) satisfies linearity, nullity, commu- tativity, symmetry, and efficiency properties (please see the supplementary material for details). In particular, the efficiency property is given as follows.
Efficiency property: The output of the DNN given the entire input uNN) can be decomposed into interactions of different orders, i.e. v(N)= v(1) ΣIEN oi (0)))) + Σ En.jeN Σn- di
((m) where
ffm) der m-1-m (()) and (i) def v({e)) vg))
Decomposing the overall attacking utility into interactions of different orders. According to the efficiency property of interactions, the output of the DNN w.E.. the image can be decomposed into the sum of multi-order interactions between different pairs of input variables. Thus, we can decompose the overall utility of adversarial perturbations on the network output into elementary effects on interactions.
Au(N def
v(N[z)) - u(N(2ddr) -v(0lx)) + Σ TD (1lz)
Σ Σ
(m) (x)
(3)
REN
GFEN m=0
usually can ignored
where x IR" denotes the normal sample, and -nt = x + Ax R² denotes the adversarial example. e(N]2""") denotes the network output given all variables in N of the adversarial example 2*th v(N (x) corresponds to the normal sample. The first term Av(0) = v00 (z) v(0 x = 0. In the second term, ( det (u((i)a)) - =(]==)) (r(1iH22**) - v00 =))) = u(fi)(z)) (z) - v(()) Because in most applications, the importance of a single variable (e.g. a pixel) is usually small, we can ignore this term. In the third term, AJ(") (a:) denotes the attacking utility of the m-order interaction between variables (1, in AJ(m) (x) =-1-m (1(m) (z), where A/(")(a))
(a) def ((m) r((m) (2"d)) measures the clementary effects of adversarial perturbations the m-order interaction.
5

---

frer
VOSIE
V05-66
Ped
Sarled0
(c)
Pointhuire leameed
the ModelMett1
(0) Untargoted bttack
stiak
Figure 3: The multi-order interaction I and (m))
of standard DNNs and adversarially trained
adv
DNNs. Adversarial perturbations mainly affected high-order interactions.
Explaining adversarial attacks and defense using interactions
To simplify the story, we only study the simplest and widely- untargeted and targeted &oe PGD attacks (34).
4.1 Attacks mainly affect high-order interactions
Attacking utility of m-order interactions. According to Eq. (3). effects of adversarial attacks mainly depend on changes of interactions A Argy (I) (or A (x)). Thus, in this section, we further conduct experiments to show that adversarial attacks mainly affect (x)) of high orders. In order to compare the multi-order interactions in normal samples and those in adversarial examples, measure the average interaction of specific order among different pairs of variables in different input images, i.e. [(m] Exgn (x)). where Ω S R. denotes the set of all samples.
We use the normal samples Qar to compute ffm)) and use adversarial examples Paty to compute rim) In this way, A/(m) ((m) r/()) represents effects of attacks on the m-order interactions. Similarly, A7()) def E [AJ ((m)))
(x)] (x)]
p-1-m (o")) measures the attacking utility of the m-
order interactions according to Eq. (
Comparing attacking utilitics between interactions of different orders (in terms of ((m)). In order to measure 1!TT) and f(m)) we conducted experiments on ResNet-18/34/50 [24]. Wide- ResNet50-4 [67]. DenseNet- 161 16). and VGG-16 [45]. For each DNN, we obtained both the
standardly trained version and the adversarially trained version on the ImageNet dataset 42
We also conducted experiments on PointNet++ [40] learned on the ModelNet10 dataset [61]
which is 3D dataset. We measured the interaction f(m) by setting u(S]x) = log p(y gi""ng variables in S in the input and mask variables in N \ S), and E Q was sampled from the validation set. By following settings in (.. the masked variables N \ S were set to the average value over different input samples. However, the computational cost of ((m) was intolerable. To reduce the computational cost, we applied the sampling-base approximation method in (70) and computed interactions at the grid level, rather than the pixel level. Please see the supplementary material for more discussions.
x PGD attacks 34 with the Eso constraint | fo. S to We considered both untargeted and targeted generate adversarial examples. We set 32/255 by following the setting 62.. The step size was set to 2/255. For fair comparisons, we controlled the perturbation generated for each image to have similar attacking utility of The attacking utility in untargeted attacks was defined as U Fumaagee( (x: = , (N( h (N]a:"")) where ,, (Nlar) and nu (NI (a**)) denote network outputs of the ground-truth category ynuh before the softmax layer, when taking the normal sample and the adversarial example as input, respectively. The attacking utility in targeted attacks was defined as Uunga(22) (z) = (hy (N]=:">) h (N """)) (hiaaa (N]z)) hu (N]=)), where hy denote the network output of the target category (aren
Results. Figure 3 shows the multi-order interactions within normal samples and adversarial examples. We found that adversarial perturbations significantly decreased high-order interactions, in both ad adversarially trained DNNs and standard DNNs. For example, in Figure (a), low-order interactions
'we used pretrained models released by Salman al. 43
'In the untargeted attack, we considered the misclassified category as the target category. In the targeted attack, the target label was set as the misclassified category in the untarget attack. When we consider interaction w.r.t the target category, set v(S) p(y aigeel given variables in S and mask variables in N \ S).

---

Adversarially trained VGG-12
Adverarially trained DNN - Standard DNN
Untargeti
4770
Danaahes11 18
Baciwe-n Reelen-3 31
Damrabis--11 VGG-16
cxber
coke
ond
Tunt
sllck
Figure 4: Distribution of compositional attacking utilities caused by interactions of different orders
Figure 5: The interaction disentanglement D(m), Interactions of adversarially trained DNNs exhib- ited higher disentanglement than those of stan- dard DNNs.
{A)()).
(m < 0.5m) in standard ResNet-18 18 decreased a little, while the interaction of order m = 0.95m dropped from 0.01 to -0.059. This phenomenon was consistent with the heuristic findings of Dong et al. [16) that neurons corresponding to high-level semantics were ambiguous.
Additional experiments on the target category and other categories. Beyond above analysis about interactions w.r.f. the ground-truth category, we also conducted experiments and found that high-order interactions w.r.. the target category increased significantly. Please see the supplementary material for details. In sum, high-order interactions were much more sensitive than low-order interactions, which verified our conclusions.
Theoretic explanation of the sensitivity of high-order interactions. Besides the above empirical observation, can also theoretically prove that high-order interactions more sensitive than low-order interactions.
Proposition 1 (equivalence between the multi-order interaction and the mutual information): Given an input sample æ E X S R" and the network output Y. we define Xs = {xs|æ E X] where S C. N; each zg represents the sample, where variables not in S are masked. If v(S) is set as the entropy of classification v(S) HY]]Xs) Σzg (. X5; X|x)). The conditional mutual information MI(X;; X|: mea- sures the remaining mutual information between X, Xy and Y, when Xs is given. When Xs (with m pixels) is given, MI( Xy; Y Y|Xs) can be considered as the benefit to the inference from the interaction between X; and Xy. Please the supplementary material for proofs.
æs), then 1/())
Proposition indicates that compared to low-order interactions, high-order interactions are condi- tioned on larger contexts 8, i.e. conditioned on more contextual perturbations, thereby suffering more from adversarial perturbations.
Note that in Proposition 1, we set e(S) = H()]xs), which is slightly different from setting u(S) log logp(y = y jrack [S, æ) in Section 4.1 Nevertheless, the trend of eSS) can roughly reflect the negative trend of i(S), which is discussed in the supplementary material.
Comparison with frequency-based methods. Previous studies [66] 51 23 explained adversarial perturbations as high-frequent between normal samples and adversarial samples. We find that high-order interactions can better distinguish adversarial examples and normal samples, than the frequency of features, which indicates that the interaction metric can better explain the essential property of adversarial perturbations. Please see the supplementary material for more details.
features. Figure 6 (left) shows the difference in the frequency
4.2 Explaining specific interactions encoded by adversarially trained DNNS
Discovery. In order to understand the difference in signal-processing behaviors between adversarially trained DNNs and standard DNNs, we have proven that the overall attacking utility Aee [x) can be approximately decomposed as the sum of attacking utilities on multi-order interactions (m), according to Eq. 3 Figure shows the attacking utility of multi-order interactions i.e.
(m)) 1-1- (m)
"Note that unlike the bivariate mutual information, MI (ss) can be negative.
7

---

We noticed that for standard DNNs, adversarial attacks mainly affected high-order interactions. For adversarially trained DNNs, although high-order interactions were usually sensitive to attacks, low/middle-order interactions took up more attacking utilities. This phenomenon actually can also be observed in Figure 3 which is discussed in the supplementary material. Considering Eq. (3) this indicated that adversarial perturbations towards adversarially trained DNNs penalized both complex features of global collaborations and simple features of local collaborations.
Explanation. We further explain the above phenomena, i.e. why high-order interactions in adversari- ally trained DNNs are more robust to attacks than those in standard DNNs. To this end, we propose the following disentanglement metric for the interaction of specific order.
D (m)) EE.nnB if (m (i S|x)| ErnnE BSscA1600h8 Sla)]
1 ((m) (x))
(4)
its EsEMM (ee S|x)]
The above disentanglement metric examines whether or not the m-order interactions represent discriminative information for a specific category. The high value of D(m) indicates that the m-order interactions relatively purely describe specific categories. In other words, the interactions between (i,j)) under different contexts S consistently have the same effects (either positive or negative) on the inference of a specific category. Let us consider the following toy example. When the pair of (i.j) consistently have positive interactions towards a specific category under different contexts, i.e. VS C N \ jr. S|| = m, Av(i, j. S|z) > 0, then we have D( = 1. This means that the mi-th interactions between i and] j stably promote the output probability of this category. In contrast, a low value of D(m) indicates that interactions between (i, represent diverse categories. lee. given different contexts S, interactions between (i,j) sometimes have positive effects on a specific category, and sometimes have negative effects. Please see the supplementary material for more discussions.
Experiments. Figure compares comppres the interaction disentanglement ((m) of standard DNNs and the disentanglement of adversarially trained DNNs. Interactions of adversarially trained DNNs were more disentangled than those of standard DNNs, especially for low-order interactions. This indicated that low-order interactions in adversarially trained DNNs encoded more category-specific information for inference than low-order interactions in standard DNNs.
Based on this observation, we could explain the robustness of high-order interactions to attacks in adversarially trained DNNs. Adversarial training learned more category-specific low-order interac- tions, which boosted the difficulty of attacking high-order interactions. This was because high-order interactions (usually global features) were usually constructed by low-order interactions (usually local features). Let us take the peacock in Figure 2 (right) for example. In this image, low-order interactions (simple features) represented the body of the peacock and the green garden. In this case, was difficult to attack this image to other categories (e.g. the bicycle category) by constructing high-order interactions of the bicycle category using these peacock low-order features. Due to the difficulty of attacking high-order interactions, the adversarial examples towards the adversarially trained DNN had to attack low-order interactions, instead.
4.3 Unifying four existing adversarial defense methods
Explaining the attribution- method of detecting adversarial examples. Yang et al. [65] proposed a method to use the attribution score of input variables to detect adversarial examples. In order to prove the effectiveness of this method, we define the multi-order Shapley value just like
the multi-order interaction, as follows. αf00) (ilar) def EsgNN(s)..ssi (s). U [z) =(S)r),, where m denotes the order of the Shapley value. Then, we can prove that the attribution score which was used in 655 to detect adversarial exmaples, can be writtern as (i)z) v(N[r) v(N \ (1)lz). We
further prove that ((())()))) can be decomposed into interactions of different orders.
<(N(z) -000=)))))))
ni Σ Σ (f(m)((x))
1
(ila))
Σ
1o (x)) + (ilo) (5)
According to the above equation, the overall adversarial effects can also be decomposed into ele- mentary effects on (i)z). (i]x)) = v(ilz)- v(0)z) x)) is usually small and can be ignored, as discussed below Eq. (3) Among Shapley values of all orders, only the (n 1)-order component ((n=1) contains the interactions of the highest order, which are the most sensitive interactions,
according to Section 4.1 Therefore, the Shapley value component ((n=1)(ilx)) is supposed to be
8

---

Betwern variance Indiasa aance
Fistee's
We compared the Fisher's disciminent ralio between interaction metric
full rank image
k rank image
tn
kank image
300
m frequency magnitude matric. PV).
On normal samples
On adversarial examples
Using (ire
port denoles the magnilude the r-frequeccy Fourier componenta.
0.04
0.02
Uning pm
(p07) Eawsster
001
4.02
where FihM) - Sen Low [Cx.y]e" "tt.y//"///wwydda.
0.02
0.05
110
order
order
Figure 6: (Left) The game- theorethe interaction is more significant metric to distinguish normal
samples and adversarial examples. (Right) Multi-order interactions in images of different ranks.
Table I: Ratio of adversarial examples whose classification results were corrected.
Standard DNNs
culout
6 = 0.1
d 0.2
outs
d = 0.3
Advensarally trained DNNs
culout
0.1
oars
0.2
n 0.3
R8sNet-18
7.12%
19.62%
35.55%
44.14%
ResNet-18 18
23.92%
22,40%
33.78%
39.18%
ResNet-50
10.63%
28.53%
45.53%
52.33%
ResNet-50
24.27%
23.23%
35.23%
41.54%
DenseNet-161
11.32%
27.16%
46.15%
56.35%
DenseNet-161
35.65%
24.65%
39.25%
48.74%
the most sensitive to adversarial perturbations, which proves the effectiveness of the detection of adversarial examples. Please see the supplementary material for related proofs and discussions.
Explaining high recoverability of adversarial examples towards adversarially trained DNNs.
The adversarial recoverability of a DNN is referred to as whether the DNN's adversarial examples can be inverted back to the normal sample by minimizing the classification loss. Specifically, given an adversarial example -= generated by the untargeted attack [44] via maX s E(zadh, y we conduct a targeted attack (34) on the adversarial sample invert the classification result back to its broound-trtth label, i.e. ming E(r-dv + 8', y
). Let â = ولدد + 8' denote the recovered sample. If || z:I2 I || 2/12, it indicates a high recoverability; otherwise, a low recoverability.
We find that adversarial examples generated by adversarially trained DNNs usually exhibit higher recoverability than those generated by standard DNNs. This phenomenon can be explained by Proposition 1 in Section [4.]] i.e. low-order interactions correspond to the mutual information condi- tioned on smaller adversarial perturbations, thereby suffering less from attacks. Therefore, we can partially explain the high recoverability of adversarial examples towards adversarially trained DNNs. is because adversarially trained DNNs mainly focus on low-order interactions (see Section 4.2). which leads to high recoverability.
Besides, we conducted experiments ResNet- 18/50 and DenseNet- 161 trained on the ImageNet dataset, which also validated the high recoverability of adversarial examples generated on adversarially trained DNNs. Please see the supplementary material for details.
Explaining the rank-based method. Jere et al. 30 discovered that standard DNNs paid certain attention to high-rank (w.r.. the Singular Value Decomposition) features, but adversarial training put more attention on low-rank features. This implied that adversarial examples mainly contained high-rank features.
We used [30] to reduce the SVD rank of an image (either a normal sample or an adversarial example) to 1 k-rann image and 1 k-rank image, where k denoted the full rank of the image. Figure (right)
16
shows that (1) compared with normal samples, the rank- unnkrreduinng operation on adversarial examples
significantly increased high-order interactions. This indicated our conclusions in Section 4.1 could
explain that adversarial perturbations were mainly high-rank components in images. (2) When
the rank of images was further reduced from f to TE k. the rank-reducing operation affected both low-order and high-order interactions. However, when we reduce the rank of either normal samples or adversarial examples, they exhibited similar effects on low-order interactions, but exhibited dramatically different effects on high-order interactions. This indicated that the most discriminative factor of distinguishing adversarial examples from normal samples high-order interactions, rather than the vank-reducins operation. In other words, the game-theoretic interaction presents a more essential property of adversarial attacks.
Explaining the cutout method. DeVries and Taylor [15] proposed the cutout method to boost the robustness of DNNs by masking out square region of the input during training. This operation can be roughly considered as applying a random dropout operation
to input images. The dropout operation on input images has been proven to destroy interactions between input variables 770. To this end, we have further proven that the dropout operation mainly hurts high-order interactions, rather than order interactions (please see the proof in the supplementary material). In this way.

---

the cutout method can be considered as removing high-order interactions and pushing DNNs to learn more insensitive low-order interactions. Therefore, the learned DNN robust adversarial attacks.
In experiments, we applied the dropout operation to the misclassified adversarial examples, order to verify the attacking-alleviating influence the network output of removing high-order interactions. If the removal of high-order interactions could alleviate the effects of adversarial attacks, it would prove the attacking-allleiattin influence of removing high-order interactions. Given 1es50t-18/50 and DenseNet-161 trained on the ImageNet dataset, we selected normal samples that are correctly classified in the validation set of the ImageNet dataset, and generated adversarial examples with the so untargeted PGD attack based on [62]. The attack was stopped once it succeeded. We applied the dropout operation with different dropout rates a at the pixel level, and the dropped pixels were filled with the average value of surrounding pixels. For the cutout method, we set the length of the side of the masked square regions as 112, which was half of the side length of the input sample (dropping = 25% pixels of the input), following settings in [15]. Table [ reports the ratio of adversarial examples whose classification results were corrected. When we applied dropout to adversarial examples, the classification accuracy of adversarial examples significantly increased, and even performed better than the cutout method. This indicated that the removal of high-order interactions presented more essential defense mechanism than the cutout method.
5 Conclusion
In this paper, we have used the multi-order interaction to provide a unified understanding for the success of adversarial attacks and defense. Based the multi-order interaction, have explained adversarial attacking as mainly affecting high-order interactions between input variables. Furthermore, have also explained the success of adversarial training, i.e. learning more category-specift low- order interactions to boost the robustness. Besides, we have further provided unified explanation for some existing adversarial defense methods.
Acknowledgments and Disclosure of Funding
This work is partially supported by National Science and Technology Innovation 2030 Major Project of the Ministry of Science and Technology of China under Grant (2021ZD011 1602), the National Nature Science Foundation of China (No. 61906120, U19B2043), Shanghai Natural Science Foun- dation 100300000022111340000, Shanghai Municipal Science and Technology Major Project (221ISHZDZX010) This work is also partially supported by Huawei Technologies Inc. Prof. Yisen Wang is partially supported by the National Natural Science Foundation China under Grant 62006153, and Project 2020BD006 supported by PKU-Baidu Fund. Xin Wang is supported by Wu
1ZR
Wen Jun Honorary Doctoral Scholarship, Al Institute, Shanghai Jiao Tong University.
10

---

References
[1] Marco Ancona, Cengiz Oztireli, and Markus Gross. Explaining deep neural networks with polynomial time algorithm for shapley value approximation. In JCML. 2019.
[2] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In ICML, 2018.
[3] Yang Bai, Yan Feng. Yisen Wang, Tao Dai, Shu-Tao Xia, and Yong Jiang. Hilbert-based generative defense for adversarial examples. In ICCV, 2019.
[4] Yang Bai, Yuyuan Zeng, Yong Jiang, Yisen Wang, Shu-Tao Xia, and Weiwei Guo. Improving query efficiency of black-hox adversarial attack. In ECCV, 2020.
[5] Yang Bai, Yuyuan Zeng, Yong Jiang, Shu-Tao Tao Xia, Xingjun Ma, and Yisen Wang. Improving adversarial robustness via channel-wise activation suppressing. In ICLR, 2021.
[6] Arjun Nitin Bhagoji. Warren He, Bo Li, and Dawn Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In ECCV, 2018.
[7] Akhilan Boopathy, Sijia Liu, Gaoyuan Zhang, Cynthia Liu, Pin-Yu Chen, Shiyu Chang, and Luca Daniel. Proper network interpretability helps adversarial robustness in classification. In ICML, 2020.
[8] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In SP, 2017.
[9] Prasad Chalasani, Jiefeng Chen, Amrita Roy Chowdhury, Xi Wu, and Somesh Jha. Concise explanations of neural networks using adversarial training. In JCML, 2020.
[10] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi. and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017.
[11] Xu Cheng, Chuntung Chu, Yi Zheng, Jie Ren, and Quanshi Zhang. A game-theoretic taxonomy of visual concepts in dnns. arXiv preprint arXiv:2106. 10938, 2021.
[12] Xu Cheng, Xin Wang, Haotian Xue, Zhengyang Liang, and Quanshi Zhang. hypothesis for the acsthetic appreciation in neural networks. arXiv preprint arXiv:2 02646,,46, 2021.
[13] Moustapha Cisse, Yossi Adi, Natalia Neverova, and Joseph Keshet. Houdini: Fooling deep structured prediction models. arXiv preprint arXiv:1707.05373 2017.
[14] Nilaksh Das, Madhuri Shanbhogue, Shang- Tse Chen, Fred Hohman, Li Chen, Michael E Kounavis, and Duen Horng Chau. Keeping the bad guys out: Protecting and vaccinating deep learning with jpeg compression. arXiv preprint arXiv: I 709002000, 2017.
[15] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:1708.0m 04558, 2017.
[16] Yinpeng Dong, Hang Su, Jun Zhu, and Fan Bao. Towards interpretable deep neural networks by leveraging adversarial examples. arXiv preprint /708 170.00599, 2017.
[17] Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. Exploring the landscape of spatial robustness. In ICMI,, 2019.
[18] Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Analysis of classifiers' robustness adversarial perturbations. Machine Learning, 107(3)488-5088 2018
[19] Ji Gao, Beilun Wang, Zeming Lin, Weilin Xu, and Yanjun Qi. Deepeloak: Masking deep neural network models for robustness against adversarial samples. arXiv preprint (8K3::1772006666 2017.
[20] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, Ian Goodfellow, and G Brain. The relationship between high high-dimennional geometry and adversarial examples. arXiv preprint arXiv:1801.0m 027744 2018.
[21] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamessing adversarial examples. arXiv preprint arXiv:1412.6577 1412.5572, 2014.
[22] Michel Grabisch and Mare Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 28(4):547-5655 565, 1999.
11

---

[23] Paula Harder, Franz-Josef Pfreundt, Margret Keuper. and Janis Keuper. Spectraldefense: Detecting adversarial attacks cans in the fourier domain. arXiv preprint arXiv:2103.03006 2021.
[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[25] Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In NeurlPS, 2017.
[26] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, 2017.
[27] Alexey Ignatiev, Nina Narodytska, and Joao Marques-Sike Silva. On relating explanations and adversarial examples. In NewrlPS, 2019.
[28] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black- blxck-box&&a adversarial attacks with limited queries and information. In ICML, 2018.
[29] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry, Adversarial examples are not bugs, they are features. In NeurlPS, 2019.
[30] Malhar Jere, Maghav Kumar, and Farinaz Koushanfar. A singular value perspective on model robustness. arXiv preprint arXiv:2012.03516. 2020.
[31] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples the physical world. arXiv preprint Xiv:16607002533 2016.
[32] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transfcrable adversarial examples and black-box attacks. In ICLR, 2017.
[33] Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoencheck, Dawn Song, Michael E Houle, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In ICLR, 2018.
[34] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[35] Dongyu Meng and Hao Chen. Magnet: a two-pronged defense against adversarial examples. SIGSAC, 2017.
[36] Aran Naychi and Surya Ganguli. Biologically inspired protection of deep networks from adversarial attacks. arXiv preprint 703iv:/703.09202, 2017.
[37] Ambar Pal and Rene Vidal. A game theoretic analysis of additive adversarial attacks and defenses. In NeurIPS, 2020.
[38] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson. Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In EuroS&P, 2016.
[39] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, 7. Berkay Celik, and Ananthram Swami. Practical black-hox attacks against machine learning. In ASIA-CCS, 2017.
[40] Charles R Qi. Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In CVPR, 2017.
[41] Jie Ren, Zhampeng Zhou Qirui Chen, and Quanshi Zhang. Learning baseline values for shapley values. arXiv preprint arXiv:2105. 10719, 2021.
[42] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. Imagenet large scale visual recognition challenge. In International Journal of Computer Vision, 115(3):211-552, 2015.
[43] Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? arXiv preprint arXiv:2007.0 07,489 2020.
[44] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(7833307-317, 1953.
[45] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. In ICLR, 2015.
12

---

[46] Yang Song, Rui Shu. Nate Kushman, and Stefano Ermon. Constructing unrestricted adversarial examples with generative models. NewrIPS, 2018
[47] Nitish Srivastava, Geoftrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The journal of Machine Learning Research, 15 (1):1929-1958, 2014.
[48] Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6199, 2013.
[49] Qi Tian, Kun Kuang, Kelu Jiang, Fei Wu, and Yisen Wang. Analysis and applications of class-wise robustness in adversarial training. In KDD, 2021.
[50] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry, Robust- ness may be at odds with accuracy. In ICLR, 2018.
[51] Haohan Wang, Xindi Wu, Zeyi Huang, and Eric P Xing. High highffreueency component helps explain the generalization convolutional neural networks. In CVPR, 2020.
[52] Xin Wang, Ren, Shuyun Lin, Xiangming Zhu, Yisen Wang, and Quanshi Zhang. unified approach to interpreting and boosting adversarial transfcrabilityy arXiv preprint ar 2000:02000.04055, 2020.
[53] Xin Wang, Shuyun Lin, Hao Zhang. Yufei Zhu, and Quanshi Zhang. interactions of adversarial attacks. In ICCV, 2021.
Interpreting attributions and
[54] Yisen Wang. Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In ICML, 2019.
[55] Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In ICLR, 2020.
[56] Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors adversarial examples. In JCML, 2018
[57] Robert Weber, Probabilistic values for games. The Shapley Value. Essays Honor of Lloyd S. Shapley, pages 101-119, 1988.
[58] Tsui-Wei Weng, Huan Zhang, Pin- Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsich, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In ICLR, 2018.
[59] Dongxian Wu, Yisen Wang, Shu-Tao Xia, James Bailey, and Xingjun Ma. Skip connections matter: On the transferability of adversarial examples generated with resnets. In ICLR, 2020.
[60] Dongxian Wu, Shu-Tan Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization. In NeurlPS, 2020.
[61] Zhirong Wu, Shuran Song, Aditya Khosla, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets for 2.5 d object recognition and next-best-viee prediction, arXiv preprint arXiv:1406.5611 5670. 2014.
[62] Cihang Xie, Yuxin Wu. Laurens van der Maaten, Alan L Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. In CVPR, 2019.
[63] Kaidi Xu, Sijia Liu, Pu Zhao, Pin- Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus, Yanzhi Wang. and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. In ICLR, 2018
[64] Kaidi Xu, Sijia Liu, Gaoyuan Zhang, Mengshu Sun, Pu Zhao, Quanfu Fan, Chuang Gan, and Xue Lin. In- terpreting adversarial examples by activation promotion and suppression. arXiv preprint arXiv:1904 020502. 2019.
[65] Puyudi Yang, Jianho Chen, Cho-Jui Hsich, Jane-Ling Wang, and Michael Jordan. ML-L-OO: detecting adversarial examples with feature attribution. arXiv preprint arXiv:1906. 1949999996999....
[66] Dong Yin, Raphael Gontijo Lopes, Jonathon Shlens, Ekin D Cubuk, and Justin Gilmer. A fourier perspective on model robustness in computer vision. arXiv preprint arXiv: 089888 2019.
[67] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 4rXiv:660..07146. 2016.
13

---

[68] Die Zhang, Huilin Zhou, Hao Zhang, Xiaoyi Bao, Da Huo, Ruizhao Chen, Xu Cheng, Mengyue Wu, and Quanshi Zhang. Building interpretable interaction trees for deep ulp models. In AAAI, 2021.
[69] Hao Zhang, Xu Cheng. Yiting Chen, and Quanshi Zhang. Game-theoretic interactions of different orders. arXiv preprint Stdi:20000149776 2020.
[70] Hao Zhang, Sen Li, Yinchao Ma, Mingjie Li, Yichen Xie, and Quanshi Zhang. Interpreting and boosting dropout from gaee-theoretic view. In ICLR, 2021.
[71] Hao Zhang, Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang. Interpreting multivariate interactions in dnns. In AAAI, 2021.
[72] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoreti- cally principled trade-off between robustness and accuracy. In JCML, 2019.
[73] Tianyuan Zhang and Zhanxing Zhu. Interpreting adversarially trained convolutional neural networks. In ICML, 2019.
14


Reviews:
[{"review_id": "w4ITKXLMvx", "reviewer": "Reviewer_qpWF", "summary": "The authors discover and partially prove that adversarial perturbations mainly affect high-order interactions, rather than low-order interactions. \n\nThe authors find that there is a clear difference between standard DNNs and adversarially trained DNNs. Adversarial training significantly increases the robustness of high-order interactions.\n\nThe research provides a unified understanding for the success of several existing adversarial defense methods,", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There is one related paper which also performs a game theoretic analysis for adversarial attacks and defenses [*1]. The authors should make a comparison with the paper. \n\nThe authors define the disentanglement metric to identify whether interactions of this order are discriminative for the classification of a specific category, or represent common knowledge shared by different categories. Based on the disentanglement metric, the authors discover that compared with standard DNNs, adversarially trained DNNs usually encode more discriminative low-order interactions. Discriminative low-order interactions make high order interactions of adversarially trained DNNs robust to attacks.\n\nSome studies explained adversarial examples as high-frequency features and high-rank features. It is glad to see that the problem can be viewed from a different aspect. The high order interactions can better explain the essential property of attacking-sensitive representations, i.e. the complex and large-scale visual concepts.\n\n[*1] A Game Theoretic Analysis of Additive Adversarial Attacks and Defenses, NeurIPS 2020", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not mention this. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "m4hBLdIuRy", "reviewer": "Reviewer_Chfr", "summary": "This paper provides a new perspective to explain different adversarial attacks and adversarial defenses in a \"unified\" way. Specifically, the authors exploit the multi-order interactions between inputs to analyze the robustness of DNNs. Based on the multi-order interaction, this paper further investigates the representation of high-order interactions and low-order interactions and draws some interesting conclusions. Based on the observed results, this paper gives a theoretical explanation of the commonality between adversarial attacks and defenses.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "$\\textbf{Cons}:$\n\n(1) My biggest concern of this paper is that I can not agree with your statement about \"a unified view to explain different adversarial attacks and defenses\".  I am very satisfied with the perspective of the utilized \"multi-order interaction\" to conduct adversarial attacks and defenses. However, in this paper, the discussion only happened in the gradient-based adversarial attacking method ($i.e.$, PGD and momentum attack) and adversarial training defense.  I think that these attacking/defending strategies can not represent all of the adversarial area works ($e.g.$, optimization-based attacking method and other defending methods). And thus, causing the following concern: is this proposed theory can be extended to other related works? I have reservations about that.\n\n(2)In Line 261, the author claimed that adversarial perturbations towards adversarially trained DNNs penalized both complex features of global collaborations and simple features of local collaborations. However, there is no evidence to say that global collaborations mean complex features and local collaborations mean simple features, at least not provided or clarified (I see the statement in Line 288 but I can not easily agree). And according to Figure 4, it can be clearly witnessed that some x-order interactions, including low-order interactions, are increased ($i.e.$, not penalized).\n\n(3) The writing of this paper should be carefully gone through. In some paragraphs, what makes me confused is that the attacker is stated as DNN. But in my opinion, the attacker who performs attacks ($i.e.$, attack low-order interactions or high-order interactions) should be an adversarial example, not a DNN.\n\n#post-rebuttal\n\nI am satisfied with the author's explanation, so I am willing to raise my score and give a acceptance", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Almost addressed the limitations and potential negative societal impact. See my concern (2).", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Ued0Cmp1h22", "reviewer": "Reviewer_T63V", "summary": "The Shapley interaction index is leveraged to analyze the adversarial robustness, with an ambitious goal of unifying different explanations for adversarial attacks and defenses.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\na. The Shapley (interaction) index is a well-known mathematical quantity in the field of game theory and has been explored in the ML community, particularly to understand DNN [1].\n\nb. A similar decomposition of the Sharpley interaction index has also been provided in [58], which may undermine the technical novelty of the current work.\n\nc. The discovery that higher-order interactions are affected by the adv attack the most is interesting.\n\nQuality:\n\na. From Figure 3, it seems to the reviewer that the behaviors of standard and adv trained CNNs are quite similar under the $I^{(m)}$ measure. Does this mean that the adv training is not that effective? If so, this goes against empirical evidence that adv training is helpful?\n\nb. Have the authors tried to experiment with the training methods with certified robustness? The reviewer wonders whether a similar figure (like figure 3) can be produced.\n\n\nClarity:\n\na. Overall, the reviewer is comfortable reading the first two sections and begins to find the remaining sections difficult to comprehend. For example, why can the trend of $\\hat{v}(S)$ be reflected by $v(S)$? \n\nb. What are the motivations of the two equations in Eq. (4)?\n\nc. How do the authors implement the masking? Setting to zero or mid-gray or Gaussian noise? Will different choices affect the results?\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors may improve the writing by narrowing down the scope.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Ey88CeNvAYk", "reviewer": "Reviewer_Razy", "summary": "This work provides a unified understanding for adversarial perturbations and robustness based on the multi-order interaction between input variables.  The experimental results and theoretical analyses validate that adversarial perturbations are highly correlated to the high-order interactions. Adversarial training significantly improves the disentanglement of low-order interactions, thus enhancing the robustness of sensitive high-order interactions.  The proposed multi-order perspective of adversarial robustness can explain the reasons for some methods  improving adversarial robustness.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and organized. The understanding for adversarial robustness seems to be well motivated and brings much conceptual improvement. The research studies the relationship between the adversarial attacks and robustness, and multi-order interactions. \nOn one hand, the research discovers high-order interactions are frequently affected by adversarial attacks and explains this phenomenon theoretically. On the other hand, the authors show that adversarially-trained DNNs make the low-order interactions more discriminative compared to naturally-trained DNNs. Comprehensive experiments are conducted and support the claims in this paper. Besides, this paper provides the unified understanding for the success of some existing adversarial training method from this novel perspective. \n\nThere is a minor question --- I wonder if the strength of adversarial attacks (e.g., the iteration numbers of PGD) is related to the perturbations on high-order interations. That is to say, could we use the pertubetions on high-order interactions to measure the strength of adversarial attacks?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper contributes to understanding adversarial robutness. Therefore,  no potential negative societal impacts incur.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper focuses on a new perspective to explain different adversarial attacks and adversarial defenses in a unified way. The philosophy behind sounds interesting to me, namely, exploit the multi-order interactions between inputs to analyze the robustness of DNNs. This philosophy leads to the representation of high-order interactions and low-order interactions and some interesting conclusions that I have never seen.

The clarity and novelty are marginally above the bar of NeurIPS. However, there are three key issues proposed by Reviewer T63V that should be merged in your next version. First, the authors reuse the techniques to prove the decomposition of the network output in this paper, which bring limited technical novelty to the community. Please try to explain more and revise that part. Second, due to pretty much the same formulation, the proofs of linearity, nullity, commutativity, and symmetry follow straightforwardly. Third, the equivalence between the multi-order interaction and mutual information seems straightforward as well. By the way, please revise your updated version more clear and accessible, because the reviewer still fails to understand how to compute the proposed measure with seemingly combinatorial complexity.

While all reviewers had some concerns on the significance, the authors did a particularly good job in their rebuttal. Thus, most of us have agreed to accept this paper for publication. Please include the additional explanation and experimental results (especially for Reviewer T63V) in the next version. 
Decision: Accept (Poster)