GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks
Authors: Xiaoqi Wang
Han Wei Shen
Venue: ICLR 2023 poster (2023)
Keywords: AI Interpretability
Graph Neural Networks
Model-Level Explanation of Neural Networks

Abstract: Recently, Graph Neural Networks (GNNs) have significantly advanced the performance of machine learning tasks on graphs. However, this technological breakthrough makes people wonder: how does a GNN make such decisions, and can we trust its prediction with high confidence? When it comes to some critical fields, such as biomedicine, where making wrong decisions can have severe consequences, it is crucial to interpret the inner working mechanisms of GNNs before applying them. In this paper, we propose a model-agnostic model-level explanation method for different GNNs that follow the message passing scheme, GNNInterpreter, to explain the high-level decision-making process of the GNN model. More specifically, GNNInterpreter learns a probabilistic generative graph distribution that produces the most discriminative graph pattern the GNN tries to detect when making a certain prediction by optimizing a novel objective function specifically designed for the model-level explanation for GNNs. Compared to existing works, GNNInterpreter is more flexible and computationally efficient in generating explanation graphs with different types of node and edge features, without introducing another blackbox or requiring manually specified domain-specific rules. In addition, the experimental studies conducted on four different datasets demonstrate that the explanation graphs generated by GNNInterpreter match the desired graph pattern if the model is ideal; otherwise, potential model pitfalls can be revealed by the explanation.

Published as a conference paper at ICLR 2023
GNNINTERPRETER: A PROBABILISTIC GENERATIVE MODEL-LEVEL EXPLANATION FOR GRAPH NEURAL
NETWORKS
Xiaoqi Wang
Han-Wei Shen
The Ohio State University wang. 550200su..uc.mm edu
The Ohio State University shen. 94@osu.
ABSTRACT
Recently, Graph Neural Networks (GNNs) have significantly advanced the perfor- mance of machine learning tasks on graphs. However, this technological break- through makes people wonder: how does a GNN make such decisions, and can we trust its prediction with high confidence? When it comes to some critical fields, such as biomedicine, where making wrong decisions can have severe consequences, it is crucial interpret the inner working mechanisms of GNNs before applying them. In this paper, we propose a model-agnostic model-level explanation method for different GNNs that follow the message passing scheme, GNNnnterpreter, to ex- plain the high-level decision- GNNnnterpreter learns a probabilistic generative graph distribution that produces the most discriminative graph pattern the GNN tries to detect when making a certain prediction by optimizing a novel objective function specifically designed for the model-level explanation for GNNs. Compared to existing works, GNNInterpreter is more flexible and computationally efficient in generating explanation graphs with different types of node and edge features, without introducing another blackbox requiring manually specified Nomain-specifii rules. In addition, the experimental studies conducted on four different datasets demonstrate that the explanation graphs generated by GNNInterpreter match the desired graph pattern if the model is ideal; otherwise, potential model pitfalls can be revealed by the explanation.
process of the GNN model. More specifically,
INTRODUCTION
Graphs are widely used model data in many applications such as chemistry, transportation, etc. Since a graph is unique non-Euclidean data structure, modeling graph data remained a challenging task until Graph Neural Networks (GNNs) emerged (Hamilton et al. 2017 Cao et al. 2016). As powerful tool for representation learning on graph data, GNN achieved state-of-the- art performance on various different machine learning tasks on graphs. As the popularity of GNNs rapidly increases, people begin to wonder why one should trust this model and how the model makes decisions. However, the complexity of GNNs prevents humans from interpreting the underlying mechanism in the model. The lack of self-explainability becomes a serious obstacle for applying GNNs to real-world problems, especially when making wrong decisions may incur an unaffordable cost.
Explaining deep learning models text or image data (Simonyan al. 2014 Selvaraju al. 2019) has been well-studied. However, explaining deep learning models on graphs is still less explored. Compared with explaining models on text or image data, explaining deep graph models a more challenging task for several reasons (Yuan et al.] 2020b): (i) the adjacency matrix representing the topological information has only discrete values, which cannot be directly optimized via gradient- based methods (Duval & Malliaros) 2021). (ii) in some application domains, graph is valid only it satisfies a set of domain-specific graph rules, so that generating a valid explanation graph to depicts the underlying Docision-making process of GNNs is a nontrivial task, and (iii) graph data structure is heterogeneous in nature with different types of node features and edge features, which makes developing
sicesiz--iit-alll explanation method for GNNs to be more challenging. In this paper, we attempt to interpret the high-level decision decision-making process of GNNs and to identify potential model pitfalls, by resolving these three challenges respectively.

---

Published as a conference paper at ICLR 2023
In recent years, explaining GNNs has aroused great interest, and thus many research works have been conducted. The existing works can be classified into two categories: instance-level explanations (Luo et al.; 2020: Ying et al. 2019 Vu & Thai 2020) and model-level explanations (Yuan et al.) 2020a). Instance-level explanation methods focus on explaining the model prediction for a given graph instance, whereas model-level explanation methods aim understanding the general behavior of the model not specific to any particular graph instance. If the ultimate goal is to examine the model reliability, one will need examine many instance-level explanations one by one draw a rigorous conclusion about the model reliability, which is cumbersome and time-consuming Conversely, the model-level explanation method can directly explain the high-level decision- decision-making rule inside the blackbox (GNN) for target prediction, which is less time-consuming and more informative regarding the trustworthiness of the GNNs. Besides, it has been shown that any instance-level explanation method would fail to provide faithful explanation for GNN that suffers from the bias attribution issue (Faber et al. 202I), while the model-level explanation methods can not only provide a faithful explanation for this case but also diagnose the bias attribution issue.
Even though the model-level explanation methods for GNNs have such advantages, they are much less explored than the instance-leve explanation methods. In this paper, we propose a probabilistic generative model-level explanation method for explaining GNNs on the graph classification task, called GNNInterpreter. It learns a generative explanation graph distribution that represents the most discriminative features the GNN tries to detect when making a certain prediction. Precisely, the explanation graph distribution is learned by optimizing a novel objective function specifically designed for the model-level explanation of GNNs such that the generated explanation is faithful and more realistic regarding the domain-specific knowledge. More importantly, GNNInterpreter is a general approach to generating explanation graphs with different types of node features and edge features for explaining different GNNs which follows the pesssage-passingg scheme. We quantitatively and qualitatively evaluated the efficiency and effectiveness of GNNInterpreter on four different datasets, including synthetic datasets and public real-world datasets. The experimental results show that GNNInterpreter can precisely find the ideal topological structure for the target prediction if the explained model is idcal, and reveal the potential pitfalls in the model decision- decision-making process there are any. By identifying these potential model pitfalls, people can be mindful when applying this model to unseen graphs with a specific misleading pattern, which is especially important for some fields in which making wrong decisions may incur unaffordable cost. Compared with the current state-of-the-art model-level explanation method for GNNs, XGNN (Yuan et al., 2020a)), the quantitative and qualitative evaluation result shows that the explanation graphs generated by GNNInterpreter are more representative regarding the target class than the explanations generated by XGNN. Additionally, GNNInterpreter has the following advantages compared with XGNN:
GNNInterpreter is more general approach that can generate explanation graphs with different types of node features and edge features, whereas XGNN cannot generate graphs with continuous node features or any type of edge features.
By taking advantage of the special design of our objective function, GNNInterpreter is more flexible in explaining different GNN models without the need of having domain-specific knowledge for the specific task, whereas XGNN requires domain-speciff knowledge to manually design the reward function for the reinforcement learning agent.
GNNInterpreter is more computationally efficient. The time complexity for GNNInterpreter is much lower than training deep reinforcement learning agent as in XGNN. Practically, it usually only takes less than a minute to explain one class for GNN model.
GNNInterpreter is numerical optimization approach without introducing another blackbox to explain GNNs, unlike XGNN which trains a deep learning model to explain GNNs.
2 RELATED WORK
Graph Neural Network. GNNs have achieved remarkable success in different machine learning tasks, including graph classification (Lee et al. 2018), ,, node classification (Xu et al. 2019) and link prediction (Zhang & Chen 2018). There exists a variety of GNN models (Kipf & Welling 2017] Gilmer et al. [017 Veličković et al. 22018), but they often share a common idea of message passing as described in section 3 In this paper, we will focus on interpreting the high-level decision-makin process of graph classifiers and diagnosing their potential model pitfall.
2

---

