#  Generating Robust Counterfactual Witnesses for Graph Neural Networks

Dazhuo Qiu  Aalborg University
Denmark
<EMAIL_ADDRESS>Mengying Wang  Case Western Reserve University
USA
<EMAIL_ADDRESS>Arijit Khan  Aalborg University
Denmark
<EMAIL_ADDRESS>Yinghui Wu  Case Western Reserve University
USA
<EMAIL_ADDRESS>
###### Abstract

This paper introduces a new class of explanation structures, called robust
counterfactual witnesses ($\mathsf{RCWs}$), to provide robust, both
counterfactual and factual explanations for graph neural networks. Given a
graph neural network ${\mathcal{M}}$, a robust counterfactual witness refers
to the fraction of a graph $G$ that are counterfactual and factual explanation
of the results of ${\mathcal{M}}$ over $G$, but also remains so for any
“disturbed” $G$ by flipping up to $k$ of its node pairs. We establish the
hardness results, from tractable results to co-$\mathsf{NP}$-hardness, for
verifying and generating robust counterfactual witnesses. We study such
structures for $\mathsf{GNN}$-based node classification, and present efficient
algorithms to verify and generate $\mathsf{RCWs}$. We also provide a parallel
algorithm to verify and generate $\mathsf{RCWs}$ for large graphs with
scalability guarantees. We experimentally verify our explanation generation
process for benchmark datasets, and showcase their applications.

##  I Introduction

Graph neural networks ($\mathsf{GNNs}$) have exhibited promising performances
in graph analytical tasks such as classification. Given a graph $G$ and a set
of test nodes $V_{T}$, a $\mathsf{GNN}$-based node classifier aims to assign a
correct label to each node $v\in V_{T}$. $\mathsf{GNN}$-based classification
has been applied for applications such as social networks and biochemistry [1,
2, 3].

For many $\mathsf{GNNs}$-based tasks such as node classification, data
analysts or domain scientists often want to understand the results of
$\mathsf{GNNs}$ by inspecting intuitive, explanatory structures, in the form
where domain knowledge can be directly applied [4]. In particular, such
explanation should indicate “invariant” representative structures for similar
graphs that fall into the same group, _i.e.,_ be “robust” to small changes of
the graphs, and be both “factual” (that preserves the result of
classification) and “counterfactual” (which flips the result if removed from
$G$) [5]. The need for such robust, and both factual and counterfactual
explanation is evident for real-world applications such as drug design or
cyber security.

Consider the following real-world examples.

Example 1: [Interpreting “Mutagenics” with Molecular Structures]. In drug
discovery, $\mathsf{GNNs}$ have been applied to detect mutagenicity
structures, which has an adverse ability that causes mutations [6, 7].
Consider $G_{1}$ depicted in Fig. 1, which is a graph representation of a
real-world molecular database [8, 9]. The nodes of $G_{1}$ refer to the atoms
of the molecules, and the edges of $G_{1}$ represent the valence bonds between
a pair of atoms. Given a set of “test nodes” $V_{T}$ in $G$, a
$\mathsf{GNN}$-based classifier $M$ is trained for the task to correctly
assign, for each of the nodes in $V_{T}$, a label: “$\mathsf{mutagenic}$”, if
it belongs to a chemical compound that is a mutagenicity structure; and
“$\mathsf{nonmutagenic}$”, otherwise.

A natural interpretation to a chemist would be to identify a subgraph $G_{1}$
that contains most of the “mutagenic” nodes as a toxicophore structure, that
is, a critical fraction of chemical compounds responsible for mutagenicity
[10]. Consider the example in Figure 1. On the left is a mutagenic molecule
due to the bold nitro group. Meanwhile, the remaining structure after removing
the nitro group is considered as non-mutagenic. However, considering a similar
molecule that only misses two bonds (dotted edges), which is in the middle,
the red bold structure is an aldehyde with a high risk of triggering
mutagenicity. To ensure that the discovered mutagenic-related chemical
compounds are meaningful to a family of molecules, it is required to find a
robust explanation structure, such as the bold indicated structure on the
right molecule.

Figure 1: $G_{1}$: Left-Bold nodes and edges indicate a counterfactual.
Middle-Red bold nodes and edges indicate a new counterfactual after deleting
dotted edges. Right-A counterfactual robust to graph edits. $G_{2}$: The
shaded area is a robust counterfactual, also “vulnerable zone” in cyber
networks.

Existing $\mathsf{GNN}$ explanation methods may return different structures as
the test nodes vary, or carry “noisy” structures such as carbon rings or
hydrogen atoms that are not necessarily corresponding to toxicophores (as
verified in our case study; see Section VII). This may make it difficult for a
chemist to discern the potential toxic structure hidden inside normal
structures. (e.g., red bold aldehyde in the middle molecule of Figure 1.)
Moreover, instead of analyzing explanations for each molecule, identifying a
common “invariant” explanation that remains the same over a family of similar
molecules with few bond differences could improve the efficiency of
identifying mutagenic-related chemical compounds. A more effective approach is
expected to directly compute explanation structures which are, or contain such
toxicophores as robust structures, closer to what a chemist is familiar with.
$\Box$

Our second example illustrates the need for such structures in cyber security,
where new edges are inserted as part of real-world cyber attacks. In such
context, the explanation structures themselves may indicate “invariant”
structures that need to be protected regardless of attack tactics.

Example 2: [Understanding “Vulnerable Zone” in Cyber Networks]. Graph $G_{2}$
in Fig. 1 is a fraction of a provenance graph [11]. It consists of nodes that
represent files (oval) or processes (rectangle), while the edges depict access
actions. The graph contains a substructure that captures a multi-stage attack.
The attack is initiated by an email with a malicious attachment that is
disguised as an invoice, and targets at a script “breach.sh” to perform a data
breach. Attack tactics are encoded as paths or subgraphs (with red-colored,
solid or dashed edges) in $G_{2}$. A $\mathsf{GNN}$-based node classifier is
trained to identify potential attack targets (to be labeled as “vulnerable”,
colored orange in $G_{2}$) [12].

An emerging challenge is to effectively detect a two-stage tactic, which first
uses, _e.g.,_ “DDoS” as a deceptive attack (via red dashed edges) on various
fake targets to exhaust defense resources, to hide the intention of data
breaching from an invariant set of high-value files as true target (via red
solid edges). In such cases, a $\mathsf{GNN}$-classifier can be “fooled” to
identify a test node as “vulnerable” simply due to majority of its neighbors
wrongly labeled as “vulnerable” under deceptive stage. On the other hand, a
robust explanation for those correct labeling of test nodes should stay the
same for a set of training attack paths. In such cases, the tactic may switch
the first-stage targets from time to time to maximize the effect of deceptive
attacks. As the explanation structures remain invariant despite various
deceptive targets, they may reveal the true intention regardless of how the
first stage deceptive targets change. As such, the explanation also suggests a
set of true “vulnerable” files that should be protected, thereby helping
mitigate the impact of deceptive attacks.

Nevertheless, computing such an explanation can be expensive due to the large
size of provenance graphs. For example, a single web page loading may already
result in 22,000 system calls and yields a provenance graph with thousands of
nodes and edges [13, 11]. Especially for sophisticated multi-stage attacks
above, it may leave complex and rapidly changing patterns in the provenance
graph. Detecting and mitigating such attacks require the ability to process
large amounts of data quickly for real-time or near-real-time threat analysis.
$\Box$

The above examples illustrate the need to generate subgraphs as explanation
structures for $\mathsf{GNN}$-based classification, which are (1) “factual”,
_i.e.,_ contributing subgraphs that are consistently responsible for the same
assigned class labels to test nodes, (2) “counterfactual”, _i.e.,_
$\mathsf{GNN}$ result changes if such explanation structures are removed, and
moreover, (3) “robust”, _i.e.,_ remain to be a factual and counterfactual
explanation upon certain amount of structural disturbance in the graphs.
Several methods generate explanation structures (factual or counterfactual)
for $\mathsf{GNN}$-based classification [14, 15, 16, 17, 18], yet can not
guarantee all the three (factual, counterfactual, and robust) criteria upon
edge updates.

Given a pre-trained $\mathsf{GNN}$ model ${\mathcal{M}}$ and a graph $G$, how
do we formally characterize such “invariant” structures? Moreover, how can we
efficiently compute such “invariant” structures for $\mathsf{GNN}$-based node
classification over large graphs?

Contributions. To address the above challenges, we propose a novel class of
$\mathsf{GNN}$ explanation structures called robust counterfactual witness,
and develop cost-effective methods to compute them. We summarize our main
contributions below.

(1) We formalize the notion of robust counterfactual witness ($\mathsf{RCW}$)
for $\mathsf{GNN}$-based node classification. An $\mathsf{RCW}$ is a subgraph
in $G$ that preserves the result of a $\mathsf{GNN}$-based classifier if
tested with $\mathsf{RCW}$ alone, remains counterfactual (i.e., the
$\mathsf{GNN}$ gives different output for the remaining fraction of the graph
if $\mathsf{RCW}$ is excluded), and robust (such that it can preserve the
result even if up to $k$ edges in $G$ are changed).

(2) We analyze properties of $k$-$\mathsf{RCWs}$ in regards to the
quantification of $k$-disturbances, where $k$ refers to a budget of the total
number of node pairs that are allowed to be disturbed. We formulate the
problems for verifying (to decide if a subgraph is a $k$-$\mathsf{RCW}$) and
generating $\mathsf{RCWs}$ (for a given graph, $\mathsf{GNN}$, and
$k$-disturbance) as explanations for $\mathsf{GNN}$-based node classification.
We establish their computational hardness results, from tractable cases to co-
NP hardness.

(3) We present feasible algorithms to verify and compute $\mathsf{RCWs}$,
matching their hardness results. Our verification algorithm adopts an “expand-
verify” strategy to iteratively expand a $k$-$\mathsf{RCW}$ structure with
node pairs that are most likely to change the label of a next test node, such
that the explanation remains stable by including such node pairs to prevent
the impact of the disturbances.

(4) For large graphs, we introduce a parallel algorithm to generate
$k$-$\mathsf{RCWs}$ at scale. The algorithm distributes the expansion and
verification process to partitioned graphs, and by synchronizing verified
$k$-disturbances, dynamically refines the search area of the rest of the
subgraphs for early termination.

(5) Using real-world datasets, we experimentally verify our algorithms. We
show that it is feasible to generate $\mathsf{RCWs}$ for large graphs. Our
algorithms can produce familiar structures for domain experts, as well as for
large-scale classification tasks. We show that they are robust for noisy
graphs. We also demonstrate application scenarios of our explanations.

Related Work. We summarize the related work as follows.

Graph Neural Networks. Graph neural networks ($\mathsf{GNNs}$) are deep
learning models designed to tackle graph-related tasks in an end-to-end manner
[19]. Notable variants of $\mathsf{GNNs}$ include graph convolution networks
(GCNs) [20], attention networks (GATs) [21], graph isomorphism networks (GINs)
[22], APPNP [23], and GraphSAGE [24]). Message-passing based $\mathsf{GNNs}$
share a similar feature learning paradigm: for each node, update node features
by aggregating neighbor counterparts. The features can then be converted into
labels or probabilistic scores for specific tasks. $\mathsf{GNNs}$ have
demonstrated their efficacy on various tasks, including node and graph
classification [20, 22, 25, 26, 27], and link prediction [28].

Explanation for GNNs. Several approaches have been proposed to generate
explanations for $\mathsf{GNNs}$ [29, 30, 31, 32, 33, 14, 34, 15, 18, 16, 17].
For example, GNNExplainer [14] learns to optimize soft masks for edges and
node features to maximize the mutual information between the original and new
predictions and induce important substructures from the learned masks.
SubgraphX [15] employs Shapley values to measure a subgraph’s importance and
considers the interactions among different graph structures. XGNN [18]
explores high-level explanations by generating graph patterns to maximize a
specific prediction. GCFExplainer [16] studies the global explainability of
GNNs through counterfactual reasoning. Specifically, it finds a small set of
counterfactual graphs that explain $\mathsf{GNNs}$. CF2 [35] considers a
learning-based approach to infer substructures that are both factual and
counterfactual, yet does not consider robustness guarantee upon graph
disturbance. $\mathsf{CF}$-$\mathsf{GNNExp}$ [34] generates counterfactual
explanations for GNNs via minimal edge deletions. Closer to our work is the
generation of robust counterfactual explanations for $\mathsf{GNNs}$ [36]. The
explanation structure is required to be counterfactual and stable (robust),
yet may not be a factual explanation. These methods do not explicitly support
all three of our objectives together: robustness, counterfactual, and factual
explanations; neither scalable explanation generation for large graphs are
discussed.

