Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a model that estimates the confidence of an explanation model of a classification model. The proposed model takes into account the variance in explanations of the explanation model, as well as the brittleness of the decision boundary around the sample that is to be explained. Samples that lie around a _complex_ decision boundary are assigned a high uncertainty. The complexity of the decision boundary is here measured as the length of the shortest path on the decision boundary that connects two close samples. This definition requires the computation of a geodesic distance, which is approximated over a Monte-Carlo sampling method. The experiments compare uncertainty methods for explanations on MNIST, fashion MNIST and three UCI datasets.
strength_and_weaknesses: # Strengths
* The model choices are generally well substantiated
* The authors explain well the (computational) challenges and limits of the method and possible remedies
* The figures are helpful to illustrate the ideas
* The proposed idea to use the geodesic kernel in the Gaussian process is sound and quite neat
# Weaknesses
* Although I feel like I understand the idea well and the reasoning behind it, I have problems to really understand the whole training and inference process. There is this one paragraph summarizing the method, but it depicts the method only textually and I am missing a more technical description of the method. After all, a lot of things come here together.
* I am sorry, but I have to ask: do we really need extra methods to derive uncertainty for explaining models of the actual model? It appears to me that the explainer is not really needed that much here after all, only for the variance term. Can't the proposed method be used as a confidence measure of the black-box model itself? There is a whole subsection describing well the issues with explaining models, their insufficiency, and their lack of actually explaining what is happening in the model. Why would we want to fix these flawed models, instead of scraping them and doing something proper? The proposed method itself relies on multiple hyper-parameters and it introduces another layer of possible inaccuracies, introducing possibly another false sense of trust. I believe that when the model could be used at least directly to replace the absolute failing uncertainty measure of softmax, that this would be a good contribution. I wonder if this is possible or if the inference would then take too long. This brings me to the next point:
* The sample complexity seems to be high, especially when brittle decision boundaries are supposed to be detected. I approve that there is a complexity analysis, but I wonder if in practice the time to train and to conduct inference for this model is so high that it prevents the usage of big datasets.
clarity,_quality,_novelty_and_reproducibility: The paper is good/nice to read and ok to follow, but somehow it's not exactly clear, which impacts in particular the reproducibility. I think the idea of using the geodesic distance on the decision boundary is sound and its application in this context seems novel. 
summary_of_the_review: Nice idea with a somewhat flawed application, trying to build upon the flawed explaining models. Clarity should be improved in the rebuttal. Training and Inference complexity is possibly awfully high. Because I like the idea, I would argue for a weak reject, although I see many issues with the paper as is.

# After Rebuttal Thoughts
The authors accomodated my request for clarity regarding the final method. I still have my concerns about the proposed approach, because it creates another layer of trust, that is however not certified. This is my main issue with the paper. The issue with the inference complexity also seems to consist, although I truly appreciate that the authors added a discussion about this.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on the problem of reliable explanations. The authors find that existing methods can be inconsistent or unstable. Therefore, there is an impending need to quantify the uncertainty of such explanation methods in order to understand when explanations are trustworthy. The authors introduce a novel uncertainty quantification method parameterized by a Gaussian Process model, which combines the uncertainty approximation of existing methods with a novel geodesic-based similarity which captures the complexity of the target black-box decision boundary.

strength_and_weaknesses: Strengths:
1. The authors introduce a geometric perspective on capturing explanation uncertainty and define a novel geodesic-based similarity between explanations.
2. The authors prove theoretically that the proposed similarity captures the complexity of the decision boundary from a given black-box classifier.
3. This paper proposed a novel Gaussian Process-based framework.


Weaknesses:
1.  Since the proposed method is a combination of several components, an ablation study is necessary to identify the contribution of each component. Otherwise, it is difficult to evaluate the effectiveness of the proposed method.

2. Performance is lacking on large-scale benchmarks. It is better to show some experimental results in large-scale datasets (e.g., CIFAR100, ImageNet) to demonstrate the effectiveness of the proposed method.

3. Some important related work missing, such as [1, 2]

[1] Zhang, Yujia, Kuangyan Song, Yiming Sun, Sarah Tan, and Madeleine Udell. "Why Should You Trust My Explanation?" Understanding Uncertainty in LIME Explanations." arXiv preprint arXiv:1904.12991 (2019).
[2] Patro, Badri N., Mayank Lunayach, Shivansh Patel, and Vinay P. Namboodiri. "U-cam: Visual explanation using uncertainty based class activation maps." In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7444-7453. 2019.

