Training for Stable Explanation for Free
Authors: Chao Chen
Chenghua Guo
Rufeng Chen
Guixiang Ma
Ming Zeng
Xiangwen Liao
Xi Zhang
Sihong Xie
Venue: NeurIPS 2024 poster (2024)
Keywords: accountable machine learning
stability
transparency
interpretability
Primary area: interpretability_and_explainability
TL;DR: We propose a framework for stable and transparent model without expensive training.

Abstract: To foster trust in machine learning models, explanations must be faithful and stable for consistent insights. Existing relevant works rely on the $\ell_p$ distance for stability assessment, which diverges from human perception. Besides, existing adversarial training (AT) associated with intensive computations may lead to an arms race. To address these challenges, we introduce a novel metric to assess the stability of top-$k$ salient features. We introduce R2ET which trains for stable explanation by efficient and effective regularizer,
and analyze R2ET by multi-objective optimization to prove numerical and statistical stability of explanations. Moreover, theoretical connections between R2ET and certified robustness justify R2ET's stability in all attacks. Extensive experiments across various data modalities and model architectures show that R2ET achieves superior stability against stealthy attacks, and generalizes effectively across different explanation methods. The code can be found at https://github.com/ccha005/R2ET.

Training for Stable Explanation for Free
Chao Chen'
Chenghua Guo
Rufeng Chen Guixiang Ma*
Ming Zeng" Xiangwen Liao Xi Zhang?
Sihong Xie
SSchol of Computer Science and Technology. Harbin Institute of Technology (Shenzhen), China
Key Laboratory of Trustworthy Distributed Computing and Service (MoF),
Beijing University of Posts and Telecommunications, China
Artificial Intelligence Thrust, The Hong Kong University of Science and Technology (Guangzhou), China 4 Intel, USA *Carnegie Mellon University, USA
"College of Computer and Data Science, Fuzhou University, China chaOinboz@gmail. com {chenghuaguo zhangx) @bupt edu, schen514@connen hkust-gz. wad.edu.com cn jean. maguixi ang@gmail com ming zeng@sv. cmu. edu *Corresponding to: liaoxwθfzu edu. com
Abstract
To foster trust machine learning models, explanations must faithful and stable for consistent insights. Existing relevant works rely the Ep distance for stability assessment, which diverges from human perception. Besides, existing adversarial training (AT) associated with intensive computations may lead arms race. To address these challenges, we introduce a novel metric to assess the stability of top-k salient features. We introduce R2ET which trains for stable explanation by efficient and effective regularizer, and analyze R2ET by multi- objective optimization to prove numerical and statistical stability of explanations. Moreover, theoretical connections between R2ET and certified robustness justify R2ET's stability in all attacks. Extensive experiments across various data modalities and model architectures show that R2ET achieves superior stability against stealthy attacks, and generalizes effectively across different explanation methods. The code can be found at htthpss://gittt thgggtht.b.... cww ccmm005/h00
Introduction
Deep neural networks have proven their strengths in many real real-world applications, and their ex- plainability is fundamental requirement for humans' trust [25] 62]. Explanations usually attribute predictions to human-understanddabe basic elements, such as input features and patterns under net- work neurons 35 Given the inherent limitations of human cognition
69 only the most relevant top-k features are presented to the end-users [89]. Among many existing explanation methods, gradient-based methods [55] 24 are widely adopted due to their inexpensive computation and intu- itive interpretation. However, the gradients can be significantly manipulated with neglected changes the input [6 23 The susceptibility of explanations compromises their integrity as trustworthy
evidence when explanations are legally mandated [25] such as credit risk assessments 4
Challenges. As shown in Fig. novel explanation methods 77 and training methods
are proposed to promote the robustness of explanations. We focus on training methods since novel explanation methods require extra inference (explanation) time and may fail the sanity check M. Existing works 17
13 16] study the explanation stability (robustness) through lp distance. However, as shown in the right part of Fig. [ perturbed explanation with a small lp distance the original can exhibit notably different top salient features. Therefore, relying on f, distance as a metric for optimizing the explanation stability fails to attain desired robustness, indicating the necessity for
88
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Truining Methood
1
3
Explanation Grad'
Z(x')
Z(x)
Zix")
Vanilla Training
AT
Ma
based
Sarapo
Incees
Regulanizer:
Hessiza-relatee relottd
Target Engur
Explacation I[x] H8)
Rdacrion
RIET (ours)
x
x
Zix:
0.1
Goallmaax Dist Dist( (Z(x), Zix'))
Raad
Dist =fle nonn
2000 X0xila - 0.30 2007
[2000 200
Kankiing (ours)
Figure 1: Left: Green (0): Model training. Yellow (2-4): Explanation generation for target input. Red (Q- Adversarial attacks against the explanation by manipulating the input. Right: Two examples of the saliency maps (explanations) show that smaller Ep distances do not imply similar top salient features. I(x") has a smaller &a distance from the original explanation Z(x), but manipulates the explanation more significantly (by top-k metrie) shown in blue dashed boxes. Statistically, I(x') has a 67% top-3 overlap in the tabular case, and 36% top-50 overlap in the image, compared with I(x') y's 100% and 92% top-k overlap, respectively.
novel ranking-basse -ased distance metric. Second, unlike robustness of prediction and lp distance based explanation, analyses of robustness on ranking-based explanations are challenging due to multiple objectives (feature pairs), which are dependent since features are from the same model. Finally, adversarial training (AT) 866. [4] has been adopted for robust explanations, yet it potentially leads to an attack-defense arms race. AT conditions models on adversarial samples, which intrinsically rely on the objectives of the employed attacks. When defenders resist well against specific attacks, attackers will escalate attack intensity, which iteratively compels defenders to defend against fiercer attacks. Besides that, AT is time-intensive due to the search for adversarial samples per training iteration.
Contributions. We center our contributions around a novel metric called "ranking explanation thickmess" that precisely measures the robustness of the top-k salient features. Based on the bounds of thickness, we propose R2ET, a training method, for robust explanations by an effective and efficient regularizer. More importantly, R2ET comes with a theoretically certified guarantee of robustness to obstruct all attacks (Prop. 4.5). avoiding the arms race. Besides certified robustness, we theoretically prove that R2ET shares the same goal with AT but avoids intensive computation (Prop. 4.6). and the connection between R2ET with constrained optimization (Prop. 4.7). We also analyze the problem by multi-objective optimization to prove explanations' numerical and statistical stability in Sec. 5
Results. We experimentally demonstrate that: i) Prior lp norm attack cannot manipulate explanations as effectively as Lunking-based attacks. R2ET achieves more ranking robustness than state-of satee-of-the- the- art methods; ii) Strong evidence indicates a substantial correlation between explanation thickness and robustness; iii) R2ET proves its generalizability by showing its superiority across diverse data modalities, model structures, and explanation methods such as concept-based and saliency map-based.
2 Related Work
Robust Explanations. Gradient-based methods are widely used due to their simplicity and efficiency (55), while they lack robustness against small perturbations (23]. Adversarial training (AT) used to improve the explanation robustness 13 74]. Alternatively, some works propose replacing ReI.U function with softplus [17). training with weight decay [16), and incorporating gradient- and Hessian- related terms regularizers [17 88 91]. Besides, some works propose post-hoc explanation methods, such as SmoothGrad (75). More relevant works are discussed Appendix C
Ranking robustness in IR. Ranking robustness in information retrieval (IR) is well-studied [106] 26 104]. Ranking manipulations in IR and explanations are different since 1) In IR, the goal is to distort the ranking of candidates by manipulating one candidate or the query. We manipulate input to swap any pairs of salient and non-salient features. 2) Ranking in IR is based on the model predictions. However, explanations rely on gradients, and studying their robustness requires second or higher-order derivatives, necessitating an efficient regularizer to bypass intensive computations.
3 Preliminaries
Saliency map explanations. Let classification model with parameters w be fxx, w) R (0, 1Jc and fe(x, w) the probability of class e for the input x. Denote saliency map explanation for concerning class as I(xx c; f) Vxfe(x, w). Since ff is fixed for explanations, we omit

---

w and fix to the predicted class. We denote Z(x, cx f) by I(x), and the i-th feature's 's importance score, e.g., the i-th entry of [(x). (x). The theoretical analysis following will mainly based on saliency explanations, and more explanation methods, such as Gradx Inp, SmoothGrad [7] and IG
777. are studied Sec. 6 and Appendix A.1.2
Threat model. The adversary solves the following problem to find the optimal perturbation 8* to distort the explanations without changing the predictions [7]
8 = arg max (xx), I(x + 6)), S.L. arg max fx(x) arg max fe(x + 8).
(1)
is the perturbation whose & norm is not larger than a given budget e. Dist(:.)) evaluates how different the two explanations are. We tackle constraints by constrained optimization (see B.2.3 and will not explicitly show the constraints.
Explanation Robustness via Thickness
We first present the rationale and formal definition of thickness in Sec. 4.1 then propose R2ET
algorithm to promote the thickness grounded on theoretical analyses in Sec. 4.2 All omitted proofs and more theoretical discussions are provided in Appendix A
4.1 Ranking explanation thickness
Quantify the gap. Given model f and the associated original explanation I(x) with respect to an input x E R", we denote the gap between the i-th and j-th features' importance by h(x, j, = (x). Clearly, h(x, i. > 0 if and only if the i-th feature has more positive contribution - [x)- to the prediction than the j-th feature, The magnitude Although the feature importance order varies across different x, for notation brevity, label the features in a descending order such that hxx, i. >> O, Vi < j, holds for any original input x. This assumption will not affect the following analysis.
reflects the disparity in their contributions.
Pairwise thickness. The adversary in Eq. 1 searches for perturbed input x' to flip the ranking between features i and j so that h(x', i) < O for some < j. A simple evaluation metric, such as 0 11 [x(x,, (11(xxi,) i) 2 0). can only indicate if the ranking flips at x', failing to quantify the extent of disarray. Moreover, it is greatly impacted by the choice of x'. Conversely, the explanation thickness defined by the expected gap of the relative ranking of the feature pair (i,j) in a neighborhood of x.
Definition 4.1 (Pairwise ranking thickness). Given a model f. an input x E X' and a distribution 'D of perturbed input x' D. the pairwise ranking thickness of the pair of features (i,j) is
o(f.x,D,i.j) de ExIND [(" h(x((), d.
where x(t) = (1 - t)x + tx E [0, (2)
The integration computes the average gap between two features from x'. The expectation over x' ~ 'D makes an overall estimation. For example, x' can be from a Uniform distribution [88) or the adversarial samples local to x (97). The relevant work [97] proposes the boundary thickness to evaluate model's prediction robustness by the distance between two level sets.
propose maintaining the ranking between every two entities (features). However, as shown in Fig. I only the top-k important features in I(x) attract human perception the most, and will be delivered end-users. Thus, we focus on the relative ranking between a top-k salient feature and any other non-salient one.
Top-k thickness. Existing works in general robust ranking 105
Definition 4.2 (Top-k ranking thickness). Given a model f, input x E X, and distribution D of x' D. the ranking thickness of the top-k features is
O x. D.K)
Σ
Σ OU.x,D,i,3)
(3)
knn
Variants and discussions. We consider and discuss the following three major variants of thickness.
One variant of thickness Eq.
2 in probability version:
(pr(fxx, jj der Ex [ (1((x(t),,,,)) 2 oldt
3

---

However, the inherent non non-differentiability of the indicator function hinders effective analysis and optimization of thickness. One may replace it with a sigmoid to alleviate the non diffferentiabbiity issue. Yet, the use of sigmoid can potentially lead to vanishing gradient problems.
By considering the relative positions of the top-k features, one can define an average precision @I
1 K like thickness O ap R k==1 (f, D, k), or discounted cumulative gain 33] like thickness
def
* th i-11 2 Tog0-E+1) Other variants for specific properties or purposes can be derived similarly, and we will study these variants deeply in future work.
dog
Σ
e(fx.D.i.))
Many non-salient features are less likely to be confused with the top-k salient features (see Fig. g). and treating them equally may complicate optimization. Thus, one may approximate the top-k thickness by k' pairs of features Σ h(x, k- k-i. -ii+), which selects k' distinct pairs with minimal h(x, j). We include the case when k' k denoted with the suffix "-mm" in the experiments.
4.2 R2ET: Training for robust ranking explanations
We will theoretically (in Sec. 5 and experimentally (in Sec. 6 demonstrate that maximizing the ranking explanation thickness in Eq. (3) can make attacks more difficult and thus the explanation more robust. Thus, a straightforward way is to add @ x, D, k) as a regularizer during training:
min L = Ex [Ca - XO(S; x, D)]:
where Lote is the classification loss. However, direct optimization of θ requires M1 x M2 X 2 backward propagations per training sample. M1 is the number of x' sampled from D; M2 is the number of interpolations x(t) between x and x'; and evaluating the gradient of h(x, i,j) requires at least 2 backward propagations [59]. In response, we consider the bounds of θ in Prop. 4.4 and propose R2ET which requires only backward propagations each time.
Definition 4.3 (Locally Lipschitz continuity). A function f is I-locally Lipschitz continuous
S c. Proposition 4.4. (Bounds of thickness) Given an I.-locally Lipschitz model f. for some T. > 0, pairwise ranking thickness @f,, "( j. is bounded by
[lf(x) f(x))))))))))))) l22 I L||x x'I22 holds for all x' B2(x, c) fx' E R ||x 1xx-xt x'
N(x,i,)) -c* c* (x) (x) S @ D,i,)) S Mxx, + (L+ + Lj);
(5)
where Hx(x) is the derivative of [x() with respect to x, and L; = maxx |H (x')
Noticing lim [xx)lla-> Of,,x, i) h(x, j). the objective of the proposed R2ET, Robust Ranking Explanation via Thickness, is to maximize the gap and minimize Hessian norm:
min C = Ex Lets A Σ Σ Mxx A2 H2)1
(6)
where A1, Ag O. R2ET with A O recovers Hessian norm minimization for smooth curvature
[7]. The difference between R2ET in Eq. (6) and vanilla model are two regularizers. h(x, i, = [x)) -I, (x) can be calculated by one time backward propagation over I(x), and the summations are done by assigning different weights to (x),, e.g., (n - k) for <= k. and -k for > k. [x(()]]2 is estimated by the finite difference (calculating the difference of the gradient of I(x) and I(x + 8)), which costs two times backward propagation (52] Thus, R2ET is at an extra cost of times backward propagation. For comparison, AT (in PGD-style) searches the adversarial samples by
M2 (being 40 in 13 70)) iterations for each training sample in every training epoch.
We connect R2ET to three established robustness paradigms, including certified robustness, AT, and constrained optimization. Intuitively, three methods assess robustness from the adversary's perspective by identifying the worst-case samples and restricting model responses to these cases. Conversely, R2ET is defender-oriented, which preserves models' behavior stably by imposing restrictions on the rate of change, avoiding costly adversarial sample searches.
Connection to certified robustness. Prop. 4.5 delineates the minimal budget required for a successful attack. The defense strategy of maximizing the budget can effectively mitigate the arms race by obstructing all attacks. The strategy essentially aligns with R2ET, but empirically less stable and harder to converge due to the second-order term in the denominator. The proof is based on (28).

---

