DAG Matters! GFlowNets Enhanced Explainer for Graph Neural Networks
Authors: Wenqian Li
Yinchuan Li
Zhigang Li
Jianye HAO
Yan Pang
Venue: ICLR 2023 poster (2023)
Keywords: GNN
Interpretability

Abstract: Uncovering rationales behind predictions of graph neural networks (GNNs) has received increasing attention over the years. Existing literature mainly focus on selecting a subgraph, through combinatorial optimization, to provide faithful explanations. However, the exponential size of candidate subgraphs limits the applicability of state-of-the-art methods to large-scale GNNs. We enhance on this through a different approach: by proposing a generative structure – GFlowNets-based GNN Explainer (GFlowExplainer), we turn the optimization problem into a step-by-step generative problem. Our GFlowExplainer aims to learn a policy that generates a distribution of subgraphs for which the probability of a subgraph is proportional to its’ reward. The proposed approach eliminates the influence of node sequence and thus does not need any pre-training strategies. We also propose a new cut vertex matrix to efficiently explore parent states for GFlowNets structure, thus making our approach applicable in a large-scale setting. We conduct extensive experiments on both synthetic and real datasets, and both qualitative and quantitative results show the superiority of our GFlowExplainer.

Published as a conference paper at ICLR 2023
DAG MATTERS! GFLOWNETS ENHANCED Ex- PLAINER FOR GRAPH NEURAL NETWORKS
Wenqian Li Yinchuan Li Zhigang Jianye Hao?:3, Yan Pang
National University of Singapore, Singapore
Huuawei Noah's 's Ark Lab, Beijing, China
Tianjin University, Tianjin, China
Wenqiandu. nus edu, (liyinchuan, haojianye scs.lzgêt ju. edu. cn, jamespanggnus edu.sg sg
jeaeeeeeeeeeeeeeeeeeeeeeeeeeee wwwwawei....ooommoomo com com
ABSTRACT
Uncovering rationales behind predictions of graph neural networks (GNNs) has received increasing attention over the years. Existing literature mainly focus on selecting a subgraph, through combinatorial optimization, to provide faithful ex- planations. However, the exponential size of candidate subgraphs limits the ap- plicability of state-of-the-ar methods to large-scale GNNs. We enhance on this through different approach: by proposing generative structure GFlowNets- based GNN Explainer (GFlowExplainer)) we turn the optimization problem into step-by-step generative problem. Our GFlowExplainer aims learn a policy that generates distribution of subgraphs for which the probability of subgraph is proportional to its' reward. The proposed approach eliminates the influence of node sequence and thus does not need any pre-training strategies. We also propose new cut vertex matrix to efficiently explore parent states for GFlowNets struc- ture, thus making our approach applicable in large-scale setting. We conduct extensive experiments on both synthetic and real datasets, and both qualitative and quantitative results show the superiority of our GFlowFxplainer.
INTRODUCTION
Graph Neural Networks (GNNs) have received widespread attention due to the springing up of graph-structured data in real-world applications, such social networks and chemical molecules Zhang et al. (2020). Various graph related task are widely studied including node classi- fication Ceatifn Henaff al. (2015); uncovering rationales behind predictions of graph neural networks (GNNs) is relatively less ex- plored. Recently, some explanation approaches for GNNs have gradually stepped into the public eye. There are two major branches of them: instance-level explanations and model-level explana- tions Yuan et (0022). In this paper, we mainly focus on instance-level explanations.
al. (2020) and graph classification Zhang et al. (2018). However,
Instance-level approaches explain models by identifying the most critical input features for their predictions. They have four sub-branches: GradientssFeattree--ban Zhou et al. (2016); Baldassrree
& Azizpour (2019); Pope al. (2019), Perturbation-baset YYng et al. (2019); Luo et al. (2020);
Schlichtkrull et al. (2020); Wang et al. (2020). Decompose- based Baldassarre & Azizpour 2019
Schnake et al. Feng et al. 2021 and Surrogate- Vu & Thai (2020); Huang al. 2022
Yuan et al. (2022). Some works such as XGNN Yuan et al. (2020) and RGExplainer (Shan et al. (2021) apply reinforcement learning (RL) to model-level and instance-level explanations. However, the pioneering works have some drawbacks. Perturbation-basc
approaches return the discrete edges for explanations, which are not as intuitive as graph generation-baue approach, which could provide connected graphs. However, the task of searching connected subgraphs is a combinatorial problem, and the potential candidates increase exponentially, making most current approaches inefficient and
Equal Contribution
Corresponding Author: Yan Pang
This is the joint work between National University of Singapore and Huawei Noah's 's Ark Lab.
This work was completed while Wenqian Li member of the Huawei Noah's Ark Lab for advanced study.

---

Published as a conference paper at ICLR 2023
intractable in large-scale settings. In addition, current research consider Monte-Carle tree search, which has high variance and ignores the fact that graph is an unordered set. This could lead to a loss of sampling efficiency and effectiveness, i.e., the approaches fail to consolidate information of sampled trajectories that form the same subgraph with different sequences.
To address the above issues, take advantage of the strong generation property of Generative Flow Networks (etlowNets) Bengio et al.] (2021b) and cast the combinatorial optimization problem as a generation problem. Unlike the previous work, which focus on the maximization of mutual information, our insight is to learn a generative policy that generates a distribution of connected subgraphs with probabilities proportional to their mutual information. We called this approach which could overcome the current predicament for the following reasons. First, it has stronger exploration ability due to its flow matching condition, helping us to avoid the trap of suboptimal solutions. Second, in contrast to previous tree search or node sequence modeling, GFlowExplainer consolidate information from sampled trajectories generating the same subgraph with different sequences. This critical difference could largely increase the utilization of generated samples, and hence improve the performance. Moreover, by introducing a cut vertex matrix, GFlow- Explainer could be applied in large-scale settings and achieve better performance with fewer training epochs. We summarize the main contributions as follows.
GF SrlowExplainee
Main Contributions: 1) We propose new hand-crafted method for GNN explanation via GFlowNet frameworks to sample from a target distribution with the energy proportional to the predefined score function; 2) We take advantage of the DAG structure in GFlowNets to connect the trajectories of outputting the same graph but different node sequences. Therefore, without any pre-training strategies, we can significantly improve the effectiveness of our GNN explanations; 3) Considering relatively cumbersome valid parent state explorations in GFlowNets because of the con- nectivity constraint of the graph, we introduce the concept of cut vertex and propose a more efficient cut vertex criteria for dynamic graphs, thus speeding up the whole process: 4) We conduct extensive experiments to show that GFlowExplainer can outperform current state-of-the-an approaches.
2 RELATED WORK
Graph neural networks (GNNs) are developing rapidly in recent years and have been adopted to leverage the structure and properties of graphs SScarelli et al. (2008); Lanchez-Lengeling et al. (202I). Most GNN variants can be summarized with the message passing scheme, which is composed of pattern extraction and interaction modeling within each Gilmer jet al. (017). These approaches aggregate the information from neighbors with different functions, such as 2017), sum-pooling in GIN Xu et al. (2018), attention mechanisms in GAT Velickovic et al. (2017). SGC et al. (2019) 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 Kliepera et al. (2018) shares the similar idea by decoupling feature transformation and neighbor aggregation.
Graph Neural Networks:
in GCN Welling & Kipf (2016), GrpahS AGE |Hamilton et al.
Generative Flow Networks: Generative flow networks Bengio al. (2021 b) aim train gen- erative policies that could sample compositional objects x E DD by discrete action sequences with probability proportional a given reward function. This network could sample trajectories accord- ing to a distribution proportional to the rewards, and this feature becomes particularly important when exploration is important. The approach also differs from RL, which aims maximize the expected return and only generates single sequence of actions with the highest reward. GFlowNets has been applied in molecule generation Bengio al. (202 la Jain et al. (002). discrete probabilis- tic modeling Zhang et al. (2022), bayesian structure learning Deleu et al. (022). causal discovery Li et al. 2022) and continuous control tasks Li et al. (2023).
Instance-level approaches explain models by identifying the approaches, e.g., Zhou et al. (2016); Baldassarre & Azizpour (2019): Pope et al. (2019), compute the gradients or map the features to the input to explain the important terms while the scores sometimes could not reflect approaches, GNNExplainer Ying et al. (2019) is the first specific design for explanation of GNNs, which formulates an optimization task to maximize the mutual information between the GNN predictions and the distribution of poten-
Instance-level GNN Explanation:
most critical input features for their predictions. Gradients/Features-bon
the contributions intuitively. As for the perturbation-baut
2

---

