Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this study, a metric called Astuteness is introduced as a criterion to evaluate the reliability of explanations. Intuitively, if the distance between explanations given for two samples that are within a certain distance is also within a certain distance, then the explanation has astuteness. This definition can be interpreted as defining the robustness of an explanation. More specifically, it relates the distance in the sample space to the distance in the explanation space by probabilistic Lipschitzness. In this study, the authors show that for some certain classes of explanatory methods, such as SHAP and CXplain, the probabilistic lower bound of the astuteness of an explanation depends on the square root of the number of feature dimensions D and the Lipschitz constant L. The reliability of this probabilistic lower bound is also evaluated experimentally with several datasets.
main_review: The definition of astuteness introduced as a criterion for assessing the reliability of explanations seems to be a natural and useful definition. It is also interesting that lower bounds of astuteness can be derived for well-known explanatory methods. On the other hand, the derivation is elemental and does not lead to surprising results or useful results that can be used to improve the reliability of explanations. The result that the robustness of the explainer is bounded by the Lipschitz constant of the prediction function also seems obvious, since useful explanatory methods are naturally required to be robust against perturbation.
summary_of_the_review: Although the proposed definition is natural and useful as a criterion for evaluating the reliability of explanations, it cannot be said that the analysis using the criterion leads to useful results for improving explanatory methods, and it seems that more detailed analysis and deeper insight into the relationship between explanatory methods and the proposed criterion are needed for publication.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of robustness of local explanations of a classifier at some input x. Explanations can be generated by several methods: Shapley-value-based, mean-effect-based, and removal-based. Since the explanation methods use the output of the classifier f, the change in the explanations can be related to the change in the output of f, and the latter is quantified by the Lipschitz constant of f.
Lower bounds of \epsilon that bounds the change in the explanation in "explanation astuteness" is proved for three example explanation methods. This gives the "best-case" robustness in the explanations given perturbation in the input x. Experiments on 7 datasets evaluated the tightness of a low-bound of "explanation astuteness", which is the probability that two close inputs x and x' have their explanations \phi(x) and \phi(x') differ by no more than some upper-bound related to d(x,x').
main_review: Strengths:
+ very important problem to study. The robustness of explanation problems has been studied by prior work, but there is a lack of theoretical analysis from the perspective of function smoothness.
+ the proofs are detailed and correct.
+ covers some of the representative explanation methods, such as SHAP.
+ data and codes are released.

Weaknesses:
- The proof does not bring much new insight that are relevant to explanation robustness. There two sub-problems that are important but not addressed: 1) what's the worst-case change in the explanations (that would require a upper-bound over \epsilon, rather than a lower-bound); 2) the individual explanation element are treated independently but in practice, the features are ranked and only a small number of them are selected as an explanations, and a small change in explanation vector may lead to rather different top-k salient features.

- experimental sections are not comprehensive and vague. For example, it is not clear how to estimate the Lipschitz constant of a neural network. It is also not clear why the predicted astuteness should lower-bound the estimated one. In fact, the definition of the predicted/estimated astuteness is not given. How the experiment in Figure 2 support the theory is not explained clearly. Lastly, from Figure 2, the bounds seem quite loose: will they be useful in practice, and how they can be used?
summary_of_the_review: Problem studied are good, but theory and experiments have room for improvement.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on the reliability of explainers, where an explainer should give similar explanations for similar data inputs. To this end, the authors introduce and define "explainer astuteness", which leverages the concept of "probabilistic Lipschitzness" (the probability of local smoothness of a predictor/classifier function). The paper explores the reliability of different types of explainers by analyzing the connection between the robustness of explanation methods and the smoothness of the black-box predictor function they are trying to explain. Finally, the authors provide a theoretical way to connect the explainer astuteness to the probabilistic Lipschitzness of the black-box function and explore how the smoothness of the black-box function impacts an explainers' astuteness.
main_review: The paper essentially talks about the robustness of an explanation method that has been extensively studied in the XAI literature [1,2. 3]. Given below is a list of the papers' strengths and weaknesses:

Strengths:
1. Given the Lipschitzness of the prediction function, the paper provides lower bound guarantees on the astuteness of different explanation methods.
2. It analyzes three types of explanation methods: i) Shapley value-based, ii) explainers that simulate the mean effect of features, and iii) explainers that simulate individual feature removal.
3. Empirical evaluations using real and synthetic datasets demonstrate that the lower bound holds in practice.

Weaknesses:
1. Alvarez-Mellis et al. [1] defined that an explanation satisfies robustness if similar inputs do not result in substantially different explanations. The explainer astuteness (defined by the authors) is similar to the above definition of robustness. However, both robustness and astuteness do not consider the model behavior while defining similarity. The underlying assumption is that the model prediction remains the same for similar inputs, but we should also consider that the model can output the same predictions using different logic paths. It would be great if the authors can comment on this, or will the astuteness formulation change on considering this.
2. The paper is hastily written with errors in proofs: i) In the proof of Theorem 1, the last two $f(\cdot)$ terms of the first two equations should be $f(x' \odot  z_{-i})$. ii) In Equation 5, the sign associated with $f(x' \odot  z_{-i})$ should be $+$, and iii) typos in Equation 12.
3. The assumption made in Equation 6 for taking the maximum is unclear. It would be helpful if the authors can expand that.
4. In the experiments, the authors mention that "some deviations can be expected since the theoretical results assume the ideal scenario for each of the methods and assume that the probabilities can be computed exactly, which is not the case in practice" -- what do the authors mean by the ideal scenario? and if the calculated probabilities are not exact, then how reliable are the bounds?

[1]  Alvarez-Melis, David, and Tommi S. Jaakkola. "On the robustness of interpretability methods." ICML WHI. 2018.

[2] David Alvarez-Melis, Tommi S. Jaakkola, "Towards Robust Interpretability with Self-Explaining Neural Networks". In NeurIPS, 2018.

[3] Lakkaraju, Himabindu, Nino Arsov, and Osbert Bastani. "Robust and stable black box explanations." In ICML, 2018.
summary_of_the_review: The paper presents theoretical guarantees for different classes of explanation methods. However, the notion of stability/robustness/astuteness has been extensively studied in the existing literature and the novelty of the work is thus a bit unclear.
review_title: null

Meta-review: The paper explores "Astuteness of explainer", to measure reliability of the explanations. There were concerns about the overlap of the proposed work with existing literature.  It was felt that both theory and experiments need more development
Decision: Reject