Proposition 4.5. For all 6 with ||ô]12 S min( maxx HH(x') H it holds [[,(x,,,) > 0] 11[[(x 6,1,)) 0] for all (1. pair, that all the feature rankings do not change.
h(x.-))
Connection to adversarial training (AT). Prop. 4.6 Liimllis that R2ET shares the same goal AT but employs regularizers to avoid costly computations. The proof Appendix is3 based on 194.
Proposition 4.6. The optimization problem in Eq.
(6 is equivalent to the following min-max problem:
min (6,,
max EM
Rxx file
Σ
Σ 1=1
h(x + 86., 863)
(7)
where 61,5 R is perturbation targeting the (i. pair of features. M is the feasible of perturbations where each ö5, is independent of each other, with |I Ee, 8G.5
shows that R2ET aims to keep the feature in the "correct" positions, c.g., 1,Zz 2 G₁2 for the local vicinity of original inputs, thus promoting robustness. First, Eq. (6) can be considered Lagrange function for the constrained problem in Eq. (8)
Connection to constrained optimization. Prop. 4.7
min Ex (Cris + {x)
I,I(X) 2 G., Vi E (I,....n):
(8)
where G; 2 0 is a predefined margin. I; (n k) for S k. and L; - otherwise, which labels features the top as positive and those at the bottom as negative. The proof is based on 34
Proposition 4.7. The optimization problem Eq. (8) is equivalent to the following problem:
min
Ex [Crse]
s.t.
min &ell
4x (.) G., ViE nn.
w
Analyses of numerical and statistical robustness
Numerical stability of explanations. Different from prior work, we characterize the worst-case complexity of explanation robustness using iterative numerical algorithm for constrained multi- objective optimization. Threat model. The attacker aims to swap the ranking of any pair of salient feature i and a non-salient feature j. so that the gap hxx, i. < O, while does not change the input and the predictions fxx significantly for stealthiness. We assume that the attacker has access the parameters and architecture of the model ff to conduct gradient-based white- box attacks.
Optimization problem for the attack. Each h(x, i, can be treated as an objective function for the attacker, who however does not know which objective is the easiest to attack. Furthermore, attacking one objective can make another easier or harder attack due to their dependency on the same model f and the input x. As a result, an attack against a specific target feature pair does not reveal the true robustness of the feature ranking. We quantify the hardness of successful attack (equivalently, explanation robustness) by upper bound the number of iterations for the attacker to flip the first (unknown) feature pair. The longer it takes to flip the first pair, the more robust the explanations of (x) are. Formally, for any given initial input x0) ((p) in the superscript means the p-th attacking iteration), the attacker needs to iteratively manipulate x to reduce the gaps l(x, i,
for all E {l....,k) k) and j E {ke 1.....,)) n) packed in a vector objective function:
MOO-Attackxx, e): min [b (x)...., hm (x)], s.t. [x f(x(()) Se.
(10)
where (x)) N(xx i.j), with l t= 11 1,....,, m indexing the m pairs of (i,j).
Comments: (i) The scalar function E. E, i,j) is unsuitable for theoretical analyses, since there can be pair of features flipped at a stationary point of the sum. Simultaneously minimizing multiple objectives identifies when the first pair of features is flipped and gives pessimistic bound for defenders (and an optimistic bound for attackers).
(ii) We could adopt the Pareto criticality for convergence analysis (21), but Pareto critical point indicates that no critical direction (moving in which does not violate the constraint) leads to joint descent in all objectives, rather than that an objective function by has been sufficiently minimized. (ii) Different from the unconstrained case in [19], constrain the amount of changes in x and (x).
5

---

We propose a trust-region method, Algorithm 1
to solve MOO-Attack (A.4 more details), First, we define the merit function @ that combines the f-th objective and the constraint in Eq. (T):
(x(x,
t) def [x)]l + [he(x) t|.
(11)
As an approximating model for the trust-region method, the linearization of Φ(x, t) is
Lsee (x, f, d) (l.(x) + (xx)
T dll [he(x) + ge(x) t/,
where (xx is the Jacobian of f and ge (x) is the gradient of he. The maximal reduction in L0, (x, t, 0) within a radius of A > is
Xe (x, t)
Le (x, t, 0)
min L0 (x, t, d).
(12)
d:jdi|sa
x is called a critical (approximately critical) point of oe when Xe(x, t) = 0 (or S E).
Algorithm 1 Attacking a pair of features
Input: target model f. imput x, explanation I(x), trust-region method parameters < Y, < 1.
2: Set k ==1 1, x(P) x, (0)) = [x(())) hh - (P))
3: while minigesm (x(p),, ((2) 2 do
4: Solve TR-MO0(x(P), A (p)) obtain joint descent direction d(z) for all loc-
5: Update Pe using d(e) for each = 1,..... m.
if mine Pi (p) 17 then
6:
7: Update 1 (x+1) and x(++1).
8: else
9:
Update ((++1) = A
10:
end if
11:
end while
The core of Algorithm| is TR-MOO(x, A), whose optimal solution provides a descent direction d for all linearized merit functions la. (not be (b)):
{
mina,d
TR-MOO(x, A)
s.t.
Lar
(x, 1, d) Va ||d|| S.
where is the minimal amount of descent and A the current radius of search for d.
Different from the local convergence results (20g we provide a global rate of convergence for Algorithm to justify thickness maximization in Theorem [.1] Specifically, it implies that increasing gaps between salient and non-salient features tend to result in larger Itep hlow. which makes it harder for attackers to alter the rankings, leading to stronger explanation robustness.
Theorem 5.1. Suppose that f(x) and hx(x) are continuously differentiable and he bounded. Then Algoritium generates an e-first-order critical point for problem Eq. (10) at most (hup -hlow) Ch
iterations, where is a constant independent of but depending on 7y and v in Algorithm hup def
de maxxfmax, ha hy(x)....., maxx Nm (x)), and hlow mine (min h1
hm (x)).
Statistical stability of explanations. We use McDairmid's inequality for dependent random vari- ables and the covering number of the space F of saliency maps I in Theorem 5.2 The theorem justifies maximizing the gap by showing bound on how likely a model can rank some non-salient features higher than some salient features due to perturbation to x. Specifically, for consistent empirical risk level Re larger gap corresponds a larger u, which leads smaller covering number (JF ). It indicates a reduced probability of high true risk R thereby implying more explanations robustness against perturbations. Importantly, this insight is universal regardless of the approach to achieving the larger gaps. See Appendix A.5 relevant definitions and details.
Theorem 5.2. Given model f. inpul x, surrogute loss the and a constant >> O. for arbitrary saliency map I E F and any distribution D surrounding x that preserves the salient features in x,
Pr { Rin (I,x) x) 2 R + +e} S exp (- 2mm2
(-x
N
(F
Eu
X

---

Table 1: P@k & (shown in percentage) of different models (rows) under ERAttack MSE attack. k for the first three dataset, and & 50 for the rest. Bold (and underlines) highlight winner (and runner-up). i indicates the significant superionity between R2ET winner and non-R2ET winner (pairwise t-test at a 5% significance level). * Est-H has about 4% lower clean AUC than others on BP. Exact- H and SSR only apply to tabular datasets, since computing the exact Hessian and its eigenvalues is extremely expensive.
Method
Adult
Bank
COMPAS
CIFAR-I0
ROCT
ADHD
BP
features
28
18
16
28*28
32*32
771"514
6555
3240
Vanilla
87.6/ 87.7
83.0/94.0
89,2/99.7
59.0/
66.5 68.3
71.7
45.5/8111
09.4/88.9
91.7 91.8
82.4
87.7 99.4
59.1 64.8
65.2/66.6
71.2 68.9
79.6/7944
69.4/ 88.6
97.5
95.4/95.5
62.9/669
81.
68.7/90.
Est-H
87.1 / 87.2
88.4/81.8
87.6/97.7
85.2/90.2 -/-
77.1 -/-
78.9/78.0
38.2/83.7 -/-
(75.0/91.4)
Exact II
89.6 89.7
$1.9/85.66
71.2/ 96.0
-1-
-/-
91.2/
76.3 84.5
97.1
-/-
-/-
AT
91,4
80.0/ 88.4
84.27 90.5
56.0 63.9
61.6/ 66.8
78.0 72.9
89,4/81.0
72.0/89
R2ET
97.5 97.77
100.0" 100.0*
91.01 99.2
82.8 89.7
67.3 72.2
79.4 70.9
60.7/ 86.8
70.9/ 89.5
R2ET-mm
93.6
95.87 98.2
95.37 97.2
81.6/89.7
77.2 77.44
60.2
64.2/
72.4/910
R2ET
92.1 92.7
B0.4 / 90.5
92.07 99.9
85.7 / 90.88
75.0/ 77.4
79.37 70.9
71.6 /91.3
/ 89.99
R2ET-mm
87.8 87.9
75.1 / 85.4
82.1 998.4
99.4/
78.0" 79.1
/
58.8 1..8/88 87.5
73.8 /91.1
where N is the covering number of the space with radius [102]. X is the chromatic number of a dependency graph of all pairs of salient and non-salient features (81] for McDairmid's 'ss inequality.
6 Experiments
This section experimentally validates the proposed defense strategies, R2ET, from various aspects, and Appendix [B] provides more details and results. For a fair comparison, R2ET operates without any prior knowledge of the "true" feature ranking. At each training iteration, R2ET aims to preserve the feature ranking determined in the immediately preceding iteration.
Datasets. We adopt DNNs for three tabular datasets: Bank [53]. Adult, and COMPAS [34], and two image datasets, CIFAR-10 10 (36] and ROCT [22]. ROCT consists of real-world medical images having 771x514 pixels on average, making it comparable in scale to CelebA (178x218) 8), ImageNet (469x387), and MS COCO (640x480). Besides, dual-input Siamese networks
48 are adopted on
MNIST 40) and two graph datasets, BP 48 and ADHD 44
Evaluation metries. Precision @ k (P@ k) 88 is used quantify the similarity between explanations in Appendix B.2.6 to show that
before and after attacks. We adopt three faithfulness metrics 72 15
explanations from R2ET are faithful.
All the models have comparable prediction performance. Specifically, the vanilla models achieve AUC of 0.87, 0.64, 0.83, 0.99, 0.87, 0.82, 0.69, and 0.76 on Adult, Bank, COMPAS, MNIST, CIFAR- 10, ROCT, BP, and ADHD, respectively. Correspondingly, all other models reported only when their AUC is no less than 0.86, 0.63, 0.83, 0.99, 0.86, 0.82, 0.67, and 0.74, respectively.
Explanation methods. Gradient (Grad for short) is used as the explanation method if not specified. We also share findings when adopting robust explanation method, e.g., SmoothGrad (SG) [75] and Integrated Gradient (IG) 777, and concept-based explanation methods (on ROCT datasets).
6.1 Compared methods
We conduct two attacks in the PGD manner [0 Explanation Ranking attack (ERAttack) and MSE attack. ERAttack minimizes Σ Ej h(x', ((x',,,) i, to manipulate the ranking of features in explanation Z(x), and MSE attack maximizes the MSE (i.e., l, distance) between I(x) and [(x').
The proposed defense strategy R2ET is compared with the following baselines.
Vanilla: provides the basic ReLU model trained without weight decay or any regularizer term.
Curvature smoothing based methods: Weight decay (WD) 17 implicitly binds Hessian norm by weight decay during training, and Softplus (SP) 16 17 replaces ReLU with Softplus(x;;)) p) = In(1 + e..). Est-H [17] and Exact-H consider the estimated (by the finite difference (52) and

---

Table 2: P@k models under ERAttack when adopting Grad SG / IG as the explanation method.
Method
Adult
Bank
COMPAS
MNIST
ADHD
BP
Vanilla
87.6/94.0/11.
83.0/ 90.0 88.1
84.2 92.9/ 94.7
59.D/67.9/82
4 56.9
59,4 60.8
WD
91.7197.3/5555
$2.4/91.3855
87.7 (97./97.4/999 99.1
59.1 68.1/830
47.6/42.1/5.22
69.4/61.8
SP
97.4/95.3/633 63.9
25.4/96.7999
99.5/ 100.0/ / 100.0
62.9/69.0/ 85.4
42.5/
36.9/4499
68.7 58.6 60.5
Est-H
87.1/93.1/61.
78.47 87.3 / 82.4
82.6/ 8 89,9
87.9/ 89.5
48.2/4489/547
(75.0/ /3.0/ 58.5)
AT
68.4/76.6/ 60.0
80,0/ 85.9/ 82.6
84.2 85.9 82.4
56.0/61.5 79.3
59.4/41.2/4..0
72.0/ 56.7/
R2ET, a
97.5/97.5//7..
100.0/
100.0/ 100.0
91.0/ 99.6 93.6
82.8 82.8/ 89.0
60.7/56.//60
64.2/ 66.0
RDET-mm,, x
1/5/97.4/55.9
95.8/ / 96.3
25.3 99.1 / 95.5
81.6/ 86.8/ 88.7
64.2 59.5 66.9
22.4 / 65.5 64.1
R2ET
92.1/99.3/544
84.4 80.4/
92.0/ /9.7 100.0
85.7 /8.5
71.6/ 67.2/65..
71.5 14.5/64.0/655 /65.0
R2FT-mm
87.8 54.2.
75.1 85.1 / 80.3
82.1 99.55 99.5
85.3/ / 88.1/90.1 /90.1
58.8/ 50.1 /51.4
73.8 / 65.6 /
exact Hessian norm as the regularizer, respectively. SSR [88] sets the largest eigenvalue of the Hessian matrix as the regularizer.
Adversarial Training (AT)
31 92 finds f by miny Las + 8", where 5*
arg max, -E Σj=x+1 1
Variants of R2ET: R2ET-mm selects multiple (k) distinct i.j with minimal h(x, as discussed
in Sec. 4.1 R2ET H and R2ET-mm, н are the ablation variants of R2ET and R2ET-mm, respectively, without optimizing the Hessian-related term in Eq. (6) (A2 0). Est-H can be considered an ablation variant of R2ET (A1 = 0).
6.2 Overall robustness results
Attackability of ranking-based explanation. [ the explanation robustness of different models against Attttack and MSE attacks on all datasets. More than 50% of models achieve least 90% P@ l: against MSE attacks, concluding that MSE attack cannot effectively alter the rankings of salient features, even without extra defense (row Vanilla). The ineffective attack method can give false (over-optimistic) impression of explanation robustness. In contrast, ER Attak can displace more salient features from the top-k positions for most models and datasets, leading significantly lower P@* k values than MSE attack. Intuitively, R2ET performs better against attacks since the attackers (by either MSE attack or ERAttack) are supposed keep the predictions unchanged. R2ET maintains consistency between model explanations and predictions, which ensures that significant manipulation in the top salient features leads to a detectable change the model's ' predictions.
Effectiveness of R2ET against ERAttacks. We evaluate the effectiveness of different defense strategies against ERAttack, and similar conclusions can be made with MSE attacks case. (1) The best (highest) top-k of R2ET and its variants across most datasets indicate their superiority in preserving the top salient features.
(2) It is counter-intuitive that R2FT H as an ablation version of R2ET, outperforms R2ET on Adult and Bank. The reason is that R2ET . has the highest thickness on these datasets (see Table 3 in Sec. (63). (3) Overall, the curvature smoothing- based baselines without considering the gaps among feature importance perform unstably and usually badly across datasets. Their inferior performance is exactly consistent with the discussion in Sec 4.2 Specifically, solefy minimizing Hessian-relan related terms may marginally contribute to the ranking robustness. (4) We do not compare with many AT baselines 774 70 but Fast-AT [92,, which provides a fairer basis for comparing with R2ET and baselines since they require similar training time and resources. However, AT suffers from unstable robust performance and cannot perform well on most datasets.
Apply R2ET to other explanation methods. We demonstrate the efficacy and generalizability of R2ET by adopting the concept-basee explanation method, SG and IG, respectively.
Concept-based explanation shows the neurons' maximal activations in a specific model layer. We concentrate on the 512 neurons in the penultimate layer of ResNet 27] ROCT. To this end, the most stimulated neurons must be stable under perturbations. We define I, as the activation map of the i-th penultimate neuron, and derive the objective analogous to Eq. (6). Empirical results in Table (col ROCT) illustrate that R2ET and its variants, again, perform best against ERAttack.
Table 2 reports the results of models trained using Grad but evaluated by SG and IG. The following conclusions can be drawn: (1) Compared to Grad, SG and IG generally promote explanation robustness. Notably, regardless of the explanation method used, R2ET and its variants consistently
8

---

achieve the highest P@k. (2) Applying Grad to R2ETs usually results in greater robustness than adopting SG/IG to baselines. For example MNIST, R2ET with Grad attains P@ k of 85%, while applying SG to the baselines (except Est-H) fails to exceed a P@K k of 70%. (3) R2ET can generalize and transfer the robustness to explanation methods divergent from those utilized during training.
6.3 Understanding thickness and attackability
Assessing model vulnerability: critical role of thickness. As discussed in Section [ the number of attack iterations required to reach the first successful flip between salient and non-salient features characterizes the ranking explanation robustness. In Fig. [ each dot in subplots represents an individual sample x. The left subplot demonstrates high correlation between the sample's thickness and the attacker's required iterations to manipulate the rankings. This high correlation signifies that samples with greater thickness demand a larger attack budget for a successful manipulation, thereby justifying thickness as more precise metric of explanation ranking robustness.
To understand why R2ET does not always outperform other models, Table juxtaposees P@ k with dataser-level thickness, defined as the average thickness of all samples across a dataset. Notably, the model exhibiting optimal explanation robustness (P@ k) consistently displays the greatest thickness, irrespective the method employed, aligning with Theorem 5.2
Optimal Method Selection. Thickness has proven its efficacy as an indicator for evaluating ex- planation ranking robustness, rendering it an apt criterion for method selection. Table [ indicates more straightforward way to pick model: deploy R2ET H (and R2ET-mm, for datasets with a limited feature set, and R2ET (and R2ET-mm) for datasets for datasets with more features. This is because distinguishing salient and non-salient features is easier in datasets with fewer features. Conversely, maintaining such distinctions becomes more complex and potentially less efficient as the feature count increases, where reducing the Hessian norm is advantageous, it complicates the manipulation of feature magnitude.
1000
noo
800-
600
Correlation:
600
Table 3: P@k under ERAttack / model-level thickness. Refer to Table 5 for more results.
400
400
200
200
Correlation: 0.06
0.90
0.92
3.94 0.36 0.98
1.50
ca 1.0 15
thiocness
Method
Adult
COMPAS
BP
Figure 2: The number of iterations to first flip versus sample-level level thickness (Ieft) and Hessian norm (right) for R2ET on COMPAS. Each dot represents an indi- vidual sample x.
SP
97.4 / 0.9983
99.5 0.9999
68.7 / 0,9000
62.6/099557
75.0/ 0.93563
R2ET
97.5 0.9989
91.0/0.9727
70.9 7.99/1
R2FT
92.1 0.99970
92.0/ 0.9866
71.5 0.9926
R2ET-mm
87.8/0.9994
82.1 0.9544
73.8/ 0.93561
6.4 Case study: saliency maps visualization
For visual evaluation, Fig. B displays models' saliency maps the ideal testbeds, MNIST and CIFAR-10. On MNIST, Vanilla and WD perform poorly, where about 50% of the top 50 important pixels fell out of top positions under attack. Even worse, the salient pixels identified by Vanilla and WD fail to highlight the digit's spatial patterns (e.g.. pixels covering the digits). In contrast, R2ET and R2ET-mm maintain over 90% of salient features encoding the digits' recognizable spatial patterns on the top. Similar trends are observed in CIFAR-10 10, exemplified by the ship. Vanilla and WD exhibit inferior P@ ls scores, whereas R2ET and R2ET-mm achieve around 90% @@k. Interestingly, all four models identify the front hull of the ship as the significant region for the predictions. However, ERAttack manipulates the explanations of Vanilla and WD include another region, the wheelhouse. while the critical explanation regions of R2ET and R2ET-mm under attacks remain unaffected. The wheelhouse could be a reason for the ship class, but the inconsistency in explanations due subtle perturbations raises confusion and mistrust. Fig, provides more results concerning all models.
Conclusion
We proposed "explanation ranking thickness" to measure the robustness of the top-ranked salient features to align with human cognitive capability. We theoretically disclosed the connection between

---

Original Input
Vanilla
R2ET
R2ET-mm
ori
pert.
pert.
pert.
ori.
pert.
Fou-SE EN
3
Figure 3: Explanations of original (ori.) and perturbed (pert.) images against ERAttack from MNIST (class digit k=50) and CIFAR-10 (class ship, k=100). The top k salient pixels highlighted, and darker colors indicate higher importance. P@ is reported within each subplot.
thickness and min-max optimization problem, and global convergence rate of constrained multi-objective attacking algorithm against the thickness. The theory leads to an efficient training algorithm R2ET. On 8 datasets (vectors, images, and graphs), compared 7 state-of-the-an baselines and 3 variants of R2ET, and consistently confirmed that explanation ranking thickness is strong indicator of the stability of the salient features. However, R2ET is based on the surrogate loss of thickness, rather than exact thickness, which prevents from outperforming others all the time. Besides, the theoretical analysis and discussions are based on gradient-basee explanation methods. In the future, we plan to further apply R2ET to a broader spectrum of explanation methods. We also plan investigate scenarios involving highly variable and noisy data and further adjust R2ET to ensure robustness and reliability in more diverse and challenging environments. This paper goals to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel are negative and must be specifically highlighted here.
8 Acknowledgments
This material based upon work supported by the National Science Foundation under Grant Num- ber 2008155. Chao Chen was supported by the National Key Research and Development Pro- gram of China (No. D023YFB3106504), Pengcheng-Cii 2024ZY2B0050), and the Natural Science Foundation of China (No. 62476060). Chenghua Guo and Zhang were supported by the Natural Science Foundation of China (No. 62372057). Rufeng Chen and Sihong Xie were supported in part by the National Key R&D Program of China (No. 2023YFF0725001), the Guangzhou-HKKSS HKUST(GZ) Joint Funding Program (No. 2023A03J0008), and Education Bureau of Guangzhou Municipality, Xiangwen Liao supported by the Natural Science Foundation of China (No. 62476060).
Mobile Jointly Funded Project (No.
10

---

References
[1] Julius Adebayo, Justin Gilmer, Michael Muelly, lan Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. NeurIPS, 31, 2018.
Shivani Agarwal. The infinite push: new support vector ranking algorithm that directly optimizes accuracy at the absolute top of the list. In SDM, 2011.
[3] Marco Ancona, Cengiz Oztireli, and Markus Gross. Explaining deep neural networks with polynomial time algorithm for shapley value approximation. In ICML, 2019.
[4] Christopher Anders, Plamen Pasliev, Ann-Kathin Dombrowski, Klaus- Robert Müller, and Pan Kessel. Fairwashing explanations with off-manifold detergent. In ICML, 2020.
[5] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of Computing, 2012.
[6] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 2015.
[7] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. ICML, 2019.
[8] Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Smooth loss functions for deep top-k classification. ICLR, 2018
[9] Coralia Cartis, Nicholas I M Gould, and Philippe L Toint. On the complexity of finding first-order critical points in constrained nonlinear optimization. Mathematical Programming, 2014.
[10] Aditya Chattopadhyay, Piyushi Manupriya, Anirban Sarkar, and Vineeth N Balasubramanian. Neural network attributions: A causal perspective. In ICML, 2019.
[11] Chao Chen, Yifan Shen, Guixiang Ma, Xiangnan Kong. Srinivas Rangarajan, Xi Zhang, and Sihong Xie. Self-learn explain siamese networks robustly. ICDM, 2021.
[12] Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. L-shapley and c-shapley: Efficient model interpretation for structured data. ICLR, 2019.
[13] Jiefeng Chen, Xi Wu, Vaibhav Rastogi, Yingyu Liang, and Somesh Jha. Robust attribution regularization. NeurlPS, 2019.
[14] Zhun Deng, Linjun Zhang, Amirata Ghorbani, and James Zou, Improving adversarial robust- ness via unlabeled out-of-domain data. In AISTATS, 2021.
[15] Jay Young, Sarthak Jain, Nazneen Fatema Rajani, Eric Lehman, Caiming Xiong, Richard Socher, and Byron C Wallace. Eraser: A benchmark to evaluate rationalized nlp models. ACL, 2019.
[16] Ann-Kathrin Dombrowski, Maximilian Alber, Christopher J Anders, Marcel Ackermann, Klaus-Robert Müller, and Pan Kessel. Explanations can be manipulated and geometry is to blame. NeurlPS, 2019.
[17] Ann-Kathrin Dombrowski, Christopher Anders, Klaus-Robee Müller, and Pan Kessel. Towards robust explanations for deep neural networks. Pattern Recognition, 2021.
[18] Ricardo Dominguez-Olmedo, Amir H Karimi, and Bernhard Schölkopf. On the adversarial robustness of causal algorithmic recourse. In /CML, 2022.
[19] Fliege, A F Vaz, and L N Vicente. Complexity of gradient descent for multiobjective optimization. Optimization Methods and Software, 2019.
[20] Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 2000.

---

[21] Jörg Fliege and A. Ismael F. Vaz. A method for constrained multiobjective optimization based on sqp techniques. SIAM Journal on Optimization, 2016.
[22] Peyman Gholami, Priyanka Roy, Mohana Kuppuswamy Parthasarathy, and Vasudevan Laksh- minarayanan. Octid: Optical coherence tomography image database. Computers & Electrical Engineering, 2020.
[23] Amirata Ghorbani. Abubakar Abid, and James Zou, Interpretation of neural networks is fragile. In AAAI, 2019.
[24] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim. Towards automatic concept- based explanations. NeurIPS, 2019.
[25] Bryce Goodman and Seth Flaxman. European union regulations on algorithmic decision- making and a "right to explanation". Al magazine, 2017.
[26] Gregory Goren, Oren Kurland, Moshe Tennenholtz, and Fiana Raiber. Ranking robustness under adversarial document manipulations. In SIGIR, 2018.
[27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[28] Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. NeurIPS, 2017.
[29] Juyeon Heo, Sunghwan Joo, and Taesup Moon. Fooling neural network interpretations via adversarial model manipulation. NeuriPS, 2019.
[30] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. TKDE, 2022.
[31] Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvári. Learning with strong adversary. ICLR, 2016.
[32] Adam Ivankay, Ivan Girardi, Chiara Marchiori, and Pascal Frossard. Far: A general framework for attributional robustness. BMVC, 2020.
[33] Kalervo Järvelin and Jaana Kekäläinen. Ir evalluation methods for retrieving highly relevant documents. In SIGIR, 2017
[34] Shuichi Katsumata and Akiko Takeda. Robust cost sensitive support vector machine. In AISTATS, 2015.
[35] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, et al. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (teav). In ICML, 2018.
[36] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[37] Maksim Lapin, Matthias Hein, and Bernt Schiele. Top-k multiclass svm. NeurlPS, 2015.
[38] Maksim Lapin, Matthias Hein, and Bernt Schiele. Loss functions for top-k error: Analysis and insights. In CVPR, 2016.
[39] Maksim Lapin, Matthias Hein, and Bernt Schicle. Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification. PAMI, 2017.
[40] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
[41] Tang Li, Fengchun Qiao, Mengmeng Ma, and Xi Peng. Are data-driven explanations robust against out-of-distribution data? In CVPR, 2023.
[42] Xiaodan Li, Jinfeng Li, Yuefeng Chen, Shaokai Ye, Yuan He, Shuhui Wang, Hang Su, and Hui Xue. Qair: Practical query-efficient black- attacks for image retrieval. In CVPR, 2021.
12

---

[43] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-coneave minimax problems. ICML, 2020.
[44] Ao Liu, Xiaoyu Chen, Sijia Liu, Lirong Xia, and Chuang Gan, Certifiably robust interpretation via rényi differential privacy. Artificial Intelligence, 2022.
[45] Yifei Liu, Chao Chen, Yazheng Liu, Xi Zhang, and Sihong Xie. Shapley values and meta- explanations for probabilistic graphical model inference. In CIKM, 2020.
[46] Yang Young Lu, Wenbo Guo, Xinyu Xing, and William Stafford Noble. Dance: Enhancing saliency maps using decoys. In ICML, 2021.
[47] Scott M Lundherg and Su-In Lee. A unified approach to interpreting model predictions. NewrIPS, 2017.
[48] Guixiang Ma, Nesreen K Ahmed, Theodore I. Willke, Dipanjan Sengupta, Michael W Cole, Nicholas B Turk-Browne, and Philip S Yu. Deep graph similarity learning for brain data analysis. In CIKM, 2019.
[49] Guixiang Ma, Lifang He, Bokai Cao, Jiawei Zhang, Philip S Yu, and Ann B Ragin. Multi-graph clustering based on interior-node topology with applications to brain networks. In ECML. PKDD, 2016.
[50] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. ICLR, 2017.
[51] Piyushi Manupriya, Tarun Ram Menta, Sakethanath N Jagarlapudi, and Vineeth N Balasub- ramanian. Improving attribution methods by learning submodular functions. In AISTATS, 2022.
[52] Seyed-Mohsen Moosavi-Dezfoolii Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In CVPR, 2019.
[53] Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 2014.
[54] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In FAceT, 2020.
[55] lan E Niclsen, Dimah Dera, Ghulam Rasool, Ravi Ramachandran, and Nidhal Carla Bouay- naya. Robust explainability: A tutorial on gradient-based attribution methods for deep neural networks. IEEE Signal Processing Magazine, 2022.
[56] Álvaro Parafita and Jordi Vitrià. Explaining visual models by causal attribution. In ICCVW, 2019.
[57] Remigijus Paulavičius and Julius Žilinskas. Analysis of different norms and corresponding lipschitz constants for global optimization. Technol. Econ. Dev, 2006.
[58] Judea Pearl. Theoretical impediments to machine learning with seven sparks from the causal revolution. WSDM, 2018
[59] Barak A Pearlmutter. Fast exact multiplication by the hessian. Nearal computation, 1994.
[60] Felix Petersen, Hilde Kuehne, Christian Borgelt, and Oliver Deussen. Differentiable top-k classification learning. In ICML, 2022.
[61] Vipin Pillai, Soroush Abbasi Koohpayegani, Ashley Ouligian, Dennis Fong, and Hamed Pirsiavash. Consistent explanations by contrastive learning. In CVPR, 2022.
[62] Pearl Pu and Li Chen. Trust building with explanation interfaces. In IUI, 2006.
[63] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Under- standing and mitigating the tradcoff between robustness and accuracy. ICML, 2020.
13

---

[64] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should trust you?" explaining the predictions of any classifier. In SIGKDD, 2016.
[65] Laura Rieger and Lars Kai Hansen. A simple defense against adversarial attacks on heatmap explanations. WHI, 2020.
[66] Jérôme Rony, Eric Granger, Marco Pedersoli, and Ismail Ben Ayed. Augmented lagrangian adversarial attacks. ICCV, 2020.
[67] Kevin Roth, Yannic Kilcher, and Thomas Hofmann. Adversarial training is a form of data- dependent operator norm regularization. NeurIPS, 2020.
[68] Cynthia Rudin. The P-Norm Push: A Simple Convex Ranking Algorithm That Concentrates at the Top of the List. JMLR, 2009.
[69] Thomas Saaty and Mujgan S Ozdemir. Why the magic number seven plus or minus two. Mathematical and computer modelling, 2003.
[70] Anindya Sarkar, Anirban Sarkar, and Vineeth N Balasubramanian. Enhanced regularizers for attributional robustness. In AAAI, 2021.
[71] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient- based localization. In ICCV, 2017.
[72] Sofia Serrano and Noah A Smith. Is attention interpretable? ACL, 2019.
[73] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In ICML, 2017.
[74] Mayank Singh, Nupur Kumari, Puneet Mangla, Abhishek Sinha, Vineeth N Balasubramanian, and Balaji Krishnamurthy. Attributional robustness training using alignment. In ECCV, 2020.
spatial
[75] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. arXiv preprint arXiv:1706.03888 2017.
[76] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for simplicity: The all convolutional net. ICLR workshop. 2015.
[77] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In ICML, 2017.
[78] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. ICLR, 2018
[79] Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao. Theoretical analysis of adversarial learning: A minimax approach. NeurIPS, 2019.
[80] Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. NeurlPS, 2021.
[81] Nicolas Usunier, Massih R Amini, and Patrick Gallinari. Generalization error bounds for classifiers trained with interdependent data. In NeurlPS, 2005.
[82] Minh Vu and My Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. NeurIPS, 2020.
[83] Fan Wang and Adams Wai-Kit Kin Kong. Exploiting the relationship between kendall's rank correlation and cosine similarity for attribution protection. NeurIPS, 2022.
[84] Fan Wang and Adams Wai-Kin Kong. A practical upper bound for the worst-case attribution deviations. CVPR, 2023.
14

---

[85] Hongjun Wang, Guangrun Wang, Ya Li, Dongyu Zhang, and Liang Lin. Transferable, control- lable, and inconspicuous adversarial attacks on person re-identification with deep mis-ranking. In CVPR, 2020.
[86] Lidan Wang, Paul N Bennett, and Kevyn Collins- Tollins-Thompson. Robust ranking models via risk-sensitive optimization. In SIGIR, 2012.
[87] Yisen Wang. Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. ICML, 2021.
[88] Zifan Wang, Haofan Wang, Shakul Ramkumar, Matt Fredrikson, Piotr Mardziel, and Anupam Datta. Smoothed geometry for robust attribution. NewrIPS, 2020.
[89] Tianjun Wei, Tommy WS Chow, Jianghong Ma, and Mingho Zhao. Expgen: Review-aware graph convolution network for explainable recommendation. Neural Nehworks, 2022.
[90] Yuxin Wen, Shuai Li, and Kui Jia. Towards understanding the regularization of adversarial robustness on neural networks. In ICML, 2020.
[91] Matthew Wicker, Juyeon Heo, Luca Costabello, and Adrian Weller. Robust explanation constraints for neural networks. ICLR, 2023.
[92] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. ICLR, 2020.
[93] Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K Jain. Adversarial attacks and defenses in images, graphs and text: A review. Int. Autom. Comput., 2020.
[94] Huan Xu, Constantine Caramanis, and Shie Mannor. Robustness and regularization of support vector machines. JMLR, 2009.
[95] Forest Yang and Sanmi Koyejo. On the consistency of top-k surrogate losses. In ICML, 2020.
[96] Yao-Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaudhuri. closer look at accuracy vs. robustness. NeurlPS, 2020.
[97] Yaoqing Yang, Rajiv Khanna, Yaodong Yu, Amir Gholami, Kurt Keutzer, Joseph E Gonzalez, Kannan Ramchandran, and Michael W Mahoney. Boundary thickness and robustness in learning models. NeurlPS, 2020.
[98] Jason Yosinski, Jeff Clune, Anh Nguyen, Thomas Fuchs, and Hod Lipson. Understanding neural networks through deep visualization. arXiv preprint arXiv:1506 106.0699, 2015.
[99] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, 2021.
[100] Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In ECCV, 2014.
[101] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML. 2019.
[102] Tong Zhang. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR, 2002.
[103] Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In CVPR, 2016.
[104] Mo Zhou, Zhenxing Niu, Le Wang, Qilin Zhang, and Gang Hua. Adversarial ranking attack and defense. In ECCV, 2020.
[105] Mo Zhou, Le Wang, Zhenxing Niu, Qilin Zhang, Yinghui Xu, Nanning Zheng, and Gang Hua. Practical relative order attack in deep ranking. In ICCV, 2021.
[106] Yun Zhou and W Bruce Croft. Ranking robustness: novel framework to predict query performance. In CIKM, 2006.
15

---

Appendix A provides theoretical proofs for the propositions and lemmas. Appendix B reports exper- imental settings and results. Appendix Shshows relevant works concerning explanation robustness, ranking robustness, and top-k intersection.
A Proofs
respectively, As the supplementary of Sec. 5 theoretical analyses on numerical and statistical robustness are A.4 A..4 and A.5 respectively.
Proof's concerning Prop. 4.4 4.5 and are in A.1 A.2 and A.3
A.1 Bounds of Ranking Explanation Thickness
A.1.1 Bounds of Pairwise Thickness
We denote x as the target sample, ||öl12 S as the perturbation, x' x 6 as the perturbed input, and x() (1 - 1)x Ix', I E [0, 1]. Here, I(x) is not specifically defined as (x)(x), but an arbitrary explanation method.
Proposition A.1. [Bounds of ranking explanation thickness] Given L-locally Lipschitz model fxx,, for some L 2 x-x"" ma.,ax Ln where x* = arg (Bxxx) explanation thickness for the fe) pair of target x is bounded by
((xx)I(xx'1] the ranking x
Ex [// i(x());,, s((xi,)) c* (I, + Iy).
((x, - 6 1 VxI,(x)122
where Hx(x) is the i-th column of Hessian matrix of f with respect to the input x, and Li = maxx)) V 12.
Lower bound.
Proof. We start from the definition of ranking thickness between (i, (i,j)-th features of in Eq.
h(x(t).i,j)dt
[,(x + 10) -Iş(x 18)dt
(x) t6 [vI(() I,(x) t5 VxI,(x)dt
(13)
-x, - (x + 8T
VxI(xx) 8T
2 VxI
2
2I(x) (x) - E ク V Ix (x)1
We approximate the gradient at intermediate point x + to by the Taylor Expansion on line-3. Then the minimum is found with 8* arg min 18T (V (x) (x)) -c - IV on line-5.
Vx
Upper bound. We introduce two lemmas from
88
before the proof.
Lemma A.2. If function f RR. - IR I.-locally Lipschitz within Bp(x, 6), such that [f(x)
f(x') < L|xx x'Ipp, Vx (x,xx fx': ||x x11p S {), then
== (x.,
||Vxx((x))
(14)
where y + = -,,15
Lemma A.3. function f(x) is L-locally Lipschitz continuous in B2(x, c), then I(x) is K K-locally Lipschitz as well, where K <
2L and x* = arg max (x.) [[xx I(x 2ll
16

---

Proof. Given an L-locally Lipschitz fxx). Lemma A.3 further indicates that [x(x) R" + R is
locally Lipschitz as well. By adopting p q on Lemma A.2 the Lipschitz constant is specified by I = (xx [ Iz [x 1|2. Formally,
[xx) - Ix(xx
[I(x) - I(x'Il2 & L.|[x x'12.
h(x(t),i.j)dt
-h(x6: i.
(x)( - Ix(x)) - (I)(Z)) - I,(x)) + (I(x) - (x))
(15)
<|I((x)) - -I((x] + +I,(
- -x)( + (I((x) - -I,(x)
SL,1116- - -x12 + 4,11x - x112 + (Ii(x) (xxx)
Sc* (L, + I,) + (I(x) (x)x)
Based on first mean value theorem, there exists x within the line segment x and x' such that Mxx: i, .o ix line-2. The Lipschitz constant L of satisfies L ||x-x"||
max; T4 xxxx"] II max; (xx (x)((x))
A.1.2 Instantiation
Notice that the inequality in Eq. 13) holds for arbitrary explanation methods. Here, we consider different explanation methods (Grad, Gradx Inp. SG, and IG) to specify T(x) and corresponding bounds. We leave DeepLIFT (73) and LRP [6 to further study, and we do not consider Grad-CAi
7 and Guided Backpropagation (76 since they are designed only for specific networks.
Grad. When adopting Grad as explanation method, where I(x) = Vf(x) and VxI(x) = H(),,
recovers Prop. 4.4
( () (16)
where H(x) is the Hessian matrix, and specifically I maxx'eB,(x.)) (x'('') ||22
SmoothGrad. When adopting SmoothGrad, where I(x) = M E,. vf(x + 3m) and 8m NO0 we have VxI(x)= मे Em H + Pm). We derive the lower bounds analogy to the derivations on Eq. [3)
J h(x(f),
1
Σ /
(Vf(x +6 Brn)s; - (Vf(x + + + ;mi))
M m
(17)
1
Σ (Vf(())): - (VI(x)); -c* +H,((x) H2(x))12 + (H((() -H((x))
2 M
m
1 =(Vs(x)); (Vʃ(x)), - 1 + +1111((x) Hx)2)112 M
-
Bro)" Bn,) (H,(x) H,(()))
Note: when M is large enough, 1 Σm 3m - since 3m is drawn from from.N((.. (0, 02
17

---

Grad Inp. When adopting Grad X Inp. where I(x)
V diag(( V ................................ (Vf)). + (x). The lower bounds derived from Eq. (3 can be further specified:
① X, we have VxI(x) =
[x() - (x) 2
[V Vx2,(x)1
=I,(x) - [x) e
[1 - (2(() + lo.....
0]
2I(x) [x) 2
(1 H2(x)]12 [1 ...,,,,,11......... (V))...., -1)
-I((x (x) c* 1
1
2V +V
+ (V/))
Hxixx) H2(x)]la
(18)
2
2(V - (V/(x)) - (V((x)), - (VS(x)); - 1
2 -11,,((x) - (x(x)]22
2
=(VI(x)), [1 - ;) (V/(x)), (1) ;)
[H:(()) - H2(x)]l2
(VV(())) (V - " H1((x) (x)()
Note: is the i-th feature of the input and < since the perturbation is supposed to be neglectable.
Integrated Grad. When adopting Integrated Grad, I(x) (x- x Sa ff + +a(x - )a)
By setting x" O, we have I(x) x x Sazo V Vf(a))da. Similar to the Grad Inp case, the lower bound of IG can be derived:
[(x)= [x(
VxIi(x) (x)]
2 (V[(ax)) - -V (V/((VV/())))))))) e * _ [1xx)xx)= - Hyxxx))l2dd
(19)
2 (VF(())) - (V[(x)))a -c [H( Hx)()
A.1.3 Generalization to Top-k Thickness
Since the inequalities in Eq. Thus.
13 and
15 hold for any choice of x' E B2(xx e) with specific e.
VxI, 1a s Ex [// h(x(t), j)dt < <h(xi,,)) + +e* (L, + Lÿ).
h(x, i, - V -
Furthermore, the bounds of the top-k ranking thickness hold for any choice of comparison pairs:
Σ (xx(,)) - c* 6
( IV (xI(()) s Ex
Σ S. 1.j
h(x(O),,))dt
S
Σ
[M + (I, + Ig))
1
(20)
Instantiation for the top-k thickness be derived similarly to those in A.1.2
A.2
Connection between R2ET and Certified Robustness
Mx...) Proposition A.4. For all 8 with ||ö||2 S min(s..) maxy [[( 21 it holds 1[, i.j) 0] 1/((xx + (, for all (i.j) pair, that is all the feature rankings do not change.
Proof. The proof is adapted from the work (28 We consider the minimal budget required to achieve h(x + 5, i, < 0, e.g., [x 5) - [x + 8) < O, given ((x,i,5) > 0. The same proof can be done for i, < O. Based on the calculus, it holds that
+(x+ Ixx)+ J (H+(x 18),
+ = 5)x+ + f." (H + 15), 6)
18

---

To achieve [(x+0) - -x (5x+00) +0 <0,
[((x] + / (H,(x + 11), 57dt) (3(00+ + J (H,(x+ 16), 16), <0 0,
which implies that
- < <f (H5(x+15),)) 1 (Hi(x 18),6)dd
Based on the Hölder's inequality,
[(x) - Ix(x) < |61| / [ + t6) - H + t5) 12dt,
Thus, the minimal budget required to flip the ranking between the feature pair (i,
[x) [x(x)
|| >
So [H + 16) H, + 16)lladl
[x(x) I, [x)
maxx'eB,(x'.s) [x()') Hy (x')ll2
Thus, the minimal budget required to flip any ranking is min max [x(x'))
M(x..))
A.3 Connection between AT and R2ET
Following Sec. given a model f R" - [0, 1]c and an input I(x, c; (xfe(x) is the explanation and (x) the score for the i-th feature. We assume that T(x) is sorted and top-k ones are salient features. The proof is based on the prior work (94).
The objective of Adversarial Training (AT) for training model by min-max game in Sec. 4.2
min
Cete
1(x + 8.g,
(21)
JEM
11==+1
We explicitly show the weight of each I, which is 1 = (n k) if S k, and 4 = -k, otherwise, and rewrite AT's goal:
min max W (G.......JJMM
Cole Σ
4I, 6z).
(22)
im1
or
min (.)....8))MMM
4I, + 6:), Lole +
(23)
1=1
where 6 specific to the i-th feature input x.
We will prove the equivalence between R2ET in Eq.
(6)
and AT in Eq. (1 by proving that
min 6.......JJMM 1=1
Σ
4I,(x + 5t)
(24)
equivalent to
(x) emax 4: [anaxx||HHei (1)
(25)
1=1
R" ||0|| S. E), we consider a perturbation set M where perturbations on each feature are independent, but the aggregation of perturbations is controlled. Formally, M satisfies M CMC where
Proof. Given an norm ball My = {6 E
M - U where M, {(6),...,,,,666 MM; 0 = -};
M+ del ((a16),..., a Σ ai = 1; 2 0, E Ma, io..i=......... I.....n..
1=1
19

---

M CMCM M naturally implies that
min (
4T((x + 6.) s
min (fI.....JeMM
1 + 6:) v
min (3 JEM
4Tx(x + 8.).
1=1
(26)
We will prove that v is not smaller than the rightmost term and not larger than the leftmost term in Eq. (26).
To prove v 2 (i.. Ei=1 4Ix(x + 8:).
n 11,, +6) 6,) i=1
min (61...,6)EM
min
4I, + 8.)
i=1
(x]x(x) +
min
(x1((x) da
(6 (.MM
4I,(x)
min
min
(x)x(x) 8c
(E(L......) MEMo
Σ (x,(x)
max LE te
(e]He(
The inequality on line-2 holds since Mj M- The equality on line-4 holds due to the definition of M,, where only one 6 of (.(x)
8p) is from Ma and the rest are all zeros. The equality on
line-5 holds by picking 8, = - [x,[x
To prove S min JJMM El (xx
min ( (f a=1
Σ (x
Σ 4arTI(x 8.)
min
_, s=1
n
4I(xx) + min Σ, 2:
ag min 1,, T5: M.
4I((x) + min min (HH(()) (x) Toc 1E(L....)) M.EMo
4Ix(x) - max (1)H1,(x)l1..
(E(1.....)
A.4 A multi-objective attacking algorithm and its analysis
We present an algorithm that will terminate finite iterations, and flip the first pair of salient and non-salient features, or claim failed attack. The algorithm is based trust-region method designed for single non-convex but smooth objective with nonlinear and non-convex equality constraints (9]
Let the output vector fxx)= (x)
Given features and top-k salient features, there are m = x (n 1)) objectives that can be indexed by subscripts & so that the objective vector becomes [h1 (x)....... .... hx))). ... Am (x)). Let ||I| be convex norm with Lipschitz constant 1.
20

---

Algorithm 2 Attacking a pair of features
Input:
initial input target model f. current explanation I(x), tolerance 0, trust-region method parameters
v > and q O.
Set h = 1, x()) x, 1 = fl (P) || + hz(x(o)) - e(P) for each objective he-
while min (x (()) 2 do
Solve TR-MO0(x(2) (p) A (P)) to obtain joint descent direction (P)) for all linearized merit functions Lo,,
(p) = (e(x(() ((0) (x(() 4a(0), ,(0)) for each = 1,..., m. (x(() ./7 00) 0011/ (x(()) ,(m))
PE
if min; Pi. > 1 then
(p)
x(++1) x(1) d())
A(+11 A (p)
if (e(x(e)) 2 then
(lpt1) 1f
(p)
- x((x1)) ((2)) + de(x(xt1)) (lo)).
else
t ( 2he 2 {(r) - 61(x(1), (1()) + (x(xx()1)) )
end if
else
x(++1) x(1).
A (o+1) = An)
((ot1) (1 for l ,,..., m.
end if' end while
Since are working with numerical algorithms, approximately feasible set will be appropriate. Define the following constrained MOO problem
min x
(x), ..... ,x(x),...........),,,,,..)). ... hmm [x)))]]
(27)
s.t. [lf(x) f(x [(x(0))] S cf.
||x (0) ||2 S Ex.
In the sequel, the two constraints can be combined such that
[lf(x) f(x( Sc
(28)
x]. Therefore, let f denote f to simplify the notation. Define for some O, with f(x) [f(x), the domain
Ci def {x: ll((x) f(x(")) c).
(29)
Assumption A.1: The constraint function fxx is continuously differentiable on the domain TR.,, and the objective functions he, i 1,..., m, continuously differentiable in the set
C₂ c 1(0, ()),
(30)
where 8 >> is a constant, A (1) is the initial radius argument for the trust-region method for multi- objective optimization TR-MOO(x, A) be defined below, and B(0,, (2) is an open ball centered radius 8A (1),
Assumption A.2:
The objective functions heg é= 1....., m are bounded in the set C₁. Specifically,
Now min min h (x)..... min fm (x)),
(31)
def hmp max max hi (x), max hmm (x)).
(32)
We give attacking algorithm MOO-attack that can either find the first feature pair to flip in an explanation, or claim that is impossible to flip any feature pair. The superscript (p), p = 1, 2,..... indicates the number of iterations.
21

---

The attacking algorithm may not be able to flip any pair of features when minisegm Xe(x(e), (e()) < but there can be other objective functions that still have Xe(x(1), (()) 2 and there is chance to flip the corresponding pairs of features. We will remove any objective function he with Xe(x(<), ) < c and return to the while loop to try to flip other pairs of features. If all objective functions are removed at the end, the attacker fails to attack the explanation.
We adapt the theoretical results from [ the above multi-objective optimization algorithm to show a global convergence rate for the attacker.
Lemma A.S. Suppose that assumption A.I holds. If x(()) E C1, then for each linearized merit function tor
(p) (xc(x(1) ((()) 0)) - love (x(1)) 12 (d)) (Ai) 1)xe(x(()) ((P)).
(33)
Lemma A.S shows sufficient descent in the linearized merit functions in the direction d The proof can be found in Lemma 2.1 in [9].
Lemma A.6. Suppose that assumption A.I holds. In each iteration for k 2 1 in Algorithm 7 the following properties hold:
he(x(!)) - +(0) -tp > 0, = 0,,=11..... 1....,m. m,
(34)
@ (14)= =E, 6=== =l,...,m. m,
(35)
Ihe(x(1)) (6/01 S &e, = -1...,, 1f(x(1)) S.
(36)
(37)
Lemma sh6 that from iteration to iteration during the loop in Algorithm]] 1 the invariants will be maintained. The proof can be obtained by applying Lemma 2.2 in 9 to each of the objective functions independently.
The last inequality indicates that during the attack, the manipulated input x(() remains in the approximate feasible set C1 and that the prediction by f is not changed. This is important to make the attack stealthy. The second last inequality shows that each objective he will chase the corresponding
target {(P)) over the iterations, so that if (p) can be shown to be decreasing sufficiently fast, we can
show the convergence hg, Note that different targets (!)) will move at different speeds, as they are updated independently in the algorithm. Also, target is not guaranteed to be reduced below zero for
hy to become negative and the f-th pair of features will flipped.
Lemma A.7. Suppose that assumptions A. and A.2 hold. Then with min; (x(x()), ((6)) 2 and
(1 - n)
(p) < min
(38)
Lgs L2
the condition ming Pe > n in Algorithmn will hold true and A (p+1) AA)), Furthermore, with
mine Xe (x(x(1), {(o) 2 e, we have, for all p 2 1,
(Aa) min (1 - --y
A (p) min
(39)
T.ge + 1/2 [.
Lemma A.7 shows that when the radius (P) used in TR-MO0(x("), (P)) is small enough, the radius won't 't be further reduced. Together with Lemma/A.5 the linearized merit functions are reduced sufficiently per iteration. The proof is modification to the proof of Lemma 3.2 in [9] with the derivation done for each of the objective functions h4 to guarantee sufficient descent in all merit functions. An interesting observation is that the search radius A (P) is restricted by the objective that has the most rapid change in its gradient gæ (characterized by Lg.). If all objectives are smooth (with small Lg,) ), the search radius can be larger and the reduction in the merit functions is larger. The second inequality of the above lemma says that the search radius will have a lower bound across all iterations.
Lemma A.8. There are at most (og( number of times that A (x) will be reduced by the factor of 7.
22

---

Lemma A.8 characterizes the times to reduce the search radius. It is because, starting from A once iteration p. there will be 1oge + 2
A falls below ming (1-1)e
reduction in future iterations.
Lemma A.9. Suppose that assumptions A.1 and A.2 hold. Whenever x(9) is updated in Algorithm for each functionn he, both the reductions de (x(x()), +(() are least
,te -)) ()))((xx(),, (!p) (())) and t b
min AA (1)
min (1-1) 7) 2217 Lge + //3
(40)
Lemma A.9 shows sufficient reduction in the merit functions and the targets. The proof is to use the condition that Pe > 1) for all & 1, 1....,,,... m, Eq. (33). the condition that minigesm (e(x((), t())) z
and Eq.
39
Lastly, present the main global convergence results.
Theorem A.10. Suppose assumptions A. A.1-A.2 hold. Then Algorithm generates an e-firstoonter critical point for problem Eq. (27) in al most
(hou hlww
(41)
iterations of the while loop in the algorithm, where is a constant independent of but depending on 7i T,, Lig and L..
The proof hinge on the following inequality
Now
I (e((x(1))
(42)
$ t( +e
(43)
< 1/ iptize +e
(44)
< he ipRize +
(45)
< hup ip,ize? +
(46)
where in is the number of iterations between and p where mine Pi (0')
> 1,, 1 S p S p/, is true.
K2 min A1(), min (1 - n)y
77
(47)
L.g I
Therefore,
ip < hup
Rlow +
(48)
R
Since I[[[))())) grows slower than 1/e², the overall number of iterations is in the order of (hup
Now)
22
A.5 Statistical robustness
We will tools for generalization error analysis on any single input x to prove that with a high probability, the empirical error of ranking salient features of x for a fixed model f is not too far away from the true error of ranking the same set of salient features, with respect random sampling of from an arbitrary distribution D on a support set around x where the salient features are preserved.
Roadmap: We first adopt the McDairmid's inequality for dependent variables to show concentration incquality for ranking errors fixed feature ranking function based on the salient score function Σ(x). Then will adopt the standard covering number argument in (2] 68 prove uniform convergence that depends on the margin in the empirical ranking loss, therefore justifying the maximization of the gap/thickness between the scores of salient and non-salient features in R2ET.
Basic definitions. Given I and x, define the true and empirical 0-1 risks
Raye (I, x)
(x('') < <I,(x')
(49)
23

---

A 1 (I, x)
1 (x) (x)].
(50)
m
To relate the risks to the thickness, consider the loss @u (z), v > 0, which is similar to the hinge loss
2 < 0,
(2)
1 - 2/u
0 - 2 < u,
(51)
0
2 2
Based on Φu. we define the surrogate true and empirical risks
Du (x(I((x)) -2(())
1e (I, x) = Ex
(52)
i=
k m
[I, x)
Sn (I(() - Ix()))
(53)
Lastly, an upper bound of (=) can be defined as a large-margin 0-1 loss: if 2 u. the loss is 0, and
otherwise, the loss is 1. The corresponding empirical risk Ho (I, 1 Σ E [I < (x(x) + u| counts how many pairs of salient and non-salient features that the salient feature is less salient than the non-salient feature according to I.
Generalization bound of Re (I, for specific I. As we randomly sample x' from D, the terms (x'x) and the associated 0-1 and du losses. The typical McDiarmid's inequality bounds the probability of a function of multiple independent random variables from the expectation of the function. The elements in &o. not independent. The saliency scores of different features dependent since they function of the same model f. the input x, and the mechanism that calculate the gradients for I. In [8]] the authors generalized the inequality to dependent variables, and we adopt their conclusion follows:
Lemma A.11. Given prediction model f, saliency map I, input x, distribution D surrounding x, surrogate loss Qu and a constant e O, we have
(- 2mmc²
Pre
{ RR
(I.x)
R (I, + c < 2 exp
(54)
X
where X is the chromatic number of the dependency graph of the pairs of random variables (I,,I) for any i S k and k 1 S S n.
Comments:
The above dependency graph describes when two pairs of random variables (I, (regarded as a random vector) and (Iv I,,) (regarded another random vector) are dependent. In particular, the two nodes (Z, TT) and (Ir, I are linked if they are dependent. This graph depends on I, x, and 'D and is in general unknown.
The chromatic number of the dependency graph is upper- bounded by plus the maximum degree of nodes on the dependency graph, which 1+m. In the worst case, the bounds Eq. (54) approximates 2 exp( (2.2) as becomes sufficiently large.
Uniform convergence of the class saliency score functions. Since R2ET searches the optimal I function from a class F of such functions given f. I, x, and D, u > O, with the preference over I that has large gap u so that (x) I, (x) + u for salient feature and non-salient feature j.
Theorem A.12. Given prediction model f, input surrogate loss &ne and constant > 0, for arbitrury saliency map I and any distribution D surrounding x that preserves the salient features in x, we have
2m
exp where N(F, E1) is the covering number of the functional space FF with radius 1102/.
PIx [ (I,
(T, S 22N $
(55)
24

---

Comments:
The proof is standard and similar proof can be found in [68]
With larger > O, the empirical risk R. (Z, x) will increase as more pairs of salient and non-salient features will not have their saliency score larger than this gap. On the other hand, the
covering number M(F eu will decrease as u increases larger radius can cover more F. This represents a model selection problem.
Last but not least important, with a larger gap u that R2ET can optimize I, with a random perturbation of to x' that has the same saliency features, the true risk (representing how bad the true explanations can be perturbed) will be low.
B Details of Experiments
We provide detailed experimental settings in B.I and comprehensive results B.2 Specifically, correlation exploration (B.2. case study (B.2.2). constrained optimizations (B.2.3). ablation studies (B.25), accuracy and explanation robustness trade-off (B.2.4), more explanation methods (??), and faithfulness evaluations (.2.6).
B.1
Experimental Settings
B.1.1 Datasets and Target Model Structure
Tabular data. Three tabular datasets are included: Adult, Bank [53] and COMPAS [54]. We divide each tabular dataset into training. validation, and test portions at ratio of 70 15 15, respectively. follow [I] to binarize and map the original inputs mixing with strings and numbers 28-dim, 18-dim, and 16-dim feature spaces, respectively.
we adopt an SN, where the embedding model is classic CNN, consisting of two convolutional layers with 3*3 kernels followed by max-pon pao-lini and three fully-connected layers. Then We use cosine similarity as the similarity metric, and classifier is single-layer linear model taking the outputs from the embedding models as inputs. To construct pairing samples, we randomly sample 2400 pairs of images with digits 3 and 8 from training images as the training set, and 300 and 600 pairs from test images as the validation and test sets, respectively.
Image data. We adopt ResNet18 (27) for CIFAR-10 10 [6). As for MNIST 40
Graph data. We apply SNs to two graph datasets, BP 48 and ADHD 49), where each brain network comprises 82 and 116 nodes, respectively. We pair any two training graphs as the training set. To simulate real medical diagnosis (by comparing new sample with those in the database), each validation (testing) pair consists of a training graph and validation (test) graph. The embedding model consists of a two-layer GCN, where the first layer maps inputs to a 256-dimension hidden space following ReLU, and then maps 128-dimension embedding space. Then it adopts a mean pooling to aggregate node features to graph-level one. The cosine similarity is used to measure the similarity between two embeddings. The classifier is single-layer linear model taking the outputs from the corresponding embedding models as inputs.
B.1.2 Methodology of Training Target Models
We train all the models from scratch, except that ResNet retrained from the Vanilla model. The model with relatively high cAUC and the highest P@ k on the validation set will be adopted as the outstanding model for further evaluation. Specifically, We choose the last model with cAUC higher than threshold on the validation set. Then the outstanding model is the one with the highest P@k out of these high CAUC models on the validation set.
Details of training by R2ET. While incorporating a priori information could enhance R2ET's performance, we do not furnish the model with such information to ensure fair comparison among training methods. 1) Training from scratch: The model incrementally develops an understanding of feature importance. At the /-th training iteration, aims to preserve the feature ranking from the (1-1) iteration. This iterative refinement stabilizes the model's perception of feature importance without any predefined ranking knowledge. 2) Training from a Vanilla Model: We leverage the established model's feature ranking as a baseline. Given that the vanilla model has achieved
25

---

Values
Description
Tabular
MNIST
CIFAR-I0
Graphs
base model architecture" hidden dimension number of features k' for R2ET-mm maximal training epochs
2- l-yyerr MLP
SN with CNN
ResNet
SN with 2-layer GCN
32
3 kernel
[27
256
100
100
50
100
300
100
10 (retrain)
10
learning rate carly stopping
10-4
10-3
10
10
N/A
N/A
N/A
maximal attack iteration
1000
100
100
100
perturbation per iteration
10-3
10
5 10
10
k for Est-1I for SP weight-decay for WD
(10 6 10
10 10-
[0.5. 1,5, 10, 100)
(5 10 5 10 5x 10 10 1002,00.20000 10
À for single regularization methods
{0.01, 1,1, 1, 10, 1003
Table 4: (Hyper)-parameters used in experiments. "SN" means Siamese Networks for dual input.
satisfactory performance (AUC), its explanation ranking is reliable reference. The goal of R2ET is to maintain this inherited feature ranking during retraining.
Selections of hyperparamters and parameters. Table 4 shows the default adopted in the experiments. Attacks are conducted a PGD-style [50), and the infinity norm of the perturbations in each iteration is restricted A and A are selected as the same as the best À for R2FT, и and est-H, respectively. Alternatively, we simply set A = Ag = A, and À can drawn from {0.01, 0.1, 1,5, 5, 10, 100).
more than 5 for images and 0.2 for graphs. For R2ET,
When adopting SmoothGrad (SG) 75) as explanation method, where Isg(x) = M Σ I(x + 3m) and Bm ~ (O, T2 M is set 50 for all datasets, and x² = 0.5, 25.52 0.01 for tabular, images, and graphs, respectively. When adopting Integrated Gradients (IG) (77]. where (x)(x) (x x²) O
I vx + a(x da. In practice, we set x = 0, and approximate the integration by interpolating 100 samples between x" and x.
Running environment. We mainly conduct experiments for three tabular data and CIFAR-10 on the following two machines. Both come with 16-core Intel Xeon processor and four TITAN GPUs. One installs 16.04.3 Ubuntu with 3.8.8 Python and 1.7.1 PyTorch, and the other installs 18.04.6 Ubuntu with 3.7.6 Python and 1.8.1 PyTorch. The MNIST and graph datasets are run on a machine with two 10-core Intel Xcon processors and five GeForee RTX 2080 Ti GPUs, which installs 18.04.3 Ubuntu with 3.9.5 Python and 1.9.1 Py Torch.
B.1.3 Saliency Maps of Target Models
We use the absolute gradient values as the explanation for tabular datasets. For MNIST, we use the normalized absolute gradient values as the explanations. For CIFAR-10, the sum of the absolute gradient values is used as the explanation. For graph data, we use element-wise multiplication of the gradient and the input as the explanation 1..
B.1.4 Evaluation Metries
We adopt precision @ k to evaluate the explanation robustness by quantifying the similarity between I(x) and Z(x'): AUCs and sensitivity evaluate the model's classification performance (see B.2.3 and B B.2.4): and DFFOT, COMP, and SUFF to evaluate the explanation faithfulness (see B.2.6
jaithfuto
Precision @k (P@k) It is widely used evaluate the robustness of explanations
23 Formally,
P@I(I(x),I(x)) [[() n I(x' )pn]
k
where [(x) is the set of the i most important features of the explanation I(x). |.| counts the number of elements.
26

---

Clean AUC (cAUC) and adversarial AUC (aAUC), Besides robust explanations, the model needs robust predictions. Thus, we adopt cAUC and aAUC to measure the model's 's classification performance before and after the attack, respectively.
Sensitivity (Sen). Since attacks can be detected by checking the consistency of predictions 93 Sen measures the ratio at which classification results change after an attack for models.
Decision Flip- Fraction of Tokens (DFFOT) [72 measures the minimum fraction of important features to be removed to flip the prediction. A lower DFFOT indicates more faithful explanation.
k
DFFOT min n
s.t. arg fa(x) arg max fc(X((v))
where the number of features, and [Vv] the perturbed input whose top-k important features are removed.
Comprehensiveness (COMP) [5| measures the changes of predictions before and after removing the most important features. A higher COMP means more faithful explanation.
COMP-
[f(())
fa(xpva))
|
KE
where K' is {l...., n for tabular data, and {1% n., 5% 10% n,, 20% * n, 50% n3 for images and graphs. The same setting of K is adopted for SUFF.
Sufficiency (SUFF) [TS] measures the change of predictions if only the important tokens are preserved. lower SUFF means a more faithful explanation.
SUFF
Σ
[fa(x) fa(x)))
|
AEK
where X|j is the perturbed input with only top-k important features.
B.1.5 Introduction to Siamese Network
An SN predicts whether two samples, x* and x', are from the same class. The SN uses a network to embed each input, respectively, and measures their similarity by a similarity function. The prediction for class 1 (two samples from the same class), Pr(y = 1[x", "1xx,x)) x"),
(56) and ASN = SN for class sim(-. w1) ) similarity function, such as the cosine similarity. and emb(;; wo) is an embedding network, such as GNN. w (Wo. wi) is the SN's parameter set. The ground truth used in SN is yd = 1ly" = y²), where y" is the label of x
JISN(x (x", x'; w) sim(emb( wo). emb(x"; wo); W1),
To predict a single input, one can further train a classifier fCL based on the embedding part of the SN. For example, fC2(x) cls(emb(x; w(); w2). where w/ can be the same as retrained from Wo in Eq. (5). and cls(;; w2) is classifier such as a linear model with the parameter set W2.
B.2
Additional Experimental Results
B.2.1
Settings for Correlation Experiments and More Results
We explore the correlation between the manipulation epochs, thickness, and Hessian norm concerning different models on various datasets. Specifically, as shown in Fig. 4 we consider different datasets and methods, such as Vanilla, est-H, and R2ET. Since images and graphs have more features than the three tabular datasets, almost all adversarial samples will swap feature pairs under the first epoch of attack. Alternatively, we set the manipulation epoch metric for graph and image datasets to record the first epoch where P@ k drops below 0.8. We do not plot the results on Bank, where R2ET achieves 100% P@k. Fig. presents the correlations between manipulation epochs and the other four metrics. Besides thickness measured by adversarial samples and Hessian norm as used in Sec. 6.3 we additionally show the thickness measured by either the average minimal of few Gaussian samples to mimic random noise [066. Although the thickness evaluated by Gaussian distribution is not specific to adversarial attacks, the corresponding correlations are much higher than between the manipulation epoch and Hessian norm.
The dataset-level thickness is defined as the average thickness over all the samples. Table 5 reports P@ & and dataset-level thickness. Clearly, the models with high P@k performance usually have relatively large thickness well, and vice versa.
27

---

2000
1000
1000
1000
800
800
600
Correlation: 0.84
Corretation-0..o
Correlation: 0.61
600
Correlation: 0.71
400
200
0.52
3.94
036
0.30
1.00
0.52
6.9
0.56
6.91
Housian
Th vinnes (mean of Raussien)
Thickness (min Caussien)
1000
1000
1000
100n
800
800
0.77
600
Coreladion
600-
Correlation: 0.62
600
Correlation: 0.69
400
400-
400-
4GB
200
200
200
0:37
Thiconesa
Gaussian)
1000
1000
1000
1000
000
800
Correlation: 0.94
Correlation: 0.76
600-
Correlation: D B8
200
Com ation: 0.42
200
200
Thecnnes
0.0
0.2
Hossian norm
0.4
0.6
0.8
1.0
0.5825858
Gausstan)
1000
1000
1000
800
800
800
800. Correlation: 0.89
600
600
Correlation:
600
Correlation: 0.58
lyrve
400
400
400
400
200
200
Correl attin: 0.06
200
200
0.90
0.2 D.T 0.96
0.D 0.2 0.4 G
1.4
0.56
Thicamess
deness Gaursion)
Thickness Gaurstan)
1000
100
100
80
80
60
60
Correlation: 0.04
60-
Correlation:
Correlation: 0.33
40-
40
40
40
20-
20
20
20
DV
0.52
0.0
0.5
1.0
1.5
2.0
0.933
540
950
370 980
Trickesss
Hessian norm
Thickness (mean Caussian)
1.00
160
80
Correlation: 0.64
60
Correlation:
40
40
40
49-
20
20
0.0 1015 20 3.5
0.90
6.2
034
0.96
0.98
1.50
520.5400 32.0040.560..5 060.88100
ThicknIss
Hessian norm
(mean Gaussian)
Thickness Caussin)
1.00
100
100
100
7,7
Iniitttt 344
80
60
Correlation: 0.50
Correlation: 0.13
Correlation: 0.11
Correlafi attina 0.15
5.85
10 Hessian noom
0.829 8783599088 95055507000000 Thickness Gaussiani
8.528.850 950000 925 550 973.000
Figure 4: We show the correlation between the manipulation epoch and other metrics, including thickness evaluated by adversarial samples, Hessian norm, and thickness evaluated by (mean and min of) Gaussian samples for different models various datasets. From top to bottom: Vanilla. est-H models on Adult, respectively. R2ET models on Adult, COMPAS, MNIST, ADHD, and BP, respectively.
28

---

Table 5: P@k (shown in percentage) of different robust models (rows) under ERAttack and the values of dataset-level thickness.
Method
Adult
Bank
COMPAS
MNIST
ADHD
BP
Vanilla
87.6 / 0.9889
33.0/0.9692
84.2 009533
59.0/0.7725
45.5
69.4 / 009222
WD
91.7 0.9960
0.94/0
87.7 0.9769
/9.1
47.6/0.9343
69.4 / 0.9298
SP
97.4/ 0.9983
99.5/ 9.9970
62.9/0.9771
0.9316
68.7 / 0.9300
Est-H
87.1 0,9875
7.9483
8..6/
8 -/-
5 18.2/0.950 0,9578 -/-
75.0 / 0,9356
Exact-H
89.6/ 0,9932
81.9 1../0..95 0.9521
77.2/099383
-/-
SSR
91.2/ 0.9934
76.3 06.3/0.90 0,9370
82.1 / 0.9549
-/-
-1-
AT
68.4/ 0.9372
80.0 0.9473
84.2 0.9168
59.4/0.9597
72.0/ 0.9342
R2ET
97.5 0.9989
100.0 1.0000
9
82.8 / 0.9949
7 60.588
R2ET-mm;.
93.5 0.9963
95.8/ 0.9874
95.3 0.9906
81.6 0.9942
/
72.4 15.4/035 0.9342
R2ET
92.1 0.9970
80.4 0.9334
92.0/ 0.9865
85.7 0.9949
71.6 0.9731
71.5 / 0.929
R2ET-mm
87.8 0.9943
75.1 0.9102
82.1 0.9544
85.3 0.9948
58.8 0.9588
73.8 / 0.9356
B.2.2
More Results for Case Study
Fig. 5 shows the saliency maps for case studies concerning all the baselines and R2ETs.
B.2.3 Constrained Optimization for Attacks
We show the general form of adversarial attacks by constrained optimization framework for explanations in Sec. 3 Since defenders can catch adversarial attacks if there are any changes in predictions, the attackers must keep all S predictions unchanged during the attacks, where S for SNs and S = 1 for DNNs. We denote the primary objective in Eq. ( manipulating the explanations as Go. and constraints for small prediction changes (measured by KL--divergence) as Is. < I S. Naturally, we construct Lagrangian function with the non-negative multiplier = [Yo. 71 7s] E S+1.
((x,7) = (x) (x+++ + (x).
(57)
Some previous works manually set y a hyperparameter by experience [16., dismissing the relatives among 9a. Instead, we care about the unsatisfied constraints with higher weights by uplifting 7 with
larger ga. Thus, we adopt the following methods to update both primal variables and dual variables
66 11:
Gradient descent ascent (GDA) solves the nonconvex-concave minimax problems 43 by
x - x
ac The
Ox
ac + + 17, 8yy
(58)
where and 77, are the learning rates. Notice that (C(x.))
9 Vs E (1...., S}. and 7o is
07.
passively updated by the normalization Σ = 1 at the end of each iteration.
Hedge is an incarnation of Multiplicative Weights algorithm that updates y using exponential factors In each iteration, we normalize 7 such that E9 = 7/ = 1, and then update by
7 f- ② "ttgee (ooeedtooooo-910. 91....999)
(59)
where MHddge is the learning rate, c is the dementtwwse multiplication, and exp is exponential operation.
Another way to update weights y is to solve quadratic programming (QP) problem
S
max
1/ (x)1
s.t.
Σ
7s 7. 2 Vs E
=1
S). (o....,S).
(60)
0=0
8=0
We also include unconstrained attack without any constraints, and no update that fixes the weights
to 7 8+1 1.
29

---

Vanilla
WD
SP
Est-H
Origina
000ic42..0% 200%
Pgtt-4.00m
Piak 56 0%
Pigk 68, 0%
PG 0%
Piak-52.08 52.0%
8g.-86.0%
Pii--8800 53.0%
Peturiel
R2ET
R2ET-mma
R2ET
R2ET
Osiginel
Pgkk-880% 0%
Pgk--4.0%
90.0%
9gkk-22.0%
Pg 94.0%
88.008805
96.0-96.0%
94.0%
Pettrbed
Vanilla
WD
Est-H
Ohiginal
Pigk-76.0% 0%
Pgk-68.00
P
Pik--0000
18kk-86.0% 0%
P-K-74.00 74.0%
Pgk-84.0%
PgkK-94 94.09
Patubbed
R2ET
R2ET-mma
R2ET
R2ET-mm
Ohieginal
Pg
PGKK
P@
Pattubed
Figure 5: Saliency maps concerning the original image pair and the image pair perturbed under ERAttack for methods. The red pixels are the top 50 important features in saliency maps, with darker colors meaning more important.
30

---

Scatter plots in Fig. 6 show different constrained attack methods in terms of P@k and sensitivity. The attacker looks for lower sensitivity and P@k: lower sensitivity means that the constraints are better satisfied, and lower P@k means that more top-k: important features in the explanation are distorted. The asterisks highlight the attack methods having the smallest P@ and no more than 2% sensitivity. These attack methods are used to evaluate the defense strategies in Table [ We do not use constrained attacks on three tabular datasets and MNIST because their sensitivity is 0%. Besides, Table 6 shows that the difference between CAUC and aAUC for all methods is no more than 0.01, indicating the success of the selected constrained attack to retain the predictions.
Performance ERAttack under different constraint int attacks on BP dataset
Performance attacks under different constraint attacks on BP dalaset
0.50
0448
GAe
Sensitivity
Sensitivityy
042
0400
0.99
0413
0000
8009
5.900
9082
5:04
040
19550
5.875 wow 8.91 oaica cant 1.00 uanoo cidd
Piök
P@K
Performance of ERAttack under different constraint attacks ADHD dataset
Performance MSE different constraine attacks ADHD dataset
1:31
Da spides
no soate
Sersiitivty
Herge
Sensitivvl Erviiyy
1:22
640 085
U/B E40 6R0 14%
8.40
0.51
5.02
P@k
Figure 6: Performance of different constrained FRAttack and MSE attacks BP and ADHD for Vanilla. Points in different colors represent different constraint attack methods, and the same color represents the same method with different step sizes. The red line implies the Pareto front, and the asterisk marks the selected attack method.
Table 6: CAUC/AAUC of SNs trained by different methods under ERAttack and MSE attack on ADHD and BP.
Method
ADHD(ERAttac))
BP(ERAttack)
ADHD(MSE attack)
BP(MSE attack)
Vanilla
0.7663 0.7729
0.6812 / 0.6920
0.7663 0.7659
0,6744 / 0.6776
WD
0.7513 / 0.7582
0.6739 / 0.6726
0.7508 0.7542
0.6753 / 0.6722
SP
0.7443 / 0.7358
0.6767 / 0.6817
0.7395 0.7375
0.6706 / 0.6763
Est-H
0.7619 / 0.7643
0.6576 0.6594
0.7618 0.7633
0.6572 / 0.6558
AT
0.7325 / 0.7277
0.6405 / 0.6347
0.7649 0.7659
0.6728 / 0.6773
R2ET
0.7090 / 0.7153
0.6697 / 0.6732
0.7061 0.7058
0.6665 / 0.6700
R2ET-mm;
0.7099 0.7008
0.6711 / 0.6720
0.7020 0.
0.6642 / 0.6654
R2ET
0.7169 / 0.6973
0.6833 / 0.6839
0.7049 0.7104
0.6738 / 0.6780
R2ET-mm
0.7590 0.7633
0.6892 0.6957
0.7583 0.7580
0.6841 0.6852
B.2.4
Trade-off between Accuracy and Explanation Robustness
good defensive strategy should be both robust and accurate. Authors in 78 find the trade-off between prediction robustness and prediction performance. We explore the trade-off between the explanation robustness (P@ k) and prediction performance (cAUC/aAUC). A defender looks for a higher P@k and AUCs. In Fig. 7 at least one R2ET and its variants are on the Pareto front all datasets, demonstrating that R2FT and its variants are more advantageous the trade-off between robustness and accuracy. Furthermore, on MNIST, compared with other methods on the Pareto front,
31

---

R2ET variants on the Pareto front sacrifice less AUC (less than 2%) but gain significant improvements on P@k (20% 40%). On BP, Est-H improves k@ by 0.01 but loses about 4% AUC. R2ET on ADHD with both high AUC and the highest P@ k: indicates the possibility that model can be precise and explanation-robust at the same time.
Trade off between Pakk and cAUC MNIIST
Trade-off between Pakk and cAUC on ADHD
Trade off between Pink and cAUC on BP
84120
CALI
k.m
VD
017
SUTT
0.00
012
840
612
P@k
0.2
P@k
0/2
Trade-off between P@k and aAUC MNIST
Trfde between Poik and SAUC ADHD
Trade-off between P@k and aAUC on BP
1.50
6.45-
JAUIC
0:79
0/2
Tur
14/0
672
X3100
678
P@k
Pgak
P@k
1/2
Figure 7: Trfde-off between explanation robustness (P@k) and prediction performance (cAUC/aAUC) on MNIST, BP and ADHD. The red lines imply the Pareto front, and the triangles present R2ET and its variants.
B.2.5 Sensitivity Analysis
Table 7: P@k (shown in percentage) of models trained by different methods under ERAttack. Three numbers on tabular datasets present the results when i is 2, 5, and 8, respectively. h: is set to 10, 30, and 50 on the rest datasets, respectively.
Method
Adult
Bank
COMPAS
MNIST
ADHD
BP
Vanilla
79.3/81.9 87.6
97.9/8144/ 83,0
66.17
84.2
51.6/ 56.7/
39.4/43.2/44
43..2/45.3
63.8 67.3 68.7
WD
100.0/ /99.8/99////// / /91.7
97.2/ 92.592.575 82.4
100.0/88.1 /87.7
51.6/ 56.6
41.0/
/ 48.6
63.6 68.0 68.8
SP
100.0/ 100.0/ 97.4
100.0/ /9.999/999 95.4
100.0/ 100.0 99.5
54.//0.5/63.
39.4/42.7 /4.77
63.9/
66.9 16.9
Est-H
100.0/92.9 /
86.9/83.9
78.4
99.9 83.9 82.6
80,2/82.9 8445
53.3/564/57.1
70.8/ 74.8/ 74.3
Exact-H
100.0/
92.9 81.9
77.2
-1-1-
-1-1-
SSR
100.0 100.0/92.9// / 91.2
87.0 /7.0/85.8/ 76.3
87.4/87.1 82.1
-1-1-
-1-1-
-1-1-
R2FT, N
/90.0/98.5// / 97.55
100.0 / 96.0/ 100.0
84.0 99.1
77.67 /0.6/8077/88 /82.3
59.3/6266/3.1
64.5 /9.77141
R2ET N
100.0/ 99.8 / 93.5
99.2 / 94.8 / 95.8
100.0 / 83.7 95.3
76.5 / 80.0/819
57.2/623// / 64.3
67.6/715/73.1
R2FT
/90.0/93.2/ / 92.1
100.0/ /91. 80.4
79.4 88.8 92.0
81.4/84.1 /85,3
70.7/74.1
66.1/70.5722
R2ET-mm
99.7 /87.8
92.2//
89.0 89.0 82.1
80.6/ 83.5 /849 55.3/ 60.1
(0.//74./75.
In this section, we consider the impacts of three hyperparameters or settings.
Impacts of k. Table 7 shows that R2ET and its variants stay the top compared with other baselines for various k. Besides, we further explore the more fundamental reasons why models perform differently for various k. As mentioned in Eq. (5). the gaps of gradients of original inputs positively contribute to the thickness. In Fig. g we sort the gradients of Vanilla models in descending order
where their gaps can be inferred. Vanilla achieves about 100% P@ k when A 2 Adult and Bank, indicating that even ERAttack cannot effectively manipulate the ranking in such scenarios. The reason is that the top features are much more significant than the rest as shown in Fig. g However, there is narrow margin between the top 2 and top 3 features on COMPAS, and attackers can easily flip their relative rankings, thus Vanilla's s P@ l reduces to around 2/3. On MNIST, BP and ADHD, Vanilla models' P@K k increases as & grows. It seems that models are more efficient against ER Attack with larger k. However, the absolute number of success manipulations for top-k features increases for larger k. Take Vanilla on MNIST as an example, ERAttack distorts the model's 5 features when k=10,
32

---

Gradient magnitude of Vanilla adult
Gradient magnitude of Vanilla bank
Gradlent magnitude of Vanilla on compas
Gradient magnitude
Gradient magnitude
Gradient magnitude
Features in order
Features in order
Gradi ent magnitude of Vanilla an MNIST
Gradient magnitude of Vanilla on ADHD
Gradient magnitude Vanilla
Gradlcnt magnituds
6012-
Gradient maghitude
6413-
mag
0.08
0.08
6089
Features in order
Features in order
Features order
Figure 8: We order the features based on the Vanilla model's gradient magnitude with respect to each original input on different datasets. Notice that these figures would differ for various models.
Impacts in dataset
189
R2ETT,
12ET-mmu
Vanila
FsiH
Exatt-H1
Figure Sensitivity analysis on the number of selected pairs. R2ET and R2ET-mm, H are examined in Bank dataset.
and about 40% 50=20 features when k=50. Since ERAttack uses the same budget for different becomes harder for ERAttack to manipulate more features simultancously (for larger k). However, it indeed kicks off more features from the top positions due to narrower margins on the long tail.
Impacts of the number of selected pairs k'. As discussed Sec. 4.2 fewer (k') compared feature pairs for R2ET and its variants alleviate optimization issues. Specifically, R2ET takes k+k++1 k-1 1xx, i, k) + " -j=k+1 h(x, k; as objective. Since R2ET, and R2ET-mm, are the two best variants tabular datasets, we conduct a sensitivity analysis of these two methods on Bank. We set & 8, and change k from to k. Fig. 9 indicates that R2ET, /r and R2ET-mm, pairs of features
perform much better when k' than those with k' 4. Apparently, when are taken into consideration, R2ET and its variants have a more comprehensive view of feature rankings to maintain the rankings better. Besides that, R2ET and R2ET-mm, outperform almost all baselines, except for SP, for all k'.
Impacts of pretrain retrain. Lastly, we explore how good these methods when applying them in the retrain schema, and each model is retrained from the Vanilla model for at most 10 epochs. Since the Vanilla model has already converged and reached good AUC, we assume that the Vanilla model's explanation ranking is an excellent reference. Thus these robust methods try to maintain the Vanilla model's rankings. The retraining will be terminated if P@ between Vanilla and retrain models' rankings significantly drops, or the retrain model's s cAUC drops lot. Table & presents results for comparing two training schemas. Since SP changes the models' structure (activation function), we do not consider it here. Instead, we add one more baseline, CL (28), because retraining demands much fewer training epochs, thus its time complexity acceptable. More details for
Present the
can be found in Sec. 4.2 Besides that, none of retrain models by Exact-H and SSR can maintain Vanilla model's explanation rankings and cAUC at the same time in Bank dataset, and thus both are not applicable.
33

---

Table 8: p@k (shown in percentage) of models trained by different methods under ERAttack (A: 8). Two numbers indicate the performance of models being trained from scratch or retrained from Vanilla models.
Method
Adult
Bank
COMPAS
Vanilla
87.6 87.6
83.0 / 83.0
84.2/84. 84.2
WD
91.7 88.3
82.4/82.1
87.7 /2.7
CL
-/93.1 87.1 /92.1
-/ 10000
-/87.1
Est-H
/8.22 81.9 1-
82.6/85.1
Exact-H
89.6 / 88.7
87.0
SSR
91.2 / 88.7
76.3 /-
82.1 / 186.1
R2ET,
97.5/ 100.0 93.5/ 100.0
100.0 / 100.0
91.9 / 97.88
R2ET-mm, a
95.8 / 98.3
95.3 99.6
R2ET
92.1 /92.6
80.4 86.2
92.0 85.1
R2FT-mm
75.1 / 86.2
82.1 /874
B.2.6 Faithfulness of explanations on different models
We report the faithfulness of explanations evaluated by three widely used metries, DFFOT, COMP and SUFF, in Table 9
Table 9: Faithfulness of explanations evaluated by DFFOT COMP (1) SUFF (1).
Method
Adult
Bank
COMPAS
MNIST
ADHD
BP
Vanilla
0.24/ /0.18
0.23/0.14/0.04
0.17/0.37
0.37/0.16/022
0.51 /0.05/ 0.28
0.40/ 0.06 0.299
WD
0.45/0.47002
2.26/0.270.00
0.29/0.41/0.18
0,37/0.16/0.2
0.49 /0.06/ 0.27
0.35 / 0.05 0.33
SP
1.43/047/00
1.35/0.11000
0,29 0.29/0.45/0.1
0,38
0.30/0.10/ 0.34
0.38/ /0.06/00/// 0030
Est-H
0.44 0..44/0.44
0.18/0.21
0.06
/2.42/./0011
0,23
/0.04/0000 0.26 0.59
/.45 0.24
Exaci-H H
0.43 0..46 0.23
/.14 / 0.04
0.30/0.40/0.18
-1-7-
-/-1-
-1-1-
SSR
0.54
L.06//.04//
0.32/0.43/0.18
-1-1-
-1-7-
AT
0,16/0.14/00 0.008
0.19/0.10/000
0.03
0.24/0.10/ /.01
1.40/0.1//0.28
0.35 /0.10/0///00 0.26
0.46 /..06/06/// 1.25
R2ET x
0.13
0.34/0.32/00 0.10
/./00//0/..11
0.23 /.222/022222 0.19
0.38 /0.1//0///0300 0.37
0.43 0.07 0.29 0.42 /.00 / /0.99
R2FT-mm,
0.42/0.47 0.22
0.34 /0.41 / 0.14
0.25/0.42/0.1
0,25 /..22/ 0.21
0.37 / 0.17 0.37
R2ET
0.32/0.460..1
0.11/0.24/000
0.27 02.39/.9/0.11
0.18/0.244 0.23
0.42 0.07 0.29
R2ET-mm
0,38 / 0.48////// 0.20
0.12 022/0021//// 0.08
0,28 0.44 00.15
0.19 0.26 0.22
0,50
0.25
0.45 / 0..05 0.29
C Related Work
Explainable machine learning and explanation robustness. Recent post-hoc explanation methods
for deep networks can be categorized into gradient- based [103]
71
7
75
777
73
100,
98
35).
surrogate model based (64 30 82), Shapley values [47 12
45
99 and causality [58] 10 56).
The gradient-based methods are widely used in practice due to their simplicity and efficiency
55
while they are found to lack robustness against small perturbations 23
Some works
83 70 80 propose to improve the explanation robustness by cone-conu adversarial training (AT). To bypass the high time complexity of AT, some works propose replacing ReLU function with softplus 17 training with weight decay [16], and incorporating gradient- and Hessian- related terms as regularizers [1
13
32
88 9T]. Some works propose new explanation methods, rather than truining methods, to enhance explanation robustness 46
44 [1 51 (5) 75). Besides, many works 96, [4 78, 90. [01 [8] for improving adversarial robustness focus on prediction robustness, instead of explanation robustness, and thus are different from our work. The work [97] proposes the prediction thickness by measuring the distance between two decision boundaries, while our explanation thickness qualifies the expected gaps between two features' importance. Furthermore, the explanation thickness is inherently more complicated to optimize due to the nature of gradient- gradient-based explanations being defined as first-order derivative relevant terms.
[50 79 87 12 67 63 97
28
Ranking robustness in IR. Ranking robustness in information retrieval (IR) concerning noise [166 and adversarial attacks (26) 104
105
42 85 is well-studied. Ranking manipulations in
IR and explanations are different because 1) IR, authors either manipulate the position of one
candidate [104] 26), or manipulate query to distort the ranking of candidates [104] [05] 42 We
34

---

manipulate input to swap any pairs of salient and non-salient features. 2) Ranking in IR is based on the model predictions. However, explanations are defined by gradient its variants, and studying their robustness requires second or higher-order derivatives, and it motivates us to design an efficient regularizer bypass costly computations.
Top-k intersection. Top-k intersection is widely used to evaluate explanation robustness 13 88
74
32
83
70
23
However, most existing works study the explanation robustness through Lp
norm [13
16
7
88
cosine similarity 83 84]. Pearson correlation [32], Kendall tau [83] or
KL-divergence 70). These correlation metrics measure the explanation similarity using all features, and high similarity can have entirely different top salient features. To optimize the top-k intersection in classification tasks. some works propose various surrogate losses based on the upper bounds of
top-k intersection 12 37 38 39, g 95 60]. The upper bounds hold for predictions whose gaps are not larger than one, while it is not always true for gradient-ban based explanations with unbounded values, which prevents adopting similar methods to explanation tasks.
Distributional shift. The distributional shifts [6] 41 and our work are distinct concerning the "perturbation budget" between the original and perturbed inputs: In contrast, the distributional shifts ensure reasonable predictions (and explanations) for out-of-distribution samples, where substantial deviation from the in-distribution samples is expected, naturally leading to different explanations and rankings. The input perturbations are intentionally neglectable in ours, and other adversarial robustness works, for stealthiness.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction outline the primary contributions, which include
the thickness metric (in Sec. (4.1 and corresponding training method R2ET (in Sec.
alongside their theoretical analyses (in Sec. 5 and experimental results (in Sec.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The only noticed limitation of the work is discussed in Sec.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification: The complete proofs for the theoretical analyses are provided in Appendix A
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the information needed reproduce all the experimental results disclosed in Appendix
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is public at
wwwpccc//ccccccc/ccc//cc R2ET
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The relevant information is disclosed in appendix 1.2
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Main result in Table includes the statistical significance tests.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification:
The relevant information is disclosed in appendix B.1.2
36

---

9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp/s//aarrrpp..ccccaaaa/aaas
Question:
Answer: [Yes]
Justification: The research conforms with the NeurlPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field Machine Learning. There many potential societal consequences of work, none which we feel must be specifically highlighted here.
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original papers for the datasets cited properly.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
37


Reviews:
[{"review_id": "73587jkDH0", "reviewer": "Reviewer_X6uh", "summary": "In this work, the authors study explanation robustness particularly for saliency-based explanations based on gradient information. They propose to use a robustness metric based on the saliency ranking of features. The central benefits claimed (taken from the introduction_ for this approach are: \n* Relying on $\\ell_p$ metrics is not a good/reliable proxy for robustness\n* Attacking $\\ell_p$ metrics leads to an arms race between attackers and defenders\nIn their methodology they provide an alternative called R2ET, the ranking based robustness metric, and describe how this is linked to certified prediction robustnes and adversarial training. Moreover, they state the optimization problems one must solve to compute the R2ET metric. \nExperimentally, the authors explore tabular and image datasets and across various models compute the described R2ET metric.", "questions": "It is not impossible that my main three points in the weaknesses section stem from a misunderstanding. Do the authors think that I have missed something or misrepresented any of their points?", "limitations": "The primary limitation of the paper is in its motivation.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well written in that the authors make their motivations and methodology clear. They also attack an interesting and worthwhile problem in explanation robustness and have put substantial time into their experiments which leads to a comprehensive evaluation of the proposed metric.", "weaknesses": "The two critical weaknesses I see with this work are its motivation and evaluation. \n\nMotivation: \nPoint 1) The authors first motivation is that explanations within a small $\\ell_p$ norm can flip all of the rankings and have significantly different \"top\" features, thus we should use a ranking approach. However, this exhibits the fallacy of \"begging the question.\" Explanations within a small $\\ell_p$ norm ball can only appear different when visualized with a heatmap if the values in each feature dimension are very small.^1 This is because what the heatmap shows us is a \"ranking\" of the highest magnitude features, thus the argument boils down to: \"Because small $\\ell_p$ norm explanations have a non-robust ranking, we should look at a robust ranking approach\" which seems like a poor motivation given that explanations with a small $\\ell_p$ norm are not the only kinds of explanations that exist unless your classifier is extremely flat. \n\nPoint 2) The authors state that attacking $\\ell_p$ robustness leads to an arms race, but also cite [89] which is a formal certification method that proves no attacker exists and therefore thwarts the arms race (although only for small models). If the authors wish to claim the attackers arms race as a motivation for this paper I think they need to do more to (1) show that an arms race will not exist for their method which is not obvious to me and (2) need to show that they scale far beyond [89] which it appears they already do, but this point will need to be made explicit \n\nPoint 3) I think the authors should introduce some toy experiments to show where and how their approach really benefits compared to gradient-based explanations. My intuition is that the only benefit of this approach is when the magnitude of the input gradient is small. Is this the authors intuition as well? \n\n^1 I suspect if the authors add values to the colormap under the right-most portion of figure 1 we will see this. Because the", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> To Weakness 1: The authors first motivation is that explanations within a small L-p norm can flip all of the rankings and have significantly different \"top\" features ...\n\n1. **There is a misunderstanding of what the L-p norm is measuring** and let us clarify that. The “small L-p norm” is **not used to measure the magnitude of the explanation itself**, but to **qualify the distance between an original and its perturbed counterpart**. Our study is driven by the observations (Fig. 1) that a “slightly manipulated” explanation (with *a small L-p distance to the original explanation*) can lead to *extremely different feature rankings* from the original ranking, altering human perception and decision-making processes. Thus, we study ranking-based metrics aligning with human perception of salient features.\n\n2. The above response is **irrelevant** to the magnitude of the original explanation (e.g., no matter whether the gradient’s L-p norm is large or small). As detailed in Proposition 4.5, changes in rankings depend on the joint effect of the *differences in gradient values* and the *Hessian matrix*, rather than the value of the L-p norm.\n\n3. In our experiments, the classifiers are not necessary to be (extremely) flat since we impose no such constraints and assumptions on the explanations, and R2ET has shown to be effective generally. \n\n> To Weakness 2: The authors state that attacking L-p robustness leads to an arms race...\n\n1. Theoretically, Proposition 4.5 delineates that the defender, e.g., R2ET, with proper objective function preserves the explanation rankings for **all** types of attackers with a given perturbation budget, and thus mitigates the arms races. Specifically, the proposition shows that the attackers cannot alter the models’ explanation ranking if their perturbation budgets is below the critical threshold (RHS of the inequality). The only chance to manipulate the ranking is to increase the attack budgets. On the other hand, the defenders, e.g., R2ET, increase the critical threshold to prevent **any types of attackers** to mitigate the arms races. In the case of Hessian norm being nearly zero (the denominator goes to zero), it becomes practically impossible for attackers to manipulate rankings successfully. Notice that the proposition is regardless of the “scale” of the models. \n\n2. Experimentally, Table 1 and Appendix B.2.3 report explanation robustness facing **attackers with different objectives and different attack strategies**, respectively. For all types of attackers, R2ET typically showcases superior robustness under various attacks, indicating the mitigation of the arms races. The datasets and models involved in the experiments are significantly “larger” than those in [89], e.g., the largest feature dimension studied in [89] is **2k** in [89] compared to **396k** in ours.\n\nIn sum, we will clarify these statements more explicitly in the revised version. \n\nPS. Our proposed approach focuses on ranking-based metrics for evaluating explanation robustness, and contrasts to the L-p norm-based metrics used in [89].\n\n> To Weakness 3: I think the authors should introduce some toy experiments...\n\nEssentially, R2ET enhances explanation ranking robustness because it maximizes the gaps among features and minimizes Hessian norm, **rather than minimizing the magnitude of the gradient**. Intuitively, wider gaps (larger absolute distances) indicate more significant distinctions in feature importance. The Hessian norm implies the change rate of the feature importance, and a smaller Hessian norm makes it harder for attackers (or any perturbations) to change the model behavior. \n\nOur empirical evidence shows that the key is not the magnitudes of gradients, but their differences. Specifically, in Lines 935-943 (Figures 8 and Table 7) of the appendix, we take the top-2 case of models in Bank and COMPAS in Figure 8 and Table 7 as an example: the model for Bank showcases a smaller average gradient magnitude (approximately 0.08) yet achieves greater top-2 robustness compared to the one for COMPAS, which has a larger gradient magnitude (around 0.3). It indicates that our approach’s benefits extend beyond conditions where gradient magnitudes are minimal.\n\nTo address your suggestion regarding toy experiments, which could indeed further validate and clarify the benefits of R2ET. We will consider adding these experiments in the revised version.\n\n\n> To Question: It is not impossible that my main three points in the weaknesses section stem from a misunderstanding. Do the authors think that I have missed something or misrepresented any of their points?\n\n**The most significant misunderstanding is the role of L-p norm. We do not focus on the norm of explanation, e.g., $|I(x)|$, nor small norm explanations. Instead, we investigate whether the L-p distance between the original explanation and its perturbed counterpart, e.g., $|I(x)-I(x’)|$, can serve as a suitable explanation robustness measurement.**\n\nThe reviewer seems to misunderstand that we study and restrict the L-p norm of explanation, and doubts the motivation for studying gradient-based explanations with a small L-p norm. However, as Figure 1 shows, our core argument is that even a seemingly minor change (evaluated by L-p norm) in explanations could lead to extremely different explanation rankings (compared to their original explanation ranking). It underscores the necessity for a novel ranking-based approach to assess explanation robustness. **The magnitude of the gradient is not our main focus, and will only marginally impact our theoretical and experimental conclusions.**\n\n***We would appreciate it if the reviewer could diminish the misunderstanding and re-read the manuscript concerning our response. It would be even better if the reviewer could give more feedback and raise the scores.***", "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": "", "extra_scores": {}}, {"review_id": "APNY4Rtmw9", "reviewer": "Reviewer_9MCa", "summary": "The paper describes a regularizer to add to a loss function to encourage the resulting model to\nhave input attributions robust to ranking changes in its top k features. That is, for an input x,\nthe input attributions (a score for each input) for this input will be similarly ordered (at least\nin the top k scoring features) as compared to the input attribution of any small perturbation x' of\nx. The argument to use ranking and top-k ranking for defining robustness is that only the top few\ninput features are of relevance to a human interpreting an explanation. Ranking robustness itself\nmight be because the relative importance of features is more relevant to the human than the\nabsolute magnitudes of the importance.\n\nTo make ranking robust, the regularizer encourages gaps or \"thickness\" in the scores of top-k most\nimportant features which would naturally make it harder to reorder them via a small perturbations\nin the inputs and therefore (by addition of Hessian to encourage smoothness of gradients) feature\nimportance scores (which are assumed to be gradients or \"saliency\"). Analytical arguments are made\nas to how to effectively implement the regularizer in a more efficient fashion. Analytical\narguments are presented as to a worst-case performance of an attack on the proposed method (though\nwhy worst case is relevant confuses me).\n\nA large collection of experiments demonstrate the use of the regularizer (termed R2ET) with various\nparameters and compared to other robustness methods faced with several adversarial explanation\nmanipulation methods. These results show the proposed method is not optimal in all cases though it\nis in many.", "questions": "- Q1. My understanding of a lot of the technical discussions in the paper was limited so the\n  comments in the weaknesses in the prior section might not be fully justified. If this is the\n  case, please address how the paper does not have the stated weakness. For those that are\n  weaknesses, please comment on plausibility of addressing them either with my suggestions or\n  otherwise.\n\n- Q2. Proposition 4.6 relates Equation 6 and Equation 7. 7 includes perturbations while 6 does not.\n  I'm having trouble qualifying the perturbations to make the statement make sense. Please include\n  some higher-level points as to why this and other \\theorems follow.\n\n- Q3. Some results show that the regularization without the Hessian performs better than with it\n  which is casting some doubt on the theoretical arguments. Alternatively it could be a mismatch\n  between P@k and the optimization goal. Can ranking consistency be measured more directly? (i.e.\n  as per suggestion of W1) and would it be able to explain the \\H results?\n\n- Q4. How would directional scores affect the methodology? While saliency has a sign, I don't see\n  it demonstrated in this paper with a sign. Have all attributions been absolute valued first?\n  Generally an explanation with both positive attribution and negative attribution would be more\n  valuable and perhaps relative to ranking, having top-k (positive) and bottom-k (negative) would\n  be the equivalent.\n\n- Q5. I'm not following the purpose of worst-case complexity of an adversarial attack (Section 5).\n  Wouldn't it make more sense to lower bound the complexity of an attack instead of upper bound it?", "limitations": "Only one limitation is noted in Section 7 with regards to using a surrogate of thickness. I believe\nthere are further limitations as noted in W3 for example. Societal impacts not mentioned though\naddressing explanation robustness for its own sake or against adversarial perturbations is expected\nto have only positive societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ S1. The approach includes analytical and experimental methods and seems to achieve to some extent\n  the ranking robustness goal.\n\n+ S2. Multiple adversarial attacks experimented with including one aimed at ranking specifically.\n\n+ S3. Multiple other robustness methods experimented with including several that approximate some\n  of the same loss terms (i.e. the Hessian) in different ways (though lack of experimental timing\n  information is a shortcoming as listed below).", "weaknesses": "- W1. Motivation is based on ranking robustness but ranking robustness is not directly measured in\n  the experimental sections. In the collection of explanation metrics enumerates in B.1.4, the P@k\n  only partially exposes robustness with respect to ranking thought would miss all importance swaps\n  that happen within the top k features. The experimental discussion seems to be making the case\n  that the proposed top-k thickness metric is related to P@K but as P@k does not fully capture\n  ranking robustness, those arguments also fail to make the connection. While I agree that\n  optimizing for thickness would promote ranking stability, I do not find the concepts identical\n  (i.e. there may be other or better ways to achieve ranking stability). Some experimental results\n  may be hinting at the mismatch where I see the regularizer without Hessian sometimes\n  outperforming the one with it.\n\n  Suggestion: Include a more direct ranking robustness measure in the experimental results. I'm\n  unsure what form of such a measure would be. Perhaps ranking correlation from [103] can be used\n  for feature importance in the present paper.\n\n- W2. Computational effort reduction not demonstrated. Part of the design seems to be limit\n  backwards passes or other computationally costly steps. The experiments are plenty but none seem\n  to demonstrate this aspect. There is an analytical time complexity discussion in the \"Time\n  complexity of R2ET\" paragraph. The title itself suggests that stability is free but is a bit\n  deceptive in that the training incurs additional costs.\n\n  Suggestion: Include the experimental measurements of effort in the results. One of the strengths\n  of the present approach is that the explanation-time is less costly as saliency is relatively\n  less costly than alternatives. Showing this would be good to discuss/experiment with as well.\n\n- W3. Most (or all) theoretical analysis applies only to saliency. Arguments/discussions regarding\n  Proposition 4.6 in the appendix include the assumption that the explanation is a gradient (a\n  saliency explanation). Saliency are defined in Preliminaries but it is not clearly stated there\n  that the rest of the paper assumes all explanations are of this form. As the methods target\n  saliency, a lot of this paper depends on saliency being a good explanation method to begin with.\n  However, plenty of works argue that it is not (see [73, 75]). Some benefits of things like IG\n  also share motivation to ranking robustness (that relative scores are more important than\n  absolute).\n\n  Suggestion: Make it clear that the analytical sections make this assumption. Also, note in the\n  \"Apply R2ET to other explanation methods\" paragraph in Section 6 that the analytical conclusions\n  do not apply to these other methods. A good inclusion to the limitations discussion would be that\n  saliency itself has some problems which may warrant use of a different explanation method\n  especially for problems with regards to robustness which this work is attempting to solve using a\n  regularizer.\n\nOther comments/suggestions:\n\n- C1. The intro/motivation could use some discussion of how the primary desiderata in explanations\n  and how they related to each other. The paper is primarily based on ranking robustness which I\n  could say is an element of an explanation's interpretability and resistance to adversarial\n  manipulation. From here it would be useful to say that addressing robustness could be done with\n  adjustments to the explanation method or to adjustment to the model or training. The paper\n  discusses the second but a note about the benefits/drawbacks of the first would be good to\n  include as they introduce some of the subsequent experiments which are presently hard to fit into\n  the big picture.\n\n  1. Want (interpretability and) resistance to adversarial manipulation.\n\n  2. Option 1: Change the explanation method (don't use Saliency). Benefit: no model changes.\n     Drawbacks: faithfulness vs robustness tradeoff. Explanation-time costs might be large.\n\n     Option 2: Add regularizer for saliency during training. Benefits: Fast (or \"free\" as per\n     title) explanations, better faithfulness, Drawbacks: training-time costs, utility loss.\n\n     Option n: ???\n\n  3. We do Option 2 and here are analytical and experimental results demonstrating the strengths\n     and the impact of weaknesses.\n\n  This chain of thought justifies the present (i.e. faithfulness) and suggested experiments (i.e.\n  costs as per Weakness W2). Some of the experiments in the Appendix might be approaching these\n  points though I'm having trouble connecting the dots.\n\n- C2. The \"thickness\" notion could be better presented in the experiments. Figure 8 in the appendix\n  shows some saliency/importance graphs without regularization for gaps. Can you include similar\n  pictures for regularized models? I would expect to see the top-k features to have a linear\n  decrease in importance. Seeing this (or something else) could go a long way in building intuition\n  in the approach described in this paper.\n\nSmaller things:\n\n- The intro point about \"inherent limitations of human cognition\" as an argument for top-k\n  importance doesn't apply as well to vision tasks where our eyes look at a huge number of raw\n  features and necessarily so in order to resolve higher-level structures.\n\n- The top-k thickness paragraph on line 97 cites [107] as a work suggesting maintaining ranking of\n  features but this work is not on feature importance. The \"raking\" there is because the topic is\n  ranking models.\n\n- The statement \"only the top-k important features in \\cal{I}(x) are more relevant to human\n  perception\" is quite vague and I'm unsure how it could be formalized. Also note the grammar issue\n  (\"more relevant\" than what?).\n\n- \"cost computations\" -> \"costly computations\".\n\n- \"single-input DNNs\", this reads like the DNNs have a single input neuron but doesn't mean that.\n  Rephrase?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\nDue to the character limitation of rebuttal, we have to make the response concise and simple. Feel free to discuss them if more questions/concerns. \n\n> To W1:\n\nWe agree that P@k may not be the “best” and “direct” metric for capturing ranking stability, and believe that the study of “best” evaluation measurement may be explored in future work, which potentially calls for psychology experts or human-involved surveys.\n\nWe evaluate the explanation ranking robustness by P@k because 1) P@k is widely used to evaluate the explanation robustness in existing works [13, 86, 72, 32, 81, 68, 23]. 2) P@k better aligns with human perception. As shown in Figure 1, only the top few features (without their importance score nor relative rankings) will be delivered to end-users in credit card applications. \n\nFurthermore, as discussed in Lines 997-1000, while there are various metrics for ranking similarity—such as cosine similarity, Pearson correlation, and the one in [103]—these can be sensitive to changes in the ordering of less important features, which might not reflect human perception accurately as well. Because they often consider the entire rankings, potentially distorting their usefulness in scenarios where only the most critical features are relevant to decision-making.\n\n> To W2:\n\nWhile we include an analytical discussion on the time complexity of R2ET in the Appendix, we acknowledge that we did not present empirical data comparing the actual training times. Because the training time is influenced by several factors such as *convergence rates, hardware specifications, and learning rates*. Rather, we compare R2ET with baselines using **similar analytical training resources** (number of backward propagations), except Exact-H and SSR which are much more costly. Besides, we agree that demonstrating the computational efficiency of R2ET during explanation time could significantly strengthen our argument, as R2ET adds no cost to the existing gradient-based explanation methods.\n\n> To W3:\n\nIn the revised version, we will clarify that the theoretical analysis applies to gradient (saliency) explanations, as initially introduced in the preliminary. Although the primary results are on saliency explanations, we extend our work by showing that R2ET could generalize to other mentioned explanation methods, such as Grad*Inp, IG and SmoothGrad, by maximizing their lower bounds (Appendix A.1.2). The experimental results further indicate R2ET could fit more explanation methods.\n\n> To C1: \n\nThanks a lot. We agree with your comments, and will partially modify our writings logics in the revised version according to your suggestions.\n\n> To C2:\n\nWe report “thickness” in Figure 2, Table 3, and Table 5, to show the strong correlation between thickness and robustness. The gaps shown in Figure 8 are not exactly the same as the thickness. We will include more figures for R2ET, and it is supposed to see a significant gap between the $k$-th and $(k+1)$-th features, aligning with R2ET's objectives.\n\n> To \"small things\":\n\nFor small thing 1: We agree that humans may resolve higher-level structures and discuss such high-resolution images in the “concept-based” explanation cases, where top-k *sub-regions* may be of more importance than others. \nFor others, we will modify our writing and make them clearer.\n\n> To Q1:\n\nPlease refer to the response above. \n\n> To Q2:\n\nThe connection is the perturbation budget $\\epsilon$. Intuitively, Eq. (5) shows that a L-locally Lipschitz model’s local behavior under an $\\epsilon$ manipulation can be approximated using $\\epsilon$ and its high-order derivative information (such as Hessian). A large $\\epsilon$ (for a stronger manipulation) leads to a rigorous restriction to the model (e.g., smaller change rates). Based on Eq. (5), R2ET in Eq. (6) “integrates” $\\epsilon$ into $\\lambda_2$. On the other hand, Eq. (7) aligns with two objective functions with $\\epsilon$ as shown in Lines 629-634.\n\n> To Q3:\n\nWe have justified the use of P@k in response to W1. \n\nAs shown in Table 3, the model with the highest thickness leads to the best P@k. Thus, we attribute the super performance of R2ET\\H to their higher thickness than R2ET. In other words, R2ET does not always achieve the best performance *may* because of the potential mismatch between **R2ET’s optimization goal** and **thickness**. Although we agree that there *may* be a mismatch between **P@k** and **“real ranking consistency”**. The later mismatch will be one of our future research directions.\n\n> To Q4:\n\nOur analysis and methods in Sections 4 and 5 are independent of the signs of gradients. In other words, the statements and proofs will hold in the general case where saliency does or does not have a sign. In the experiments, we follow existing works to take the magnitude (absolute values) of the gradient.\n\n> To Q5:\n\nWe study the “worst-case” for attackers in Sec. 5, which provides a guarantee for a successful attack on the explanation rankings. In practice, the attacker could be limited to its attack (perturbation) budget and computation resources (number of attack iterations). Thus, the guaranteed successful attack is defined by the upper bound of the attack iterations.\n\n> To limitation:\n\nWe will show the assumptions more explicitly as one of the limitations, and discuss the (positive) societal impacts in the revised version.", "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": "", "extra_scores": {}}, {"review_id": "amOigPlbE8", "reviewer": "Reviewer_VSmU", "summary": "The paper aims at a robust explanation of predictive models. A new concept called “feature ranking robustness” is proposed and a corresponding objective function called “explanation thickness” and an optimization algorithm R2ET is designed to increase the thickness during model training time. Theoretical analyses that covers the numerical and statistical aspects of the thickness are provided. Experiments results on diverse data modalities including tabular, image, and graph data, demonstrate the robustness of the explanations obtained from the thickness metric.", "questions": "-\tIn Figure 2, why the correlation indicates that thickness is a better metric of explanation robustness? More details are needed.\n-\tWhen applying R2ET to other explanation methods, do you need to modify the R2ET algorithm? In other words, how easy it is to apply R2ET to a broader spectrum of explanation methods?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The enhancement of explanation robustness is different from prediction robustness as higher-order gradients are involved. The submission consider a new metric based on relative ranking of top-k salient features rather than distance between saliency maps over all features, thus focusing more on the important features that will be perceived by the users.\n2) he theoretical analyses are relevant and novel. In particular, the authors connect thickness to certified robustness, adversarial training, and constrained optimization (section 4.2), and the multi-objective optimization analysis help clarify the trade-off between model accuracy and explanation robustness. The experimental results are solid, with many datasets, baselines, and metrics to verify the proposed method.\n3) The paper is well-organized and concepts are clearly defined.\n4) while explanation robustness has been studied previously, the paper adopts a new perspective of top-k thickness. Then this concept results in a new optimization algorithm and in-depth theory. In particular, formulating explanation problem under the MOO framework and the learning theoretical framework make unique and significant contribution to the XAI community. It seems that the R2ET algorithm can be applied to multiple different gradient-based explanation methods.", "weaknesses": "-\tThe thickness concept has been used for prediction robustness. \n-\tEq. (6) involves evaluating the Hessian matrix and that can be quite time consuming, compared to WD that does not need the Hessian matrix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\n\n>To Weakness 1: The thickness concept has been used for prediction robustness.\n\nTheir fundamental meanings differ: the thickness for prediction robustness measures the distance between two decision boundaries, while explanation thickness qualifies the expected gaps between two features' importance. Furthermore, different from the “boundary thickness” for prediction robustness, our explanation thickness is inherently more complicated to optimize due to the nature of gradient-based explanations being defined as first-order derivative relevant terms. Thus, we try to speed up the computation and avoid adversarial training. \n\n> To Weakness 2: Eq. (6) involves evaluating the Hessian matrix and that can be quite time consuming, compared to WD that does not need the Hessian matrix.\n\nWhile Eq. (6) requires calculating the Hessian norm, we address the potential computation burden by the finite difference. It allows us to **estimate the Hessian norm effectively with only two additional backward propagations**. Thus, compared to Vanilla and WD, R2ET remains competitive in terms of computations. R2ET is much more time-saving comparing many existing baselines, such as about **20x faster** than adversarial training. More discussions concerning time complexity are in Lines 810-818.\n\n\n> To Question 1: In Figure 2, why the correlation indicates that thickness is a better metric of explanation robustness? More details are needed.\n\nThe left subfigure demonstrates a high correlation between the sample’s thickness and the attacker’s required budget to manipulate the rankings. This high correlation signifies that samples with greater thickness demand a larger attack budget for a successful manipulation, thereby justifying that thickness serves as a metric for evaluating explanation robustness. \n\nConversely, the right subfigure shows a low correlation between the Hessian norm of samples and the required attack budget. It indicates that the difficulty of manipulating explanations remains similar across samples, regardless of whether they have a large or small Hessian norm. This low correlation suggests that the Hessian norm is not a reliable indicator of explanation robustness. \n\n> To Question 2: When applying R2ET to other explanation methods, do you need to modify the R2ET algorithm? In other words, how easy it is to apply R2ET to a broader spectrum of explanation methods?\n\nR2ET is general to *a range of gradient-based explanation methods*—including Gradient (Grad), Gradient*Input, SmoothGrad, and Integrated Gradients (IG)—**without any modifications** given theoretical analysis (see Appendix A.1.2) and experimental outcomes (Section 6). \n\nIn the future, we aim to extend R2ET to a broader spectrum of explanation methods *beyond gradient-based ones*. Given the objective of R2ET that directly maximizes the gaps between feature importances and minimizes the Hessian norm, R2ET should also perform effectively with other explanation methods.", "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": "", "extra_scores": {}}, {"review_id": "jUZRfiFvfj", "reviewer": "Reviewer_4WDh", "summary": "The paper proposes a novel metric for assessing the stability of explanations in machine learning models, which is crucial for their trustworthiness. The authors introduce a method called R2ET (Robust Ranking Explanation via Thickness) designed to train models to generate stable explanations efficiently and effectively. They provide experiments across various data modalities and model architectures, showing that R2ET achieves superior stability against stealthy attacks and generalizes effectively across different explanation methods.", "questions": "Should the authors address the identified weaknesses (listed in descending order of importance), I would be inclined to raise my rating. These revisions would enhance the paper’s contribution to the field and its practical applicability.", "limitations": "The discussion of limitations in the paper could be more comprehensive. While the authors mention general applicability issues, they do not delve into specific limitations that might affect the deployment of their method in real-world settings, particularly in scenarios with highly variable and noisy data.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of a new metric that aligns more closely with human perception than existing $\\ell_p$ distance measures is compelling.\n2. The theoretical grounding of the methods and the extensive empirical validation provide a high degree of confidence in the results.\n3. The paper is clearly written.", "weaknesses": "1. The paper’s discussion of explanation robustness is focused on adversarial robustness. However, the explanation robustness can also be affected by other factors, such as distributional shifts [1, 2]. It would be beneficial to discuss the relationship and difference between the proposed method and these methods.\n2. While the paper tests various data modalities, the focus is small-scale datasets, such as MNIST. Could you discuss the potential limitations of the R2ET method when applied to real-world, large-scale datasets? An evaluation of the scalability of the proposed method is beneficial.\n\n[1] Li et al. “Are Data-driven Explanations Robust against Out-of-distribution Data?” CVPR 2023.\n\n[2] Pillai et al. “Consistent explanations by contrastive learning” CVPR 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\n\n> To Weakness 1: The paper’s discussion of explanation robustness is focused on adversarial robustness. However, the explanation robustness can also be affected by other factors, such as distributional shifts [1, 2]. It would be beneficial to discuss the relationship and difference between the proposed method and these methods.\n\n1. We believe that adversarial robustness (AR) and distributional shifts (DS) as highlighted in [1,2] are **distinct** because of the “perturbation budget” $\\epsilon$ between the original and perturbed inputs: $\\epsilon$ is **intentionally small** in AR for stealthiness, but **relatively large** in DS due to the more substantial variations inherent in out-of-distribution (OOD) samples, making DS and AR **incomparable**. \n\nSpecifically, the goal of AR is to **maintain the explanations unchanged** even with *neglectable* input perturbations, aiming for consistency in explanations. In contrast, DS ensures **reasonable predictions (and explanations) for OOD samples**, where a *substantial deviation* from the in-distribution samples is expected, naturally leading to **different explanations and rankings**.\n\nFor example, two images of birds (e.g., Figure 2 from [1]), although from the same class, differ significantly in shape and location, leading to varied feature importance across the images. This variability is typical in DS scenarios. Conversely, in AR cases, the visual and explanatory differences are minimal, thereby requiring the explanation rankings to remain consistent.\n\n2. Despite the fundamental differences of $\\epsilon$ between AR and DS, the concepts and properties of thickness and R2ET, as detailed in Section 4, are not specified to AR, but **broadly applicable to different robustness scenarios**. Thus, we can view them in the DS frameworks:\n\nSpecifically, the variable $\\mathcal{D}$ in Definition 4.1 and 4.2 (definition of thickness) denotes the (unknown) distribution of sample $x'$. The thickness can be defined under DS framework by viewing $x\\in\\mathcal{X}$ as in-distribution samples, and $x'\\in\\mathcal{D}$ as out-of-distribution samples. Furthermore, Propositions 4.4 – 4.7 do not rely on specific assumptions about the distribution $\\mathcal{D}$ and merely limit the perturbation budget to $\\epsilon$. Thus, these propositions hold even if $\\mathcal{D}$ represents the out-of-distributions. This adaptability indicates the universal applicability of thickness and R2ET, making them address both AR and DS challenges effectively.\n\n> To Weakness 2: While the paper tests various data modalities, the focus is small-scale datasets, such as MNIST. Could you discuss the potential limitations of the R2ET method when applied to real-world, large-scale datasets? An evaluation of the scalability of the proposed method is beneficial.\n\nWe want to point out that we also include ROCT image dataset from *real-world medical applications* (where robust explanation is of critical importance) in our experiments. The dataset consists of images having 771x514 pixels on average, making it **comparable in scale** to well-known datasets such as ImageNet (469x387), MS COCO (640x480), and CelebA (178x218). \n\nRegarding the scalability of the R2ET method, we analyze the computational efficiency of R2ET, highlighting that it requires **only two additional backward propagations**. This makes R2ET considerably more efficient (**20x faster**) than many adversarial training (AT) methods, as well as [1] and [2]. More discussions are disclosed in Lines 810-818. This efficiency suggests that R2ET’s approach to generating robust explanations is scalable to larger, more complex datasets while maintaining computational feasibility.\n\n\n> To Limitation: The discussion of limitations in the paper could be more comprehensive. While the authors mention general applicability issues, they do not delve into specific limitations that might affect the deployment of their method in real-world settings, particularly in scenarios with highly variable and noisy data.\n\nWe recognize that the limitations discussed could be expanded to better address scenarios that involve highly variable and noisy data, which fall outside the “small perturbation” scenarios. While the theoretical analyses in Sections 4-5 will still hold across varying distributions and perturbations, affirming that our approach is theoretically sound under unknown perturbations. It points to a valuable direction for future research: testing and potentially adjusting R2ET to ensure robustness and reliability in more diverse and challenging environments.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers have reached a consensus that the paper has made a good theoretical and experimental contribution to explanation robustness. The paper is well-organized and the proposed perspective of top-k thickness is new. Following reviewers' comments, AC is happy to recommend acceptance for this paper.

However, note that some weaknesses are highlighted by the reviewers. These include:
1. The motivation needs to be further polished.
2. Discuss the computational overhead of the proposed method and its application to more large-scale datasets.

Please take these comments into consideration in the revised version of this paper.
Decision: Accept (poster)