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_cc_2024_Conference
Published: 2024-05-14 04:36:09

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.

Main paper: 
 introduction: 
 Deep neural networks have proven their strengths in many real-world applications, and their explainability is a fundamental requirement for humans' trust [25, 62] . Explanations usually attribute predictions to human-understandable basic elements, such as input features and patterns under network 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 intuitive interpretation. However, the gradients can be significantly manipulated with neglected changes in the input [16, 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. 1 , novel explanation methods [75, 77] and training methods [13, 17, 88] 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 [1] . Existing works [17, 88, 13, 16 ] study the explanation stability (robustness) through ℓ p distance. However, as shown in the right part of Fig. 1 , a perturbed explanation with a small ℓ p distance to the original can exhibit notably different top salient features. Therefore, relying on ℓ p distance as a metric for optimizing the explanation stability fails to attain desired robustness, indicating the necessity for ⃝): Adversarial attacks against the explanation by manipulating the input. Right: Two examples of the saliency maps (explanations) show that smaller ℓp distances do not imply similar top salient features. I(x ′′ ) has a smaller ℓ2 distance from the original explanation I(x), but manipulates the explanation more significantly (by top-k metric) 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 ′ )'s 100% and 92% top-k overlap, respectively. a novel ranking-based distance metric. Second, unlike robustness of prediction and ℓ p 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) [86, 74] 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 thickness" 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 ℓ p norm attack cannot manipulate explanations as effectively as ranking-based attacks. R2ET achieves more ranking robustness than state-of-theart 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. 
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) is used to improve the explanation robustness [13, 74] . Alternatively, some works propose replacing ReLU function with softplus [17] , training with weight decay [16] , and incorporating gradient-and Hessianrelated terms as regularizers [17, 88, 91] . Besides, some works propose post-hoc explanation methods, such as SmoothGrad [75] . More relevant works are discussed in 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. 
preliminaries: 
 Saliency map explanations. Let a classification model with parameters w be f (x, w) : R n → [0, 1] C , and f c (x, w) is the probability of class c for the input x. Denote a saliency map explanation [1] for x concerning class c as I(x, c; f ) = ∇ x f c (x, w). Since f is fixed for explanations, we omit w and fix c to the predicted class. We denote I(x, c; f ) by I(x), and the i-th feature's importance score, e.g., the i-th entry of I(x), by I i (x). The theoretical analysis following will mainly based on saliency explanations, and more explanation methods, such as Grad× Inp, SmoothGrad [75] , and IG [77] , are studied in Sec. 6 and Appendix A.1.2.Threat model. The adversary solves the following problem to find the optimal perturbation δ * to distort the explanations without changing the predictions [17] :δ * = arg max δ is the perturbation whose ℓ 2 norm is not larger than a given budget ϵ. 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.Quantify the gap. Given a model f and the associated original explanation I(x) with respect to an input x ∈ R n , we denote the gap between the i-th and j-th features' importance by h(x, i, j) = I i (x) -I j (x). Clearly, h(x, i, j) > 0 if and only if the i-th feature has a more positive contribution to the prediction than the j-th feature. The magnitude of h reflects the disparity in their contributions.Although the feature importance order varies across different x, for notation brevity, we label the features in a descending order such that h(x, i, j) > 0, ∀i < j, holds for any original input x. This assumption will not affect the following analysis.Pairwise thickness. The adversary in Eq. ( 1) searches for a perturbed input x ′ to flip the ranking between features i and j so that h(x ′ , i, j) < 0 for some i < j. A simple evaluation metric, such as θ = 1[h(x ′ , i, j) ≥ 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 is 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 ∈ X and a distribution D of perturbed input x ′ ∼ D, the pairwise ranking thickness of the pair of features (i, j) isEQUATIONThe integration computes the average gap between two features from x to 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 a model's prediction robustness by the distance between two level sets.Top-k thickness. Existing works in general robust ranking [105] propose maintaining the ranking between every two entities (features). However, as shown in Fig. 1 , only the top-k important features in I(x) attract human perception the most, and will be delivered to end-users. Thus, we focus on the relative ranking between a top-k salient feature and any other non-salient one. Definition 4.2 (Top-k ranking thickness). Given a model f , an input x ∈ X , and a distribution D of x ′ ∼ D, the ranking thickness of the top-k features isEQUATIONVariants and discussions. We consider and discuss the following three major variants of thickness.• One variant of thickness in Eq. ( 2) is in a probability version:Θ Pr (f, x, D, i, j) def = E x ′ ∼D 1 0 1[h(x(t), i, j) ≥ 0]dt .However, the inherent non-differentiability of the indicator function hinders effective analysis and optimization of thickness. One may replace it with a sigmoid to alleviate the non-differentiability issue. Yet, the use of a sigmoid can potentially lead to vanishing gradient problems. • By considering the relative positions of the top-k features, one can define an average precision@k like thicknessΘ ap def = 1 K K k=1 Θ(f, x, D, k), or a discounted cumulative gain [33] like thickness Θ dcg def = k i=1 n j=k+1Θ(f,x,D,i,j) log(j-i+1) . Other variants for specific properties or purposes can be derived similarly, and we will study these variants deeply in future work.• Many non-salient features are less likely to be confused with the top-k salient features (see Fig. 8 ), and treating them equally may complicate optimization. Thus, one may approximate the top-k thickness by k ′ pairs of featuresk ′ i=1 h(x, k -i, k +i), which selects k ′ distinct pairs with minimal h(x, i, j). We include the case when k ′ = k denoted with the suffix "-mm" in the experiments.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 Θ(f, x, D, k) as a regularizer during training:EQUATIONwhere L cls is the classification loss. However, direct optimization of Θ requires M 1 × M 2 × 2 backward propagations per training sample. M 1 is the number of x ′ sampled from D; M 2 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 2 backward propagations each time.Definition 4.3 (Locally Lipschitz continuity). A function f is L-locally Lipschitz continuous if ∥f (x) -f (x ′ )∥ 2 ≤ L∥x -x ′ ∥ 2 holds for all x ′ ∈ B 2 (x, ϵ) = {x ′ ∈ R n : ∥x -x ′ ∥ 2 ≤ ϵ}. Proposition 4.4.(Bounds of thickness) Given an L-locally Lipschitz model f , for some L > 0, pairwise ranking thickness Θ(f, x, D, i, j) is bounded byEQUATIONwhere H i (x) is the derivative of I i (x) with respect to x, andL i = max x ′ ∈B2(x,ϵ) ∥H i (x ′ )∥ 2 .Noticing lim ∥H(x)∥2→0 Θ(f, x, D, i, j) = h(x, i, j), the objective of the proposed R2ET, Robust Ranking Explanation via Thickness, is to maximize the gap and minimize Hessian norm:EQUATIONwhere λ 1 , λ 2 ≥ 0. R2ET with λ 1 = 0 recovers Hessian norm minimization for smooth curvature [17] . The difference between R2ET in Eq. ( 6) and vanilla model are two regularizers. h(x, i, j) = I i (x) -I j (x) can be calculated by one time backward propagation over I(x), and the summations are done by assigning different weights to I i (x), e.g., (n -k) for i <= k, and -k for i > k. ∥H(x)∥ 2 is estimated by the finite difference (calculating the difference of the gradient of I(x) and I(x + δ)), which costs two times backward propagation [52] . Thus, R2ET is at an extra cost of 2 times backward propagation. For comparison, AT (in PGD-style) searches the adversarial samples by M 2 (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 is 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 δ with ∥δ∥ 2 ≤ min {i,j} h(x,i,j)max x ′ ∥Hi(x ′ )-Hj (x ′ )∥2 , it holds 1[h(x, i, j) > 0] = 1[h(x + δ, i, j) > 0]for all (i, j) pair, that is all the feature rankings do not change.Connection to adversarial training (AT). Prop. 4.6 implies that R2ET shares the same goal as AT but employs regularizers to avoid costly computations. The proof in Appendix A.3 is based on [94] .Proposition 4.6. The optimization problem in Eq. ( 6) is equivalent to the following min-max problem:EQUATIONwhere δ i,j ∈ R n is a perturbation to x targeting at the (i, j) pair of features. M is the feasible set of perturbations where each δ i,j is independent of each other, with ∥ i,j δ i,j ∥ ≤ ϵ.Connection to constrained optimization. Prop. 4.7 shows that R2ET aims to keep the feature in the "correct" positions, e.g., l i I i ≥ G i , for the local vicinity of original inputs, thus promoting robustness. First, Eq. ( 6) can be considered a Lagrange function for the constrained problem in Eq. ( 8):EQUATIONwhere G i ≥ 0 is a predefined margin. l i = (n -k) for i ≤ k, and l i = -k otherwise, which labels features at the top as positive and those at the bottom as negative. The proof is based on [34] .Proposition 4.7. The optimization problem in Eq. ( 8) is equivalent to the following problem:EQUATION5 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 multiobjective optimization. Threat model. The attacker aims to swap the ranking of any pair of a salient feature i and a non-salient feature j, so that the gap h(x, i, j) < 0, while does not change the input x and the predictions f (x) significantly for stealthiness. We assume that the attacker has access to the parameters and architecture of the model f to conduct gradient-based white-box attacks.Optimization problem for the attack. Each h(x, i, j) 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 to 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 a successful attack (equivalently, explanation robustness) by an upper bound on 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 f (x) are. Formally, for any given initial input x (0) ((p) in the superscript means the p-th attacking iteration), the attacker needs to iteratively manipulate x to reduce the gaps h(x, i, j) for all i ∈ {1, . . . , k} and j ∈ {k + 1, . . . , n} packed in a vector objective function:EQUATIONwhere h ℓ (x) def = h(x, i, j), with ℓ = 1, . . . , m indexing the m pairs of (i, j).Comments: (i) The scalar function i j h(x, i, j) is unsuitable for theoretical analyses, since there can be no 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 a pessimistic bound for defenders (and an optimistic bound for attackers). (ii) We could adopt the Pareto criticality for convergence analysis [21] , but a Pareto critical point indicates that no critical direction (moving in which does not violate the constraint) leads to a joint descent in all objectives, rather than that an objective function h ℓ has been sufficiently minimized. (iii) Different from the unconstrained case in [19] , we constrain the amount of changes in x and f (x).We propose a trust-region method, Algorithm 1, to solve MOO-Attack (A.4 for more details). First, we define the merit function ϕ ℓ that combines the ℓ-th objective and the constraint in Eq. ( 10):EQUATION) As an approximating model for the trust-region method, the linearization of ϕ(x, t) isl ϕ ℓ (x, t, d) = ∥f (x) + J(x) ⊤ d∥ + |h ℓ (x) + g ℓ (x) ⊤ d -t|,where J(x) is the Jacobian of f at x and g ℓ (x) is the gradient of h ℓ . The maximal reduction in l ϕ ℓ (x, t, 0) within a radius of ∆ > 0 isEQUATION)x is called a critical (approximately critical) point of ϕ ℓ when χ ℓ (x, t) = 0 (or ≤ ϵ).Algorithm 1 Attacking a pair of features 1: Input: target model f , input x, explanation I(x), trust-region method parameters 0 < γ, η < 1.EQUATIONℓ = ∥f (x (p) )∥ + h ℓ (x (p) ) -ϵ (p) . 3: while min 1≤ℓ≤m χ ℓ (x (p) , t (p) ) ≥ ϵ do 4:Solve TR-MOO(x (p) , ∆ (p) ) to obtain a joint descent direction d (p) for all l ϕ ℓ . The core of Algorithm 1 is TR-MOO(x, ∆), whose optimal solution provides a descent direction d for all linearized merit functions l ϕ ℓ (not h ℓ or ϕ ℓ ):TR-MOO(x, ∆) min α,d α s.t. l ϕ ℓ (x, t, d) ≤ α, ∀1 ≤ ℓ ≤ m, ∥d∥ ≤ ∆.where α is the minimal amount of descent and ∆ is the current radius of search for d.Different from the local convergence results [20] , we provide a global rate of convergence for Algorithm 1 to justify thickness maximization in Theorem 5.1. Specifically, it implies that increasing gaps between salient and non-salient features tend to result in larger h up -h low , which makes it harder for attackers to alter the rankings, leading to stronger explanation robustness. Theorem 5.1. Suppose that f (x) and h ℓ (x) are continuously differentiable and h ℓ is bounded. Then Algorithm 1 generates an ϵ-first-order critical point for problem Eq. ( 10) in at most(h up -h low ) κ ϵ 2iterations, where κ is a constant independent of ϵ but depending on γ and η in Algorithm 1,h up def = max ℓ {max x h 1 (x), . . . , max x h m (x)}, and h low def = min ℓ {min x h 1 (x), . . . , min x h m (x)}.Statistical stability of explanations. We use McDairmid's inequality for dependent random variables and the covering number of the space F of saliency maps I in Theorem 5.2. The theorem justifies maximizing the gap by showing a bound on how likely a model can rank some non-salient features higher than some salient features due to perturbation to x. Specifically, for a consistent empirical risk level R emp 0,1,u , a larger gap corresponds to a larger u, which leads to a smaller covering number N (F, ϵu 8 ). It indicates a reduced probability of high true risk R true 0,1 , 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 for relevant definitions and details. Theorem 5.2. Given model f , input x, surrogate loss ϕ u , and a constant ϵ > 0, for arbitrary saliency map I ∈ F and any distribution D surrounding x that preserves the salient features in x, where N is the covering number of the space F with radius ϵu 8 [102] . χ is the chromatic number of a dependency graph of all pairs of salient and non-salient features [81] for McDairmid's inequality.EQUATION 
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 [54] , and two image datasets, CIFAR-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), 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 [49] .Evaluation metrics. Precision@k (P@k) [88] is used to quantify the similarity between explanations before and after attacks. We adopt three faithfulness metrics [72, 15] in Appendix B.2.6 to show that 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) [77] , and concept-based explanation methods (on ROCT datasets).We conduct two attacks in the PGD manner [50] : Explanation Ranking attack (ERAttack) and MSE attack. ERAttack minimizes k i=1 n j=k+1 h(x ′ , i, j) to manipulate the ranking of features in explanation I(x), and MSE attack maximizes the MSE (i.e., ℓ 2 distance) between I(x) and I(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; ρ) = 1 ρ ln(1 + e ρx ). Est-H [17] and Exact-H consider the estimated (by the finite difference [52] ) and 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 min f L cls (f ; x + δ * , y), where δ * = arg max δ - k i=1 n j=k+1 h(x + δ, i, j). • Variants of R2ET: R2ET-mm selects multiple (k) distinct i, j with minimal h(x, i, j) as discussed in Sec. 4.1.R2ET \H and R2ET-mm \H are the ablation variants of R2ET and R2ET-mm, respectively, without optimizing the Hessian-related term in Eq. ( 6) (λ 2 = 0). Est-H can be considered an ablation variant of R2ET (λ 1 = 0).Attackability of ranking-based explanation. Table 1 reports the explanation robustness of different models against ERAttack and MSE attacks on all datasets. More than 50% of models achieve at least 90% P@k 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 a false (over-optimistic) impression of explanation robustness. In contrast, ERAttack can displace more salient features from the top-k positions for most models and datasets, leading to 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 to 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 in 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 R2ET \H , as an ablation version of R2ET, outperforms R2ET on Adult and Bank. The reason is that R2ET \H has the highest thickness on these datasets (see Table 3 in Sec. 6.3). ( 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, solely minimizing Hessian-related terms may marginally contribute to the ranking robustness. (4) We do not compare with many AT baselines [74, 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-based 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 a ResNet [27] on ROCT. To this end, the most stimulated neurons must be stable under perturbations. We define I i as the activation map of the i-th penultimate neuron, and derive the objective analogous to Eq. ( 6). Empirical results in Table 1 (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 achieve the highest P@k.(2) Applying Grad to R2ETs usually results in greater robustness than adopting SG/IG to baselines. For example in MNIST, R2ET with Grad attains a P@k of 85%, while applying SG to the baselines (except Est-H) fails to exceed a P@k of 70%. (3) R2ET can generalize and transfer the robustness to explanation methods divergent from those utilized during training.Assessing model vulnerability: critical role of thickness. As discussed in Section 5, 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. 2 , each dot in subplots represents an individual sample x. The left subplot demonstrates a 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 a more precise metric of explanation ranking robustness.To understand why R2ET does not always outperform other models, Table 3 juxtaposes P@k with dataset-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 of the method employed, aligning with Theorem 5.2.Optimal Method Selection. Thickness has proven its efficacy as an indicator for evaluating explanation ranking robustness, rendering it an apt criterion for method selection. Table 1 indicates a more straightforward way to pick a model: deploy R2ET \H (and R2ET-mm \H ) 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, as it complicates the manipulation of feature magnitude. For visual evaluation, Fig. 3 displays models' saliency maps on 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, exemplified by the ship. Vanilla and WD exhibit inferior P@k scores, whereas R2ET and R2ET-mm achieve around 90% P@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 to 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 to subtle perturbations raises confusion and mistrust. Fig. 5 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 thickness and a min-max optimization problem, and a global convergence rate of a constrained multi-objective attacking algorithm against the thickness. The theory leads to an efficient training algorithm R2ET. On 8 datasets (vectors, images, and graphs), we compared 7 state-of-the-art baselines and 3 variants of R2ET, and consistently confirmed that explanation ranking thickness is a 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 it from outperforming others all the time. Besides, the theoretical analysis and discussions are based on gradient-based explanation methods. In the future, we plan to further apply R2ET to a broader spectrum of explanation methods. We also plan to 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.Appendix A provides theoretical proofs for the propositions and lemmas. Appendix B reports experimental settings and results. Appendix C shows relevant works concerning explanation robustness, ranking robustness, and top-k intersection. 
 
 Appendix: Proofs concerning Prop. 4.4, 4.5, and 4.6 are in A.1, A.2 and A.3, respectively. As the supplementary of Sec. 5, theoretical analyses on numerical and statistical robustness are in A.4 and A.5, respectively.A.1 Bounds of Ranking Explanation ThicknessWe denote x as the target sample, ∥δ∥ 2 ≤ ϵ as the perturbation, x ′ = x + δ as the perturbed input, andx(t) = (1 -t)x + tx ′ , t ∈ [0, 1].Here, I(x) is not specifically defined as ∇ x f (x), but an arbitrary explanation method. Proposition A.1. [Bounds of ranking explanation thickness] Given a L-locally Lipschitz modelf (x), for some L ≥ ∥x-x * ∥2•maxi Li 2 where x * = arg max x ′ ∈B2(x,ϵ) ∥I(x)-I(x ′ )∥2 ∥x-x ′ ∥, the ranking explanation thickness for the (i, j) feature pair of a target x is bounded byh(x, i, j) -ϵ * 1 2 ∥∇ x I i (x) -∇ x I j (x)∥ 2 ≤ E x ′ 1 0 h(x(t), i, j)dt ≤ h(x, i, j) + ϵ * (L i + L j ),where H i (x) is the i-th column of Hessian matrix of f with respect to the input x, andL i = max x ′ ∈B2(x,ϵ) ∥∇ x I i (x ′ )∥ 2 .Lower bound.Proof. We start from the definition of ranking thickness between (i, j)-th features of x in Eq. ( 2).EQUATIONWe approximate the gradient at intermediate point x + tδ by the Taylor Expansion on line-3. Then the minimum is found with δ * = arg min ∥δ∥≤ϵ1 2 δ ⊤ (∇ x I i (x) -∇ x I j (x)) = -ϵ ∇xIi(x)-∇xIj (x) ∥∇xIi(x)-∇xIj (x)∥on line-5.Upper bound. We introduce two lemmas from [57] and [88] before the proof.EQUATION)where1 p + 1 q = 1, 1 ≤ p, q ≤ ∞. Lemma A.3. If a function f (x) is L-locally Lipschitz continuous in B 2 (x, ϵ), then I(x) is K-locally Lipschitz as well, where K ≤ 2L ∥x-x * ∥ and x * = arg max x ′ ∈B2(x,ϵ) ∥I(x)-I(x ′ )∥2 ∥x-x ′ ∥2.Proof. Given an L-locally Lipschitz f (x), Lemma A.3 further indicates that I i (x) : R n → R is locally Lipschitz as well. By adopting p = q = 2 on Lemma A.2, the Lipschitz constant is specified byEQUATION)Based on first mean value theorem, there exists x ′ 0 within the line segment x and x ′ such that h(x ′ 0 , i, j) =1 0 h(x(t), i, j)dt on line-2. The Lipschitz constant L of f satisfies L ≥ ∥x-x * ∥ 2 * max i L i = ∥x-x * ∥ 2 * max i max x ′ ∈B2(x,ϵ) ∥∇ x I i (x ′ )∥ 2 .Notice that the inequality in Eq. ( 13) holds for arbitrary explanation methods. Here, we consider different explanation methods (Grad, Grad× Inp, SG, and IG) to specify I(x) and corresponding bounds. We leave DeepLIFT [73] and LRP [6] to further study, and we do not consider Grad-CAM [71] and Guided Backpropagation [76] since they are designed only for specific networks.Grad. When adopting Grad as explanation method, where I(x) = ∇f (x) and ∇ x I(x) = H(x), it recovers Prop. 4.4.EQUATIONwhere H(x) is the Hessian matrix, and specificallyL i = max x ′ ∈B2(x,ϵ) ∥H i (x ′ )∥ 2 .SmoothGrad. When adopting SmoothGrad, whereI(x) = 1 M m ∇f (x + β m ) and β m ∼ N (0, σ 2 I), we have ∇ x I(x) = 1 M m H(x + β m ).We derive the lower bounds analogy to the derivations on Eq. ( 13):EQUATIONNote: whenM is large enough, 1 M m β m → 0 since β m is drawn from N (0, σ 2 I).Grad × Inp. When adopting Grad × Inp, where I(x) = ∇f (x) ⊙ x, we have ∇ x I(x) = diag((∇f ) 1 , . . . , (∇f ) n ) + H(x). The lower bounds derived from Eq. ( 13) can be further specified:EQUATIONNote: x i is the i-th feature of the input x, and ϵ ≪ x i since the perturbation is supposed to be neglectable.Integrated Grad. When adopting Integrated Grad, I(x) = (x -x 0 ) ⊙ 1 α=0 ∇f (x 0 + α(x -x 0 ))dα. By setting x 0 = 0, we have I(x) = x ⊙ 1 α=0 ∇f (αx)dα. Similar to the Grad × Inp case, the lower bound of IG can be derived:EQUATIONSince the inequalities in Eq. ( 13) and ( 15) hold for any choice of x ′ ∈ B 2 (x, ϵ) with a specific ϵ. Thus,h(x, i, j) -ϵ * 1 2 ∥∇ x I i (x) -∇ x I j (x)∥ 2 ≤ E x ′ 1 0 h(x(t), i, j)dt ≤ h(x, i, j) + ϵ * (L i + L j ).Furthermore, the bounds of the top-k ranking thickness hold for any choice of comparison pairs:EQUATIONInstantiation for the top-k thickness can be derived similarly to those in A.1.2.Proposition A.4. For all δ with ∥δ∥ 2 ≤ min {i,j} h(x,i,j)max x ′ ∥Hi(x ′ )-Hj (x ′ )∥2 , it holds 1[h(x, i, j) > 0] = 1[h(x + δ, i, j) > 0]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 + δ, i, j) < 0, e.g., I i (x + δ) -I j (x + δ) < 0, given h(x, i, j) > 0. The same proof can be done for h(x, i, j) < 0. Based on the calculus, it holds thatI i (x + δ) = I i (x) + 1 0 ⟨H i (x + tδ), δ⟩dt, I j (x + δ) = I j (x) + 1 0 ⟨H j (x + tδ), δ⟩dt.To achieve I i (x + δ) -I j (x + δ) < 0,I i (x) + 1 0 ⟨H i (x + tδ), δ⟩dt -I j (x) + 1 0 ⟨H j (x + tδ), δ⟩dt < 0,which implies thatI i (x) -I j (x) < 1 0 ⟨H j (x + tδ), δ⟩dt - 1 0 ⟨H i (x + tδ), δ⟩dt.Based on the Hölder's inequality,I i (x) -I j (x) < ∥δ∥ 2 1 0 ∥H i (x + tδ) -H j (x + tδ)∥ 2 dt,Thus, the minimal budget required to flip the ranking between the feature pair (i, j) is∥δ∥ 2 > I i (x) -I j (x) 1 0 ∥H i (x + tδ) -H j (x + tδ)∥ 2 dt , > I i (x) -I j (x) max x ′ ∈B2(x ′ ,ϵ) ∥H i (x ′ ) -H j (x ′ )∥ 2 .Thus, the minimal budget required to flip any ranking is min {i,j} h(x,i,j)max x ′ ∥Hi(x ′ )-Hj (x ′ )∥2 .Following Sec. 3, given a model f : R n → [0, 1] C and an input x, I(x, c; f ) = ∇ x f c (x) is the explanation and I i (x) is the score for the i-th feature. We assume that I(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 a model by a min-max game in Sec. 4.2 is:EQUATION)We explicitly show the weight of each I i , which is l i = (n -k) if i ≤ k, and l i = -k, otherwise, and rewrite AT's goal: EQUATIONEQUATIONwhere δ i is specific to the i-th feature of input x.We will prove the equivalence between R2ET in Eq. ( 6) and AT in Eq. ( 21) by proving that min (δ1,...,δn)∈M n i=1EQUATIONis equivalent toEQUATION)Proof. Given an ϵ norm ball M 0 def = {δ ∈ R n : ∥δ∥ ≤ ϵ}, we consider a perturbation set M where perturbations on each feature are independent, but the aggregation of perturbations is controlled. Formally, M satisfies M -⊆ M ⊆ M + , where M -def = ∪ n i=1 M - i , where M - i def = {(δ 1 , . . . , δ n )|δ i ∈ M 0 ; δ t̸ =i = 0}; M + def = {(α 1 δ 1 , . . . , α n δ n )| n i=1 α i = 1; α i ≥ 0, δ i ∈ M 0 , i = 1, . . . ,EQUATIONWe will prove that ν is not smaller than the rightmost term and not larger than the leftmost term in Eq. ( 26).To prove ν ≥ min (δ1,...,δn)∈M -n i=1 l i I i (x + δ i ). min (δ1,...,δn)∈M - n i=1l i I i (x + δ i ) ≤ min (δ1,...,δn)∈M - i n i=1 l i I i (x + δ i ) = n i=1 l i I i (x) + n i=1 min (δ1,...,δn)∈M - i l i H i (x) ⊤ δ i = n i=1 l i I i (x) + min t∈{1,...,n} min δt∈M0 l t H t (x) ⊤ δ t = n i=1 l i I i (x) -ϵ max t∈{1,...,n} l t ∥H t (x)∥ 2 .The inequality on line-2 holds since M - i ⊆ M -. The equality on line-4 holds due to the definition of M - i , where only one δ t of (δ 1 , . . . , δ n ) is from M 0 and the rest are all zeros. The equality on line-5 holds by picking δ t = -ϵ Ht(x) ∥Ht(x)∥ . To prove ν ≤ min (δ1,...,δn)∈M + n i=1 l i I i (x + δ i ). min (δ1,...,δn)∈M + n i=1l i I i (x + δ i ) = min i αi=1,αi≥0, δi∈M0 n i=1 l i α i I i (x + δi ) = n i=1 l i I i (x) + min i αi=1,αi≥0 n i=1 α i min δi∈M0 l i H i (x) ⊤ δ i = n i=1 l i I i (x) + min t∈{1,...,n} min δt∈M0 l t H t (x) ⊤ δ t = n i=1 l i I i (x) -ϵ max t∈{1,...,n} l t ∥H t (x)∥ 2 .We present an algorithm that will terminate in finite iterations, and flip the first pair of salient and non-salient features, or claim a failed attack. The algorithm is based on a trust-region method designed for single non-convex but smooth objective with nonlinear and non-convex equality constraints [9] .Let the output vector f (x) = [f 1 (x), . . . , f C (x)]. Given n features and top-k salient features, there are m = k × (n -k) objectives that can be indexed by subscripts ℓ so that the objective vector becomes [h 1 (x), . . . , h ℓ (x), . . . , h m (x)]. Let ∥∥ be a convex norm with Lipschitz constant 1.Input: initial input x, target model f , current explanation I(x), tolerance ϵ > 0, trust-region method parameters 1 > η > 0 and 1 > γ > 0.Set k = 1, x (p) = x, t (p) ℓ = ∥f (x (p) )∥ + h ℓ (x (p) ) -ϵ (p)for each objective h ℓ . while min 1≤ℓ≤m χ ℓ (x (p) , t (p) ) ≥ ϵ do Solve TR-MOO(x (p) , ∆ (p) ) to obtain a joint descent direction d (p) for all linearized merit functions l ϕ ℓ .EQUATIONℓ ,0)-l ϕ ℓ (x (p) ,t(p) ℓ ,d (p) )for each ℓ = 1, . . . , m.EQUATIONℓ ) + ϕ ℓ (x (p+1) , t (p) ℓ ). end if else x (p+1) = x (p) . ∆ (p+1) = γ∆ (p) . t (p+1) ℓ = t (p)ℓ for ℓ = 1, . . . , m. end if end while Since we are working with numerical algorithms, an approximately feasible set will be appropriate. Define the following constrained MOO problem min x [h 1 (x), . . . , h ℓ (x), . . . , h m (x)],s.t. ∥f (x) -f (x (0) )∥ ≤ ϵ f , ∥x -x (0) ∥ 2 ≤ ϵ x (27)In the sequel, the two constraints can be combined such thatEQUATIONfor some ϵ > 0, with f (x) = [f (x), x]. Therefore, we let f denote f to simplify the notation. Define the domainEQUATIONAssumption A.1: The constraint function f (x) is continuously differentiable on the domain R n , and the objective functions h ℓ , ℓ = 1, . . . , m, are continuously differentiable in the setEQUATIONwhere δ > 1 is a constant, ∆ (1) is the initial radius argument for the trust-region method for multiobjective optimization TR-MOO(x, ∆) to be defined below, and B(0, δ∆ (1) ) is an open ball centered at 0 of radius δ∆ (1) .Assumption A.2: The objective functions h ℓ , ℓ = 1, . . . , m are bounded in the set C 1 . Specifically,EQUATIONEQUATIONWe give an attacking algorithm MOO-attack that can either find the first feature pair to flip in an explanation, or claim that it is impossible to flip any feature pair. The superscript (p), p = 1, 2, . . . indicates the number of iterations.The attacking algorithm may not be able to flip any pair of features when min 1≤ℓ≤m χ ℓ (x (p) , t (p) ) < ϵ, but there can be other objective functions that still have χ ℓ (x (p) , t (p) ) ≥ ϵ and there is a chance to flip the corresponding pairs of features. We will remove any objective function h ℓ with χ ℓ (x (p) , t (p) ) < ϵ 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 [9] to the above multi-objective optimization algorithm to show a global convergence rate for the attacker.Lemma A.5. Suppose that assumption A.1 holds. If x (p) ∈ C 1 , then for each linearized merit function l ϕ ℓ l ϕ ℓ (x (p) , tEQUATIONLemma A.5 shows sufficient descent in the linearized merit functions in the direction d (p) . The proof can be found in Lemma 2.1 in [9] . Lemma A.6. Suppose that assumption A.1 holds. In each iteration for k ≥ 1 in Algorithm 1, the following properties hold:EQUATIONEQUATIONEQUATIONEQUATIONLemma A.6 shows 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 (p) remains in the approximate feasible set C 1 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 h ℓ will chase the corresponding target t (p) ℓ over the iterations, so that if t(p)ℓ can be shown to be decreasing sufficiently fast, we can show the convergence of h ℓ . Note that different targets t (p) ℓ will move at different speeds, as they are updated independently in the algorithm. Also, a target is not guaranteed to be reduced below zero for h ℓ to become negative and the ℓ-th pair of features will be flipped.Lemma A.7. Suppose that assumptions A.1 and A.2 hold. Then with min ℓ χ ℓ (x (p) , t (p) ) ≥ ϵ andEQUATIONthe condition min ℓ ρ (p) ℓ > η in Algorithm 1 will hold true and ∆ (p+1) = ∆ (p) . Furthermore, with min ℓ χ ℓ (x (p) , t (p) ) ≥ ϵ, we have, for all p ≥ 1,EQUATIONLemma A.7 shows that when the radius ∆ (p) used in TR-MOO(x (p) , ∆ (p) ) is small enough, the radius won't be further reduced. Together with Lemma A.5, the linearized merit functions are reduced sufficiently per iteration. The proof is a modification to the proof of Lemma 3.2 in [9] , with the derivation done for each of the objective functions h ℓ to guarantee sufficient descent in all merit functions. An interesting observation is that the search radius ∆ (p) is restricted by the objective that has the most rapid change in its gradient g ℓ (characterized by L g ℓ ). If all objectives are smooth (with small L g ℓ ), 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 O(⌈| log(ϵ)|⌉) number of times that ∆ (p) will be reduced by the factor of γ.Lemma A.8 characterizes the times to reduce the search radius. It is because, starting from ∆ (1) , once∆ (p) falls below min ℓ (1-η)ϵ Lg ℓ + 1 2 L Jat iteration p, there will be no more reduction in future iterations.Lemma A.9. Suppose that assumptions A. are at least min ∆ (1) , minEQUATION)Lemma A.9 shows a sufficient reduction in the merit functions and the targets. The proof is to use the condition that ρ (p) ℓ > η for all ℓ = 1, . . . , m, Eq. ( 33), the condition that min 1≤ℓ≤m χ ℓ (x (p) , t (p) ) ≥ ϵ, and Eq. ( 39).Lastly, we present the main global convergence results. Theorem A.10. Suppose assumptions A.1-A.2 hold. Then Algorithm 2 generates an ϵ-first-order critical point for problem Eq. ( 27) in at most(h up -h low ) κ ϵ 2 (41)iterations of the while loop in the algorithm, where κ is a constant independent of ϵ but depending on γ, η, L h ℓ , and L J .The proof hinge on the following inequalityEQUATIONEQUATION≤ t(1)EQUATIONEQUATION)where i p is the number of iterations between 1 and p where min ℓ ρEQUATIONTherefore,EQUATION)Since O(⌈| log(ϵ)|⌉) grows slower than 1/ϵ 2 , the overall number of iterations is in the order of (h up -h low ) κ ϵ 2 .We will use 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 to random sampling of x 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 a concentration inequality for ranking errors of a fixed feature ranking function based on the salient score function I(x). Then we will adopt the standard covering number argument as in [2, 68] to 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 risksEQUATIONEQUATIONTo relate the risks to the thickness, consider the loss ϕ u (z), u > 0, which is similar to the hinge lossEQUATIONBased on ϕ u , we define the surrogate true and empirical risksEQUATIONEQUATIONLastly, an upper bound of ϕ u (z) can be defined as a large-margin 0-1 loss: if z ≥ u, the loss is 0, and otherwise, the loss is 1. The corresponding empirical riskR emp 0,1,u (I, x) = 1 m k i=1 n j=1 1[I i (x) < I j (x) + u]counts how many pairs of salient and non-salient features that are the salient feature is u less salient than the non-salient feature according to I.ϕ,u (I, x) for a specific I. As we randomly sample x ′ from D, the terms I i (x ′ ) and the associated 0-1 and ϕ u 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 R emp ϕ,u are not independent. The saliency scores of different features are dependent since they are function of the same model f , the input x, and the mechanism that calculate the gradients for I. In [81] , the authors generalized the inequality to dependent variables, and we adopt their conclusion as follows: Lemma A.11. Given prediction model f , saliency map I, input x, distribution D surrounding x, surrogate loss ϕ u , and a constant ϵ > 0, we haveEQUATION)where χ is the chromatic number of the dependency graph of the pairs of random variables (I i , I j ) for any 1 ≤ i ≤ k and k + 1 ≤ j ≤ n.Comments:• The above dependency graph describes when two pairs of random variables (I i , I j ) (regarded as a random vector) and (I i ′ , I j ′ ) (regarded as another random vector) are dependent. In particular, the two nodes (I i , I j ) and (I i ′ , I j ′ ) 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 1 plus the maximum degree of nodes on the dependency graph, which is 1+m. In the worst case, the bounds in Eq. ( 54) approximates 2 exp(-2ϵ 2 ) as m becomes sufficiently large.Uniform convergence of the class of saliency score functions. Since R2ET searches the optimal I function from a class F of such functions given f , I, x, and D, u > 0, with the preference over I that has a large gap u so that I i (x) > I j (x) + u for salient feature i and non-salient feature j. Theorem A.12. Given prediction model f , input x, surrogate loss ϕ u , and a constant ϵ > 0, for arbitrary saliency map I ∈ F and any distribution D surrounding x that preserves the salient features in x, we haveEQUATION)where N (F, ϵu 8 ) is the covering number of the functional space F with radius ϵu 8 [102] .Comments:• The proof is standard and a similar proof can be found in [68] .• With a larger u > 0, the empirical risk R emp 0,1,u (I, 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 N (F, ϵu 8 ) will decrease as u increases as a larger radius can cover more I ∈ 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 x to x ′ that has the same saliency features, the true risk (representing how bad the true explanations can be perturbed) will be low.We provide detailed experimental settings in B. 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 a ratio of 70 : 15 : 15, respectively.We follow [11] to binarize and map the original inputs mixing with strings and numbers to 28-dim, 18-dim, and 16-dim feature spaces, respectively.Image data. We adopt ResNet18 [27] for CIFAR-10 [36] . As for MNIST [40] , we adopt an SN, where the embedding model is a classic CNN, consisting of two convolutional layers with 3*3 kernels followed by max-pooling and three fully-connected layers. Then We use cosine similarity as the similarity metric, and classifier is a 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.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 a new sample with those in the database), each validation (testing) pair consists of a training graph and a 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 to a 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 a single-layer linear model taking the outputs from the corresponding embedding models as inputs.We train all the models from scratch, except that ResNet is retrained from the Vanilla model. The model with a 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 a 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. satisfactory performance (AUC), its explanation ranking is a 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 (hyper)-parameters adopted in the experiments. Attacks are conducted in a PGD-style [50] , and the infinity norm of the perturbations in each iteration is restricted to no more than 5 for images and 0.2 for graphs. For R2ET, λ 1 and λ 2 are selected as the same as the best λ for R2ET \H and est-H, respectively. Alternatively, we simply set λ 1 = λ 2 = λ, and λ can be drawn from {0.01, 0.When adopting SmoothGrad (SG) [75] as explanation method, whereI SG (x) = 1 M M m I(x + β m ) and β m ∼ N (0, σ 2 I), Mis set 50 for all datasets, and σ 2 = 0.5, 25.5 2 , 0.01 for tabular, images, and graphs, respectively. When adopting Integrated Gradients (IG) [77] , whereI IG (x) = (x -x 0 ) ⊙ 1 α=0 ∇ x f (x 0 + α(x -x 0 ))dα.In practice, we set x 0 = 0, and approximate the integration by interpolating 100 samples between x 0 and x.Running environment. We mainly conduct experiments for three tabular data and CIFAR-10 on the following two machines. Both come with a 16-core Intel Xeon processor and four TITAN X 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 Xeon processors and five GeForce RTX 2080 Ti GPUs, which installs 18.04.3 Ubuntu with 3.9.5 Python and 1.9.1 PyTorch.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] .We adopt precision@k to evaluate the explanation robustness by quantifying the similarity between I(x) and I(x ′ ); AUCs and sensitivity to evaluate the model's classification performance (see B.2.3 and B.2.4); and DFFOT, COMP, and SUFF to evaluate the explanation faithfulness (see B.2.6).• Precision@k (P@k). It is widely used to evaluate the robustness of explanations [23] . Formally,P@k(I(x), I(x ′ )) = |I(x) [k] ∩ I(x ′ ) [k] | k ,where I(x) [k] is the set of the k most important features of the explanation I(x). | • | counts the number of elements.• 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 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 a more faithful explanation.DFFOT = min k k n , s.t. arg max c f c (x) ̸ = arg max c f c (x [\k] ),where n is the number of features, and x [\k] is the perturbed input whose top-k important features are removed. • Comprehensiveness (COMP) [15] measures the changes of predictions before and after removing the most important features. A higher COMP means a more faithful explanation.COMP = 1 ∥K∥ k∈K |f c (x) -f c (x [\k] )|,where K is {1, . . . , n} for tabular data, and {1% * n, 5% * n, 10% * n, 20% * n, 50% * n} for images and graphs. The same setting of K is adopted for SUFF.• Sufficiency (SUFF) [15] measures the change of predictions if only the important tokens are preserved. A lower SUFF means a more faithful explanation.SUFF = 1 ∥K∥ k∈K |f c (x) -f c (x [k] )|,where x [k] is the perturbed input with only top-k important features.An SN predicts whether two samples, x s and x t , 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 s , x t ), is f SN 1 (x s , x t ; w) = sim(emb(x s ; w 0 ), emb(x t ; w 0 ); w 1 ), (56) and f SN 0 = 1 -f SN 1 for class 0. sim(•, •; w 1 ) is a similarity function, such as the cosine similarity, and emb(•; w 0 ) is an embedding network, such as GNN. w = {w 0 , w 1 } is the SN's parameter set.The ground truth used in SN is y st = 1[y s = y t ], where y s is the label of x s .To predict a single input, one can further train a classifier f CL based on the embedding part of the SN. For example, f CL (x) = cls(emb(x; w ′ 0 ); w 2 ), where w ′ 0 can be the same as or retrained from w 0 in Eq. ( 56), and cls(•; w 2 ) is a classifier such as a linear model with the parameter set w 2 .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. 4 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 or minimal of a few Gaussian samples to mimic random noise [106] . 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@k and dataset-level thickness. Clearly, the models with high P@k performance usually have a relatively large thickness as well, and vice versa. Fig. 5 shows the saliency maps for case studies concerning all the baselines and R2ETs.We show the general form of adversarial attacks by a 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 = 3 for SNs and S = 1 for DNNs. We denote the primary objective in Eq. ( 1) manipulating the explanations as g 0 , and constraints for small prediction changes (measured by KL-divergence) as g s , 1 ≤ s ≤ S. Naturally, we construct a Lagrangian function with the non-negative multiplier γ = [γ 0 , γ 1 , . . . , γ S ] ∈ R S+1 + :EQUATIONSome previous works manually set γ as a hyperparameter by experience [16] , dismissing the relatives among g s . Instead, we care about the unsatisfied constraints with higher weights by uplifting γ s with larger g s . Thus, we adopt the following methods to update both primal variables x and dual variables γ [66, 11] :• Gradient descent ascent (GDA) solves the nonconvex-concave minimax problems [43] byEQUATIONwhere η x and η γ are the learning rates. Notice that ∂L(x,γ) ∂γs = g s , ∀s ∈ {1, . . . , S}, and γ 0 is passively updated by the normalization S s=0 γ s = 1 at the end of each iteration. • Hedge is an incarnation of Multiplicative Weights algorithm that updates γ using exponential factors [5] . In each iteration, we normalize γ such that S s=0 γ s = 1, and then update γ by γ ← γ ⊙ exp η Hedge [g0,g1,...,g S ] ,(EQUATIONwhere η Hedge is the learning rate, ⊙ is the element-wise multiplication, and exp is exponential operation. We also include unconstrained attack without any constraints, and no update that fixes the weights to γ = 1 S+1 1.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@k and no more than 2% sensitivity. These attack methods are used to evaluate the defense strategies in Table 1 . 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. A 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 on all datasets, demonstrating that R2ET and its variants are more advantageous in the trade-off between robustness and accuracy. Furthermore, on MNIST, compared with other methods on the Pareto front, 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 P@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 a model can be precise and explanation-robust at the same time. In this section, we consider the impacts of three hyperparameters or settings.Impacts of k. Table 7 shows that R2ET and its variants stay at 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. 8 , we sort the gradients of Vanilla models in descending order where their gaps can be inferred. Vanilla achieves about 100% P@k when k = 2 on Adult and Bank, indicating that even ERAttack cannot effectively manipulate the ranking in such scenarios. The reason is that the top 2 features are much more significant than the rest as shown in Fig. 8 . However, there is a narrow margin between the top 2 and top 3 features on COMPAS, and attackers can easily flip their relative rankings, thus Vanilla's P@k reduces to around 2/3. On MNIST, BP and ADHD, Vanilla models' P@k increases as k grows. It seems that models are more efficient against ERAttack 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, and about 40% * 50=20 features when k=50. Since ERAttack uses the same budget for different k, it becomes harder for ERAttack to manipulate more features simultaneously (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 in Sec. 4.2, fewer (k ′ ) compared feature pairs for R2ET and its variants alleviate optimization issues. Specifically, R2ET takes k-1 i=k-k ′ +1 h(x, i, k) + k+k ′ +1 j=k+1 h(x, k, j) as objective. Since R2ET \H and R2ET-mm \H are the two best variants in tabular datasets, we conduct a sensitivity analysis of these two methods on Bank. We set k = 8, and change k ′ from 1 to k. Fig. 9 indicates that R2ET \H and R2ET-mm \H perform much better when k ′ > 4 than those with k ′ ≤ 4. Apparently, when more pairs of features are taken into consideration, R2ET and its variants have a more comprehensive view of feature rankings to maintain the rankings better. Besides that, R2ET \H and R2ET-mm \H outperform almost all baselines, except for SP, for all k ′ . Impacts of pretrain / retrain. Lastly, we explore how good these methods are 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 a 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@k between Vanilla and retrain models' rankings significantly drops, or the retrain model's cAUC drops a lot. Table 8 presents the 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 is acceptable. More details for CL 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. Explainable machine learning and explanation robustness. Recent post-hoc explanation methods for deep networks can be categorized into gradient-based [103, 71, 7, 75, 77, 73, 100, 98, 35] , surrogate model based [64, 30, 82] , Shapley values [47, 12, 45, 99, 3] , 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, 29] . Some works [13, 74, 32, 83, 70, 80] propose to improve the explanation robustness by time-consuming 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 Hessianrelated terms as regularizers [17, 88, 91] . Some works propose new explanation methods, rather than training methods, to enhance explanation robustness [46, 44, 11, 51, 65, 75] . Besides, many works [50, 79, 87, 52, 67, 63, 97, 28, 96, 14, 78, 90, 101, 18] 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-based explanations being defined as first-order derivative relevant terms.Ranking robustness in IR. Ranking robustness in information retrieval (IR) concerning noise [106] and adversarial attacks [26, 104, 105, 42, 85] is well-studied. Ranking manipulations in IR and explanations are different because 1) In IR, authors either manipulate the position of one candidate [104, 26] , or manipulate a query to distort the ranking of candidates [104, 105, 42] . 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 are defined by gradient or its variants, and studying their robustness requires second or higher-order derivatives, and it motivates us to design an efficient regularizer to 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 ℓ p norm [13, 16, 17, 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 a 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 [2, 37, 38, 39, 8, 95, 60] . The upper bounds hold for predictions whose gaps are not larger than one, while it is not always true for gradient-based explanations with unbounded values, which prevents adopting similar methods to explanation tasks.Distributional shift. The distributional shifts [61, 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 a 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. 


