# Empowering Counterfactual Reasoning over Graph Neural Networks through
Inductivity

Samidha Verma
Indian Institute of Technology, Delhi, India
<EMAIL_ADDRESS>
&Burouj Armgaan
Indian Institute of Technology, Delhi, India
<EMAIL_ADDRESS>
&Sourav Medya
University of Illinois, Chicago, USA
<EMAIL_ADDRESS>
&Sayan Ranu
Indian Institute of Technology, Delhi, India
<EMAIL_ADDRESS>

###### Abstract

Graph neural networks (Gnns) have various practical applications, such as drug
discovery, recommendation engines, and chip design. However, GNNs lack
transparency as they cannot provide understandable explanations for their
predictions. To address this issue, counterfactual reasoning is used. The main
goal is to make minimal changes to the input graph of a Gnn in order to alter
its prediction. While several algorithms have been proposed for counterfactual
explanations of Gnns, most of them have two main drawbacks. Firstly, they only
consider edge deletions as perturbations. Secondly, the counterfactual
explanation models are transductive, meaning they do not generalize to unseen
data. In this study, we introduce an inductive algorithm called InduCE, which
overcomes these limitations. By conducting extensive experiments on several
datasets, we demonstrate that incorporating edge additions leads to better
counterfactual results compared to the existing methods. Moreover, the
inductive modeling approach allows InduCE to directly predict counterfactual
perturbations without requiring instance-specific training. This results in
significant computational speed improvements compared to baseline methods and
enables scalable counterfactual analysis for Gnns.

##  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 [20], designing
chips [16], and recommendation engines [31]. Despite significant success in
prediction accuracy, Gnns, like other deep learning based models, lack the
ability to explain why a particular prediction was made. Explainability of a
prediction model is important towards making it trust-worthy. In addition, it
sheds light on potential flaws and generates insights on how to further refine
a model.

Existing Works:  At a high level, Gnn explainers can be classified into the
two groups of instance-level [32, 14, 18, 36, 7, 35, 13, 21, 12, 4, 1, 27] or
model-level explanations [33]. Consistent with their nomenclature, instance-
level explainers explain a specific input graph, whereas model-level
explainers provide a high-level explanation in understanding general behaviour
of the Gnn model trained over a set of graphs. Recent research has also
focused on global concept-based [30, 2] explainers that provide both model and
instance-level explanations. Instance-level methods can broadly be grouped
into two categories: factual reasoning [32, 14, 18, 36, 7, 35] and
counterfactual reasoning [13, 21, 4, 1, 27]. 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 Gnn’s prediction. Perturbations correspond to
removal and addition of edges.

Compared to factual reasoning, counterfactual reasoners have the additional
advantage of providing a means for recourse [23]. For example, in drug
discovery [8, 29], mutagenicity is an adverse property of a molecule that
hampers its potential to become a drug [9]. 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.

Figure 1: The figure contains two graphs with the right graph being labeled
“Motif”. Each node in the left graph belongs to either the green class (label)
or yellow. Green class indicates a node that is part of a subgraph isomorphic
to the motif; yellow otherwise. Addition of the dotted edge incident on node A
changes its label from yellow to green since it becomes part of the motif.

In this work, we study counterfactual reasoning over Gnns towards node
classification. To illustrate our problem, let us consider the input graph
shown in Fig. 1. 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 on node A does not exist, for now. At this stage, if we
ask the counterfactual reasoner to flip 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 $\otimes$.

Existing works on counter-factual reasoning over Gnns suffer from two key
limitations:

  * •

Ability to add edges: Most of the existing techniques do not consider addition
of edges (or nodes); they only consider edge removals. This limitation
severely compromises the search space consisting of possible “changes” on the
input graph. As an example, in Fig. 1, if we only consider deletions, it is
impossible to flip the label of A.

  * •

Inductive modeling: Existing techniques, with the exception of Gem [12], are
transductive in nature, i.e., they cannot generate counterfactuals on unseen
nodes. As an example, if the model is trained to generate counterfactuals on
node $v$ of graph $G$, it cannot be used to generate counterfactuals on
another node $u$ 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 input graph due to external factors such as new
friend connections in a social network, citations in a citation network, etc.

Table G in the Appendix presents a structured summary of the instance-level
explainers.

Contributions:  In this work, we develop InduCE (Inductive Counter-factual
Explanations), that addresses the above limitations of existing 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 reasoning 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 introduce 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(|\mathcal{E}|)$, where $\mathcal{E}$ is the set of edges in the graph.
(§ 2).

  * •

Algorithm: Identifying the smallest number of edge additions or removals that
alter the prediction is a 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 combinatorial optimization problem through
reinforcement learning powered by policy gradients [28] (§ 3).

  * •

Empirical validation: Through extensive experiments on benchmark graph
datasets, 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
is indeed the reason driving InduCE’s superior performance. Finally, we also
showcase the computation gains obtained due to embracing the inductive
paradigm instead of transductive modeling (§ 4).

##  2 Preliminaries and Problem Formulation

We use the notation $\mathcal{G}=(\mathcal{V},\mathcal{E})$ to denote a graph
with node set $\mathcal{V}$ and edge set $\mathcal{E}$. We assume each node
$v_{i}\in\mathcal{V}$ is characterized by a feature vector
$x_{i}\in\mathbb{R}^{d}$. Furthermore, $l(v):v\rightarrow\mathcal{C}$ is a
function mapping each node $v$ to its true class label drawn from a set
$\mathcal{C}$. We assume there exists a Gnn $\Phi$ that has been trained on
$\mathcal{G}$. Given an input node $v_{i}\in\mathcal{V}$, we assume
$\Phi(\mathcal{G},v,c)$ outputs a probability distribution over class labels
$c\in\mathcal{C}$. The predicted class label is therefore the class with the
highest probability, which we denote as
$L_{\Phi}(\mathcal{G},v)=\arg\max_{c\in\mathcal{C}}\\{\Phi(\mathcal{G},v,c)\\}$.

######  Problem 1 (Counterfactual Reasoning on Gnns)

Given input graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, a target node
$v\in\mathcal{V}$, a Gnn model $\Phi$, and an optional set of node pairs
$\mathcal{V}_{c}=\\{(v_{i},v_{j})\mid v_{i},v_{j}\in\mathcal{V}\\}$ between
which edges may be perturbed, find the closest graph $\mathcal{G}^{*}$ by
minimizing the number of perturbations, such that
$L_{\Phi}(\mathcal{G}^{*},v)\neq L_{\Phi}(\mathcal{G},v)$ and all perturbed
edges are among pairs in $\mathcal{V}_{c}$.

In a real world, we may not have control over all perturbations.
$\mathcal{V}_{c}$ allows us to specify that. If
$\mathcal{V}_{c}\subseteq\mathcal{E}$, we restrict to only deletions. On the
other hand, if $\mathcal{V}_{c}\cap\mathcal{E}=\emptyset$, 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 $\Phi$ is visible
to us, but not its parameters. Second, the reasoner should be inductive, which
means we should learn a predictive model $\Pi$, that can predict the
counterfactual graph $\mathcal{G}^{*}$ given the inputs $\mathcal{G}$, Gnn
$\Phi$, and target node $v$.

######  Theorem 1 (NP-hardness)

Counterfactual reasoning for Gnns, i.e., Prob. 1, is NP-hard.

We prove NP-hardness by mapping counter-factual reasoning over Gnns to the
set-cover problem. The details The are provided in the App. A). 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 $\Pi$, and
thus, the proposed algorithm is broken into two phases: training and
inference. During training, we learn the parameters of the model $\Pi$ and
during inference, we predict the counterfactual graph using $\Pi$. Theorem 1
prohibits us from supervised learning since generating training data of
ground-truth counterfactuals is NP-hard. Hence, we use reinforcement learning.
Through discounted rewards, reinforcement learning allows us to model the
combinatorial relationships [10] in the perturbation space.

###  3.1 Learning $\Pi$ as an MDP