Published as a conference paper at ICLR 2023
Instance-Level Explanation of GNN. Encouraged by the success of explaining deep neural networks on image or text data, a multitude of instance-level explanation methods of GNNs have been proposed in the past few years. Their goal is to explain why a particular prediction is being made for specific input, which is substantially different than our explanation goal. According to a recent survey (Wu al. 2022), most instance-level explanation methods can be classified into six categories: gradient-based
& Azizpour, (2019), verturbation-baser methods (Yuan et al. 2021p decomposition methods (Schwarzenberg et al. 2019), surrogate methods (Duval & Malliaros
2021), generation- methods et al. [202 Lin et al. 2021; 2022), and counterfactual based methods. Similar to our method, PGExplainer Luo et (0200 also adopts Gumbel-Softmaal
tickk(Maddison et al. 2016) to learn the explanation distribution. However, we learn model-level explanation distribution obtained by gradient ascent to capture the class-specific discriminative features, while they learn an instance-level explanation distribution predicted by an MLP to identify the important nodes and features toward the GNN prediction for a given graph. In addition to these six categories, some instance-level explanation methods do not fall into any one of the categories. For instance, Veyrin-Forred et al. (2021) mines the activation pattern in the hidden layers to provide instance-level explanations and summarize the different features of graphs in the training data.
Model-Level Explanation of GNN. Model-level explanation methods aim to explain the general behavior of a model without respect any specific input. The current state-of- of-therr- model- level explanation method for GNNs is XGNN (Yuan et al., (2020a). Similar to most of the model- level explanation methods for other deep learning models (Simonyan et al. 2014). XGNN and GNNInterpreter share common goal of generating explanation graphs to maximize the likelihood of the target prediction being made by the GNN model, but with fundamentally different approaches. XGNN trains a deep reinforcement learning model to generate the explanation graphs, while we employ a numerical optimization approach learn the explanation graph via continuous relaxation. To facilitate the validity of the explanation graph, XGNN incorporates hand-crafted graph rules into the reward function so that the reinforcement learning agent can consider these rules when providing explanations. However, manually specifying these graph rules is cumbersome and requires comain-specifii knowledge about the task. XGNN has another limitation that it cannot generate explanation graphs with any type of edge features continuous node features.
BACKGROUND
Notations. A graph is represented as G = EV. where V and E are the sets of nodes and edges. Besides, the number of edges and nodes are denoted as M and N, respectively. The topological information of graph deseribed by an adjacency matrix A E {0, 1 where asj if there exists an edge between node and node j. and a:y- = 0 otherwise. In addition, the node feature matrix X E N x and edge feature matrix Z E M Mx represent the features for N nodes and M edges.
Graph Neural Networks. In general, the high-level idea of GNN is message passing. For each layer, it aggregates information from neighboring nodes to learn the representation of each node. For hidden layer i, the message passing operation can be described as H' f(H A,, Z) and H X, where H' E NxF is the hidden node representation output from Hth layer and F is the output feature dimension. The propagation rule f can be decomposed into three components: computing the messages according to the node embedding at the previous layer H'-1 aggregating the messages from neighboring nodes, and updating the hidden representation H' for each node based upon the aggregated message. It is worth mentioning that GNNinterpreter can explain different GNNs that follow this message-passinn scheme.
4 GNNINTERPRETER
In this paper, we propose a model-level explanation method, GNNInterpreter, which is capable of disclosing the high-level decision-making process of the model for the purpose of examining model reliability. GNNInterpreter is a numerical optimization approach that is model-agnostic for explaining various GNNs following the message- passeeggasinggggg scheme. It provides explanation graphs with either discrete or continuous edge features and node features. Besides, we design a novel objective function that considers both the faithfulness and validity of the explanation graphs Due to the
3

---

Published as a conference paper at ICLR 2023
discreteness nature of graph data, we learn generative explanation graph distribution by adopting the Gumbel-Softman trick (Maddison et al. (016))
4.1 LEARNING OBJECTIVE
To reveal the high-level decision-making process of the model, one effective approach is construct an explanation graph that can trigger specific response from the model as much as possible. Similar to most of the model-level explanation methods for other deep learning models (Simonyan al. et al.) 2015), the explanation for GNNs can be obtained by maximizing the likelihood of the explanation graph G being predicted as target class by the GNN model. However, solely maximizing the likelihood without constraints may not necessarily result in meaningful explanations. This because a local maxima in the objective landscape may lie outside of the training data distribution. The explanation yielded from this type of maxima is mathematically legitimate but may provide no meaningful insights on how the model actually reasons over the true data distribution. Especially when there exists Nomain-specifff knowledge that restricts the validity of the data, the explanations are expected to stay inside the hard boundary of the true data distribution. XGNN (Yuan) jet al. 2020a) addresses this problem by manually specifying set of graph rules and evaluating the validity of explanation graphs according to the specified rules as a part of the reward function for the reinforcement learning agent. The essential goal is confine the distribution of the explanation graphs to the domain-specific boundary. Nevertheless, manually specifying rules not only is tedious and time-consuming, but also requires domain expertise which is not always available. Moreover, in many cases, the rules over data distribution can not even be programmatically specified. Therefore, we propose to leverage the abstract knowledge learned by the GNN itself to prevent the explanation from deviating from the true data distribution. This can be achieved by maximizing the similarity between the explanation graph embedding and the average embedding of all graphs from the target class in the training set. Thus, we mathematically formulate our learning objective as follows,
max [.G)) = max L(A, X) G
max de (A, Z,X) + pasim ( (b> A, Z, X), th)) A.Z.X
(I)
A.Z.X
where L is the objective function; Φe is the scoring function before Softmax corresponding to the class of interest predicted by the explained GNN; &b is the graph embedding function of the explained GNN; vb, is the average graph embedding for all graphs belonging to class e in the training set; simeos denotes the cosine similarity; μ is
representing the weight factor.
Given the learning objective defined above, one possible approach to obtain the explanation graph is that we adopt the gradient ascent iteratively update the explanation graph G' toward maximizing the learning objective. However, this approach cannot be directly applied here because the discrete adjacency matrix A encoding the graph topology is din-differentiable, namely V(L(A, Z, X) does not exist. Therefore, in order to adopt the gradient ascent method, A needs to be relaxed to a continuous variable. In addition, if the training graphs of the GNN model have discrete edge features or discrete node features, then Z and X are also required to be relaxed to the continuous domain such that VzL(A, Z, X) and VxL(A, Z, X) exist. Given that the continuous edge features and continuous node features do not require any special accommodation to adopt the gradient ascent, we will only discuss how to learn continuously relaxed explanation graph with discrete edge features and discrete node features in the following sections.
4.2 LEARNING GENERATIVE GRAPH DISTRIBUTION WITH CONTINUOUS RELAXATION
To learn a probabilistic generative graph distribution, from which the graph drawn maximizes the learning objective, two assumptions have been made (see the detailed justification of the assumptions in Appendix C.. The first assumption is that the explanation graph is Gilbert random graph (Gilbert 1959). in which every possible edge occurs independently with probability 0 < p < 1. The second assumption is that the features for each node and edge are independently distributed. Given these two assumptions, the probability distribution of the graph G, random graph variable, can be factorized
as
P(G) = P(.)) II P(an))
EV
(L,)EB
where aij = 1 when there exists an edge between node i and j and aij = 0 otherwise, ziy denotes the edge feature between node i and j. and x; represents the node feature of node i.
4

---

