summaries: 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.  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. 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.  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.
abstractText: As machine learning algorithms are deployed ubiquitously to a variety of domains, it is imperative to make these often black-box models transparent. Several recent works explain black-box models by capturing the most influential features for prediction per instance; such explanation methods are univariate, as they characterize importance per feature. We extend univariate explanation to a higher-order; this enhances explainability, as bivariate methods can capture feature interactions in black-box models, represented as a directed graph. Analyzing this graph enables us to discover groups of features that are equally important (i.e., interchangeable), while the notion of directionality allows us to identify the most influential features. We apply our bivariate method on Shapley value explanations, and experimentally demonstrate the ability of directional explanations to discover feature interactions. We show the superiority of our method against state-of-the-art on CIFAR10, IMDB, Census, Divorce, Drug, and gene data.
references.authors: R. Achanta A. Shaji K. Smith A. Lucchi P. Fua Sabine Süsstrunk
references.title: SLIC Superpixels Compared to State-of-the-Art Superpixel Methods
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: Yoav Arnson Yehuda Shoenfeld Howard Amital
references.title: Effects of tobacco smoke on immunity, inflammation and autoimmunity
references.venue: Journal of autoimmunity,
references.authors: Sebastian Bach Alexander Binder Grégoire Montavon Frederick Klauschen Klaus-Robert Müller Wojciech Samek
references.title: On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation
references.venue: PloS one,
references.authors: Jørgen Bang-Jensen Gregory Z Gutin
references.title: Digraphs: theory, algorithms and applications
references.venue: Springer Science & Business Media,
references.authors: Roderick Bloem Harold N Gabow Fabio Somenzi
references.title: An algorithm for strongly connected component analysis in n log n symbolic steps
references.venue: Formal Methods in System Design,
references.authors: Thomas Bonald Nathan de Lara Quentin Lutz Bertrand Charpentier
references.title: Scikit-network: Graph analysis in python
references.venue: Journal of Machine Learning Research,
references.authors: Howard D Bondell Brian J Reich
references.title: Simultaneous regression shrinkage, variable selection, and supervised clustering of predictors with oscar
references.authors: Jianbo Chen Le Song Martin Wainwright Michael Jordan
references.title: Learning to explain: An information-theoretic perspective on model interpretation
references.venue: Proceedings of the 35th International Conference on Machine Learning,
references.authors: Tianqi Chen Carlos Guestrin
references.title: XGBoost: A Scalable Tree Boosting System
references.venue: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
references.authors: Kyunghyun Cho Bart van Merrienboer Çaglar Gülçehre Fethi Bougares Holger Schwenk Yoshua Bengio
references.title: Learning phrase representations using RNN encoder-decoder for statistical machine translation
references.venue: CoRR, abs/1406.1078,
references.authors: Smita Chormunge Sudarson Jena
references.title: Correlation based feature selection with clustering for high dimensional data
references.venue: Journal of Electrical Systems and Information Technology,
references.authors: Ian Covert Scott Lundberg Su-In Lee
references.title: Feature removal is a unifying principle for model explanation methods
references.venue: CoRR, abs/2011.03623,
references.authors: Ian Covert Scott Lundberg Su-In Lee
references.title: Understanding global feature contributions through additive importance measures
references.venue: arXiv preprint arXiv:2004.00668,
references.authors: Ian Covert Scott M Lundberg Su-In Lee
references.title: Understanding global feature contributions with additive importance measures
references.venue: Advances in Neural Information Processing Systems,
references.authors: Tianyu Cui Pekka Marttinen Samuel Kaski
references.title: Learning global pairwise interactions with bayesian neural networks
references.venue: arXiv preprint arXiv:1901.08361,
references.authors: Anupam Datta Shayak Sen Yair Zick
references.title: Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems
references.venue: IEEE symposium on security and privacy (SP),
references.authors: Dheeru Dua Casey Graff
references.title: UCI machine learning repository, 2017
references.venue: URL http://archive. ics.uci.edu/ml
references.authors: Alexandre Duval Fragkiskos D Malliaros
references.title: Graphsvx: Shapley value explanations for graph neural networks
references.venue: arXiv preprint arXiv:2104.10482,
references.authors: E. Fehrman A.K. Muhammad E.M. Mirkes V. Egan A.N. Gorban
references.title: The Five Factor Model of personality and evaluation of drug consumption risk
references.authors: Matthias Fey Jan Eric Lenssen
references.title: Fast graph representation learning with pytorch geometric, 2019
references.venue: URL http://arxiv.org/abs/1903.02428. cite arxiv:1903.02428
references.authors: Christopher Frye Colin Rowat Ilya Feige
references.title: Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability
references.venue: Advances in Neural Information Processing Systems,
references.authors: Michel Grabisch Marc Roubens
references.title: An axiomatic approach to the concept of interaction among players in cooperative games
references.venue: International Journal of game theory,
references.authors: Riccardo Guidotti Anna Monreale Salvatore Ruggieri Franco Turini Fosca Giannotti Dino Pedreschi
references.title: A survey of methods for explaining black box models
references.venue: ACM computing surveys (CSUR),
references.authors: Isabelle Guyon André Elisseeff
references.title: An introduction to variable and feature selection
references.venue: Journal of machine learning research,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Joseph D Janizek Pascal Sturmfels Su-In Lee
references.title: Explaining explanations: Axiomatic feature interactions for deep networks
references.venue: Journal of Machine Learning Research,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In ICLR (Poster),
references.authors: Jon M Kleinberg
references.title: Hubs, authorities, and communities
references.venue: ACM computing surveys (CSUR), 31(4es): 5–es,
references.authors: Alex Krizhevsky
references.title: Learning multiple layers of features from tiny images
references.venue: Technical report,
references.authors: Edward Loper Steven Bird
references.title: Nltk: The natural language toolkit
references.venue: Proceedings of the ACL Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics. Philadelphia: Association for Computational Linguistics,
references.authors: Scott M Lundberg Su-In Lee
references.title: A unified approach to interpreting model predictions
references.venue: Advances in Neural Information Processing Systems,
references.authors: Scott M Lundberg Gabriel G Erion Su-In Lee
references.title: Consistent individualized feature attribution for tree ensembles
references.venue: arXiv preprint arXiv:1802.03888,
references.authors: Scott M Lundberg Gabriel Erion Hugh Chen Alex DeGrave Jordan M Prutkin Bala Nair Ronit Katz Jonathan Himmelfarb Nisha Bansal Su-In Lee
references.title: From local explanations to global understanding with explainable ai for trees
references.venue: Nature machine intelligence,
references.authors: Dongsheng Luo Wei Cheng Dongkuan Xu Wenchao Yu Bo Zong Haifeng Chen Xiang Zhang
references.title: Parameterized explainer for graph neural network
references.venue: arXiv preprint arXiv:2011.04573,
references.authors: Andrew Maas Raymond E Daly Peter T Pham Dan Huang Andrew Y Ng Christopher Potts
references.title: Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics
references.venue: Human language technologies,
references.authors: Aria Masoomi Chieh Wu Tingting Zhao Zifeng Wang Peter Castaldi Jennifer Dy
references.title: Instancewise feature grouping
references.venue: Advances in Neural Information Processing Systems,
references.authors: W Meeusen L Cuyvers
references.title: Clique detection in directed graphs: A new algorithm
references.venue: Journal of Computational and Applied Mathematics,
references.authors: Guillermo Owen
references.title: Multilinear extensions of games
references.venue: Management Science, 18(5-Part-2):64–
references.authors: Lawrence Page Sergey Brin Rajeev Motwani Terry Winograd
references.title: The pagerank citation ranking: Bringing order to the web
references.venue: Technical report, Stanford InfoLab,
references.authors: Jeffrey Pennington Richard Socher Christopher D. Manning
references.title: Glove: Global vectors for word representation
references.venue: In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532–1543,
references.authors: Elizabeth A. Regan John E. Hokanson James R. Murphy Barry Make David A. Lynch Terri H. Beaty Douglas Curran-Everett Edwin K. Silverman James D. Crapo
references.title: Genetic epidemiology of COPD (COPDGene) study
references.venue: design. COPD,
references.authors: Marco Tulio Ribeiro Sameer Singh Carlos Guestrin
references.title:  why should i trust you?" explaining the predictions of any classifier
references.venue: In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining,
references.authors: Patrick Schwab Walter Karlen
references.title: Cxplain: Causal explanations for model interpretation under uncertainty
references.venue: Advances in Neural Information Processing Systems,
references.authors: Yoav Shoham Kevin Leyton-Brown
references.title: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations
references.authors: Avanti Shrikumar Peyton Greenside Anshul Kundaje
references.title: Learning important features through propagating activation differences
references.venue: In International Conference on Machine Learning,
references.authors: Erik Štrumbelj Igor Kononenko
references.title: Explaining prediction models and individual predictions with feature contributions
references.venue: Knowledge and information systems,
references.authors: Agnieszka Strzelak Aleksandra Ratajczak Aleksander Adamiec Wojciech Feleszko
references.title: Tobacco smoke induces and alters immune responses in the lung triggering inflammation, allergy, asthma and other lung diseases: a mechanistic review
references.venue: International journal of environmental research and public health,
references.authors: Mukund Sundararajan Ankur Taly Qiqi Yan
references.title: Axiomatic attribution for deep networks
references.venue: In International Conference on Machine Learning,
references.authors: Mukund Sundararajan Kedar Dhamdhere Ashish Agarwal
references.title: The shapley taylor interaction index
references.venue: In International Conference on Machine Learning,
references.authors: Mukund Sundararajan Kedar Dhamdhere Ashish Agarwal
references.title: The Shapley Taylor Interaction Index
references.venue: In Proceedings of the 37th International Conference on Machine Learning,
references.authors: R. Tarjan
references.title: Depth-first search and linear graph algorithms
references.venue: SIAM J. Comput.,
references.authors: Michael Tsang Dehua Cheng Yan Liu
references.title: Detecting statistical interactions from neural network weights
references.venue: arXiv preprint arXiv:1705.04977,
references.authors: Michael Tsang Youbang Sun Dongxu Ren Yan Liu
references.title: Can i trust you more? model-agnostic hierarchical explanations
references.venue: arXiv preprint arXiv:1812.04801,
references.authors: Michael Tsang Sirisha Rambhatla Yan Liu
references.title: How does this interaction affect me? interpretable attribution for feature interactions
references.venue: arXiv preprint arXiv:2006.10965,
references.authors: Jiaxuan Wang Jenna Wiens Scott Lundberg
references.title: Shapley flow: A graph-based approach to interpreting model predictions
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: David C Yang Ching-Hsien Chen
references.title: Cigarette smoking-mediated macrophage reprogramming: mechanistic insights and therapeutic implications
references.venue: Journal of nature and science,
references.authors: Rex Ying Dylan Bourgeois Jiaxuan You Marinka Zitnik Jure Leskovec
references.title: Gnnexplainer: Generating explanations for graph neural networks
references.venue: Advances in neural information processing systems,
references.authors: Mustafa Kemal Yöntem Kemal Adem Tahsin İlhan Serhat Kiliçarslan
references.title: DIVORCE PREDICTION USING CORRELATION BASED FEATURE SELECTION AND ARTIFICIAL NEURAL NETWORKS
references.venue: Nevşehir Hacı Bektaş Veli Üniversitesi SBE Dergisi,
references.authors: Jinsung Yoon James Jordon Mihaela van der Schaar
references.title: Invase: Instance-wise variable selection using neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Hao Yuan Haiyang Yu Shurui Gui Shuiwang Ji
references.title: Explainability in graph neural networks: A taxonomic survey
references.venue: CoRR, abs/2012.15445,
references.authors: Hao Yuan Haiyang Yu Jie Wang Kang Li Shuiwang Ji
references.title: On explainability of graph neural networks via subgraph explorations
references.venue: arXiv preprint arXiv:2102.05152,
references.authors: Matthew D Zeiler Rob Fergus
references.title: Visualizing and understanding convolutional networks
references.venue: In European conference on computer vision,
references.authors: Xiangrong Zeng Mário AT Figueiredo
references.title: Solving oscar regularization problems by fast approximate proximal splitting algorithms
references.venue: Digital Signal Processing,
references.authors: Hao Zhang Yichen Xie Longjie Zheng Die Zhang Quanshi Zhang
references.title: Interpreting multivariate shapley interactions in dnns
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
sections.heading: 1 INTRODUCTION
sections.text: The ability to interpret and understand the reasoning behind black box decision-making increases user trust; it provides insights into how a model is working and, as a consequence, how a model can be improved. This has led to a large body of work on the development of explanation methods (Ribeiro et al., 2016; Chen et al., 2018; Yoon et al., 2018; Lundberg & Lee, 2017) applied to blackbox models. Intuitively, such methods aim to explain black-box behavior by understanding how individual features influence prediction outcomes. Recently, Covert et al. Covert et al. (2020a) proposed a unifying mathematical framework capturing a broad array of explainability techniques, termed Removal-based Explanation methods. Nevertheless, the overwhelming majority of existing literature on explainability has a significant drawback: present methods only provide univariate explanations and, as a result, they do not take into account feature interactions. This is problematic precisely because many black box models, such as deep neural networks, perform well by creating complex structures and combining features in their latent layers. To address this, recent methods have been proposed to learn the interaction between features (Sundararajan et al., 2020a; Maas et al., 2011). Their definition of interaction assumes features affect each other symmetrically; however, in many real-world applications, feature interactions may be asymmetrical. We also observe this experimentally (Fig. 1), and argue of the importance of developing black-box interactions that not only capture interactions, but also incorporate asymmetry. Overall, we make the following contributions:
  • We propose a method to extend any given univariate removal-based explanation to a bivariate explanation model that can capture asymmetrical feature interactions, represented as a directed graph. Our method is general, and can be applied to a broad array of univariate removal-based explanations, as defined by Covert et al. (2020a). • We show that analyzing this graph gives a semantically-rich interpretation of black boxes. In particular, beyond the ability to identify most influential features, the graph can identify directionally redundant features, i.e., features whose presence negates the influence of other features, as well as mutually redundant features, i.e., features that are interchangeable. These two concepts cannot be captured by neither univariate nor symmetric bivariate explanations in existing literature. • We systematize the analysis of the directed explanation graph, providing both formal definitions of the aforementioned notions as well as algorithms for scrutinizing and explaining black-box model behavior. We also provide theoretical justification for these definitions in the context of SHAP, the Shapley value explanation map introduced by Lundberg & Lee (2017).
  • Finally, extensive experiments on MNIST, CIFAR 10, IMDB, Census, Divorce, Drug, and gene expression data show that our explanation graph outperforms prior symmetrical interaction explainers as well as univariate explainers with respect to post-hoc accuracy, AUC, and time.