Given graph $\mathcal{G}$, we randomly select a subset of vertices from
$\mathcal{V}$ to train $\Pi$. Given a target node $v$, the task of $\Pi$ is to
iteratively delete or add edges such that with each perturbation the
likelihood of $\Phi(\mathcal{G}^{t},v)\neq\Phi(\mathcal{G},v)$ changes
maximally. Here, $\mathcal{G}^{t}=(\mathcal{V},\mathcal{E}^{t})$ denotes graph
$\mathcal{G}$ after $t$ perturbations starting with
$\mathcal{G}^{0}=\mathcal{G}$. We model this task of iterative perturbations
as a markov decision process (MDP). Specifically, the state captures a latent
representation of the graph indicative of how it would react to a
perturbation. An action corresponds to an edge addition or deletion by $\Pi$.
Finally, the reward is a function of the number of perturbations, which we
want to minimize, and the probability of $\Phi(\mathcal{G}^{t},v)$ flipping
following the next action (edge addition or deletion), a value that we want to
maximize. We next formalize each of these notions.

State: Intuitively, the state should characterize how likely the class label
of the target node $v$ would flip following a given action. Towards that end,
we observe that a Gnn of $\ell$ layers aggregates information from the
$\ell$-hop neighborhood of $v$. 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 set of node representations in the $h$-hop neighborhood of the
target node $v$, where ideally $h>\ell$. Specifically, at time $t$, the state
is:

$\displaystyle\mathbf{S}^{t}_{v}$
$\displaystyle=\left\\{\mathbf{x}^{t}_{u}\mid
u\in\mathcal{N}^{h}_{v}\right\\}\text{, where}$ (1)
$\displaystyle\mathcal{N}^{h}_{v}$ $\displaystyle=\left\\{u\in\mathcal{V}\mid
sp(v,u)\leq h\right\\}$ (2)

Here, $sp(v,u)$ denotes the length of the shortest path from $v$ to $u$ in the
original graph $\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$.

The representations of nodes, i.e., $\mathbf{x}^{t}_{u}$, are constructed
using a combination of semantic, topological, and statistical features.

Figure 2: Pipeline of the policy learning algorithm in InduCE. $\delta$
indicates the maximum number of allowed perturbations.

  * •

Original node Features:  It is common to encounter graphs where nodes are
annotated with features or labels (recall the definition of $x_{i}$ in § 2).
We retain these features.

  * •

Degree Centrality: The higher the degree of a 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 a part its representation.

  * •

Entropy: The entropy of a node at time $t$ is defined as
$e^{t}_{u}=-\sum_{\forall c\in\mathcal{C}}p_{c}\log p_{c}\text{, where
}p_{c}=\Phi\left(\mathcal{G}^{t},v,c\right)$. The entropy quantifies the
uncertainty of the Gnn $\Phi$ on a given node. We hypothesize that if the
$\Phi$ is highly certain (i.e., low entropy) about the class label of some
node $u$, then any perturbation on $u$ is unlikely to make it flip. 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 $\mathbf{x}^{t}_{u}$.

  * •

Class label:  Finally, we include the predicted class label of a node, i.e.,
$L_{\Phi}(\mathcal{G}^{t},u)$ in the form of one-hot encodings of dimension
$\mathcal{C}$.

The final representation of node $u$ and time $t$ is therefore the
concatenation of the above features, i.e.,

$\mathbf{x}_{u}^{t}=x_{i}\mathbin{\|}degree^{t}_{u}\mathbin{\|}e^{t}_{u}\mathbin{\|}\left(\text{one-
hot}\left(L_{\Phi}\left(\mathcal{G}^{t},u\right)\right)\right)$ (3)

Here, $\mathbin{\|}$ represents the concatenation operator.

Actions: The action space consists of all possible edge deletions in the
$h$-hop neighborhood of target node $v$ and additions of edges from $v$ to
other non-attached nodes in its $h$-hop neighborhood. Formally, the sets are
defined as follows:

$\displaystyle\mathcal{E}^{t}_{v,del}$
$\displaystyle=\left\\{e=(u_{i},u_{j})\in\mathcal{E}^{t}\mid
u_{i},u_{j}\in\mathcal{N}^{h}_{v}\right\\}$ (4)
$\displaystyle\mathcal{E}^{t}_{v,add}$
$\displaystyle=\left\\{e=(v,u_{j})\not\in\mathcal{E}^{t}\mid
u_{j}\in\mathcal{N}^{h}_{v}\right\\}$ (5)

The action space is the perturbation set:

$\hskip
6.50403pt\mathcal{P}^{t}=\mathcal{E}^{t}_{v,del}\cup\mathcal{E}^{t}_{v,add}$
(6)

Reward: Our objective is to flip the predicted label of target node $v$ with
the minimum number of perturbations in $\mathcal{N}^{h}_{v}$ in order to find
the counterfactual. To capture these intricacies, we formulate the reward of
an action $a$ as a combination of the prediction accuracy of Gnn $\Phi$ and
the number of perturbations made so far.

$\displaystyle\mathcal{R}^{t}_{v}(a)$
$\displaystyle=\frac{1}{\mathcal{L}^{t+1}_{v,{pred}}+\beta\times
d(\mathcal{G},\mathcal{G}^{t})}\text{, where}$ (7)
$\displaystyle\mathcal{L}^{t}_{v,pred}$ $\displaystyle=\sum_{\forall
c\in\mathcal{C}}\mathds{1}_{l(v)=c}\log\left(\Phi\left(\mathcal{G}^{t},v,c\right)\right),d(\mathcal{G},\mathcal{G}^{t})$
$\displaystyle=t+1$ (8)

In simple terms, $\mathcal{L}^{t+1}_{v,pred}$ is the log-likelihood of the
data predicted by $\Phi$ in $\mathcal{G}^{t+1}$ on $v$. $\mathcal{G}^{t+1}$ is
the created upon perturbing $\mathcal{G}^{t}$ with action $a$. $\beta$ is a
hyper-parameter that regulates how much weight is given to log-likelihood of
the data vs. the perturbation count. $d$ is the distance function, which in
our case is simply the number of edge edits made to $\mathcal{G}$ at time step
$t$.

State Transitions: At time $t$, the action corresponds to selecting a
perturbation $a\in\mathcal{P}^{t}$ (Recall Eq. 6) from
$p^{t}_{a,v}\sim\Pi\left(a\mid\mathcal{S}^{t}_{v}\right)$. We will discuss the
computation of $p^{t}_{a,v}$ in § 3.2.

###  3.2 Neural Architecture for Policy Training

To learn $p^{t}_{a,v}$, we we take the representations in
$\mathbf{S}^{t}_{v}$, and pass them through a neural network comprising of a
$K$-layered Graph Attention Network (Gat) [22], an MLP, and a final SoftMax
layer. The Gat learns a $d$-dimensional representation
$\mathbf{a}\in\mathbb{R}^{d}$ for each perturbation $a\in\mathcal{P}^{t}_{v}$.
$\mathbf{a}$ is then passed through an Multi-layered Perceptron (MLP) to embed
them into a scalar representing their value, which is finally passed over a
SoftMax layer to learn a distribution over $\mathcal{P}^{t}_{v}$. The entire
network is trained end-to-end. We next detail each of these components.

Gat: Let $\forall
u\in\mathcal{N}^{h}_{v},\mathbf{h}^{0}_{u}=\mathbf{x}^{t}_{u}$ (Recall Eq.3).
In each layer $k\in[1,K]$, we perform the following transformation:

$\mathbf{h}^{k}_{u}=\sigma\left(\sum_{\forall
u^{\prime}\in\mathcal{N}^{1}_{u}\cup\\{u\\}}\alpha^{k}_{u,u^{\prime}}\mathbf{W}^{k}\mathbf{h}^{k-1}_{u^{\prime}}\right)$
(9)

