# Rethinking Stability for Attribution-based Explanations

Chirag Agarwal1, Nari Johnson2, Martin Pawelczyk3, Satyapriya Krishna4,
Eshika Saxena4, Marinka Zitnik4 & Himabindu Lakkaraju4
1 Media and Data Science Research Lab, Adobe
2 Carnegie Mellon University
3 University of Tübingen
4 Harvard University

###### Abstract

As attribution-based explanation methods are increasingly used to establish
model trustworthiness in high-stakes situations, it is critical to ensure that
these explanations are stable, e.g., robust to infinitesimal perturbations to
an input. However, previous works have shown that state-of-the-art explanation
methods generate unstable explanations. Here, we introduce metrics to quantify
the stability of an explanation and show that several popular explanation
methods are unstable. In particular, we propose new Relative Stability metrics
that measure the change in output explanation with respect to change in input,
model representation, or output of the underlying predictor. Finally, our
experimental evaluation with three real-world datasets demonstrates
interesting insights for seven explanation methods and different stability
metrics.

##  1 Introduction

With machine learning (ML) models being increasingly employed in high-stakes
domain such as criminal justice, finance, and healthcare, it is essential to
ensure that the relevant stakeholders understand these models’ decisions.
However, existing approaches to explain the predictions of complex machine
learning (ML) models suffer from several critical shortcomings. Recent works
have shown that explanations generated using attribution-based methods are not
stable (Ghorbani et al., 2019; Slack et al., 2020; Dombrowski et al., 2019;
Adebayo et al., 2018; Alvarez-Melis, Jaakkola, 2018; Bansal et al., 2020),
e.g. that infinitesimal perturbations to an input can result in substantially
different explanations.

Existing metrics (Alvarez-Melis, Jaakkola, 2018) measure the change in
explanation only with respect to the input perturbations, e.g., they only
assume black-box access to the predictive model, and don’t leverage
potentially meaningful information such as the model’s internal
representations to evaluate stability. To address these limitations of
existing stability metrics, we propose Relative Stability that measures the
change in output explanation with respect to the behavior of the underlying
predictive model (Section 3.3). Finally, we present extensive theoretical and
empirical analysis (Section 4.2) for comparing the stability of seven state-
of-the-art explanation methods using multiple real-world datasets.

##  2 Related Works

This paper draws from two main areas of prior work: 1) attribution-based
explanation methods, and 2) stability analysis of explanations.

Attribution-based Explanation Methods. While a variety of approaches have been
proposed to explain model decisions for classifiers, our work focuses on
_local feature attribution explanations_ , which measure the contribution of
each feature to the model’s prediction on a point. In particular, we study two
broad types of feature attribution explanations: gradient-based and
approximation-based. Gradient-based feature attribution methods like
VanillaGrad (Simonyan et al., 2014), SmoothGrad (Smilkov et al., 2017),
Integrated Gradients (Sundararajan et al., 2017), and Gradient$\times$Input
(Shrikumar et al., 2017) leverage model gradients to quantify how a change in
each feature would affect the model’s prediction. Approximation-based methods
like LIME (Ribeiro et al., 2016), SHAP (Lundberg, Lee, 2017), Anchors (Ribeiro
et al., 2018), BayesLIME, and BayesSHAP (Slack et al., 2021) leverage
perturbations of individual inputs to construct a local approximation model
from which feature attributions are derived.

Explanation Stability. Recent works have formalized desirable properties for
feature attribution explanations (Agarwal et al., 2022). Our work specifically
focuses on the _stability_ of explanations. Alvarez-Melis, Jaakkola (2018)
argued that “similar inputs should lead to similar explanations” and is the
first work to formalize a metric to measure the stability of local explanation
methods. We highlight potential issues with this stability metric that
measures stability only w.r.t. the change in _input_.

##  3 Stability Analysis for Evaluating Explanations

###  3.1 Notation and Preliminaries