Decision: 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.

Reviews: review: paper_summary: paper_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: 
* Relying on $\ell_p$ metrics is not a good/reliable proxy for robustness
* Attacking $\ell_p$ metrics leads to an arms race between attackers and defenders
In 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. 
Experimentally, the authors explore tabular and image datasets and across various models compute the described R2ET metric.
strength_weakness: strength_weakness: The two critical weaknesses I see with this work are its motivation and evaluation. 

Motivation: 
Point 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. 

Point 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 

Point 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? 

^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
questions: 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: limitations: The primary limitation of the paper is in its motivation.
paper_summary: paper_summary: The paper describes a regularizer to add to a loss function to encourage the resulting model to
have input attributions robust to ranking changes in its top k features. That is, for an input x,
the input attributions (a score for each input) for this input will be similarly ordered (at least
in the top k scoring features) as compared to the input attribution of any small perturbation x' of
x. The argument to use ranking and top-k ranking for defining robustness is that only the top few
input features are of relevance to a human interpreting an explanation. Ranking robustness itself
might be because the relative importance of features is more relevant to the human than the
absolute magnitudes of the importance.

To make ranking robust, the regularizer encourages gaps or "thickness" in the scores of top-k most
important features which would naturally make it harder to reorder them via a small perturbations
in the inputs and therefore (by addition of Hessian to encourage smoothness of gradients) feature
importance scores (which are assumed to be gradients or "saliency"). Analytical arguments are made
as to how to effectively implement the regularizer in a more efficient fashion. Analytical
arguments are presented as to a worst-case performance of an attack on the proposed method (though
why worst case is relevant confuses me).