sections.heading: 2 RELATED WORK
sections.text: Many methods have been proposed for explaining black box models (Guidotti et al., 2018). For instance, LIME (Ribeiro et al., 2016) explains the prediction of a model by learning a linear model locally around a sample, through which it quantifies feature influences on the prediction. SHAP (Lundberg & Lee, 2017) learns an influence score for each feature based on the Shapley value (Shapley, 2016). L2X (Chen et al., 2018) learns a set of most influential features per sample based on the mutual information between features and labels. Recently, Covert et al. (2020a) unified many of such explanation methods under a single framework; we present this in detail in Sec. 3.
  However, all of these methods only capture the univariate influences of each feature; i.e., they do not explain feature interactions. Discovering feature interactions has drawn recent interest in machine learning (Bondell & Reich, 2008; Chormunge & Jena, 2018; Zeng & Figueiredo, 2014; Janizek et al., 2021; Zhang et al., 2021; Tsang et al., 2018; 2020). Tsang et al. (2017) proposed a framework to detect statistical interactions in a feed-forward neural network by directly interpreting the weights of the model. Cui et al. (2019) proposed a non-parametric probabilistic method to detect global interactions. However, most such methods study feature interactions globally (for all instances). In contrast, our work detects interactions per individual instance. The work more related to explainability of a black box via feature interaction is Shapley interaction. Grabisch & Roubens (1999) proposed a Shapley interaction value to explore the interaction between features rather than feature influence. Lundberg et al. (2018) and Sundararajan et al. (2020a) applied Shapley interaction value to explain black box predictions. Instance-wise Feature Grouping (Masoomi et al., 2020) explored the effects of feature interaction by allocating features to different groups based on the similarity of their contribution to the prediction task. These methods assume a symmetrical interaction between features; in contrast, our method provides instance-wise explanations that can capture asymmetrical (directional) interactions.
  Another type of explainers are Graph Neural Network (GNN) explainers (Yuan et al., 2020). These methods assume that the black-box model has a GNN architecture; i.e. the model incorporates the input graph structure in its predictions. In contrast, our method allows the black box to be any type of function (e.g., CNN, GNN, Random Forest) and does not assume access to a graph structure: we learn the feature interactions directly from the data. A small subset of GNN explainers, especially local, perturbation-based methods such as (Yuan et al., 2021; Duval & Malliaros, 2021; Luo et al., 2020; Ying et al., 2019) can be applied to black-box models. This can be done by assuming a non-informative interaction structure on the data and allowing the explainers to mask or perturb the interaction edges. However, non-GNN black box models are unable to utilize the graph structure.
  Causal methods provide explanations through feature influence by utilizing knowledge about causal dependencies. Frye et al. (2020) generalized the Shapley-value framework to incorporate causality. In particular, they provided a new formulation for computing Shapley value when a partial causal understanding of data is accessible, which they called Asymmetric Shapley values. Wang et al. (2021) extend this idea to incorporate the entire casual graph to reason about the feature influence on the output prediction. Causal methods rely on prior access to casual relationships; in contrast, our method learns the asymmetrical interaction between features rather than the casual dependencies.
