# Explaining the Explainers in Graph Neural Networks: a Comparative Study

Antonio Longa<EMAIL_ADDRESS>Fondazione Bruno Kessler, Trento, Italy
University of Cambridge, Cambridge, United Kingdom  Steve Azzolin  University
of Cambridge, Cambridge, United Kingdom  Gabriele Santin  Fondazione Bruno
Kessler, Trento, Italy  Giulia Cencetti  Fondazione Bruno Kessler, Trento,
Italy  Pietro Liò  Bruno Lepri  Fondazione Bruno Kessler, Trento, Italy
Andrea Passerini  University of Cambridge, Cambridge, United Kingdom

###### Abstract

Following a fast initial breakthrough in graph based learning, Graph Neural
Networks (GNNs) have reached a widespread application in many science and
engineering fields, prompting the need for methods to understand their
decision process.

GNN explainers have started to emerge in recent years, with a multitude of
methods both novel or adapted from other domains. To sort out this plethora of
alternative approaches, several studies have benchmarked the performance of
different explainers in terms of various explainability metrics. However,
these earlier works make no attempts at providing insights into why different
GNN architectures are more or less explainable, or which explainer should be
preferred in a given setting.

In this survey we fill these gaps by devising a systematic experimental study,
which tests ten explainers on eight representative architectures trained on
six carefully designed graph and node classification datasets. With our
results we provide key insights on the choice and applicability of GNN
explainers, we isolate key components that make them usable and successful and
provide recommendations on how to avoid common interpretation pitfalls. We
conclude by highlighting open questions and directions of possible future
research.

##  1 Introduction and Motivation

Graph Neural Networks (GNNs) have emerged as the de-facto standard for graph-
based learning tasks. Regardless of their apparent simplicity, that allows
most GNN architectures to be expressed as variants of Message Passing [28],
i.e., exchanging messages between nodes, GNNs have proved extremely effective
in preserving the natural symmetries present in many real-world physical
systems [85, 39, 59, 23, 8]. The versatility of GNNs allowed them to be also
applied to emulate classical algorithms [12], addressing tasks like bipartite
matching [27], graph coloring [50] or the Traveling Salesperson Problem [58],
and approximate symbolic reasoning tasks like propositional satisfiability
[73, 72, 86] and probabilistic logic reasoning [102]. Despite recent works
trying to adapt the Transformer architecture, made popular by a wide success
first in language [81, 66, 61, 60] and then in vision applications [18, 62,
51], to the graph domain [43, 63, 97, 20, 103], the natural inductive bias of
GNNs remains at the basis of the current success of GNNs. A major drawback of
GNNs with respect to alternative graph processing approaches [35, 56, 76, 30]
is the opacity of their predictive mechanism, which they share with most deep-
learning based architectures. This severely limits the applicability of these
technologies to safety-critical scenarios. The need to provide insights into
the decision process of the network, and the need to provide explanations for
automatic decisions affecting human’s life [16, 42], have stimulated research
in techniques for shading light into the black box nature of deep
architectures [65, 74, 88, 98, 80, 78, 79, 57, 31]. The approaches have also
been adapted to generate explanations for GNN models [78, 79, 57, 6]. However,
networked data have peculiarities that pose specific challenges that
explainers developed for tensor data struggle to address. The main challenge
comes from the lack of a regular structure, as nodes have variable number of
edges, which requires ad-hoc strategies to be properly addressed. Indeed, a
number of approaches have been recently developed that are specifically
tailored to explain GNN architectures. Yuan et al. [95] proposed a
categorization of explainers into four categories: _gradient-based_ which
exploit gradients of the input neural network [79, 80, 57]; _perturbation-
based_ where perturbations of the input graphs are aimed at obtaining
explainable subgraphs [91, 53, 24, 69]; _decomposition-based_ which try to
decompose the input identifying the explanations [6, 57, 70]; and _surrogate-
based_ where a simple interpretable surrogate model is used to explain the
original neural network [38, 101, 84].

It is often the case, however, that each work proposes a new set of benchmarks
or metrics, making the comparison across works complicated. We thereby stress
the need for a comprehensive evaluation that can fairly benchmark the
explainers under a unified lens. One of the first attempts to provide such a
comparative analysis is the up mentioned work by Yuan et al. [95], where a
taxonomy of the available explainers was proposed. In addition to this, the
authors reported a detailed overview of the most common datasets used to
benchmark explainers, along with the adopted evaluation metrics. However,
despite the wide coverage of explainers, datasets, and evaluation metrics,
only a single GNN architecture, namely a simple Graph Convolutional Network
[44], was evaluated, so that nothing can be said about the impact of different
architectures in the resulting explanations. A similar limitation affects the
works of Zhao et al. [104] and Agarwal et al. [1, 2] that, despite presenting
interesting insights in terms of consistency of explainers, desired properties
of explanation metrics and even introducing a generator for synthetic graph
benchmarks, focus their analysis to a single GNN architecture. Li et al. [49]
conducted the first empirical study comparing different GNN architectures.
However, their study is limited to node classification and the three
explainers under analysis [91, 53, 69] are not well representative of the
diversity of explanation strategies that have been proposed, as summarized in
the aforementioned taxonomy [95]. The most comprehensive study to date is the
recent work by Rathee at al. [64], that evaluated four GNN architectures over
nine explainers for both node and graph classification. However, the main goal
of this study is proposing a benchmarking suite to quantitatively evaluate
explainers, with no attempts at providing insights into why different GNN
architectures behave differently in terms of explainability, or which
explainer should be preferred in a given setting.

In spite of the aforementioned recent studies benchmarking explainability
methods for GNNs, no investigation has been done in characterizing the typical
explanation patterns associated to the topological concepts learned by the
network and how different architectures affect the explanation. In our work,
we address these issues by answering the following research questions:

  * •

RQ1: How does the architecture affect the explanations?

  * •

RQ2: How do explainers affect the explanations?

  * •

RQ3: How do different types of data affect the explanations?

Overall, our work aims to go beyond a merely quantitative evaluation of the
performance of explainer-GNN pairs and to make a significant step towards
explaining explainability. We run an unprecedented number of experiments
involving eight GNN architectures, ten instance-based explainers, and six
datasets (divided into node and graph classification) and enrich the
quantitative results we obtain by providing a deep understanding of the
reasons behind the observed behaviours, together with a set of recommendations
on how to select and best use the most appropriate explainer for the task
under investigation while avoiding common pitfalls, as well as a number of
open problems in GNN explainability that we believe deserve further
investigation.

The remaining of the paper is structured as follows: Section 2 presents an
overview of GNN architectures, with greater detail on the models that we
adopted in our study. On the same vein, Section 3 introduces the explainers
for graph models, while Section 4 describes the benchmark datasets. Section 5
presents the evaluation metrics employed to asses the explanation’s quality.
Section 6 summarizes how we trained the tested architectures, and Section 7
presents the results expressed with respect to the research questions defined
above. Finally, in Section 8 we discuss the results.

##  2 Graph Neural Networks

In this section we first introduce the notation to deal with the GNN
formalism, then we review the GNN architectures explicitly used in our study.
We consider a graph $G:=(V,E,\boldsymbol{X})$, with $n_{V}\in\mathbb{N}$ nodes
$V:=\\{1,\dots,{n_{V}}\\}$, $n_{E}\in\mathbb{N}$ edges $E\subset V\times V$,
and a matrix of $d$-dimensional node features
$\boldsymbol{X}\in\mathbb{R}^{n_{V}\times d}$, where the $i$-th row of
$\boldsymbol{X}$ is the vector of $d\in\mathbb{N}$ features of the $i$-th
node. We use the matrices
$\boldsymbol{A},\boldsymbol{L},\boldsymbol{I},\boldsymbol{\tilde{A}},\boldsymbol{\tilde{D}},\boldsymbol{\tilde{L}}\in\mathbb{R}^{n_{V}\times
n_{V}}$, where $\boldsymbol{A}$ and $\boldsymbol{L}$ are the adjacency and
Laplacian matrices of $G$, $\boldsymbol{I}$ is the $n_{V}$-dimensional
identity matrix, $\boldsymbol{\tilde{A}}:=\boldsymbol{A}+\boldsymbol{I}$,
$\boldsymbol{\tilde{D}}$ is its diagonal matrix, and
$\boldsymbol{\tilde{L}}:=\frac{2}{\lambda_{\max}(\boldsymbol{L})}\boldsymbol{L}-\boldsymbol{I}$
is the scaled and normalized Laplacian, where $\lambda_{\max}(\boldsymbol{L})$
is the largest eigenvalue of $\boldsymbol{L}$. Furthermore, $N(i):=\\{j\in
V:(i,j)\in E\\}$ is the first order neighborhood of the node $i\in V$.

Each GNN layer takes as input the graph $G$, and maps the node features
$\boldsymbol{X}\in\mathbb{R}^{n_{V}\times d}$ to updated node features
$\boldsymbol{X}^{\prime}\in\mathbb{R}^{n_{V}\times d^{\prime}}$ for a given
$d^{\prime}\in\mathbb{N}$. Some specific GNN layers, like Hierarchical pooling
layers [106, 92, 46, 11], instead of refining the embedding for each input
node aggregate nodes in order to coarsen the graph in a similar way as done by
pooling methods for vision models [14, 79, 45], thus resulting in a node
feature matrix $\boldsymbol{X}^{\prime}\in\mathbb{R}^{n^{\prime}\times
d^{\prime}}$ where $n^{\prime}<n_{V}$. Overall, this new feature matrix
$\boldsymbol{X}^{\prime}$ represents the embedding or representation of the
nodes after the application of one layer of the network. When needed, we
denote as $\boldsymbol{X}_{i},\boldsymbol{X}_{i}^{\prime}$ the original and
transformed feature vector of the $i$-node, i.e., the transpose of the $i$-th
row of the matrices $\boldsymbol{X},\boldsymbol{X}^{\prime}$. Specifying the
map $\boldsymbol{X}\to\boldsymbol{X}^{\prime}$ is thus sufficient to provide a
full specification of the different layers. These transformations are
parametric, and they depend on trainable weights that are learned during the
optimization of the network. We represent these weights as matrices
$\boldsymbol{W}$. Additional terms specific to single layers are defined in
the following.

After an arbitrary number $t$ of GNN layers stacked in sequence, the node
embedding matrix $\boldsymbol{X}^{(t)}$ is further processed in a way that
depends on the task to perform. In node classification settings [44, 37],
where the aim is predicting one or more node properties, a Multi-Layer
Perceptron (MLP) [34] (with shared parameters across nodes) is applied to each
node’s embedding independently in order to output its predicted class. For
graph classification settings [37] instead, where the goal is predicting a
label for the entire graph, a permutation invariant aggregation function (like
mean, max, or sum) is applied over nodes’ embedding to compress
$\boldsymbol{X}^{(t)}$ into a single vector which is then mapped to the final
prediction via a standard MLP.

With this notation settled, we can now fully define the architectures that we
are going to consider. In selecting the architectures to be included in our
study, we relied on the comprehensive taxonomy of GNN methods published by
Zhou et al. [106]. Since our goal is to provide an extensive overview of
explainability methods for GNNs, we selected the models to benchmark aiming at
covering as much as possible the different categories of the taxonomy. The
specific methods are also selected depending on their popularity, their ease
of training, their performances on our benchmark datasets, and their code
availability. Overall, we analyzed the following categories: _Convolutional_
whose computation can be roughly intended as a generalization of the
convolution operation on the image domain. Such convolution can either be
_Spectral_ [17, 44], theoretically grounded in graph signal processing [77],
or _Spatial_ [82, 32, 90, 29], where the operations are usually defined in
terms of graph topology; The _Pooling_ category contains all approaches that
aggregate node representations in order to perform graph-level tasks. They can
be further differentiated into _Direct_ [83, 99], where nodes can be
aggregated with different aggregation strategies, often called readout
functions, and _Hierarchical_ [92, 11, 93, 46, 9], where nodes are
progressively hierarchically aggregated based on their similarity. The latter
methods often allow one to cluster nodes both based on their features and
their topological neighborhood [92, 9]. Despite covering the major aspects of
GNN architectures, the aforementioned taxonomy lacks some of the fundamental
works that we will analyze in our study. Particularly, to compensate that, we
decided to respectively include the Graph Isomorphism Network (Gin) [90] and
the GraphConv Higher Order Network (GraphConv) [55] as _Spatial Convolution_
and _Higher Order_ , the latter being a new category added to the taxonomy. A
summary of such categorization can be found in Figure 1. In the following, we
broadly describe each GNN model used in this work, reporting for each one the
category as identified by Zhou et al. [106]. Although the following
definitions are often given as global functions of the graph for notational
convenience, we remark that all the layers of a GNN can be efficiently
implemented as local operations by means of a message-passing or sparse matrix
multiplications.

Figure 1: An overview of the adopted GNN architectures structured in a
taxonomy as defined by Zhou et al. [106]. In particular, blue boxes represent
the categories as defined by the aforementioned work, while the purple box
corresponds to the newly introduced Higher Order category.

Chebyshev Spectral Graph Convolution

(Cheb, Spectral Convolution) [17]: The Chebyshev spectral graph convolutional
operator [17] was aimed to generalize the convolution operation from the image
to the graph domain. In doing so, it approximates the convolution of the node
features with a trainable filter where such approximation is defined in the
Fourier domain by means of a Chebyshev polynomial. Since explicitly computing
the convolution in the Fourier domain is very computationally expensive, to
this end Cheb adopts the truncated recursive Chebyshev expansion [33], where
the Chebyshev polynomial $T_{k}(x)$ of order $k$ can be computed by the
recurrence $T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)$ with $T_{1}=1$, $T_{2}=x$. Given
a degree $K\in\mathbb{N}$, we thus have:

$\boldsymbol{X}^{\prime}=\sum_{k=0}^{K}\boldsymbol{Z}^{(k)}\cdot\boldsymbol{W}^{(k)},$
(1)

where $\boldsymbol{Z}^{(k)}$ is computed recursively as:

$\displaystyle\boldsymbol{Z}^{(1)}$ $\displaystyle=\boldsymbol{X},$
$\displaystyle\boldsymbol{Z}^{(2)}$
$\displaystyle=\boldsymbol{\tilde{L}}\cdot\boldsymbol{X},$
$\displaystyle\boldsymbol{Z}^{(k)}$
$\displaystyle=2\boldsymbol{\tilde{L}}\cdot\boldsymbol{Z}^{(k-1)}-\boldsymbol{Z}^{(k-2)}.$

In our analysis we kept $K=5$.

Graph Convolutional Network

(Gcn, Spectral Convolution) [44]: Gcn [44] represents a first-order
approximation of localized spectral filters on graphs [17]. For a single
layer, the node representation is computed as:

$\boldsymbol{X}^{\prime}=\sigma(\boldsymbol{\tilde{D}}^{-1/2}\cdot\boldsymbol{\tilde{A}}\cdot\boldsymbol{\tilde{D}}^{-1/2}\cdot\boldsymbol{X}\cdot\boldsymbol{W}),$
(2)

with $\boldsymbol{W}\in\mathbb{R}^{d\times d^{\prime}}$, and where
$\sigma:\mathbb{R}\to\mathbb{R}$ is a nonlinear activation function that is
applied entry-wise. The normalization applied to $\boldsymbol{\tilde{A}}$ is
in place to avoid numerical instabilities after successive applications of the
above propagation rule. It effectively normalizes the node-wise aggregation by
a weighted sum where each neighbor is weighted by the incident edge weight
normalized by the degree of the two nodes. The connection with Cheb introduced
above can be seen by keeping the number of convolutions per layer to 1, thus
by setting $K=1$. After some further simplifications detailed in [44], and
here omitted for brevity, we can rewrite the spectral convolution as
$\boldsymbol{W}^{(k)}\cdot(\boldsymbol{I}+\boldsymbol{\tilde{D}}^{-1/2}\cdot\boldsymbol{\tilde{A}}\cdot\boldsymbol{\tilde{D}}^{-1/2})\cdot
x$. After applying the renormalization trick introduced in [44] and by
generalizing the formulation to a node feature matrix
$\boldsymbol{X}\in\mathbb{R}^{n_{V}\times d}$ we get the formulation of Eq 2.

Graph SAmple and aggreGatE

(GraphSage, Spatial Convolution) [32]: This work was proposed as an extension
of Gcn, with some minor modifications. Contrary to Gcn, which inherently
implements a weighted mean neighborhood aggregation, GraphSAGE generalizes to
different kinds of aggregations like mean, max or Long Short-Term Memory
(LSTM) aggregations [32, 36].

$\boldsymbol{X}^{\prime}_{i}=\boldsymbol{W}_{1}\boldsymbol{X}_{i}+\boldsymbol{W}_{2}\cdot
aggregation_{j\in N(i)}\boldsymbol{X}_{j},$ (3)

where $\boldsymbol{W}_{1},\boldsymbol{W}_{2}$ have both dimension $n_{V}\times
d^{\prime}$ and the function aggregation can be any permutation invariant
function. Note that in the case of the LSTM aggregation, the authors adapted
LSTMs to operate on sets by simply applying the LSTMs to a random permutation
of the nodes. In our study we used the mean of node features as aggregator.

Graph Isomorphism Network

(Gin, Spatial Convolution) [90]: The work of Xu et al. [90] was among the
first ones to study the expressive power of GNNs in relation to the
Weisfeiler-Lehman (WL) test of isomorphism [87]. The key insight is that a GNN
can have as large discriminative power as the WL test if the GNN’s aggregation
scheme is highly expressive and can model injective functions, like the
aggregation of the WL test. They studied the conditions for which a GNN has
the same discriminative power as the WL test, and then they proposed the Graph
Isomorphism Network (Gin) that provably satisfies such conditions [90]. The
Gin computes node representations as:

$\boldsymbol{X}^{\prime}=h_{\boldsymbol{W}^{\prime}}((\boldsymbol{A}+(1+\epsilon)+\boldsymbol{I})\cdot\boldsymbol{X}),$
(4)

where $\epsilon\in\mathbb{R}$ is a small number, and
$h_{\boldsymbol{W}^{\prime}}$ is a neural network whose weights
$\boldsymbol{W}^{\prime}$ are the trainable part of the Gin layer. This model
generalizes the WL test and hence achieves maximum discriminative power with
respect to the WL test [90]. In our work, to limit the complexity of the
network, we limited $h_{\boldsymbol{W}^{\prime}}$ to have a single layer.

Graph Attention Network

(Gat, Spatial Attentional Convolution) [82]: Following the successes of
attention mechanism in natural language processing [81, 60, 61, 66] and in
computer vision [89, 18, 62], Veličković et al. [82] proposed a GNN layer
which computes each node’s representation as a weighted sum of neighborhood
features, where the weights are computed via an attention mechanism. Such
attention mechanism helps the layer to focus on neighbors which are considered
to be important for the current node, instead of treating each neighbor
equally importantly [5]. Specifically, the propagation rule for each node can
be defined by:

$\boldsymbol{X}^{\prime}_{i}=\sum_{j\in
N(i)\cup\\{i\\}}\alpha_{i,j}\boldsymbol{W}\cdot\boldsymbol{X}_{j},$ (5)

where the $\alpha_{i,j}$ are attention coefficients, which are the output of a
single-layer feed forward neural network applied to
$\boldsymbol{W}\cdot\boldsymbol{X}_{i},\boldsymbol{W}\cdot\boldsymbol{X}_{j}$.
Namely, if $[x||y]$ denotes the concatenation of the vectors $x,y$, and if
$\boldsymbol{W}^{\prime}\in\mathbb{R}^{2d^{\prime}\times 1}$ is a vector of
trainable weights, then $\alpha_{i,j}$ is defined by

$\alpha_{i,j}:=\dfrac{\exp(\operatorname{LeakyReLU}((\boldsymbol{W}^{\prime})^{T}[\boldsymbol{W}\boldsymbol{X}_{i}||\boldsymbol{W}\boldsymbol{X}_{j}]))}{\sum_{k\in
N(i)\cup\\{i\\}}\exp(\operatorname{LeakyReLU}((\boldsymbol{W}^{\prime})^{T}[\boldsymbol{W}\boldsymbol{X}_{i}||\boldsymbol{W}\boldsymbol{X}_{k}]))},$
(6)

where $\operatorname{LeakyReLU}$ has usually a slope $\alpha:=0.2$ if $x\leq
0$. Similarly as previous works on attention [18, 81, 15, 60, 61, 66, 62], Gat
can implement multi-head attention in order to increase the attention’s
expressive power in modelling different aspects of node features.

MinCutPooling

(MinCutPool, Hierarchical Pooling) [9]: Similarly to other graph pooling
mechanisms [92, 11, 93, 46], MinCutPool is able to hierarchically aggregate
nodes into coarser representations in order to summarize local components and
remove redundant information. Graph pooling follows a similar idea as pooling
in standard architectures for vision applications [14, 79, 45], where it helps
to reduce the memory and computation footprint of the model. However, the
structured graph domain poses new challenges which required ad-hoc techniques
for achieving good performing pooling methods. MinCutPool [9] achieves so by
formulating a relaxation of the MinCut problem and by training a GNN to
compute cluster assignment by jointly optimizing the downstream supervised
loss and the additional unsupervised _mincut_ loss. In particular, a soft
cluster assignment matrix $\boldsymbol{S}\in\mathbb{R}^{n_{V}\times
n_{V}^{\prime}}$ is computed with a MLP with softmax activation over a refined
set of node features (e.g. after one or more layers of message passing). Then,
both the adjacency matrix and the node features’ matrix are updated
accordingly:

$\displaystyle\boldsymbol{X}^{\prime}$
$\displaystyle=\boldsymbol{S}^{T}\cdot\boldsymbol{X},$ (7)
$\displaystyle\mathbf{\tilde{A}}$
$\displaystyle=\boldsymbol{S}^{T}\cdot\boldsymbol{A}\cdot\boldsymbol{S}-\boldsymbol{\mathit{I}_{n_{V}^{\prime}}}diag(\boldsymbol{S}^{T}\cdot\boldsymbol{A}\cdot\boldsymbol{S}),$
(8) $\displaystyle\boldsymbol{A}^{\prime}$
$\displaystyle=\tilde{D}^{\frac{1}{2}}\cdot\mathbf{\tilde{A}}\cdot\tilde{D}^{\frac{1}{2}}.$

We refer the interested reader to [9] for the details about the mathematical
formulation of the differentiable MinCut problem. Since pooling methods modify
the graph structure, they are not typically suitable for node classification
and link predictions tasks [92, 11, 93, 46]. We will henceforth refer to as
MinCutPool for an architecture implemented with Gcn layers interleaved with
the MinCutPool operator.

Set2Set

(Direct Pooling) [83]: The Set2Set model [83] is a specific approach for
global graph pooling which takes as input the node-level representations, as
computed by any GNN layer, and outputs a single representation for the entire
graph suitable for graph-level tasks (e.g. graph classification [37],
molecular property prediction [41, 10], etc.). Whilst traditional approaches
simply taking the mean/max/sum of every node’s representations, Set2Set can be
seen as learning the aggregation via an LSTM. Thus, the node features are
treated as sequences, which are processed through an LSTM network to obtain an
embedding of the entire graph, represented as a vector of length $2d$. To
enforce permutation equivariance, the ordering of the nodes can be either
learned or randomized during training. The underlying LSTM works as follows:

$\displaystyle\textbf{q}_{t}$
$\displaystyle=\text{LSTM}(\textbf{q}^{*}_{t-1}),$ (9)
$\displaystyle\alpha_{i,t}$
$\displaystyle=\operatorname{softmax}(\boldsymbol{X}_{i}\cdot\textbf{q}_{t}),$
$\displaystyle\textbf{r}_{t}$
$\displaystyle=\sum_{i=1}^{n_{V}}\alpha_{i,t}\boldsymbol{X}_{i},$
$\displaystyle\textbf{q}_{t}^{*}$
$\displaystyle=\left[\textbf{q}_{t}||\textbf{r}_{t}\right].$

where $\textbf{q}_{t}^{*}$ is the output of the layer. The subscript
$t\in\\{1,\dots,T\\}$ indicates that the process may be repeated a number
$T\in\mathbb{N}$ of times. In our work we refer to Set2Set as a GNN
architecture implemented as a number of Gcn layers with the Set2Set global
pooling operator and with a value of $T=7$.

GraphConv

(Higher Order) [55]: To increase the expressivity of GNNs, researchers
developed techniques to capture not only 1-hop connections, i.e., between the
node neighborhood, but also to capture higher order connections [55, 48, 19,
67, 100, 47, 26]. This network captures higher order connections of a graph
(up to order two) by aggregating information from neighbourhood nodes and
incident edges. It is defined as:

$\boldsymbol{X}^{\prime}_{i}=\boldsymbol{W}_{1}\boldsymbol{X}_{i}+\boldsymbol{W}_{2}\sum_{j\in
N(i)}e_{i,j}\cdot\boldsymbol{X}_{j},$ (10)

where $\boldsymbol{W}_{1}$ and $\boldsymbol{W}_{2}$ are learnable weight
matrices, while $e_{i,j}$ is the edge weight from node $i$ to node $j$.

##  3 GNN Explainability

To analyze and understand the strengths and weakness of graph explanation
algorithms, we selected instances of GNN explainers which are representative
of the current state of the art. To this end, we follow the systematization
proposed by Yuan et al. [95], and choose to investigate _instance-based_
explainers[105, 74, 78, 80, 79, 84, 91, 6, 71, 38, 65, 96, 54, 75, 52, 101,
70, 24], i.e., those which aim at identifying components of the input that are
responsible for the model’s output. This is in contrast with _model-based_
explainers, which rather try to provide a global understanding of a trained
model [3, 94]. Since the available model-based explainers are very
heterogeneous (i.e. it is not available a unified evaluation setting), and
since previous works on benchmarking graph explainers have focused on
instance-based methods [95, 104, 1, 2, 49, 64], we thereby omit model-based
explainers. In particular, Yuan et al. [95] identifies four macro categories
of instance-based explainers, namely gradient-, perturbation-, decomposition\-
and surrogate-based models. Roughly speaking, gradient-based explainers
exploit gradients of the input neural network [79, 80, 57], perturbation-based
models perturb the input aiming to obtain explainable subgraphs[91, 53, 24,
69], decomposition-based models try to decompose the input identifying the
explanations [6, 57, 70], while surrogate-based models use a simple
interpretable surrogate to explain the original neural network [38, 101, 84].

Independently from this categorization, a further fundamental distinction is
among explainers providing explanations in terms of edge [91, 53, 69, 96] or
node masks [79, 80, 57, 6, 57, 70]. We refer to edge mask every time the
explainer gives as output any sort of likelihood for each edge in the input
graph. Conversely, a node mask represents likelihoods for every node in the
graph. Despite this distinction, it is anyway possible to transform an edge
mask into a node mask with a loss of information (and vice-versa) by, for
example, averaging for each node the likelihoods of the edges incident to that
specific node. Few explainers allow also to extract a node feature mask [91,
78], which highlights the contribution of each single feature in the input
node feature mask. However since single node features are not representative
of the underlying topological structure which we are interested in, and in
line with most previous works [95, 104, 1, 2, 49, 64], we do not consider
single node features’ explanations. Furthermore, to maintain a unique and
homogeneous evaluation setting, we convert every edge mask into a node mask,
accordingly to the procedure described before.