Robustness of GNNs. Robustness of $\mathsf{GNN}$ models has been separately
studied, such as certifiable robustness [37]. It verifies if a model remains
robust under bounded disturbance of edges. In particular, robust training of
$\mathsf{GNNs}$ that ensures such robustness has been investigated [38]. A
general strategy is to identify adversarial edges that, if removed, changes
the results of test nodes. If no such structure can be identified, the nodes
are certified to be robust. The key difference in our problem is that we
consider robust substructures of the data that preserve the results of a given
fixed model as well as its explanation structure. Therefore, prior robust
learning cannot be used to identify our explanation structures due to
different objectives.

##  II Preliminaries

We start with a review of $\mathsf{GNNs}$. We then introduce our robust
subgraph explanation structures. Important notations are summarized in Table
I.

TABLE I: Symbols & Notations Symbol |  Meaning
---|---
$G$ = $(V,E)$ |  graph with nodes $V$ and edges $E$
$(X,A)$ |  $X$: node feature matrix; $A$: adjacency matrix
${\mathcal{M}}$; $M$ |  a GNN-based classifier; inference function of ${\mathcal{M}}$
$X^{i}$; Z |  node embeddings at layer $i$ of ${\mathcal{M}}$;
logits (output) of inference process
$L$; $F$ |  # layers of ${\mathcal{M}}$; # features per node
$G_{w}$; $G_{s}$ |  a verified witness; a subgraph to be verified
$C$=$(G,G_{s},V_{T},M,k)$ |  a configuration that specifies graph $G$;
a subgraph $G_{s}$ to be verified as witness;
inference function $M$ (of a $\mathsf{GNN}$ ${\mathcal{M}}$);
test nodes $V_{T}$, and $k$ (in $k$-disturbance)
$\mathsf{CW}$; $\mathsf{RCW}$; $k$-$\mathsf{RCW}$ |  counterfactual witness;
robust counterfactual witness;
$k$-robust counterfactual witness
$m^{*}_{l,c}(v)$ |  worst-case margin of test node $v$

###  II-A Graphs and Graph Neural Networks

Attributed Graphs. We consider a connected graph $G=(V,E)$, where $V$ is the
set of nodes, and $E\subseteq V\times V$ is the set of edges. Each node $v$
carries a tuple ${\sf F}(v)$ of attributes (or features) and their values.

Graph Neural Networks (GNNs). $\mathsf{GNNs}$ [19] are a family of well-
established deep learning models that extend traditional neural networks to
transform graphs into proper embedding representations for various downstream
analyses such as node classification. $\mathsf{GNNs}$ employ a multi-layer
message-passing scheme, through which the feature representation of a node $v$
in the next layer is aggregated from its counterparts of the neighborhoods of
$v$ in $G$ at the current layer. A $\mathsf{GNN}$ with $L$ layers iteratively
gathers and aggregates information from neighbors of a node $v$ to compute
node embedding of $v$. For example, the Graph Convolution Network
($\mathsf{GCN}$) [20], a representative $\mathsf{GNN}$ model, adopts a general
form as:

$X^{i}=\delta(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}X^{i-1}\Theta^{i})$
(1)

Here $\hat{A}=A+I$, where $I$ is the identity matrix, and $A$ is the adjacency
matrix of $G$. $X^{i}$ indicates node feature representation in the $i$-th
layer ($i\in[0,L]$). Here $X^{0}=X$, which refers to the matrix of input node
features. Each row $X_{v}$ of $X$ is a vector encoding of a node tuple ${\sf
F}(v)$.111 The encoding can be obtained by, e.g., word embedding or one-hot
encoding [39], among other featurization techniques. The matrix $\hat{D}$
represents the diagonal node degree matrix of $\hat{A}$. The function
$\delta(.)$ is a non-linear activation function, and $\Theta^{i}$ represents
the learnable weight matrix at the $i$-th layer.

$\mathsf{APPNPs}$, a class of Personalized PageRank based $\mathsf{GNNs}$
${\mathcal{M}}$ [37], specifies the $\delta$ function (Eq. 1) with a
Personalized PageRank propagation matrix:
$X^{L}=(1-\alpha)(I-\alpha\hat{D}^{-1}\hat{A})^{-1}\cdot X\Theta$. Here $D$ is
the diagonal matrix of node out-degrees with ${D}_{ii}=\sum_{j}{A}_{ij}$, and
$\alpha$ is teleport probability. Other notable $\mathsf{GNN}$ variants are
$\mathsf{GraphSage}$ [24] that samples fixed-size neighbors, and
$\mathsf{GAT}$ [21] that incorporates self-attention.

$\mathsf{GNN}$-based node classification. Given a graph $G$ = $(V,E)$ and a
set of labeled “training” nodes $V_{Train}$, the node classification task is
to learn a $\mathsf{GNN}$-based classifier ${\mathcal{M}}$ to infer the labels
of a set of unlabeled test nodes. A $\mathsf{GNN}$-based classifier
${\mathcal{M}}$ of $L$ layers (1) takes as input $G$=$(X,A)$ and learns to
generate representations $X^{L}$, converts them into labels that best fit the
labels of $V_{Train}$ in $G$, and (2) assigns, for each unlabeled test node
$v\in V_{T}$, a class label $l\in\text{\L}$.

Inference. The label assignment is determined by an “inference process” $M$ of
${\mathcal{M}}$. Given a set of test nodes $V_{T}$, the process outputs a
“logits” matrix ${Z\in\mathbb{R}^{|V_{T}|\times|L|}}$ in $M$’s output layer,
for each node $v\in V_{T}$ and each label $l\in L$, to be converted to
likelihood scores of $l$ given $v\in V_{T}$; the higher, the more likely $v$
is assigned with $l$. A softmax function is then used to convert the logits to
corresponding labels. To make a (simplified) difference, (1) we consider the
inference process as a polynomial-time computable function $M(v,G)$ = $l$
($v\in V_{T}$), with a “result” $l$ for $v$; and (2) we refer to the output
logits $Z$ of $M$ simply as “output” of $M$.

In particular, we consider three trivial cases: $M(v,v)$ = $l$, and denote
$M(v,\emptyset)$ or $M(\emptyset,G)$ as “undefined”.

Fixed and deterministic GNN. Given a set of test nodes $V_{T}$, a
$\mathsf{GNN}$ ${\mathcal{M}}$ is fixed if its inference process $M(v,G)$ does
not change for any input test node $v$ in $V_{T}$. That is, it has all factors
which determine the computation of $M(\cdot)$ such as layers, model
parameters, among others, fixed. We say that ${\mathcal{M}}$ is deterministic
if $M(\cdot)$ always generates the same output for the same input. In this
work, we consider a fixed, deterministic $\mathsf{GNN}$ ${\mathcal{M}}$. In
practice, most of the $\mathsf{GNNs}$ are deterministic for the need of
consistency and accuracy guarantees.

###  II-B Explanation Structures

To characterize our explanation structures as subgraphs, we introduce a
notation of witnesses.

Witnesses. Given a graph $G$, class labels Ł, and a $\mathsf{GNN}$
${\mathcal{M}}$, a test node $v\in V_{T}$ for which $M(v,G)$=$l\in\text{\L}$,
we say that a subgraph $G_{w}$ of $G$ is

(1) a factual witness of result $M(v,G)$=$l$, if $M(v,G_{w})=l$222Note that
this indicates $G_{w}$ containing $v$ as one of its nodes.;

(2) a counterfactual witness ($\mathsf{CW}$) of $M(v,G)$=$l$, if (a) it is a
factual witness of $M(v,G)$=$l$, and (b) $M(v,G\setminus G_{w})$ $\neq l$; and

(3) a $k$-robust counterfactual witness $k$-$\mathsf{RCW}$ of $M(v,G)$=$l$, if
for any graph $\widetilde{G}$ obtained by a $k$-disturbance on $G\setminus
G_{w}$, $G_{w}$ remains to be a $\mathsf{CW}$ for $M(v,\widetilde{G})$=$l$.

Here (1) $G\setminus G_{w}$ is the graph obtained by removing all the edges of
$G_{w}$ from $G$, while keeping all the nodes; and (2) a $k$-disturbance to a
graph $G$ refers to an operation that “flips” at most $k$ node pairs (denoted
as $E_{k}$) from $G$, including edge insertions and removals. For a
$k$-disturbance posed on $G\setminus G_{w}$, it only “flips” a set of node
pairs $E_{k}$ that are not in $G_{w}$, _i.e.,_ it does not insert nor remove
edges of $G_{w}$. A $k$-disturbance may capture a natural structural
difference of graphs (_e.g.,_ chemical compounds that differ with at most $k$
bonds).

Given a set of test nodes $V_{T}\subseteq V$, we say that $G_{w}$ is a
$k$-$\mathsf{RCW}$ of $V_{T}$ _w.r.t._ $\mathsf{GNN}$ ${\mathcal{M}}$, if for
every test node $v\in V_{T}$, $G_{w}$ is a $k$-$\mathsf{RCW}$ for the result
$M(v,G)$=$l$. Note that a $k$-$\mathsf{RCW}$ $G_{w}$ of the test nodes $V_{T}$
naturally contains $V_{T}$ as its nodes.

We define several trivial cases. (1) A single node $v\in V_{T}$ is a trivial
factual witness of $M(v,G)$=$l$, as $M(v,v)$=$l$ trivially; it is a trivial
$\mathsf{CW}$ because $M(\emptyset,G)$ is undefined. (2) The graph $G$ is a
trivial factual witness as $M(v,G)$ trivially equals to itself; a trivial
$\mathsf{CW}$ for $M(v,G)$=$l$, as it is a trivial factual witness, and
$M(v,\emptyset)$ is undefined; and also a trivial $k$-$\mathsf{RCW}$, since no
$k$-disturbance can be applied to $G\setminus G$ = $\emptyset$. In practice,
we aim at finding “non-trivial” $k$-$\mathsf{RCWs}$ as subgraphs with at least
an edge, and are not $G$ themselves.

Example 3: The graph $G_{2}$ (Fig. 1) has a test node ‘breach.sh’, which is
the target file for a data breach and is labeled “vulnerable”. A valid attack
path must access a privileged file (‘/.ssh/id$\\_$rsa’ or ‘/etc/sudoers’) and
the command prompt (‘cmd. exe’) beforehand. Prior to executing the true attack
path (via red solid edges), the malware performs a non-aggressive deceptive
‘DDoS’ attack (via red dashed edges) to mislead the prediction of $M$, where
the GNN ${\mathcal{M}}$ is trained to identify whether a file is “vulnerable”
(in orange) or not (in green).

(1) There are two primary witnesses to explain the test node’s label:
(‘cmd.exe’, ‘/.ssh/id$\\_$rsa’, ‘breach.sh’) and (‘cmd.exe’, ‘/etc/sudoers’,
‘breach.sh’), each includes a factual path that leads to the breach and serves
as evidence to explain the test node’s label as “vulnerable”.

(2) Furthermore, a $\mathsf{CW}$ is shown as the combined subgraph of these
two witnesses, denoted as $G_{w_{2}}$ (shaded area of $G_{2}$ in Fig. 1).
Removing all edges in $G_{w_{2}}$ from $G$ will reverse the classification of
the test node to “not vulnerable”, as the remaining part is insufficient for a
breach path.

(3) $G_{w_{2}}$ is also a $k$-$\mathsf{RCW}$ for the test node’s label, where
$k$=$3$, which is the maximum length of a deceptive attack path. It indicates
that for any attack path involving up to $k$ deceptive steps, $G_{w_{2}}$
remains unchanged. It, therefore, identifies the true important files which
must be protected to mitigate the impact of deceptive attacks. $\Box$

