"Are Your Explanations Reliable?" Investigating the Stability of LIME in Explaining Text Classifiers by Marrying XAI and Adversarial Attack
Authors: Christopher Burger
Lingwei Chen
Thai Le
Venue: EMNLP 2023 Main (2023)
Keywords: Interpretability
Stability
Robustness
Explainability

Abstract: LIME has emerged as one of the most commonly referenced tools in explainable AI (XAI) frameworks that is integrated into critical machine learning applications (e.g., healthcare and finance). However, its stability  remains little explored, especially in the context of text data, due to the unique text-space constraints. To address these challenges, in this paper, we first evaluate the inherent instability of LIME on text data to establish a baseline, and then propose a novel algorithm XAIFooler to perturb text inputs and manipulate explanations that casts investigation on the stability of LIME as a text perturbation optimization problem. XAIFooler  conforms to the constraints to preserve text semantics and original prediction with small perturbations, and introduces Rank-biased Overlap (RBO) as a key part to guide the optimization of XAIFooler  that satisfies all the requirements for explanation similarity measure. Extensive experiments on real-world text datasets demonstrate that XAIFooler  significantly outperforms all baselines by large margins in its ability to manipulate LIME's explanations with high semantic preservability.

"Are Your Explanations Reliable?" Investigating the Stability of LIME in Explaining Text Classifiers by Marrying XAI and Adversarial Attack
Christopher Burger University of Mississippi Oxford, MS, USA cburger@olemiis.. edu
Lingwei Chen
Thai Le University of Mississippi Oxford, MS, USA thaile@olemiss edu
Wright State University
Dayton, OH, USA lingwei www.wwiicheewright...o edu
Abstract
(1) skin
(1) skin
(2) winter,
(2) rash
LIME has emerged one of the most com- monly referenced tools in explainable Al (XAI) frameworks that is integrated into critical chine learning applications-c.g, healthcare and finance. However, its stability remains little ex- plored, especially in the context of text data, due to the unique text-space constraints. To address these challenges, in this paper. we first evaluate the inherent instability of LIME on text data to establish a baseline, and then pro- pose novel algorithm XAIFOOLER per- turb text inputs and manipulate explanations that casts investigation on the stability LIME text perturbation optimization problem. XAIFOOLER conforms to the constraints to preserve text semantics and original prediction with small perturbations, and introduces Rank- biased Overlap (RBO) as key part to guide the optimization of XAFFOOLER that satisfies all the requirements for explanation similarity measure. Extensive experiments on worldworld text datasets demonstrate that XAIFOOLER sig- nificantly outperforms all baselines by large ability to manipulate LIME'S explanations with high semantic preservabil- ity. The code is available at https: thub. com/cburgers www.rreerrrrrireeeeeem ssx
(3) joint
worse
(5) winter
(13) rash
(11) (11))ooit
have a skin rash that gets becomes worse the winter. have moisturize more regularly consistently and have [...].
also have joint pain."
Figure I: With only two perturbations, XAIFOOLER significantly demoted "joint pain" symptom from top-3 to 11th-rank (left- figure) while maintaining the original prediction label of "peptic ulcers" and retaining the clarity and meaning the original text.
While explainability in Al general concept has yet fully coalesce an accepted set of defini- tions (Ghorbani et al., 2019), the concept of Stabil- ity starts to occur throughout the discussions and re- mains prominent (Molnar, 2022; Doshi- and Kim, 2017: Zhang et al., 2020). A stable explana- tion refers to one where small changes to the input should have corresponding small effeet on the output. In other words, similar inputs to model should produce similar explanations. Lack of stabil- ity in an explanatory method undermines its trust- worthiness (Ghorbani et al., 2019), and renders all subsequent explanations suspect. This lack trust- worthiness is one reason why the adoption of Al in disciplines like healthcare has progressed slower than in other disciplines (Markus et al., 2021).
margins
1 Introduction
Machine learning has witnessed extensive research, leading to its enhanced capability in predicting a wide variety of phenomena (Pouyanfar et al., 2018). Unfortumately, this increased effectiveness has come at the cost of comprehending the inner workings of the resulting models. To address this challenge, explainable AI (XAI), also known as in- terpretable AI (Tjoa and Guan, 2020), has emerged a discipline focused on understanding why model makes the predictions it does. XAI contin- ues to grow importance due both legal and societal demands for elucidating the factors con- tributing to specific model predictions.
Previous work on XAI stability has focused on models where üunction-based continuity criteria naturally apply to tabular and image-based data (Alvarez-Melis and Jaakkola, 2018; Zhang et al., 2020; Ghorbani et al., 2019). However, text data in natural language is not amenable to such direct quantification. Therefore, the process of generat- ing appropriate perturbations test stability in text explanations remains little explored (Ivankay et al., 2022). Unlike perturbations tabular or image- based data, text perturbations pose unique chal-

---

lenges satisfy necessary constraints of semantic similarity and syntactic consistency. Violation of these constraints can create fundamentally differ- ent meaning conveyed by the document. Under the assumption the explanatory algorithm works cor- rectly, these perturbations may alter the resulting explanation, where quantifying difference between explanations also needs to characterize their prop- erties, such as feature ordering and weights within explanations presented in Fig. 1.
margins in its ability manipulate LIME's expla- nations with high semantic preservability.
2
Background
2.1 LIME
In this paper, we adopt Local Interpretable Model- agnostic Explanations (LIME) (Ribeiro et al., 2016) as our target explanatory algorithm. LIME has been a commonly researched and referenced tool in XAI frameworks, which is integrated into critical ML applications such as finance (Gramegna and Giudici, 2021) and healthcare (Kumarakulasinghe et al., 2020; Fuhrman et al., 2022). To explain pre- diction, LIME trains shallow, explainable surro- gate model such as Logistic Regression training examples that are synthesized within the vicinity of an individual prediction. The resulting explanation is subset of coefficients of this surrogate model that satisfies the fundamental requirement for in- terpretability. In NLP, explanations generated by LIME are features-e.g. e.g. words, returned from the original document, which can be easily understood even by non-specialists.
In this paper, we explore the stability of expla- nations generated on text data via LIME (Ribeiro et al., 2016), which is a widely used explanatory al- gorithm in XAI frameworks. We first examine the inherent stability of LIME by altering the number of samples generated to train the surrogate model. Us- ing this baseline, we then propose XAIFOOLER, novel algorithm that perturbs text inputs and manip- ulates explanations to investigate in depth the sta- bility of LIME in explaining text classifiers. Given a document, XAIFOOLER proceeds with iterative word replacements conforming to the specified con- straints, which are guided by Rank-biased Over- lap (RBO) that satisfies all the desired characteris- tics for explanation similarity measure. As such, XAIFOOLER yields advantages that only small per- turbations the least important words are needed, while the semantics and original prediction of the input are preserved yet top-ranked explanation fea- tures are significantly shifted. Fig. shows an example that XAIFOOLER only performs two per- turbations (i.e., "gets" -> "becomes" and "regu- larly" - "consistently"). but effectively demotes the t3p-3 features-e.2 e.g., "joint" (1 1 rank), that explains the "joint pain" symptom with- out changing the prediction of peptic ulcers discase. Our contributions are summarized follows.
2.2 XAI Stability
Existing research work on XAI stability has pre- dominant emphasis on evaluating models using tabular and/or image data across various interpreta- tion methods, which often use small perturbations to the input data generate appreciable different explanations (Alvarez-Melis and Jaakkola, 2018; Ghorbani et al., 2019; Alvarez-Melis and Jaakkola, 2018), or generate explanations that consist of arbi- trary features (Slack et al., 2020).
LIME specifically has been analyzed for its effi- cacy. Garreau et al. first investigated the stability of LIME for tabular data (Garreau and Luxburg, 2020; Garreau and von Luxburg, 2020), which showed that important features can be omitted from the re- sulting explamations by changing parameters. They extended the analysis to text data later (Mardaoui and Garreau, 2021) 1) but only on the fidelity instead of stability of surrogate models. Other relevant works in text domain include (Ivankay et al., 2022), which utilized gradient- based explanation methods, assuming white-box access to the target model and hence not realistic because model parameters are often inaccessible in practice; and (Sinha et al., 2021), which revealed that LIME'S explanations are unstable to black-box text perturbations. How- ever, adopts a very small sampling rate for LIME
We assess the inherent instability of LIME preliminary step towards better understanding of its practical implications, which also serves as a baseline for subsequent stability analysis.
We cast investigation on the stability of LIME as a text perturbation optimization problem, and in- troduce XAIFOOLER with thoughtful constraints and explanation similarity measure RBO to gener- ate text perturbations that effectively manipulates explanations while maintaining the class predic- tion in cost-efficient manner.
We conduct extensive experiments on real-world text datasets, which validate that XAIFOOLER significantly outperforms all baselines by large

---

