# ONNXExplainer: an ONNX Based Generic Framework to Explain Neural Networks
Using Shapley Values

Yong Zhao1 Runxin He2, Nicholas Kersting2, Can Liu1, Shubham Agrawal1,
Chiranjeet Chetia1, Yu Gu2 Corresponding author.

###### Abstract

Understanding why a neural network model makes certain decisions can be as
important as the inference performance. Various methods have been proposed to
help practitioners explain the prediction of a neural network model, of which
Shapley values are most popular. SHAP package is a leading implementation of
Shapley values to explain neural networks implemented in TensorFlow or PyTorch
but lacks cross-platform support, one-shot deployment and is highly
inefficient. To address these problems, we present the ONNXExplainer, which is
a generic framework to explain neural networks using Shapley values in the
ONNX ecosystem. In ONNXExplainer, we develop its own automatic differentiation
and optimization approach, which not only enables One-Shot Deployment of
neural networks inference and explanations, but also significantly improves
the efficiency to compute explanation with less memory consumption. For fair
comparison purposes, we also implement the same optimization in TensorFlow and
PyTorch and measure its performance against the current state of the art open-
source counterpart, SHAP. Extensive benchmarks demonstrate that the proposed
optimization approach improves the explanation latency of VGG19, ResNet50,
DenseNet201, and EfficientNetB0 by as much as 500%.

## Introduction

Explainabile AI (XAI), one of the pillars of the greater Responsible AI
programme coming of age, is playing an increasingly vital role in deployments
of machine learning models in commercial settings for two major reasons: first
because such models are responsible for a growing portion of the automated
decisions behind our everyday lives, where at the very least the consumers
themselves want explanations of these decisions; and second because of the
rising realization that most, if not all models, in particular Neural Networks
(NNs) trained on a sufficiently large corpus, will contain hidden biases
(Bender et al. 2021) that one would like to expose and rectify wherever they
drive a model decision, hopefully before impacting consumers. Not
surprisingly, a large number of techniques have been proposed over the years
to explain model decisions ( (Friedman 2001), (Byrne 2019), (Ribeiro, Singh,
and Guestrin 2016), (Lundberg and Lee 2017), (Altmann et al. 2010), (Morris
1991), (Apley and Zhu 2020), (Ribeiro, Singh, and Guestrin 2018), (Miller
2021), (Sundararajan, Taly, and Yan 2017a), (Yang, Rangarajan, and Ranka
2018), (Gurumoorthy et al. 2019), (Burkart and Huber 2021), (Lou et al.
2013)), of varying degrees of usefulness depending on the model and domain.
Typically one analyzes model decisions after the fact (offline) with an
arsenal of such techniques on an as-need basis, with SHAP (Lundberg and Lee
2017) tending to hold an especially popular place for both its power,
simplicity, and in some sense optimality as an explainer.

The production environment of large, sensitive industries such as consumer
finance, however, necessitate immediate real-time responses to model
decisions, ideally incorporating explainability into the model inference
process, yet XAI is not always an affordable option in leading frameworks.
Open Neural Network Exchange (ONNX) (onnx.ai 2021) models deployed on a Triton
(NVIDIA 2023) inferencing framework, for example, enjoy superior performance
(Guan et al. 2023) to competing choices such as TorchServe (Paszke et al.
2019a) or Tensorflow Serving (TFS) (Abadi et al. 2015), yet, lacking a
mechanism to store backwards layer derivatives (because all that matters for
inference is forward-propagation!), SHAP/XAI support is absent.

We propose to remedy this situation with a low-latency explainer based on
Shapley values (Nowak and Radzik 1994) specifically made for NN models,
ONNXExplainer. Our contributions are summarized as following:

  1. 1.

We build a deployable automatic differentiation scheme in the ONNX ecosystem
to obtain backpropagated gradients. This in turn provides the input data with
a heatmap that shows the attributions of the features in modern inference
servers (e.g., Triton).

  2. 2.

A novel optimization approach that pre-computes intermediate outputs for the
reference samples substantially accelerates the explanations as seen in four
benchmarked models in three frameworks (ONNX, TensorFlow, and PyTorch). In
addition, our approach significantly reduces memory consumption when the
number of reference samples is same as SHAP, which allows use of more
reference samples and thereby enables better explanation with the same
hardware constraints.

  3. 3.

One shot deployment, i.e. combining inference and explanations together as one
model, is enabled to simplify on-boarding explainable models on device.

## Related Work

As Machine Learning models are deployed in different industries and gradually
playing an increasingly important role for stakeholders to make critical
business decisions, the explainability of a model prediction becomes
critically important. Many methods have been proposed to explain machine
learning models. In general, the model explainers can be divided into two
categories: model-agnostic (Ribeiro, Singh, and Guestrin 2016; Strumbelj and
Kononenko 2010; Wachter, Mittelstadt, and Russell 2017; Mothilal, Sharma, and
Tan 2020) and model-specific, such as deep learning explainers (Shrikumar,
Greenside, and Kundaje 2017; Selvaraju et al. 2017; Binder et al. 2016;
Sundararajan, Taly, and Yan 2017b; Simonyan, Vedaldi, and Zisserman 2019;
Dhamdhere, Sundararajan, and Yan 2018). In SHAP (SHapley Additive
exPlanations) (Lundberg and Lee 2017), the authors propose a unified framework
to interpret machine learning models based on Shapley values (Nowak and Radzik
1994) and SHAP contains both model-agnostic and model-specific explainers.

Model-agnostic explainers, such as LIME (Ribeiro, Singh, and Guestrin 2016)
and kernel explanation in SHAP (Lundberg and Lee 2017), perturbs the input and
trains a surrogate model to approximate models’ prediction to obtain
explanations without opening up the black-box models. Among deep learning
explainers, backpropagated (BP) gradients-based approaches predominate because
it attributes the importance scores to each feature in the input naturally.
Saliency maps have been used for some time to visualize/interpret the images
(Simonyan, Vedaldi, and Zisserman 2013; Dabkowski and Gal 2017). Attribution
propagation approach propagates the contributions of all neurons in the
network to the input (Sundararajan, Taly, and Yan 2017b; Montavon et al. 2017;
Shrikumar, Greenside, and Kundaje 2017). DeepLIFT (Shrikumar, Greenside, and
Kundaje 2017) outperforms other BP methods by backpropagating negative
relevance to increase class-sensitivity and solve the convergence problem and
it is the only BP method that passes the test in one recent work which
theoretically analyzes BP methods (Sixt, Granz, and Landgraf 2020).

In addition to LIME and SHAP, several other open source python packages for
XAI have been introduced (Biecek 2018; Baniecki et al. 2021; Yang et al. 2022;
Arya et al. 2019; Nori et al. 2019; captum.ai 2023). Many of them are an
unification of existing methods or mostly a wrapper of LIME and SHAP with
interactive utilities. For instance, OmniXAI (Yang et al. 2022) builds model-
specific and model-agnostic explainers on top of LIME and SHAP. Captum
(captum.ai 2023) is a different case with PyTorch interface which integrates
several explainers for NNs. However, none of them allow framework
interoperability or easy deployment on different hardware in modern inference
servers. Our approach proposes to use DeepLIFT (Shrikumar, Greenside, and
Kundaje 2017) to compute Shapley values for NNs in ONNX ecosystem, which
allows us to combine inference and explanation together as one model file to
deploy across various hardware in real time.