We further justify that $\mathsf{RCWs}$ serve as a desirable explanation
structure by showing an invariant property.

Lemma 1: Given graph $G$, a set of test nodes $V_{T}$, and a fixed
deterministic $\mathsf{GNN}$ ${\mathcal{M}}$ with inference function $M$, a
$k$-$\mathsf{RCW}$ for $V_{T}$ is a $k^{\prime}$-$\mathsf{RCW}$ for
$V_{T}^{\prime}$, for any $k^{\prime}\in[0,k]$, $V_{T}^{\prime}\subseteq
V_{T}$. $\Box$

Proof: We first prove that for any node $v\in V_{T}$, a $k$-$\mathsf{RCW}$
$G_{w}$ for $M(v,G)$ remains to be a $k^{\prime}$-$\mathsf{RCW}$ for $M(v,G)$,
for any $k^{\prime}\in[0,k]$. One can verify the above result by
contradiction. Assume that there is a $k^{\prime}\in[0,k]$, such that a
$k$-$\mathsf{RCW}$ $G_{w}$ is not a $k^{\prime}$-$\mathsf{RCW}$, then (a)
$G_{w}$ is not a factual witness, or it is not counterfactual, both contradict
to that $G_{w}$ is an $\mathsf{RCW}$; or (b) $G_{w}$ is a $\mathsf{CW}$ but is
not robust. Then there exists a $k^{\prime}$-disturbance with $k^{\prime}$
edges $E_{k}^{\prime}$ in $G\setminus G_{w}$, which “disproves” that $G_{w}$
is a $k$-$\mathsf{RCW}$. As $k^{\prime}\leq k$, the same
$k^{\prime}$-disturbance prevents $G_{w}$ to be a $k$-$\mathsf{RCW}$ by
definition. This contradicts to that $G_{w}$ is a $k$-$\mathsf{RCW}$. Hence,
$G_{w}$ remains to be a $k^{\prime}$-$\mathsf{RCW}$ for $M(v,G)$. As the test
node $v$ ranges over $V_{T}$, the above analysis holds to verify that $G_{w}$
remains to be a $k^{\prime}$-$\mathsf{RCW}$ for any subset
$V_{T}^{\prime}\subseteq V_{T}$. Lemma II-B thus follows.

We next study two classes of fundamental problems for $\mathsf{RCWs}$,
notably, verification and generation.

##  III Verification of Witnesses

For the ease of presentation, we introduce an input configuration for
verification problem.

Configuration. A configuration $C$ = $(G,G_{s},V_{T},M,k)$ specifies a graph
$G$ with a set of test nodes $V_{T}$, a fixed, deterministic $\mathsf{GNN}$
inference process $M$, an integer $k$ to specify $k$-$\mathsf{RCW}$, and a
subgraph $G_{s}$ of $G$. Specifically, a counterfactual witness $\mathsf{CW}$
is a $0$-$\mathsf{RCW}$ ($k$=0), _i.e.,_ no robustness requirement is posed.

###  III-A Verification Problem

Given a configuration $C$ = $(G,G_{s},V_{T},M,k)$, the verification problem is
to decide if $G_{s}$ is a $k$-$\mathsf{RCW}$ for $V_{T}$ _w.r.t._ $M$. We
first study the complexity of two special cases.

Verification of factual witnesses. The witness verification problem takes as
input a configuration $C$ = $(G,G_{s},V_{T},M,0)$ and decides if $G_{s}$ is a
factual witness for $V_{T}$, _i.e.,_ for every test node $v\in V_{T}$, $G_{s}$
is a factual witness.

We have the following result.

Lemma 2: The witness verification problem is in $\mathsf{PTIME}$. $\Box$

Similarly, the verification problem for $\mathsf{CW}$ is to decide if a given
subgraph $G_{s}$ of $G$ is a counterfactual witness for $V_{T}$. We show that
this does not make the verification harder.

Lemma 3: The verification problem for $\mathsf{CW}$ is in $\mathsf{PTIME}$.
$\Box$

We prove the above two results with two verification algorithms,
$\mathsf{verifyW}$ and $\mathsf{verifyCW}$, which invoke the inference process
$M$ of $\mathsf{GNN}$ ${\mathcal{M}}$ to check if the label $M(v,G_{s})$ and
$M(v,G\setminus G_{s})$ remain to be $l=M(v,G)$, respectively. One may justify
that $\mathsf{verifyW}$ and $\mathsf{verifyCW}$ are in $\mathsf{PTIME}$ by
observing that the inference function $M$ is $\mathsf{PTIME}$ computable, with
a cost typically determined by $L$, $|V|$, $|E|$, $d$, and $F$, where $L$ is
the number of layers of the $\mathsf{GNN}$ ${\mathcal{M}}$, $d$ =
$\frac{|E|}{|V|}$ is the average degree of $G$, and $F=|{\sf F}(v)|$ is the
number of features per node. For example, the inference cost of message-
passing based $\mathsf{GNNs}$ (_e.g.,_ $\mathsf{GCNs}$, $\mathsf{GATs}$,
$\mathsf{GraphSage}$), or PageRank based $\mathsf{APPNPs}$ is
$O(L|E|F+L|V|F^{2})$ [40, 23].

Despite the verification of witnesses and $\mathsf{CW}$ is tractable, its
$\mathsf{RCW}$ counterpart is nontrivial.

Theorem 1: The $k$-$\mathsf{RCW}$ verification problem is $\mathsf{NP}$-hard.
$\Box$

Proof sketch:  We make a case for $\mathsf{APPNPs}$. Given $G_{s}$, we first
invoke $\mathsf{verifyW}$ and $\mathsf{verifyCW}$ in $\mathsf{PTIME}$ to check
if it remains to be a $\mathsf{CW}$. If $G_{s}$ is not a factual witness or a
$\mathsf{CW}$, we assert that $G_{s}$ is not a $k$-$\mathsf{RCW}$. Otherwise,
the problem equals to verify if a $\mathsf{CW}$ $G_{s}$ is a
$k$-$\mathsf{RCW}$. We prove this by first showing that it is a general case
of the $k$-edge PageRank maximization problem: Find at most $k$ node pairs
from a graph s.t. the PageRank scores of a targeted node $v$ is maximized if
these $k$ links are inserted.

We then show the hardness of the $k$-edge PageRank maximization problem by
constructing a $\mathsf{PTIME}$ reduction from the link building problem
($\mathsf{LBP}$), a known $\mathsf{NP}$-hard problem [41]: Given a graph
$G=(V,E)$, a node $v\in V$, a budget $k\geq 1$, find the set $S\subseteq
V\backslash\\{v\\}$ with $|S|=k$ s.t. the PageRank score of $v$ in
$G^{\prime}(V,E\cup(S\times\\{v\\}))$ is maximized. As the $k$-edge PageRank
maximization problem is $\mathsf{NP}$-hard, the verification of
$k$-$\mathsf{RCW}$ is $\mathsf{NP}$-hard. $\Box$

Algorithm. We outline a general verification algorithm, denoted as
$\mathsf{verifyRCW}$. Given a configuration $C$, the algorithm first invokes
$\mathsf{verifyW}$ and $\mathsf{verifyCW}$ to check if $G_{s}$ is a factual
witness and a $\mathsf{CW}$, both in $\mathsf{PTIME}$ (Lemma III-A and Lemma
III-A). If $G_{s}$ remains to be a $\mathsf{CW}$, it next performs a $k$-round
of verification, to verify if $G_{s}$ is a $j$-$\mathsf{RCW}$ in the $j$-th
round by enumerating all $j$-disturbances. It early terminates whenever a
$j$-th disturbance is identified, which already disproves that $G_{s}$ is a
$j$-$\mathsf{RCW}$, given Lemma II-B.

###  III-B A Tractable Case

While it is in general intractable to verify $k$-$\mathsf{RCW}$, not all is
lost: We show that there exists a tractable case for the verification problem
when the $k$-disturbance is further constrained by a “local budget”, for the
class of $\mathsf{APPNPs}$. We introduce two specifications below.

$(k,b)$-disturbance. Given a graph $G$, a $k$-disturbance is a
$(k,b)$-disturbance to $G$ if it disturbs at most $k$ edges, and meanwhile at
most $b$ edges for each involved nodes in $G$. Here $b$ is a pre-defined
constant as a local “budget” for a permissible disturbance. In practice, a
local budget may indicate the accumulated total cost of “local attack” of a
server, or variants of bonds in-degree as seen in chemical compound graphs
[9], which are typically small constants (_e.g.,_ $\leq 5$).

Node robustness. We start with a characterization of node robustness that
extends certifiable robustness [37], which verifies if a predicted label can
be changed by a $k$-disturbance. This work makes a case for $\mathsf{APPNPs}$,
a class of Personalized PageRank based $\mathsf{GNNs}$ ${\mathcal{M}}$ as
aforementioned. Given a configuration $C$ = $(G,G_{s},V_{T},M,k)$, where $M$
is the inference process for a fixed deterministic $\mathsf{APPNP}$
${\mathcal{M}}$, a node $v\in V_{T}$ is robust _w.r.t._ configuration $C$, if
a “worst-case margin” $m_{l,*}^{*}(v)$ = $\min_{c\neq l}$ $m_{l,c}^{*}(v)>0$,
where $M(v,G)$ = $l$, and $c$ is any other label $(c\neq l)$. We define
$m_{l,c}^{*}(v)$ as:

$\begin{split}\vspace{-2.5ex}m_{l,c}^{*}(v)&=\min_{E_{k}\subseteq G\setminus
G_{s}}m_{l,c}(v)\\\ &=\min_{E_{k}\subseteq G\setminus
G_{s}}\pi_{E_{k}}\left(v\right)^{T}\left(Z_{\\{:,l\\}}-Z_{\\{:,c\\}}\right)\vspace{-1ex}\end{split}$
(2)

where $E_{k}$ ranges over all the possible $(k,b)$-disturbances that can be
applied to $G\setminus G_{s}$, and
${\pi_{E_{k}}\left(v\right)=\boldsymbol{\Pi}_{v,:}}$ is the PageRank vector of
node $v$ in the PageRank matrix
$\boldsymbol{\Pi}=(1-\alpha)({I}_{N}-\alpha{D}^{-1}{A^{\prime}})^{-1}$, with
$A^{\prime}$ obtained by disturbing the adjacency matrix of $G$ with $E_{k}$,
_e.g.,_ $A^{\prime}[i,j]$ = $0$ (resp. $1$) if $(v_{i},v_{j})\in E_{k}$ (resp.
$(v_{i},v_{j})\not\in E_{k}$). Note that we do not explicitly remove the edges
and change $G$, but reflect the tentative disturbing by computing
$A^{\prime}$. ${Z\in\mathbb{R}^{|V|\times|L|}}$ collects the individual per-
node logits for $\mathsf{APPNPs}$. By verifying $m_{l,*}^{*}(v)>0$ (_i.e.,_
$m_{l,c}^{*}(v)>0$ for any $c\in\text{\L}$ other than the label $l=M(v,G)$),
it indicates that under any disturbance of size $k$ in $G\setminus G_{s}$, $M$
always predicts the label of node $v$ as $l$.

We next outline a $\mathsf{PTIME}$ algorithm $\mathsf{verifyRCW}$ (Algorithm
1) for $\mathsf{APPNPs}$. The algorithm verifies if a given subgraph $G_{s}$
is a $k$-$\mathsf{RCW}$ for a single node $v\in V_{T}$ _w.r.t._
${\mathcal{M}}$ under $(k,b)$-disturbance. For a configuration $C$ with test
set $V_{T}$, it suffices to invoke $\mathsf{verifyRCW}$ for each $v\in V_{T}$.
We show that such $\mathsf{PTIME}$ solution exists with the following
condition given in Lemma III-B. Lemma III-B itself does not require the notion
of local budget; however, the $\mathsf{PTIME}$ computation of $E^{*}_{k}$
(defined in Lemma III-B) needs a local budget.