A large collection of experiments demonstrate the use of the regularizer (termed R2ET) with various
parameters and compared to other robustness methods faced with several adversarial explanation
manipulation methods. These results show the proposed method is not optimal in all cases though it
is in many.
strength_weakness: strength_weakness: - W1. Motivation is based on ranking robustness but ranking robustness is not directly measured in
  the experimental sections. In the collection of explanation metrics enumerates in B.1.4, the P@k
  only partially exposes robustness with respect to ranking thought would miss all importance swaps
  that happen within the top k features. The experimental discussion seems to be making the case
  that the proposed top-k thickness metric is related to P@K but as P@k does not fully capture
  ranking robustness, those arguments also fail to make the connection. While I agree that
  optimizing for thickness would promote ranking stability, I do not find the concepts identical
  (i.e. there may be other or better ways to achieve ranking stability). Some experimental results
  may be hinting at the mismatch where I see the regularizer without Hessian sometimes
  outperforming the one with it.

  Suggestion: Include a more direct ranking robustness measure in the experimental results. I'm
  unsure what form of such a measure would be. Perhaps ranking correlation from [103] can be used
  for feature importance in the present paper.

- W2. Computational effort reduction not demonstrated. Part of the design seems to be limit
  backwards passes or other computationally costly steps. The experiments are plenty but none seem
  to demonstrate this aspect. There is an analytical time complexity discussion in the "Time
  complexity of R2ET" paragraph. The title itself suggests that stability is free but is a bit
  deceptive in that the training incurs additional costs.

  Suggestion: Include the experimental measurements of effort in the results. One of the strengths
  of the present approach is that the explanation-time is less costly as saliency is relatively
  less costly than alternatives. Showing this would be good to discuss/experiment with as well.