## Deep Learning Important FeaTures (DeepLIFT)

In this manuscript we use an approximation to Shapley values based on
DeepLIFT, the philosophy of which is to explain the difference in output from
some reference output in terms of difference of the input from the
corresponding reference input, measuring the target input’s importance on the
model prediction through back-propagation (Shrikumar, Greenside, and Kundaje
2017).

In this section, we introduce mathematical operators and their notations in
this manuscript. For a neural network model, let $t$ denote the output of a
neuron in some intermediate layer and $x_{0},x_{1},\cdots,x_{n}$ denote the
necessary and sufficient inputs to compute the $t$ from the neuron. The
reference-from-difference $\Delta{t}$ is denoted as $\Delta{t}=t-t^{0}$, where
$t^{0}$ is the corresponding output of the neuron from the reference input
${x^{0}}_{0},{x^{0}}_{1},\cdots,{x^{0}}_{n}$, which is chosen according to
domain knowledge and heuristics (for MNIST digit recognition, for example, one
could choose an all-black background image of 0’s). DeepLIFT assigns
contribution scores $C_{\Delta{x_{i}}\Delta{t}}$ to $\Delta{x_{i}}$ s.t.,

$\sum^{n}_{i=1}C_{\Delta{x_{i}}\Delta{t}}=\Delta{t},$ (1)

where $C_{\Delta{x_{i}}\Delta{t}}$ is the amount of difference-from-reference
in $t$, and it is attributed to or ’blamed’ on the different-from-reference of
$x_{i}$. The intuition is, as explained in (Lundberg and Lee 2017), that of a
sort of fast approximation of Shapley values where we examine the effect of
’including’ each $x_{i}$ in place of its reference default ${x^{0}}_{i}$.

Then the multiplier/derivative is defined as :

$m_{\Delta{x}\Delta{t}}=\frac{C_{\Delta{x}\Delta{t}}}{\Delta{x}},$ (2)

where $\Delta{x}$ is the difference-from-reference in input $x$ and
$\Delta{t}$ is the difference-from-reference in output $t$. Since the
contribution of $\Delta{x}$ to $\Delta{t}$ is divided by the input difference,
$\Delta{x}$, we can use the multiplier as a discrete version of a partial
derivative (Shrikumar, Greenside, and Kundaje 2017).

The chain rule for the multiplier can then be defined as the following,

$m_{\Delta{x_{i}}\Delta{t}}=\sum^{n}_{j=1}m_{\Delta{x_{i}}\Delta{y_{j}}}m_{\Delta{y_{j}}\Delta{t}},$
(3)

where $x_{i}$ is the neuron input for layer $H_{l}$;
$y_{0},y_{1},\cdots,y_{n}$ are neuron outputs for layer layer $H_{l}$ and
neuron inputs for successor of $H_{l}$. The analogy to partial derivatives
allows us to compute the contributions of model output w.r.t. model input via
back-propagation. The Shapley values can then be approximated by the average
as:

$\phi\approx Avg(\mathcal{M}*(X-R)),$ (4)

where $\mathcal{M}$ is the final matrix computed by multiplier w.r.t. the
model input in the back-propagation and $X$ is the input and $R$ is input’s
reference. Our focus is how to implement and accelerate $\mathcal{M}$ in the
ONNX ecosystem for any neural network. In ONNXExplainer, we adjust gradient
(multiplier) computation for nonlinear operators (e.g., Sigmoid and
MaxPooling) and use the original gradients computation for linear operators
(e.g., MatMul and Conv).

## Method

ONNX is an open-source standard representing neural networks in order to make
it easier for researchers and engineers to move NNs among different deep
learning frameworks and computing devices (onnx.ai 2021). We propose
ONNXExplainer to explain and interpret NNs in the ONNX ecosystem. As in SHAP
(Lundberg and Lee 2017), ONNXExplainer uses DeepLIFT (Shrikumar, Greenside,
and Kundaje 2017) to compute the Shapley values as a measure of feature
importance for NNs. SHAP depends on the automatic differentiation mechanism in
TensorFlow and PyTorch to compute gradients for Shapley value. However, in
onboarding deep learning models on a device for inference, current deep
learning frameworks will discard gradient information and only keep the
forward pass graph. In this scenario, SHAP cannot be saved or called directly
from the inference engine, e.g., ONNXruntime, because of the missing
dependencies and computation graphs to calculate differentiation and
gradients. Instead, ONNXExplainer provides its own automatic differentiation
mechanism to compute gradients for NNs so that practitioners can use it to
serve their NN models with Shapley values in a production pipeline. To make
ONNXExplainer explain a general NN, it has three key components as shown in
Figure 1: Neural Network Parser, Gradients/Multipliers Computation, and
Automatic Differentiation. Moreover, an optimization approach is provided to
improve the inference time by pre-computing intermediate outputs to forward
propagation inside ONNXExplainer.

Figure 1: A Schematic ONNXExplainer workflow for NN models, containing Parser,
Gradient/Multiplier Computation, Automatic Differentiation (Depth First Search
and gradient flows), and inference time optimization (Cache)

#### Neural Network Parser

As shown in Figure 1, a general NN model is converted to an ONNX format model.
The ONNX model contains computation nodes to inference the inputs. After
feeding the ONNX Model for NNs to ONNXExplainer, it first establishes the
forward symbolic graph. In the forward symbolic graph one computation node is
linked to other computation nodes because the output of the computation node
is always either the input to other computation node(s) or the output of the
ONNX model. With that, we can build the backward graph’s main structure whose
vertexes carry information about the computation nodes111The python style code
for the Parser is provided in the Appendix A..

#### Gradients/Multipliers Computation

Each deep learning framework contains hundreds of operators. We need to
implement/define gradients (for linear operators) and multipliers (for
nonlinear operators) in the ONNX ecosystem as well. In the current manuscript,
we have provided gradients/multipliers computation for more than 25 operators,
including Concat, Add, Mul, MatMul, Gemm, Sigmoid, ReLU, Softmax, Conv,
MaxPool, AveragePool, GlobalAveragePool, Transpose, BatchNormalization, and
others. When executing the forward symbolic graph, some intermediate outputs
needed for the gradient computation might be retained in memory for other
operations (Abadi et al. 2016; Paszke et al. 2017, 2019b). In this way, the
deep learning frameworks can avoid extra computations when training the NNs.
However, those intermediate outputs usually are opaque to the users. After
training, current deep learning frameworks in the market will freeze the model
and keep only the forward symbolic graph for inference. Under this scenario,
we have to implement the gradients/multipliers computation for the inference
operators only using the existing forward symbolic graph222Details are
provided in the Appendix B.. To summarize at a high level, we use the Linear
Rule for linear operations to compute gradients and the Rescale Rule and the
RevealCancel Rule for nonlinear operations to compute multipliers (Shrikumar,
Greenside, and Kundaje 2017).

#### Automatic Differentiation

