Soundness and Completeness: An Algorithmic Perspective on Evaluation of Feature Attribution
Authors: Yawei Li
Yang Zhang
Bernd Bischl
Mina Rezaei
Venue: Submitted to ICLR 2023 (2023)
Keywords: explainable AI
explainability
feature attribution

Abstract: Feature attribution is a fundamental approach to explaining neural networks by quantifying the importance of input features for a model's prediction. Although a variety of feature attribution methods have been proposed, there is little consensus on the assessment of attribution methods. In this study, we empirically show the limitations of \emph{order-based} and \emph{model-retraining} metrics. To overcome the limitations and enable evaluation with higher granularity, we propose a novel method to evaluate the \emph{completeness} and \emph{soundness} of feature attribution methods. Our proposed evaluation metrics are mathematically grounded on algorithm theory and require no knowledge of "ground truth" informative features. We validate our proposed metrics by conducting experiments on synthetic and real-world datasets. Lastly, we use the proposed metrics to benchmark a wide range of feature attribution methods. Our evaluation results provide an innovative perspective on comparing feature attribution methods. Code is in the supplementary material. 

Under review as a conference paper at ICLR 2023
SOUNDNESS AND COMPLETENESS: AN ALGORITHMIC PERSPECTIVE ON EVALUATION OF FEATURE ATTRIBUTION
Anonymous authors Paper under double-blind review
ABSTRACT
Feature attribution a fundamental approach to explaining neural networks by quantifying the importance of input features for model's prediction. Although a variety of feature attribution methods have been proposed, there is little con- sensus on the assessment of attribution methods. In this study, we empirically show the limitations of order-based and model-retraining metrics. To overcome the limitations and enable evaluation with higher granularity, propose novel method to evaluate the completeness and soundness of feature attribution meth- ods. Our proposed evaluation metrics are mathematically grounded on algorithm theory and require no knowledge of "ground truth" informative features. We vali- date our proposed metrics by conducting experiments on synthetic and real-world datasets. Lastly, we use the proposed metrics to benchmark wide range of fea- ture attribution methods. Our evaluation results provide an innovative perspective on comparing feature attribution methods. Code is in the supplementary material.
INTRODUCTION
Explaining the prediction of machine learning (XML) models is an important component of trust- worthy machine learning in various domains, such as medical diagnosis (Bernhardt et al., 2022] Khakzar et al., 2021b a). drug discovery (Callaway) [022] Jiménez-Luna et al., 2020), and au- tonomous driving (Kaya et al., 2022] Can et al. 2022). One fundamental approach to interpret- ing neural networks feature attribution, which indicates how much each feature contributes to a model's 's prediction. However, different feature attribution methods can produce conflicting results for a given input (Krishna et al. 2022). In order to evaluate how well a feature attribution explains the prediction, different evaluation metrics have been proposed in the literature.
Despite valuable efforts and significant contributions to proposing a new evaluation strategy for feature attribution methods, several problems of concern remain. (1) Some evaluation strategies use duplicate or even conflicting definitions. For instance, (Ancona et al. 2018) define sensitivity-n as the equality between the of attribution and the output variation after removing the attributed features, while (Yeh et al.) 2019) define the sensitivity as the impact of insignificant perturbations on the attribution result. (Lundstrom et al., (2022) provide another version of sensitivity, where the attribution of feature should be zero if it does not contribute to the output.
(2) The retraining on modified dataset (Hooker et al. 2019) Zhou et al. 2022) time-consuming. Furthermore, many retraining based evaluations imply ly strong assumption that only a part of the input is learned during retraining. For instance, ROAR (Hooker et al.) 2019) assumes that model only learns to use features that are not removed during perturbation, and (Zhou et al. (022) assumes that retrained model only learns watermarks added into the original images of a semi-natural dataset. Later in this work, we show that model pick up any features in the dataset during retraining. (3) Many evaluation metrics are only sedsiisensitive, meaning that they only evaluate whether one feature is more important than another while ignoring how differently the two features contribute to the output.
To overcome the discussed challenges, we propose to evaluate the alignment between attribution and informative features from algorithmic perspective. The two proposed metrics work in conjunction with each other and reflect different characteristics of feature attribution methods. Our proposed metrics are both order-sensitive and value-sensitive, allowing for stricter differentiation between

---

Under review as a conference paper at ICLR 2023
two attribution methods. Therefore, the information provided by metrics is more fine- grained compared to existing metrics. In addition, our proposed metrics can perform evaluation without knowing the "ground truth" informative features for model inference, as utilize the model's performance as an approximate metric to compare different feature attribution methods.
To summarize contributions:
We empirically reveal the limitations of existing evaluation strategies for feature attribution. We show that -bsed evaluations can be underperforming. We further demonstrate that evaluations with retraining are not guaranteed to be correct.
We draw inspiration from algorithm theory and propose two novel metrics for faithfully evaluating feature attribution methods. Our approach requires no prior knowledge about "ground truth" informative features. We conduct extensive experiments validate the correctness of our metrics and empirically show that our approach overcomes the problems associated with existing metrics.
We comprehensively benchmark feature attribution methods with our proposed metrics. Our benchmark reveals some undiscovered properties of existing feature attribution meth- ods. We also examine the effectiveness of ensemble methods to showcase that our metrics can help to create better feature attribution methods.
2 RELATED WORK
Attribution methods explain model by identifying informative input fea- tures given an associated output. Gradient- based methods (Simonyan et al. 2014] Baehrens et al. 2010 Springenberr al. 2015: Zhang et al. 2018 Shrikumar al.) (017) produce attribution based on variants of poopppropagttion rules. Another family of methods attempts to approximate Shapley values (Shapley )997), where features butions. Examples of these methods include DeepSHAP (Lundberg & Lee 2017) and Integrated Gradients (IG) (Sundararajan et al., 2017 Sundararajan & Najmi 2020; | Jundstrom et al. 2022 Additionally, perturbation- 2016) such as Extremal Perturbations (ExPeturb) (Fong 20199) rely on perturbing input fea- tures and measuring the impact on output. Moreover, IBA (Schulz et al. (2020) and InputIBA (Zhang al. 2021) are derived from information bottlenecks. InpullBA finds a better prior for the infor- mation bottleneck at the input, thus producing more fine ome-grrined attribution maps than IBA. Lastly, attribution methods based on activation maps like CAM (Zhou al.) 2016) and GradCAM (Sel- varaju et al. (017) use activations gradients of hidden layers.
Feature Attribution
considered as cooperative players with different contri-
methods (Fong & Vedaldi| Fong et al. 2019: Ribeiro et al.,
In this work, we analyze and study some representatives from each of these categories. Specifically,
we assess GradCAM (Selvaraju et al. 2017). DeepSHAP (Lundberg & Lee (007)). IG (Sundararajan ct al. 2017). ExPerturb (Fong et al. 2019). IBA (Schulz et al. 2020) and InputIBA (Zhang et al.
2021
Evaluation metrics for feature attribution Earlier efforts have attempted to evaluate various feature attribution methods. One category of these methods is expert-grounded metrics that rely on visual inspection (Yang al. 2022), pointing game (Zhang al. 2018). human-Al collaborative tasks (Nguyen et al.] 2021). However, the evaluation outcome is subjective and does not guarantee consistency. Another category is cineiional-groundee metrics (Petsiuk al. 2018 Samek al.) 2016 Ancona et al., 2018) that perturb input according to altribution order and measure the change of model's output. Prior works usually consider two removal orders: MoRF (Most Relevant First) and LeRF (Least Relevant First). (Hooker et al.) 2019) argued that removing features can lead to adversarial effects. They proposed method ROAR to retrain the model on the perturbed dataset to mitigate the adversarial effect. Later, ROAD (Rong et al.) (022) showed that the perturbation masks can leak class information, leading to an overestimated evaluation outcome. Recently, (Zhou et al.) 2022) proposed to inject "ground truth" features into the training dataset and forced the model to learn these features solely. They then tested if an attribution method identified these features. Furthermore, (Khakzar et al. (022) propose generate datasets with null features and then test the axioms for feature attribution. Another sub-type in functional functional-grounded metrics focuses on sanity checks for attribution methods (Adebayo et al. 2018). The key differences between approach
2

---

Under review as a conference paper at ICLR 2023
0.392
Toot Accuaayy
2.
6.0
Kosnaed
Onginal
(a) Example images in the modified dataset for retraining
(b) Accuracy
Figure/ 1: Retraining on the modified dataset. Our malicious modification scheme perturbs a small fraction of background pixels but introduces a high correlation with classes. The test accuracy on the unperturbed test set shows that the retrained model ignores the remaining features but learns to mostly rely on introduced artifacts for classification. Hence, the low test accuracy here not due to information removal, but due to not learning from the true class-related information.
and the aforementioned approaches are: (1) our approach does not entail retraining modified or semi-natural datasets, and (2) our approach can distinguish between attribution methods that arrange features in the same order but assign features with different attribution values.
3 PROBLEM FORMULATION AND METHOD
3.1 ISSUES WITH FEATURE IMPORTANCE EVALUATIONS
In this section, illustrate two complications with feature importance evaluations. One issue related to order-based evaluation. Another issuc is related to evaluations that rely on retrained models. We discuss these issues in detail in the following text.
So far, many feature importance evaluations operate by removing features by attribution order, then observing the variation in the classifier's output. In this work, we argue that prder-based evaluations are insufficient. Since these evaluations perturb features based on their relative order of attribution values, the magnitude of attribution values is less considered during evaluation. Subsequently, dif- ferent attribution methods can have similar evaluation outcomes as long as the relative attribution order is preserved regardless of the actual attribution value. We empirically demonstrate this conflict with one falsification experiment shown in Fig. 3c left.
Another issue with regard to the evaluation of feature attribution methods retraining. Some eval- uation approaches use retraining the retrained model. Retraining- based evaluations assume either the retrained model learns solely from remaining features after perturbation, the retrained model exclusively relies on introduced features during perturbation. However, neither of these assumptions necessarily holds, as there no hard constraint in objective functions or learning procedures to restrain model from learning cer- tain features. the retraining is not ensured to follow these assumptions, the model's performance insufficiently trustworthy for evaluating feature attribution methods.
purposefully modified dataset, then report the performance of
We again demonstrate the issue related to retraining using one counterexample. Since retraining is modified dataset, maliciously design modification scheme to show that
usually conducted the model cannot learn the remaining features in this case. Our malicious strategy is to perturb a small number of pixels from the training data, such that the foreground object is intact in the image, but the perturbed pixels are now highly correlated to the class. Specifically, we choose CIFAR- 10 KKrizhessky et al.) 2009g) as the original dataset and perturb 5% of the pixels for each image in the training set. As objects are usually centered in CIFAR-10 10 images, we only perturb pixels close to the edges. However, the perturbation is class-related. If image belongs a certain class, we always remove pixels at a fixed position for that class. Fig. Ta shows examples of perturbed images. We use the modified dataset for retraining and report the accuracy on the unperturbed test set to evaluate how many remaining features are learned during retraining. More details of this experiment can be found in Appendix E Fig. Tb shows test accuracy of the original and retrained model. We observe that the retrained model has not learned to classify images using the remaining features. We hypothesize that modifying a dataset changes the loss landscape, and the model would converge another optimum that has steeper gradients in the vicinity. Nevertheless, this example
3

