# How Consistent are Clinicians?
Evaluating the Predictability of Sepsis
Disease Progression with Dynamics Models

Unnseo Park, Venkatesh Sivaraman & Adam Perer
Human-Computer Interaction Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Reinforcement learning (RL) is a promising approach to generate treatment
policies for sepsis patients in intensive care. While retrospective evaluation
metrics show decreased mortality when these policies are followed, studies
with clinicians suggest their recommendations are often spurious. We propose
that these shortcomings may be due to lack of diversity in observed actions
and outcomes in the training data, and we construct experiments to investigate
the feasibility of predicting sepsis disease severity changes due to clinician
actions. Preliminary results suggest incorporating action information does not
significantly improve model performance, indicating that clinician actions may
not be sufficiently variable to yield measurable effects on disease
progression. We discuss the implications of these findings for optimizing
sepsis treatment.

##  1 Introduction

Sepsis is a leading cause of death in hospitals, and there is currently little
clinical consensus around best practices for treatment (Centers for Disease
Control and Prevention, 2021). Several recent works have applied reinforcement
learning (RL) methods in efforts to support clinicians’ decision-making on
sepsis patients in the intensive care unit (ICU). While these algorithms have
shown promise when evaluated using off-policy policy evaluation (OPE) methods,
they have also been critiqued for recommending incorrect and even dangerous
treatment plans, particularly for more severely ill patients (Jeter et al.,
2019; Sivaraman et al., 2023). Due to ethical concerns around prospectively
evaluating these models, it is currently an open question whether it is
possible to derive policies from public observational datasets that truly
improve current clinical practice.

To produce meaningful recommendations with adequate data support, we propose
that patient trajectory datasets should exhibit diversity in observed actions
that correlates with differences in outcomes conditioned on a particular
state. In the RL formulation shown in Fig. 1, we assume that for a given state
$s_{t}$ we can estimate not only the cumulative reward of taking observed
action $a_{t}$, but also the reward for taking a different action
$a^{\prime}_{t}$. This would allow the offline-trained RL agent to accurately
choose between $a_{t}$ or $a^{\prime}_{t}$ despite having only observed
directly the results of the former action.

Figure 1: Markov decision process model for patients with sepsis in the ICU.
$s_{t}$ represents the patient state at time $t$, $a_{t}$ represents a
treatment action, and $y_{t}$ represents a function of the state that captures
the patient’s disease severity. Brackets indicate how these values are used in
our experiment.

It is difficult to measure action and outcome diversity conditioned on states
directly, since this can depend heavily on how the state is represented.
Instead, we constructed an experiment in which we trained transformer-based
dynamics models to predict future disease severity given a patient’s state and
optionally the treatment actions that were taken over the subsequent hours. If
clinician actions are diverse and have an effect on outcomes, then the action
information should improve a model’s ability to predict future observed
disease severity. Below we present preliminary results from this experiment
and discuss their implications for future efforts to optimize sepsis
treatment.

##  2 Related Work

Several studies (Raghu et al., 2017; Peng et al., 2018; Yu et al., 2019; Liu
et al., 2021; Ju et al., 2021) have applied RL to train treatment policies for
sepsis patients. For instance, the AI Clinician agent proposed by Komorowski
et al. (2018) utilized tabular $Q$-learning, while subsequent works have
proposed combining deep RL with kernel-based RL (Peng et al., 2018), applying
deep inverse RL (Yu et al., 2019), integrating physiological models
(Nanayakkara et al., 2022), and improving sample efficiency by focusing on
important timesteps (Liang et al., 2022; Ju et al., 2021)). Tang et al. (2023)
further introduced an approach that leverages factored action spaces to
improve the efficiency of offline RL in healthcare settings.

Other research highlights the challenges and shortcomings of these algorithmic
approaches. For example, Killian et al. (2020) found that even powerful
sequential models were unable to accurately separate patient state
representation by mortality. Jeter et al. (2019) suggested that the
$Q$-learning approach may learn to recommend dangerous treatments for severely
ill patients because the most common clinician actions have consistently low
rewards, whereas rarer actions may have high but noisy estimated values.
Gottesman et al. (2020) proposed improving RL policy evaluation by identifying
timepoints with a high OPE weight, while Ji et al. (2021) selected and
visualized trajectories that may explain policy behavior. To our knowledge,
however, predicting future disease outcomes from actions has not been examined
as a way to evaluate the feasibility of off-policy RL in sepsis.

##  3 Methods

###  3.1 Data and Preprocessing

Patient trajectory data was extracted following Komorowski et al. (2018) and
Killian et al. (2020) from MIMIC-IV (Johnson et al., 2020) and the eICU
Collaborative Research Database (Pollard et al., 2018).111While previous work
has generally used MIMIC-III, the AI Clinician modeling procedure has been
shown to yield consistent results in the two versions of MIMIC (Sivaraman et
al., 2023).222Preprocessing and modeling code available at
https://github.com/cmudig/AI-Clinician-MIMICIV. Data was aggregated at one-
hour intervals, and patients with more than 14 days in the ICU were excluded.
Missing data was imputed using a transformer-based autoencoder model. This
resulted in a total of 2,060,446 timesteps from 33,779 patients.

The state space for our models consisted of 60 normalized observation
variables (vitals, labs, prior treatments, and fluid balances) and 35
demographic variables (age, gender, and Elixhauser comorbidities). The action
space comprised log-transformed continuous-valued dosages of IV fluids and
vasopressors. Three widely-used severity metrics were used as outcomes: the
Sequential Organ Failure Assessment (SOFA) score, the Systemic Inflammatory
Response Syndrome (SIRS) score, and Shock Index. Actions and disease severity
were $z$-transformed for model input and output.

###  3.2 Models

##### Dynamics models

Our experiment utilized decoder-only transformer models, where each input
“token” comprised embeddings of the patient’s observed state, demographics,
and actions.333We conducted the same experiments with linear and recurrent
networks as well as XGBoost models, but found that transformers yielded the
best performance. The model consisted of two transformer blocks, each
comprising 4 self-attention layers, each with 16 attention heads and a total
dimension of 1024. The first transformer block took the state and demographic
embeddings as input, while the second transformer block added embedded
clinician actions. Models were trained on the future disease severity task
along with three other proxy tasks: (1) predicting the current state of the
patient, (2) predicting whether the current state is the last step in the
patient’s trajectory, and (3) predicting whether two embeddings correspond to
states that are adjacent in time. The proxy tasks were included only to
improve the model’s convergence and generalizability, and results for these
tasks are not shown.

##### Behavior cloning

While the dynamics models described above aimed to predict the difference in
disease severity as a function of states and actions, we also trained behavior
cloning models to predict clinician actions as a function of states. These
models utilized the first transformer block from above to encode the state
observations and demographics, then applied a two-layer feedforward network to
simultaneously predict fluid and vasopressor dosages at one-hour intervals up
to 6 hours ahead.

##  4 Experiment Results

###  4.1 Influence of Action Inputs on Disease Severity Predictions

Three groups of models, totaling 81 dynamics models, were trained to predict
changes in future disease severity. The first group was trained with both
future action information and state information. In contrast, the second
group, featuring identical architectures, had all future actions set to the
mean action values (effectively removing them from training). The last group
also shared identical architectures, but was trained without the information
about states. Furthermore, disease severity changes were measured according to
the three metrics described above at 6 hours, 12 hours, and 18 hours ahead.
Each model configuration was trained and evaluated across three random weight
initializations. We then conducted four evaluations for each model by
generating predictions on variants of the test dataset: True (original
treatment actions), Zero (all dosage values set to zero), Shuffled (real but
randomly-permuted dosages), and Mean (all actions replaced with the mean
dosages). Fig. 2 shows the root mean squared error (RMSE) of these predictions
in $z$-scaled space, as well as two examples comparing model predictions to
ground-truth.

Figure 2: Left: RMSE (lower is better) of the predicted change in disease
severity across training schemes (“Train Actions”, “Train States,” and “Train
States + Actions”) and action inputs at test time (True, Zero, Shuffled, and
Mean). Error bars indicate the standard deviation across three random weight
initializations. Note that all units are in $z$-scaled space, so an RMSE of 1
corresponds to 1 standard deviation in the severity metric. Right: example
histograms comparing true and predicted changes in SOFA score at 12 hours
ahead, in the True and Shuffled evaluation conditions.

Overall, the RMSE was almost constant across training conditions and action
input types except for the Mean condition, which generally showed higher error
and variance across initializations when actions were used in training (likely
because consistently receiving nonzero fluids and vasopressors is a highly
unusual input). Among the other three conditions, the range of RMSEs was
within 0.05 for SIRS and Shock Index, and within 0.1 for SOFA. Furthermore,
performance in the True condition was highly similar whether or not actions
were provided during training. This null result suggests that actions did not
substantially improve the model fit, consistent with our hypothesis that they
are not diverse enough for policy learning. In addition, models trained
without state information showed similar trends, indicating that action
information is largely redundant with the states.

###  4.2 Prediction of Future Actions with Behavior Cloning

To evaluate the predictability of actions from states more directly, we
trained 3 replicates of the behavior cloning model with different random
weight initializations. If these models showed a strong fit to the data, one
could infer that actions were fully consistent and predictable across
clinicians.

Fig. 3 shows that the average $R^{2}$ correlations between the true and
predicted actions (in log-transformed and $z$-scaled units) were overall low,
particularly after several hours. IV fluid predictions were markedly less
correlated with the true values than vasopressor predictions, perhaps because
(1) vasopressors are more commonly zero than fluids, increasing the overall
predictability of vasopressor use, or because (2) the amount of IV fluid used
is generally more clinician-dependent. The regression models also appeared to
struggle with the wide range of fluid dosage values, and tended to predict
values within a more constrained range (Fig. 3, third panel).

Aside from the possible modeling issues in the IV fluid predictions, the low
correlations across both treatments suggest there is in fact some diversity in
clinician actions that could benefit policy learning. However, action
diversity does not necessarily correspond to observable differences in
outcomes, since there is likely a range of treatment dosages that correspond
to similar effects for a given patient state. The results in the preceding
section suggest that even when dosage differences exist, they may not yield
sufficient differences in outcomes to provide a useful signal to an RL agent.

Figure 3: Left: correlations between true and predicted normalized actions
from 1 to 6 hours ahead. Right: example histograms of correlations between
true and predicted normalized actions at 6 hours.