Automatic differentiation is useful for implementing machine learning
algorithms such as back-propagation for training neural networks. PyTorch and
TensorFlow both use automatic differentiation. However, when the models get
on-boarded on device for inference purpose, they usually are frozen as a file
which containing only the model structure (forward pass) and corresponding
parameters. DeepLIFT needs the back-propagation to compute Shapley values and
SHAP is reliant on the tf.gradient for TensorFlow and the torch.autograd.grad
for PyTorch, both of which are not serializable. Hence, we need to build our
own automatic differentiation in the ONNX ecosystem.

Figure 2: Four types of gradient flows.

The differentiation algorithm conducts Depth First Search (DFS) to identify
all of the operators in the backward pass from the output to the input to the
model and sums the partial gradients that each operator contributes. Before
introducing how the DFS works, we demonstrate the four types of gradient flows
as shown in Figure 2:

  * •

one2one: The one2one type is simple: both incoming and outgoing gradients just
have one branch. We multiply the incoming gradients with the local gradients
if any to obtain the outgoing gradients. Activation functions are typical
operators of this type. If the operator has no local gradients, we just pass
the incoming gradients to the successors in the backward pass.

  * •

many2one: The many2one type has multiple flows of incoming gradients but one
flow of outgoing gradients. We sum all incoming gradients at first and then
multiply this summation with the local gradients if any to obtain the outgoing
gradients.

  * •

one2many: The one2many type has one flow of incoming gradients and multiple
flows of outgoing gradients. After multiplying the incoming gradients with
local gradients if any, we split or assign the outgoing gradients to the
successors.

  * •

many2many: The many2many type is the combination of many2one and one2many.

Algorithm 1 DFS to compute Shapley values

Input: the backward graph $G$, the first computation node $N$
Output: Gradient node list $L$

1: Let $S$ be the stack.

2: $S$.push($N$)

3: Mark $N$ as visited.

4: Define the difference-from-reference $y_{x}-y_{r}$ as the loss $grad_{in}$.
{$y$ is the output of model.}

5: while $S$ is not empty do

6: $C$ $\leftarrow$ $S$.pop()

7: $O,grad_{in}\leftarrow F_{grad}(C,G,grad_{in})$ {$F_{grad}$ is the function
to compute gradients/multipliers for operators.}

8: Append $O$ to $L$.

9: for neighbor $W$ of $C$ in $G$ do

10: if $W$ is not visited and it gets all gradient flows then

11: $S$.push($W$)

12: Mark $W$ as visited.

13: end if

14: end for

15: end while

16: return $L$

Figure 3: Inference graph to the demo model.

(a) SHAP

(b) Optimization

Figure 4: The diagrams of computing Shapley values using SHAP and our
optimization approach for a simple forward symbolic graph with two computation
nodes: MatMul and Sigmoid. In diagrams, blue nodes are for the forward pass
and orange nodes are for the backward pass. For instance, an orange Sigmoid
node is the gradient computation of a blue Sigmoid node in the back-
propagation. The grey area in each box is the output shape of the computation
node. We use 5 reference samples to explain the data in the example.

ONNXExplainer uses DFS (Depth-First Search) to reverse the forward symbolic
graph to compute Shapley values. The procedure is summarized in Algorithm 1.
The DFS algorithm takes the backward graph $G$ and the first computation node
$N$ as the inputs and it returns a list of computation nodes. Here the
backward graph $G$ is obtained from Neural Network Parser and $N$ is the first
computation node in the backward pass. Each vertex in $G$ contains information
to perform DFS and we use the name of the visiting computation node to get
that information. From lines 1-3, we create an empty stack and push $N$ onto
the stack, marking $N$ as visited. Line 4 defines the loss $y_{x}-y_{r}$ to
compute gradients w.r.t. the model input. The rest of the algorithm details
how to traverse all computations nodes in the backward pass. Function
$F_{grad}$ returns a list of computation nodes $O$ to compute gradients for
the visiting node $C$ and the incoming gradients $grad_{in}$ for next node(s)
in line 7. If the neighboring node $W$ of $C$ is not visited and it receives
all incoming gradient flows, we push $W$ onto the stack and mark it as
visited.

#### Automatic Differentiation Acceleration and Computation Graph
Simplification

In SHAP when the reference data is fed to the model, there are redundant
operators during Shapley value’s generation. For example, the target point’s
output is recomputed every time when comparing with a reference point, thus
making SHAP inefficient. Meanwhile, the automatic differentiation’s
acceleration algorithm inside ONNXExplainer optimizes the existing computing
approach and simplifies the computation graph to generate Shapley values. Some
of the optimization and simplification strategies are like caching commonly-
used intermediate outputs during the forward pass for backward propagation.
Figure 3 shows a demo neural network graph to explain the details of our
optimization and simplification algorithm. This simple forward symbolic graph
contains only two nodes: MatMul with weight W and Sigmoid, their corresponding
dimensions listed in Figure 3. Figure 4 shows two diagrams of how our approach
and SHAP compute Shapley values for the NN model in Figure 3. SHAP explains
the input based on an iterative comparison to the sample inside the reference
data set one by one. In the example in Figure 4, we have 5 reference samples
as $R$ of $5\times 32$ to explain one example $X$ of $1\times 32$. We
summarise how our optimization approach simplifies the computation graph of
Shapley values compared to the usual SHAP in two respects:

  * •

Forward pass: For SHAP, shown in Sub-figure 4(a) as the blue blocks, each
sample inside the reference set has to inference both the target and the
reference to get the final output difference. Thus for this demo, SHAP has to
infer 10 times in total: 5 for the one-time reference 5 for the target input.
On the other hand, as shown in Sub-figure 4(b) as the mirror forward pass, the
forward symbolic graph in the optimized approach only infers the target once
then caches the output and broadcast for further usage. $h_{R}$ is the outcome
of MatMul and also is the input to Sigmoid for the reference data.
$\hat{y}_{R}$ is the outcome of Sigmoid for the reference points. Both $h_{R}$
and $\hat{y}_{R}$ are ingested in computing the multiplier for Sigmoid in
explaining new data on-the-fly.

  * •

Backward pass: This example has one linear operator, MatMul, and one nonlinear
operator, Sigmoid, and their optimized gradient computations are indicated
respectively as following.

    1. 1.

Sigmoid: As shown in the shaded areas of Figure 4(a), since SHAP computes the
target output 5 times in the previous forward step, it needs to first split
the data then do the subtraction and finally tile back in order to pass
further operators. Meanwhile, as the shaded areas in Figure 4(b) show, the
target’s output from the forward pass is directly broadcast to the subtraction
operator. Thus, due to the redundant computation in the forward pass, SHAP has
two more Splits and one more Tile than our optimization approach. Moreover,
because the subtraction outputs’ dimension is reduced from $10\times 1$ to
$5\times 1$, the Greater in the optimization approach takes half the number of
floating-point operations as SHAP. Both SHAP and our approach use the
reference’s Sigmoid gradients as the incoming gradients for MatMul. The
difference is our approach computes the gradients only one time when
constructing the backward symbolic graph and SHAP keeps recomputing the same
gradients at run-time.

    2. 2.

MatMul: Similar to the Greater operation in Sigmoid, the transposed $W$ in the
optimization approach multiplies with half the number of floating-point
operations that SHAP needs to acquire the gradients.

### One-shot Deployment