Machine Learning Model. Given a feature domain $\mathcal{X}$ and label domain
$\mathcal{Y}$, we denote a classification model $f{:}\leavevmode\nobreak\
\mathcal{X}{{\,\rightarrow\,}}\mathcal{Y}$ that maps a set of features
${\mathbf{x}}{\in}\mathcal{X}$ to labels ${\mathbf{y}}{\in}\mathcal{Y}$, where
${\mathbf{x}}\in\mathbb{R}^{d}$ is a $d$-dimensional feature vector,
${\mathbf{y}}\in\\{0,1,\dots,\text{C}\\}$ where C is the total number of
classes in the dataset. We use
${\mathbf{X}}=\\{{\mathbf{x}}_{1},{\mathbf{x}}_{2},\dots,{\mathbf{x}}_{N}\\}$
to denote all the $N$ instances in the dataset. In addition, we define
$f({\mathbf{x}}){=}\sigma(h({\mathbf{x}}))$, where
$h:\mathcal{X}{{\,\rightarrow\,}}\mathbb{R}$ is a scoring function (e.g.,
logits) and $\sigma:\mathbb{R}{{\,\rightarrow\,}}\mathcal{Y}$ is an activation
function that maps output logit scores to discrete labels. Finally, for a
given input ${\mathbf{x}}$, the output predicted class label is:
$\hat{y}_{{\mathbf{x}}}{=}\operatorname*{arg\,max}_{c}f({\mathbf{x}})$. We
assume access to the gradients and intermediate representations of model $f$.

Explainability Methods. An attribution-based explanation method $\mathcal{E}$
generates an explanation $\mathbf{e}_{{\mathbf{x}}}\in\mathbb{R}^{d}$ to
explain model prediction $f({\mathbf{x}})$. To calculate our stability
metrics, we generate perturbations ${\mathbf{x}}^{\prime}$ by adding
infinitesimal noise to ${\mathbf{x}}$, and denote their respective explanation
as $\mathbf{e}_{{\mathbf{x}}^{\prime}}$.

###  3.2 Existing Definition and Problems

Alvarez-Melis, Jaakkola (2018) formalize the first stability metric for local
explanation methods, arguing that explanations should be robust to local
perturbations of an input. To evaluate the stability of an explanation for
instance $\mathbf{x}$, perturbed instances $\mathbf{x^{\prime}}$ are generated
by adding infinitesimally small noise to the clean instance $\mathbf{x}$ such
that $\hat{y}_{\mathbf{x}}=\hat{y}_{\mathbf{x^{\prime}}}$:

$\displaystyle\text{S}(\mathbf{x},\mathbf{x^{\prime}},\mathbf{e}_{\mathbf{x}},\mathbf{e}_{\mathbf{x^{\prime}}})=\max_{\mathbf{x^{\prime}}}\frac{||\leavevmode\nobreak\
\mathbf{e}_{\mathbf{x}}-\mathbf{e}_{\mathbf{x^{\prime}}}\leavevmode\nobreak\
||}{||\leavevmode\nobreak\ \mathbf{x}-\mathbf{x^{\prime}}\leavevmode\nobreak\
||},\leavevmode\nobreak\ \forall\mathbf{x^{\prime}}\leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\
\mathbf{x^{\prime}}\in\mathcal{N}_{\mathbf{x}};\leavevmode\nobreak\
\hat{y}_{\mathbf{x}}=\hat{y}_{\mathbf{x^{\prime}}}$ (1)

where $\mathcal{N}_{\mathbf{x}}$ is a neighborhood of instances
$\mathbf{x}^{\prime}$ similar to $\mathbf{x}$, and $\mathbf{e}_{\mathbf{x}}$
and $\mathbf{e}_{\mathbf{x^{\prime}}}$ denote the explanations corresponding
to instances $\mathbf{x}$ and $\mathbf{x}^{\prime}$, respectively. For each
point ${\mathbf{x}}^{\prime}$, the stability ratio in Equation 1 measures how
the output explanation varies with respect to the change in the _input_.
Because the neighborhood of instances $\mathcal{N}_{\mathbf{x}}$ are sampled
to be similar to the original instance $\mathbf{x}$, the authors argue that
points that are similar should have similar model explanations, e.g., we
desire the ratio in Equation 1 to be close to $1$ (Alvarez-Melis et al.,
2021). This stability definition relies on the point-wise neighborhood-based
local Lipschitz continuity of the explanation method
$\mathbf{e}_{{\mathbf{x}}}$ around $\mathbf{x}$.