$\sigma$ is an activation function, $\alpha^{k}_{u,u^{\prime}}$ are learnable,
layer-specific attention weights, and
$\mathbf{W}^{k}\in\mathbb{R}^{d^{k-1}\times d^{k}}$ is a learnable, layer-
specific weight matrix where $d^{k}$ is the hyper-parameter denoting the
representation dimension in hidden layer $k$. In our implementation, we use
LeakyReLU with negative slope $0.01$ as the activation function. The attention
weights are learned through an MLP followed by a SoftMax layer. Specifically,

$\displaystyle
e^{k}_{u,u^{\prime}}=\texttt{MLP}(\mathbf{h}^{k-1}_{u}\mathbin{\|}\mathbf{h}^{k-1}_{u^{\prime}})\text{,
where }e^{k}_{u,u^{\prime}}\in\mathbb{R},\hskip
50.58878pt\alpha^{k}_{u,u^{\prime}}=\frac{exp\left(e^{k}_{u,u^{\prime}}\right)}{\sum_{\hat{u}\in\mathcal{N}^{1}_{u}\cup\\{u\\}}exp\left(e^{k}_{u,\hat{u}}\right)}$

After $K$ layers, the Gat outputs the final representation
$\boldsymbol{\mathcal{X}}_{u}=\mathbf{h}^{K}_{u}$ for each node $u$ in $v$’s
neighborhood. Semantically, given the initial state representation
$\mathbf{x}^{t}_{u}$, the Gat enriches them further by merging with
topological information. Finally, the representation of an action
$a\in\mathcal{P}^{t}_{v}$ is set to $\mathbf{a}=\mathcal{X}_{u}\
||\mathcal{X}_{v}\ ||\ t(u,v)$, where:

$t(u,v)=\begin{cases}0,&a\in\mathcal{E}^{t}_{v,del}\text{ (Recall
Eq.~{}\ref{eq:del})}\\\ 1,&a\in\mathcal{E}^{t}_{v,add}\text{ (Recall
Eq.~{}\ref{eq:add})}\end{cases}$ (10)

MLP and SoftMax layers: The value of $a$ is $s_{a}=\texttt{MLP}(\mathbf{a})$,
where $s_{a}\in\mathbb{R}$. Finally, we get a distribution over all actions in
$\mathcal{P}^{t}_{v}$ as:

$p^{t}_{a,v}=\Pi(a\mid\mathcal{S}^{t}_{v})=\frac{exp(s_{a})}{\sum_{\forall
a^{\prime}\in\mathcal{P}^{t}_{v}}exp(s_{a^{\prime}})}$ (11)

###  3.3 Policy Loss Computation

We iteratively sample an action as per Eq. 11 till either the label flips or
we exceed the maximum number of perturbations (which is a hyper-parameter).
This iterative selection generates a trajectory of perturbations
$\mathcal{T}_{v}=\\{a_{1},\cdots,a_{m}\\}$. We use the standard loss for
policy gradients on $\mathcal{T}_{v}$ [28]. More specifically, we minimize the
following loss function:

$\mathcal{J}(\Pi)=-\frac{1}{\mathcal{V}_{tr}}\left(\sum_{\forall
v\in\mathcal{V}_{tr}}\left(\sum_{t=0}^{\lvert\mathcal{T}_{v}\rvert}\log{p^{t}_{a,v}}\mathcal{R}^{t}_{v}(a_{t})+\eta
Ent(\mathcal{P}^{t}_{v})\right)\right)$ (12)

Here, $\mathcal{V}_{tr}\subseteq\mathcal{V}$ is the subset of nodes on which
the RL policy is being trained. $Ent(\mathcal{P}^{t}_{v})$ is the entropy of
the current probability distribution over the action space.

$Ent(\mathcal{P}^{t}_{v})=-\sum_{\forall
a\in\mathcal{P}^{t}_{v}}p^{t}_{a,v}\log(p^{t}_{a,v})$ (13)

By adding the entropy to the loss, we encourage the RL agent to explore when
there is high uncertainty. $\eta$ is a hyper-parameter balancing the explore-
exploit trade-off. For simplicity of exposition, we omit the discussion on
discounted rewards in Eq. 12. Discounted rewards better capture the
combinatorial relationship in the perturbation space. Refer to App. B for
details.

###  3.4 Training and Inference

Fig. 2 presents the training pipeline. Starting from the original graph, we
compute the state representation at each iteration $t$. The state is passed to
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 $\phi$ is then applied on the modified graph. If the label
flips or the number 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.1 in the Appendix.

Inductive inference: We iteratively make forward passes till the label flips
or we exceed the budget. The forward pass is identical to the training phase
with the only exception being we 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.

Complexity of InduCE: The time complexity of training phase is
$\mathcal{O}(|\mathcal{V}_{tr}|(\mathcal{|V|}+\mathcal{|E|}))$ and the test
phase is $\mathcal{O}(|\mathcal{V}|_{test}|(\mathcal{|V|}+\mathcal{|E|}))$.
Here $\mathcal{V}_{tr}$ and $\mathcal{V}_{test}$ denote the number of nodes in
the train and test sets respectively. The derivations are provided in App. E.

##  4 Experiments

In this section, we benchmark InduCE against established baselines. The code
base and datasets used in our evaluation are available anonymously at
https://github.com/idea-iitd/InduCE.git. Details of the hardware and software
platform are provided in App. F.

###  4.1 Datasets