As shown in Figure 1, one of the major contributions to the proposed
ONNXExplainer is its ability to save the forward neural network and its
corresponding graph to calculate Shapley values together in a single ONNX file
for one-shot deployment. Meanwhile the current open-sourced libraries, such as
SHAP (Lundberg and Lee 2017), need to call their own APIs (Application
Programming Interfaces) in order to generate Shapley values, accounting for an
extra step during deployment. Moreover, these libraries depend on other deep
learning frameworks, such as TensorFlow or PyTorch, as their computation
backend, which makes the on-device deployment even more complicated.

## Results

### Experimental Settings

#### Dataset

We use images of $3\times 224\times 224$ with 10 classes on the ILSVRC-2012
dataset (Deng et al. 2009) to evaluate the explanation time between our
optimization approach and SHAP. We use a reference input of all zeros both for
the optimization approach and SHAP.

#### Neural Networks

We use four representative models: VGG19 (V19) (Simonyan and Zisserman 2014),
ResNet50 (R50) (He et al. 2016), DenseNet201 (D201) (Huang et al. 2017), and
EfficientNetB0 (EB0) (Tan and Le 2019) in our benchmarks. V19 is one of the
neural networks with a large number of weights with 19 weighted layers and no
jump layers. R50 is one variant of residual NNs that stack residual blocks, in
which skip connections are jump layers to convert regular networks to residual
networks via addition. R50 has 107 weighted layers and 16 ”add” jump layers.
D201 is the largest DenseNet variant which concatenates all previous layers
with the current layer to form skip connections. It has 33 jump layers. EB0 is
a scaling NN with much fewer parameters and faster speed that is used for on-
device platforms. It has 25 jump layers of 9 additions and 16
multiplications333Details of the NNs and theoretical analysis of computational
complexity and memory consumption to explain them can be found in the Appendix
C..

#### Machine

We use two machines to perform our benchmarks444All brand names, logos and/or
trademarks are the property of their respective owners, are used for
identification purposes only, and do not necessarily imply product endorsement
or affiliation by the authors and their associated employers or institutions..

Machine A: CPU: AMD EPYC 7513 32-Core Processor; Total Memory:1056 GB

Machine B: GPU: V100; CPU: Intel(R) Xeon(R) Gold 6130 CPU; Total Memory: 790
GB; Nvidia Driver: 510.108.03; CUDA version: 10.1;

All benchmarks running on three machines use the same library dependencies:
TensorFlow 1.15.0, onnxruntime-gpu 1.12.0, onnx 1.12.0, Torch 1.13.1.

### The Visualization of Explanations from SHAP and optimized ONNX Explainer

Figure 5: Visualization of original images and its corresponding Shapley values simulation images by OPT-ONNX and SHAP (NON-TF). Each row represents a respective model. The first column is the images being explained, the second column is the simulation images by OPT-ONNX, and the last one is simulation images by SHAP[TF]. NN | agreement (%) | ONNX (%) | SHAP (%)
---|---|---|---
V19 | 100.0 | 0.0 | 0.0
R50 | 99.4 | 0.6 | 0.0
D201 | 99.8 | 0.2 | 0.0
EB0 | 99.6 | 0.4 | 0.0
Table 1: User agreement on closeness of contribution scores between OPT-ONNX
and NON-TF. The third column means ONNX is better and the last column means
SHAP is better.

To evaluate contribution scores obtained by different explainers, we design
the following task: in test dataset, we randomly select 10 images from 10
classes to conduct a user study. We do this by using OPT-ONNX and SHAP (NON-
TF) to compute Shapley values to explain 100 images, respectively. Then, we
only plot simulation images of Shapley values for the predicted class by four
models. We arrange original images and simulation images of Shapley values
(randomized order) in a row and send 100 rows of images for each model to
users. Table 1 shows users’ agreement on whether the contribution acquired by
OPT-ONNX and NON-TF are the same. We observe that all users have a high
agreement score (over 99%) that OPT-ONNX and NON-TF explain the images equally
well. In some cases, OPT-ONNX does better than NON-TF. Figure 5 shows example
images and corresponding contribution score simulation images by OPT-ONNX and
NON-TF for each model. It can be concluded that it is hard to tell the
difference between the two simulation images visually555Numerical comparisons
between the explainers can be found in the Appendix D..

### Memory Consumption and Latency Analysis

In this subsection, we use the optimization approach and SHAP described in
previous sections for a detailed memory consumption and latency analysis. SHAP
supports explaining NNs implemented in TensorFlow (NON-TF) (Abadi et al. 2016)
and PyTorch (NON-PT) (Paszke et al. 2019b). Other than ONNXExplainer (OPT-
ONNX), we implement ONNXExplainer with no optimization (NON-ONNX) and
optimized SHAPs. In this manuscript, we implement the same optimization
process (optimized SHAPs) in TensorFlow (OPT-TF) and PyTorch (OPT-PT) as in
ONNX. Then we can compare the latency for three pairs of explainers in the
same frameworks: OPT-ONNX versus NON-ONNX, OPT-TF versus NON-TF, OPT-PT and
NON-PT. In addition, we use half-precision for the four NN models with GPUs in
benchmarks.

#### Memory Consumption

| V19 | R50 | D201 | EB0
---|---|---|---|---
OPT-ONNX |  86/166 |  182/362 |  78/158 |  166/255
NON-ONNX | 61/121 | 130/256 | 47/93 | 68/135
OPT-TF |  79/149 |  157/242 |  60/115 |  154/232
NON-TF | 76/150 | 81/150 | 34/66 | 78/141
OPT-PT |  97/175 |  112/253 |  72/127 |  114/266
NON-PT | 72/163 | 107/243 | 49/104 | 89/204
Table 2: The largest number of reference images that can be used on a V100 GPU
[FP32/FP16].

As mentioned earlier, the optimization reduces the memory consumption in the
forward pass and theoretically in the backward pass too. Non-optimized
explainers explain the data one by one and so do its counterparts in the
benchmarks (more details in Appendix C). The largest number of reference
images is used to measure the memory usage in both optimized and non-optimized
explainers. Table 2 shows the largest number of reference images that can be
used on a V100 GPU for each explainer. In general, the optimized approach can
use many more reference images than its counterparts both using single and
half precision floating point except for OPT-TF for V19 in half precision. The
more reference samples, the more accurate the explanation is. In terms of
frameworks, OPT-ONNX for EB0 and V19 and OPT-TF for R50 and D201 gain a
superior edge over the number of reference images both in single and half
precision. In terms of models, the optimized explainers for EB0 can use more
reference images than their counterparts in other three models except for OPT-
PT for D201 in single precision and OPT-TF for D201 in half precision.

#### Latency Analysis

We infer and explain 100 images in each benchmark. After loading the models,
the first few inference requests can be significantly slower at run-time due
to deferred initialization and optimizations. Thus we consider the time to
explain the first image out of 100 as the cold start time (or warmup time) and
average the per-image latency of the rest for each benchmark.

Figure 6: Latency Comparison[FP32] between Optimization and Non-
optimization/SHAP in three Frameworks (ONNX, TensorFlow, and PyTorch) using
CPU cores on Machine A.

