Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposed to study the directional feature interactions to explain deep models. The proposed method is a graph-based explainer and the data can be considered as graphs. Then it studies the Bivariate Shapley values to consider the directional feature interactions. Experiments on several datasets show very promising results. 
main_review: + The studied problem is very important and interesting. XAI is highly related to the model's trust and safety

+ The proposed method- using Bivariate Shapley values to study feature interactions- is novel and reasonable. Considering data in DAG format is reasonable and their connections are represented as edges.

+ Experimental results are very promising and the analysis is very useful.

+ It is great to see some discussion about the connections between the proposed method and GNN explanation techniques. 

- While this work discussed several GNN explanation techniques, it would be better to compare the proposed method with them. I believe this can be done with simple modifications. For example, GNNExplainer (also some other GNN explanation techniques) does not require the model to be GNN---actually, it also treats the model as the black-boxes. Then when the input is represented as the DAG and the same feature interactions can be captured. Such experimental comparisons can better connect the proposed method to the GNN explanation area. 

- A better literature review of GNN explanation techniques is desired. 
summary_of_the_review: Overall, I think the studied problem is important and the proposed method is novel and reasonable. Considering that some experimental comparisons are missing, I believe this is a borderline paper and recommend a weak accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In previous studies, Shapley value has been widely used to explain model predictions, in which previous studies generally characterized importance for each feature instance separately. While some works have explored the effect of combinatorial features on prediction, no works have explored how features interact to influence each other, such as whether feature A is redundant if feature B is present. 

In order to achieve this goal, this paper offers an intuitive solution. The degree of feature interaction is estimated using a matrix called a bivariate Shapley explanation map. The j-th column and i-th row of the matrix represents how feature i influences the prediction if feature j has been included. Item ij can be seen as a revised Shapley value: rather than summing up the marginal contributions of all coalitions, it only considers them when feature j appears. They then propose four different types of interactions based on this definition: least/most influential features, directional/mutual redundancy. The experimental results indicate that the proposed method can efficiently discover these four types of feature interactions.

main_review: ## Strength:

-   The paper is well organized. The authors provide sufficient background and motivation. Despite the fact that the Shapley value has been applied to a wide variety of AI applications, there is precisely no method to explore how the features affect each other non-symmetrically.
This work takes an interesting approach. Making the interaction matrix conditional on a particular feature by modifying the original Shapley value sounds natural and simple. 


-   The paper provides extensive empirical results, which indicate that the approach is a good explanation for measuring the influence of features on each other.


## Weakness:

-   I am concerned about how well the sampling and kernel methods estimate the true bivariate Shapley explanation map?
 What is the variance of the estimation, and, how about the performance if one uses a true explanation map? In figure 2 and table 2, the authors only show BivShap-S and not the BivShap-K which is used in all the other experiments. How does the performance look like with BivShap-K.

- The bivariate Shapley explanation in  Eq (6) has a conditional interpretation as the authors describe, specifically, $E^2(u)_{ij}$ represents the importance of feature j conditioned on feature i being present.  Could this conditional representation be rigorously verified, say, in the EBM (energy based model) treatment of valuation criteria in [1]: 
 
- The monotone utility function is a necessary condition of the transitivity property of mutual redundancy in Corollary 1.1. Does the model used in experiments satisfy the monotone condition? If not, how do you select the features to mask in the mutual redundancy experiment of figure 2?
 
-   The authors claim that their method can be extended into high-order scenarios, and provide a method to calculate the multivariate explanation map in appendix E. As far as I see, a more complicated problem is how to define the interaction types in high-order scenarios and how to discover them? Does the PageRank algorithm fit into this case? I would appreciate a comment from the authors providing more discussions about it. It will be exactly encouraging for future works.
 
-   The part of experiments is hastily written and needs more refinement: algorithm 1 and algorithm 2 are totally the same; in F.1.1, Fig. 2(a) and 2(b) are missing; the reference of table and figure are interleaved in the main paper and appendix, that is quite unfriendly to readers. It is also not well illustrated how the PageRank algorithm is used to search for influential and redundant features. I think it is worthy of using an additional section to illustrate them.


[1] Bian, Y., Rong, Y., Xu, T., Wu, J., Krause, A., & Huang, J. (2021). Energy-Based Learning for Cooperative Games, with Applications to  Valuation Problems in Machine Learning. arXiv preprint arXiv:2106.02938.