Below we report a brief overview of our benchmark explainers. Despite the
existence of other works proposing explainers, which occasionally fall outside
the aforementioned categorization [96, 54, 75, 52, 38, 101, 70], we limited
our analysis on a subset. More specifically, the criteria for selecting a
given explainer can be roughly summarized by _i)_ representativity of a
specific category as outlined before; _ii)_ code availability; and _iii)_
feasibility of usage, i.e., whether the explainer is not too computationally
heavy to be used. Unfortunately, for the _decomposition_ category, we did not
find an explainer with a working codebase that could be promptly included in
our study.

Given a GNN $g$ to be explained, let $g(e)^{c}=y^{c}=\left(w^{c}\right)^{T}e$
be the prediction of the model where $e$ corresponds to the final graph-level
or node-level embedding. The vector $w^{c}\in\mathbb{R}^{d^{\prime}}$ contains
instead the learned Fully Connected weights for class $c$ to perform the final
classification, and $\textsc{H}^{c}[n]$ represents the importance of node $n$
for the prediction of class $c$. A brief summarization of the methods is
available in Table 1.

GradExplNode

(Gradient) [78]: Inspired by the previous work computing explanation in the
context of Bayesian classification [4], GradExplNode computes the attribution
for each input by backpropagation to the input space. The general idea is that
the magnitude of the derivative gives insights into the most influential
features that, if perturbed, give the highest difference in the output space:

$\textsc{H}_{\textsc{GradExplNode}}^{c}[n]=\frac{\partial
y^{c}}{\partial\boldsymbol{X}_{n}}$ (11)

To derive a single value for each input node, it is possible to take the
maximum magnitude along the feature channel. Similarly, if the GNN to explain
supports edge weights, then this method can be applied on edges, thus
producing an edge mask. In the rest of the paper we will refer to this method
with GradExplNode and GradExplEdge, whether it is applied to node or edges,
respectively.

GuidedBp:

(Gradient) [79] Guided Back Propagation (GuidedBp) follows a similar approach
as GradExplNode, with the only difference that in the backpropagation it clips
negative gradients which corresponds to features prone to decreasing the
target activation, and thus considered as noise.

IntegratedGradients:

(Gradient) [80] IntegratedGradients builds on top of simple Gradient-based
methods, like GradExplNode, by integrating the gradient along a path.
Specifically, given $x^{\prime}\in\mathbb{R}^{d}$ a baseline input which
represents a neutral input, often represented by a zero-vector, the resulting
explanation is computed as:

$\textsc{H}_{\textsc{IntegratedGradients}}^{c}[n]=(\boldsymbol{X}_{n}-x^{\prime})\int_{0}^{1}\frac{\partial
f(x^{\prime}+\alpha(\boldsymbol{X}_{n}-x^{\prime}))}{\partial\boldsymbol{X}_{n}}\,d\alpha$
(12)

In short, the explanation corresponds to the integral computation of the
gradients along the straight line path from an input baseline to the original
value of the input. The adoption of this integral computation was shown to
provide better theoretical guarantees then other approaches, as demonstrated
in [80]. Nonetheless, for an efficient implementation, the integral in Eq 12
is substituted by a finite summation. This explainer can be applied even on
edges if the GNN support edge weights. In the rest of the paper, we will refer
to IgNode and IgEdge, whether it is applied to nodes or edges, respectively.

Cam

(Gradient) [57]: Class Activation Map (Cam) maps backward the node features in
the final layer to the input space for identifying important nodes. It
represents a straightforward adaptation of Cam originally developed for
Convolutional Neural Networks [105] to the graph domain. The Cam heat-map for
node $n$ and class $c$ is defined as:

$\textsc{H}_{\textsc{Cam}}^{c}[n]=ReLU\left(\left(w^{c}\right)^{T}\boldsymbol{X}^{(t)}_{n}\right)$
(13)

GradCam

(Gradient) [57]: GradCam represents an extension of Cam. Instead of using the
weights $w^{c}$ to weight the contribution of each feature, GradCam uses the
gradient of the output with respect to node features.

$\textsc{H}_{\textsc{GradCam}}^{c}[n]=ReLU\left(\left(\alpha^{c}\right)^{T}\boldsymbol{X}^{(t)}_{n}\right)$
(14) $\alpha_{k}^{c}=\frac{1}{N}\sum_{n=1}^{N}\frac{\partial
y^{c}}{\partial\boldsymbol{X}^{(t)}_{n,k}}$ (15)

where $\alpha^{c}=[\alpha^{c}_{0}\dots\alpha^{c}_{d^{\prime}}]$. Note GradCam
allows also to compute the heat-map for each layer independently, by simply
replacing the node feature matrix in the above equations with the features of
any specific layer [74].

GNNExplainer

(Perturbation) [91]: GnnExpl was the first algorithm specifically tailored for
GNNs. It is able to provide an explanation both in terms of a subgraph of the
input instance to explain, and a feature mask indicating the subset of input
node features which is most responsible for the GNN’s prediction. Overall, it
is formulated as an optimization problem maximizing the Mutual Information
between the GNN’s predictions and distribution of possible subgraphs. However,
in practical terms, since the optimization problem formulated in this way is
intractable given the exponential number of subgraphs for a specific input
graph, a relaxed version is actually computed, which can be interpreted as a
variational approximation of the distribution of subgraphs. Nonetheless,
despite the non-convex nature of the problem, the authors empirically observed
that the aforementioned approximation together with a regularizer for
promoting discreteness converges to good local minima.

PgExpl:

(Perturbation) [53]: The Parametrized Explainer for GNNs (PgExpl) [53] adopts
a very similar formulation of the explanation problem as GnnExpl where the two
major differences are: _i)_ PgExpl provides solely explanations in terms of
subgraph structures, neglecting explanations in terms of node features; _ii)_
instead of directly optimizing continuous edge and features masks as done by
GnnExpl, it uses Gradient Descend to train a MLP which, given the two
concatenated node embeddings $[X_{i}^{(t)}||X_{j}^{(t)}]$, predicts the
likelihood of the edge ($i$, $j$) being a relevant edge.

PgmExpl

(Surrogate) [84]: PgmExpl builds a surrogate model of the GNN to explain by
building a probabilistic graphical model. Random node features perturbations
are applied to the given instance and, for each perturbation, the algorithm
records the influence of the perturbation to the final prediction. After a
number of perturbations, a dataset is generated and used to learn an
interpretable Bayesian network which serves as final explanation [84].

Name | Category | Task | Mask type
---|---|---|---
GradExplNode | Gradient | Graph/Node | Node
GradExplEdge | Gradient | Graph/Node | Edge
GuidedBp | Gradient | Graph/Node | Node
IgEdge | Gradient | Graph/Node | Edge
IgNode | Gradient | Graph/Node | Node
Cam | Gradient | Graph/Node | Node
GradCam | Gradient | Graph/Node | Node
GnnExpl | Perturbation | Graph/Node | Edge
PgExpl | Perturbation | Graph/Node | Edge
PgmExpl | Surrogate | Graph/Node | Node
Table 1: Summary of explainers analyzed in this work. The columns _Task_
represents to which downstream task the explainer can be applied to, while
_Mask type_ represents whether the explainer returns explanations in terms of
entire node importance, single node features importance, or edge importance.

##  4 Benchmark datasets

In this section we present the graph benchmark datasets employed in our work,
the majority of which represent newly proposed datasets. In designing the new
benchmarks, we took inspiration from Faber et al. [22] who analyzed frequent
biases in evaluating GNN explainers and pointed out that explainers should be
evaluated on controlled benchmarks where the ground-truth evidence for target
labels is known, and that different benchmarks should aim at testing different
aspects of the GNN. In the following we describe in detail each dataset, both
for node and graph classification.

###  4.1 Datasets for graph classification

Grid:

Inspired by the benchmarks presented in Ying et al. [91], the Grid dataset is
composed by 1000 Barabási-Albert (BA) graphs [7]. To half of these 1000 graphs
we attach a $3\times 3$ grid, and the resulting graphs are assigned to the
positive class, while the ones without grid are the negative class The number
of nodes in the BA graph is a uniformly distributed random number between 15
and 30 (for the negative class) and between 6 and 21 (for the positive class).
This guarantees that when adding the grid, the average number of nodes in the
positive class matches the one in the negative class. It is worth mentioning
that in the experiments done by Ying et al. [91], the total number of nodes is
fixed. This benchmark evaluates the ability of the explainers to identify
explanations consisting of a simple connected pattern.

Grid-House:

Grid-House is characterized by two concepts. A $3\times 3$ grid, as in the
previous benchmark, and a house made of 5 nodes. The base structure, to witch
the concepts are attached, is a BA graph with a random number of nodes, and
the final task corresponds to binary classification. The negative class
consists of a BA graph connected to a grid or a house, while the positive
class is composed by a BA graph connected to both a grid and a house. This
benchmark aims at evaluating compositionality, as identifying simple patterns
in isolation is insufficient to characterize the ground truth.

Stars:

The Stars benchmark is characterized by a random graph connected to a variable
number of star-shaped structures (from one to four). For the random graph
generation, this time, we opted for the Erdős-Rényi (ER) random graph model
[21] in order to avoid a possible interference of stars generated in a BA
graph. We defined a three-class classification task, depending on the number
of stars present in each sample: class 0 corresponds to 1 star, class 1 to 2
stars, and class 2 to 3 or 4 stars. Each star has a fixed size of 16 nodes,
and the total number of nodes is uniformly distributed between 30 and 50. This
benchmarks is aimed at evaluating how explainers deal with counting
substructures. Note that standard message-passing GNNs can learn to count
star-like motifs, while more densely connected substructures are out of reach
[13].

House-Color:

None of the previous benchmarks involves node features. Thus, in this
benchmark we test how node features affect explanations. In particular, we
have a random BA graph with (one-hot encoded) random colored nodes
(blue,green,red). To the base BA graphs, we attached from one to three house-
like structures made of five nodes. One of these houses has a uniform color,
which is blue for the negative class and green for the positive one. The other
houses have random colors.

###  4.2 Datasets for node classification

Shapes:

The BA-Shapes dataset (henceforth referred to as Shapes), introduced in Ying
et al. [91], is a widely used dataset for benchmarking GNN explainers [91, 53,
75, 95, 96, 104]. It is composed by 300 nodes and a set of 80 five-node house-
structured network motifs which are randomly attached to the base graph,
generated following the BA model [7]. Nodes are assigned to four categories,
namely they either do not belong to a house (class 0), or they are classified
depending on their structural function in the house: they may be either on the
middle below the roof (class 1), on the base (class 2), or on the top of the
roof (class 3). The expected ground truth explanation is a house motif for all
classes.

Infection:

This benchmark graph has been introduced in Section 5.1 of Faber et al. [22],
and we use it with minor modifications111The code to generate this benchmark
can be found at https://github.com/m30m/gnn-explainability.. Starting from a
directed ER graph [21] with $1000$ nodes and an edge-generation probability
$p=0.004$, a set of $50$ nodes is selected uniformly at random and identified
as infected. The state of each node is mapped to a node feature by one-hot
encoding, i.e., a node has feature $[0,1]$ if it is healthy and $[1,0]$ if it
is infected. The label of a node is defined based on the length of a minimal
directed path to reach this node from an infected one. Namely, if this
distance is denoted as $d$, then the node has label $0$ if $d=0$ (i.e., the
node itself is infected), label $1$ if $d=1$ or $d=2$, and label $2$
otherwise, i.e., $d\geq 3$. We remark that the original dataset included $5$
classes ($d=0,1,2,3$, and $d\geq 4$), but we restrict to three to simplify the
presentation of the results. Accordingly, we employ two-layer networks instead
of the four-layer ones used in [22]. From the definition of the dataset we
identify the expected ground truth explanations of a node $v$ as follows. For
label zero, the explanation is the node itself. For label 1, any directed path
of length one or two from an infected node to $v$ is a valid explanation. For
label 2, the explanation is given by the union of all directed paths of length
up to 2 from any node in the graph to $v$. In the last case, indeed, the
network has to check the entire set of nodes from which $v$ is reachable in at
most two steps to exclude that any of them is infected.

##  5 Assessment of the explanation quality

Evaluating GNNs’ explanations is a challenging task that requires to verify if
and how the explainer is effective in capturing the behaviour of the model.
There are two main strategies to evaluate explanation quality. The first is a
supervised strategy [68, 91, 25], that measures the similarity of the
extracted explanation with an existing ground-truth, which is assumed to be
known. The second strategy is an unsupervised one, that measures how much the
prediction of a GNN on the full graph resembles the prediction computed on the
extracted explanation only, and this does not require to have a ground-truth
explanation available.

We consider a metric for each of these two strategies, in order to capture
different aspects of the quality of an explanation: the plausibility of the
explanation with respect to a ground-truth concept that an accurate GNN is
expected to have learned, and the fidelity of the explanation with respect to
the prediction of the GNN to be explained. Namely, with plausibility we
quantify the consistency between the explainer mask and a human-level
intuition of what a plausible explanation looks like. On the other hand,
fidelity measures the consistency between the model prediction on the full
graph and the on the explanation subgraph, and thus it works with a sort of
model-based instead of human-based ground truth.

In this work we will evaluate explainers according to both strategies, and
study the trade-off between the two.

###  5.1 Single-instance metrics

In the following we detail the metrics we employ, namely _plausibility_ ($P$)
and _fidelity_ ($F$), the latter further divided in its _comprehensiveness_
($F_{com}$) and _sufficiency_ ($F_{suf}$) components.

Each of the scores or metrics is computed for a specific instantiation of a
dataset with $n_{c}\in\mathbb{N}$ classes, a class
$c\in\\{0,1,\dots,n_{c}-1\\}$, a model, and an explainer. We thus assume that
these four are fixed in the following, and we stress that the same computation
has to be repeated for each of these configurations. Moreover, we remark that
the metrics are computed on the training set alone, as we need access to the
labels of the graphs or nodes.