Lemma 4: Given the configuration $C$ that specifies $\mathsf{APPNP}$
${\mathcal{M}}$, let $G_{s}$ be a verified $\mathsf{CW}$ of $M(v,G)$ = $l$ for
a node $v\in V_{T}$, and only $k$-disturbance is allowed, then $G_{s}$ is a
$k$-$\mathsf{RCW}$ of $M(v,G)$=$l$, if and only if $M(v,G\setminus E^{*}_{k})$
= $l$, where $E^{*}_{k}$ = $\operatorname*{arg\,max}_{E_{k}\subseteq
G\setminus G_{s},c\neq
l}\pi_{E_{k}}\left(v\right)^{T}\left(Z_{\\{:,c\\}}-Z_{\\{:,l\\}}\right)$.
$\Box$

Proof sketch:  Let $\widetilde{G}$ be the graph obtained by disturbing
$E^{*}_{k}$ in $G\setminus G_{s}$. For the If condition, let $E^{*}_{k}$ be
the node pairs to be disturbed in the corresponding $k$-disturbance in
$G\setminus G_{s}$. As $E^{*}_{k}$ maximizes
$\pi_{E_{k}}\left(v\right)^{T}\left(Z_{\\{:,c\\}}-Z_{\\{:,l\\}}\right)$, which
indicates that it minimizes the gap between the likelihoods that some label
$c\neq l$ being assigned to $v$, quantified by the worst-case margin
$m^{*}_{l,c}$, for every label $c$ that is not $l$. Then, if $m^{*}_{l,c}>0$
for every $c\neq l$ under disturbance $E^{*}_{k}$, $M(v,\widetilde{G})$ will
remain to be $l$. This means that no $k$-disturbance in $G\setminus G_{s}$
will change $v$’s label. Meanwhile, since disturbing $E_{k}^{*}$ alone is not
sufficient enough to affect the outcome of $M$ on $v$, and as $G_{s}$ is a
verified $\mathsf{CW}$ for $M(v,G)=l$, so $M(v,G\setminus G_{s})\neq l$, then
$M(v,\widetilde{G}\setminus G_{s})\neq l$ holds for any $k$-disturbance.
Hence, $G_{s}$ is a $k$-$\mathsf{RCW}$ of $M(v,G)$=$l$ by definition.

The Only If condition can be shown by contradiction. Assuming there exists a
set $E^{*}_{k}$ that makes $M(v,\widetilde{G})\neq l$, and $G_{s}$ is still a
$k$-$\mathsf{RCW}$ of $M(v,G)$ = $l$; since ${\mathcal{M}}$ is fixed and
deterministic, $M(v,G_{s})$ = $l$ is not affected by disturbing $E_{k}$
“outside” of $G_{s}$; yet $M(v,\widetilde{G})\neq l$, hence $G_{s}$ is not a
factual witness for $M(v,\widetilde{G})$ = $l$, and hence not a $\mathsf{CW}$
for $M(v,\widetilde{G})$ = $l$, violating the third condition in the
definition of $k$-$\mathsf{RCW}$ for $G$. Hence $G_{s}$ is not a
$k$-$\mathsf{RCW}$ of $M(v,G)$ = $l$. This contradicts to that $G_{s}$ is a
$k$-$\mathsf{RCW}$ of $M(v,G)$=$l$. $\Box$

Algorithm 1 Algorithm $\mathsf{verifyRCW}$-$\mathsf{APPNP}$ (single node)

0: A configuration $C$ = $\\{G,G_{s},v,{\mathcal{M}},k\\}$, integer $b$;

0: $\mathsf{true}$ if $G_{s}$ is a $k$-$\mathsf{RCW}$, $\mathsf{false}$
otherwise.

1: if ${\mathsf{verifyW}}(C)=$$\mathsf{false}$ or
${\mathsf{verifyCW}}(C)=$$\mathsf{false}$ then

2: return $\mathsf{false}$;

3: construct graph $G^{\prime}$ = $G\setminus G_{s}$;

4: $\hat{A}^{\prime}$ = $A^{\prime}+I$, where $A^{\prime}$ is adjacency matrix
of $G^{\prime}$;

5: initialize edge set $E^{0}$ with arbitrary subset of $G^{\prime}$;

6: for each $c\in L\setminus\\{l\\}$ do

7: $\mathbf{r}$ = ${Z}_{\\{:,c\\}}-{Z}_{\\{:,l\\}}$;

8: $E^{*}$ = ${\mathsf{PRI}}(\mathbf{r},b,E^{0})$; /*get $(k,b)$-disturbance*/

9: if $M(v,G\setminus E^{*})\neq l$ or $|E^{*}|>k$ then

10: return $\mathsf{false}$;

11: return $\mathsf{true}$;

Procedure: ${\mathsf{PRI}}(\mathbf{r},b,E^{0})$

1: initialize integer $i$=$0$;

2: while $E^{i}\neq E^{i-1}$ or $i=0$ do

3: update $\hat{A}^{\prime}$ by “disturbing” $E^{i}$ in $G$; /*flip entries*/

4: update $X^{L}$ =
$(I_{N}-\alpha\hat{D}^{-1}\hat{A}^{\prime})^{-1}\cdot\mathbf{r}$;

5: $s(u,u^{\prime})$=$(1-2A^{\prime}_{uu^{\prime}})$
$(X_{u^{\prime}}-\frac{X_{u}-X_{u}^{\prime}}{\alpha})$,
$\forall(u,u^{\prime})\in G^{\prime}$;

6: $E_{b_{u}}$ := $\text{top}_{b}\\{(u,u^{\prime})\in G^{\prime}\mid
s(u,u^{\prime})>0\\}$, $\forall u\in G^{\prime}$;

7: $E_{b}^{i}$ = $\bigcup_{u\in G^{\prime}}E_{b_{u}}$;

8: $E^{i+1}$ = $(E^{i}\cup E^{i}_{b})-(E^{i}\cap E^{i}_{b})$, $i=i+1$;

9: if $M(v,G\setminus E^{i})\neq l$ then break;

10: return $E^{i}$

Based on the above result, it suffices to show that there is a
$\mathsf{PTIME}$ solution to the optimization problem that computes
$E^{*}_{k}$ (under $(k,b)$-disturbance), which maximizes
$\pi_{E_{k}}\left(v\right)^{T}\left(Z_{\\{:,c\\}}-Z_{\\{:,l\\}}\right)$.
Following [37], we present a greedy edge selection strategy to construct
$E^{*}_{k}$ in $\mathsf{PTIME}$.

Algorithm. Algorithm 1 first invokes $\mathsf{verifyW}$ and
$\mathsf{verifyCW}$ to check if $G_{s}$ is a factual witness and a
$\mathsf{CW}$ (lines 1-2). If $G_{s}$ remains to be a $\mathsf{CW}$, it then
follows an iterative “optimize-and-verify” process, which first computes a set
of edges $E_{k}$ that can optimize
$\pi_{E_{k}}\left(v\right)^{T}\left(Z_{\\{:,c\\}}-Z_{\\{:,l\\}}\right)$, and
then verifies if the $(k,b)$-disturbance changes the label.

Procedure $\mathsf{PRI}$. It nontrivially optimizes the policy iteration
procedure [37], which goes through multiple rounds of top-$b$ edges selection
to get $E^{*}$ that mostly hurts $G_{s}$ as a $\mathsf{CW}$ for $M(v,G)=l$. In
each round $i$, it calculates a score $s(u,u^{\prime})$ for each node pair
$(u,u^{\prime})\in G^{\prime}$, which measures the potential improvement on
the PageRank score of test node $v$ by flipping $(u,u^{\prime})$. Then, for
each node $u\in G^{\prime}$, it selects at most $b$ node pairs with the
highest positive $s(u,u^{\prime})$ and constructs $E_{b}^{i}$ (line 6-7).
$\mathsf{PRI}$ greedily improves $E^{i}$ by removing or inserting the edges in
$E_{b}^{i}$ to obtain $E^{i+1}$ and feeds it to the next iteration (line 8).
Whenever a set of node pairs $E^{i}$ is constructed, it checks if the label of
$v$ changes by “disturbing” $G$ with $E^{i}$ (line 9). If so, $G_{s}$ is not a
$k$-$\mathsf{RCW}$ as “disapproved” by $E^{i}$ and returns “false”. Otherwise,
$G_{s}$’s robustness will be asserted by testing all possible disturbances
until it reaches a point where no further improvement can be made on $E^{*}$,
at which point $\mathsf{PRI}$ terminates and returns the optimized $E^{*}$.

Remarks. One notable aspect of Procedure $\mathsf{PRI}$ is that it only
ensures local $b$-size disturbance on each node in $G^{\prime}$ and it
achieves global optimization without guaranteeing $k$-size disturbance.
Consequently, in line 9 of Algorithm 1, we only check the disturbance where
$|E^{i}|\leq k$ to confirm that $G_{s}$, which is asserted as a
$k$-$\mathsf{RCW}$, is indeed accurate. If Procedure $\mathsf{PRI}$ generates
an $E^{*}$ that exceeds $k$ in size, we reject it as false (line 9, Algorithm
1). This approach may accidentally reject some legitimate cases, but it is
sufficient to meet the requirements of the subsequent generation algorithm
(Section IV) that invokes it. The correctness is ensured by the greedy
selection process (following a “local budget”) that correctly solves the
Personalized PageRank maximization problem, which meanwhile minimizes the
worst-case margin (Lemma III-B) following the analysis in [37], where a
$\mathsf{PTIME}$ solution is provided. For time cost, $\mathsf{verifyRCW}$
iterates at most $|G\setminus G_{s}|$ configurations in Procedure
$\mathsf{PRI}$ [42], and both $\mathsf{verifyW}$ and $\mathsf{verifyCW}$
remain to be in $\mathsf{PTIME}$ (Lemma III-A and Lemma III-A). Setting
$G^{\prime}=G\setminus G_{s}$ and $d_{m}$ as the maximum node degree, the
total cost is $O(L|G^{\prime}|(d_{m}\log d_{m}+LF(|E|+|V|F)))$ for
representative $\mathsf{GNNs}$.

##  IV RCW Generation Problem

The generation problem, unlike verification, is to compute a nontrivial
$k$-$\mathsf{RCW}$ if exists, for a given configuration $C$ =
$(G,\emptyset,V_{T},M,k)$, or simply $(G,V_{T},M,k)$ as the $k$-$\mathsf{RCW}$
is to be computed. We can verify the following result.

Theorem 2: Given a configuration $C$ = $(G,V_{T},M,k)$, the $k$-$\mathsf{RCW}$
generation problem is in general co-$\mathsf{NP}$-hard. $\Box$

Proof sketch:  It suffices to consider a “single node”. A problem is
co-$\mathsf{NP}$-hard if its complementary problem is $\mathsf{NP}$-complete.
The decision problem of $k$-$\mathsf{RCW}$ generation for a configuration $C$
= $(G,v,M,k)$ is to decide if there exists a subgraph $G_{s}$ such that for
any $k$-disturbance, $G_{s}$ remains to be a $\mathsf{CW}$ for
$M(v,\widetilde{G})$=$l$, where $\widetilde{G}$ is obtained by disturbing $G$
with the $k$-disturbance. Its complementary problem is to verify if no
subgraph $G_{s}$ in $G$ can be a $k$-$\mathsf{RCW}$, _i.e.,_ for any subgraph
$G_{s}$, there always exists some $k$-disturbance that “disapproves” $G_{s}$
to be a $k$-$\mathsf{RCW}$. We make a case for $\mathsf{APPNPs}$ for the
complementary problem. (1) There is an $\mathsf{NP}$ algorithm that non-
deterministically guesses a subgraph $G_{s}$ and a $k$-disturbance, and solves
a verification problem given $G_{s}$ and $k$-disturbance in $\mathsf{PTIME}$
with inference test. (2) The $\mathsf{NP}$-hardness follows from Theorem
III-A, which shows that the verification problem of $k$-$\mathsf{RCW}$ for
$\mathsf{APPNPs}$ is already $\mathsf{NP}$-hard. Putting these together,
Theorem IV follows. $\Box$

One may consider a more feasible case when the verification problem is
tractable. Following Lemma III-B, we identify a tractable case for
$\mathsf{APPNPs}$ under $(k,b)$-disturbances.

Lemma 5: Given a configuration $C$ = $(G,V_{T},M,k,b)$ and only
$(k,b)$-disturbances are allowed, the $k$-$\mathsf{RCW}$ generation problem
for $\mathsf{APPNPs}$ is in $\mathsf{PTIME}$. $\Box$