GB
S2D
IMDB
Intersection Proportion
1.0
1.0
1.0
Time Per Explanatii on (s)
BERT
Average Runtime
DistilBERT
20
30
0.9
-40
RoBERTa
0.9
0.9
0.8
30
0.8
20
0.7
0.8
10
-20
0.7
100.6
10
0.6
2500
5000
7500
2500
5000
7500
2500
5000
7500
Sampling Rate
Sampling Rate
Sampling Rate
Figure 2: Inherent explanation instabilities for each model and dataset.
(n=500) which we later demonstrate to signifi- cantly overestimate LIME'S instability. Moreover, its experiment settings are not ideal as it allows the perturbations of top-ranked predictive features, which naturally change the resulting explanations. Although existing works have showed that LIMR sensitive to small perturbations the target model's 's inputs or parameters, they do not answer the fundamental question of whether LIME itself is inherently unstable without any changes to the in- put model's parameters. Answers to this "what is the inherent instability of LIME" question would establish meaningful baseline that helps better evaluate our stability analysis.
Dataset
Mean
Median
Min
GB
82.0% (J A18%)
82.0%
75.5%
S2D IMDB
84.0% (J A16%)
84.4%
72.9%
71.5% (U A28.5%)
70.4%
67.3%
Table 1: Statistics explanation similarities when using different alternate sampling rates compared against the base explanation with default sampling rate n-5K.
runtime due to large number of inference passes required to collect all f(d)).
To test the inherent instability of LIME, we first select arbitrary number of documents and gener- explanations at different sampling rates from 1K-7K for three state-of-the of-the--rt classifiers, includ- ing BERT (Devlin et al., 2019), RoBERTa (Liu et al., 2019), DistilBERT (Sanh et al., 2019), trained on three corpus varying in lengths. Then. we compare them against the base explanation gen- erated with the default sampling rate (n=5K), Ta- ble shows that altering the sampling rate from its default value results in significant dissimilarities in the explanations 1.16%-128.55
3 Preliminary Analysis
Inherent Instability of LIME. This section first assesses the inherent instability of LIME. Our aim is to determine if LIME produces inconsistent re- sults even when no changes are made to the target model's inputs parameters. Let d be docu- ment whose prediction under target model f()) is be explained. A simplified process of LIME'S explanation generation for (dd is as follows.
in similarity on average), which observe to be more significant on longer documents. This happens because longer documents generally require more training exam- ples to refine the local model g(-) to better approxi- mate f(-). Fig. 2 gives us a closer look into such instability, which further shows evidence that in all datasets, both bounded variation and diminish- ing returns converge the sampling However, with small sampling rates n-e.g., n<4K in IMDB dataset, slight changes in n produce sig- nificantly dissimilar explanations.
Step 1: Generate perturbed document de by ran- domly selecting k words from d and remove all of their occurrences from d.
Step 2: Repeat Step / to sample different per- turbations /d
increases.
Step 3: Train an explainable model g(-) via super- vised learning with features d, and labels f(d)).
Here is the sampling rate which determines the number of local training examples needed to train the surrogate model g(.). Sampling rate greatly influences the performance of LIME. Intuitively, small n often leads to insufficient amount of data for training good g()). ). In contrast, a large n may result better g(-) but also adversely increase the
Overall, LIME itself is inherently unstable, pecially when is small, even without any modifi- cations the target model or its inputs. Contrast to small sampling rates-e.g.. n=500, adopted existing analytical works, our analysis implics that n. should be sufficiently large according to each

---

dataset maximize the trade-off between compu- tational cost and explanation stability. However, the source of the instability within LIME is yet un- determined. We emphasize the importance of this question but leave its investigation for future work. Motivation This inherent instability is significant in practice due the fact that many important AI systems-e.g,, ML model debugging (Lertvit- layakumjorn and Toni, 2021) or human-in -imaa---tthe-loop system (Nguyen and Choo, 2021), use surrogate methods such as LIME as a core component. This instability also has implications on software secu- rity where malicious actors can exploit this insta- bility and force AI models to produce unfaithful explanations. Given that there exists some level of instability within the explanations by default, we now ask if alterations to the input text can demon- strate instability beyond that of the baseline levels already seen. That is, can perturbations to the input that are carefully chosen to retain the underlying meaning of the original text result in appreciably different explanations. If so, the concerns about in- stability mentioned above become that much more pressing. To do this, we propose to investigate the robustness of LIME by formulating this perturba- tion process as an adversarial text attack optimiza- tion problem below.
Trivially, changing words chosen arbitrarily and with equally arbitrary substitutions would, even- tually, produce an explanation different from the original. However, this will also likely produce a perturbed document dp whose semantic meaning drastically differs from d3. Thus, we impose a con- straint on the semantic similarity between do and dp to ensure that the perturbed document dp does not alter the fundamental meaning of dg:
Sim, (de. dp) 2 5,
(3)
where (-m is the semantic similarity between two documents and ō is a sufficiently large hyper- parameter threshold.
Even with the semantic constraint in Eq. (3), there can still be some shift regarding the context and semantics of de and dp that might not be im- peccable to humans yet cannot algorithmically cap- tured by the computer either. Ideally, the malicious actor wants the perturbed document dp to closely resemble its original dz. However, as the number of perturbations grows larger, the document retains less of its original context and meaning. To ad- dress this issue, we impose a maximum number of perturbations allowed through the use of a hyper- parameter as follows:
(4) where an accepted i-th perturbation will have re- placed i total number of words (as each perturba- tion replaces a single word) and Iff is the total number of unigram bog-of-words features in f.
i E [f],
4 Problem Formulation
Our goal is to determine how much a malicious ac- tor can manipulate explanations generated by LIME via text perturbations-i.e. minimally perturbing document such that its explanation significantly changes. Specifically, a perturbed document dp is generated from a base document dz, such that for their respective explanations Cdp and ed, we minimize their explanation similarity: dp = argmin Sime Cdp)
We can now generate perturbations a way that maintains the intrinsic mcaning of the original doc- ument. If we are to manipulate the explanation (Eq. (1)) while maintaining both Eq. (2), Eq. (3) and Eq. (4), it is trivial to just replace some of the most important features of f. However, in practice, changing the most important features will likely result in a violation constraint in Eq. (2). More- over, this will not provide meaningful insight to the analysis on stability in that we want to measure how many changes in the perturbed explanation that correspond to small (and not large) alterations to the document. Without the following constraint, highly weighted features will often be perturbed, even with search strategy focused towards fea- tures of minimal impact on the base explanation. This happens due to the strength of the previous constraints focused on maintaining the quality of the document. Thus, the set of top k feature(s) be- longing to the base explanation Cd, must appear in
(1)
dp
where S-m is the similarity function between two explanations. To optimize Eq. (1), our method involves scries of successive perturbations within the original document as often proposed in adver- sarial text literature. In typical adversarial text setting, malicious actors aim to manipulate the tar- get model's 'ss prediction on the perturbed document, which naturally leads to significant changes in the original explanation. But this is not meaningful for our attack; thus, we want to preserve the original prediction while altering only its explanation:
f(d)) = f(dp);
(2)

---