##  5 Discussion

This work explored the impact of clinician actions on the predictability of
future changes in sepsis disease severity, in order to gain insight into
whether actions have sufficient diversity to support accurate RL-based
policies. We found that action information does not confer substantive
improvements in dynamics model fit, as our transformer models could predict
future disease severity almost equally well with or without true actions as
input. Taken alone, the dynamics model results in Sec. 4.1 might suggest that
actions are fully predictable from the states and there was no need to learn
from the action inputs. This echoes results from Beaulieu-Jones et al. (2021),
who critique patient risk predictions as “looking over the shoulders of
clinicians.” However, action prediction (Sec. 4.2) was still fairly noisy,
indicating that while variation in actions exists, it is not enough to cause
measurable differences in outcomes in our sepsis cohort. Rather, the outcome
differences we observe may be more driven by unobserved patient variables or
natural random variation.

Some of the observed lack of diversity in actions on MIMIC data may be due to
inherent challenges in working with patient trajectories. For instance, there
may only be a small number of treatment possibilities that are clinically
feasible and safe, limiting the space of actions that clinicians could take.
Clinicians may also tend to choose actions in predefined patterns, such as
monotonically increasing or decreasing dosages, that appear diverse yet lead
to consistent outcomes. Alternatively, missing data imputation could have
caused patient states and actions to appear more consistent than they really
are. These obstacles are likely to exist in any patient treatment dataset,
underscoring the importance of using learning methods that are robust to
missingness and a constrained action space.

Another possible explanation for our results is that our models simply didn’t
learn to use actions effectively, and a better model formulation might yield
more pronounced differences between the “Train States” and “Train States +
Actions” models. It is impossible to determine a priori whether there exists a
more effective way to use actions, but we conjecture that if such a method
exists, it would likely require more clinically-informed descriptions of
actions than what has currently been explored in the literature. For instance,
models could use other treatments such as antibiotics and mechanical
ventilation, contextualize actions using the patient’s physiological state, or
limit the training data to only the most important decision points. Future
work should incorporate clinician guidance on how to meaningfully encode
treatments to further test the effects of action information.

This work highlights the importance of diversity in data sources when building
medical recommendation models. While it has been extremely valuable in
developing and exploring ways to improve sepsis treatment, the MIMIC dataset
is sourced from a single well-resourced hospital in Boston (Johnson et al.,
2020), where clinicians are likely to be consistent and compliant with
existing practice guidelines. Human-centered ML efforts undertaken in
collaboration with clinicians and medical data experts can also inspire more
clinically-relevant and performant model formulations, such as focusing on the
emergency department (a higher-stress environment that is less specialized
towards sepsis than the ICU) or building smaller models that are relevant to
specific subgroups of patients (Sivaraman et al., 2023). Through these
research directions, applied ML efforts may be able to better utilize
available observational data to improve sepsis treatment recommendation.

#### Acknowledgments

The authors would like to thank Dr. Jeremy Kahn, Andrew King, Jason Kennedy,
and the anonymous reviewers for feedback on the manuscript. This work was
supported by a National Science Foundation Graduate Research Fellowship
(DGE2140739), and by the Carnegie Mellon University Center of Machine Learning
and Health.

## References

  * Beaulieu-Jones et al. (2021) Brett K. Beaulieu-Jones, William Yuan, Gabriel A. Brat, Andrew L. Beam, Griffin Weber, Marshall Ruffin, and Isaac S. Kohane.  Machine learning for patient risk stratification: standing on, or looking over, the shoulders of clinicians?  _npj Digital Medicine_ , 4(1):1–6, March 2021.  ISSN 2398-6352.  doi: 10.1038/s41746-021-00426-3.  URL https://www.nature.com/articles/s41746-021-00426-3.  Publisher: Nature Publishing Group.
  * Centers for Disease Control and Prevention (2021) Centers for Disease Control and Prevention.  What is sepsis?, 2021.
  * Gottesman et al. (2020) Omer Gottesman, Joseph Futoma, Yao Liu, Sonali Parbhoo, Leo Anthony Celi, Emma Brunskill, and Finale Doshi-Velez.  Interpretable off-policy evaluation in reinforcement learning by highlighting influential transitions.  _37th International Conference on Machine Learning, ICML 2020_ , PartF16814:3616–3625, 2020.  arXiv: 2002.03478.
  * Jeter et al. (2019) Russell Jeter, Christopher Josef, Supreeth Shashikumar, and Shamim Nemati.  Does the ”Artificial Intelligence Clinician” learn optimal treatment strategies for sepsis in intensive care?  _arXiv_ , November 2019.  ISSN 1078-8956.  doi: 10.1038/s41591-018-0213-5.  arXiv: 1902.03271.
  * Ji et al. (2021) Christina X. Ji, Michael Oberst, Sanjat Kanjilal, and David Sontag.  Trajectory Inspection: A Method for Iterative Clinician-Driven Design of Reinforcement Learning Studies.  _AMIA … Annual Symposium proceedings. AMIA Symposium_ , 2021(i):305–314, 2021.  ISSN 1942597X.  arXiv: 2010.04279.
  * Johnson et al. (2020) A Johnson, L Bulgarelli, T Pollard, S Horng, L A Celi, and R Mark.  MIMIC-IV (version 1.0), 2020.
  * Ju et al. (2021) Song Ju, Yeo Jin Kim, Markel Sanz Ausin, Maria E. Mayorga, and Min Chi.  To Reduce Healthcare Workload: Identify Critical Sepsis Progression Moments through Deep Reinforcement Learning.  _Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021_ , pp. 1640–1646, 2021.  doi: 10.1109/BigData52589.2021.9671407.  Publisher: IEEE.
  * Killian et al. (2020) Taylor W. Killian, Haoran Zhang, Jayakumar Subramanian, Mehdi Fatemi, and Marzyeh Ghassemi.  An Empirical Study of Representation Learning for Reinforcement Learning in Healthcare.  pp. 1–22, 2020.  URL http://arxiv.org/abs/2011.11235.  arXiv: 2011.11235.
  * Komorowski et al. (2018) Matthieu Komorowski, Leo A. Celi, Omar Badawi, Anthony C. Gordon, and A. Aldo Faisal.  The Artificial Intelligence Clinician learns optimal treatment strategies for sepsis in intensive care.  _Nature Medicine_ , 24(11):1716–1720, 2018.  ISSN 1546170X.  doi: 10.1038/s41591-018-0213-5.  URL http://dx.doi.org/10.1038/s41591-018-0213-5.  arXiv: 1902.03271 Publisher: Springer US.
  * Liang et al. (2022) Dayang Liang, Huiyi Deng, and Yunlong Liu.  The treatment of sepsis: an episodic memory-assisted deep reinforcement learning approach.  _Applied Intelligence_ , 2022.  ISSN 15737497.  doi: 10.1007/s10489-022-04099-7.  Publisher: Applied Intelligence.
  * Liu et al. (2021) Ran Liu, Joseph Greenstein, James Fackler, Jules Bergmann, Melania Bembea, and Raimond Winslow.  Offline reinforcement learning with uncertainty for treatment strategies in sepsis.  2021\.
  * Nanayakkara et al. (2022) Thesath Nanayakkara, Gilles Clermont, Christopher James Langmead, and David Swigon.  Unifying cardiovascular modelling with deep reinforcement learning for uncertainty aware control of sepsis treatment.  _PLOS Digital Health_ , 1(2):e0000012, 2022.  doi: 10.1371/journal.pdig.0000012.  URL http://dx.doi.org/10.1371/journal.pdig.0000012.  arXiv: 2101.08477.
  * Peng et al. (2018) Xuefeng Peng, Yi Ding, David Wihl, Omer Gottesman, Matthieu Komorowski, Li Wei H. Lehman, Andrew Ross, Aldo Faisal, and Finale Doshi-Velez.  Improving Sepsis Treatment Strategies by Combining Deep and Kernel-Based Reinforcement Learning.  _AMIA … Annual Symposium proceedings. AMIA Symposium_ , 2018:887–896, 2018.  ISSN 1942597X.  arXiv: 1901.04670.
  * Pollard et al. (2018) Tom J Pollard, Alistair E W Johnson, Jesse D Raffa, Leo A Celi, Roger G Mark, and Omar Badawi.  The eICU Collaborative Research Database, a freely available multi-center database for critical care research.  _Scientific data_ , 5(1):1–13, 2018.
  * Raghu et al. (2017) Aniruddh Raghu, Matthieu Komorowski, Leo Anthony Celi, Peter Szolovits, and Marzyeh Ghassemi.  Continuous State-Space Models for Optimal Sepsis Treatment - a Deep Reinforcement Learning Approach.  68, 2017.  URL http://arxiv.org/abs/1705.08422.  arXiv: 1705.08422.
  * Sivaraman et al. (2023) Venkatesh Sivaraman, Leigh A. Bukowski, Joel Levin, Jeremy M. Kahn, and Adam Perer.  Ignore, Trust, or Negotiate: Understanding Clinician Acceptance of AI-Based Treatment Recommendations in Health Care.  volume 1. Association for Computing Machinery, 2023.  doi: 10.1145/3544548.3581075.  arXiv: 2302.00096 Publication Title: Conference on Human Factors in Computing Systems - Proceedings Issue: 1.
  * Tang et al. (2023) Shengpu Tang, Maggie Makar, Michael W. Sjoding, Finale Doshi-Velez, and Jenna Wiens.  Leveraging Factored Action Spaces for Efficient Offline Reinforcement Learning in Healthcare, May 2023.  URL http://arxiv.org/abs/2305.01738.  arXiv:2305.01738 [cs].
  * Yu et al. (2019) Chao Yu, Guoqi Ren, and Jiming Liu.  Deep inverse reinforcement learning for sepsis treatment.  _2019 IEEE International Conference on Healthcare Informatics, ICHI 2019_ , pp. 31–33, 2019.  doi: 10.1109/ICHI.2019.8904645.  Publisher: IEEE.


# Token Merging for Fast Stable Diffusion

Daniel Bolya Judy Hoffman
Georgia Tech
<EMAIL_ADDRESS>
###### Abstract