We next present a feasible algorithm to generate $k$-$\mathsf{RCW}$ for
$\mathsf{GNN}$ ${\mathcal{M}}$. The algorithm ensures to output a
$k$-$\mathsf{RCW}$ in general cases; and in particular, ensures a
$\mathsf{PTIME}$ process for $\mathsf{APPNPs}$ under $(k,b)$-disturbance.

Algorithm 2 Algorithm $\mathsf{RoboGExp}$

0: A configuration $C$ = $\\{G,V_{T},M,k\\}$, integer $b$ (local budget);

0: A $k$-$\mathsf{RCW}$ $G_{s}$ of $V_{T}$ _w.r.t._ ${\mathcal{M}}$.

1: initialize $G_{s}$=${\mathcal{V}}_{T}$; set $E_{k}$=$\emptyset$; queue $Q$
= $V_{T}$;

2: while $G\setminus G_{s}\neq\emptyset$ do

3: update $C$=$(G,Q,M,k)$;

4: if ${\mathsf{verifyRCW}}(C,G_{s})$=$\mathsf{false}$ then

5: return $G$;

6: while $Q\neq\emptyset$ do

7: $Q$=$\\{v|v~{}\text{is not in $G_{s}$},v\in V_{T}\\}$;

8: node $v$=$Q.{\mathsf{dequeue}}()$;

9: $G_{s}$=$\mathsf{Expand}$ $(v,G_{s},C)$;

10: if ${\mathsf{verifyRCW}}(C,G_{s})$=$\mathsf{false}$ then

11: return $G$;

12: return $G_{s}$;

13: return $G_{s}$;

Procedure: ${\mathsf{Expand}}(v,G_{s},C)$

1: set $N_{k}$= $\\{u|u\in G\setminus G_{s}\\}$;

2: queue $v.Q_{k}$=$\emptyset$; set $E_{k}$=$\emptyset$;

3: while there is an unvisited pair $(u,u^{\prime})$ in $G\setminus G_{s}$ do

4: $v.Q_{k}$=${(u,u^{\prime})}$;

5: update worst-case margin $m^{*}_{l,c}(v)$;

6: update $E_{k}$ as all pairs $(u,u^{\prime})$ that maximize the worst-case
margin;

7: augment $G_{s}$ with $E_{k}$;

8: return $G_{s}$;

##  V Generating Robust Witnesses

We present our main result below.

Theorem 3: Given a configuration $C$ that specifics $G$, ${\mathcal{M}}$,
$V_{T}$, and $k$, there is an algorithm that generates a $k$-$\mathsf{RCW}$ in
$O((N+|G|)(L|E|F+L|V|F^{2}))$ time, where $N$ is the total number of verified
$k$-disturbances. Specifically for $\mathsf{APPNPs}$, given
$G^{\prime}=G\setminus G_{s}$ and $d_{m}$ as maximum degree, it is in
$O(L|G^{\prime}||V_{T}|\cdot(d_{m}\log d_{m}+LF(|E|+|V|F)+k))$ time. $\Box$

We present an algorithm as a constructive proof. Following Lemma III-B, it
suffices to ensure that the algorithm verifies the sufficient and necessary
condition. To this end, it processes a set of test nodes $V_{T}$ “one node at
a time”, and iteratively grows $G_{s}$ with an “expand-verify” strategy for
each node: (1) It approximates the optimal set of node pairs $E^{*}_{k}$ that
can minimize the worst-case margin $m^{*}_{l,c}$ of $v$ (Eq. 2), _i.e.,_ most
likely to change its label if “flipped” 333For $\mathsf{APPNPs}$, maximizing
Personalized PageRank score as in Lemma III-B. (see Procedure
$\mathsf{Expand}$); and (2) augment $G_{s}$ to contain $E^{*}_{k}$, such that
it “secures” $G$ by preventing disturbances from $E^{*}_{k}$. As such,
$M(v,G\setminus G_{s})$ is most likely444Here the optimality of $E^{*}_{k}$ is
not guaranteed by the procedure, and needs to be verified, for general cases.
to be $l$, and $G_{s}$ will remain to be a $k$-$\mathsf{RCW}$ for
$M(v,G\setminus G_{s})$ determined by the next round of verification.

Algorithm. The algorithm, denoted as $\mathsf{RoboGExp}$ and illustrated in
Algorithm 2, outputs a non-trivial $k$-$\mathsf{RCW}$ $G_{s}$ if exists; and
terminates with the trivial $k$-$\mathsf{RCW}$ $G$ by default. It uses (i) a
queue $Q$ to coordinate the processing of the test nodes $V_{T}$, (ii) for
each test node $v\in V_{T}$, a queue of node pairs $v.Q_{k}$, to track the
$k$-disturbance that most likely to change its own label. (1) It initializes
$G_{s}$ as a trivial $\mathsf{CW}$ set $V_{T}$ (line 1), and grows $G_{s}$ up
to the trivial $k$-$\mathsf{RCW}$ $G$ to guarantee the termination (lines
2-12). (2) The expansion of $G_{s}$ is controlled by a node-by-node process
(lines 7-12). Given a verified $k$-$\mathsf{RCW}$ $G_{s}$ for a fraction of
$V_{T}$ (lines 3-5); it invokes procedure $\mathsf{Expand}$ to process $v$ and
to grow $G_{s}$. (3) The process continues until either a nontrivial
$k$-$\mathsf{RCW}$ $G_{s}$ for $V_{T}$ is identified and is returned (line
13), or no such structure can be found, and trivial explanations are returned
(lines 5 and 11).

Procedure $\mathsf{Expand}$. The procedure $\mathsf{Expand}$ iteratively
explores an unvisited node pair $(u,u^{\prime})$ in $G\setminus G_{s}$ and
iteratively estimates if the worst-case margin is affected by including
$(u,u^{\prime})$ in a $k$-disturbance. If $m^{*}_{l,c}$ is less than $0$, a
$k$-disturbance is enlisted to $v.Q_{k}$ to augment $G_{s}$ for further
verification.

In particular for $\mathsf{APPNPs}$ under $(k,b)$-disturbance,
$\mathsf{Expand}$ implements the greedy policy iteration process in the
procedure $\mathsf{verifyRCW}$-$\mathsf{APPNP}$ (which replaces lines 5-6 with
an implementation that simulates lines 7-10 of
$\mathsf{verifyRCW}$-$\mathsf{APPNP}$), to expand $G_{s}$ with the optimal
edge set $E^{*}_{k}$

Figure 2: Generating robust witness for $G_{1}$ with expansion and
verification.

Example 4: Figure 2 illustrates the expansion and verification process.
Consider the mutagenic molecule graph $G_{1}$ with two test nodes $V_{T}$ =
$\\{v_{1},v_{2}\\}$, and set $k$=2, $b$=1. Both nodes $v_{1}$ and $v_{2}$ are
labeled ‘mutagenic’ by an $\mathsf{APPNP}$ ${\mathcal{M}}$. A currently
verified $2$-$\mathsf{RCW}$ $G_{w1}$ is identified for node $v_{1}$ (with bold
edge), which contains $v_{1}$ and its three direct neighbors.

(1) Given $G_{w1}$, we start with $v_{2}$. On the right figure,
$\mathsf{RoboGExp}$ invokes $\mathsf{Expand}$ to estimate, from the
”changeable” area $(G_{1}\setminus G_{w1})$, those node pairs that are most
likely to maximize the worst-case margin of $v_{2}$ from ‘mutagenic’ to
‘nonmutagenic’ if disturbed. Assume that we have two possible $E_{expand}^{*}$
for augmentation, which lead to two possible $G_{s}$ to be verified after
$\mathsf{Expand}$: $G_{w1}\cup\\{e_{1},e_{3}\\}$ and
$G_{w1}\cup\\{e_{2},e_{4}\\}$.
(2) In the verification phase, $\mathsf{verifyRCW}$-$\mathsf{APPNP}$ invokes
$\mathsf{PRI}$ to generate disturbance $E_{disturb}^{*}$, i.e.,
$\\{e_{5},e_{6}\\}$. The red bold area indicated in Figure 2 is an aldehyde
structure and shows the ‘mutagenic’ property under the disturbance. The
$G_{w1}\cup\\{e_{2},e_{4}\\}$ fails the verification since the augmented part
is not associated with any ‘mutagenic’ structure, while
$G_{w1}\cup\\{e_{1},e_{3}\\}$ reaches to the carbon node in the aldehyde
structure, which is responsible for ‘mutagenic’, ensuring the inclusion of
‘mutagenic’ structure and explains the label of $v_{2}$ under disturbance.
Finally, the bold structure on the right graph, denoted as $G_{w2}$, is the
$\mathsf{RCW}$ that it finds. $\Box$

Analysis. Algorithm $\mathsf{RoboGExp}$ always terminates with either a non-
trivial $k$-$\mathsf{RCW}$, or trivial cases. For the time cost, (1) it takes
a total verification cost in $O(N\times I)$ (line 4), where $N$ is the total
number of $k$-disturbances being verified, and $I$ is the
$\mathsf{GNN}$-specific single inference cost, which is typically bounded in
$O(L|E|F+L|V|F^{2})$ for representative $\mathsf{GNNs}$ (_e.g.,_
$\mathsf{GCNs}$, $\mathsf{GATs}$, $\mathsf{GraphSage}$, $\mathsf{APPNPs}$)
[40, 43]. Procedure $\mathsf{Expand}$ takes $O(|G|I)$ time, as $G_{s}$ grows
at most $|V|+|E|$ times555Note that although $G_{s}$ considers node pairs in
$|V|\times|V|$, it only grows to size $|G|$ and does not add node pairs
already included.. The total cost is thus in $O((N+|G|)L|E|F+L|V|F^{2})$.

Specifically for $\mathsf{APPNPs}$, the algorithm $\mathsf{RoboGExp}$ invokes
procedure $\mathsf{verifyRCW}$-$\mathsf{APPNP}$ to verify $k$-$\mathsf{RCW}$,
set $G^{\prime}=|G\setminus G_{s}|$, $d_{m}$ as the maximum degree, as
analyzed in Algorithm 1, it takes $O(L|G^{\prime}|\cdot(d_{m}\log
d_{m}+LF(|E|+|V|F)))$ time to process each node $v\in V_{T}$. The optimal node
pairs $E^{*}_{k}$ for a node $v$ only need to be computed once in
$\mathsf{verifyRCW}$-$\mathsf{APPNP}$ (line 8) or by $\mathsf{Expand}$ (line
6) via a deterministic process, hence the procedure $\mathsf{Expand}$ does not
incur additional verification, and has cost $O(k|V_{T}|)$. Thus the total cost
is $O(L|G^{\prime}||V_{T}|\cdot(d_{m}\log d_{m}+LF(|E|+|V|F)+k))$. Here $L$ is
usually a small constant, and $|V_{T}|$ and $d_{m}$ are relatively much
smaller compared with $|V|$ and $|E|$, respectively.

Given the above analysis, Lemma IV and Theorem V follow.

##  VI Parallel Witness Generation

When the graph is large, the verification of $k$-$\mathsf{RCW}$ can be
expensive and is a major bottleneck. We next present a parallel algorithm,
denoted as $\mathsf{paraRoboGExp}$ and is illustrated as Algorithm 3. Our idea
is to parallelize the verification into a smaller manageable tasks
<$G_{i},G_{s},j$>, each of which checks “if there is a disturbance from
$G_{i}$ alone that disproves $G_{s}$ to be a $j$-$\mathsf{RCW}$ of
$M(v,G)$=$l$”, and performs parallelized verification for each fragment
$G_{i}$ of $G$.

Given Lemma II-B, we observe the following result.

Lemma 6: Given a subgraph $G_{i}$ of $G\setminus G_{s}$, If there is a
$j$-disturbance $E^{i}_{j}$ in $G_{i}\setminus G_{s}$, and applying
$E^{i}_{j}$ to $G$ changes the result $M(v,G)$ = $l$, then $G_{s}$ is not a
$k$-$\mathsf{RCW}$ for $M(v,G)$=$l$, for any $k\geq j$. $\Box$

Algorithm 3 Algorithm $\mathsf{paraRoboGExp}$

