Explanations of Black-Box Models based on Directional Feature Interactions
Authors: Aria Masoomi
Davin Hill
Zhonghui Xu
Craig P Hersh
Edwin K. Silverman
Peter J. Castaldi
Stratis Ioannidis
Jennifer Dy
Venue: ICLR 2022 Spotlight (2022)
Keywords: Explainability
Shapley values
Interpretability
Directional interaction
feature interaction

Abstract: 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.  

Published as a conference paper at ICLR 2022
EXPLANATIONS OF BLACK-BOX MODELS BASED ON DIRECTIONAL FEATURE INTERACTIONS
Aria Masoomi'
Davin Hill"
Zhonghui Xu²
Craig P. Hersh
Edwin K. Silverman" 2
Peter J. Castaldi
Stratis Ioannidis
1
Jennifer Dy
ABSTRACT
As machine learning algorithms are deployed ubiquitously to a variety of domains, it is imperative make these often black-box models transparent. Several recent works explain black-box models by capturing the most influential features for pre- diction per instance; such explanation methods are univariate, as they characterize importance per feature. We extend univariate explanation to higher-order, this enhances explainability, as bivariate methods can capture feature interactions 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 identify the most influential features. We apply our bivariate method on Shapley value explanations, and experimentally demonstrate the ability of directional explanations discover feature interactions. We show the superiority of our method against state-of satee-of-the- the--art on 11,AR10, IMDB, Census, Divorce, Drug, and gene data.
INTRODUCTION
The ability to interpret and understand the reasoning behind black box decision-making increases user trust; it provides insights into how model is working and, consequence, how model can be improved. This has led to a large body of work on the development explanation methods (Ribeiro al., 2016; Chen al., 2018: 8; Yoon al., 2018; Lundberg & Lee, 2017) applied to black-box models. Such methods aim to explain black-box behavior by understanding how individual features influence prediction outcomes. Recently, Covert al. (2020a) proposed unifying mathematical framework capturing a broad array of explainability techniques, termed cemooval-based Explanation methods. Nevertheless, the overwhelming majority of explainability methods have significant drawback: they 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 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 (see Fig. 1), and argue of the importance of developing black-box explanations 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- explanation to a bivariate explanation model that capture asymmetrical feature interactions, represented 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).
explanate
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
Northeastern University, Department Electrical and Computer Engineering, Boston, MA. USA. Imasoomi a @enortheastee edu, (dhill, ioannidis, jay (ecce neu.eeuu BBrigham and Women's Hospital, Channing Division of Network Medicine, Boston, MA, USA. (rezxu, craig waaig.aa hersh, reeks, repja] @channi hh.

---

Published as a conference paper at ICLR 2022
mutually redundant features, i.e., features that are interchangeable. These two concepts cannot be captured by either univariate or 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 ex- pression 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.
RELATED WORK
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 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 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 single framework; we present this in detail in Sec. 3.
However, all of these methods only capture the univariate influence 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; Jamizek et al., 2021; Zhang et al., 2021: Tsang et al., 2018: 2020). Tsang al. (2017) proposed a framework to detect statistical interactions in a foed-forward neural network by directly interpreting the weights of the model. Cui et al. (2020) 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 Shapley interaction value to explore the interaction between features rather than feature influence. Lundberg al. (2018a) and Sundararajan 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 different groups based on the similarity of their contribution the prediction task. These methods assume 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- model has a GNN architecture: i.c. 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-ban
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 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 al. (2021a) a) 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 casual relationships; in contrast, our method learns the asymmetrical interaction between features rather than causal dependencies.
3 BACKGROUND
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 an individual sample basis. Typically, this is done by attributing the
2

---

Published as a conference paper at ICLR 2022
prediction to sample features that were most influential on the model's output. The latter is discovered through some form of imput perturbation (Lundberg & Lee. 2017: Zeiler & Fergus, 2014). Covert et al. (2020a) proposed a framework, unifying a variety of different explainability methods. As we generalize this framework, we formally describe it below.
Univariate Removal-Based Explanations. The unifying framework of Covert et al. identifies three stages in a removal- based explanation method. The first, feature- 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 function f f: X + Y mapping input features x E X' C R.d to labels y E y. Let D = [1,.... ..l,...,d3 be the feature space coordinates. Given an input z E X and subset of features S C D, let zs = [ri])es E Rd be the projection of to the features in S. In the local interpretability setting, we are given a black-box model f. an input X and (in some methods) the additional ground truth label y E V. 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,
where P(D) = 2D is the power set of D. Given an input x E X, and a set of features C D, the map Fax, 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 Fxx, S] = f(00;=s)) i.e. replace the "removed" coordinates with zero. Other methods (Lundberg et al., 2020; Covert et al., 2020b) remove fcatures by marginalizing them out using their conditional distribution p(Xg Xx J, where $ D S.i.e F(x, S) [[f(X) w.).
Having access to the subset function F, the model behavior stage defines a utility function
P(D) + R
(2)
quantifying the utility of a subset of features S C D. For instance, some methods (Covert et al., 2020b; 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((z, 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., Y)..
(())= = ((F
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 lf = P(D) + R) be the set of all possible utility functions. An explanation map is a function
E : U Rd
mapping utility function to a vector of scores, one per feature in D. These scores summarize each feature's 'ss value and are the final explanations produced by the removal-based explainability algorithm (F, u, F)). For instance, some methods (Zeiler & Fergus, 2014; Petsiuk et al., 2018; Schwab Karlen, 2019) define E(u); = u(D)- u(D) \ {t}), or E(u); u( {i)) u00) (Guyon & Elisseeff, 2003). Some methods learn E'(u) by solving an optimization problem (Chen et al., 2018; Ribeiro et al., 2016; Yoon et al., 2018). For example, L2X defines E(u)= argmax u(S) for given k.
5:|5|=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 coalition 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 unified measure of feature influence which uses Shapley value for summarization. They also showed that explainers such as LIME. DecpLIFT (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); = Escp(() || (d-1s)-11)) 1]!
(u (i)) u(S)),
(4)
3

---