We assume to have a graph $G$ (for graph-classification tasks) or a node $v\in
G$ (for node-classification ones) of class $y=c$, and denote as $g$ the
trained GNN. We have GNNs which output a class probability prediction vector
in form of a soft max, so that the predicted class probabilities sum to $1$.
Since we are considering one class at a time, in the following we assume to be
working with only the output’s entry corresponding to class $c$.

Only the graphs (or nodes) which are correctly classified by the trained GNN
are considered further and run through the explainer, which returns a
corresponding soft explanation mask $G_{\exp}$, which is a copy of the
original graph with associated node or edge weights (for node- or edge-based
explainers).

Before computing the metrics, these soft-mask explanations are processed and
filtered by means of three operations:

  * •

_Conversion:_ Edge masks are converted to node masks by assigning to each node
the weight given by the average of the weights of its incident edges. This
operation makes it easier to compare the scores of edge-based and node-based
explainers, and we choose to use node masks since node-based explainers are
more common in our taxonomy (see Section 2).

  * •

_Filtering:_ For each mask we check the difference between the largest and the
smallest weight. If the difference is below a tolerance $\tau=10^{-3}$, we
discard the graph or node for the given combination of dataset, class, model,
and explainer (the graph or node may still pass the filter for other
settings). The goal of this filter is to discard poorly informative
explanations.

  * •

_Normalization:_ The remaining explanation masks are normalized instance by
instance, so that each explanation has weights in $[0,1]$. This has the effect
of making the computation of the metric uniform across the entire dataset, and
comparing its values to those obtained with other settings.

After these operations have been applied, we compute the metrics as follows.
We formalize each metric as it is computed on a single instance (a graph or a
node), and remark that the overall values of plausibility or fidelity for the
entire (dataset, class, model, explainer)-configuration is obtained by
averaging over these single instances.

##### Plausibility

Let $\overline{G}_{\exp}$ be the expected ground truth for class
$c\in\\{0,1,\dots,n_{c}-1\\}$, represented by a copy of the original graph $G$
with an hard mask highlighting the ground truth nodes. Following [64], the
plausibility $P$ of the explanation is defined as

$P=\operatorname{AucROC}(G_{\exp},\overline{G}_{\exp}),$

i.e., the area under the ROC curve between the computed soft mask and the
ground truth hard mask.

It is clear that this metric can only be computed on benchmarks in which the
ground truth explanation can be defined, and it is completely dependent on
this definition. For each dataset, the ground truths that we are using to
compute $P$ are defined in Section 4. Whenever multiple ground truth are
possible (e.g., the shortest paths in Infection), we compute the plausibility
of each candidate and consider only the highest one.

##### Sufficiency

The fidelity sufficiency $F_{suf}$ [64] is the difference in the predicted
probability when computed on the graph and on the explanation. Since the
explanation is a soft mask, we fix a number of levels $N_{t}\in\mathbb{N}$ and
apply an incremental thresholding with $N_{t}+1$ threshold levels
$t_{k}=k/N_{t}$, $k=0,\dots,N_{t}$, where we define $G_{\exp}(t_{k})$ to be
the hard mask explanation derived from $G_{\exp}$ with threshold $t_{k}$.

Using $N_{t}=100$, we define the metric by

$F_{suf}=\frac{1}{N_{t}-1}\sum_{k=1}^{N_{t}-1}\left(g(G)-g(G_{\exp}(t_{k}))\right),$

i.e., the average change in prediction over all the possible hard masks.

This metric may possibly be negative, and a smaller value indicates a better
result. This indeed may happen only if the explanation provides an higher
probability for the correct class than the entire graph, and thus the
explanation mask manages to filter unnecessary parts of the graph. For this
reason this metric is harder to compare to other scores, so when used alone we
transform it to a renormalized metric $F_{suf}^{\prime}$, which has values in
$[0,1]$ and where $F_{suf}^{\prime}=1$ means a good quality of the
explanation. The normalization takes into account the number of classes
$n_{c}$, and is defined for $p=\frac{n_{c}-1}{n_{c}}$ as

$F_{suf}^{\prime}=1-\frac{F_{suf}+p}{1+p}=\frac{n_{c}}{2n_{c}-1}(1-F_{suf}).$

##### Comprehensiveness

The fidelity comprehensiveness $F_{com}$ [64] is instead the difference in the
predicted probability when computed on the graph and on the complement of the
explanation. Proceeding as in the computation of the sufficiency, we define

$F_{com}=\frac{1}{N_{t}-1}\sum_{k=1}^{N_{t}-1}\left(g(G)-g(G\setminus
G_{\exp}(t_{k}))\right),$

where now $G\setminus G_{\exp}(t_{k})$ is the complement of the hard mask
$G_{\exp}(t_{k})$. This metric may as well assume negative values, but good
explanation have in this case $F_{com}$ close to $1$. (the complement of the
explanation provides low probability).

We are not using this metric for node-classification datasets, since its
evaluation would require to compute the model prediction on $G\setminus
G_{\exp}(t_{k})$, which is a graph that may possibly not contain the node
whose classification we are willing to explain.

##### Fidelity

To aggregate $F_{com}$ and $F_{suf}$ into a unique fidelity metric, for graph-
classification tasks we compute what we call _$f1$ -fidelity_ ($F_{f1})$,
which is defined by

$F_{f1}=2\frac{(1-F_{suf})\cdot F_{com}}{(1-F_{suf})+F_{com}}.$

This is indeed the $f1$ score [40] between $F_{com}$ and $(1-F_{suf})$. In
graph classification tasks, we use this metric in place of $F_{com}$ and
$F_{suf}$.

###  5.2 Aggregation

After we evaluate any of these metrics on each (dataset, class, model,
explainer)-configuration, we need an aggregation mechanisms to assign a unique
score to the models and the explainers over all classes and datasets. This
permits to avoid visualizing the detailed metrics over the entire set of
configurations, and make the results easier to be interpreted.

To define these aggregate metrics we proceed as follows, where the same
procedure are repeated for both plausibility and fidelity:

  1. 1.

For each (dataset, class, model, explainer)-configuration we keep only the
class with the highest value of the metric, i.e., the best explained class.

  2. 2.

For a given dataset, we rank the model-explainer pairs according to the values
selected in point (1). The aggregated score of each pair is the ranking number
$1,2,\dots$.

  3. 3.

The dataset-level scoring of an architecture, of an explainer, or of a
category of explainers (e.g. grad-based, or edge-based) is the average of the
scores of point (2) over all the corresponding pairs.

  4. 4.

To obtain global answers (over all the datasets), the scores of point (2) are
averaged over the datasets, and the operations of point (3) are repeated using
these values.

We mention in particular that the answer to the research questions (Section
7.1) are computed from these aggregations.

To assess instead the stability the explanations over an entire dataset, we
propose a qualitative visualization of the masks which is discussed for each
experimental setting.

##  6 Experimental setting

Any explainer provides an explanation of the prediction of a given instance of
a model, as it is obtained after an optimization process on a specific
dataset. It is thus of paramount importance to identify the choices made in
the training of the networks that will be analyzed in the following.

##### Graph classification

We report in Table 2 the details of the networks used in each graph
classification task, the parameters used for their optimization, and the
resulting train and test accuracies.

For each dataset and each architecture, the table shows the dimensions of the
hidden layers of GNN type (column GNN) and of fully connected type (column
Fully conn.), and any additional parameter used for the definition of the
architecture (see Section 2 for a definition of these hyperparameters). For
example, in the first row the numbers $30-30-30$ and $10-2$ mean that three
Gcn layers are applied, each mapping to a target dimension of $30$, followed
by two fully connected layers with target dimensions $10$ and $2$. We remark
that the final aggregation function is a mean for all datasets except for
Stars, where we used a sum aggregation. The table additionally reports the
learning rate (column LR) and number of epochs used in the training, where an
ADAM optimizer has been used in each case. We remark that these configurations
have been chosen with the guiding principle of obtaining the simplest
configuration achieving a target $0.95\%$ train accuracy.

The last two columns of Table 2 show the resulting train and test accuracies
obtained by the models trained according to these specifications. We remark
that for some configurations it was not possible to achieve the desired target
accuracy, so the table reports an ”X” in place of the accuracy values, and it
reports the values corresponding to the largest architecture which has been
tested. Being not sufficiently accurate, these models have been removed from
the successive analysis.

Dataset | Architecture |  GNN |  Fully conn. | HyperParams | LR | Epochs |  Train Acc |  Test Acc
---|---|---|---|---|---|---|---|---
Grid | Gcn | 30-30-30 | 10-2 | - | 0.001 | 1500 | 0.994 | 0.998
GraphSage | 30-30-30 | 10-2 | - | 0.01 | 3000 | X | X
Gat | 30-30-30 | 10-2 | heads = 1 | 0.01 | 3000 | X | X
Gin | 30-30 | 30-2 | - | 0.001 | 1000 | 1.0 | 1.0
Cheb | 30-30 | 30-2 | - | 0.001 | 1000 | 1.0 | 1.0
MinCutPool | 32-32-32 | 32-2 | - | 0.001 | 700 | 0.92 | 0.93
Set2Set | 30-30-30 | 10-2 | - | 0.001 | 1500 | 0.97 | 0.97
| GraphConv | 30-30 | 30-2 | - | 0.001 | 500 | 1.0 | 1.0
Grid-House | Gcn | 60-60-60-60 | 60-10-2 | - | 0.001 | 7000 | 0.97 | 0.97
GraphSage | 60-60-60-60 | 60-10-2 | - | 0.01 | 3000 | X | X
Gat | 60-60-60-60 | 60-10-2 | heads = 3 | 0.01 | 3000 | X | X
Gin | 30-30 | 30-2 | - | 0.001 | 1000 | 0.99 | 1.0
Cheb | 30-30-30 | 30-2 | - | 0.001 | 1000 | 1.0 | 0.98
MinCutPool | 32-32-32 | 32-2 | - | 0.001 | 700 | 0.95 | 0.95
Set2Set | 60-60-60-60 | 60-10-2 | - | 0.001 | 1500 | 0.97 | 0.97
| GraphConv | 30-30 | 30-2 | - | 0.001 | 500 | 1.0 | 1.0
Stars | Gcn | 70-70-70 | 30-3 | - | 0.005 | 1000 | 0.99 | 1.0
GraphSage | 30-30-30 | 30-3 | - | 0.01 | 3000 | X | X
Gat | 30-30-30 | 10-3 | heads = 1 | 0.01 | 3000 | X | X
Gin | 40-40 | 30-3 | - | 0.001 | 3000 | 0.99 | 1.0
Cheb | 30-30 | 30-3 | - | 0.001 | 1000 | 0.99 | 0.99
MinCutPool | 32-32-32 | 32-3 | - | 0.001 | 400 | 0.99 | 0.99
Set2Set | 70-70-70 | 30-3 | - | 0.001 | 1500 | 0.99 | 0.99
| GraphConv | 30-30 | 30-3 | - | 0.001 | 500 | 0.99 | 0.99
House-Color | Gcn | 30-30 | 15-2 | - | 0.001 | 4000 | 0.99 | 0.99
GraphSage | 30-30-30 | 30-2 | - | 0.001 | 1000 | 1.0 | 0.99
Gat | 10-20-40 | 10-2 | heads = 2 | 0.001 | 500 | 0.99 | 0.99
Gin | 30-30 | 30-2 | - | 0.001 | 1000 | 1.0 | 0.99
Cheb | 30-30 | 30-2 | - | 0.001 | 500 | 1.0 | 1.0
MinCutPool | 32-32 | 32-2 | - | 0.001 | 400 | 0.96 | 0.97
Set2Set | 30-30 | 15-2 | - | 0.001 | 1500 | 1.0 | 0.99
| GraphConv | 30-30 | 30-2 | - | 0.001 | 500 | 1.0 | 1.0
Table 2: Configuration of the graph-classification models, and corresponding
accuracies. The table reports for each dataset and each architecture the
dimension, number, and hyperparameters defining the hidden layers, together
with the optimization parameters, and the obtained train and test accuracies.
The configuration-dataset pairs which did not reach the target $95\%$ train
accuracy are marked with an ”X”, and are not further analyzed in this work.

##### Node classification

In the same way, we report in Table 3 the configurations and accuracies
related to the node-classification tasks.

Dataset | Architecture |  GNN |  Fully conn. | LR | Epochs |  Train Acc |  Test Acc
---|---|---|---|---|---|---|---
Shapes | Gcn | 30-30-30 | 10-4 | 0.0005 | 2000 | 0.98 | 0.98
GraphSAGE | 30-30 | 4 | 0.005 | 2000 | 1.0 | 1.0
Gat | 30-30-30 | 10-4 | 0.0005 | 2000 | X | X
Gin | 70-70-70 | 4 | 0.0005 | 5000 | 0.96 | 0.95
Cheb | 30-30 | 4 | 0.0005 | 300 | 1.0 | 1.0
Infection | Gcn | 30-30 | 30 | 0.005 | 500 | 0.951 | 0.950
GraphSAGE | 30-30 | 30 | 0.005 | 500 | 1.000 | 0.995
Gat | 30-30 | 30 | 0.005 | 500 | 0.977 | 0.975
Gin | 30-30 | 30 | 0.005 | 500 | 0.952 | 0.950
Cheb | 30-30 | 30 | 0.0005 | 600 | 0.993 | 0.950
Table 3: Configuration of the node-classification models, and corresponding
accuracies. The table reports for each dataset and each architecture the
dimensions and number of hidden layers, together with the optimization
parameters, and the obtained train and test accuracies. The configuration-
dataset pairs which did not reach the target $95\%$ train accuracy are marked
with an ”X”, and are not further analyzed in this work.

##  7 Results

###  7.1 Research questions

The comparative analysis of the behavior of the explainers is developed along
the following reasearch questions, which will apply to both node and graph
classification tasks.

  * •

