Task-Agnostic Graph Neural Explanations
Authors: Yaochen Xie
Sumeet Katariya
Xianfeng Tang
Edward W Huang
Nikhil Rao
Karthik Subbian
Shuiwang Ji
Venue: ICLR 2022 Submitted (2022)
Keywords: Explainability
interpretability
graph neural networks
self-supervised learning

Abstract: Graph Neural Networks (GNNs) have emerged as powerful tools to encode graph structured data. Due to their broad applications, there is an increasing need to develop tools to explain how GNNs make decisions given graph structured data. Existing learning-based GNN explanation approaches are task-specific in training and hence suffer from crucial drawbacks. Specifically, they are incapable of producing explanations for a multitask prediction model with a single explainer. They are also unable to provide explanations in cases where the GNN is trained in a self-supervised manner, and the resulting representations are used in future down-stream tasks. To address these limitations,  we propose a Task-Agnostic Graph Neural Explainer (TAGE) trained under self-supervision without knowledge about downstream tasks.   TAGE enables the explanation of GNN embedding models without downstream tasks and allows efficient explanation of multitask models. Our extensive experiments show that TAGE can significantly speed up the explanation efficiency while achieving explanation quality as good as or even better than current state-of-the-art GNN explanation approaches.

Under review as a conference paper at ICLR 2022
TASK-AGNOSTIC GRAPH EXPLANATIONS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have emerged as powerful tools encode graph structured data. Due to their broad applications, there is an increasing need to develop tools explain how GNNs make decisions given graph structured data. Existing learning- -based GNN explanation approaches are task-specific in training and hence suffer from crucial drawbacks. Specifically, they are incapable of pro- ducing explanations for multitask prediction model with a single explainer. They are also unable to provide explanations in cases where the GNN trained in a self-supervised manner, and the resulting representations are used in future down- stream tasks. To address these limitations, we propose a Task- Agnsstii GNN Explainer (TAGE) trained under self-supervision with no knowledge of down- stream tasks. TAGE enables the explanation of GNN embedding models with- out downstream tasks and allows efficient explanation of multitask models. Our extensive experiments show that TAGE can significantly speed up the explanation efficiency by using the same model explain predictions for multiple downstream tasks while achieving explanation quality as good as or even better than current state-of- the GNN explanation approaches.
INTRODUCTION
Graph neural networks (GNNs) Kipf & Welling 2017: Veličković et al. 2018 Xu et al. 2019) have achieved remarkable success in learning from real-world graph-structured data due their unique ability to capture both feature-wis wise and topological information. Extending their success, GNNs are widely applied in various research fields and industrial applications including quantum chem- istry (Gilmer et al., 2017), drug discovery (Wu et al., 201 8, Wang et al. 2020), social networks (Fan al.) 2019), and recommender systems (Ying et al.) 2018). While multiple approaches have been proposed and studied to improve GNN performance, GNN explainability is an emerging area and has a smaller body of research behind it. Recently, explainability has gained more attention due to an increasing desire for GNNs with more security, fairness, and reliability. Being able to provide good explanation to a GNN prediction increases model reliability and reduces the risk of incorrect predictions, which is crucial in fields such molecular biology, chemistry, fraud detection, etc.
Existing methods adapting the explanation methods for convolutional neural networks (CNNs) or specifically designed for GNNs have shown promising explanations multiple types of graph data. A recent survey (Yuan et af.) 2020) categorizes existing explanation methods into gradient-based. perturbation, decomposition, and surrogate methods. In particular, perturbation methods involve learning or optimization (Ying et al. 2019 Luo et al.) 2020 Yuan et al. 2002 Lin et al. (202I) and, performance in terms of explanation quality. These methods train post-hoc explanation models on top of the prediction model be explained. Earlier approaches like GNNExplainer (Ying et al.) 2019) require training or optimizing an individual explainer for each data instance, i.e., graph or node to be explained. In contrast, PGEXxpainne (Luo et al.. 2020) performs inductive learning, i.e., it only requires one-time training. and the explainer can be generalized to explain all data instances without individual op- timization. Compared to other optimization-base improves the efficiency in terms of time cost without performance loss by learning.
while bearing higher computational costs, generally achieve state-of-the-ee
explanation methods, PGExplainer significantly
However, even -fate-of-the-ar art explanation methods like PGExplainer are still task- sesk-specific at train- ing and hence suffer from two crucial drawbacks. First, current methods are inefficient in explaining multitask prediction for graph-structung data. For example, one may need to predict multiple chem- ical properties in drug discovery for molecular graph. In particular, ToxCast from MoleculeNet has

---

Under review as a conference paper at ICLR 2022
End-too-nd teak-speciiic explainers
Two-atage fesk-agnaasic explanations
lask-spec explainor
lask-speciicc explaiier?
Tack-sper spee-p explainer 3
Embedding Explainer
Downstream Explainer
Condition vdimension importanc))
Important subgrash
GNN-MLP
MLP
Predictions
Nodelgraph embedding
Multtiskk model
Embodding Model
preciction
Nead mako diflecied explainers explain mullttook
prediction model. Unable without downstream.
Trained
downstream
euplain muulipple
Figure 1: A comparison between typical end-to-end task-specific GNN explainers and the proposed task-agnostic explanation pipeline. To explain a multitask model, typical explanation pipelines need optimize multiple explainers, whereas the two-stage explanation pipeline only learns one embed- ding explainer that can cooperate with multiple lightweight downstream explainers.
167 prediction tasks. In these cases, it common to apply a single GNN model with multiple output dimensions to make predictions for all tasks. However, one is unable employ single explainer to explain the above model, since current explainers are trained specifically to explain one prediction task. As result, in the case of ToxCast, one must train 167 explainers explain the GNN model. Second, in industry settings, it is common to train GNN models in a two-stage fashion due to scal- ing, latency, and label sparsity issues. The first stage trains a GNN- embedding model with a massive amount of unlabeled data in an unsupervised manner to learn embeddings for nodes or graphs. The second stage trains lightweight models such multilayer perceptrons (MLPs) using the frozen embeddings as input to predict the downstream tasks. In the first stage, the downstream tasks are usually unknown or undefined, and existing task-specific explainers cannot be applied. Also, there can be tens to hundreds of downstream tasks trained on these GNN embeddings, and training a separate explainer for each task is undesirable and downright impossible.
To address the above limitations, we present new task-agnostic explanation pipeline, shown in Figure where we decompose a prediction model into a GNN embedding model and a downstream model, designing separate explainers for each component. We design the downstream explainers to cooperate with the embedding explainer. The embedding explainer is trained using a self-supervised training framework, which dub Task-Agnostic GNN Explainer (TAGE), with no knowledge of downstream tasks, models, or labels. In contrast to existing explainers, the learning objective for TAGE is computed at the graph node embeddings without involving task-related predictions. In addition to eliminating the need for downstream tasks in TAGE, we argue that the self-supervision performed on the embeddings can bring additional performance boost in terms of the explanation quality compared to existing task-specific basclines such as GNNExplainer and PGExplainer.
We summarize our contributions follows: We introduce the task task-agnostic explanation problem and propose a two-stage explanation pipeline involving an embedding explainer and a downstream explainer. This enables the explanation of multiple downstream tasks with a single embedding ex- plainer. 2) We propose a self-supervised training framework TAGE, which is based on conditioned contrastive learning to train the embedding explainer. TAGE requires no knowledge of downstream tasks. 3) We perform experiments on real-world datasets and observe that TAGE outperforms isting lcarning-bast based explanation baselines in terms of explanation quality, universal explanation ability, and the time required for training and inference.
TASK-AGNOSTIC EXPLANATIONS
2.1 NOTATIONS AND LEARNING-BASERR GNN EXPLANATION
Our study considers the attributed graph G with node set and edge set We formulate the attributed graph tuple of matrices X), where A (0, 1)IVixIVI denotes the adjacency matrix and X RIVlxd, denotes the feature matrix with feature dimension of dy. We assume that the prediction model F' that is to be explained operates on graph-structured data through two components: a GNN-baser embedding model and lighter downstream models. Denoting the input space by G, node-level embedding model &,, - R/V[xd takes graph input and computes
2

