One Explanation is Not Enough:
Structured Attention Graphs for Image Classification

A central claim of the paper we purport to prove is that the MSEs are not unique, and can be found by systematic search in the space of subregions of the image. The search objective is to find the minimal sufficient explanations $N_{i}$ that score higher than a threshold where no proper sub-regions exceed the threshold, i.e., find all $N_{i}$ such that:

for some high probability threshold $P_{h}$.

But such a combinatorial search is too expensive to be feasible if we treat each image pixel as a patch. Hence we divide the image into a coarser set of non-overlapping patches. One could utilize a superpixel tessellation of an image to form the set of coarser patches. We adopt a simpler approach: we downsample the image into a low resolution $r\times r$ image. Each pixel in the downsampled image corresponds to a coarser patch in the original image. Hence a search on the downsampled image is computationally less expensive. We set the hyperparameter $r=7$ in all our experiments. Further, to use an attention map $M$ as a heuristic for search on the downsampled image, we perform average pooling on $M$ w.r.t. each patch $p_{j}$. This gives us an attention value $M(p_{j})$ for each patch, hence constituting a coarser attention map. Once the attention map is generated in low resolution, we use bilinear upsampling to upsample it to the original image resolution to be used as a mask. Bilinear upsampling creates a slightly rounded region for each patch which avoids sharp corners that could be erroneously picked up by CNNs as features.

We analyze two different search methods for finding the MSEs:

Each search method yields a set of MSEs constituting multiple minimal regions of an image sufficient for the black-box classifier to correctly classify the image with a high confidence. We measure the size of these minimal regions in terms of the number of patches they are composed of.

Fig. 3 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 $\leq 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 of 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 in 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 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 an saliency map method is limited to a low resolution whereas some other saliency map algorithms can generate heatmaps at a higher resolution, this result shows that the beam search algorithm is more effective than traditional saliency map approaches at a low resolution.

Given the set of MSEs obtained via different search methods, we 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 1 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 to have multiple MSEs sufficient for confident classification, with $\approx 2$ explanations per image if we do not allow any overlap, and $\approx 5$ explanations per image if we allow a 1-patch overlap. Table 1 provides the percentage of images having a 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 decision-making of the CNN classifier.

We first find multiple candidate MSEs

$\tilde{N}_{\text{candidates}}=\{\tilde{N_{1}},...,\tilde{N_{t}}\}$, for some $t>1$ through search. We observe that the obtained set $\tilde{N}_{\text{candidates}}$ often has a large number of similar MSEs that share a number of literals. To minimize the cognitive burden on the user and efficiently communicate relevant information with a small number of MSEs, we heuristically prune the above set to select a small diverse subset. Note that we prefer a diverse subset (based on dispersion metrics) over a representative subset (based on coverage metrics). This choice was based on the observation that even a redundant subset of candidates $\tilde{N}_{\text{redundant}}\subset\tilde{N}_{\text{candidates}}$ can achieve high coverage when the exhaustive set $\tilde{N}_{\text{candidates}}$ has high redundancy. But $\tilde{N}_{\text{redundant}}$ has lower information compared to a diverse subset of candidates $\tilde{N}_{\text{diverse}}\subset\tilde{N}_{\text{candidates}}$ obtained by optimizing a dispersion metric.

More concretely, we want to find an information-rich diverse solution set $\tilde{N}_{\text{diverse}}\subset\tilde{N}_{\text{candidates}}$ of a desired size $c$ such that $|\tilde{N_{i}}\cap\tilde{N_{j}}|$  is minimized   for all $\tilde{N_{i}},\tilde{N_{j}}\in\tilde{N}_{\text{diverse}}$ where $i\not=j$. We note that $\tilde{N}_{\text{diverse}}$ can be obtained by solving the following subset selection problem:

For any subset $X$ of the candidate set, $\psi(X)$ is the cardinality of the largest pairwise intersection over all member sets of $X$. $\tilde{N}_{\text{diverse}}$ is the subset with minimum value for $\psi(X)$ among all the subsets $X$ of a fixed cardinality $c$. Minimizing $\psi(X)$ is equivalent to maximizing a dispersion function, for which a greedy algorithm obtains a solution up to a provable approximation factor [7]. The algorithm initializes $\tilde{N}_{\text{diverse}}$ to the empty set, and at each step adds a new set $y\in\tilde{N}_{\text{candidates}}$ to it which minimizes $\max_{z\in\tilde{N}_{\text{diverse}}}|y\cap z|$. The constant $c$ is set to $3$ in order to show the users a sufficiently diverse and yet not overwhelming number of candidates in the SAG.

After we have obtained the diverse set of candidates $\tilde{N}_{\text{diverse}}$, it is straightforward to build the SAG. Each element of $\tilde{N}_{\text{diverse}}$ 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 a parent set). We calculate the confidence of each node by a 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 $P_{l}$ as a measure to avoid visual clutter in the SAG. $P_{l}$ is set to $40\%$ as a sufficiently low value.

A flowchart illustrating the steps involved to generate a SAG for a given image input is shown in Fig.5. All the SAGs presented in the paper explain the predictions of VGGNet [28] as the classifier. Results on ResNet-50,

as well as details regarding the computation costs for generating SAGs are provided in the appendix.