0: Graph $G=\\{G_{1},G_{2},\dots,G_{n}\\}$, test nodes $V_{T}$, and $k$.

0: A $k$-$\mathsf{RCW}$ $G_{s}$ of $V_{T}$ _w.r.t._ ${\mathcal{M}}$. /*At
Coordinator $s_{0}$*/

1: initialize $G_{s}$=${\mathcal{V}}_{T}$; set $E_{k}$=$\emptyset$; queue $Q$
= $V_{T}$;

2: compute bitmap $B$ of adjacency matrix of $G$

3: while $Q\neq\emptyset$ do

4: $Q$=$\\{v|v~{}\text{is not in $G_{s}$},v\in V_{T}\\}$;

5: node $v$=$Q.{\mathsf{dequeue}}()$;

6: for $j=1$ to $k$ do

7: $G^{i}_{s_{j}}$ = ${\mathsf{paraExpand}}(C,G_{i},G_{s},j,B_{j})$;
/*parallel expansion*/

8: ${\mathsf{paraverifyRCW}}(C,G^{i}_{s_{j}},G_{s},j,B_{j})$;/*Parallel
verification*/

9: synchronize $B$;

10: $G_{s_{j}}$= $\bigcup_{i=1}^{n}G^{i}_{s_{j}}$;

11: if ${\mathsf{verifyRCW}}(C,G_{s_{j}},B_{j})$=$\mathsf{false}$ then

12: update $B_{j}$; continue;

13: return $G_{s}$;

Partition. The algorithm $\mathsf{paraRoboGExp}$ works with a coordinator site
$S_{0}$ and $n$ workers $\\{S_{1},\ldots S_{n}\\}$. Given a configuration $C$
= $(G,V_{T},M,k)$, it ensures an “inference preserving partition” such that
local verification and inference can be conducted. (1) The $\mathsf{GNN}$
model ${\mathcal{M}}$ is duplicated at each site. (2) The graph $G$ is
fragmented into $n$ partitions $\\{G_{1},\ldots G_{n}\\}$ through edge-cut
based partition where each worker $S_{i}$ processes one fragment $G_{i}$. For
each “border node” $v$ that resides in fragment $G_{i}$, its $k$-hop neighbors
are duplicated in $G_{i}$, to ensure that no data exchange is needed for
parallel verification. (3) Each row of the adjacency matrix is converted into
a bitmap, a sequence of bits where each bit represents the presence (‘1’) or
absence (‘0’) of an edge from the vertex corresponding to that row to another
vertex. All local fragments share a compressed bitmap encoding $B$ of the
adjacency matrix of $G$, the node features $X^{0}$, and the common $V_{T}$,
such that $M(v,G)$ can be inferred locally without expensive data
communication.

Algorithm. Algorithm $\mathsf{paraRoboGExp}$ is illustrated as Algorithm 3. It
starts with the initialization similar to its sequential counterpart
$\mathsf{RoboGExp}$. In addition, it uses one bitmap for each worker to record
verified $k$-disturbances and a global bitmap $B$ to synchronize all
$k$-disturbances verified from each worker to avoid redundant verification. It
mainly parallelizes the computation of two procedures: $\mathsf{Expand}$, with
procedure $\mathsf{paraExpand}$ (line 8), and $\mathsf{verifyRCW}$, with
procedure $\mathsf{paraverifyRCW}$ (line 9) (not shown). It assembles an
expanded global subgraph $G_{s_{j}}$ as the union of all verified local
counterparts (line 11). As this does not necessarily ensure all disturbances
are explored, it continues to complete a coordinator side verification, yet
does not repeat the verified local ones (lines 12-13) using the global bitmap
$B$.

The procedure $\mathsf{paraExpand}$ grows the current verified
$j-1$-$\mathsf{RCW}$ $G_{s_{j-1}}$ at each site in parallel, and sends the
locally expanded $G^{i}_{s_{j}}$ to the coordinator with locally expanded node
pairs that can optimize the worst case margin $m^{*}_{l,c}(v)$. Similarly, the
procedure $\mathsf{paraverifyRCW}$ examines and only sends $G^{i}_{s_{j}}$
that remains to be a $\mathsf{CW}$, and updates the bitmap $B$ with the
verified local $k$-disturbance.

Analysis. The algorithm $\mathsf{paraRoboGExp}$ correctly parallelizes the
computation of its sequential counterpart $\mathsf{RoboGExp}$, as guarded by
the coordinator side verification, and reduces unnecessary data shipment and
verification, given Lemma VI. For the parallel cost, there are at most
$k|V_{T}|$ rounds of parallel computation. The total time cost (including
communication cost) is $O(\frac{|G|+|B|)(L|E|F+L|V|F^{2})}{n}+I_{0}\cdot
L|E|F+L|V|F^{2})$. Here $I_{0}$ refers to the number of $k$-disturbances
verified at the coordinator. Algorithm $\mathsf{paraRoboGExp}$ reduces
unnecessary and redundant verification. This analysis verifies that
$\mathsf{paraRoboGExp}$ scales well as more processors are used.

##  VII Experimental Study

We experimentally evaluate our algorithms with three real-world and one
synthetic datasets. We evaluate the following: (RQ1): (a) the quality of the
$k$-$\mathsf{RCWs}$ generated by $\mathsf{RoboGExp}$ in terms of robustness
and fidelity measures; (b) the impact of critical factors, including test node
size $|V_{T}|$ and degree of disturbances ($k$), to the quality; (RQ2): (a)
the efficiency of $\mathsf{RoboGExp}$ and $\mathsf{paraRoboGExp}$ for large
graphs, (b) the impact of $|V_{T}|$ and $k$ to efficiency, and (RQ3): The
scalability of $\mathsf{paraRoboGExp}$. We also perform two case study
analyses to showcase real applications of $\mathsf{RoboGExp}$. The codes and
datasets are made available at [44].

###  VII-A Experiment settings

Datasets. Our datasets are summarized below (Table II):

(1) $\mathsf{BAHouse}$ [14], a synthetic dataset, uses a Barabási-Albert graph
as the base with a house motif. Each node has 5 neighbors on average, with
motifs labeled 1, 2, and 3 as ‘roof’, ‘middle’, and ‘ground’. The remaining
nodes are labeled 0.

(2) $\mathsf{PPI}$ [45], a protein-protein interaction dataset, contains human
proteins (nodes) and their interactions (edges). Node features include motif
gene sets and immunological signatures, labeled by gene ontology sets
reflecting functional properties.

(3) $\mathsf{CiteSeer}$ [46] is a citation dataset for computer science. Each
node is a publication with edges as citation relations. There are 6 classes:
Agents, AI, DB, IR, ML, and HCI. “Agents” specifically pertains to papers
related to the field of autonomous agents and multi-agent systems. Each node
features a binary vector for keyword occurrences.

(4) $\mathsf{Reddit}$ [47] is a large-scale social network dataset with
hundreds of millions of edges and a set of nodes (posts) with features and
node classes. Node features are word vectors, and node labels are communities
in which the post belongs.

For injecting $k$-disturbances, we adopt a strategy that mainly removes
existing edges to capture cases that establish new links in real networks may
be expensive 666Other disturbance strategy exists such as insertion-only or
random attacks; the best choice is application-specific..

TABLE II: Statistics of Datasets

Dataset | # nodes | # edges | # node features | # class labels
---|---|---|---|---
$\mathsf{BAHouse}$ | 300 | 1500 | - | 4
$\mathsf{PPI}$ | 2,245 | 61,318 | 50 | 121
$\mathsf{CiteSeer}$ | 3,327 | 9,104 | 3,703 | 6
$\mathsf{Reddit}$ | 232,965 | 114,615,892 | 602 | 41

GNN Classifiers. Following the evaluation of $\mathsf{GNN}$ explanation [15,
14, 17, 16], we adopt standard message-passing graph convolutional network
($\mathsf{GCNs}$) configured with $3$ convolution layers, each featuring an
embedding dimension of 128. We remark that our solutions are model-agnostic
and generalize to $\mathsf{GNN}$ specifications.

GNN Explainers. We compare $\mathsf{RoboGExp}$ against two recent GNN
explainers. We use the original codes and authors’ configurations for a fair
comparison. (1) $\mathsf{CF}$-$\mathsf{GNNExp}$ [34] generates counterfactual
explanations for GNNs via minimal edge deletions, but overlooks factual
explanations. (2) $\mathsf{CF\textsuperscript{2}}$ [35] integrates factual and
counterfactual reasoning for a specified test node into a single optimization
problem, allowing the generation of GNN explanations that are both necessary
and sufficient, but without robustness guarantees.

We are aware of two more recent methods [16] and [36]. Both are optimized for
counterfactual explanations. The former has source codes relying on a pre-
trained model; and the latter provides no available codes for node
classification based explanation generation. Neither discusses efficiency and
scalability of explanation generation. We thus cannot provide a fair
experimental comparison with them.

Evaluation metrics. We evaluate $\mathsf{RoboGExp}$ and other explainers based
on the following set of metrics.

(1) Normalized ${\mathsf{GED}}$. Graph edit distance (${\mathsf{GED}}$)
measures the number of edits required to transform one graph to another. We
use a normalized $\mathsf{GED}$ (defined in Eq. 3; where the graph size refers
to the total number of nodes and edges) to quantify the structural similarity
of generated $\mathsf{RCWs}$, over their counterparts from disturbed graphs.
The ${\mathsf{GED}}$ quantifies the ability that a $k$-$\mathsf{RCW}$
$G_{w}^{\prime}$ from a disturbed graph by a $k$-disturbance remains to be an
“invariant” compared to its original counterparts $G_{w}$ before
$k$-disturbances, which indicates their robustness: the smaller, the more
“robust”.

$\text{normalized
{$\mathsf{GED}$}}(G_{w},G_{w}^{\prime})=\frac{{\mathsf{GED}}(G_{w},G_{w}^{\prime})}{\max(|G_{w}|,|G^{\prime}_{w}|)}$
(3)

(2) $\mathsf{Fidelity+}$ [48]. It quantifies the deviations caused by removing
the explanation subgraph from the input graph. Fidelity+ evaluates the
counterfactual effectiveness. A higher Fidelity+ score indicates better
distinction, hence the better. Below, $\mathbbm{1}$ is 1 if $M(v,G)=l$, and 0
otherwise.

$Fidelity+=\frac{1}{|V_{T}|}\mathop{\sum}_{v\in
V_{T}}(\mathbbm{1}(M(v,G)=l)-\mathbbm{1}(M(v,G\setminus G_{s})=l))$

(3) $\mathsf{Fidelity-}$ [48]. It quantifies the difference between the
results over $G$ and the generated $\mathsf{RCWs}$, indicating a factual
accuracy. Ideal Fidelity- scores are low, even negative, indicating perfectly
matched or even stronger predictions.

$Fidelity-=\frac{1}{|V_{T}|}\mathop{\sum}_{v\in
V_{T}}(\mathbbm{1}(M(v,G)=l)-\mathbbm{1}(M(v,G_{s})=l))$

(4) Generation Time. The total response time on generating explanations for
all the test nodes $|V_{T}|$. To evaluate the impact of the factor $k$ on
$k$-disturbances to generation time, we report the total response time it
takes to “re-generate” the explanations for each method. The learning-based
methods $\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$
require retraining upon the change of graphs. We include the training and
generation costs for both.

Environment. Our algorithms are implemented in Python 3.8.1 by PyTorch-
Geometric framework [49]. All experiments are conducted on a Linux system
equipped with 2 CPUs, each possessing 16 cores and 256 GB RAM.

###  VII-B Experiment results

Exp-1: Effectiveness: quality of explanations (RQ1(a)). Using
$\mathsf{CiteSeer}$, we first evaluate the effectiveness of
$\mathsf{RoboGExp}$, $\mathsf{CF\textsuperscript{2}}$, and
$\mathsf{CF}$-$\mathsf{GNNExp}$ in terms of the quality of the explanations
they generate. The results over other datasets are consistent, hence omitted.