Table 1: The statistics of the benchmark datasets. | Tree-Cycles | Tree-Grid | BA-Shapes | Amazon | ogbn-arxiv
---|---|---|---|---|---
# Classes | 2 | 2 | 4 | 6 | 40
# Nodes | 871 | 1231 | 700 | 397 | 169,343
# Edges | 1950 | 3410 | 4100 | 2700 | 1,166,243
Motif size (# nodes) | 6 | 9 | 5 | NA | NA
Motif size (# edges) | 6 | 12 | 6 | NA | NA
# Nodes from motifs | 360 | 720 | 400 | NA | NA
Avg node degree | 2.23 | 2.77 | 5.86 | 15.90 | 6.89

Benchmark Datasets: We use the same three benchmark graph datasets used in
[21, 12, 13]. Statistics of these datasets are listed in Table 1. 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. F.1.

$\bullet$ Real Dataset: We additionally use real-world datasets from the
Amazon-photos co-purchase network [19] and ogbn-arxiv [25]. In the Amazon
dataset, each node corresponds to a product, edges correspond to 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 a citation network. The nodes are all computer science arXiv
papers indexed by MAG [25]. Each directed edge represents that one paper cites
another. The features are word embeddings of the title and the abstract
computed by the skip-gram model [15]. The labels are subject areas. Since the
class labels in these datasets are not based on presence or absence of motifs,
the corresponding cells in Table 1 are marked as “NA”.

###  4.2 Baselines

We benchmark InduCE against the state-of-the-art baselines of (1) CF-
GnnExplainer [13], (2) Cf2 [21], and (3) Gem [12]. In addition, we also
compare against the state-of-the-art factual explainer (4) PGExplainer 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 [13, 21, 12].
Finally, we also compare against (5) Random perturbations. While Cf2 and CF-
GnnExplainer are transductive, Gem and PGExplainer are inductive. The codebase
of all algorithms have been obtained from the respective authors.

We do not consider [34] and [4] since they are limited to graph
classification. We omit GnnExplainer[32], since both Cf2 and CF-GnnExplainer
outperformed GnnExplainer. Further, we do not study Bacciu et al. [3] since it
uses internal representations of the black-box Gnn model to exploit domain-
specific knowledge. We focus on a domain-agnostic setting. Furthermore, unlike
in [3], we do not assume access to the embeddings of the black-box model.
Hence, our algorithm is also applicable in situations where the internal
details of the Gnn are hidden from the end-user due to proprietary reasons.

####  4.2.1 Performance measures

To quantify performance, we use the standard measures from the literature
[13].

  * •

Fidelity: Fidelity is the percentage of nodes whose labels do not change when
the edges produced by the explainer (algorithm) are perturbed. Lower fidelity
is better. Furthermore, it may be argued that fidelity is the most important
metric among the three measures.

  * •

Size: Explanation size is the number of edges perturbed for a 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 a non-
zero class label only if they belong to a motif, the explanation for nodes
should be edges in the motif itself. Note that accuracy is computable only on
the benchmark datasets since they include ground-truth explanations.

  * •

Sparsity: Sparsity is defined as the proportion of edges from
$\mathcal{N}^{\ell}_{v}$, i.e., the $\ell$-hop neighbourhood of the target
node, that is retained in the counter-factual $v$ [35]; a value close to $1$
is desired. Since sparsity is inversely correlated to size, we present
sparsity values of our experiments in App. G.

Other settings: Details of additional experimental settings regarding the
counterfactual task, the black-box Gnn, training and inference are given in
App. F.3.

Method | Tree-Cycles | Tree-Grid | BA-Shapes
---|---|---|---
Fid.(%) $\downarrow$ | Size $\downarrow$ |  Acc.(%) $\uparrow$ |  Fid.(%) $\downarrow$ |  Size $\downarrow$ |  Acc.(%) $\uparrow$ |  Fid.(%) $\downarrow$ |  Size $\downarrow$ | Acc.(%)$\uparrow$
Random | 0 | 3.18 ±2.32 | 67.08 | 0 | 8.32 ±4.95 | 73.44 | 0 | 283.97 ±272.76 | 15.57
CF-GnnEx | 49.0 | 1.05 ±0.23 | 100 | 10 | 1.37 ±0.58 | 92.24 | 37.0 | 1.31 ±0.55 | 95.83
Cf2 | 76.38 | 4.18 ±1.89 | 67.68 | 98.45 | 5.5 ±1.5 | 44.64 | 23.68 | 4.10 ±1.64 | 70.54
InduCE (transductive) | 0 |  1.01 ±0.12 | 98.61 | 0 |  1.02 ±0.12 | 97.67 | 0 |  1.30 ±0.90 | 95.31
CF-GnnEx $++$ | 100 | NULL | NULL | 100 | NULL | NULL | 38.16 | 6315.44 ±9916.50 | 17.36
Cf2 $++$ | 13.89 | 28.34 ±7.56 | 19.24 | 28.68 | 12.90 ±7.71 | 27.44 | 100 | NULL | NULL
InduCE (transductive)$--$ | 0 | 1.40 ±1.49 | 81.94 | 0 | 1.24 ±0.43 | 92.64 | 6.6 | 1.42 ±1.49 | 83.22

Table 2: Results for transductive methods: Lower fidelity, smaller size, and
higher accuracy are desired. The best results are highlighted in bold. Fid.
denotes fidelity and Acc. denotes Accuracy.

Method | Tree-Cycles | Tree-Grid | BA-Shapes
---|---|---|---
Fid.(%) $\downarrow$ | Size $\downarrow$ |  Acc.(%) $\uparrow$ |  Fid.(%) $\downarrow$ |  Size $\downarrow$ |  Acc.(%) $\uparrow$ |  Fid.(%) $\downarrow$ |  Size $\downarrow$ | Acc.(%)$\uparrow$
PGExplainer | 34.72 | 6 | 76.85 | 41.09 | 6 | 66.93 | 6.58 | 6 | 89.25
Gem | 95 | 6 | 88.97 | 97 | 6 | 94.57 | 17 | 6 | 98.44
InduCE (inductive) | 0 |  2.31 ±1.44 | 96.65 | 0 |  4.67 ±2.91 | 91.05 | 2.6 |  4.37 ±3.53 | 64.40
InduCE (inductive) – – | 36.3 | 1.67 +- 0.90 | 90.32 | 16.3 | 6.38 ±3.74 | 86.31 | 40.8 | 3.37 ±3.04 | 56.08

Table 3: Results for inductive methods. The best result in each category is
highlighted in bold.

###  4.3 Quantitative Results on Benchmark Datasets

Transductive methods: Table 2 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 in all settings. For Tree-Cycles and BA-
Shapes, CF-GnnExplainer is producing better accuracy. However, we note that
its fidelity is much worse, indicating it fails to find an explanation more
frequently. More generally, while CF-GnnExplainer consistently achieves the
lowest size among the baselines, its fidelity is much worse. This indicates
that CF-GnnExplainer is able to solve only the easy cases and hence the low
size is deceptive as it did not solve the difficult ones.

Inductive methods: Table 3 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 recall that the
explanation size is fixed in Gem and PGExplainer since they work with fixed
budgets.

r3.4in

(a) Inductive (b) Transductive

Figure 3:  The distributions of the edit size and their internal composition
of edge additions and deletions by InduCE on the Tree-Cycles dataset.

Transductive vs Inductive:  We further compare the inductive version (Table 3)
of our method, InduCE with the transductive baselines (Table 2). While the
transductive methods have a clear advantage of re-training the model instance
wise, the results produced by InduCE-inductive are comparable. As noted
earlier, although CF-GnnExplainer achieves better size than InduCE-inductive,
its fidelity is much worse indicating that the low size is a manifestation 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).

Impact of edge additions: We seek answers to two key questions: (1) How much
does the performance of InduCE deteriorate if we restrict edge additions? (2)
If we empower the baselines 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 2 and 3 present
these results. It is evident that the deletion-only version produces inferior
results for both the transductive and inductive versions. In Fig. 3, we
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. I). 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 Cf2 with edge
additions, denoted as CF-GnnExplainer $++$ and Cf2 $++$ respectively. 111Gem
is not extendible to additions (See App. F.2 for details), PGExplainer does
not incorporate perturbations with the intent of flipping the label since it
is a factual explainer. Both Cf2 and CF-GnnExplainer use a mask-based
strategy. A mask is a learnable binary matrix of the same dimension as the
$\ell$-hop neighborhood of the target node. By taking an element-wise 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 CF-GnnExplainer drops, while for Cf2,
we see improvement in fidelity in two out of three datasets. Further
investigation into this performance reveals that edge additions significantly
increase the search space of possible perturbations (See Table H in Appendix).
A 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 of perturbations is selected based
on their marginal gains. This allows better modeling of the combinatorial
nature of counter-factual reasoning.

Overall, the above experiments reveal that both additions, as well as an
algorithm equipped to model large combinatorial spaces, are required to
perform well.

Additional experiments: App. H contains further empirical data on (1) the
impact of heuristic features and (2) the choice of Gnn architecture in the MDP
on performance. Experiments on counterfactual size vs accuracy trade-off are
given in App. J.

###  4.4 Quantitative Results on Real Datasets

Method |  Fid.(%) $\downarrow$ | Size $\downarrow$
---|---|---
Random | 100 | NULL
CF-GnnExplainer | 100 | NULL
Cf2 | 60 | 13.7 +- 16.98
InduCE (transductive) | 53.50 | 4.72 $\pm$ 4.38

(a) Transductive

Method |  Fidelity(%) $\downarrow$ | Size $\downarrow$
---|---|---
PGExplainer | 100 | NULL
Gem | 100 | NULL
InduCE (inductive) | 93.00 | 6.60 $\pm$ 2.87

(b) Inductive

Table 4:  Results for (a) transductive and (b) inductive methods on the Amazon
dataset. “NULL" denotes that the method could not produce a counterfactual.

Method |  Fid.(%) $\downarrow$ | Size $\downarrow$
---|---|---
CF-GnnExplainer | DNS | DNS
Cf2 | DNS | DNS
InduCE (transductive) | 0 | 1.00 $\pm$ 0.00

(a) Transductive

Method |  Fidelity(%) $\downarrow$ | Size $\downarrow$
---|---|---
PGExplainer | 95.50 | 4
Gem | DNS | DNS
InduCE (inductive) | 78.7 |  3.11 ±3.04

(b) Inductive

Table 5:  Results for (a) transductive and (b) inductive methods on the ogbn-
arxiv dataset. “DNS" denotes that the method could not produce a
counterfactual as it did not scale. Refer to App. K that details reasons on
why these baselines failed to scale on ogbn-arxiv."