The landscape of image generation has been forever changed by open vocabulary
diffusion models. However, at their core these models use transformers, which
makes generation slow. Better implementations to increase the throughput of
these transformers have emerged, but they still evaluate the entire model. In
this paper, we instead speed up diffusion models by exploiting natural
redundancy in generated images by merging redundant tokens. After making some
diffusion-specific improvements to Token Merging (ToMe), our ToMe for Stable
Diffusion can reduce the number of tokens in an existing Stable Diffusion
model by up to 60% while still producing high quality images without any extra
training. In the process, we speed up image generation by up to $2\times$ and
reduce memory consumption by up to $5.6\times$. Furthermore, this speed-up
stacks with efficient implementations such as xFormers, minimally impacting
quality while being up to $5.4\times$ faster for large images. Code is
available at https://github.com/dbolya/tomesd.

##  1 Introduction

With the rise of powerful diffusion [21, 4] models such as DALL-E 2 [13],
Imagen [18], and Stable Diffusion [15], generating high quality images has
never been easier. However, running these models can be expensive, especially
for large images. All of these methods function by denoising images through
several evaluations of a transformer [22] backbone, meaning that computation
scales with the square of the number of tokens (and thus also the square of
pixels).

Several existing methods to speed up transformers have already been
successfully applied to open-source diffusion models such as Stable Diffusion.
Flash Attention [2] computes attention efficiently by cleverly accounting for
memory bandwidth. XFormers [8] contains several optimized implementation of
transformer components. And as of PyTorch 2.0, these optimizations are
natively available [12].

However, none of these approaches reduce the amount of work necessary—they
still evaluate the transformer on every token. Most images, including those
generated by diffusion models, have a high amount of redundancy. And thus,
performing computation on every token is a waste of resources. Recent work in
token reduction such as token pruning [14, 23, 11, 7] and token merging [10,
17, 1] have shown the ability to remove these redundant tokens in transformers
to speed up evaluation with a small accuracy drop.

Though most of these methods require re-training the model (which would be
prohibitively expensive for e.g., Stable Diffusion), Token Merging (ToMe) [1]
stands out in particular by not requiring any additional training. While the
authors only apply it to ViT [5] for classification, they claim that it should
also work for downstream tasks.

Figure 1: Token Merging for Stable Diffusion. When applied properly, ToMe [1]
can significantly increase the speed of image generation without jeopardizing
quality. Moreover, its benefits stack with existing methods such as xFormers
[8]. With ToMe and xFormers together, this $2048\times 2048$ image generated
in just 28 seconds on a 4090, which is 5.4$\times$ faster than the original
model.

In this paper, we put that to the test by applying ToMe to Stable Diffusion.
Out of the box, a naïve application can speed up diffusion by up to $2\times$
and reduce memory consumption by $4\times$ (Tab. 1), but the resulting image
quality suffers greatly (Fig. 3). To address this, we introduce new techniques
for token partitioning (Fig. 5) and perform several experiments to decide how
to apply ToMe (Tab. 3). As a result, we can keep the speed and improve the
memory benefits of ToMe, while producing images extremely close to the
original model (Fig. 7, Tab. 4). Furthermore, this speed-up stacks with
implementations such as xFormers (Fig. 1).

##  2 Background

In this work, our goal is to speed up an off-the-shelf Stable Diffusion [15]
model without training using ToMe [1].

#### Stable Diffusion.

Diffusion models [20, 21, 4] generate images by repeatedly denoising some
initial noise over some number of diffusion steps. Like most modern large
diffusion models, Stable Diffusion uses a U-Net [16] with transformer-based
blocks. Thus, it first encodes the current noised image as a set of tokens,
then passes it through a series of transformer blocks. Each transformer block
has the standard self attention [22] and multi-layer perception (mlp) modules,
with the addition of a cross attention module to condition on the prompt (see
Fig. 2).

#### Token Merging.

Token Merging (ToMe) [1] reduces the number of tokens in a transformer
gradually by merging $r$ tokens in each block. To do this efficiently, it
partitions the tokens into a source (src) and destination (dst) set. Then, it
merges the $r$ most similar tokens from src into dst, reducing the number of
tokens by $r$, making the next block faster.

Figure 2: A U-Net Block with ToMe applied. Stable Diffusion [15] uses a U-Net
[16] model with transformer-based blocks [22]. We apply ToMe [1] by merging
tokens before each component of the block and unmerging after to reduce
compute costs (Sec. 3).

##  3 Token Merging for Stable Diffusion

While ToMe as described in Sec. 2 works well for classification, it’s not
entirely straightforward to apply it to a dense prediction task like
diffusion. While classification only needs a single token to make a
prediction, diffusion needs to know the noise to remove for every token. Thus,
we need to introduce the concept of unmerging.

###  3.1 Defining Unmerging

While other token reduction methods such as pruning (e.g., [14]) remove
tokens, ToMe is different in that it merges them. And if we have information
about what tokens we merged, we have enough information to then unmerge those
same tokens. This is crucial for a dense prediction task, where we really do
need every token.

Figure 3: ToMe applied naïvely as described in Sec. 3 works to maintain image
coherence, but the content inside the image can change drastically with high
amounts of reduction.  Figure 4: Importance of Merging. If we just prune
tokens instead (and replace them with 0), the resulting images quickly
degrade.

In this work, we’ll define unmerging in the simplest possible way. Given two
tokens with $c$ channels $x_{1},x_{2}\in\mathbb{R}^{c}$ s.t. $x_{1}\approx
x_{2}$, if we merge them into a single token $x^{*}_{1,2}$, e.g.,

$x_{1,2}^{*}=(x_{1}+x_{2})/2$ (1)

we can “unmerge” them back into $x_{1}^{\prime}$ and $x_{2}^{\prime}$ by
setting

$x_{1}^{\prime}=x_{1,2}^{*}\qquad x_{2}^{\prime}=x_{1,2}^{*}$ (2)

While this loses information, the tokens were already similar so the error is
small. We find this works well in our case, but other unmerging methods might
be worth exploring.

###  3.2 An Initial Naïve Approach

Merging tokens and then immediately unmerging them doesn’t help us though.
Instead, we’d like to merge tokens, do some (now reduced) computation, and
then unmerge them afterward so we don’t lose any tokens. Naïvely, we can just
apply ToMe before each component of each block (i.e., self attn, cross attn,
mlp), and then unmerge the outputs before adding the skip connection (see Fig.
2).

#### Details.

Because we’re not accumulating any token reduction (merged tokens are quickly
unmerged), we have to merge a lot more than the original ToMe. Thus instead of
removing a quantity of tokens $r$, we remove a percentage ($r\%$) of all
tokens. Moreover, computing token similarities for merging is expensive, so we
only do it once at the start of each block. Finally, we don’t use proportional
attention and use the input to the block $x$ for similarly rather than
attention keys $k$. More exploration is necessary to find if these techniques
carry over from the classification setting.

Method |  r% |  FID $\downarrow$ |  s/im $\downarrow$ |  GB/im $\downarrow$
---|---|---|---|---
Baseline |  0 |  33.12 |  3.09 |  3.41
ToMe (Naïve) |  10 |  33.14 |  2.60 |  2.99
|  20 |  33.53 |  2.29 |  2.17
|  30 |  33.60 |  2.11 |  1.71
|  40 |  34.67 |  1.81 |  1.26
|  50 |  38.95 |  1.53 |  0.89
Table 1: Quantitative evaluation of the results in Fig. 3. While the approach
in Sec. 3 can lead to $\sim$2$\times$ faster image generation with
$\sim$4$\times$ less memory used (here for $512\times 512$ images), it results
in a significantly higher FID score. Thus, we explore further.

##  4 Further Exploration

Amazingly, the simple approach described in Sec. 3 works fairly well out of
the box without any training, even for large amounts of token reduction (see
Fig. 3). This is in stark contrast to if we pruned tokens instead, which
completely destroys the image (see Fig. 4). However, we’re not done yet. While
the images with ToMe applied look alright, the content within each image
changes drastically (mostly for the worse). Thus, we make further improvements
using Naïve ToMe with 50% reduction as our starting point.

#### Experimental Details.

To quantify performance, we use Stable diffusion v1.5 to generate 2,000
512$\times$512 images of ImageNet-1k [3] classes (2 per class) using 50 PLMS
[9] diffusion steps with a cfg scale [4] of 7.5. We then compute FID [6]
scores between those 2,000 samples and 5,000 class-balanced ImageNet-1k val
examples using [19]. To test speed, we simply average the time taken over all
2,000 samples on a single 4090 GPU. Applying ToMe naïvely increases FID
substantially (see Tab. 1), though evaluation is up to $2\times$ faster with
up to $4\times$ less memory used.

###  4.1 A New Partitioning Method

By default, ToMe partitions the tokens into src and dst (see Sec. 2) by
alternating between the two. This works for ViTs without unmerging, but in our
case this causes src and dst to form alternating columns (see Fig. 5a). Since
half of all tokens are in src, if we merge 50% of all tokens, then the
entirety of src gets merged into dst, so we effectively halve the resolution
of the images along the rows.

A simple fix would be to select tokens for dst with some 2d stride. This
significantly improves the image both qualitatively (Fig. 5b) and
quantitatively (Tab. LABEL:tab:partition_ablations_strided) and gives us the
ability to merge more tokens if we want (i.e., the src set is larger), but the
dst tokens are still always in the same place. To resolve this, we can
introduce randomness.

However, if we just sample dst randomly, the FID jumps massively (Tab.
LABEL:tab:partition_ablations_random w/o fix). Crucially, we find that when
using classifier-free guidance [4], the prompted and unprompted samples need
to allocate dst tokens in the same way. We resolve this by fixing the
randomness across the batch, which improves results past using a 2d stride
(Fig. 5c, Tab. LABEL:tab:partition_ablations_random w/ fix). Combining the two
methods by randomly choosing one dst token in each $2\times 2$ region performs
even better (Fig. 5d), so we make this our default going forward.

Figure 5: Partitioning src and dst. ToMe [1] merges tokens from src into dst.
(a) By default, ToMe alternates src and dst tokens. In our case, this causes
dst to form regular columns which leads to bad outputs (poor fish). (b) We can
improve generation by sampling dst with a 2d stride (e.g., $2\times 2$), but
this still forms a regular grid. (c) We can introduce irregularity by sampling
randomly, but this can cause undesirable clumps of dst tokens. (d) Thus, we
sample one dst token randomly in each $2\times 2$ region.