We run benchmarks using CPUs on Machine A and the results are shown in Figure
6. The optimized explainers are much faster at explaining the images than the
non-optimized explainers in all settings. Additionally, the speedup efficiency
obtained by ONNX and TensorFlow is stronger than PyTorch in all models.
Framework-wise and for optimized explainers, PyTorch is the fastest for all
models and TensorFlow comes next fastest.

Figure 7: Latency Comparison[FP32] between Optimization and Non-
optimization/SHAP in three Frameworks (ONNX, TensorFlow, and PyTorch) using
GPU on Machine B. We use 45, 30, and 45 for NON-ONNX, NON-TF, and NON-PT for
DenseNet201 because of memory limitation.

Figures 7 show latency comparisons on a V100 GPU666Half-precision benchmarks
can be found in the Appendix E.. It can be observed that optimized explainers
are superior to non-optimized explainers in most of benchmarking
configurations with one exception of cold start time for R50 by TensorFlow. In
this exception, OPT-TF spends a little more time explaining R50 than NON-TF
during warmup time in a few data points. Compared to benchmarks on CPU,
TensorFlow and ONNX both need to significantly warm up the models. In
particular, it takes TensorFlow hundreds of seconds to explain the first image
in all models. This tells us substantially warming up the models would
guarantee smooth production traffic without any delays. In terms of average
latency, OPT-TF and OPT-PT performs very close in all models. It seems that
OPT-TF has the largest acceleration gains than its peers for R50, D201, and
EB0 and OPT-ONNX surpasses OPT-TF and OPT-PT in speeding up the explanation
for V19.

## Conclusion

In this work we propose the ONNXExplainer to explain NNs using Shapley values
in the ONNX ecosystem. In ONNXExplainer, we build our own automatic
differentiation which enables one-shot deployment of NNs in inference
pipelines, such as Triton and ONNXruntime. The optimization by precomputing
outcomes from the reference data reduces lots of redundant computations in
explaining NNs. We develop and benchmark optimized explainers and non-
optimized explainers in three major deep learning frameworks (ONNX,
TensorFlow, and PyTorch) and test and compare the explainers using four
typical neural networks: VGG19, ResNet50, DenseNet201, and EfficientNetB0. The
benchmarks show that our optimized explainers significantly outperform
counterparts in terms of inference resources usage and explanation latency.

Future work will continue to generalize ONNXExplainer by: 1) supporting
gradients/multiplier computation for more operations, such as Loop, GatherND;
2) supporting more NN structures, such as Bidirectional LSTM/GRU models; 3)
further optimization of the gradients computation graph.

## Author Contributions

Conceptualization, methodology, Algorithm, Y.Z.; Experiments, Y.Z., R.H, N.K.;
writing–original draft preparation, Y.Z., R.H, N.K., C.L.; writing–review and
editing, R.H, Y.Z., N.K., S.A., C.L., C.C., Y.G.; visualization, Y.Z., R.H.