---

Under review as a conference paper at ICLR 2022
Table I: Comparisons properties of common GNN explainers. Inductivity and lask-agnosticism are inapplicable for gradient/rule-basee methods as they do not require learning. In the last column, we show the number of required explainers for a dataset with N samples and M tasks.
Learning
Inductive
Task-agnostic
explainers required
Gradient- Rule-basee
No
GNNExplainer ( (Ying et al. 2019)
Yes
No
No
M
N
SubgraphX (Yuan et al. 2021)
Yes
No
No
M
PGExplainer (Luo et al. 2020
Yes
Yes
No
M
Task-agnostic explainers
Yes
Yes
Yes
embeddings of dimension for all nodes in the graph, whereas a graph-level embedding model Eg RIxd computes embedding for the input graph. Subsequently, the downstream model R computes predictions for the downstream task based on the embeddings.
D D -
Typical GNN explainers consider a spek-ip GNN-based model as a complete unit, i.e., F := D Given graph G' and the GNN-based model F to be explained, the subgraph Gsub that contributes the most to the final prediction made by F. In other words, claim that given prediction is made because F captures crucial information provided by some subgraph Gubb- The learning- based (or cetimizzation-baseee GNN explanation employs a parametric explainer To associated with the GNN model F' to compute the subgraph Gsub of the given graph data. Concretely, the explainer To computes the importance score for each node or edge, denoted as w, or ways or masks for node attributes denoted as m. It then selects the subgraph Guub induced by important nodes and edges, i.e,, whose scores exceed a threshold I, and by masking the unimportant attributes. our study, we follow Luo et al. (202)), focusing on the importance of edges to provide explanations to GNNs. Formally, we have Goub (V, Esub) = (G()), where Exab = {11,, 0y) (v,, U,) E E, way 2 t}.
goal is to identify
2.2 TASK-AGNOSTIC EXPLANATIONS
As introduced in Section all existing learning- based or optimization -baeed explanation approaches are task-specifie and hence suffer from infeasiblity or inefficiency in many real-application scenar- ios. In particular, they are of limited use when downstream tasks are unknown or undefined and fail to employ a single explainer to explain a multitask prediction model.
To enable the explanation of GNNs in two-stage training and multitask scenarios, we introduce a new explanation paradigm called the task-agnostic explanation. The task-agnostic explanation considers a whole prediction model as an embedding model followed by any number of downstream models. focuses explaining the embedding model regardless of the number or the existence of downstream models. In particular, the task-ap aask-agnottic explanation trains only one explainer (1(gg) to explain the embedding model E, which should satisfy the following features. First, given input graph G, the explainer (t should be able provide different explanations according to specific downstream tasks being studied. Table 1 compares the properties of common GNN explanation methods and the desired task-agnostic explainers in multitask scenarios. Second, the explainer (ttag) can be trained when only the embedding model is available, e.g.. at the first stage of a two-stage training paradigm, regardless of the presence of downstream tasks. When downstream tasks and models are unknown,
Th T(tag) can still identify which components of the input graph are important for certain embedding dimensions of interest.
THE TAGE FRAMEWORK
Our explanation framework TAGE follows the typical scheme of GNN explanation introduced in the previous section. It provides explanations by identifying important edges in given graph and removing the edges that lead to significant changes in the final prediction. Specifically, the goal of the TAGE is to predict the importance score for each edge in a given graph. Different from existing methods, the proposed TAGE breaks down typical end-to-end GNN explainers into two components. We now provide general descriptions and detailed formulations to the proposed framework.
3

---

Under review as a conference paper at ICLR 2022
3.1
EXPLANATION PIPELINE
Following the principle of the desired task-agnostic explanations, we introduce the task-agnostic explanation pipeline, where a typical explanation procedure is performed in two steps. In particular, decompose the typical end-to-end learning- GNN explainer into two parts: the embedding explainer TT and the downstream explainer Tdown, corresponding to the two components in the two-stage training and prediction procedure. We compare the typical explanation pipeline and the two-stage explanation pipeline in Figure [ The embedding explainer and downstream explainers can be trained or constructed independently from each other. In addition, the embedding explainer can cooperate with any downstream explainers to perform end-to-end explanations on input graphs.
The downstream explainer aims to explain task-specific downstream models. As downstream mod- els are usually lightweight MLPs, we simply adopt gradient-based explainers for downstream ex- plainers without training. The downstream explainer takes a downstream model and the graph or node embedding vector as inputs and computes the importance score of each dimension on the em- bedding vector. The importance scores then serve as a condition vector input to the embedding explainer. Given the condition vector, the embedding explainer explains the GNN-based embed- ding model by identifying an important subgraph from the input graph data. In other words, given different condition vectors associated with different downstream tasks models, the embedding explainer can provide corresponding explanations for the same embedding model. Formally, we denote the downstream explainer for models from 9 by Tdown 9 x Rd + R which maps in- put models and embeddings into importance scores m for all embedding dimensions. We denote the embedding explainer associated with the embedding model & by TTg R x G 9, which maps a given graph into a subgraph of higher importance, conditioned on the embedding dimension importance m E Rd.
The training procedures of the embedding explainer are independent of downstream tasks or down- stream explainers. particular, the downstream explainer is obtained from the downstream model only, and the training of the embedding explainer only requires the embedding model and the in- put graphs. As downstream models are usually constructed as stacked fully connected (FC) layers and the explanation of FC layers has been well studied, our study mainly focuses on the non-trivial training procedure and design of the embedding explainer.
3.2 TRAINING EMBEDDING EXPLAINER UNDER SELF- SULE--UPEEIIIION
A straightforward idea of explaining an embedding model with no knowledge of downstream tasks is to employ existing explainers and perform explanation on the pretext task, such as graph recon- struction (Kipf & Welling 2016) or context prediction (Hu et al., all] 2020), used during the pre-training of GNNs. However, such explanations cannot generalize to future downstream tasks as there are lim- ited dependencies between the pretext task and downstream tasks. Therefore, training an embedding explainer without downstream models or labels is challenging, and it is desirable to develop a gen- cralizable training approach for the embedding explainer. To this end, we propose a self-supervised learning framework for the embedding explainer.
The learning objective of the proposed framework seeks to maximize the mutual information (MI) between two embeddings with certain dimensions masked, i.e., one of the given graphs and one of the corresponding subgraph of high importance induced by the explainer. We introduce a masking vector p E Rd to indicate specific dimensions of embeddings explanation, we obtain the masking vector from the importance vector computed by any downstream explainer Taown. As no downstream importance vector is available at training, we sample the mask- ing vector p from a multivariate Laplace distribution due to the sparse gradient assumption, i.e., only a few dimensions are of high importance. Formally, the MI-based learning objective
which maximize MI. During
max (pIMI(p & E(G), p @ ((To(p))))))
(1)
where MI(-,-) computes the mutual information between two random vectors, p denotes the random masking vector sampled from a certain distribution, (p G) computes the subgraph of high impor- tance, and @ denotes the element-wise multiplication. which applies masking to the embeddings E()) Figure 2 outlines the training framework and objective. Intuitively, given an input graph and the desired embedding dimensions to be explained, the explainer To predicts the subgraph whose
4