$s_{y}\times s_{x}$ |  dst% |  FID $\downarrow$
---|---|---
$1\times 2$ |  50 |  38.95
$2\times 1$ |  50 |  39.28
$2\times 2$ |  25 |  36.12
$2\times 4$ |  12.5 |  37.09
$4\times 2$ |  12.5 |  37.14
$4\times 4$ |  6.25 |  38.97
(a)

method |  fix |  FID $\downarrow$
---|---|---
rand 25% |  ✗ |  46.08
rand 25% |  ✓ |  36.00
rand $2\times 2$ |  ✓ |  35.66

(b)

Table 2: Partition Experiments. Evaluation of the src and dst partitioning
methods described in Fig. 5. 50% of tokens are merged in all experiments.
Random methods (b) perform the best provided we fix the randomness across the
batch (see Sec. 4.1).

self |  cross |  |  |
---|---|---|---|---
attn |  attn |  mlp |  FID $\downarrow$ |  s/im $\downarrow$
✓ |  ✓ |  ✓ |  35.66 |  1.56
✓ |  ✗ |  ✓ |  36.10 |  1.57
✓ |  ✗ |  ✗ |  33.73 |  1.64
✗ |  ✗ |  ✓ |  34.70 |  2.81
(a)

min |  |  |
---|---|---|---
tokens |  blocks |  FID $\downarrow$ |  s/im $\downarrow$
64 |  15 (all) |  35.66 |  1.56
256 |  14 |  35.71 |  1.55
1024 |  9 |  34.37 |  1.56
4096 |  4 |  33.29 |  1.63
(b)

r% start |  r% end |  FID $\downarrow$ |  s/im $\downarrow$
---|---|---|---
70 |  30 |  35.89 |  1.65
60 |  40 |  35.53 |  1.58
50 |  50 |  35.66 |  1.56
40 |  60 |  36.09 |  1.58
30 |  70 |  36.45 |  1.61
(c)

Table 3: Design Experiments. Using the random $2\times 2$ partitioning method
from Tab. 2, we now explore how best to apply ToMe (with $r=50\%$). Each
experiment is independent, and we highlight our resulting design choice in
gray.

###  4.2 Design Experiments

In Sec. 3, we apply ToMe to every module, layer, and diffusion step. Here we
search for a better design (Tab. 3).

####  What should we apply ToMe to?

Originally, we applied ToMe to all modules (self attn, cross attn, mlp). In
Tab. LABEL:tab:ablations_what, we test applying ToMe to different combinations
of these modules and find that in terms of speed vs. FID trade-off, just
applying ToMe to self attn is the clear winner. Note that FID doesn’t consider
prompt adherance, which is likely why merging the cross attn module actually
reduces FID.

####  Where should we apply ToMe?

Applying ToMe to every block in the network is not ideal, since blocks at
deeper U-Net scales have much fewer tokens. In Tab. LABEL:tab:ablations_where,
we try restricting ToMe to only blocks with some minimum number of tokens and
find that only the blocks with the most tokens need ToMe applied to get most
of the speed-up.

####  When should we apply ToMe?

It might not be right to reduce the same number of tokens in each diffusion
step. Earlier diffusion steps are coarser and thus might be more forgiving to
errors. In Tab. LABEL:tab:ablations_when, we test this by linearly
interpolating the percent of tokens reduced and find that indeed merging more
tokens earlier and fewer tokens later is slightly better, but not enough to be
worth it.

Figure 7: Qualitative Results. Our version of ToMe retains the image content, even at high token reduction. While some slight detail may be lost (e.g., in the background for the dog and bird), our method still handles complex scenes well (like the coral reef).  Method |  r% |  FID $\downarrow$ |  s/im $\downarrow$ |  GB/im $\downarrow$
---|---|---|---|---
Baseline |  0 |  33.12 |  3.09 |  3.41
ToMe for SD |  10 |  32.86 |  2.56 |  2.99
|  20 |  32.86 |  2.29 |  2.17
|  30 |  32.80 |  2.06 |  1.71
|  40 |  32.87 |  1.85 |  1.26
|  50 |  33.02 |  1.65 |  0.89
|  60 |  33.37 |  1.52 |  0.60
Table 4: Quantitative Results. Using the improvements from Sec. 4, our ToMe
for Stable Diffusion obtains similar or better FID compared to the baseline
while still being up to $2\times$ faster and using up to $5.6\times$ less
memory with 60% of tokens reduced.

##  5 Putting It All Together

We combine all the techniques discussed in Sec. 4 into one method, dubbed
“ToMe for Stable Diffusion”. In Fig. 7 we show representative samples of how
it performs visually, and in Tab. 4 we show the same qualitatively. Overall,
ToMe for Stable Diffusion minimally impacts visual quality while offering up
to $2\times$ faster evaluation using 5.6$\times$ less memory.

#### ToMe + xFormers.

Since ToMe just reduces the number of tokens, we can still use off the shelf
fast transformer implementations to get even more benefit. In Fig. 1 we test
generating a $2048\times 2048$ image with ToMe and xFormers combined and find
massive speed benefits. We can get even more speed-up if we’re okay with
sacrificing more visual quality (Fig. 8). Note that with smaller images, we
found this speed-up to be less pronounced, likely due to the diffusion model
not being the bottleneck. Moreover, the memory benefits did not stack with
xFormers.

Figure 8: Tuning for More Speed-up. The result in Fig. 1 (a) uses the choices
made in Sec. 4, which are tuned for the best quality. However, we can get even
more speed-up if we are okay with some drop in fidelity (b), but there’s a
limit (c) after which most time is taken by modules outside of our control,
resulting in little further speed-up. (Hint: the bird’s plumage gets less
detailed).

##  6 Conclusion and Future Directions

Overall, we successfully apply ToMe to Stable Diffusion in a way that
generates high quality images while being significantly faster. Notably, we do
this without training which is rather remarkable, as any other token reduction
method would require retraining. Still, these results could likely be improved
by exploring 1.) better unmerging strategies or 2.) whether proportional
attention or key-based similarity are useful for diffusion. Furthermore, our
success motivates more exploration into using ToMe for dense prediction tasks.
We hope this work can serve as both a useful tool for practitioners as well as
a starting point for future research in token merging.

Figure 9: More examples of ToMe for SD. Even at 60% of tokens merged, ToMe for
SD keeps the image the same (most of the time).

## References

  * [1] Daniel Bolya, Cheng-Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman.  Token merging: Your ViT but faster.  In ICLR, 2023.
  * [2] Tri Dao, Daniel Y Fu, Stefano Ermon, Atri Rudra, and Christopher Ré.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  arXiv:2205.14135 [cs.LG], 2022.
  * [3] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In CVPR, 2009.
  * [4] Prafulla Dhariwal and Alexander Nichol.  Diffusion models beat gans on image synthesis.  NeurIPS, 2021.
  * [5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In ICLR, 2020.
  * [6] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  NeurIPS, 2017.
  * [7] Zhenglun Kong, Peiyan Dong, Xiaolong Ma, Xin Meng, Wei Niu, Mengshu Sun, Bin Ren, Minghai Qin, Hao Tang, and Yanzhi Wang.  Spvit: Enabling faster vision transformers via soft token pruning.  In ECCV, 2022.
  * [8] Benjamin Lefaudeux, Francisco Massa, Diana Liskovich, Wenhan Xiong, Vittorio Caggiano, Sean Naren, Min Xu, Jieru Hu, Marta Tintore, Susan Zhang, Patrick Labatut, and Daniel Haziza.  xformers: A modular and hackable transformer modelling library.  https://github.com/facebookresearch/xformers, 2022.
  * [9] Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao.  Pseudo numerical methods for diffusion models on manifolds.  arXiv:2202.09778 [cs.CV], 2022.
  * [10] Dmitrii Marin, Jen-Hao Rick Chang, Anurag Ranjan, Anish Prabhu, Mohammad Rastegari, and Oncel Tuzel.  Token pooling in vision transformers.  arXiv:2110.03860 [cs.CV], 2021.
  * [11] Lingchen Meng, Hengduo Li, Bor-Chun Chen, Shiyi Lan, Zuxuan Wu, Yu-Gang Jiang, and Ser-Nam Lim.  Adavit: Adaptive vision transformers for efficient image recognition.  In CVPR, 2022.
  * [12] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In NeurIPS. 2019.
  * [13] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  arXiv:2204.06125 [cs.CV], 2022.
  * [14] Yongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu, Jie Zhou, and Cho-Jui Hsieh.  Dynamicvit: Efficient vision transformers with dynamic token sparsification.  NeurIPS, 2021.
  * [15] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In CVPR, 2022.
  * [16] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In MICCAI, 2015.
  * [17] Michael Ryoo, AJ Piergiovanni, Anurag Arnab, Mostafa Dehghani, and Anelia Angelova.  Tokenlearner: Adaptive space-time tokenization for videos.  In NeurIPS, 2021.
  * [18] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S Sara Mahdavi, Rapha Gontijo Lopes, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  NeurIPS, 2022.
  * [19] Maximilian Seitzer.  pytorch-fid: FID Score for PyTorch.  https://github.com/mseitzer/pytorch-fid, August 2020.  Version 0.2.1.
  * [20] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.  Deep unsupervised learning using nonequilibrium thermodynamics.  In ICML, 2015.
  * [21] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  NeurIPS, 2019.
  * [22] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  NeurIPS, 2017.
  * [23] Hongxu Yin, Arash Vahdat, Jose Alvarez, Arun Mallya, Jan Kautz, and Pavlo Molchanov.  A-ViT: Adaptive tokens for efficient vision transformer.  In CVPR, 2022.


# Explainability in Graph Neural Networks: An Experimental Survey

Peibo Li  Yixing Yang  Maurice Pagnucco&Yang Song111Contact Author
School of Computer Science and Engineering, University of New South Wales,
Sydney, Australia
{peibo.li, yixing.yang, morri<EMAIL_ADDRESS>
###### Abstract

Graph neural networks (GNNs) have been extensively developed for graph
representation learning in various application domains. However, similar to
all other neural networks models, GNNs suffer from the black-box problem as
people cannot understand the mechanism underlying them. To solve this problem,
several GNN explainability methods have been proposed to explain the decisions
made by GNNs. In this survey, we give an overview of the state-of-the-art GNN
explainability methods and how they are evaluated. Furthermore, we propose a
new evaluation metric and conduct thorough experiments to compare GNN
explainability methods on real world datasets. We also suggest future
directions for GNN explainability.

##  1 Introduction

Even though deep learning models have achieved unprecedented success, they are
criticized as being black-boxes Arrieta et al. (2020), due to the lack of
explainability, where people cannot understand how these models make
decisions. To address this issue, many different methods and frameworks have
been proposed to explain Convolutional Neural Networks (CNNs). To name a few,
Grad-CAM Selvaraju et al. (2017) provides visual explanations by generating
heat maps of the gradients from the last covolutional layer. LIME Ribeiro et
al. (2016) generates locally faithful explanations of any classifier or
regressor by learning an interpretable model locally. Chen et al. (2019)
proposes a prototypical part network (ProtoPNet) that is able to identify
prototypical parts in images without sacrificing model performance.

Graph Neural Networks (GNNs) have been shown to be very effective for many
applications, such as computer vision Bai et al. (2021); Xiang et al. (2021);
Zhang et al. (2021), citation networks analysis Gong and Cheng (2019);
Velickovic et al. (2018), recommendation in social networks Fan et al. (2019);
Chaudhary et al. (2019); Guo and Wang (2020), drug discovery Rathi et al.
(2019); Xiong et al. (2019), and community discovery Liu et al. (2019); Fang
et al. (2020). To explain GNNs, classic explainability methods for CNNs can be
extended for GNNs. For example, similar to Grad-CAM, in Pope et al. (2019), a
gradient-based explainability method is proposed for explaining GNNs. More
recently, some explainability methods focusing on the nature of the GNNs’
structures have emerged. GNNExplainer Ying et al. (2019) was proposed to
explain GNNs by masking unimportant edges/node features. Specifically,
GNNExplainer learns a trainable mask of the input graph for each individual
sample. Following the masking idea, PGExplainer Luo et al. (2020),
PGMExplainer Vu and Thai (2020) and GraphMask Schlichtkrull et al. (2021) were
proposed to learn stand-alone models to predict important edges, with
PGExplainer and GraphMask based on multilayer perceptrons and PGMExplainer
based on interpretable probabilistic graphical models. In addition, SubgraphX
Yuan et al. (2021) adopts Monte Carlo Tree Search Silver et al. (2017) to
identify important subgraphs. XGNN Yuan et al. (2020a) provides a model-level
explanation by training a GNN model with a graph generator which is guided by
reinforcement learning.

In this paper, we review the recent development of GNN explainability methods
and provide critical analysis. Furthermore, to compare GNN explainability
methods on any given dataset, we propose a novel human-free evaluation metric.
To the best of our knowledge, we are the first to perform objective and
thorough experiments on GNN explainability methods. Major limitations of
existing studies and our contributions can be summarized as follows: 1)
Reviews of GNN explainability are very limited. The existing survey papers for
GNNs Wu et al. (2020); Zhou et al. (2020); Zhang et al. (2022, 2019) only
include a brief discussion of GNN explainability methods. The only review
paper for GNN explainability Yuan et al. (2020b) lacks an experimental study.
Motivated by these, we present in this paper a critical review of the current
state-of-the-art in GNN explainability with in-depth experimental evaluation.
2) Existing evaluation metrics require human knowledge for ground truth and
thresholding, which can only be used in certain domains. To enable comparison
across most of the real-world datasets, we propose a human-free evaluation
metric. 3) Existing experimental studies have only been performed on synthetic
data or small molecule datasets. However, GNN explainability methods should be
tested on more real-world datasets in different domains, since explainability
is essential to ensure the trustworthiness and transparency of GNN models,
which is a critical requirement for real-world applications. Therefore, based
on existing and our novel evaluation metrics, we benchmark the existing
explainability methods on three citation networks. 4) Existing evaluations for
explainability methods have only been performed over the basic GCN model Kipf
and Welling (2016). The effectiveness of these methods over more advanced GNN
models needs to be verified. In our work, we experimentally study
explainability for different methods over multiple advanced GNN models with
different aggregation functions and deeper structures.