## References

  * Abadi et al. (2015) Abadi, M.; Agarwal, A.; Barham, P.; Brevdo, E.; Chen, Z.; Citro, C.; Corrado, G. S.; Davis, A.; Dean, J.; Devin, M.; Ghemawat, S.; Goodfellow, I.; Harp, A.; Irving, G.; Isard, M.; Jia, Y.; Jozefowicz, R.; Kaiser, L.; Kudlur, M.; Levenberg, J.; Mané, D.; Monga, R.; Moore, S.; Murray, D.; Olah, C.; Schuster, M.; Shlens, J.; Steiner, B.; Sutskever, I.; Talwar, K.; Tucker, P.; Vanhoucke, V.; Vasudevan, V.; Viégas, F.; Vinyals, O.; Warden, P.; Wattenberg, M.; Wicke, M.; Yu, Y.; and Zheng, X. 2015.  TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems.  Software available from tensorflow.org.
  * Abadi et al. (2016) Abadi, M.; Barham, P.; Chen, J.; Chen, Z.; Davis, A.; Dean, J.; Devin, M.; Ghemawat, S.; Irving, G.; Isard, M.; et al. 2016.  Tensorflow: a system for large-scale machine learning.  In _Osdi_ , volume 16, 265–283. Savannah, GA, USA.
  * Altmann et al. (2010) Altmann, A.; Toloşi, L.; Sander, O.; and Lengauer, T. 2010.  Permutation importance: a corrected feature importance measure.  _Bioinformatics_ , 26(10): 1340–1347.
  * Apley and Zhu (2020) Apley, D. W.; and Zhu, J. 2020.  Visualizing the effects of predictor variables in black box supervised learning models.  _Journal of the Royal Statistical Society Series B_ , 82(4): 1059–1086.
  * Arya et al. (2019) Arya, V.; Bellamy, R. K. E.; Chen, P.-Y.; Dhurandhar, A.; Hind, M.; Hoffman, S. C.; Houde, S.; Liao, Q. V.; Luss, R.; Mojsilović, A.; Mourad, S.; Pedemonte, P.; Raghavendra, R.; Richards, J.; Sattigeri, P.; Shanmugam, K.; Singh, M.; Varshney, K. R.; Wei, D.; and Zhang, Y. 2019.  One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques.
  * Baniecki et al. (2021) Baniecki, H.; Kretowicz, W.; Piatyszek, P.; Wisniewski, J.; and Biecek, P. 2021.  dalex: Responsible Machine Learning with Interactive Explainability and Fairness in Python.  _Journal of Machine Learning Research_ , 22(214): 1–7.
  * Bender et al. (2021) Bender, E. M.; Gebru, T.; McMillan-Major, A.; and Shmitchell, S. 2021.  On the Dangers of Stochastic Parrots: Can Language Models Be Too Big?  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’21, 610–623. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450383097.
  * Biecek (2018) Biecek, P. 2018.  DALEX: Explainers for Complex Predictive Models in R.  _Journal of Machine Learning Research_ , 19(84): 1–5.
  * Binder et al. (2016) Binder, A.; Montavon, G.; Lapuschkin, S.; Müller, K.-R.; and Samek, W. 2016.  Layer-wise relevance propagation for neural networks with local renormalization layers.  In _Artificial Neural Networks and Machine Learning–ICANN 2016: 25th International Conference on Artificial Neural Networks, Barcelona, Spain, September 6-9, 2016, Proceedings, Part II 25_ , 63–71. Springer.
  * Burkart and Huber (2021) Burkart, N.; and Huber, M. 2021.  A survey on the explainability of supervised machine learning.  _J. of Artificial Intelligence Research_ , 70: 245–317.
  * Byrne (2019) Byrne, R. M. J. 2019.  Counterfactuals in Explainable Artificial Intelligence (XAI): Evidence from Human Reasoning.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , 6276–6282. International Joint Conferences on Artificial Intelligence Organization.
  * captum.ai (2023) captum.ai. 2023.  Captum: Model Interpretability for PyTorch.  https://captum.ai/.  Version: beta.
  * Dabkowski and Gal (2017) Dabkowski, P.; and Gal, Y. 2017.  Real time image saliency for black box classifiers.  _Advances in neural information processing systems_ , 30.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_ , 248–255. Ieee.
  * Dhamdhere, Sundararajan, and Yan (2018) Dhamdhere, K.; Sundararajan, M.; and Yan, Q. 2018.  How important is a neuron?  _arXiv preprint arXiv:1805.12233_.
  * Friedman (2001) Friedman, J. H. 2001.  Greedy function approximation: A gradient boosting machine.  _The Annals of Statistics_ , 29(5): 1189 – 1232.
  * Guan et al. (2023) Guan, H.; Dwarampudi, M. R.; Gunda, V.; Min, H.; Yu, L.; and Zou, J. 2023.  A Comparison of Decision Forest Inference Platforms from A Database Perspective.  _arXiv preprint arXiv:2302.04430_.
  * Gurumoorthy et al. (2019) Gurumoorthy, K. S.; Dhurandhar, A.; Cecchi, G.; and Aggarwal, C. 2019.  Efficient Data Representation by Selecting Prototypes with Importance Weights.  In _2019 IEEE International Conference on Data Mining (ICDM)_ , 260–269. Los Alamitos, CA, USA: IEEE Computer Society.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Huang et al. (2017) Huang, G.; Liu, Z.; Van Der Maaten, L.; and Weinberger, K. Q. 2017.  Densely connected convolutional networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 4700–4708.
  * Lou et al. (2013) Lou, Y.; Caruana, R.; Gehrke, J.; and Hooker, G. 2013.  Accurate Intelligible Models with Pairwise Interactions.  In _Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’13, 623–631. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450321747.
  * Lundberg and Lee (2017) Lundberg, S. M.; and Lee, S.-I. 2017.  A unified approach to interpreting model predictions.  _Advances in neural information processing systems_ , 30.
  * Miller (2021) Miller, T. 2021.  Contrastive explanation: a structural-model approach.  _The Knowledge Engineering Review_ , 36: e14.
  * Montavon et al. (2017) Montavon, G.; Lapuschkin, S.; Binder, A.; Samek, W.; and Müller, K.-R. 2017.  Explaining nonlinear classification decisions with deep taylor decomposition.  _Pattern recognition_ , 65: 211–222.
  * Morris (1991) Morris, M. D. 1991.  Factorial Sampling Plans for Preliminary Computational Experiments.  _Technometrics_ , 33(2): 161–174.
  * Mothilal, Sharma, and Tan (2020) Mothilal, R. K.; Sharma, A.; and Tan, C. 2020.  Explaining machine learning classifiers through diverse counterfactual explanations.  In _Proceedings of the 2020 conference on fairness, accountability, and transparency_ , 607–617.
  * Nori et al. (2019) Nori, H.; Jenkins, S.; Koch, P.; and Caruana, R. 2019.  InterpretML: A Unified Framework for Machine Learning Interpretability.  _arXiv preprint arXiv:1909.09223_.
  * Nowak and Radzik (1994) Nowak, A. S.; and Radzik, T. 1994.  The Shapley value for n-person games in generalized characteristic function form.  _Games and Economic Behavior_ , 6(1): 150–161.
  * NVIDIA (2023) NVIDIA. 2023.  Triton Inference Server: An Optimized Cloud and Edge Inferencing Solution.  https://developer.nvidia.com/nvidia-triton-inference-server.  Version: x.y.z.
  * onnx.ai (2021) onnx.ai. 2021.  ONNX.  https://onnx.ai/.  Version: 1.12.0.
  * Paszke et al. (2017) Paszke, A.; Gross, S.; Chintala, S.; Chanan, G.; Yang, E.; DeVito, Z.; Lin, Z.; Desmaison, A.; Antiga, L.; and Lerer, A. 2017.  Automatic differentiation in pytorch.
  * Paszke et al. (2019a) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Kopf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019a.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _Advances in Neural Information Processing Systems 32_ , 8024–8035. Curran Associates, Inc.
  * Paszke et al. (2019b) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; et al. 2019b.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ , 32.
  * Ribeiro, Singh, and Guestrin (2016) Ribeiro, M. T.; Singh, S.; and Guestrin, C. 2016.  ”Why Should I Trust You?”: Explaining the Predictions of Any Classifier.  KDD ’16, 1135–1144. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450342322.
  * Ribeiro, Singh, and Guestrin (2018) Ribeiro, M. T.; Singh, S.; and Guestrin, C. 2018.  Anchors: High-Precision Model-Agnostic Explanations.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 32(1).
  * Selvaraju et al. (2017) Selvaraju, R. R.; Cogswell, M.; Das, A.; Vedantam, R.; Parikh, D.; and Batra, D. 2017.  Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization.  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , 618–626.
  * Shrikumar, Greenside, and Kundaje (2017) Shrikumar, A.; Greenside, P.; and Kundaje, A. 2017.  Learning important features through propagating activation differences.  In _International conference on machine learning_ , 3145–3153. PMLR.
  * Simonyan, Vedaldi, and Zisserman (2013) Simonyan, K.; Vedaldi, A.; and Zisserman, A. 2013.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  _arXiv preprint arXiv:1312.6034_.
  * Simonyan, Vedaldi, and Zisserman (2019) Simonyan, K.; Vedaldi, A.; and Zisserman, A. 2019.  Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv 2013.  _arXiv preprint arXiv:1312.6034_.
  * Simonyan and Zisserman (2014) Simonyan, K.; and Zisserman, A. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_.
  * Sixt, Granz, and Landgraf (2020) Sixt, L.; Granz, M.; and Landgraf, T. 2020.  When explanations lie: Why many modified bp attributions fail.  In _International Conference on Machine Learning_ , 9046–9057. PMLR.
  * Strumbelj and Kononenko (2010) Strumbelj, E.; and Kononenko, I. 2010.  An efficient explanation of individual classifications using game theory.  _The Journal of Machine Learning Research_ , 11: 1–18.
  * Sundararajan, Taly, and Yan (2017a) Sundararajan, M.; Taly, A.; and Yan, Q. 2017a.  Axiomatic Attribution for Deep Networks.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, 3319–3328. JMLR.org.
  * Sundararajan, Taly, and Yan (2017b) Sundararajan, M.; Taly, A.; and Yan, Q. 2017b.  Axiomatic attribution for deep networks.  In _International conference on machine learning_ , 3319–3328. PMLR.
  * Tan and Le (2019) Tan, M.; and Le, Q. 2019.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In _International conference on machine learning_ , 6105–6114. PMLR.
  * Wachter, Mittelstadt, and Russell (2017) Wachter, S.; Mittelstadt, B.; and Russell, C. 2017.  Counterfactual explanations without opening the black box: Automated decisions and the GDPR.  _Harv. JL & Tech._, 31: 841.
  * Yang, Rangarajan, and Ranka (2018) Yang, C.; Rangarajan, A.; and Ranka, S. 2018.  Global Model Interpretation via Recursive Partitioning.
  * Yang et al. (2022) Yang, W.; Le, H.; Savarese, S.; and Hoi, S. 2022.  OmniXAI: A Library for Explainable AI.

##  Appendix A Parser code

Listing 1 Network Neural parser code and build backward pass graph

⬇

1from collections import defaultdict

2class GraphVertex: #define vertex of backward graph

3 def __init__(self,

4 node=None, #computation node

5 neighbors=None, #neighbors in backward pass

6 flowin_grads=None, #incoming gradients

7 flowout_grad=None, #outgoing gradients

8 forward_times=1, #num of flowing in grads

9 pass_grads=None

10 ):