---

Under review as a conference paper at ICLR 2022
Graph-level Yask
Training Framework
P
Emnbadiin Model
Masked ambediina e 8(G)
Projection
X
MLP
GNN
Ris
Edge
Fnn
Concatenation
importance
Noxee-loval Task
Explainer
Randomtt genersted
Selest propntant Edges
condition vector p
MLP
G, E1h O))
GNN
[Ri) R-) Steryel
E(Tatp.
Masked subgraph embocdi
Emoodiingg
Element-wise Mullipliatioo
Mutual information Maximization
Figure 2: Overviews of the self-supervised training framework for the embedding model (right) and the architecture of the parametric explainers (left). During training, we generate random condition vectors input to the embedding explainer and mask the embeddings. The learning objective seeks to maximize the mutual information between two embeddings on certain dimensions.
embedding shares the maximum mutual information with the original embedding on the desired dimensions.
Practically, the mutual information is intractable and is hence hard to directly compute. A common approach to achieve efficient computation and optimization is to adopt the upper bound estimations of mutual information, namely, the -anson-Shannon Estimator (JSE) (Nowozin al.) 2016) and the InfoNCE (Gutmann & Hyvärinen 2010). These upper bound estimations also referred to as contrastive loss and are widely applied in self-supervised representation learning (Hjelm et al. 2019
(Sun al. 2019 Veličković al. (2019) for both images and graphs. Adopting these estimators, the objectives are efficiently computed as
log [o( 2:)² (p 21,0))] + N2 N
log [I ((D 2D) 2n,0)]]
min
N
(
N log Σ Ej exp (pp(((p) 2 2;)²² (p 2;.0)}
expl 2,) 8 z1,0)}
min
(3)
N
for ISE and InfoNCE, respectively, where N denotes the number of samples in a mini-batch, o denotes Sigmoid function, and 2,,0 are embeddings of the original graph G; and its subgraph (G.)., or target nodes of the two graphs. Our objective involves condition vectors as masks on the embeddings, which differs from typical contrastive loss used in self-supervised representation learning. We hence call the proposed objective the conditioned contrastive loss.
To restrict the size of subgraphs given by the explainer, additionally add size regularization term R, computed as the averaged importance score, to the above objectives. In the case where edge importance scores Wij E [0, 1] are computed, the regularization term computed as
R(G) Σ
A /wiyl Ae [wis log wij (1 wiy) log(1 1 wiy)],
(EEN))E
where Às and de hyper-parameters controlling the size and the entropy of edge importance scores, respectively.
3.3 EXPLAINER ARCHITECTURES
Embedding explainers. Inspired by explainer architectures used by PGExplainer, we adopt the multilayer perceptron (MLP) to predict the importance score Wij for each edge (u, uj) E E, on top of learned embeddings z; and zj of the two nodes connected by the edge. Edges with scores higher than threshold are considered important edges that remain in the selected subgraph. In order for the embedding explainer to cooperate with different downstream explainers and provide diverse explanations for different tasks, it additionally requires condition vector as input indicating
5

---