Figure 1: Decision boundaries and embeddings of a two-layer neural network
predictor $f$ with 100 units trained on the circles dataset. The heatmaps
(left and middle column) shows the models’ confidence for the positive-class
(in blue), test set examples ${\mathbf{x}}$ ( , ), and a set of perturbed
samples ${\mathbf{x}}^{\prime}$ ( ). While all perturbed samples
$\mathbf{x}^{\prime}$ are predicted to the same class as
$\mathbf{x}^{\prime}$, the embeddings (right column) for some
$\mathbf{x}^{\prime}$ are far from the embeddings of $\mathbf{x}^{\prime}$ and
similar to the embeddings of Class 0, highlighting the need of incorporating
the model behavior using its internal embeddings (Equations 3,5).

Problems. We note two key problems with the existing stability definition: i)
it only assumes black-box access to the prediction model $f$, and does not
leverage potentially meaningful information such as the model’s internal
representations for evaluating stability; and ii) it implicitly assumes that
$f$ has the same _behavior_ on inputs ${\mathbf{x}}$ and
${\mathbf{x}}^{\prime}$ that are similar. While this may be the case for
underlying prediction models that are smooth or robust, this assumption may
not hold in a large number of cases. In Figure 1, we discuss a toy example
where perturbed samples $\mathcal{N}_{{\mathbf{x}}}$ have drastically
different intermediate representations than the original point ${\mathbf{x}}$.
Note that since the goal of an explanation is to faithfully and accurately
represent the behavior of the underlying prediction model (Agarwal et al.,
2022), we argue that an explanation method _should_ vary for points
${\mathbf{x}}$ and ${\mathbf{x}}^{\prime}$ where the prediction model’s
behavior differs. Thus, we argue for the inclusion of new stability metrics
that measure how much explanations vary with respect to the behavior of the
underlying prediction model.

###  3.3 Proposed metric: Relative Stability

To address the aforementioned challenges, we propose Relative Stability that
leverages model information to evaluate the stability of an explanation with
respect to the change in the a) input data, b) intermediate representations,
and c) output logits of the underlying prediction model.

a) Relative Input Stability. We extend the stability metric in Equation 1 and
define Relative Input Stability that measures the relative distance between
explanations $\mathbf{e}_{{\mathbf{x}}}$ and
$\mathbf{e}_{{\mathbf{x}}^{\prime}}$ with respect to the distance between the
two inputs ${\mathbf{x}}$ and ${\mathbf{x}}^{\prime}$.