In Tables 4a and 4b, we present the results.Consistent with the performance on
benchmark datasets, InduCE continues to outperform all the baselines almost in
both transductive and inductive settings. We note that most of the baselines
failed to produce counterfactuals in Amazon. 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.5 Efficiency

Table 6a presents the inference times of various algorithms. First, the
inductive methods (InduCE, PGExplainer and Gem) are much faster than the
others. Between the inductive methods, PGExplainer is the fastest. InduCE-
inductive is slower since the search space for InduCE is larger due to
accounting for both edge additions and deletions. Second, InduCE-inductive is
up to $79$ times faster than the transductive methods such as CF-GnnExplainer
and Cf2. This speed-up is a result of only doing forward passes through the
neural policy network, whereas, transductive methods learn the model
parameters on each node separately. Even the transductive version of InduCE is
faster than the other transductive methods for Tree-Cycles and Tree-Grid.

Scalability against graph size: Table 6b presents the inference time per node
across all datasets. We observe that InduCE scales to million-sized networks
such as ogbn-arxiv. We observe that the growth of the running time is closely
correlated with the neighbourhood density, i.e., the average degree of the
graph, and not the graph size. In a Gnn with $\ell$ layers, only the
$\ell$-hop neighborhood of the target node matters.

Method | Tree-Cycles | Tree-Grid | BA-Shapes
---|---|---|---
PGExplainer | 0.41 | 0.62 | 0.38
Gem | 0.16 | 0.73 | 8.64
CF-GnnEx | 1295.66 | 2382.51 | 3964.36
Cf2 | 165.56 | 249.92 | 2565.87
InduCE (ind.) | 4.36 | 17.64 | 68.33
InduCE (trans.) | 66.08 | 331.58 | 6546.48

(a) Efficiency

Dataset | #Nodes | #Edges | Avg. degree | Time/node (ms)
---|---|---|---|---
Tree-Cycles | 871 | 1,950 | 2.23 | 60.56
Tree-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 6: (a) Running times (in seconds) of each algorithm on entire test set.
(b) Scalability against various graph properties.

###  4.6 Case Study: Counter-factual Visualization

In this section, we visually showcase how counter-factual explanations reveal
vulnerabilities of Gnns and why edge additions are important.

Revealing Gnn vulnerabilities: A sample counterfactual explanation by various
algorithms on Tree-Cycles dataset is provided in Fig. 4a. The target node is
part of a motif (6-cycle) and therefore the expected counter-factual
explanation is to make it a non-member of a 6-cycle. CF-GnnExplainer correctly
finds on 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-motif node although it is not. Furthermore, this limitation is uncovered
only since InduCE can add edges. Similar observations in other datasets are
available in Figs. Ea-Eb in Appendix.

Impact of additions: In Fig. 4b top-left, we share an example where InduCE
flips the label of a target node (orange) by making it part of the 6-node
cycle motif through edge addition. Since baseline strategies are only capable
of deletes, they fail to flip the label of such nodes. Further in the top-
right (Tree-Grid) example, we see InduCE breaks the grid motif and connects
the target node (orange) to a non-motif neighbour, hence colluding its
embeddings and flipping its label. These examples showcase the importance of
edge addition to intuitively explain how the black-box Gnn works.

(a) Tree-Cycles

(b) Impact of additions

Figure 4: Visualization of counterfactual explanations for the same node
(orange) produced by different methods. Semantically, the node label should
flip if it is not a part of the motif. (a) Counterfactual explanation for
Tree-Cycles Dataset, (b) Counterfactuals predicted by InduCE.

##  5 Conclusion

The ability to explain predictions is critical towards making a model
trustworthy. In this work, we proposed InduCE to 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 counterfactual space exploration and transductivity.
InduCE provides a boost to counterfactual analysis on Gnns by unleashing the
power of edge additions and inductively predicting explanations on unseen
nodes. The proposed features not only lead to better explanations but also
provide a significant speed-up allowing InduCE to perform counterfactual
analysis at scale.

Limitations: InduCE performs counter-factual reasoning by perturbing only the
topological space. In future, we will consider characterization of the node
feature space and explore the joint combinatorial space of topology and
features.

## References

  * [1] Carlo Abrate and Francesco Bonchi.  Counterfactual graphs for explainable classification of brain networks.  In KDD, page 2495–2504, 2021.
  * [2] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Lio, and Andrea Passerini.  Global explainability of GNNs via logic combination of learned concepts.  In The Eleventh International Conference on Learning Representations, 2023.
  * [3] Davide Bacciu and Danilo Numeroso.  Explaining deep graph networks via input perturbation.  IEEE Transactions on Neural Networks and Learning Systems, pages 1–12, 2022.
  * [4] Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang.  Robust counterfactual explanations on graph neural networks.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
  * [5] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM (JACM), 45(4):634–652, 1998.
  * [6] Matthias Fey and Jan Eric Lenssen.  Fast graph representation learning with pytorch geometric.  arXiv preprint arXiv:1903.02428, 2019.
  * [7] 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.
  * [8] Mingjian Jiang, Zhen Li, Shugang Zhang, Shuang Wang, Xiaofeng Wang, Qing Yuan, and Zhiqiang Wei.  Drug–target affinity prediction using graph neural network and contact maps.  RSC advances, 10(35):20701–20712, 2020.
  * [9] Jeroen Kazius, Ross McGuire, and Roberta Bursi.  Derivation and validation of toxicophores for mutagenicity prediction.  Journal of medicinal chemistry, 48(1):312–320, 2005.
  * [10] 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.
  * [11] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [12] Wanyu Lin, Hao Lan, and Baochun Li.  Generative causal explanations for graph neural networks.  In International Conference on Machine Learning, pages 6666–6679. PMLR, 2021.
  * [13] Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri.  Cf-gnnexplainer: Counterfactual explanations for graph neural networks.  In AISTATS, pages 4499–4511, 2022.
  * [14] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang.  Parameterized explainer for graph neural network.  Advances in neural information processing systems, 33:19620–19631, 2020.
  * [15] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
  * [16] 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, Quoc V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean.  Chip placement with deep reinforcement learning.  CoRR, abs/2004.10746, 2020.
  * [17] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov.  Interpreting graph neural networks for nlp with differentiable edge masking.  arXiv preprint arXiv:2010.00577, 2020.
  * [18] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li.  Reinforcement learning enhanced explainer for graph neural networks.  In NeurIPS 2021, December 2021.
  * [19] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of graph neural network evaluation.  arXiv preprint arXiv:1811.05868, 2018.
  * [20] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackermann, et al.  A deep learning approach to antibiotic discovery.  Cell, 180(4):688–702, 2020.
  * [21] Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang.  Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning.  In Proceedings of the ACM Web Conference 2022, WWW ’22, page 1018–1027, 2022.
  * [22] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In International Conference on Learning Representations, 2018.
  * [23] 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.
  * [24] Minh N Vu and My T Thai.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  arXiv preprint arXiv:2010.05788, 2020.
  * [25] Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia.  Microsoft Academic Graph: When experts are not enough.  Quantitative Science Studies, 1(1):396–413, 2020.
  * [26] Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-seng Chua.  Causal screening to interpret graph neural networks.  2021\.
  * [27] Geemi P Wellawatte, Aditi Seshadri, and Andrew D White.  Model agnostic generation of counterfactual explanations for molecules.  Chemical science, 13(13):3697–3705, 2022.
  * [28] Ronald J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Mach. Learn., 8(3–4):229–256, may 1992.
  * [29] Jiacheng Xiong, Zhaoping Xiong, Kaixian Chen, Hualiang Jiang, and Mingyue Zheng.  Graph neural networks for automated de novo drug design.  Drug Discovery Today, 26(6):1382–1393, 2021.
  * [30] Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Lió.  Global concept-based interpretability for graph neural networks via neuron analysis.  2023\.
  * [31] 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, page 974–983, 2018.
  * [32] 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.
  * [33] 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 on Knowledge Discovery & Data Mining, pages 430–438, 2020.
  * [34] 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 on Knowledge Discovery & Data Mining (KDD), pages 430–438, 2020.
  * [35] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji.  Explainability in graph neural networks: A taxonomic survey.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022\.
  * [36] Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji.  On explainability of graph neural networks via subgraph explorations.  In ICML, pages 12241–12252. PMLR, 2021.

## Appendix

Method | Explainability Paradigm | Additions | Deletions | Inductive | # explainers required
---|---|---|---|---|---
GNNExplainer[32] | Factual | ✗ | ✓ | ✗ | $N$
GraphMask[17] | Factual | ✗ | ✓ | ✗ | $N$
Causal Screening[26] | Factual | ✗ | ✓ | ✗ | $N$
SubgraphX[36] | Factual | ✗ | ✓ | ✗ | $N$
PGM-Explainer[24] | Factual | ✗ | ✓ | ✗ | $N$
PGExplainer[14] | Factual | ✗ | ✓ | ✓ | $1$
GEM[12] | Counterfactual | ✗ | ✓ | ✓ | $1$
CF-GNNExplainer[13] | Counterfactual | ✗ | ✓ | ✗ | $N$
CF2[21] | Counterfactual + Factual | ✗ | ✓ | ✗ | $N$
InduCE (Ours) | Counterfactual | ✓ | ✓ | ✓ | $1$

Table G: Comparison on properties of common perturbation-based GNN explainers. The last column shows the number of required explainers for a graph with $N$ nodes. Dataset | k-hop | #additions | #deletions | ratio (#additions/#deletions)
---|---|---|---|---
Tree-cycles | 4 | 18313 | 1105 | 16.57
Tree-grid | 4 | 98942 | 3960 | 24.98
BA-shapes | 4 | 3140886 | 47580 | 66.01
Amazon-Photos | 4 | 12144800 | 432160 | 28.10
ogbg-arxiv | 3 | 354496362 | 524330 | 676.09
Table H: Ratio of no. of additions to deletions of datasets.

(a) Tree-Grid

(b) BA-Shapes

Figure E: Visualization of counterfactual explanations for the same node
(orange) produced by different methods. Semantically, the node label should
flip if it is not a part of the motif, i.e., (a) $3\times 3$-grid, and the (b)
the house respectively. CF-GnnExplainer is unable to find a counterfactual in
(b). Algorithm 1 Training pipeline of InduCE.

Input: Graph $\mathcal{G}$, Gnn $\Phi$, Train set $\mathcal{V}_{tr}$,
perturbation budget $\delta$, number of episodes $M$

Output: Policy $\Pi$

1:$\mathcal{V}_{batch}\ \leftarrow\
\\{\mathcal{V}_{1},\mathcal{V}_{2}\,\dots,\mathcal{V}_{B}|\cup_{i=1}^{\mathbb{B}}\mathcal{V}_{i}=\mathcal{V}_{tr}\\}$
$\triangleright$ Random partitioning instances of $\mathcal{V}_{tr}$ into $B$
batches

2:$\Pi\leftarrow$ initialize with random parameters

3:for all $e\ \in[1,M]$ do

4: for all $\mathcal{V}_{b}\in\mathcal{V}_{batch}$ do

5: for all $v\in\mathcal{V}_{b}$ do

6: $t\leftarrow 0$

7: while $L_{\Phi}(\mathcal{G}^{0},v)=L_{\Phi}(\mathcal{G}^{t},v)\And
t<\delta$ do

8: compute $\mathcal{S}_{v}^{t}$

9: $a^{t}\leftarrow\ \textrm{sample from}\
\Pi(\mathcal{S}_{v}^{t},\mathcal{P}^{t})$

10: $\mathcal{G}_{v}^{t+1}\leftarrow\ \textrm{perturb}\ \mathcal{G}_{v}^{t}\
\textrm{with edge}\ a^{t}$

11: $\mathcal{R}_{v}^{t}\leftarrow\ \textrm{compute reward using Eq.10}$

12: $\mathcal{R}_{dis,v}^{t}\leftarrow\ \textrm{compute discounted rewards
using Eq.\ref{eq:dis_reward}}$

13: $\mathcal{\tilde{R}}_{dis,v}^{t}\leftarrow\ \textrm{normalize discounted
rewards using Eq.\ref{eq:norm_reward}}$

14: $t\leftarrow t+1$

15: Backpropagate to minimize loss using Eq. 17

16:Return $\Pi$

Algorithm 2 Test pipeline of InduCE.

Input: Graph $\mathcal{G}$, Gnn $\Phi$, Test set $\mathcal{V}_{test}$, maximum
perturbation budget $\delta$

Output: Counterfactual explanations CF

1:$CF=\phi$

2:$\Pi\leftarrow$parameters of pre-trained policy

3:for all $v\in\mathcal{V}_{test}$ do

4: $Exp\leftarrow\emptyset$

5: $t\leftarrow 0$

6: while $L_{\Phi}(\mathcal{G}^{0},v)=L_{\Phi}(\mathcal{G}^{t},v)\And
t<\delta$ do

7: compute $\mathcal{S}_{v}^{t}$

8:
$a^{*}\leftarrow\arg\max_{a\in\mathcal{P}^{t}}\Pi(\mathcal{S}_{v}^{t},\mathcal{P}^{t})$

9: $\mathcal{G}_{v}^{t+1}\leftarrow\ \textrm{perturb}\ \mathcal{G}_{v}^{t}\
\textrm{with edge}\ a^{*}$

10: $t\leftarrow t+1$

11: if $L_{\Phi}(\mathcal{G}^{0},v)\neq L_{\Phi}(\mathcal{G}^{t},v)$ then

12: $CF=CF\cup Exp$

13:Return CF

###  A Proof of Theorem 1

Proof. To prove NP-hardness of the problem we reduce it from the classical set
cover problem.

######  Definition 1 (Set Cover [5])

Given a collection of subsets $\mathcal{S}=\\{S_{1},\cdots,S_{m}\\}$ from a
universe of items $U=\\{u_{1},\cdots,u_{n}\\}$ identify the smallest
collection of subsets $\mathbb{\mathcal{A}^{*}}\subseteq\mathcal{S}$ covering
the set $U$, i.e.,

$\mathcal{A}^{*}=\arg\min_{\mid\mathcal{A}\mid,\mathcal{A}\subseteq\mathcal{S}}\bigcup_{\forall
S_{i}\in\mathbb{\mathcal{A}}}S_{i}=U$ (14)