Under review as a conference paper at ICLR 2022
the specific downstream task to be explained. We handle the condition vector in similar manner to Conditional GAN (Mirza & Osindero 2014). Formally, the graph-level embedding explainer takes the embeddings, 2, and 2j. and the condition vector p inputs and computes the importance score by
Wij MLP,, (|=: æ,] & (f)(
(5)
where [::-] denotes the concatenation along the feature dimension, @ denotes the element-wise mul- tiplication, denotes the activation function, and fg R R is linear projection. The node-level embedding explainer takes an additional node embedding as its input, as the explainers expected to predict different scores for the same edge when explaining different target nodes. The formulation of computing the importance score is as follows,
Wij = MLP,, n (1 Rgi Starget @ (fx())))
(6)
where fg IR + Rd is linear projection, and Starget denotes the embedding of the target node whose prediction is to be explained.
Downstream explainers. We adopt the gradient-based explainer to explain the downstream models. Formally, given an input embedding x and its prediction probabilities D(z) E 1] among all C classes, we compute the gradient of the maximal probability w.r.t. the input embedding:
i maxexc D(z)[c)
E Riddd
Oz
where [c] denotes the probability for class c. To convert the gradient into the condition vector, we further perform normalization and only take positive values reflecting only positive influence to the predicted class probability, ie.,, p = (eo.m())
EXPERIMENTAL STUDIES
We conduct two groups of quantitative studies evaluating the explanation quality and the universal explanation ability, i.., training a single explainer explain all downstream tasks, of TAGE. We then compare the efficiency of multiple learning-based GNN explainers in terms of training and explanation time cost. We further provide visualizations to demonstrate the explanation quality as well as the ability to explain GNN models without downstream tasks.
4.1 DATASETS
To demonstrate the effectiveness of the proposed TAGE on both node-level and graph-level tasks, we evaluate TAGE on three groups of real-world datasets that contain potentially multiple tasks. The datasets are described as follows and their statistics are summarized in Appendix
MoleculeNet. The MoleculeNet (Wu et al.) 2018) library provides collection of molecular graph datasets for the prediction of different molecule properties. a molecular graph, each atom in the molecule is considered as a node, and each bond is considered molecule properties is graph-level task. We include three graph classification tasks from Molecu- leNet to evaluate the explanation of graph-level tasks: HIV, SIDER, and BACE.
edge. The prediction of
Protein-Protein Interaction. The Pooten--Protein Interaction (PPI) ZZiniik & Leskoved 2017 dataset documents the physical interactions between proteins in 24 different human tissues. In PPT graphs, each protein is considered as a node with its motif and immunological features, and there an edge between binary labels associated with different protein functions. As different protein functions are not ex- clusive each other, the prediction of each protein function considered an individual task. We utilize the first five out of 121 tasks to evaluate the explanation of node-level tasks.
proteins if they interact with each other. Each node in the graphs has 121
E-commerce Product Network. The E-commerce Product Network (EPN constructed with subsampled, anonymized logs from an e-commerce store, where entities including buyers, products, merchants, and reviews are considered as nodes, and interactions between entities are considered as edges. We subsample the data for the sake of experimental evaluations and the dataset characteristics
Proprictary dataset

---

Under review as a conference paper at ICLR 2022
BACE
SIDER
HIV
0.7
0.5
0.6
0.5
TAGExpaine
Fidellyy
0.4
0.4
PGExpairer
0.3
0.3
0.3
DeaplIFT
GNNExpliiner
0.2
GredCam
0.1
0.11
0.1
0.95
0.9
0.65
0.9
0.95
0.85
0.8
0.75
PPL (Task
PPI (Task 1)
(Tak 21
0.5
0.6
0.4
0.5
TAGExp aleer
Fideity
0.3
PGExplaine
0.3
GNNExplainar
0.2
0.2
0.3
DeepLIFT
GradDAM
0.1
0.2
0.1
0.7
Sparsity
Sparsity
Sparsily
Figure 3: Quantitative performance comparisons with baseline methods six tasks from Molecu- leNet (top row) and PPI (bottom row). The curves are obtained by varying the threshold for selecting important edges.
do not mirror actual production traffic. We study the explanation of the classification of fraudulent entities (nodes). where the prediction for different types of entities are considered as individual tasks. We evaluate our framework specifically on classifications of the buyer, merchant, and review nodes.
4.2 EXPERIMENT SETTINGS AND EVALUATION METRICS
For each real-world dataset, we evaluate explainers on multiple downstream tasks that share single embedding model. For consistency with industrial use cases, we perform the two-stage training paradigm obtain GNN models to be explained. In particular, the GNN-based embedding model in an unsupervised fashion. We then freeze the embedding model and use the learned embeddings train individual downstream models structured 2-layer MLPs. Specifically, for graph-level classification tasks in MoleculeNet, we employ the GNN pretraining strategy context prediction (Hu et al. (2020) to train a 5-layer GIN (Xu al. 2019) the embedding model on ZINC-2M (Sterling & Irwin 2015) containing 2 million unlabeled molecules. For the node-level classification on PPI. we employ the sulf-super training method GRACE (Zhu al.) 2020) to train a 2-layer GCN (Kipf & Welling, 2017) on all 21 graphs from PPI without using labels. For the larger-scale node-level classification on EPN, we use graph autoencoder (GAE) (Kipf & Welling 2016) to train the embedding model on sampled subgraphs of EPN. More implementation details are provided in Appendix [
first use unlabeled graphs train
As the involved real-world datasets do not have ground truth for explanations, we follow previous studies (Pope et al. 2019; Yuan et al.) 2020 2021) to adopt a fidelity score and a sparsity score to quantitatively evaluate the explanations. Intuitively, the fidelity score measures the level of change in the probability of the predicted class when removing important nodes or edges, whereas the sparsity score measures the relative amount of important nodes nodes associated with important edges. A formulation of the scores are provided in Appendix B. Note that compared to explanation evaluation with ground truths, the fidelity score is considered more faithful to the model, especially when the model makes incorrect predictions, in which case the explanation ground truths become inconsistent with evidence to making the wrong predictions. In practice, one needs trade off between the fidelity score and the sparsity score by selecting the proper threshold for the importance.
4.3 QUANTITATIVE STUDIES
We conduct two groups of quantitatively experimental comparisons. We first demonstrate the ex- planation quality of individual tasks in terms of the fidelity score and the sparsity score. We do this by comparing TAGE with multiple baseline methods including non- con-learning-bate based methods Grad- CAM (Pope et al. 2019) and DeepLIFT (Shrikumar et al.) (017)) as well as learning- based methods GNNExplainer (Ying et al., 2019) and PGExplainer (Luo et al,, 2020). We do not include other optimization or search-based methods such Konte-Carlo tree search (Jin et al. 2020) due the
7

---

Under review as a conference paper at ICLR 2022
Table 2: Fidelity scores with controlled sparsity on the node-level classification dataset PPI. Each column corresponds to an explainer model trained on (or without) a specific downstream task. Un- derlines highlight the best explanation quality in terms of fidelity, on the same level of sparsity.
PGExplainer (trained on)
TAGB
Eval on
Task 0
Task
Task 2
Task 3
Task 4
w/o downstream
Task 0
0.184 20.3443
-0.005
=0.268
0.033
=0.335
0.034
10.310
0.018
19.194
0.271 +0.385
Task
0.046 #0.447
0.197 =0.380
0.043 #0.114
0.008
#0.297
0.021 10.183
0.300 #0.415
Task 2
0.028 +0.434
0.001 =0.283
0.345
#0.458
0.024 #0.320
0.097 #0.320
0.499 40.480
Task 3
0.075 #0,364
-0.015 #0.219
0.036
#0.317
0.262
#0.418
0.040
#0.221
0.289 +0,427
Task 4
0.035 #0.413
-0.021 #0.238 0.223 #0.438
0.075 #0.374
0.242 +0.373
0.330 #0.442
significant time cost on real-world datasets. Note that to show the effectiveness of universal expla- nations over different downstream tasks, only train one embedding explainer for all tasks in dataset, on top of which a gradient- -hased downstream explainer is applied to explain multiple down- stream tasks. In contrast, for existing learning- based methods, we need to train multiple explainers to explain downstream tasks individually. For all methods, we vary the threshold for selecting im- portant nodes or edges and compare how fidelity scores change over sparsity scores on each task and dataset. The results are shown in Figure 4 In particular, TAGE outperforms other baaning-bbsee explainers on BACE, SIDER, and PPI (tasks O and 1). For HIV and PPI (task 2), TAGE more effective at higher sparsity levels, i.e., when fewer nodes are considered important and masked.
To justify the necessity of task-agnostic explanation and demonstrate the universal explanation abil- ity of TAGE, we include PGEExpaiiner as our baseline and compare the explanation quality when adopting single explainer to explain multiple downstream tasks. For PGExplainer, we train mul- tiple explainers
different downstream tasks and evaluate each explainer different downstream tasks. For TAGE, we train one explainer without downstream tasks and evaluate it on different down- stream tasks. Results shown in Table 2 (PPI) and Appendix D (MoleculeNet and EPN) indicate that task-specific explainers fail to generalize to different downstream tasks and hence are unable to pro- vide universal explanations. On the other hand, the task agnossgi explainer. although trained without downstream tasks, can provide explanations with even higher quality for any downstream tasks.
GNNExplainer and PGExplainer should generally outperform task-agnostic explainers, as they specific to data examples or tasks. This should especially be true when TAGE and PGExplainer have the same level of parameters. However, we surprisingly find that TAGE outperforms the learning- based baselines. One possible reason can be the non-injective characteristic of the downstream MLPs on top of GNNs, where different embeddings can produce similar downstream prediction results. Due to this characteristic, the learning objective of TAGE computed between embeddings brings stronger supervision than the objective computed between final predictions, as the latter ob- jective does not guarantee consistency between embeddings or between input graphs and subgraphs.
4.4 MULTITASK EXPLANATION EFFICIENCY
A major advantage of the task-agnostic explanation is that it removes the need for training individual explainers, which consumes the majority of the total time cost to explain a model on dataset. We hence evaluate the efficiency of TAGE in terms of time cost for explanation and compare it to the two learning- -baee explainer baselines. We record the time cost for the training and inference of different explanation methods on the same dataset and device, shown in Table 3 All results are obtained from running the explanation on the PPI dataset with 121 node classification tasks with single Nvidia Tesla V100 GPU. Although the inference time cost of TAGE is slightly higher than that of PGExplainer, the results show TAGE costs significantly less time than GNNExplainer and PGExplainer, especially in the multitask cases (T > 1). TAGE allows the explanation of many downstream tasks within reasonable time duration.
4.5 VISUALIZATIONS AND EXPLANATION TO EMBEDDING DIMENSIONS
We visualize the explanations of the three learning-base based explanation methods on the BACE task, which aims to prediet the inhibitor effect of molecules to human 8-secretase 1 (BACE-1) (Wu et al.
2018). Additional visualizations on HIV and SIDER are also provided in Appendix[E] The visualiza- tion results shown in Figure 4, Each molecule visualization shows the top 10% important edges
8

---

Under review as a conference paper at ICLR 2022
Table 3: Comparison of computational time cost among three learning-based GNN explainers the PPI dataset. The left two columns record time cost breakdown for ' downstream tasks. The fourth column estimates the total time cost for explaining all 121 tasks of PPI. The last row shows the speedup times compared to GNNExplainer and PGExplainer, respectively.
Time cost
Training (s) 20040.1* 1
Inference (s) Total time (T=1) (s)
total for 121 tasks
GNNExplainer
20040.1
28 d
PGExplainer
7117.0*T
427.2%T
7604.2
10.7 d
TAGE
1405.3
582.7*T
1988.0
0.83 d
Specdup
/0.73x
10.1X /388
33.7x 12.9x
(With downstream task)
(No downstream tack)
GNNExplainer
PGExplainer
TAGE
TAGE-Single Dimension
TAGE-Single Dimension
2888
-0.4210
0-7011
(D.6287]
(0-6183)
0969
-0.0145
0-5022
(D.0494)
(0.8153)
(0.0193)
(0-3705)
Figure 4: Visualizations on explanations to the GNN model for the BACE task. Top 10% impor- tant edges are highlighted with red shadow. The numbers below molecules are fidelity scores when masking-ou out the top 10% important edges. Right two columns are explanations to two certain em- bedding dimensions without downstream tasks. Fidelity scores in the right two columns explaining two embedding dimensions are still computed for the BACE task but are just for reference.
(bonds) predicted by an explainer with red shadow, together with the fidelity score on the molecule. The left three columns explanation results with the BACE downstream task. The right columns are explanations by TAGE to two specific graph embedding dimensions, without downstream mod- els. Embedding dimensions with greater values among all are selected in the visualizations, To obtain explanations to certain embedding dimensions, we input the one-hot vectors to the embed- ding explainer condition vectors. The visualization results indicate that while baseline methods select scattered edges important, TAGE tends to select edges that form connected substructure, which is more reasonable when explaining molecule property predictions where certain functional group is important for the property. In addition, the right three columns indicate that dimensions in the embedding correspond different substructures and TAGE able to provide explanations the dimensions without downstream tasks.
5 CONCLUSIONS
Existing task-specific learning- based explainers become inapplicable under real scenarios when downstream tasks or models are unavailable and suffer from inefficiency when explaining real-world graph datasets with multiple downstream tasks. We introduced TAGE, including the task-agnostic GNN explanation pipeline and the self-supervised training framework to train the embedding ex- plainer without knowing downstream tasks or models. Our experiments demonstrate that the TAGE generally achieves higher explanation quality in terms of fidelity and sparsity with the significantly reduced explanation time cost. We discuss potential limitations and their solutions in Appendix G

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The experiment setting and evaluation protocol are described in Section 4. In particular, we de- scribe how the models be explained are trained. To further ensure reproducibility, we provide implementation details including explainer configurations, training settings, and how evaluation are performed in Appendix B. The detailed computation of sparsity and fidelity scores are provided in Appendix C. The code to fully reproduce the results will be released upon acceptance.
REFERENCES
Wengi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation, In The World Wide Web Conference, pp. 417-426, 2019.
Matthias Fey and Jan Lenssen. Fast graph representation learning with Py Geometrie. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learming, pp- 1263-1272. PMLR, 2017.
Michael Gutmann and Aapo Hyvärinen. for unnormalized statistical models. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
estimation: A new estimation principle
Devon Hjelm, Alex Fedorov, Samuel Marchil-nr, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. International Conference on Learning Representations, 2020.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Multi-objective molecule generation using interpretable substructures. In International Conference Machine Learning, pp. 4849-4859. PMLR, 2020.
Thomas N Kipf and Max Welling. arXiv:1611.07300 2016.
Variational
graph auto-encoders.
arXiv preprint
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Wanyu Lin, Hao Lan, and Baochun Li. Generative Causal Explanations for Graph Neural Networks. In International Conference on Machine Learning, 2021.
Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Liu, Keqiang Yan, Haoran Liu, Cong Fu, Bora Oztekin, Xuan Zhang, and Shuiwang Ji. DIG: A turnkey library for diving into graph deep learning research. Journal of Machine Learning Research, 22(240):1-9 2021. URL httt::/tpjiili htwpa..rr//a.....mmmmm..e.aeeeee pttp://ppprs//222
21- 11-0343.hte html
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Advances in neural information processing systems, 2020.
Mehdi Mirza and Simon Osindero. Conditional generative adversarial nets. I. 2014.
arXiv preprint
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural sam- plers using variational divergence minimization. In Advances in Neural Information Processing Systems, pp. 271-279, 2016.
10

---

Under review as a conference paper at ICLR 2022
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. 2019.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE Con- ference on Computer Vision and Puttern Recognition, pp. 10772-10781, 2019.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference Machine Learning, pp. 3145- 3153, 2017.
Teague Sterling and John Irwin. Zinc 15-ligand discovery for everyone. Journal of Chemical Information and Modeling, 55(11):2324-2337, 2015.
Fan-Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- tional Conference on Learning Representations, 2019.
Petar Veličković, William Fedus, William L. Hamilton, Pictro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In International Conference Learning Representations, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lið, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Zhengyang Wang, Meng Liu, Youzhi Luo, Zhao Xu, Yaochen Xie, Limei Wang. Lei Cai, Qi Qi, Zhuoning Yuan, Tianbao Yang, and Shuiwang Ji. Advanced graph and sequence neural networks for molecular property prediction and drug discovery. arXiv preprint arXiv:2012.01981, 2020.
Zhengin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical Science, 9(2):113-53)) 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974- 983, 2018.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in neural information processing systems. pp. 9244 92559225,2222 2019.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, arXiv preprint 20Xi:20012.15445 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. arXiv preprint arXiv:2 2021.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):110--1198 2017.
11