$\displaystyle\text{RIS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})$
$\displaystyle=\max_{{\mathbf{x}}^{\prime}}\frac{||\frac{(\mathbf{e}_{{\mathbf{x}}}-\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{\max(||\frac{({\mathbf{x}}-{\mathbf{x}}^{\prime})}{{\mathbf{x}}}||_{p},\epsilon_{min})},\leavevmode\nobreak\
\forall{\mathbf{x}}^{\prime}\leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\
{\mathbf{x}}^{\prime}\in\mathcal{N}_{{\mathbf{x}}};\leavevmode\nobreak\
\hat{y}_{{\mathbf{x}}}=\hat{y}_{{\mathbf{x}}^{\prime}}$ (2)

where the numerator of the metric measures the $\ell_{p}$ norm of the _percent
change_ of explanation $\mathbf{e}_{{\mathbf{x}}^{\prime}}$ on the perturbed
instance ${\mathbf{x}}^{\prime}$ with respect to the explanation
$\mathbf{e}_{{\mathbf{x}}}$ on the original point ${\mathbf{x}}$, the
denominator measures the $\ell_{p}$ norm between (normalized) inputs
${\mathbf{x}}$ and ${\mathbf{x}}^{\prime}$ and the $\max$ term prevents
division by zero in cases when norm
$||\frac{({\mathbf{x}}-{\mathbf{x}}^{\prime})}{{\mathbf{x}}}||_{p}$ is less
than some small $\epsilon_{min}{>}0$. Here, we use the percent change from the
explanation on the original point to the explanation on the perturbed instance
in contrast to the absolute difference between the explanations (as in
Equation 1) to enable comparison across different attribution-based
explanation methods that have vastly different ranges or magnitudes.
Intuitively, one can expect similar explanations for points that are similar –
the percent change in explanations (numerator) should be _small_ for points
that are close, or have a _small_ $l_{p}$ norm (denominator). Note that the
metric in Equation 2 measures instability of an explanation and higher values
indicate higher instability.

b) Relative Representation Stability. Previous stability definitions in
Equation 1-2 do not cater to cases where the model uses different logic paths
(e.g., activating different neurons in a deep neural network) to predict the
same label for the original and perturbed instance. In addition, past works
have presented empirical evidence that the intermediate representations of a
model are related to the underlying behavior or reasoning of the model
(Agarwal et al., 2021). Thus, we leverage the internal features or
representation learned by the underlying model and propose Relative
Representation Stability as:

$\displaystyle\text{RRS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})$
$\displaystyle=\max_{{\mathbf{x}}^{\prime}}\frac{||\frac{(\mathbf{e}_{{\mathbf{x}}}-\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{\max(||\frac{(\mathcal{L}_{{\mathbf{x}}}{-}\mathcal{L}_{{\mathbf{x}}^{\prime}})}{\mathcal{L}_{{\mathbf{x}}}}||_{p},\epsilon_{min})},\leavevmode\nobreak\
\forall{\mathbf{x}}^{\prime}\leavevmode\nobreak\ \leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
{\mathbf{x}}^{\prime}\in\mathcal{N}_{{\mathbf{x}}};\leavevmode\nobreak\
\leavevmode\nobreak\ \hat{y}_{{\mathbf{x}}}{=}\hat{y}_{{\mathbf{x}}^{\prime}}$
(3)

where $\mathcal{L}(\cdot)$ denotes the internal model representation, e.g.,
output embeddings of hidden layers, and $\delta$ is an infinitesimal constant.
Due to insufficient knowledge about the data generating mechanism, we follow
the perturbation mechanisms described above to generate perturbed samples
${\mathbf{x}}^{\prime}$ but use additional checks to ensure that for certain
perturbations the model behaves similar to its training behavior. For any
given instance ${\mathbf{x}}$, we generate $m$ local perturbed samples such
that $||{\mathbf{x}}-{\mathbf{x}}^{\prime}||_{p}\leq\epsilon$, and
$\hat{y}_{{\mathbf{x}}}{=}\hat{y}_{{\mathbf{x}}^{\prime}}$. For every
perturbed sample, we calculate the difference in their respective explanations
and using Equation 3 calculate the relative stability of an explanation. Note
that, as before, the metric in Equation 3 measures instability of an
explanation and higher values indicate higher instability.

Finally, we show that the Relative Input Stability can be bounded using the
Lipschitzness of the underlying model. In particular, we proof that RIS is
upper bounded by a product of the Lipschitz constant $L_{1}$ of the
intermediate model layer (assuming a neural network classifier) and our
proposed Relative Representation Stability. See Appendix A for the complete
proof.

$\displaystyle\text{RIS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})<\lambda_{1}L_{1}\times\leavevmode\nobreak\
\text{RRS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})$
(4)

c) Relative Output Stability. Note that Relative Representation Stability
assumes that the underlying ML model is white-box, i.e., explanation method
has access to the internal model knowledge. Hence, for black-box ML models we
define Relative Output Stability as:

$\displaystyle\text{ROS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})$
$\displaystyle=\max_{{\mathbf{x}}^{\prime}}\frac{||\frac{(\mathbf{e}_{{\mathbf{x}}}-\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{\max(||h({\mathbf{x}}){-}h({\mathbf{x}}^{\prime})||_{p},\epsilon_{min})},\leavevmode\nobreak\
\forall{\mathbf{x}}^{\prime}\leavevmode\nobreak\ \leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
{\mathbf{x}}^{\prime}\in\mathcal{N}_{{\mathbf{x}}};\leavevmode\nobreak\
\leavevmode\nobreak\ \hat{y}_{{\mathbf{x}}}{=}\hat{y}_{{\mathbf{x}}^{\prime}}$
(5)

where $h({\mathbf{x}})$ and $h({\mathbf{x}}^{\prime})$ are the output logits
for ${\mathbf{x}}$ and ${\mathbf{x}}^{\prime}$, respectively. Again, we proof
that RRS is upper bounded by a product of the Lipschitz constant $L_{2}$ of
the output model layer and our proposed Relative Output Stability. See
Appendix A for the complete proof.

$\displaystyle\text{RRS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})<\lambda_{2}L_{2}\leavevmode\nobreak\
\times\leavevmode\nobreak\
\text{ROS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})$
(6)

##  4 Experiments

To demonstrate the utility of relative stability, we systematically compare
and evaluate the stability of seven explanation methods using three real-world
datasets using equations defined in Section 3. Further, we show that, in
contrast to relative input stability, relative representation and output
stability better captures the stability of the underlying black-box model.

###  4.1 Datasets and Experimental Setup

Datasets. We use real-world structured datasets to empirically analyze the
stability behavior of explanation methods and consider 3 benchmark datasets
from high-stakes domains: i) the German Credit dataset (Dua, Graff, 2017)
which has records of 1,000 clients in a German bank. The downstream task is to
classify clients into good or bad credit risks, ii) the COMPAS dataset (Mattu
et al., 2016) which has records of 18,876 defendants who got released on bail
at the U.S state courts during 1990-2009. The dataset comprises of features
representing past criminal records and demographics of the defendants and the
goal is to classify them into bail or no bail, and iii) the Adult dataset
(Dua, Graff, 2017) which has records of 48,842 individuals including
demographic, education, employment, personal, and financial features. The
downstream task is to predict whether an individual’s income exceeds $50K per
year.