the perturbed explanation Edp' Cd n Nc * Ø Vc ed, kj.
Algorithm 1 Adversarial Explanation Generation
(5)
1: Input: target model f. Original Document do. Base Explanation ca. Maximum Perturbation Threshold pc. Current Perturbations p. Current Similarity
Overall, our objective function is as follows.
2: Output: Perturbed Document dz, Perturbed Explana- tion 6p. Updated Similarity 8
OBJECTIVE FUNCTION: Given a document do. e, k.
a target model f and hyper-paramett
3: Initialize: 6p 4- ca. i 4- 0, 4- 1, + 0
our goal is to find a perturbed document dp by optimizing the objective function: dp argmin Side ed,),
4: Initialize: 1 + indices of replacement candidates that satisfy C
5: while / * Ø and < Pt do = RRBOdd, perturbld, [b]] 7: if
6:
dp
then
s.t. f(db) = f(dp).
8:
s <- $;
9:
Cn < perturb(d,
Simg(dg. dp) 2
(6)
10:
end if
11:
[[]] =
i |,/
12:
i +-i+1
13:
end while
e,p nc + Ø VcE E ed
14:
return (dy; Sp,
5 XAIFOOLER
4, 5), we only accept a perturbation if it satisfies these constraints, and at the same time improves the current best explanation dissimilarity. To re- duce the search space of replacements, we only se- lect replacement candidates that maintain the same part-of-speech function and also within a similarity threshold with the word to be replaced in counter- fitted Paragram-SL99 SL999 word-embeuding space (Wi- eting et al., 2015) as similarly done in prior adver- sarial text literature (TextFooler (Jin et al., 2020)). Since our perturbation strategy solely applies the constraints at the word level, certain perturbations may result in undesirable changes in textual qual- ity, which is often observed in texts perturbed by popular word-level methods such as TextFooler. However, our proposed algorithm (Alg. 5.1) is generic to any black-box text perturbation func- tions perturb(-) (Alg. 5.1, Ln. 6, 9).
To solve the aforementioned objective function (Eq. (6)), we propose XAIFOOLER, a novel greedy- based algorithm to manipulate the explanations of a text-based XAI method whose explanations are in the form of a list of words ordered by importance to the surrogate model. We then demonstrate that XA KAIFOOLER can effectively alter the explanations of LIME beyond the intrinsic instability (Sec. 3) via carefully selected text perturbations.
5.1 XAIFOOLER Algorithm
Algorithm 1 describes XAIFOOLER in two steps. First, given input document, it decides which words perturb and in what order (Ln. 4). Next, it greedily replaces each of the selected word with a candidate that (i) best minimizes the explana- tion similarity via Sime and (ii) satisfies all the constraints in Sec. 4 until reaching the maximum number of perturbations (Eq. (4)) (Ln. 5-13).
5.2 Explanation Similarity Characterization
Step 1: Greedy Word Selection and Ordering. We disregard all stopwords and the top-k important features based on their absolute feature importance scores returned from LIME. We then order the remaining words in the original document d, in descending order according to how many changes they make in the original prediction when they are individually removed from dp. Intuitively, we pri- oritize altering features of lower predictive impor- tance to signify the instability of LIME (Eq. 5).
The most important factor that guides the optimiza- tion of XAIFOOLER is the explanation similarity function Sim, needed to compare two explanations Cdy and edg. In selecting a good Sim, function, we need to first characterize it. The explanations edg- Ca, returned from LIME are ranked lists. That is, they are an ordered collection of features. Specif- ically LIME'S explanations consist of unique fea- tures which are ordered w.r.t their importance to the local surrogate model. While there is substan- tial amount of prior work discussing comparison methods for ranked lists, the structure of LIME'S explanations and our constraints are not ideal for many common methods. Thus, for our purposes, a desirable Sim, has properties as follows.
Step 2: Greedy Search with Constraints. We subsequently replace each word in the list returned from Step with a list of candidates and only keep those that help decrease the explanation similarity Sim, (Alg. 1, Ln. 6-) To satisfy Eq. (2, 3,

---

(A) Positional Importance (Kumar and Vassilvit- skii, 2010). We require that relative ordering be imposed on the features-i.e.. higher-ranked fea- tures should be accorded more influence within (.) That is, moving the Ist-ranked feature to rank 10 should be considered more significant than moving the 10th-ranked feature to rank 20. Moreover, this requirement also accounts the fact that end-users often consider only the top ht most important and not all of the features (Stepin al., 2021) in practice, and thus Sime(.) should be able to distinguish the ranking of different features.
Feature/ Measure
Positional Feature Disjoint Unequal-
Importance Weighting Features Length List
Jaccard Index Kendall's Spearman's
Center of Mass
RBO
TRBO: Rank-biased Overlap: customized formulas exist
Table 2: Comparisons among explanation similarity
measures with RBO satisfying all the requirements.
1.0
Jaccard Similarity
Rank Correlation
(B) Feature Weighting. This is a strengthening of the positional importance by considering not only discrete positional rankings such as 1st, 2nd, 3rd, but also their continuous weights such as the fea- ture importance scores provided by LIME. This provides more granularity in the resulting expla- nation similarities and also better signals to guide our optimization process for Eq. (6).
Similarity
RBO (90%
5)
0.6
RBO (80% mass on top 5)
0.4
0.2
0.0
10000
20000
30000
40000
50000
Permutation
Figure 3: Simulation 50K permutations of 50 fea- tures: RBO outputs smoothed, richer signals while other measures return zero similarity for over half the permuta- tions and show poorer delineation among top-k features, resulting in the non-smoothed, step-wise behavior.
(C) Disjoint Features. We require that disjoint lists can be compared. Consider a single word replace- ment of word w with word w' in document da with base explanation CdN and perturbed explana- tion Edp, generated from d-wc+w'. The perturbed explanation Ed, cannot contain the word w or any subset of d, containing as a possible feature. And so each perturbation is likely to result an expla- nation that is disjoint. Many similarity measures that have a requirement for non-disjoint lists often have an implementation that relaxes this require- ment. However, as the amount of disjoint features increases, these measures will struggle to deliver appropriate similarity values.
as it not only indicates a change in the weights but also provides information about where that weight is being assigned. However, change in COM does not imply an actual change in the relative order of features. The second group is feature-based This includes (1) Jaceard Index, which compares two sets by computing the ratio of the shared elements between the sets to the union of both sets. Being a strictly bet-based measure, the Jaccard index lacks positional importance and feature weighting (exten- sions exist to allow weight), making it unsuitable for our problem. (2) Kendall's & Spearman's p are commonly used for determining the similarity of two ranked lists. The central idea of both is the order of the features. However, they disregard any ranking weights, the capacity to handle unequal list lengths, and disjoint features. Remedies are also availablc-c.g.. Kumar and Vassilvitskii (2010). but they do not fulfill all the requirements and can result in information loss.
(D) Unequal List Lengths. Similarly to (C) but if w/ already exists in the original explanation cbs the length of ep will be different from e due to dp having one less unique unigram feature.
5.3 Existing Similarity Measures
With the above characterization, we proceed to search for an ideal explanation similarity measure for Sim, from some of commonly used measures on ranked lists. The first group of such is weight- based. This includes (1) Lp: The standard I.p distances discard the feature order entirely and in- stead concentrate on their associated weights. Cer- tain formulations exist that allow weighting the ele- ments, but the I.p distances still lack the capacity to handle differing ordered-IE list lengths. (2) Center of Mass (COM): COM is an improvement upon Lp
5.4 RBO:
The Best of both Worlds
So far, none of the mentioned measures satisfies all requirements. Fortunately, there exists Rank- biased Overlap (RBO) (Webber et al., 2010) that well fits to our criteria. RBO is a feature- comparison measure that combines the benefits of

---

DistilBERT
BERT
RoBERTa
Datasct/Method
ABST
RCT
INSL
SIM
PPL.
ABST
RC;
INS|
SIM
PPL.
ABST
RCT
INS
SIM
PPL.
Inherency
4.92
0.34
0.83
1.00
33.17
5.66
0.48
0.83
1.00
34.51
5.90
0.52
0.82
1.00
33.88
IMDB
Random
5.90
0.50
0.84
0.89
71.07
6.80
0.58
0.80
0.88
75.74
7.33
0.52
0.78
0.89
73.89
LOM
3.94
0.33
0.89
0.96
40.35
4.92
0.41
0.87
0.95
43.85
6.08
0.47
0.83
0.95
43.41
Ly
9.07
0.52
0.81
0.89
69.54
8.76
0.57
0.79
0.89
71.16
9.96
0.65
0.78
0.89
72.87
XAIFOOLER
I0.43
0.65
0.75
0.89
67.01
11.44
0.69
0.72
0.89
67.79
12.65
0.76
0.72
0.90
63.15
Inherency
1.30
0.23
0.88
1.0
12.3
1.65
0.24
0.85
1.0
12.30
3.09
0.36
0.76
1.00
12.30
Random
1.72
0.27
0.85
0.84
77.69
2.49
0.41
0.80
0.85
79.22
3.66
0.48
0.77
0.84
83.04
S2D
LOM
1.18
0.20
0.91
0.95
19.59
1.38
0.29
0.88
0.94
19.88
2.44
0.30
0.82
0.94
20.04
Lp
2.98
0.52
0.75
0.85
82,90
3.76
0.54
0.77
0.84
97.81
4.99
0.52
0.69
0.85
66,98
XAIFOOLER
3,95
0.62
0.73
0.88
47.49
4.75
0.54
0.74
0.89
48.76
6.11
0.62
0.67
0.89
38.79
Inherency
0.53
0.16
0.89
1.00
167.35
0.55
0.15
0.87
1.00
171.88
0.44
0.16
0.93
1.00
169.19
Random
1.31
0.32
0.72
0.81
618.18
1.38
0.30
0.75
0.81
616.60
0.99
0.23
0.79
0.82
6.37.65
LOM
0.60
0.22
0.89
0.91
322.85
0.55
0,11
0.90
0.91
312.81
0.47
0.10
0.91
0.91
295.33
2.06
0.39
0.66
0.86
583.15
1.99
0.47
0.71
0.86
547.91
1.47
0.43
0.77
0.87
553.80
XAIFOOLER
2.02
0.48
0.71
0.89
358.88
2.10
0.52
0.71
0.89
368.53
1.56
0.45
0.78
0.91
353.98
bold and underline statistics denote the best and second best results except "Inherency"
Table Experiment results in terms of explanation changes (ABS, RC, INS) and semantic preservation (SIM, PPI.)
the set-based approaches while retaining the posi- tional information and capacity for feature weight- ings. The weights assigned to the features are con- trolled by convergent series where the proportion of weights associated with the first & features is de- termined by a hyper-parameter pe [0, 1). As p-+0 more weight assigned to the topmost features, while as p->1 1 the weight becomes distributed more evenly across all possible features.
tion (GB) (Dinan et al., 2020), of varying averaged lengths (230, 29, 11 tokens), and number of labels (2, 21, 2 labels) (see Table B.7-Appendix). Each dataset is split into 80% training and 20% test sets. We use the training set to train three target models, namely DistilBERT (Sanh al., 2019), BERT (De- vlin et al., 2019) and RoBERTA (Liu et al., 2019). achieving around 90%-97% in test prediction F1 score.
Fig. illustrates the comparison between RBO, Jaccard, and Kendall/Spearman measures, which highlights two advantages of RBO. First, RBO al- lows features outside the top i some small influ- ence the resulting similarity. Second, the weight- ing scheme associated with RBO allows more gran- ularity when determining similarity by applying weight to the top k features (Fig. 3), which lack- ing with the other measures. In other words, RBO provides richer signals to guide the greedy opti- mization step of XAIFOOLER. Morcover, RBO allows us to decide how much distribution mass to assign to the top-k features (Fig. 3 with 90% & 80% mass)). This enables to focus on manipu- lating the top-k features that the end-users mostly care about while not totally ignoring the remaining features. We refer the readers to Appendix for detailed analysis on RBO and other measures.
Baselines. We compare XAIFOOLER against four baselines, namely (1) Inherency: the inherent in- stability of LIME due to random synthesis of train- ing examples to train the local surrogate model (Sec. 3); (2) Random: randomly selects a word to perturb and also randomly selects its replace- ment from a list of nearest neighbors (3) Location of Mass (LOM): inspired by Sinha et al. (2021), similar to XAIFOOLER but uses COM (Sec. 5.3) as the explanation similarity function; (4) Lp: sim- ilar to XAIFOOLER but uses L2 (Sec. 5.3) as the explanation similarity function.
Evaluation Metries. Similar to prior works, we report the explanation changes of top-k features using: Absolute Change ranking orders (ABST); Rank Correlation (RCt), which is calculated by the formula: 1- m0 1t-mma00.SppamaannCC Spparman-Correlation(....
k), ed, kl): Intersection Ratio (INS))-i.e., ratio of features remained in top k after perturbation. Morcover, we also report the semantic similar- ity between dy and dp (SIMt) by calculating the cosine-similarity of their vectors embedded using USE (Cer et al., 2018); and the naturalness of d, by calculating its perplexity score (PPL.) using large language model GPT2-Large (Radford et al., 2019)
6 Experiments
6.1 Set-up
Datasets and Target Models. We experiment with three datasets: sentiment analysis (IMDB) (Maas et al., 2011), symptom to diagnosis classification (S2D) (from Kaggle) and gender bias classifica-