clarity,_quality,_novelty_and_reproducibility: This paper is well-presented and organized. The proposed idea is novel. The authors provide the code for experiment result reproduction.

summary_of_the_review: See *Strength And Weaknesses*
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes to quantify uncertainty of explanations by modelling explanations via a Gaussian process regression, and by defining a kernel called the "weighted exponential geodesic" (WEG) kernel. This kernel computes the similarity between two data points via their distances to the decision boundary, and the geodesic distance (of their "projections") on the decision boundary. Experiments show that the proposed measure indeed places larger uncertainty close to the decision boundary, and smaller uncertainty elsewhere.
strength_and_weaknesses: **Strengths**:

+ The paper tackles an important problem of estimating the uncertainty of explanations, which can be used to (potentially) judge whether or not trust the underlying explanation.

+ The proposed WEG kernel is a nice definition of the geodesic distance between two data points with respect to an underlying decision boundary. Arguments made to show that it constitutes a well-defined kernel, and that it is related to the exponential geodesic kernel are appreciated.

**Weaknesses**:

**Weak experiments; unclear if advances are practically relevant** 

The experiments in this paper consist of (1) qualitative uncertainty visualizations for two selected features, (2) showing that uncertainty decreases for regularized models. Either of these experiments are not convincing demonstrations of the usefulness of uncertainty quantification, as they do not deliver on the promise of "whether or not to trust an explanation". In particular, it is still unclear whether there is a clear, concrete setting where the proposed method is truly advantageous. Some examples of experiments closer to this goal include, (1) studying the faithfulness or robustness of explanations, and comparing them with this uncertainty metric. Does the proposed metric provide a cheaper way to identify data points whose explanations are likely to be unreliable based on these (or other) metrics? (2) A toy example where the explanations and the underlying uncertainties associated with explanations are known in advance, and a demostration of whether the proposed approach is able to correctly recover these. Note that these are mere suggestions, and that any experiment that can convince the readers of potential usefulness and practical utility of these methods is welcome.

**Missing discussion of scalability and statistical efficiency of proposed approach**

The core components of the proposed algorithm involve sampling from the decision boundary and computation of the geodesic distance. These are computationally expensive for large problems, as due to the curse of dimensionality one would expect the cost of characterizing the decision boundary (by sampling) to be exponential in the data dimensionality. The authors claim that they "apply adversarial attacks to reduce search space size" for MNIST, however it is unclear if this heuristic results in generation of independent samples from the decision boundary as required for the monte carlo sampling approach. Some discussion on the statistical properties of this approach and its computational complexity would improve the paper in my view.

**Distance from DB may not be as important as its curvature**

Consider the case of "explaining" a linear model, where some methods (gradients, smoothgrad) return the weight vector itself as an explanation (https://arxiv.org/abs/1711.06104), and thus there is no uncertainty in this case. However the proposed method still assigns non-zero uncertainty values to explanations based on both the geodesic distance as well as distance from the DB, which seems to contradict the ground truth. Thus the proposed approach may not be ideal to quantify uncertainty, and some discussion on this counterexample is welcome.

clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is mostly clear and easy to read. The discussion around Theorem 2 is difficult to understand (at least to me), and some larger context regarding why this theorem is interesting would help.

Quality: The technical quality in this paper is moderate. While the method itself seems mostly fine (barring an issue discussed in the weaknesses section), the paper has poor experimental results which reduces its overall quality.

Novelty: The methods proposed in this paper are novel to the best of my knowledge and add to the literature on estimating uncertainty of explanation methods.

Reproducibility: The paper scores low on reproducibility, as the paper does not provide either the source code to reproduce experiments, or a succinct description of the exact algorithm used. In particular, the precise algorithm to compute the geodesic distances or sample decision boundary points are not given explicitly.  
summary_of_the_review: While the proposed WEG kernel is interesting, the experiments are underwhelming, and do not convincingly demonstrate that the proposed approach achieves its goals of telling users when to trust an explanation method. As a result, I am leaning toward a reject.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes to quantify uncertainty of explanations by modelling explanations via a Gaussian process regression, and by defining a kernel called the "weighted exponential geodesic" (WEG) kernel. The reviewers and AC agree that the lack of stronger evidence for the effectiveness of this approach calls into question its practical relevance and usefulness. Further research is necessary to strengthen the case for this method and demonstrate its ability to achieve its intended objective.
Decision: Reject