---

Under review as a conference paper at ICLR 2022
A DATASET STATISTICS
The statistics of datasets used for evaluating TAGE are shown in Table
Table 4: Statistics of multitask datasets used for explanation quality evaluation. The column "Total"
under MoleculeNet indicates total number of commonly studied tasks from MoleculeNet.
MoleculeNet BACE
PPI
EPN
HIV
BBBP
Sider
Total
# of Graphs
41127
2039
1513
1427
24
Avg. # of Nodes
25.53
24.05
34.12
33.64
56,944
5.86 mn.
Avg. # of Edges
27.48
25.94
36.89
35.36
818,716
63.07 mn.
# of Tasks
1
1
27
227
121
B IMPLEMENTATION DETAILS
Structure of explainer. Our implementation is based on Pytorch (asske et al. 2019), Pytorch Ge- ometric (Fey Lenssen 2019), and Dive-into-graphs (Liu et al. 2021). We implement the explainer with linear projection Jp that maps the condition vector the same dimension as concatenated embeddings, and 2-layer MIP with ReL.U activation that maps concatenated embeddings with mask to the important score.
Implementation training objectives. We adopt the Jason-Shannon Estimator as the lower bound for mutual information maximization for the two public datasets. For graph-level tasks, given a mini- batch of N samples, we consider the embeddings of a graph and its subgraph G2 as a positive pair (with N positive pairs in total), and the embeddings of graph G2 and the subgraph Gy,, of another sample as negative pair (with N - N pairs in total). For node-level tasks, we still randomly sample nodes from the entire graph at each iteration and compute the contrastive losses on original embeddings of the N nodes, and embedding of the N nodes when the important subgraph is selected, respectively for each node. Similar to graph-level tasks, we consider embeddings of the same node (in original graph in subgraph) node j in selected subgraph as a negative pair (N2 N in total).
positive pair, and embeddings of node i in full graph and
Training configurations. We set the hyperparameters in the size regularization term X 0.05 and Ae = 0.002, respectively. For graph-level explanation on MoleculeNet, we train the embed- ding explainer on ZINC-2M with learning rate 4 and mini-batch size 256 for epoch. The random condition vectors are generated from laplace distribution Laplace 0.2). For node-level explanation PPI, we train the embedding explainer on PPI without labels with learning rate 5e 5e-6 and mini-batch size 4 for epoch. The random condition vectors are generated from laplace dis- tribution Laplace (O, 0.1). For the EPN dataset, we train the embedding explainer with InfoNCE loss, learning rate le 4 and mini-batch size 16. The random condition vectors are generated from laplace distribution Laplace(O,, 0.25). The hyperparameters in the size regularization term are set to A = 0.5 and A 0 for the stable training with InfoNCE.
Evaluation. In molecule and protein property prediction, we are usually interested in the positive samples, i.e., the existence of what substructure lead to certain property. For dearning-based base- line methods, we find it common that only one class of the two have good explanation. and the class with higher explanation quality is not necessarily the positive class. For example, PGExplainer has a pear-to-zent fidelity score for the positive class of SIDER. We hence compare only the higher fidelity score among two classes for all explanation methods and datasets.
12