We show that given any instance of a set cover problem
$\langle\mathcal{S},U\rangle$, it can be mapped to Prob. 1. Specifically, we
construct a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where
$\mathcal{V}=N\cup\mathcal{S}\cup U$. Here, $N$ is an arbitrary set of nodes.
In addition, we have a node corresponding to each set $S\in\mathcal{S}$ and
each item $u\in U$. There is an edge between two nodes
$v_{i},v_{j}\in\mathcal{V}$ if $v_{i}$ corresponds to some set
$S\in\mathcal{S}$, $v_{j}$ corresponds to item $u\in U$, and $u\in S$. There
are no edges among nodes in $N$. The Gnn $\Phi$ predicts the label of any node
$v\in N$ as $1$ if all nodes from $U$ are reachable from $v$, otherwise $0$.
Furthermore, let the set of allowed perturbations be
$\mathcal{V}_{c}=\\{(v_{i},v_{j})\mid v_{i}\in N,v_{j}\in\mathcal{S}\\}$.
Given any $v\in N$, with $L_{\Phi}(\mathcal{G},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
$\mathcal{S}$.

With this construction, only edge additions are allowed. Now it is easy to see
that the smallest edge set flipping the label of $v$ corresponds to connecting
$v$ to nodes in $\mathcal{A}^{*}$, where $\mathcal{A}^{*}$ is the solution for
the set cover problem. $\hfill\square$.

###  B Discounted Rewards

The objective of the policy $\Pi$ is to find minimal counterfactual
explanations for Gnns using the reward function mentioned in Eq 10. However,
we can observe that in that equation, the marginal reward at each 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
$\mathcal{T}_{v}$ in order to penalize larger counterfactual size, thus we use
discounted rewards (Eq 15) with $\gamma$ being the discount factor to achieve
the objective. Since we want minimal explanation size, we use small values of
$\gamma$ (Refer App. F.3).

$\mathcal{R}^{t}_{dis,v}(a_{t})=\sum_{i=0}^{\delta}\gamma^{i}\mathcal{R}_{v}^{t+i+1}(a_{t})$
(15)

here $\delta$ 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 a baseline,
$b(S_{v}^{t})$ 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.

$\mathcal{\tilde{R}}^{t}_{dis,v}(a_{t})=\frac{\mathcal{R}^{t}_{dis,v}(a_{t})-\mathcal{\bar{R}}^{t}_{dis,v}(a_{t})}{\max(\sigma{(\mathcal{R}^{t}_{dis,v}(a_{t})),\
c)}}$ (16)

where $\sigma{(\mathcal{R}^{t}_{dis})}$ is the standard deviation, $c$ is a
constant. The optimized version of the loss function(Eq 12) is in App. C.

###  C Batching

Equation 12 takes an average gradient over all examples in 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 use normalized
discounted rewards in the loss function(Refer Eq. 17).

$\scriptsize\mathcal{J}(\Pi)=-\frac{1}{\mathcal{V}_{batch}}\left(\sum_{\forall
v\in\mathcal{V}_{batch}}\left(\sum_{t=0}^{\lvert\mathcal{T}_{v}\rvert}\log{p^{t}_{a,v}}\mathcal{\tilde{R}}^{t}_{dis,v}(a_{t})+\eta
Ent(\mathcal{P}^{t}_{v})\right)\right)$ (17)

###  D InduCE: Algorithm

The training and test pipelines of InduCE are provided in Alg. 1 and Alg. 2
respectively. As evident from Alg. 2, using InduCE we can train once and test
on unseen nodes using just a forward pass through the policy network which
makes it more efficient than the transductive baselines (recall Table 6a).

Dataset | Train accuracy(%) | Test Accuracy(%)
---|---|---
Tree-cycles | 91.23 | 90.86
Tree-grid | 84.34 | 87.44
BA-shapes | 96.61 | 98.57
Amazon-Photos | 89.59 | 88.75
ogbn-arxiv | 71.59 | 55.07
Table I: Accuracy of Gnn $\Phi$ on the three benchmark datasets.

###  E Complexity of InduCE

Train-Phase: Training the policy network involves four key steps, i.e.,
compute the state, forward pass through the policy network, sample and take
action, and compute the marginal reward of the action. Among the above, state
computation and performing the action take $\mathcal{O}(1)$ time. Time taken
by a forward pass through the policy network involves a combination of
computing node embeddings using Gat and computing a score for each action in
the action space $\mathcal{P}^{t}$ through the MLP. Forward pass through the
Gat takes $\mathcal{O}(K(\mathcal{|V|}h_{i}h_{d}+\mathcal{|E|}h_{d}))$ [22]
where $K$, $h_{i}$ and $h_{d}$ are the number of Gat layers, input and hidden
dimensions respectively. Action score computation using MLP takes
$\mathcal{O}(|\mathcal{P}^{t}|h_{m}(h_{d}+(J-2)h_{m}+1)))$, $J$ and $h_{m}$
are number of MLP layers and hidden dimensions. Computing the reward function
involves taking a forward pass through a GCN which takes
$\mathcal{O}(L|\mathcal{E}|h_{i}h_{d}\mathcal{|C|})$ time, here $L$ and
$\mathcal{|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
$V_{tr}$ until a maximum of $\delta$ time steps. Combining the above costs,
treating $J$, $K$, $L$, $h_{i}$, $h_{d}$, $h_{m}$ and $\mathcal{|C|}$ as fixed
constants which have small values, and with the knowledge that
$|\mathcal{P}^{t}|=\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ (refer Eq. 6),
the complexity with respect to the input parameters reduces to
$\mathcal{O}(|\mathcal{V}_{tr}|M\delta(\mathcal{|V|}+\mathcal{|E|}))$.

Test-Phase: The test phase involves state computation, forward pass through
the policy network, and performing the action with highest probability for a
maximum of $\delta$ time-steps for every node in the test set
$\mathcal{V}_{test}$. Therefore following the discussion in the training
phase, the time complexity of test phase is
$\mathcal{O}(|\mathcal{V}|_{test}|\delta(\mathcal{|V|}+\mathcal{|E|}))$.

Detailed algorithm of InduCE is given in App. D.

###  F 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.

####  F.1 Benchmark datasets

  * •

BA-SHAPES: The base graph is a Barabasi-Albert (BA) graph. The motifs are
house-shaped structures made up of 5 nodes (Refer Figure Eb). 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.

  * •

TREE-CYCLES: The base graph is a binary tree with 6-node cycles used as motifs
(Refer Figure 4a). 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 base graph is a binary tree and the motif is a $\mathbf{3\times
3}$ grid connected to random tree nodes (Refer Figure Ea). Just like tree-
cycles dataset binary class labelling has been done.

####  F.2 Baselines

  * •

CF-GnnExplainer [13]: Being a transductive method for counterfactual
explanations, it learns a new set of parameters for every node and cannot be
used to explain unseen nodes.

  * •

Cf2 [21]: While being transductive in nature, it combines both counterfactual
and factual properties to give an explanation. Cf2 tunes the parameter
$\alpha$ to weigh the contribution of factual explanations. We compare Cf2
with $\alpha=0$ where it becomes as a counterfactual explainer.

  * •

Gem [12]: This is inductive by nature, however, it only considers edge
deletions. It has a limitation that it learns a counterfactual explanation
model where the number of perturbations is fixed, i.e., it does not minimize
the number of perturbations with the sole focus on flipping the label. We use
the default size of $6$ as the perturbation size as recommended by the
authors.

Note that Gem is not extendable to include edge additions. Specifically, GEM
has a distillation process that generates the ground truth. Distillation
involves removing every edge in a node’s neighbourhood iteratively and seeing
its effect on the loss. The deletions are then sorted based on their effect on
the loss. The top-$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 to create the distilled ground truth does not scale. In
addition, it is also unclear how to set $k$ in the presence of additions.

  * •

PGExplainer [14]: This method is also inductive and only considers edge
deletions. It is a 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 Amazon-Photos and ogbn-arxiv, respectively.

  * •

Random:  We use the same baseline as used in [13]. 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.

####  F.3 Training and Parameters

##### Counter-factual task:

We provide a node that is part of a motif to the counterfactual explainer, and
the the task is to flip its label by recommending changes in the graph. All
nodes that are part of a motif, are given a specific label and non-motif nodes
are given a different label. Since the nodes are always chosen from motifs,
the explanation is the motif itself. This setup is identical to Cf2 and CF-
GnnExplainer.

##### The Gnn model $\Phi$:

We use the same Gnn model used in CF-GnnExplainer and Cf2. Specifically, it is
a Graph Convolutional Networks trained on each of the datasets. Each model has
3 graph convolutional layers, with 20, 128 and 256 hidden dimensions for the
benchmarking datasets, Amazon-photos and ogbn-arxiv respectively. The non-
linearity used is relu 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 datasets. 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-Photos dataset. We choose one random node as the central
node and took its $3-$hop neighbourhood in our dataset. Amazon Photos has an
average degree of 13, hence, the $3-$hop neighborhood covers a 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 $\Phi$ for
each dataset is mentioned in Table I.

Training, Inference and Parameters:  For InduCE and Gem, we use a
train/evaluation split of 80/20 on the benchmark 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 CF-GnnExplainer and Cf2 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 $\beta=0.5$ so
as to give equal weight to the predict loss and distance loss (see Eq. 10). We
use different values of $\gamma\in\\{0.4,0.6\\}$ and find the best performance
at $\gamma=0.4$ for the inductive setting and $\gamma=0.6$ for the
transductive setting with a maximum perturbation budget $\delta=15$. We use
maximum number of episodes $\mathbb{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$ as the activation function. We use three different values
for $\eta\in\\{0.1,0.01,0.001\\}$ and $\eta=0.1$ improves the performance due
to higher weight for exploration.

Method | Sparsity (Tree-Cycles) | Sparsity (Tree-Grid) | Sparsity (BA-Shapes) | Amazon-photos | ogbn-arxiv
---|---|---|---|---|---
CF-GnnExplainer | 0.93 | 0.95 | 0.99 | NULL | DNS
Cf2 | 0.52 | 0.59 | 0.92 | 0.99 | DNS
InduCE\- transductive | 0.92 | 0.96 | 0.98 | 0.99 | 0.78

Table J:  Comparison of "sparsity" of counterfactuals predicted by
transductive methods. “NULL” means the baseline could not find a
counterfactual. “DNS” means that the baseline did not scale.

Method | Sparsity (Tree-Cycles) | Sparsity (Tree-Grid) | Sparsity (BA-Shapes) | Amazon-photos | ogbn-arxiv
---|---|---|---|---|---
PGExplainer | 0.34 | 0.64 | 0.61 | NULL | 0.66
Gem | 0.54 | 0.77 | 0.88 | NULL | DNS
InduCE\- inductive | 0.81 | 0.83 | 0.98 | 0.99 | 0.64

Table K: 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. Policy Variant | Tree-Cycles
---|---
Fid.(%) $\downarrow$ |  Size $\downarrow$ |  Acc.(%) $\uparrow$
InduCE-inductive-Gcn | 0 | 2.62 ±1.52 | 78.84
InduCE-inductive-Gat | 0 | 1.99 ±1.00 | 97.47
InduCE-transductive-Gcn | 0 | 1.08 ±0.27 | 96.84
InduCE-transductive-Gat | 0 | 1.08 ±0.27 | 96.20
Table L: Importance of attention in the Gnn component of InduCE.

###  G Additional Results on Sparsity of Counterfactuals

Recall, sparsity is defined as the proportion of edges in
$\mathcal{N}^{l}_{v}$, i.e., the $\ell$-hop neighbourhood of the target node
$v$. Since counterfactuals are supposed to be minimal, a value close to 1 is
desired. We compare InduCE with its baselines on sparsity in Tables J and K.
We observe that InduCE produces better or comparable explanations in terms of
sparsity. In Table K we 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 5b).
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 J
as its fidelity is much higher than the latter (Recall Table 2).]

Method | Tree-Cycles | Tree-Grid | BA-Shapes
---|---|---|---
Fid.(%) $\downarrow$ |  Size $\downarrow$ |  Acc.(%) $\uparrow$ |  Fid.(%) $\downarrow$ |  Size $\downarrow$ |  Acc.(%) $\uparrow$ |  Fid.(%) $\downarrow$ |  Size $\downarrow$ |  Acc.(%) $\uparrow$
Features only | 0 | 3.12 ±1.96 | 80.05 | 0 | 4.50 ±3.16 | 73.12 | 18.4 | 3.62 ±3.46 | 70.29
Features + D | 0 | 2.56 ±1.73 | 65.74 | 0 | 3.71 ±2.51 | 84.26 | 9.2 | 4.02 ±4.27 | 98.89
Features + E | 0 | 2.24 ±1.15 | 72.69 | 0 | 3.37 ±2.22 | 94.63 | 68.4 | 1.25 ±0.83 | 86.25
Features + OH | 0 | 3.19 ±1.83 | 79.70 | 2.3 | 4.10 ±3.13 | 87.17 | 28.9 | 4.63 ±3.41 | 32.75
Features + D + E | 0 | 2.81 ±1.55 | 85.19 | 0 | 3.12 ±1.96 | 84.77 | 48.7 | 2.43 ±2.65 | 63.71
Features + D + OH | 0 | 2.65 ±1.58 | 69.31 | 0 | 3.16 ±2.21 | 92.02 | 1.3 | 3.62 +- 2.45 | 62.08
Features + E + OH | 0 | 2.62 ±1.52 | 78.84 | 0 | 3.47 ±2.28 | 89.15 | 27.6 | 4.2 ±3.02 | 56.00
Features + D + E + OH | 0 | 2.31 ±1.44 | 96.65 | 0 | 4.67 ±2.91 | 91.05 | 2.6 | 4.37 ±3.53 | 64.4

Table M: 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 each of these features.
Our proposed method InduCE is superior when it uses all the features.

###  H Ablation Study

To infuse more information about the local graph structure and and its
statistics, we use several heuristic 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 M summarises
the findings. Our method is most consistent when it 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.
Gcn 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 L. We see that Gat significantly
outperforms Gcn in the inductive version and thereby justifying our choice.

Heuristic Features: Table M 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 as we
see in Table 1 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.

###  I Additional Results on Counterfactual Size Distributions

In figures F and G we observe the distributions of edit distance between the
original and the counterfactual $h$-hop neighbourhood of instances in Tree-
Grid and BA-Shapes datasets respectively. As observed both in 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 are tailored instance by
instance. InduCE-inductive however with a minor trade-off in the
counterfactual size, provides a comparable performance to InduCE-transductive
(recall Tables 2 and 3) while providing a speed-up of $79$x over all the
transductive baselines (recall Table 6a). We further conduct experiments on
how the accuracy of the explainer is affected with increasing counterfactual
size in App. J.

(a) Inductive (b) Transductive

Figure F:  The distributions of the edit size and their internal composition
of edge additions and deletions by InduCE on the Tree-Grid dataset.

(a) Inductive (b) Transductive

Figure G:  The distributions of the edit size and their internal composition
of edge additions and deletions by InduCE on the BA-Shapes dataset.

###  J Size vs. Accuracy Trade-off

The accuracy vs. counterfactual size trade-off for InduCE in Table N and O. We
observe that with higher size, the accuracy decreases. Recall, we use
benchmark datasets with ground-truth explanations where a node belongs to a
particular class if it belongs to a 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 flip the
label till a large set of edits are made.

Size | Acc. % (Tree-Cycles) | Acc. % (Tree-Grid) | Acc.% (BA-Shapes)
---|---|---|---
1 | 100 | 100 | 100
3 | 94 | 97 | 100
5 | 73 | 89 | 100
6 | 83 | NA | NA
7 | 86 | 88 | 100
10 | NA | 80 | 100
15 | NA | 73 | 73

Table N:  Counterfactual Size vs. 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) | Acc. % (BA-Shapes)
---|---|---|---
1 | 97 | 98 | 100
2 | 100 | 100 | 100
6 | NA | NA | 50
7 | NA | NA | 57

Table O:  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 was not present.

###  K Baselines for “ogbn-arxiv” Dataset.

The baselines do not scale for Ogbn-arxiv dataset. We describe the details as
follows. Ogbn-arxiv is a million-sized node prediction dataset with 169,343
nodes and 1,166,243 edges. Cf2 and Gem do not scale (Recall Tables 5a and 5b)
on this dataset since they employ computations on a dense adjacency matrix,
which require $\mathcal{O}(n^{2})$ space, where $n$ is the number of nodes in
the graph. For a million-sized graph, this leads to memory overflow. Adapting
to a sparse adjacency matrix requires non-trivial changes to the source code.

CF-GnnExplainer extracts the $k-$hop neighbourhood of a target node at runtime
and adapts to sparse adjacency matrices more easily. CF-GnnExplainer’s
algorithm is model-agnostic, however, the code-base is suitable for its
customized black-box and cannot be trivially extended to any other black-box.
The explainer loads the black-box weights into itself before freezing them,
assuming that the black-box uses the same architecutre 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’s code from scaling for ogbn-arxiv(Recall Table 5a). We use
PyTorch-geometric’s [6] standard GCNConv layers [11] that are compatible with
sparse adjacency matrices to scale the black-box Gnn to the million-sized
graph. InduCE’s code is written in a model-agnostic fashion. Any black-box Gnn
which employs log SoftMax non-linearity at the last layer is compatible with
InduCE.