Published as a conference paper at ICLR 2023
Intuitively, dzj be modeled as Bernoulli distribution, dij Bernoulli(@sy). in which the probability of success 6, represents the probability of an edge existing between node i and j in G. For the discrete edge feature 4ij and the discrete node feature 2;, follow a Categorical distribution, a generalized Bernoulli distribution, with the parameter specifying the probability of each possible outcome for the categorical node feature and the categorical edge feature. Formally, žij ~ Categorical(qij) and ~ Categorical(p:) where ||q:/ |1 = 1 and ||Pilll 1. We define the number of edge categories k dim(g.)) and the number of node categories ky = dim( Thus, to learn the probabilistic distribution for explanation graphs, we can rewrite the learning objective as
assume that 2ij and x;
max L(G) = max BG- (A + pasi (,) b.)). e.Q.P
(3)
To adopt gradient ascent over the learning objective function with respect to a graph with the discrete edge feature žij and the discrete node feature H;, we relax aij. 2ij and x; to continuous random variables dij. Rij and x,, respectively. Specifically, agj is relaxed dæj E [0, 1]: Zaj is relaxed to Z,y (0, 1]&g | | 1; and m; is relaxed X; E [0, 1] || 1 1. Given that the Concrete distribution (Maddison et al. (0166) a family of continuous versions of Categorical random variables with closed-form density, the distribution of continuously relaxed ūij. Σig and ž; can be written as
Üij ~ Binary BinaryConcrede Concrete(wr. Ta); Egj ~ Concrete(M Tz), 32 (oncrette(E,,7.
for ūij E À and wij E 5 for ā, Z and M,j E H for 7. X and &
(4)
where r (0, 00) the hyper-parameter representing the temperature, why = Log(Otz/(0 01)) My log Qij. and & log pi. As the temperature approaches zero, the Concrete distribution is mathematically equivalent to the Categorical distribution.
However, in order to learn the generative explanation graph distribution, the sampling function for sampling a.y. Eig and z from the Concrete distribution is required to be differentiable. Thus, the reparametrization trick is adopted to approximate the sampling procedure of ā.j. Eg and o; by differentiable function. Given an independent random variable e Uniform(O,1), the sampling function with the reparameterization trick is as follows,
aig sigmoid ((wi + log log(1 (1 - -)] /Ta) Σij Softmax ((ng log( log é)) /T=)
T; Softmax ((Ei looolo( - log e)) /T.))
Given this reparameterizztioon trick, the probability of ā:j to be close to is the same as the probability of a.j to equal 1 and vice versa. Specifically, P(ā.z + 1) 1 P(ā.j 0) P(ay 1) Oıg signnoi((wzy). Similarly, ži and ã; drawn from the Concrete distribution as in lnquationn 3 is an approximation of zij and Fy. Therefore, the learning objective with continuous relaxation and reparameterization trick can be approximated by the Monte Carlo method with K samples,
draw sample ā.y
approximation of aiy, where
K
max ((A,, Z,X] e.Q.P
Rs max 2,H.3
max Σ L(A 2, (6)
S.H. K k=
4.3 REGULARIZZTION
In order to facilitate optimization and ensure that the explanation graphs are constrained to desired properties, we employ three types of regularization on the latent parameters. Firstly, we apply L and Le regularization on all latent parameters during training to avoid gradient saturation and to help escape from local maxima. Secondly, to encourage the explanation to be succinct as possible, we impose a budget penalty to limit the size of the explanation graph. Lastly, the connectivity incentive term is introduced to encourage neighboring edge correlation. The equations and detailed explanations for all regularization terms are presented in Apppeddi A] Putting everything together, the detailed algorithm of GNNNnterpreter is shown in algorithm
5

---

Published as a conference paper at ICLR 2023
Algorithm 1: Generate Explanation Graphs Using GNNInterpreter
Calculate the average graph embeeddin vh training initialize lalent parameters H. while not converged do 4- I... KC
Using reparamcterization trick, sample A, 2, X with Equation
Obtain the class score .(4) < &c(A, 2, X) and the graph embedding b < ve 8).
Calculate x Σ> Am (00)) + psimeea (b (b2) with the regularization
Culculate V., Ve and VzL. then updane 12. H. and a using gradient aseent.
Let @ = sigmoid( (S)). P p= Softmax(3). Q Softmax(H).
G (A, 2, X). where Bernoulli@@), Categorical( (Q). X Categorical(P).
4.4 THE GENERALIZABILITY OF GNNINTERPRETER
GNNInterpreter can generate explanation graphs with different types of node and edge features as needed. If the node or edge feature is continuous, V (A, Z. X) and (z, Z, X) naturally exist, only the adjacency matrix A need to be relaxed as shown in Equation 4 In Addition, unlike XGNN, which only works with a single categorical node feature, the number edge and node features are not limited & GNNInterpreter. Generally speaking, GNNInterpreter can explain all common GNNs following the message passing scheme, in which messages are aggregated from their neighbors to update the current node embedding. To adapt message passing for GNNntteprrete, messages passed between every pair nodes, but each message is weighted by 0g = sigmoid(ww.). Thus, 0, approaches node and node j highly likely to be neighbors. With this small modification, GNNInterpreter can be easily applied to different message- caassae-passing-baee -based GNNs.
5 EXPERIMENTAL STUDY
To comprehensively assess the effectiveness of GNNInterpreter, we carefully design experimental flexibility of generating explanation graphs with
studies conducted on 4 datasets to demonstrate various feature types and manifest our capability of explaining different GNNs. Specifically, we train
GNN classifier for each dataset and adopt GNNInterpreter explain. In addition, we quantitatively and qualitatively compare the efficacy of GNNInterpreter with XGNN (Yuan et al. 2020a). Details about the experiments and synthetic datasets generation are presented in Appendix G and
Table 1: The statistics of datasets and some technical details about their corresponding GNN models.
Dataset
# Classes
Node Features /
Edge Features
Average Edges
Average of Nodes
GNN Type
Test Accurncy
GNN
MUTAG Kersting 2016
19.79
17.93
GCN Kinf & Welling 2017
0.9468
Cyenery Motif Shape
$2.76
52.51
NNCoBV
0.9921
77.36
$7.07
(Kip) 2017
0.9964
71.86
30.17
GCN (iip & Wellnng 2017
0.9725
5.1 DATASETS
Synthetic Dataset. We synthetically generate 3 datasets which are Cyclicity, Motif, and Shape (see Table I). (1) In Cyclicity, the graphs have categorical edge feature with 2 possible values: green or red. There are 3 class labels in Cyclicity, which are Red-Cyclic graphs, Green-Cyclic graphs, and Acyelic graphs. Specifically, graph will be labeled as green/red cyclic graph only if it is cyclic and the edges forming that cycle are all green/red. If a graph is categorized as Acyelic, then it either does not contain a cycle at all contains a cycle but with a mixture of green and red edges. (2) The graphs in Motif are labeled according to whether they contain a certain motif. There are 4 motifs (i.e., House, House-X, Complete-4, and Complete-5) will possibly appear the graphs and each motif corresponds to one class label. There is another class that contains the graphs without any special motif. Besides, each node the graphs has a categorical node feature with 5 possible values: red, orange, green, blue, and purple. (3) Shape contains 5 classes of graphs: Lollipop. Wheel, Grid, Star, and Others. In all the classes except the Others class, graphs are generated with the corresponding shape. For the Others class, graphs are randomly generated without any special topology.
Real-world Dataset. MUTAG (Kersting et al. 2016) is a real-world dataset with 2 classes: Mutagen and Nonmutagen. Each molecule graph is categorized according its mutagenic effect (Debnath

---

Published as a conference paper at ICLR 2023
al., 1991). Given the fact that the molecules with more NO2 more likely to mutate, the graphs in the Mutagen class tend to have more NO₂ than those in the Nonmutagen class. Besides, the Mutagen class and the Nonmutagen class share common feature which is rings of carbon atoms.
5.2 RESULTS
To investigate whether we can truly explain the high-level Doecision-makingg process, we evaluated GNNInterpreter both quantitatively and qualitatively. Following XGNN (Yuan al. (020a), the class probability of the explanation graphs predicted by the GNN is adopted as the quantitative metric since GNNnnterpretrr and XGNN share a common objective of maximizing the target class score (Table 2). To qualitatively evaluate GNNInterpreter, we present one explanation graph per class for all datasets in Figure ! which are predicted as the target class with the class probability 1. Due to the page limit, more explanation graphs per class per dataset are presented in Appendix F
Table 2: The quantitative results for 4 datasets. As the quantitative metric, we compute the average class probability 1000 explanation graphs and the standard deviation them for every class in all 4 datasets. In addition, the average training time per class of training 100 different GNNInterpreter and XGNN models, is also included for efficiency evaluation.
Datnset [Method]
Predicted Class Probubility by GNN
Training Time Per Class
MUTAG [XGNN]
Muragen
Nonmutagen
128
0,986 0,057
0,991 0.083
MUTTGG [Owrs]
Mutagan
Nonmulagen
12x
0.000
Cyclicity [Ours]
Red Cyclic
Green Cyche
Acyche
House
House-X
Complete-4
Complete-5
Moxif
0.918 :: 0.268
0,999
0.032
1.000 = 0.000
0.998 0.045
Shape [Ouns]
Lollipop
Wheel
Grid
0.742 + 0.360
0.989 0.100
0.996 - 0.032
1.000 0.000
Dataset [Method]
Genernted Model-Level Explanation Graphs
MUTAG [XGNN]
esplasation
esanple
explasation
esample
Musage
Nommiigge
MUTAG [Qurs]
replaration
esample
explanatio
esampl
Rel Cyclic
Green Cyclic
Axyelie
Cyclicity [Ours]
caplexation
ctampl:
eaplanation
cumppe
explanation
cuampl:
House
Howe-X
Complce-4
Complexe
Motif [Oars]
esplazation
explanation
esplanation
explanziion
Lotlipop
Wheel
Grdd
Shape
[Ours]
rapletation
ecample
eaplonation
ecamppe
esplanation
example
explasation
esamplo
Figure 1: The qualitative results for 4 datasets. For each class in all datasets, the explanation graph with the class probability of 1 predicted by the GNNs is displayed on the left; as reference, the example graph selected from the training data of the GNNs or the motif displayed on the right. The different colors in the nodes and edges represent different values in the node feature and edge feature.
Since XGNN the current state-of-th wht---o-hhhheeeee art model-level explanation method for GNNs, we compare GNNInterpreter with XGNN quantitatively and qualitatively. However, given that XGNN cannot generate explanation graphs with edge features, XGNN is not applicable to the Cyclicity dataset. For Motif and Shape, attempted adopt XGNN to explain the corresponding GNNs, but the
7

---

Published as a conference paper at ICLR 2023
explanation results were not acceptable even after extensive efforts of trial-and-error XGNN. Therefore, for fair comparison, we only present the evaluation results of XGNN on the GNN trained on MUTAG, with the same addition to these 4 datasets, we also conducted experiments on the Is is_Acyclic dataset synthesized by XGNN authors, but we failed reproduce similar results claimed in the XGNN paper. The details of our comparative study on the Is Acyclic dataset against XGNN can be found in infsusecction D.2)
settings for MUTAG as they discussed in their paper. In
The quantitative evaluation in Table 2 shows that all explanation graphs generated by GNNInterpreter are classified correctly with 100% probability for both classes with zero variance, which indicates that we can consistently generate the most representative explanation graphs in terms of the explained GNN for all three classes. On the contrary, the GNN is more hesitant or diffident when classifying the XGNN explanation graphs for both classes. Speaking of the time efficiency, for explaining the same GNN model trained on MUTAG, we can generate an explanation graph about 10 times faster than XGNN on average according to TTall 2| (see the time complexity analysis of XGNN and GNNInterpreter in Appendix B). In Figure I the GNNInterpreter explanation for Mutagen class contains repeated NO, whereas the GNNInterpreter explanation for Nonmutagen class does not contain O atom at all, which is perfectly aligned with our background knowledge about the MUTAG dataset mentioned in subsectionn 5.1 In contrast, the XGNN explanation for the Mutagen class only contains single NO2, which a less accurate or ideal explanation than ours. In addition, according to our explanation graphs for both classes, they indicate that the GNN trained with MUTAG likely to suffer from the bias attribution issue (Faber al. (021) because the explanation graph for Nonmutagen class does not contain any special pattern but achieve the class probability of
MUTAG.
This finding is further verified by the additional experiments we conducted (see subbsectin E.2)
Cyclicity. In addition to the good quantitative performance shown in Table 2, the explanation graphs for Red Cyclic and Green Cyclic only contain multiple red cycles and multiple green cycles, respectively; the explanation graph for Acyclic does not contain any cycle with homogeneous edge colors (see F. These explanations reveal pattern that the more occurrences of a discriminative feature for the corresponding class (i.e., red cycle, green cycle, and cycle with heterogeneous edge color, respectively) the more confident the GNN is during the decision makiing process.
Motif. The result in Table 2) shows that the explanations for all classes successfully identify the discriminative features perceived by the GNN. In Figure [] the explanations for House and Complete- 5 classes match the exact motif. Even though the explanation graphs for House-X X and Complete-4 do not match the exact motif, it still obtains the class probabilities of 1. By analyzing the commonality between the explanations and their corresponding ground truth motifs for House-X and Complete-4 respectively, we speculate the discriminative features the GNN tries to detect for these two classes are the following: in House-X graphs, the orange node and the red node should have 3 neighbors except the purple node, the green node and the blue node should have 4 neighbors in a different color; in Complete-4 graphs, every node should have neighbors in a different color. Clearly, the GNN with test accuracy of 7.0.999 99.9964 ( (Table 7) perceives the wrong motifs as the House-X and Complete-4, which implies the potential risk of misclassification for unseen graphs with misleading patterns. The inconsistency between the explanations and the truth motifs raises a red flag that the GNN might be cheating by using some partly correct discriminative features as evidence to make decisions.
Shape. In Table 2, the explanations for all the classes except Lollipop achieve a good quantitative performance. For Lollipop, the average class probability of 0.742 is still reasonably high probability than 0.2 (the baseline probability of random guessing for classification task with 5 classes). Besides, the explanation graphs for all 4 classes presented in Figure I are almost consistent with the desired graph patterns. Nonetheless, it also discloses some interesting findings regarding the high-level decision-makee -mking process of the GNN. For Wheel and Grid class, the explanation graphs are not very perfect but with the predicted class probability of 1. Accordingly, we infer the true belief inside the GNN is that: the discriminative features of Wheel graph and Grid graph are a single common vertex shared by multiple triangles and multiple polygons sharing some common edges, respectively. These might become the potential model pitfalls because, for example, the GNN will be easily tricked by non-wheel graph in which there exists a common vertex shared by multiple triangles.
Verification Study. Since the ground truth model-level explanation graphs are unknown, the correct- ness of our analysis regarding these potential GNN pitfalls cannot be directly justified. Therefore, to verify the correctness, we conduct controlled experimental studies to test how the GNN behaves on some carefully chosen input graphs with specific misleading patterns. As mentioned above, we
8

---

Published as a conference paper at ICLR 2023
speculate the discriminative feature the GNN tries to detect for the House-X class is that "orange node and red node should have 3 neighbors except purple node, green node and blue node should have 4 neighbors in different color". . We found 9 plausible motifs (including the ground truth House-X) which satisfy this rule (see (. Given a fixed set 5000 base graphs, each of the 9 different motifs is attached to the same node of each base graph respectively. Thus, obtain 9 sets of graphs, each of which contains 5000 graphs corresponding to one of the motifs. For each motif set, the classification results are presented in Table We can see that motif 1-8 successfully fool the explained GNN because large portion of the non non-House-X graphs are incorrectly classified as House-X, This verification result strongly supports our qualitative analysis regarding the potential model pitfall for House-X class. The verification studies for more classes are presented in Appendix E
Plausible House-X Motifs
Figure 2: The ground truth class label for motif 1-8 and motif is Others and House-X, respectively.
Table 3: The classification results of plausible House-X motifs.
Motif 1
Motif 2
Motir 1808
Motir
Motif 2133
Motit 6
Motif
Motif
Motif 9 (CT)
1970
397
House
0
0
0
House- X
3566
2779
3192
3030
2817
4403
3318
3301
4990
Complete-4
0
Complete-3
0
0
0
Ablation Study, many cases, especially when true graphs are constrained with certain domain- specific rules, the second term of the objective function in [qqation I plays significant role in generating meaningful explanations. To assess the effectiveness of the second term, we take the Mutagen class from MUTAG dataset shown in Figure 3 the explanation without the second term completely deviates from the true data distribution because the ground truth discriminative feature of the mutagen class (i.e., NO2) is completely missing in the explanation without the second term. Even though the explanation without the second term achieves significantly higher logit, it is difficult to gain meaningful insights from the explanation without the second term. That is to say, the out-of cattof-distribution explanation graph generated without the second term might not provide meaningfu insight into how the model actually reasons over the true data distribution, which is what we actually care about.
example conduct ablation study this term. As
With Second Term
Without Second Term
Graphs
Logits
43.45
34,98
310.1
286
Figure 3: The ablation study the second term on the mutagen class from MUTAG dataset. For each category (column), we present 2 explanation graphs with the class score before Softmax (logits).
CONCLUSION
We propose GNNInterpreter, probabilistic generative model-level explanation method for GNNs. which learns a graph distribution to depict the discriminative and representative pattern perceived by the GNNs for target class. By optimizing the objective function we designed, GNNInterpreter can generate faithful and realistic explanations, without requiring manually specified domain-specific graph rules. Compared with XGNN, GNNInterpreter is more general and computationally efficient because it works with different types of edge and node features, while having lower time complex- ity. This makes GNNInterpreter more practical and accessible in real-world applications. More importantly, the experimental results show that GNNInterpreter results than XGNN on the real-life dataset, but also reveal the potential model pitfalls such as the bias attribution issue and misclassification of unseen graphs with misleading graph patterns.
not only produce more faithful

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENT
The work was supported in part by the US Department Energy SciDAC program DE-SC0021360, National Science Foundation Division of Information and Intelligent Systems II5-1955764, and National Science Foundation Office of Advanced Cyberinfrastructure 02C-2112606.
REFERENCES
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. ArXiv, abs/1905.13686, 2019.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. AAAI' 16, pp. 1145-1152. AAAI Press, 2016.
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Corwin Hansch. cruuctur-acctvvity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal Medicinal Chemistry, 34(2):786 797, 1991. doi: 10.1021/jm00106mm 0664606 URL
1021/3m001n 66066
Alexandre Duval and Fragkiskos Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), 2021.
ERDDS and R&WI. On random graphs 1960.
Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is
wrong: On evaluating gnn explanation methods. KDD '21, pp. 332 341, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 9781450383325. doi: 10.1 00.1145534445548444788..
URL htt.hhtts://ddoo .orpiioorg/// 10, /4/ . 3467283
E. N. Gilbert. Random graphs The Annals of Mathematicaal Statistics, 30(4): 1959. ISSN 00034851. URL http: wwww.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. 04 2017.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs 06 2017.
Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Bench- mark data sets for graph kernels, 2016. URL http:::://rrppeeeeeeisss.o cs. htw.://eereeee...........tttttae tu-dortmund
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICI.), 2017.
John Lee, Ryan Rossi, and Xiangnan Kong, Graph classification using structural attention. pp. 1674, 07 2018. doi: 10.1 19.114///21811.3219999
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In International Conference Machine Learning, pp. 6666 66666667..66 PMLR, 2021.
Wanyu Lin, Hao Lan, Hao Wang, and Baochun Li. Orphicx: model for interpreting graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13729 13738, 2022.
cunsalit-innspird latent variable
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in Neural Information Processing Systems, 33, 2020.
Christopher Maddison, Andriy Mnih, and Yee Teh. The concrete distribution: continuous relaxation of discrete random variables. 11 2016.
10

---

Published as a conference paper at ICLR 2023
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks easily fooled: High confidence predictions for unrecognizable images. pp. 427-433 433,, 06 2015. doi: 10.1099CVPR22215.226660
Richard Rado. Universal graphs and universal functions. Acta Arithmetica, 9(4):331-340, 1964.
Robert Schwarzenberg, Mare Hübner, David Harbecke, Christoph Alt, and Leonhard Hennig. Lay- erwise relevance visualization in convolutional text graph classifiers. ArXiv, abs/1909. 1091,, 2019.
Ramprasaath R. Sclvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localiza- tion. International Journal of Computer Vision, 128:336-359 2019.
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 Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 22523-22533. Curran Associates, Inc., 2021. URL http:tttpps//ppreeeeiigg/ neurips cC/
7...bee66665cc8... 921 orc.ee/442222eceeceeeeeeeeeeeeee pdf
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. CoRR, abs/1312.6034, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. URL httpp::
n forum? id=rJXMpi kCZ. accepted poster.
Luca Veyrin-Forree Forrer, Ataollah Kamal, Stefan Duffner, Mare Plantevit, and Céline Robardet. On gnn explanability with activation patterns. 2021.
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. ArXiv, abs/2010.05788, 2020.
Bingzhe WU, Yatao Bian, Hengtong Zhang, Jintang Li, Junchi Yu, Liang Chen, Chaochao Chen, and Junzhou Huang. Trustworthy graph learning: Reliability, explainability, and privacy protection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 22, pp. 4838-4839, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 470393803 doi: 10. 00.1145/3534678355259999 3534678 3542597
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Xiao Liu, and Xiang Zhang. Spatio-temporal attentive rnn for node classification in temporal attributed graphs. pp. 3947-3953, 08 2019. doi: 10.24963/ 20195.2019/54.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32:924009251, 12 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. pp. 430, 08 2020a. doi: 10. 11453394486..403000
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, ArXiv, abs/2012.15445, 2020b.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12241-12252. PMLR, 18-24 Jul 2021. URL / mlr. www.s
pwwps/eesssspee /ttess/v139// wrress/v139/yunzil1 html
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. 02 2018.
11

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
Regularization
B The Time Complexity Analysis of GNNInterpreter and XGNN
13
C Justification of Assumptions Regarding Explanation Graph Distribution
14
D Additional Evaluation Results
14
DJ Random Baseline
14
D.2 Acyclic;:: Synthctic Dataset from XGNN Paper
14
D.3 ColorConsistency: Synthetic Data with Node Features and Edge Features
16
E
Verification Study Our Analysis about Qualitative Results
17
Motif]
17
MUTAG
F
Multiple Explanation Graphs Per Class Per Datasel
21
Experimental Setup
21
H
Synthetic Dataset Generation
21
Experimental Details of GNN Classifiers
21
1.1
MUTAG
21
1.2
Cyclicity
23
1.3
Motif
................................
23
1.4
Shape
................................
23
1.5
ColorConsistency
................................
24
1.6
Acyclic
24
Experimental Details of GNNInterpreter
25
A REGULARIZATION
In order to facilitate optimization and ensure that the explanation graphs are constrained to desired properties, we apply multiple regularization terms to the latent parameters.
L, and L2 Regularization. I, and L2 regularizations are widely used encourage model sparsity and reduce the parameter size. In our case, both regularizations are applied Ω during the optimization reduce its size, with purpose mitigating the saturating gradient problem caused by the sigmoid function in Equation 5 For & {1,2}. La penalty term is defined as
Rı, |2
Budget Penalty. Budget penalty is employed in instance-level GNN explanation methods (i.c., PGExplainer (Luo et al.) 2020) and GNNExplainer (Ying et al. 2019)) to generate compact and meaningful explanations. For the model-level explanation, the budget penalty can prevent the size of explanation graphs from growing unboundedly with repeated discriminative patterns. The budget penalty is defined as
Rs softplus ([s) -B)²
8
12

---

Published as a conference paper at ICLR 2023
where B is the expected maximum number of edges in the explanation graph. Unlike PGExplainer, we utilize softplus instead of ReLU to slack the rate of gradient change near the boundary condition. In addition, the penalty is squared further discourage extremely large graphs.
Connectivity Incentive. Inspired by PGExplainer, we apply a connectivity incentive to encourage explanation graphs to be connected, by minimizing the Bullback-Leible divergence between the probabilities of each pair of edges that share a common node in the Gilbert random graph.
Re Σ
Σ iEV (.kE(())
DKL (P.ylPP)
where Psç denotes the Bernoulli distribution parameterized by (ig) As opposed to PGEx- plainer, divergeee is chosen over cross-entropy in order to decouple the entropy of individual edge distributions from the connectivity incentive.
B THE TIME COMPLEXITY ANALYSIS OF GNNINTERPRETER AND XGNN
Algorithm 2: Time Complexity Analysis for GNNInterpreter
Calculate the average graph emhedding v5. from training data and initialize latent parameters 52 H, and while not converged do for l: <- 1...K do
Using the reparameterization trick, sample A, Z, X with Equation 0(2N2 + N) = O(N3) + De (A, 2, X) and graph embedding h + th A, 2, X). O(N?) (k) 88 + pusime.. (h.a) v5.) with the regularization terms. O(K)
Obtain class score a
Calculate T. x Σe
k==
Calculate VnL. V L. and V=L. then update 52, H. and E\r using gradient ascent. O(N2)
(S)) P Softmax(E)) Q Softmax(H).
return G (A, Z, X). where A Bernoulli @). Z ~ Categorical (Q. X ~ Categorical(P))
GNNInterpreter. Let N be the number of vertices for the Gilbert random graph distribution, which indicates the maximum number of nodes in the explanation graph. algorithm 2] for each Monte Carlo sampling process in line 4, it takes O(N2) to sample Å and Z, and takes (NN) to sample X. To obtain the class score and the graph embedding in line 5, it requires one forward pass through the GNN to be explained, which takes O(N2) time. Therefore, the inner loop takes O33 + N) = ONN2) as a whole. Performing K Monte Carlo sampling will thus take O(K O(KN)) N2). Then, in line 6, computing loss function takes O(K) for K samples from the inner loop. In the end, performing back- propagation and gradient ascent also takes O(N2) in line 7. For each iteration, have O(KK- 1) + K) D(KN2). Assuming that GNNInterpreter takes T iterations to converge, the time complexity of the entire algorithm is OTTNN
XGNN. In comparison, XGNN a reinforcement learning- beased based approach for generating explanation graphs. It formulates the graph generator as a policy function that generates one edge at time and uses the GNN class score as a reward function. It leverages the policy gradient method to optimize the policy function during training. The whole XGNN training procedure runs repeatedly for T episodes. For each episode, . generation steps are performed to generate a graph with most M edges. A Rollout, procedure is performed R times in each generation step. During Rollout, each generation step takes O(M) time for the GNN forward pass to evaluate the reward value, with maximum of M generation steps. In total, R times of Rollout procedure will take O time. For M generation steps in each episode, the time complexity is )) Assuming the total number of episodes is T, the time complexity of training XGNN model is then (TTM)).
For a connected explanation graph with N nodes and M edges, M > NN always holds, Since K and R are hyper-parameter parameters, higher than OTT)22 = O(N2). As a result, GNNInterpreter outperfomms XGNN in terms of time complexity.
treat them as constants. Thus, O(TRM²) O(M3) is much
13