Predictors. We train logistic regression (LR) and artificial neural network
(ANN) as our predictive models. Details in Appendix B.

Explanation methods. We evaluate seven attribution-based explanation methods,
including VanillaGrad (Simonyan et al., 2014), Integrated Gradients
(Sundararajan et al., 2017), SmoothGrad (Smilkov et al., 2017),
Input$\times$Gradients (Shrikumar et al., 2017), LIME (Ribeiro et al., 2016),
and SHAP (Lundberg, Lee, 2017). Following Agarwal et al. (2022), we also
include a random assignment of importance as a control setting. Details on
implementation and hyperparameter selection for the explanation methods are in
Appendix B.

Setup. For each dataset and predictor, we: (1) train the prediction model on
the respective dataset; (2) randomly sample $100$ points from the test set;
(3) generate $50$ perturbations for each point in the test set; (4) generate
explanations $\mathbf{e}_{{\mathbf{x}}^{\prime}}$ for each test set point and
its perturbations using seven explanation methods; and (5) evaluate the
stability of the explanations for these test points using all stability
metrics (Equations 2,3,5).

Figure 2: Theoretical upper bounds for the (log) relative input stability
(RIS) computed using the right-hand-side of Equation 4 across seven
explanation methods for an ANN predictor trained on Adult dataset. Results
show that RIS is upper bounded by the product of $L_{1}$ and RRS (relative
representation stability), where $L_{1}$ is the Lipschitz constant between the
input and hidden layer of the ANN model. Results for the Compas and German
dataset are shown in Appendix 5.

###  4.2 Results

Empirically verifying our theoretical bound. We empirically evaluated our
theoretical bounds by computing the LHS of Equation 4 for all seven
explanation methods. Results in Figure 2 illustrate the empirical and
theoretical bounds for the Relative Input Stability, confirming that none of
our theoretical bounds are violated. In addition, we observe that, on average
across all explanation methods, our upper bounds are tight with the mean
theoretical bounds being 233% higher than that of the empirical values.
Similar results are found for other datasets in Appendix 5.

(a) Adult dataset

(b) Compas dataset

(c) German Credit dataset

Figure 3: Empirically calculated log stability of relative stability variants
(Equations 2-5) across seven explanation methods. Results on the Adult (a),
Compas (b), and German (c) dataset trained with ANN predictor show that
SmoothGrad generates the most stable explanation across RRS and ROS variants.
Results for all datasets trained on Logistic Regression models are shown in
Appendix 4.

Evaluating the stability of explanation methods. We compare the stability of
explanation methods by computing instability using all three variants as
described in Section 3.3. Results in Figure 3 show that the median instability
of all explanation methods using Relative Input Stability (Figure 3; blue) are
lower than that for the Representation (Figure 3; green) and Output Stability
(Figure 3; orange) because the relative input stability (Equation 2) scores
are highly influenced by the input differences
(${\mathbf{x}}-{\mathbf{x}}^{\prime}$), i.e., the median RIS scores across all
explanation methods are always lower than RRS and ROS. Finally, we observe
that while no explanation method is completely stable, on average across all
datasets and representation stability variants, the SmoothGrad explanation
method generates the most stable explanation and outperforms other methods by
12.7%.

