Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors suggest a method to construct multiple explanations for why a classifier predicted a specific class for a specific image, called SAG (Structured Attention Graphs). SAGs show multiple obfuscated versions of the original image, where different parts of each version are obfuscating as much as possible while keeping the original confidence of the classifier in its classification. The result resembles attention maps and saliency maps and can provide insights to which areas in the image are important for the classifier. The authors further compare their method to two baselines in a human study.  In the study, human participants predicted which of two perturbed images would provide a larger confidence for the classifier.
main_review: The idea of empirically hiding a part of the image to check whether that part is important for the classifier is simple yet elegant, and its uses in providing multiple attention maps compared to other methods are interesting. The authors did a great job creating a user study to check their method.  The paper is easy to read, apart from a few typos written below.

Comments:
The strongest point of the paper, the human study, has several issues:
* The authors only compare their method to two baselines, one of which is relatively old (from 2017). While human studies are limited by nature and one cannot compare to all baselines, the authors could at least explain why they chose these two baselines and not the many more that exist in the field, for example the ones they suggested in the related work section.
* The study itself tests how well can human participants predict the confidence of a classifier given an image with hidden patches, and given different explanations (either SAGs, GRAD-CAMs or I-GOSs). While the authors convincingly show that SAGs explain better which obfuscation will decrease the confidence of the classifier more, this performance is not surprising, since the test was designed specifically to highlight the strengths of SAG: Figure 4c shows that the explanations provide a numerical value to how much confidence did the classifier lose when a specific patch was removed. This numerical value gives the participants the direct answer to the question, without checking whether they really obtained a better understanding of which regions does the classifier pay attention to.
* This tailoring of the task to the method is further made worse since the heat maps provided by Grad-CAM and I-GOS are overlayed on top of the image (As in figure 1b-c) instead of highlighting the salient regions on top of darkened regions of the original image, as in figure 1d. This harder-to-understand display of the attention map leads to a false reduction in human performance, while the information necessary to transform the baseline saliency maps to similar explanations as in figure 1d is trivial.

* Apart from the human study, there isn’t a comparison between the baselines and the new method. While SAG provides multiple attention maps instead of the usual one, other methods that create attention maps for inner layers do the same. It would have been useful to provide an additional non-human test of the explanations. For example, it would be interesting to see whether the regions that are highlighted by the attention maps of other methods are enough for the classifier to provide confident predictions. 

* While the idea of finding which areas of the image are not necessary for classification is elegant, the algorithm proposed in the study is based on the repeated inference of the model on slightly altered images, making it very slow (30 seconds per image using a strong GPU). Furthermore, the authors do not compare this speed to other explanation methods, including the ones that are discussed in the paper.

* No pseudocode or anonymized code repository are included, making it difficult to reproduce or check the results of the method.

Minor comments:

* The introduction makes various claims without providing any reference to account for them. In general, the introduction lacks references to previous reviews of the large field of visual explanations to classifier decisions.
* The authors do not define what is an explanation or an attention map, despite using both interchangeably throughout the paper.
* The authors use the term "local" in several places in the paper without explaining its meaning in this context (e.g., "localized attention maps", "small localized explanations", "local attention maps")
* The ablation study, while important, might be a bit misleading: The authors discuss the importance of the interaction part where the human participants click on an option to see which nodes of the graph are relevant to it. While this part of the method is indeed important, it seems that it is not the interaction itself that provides the added performance, but rather the additional information provided after the click. A better ablation test would have been to either provide all information, without the participants clicking on an option, or waiting for the participants to click before displaying the information, and then comparing the results (in addition to the option of not providing the information at all).
* The authors don't perform hyperparameter search, and don't provide sufficient explanations to most of the hyperparameter choices.
* In figure 3, it is unclear how did the authors determine that GRAD-CAM and I-GOS cannot explain some of the images in ImageNet. If the metric for explainability is to check the size of the attention map and compare it to some threshold, then it is not a good proxy for explanation, as being small (or large) was not a goal for the other methods and is not a measurement of explainability.

Most of the paper is clearly written. There are a few typos that can be fixed:
Line 30 -- figure 1 is a single figure, not figs in plural
Line 31 -- "if input to the CNN" -> if given as input to the CNN
Line 34 -- "explanations (attention maps)" -> explanations (i.e., attention maps)
Line 120 -- A word is missing from the sentence
Line 139 -- "that score higher than a threshold and no proper sub-regions" -> "that score higher than a threshold and where no proper sub-regions"
Line 139 -- "explanations (regions)" -> "explanations (i.e., regions)" (also, this contradicts the definition in line 34)
Figures 5-6: The numbers showing the average are difficult to read.

The relation to prior work could be better. The authors only compare their work to two other baselines, one of which is from 2017, without explaining why the other methods described in the related work section were not compared to. There are many works generating saliency maps, attention maps and heat maps explaining the decision of the classifier on a single image, and the comparison could have been more thorough. If some methods were excluded from the human study due to the difficulties in obtaining participates, at least a proxy metric that does not require human participants could have been suggested and used.

The authors do a good job comparing SAG to one of the methods that were not part of the human study, Anchors; it would have been better if more methods were given a similar treatment. 

The idea of empirically checking which areas of the image are necessary for the classifier to predict confidently is interesting and the human study is informative. However, the empirical algorithm makes it not feasible for generating explanations in a large scale. It would be very interesting to see how this method can be combined with a less empirical approach, e.g., finding the regions that are necessary by studying the weights of the network instead of repeatedly running inference on the same image with slight alterations.



limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The contributions of the paper are threefold. The paper proposes t the use of beam search algorithm for evaluating attention maps of CNN image classifications. Introduce a novel graph representation for visualizing image classifications by CNNs called Structured Attention Graphs (SAGs). Conducted a user study for demonstrating the effectiveness of SAGs.
main_review: Overall, the paper introduces the idea of multiple explanations for analyzing CNN classifiers, which seems interesting and somewhat novel to me. In addition, it shows interesting findings on explaining image classification, such as the existence of multiple explanations for explaining an image and how to obtain such diverse explanations, which leads to an interesting analysis in Section 3.2. However, I am a bit lukewarm about this paper especially because its core piece, the structured representation (SAG), does not seem to provide very meaningful analysis on explaining image classifications.

The main concern I have is about the meaning of the connectivity in the attention graphs. It is unclear to me if the connectivity adds any additional information for the user to explain the images. It seems to me that presenting the root node for each MSE would already present all the minimal regions to the user, which makes me wonder about the need for a structured representation in this case.

I believe in terms of novelty the overall pipeline seems moderate since ultimately the paper still relies on attention maps as in Grad-CAM for the graph visualization. 

The paper seems algorithmically sound to me from the details presented. However, from a non-expert view on explainability techniques for CNNs, the motivation is unclear especially on how useful these explanations as attention maps are in practice. 

It seems that having multiple attention maps serves solely for improving image explainability with fewer image patches from Figure 3, which is ok, but not very exciting to me.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this work, the authors propose a new method that applies search strategies to find minimal yet diverse regions of interest in image classification. The proposed method considers classifiers as black-boxes and merely relies on the forward propagation so it is practically useful and would be more efficient than the gradient-based methods to generate class-specific attention maps. Moreover, a user study based on 100 participants is provided, which evaluates the attention maps generated by the proposed method from a perspective of human vision.
main_review: Strengths:
+ As mentioned in the summary, the proposed method is practically useful and would be more efficient than the gradient-based methods to generate class-specific attention maps.

+ It is interesting to evaluate the agreement between computer vision and human vision on the attention maps.

Weaknesses:
- For completeness, the search objective (Eq. (1)) should take into account or discuss all the possibilities. Nevertheless, the objective does not consider the situation that there is only one patch that has higher confidence than the image. In this situation, according to the objective, N_{i} would be an empty set.

- The link between the motivation "one explanation is not enough" and the proposed structured attention graphs (SAGs) is in question. As shown in Figure 1, there are three regions (i.e., d, e, f) of interest that lead to high confidence w.r.t. the ground-truth class. Can we merge them into one such that we have one comprehensive explanation? 

- The connection between the proposed method and conventional vision task(s) is unclear. Specifically, the related works, i.e., Grad-CAM, LayerCAM, Ablation-CAM, provide experimental results to demonstrate that their attention maps are helpful for class-specific localization. In contrast, this work does not either provide similar experiments or discuss this. Therefore, without convincing empirical evidence, I don't understand how the proposed method benefits the community for vision task(s).

- To study the problem of finding multiple explanations, multi-label datasets, e.g., MS COCO, may be better than single-label datasets, e.g., ImageNet, which is used in this work. In other words, for the images that are with single labels and are probably object-centric, what is the reason to generate multiple explanations for understanding the classification results?

- The writing can be improved. 
  1). Section 4.1 is not clear as X in line 236 is not self-contained. Does it represent a set of images, which is defined in line 121? However, according to the context, this section presents how to find multiple candidate minimal sufficient explanations on an image, instead of a set of images.
  2). Symbol c is defined as the desired size in line 243, while it is also defined as a class in line 121.
  3). The acronym MSE (Minimal sufficient explanation) may give rise to some confusion as it conventional stands for mean squared error.

- This work misses a few analyses for better understanding the proposed methods. Specifically, what is the time complexity w.r.t. the number of patches? How do the number of patches and P_{h} influence the proposed method and the conclusion of the user study?
limitations_and_societal_impact: In the checklist, 1.d, the answer states "We discuss a potential negative societal impact of our work in the appendix", but I couldn't find such a discussion in the appendix.

Regarding the potential societal impact, the authors may want to discuss computational models' bias, which may be reflected on class-specific attention maps.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper suggests a new method to generate and present attention maps for CNNs such that users can better understand the decisions of a CNN. They also empirically compare their method with two existing approaches in a psychophysical experiment.
main_review: # Concerns/Questions
- Section 3 is written in a confusing way: (1) The section contains general definitions and motivations just as well as specific parameter values and details relevant for the actual experiment - separating this a bit more will improve clarity. (2) In 3.1 the term "attention map" is used multiple times; however, it remains unclear whether the proposed method is supposed to generate such a map or if access to it is implicitly assumed. This section is hard to follow since the parts about the attention map are interleaved with those relevant to the MSEs. Furthermore, at the beginning it sounds like the search methods are meant to generate the attention map - however, in the description of the beam search method it sounds like access to an existing heatmap is assumed (line 170f.) Since this new method is the core contribution of the paper, this section must be improved in clarity.
- The proposed beam search (as far as I understood it) seems to assume the relevance of a specific image patch can be tested by looking at the activations caused by it in isolation (due to the way the candidate successor states are generated). This seems suboptimal given that there might be regions in the image which on their own are completely useless for the CNN but are highly relevant for the CNN if present at the same time. Either, this situation should be handled by the search algorithm or this issue should at least be reflected and discussed in the manuscript.
- Line 201f: I'm not sure whether the results presented in table 2 really allow us to say that "many" images have more than one way to classify them - if no overlap is allowed ~80% of the images only have 1 MSE which begs the question whether "many" is the best word to describe this situation.
- The paper refers to a "VGGNet" multiple times. It is unclear whether this refers to a VGG-16, VGG-19, or something completely different.
- Section 4: The description of how the SAG is constructed sounds a bit like the reverse process of what was described before in section 3 (instead of adding more and more image patches to the MSE candidates one now removes them one by one). By making the connection between these two things clearer the description of section 4 might be easier to digest for future readers.
- It's great to see that the new method was tested in a psychophysical experiment! Here are a few questions and comments regarding the experiment:

    1. In the experiment the task of selecting 1 out of 2 images with partially grayed out content was used as a proxy to determine how well participants understand the activations of a CNN. While it is totally fine that to use this artificial task (which I cannot imagine by itself will occur in real-world applications of XAI), I'm a bit skeptical of the possible implications: To be precise, in line 285ff. the "click interactions" in the SAG setting are introduced. First of all, highlighting image regions that are relevant in both the selected image option and the supporting SAG visualization are definitely helpful for users in this task (as this removes the mental burden for them of comparing the visualizations and finding the one that has the largest overlap in a certain region; this is also supported by your figure 6a). Since this highlighting option is only tested for the SAG condition and not the other attention map methods (here one could also add such a feature, e.g., by also applying the mask used to gray out the option 1 and 2 images to the attention map) this feels like it gives an unfair advantage to the SAG method. Of course one could argue that this is in fact a feature of the SAG method, however, this feature is only an advantage in this specific task setup and as stated before, the task setup used here is artificial in nature and does not reflect realistic use-cases of any attention method (which is fine as said before).

    2. Figure 5c: Do you have an idea why the reaction time for the SAG (before) condition is that different compared to other before conditions?
     3. Figure 5b: Do you have an intuition why the distribution of the confidence ratings in the SAG (incorrect) case looks like it does?
    4. I'm not sure whether one can use t-tests to test for significant differences given that your score data is bounded to lie between 1 and 10 and t-tests assume that the data/mean of the data is normally distributed. Hence, a different test that does not rely on said assumption would be more suitable in my opinion.

# Minor Comments
- Please update the figures such that the text is larger and can be read more easily.
- The examples of SAGs such as figure 2 and figure 4 are very blurred and almost impossible to read. Please replace them with a high-resolution version of said figures. In addition, figure 2 appears quite disruptive due to its black background.
- Please update the layout of your tables 1 and 2 as they are visually hard to parse.
- Figure 5: It looks like the subfigures were cut off at the top and bottom. 

**Final comment**: I read the other reviews and the authors' rebuttal, and decided to keep my current rating.
limitations_and_societal_impact: The authors discussed the limitations and potential negative societal impact in their submission.
review_title: null

Meta-review: The work proposes an occlusion based interpretability method that progressively occludes (from multiple starting points) an image to reveal areas where model confidence is substantially affected after occlusion. The primary concerns raised by reviewers focused on the human evaluation experiment (which is the primary evaluation provided in the work). While human evaluations are a fantastic way to evaluate interpretability methods, multiple reviewers noted the experiment is designed in a way to specifically favor the occlusion method rather than evaluate how the method would actually be used. Specifically, the only conclusion one can draw form the human eval is that showing how different occlusions of an image affect model confidence improves a human's ability to predict the effects of new occlusions of the same image. This does not lend much credibility as to the improved utility of the interpretability method because users of interpretability methods aren't actually interested in predicting model confidence under occlusion. Redesigning this study to focus on how users typically use these methods will improve the paper.
Decision: Accept (Poster)