---

Under review as a conference paper at ICLR 2023
shows that it is difficult to constrain the learning process. Subsequently, retrained model can learn to rely on any features in the retraining dataset to make predictions, regardless of whether the feature is introduced by modification from the original dataset. Many retraining- based evaluations assume that a model learns a specific part of the input and define evaluation metrics based on this assumption. Since we showed this assumption can be violated easily, these evaluations based on retraining have no guarantee of correctness.
(Zhou et al. 2022) recently proposed an evaluation method that modifies dataset by adding artificial ground truth, then evaluates feature attribution methods on the model trained on the modified dataset. Nevertheless, training on modified nati-natural dataset also comes with a problem. Specifically, the learning task deviates from the original learning task when training on a semi-natura dataset. As a result, explanation methods can behave very differently on the semi-natural dataset, and we cannot obtain the actual performance of explanation methods. We demonstrate the issue by evalu- ating the performance of models as well as explanation methods on three different datasets. Here, use CIFAR- 100 (Krizhevsky et al., 2009b) as our learning task, then we add watermarks to in- ject artificial ground truth as (Zhou et 20222 suggested. Moreover, we generate a pure synthetic dataset having only watermarks in images. After training models on three datasets, we obtain test accuracy of 70.4% on CIF,R-100, 99.0% on the semi- natiral dataset, and 99.6% on the pure syn- thetic dataset. This shows that the difficulty of the original task is significantly greater than the task associated with the semi-natural dataset. However, we want to evaluate the performance of explanation methods on complex models trained on real-world datasets. An over-simplified dataset deviating from real datasets only creates a primitive evaluation setup. More importantly, as shown in Appendix B GradCAM outperforms IG and DeepSHAP on CIFAR-I00, while IG and DeepSHAP are much better than GradCAM on the semi- and pure synthetic datasets. This suggests that evaluating attribution methods across different datasets are inconsistent and may lead unfaithful conclusions.
3.2 AN ALGORITHMIC PERSPECTIVE EVALUATION
we discussed the issue with order-based evaluations. To overcome the limitations mentioned above and provide evaluation results with higher granularity, we develop an evaluation based on algorithm theory. Specifically, since feature attribution methods are algorithms, we can apply metrics in algorithm theory to assess their correctness. The correctness of an algorithm is typically related to two concepts: soundness and completeness (Smith) 2010). While prior works about attribution method evaluations mainly focus measuring the relative correctness of method, they ignore the fact that violation of either soundness or completeness can result in a partially correct algorithm. As first step, adapt the definitions from algorithm theory to formally define complete and sound feature attribution methods, respectively. Given a set F that contains all features in the dataset, let A C F be set of salient features identified by an attribution method, and given set of informative features I C F for the model, we have:
In Section 3.1
Definition 3.1 (Complete Feature Attribution). An attribution method is complete iff all informative features for the model are identified by the attribution method. YF e I, F E A.
Definition 3.2 (Sound Feature Attribution), An attribution method is sound iff all salient features by the attribution method are informative for the model. VF E A, e I.
However, almost all existing attribution methods are neither sound nor complete. In this case, evalu- ating whether a method is sound complete provides very limited information and cannot be used as a comparative metric. To measure the relative deviation from being perfectly sound and com- plete, we define soundness and completeness as more relaxed metrics. Completeness assesses the performance of an attribution method by checking how well the resulting attribution map covers the informative features. Complementary to completeness, soundness evaluates how well salient features contain true informative features. Formally, we define completeness as |A4 n / and soundness as |Anz]/ /lA The operator |-| calculates the set volume. Unlike conventional cardinality, which counts the number of features, we define the volume as the total attribution or information in a set. By using 1 we can obtain the overall effect of features with different amounts of information or with different attribution values.
There are three major challenges in evaluating soundness and completeness. One challenge is that feature importance and feature attribution are not discrete, so must evaluate them at different
4

---

