Reinforcement Learning Enhanced Explainer for Graph Neural Networks
Authors: Caihua Shan
Yifei Shen
Yao Zhang
Xiang Li
Dongsheng Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph neural networks
Interpretability
Reinforcement Learning

Abstract: Graph neural networks (GNNs) have recently emerged as revolutionary technologies for machine learning tasks on graphs. In GNNs, the graph structure is generally incorporated with node representation via the message passing scheme, making the explanation much more challenging. Given a trained GNN model, a GNN explainer aims to identify a most influential subgraph to interpret the prediction of an instance (e.g., a node or a graph), which is essentially a combinatorial optimization problem over graph. The existing works solve this problem by continuous relaxation or search-based heuristics. But they suffer from key issues such as violation of message passing and hand-crafted heuristics, leading to inferior interpretability. To address these issues, we propose a RL-enhanced GNN explainer, RG-Explainer, which consists of three main components: starting point selection, iterative graph generation and stopping criteria learning. RG-Explainer could construct a connected explanatory subgraph by sequentially adding nodes from the boundary of the current generated graph, which is consistent with the message passing scheme. Further, we design an effective seed locator to select the starting point, and learn stopping criteria to generate superior explanations. Extensive experiments on both synthetic and real datasets show that RG-Explainer outperforms state-of-the-art GNN explainers. Moreover, RG-Explainer can be applied in the inductive setting, demonstrating its better generalization ability. 

Reinforcement Learning Enhanced Explainer for Graph Neural Networks
Caihua Shan', Yifei Shen', Yao Zhang', Xiang Li', Dongsheng Li!
'Microsoft Research Asia
{caihua shan, dongsheng. 1.] @mi crosoft....... com
The Hong Kong University of Science and Technology
yshenaw&connect. ust. hk
FFudan University
yaozhang@fudan edu.
"ast China Normal University
xiangl @dase. ecnu secuueduu. cn
Abstract
Graph neural networks (GNNs) have recently emerged as revolutionary technolo- gies for machine learning tasks on graphs. In GNNs, the graph structure is generally incorporated with node representation via the message passing scheme, making the explanation much more challenging. Given a trained GNN model, a GNN explainer aims to identify most influential subgraph to interpret the prediction of instance (e.g., a node or a graph), which is essentially a combinatorial optimization prob- lem over graph. The existing works solve this problem by continuous relaxation or search-based heuristics. But they suffer from key issues such as violation of message passing and hand-crafted heuristics, leading to inferior interpretability. To address these issues, we propose a RL-enhanced GNN explainer, RG-Explainer, which consists of three main components: starting point selection, iterative graph generation and stopping criteria learning. RG-Explainer could construct a con- nected explanatory subgraph by sequentially adding nodes from the boundary of the current generated graph, which is consistent with the message passing scheme. Further, we design an effective seed locator to select the starting point, and learn stopping criteria to generate superior explanations. Extensive experiments on both synthetic and real datasets show that RG-Explainer outperforms state-of-the-arr GNN explainers. Moreover, RG-Explainer can be applied in the inductive setting, demonstrating its better generalization ability.
Introduction
Graph Neural Networks (GNNs) extend neural network models on ubiquitous graph data via utilizing the message passing scheme to incorporate graph structures with node features. They have achieved state-of-the-arr performance not only in classic machine learning tasks graphs, e.g., node classifi- cation [10, 28), link prediction [38], and graph classification [33], but also in reasoning tasks, e.g.. intuitive physics [4] mathematical reasoning [24] and IQ tests 3 Similar to most deep learning methods, one major limitation GNNs is the lack of the interpretabilityy for the predicted results; post-hoc analysis is usually needed to explain the results.
To enhance the interpretability of GNNs, line of works B4 30
focused on developing GNN explainers. The goal of GNN explainers is to identify most influential subgraph structure to interpret the predicted label of an instance (e.g., node graph). can be generally formulated as
37 31
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