Published as a conference paper at ICLR 2022
where S E P(D). Direct computation of Eq. (4) is challenging. the summands grow exponentially as the number of features increases. Strumbelj & Kononenko (2014) proposed an approximation with Monte Carlo sampling, known as Shapley sampling values. Lundherg & Lee (2017) introduced KemelSSHA and DeepSHAP to compute the shapley values using kernel and neural network ap- proaches respectively, and showed that such methods require fewer evaluations of the original model to obtain similar approximation accuracy as prior methods.
4 FROM UNIVARIATE TO MULTI- VARIATE EXPLANATIONS
Univariate removal-based explanation methods presented in the previous section share similar limitation: they do not explain feature interactions in the black box model. Given a univariate explanation map E 1 - R we propose a method which discovers feature interactions. Let u E 24 be the utility function u P(D) - R. Given this u E U, we define the bivariate explanation F.2 :4 -> Rdxd as d x matrix: the 7th column of this matrix is Fl(us), i.e., the univariate explanation applied to utility function ug. where is defined as:
extend to its Bivariate explanation map
u4 : P(D) - IR s.t. AS E P(D), m.(S) = (u(S), i 00 if
(5)
Intuitively, the utility function u, is a restriction of u to sets in which when i is an included feature. As result, E(u,) E It determines a feature's 's influence conditioned on the presence of feature i. I We denote the 5th element by E(u,), = (u))) which represents the importance of feature conditioned on feature i being present.
Bivariate Shapley Explanation Map. As a motivating example, let explanation map E : 4 - Rd be the Shapley map, defined in Eq. (4). Applying the Bivariate explanation extension (5) to the Shapley value we obtain:
(u) - -E |SII (d-1s)-10) ( (i)) u(S)).
(6)
We provide the derivation of this formula in App. E in the supplement. An important feature of the above bivariate explanation that it is not symmetric: in general, ("()) # (r(u)). In other words, feature i may influence differently than how feature influences i. This is in sharp contrast with other bivariate explanation methods, such as, c.g., interaction Shapley (Grabisch & Roubens, 1999; Sundararajan al., 2020a), that are symmetric. Hence, E² E²(u) is asymmetric matrix, that can be represented by a weighted directed graph denoted by g = (Vg. Eg. Wg), where weights Wi(i.j) (u) (see App. B for a brief review of graph terminology). We call the directed explanation graph. The directionality of G/asymmetry of E² 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 negative sentiment. We used a Recurrent Neural Network (RNN) the black box and SHAP as the univariate explainer. Specifically, given a black box model f and a point x, SHAP chooses F(x, (X X = 22]. u F(x, S), and E 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 F² for the sentence, "The movie is the worst; surprisingly awful", which is predicted to have negative sentiment. Both explanations are shown in Fig. 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 E?, we realize this explanation is in fact mislcading. The absence of 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 surprrsiingl"" does not remove the influence of 'worst', which still influences the classification
"This approach can also he directly generalized beyond bivariate multivariate explanations (see App. F).
4

---

Published as a conference paper at ICLR 2022
Input
Prediction
The movie was the worst; surprisingly awful
Black Box
Negative Sentiment
(a) Univariate
(b) Directed Explanation Graph g
Shapley
Mutual Redundancy
Directional Redundancy
The
0.0
The
movie
was
the
Worst & Awful are Mutually Redundant
Awful makes (The, movie, was, surprisingly) redundant
movie
0.0
Was
0.0
out
the
0.0
HUrprisingl ny
Top Influential Features
worst
0.3
0.0
0:15
2. Awful
surprisinglv
Awful
Worst
3. Surprisingly
awful
0.3
Figure I: a) Univariate Shapley value. The values suggest that 'surprisingly', 'worst', 'awful' are the most influential features, however it does not explain feature interactions b) Using Shapley explanation map E, plot the Directed Explanation graph & using method. An edge i - represents the conditional influence of word when word is present. We can then use the properties of Graph 9 to derive notions of Mutual and Directional Redundancy, well Influential Features.
outcome. This lack of symmetry informative, and would not be detected from either a univariate or bivariate but symmetric explanation.
'awful' vs 'worst': The univariate explanation suggests that 'awful' and 'worst' are both influential. However, from the Shapley graph, we observe the absence of 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 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 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, over- all, not influential:; more generally, there consistency between features that E identifies as non-influential and sources in G.
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 sink, it still has many edges pointing into it. This is intuitive: sinks, that have no outgoing edges, indicate that all other words lose their influence when these words are present. 'Surrpisingly"' is important, but there are still other words that negate its influence (namely, 'awful" and 'worst').
Most Influential Features:
In summary, the above example illustrates how E² and G reveal more information than was present in E alone. Although in more nuanced way, the most and least influential features again stand out; however, in addition to this, features deemed as influential by SHAP can 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 how the black box makes predictions, and neither observable from univariate explanations.
4.1 ANALYZING THE DIRECTIONAL EXPLANATION GRAPH
Motivated by the above observations, we turn our attention 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 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 transitive, it implies the existence of entire equivalence classes of features that all interchangeable. Our goal in this section is to
5

---

Published as a conference paper at ICLR 2022
both state such concepts formally, but also describe algorithms through which these concepts can be used to scrutinize and interpret E² and G.
Most Influential Features in Graph G. Most influential features in E can be identified sinks in G. These are casy to identify in polynomial time (as 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 through a random-walk inspired harmonic function on G. like the classic PageRank (Page et al., 1999) or HITS (Kleinberg, 1999).² These correspond to the steady state distribution over a random walk on the graph with random restarts; as such it indeed offers more graduated version of the notion of "sinkness", as desired. Variants, such as personalized PageRank (Page et al., 1999), can also be used, whereby the random restart is to node sampled from a predetermined distribution over the vertices of G. Setting this to be proportional to the magnitude of the univariate Shapley value E interpolates between the univariate map (that captures univariate influence but not directionality) and E (that captures 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 E D, i is directionally redundant with respect to feature j if E2((),) = O.
Directionality arises in Def. 4.1 because [²) in general is not symmetric, i.c., L2((),y & (2) Nevertheless, we can have features j that have the same influence on the model (c.g. 'awful' and 'worst" in the example). We formalize this idea to the E explanation through the following definition:
Definition 4.2. Given j.j E D, features i, are mutually redundant if (u)s = (u) = 0.
Transitivity of Mutually Redundant Features. Given that mutual redundancy is symmetric, it is natural ask if 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 suggests that groups of features may act interchangeably (here, corresponding to variants of "bad"). ). Identifying such groups is important for interpreting the model, as it exhibits an invariant behavior under the exchange of such features. We thus turn our attention to studying the transitivity properties of mutual redundancy. To do this, we define unweighted directed graph H = (V2, Ex), where VR= = Vg and Σн = {i. j) E Egl Wi between any two features: edge from to j (i.e., i j) indicates that feature j is directionally redundant with respect to feature i. We call H the Redundancy Graph. In practice, we may use the relaxed version of redundancy. Given redundancy threshold y, we define H4 (Vn, E32) to be a graph where VH= = VG and EG, = [i.j) E Eg : (i) S 7) Intuitively. if the presence of feature makes the influence of the other less than the threshold 7, we still declare the latter to be redundant. If mutual redundancy is transitive, Graph H is also transitive; formally:
j) = 0}. Graph H. captures the redundancies
Definition 4.3, An unweighted directed graph H is transitive if (i.j), (1. k) E Ex, then ki, E F---
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 the non-symmetry of directed redundancy. Not every explanation graph & 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 k E D, assume that maxjesçN Iu(S U (i) u(S) S Ej and maxessNN [u(S U [k}) u(S) S Es. Then, the following inequalities hold: (E?( S di
E
[E* < fe., and [E*
(22, + +.).
In short, Theorem 1 states that for a given path i j + k the summation of upper bounds for edges - and j + k can be used to upper bound the weight of the edge + k. An immediate implication of this "triangle-inequality" -like theorem is that if all e 0, as is the case in directed redundancy, the weight of edge i > must also be zero. In other words:
Corollary 1.1. Graph H for Shapley explanation map with a monotone utility function is transitive.
In the context of HITS, "almost" sources and sinks correspond to "hubs" and "authoritics", respectively.

---

Published as a conference paper at ICLR 2022
Most importantly, Theorem 1 proves something stronger than that. In fact, it allows for "almost transitivity" of graph 7 in the case of approximate Shapley value computation: even if we set the threshold to non-zero value, short paths (of length r/e) 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 7 is non-zero. Collapsing these connected components we obtain DAG, also known as the quotient graph (see App B). 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 different set of nodes, and capture 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 harmonic function of nodes like Pagerank (over H. could be used.
5 EXPERIMENTS
In this section, we investigate the ability of Bivariate Shapley for discovering (a) mutual redundancy, (b) directional redundancy, and (c) influential features, from black- models. Fully evaluating Shapley values is computationally expensive; Shapley approximation methods for comparison, Shapley Sampling (BivShap-S) and KerneISHAP (BivShap-K). The algorithms are outlined in App. G.I.I. The KernelSHAP approximation signifi- cantly 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 y = 10 for the threshold in converting 9 to H. which generally corresponds to 50% average graph density across the datasets (see App. G.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 is publicly available."
implement Bivariate Shapley using two different
Data. We evaluate our methods on COPDGene (Regan et al., 2010), CIFARIO (Krizhevsky, 2009) and MNIST (LeCun & Cortes, 2010) image data, IMDB text data, and on three tabular UCI datasets (Drug, Divorce, and Census) (Dua & Graff, 2017). We train separate black-box models for each dataset. MNIST, CIFARIO, COPDGene, and Divorce use neural network architectures; Census and Drug use tree-based models (XGBoost (Chen & Guestrin, 2016) and Random Forest). Full dataset and model details can be found in App. G.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 feature ranking or by choosing a subset of features. Second-order methods Shapley Interaction Index (Sh-Int) (Owen, 1972), Shapley-Tayloo Index (Sh-Tay) (Sundararajan et al., 2020b), and Shapley Excess (Sh-Exe) (Shoham & Leyton- Leyton-Brown, 2008) capture symmetric interactions, on 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 are provided in App. G.I.
(a) Mutual Redundancy Evaluation.
We evaluate the validity of mutually redundant features through the change in model accuracy after masking redundant features, with post-hoe accuracy results shown in Fig. 2. We identify such features as groups of strongly connected nodes in graph H. which we find using depth-first search on H using Tarjan's 's algorithm (Tarjan, 1972). After finding the mutually redundant groups, we test their exchangeability by randomly selecting subsets of features within the group 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 Fig. 2. Note that these groups can be discovered by other second-orde -oddr methods by similarly interpreting the resulting feature interactions as adjacency matrix; we include the results for applying the same algorithm to Sh-Int, Sh-Tay and
httpp:://gi wtw...com/dvviiii. /arvariiiiiaaaeeeeaeea iatiaarttteepeee
7

---

Published as a conference paper at ICLR 2022
COPD
IMDS
CIFAR10
MNIST
Divorce
Drug
Census
BivShap-S
BivShap-K
Sh-Int
Sh-Tay
Sh-Exc
Post-Hoo Accuracy 1%0
100
0
40 96.
60 Foatures Masked
0
20 Features Masked
60
60 56 Features Masked
20
80
20
40
80
20 40
60
80
%6 Features Masiond
%6 Foatures Masked
Figure 2: Post-hoc accuracy evaluated on Mutual Redundancy masking derived from graph H. Strongly connected nodes in H are randomly masked with increasing mask sizes until a single node remains, represented by the final marker for each dataset. Note that we cannot run Sh-Tay and Sh-Exc on COPD due their computational issues with large numbers of features.
Post hoc Aczy
%. Feat Masked
Time Complexity: Seconds per Sample
Dataset
Ht-Sink Masked
H-Source Masked
H--Sink
H-Source
Dataset
#Features
BivShap-S
SivShap-K K
Si-Int
Sh-
Sl--xxc
Masked
Masked
COPD
1077
5942
112900
838200
COPD
99.5
62.7
1.5
98.5
CI
255
218
2.5
2819
CIFARIO
94.6
15.0
6.2
93.8
MNIST
196
116
1.5
1194
2350
MNIST
100.0
13.4
77.7
22.3
IMDB
$400
207
1.9
160
1279
1796
IMDB
100.0
54.0
3,5
96.5
Census
12
2.7
0.20
2,6
11.6
5.3
Census
100.0
82.0
23.8
76.2
Divorce
54
18.2
0.34
6,5
63.2
93.3
Divoree
100.0
51.5
22.2
77.8
Drug
6
2.3
0.07
1.21
10.1
0.96
Drig
100.0
48.5
43.5
56.5
Table 1: Execution time comparison. Results are calculated on the time to produce the interaction matrix (including all features) for a single sample, as measured by seconds per sample.
Table 2: Post-hoc accuracy of BivShap-S after masking H-source nodes, representing features with minimal redundancies, and H-sink nodes, representing directionally redundant features.
Sh-Exc. We observe that masking arbitrary number of mutually redundant features has minimal 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.
(b) Directional Redundancy Evaluation. We validate directional redundancy using post-hoc accuracy as shown in Tbl. Additional results for BivShap-K are shown in App. G.2.3. We identify directionally redundant features as H-sink nodes, 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--surces. We then evaluate the relevance of the identified nodes using post-hoc 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 in Tbl. 2 that masking sinks has little effect on accuracy, suggesting that these features contain redundant information given the unmasked source nodes. In contrast, masking H-source nodes and keeping sinks results in large decreases in accuracy, indicating that prediction-relevant information lost during masking.
(c) 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 2 0 value to the adjacency matrix of & 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 Fig. 3. BiwShap-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 ss steady-state distribution. However, we can also incorporate feature importance
8

---

Published as a conference paper at ICLR 2022
Bivariate Methods
Univariate
COPD
CIFAR10
MNIST
Sh-int
Sh Sam
90
Sh-Tay
KSHAP
Post-hoc accuracy (%)
80
Shy Exc
L2X
BivShap
70
BlyShap-K
GNN
Methods
20
100
60
80
100
40
60
80
100
GNNEXp
Divorce
Drug
90
70
80
100
60 80
100
40
60
80
100
20
40
60
100
% features masked
Figure 3: Comparison of explanation methods feature removal task. Methods are evaluated on their ability to maintain post-hoe accy while removing the least influential features. We apply PageRank to graph other explanation methods by iteratively masking the lowest ranked features. Note that we cannot run Sh-Tay and Sh-Exc on COPD due their computational issues with large numbers of features.
derive univariate ranking based feature redundancy. We compare to
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 Fig. 4, we investigate exam- ples from MNIST and CIFAR10 for illustrative purposes. We see that images with homogenous background pixels show larger amounts of redundancy as identi- fied using graph H in the middle row. This redundancy also ev- idenced in the directional redun- dancy 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 pixels where the foreground ob- ject lies the image and key areas of the object.
automobile
Original Sample
3
3
Mutual Redundancy
Directional Redundancy
Figure 4: We explore samples from MNIST and CIFARIO. Middle row: we identify Mutually Redundant features from graph H. indicated by the white pixels in each image. Bottom row: We apply redundancy ranking graph & and show heatmap of PageRank scores; important nodes have higher PageRank scores.
Time Comparisons and Additional Results. Tbl. I 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. G.2.5. In the appendix we also provide additional evaluation results based AUC (App. G.2.1) well Gene Ontology enrichment analysis of the feature rankings identified in the COPD dataset (App. G.2.6).
CONCLUSION
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 mutual redundancy and directional redundancy. Our theoretical contribution leads to 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. We discuss societal impacts in App. A.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
The work described was supported in part by Award Numbers U01 HL089897, U0I HL089856, RO1 H1.24233, RO1 HL147326 and 2132HL007427-41 from the National Heart, Lung, and Blood Institute, the FDA Center for Tobacco Products (CTP).
REFERENCES
R. Achanta, A. Shaji, K. Smith, A. Lucchi, Fua, and Sabine Süsstrunk. SLIC Superpixels Compared to State-of-the-Ar Superpixel Methods, IEEE Transactions Pattern Analysis and Machine Intelligence, 24(11):224--2282, November 2012. ISSN 0162-8828, 2160-9292. doi: 10.1 N0.1009/PAAM..21222220
Yoav Armson, Yehuda Shoenfeld, and Howard Amital. Effects of tobacco smoke on immunity, inflammation and autoimmunity. Journal of autoimmumity, 34(3):1258-J265 2010.
Alejandro Barredo Arrieta, Natalia Díaz-Rodríguezz Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador García, Sergio Gil-López, Daniel Molina, Richard Benjamins, et al. Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai. Information Fusion, 58:82-115 115, 2020.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, -labr-Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e01301 30140, 2015.
Jørgen Bang-Jensen and Gregory Z Gutin. Digraphs: theory, algorithms and applications. Springer Science & Business Media, 2008
Roderick Bloem, Harold N Gabow, and Fabio Somenzi. An algorithm for strongly connected component analysis in log n symbolic steps. Formal Methods in System Design, 28(1):37-56, 2006.
Thomas Bonald, Nathan de Lara, Quentin Lutz, and Bertrand Charpentier. Scikit-network: Graph analysis python. Journal of Machine Learning Research, 21(185):1-6, 2020, URL http: //jml r. org. http:/apers//ve /vaeess/22111 20 412 html.
Howard D Bondell and Brian Reich. Simultaneous regression shrinkage, variable selection, and supervised clustering of predictors with oscar. Biometrics, 64(1):115-12)) 2008.
Rich Caruana, Yin Lou, Johannes Gehrke, Paul Koch, Mare Sturm, and Noemie Elhadad. Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1721-1730, 2015.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning explain: information-theorede perspective on model interpretation. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 883-892. PMLR, 10-15 Jul 2018. URL http://proceediin
mmlr, press / htt////0///////// j. html.
Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp- 785-794, August 2016. doi: 10. 10.1145/2939672.293977
Kyunghyun Cho, B van Merrienboer, Caglar Gulcehre, F Bougares, H Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In Conference on Empirical Methods in Natural Lunguage Processing (EMNLP 2014), 2014.
Smita Chormunge and Sudarson Jena. Correlation based feature selection with clustering for high dimensional data. Journal of Electrical Systems and Information Technology, 5(3):542-549 2018.
10

---

Published as a conference paper at ICLR 2022
Ian Covert, Scott Lundberg, and Su-In Lee. Feature removal is unifying principle for model explanation methods. CoRR, abs/2011.03623 2020a. URL https://aaxxiiiii org/ abs/
Ian Covert, Scott M Lundberg, and Su-In Lee. Understanding global feature contributions with additive importance measures. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17212-17223. Cur- ran Associates, Inc., 2020b. URL https: http:: https:::s/pppcceedinggoo neurips. cc hctpppppe/220/////// pdff.
File/c7bf0br a 665eb33ee2c72ccffffff46555
Tianyu Cui, Pekka Marttinen, and Samuel Kaski. Learning global pairwise interactions with bayesian neural networks. In Giuseppe De Giacomo, Alejandro Catala, Bistra Dilkina, Michela Milano, Senen Barro, Alberto Bugarin, and Jerome Lang (eds.), ECAI 2020 24th European Conference on Artificial Intelligence, including 10th Conference
Prestigious Applications of Artificial Intelligence, PAIS 2020 Proceedings, Frontiers Artificial Intelligence and Applications, pp- 1087-1094, United States, August 2020. IOS Press. doi: 10.3233/FAIA200205.
Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems. In 2016 IEEE symposium on security and privacy (SP), pp. 598-617. IEEE, 2016.
Finale Doshi- Velez and Been Kim. Towards rigorous science of interpretable machine learning. arXiv preprint arXiv: 1702.067000860 2017.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive. ics. uci. edu/ml. mml.
Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. arXiv preprint arXiv:2104. 10482, 2021.
Razich Faghihpiraycsh, Sebastian Ruf, Marianna La Rocca, Rachael Gameer, Paul Vespa, Deniz Erdoğmuş, and Dominique Dunean. Automatic detection of eeg epileptiform abnormalities in traumatic brain injury using deep learning. In 2021 43rd Anmual International Conference of the IEEE Engineering in Medicine Biology Society (EMBC), pp. 302-305, 2021. doi: 10. 10.1109/
EMBC46164.2022 9630242.
Elaine Fehrman, Awaz K. Muhammad, Evgeny M. Mirkes, Vincent Egan, and Alexander N. Gorban. The five factor model of personality and evaluation of drug consumption risk. Francesco Palumbo, Angela Montanari, and Maurizio Vichi (eds.), Data Science, pp. 231-242, Cham, 2017. Springer International Publishing. ISBN 978-3-319-5572366
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric, 2019. URL http:ttp:///aaaeeee //rxivv...iivvv//aa/iii wwwp//ggg//////////.///e.e/ abs/ 1903. 02428. cite arxiv: 190v.199...2228.
Christopher Frye, Colin Rowat, and Ilya Feige. Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 1229-1239, Curran Associates, Inc., 2020. URL https: //tp::::////eeeee/ee http://pooeeeeenceee/eeeee neuriiss cc/ paper/2020/E8 falo/fillle/ filffllllllii 0dwlee//d7000e 7044 3dd.aaaaaaa222aa3aaaamaaa fbdd 9e bbde pdf.
Michel Grabisch and Mare Roubens. An axiomatic approach to the concept of interaction among
players in cooperative games. International Journal of game theory, 28(4):547-565, 1999.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM computing surveys (CSUR), 51(5):1-42,2015 2018.
Isabelle Guyon and André Flisseeff, An introduction to variable and feature selection. Journal of machine learning research, 3(Mar): 157-1182, 2003.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. doi: 10. 1.110//VPPR.2066.99

---

Published as a conference paper at ICLR 2022
Joseph D Janizek, Pascal Sturmfels, and Su-In Lee. Explaining explanations: Axiomatic feature interactions for deep networks. Journal of Machine Learning Research, 22(104):1-54, 2021.
Been Kim, Elena Glassman, Brittney Johnson, and Julie Shah. ibem: empowering humans via intuitive interaction. CSAIL Technical Reports, 2015.
Interactive bayesian case model
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Jon M Kleinberg. Hubs, authorities, and communitics. ACM computing surveys (CSUR), 31(ss)):
5-cs, 1999.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436444, 2015.
Zachary Lipton. The mythos of model interpretability: In machine learning, the concept of interpretability both important and slippery. Queue, 16(3):31-57, 2018.
Edward Loper and Steven Bird. Nltk: The natural language toolkit. In Proceedings of the ACL Workshop Effecttiv Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics. Philadelphia: Association for Computational Linguistics, 2002.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- neurips cccpaaper/227/EE1e. ciates, Inc., 2017. URL https://proceedd//e pdf.
8a20a8
Scott M Lundberg, Gabriel G Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv: (80::080880.00 2018a
Scott M. Lundberg, Gabriel G. Erion, and Su-In Lee. Consistent individualized feature attribution for tree ensembles. CoRR, abs/1 802.03888. 2018b. URL http::///aaxx org/ /1802. 03888.
Scott M Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations to global understanding with explainable ai for trees. Nature machine intelligence, (1))55667,, 2020.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. arXiv preprint ar arXiv22011.0457, 2020.
Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pp. 142-150, 2011.
Aria Masoomi, Chieh Wu, Tingting Zhao, Zifeng Wang, Peter Castaldi, and Jennifer Dy. Instance- wise feature grouping. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13374-13386. Curran As- sociates, Inc., 2020. URL D inerreeeeddnnnnee.n............ 9b1 beaDDassedeeoDeeeaaaeeff33333333
neurips httpp..cc/ppaee wwtppcpppppppeeeeeeecep 2020/ file/ pdf.
W Meeusen and Cuyvers. Clique detection in directed graphs: new algorithm. Journal of Computational and Applied Mathematics, 183):185-203 1975.
Mark Newman. Networks. Oxford university press, 2018.
Guillermo Owen. Multilinear extensions of games. Management Science, 18(5-Part-2):64 79, 1972. URL
repec. wwtpee..rr//PPPe..... inm: ormnsc:v: 18:y:
1972:1:5-part-2:p:::
12

---

Published as a conference paper at ICLR 2022
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word
representation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1543, 2014. URL http: www. ac web. org/ anthologyyl.oo/oaoooooooool (ealoogyyD14-1000 116.1.
Vitali Petsiuk, Abir Das, and Kate Saenko. Rise; Randomized input sampling for explanation of black-box models. In Proceedings of the British Machine Vision Conference (BMVC), 2018.
Elizabeth A. Regan, John E. Hokanson, James R. Murphy, Barry Make, David A. Lynch, Terri H. Beaty, Douglas Burran-EEveeet,, Edwin K. Silverman, and James D. Crapo. Genetic epidemiology of COPD (COPDGene) study design. COPD, 7(1):32-43, February 2010. ISSN 1541-2563. doi: 10.3 141109//51155500344999999
Michael Reich, Ted Liefeld, Joshua Gould, Jim Lerner, Pablo Tamayo, and Jill P. Mesirov. GenePat- tern 2.0. Nature Genetics, 3805):000-511 May 2006. ISSN 1061-4036. doi: (0.1038/g0000655000
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. why should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1135-1144, 2016.
Daniel A. Schult. Exploring network structure, dynamics, and function using networkx. In In Proceedings of the 7th Python in Science Conference (SciPy, pp. 11-15, 2008
Patrick Schwab and Walter Karlen. Cxplain: Causal explanations for model interpretation un- der uncertainty. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, Curran As- sociates, Inc., 2019, URL httpt: httpttppp///pprceedngg.... neurips wttppppee/011/////e file/ 3ab6be4 6 wtw.eeeessaaaa3aaboloooooo www.-eeeff....eee.-ee--e Paper.pdf.
Lloyd S Shapley. 17. A value for n-person games. Princeton University Press, 2016.
Yoav Shoham and Kevin Leyton-Brood Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008. doi: 10.1017/CB0978051111 1654.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference on Machine Learning, pp. 3145- 3153. PMLR, 2017.
Erik Štrumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and information systems, 41 41(3):647-665, 2014.
Agnieszka Strzelak, Aleksandra Ratajczak, Aleksander Adamiec, and Wojciech Feleszko. Tobacco smoke induces and alters immune responses in the lung triggering inflammation, allergy, asthma and other lung diseases: a mechanistic review. International journal of environmental research and public health, 15(5): 1033, 2018
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328. PMLR, 2017.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The shapley taylor interaction index. In International Conference on Machine Learning, pp. 9259-9268. PMLR, 2020a.
Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The Shapley Taylor Interaction Index. In Proceedings of the 37th International Conference on Machine Learning, pp. 9259-9268. PMLR, November 2020b.
R. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1:146-160, 1972.
Michael Tsang, Dehua Cheng, and Yan Liu. Detecting statistical interactions from neural network weights. arXiv preprint arXiv: 700.77555.77777 2017.
Michael Tsang, Youbang Sun, Dongxu Ren, and Yan Liu. Can i trust you more? model-agnostic hierarchical explanations. arXiv preprint /8/1v:/8/2.04480 2018
13

---

Published as a conference paper at ICLR 2022
Michael Tsang, Sirisha Rambhatla, and Yan Liu. How does this interaction affect me? interpretable attribution for feature interactions. arXiv preprint arXiv:2006.10963 2020.
Jiaxuan Wang, Jenna Wiens, and Scott Lundberg. Shapley flow: A graph-based approach to
interpreting model predictions. In International Conference on Artificial Intelligence and Statistics, pp. 721-729. PMLR, 2021a.
Zifeng Wang, Aria Masoomi, Zhonghui Xu, Adel Boueiz, Sool Lee, Tingting Zhao, Russell Bowler, Michael Cho, Edwin Silverman, Craig Hersh, Jennifer Dy, and Peter Castaldi. Improved prediction of smoking status via isoform-aware ma-seq deep learning models. PLOS Computational Biology, 17(10) 10 2021b. doi: 10.137 1 1009433. URL htt.t:////// http:://dooooooo/ 10. 1ww.137//// jooronuuaaaa.a... pcb.ia..ppppp..... pcbi. 1009433.
Qianfan Wu, Adel Boueiz, Alican Bozkurt, Arya Masoomi, Allan Wang, Dawn DeMeo, Scott Weiss, and Weiliang Qiu. Deep learning methods for predicting disease status using genomic data. Journal of biometrics biostatistics, 9, 01 2018.
David Yang and Ching- Chen. Cigarette smoking- smoking-mediated mediated macrophage reprogramming: mechanistic insights and therapeutic implications. Journal of nature and science, 4(11), 2018.
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:9240, 2019.
Mustafa Kemal Yöntem, Kemal Adem, Tahsin ilhan, and Serhat Kiliçarslan. DIVORCE PREDIC- TION USING CORRELATION BASED FEATURE SELECTION AND ARTIFICIAL NEURAL NETWORKS. Nevşehir Hacı Bektaş Veli Universitesi SBE Dergisi, 9(1::559-273, June 2019.
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. Invase: Instance- variable selection using neural networks. In International Conference Learning Representations, 2018.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainabilityy in graph neural networks: A taxonomic survey. CoRR, abs/2012. 154455 2020. URL https://arxiv. http://aaxxwvv..aaaab.. /b222222..
15445.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. arXiv preprint arXiv:2102.05152 52, 2021.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, pp. 818-833. Springer, 2014.
Xiangrong Zeng and Mário AT Figuciredo. Solving oscar regularization problems by fast approximate proximal splitting algorithms. Digital Signal Processing, 31:124-135, 2014.
Hao Zhang, Yichen Xie, Longjie Zheng, Die Zhang, and Quanshi Zhang. Interpreting multivariate shapley interactions in dans In The AAAI Conference on Artificial Intelligence (AAAI), 2021.
14

---

Published as a conference paper at ICLR 2022
APPENDIX A SOCIETAL IMPACTS
As machine learning algorithms are widely deployed variety of domains such as health care, criminal justice system, and financial markets (LeCun et al., 2015; Doshi-Velez & Kim, 2017: Faghihpirayesh et al., 2021; Wang et al., 2021b; Lipton, 2018; Caruana al., 2015; Kim et al., 2015; Wu et al., 2018), it is important to make these often blxck-box models transparent. Understanding the reasoning behind the decisions black-box models may enable users' trust the model. This paper proposes novel method to explain black-box models. In particular, we extend univariate feature removal-based explanations higher-order bivariate explanations that allows discovery of directional feature interactions. Explainability opens up future research directions that can help data scientists check for bias, fairness, and vulnerabilities the models they use (Arrieta et al., 2020; Guidotti et al., 2018).
This paper provides a general machine learning approach for explaining black-box models that can be applied any data. We care about possible societal impact of applying machine learning to advance our understanding of disease. In this paper, our explanation method allows us to find the most influential genes for differentiating smokers versus non-smokers, potentially leading to better understanding of the relationship between smoking and lung disease by identifying how genes interact with each other for smoker versus a non-smoker. We plan to pursue further analysis of our results with careful guidance and insights from our medical expert collaborators. Machine learning (ML) can be applied to a variety of applications (to do harm or good), we encourage our colleagues to apply ML to beneficial applications such as health. Nevertheless, to be done correctly, one needs to work closely with domain experts to make proper judgments and lead to accurate conclusions. To increase the impact of our method, we make our source code publicly available.*
APPENDIX B GRAPH PRELIMINARY
Directed Graph (Digraph):
A Directed Graph G is defined by pair E), where V is non-empty finite set of elements called vertices and a finite set of ordered pairs of distinct vertices called ares or edges
Subdigraph:
digraph = (Vx, Ex)) is subdigraph of a digraph g (Vg, Eg) Vn Vg and Ey S Eg and every edge in Ex has both end-vertices in Vx, One says H. is induced by Vy and call H an induced subdigraph of G (Bang-Jensen Gutin, 2008).
Degree of a Directed Graph
Given V V the indegree of v is denoted d (v) which is the number of edges that points and the outdegree is denoted d't (v) which is the number of edges that points out from v to some other vertices. A node v E V is a source if d (w) = 0 and it a sink if dt (v) = 0 (Bang-Jensen & Gutin, 2008).
Weighted Directed Graph: is Directed Graph g = (V, E) with a mapping W : E - which assigns values to each edge. Hence, G can be shown as a triplet (V, E, W)) (Bang-Jensen & Gutin, 2008).
Walk:
walk in directed graph g (V, F)) is an alternating sequence W 21d12222273.. ... 10:---1----1111 where v; E V, < Vi < k and a; E E such that a, (Ii 2141) (Bang-Jensen & Gutin, 2008).
Strongly connected components (SCC)
In a directed graph G vertex y is reachable from vertex x if there is walk from to y. A directed graph G strongly connected if for every pair of x, y E V, x is reachable from y and vice versa.
A strongly connected component of an directed graph g is maximal induced subgraph that is strongly connected.
hhttps://// httppss////ittuub.cmm//aaaa http:://th..ht..cccco/////m/////
15

---

Published as a conference paper at ICLR 2022
Complete Graph. A directed graph 9 (V, E) is complete, if for every pair x, y E V, have (z, y), (g. x) E E (Bang-Jensed & Gutin, 2008).
Cliques: A clique is complete subdigraph of given graph (Meeusen & Cuyvers, 1975).
Quotient Graph
Given the graph H (V, Ex), we denote S (Vs, Es) quotient graph through strong connectivity equivalence relation, i.e., i j = i and j are strongly connected. More precisely:
Definition Given the graph H. (V, Ex), denote S (Vs, Es) reduced graph where:
The set of vertices the quotient set, ie., Vs = V/ ~ (SCC(u) : o E V}
Two equivalence classes SCC(u), SCC(v) E Vs forms an edge if and only if (u, v) E En In particular (Bloem et al., 2006):
Es = ((C) C*) C C" and Eu E C, E C² (v,0') E Exd
(7)
Graph Density of Digraphs:
Graph density computes ratio number of edges in the graph to the maximal number of edges, i.e.,
m
d
(8)
n 1)
where n is the number nodes and is the number of edges in the directed graph.
APPENDIX C PROOF OF THE THEOREM AND COROLLARY 1.1.
We restate the Theorem 1:
C.I THEBRREM
For i, & E D, assume that
max ((SUU()) u(S) E
(1)
JESCD
max iESCD
[u(SU (A}) u(S) &
(II)
Then, the following inequalities hold:
E S d!
2 T (E),)(( S d!
zci
(A)
E (w) 5 d!
ワ (28, + +()
(B)
Proof. Part A)
Using Eq (6), (u)g is equal to:
SS (d ( 1)!
[b3() =|
Σ
(u(SU((i)) -(S) <
(9)
d!
)ESCDV()
|S (d [S|
(u(SU u(S))
triangular inequality
(10)
f!
JESCD((1)
S (d |8| 1)!
SS (d 1S| 1)!
d!
Σ
d!
Ej Σ
)
2
(11)
JESCD((
JESCDV()
16

---

Published as a conference paper at ICLR 2022
*:All the possible combinations of features are d! but half of these times j E S and half of these times j & S, because given a sequence of features a1,.... dg where j E as follows:
(a1 J. 91s)
i
(115)42.... ... ad)
(12)
[S]
d-18|-1
There is an exact sequence on j $ S follows:
(1s)+2..... a.)
i (a1........us)
(13)
d-1s1-1
[S]
so it is d! elements that j E S, similarly derive the other inequality in part A which is 2 |2 S 2
Part B)
We start by writing E2 from Eq (6), i...:
|S (d - |S| 1)!
E (w)l (x)(
=1
Σ
(u(S U [K}) u(S))
d!
JESCDM(N)
(14)
IS! (d |S| 1)! (ESCDA(K)
((u(S (k)) u(S))
d!
where we used triangular inequality, now we look at the element inside the summation separately
when E and $ S. note that all cases j E S, particular we have:
i E S, then from the assumption 2 we have |u(S U (k)) - (SS))is less equal than 6j
if i ø this case we have the following:
( - u(S) S Ej, (SUU))) Es
we use (I)
ie U (i), we use (II)
(15)
(u) U (k}) - u(Su E
jE we use (I)
Using these three inequalities we have:
[[u(S (i)) u(S)] + (u(S U ((( (4 USSU (SU)))]
(u(S U (k)) u(S) [ (1)) u(S)] | (|SS::))))_Xx133333333333333333(
w5 (+)]
[[u(S [i) U (k}) - ( s +5 +ビ
(16)
where * uses triangular inequality. Hence have each element most 25 + e; for both cases when i E S or i & S. thus we have:
max (u(SU ((t)) e(S)) - (2s, + s:)
(17)
JESCD
using the similar arguments as in part A, we have the following:
S! (d |S| 1}!
132 =5
[u(SSU (k)) u(S))
d!
(18)
S|! (d |S| 1)!
+ Es) = d!
Σ
(2E,
(2s + Ex)
d!
2
(ESC
17

---

Published as a conference paper at ICLR 2022
C.2 COROLLARY 1.1.
For the corollary we did not mention what u is, to compute (u),, we need u. In this corollary assume that the utility function is monotone. In particular, Utility function P(D) - R is monotone iff
SS s.t S S S P(D) = u(S) - uSS).
This assumption on utility states that more features given the model does not hurt. An exmple of such utility function is mutual information, i.e., u(S) = (Xx:Y).
Corollary 1.1. (Transitivity): If E is the Shapley explanation map and u be a monotone utility function, then graph H. is transitive.
Proof. If E3) = 0 and (²) = 0 we want to show (2( =
Based on the assumption u monotone, hence every marginal gain is greater or equal than zero, i...
u(S U {i}) - uS)) 2 0, for all S _ P(D) an i E D.
Based on the assumption we have (2)) 0, i.i.c
|S| (d (dd1is] ( (d-1s-11 1)! - u(S)) = (19)
(2) =0 =
Σ
d!
(E)
But every element of the sum is greater or equal than zero hence, maxjesco I ((SSUi))
similarly from E (²²() we have maxiesCD [u(SU {k}) u(S) = 0. Using Theorem result
we have:
d! (28g 8i) E
Ex 0.
(20)
2
APPENDIX D PAGERANK
D.1 PAGERANK
PageRank (Page et al., 1999) is algorithm used by Google search in order to give a importance ranking for web pages in their search engine. Page rank output is probability distribution which represent the likelihood of person random clicking different links to end up in specific web page form (Page et al., 1999). here we overview the PageRank algorithm. The PageRank scores given the solution of the following system of equations:
8c E [0, 1), where Eiev 8
Σ
W'je WHs; for E V.
8 = a+
dy
FUAEE
where a E [0, 1] is a dampening factor (default value 0.85),
d Σ Wyk
K.G.EEEE
the outgoing weighted degree of node and [pi]iEv a probability distribution over V. In standard PageRank, [V] i.e., is the uniform distribution. In personalized pagerank, a different distribution, possibly differentiated per node, is used.
Intuitively, the PageRank scores correspond to the steady state random walk over the weighted graph with random restarts: with probability (1 a) the walker transitions to edge selected with probability proportional to neighboring edge weights. With probability a, the walker jumps to a random node in V, sampled from probability distribution p. Usually, they are via iterative applications of the above random walk transition equations, applied to a starting distribution over V V(Newman, 2018 8; Page et al., 1999).
18

---

Published as a conference paper at ICLR 2022
APPENDIX E DERIVATION OF BIVARIATE SHAPLEY EXPLANATION MAP FORMULA
To prove the equation (6), we need compute the E²(u); elements of the matrix F² (2())) (u) is the element in intersection jth column and 7th row. Based on the definition of E², we jth column is represented as L'(;)) where uj is defined as in eq (5). In the case of shapley explanation E(uy); has specific form based on Shapley value eq (4), i.e.
= EscDVO
19 (d- d!
(u - u,(
(21)
From the definition of új we know is zero if j & S, thus we can remove those from the summation, i.e.,
(N( = EjEseni EjES.CDAO
[S] (u, (S) - ()())
ISII (d= (uy (SU uy( =
(22)
EjESCDAO
|S|! (d= (u(SU (i)) u(S)) +0
APPENDIX F EXTENSION OF BIVARIATE EXPLANATION MAP TO MULTIVARIATE EXPLANATION
To generalize the bivariate explanation map E², define E* : 14 + RR x d which outputs
tensor, let I' be the tensor output, each element of this tensor would be denoted as Thi...u E hence each column would be defined as T E Rd and similar to E² is defined as E(u;,..i.. where u is defined as follows:
u, if fúr fii.... S
Wig..i 1: P(D) -R VS P(D), Whr (S)
(23)
0, if ( g S
APPENDIX G DETAILS OF EXPERIMENTAL SETUP AND ADDITIONAL EXPERIMENTAL RESULTS
G.1 EXPERIMENT SETUP
G.1.1 ALGORITHMS
Approximating Graph G with Shapley Sampling. Computation over all subsets features is computationally expensive. In practice we can use approximate the Bivarate Shapley value over fixed number of samples by adapting the sampling algorithm introduced by Štrumbelj & Kononenko (Štrumbelj & Kononenko, 2014), as seen in Alg. 1. Note that computing the G matrix adds no complexity to the original algorithm; we simply keep track of when feature j absent (i.e. j & S and set the value function output to zero when this condition occurs. We can therefore calculate the bivariate and univariate shapley values concurrently. Note that since we are discarding or "filtering out" the samples where is absent, we need to double the number of samples to achieve the same approximation accuracy as the univariate calculation.
Approximating Graph & with KernelSHAP.
As mentioned in Section 4, our method can be generalized to any removal-based Shapley approxima- tion other removal-based explainer. More concretely, each column of the d x d interaction matrix, representing interactions between d features, can be considered an independent explanation where the column feature is always present. Therefore which explanation method to use based on the constraints of their intended application. However, we can also improve performance by taking advantage of different approximation methods.
method is extremely flexible; the user can decide
19

---

Published as a conference paper at ICLR 2022
Algorithm 1 Approximate Graph 9 with Shapley Sampling Algorithm
Input: Data Sample x E X' Rd Utility Function f, Number Samples
Output: Adjacency Matrix G E BBdxa
Initialize =
for i=I... do
for m=I...M do
Create random permutation O of size d
Define as permuted index of feature
Define the set of indices ( and set indices D {O}
Sample random baseline w E X'
by Tali 7 (DD)(
\\ Symbol @ indicates concatenation
= ns uDD
for j E do
G. = Gr + f(b.) - f(bb)
end
end
end
G
9
Return g
Performance is improved through the use of two properties in KernelSHAP. First, save the sampled model outputs and reuse these values when recalculating KernelSHAP over all d features. This allows for fixed number of model samples independent of the number of data features. Second, note that KernelSHAP attributions are calculated through a weighted linear regression mechanism. Bivariate Shapley simply changes the model output (setting the output zero) depending on whether feature is present or removed, which corresponds to applying a binary mask over the linear regression labels. Therefore of the interaction matrix with two matrix multiplications with the sparse labels. This results in significant speed improvements and allows scaling to datasets with large number of features. such as the COPD dataset with 1,077 features.
save the intermediate linear regression calculation and evaluate each column
Mutual Redundancy on Graph H. Given the unweighted graph H. we want to find groups of mutually redundant features as investigated in Fig. 2. These features are identified as strongly connected nodes within the graph. We use the package NetworkX (Schult, 2008), which implements Tarjan's algorithm (Tarjan, 1972) to identify such nodes. Tarjan's algorithm is depth-first search that runs in lincar time. This algorithm for identifying mutually redundant features is outlined Alg. 3.
To generate the results of Fig. 2, apply binary mask for each sample such that given percentage of its mutually redundant features are set to their baseline value. Note that the number of features masked for given percentage may vary between samples, since the 76 is calculated on an instance- wise basis. We then record the accuracy for the set of masked samples.
Graph H. Directional redundancy is defined in terms of H-sinks and H-sources on graph H. which we investigate in Table 2. There are a number of methods to identify source and sink nodes graph; in implementation we the PageRank algorithm (Page et al., 1999) and take the maximally and minimally-ranked node as the sink and source, respectively (Alg. 4). Note that using PageRank in such manner will only identify singular sinks and sources, therefore we first separate graph H into its connected subgraphs and apply PageRank to the condensation graph of each subgraph. We use the PageRank implementation in the Seikit-Networf package (Bonald
Directional Redundancy
'Not that π (x) = oo when |x| E (0, d). therefore in practice we remove two variables during the linear regression calculation and enforce the following two constraints. 1) do fR(AA)), where do is defined as the bias/ intercept term in the regression, and 2) Σ, Φi f(x) - (
20

---

Published as a conference paper at ICLR 2022
Algorithm 2 Approximate Graph 9 with KemneSSHAP Algorithm
Input: Data Sample x E & R Utility Function f. Number Samples Output Univariate Shapley Values & E R", Adjacency Matrix G E Raxd
Initialize E R Initialize matrix X E [0, Initialize matrix 1I as an identity matrix 1M Initialize vector R. Define the KernelSHAP weighting kernel (x) chouse [x]) =|[d-1ar) (xr)
(d-1)
Randomly draw M samples around for m=1...M do
Sample random baseline X Sample binary vector {0, 1]d Calculate perturbed labels = f o x @w)
V\ Symbol O indicates Hadamard product
Xm, f- 36 Ym 6 -- Tm,m &- (Ttm)
Mixi indicates indices and] in matrix X. indicates the entire row / column.
end
\\ Solve a constrained 9, weighted linear regression
Define r = (X"11))=X"11
Define |+ = --
remove the last row of r remove the first row of r
Define r- = 1-
\\ Remove the last feature regression calculation with the constraint that Σ, Φ: = f(x) ((()) Define á r+[y X. (f(x) [(E[X))
ó (f(x) - f(E[T)) Σ, 0.)
\\ Enforce constraint. @ indicates concatenation.
\\
Iterate regression calculation over filtered labels
for / do
Define ++ = Y ② X Define o* 1 1 X x f(x)]
Vi Set Y. = 0 feature was not selected in X
Define Y
2 -X:s)
M\ Set Ym 0 feature j was selected Xm.:
Define o = r---- Xx,a f(E[x)))
a+ o+ @ (da 22-1)
Utilize the property that o- + x
Gog t ot
end
Return 6, g
et al., 2020) with no personalization and default damping 0.85. In practice, we found that changing the damping parameter had no effect on identified features.
In Table we show the results of completely masking all H-sources and H-sinks. We apply binary mask, setting the value all H-source or H-sink features to their baseline values, then record the sample accuracy.
Redundancy Ranking on Graph G. We want to create continuous ranking of feature redundancy given graph G, as investigated in Fig. 3. We first add 10 to each element in & to eliminate disconnected subgraphs. Note that for certain value functions, such as those used our experiments, the graph G contain negative values. We normalize these negative values by applying element-
21

---

Published as a conference paper at ICLR 2022
Weighted, Directed Explanation Graph g
Unweighted, Directed Explanation Graph H
The
movie
was
the
The
movie
the
a.ap
cuzz
A1
Su Surprisinaly
Surprisingly
0.13
611
Awful
Worst
Awful
Worst
Figure 5: Comparison of graph and graph H. for the the given IMDB example "The movie was the worst; surprisingly awful", which is classified negative sentiment. Note that the sinks and sources of graph and graph are reversed in terms of influential and redundant features. I.E. the source nodes of graph & represent redundant features, whereas the sink nodes of graph H represent (directionally) redundant features.
Algorithm 3 Mutual Redundancy Graph H
Input: Unweighted Directed Graph
Output Groups of Mutually Redundant Features
Define S = {a1,..., }m) the set of strongly connected subgraphs in H
Return S
Algorithm 4 Directional Redundancy on Graph 7
Input: Unweighted Directed Graph 7
Output Source Nodes and Sink Nodes
Define W= = (Mr, Wm } as the set of weakly connected subgraphs in H
for i = I.....m do
Create condensed graph e Condensation(us))
Source Node argmax PageRank (c.) Sink Node w: argmin PageRank (c.)
end
Source Nodes = Condensation "(()) Oies
Sink Nodes Condensation ((wr .... Wm.)
Return Source Nodes, Sink Nodes
wise Softplus function: Softplus(z) In(1 + e²). We then directly apply the PageRank algorithm from Scikit-Network to obtain feature rankings. We again use the default damping parameter of 0.85 for all datasets.
One issue we observed during testing was the occurrence of nodes with identical PageRank scores, indicating a similar level of redundancy. With other information, this would necessitate random selection when generating the feature ranking. With this motivation, we experiment with using the univariate shapley values personalization values. In personalized PageRank, the personalization
22

---

Published as a conference paper at ICLR 2022
values dictate the distribution over nodes for which random jump will land. With personalization, a random jump will land in each node with equal probability; i.c. the personalization is assumed to be uniform. By setting the personalization to the univariate shapley values, we bias the stationary distribution towards nodes that have high shapley values. Therefore, nodes of similar redundancy would be further ranked by their respective univariate shapley values. In practice, using personaliza- tion slightly improves post-hoc accuracy results in Fig. 3 for larger masking percentages. The full algorithm for generating the redundancy ranking of features outlined in Alg. 5.
Algorithm 5 Directional Redundancy Ranking Graph G.
Input:
Weighted Directed Graph G. optional Univariate Feature Ranking I E Red Output Score vector S E R", representing relative feature importance for each feature.
Define A as the adjacency matrix for Graph G
Ā A 10
Add = 0 to ensure all nodes are connected Element-wise Softplus function to normalize negative values
= (A))
if Persomalization then
S = PageRank(A) A) with Personalization Values R
else
PageRank(A)
end
Return S
G.1.2 IMPLEMENTATION DETAILS FOR BIVARIATE SHAPLEY AND COMPETITORS.
Unless otherwise specified, we use the default parameters when implementing comparison methods using publicly available code.
Removal-based methods typically assign a value to act as proxy for feature's absence during feature removal. This value commonly referred to as a baseline, or reference value, and is often assigned to be some a priori neutral value. While different removal-based methods may have different baseline values as default, we assign a single baseline value used for all methods for a given dataset. This is to maintain comparability, since the objective of our experiments is to evaluate the explanation calculation rather than the choice of baseline value. For tabular data, we define the value for all removed features to be zero, except the Divorce dataset where value of '3' indicates the average response, and the Census dataset where we fix the baseline to be the average value for each feature. For images, we use pixel value of zero. For text, we the word embedding for the selected feature to be the zero vector.
Bivariate Shapley Sampling. We apply Bivariate Shapley on variety of prediction models (detailed in section G.1.3), using a value function u(S) = Ew->s(((" = gl = xs L Ws)]. where the model's predicted class, S is the complement of S, and w represents samples drawn from baseline distribution B. As previously discussed, this baseline distribution is fixed to value that is dependent on the given dataset. We set m, the number of samples drawn in alg. to be 1000.
Bivariate Shapley Kernel. We utilize the algorithm described in G.c.
1.1.1 by adapting the publicly available package for kernelSHAP (Lundberg & Lee, 2017). We keep the same default parameters as KernelSHAP, except we double the number of default samples to account for the Bivariate Shapley filtering-
Shapley Excess. Shapley Excess refers to the surplus value from contribution of players in a coalition game grouped in a singleton coalition as compared to their individual contributions. This can be written formally as:
Φ2
Φi
23

---

Published as a conference paper at ICLR 2022
where 6e is the shapley value of group of players when considered singleton player. We implement this formula using the KemeISHAP approximation by combining features and evaluating the resulting excess Shapley value.
Shapley Interaction Index. Introduced by (Grabisch & Roubens, 1999). Shapley Interaction Index has gained popularity due to the efficient implementation by (Lundberg al., 2018b) on tree-based prediction models. In order to apply this method efficiently with the entirety of the datasets in our experiments, we use the KerneISHAP approximation calculate Shapley Interaction Index. This implementation results in significantly faster calculations compared to Shapley Sampling approximations (as seen in tbl 8. We use the default parameters of KernelSHAP, applied 2 x d times per sample, where d is the number of features.
Shapley Excess. Shapley Excess refers to the surplus value from contribution of players in a coalition game grouped in singleton coalition as compared to their individual contributions. This can be written formally as:
Ø=
Σ Φ iES
where 6s is the shapley value of a group of players when considered as singleton player. We implement this formula using the KerneSSHAP approximation by combining features and evaluating the resulting excess Shapley value.
Shapley Taylor Index. Introduced by Sundararajan et al. (2020b). As of this writing, there is no publicly available code for the Shapley Taylor Index. Therefore we build our own implementation using the Shapley Sampling approximation as outlined in the original paper. We choose sample size of m = 200 for each element of the interaction matrix.
GNNExplainer. Introduced by Ying al. (2019), GNNExplainer is method for explaining GNN-based black-box model. It can be used on a variety of GNN tasks, such as node or graph classification, and identifies compact subgraph and subset of node features that best explains the GNN output. This is accomplished through the use of a soft mask on the edges and node features of the input graph. Specifically, GNNExplainer trains a neural network to generate the edge and node feature masks, with the objective of maximizing mutual information between the black-box output of the masked graph and the label.
While GNNExplainer was originally intended to explain GNN models, it can be used in conjunction with non-GNN models. In our implementation, our objective is identify the important edges between the features of data sample. Therefore we define a fully-connected graph with the features as the graph nodes. When applying GNNExplainer to this fully-connected graph, GNNExplainer returns edge importance values for the given data sample. This output can be converted to subgraph using specifying a threshold, below which the edges are removed. In our experiments, we directly use the edge importance values the weights of a directed, weighted graph. This resulting graph is then evaluated and compared with Bivariate Shapley using the same algorithms for identifying mutually redundant features, directionally redundant features, and feature redundancy ranking, as outlined in App. G.1.I. We implement GNNExplainer using the Pytorch Geometric package (Fey & Lenssen, 2019) with default parameters.
Note that while GNNExplainer can indeed be applied to non-GNN models, these models may not be able to incorporate the graph structure in its predictions. For example, even though GNNExplainer applies an edge mask to the input graph, this edge information is meaningless if the black-box model not designed use this structure in its prediction. In this case, the GNNExplainer will receive non non-informative black-box outputs in its mutual information maximization objective.
G.1.3 DATASETS AND MODELS
COPDGene. The COPDGene dataset is an observational study with a cohort of 10,000 participants designed to identify the genetic risk factors for COPD. The study contains participants with and without COPD; COPD diagnosis, subtyping, and progression are monitored using high-resolution CT scans. We are interested in investing the relation between gene expression and smoking status (see section G.2.6 for details). The dataset contains aNA-sequen count data for 1,077 genes and the associated binary label for smoking status. We use neural network with 4 fully-connected
24

---

Published as a conference paper at ICLR 2022
Domain
Genetics
Image
Text
Tabular
Dataset
COPDGene
CIFARIO 10
MNIST 10
IMDB
Census
Divorce
Drug
Classes
2
Train/Test Samples
1,641/407
50k/10k
60k/10K
25k/25k
26k/6.5k
102/68
1413/472
Model
4. Layer MLP
Resnet18
2 Layer CNN
L-yyr GRU
XGBooot
3-yayer MLP
Random Forest
Model Accuracy
88.2
89.8
99.0
88.1
87.3
98.5
85.3
Table 3: Summary of the datasets and models in our investigation
layers of 200 hidden units, batch normalization, and relu activation. The model is trained using Adam (Kingma & Ba, 2017) with learning rate 10-3 for 800 epochs, achieving a test accuracy 88.2%.
CIFARIO. CIFARIO (Krizhevsky, 2009) consists of 60k images of dimension 32 x 32 with RGB channels. We train a Convolution Neural Network (CNN) to classify the 10 different classes, using Resnet18 architecture (He et al., 2016) with default parameters. We apply color jittering and horizontal flip data augmentations, as well as data normalization. The model is trained using Adam with learning rate 10 for 80 epochs, achieving test accuracy of 89.8%.
While is possible to use individual pixels when calculating Bivariate Shapley, we choose to superpixels to reduce computation and improve the interpretability of results. Superpixels are contiguous clusters of pixels that are treated as a single feature for feature importance purposes; iee all individual pixels within the superpixel are masked selected jointly. We use the simple linear iterative clustering (SLIC) algorithm (Achanta et al., 2012) in our image experiments. SLIC divides the image into similarly sized superpixels based on clustering in the CIELAB color space. For CIFARIO I0, we use SLIC with 255 superpixels and minimal smoothing (a - 5).
MNIST. MNIST (LeCun & Cortes, 2010) consists of 28 28 greyscale images with the handwritten numerals 0 9. We train a CNN with two convolution layers and a single batch normalization layer. Each convolution uses 6 x kernel size, stride 2, and a 200 channel mapping. We train the model using stochastic gradient descent (SGD) with learning rate 10-2 for 20 epochs, achieving a test accuracy of 99.0%. We again use SLIC to create superpixels; for MNIST we use 196 superpixels and 5.
IMDB. The Large Movie Review Dataset (IMDB) (Maas al., 2011) consists 50k movie reviews which we use for the task of sentiment analysis. We train Recurrent Neural Network (RNN) classifier with a single Gated Recurrent Unit (GRU) (Cho et al., 2014) layer of 500 hidden units to predict either positive or negative sentiment. We tokenize each review using the NLTK package (Loper & Bird, 2002) and map each token to a pretrained word embedding. We use the 300-dimensional GloVe (Pennington et al., 2014) embedding with 840B tokens, pretrained on the Common Crawl dataset. We limit the vocabulary to 10k tokens and text sample length to 400 tokens. The model was trained using Adam with learning rate 10-4 for 15 epochs, achieving test accuracy of 88.1%.
Census.
The UCI Census Income dataset aggregates data from the 1994 census dataset. We use 12 features, including both continuous and discrete data, predict whether an individual has anmual income greater than $50k. Our model is trained using XGBoost (Chen & Guestrin, 2016) with maximum of 5000 trees, 1 0.01, and subsample 0.5, achieving 87 37.3%tt accuracy.
Divorce. The UCI Divorce Predictors dataset (Yöntem et al., 2019) consists of a 54-question survey with 170 participants regarding various activities and attitudes towards their partners. Each question is answered with ranking on scale from 1 - 5. We train 3-layer MLP with relu activation, predicting the participant was divoreed. Each hidden layer contained 50 hidden units. The model was trained using SGD with learning rate 0.1 and achieved test accuracy of 98.5%. During the Bivariate Shapley calculation, we use baseline value of 3 to indicate a feature's absence, as this represents the value representing neutral response.
Drug, The UCI Drug Consumption dataset (Fehrman et al., 2017) consists of 1,885 responses to an online survey concerning the consumption habits of various drugs. We use binary features for the six drugs nicotine, marijuana, cocaine, crack, ecstasy, and mushrooms, indicating whether the respective drug has been previously consumed. We build model to predict whether the participant has also consumed a seventh drug, LSD. We use random forest model with 100 trees, achieving a test accuracy of 85.3%
25

---

Published as a conference paper at ICLR 2022
Clinical Center
Institution Title
Protocol Number
National Jewish Health
National Jewish IRB
HS- 18S-1
Brigham and Women's Hos- pital
Partners Human Research Committee
2007-P-000554/2;
BWH
Baylor College of Medicine
Institutional Review Board for Baylor College of Medicine and Affiliated Hospitals
H-222009
Michael
E.
DeBakey
Institutional Review Board for Baylor College of Medicine Affiliated Hospitals
H H-22200
VAMC
Columbia University Medi-
Columbia University Medical Center IRB
IRB-AAACY324
cal Center
Duke University Medical Center
The Duke University Health System Institutional
Pro00004464
Review Board for Clinical Investigations (DUHS IRB)
Johns Hopkins University
Johns Hopkins Medicine Institutional Review Boards (JHM IRB)
NAg0011524
Los Angeles Biomedical Re-
The John F. Wolf, MD Human Subjects Committee
12756-01
scarch Institute
of Harbor-UCLA Medical Center
Morehouse School
of
Morehouse School of Medicine Institutional Re- Board
07-1029
Medicine
Temple University
Temple University Office for Human Subjects Pro-
11369
tections Institutional Review Board
University of Alabama at
The University of Alabama Birmingham Institu-
FO70712014
Birmingham
tional Review Board for Human Use
University of California,
University of California, San Diego Human Re-
70876
San Diego
search Protections Program
University of lowa
The University of Iowa Human Subjects Office
200710717
Ann Arbor VA
VA Ann Arbor Healthcare System IRB
PCC 2008--110732
University of Minnesota
University of Minnesota Research Subjects' Pro-
0801M24949
tection Programs (RSPP)
University of Pittsburgh
University of Pittshurgh Institutional Review
PR007120059
Board
University of Texas Health
UT Health Science Center San Antonio Institu- tional Review Board
HSC20070644H
Sciences Center at San An- tonio
Health Partners Research Foundation
Health Partners Research Foundation Institutional
07-127
Review Board
University of Michigan
Medical School Institutional Review (IRBMED)
Board
HUM00014973
Minneapolis VA Medical
Minneapolis VAMC IRB
4128-A
Center
Fallon Clinie
Institutional Review Beard/Research Review Com- mittee Saint Vincent Hospital Fallon Clinic
1143
Fallon Community Health Plan
Table 4: IRB Information for COPDGene Dataset
G.1.4 LICENSES FOR COPDGENE DATA
All participants provided their informed consent, and IRB approval was obtained from all concerned institutions. IRB information is provided in Tab. 4.
G.2 ADDITIONAL EXPERIMENTAL RESULTS
G.2.1 INSERTION AND DELETION AUC
Insertion AUC (iAUC) and Deletion AUC (dAUC), introduced by (Petsiuk et al., 2018), quantify the ability for explainer to find the most influential features of given black-box model. We use iAUC and dAUC as a supplementary metric to evaluate the redundancy- based ranking we explore in figure 3.
To summarize, dAUC iteratively removes the highest-ranked features a given image and measures the change in model output compared to the baseline prediction, summarized by the under
26

---

Published as a conference paper at ICLR 2022
Insertion AUC (Higher better)
Deletion AUC (Lower better)
Datuset
COPD
CI
MNIST
IMDR
Census
Divorce
Drig
COPD
CIPARIO
MNIST
IMDB
Census
Divorce
Drug
Ours-So SS
0.48
0.75
0.85
0.45
0.43
0.30
0.30
0.01
0.05
0.03
0.02
0.32
0.05
0.10
Ours-K
0.49
0.65
0.84
0.43
0.42
0.30
0.30
0.00
0,08
0.03
0,02
0.32
0.05
0.10
Sb-Sam
0,48
0.75
0.85
0.45
0.43
0.30
0.30
0.01
0,05
0.03
0,02
0.32
0.05
0.10
KSHAP
0.42
0.77
0.29
0.42
0.29
0.30
0.09
0.17
0.17
0.03
0.36
0.05
0.11
Sh-Int
0.20
0.35
0.46
0.32
0.43
0.17
0.23
0.31
0.52
0.29
0.33
0.14
0.20
Tay
0.78
0.42
0.16
0.27
0.19
0.19
0.31
0.05
0.19
Fxx
0.51
0.37
0.31
0.29
0.15
0.29
GNNEXp
0.25
0.15
0.25
0.30
0.38
0.25
0.26
0.25
0.15
0.25
0.30
0.38
0.25
0.27
Table 5: Influential Feature Evaluation through Insertion and Deletion AUC. We calculate a feature ranking by applying PageRank on the 9 graph, iteratively removing the most influential feature, then evaluating AUC the resulting curve. Note that we cannot run Sh-Tay and Sh-Exc methods on the COPD dataset due to their computational issues with the large number of features.
10% Features Mask
50% Features Musk
Datasct
Ours
Shap
Sampl
Int
KemelSHAP
L2X
Ours
Shap
Sampl
Int
KemeISHAP
L2X
COPD
100
0.0 100
0.0 82.8
1.9 99.3
0.4
92.6
1.3
100
0.0
100 + 0.0 65.3
100
0.0 86.0
+ 1.7
CIFARIO
99.4 0.3
99.0
1. 0.4 70.2
2.0
86.6
1.0 71.4
1:4.::2000 2.0
93.0
92.4
1.2 32.8
2.1 54.9
1.4 23.2
1.9
MNIST
100 + 0.0 100
2 0.0
84.6
1.6
100
0.0
100
1: 0.0
100
0.0
100
+ 0.0
62.8
2.2 99.9 1 0.4 100
0.0
IMDB
100 000=00
100
0.0 92.6
1.2
100
94.0
100
0.0
100
+
0.0
61.4
1.0
57.9
2.2
Census
100 + 0.0
100
0.0 100
0.0
9.9
0.8
96.8
0.8
96.8
0.8
918
+
1.0 90.0
1.3
84.8
1.6
Diverce
100 0.0
100
98.5
100
0.0
100
1
100
100
98.5
1.5
98.5
Drug
100 0.0
100
1 0.0
91.7
+
1.3 100
0.0
100
1 0.0
99.2
0.4 99.2
0.4 77.1
+ 1.9 100
+
0.0
75
4
2.0
Table 6: Accuracy results for masking redundant features as identified using PageRank on graph G. These results mirror Figure 3 but with the result variance, as represented by + standard deviation. Note that for datasets with 10 features, the given feature mask percentage is approximate.
the curve. Lower dAUC values indicate that the explainer can accurately assess the features most influential towards the model output. Conversely, iAUC starts with uninformative bascline sample then iteratively inserts the highest-ranked features, then measures change in model output through AUC. Higher values of iAUC indicate better performance. We evaluate Bivariate Shapley, as well as a variety of popular univariate and bivariate black-box explainers, on these two metrics in table 5.
G.2.2 SAMPLING VARIANCE OF POST-Hoc ACCURACY RESULTS
The Bivariate Shapley method, like other shapley-based methods, does not involve any training or optimization of weights. Therefore it does not suffer from issues related to data variability. In addition, the quantitative results from our experiments are averaged over x 500 test samples (less for divorce and drug, due to dataset size). We show the variance results for Figure 3 in Table 6.
G.2.3 BIVSHAP-K K RESULTS FOR SINK AND SOURCE MASKING ON GRAPH H.
The BivShap-K K results for sink and source masking on graph H are omitted in table 2 due to space constraints. We present the full full results in table
G.2.4 SENSITIVITY OF GRAPH H, TO
In Section 4.1 we define relaxed version of the redundancy graph H, = (VH, EX) where Vn2 Vgg and E7 = ((i.j) E Eg [i) S 7}. Intuitively, y E R acts as threshold to define redundant edges in Hy As y increases, the number of edges in H. also increases, resulting in larger mutually redundant clusters and a higher sensitivity to directional redundancy. From the perspective of accurately representing the black-box model, the choice of 7 presents tradcoff akin to sensitivity and specificity: larger 7 values more easily identify true redundancies within the data (increased sensitivity), the cost of potentially mislabeling non-redundancies (reduced specificity).
While it is trivial to choose y through cross- validatio using post-hoe accuracy (or equivalent metric), such methods are not ideal for instance- wise explanation purposes where the practitioner may not have access to a sufficient number of validation samples. We therefore attempt to establish guidelines for choosing 7. In particular we investigate the effect of 7 on graph density (Figure 6). Note that
27

---

Published as a conference paper at ICLR 2022
Shapley-S
Bivariate Shupley-K
PH-Accy
% Fest Masked
PH-Accy
% Feat Masked
Dataset
Sink
Source Masked
Sink
Source
Dataset
Sink
Source Masked
Sink
Source
COPD
99.5
62.7
1.5
98.5
COPD
97.3
62.7
13.6
86.4
CIFARID
94.6
15.0
6.2
93.8
CIFARIO
82.6
19.4
10.4
89.6
MNIST
100.0
13.4
77.7
22.3
MNIST
100.0
17.6
13.6
86.4
IMDB
100.0
54.0
3.5
96.5
IMDB
97.2
54.0
23.7
76.3
Census
100.0
82.0
23.8
76.2
Census
100.0
82.0
33.3
66.7
Divorce
100.0
51.5
22.2
77.8
Divorce
100.0
51.5
22.0
78.0
Drug
100.0
48.5
43.5
56.5
Drug
100.0
48.5
43.5
56.5
Table 7: Posthoc-accy of BivShap-S and BivShap-K after masking H-source nodes, representing
features with minimal redundancies, and H-sink nodes, representing directionally redundant features.
H-Radundancy Masking
Density Graph
COPD
CIFAR10
MNIST
0.6
Post-hac accuracy | Density
0.2
-10
-8
-6
-4
-2
0-10
-8
-6
-2
0-10
-6
-6
-4
-2
Census
Divorce
Drug
1.0
0.8
0.4
0.2
-4
0-10
-6
-2
0-10
-8
Log-Gamma
Figure 6: Sensitivity analysis of graph H. to parameter y. We compare the density of H as y increases to the post-hoc accuracy after masking all directionally redundant features found in H.
increasing " also increases the density of graph H. We accuracy exhibits a sharp decrease, suggesting that the identified redundancies are not truly redundant. The ideal y depends the level of redundancy in the dataset, therefore the value should be chosen based on the given task. For experimental purposes, we use a constant y = 10-5 for all datasets.
that certain density, post-hoc
We also explore how inereasing ? affects the identification of mutually redundant features in Figure 7. We similarly see that increasing increases the number of edges in graph H. which correspondingly increases the number of mutually redundant features identified. For datasets with inherently low mutual redundancy, such as CIFAR 10, this has the effect of reducing Post-hoc accuracy when is increased past certain threshold. Therefore in practice should be selected either through cross validation, or by examining the density curve as in Figure 6.
G.2.5 TIME COMPLEXITY DETAILS WITH UNIVARIATE COMPARISON.
Table 8 includes the full feature attribution timing results. Note that L2X requires an initial training stage for neural network-ban -ased explainer model, which is not included these results. Once this explainer model is trained, the topk features are obtained through single forward pass, which is the activity measured in Table 8. All experiments are performed on an internal cluster equipped with Intel Gold 6132 CPUs. The evaluations CIFAR10. MNIST, IMDB datasets were calculated using GPUs (Nvidia Tesla V100), whereas the other datasets were trained without a GPU. Finally, the calculated times averaged over all samples used in the experiments (500 samples, unless the
28

---

Published as a conference paper at ICLR 2022
COPO
IMDS
CIFARIO
MNIST
Divarce
Drug
Consus
BivShap-S
BivShap-K
Sh-Tay
Sh-Exc
100
-Ah
PH-accy
11e-05
70
50
30
100
Xra
PH-aCCy
1-00.000 00.0003
80
70
50
30
100
++
Ptt-accy
V-
80
660
30
20
100
80 % Features Masked
20 40
60
100
20
40
60
80
100
80 % Features Masked
20 40
60
100
20 40 60 80 100 Features Masked
Features Masked
Features Masked
Posthoc Accuracy evaluated on Mutual Redundancy masking derived from graph H. Strongly connected nodes in H. are randomly masked with increasing mask sizes until a single node remains, represented by the final marker for each dataset. Each row represents different selection of threshold parameter Note that we cannot run Sh-Tay and Sh-Exc methods the COPD dataset due to their computational issues with the large number of features.
Figure
Bivariate Methods
Univariate Methods
GNN Methods
Daraset
Features
Ours-SS
Ours-K
Sh-Int
Sh-Tay
Sh-Fxc
Sh-Sam
kSHAP
L,XX
GNNExp
COPD
5942
36
2877
112900
3047
CIFARIO
255
218
2.5
101
2819
62674
140
0.65
0.79
MNIST
196
116
1.5
48
1194*
2350*
57
0.34
0.42
IMDB
<400
207
1.9
160
1279
1796*
103
0.40
0.00
0.73
Ceasus
12
2.7
0.20
2.6
11.6
5.3
1.6
0.83
0.00
0.17
Divorce
54
18.2
0.34
6.5
63.2
93.3
11.3
0.16
0.00
0.15
Drug
2.3
0.07
1.21
181
0.96
1.26
0.10
0.00
1.54
Table 8: Time comparison in seconds per data sample for the methods used for the post-hoc accuracy and AUC calculations. Fields indicated by which were averaged over 5 samples due computational cost, otherwise time calculations were averaged over 500 samples (or the total number of test samples
if fewer than 500)
dataset has less than 500 samples total), except for the fields indicated by which were averaged over samples due to computational cost.
As previously mentioned in Sec 1.1.1, 1, the Bivariate Shapley method can be applied naively to any removal-based explanation method repeating the explainer's calculations times, where is the number of data features. It follows that our method's time complexity is dependent explanation method and, when implemented naively, linearly scales that method's ' complexity by the number of features. Certain methods, such as KemelSHAP, efficient implementations of Bivariate Shapley, which we outline in App G.I.I. We provide time comparisons to competing methods in Table 1.
the choice
be adapted realize even more
29

---

Published as a conference paper at ICLR 2022
Group
Pathway Name
Genes
q-value
Smoker
GSE25123 WT PPARG KO MACROPHAGE TIA STIM DN
0.02
GSE32986 GMCSF GMCSF
CURDLAN LOWDOSEE STIM DC_
GSE45365 WT VS. JENAR KO
NAIVE, VS, CO_ CDIIB DC_
18
0.20
TCELL,
GSE40274_ FOXP3_ VS, SSS_SOXP__AAA AND AND_LEFI TRANSDUCED DSSDDUED_ACTVVVTEE..CM ACTIVATED_COs CEA_DCCC__TTLLLU
25
0.21
GSE32986_ UNSTIML WW___S__CUUUURR "S__CDA,NN, LOWDOSE STIM_DC
0.32
NonSmoker
GSE25123 WT. VS PPARG_ KO MACROPHAGE STIM
STWDDOEESTMM..CCCCEEC GSE32986, UNSTIM VS, CURDLAN, LOWDDSE STIM DC DN
28
0.13
GMCSF
CURDLAN
DC
Table 9: GO enrichment results for the redundancy- ranking of graph G for Smoker and Nonsmoker subgroups. Gene pathways with q- q-value < 0.05 bolded.
G.2.6 GENE ONTOLOGY ENRICHMENT ANALYSIS OF COPDGENE DATASET
Chronic Obstructive Pulmonary Disease (COPD) is chronic inflammatory lung disease. The relation between COPD and smoking is well-established; it has been shown that smoking increases the risk of developing lung disease through variety of ways, such as increasing lung inflammation (Arnson et al., 2010). Here, we investigate the relation between gene expression data and smoking status in COPDGene data. We show the interpretation power of our methods by relating our most influential genes to biological pathways which correspond to smoking. We performed Gene Set Enrichment Analysis (GSEA) using the GenePattern web interface (Reich al., 2006) on the ranking of influential features, which generate follows. We first calculate graph & locally, in Alg. 1. We then create the global G graph for each subgroup. smokers and non-smokers, by averaging the adjacency matrix algorithm outlined in Section G.1.1 to obtain subgroup-specifte importance scores. We use the list of 1,079 unique gene names with their associated importance score input into the GenePattern interface. Gene set enrichment for these two groups was calculated using the GSEAPreranker module with 1000 permutations, using the Hallmark sets (c7 a.l.lll.7. v.....ymbools gmt). We observed genetic pathways corresponding to Macrophages as statistically significant at v-vulue 0.05 (the pathway table in the App., Table. 9). Macrophages are type of immune cells that can initiate inflammation, and they also involve the detection and destruction of bacteria in the body. The relation between such cells and smoking has been observed in biological domain; many studies have observed that smoking induces changes in immune cell function in COPD patients (Yang & Chen, 2018; Strzelak et al., 2018).
all samples within each subgroup (Fig. 8). We directly apply the ranking
wt..vv7...mmbsss..... gmtt and Immunologic gene
30

---

Published as a conference paper at ICLR 2022
Smoker
Nonsmoker
Gene Index
Gene Index
114
152
190
228
304
842
380
456
294
532
570
684
722
760
790
896
874
912
1064
152
90
228
268
304
380
$32
570
608
646
694
722
760
798
87-4
9122
090
960
1026
1064
Gene Index
Index
0.00
0.02
0.04
0.06
0.08
0.10
-0.05
0.004
0.03
0.02
-0.01
0.00
0.01
Figure 8: Adjacency matrix for graph G, averaged over Smoker and Nonsmoker subgroups and
displayed as a heatmap.
31


Reviews:
[{"review_id": "djzEyDWyJG", "reviewer": "Reviewer_k52n", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "## Strength:\n\n-   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.\nThis work takes an interesting approach. Making the interaction matrix conditional on a particular feature by modifying the original Shapley value sounds natural and simple. \n\n\n-   The paper provides extensive empirical results, which indicate that the approach is a good explanation for measuring the influence of features on each other.\n\n\n## Weakness:\n\n-   I am concerned about how well the sampling and kernel methods estimate the true bivariate Shapley explanation map?\n 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.\n\n- 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]: \n \n- 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?\n \n-   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.\n \n-   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.\n\n\n[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.\n", "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. \n\nIn 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.\n", "summary_of_the_review": "The idea and presentation of this work are, in my opinion, good despite existing problems. \nFurthermore, 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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YHoAhS12vuJ", "reviewer": "Reviewer_GZtH", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strength\n1. 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.\n2. The authors carry out an extensive experiment on a diverse set of models and tasks with comparison to several state-of-the art method.\n3. 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.\n4. The authors provide both theoretical justification as well as good illustrative examples.\n\nWeakness\n1. 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.\n", "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.", "summary_of_the_review": "The paper proposed an interesting and innovative solution to an important problem. Also the evaluation is very convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VHUXOTP1Ui", "reviewer": "Reviewer_5zsk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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\nThe 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.\n\nAs 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.\n\nThe proposed method appears to be technically sound and general, providing a framework for computing directional bivariate-explanation maps using any univariate explainer.\n\nExperiments 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.\n\nThe 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.\n\n\nWeaknesses\n\nI'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?\n\nIn 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?\n\nIt 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.\n\nHow does the choice of the univariate explainer affect the bivariate explanations? Is there a significant difference when using one univariate explainer versus another?\n\n\nMinor Weaknesses\n\nWhy is BivShap-K not included in Figure 2?\n\nIt'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.\n\nMissing '.' at the end of sentence 4 in the section, \"Illustrative Example\".\n\n\nAdditional Questions\n\nWhat is the utility function used in the experiments to compute approximate BivShap-S?\n\nThe \"Data.\" section says a neural network and a tree-based model is trained on the Divorce dataset, is this right?\n\nWhat are the hardware details used for the experiments?", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PIYxZCxK7Py", "reviewer": "Reviewer_WTCZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 studied problem is very important and interesting. XAI is highly related to the model's trust and safety\n\n+ 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.\n\n+ Experimental results are very promising and the analysis is very useful.\n\n+ It is great to see some discussion about the connections between the proposed method and GNN explanation techniques. \n\n- 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. \n\n- A better literature review of GNN explanation techniques is desired. ", "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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)