- W3. Most (or all) theoretical analysis applies only to saliency. Arguments/discussions regarding
  Proposition 4.6 in the appendix include the assumption that the explanation is a gradient (a
  saliency explanation). Saliency are defined in Preliminaries but it is not clearly stated there
  that the rest of the paper assumes all explanations are of this form. As the methods target
  saliency, a lot of this paper depends on saliency being a good explanation method to begin with.
  However, plenty of works argue that it is not (see [73, 75]). Some benefits of things like IG
  also share motivation to ranking robustness (that relative scores are more important than
  absolute).

  Suggestion: Make it clear that the analytical sections make this assumption. Also, note in the
  "Apply R2ET to other explanation methods" paragraph in Section 6 that the analytical conclusions
  do not apply to these other methods. A good inclusion to the limitations discussion would be that
  saliency itself has some problems which may warrant use of a different explanation method
  especially for problems with regards to robustness which this work is attempting to solve using a
  regularizer.

Other comments/suggestions:

- C1. The intro/motivation could use some discussion of how the primary desiderata in explanations
  and how they related to each other. The paper is primarily based on ranking robustness which I
  could say is an element of an explanation's interpretability and resistance to adversarial
  manipulation. From here it would be useful to say that addressing robustness could be done with
  adjustments to the explanation method or to adjustment to the model or training. The paper
  discusses the second but a note about the benefits/drawbacks of the first would be good to
  include as they introduce some of the subsequent experiments which are presently hard to fit into
  the big picture.

  1. Want (interpretability and) resistance to adversarial manipulation.

  2. Option 1: Change the explanation method (don't use Saliency). Benefit: no model changes.
     Drawbacks: faithfulness vs robustness tradeoff. Explanation-time costs might be large.

     Option 2: Add regularizer for saliency during training. Benefits: Fast (or "free" as per
     title) explanations, better faithfulness, Drawbacks: training-time costs, utility loss.

     Option n: ???

  3. We do Option 2 and here are analytical and experimental results demonstrating the strengths
     and the impact of weaknesses.

  This chain of thought justifies the present (i.e. faithfulness) and suggested experiments (i.e.
  costs as per Weakness W2). Some of the experiments in the Appendix might be approaching these
  points though I'm having trouble connecting the dots.

- C2. The "thickness" notion could be better presented in the experiments. Figure 8 in the appendix
  shows some saliency/importance graphs without regularization for gaps. Can you include similar
  pictures for regularized models? I would expect to see the top-k features to have a linear
  decrease in importance. Seeing this (or something else) could go a long way in building intuition
  in the approach described in this paper.

Smaller things:

- The intro point about "inherent limitations of human cognition" as an argument for top-k
  importance doesn't apply as well to vision tasks where our eyes look at a huge number of raw
  features and necessarily so in order to resolve higher-level structures.

- The top-k thickness paragraph on line 97 cites [107] as a work suggesting maintaining ranking of
  features but this work is not on feature importance. The "raking" there is because the topic is
  ranking models.

- The statement "only the top-k important features in \cal{I}(x) are more relevant to human
  perception" is quite vague and I'm unsure how it could be formalized. Also note the grammar issue
  ("more relevant" than what?).

- "cost computations" -> "costly computations".

- "single-input DNNs", this reads like the DNNs have a single input neuron but doesn't mean that.
  Rephrase?
questions: questions: - Q1. My understanding of a lot of the technical discussions in the paper was limited so the
  comments in the weaknesses in the prior section might not be fully justified. If this is the
  case, please address how the paper does not have the stated weakness. For those that are
  weaknesses, please comment on plausibility of addressing them either with my suggestions or
  otherwise.

- Q2. Proposition 4.6 relates Equation 6 and Equation 7. 7 includes perturbations while 6 does not.
  I'm having trouble qualifying the perturbations to make the statement make sense. Please include
  some higher-level points as to why this and other \theorems follow.

- Q3. Some results show that the regularization without the Hessian performs better than with it
  which is casting some doubt on the theoretical arguments. Alternatively it could be a mismatch
  between P@k and the optimization goal. Can ranking consistency be measured more directly? (i.e.
  as per suggestion of W1) and would it be able to explain the \H results?

- Q4. How would directional scores affect the methodology? While saliency has a sign, I don't see
  it demonstrated in this paper with a sign. Have all attributions been absolute valued first?
  Generally an explanation with both positive attribution and negative attribution would be more
  valuable and perhaps relative to ranking, having top-k (positive) and bottom-k (negative) would
  be the equivalent.

- Q5. I'm not following the purpose of worst-case complexity of an adversarial attack (Section 5).
  Wouldn't it make more sense to lower bound the complexity of an attack instead of upper bound it?
limitations: limitations: Only one limitation is noted in Section 7 with regards to using a surrogate of thickness. I believe
there are further limitations as noted in W3 for example. Societal impacts not mentioned though
addressing explanation robustness for its own sake or against adversarial perturbations is expected
to have only positive societal impact.
paper_summary: paper_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.
strength_weakness: strength_weakness: -	The thickness concept has been used for prediction robustness. 
-	Eq. (6) involves evaluating the Hessian matrix and that can be quite time consuming, compared to WD that does not need the Hessian matrix.
questions: questions: -	In Figure 2, why the correlation indicates that thickness is a better metric of explanation robustness? More details are needed.
-	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?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_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.
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.

[1] Li et al. “Are Data-driven Explanations Robust against Out-of-distribution Data?” CVPR 2023.

[2] Pillai et al. “Consistent explanations by contrastive learning” CVPR 2022.
questions: 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: 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.

Comments: title: Thank you for the reply
Thanks for your comments
comment: Thank you once again. We truly appreciate your insightful and valuable feedback on our work.
I will keep my score after reviewing other referees' comments and the manuscript.
Thank you so much!
Thanks for the further discussion.

> is it the case that both top-k thickness and R2ET optimization goal care not about influence within the top k features nor the influence within the bottom non-top-k features? 

We motivate the research based on the P@k (one of the widely used ranking-based metrics), which does *not* care about the rankings within the top-k features, nor the rankings within the remains. Thus, we naturally do not intend to consider such relative rankings for top-k thickness and R2ET.

> In this case, your last comment that there might be "mismatch between R2ET’s optimization goal and thickness" is confusing. Was that point about thickness other than top-k ranking thickness of Definition 4.2? 4.2 thickness seem to have a direct representation in the loss term, the one with \lambda_1 coeff of Equation (6).

R2ET's objective in Eq. (6) and thickness in Eq. (3) in Definition 4.2 are not exactly the same. 

Let us go back to the *pairwise* thickness defined in Eq. (2) in Definition 4.1: The *pairwise* thickness measures the explanation robustness by comprehensively capturing the surrounding gaps (by expectation and integration).

The top-k thickness, defined by pairwise thickness, accumulates the pairwise thickness of all possible top-bottom pairs. Thus, an **exact** computation of top-k thickness will involve expectation and integration due to Eq. (2).

R2ET optimizes the *bounds* of the top-k thickness based on Eq. (5), rather than the definition of the top-k thickness directly.
$h(x,i,j)$ in Eq. (6) refers to the *gap*, rather than *thickness*.
Thus, optimizing R2ET's objective function does not essentially lead to the best thickness.

> I have now some deeper concerns about the importance of setting k in the methodology. The implicit goal when using some value of k is that we want a model that has k important features and n-k non-important features for each explanation. Given that explanation faithfulness is among the goals of explanations in general and in this paper, the setting of k is as much, if not more, about the problem being solved/predicted by the model than it is about the complexity/interpretability of explanations. If k is too small or too large, the regularization will force the model to do some weird things. Some tasks might not even have a fixed k number of inputs that are important uniformly (i.e. 1 feature is necessary to make prediction for some set of instances while 2 features are necessary for a different set). Can you comment on how to deal with this aspect of the methodology?

It is a great question. We believe it is asking for a more "fine-grained" explanation robustness. In a nutshell, we can generalize R2ET to a more "fine-grained" version, although it may go far away from some practical scenarios (e.g., credit card applications only disclose a fixed number of reasons for final decisions).

As discussed in Lines 107-110, we can generalize R2ET (based on precision@k) to address broader requirements and/or properties. For example, the average precision@k (AP@k) or discounted cumulative gain (DCG) takes the relative rankings/positions among top-k (or the bottom) features into account. To incorporate these metrics, R2ET can be easily extended by setting different weights to various feature pair rankings. Intuitively, the key difference between R2ET (P@k) and the adaptations (based on AP@k and DCG) will be the weights of gaps $h(x,i,j)$ in Eq.(6), and R2ET adaptations encourage to maintain rankings between *any* feature pairs.

In the case of AP@k or DCG, setting $k=n$ ($n$ be the number of features) is meaningful, and R2ET models will keep reasonable gaps between *any* feature pairs. In other words, models can provide the ranking of every feature's importance.



Thanks again for your time and consideration. Please let us know if further concerns.
After reading the discussions I'm realizing my reading of thickness and the loss terms was slightly off hence some of my questions were misdirected. First let me make sure I'm viewing this right now: is it the case that both top-k thickness and R2ET optimization goal care not about influence within the top k features nor the influence within the bottom non-top-k features? In this case, your last comment that there might be "mismatch between R2ET’s optimization goal and thickness" is confusing. Was that point about thickness other than top-k ranking thickness of Definition 4.2? 4.2 thickness seem to have a direct representation in the loss term, the one with \lambda_1 coeff of Equation (6). 

Also; I have now some deeper concerns about the importance of setting k in the methodology. The implicit goal when using some value of k is that we want a model that has k important features and n-k non-important features for each explanation. Given that explanation faithfulness is among the goals of explanations in general and in this paper, the setting of k is as much, if not more, about the problem being solved/predicted by the model than it is about the complexity/interpretability of explanations. If k is too small or too large, the regularization will force the model to do some weird things. Some tasks might not even have a fixed k number of inputs that are important uniformly (i.e. 1 feature is necessary to make prediction for some set of instances while 2 features are necessary for a different set). Can you comment on how to deal with this aspect of the methodology?
Thank you for your reply; I am happy to raise my score.
Thank you for taking the time to revisit our paper and for further considering our manuscript. We greatly appreciate your positive reassessment and for raising the score based on the favorable impression of our work.
I have re-read the paper after the author rebuttal and several of my concerns have been addressed. I still have a few minor concerns, but given the review period is coming to a close I will give the authors the benefit of the doubt and raise my score to reflect my overall postive impression of the paper.