an optimization problem that maximizes the mutual information between the predicted results and the distribution of relevant subgraphs under some size constraints.
The pioneering works, e.g. GNNExplainer (34] and PGExplainer
attempt to solve the opti- mization problem with continuous relaxation. These methods optimize soft mask matrix for edges, and select the important nodes/edges by the threshold. However, they cannot guarantee that nodes and edges in the output subgraph are connected. Thus, their explanatory subgraphs cannot explicitly visualize the message passing paths. Besides, they consider the importance of each edge indepen- dently, and ignore the interactions among selected nodes and edges. Some recent works, such as SubgraphX (37] and Causal Screening [31], design the search criteria and use search- based methods solve the optimization problem. Due the combinatorial property of searching explanatory graph structures, it is difficult to design general hand-crafted search criterion. These criteria are limited on specific situations and thus not widely applicable.
To address these issues, we propose RG- RG-Explainer, which adopts reinforcement learning to explain GNNs' predictions. Our framework is inspired by classic combinatorial optimization solvers, which consists of three crucial steps: starting point selection, iterative graph generation and stopping criteria learning. These three components work logether generate an explanatory graph that interprets the predicted label of a given node/graph instance, as we elaborate next.
Firstly, starting point selection selects the most important node the seed node in the instance. If the task is to interpret the prediction of a specifie node label, then the most important node refers to the node itself. To explain graph label, we design seed locator to learn the node that influences the graph label the most. Iterative graph generation is the key module in our method, which generates the nodes in the explanatory graph sequentially Specifically, we add influential node (action) from the neighbors based on the current generated graph (state) at each step. It explicitly guarantees the connectivity of the generated graph. The generation process is controlled by the reward, i.e., the mutual information between the original predicted label and the label made by the generated graph. To ensure compact and meaningful explanatory graph, we also involve some constraints into the reward, such as size loss, radius penalty and similarity loss. Finally, stopping criteria are learned to further avoid generating very large explanatory graphs.
Furthermore, our method has better generalization ability and can be applied in both transductive and inductive setting. Different from the bearch-based methods, we learn the heuristies from the data automatically. A well-trained RG-Explainer can infer the explanations of instances which are not involved in the training phase.
We conduct extensive experiments on both synthetic and real-world datasets to show that the proposed RG-Explainer can achieve superior performance compared to state-of-the-ae GNN explainers. In particular, our visualization results further demonstrate the better intepretability of our method.
2
Related Work
Graph Neural Networks. Graph neural networks (GNNs) have achieved great success on graph- structured data in many real-world applications, including recommender systems, chemistry and bioin- formatics [12)) The majority of GNNs used today follow the message passing scheme [8]. which aggregate information from neighbors with different aggregation functions. like mean/max/LSTMM
pooling in GCN 13 and GraphSAGE [00, sum-pooling in GIN [3), attention mechanisms in GAT 28), etc. SGC 32 observes that the superior performance of GNNs is mainly due to the neighbor aggregation rather than feature transformation and nonlinearity, and proposed a simple and fast GNN model. APPNP [4] shares the similar idea by decoupling feature transformation and neighbor aggregation.
Graph Generation. There have been a variety of methods for graph generation. RVAE 20] is variational auto-encoder (VAE) based method with regularizer to ensure semantic validity. Normalizing flow based methods including GraphNVP [21], GraphAF 27 and GraphDF [8] utilize invertible neural networks to define mappings between latent variables and data points. Generative adversarial networks (GANs) 9 based methods like MoIGAN ( and GCPN 35 involve a generator and discriminator, where the generator is adversarially trained to fool the discriminator.

---

From the perspective of graph generation process, they can be classified into one-shot generation and iterative generation. RVAE and MolGAN directly generate adjacency matrices, while GraphAF. GraphDF and GCPN generate graphs by sequentially adding new nodes and edges. Though our proposed RG-Explainer is an iterative generation method, RG-Explainer different from the graph generation methods in that the above methods generate graph out of the air, while RG-Explainer needs to dynamically select suitable subgraphs to explain the predictions.
Graph Combinatorial Optimization with RL. With the success of deep reinforcement learning in games [22]. researchers have attempted to utilize RL techniques for the graph combinatorial optimization problems |6 19 39 225). Specifically, S2V-DQN [6] uses deep Q-learning with graph embedding to learn effective algorithms for the Minimum Vertex Cover, the Maximum Cut and the Traveling Salesman problems. A graph pointer network is proposed in [19] to solve the TSP efficiently. Further, Seal (39] learns heuristics to detect communities in the graph with policy gradient. Note that explaining GNNs is also combinatorial optimization problem. Thus, in this paper, propose a RL-based framework with three dedicated steps to generate explanations.
Post-hoc Analysis in Graph Neural Networks. By extending existing image/text explanation
techniques to the graph, some gradient-based methods (23 I are proposed to study the importance of nodes and edges in the graph. However, their performances have been proved to be sub-optimal (34 because they cannot incorporate the special properties of graphs.
GNNExplainer (3 is the first specific method proposed to explain trained GNNs. It defines the problem as an optimization task, which maximizes the mutual information between the predicted labels and the distribution of possible subgraphs under some constraints. Following the problem setting, PGExplainer [17] leverages the representations generated by the trained GNN and adopts deep neural network learn the crucial nodes/edges. These methods both utilize the continuous relaxation on edges, and add size and entropy constraints to make the explanation small and sparse. Specifically, they optimize soft mask matrix for edges, and select crucial nodes/edges by the threshold. However, they compute the importance of each edge independently, which may lead to disconnected explanatory graph with information redundancies. Our model sequentially adds important nodes from the neighbors of the current generated graph, which considers the information already involved in the current graph and ensures the connectivity.
SubgraphX [37] uses Monte Carlo tree search and Shapley value as a score function to find the best connected subgraphs explanations for GNNs. Causal Screening [31] is another search-based method, but it uses greedy search and causality measure to generate the explanations. Different from the search-based methods where heuristics heuristics from data, which can be widely applicable. Besides, our sarning-based method could train by a small of instances, and infer the explanations of many other similar unseen instances much faster than the search-based methods.
usually hand-crafted, our method uses RL to learn
Different from the instance-level explanation, there also exists the model-level explanation to in- vestigate general patterns for predictions. For example, XGNN (36] utilizes the graph generator to interpret GNNs at the model-level. In particular, the instance-level explainer interprets the prediction for a certain given instance while the model-level explainer is input-independent and less precise.
3 Preliminary
In this section, we first introduce the notations used and then give the formal problem definition.
Graph. Let G = E) denote the graph with node set V = fei D2 ..... uNn} and edge set E E VXV. Nodes in V could be associated with d-dimensional node features X' E N The graph G is described by the adjacency matrix A such that each entry Aij = if esj E E; 0, otherwise. Ā = A In denotes the adjacency matrix with added self-loops. A symmetrically normalized adjacency matrix with self-loops could be computed by D- 1/2 AD 1/2, where D is the diagonal degree matrix of A.
Given an input graph G and node features X, GNN model J(G, X') learns node representations. To fuse the information of both node features and graph topology in node
Message Passing.
3

---

Prediction R eguularization
MLP
Locator
Explandtory Graph
APPNP
Final reprosnttitinns
2, and genersted by rained model (+)
Generator
Seed Moda
STOP
Ro
Bolbu
Selected Node
Coordinate lbrotinn
Backward Ipadienttrowadd
Figure I: Illustration for explaining GNNs on graph classification. It contains two main components: locator and a generator. The locator selects seed node and feeds into the generator. Based on the seed node, the generator then generates complete explanatory graph and obtains the final reward from the environment. This reward is used as feedback to update the generator and the locator. We alternatively optimize the generator and locator until convergence.
representation vectors, GNN models utilize the message passing scheme to aggregate information from node neighbors. At each layer a node v aggregates all the messages in the ((-1)-th layer from all its neighbors to generate its embedding: h1 update (wee()) message(h, "1,-,,h,,,)), M,,"),
where (uv) is the neighbor set of node v. With layers, each node v generates embedding vector =, ho from the I.-hop neighborhood. In the node classification task, we train an classifier with 2, as input to predict the label for node v. In the graph classification task, we first use an aggregation function readout( 3) to generate the graph representation, which is further fed into classifier to predict the label.
Problem Definition. Given input graph G - EV, and trained GNN model f(-), GNN explainers aim to generate an explanatory subgraph S = (Vss Es), where Vss E V and Eg E E. The goal is to maximize the mutual information between the original label prediction Y = fG) and the label prediction distribution based on the generated explanatory subgraph. Formally, the objective can be given as maxş MI(Y, S) HYY HY)S)), where MI(-) the mutual information function and (-) is the entropy function. Since H(Y) is fixed in the explanation stage, the objective can be rewritten as ming S))
Methodology
The objective ming (Y)S) is intractable since there exponential candidates for S. It can be considered as combinatorial optimization problem, where we need to choose subset of nodes in the graph to optimize the objective. We explore how RL can be used to iteratively understand the representations produced by GNNs, and generate the explanatory subgraph optimizing the objective. Three proposed components will be described in the following.
4.1 Iterative Graph Generation (Graph Generator)
Given starting point Up. the graph generator used generate a connected subgraph S (Vo, U1 -.. } where we select one node in step and T is the total number of steps. Specifically, the 1-th step, we have the current partial solution S. {vo, vi ... ............. 1t-1). We next select
new node from the boundary 0S,-1 and expand the solution S. S U (vt). The state is defined the combined representation of both Up and S.-1. The action space the boundary OS,1 (v)),,,N( We further associate the solution with a reward value.

---

State. At the f-th step, we first augment each node feature vector by adding the information of the starting point and the current partial subgraph. For each node S or d I. we concatenate two values with its original feature vector Le:
x = Ie. 1l (ve(va))+ (veS X = [1.):0Es.
(I)
where is the indicator function and 1 (uES) 1 if v E S otherwise O. We concatenate the augmented node features and obtain the initial state representation X;.
Each node could further combine information from its current neighborhood. To achieve this, utilize some existing GNN methods, e.g., APPNP [14,, which separate the non-linear transformation and information propagation. These methods have shown be highly efficient and also effective. Specifically, we have the following update equation:
H (0) = 0, H((+1) =(1 (1- a)- aHH
where 1₁ is the trainable weight matrix, A the symmetrically adjacency matrix, and a a hyper- parameter used to control weight. After L-layer updates, we obtain the node representations Hf feed them into a MLP to improve the representation ability:
H.(w)= MIP(H, (v); 92), a USS
(3)
where O₂ is the learnable parameters in the MLP. At the t-th step, we only consider the nodes in S and - because other nodes do not influence the state and action space.
Action. Since the connectivity of the generated subgraph is required, we take as,- the action space at the t-th step. We utilize a softmax function to calculate the probability of taking an action E as,-1:
exp(0 H,(v)) (v) Eveas... exp(0g H(()))) EE 0S.
where 0g is the trainable parameter vector.
Objective. Following [17,, we use the cross-entropy function replace the conditional entropy function ming (Y)S) with given instances. We rewrite the objective as:
N C 35 co P(g((())) = =), Prediction Loss = N ==1
(5)
where S, is the explanatory subgraph for the n-th instance, C' is the number of possible predicted
labels, P(Y = c) is the probability that the original output of the trained GNN f is c, and P(f(S.) =
c) is the probability that the label prediction of f on the subgraph S, is
We further introduce some regularization terms to restrict the characteristics the explanatory subgraph. To obtain compact and succinet explanatory subgraph S, we define size loss and radius penalty, respectively. The size loss is used to limit the number of nodes in S while the radius penalty can compute the longest length of the shortest path from the seed node to other nodes in S. We also introduce a similarity loss that measures the similarity between the original node representation Zvo and the new representation generated on S. Formally, these loss function are defined as:
Size Loss = ||S]|
Radius Penalty
max Distance u), Similarity Loss = [|/AT(vo) (1(10o)22 Zuo ll2- w
(6)
The final objective is minimize
L(S) Prediction Loss + A Size Loss + X2 Radius Penalty + Xg Similarity Loss,
where X, are tlyee-paraaeteen to control the term importance.
Reward. We take the objective function loss L as the (negative) reward. However, the loss cannot be separated into each generation step. If we simply compute -(.)) the (-th step and regard it as the reward r, for the state-action pair (s,,a,) it could lead to the sub-optimal results. Therefore, we do not compute intermediate rewards when adding a new node to the subgraph. We only return the reward -L(S) when complete the generation process of S.
5

---

Optimization with policy gradient. We learn the graph generator G = {01, 22 03} via policy gradient. The policy Ti learned to maximize Es ro--G- C(S), whose policy gradient
ve = wrlonn
V log To (((,-)-)
(8)
Here, So is the given seed up and Q(St- vx)= = Eu wr. ur --l.ssissss-- [(5) the state-action value function. Specifically, use the Monte-Carle estimation to approximate Q values:
1 ΣE
i1 -
when << T when t=
(()
M
C(S Uv)
where ( 1,.....M are rollouts (i.e., complete explanatory graphs) sampled from the policy given the partial solution S and Ur. In this way, we can distribute reward signals at all steps.
4.2 Stopping Criteria Learning
We further learn the stopping criteria to judge the goodness of the current generated graph. We add special STOP action into the action space to learn node selection and stopping criteria simultaneously. Since we have already obtained the node representation H, in the current state, the STOP action could aggregate the representations with self-attention mechanism:
exp(0] (l((w)
(v))) Enc(S exp (u))
H.TPP)
Σ (v) (10)
(E 1888,
where the parameter 04 helps to learn the attention 7e(v) for each node v in the current state.
After having (STOP)), we could put into Eqn. and compute a, (STOP) and ( together. In practice, we also set maximum number of generation steps to avoid generating very large subgraphs.
4.3 Starting Point Selection (Seed Locator)
For node classification tasks, the starting point is the node instance whose predicted label needs to be interpreted. However, the starting point is difficult select for graph instance. To solve the problem, we need to construct seed locator IL to first identify the most influential node in the graph and then generate the explanatory subgraph from that node.
Given graph instances In. the objective in Eqn. coull rewritten with the locator L:
P(S(g.) log
log (L)((((())) c),
(11)
12
where both the generator G and the locator L are to be learned. The regularization terms in Eqn. can be further added to the objective for more constraints. We train G and L coordinately. i.e. we fix the parameters in one module and train the other module optimize the objective in Eqn. 11 iteratively.
When we fix L, the way to train G the same as described in Sec. 4.1 Here we introduce how to construct IL when G is fixed. Based on G, we can generate subgraph S for each node in the graph instance and compute the corresponding reward L(S). A straightforward way is to enumerate over all the nodes and select the node with the highest reward. However, such brute-force method is computationally infeasible when we have many graph instances. Therefore, we adopt lcarning-baat based method. Specifically, we use three-layer MLP model the influence of node Vinn the label of the graph instance Gn.
Wi,n MLP([Zg... Ze,,,.),
(12)
where Zgn, and Ze.-, are the final representations the graph instance In and the node U generated by the trained model f(-). respectively. Because the goal of
return the node vg,, with highest win for graph In. we utilize the Kullback-Leible divergence loss, KLDivLoss (ws,sss,,,,..> GG (GG(,,,)) (v,,.) ()))) which aims to make the distribution between estimated values wi,. and the actual reward of explana- tory subgraph produced by the current generator close. The softmax layers are used to transform win and - L (v).)) into two distributions over the nodes fi,. graph In- We sample graph instances to train the MLP, and let L Jearn what kind of seed nodes has the highest reward to minimize Eqn

---

4.4 Pre-training
In this section, we show the pre-training strategies with Maximum Log-Likelihoon Estimation (MLE) that can be used to initialize the generator G and the locator L, respectively.
Pretrain G. The generator produces an unordered set S but in ordered sequence. We maximize over all possible generated orderings for an explanatory graph [29]:
max
log (oriil "r()),. (o(e-1))),
(13)
where t is any valid permutation given S. Here, the validity means that each (7(() should be in the boundary of (Vo, (r((). -.. (r(
Considering there
most T! orderings in the worst case,
bootstrapped way with
set2set [29] to approximate Eqn. 13 Specifically, we optimize Eqn. [3 by maximizing the following
set-wise log-likelihood instead:
log (( (uo, ".
(14)
where (1) = arg max G(1 (1) (r-(i-)))) Here we utilize the 3-hop neighborhood of seed nodes the initial explanations S (i.e., pre-training samples). After constructing the samples, we train G to maximize the set-wise log-likelihood in Eqn. Vinyals et al. [29] also pointed out naively optimize it, the model would pick a random ordering and get stuck on it. Thus, a list-wise log-likelihood is also necessary to explore the space of ordering. For each pretrain sample S, we choose valid permutation 7' with random lengths in advance, and optimize the list-wise MLEE
ΣL log G (z)(()) ( (r)( (;(-))))))
Pretrain L. We pretrain the locator L without the generator G. Similar as in G, we utilize the 3-hop neighborhood of node as the initial explanatory subgraph S. We randomly sample some nodes in the graph instances and compute the rewards of their 3-hop neighborhoods. These samples are used to pretrain the parameters in L.
Experiments
In this section, we first introduce experimental setup. Then we compare RG-Explainer with two state-of-the-art baselines GNNExplainer [34] and PGExplainer [17] both qualitative and quantitative evaluations. Further, we evaluate the performance of our method in the inductive setting. Due to the space limitation, we move the pseudocode, implementation details and ablation study to the supplementary materials. We also attach our codes in the supplementary materials.
5.1 Setup
For fairness, we follow the experimental setup in [7 [7.22 [2]. i.c., the same datasets, trained GNN model and evaluation metrics. Besides, we also utilize the same fine-tuned parameters in [2 for our competitors, GNNExplainer and PGExplainer.
Datasets. We use six datasets, in which four synthetic datasets (BA-shapes, BA-Community, Tree- Cycles and Tree-Grid) are used for the node classification task and two datasets (BA-2motifs and Mutagenicity) are used for the graph classificition task. These datasets bases. The motif a small but important substructure in a graph, which has been shown to play a crucial role in predicting the label of node/graph instances [ 15 [6]. The base is the remaining part of a graph which randomly generated. Motifs are taken as the ground-trun and the goal of explainers is to find them. Details of these datasets described as follows.
composed of motifs and
(a) The BA- BA-shapes dataset consists of one Barabasi-Albert([B graph (2 as the base and 80 house- structure motifs. Each motif is randomly attached to node in BA graph and extra edges are added as noises. (b) The BA-community dataset comprised of two BA-shapes with different node features generated by Gaussian distributions. The extra edges are also added to connect two BA-shapes. (c)
7

---

Table Visualization (Qualitative Evaluation)
Node Classification
Graph Classifictionn
BA Stupes
BA Community
Tree Cycles
Tree Frid-Grid
BA 2motiss
MUTAG
Explanations GNN- Explainer
Explanations PG- Explainer
Explanations by RG- Explainer (ours)
Ground- Truth Moiff
The Tree-cycles dataset includes a multi-level binary tree as the base and 80 six-node cycle motifs. The cycle motifs are randomly attached the tree. (d) The Tree-grid dataset is similar Tree-cycles, which uses the 3 x grid motifs instead. (e) The BA-motifs dataset has 1000 graphs where half of them are BA graph attached with house-structure motif, while the are BA graph attached with a five-node cycle motif. (f) The Mutagenicity dataset is real dataset, which includes 4337 molecule graphs. They can be classified as mutagenic or nonmutagenic depending on whether having N NH or NO2 motifs.
Model. We use the trained GNN model in 12 whose architecture is given in 34 Specifi- cally, the model that consists of three consecutive Graph Convolution layers connected with fully connected layer is used for node classification. For graph classification, the model includes three consecutive Graph Convolution layers fed into two max and mean pooling layers, respectively. The two pooling layer output embeddings are then concatenated to generate the input for fully connected layer for graph classification.
Metrics. The motifs in each dataset are the ground-truth explanations. The edges in the motif positive and other edges negative. GNNExplainer and PGExplainer return mask matrix to represent the importance of each edge in the instance. Our method generates a subgraph. Based the generation order of edges, we could also assign different weights edges. Therefore, the explanation problem can be formalized as a binary classification task, where edges in the ground-truth motif taken prediction labels and the weights of edges viewed as prediction scores. With the explanatory subgraph provided by explainers, the AUC score can be computed to measure the accuracy for quantitative evaluation.
5.2 Qualitative evaluation
Table [ visualizes some examples of explanatory graphs on all the datasets. For node classification, we amplify the center node instance and generate the subgraph from it. For graph classification, the graph represents the whole graph instance. We use different colors to denote node labels.
Intuitively, superior explainer should include more edges in the ground-truth motif and less irrelevant nodes and edges in the explanatory subgraph. To show whether explainers assign larger weights to edges in the motif, use the bold black edges represent the top-k edges, where &t is the number of edges inside the ground-trui truth motif.
For easy cases, all the methods could find the ground-truth motif. Thus, we choose some difficult instances to show advantages of our method. From the table, we see that all the three methods generate subgraphs that contain the ground-truth "house" motif both BA-Shapes and BA-

---

Table 2: Explanation AUC (Quantitative Evaluation).
Node Classification
Graph Classification MUTAG
BA-Shapes
BA-Community
Tree-Cycles
Tree-Grid
BA-2motifs
GiNNExplainer
0.742 + 0.006
0.708 + 0.004
0.540 + 0.017
0.714 0.002
0.499 0.004
0.606 + 0.003
PGExplainer
0.999 + 0.000
0.825 = 0.040
0.760 - 0.014
0.679 + 0.008
0.133 +: 0.046
0.847 : 0.081
RG-Explainer (ours) Improve
0.985 0.013
0.919 0.017
0.787 0.099
0.927 0.031
0.657 +: 0.107
0.873 + 0.028
-1.5%
11.4%
3.6%
29.8%
31.7%
2.8%
BA Communkyy
Tree-Grid
MUTAG
0.05
0.05
0.9
sople
0.8
0.85
0.75
0.8
NUC
0.7
0.75
0.8
0.7
0.65
23p-capl ner (nouctiv))
(SG-0opla oar Unouctivl
0.65
(G--2-00 ner (novetie)
0.6
RG- up sinee (Tonecacciv)
0.5
RG-Feehhiie (Trneetcciv))
0.8
RGT qu-iiee (Tnreccecio)
Pido of Training Instances
Padoo Training Instances
Redoo Training Instances
Figure 2: Comparison between RG-Explainer and PGExplainer in the inductive setting.
Community datasets. However, both GNNExplainer and PGExplainer include many irrelevant nodes and edges, while our method adopts the stopping criteria to generate more concise subgraphs. On both Tree-Cycles and Tree-Grid datasets, since we select the connection node between the base and the motif as the node instance, it is hard to identify the ground-trut toound-truth motif (cycle grid) exactly. This is because the explanatory subgraphs could easily include the base. Compared with competitors, method can generate the explanatory subgraphs that contain the complete ground-truth motifs, i.e,, edges in the motifs are all marked as black.
For graph classification, explainers should identify the ground-truth motif that decides the label of graph instances. For the instance in BA-2motifs, the ground-truth "house" motif is located at the right bottom. Both GNNExplainer and PGExplainer involve accurate and wrong edges in the explanations, while our method only adds edges in the ground-truth "house" motif to the generated subgraph. For the MUTAG dataset, both PGExplainer and method identify the correct motif. In particular, our method correctly locates the O atom and obtains the ground-truie motif NO2.
5.3 Quantitative evaluation
We next show the quantitative results in Table For each method, we compute the average AUC scores and standard deviations over 10 runs. Note that the AUC scores reported here are a bit different from that in the original papers due to the unstable convergences [12..
From the table. we see that our method RG- RG-Explainer achieves the best results on 5 out of datasets. For example, the AUC score of RG- EGGElllainer on Tree-Grid is 0.927 while that of the runner-up only 0.714, leading to an improvement of 29.8%. On the BA-Shapes dataset, RG-Explainer achieves comparable results with the winner's s and significantly outperforms GNNExplainer. These results show the advantage of applying reinforcement learning techniques in constructing explanatory subgraphs. Further, since the constructed subgraphs are connected, they could better characterize motifs the graph. Note that in the graph classification task, our method uses a locator to first select the seed nodes. We also test the performance of the locator and find that the locator selects 66% and ~ 84% accurate seed nodes (i.e., nodes in the ground-trume -tuth motif) for BA-2Motifs and MUTAG, respectively. This further explains the good performance of RG- EG-Explainer for graph classification.
5.4 Inductive setting
We further test the performance of RG-Explainer in the inductive setting. We compare with PGExplainer, which are both learning- methods. Specifically, we vary the training set sizes from (10%, 30%, 50%, 70%, 90%) and take the remaining instances for testing. For each dataset, we run the experiments 10 times and compute the average AUC scores.

---

Due to the limited space, Only shows the results on BA-Community. Tree-Grid and MUTAG datasets. For other datasets, see the supplementary material. The figure also includes the results of both methods in the transductive setting (i.e., use all the instances) for reference. From the figure, RG-Explainer generally outperforms PGExplainer as the training set size increases. For example, with only 10% training instances in the Tree- dataset, RG-Explainer significantly outperforms PGExplainer by large margin. This shows that RG-Explainer generalizes better than PGExplainer.
Conclusion
We present RG-Explainer to generate the instance-level explanations for GNNs in this paper. The RL-based generator is proposed to ensure the message passing nature of GNNs. Besides, we design the seed locator and stopping criteria to find the most influential node in graph instance and check whether the generated explanatory graph is good enough, respectively. Though our method increases the transparency of GNN predictions, may put GNN models at a high risk of being attacked. How to utilize the GNN explanations to make GNN models more robust is a future research direction.
References
[1] F. Baldassarre and H. Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: /905. 00055/3666, 13686, 2019.
[2] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. science, 286(5439):509-51) 1999.
[3] D. Barrett, F. Hill, A. Santoro, A. Morcos, and T. Lillicrap. Measuring abstract reasoning in neural networks. In ICML, pages 511-520. PMLR, 2018.
[4] P. W. Battaglia, R. Pascanu, M. Lai, D. Rezende, and K. Kavukcuoglu. Interaction networks for learning about objects, relations and physics. arXiv preprint
2016.
[5] A. R. Benson, D. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 353(6295):163-11 166, 2016.
[6] H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In NeurIPS, pages 6348-6358, 2017.
[7] N. De Cao and T. Kipf. Molgan: An implicit generative model for small molecular graphs arXiv preprini arXiv: 1973, 2018.
[8] J. Gilmer, S. S. Schoenbolz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In JCML, pages 1272-1272, 2017.
[9] I. Goodfellow, J. Plouget-Abadic M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In NeurlPS, pages 2672-2666662 2772,2680,20 2014.
[10] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In NeurlPS, pages 1024-1034, 2017.
[11] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. SIGIR, pages 639-648, 2020.
[12] L. Holdijk, M. Boon. S. Henckens, and de Jong. [re] parameterized explainer for graph neural network. In ML Reproducibility Challenge 2020, 2021.
[13] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks.
In ICLR, 2017.
[14] Klicpera, A. Bojehevski, and S. Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
[15] A. S. Konagurthu and A. M. Lesk. On the origin of distribution patterns of motifs in biological networks. BMC Systems Biology, 2(1):1-8, 2008
[16] X. Li, R. Cheng, K. C.-C. Chang, C. Shan, C. Ma, and H. Cao. On analyzing graphs with motif- paths. Proceedings of the VLDB Endowment, 1466):111--112; 2021.
[17) D. Luo, W. Cheng, Xu, W. Yu, B. Zong, H. Chen, and X. Zhang. Parameterized explainer for graph neural network. In NeurIPS, 2020.
10

---

[18] Y. Luo, K. Yan, and S. Ji. Graphdf: A discrete flow model for molecular graph generation. In ICML, 2021.
[19] Q. Ma, S. Ge, D. He, D. Thaker, and I. Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv: 1911.009366 2019.
[20] T. Ma, J. Chen, and C. Xiao. Constrained generation of semantically valid graphs via regularizing variational autoencoders. In NeurlPS, 2018.
[21] K. Madhawa, K. Ishiguro, K. Nakago, and M. Abe. Graphnvp: An invertible flow model for generating molecular graphs. arXiv preprint DrXiv:1905. 1600, 2019.
[22] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep rein- forcement learning. nature, 518(7540):529-33) 2015.
[23] P. E. Pope. S. Kolouri, M. Rostami, C. E. Martin, and H. Hoffmann. Explainability methods for graph convolutional neural networks. In CVPR, pages 10772-10781, 2019.
[24] D. Saxton, E. Grefenstete, Hill, and P. Kohli. Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv: /904.0/557, 2019.
[25] C. Shan, N. Mamoulis, R. Cheng, G. Li, X. Li, and Y. Qian. An end-to-end deep rl framework for task arrangement in crowdsourcing platforms. In ICDE, pages 49-60 IEEE, 2020.
[26] Y. Shen, Y. Wu, Y. Zhang, C. Shan, J. Zhang, K. B. Letaief, and D. Li. How powerful is graph convolution for recommendation? CIKM, 2021.
[27] C. Shi, M. Xu, Z. Zhu, W. Zhang, M. Zhang, and J. Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. In ICLR, 2020.
[28] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. In ICLR, 2018.
[29] O. Vinyals, S. Bengio, and M. Kudlur. Order matters: Sequence to sequence for sets. ICLR, 2015.
[30] M. N. Vu and M. T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In NeurIPS, 2020.
[31] X. Wang, Y. Wu, A. Zhang, X. He, and T. seng Chua. Causal screening to interpret graph neural networks, 2021.
[32] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In ICML, pages 6861-6871. PMLR, 2019.
[33] K. Xu, Hu, Leskovec, and Jegelka. How powerful are graph neural networks? In ICLR, 2018.
[34] R. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec. Gnnexplainer: Generating explana- tions for graph neural networks. In NeurIPS, pages 9240-92511 2019.
[35] J. You, B. Liu, R. Ying, V. Pande, and J. Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. arXiv preprint arxiv:/806.02447. 2018.
[36] H. Yuan, J. Tang, X. Hu, and S. Ji. Xgnn: Towards model-level explanations of graph neural
networks. In KDD, pages 430-438, 2020.
[37] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji. On explainability of graph neural networks via subgraph explorations. ICML, 2021.
[38] M. Zhang and Y. Chen. Link prediction based graph neural networks. In NeurlPS, pages 5165-5175, 2018
[39] Y. Zhang, Y. Xiong, Y. Ye, T. Liu, W. Wang, Y. Zhu, and Yu. Seal: Learning heuristics for community detection with generative adversarial networks. In KDD, pages 1103-1113, 2020.
11


Reviews:
[{"review_id": "ssqUy6QCC5A", "reviewer": "Reviewer_GKcV", "summary": "This paper studied the explanation for GNNs. The authors formulated the task of generating an exploratory sub-graph as a combinatorial optimization problem, and proposed a framework, RG-Explainer, to solve the problem via reinforcement learning. \n\nThe RG-Explainer framework consists of three parts: a seed locator for starting node selection, a graph generator for generating the explanatory sub-graph, and a learned stopping criteria to avoid generating very large explanatory graphs. \n\nThe authors conducted experiments on node classification and graph classification tasks.  The qualitative results showed that the proposed method could provide plausible explanations. The quantitative results showed that the proposed method has better accuracy, and outperforms the baseline in both inductive and transductive settings.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The proposed framework is novel in terms of GNN explanatory. The authors introduced RL-based learning schema for the explanatory sub-graph generation.  \n\nQuality: The proposed framework is reasonable. My main concerns are about the experiment results. \n1)\tIt seems that the authors did not implement the baselines based on the officially released code (e.g., https://github.com/flyingdoog/PGExplainer for [16]), but the reproduction challenge ([11]), which reports much lower results compared to the original paper.  A proper justification will be appreciated. \n2)\tMore ablation studies are necessary to clarify the contribution of different components (e.g., the different components in Eq. (7), and the pre-training part).\n3)\tWhether this RL-based framework requires longer training / inference time?The efficiency analysis, as discussed in existing works [16, 34], would be good to be included. \n\nClarity: Overall, this paper is written clearly, except that Figure 1 is a bit confusing. In particular, \n1)\tDoes the locator receive the reward from the environment? \n2)\tIn the graph generator, should the reward arrows within the episode be removed, as the reward is assigned episodically? \n3)\tWhat is the meaning of the “right” ticks? \n\nSignificance: The significance is moderate. Although RL has been extensively studied in solving combinatorial optimization problems (e.g., the routing problems), this paper provides a new direction for RL application.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations have been discussed before, and there's no obvious negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "D0w1jnb4JX5", "reviewer": "Reviewer_MN97", "summary": "This paper proposes an RL-based GNN explainer to address the neglected interactions among nodes and edges in the generated subgraph for model interpretation in the existing works. Specifically, the subgraph generation process is modeled as a Markov decision process (MDP) where the state is the currently selected node, action space is composed by the candidate neighboring nodes, and reward signal is the combinatorial loss to encourage the RL learner to generate a compact and succinct subgraph. In this way, the subgraph generation process strictly follows the structure of the original graph and therefore considers the interactions among nodes and edges.", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\n1. In general, this paper is well-written and easy to follow.\n2. The proposed model is technically sound. Specifically, the definition of MDP seems reasonable, the reward signal is properly designed and well-motivated and the sparse reward signal problem is addressed properly with Monte-Carlo estimation. In addition, stopping criteria are designed to avoid large subgraphs with a maximum number of generation steps; and the starting point selection with the learning-based approach is designed to address graph classification scenarios efficiently.\n3. The qualitative evaluation and quantitative results show the superior outcome comparing with state-of-the-art approaches.\n\nWeaknesses:\n1. Policy gradient and Monte-Carlo estimation may suffer from high variances and could be unstable, which may not be able to generate explanation consistently. Monte-Carlo estimation could also be inefficient. More analysis on rollout reward evolution with respect to the training timestamps may help.\n2. Line 200 \"In this way, we can solve the sparse reward problem and also distribute reward signals at all steps.\" The sparse reward is a very challenging problem. I understand that Monte-Carlo estimation could help since it gives a reward to each step. However, Monte-Carlo estimation suffers from high variance, which could slow down the convergence. To my knowledge, this is far from \"solve \" sparse rewards. A term like \"alleviate\" could be more appropriate. I would also expect more discussion of why Valina Policy Gradient and Monte-Carlo estimation are adopted here, why they can tackle the sparse reward, and why not using other RL algorithms that could be more stable and may generate more consistent explanations, like DQN or A2C.\n3.More justification of leveraging the self-attention mechanism to generate stop signal is needed as it seems a bit arbitrary to directly incorporate the \\tilde{H}_t(STOP) into action space. In addition, the author mentioned that a maximum number of generation steps is still needed to avoid generating large subgraphs. It is unclear whether the self-attention mechanism is effective. Ablation studies with respect to the sizes of the generated graph without maximum generation steps would be helpful.\n\n-------------------------------- Post rebuttal --------------------------------\n\nThe authors' response has addressed my concerns. The score is raised.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1O62TY9OyuB", "reviewer": "Reviewer_gLix", "summary": "This paper proposes an RL-enhanced GNN explainer, RG-Explainer which could construct a connected explanatory subgraph by sequentially adding nodes from the boundary of the current generated graph, and can be used for inductive setting. Experiments on both synthetic and real datasets are carried out to compare the proposed algorithm with existing  GNN explainers. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The reviewer finds this manuscript well-written and the performance of the algorithm impressive. The reviewer believes such a framework could be useful for understanding and explain the performance of GNNs.\n\nOne major question is regarding the complex convergence of the algorithm. Due to the introduction of the RL framework, which leads to high training complexity, and the policy gradient may not necessarily converge. However, no analysis or experiments were provided regarding this issue. More discussion with respect to the convergence of the framework is needed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, but the discussion of societal impact is not in the main text but in the supplementary document.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the issue of explainability in GNNs using RL for finding explanatory subgraphs. The authors provided an extensive rebuttal including new experimental results requested by the reviewers. The AC believes the authors' responses address in a satisfactory manner the reviewers' comments and recommends acceptance.
Decision: Accept (Poster)