We measured human understanding of classifiers indirectly with predictive power, defined as the capability of predicting $f_{c}(N)$ given a new set of patches $N\subset x$ that has not been shown. This can be thought of 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: $\mathbb{I}(f_{c}(N_{1})>f_{c}(N_{2}))$, with $\mathbb{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 a higher confidence score for the class predicted by the classifier on the original image.

Using this measure, we compared SAG with two state-of-the-art saliency map approaches I-GOS [21] and Grad-CAM [25].

We recruited 60 participants comprising of graduate and undergraduate students in 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.e., between-subjects study design). They were first shown a 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 a reference image with its classification but no 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 on which they think would be more likely to be classified as the same class as the original image (shown in Fig. 6(a)). They were also asked to provide a confidence rating about how sure they were about their response. In the second section, the 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 to highlight the corresponding SAG nodes that have overlapping patches with the selected option and also highlight their outgoing edges (as shown in Fig. 6(c)). 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.

Fig. 9 shows the results comparing the metrics across the three conditions. Fig. 9(a) indicates that participants got more answers correct when they were provided with SAG explanations (Mean$=$8.6, SD$=$1.698) than when they were provided with I-GOS (Mean$=$5.4, SD$=$1.188) 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 both³³3To 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 two variables that are not necessarily normally distributed [31].).

Fig. 9(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 are almost the same for both correct and incorrect responses in 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 I-GOS and Grad-CAM may imply that participants lack a realistic assessment of the correctness of their

mental models.

Fig. 9(c) shows that SAG explanations required more effort for participants to interpret explanations. This is expected because SAGs convey more information compared to other saliency maps. However, we believe that the benefits of gaining the right mental models and “appropriate trust” justify the longer time users need to digest the explanations.

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 an ablation study, we include two ablated versions of SAGs: (1) SAG/I, which is a SAG without the click interaction, comprising only of the graph visualization and (2) SAG/G, which is a SAG without the graph visualization, comprising only of the root nodes and the interaction. These root nodes of the SAG are similar in spirit to the if-then rules of Anchors [23] and serve as an additional baseline.

To evaluate how participants would work with SAG/I and SAG/G, we 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 an ablated version of SAGs via the aforementioned study procedure. The results of the ablation study are shown in Fig. 8. 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. 8(a)). 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 (as in Fig. 8(b)). Participants spent a longer time to interpret a SAG when they were not provided with the interaction feature, while interpreting just the root nodes took a shorter time (as in Fig. 8(c)). 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, 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.

Here we provide the scores of all the 100 users that participated in our user study. We see that the scores are fairly random when participants are not provided with any explanation. Moreover, participants spending more time on the questions do not necessarily achieve higher scores. After providing the explanations, we see that high scores (8 and above) are exclusively obtained by participants working with SAG and its ablations. As discussed earlier, participants working with SAG and SAG/I tend to have a higher response time than participants working with other explanations.

In Section 3, we state that images perturbations can be implemented by either setting the perturbed pixels to zeros or to a highly blurred version of the original image. All the experiments and results in the paper involve image perturbations obtained using the former method. In this section of the appendix, we provide a snapshot of the effect of using blurred pixels as perturbations instead. We use ImageNet validation set as the dataset and VGGNet as the classifier for these experiments. Fig. 10 shows that we obtain a better coverage of the images explained for a given size of minimal sufficient explanations (MSE) on using blurred pixels as perturbations. We hypothesize that this behavior is due to spurious boundaries created on setting the perturbed pixels to zeros, which undermines the classifier’s prediction scores. Such boundaries are absent on using blurred version of the original image for perturbations.

All the experiments and results in the paper use VGGNet as the black-box classifier. In this section of the appendix, we provide a brief analysis of the nature of multiple minimal sufficient explanations (MSEs) for ResNet [12] as the black-box classifier. We use the same dataset i.e., the ImageNet validation set for these experiments.

From Fig. 11, we see that the beam search is slightly sub-optimal at finding minimal MSEs for ResNet than for VGGNet. Similarly, Table 2 shows that beam search finds a lower number of MSEs on average when the classifier being explained is ResNet. The difference between the modes of the distributions for the two classifiers becomes stark on increasing the beam width. We hypothesize that these differences in the two distributions for the number of MSEs are due to the different perturbation maps obtained for the two classifiers, which we use for guiding the beam search. Digging deeper into the nature of MSEs for various classifiers is one of the possible avenues for future research.

A representation of computation cost of all the methods and baselines used in our work is provided in table 3 in terms of the wallclock time taken by each method to find and build the explanation for a single image. These values were obtained over a random sample of 100 images from the IMAGENET validation set using a single NVIDIA Tesla V100 GPU.

SAGs can be particularly useful to gain insights about the predictions of a neural network and facilitate debugging in case of wrong predictions. For example, Fig. 12 shows that the image with ground truth class as “seashore" is (wrongly) classified as a “shopping cart" by VGG-Net because the coast fence looks like a shopping cart. Interestingly, the classifier uses the reflection of the fence as further evidence for the class “shopping cart": with both the fence and the reflection the confidence is more than $83\%$ but with only the fence it was $52\%$. The patch corresponding to the reflection is not deemed enough on its own for a classification of shopping cart(evident from the drop in probabilities shown in SAG).

We provide more examples of SAGs for explaining wrong predictions by VGG-Net. These SAG explanations provide interesting insights into the wrong decisions of the classifier. For contrast, we also show the corresponding Grad-CAM and I-GOS explanations for the wrong predictions.

Here we provide more examples of SAGs for various images with their predicted (true) classes. In order to emphasize the advantage of our approach over traditional attention maps, we also provide the corresponding Grad-CAM and I-GOS saliency maps.