Under review as a conference paper at ICLR 2023
value levels. Another harder challenge is that have no information about informative features I. Therefore, is intractable to directly calculate (Anz). Lastly, we cannot retrain a model or modify the dataset during evaluation due to the above-illustrated issue with retraining. We show in subsequent sections how we address these challenges and evaluate completeness and soundness.
3.2.1 COMPLETENESS EVALUATION
As discussed, completeness evaluates if all informative features included in attribution maps. Although we have no knowledge about informative features for the model, we can leverage the model provide indirect indications. We make the following assumption throughout the work:
Assumption 1. Given a dataset DD, F be the of all input features in DD, be model, and p be performance metric to assess the performance of model f. 4FI,F2 FF, if ((F() < p(f(F2)) then I n Fil II n F2), where I F is the set of informative features for model f.
According Definition 3.1 removing salient features generated from a complete method would also cause the removal of informative features. We can leverage this statement to compare the completeness across different attribution methods.
Theorem 3.1. Assume two attribution methods with returned salient features A1 and A2, respec- lively. If p(J(F)) Ai)) < P(J(F) \ A2)), then the attribution methud associated with A is more complete than the one ussociated with A2.
Proof: Assume salient features to A. After removing these features from the input, the set of remaining informative features is I A. Then, we have:
I
A I (AnZ) Z
AAnZ| == complttnnss(()))
(1)
I
in the above equation. In addition, since the set of informative features is constant given fixed model, we can ignore [ and solely use |I \ Al to evaluate relative completeness. However, [I \ AA is not accessible. To approximate II Al, we leverage Assumption I and pass \ A through the target model f to report the performance measure p(f(F) A)). If (( A1) < ((f(F) A2)), then [I\ Ail < <I \ A2l. Hence, the completeness of Ai is larger than the completeness of A2. We have
Because our defined| satisfies associativity, we have [Z\ 1Z -An
proved Theorem 3.1
Based on the above analysis, we briefly describe our procedure for evaluating completeness differ- ent attribution thresholds. We start with the unperturbed input and gradually remove input features above the designated attribution values. Then we pass the remaining features to the model and report the model performance difference between the origin and remaining features. A higher score differ- ence means higher completeness. As noted in ROAD, imputation can mitigate the class information leakage and adversarial effect. Therefore, impute perturbed images to diminish the undesired side effects caused by perturbation. The detailed procedure is shown in Appendix F
3.2.2 SOUNDNESS EVALUATION
After we defined metric to evaluate the completeness, we propose metric for soundness evalu- ation. We adopt the same notation from Section [.2.1] and use A for a set of salient features. We further define I, C I such that |Z,| of useful information for model prediction. We refer to this value u as the information level. Nev- ertheless, is intractable in our setting. Based on Assumption I if two sets of features can yield the same model performance, then the information level of these two sets of features is identical. Subsequently, we use model performance as an indirect indicator for information level and mea- sure the soundness at different model performance levels. To have unique I,, we further define the features belonging to I, as the most salient informative features, i.c., every feature in I,, is informative for decision making and has higher attribution value compared with other informative features. To tackle the continuity of attribution values, we define soundness at information level u as Soundness AAnII//AA Similarly to completeness evaluation, AnII, is infeasible to calculate, since we have no knowledge of informative features. Nevertheless, we can leverage the model to conduct soundness evaluation without calculating | Jn We show this in the following analysis:
The value is abstract notion denoting the amount
5

---

Under review as a conference paper at ICLR 2023
Lemma 3.2. Let A.. A, be two sets of salient features returned from different attribution methods, and Iy be informative features at information level v, if p(f(A.)) = p(f(A,)) = p(f((.)). then |A |A, ni Ipl-
The proof of Lemma 3.2 is shown in Appendix C With the help of Lemma 3.2 we can find A that satisfies IA | However, we still lack the necessary information to obtain Ig. One issue is that the resulting A is an overestimate of In.
Lemma 3.3. Given set features A and a of informative features In. if (((()) - ((S(I))) then we have In C A.
The proof of Lemma 3.3 is shown in Appendix [ The proof of Lemma 3.3 implies that if we can exclude non-informative features in A, we would obtain [Z,|] without overestimation. Thus, we can obtain the soundness at information level v without explicitly calculating |nnZ.
Theorem 3.4. If 3A* S A, such that p(J(I,)) - p(S(A)), and A n OF 0, then the soundness at information level is JA-
AT
Proof: For A C A that satisfies p(.(I.)) p(((A))) we have JA' [Z,]] Furthermore, ( Z) 0, then A C.. Since |A* nz| [Zal and A CI, we have |A*1 [Zp|.
Theorem suggests a way to evaluate soundness. Instead of calculating n for any possible choice of A. we can gradually increase A by adding small fraction of salient features AAA into A. If adding AA has no positive effect on model performance, i.e., ((A + AA)) S (A)())), would skip these features and continue adding other salient features. Once include enough salient features and find a A that satisfies A n I I.. we calculate [A.1 [A] information level v.
as the soundness at
In practice, we first gradually include the most salient features into the input. Then, we examine and exclude non non-informative features based on the change in model performance. At each step, we compute the attribution ratio, i.e., the ratio of informative attribution divided by the total attribution. We then plot the curve of attribution ratio vs. model's performance. For a fixed performance score (equivalent to information level), higher attribution ratio indicates better attribution method. We also apply image imputation here as in Section 3.2.1 The details are shown in Appendix G
4 EXPERIMENTS
Unless specified otherwise in the remaining text, we use an ImageNet (Deng et al., 2009) pre-trained VGG16 (Simonyan & Zisserman| 2015) the classifier and perform feature attribution the Im- ageNet validation set. We follow the same linear imputation strategy described in ROAD (Rong et al. 2022) to mitigate the class information leakage or adversarial effect. More details on experi- ment configurations can be found in Appendix
4.1 VALIDATION TESTS ON COMPLETENESS AND SOUNDNESS EVALUATIONS
In addition to analysis in previous sections, the incentive of this section is to empirically vali- date the correctness of our proposed soundness and completeness metrics. Prior works on feature attribution evaluation focus more on the definition and heuristic of evaluation strategies but ignore testing on real and adversarial cases. Subsequently, many proposed heuristics were later discovered have flaws. Therefore, validation is essential for evaluation metrics.
Our validation experiments have two complementary settings. We first use synthetic dataset and design model validate our evaluation metrics. Because the model is fully transparent, we can simply obtain the ground truth features for the model. Hence, we can thoroughly examine whether our proposed evaluations have the desired behavior in different scenarios. Then, we conduct our experiment on real, complex dataset to show the behavior of our metrics in more realistic setting.
4.1.1 SYNTHETIC DATASET
In this experiment, our goal is to design a synthetic dataset and a simple linear model for feature attribution. With synthetic dataset and primitive model, can perform feature attribution to

---

Under review as a conference paper at ICLR 2023
1.0
01
To Daaetiee
0.
0.0
Gound
Gouad
Herooee
0.4
Herroce
lazodace
Introdace
02
64
0.2
12
Arrbutio Thronddd
Acouxy
(a) Completeness
(b) Soundness
Figure 2: Completeness and soundness evaluations on the synthetic dataset. Attribution threshold t indicates that pixels with attribution greater than are masked. The curve and error bar, respectively, show the mean and variance of 1000 trials of random attribution removal and introduction. The curves of Remove and Ground Truth are overlapped in (h) they both saturate at 1. Both soundness and completeness evaluations can faithfully reflect the changes we made in attribution maps.
obtain "ground truth" attribution maps. Given ground truth attribution maps that are already sound and complete, we can apply modifications to them and anticipate the changes in completeness or soundness. Specifically, increasing attribution values of non-informative features in ground truth attribution maps would hurt the soundness of the resulting maps but improve completeness. In contrast, removing attribution from ground truth attribution maps would reduce completeness but not soundness. Hence, we can use our proposed soundness and completeness metries to evaluate the modified attribution maps and check if the evaluation outcome can reflect the changes in soundness and completeness after modification.
The synthetic dataset a two-class dataset. Data points are sampled from a 200-dimensional Gaus- sian distribution .N (N I). If all features from a data point sum up be greater than zero, assign a positive label to the data point, and otherwise, we assign a negative label. The model is designed to fully replicate the data generation process and can be formulated y o <EE,, z4); where æ; is the i-th feature and (-) is step function that rises at x 0. As the model is a transparent linear model, can obtain the sound and complete "ground truth" attribution maps. More details on the attribu- tion process are described in Appendix H.. We randomly add and remove attribution from "ground truth" " feature maps 1000 times each, producing 2000 different modifications, and then compare the soundness and completeness between modified and original attribution maps using our metrics.
Based on the statistical results shown in Fig. we observe that the completeness of Remove is consistently higher than the completeness of the ground truth attribution, while the completeness of Introduce is always lower than the completeness of the ground truth attribution. In soundness evaluation, we observe that these three methods ranking is reversed. Note that the soundness of the ground truth attribution is the optimum state of 1, and hence, Remove can also only reach this state. In conclusion, the behavior of soundness and completeness evaluations expected, thus validating that our proposal is correct in this case.
4.1.2 IMAGENET
Unlike the experiment in Section 1.11 (for which sound and complete attribution maps can be easily obtained), the ground truth attribution maps for ImageNet are inaccessible. Therefore, we cannot guarantee that the introduced attribution is exclusively added to non-informative features. In other words, the introduced attribution does not necessarily reduce soundness. Due this natural con- straint, we herein only compare the completeness between modified and original attribution maps. Here, we modify the GradCAM attribution maps in this experiment. We expect modified attribution maps with removal operation to be less complete than GradCAM, since the removal operation only removes attribution. On the other hand, adding attribution on GradCAM attribution maps would result in more complete attribution maps than GradCAM attribution maps.
To cover various modification cases, we implement three pairs of different schemes to modify the attribution maps obtained on ImageNet. When removing attribution, Constant and Random lower attribution by a constant and random positive value, respectively; Partial sets a part of the pixels' attribution to O. When introducing additional attribution, Constant and Random raise attribution by a constant and random positive value, respectively; Partial sets the attribution of some less important pixels to a high value. Some examples visualized in Fig. The details of attribution modifica-
7

---

Under review as a conference paper at ICLR 2023
Conslant
Random
Partial
Dillcre
Origiia Intodaae
RM
Tavalod
(b) Completeness
Constant
Random
Partial
drigiial Inaodace
(a) Modified attri- bution maps
(c) ROAD
Figure Comparison between modified and original (GradCAM) attribution maps in terms of completeness. In (a), modifications Remove and Introduce are denoted by (R) and (I), respectively. From (b), we can see that completeness evaluation able to correctly capture the changes caused by removing and introducing attribution. However, ROAD (c) cannot distinguish between these changes in Constant and Random modifications. Further examples are shown in Appendix H..3
tion can be found in Appendix H.3 The results in Fig. are consistent across different modification schemes and conform to our expectations. In summary, the experiment results validate the correct- ness of our proposed metrics. Furthermore, as depicted in Fig- ROAD fails to distinguish between the modified attribution maps in Constant and Random modification schemes. This shows that our completeness metric can effectively overcome the limitation of order-based evaluation metrics.
4.2 BENCHMARKING ATTRIBUTION METHODS
The ultimate purpose of developing metrics is use them to compare attribution methods. There- fore, we benchmark some representative attribution methods here and hope the empirical findings and implications can inspire future research in feature attribution. to provide readers with an intuition about the soundness and completeness of these attribution meth- ods. The benchmark results are presented in Fig. 5a and Fig. 5b Several observations can be made as follows:
Fig. 4 we first show sample
Complete methods are not necessarily sound (and vice versa). For instance, ExPerturb appears far more complete than other competitors, owing to the fact that the perturbed area is large enough to cover foreground objects. Nevertheless, ExPerturb unsound, since it assigns high attribution background pixels in the perturbed area. Visual results in Fig. 4 support our argument. In ad- dition, two equally complete methods can exhibit different levels of soundness (and vice versa), as exemplified the comparison of IG vs. DeepSHAP shown in Fig. 5 Fig. [b)
Layer attribution methods outperform axiomatic ones. Layer altribution methods like GradCAM hidden layer and then interpolate the attribution map the input
and IBA perform attribution size. InputIBA also belongs to this category, as it leverages the distribution on hidden layer. In contrast, axiomatic methods such as DeepSHAP and IG perform attribution directly on input pixels. These methods usually produce very sparse attribution maps, which explains why they are less com- plete than layer attribution methods. The interpolation operation also enhances the completeness of layer attribution methods. One might expect layer attribution's 's proclivity for assigning attribu- tion to the background in interpolated attribution maps. However, layer attribution methods appear even sounder than axiomatic ones in metric: We first emphasize that IG (or DeepSHAP) also assigns small but nonz attribution values to background pixels. The attribution of background will be determined false attribution. Furthermore, IG's total amount of attribution is substantially smaller than layer attribution methods. Therefore, the false attribution in IG leads to a more consid- erable drop in the attribution ratio hence, the soundness. The observation also implies that layer
8

---

Under review as a conference paper at ICLR 2023
Imspe
GradCAM
DemSSHAP
ExPorturb
IG
IBA
InputBBA
Figure 4: Sample attribution maps. observe clear inconsistency between attribution methods. The image is randomly chosen, and more examples are provided in Appendix H.2
Acgincy Dilleone
GraCCAM
Accemcy thtffernuz
0.5
88
GralCAM Eahlnngh
Amiliion
JC-SQ
3.2
8.5
0.6
ImpoTRA
0.5
0..
0.6
666 Arsbutio Thrabeld
0,
02
Arrilutios Throkeldd
Accuncy
Accuaay
(a) Completeness of vari- ous attribution methods
(b) Soundness of various (c) Completeness of IG (d) Soundness of IG sembles
attribution methods
ensembles
Figure 5: The completeness and soundness benchmarks. (a)-(b) Comparison between various at- tribution methods. method that shows high completeness does not necessarily imply that also yields high soundness. Layer attribution methods such IBA, GradCAM not only more com- plete but also sounder than DeepSHAP and IG. (c)-(d) Comparison between IG ensembles. Al- though ensemble methods improve soundness, not all of them improve completeness.
attribution methods exhibit more distinct differentiation between foreground and background. This property may benefit downstream tasks, such as weakly reakry--upervvied object localization (Zhou et al.) Selvaraju al. 2017).
2016
4.3
EVALUATING ENSEMBLE METHODS
Several ensemble methods (Smilkov et af. 2017, Hooker al. 2019 Adebayo et al.) 2018) have been recently proposed to enhance the performance of IG and DeepSHAP, In this experiment, evaluate ensemble methods in order to investigate whether applying ensemble tricks beneficial. By doing so, demonstrate that evaluation metrics be used guide for improving feature attribution methods. We consider three ensemble methods IG: SmoothGrad (IG-SG) (Smilkov al. 2017). SmoothGrad (IG-SQ) (Hooker al. 2019). and VarGrad (IG-Var) (Adebayo al. The benchmark results are presented in Fig. Scladd and Fig. 5d
2018
Surprisingly, only method IG-SG improves completeness. The completeness results consis- tent with the visual results shown in prior work (we also present visual results in Appendix [H.4 further examination). Compared IG, IG-SG assigns attribution fore, IG-SQ and IG-Var have less coverage of informative features. In addition, all three ensemble methods improve the soundness of IG et al. 2017). the gradients fluctuate dramatically in neighboring samples. Hence, aggregating the attribution of neighboring samples can reduce false attribution and enhance soundness.
larger of pixels. There-
on par with GradCAM and IBA. As noted in (Smilkov
5 CONCLUSION
In this work, we first revealed the issues with order-based and model-retraining approaches. We then introduced methodology to evaluate the soundness and completeness of feature attribution methods based on algorithm theory. Compared to existing metries, our metrics have higher differentiation granularity. We circumvented the need to know "ground truth" informative features by utilizing the model's 's performance as an approximate and comparative assessment. Validation experiments provided convincing evidence for the effectiveness of our metrics. We also benchmarked various attribution methods and demonstrated that our metries contribute towards a better understanding of feature attribution and can benefit future research explainability.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems. Curran As- sociates, Inc., 2018.
Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better understanding of gradient-based attribution methods for deep neural networks. International Conference on Learning Representations, 2018.
David Bachrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus- Robert Müller. How explain individual classification decisions. The Journal of Machine Learn- ing Research, 11:1 111:1803-1888 1831, 2010.
Mélanie Bernhardt, Charles Jones, and Ben Glocker. Potential sources of dataset bias complicate investigation underdiagnosis by machine learning algorithms. Nature Medicine, 28(6):1157- 1158, 2022.
Ewen Callaway. 'the entire protein universe': Ai predicts shape of nearly every known protein. Nature, 608(7921):15-16, 2022.
Yigit Baran Can, Alexander Liniger, Danda Pani Paudel, and Luc Van Gool. Topology preserving lo- cal road network estimation from single onboard camera image. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 17263-17272, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009.
doi: 10. WOW.///V..000050000000
Ruth Fong, Mandela Patrick, and Andrea Vedaldi. Understanding deep networks via extremal per- turbations and smooth masks. In Proceedings of the IEEE/CVF international conference on com- puter vision, pp. 2950-2958, 2019.
Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful pertur- bation. In Proceedings of the IEEE international conference on computer vision, pp. 3429-3437, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. benchmark for interpretabil- ity methods in deep neural networks. Advances in neural information processing systems, 32, 2019.
José Jiménez-Luna, Francesca Grisoni, and Gisbert Schneider. Drug discovery with explainable artificial intelligence. Nature Machine Intelligence, 2710):573-584 2020.
Berk Kaya, Suryansh Kumar, Carlos Oliveira, Vittorio Ferrari, and Luc Van Gool. Uncertainty- aware deep multi-view photometric stereo. In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, pp. 12601-12611, 2022.
Ashkan Khakzar, Sabrina Musatian, Jonas Buchberger, Icxel Valeriano Quiroz, Nikolaus Pinger, Soroosh Baselizadeh, Seong Tae Kim, and Nassir Navab. Towards semantic interpretation of thoracic disease and covid-19 19 diagnosis models. In International Conference on Medical Image Computing and Computer-Assister Intervention, pp. 499-508. Springer, 2021a.
Ashkan Khakzar, Yang Zhang, Wejdene Mansour, Yuezhi Cai. Yawei Li, Yucheng Zhang, Seong Tae Kim, and Nassir Navab. Explaining covid- 19 and thoracic pathology model predictions by iden- tifying informative input features. In International Conference on Medical Image Computing and Cosputer-Assisted Intervention, pp. 391 391-401. Springer, 2021b.
10

---

Under review as a conference paper at ICLR 2023
Ashkan Khakzar, Pedram Khorsandi, Rozhin Nobahari, and Nassir Navab. Do explanations explain? model knows best. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 10244, 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Narine Kokhlikyan, Vivek Miglani, Miguel Martin, Edward Wang, Bilal Alsallakh, Jonathan Reynolds, Alexander Melnikov, Natalia Kliushkina, Carlos Araya, Siqi Yan, and Orion Reblitz- Richardson. Captum: unified and generic model interpretability library for pytorch, 2020.
Satyapriya Krishna, Tessa Han, Alex Gu, Javin Pombra, Shahin Jabbari, Steven Wu, and Himabindu Lakkaraju. The disagreement problem in explainable machine learning: A practitioner's perspec- tive. arXiv preprint arXiv:2202.0100 2602000022, 2022.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009a.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 100 (canadian institute for advanced research). 2009b. URL httt::htt////ttt cs. www.nto. www.ootttood////iieaiee cirarraaa...///.o html
Scott M Lundberg and Su-In Lee. A unified approach interpreting model predictions. Advances in neural information processing systems, 30, 2017.
Daniel D Lundstrom, Tianjian Huang, and Meisam Razaviyayn. A rigorous study of integrated gradients method and extensions to internal neuron attributions. In International Conference Machine Learning, pp. 14485-14508. PMLR, 2022.
Giang Nguyen, Daeyoung Kim, and Anh Nguyen. The effectiveness of feature attribution methods
and its correlation with automatic evaluation scores. Advances in Neural Information Processing Systems, 34:26422 264366, 2021.
Vitali Petsiuk, Abir Das, and Kate Saenko. Rise: Randomized input sampling for explanation of black-box models. BMVC, 2018
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144, 2016.
Yao Rong, Tobias Leemann, Vadim Borisov, Gjergji Kasneci, and Enkelejda Kasneci. A consistent and efficient evaluation strategy for attribution methods. In International Conference on Machine Learning, pp. 18770-18795. PMLR, 2022.
Wojeiech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus-Robee Müller. Evaluating the visualization of what a deep neural network has learned. IEEE transactions on neural networks and learning systems, 28 (1111)):660226777 2016.
Karl Schulz, Leon Sixt, Federico Tombari, and Tim Landgraf. Restricting the flow: Information bottlenecks for attribution. In International Conference on Learning Representations, 2020.
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. 2017 IEEE International Conference on Computer Vision (ICCV), pp. 618-626, 2017. doi: 10. 10.1109//C
Lloyd S Shapley. A value for n-person games. Classics in game theory, 69, 1997.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference machine learning, pp. 3145- 3153. PMLR, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego CA, USA. May 7-9, 2015, Conference Track Proceed- ings, 2015.
11

---

Under review as a conference paper at ICLR 2023
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Yoshua Bengio and Yann Le- Cun (eds.), 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Workshop Track Proceedings, 2014.
Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda B. Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. Workshop on Visualization for Deep Learning, ICML, 2017.
Peter Smith. Types of proof system. 2010. URL http::/ww..oogicaaateeeee
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin A. Riedmiller. Striving for simplicity: The all convolutional net. In Yoshua Bengio and Yann LeCun (eds.), 3rd Inter- national Conference on Learming Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Workshop Truck Proceedings, 2015.
Mukund Sundararajan and Amir Najmi. The many shapley values for model explanation. In Inter- national conference on machine learning, pp. 9269-92788 PMLR, 2020.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference on machine learning, pp. 3319-3328, PMLR, 2017.
Scott Cheng-Hsin Yang, Nils Erik Tomas Folke, and Patrick Shafto. A psychological theory of explainability. In International Conference Machine Learning, pp. 25007-25021. PMLR, 2022.
Chih-Kun Kuan Yeh, Cheng- Yu Hsieh, Arun Suggala, David I Inouye, and Pradeep K Ravikumar, On the (in) fidelity and sensitivity of explanations. Advances Neural Information Processing Systems, 32, 2019.
Jianming Zhang, Sarah Adel Bargal, Zhe Lin, Jonathan Brandt, Xiaohui Shen, and Stan Sclaroff. Top-down neural attention by excitation backprop. International Journal of Computer Vision, 126 (10):1044-1102, 2018
Yang Zhang, Ashkan Khakzar, Yawei Li, Azade Farshad, Seong Tae Kim, and Nassir Navab. Fine- grained neural network explanation by identifying input features with predictive information. Ad- vances Neural Information Processing Systems, 1120040-2005.. 2021.
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2921-2929, 2016.
Yilun Zhou, Serena Booth, Marco Tulio Ribeiro, and Julie Shah. Do feature attribution methods correctly attribute features? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9623-9633, 2022.
12

---

Under review as a conference paper at ICLR 2023
APPENDIX
A NOTATIONS
Table lists the notations used in this paper.
Table 1: Table of notations.
F
a set that contains all features in the dataset a set of attributed features
A
a set of informative features for model the operator to calculate the set volume a single feature in F scalar
f
a model to be explained
P
a performance metric to assess the performance of model f'
a (labeled) dataset
B EVALUATING ATTRIBUTION METHODS ON RETRAINED MODELS
we argue that the attribution methods can behave much differently when explaining the model retrained on semi-natural dataset. As result, is not faithful to use the evaluation result on the demonstrate this issue with an experiment.
In Section 3.1
dataset as an assessment for the feature attribution methods. In this section, we
We up the experiment as follows: first re-assign the labels for CIFAR- -EFAR-10 (Krizhevsky al., 2009b) images and add watermarks as suggested in (Zhou et al., 2022), obtaining semi-natural dataset. Next, we inject watermarks to a blank canvas, obtaining pure-synthetic dataset. After that, we train VGG-16
the CIFAR-IO0, semi-natural, and pure synthetic dataset, respectively. After obtaining the classification models, we apply GradCAM, IG, and DeepSHAP to them to get the attribution maps. In the end, we benchmark the three attribution methods each dataset using ROAD (Rong et al. 2022).
The models achieve 70.4% CIFAR-100, 99.0% the semi-natural dataset, and 99.6% the pure synthetic dataset, respectively. The difference of accuracy shows that the learning tasks are differently complex across three datasets. Futhermore, depicted in Fig 6 GradCAM outperforms IG and DeepSHAP on (IFAR-100, while IG and DeepSHAP are much better than GradCAM on the semi-natural and pure synthetic datasets. The evaluation results on the semi-natural dataset cannot correctly reflect attribution methods' performance on the real-world dataset.
0.70
GraCAAM
GracCAM
GrdCAM
IG DoepSHAA
0.65
DeppIIAP
0.20
DopSiLAP
0.4
0.60
Accuncy
0.15
Accuracy
0.10
0.2
0.50
0.05
0.00
0.0
11.6
0.8
0.4
Ratio by
by Area
Mask Ratio by Area
(a) Original CIFAR-100
(b) Semi-natural datasct
(c) Pure synthetic datasett
Figure 6: ROAD evaluation different datasets. The performance of attribution methods can be much different between the real-world dataset and semi- natural (or pure synthetic) dataset.
C PROOF OF LEMMA 3.2
Here, show the Lemma 3.2 again avoid frequent turning pages for readers.
13

---

Under review as a conference paper at ICLR 2023
Lemma. Aj salient features returned from different attribution methods, and VI. informa- rive features at information level v, if p(f((A)) = p(f(A,)) p(f then A, ni = A, nI= Ip-
Proof: we use result from Assumption I
Since p(f(A.)) = p(J(A,)) p(J(I.)), we have [A, nz = [A, nz = I. nI. As defined as a condition, Iy denotes informative features, thus have In C I. Hence, I. nI I..
D PROOF OF LEMMA 3.3
Here, we show the Lemma 3.3 again avoid frequent turning pages for readers.
Lemma. Given set of features A and set of informative features In, if p(f(A)) p(f(Io)), then we have In C A.
Proof: Assume we have a set of features A, and set of non-informative features AN S. (F)
We can have:
(AU (An (Ax nI.)
= (AnNI, U$
(2)
ANI..
Hence, given a set A, we can always find larger set AU AN that satisfies (AUAx) ANI.. The A U AN can be defined as the new A, then we always have I, A.
We show in this lemma that under ((f( pl (I.)). the informative feature set Iy always subset of A. Moreover, we show that A is only larger than I., if A contains non-informative features. This implies that if we can somehow remove the non-informative features from A, we can have |A| IZl-
E FALSIFICATION EXPERIMENT CONFIGURATIONS
In this section, we show the experimental setup used for generating the results presented in Fig. and Fig.
For Fig. We apply the Constant modification in Table 2 to GradCAM attribution maps Ima- geNet. In addition, we set the noise level in ROAD to 0.01 when performing noisy linear imputation. This noise level also adopted in the experiments in Section 4.1tion4.11.2 4.1.2 Section 4.2 and Section 4.3
In the retraining experiment shown in Fig. I we use the CIFAR-I0 (Krizhevsky et al. 2009a) dataset. The model is a tiny ResNet (He et al. 2016) with only 8 residual blocks. Training is conducted using Adam (Kingma& & Ba 2015) optimizer with learning rate of 0.001 and weight decay of 0.0001. The batch size used for the training is 256, and we train a model in 35 epochs. Next, we describe how construct the maliciously modified dataset for retraining. We generate modified dataset from the original CIFAR-10 dataset.
perturb 5% of each training image and replace the perturbed pixels with black pixels. The perturbation is class related. For different classes, we select different positions that are close to the edge of the image, so the object (which is usually the center of the image) is barely removed.
F THE IMPLEMENTATION OF COMPLETENESS METRIC
For the completeness metric, the attribution threshold means that the pixels with attribution be- tween [t, 1] will be masked (i.e., value-based MoRF). We start from = 0.9 and decrease t by the step size of 0.1. Algorithm demonstrates the computation process.
G THE IMPLEMENTATION OF SOUNDNESS METRIC
For the soundness metric, the mask ratio v means that the top e pixels in an attribution map sorted in ascending order masked (i.e., area-based LeRF). We start from 0.98 and decrease by
14

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Completeness evaluation
Input: f: model; ID> {I:; Vi, A: A: labeled dataset with input label Yi. and attribution
map A, for each (34, Vi): : d: perturbation function; t/: noisy linear imputation funetion; T= (0.9, 0.8, 0. 0.1): attribution thresholds; Acc: accuracy evaluation function.
Output: Sa: Accuracy differences associated with attribution thresholds T.
Initialize Sa:
so < Aceef (D) ;// Accuracy the unperturbed dataset
foreach t in T do
D, + 0 Initialize dataset of imputed images
foreach 24, Mi D
c - Ai,4; Perturb pixels whose attribution exceed
34 //1 Impute the perturbed image
Append(D, (B;,
+ ; ; Accuracy on the imputed dataset
(Sp, 80 - 8t) Accuracy difference at the current step
return SA:
the step size 0.01. This is equivalent to first inserting 2% of the most important pixels in a blank canvas and inserting 1% more pixels at each step. If the accuracy difference between the current step and the previous step is smaller than the threshold 0.01, then the attribution of new added pixels is deemed to be false attribution and will be discarded. Iggorithmm@demonnstann the detailed procedure.
H VALIDATION AND BENCHMARK EXPERIMENTS
H.1 IMAGENET IMAGES FOR FEATURE ATTRIBUTION
We randomly select images for each class in the ImageNet validation set, obtaining subset with 5000 images. When performing attribution, the images and attribution maps are resized to 224 x 224 before being fed into the pretrained VGG16 model.
H.2 IMAGENET ATTRIBUTION MAPS
In this sub-section, we present the configurations for generating attribution maps on ImageNet. For GraCAM and IBA, We resize the resulting attribution maps to the same size as the corresponding input images. We use the implementations of GradCAM, DeepSHAP, IG in Captum (Kokhlikyan et al. 2020), and the implementation of ExPerturb in TorchRay and the implementations of IBA and InputlBA the official InputBBA codebase (Zhang al. 2021). Some hyper- parameees for producing attribution maps are:
GradCAM We perform attribution on the features. 28 layer of VGG16 (i.e. the last convolu- tional layer).
DeepSHAP and We choose as the baseline for attribution. We clamp the attribution to interval 1].
ExPerturb We set the area perturbed region to 0.4.
IBA and InputIBA We attach the hidden information bottleneck to features. 17 layer of VGG16. We set the penalty coefficient B, = 20 for the hidden information bottleneck, and B, = 20 for the input information bottleneck.
Fig. we provide more visual results of different attribution methods. The samples are randomly selected.
15

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Soundness evaluation
Input: f: model; ID = {T,, Vi, A J labeled dataset with input 2;, label Yı, and attribution map A, for each (I,, y:): qy perturbation function; th: noisy linear imputation function;
M = {0.99, 0.98, 0.97.... 0.01}: mask ratios (by area); Acc: accuracy evaluation
function.:
accuracy threshold; New function that identifies the new inserted features at the current step.
Output: IP: A set of tuples with each tuple being the accuracy and the attribution ratio.
Initialize P;
A (0,00 (0....,,00 000 :// Initialize the set of features with false
attribution for each sample.
mo - 1:// Initialize the mask ratio at the previous step.
80 + 0// Initialize the accuracy at the previous step.
foreach m in MI do
Dm - // Initialize imputed dataset
foreach te A; in Do
24 A4.
Perturb image in LeRF order.
2 t (ix) /// Impute image.
A < New Ai, m, mn): /// Identify new added features
Append((n.. (Ti, Vi, A;, AA:));
Sm Aco(f, De) Accuracy
the imputed dataset.
sm so < then
foreach ((0;, Vi. A,, AA)), A.) in (m,, do
Á - U // Update the features with false attribution.
foreach ((Ti, Vi, Ai, A.),, in (Dm, A) do
+ [4, -Adl.
[A,
T N Li=1 qi 1/ Attribution ratio at the current step.
Append(F, (8m, /// Update results.
80 f- 8m : // Update the accuracy at the previous step. me + m ; Update the mask ratio at the previous step.
return P:;
H.3 VALIDATION TESTS
Experiment on the synthetic dataset We create a two-class dataset of 1000 sample data points, and each data point has 200 features. The data point is sampled from 200-dimensional ( I) Gaussian distribution. If all features for a sample point sum up to be greater than zero, we assign a positive class label to this sample. Otherwise, negative class label is assigned (as described in the main text). The model is a linear model and can be formulated as = o (2 2z), where æ; is the 1
i-th feature, and (-) is step function that rises at x 0, a (xx) -- if x O, and a & > 0. In other words, the model also sums up all features of input and returns a positive value if the result greater than zero. Hence, the model can classify the dataset with 100% accuracy. Lastly, we describe how we create ground-truit attribution maps for this model and dataset. As the model is linear model, and each feature I; is sampled from zero-mean Gaussian distribution, the Shapley Similarly. the Shapley value for 2; with
if
value for with (xx)) = is then 1 (z; E [x]] a (xx)) = - is I,, We confirm that attribution maps generated by Shapley values are fully correct for linear models. As result, for positive samples, the attribution values are the same as feature values. For negative samples, the attribution values are the negation of feature values, which means that negative features actually contribute the negative decision. Finally, modify the attribution maps to be compatible with our soundness and completeness evaluation. Since our evaluation only supports positive attributions, clip negative attribution values zero. This conversion step has
16

---

Under review as a conference paper at ICLR 2023
Table 2: The modifications of attribution maps on ImagNet.
Implementation Constant
Removing attribution
Introducing attribution
Subtract the attribution map by constant 0.6.
Add the attribution map with constant 0.6.
Random
Sample shift from ((-0.66 0) for each pixel independently, and add the attribution of each pixel with the corresponding shift.
Sample shift from 4(0, 0.6) for each pixel independently, and add the attribution of each pixel with the corresponding shift.
Partial
Sort the attribution map in ascend- ing order and select the pixels in indexing range [0.6NN, 0.8N], where N is the number of pixels. Then set the attribution of these pixels to O.
Sort the attribution map in ascend- ing order and select the pixels in indexing range [0, 0.4NV, where N is the number of pixels. Then set the attribution of these pixels to qu.8. where qi denote the t-th quan- tile attribution values.
negative effect the actual evaluation. The rest of the evaluation setup is identical to other experiments.
The experiment on the ImageNet We implement three different modification schemes and mod- ify the GradCAM attribution maps. The details thereof are presented in Table 2 We show some examples of modified attribution maps in Fig. The images are randomly selected.
H.4 ENSEMBLE METHODS OF
In each ensemble method, samples for a given input sample. Fig. Iigows additional examples IG and its ensemble methods. The images are randomly selected.
isotropic Gaussian kernel (O,00.3 I) sample 20 noisy
17

---

Under review as a conference paper at ICLR 2023
Image
GradCAM
DeepSHAP
ExPerturb
IG
IBA
InputIBA A
Figure 7: Examples of various attribution maps. The authors ensure that samples are not cherry- picked.
18

---

Under review as a conference paper at ICLR 2023
Image
Original
Constant (R)
Constant (1)
Random (R)
Random (I)
Partial(R)
Partial (I)
Figure 8: Examples of modified attribution maps. (R) and (1) denote the Remove and Introduce modification, respectively. The authors ensure that samples are not cherry-picked.
19

---

Under review as a conference paper at ICLR 2023
Image
IG
IG-SG
IG-SQ
IG-Var
Figure 9: Examples of IG and ensembled attribution maps. The authors ensure that samples not therry-picked.
20


Reviews:
[{"review_id": "zTSZoyFljL", "reviewer": "Reviewer_7Hq4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors propose two new metrics to evaluate feature attribution explanations: completeness and soundness which are based on algorithm theory. Authors show limitations of several existing order-based and model-retraining based metrics. The metrics are evaluated on several explainability methods such as GradCAM, DeepSHAP, IG, etc. for images. ", "summary_of_the_review": "See above", "strength_and_weaknesses": "+ \nOverall I think evaluating explanations is an important topic and new metrics/techniques to help evaluate explanations would be very useful to the community. \n\n-\nThe significance of these two metrics is not clear based from the submission. What is the risk of not computing these metrics?\nThere are new pieces of work based on computing ground truth: https://arxiv.org/pdf/2104.14403.pdf\nIt would be useful to show empirically if the proposed new metrics could become a good substitute for evaluating explanations without the need for ground truth, at least to some extent. \n\nIt would be good to show the results for tabular and text data. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tDOOMcljf7F", "reviewer": "Reviewer_iZ2R", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed two new metrics, completeness and soundness, for evaluating attribution maps. The two most important characteristics of these two metrics are that they do not require model retraining and are sensitive to the actual values of the attribution scores, not just their ordering. These two metrics are evaluated for many popular saliency maps, and several conclusions are drawn. ", "summary_of_the_review": "Overall, I do not believe that this paper makes a sufficiently significant contribution to merit acceptance. However, I would also want to note that the non-clarity of writing (in my opinion) prevents me from giving a very confident assessment. ", "strength_and_weaknesses": "**Section 1 and 2**\n\nWhile I agree with the authors on their motivation to make evaluations that are not order-based or require model-retraining, I believe that there are some misrepresentations of the prior work, in particular (Hooker et al. 2019) and (Zhou et al. 2022) which I happen to be quite familiar with. \n\n> (Zhou et al. 2022) assumes that a retrained model only learns watermarks added into the original images of a semi-nature dataset\n\nFrom my understanding, they reassigned the labels to be only correlated with the injected features (e.g. watermarks). While this is kind of an extreme operation, this does guarantee that none of the other features are actually correlated with the label, and the model could not use any other features to achieve better than random chance performance. \n\n> Many evaluation metrics are only order-sensitive, meaning that they only evaluate whether one feature is more important than another while ignoring how differently the two features contribute to the output.\n\nThe attr% metric used by (Zhou et al. 2022) does depend on the actual value of the attribution. \n\n> We use the modified dataset for retraining and report the accuracy on the unperturbed test set to evaluate how many remaining features are learned during retraining.\n\nThis is in reference to (Hooker et al. 2019) paper on the discussion of retraining. Here, the authors used the perturbed data in training and unperturbed data in testing, creating a distribution shift, which is exactly what this paper argued to avoid, by introducing the retraining step (perturbing both training and test data). Thus, I fail to see what the results actually demonstrate, because if the model (retrained or not) is tested on a different distribution, its performance can be affected by many OOD issues. \n\n**Section 3**\n\nI have many questions on it. \n\nAssumption 1: $\\rho$ is defined as a performance metric (e.g. accuracy). However, there can be features that have high impact on model prediction, but not in a way that contributes to the model performance. For example, a feature could improve the performance on a subset of inputs and hurt that on another subset, balancing out the $\\rho$ metric. This is related to \"Model behavior\" in Fig. 1 of [1]. \n\nSec. 3.2.2: I don't quite understand the definition of $I_v$ and information level. Do we assume an ordering on $I$, such that $I_v$ is the top-$v$ important features in $I$, or something else? \n\nRelated to the point above, I guess throughout, we assume that the saliency map generates a binary split of features into $A$ and $F\\backslash A$. Most attributions are continuous. I think the authors used some thresholding, which may be related to the information level, but I don't find the details. \n\nThe authors mentioned that $I$ is unknown (i.e. the unknown ground-truth problem). However, reading through Sec. 3, I still don't understand how $I$ is in practice inferred or approximated. I would appreciate a high-level overview and roadmap at the beginning of this section before going into technical definitions and proofs. \n\nMinor: Def 3.1 and 3.2 can be written as $I\\subseteq A$ and $A\\subseteq I$. \n\n[1] https://arxiv.org/pdf/2011.14878.pdf\n\n**Section 4**\n\nThe experiment covers a wide range of explanation methods. However, at the end of the day, all conclusions are drawn based on the two proposed metrics. Their relationship with other metrics is not clear. In other words, since these two metrics are again *defined* (starting from Def. 3.1, 3.2 and Assumption 1), it is not clear how or why they are a better alternative to existing approaches, and what their limitations are. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cxNnaot8wA5", "reviewer": "Reviewer_4ijn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the author propose an evaluation method for feature attribution based on the concept of soundness and completeness. The two notions are described along with how they might be approximated when ground truth feature importance is unavailable. The results show the metrics to behave sensibly when saliency maps are manipulated in specific ways.", "summary_of_the_review": "Overall, while there is some merit to the submission in its attempt to use formal and standardized way for evaluating attribution methods, I am not entirely convinced of its novelty beyond the introduction of new terminology. The writing is fairly clear but the details on actual implementation are not present in the paper’s main body. Based on these observations, I am not inclined for the paper to be accepted at the venue. ", "strength_and_weaknesses": "The problem of evaluating saliency method is a pertinent one and several ways have been proposed in recent literature approaching from varying perspectives. The proposal in this paper is quite sensible, paralleling the well understood notion of precision and recall (in case of soundness and completeness respectively). However, I had a few concerns:\n\n1. While the framing is unique, it appears to me that the proposed metrics have strong relationship to the insertion and deletion based metrics. For example, to my best understanding, completeness is essentially the deletion metric with the only difference that instead of ordered removal (remove top x% attributed pixels), it uses absolute thresholds (remove pixels with attribution greater than y) before measuring the performance change. Did I miss something? What’s the justification for introducing new terminology if the change is indeed that minor?\n\n2. How does this proposal differ from ROAD other than using values instead of order as noted above?\n\n3. I find the connection between the formalization and the actual implementation a little tenuous. While considerable space is devoted to the theory, the actual algorithms are delegated to the appendices. I also found it difficult to see how the theory truly informed the algorithms.\n\n4. The results section is somewhat lacking. The experiments on the toy dataset conform to the expectation which is good but not enough evidence of the goodness of the metrics. Then the section proceeds to benchmark the attribution methods using the proposed metrics. While interesting, the goal of the results section should be to convince the reader of the merit of the proposal. Just applying the metric to existing techniques doesn’t build any confidence in me for the work in the paper. Any insights thus generated have a confound of whether the observations say something about the proposed metrics or about the techniques studied. \n\n5. Minor: “semi-nature datasets”, “nature constraints”. The formatting style of I in equation (1) and proof of Theorem 3.4 is inconsistent in places.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "YwePGKPyk0w", "reviewer": "Reviewer_rKgk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is written to introduce two notions of evaluation for model explanations: soundness and completeness. The definitions for these metrics are straightforward but require prior knowledge of the ground-truth important features. The authors therefore suggest practical alternatives, which appear to reduce to procedures very similar to existing ones: making predictions with different subsets of (un)important features and analyzing how the predictions change.", "summary_of_the_review": "The authors propose two new criteria for evaluating model explanations. They are intended to address shortcomings in existing methods but re-use many of their key ideas. Thus, the novelty and significance are limited.", "strength_and_weaknesses": "--- Strengths ---\n\n- Several flaws about some existing evaluations are pointed out.\n\n--- Weaknesses ---\n\nAbout the method:\n- One of the key challenges with the method is that we don't have access to the ground-truth important features. The authors thus resort to approximate approaches, which seem geared primarily at comparing two attribution vectors rather than scoring one in isolation. Furthermore, the final procedure involves re-doing the prediction repeatedly with different amounts of (un)important features held out. Ultimately, this procedure is extremely similar to insertion/deletion (Petsiuk et al, 2018), but perhaps with a couple extra steps. The novelty thus seems quite limited.\n- The ideas behind soundness and completeness are very simple, there's no need to resort to vague notions of \"algorithm theory.\" As a reader it's a bit frustrating to see \"algorithm theory\" mentioned multiple times and then find out what the authors actually mean by it. You can just say what this method is: testing if the explanation identifies the important features but nothing more.\n- Describing other methods, the authors write: \"While prior works about attribution method evaluations mainly focus on explaining whether a method is correct or not, they ignore the fact that violation of either soundness or completeness can result in a partially correct algorithm.\" I don't get the point of this, it's not like other methods return a 0/1 value of whether the attribution is correct - they also return scores. What's the significant difference?\n- Theorem 3.3 is a simple result, perhaps it should be re-named as a proposition?\n- Mixing the ideas of set cardinality and summation within a set seems a bit sloppy. For example, in the proof for theorem 3.1, $|I \\setminus A| = |I \\setminus (A \\cap I)|$ is a valid equality if we're talking about set cardinality, but not if we're talking about summation. \n- When talking about the \"information level\", the notation $I_v$ defined as $I_v \\subseteq I$ s.t. $|I_v| = v$ doesn't make sense to me. There can be many subsets of that size, so which one is it? \n- In theorem 3.4, what is the relationship between $\\mathcal{A}^*$ and $\\mathcal{A}$? Should we have $\\mathcal{A}^* \\subseteq \\mathcal{A}$? If so, this should be specified.\n\nAbout discussions of prior work:\n- In describing prior work, the authors write that one issue is duplicate or conflicting definitions (e.g., \"sensitivity\"). I agree that it's an issue, but by the authors' account it seems like an issue with terminology rather than the metrics themselves, which is perhaps not as interesting.\n- In describing prior work, the authors frequently refer to \"order-based\" and \"model-retraining\" as the two groups of existing methods. This categorization of metrics doesn't make sense to me, they're overlapping categories and some methods belong to neither. For example, ROAR (Hooker et al, 2019) is both order-based and involves model retraining. Sensitivity-n (Ancona et al, 2018) is neither. This seems like a strange way to group existing evaluation methods.\n- The cost of model retraining is indeed a problem, and this is a complex issue because naive approaches like replacing with zeros are problematic in their own way (see Hooker et al, 2019). However, the authors don't actually \"solve\" this problem, they just impute the missing features. I'm not sure this can be described as a novel solution, as it's the same approach used by many other methods already (e.g., Petsiuk et al 2018, Ancona et al 2018).\n- The authors make a point of criticizing methods that are only sensitive to ordering, but what about the methods that aren't? For example, sensitivity-n (Ancona et al, 2018, already cited) and faithfulness [1]. These test the specific attribution scores rather than just their ordering.\n\n[1] Bhatt et al, \"Evaluating and aggregating feature-based model explanations\" (2021)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject