One Explanation is Not Enough: Structured Attention Graphs for Image Classification
Authors: Vivswan Shitole
Li Fuxin
Minsuk Kahng
Prasad Tadepalli
Alan Fern
Venue: NeurIPS 2021 Poster (2021)
Keywords: explaining deep neural networks
perturbation based explanations

Abstract: Attention maps are popular tools for explaining the decisions of convolutional neural networks (CNNs) for image classification. Typically, for each image of interest, a single attention map is produced, which assigns weights to pixels based on their importance to the classification. We argue that a single attention map provides an incomplete understanding since there are often many other maps that explain a classification equally well. In this paper, we propose to utilize a beam search algorithm to systematically search for multiple explanations for each image. Results show that there are indeed multiple relatively localized explanations for many images. However, naively showing multiple explanations to users can be overwhelming and does not reveal their common and distinct structures. We introduce structured attention graphs (SAGs), which compactly represent sets of attention maps for an image by visualizing how different combinations of image regions impact the confidence of a classifier. An approach to computing a compact and representative SAG for visualization is proposed via diverse sampling. We conduct a user study comparing the use of SAGs to traditional attention maps for answering comparative counterfactual questions about image classifications. Our results show that the users are significantly more accurate when presented with SAGs compared to standard attention map baselines. 