sections.heading: 3 BACKGROUND
sections.text: In general, explainability methods aim to discover the reason why a black box model makes certain predictions. In the local interpretability setting (Chen et al., 2018; Lundberg & Lee, 2017; Ribeiro et al., 2016; Sundararajan et al., 2017), which is our main focus, explanations aim to interpret predictions made by the model on an individual sample basis. Typically, this is done by attributing the prediction to sample features that were most influential on the model’s output. The latter is discovered through some form of input perturbation (Lundberg & Lee, 2017; Zeiler & Fergus, 2014). In a recent paper, Covert et al. (2020a) proposed a unifying framework for a variety of different explainability methods. As our work generalizes this framework, we formally describe the removal-based explanation framework by Covert et al. below.
  Univariate Removal-Based Explanations. The unifying framework of Covert et al. identifies three stages in a removal-based explanation method. The first, feature-removal, defines how the method perturbs input samples by removing features; the second, termed model-behavior, captures the effect that this feature removal has on the black-box model predictions; finally, the summary stage abstracts the impact of feature subset selection to a numerical score for each feature, capturing the overall influence of the feature in the output.
  Formally, a black-box model is a function f : X → Y , mapping input features x ∈ X ⊆ Rd to labels y ∈ Y . Let D ≡ {1, . . . , d} be the coordinates of the feature space. Given an input x ∈ X and a subset of features S ⊆ D, we denote by xS = [xi]i∈S ∈ Rd the projection of x to the features in S. In the local interpretability setting, we are given a black-box model f , an input x ∈ X and in some methods the additional ground truth label y ∈ Y , and wish to interpret the output f(x) produced by the model. The three stages of the removal based model are defined by a triplet of functions (F, u,E), which we define below.
  First, the feature removal stage is defined by a subset function
  F : X × P (D) → Y, (1)
  where P (D) = 2D is the power set of D. Given an input x ∈ X , and a set of features S ⊆ D, the map F (x, S) indicates the label generated by the model when feature subset S is given. For example, several interpretability methods (Yoon et al., 2018; Chen et al., 2018) set F (x, S) = f([0;xS ]), i.e., replace the “removed” coordinates with zero. Other methods (Lundberg et al., 2020; Covert et al., 2020c) remove features by marginalizing them out using their conditional distribution p(XS̄ |XS = xS), where S̄ = D \ S, i.e., F (x, S) = E[f(X)|XS = xs]. Having access to the subset function F , the model behavior stage defines a utility function
  u : P (D) → R (2) quantifying the utility of a subset of features S ⊆ D. For instance, some methods (Covert et al., 2020c; Schwab & Karlen, 2019) calculate the prediction loss between the true label y for an input x, using a loss function ℓ, i.e., u(S) = −ℓ(F (x, S), y). Other methods (Chen et al., 2018; Yoon et al., 2018) compute the expected loss for a given input x using the label’s conditional distribution, i.e., u(S) = −Ep(Y |X=x)[ℓ(F (x, S), Y )]. The utility function can be difficult to interpret due to the exponential number of possible feature subsets. This is addressed by the summary stage as follows. Let U = {u : P (D) → R} be the set of all possible utility functions. An explanation map is a function
  E : U → Rd (3) mapping a utility function to a vector of scores, one per feature in D. These scores succinctly summarize each feature’s value and are the final explanations produced by the removal-based explainability algorithm (F, u,E). For instance, some methods (Zeiler & Fergus, 2014; Petsiuk et al.; Schwab & Karlen, 2019) define E(u)i = u(D)− u(D \ {i}), or E(u)i = u({i})− u(∅) (Guyon & Elisseeff, 2003). Some methods learn E(u) by solving an optimization (Chen et al., 2018; Ribeiro et al., 2016; Yoon et al., 2018). For instance L2X defines E(u) = argmax
  S:|S|=k u(S), for a given k.
  The Shapley Value Explanation Map. In our experiments, we focus on Shapley value explanation maps. Shapley (Shapley, 2016) introduced the Shapley value in coalition/cooperative games as a means to compute “payouts”, i.e., ways to distribute the value of a coalition to its constituent members. Treating features as players in such a coalition, the Shapley value has been used by many research works on explainability to compute feature influence (Datta et al., 2016; Lundberg et al., 2020; Covert et al., 2020b). For instance, Lundberg & Lee (2017) proposed SHAP as a unified measure of feature influence which uses Shapley value for summarization. They also showed that explainers such as LIME , DeepLIFT (Shrikumar et al., 2017), LRP (Bach et al., 2015), QII (Datta et al., 2016) can all be described by SHAP under different utility functions. Formally, given a utility function u, the SHAP explanation map E(u) has coordinates:
  E(u)i = ∑ S⊆D\{i} |S|! (d−|S|−1)! d! (u(S ∪ {i})− u(S)) (4)
  where S ∈ P (D). Direct computation of Eq. (4) is challenging, as the summands grow exponentially as the number of features increases. Štrumbelj & Kononenko (2014) proposed an approximation
  with Monte Carlo sampling, known as Shapley sampling values. Later on, Lundberg & Lee (2017) introduced KernelSHAP and DeepSHAP to compute the shapley values using kernel and neural network approaches respectively, and showed that such methods require fewer evaluations of the original model compared to other methods to obtain similar approximation accuracy.