---

Published as a conference paper at ICLR 2023
C JUSTIFICATION OF ASSUMPTIONS REGARDING EXPLANATION GRAPH DISTRIBUTION
In this section, would like justify the two assumptions made regarding the explanation graph distribution. Our first assumption is that we assume the explanation graph is a Gilbert graph(Gilber) 1959). Compared with other widely used probability models over graphs (i.e., Erdo-Renyi graph (ERDdS & R&W WT 1960), Rado graph(Rado) 1964), and random dot dot-product model), Gilbert random graph is more suitable for our cases. First, the Erdo-Renyi graph models the graph in a probability space of a fixed number of edges and nodes. However, for generating the model-level explanation graphs, we do not want to enforce a hard constraint on the number of edges a priori. Instead, we want our explanation method to flexibly learn how many edges should be in the explanation graph. Speaking of the Rado graph, it is a random graph with an infinite number of nodes and edges distributed independently, which will result in an explanation graph with an infinite number of nodes, Apparently, we are unable to visually analyze an explanation graph with an infinite number of nodes. Lastly, the random dot-product graph model is just a generalized version of the Gilbert random graph. Therefore, we decide to model the explanation graph distribution as a Gilbert random graph because it is the most reasonable choice for our purpose.
Our second assumption is assuming features for each node and edge are independently distributed. We chose to make this assumption because this will simplify most of the mathematics as a standard practice in statistics. We acknowledge that this assumption might not always hold, but our explanation method actually takes into account the dependency a different way while learning the explanation graph distribution. The reason is that the training process will compute the gradient through the message- paaseegasnng operation inside GNN, and the message- paasge-ppsingggg operation exchanges information across the whole graph in the forward pass. Therefore, the gradient computed backward will capture the correlation among latent parameters of the independent distributions. Through this mechanism, the dependency among edge distributions, edge feature distributions, and node feature distributions are all taken into account in the learning process. That is to say, the independence assumption we made is only applied to sampling an explanation graph from the learned explanation graph distribution, while the latent parameters of those distributions are actually correlated under the hood.
D ADDITIONAL EVALUATION RESULTS
D.1 RANDOM BASELINE
To better demonstrate the effectiveness of our method, we also quantitatively evaluate how the classifier would behave on a set of random graphs, which can serve as the evaluation of a random baseline. For each dataset, we generate 1000 Gabriel random graphs with the same number of nodes the average number of nodes in Table 4 Then, the average class probability with the standard deviation (predicted by the corresponding classifier) for 1000 random graphs is computed and reported in Table 5| As you can see, for all the classifiers we explained, our explanation graph can obtain a significantly higher class probability than the random graphs on average. It is very interesting to see that, the random graphs are very likely to be classified as the negative class, for the dataset including MUTAG, Cyclicity, Is Asyccli,,, and ColorConsistency.
D.2 Is SS_ACCIICC: SYNTHETIC DATASET FROM XGNN PAPER
In order to conduct a more comprehensive comparison with the current state-of-the-ar method (XGNN), we managed to evaluate GNNInterpreter on Is Acyclic data which is synthetically generated by the XGNN authors and posted at XGNN GidHui We trained a GCN classifier on this dataset with accuracy of (see the last row of Table 4) and adopted GNNInterpreter to explain the two classes in Is_ is_Acycic.. The quantitative and qualitative evaluation of GNNInterpreter on Is Acyclic is conducted in a similar manner of other datasets, which shown in Table 5 and Figure respectively.
However, it is unfortunate that XGNN could not provide any meaningful explanation for the GCN model we trained on Is Acyelic (like what we experienced for the Shape and Motif dataset). We spent an extensive amount of time tuning the hyper-parameter of XGNN, but we still could not obtain
14