Published as a conference paper at ICLR 2023
tial subgraphs. Unfortunately, GNNExplainer and Causal Screening Wang al. (2020) may lack a global view of explanations and be stuck at local optima. Even though PGExplainer Luo et al. (020)) and GraphMask (Schlichtkrull et al. (2020) could provide some global insights, they require a reparameterization trick and could not guarantee that the outputs of the subgraph are connected, which lacks explanations for the message passing scheme in GNNs. Shapley-value based approaches SubgraphX Yuan et al. (2021) and GraphSVX Duval & Malliaros (2021) are computationally ex- pensive especially for exploring different subgraphs with the MCTS algorithm. Decomposed- approaches, for example, L Baldassarre & Azizpour (201)) GNN-LRPPSchnake et al. (2020) and Feng et al. (202T), evaluate the importance of input features by decomposing the model predictions into several terms, at the price of raising the difficulty of applying the method to com- plex and structured graph datasets. Surrogate-based approaches PGMExplainer Vu & Thai (2020) and GraphL.ime |Huang et al. (2022) sample data set from the neighbors of a given example and then fit an interpretable model for that data set. However, this approach requires a careful definition of neighboring areas, making the generalization to other problem settings highly non-trivial. As an another attempt, XGNN Yuan et al.] (2020) and RGExplainer [Shan et al.] (202T) apply reinforce- ment learning model-level and instance-level explanations respectively, while the latter requires inefficient pre-training strategies and has high variances for sampling.
3 GFILOWEXPLAINER
3.1 PROBLEM FORMULATION
Let G = EV,E) denote a graph on nodes and edges & with d-dimensional node features X' {II,..., InJ, r; E Rdd The adjacency matrix A describes the edge relationships of G, i.e. Aa for all i E V and Aij = 1 for all (1t, E E. Á is the symmetrical adjacency matrix computed by Å = 1-112220 AD-1/2 where D is the diagonal degree matrix of A. Let & denote a trained GNN model, which is optimized on all instances in the training set and is then used for predictions. Given an instance, i.e. a node v or graph G, the goal of GNN Explanation is identify a subgraph G. = (V., E,) and the associated features X, { E G.} that are important for the GNN prediction Y (bu))) or y, = (G,) where di is graph instance. The previous works formulate this task as an optimization problem and the objective is to maximize the mutual information
max MaX. H(Y) HYYG..) = min H(Y G,
G,
where MT(-) is the mutual information function, H(-) is the entropy function, ÿ is the prediction of & with G2 as the input and H (Y G.)) -E,,,, [log Ps (Y (Y).. Since H (Y) fixed in the expla- nation state, the objective can be rewritten as ming, H HY|) which is to minimize the uncertainty of & when the GNN computation is limited to G..
From the graph generation perspective, since there are exponential candidates for explaining for ÿ. it is not trivial to direct solve such combinatorial optimization problem. Thus we turn this optimization problem into by-p-b generative problem (see Figure I]. We propose our generative structure as GFlowNettsbbased GNN Explainer, abbreviated as GF Meloxpplaaiee (S, A) where S is finite set of states, and A is the action set consisting transitions a; : 8, + 81+1- The insight comes from that we could consider G, as a compositional object. Starting from an empty graph, we can train our policy network to generate such G, by sequentially adding one neighbor node at each step to ensure the connectivity of an explanation graph, in which G (s())) refers to subgraph at state 8t, and adding one node refers to an action a; making a state transition 8, -> 81+1- Different from traditional optimization problems maxmizing the mutual information our objective is to construct a TD-like flow matching condition, to obtain a generative forward policy πt T[ae so that P(Y G.) r(Y, G.), where rYY, is predefined reward function based on MI(Y, G.).
which consists of tuple
The rest of the section is organised as follows: we first introduce the flow modeling of GFlowNets in Section 3.2 The crucial elements of GFlowExplainer structure are defined in Sections 3 and
3.4 We propose a new framework to address the connectivity problem for an effective exploration
of parent states in GFlowExplainer in 3.5
3

---

Published as a conference paper at ICLR 2023
Valid parents 4
Update
Policy Network
P(S, 8:
Pollcy Network
F(4r11 -))
x(o
20
Policy Network
91
Score
r(sy)
8p-1
Function
Figure 1: Structure of GFlow Explainer: Sampling from a starting node vo (pink), for each state St, the combined features of subgraph (pink and black) and neighbor nodes (orange) are fed into the policy network to sample an allowed action a, : {22}** vertices updated based on 8t+1 to find valid parents Sp for calculating inflows F(Sp + 8141). Either outflows F($++1 + S.) or reward r(sy) is calculated based on the stopping criteria.
T(a 8t) and obtain St41- Then cut
3.2 FLOW MODELING
Following Bengio et al. 2021b). Consider a direct acyclic graph (DAG) G AA, where is a finite set states and A is subset S representing directed edges, and each element of A corresponds to the state transition a, + S1+1- The complete trajectory is a sequence of states т (#0: ...; 8n; 8f) E TT where 8o an initial state, 8, terminal state and TT is set containing all complete trajectories. In order to measure the proba- bilities associated with states 8, non-negative function F(.) corresponding "flow" is introduced. F(sr, dx) = F(; - 5t+1) corresponds to edge flow action flow. F(T) corresponds to the trajectory flow and the state flow is the sum of all trajectory flows passing though that state, denoted as F(s) = Eeer F(T). If fix the total flow of the DAG as Z flowing into terminal states s to the given value r(sr), ). and consider the DAG out through all sy, we can obtain Z = F(so) F(s)) rssy).
Flows and Probability Measures:
water pipe, in which water enters in so and flows
Based this flow network, the stochastic policy associated with the normalized flow probability P is defined as follows,
I(a, st) = PP(S1+1 (s)) = P(s - set1 8x) = F(s + St+1)
(2)
F(s.)
where Pp(841 st) is called the forward transition probability. Then we can obtain PP(T) (f= Pr (8)) which yields
=
F(s) PF(s) Σ PF(T)- F(eTF(T) 2
T:SET
Our goal is to obtain = Pr(T) x r(s)).
Coate-Conditional Flow Network Following Bengio et al. (2021b), consider flow network based on a DAG g = =S, and a non-negative flow function F(-). For each state E S, the subgraph G, consists of all s' such that s' 2 where > follows the partial order. Then the state-conditional flow network is based on the family (G., E S} with a conditional flow function F: x T -> R- in which T = Us and Ts is the set of trajectories in G, containing all {r (s....,8y) 85)} such that Vsn, 8m T
Fs(sn 5m) F(s.. + 8m).
Based on this definition, we have the initial flow of the state- cate-conniiional flow network refers to marginalize the terminating flows F(s' + +sy), i.e., for any terminating state s' we have Bengio
al. (2021b)
Fs(50 18) Fo(s)
Σ F(s' + s8))
4

---

Published as a conference paper at ICLR 2023
Then, can obtain the corresponding probability measures the following
P.(s' (s) F, - (8)) Fs(s)
As 2
The flow F(s) through state in the original flow network could not provide the marginalization over the downstream terminating flows, we thus introduce this state-conditional flow network satisfying the desired marginalization property. In our task, considering the message passing scheme, we set to start sampling the trajectory based on chosen starting node vp. thus the transition from an empty graph to that node no is ignored here. We can consider that each trajectory sampled from the subgraph family {Gea) ). where 8o vo. Then similar to the way estimate the flow of a flow network using GFlowNct, based on the conditional state flow network, we could still train a policy to obtain Pao (sy) x r(sg). Based equation [ we can omit this subscript in the following sections.
3.3 STATES AND ACTIONS
In this subsection, give the following definitions on states and actions, and also node neighbours and graph neighbors for following valid action set A and valid parent states in Section 3.5
(State) A state St E S in GFlowExplainer refers to a subgragh (s consists of several nodes. The initial state So contains starting point vo and final state 8y subgraph attaining the stop criteria.
Definition
Since we need to guarantee the connectivity of the generated subgraph G.. for every step we can only select node from the boundary of the current subgraph (s)).
Definition 2 (Neighbours) There are two types of neighbors: node neighbors and graph neighbors. Ye,, U/ E Gg. if [Ve, Uj} E E, then we define o as a neighbor of node Uj. denoted as v, E (v;)), and vice versa; Yu, & Go, if 3oz E G., such that {ui, Uj E E, then we define vs neighbor of graph Gz())), denoted as v; E (st.)
Simply to say, graph neighbours contain boundary nodes that have yet been selected into the sub- graph. Node neighbours represent the connect relationships of each pair of nodes in the subgraph.
Definition 3 (Action) An action de St - 86+1 A in GFlowExplainer is to add node from (st). denoted as a, : {vx}+ ~ Ns::). Thus making a state transition St-1 = St U [u,}.
Since need to combine the features of all nodes in (sss) and Gs(st) the input to calculate the action distribution, for each node u; E (s:)) U (s:). we concatenate two indicator functions with its original feature vector 2;, to distinguish the initial node uo and all nodes in the subgraph (st). The insights behind are: 1) for the node classification task, the generated same subgraph should have different scores for the specific node to be explained; 2) the allowed action is to select node in (*x)) instead of (&t),, which will introduce cycles for our DAG structure. Therefore, the initial feature representation X is obtained by follows,
xf [ 1 m m (c.)l, X [e]leeee.
Considering the associations among nodes in graph structured data, for each node U. crucial to combine information from its neighbours. To achieve this, we apply APPNP, a GNN method proposed by Klicpera al. (2018), which separates the non-linear transformation and information propagation. We have the following update equation,
H!C) = 0 H((t1) = (1 a1 + a.!
(8)
where θ, is the trainable weight matrix, a is a hyper-parameter used to control weight. After L- layer updates, we obtain the node representations H.,, and then feed them into a MLP improve the representation ability:
(v.) (c)); (())s))
(9)
where O2 is the leamable parameters in the MI..
5

---

