InduCE: Inductive Counterfactual Explanations for Graph Neural Networks
Authors: Samidha Verma
Burouj Armgaan
Sourav Medya
Sayan Ranu
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) drive several real-world applications including drug-discovery, recommendation engines, and chip designing. Unfortunately, GNNs are a black-box since they do not allow human-intelligible explanations of their predictions. Counterfactual reasoning is an effort to overcome this limitation. Specifically, the objective is to minimally perturb the input graph to a GNN, so that its prediction changes. While several algorithms have been proposed towards counterfactual explanations of GNNs, majority suffer from three key limitations: (1) they only consider perturbations in the form of deletions of existing edges, (2) they perform an inefficient exploration of the combinatorial search space, (3) the counterfactual explanation model is transductive in nature, i.e., they do not generalize to unseen data. In this work, we propose an inductive algorithm called InduCE, that overcomes these limitations. Through extensive experiments on graph datasets, we show that incorporating edge additions, and modelling marginal effect of perturbations aid in generating better counterfactuals among available recourse. Furthermore, inductive modeling enables InduCE to directly predict counterfactual perturbations without requiring instance-specific training. This leads to significant computational speed-up over baselines and allows counterfactual analyses for GNNs at scale.

Published in Transactions on Machine Learning Research (05/2024)
InduCE: Inductive Counterfactual Explanations for Graph
Neural Networks
Samidha Verma Indian Institute of Technology, Delhi, India
samidha. seniibo..ermaacce.ittte.
Burouj Armgaan
Indian Institute of Technology, Delhi, India
Sourav Medya
medya@ric.col edu
University of Alinois, Chicago, USA
Sayan Ranu
sayanrenu@itd.c oc.
Indian Institute of Technology, Delhi, India
Reviewed on OpenReview:
Abstract
Graph neural networks (GNNs) drive several real-world applications including drug- discovery, recommendation engines, and chip designing. Unfortunately, GNNS are a black-bor since they do not allow human-intelligbble explanations of their predictions. Counterfuctual reasoning is an effort to overcome this limitation. Specifically, the objective to minimally GNN, so that its prediction changes. While several algo- rithms have been proposed towards counterfactual explanations of GNNS, majority suffer from three key limitations: (1) they only consider perturbations in the form of deletions of existing edges, (2) they perform an inefficient exploration of the combinatorial search space, (3) the counterfactual explanation model is transductive nature, i.c., they do not gener- alize to unseen data. In this work, we propose an inductive algorithm called INDUCE, that overcomes these limitations. Through extensive experiments on graph datasets, we show that incorporating edge additions, and modelling marginal effect of perturbations aid in generating better counterfactuals among available recourse. Furthermore, inductive mod- eling enables INDUCE to directly predict counterfactual perturbations without requiring instanco-specific training. This leads to significant computational speed-up over basclines and allows counterfactual analyses for GNNS at scale.
perturb the input graph
1 Introduction and Related Work
The applications of Graph Neural Networks (GNNs) have percolated beyond the academic community. GNNS have been used for drug discovery Stokes et al. (2020). designing chips Mirhoseini et al. (020). and recom- mendation engines Ying al. (2018). Despite significant success prediction accuracy, GNNS, like other deep lcarning based models, lack the ability to explain why a particular prediction was made. Explainability of prediction model is important towards making trust-worthy. In addition, sheds light on potential flaws and generates insights how to further refine model.
Existing Works: At high level, GNN explainers can be classified into the two groups of instance-level Ying
et al. 20099) Luo el al. 2020 Shan et al. (2021) ; Yuan et al. [202]] ; Huang et al. (2022): Yuan et al. (2022): Lucic et al. 2022 Tan et al. 2022); : Lin et al. (2021) Bajaj et al. (021;;Abratt
Bonchi (2221) Wellawatte
et al. (2022) or model-level explanations Yuan al. (2020) Consistent with their nomenclature, instance- level explainers explain specific input graph, whereas model-level explainers provide a high-level explanation in understanding general behaviour of the GNN model trained set of graphs. Recent research has also

---

Published in Transactions on Machine Learning Research (05/2024)
Ethene: C2
Ethane:CyH,
Figure 1: The figure illustrates the graph representations of two molecules. A node classified red if it represents unsaturated carbon atom, meaning the valency of the atom is not saturated by covalent bonds with hydrogen atoms. Otherwise, the node is classified green. In the counterfactual task of converting an unsaturated carbon atom to saturated one, we need to add two hydrogen bonds, as indicated by the green edges in Ethane. Counterfactual reasoners that only consider edge deletions would be able to explain saturated carbon atoms with counterfactuals, but not vice versa.
Method
Explainabiltt Paradigm
Modeling Marginal Impact.
Additions
Deletions
Inductive
explainors required
GNNExplaine
2010
Pactual
N
PGEapliiee
GEM
OP-GNNKxphier Jocle
2029
Comnterfactual
OP Tan <t al.
2024
Countrsictual Factual
X
RC RC-esplamn NaR
+l 202
Comnorr tndl Factood
X
ClaneMa et 2022
Comntrffacuul
IoduCT
Commerffactnl
Table 1: Comparison on properties of common perturbation-based GNN explainers. The last column shows the number of required explainers for a graph with N nodes.
focused on global concept-based Xuanyuan al. (2023 Azzolin et al.
2023 explainers that provide both
model and instance-level explanations. Instance level modhods can broadly be grouped into two categories:
factual reasoning Ying ct al. (2019): Luo ct al. (0200); Shan ct al. (2021) ;; Yuan et al. (2021): Huang
et al. 2022;; Yuan et al. (022 and counlerfuclaal reasoning Lucic et al. 2022]; Tan et al. (2022); Bajaj
et al.
2021: : Abrate & Bonchi 2021]; Wellawatte et al. (2022.. Given the input graph and a GNN, factual
reasoners seek to identify the smallest sub-graph that is sufficient to make the same prediction as on the entire
input graph. Counterfactual reasoners, on the other hand, seek to identify the smallest perturbation on the input data that changes the Gxv's prediction. Perturbations correspond to removal and addition of edges.
Compared to factual reasoning, counterfactual reasoners have the additional advantage of providing means for recourse Voigt & Von dem Bussche (2017). For example, in drug discovery Jiang et al. (2020); Xiong et al. (2021), mutagenicity is an adverse property of a molecule that hampers its potential to become a drug Kazius et al. 2005). While factual explainers can attribute the subgraph causing mutagenecity, counterfactual reasoners can identify this subgraph along with the changes that would make the molecule non-mutagenic. this work, we study counterfactual reasoning over GNNs. To illustrate our problem, let us consider the input graph shown in Fig. Here, each node belongs to the green class if it is part of the motif (subgraph) shown on the right. Otherwise, it belongs to the yellow class. The dotted edge At this stage, if we ask the counterfactual reasoner to change the label of node A, the best answer would be to add the dotted edge. Similarly, for node B, one possible answer would be to delete the edge marked with @.
node A does not exist, for now.
Table I presents a structured summary of the instance-level counterfactual explainers. In this work, we innovate on the following key directions that lead to improved explanations and efficiency ($ 4).
Modeling Marginal Probabilities in the Perturbations Space: Identifying the minimal set of per- turbations that induces a change in graph predictions inherently involves combinatorial problem. Hence, it is important for the learning methodology model the marginal influence exerted by individual per- turbations on the remaining perturbations. Existing algorithms have largely disregarded this vital aspect Notably, Cp2 Tan et. al. (2022), CT-GNNEXPLAINER Lucic et al. 2022 and RCEXPLAINER adopt an approach centered on learning a binary mask representing the joint distribution over the feasible perturba- tions. CLEAR uses Graph-VAN VAE Simonovsky & Komodakis (2018) to generate counterfactual graph, thus learning only the joint distribution by optimizing modified counterfactual loss Ma et al. (2022) over the generated graph. Tn contrast, INDUCE introduces innovative reinforcement learning- based strategy,
2

---

Published in Transactions on Machine Learning Research (05/2024)
Rode
Dass
P
Closs
V1
Va
Vio
V2
V5
9.
Attached to green node
V1
V.
motif
V22
%
Vi
Wheel Motif
Ve
Target
M/a
Vo
(8)
(b)
(c)
(d)
Figure 2: (a) A sample graph that highlights the merits of marginal edits over one-shot edits. (b) A wheel
motif (c) Class labels of each node (d) Ground truth rules for each class where and mean presence and absence of the property, respectively. The node colors represent the node labels.
wherein we focus on quantifying the marginal effect of an individual perturbation within the context of a given set of other perturbations. This perspective facilitates the exploration of the combinatorial space at a more nuanced level, resulting in demonstrably enhanced outcomes, as substantiated in $ $ Fig. 2 presents an example showcasing the merits of marginal edits over one shot. Consider the sample graph under binary node classification where node v1, belonging to class is the larget node. Assume that in the underlying data, node belongs class 1 if it is attached either green node or at the center of a wheel motif or both (scc the class label function in Fig. 2 Otherwise, node belongs to class O. Provided the trained GNN has learned this logic, counterfactus explanation from U1 and remove any one of the wheel's spokes (edges between the target and the ring). Now, let us look at the counterfactual generation for the target node under one-shot and marginal settings:
would detach the green node
One-shot: Explainers that learn a mask for all the edges in parallel will assign an importance value I to the edge (1i, 02) between the target and the green node, and importance T2 to all the spokes ((v1, v3). (vi, vs), (Vi, vo), (v1, v7)) since all of them have an identical contribution to the target node's predicted class. Since one-shot explainers employ independent selection on each edge for deletion, it either selects all spokes for deletion none. Thus, when a counter- counter-factual explanation is found, it leads to six edge deletions to get the counterfactual when only two edits should suffice.
Marginal: A marginal explainer's first episode will be identical. The edge (21,02) will have importance I1, and all the spokes will be assigned importance Iz. Now, based on these values, the marginal explainer will either pick the (v1, 02) edge or one of the spoke edges. Let us consider both cases:
1. (v1,0% v2) is deleted in the first episode. In the next episode, the importance values will be recomputed and all the spokes will, once again, receive the same importance. Now, one of them will be chosen and deleted. At the end of this episode, the explainer will identify that the resultant graph has crossed the decision boundary, and there is need to proceed and thereby finding explanation of size 2. 2. One of the spokes with importance I2 is chosen and deleted first. In the next episode, the importance scores will be recomputed for all the edges. The remaining spokes will be assigned identical importance values again, however, it will be a significantly lower value since deleting a spoke no longer has an effect on the GNN's prediction. This is because the marginal explainer will see that removing more spokes has lower reward than removing the green node's edge. Hence, the explainer will remove the green nodc's edge. Following this, the explainer will identify that the resultant graph has crossed the decision boundary, and the process will terminate.
In either case, the marginal explainer will return counterfactual graph with only two edge deletions, which is closer (in this case identical) to the ground truth compared to onc-shot's six edits, showing its superior quality.
Ability to add edges: In counterfactual reasoning, the task is to identify the minimal change in graph such that the label changes. This objective is different from factual explanations where the goal is to identify the substructure responsible for a prediction. Indeed, in a factual explainer, edge additions do not have role since we need to reason within the scope of the structural components within the input
3

---

Published in Transactions on Machine Learning Research (05/2024)
graph being explained. However, in counter-factual reasoning, there is no natural reason to remain constrained to deletions only. Several existing techniques do not consider addition of edges (or nodes); they only consider edge removals. This limitation compromises the search space consisting of possible "changes" on the input graph. Fig. I illustrates this limitation with a concrete example. Specifically, an unsaturated hydrocarbon can be converted to a saturated hydrocarbon only through addition of Alges.Saturate hydrocarbons are significantly less reactive (and therefore a more stable fuel) than unsaturated hydrocarbons, leading to vastly different properties. Now, consider the counterfactual task of identifying the minimal change in unsaturated carbon to obtain a saturated hydrocarbon. This task requires adding (saturating) C-H edges to the unsaturated carbon atoms (highlighted in red color). However, existing counterfactual reasoners, with the exception of CLEAR Ma et al. (2022). lack the capability to add edges. We address this gap in our proposed method.
Inductive modeling: Several of the existing counterfactual explainers are transductive in nature (See Table i.c., they cannot generate counterfactuals on unseen nodes. As an example, if the model is trained to generate counterfactuals on node e of graph G, it cannot be used to generate counterfact uals on another node of G. Consequently, these transductive models need to be retrained on each node of an input graph. In contrast, an inductive model learns parameters from a train set of nodes, which in turn can be used to predict counterfactual on unseen nodes. In addition, an inductive model is robust to changes in the imput graph due to external factors such as new friend connections in a social network, citations in a citation network, etc. CF² and OE-GNNEXPLAINER cannot be used in an inductive setting for the following reason. These explainers initialize a parameter space based on the number of nodes in the input graph, resulting in an n n weight matrix. Subsequently, this matrix is transformed into a binary n x n mask matrix, which is element-wise multiplied with the original graph's adjacency matrix to denote edge deletion (with Os in the mask indicating deletion). As consequence, the model's parameters are contingent upon the graph's node count, making it infeasible to apply on unseen graphs of varying sizes in an inductive setting,
Contributions: In this work, we develop INDUCE (Inductive Counter-factual Explanations), that addresses the above limitations of cxisting counterfactual reasoners. We propose INDUCE to addresses these challenges and make the following contributions:
Novel formulation: We formulate the novel problem of model-agnostic, inductive counterfactual rea- soning over GNNS for node classification. It is worth noting that both inductive modeling and the ability to add edges introduce non-trivial challenges. In inductive modeling, we need to learn parameters that embodies general rules to be used for predicting counterfactuals. In the transductive approach, since parameters are learned for each specific node, there is no generalization component. Edge additions in- troduce a significant scalability challenge as the number of possible additions grows quadratically to the number of nodes in the graph. In contrast, the number of edge deletions is O(EE), where E the set of edges in the graph. ($ ().
Algorithm: Identifying the smallest number of edge additions removals that alter the prediction is combinatorial optimization problem. We prove that computing the optimal solution to the problem is NP- hard 2 As a heuristic, we learn to solve this combinalorial optimization problem through reinforcement learning powered by policy gradients Williams 1992) 3) Instead of learning the joint distribution over perturbations, the proposed approach sequentially selects the optimal set of perturbations by modeling their marginal effect.
Empirical validation: We show that INDUCE outperforms state-of-the-art algorithms in metrics relevant to counterfactual reasoning. We further analyze the generated counterfactuals and provide compelling evidence that enabling edge additions and modelling the marginal effect of pert urbations impart superior performance. Finally, we also showcase the computation gains obtained due to embracing the inductive paradigm instcad of transductive modelling (8 4
2 Problem Formulation
We use the notation g = (V,E) to denote a graph with node set V and edge set E. We assume each node Ug E V is charactcrized by feature vector x; E Rdd. Furthermore, 1(v) : v - C is a function mapping each node to its true class label drawn from a set C. We assume there exists a GNN & that has been trained G. Given an input node i; E V, we assume (GG,v,)) outputs probability distribution over class labels
4

---

Published in Transactions on Machine Learning Research (05/2024)
C. The predicted class label is therefore the class with the highest probability, which we denote (9, = arg max.ec ( v, c)).
Problem 1 (Counterfactual Reasoning on Gnns) Given input graph G = (V,E), a target node u E V, a GNN model P and an optional set of node pairs Ve = ((0,,y)) Us, Uj E v} between which edges may be perturbed, find the closest graph 9" by minimizing the number of perturbations, such that Lo(g", u) # L) and all perturbed edges are among pairs in Ve.
In real world, may not have control over all perturbations. Ve allows us to specify that. If S EE we restrict to only deletions. On the other hand, if V. n = 0, we only allow additions.
In our problem, we enforce two restrictions on the counterfactual reasoner. First, it should be model-agnostic, i.e, only the output of & is visible to us, but not its parameters. Second, the reasoner should be inductive, which means we should learn a predictive model 11, that can predict the counterfactual graph G given the inputs G, GNN & and target node
Theorem (NP-hardness) Counterfactual reasoning for GNNS, i.e., Prob. 1 is NP-hard.
PROOF. To prove NP-hardness of the problem we reduce from the classical set cover problem.
Definition 1 (Set Cover Feige (1998)) Given a collection of subsets S (S .S.....mm from universe
of items U = {u1,". , identify the smallest collection of subsets A C S covering the set U, i.c.,
A = aig min U S =U IALASS VS:EA
(1)
We show that given any instance of a set cover problem (S, U), it can be mapped to Prob. 1 Specifically, we construct a graph = (V, where V NUSUU. Here, N is an arbitrary set of nodes. In addition, and each item U. There an edge between two nodes
we have a node corresponding Uy E V if e corresponds some set S E S, by corresponds to item u U, and u E S. There are no edges among nodes in N. The GNN & predicts the label of any node N as 1 if all nodes from U are reachable from v, otherwise 0. Furthermore, let the set of allowed perturbations be V. {(v,, vj) e E N, Uj E S). Given any E N, with L v) = 0, the counterfactual reasoner therefore needs to identify the minimum number of edges to add so that all nodes from U are reachable from v through some nodes in S.
each set S
With this construction, only edge additions are allowed. Now it is easy to see that the smallest edge set changing the label of corresponds to connecting nodes in A", where A is the solution for the set cover problem.
Owing to NP-hardness, it is not feasible to identify the closest counterfactual graph in polynomial time. Hence, we aim to design effective heuristics.
3 InduCE
Our goal is to learn an inductive counterfactual reasoning model II, and thus, the proposed algorithm is broken into two phases: training and inference. During training, we learn the parameters of the model IT and during inference, we predict the counterfactual graph using II. Theorem [ prohibiss us from supervised learning since generating training data of ground-truth counterfactuals is harh.rd. Hence, ment learning. Through discounted rewards, reinforcement learning allows us model the combinatorial relationships Khalil et al. (2017) in the perturbation space.
reinforce-
3.1 Learning II as an MDP
Given graph G, we randomly select a subset of vertices from V to train II. Given a target node v, the task of II is to iteratively delete or add edges such that with each perturbation the likelihood of & ()) + @(G v) changes maximally. Here, g* (V,E*) denotes graph 9 after perturbations starting with g G. We
We note that the proof should be confused with the NP-hardness proof in Huang al. (202)) which shows that global counterfactual summarization is NP-hard.
5

---

Published in Transactions on Machine Learning Research (05/2024)
2
Neural Network for Policy Learning
g
G++l
Sample perturbation
Compute
t=0
Start
GAT
MLP
SoftMax
Distribution perturbations
Apply GNN
Update parameters of il through backpropagation based LossfEq.
If label flipoed
No
Yes
8
Figure 3: Pipeline of the policy learning INDUCE. 5 indicates the maximum number of perturbations.
model this task of iterative perturbations as markou decision process (MDP). Specifically, the state captures latent representation of the graph indicative of how would react a perturbation. An action corresponds an edge addition deletion by II. Finally, the reward is function of the number of perturbations, which want to minimize, and the probability of 4G 2) changing following the next action (odge addition or delction), a value that we want to maximize. We next formalize cach of these notions.
State: Intuitively, the state should characterize how likely the class label of the target node v would change following a given action. Towards that end, we observe that a GNN the E-hop neighborhood of Nodes outside this neighborhood do not impact the prediction of a GNN. Motivated by this design of GNNs, the state in our problem is the of node representations in the h-hop neighborhood of the target node v, where ideally h 2 l. Specifically, at time t, the state is:
layers aggregates information from
St {x E N where N = {u e V sp(u, u) s h}
(2)
(3)
Here, sp(v,u) u) denotes the length of the shortest path from v to a in the original graph 9 = (V,E).
The representations of nodes, ie., x are constructed using a combination of semantic, topological, and statistical features.
Original node Fentures: It is common to encounter graphs where nodes are annotated with features labels (recall the definition of x; in $ We retain these features.
Degree Centrality: The higher the degree of node, the more information it receives from its neighbors. Thus, when an edge is added or deleted from the target node to a high-degree node, it may have significant impact on the representation of the target. Based on this observation, we use the degree of a node as part its representation.
Entropy: The entropy of node at time defined = Pe log where Pe = (g', v, c)... The entropy quantifics the uncertainty of the GNN O on given node. We hypothesize that if the + is highly certain (i.e., low entropy) about the class label of some node then any perturbation on u is unlikely to make it change. Similarly, the opposite is true on nodes with high entropy. Due to this information content of entropy, we use it as one of the features in x Class label: Finally, we include the predicted class label of a node, i..., (g u) in the form of one-hot encodings of dimension C.
=
The final reprosentation of node u and time is therefore the concatenation of the above features, i.c.,
x; degree ll et, I| (one-hot (Lo (g*,u)) u)))
Here, || represents the concatenation operator.
Actions: The action space consists of all possible edge deletions in the h-hop neighborhood of target node and additions of edges from to other non-attached nodes in its h-hop neighborhood. Formally, the sets