##  5 Conclusion

We introduce Relative Stability metrics that measure the change in output
explanation with respect to the behavior of the underlying predictive model.
To this end, we analyze the stability performance of seven state-of-the-art
explanation methods using multiple real-world datasets and predictive models.
Our theoretical and empirical analysis demonstrate that representation and
output stability indicates that SmoothGrad explanation method generates the
most stable explanation. We believe that our work is an important step towards
developing a broader set of evaluation metrics that incorporate the behavior
of the underlying prediction model.

## References

  * Adebayo et al. (2018) Adebayo Julius, Gilmer Justin, Muelly Michael, Goodfellow Ian, Hardt Moritz, Kim Been.  Sanity checks for saliency maps  // NeurIPS. 2018.
  * Agarwal et al. (2021) Agarwal Chirag, Lakkaraju Himabindu, Zitnik Marinka.  Towards a unified framework for fair and stable graph representation learning  // UAI. 2021.
  * Agarwal et al. (2022) Agarwal Chirag, Zitnik Marinka, Lakkaraju Himabindu.  Probing GNN Explainers: A Rigorous Theoretical and Empirical Analysis of GNN Explanation Methods  // arXiv. 2022.
  * Alvarez-Melis, Jaakkola (2018) Alvarez-Melis David, Jaakkola Tommi S.  On the robustness of interpretability methods  // ICML Workshop on Human Interpretability in Machine Learning. 2018.
  * Alvarez-Melis et al. (2021) Alvarez-Melis David, Kaur Harmanpreet, II Hal Daum ̵́e, Wallach Hanna, Vaughan Jennifer Wortman.  From Human Explanation to Model Interpretability: A Framework Based on Weight of Evidence  // HCOMP. 2021.
  * Bansal et al. (2020) Bansal Naman, Agarwal Chirag, Nguyen Anh.  Sam: The sensitivity of attribution methods to hyperparameters  // CVPR. 2020.
  * Dombrowski et al. (2019) Dombrowski Ann-Kathrin, Alber Maximilian, Anders Christopher J, Ackermann Marcel, Müller Klaus-Robert, Kessel Pan.  Explanations can be manipulated and geometry is to blame  // arXiv. 2019.
  * Dua, Graff (2017) Dua Dheeru, Graff Casey.  UCI Machine Learning Repository. 2017.
  * Ghorbani et al. (2019) Ghorbani Amirata, Abid Abubakar, Zou James.  Interpretation of neural networks is fragile  // AAAI. 2019.
  * Gouk et al. (2021) Gouk Henry, Frank Eibe, Pfahringer Bernhard, Cree Michael J.  Regularisation of neural networks by enforcing lipschitz continuity  // Machine Learning. 2021.
  * Lundberg, Lee (2017) Lundberg Scott M, Lee Su-In.  A unified approach to interpreting model predictions  // NeurIPS. 2017.
  * Mattu et al. (2016) Mattu S, Kirchner L, Angwin J.  How we analyzed the COMPAS recidivism algorithm.  // ProPublica. 2016.
  * Ribeiro et al. (2016) Ribeiro Marco Tulio, Singh Sameer, Guestrin Carlos.  ” Why should i trust you?” Explaining the predictions of any classifier  // KDD. 2016.
  * Ribeiro et al. (2018) Ribeiro Marco Tulio, Singh Sameer, Guestrin Carlos.  Anchors: High-precision model-agnostic explanations  // AAAI. 2018.
  * Shrikumar et al. (2017) Shrikumar Avanti, Greenside Peyton, Kundaje Anshul.  Learning important features through propagating activation differences  // ICML. 2017.
  * Simonyan et al. (2014) Simonyan Karen, Vedaldi Andrea, Zisserman Andrew.  Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps  // ICLR. 2014.
  * Slack et al. (2021) Slack Dylan, Hilgard Anna, Singh Sameer, Lakkaraju Himabindu.  Reliable post hoc explanations: Modeling uncertainty in explainability  // NeurIPS. 2021.
  * Slack et al. (2020) Slack Dylan, Hilgard Sophie, Jia Emily, Singh Sameer, Lakkaraju Himabindu.  How can we fool LIME and SHAP? Adversarial Attacks on Post hoc Explanation Methods  // AIES. 2020.
  * Smilkov et al. (2017) Smilkov Daniel, Thorat Nikhil, Kim Been, Viégas Fernanda B., Wattenberg Martin.  SmoothGrad: removing noise by adding noise  // ICML Workshop on Visualization for Deep Learning. 2017.
  * Sundararajan et al. (2017) Sundararajan Mukund, Taly Ankur, Yan Qiqi.  Axiomatic attribution for deep networks  // ICML. 2017\.

##  Appendix A Theoretical Interpretation

Prior works have shown that commonly used artificial neural network (ANN)
models comprise of linear and activation layers which satisfy Lipschitz
continuity (Gouk et al., 2021). Let us consider a 2-layer ANN model $f$, where
$h_{1}(\cdot)$ and $h_{2}(\cdot)$ represent the outputs of the first and
second hidden layers, respectively. For a given input ${\mathbf{x}}$ and its
perturbed counterpart ${\mathbf{x}}^{\prime}$, we can write the Lipschitz form
for the first hidden layer as:

$\displaystyle||\leavevmode\nobreak\
h_{1}({\mathbf{x}})-h_{1}({\mathbf{x}}^{\prime})\leavevmode\nobreak\
||_{p}\leq L_{1}\leavevmode\nobreak\ ||\leavevmode\nobreak\
{\mathbf{x}}-{\mathbf{x}}^{\prime}\leavevmode\nobreak\ ||_{p},$ (7)

where $L$ is the Lipschitz constant of the hidden layer $h_{1}(\cdot)$. Taking
the reciprocal of Equation 7, we get:

$\displaystyle\frac{1}{||\leavevmode\nobreak\
h_{1}({\mathbf{x}})-h_{1}({\mathbf{x}}^{\prime})\leavevmode\nobreak\
||_{p}}>\frac{1}{L_{1}}\leavevmode\nobreak\ \frac{1}{||\leavevmode\nobreak\
{\mathbf{x}}-{\mathbf{x}}^{\prime}\leavevmode\nobreak\ ||_{p}},$ (8)

Multiplying both sides with $||\leavevmode\nobreak\
\frac{(\mathbf{e}_{{\mathbf{x}}}{-}\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}$,
we get:

$\displaystyle\frac{||\leavevmode\nobreak\
\frac{(\mathbf{e}_{{\mathbf{x}}}{-}\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{||\leavevmode\nobreak\
h_{1}({\mathbf{x}})-h_{1}({\mathbf{x}}^{\prime})\leavevmode\nobreak\
||_{p}}>\frac{1}{L_{1}}\leavevmode\nobreak\ \frac{||\leavevmode\nobreak\
\frac{(\mathbf{e}_{{\mathbf{x}}}{-}\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{||\leavevmode\nobreak\
{\mathbf{x}}-{\mathbf{x}}^{\prime}\leavevmode\nobreak\ ||_{p}},$ (9)

With further simplifications, we get:

$\displaystyle\frac{||\leavevmode\nobreak\
\frac{(\mathbf{e}_{{\mathbf{x}}}{-}\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{||h_{1}({\mathbf{x}})||_{p}||\frac{h_{1}({\mathbf{x}})-h_{1}({\mathbf{x}}^{\prime})}{h_{1}({\mathbf{x}})}||_{p}}>\frac{1}{L_{1}}\leavevmode\nobreak\
\frac{||\leavevmode\nobreak\
\frac{(\mathbf{e}_{{\mathbf{x}}}{-}\mathbf{e}_{{\mathbf{x}}^{\prime}})}{\mathbf{e}_{{\mathbf{x}}}}||_{p}}{||{\mathbf{x}}||_{p}||\frac{{\mathbf{x}}-{\mathbf{x}}^{\prime}}{{\mathbf{x}}}||_{p}}$
(10)

For a given ${\mathbf{x}}^{\prime}$ and representations from model layer
$h_{1}(\cdot)$, using Equations 2-3, we get:

$\displaystyle\frac{\text{RRS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})}{||h_{1}({\mathbf{x}})||_{p}}>\frac{1}{L_{1}}\leavevmode\nobreak\
\frac{\text{RIS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})}{||{\mathbf{x}}||_{p}},$
(11)
$\displaystyle\Rightarrow\text{RIS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})<\big{(}L_{1}\frac{||h_{1}({\mathbf{x}})||_{p}}{||{\mathbf{x}}||_{p}}\big{)}\leavevmode\nobreak\
\times\leavevmode\nobreak\
\text{RRS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}}),$
(12)

where we find that the Relative Input Stability score is upper bounded by
$L_{1}$ times
$\lambda_{1}{=}\frac{||h_{1}({\mathbf{x}})||_{p}}{||{\mathbf{x}}||_{p}}$ times
the Relative Representation Stability score. Finally, we can also extend the
above analysis by substituting $h_{1}(\cdot)$ with the output logit layer
$h_{2}(\cdot)$ and show that the same relation holds for Relative Output
Stability:

$\displaystyle\text{RRS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}})<\lambda_{2}L_{2}\leavevmode\nobreak\
\times\leavevmode\nobreak\
\text{ROS}({\mathbf{x}},{\mathbf{x}}^{\prime},\mathbf{e}_{{\mathbf{x}}},\mathbf{e}_{{\mathbf{x}}^{\prime}}),$
(13)

where $\lambda_{2}=||h_{1}({\mathbf{x}})||_{p}$.

##  Appendix B Implementation Details

Predictors. We train logistic regression (LR) and artificial neural network
(ANN) models. Details in Appendix B. The ANN models have 1 hidden layer of
width $100$ followed by a ReLU activation function and the output Softmax
layer.

Predictor Training. To train all predictive models, we used a 80-10-10 train-
test-validation split. We used the RMSProp optimizer with learning rate
$2e-03$, the binary cross entropy loss function, and batchsize $32$. We
trained for $100$ epochs and selected the model at the epoch with the highest
validation set accuracy as the final prediction model to be explained in our
experiments.

Explanation Method Implementations. We used existing public implementations of
all explanation methods in our experiments. We used the following captum
software package classes: i) captum.attr.Saliency for VanillaGrad; ii)
captum.attr.IntegratedGradients for IntegratedGradients; iii)
captum.attr.NoiseTunnel; iv) captum.attr.Saliency for SmoothGrad; v)
captum.attr.InputXGradient for Gradients$\times$Input; and vi)
captum.attr.KernelShap for SHAP. We use the authors’ LIME python package for
LIME.