---

Average across all Results
Ranking Changes Before and After Perturbation
Method
ABS INS, PPL.
"uuer sick of liberals thinking it's ok to dictate where they think thinking israeli jews should be allowed to live. including israel"
Rnd Order+Rnd Search
3.51 0.40 0.79 0.85 259.23
Rnd Order+Greedy Search
4.63 0.51 0.79 0.91 123.45
Greedy Order+Greedy Search 6,11 0.59 0.73 0.89 157.15
liberals: 1st +
2nd; israeli: 3nd + 4rd; thinking: 5th + lst;
"Greedy Order+Grreedy Scarch": Ours; "Rnd": Random
Table 5: Case Study: Perturbation Examples and the Corresponding Changes in Explainable Feature Rank- ings on Twitter Hate Speech Detection.
Table 4: Both step (Greedy Order) and step (Greedy Search) (Sec. 5.1) are crucial to XAIFOOLER.
Model/
DistiBBERT
BERT
RoBERTA
as a proxy. Arrow 1 and + denote the higher, the better and the lower, the better, respectively.
Dataset
Doc
Token
Doc
Token
Doc
Token
IMDB
331.5
9.1
505.2
13.9
564.9
15.5
Implementation Details. We set 6t-0.1 with minimum allowance of 3 tokens to account for short texts. We use Fig. B.6 to select the hyper- parameter p values of RBO that correspond to 90%, 95%, 95% mass concentrating in the top-5 -k).), top-3 (k+3) and top-2 (k+-2) features for IMDB, S2D and GB dataset, respectively. Based on Sec. 3, we set the sampling rate n such that it is suffi- ciently large to maintain stable change in LIME'S inherent instability, resulting in of 4.5K, 2.5K and 1.5K for IMDB, S2D and GB dataset. During perturbation, we constrain the final perturbed docu- ment to result in at least one of the top & features decreasing in rank to mitigate sub-optimal pertur- bations being accepted ultimately increasing the quality of the final perturbed document by allow- ing us to set lower threshold for the total number of perturbations at the cost of more computational effort. Appendix Sec. A.1 includes the full repro- ducibility details.
S2D GB
242.5
12.0
518.5
25.7
482.1
23,9
188.7
18.2
385.7
36.9
421.1
40.6
Table 6: Average attack runtimes in seconds per docu- ment and token (NVIDIA RTX A4000). ness of using RBO over other similarity function such as Lp and LOM (Sec. 5.4). Evidently, replac- ing any of the procedure steps of XAIFOOLER with random mechanism dropped its performance (Ta- ble 4). This demonstrates the importance of both Step 1 (greedy ordering of tokens to decide which one to perturb first) and Step 2 (greedy search for best perturbations) described in Sec. 5.1.
7 Discussion
Case Study: XAI and Content Moderation. XAI systems are often used in conjunction with Homma--nn-th-lowe tasks such online content moderation-e.2. detecting hate speech fake news, where quality assurance is paramount. Thus, manipulations on such XAI systems will lead to hu- man experts receiving incorrect signals and hence resulting in sub-optimal results or even serious con- sequences. Evaluation of XAIFOOLER on 300 pos- itive examples from a Twitter hate speech detection dataset with k-2 shows that XAIFOOLER often demotes the sst-rank feature out of top-2, reducing RC' to 0.4 and INS to 0.78, while still maintaining the original semanties with SIM90.9. This means X ATFOLLER can force the Al system to output correct predictions but for wrong reasons. Table 5 describes such a case where XAIFOOLER uses the existing "thinking" to replace "think", promot- ing this feature to 1st rank while demoting more relevant features such "liberals" and "isracli".
6.2 Results
Overall. LIME is unstable and vulnerable against text perturbations. Table 3 shows that XAIFOOLER significantly outperformed all baselines by large margins in its ability to manipulate LIME'S explana- tions, showing average changes in AABS1, ARC and AINS) of +1++11100 +128% +101% and -1.63% com- pared to Inherent Instability, and of +22%, +16% and -3.15 15% compared to the 2nd best I, baseline. Moreover, also delivered competitive results for semantic preservation, consistently outperforming all the baselines except LOM,, which showed to be very good at preserving the original seman- tics. This happened because LOM scores often reached 0.5-ic., moving the location of centered mass over 50% of total length, very quickly without many perturbations, yet this did not always guarantee actual changes in feature rankings.
Instability Distribution. Fig. 4 illustrates the dis- tributions of explanation shifts after perturbations on IMDB (S2D, GB results are included in the Appendix). This shows that LIME'S instability ex- presses differently among documents, with some
Ablation Test. Table 3 confirms the appropriate-

---

DiS-DEttIBERT
ABS-BERT
ABS RoBERTO
INS- INS-DRRIBERT
INS-BERT
INS-RoBERTH
1.00
0.75
Dendyy
Random
Inherent
20
20
40
20
0.0 0.5
1.00.0
0.5
1.00.0
0.5
1.0
Figure 4: CDF plots absolute change (ABS*) and k-Intersecttin (INS.)) statistics on IMDB dataset.
are easier manipulate than others. Fig. 4 also shows that if one to calculate attack success rate using a threshold, which often customized to specific applications, XATFOOLER will still con- sistently outperform the baselines.
in Table and especially Fig. 2, where we see a rapid diminishing returns in explanation fidelity as the sample rate n increases. Although our choice sampling rates are already significantly higher than prior works, this reduction in sampling rate was necessary due to the extensive computation time required, with the explanation generating process being the largest proportion of computation time. The extensive computation time prevented exten- sive testing with a large range of sampling rates, especially those higher than the default of n-5K. We leave the question of what effect, any, "over- sampling" with rates much higher than the default has on stability to future work. It remains unex- plored just how much effect the base model itself has the resulting explanation similarity. That is, are certain type of models amplifying LIME'S unstable results? This question also applies the LIME itself. Our choice of surrogate model was the default, but this can be replaced. What are the differences between the choices for local model when it comes to stability?
Document Length v.s. Sampling Rate v.s. Run- time. The majority of computation time is spent generating explanations using LIME. Table 6 shows that the average runtime slowly increases the document length grows while the time per token decreases. Moreover, larger documents have more possibilities for effective perturbations, resulting in a more efficient search and ultimately fewer expla- nations to generate. Shorter documents are faster to run LIME, but require extensive searching to find acceptable perturbations and generate many explanations. Furthermore, for shorter documents the explanations are quite stable even rates much lower than the default, and as the document size increases, lower sampling rate values begin de- grade stability (Fig. 2, Table I).
8 Conclusion
Broader Impacts and Ethics Statement
This paper affirms that LIME is inherently unsta- ble and explanations can be exploited via text perturbations. We re-purpose and apply RBO as a key part of our algorithm XAIFOOLER, which we have shown to provide competitive results against other adversarial explanation generation methods, and do in way that satisfies our criteria from earlier when determining just how best to compare an explanation. Future works include understand- ing the interactions between the target model and LIME that lead to such instability.
The authors anticipate there be no reasonable cause to believe use of this work would result harm, both direct or implicit. Similar to cxisting adversarial attack works in NLP literature, there might be a possibility that malicious actors might utilize this work to manipulate real life Al systems.
However, we believe that the merits of this work in providing insights LIME's s stability outweigh such possibility. Concerns about computational ex- penditure, and the remedies taken to reduce impact, are addressed in Sec. A.1.3. The authors disclaim any conflicts of interest pertaining to this work.
Limitations
Our method and the results collected from used the default settings and parameters for the ex- planation generation framework within TXXTEX- PLAINER* with the exception of the sampling rate This departure is justified by the results shown
Acknowledgements
L. Chen's work is partially supported by the NSF under grant CNS-2245968. The authors thank the anonymous reviewers for their many insightful comments and suggestions.
"https://elis htairr///// readthedoss.hc.ii

---