---

Published in Transactions on Machine Learning Research (05/2024)
are defined follows:
Ex,det = {e e = (4, Uz) E Ex uu, us E EN}
(5)
E
v,add {e (v, & E² uj N
(6)
The action space is the perturbation set:
=i= E U Eo
E
(7)
Reward: Our objective is to change the prodicted label of target node v with the minimum number of perturbations in Aoth in order to find the counterfactual. To capture these intricacies, we formulate the reward of an action a combination of the prediction accuracy of GNN and the number of perturbations made far.
1
L++1 Fupred + g() where
(8)
C Suep
Σ log ( (g', e,,)),
d(c.g))-+11
(9)
YeEC
In simple terms, Lt41 Spree is the log- log-likeldhood of the data predicted by 4 in g++l on v. G++1 the created upon perturbing 9 with action a. / is a hyper-paramctor that regulates how much weight given to log-likclihood of the data vs. the perturbation count. d is the distance function, which in our case is simply the number of edge edits made G time step f.
State Transitions: At time 6, the action corresponds selecting perturbation p' (Recall Eq. from Pb,, ~ (a 5t). We will discuss the computation of Ph.. in $ $.2
3.2 Neural Architecture for Policy Training
To learn Pa.,, we take the representations in Sh, and pass them through neural network comprising of K-layered Graph Attention Network (GAT) (Velčkkvić et al. 2018), an MLP, and final softmax layer. The GAT learns a d-dimensional representation a E R2d for each perturbation a E Pl, is then passed through an Multi-layered Perceptron (MLP) to embed them into a scalar representing their value, which is finally passed over softmax layer to learn distribution over P. The entire network is trainod end-to-end. We next detail each of these components.
GAT: Let Vu Ahh, h2 xt, (Recall Eq In each layer k E [I, we perform the following transformation:
h =
k
W o''
(10)
u,
VV'EAGU
a is an activation function, af are learnable, layer-specific attention weights, and W IRd"- learnable, layer-specific weight matrix where d is the hyper-parametee demoting the representation dimension in hidden layer k. In our implementation, we use LeakyReLU with negative slope 0.01 the activation function. The attention weights are learned through an MLP followed by softmax layer. Specifically,
xat is a
c cu MLP(h || (b))),, ), where ei E R. exp (ct...)
( Ou,a ΣRENZU(H) exp (Cu(i)
After K layers, the GAT outputs the final representation X, h for each node in v's neighborhood. Semantically, given the initial state reprosentation x the GAT enriches them further by merging with topological information. Finally, the representation of an action E pt is set to Xx, ||Y, || ((u, v), where:
f0, E Eha (Recall Eq.
(u,
(11)
{1, 1, El (Recall Eq.
6

---

Published in Transactions on Machine Learning Research (05/2024)
MLP and SoftMax layers: The value of is sa MLP(a), where Sa R. Finally, get distribution over all actions in P as:
exp(sa)
Papy = [Iaa| (. = Exe'p exp((sa)
(12)
3.3 Policy Loss Computation
We iteratively sample an action as per Eq. 12 till either the label changes or we exceed the maximum number of perturbations (which is a rrper-parameter This iterative selection generates a trajectory of perturbations
fai,... , We use the standard loss for policy gradients on T. Williams (1992). More specifically,
we minimize the following loss function:
--- VoEVer
TTll
I(TT) = Ver
1
Σ
Σ E=
log
logr',, (as(s)) nEnt(P))
(13)
Here, Ver CV is the subset of nodes on which the RL policy is being trained. Ent(P!) is the entropy of the current probability distribution over the action space.
Ent(Pt) = Σ
Pap log(pa,")
(14)
VaEP!
By adding the entropy to the loss, we encourage the RI. agent to explore when there high uncertainty. v) a seper-paramete balancing the explore- appore--zplooit trade-off. For simplicity of exposition, we omit the discussion discounted rewards in Eq. 13 Discounted rewards better capture the combinatorial relationship in the perturbation space. Refer to App. for details.
3.4 Training and Inference
Fig. 3 presents the training pipeline. Starting from the original graph, we compute the state representation each iteration The state is passed the neural network to compute a distribution over the perturbation space. A perturbation is sampled from this distribution and the graph is accordingly modified. The GNN @ is then applied on the modified graph. If the label changes or the nunber of perturbation exceeds the maximum limit, we update the policy parameters. Otherwise, we update the state and continue building the perturbation trajectory in the same manner. The pseudocode of the training pipeline is provided in Alg 2 [Refer to App. A)
In INDUCE, each odit involves either adding or deleting an edge. The embedding of such an edge (or action) formed by concatenating the embeddings of its connected nodes. These node embeddings are learned through GAT operating the current graph state. Since GAT is inherently inductive-meaninn their parameter set is invariant to changes in graph size - Induce inherits this property. This is demonstrated in Eq. 10 where the parameter set dimension is bounded by W E Baaa 1xa" Here, d signifies the hidden dimension in layer A and is independent of the graph size. In essence, the embedding of an action (such as edge addition or deletion) is influenced by the local ε-hop neighborhood surrounding the two nodes involved in the edit. Consequently, even when presented with an unseen graph, as long as the training data contains similar distributions of neighborhood topologies, the predictive accuracy of INDUCE remains robust.
Inductive inference:
Alg. presents the pseudocode of the inference pipeline. We iteratively make forward passes till the label changes or exceed the budget. The forward pass is identical to the training phase with the only exception being deterministically choose the perturbation with the highest likelihood instead of sampling.
Transductive Inference:
This phase proceeds identical to the training phase with the only exception that we learn a target node specific policy instead of one that generalizes across all nodes.
3.5 Complexity of InduCE
Train-Phase: Training the policy network involves four key steps, i.c., compute the state, forward pass through the policy network, sample and take action, and compute the marginal reward of the action. Among
8

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 1 Test pipeline of INDUCE.
Input: Graph G, GNN Φ; larget node v; maximum perturbation budget
Output: Counterfactual explanations CF
1: CF =
2: parameters pre-trained policy
3: f
4: while Lg(g9, v) = (g v) t < do
5: compute St.
6: a" f- pa I Pt)
7: gt+1 perturb o with edge a
8: tet+1
9:
Lg(g", + Lg v) then
10: CF (F
Return CF
the above, stale computation and performing the action take ((1) time. Time taken by a forward pass through the policy network involves a combination of computing node embeddings using GAT and computing score for each action in the action space p through the MLP. Forward pass through the GAT takes (1
(Velččković et al. 2018) where K, h2 and ha are the number of GAT layers, imput and hidden dimensions respectively. Action score computation using MLP takes ((PP()m (ha + (J - 2m + 1))); J and Am are number of MLP layers and hidden dimensions. Computing the reward function involves taking a forward pass through a GCN which takes E(L (habha(C) time, here L and |C] are the number of layers and number of classes respectively. The above steps are repeated for M episodes for each node in training set Ver until a maximum of time steps. Combining the above costs, treating J, K, L,, his has hm and [C] as fixed constants which have small values, and with the knowledge that [P4] [(V) + (εl) (refer Eq. 7 the complexity with respect to the input. parameters reduces
[ [&)))
Test-Phaser The test phase involves state computation, forward pass through the policy network, and performing the action with highest probability for a maximum of 5 time-steps for every node in the test set Veest- Therefore following the discussion in the training phase, the time complexity of test phase is keet
(([))) (6([)) (8))).
4 Experiments
In this section, we benchmark INDUCE against established baselines. The anonymized code base and datasets used in our evaluation are submitted with supplementary matcrial. The hardware and software platform details are provided in App. D
4.1
Datasets
Tree-Cycles
Tree-Grid
BA-Shapes
Amazon
ogbn-arxiv
# Classes
4
6
40
# Nodes
871
1231
700
397
169,341
# Edges
1950
3410
4100
2700
1,166,243
Motif size nodes)
6
5
NA
NA
Motif size (# edges)
6
12
6
NA
NA
Nodes from motifs
360
720
100
NA
NA
Avg node degree
2.23
2.77
5.86
15.90
6.80
Table 2: The statistics of the benchmark datasets.
Benchmark Datasets: We use the same three benchmark graph datasets used in Tan et al. 2022 Lin
et al. (2021); Lucic et al. (2022). Statistics of these datasets are listed in Table 2 Each dataset has an undirected base graph with pre-defined motifs attached to random nodes of the base graph, and randomly added additional edges to the overall graph. The class label of a node indicates whether it is part of a node or not. Further details on the datasets are provided in App. D.1
Real Dataset: We additionally use real-world datasets from the Amazon-photos co-purchase net- work Shchur al. (0018) and ogbn-arxiv Wang et al. 2020 In the Amazon dataset, each node corresponds

---

Published in Transactions on Machine Learning Research (05/2024)
Tree-Cycles
Trep-Grid
BA-Shapes
Fid.(%)
Size 1
Acc.(%6]
(%d.
Size
Acc.(%))
Fld.
Size >
Acc.(%a]7
Random
67.08
283 4-272.76
15.57
CP-GanEx
49.0
1.05 +0.23
100
10
1.37 +0.58
92.24
37.0
1.31 +0.55
95.83
Cr
+1.89
68
98.45
+1.5
70.54
InduCE
1.01 =0.12
99.61
1.02 +0.12
97.67
0
1.30
+:0.90
95.31
(trans.)
CR-GanEx ++
100
NULL
NULL
100
NULLI 1.24 +0.43
NULL
38.16
6311544
+-9016.50
17.96
CF
100
NULL 83.22
InduCK (trans.)
1.40 +1.49
81.94
92.64
6.6
1:42 +:144
Table 3: Results for transductive methods: Lower fidelity, smaller size, and higher accuracy are desired. "NULL" denotes that the method could not produce counterfactual. The best results in bold. Tr., Fid., Acc. denote transductive, fidelity and accuracy, respectively. The best result in each category is highlighted in bold. The second best in each category is underlined.
a product, edges correspond products that are frequently co-purchased, node features encode bag-of- words from product reviews and the node class label indicates the product category. The ogbn-arxiv dataset is citation network. The nodes are all computer science arXiv papers indexed by MAG Wang al. (2020) Each directed edge represents that and the abstract computed by the skip-gram model Mikolov et al. (2013). The labels are subject arcas. Since the class labels in these datasets are not based on presence or absence of motifs, the corresponding cells in Table are marked as "NA"
paper cites another. The features are word embeddings of the title
4.2 Baselines
We benchmark INDUCE against the state-of-the-art baselines of (1) CF- GIINGNNEEEELNNE Lucic al. (0022)
(2) CF2 Tan et al. (2022), (3) RCEXPLAINER Bajaj et al. (2021) and (4) CLEAR Ma et al (022)) In addition, we also compare against the state-of-the-att factual explainers (5) PGEXPLAINER Luo al. (020)) and (6) GEM (Lin et al.] 2021) to show that when factual explainers are used for counter-factual reasoning by removing the factual explanation (subgraph) from the input graph, they are not effective. This is consistent with prior reported literature Lucic et al. (2022); Tan et al. (2022); Lin et al. (202I). Finally, we also compare against (5) RANDOM perturbations. While CF2 and CF-GNNEXPLAINER are transductive, RCEXPLAINER, CLEAR, GEM and PGEXPLAINER are inductive. The codebase of all algorithms, except RCEXPLAINER (Refer App. [] have been obtained from the respective authors. We provide the hyper- parameter settings for all the baselines in the App D.2 A detailed analysis of how the parameters affect the performance of INDUCE is provided in App.
4.3 Performance Measures
To quantify performance, we use the standard measures from the literature Lucic et al. 2022
Fidelity the percentage nodes whose labels do not change when the edges produced by the explainer (algorithm) are perturbed. Lower fidelity better. Furthermore, it may argued that fidelity is the most important metric among the three measures.
Fidelity:
Size: Explanation size is the number of edges perturbed for given node. Lower size is better. Accuracy: Accuracy is the percentage of explanations that are correct. As standard in CF2,CF- GNNEXPLAINER, and GEM, this translates to the percentage of edges in the counterfactual that belong to the motif. Since nodes have non-zero class label only if they belong to motif, the explanation for nodes should be edges in the motif itsolf. Note that accuracy computable only on the benchmark datasets since they include ground-truth explanations.
Sparsity: Sparsity is inversely related size. We present the definition and results in App. space constraints.
D due
Other settings: Details of experimental settings, the black-box GNN, training and inference are in App. D.3
10

---

Published in Transactions on Machine Learning Research (05/2024)
Method
Cycl-Cylls
Trea-Grid
BA-Shapes
(id.
Slzc
A7c. 1
Fld.(%)
Size
Acc.(%%)
Fid.(%)
Size 4
Acc.
PGExplainer
34.72
76.85
41.09
66.93
6.58
89.25
Gem
95
86.97
97
91.57
17
98.44
RCExplainer
61
1.0
=0.0
70.73
100
NULL
NULL
NA
NA
NA
Clear
56.94
47.92
+-21.84
86.17
184. 16 +34.22
96.34
DNS
DNS
DNS
InduCE (Ind.)
1:44
96.57
4.67 4:2.91
91.05
2.6
4.37 +3.53
InduCE (Ind.)
36.3
1.67
0.90
90:32
16.3
6.38 33.74
86.31
40.8
3.37
1:300
56.08
Table 4: Results for inductive methods. The best result in each category is highlighted in bold. The
second best each calegory is underlined. "DNS' denotes that the method did not scale "NA" means not applicable as RCEXPLAINER code did not extend to multi-class setting.
4.4 Quantitative Results
Transductive methods: Table g presents the results (for now, we will focus on the first four rows). Our method INDUCE in the transductive setting outperforms all the baselines almost all sottings. For Tree-Cycles and BA-Shapes, CF-GNNEXPLAINNER is producing better accuracy. However, we note that its fidelity is much worse, indicating it fails to find an explanation more frequently. While CF-GNNEXPLAINER consistently achieves the lowest size among the baselines, its fidelity is much worse. This indicates that DF-GNNEXPLAINER is able to solve only the easy cases and hence the low size is deceptive as it did not solve the difficult ones.
Table | shows that INDUCE is superior to GEM and PGEXPLAINER in most cases. The fidelity scores produced by GEM and PGEXPLAINER are much higher (worse). This indicates, in most of the cases, GEM and PGEXPLAINER are unable to find a counterfactual example. Also the explanation size is fixed in GEM and PGEXPLAINER since they work with fixed budgets. CLEAR performs worst in terms of average explanation size. This defeats the purpose of counterfactual explanations since the perturbations should be minimal so that the instance just crosses the decision boundary. This is necessary to make the explanations human-intelligible as well. It. has non-zero fidelity as it significantly perturbs the target nodes' local neighbourhoods, hence leading to a change the predicted labels. The high accuracy possibly due a large number of edge additions but meaningless in the face of significantly large counterfactual size. Moreover, it does not scale for the dense datasets, BA-Shapes. Conclusively, generative modelling used by CLEAR, leads to complex explanations owing to large edits in the graph structure. Thus, modelling the marginal impact of perturbations through policy gradients is effective approach. RCEXPLAINER did not extend to multi-class setting. It has high fidelity, low size and accuracy, indicating that it only finds counterfactuals for easy cases.
Inductive methods:
Transductive vs Inductive: We further compare the inductive version (Table 4 of our method, INDUCE with the transductive baselines (Table 3). While the transductive methods have a clear advantage of re- training the model instance wise, the results produced by INDuCIB-induetive are comparable. As noted earlier, although CF-GNNEXPLAINER achieves better size than indicating that the low size: is a manilestation ion of not being able to explain the hard cases that INDUCE is able to explain. Moreover, in addition to the ability to generalize to unseen nodes, inductive modeling also imparts a dramatic speed-up in generating explanations (see Table 6a).
its fidelity is much worse
Impact of motif topology: The complexity of the motif topology, along with the inherent difficulty of the prediction task, significantly influences the prediction accuracy of the GNN being explained and hence also alfects the explainer. Specifically, when the GNN'S predictions are poor due to the complexity of the task, there may be inherent uncertainty in the model functionality. This uncertainty explainer, as it must contend with ambiguity and variability in the model being explained when proposing counterfactual explanations. The explainer may struggle to provide confident and reliable explanations in the face of such uncertainty, leading to potentially inconsistent or unreliable results.
pose challenges for the
Furthermore, the larger the size of the motif, the more is the expected size of the explanation to make a non-motif node part of a motif. This trend is visible in Table A where the explanation size of Induce is largest. for Tree-grid dataset, where the motif consists of 9 edges.
11

---

Published in Transactions on Machine Learning Research (05/2024)
Finally, the shape also plays role. The expressivity of message-passing GNN is bounded by 1-WL tests Xu et al. (019)). Tf the GNN cannot distinguish between two shapes, this ambiguity will be passed on to the explainer as well.
Additional experiments: App. contains experiments on the impact of (1) heuristic features and (2)
the choice of GNN architectures. Experiments on counterfactual size vs accuracy trade-off are App.
Addition letion
Addition
Number of exanppes
examples
60
Delction
80
15
20
20
Counterfactual
Counterfactual
(a) Inductive
(b)
Transductive
Figure 4: The distributions of the edit size and their internal composition of edge additions and deletions
by INDUCE on the Tree- Cycles dataset.
4.5 Impact of Edge Additions
We seek answers to two key questions: (1) How much does the performance of INDUCE deteriorate if we restrict odge additions? (2) If we empower the basclines also with additions, do they match up to INDUCE? To answer the first question, we study the performance of INDUCE in the setting where only edge deletions are allowed. The rows corresponding to INDUCE (transductive)- -- and INDUCE (inductive) in Tables 3 and | present these results. It evident that the deletion-only version produces inferior results for both the transductive and inductive versions. In Fig. 4 further study the frequency distribution of edge additions and deletions in the counter-factual explanations produced by INDUCE in Tree-Cycles dataset (results on other datasets are in App. Gb. We observe that additions dominate the perturbations, and thereby, further establishing its importance, which INDUCE unleashes. To address the second question, we empower CF- GNNEXPLAINER and CF² with edge additions, denoted as UFF-GNEXXPLAINE ++ and CF2 ++ respectively. Both CF2 and BF--GNEXXPLAINE use a mask-based strategy. A mask learnable binary matrix of the ε-hop neighborhood of the target node. By taking an clement-wist product of the mask with the adjacency matrix, one obtains the edges to be deleted. When empowered with additions, the mask itself becomes the new adjacency matrix. Surprisingly, the performance of EER-GNNEXPLAINE drops, while for CF², we see improvement in fidelity in two out of three datascts. Further investigation into this performance reveals that edge additions significantly increase the search space of possible pert perturbations (See Table D in Appendix). mask- based strategy is a single-shot learnable paradigm that does not examine the marginal effect of each perturbation. When the perturbation space increases, it overwhelms the learning procedure. In contrast, INDUCE uses reinforcement learning where a trajectory perturbations is selected based their marginal gains. This allows better modeling of the combinatorial nature of counterfactual reasoning. Overall, the above experiments reveal that both additions, well as algorithm equipped to model large combinatorial spaces, are required to perform well.
the same dimension
4.6 Impact of Modeling Marginal Impact
INDUCE adopts an auto-regressive framework where the selection of edits depends on previously selected edits. This design is adopted since, as established in Theorem [ counterfactual reasoning is a combinatorial problem. What hoppens if we ignore modeling the marginal impact of edits? We investigate this aspect
2GEM is not extendible additions (See App. D.2 for details); PGEXPIAINER does incorporate perturbations with the intent. of changing the lahel since is factual explainer.
12

---

Published in Transactions on Machine Learning Research (05/2024)
100
90
Single-shot Marginal
Relative Change in Entray
0.02
Max Possible Jaccard
0.8
70
0.00
60
50
-0.02
Ria
Jaccard
40
0.4
30
-0.04
20
0.2
10
-0.06
1
0.0
Counterfactual Size (k)
Counterfactual Size/elterations
Counterfactual Size/etterations
(a) Single-shot vs. iterative
(b) Evolution entropy
(c) Evolution of ranking
Figure 5: (a) Fidelity comparison of INDUCE with single-shot prediction on the BA-Shapes dataset. In
single-shot prediction, we select the edits with highest predicted reward directly. Recall that lower fidelity is better. (b) Evolution the entropy of the score distribution over perturbation space against the number of iterations (explanation size). (c) Evolution of the top-5 highest scoring edits against the number of iterations (explanation size).
As visible, INDUCE achieves significantly lower fidelity than its single-shol counterpart, thus emphasizing the importance of modeling the marginal impact of edits. In single-shot prediction, we directly add the top-k edits with the highest expected reward based on the original graph state. This contrasts with the auto-regressive pipeline where a single edit with the highest expected reward first added to the original graph, and then all available edits are re-prioritized based their expected rewards the edited graph. To ensure fair comparison, k in the single-shot approach is set to the number of edits made by INDUCE until the node label changes.
in Fig. 5a
We next analyze the evolution of the entropy of the perturbation space in Fig. 5b entropy indicating consolidation of perturbation preference till a certain number of iterations, beyond which, it starts to increase again. This trend is not entirely surprising, since a higher number of iterations indicates that INDUCE has failed to change the label of the target node despite significant number of edits, and such cases correspond to higher amount of uncertainty
We note a decrease in
How does the ranking of the edils based on their expected rewards change over ileralions? Fig. 5c analyzes this question. Specifically, we compute the top-k highest ranked edits at each timestep t, starting from t = 0, and compute its Jaccard similarity to the top-k list at + 1. Note that since we select the highest ranked edit each timestep, and therefore this edit cannot be present in the next timestep, the maximum Jaccard similarity between the lists at two consecutive time steps is (k: 1)/(k + 1). In Fig. 50 we note that the Jaccard similarity consistently lower than this upper bound, indicating that the ranking list is evolving over time. & is set to 5 in this analysis. Connecting back to Fig. 5a this further highlights the need for modelling perturbations marginally instead of single-shot.
4.7 Quantitative Results on Real Datasets
ogbn-
Method
Fid.(%) I
Size
Fid.(%)
Size
CF-GnnEx
100
NULL
DNS DNS 0
DNS
Cr2
60
13.7
16.98
DNS
InduCE (trans.)
53.50
4.72
+ 4.38
1.00
0.00
Table 5: Results for transductive methods on the real-world dataset. "NULL" denotes that the method could not produce a counterfactual. "DNS" denotes that the method could not produce a counterfactual it did not scale. Refer to App. that details reasons on why these basclines failed to scalc.
In Tables 5a and 5b, we present the results of INDUCE and other basclines on the real-world datasets. Consistent with the performance on benchmark datasets, INDUCE continues outperform all the basclines almost. in both transductive and inductive settings. We note that most of the baselines failed to produce
13

---

Published in Transactions on Machine Learning Research (05/2024)
Method
Amazon
ogbn-arxiv
(id.(%) 4
Size
(%d.(%)
Size J
PGExplainer
100
NULL
96.50
4
Gem
100
NULL
DNS
DNS
Clear
DNS
DNS
DNS
DNS
InduCE (ind.)
93.00
6.60
2.87
78.7
3.11 43.04
Table 6: Results for inductive methods on the real-world dataset. "NULL" denotes that the method could not produce a counterfactual. "DNS" denotes that the method could not produce a counterfactual as did not scale. Refer to App. that details reasons on why these baselines failed to scale.
Method
Tree-Cycle Tree-Grid
BA-Shapes
PGExplainer
0.41
0.62
0.38
Gem
0.16
0.73
8.61
CF-GnnEx
1295.66
2382.51
3964.36
Cf = 0.G)
304.13
154.88
2627.09
RCExplainer
0.76
1.42
NA
CLEAR
0.06
0.10
DNS
InduCE (ind.)
4.36
17.64
InduCE (traus.)
66.08
331.58
6546.48
Efficiency
Dataset
NNoes
#Edges
Avg. degree
Time/non noode (ms)
Tree-Cycles
871
1,950
2.23
60.56
Tree-Gris Grid
1,231
3,410
2.77
13.67
BA-Shapes
700
4,100
5.86
89.91
ogbn-arxiv
169,343
1,166.243
6.89
353.43
Amazon-photos
7,487
119,043
15.90
5242.32
(b) Scalability
Table 7: (a) Running times (in seconds) of each algorithm on entire test set. (b) Scalability against various graph properties. "DNS' denotes that the method did not scale. RCEXPLAINER code does not extend to multi-class setting, we denote this as "NA"
counterfactuals in Amazon, while CLEAR fails to scale. In ogbn-arxiv, on the other hand, all baselines except PGEXPLAINER fails to scale; they crash with out-of-memory exception. In contrast, INDUCE produces promising performance with the transductive version achieving 0% fidelity.
4.8 Efficiency
Table 6a presents the inference times of various algorithms. First, the inductive methods (INDUCE, CLEAR, RCEXPLAINER, PGEXPLAINER and GEM) are much faster than the others. Between the inductive methods, PGEXPLAINER and CLEAR are the fastest. InDuCE-inductive is slower since the search space for INDUCE: is larger due to accounting for both edge additions and deletions. CLEAR is significantly faster than INDUcE-inductive because it generates a perturbed adjacency matrix for the input graph rather than modelling the marginal effect of edge perturbations. It should be noted that CLEAR performs significantly worse quantitative metries and does not scale for dense and large datasets (Recall Table 4.. Socond, InnuCE-indeetive GNNEXPLAINER and Cr², This speed-up network, whereas, transductive methods learn the model parameters each node separately. Even the transductive version of INDUCE is faster than the other transductive methods for Tree- Cycles and Tree-Grid.
up to 79 times faster than the transductive methods such as CF-
result of only doing forward passes through the neural policy
Scalability against graph size: Table 6b presents the inference time per node across all datasets. We observe that INDUCE, scales million-sized networks such as ogbn-arxiv. We observe that the growth of the running time is closely correlated with the neighbourhood density, i.c., the average degree of the graph, and not the graph size. In GNN with l layers, only the 8-hop neighborhood of the target node matters.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Mutagenicity
Mutag
AIDS
Method
Fid.(%)
Size
Fid.(%)
Size !
Fid.(%)
Size
Cf
38.7
2.87 #1.36
88.2
1.25 #0.43
98.5
4.83 12.19
InduCE (trans.)
20.2
1.30 =0.81
1.35 +0.61
67.8
4.61 =2.38
RCExplainer
39.2
1.02 20.25
47.1
2.72 +3.4
91.2
1.0 #0.0
Clear
OOM
0OM
64.7
16.08 +6.3
86.2
296.36
+:36.57
InduCE (ind.)
45.1
5.32
#3.85
20.60
5.0
#3.42
91.20
8.91 #3.91
Table 8: Results on graph classification. The best result in each category is highlighted in bold. The second best in each category is underlined.
4.9 Case Study: Coutter-factual Visualization
INDUCTIVE
2XBB-CYCL88
TREE-GRID
HOPEP
OPGIMExpla Lenn
(7'2(=-0)
FREE-CYCLES
JA SHAPEH
(a) Tree-Cycles
(b) Imupcct of additions
Figure 6: Visualization of counterfactual explanations for the same node (orange) produced by different methods. Semantically, the node label should change if it is not part of the motif. (a) Counterfactual
explanation for Tree-Cycles Dataset, (b) Counterfactuals predicted by INDUCE.
In this section, we visually showcase how counterfactual explanations reveal GNN vulnerabílities and the importance of edge additions.
Revealing GNN vulnerabilities: A sample counterfactual explanation by various algorithms on Tree- Cycles dataset is provided in Fig. 6a The target node is part of motif (6-cyele) and therefore the expected counter-factual explanation is to make it non-member of a 6-cycle. CF-GNNEXPLLAINER correctly finds such explanation by deleting an edge. Both GEM and CF2 recommend a much larger explanation than necessary. In contrast, INDUCE adds an edge. More interestingly, the target node continues to remain part of the motif. This uncovers a limitation of GNN since it falsely classifies the target node as a non-mott node although is not. Furthermore, this limitation is uncovered only since INDUCE can add edges. Similar observations in other datasets are available in Figs. Ga Gb in Appendix.
Impact of additions: In Fig. 6b top-left, we share example where INDUCE changes the label of target node (orange) by making it part of a cycle through edge additions. Since basclines are only capable of deletes, they fail to change the label of such nodes. However, INDUCE highlights that the GNN does not learn cycle-motifs of specific lengths. In the top-right (Tree-Grid), INDUCE breaks the grid motif and connects the target node (orange) to a non-motif neighbour, hence colluding its embeddings and changing its label. These examples show the importance of edge addition to intuitively explain how the black-box GNN works.
4.10 Performance on Graph Classification
While our focus is on explaining node classification, INDUCE can be generalized to graph classification as well. To adapt INDUCE pipeline for explaining graph classification, we use the entire graph to construct the MDP state instcad of the (-hop neighborhood of the target node. Morcover, the action space defined by all pairs of nodes in the graph since there is no notion of a target node. The rest of the pipeline remains unchanged.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Table 8 presents the results on graph classification explainability on the Mutagenicity Riesen & Bunke (2008) Kazius et al. (2005), Mutag Tvanov et al. (2019) and ATDS Tvanov et al. (2019) datasets. As visible Induce- transductive achieves the best fidelity, while being marginally higher in explanation size, when compared to the smallest size achieved by any of the baselines.
5
Concluding Insights
Despite being a black-box, Graph neural networks (GNNS) are becoming the go-to tool for topological data analysis due to their superlative prediction accuracy. The ability to explain predictions is critical towards making a model trustworthy. In this work, we proposed INDUCE understand GNNS via counterfactual reasoning for the node classification task. While several algorithms in the literature produce counterfactual explanations of GNNS, they suffer from restricted inefficient counterfactual space exploration and trans- ductivity. INDUCE provides a boost to counterfactual analysis GNNS by unleashing the power of edge additions, efficient exploration of the combinatorial scarch space through marginal rewards and inductively predicting explanations on unseen nodes. The proposed features not only lead to better explanations but also provide significant speed-up allowing INDUCE to perform counterfactual analysis at scale.
References
Carlo Abrate and Francesco Bonchi. Counterfactual graphs for explainable classification of brain networks. In KDD, pp. 2495-2504, 2021.
Steve Azzolin, Antonio Longa, Pictro Barbiero, Pictro Lio, and Andrea Passcrini. Global explainability of GNNs via logic combination of learned concepts. In The Fleventh International Conference on Learning Representations, 2023. URL https: htttss///penrreiew..rr httprrrrrree..ee///oudnd-dd----e -rooum?iddOURRRIYYY
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang, Robust counterfactual explanations graph neural networks. In A. Beygekzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: tGs7N54M
Uriel Foige. threshold of in n for approximating set cover. Journal of the ACM (JACM), 45(4))634-65 652, 1998.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint Xrv: 1903. 02428, 2019.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
Zexi Huang, Mert Kosan, Sourav Modya, Sayan Ramu, and Ambuj Singh. Global counterfactual explainer for graph neural networks. Tn Proceedings of the Sizleenth ACM International Conference on Web Search and Data Mining, pp. 141-149, 2023.
Sorgei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. Geometric Learning and Graph Representations ICLR Workshop, 2019.
Mingjian Jiang, Zhen Li, Shugang Zhang, Shuang Wang, Xiaofeng Wang, Qing Yuan, and Zhiqiang Wei. Drug-tare affinity prediction using graph neural network and contact maps. RSC advances, 10(35): 20701-20712, 2020.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1):312-322 2005.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
16

---

Published in Transactions on Machine Learning Research (05/2024)
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint Xiv: 1609. 02907, 2016.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In International Conference on Machine Learning, pp. 6666 6669.667. PMLR, 2021.
Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cf- gnnexplainer: Counterfactual explanations for graph neural networks. In AISTATS, pp- 4499-4511, 2022.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haileng Chen, and Xiang Zhang. Pa- rameterized explainer for graph neural network. Advances in neural information processing systems, 33: 19620-19631, 2020.
Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. Clear: Generative counterfactual explanations on graphs. Advances Neural Information Processing Systems, 35:25895-25907, 2022.
Tomas Mikolov, Πlya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compasitionality. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Newral Information Processing Systems, vol- ume 26. Curran Associates, Inc., 2013. URL
pepper flesspaper /aopp/rr/203///// 013/file/
Papper..pd
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe W. J. Jiang, Ebrahim M. Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Anand Babu, Quoe V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean. Chip placement with deep reinforcement learning. CoRR, abs/2004.10746, 2020.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 287-297. Springer, 2008.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced ex- plainer for graph neural networks. In NewrIPS 2021, December 2021. URL http:////www.mmooofff..cco gt-uus/reearrd//uullcttooo wwwnfoorrreeeetteeerrriieiiin httpae/weww...negeoaaaoddeeeeeee for for-neerr----rr-------- nerappi--nuurll--ntwwrrsss
enhanced
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXio preprint arXiv:181 1.05868, 2018.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In 27th International Conference on Artificial Neural Networks (ICANN), 2018.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Raii Ruizi, Nina M Donghia, Craig R MacNair, Shawn French, Lindscy A Carfrac, Zohar Bloom-Ackermann, et al. A deep learning approach to antibiotic discovery. Cell, 180(4))688-700) 702, 2020.
Juntao Tan, Shijic Geng, Zuohmi Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, WWW '22 pp.
2022.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.
Graph attention networks. In International Conference on Learning Representations, 2018. URL https:
//ooenneview.nnet/ooumm http:/oorrommmdddddppipc.
Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152676):10 5555, 2017.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong, and Anshul Kanakia. Mi- crosoft Academic Graph: When experts are not enough. Quantitative Science Studies, 1(1):396-413, 02 2020.
17

---

Published in Transactions on Machine Learning Research (05/2024)
Geemi P Wellawatte, Aditi Seshadri, and Andrew D White. Model agnostic generation of counterfactual explanations for molecules. Chemical science, (3(13):3697-3700) 2022.
Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning.
Mach. Learn., 8(3 4):229 256, may 1992. TSSN 0885-6125. doi: 10.1007/BF0099220 URL https:/ doi.org/ 10.1000 2001000//F009966000 BF00992696
Jiacheng Xiong, Zhaoping Xiong, Kaixian Chen, Hualiang Jiang, and Mingyue Zheng. Graph neural networks for automated de novo drug design. Drug Discovery Today, 26(():13822133) 13393, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Represenlations, 2019. URL https: ryGs6iA5Km
Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Liò. Global concept- based interpretability for graph neural networks via neuron analysis. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Sympostum on Educational Advances in Artificial Intelligence, 2AAT23/TAAT23/ E.A AAAT Press, 2023. ISBN 978-1-57735-880-00 doi: 10.1609 106992aai.v3711) 262677.
URL httpp://doi..rrg 10. 1609/ aat.0///aai.v371.22220.. v3719.26267
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, pp. 974-983, 2018.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, 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. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 430 438, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Lú, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, 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 Pottern Analysis and Machine Intelligence, 2022.
18

---

Published in Transactions on Machine Learning Research (05/2024)
Dataset
k-hop
#additions
#deletions
ratio (#addittons//Hdeleeiinn
Tree-cycles
18313
1105
16.57
Tree-grid
98942
3960
24.98
BA-shapes
3140886
17580
66.01
Amazon-Photos
12144800
432160
28.10
ogbg-arxiv
354496362
524330
676.09
Table Ratio of no. additions to deletions datasets.
HOLLY
30007208
CreNNExplainer
CF 21-2000
DELATION
CPGNssxpleiner
C2'2(a-0)
(a) Tree-Grid
(b) BA-Shapes
Figure G: Visualization of counterfactual explanations for the same node (orange) produced by different methods. Semantically, the node label should change it not part of the motif, i.e., (a) 3 3-grid, and the (b) the house respectively. CF-GNNEXPPLANEE is unable to find counterfactual in (b).
A Appendix
A InduCE Training
The training pipeline of INDUCE is given in Algorithm 2
B Discounted Rewards
The objective of the policy II is to find minimal counterfactual explanations for GNNs using the reward can observe that in that equation, the marginal reward at each function mentioned in Eq 10. However, step is given equal weight. In our case, we want the immediate rewards to have higher weight over the rewards encountered later on in the perturbation trajectory T. in order to penalize larger counterfactual size, thus we use discounted rewards (Eq 15 with y being the discount factor to achieve the objective. Since we want minimal explanation size, we use small values of y (Refer App. D.3)
(at) Σ y Z' (ar)
(15)
here d is the maximum perturbation budget. One limitation of policy gradient is high variance caused by the scale of rewards. A common way to reduce variance is to subtract baseline, b(S))) such that it does not induce bias in the policy gradient. A simple baseline can be the mean of the discounted rewards, so that we train the policy to pick trajectories that give rewards better than the average rewards. We also normalize the discounted reward further by dividing with the standard deviation.
Rice, (a:) Rtt (at) max Ri (at)); c)
R'
(16)
19

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 2 Training pipeline of INDUCE.
Input: Graph G, 4, Train Vizi perturbation budget 6, number episodes Output: Policy II
1: Vbatch (V1, Va ..... Vel Uf V+r]
Random partitioning instances of into B batches
2: II - initialize with random parametere
3: for
do
4:
for all V. E Voutoh do
for all u V4, do
6:
7:
while (00 n) = (G' 1) & 1 do
8:
compute S
9:
a' sample from II(S P!)
10:
G
perturh 6 with edge a²
11:
R.
compute reward using Eq
12:
R deso compute discounted rewards using Eq 16
13:
R din
normalize discounted rewards using
15:
Backpropagate minimize loss using Eq.
16: Return
Dataset
Train accuracy(%) (%)
Test Accuracy (%)
Tree-cycles
91.23
90.86
Tree-grid
84.34
87.44
BA-shapes
96.61
98.57
Amazon-Photor
89.59
88.75
ogbn-arxiv
71.59
55.07
Mutagenicity
85.37
85.38
Mutag
90.84
87.18
AIDS
99.57
99.25
Table J: Accuracy of GNN & on datasets used in this study.
where (R is the standard deviation, e is constant. The optimized version of the loss function (Eq 13 is in App.
C Batching
13 takes an average gradient over all examples the training set. This setting may lead to over-smoothing of the gradients and hence induce difficulty in training. To counter this issue, we performed batching of node instances, and back-propagated with the average gradients computed on nodes in the batch. Thus we optimize our policy on batches of nodes, and normalized discounted rewards in the loss function (Refer Eq. 17
Equation
Tul Σ logri, (ar) vEnt(p!)
Σ
J(M)
(17)
Vontoh
Vog VhaVaatc
Experimental Setup
All reported experiments are conducted on an NVIDIA DGX Station with four V100 GPU cards having 128GB GPU memory, 256GB RAM, and a 20 core Intel Xeon E5-2698 v4 2.2 Ghz CPU running in Ubuntu 18.04.
20

---

Published in Transactions on Machine Learning Research (05/2024)
D.1 Benchmark datasets
The base graph is a Barabasi-Albert (BA) graph. The motifs are house-shaped struc- tures made up of nodes (Refer Figure Gbj. Non-motif nodes are assigned class 0, while nodes at the top, middle, and bottom of the motif are assigned classes 1, 2, and 3, respectively.
BA-SHAPES:
TREE-CYCLES: The base graph is binary tree with 6-node cycles used as motifs (Refer Figure baI. The motifs are connected to random nodes in the tree. Non-motif nodes are labelled 0, while the motif nodes are labelled 1.
TREE-GRID; The basc graph is a binary tree and the motif is a 3 x 3 grid connected to random tree nodes (Refer Figure Gal. Just like tree-cycles dataset binary class labelling has been done.
D.2 Baselines
CF-GnnExplainer Lucic et al. (2022) Being transductive method for counterfactual explanations, it learns a new set of parameters for every node and cannot be used to explain unseen nodes. We use the default hyperparameters used by the authors.
2f Tan et al. (2022): While being transductive in nature, it combines both counterfactual and factual properties to give an explanation. Cr² tunes the parameter a to weigh the contribution of factual explanations. We compare CF² with = 0 where it becomes as counterfactual explainer.
Gem Lin et al. (2021): This is inductive by nature, however, it only considers edge deletions. It has a limitation that it learns factual explanation model where the number of perturbations fixed, ie., it does not minimize the number of perturbations with the sole focus on changing the label. We use the default size of 6 the perturbation size as recommended by the authors.
Note that GEM is not extendable to include edge additions. Specifically, GEM has distillation process that generates the ground truth. Distillation involves removing every edge in node's neighbourhood itcratively and seeing its effect on the loss. The delctions are then sorted based on their effect on the loss. The lop-k edges (k is user-specified) are used as the distilled ground truth. The explainer is later trained to generate graphs that are the same as the distilled ground truth. To extend this process for additions, the number of possible edge edits is significantly higher and the iterative process of GEM create the distilled ground truth does not scale. In addition, it is also unclear how to set in the presence of additions.
PGExplainer Luo et al. 2020); This method is also inductive and only considers edge deletions. It is factual explainability method and requires a fixed explanation size as a hyper-parameter. We use the default size of 6 as the perturbation size as recommended by the authors for the benchmark datasets. We also use size 6 and 4 for Himazon-Photorn and ogbn-arxiv, respectively.
RCExplainer Bajaj et al.] (2021): This method learns explanations that are stable when the input graph is minimally perturbed. The method is inductive and combines, both counterfactual and factual properties. The method has hyper-parameter À which is used to weigh the contribution of the factual explanations. We set À = 0 for comparison of methods in the counterfactual setting.
Clear Ma et al. 2022): CLEAR is an inductive, generative counterfactual explainer. It is capable of node addition or deletion, node feature perturbation and edge additions as well as deletions. The authors' code prioritizos graph classification explainability. We adapt it for node classification by using k-hop ego networks for target nodes and training the explanater on these networks. We use the authors' default hyperparameters.
CLEAR, along with all other basclines do not model the marginal impact of perturbations, which empiri- cally produces better explanations (Refer Table 4 6). due to the muanced exploration of the combinatorial search space.
Random: We use the same baseline as used in Lucic et al. (002)). It makes the choices of deleting an edge randomly by generating a random subgraph mask for the h-hop neighbourhood of the node and perturbing it.
D.3 Training and Parameters
We provide a node that is part of motif to the counterfactual explainer, and the the task is to change its label by recommending changes in the graph. All nodes that are part of motif,
Counter-factual task:
21

---

Published in Transactions on Machine Learning Research (05/2024)
are given specific label and non-motif nodes are given different label. Since the nodes are always chosen from motils, the explanation is the motif itself. This setup is identical to Cv2 and CP-GNNEXPLAINER.
The Gan model Φ: We use the same GNN model used in CF-GNNEXPLAINER and CF Specifically, it is a Graph Convolutional Networks trained on each of the datasets. Each model has graph convolutional lay- ers, with 20, 128 and 256 hidden dimensions for the benchmarking datasets, Amazon-photos and ogbn-arxiv respectively. For graph classification we use GNN with 3 Iconvolutional layers and 20 hidden dimensions. To compute the graph embedding we do a max-polling over the node embeddings. The non lineariy used is retu for the first two layers and log softmax after the last layer of GCN. The learning rate is 0.01. The train and test data are divided in the ratio 80:20 for benchmark datascts. For ogbn-arxiv, we use the standard splits provided in the ogb package. In our experiments, we use a scaled-down version of the Amazon-Pholos dataset. We choose one random node as the central node and took its 3 3-hop neighbourhood in our dataset. Amazon Photos has an average degree of 13, hence, the 3 hhop neighborhood covers reasonable distribution of class labels. We split the nodes of this subgraph in the ratio of 80 : 20 for train and test sets. The accuracy of the GNN model & for each dataset. is mentioned in Table D]
Training, Inference and Parameters: For INDUCE and GEM, use aasin/vvaluation split of 80/20 on the benchmark, graph and the Amazon- Photos datasets. For ogbn-arxiv, we train on 10 random examples per class, and sample 1000 random nodes as the test dataset. We make sure that the test and train sets are disjoint. The evaluation set for all techniques are identical. For GEM and INDUCE, the train set is identical. Since CT-GNNEXPLAINER and CF² are transductive, only the evaluation set is used for them where they learn a node-specific parameter set. The same happens on the transductive version of INDUCE.
Parameters settings: We use h 4 because extracting the 4-hop neighbourhood as the subgraph ensured that we preserve the black-box model's accuracy. We use B 0.5 so to give equal weight to the predict loss and distance loss (see Eq. 10). We use different values of y E {0.4, 0.6} and find the best performance at ς = 0.4 for the inductive setting and ς = 0.6 for the transductive setting with a maximum perturbation budget& 5 = 15. We use maximurn number of episodes M 80, 500, 500 for BA-shapes, Tree-cycles and Tree- grid respectively. We use GAT as the GNN of choice for the policy network. For the policy network, we use 3 GAT layers, 2 fully connected MLP layers, 16 hidden dimension, a learning rate of .0003 and LeakyReLU with negative slope 0.1 the activation function. We use three different values for r {0.1, 0.001} and r = 0.1 improves the performance due to higher weight for exploration.
Mathod
Sparsity (Treo-Cycles)
Sporsity (Tree-Crid) || Sparsity (BA-Shapes)
Amazon-photos
ogbn-arxiv
CF-GnnEx
0.93
0.95
0.99
NULL
DNS
CP
0.59
0.92
0.90
DNS
InduCE (trans.)
0.92
0.96
0.98
0.99
0.78
Comparison of "sparsity" of counterfactuals predicted by transductive methods. "NULL" means the baseline could not find a counterfactual. "DNS" means that the base- line did not scale.
Table K:
Method
|| Sparsity (Tree-Cycles)
|| Sparsity (Tree-Grid)
Sparsity (BA-Shapes)
Amazon-photos
ogbn-arxiv
PGExplainer
0.64
0.61
NULL
0.66
Gam
0.54
0.77
0.88
NULI
DNS
RCExplainer
0.97
0.98
NA
NA
NA
Clear
0.71
0.77
InduCE (ind.)
0.90
0.88
0.99
0.99
0.64
Table L: Comparison of "sparsity" " of counterfactuals predicted by inductive methods. "NULL" means the baseline could not find a counterfactual. "DNS" means that the baseline did not scale (please refer to App. I for detailed reasoning). "NA" " means not applicable as RCExplainer code did not extend to multi-class setting (Refer App. J for details.)
E Additional Results on Sparsity of Counterfactuals
Sparsity is defined as the proportion of edges in Ng. i.c., the ε-hop neighbourhood of the target node v. Since counterfactuals are supposed to be minimal, value close to 1 is desired. We compare INDUCE
22

---

Published in Transactions on Machine Learning Research (05/2024)
with its baselines on sparsity in Tables K and
We observe that INDUCE produces better comparable explanations in terms of sparsity. In Table L observe that the sparsity of InduCE-inductive is slightly less than PGEXPLAINER for the ogbn-arxiv dataset. However, the fidelity of PGEXPLAINER is greater than INDUCE-inductive (Recall Table 60_ Thus, when looking at the combined results, one may conclude that PGEXPLAINER finds counterfactual explanations for the easier examples and, as a result, has sparser explanations. Similarly, we can interpret the sparsity of CF-GNNEXPLAINER being better than INDUCE- transductive for Tree-Cycles in Table K as its fidelity is much higher than the latter (Recall Table 3
F
Ablation Study
To infuse more information about the local graph structure and and its statistics, we use several hcuristic features such as degree, entropy, and one-hot encoded labels (Refer 3.1). We conduct an ablation study to investigate the effectiveness of each heuristic feature. Table MableeSsmmnl Nummarises the findings. Our method is most consistent when uses all features. Note that features and entropy together produce competitive results, However, the fidelity in BA-Shapes becomes much worse from this combination. This means, in most of the cases, this combination is unable to find the counterfactual example. In such cases, the possibility of getting better values in other measures increases.
Gen Vs. Gat: INDUCE uses a GAT to train the RL policy. In the next experiment, we evaluate the impact of replacing the GAT with a Graph Convolutional Network (GCN). The results are presented in Table M We see that GAT significantly outperforms GCN in the inductive version and thereby justifying our choice.
Heuristic Features: Table N contains an exhaustive analyses of the performance of InDUCE-INDUCTIVE using all combinations of heuristic features mentioned in section 3 The combination of features and entropy seems to allow best performance of the model on Tree-grid and Tree-cycles datasets, however we see in Table that BA-shapes is a dense network and clearly the degree heuristic in combination with node features leads to excellent performance for BA-shapes in terms of the size and the accuracy. Since the ability of the method to find a counterfactual weighs more, our default model containing all heuristic combined with node features gives best overall performance in fidelity, with size and accuracy being better or comparable to the other combinations in most cases.
G Additional Results on Counterfactual Size Distributions
In figures and we observe the distributions of edit distance between the original and the counterfactual h-hop neighbourhood of instances in Tree-Gres Pree-Grid and BA-Shapes datasets respectively. As observed both inductive and transductive versions of INDUCE most of the counterfactuals are of small size and dominated by edge additions. However, we can also observe that the transductive versions of INDUCE does produce counterfactuals of size mostly localised around 1. This is because the parameters instance. INDuCt-induetive however with minor tradc-off in the counterfactual size, provides comparable performance to InDuCE-trausduchh transductive baselines (recall Table 7ah. We further conduct experiments on how the accuracy of the explainer is affected with increasing counterfactual size in App.
tailored instance by
(recall Tables 3 and g while providing a speed-up of 79x over all the
Tree-Cycles
Policy Variant
Fid. 1
Size 1
A%)
0
2.62 11.52
78.84
0
1.99
+1.00
97.47
InduCE- BaauuC--transduttv--Caaa
0
1.08
+0.27
96.84
InduCCB-transduucivv-Caa
0
1.08
+0.27
96.20
Table M: Importance of attention in the GNN component of INDUCE.
23

---

Published in Transactions on Machine Learning Research (05/2024)
Method
FRL.(2)
Tree- Tree-Cycles Staw
Acc.(%)
Fid.(%)
Tree-Grid
Size 4
Aec.[%)
FRl.(%))
BA-Shapes
Stew
Aec:(%)]
Peatures only
3.12
11:06
80.05
4.50 13.16
73.12
18.4
3.62
13.38
70.29
Features +
Panturus
3.19
79.70
28.9
Peatures + D
2.81 11:55
85.19
3.12
1:196
81.77
48.7
2.43 1.285
63.71
Foatures + D OH
1.05
41.58
69.31
3.16
#:2.1
92.02
1.3
8.62
22.45
02.08
Pentures E. OH
2.62
+1.52
78.84
3.47
+2225
88.15
27.6
4.2
+3.00
56.00
Fuatures + E OH
2.51 +1.44
96.65
4,67 #2.91
91.05
2.8
4.37 +3.53
64.4
Table N: Ablation study results. D, E, and OH represents degree, entropy, and one hot encoded labels respectively. We vary node features along with different heuristic features to measure the effect of cach of these features. Our proposed method INDUCE is superior when it uses all the features.
Addition
Number of excmmlles
Do letion
examples
Deletion
20
15
20
20
Countertactual
Counterfactual size
(a) Inductive
(b) Transductive
Figure H: The distributions of the edit size and their internal composition of edge additions and deletions by INDUCE on the Treo-Grid dataset.
H Size Accuracy Trade-off
The accuracy comnteracttull size trade-off for InduCE in Table O and P We observe that with higher size, the accuracy decreases. Recall, use benchmark datasets with ground-truth explanations where a node belongs to a particular class if it belongs to certain motif. Hence, an explanation is accurate if it includes edges from the motif. We observe that when the explainer fails to find short explanations, it typically deviates towards a sequence of edges outside the motif. Hence the explainer fails to change the label till large set. of edits are made.
Size
Ace. (Tree- (Tree-Cycles) || Acc. (Tree-Grid)
Ace.% (BA-Shapes)
1
100
100
100
3
94
97
100
5
73
89
100
6
83
NA
NA
7
86
88
100
NA
100
15
NA
73
73
Table O: Counterfactual Size Accuracy Trade-off for InduCE- inductive: The results suggest that as counterfactual size increases, the accuracy of the explanation decreases. NA stands for counterfactual of that size was not present.
Size
Acc. % (Tree-Cycles)
Acc. % (Tree-Grid
Ace. (BA-Shapes)
100
100
100
100
NA
NA NA
50
NA
57
Table Counterfactual Size vs. Accuracy Trade-off for InduCE- transductive: The results suggest that as counterfactual size increases, the accuracy of the explanation decreases. NA stands for counterfactual of that size not present.
24

---

Published in Transactions on Machine Learning Research (05/2024)
Additiion
Addition
Number of examples
Deletion
Number examples
Deletion
40
30
20
20
10
10
91101112231111
Counterfactual size
Counterfactual size
(a) Inductive
(b) Transductive
Figure I: The distributions of the edit size and their internal composition of edge additions and deletions by
INDUCE the BA-Shapes datasct.
Non-scalability of the Baselines
Most baselines do not scale for Ogbn-arxiv dataset. We describe the details as follows. Ogbn-arxiv is million-sized node prediction datasct with 169,343 nodes and 1,166,245 edges. CF?, GEM and CLEAR do not scale (Recall Tables 5a and 5b) on this dataset since they employ computations dense adjacency matrix, which require O(n2) space, where is the number of nodes in the graph. For million-sized graph, this leads to memory overflow. Adapting to sparse adjacency matrix requires non-trivial changes to the source code.
EI-LANEER extracts the k-hop neighbourhood of target node at the runtime and adapts to sparse adjacency matrices more easily. SF--GNEEXPAINNE'SS algorithm is model-agnostic, however, the code-base suitable for its customized black-box and cannot be trivially extended any other black-box. The explainer loads the black-box weights into itself before freezing them, assuming that the black-box uses the same architecture as itself. It then uses those weights rather than the black-box GNN during the explanation. In case the explainer's architecture does not match the black-box architecture, the keys for loading the weights do not match, hence, the explainer's weights are not loaded, rather randomly initialized. As a result, the explainer gets initialized with random weights rather than the black-box's weights and acts as a random classifier. This is an inefficient design choice and prevents CF-GNNEXPLAINER code from scaling for ogbn-arxiv(HL) (Recall Table 5p. We use syTorcch-gemeettee GCNCone layers Kipf & Welling (2016) that compatible with sparse adjacency matrices to scale the black-box GNN to the million-sized graph. INDUCE's code is wrilten in model-agnostic fashion. Any black-box GNN which employs log softmax non-linearity at the last layer is compatible with INDUCE.
Fey & Lenssen (0119) standard
Clear further does not scale for dense networks BA-Shapes and Amazon (Recall Table and 5b. The reason that for dense graphs k-hop neighbourhoods are significantly larger. The backbone of CLEAR is graph- VAE Siioonovsy & Komodakis (2018) which does not scale for large graphs.
Results of RCExplainer on Benchmark datasets
The codebase provided by the authors of RCEXPLAINER could be utilized for explanation of graph classifica- tion only. We modified it for node classification by taking the k-hop ego-networks of nodes and training the explainer with these networks, however, the results were not reproducible. Hence, we implemented the code for the binary node classification task. The explainer failed to push the node across the decision boundary to get a counterfactual and was stuck in an infinite loop. We further limited the loop to a finite number of iterations. The results are reported on the benchmark binary classification datasets in Table 4 We observe the predicted counterfactuals are sub-par IxDuCE-inductive
25

---

Published in Transactions on Machine Learning Research (05/2024)
Treo-Cycles
Tres-Crid
BA-Shapes
Fid.(%))
Size 4
(%c.
Fid.(%)
Size J
Aec.(%)
Fld.(%)
Size J
Acc.(%6]7
0.0001
1.01 #0.12
97.22
#0.12
96.12
1.21 +:0.67
97.87
0.25
0
1.01 #0.12
97.22
1.02 #0.12
96.90
1.30 #:0.6
84.3 34
(clfaault)
1.01
+0.12
98.61
1.02
97.67
+0.90
95.31
0.75
1.01 #0.12
96.83
1.02 #0.12
96.90
1.33
+0085
90.79
1.00
1.01 10.12
97.22
1.02 10.12
96.90
1.39
1.00
94.38
varying (3: Lower fidelity, smaller size, and higher accuracy are desired. The best results are in bold. Tr., Fid., Acc. denote transductive, fidelity and accuracy, respectively. The best result is highlighted in bold.
Table Q: Results for InduCE-transduuctvve
Trep-Cycler
Theo-Crid Size J
BA-Shapes Size J
Fid.(%))
Sizee J
A%c.
Fid.(%6)
A%c.(%)
Fid.(%6)
Acc.(56)7
0.0001
2.31
11.44
96.65
4.63
#:2.1
4.37
+3553
0.25
0
2.31
11.44
96.65
4.63
#2.91
91.21
2.6
4.37
23.53
64.40
(defaauts)
1:444
96.37
3.5.3
64.40
0.75
2.81
+1.44
96.65
4.63
#2291
91.21
2.6
4.37
+3.53
64.40
1,00
#1.44
96.65
4.63
#:291
91.21
+3.53
64.40
varying 3: Lower fidelity, smaller size, and higher accuracy are desired. The best results are in bold. Tr., Fid., Aec. denote transductive, fidelity and accuracy, respectively. The best result is highlighted in bold.
Table R: Results for InduCE-inductive
K Effect of Hyper- spper-parameters
In this section, we examine the effect of varions hyper-parameterd on the performance of INDUCE on the three benchmark datasets.
Impact of 8: In this experiment, we vary 3 parameter that regulates the weightage of log- lieeliil vs. the perturbation count in Equation D The results are provided in Tables Q and R for the transductive and inductive settings respectively. We vary / from 0.0001 to 1. We observe that INDUCE is robust to change in 3 in most cases. This can be attributed to the small sizes of counterfactuals in general in the benchmark datasets. Thus, the actual effect of B may come into play for larger-sized counterfactuals when trajectories are longer, i.c., a larger set of edits are needed to change the class label of the target node. Further, for INDU CF-transduettive we observe that for BA-Shapes datasets as / increases the counterfactual size increases. This seems counter-int inntttrriittuiive it is more important to focus reducing the log-likelihood of the label rather than increasing the weight of the counterfactual size component of the reward function. In this manner, the model is incentivized to pick perturbations that will cause the target to cross the decision boundary in the early stages of the action trajectory.
the face but hints the fact that for smaller trajectories,
Impact of hops (h): In this experiment, we vary the number hops in the ago-network of the target node while keeping the number of layers in the policy network constant. The results are provided in tables S and T We vary the number of hops from to 5, where 3 was the number of layers in the GNN being explained. We observe that, in general, hop-value closer to the number of GNN layers leads to better effectiveness. This observation especially shines for INDUCE- the hops cause a drastic drop in performance. This can be attributed to the explosion of the size of the action space or the search space of counterfactuals, which may cause generalizability issues. Furthermore, inductive explanations are harder since the explainer needs to generalize to unseen data.
(Refer Table T wherein increasing
Impact of GAT-layers: Finally, we study the impact of the number of layers in the GAT used in the policy network while keeping everything else fixed. The results are provided in Tables [and]] V We observe that the number of GAT layers should be close to the number of GNN black-box layers, and thus, also the number of hops in the target's eeo-ne Note that earlier we observed that increasing the number of hops in the ego network of the target node beyond the number of layers in the GNN black box reduces performance (Recall Table T For an ego-network with a smaller number of hops, if we use a GAT with a larger number layers, the embeddings would be over-smoothed, and that would lead to degraded performance. Therefore, idcally, for INDUCE we used 4-hop ego- network and a 3-layered GAT.
26

---

Published in Transactions on Machine Learning Research (05/2024)
Tree-Cyclos
Tres-Grid
BA-Shapes
Hop=(b)
Fid.(56)
Aoc.(%)
Fld.((5)
Aoc.(%))
Fld.(5))
Aec-(%))
0
143
10.16
99.31
0
1.14
10.35
93.80
0
1.08
0.27
91.71
0
1.01
1:0122
97.22
0
1.02 10.12
90.90
0
1.12
10.36
94.96
(defanit)
1.01 #0.12
98.61
0
1.02 =0.12
97.07
0
1.30
#0.90
95.31
1.01
#:012
100
1.02 =0.12
99.22
1.43 +0.09
93.31
Table S: Results for InduuEv-rrasdductive on varying hops of target's neighbourhood: Lower fidelity, smaller size, and higher accuracy are desired. The best results are bold. Tr., Fid., Acc. denote transductive, fidelity and accuracy, respectively. The best result is highlighted in bold.
Hops(h)
Tree- Cree-Cycles Size
Pree-Grid
BA-Shapes Sise
Fid.(%)
Arc.(%)
Fid.(9E)
Acc.(%)
vid.(%)
Acc.(%))
1.82 1.18
97.08
1.55
2.08 1.67
94.90
3.95
2.423 12.43
94.77
1.09
98.
3.44 2.49
13.16
2,70
#2.86
75.54
(defanls)
2.31 11.44
96.57
1.67
12.91
91.05
2.6
4.37
4:3.5
64, 10
2.06
11.39
96.03
8.52
5.38
1:3 82
3.49
2:3002
83.54
Table T: Results for InduCE-inductive on varying hops of target's neighbourhood: Lower fidelity, smaller size, and higher accuracy are desired. The best results are in bold. Tr., Fid., Ace. denote transduc- tive, fidelity and accuracy, respectively. The best result is highlighted in bold.
Treo-Cyeles
Tres-Grid
B BA-Shapes Size
Layers
Fid.(%)
Acc.(%))
Fid.(%)
J
Acc.(%)
Fid.(%)
Acc.(%))
1.01 10.12
97.22
1.02 10.12
97.67
1.22 10070
98.38
(default)
1.01 10.12
98.61
1.02 10.12
97.07
1.30 2:090
95.31
1.01 #0.12
07.22
1.02 =0.12
99.22
1.18 #0060
97.32
1.01
97.22
97.67
+0.88
02.543
Table U: Results for InduCE-transduuttvve on varying GAT layers policy network: Lower fidelity, smaller size, and higher accuracy are desired. The best results are in bold. Tr., Fid., Acc. denote transductive, fidelity and accuracy, respectively. The best result is highlighted in bold.
Treo-Cycles
Treo-Grid
BA-Shapps
Layers
Fld.(%)
A%c.(%)
Fid(5%)
J
Aoc.(%)
Fid.(%)
Acc-(56)
1.81
20.93
89.93
0.78
2,83
+2.39
95.59
68.74
3.26
#2260
92
(default)
2.31
.44
96.57
4.67
2.6
4.37
+3368
2.88
1.48
66.20
2.80
1188
86.76
3.95
4.27
#1.01
61.85
65:45
+22.55
76.22
3.39
+:3.8
95.13
Table V: Results for InduCE-inductive on varying GAT layers in policy network: Lower fidelity, smaller size, and higher accuracy desired. The best results are in bold. Tr., Fid., Acc. denote transduc- live, fidelity and accuracy, respectively. The best result is highlighted in bold.
27


Reviews:
[{"review_id": "EgIiCPxvGi", "reviewer": "Reviewer_uNdq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- InduCE solves the edge perturbation combinatorial optimization problem through reinforcement learning to bypass the NP-hard optimal solution computation\n- The model is inductive and can support both edge addition and deletion perturbation.\n- The paper is easy to follow.\n\nCons and questions \n- In section 3.1 it says \"Intuitively, the state should characterize how likely the class label of the target node v would flip following a given action\". For non-binary classification problems (i.e., the number of classes is larger than 2), how is \"flip\" applied and can be understood? My understanding is that by \"flip\", the label changes. However \"flip\" can sound weird for multi-label scenarios.\n- In section 3.2, \"Gat\" should be \"GAT\". \n- The evolution of the distribution over perturbation space can be further discussed in the paper. For example, showing the width / entropy evolution across iterations. \n- How does the presence and shape of the predefined motif contribute and influence the inference result?\n- Can you elaborate more on the inductive nature of InduCE and how it enables the algorithm to generalize to unseen data without instance-specific training, and how it differs from the transductive approaches?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents InduCE, a novel algorithm for generating counterfactual explanations in GNNs. This inductive learning framework models marginal probabilities in the perturbations space and enables both edge additions and deletions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please answer and address cons and questions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gcKIAIKkIm", "reviewer": "Reviewer_YfqB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Point out issues of existing approaches.\n- Provide theoretical analysis for the difficulty of the studied problem and the complexity of the proposed method.\n- The experiments on five datasets show promising results.\n\nWeaknesses:\n- One of the major contributions of this paper is modeling the marginal effect of perturbations aid in generating better counterfactuals, which seems to be the main reason for the improvement of effectiveness. This point is important but has not been well validated. Adding theoretical analysis for the improvements of the marginal effect modeling on counterfactual explanation would be beneficial.\n- Certain parts of this paper lack clarity, making them difficult to follow. Some terms, such as the sufficiency score metric, are introduced without clear explanation.\n- The overall writing quality requires enhancement. Some typos are present in the current version, and informal formatting is observed throughout.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the counterfactual explanation problem on GNNs. It discussed some issues in existing work, including 1) lack of marginal probability modeling; 2) inability to add edges; and 3) lack of generalization. \n\nTo address these problems, this work proposes a model-agnostic, inductive counterfactual reasoning method for GNNs – InduCE, which contains two phases: training and inference. In training, a counterfactual reasoning model is learned, and in inference, the counterfactual graph is predicted based on the reasoning model.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Clear validation for the improvements in marginal effect modeling of perturbations \n2. Need careful proofreading and improvement for presentation.", "broader_impact_concerns": "No concerns on the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IxiXIdtlSW", "reviewer": "Reviewer_jot5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The problem of developing explainable graph neural networks is important and useful in real applications. \n\n+ Proposed a new counterfactual explanation method for graph neural networks. It is reasonable to leverage the reinforcement learning framework to model the process of explainable structure generation. The proposed method achieves competitive performance in comparison with multiple baseline methods. \n\n+ The presentation is clear and easy to follow.\n\nWeaknesses\n- Inductive Setting: The authors claimed that inductive ability is an important strength of the proposed method. However, existing parameterized algorithms can also be employed for inductive inference tasks on new nodes/graphs by utilizing the learned model, specifically the optimized parameters. I find this claim less convincing, and I believe additional demonstrations are necessary to substantiate it. \n\n- Edge Addition: Additionally, the authors introduced the edge addition operation. While it makes sense to utilize existing sub-structures to explain prediction results, it remains unclear to me how we can interpret the model's outcomes using newly added edges, given that these edges are not originally part of the graph. Once again, I believe more demonstrations are essential to clarify this aspect.\n\n- Task/Experiment: As far as I know, many existing methods (e.g., PGExplainer) can be applied/adapted to both node-level and graph-level tasks. Whether the proposed method be applied to graph-level tasks? If so, it would be better to see experiments/results regarding the graph classification task using existing graph-level data such as MUTAG.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new counterfactual explanation method for graph neural networks. The major idea is to model the edge perturbation process as the Markov decision process and leverage the reinforcement learning framework to generate explainable structures. Experiments on several datasets demonstrate that the proposed method can outperform multiple baseline methods for the explainable node classification task. Additional analytical experiments and case studies are further provided to show the effectiveness and efficiency of the proposed method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above weaknesses.", "broader_impact_concerns": "No ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The motivation of the work is to be able to describe the minimal perturbation to a GNN graph that would enable a particular node's prediction to change. The authors tackle several aspects of this that (in combination) were not previously handled by works in this area: first, they wish for the graph perturbations to include both edge deletions *and* additions. Second, they want to build a model that need not be trained on a fixed set of nodes (and re-trained on unseen nodes). Third, they model marginal probabilities in the perturbations. 

The authors propose a solution relying on an RL-based scheme. While it is fairly intricate, the authors obtain a number of high-quality results. Additionally, they have a wide variety of experiments demonstrating the value of the approach vs techniques that only include a subset of their desired properties.

Generally, the reviewers found the motivation for the paper compelling. They asked for additional clarity. The authors' updated draft is significantly clearer and is now easy to read.  

Two concerns came up during the review process. One is how large of a contribution/how novel the authors' work is. Following TMLR's policy, this is not a crucial criteria (and I additionally believe there would be sufficient novelty in any case). The second concern is the theoretical value of the marginal information (vs zero-shot). The authors have done a solid job of demonstrating the impact empirically (i.e., Figure 4).

Overall, I believe the paper is worth accepting modulo some minor changes. I would like to see a revision with some minor aspects handled:
- It would be great for the authors to construct an intuitive argument or description for the value of modeling the marginal impact of edits. A full theoretical treatment (suggested by one of our reviewers) is not needed but could be a great topic for future work. Arguing for or explaining scenarios where we have reason to believe these gains are available (or conversely, will not be) is sufficient for the current work.
- While the paper has been improved clarity-wise, there are still some elements that could be further fleshed out. For example, it would be great to comment on how hyperparameter counts affect different techniques. The proposed technique in particular has a number of hyperparameters. It would be great to know how stable these are with respect to different graphs or problems, especially the reward function parameter $\beta$ and $h$, the number of hops used.
Decision: Accept (poster)