---

Published as a conference paper at ICLR 2023
meaningful and acceptable explanation graphs. We also attempted to conduct comparative study on the GNN model trained by the XGNN authors because its model checkpoint is available in the google drive folder they shared. But unfortunately, the model definition of the GNN model on Is Acyclic is not available on their GitHub (only the model definition of GNN for MUTAG is provided on their GitHub), so we cannot successfully load the model checkpoint they trained for Is Acycllic. Even so, the quantitative and qualitative evaluation of XGNN on the GCN model we trained on Is As_Acyclicc is still presented in Table 5 and Figure 4
Speaking of the evaluation results, the quantitative result in Table 3 shows that, for both classes, we can consistently generate faithful explanations containing the discriminative pattern of the target class perceived by the GNN. However. the XGNN explanations for both classes are less ideal because the average class probability over 1000 explanation graphs for the Cyclic class is almost zero. This indicates that the explanation graphs generated for both classes will be classified as Acyclic by the GNN, no matter which the target class to explain. In terms of computational time, we can generate an explanation graph about two times faster than XGNN on average. Qualitatively speaking, our explanation graphs for both Cyclic and Acyelic classes are consistent with the class definition with the expected properties (see Figure 4). Namely, the explanation graph for Cyclic contains cycles, while the explanation graph for Acyclic does not contain any cycles. In contrast, for both classes, XGNN fails to generate an explanation graph beyond two nodes, even after our extensive trail-and-error effort.
Table 4: The statistics of datasets including Is Acyclic and ColorConsistency, and some technical details about their corresponding GNN models.
Datasel
Classes
Node Features
Edge Features
Average Edges
Average of Nodes
GNN Type
Test Accurncy
GNN
MUTAG
Kersting 2016
19.
17.93
GCN (Kipl& & Welline
2017
0.9468
Cyanaty
52.76
52.51
NNCW Teinerr
0.9921
Motif
5
77.36
57.07
GCN Kijr & wa
2017
0.9964
Shape
5
71.86
30.17
GCN Cu Weiiigg
2017
0.9725
ItAccyllic
2
30,04
28.46
GCN
1,0000
ColorComistency
$2.33
Venckkoii
2013
0.9963
Table 5: The quantitative evaluation results for all 6 datasets including ls_Acyclic. As the quantitative metric, we compute the average class probability of 1000 explanation graphs and the standard deviation of them for the two classes. In addition, the average training time per class of training 100 different GNNInterpreter and XGNN models is also included for efficiency evaluation.
Datuset [Method)
Predicted Class Probability by GNN
Training Time Per Class
Cyclic
Acyclic 0.927 0,000
As_Acci [XGNN]
0.000
45
Cyclic
Acyelic
Is_Acyclic [Ours]
20
0.999 = 0.001
1.000 =: 0,000
Cyclic
Acyelic 0,857 + 0.155
ls_Acyclic [Randoma]
0.143 = 0.155
Muiagea
Nonmulagen
MUTAG [XGNN]
0.057
0.991 0.083
128
MUTAG (Ours)
Mulagen
Noumulagen
12.
1.000-
0.000
10000 0.000
MUTAG [Randon]
Mutagen
Nonmulagen
0.068 + 0,251
0.32 0.251
ColorConsiicnnyy [Ours]
Consistent
0.110
L000 0,000
Inconsistent
58
ColorConsiseecyy [Random]
Crnsistent
Inconsistent
0.017 0.118
0,983 0,118
Cyclicity [Ours]
Red Cyclic
Green Cycli
Acyelic
49.s
1.000 0,000
1000 0.000
1.000 0.000
Red Cyclic
Green Cyche
Acyelic D.962 0.183
Cyclicity [Random)
0,033 0.143
D015 0,118
Moxif [Ours]
0.918 + 0,268
House
0.999 + 0.032
Xouse-X
1.00 = 0,900
Complete-4
Complete 0.998 + 0.045
83
Moxif [Random]
House
House-X
Complete-4
Complete-5
0.000 0.000
0.000
0.000
0.000 : 0.900
0.000 z 0,000
Shape [Ouns]
Lollipop
Wheel
Grid
Star
0.742 + 0,360
0.989 + 0,100
D9966 + 0.032
1.000 + 0.000
Shape [Random]
Lollipop
Wheel
0.214 à 0,301
0.000 A 0.000
0.151 + 0,307
0.000 1: 0.000
15

---

Published as a conference paper at ICLR 2023
Dataset [Method]
Generated Model-Level Explanation Graphs
Cyclic
Acyclic
score=0.076
score=0.927
Is ]
explanation
example
explanation
example
Cyclic
Acyclic
score=1.000
score=1.000
P_AAcycli(OOurs
explanation
example
explanation
example
Consisteat
Incousistent
score=0.979
scorewl
ColorConsistencyy(Onss]]
explamation
example
explamation
example
Figure 4: The qualitative results for Is Acyclic and ColorConsistency. As reference, the example graph selected from the training data of the GNNs is displayed on the right. Also, the class score after Softmax of the target class is presented above each corresponding explanation graph. For ColorConsistency, the edges with inconsistent color is drawn with a colored outline.
D.3 COLORCONSISTENCY: SYNTHETIC DATA WITH NODE FEATURES AND EDGE FEATURES
With the purpose of further demonstrating the generalizability of GNNInterpreter, we conduct an experimental study on explaining a (VT(Veličkovi al.) 2018) model trained classify synthetic dataset (ColorConsistency) with both node features and edge features. To be specific, ColorConsistency contains two classes: the Consistent class is the graphs with all the node features and edge features has consistent color; and the Inconsistent class is otherwise. The consistency of color is defined as the natural color addition physics. For example, if node is in red and node is in green, then the edge between u and should be in yellow. If there is one edge in the graph that does not follow this color consistency, then this graph should categorized into Inconsistent class. The statisties of ColorConsistency and the test accuracy of the corresponding GAT Classifier are presented in Table 4 Please refer algorithm for detailed generation procedure of ColorConsistency.
To assess our effectiveness on explaining the GAT classifier trained on ColorConsistency, we quantita- tively and qualitatively evaluate the faithfulness of the generated explanation graph. According the quantitative result in Table 5] we can consistently generate an explanation graph with discriminative features of the corresponding class because the predicted class probability of our explanation graphs for both classes is close to or equal to on average. Speaking of the qualitative evaluation, the explanation graph per class along with the predicted class probability is presented Figure [ The edges with inconsistent color are drawn with colored outline. As you can see, the explanation graph of the Inconsistent class matches the definition ground truth Inconsistent graph because every edge all have an inconsistent color. It may indicate that the GNN has correctly learned the discriminative features of the Inconsistent class. The more discriminative features are detected, the more confident GNN is to classify it as the Inconsistent class. However, the explanation graph of the Consistent class does not follow the true definition of "Consistent" so the ground truth label of the Consistent explanation graph should be "Inconsistent". This is very interesting observation because the GNN test accuracy is as high as 0.9963 (see Table 4). The explanation of the Consistent class reveals potential risk of misclassification for graphs with few inconsistently colored edges.
16

---

Published as a conference paper at ICLR 2023
E A VERIFICATION STUDY OF OUR ANALYSIS ABOUT QUALITATIVE RESULTS
From Figure 1 we can see that the explanation graphs for some classes are different from the true graphs in the training data, which might indicate the potential pitfall of the explained GNN. However, since the ground truth model-level explanation graph does not exist, it is difficult to verify the correctness of analysis regarding these potential pitfalls. In this section, we conducted the controlled experimental studies for MUTAG, House-X in Motif and Complete-4 in Motif, to verify our high-leve interpretation of the explained GNN mentioned in the subsectiio 5.2
E.1 MOTIF
Complete-4 In subsecction 5.2, we infer that the discriminative feature the GNN tries to detect is that "every node should have 3 neighbors in different color". This rule is concluded from our observation of the commonality between explanation graph and the ground truth motif. We found 8 different motifss (including the ground truth Complete-4) which satisfy this rule, as shown in Figuure 3| Given fixed set of 5000 Rome graphs, these 8 different motifs 5000 Rome graphs. As a result, we obtain 8 sets of graphs, and each set includes 5000 graphs corresponding to a single motif. For each motif set, the average predicted class probability of each class and the total number of graphs that are classified as each class are presented in the Table 6 and Table 7 respectively. We can clearly see that motif 1-6 successfully fool the explained GNN because their predicted class probability of Complete-4 is significantly higher than their predicted class probability of Others. These results indicate that our previous analysis in ssubsectionn 5.2 regarding how the GNN makes predictions for Complete-4 is correct. Namely, the GNN trained with the Motif dataset is highly likely to incorrectly classify the graphs containing a misleading pattern identified by the GNNntterpre,rr, even though the GNN accuracy is high 0.9964 (see Table I.. Therefore, GNNinterpreter can be served as a sanity check for GNNs, especially the ones with high accuracy, and remind people to be cautious when applying GNNs to classify some unseen graphs containing the misleading patterns identified by the GNNInterpreter.
attached the same node of those
Motif 1
Motif 2
Motif 3
Motil
Motil
Figure 5: Plausible Complete-4 motifs. The motifs satisfying the rule that every node should have neighbors in different color. The motif 8 is the ground truth Complete-4 motif. The ground truth class label of motif 1-7 should be the Others class.
Table The quantitative results of plausible Complete-4 motifs. For each motif set (column), the average predicted class probability of each class (row) is computed by averaging over 5000 graphs containing the corresponding t
Motif I
Motif 2
Motif
Motif 4
Motif 5
Motif 6
Motif
Motif 8 (GT)
Others
0,4123
0.4064
0.4122
0.4033
0.4116
0.4019
0.9974
0.0066
House
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0021
0.0000
House-X
0.0002
0.0006
0.0004
0.0007
0.0003
0.0002
0.0001
0.0000
Complete-4
0.5875
0.393
0.3874
0.596
0.5881
0,3978
0.0004
0.9934
Complete-5
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0001
0.0000
17

---

Published as conference paper at ICLR 2023
Table The classification results of plausible Complete-4 motifs. For each motif (column), the total number of graphs that are classified as classes (row) is presented in this table. The sum of all columns should be 5000 because that is the total number of graphs in each motif set.
Motif 1
Motif 2
Motif 3
Motif
Motif 5
Motif 6
Motif 7
Motif 8 (GT)
Others
2030
1983
2016
1985
2031
1966
4994
House
0
4
House-X
0
Complete-4
2969
3014
2983
3011
2986
3033
Complete-5
0
House-X subsecction 5.2 we speculate the discriminative feature perceived by the explained GNN is that "orange node and red node should have 3 neighbors except purple node, green node and blue node should have neighbors different color". This discriminative feature also deduced from the commonality between our explanation for House-X X and the ground truth motif. The 9 motifs satisfying this rule are shown in Figure 6 The controlled experimental study for House-X class is conducted in similar manner for Complete-4 class. The quantitative results for each motif set in Table 8 and Table 9 show that all the plausible motifs satisfying the rule are highly likely to be matter what number of graphs from motif set 1-8 are misclassified to the House-X class, especially motif and motif 6. It also indicates that the GNN is easily fooled by the graphs containing the plausible motifs satisfying the rule that "orange node and the red node should have 3 neighbors except the purple node, the green node and the blue node should have 4 neighbors in different color". In summary, speaking of the GNN trained on the Motif dataset with an accuracy of 0.9964, this verification study shows that our explanation results are faithful because it successfully reveals the true model pitfalls.
classified as House-X,
their corresponding ground truth labels. Specifically, large
Molif
Motil
Motif 3
Motif
Mobil
Motif
Mottf
Figure 6: Plausible House-X motifs. The motifs satisfying the rule that the orange node and the red node should have neighbors except the purple node, the green node and the blue node should have 4 neighbors in a different color. The motif 9 is the ground truth House-X motif. The ground truth class label of motifs 1-8 should be the Others class.
E.2 MUTAG
According to the explanation graphs provided in Figure the discriminative feature captured by our explanation graph for the mutagen class is the occurrences of the NO2 group. However, there are no special patterns observed from our explanation graph for the non-mutagen class. To verify whether the occurrences NO2 group is truly the discriminative feature GNN tries to detect when making a prediction for the mutagen class, designed controlled experiment such that each set of graphs contains different numbers of NO2 group while keeping other experimental settings the same. To be specific, given 1000 randomly generated Gabriel graphs with 5-10 nodes, each time attach 15
18

---

Published as a conference paper at ICLR 2023
Table 8: The quantitative results of plausible House-X motifs. For each motif set (column). the average predicted class probability of each class (row) is computed by averaging over 5000 graphs containing the corresponding motif.
Motif
Motif
Motif 3
Motif 4
Motif 5
Motif 6
Motif 7
Motif 8
Motif 9 (GT)
Others
0.2929
0.4411
0.3558
0.3849
0.4317
0.1296
0.3351
0.3373
0.0022
House
0.0000
0.0000
0.0000
0.0000
0,0000
0.0000
0.0000
0.0000
0.0000
House-X
0.7053
0.5581
0.6435
0.6144
0.5678
0.8700
0.6641
0.6620
0,9978
Complete-4
0.0002
0.0003
0.0004
0.0004
0.0004
0.0003
0.0008
0.0007
0.0000
Complete-5
0.0016
0.0004
0.0002
0.0003
0.0002
0.0001
0.0000
0,0000
0.0000
Table 9: The classification results of plausible House-X motifs. For each motif set (column), the total number of graphs that are classified classes (row) is presented in this table. The sum of all columns should be 5000 because that is the total number of graphs in each motif set.
Motif
Motif
Motif
Motif
Motif
Motif
Motif 7
Motif 8
Motif (GT)
Others
1434
2251
1808
1970
2183
597
1682
1696
10
House
0
0
0
0
0
0
0
0
0
House-X
3566
2749
3192
3030
2817
4403
3318
3304
4990
Complete-4
0
0
0
0
0
0
0
0
Complete-5
0
0
0
0
0
0
0
0
nodes to these random graphs. These 15 nodes will be divided into 5 groups, and each group has nodes. The frequency of NO2 group appearing in these 15 nodes varies from 0 to 5. For instance, in Figure 7] the example graph for 5 NO2 contains a Gabriel graph with 6 nodes and 5 NO2 groups; the example graph for 4 NO2 contains the same Gabriel graph, 4 NO2 groups, and a random group of nodes. As a result, we will obtain 6 sets of graphs and each set includes 1000 graphs containing a fixed number of NO2 group.
Then, we feed these 6000 graphs into the GNN trained with the MUTAG dataset to obtain the quantitative results. Similar to what we did for Motif dataset, for each 1000 graphs with a fixed number of NO2 group, the average predicted class probability for each class and the number of graphs being classified as each class presented in Table 10 and Table III We can clearly see that as more and more NO2 group occurs, the GNN become more and more certain about classifying these graphs as the mutagen class. That is to say, the number of occurrences of NO2 groups indeed is the discriminative features the GNN tries to detect when making a prediction for the mutagen class, which is consistent with our previous finding when analyzing our explanations for both classes in subsection 5.2, Thus, this verification study proves that our explanations for MUTAG dataset are faithful and informative because they can correctly interpret the high-level decision-making process of the GNN.
has been shown that GNNs trained on binary classification tasks can suffer from the bias attribution issue (Faber et al. 20 Essentially, the GNN with bias attribution issue will classify any graphs as class A unless it finds sufficient evidence of class B. From Table 10 and Table 11, it is interesting to observe that the GNN seems biased toward the non-mutagen class unless the GŇN finds enough evidence (i.e., NO2 group) for the mutagen class. This indicates that this GNN is suffering from the bias attribution issue that no special pattern observed from our explanation graph for the non- mutagen class in Figure [ Therefore, this verification study also proves that the faithful explanation generated by GNNInterpreter can help us to diagnose whether the GNN suffering from the bias attribution issue.
Table 10: The quantitative results of graphs with different numbers of NO2 groups. For each 1000 graphs with the fixed number of NO2 groups (column), the average predicted class probability of each class (row) is computed by averaging over 1000 graphs containing the fixed number of NO2 group.
Nodes
NN.,
NOO,
NO.
NO.,
4NO,
NO
Mun-Meuagen
0.9837
0.9651
0.9186
0.7593
0.3998
0.0714
Mutagen
0.0163
0.0349
0.0814
0.2407
0.6002
0.9286
19

---

Published as a conference paper at ICLR 2023
NO2
2 NO2
3 NO2
NO2
5 NO2
(a) Example Graphs
Br
(b) Node Labels
Figure 7: The example graphs with different numbers of NO2 groups attached to the same Gabriel graph with 6 random nodes.
Table 11: The classification results of graphs with different numbers of NO2 groups For each 1000 graphs with the fixed number of NO2 groups (column), the number of graphs being classified as the classes (row) is presented. The sum all columns should be 1000.
15 Nodes
0 NO,
NO,
2 NNO,
NO,
NO,
5 NO
Non-Mutagen
984
965
917
758
396
71
Mutagen
16
35
83
242
604
929
20

---

Published as a conference paper at ICLR 2023
F MULTIPLE EXPLANATION GRAPHS PER CLASS PER DATASET
The redundant evidence pitfall is potential problem in evaluating the instance-level explanation when the ground truth explanations are not unique (Faber et al. 202T). Specifically, when there are multiple ground truth explanations, comparing the generated explanation against only one ground truth explanation might yield wrong weak results. However, for a model-level explanation method, the ground truth explanation graph does not exist because feature the GNNs learned for each class is. Therefore, we do not rely on the ground truth explanation evaluate our method. Instead, we can directly measure how discriminative the generated explanation is for a certain class by the corresponding class score predicted by the GNN. If the class score after softmax is close I, indicates that the generated explanation indeed contains the discriminative features GNN tries to detect for certain class. In word, the redundant evidence pitfall in evaluating our method does not exist because we do not rely on the ground truth explanation evaluate our method.
know what the true discriminative
However, for model-level explanation methods, there might exist multiple discriminative features the GNN tries to detect for specific class. In this case, different explanation graphs could be generated by applying our method for multiple times with different random initialization. Given that generating an explanation per class only takes less than minute (as shown in Table 5), we believe generating multiple explanations per class is feasible in terms of the time cost. For each dataset, multiple qualitative examples per class shown in Figure
G EXPERIMENTAL SETUP
All the experiments are conducted on a single core of an Intel Core 19 CPU. Speaking of the software, all the models are implemented in Python 3.9. We use PyTorch 1.10 for auto-differentiation and numerical optimization. Besides, all the GNNs are implemented with PyTorch Geometric 2.0. We also use PyTorch-Scatter library to handle vector gather-scatter operations. Lastly, we utilize NetworkX for graph data generation and processing.
H SYNTHETIC DATASET GENERATION
In the experimental study, we evaluate the efficacy of GNNInterpreter on 4 synthetic datasets: Cyclicity, Shape, Motif, ColorConsistency, and Is is_Acyclic. Among them, Cyclicity, Motif, and ColorConsistency are synthetically generated on top of Rome Datase which has 11534 undirected graphs with 10-100 nodes. The generation procedures for the first 4 synthetic datasets are specified in algorithm 3 algorithm 4 algorithm 5] and algorithm 6) respectively. Lastly, Is Acyclic dataset is dataset synthetically generated by the XGNN authors (Yuan et al. 2020a).
I EXPERIMENTAL DETAILS OF GNN CLASSIFIERS
In the experimental study, we adopt GNNnnterpreter to explain 5 GNN classifiers which are trained on 5 different datasets. In this section, we will describe some experimental details about the GNN models for datasets. These experimental details include the model architecture, hyper-parameter settings, and test FI scores per class obtained by the GNN models.
1.1 MUTAG
The GNN classifier we implemented for MUTAG dataset is a deep GCN model that contains 3 GCN layers of width 64, global mean pooling layer, and dense layers in the end. The model uses LeakyReLU as activation. Before training, the model parameters are initialized with the Kaiming initializer. During training, the AdamW optimizer is used for optimization with learning rate of 0.01 and weight decay of 0.01. The Fl scores for two classes in Table show that the GNN is more accurate when making decisions the Mutagen class.
21

---

Published as a conference paper at ICLR 2023
Datawt
Clooe
GNNinterpretee Model-Level Explatation Graphe
Mutagen
Not-milages
Red Cyclic
Cyclicity
Green Cyclic
Acyclic
House
Honse X
Complese-4
Complese-S
b. Asyelic
Acyclic
Consistens
ColoConsisseeey
Incomsistent
Figure 8: The qualitative results for 6 datasets. For each class in all datasets, multiple explanation graphs with the class probability of predicted by the GNNs are displayed. If the dataset has the node feature or edge feature, the different colors in the nodes and edges correspondingly represent different values in the node feature and edge feature.
22

---

Published as a conference paper at ICLR 2023
Algorithm 3: Cyclicity dataset generation procedure
Edge Classes: (RED, GREEN]
Graph Classes: IRED-CYCLIC, GREEN-CYCLIC, ACYCLIC)
Input: Rome Dataset
Output: A collection of pairs consisted of a graph and its label
for G in Rome Dataset do
Randomly label each edge in G as RED or GREEN.
G acyclic then yield (G, ACYCLIC) break
while more than one eycle exists in
Remove random edge from random cycle in G. Randomly pick color Ceyele (RED, GREEN]. Relable all edges in the remaining cycle in G Coyele- Randomly pick color Codee (RED, GREEN). Relable random edge in the remaining cycle in as Cedge. if Ceycle = Codge RED then yield (G, RED-CYCLIC
10
11
12
14
Ceyele = Cotge = GREEN then
15
yield (G, GREEN-CYCLIC)
16
clse
17
yicld (C, ACYCLIC)
Algorithm 4: Motif dataset generation procedure
Node Classes: [RED, GREEN, ORANGE, BLUE, MAGENTA]
Graph Classes: [HOUSE, HOUSE-X, X, COMPLETE-4, COMPLETE-S, OTHERS]
Input: Rome Dataset
Output: A collection of pairs consisting of graph and its label
Let GGoorss, Gitouse-x, GCOMPLETE-,, GCOMPLETE-S f be motifs for the corresponding classes.
Define + as graph operator such that G1 + G2 generates union graph G1 G2 an additional edge between random node in G1 and random node in G2-
for G in Rome Dataset do
Randomly assign color Gnode E (RED. GREEN, ORANGE, BLUE, MAGENTA) for each node in G Randomly select label L E (OTHERS, HOUSE, HOUSE-X. COMPLETE-4, COMPLETE-5), if L OTHERS then Let GoiBers be random motif in [GhoUSE, GHOUSE GCOMPLETE GCOMPLETE but with random edge being removed.
yield (G + Gr.,
1.2 CYCLICITY
The GNN classifier for Cyclicity dataset is deep NNConv model that contains 5 NNConv layers of width 32 with a single-layered edge network, a global mean pooling layer, and 2 dense layers end. Before training, the model parameters Adam optimizer is used for optimization with a learning rate 0.01, learning rate decay of 0.01, and weight decay of 0.01. As shown in Table 12 all three classes have similar Fl scores, which means that the GNN model has a balanced performance on each class.
initialized with Kaiming initializer. During training,
1.3 MOTIF
The Motif dataset uses exactly the same model architecture and hyper-parameter settings the MUTAG dataset. The Fl score per class presented in Table 12 indicates that the GNN achieves a perfect performance on Complete-5 class and near-perfect performance on every other class.
I.4
SHAPE
The Shape dataset uses the same model architecture and hyper-parammn parameter settings as the MUTAG dataset except that the model contains 4 GCN layers instead of 3 GCN layers. Also, the F1 score per
23

---

Published as a conference paper at ICLR 2023
Algorithm 5: Shape dataset generation procedure
Graph Classes: [LOLLIPOP, WHEEL, GRID, STAR, OTHERS)
Output: collection pairs consisted a graph and its label
for 8000 times do
Randomly select a label L E {OTHERS, LOLLIPOP, WHEEL, GRID, STAR). switch L do
case LOLLIPOP do
Sample lollipop graph GoOLLIPP with random number head nodes n E {4,.., 163 and random number of tail nodes m {1,... 16).
case WHEEL do
Sample wheel graph GWeEEL with random numher of non-center nodes {4, 64].-
case GRID do
Sample grid graph Gciann with random width w E (2....,8 8) and random height h {2,-..88)
10
case STAR do
Sample star graph GSTAR with random number of non-center nodes E (4....,61) 64).
12
case OTHERS
13
Sample Binomial random graph Goruas with random number nodes n {8,..., 32} and random edge probability [0.2, 1].
14
Add random number of noisy edges to Gr with random ratio p [0,0.2].
15
yield (Gz, L)
Algorithm 6: ColorConsistency dataset generation procedure
Node Classes: [RED, GREEN, BLUE)
Edge Classes: (RED, GREEN, BLUE, YELLOW, CYAN, MAGENTA)
Graph Classes:
(CONSISTENT, INCONSISTENT)
Output: A collection of pairs consisting graph and its label
for G in Rome Dataset
Randomly assign a color C. E {RED, GREEN, BLUB) for each node in G for each edge (u. v)) do
Assign color C. C. C. {RED, GREEN, BLUE, YELLOW, CYAN, MAGENTA). where denote operator to mix two colors. Randomly select label L E [CONSISTENT, INCONSISTENT). if L INCONSISTENT then for each in K random edges G. where of edges in Reassign a random color C E {RED, GREEN, BLUE, YELLOW, CYAN, MAGENTA]|MC.. yield (G, L)
class in Table 12 shows that the GNN can perfectly predict the Star class, whereas the predictions for the Lollipop class and the Grid class are less accurate.
I.5 COLORCONSISTENCY
The ColorConsistency dataset has both node features and edge features. So, we take advantage of the GAT model Veličković al. (2018) to classify this type of graph data. The GAT model use contains GAT layers of width 16, global sum pooling layer, and 2 dense layers in the end. Before training, the model parameters are initialized with the Kaiming initializer. During training, the Adam W optimizer is used for optimization with learning rate of 0.001, a learning rate decay of 0.01, and weight decay of 0.01. The model able predict both classes with Fl scores very close 1.0.
I.6 Is_ACYC
The Is_ s_Acycliic dataset uses the same model architecture and dataset except that pooling is used instead of mean pooling for the global pooling layer, due to the nature of the task that the class prediction can very sensitive to local patterns. The model is able to predict both classes perfectly with an F1 score of 1.0.
settings as the Shape
24

---

Published as a conference paper at ICLR 2023
Table 12: The Fl score per class of the corresponding GNN classifiers for all datasets.
Dataset
F1 Scores of GNN Classifier
Mutagen
Nonmutagen
MUTAG
0.961
0.917
Red Cyclic
Green Cyclic 0.992
Acyclic
Cyclicity
0.995
0.993
House
House-X
Complete-4 0.996
Complete-5
Motif
0.998
0.998
1.000
Lollipop
Wheel
Grid 0.966
Star
Shape
0.969
0.994
1.000
Cyclic
Acyclic
ls_Acyclic
1.000
1.000
Consistent
Inconsistent
ColorConsistency
0.9963
0.9962
Table 13: The regularization weights of GNNInterpreter for explaining the GNN models correspond- ing to each dataset.
Regularization Weights
Dataset
Class
R1.,
R
Ra
R,
Mutagen
5
20
MUTAG
Nonmutagen
2
10
Red Cyclic
5
10000
100
Cyclicity
Green Cyclic
10
5
2000
50
Acyclic
10
2
5000
50
House
1
5000
House-X
5
2
2000
Motif
Complete-4
5
10000
Complete-5
10000 5
Lollipop
5
5
Wheel
10
5
10
Shape
Grid
1
2
Star
10
2
200
Cyclic
0
0
500
Is Is_Acyclic
Acyclic
5
500
Consistent
50
ColorConsistency
Inconsistent
0
50
J EXPERIMENTAL DETAILS OF GNNINTERPRETER
For all experiments, we choose to set the Concrete Distribution temperature 7 = 0.2. We use the sample size K = 10 for all Monte Carlo samplings. For optimization, adopt the SGD optimizer with learning rate of and terminate the learning procedure until convergence. Additionally, in the training objective, the embedding similarity weight l is set to I for every dataset except MUTAG. For the MUTAG dataset, we let μ 10 due to its nature that the structure of the graphs in the dataset needs to follow certain domain -peciff rules. higher value of μu allows the GNNInterpreter to implicitly capture these rules from the average graph embeddings. Speaking of the regularization weight, we employ grid search to obtain the best results under different combinations of regularization terms. To ensure the reproducibility of our experimental results, we also report the exact regularization weights used for all the quantitative and qualitative evaluations from the manuscript in Table 13 Note that we adopt constant weight strategy for LI regularization Rt, L2 regularization Ri,, and connectivity constraint R. throughout the training process. In contrast, for budget penalty Rg, we employ 500-iteration initial warmuup period to gradually increase the weight starting from 0.
25


Reviews:
[{"review_id": "YU0bGfhta3F", "reviewer": "Reviewer_ErAv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "With the increasing use of complex black-box Graph Neural Networks (GNNs) in high-stakes applications, it is critical to developing explanation algorithms to understand their decisions. To this end, several methods have been proposed to generate instance-level explanations for GNN predictors. However, most works focus on generating predictions for individual node- or graph-class predictions and fail to generate model-level explanations that aim to understand the global behavior of the model. In this work, the authors propose, GNNInterpreter, a probabilistic generative model-level explanation method for GNNs that learns an explanation graph distribution that identifies the discriminative features of a graph for a given class prediction. Experimental results show that GNNInterpreter generates faithful explanations for synthetic and real-world datasets.", "summary_of_the_review": "Look at the strengths and weaknesses for complete details.", "strength_and_weaknesses": "**Strengths**\n\n1. The paper presents a new method for generating model-level explanations for graphs with different types of node and edge features.\n2. The proposed algorithm is computationally efficient and takes 10x less time than currently used graph explainer algorithms.\n\n**Weaknesses and Open Questions**\n1. The paper argues that an important goal of a GNN model explainer is to confine the distribution of the explanation graphs to the domain-specific boundary and leverages the abstract knowledge learned by the GNN itself to prevent the explanation from deviating from the true data distribution. However, the distribution from this representation may not be essentially similar to the true data distribution.\n2. GNNInterpreter assumes white-box access to the model and training dataset, where it approximates the domain knowledge using the average embedding of all graphs $\\psi_{c}$ from the target class in the training set. This drastically limits the approach to smaller models and datasets.\n3. The description of GNNInterpreter is incomplete in the main tex. For instance, Equation 8 only provides the generic loss for training $\\omega_{ij}$, $\\eta_{ij}$, and $\\xi_{ij}$ parameters and does not talk about the critical $\\ell_{p}$-loss and other constraints.\n4. The paper does not talk about the *Redundant Evidence* pitfall mentioned in Faber et al. [1] Do they report the results by taking the maximum score across all possible explanations for a given class?\n5. It would be great to comment on other baseline explainers for graph classifiers like [2-3] or a random baseline.\n\n**References**\n1. Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. When comparing to ground truth is wrong: On evaluating gnn explanation methods. In KDD, 2021.\n2. Veyrin-Forrer, L., Kamal, A., Duffner, S., Plantevit, M., & Robardet, C. On GNN explanability with activation patterns, 2021.\n3. Duval, Alexandre, and Fragkiskos D. Malliaros. GraphSVX: Shapley value explanations for graph neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springee, 2021.\n", "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": {}}, {"review_id": "NAZ64emA1n", "reviewer": "Reviewer_B5NJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "summary_of_the_paper": "This paper presents a probabilistic generative model-level explanation method for GNN named GNNInterpreter. By relaxing the adjacency matrix, the node features, and the edge features to continuous variables, it generates a graph capturing the critical characteristics that the GNN models discriminate the classes.\n\nCompared to its counterpart XGNN, GNNInterpreter is capable of generating graphs with continuous node features as well as edge features. It also requires no domain expertise or knowledge.", "summary_of_the_review": "The interpreter for GNN presented in the paper outperforms XGNN, which is the SOTA GNN model-level explainer. Most of the paper is well-written and the proposed method is well-supported. Some minor weaknesses need to be fixed.", "strength_and_weaknesses": "Strength:\n1. Great ambition in attempting to interpret GNN models on different types of graphs.\n2. By using an objective function instead of adopting the reinforcement learning setting, the efficiency is greatly improved.\n3. The relaxation on the adjacency matrix and the features is clearly described.\n\nWeakness:\n1. Need to clarify that this method focuses on graph classification task, similar to XGNN.\n2. None of the experiments is carried out on a graph with both node features and edge features.\n3. Due to the space limitation, the algorithms and most of the figures are in the appendix, making the main body of the paper a little bit dry.\n4. In \"The lack of self-explainability becomes a serious obstacle for applying GNNs to real-world problems, especially those when making wrong decisions may incur an unaffordable cost\" the \"those\" should be removed. \n\nSuggestion:\n1. Try to move Algorithm 1 back into the main body of the paper. It's essential for understanding the whole structure of GNNInterpreter.\n2. Instead of continuous relaxation, maybe optimization methods on the discrete settings could be considered as alternatives, such as subgradient.\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "D3749MlZqu2", "reviewer": "Reviewer_JE8w", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes GNNInterpreter to detect a model-level explanation for GNN. GNNInterpreter learns a probabilistic generative graph distribution to detect the model-level explanation without introducing another model. Experiments are evaluated on both synthetic and real-world datasets. ", "summary_of_the_review": "This paper is easy to read and proposes a new approach to explain GNN models with a probabilistic generative graph. The author should explain the problem, followed by laying out their arguments more clearly. More experiments enforcing the arguments empirically are needed. Overall, the current version of this paper is not ready to be published in ICLR.", "strength_and_weaknesses": "**Strengths:**\n1. It is novel that this paper learns a probabilistic generative graph distribution to generate an explanation graph with different types of node features and edge features.\n2. The experimental results are analyzed in detail, and the proposed method is tested on several datasets. \n\n**Weaknesses:**\n1. Some of the latest related works on the instance-level explanation of GNN are not thoroughly discussed, such as causal explanation GEM [1] and OrphicX [2], reinforcement learning explanation RG-Explainer [3] and perturbation-based explanation SubgraphX [4].\n2. The experiments in this paper to evaluate explanation only focus on graph classification, while other GNNs tasks are also crucial in explainability research, such as node classification and link prediction.\n3. In Section 4.2, the authors present two assumptions to learn a probabilistic generative graph distribution, but an explanation of the reasonableness of the assumptions is missing.\n4. In Section 4.3, the reparameterization trick is efficient for the sampling function to be differentiable. However, it is not new to use this idea which has been used by previous work such as PGExplainer [5].\n5. It is said that \"instance-level methods are very time-consuming,\" but the authors do not compare the proposed method with these instance-level models to illustrate this claim. It is suggested to add relevant comparative experiments to support this claim.\n6. In addition, it does not analyze the time complexity and shows why GNNInterpreter saves more time than XGNN, which is critical for showing the effectiveness of the proposed method.\n7. In Section 5.2, the experiments only choose GCN or NNConv as GNN models, which are not comprehensive to illustrate model-agnostic on other GNN models such as GAT and GraphSage.\n8. In Section 5.2, the experiments in the verification study show the reasonableness of speculation to House-X class. However, it does not adequately explain the reasons for the difference between the explanations and ground truth in House-X and Complete-4.\n\n[1] Generative Causal Explanations for Graph Neural Networks. ICML, 2021.   \n[2] OrphicX: A Causality-Inspired Latent Variable Model for Interpreting Graph Neural Networks. CVPR, 2022.   \n[3] Reinforcement Learning Enhanced Explainer for Graph Neural Networks. NeurIPS, 2021.   \n[4] On Explainability of Graph Neural Networks via Subgraph Explorations. ICML, 2021.   \n[5] Parameterized Explainer for Graph Neural Network. NeurIPS, 2020.   \n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0uPZPv0smE", "reviewer": "Reviewer_jhWR", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper proposes a model-level explanation method for GNNs. The core idea is, given a class, to maximize a graph that has the highest softmax-activation for that class. In order to obtain graphs that are meaningful, a regularization term is added forcing similarity of the graph embedding with the average embeddings for the same class. Because many components of a graph are discrete (e.g., the presence or absence of an edge), they apply the Gumbel-Softmax trick to reparameterize the gradients, under the assumption that all edges can be independently sampled. They compare the method with a baseline method, XGNN, or a series of standard benchmarks.", "summary_of_the_review": "Overall, I believe the results are interesting from the point of view of xAI on graphs. However, the method is a simple adaptation of techniques from the CV world. The experiments lack some important points to showcase the validity of the methods. Because of this, I think this is at most a borderline paper in terms of the ICLR audience, that could benefit from the points raised above, especially concerning a more proper evaluation of the state-of-the-art and more experimental details.", "strength_and_weaknesses": "First, the method which is proposed is basically activation maximization applied to a graph, with a simple \"localization\" term (see, e.g., [1]) to force the embeddings to lie close to the embeddings of the real graphs. I would suggest to discuss explicitly the relation of the method with known methods from the CV literature. In my experience, in the CV literature this kind of localization regularization is uncommon because it tends to \"collapse\" the answer on the reference point (the average of the embeddings). It would be interesting for the authors to evaluate whether this is also happening here (i.e., what happens if I simply take the $\\hat{\\phi}$ term from (2) and visualize it after proper thresholding?).\n\nThe core innovation of the work is using the GS trick to reparameterize the gradients. Also here, this is quite common today in the GNN literature (e.g., DGM for latent graph imputation, PGExplainer for explanation, adaptive graph sparsification, ...). There are also many recent proposals to generate discrete structures that do not require to assume independence of all edges, which is really strong [2]. I believe it would be better to discuss these applications on the paper, as they are clearly related (especially PGExplainer and similar works).\n\nThird, the authors mention several time that \"the generated explanation is both faithful and valid regarding the domain-specific knowledge\", but this cannot guaranteed since this is only enforced through a weak regularization (indirectly via the embeddings). Unless this is tested more extensively, I believe these sentences are not valid.\n\n[1] https://www.sciencedirect.com/science/article/pii/S1051200417302385\n[2] https://arxiv.org/abs/2106.01798", "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": "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:

Decision: Accept: poster