One Explanation is Not Enough: Structured Attention Graphs for Image Classification
Vivswan Shitole, Fuxin, Minsuk Kahng, Prasad Tadepalli, Alan Fern Oregon State University
(shitolev, 1if, minsuk.kahng, tadepall, alan. haa..feem@@oreggntttee...ee
Abstract
Saliency maps popular tools for explaining the decisions of convolutional neural networks (CNNs) for image classification. Typically, for each image of interest, single saliency map produced, which assigns weights to pixels based on their importance to the classification. We argue that single saliency map provides an incomplete understanding since there are often many other maps that can explain a classification equally well. In this paper, we propose to utilize a beam search algorithm to systematically search for multiple explanations for each image. Results show that there are indeed multiple relatively localized explanations for many images. However, naively showing multiple explanations users can be overwhelming and does not reveal their common and distinct structures. We introduce structured attention graphs (SAGs), which compactly represent sets attention maps for an image by visualizing how different combinations of image regions impact the confidence of a classifier. An approach to computing a compact and representative SAG for visualization is proposed via diverse sampling, We conduct a user study comparing the use of SAGs to traditional saliency maps for answering comparative counterfactual questions about image classifications. Our results show that user accuracy is increased significantly when presented with SAGs compared to standard saliency map baselines.
Introduction
With the emergence of convolutional neural networks (CNNs) the most successful learning paradigm for image classification, the need for human understandable explanations of their decisions has gained prominence. Explanations lead to deeper user understanding and trust of the neural network models, which crucial for their deployment in safety-critical applications. They can also help identify potential causes of misclassification. An important goal of explanation is for the users to gain a mental model of the CNNs, so that the users can understand and predict the behavior of the classifier [17 in cases that have not been seen. A better mental model would lead appropriate trust and better safeguards of the deep networks in the deployment process.
A popular line of research towards this goal has been display attention maps, sometimes called saliency maps or heatmaps. Most approaches assign weights to image regions based on the importance of that region to the classification decision, which is then visualized to the user. This approach implicitly assumes that a single saliency map with region-specifee weights is sufficient for the human construct reasonable mental model of the classification decision for the particular image.
We argue that this is not always the case. Fig. d-f) show three localized attention maps highlighting different regions. Each of these images, if given as input to the CNN, results in very confident prediction of the correct category. However, this information is not apparent from a single saliency map as produced by current methods (Fig. (b-c)). This raises several questions: How many images have small localized explanations (i.e., attention maps) that lead to high confidence predictions? Are
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(a) Original Image
(b) Grad-CAM heatmap
(c) I-GOS heatmap
(d) Region (c) Region 2 (f) Region
(98% confidence) (97% confidence) (93% confidence)
Figure 1: An image (a) predicted Goldfinch with two saliency maps (b) and (c) obtained from different approaches as explanations for the classifier's (VGGNet (27] prediction. Each these saliency maps creates narrow understanding of the classifier. In (d), (e) and (f), we present three diverse regions of the image that might not be deemed important by the singleton saliency maps (b) and (c), and yet are classified as the target class with high confidence by the same classifier
91%
10%
Figure 2: Example SAG. For the goldfinch image on the left, a SAG on the right is structured as directed acyclic graph with each root node representing minimal region of the image sufficient to achieve a high confidence for the classifier's prediction. Each child node is obtained by deleting patch (denoted by red contour) from the parent, causing drop in the classifier's confidence. A significant drop in confidence implies the removed patch was of high importance to the classifier. More examples of SAGs are provided in the appendix
there multiple distinct high confidence explanations for each image, and if so, how to find them? How efficiently visualize multiple explanations to to yield deeper insights?
The first goal of this paper is to systematically evaluate the sizes and numbers of high-confidence local attention maps of CNN image classifications. For this purpose, rather than adopting commonly used gradient-based optimization approaches, we employ discrete search algorithms to find multiple high-confidence attention maps that are distinct in their coverage.
The existence of multiple attention maps shows that CNN decisions may be more comprehensively explained with a logical structure in the form of disjunctions of conjunctions of features represented by local regions instead of singleton saliency map. However, a significant challenge utilizing this as explanation is to come up with proper visualization to help users gain more comprehensive mental model of the CNN. This leads us our second contribution of the paper, Structured Attention Graphs (SAGs) [. which are directed acyclic graphs over attention maps of different image regions. The maps are connected based on containment relationships between the regions, and each map is accompanied with the prediction confidence of the classification based on the map (see Fig. 2 for an example). We propose a diverse sampling approach to select a compact and diverse set of maps for SAG construction and visualization.
This new SAG visualization allows users to efficiently view information from a diverse set of maps, which serves as a novel type of explanation for CNN decisions. In particular, SAGs provide insight by decomposing local maps into sub-regions and making the common and distinct structures across maps explicit. For example, observing that the removal of particular patch leads to huge drop in the confidence suggests that the patch might be important that context.
Source code for generating SAGs: http://sggggghhao.o////////////t

---

Our visualization can also be viewed as representing a (probabilistic) Monotone Disjunctive Normal Form (MDNF) Boolean expression, where propositional symbols correspond to primitive image regions we call 'patches'. Each MDNF expression is a disjunction of conjunctions, where any one of the conjunctions (e.g., one of the regions in Fig. D is sufficient for a high confident classification. Following [3], we call these minimal sufficient explanations (MSEs). Each conjunction is true only when all the patches that correspond to its symbols are present in the image.
We conducted a large-scale user study (100 participants total) to compare SAGs to two saliency map methods. We wondered if participants can answer challenging counterfactual questions with the help of explanations, e.g., how a CNN model classifies an image if parts of the image are occluded. In our user study, participants were provided two different occluded versions of the image (i.e.. different parts of the image are occluded and asked to choose one that they think would be classified more positively. Results show that when presented with SAG, participants correctly answer significantly more of these questions compared to the haselines, which suggests that SAGs help them build better mental models of the behavior of the classifier on different subimages.
In summary, our contributions are as follows:
With a beam search algorithm, we conducted a systematic study of the sizes and numbers of attention maps that yield high confidence classifications of a CNN (VGGNet (27]) on ImageNet 77. We showed that the proposed beam search algorithm significantly outperforms Grad-CAM and I-GOS in its capability to locate small attention maps to explain CNN decisions.
We introduce Structured Attention Graphs (SAGs) as a novel representation to visualize image classifications by convolutional neural networks.
We conducted user study demonstrating the effectiveness of SAGs in helping users gain deeper understanding of CNN's decision making.
2
Related Work
Much recent work on interpretability of CNNs is based on different ways to generate saliency maps depicting the importance of different regions to the classification decisions. These include gradient- based methods that compute the gradient of the outputs of diffcrent units with respect to pixel input
32 24 perturbation-based methods, which perturb parts of the input to see which ones are most important to preserve the final decision [5] [9) and concept-based methods, which analyze the alignment between individual hidden neurons and a set of semantic concepts B [4 [33] Importantly, they all generate a single saliency map for the image and have been found to
31
26
28
25
29
25
be brittle and unreliable [15
Another popular approach LIME (1), which constructs simplified interpretable local classifiers consistent with the black-box classifier in the neighborhood of single example. However, the local classifier Iearns a single linear function, which is sufficient to correctly classify the image but does not guarantee consistency with the classifier on its sub-images. More recently, Anchors [ learns multiple if-then-rules that represent sufficient conditions for classifications. However, this work did not emphasize image classification and did not systematically study the prevalence of multiple explanations for the decisions of CNNs. The if-then-rules in Anchors can be thought of as represented by the root nodes in our SAG. SAGs differ from them by sampling diverse set for visualization, as well as by additionally representing the relationships between different subregions in the image and their impact on the classification scores of the CNN. The ablation study of Section 5.3 shows that SAGS enable users to better understand the importance of different patches on the classification compared to Anchors-likk -lie rules represented by their root nodes.
Some prior work identifies explanations in terms of minimal necessary features S and minimal sufficient features [5]. Other work generates counterfactuals that are coherent with the underlying data distribution and provides feasible paths to the target counterfactual class based on density weighted metrics [19. In contrast, work yields multiple explanations in terms of minimal sufficient features and visualizes the score changes when some features are absent simultaneously answering multiple counterfactual questions.
Network distillation methods that compile a neural network into boolean circuit 4 or a decision tree [16] often yield uninterpretable structures due to their size or complexity. Our work balances the
3

---

information gain from explanations with the interpretability of explanations by providing small set of diverse explanations structured as a graph over attention maps.
Investigating Image Explanations
In this section, we provide comprehensive study of the number of different explanations of the images as well as their sizes. As the number of explanations might be combinatorial, we limit the search space by subdividing each image into 49
patches, which corresponds to the resolution utilized in Grad-CAM (24]. Instead of using heatmap algorithm, we propose to utilize search algorithms to check the CNN (VGGNet (27) predictions on many combinations of patches in order to determine whether they are able to explain the prediction of the CNN by being minimum sufficient explanation, defined as having a high prediction confidence from minimal combination of patches w.r.t. using the full image. The rationale is that if the CNN is capable of achieving the same confidence from subimage, then the rest of the image may not add substantially to the classification decision. This corresponds to common metrics used in evaluating explanations
[23] [8 20), which usually score saliency maps based on whether they could use a small highlighted part of the image to
achieve similar classification accuracy as using the full image. This experiment allows us to examine multiple interesting aspects, such as the minimal number of patches needed to explain each image, as well as the number of diverse explanations by exploring different combinations of patches. The ImageNet validation dataset of 50, 000 images is used for our analysis.
Formally, we assume a black- box classifier f that maps X - [0, 1] where X is an instance space and C is a set of classes. If E X is an instance, we use fz( to denote the output caasscoonitional probability on class с E C. The predicted class claditcon probability is referred as confidence of the classification
the rest of the paper. In this paper we assume X a set of images. Fach image x E X can be seen as set of pixels and is divided into r2 non-overlapping primitive regions Ps called 'patches,' i.e., U PPs, where p: P. 0 if i + j. For any image x X, we let of (x) =
fc(x) and call fx) the target class of x. We associate the part of the image in each patch with propositional symbol
literal. conjunction N of set of literals is the image region that corresponds to their union. The confidence of a conjunction is the output of the classifier applied to it, denoted by (e(NN. We determine this by running the classifier on a perturbed image where the pixels in x' \ N are either set to zeros or to a highly blurred version of the original image. The latter method is widely used in saliency map visualization methods remove information without creating additional spurious boundaries that can distort the classifier predictions [ [8 20
A minimal sufficient explanation (MSE) of an image E class w.r.t. f is defined as minimal conjunction/regionn that achieves a high prediction confidence (fc(N)) > Pafc(=)) w.r.t. using the entire image, where we set PA- 0.9 as sufficiently high fraction in experiments. That is, if we provide the classifier with only the region represented by the MSE, it will yield a confidence at that is at least 90% of the confidence for the original (unoccluded) image input. Often will be most interested in MSES for c c= (x).
3.1 Finding MSEs via Search
central claim of the paper we purport to prove is that the MSEs not unique, and be found by systematic search in the space of subregions of the image. The search objective is to find the minimal sufficient explanations N, that score higher than threshold where no proper sub-regions exceed the threshold, i.c., find all N₂ such that:
fc(N.) 2 Prfe(#), max fe(n,) < Pafe(x) R,CN,
(1)
for some high probability threshold Py.
But such a combinatorial search is too expensive to be feasible if we treat each image pixel as patch. Hence we divide the image into coarser set of ovrroviala patches. One could utilize a superpixel tessellation of an image to form the set of coarser patches. We adopt simpler approach: we downsample the image into low resolution r X image. Each pixel in the downsampled image corresponds to a coarser patch in the original image. Hence search on the downsampled image is computationally less expensive. We set the hyperparameter r = all our experiments. Further, to use an attention map M as a heuristic for search on the downsampled image, we perform average

---

100
Overlap
Method CombS
Mean
Variance
Mode
1.56
0.69
BeamS-3
1.72
0.98
BeamS-
1.87
1.01
2
Overlap
Method
Mean
Variance
Mode
CombS
3.16
5.82
Search withh Search width15
B
4.18
7.24
2
BeamS-15
4.51
7.22
Figure Percentage of images explained by different number of patches.
Table I:
Number of diverse MSEs obtained by allowing for different degrees of overlap.
pooling on M w.r.. each patch Py- This gives us an attention value M (py) for each patch, hence constituting coarser attention map. Once the attention map generated in low resolution, use bilinear upsampling to upsample it to the original image resolution to be used as mask. Bilinear upsampling creates slightly rounded region for each patch which avoids sharp corners that could be erroneously picked by CNNs as features.
We analyze different search methods for finding the MSEs:
Restricted Combinatorial Search: Combinatorial search constrains the size of the MSE to patches and finds the MSEs N₂ by searching for all combinations (conjunctions) of & patches that satisfy the criterion in Equation [ However, such combinatorial search over the entire downsampled image will be of the order (.)) which is computationally expensive. Hence, we first prune the search space by selecting the m most relevant patches, where the relevance of each patch Py is given by an attention map M (P,), and then carry out combinatorial search. We set 10 and vary < < m as hyperparameters. These hyperparameter choices allow the combinatorial search to complete in reasonable time.
Beam Search: Beam search searches for set of most MSEs S (Ni, N2...., Nu)) by maintaining a set of w distinct conjunctions of patches S (Ni, 2...... .... N as states at the ith iteration. It adds a patch to each conjunction
obtain new set of w distinct conjunctions Si+1 [N]+1 NN .....N.. ....)) as successor states for the next iteration, until they satisfy the criterion in equation to yield the set S. This is similar to the traditional beam search with beam width w, but we leverage the attention map M for generating the successor states. More concretely, the search is initialized by selecting the highest weighted w patches from the attention map as the set of initial w states 5 (NP, No, ...; ) At any iteration for each state Nj St we generate yf candidate successor states {Q) 2/2--.. Li by adding the highest weighted patches in the attention map that are not already in Ny. By doing this for each of the states in St, we generate set of w q candidate successor states. We obtain the classification score for each candidate successor state fe fe(Q), (zzz) and select the highest scoring states as the successor states gi+1 [N[+1 N7 ..... Ni+1). We chose
as a hyperparameter. This choice of value for the hyperparameter allows the beam search to complete in reasonable time.
3.2 Size of Minimal Sufficient Explanations
Each search method yields set of MSEs constituting multiple minimal regions an image sufficient for the black-box classifier to correctly classify the image with high confidence. We measure the size these minimal regions in terms the number patches they are composed of.
Fig. shows these plots for different search methods on the VGG network. Results on ResNet-50 are shown in the appendix. For each chosen size k. we plot the cumulative number of images whose MSE has a size < k. We see that 80% images of the ImageNet validation dataset have at least one MSE comprising of 10 or less patches. This implies that 80% images the dataset can be confidently classified by the CNN using a region of the image comprising of just 20% of the area of the original image, showing that most cases CNNs are able to make decisions based on local information instead of looking at the entire image. The remaining 20% of the images in the dataset have MSEs that
5

---

Overlap =
Overlap
# of diverse
1
2
4
5
2
3
4
5
Method
MSEs
CombS
87%
9%
2%
0%
0%
79%
5%
4%
2%
2%
BeamS-3
84%
11%
2%
0%
0%
65%
15%
6%
3%
2%
BeamS-15
79%
15%
2%
1%
0%
59%
16%
8%
5%
2%
Table 2: Percentage of images versus number of diverse MSEs obtained by allowing for different degrees overlap.
fall in the range of 11-49 patches (20%- 100% of the original image). Besides, one can see that many more images can be explained via the beam search approach w.r.t. conventional heatmap generation approaches, because the search algorithm evaluated combinations more comprehensively than these heatmap approaches and is less likely to include irrelevant regions, For example, at 10 patches, beam search with all beam sizes can explain about 80% of ImageNet images, whereas Grad-CAM and I-GOS can only explain about 50%. Although beam search as saliency map method is limited to low resolution whereas some other saliency map algorithms can generate heatmaps at higher resolution, this result shows that the beam search algorithm is more effective than traditional saliency map approaches at a low resolution.
3.3 Number of Diverse MSEs
Given the set of MSEs obtained via different search methods, also analyze the number of diverse MSEs that exist for an image. Two MSEs of the same image are considered to be diverse if they have less than two patches in common. Table provides the statistics on the number of diverse MSEs obtained by allowing for different degrees of overlap across the employed search methods. We see that images tend have multiple MSEs sufficient for confident classification, with 2z 2 explanations per image if we do not allow any overlap, and s 5 explanations per image if we allow a 1-patch overlap. Table provides the percentage of images having particular number of diverse MSEs. This result confirms our hypothesis that in many images CNNs have more than one way to classify each single image. In those cases, explanations based on a single saliency map pose an incomplete picture of the massion-making of the CNN classifier.
4 Structured Attention Graphs
From the previous section, we learned about the prevalence of multiple explanations. How can we then, effectively present them to human users so that they can better build mental models of the behavior of image classifiers?
This section introduces structured attention graphs (SAGs), a new way to compactly represent sets of attention maps for an image by visualizing how different combinations of image regions impact the confidence of classifier. Fig. 2 shows example. A SAG is directed acyelic graph whose nodes correspond to sets of image patches and edges represent subset relationships between sets defined by the removal of single patch. The root nodes of SAG correspond sets of patches that represent minimal sufficient explanations (MSEs) as defined in the previous section. Typically, the score of the root node N; is higher than all its children n. N;- The size of the drop in the score may correspond to the importance of the removed patch N, \ n,y. Under the reasonable assumption that the function is monotonic with the set of pixels covered by the region, the explanation problem generalizes learning Monotone DNF (MDNF) boolean expressions from membership (yes/no) queries, where each disjunction corresponds primitive patches. Information- -theoreti bounds imply that the general class of MDNF expressions not learnable with polynomial number of membership queries although some special cases are The next two subsections describe how SAG is constructed.
root node of the SAG, which in turn represents a conjunction of
learaalee 1
4.1 Finding Diverse MSES
We first find multiple candidate MSEs Neundidates = (N....., No), for some t > 1 through search. We observe that the obtained set Neandidates often has a large number of similar MSEs that share

---

Image
Get Perturbation Mask
P-322
Impoee mask
roak
Downsample
Upeampte
Diverse Subset Selection
Figure 4: Illustration of the steps for generating SAG (on top middle) from a given image (on top left).
a number of literals. To minimize the cognitive burden on the user and efficiently communicate relevant information with small number MSEs, we heuristically prune the above set select a small diverse subset. Note that we prefer a diverse subset (based on dispersion metrics) over representative subset (based on coverage metries). This choice was based on the observation that even a redundant subset of candidates Needundan: C Newndidates can achieve high coverage when the exhaustive set Neandidates has high redundancy. But Nredundant has lower information compared diverse subset of candidates Ndiverse Neandidates obtained by optimizing a dispersion metric.
More concretely, we want to find an information-rich diverse solution set Naiverse C Neandidates of desired size such that N, N2) is minimized for all N., N, Ndiveese where + j. We note that Ndiverse be obtained by solving the following subset selection problem:
Niiverse
argmin (X)), X |
where
(XX)
max NA
I N
For any subset X of the candidate set, (xX is the cardinality of the largest pairwise intersection over all member sets of X. Ndiverse is the subset with minimum value for (X) among all the subsets X of a fixed cardinality c. Minimizing (X) is equivalent to maximizing a dispersion function, for which greedy algorithm obtains solution up to provable approximation factor (6). The algorithm initializes Nuivense to the empty and at each step adds new set E Neandidates to it which minimizes max ma Navera ( n z|. The constant e is set to in order to show the users a sufficiently diverse and yet not overwhelming number of candidates in the SAG.
4.2 Patch Deletion to Build the SAG
After we have obtained the diverse set of candidates Naveres straightforward build the SAG. Each element of Naivene forms a root node for the SAG. Child nodes are recursively generated by deleting one patch at a time from a parent node (equivalent to obtaining leave-one-out subsets of parent set). calculate the confidence each node by forward pass of the image represented by the node through the deep network. Since nodes with low probability represent less useful sets of patches, we do not expand nodes with probability less than a threshold Pt as a measure to avoid visual clutter in the SAG. P. is set to 40% sufficiently low value.
flowchart illustrating the steps involved generate SAG for a given image input shown in Fig All the SAGs presented in the paper explain the predictions of VGGNet [27] as the classifier. Results on 5e,Net-50, as well as details regarding the computation costs for generating SAGs are provided in the appendix.

---

0.80) Here on mage dasefee ae "Linoushe" Thoo image trnk
G 5ob Hes is the came image coreileed as 'Linou eine". with comeporetnn atamben map soplanation Now will the robot to more corfdert coss Mig as Linoca nar (Clck options sints)
510) Hore is the same image diass oo "Limouinn"" whih lnnatin thine will the rotas be more
srwan bulta, whach highlymeed the robot to mose corforet clossligg os Uinouinn?? guea
comeeporcing
you
(a) Before explanation shown (b) After explanation shown
(c) Clicking on one of the options
Figure 5: An example question used the user study: (a) first, two options presented without a SAG explanation; (b) then, the same two options presented but with SAG explanation; (c) same as (b), but when a participant clicks on one of the options, related parts in the SAG are highlighted.
User Study
We conducted user study to evaluate the effectiivness of our proposed SAG visualization User studies have been popular method to evaluate explanations. For instance, Grad-CAM [24] con- ducted a user study to evaluate faithfulness and user trust on their saliency maps, and LIME [21] asked participants to predict generalizability of their method by showing their explanations to the participants. This section descrihes the design of our study and its results.
5.1 Study Design and Procedure
We measured human understanding of classifiers indirectly with predictive power, defined as the capability of predicting Je(N) given new set of patches N C that has not been shown. This can be thought as answering counterfactual questions "how will the classification score change if parts of the image are occluded?" Since humans do not excel in predicting numerical values, we focus on answering comparative queries, which predict the TRUE/FALSE value of the query: (NN) (NN2), with I being the indicator function. In other words, participants were provided with two new sets of patches that have not been shown in the SAG presented to them and were asked to predict which of the two options would receive higher confidence score for the class predicted by the classifier on the original image. Using this measure, we compared SAG with two ofate-of-the-a art saliency map approaches I-GOS 20 and Grad-CAM (24]
We recruited 60 participants comprising of graduate and undergraduate students engineering students at our university (37 males, 23 females, age: 18-30 years). Participants were randomly divided into three groups with each using one of the three saliency map approaches (i.c., between- subjects study design). They were first shown tutorial informing them about the basics of image classification and saliency map explanations. Then they were directed to the task that involved answering 10 sets of questions. Each set involved an image from ImageNet. These 10 images are sampled from a subset of ImageNet comprising of 10 classes. Each question set composed of two sections. First, participants were shown reference image with its classification but explanation. Then they were asked to select one of the two different perturbed versions of the reference image with different regions of the image occluded, based which they think would be more likely to be classified as the same class as the original image (shown in Fig. 5(a)). They were also asked to provide confidence rating about how sure they were about their response. In the second section, the
"The user study has been approved by IRB, followed the informed consent procedure and involved no more than minimal risk to the participants.
8

---

38
13.0
Score for 2000
Yean
-3
1205betand
GCCAP suc
(a) Number correct responses
(b) Participant confidence
(c) Time taken by participants
Figure 6: User study results comparing SAG to I-GOS and Grad-CAM. Dashed yellow lines in the
box plots denote mean values.
participants were shown the same reference image, but now with a saliency map or SAG additionally. They were asked the same question to choose one of the two options, but this time under the premise of an explanation. Along with a SAG representation, they can click on an option highlight the corresponding SAG nodes that have overlapping patches with the selected option and also highlight their outgoing edges (as shown in Fig. (()). Each participant was paid $10 for their participation.
The metrics obtained from the user study include the number of correct responses among the 10 questions (i.e., score) for each participant, the confidence score for each of their response (i.e., 100 being completely confident; 0 being not at all), and the time taken to answer each response.
5.2
Results
Fig. 5 shows the results comparing the metrics across the three conditions. Fig. 0 indicates that
participants got answers correct when they provided with SAG explanations (Mean=8.6.
SD=1.698) than when they were provided with I-GOS (Mean=5.44 SD= 181) or Grad-CAM
(Mean=5.3, SD=1.031) explanations. The differences between SAG and each of the two other methods are statistically significant (p <0.0001 in Mann-Whitney U tests for bo
Fig. b) shows the participants' levels of confidence for correct and incorrect answers across all three conditions after being provided with the explanations. The plots show that their confidence levels almost the same for both correct and incorrect responses the cases of I-GOS and Grad-CAM. However, for the case of SAG, participants have lower confidence for incorrect responses and higher confidence for correct responses. Interestingly, the variance in confidence for incorrect answers is very low for the participants working with SAG explanations. The increased confidence for correct responses and reduced confidence for incorrect responses implies that SAG explanations allow users to "know what they know" and when to trust their mental models. The indifference in confidence for correctness in J-GOS and Grad-CAM may imply that participants lack a realistic assessment of the correctness of their mental models.
Fig. ((c) shows that SAG explanations required more effort for participants interpret explanations. This is expected because SAGs convey more information compared to other saliency maps. However, believe that the benefits of gaining the right mental models and "appropriate trust" justify the longer time users need to digest the explanations.
5.3 Ablation Study
The two major components of the SAG condition used in the study are the graph-based attention map visualization and the user interaction for highlighting relevant parts in the visualization. As ablation study, we include two ablated versions of SAGs: (1) SAG/I, which is SAG without the click interaction, comprising only the graph visualization and (2) SAG/G, which SAG without the graph visualization, comprising only of the root nodes and the interaction. These root nodes of the SAG are similar in spirit the if-then rules of Anchors ?
and serve additional baseline.
"To check the normality of each variable, we first ran Shapiro Wilk tests, and the results indicated that some of the variables are not normally distributed. Thus we used the Mann- Whitney U tests which are often used for comparing the means of variables that are necessarily normally distributed [0)

---

10.3
CAC
SACiomest
Stacatter
alorten
Number of correct responses
(b) Participant confidence
(c) Time taken by participants
Figure 7: Ablation study results comparing SAG to SAG/I and SAG/G.
To evaluate how participants would work with SAG/I and SAG/G, additionally recruited 40 new participants (30 males, 10 females, age: 18-30 years) from the same recruitment effort as for earlier experiments and split them into two groups, with each group evaluating ablated version of SAGs via the aforementioned study procedure. The results of the ablation study are shown Fig. The participants received significantly lower scores when the user interaction (SAG/I) or the graph structure (SAG/G) are removed (p <0.0001 in Mann-Whitney U tests for both; data distribution shown in Fig. Ta This implies that both the interaction for highlighting and the graph structure are critical components of SAGs. The correlations of high confidence with correctness and low confidence with incorrectness are maintained across the ablated versions in Fig. 7bb. Participants spent a longer time to interpret SAG when they were not provided with the interaction feature, while interpreting just the root nodes took shorter time (as in Fig. 7cp. It is also worth noting that the differences between SAG without the interactive feature (SAG/I) and each of the two baseline methods (i.e., Grad-CAM and I-GOS) are also statistically significant (p =0.0004 and p =0.0012 2, respectively), showing the effectiveness of presenting multiple explanations using the graph structure. More data for all the 100 participants involved in the studies is provided in the appendix.
Conclusions and Future Work
In this paper, we set out to examine the number of possible explanations for the decision- decision-making of an image classifier. Through search methods, especially beam search, we have located an average of 2 explanations per image assuming no overlap and explanations per image assuming an overlap of most patch (about 2% of the area of the image). Moreover, we have found that 80% of the images in ImageNet has explanation of at most 20% of the area of the image, and it is shown that beam search more efficient than other saliency map approaches such as GradCAM and I-GOS in locating compact explanations at low resolution.
Based these findings, presented new visual representation, SAG, that explicitly shows multiple explanations of an image. It effectively shows how different parts of an image contribute to the confidence of an image classifier's decision. We conducted large-scale suman-subbect study (i.e., 100 participants), and participants were able to answer counterfactual-sty/ questions significantly more accurately with SAGs than with the baseline methods.
There are many interesting future research directions. One weakness of our approach is that takes time for people to digest SAGs than the existing methods. This could be mitigated via more advanced interfaces that allow users to interactively steer and probe the system to gain useful insights [12]. Another direction is generalize our approach multiple images and apply methodology to other modalities such as language and videos.
Acknowledgements
This work was supported by DARPA #N66001-17-2-4030 and NSF #1941892. Any opinions. findings, conclusions, or recommendations expressed are the authors" and do not reflect the views of the sponsors.
10

---

References
[1] Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi. 2014. On Exact Learning Monotone DNF from Membership Queries. In International Conference Algorithmic Learning Theory. 111-124.
[2] Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus Robert Müller, and Wojciech Samek. 2015. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PLoS One 10 (July 2015).
[3] David Bau, Bolei Zhou, Aditya Khosla, Aude Oliva, and Antonio Torralba. 2017. Network Dissection: Quantifying Interpretability of Deep Visual Representations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 6541-6549.
[4] Arthur Choi, Weijia Shi, Andy Shih, and Adnan Darwiche. 2017. Compiling neural networks into tractable Boolean circuits. intelligence (2017).
[5] Piotr Dabkowski and Yarin Gal. 2017. Real Time Image Saliency for Black Box Classifiers. In Advances in Neural Information Processing Systems (NIPS), Vol. 30.
[6] Anirban Dasgupta, Ravi Kumar, and Sujith Ravi. 2013. Summarization through submodularity and dispersion. In Proceedings of the 51 Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers). 1014-1022.
[7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 248-255.
[8] Amit Dhurandhar, Pin- Yu Chen, Ronny Luss Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das. 2018. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems (NIPS), Vol. 31. 592-603.
[9] R. C. Fong and A. Vedaldi. 2017. Interpretable Explanations of Black Boxes by Meaningful Perturbation. In 2017 IEEE International Conference on Computer Vision (ICCV). 3449-3457.
[10] Amirata Ghorbani, Abubakar Abid, and James Zou. 2019. Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 3681-3688.
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. 770-778.
[12] Fred Hohman, Minsuk Kahng, Robert Pienta, and Duen Horng Chau. 2019. Visual analytics in deep learning: An interrogative survey for the next frontiers. IEEE Transactions on Visualization and Computer Graphics 25, 8 (2019), 2674-2693.
[13] Omar Zia Khan, Pascal Poupart, and James P. Black. 2009. Minimal Sufficient Explanations for Factored Markov Decision Processes. In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS). AAAI.
[14] Been Kim, Martin Wattenberg, Justin Gilmer, Carrie Cai, James Wexler, Fernanda Viegas, and Rory Sayres. 2018. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In Proceedings of the 35th International Conference on Machine Learning (ICML). PMLR, 2668-2677.
[15] Pieter-Jan Kindermans, Sara Hooker, Julius Adebayo, Maximilian Alber, Kristof T Schütt, Sven Dähne, Dumitru Erhan, and Been Kim. 2017. The (un)reliability of saliency methods. arXiv preprint arXiv: 1.00867 (2017).
[16) Xuan Liu, Xiaoguang Wang, and Stan Matwin. 2018. Improving the interpretability of deep neural networks with knowledge distillation. In 2018 IEEE International Conference on Data Mining Workshops (ICDMW), IEEE, 905-912.

---

[17] Sina Mohseni, Niloofar Zarei, and Eric D Ragan. 2021. A multidisciplinary survey and frame- work for design and evaluation of explainable AI systems. ACM Transactions on Interactive Intelligent Systems (TiiS) 11, 3-4 (2021), 1-45.
[18] Vitali Petsiuk, Abir Das, and Kate Saenko. 2018. RISE: Randomized Input Sampling for Explanation of Black-box Models. In Proceedings of the British Machine Vision Conference (BMVC).
[19] Rafael Poyiadzi, Kacper Sokol, Raul Kantos-Rodriguue Tijl De Bie, and Peter Flach. 2020. FACE: Feasible and actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society. 344-350.
[20] Zhongang Qi, Saeed Khorram, and Li Fuxin. 2020. Visualizing Deep Networks by Optimizing with Integrated Gradients.. In Proceedings of the AAAI Conference on Artificial Intelligence.
[21] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016. Why should I trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD Interna- tional Conference on Knowledge Discovery and Data Mining. ACM, 1135-1144.
[22] Marco Túlio Ribeiro. Sameer Singh, and Carlos Guestrin. 2018. Anchors: High-Precision Modsl-Agnostic Explanations. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. AAAI Press, 1527-1535.
[23] Wojeiech Samek, Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, and Klaus- Robert Müller. 2016. Evaluating the visualization of what deep neural network has learned. IEEE transactions on neural networks and learning systems 28, 11 (2016), 2660-2673.
[24] R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and Batra. 2017. Visual Explanations from Deep Networks via Gradient-Based Localization. In 2017 IEEE International Conference on Computer Vision (ICCV). 616-626.
[25] Avanti Shrikumar, Peyton Greenside, Anna Shcherbina, and Anshul Kundaje. 2016. Not Just a Black Box: Learning Important Features Through Propagating Activation Differences. arXiv preprint I
(2016).
[26] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. 2014. Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps. ICLR Workshop (2014).
[27] Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large- scale image recognition. arXiv preprint 140iv: 1556 (2014).
[28] J.T. Springenberg. Dosovitskiy, T. Brox, and M. Riedmiller. 2015. Striving for Simplicity: The All Convolutional Net. In ICLR Workshop.
[29] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017. Axiomatic Attribution for Deep Networks. In Proceedings of the 34th International Conference on Machine Learning (ICML). PMLR, 3319-3328.
[30] Jacob O Wobbrock and Matthew Kay. 2016. Nonparametric statistics in human-computer interaction. In Modern Statistical Methods for HCI. Springer, 135-170.
[31] Matthew D. Zeiler and Rob Fergus. 2014. Visualizing and Understanding Convolutional Networks. In European Conference on Computer Vision (ECCV). Springer, 818-833. -333
[32] Jianming Zhang, Zhe Lin, Jonathan Brandt, Xiaohui Shen, and Stan Sclaroff. 2016. Top-down Neural Attention by Excitation Backprop. In European Conference on Computer Vision (ECCV). Springer, 543-559.
[33] Bolci Zhou, Yiyou Sun, David Bau, and Antonio Torralba. 2018. Interpretable Basis Decompo- sition for Visual Explanation. In Proceedings of the European Conference on Computer Vision (ECCV). 122-138.
12


Reviews:
[{"review_id": "ztkXVDxltTD", "reviewer": "Reviewer_uoik", "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.", "questions": "", "limitations": "", "rating": 4, "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": "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.\n\nComments:\nThe strongest point of the paper, the human study, has several issues:\n* 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.\n* 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.\n* 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.\n\n* 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. \n\n* 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.\n\n* No pseudocode or anonymized code repository are included, making it difficult to reproduce or check the results of the method.\n\nMinor comments:\n\n* 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.\n* The authors do not define what is an explanation or an attention map, despite using both interchangeably throughout the paper.\n* 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\")\n* 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).\n* The authors don't perform hyperparameter search, and don't provide sufficient explanations to most of the hyperparameter choices.\n* 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.\n\nMost of the paper is clearly written. There are a few typos that can be fixed:\nLine 30 -- figure 1 is a single figure, not figs in plural\nLine 31 -- \"if input to the CNN\" -> if given as input to the CNN\nLine 34 -- \"explanations (attention maps)\" -> explanations (i.e., attention maps)\nLine 120 -- A word is missing from the sentence\nLine 139 -- \"that score higher than a threshold and no proper sub-regions\" -> \"that score higher than a threshold and where no proper sub-regions\"\nLine 139 -- \"explanations (regions)\" -> \"explanations (i.e., regions)\" (also, this contradicts the definition in line 34)\nFigures 5-6: The numbers showing the average are difficult to read.\n\nThe 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.\n\nThe 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. \n\nThe 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.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "i21tpbFEgyv", "reviewer": "Reviewer_ay96", "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.", "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": "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.\n\nThe 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.\n\nI 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. \n\nThe 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. \n\nIt 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "berbm5p3_f5", "reviewer": "Reviewer_2sbT", "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.", "questions": "", "limitations": "", "rating": 4, "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": "# Concerns/Questions\n- 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.\n- 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.\n- 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.\n- The paper refers to a \"VGGNet\" multiple times. It is unclear whether this refers to a VGG-16, VGG-19, or something completely different.\n- 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.\n- 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:\n\n    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).\n\n    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?\n     3. Figure 5b: Do you have an intuition why the distribution of the confidence ratings in the SAG (incorrect) case looks like it does?\n    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.\n\n# Minor Comments\n- Please update the figures such that the text is larger and can be read more easily.\n- 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.\n- Please update the layout of your tables 1 and 2 as they are visually hard to parse.\n- Figure 5: It looks like the subfigures were cut off at the top and bottom. \n\n**Final comment**: I read the other reviews and the authors' rebuttal, and decided to keep my current rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations and potential negative societal impact in their submission.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "QSaIbcfo7BD", "reviewer": "Reviewer_sSPC", "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.", "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": "Strengths:\n+ 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.\n\n+ It is interesting to evaluate the agreement between computer vision and human vision on the attention maps.\n\nWeaknesses:\n- 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.\n\n- 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? \n\n- 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).\n\n- 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?\n\n- The writing can be improved. \n  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.\n  2). Symbol c is defined as the desired size in line 243, while it is also defined as a class in line 121.\n  3). The acronym MSE (Minimal sufficient explanation) may give rise to some confusion as it conventional stands for mean squared error.\n\n- 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nRegarding the potential societal impact, the authors may want to discuss computational models' bias, which may be reflected on class-specific attention maps.", "review_text": "", "extra_scores": {"ethical_concerns": "In this work, more than 60 persons participate in the user study. According to the answers to the questions in the checklist, 1.d, 5.a--c, the authors address my ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}]

Author rebuttal:

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)