---

Under review as a conference paper at ICLR 2022
C FIDELITY AND SPARSITY
Given a set of graphs } and node masks m predicted by the explainer, the fidelity score and the sparsity score are computed follows.
Fidelity prob
-(C
f(G
Sparsity
N mm
(8)
where N denotes the number of graphs nodes be explained, denotes the GNN model sociated with specific downstream task, o denotes the class of interest, which can be either the labeled class or the original predicted class, G2 and G G.- m- denote the original graph and graph with important nodes removed, respectively. Explanations with both scores higher are better.
D ADDITIONAL RESULTS FOR UNIVERSAL EXPLANATION ABILITY
Universal explanation performance on MoleculeNet and EPN. Evaluation results for the uni- versal explanation ability on the MoleculeNet and EPN datasets are shown in Table and Table respectively.
Table 5: Fidelity scores with controlled sparsity on graph-level molecule property prediction tasks. Each column corresponds to explainer model trained (or without) specific downstream task. Underlines highlight the best explanation quality in terms of fidelity, on the same level of sparsity.
PGExplainer (trained on) HIV
TAGE w/o downstream
Eval on BACE
BACE
BBBP
SIDER
0,252 +0.340
0.007 #0.251
0.026 +0.022
-0.151 #0.330
0.378 #0.293
HIV
-0,001 #0.197
0.473 #0.404
0.013 +0.029
-0.060 #0.356
0.595 #0.321
BBBP SIDER
0.001 +0.237
-0.056 +0.226
0.182 10.169
-0.252 +0.440
0.193 10.161
0.012 10.219
-0.009 40.212
0.003 40.029
0.444 40.391
0.521 #0.278
Table 6: Fidelity scores with controlled sparsity on the E-commerce product dataset. Each column corresponds to one explainer model trained on different tasks or without downstream task. Under- lines highlight the best explanation quality in terms of fidelity, on the same level of sparsity.
PGExplainer (trained on)
TAGE w/o downstream
Eval
Buyers
Sellers
Reviews
Buyers
0.2009 #0.2233
0.1731 +0.3774
0.1740 #0.4463
0.2713 40. 1834
Sellers
0.5465 #0.4773
0.3246 +0.4026
0.1128 +0.3019
0.6515 #0.3426
Reviews
0.4178 #0.3683
0.1258 +0.3492
0.2310 +0.4178
0.5692 #0.4214
Comparison of explanation performance when trained on different datasets. Specifically for the MoleculeNet dataset, as there a larger unlabeled dataset, ZINC, available for the first stage training of encoder, the training of our exlainer also performed the ZINC dataset. For more strict comparison with the baseline explainer who is trained on individual MoleculeNet dataset, we additional evaluate the explanation quality when the same individual MoleculeNet dataset is used to train TAGE. The results are shown in Table 7 When trained on the same datasets individually, TAGE still performs better than the baseline explainer in terms of fidelity scores. In the individual dataset case, we need to train different explainers, similarly to the training of PGExplainer, as the datasets for the four tasks are different.
Evaluation on the synthetic dataset BA-Shapes. On the BACE dataset and task, we additionally compare TAGE with another recent SOTA learning-based method GEM (Lin et al. 202T whose explainer is trained based on the Granger causality in Table g Note that GEM is not originally proposed under our setting. It assumes that there is a fixed number of important nodes when per- forming explanation and hence the final explanation is boolean selection of nodes. We adapt GEM to compute fidelity scores under different sparsity scores by varying the threshold when generating explanation groundtruth with Granger causality.
13

---

Under review as a conference paper at ICLR 2022
Table 7: An ablation training TAGE different datasets (ZINC individual MoleculeNet datasets).
Method
BACE
HIV
BBBP
SIDER
PGExplainer
0.252 #0.340
0,473 #0,404
0.182 169
0.444 #0.391
TAGE (individual)
0.402 #0.281
0.541 +0.330
0.202 #0.157
0.516 #0.292
TAGE (ZINC)
0.378 #0.293
0.595 #0.321
0.193 #0.161
0.521 #0.278
Table 8: A comparison between TAGE, GEM, and PGExplainer on BACE in terms of fidelity scores when fixing the sparsity scores. For GEM, we vary the threshold when generating explanation groundtruth with Granger causality to obtain explanations with different sparsity scores.
Sparsity
0.90
0.85
0.80
0.75
TAGE
0,3349
0.4992
0.5383
0.5309
GEM Lin et al. 2021)
0.2829
0.3607
0.4260
0.4035
PGExplamer
0.2521
0.3207
0.4605
0.5161
E VISUALIZATIONS ON HIV AND SIDER
Visualizations on HIV and SIDER are shown in Figure
and Figure 6
respectively.
(With downstream task)
(No downstream tack)
GNNExplainer
PGExplainer
TAGE OH
TAGE-Single Dimension
TAGE-Single Dimension
OH
OH
OH
OH
OH
OH
OH
-4. 76e-17
0.64
(D.0146)
(3. 33-0998-6)
Dii
0.2617
(0.0263)
(0.2890)
Ci OH
Ci OH
CI OH
CI OH
Ci OH
D,9810
0. 7741
0.9820
(0)
(0.9894)
HD
0.4294
0. 2156
0.5763
(0.4154)
43.44377
Figure 5: Visualizations on explanations to the GNN model for the HIV task. Top 10% impor- tant edges are highlighted with red shadow. The numbers below molecules are fidelity scores when masking-ou out the top 10% important edges. Right two columns are explanations to two certain em- bedding dimensions without downstream tasks.
14

---

Under review as a conference paper at ICLR 2022
(With downstream Iask) PGExplainer
(No downstream fask)
GNNExplainer
TAGE
TAGE-Single Dimension TAGE-Single Dimension
-0.0528
0. 31.5
0. 8071
[0.3551]
(0.0286)
Ci
Ci
Ci
NH
NH
NH
NH
NH
0.1565
-0.6427
0.3383
(0.0942)
(0.0875)
HD
HD
HO
HD
HD
N
NHb
CH
0.0045
-0. 0387
0. 6603
(0.6403)
(0.0099)
OH
OH
OH
OH
OH
N
-0.1046
-0.2515
0.4669
(0.2652)
(0.1826)
Figure 6: Visualizations on explanations to the GNN model for the SIDER task. Top 10% im- portant edges are highlighted with red shadow. The numbers below molecules are fidelity scores when masking-out the top 10% important edges. Right two columns are explanations to two certain embedding dimensions without downstream tasks.
F EXPERIMENTAL STUDIES ON THE SYNTHETIC DATASETS BA-SHAPES
We perform an additional evaluation on the BA-Shapes synthetic datasets used in GNNEx- plainer Ying et al. 2019) and provided by thetic dataset is less complicated compared to the real-world datasets. We train a 3-layer GCN for the node-classification with training accuracy of 0.95. The AUC score (for importance edges) of TAGE is 0.999 compared to 0.963 and 0.925 of PGExplainer and GNNExplainer, respectively. Note that the bascline scores are from the PGExplainer paper and some re-implementation-1 of PGEx- plainer can also achieve an AUC score of 0.999. Our purpose to show our score on BA-Shapes to demonstrate that TAGE on par with its baselines even when considering the typical single- task setting. Figure / visualizes 20 examples of explanations. TAGE is able to provide accurate explanations for all the 20 examples.
Geometric (Fey & Lenssen 2019 The syn-
G DISCUSSION OF LIMITATIONS AND POTENTIAL SOLUTIONS
Inductive learning of explanations. Our study focus on the setting of inductive learning of the explanation, ie., to train the explainer on a given dataset and perform inference on new coming data. There are many work conducted under the inductive setting, such PGExplainer. All methods under this setting may have a potential limitation that the explainer may suffer from some dataset bias when training data and the data to be explained are inconsistent. This an interesting problem that requires further investigation. However, we believe that this is a separate problem and applies
15

---

Under review as a conference paper at ICLR 2022
Figure Visualizations on explanations the synthetic dataset BA-Shapes.
16

---

Under review as a conference paper at ICLR 2022
to all inductive learning methods. In addition, the size of graph could be inconsistent for training and inference. To tackle this issue, we obtain the substructure by selecting top percentage of edges according to their important scores.
Black-box explanations. Similarly to our baseline method PGExplainer, our explainer relies on node embeddings inputs to the explainer. In particular, the node embeddings serve represen- tations to allow explainers identify each node. explanations tell neural network-based explainers which edge they are looking the inductive methods is that when the node embeddings may become unavailable when explaining black-box model. The study of explaining blxck-box models (where only output available) is different direction of study in scenarios like attacking. Many current SOTA explanation approaches, such as Grad-Cam, GNN-LRRP, and PGExplainer, fail under the black-box setting. However, if one would like to adapt our approach to the black-box setting, it is still feasible by adopting a surro- gate model for the black-box model and perform explanation on the surrogate model. In addition, mentioned above, the node embeddings are mainly used to identify which node the explainer looking at, we does not necessarily require the original embedding. When node embedding are unavailable, still use any representation of nodes long it can identify the node based on its feature and topology.
required by any (inductively) learning based
limitation of
17


Reviews:
[{"review_id": "h4z8ZLujRKL", "reviewer": "Reviewer_y6T6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. This paper considered an interesting setting where there is no downstream task, or the target model to be explained is a multi-task model. Specifically, the entire pipeline consists of two explainers: an embedding explainer and a downstream explainer, which can be trained in isolation. The proposed method uses the downstream explainer to get dimension importance and highlight the important dimensions. \n\n2. The presentation of the paper is in general clear.\n\n3: It is a novel setting that is different from existing ones.\n\n\nWeaknesses:\n\n1. The technical contribution of this paper is limited. The proposed method is somewhat incremental compared with the existing method PGExplainer. Many design details are directly borrowed from PGExplainer. For example, the design of the embedding explainer and the form of the regularization term are the same.\n\n2. There is very little intuition provided to justify the practical significance of the explanation provided by the embedding explainer if there is no downstream task. I would suggest the authors include some examples of the generated explanations, which is essential to determine whether the claimed fidelity brings meaningful results in practice.\n\n3. Some key baselines are missing. For example, Gem [1] is also a learning-based explainer published in ICML2021. However, the author did not discuss and compare theirs with this work. I'd like to see the comparisons between the proposed method and [1].\n\n[1] Wanyu Lin, Hao Lan, Baochun Li. Generative Causal Explanations for Graph Neural Networks. ICML 2021.\n\n\n4. The proofs of Equations 2 and 3 are insufficient. Besides, in Equation 3, the definition of the positive and negative samples is unclear. The sample, positive sample, and negative sample in conditional contrastive loss should be specified for graph-level or node-level tasks. \n\n\n5. Regarding the method itself, the target model of the embedding explainer seems limited to node-level embedding models instead of graph/node-level embedding models. Specifically, graph embeddings are required when training the embedding explainer. When it comes to the implementation details of embedding explainers, node embeddings are required. Although node embeddings can be simply compressed to graph embeddings, the reversion is difficult. Therefore, an embedding explainer targeting a graph-level embedding model will fail to predict node-pair importance scores.\n\n6. \"For all methods, we vary the threshold for selecting important nodes or edges and compare how fidelity scores change over sparsity scores on each task and dataset.''\n\nHow to set the threshold is not clear. \n\n7. The empirical evidence could be more substantial.\n\n-\tIn essence, an idea explainer should be human-understandable. However, by looking at the Visualization in Figure 4, model explainability is not clear. Visualizing a few instances is not convincing in terms of model explainability. Further analyses are expected. \n\n\n-   About the evaluation of universal explanation ability, experiments results with downstream tasks are missing, which are indispensable for demonstrating the effectiveness of TAGE.\n\n-   On the experimental design, some scenarios do not satisfy the multi-task setting defined in general. For example, predicting the 121 binary labels for nodes in the PPI dataset is a multi-label classification task and cannot be regarded as 121 independent tasks. It is unfair to compare with the baseline PGExplainers trained and eval on this problematic experimental setting. Therefore, the results in Table 2 do not justify the use of TAGE.\n\n-   In Figure 3, on Task0 of the PPI data set, the fidelity scores of the proposed method are much lower than those of DeepLIFT. I would like to see a reasonable elaboration on this underperformance.\n\n\nMinor points:\n\nIn figure 2, the expression of $G_s$ is wrong. It should be written as $\\tau_\\theta(p, G)$, the \\eps operation should be done after using the GNN model.\n\nIn Section 3, $z_i$ (or $z_j$) denotes a graph embedding and a node embedding successively, which is ambiguous. If the author could distinguish between the notations of two different embeddings, this section would be more readable.\n", "summary_of_the_paper": "The authors propose TAGE, a task-agnostic explanation method for explaining GNNs. TAGE explains GNN embedding models without downstream tasks and allows the explanation of multi-task models. This paper maximizes the mutual information of masked graph embedding and masked subgraph embedding as the objective function. The regularization term is added to restrict the number of edges. Empirical results focus on three aspects: (1) Improvement in fidelity scores brought by TAGE; (2) Visualizations on explanations to the GNN model; and (3) Comparison of computational time cost among GNN explainers.\n", "summary_of_the_review": "The technical contribution of this paper is limited. The proposed method is somewhat incremental compared with the existing method PGExplainer.  The paper lacks rigorous empirical analysis, especially in terms of studying the interpretability aspect. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "csX3yCizs5E", "reviewer": "Reviewer_CLGN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n1.\tThe motivation is technically a good angle. Indeed extra costly training for generating explanations is a bottleneck for the applications. \n2.\tThe paper is easy to understand.\n3.\tThe method is simple but effective. \n\n**Weakness**\n1.\tThis paper mainly focuses on explaining multi-task models, which somehow limits the applicability.\n2.\tWhy does the author use $\\boldsymbol{p}\\otimes \\mathcal{E}(\\mathcal{T}_\\theta(\\boldsymbol{p}, G))$ but $p\\otimes\\mathcal{E}(\\mathcal{T}_\\theta(\\boldsymbol{p},G))$. If there is a performance gap between this two formulations, I wonder how each of them affect the quality of generated explanations.\n3.\tDuring the self-training of the embedding model, $p$ is sampled from a multivariate Laplace distribution, while later, the input is the conditional embeddings generated by the gradient. The distributions of the two groups of inputs could be different numerically and thus may affect the specific performance of the embedding model. Can the authors comment on this a bit? \n4.\tSome typos: last row of page 5 “as input” should be “an input”; In Section 4.1, “include four graph classiﬁcation tasks” should be “include three graph classiﬁcation tasks”.\n", "summary_of_the_paper": "This paper is motivated by the fact that existing task-specific explainers are too expensive to be applied to generating explanations for a model trained for multi-tasks. They decompose the typical end-to-end learning-based GNN explainer into two parts: the embedding explainer $\\mathcal{T}_{\\mathcal{E}}$ and the downstream explainer $\\mathcal{T}_d$ ($d$ for down). \nThe downstream explainer maps embeddings into importance scores $m$ for all embedding dimensions given a trained model and certain inputs. The embedding explainer is associated with the embedding model $\\mathcal{E}$, which maps a given graph into a subgraph of high importance, conditioned on the embedding dimension importance.\n\nFinally, $\\mathcal{T}_{\\mathcal{E}}$ is trained via a self-supervised manner, and they use a gradient explainer for $\\mathcal{T}_d$. In the experiments, TAGE outperforms the SOTA explainers w.r.t fidelity, sparsity, and especially time cost.\n", "summary_of_the_review": "I think this work is overall good, however, some technical details need to be clarified and the proposed model can only be necessarily applied to a limited range of explainers.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "b-nIy5WPi8l", "reviewer": "Reviewer_QC3Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides an interesting framework to tackle graph explanation. \n\n(1) Competitive baseline\n\nOther methods, such as PGExplainer, are training multiple explainers on different downstream tasks and evaluating each explainer on different downstream tasks. Should they have more expression power to achieve an upper bond for one universal explainer for all tasks or at least can recover the results of one universal explainer?  However, existing methods showed much worse results in Fig3. I speculate the reason maybe that many aspects of the two methods are different. Therefore, it will be interesting to see under exactly the same setup of Task-Agonistic, but one trainer per task, if the proposed method doesn't lead to much information drop then it demonstrates the good performance. \n\n(2) Novelty\nThe paper is quite similar with graph pretraining to learn a useful embedding and contrastive learning with mutual information , but with additional explanation part. Can the author recap on the major novelty contribution?  \n\n(3) Intuition of design of p \nPage 4 sec 3.2 \"We introduced a masking vector p  to indicate specific dimensions of embeddings on which to maximize MI. During\nexplanation, we obtain the masking vector from the importance vector computed by any downstream\nexplainer T_down. As no downstream importance vector is available at training, we sample the masking vector p randomly\". \n\nHow can the randomly selection of p during training help with specific dimension of embedding from importance vector during testing? \n\n", "summary_of_the_paper": "The authors proposed a method to offer explanations for a multitask prediction model with a single explainer. The method provides explanations in cases where the GNN is trained in a self-supervised manner, and the resulting representations are used in future downstream tasks. \n", "summary_of_the_review": "The paper is tackling an interesting problem -- explanation of graph. However, some results are a bit counter-intuitive. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9OGXJ8H6b4V", "reviewer": "Reviewer_ovjT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed scenario where we typically need to use two-stage GNNs is interesting and makes sense.\n\nThe proposed method is simple and somehow can achieve the desired goal.\n\nThere are several concerns.\n\n1, The setup of the explainer in this manuscript is a little different from the traditional ones. In the field of DNN (CNN or GNN) explanation, we may want to make the explanation only rely on the input sample and the model, which is most of the previous works have done. However, the proposed explainer needs one to train on the whole dataset used for the model to be explained. This may lead to several problems. 1) the explainer itself will rely on the training data, which may bring the same dataset bias to the explanation. 2) the proposed explainer, under its setup, is more like an input distillation model, where the input graph will be shrunk during the inference time.\n\n2, The proposed method seems to be a general method for the DNN models, not limited to the GNN. I'm wondering if the authors have tried to apply the proposed method to the CNN or transformer?\n\n3, For the evaluation, it would be interesting to apply the proposed method on the generated synthetic datasets like that used in GNNExplainer, where the ground truth explanations are available.", "summary_of_the_paper": "In this manuscript, a new explainer for GNNs is proposed. The newly proposed method aims to provide a task-agnostic explanation for the embedding GNNs rather than a specific downstream task. The motivation of the proposed method is that the modern GNNs are typically trained in a two-stage manner, where the embedding GNN is trained in the first stage and then the task-specific lightweight MLP. The proposed method is trained based on the MI between the whole graph and sub-graph generated by the explainer.", "summary_of_the_review": "The main concerns are about the setup of the explainer and the evaluation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary of the paper and the reviews:
The authors propose a method to explain the GNN predictions in a task-agnostic setting, meaning that the method can be applied to a new downstream task without fine-tuning. The task is formulated as to predict the important subgraph given the input graph and the ground truth label. The learning algorithm optimizes the mutual information between the embedding of the subgraph and the original graph. The experiment shows the quantitative improvement measured by the fidelity score, the qualitative visualization of highlighted subgraphs and comparison of the cost w.r.t the baseline GNN explainer models. 
Strength: 
1) The task-agnostic setting is novel.
2) The proposed method shows improvement in the fidelity score with a reduced training cost over the baseline models
Weakness: 
1) The proposed objective requires additional justification. To optimize the intractable mutual information objective, the authors propose JSE and InfoNCE as upper bound estimations of mutual information, but the negative sampling technique in the proposed method is not fully justified.
2) During training, the authors simulate the task-specific importance vector by sampling masks from a Laplace distribution. During testing, the importance vector is obtained by gradient-based approach. Further analysis is needed to quantify the effect of this training/testing discrepancy.  
3) In the empirical experiment, the proposed task-agnostic model outperforms the task-specific baselines. Why should such an outcome happen? The reason needs additional analysis but is not provided in the current paper. Moreover, the qualitative results of a few examples are not sufficiently convincing for the reported empirical success.

Summary of the discussions and the decision by reviewers: One reviewer asked for a justification of the negative sampling approaches used to approximate the mutual information objective. While the authors described their implementation design in their rebuttal, the theoretical justification of the method was not enough. Two reviewers raised the question about how randomly sampling importance masks during training could affect the downstream tasks performance, which was not fully addressed in the rebuttal. Other than that, the experimental concerns about new baselines and datasets were well addressed by the authors.

Recommendation: The paper has received borderline review scores (5, 5, 5, 6). Although the authors addressed some of the concerns in their rebuttal on the experimental design and added important baselines, more convincing justifications/analysis for the proposed method are still missing. Therefore, the reviewers didn’t raise their scores. Based on the above concerns, the recommendation is to reject.
Decision: Reject