References
Ravi Kumar and Sergei Vassilvitskii. 2010. Generalized distances between rankings. In Proceedings of the 19th International Conference World Wide Web, WWW '10, page 571-580, New York, NY, USA. Association for Computing Machinery.
David Alvarez-Melis and Tommi Jaakkola. 2018. On the robustness of interpretability methods. ICML.
Workshop on Human Interpretability in Machine Learning (WHI 2018).
Nesaretnam Barr Kumarakulasinghee Tobias Blomberg. Jintai Liu, Alexandra Saraiva Leao, and Panagiotis Papapetrou. 2020. Evaluating local interpretable model-agnostic explanations on clinical machine learning classification models. In 2020 IEEE 33rd In- ternational Symposium on Computer-Base Based Medical Systems (CBMS), pages 7-12. IEEE.
Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Cespeddes Steve Yuan, Chris Tar, et al. 2018. Universal sentence encoder. arXiv preprint 1rXivv1803.11111
Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and
Kristina Toutanova. 2019. BERT: pre-training of deep bidirectional transformers for language under- standing. Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies (NAACL-HLT), pages 4171-4188
Piyawat Lertvittayakumjor and Francesca Toni. 2021, Explanation- human debugging of NLP mod- els: A survey. Transactions of the Association for Computational Linguistics, 9: -58--8555
Yinhan Liu, Myle Ou, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. RoBERTa: robustly optimized BERT pretraining approach. arXiv preprint arXiv:1907. 1699..
Emily Dinan, Angela Fan, Ledell Wu, Jason Weston, Douwe Kiela, and Adina Williams. 2020. Multi- dimensional gender bias classification. In Proceed- ings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 314-331, Online. Association for Computational Lin- guistics.
Andrew L.. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. 2011. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. pages 142-150, Portland. Oregon, USA. Association for Computational Lin- guistics.
Finale Doshi-Velde and Been Kim. 2017. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08661
Jordan D Fuhrman, Naveena Gorre, Qiyuan Hu, Hui Li, Issam EI Naqa, and Maryellen L. Giger. 2022. A review of explainable and interpretable ai with applications in covid- 19 imaging. Medical Physics, -9(1):1114
Dina Mardaoui and Damien Garreau. 2021. An analysis of LIME for text data. International Conference on Artificial Intelligence and Statistics, pages 3493- 3501. PMLR.
Damien Garreau and Ulrike Luxburg. 2020. Explaining the explainer: first theoretical analysis of LIME. In International Conference on Artificial Intelligence and Statistics, pages 1287-1296. PMLR.
Aniek F. Markus, Jan A. Kors, and Peter R. Rijnbeek. 2021. The role of explainability in creating trustwor- thy artificial intelligence for health care: A compre- hensive survey of the terminology, design choices, and evaluation strategies. Journal of Biomedical In- formatics, 1 113:103655.
Damien Garreau and Ulrike von Luxburg. 2020. Look- ing deeper into tabular LIME. arXiv preprint arXiv:2008.1100 11092.
Christoph Molnar. 2022. Interpretable Machine Learn- ing. 2nd edition.
Amirata Ghorbani, Abubakar Abid, and James Zou, 2019. Interpretation of neural networks is fragile. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3681-3688.
John X. Morris, Eli Lifland, Jin Yong Yoo, Jake Grigsby. Di Jin, and Yanjun Qi. 2020. Textattack: A frame- work for adversarial attacks, data augmentation, and adversarial training in nlp.
Alex Gramegna and Paolo Giudici. 2021. Shap and lime: an evaluation of discriminative power in credit risk. Frontiers in Artificial Intelligence, 4:752558.
Tien N Nguyen and Raymond Choo. 2021. Human-in- the-loop xai-enabled vulnerability detection, inves- tigation, and mitigation. In 2021 36th IEFF/ACM International Conference on Automated Software En- gineering (ASE), pages 1210-1211 IEEE.
Adam Ivankay, Ivan Girardi, Chiara Marchiori, and Pascal Frossard. 2022. Fooling explanations in text classifiers. International Conference on Learning Representations (ICLR).
Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. 2020. BERT really robust? a strong baseline for natural language attack on text classifica- tion and entailment. In Proceedings of the AAAI con- ference on artificial intelligence, volume 34, pages 8018-8025.
Samira Pouyanfar, Saad Sadiq. Yilin Yan, Haiman Tian, Yudong Tao, Maria Presa Reyes, Mei-Ling Shyu, Shu-Ching Chen, and Sundaraja S Iyengar. 2018. A survey deep learning: Algorithms, techniques, and applications. ACM Computing Surveys (CSUR). 51(5):1-36.

---