Metric hyperparameters. For all metrics, we generate a neighborhood
$\mathcal{N}_{{\mathbf{x}}}$ of size $50$ for each point ${\mathbf{x}}$. The
neighborhood points were generated by perturbing the clean sample
${\mathbf{x}}$ with noise from $\mathcal{N}({\mathbf{x}},0.05)$. For data sets
with with discrete binary inputs we used independent Bernoulli random
variables for the pertubations: for each discrete dimension, we replaced the
original values with those that were drawn from a Bernoulli distribution with
parameter $p=0.03$. Choosing a small $p$ ensures that only a small fraction of
samples are perturbed to reduce the likelihood of sampling an out-of-
distribution point. For internal model representations
$\mathcal{L}_{{\mathbf{x}}}$ we use the pre-softmax input linear layer output
embedding for the LR models, and the pre-ReLU output embedding of the first
hidden layer for the ANN.

Explanation Method | Hyperparameter | Value
---|---|---
| n_samples | $1000$
LIME | kernel_width | $0.75$
| std | $0.05$
SHAP | n_samples | $500$
SmoothGrad | std | 0.05
Integrated Gradients | baseline | train data means
Random Baseline | attributions from $\mathcal{N}(0,1)$ |
Table 1: Hyperparameters used for explanation methods. For hyperparameters not
listed, we used their package defaults.

(a) Adult dataset

(b) Compas dataset

(c) German dataset

Figure 4: Empirically calculated log stability of all three relative stability
variants (Equations 2-5) across seven explanation methods. Results on the
Adult dataset trained with Logistic Regression predictor show that SmoothGrad
generates the most stable explanation across representation and output
stability variants.

(a) Compas dataset

(b) German credit dataset

Figure 5: Theoretical upper bounds for the (log) relative input stability
(RIS) computed using the right-hand-side of Equation 4 across seven
explanation methods for an ANN predictor trained on the Compas and German
credit datasets. Results show that RIS is upper bounded by the product of
$L_{1}$ and RRS (relative representation stability), where $L_{1}$ is the
Lipschitz constant between the input and hidden layer of the ANN model.