Quality of Explanations. Setting $k$ = $20$, and $|V_{T}|$ = $20$, we report
the quality of the explanation structures of $\mathsf{RoboGExp}$,
$\mathsf{CF\textsuperscript{2}}$, and $\mathsf{CF}$-$\mathsf{GNNExp}$ in Table
III. The table shows that $\mathsf{RoboGExp}$ outperforms both
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ for all
three metrics. (1) $\mathsf{RoboGExp}$ outperforms
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ by twice
and $2.3$ times in terms of $\mathsf{GED}$. This demonstrates that it can
generate explanations that are much more stable in structural similarity over
the disturbance of underlying graphs. (2) $\mathsf{RoboGExp}$ achieves best
scores in $\mathsf{Fidelity+}$ and $\mathsf{Fidelity-}$, outperforming
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$. These
indicate that $\mathsf{RoboGExp}$ can generate explanations as $\mathsf{RCWs}$
that stay consistent with the results of $\mathsf{GNN}$ classification
simultaneously as factual, and counterfactual explanations.

We remark that the $\mathsf{RCWs}$, by definition, should be theoretically
achieving $\mathsf{Fidelity+}$ as $1.0$ and $\mathsf{Fidelity-}$ $0.0$, as
counterfactual and factual witnesses, respectively. The reason that it does
not achieve the theoretical best scores is due to the fact that not all the
test nodes retain the same labels, leading to non-existence of non-trivial
$k$-$\mathsf{RCWs}$ in some cases.

We also compare the size of the explanations. $\mathsf{RoboGExp}$ generate the
smallest size, which is on average half of their
$\mathsf{CF\textsuperscript{2}}$ counterparts.
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ produce
explanations as the union of subgraph structures at instance-level (for single
test node), which may contain redundant nodes and edges that occur more than
once. The explanation subgraphs produced by $\mathsf{RoboGExp}$ are more
concise, due to which their generation targets for all test nodes in a greedy
selection approach.

TABLE III: Quality of explanations ($\mathsf{CiteSeer}$) | NormGED | Fidelity+ | Fidelity- | Size
---|---|---|---|---
$\mathsf{RoboGExp}$ | 0.32 | 0.79 | 0.05 | 66
$\mathsf{CF\textsuperscript{2}}$ | 0.68 | 0.47 | 0.06 | 132
$\mathsf{CF}$-$\mathsf{GNNExp}$ | 0.72 | 0.65 | 0.13 | 78

Exp-2: Effectiveness: impact of factors (RQ1(b)). We next investigate the
impact of the size of disturbance $k$ and test size $|{\mathcal{V}}_{T}|$ on
the effectiveness of $\mathsf{RoboGExp}$, $\mathsf{CF\textsuperscript{2}}$,
and $\mathsf{CF}$-$\mathsf{GNNExp}$. We report their performances in Fig 3.

Varying $k$. Fixing $|{\mathcal{V}}_{T}|=20$, we vary $k$ from $4$ to $20$,
and report the results in Fig 3(a), (c), and (e).

(1) Fig 3(a) shows us that for all approaches, $\mathsf{GED}$ increases for
larger $k$. Increasing $k$ implies a more substantial disturbance, and
accordingly larger variance to the underlying graph, hence larger differences
in $\mathsf{RCWs}$ to retain the label of $V_{T}$. Due to the similar reason,
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ exhibit
larger $\mathsf{GED}$. On the other hand, $\mathsf{RoboGExp}$ consistently
outperforms $\mathsf{CF\textsuperscript{2}}$ and
$\mathsf{CF}$-$\mathsf{GNNExp}$. For example, it outperforms both when $k$ =
$20$, with a $\mathsf{GED}$ that remains better than the best scores
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ can
reach.

(2) Fig 3(c) verifies that in general, all three methods achieve higher
$\mathsf{Fidelity+}$ as $k$ becomes larger. Meanwhile, $\mathsf{RoboGExp}$
maintains higher and more stable $\mathsf{Fidelity+}$ than
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$, for all
cases. We found that with $|V_{T}|$ unchanged, larger $k$ allows
$\mathsf{RoboGExp}$ to explore more $k$-disturbances “outside” of
$\mathsf{RCWs}$, and identify edges that are more likely to change the node
labels. By incorporating such edges into $\mathsf{RCWs}$, the generated
explanations are also closer to the decision boundary. This verifies that
$\mathsf{RoboGExp}$ is able to respond better to larger structural variance of
graphs and find counterfactual structures that better approximate the decision
boundary of $\mathsf{GNNs}$. $\mathsf{RoboGExp}$ remains least sensitive due
to its ability to find robust explanations under disturbances.
$\mathsf{CF}$-$\mathsf{GNNExp}$ outperforms $\mathsf{CF\textsuperscript{2}}$
due to its specialized learning goal towards counterfactual property.

Figure 3: Effectiveness with Impact Factors

(3) In Fig 3(e), all methods have improved results with smaller
$\mathsf{Fidelity-}$ as $k$ becomes larger. The erratic trend in
$\mathsf{CF\textsuperscript{2}}$’s $\mathsf{Fidelity-}$ score is indicative of
its less consistent factual explanation generation process, particularly when
the graph is subjected to disturbances. Comparing
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$,
$\mathsf{CF\textsuperscript{2}}$ is able to achieve $\mathsf{Fidelity-}$
scores that are closer to $\mathsf{RoboGExp}$, due to that it considers both
factual and counterfactual explanations, while $\mathsf{CF}$-$\mathsf{GNNExp}$
is optimized for generating counterfactual explanations. Similar to
$\mathsf{Fidelity+}$, larger $k$ allows $\mathsf{RoboGExp}$ to explore more
disturbances and increases its chance to identify factual and counterfactual
structures, resulting in a lower $\mathsf{Fidelity-}$.

Varying $|{\mathcal{V}}_{T}|$. Fixing $k=20$, we vary $|{\mathcal{V}}_{T}|$
from $20$ to $100$, and present the results in Fig 3(b), (d), and (f).

(1) Fig 3(b) depicts the following. $\mathsf{RoboGExp}$ remains to outperform
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$
constantly in all cases. Both $\mathsf{RoboGExp}$ and
$\mathsf{CF\textsuperscript{2}}$ exhibit a relatively stable performance in
$\mathsf{GED}$ as $|{\mathcal{V}}_{T}|$ varies from $20$ to $100$.
$\mathsf{CF\textsuperscript{2}}$ is quite stable due to its goal of seeking
factual and counterfactual explanations, which may have helped it identify
similar structures. $\mathsf{CF}$-$\mathsf{GNNExp}$ is quite sensitive to
larger $|V_{T}|$, due to larger test nodes introducing more structurally
different explanations.

(2) In Fig 3(d), all methods have lower $\mathsf{Fidelity+}$ scores as
$|V_{T}|$ becomes larger. As more test nodes are introduced, it becomes
difficult to maintain a counterfactual explanation due to more diverse
structures. $\mathsf{CF\textsuperscript{2}}$ optimizes on both factual and
counterfactual explanations, and demonstrates more sensitive behavior.
$\mathsf{CF}$-$\mathsf{GNNExp}$ outperforms $\mathsf{CF\textsuperscript{2}}$
in this case due to its optimization for only counterfactual explanations. On
the other hand, $\mathsf{RoboGExp}$ remains to outperform
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$, and is
least sensitive to $|V_{T}|$. It is likely that the goal to find stable
explanation for all test nodes greatly mitigates the impact of the additional
diversity introduced by larger $V_{T}$.

(3) In Fig 3(f), all three methods find it difficult to maintain
$\mathsf{Fidelity-}$ as $|V_{T}|$ is larger. $\mathsf{RoboGExp}$ continues to
achieve the best $\mathsf{Fidelity-}$ scores. The difference is that
$\mathsf{CF\textsuperscript{2}}$ in turn outperforms
$\mathsf{CF}$-$\mathsf{GNNExp}$ and is able to achieve $\mathsf{Fidelity-}$
scores closer to $\mathsf{RoboGExp}$, due to its optimization on both factual
and counterfactual explanations. In general, $\mathsf{RoboGExp}$ remains the
least sensitive to $V_{T}$, due to its prioritization strategy and enforcement
of robustness verification.

Exp-3: Efficiency (RQ2). We report the efficiency of $\mathsf{RoboGExp}$,
$\mathsf{CF\textsuperscript{2}}$, and $\mathsf{CF}$-$\mathsf{GNNExp}$ in Fig
4. By default, we set $k=20$, $|{\mathcal{V}}_{T}|=20$, and test with
$\mathsf{CiteSeer}$.

Overall efficiency. Fig 4(a) shows the response time of $\mathsf{RoboGExp}$,
$\mathsf{CF\textsuperscript{2}}$, and $\mathsf{CF}$-$\mathsf{GNNExp}$ for
three real-world datasets: $\mathsf{BAHouse}$, $\mathsf{CiteSeer}$, and
$\mathsf{PPI}$. $\mathsf{RoboGExp}$ constantly outperforms
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ for all
datasets. We found that the later two incur major overhead in the learning
process to infer the explanations, which remains a main bottleneck and
sensitive to large graphs with enriched features. Our methods explore bounded
numbers of $k$-disturbances with efficient expansion and verification
algorithms, and avoid unnecessary $\mathsf{GNN}$ inferences. For example,
$\mathsf{RoboGExp}$ takes only 58.6% of the time of
$\mathsf{CF}$-$\mathsf{GNNExp}$ and 12.03% of the time of
$\mathsf{CF\textsuperscript{2}}$ to find explanations that are factual,
counterfactual, and robust. Moreover, upon the disturbance of graph $G$,
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ require
retraining and “re-generate” explanations, while $\mathsf{RoboGExp}$ can be
applied to find robust explanations “once-for-all” for any variants of $G$
under $k$-disturbance.

Figure 4: Scalability and Efficiency

Impact of $k$. Using the same setting as in its effectiveness counterparts in
Figs. 3 (a), (c), and (e), we report the response time of $\mathsf{RoboGExp}$,
$\mathsf{CF\textsuperscript{2}}$, and $\mathsf{CF}$-$\mathsf{GNNExp}$ as $k$
varies from $4$ to $20$. All methods take more time as $k$ becomes larger. As
expected, $\mathsf{RoboGExp}$ takes more time to verify a larger number of
$k$-disturbances, yet still benefits from its localized search in “nearby”
area of the explanations. Both $\mathsf{CF\textsuperscript{2}}$ and
$\mathsf{CF}$-$\mathsf{GNNExp}$ incur increased overhead in learning; the
difference is that $\mathsf{CF\textsuperscript{2}}$ directly re-learns the
matrix representation, and $\mathsf{CF}$-$\mathsf{GNNExp}$ re-learns to remove
edges to sparsify the matrix, hence benefits better from removal-heavy
disturbances.

Varying $|{\mathcal{V}}_{T}|$. Using the same setting as in its effectiveness
counterparts in Figs. 3 (b), (d), and (f), we evaluate the impact of $|V_{T}|$
by varying it from $20$ to $100$. As shown in Figure 4(c), $\mathsf{RoboGExp}$
scales well and is insensitive in response time, due to its prioritization
strategy that favors the processing of test nodes which are unlikely to have
labels changed given current explanations. In contrast, both
$\mathsf{CF\textsuperscript{2}}$ and $\mathsf{CF}$-$\mathsf{GNNExp}$ are
sensitive, due to that both re-generate explanations each time $V_{T}$
changes, and incur higher cost with more test nodes.

Exp-4: Scalability (RQ3). We next evaluate the scalability of
$\mathsf{paraRoboGExp}$, in terms of the number of threads and $k$. Fig 4(d)
verifies the result over a large real-world dataset $\mathsf{Reddit}$.
$\mathsf{paraRoboGExp}$ scales well as the number of threads increases, with
consistent impact due to larger $k$. The generation time is improved by 70.7%
as the number of threads varies from $2$ to $10$ when $k$=10. The result
verifies that it is practical to generate explanations over large graphs, and
the response time can be effectively better improved for larger-scale
disturbances (i.e., when $k$ is larger).

Exp-5: Case Analysis. We next present two case studies, to showcase the
application scenarios of $\mathsf{RoboGExp}$.