sections.heading: 4 FROM UNIVARIATE TO MULTI-VARIATE EXPLANATIONS
sections.text: Univariate removal-based explanation methods presented in the previous section share a similar limitation: they do not explain feature interactions in the black box model. Given a univariate explanation map E : U → Rd, we propose a method to extend E to its Bivariate explanation map which discovers feature interactions. Let u ∈ U be the utility function u : P (D) → R. Given this u ∈ U , we define the bivariate explanation E2 : U → Rd×d as a d× d matrix: the ith column of this matrix is E(ui), i.e., the univariate explanation applied to utility function ui, where ui is defined as:
  ui : P (D) → R s.t. ∀S ∈ P (D), ui(S) = { u, if i ∈ S, 0, if i /∈ S. (5)
  This approach can also be directly generalized beyond bivariate to multivariate explanation maps (see App E). Intuitively, the utility function ui is a restriction of u to sets in which when i is an included feature. As a result, E(ui) ∈ Rd determines a feature’s influence conditioned on the presence of feature i. We denote the jth element by E(ui)j = E2(u)ji which represents the importance of feature j conditioned on feature i being present.
  Bivariate Shapley Explanation Map. As a motivating example, let explanation map E : U → Rd be the Shapley map , defined in Eq. (4). Applying the Bivariate explanation extension (5) to the Shapley value we obtain:
  E2(u)ij = ∑ j∈S⊆D\{i} |S|! (d−|S|−1)!
  d! (u(S ∪ {i})− u(S)). (6) We provide the derivation of this formula in App D in the supplement. An important feature of the above bivariate explanation is that it is not symmetric: in general, E2(u)ij ̸= E2(u)ji. In other words, feature i may influence j differently than how feature j influences i. This is in sharp contrast with other bivariate explanation methods, such as, e.g., interaction Shapley (Grabisch & Roubens, 1999; Sundararajan et al., 2020a), that are symmetric. Hence, E2(u) is an asymmetric matrix, that can be represented by a weighted directed graph denoted by G = (VG , EG ,WG), where weights WG(i, j) = E2(u)ji (see App A for a brief review of graph terminology). We call G the directed explanation graph. The directionality of G/asymmetry of E2 has important implications for explainability, which we illustrate next with an example.
  Illustrative Example (Univariate Shapley vs. Bivariate Shapley). In order to motivate the bivariate explanation map, highlight its difference from the univariate Shapley explanation, and illustrate the importance of directionality, we study the directed explanation graph of one sample of “The Large Movie Review Dataset (IMDB) (Maas et al., 2011)”. This is a dataset of movie reviews with labels indicating positive or negative sentiment. We used a Recurrent Neural Network (RNN) as the black box and SHAP as the univariate explainer. Specifically, given a black box model f and a point x, SHAP chooses F (x, S) = E[f(X)|XS = xs], u = F (x, S), and E to be the explanation map using Shapley value. We compute both the univariate Shapley explanation E, as well as the directed explanation graph G/bivariate explanation E2 for the sentence, “The movie is the worst; surprisingly awful”, which is predicted to have negative sentiment. Both explanations are shown in Figure 1. We observe the following differences:
  The influence of word ‘surprisingly’: In Fig. 1(a), we observe that SHAP explanation E identifies ‘awful’, ‘worst’, ‘surprisingly’ as the most influential features. The negative Shapley value for ‘Surprisingly’ indicates that this feature affects prediction strongly in favor of a positive label (opposite of the black box outcome). However, looking at E2, we realize this explanation is in fact misleading. The absence of an edge from ‘worst’ → ‘surprisingly’ suggests that in the presence of ‘worst’ the word ‘surprisingly’ has no influence. Interestingly, the reverse edge does exist; hence, presence of ‘surprisingly’ does not remove the influence of ‘worst’, which still influences the classification outcome. This lack of symmetry is informative, and would not be detected from either a univariate or a bivariate but symmetric explanation.
  ‘awful’ vs ‘worst’: The univariate explanation E suggests that ‘awful’ and ‘worst’ are both influential. However, from the Shapley graph, we observe the absence of an edge from ‘awful’ → ‘worst’ and
  vice versa. This indicates that the presence of either word negates the influence of the other on the classification outcome, making it redundant. Another way to interpret this is that ‘awful’ and ‘worst’ are interchangeable. This is aligned with our understanding that awful and worst have a similar meaning, and is an observation that is not evident from the univariate SHAP E alone.
  Least Influential Features: Words like ‘The’, ‘movie’ have Shapley value zero. Such words are sources in the directed explanation graph G, i.e., have only outgoing edges towards ‘awful’, ‘worst’, and ‘surprisingly’ but no incoming edges at all. This suggests that they are, overall, not influential; more generally, there is a consistency between features that E identifies as non-influential and sources in G.
  Most Influential Features: The support of E (i.e., words ‘awful’, ‘worst’, ‘surprisingly’) represents the words that have the greatest influence. In graph G, we observe that ‘awful’ and ‘worst’ are the sinks of the graph (have only incoming edges, and no outgoing edges); even though ‘surprisingly’ is not a sink, it still has many nodes point into it. This is intuitive: sinks, that have no outgoing edges, indicate that all other words lose their influence when these words are present. ‘Surprisingly’ is important, but there are still other words that negate its influence (namely, ‘awful’ and ‘worst’).
  In summary, the above example illustrates how E2 and G reveal more information than was present in E alone. Although in a more nuanced way, the most and least influential features again stand out; however, in addition to this, features deemed as influential by SHAP can be discovered to be less influential when observed in conjunction with other features; similarly, groups of influential but mutually redundant features may also arise. Both enhance our understanding of how the black box makes predictions, and neither are observable from univariate explanations.
sections.heading: 4.1 ANALYZING THE DIRECTIONAL EXPLANATION GRAPH
sections.text: Motivated by the above observations, we turn our attention to means of systematizing the analysis and interpretation of the Directional Explanation graph. In particular, we identify ways to discover the following notions from the graph G: (a) the most influential features for the black box model, taking their interaction into account, and the extent to which they act as sinks of G; (b) inferring redundancies between the features, by formally defining and detecting Directional Redundancy (e.g. ‘surprisingly’ and ‘awful’) and Mutual Redundancy (e.g. ‘awful’ and ‘worst’); and (c) the transitivity properties of mutually redundant features: if mutual redundancy is transient, it implies the existence of entire equivalence classes of features that are all interchangeable. Our goal in this section is to both state such concepts formally, but also describe algorithms through which these concepts can be used to scrutinize and interpret E2 and G.
  Most Influential Features in Graph G. Most influential features in E2 can be identified as sinks in G. These are easy to identify in polynomial time (as the nodes with no outgoing edges). Nevertheless, a more graduated approach seems warranted, to identify nodes that are ‘almost’ sinks (like ‘surprisingly’ in Fig. 3). This can be accomplished by the use of a random-walk inspired harmonic function on G, like the classic PageRank (Page et al., 1999) or HITS (Kleinberg, 1999).1 These typically correspond to the steady state distribution over a random walk on the graph with random restarts; as such it indeed offers a more graduated version of the notion of “sinkness”, as desired. Variants of this, such as personalized PageRank (Page et al., 1999), can also be used, whereby the random restart is to a node sampled from a predetermined distribution over the vertices of G. Setting this to be, e.g., proportional to the magnitude of the univariate Shapley value E can create an interpolation between the univariate map (that captures univariate influence but not directionality) and E2 (that captured directionality and “sinkness”).
  Directional Redundancy and Mutual Redundancy. In the example stated above, using a bivariate explanation map enabled us to discover which features are redundant with respect to other features. One of these examples was symmetric (e.g. ‘awful’ and ‘worst’) and one was one-sided (e.g. ‘awful’ makes ‘surprisingly’ redundant, but not vice-versa). Motivated by this, we define:
  Definition 4.1. Given i, j ∈ D, i is directionally redundant with respect to feature j if E2(u)ij = 0.
  Directionality arises in Def. 4.1 because E2(u) in general is not symmetric, i.e., E2(u)ij ̸= E2(u)ji. Nevertheless, we can have features i, j that have the same influence on the model (e.g. ‘awful’ and ‘worst’ in the example). We formalize this idea to the E2 explanation through the following definition:
  Definition 4.2. Given i, j ∈ D, features i, j are mutually redundant if E2(u)ij = E2(u)ji = 0.
  Transitivity of Mutually Redundant Features. Given that mutual redundancy is symmetric, it is natural to ask if it is also transitive: if ‘bad’ and ‘awful’ are mutually redundant, and so are ‘awful’ and ‘terrible’, would that imply that ‘bad’ and ‘terrible’ are also mutually redundant? This behavior is natural, and suggest that groups of features may act interchangeably (here, indeed corresponding to variants of ‘bad’). Clearly, identifying such groups is important for the interpretability of the model, as it exhibits an invariant behavior under the exchange of such features. We therefore turn our attention to studying the transitivity properties of mutual redundancy. To do this, we define unweighted directed graph H = (VH, EH), where VH = VG and EH = {(i, j) ∈ EG |WG(i, j) = 0}. Graph H captures all the redundancies between any two pair of features and existence of an edge from i to j (i.e., i → j) represents that feature j is directionally redundant with respect to feature i. We denote H as Redundancy Graph. In practice, we may use the relaxed version of redundancy. Given a redundancy threshold γ, we define Hγ = (VH, EγH) to be a graph where VH = VG and EγH = {(i, j) ∈ EG : |WG(i, j)| ≤ γ}. Intuitively, if the presence of a feature makes the influence of the other less than the threshold γ, we still declare the latter to be redundant. If mutual redundancy is transitive, Graph H would also be transitive; formally: Definition 4.3. An unweighted directed graph H is transitive if (i, j), (j, k) ∈ EH, then (i, k) ∈ EH.
  In other words, a transitive graph comprises a collection of cliques/fully connected graphs, captured by mutual redundancy, along with possible ‘appendages’ (pointing out) that are due to the non-symmetry of directed redundancy. Not every explanation graph G leads to a transitive H. In the following theorem however, we prove that the Shapley explanation map E indeed leads to the transitivity of mutual redundancy and, thereby, the graph H: Theorem 1. For i, j, k ∈ D, assume that maxj∈S⊆N |u(S ∪ {i}) − u(S)| ≤ εj and maxi∈S⊆N |u(S ∪ {k}) − u(S)| ≤ εi. Then, the following inequalities hold: |E2(u)ij | ≤ d!2 εj , |E2(u)ki| ≤ !2εi, and |E 2(u)kj | ≤ d!2 (2εj + εi).
  In short, Theorem 1 states that for a given path i → j → k the summation of upper bounds for edges i → j and j → k can be used to upper bound the weight of the edge i → k. An immediate implication of this “triangle-inequality”-like theorem is that if all ϵ = 0, as is the case in directed redundancy, the weight of edge i → k must also be zero. In other words: Corollary 1.1. Graph H for Shapley explanation map with a monotone utility function is transitive.
  1In the context of HITS, “almost” sources and sinks correspond to “hubs” and “authorities”, respectively.
  Most importantly, Theorem 1 proves something stronger than that. In fact, it allows for ‘almost transitivity’ of graph Hγ in the case of approximate Shapley value computation: even if we set the threshold γ to a non-zero value, short paths (of length γ/ϵ) will also be guaranteed to be transitive. The proofs for Thm. 1 and Corollary 1.1 are provided in the supplement.
  Sources and Sinks in the Redundancy Graph. Beyond identifying classes of mutually redundant features, the redundancy graph H can also be used to identify (classes of) features under which all remaining features become redundant. This can be accomplished in the following fashion. First, the strongly connected components/classes of mutually redundant features need to be discovered. As a consequence of Thm. 1, such strongly connected components will be cliques if the exact Shapley explanation map is used, or almost cliques if the threshold γ is non-zero. Collapsing these connected components we obtain a DAG, also known as the quotient graph (see App A). The sources of this quotient graph (which may correspond to entire classes) correspond to feature classes that make all other features redundant (possibly through transitivity). Note the distinction between sinks in G and sources in H, that may be a different set of nodes, and capture a different kind of importance. Again, rather than determining importance simply from the fact that a node in H is a source, a more graduated approach, using a harmonic function of nodes like Pagerank (over H) could be used.
sections.heading: 5 EXPERIMENTS
sections.text: In this section, we investigate the ability of Bivariate Shapley for discovering (1) mutual redundancy, (2) directional redundancy, and (3) influential features, from black-box models. Fully evaluating shapley values is computationally expensive; we implement Bivariate Shapley using two different Shapley approximation methods for comparison, Shapley Sampling (BivShap-S) and KernelSHAP (BivShap-K). The algorithms are outlined in App F.1.1. The KernelSHAP approximation significantly reduces computational time (tbl. 1) at the cost of slightly reduced Post-hoc accuracy results (tbl. 3). In our method comparisons, We take 500 test samples from each dataset (less if the test set is smaller than 500) and generate their respective G and H graphs. We select γ = 10−5 for the threshold in converting G → H, which generally corresponds to 50% average graph density across the datasets (see App. F.2.4 for details). All experiments are performed on an internal cluster with Intel Xeon Gold 6132 CPUs and Nvidia Tesla V100 GPUs. All source code will be made publicly available.
  Data. We evaluate our methods on a 1077 RNAseq COPDGene data (Regan et al., 2010), CIFAR10 (Krizhevsky, 2009) and MNIST (LeCun & Cortes, 2010) image data, IMDB text data, and on three tabular UCI datasets (Drug, Divorse, and Census) (Dua & Graff, 2017). We train separate black-box models for each dataset. Image and text datasets, as well as COPDGene and Divorce use neural network architectures; Census and Divorce use tree-based models (XGBoost (Chen & Guestrin, 2016) and Random Forest). Full dataset and model details can be found in App. F.1.3.
  Competing Methods. We compare our method against both univariate and bivariate, instance-wise, black-box explanation methods. Univariate methods Shapley sampling values (Sh-Sam), KernelSHAP (kSHAP), and L2X are used to identify the top important features, either through a feature ranking or by choosing a subset of features. Second-order methods Shapley Interaction Index (Sh-Int) (Owen, 1972), Shapley-Taylor Index (Sh-Tay) (Sundararajan et al., 2020b), and Shapley Excess (Sh-Exc) (Shoham & Leyton-Brown, 2008) capture symmetric interactions, for which we apply the same PageRank algorithm as Bivariate Shapley to derive a feature ranking. We also compare to a GNN explanation method GNNExplainer (GNNExp). Further details regarding control parameter settings of these competing methods and licensing information are provided in App F.1.
  (1) Mutual Redundancy Evaluation.
  We evaluate the validity of mutually redundant features by evaluating the change in model accuracy after masking redundant features, with post-hoc accuracy results shown in Figure 2. We identify such features as groups of strongly connected nodes in graph H, which we find using a depth-first search on H using Tarjan’s algorithm (Tarjan, 1972). After finding the mutually redundant groups, we test their exchangeability by randomly selecting subsets of features within the group to mask. We evaluate post-hoc accuracy at different levels of masking. Masking all but one feature results in the quotient graph S, which is represented by each dataset’s marker in Figure 2. Note that these groups can be discovered by other second-order methods by similarly interpreting the resulting feature interactions as an adjacency matrix; we include the results for applying the same algorithm to Sh-Int, Sh-Tay and Sh-Exc. We observe that masking an arbitrary number of mutually redundant features has minimal
  Time Complexity: Seconds per Sample Dataset #Features BivShap-S BivShap-K Sh-Int Sh-Tay Sh-Exc COPD 1077 5942 36 2877 112900 838200
  CIFAR10 255 218 2.5 101 2819 6267 MNIST 196 116 1.5 48 1194 2350 IMDB ≤400 207 1.9 160 1279 1796 Census 12 2.7 0.20 2.6 11.6 5.3 Divorce 54 18.2 0.34 6.5 63.2 93.3
  Drug 6 2.3 0.07 1.21 10.1 0.96
  Table 1: Time comparisons of the methods. Results are calculated on the time to produce the interaction matrix (including all features) for a single sample, as measured by seconds per sample.
  PH-Accy % Feat Masked Dataset Sink
  Masked Source Masked Sink Masked Source Masked
  COPD 99.5 62.7 1.5 98.5 CIFAR10 94.6 15.0 6.2 93.8 MNIST 100.0 13.4 77.7 22.3 IMDB 100.0 54.0 3.5 96.5 Census 100.0 82.0 23.8 76.2 Divorce 100.0 51.5 22.2 77.8
  Drug 100.0 48.5 43.5 56.5
  Table 2: Posthoc-accy of BivShap-S after masking H-source nodes, representing features with minimal redundancies, and H-sink nodes, representing directionally redundant features.
  impact to accuracy under the BivShap method. In contrast, the groups identified by the other methods do not share the same level of feature interchangeability. In terms of finding mutual redundancy, this suggests that incorporating directionality is critical in identifying mutually redundant features; undirected methods do not capture the full context of feature interactions. We also note that no mutually redundant features were found by GNNExplainer, which indicates that the edges of its explanation graph are unable to capture feature interchangeability.
  (2) Directional Redundancy Evaluation. We validate directional redundancy using post-hoc accuracy as shown in tbl. 2. Additional results for BivShap-K are shown in App. F.2.3. We identify directionally redundant features as H-sinks and H-sources, which we identify using PageRank. We collapse the strongly connected components in graph H to its quotient graph S , then apply PageRank to each connected graph in S. The maximum and minimum ranked nodes in each connected graph correspond to the sinks and sources in S , respectively. The condensed sinks and sources are expanded to form H-sinks and H-sources. We then evaluate the relevance of the identified nodes using posthoc accuracy of masked samples. To validate our claims of directionality, we compare the results of masking H-source nodes and H-sink nodes, where H-sink nodes represent the directionally redundant features. We observe that masking sinks have little effect on accuracy, suggesting that these features contain redundant information given the unmasked source nodes. In contrast, masking source nodes and keeping sinks results in large decreases in accuracy, indicating that prediction-relevant information is lost during masking.
  (3) Influential Feature Evaluation. While mutual and directional redundancy can be investigated individually using graph H, we can combine both concepts in a continuous ranking of features based on the steady-state distribution of a random walk on graph G. We add a small ϵ ≈ 0 value to the adjacency matrix of G to ensure that all nodes are connected, then directly apply PageRank. The resulting feature scores are ranked, with high-scoring features representing high importance. We observe the experimental results in Figure 3. BivShap-S consistently performs the best across data sets, including against BivShap-K, which suggests some small accuracy tradeoff for the faster approximation. Note that Bivariate Shapley does not explicitly utilize feature importance, but rather each feature’s steady-state distribution. However we can also incorporate feature importance
  information, defined by univariate Shapley, through Personalized PageRank. Personalization increases the steady state probabilities for important features.
  Additional Illustrative Examples from MNIST and CIFAR10 Datasets
  In Figure 4 we investigate examples from MNIST and CIFAR10 for illustrative purposes. For the image examples, we see that images with homogenous background pixels show larger amounts of redundancy as identified using graph H in the middle row. This redundancy is also evidenced in the directional redundancy ranking in the bottom row, where the mutually redundant pixels are shown to have similar PageRank scores. We observe that pixels with higher scores make sense and correspond to pixels where the foreground object lies in the image and at key areas of the object.
  Time Comparisons and Additional Results. Table 1 reports the time in seconds per sample to calculate feature interactions. Note that BivShap-K performs the best among Bivariate methods. Full details of timing setup is listed in App. F.2.5. In the appendix we also provide additional evaluation results based on AUC (App. F.2.1) as well as a Gene Ontology enrichment analysis of the feature rankings identified in the COPD dataset (App. F.2.6).
sections.heading: 6 CONCLUSION
sections.text: We extend the removal-based explanation to bivariate explanation that captures asymmetrical feature interactions per sample, which we represent as a directed graph. Using our formulation, we define two concepts of redundancy between features, denoted as mutual redundancy and directional redundancy. Our theoretical contribution leads to a systematic approach for detecting such redundancies through finding the cliques and sources in graph H. Experiments show the benefit of capturing directional redundancies and the superiority of our method against competing methods.