Alec Radford, Jeff Wu, Rewon Child, David Luan. Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners.
A
Reproducibility
A.1 Implementation Details
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016. "Why should I trust you?" Explain- ing the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135- 1144.
This section provides all details needed to repro- duce our experiment results. The open-source implementation is available at: https: / thub.
Com//bburgerllemiss///
A.1.1 Hardware
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019. DistilBERT, distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint urXiv:1910.000 108.
Facts and figure relating computation time were generated using single NVIDIA RTX A4000 on virtual workstation with 45 GiB RAM.
Sanchit Sinha, Hanjie
Chen, Arshdeep Sekhon, Yangfeng Ji. and Yanjun Qi. 2021. Perturbing inputs for fragile interpretations in deep natural language processing. arXiv preprint arXiv:2/08.0490
A.1.2 Frameworks Software
We use an off-the-shelf LIME implementation, TEXTEXPLAINER, itself subset of the popular explanability package EL15 TEXTEXPLAINER provides extensive functionality for formatting and printing explanation output. XAIFOOLER is imple- mented using the TEXTÁTTACK framework (Mor- ris et al., 2020), a full featured package designed for adversarial attacks in natural language. TEX- TÄTTACK'S is design offers the ability to quickly ex- tend or implement most aspects of the adversarial example generation workflow.
Dylan Slack. Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. 2020. Fooling LIME and SHAP: Adversarial attacks on post hoc explanation methods. In Proceedings of the AAAI/ACM Confer- ence AI, Ethics, and Society, pages 180-186.
Ilia Stepin, Jose M Alonso, Alejandro Catala, and Martín Pereira-Farriia. 2021. survey contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access, 9:1 197497--100
A.1.3 Parameter Selection
Erico Tjoa and Cuntai Guan. 2020, survey on explain- able artificial intelligence (xai): Toward medical xai. IEEE transactions on neural networks and learning systems, 32 48:333348813.
Our values for the RBO weighting were 0.75, 0.49, and 0.32 respectively for the IMDB, S2D, and GB datasets. These values were determined based on the attributes in Sec. 5.2 and the average length of the explanation features. Shorter document lengths generate smaller explanations, and so have more importance associated with the smaller number of features. We must treat altering the positions the top 5 features in an explanation with 7 total features as more significant than for an explanation with 150 features. This significance is controlled by the RBO value with smaller value assigning more importance to the top features.
William Webber, Alistair Moffat, and Justin Zobel. 2010. A similarity measure for indefinite rankings. ACM Transactions Information Systems (TOIS), 28(4):1- 38.
John Wieting, Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2015. From paraphrase datahase to compo- sitional paraphrase model and back. Transactions of the Association for Computational Linguistics, 3:345- 358.
Xinyang Zhang, Ningfei Wang. Hua Shen, Shouling Ji. Xiapu Luo, and Ting Wang. 2020. Interpretable deep learning under fire. In 29th USENIX security symposium ( (USENIX security 20).
Our values for the sampling rates were 4,500, 2,500, and 1,500 respective for the IMDB, S2D, and GB datasets. These values were derived based on the analysis shown in Fig. 2 where the baselines for the inherent stability were determined. Our goal is to balance explanation fidelity and running time, as is seen in Table 6 the computational expenditure for this process is extensive.
The maximum perturbation budget was set 20% of the total document length (rounded up as to guarantee at least one perturbation). This budget
h/ttps://el15.. rew.hiedossdcccccccs.oooooo io/

---

is lower than some other work in adversarial expla- nations, but the requirement for consistency in the meaning of the perturbed document necessitated a modest limit to the perturbations. This consistency, especially for larger documents, began to degrade appreciably beyond ~20
of Fi and F2 J(F,F2) despite no pair of values having an equal position. These lists are clearly different, but the Jaccard Index does not have the capacity to differentiate between them. Additionally, the Jaccard Index assigns an equal value, related to the total number of elements, for any dissimilarity between the lists. For example, let
B Motivating RBO
Fi = [a, b, C, ... 2, 9/
Our use of RBO follows from our choice of desired
F2 = |a, b, C, I, y. F3 = (a, b, C, 2. y, W]
attributes in Sec. 5.2. Here we provide examples to justify our selection of similarity measure ex- panding on the summary in Table 2. Note that the weight-basee based distances Lp. and LOM are different enough from the structure of the feature-based mea- sures like RBO that direct comparison difficult. Their construction gives them particular strengths but they fundamentally are unable to satisfy our desired attributes. They remain included as impor- tant metrics used for comparison against the other similarity measures.
With F1 being ordered by weight in decreasing importance.
Finally let weight(a)) weight(a) and weight(y) weight(w) weight(z).
Then we have J(Fi. F2) = I(Fi, Fg).
However, RBO can be compared directly to the Jaccard and Kendall Spearman similarities. We do so in Fig. where we demonstrate two of RBO's advantages. First, RBO provides some capacity for determining similarity when using features not within the selected top k. Second, the weighting scheme associated with RBO allows more granu- larity when determining similarity; in other words, the similarity output is smoother due the weight assignment, which lacking with the other mea- sures. Here a fixed list of 50 features is generated, which is then uniformly shuffled 50,000 times. The results are plotted according to the similarity out- put from each of the measures with respect to the top 5 features. We see RBO allows some small amount of similarity to remain desipte assigning the significant majority of the mass the top features. The other measures return 0 similarity for over half the permutations, as our requirement for a concise explanation allows us only to concentrate on the top few features. The other measures show poorer delineation between important features (as determined by position in the top 5), resulting in the step-wise behavior (explained more in the mea- sure's 's respective subsections below).
Clearly the similarity between F1 and Fg should be considered less than F1 and F3 as we have ad- ditional information pertaining to each feature's importance.
B.2 Kendall's & Spearman's p
Kendall's & Spearman's are subject to similar issues affecting the Jaccard Index. Both and p can handle the first scenario, while the Jaccard Index could not. That is, for Fi [a, b, c] and F2 [c, b, al then Kendall(Fi.Fe) + and Spearman (FearmanFFi.FF) F2) * 1. However, т and are similar to Jaccard in that the difference between weighted features has not been taken into account. For example, let
Fi = [a, b, c, c..,
F2 = [b, a, C,.,, 8, 2]
F3 fa, b,
...,, C,.,,
Then Kendall(F1, F2) Kendall(F1, Fs), and Spearman(Fi, F2) SppermmanFF.... Fz).
The exchange between features and b should be considered more important than the exchange between features y and The resulting value is also related to the size of the lists, and a single exchange two adjacent becomes less important as the size the lists grows larger.
B.1 Jaccard Index
The Jaccard Index, being entirely set-based, preserves no order between two lists of feature explanations. For collections of features Fi = [a, b, c] and Fz = [c, b, a] the Jaccard Index

---

ABS-DistIBERT
ABS-BERT
ABS-RoBERTa
INS-DIstIBERT
INS-BERT
INS-RoBERTa
Density
Random
0.0
XAlFooler
10
10
20
0
10
20
0.0
0.5
1.00.0
0.5
1.00.0
0.5
1.0
ABS DistilBERT
ABS BERT
ABS RoBERia
INS DistilBERT
INS-BERT
INS RoBRTa
1.0
Density
0.5
0.0
0.0
2.5
5.0
0.0
2.5
5.0
0.0
0.5
1.00.0
0.5
1.00.0
0.5
1.0
Figure B.5: CDF plots of absolute change (ABS1) and k-Intersection (INS.) statistics S2D (top) and GB (hottom) dataset.
B.3 Lp
#
# of Labels
Dataset
DistilBERT BERT RoBERTa
Tokens
Lp discards positional importance and instead con- centrates on the weights associated with the fea- tures. We can encounter a scenario where the or- der of the features identical, but the weights have shifted enough provide a substantial Lp distance. Consider list of features Fi = [[a, b, c] and F2 [a, b, c] with weights W1 = [3, 2, 1] and W2 [1, 2]. Clearly the Ly distance here will be non-zero, but the position of the features remains identical. Does the change in total weight matter? It may, and Lp is well specified if that is the case. However, may not necessarily understand just how important the differences between weights are. Because of this, we do not wish set thresh- old for significance between the two explanations purely on a distance between the weights. We in- stead appeal to the position of the features, a coarse form of weighting, and use our own scheme for weight importance that concentrates the weights in easily tuned manner of our own choosing.
IMDB
230
2
0.91
0.92
0.94
S2D
29
21
0.94
0.93
0.97
GB
11
2
0.90
0.90
0.89
Table B.7: Dataset statistics and prediction performance (Fl Score) of target classification models on test set.
Fi la, b,, F2 = (a, b, d.
With weights Wi = (1,0,5,0, W₂ = 1, 1.2, 2, 1.3,
Both collections of features possess the same total weight, and the same location of mass (center). But F2 has significantly different assignment of weights and it reasonable conclude that this explanation is different.
Additionally, for certain explanations that are highly concentrated in weight may not be feasi- ble to find perturbations that are able to distribute this among other features to the extent necessary to move the location of mass. For example, let W3 [1,2, 2, 1, 1000, 2, 2, 1]. We would have redis- tribute the overwhelming majority of the weight the other features order to move this location of mass away from index
B.4 Location of Mass
While Lp determines that weight shifting. LOM provides insight into where it is moving. the location (usually center) of the cumulative weights has shifted, then more weight has been assigned to or away from certain features and so the explanation must then be different. LOM has issues similar to Lp in that the actual location of mass may shift despite weight being changed significantly among many features. For example, consider the lists of features

---

Mass Attributed to top the k Features
1.0
Combined Mass
0.8
0.6-
k (GB)
0.4
(S2D)
k (IMDB)
90% Combined Mass
0.2
95% Combined Mass
0.0
0.2
0.4
0.6
0.8
1.0
p
Figure B.6: Mass associated with the top k features for different values of RBO's hyper-parameter
C Other Supplementary Materials
1. Statistics of experimental datasets and the per- formance of target models on their test sets (Table B.7)
2. Relationship between combined distribution mass, &t and hyper-parameter of RBO (Fig. B.6)
3. CDF plots for GB and S2D Datasets (Fiig. B.5)


Reviews:
[{"review_id": "Wcvk53rMGC", "reviewer": "Reviewer_BX5w", "summary": "", "questions": "- Question A: The Disjoint Features requirement seems to be due to simplify your implementation and\n  not due to some desirable property. Is it?\n\n  Possibly related, the example Table 5 has no \"think\" in the perturbed output. What is thus the\n  ranking of \"think\" in that perturbation?\n\n- Question B: Table 3 has a lot of metrics shown. I imagine each of the metrics can be made an\n  optimization goal in an explanation attack which would then give it an advantage in terms of that\n  metric at least. Can you adjust your method at least with different target goals and see whether\n  they are independently optimizable?", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary:** The authors would like to thank the reviewer for their substantial effort in enumerating their concerns and opinions. Especially, we appreciate the extensive nature of the provided suggestions. Given the potential positive impacts of our work in promoting a more secure and robust XAI and hence encouraging the adoption of XAI in practice, we respectfully ask the reviewer to reconsider the following main concerns. First, regarding the source of instability concern. We have already varied different components in our experiments (e.g., target model, dataset) while consistently using the LIME’s default setting to minimize the confounding effects on our instability analysis. Even with these efforts, we also acknowledged in the Limitation section regarding this concern as an out-of-scope direction for future work. In addition to this concern, we recognize that the remaining provided suggestions (listed in the “reasons to reject” box) did not constitute major technical or methodology flaws of our work and hence we respectfully ask the reviewer to reconsider these in the final scoring.\n\nWe appreciate and fully address the suggestive feedback from the reviewer below and also in our final manuscript.\n \n \n\n> Concerns/suggestions regarding source of instability\n\nTo control model instability, we have preserved its original prediction and further explored setting a bound on the difference between output probabilities for original and perturbed texts. Initial investigations revealed only slight differences. We thus removed this constraint in the final experiments to align with general adversarial attack paradigms where attack success is based on class output rather than direct probability differences.\n\nOne of our primary, if unstated goals, was to closely adhere to the “standard” LIME usage for better generalization to common practitioner use cases by avoiding changes from the default. Maintaining default LIME settings also facilitated greater-depth testing across three diverse datasets and target transformer models. While recognizing the importance of exploring alternative LIME settings and components, we consider this a natural next step for future research.\n\nWe also appreciate the suggestions of directly perturbing the word embedding of the target model. While further experimentation is necessary to determine whether perturbing word embeddings would yield greater stability, our focus is to design a threat model that is realistic and practical, which often assumes that a white-box access to the target model’s parameters (e.g., embedding layers) is unavailable.\n\nMost importantly, we have *acknowledged the source of instability as one of out-of-scope topics in the Limitation section* and considered this as a future work.\n\n> Concerns regarding sample complexity of LIME’s learning model and suggestion on investigating smaller models and the unnecessity of using state-of-the-art models\n\nWe use LIME’s default Logistic Regression learning model, which is a sufficiently simple model for this purpose. Most importantly, we are not trying to train LIME’s learning model to approximate the complex transformer models such as BERT and RoBERTa  as a whole but only their decision boundaries on a small, local vicinity surrounding a single data point. This requires a much smaller sampling rate. Evidently, Figure 2 shows that a much larger sampling rate is not needed as the stability reaches a plateau after the sampling rate reaches a certain threshold that is close to LIME’s default, recommended sampling rate. \n\nWe here provide the following data from a simple feed-forward neural network (FNN) on two NLP datasets. Here the measure is reported in RBO (the lower the better). As we can observe, our framework is still able to perform well on a simple FNN model, achieving low RBO scores similarly to when tested with complex target models BERT and RoBERTa.\n\n| Model | Dataset | RBO |\n|---|---|---|\n| FNN | IMDB | 0.42 |\n| BERT | IMDB | 0.44 |\n| FNN | Twitter Hate Speech | 0.33 |\n| RoBERTa | Twitter Hate Speech | 0.44 |\n\n> Concerns regarding that the top features does not change and constraints in Eq. (5)\n\nThe reviewer might have misunderstood our writings and we would like to clarify as follows. Our intent behind Eq. (5) is only to prevent the perturbation of features that are considered significantly important by LIME. Our primary concern is that if they are candidates for perturbation, the results become uninteresting in that changing an important feature results in an appreciable change in the explanation. We are unconcerned with the location of this feature, just that it remains within the explanation. So, we agree with the reviewer that Eq. (5) actually makes our problem more challenging and practical, hence worth investigating.\n\n> Concerns regarding dismissing comparisons with white-box attacks as baselines\n\nWe intentionally scoped our paper as a black-box attack due to two reasons. First, black-box attack is more realistic in practice, which makes our analysis closer to what will happen in real life where the text perturbation process does not require parameters access to the target model. Second, black-box attack is aligned with the original purpose of LIME being a post-hoc explainer for black-box models. Regardless, our framework is also compatible with white-box attacks in NLP such as HotFlip as pointed out by the reviewer. \n\n> Concerns regarding Table 5\n\nThe word replacement in table 5 is algorithmically correct, but the reviewer makes an excellent point in that the replacement might come across as not truly semantically valid without further explanation. We would like to clarify as follows. The perturbation algorithm constraints for part of speech replacement only work at word level, so while the perturbation from think -> thinking passes the algorithm’s checks as both can exist in different sentences but are the same type of word, and the resulting replacement in the sentence itself may be “out of bounds”. We will elaborate in the final manuscript to emphasize that the constraints here only apply to world level replacements.\n\n> Concerns regarding performance comparison with a random baseline\n\nIn addition to the random perturbation baseline, we also carefully select other non-random baselines (Inherency, LOM, L_p)  in relevant literature as shown in our main experiment results. Moreover, we also provide an ablation study to analyze the performance gain of different components of the proposed framework. \n\n> Disjoint features requirement \n\nWe want to clarify that this feature is a desired property or a requirement. Generally speaking, should a feature be selected for perturbation that occurs repeatedly within the document, the resulting perturbed explanation will have its previous length plus one for the new word now within the document.\n\n> Suggestion on using other metrics for optimization\n\nOur inclusion of multiple comparative metrics was focused towards providing a justification for RBO as an efficient measure of similarity. Our goal is chiefly to demonstrate instability in LIME, the choice of RBO is just a means to do so in a manner that satisfies the requirements we set out in Section 5.3. The other metrics have seen use in similar related work, we felt that empirical justification of RBO was necessary rather than an argument solely from desiderata of Section 5.3. \n\n> Low reproducibility score (3.0 score)\n\nWe respectfully disagree with a low given reproducibility score. We have provided details on reproducibility in the Appendix section and in the main text, including specific hardwares, software, datasets, sampling rates, RBO parameters and other hyper-parameters needed to reproduce the results. We also mentioned that we will open-source all implementations. We also endeavored to maintain as close to the default settings for the packages used (e.g., LIME) as possible to avoid only a shallow investigation among different datasets and models due to concerns of the appearance of cherry picking / anomalous sampling", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "+ Proposed method has overall better performance at least in terms of the metrics tested.\n\n+ Several baselines compared experimentally.", "reasons_to_reject": "- While studying instability of LIME, the work likely confuses that instability with various\n  other sources of instability involved in the methods:\n\n  - Instability in the model being explained.\n\n  - Instability of ranking metrics used.\n\n  - Instability of the LIME implementation used. This one drops entire words instead of perturbing\n    embeddings which would be expected to be more stable. Dropping words is a discrete and\n    impactful process compared to embedding perturbation.\n\n  Suggestion: control for other sources of instability. That is, measure and compare model\n  instability vs. resulting LIME instability; measure and compare metric instability vs. resulting\n  LIME instability. Lastly consider evaluating the more continuous version of input perturbation\n  for LIME based on embeddings. While the official implementation does not use embeddings, it\n  shouldn't be too hard to adjust it given token embedding inputs.\n\n- Sample complexity of the learning LIME uses to produce explanations is not discussed. LIME\n  attempts to fit a linear model onto a set of inputs of a model which is likely not linear. Even\n  if the target model was linear, LIME would need as many samples as there are input features to be\n  able to reconstruct the linear model == explanation. Add to this likelihood of the target not\n  being linear, the number of samples needed to estimate some stable approximation increases\n  greatly. None of the sampling rates discussed in the paper is suggestive of even getting close to\n  the number of samples needed for NLP models.\n\n  Suggestion: Investigate and discuss sample complexity for the type of linear models LIME uses as\n  there may be even tight bounds on how many samples are needed to achieve close to optimal/stable\n  solution.\n\n  Suggestion: The limitations discusses the computational effort is a bottleneck in using larger\n  sample sizes. I thus suggest investigating smaller models. It is not clear that using\n  \"state-of-the-art\" models is necessary to make the points the paper is attempting to make.\n\n- Discussions around focus on changing or not changing the top feature are inconsistent throughout\n  the work and the ultimate reason behind them is hard to discern. Requiring that the top feature\n  does not change seems like a strange requirement. Users might not even look at the features below\n  the top one so attacking them might be irrelevant in terms of confusing user understanding.\n\n       \"Moreover, its experiment settings are not ideal as it allows perturbations of top-ranked\n        predictive features, which naturally change the resulting explanations\"\n\n  Isn't changing the explanations the whole point in testing explanation robustness? You also cite\n  this point later in the paper:\n\n       \"Moreover, this requirement also accounts the fact that end-users often consider only the\n        top k most important and not all of the features\"\n\n  Use of the ABS metric which focuses on the top-k only also is suggestive of the importance of top\n  features. If top features are important, isn't the very top is the most important of all?\n\n  Later:\n\n       \"... changing the most important features will likely result in a violation to constraint in\n        Eq. (2)\"\n\n  Possibly but that is what makes the perturbation/attack problem challenging. The text that\n  follows does not make sense to me:\n\n       \"Moreover, this will not provide any meaningful insights to analysis on stability\n        in that we want to measure how many changes in the perturbed explanation that\n        correspond to small (and not large) alterations to the document.\n\n  I do not follow. The top feature might change without big changes to the document.\n\n  Suggestion: Coalesce the discussion regarding the top features into one place and present a\n  self-consistent argument of where and why they are allowed to be changed or not.\n\nSmaller things:\n\n- The requirement of black-box access should not dismiss comparisons with white-box attacks as\n  baselines.\n\n- You write:\n\n      \"As a sanity check, we also constrain the final perturbed document to result in at least one\n      of the top k features decreasing in rank.\"\n\n  This does not sound like a sanity check but rather a requirement of your method. If it were\n  sanity check, you'd measure whether at least one of the top k features decreased without imposing\n  it as a requirement.\n\n- The example of Table 5 seems to actually change the meaning significantly. Why was such a change\n  allowed given \"think\" (verb) and \"thinking\" (most likely adjective) changed part of speech?\n\n- You write:\n\n      \"Evidently, replacing any of the procedure steps of XAIFOOLER with a random mechanism dropped\n      its performance\"\n\n  I'm unsure that \"better than random\" is a strong demonstration of capability.", "questions_to_authors": "- Question A: The Disjoint Features requirement seems to be due to simplify your implementation and\n  not due to some desirable property. Is it?\n\n  Possibly related, the example Table 5 has no \"think\" in the perturbed output. What is thus the\n  ranking of \"think\" in that perturbation?\n\n- Question B: Table 3 has a lot of metrics shown. I imagine each of the metrics can be made an\n  optimization goal in an explanation attack which would then give it an advantage in terms of that\n  metric at least. Can you adjust your method at least with different target goals and see whether\n  they are independently optimizable?", "paper_topic_and_main_contributions": "The work describes the evaluation of the \"stability\" of explanations of input importance in NLP\nmodels as computed by the LIME method. The method involves making small perturbations in the inputs\nso as to preserve their meaning but to change the explanations in terms of producing different\nrankings of most important input words. Various metrics are tested for both preservation of meaning\nduring perturbation and the resulting explanation dissimilarity. Compared to several baselines, the\npresented work termed \"XAIFooler\" does mostly better save for various points where it is beat in\nterms of input semantic preservation by one baseline method. The paper uses these results to both\ndemonstrate the better performance of their perturbation method and to argue that LIME explanations\nare inherently unstable.", "excitement": 2, "reproducibility": 3, "ethical_concerns": "Yes", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Justification_for_Ethical_Concerns": "Minor: the work describes attacks on model explanations but offers no prescriptions how to prevent\nor defend against them. It is unbalanced towards the negative side of the societal impacts scale."}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "- The term \"ranked list\" is used several times but it is not clear whether that includes scores of\n  the items in the list. Please define or used a different term before first use. The description\n  of Feature Weighting suggests scores are part of ranked list.\n\n- Line 353: \"explanation similarity\" -> \"explanation dissimilarity\""}}, {"review_id": "lB2gP16OTJ", "reviewer": "Reviewer_bxaW", "summary": "", "questions": "A. Is it possible to provide examples of base and perturbed documents? \n\nB. Do you think XAIFooler can be applied to other XAI methods besides LIME, e.g., SHAP or GradCAM?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary:** The authors would like to thank the reviewer for their time and especially for their cogent summary of the paper. We would like to address the concerns listed below.\n\n> Connection between LIME’s instability and XAIFooler perturbation method\n\nThe initial instability exploration resulted from questions about the effectiveness of early forms of XAIFooler. In related works we saw a lack of discussion on what levels of inherent instability imparted due to LIME’s sampling process within the explanation generation. In order to avoid reporting seemingly significant results that fell within whatever baseline instability already exists (For example, in Figure 2 if a perturbed document’s similarity under a comparable measure returned ~80%, we would not be able to make an effective judgment that it was unstable due to the baseline being ~75% on an unperturbed document), we sought to establish a reasonable minimum sample rate that balanced explanation convergence and performance. We consider XAIFooler as an extension of the exploration of the instability associated with LIME (or other similar methods, see our more specific response to your question about generalizability of XAIFooler to other XAI methods) beyond the initial instability resulting from the sampling process. The authors would gladly clarify the connection between XAIFooler itself and the initial instability discussion as a revision.\n\n>  Is it possible to provide examples of base and perturbed documents?\n\nBoth figure 1 and table 5 are actual output of the process, with the blue text the original word(s) and the red text the chosen substitutions. We have included one of them in the table below from the symptom to diagnosis classification (S2D) dataset and Twitter hate-speech detection dataset.\n\n| Original Text | Perturbed Text | Original Features (Ordered by ranks) | Perturbed Features (Ordered by ranks) |\n|---|---|---|---|\n| I have a skin rash that gets worse in the winter. I have to moisturize more regularly and have [...] I also have joint pain | I have a skin rash that becomes worse in the winter. I have to moisturize more consistently and have [...] I also have joint pain | skin winter joint moisturize regularly worse gets air dry use moisturized painrash humidifiers | skin rash worse pain winter moisturized moisturize dry humidifiers consistently joint use air |\n| @user sick of liberals thinking it's ok to dictate where they think israeli jews should be allowed to live, including in isrâ | @user sick of liberals thinking it's ok to dictate where they thinking israeli jews should be allowed to live, including in isrâ | liberals isrâ israeli jews thinking allowed | thinking liberals isrâ israeli jews dictate |\n\n> Do you think XAIFooler can be applied to other XAI methods besides LIME, e.g., SHAP or GradCAM?\n\nXAIFooler can be used directly with any post-hoc XAI method that returns a tuple of features such as LIME or SHAP. For methods that lack a relative ordering of the feature importance XAIFooler is compatible but requires an appropriate choice of similarity measure, namely for RBO the weight associated with each feature must be considered equal which can be adjusted simply by altering RBO’s dedicated weighting parameter.\n\nBy enabling XAIFooler to accept white-box classification model, it will be compatible with other XAI methods that are gradient based such as GradCAM. However, we are uncertain if we will observe similar trends in the instability results. The authors consider it an important question, both in the specific case for XAIFooler directly, and in the general case where the entire corpus of related work in text stability can generalize to gradient based methods.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This is a well-written paper, and easy to follow. The algorithm is well-articulated, and framing it as an adversarial text generation optimization problem makes sense. I appreciate the careful baseline comparisons in Table 3, as well as the extensive ablations which show (1) that RBO is a well-suited similarity function, and (2) both greedy ordering and greedy search are integral to XAIFooler's good performance. Additionally, the case study in the Discussion section on content moderation underlines the importance of building AI systems that are robust against adversarial input produced by the likes of XAIFooler. \n\nOverall, minor changes aside, I like this paper and would like to see it accepted for publication.", "reasons_to_reject": "One weakness to this paper is that it is not clear to me the linkage between the fundamental instability of LIME, and how XAIFooler is meant to affect this instability. I'm not really convinced by the justification in L246-L251, since it seems like we are talking about two different issues here: LIME produces inconsistent results when the sampling rate is varied, and LIME can further be induced to produce inconsistent results when provided a minimally perturbed document. I think a more in-depth explanation or re-framing is in order here.", "questions_to_authors": "A. Is it possible to provide examples of base and perturbed documents? \n\nB. Do you think XAIFooler can be applied to other XAI methods besides LIME, e.g., SHAP or GradCAM?", "paper_topic_and_main_contributions": "This paper's contributions are twofold. First, this paper demonstrates the fundamental instability of a popular explainability technique, LIME (Ribeiro et al., 2016), which displays inconsistent explanation results on textual experiments just by varying the sampling rate (the number of local training examples used to train its surrogate model), without alterations to input or model parameters. \n\nSecond, this paper additionally contributes an adversarial attack algorithm, XAIFooler, which can distort the explanations produced by LIME via minimal text perturbations. Formulated as an adversarial text attack optimization problem, this algorithm takes in an input document and conducts an iterative greedy word selection / search process, ultimately returning a perturbed document that fulfills a list of constraints: 1). its explanations should be maximally different, 2). the original prediction is preserved, 3). there is sufficiently large semantic similarity between the base and perturbed documents, 4). the number of possible perturbations is constrained, 5). the top-k ranked features from the base explanation likewise also appear in the perturbed explanation. \n\nThe paper also makes a point to identify a good explanation similarity function, which should account for positional importance, the continuous weights of feature importance scores, disjoint features, and unequal list lengths. The paper identifies Rank-based Overlap (RBO) as a suitable candidate among several other measures. Across three textual classification tasks and three BERT-based models, XAIFooler displays sufficiently convincing results at 1). distorting the explanation feature ranking, 2). maintaining adequate similarity between old and perturbed documents, 4). maintaining naturalness of text via the perplexity.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Grammar:\n\nL434: \"(Kumar and Vassilvitskii, 2010)\" -> \"Kumar and Vassilvitskii, 2010\"\n\nL492: \"inspired by (Sinha et al., 2021)\" -> \"inspired by Sinha et al., 2021\""}, "extra_text": {}}, {"review_id": "dHK7QsYA31", "reviewer": "Reviewer_pyA2", "summary": "", "questions": "- Question A: What are the main differences between this work and Location of Mass (Sinha et al., 2021)?\n- Question B: What is the necessity of constraint of eq (5)?\n- Question C: Please provide some of the examples generated by XAIFOOLER.\n", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary:** The authors would like to thank the reviewer for their valueable time and feedback. We respectfully ask the reviewer to reconsider our work's novelty beyond the baseline Location of Mass (Since et al., 2021) as we proposed a very different experiment setting and constraints. We would like to address all of the concerns in detail as follows.\n\n> Differences from Location of Mass (Sinha et al., 2021)\n\nWe view our work as complementary to the Location of Mass paper (Sinha et al., 2021) in that by establishing a starting point for investigation through an understanding of the inherent instability other strategies for measuring the robustness of XAI methods can result in more *meaningful conclusions*. We consider our contributions to be threefold:\n\n**(1) An exploration of the inherent instability within LIME:** Determining levels of instability within LIME before any perturbations are applied is necessary to produce meaningful results in future work. By establishing such data we can provide a way to prevent inappropriate conclusions from being drawn to due sampling bias. This strengthens future research efforts in that more reasonable judgments can be made about LIME’s efficacy. We also want to emphasize that our sampling rate is not only set as a much larger value (e.g., 9x on IMDB dataset) compared to Location of Mass (Sinha et al., 2021) and hence a more challenging experiment setting, the introduction of the inherent instability analysis also provides reasonings on which minimally sufficient sampling rate to be used.\n\n**(2) A systematic motivation on the proper selection of similarity measure for adversarial XAI:** As the similarity measure is the heart of the comparison between explanations, it is directly responsible for the conclusions drawn from the experiments. By motivating specific requirements based on both the general adversarial XAI process, and the individual particulars of LIME itself we can again draw more systematic conclusions. Thus, the provided insights and reasons on how RBO is different from existing metrics such as LOM and L_p is not merely a random adoption, and serves as a framework for meaningful discussion in future works.\n\n**(3) A meaningful search methodology and practical threat model:** Different from Location of Mass (Sinha et al., 2021) which allows perturbations of important, top-ranked explanation features/words, our choice to perturb the unimportant words initially gives us the advantage of casting the adversarial process directly and practically in terms of the definition of stability where small input changes should result in small output changes in real life. We do consider the LOM measure as interesting and underutilized with respect to text data. And especially well suited for addressing the similar research question where the most important features are selected for perturbation, testing the stability in terms expecting significant changes in the resulting explanation for changes in the important feature(s). We instead elected to pursue the search for perturbations of unimportant features in contrast to some related work to demonstrate this instability in a way that is analogous to traditional adversarial attack on text models with subtle perturbations. This subtlety we felt would be best achieved by avoiding perturbations of important words in the explanation due to the large changes in explanation similarity despite otherwise quality substitutions.\n\n> Necessity of constraint of eq (5)\n\nWe think that our descriptions of Eq. (5) might come across as a misunderstanding. Our intent behind Eq. (5) is only to prevent the perturbation of features that are considered significantly important by LIME. Our primary concern is that if they are candidates for perturbation, the results become uninteresting in that changing an important feature results in an appreciable change in the explanation. We are unconcerned with the location of this feature, just that it remains within the explanation. Hence, Eq. (5) actually makes our problem more challenging and practical, hence worth investigating. \n\n> Some of the examples generated by XAIFOOLER\n\nBoth figure 1 and table 5 are actual output of the process, with the blue text the original word(s) and the red text the chosen substitutions. We have included one of them in the table below from the symptom to diagnosis classification (S2D) dataset and Twitter hate-speech detection dataset.\n\n| Original Text | Perturbed Text | Original Features (Ordered by ranks) | Perturbed Features (Ordered by ranks) |\n|---|---|---|---|\n| I have a skin rash that gets worse in the winter. I have to moisturize more regularly and have [...] I also have joint pain | I have a skin rash that becomes worse in the winter. I have to moisturize more consistently and have [...] I also have joint pain | skin winter joint moisturize regularly worse gets air dry use moisturized painrash humidifiers | skin rash worse pain winter moisturized moisturize dry humidifiers consistently joint use air |\n| @user sick of liberals thinking it's ok to dictate where they think israeli jews should be allowed to live, including in isrâ | @user sick of liberals thinking it's ok to dictate where they thinking israeli jews should be allowed to live, including in isrâ | liberals isrâ israeli jews thinking allowed | thinking liberals isrâ israeli jews dictate |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The paper is well-written and clear.\n- The study of the inherent instability of LIME is interesting.\n- The experiments are thorough, and the attack outperforms the baselines.", "reasons_to_reject": "- The method is very similar to the method of Location of Mass (Sinha et al., 2021). It seems that the only difference is the metric used to find the similarity between two explanations (RBO vs COM) and the larger sampling rate. This makes the contribution of the paper limited.\n\n- It is not clear why the k important features must appear in the perturbed explanation (eq (5)). It is necessary that the top k features not be perturbed by the attack, but it does not seem necessary that they appear in the perturbed explanation.", "questions_to_authors": "- Question A: What are the main differences between this work and Location of Mass (Sinha et al., 2021)?\n- Question B: What is the necessity of constraint of eq (5)?\n- Question C: Please provide some of the examples generated by XAIFOOLER.\n", "paper_topic_and_main_contributions": "This paper first show that LIME is inherently unstable and produces inconsistent results, especially in low sampling rates. Moreover, they propose a word-replacement-based attack, XAIFOOLER, that perturbs text inputs and manipulate explanations generated by LIME. They define several constraints to maintain the similarity between the adversarial and original document while reducing the similarity between the explanation of the original and adversarial document. They propose to use Rank biased Overlap (RBO) to measure the similarity between two explanations.", "excitement": 2, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the "stability" of LIME-based word importance scores. It consists in making small perturbations to the input, so as to preserve its meaning, but changing the explanation in terms of the ranking of the most important words. The perturbation technique introduced by the authors is named XAIFooler and is compared to various baseline methods, demonstrating its superiority as an adversarial attack method on LIME, and more broadly, this result highlights the "instability" or vulnerability of the LIME explanation method.

A strength of the work is that the authors use various metrics both to quantify the preservation of meaning during perturbation, as well as to quantify the resulting explanation dissimilarity. Thereby the authors make the point that among explanation similarity metrics the Rank-biased Overlap (RBO) is the most suited. Overall the evaluation is thorough, and in addition the paper is well-written.

More generally, the present work is complementary to a previous work also studying the vulnerability of LIME explanations to small perturbations in the input (Sinha et al. 2021, BlackboxNLP Workshop). Compared to this previous work, the authors additionally: 1) investigate the "inherent" instability of LIME (i.e. the impact of the LIME sampling rate on the LIME explanation similarity), 2) provide some analysis and comparisons to justify the choice of a similarity metric for explanations, and finally 3) allow only perturbation of less important words to demonstrate the instability of LIME even when performing only subtle changes in the input.

Nevertheless it remains an open question for future work whether the discovered explanation instabilities are specific to the LIME explanation method, or if such instabilities arise from the LIME's explanation setup which could also apply to other explanation methods as well, i.e. having only black-box access to the model and performing only a limited number of queries onto the model (through the sampling rate).
Decision: Accept-Main