The rest of this article is organized as follows. Section 2 provides an
introduction to explainability in general. Section 3 discusses the literature
of GNN explainability methods. Section 4 introduces the experiments that we
conducted in detail. Section 5 discusses the future direction of GNN
explainability. Section 6 summarizes this article.

##  2 Explainability

Generally, explainability is one of the two most important branches of
Explainable AI (XAI); the other one being interpretability. Interpretability
here refers to designing models with human understandable structures Rudin
(2019); Freitas (2014); Huysmans et al. (2011), such like decision trees. For
explainability, it is the ability to explain a black-box model, i.e., to make
the black-box model easier to understand or reveal the reason for its
effectiveness, such as highlighting an area of an image that is accountable
for the prediction. We can regard interpretability and explainability as two
opposite translations, where interpretability is to translate human-
understandable knowledge to machine learning models, and explainability is to
translate black-box models to human-understandable knowledge. We refer the
interested reader to Guidotti et al. (2018) and Arrieta et al. (2020) for a
more detailed introduction to XAI.

In this paper, we focus on explainability. Generally in deep learning,
explainability methods can be grouped into two categories. The first category
is feature visualization. For instance, in the image domain, saliency maps
Selvaraju et al. (2017); Shrikumar et al. (2017); Lundberg and Lee (2017); Woo
et al. (2018) are used to highlight important image areas for predictions. In
the text domain, heatmaps Karpathy et al. (2015); Kádár et al. (2017);
Bahdanau et al. (2015); Mullenbach et al. (2018) are used to visualize input-
output alignment and to highlight important words in input-text. Despite
feature visualization being very popular in image and text domains, it is not
applicable for explaining graphs. This is because graphs provide non-Euclidean
data, which are inherently hard to visualize. Besides, there are some
drawbacks of visualizations; first, the quality of visualization is very
subjective and difficult to be objectively evaluated; second, these methods
can only be applied to limited examples, without obtaining a global view of
the entire dataset.

Another category of explanation methods is to mimic the original models’
behaviors. One popular method is to train a surrogate model, which is based on
inherently interpretable models (e.g., decision trees, support vector
machines) and trained to approximate the black-box model’s behaviors Ribeiro
et al. (2016). Another way is based on perturbation Luo et al. (2020);
Schlichtkrull et al. (2021); Vu and Thai (2020); Ying et al. (2019); Yuan et
al. (2021, 2020a). Specifically, different perturbations of input features or
model structures are generated, and the corresponding model behaviors are
monitored and analyzed. In this process, those input features and model
structures that decisively affect the model behaviors can be detected. While
explanation models are less intuitive to humans, they are easier to be
quantified and statistically analyzed.

To evaluate the explanation methods, there are mainly two types of evaluation
criterion: Plausibility and Faithfulness. Plausibility refers to how
convincing the explanations are to human, therefore it is more related to
human evaluation, which most of the existing studies rely on Selvaraju et al.
(2017); Shrikumar et al. (2017); Lundberg and Lee (2017); Woo et al. (2018).
However, human evaluation is not always practical and can be very subjective.
For more objective evaluation, Faithfullness was proposed and widely used
Lakkaraju et al. (2019); Wiegreffe and Pinter (2019); Jacovi and Goldberg
(2020); Schlichtkrull et al. (2021). Faithfulness refers to whether an
explanation faithfully reflects the underlying reasoning process of a model,
and several evaluation metrics for faithfulness have been proposed, including
disagreement between labels assigned by the explanation model and the black-
box model Lakkaraju et al. (2019); Total Variation Distance between the
adversarial trained attention model’s predictions and the original attention
model’s predictions Wiegreffe and Pinter (2019); and, the difference of
downstream task accuracy between the explanation model and the original model
Schlichtkrull et al. (2021).

##  3 GNN Explainability

To explain how GNNs work, many different methods have been developed. We
present a taxonomy of these methods by categorizing them based on their
origin; non-GNN-originated methods, i.e., methods extended from other deep
learning domains, and GNN-originated, i.e., methods specifically designed for
GNNs. Different from the previous GNN explainability review Yuan et al.
(2020b), we focus primarily on GNN originated methods since they are more
recent. We also review the evaluation metrics and datasets in this section.

Usually, the explanations of GNNs are represented as important subgraphs of
their computational graphs. While some of the explainability methods just
output the subgraphs Vu and Thai (2020); Yuan et al. (2021, 2020a), most of
them assign an importance score to every edge of the graph; and, to get the
important subgraph, thresholding based on these importance scores is needed
Ying et al. (2019); Luo et al. (2020); Schlichtkrull et al. (2021).

###  3.1 Non-GNN-originated Methods

Baldassarre and Azizpour (2019) exploited the capacibility of gradient-based
and decomposition-based methods for explainability. For gradient-based
methods, they implemented Sensitivity Analysis (SA) Gevrey et al. (2003) and
Guided Backpropogation (GBP) Springenberg et al. (2014) (previosly designed
for image domain) for GNNs. For decomposition-based methods, they implemented
Layer-wise Relevance Propagation (LRP) Montavon et al. (2017). This study is
the first work to focus on explainability techniques for GNNs and set the
ground for later development.

Pope et al. (2019) developed analogues for GNNs of three prominent
explainability methods for classic CNNs, which are contrastive gradient-based
(CG) saliency maps Simonyan et al. (2014), Class Activation Mapping (CAM) Zhou
et al. (2016) and Excitation Backpropagation (EB) Zhang et al. (2018), and
their variants, gradient-weighted CAM (Grad-CAM) Selvaraju et al. (2017) and
contrastive EB (c-EB) Zhang et al. (2018). They quantitatively evaluate the
performance of these methods with respect to fidelity, contrastivity and
sparsity. According to their experiments, they found Grad-CAM is the most
suitable among the studied methods for explanations on graphs of moderate
size.

###  3.2 GNN-originated Methods

GNNExplainer Ying et al. (2019) is the first general, model-agnostic approach
for GNN-based models on any graph-based tasks. Given a graph $G_{o}$ with node
features $X_{o}$ and a trained GNN $\Phi$, GNNExplainer can provide
explanations for any node $v$. It aims to identify a subgraph $G_{S}\subset
G_{o}$ and the associated subset of features $X_{S}^{F}$ that are important
for $\Phi$’s prediction. Here $F$ is a binary feature selector which is a
feature mask, and $X_{S}^{F}=X_{S}\odot F$. The objective is to maximize the
mutual information between the explanations and the original model.
Mathematically, it follows the optimization framework:

$\max_{G_{S},F}MI(Y,(G_{S},F))=H(Y)-H(Y|G=G_{S},X=X_{S}^{F})$ (1)

where the mutual information $MI$ quantifies the change in the probability
between $Y=\Phi(G_{o},X_{o})$ and $Y=\Phi(G_{S},X_{S})$. GNNExplainer explains
GNNs based on the input graph perturbation and exploits the structural
information from GNNs. However, it suffers from the scalability problem as the
size of parameters is proportional to the size of input graphs. Besides,
GNNExplainer only provides instance-level explanations which lack a global
understanding of predictions. Even though it is indicated that GNNExplainer
can be trained in a multi-instance manner, it is only at a theoretical level
without experimental justification.

PGExplainer Luo et al. (2020) was later proposed to provide a global
understanding of predictions made by GNNs. Specifically, it follows the
optimization framework of GNNExplainer but relaxes the edge weights from
binary variables to continuous variables in the range $(0,1)$ and adopts the
reparameterization trick to efficiently optimize the objective function with
gradient-based methods. Also, PGExplainer collectively explains predictions
made by a trained model on multiple instances, which enable it to have a
global view of a GNN model. It also improves computational efficiency by using
a stand-alone model to predict the importance of all edges in the graph, which
makes the parameter size independent from the graph size.

GraphMask Schlichtkrull et al. (2021) is a post-hoc method to identify
unnecessary edges. Different from GNNExplainer and PGExplainer, it learns a
simple classifier for every edge in every layer to predict if that edge can be
discarded; and the classifier is trained using the entire dataset. The
objective function can be summarized as follows:

$\displaystyle\max_{\lambda}\min_{\pi,b}$ $\displaystyle\sum\limits_{G,X\in
Dataset}\Big{(}\sum\limits_{k=1}^{L}\sum\limits_{(u,v)\in\mathcal{E}}\mathbbm{1}_{[\mathbb{R}\neq
0]}(g_{\pi,b}^{k}(u,v))\Big{)}$
$\displaystyle+\lambda\Big{(}D_{*}[\Phi(G,X)||\Phi(G_{S},X)]-\beta\Big{)}$ (2)

where $g_{\pi,b}^{k}$ computes the importance of any edge $(u,v)$ in the
$k^{th}$ layer, $\Phi(G,X)$ and $\Phi(G_{S},X)$ denote the two outputs from
the original trained GNN, and the explanation model over $G_{S}$,
$\mathbbm{1}$ is the indicator function and $D_{*}$ is a divergence function
to measure how the two outputs differ. Sparse relaxation Louizos et al. (2017)
is used to enable gradient-descent since the original objective is not
differentiable. Similar to PGExpaliner, GraphMask can provide a global
understanding of the trained GNN model. Furthermore, GraphMask provides
relevant paths by giving each layer a different mask.

PGM-Explainer Vu and Thai (2020) adopts the Probabilistic Graphical Model
(PGM) to give a model-agnostic explainer for GNNs. To explain a trained GNN
model $\Phi$, PGM-Explainer generates a PGM, which approximates the original
prediction of $\Phi$. Generally, PGM-Explainer contains three major
components: it first generates a set of input-output pairs, called sampled
data, by perturbing the original graph; then, the variables selection step
eliminates unimportant variables from the sampled data; and finally, it fits
the explanation Bayesian Networks for the filtered data from previous steps to
generate the explanation model. Different from other explainability models,
PGM-Explainer can illustrate the dependency among explained features. However,
PGM-Explainer is limited to instance level explanation and the learning
process of Bayesian Networks is very computationally expensive.

SubgraphX Yuan et al. (2021) explains GNNs on a subgraph level by efficiently
exploring different subgraphs with Monte Carlo Tree Search (MCTS). To be more
specific, SubgraphX builds the MCTS by setting the input graph as the root
node and each of the other nodes corresponds to a connected subgraph. Each
edge in the MCTS denotes the graph associated with a child node and is
obtained by pruning nodes from the graph associated with the parent node. The
MCTS algorithm explores paths from the root to leaves guided by visiting
counts and rewards. To evaluate the importance of subgraphs, SubgraphX forms a
cooperative game with generated subgraphs as players and uses the Shapley
value Kuhn and Tucker (1953) as the scoring function. The resultant connected
subgraphs are provided as explanations, which reveal the information contained
in the interactions among different nodes and edges. The drawback of SubgraphX
is similar to PGM-Explainer: it can only provide instance-level explanations
and cannot be applied to large graphs as the size of search trees increase
exponentially.

XGNN Yuan et al. (2020a) is a model-level explanation method for graph
classification problems, providing high-level insights and a generic
understanding of how GNNs work. In particular, for each chosen class $c_{i}$,
it generates a graph pattern that maximizes the predicted probability of the
GNN model for this class. This can reveal the relationships between graph
patterns and the predictions of GNNs. Graph generation is formulated as a
reinforcement learning task trained via a policy gradient method based on
information from the trained GNNs, where for each step, the graph generator
predicts where to add an edge into the current graph. However, XGNN can not be
applied to node classification tasks. Moreover, it falls into a paradox that
it uses one black-box to explain another black-box.

###  3.3 Evaluation Metrics

To evaluate GNN explainability, as we introduced before, faithfulness is
commonly assessed, which refers to how accurately the explanation reflects the
true reasoning process of the model. Another popular criterion is plausibility
Lakkaraju et al. (2019), which refers to how convincing the explanation is to
humans. Although there is not a standard evaluation metric in this field, all
the currently used metrics usually reflect one of these two aspects.

####  3.3.1 Plausibility Evaluation

Accuracy: Accuracy is used when the datasets contain human defined ground
truth explanation patterns Ying et al. (2019); Luo et al. (2020); Yuan et al.
(2020a); Vu and Thai (2020). Accuracy measures how well the generated
explanation fits the ground truth. Formally, it is defined as
$\frac{|\mathbf{GT}\cap\mathbf{E}|}{|\mathbf{E}|}$, where $\mathbf{GT}$ is the
set of edges in the ground truth explanation and $\mathbf{E}$ is the set of
edges in the generated explanation. Note that accuracy is related to the size
of the generated explanation; hence, it often requires users to threshold the
dense explanation based on the size of ground truth explanations. As this
needs human-defined ground truth for datasets, accuracy is not applicable to
most real-world datasets.

####  3.3.2 Faithfulness Evaluation

Sparsity and Fidelity: Sparsity is usually combined with fidelity, where
sparsity measures how many redundant edges are removed from the original
graph. A higher sparsity is preferred, as intuitively the explanation subgraph
should be the smallest subgraph with all information needed to make the
decision. Fidelity measures how faithful the explanation model is to the
original GNN model. Formally, sparsity is defined as:

$\displaystyle Sparsity=1-\frac{m}{M}$ (3)

where $m$ is the size of the important subgraph (i.e., the number of edges)
and $M$ is the size of the original graph. Fidelity is defined as:

$\displaystyle Fidelity=$ $\displaystyle P(Y=c|G)-P(Y=c|G\setminus G_{S}),$
$\displaystyle c=\mathop{\arg\max}_{c\in C}P(Y=c|G)$ (4)

where $P$ is the probabilistic distribution output by the model, $Y$ is the
prediction, $G$ is the original graph, $G_{S}$ is the explanation and $C$ is
the set of all the classes. This equation evaluates the faithfulness of the
explanation to the model by measuring the difference between predictions from
the graphs removing the important subgraphs and the original input graphs. In
practice, fidelity is computed and averaged over explanations with different
sparsities.

Inverse Fidelity: This evaluation metric compares the accuracy of the model
using the important subgraph and the accuracy of the model using the original
graph w.r.t the task over the test set Schlichtkrull et al. (2021). It is
defined as:

$InvFidelity=\frac{1}{N}\sum_{N}^{i=1}(\mathbbm{1}(\hat{y_{i}}^{\prime}=y_{i})-\mathbbm{1}(\hat{y_{i}}=y_{i}))$
(5)

where $y_{i}$ is the label, $N$ is the number of samples, $\hat{y_{i}}$ and
$\hat{y_{i}}^{\prime}$ are the predictions from original model and
explanations.

Faithfulness evaluation metrics are motivated by understanding models’
underlying reasoning process, differentiated from the reasoning process
produced by explainability methods, and do not require ground truth
explanations; hence, they can be applied to all tasks. The studies that use
accuracy usually select the same number of edges with the highest importance
score as the number of edges in the ground truth. As discussed above, first,
ground truth is not available in most of the real-world datasets; second, the
human-defined ground truth is not guaranteed to be correct as we would not
need to explain the models if we already know how they reason, which makes the
metric less reliable. Fidelity and inverse fidelity are usually computed over
different sparsities. The problem with this is that a certain sparsity can
have different impact on different data points. For instance, a 50% sparsity
might not affect the model’s prediction for a node with a large neighborhood,
while it might change the model’s prediction significantly for a node with a
small neighborhood. Therefore, it is not fair to directly compare fidelity
across different data points based on the same sparsity. Further discussion is
presented in Section 4.

Figure 1: Performance of GraphMASK, GNNExplainer and PGExplainer on GCN, GAT,
GCNII. No result for PGExplainer on GCNII for Pubmed because running out of
memory. At the same evaluation confidence (EC), higher sparsity means a
smaller number of edges are retained. A good explanation should has as high
sparsity as possible with high evaluation confidence.

###  3.4 Datasets

GNN explainability methods are commonly evaluated on synthetic datasets ,
where the most popular method to generate synthetic datasets is introduced in
Ying et al. (2019), which starts with a base graph and then attaches motifs to
randomly selected nodes in the base graph. Specifically, they constructed the
following five datasets: (1) BA-shapes: It is a node classification dataset,
where the base graph is a Barabási-Albert graph and the motif is a house
structure. There are four classes in this dataset; one of the classes
indicates the nodes in the base graph while the rest of the classes indicate
the relative location of nodes in the motif. There is no node feature in this
dataset. (2) BA-community: It extends BA-shapes to more complicated scenarios
with 8 classes. Basically, there are two sets of BA-shape structures, and the
nodes belonging to different sets have different labels even when their
relative locations within the set are the same. To distinguish the two sets,
node features are introduced. (3) Tree-Cycle: It is a node classification
dataset with two classes, where the base structure is a binary tree, and the
motif is a 6-node cycle structure. The class only indicates whether the nodes
are in motifs. (4) Tree-Grids: It is similar to Tree-Cycle, with the only
difference being that the motif is a 9-node grid. (5) BA-2Motifs: It is a
graph classification dataset with 2 classes. The graphs are obtained by
attaching different motifs to Barabási-Albert graphs, and classes indicate the
type of motifs in the graphs.