Deciphering invariant in drug structures. Fig. 5 depicts a chemical compound
graph $G_{3}$ with a test node $v_{3}$ classified as “Mutagenic”. On the top
right is the $\mathsf{RCW}$ $G_{w3}$ generated by $\mathsf{RoboGExp}$, which
preserves the aldehyde structure in the blue area – crucial for recognizing
$v$ as a component from a toxic fraction. $\mathsf{CF\textsuperscript{2}}$
generates a larger explanation $G^{\prime}_{w3}$. For two molecule variants
$G^{1}_{3}$ and $G^{2}_{3}$ of $G_{3}$ obtained by removing the edge $e_{7}$
and edge $e_{8}$, respectively, $\mathsf{RoboGExp}$ verifies that $G_{w3}$
remains to be a $1$-$\mathsf{RCW}$ for the family of all three compounds,
while $\mathsf{CF\textsuperscript{2}}$ generates two different explanations
$G^{\prime 1}_{w3}$ and $G^{\prime 2}_{w3}$. Observe that in both $G^{\prime
1}_{w3}$ and $G^{\prime 2}_{w3}$, their aldehyde structure contains one
redundant connection to a hydrogen atom, which will change the label of
$v_{3}$ to “nonmutagen”. Indeed, while the structure O-C-H is easy to be
recognized as a toxic fragment responsible for mutagenic property, and is
preserved in $G_{w3}$, additional “noisy” substructure that contains O, C, and
two H is included to $\mathsf{CF\textsuperscript{2}}$ generated structures,
making it hard to distinguish the node to be in a mutagenic fraction or not.

Figure 5: Case Study: Left: a small $\mathsf{RCW}$ that capture an invariant
structure for three variants of a drug structure; Right: an $\mathsf{RCW}$
that explains topic change with matching new citations.

Explaining topic change with new references. Our second case shows that
$\mathsf{RoboGExp}$ is able to respond quickly to the change of true labels
with new explanation. Consider $G_{4}$ from $\mathsf{CiteSeer}$ with a node (a
paper) about Quantum Computing, which has the label ‘Physics’, and has an
explanation $G_{w4}$ found by $\mathsf{RoboGExp}$ that identifies its relevant
papers, all in physics area. Recent citations “disturb” $G_{4}$ to $G_{5}$
with new neighbors that cite the paper from computer sciences, via which the
$\mathsf{GCN}$ ${\mathcal{M}}$ updates its label to be “Computer Science”.
$\mathsf{RoboGExp}$ responds by discovering a new explanation $G_{w5}$, with
small changes that include a majority of major computer science citations and
less from physics. This verifies that $\mathsf{RoboGExp}$ strikes a balance
between factual and robustness as the true label changes.

##  VIII Conclusion

We proposed $k$-robust counterfactual witnesses ($k$-$\mathsf{RCW}$), an
explanation structure for $\mathsf{GNN}$-based classification, that are
factual, counterfactual, and robust to $k$-disturbances. We established the
hardness and feasibility results, from tractable cases to
co-$\mathsf{NP}$-hardness, for both verification and generation problems. We
introduced feasible algorithms to tackle the verification and generation
problems, and parallel algorithms to generate $\mathsf{RCWs}$ for large
graphs. Our experimental study verified the efficiency of explanation
generation, and the quality of the explanations, and their applications. A
future topic is to enhance our solution to generate minimum explanations, and
evaluate their application for other $\mathsf{GNNs}$-based tasks.

Acknowledgment. Dazhuo Qiu and Mengying Wang contributed equally. Qiu and Khan
acknowledge support from the Novo Nordisk Foundation grant NNF22OC0072415.
Wang and Wu are supported in part by NSF under CNS-1932574, ECCS-1933279,
CNS-2028748 and OAC-2104007.

## References

  * [1] J. You, B. Liu, Z. Ying, V. Pande, and J. Leskovec, “Graph convolutional policy network for goal-directed molecular graph generation,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 31, 2018.
  * [2] E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility: user movement in location-based social networks,” in _ACM International Conference on Knowledge Discovery and Data Mining (KDD)_ , 2011, pp. 1082–1090.
  * [3] L. Wei, H. Zhao, Z. He, and Q. Yao, “Neural architecture search for gnn-based graph classification,” _ACM Transactions on Information Systems_ , 2023.
  * [4] T. Chen, D. Qiu, Y. Wu, A. Khan, X. Ke, and Y. Gao, “View-based explanations for graph neural networks,” in _ACM International Conference on Management of Data (SIGMOD)_ , 2024.
  * [5] J. Zhou, A. H. Gandomi, F. Chen, and A. Holzinger, “Evaluating the quality of machine learning explanations: A survey on methods and metrics,” _Electronics_ , vol. 10, no. 5, p. 593, 2021.
  * [6] J. Xiong, Z. Xiong, K. Chen, H. Jiang, and M. Zheng, “Graph neural networks for automated de novo drug design,” _Drug Discovery Today_ , vol. 26, no. 6, pp. 1382–1393, 2021.
  * [7] M. Jiang, Z. Li, S. Zhang, S. Wang, X. Wang, Q. Yuan, and Z. Wei, “Drug–target affinity prediction using graph neural network and contact maps,” _RSC advances_ , vol. 10, no. 35, pp. 20 701–20 712, 2020.
  * [8] L. David, A. Thakkar, R. Mercado, and O. Engkvist, “Molecular representations in ai-driven drug discovery: a review and practical guide,” _Journal of Cheminformatics_ , vol. 12, no. 1, pp. 1–22, 2020.
  * [9] A. M. Albalahi, A. Ali, Z. Du, A. A. Bhatti, T. Alraqad, N. Iqbal, and A. E. Hamza, “On bond incident degree indices of chemical graphs,” _Mathematics_ , vol. 11, no. 1, p. 27, 2022.
  * [10] J. Kazius, R. McGuire, and R. Bursi, “Derivation and validation of toxicophores for mutagenicity prediction,” _Journal of Medicinal Chemistry_ , vol. 48, no. 1, pp. 312–320, 2005.
  * [11] H. Ding, J. Zhai, D. Deng, and S. Ma, “The case for learned provenance graph storage systems,” in _32nd USENIX Security Symposium (USENIX Security 23)_ , 2023, pp. 3277–3294.
  * [12] T. Bilot, N. El Madhoun, K. Al Agha, and A. Zouaoui, “Graph neural networks for intrusion detection: A survey,” _IEEE Access_ , 2023.
  * [13] W. U. Hassan, A. Bates, and D. Marino, “Tactical provenance analysis for endpoint detection and response systems,” in _2020 IEEE Symposium on Security and Privacy (SP)_ , 2020, pp. 1172–1189.
  * [14] Z. Ying, D. Bourgeois, J. You, M. Zitnik, and J. Leskovec, “Gnnexplainer: Generating explanations for graph neural networks,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 32, 2019.
  * [15] H. Yuan, H. Yu, J. Wang, K. Li, and S. Ji, “On explainability of graph neural networks via subgraph explorations,” in _International Conference on Machine Learning (ICML)_ , 2021, pp. 12 241–12 252.
  * [16] Z. Huang, M. Kosan, S. Medya, S. Ranu, and A. Singh, “Global counterfactual explainer for graph neural networks,” in _WSDM_ , 2023.
  * [17] S. Zhang, Y. Liu, N. Shah, and Y. Sun, “Gstarx: Explaining graph neural networks with structure-aware cooperative games,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2022.
  * [18] H. Yuan, J. Tang, X. Hu, and S. Ji, “Xgnn: Towards model-level explanations of graph neural networks,” in _ACM international conference on knowledge discovery and data mining (KDD)_ , 2020, pp. 430–438.
  * [19] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [20] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [21] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [22] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _ICLR_ , 2019.
  * [23] J. Klicpera, A. Bojchevski, and S. Günnemann, “Predict then propagate: Graph neural networks meet personalized pagerank,” in _ICLR_ , 2019.
  * [24] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , 2017, pp. 1024–1034.
  * [25] M. Zhang, Z. Cui, M. Neumann, and Y. Chen, “An end-to-end deep learning architecture for graph classification,” in _AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [26] Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec, “Hierarchical graph representation learning with differentiable pooling,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 31, 2018.
  * [27] J. Du, S. Wang, H. Miao, and J. Zhang, “Multi-channel pooling graph neural networks.” in _IJCAI_ , 2021, pp. 1442–1448.
  * [28] M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 31, 2018.
  * [29] M. D. Zeiler and R. Fergus, “Visualizing and understanding convolutional networks,” in _Computer Vision (ECCV)_ , 2014, pp. 818–833.
  * [30] R. Schwarzenberg, M. Hübner, D. Harbecke, C. Alt, and L. Hennig, “Layerwise relevance visualization in convolutional text graph classifiers,” in _Workshop on Graph-Based Methods for Natural Language Processing (TextGraphs@EMNLP)_ , 2019, pp. 58–62.
  * [31] Q. Huang, M. Yamada, Y. Tian, D. Singh, and Y. Chang, “Graphlime: Local interpretable model explanations for graph neural networks,” _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * [32] M. S. Schlichtkrull, N. De Cao, and I. Titov, “Interpreting graph neural networks for nlp with differentiable edge masking,” in _ICLR_ , 2021.
  * [33] D. Luo, W. Cheng, D. Xu, W. Yu, B. Zong, H. Chen, and X. Zhang, “Parameterized explainer for graph neural network,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 33, pp. 19 620–19 631, 2020.
  * [34] A. Lucic, M. A. Ter Hoeve, G. Tolomei, M. De Rijke, and F. Silvestri, “Cf-gnnexplainer: Counterfactual explanations for graph neural networks,” in _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , vol. 151, 2022, pp. 4499–4511.
  * [35] J. Tan, S. Geng, Z. Fu, Y. Ge, S. Xu, Y. Li, and Y. Zhang, “Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning,” in _Proceedings of the ACM Web Conference 2022_ , 2022, pp. 1018–1027.
  * [36] M. Bajaj, L. Chu, Z. Y. Xue, J. Pei, L. Wang, P. C.-H. Lam, and Y. Zhang, “Robust counterfactual explanations on graph neural networks,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 34, pp. 5644–5655, 2021.
  * [37] A. Bojchevski and S. Günnemann, “Certifiable robustness to graph perturbations,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [38] S. Guan, H. Ma, and Y. Wu, “Robognn: Robustifying node classification under link perturbation,” in _IJCAI_ , 2022.
  * [39] M. Gardner, J. Grus, M. Neumann, O. Tafjord, P. Dasigi, N. Liu, M. Peters, M. Schmitz, and L. Zettlemoyer, “Allennlp: A deep semantic natural language processing platform,” _arXiv preprint arXiv:1803.07640_ , 2018.
  * [40] M. Chen, Z. Wei, B. Ding, Y. Li, Y. Yuan, X. Du, and J.-R. Wen, “Scalable graph neural networks via bidirectional propagation,” _Advances in neural information processing systems_ , vol. 33, pp. 14 556–14 566, 2020.
  * [41] M. Olsen and A. Viglas, “On the approximability of the link building problem,” _Theoretical Computer Science_ , vol. 518, pp. 96–116, 2014.
  * [42] R. Hollanders, J.-C. Delvenne, and R. Jungers, “Policy iteration is well suited to optimize pagerank,” _arXiv preprint arXiv:1108.3779_ , 2011.
  * [43] H. Zhou, A. Srivastava, H. Zeng, R. Kannan, and V. Prasanna, “Accelerating large scale real-time gnn inference using channel pruning,” _Proc. VLDB Endow._ , vol. 14, no. 9, 2021.
  * [44] “Code and datasets,” 2023, https://github.com/DazhuoQ/RoboGExp.
  * [45] M. Zitnik and J. Leskovec, “Predicting multicellular function through multi-layer tissue networks,” _Bioinformatics_ , vol. 33, no. 14, pp. i190–i198, 2017.
  * [46] C. L. Giles, K. D. Bollacker, and S. Lawrence, “Citeseer: An automatic citation indexing system,” in _Proceedings of the Third ACM Conference on Digital Libraries_ , 1998, p. 89–98.
  * [47] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _Advances in Neural Information Processing Systems_ , p. 1025–1035, 2017.
  * [48] H. Yuan, H. Yu, S. Gui, and S. Ji, “Explainability in graph neural networks: A taxonomic survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 45, no. 5, pp. 5782–5799, 2023.
  * [49] M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” _arXiv preprint arXiv:1903.02428_ , 2019.