RQ1: How does the architecture affect the explanations? This research question
can be naturally divided into the following three subquestions:

    * –

_RQ1.1: Which is the architecture that has the best explanation? _ With this
question we would like to understand which is the architecture that achieves
the best score, either in terms of f1-fidelity or plausibility.

    * –

_RQ1.2: Which is the easiest architecture to explain?_ This question aims at
finding what is the architecture that is well explained by the greatest number
of explainers.

    * –

_RQ1.3: Which is the hardest architecture to explain?_ In this case we want to
search for an architecture that achieves the lowest score.

  * •

RQ2: How do explainers affect the explanations? Even this question can be
divided into subquestions, which try to cover different open problems related
to state of the art GNN explainers. We identify them as follows:

    * –

_RQ2.1 : Which is the explainer that explains in the best way?_ Here we are
interested in finding the explainer able to obtain the highest Plausibility or
Fidelity.

    * –

_RQ2.2 : Which is the explainer that explains the maximum number of
architectures?_ This aspect is particular important because we need explainers
which are robust with respect to different GNN architectures.

    * –

_RQ2.3 : Which is the category of explainers that provides the best
explanations?_ The subquestion searches for the best category of explainers.
As defined by [95], we consider three macro-categories, namely gradient based
(Grad), perturbation based (Pert), and decomposition based (Dec).

    * –

_RQ2.4 : Which is the best mask type between node and edge?_ By answering this
question we investigate if there is an advantage for explainers based on node
or edge importances.

We would like to remark that RQ2.3 and RQ2.4 are particularly relevant for
future research in GNN explainability, since they may provide actionable
guidelines for the development of new explainers.

  * •

RQ3: How do different types of data affect the explanations? To address this
question we analyze each datasets separately. We remark that each dataset has
been chosen to represent different types of challenges, that will be discussed
in relation to this question.

###  7.2 Graph classification

####  7.2.1 RQ1: How does the architecture affect the explanations?

Table 4 visualizes in a compact form the answer to research questions RQ1,
where the aggregation mechanism described in Section 5.2 has been used to
identify a ranking of the architectures for each dataset across all
explainers, both in terms of plausibility and fidelity, and the highest
ranking architecture is reported for each research question and dataset. Each
column in the figure refers to a specific dataset (Grid to House-Color, see
Section 4), while the first column shows the overall answer obtained by
considering all the datasets at once. Also in this case we refer to Section
5.2 for the details of the computation of this ranking.

Although the architecture with the best explanation (RQ1.1) varies depending
on the dataset, the overall best performer is GraphConv both for plausibility
(paired with GradExplEdge) and fidelity (paired with IgEdge). This indicates a
sort of consistency in the performances of GraphConv: It may not be the single
best one for any dataset, but it is always among the best performing ones, in
a way that makes it to be the best in terms of aggregated scores.

The overall easiest architecture to explain on average (RQ1.2) is Gcn for both
plausibility and fidelity, even if each dataset has a different behaviour. A
possible motivation behind this result may come from the fact that Gcn are
among the simplest models based on message passing, even if other
architectures (e.g. GraphSage and Gin) are equally simple. A difference so
large may thus be related to other aspects that we are unable to identify.
Moreover, we remark that Gcn and Set2Set work with the same underlying GNN
layers (Gcn), and they differ only in the final aggregation operation (a sum
in Gcn, and an LSTM in Set2Set). The better performances of Gcn are thus
hinting to the fact that a different global aggregation alone is responsible
for changing a network’s explainability, and that linear aggregations (Gcn)
are, perhaps unsurprisingly, easier to explain than nonlinear ones (Set2Set).
In general terms, the role of the global aggregation function and its
stability across different tasks is yet to be fully understood, and has not
received great attention in the explanation literature. Thus, we believe that
a systematic study in this direction may be an interesting future direction of
research.

The two metrics of plausibility and fidelity agree only in House-Color. This
is the only dataset with meaningful node features, and we expect that this
makes the learning process more stable and closer to the identification of
concepts closer to GT, so that the same explainer is able to provide high
score explanations for both metrics.

Finally, from the figure it is easy to see that Gin is the most difficult
network to explain (RQ1.3), for both plausibility and fidelity in each dataset
except for Stars. This stark difficulty in explaining Gin is not directly
understandable, especially because it is implemented with a single-layer MLP,
which does not introduces stronger non-linearity than a simpler GCN. This
aspect could be interesting to be addressed by future studies.

Moreover, the difficulty in explaining MinCutPool on Stars may be due to the
fact that in this case the task is to count the number of occurrencies of a
concept (the stars) in a dataset. Although the concept itself is the easiest
possible to identify for message passing based GNNs, it seems that concept-
counting is hard to explain for a pooling mechanism.

Plausibility
---
| All | Grid | Grid-House | Stars | House-Color
RQ1.1 | GraphConv | GraphConv | Cheb | Set2Set | Gcn
RQ1.2 | Gcn | Cheb | Gcn | Set2Set | MinCutPool
RQ1.3 | Gin | Gin | Gin | MinCutPool | Gin
Fidelity
| All | Grid | Grid-House | Stars | House-Color
RQ1.1 | GraphConv | Cheb | Set2Set | GraphConv | Set2Set
RQ1.2 | Gcn | Gcn | MinCutPool | GraphConv | MinCutPool
RQ1.3 | Gin | Gin | Gin | MinCutPool | Gin
Table 4: Experimental answer to RQ1 for graph classification. The table shows
the top-ranking architecture with respect to each subquestion RQ1.1, RQ1.2,
RQ1.3, for each dataset Grid to House-Color, and overall. The rankings are
computed with respect to the Plausibility and the Fidelity metrics, and the
colors identify different architectures.

To offer an additional insight into this fine-grained behavior of Gcn, which
is the easiest architecture to explain according to RQ1.2 in terms of both
metrics, we pick a random element from each dataset and analyze the mask
provided by each explainer. Figure 2 reports these masks, where the rows show
the representative graph from each dataset, and each column corresponds to a
different explainer. The first five explainers return a node importance, while
the last four are edge-based. In both cases, the node or edge importance is
rendered by a different color intensity. We stress once again that only one
graph per dataset is shown in the figure, and thus the following discussion is
of a rather qualitative nature, to be complemented with the metrics discussed
in the first part of this section. Gcn manages to achieve good results in
terms of both plausibility and fidelity, meaning that its explanations are
both close to the expected ground truth and to the actual one used by the
models to realize their prediction. This duality can be observed across the
examples of Figure 2. Indeed, there are cases where the masks identify clearly
the grids in Grid (Cam, GradCam, IgEdge, GradExplEdge, PgExpl), the grid, the
house and the path connecting them in Grid-House (most node-based explainers,
and PgExpl), the stars in Stars (GuidedBp and GradExplNode), and the colored
house in House-Color (GradCam, GuidedBp, GradExplNode). On the other hand, for
many other dataset-explainer combinations the mask is less localized and
interpretable by an human eye, but the overall high scores of this explainer
suggest these explanations could still be good, at least in terms of fidelity
and thus from a model perspective, even if they deviate from the expected
ground truth. A more in-depth analysis of the actual behavior on each dataset
is presented in Section 7.2.3.

Figure 2: Explanation masks (node- or edge-based) computed by the different
explainers on the predictions of Gcn. Each row visualizes the mask computed
for a given random graph from each dataset.

####  7.2.2 RQ2: How do explainers affect the explanations?

The answers to this question are summarized in Table 5, where we used again
the aggregation strategies defined in Section 5.2 to establish a ranking of
the explainers and select the best ones, both for each dataset and overall.

Interestingly, the overall best explainer is different for plausibility and
fidelity, but it is the same when looking at the best performing one in
absolute terms (RQ2.1), and on average across all architectures (RQ2.2). In
fact, the highest plausibility is achieved by GradExplEdge, while the highest
fidelity is achieved by IgEdge. Although different, they both produce an edge
importance mask with a gradient-based mechanism.

At the dataset level, it is worth remarking that House-Color is the only one
whose absolute best explainer (RQ2.1, GuidedBp) and average best one (RQ2.2,
GradCam) are node-based, and this may clearly be due to the fact that this
dataset is the only one with meaningful node features.

In terms of average performances (RQ2.3), perturbation based explainers are
those that best explain all the models for both plausibility and fidelity,
even if the single best ones are edge- and gradient-based (RQ2.1). This
discrepancy is similar to what happens in node classification (Section 7.3.2).
However, while for node tasks the local grad-based explainers worked better,
here perturbation mechanisms are more effective, and this is understandable
since graph classification may require these more global type of explanation.
The answer to this question is particularly remarkable, since perturbation-
based explainers are selected as the best ones for both metrics and for all
datasets, with the single exception of fidelity for Stars, and also overall.

When looking at the average over the entire groups (RQ2.4), edge-mask based
explainers are clearly overperforming node-based ones, in accordance with
RQ2.1 and RQ2.2. We argue that this may be due to the fact that edge-based
explainers have been developed specifically for graph-explanation tasks, while
node-based ones are all adaptations of existing explainers, introduced for
other settings. We remark once again that this is the case only for graph
classification, while for node-based tasks (Section 7.3.2) node-based
explainers appear to be superior.

Plausibility
---
| All | Grid | Grid-House | Stars | House-Color
RQ2.1 | GradExplEdge | IgEdge | PgExpl | IgEdge | GuidedBp
RQ2.2 | GradExplEdge | GradExplEdge | PgExpl | GradExplEdge | GradCam
RQ2.3 | Pert | Pert | Pert | Grad | Pert
RQ2.4 | Edge | Edge | Edge | Edge | Edge
Fidelity
| All | Grid | Grid-House | Stars | House-Color
RQ2.1 | IgEdge | PgExpl | IgEdge | GradExplEdge | PgExpl
RQ2.2 | IgEdge | IgEdge | IgEdge | GnnExpl | GradCam
RQ2.3 | Pert | Pert | Pert | Pert | Pert
RQ2.4 | Edge | Edge | Edge | Edge | Edge
Table 5: Experimental answer to RQ2 for graph classification. The table
reports the top-ranking explainer with respect to each subquestion
RQ2.1-RQ2.4, for each dataset Grid to House-Color, and overall. The rankings
are computed with respect to the Plausibility and the Fidelity metrics, and
the colors identify different explainers.

Similarly to the previous section, Figure 3 zooms into GradExplEdge, which is
the best-ranking explainer according to RQ2.1 and with respect to
plausibility. We show the results for each dataset and each GNN for which
GradExplEdge works, i.e., those that accept edge weights in the training
phase. The high plausibility of the explainer means that it is effective in
identifying the human-expected explanations in the graphs, and this is clearly
visible in the examples of Figure 3: with a few exceptions, the dark red edges
identify the grid in Grid, a path connecting the grid and the house in Grid-
House, the stars in Stars, and the colored house in House-Color.

Figure 3: Explanation masks computed by GradExplEdge on the predictions of the
different models. Each row visualizes the mask computed for a given random
graph from each dataset.

####  7.2.3 RQ3: How do different types of data affect the explanations?

To address the third question we analyze the datasets separately. We remark
that each dataset has been chosen to represent different types of challenges,
that will be discussed in each of the following paragraphs.

##### Grid

In the first dataset, the concept is a grid attached to a random
Barabási–Albert (BA) network. Since the BA component is identical in the
positive and negative classes, the only discriminative subgraph is the grid
(or part of it). In fact, the minimal discriminant subgraph for this dataset
is a square, because the BA component does not contain it.

Figure 4 visualizes the performance of each model-explanation pair when
applied to this dataset. Each pair is located according to the two-dimensional
coordinate given by the resulting Fidelity (horizontal axis) and Plausibility
(vertical axis), and it is identified by the model name and by a color
representing the explainer. We use warm colors for node-based explainers, and
cold colors for edge-based ones.

This visualization permits to identify those model-explanation pairs which
strike the best balance between the two scores, namely, models that maximize
both plausibility and fidelity are in the top right corner of the figure. It
is first relevant to observe that a clear positive correlation emerges for the
top-performing pairs, in the sense that there are no cases where a high
fidelity is achieved without a correspondingly high plausibility, and
viceversa. Moreover, the highest plausibility is achieved by GraphConv with
IgEdge, while Cheb with PgExpl obtain the highest fidelity. These are also the
two Pareto-optimal pairs, i.e., any other pair reaches either a smaller
fidelity or a smaller accuracy. In this sense, they are the best ones
according to this evaluation.

Moreover, it is remarkable to observe that the three best performing pairs
(thus including also the Gcn-GradExplEdge pair) have all edge-based
explainers. This fact is in perfect accordance to the answer to RQ2.4 (Section
7.2.2), which identifies this type of explainers as superior to node-based
ones. Observe however that Grid has no node features, and this may bias this
aspect.

Figure 4: Fidelity and plausibility achieved by all the model-explainer pairs
when applied to Grid. In each pair the name refers to the model, while the
color identifies the explainer.

For these three top-performing pairs (GraphConv-IgEdge, Cheb-PgExpl, Gcn-
GradExplEdge) we further investigate the quality of the explanations by
quantifying their stability. Namely, we are interested in understanding how
the different instances of graphs in the dataset are explained, and if there
is any recurring pattern in these explanations.

This stability is shown in Figure 5, where each edge in the grid motif is
colored according to its importance averaged over all the networks in Grid,
with a color scale ranging from white (for importance 0) to dark red (for
importance 1). This stability is shown in Figure 5, where each edge in the
grid motif is colored according to its importance averaged over all the
networks in Grid, with a color scale ranging from white (for importance 0) to
dark red (for importance 1). The width of each edge is instead proportional to
the standard deviation of the explanation across the dataset, such that
thicker edges describe a larger deviation, hence a smaller stability, and
vice-versa.

We notice that the most stable explanation is given by GraphConv with IgEdge,
since the entire grid motif is dark red and with thin edges. On the other
hand, the most unstable one is Gcn with GradExplEdge, where not all edges are
important, and a considerable deviation is found across the dataset (thick
edges).

Figure 5: Stability of the explanations computed across the dataset Grid for
the three top-performing model-explanation pairs. The colors identify
important edges (dark red), and the edge thickness the variability of the
importance in the dataset.

To conclude the analysis on Grid, Figure 6 shows a prototypical explanation
for each GNN, paired with its best explainer as identified by highest
combination of the two metrics. Overall, we can assert that each GNN can be
explained fairly well if the concept is a simple subgraph into the network. As
anticipated in subsection 7.2.1, Gin is the hardest to explain, while the best
explanations are obtained with grad and perturbation based explanations
producing edge masks.

Figure 6: Examples of explanations provided for each model and its highest
plausibility explainer, when applied to a random sample from Grid. The
plausibility and fidelity values are those of the entire dataset, as reported
in Figure 4.

##### Grid-House

In this dataset class 0 contains either an house or a grid, while class 1
contains both of them. Thus just identifying the presence of a simple pattern
(a grid or a house) is insufficient for discrimination, and the GNN needs to
learn how to combine them. In addition to investigate compositionality, this
dataset can also help investigating an aspect that we name _laziness_. Namely,
a network can address a binary classification problem by learning patterns
characterizing only one of the two classes, and predicting the other one when
these patterns are absent.

As with Grid, we start by the comparative analysis of plausibility and
fidelity for each GNN-explainer pair in Figure 7, where in this case the
results are reported for both class 0 (left panel) and class 1 (right panel).
Here a remarkable difference can be observed between the two classes, since it
is clear that for class 1 a linear correlation is present between the two
metrics for each model-explainer pair, while for class 0 a high plausibility
is associated with a low fidelity, and viceversa. The best explanations are
clearly those for class 1, confirming the laziness phenomenon explained above.
This finding suggests that care should be taken in evaluating instance-based
explanations, as the reason for predicting a certain class could lie in the
absence of evidence in favour of the alternative one.

In more general terms, this result shows a substantial discrepancy between
plausibility and fidelity, and it indicates that it is crucial to jointly
consider both metrics to properly evaluate GNN explainability.

Moreover, for class 1 it is easy to see that MinCutPool, Cheb and Gcn stay on
the Pareto front when paired with PgExpl, which is thus the best explainer in
this case. In the top right of the figure, the majority of the colors are
cold, corresponding to edge-based explainers. In the case of class 0, instead,
it can be verified that the high-plausibility model-explanation pairs (top
left corner in the figure) all capture either the house or the grid, but no
other structure in the graph. On the other hand, the high-fidelity ones
(bottom right, i.e., Set2Set plus IgEdge, MinCutPool plus Cam, and Gcn plus
Cam) have explainers which capture both part of the motif (grid or house), and
part of the BA graph. This confirms the unreliability of the explanations
extracted from the “default” class.

Figure 7: Fidelity and plausibility achieved by all the model-explainer pairs
when applied to Grid-House, for class 0 (left) and class 1 (right). In each
pair the name refers to the model, while the color identifies the explainer.

In terms of stability, Figure 8 shows the average explanations for the three
top-performing explainers for each of the two classes. Regarding class 0, we
can see that both Cheb-PgExpl and Set2Set-GuidedBp identify both the grid and
the house, and this reflects the high plausibility shown in the left panel in
Figure 7. On the other hand, IgEdge does not capture neither the grid nor the
house, but it captures part of the BA component, and this explains the low
plausibility and high fidelity. These observations confirm the insights
obtained from Figure 7.

For class 1 the situation is more uniform, since the three optimal pairs all
achieve a rather similar stability. Indeed, the two motifs are colored in dark
red, and the edges are rather thin. A partial exception is the case of Cheb-
GuidedBp, where the the house motif has a lighter color (and thus a smaller
average importance across the dataset), and the grid has some variability over
the edges’ thickness, indicating a larger standard deviation in their
importance.

Figure 8: Stability of the explanations computed across the dataset Grid-House
for the three top-performing model-explanation pairs, for each of the two
classes. The colors identify important edges (dark red), and the edge
thickness the variability of the importance in the dataset.

Finally, in Figure 9 we show an example of the explanation provided by the
best explainer associated to each model, for both class 0 and class 1. These
explanations are visualized with the same color scale used for the previous
dataset, and computed for a graph randomly selected from each class in Grid-
House. The high plausibility pairs are clearly visible since they identify the
house for class 0 (Cheb-PgExpl and MinCutPool-PgExpl) and both structures and
their connection for class 1 (MinCutPool-PgExpl). Interestingly, even the high
fidelity ones are easy to spot (GradCam-Set2Set for class 0, Cheb-PgExpl for
class 1), and this indicates a good agreement between the expected and learned
concepts.

Figure 9: Examples of explanations provided for each model and its highest
plausibility explainer, when applied to a random sample from Grid-House. Each
row shows the results for one of the two classes. The plausibility and
fidelity values are those of the entire dataset, as reported in Figure 7.

##### Stars

This dataset has three classes: each graph is obtained starting from an
Erdős–Rényi graph, to which we attach one (class 0), two (class 1), three or
four (class 2) stars. This dataset thus evaluates GNN explainers on concepts
involving counting.

In order to enable this motif-counting capability, we used for all
architectures a sum-based global aggregation in place of a mean-based one,
which would prevent the networks from being able to count occurrences of
motifs. Indeed, mean-based versions of all models of all models were trained
as well, but none of them reached the threshold train accuracy of $95\%$ (see
Section 6).

The behaviors of each model-explainer pair is visualized in Figure 10, with a
panel for each class.

Class 0 is explained well by explainers producing node masks, and especially
by GradExplNode on GraphConv. However, all the model-explanation pairs have a
fairly limited plausibility when compared with the other datasets, and none of
them has a plausibility larger than $0.8$.

For class 1 the best combined performances are achieved by Gin explained by
IgNode and Cam, even if also in this case the fidelity is almost always below
0.8, with instead a quite high plausibility. This indicates that these
explainers may be good in identifying the expected ground truth (the stars),
thus obtaining high plausibility, but that the presence of these motifs alone
may be insufficient for predicting the class, when not complemented by a non-
negligible part of the ER graph.

The right panel of Figure 10 shows the results for class 2. Also in this case
the plausibility is very limited across the entire set of models and
explanations. Looking at the fidelity alone, it is evident that the best
performing explainers are those that produce an edge mask. In this case, a
direct inspection of the explanations shows that these explainers not only
capture the stars, but also paths connecting them. This makes the explanations
farther away from the expected ground truth (thus obtaining low plausibility),
but apparently provide better masks for the model to correctly identify the
class.

From these results, it seems clear that there may be some clash between the
identification of the motifs (high plausibility) and the fact that these
motifs are sufficient to predict the class (low fidelity). To try to explain
this behavior, we evaluated all the trained networks on the exact expected
ground truth explanations, i.e., four graphs obtained by one, two, three or
four disconnected stars. For all these graphs, all the models predict class 2
(i.e., that with three or four stars attached to an ER graph), thus completely
missing the correct classification for class 0 and class 1. These stars are
thus clearly insufficient to characterize what the networks use for
prediction. This result reveals the difficulty in defining the plausibility of
an explanation, even in the presence of explicitly defined ground truths.

Figure 10: Fidelity and plausibility achieved by all the model-explainer pairs
when applied to Stars, for class 0 (left) and class 1 (right). In each pair
the name refers to the model, while the color identifies the explainer.

Figure 11 shows the stability of the explanations when restricted to the the
stars which identify the three classes. We remark that both node- and edge-
based explainers are visualized, and thus the colouring and thickness may
apply to either the nodes or the edges.

In class 0, explainers that produce a node mask (IgNode on Set2Set, and
GradExplNode on GraphConv) capture really well the star (intensity of the
color) with a low standard deviation (size of the nodes), i.e., they are
extremely stable. Remarkably, in the case of GraphConv the explainer gives no
importance to the center of the star, while for Set2Set it does. On the other
hand, GnnExpl on Gin identifies the star but with a low intensity, and this
explains the corresponding low plausibility observed in Figure 10.

For class 1, all the three best model-explainer pairs captures the stars, even
if Cam has a higher standard deviation. Surprisingly, Cam gives to the central
node of the star always the highest importance (dark color and small size),
while IgNode does the opposite (light color and large size). It is interesting
to observe that both masks are reasonable ways to identify the two stars, and
it may be difficult to recognize one or the other as the actual correct
explanation. This difference is made even more interesting by the fact that
the two explanations apply to the same model (Gin), and that the resulting
fidelity and plausibility are essentially the same (see Figure 12, central
panel).

Finally, for class 2 all the explainers captures the stars with high
importance and low standard deviation, without significant differences.

Figure 11: Caption

Figure 12 reports, for each model and each class, an example explanation
provided by the corresponding best explainer. All masks are computed on a
graph randomly drawn from the dataset for each class.

Figure 12: Examples of explanations provided for each model and its highest
plausibility explainer, when applied to a random sample from Grid-House. Each
row shows the results for one of the two classes .The plausibility and
fidelity values are those of the entire dataset, as reported in Figure 10.

##### House-Color

In this dataset we would like to explore how the node features affect the
explanations. In particular, both classes have a BA base graph with attached
one, two, or three houses, and each node has a random color, except for one
house that has all nodes colored blue (class 0) or green (class 1). In
particular, the two classes represent essentially the same type of pattern,
and thus we have no reason to expect that a _lazy_ GNN should prefer one or
the other, and consequently no way to anticipate a difference in their
explainability.

The comparison of fidelity and plausibility in shown in Figure 13. To avoid
visualizing too many results, the figure is limited to those pairs with both
plausibility and fidelity greater than $0.5$.

Also in this case a linear correlation between the two metrics is clearly
present, even if there is a group of outliers with high plausibility and low
fidelity (the MinCutPool models with explainers GradExplNode and GuidedBp, for
the two classes). In this case, a closer inspection of the single explanations
reveals that the explanations mask are able to capture well the colored house,
thus achieving a large plausibility, but they contain also a significant
amount of noise that spoils the fidelity. An example of this behavior can be
observed in the examples in Figure 15.

Moreover, for this dataset the optimal pairs are based on GraphConv and
Set2Set, with explanations GradExplEdge, IgEdge, PgExpl. In particular, edge-
based explainers are the top performing ones also in this case.

Another remarkable aspect is the fact that for each model-explainer pair, only
one between class 0 and class 1 achieves high scores (i.e., both high fidelity
and high accuracy). This suggests again a lazy behaviour for the GNN even in
the case in which both classes are equally easy to explain (Figure 13), where
some GNNs are learning to characterize class 0 and other class 1, but none
modelling both.

Figure 13: Fidelity and plausibility achieved by all the model-explainer pairs
when applied to House-Color, where the two classes (0 and 1) are represented
in the left and right panel. In each pair the name refers to the model, while
the color identifies the explainer. The plot is limited to metrics larger than
$0.5$ to simplify the visualization.

In Figure 14 we report the average explanation for the three top-performing
pairs, which all comprise edge-based explainers. Differently from the previous
datasets which had no node feature, the figure visualizes also the color of
the node feature close to each node. In all cases the explanation is very
strong across the dataset (dark red color), with a minimal standard deviation
for GraphConv-GradExplEdge, and a maximal one for GraphConv-IgEdge.

Figure 14: Stability of the explanations computed across the dataset House-
Color for the three top-performing model-explanation pairs. The colors
identify important edges (dark red), and the edge thickness the variability of
the importance in the dataset.

Examples of explanation masks computed on random samples from House-Color are
reported in Figure 15, where again we show for each class and for each model
only the corresponding best performing explainer.

Once again, explainers that produces edge features are more effective in terms
of plausibility and fidelity. It is worth mentioning that there are no
explainers having high fidelity in both classes, arguing the thesis that GNNs
are lazy and learn only one class. On the other hand, at least one class for
each GNN can be explained by an explainer. As one may expect, the only
exception is the Gat architecture, because the attention mechanism strongly
operate on node features, and none of the studied explainers operate on node
features.

Figure 15: Examples of explanations provided for each model and its highest
plausibility explainer, when applied to a random sample from Grid-House. Each
row shows the results for one of the two classes .The plausibility and
fidelity values are those of the entire dataset, as reported in Figure 13.

###  7.3 Node classification

####  7.3.1 RQ1: How does the architecture affect the explanations?

To answer this question, we summarize the performance of the different
architectures across all explainers by using the aggregation mechanism
described in Section 5.2. The plausibility and fidelity results for each of
the two datasets Shapes and Infection, and the overall results are reported in
Table 6.

The most explainable architectures are GraphSage for the plausibility metric
(explained by GradCam), and Gin for fidelity (explained by GnnExpl). They are
clearly identified as such by both RQ1.1 and RQ1.2, i.e., both as single best
performing architectures and mean best performing ones. The same holds also
for the single dataset, even if with a small variability, and this suggests
that the answer is quite solid and stable. The difference between the two
metrics indicates that for GraphSage one gets explanations that better
resemble the expected ground truth, and are thus closer to a human-level
explanation. On the other hand, for Gin one obtains explanations with a higher
fidelity, meaning that they better capture the actual patterns that the
trained Gin uses in building its decisions.

The hardest architectures to explain on average (RQ1.3) are also identified
quite stably, and they are again different for the two metrics. In terms of
plausibility Cheb is the unique hardest to explain architecture, while from
the point of view of fidelity GraphSage is the hardest to explain both overall
and for Shapes. We have obtained no insight into this behavior so far. The
result for fidelity, in particular, highlights a potential problem with
explaining GraphSage predictions. While its explanations are the most
plausible in term of ground-truth (as shown by RQ1.1 and RQ1.2), they tend to
diverge from the actual behaviour of the network, at least as measured by the
fidelity score. This confirms the importance of considering both metrics, and
the difficulty in defining a unique perspective in evaluating the quality of
an explanation. In particular, it may be possible the case that the fidelity
metric (here represented by the sufficiency alone as in all node-
classification experiments) is not effective in capturing the model
predictions.

| Plausibility | Fidelity
---|---|---
| All | Shapes | Infection | All | Shapes | Infection
RQ1.1 | GraphSage | GraphSage | Gcn | Gin | Gcn | Gin
RQ1.2 | GraphSage | Gcn | GraphSage | Gin |  Gcn/Gin | Gin
RQ1.3 | Cheb | Cheb | Cheb | GraphSage | GraphSage | Gcn
Table 6: Experimental answer to RQ1 for node classification. The table shows
the top-ranking architecture with respect to each subquestion RQ1.1, RQ1.2,
RQ1.3, both for the single datasets Shapes and Grid-House, and overall. The
rankings are computed with respect to the Plausibility and the Fidelity
metrics.

Figure 16 shows examples of explanation masks computed by the different
explainers on GraphSage, which is the architecture with the highest average
plausibility (RQ1.2), over all explainers which passed the filtering procedure
(Section 5.2). For each dataset we visualize a sample node and its 2-hop
neighborhood (directed in the case of Infection, i.e., the set of nodes from
which the ego node is reachable following two edges). For both datasets we
focused on nodes with label 1, i.e., the base of the roof in Shapes, and a
node at distance one or two from an infected node in Infection. This means
that their associated ground truths are the entire house in Shapes, and a path
of length one or two in Infection (in this case multiple possible ground truth
may exist, and only the one with the highest plausibility is considered for
the computation of the metric). Despite GraphSage being the model with the
highest plausibility, it is clear from these examples that there is a high
variability across nodes and explainers. Moreover, for Shapes the house is
well highlighted by GradCam, PgmExpl, and GnnExpl, but the explanation
additionally includes spurious nodes and edges with equally large importance.
A similar situation can be observed for Infection. In both cases, a finer
inspection (see Section 7.3.3) reveals that the plausibility of GraphSage,
despite being the highest on average over classes and explainers, is fairly
limited for class 1: the values are below $0.6$ for class 1 in Shapes (Figure
18), and with high spread and mean around 0.6 for class 1 in Infection (Figure
20). We remark that for both datasets, other classes achieve an higher
plausibility.

In any case, this variability across the same dataset has to be taken into
account, and a word of caution is in order when using instance-based
explanations, since the single masks are those which are actually utilized to
inspect the model and try to extract information on its decisions. Their
usefulness may vary largely from node to node.

Figure 16: Explanation masks (node- or edge-based) computed by the different
explainers on the predictions of GraphSage on Shapes and Infection. Each row
visualizes the mask computed for a given random graph from each dataset. For
each dataset, only the explainers which passed the filtering procedure are
shown.

####  7.3.2 RQ2: How do explainers affect the explanations?

Table 7 shows that, while GradCam provides the single best explanation in
terms of plausibility, GnnExpl is the best one both in terms of mean
performances (RQ2.2) for both metrics, and maximal performances (RQ2.1) for
plausibility, and can be thus considered as the overall best performing
explainer in this setting. It is worth remarking that this is a perturbation-
and edge-based explainer.

When looking at average performances for the entire category the situation is
instead different, and it turns out that gradient- (RQ2.3) and node-based
(RQ2.4) explainers are to be preferred. In particular, PgExpl (perturbation-
and edge-based) has very poor performances and this lower the aggregates
scores of the corresponding categories. This fact is possibly justifiable
since we are dealing with node classification tasks, where local explanations
like those provided by gradient based explainers may be more effective.
Moreover, since meaningful explanation should be limited to a node’s $k$-hop
neighborhood, it is reasonable to expect that highlighting single nodes
instead of edges is sufficient to explain the decision. In particular, the
node itself is already defining the relevant neighborhood, and we may thus
expect that the additional missing information required to elaborate a
decision is given by the nodes’ labels.

| Plausibility | Fidelity
---|---|---
| All | Shapes | Infection | All | Shapes | Infection
RQ2.1 | GradCam | GradCam | GradCam | GnnExpl | PgExpl | GradCam
RQ2.2 | GnnExpl | GradCam | GnnExpl | GnnExpl | GnnExpl | GnnExpl
RQ2.3 | Grad | Pert | Grad | Grad | Pert | Grad
RQ2.4 | Node | Edge | Node | Node | Edge | Node
Table 7: Experimental answer to RQ2 for node classification. The table shows
the top-ranking explainer with respect to each subquestion RQ2.1, RQ2.2,
RQ2.3, RQ2.4, both for the single datasets Shapes and Grid-House, and overall.
The rankings are computed with respect to the Plausibility and the Fidelity
metrics.

In the same setting of Figure 16, we report in Figure 17 examples of
explanations masks obtained by GnnExpl, which has the highest average
plausibility over all architectures and classes - RQ2.2. Also here,
architectures not passing the filtering step have been removed (Section 5.2).
In this case a better localization of the explanations may be observed for
Shapes for all models. Indeed, all architectures have a plausibility above
$0.8$ in class 1 in Shapes (Figure 18).

Figure 17: Explanation masks (node- or edge-based) computed on the predictions
of GnnExpl by the different explainers, both on Shapes and Infection. Each row
visualizes the mask computed for a given random graph from each dataset. For
each dataset, only the explainers which passed the filtering procedure are
shown.

####  7.3.3 RQ3: How do different types of data affect the explanations?

We analyze the two datasets separately, in order to highlight the different
aspects and challenges that they represent.

##### Shapes

The comparative visualization of the plausibility and fidelity of each
architecture-explainer pair is reported in Figure 18, where we visualize only
the classes 1 to 3 (structural elements of a house, see Section 4.2), while we
omit class 0, which having no structure is less interesting from the point of
view of explanations.

No clear correlation emerges between the two metrics, except partially for
class 1, which is the only one with architecture-explainer pairs with both
high fidelity and high plausibility. Several pairs achieve very high
plausibility (even close to $1$, and for all three classes), but always with
low fidelity (values bounded by $0.6-0.7$ depending on the class). The only
outlier is the Gcn-PgExpl pair for class 2 and 3, which has a plausibility of
about $0.9$ and fidelity of $0.8$ (class 2), and $0.7$ (class 3),

The very high plausibility indicates that the explainers agree with the human
definition of a ground truth, which is thus correctly defined to be the same
for all classes (the house structure). On the other hand, this in turn results
in an observed low fidelity. This seems to suggest that it is enough to have a
few house elements missing from the explanation (the plausibility is never
equal to 1) to spoil the model predictions, and that indeed the entire motif
has to be observed to compute a prediction. It is possible moreover that an
high plausibility is a proxy for a low sparsity of the explanation, which may
thus miss some crucial edges. On the other hand, explanations with lower
plausibility may be more spread, thus covering the entire house structure,
even if with some spurious additional edge. This result highlights again that
the sufficiency alone may be non very informative in some settings.

Regarding the well-performing Gcn-PgExpl pair, a sort of two-class lazyness
can be observed: the explanations are good for class 2 and 3, while they have
fairly limited plausibility and fidelity (around $0.5$) for class 1 . This may
suggest that the nodes in class 1 (the middle of the house) are classified by
Gcn as not being in any other class.

Figure 18: Fidelity and plausibility achieved by all the model-explainer pairs
when applied to Shapes. In each pair the name refers to the model, while the
color identifies the explainer. Class 0 is omitted from the visualization
since it is less relevant for the discussion of the explainers.

Examples in Figure 19 shows explanation masks returned for each model by its
explainer which reaches the highest plausibility. A significant overlapping
between the explanation mask and the house structure (the ground truth) can be
observed, even if in most cases the mask is at least partially spread also
over other nodes.

Figure 19: Examples of explanations provided for each model by its highest
plausibility explainer, when applied to a random node from Shapes. Each row
shows the results for one of the three house-structure classes. The
plausibility and fidelity values are those of the entire dataset, as reported
in Figure 18.

##### Infection

The pairs of models and explanations are shown in Figure 20 according to their
plausibility and fidelity on the three classes. We first remark that, out of
the two edge-based explainer considered here, only GnnExpl passes the
filtering step (Section 5.2), more specifically GnnExpl with Gcn (for class
1,2) and with Gat and GraphSage (for all classes).

Also in this case no correlation appears among the two metrics, while there
are several pairs that reach a high value of only one of the two metrics. It
is again possible that even relatively high values of the plausibility
comprise explanations where some relavant part of the ground truth is missing,
thus achieving low fidelity. For this dataset the necessity of covering the
entire motif is even more clear than for Shapes, since here single nodes
missing from an explanation may break the minimal paths connecting the node to
an infected one. Exceptions are GraphSage-GradCam and GraphSage-IgNode for
class 1, and especially Gcn-GradExplNode for class 2, which have both metrics
above values of $0.8$.

With the exception of Gcn, class 2 exhibits a clear lack of explainability,
indicating a preference of GNN architectures in focusing on class 0 and 1.
This laziness is perfectly sensible, since it is much easier to model class 2
in terms of a lack of paths from nearby infected nodes (i.e., the negation of
the other classes) than by trying to characterize all possible longer paths
from an infected node. The exception to this pattern is Gcn-GradExplNode,
which has very high scores for class 2, but is instead significantly
unexplainable for class 1 and class 0, where it is below the threshold for
visualization. This is reasonable since Gcn has a simple message passing -
aggregation mechanism, which may facilitate the identification of lack of
infected nodes in the $2$-hop neighborhood (since the infected status is the
node feature itself, see Section 4.2), even if GraphSage has a completely
analogous functioning mechanism, and it achieves nevertheless poorer results.
At this stage, we are not able to identify the actual mechanism that make
their performances so different.

Figure 20: Fidelity and plausibility achieved by all the model-explainer pairs
when applied to Infection. In each pair the name refers to the model, while
the color identifies the explainer.

Example explanations are shown in Figure 21 for each model paired with the
explainer which explains it with the highest plausibility. We show only class
1, since class 0 is trivial to visualize (the explanation is the actual node),
while for class 2 the local networks happen to have too many edges and their
visualization is not clear enough. We thus omit both since their visualization
does not provide significant insights. In this case, it is difficult to
observe a good accordance between the mask and the ground truth (a path
connecting an infected node with the node to be explained). This happens
despite the relatively high plausibilities (Figure 20), and demonstrates again
that care should be taken in considering single-instance explanations for the
interpretation of a model’s prediction.

Figure 21: Examples of explanations provided for each model by its highest
plausibility explainer, when applied to a random node from Infection. Class 0
and class 2 are omitted since their visualization does not provide significant
insights. The plausibility and fidelity values are those of the entire
dataset, as reported in Figure 20.

##  8 Discussion

The main objective of this work is to experimentally study the effectiveness
of explainers on different GNNs and types of data, identifying current
pitfalls and formulating possible future directions in the field of GNN
explainability.

Given that GNNs may learn different concepts, possibly less intuitive, than
those expected by humans, defining ground truths is not a trivial task and may
be prone to human biases. A first simple remark is that GNNs, as neural
networks in general, tend to be lazy and learn a ”default” option for one of
the classes. For this reason, a high accuracy does not necessarily imply
having learned the ground-truth concept for the class. A useful insight that
emerged from our analysis is that these human biases can often be detected by
comparing plausibility and fidelity. Indeed, an explainer with high fidelity
and low plausibility (or vice-versa) clearly indicates a discrepancy between
what is considered to be the ground truth and the concept learned by the GNN.

It is important to remark, however, that fidelity alone may not be the optimal
choice for both graph and node classification. In the case of graph
classification, the aggregation used to convert nodes embedding into a graph
embedding directly influences the fidelity. In particular, sum aggregation,
which is needed to allow GNN to count substructures, often negatively affects
fidelity, with the mere ground-truth structure achieving relatively low
fidelity because of the reduced number of nodes which in turn reduces the norm
of the overall embedding. The aggregation mechanism is a crucial component of
GNNs and its decision directly affects the quality of the explanation.
Nonetheless, there is a lack of work studying the impact of the aggregation
mechanism on explainability. This is an interesting direction for further
research. Reliably measuring fidelity can be tricky for node classification
too. On the one hand, comprehensiveness is poorly defined when explaining node
predictions (see Section 5). On the other hand, measuring fidelity only in
terms of sufficiency introduces a bias that favours larger explanations.
Indeed, finding the optimal metric for evaluating explainers is still an open
problem that deserves further investigation.

Identifying a general category of explainers working consistently better than
others is challenging. However, our results suggest that gradient-based
explainers are more suited in explaining node classification networks. We
conjecture that this is due to the fact that in node classification, the
gradient is computed only on the neighborhood of the node under investigation,
limiting the receptive field of the network. On the other hand, the category
of explainers that best explain GNNs for graph classification are those that
focus on edges, be it by perturbation or gradient. In general, edge-based
explainers outperform node-based ones whenever node features are not
available.

Concerning GNN architectures, there is a substantial difference in their
explainability, regardless of the explainer that best suits each of them. We
believe that this results is surprising yet not fully understood, given that
explainers are usually aimed to be model agnostic. Given the importance of
explaining predictions, it would be advisable to include explainability as a
metric to be optimized when designing novel GNN architectures.

##  9 Conclusion

In this survey we proposed an extensive experimental study to quantify the
effectiveness of the existing explainers and to obtain actionable
recommendations to select the optimal method for a given task.

For this comparison we evaluated ten explainers on eight different GNN
architectures, all chosen to represent the most commonly utilized instances in
a vast taxonomy of existing solutions. These methods have been tested on six
different datasets for both graph and node classification, carefully designed
or adapted to model interesting and challenging aspects of real-world
datasets.

As a result of our experimental study, we were able to describe significant
criticalities in the common explainer evaluation methods, and to identify
recurring patterns that make some category of explainers preferable in certain
situations. In particular, we proposed insights on which explainer to use, and
how to use it, depending on the available data.

Our findings naturally point to promising future research directions, and
especially highlight once more that much has yet to be understood to achieve a
satisfactory GNN explainability.

##  10 Code and data availability

Code and explanations can be found at this link:
https://github.com/AntonioLonga/Explaining-the-Explainers-in-Graph-Neural-
Networks

## References

  * [1] Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik.  Evaluating explainability for graph neural networks.  arXiv preprint arXiv:2208.09339, 2022.
  * [2] Chirag Agarwal, Marinka Zitnik, and Himabindu Lakkaraju.  Probing gnn explainers: A rigorous theoretical and empirical analysis of gnn explanation methods.  In International Conference on Artificial Intelligence and Statistics, pages 8969–8996. PMLR, 2022.
  * [3] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini.  Global explainability of gnns via logic combination of learned concepts, 2022.
  * [4] David Baehrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus-Robert Müller.  How to explain individual classification decisions.  The Journal of Machine Learning Research, 11:1803–1831, 2010.
  * [5] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473, 2014.
  * [6] Federico Baldassarre and Hossein Azizpour.  Explainability techniques for graph convolutional networks.  arXiv preprint arXiv:1905.13686, 2019.
  * [7] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  science, 286(5439):509–512, 1999.
  * [8] Sourya Basu, Jose Gallego-Posada, Francesco Viganò, James Rowbottom, and Taco Cohen.  Equivariant mesh attention networks.  arXiv preprint arXiv:2205.10662, 2022.
  * [9] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi.  Spectral clustering with graph neural networks for graph pooling.  In International Conference on Machine Learning, pages 874–883. PMLR, 2020.
  * [10] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Hans-Peter Kriegel.  Protein function prediction via graph kernels.  Bioinformatics, 21(suppl_1):i47–i56, 2005.
  * [11] Cătălina Cangea, Petar Veličković, Nikola Jovanović, Thomas Kipf, and Pietro Liò.  Towards sparse hierarchical graph classifiers.  arXiv preprint arXiv:1811.01287, 2018.
  * [12] Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković.  Combinatorial optimization and reasoning with graph neural networks.  In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 4348–4355. International Joint Conferences on Artificial Intelligence Organization, 8 2021.  Survey Track.
  * [13] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.  Can graph neural networks count substructures?  In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
  * [14] Dan C Cireşan, Ueli Meier, Jonathan Masci, Luca M Gambardella, and Jürgen Schmidhuber.  High-performance neural networks for visual object classification.  arXiv preprint arXiv:1102.0183, 2011.
  * [15] Kevin Clark, Minh-Thang Luong, Quoc V Le, and Christopher D Manning.  Electra: Pre-training text encoders as discriminators rather than generators.  arXiv preprint arXiv:2003.10555, 2020.
  * [16] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Jun Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang.  A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability.  ArXiv, abs/2204.08570, 2022.
  * [17] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  Advances in neural information processing systems, 29, 2016.
  * [18] 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.  arXiv preprint arXiv:2010.11929, 2020.
  * [19] Alexandre Duval and Fragkiskos Malliaros.  Higher-order clustering and pooling for graph neural networks.  In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 426–435, 2022.
  * [20] Vijay Prakash Dwivedi and Xavier Bresson.  A generalization of transformer networks to graphs.  arXiv preprint arXiv:2012.09699, 2020.
  * [21] Paul Erdős and Alfréd Rényi.  On random graphs i.  Publicationes mathematicae, 6(1):290–297, 1959.
  * [22] Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer.  When comparing to ground truth is wrong: On evaluating gnn explanation methods.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 332–341, 2021.
  * [23] Xiang Fu, Tian Xie, Nathan J Rebello, Bradley D Olsen, and Tommi Jaakkola.  Simulate time-integrated coarse-grained molecular dynamics with geometric machine learning.  arXiv preprint arXiv:2204.10348, 2022.
  * [24] Thorben Funke, Megha Khosla, and Avishek Anand.  Hard masking for explaining graph neural networks.  2020\.
  * [25] Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand.  Z orro: Valid, sparse, and stable explanations in graph neural networks.  IEEE Transactions on Knowledge and Data Engineering, 2022.
  * [26] Jianliang Gao, Jun Gao, Xiaoting Ying, Mingming Lu, and Jianxin Wang.  Higher-order interaction goes neural: a substructure assembling graph attention network for graph classification.  IEEE Transactions on Knowledge and Data Engineering, 2021.
  * [27] Dobrik Georgiev and Pietro Liò.  Neural bipartite matching, 2020.
  * [28] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl.  Neural message passing for quantum chemistry.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, page 1263–1272, 2017.
  * [29] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In International conference on machine learning, pages 1263–1272. PMLR, 2017.
  * [30] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * [31] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi.  A survey of methods for explaining black box models.  ACM computing surveys (CSUR), 51(5):1–42, 2018.
  * [32] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * [33] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval.  Wavelets on graphs via spectral graph theory.  Applied and Computational Harmonic Analysis, 30(2):129–150, 2011\.
  * [34] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  Neural Networks, pages 389–416.  Springer New York, New York, NY, 2009.
  * [35] David Haussler et al.  Convolution kernels on discrete structures.  Technical report, Technical report, Department of Computer Science, University of California …, 1999.
  * [36] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  Neural Comput., 9(8):1735–1780, nov 1997.
  * [37] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs.  Advances in neural information processing systems, 33:22118–22133, 2020.
  * [38] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang.  Graphlime: Local interpretable model explanations for graph neural networks.  IEEE Transactions on Knowledge and Data Engineering, 2022.
  * [39] Priyank Jaini, Lars Holdijk, and Max Welling.  Learning equivariant energy based models with equivariant stein variational gradient descent.  Advances in Neural Information Processing Systems, 34:16727–16737, 2021.
  * [40] K Sparck Jones and Cornelis Joost Van Rijsbergen.  Information retrieval test collections.  Journal of documentation, 1976.
  * [41] Arash Keshavarzi Arshadi, Milad Salem, Arash Firouzbakht, and Jiann Yuan.  Moldata, a molecular benchmark for disease and target based machine learning.  Journal of Cheminformatics, 14, 03 2022.
  * [42] Megha Khosla.  Privacy and transparency in graph machine learning: A unified perspective.  arXiv preprint arXiv:2207.10896, 2022.
  * [43] Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong.  Pure transformers are powerful graph learners.  arXiv preprint arXiv:2207.02505, 2022.
  * [44] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [45] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * [46] Junhyun Lee, Inyeop Lee, and Jaewoo Kang.  Self-attention graph pooling.  In International conference on machine learning, pages 3734–3743. PMLR, 2019.
  * [47] Bin Li, Yunlong Fan, Yikemaiti Sataer, Zhiqiang Gao, and Yaocheng Gui.  Improving semantic dependency parsing with higher-order information encoded by graph neural networks.  Applied Sciences, 12(8):4089, 2022.
  * [48] Jianxin Li, Hao Peng, Yuwei Cao, Yingtong Dou, Hekai Zhang, Philip Yu, and Lifang He.  Higher-order attribute-enhancing heterogeneous graph neural networks.  IEEE Transactions on Knowledge and Data Engineering, 2021.
  * [49] Peibo Li, Yixing Yang, Maurice Pagnucco, and Yang Song.  Explainability in graph neural networks: An experimental survey.  arXiv preprint arXiv:2203.09258, 2022.
  * [50] Wei Li, Ruxuan Li, Yuzhe Ma, Siu On Chan, David Pan, and Bei Yu.  Rethinking graph neural networks for the graph coloring problem, 2022\.
  * [51] Yang Liu, Yao Zhang, Yixin Wang, Feng Hou, Jin Yuan, Jiang Tian, Yang Zhang, Zhongchao Shi, Jianping Fan, and Zhiqiang He.  A survey of visual transformers.  arXiv preprint arXiv:2111.06091, 2021.
  * [52] Ana Lucic, Maartje A. Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri.  Cf-gnnexplainer: Counterfactual explanations for graph neural networks.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 4499–4511. PMLR, 28–30 Mar 2022.
  * [53] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang.  Parameterized explainer for graph neural network.  Advances in neural information processing systems, 33:19620–19631, 2020.
  * [54] Lucie Charlotte Magister, Dmitry Kazhdan, Vikash Singh, and Pietro Liò.  Gcexplainer: Human-in-the-loop concept-based explanations for graph neural networks, 2021.
  * [55] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4609, 2019.
  * [56] Sabyasachi Patra and Anjali Mohapatra.  Review of tools and algorithms for network motif discovery in biological networks.  IET systems biology, 14(4):171–189, 2020.
  * [57] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann.  Explainability methods for graph convolutional neural networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10772–10781, 2019.
  * [58] Marcelo Prates, Pedro H. C. Avelar, Henrique Lemos, Luis C. Lamb, and Moshe Y. Vardi.  Learning to solve np-complete problems: A graph neural network for decision tsp.  In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, 2019.
  * [59] Omri Puny, Matan Atzmon, Heli Ben-Hamu, Edward J Smith, Ishan Misra, Aditya Grover, and Yaron Lipman.  Frame averaging for invariant and equivariant network design.  arXiv preprint arXiv:2110.03336, 2021.
  * [60] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.  Improving language understanding by generative pre-training, 2018.
  * [61] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  J. Mach. Learn. Res., 21(140):1–67, 2020.
  * [62] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents.  arXiv preprint arXiv:2204.06125, 2022.
  * [63] Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini.  Recipe for a general, powerful, scalable graph transformer.  arXiv preprint arXiv:2205.12454, 2022.
  * [64] Mandeep Rathee, Thorben Funke, Avishek Anand, and Megha Khosla.  Bagel: A benchmark for assessing graph neural network explanations.  arXiv preprint arXiv:2206.13983, 2022.
  * [65] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  ”Why should i trust you?” Explaining the predictions of any classifier.  In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144, 2016.
  * [66] Gabriel Roccabruna, Steve Azzolin, and Giuseppe Riccardi.  Multi-source multi-domain sentiment analysis with BERT-based models.  In Proceedings of the Thirteenth Language Resources and Evaluation Conference, pages 581–589, Marseille, France, June 2022. European Language Resources Association.
  * [67] T Mitchell Roddenberry and Santiago Segarra.  Hodgenet: Graph neural networks for edge data.  In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 220–224. IEEE, 2019.
  * [68] Benjamin Sanchez-Lengeling, Jennifer Wei, Brian Lee, Emily Reif, Peter Wang, Wesley Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko.  Evaluating attribution for graph neural networks.  Advances in neural information processing systems, 33:5898–5910, 2020.
  * [69] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov.  Interpreting graph neural networks for nlp with differentiable edge masking.  arXiv preprint arXiv:2010.00577, 2020.
  * [70] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schutt, Klaus-Robert Müller, and Grégoire Montavon.  Higher-order explanations of graph neural networks via relevant walks.  IEEE transactions on pattern analysis and machine intelligence, 2021\.
  * [71] Robert Schwarzenberg, Marc Hübner, David Harbecke, Christoph Alt, and Leonhard Hennig.  Layerwise relevance visualization in convolutional text graph classifiers.  arXiv preprint arXiv:1909.10911, 2019.
  * [72] Daniel Selsam and Nikolaj Bjørner.  Guiding high-performance sat solvers with unsat-core predictions.  2019\.
  * [73] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill.  Learning a SAT solver from single-bit supervision.  In International Conference on Learning Representations, 2019.
  * [74] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In Proceedings of the IEEE international conference on computer vision, pages 618–626, 2017.
  * [75] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li.  Reinforcement learning enhanced explainer for graph neural networks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 22523–22533. Curran Associates, Inc., 2021.
  * [76] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt.  Weisfeiler-lehman graph kernels.  Journal of Machine Learning Research, 12(9), 2011.
  * [77] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  IEEE signal processing magazine, 30(3):83–98, 2013.
  * [78] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  arXiv preprint arXiv:1312.6034, 2013.
  * [79] Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller.  Striving for simplicity: The all convolutional net @articleluo2020parameterized, title=Parameterized explainer for graph neural network, author=Luo, Dongsheng and Cheng, Wei and Xu, Dongkuan and Yu, Wenchao and Zong, Bo and Chen, Haifeng and Zhang, Xiang, journal=Advances in neural information processing systems, volume=33, pages=19620–19631, year=2020 .  arXiv preprint arXiv:1412.6806, 2014.
  * [80] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In International conference on machine learning, pages 3319–3328. PMLR, 2017.
  * [81] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [82] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [83] Oriol Vinyals, Samy Bengio, and Manjunath Kudlur.  Order matters: Sequence to sequence for sets.  arXiv preprint arXiv:1511.06391, 2015.
  * [84] Minh Vu and My T Thai.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  Advances in neural information processing systems, 33:12225–12235, 2020.
  * [85] Rui Wang, Robin Walters, and Rose Yu.  Approximately equivariant networks for imperfectly symmetric dynamics.  arXiv preprint arXiv:2201.11969, 2022.
  * [86] Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth McMillan, and Risto Miikkulainen.  Neurocomb: Improving sat solving with graph neural networks.  arXiv:2110.14053, 2021.
  * [87] Boris Weisfeiler and Andrei Leman.  The reduction of a graph to canonical form and the algebra which appears therein.  NTI, Series, 2(9):12–16, 1968.
  * [88] Weibin Wu, Yuxin Su, Xixian Chen, Shenglin Zhao, Irwin King, Michael R. Lyu, and Yu-Wing Tai.  Towards global explanations of convolutional neural networks with concept attribution.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8649–8658, 2020.
  * [89] Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  In International conference on machine learning, pages 2048–2057. PMLR, 2015.
  * [90] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.