summary_of_the_review: The idea and presentation of this work are, in my opinion, good despite existing problems. 
Furthermore, I think it would be better to move the analysis of COPDGene data into the appendix since all experimental results in this section are missing from the main paper. The illustrative samples in the appendix should also be included as part of the main paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors generalize the univariate Shapley method to bivariate Shapley method. The authors first build a directly graph based on the asymmetric bivariate Shapley value (adding feature j to all sets contained feature i). Then several graph algorithms are applied to analyze the directly graph to derive (1) univariate feature importance available in univariate approach and (2) relations like mutually redundancy only available in bivariate approaches. Experiments on several datasets with comparison to existing methods demonstrated the superiority of the proposed method.
main_review: Strength
1. The paper proposed an interesting and innovative graph-based method to generalize the univariate Shapley value method. The natural application of graph algorithms and concepts like PageRank, connected components is very interesting.
2. The authors carry out an extensive experiment on a diverse set of models and tasks with comparison to several state-of-the art method.
3. The empirical evaluation is quite convincing as the authors compare the performance of the model to tasks of bivariate but also univariate like feature importance. The proposed method performed better in both types of tasks.
4. The authors provide both theoretical justification as well as good illustrative examples.

Weakness
1. One important aspect is that there is quite some noise in the graph edge from Shapley estimation. It would be interesting to mention how the threshold can effect the results of the methods.

summary_of_the_review: The paper proposed an interesting and innovative solution to an important problem. Also the evaluation is very convincing.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper attempts to alleviate the shortcomings of existing local-feature-interaction explainers that assume symmetrical feature interactions by proposing a bivariate feature-explanation map that can capture asymmetrical (directional) feature interactions; this analysis provides evidence of mutual and directional redundancy, offering a comprehensive understanding of the features most influential for a given prediction. This proposed approach can also be instantiated using any univariate feature-based explanation method. Empirical results on image, text, and tabular data show the ability of the proposed method to accurately identify mutual and directional redundancies.
main_review: Strengths

The proposed methodology studies a relevant and important problem in the area of feature-based explanations by identifying the influence and directional feature interactions for an individual model prediction.

As far as I can tell, the work is original and distinct from previous work on identifying influential feature interactions which assume symmetrical interactions between pairs of features.

The proposed method appears to be technically sound and general, providing a framework for computing directional bivariate-explanation maps using any univariate explainer.

Experiments are performed on 7 datasets with image, text, and tabular data using deep-learning and tree-based models; the paper also compares the proposed approach to an appropriate set of relevant baselines.

The evaluation does a nice job of illustrating and validating the ability of the proposed method to identify mutual and directional redundancies between features, a significant shortcoming of existing approaches.


Weaknesses

I'm a bit confused about the results in section "(3) Influential Feature Evaluation"; first, it is not clear to me what the objective of the experiment is, i.e., is it to maintain high accuracy as the least important features are removed (if so, perhaps this should be stated in the text or in Figure 3; also, why not remove the most influential features and observe which methods degrade classification accuracy the fastest as in previous work (Hooker et al. 2018))? In any case, this section suggests that BivShap-S performs better than all other methods, though in Figure 3 it looks as though BivShap-K performs best. Also, why are the univariate approaches--methods designed specifically to identify the most influential features--not performing just as well as the bivariate approaches on this task?

In Table 2, why is posthoc performance so high (often 99 or 100 percent) when masking sinks? I thought these are typically characterized as the most important features (e.g., "awful" or "worst" in Figure 1). Also, for COPD, CIFAR10, and IMDB, the percentage of sources masked in Table 2 is very high compared to the percentage of sinks masked; could the low predictive performance simply be a result of removing the majority of the information and not necessarily the identification of important features?

It seems the E^2 matrix (bivariate interactions) would become unwieldy as d (the number of features) increases, reducing the interpretability of any manual inspection of the resulting directional graph G. This problem is exacerbated via analysis of higher-order multivariate interactions.

How does the choice of the univariate explainer affect the bivariate explanations? Is there a significant difference when using one univariate explainer versus another?


Minor Weaknesses

Why is BivShap-K not included in Figure 2?

It's difficult to tell where some of the lines are in Figure 3, consider using some transparency when plotting. Also consider using vector graphics for plots to allow zooming in (when viewed online) without losing clarity.

Missing '.' at the end of sentence 4 in the section, "Illustrative Example".


Additional Questions

What is the utility function used in the experiments to compute approximate BivShap-S?

The "Data." section says a neural network and a tree-based model is trained on the Divorce dataset, is this right?

What are the hardware details used for the experiments?
summary_of_the_review: The paper proposes a method for computing asymmetrical feature interactions for local explanations of model predictions. The proposed approach is better able to identify mutual and directional redundancies compared to existing methods on a wide range of datasets. Overall, the paper is well-written (aside from some minor clarity issues, see review above) and provides a method that can extend the use of any univariate explainer to generate directional bivariate feature-interaction explanations. One of my main concerns is how this bivariate explainer performs better than univariate explainers at a task seemingly designed for univariate explainers.
review_title: null

Meta-review: In this paper, the authors generalize the univariate Shapley method to bivariate Shapley method. The authors first build a directly graph based on the asymmetric bivariate Shapley value (adding feature j to all sets contained feature i). Then several graph algorithms are applied to analyze the directly graph to derive (1) univariate feature importance available in univariate approach and (2) relations like mutually redundancy only available in bivariate approaches. Experiments on several datasets with comparison to existing methods demonstrated the superiority of the proposed method.  All reviews are positive.
Decision: Accept (Spotlight)