In addition to synthetic datasets, molecular datasets MUTAGDebnath et al.
(1991) and BBBP Wu et al. (2018) are commonly used for explanations over graph
classification tasks. In these datasets, each graph represents a molecule,
where the nodes represent atoms and edges represent bonds between atoms. The
labels for these graphs are determined by the chemical functionalities of the
corresponding molecules.

##  4 Experiments

Method | GCN | GAT | GCNII
---|---|---|---
GNNEx- | $\lambda=0.3912$ | $\lambda=\mathbf{0.4496}$ | $\lambda=0.2827$
-plainer | $\mu=-0.2726$ | $\mu=-0.2177$ | $\mu=\mathbf{0.0193}$
Graph- | $\lambda=\mathbf{0.5777}$ | $\lambda=0.2280$ | $\lambda=\mathbf{0.6015}$
-MASK | $\mu=\mathbf{-0.0244}$ | $\mu=\mathbf{-0.0115}$ | $\mu=-0.1605$
PGEx- | $\lambda=0.2164$ | $\lambda=0.1998$ | $\lambda=0.1073$
-plainer | $\mu=-0.4794$ | $\mu=-0.3494$ | $\mu=0.0027$
(a) Results for Cora

Method | GCN | GAT | GCNII
---|---|---|---
GNNEx- | $\lambda=0.1475$ | $\lambda=0.3825$ | $\lambda=0.1778$
-plainer | $\mu=-0.0887$ | $\mu=-0.0904$ | $\mu=\mathbf{-0.0314}$
Graph- | $\lambda=\mathbf{0.3080}$ | $\lambda=\mathbf{0.4556}$ | $\lambda=\mathbf{0.5777}$
-MASK | $\mu=\mathbf{-0.0341}$ | $\mu=\mathbf{-0.0121}$ | $\mu=-0.0930$
PGEx- | $\lambda=0.0960$ | $\lambda=0.1444$ | OOM
-plainer | $\mu=-0.1790$ | $\mu=-0.2216$
(b) Results for Pubmed. OOM denotes out of memoery.

Table 1: The average fidelity and inverse fidelity with sparsities from 0.5 to
0.95. $\lambda$ and $\mu$ represent fidelity and inverse fidelity
respectively.

In this section, we compare existing GNN explainability methods over different
GNN models on real-world citation networks datasets.

Evaluation Metric Since we cannot get ground truth explanations for such
tasks, we can only evaluate faithfulness. To do this, for all explainability
methods that only output importance scores other than the sparse subgraphs,
first, we need to sparsify the continuous edge importance scores to binary
explanations. A trivial way is to manually set a threshold and select edges
with importance scores higher than the threshold as explanations. This however
does not guarantee that the generated explanations have good quality. Then
with sparsity, we can generate explanations with different sparsities and
compute their fidelity values, obtaining the average fidelity value over
different sparsities. However, the range of fidelity values can vary
significantly for different samples and models, and hence it is not possible
to directly compare the performance of an explainability method on different
models based on fidelity. What’s more, what we want to evaluate is the
methods’ ability to find an explanation model that behaves similarly to the
original model while removing unimportant edges as much as possible. Sparsity,
however, focuses only on removing edges rather than evaluating the quality of
explanations, and hence cannot be used as an independent variable.

To this end, we propose an evaluation metric explanation confidence (EC),
which is formally defined as:

$\displaystyle EC=$ $\displaystyle
1-\frac{|P(Y=c|G)-P(Y=c|G_{S})|}{P(Y=c|G)},$ $\displaystyle
c=\mathop{\arg\max}_{c\in C}P(Y=c|G).$ (6)

This equation measures the difference between the probabilities of the
predicted class using the explanation subgraph and original graph, normalized
by the prediction probability using the original graph. A higher value
indicates a higher confidence that the explanation subgraph reflects the
actual reasoning process of the GNN model. Compared to fidelity, EC can be
used as an independent variable because its value is always $[0,1]$ for any
samples, which is thus normalized across all samples and models, making it
possible to directly compare the performance of different explainability
methods. In addition, by combining EC with sparsity, we can compute the
average sparsity over different qualities of explanations for all samples,
which has a clearer semantic compared to existing faithfulness evaluations.

Datasets Current experimental studies have been limited to synthetic datasets
and molecular datasets, which are not the most common applications of GNNs. To
evaluate the explainability methods in more realistic scenarios, we select
three of the most popular standard citation network benchmarks for GNNs: Cora
McCallum et al. (2000), Citeseer Giles et al. (1998)and Pubmed Sen et al.
(2008). In these datasets, nodes represent documents and edges represent
citations. Node features are elements of a bag-of-word representation of a
document and each node belongs to a certain class.

Setup Besides GCN Kipf and Welling (2016), we also evaluate explainability
methods on GAT Velickovic et al. (2018) and GCNII Chen et al. (2020). GAT uses
a different aggregation function to GCN, and GCNII is GCN with extra features
which allow it to have a deeper structure. As for explainability methods, we
select GNNExplainer, PGExplainer and GraphMASK because they are fundamentally
similar and easier to train. PGM-Explainer and SubgraphX do not scale to big
graphs and XGNN can not be applied to the node classification task. For each
dataset, we first train the models on the training set, and then use
GNNExplainer, PGExplainer and GraphMASK to explain them on the testing set.
Specifically, the GCNs and GATs all have two layers, the GCNIIs on Cora,
Citeseer, Pubmed have 64, 32 and 16 layers, respectively. For each sample, we
compute the highest sparsities that produce the explanations with explanation
confidence at 0.50, 0.55, 0.60, 0.65, 0.70,0.75, 0.80, 0.85, 0.90, 0.95. Then
we average the sparsities corresponding to the different explanation
confidence levels. Note we do not set explanation confidence at 1, which is
not practical. The experiments are conducted on an Nvidia RTX3090 GPU.

Results Figure 1 shows the performance of GraphMASK, GNNExplainer and
PGExplainer on GCN, GAT and GCNII for the three datasets. GraphMASK
consistently outperforms the other two methods, especially when the
explanation confidence is high. This indicates that the explanations generated
by GraphMASK are closer to the actual reasoning process of the models. This
can be explained by its architecture. For example, for a two-layer GCN, edges
outside of a node’s 1-hop neighborhood have no impact on the model’s behavior
at the second layer but affect the model’s behavior at the first layer.
GraphMASK is capable of capturing patterns like this because it treats
different layers in a graph differently while the others do not. While
PGExplainer performs the worst on GCN and GAT, it outperforms GNNExplainer on
GCNII. Furthermore, PGExplainer fails to distinguish important edges at a high
explanation confidence level on GAT and GCN. The result shows a big
performance drop from GNNExplainer when the models switch from shallow models
(GCNs, GATs) to deep models (GCNIIs), which shows that GNNExplainer is less
capable of explaining models with more parameters and deeper structures. In
addition, We report the evaluation results using existing fidelity and inverse
fidelity metrics for Cora and Pubmed in Table 1. Overall, GraphMASK still
gives the best performance while GNNExplainer has a better fidelity for GAT in
Cora and a better inverse fidelity for GCNII in Pubmed.

For both GraphMASK and PGExplainer, we benchmark them using both single-
instance level and model-level learning. The results we report for GraphMASK
are using single-instance level learning, which are better than using model-
level learning. The results we report for PGExplainer are using model-level
learning, which are similar to using single-instance level learning. We
observe that model-level learning does not give better performance in theses
dataset, and the reason behind this, which is beyond the scope of this paper,
can be investigated in future work.

##  5 Future Direction

As explainability in GNNs is still a relatively new area, there are still a
lot of challenges. We suggest three future research directions as follows.

Problem Definition The definition of explainability is still an open question
not only for explainability in GNNs but for the entire XAI community. We still
need a proper and well-accepted definition of the problem that we are trying
to solve: What is explainability? What do we want from explaining black-box
models? What makes a good explanation? We need clearer definitions for these
fundamental questions.

Evaluation Metric Unlike image and text domains where the evaluation can rely
on human experts, graph data is difficult to visualize and difficult to
understand even by human experts. Therefore, we need better quantitative
evaluation metrics that are both task-agnostic and task-specific and easy to
understand by general users.

Explainable GNN for Traditional Graph Algorithms GNNs have been used for many
traditional graph mining problems, such as subgraph enumeration and counting
Duong et al. (2021); Yang et al. (2021) and community computation Fang et al.
(2020); Liu et al. (2019); Yang et al. (2020). As traditional methods are
based on logic and mathematics, it will be interesting to study the
relationships between the explanations of GNN-based methods and the logic
behind the algorithm-based methods.

##  6 Conclusion

In this survey, we provide a critical review of state-of-the-art GNN
explainability methods, including quantitative metrics and datasets used in
the evaluation. We also propose a new evaluation metric, explanation
confidence, and present our experimental results comparing various GNN
explainability methods on different real-world datasets and GNN architectures.
Finally, we suggest our views for future directions of GNN explainability.

## References

  * Arrieta et al. [2020] A.B. Arrieta, N. Díaz-Rodríguez, J. Del Ser, A. Bennetot, S. Tabik, A. Barbado, S. García, S. Gil-López, D. Molina, R. Benjamins, et al.  Explainable artificial intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible ai.  Information Fusion, 2020.
  * Bahdanau et al. [2015] D. Bahdanau, K. Cho, and Y. Bengio.  Neural machine translation by jointly learning to align and translate.  In ICLR, 2015.
  * Bai et al. [2021] Y. Bai, J. Wang, Y. Long, B. Hu, Y. Song, M. Pagnucco, and Yu Guan.  Discriminative latent semantic graph for video captioning.  In ACM MM, 2021.
  * Baldassarre and Azizpour [2019] F. Baldassarre and H. Azizpour.  Explainability techniques for graph convolutional networks.  In ICML Workshop on Learning and Reasoning with Graph-Structured Representations, 2019.
  * Chaudhary et al. [2019] A. Chaudhary, H. Mittal, and A. Arora.  Anomaly detection using graph neural networks.  In COMITCon. IEEE, 2019.
  * Chen et al. [2019] C. Chen, O. Li, D. Tao, A. Barnett, C. Rudin, and J. Su.  This looks like that: Deep learning for interpretable image recognition.  In NeurIPS, 2019.
  * Chen et al. [2020] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li.  Simple and deep graph convolutional networks.  In ICML, Proceedings of Machine Learning Research. PMLR, 2020\.
  * Debnath et al. [1991] A. Kumar. Debnath, R.L. Lopez de Compadre, G. Debnath, A. J Shusterman, and C. Hansch.  Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity.  Journal of medicinal chemistry, 1991.
  * Duong et al. [2021] C. Duong, T. Hoang, H. Yin, M. Weidlich, Q. Nguyen, and K. Aberer.  Efficient streaming subgraph isomorphism with graph neural networks.  PVLDB, 2021.
  * Fan et al. [2019] W. Fan, Y. Ma, Q. Li, Y. He, E. Zhao, J. Tang, and D. Yin.  Graph neural networks for social recommendation.  In WWW, 2019.
  * Fang et al. [2020] Y. Fang, Y. Yang, W. Zhang, X. Lin, and X. Cao.  Effective and efficient community search over large heterogeneous information networks.  VLDB, 2020.
  * Freitas [2014] A. A Freitas.  Comprehensible classification models: a position paper.  ACM SIGKDD explorations newsletter, 2014.
  * Gevrey et al. [2003] M. Gevrey, I. Dimopoulos, and S. Lek.  Review and comparison of methods to study the contribution of variables in artificial neural network models.  Ecological modelling, 2003.
  * Giles et al. [1998] C.L. Giles, K.D Bollacker, and S. Lawrence.  Citeseer: An automatic citation indexing system.  In JCDL, 1998.
  * Gong and Cheng [2019] L. Gong and Q. Cheng.  Exploiting edge features for graph neural networks.  In CVPR, 2019.
  * Guidotti et al. [2018] R. Guidotti, A. Monreale, S. Ruggieri, F. Turini, F. Giannotti, and D. Pedreschi.  A survey of methods for explaining black box models.  CSUR, 2018.
  * Guo and Wang [2020] Z. Guo and H. Wang.  A deep graph neural network-based mechanism for social recommendations.  IEEE Transactions on Industrial Informatics, 2020.
  * Huysmans et al. [2011] J. Huysmans, K. Dejaeger, C. Mues, J. Vanthienen, and B. Baesens.  An empirical evaluation of the comprehensibility of decision table, tree and rule based predictive models.  Decision Support Systems, 2011.
  * Jacovi and Goldberg [2020] A. Jacovi and Y. Goldberg.  Towards faithfully interpretable NLP systems: How should we define and evaluate faithfulness?  In ACL, 2020.
  * Kádár et al. [2017] Ákos Kádár, Grzegorz Chrupała, and Afra Alishahi.  Representation of linguistic form and function in recurrent neural networks.  ACL, 2017.
  * Karpathy et al. [2015] A. Karpathy, J. Johnson, and Li Fei-Fei.  Visualizing and understanding recurrent networks.  arXiv preprint arXiv:1506.02078, 2015.
  * Kipf and Welling [2016] T.N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  arXiv, 2016.
  * Kuhn and Tucker [1953] H.W. Kuhn and A.W. Tucker.  Contributions to the Theory of Games.  Princeton University Press, 1953.
  * Lakkaraju et al. [2019] H. Lakkaraju, E. Kamar, R. Caruana, and J. Leskovec.  Faithful and customizable explanations of black box models.  In AIES, 2019.
  * Liu et al. [2019] Jiahao Liu, Guixiang Ma, Fei Jiang, Chun-Ta Lu, S Yu Philip, and Ann B Ragin.  Community-preserving graph convolutions for structural and functional joint embedding of brain networks.  In IEEE ICBD, 2019.
  * Louizos et al. [2017] C. Louizos, M. Welling, and D. P Kingma.  Learning sparse neural networks through $l\\_0$ regularization.  arXiv, 2017.
  * Lundberg and Lee [2017] S.M. Lundberg and S. Lee.  A unified approach to interpreting model predictions.  NeurIPS, 2017.
  * Luo et al. [2020] D. Luo, W. Cheng, D. Xu, W. Yu, Bo Zong, H. Chen, and X. Zhang.  Parameterized explainer for graph neural network.  NeurIPS, 2020.
  * McCallum et al. [2000] A. McCallum, K. Nigam, J. Rennie, and K. Seymore.  Automating the construction of internet portals with machine learning.  Information Retrieval, 2000.
  * Montavon et al. [2017] G. Montavon, S. Lapuschkin, A. Binder, W. Samek, and K. Müller.  Explaining nonlinear classification decisions with deep Taylor decomposition.  Pattern Recognition, 2017.
  * Mullenbach et al. [2018] J. Mullenbach, S. Wiegreffe, J. Duke, J. Sun, and J. Eisenstein.  Explainable prediction of medical codes from clinical text.  In NAACL-HLT, 2018.
  * Pope et al. [2019] P.E. Pope, S. Kolouri, M. Rostami, C.E. Martin, and H. Hoffmann.  Explainability methods for graph convolutional neural networks.  In CVPR, 2019.
  * Rathi et al. [2019] Prakash Chandra Rathi, R Frederick Ludlow, and Marcel L Verdonk.  Practical high-quality electrostatic potential surfaces for drug discovery using a graph-convolutional deep neural network.  Journal of medicinal chemistry, 2019.
  * Ribeiro et al. [2016] M.T. Ribeiro, S. Singh, and C. Guestrin.  “Why should I trust you?” explaining the predictions of any classifier.  In SIGKDD, 2016.
  * Rudin [2019] C. Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 2019.
  * Schlichtkrull et al. [2021] M. S. Schlichtkrull, N. De Cao, and I. Titov.  Interpreting graph neural networks for NLP with differentiable edge masking.  In ICLR, 2021.
  * Selvaraju et al. [2017] R.R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In ICCV, 2017.
  * Sen et al. [2008] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad.  Collective classification in network data.  AI magazine, 2008.
  * Shrikumar et al. [2017] A. Shrikumar, P. Greenside, and A. Kundaje.  Learning important features through propagating activation differences.  In ICLR. PMLR, 2017.
  * Silver et al. [2017] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al.  Mastering the game of go without human knowledge.  nature, 2017.
  * Simonyan et al. [2014] K. Simonyan, A. Vedaldi, and A. Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  In In Workshop at ICLR. Citeseer, 2014.
  * Springenberg et al. [2014] J.T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller.  Striving for simplicity: The all convolutional net.  arXiv, 2014.
  * Velickovic et al. [2018] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph attention networks.  In ICLR, 2018.
  * Vu and Thai [2020] M. Vu and M.T. Thai.  PGM-Explainer: Probabilistic graphical model explanations for graph neural networks.  In NeurIPS, 2020.
  * Wiegreffe and Pinter [2019] S. Wiegreffe and Y. Pinter.  Attention is not not explanation.  In EMNLP-IJCNLP, 2019.
  * Woo et al. [2018] S. Woo, J. Park, J. Lee, and In So Kweon.  Cbam: Convolutional block attention module.  In ECCV, 2018.
  * Wu et al. [2018] Z. Wu, B. Ramsundar, E.N. Feinberg, J. Gomes, C. Geniesse, A.S Pappu, K. Leswing, and V. Pande.  Moleculenet: a benchmark for molecular machine learning.  Chemical science, 2018.
  * Wu et al. [2020] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Yu Philip.  A comprehensive survey on graph neural networks.  TNNLS, 2020.
  * Xiang et al. [2021] T. Xiang, C. Zhang, Y. Song, J. Yu, and W. Cai.  Walk in the cloud: Learning curves for point clouds shape analysis.  In CVPR, 2021.
  * Xiong et al. [2019] Z. Xiong, D. Wang, X. Liu, F. Zhong, X. Wan, X. Li, Z. Li, X. Luo, K. Chen, H. Jiang, et al.  Pushing the boundaries of molecular representation for drug discovery with the graph attention mechanism.  Journal of medicinal chemistry, 2019.
  * Yang et al. [2020] Y. Yang, Y. Fang, X. Lin, and W. Zhang.  Effective and efficient truss computation over large heterogeneous information networks.  ICDE, 2020.
  * Yang et al. [2021] Y. Yang, Y. Fang, M. Orlowska, W. Zhang, and X. Lin.  Efficient bi-triangle counting for large bipartite networks.  PVLDB, 2021.
  * Ying et al. [2019] R. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec.  GNNExplainer: Generating explanations for graph neural networks.  NeurIPS, 2019.
  * Yuan et al. [2020a] H. Yuan, J. Tang, X. Hu, and S. Ji.  XGNN: towards model-level explanations of graph neural networks.  In SIGKDD. ACM, 2020.
  * Yuan et al. [2020b] H. Yuan, H. Yu, S. Gui, and S. Ji.  Explainability in graph neural networks: A taxonomic survey.  arXiv preprint arXiv:2012.15445, 2020.
  * Yuan et al. [2021] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji.  On explainability of graph neural networks via subgraph explorations.  In ICML, 2021.
  * Zhang et al. [2018] J. Zhang, S. A. Bargal, Z. Lin, J. Brandt, X. Shen, and S. Sclaroff.  Top-down neural attention by excitation backprop.  IJCV, 2018.
  * Zhang et al. [2019] Si Zhang, H. Tong, J. Xu, and R. Maciejewski.  Graph convolutional networks: A comprehensive review.  Computational Social Networks, 2019.
  * Zhang et al. [2021] C. Zhang, J. Yu, Y. Song, and W. Cai.  Exploiting edge-oriented reasoning for 3d point-based scene graph analysis.  In CVPR, 2021.
  * Zhang et al. [2022] Z. Zhang, P. Cui, and W. Zhu.  Deep learning on graphs: A survey.  IEEE Trans. Knowl. Data Eng., 2022.
  * Zhou et al. [2016] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba.  Learning deep features for discriminative localization.  In CVPR, 2016.
  * Zhou et al. [2020] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun.  Graph neural networks: A review of methods and applications.  AI Open, 2020.