Published as a conference paper at ICLR 2023
3.4 ReWARd, STARTING NODE AND STOP CRITERIA
Similarly to Luo et al. 2020), we use the cross-entropy function to replace the conditional entropy function HY 8y) with .V given instances, and define the reward function follows:
N
r(s,, Y) exp(- Y)) = exp(
P(Y - c) log P(g c)),
(10)
==1
where & is the prediction loss; / is the generated explanatory subgraph for an instance; C' is the number possible predicted labels; P c) is the probability that the original prediction of the trained GNN & is c; and P(Y c) is the probability that the label prediction of d on the subgraph 8y c. We use the exponential term here avoid negative reward.
For node classification tasks, the starting node is the node instance to be interpreted. In contrast, for graph classification tasks, any node could be the potential starting node and the choice of determines the explanation performance. Therefore, we construct a locator IL to identify the most influential node the graph similarly to (hhan et al. (202T). Given graph instances gn. the prediction loss of the classification can be rewritten with the locator IL as ÿ Φ [(g,))). {(()()))L()n)) We
train a three-layer MLP to model the influence a node Us, on the label of the graph instance Jn:
Wi.n MLP(( Fer,..)s
(11)
where 2g., and Pug,. are respectively the feature representations of the graph In and the node fi,m after 3-GCN layers based on the trained model (()). We train this neural network based on some sampling graph instances with the Kullback-Leibler divergence loss
KIDDivLsss(ui, - [( Vi.n),yg.)))
so that the distribution between estimated value wi, is closed -[(T(s) vt,n), Yg asymptoti- cally, and the softmax layers are used to transform these two values into their distributions.
To obtain a compact explanation and avoid generating large subgraphs, we impose constraint |syl < KM so that 8, has at most KM nodes. We also introduce self-attention mechanism similarly to Shaa et al. (202T), which could aggregate the feature representations:
exp(0f (v)))
(w:)) = EnyeNio)) exp (f He(o,))
t (st),
(12)
H, Σ 2.EEG 7 (H))).
(13)
where the parameter 01 learns the attention (vx) for each node u. We can concatenate (STOP) into feature representations in equation 9
We should note that all learnable parameters above are the components in our policy network.
3.5 EFFICIENT PARENT STATE EXPLORATIONS
Flow matching condition is crucial element in flow modeling. For current state st, need to explore all its direct parent states and corresponding one-step actions, i.e. 8, a T(x, a) = &t. which refers all sets (s, a) that could attain 8t. However, the connectivity constraint makes exploring valid parents non-trivial since we need to guarantee that the graph is always connected. We consider this task a cut vertex exploration problem, which aims find all vertices that will break the connectivity of a graph for each st. If a node is cut vertex, we can not find valid parent state by deleting it. By taking advantage of the step-by-step generative process, we can update and store the cut vertex without repeatedly checking. Based on Definitions 4 and S in the following Theorem [ we show how to update cut vertices for each step, which is proved Appendix A.2
Definition 4 (Cut vertex matrix) cut vertex matrix of a state 8t is a dynamic matrix 2 E Rixt where Z,, 0 and if (st) 0, then we say v; is vertex at st-
Definition (Connectivity vector) Suppose an action a, = { connectivity vector of state s binary vector (0, 1xtx1, Vo; E Gs(st), 21())) 1 if (v., v3} E

---

Published as a conference paper at ICLR 2023
Lemma Suppose action a, {Uy} b i E (st))) if is not vertex at St, vi becomes cut vertex from $1+1 iff [a(a)) and (1r 1n} E &, where t > 1. If ey is a cut vertex at St, V is not cut vertex from 8++1 iff (a())))
and a, connects all "child groups" of the v..
Theorem Staring from (st)
0 2x for any action a, [[Ug}+ E A, 2, the connectivity
vector of state St is constructed by
zn (1t) = AJin, Vuu E (G(),,,,
(14)
then we update cut vertex matrix 2 (81+1) by
Z(s(+1) = ('() z((at)
(
}.
0
(15)
where (s(s,) (st) are constructed based on the following equations: 1f ((:)) = 1, Gg(st), (uu; 13} E E Vum E (G,(s))
{ z'(0,) = 2'()) = (ax) + z(a)) [max 2m (8t) } + 1]xx1
(st) = (1 lxxt A (st) +
z(ax). Tlxtt
(16)
2. If ((())))) > 1, k = 0, t; Vu' E (st)
{ 2/m (a)) = Lawm [max (st) A 2 (at))
3y (x1) = Tue [m22 max 2m
( (8t) A = (ax)) + -1- (1-Imm (m,
(17)
where That = 1 iif ser( 2m (8t) A (8t)) F set( (mt)))),, Tmum = i0' 2r (8))2(a)) # O. Tse22
iff km,k(ss) E set( 2m (St) 2T (at)) set(.) corresponds to distinct value (except 0) in vector: Then based on Lemma ! we have the following criteria to ensure the valid parent exploration in GFlowNets: for 2 2, is cut vertex at 8t iff (2 + O.
Theorem shows how utilize dynamic graphs efficiently update the vertex and thus guar- antee valid parent explorations. This approach a kind of "amortized" checking since we only need consider additional edges from a, instead of all edges and nodes in the (st). thus having lower complexity than previous approaches. We will show the theoretical analysis in Appendix D.3
3.6 TRAINING PROCEDURE
Starting from the starting node, GFlowExplainer draws complete trajectories + = (So. 81, 84) E T by iteratively sampling (v,)+ [(a | 8t), until the stopping criteria is attained. After sampling a buffer, to train the policy (St | aa) which satisfies P(sy, Y) x r(s,, Y), we minimize the loss over the flow matching condition as follows
((T)=
Σ
Σ
F(st, uz) - Teut ((81) 1sti
Σ a1I1Ed
F(s411,
B1+1ET T(s
(18)
where )( F(sr, ar) denotes the inflows of a state 8141+ Eagiee F(S G(+1) denotes the outflows of 8t+1, and r(sy, Y) denotes the reward of the final state, which is computed by equation I0] For interior states, we only calculate outflows based on action distributions. For final
states, there are no outgoing flows and only calculate their rewards. We summarize algorithms for both node classification task and graph classification task in Appendix
4 EXPERIMENTS
In this section, first introduce experimental setup. Then compare GFlowExplainer with a few faate-of-the-e baselines GNNExplainer Ying et al. (2019). PGExplainer Luo et al. (2020), DEGREE|Fenr et al. (2021) and RG--xplained (Shan al. (2021) 1021)in in both qualitative and quantitative evaluations. Further, we evaluate the performance of our approach in the inductive setting as well as ablation experiments in Section 4.4 Appendix D
7

---

Published as a conference paper at ICLR 2023
4.1 EXPERIMENTAL SETUP
Datasets We use six datasets, in which four synthetic datasets Seshapes.BA-Communin Tree- Cycles and Tree-Grid) are used for the node classification task and two datasets (BA-2motifss and Mutagenicity) are used for the graph generation task. These datasets are composed of motifs and bases. Motifs are small substructures predicting the label of node/ /gre/ instances. Bases are the remaining parts of graph which are randomly generated. Motifs are taken as the ground-truth and the goal of explainers is to find them. Details of these datasets are described in Appendix E.3 and the visualizations are shown in Figure
graph, which have been shown to play crucial role in
Model We use the trained GNN model in Holdijk et al. (202T), whose architecture is given in Luo et al. 2020);; Ying et al. (2019). Specially, for node classification, we use the model which consists of three consecutive graph convolution layers connected with a fully connected layer. For graph classification, the model includes three consecutive graph convolution layers fed into two max and mean pooling layers. The two pooling layer output embeddings are then concatenated to generate the input for fully connected layer.
Metries The motifs in each dataset are the ground-truth explanations. The edges in the motif are positive and other edges are negative. GNNExplainer and PGExplainer return mask matrix to rep- resent the importance of each edge in the instance. RGExplainer and ours generate subgraph. The explanation problem can be formalized as a binary classification task, where edges in the ground- truth motif are taken as prediction labels and the weights of edges are viewed as prediction scores. With the explanatory subgraph provided by explainers, the AUC score can computed measure the accuracy for quantitative evaluation.
4.2 QUALITATIVE ANALYSIS
We evaluate the hingle-instane explanations for the topology-basee -basd prediction task without node features in Figure 2 in which the dots in green are our predicted nodes motif, representing the critical nodes for GNN predictions. referring to the irrelevant nodes for GNN predictions. The pink dot is the node to be interpreted, also included in the subgraph. For fair comparison, we choose the same node for each algorithm and output their generated subgraphs. As illustrated in the figure, house, cycle, and tree motifs are identified by GFlowExplainee and have relatively fewer irrelevant nodes and edges. However, in the BA- A--oommnnity dataset, RGExxpaiier fails to find the motif. For graph classifications, we visualize the explanation result for the 2--2mo dataset, and both approaches could find the five-node cycle motif for label 1.
motif, contrast, the dots in orange are predicted nodes
BA-Shapes
BA-Community
Tree-Cycles
Tree-Grd
BA-2motif
RGExplainer
Figure 2: Qualitative Analysis for RGExplainer and GFlowExplainer
4.3 QUANTITATIVE ANALYSIS
We next show the quantitative results in Table We run 10 different seeds for each approach and compute the average AUC scores and their standard deviations. From the table, we can find that our GFlowExplainer performs the best on five datasets. The difference between GFlowExplainer and the runner-up algorithm is not particularly noticeable on the BA-Shapes and MUTAG datasets. However, on the Tree-Cycke -yclle and BA-2motif datasets, GFlowExplainer improves the performance and shows its superiority to other graph generation and perturbation approaches. We should notice that without pre-training, the AUC scores of the RGExplainer on Tree-Cycles and Tree-Grid are always 0.5, while Gllowexplainer does not need any pre-training process and could access the
8

---

Published as a conference paper at ICLR 2023
Table 1: Explanation AUC (Quantitative Evaluation)
Node Classification
Graph Classification
BA-SSspes
BA-Community
Tree Cycles
Tree Grid
BA-2motifs
MUTAG
GNNEXp
0.742=0.006
0.708=0.004
0.540+00001
0.71420.002
0.499=0.001
0,498:20.003
PGExp
0.974_00.005
0.884_10.020
0.574100.21
0.673.1..004
0.133..0.045
0.843:10.084
DEGREE
0.993=000005
0.957=00010
0,902+00002
0.925=00.00
0.755 0.135
0.773::0.029
RGExp
(NoPretrain)
0.983=00021
0.684=0.012
0.500=00.000
0.500=0.000
0.503=00.011
0.623::0.021
RGExp
0.985=00013
0.858=00.021
0.787=0.099
0.927=00030
0.615=000099
0.832=:0.046
Ours
0,999 0.000
0.938.10.019
0.964.1 0.028
0.982..0.011
0.85411..01
0.802.10.024
Improve
1.4%
-2.0%
6.8%
5.9%
13.1%
4.6%
BA-Shapes
1.0
BA-Community
1.0
Tree Cycles
1.2
GF Grinntsplatee
Grian-Squence
5.9
RG NoPretrn n
AUL Scares
RGExplsiner
AUC Sporres
GP ce-Squence cmEspluiner RG-NoPreirin
0,7
All
0.0
RGDxgainer
0.4
0.7
Ratio of Training Instances
Ratio of Training Instances
Ratio of Training Instancees
Figure 3: Comparison among GFlow-Squence, GFlowExplainer, RG-NoPretrain and RGExplainer in the inductive setting for synthetic datasets. GFlowExplainer has better generalizations.
ground-truth motif better. Even though on BA-Community datasets, GFlowExplainer is a runner-up algorithm, is not far away from DEGREF.
4.4 INDUCTIVE SETTING WITH ABLATION EXPERIMENTS
To further show the effectiveness of our proposed theorem and the generalization ability of GFlow- Explainer, we conduct the ablation experiments with various cases and test the performance of GFlowFxplainer in the inductive setting. We compare GFlowFxplainer with GFlow-Sequence, GFlowNett- approach with the same state encoding, action space, reward function, and ob- jective function. The difference lies in that the state is considered as sequence and for each state 8t, there is only one parent state s = s (u; where a;-1 {ui}+, which is similar to RGEx- plainer. We also compare our Gllownxpl with RGExplainer and RGExplainer.
Specifically, we vary the training set sized from (10% 30%, 50%, 70%, 90%} and take the remain- ing instances for testing. For each dataset, run the experiments 5 times and compute the average AUC scores. For fairness, we set the same parameters for each method. The comparison results are shown Figure 3 As for BA-Shapes and Tree-Cycles, since they already have enough training samples for GFlowexplainer when the ratio is 10%, the performances of it are always good enough and fall in certain intervals. We also note that in some seeds, RGExplainer dropped sharply from the initial AUC of 0.77 to 0.5. We conjecture that the policy gradient and Monte Carlo estimation may suffer from high variances and be unstable, which may not be able to generate an explanation con- sistently. In contrast, GFlowExplain more consistent explanations. Finally, we discuss more the properties of DAG and why becomes the critical ingredient of best performance in our work in Appendix B.I
does not need any pre-training strategies and could provide
5 CONCLUSION
In this work, present GFlowExplainer to provide the instance-level explanations for GNNs. The DAG structure in our method eliminates the influence of node sequence and thus without any pre- training strategies,
could provide faithful and consistent explanations with the ensurance of the message passing nature of GNNs. We also propose a specific approach for checking cut vertices in dynamic graphs, thus accelerating the process of direct parents exploration during the training pro- cess. Extensive experiments confirm the efficiency and strong generative ability of GFlowExplainer.

---

Published as a conference paper at ICLR 2023
REFERENCES
Federico Baldassarre and Hossein Azizpour: Explainability techniques for graph convolutional net- works. arXiv preprint 1905. 1666, 2019.
Albert-Lászıó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Emmanuel Bengio, Moksh Jain, Maksym Korablyov, Doina Precup, and Yoshua Bengio. Flow network based generative models for non-iterative diverse candidate generation, 2021a.
Yoshua Bengio, Tristan Deleu, Edward J. Hu, Salem Lahlou, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations, 2021b.
Tristan Deleu, António Góis, Chris Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. arXiv preprint arXiv:2202.13903, 2022.
Alexandre Duval and Fragkiskos D Malliaros. Graphsvx: Shapley value explanations for graph neural networks. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 302-318. Springer, 2021.
Qizhang Feng. Ninghao Liu, Fan Yang, Ruixiang Tang. Mengnan Du, and Xia Hu. Degree: Decom- position based explanation for graph neural networks. In International Conference on Learning Representations, 2021.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs.
Advances in neural information processing systems, 30, 2017
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.0516: 2015.
Lars Holdijk, Maarten Boon, Stijn Henckens, and Lysander de Jong. [re] parameterized explainer for graph neural network. In ML Reproducibilityy Challenge 2020, 2021.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local inter- pretable model explanations for graph neural networks. IEEE Transactions Knowledge and Data Engineering, 2022.
Moksh Jain, Emmanuel Bengio, Alex Hermandez-Gardh Jarrid Rector-Brooks, Bonaventure FP Dossou, Chanakya Ajit Ekbote, Jie Fu, Tianyu Zhang, Michael Kilgour, Dinghuai Zhang, et al. Biological sequence design with gflownets. In International Conference on Machine Learning. pp.
PMLR, 2022.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
Wenqian Li, Yinchuan Li, Shengyu Zhu, Yunfeng Shao, Jianye Hao, and Yan Pang. Gflowcausal: Generative flow networks for causal discovery. arXiv preprint arXiv:2210.08185, 2022.
Yinchuan Li, Shuang Luo, Haozhi Wang, and Jianye Hao. Cflownets: Continuous control with generative flow networks. In International conference on learning representations, 2023.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 338-348 2020.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances neural information pro- 2020.
cessing systems,
10

---

Published as a conference paper at ICLR 2023
Nikolay Malkin, Moksh Jain, Emmanuel Bengio, Chen Sun, and Yoshua Bengio. Trajectory balance: Improved credit assignment gflownets. arXiv preprint arXiv:2201.13255 2022.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 10772-10781, 2019.
Benjamin Sanchez-Lengeling, Emily Reif, Adam Pearce, and Alexander Wiltschko. A gentle introduction to graph neural networks. Distill, 6(9):e33, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1);61-80, 2008.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for nlp with differentiable edge masking. arXiv preprint arXiv:2010.00577, 2020.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, Klaus-Robert Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks. XrXiv preprint 20Xxx::000600358,, 2020.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning en- hanced explainer for graph neural networks. Advances in Neural Information Processing Systems, 14:22523-225333 2021.
Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2): 146-160, 1972.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:20, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets. arXiv preprint arXiv: 1.000691, 2015.
Minh and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph
neural networks. Advances in neural information processing systems, 33: 33:12225-12235 2020.
Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-seng Chua. Causal screening inter- pret graph neural networks. 2020.
Max Welling and Thomas N Kipf. Semi-supervised classification with graph convolutional net- works. In J. International Conference on Learning Representations (ICLR 2017), 2016.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826. 2018.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zimik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 430- 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph ral networks via subgraph explorations. In International Conference on Machine Learning, pp. 12241-12252. PMLR. 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.

---

Published as a conference paper at ICLR 2023
Dinghuai Zhang, Nikolay Malkin, Zhen Liu, Alexandra Volokhova, Aaron Courville, and Yoshua Bengio. Generative flow networks for discrete probabilistic modeling. arXiv preprint arXiv:2202.01361, 2022.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference on artificial intelli- gence, volume 32, 2018.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 2020.
Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2921-2929, 2016.
12

---

Published as a conference paper at ICLR 2023
A PROOF OF MAIN RESULTS
A.1 PROOF OF LEMMA D
Definition 6 A node oi is a cul vertex iif 30, vb, E G, such that there is no node sequence T (Way...y vb) along edges if 0s U, which means Va could not attain Ub without passing through vi. and vise versa.
First we should note since > 1, there are at least 2 nodes in (st). Suppose on is not a cut vertex
8t, then based on Definition [ Vua: t/ E Gs()s) such that 30 (Vay..., Ub) in which os ह. Suppose = { Since there is no node deleted, we have Vr,, Ub E ($t41))//(r 8y h 36 = (Ua...., v6) in which v, & ō' based on the connectivity of Gst)). If U; becomes cut vertex S1+1, we could have Fu, E (s lia # U; lia # 1 such that Ar = (Vay..., 1i) where & U. Thus E. If (a()) > means B0 (s(++1)), Uk F Ue for ez E E, it easy to consider there is a vertex sequence U7 = (Va.... .... U2. 2/)) where U; & U, thus U2 is not a cut vertex based on Definition 6 Thus if o; becomes a cut vertex at 8141, we have (5, (W(, =
we have (u,, by)
If {er, k5) E & and W(a)) 1, then Vn, (8(++1)), Va F Us Ca o Ui, we have {va, mi) & & Therefore, there is no sequence like (Fas..., Vy) without Us. Then based on Definition above, have v; is cut vertex.
Then we complete the proof that v; not a cut vertex at 8t, ot becomes a cut vertex from 81+11 iff (a.)) = 1 and {ua, E &, where / >>>>> 1. Based this, we can get the following Corollary
Corollary Suppose an action a = {v,}* there are no cut vertex at st. (a:)) then there are no cut vertex at 81+1-
Next prove that if v, is cut vertex at Sc, Us is not cut vertex from 814-1 iff (ax)) and a connects to all "child groups" of the U/-
We can consider if o cut vertex at St, looks like a parent node in a tree and there are some children of ez. Then if (a(a) = 1, [e,,,,} E &, By becomes a new child of us in tree, and thus there a new "child group" of the Vs. Thus if an action a, {v&}* could connect all "child groups" of the then these nodes could attain each other with passing through ey instead of v; and thus i; becomes non-cut vertex from $1+1-
A.2 PROOF OF THEOREM
1
Next we prove the Theorem by mathematical induction.
1) We first prove that / = 2, 0; a cut vertex at 8:41 iff (8c4 # 0.
Suppose / = 2, then 2(x,) 002x2- Since there are only two nodes va in (s:),, without loss of generality, we define 4g = (wa) and 01 = {m,)+. Suppose a, = [w:}+.
If [Waa)) = 1, for example, {Ma, #;} E E (2% is symmetrical), then ea becomes cut vertex
according to Lemmal) Based on equation 14 equation 16 we have x(ax) = [] 0j and
0
2'(xx) = (1 - T2x2) A (2)))) + =(ar) [1]x2]] =
2
2
2'(a:) = =2((s)) =((a)) + =(a)) A
1 =
0
2
Combine these two parts based on equation 15 we have Z($441)
0
0
0
0
Since 1Z)(5 # [0]x(++1) we have e, becomes a cut vertex, and e, has two "child groups".
Next we prove this by contradiction. Suppose [a(a;)] = 1, [e,, 2t} E E and Zo(s)4) = (0) (0)xx(e+1)- Then based equations above, we have 2/ (st) [0) 1x2 and =b((;)) 0.
13

---

Published as a conference paper at ICLR 2023
0 1 1 0 1 (sx)
0
(+)+)) = = [0]xx2,
lx2, since (1 12x2)
0 we have z(ar) [x]xx =
( thus =(ar)= = [0 0j"², which contradicts to our statement that z(a,) = [] 0J² Thus we prove that 2, if ((a,)) = 1, then vs is a cut vertex at 81+1 iff ( #0.
If [aa)) > 1, since there are only 2 nodes in (st),, thus we have (a(a))) = 2, fea, E and [2h.. E Then based on Corollary [ there are no cut vertices 8t+1- Based on equation 14 equation 16 we have z(a;)= = [1 1] and
0
2st)
<(a,)) =
where Leet 0 for both (st) and (st)) since set (s()s) A [1 1)) sef(2(()))) [[],
set 21 (s:) A [1 1]) set (s:)) [0]. Ieam = O since Σ 3' (s)) ((1)
= 0.
0
Combine these two parts based on equation 15 we have Z($1+1)
0 0 0
Next we prove this by contradiction. Suppose [a(a))) 2, (ray Uz E E, E,, and 3Z (8(+1) * 0, = 0, 1, then we have three cases as follows,
If 20,0 + 0, which contradicts to equation 16 since (1 12x2) = [ 0 1
0 ]
If 2,, * 0, then have Tset which corresponds set( (Z(()) A =² =²{))) +
set (Z)()))). However, (e)(2 A = (a.)) = sell (o((Z((s))) = [0] since Zo = [0) [0]
thus it contradicts to the statement.
If =(() * O, then we have Leum 1, which means Σ ((a)))(((a))) / 0, since x(a))
[1 11"", then we should have (st) + [0] 1x2, which contradicts the cases above.
Thus we prove that = 2, if [a(a) > 1, then is cut vertex at 8141 iff 32 (8t+1) 1) + O. Above all, for 2, we have proved that ny is cut vertex at 8141 iff 32,, # 0.
2) Next we consider f. > 2, suppose at 8t, we have is a cut vertex 8; iff 32, A (8x) * # Suppose a; = {0,}+. We need to prove that is cut vertex 8141 iff 32,, (8 * O
If [(aa)) 1, without loss of generality, we consider {u;, 1i & E G, then based on equation 14 we have 2(a;) = [0-... 1 -0],, where 2a(a)) = 1, 24 (a:) = 0, vk # i.
u; not a cut vertex, have (s:) 1xt- uz a cut vertex, we have Z, & (st) ( 0, (st) is the row corresponding to Then based on equation [6, we have
2((st) = (1 - 4xx) 2 A (Z(s)) + [Z(())))=(())))) z(a)) [1]1xt}.
We should check [2, x[] and there two different cases. Before giving the proof, we intro- duce Lemma as follows,
Lemma Suppose a, N(a,) e E G.(.). 1f (x))(1 - =ax)) ) + 0, vy connects to cut vertex and if 2, (t) x(a:) 0, vy connects to non-cut vertex u..
a) If [1) (ax)) = 0. which means connects to a non-cut vertex based on Lemma 2 If not vertex 8t, have 2, (st) 0 1x and
(s)))) = [1 Txx1s ^ (st) + [z(a)) [1xx)] = .........11 1].
where (s,( 0, Z (5)) 1, wk And we have
=a())) (3'(st) x(0r)) + (ax)) A [max ((()() + +1] 1]=2
Combine these two parts based on equation (1,(81+1) 0, (st+1) k # k - 1, 2,,(01+1) =2 2. Therefore we have
15
we have 2,(5141) = -[1 [1...0m
........ ..... 2]. where
14

---

Published as a conference paper at ICLR 2023
( * O O.,tt Since v is not a cut vertex, [a(a)) = 1, for my} E, based on Lemma ! we know 24 is a cut vertex at $1+1-
b) If (1( [ * 0, which means there are some some cut vertices st, and vj connects to a cut vertex based on Lemma2 2 this case, it is easy to consider o will still be cut vertex at state
8141 since Vou Gs(s++1). the + Uj Uh # Us, vk not attain V/ along edges without passing through 8; based on [(aa]]] = and vice versa.
Without loss of generality, suppose (s)) 0, (st) 1, < <1, + i, (s,( 2. This assumption is the case that dz-1 = [ea} [W(a--)) 1, us becomes a cut vertex at 8t. Then based on equation 16] we have
(((s (1 - 1xt)) A Zx(st) (st)
={{(a)) (s)) z(a))) + (:( A [max (8((s)) + +1] 1]= =
Combine these two parts based on equation 15 we have (,(4) = [1 [1.......2. (x(x)))) is easy to see by could divide G. (s(11) into parts.
Thus we have shown that if [ax) = 1, is cut vertex iff ( 7 #0
If (ax)) > 1, without loss of generality, we can suppose (ax)) = k. k 2 2, then we have
non-zero positions in 2(ae). Before giving the proof, we propose Lemma 3 as follows,
Lemma 3 Suppose
{u;} ++, is cut vertex at st, then becomes a non-cut vertex at 8t-1 iif (et( =(a))) set (st)-
Suppose 22 is cut vertex in 8t, which means Wk + (s.) + 0, (st) has t 1 non-zero positions. We need to check whether V/ connects to all "child groups" of t/s then v; may not be a vertex after adding Vi- Then there following two cases:
a) If set(2, A =(0e)) = set (st))
* [0]. then based on Lemma we have v; becomes a
non-cut vertex at 81+1- Based on equation 17 we have
(s,)
[0]xxe
2/(a,) =
Then based on equation
16 we have 2, (8c+1) = [0] 1x(+1+)
b) set (Z((e) A z(a:)) + set( (+))), then based on Lemma we have us is still cut vertex at 8.41. Based on equation 17 we have
(st) Tser2 max (ont(sst((2)) (2)(s)) (a:))) (1 - Tset2 (1, (8e)
Since v. is cut vertex in 8t, thus (st) + 0, Vi * k. Since (a(at)) 1, we have (s(s,) z(er) # 0xx Therefore, it is easy to know 1 # O. Then based on equation 16 we have =Z,,((2411) * #.
Above all, for 2, we have proved that es is cut vertex at 8141 iff ( # 0. Therefore, we complete the proof that for t 2 2, is cut vertex at st iff 32,,) (s:) * 0.
A.3 PROOF OF LEMMA 2
If (a.)) = and ( ((t)) = [0...I...0]T, where 2: (at) and (a,) = 0, h: # If v; is cut vertex, we have (st) 0 and (st) + O. where k of i. Then based on the precise matrix multiplication, we should have (s:) - 2(a;)] + O.
If oz is not cut vertex, then Zx( [0] xt and we should have (s. =(ax))
A.4 PROOF OF LEMMA 3
Since U; is a cut vertex at 8t, then set (x))) has at least 2 different values based on calculations before, since define set(-) contains distinct value except of O.
If [a(a))) = 1, which means 2(az) has only one non-zero position, it is easy to consider v; is still cut vertex at 8111- If 2x(a.) 1, which means (1y,0s)
vi) E E, then set (e(())))) A =(aa)) 0 +
15

---

Published as a conference paper at ICLR 2023
set( (s))). If (k(a)) = 1, i, then set (s;) A z(aa)) [2,,( * (st(), Thus if [a(a;)] = 1, we have set(2,(s)) A x(a))) & sst( and 2; is still a cut vertex at $1+1-
Based on Lemma we know only [aaa) new "child group" for the current cut vertex. If a, connects to all "child groups" of a cut vertex vis then U, becomes non-cut vertex from 81+11
will potentially introduce
cut vertex, add
If [a((a)) = m, m > 1. Since =(a)) has m non-zero positions, then 2i(s)) A 2(a)) might have O, m 1 or non-zero positions following different cases:
If (sa)) A =(s)) are all zeros, 2; is not a cut vertex.
If (st) A a(a)) has m non-zero positions, e; is a cut vertex and (us, 03} EE
. If (s{):) A x(a)) has non-zero positions, is vertex and (ui U1} & E
Without loss of generality, we start with the case (x)) = [ ... ........... .0.......... ..... 12, which means at-1 = {va) makes iú become
vertex St. Thus (s:) 1, < t, + (x, 2, (st) 0. Then we have v; has two "child groups". the first group consists of all nodes in (s except of vs. the second group only has one node Va. Suppose a, [1 and [N((a)) = m.
If m = 2, (Va, vi} E, (ur, } E &, then (0r) = 24 (az) (az) = 1 and we have set (st) A =(a;)) [2] while set (2.(2,(s)) (s:)) [1. 2]. Based on Lemma [ we know a, does not connect two "child groups" and thus o; is a cut vertex at $1+1-
If m = 2. (Fa, 0 E & and {EE, 2r E,uk + v then 24 (at) = =a(a)) = 1, 2 (at) and we have set (s() A2(a)) = [1.2] = set (st)) Based Lemma we know az connect two "child groups" and thus U; is not a cut vertex at $1+1-
If m > 2, {Va o3} & &, we can easily get set( (st)) 2(a4)) = [1] * set (st)). Based on Lemma [ we know a, only connects U, and thus Us is cut vertex at st+1
Above all, we complete the proof for Lemma
B DISCUSSIONS
B. PARENT EXPLORATIONS DAG MATTERS
Since graph (st):) is generated by sequential actions, the trajectory becomes an ordered node se- quence. However, we should note that the generated subgraph should be an unordered set, which means it is independent of the sequence but determined by the connectivity of the nodes. For ex- ample, for a graph consisting of three nodes, there are pair-wise edges between these three nodes, the generated graph will be the same regardless of the order of nodes. However, if only two edges connect these three nodes, then the intermediate node as a bridge cannot be the last one added. We can conclude that the sequence matters when the ordering of adding nodes will affeec the connectivity of a graph.
There may be many trajectories that lead to the same state 8t, while sampling single trajectory T each time could not contain this information. In order to solve this problem. RGExplainer [Shan) al. 2)22)) applied the pre-training strategies with maximum Log-Likelihood Estimation (MLE) over all possible generated orderings for an explanatory graph Vinyals et al. (2015). In contrast, our GFlowExplainer is modeled based directed acyclic graph structure, multiple action sequences lead to the same graph, and the direct parent explorations for flow matching conditions "connect" these trajectories together, which naturally eliminates the influence of orderings. Therefore, there is no need to pretrain, and we can leam the policy to generate good enough candidate graphs.
We also conduct experiments show the importance of connectivity constraints for loss conver- gence in Appendix (.2
C ALGORIHTM
We show the pseudocode our GFlowExplainer for node classification and graph classification in Al Algorithm and Algorithm respectively.
16

---

Published as a conference paper at ICLR 2023
For node classification tasks, given input graph G (V,E) and its features X' trained GNN model and node instances Z, GFlowExplainer aims to train a generative policy (( 8t) and find the explanatory subgraph G for i-th node instance. Considering the prediction of node instance determined by its L-hop neighborhoods based on the message passing scheme GNNs, which L is the number of layers in the trained model Φ.
During each training epoch, AFFlainxplaine parallel generates 8f for each node U; E I based on policy x x(a 8t) by sequential actions. For every iteration, GFlooWxxlliiner samples valid action a {4/) 1 ~ <(a 82) s.t. V/ E (s(s based on the generative flow network to make a state transition St 8c+-1 and explore valid parents based on the updated cut vertex matrix 2($++)). The terminal state sf is generated once the stopping criteria is reached. When the epoch number E is reached, the trained policy x(a; st) based on the flow matching loss generates explanatory subgraphs in the inference time for evaluation.
As for the graph classification task. the difference lies in the choice of starting node. Therefore GFlowExplainer need to train additional locator IL during the training process. The final graph representations Zy., and node representations 2u,,.. are computed based on the trained GNN model 4. Then LL is trained with policy π coordinately.
Algorithm GFlowExplainee for node classification
Require: G EV, Graph ; X: Node features Z: Node instances B: batch size E: epoch number q
Jearning rate Φ trained GNN classification model
I: repeat
repeat (For each node in E I. parallel do with a batch size B)
3: Initialize = {m: ((0) = T2x2
Construct X,, H," according equation equation 8 and equation
5:
Sample a valid action o, {uy}*
St) s.t. Vi (s.)
6:
Make a state transition 8t+1 8e U {e.
7:
Update Ze+1 according equation 14
8:
Explore all valid parents with (sp, ap) based on 2
until Attain the stopping criteria Calculate rsy, Y) based on equation 10
10:
11:
Update the parameters (91, O2, 01} based on V((()) and
12:
until epoch number E is reached
Ensure: Policy T(a: 8c) and generated explanatory subgraph ( during the inference phase
Algorithm 2 GFlowExplainer for graph classification
Require: ((n) I: Graph instances B: batch size E: epoch number: vp: learning rate ; Q: trained GNN classification model
1: repeat
2:
repeat (For each node (()) E I, parallel with a batch size B)
3:
Initialize (T((G())) 2(8o) T2x2
4:
Construct X², H.' according to equation 7 equation S and equation 9
5:
Sample valid action a, {,,}+ ~ T(a s.t. e, E (s.))
6:
Make state transition 8t+1
((3
7:
Update Z,+1 according equation
Explore all valid parents with (sp, op) based on 2
9:
until Attain the stopping criteria
10:
Calculate rsy,, Y) based equation 10
11:
Update the parameters (θ,, O2 01) based VL((T) and # Coordinate train
12:
13:
for each sampled graph G E do
14:
D D= [r(s) 2.), (s v:))]
15:
Update parameters in L on D end for
16:
17:
until epoch number reached
Ensure: Policy T(sy (L((())) and generated explanatory subgraph G during the inference phase
17

---

Published as a conference paper at ICLR 2023
Table 2: Inference Time
Inference Time BA-Shapes
BA-Community Tree-Cycles Tree-Grid BA-2motifs MUTAG
GNNExplainer
53ms
76ms
49ms
57ms
34ms
16ms
PGExplainer
12ms
17ms
3ms
2ms
Ims
14ms
RGExplainer
8ms
2ms
7ms
6ms
5ms
9ms
Ours
7ms
3ms
8ms
1lms
6ms
7ms
Table 3: Training Time
Training Time BA-Shapes BA-Community Tree-Cycles Tree-Grid BA-2motif's MUTAG
RGExp
102.56s
143.73s
83.36s
463.61s
1294.26s
2918.22s
Pretrining
Ours
Update
RGExp
24s
22s
11s
5s
14s
28s
per epoch
Ours
8s
10s
9s
10s
7s
12s
D ADDITIONAL RESULTS
D.1 EFFICIENCY ANALYSIS
We also compare the inference time of GNNExplainer, PGExplainer, RGExplainer, and our GFlow- Explainer with the same environment. We compute the average inference time for explaining single instance for each task and report the results in Table 2 We could find that GNNExplainer the slowest, and the inference time of RGExplainer, PGExplainer and our GFlowExplainer are in the same order of magnitude. Therefore, we can conclude that the GelowNeet-bbsedd fraamwork will not require a longer inference time.
Since the sampling procedure for a connected subgraph is similar between RGExplainer and GFlow- Explainer. We also report the training time of our GFlowExplainer and compare it with the RGEx- plainer, whose pre-training part is also included. The comparison results are shown in Table 3 As we mentioned before, GFlow Explainrr does not need pre-training process. However, we can find that pre-training strategies of RGExplainer take much time and even become dominating in the total running time. As for the time of iterative update per epoch, GFlowExplainer is overall faster than RGExplainer, which could also show the efficiency of the proposed Theorem [] for updating ver- tices. The EFFloEEplaing is more practical than other learning-based approaches for large-scale datasets.
D.2 Loss CONVERGENCE ANALYSIS
In this section we conduct more ablation experiments to show the role of connectivity constraints for flow loss convergence. In the previous ablation experiments (refer Section 4.4 com- pare GFlow-Sequence and GFFloExplaiier on the explanation performance in the inductive setting. In this section we consider add DAG structures without connectivity constraints, that is, there ([G,(s:)l- -11) direct parents because the node to be interpreted could not be deleted, and (G(s)) corresponds to the number of nodes in the subgraph ) for state s,, We call this approach GFlow- Graph. Based on the theoretical sense, breaking connectivity constraints while exploring parent states will make the inconsistency between action space and trajectories in the DAG structure. We visualize the flow matching loss of both GFlowExplainer and GFlow-Graph We set 5 different seeds on the BA-shape datasets, 16 batches with 80 epoches for each sampling.
Figure&shows the flow matching loss of GFlowExplainer and GGllo-Graap Since the original flow loss is small at the beginning of training, we expand the multiples of the regular items in the reward function to make the loss relatively high. As result, can find that both approaches could attain convergence, but GFlowExplainer has lower losses, which confirms our statement. Furthermore, both approaches could converge fast because once confirm the starting point, the allowed action space reduces significantly due to the connectivity constraints and the stopping criteria, thus making the flow calculation easier. We also plot convergence analysis for other datasets in Figure 5 We
18

---

Published as a conference paper at ICLR 2023
GFlowExplainer
GFlow-Graph
400
Loss
200
0
40
60
80
Epoches
Figure 4: Flow matching loss for GFlowxxplainer and SFlow-Graphe
B4-Commurity
Tree-Cydes
Tree-Grid
800
GF OFinei
600
400
Row 400
200
20
Figure 5: Convergence Analysis
experimentally observe that Gllowxxplainer could converge on all these datasets, where the x-axis represents the training epoch, and the y-axis indicates the flow matching loss.
D.3 COMPUTATIONAL ANALYSIS THEOREM
Tarjan's s strongly connected components algorithm Tarjan 1972) need to iterate all nodes and edges of the subgraph (st). The time complexity is O + El) for each state, which is inefficient for dynamic graphs. In addition, exploring all edges and nodes is disaster for space complexity with large graph and not applicable in real-world applications. However, we can update and store the vertex without repeatedly checking by taking advantage of the step-by-step generative process. The idea is to snap to the properties of a cut vertex in dynamic graphs and identify conditions for transformations between cut and non-cut vertices.
To show the effectiveness and efficiency of the proposed Theorem I in this section, we visualize the vertices in dynamic graphs via a simple simulation experiment. In addition, show the time comparison between our proposed algorithm with other traditional cut vertices algorithms.
We construct a 10 X 10 adjacency matrix represent an undirected connected graph, and starting with two nodes; the subgraph adds neighbor node sequentially. We record the time of the Tarjan's algorithm and our approach. For a fair comparison, the updating process time our method is also included. We report the accumulated time in Figure We can find that with the increasing size of the graph, the accumulated time of Tarjan's 's algorithm increases sharply while our approach increases linearly. We also visualize the cut vertices exploration process in dynamic graphs in Figure 7 in which the black dot represents the action of adding that node, pink dots correspond to the cut vertex, and the orange dots are regular nodes in the subgraph. It is easy to find that only the action node will introduce a new cut vertex or delete a cut vertex. Therefore, we can only iterate the new edges introduced by the action node and check its connectivity relationships with other nodes in the subgraph. In contrast, Tarjan's 's algorithm will iterate all nodes and edges the subgraph after adding the action node; thus, it makes sense that approach has smaller time complexity.
D.4 MORE INDUCTIVE SETTING RESULTS
Due to space limit, we add some inductive experiments in this section. The Figure shows the induc- tive experiments of four algorithms on Tree-Grid and MUTAG Datasets. As for the reinforcement learning based approches, the performance of Tree-Grin is similar that of Tree- CyeeeSy Without pre-training strategies, the AUC value of RG-NoPretrain remains at 0.5 and RGExplainer could pro- vide better explanations with the increasing size of the training instances. The ratio change of the
19

---

Published as a conference paper at ICLR 2023
Accumulated Time(E 05)
17.5
Ours
Tarjans
15.0
12.5
10.0
7.5
5.0
0.0
Adding i-th node
Figure 6: Time Comparison exploring cut vertices
(1)
(2)
(3)
(4)
Figure 7: Cut vertices exploration in dynamic graphs: From left to right is the process of adding nodes step-by-step. is easy find that only the action node (black) will introduce new cut vertex (pink) or delete cut vertex.
training set has more significant influence on the performance GFlow-Sequence. GFlowexplainer can always maintain high performance, showing its strong generalization ability. In the MUTAG dataset, both GFlowExplainer and RGExplainer perform well.
E IMPLEMENTATION DETAILS
E. BASELINES
GNNExplainer Ying et al. 2019) is the first formal approach to explain trained GNNs, which defines the problem optimization task maximize the mutual information be- tween the predicted labels and the distribution of possible subgraphs with some constraints. Codes are available at hhttps:/giihub..om//Rec Ving//na-mooee--exppaann
Tree-Grid
MUTAG
0.9
0.9
Scores
GFlow-Squence GFlowExxpainer RG-NoPretrin
AUC Scores
0.7
0.7
RGExplainer
GFlow: Squence
GFlowExplainer RG NoProrrrinn
0.5
0.5
RGExpl siner
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
Ratio of Training Instances
Ratio of Tra Training Instances
Figure Inductive setting with ablation experiments on Tree-Grid Dataset and MUTAG Dataset
20

---

Published as a conference paper at ICLR 2023
Table 4: Hyper-parameten,
Hyper-parameters
Value
Batch Size
64
Number of layers of APPNP
in APPNP
0.85
Hidden dimension
64
Architecture MI.P in
64-8-1
Learning rate
lc-2
Optimizer
Adam
Number of hops
Maximum size of generated sequences
20
Training epochs (node tasks)
{50,100)
Training epochs (graph tasks)
100
Sample ratio of graph instance to train
0.2
PGExplainer Luo et al. 2020) leverages the representations generated by the trained GNN and adopts a deep neural network to learn the crucial nodes and edges. Codes are available at https://github.com httph/uww..oom/lllgooooooop htlplllgoooogg/GEpaaagggggg
DEGREE Feng et al. (0221) proposes decomposition-basse explanation method for graph neural networks, which directly decomposes the influence of node groups in the forward pass. The decomposition rules designed for GCN and GAT. Further, to ef- ficiently select subgraph groups from all possible combinations, the authors propose a greedy approach search for maximally influential node sets. Codes are available htw.aeooooiiiiaaaaeennnenniiiiie
RGExplainer (Shan et al. (2021) utilises the Reinforcement Learning to generate the instance-level explanations for GNNs. The seed locator and stopping cri- teria to find the most influential node in a graph instance and check whether the generated explanatory graph are good enough. Codes are available
E.2 EXPERIMENT ENVIRONMENT
All experiments were conducted on NVIDIA Quadro RTX 6000 environment with Pytorch. The parameters of GFlowExplainer are shown in Table
E.3 DETAILS ABOUT DATASET
We show the data statistics in Table 5 In this paper we consider the following five datasets:
The BA-shapes data consists of one Barabasi-Albert graph Barabási & Albert (1999) as the base and 80 house-structure motifs. Each motif is randomly attached to a node in BA graph and extra edges are added noises;
The BA-community dataset is comprised of two BA-shapes with different node features generated by Gaussian distributions. The extra edges are also connect two BA-shapes;
The Tree-cycles dataset includes a multi-level binary tree as the base and 80 six-node cycle motifs. The cycle motifs randomly attached to the tree.
The BA-motifs dataset has 1000 graphs where half of them BA graph attached with house-structure motif, while the rest are a BA graph attached with five-node cycle motif;
The Mutagenicity dataset is a real dataset, which includes 4337 molecule graphs. They can be classified mutagenic nonmutagenic depending whether having N H2 NO, motifs.
21

---

Published as a conference paper at ICLR 2023
Table 5: Dataset statistics
Node Classification
Graph Classification
BA-Shapes
BA-Community Tree-Cycles
Tree-Grid
BA-2motifs MUTAG
#graphs
1
1
1
1
1,000
4,337
#nodes
700
1,400
871
1,231
25,000
131,488
#edges
4,110
8,920
1,950
3,410
51,392
266,894
#labels
4
8
2
2
2
2
Shapes
B4-Community
Tree Tree-Cycles
Tree-Grid
BA-2mottfs
MUTAG
Base
Motif
Community
Latel
label
Figure 9: Base and Motif structures for each dataset Ying et al. (2019)
F ADDITIONAL EXPERIMENTS
F.1 TRAJECTORY BALANCE OBJECTIVE
In the trajectory balance loss objective, we need to parameterize the Zg. PF(s () and optional PB(s: 81+1, 8). One natural choice of Pf (P is to set it to be uniform over all the valid parents of state 8t41, i.e., (-(+(s++1) 1/#[sr - 8141 E AA} suggested in Malkin et al. (2022). In our case only parameterize the former two terms.
Previous suggests to parameterize Zo with a constant since it considers the unconditional case. Therefore, it only need approximate the total flow Z so that Z R(x), Vo E X. In contrast, our task applics the state-conditional GFlowNets, which means there are various subgraph flows Z, we need approximate to get Z, R(z[s). Simply speaking, for each G.. the Z, should be different.
To show the complexity of trajectory balance in state-conditional Gets we have two attempts.
First, we follow the unconditional case and parameterize Za with constant for initialization. This the same as to Malkin et al. (2022). Our objective is to learn the parameters of the forward conditional policies Pr (5 Stc to; and log Ze.
Second, we consider the conditional flow approximation. Our objective is to learn the parameters 0 of the forward conditional policies (r(st+1 (8t, vo; f) and function log Zo (vr). Therefore, Vr (So. Su+1 $4) T, we define the staticconditional trajectory balance as follows,
Zo(v)) II, -s PF(8 0o;
2
[(T, vo; log r(sy(un) II, -1 Pp (s
(19)
In our experiment, we train a three-layer MLP to model Z-(-). The input is the node features of vo in each trajectory and the output is the approximated flow. The learning rate for Zo(.) is 0. the hidden layer size is 128.
We plot the loss convergences for both approaches with datasets BA-Shapes in Figure 10 The unconditional flow could not converge at all and the AUC maintains 0.5 ~ 0.6, the conditional flow could converge after some fluctuations, but the AUC has high variances, shown in Table
We guess the reason behind is that in our task, the loss decreases with the change of both Zp (-)
and Pr(-1- 0). Even though the loss could converge, without good approximation of Zo (-)-
22

---

Published as a conference paper at ICLR 2023
Table 6: Comparisons among Flow Matching, Trajectory Balance (unconditional-22) and Trajectory Balance (conditional-2) Z) Objectives on BA-Shape Dataset.
AUC
Accuracy
Flow Matching
0.99
0.99
TB (uncon-Z)
0.5~0.66
TB (con-2) 2)
0.5~0.88
Trejectory Balance
2500
2000
1500
Conditional
Unconditional
1000
500
0
20
80
Epoches
Figure 10: GFlowNets using trajectory balance. Left figure shows the different flow loss with conditional (vo) unconditional Ze. Right figure shows the explanation subgraph for simple node with TB, which fails to find the motif. Without correct approximation to Z, GFlowExplainer could sample sy so that Psyy) ( x r(sy).
we could not obtain correct Pf(-1-.-:0) In the graph structure data, most nodes have the same features (especially the synthetic dataset), thus such conditional information does distinguish them when feeding them into neural networks. For example, if U; and vy have the same features, we could output same (o(v;) Zoz)), while with high probabilities that Σ (1,)) * Er(sy(og) Thus we have bias on approximations to the flow, which could further affect the approximations to Pr(- Pr(-1-:-;0) 0). However, using Flow matching loss, we have the following equation
ET(aa F(s,, aelVo) log C(vo) log r(sg)u0)= + Eamie (664410044100))
(20)
For future work, the neighbor nodes of each un could also pass message to it, thus aggregating them with more complex graph neural networks instead of MLP more suitable in this study.
F.2 QUALITATIVE ANALYSIS
F.2.1 GRAPH-SST2 DATASET
We add real-data set Graph-SST2 Yuan et al. classification. It contains 70042 graphs with average 10 nodes in each graph. Each graph is labeled by its sentiment, which is either positive negative. The node embeddings are initializes as the pre-trained BERT word embeddings. We train GCN classifier with overall accuracy 88.7%.
2022). which is sentiment graph dataset for graph
Since the graph sizes are different and some of them just contain few words, we choose graphs with relatively larger size to evaluate our explainability. We should note that this dataset does not have ground-truth structures, thus visualize the subgraphs generated by GFlowExplainer for qualitative analysis. In Figure I each sy consists of green nodes, which are identified as important nodes for classification, the orange nodes are irrelevant nodes. Both graphs are correctly classified as "negative". We could find ("be failure", "because doesn't 't know to have fun") and ('it's frustrating these guys". "waste their talents ") could explain these classification decisions.
23

---

Published as a conference paper at ICLR 2023
3ta 2irestral Trestrating
lile
2prd
sprdlessione
onal
these
Game
Bwha
Bauy
10at
13 detr
Manie
ppreibysa
12.
mmus
15ther
stalen
Aiwate
17on
15%
21n's
18parodies
Tedrives
Tashe
20doess
(19ar
Sand
Stninngs
Pahavi
27.
2itheee2gre Zerobabh
Tunniest
18ambing
23thoupm
2üwere
Zonign
20eeee
Show
2410
26whe 7the
lanie's professional success mears she musi failure at life, because she's driven by ambition and doesn't know how have fun.
it's frustrating to see these guys who are obviously pretty clever waste talent parodies things they probably thought funniest when they were high.
Figure 11: The subgraphs on the Graph-SST2 Dataset. The green nodes are identified as important nodes and the orange nodes are identified as irrelevant nodes.
Figure 12: Qualitative Comparison between PGExplainer and GFlowExplainer on MUTAG dataset.
F.2.2 MUTAG DATASET
We also visualize the results on MUTAG datasets in Figure 12 show subgraphs are more intuitive and suman-intelligiin It is known that the carbon rings and NO₂ N NH, groups are tend to be mutagenic. Our GFlowExplainer could identify these connected important components with correct classification. In contrast, the PGExplainer identifies discrete edges. In addition, GNNs utilize the message passing scheme to incorporate graph structures with node features. Our GFlowExplainer could construct the connected graphs by adding nodes from boundary of the current subgraph step- by-step, which is consistent with message passing scheme and provides more clear explanations.
F.3 QUANTITATIVE COMPARISON
In this section, compare GFlowwExlaiier with a shapley-value based approache SubgraphX| Yuan iet al. (202I) and DEGREE on accuracy. And also shows the fidelity and sparsity in our algorithm. The degree of fidelity assesses how closely related the explanations are to the model's predictions. computes the difference between predictions with and without important structures. Sparsity measures the fraction of structures that identified important by explanation methods. Note that high Sparsity scores mean smaller structures are identified as important, which can affect the Fidelity scores since smaller structures (high Sparsity) tend to be less important (low Fidelity).
24

---

Published as a conference paper at ICLR 2023
BA-Shape
0.00
0.86
Fidelity
0.64
0.62
0.60
0.55
0.80
0.75
Sparsity
Figure 13: Sparsity and Fidelity in BA-Shape dataset
Table Accuracy comparison
BA-Shape
BA-Community
SubgraphX
0.99
0.93
DEGREE
0.94
0.95
Ours
0.99
0.94
N Σ 1=1
Mi G
sparsity
(1
(21)
N
[M] denotes the number of important input features (nodes/cdges/node features) identified. |G means the total number of features in G which refers to the L-hop graph. For GFlowExplainer, the masks can be directly determined by the obtained subgraphs.
N
fidelity = Euricht -J(IG()s))
(22)
N
Suppose the number of edges(nodes) inside motif's for synthetic datasets, we will show the top-k & enges(nodes) ranked by their importance weights in graph generation process. Based on the generation order of edges(nodes). we could assign different weights to them. In our GFlowEx- plainer, the weights of nodes have corresponding relationships with the their orders, which means the enges( with larger weights will be more likely to be added to the subgraph first.
As for the accuracy calculation, comparison. We choose first nodes each generated subgraph and check whether they are in the motif base and show the results in Table 7 our implementations, we found the ground-truth indexes have some inconsistencies in each github public repository, making accuracy calculation biased, thus we fix the these inconsistencies by ourselves.
follow similar setting in SubgraphX and DEGREE for fair
25


Reviews:
[{"review_id": "v9yXgZ08NQ_", "reviewer": "Reviewer_uNyQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose to use GFlowNet in a new application, explainability for GNNs. To me, this is a resemble application for GFlowNet, though, I'm not that much familiar with the explainability problem of GNNs. Intuitively, GFLowNet is able to generate subgraphs based on learning multiple trajectories which maximize a specific reward. In this paper, the authors use MI as the reward which seems to be consistent with the previous models in this domain. \n\nThe paper is fairly well-structured and easy to follow. The most of methodological part of the paper is repeating the first GFLowNet paper. My main concern with this paper is that the authors use \"flow matching condition\" that has known issues. So, it raised some questions regarding some of the qualitative results. \n\n", "summary_of_the_review": "The paper seems to be a good application paper, however, it needs some modification in terms of the loss as well as experiments. ", "strength_and_weaknesses": "**Pros:**\n\n- Applying GFlowNet in a new domain, i.e. GNNs.\n\n**Cons:**\n\n- Based on the loss in eq. 18, the authors only use the naive \"flow matching condition\" which is underspecified and tends to have biased to smaller trajectories. Besides that, it is computationally very inefficient. These are already known and new methods have been proposed. \n\n- This also raises a question about the quantitative results. To me, it is not clear if the shown results in Figure 3 which show a smaller sub-graph for the proposed method are due to these biases or if it is really beneficial from GFlowNet. I would rather like to see the results for the \"trajectory balance\" based loss. \n\n- I'm also not sure how much gain they could get from the efficient parent state explorations. An ablation study around it would be gratefully appreciated. I think a naive solution still should not be that complicated.  \n\n- Evaluation metrics are not enough. I would like to see comparisons in terms of Fidelity and Sparsity as well. \n\n- I also believe some of the baselines are missed. \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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sO5vQxVzE8", "reviewer": "Reviewer_NBTZ", "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 authors apply GFlowNets to the problem of scheduling operations in a computational graph on homogeneous parallel hardware. The evaluate conditional GFlowNets for the first time(?) with the computational graph being the conditioning input and the schedule being the output. They also innovate by conditioning on the reward temperature in order to find a good trade-off between diversity of the generated samples and their average reward. Diversity is important in this application because the generative policy is trained using an imperfect but cheap to compute proxy and only a few of the generated schedules are then evaluated on the ground truth hardware. GFlowNets are interesting in this context because their training objective makes them sample with probability proportional to the reward (rather than maximizing the reward as in other RL approaches). Experiments show improvements against previous methods, including standard RL methods.", "summary_of_the_review": "This paper introduced a new form of application for GFlowNets, mapping a computational graph to a distribution over efficient schedules for it. To achieve this, the demonstrate the feasibility and success of the conditional GFlowNet formalism and also show how to use it to control the trade-off between diversity and average reward by conditioning on the reward temperature (exponent of the reward).\n", "strength_and_weaknesses": "GFlowNets are a new RL variant (less than a year old) with only a few applications yet, so this paper introduces a new type of application, in the realm of scheduling, and an approach which may be applicable more broadly. The successfully show empirical success on two GFlowNet novelties: conditioning on a rich input (the computational graph) and on temperature (to control the diversity-reward trade-off).\n\nIn page 5, they claim that previous works on GFlowNets did not consider the conditional case, but this is not true and they themselves mention in section 4 that Bengio et al 2021b introduced the theoretical framework for conditional GFlowNets. What is true is that may be the first (or among the first, with concurrent work) to validate experimentally this framework and show its usefulness.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "l-xLwdqhy", "reviewer": "Reviewer_CzDM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a method to explain the GNN using a newly proposed tool graph flow network(GFlowNets). This framework enables the model to connect the trajectories of the same graph even with different node sequences. The paper also proposed an efficient cut vertex criteria to speed up the whole process. Compared with traditional Tarjan methods, the proposed algorithm is much more efficient. Also, the experiment part shows that the result outperforms some other baselines.", "summary_of_the_review": "This paper provides a new perspective for graph explainers. The paper also proposed an easy but efficient algorithm to find the parent state. My main concern is the gap in performance. Another concern is the novelty.", "strength_and_weaknesses": "The authors proposed a new framework based on GFlowNet. This network is more explainable since it's based on the conditional state flow network. The whole network is trained to minimize the discrepancy between the sum of the outgoing flow and the final reward and incoming flow. This framework is intuitive and novel. The authors also proposed an efficient algorithm to speed up the parent state exploration process. \n\nFor the weaknesses, I have some concerns regarding the experiment part and the design of the loss function.\n\nJust like the authors claimed, the reward doesn't contain the sparsity or consistency part, which can be important in the GNN explainer model.\n\nSecondly, I'm a little confused since the performance shown in the paper is somehow different from the ones in the PGExplainer. Like the BA-community/Tree-cycles/BA-2motifs, there is a huge gap. Could the authors explain why? I found the performance from the arxiv version here. https://arxiv.org/pdf/2011.04573v1.pdf . Meanwhile, they are some other state-of-the-art baselines that are not compared in the paper, like IB-SUBGRAPH, GraphMask, DIR(Discovering invariant rationales for graph neural networks).  \n\nI also have a question regarding the GFlowNet, since it is somehow related to reinforcement learning, I wonder if the model is robust. Or do we need to carefully tune the model to make it work?\n\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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KvNgvGSsClj", "reviewer": "Reviewer_SPuf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 a novel strategy to obtain a connected subgraph as the interpretation of node classification and graph classification tasks. The proposed strategy starts from a state with only one node and learns a policy to achieve state transition via sampling new nodes and adding them to the current state. In general, the techniques used in this paper are novel under the topic of GNN interpretation, which reveals further insights on how to understand in what ways GNN predictions are made. However, there are also clear disadvantages in this paper. See the Summary of The Review for more details.", "summary_of_the_review": "This paper proposes a strategy inheriting the idea of Generative Flow Networks to generate subgraphs as interpretations for GNN predictions, which is novel in techniques. Meanwhile, the theorems and lemmas are supported with detailed proofs. However, there are multiple unaddressed questions that prevent this paper from being well-prepared for publication. For example, the author mentioned that the primary motivation of this paper is: (1) searching subgraphs is a combinatorial problem, and it is hard to solve; and (2) previous works model the selection of subgraphs as a sequence generation problem, which is not beneficial. However, first, most GNN interpretation works based on learning do not require solving any combinatorial problem (e.g., [1]); second, we may also regard the proposed approach in this paper based on state transitioning as a strategy based on sequence generation. I thus believe the motivations above deserve a more rigorous justification. Moreover, there is no detailed discussion on how to choose an appropriate stopping criterion. Should all generated subgraphs reach the constraint of size K_M? Will there be cases where the size of the underlying interpretation subgraph is different from each other? If they exist, how could we design an appropriate stopping criterion that fits all scenarios? \n\nFinally, I would still have extra concerns as follows.\n\n(1) There is a policy network in Fig. 1, while this notion is never mentioned elsewhere in this paper.\n\n(2) The reported AUC seems to be much worse compared with the reported accuracy in the vanilla papers of baselines (e.g., [1]). Will it be more comprehensive to compare both AUC and accuracy?\n\n(3) There is no evidence showing that the exhibited superiority is (partially) because the proposed strategy does not generate subgraphs in a sequential manner.\n\n(4) Will it be better to introduce the definitions in Section 3.3 before these notions are referred to?\n\n(5) Is there any specific reason for the unique performance inferiority on BA-Community datasets compared with the baselines?\n\n(6) Is it possible to include more than one real-world dataset for more comprehensive experiments?\n\n[1] Rex Ying et al. Gnnexplainer: Generating explanations for graph neural networks. NeurIPS 2019.\n", "strength_and_weaknesses": "Strength:\n\n(1) This paper is solid in techniques: definitions are clearly presented, and proofs are also provided in the appendix.\n\n(2) A novel approach is proposed borrowing the idea of generative flow networks to obtain subgraphs as interpretations for GNNs, which could reveal novel insights under this research topic.\n\n(3) The empirical performance superiority on most datasets seems to be promising.\n\nWeaknesses:\n\n(1) The motivation of this paper is unclear: why do we need this model considering the existing GNN interpretation approaches? The presented motivations are not convincing – see Summary of The Review for more details.\n\n(2) There are certain phenomena not clarified in the experiments – see Summary of The Review for more details.\n\n(3) Only one real-world dataset is involved in the experiments performed in this paper.\n\n(4) The writing of this paper needs to be further polished. I did notice some typos, such as “GFlowExplainer does not pre-training process”.\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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster