Empowering Counterfactual Reasoning over Graph Neural Networks through
  Inductivity
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.
Samidha Verma, Burouj Armgaan, Sourav Medya, Sayan Ranu
# Empowering Counterfactual Reasoning over Graph Neural Networks through Inductivity

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

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 InduceE (Inductive Counter-factual Explanations), that addresses the above limitations of existing counterfactual reasoners. We propose InduceE 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. (SS 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 (SS 2. As a heuristic, we _learn_ to solve this combinatorial optimization problem through reinforcement learning powered by _policy gradients_[28] (SS 3).
* **Empirical validation:** Through extensive experiments on benchmark graph datasets, we show that InduceE 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 InduceE's superior performance. Finally, we also

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.
showcase the computation gains obtained due to embracing the inductive paradigm instead of transductive modeling (SS 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.

### 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:

\[\mathbf{S}^{t}_{v}=\left\{\mathbf{x}^{t}_{u}\mid u\in\mathcal{N}^{h}_{v}\right\},\]

 (1)

\[\mathcal{N}^{h}_{v}=\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}=(\mathcal{V},\mathcal{E})\).

The representations of nodes, i.e., \(\mathbf{x}^{t}_{u}\), are constructed using a combination of semantic, topological, and statistical features.
* _Original node Features:_ It is common to encounter graphs where nodes are annotated with features or labels (recall the definition of \(x_{i}\) in SS 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_{u}^{t}=-\sum_{\forall c\in\mathcal{C}}p_{c}\log p_{c}\), 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}_{u}^{t}\).
* _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}\parallel degree_{u}^{t}\parallel e_{u}^{t}\parallel \left(\text{one-hot}\left(L_{\Phi}\left(\mathcal{G}^{t},u\right)\right)\right) \tag{3}\]

Here, \(\parallel\) 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:

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

The action space is the perturbation set: \(\mathcal{P}^{t}=\mathcal{E}_{v,del}^{t}\cup\mathcal{E}_{v,add}^{t}\) (6)

**Reward:** Our objective is to flip the predicted label of target node \(v\) with the minimum number of perturbations in \(\mathcal{N}_{v}^{h}\) 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.

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

In simple terms, \(\mathcal{L}_{v,pred}^{t+1}\) 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_{a,v}^{t}\sim\Pi\left(a\mid\mathcal{S}_{v}^{t}\right)\). We will discuss the computation of \(p_{a,v}^{t}\) in SS 3.2.

### Neural Architecture for Policy Training

To learn \(p_{a,v}^{t}\), we we take the representations in \(\mathbf{S}_{v}^{t}\), and pass them through a neural network comprising of a \(K\)-layered _Graph Attention Network_ (Gat) [22], an MLP, and a final SoftMax layer.

Figure 2: Pipeline of the policy learning algorithm in InduCE. \(\delta\) indicates the maximum number of allowed perturbations.
The Gat learns a \(d\)-dimensional representation \(\mathbf{a}\in\mathbb{R}^{d}\) for each perturbation \(a\in\mathcal{P}_{v}^{t}\). \(\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}_{v}^{t}\). The entire network is trained end-to-end. We next detail each of these components.

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

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

\(\sigma\) is an activation function, \(\alpha_{u,u^{\prime}}^{k}\) 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,

\[e_{u,u^{\prime}}^{k}=\texttt{MLP}(\mathbf{h}_{u}^{k-1}\parallel \mathbf{h}_{u^{\prime}}^{k-1})\text{, where }e_{u,u^{\prime}}^{k}\in\mathbb{R}, \alpha_{u,u^{\prime}}^{k}=\frac{exp\left(e_{u,u^{\prime}}^{k} \right)}{\sum_{\tilde{u}\in\mathcal{N}_{u}^{k}\cup\{u\}}exp\left(e_{u,\tilde{ u}}^{k}\right)}\]

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

\[t(u,v)=\begin{cases}0,&a\in\mathcal{E}_{v,del}^{t}\text{ (Recall Eq. \ref{eq:Gat})}\\ 1,&a\in\mathcal{E}_{v,add}^{t}\text{ (Recall Eq. \ref{eq:Gat})}\end{cases} \tag{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}_{v}^{t}\) as:

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

### 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}^{|\mathcal{T}_{v}|}\log p_{a,v}^{t}\mathcal{R}_{v}^{t}(a_ {t})+\eta Ent(\mathcal{P}_{v}^{t})\right)\right) \tag{12}\]

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

\[Ent(\mathcal{P}_{v}^{t})=-\sum_{\forall a\in\mathcal{P}_{v}^{t}}p_{a,v}^{t} \log(p_{a,v}^{t}) \tag{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.

### 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](https://github.com/idea-iitd/InduCE.git). Details of the hardware and software platform are provided in App. F.

### Datasets

**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".

### Baselines

We benchmark InduCE against the state-of-the-art baselines of **(1)** CF-GnnExplainer[13], **(2)** CF\({}^{2}\)[21], and **(3)** Gem[12]. In addition, we also compare against the state-of-the-art factual explainer **(4)** PGEExplainer 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 CF\({}^{2}\) and CF-GnnExplainer are transductive, Gem and PGEExplainer 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 CF\({}^{2}\) 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

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & **Tree-Cycles** & **Tree-Grid** & **BA-Shapes** & **Amazon** & **ogbn-arxiv** \\ \hline \# 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 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The statistics of the benchmark datasets.
[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 Cr\({}^{2}\),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}_{v}^{\ell}\), 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.

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

\begin{table}
\begin{tabular}{l||c|c|c||c|c||c|c||c} \hline \multirow{2}{*}{**Method**} & \multicolumn{3}{c||}{**Tree-Cycles**} & \multicolumn{3}{c||}{**Tree-Grid**} & \multicolumn{3}{c}{**B-Shapes**} \\ \cline{2-10}  & **Fld\(\%\)\(\downarrow\)** & **Size \(\downarrow\)** & **Acc.(\%\(\uparrow\))** & **Fld\(\%\)\(\downarrow\)** & **Size \(\downarrow\)** & **Acc.(\%\(\uparrow\))** & **Fld\(\%\)\(\downarrow\)** & **Size \(\downarrow\)** & **Acc.(\%\(\uparrow\))** \\ \hline Random & **0** & 31.82 \(\pm\)3.22 & 67.08 & **0** & 8.32 \(\pm\)4.95 & 73.44 & **0** & 203.97 \(\pm\)27.26 & 15.57 \\ CF-GnnEx & 49.0 & 1.05 \(\pm\)0.23 & **100** & 10 & 1.37 \(\pm\)0.58 & 92.24 & 37.0 & 1.31 \(\pm\)0.55 & **95.83** \\ CF\({}^{2}\) & 76.38 & 4.18 \(\pm\)8.99 & 67.68 & 98.45 & 5.5 \(\pm\)1.45 & 44.61 & 23.68 & 4.10 \(\pm\)6.64 & 70.54 \\ INuCE (transductive) & **0** & **1.01 \(\pm\)0.12** & 96.61 & **0** & **1.02 \(\pm\)0.12** & **97.67** & **0** & **1.30 \(\pm\)0.90** & 95.31 \\ \hline \hline \multicolumn{10}{l}{**CF-GnnEx\(\%\)\(+\)\(+\)\(+\)\(+\)\(+\)**} & 100 & NULL & NULL & 100 & NULL & NULL & NULL & \multicolumn{1}{c}{} \\ CF\({}^{2}\)\(+\)\(+\)\(+\) & 13.89 & 28.34 \(\pm\)7.56 & 19.24 & 28.68 & 12.90 \(\pm\)7.71 & 27.44 & 100 & NULL & NULL \\ INuCE (transductive)\(-\)\(+\) & **0** & 1.40 \(\pm\)1.49 & 81.94 & **0** & 1.24 \(\pm\)0.43 & 92.64 & 6.6 & 1.42 \(\pm\)1.49 & 83.22 \\ \hline \hline \end{tabular}
\end{table}
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.

\begin{table}
\begin{tabular}{l||c|c|c||c|c||c|c||c} \hline \multirow{2}{*}{**Method**} & \multicolumn{3}{c||}{**Tree-Cycles**} & \multicolumn{3}{c||}{**Tree-Grid**} & \multicolumn{3}{c}{**B-Shapes**} \\ \cline{2-10}  & **Fld\(\%\)\(\downarrow\)** & **Size \(\downarrow\)** & **Acc.(\%\(\uparrow\))** & **Fld\(\%\)\(\downarrow\)** & **Size \(\downarrow\)** & **Acc.(\%\(\uparrow\))** & **Fld.(\%\(\downarrow\))** & **Size \(\downarrow\)** & **Acc.(\%\(\uparrow\))** \\ \hline
**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 \(\pm\)1.44** & **96.65** & **0** & **4.67 \(\pm\)**2.91 & 91.05 & **2.6** & **4.37 \(\pm\)**3.53 & 64.40 \\ \hline
**InduCE** (inductive)\(+\) & 36.3 & **1.67 \(\pm\) 0.90** & 90.32 & 16.3 & 6.38 \(\pm\)3.74 & 86.31 & 40.8 & **3.37 \(\pm\)3.04** & 56.08 \\ \hline \hline \end{tabular}
\end{table}
Table 3: **Results for inductive methods.** The best result in each category is highlighted in bold.
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 (a)a).

**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 CF\({}^{2}\) with edge additions, denoted as CF-GnnExplainer \(++\) and CF\({}^{2}++\) respectively. 1 Both CF\({}^{2}\) 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 CF\({}^{2}\), 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.

Footnote 1: Gem 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.

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.

### Quantitative Results on Real Datasets

In Tables (a)a and (b)b, 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

Figure 3: The distributions of the edit size and their internal composition of edge additions and deletions by InduCE on the Tree-Cycles dataset.
exception. In contrast, InduCE produces promising performance with the transductive version achieving \(0\%\) fidelity.

### Efficiency

Table 5(a) 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 CF\({}^{2}\). 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 5(b) 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.

### 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. 3(a). 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 CF\({}^{2}\) 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. 0(a)-0(b) in Appendix.

**Impact of additions:** In Fig. 3(b) 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.

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

\begin{table}

\end{table}
Table 4: Results for (a) transductive and (b) inductive methods on the Amazon dataset. “NULL” denotes that the method could not produce a counterfactual.

\begin{table}

\end{table}
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.”
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.