11 self.node = node

12 self.neighbors = neighbors if neighbors is not None else []

13 self.flowin_grads = flowin_grads if flowin_grads is not None else []

14 self.flowout_grad = flowout_grad

15 self.forward_times = forward_times

16 self.pass_grads = pass_grads if pass_grads is not None else {}

17

18nodes = get_nodes() #get computation nodes from ONNX model

19input2node = get_input2node() #get mapping from differential inputs to
computation node

20output2node = get_output2node()#get mapping from outputs to computation node

21backward_graph = defaultdict(GraphVertex)

22backward_graph[’backward_start’].neighbors.append(nodes[0])

23

24for node in nodes:

25 for iname in node.input:

26 if iname in output2node:

27 curr_nodes = input2node[iname]

28 next_node = output2node[iname]

29 for curr_node in curr_nodes:

30 for output in curr_node.output:

31 if output not in backward_graph:

32 backward_graph[output].node = curr_node

33 if next_node not in backward_graph[output].neighbors:

34 backward_graph[output].neighbors.append(next_node)

35for name in input2node:

36 if name in backward_graph:

37 if len(input2node[name]) > 1:

38 backward_graph[name].forward_times = len(input2node[name])

In Python Code List 1, a backward pass graph is first established to keep the
structures of forward pass. The information in each vertex contains the
computation node itself, neighbors of the current computation node in the
backward graph and the number of neighbors, in- or out-flowing gradients, and
the optional argument pass_grads to tell whether the input to the nodes is
differential with the model input as shown in GraphVertex in Python Code 1.
Some operators, such as Mul and Add, allow two inputs to differentiate with
the model input and others, such as MatMul and Gemm, allow up to two inputs to
vary when only one input differentiates with the model input. We need to
determine whether the out-flowing gradients of the current computation node
can be passed to its neighbors via pass_grads when building the backward graph
using Neural Network Parser. The meat of the algorithm for Parser is shown in
Python Code List 1. Function get_input2node establishes a mapping between the
differential inputs of a computation node and itself. The argument pass_grads
retains the information on whether the input of a computation node is
differential with the model input for some operators, such as Mul.
ONNXExplainer only passes gradients to the succeeding computation node with
the differential inputs in the backward pass.

##  Appendix B Gradients/Multipliers Computation

In this section, we provide gradients/multipliers computation for several
example operators.

  * •

Concat: The concatenation is a linear operator, which has no local gradient.
We only need to split and pass the incoming gradient to the successors in the
backward pass according to the portion of how the inputs to Concat are
concatenated in the forward pass.

  * •

Mul: The effect of multiplication can be either nonlinear or linear, depending
on whether both inputs to the multiplication operation are differentiable
w.r.t the model input. If so, we use RevealCancel Rule (Shrikumar, Greenside,
and Kundaje 2017) to compute adjusted gradients. Otherwise, we multiply the
incoming gradients with the input to the multiplication that is not
differentiable w.r.t the model input to compute outgoing gradients. In case of
broadcasting, the smaller input sums the incoming gradients over the axes that
this input is ”broadcast” across with the larger input of multiplication.

  * •

Matmul: The matrix multiplication is a linear operator. Its local gradient is
the transpose of the weight w.r.t. the input. Multiplying its local gradient
with incoming gradient gives the outgoing gradient to the successors in the
backward pass.

  * •

Conv: Convolution is a linear operator. We can use Conv to compute outgoing
gradients for the Conv. Let’s take 2D convolution as an example. Consider a
case where the input is $4\times 4$, the filter is $2\times 2$, and the stride
is $1\times 1$:

$\displaystyle input$
$\displaystyle=\begin{bmatrix}X_{00}&X_{01}&X_{02}&X_{03}\\\
X_{10}&X_{11}&X_{12}&X_{13}\\\ X_{20}&X_{21}&X_{22}&X_{23}\\\
X_{30}&X_{31}&X_{32}&X_{33}\end{bmatrix}$ (1) $\displaystyle filter$
$\displaystyle=\begin{bmatrix}F_{00}&F_{01}\\\ F_{10}&F_{11}\end{bmatrix},$
(2)

where $X_{ij}$ is $batch\times C_{in}$ and $F_{ij}$ is $C_{out}\times C_{in}$.
With valid padding, the output is $batch\times C_{out}\times 3\times 3$. In
back-propagation, the incoming gradient also should be $batch\times
C_{out}\times 3\times 3$. The computation of outgoing gradient for a 2D Conv
is to convolute the padded incoming gradient $grad_{in}$ using the transposed
and flipped filter $filter^{G}$ as follows:

$\displaystyle grad_{in}$ $\displaystyle=\begin{bmatrix}0&0&0&0&0\\\
0&G^{\prime}_{00}&G^{\prime}_{01}&G^{\prime}_{02}&0\\\
0&G^{\prime}_{10}&G^{\prime}_{11}&G^{\prime}_{12}&0\\\
0&G^{\prime}_{20}&G^{\prime}_{21}&G^{\prime}_{22}&0\\\ 0&0&0&0&0\end{bmatrix}$
(3) $\displaystyle filter^{G}$
$\displaystyle=\begin{bmatrix}F_{11}^{T}&F_{10}^{T}\\\
F_{01}^{T}&F_{00}^{T}\end{bmatrix}$ (4)

With strides more than one, plus zero-padding the incoming gradient, dilations
are used to control the spacing in the incoming gradient.

  * •

Sigmoid: The Sigmoid is a nonlinear operation. The computation of adjusted
gradients is denoted as following:

$\displaystyle\sigma(x)$ $\displaystyle=\frac{1}{1+e^{-x}}$ (5) $\displaystyle
grad^{*}$ $\displaystyle=\begin{dcases}\sigma(x)(1-\sigma(x))&\text{if
}x-r<1e-6\\\ \frac{\sigma(x)-\sigma(r)}{x-r}&\text{otherwise}\end{dcases}$ (6)

Where $\sigma(x)$ is the output of Sigmoid, $x$ is the input to some neurons
for the data being explained, and $r$ is the input to some neurons for
reference data. If $x-r<1e-6$ returns true, we use the original gradients of
Sigmoid. Otherwise, we use the multiplier for Sigmoid by the Rescale Rule
(Shrikumar, Greenside, and Kundaje 2017). Multiplying $grad^{*}$ with incoming
gradients can give us the outgoing gradients. Note that most of activation
functions use the same manner to obtain $grad^{*}$ except for Softmax which
uses RevealCancel Rule (Shrikumar, Greenside, and Kundaje 2017).

  * •

Maxpooling: Maxpooling is a nonlinear operation. We use the following to
define the adjusted gradients for it (Lundberg and Lee 2017).

$\displaystyle C$ $\displaystyle=\max(y_{x},y_{r})$ (7) $\displaystyle M_{x}$
$\displaystyle=(C-y_{r})\times grad_{in}$ (8) $\displaystyle M_{r}$
$\displaystyle=(y_{x}-C)\times grad_{in}$ (9) $\displaystyle grad^{*}_{out}$
$\displaystyle=\begin{dcases}0s&\text{if }x-r<1e-7\\\ \frac{\frac{\partial
M_{x}}{\partial x}+\frac{\partial M_{r}}{\partial
r}}{x-r}&\text{otherwise}\end{dcases}$ (10)

Where $x$ and $r$ are the inputs to maxpooling neurons for the data and
reference data, respectively, and $y_{x}$ and $y_{r}$ are outputs of these
neurons. $C$ is the cross maximum between $y_{x}$ and $y_{r}$ element-wise. We
multiply incoming gradients $grad_{in}$ with $C-y_{r}$ to attain cross
positioned incoming gradients $M_{x}$. Likewise, we have $M_{r}$. If $x-r$ is
less than $1e-7$, the outgoing gradients $grad^{*}_{out}$ are zeros.
Otherwise, we use the sum of positioned gradients of Maxpooling w.r.t $x$ and
$r$ divided by $x-r$ as outgoing gradients $grad^{*}_{out}$. The incoming
gradient is only passed back to neurons that achieve the maximum and all other
neurons have zero gradients when calculating gradients for maxpooling
operations. Note that the gradients accumulate if the same neurons achieve the
maximum in different pooling windows. GlobalMaxPooling is a special case of
Maxpooling whose pooling window size is the same as the input spatial.

On the other hand, Avgpooling is a linear operation. To compute gradients
w.r.t. input of an Avgpooling operation, the incoming gradients are
distributed equally to the the locations within the pooling window. The
gradients can accumulate if two pooling windows overlap. Similarly,
GlobalAvgPooling is a special case of Avgpooling whose pooling window size is
the same as the input spatial.

Comparison | VGG19 | ResNet50 | DenseNet201 | EfficientNetB0
---|---|---|---|---
OPT-ONNX versus SHAP[NON-TF] | 99.5% | 96.6% | 96.7% | 82.6%
OPT-TF versus SHAP[NON-TF] | 99.2% | 99.2% | 99.0% | 87.9%
OPT-ONNX versus NON-ONNX | 100% | 98.7% | 100% | 99.0%
Table 1: Numerical comparison of Shapley values between two different
explainers. We use $\lvert a-b\rvert<(atol+rtol\times\lvert b\rvert)$ to
compute the percentage of closeness of two sets of Shapley values, where $a$
and $b$ are two sets of Shapley values, $atol$ is the absolute tolerance
parameter, and $rtol$ is the relative tolerance parameter. Here, $atol$ is set
to $1.0e-8$ and $rtol$ is set to $1.0e-5$.

##  Appendix C Neural Networks Used in Benchmarks and Theoretical Analysis of
Computational Complexity and Memory Consumption in Explanation

NN | #para | depth | $\frac{\\#para}{depth}$ | jump type
---|---|---|---|---
VGG19(V19) | 143.7M | 19 | 7.56 | -
ResNet50(R50) | 25.6M | 107 | 0.24 | add
DenseNet201(D201) | 20.2M | 402 | 0.05 | concat
EfficientNetB0(EB0) | 5.3M | 132 | 0.04 | add & mul
Table 2: Four representative models. Depth counts the number of layers with
parameters.

Table 2 shows the four Neural Networks used in the benchmarking experiments.
The ratio $\frac{\\#para}{depth}$ is the rate between #para, the total number
of parameters, and depth, which can be considered as a indicator of
parallelizability of the neural network. The larger width, the easier for the
GPUs to parallelize to compute neural networks. From V19 to EB0 in Table 2,
the ratio becomes smaller and smaller. So is $\\#para$. Now let us discuss the
hypothetical memory consumption and computational complexity of the four NNs
in explaining data.

#### Memory Consumption

The memory consumption decreases by a factor of $2B$ in the forward pass of
the optimized approach because the optimized approach only consumes the image
being explained. Comparatively, SHAP consumes $2B$ images in the forward pass.
Theoretically, both methods need similar amounts of memory in the backward
pass. The difference is SHAP computes the intermediate outputs for the
reference images at run-time, but the optimized approach precomputes them for
the reference images when building the backward symbolic graph. In practice,
our implementations of backward pass might need more memory than SHAP because
users have no access to the intermediate outputs of forward pass which usually
are used to compute gradients in training (Abadi et al. 2016; Paszke et al.
2017, 2019b).

Figure 1: The estimated computational complexity of backbone networks in terms
of reference image size ($B$) per explanation image by counting TeraFLOPs
manually. The red lines represent the complexity using our optimization
approach and the green lines represent it using SHAP(non-optimization
approach).

#### Estimated Computational Complexity

Four backward symbolic graphs are built for V19, R50, D201, and EB0,
respectively. FLOP stands for floating point operation, which can be used to
measure the count of floating point operations of a model. A TeraFLOP means
one trillion ($10^{12}$) floating-point operations. TeraFLOPs are estimated
theoretically for both forward and backward symbolic graphs built by SHAP and
the optimization method for each neural network shown in Figure 1. It is found
that the optimization consistently decreases the complexity over reference
image size for all networks. The count of decreased TeraFLOPs to compute
Shapley values soars quickly for all networks when increasing reference
samples until it reaches a certain number of images.

##  Appendix D Numerical Comparison of Shapley Values between Explainers

We use four explainers (OPT-ONNX, NON-ONNX, OPT-TF, and NON-TF) to compute
Shapley values for 500 images in test dataset (Models in ONNX and TensorFlow
share same weights in inference.). To verify whether our methods have close
Shapley values with SHAP (TensorFlow), we compare Shapley values between
optimized and non-optimized explainers numerically. The results are shown in
Table 1. Overall, the Shapley values by optimization method are closely
matched with Shapley values by SHAP.

##  Appendix E Latency Analysis

Figure 2: Latency Comparison[FP16] between Optimization and Non-
optimization/SHAP using two Frameworks (TensorFlow, and PyTorch) on Machine B
with GPU. We use 65 and 100 for NON-TF and NON-PT for DenseNet201 because of
memory limitation.

We also run benchmarks using half precision floating-point on one V100 GPU.
Figure 2 shows the latency over the number of reference images for four models
in two frameworks. TensorFlow models requires a great amount of time to warm
up the model. OPT-TF gains much more acceleration than OPT-PT.

Figure 3: Latency Comparison[FP16] between Optimization and Non-optimization
ONNXExplainer on Machine B with GPU. We use 90 for D201.  Figure 4: Latency
Comparison[FP16] between Optimization and Non-optimization ONNXExplainer on a
different Machine with V100 GPU. We use 90 for D201.

Figure 3 shows the latency in ONNX for four models. Surprisingly, there are
some spiking latency points both in OPT-ONNX and NOT-ONNX for R50, D201, and
EB0. This phenomenon might be a systematic reaction of hardware, software,
parallel optimization, and ONNX implementations, which needs future research.
Excluding the spiking points, we can find that OPT-ONNX outperforms NON-ONNX
in terms of latency. We run the same benchmarking experiments on a different
Machine with V100 GPU and the Nvidia Driver (455.23.05) and CUDA version
(11.1) are different from Machine B in ONNX ecosystem. The spikes are also
found in R50, D201, and EB0 as in Figure 4. In the new machine, the spiking
points occur with different input sizes than the machine B. Interestingly, in
addition to the increasing number of spikes seen in EB0 in Figure 4, the
spikes we observe are frequently lower on optimized ONNXExplainer than non-
optimized ONNXExplainer.