V-InFoR: A Robust Graph Neural Networks Explainer for Structurally Corrupted Graphs
Authors: Senzhang Wang
Jun Yin
Chaozhuo Li
Xing Xie
Jianxin Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Explainable AI
Graph Neural Networks
Machine Learning

Abstract: GNN explanation method aims to identify an explanatory subgraph which contains the most informative components of the full graph. However, a major limitation of existing GNN explainers is that they are not robust to the structurally corrupted graphs, e.g., graphs with noisy or adversarial edges. On the one hand, existing GNN explainers mostly explore explanations based on either the raw graph features or the learned latent representations, both of which can be easily corrupted. On the other hand, the corruptions in graphs are irregular in terms of the structural properties, e.g., the size or connectivity of graphs, which makes the rigorous constraints used by previous GNN explainers unfeasible. To address these issues, we propose a robust GNN explainer called V-InfoR. Specifically, a robust graph representation extractor, which takes insights of variational inference, is proposed to infer the latent distribution of graph representations. Instead of directly using the corrupted raw features or representations of each single graph, we sample the graph representations from the inferred distribution for the downstream explanation generator, which can effectively eliminate the minor corruption. We next formulate the explanation exploration as a graph information bottleneck (GIB) optimization problem. As a more general method that does not need any rigorous structural constraints, our GIB-based method can adaptively capture both the regularity and irregularity of the severely corrupted graphs for explanation. Extensive evaluations on both synthetic and real-world datasets indicate that V-InfoR significantly improves the GNN explanation performance for the structurally corrupted graphs. Code and dataset are available at https://anonymous.4open.science/r/V-InfoR-EF88

V-InFoR: A Robust Graph Neural Networks Explainer for Structurally Corrupted Graphs
Senzhang Wang"1 Central South University szwang@csu. edu. en
Jun Yin Central South University yinjun2000@csu.c edu. cn
Chaozhuo Li Microsoft Research Asia cl @mi crosoft.
Xing Xie Microsoft Research Asia xing. xi xie@mieeeeec crosoft.. com
Jianxin Wang
Central South University j jxwangtmail. csu, edu cn
Abstract
GNN explanation method aims to identify an explanatory subgraph which contains the most informative components of the full graph. However, major limitation of existing GNN explainers is that they are not robust to the structurally corrupted graphs, e.g., graphs with noisy or adversarial edges. On the one hand, existing GNN explainers mostly explore explanations based on either the raw graph features or the learned latent representations, both of which can be easily corrupted. On the other hand, the corruptions in graphs are irregular in terms of the structural properties, e.g., the size or connectivity of graphs, which makes the rigorous con- straints used by previous GNN explainers unfeasible. To address these issues, we propose a robust GNN explainer called V-InfoR F] Specifically, robust graph representation extractor, which takes insights of variational inference, is proposed to infer the latent distribution of graph representations. Instead of directly using the corrupted raw features representations of each single graph, sample the graph representations from the inferred distribution for the downstream explanation generator, which can effectively eliminate the minor corruption. We next formulate the explanation exploration as a graph information bottleneck (GIB) optimization problem. As more general method that does not need any rigorous structural constraints, our GlB-based method can adaptively capture both the regularity and irregularity of the severely corrupted graphs for explanation. Extensive evalua- tions on both synthetic and real-world datasets indicate that V-InfoR significantly improves the GNN explanation performance for the structurally corrupted graphs.
Introduction
Nowadays, graph data ubiquitous in various domains, such as citation networks [1 3) social networks [4] (]) and chemical molecules (6). GNN has manifested promising performance in many graph tasks, e.g., node classification 7 S. link prediction [.. and graph classification [TO M. by aggregating node features in light of the topological structures. Similar to other deep learning models, GNN models also have the defect that they are non-transparent, and the prediction results lack human- intelligible explanations [12]. Precise explanations can not only make people better understand GNN predictions but also assist GNN designers in detecting underlying flaws and purifying them.
"Corresponding author.
I Eqqully contribute to this research. Code and dataset are available
EF888
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

61
dib
dlb
(a) Raw graphi (G ) 9
(b) Minor comppttion ((G') 5
(C) Severecatttiionn
(GG +
An illustration of the structurally corrupted graphs, where the solid red lines represent the newly added edges and the dashed red lines represent the removed edges. (a) is the raw graph and ý is the prediction given by GNN o: (b) represents the graph G' with minor corruption whose prediction remains ÿ: (c) shows the graph G" severely corrupted such that the predicted label of GNN on it changed.
Figure I:
GNN explainer aims to identify an explanatory subgraph, whose components exert vital influence on the prediction of the full graph [[3]. Existing GNN explanation methods generally allocate significance scores for each component of the graph, and a subgraph with the highest score is extracted as the explanation of the whole graph [14]. They optimize the allocation of the significance scores by minimizing explanation loss function [5] [3] The final explanation provided by GNN explainer includes a subgraph structure along with the corresponding node features.
However, a major limitation of existing works is that they mostly focus on designing effective significance score allocation methods, but ignore such a critical problem: Whether and to what extent structurally corrupted graph will affect the performunce of the GNN explainer? In many real application scenarios, the graphs may contain various corruptions, such as noise [6. 17 and
adversarial edges [18 19 20)) Existing methods directly adopt the raw graph features 21 22 15 23
or the latent graph representations [3] 24, 25] as the input of the explainer model, and thus the output explanation may not be reliable when the input is corrupted. Previous work has shown that the explanation of deep neural networks is fragile to attacked images [26]. Thus whether the structurally corrupted graphs will remarkably affect the performance of the GNN explainer and how to address it is an interesting problem, yet has not been fully studied and remains an open research issue.
This paper for the first time investigates how to construct robust GNN explainer for structurally corrupted graphs. As illustrated in Figure based on whether the prediction of the downstream task (e.g., graph classification) is changed, the structural corruptions of graph can be categorized into minor corruptions and severe corruptions. In Figure [a), & denotes the GNN model to be explained, and G is the raw graph. Figure [ shows the case of the graph with minor corruption G², which is not so intense that the predicted graph label remains the same as the raw graph. Figure (c) shows the case of the severely corrupted graph G" where the corruption is devastating enough to the GNN and thus results in a different prediction. Based on this example, we argue that a robust GNN explainer should satisfy the following two requirements. First, the minor corruption should be considered as redundant components and filtered by the explainer as they do not affect the final prediction. Second, the severe corruption should be identified by the explainer as part of the explanation since they the non-ignorable reason that changes the final prediction. However, it is non-trivial to meet the two requirements simultaneously due to the following two challenges.
Robust graph representation extraction to eliminate the minor corruptions. As we discussed before, existing works directly use the raw graph features or the latent graph representations of each single graph as the explanation input, which will raise the risk of the GNN explainer overfitting to corruptions 126]. This is because the raw graph features can be easily corrupted by noise or adversarial attacked edges. The latent graph representations have been proved vulnerable to structural coruptiion 27 20 How to extract a robust graph representation that can effectively filter the minor corruptions while preserving the vital information for GNN explanation exploration is challenging.
Structural irregularity of the severe corruptions. The corruptions may be of different sizes or
consist of several disconnected parts the graphs, i.e., they are irregular (8 For example, in molecule chemistry, the corruptive functional groups differ largely in terms of size (c.g.. -Cl and
2

---

-CooH in solubility analysis). Moreover, a molecule containing multiple functional groups which are disconnected from each other is common in the real-world. To meet the second requirement, the structural irregularity of severe corruption should be identified by the GNN explainer. Hence it is not reasonable to adopt some predefined rigorous constraints, e-g., size constraint or connectivity constraint that are commonly used in previous explainers, to the explanations of corrupted graphs. How to design a more general objective function to adaptively capture the structural irregularity of severe corruption is also challenging.
To address the two aforementioned challenges, we propose a robust GNN explainer for structurally corrupted graphs called V-InfoR (Variational Graph Representation based Information bottleneck Robust explainer). Specifically. V-InfoR contains two major modules. (1) Robust graph represen- tations extractor. In this module. we take insights of variational inference (29 30 to model the statistical characteristics that are shared by all the observed graphs, i.e., the mean and the standard deviation. The statistics are capable of capturing the uncertainty and variability of the observed graphs. Based on the statistics, variational graph distribution is induced, which can effectively model the common features of all the graphs and filter the minor corruption. The variational graph representations provide more robust graph representation for the downstream explanation generator. (2) Adaptive explanation generator. To address the irregularity issue of the severe corruptions, we propose an Adaptive Graph Information (AGI) constraint. The AGI constraint directly restricts the information carried by the explanation without any rigorous assumptions the structural properties (e.g., size or connectivity) of the explanation. By incorporating the AGI constraint, we formulate the GNN explanation exploration a Graph Information Bottleneck (GIB) optimization problem to adaptively capture both the regularity and irregularity of the severely corrupted graphs.
Our main contributions are summarized as follows:
This work for the first time studies the negative effect of both minor and severe structural corruptions on existing GNN explainers, and proposes robust explainer V-InfoR to effectively handle the two types of corruption.
We novelly propose to incorporate variational inference to explore GNN explanation. A variational inference based robust graph information extractor proposed to mitigate the uncertainty and variability of minor corruptions when extracting the critical graph information.
We generalize the GNN explanation exploration by introducing an adaptive graph information constraint, which can capture both the regularity and irregularity of the corrupted graphs. We also theoretically derive the variational bound of this objective to make feasibly optimizable.
Extensive experiments one synthetic dataset and three real-world datasets demonstrate the superiority of V-InfoR over state-of-the-art GNN explanation methods.
2 Preliminary and Problem Statement
In this section, we will first provide the quantitative evidence that existing GNNs explainers are fragile to structurally corrupted graphs. Then we provide a formal statement of the graph explanation problem. See Appendix B for the basic notations.
2.1 Are existing GNN explainers robust to corruptions?
To study whether existing GNN explainers are robust to corruptions, we evaluate the performance of six state-of-the-an GNN explainers when minor corruption and severe corruption are injected into the raw graphs, respectively. We use the synthetic BA-3Motifs dataset (15), which is a widely used benchmark dataset for GNN explanation. To investigate the minor corruption, we select the corrupted graphs whose predictions are unchanged after randomly flipping 20% edges. For the severe corruption, we use the SOTA graph adversarial attack algorithm GRABNEL, which formulates the attack task as Bayesian optimization problem [18]. The attack budget of GRABNEL means the highest percentage of the attacked edges. We use a 10% attack budget here, which is able to change the prediction of the selected graphs and thus can be considered as the severe corruption. FNs score used as the evaluation metric and a higher FN' score means a better explanation performance 25 The formal definition will be given later in Section 4.1

---

Full graph
Variational Inference of Latent Variable
Latent Distribution
Variational Node Representation
Edge Representation
d
E
Robust graph representation extractor
GNN
Agregool
Combine
Sampled explanation
Edge probability
Latent parametens
F
LL
MLP
Optinizzng GIB Lows
GNN
GS
X5
Adaptive explanation generator
Figure 2: The overall architecture of V-InfoR, which consists of the robust graph representation extractor and the adapative explanation generator.
The result is presented in Figure of Appendix C The histograms of the three colors represent the explainer performance on raw graphs, graphs with random noise, and attacked graphs, respectively. One can see that both the minor corruption (20% random structural noise) and the severe corruption (10% GRABNEL attack) remarkably degrade the explanation performance. Minor corruption brings about an average performance degradation of 31.15% for the six GNN explainers, and severe corruption results an average performance degradation of 40.64%. The experimental result verifies that both the minor and the severe corruplions do significuntly affect the performance of existing GNN explainers. Therefore, robust GNN explainer is required for the structurllyy corrupted graphs.
2.2 Problem formulation
Formally, given the GNN model & to be explained and the input graph G = (X, A), the explanation provided by the GNN explainer is subgraph Gs (Xs, As). As is subset of the original adjacent matrix A and contains the key structure that determines prediction largely and X is the features of nodes which associates with Ag. Existing researches show that topological information is critically important to graph classification 13). Hence, our V-InfoR focuses on the structural corruption when exploring explanation. We deem an explanation Gs sufficient when it can produce the same prediction using the full graph, and deem it necessary when the prediction will change is removed from the full graph (25). ideal explanation should be both sufficient and necessary. Formally, the sufficient and necessary conditions [25] are formulated as follows, respectively,
argmax Po(c As) ÿ. aEC
argmax P Po Xs. A As) + J. <EC
(2)
where ğ = argmax.ce Po(cX A) in Formula I and 2
3 Methodology
Figure illustrates the overall architecture of V-InfoR, which is composed of two key modules, the robust graph representation extractor and the adaptive explanation generator. As shown in the upper part of Figure 2 the robust graph representation extractor takes the full graph G as input, and two GCN encoders are adopted infer the statistics of G's latent distribution (i.e., mean and standard deviation). The variational node representations, which are sampled from the latent graph distribution, will induce the edge representations. The edge representations are then fed into the adaptive explanation generator which is shown in the lower part of the figure. A multi-layer perceptron

---

projects the edge representations into the probability of each edge. The explanation subgraph Gs is generated on the basis of this probability. Finally, the proposed novel Graph Information Bottleneck (GIB) objective is optimized, which is defined over the full graph prediction ý and the explanation subgraph prediction ýs. Next, we will introduce the two modules detail.
3.1 Robust graph representation extractor
Specifically, we introduce a variational auto-encoder (VAE) 30 to deduce the statistics in the variational distribution of the minorly corrupted graphs. For a set of observed graphs g = {G*
(X* } variational inference assumes that they are generated by latent random process, involving latent continuous random variable z 22 30J. This random process contains two steps. First, a value z" is generated from a prior distribution p(z). Then the graph G is generated from conditional distribution p p(G)z) and observed by us. Variational inference aims at identifying the posterior distribution p(z G), i.e., inverting the distribution of latent variable z from the observed +
k==
graphs However, the true posterior distribution p(z G) unknown. A feasible method is introducing variational distribution q(z; G) to approximate (zz/G) (28). This work assumes that q(z; G) is a Gaussian distribution N ") and increases the similarity between q(z; G) and p(z[G). The similarity measurement is Kullback-Leibler divergence,
KL[g(z; G) Eg(a'; G) log g(=;.)) G) p(z*
We substitute the unknown p(z[G) for p(z, G)) Finally, the objective function of the robust graph representation extractor to be minimized can be formulated as
LVAE - E [log G||z] + KL[g(z; G)llp(z)).
where p(z) is the standard Gaussian distribution N (0. See Appendix A for detailed derivation.
We refer to the latent variable z as a variational representation because contains the indicative information of the observed graphs. We also refer to the model that computes the distribution g(z; G) as an encoder, since given a graph G, produces a distribution over the latent variable z, from which G' could have been generated. Similarly, p( (/zz) (z) is referred to as decoder, since given a code z it produces the probability of the possible graph G.
In our implementation, we employ a 3-layer GCN as the encoder and a simple inner product as the decoder. The first two layers of GCN aim to aggregate and combine the information from the graph. The third layer consists of two separate graph convolution operators to calculate the mean and standard deviation a of qZ; G), respectively. This procedure can be formulated as
H = GCN(H 1-1 AA), k = H =
(5)
= GCN, 4 (H?, A), log GCN, (H² A).
(6)
(7)
The variational inference procedure endows (z; G) vital graph information and is insensitive to minor corruptions. Hence the sampled graph representation which follows q(z; G) is more robust. Next, the robust representation z will be fed into the explanation generator for explanation exploration.
3.2 Adaptive explanation generator
As the second challenge stated before, severe corruptions should be identified as part of the explana- tion, but they are usually irregular in terms of size, connectivity or some other structural properties. The rigorous constraints of the structural regularity adopted in previous works 15 thus not feasible for the severe corruptions. Hence, a new GNN explanation exploration objective function is required to adaptively capture the irregularity of the severe corruptions. Inspired by the
13 25)
Graph Information Bottleneck (GIB) principle [3 32), we propose to introduce an Adaptive Graph Information (AGI) constraint in exploring GNN explanation. On the one hand, the AGI constraint functions as bottleneck to directly restrict the information carried by the explanation Gs. instead
Without ambiguity, represents the random variable and its sampled value (i.e., 2²), simultancously.
5

---

of simply restricting the size or connectivity of Gs. Without any predefined structural regularity constraints, our method can more effectively capture the irregularity of the explanation caused by the severe corruptions. On the other hand, since the information measurement of the explanation Gs can be continuously optimized, the AGI constraint can adaptively cover the discrete rigorous constraints [28]. To this end, we formulate the GNN explanation problem as GIB optimization task to adaptively generate the explanations.
The insight of the GlB-guided optimization is that the explanation Gs of graph G should contain the minimal sufficient components of G [T. GIB principle facilitates Gg to be informative enough about the prediction ğ of G (sufficient)) GIB principle also inhibits Gg from preserving redundant components which is irrelevant for predicting G (minimal). To this aim, the GIB-guided optimization task of Gg is formally defined as follows,
min GIB ÿ: Gs) = MI Gs) + (MI(G,Gs)) GGCG
(8)
where -I( denotes the mutual information. The second term MI(G, Gs) measures the vital graph information carried by the explanation Gs, which functions as the AGI constraint. Nevertheless, the GlB-guided explanation exploration task in Formula (8) cannot be directly extended to a continuous optimization procedure, because both G and G3 have discrete topological information which is difficult to optimize over. We resort to Gilbert random graph theory [33] which argues that an arbitrary graph G can be represented with a binary random variable r to reveal its existence. Additionally, the existence of one edge is conditionally independent of the other edges. rijj means there is an edge (i.j) from v; to Vi otherwise Fúj = O. To sum up, an arbitrary graph G can be represented as
random graph variable, and each edge of G is associated
P(G) Il p(ri)). (8.J)
For the binary variable Tey, a common instantiation is the Bernoulli distribution rty ~ Bern Bern(
where f,y = p(r. = 1) is the probability of edge (i existing in G. However, the Bernoulli distri- butiont cannot be directly optimized. To address this issue, we apply categorical reparametcrization 34 to the Bernoulli variable Tij. The continuous relaxation of rij can be formulated as
Tij Sigmoid log c log(1 c) + Otj) ) c Uniform(0. 1),
(10)
T
0, where we let the latent parameter cuj = log 1-8 T controls the approximation between the relaxed distribution and Bern(f.)). When approaches O, the limitation of Formula (10) is Bern(f.y).
According Formula TO), the Bernoulli parameter O.j is indeed associated with parameter aij- In our implementation, we use a multi-layer perceptron (MLP) to compute a. The MLP takes the variational node representation z as input and concatenates the representations of two nodes 2, 2 as the representation of the corresponding edge (i.j), which can be formulated as
Oig = MLP 2j]),
(11)
where [ 1] is the concatenation operator.
Based on and Formula (10), we obtain the probability matrix Mp whose elements indicate the existence of the corresponding edges. Next, we can sample the explanation Gs based on the probabilities in the matrix Mp as follows,
Gg = (Xs, As = Mp C A).
(12)
So far, we have derived the optimizable representation of Gs in Formula B). However, the optimiza- tion is still challenging since the distributions G() and p(Gs) are intractable.
Fortunately, following the variational approximation proposed in (35). we can derive a tractable variational upper bound of GIB in Formula (8) For the first term -MI( Gs), a parameterized variational approximation Po Gs)) is introduced for P(i)Gs) to get the upper bound as follows,
-M Gs) < - -Ep(Gs.)) [oggs + H()),
(13)
where p Gs) is the GNN model and (()) is an entropy independent of Gs. For the second term, we introduce gGs)) for the marginal distribution P(Gs) 28). and the upper bound is
MI(Gs,, G) < Ep())
(14)

---

where Pa (Gs G) represents the explanation generator and Gs)) represents the prior distribution
sharing similar spirit of assuming standard Gaussian prior 228 See Appendix for the detailed
derivation. Finally, we obtain the variational upper bound of the GIB Formula ( as follows,
LGIB = [) logg (o]Gs) + PC) (CL
(15)
where (Gs) is usually set as
(Gs) = II P (e(y) ~ Bern(T))
(16)
where a constant that decided by the hyper-parameter т.
Note that there are no rigorous constraints imposed in Formula (5). The second term actually functions as an adaptive constraint that inhibits Gg from containing useless information. The risk of ignoring the irregular severe corruptions in the final explanation Gg can also be largely mitigated.
To achieve robust GNN explainer for all the corruption situations, the proposed modules trained jointly by minimizing the following overall objective function,
Ljoint LVAE + LGIB.
(17)
Experiment
4.1 Experimental setup
Following the standard procedure GNN explanation [5] 22.. we conduct two steps in the experi- ments: (1) training base GNN model for prediction, and (2) generating explanations for this base model. For the first step, the base GNN model is trained to simulate the third-party predictor which is independent of the GNN explainers. We take the trained GNN model explanation generation, i.e., input the graph (no matter clean or corrupted) and get the prediction. In the second step, simulate the corruptions by introducing random noise adversarial attack to the graph structures. The random noise represents the corruptions that naturally exist in real-world which affects each graph component without any distinction. The noise ratio controls the percentage of randomly flipped edges. The advesaaiial attack represents the man-made malicious corruptions and the attack budget is the highest percentage of attacked edges.
oracle during the
Metric. For a quantitative explanation evaluation, we report the probability of sufficient Ps, the probability of necessary PN and the FNS scores. See Appendix D.I for the detailed definition.
Dataset. We evaluate the proposed V-InfoR and baseline explanation methods on one synthetic dataset and three real-world datasets. The synthetic dataset is BA-3Motifs introduced in [36. Three real-world datasets are Mutag, Ogbg-molhiv and Ogbg-ppa.
The comparable baseline explainers include gradients- based methods GradCAM 21 and IG [22]. surrogate method PGM-Explainer [37], and perturbation-base methods GNNExplainer 15 PGExplainer [2] and ReFine [36].
Baseline.
The detailed descriptions of datasets, baselines, and base GNN models given in Appendix D The ablation study presented in Appendix We also report the visualized cases of GNN explanation
for qualitative analysis in Appendix F
4.2 Quantitative Evaluation Graphs with Random Noise
We report the result on the graphs with 20% random structural noise corruptions in Table [ Specifi- cally, we randomly select the edges according the noise ratio and flip the selected ones.
The result shows that V-InfoR able to improve the explainer performance on the four datasets, with the overall metric F score improvement at least by 9.19% for the BA-3Motifs dataset and the highest improvement by 29. 29.23% for the Mutag dataset. The V-InfoR improves the performance remarkably for Mutag by 29.23% and Ogbg-molhiv datasets by 15.65%, since the irregularity of the corruptions in chemical molecule structure is more obvious than the other types graphs (motifs in BA-3Motift and biologically associations in Ogbg-ppa), and V-InfoR is able to effectively capture
7

---

Table 1: The comparison of V-InfoR and baselines under random structural noise. We use bold font mark the highest score. The second highest score is marked with underline. The Impro. is defined as [[--InfoR]-[Bes Baseline [Best Baseline].
Dataset
Metric
GradCAM
1G
GNNExplainer
POExplainer
POM-Explainer
ReFine
V-InfoR
Rank
Impro.
0.8725
0.8625
0.8535
0.8510
0.8505
0.8300
0.8820
1
1.09%
BA BA-3Motils
Pv
0.2605
0.2795
0.2410
0.2235
0.2625
0.3021
0:4012
0.4222
0,3758
0,3362
0,3540
0.3989
0,4610
1
9.19%
F3
0,8760
0,8880
0.8916
0.8900
0.8900
Mutug
0.0996
0.1068
0,1080
0.1260
0.1020
0.1260
0.1696
1
34.60%
0.1789
0.1907
0.1920
0.2199
0.1830
0.2207
0.2852
29.23%
F's
0.9230
0.9200
0.8925
0,8390
0.8360
0.9105
0.9386
1.69%
Ogbg-molliv
0.0680
0.0980
0.3020
16.21%
Fi
0.1267
0.0767
0,1701
0,2198
0,1765
0,1834
0.2542
15.65%
Ps
0,4340
0,5820
0.6616
0.6260
0.6192
0.6344
0.6700
1.27%
Oghg-ppa
Py
0.4720
0.4600
0,3480
0.2856
0.3780
0.4406
0.4930
4.45%
F88
0,4522
0.5139
0.4561
0.3922
0.4694
0.5200
0.5680
9.23%
(a) BA-3Motifs
(b) Mutag
InfoR Jours)
Infolt (ours)
0.60
Refine
Rafine
PCM PGMMExxplatner
FClllxxlalner
PGExplainer
PGExolainer
0.55
GNNExplainer IG
GNNExplainer
0.40
IG
GradCAM
GradCAM
Feg scores
0.50
0.45
0.30
0.40
0.20
0.35
0.30
0.05
0.15
0.2
0.25
0.05
0.15
0.2
noise ratio
noise ratio
Figure 3: The comparison of V-InfoR and six baselines under different noise ratios in (a) BA-3Motifs and (b) Mutag.
the irregularity. For the BA-3Motifs and Ogbg-ppa datasets with less obvious irregularity, V-InfoR can still achieve a performance improvement, since the information constraint is general enough to cover the rigorous constraint and thus avoid performance degradation.
One can also see that the raw features based explainers, including GradCAM, IG, GNNExplainer, and PGM-Explainer, perform poorly in small/medium-scal datasets (BA-3Mmotifs, Mutag and Ogbg- molhiv). This may be because the raw features are more easily to be corrupted in small/medium-scale graphs. Since the graph representation is more difficult to learn in the large-scale graph, PGExplainer and ReFine that relie on latent graph representations are unable to well explain large-scale graphs for the Ogbg-pPa ppa dataset. V-InfoR adopts the robust graph representation which is sampled from variational distribution containing common information shared by large amounts of graphs. and thus achieves an overall better performance. Furthermore, one can note that all baseline GNN explainers achieve a high Ps. while the Pn is relatively low. This phenomenon implies that the sufficient condition is casier to satisfy than the necessary condition.
As shown in Figure 3 we also evaluate V-InfoR and baselines under different noise ratios ranging from 0 to 0.30, which reverals the tendency of explainer performance with the increase of noise ratio. In real application scenarios, it is intractable to separate the minor and the severe corruptions, and both may exist simultaneously. Different noise ratios indicate different mixing ratios of the two corruptions. Note that FNs scores with zero noise ratio represent the result on raw graphs without any corruption. It shows that V-InfoR still achieves the best performance when no noise added (noise ratio = O). This reveals that even without any corruption, the robust representation extractor still extracts vital common graph information and the explanation generator adaptively identifies the explanations with regular structural properties.
8

---

Table 2: The comparison of V-InfoR and baselines under GRABNEL attack [88. We use bold font to mark the highest score. The second highest score is marked with underlines.
Ataak budogt
Danaset
Metric
GmdCAM
GNNEEplainer
PGixxplinee
PGMM-Explaiier
ReFine
V-Infok
Rank
Impro.
0.6980
1,36%
MMtods
Ps
0.3625
0.4675
0.4200
0,3700
0,3925
0.3925
0.5450
16.58%
5%
Fys
0.4772
0.5522
0.4809
0.4611
0.1730
0.1950
0.6157
10.30/S
Ps
0.5740
0,600
0,6140
0.6610
0.5830
0.6341
116760
2.27%
Muttag
0.4200
03375
0,3800
0,4003
0,4000
0.4100
0,4588
Fys
0.4851
0.4655
0.4783
0,4980
Ps
0,8720
0.4995
0.8605
0,9020
0.8125
0.8800
0.9185
1,83%
BA- 3Motif
Ps
0.0800
022005
0.2615
0,2815
0.1925
0.2100
0.3331
18. 18%
10%
Pxs
0.1466
013374
0.4011
0,4291
0,3113
0,3391
014890
13.96%
P;
0.5848
0,7320
0,6616
0.6524
0.6392
0.6140
0.7424
0.73%
Mulag
0.4160
0.3344
0,4040
Fxs
0,4852
0.4657
0.4389
0,4904
0.4391
0,4873
0.5427
10.66/5
4.3
Quantitative Evaluation on Graphs with Attack Corruption
The adversarial attack corresponds to the malicious corruption painstakingly customized by the attacker. Here we use the SOTA graph classification attack algorithm GRABNEL [18) whose attack budget is the highest percentage of attacked edges. GRABNEL employs a surrogate model to learn the mapping from attacked graph to its attack loss and optimizes the attacked graph iteratively via an adapted genetic algorithm until successful attack or budget exhaustion. Considering the overhead of executing GRABNEL, we run the attack algorithm only on the BA-3Motif's and Mutag datasets. We report the results with 5% and 10% attack budgets in Table
The result reveals that InfoR achieves an overall superior performance over the other baselines in terms of all metrics. As the attack budget grows from 5% to 10%, though the GNN explanation task becomes harder (all metrics decrease), the performance improvement of V-InfoR becomes more significant than baselines. This shows that V-InfoR can effectively mitigate the negative influence of the structural corruptions. For the Mutag dataset, the performance improvement on the graphs with GRABNEL attack (3396%) is less significant than that on the graphs with random noise (29.23%). This gap can be attributed to the difference between adversarial attack and random noise. Although the adversarial attack corruption is devastating to change the model prediction, they are subtle and introduce as less irregularity as possible to the raw graphs.
4.4 Hyper-paree parameter analysis
We further analyse the effect of three parameters on the model performance, T, 3 and n. T controls the approximation degree of rij distribution to Bernoulli distribution, which ranges in [0.1, 0.5]. B controls the balance between the strength of information restoring (i.e., min MM, Gs)) and the strength of information filtering (i.e.. min MI G)). represents the prior Bernoulli probability, which controls the distribution of (Gs).
[egure4shower the influence of the three syper-parameters V-InfoR for the BA-3Motifs and Mutag datasets. One can roughly archieve the following three conclusions. First, V-InfoR is not so sensitive to B that controls the strength of AGI constraint, which verifies the adaptability of our proposed constraint. Second, suitable value of r is around 0.3, which means the best balance between the continuity of Formula (10) and the approximation degree is achieved when = 0.3. Third, there is no obvious pattern shown Figure 4[) for the choice of क Formula (16). which means that reasonable x may largely depend on the specific dataset.
5 Related Work
Early attempts to explain GNN simply transfer gradients-based methods to graph data, and they regard the gradients of nodes and edges as significance scores [14. Though efficient and intuitive, the explanations based on gradients are unavoidably suffered from gradients saturation [23]. Surrogate
methods [37 23 are also adopted in GNN explanations. Yet limited by simple models that function as surrogates, these approaches are unable to capture topological structure which plays important role in GNN predictions [ 27 Currently, the most concerned GNN explanation methods are intturbation-based By intervening components in the graph, such as deleting (or adding) edges

---

0.50
0.50
0.45
0.45
0.40
0.40
BA Ad-3Mooiis 20% Noise
BA. 4d-3Matlss 20% Noise
0.40
BA 3Notts 10% Attack
BA 3Notts 19% Attack
BA-3Nottt:
Notse
0.35
Notse
BA-JNatis 10% Attack
Kullg 20% Noise
Nutag 10% Attack
0.30
0.30
0.30
03
0.1
0.3
0.4
0.5
9.1
0.2
0.4
0.5 (4)
0.6
0.7 0.8 0.9
131
Figure 4: The influence of parrp-ttttreee 3 in Formula (8) 7 in Formula 16 on V-InfoR.
(10) and in Formula
(or nodes), and monitoring the change of the corresponding prediction, perturbation- based GNN explanation methods [15 13 24 38) optimize the significance scores matrix round after round.
As a classic perturbation-based GNN explanation method, GNNExplainer [15 determines the significant components by maximizing the mutual information between the intervented and the original graphs. It calculates significance scores for both node features and edges, and the components whose scores are below-threshold will be removed. PGExplainer [I3] introduces a parameterized neural network to provide significance scores. It demands training procedure to endow the internal neural network with multi-categorical predicting behavior, and the trained PGExplainer can explain any new graph without retraining. While the previous methods aim to preserve the components that make the prediction invariant, CF-GNNExplainer aims to find the components that will make the prediction change if they are missing (24]. XGNN [39] formulates the GNN explanation problem as a reinforcement learning task. Starting with an empty graph, XGNN gradually adds components until the generated graph belongs to the specified class.
6 Conclusion
In this paper, we propose a robust GNN explainer V-InfoR for the structurally corrupted graphs. V-InfoR employs the variational inference to learn the robust graph representations and generalizes the GNN explanation exploration to a graph information bottleneck (GIB) optimization task without any predefined rigorous constraints. The robust graph representations are insensitive minor corruptions when extract the common information shared by the observed graphs. By introducing an adaptive graph information constraint, V-InfoR can effectively capture both the regularity and irregularity of the explanation subgraphs. Extensive experiments demonstrate its superior performance and the ablation study further illustrates the effectiveness of two proposed modules.
Acknowledgement
This research was funded by the National Science Foundation of China (No. 62172443), Open Project of Xiangjiang Laboratory (22XJ03010, 22XJ03005), the Science and Technology Major Project of Changsha (No. kh2202004), Hunan Provincial Natural Science Foundation of China (No. 20221130053), and the High Performance Computing Center of Central South University.
10

---

References
[1] Andreas Nugaard Holm, Barbara Plank, Dustin Wright, and Isabelle Augenstein. Longitudi- nal citation prediction using temporal graph neural networks. In Proceedings of AAAI, 2022.
[2] Dongsheng Luo, Yuchen Bian, Yaowei Yan, Xiao Liu, Jun Huan, and Xiang Zhang. Local community detection in multiple networks. In Proceedings of KDD, 2020.
[3] Zhoujin Tian, Chaozhuo Li, Zhiqiang Zuo, Zengxuan Wen, Lichao Sun, Xinyue Hu, Wen Zhang, Haizhen Huang. Senzhang Wang, Weiwei Deng, et al. Pass: Personalized advertiser-aware sponsored search. In Proceedings of KDD, 2023.
[4] Feiran Huang. Zefan Wang, Xiao Huang, Yufeng Qian, Zhetao Li, and Hao Chen. Aligning distillation for cold-start item recommendation. In Proceedings of SIGIR, 2023.
[5] Peiyan Zhang, Yuchen Yan, Chaozhuo Li, Senzhang Wang, Xing Xie, Guojie Song, and Sunghun Kim. Continual learning on dynamic graphs via parameter isolation. In Proceedings of SIGIR, 2023.
[6] Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound re- trieval and classification. In Proceedings of ICDM, 2006.
[7] Hao Chen, Zhong Huang, Yue Xu, Zengde Deng, Feiran Huang, Peng He, and Zhoujun Li. Neighbor enhanced graph convolutional networks for node classification and recommendation. Knowledge-Based Systems, 246:108594, 2022.
[8] Jianan Zhao, Meng Qu, Chaozhuo Li, Hao Yan, Qian Liu, Rui Li, Xing Xie, and Jian Tang. Learning on large-scale text-attributed graphs via variational inference. In Proceedings of ICLR, 2022.
[9] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Proceedings of NewrlPS, 2018.
[10] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of ICLR, 2018
[11) Zhongyu Huang, Yingheng Wang, Chaozhuo Li, and Huiguang He. Going deeper into permutation-ssnsitive graph neural networks. In Proceedings of ICMI., pages 9377-9409, 2022.
[12] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. In Proceedings of ICLR, 2014.
[13] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Proceedings of NeurIPS, 2020.
[14] Phillip F. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of CVPR, 2019.
[15) Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnex- plainer: generating explanations for graph neural networks. In Proceedings of NeurlPS, 2019.
[16] Enyan Dai, Charu Aggarwal, and Suhang Wang. Nrgnn: Learning label noise resis- tant graph neural network sparsely and noisily labeled graphs. In Proceedings of KDD, 2021.
[17] Marco Fiorucci, Francesco Pelosin, and Marcello Pelillo. Separating structure from noise in large graphs using the regularity lemma. Pattern Recognition, 98, 2020.
[18] Xingchen Wan, Henry Kenlay, Binxin Ru, Amo Blaas, Michael A. Osborne, and Xiaowen Dong. Adversarial attacks on graph classification via bayesian optimisation. In Proceedings of NeurIPS, 2021.
11

---

[19] Kai Zhou, Tomasz P. Michalak, and Yevgeniy Vorobeychik. Adversarial robustness of similarity- based link prediction. In Proceedings of ICDM, 2019.
[20] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural net- works via meta learning. In Proceedings of ICLR, 2019.
[21] Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: visual explanations from deep networks via gradient- based localization. In Proceedings of ICCV, 2017.
[22] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of ICML., 2017.
[23] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. arXiv, page arXiv:2001.662116 2020.
[24] Ana Lucic, Maartje A. ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf-gnnexplainer: counterfactual explanations for graph neural networks. In Proceedings of AISTATS, 2022.
[25] Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and fac- tual reasoning. In Proceedings of WebConf. 2022.
[26] Amirata Ghorbani, Abubakar Abid, and James Y. Zou. Interpretation of neural networks is frag- ile. In Proceedings of AAAI, 2019.
[27] Daniel Zügner, Amir Akbarnejad. and Stephan Günnemann. Adversarial attacks on neural net- works for graph data. In Proceedings of KDD, 2018.
[28] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic at- tention mechanism. In Proceedings of ICMI., 2022.
[29] David M Blei, Michael I Jordan, and John W Paisley. Variational bayesian inference with stochastic search. Proceedings of ICML, 2012.
[30] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Proceedings of ICLR, 2014.
[31] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. In Proceedings of NeurlPS, 2020.
[32] Junchi Yu, Tingyang Xu, Yu Rong. Yatao Bian, Junzhou Huang, and Ran He. Graph informa- tion bottleneck for subgraph recognition. In Proceedings of ICLR, 2021.
[33] Edgar N Gilbert. Random graphs The Annals of Mathematical Statistics, 30, 1959.
[34] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax In Proceedings of ICLR, 2017.
[35] Alexander A. Alemi, Ben Poole, Ian Fischer, Joshua V. Dillon, Rif A. Saurous, and Kevin Murphy. Fixing a broken clbo. Proceedings of ICML, 2018.
[36] Xiang Wang, Ying-Xin Wu, An Zhang, Xinagnan He, and Tat-Seng Chua. Towards multi- grained explainability for graph neural networks. In Proceedings of NeurlPS, 2021.
[37] Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In Proceedings of NeurIPS, 2020.
[38] Alexandre Duval and Fragkiskos D. Malliaros. Graphsvx: shapley value explana- tions for graph neural networks. In Proceedings of ECML/PKDD, 2021.
[39] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: towards model-level explana- tions of graph neural networks. In Proceedings of KDD, 2020.
12

---

[40] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: datasets for machine learning on graphs. In Proceedings of NeurlPS, 2020.
[41] Ekagra Ranjan, Soumya Sanyal, and Partha Pratim Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of AAAI, 2020.
[42] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neu- ral networks? In Proceedings of ICLR, 2019.
[43] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional works. In Proceedings of ICLR, 2017.
[44] Negin Entezari, Saba A. Al-Sayouri, Amirali Darvishzadeh, and Evangelos E. Papalexakis. All you need low (rank): Defending against adversarial attacks on graphs. In Proceedings of WSDM, 2020.
[45] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of KDD, 2020.
13

---

A Detailed Derivation
First, we give the detailed derivation of Formula 4 To maximize the similarity between the varia- tional distribution and the true posterior distribution, minimize the Kullback-Leibler divergence,
KL G)][p(zi(G))
(24; G) log ((2
p(z: ()
2g
Σ
(24; G) log g G)
+ Σ (zz G) log ((g)
(18)
p(zi, G)
2;
(z4 G) log (
+ log (G).
p(zz G)
2;
Since (G) is independent of z, we get the following derivation,
Σ (z; G) log g2;; G)
p(z. G)
((;;; G)
Σ (z;; G) log
p
(G|z;) p(zz)
(19)
(44;; G)
Σ ((4; G) log
[z4 G) logg((/lz)) (G/z))
p(zi)
<Zz G) [[[((] G) (log (G/z))
Next, we deduce the upper bound of MMI Gs)) in Formula 13
log p(D.Gg
- MM) -Ep(,Gs) log G()
p(9) p(Gs)
=
Ep((.s))
p(0)
log Po( Po(j)Gs)]
log p()]Gs)
= Ep((.ss)
E p()
p(ū)
pp(0)Gs)
(20)
log Po(i)Gss)
= Ep().Gs)
Ep()s KL KLIptilGs)lle((OGGs)))
p(ū)
Po(
<
Ep(j.Gs)
log
p(ū)
Ep(g.Gs) |log (ū]Gs) + (g).
At last, we deduce the upper bound of MI(Gs, G) in Formula (4
log p(Gs, G)
MI(Gs,, G) EP(Gs,0)
p(Gs) (G))
log (Gs
-BP(Gs.O)
p(Gs)
log (Gs G)
log (Gss
-Er(Gs..)
+ E EMGg
g(Gs)
p(Gs)
Pa (Gs G)
p(GGs) log (Gss)
-EP(Gs.0)
log
+ EP(aass)
(21)
y(Gs)
p v(Gs)
Po (Gg G)
-Ep(Gs.
log
EP(()(s)
-KLp(GGs)la((ss]]]
g(Gs)
Pa (Gs
<En())
Pa (G log
(Gs))
-Ep(c)
14

---

B Basic Notations
The basic notations and descriptions are summarized Table 3
Table 3: Basic notations and descriptions in the manuscirpt.
Notation
Description
G,
G
Graph instance, k-th graph instance
Gs
Explanatory subgraph
X, Xs
Node feature matrix
A, As
Adjacency matrix
g
Graph set
GNN prediction model
GNN predicted label
C,C
Specific label, label space
Ús
GNN prediction label of explanatory subgraph Cardinality of set
2,z"
Continuous random variable, k-th sampled value
N(, o²)
Gaussian distribution with mean and standard deviation Bernoulli variable of edge (i,
Taj
Bij
Bernoulli parameter of edge (i,j)
Okj
Latent parameter edge (i.
T
Temperature parameter in Concrete distribution
E
Random noise following (0,
Mp
Probability matrix
C Preliminary Experiment
The results of six SOTA GNN explainers the graphs with minor and severe corruptions is shown in Figure
The dertailed analysis in reported at Section 2.1
0.6
Raw graph
Minor
Severe
FNS scores
0.4
0.3
0.1
GradCAM
IG
GNNExplainer PGExplainer PGM-Explainer
ReFine
Figure 5: The Fys scores of the six SOTA GNN explainers on BA-3Motffs, BA-3Motff with minor corruptions, and BA-3Motifs with severe corruptions, respectively.
15

---

D Experiment supplement
D.1 Metric
We formally define the three metrics for explanation evaluation as follows,
Σ1Φ 0)
Ps
where y - argmax Po(c|Xs,
(22)
19rstt
AEC
Σ 1111 + 1) Grest
PN
where = argmax Pa(c Xs, Ass), AEC
(23)
FNS 2. P. Ps PN Ps + PN
(24)
where Grest the test dataset. Ps measures how faithfully the explanations in simulating the full graph, PN measures the indispensability of explanations, and P' score is the Harmonic mean of Ps and PN. which measures the overall performance of GNN explanation method.
D.2 Dataset
We next briefly introduce the four datasets. The statistics of the four datasets are shown in Table 4 where the "avg nodes/edges" means the average node/edge number of the graphs and the "split" is the dataset splitting of the training, validation, and testing sets.
BA-3Motifs 36 contains 3,000 synthetic graphs. Fach graph adopts Barabasi Albert graphs the base and attaches each base with one of three motifs: house, cycle, and grid. The synthetic graphs are classified into three classes according the type of attached motifs.
Mutag (6) contains 4,337 molecule graphs which are classified into two categories in accordance with their mutagenic effect on a bacterium.
Ogbg-molhiv
40 contains 41,127 molecule graphs which are classified into two categories based on whether a molecule inhibits HIV virus replication or not.
Ogbg-ppa 40 contains 158,100 100 protein-protein association networks in which nodes represent proteins and edges indicate biologically meaningful associations. These association networks cover 1,581 species that belong to 37 taxonomic groups (e.g., mammals and bacterial families). The prediction task is 37-classes classification predict which taxonomic group the network is from.
Table 4: The statistics of the four datasets.
Dataset
avg nodes
avg edges
split
BA-3Motifs
21.92
14.76
2200/400/440
Mutag
30.32
30.77
3337/500/500
Ogbg-molhiv
25.5
27.5
scaffold split (40
Ogbg-ppa
243.4
2266.1
scaffold split 44
D.3 Baseline
We next briefly introduce the baseline explainers used in our experiments, including the gradients- based, the perturbation-batt and the surrogate GNN explanation methods.
is a cenddients-based explanation method. It conducts weighted summation on the last layer representation to obtain the significance scores. The weights are provided by gradient back Back-propagation.
GradCAM 21
IG 22 is a gradients- baaded explanation method. calculates the significance scores by conducting path integral of the input feature gradients.
is perturbation- based explanation method. It perturbs both the topological structure and the node features to calculate the significance scores and search for explanation subgraphs Gs that maximize the mutual information between Gs and full graph prediction
GNNExplainer [5]
16

---

PGExplainer [33 is perturbation- explanation method. It perturbs the topology and employs a parametric neural network to calculate the significance scores, with the same objective function in GNNExplainer.
ReFine 36 is perturbation-ben based explanation method. It applies the pre-training and fine-tuning paradigm to the GNN explanation exploration problem, which promises to offer an all-round inspection of the GNN decision-making process from guatiiigaaularity.
PGM-Explainer 37 is a surrogate explanation method. It trains an interpretable Bayesian network fit the predicted label of the GNN model.
D.4
Base GNN model
The architectures and downstream task performances of the base GNN models which function as the third-party predictors in our experiments are reported in Table 5
Table 5: The architectures and downstream task performances of the base GNN models.
Dataset
Backbone
Layers
Test Acc
BA-3Motifs
LEconv
2
100.00
Mutag
GINConv
42
2
83.63
Ogbg-molhiv
GCNConv
43
5
98.13
Ogbg-ppa
GCNConv
5
60.46
E
Ablation Study
In the ablation study, we create three variants of the full V-InfoR. NA- removes the robust graph information extractor, which explores explanations based on the latent representations from the GNN model to be explained, No-GIB replaces the GIB-based optimization objective function with the traditional sparsity-driven mutual information objective function. No-VAE-GI drops both two proposed modules. We report the performance of full V-InfoR and three variants in Figure g
It shows that the performance drops significantly when removing either the robust graph representation extractor or the adaptive graph information constraint. The performance of No- VAE-GIB is the lowest among the variants. As shown in Figure the performance of No-GIB degrades more significantly than No- VAE in all the cases. This implies that the severe corruptions can more significantly affect the GNN explainers than the minor corruptions, which is consistent with the preliminary result in Section 2. On the one hand, the improvements from No- VAE-GIB to No-GIB and Vo-VAE indicate that both of the two modules are helpful to explain the corrupted graphs. On the other hand, the inferiority of No-GIB and No- VAE to the full V-InfOR further reveals that merely adopting one the two modules is unable to deal with the graphs with two types of structural corruptions.
F
Case Study
We give a visualized case study of explanations provided by V-InfoR and five baselines for the BA-3Motifs. Figure a) shows the three types of motifs: cycle, grid, and house. Figure shows the explanations on a graph with minor corruptions, whose prediction (cycle class) and ground-truth explanation (cycle) are both unchanged. V-InfoR allocates high significance scores (marked by red lines) to the cycle motif (highlighted by circle) correctly and climinates the minor corruption successfully. While the other baseline explainers pay little attention the vital cycle motif and fail to identify it as the explanation. Figure shows the explanations of the severely corrupted graph. The raw prediction and raw ground-truth explanation are both associated with the grid motifs (marked by "before corrupted"), ), which have been broken by the severe corruption. Since the severe corruption has changed the prediction to house class, the explanation should be the house motif (marked by "after corrupted"). However, the five baseline explainers still allocate high significance scores to the component of the grid motif. Only V-InfoR succeeds in identifying the house motif (highlighted by circle) as the explanation.
17

---

V-nffR
0.50
No-VAE
No-GIB
0.45
No-VAE-GIB
FNS scores
0.40
0.35
0.25
0.15
BA-3Motifs 20% Noise
BA-3Motifs 10% Attack
Mutag 20% Noise
Mutag 10% Attack
Figure 6: The ablation study of V-InfoR and three variants.
Gowndsnnh
KChpp
Emparrr
VIM
Grid
(b) Explatations griphe with minor corniption (prodiction unchanged)
Beken camrRal
Houso
Modifs
(c). Explanations commption (pradiction changed)
Figure 7: A case study of explanations provided by V-infoR and five baseline explainers.
G Robustness Evaluation
To directly demonstrate the robustness of our proposed V-InfoR, we introduce robustness evaluation metric [44 (45), which defined as the performance drop after a certain ratio of noise/adversarial attack is added into the graphs. A smaller performance drop means negative value indicates that the model can even perform better under noise/adversarial attack.
robust model and
First, we report the performance drop of V-InfoR and all the baselines in Table with GRABNEL attack ratio set as (2.5%. 5,0%, 7.5%. 10%) The results show that our proposed method can even improve the explanation performance Mutag dataset after adversarial attack, while the performance of all the baselines degrade, which can demonstrate the robustness of our model to GRABNEL attack.
As shown in Table 7 we further report the performance drop of V-InfoR and all the baselines with the random noise ratio set as (0.05, 0.10, 0.15, 0.20, 0.25, 0.30). For the Ogbg-mollhe and Ogbg-ppa. ppa, V-InfoR is more robust to the random noise than all the baselines. The result on Mutag indicates that V-InfoR stands among the top-tier robust methods, since the irregularity chemical molecules is more obvious and significant. This phenomenon implies that our method relies more on capturing the irregularity stemming from graph corruption in order to maintain its robustness. When adding adversarial attack to Mutag graphs, the robustness of our method is more significant, which
18

---

Table 6: The robustness evaluation with GRABNEL attack.
Dataset
Ratio
GradCAM
IG
GNNExplainer
PGExplainer
PGM GiM--xplainer
ReFine
V-InfoR
Rank
2.5%
0.0159
0.0190
0.0068
0.0056
0.0374
0,0092
-0.0054
Mutag
5,0%
0.0038
0.0194
0.0287
-0.0047
0.0245
0,0093
-0.0186
7.5%
0.0052
0.0286
0.0690
+0.0032
0.0496
0.0274
-0.0172
10.0%
0.0027
0.0420
0.0593
0.0035
0.0637
0.0200
-0.0147
2.5%
0.0459
0.0141
0.0085
0.0157
0.0521
0.0504
-0.0047
1
5.0%
0.0668
0.0400
0.0554
0.0509
0.0557
0.0962
-0.0010
Boo3Ms
7.5%
0.2526
0.1926
0.0805
0.0700
0.1811
0.0996
10.0%
0.3947
0,2608
0.1352
0.0859
0.2174
0.2521
0.1277
2
Table 7: The robustness evaluation with random noise.
Dataset
Ratio
GradCAM
IG
GNNExplainer
PGEEsplainer
PGM Mip-aaplainer
ReFine
V-InfoR
Rank
0.05
0.0154
0.0741
0.0297
0.0247
0.0963
0.0318
0.0054
0.0766
0.1469
0.0495
0.0577
0,0591
0.0554
Ogbg-molhhe
0.15
0.0997
0.1914
0.0658
0.0569
0.0940
0.0605
0.0156
0.20
0.1674
0.2132
0.1063
0.0518
0,1298
0,1325
0.0496
0.2149
0.1606
0.1237
0.1237
0.1556
0,1692
0.30
0,2314
0,1775
0.1469
0.1593
0,1397
0,1890
0,0858
0.05
0.0045
0,0153
0.0063
0,0228
0.0537
0,0075
0.0013
1
0.10
0.0506
0.0381
0.0402
0.1014
0.0789
0.0404
0.0172
Ogbg-ppa
0.15
0.0797
0,0403
0.0535
0,1421
0,1331
0.0648
0.0237
0.20
0,1010
0.0639
0.0844
0.2069
0,1049
0.0859
0.0328
0.25
0.1357
0,1053
0,1093
0.2224
0.1591
0.1556
0.0254
0.30
0.1797
0.0958
0.1267
0.2391
0.1656
0,1577
0.0491
0.05
0,0866
0.0849
0,1037
0.0711
0,1131
0,0781
0.0647
0.10
0.1669
0.1738
0.1532
0.1565
0.1986
0,1681
0.1189
0.15
0,2656
0.2430
0.2348
0,2099
0.2647
0,2431
0.2097
Mutag
0,20
0,3218
0.3081
0,3023
0,2800
0.2794
0,2866
0.2403
1
0.25
0.3417
0,3435
0,3343
0.3103
0.3359
0.3242
0.3118
2
0.30
0.3655
0.3775
0.3819
0,3428
0,3690
0.3670
0.3452
2
0.05
-0.0174
0.0074
0.0020
-0,0137
0.0150
0.0231
0.0061
4
0.10
-0,0041
0.0239
0.0019
0.0400
0,0353
0.0238
0.0163
3
BA-3Motifs
0.15
0.0825
0.0801
0.0493
0.0672
0,1043
0.0884
0.0878
0.20
0,1125
0.1772
0.1358
0,1402
0.1874
0,1923
0.1527
0.25
0.1278
0,2112
0.1574
0.1615
0,2100
0,2071
0.1836
0.1407
0.2169
0.1617
0.1879
0.1952
0,2285
0.1951
verifies our deduction again. For BA-3Motifs, the result shows that our proposed model is within the middle range of the robustness evaluation on BA-3Motifs graphs with random noise. This can be attributed to two main possible reasons. Firstly, the introduction of random noise results in lesser degree of irregularity compared to adversarial attack and thus the ability of our method to capture irregularities in corrupted graphs does not bring robustness improvement significantly. In contrast, our method showcases greater robustness than the baseline models when exposed to adversarial attacks on BA-3Motifs graphs. This is due the fact that such attacks will destroy the influential motifs and consequently amplify the level of irregularity. Secondly, the synthetic BA-3Motifs graph itself adheres to a more regular structure than real-world graphs, which adopts a Barabasi- graph as the base and attaches the base with one of three motifs. Consequently, the potential for our method to achieve robustness improvement is further constrained by the synthetic structural topology.
H Limitation
Node Feature Corruptions. Both the robust graph representation extractor and the adaptive explana- tion generator are proposed to mitigate and address the graph structural corruptions. Thus, V-InfoR cannot be directly applied to explain the graphs with node feature corruptions. In the future work, will extend the V-InfoR model to fulfill the robustness on node feature level.
Multi-Task Explanation. The explanation performance of V-InfoR explainer some other graph tasks, such as node classification and link prediction tasks, has not been evaluated. We argue that V-InfoR can be directly used to explain the GNN predictor node classification task, with little modification. However, the V-InfoR explainer for link prediction is non-trivial, since the GNN explanation methods on link prediction is scarce until now.
19


Reviews:
[{"review_id": "dNhw4lk0xO", "reviewer": "Reviewer_Q8Xb", "summary": "This paper proposes a method of explaining GNNs when the input graph is noisy. Existing methods tend to misexplain when noisy graphs are given. The proposed method uses GraphVAE to remove minor noise from the input graph, and a formulation with information bottlenecks allows detecting the presence of severe noise. Experiments confirm the effectiveness of the proposed method using one artificial and three real datasets.", "questions": "- Could you provide an intuitive explanation on why the GIB loss is robust with respect to severe noise?\n- Based on the trends in Figure 3, the proposed method may not be robust to noise, but simply accurate. Could you show that the proposed method is indeed robust to noise?", "limitations": "Potential negative societal impacts do not apply.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- This paper is the first to propose a GNN explanation method in noisy settings. This problem setting seems important in practice.\n- The proposed method consistently outperforms existing methods in the experiments.", "weaknesses": "- I was not convinced that the GIB loss is particularly effective in noisy situations, although it is indeed a plausible explanation. More detailed discussions are required.\n- Figure 3 shows that the proposed method outperforms the existing methods by the same amount in the absence of noise and in the presence of noise, and when noise is added, the accuracy drops at the same rate as the existing methods. The reason the proposed method outperforms the existing method may not be because it is robust to noise, but simply because it is more accurate. High accuracy is great, but given the subject of this work, which focuses on noise, it is not aligned with the main claim.\n- The proposed method is too complex for practical use. I would not want to use this as a practitioner.\n- The experiment only uses GRABNEL as severe noise. Although the authors state that GRABNEL is the attack method of SoTA, there are many aspects of the attack, and defense against only GRABNE is not sufficient. It would be better to use more attack methods, including basic ones such as nettack and metattack.\n- The method section is messy. It would be helpful to summarize a list of parameters to be optimized at the end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: Detailed discussion and intuitive explanation on the robustness of GIB loss.\n\nA1: Thanks for your comments. \n\n1). The severe corruption should be identified as a part of the explanation, since it is the non-ignorable reason that changes the model prediction. However, the irregularity issue of severe corruption makes it difficult for previous methods to identify the severe corruption as part of the explanation. Therefore, we propose the GIB loss to address the irregularity issue and thus make the proposed method robust to severely corrupted graphs. \n\n2). For example, an important motif may be corrupted by adversarial attack and becomes unconnected (removing edges) or overly large (adding edges). In this case, the regularity constraints on the explanation graph size or connectivity that adopted by previous methods are not plausible anymore. Different from them, the GIB loss does not need any regularity constraint and directly restricts the explanation by minimizing the mutual information between the explanation and the raw graph, which is able to identify the influential subgraph under severe corruption.\n>Q2: Could you show that the proposed method is indeed robust to noise?\n\nA2: Thanks for your comments. In Figure 3, as the noise ratio growing, the explanation problem also becomes more difficult and thus the performance of all the explainers (including ours) drops. Our method is able to achieve SOTA performance compared with all the baselines consistently when different amounts of noise are added into the raw graphs. Although the overall performance trend of our method is similar to baselines, its performance improvements over the two strong baselines (i.e., ReFine and IG) differ with different noise ratios.\n\nSpecifically, compared with ReFine, the improvement of our method is 3.00\\% when only 10\\% noise is added but the improvement increases to 6.21\\% when 20\\% noise is added. It implies that compared with ReFine, the performance improvement of our method is more significantly when more noise is added into the graphs (from 10\\% to 20\\%). Compared with IG, the improvement increases from 0.25\\% to 4.31\\% as the noise ratio growing from 15\\% to 25\\%.  To sum up, when the explanation problem grows hard, our method can maintain or even further boost the outperformance, which is able to demonstrate its robustness to graph structural corruptions.\n>Q3: Complexity of the proposed method for practical use.\n\nA3: Thanks for your comment. Actually, our method is easy for practical use, with the open-source code at https://anonymous.4open.science/r/V-InfoR-EF88. Compared with previous GNN explanation methods [1, 2], the proposed method has three main hyperparameters $\\pi$, $\\beta$, and $\\tau$ need to initialize, but these parameters are not hard to tune. We can use bash scripts to modify the three hyperparameters for convenience. Specifically, $\\pi$ in Formula 16 represents the prior Bernoulli probability, $\\beta$ in Formula 8 controls the balance between the two terms of GIB loss, and $\\tau$ in Formula 10 controls the approximation degree to Bernoulli distribution. According to our experimental results, users can focus on tuning $\\pi$ on specific dataset. As the hyper-parameter analysis shows, our method is not sensitive to $\\beta$ and the recommended value of $\\tau$ is 0.3.\n\nThe time complexity of V-InfoR to explain a new graph with $|V|$ nodes and $|E|$ edges is $O(|V|^2+|E|)$, which is similar to the previous works PGExplainer ($O(|V|^2+|E|)$) and GNNExplainer ($O(|V|^2+k*|E|)$). The space complexity is $O(|V|+|E|)$, since we need to restore the node representations.\n\nIf the users want to use our model to explain a new GNN that trained on his own dataset, the following instruction may be helpful. First, initialize the hyperparameters. Second, train our explainer on his own training set and the GNN model functions as an oracle. Third, tune the hyperparameter based on the validation set. Finally, input the new instance to the trained explainer and the corresponding explanation is provided.\n>Q4: Evaluation on more attack methods.\n\nA4: Thanks for your suggestion. We have added the comparison experiment against nettack [3] and metattack [4] on Mutag dataset. The results are listed in the following table.\n|Nettack|5%|10%|\n|:-|:-|:-|\n|GradCAM|0.5035|0.4392|\n|IG|0.5362|0.5064|\n|GNNExplainer|0.5142|0.4315|\n|PGExplainer|0.4977|0.4916|\n|PGM-Explainer|0.5156|0.4831|\n|ReFine|0.5398|0.5120|\n|Ours|**0.5500**(1.89%↑)|**0.5263**(2.79%↑)|\n\n|Metattack|5%|10%|\n|:-|:-|:-|\n|GradCAM|0.4909|0.4459|\n|IG|0.5220|0.4705|\n|GNNExplainer|0.5018|0.4794|\n|PGExplainer|0.4813|0.4841|\n|PGM-Explainer|0.4864|0.4671|\n|ReFine|0.5057|0.4925|\n|Ours|**0.5487**(5.11%↑)|**0.5215**(5.89%↑)|\n\nThe result shows that our method can also consistently outperform the baselines, for the adversarial attack algorithm nettack and metattack.\n>Q5: Summarize a list of parameters to be optimized at the end.\n\nA5: Thanks for your suggestion. We will improve the organization and writing of the method section in the final version if the paper is accepted. Here, we add a summarization of parameters to be optimized, as the table follows.\n|Notation|Description|1st Appearance|\n|:-|:-|:-|\n|$\\beta$|Weighted parameter between the two terms of GIB loss|Eq.8|\n|$\\tau$|Approximation degree to Bernoulli distribution|Eq.10|\n|$\\pi$|Prior Bernoulli probability|Eq.16|\n\n**We also summarize the basic notations and descriptions in our paper, please see Appendix B for more details.**\n\n[1] Parameterized Explainer for Graph Neural Network. NeurIPS 2020.\n\n[2] GNNExplainer: Generating Explanations for Graph Neural Networks. NeurIPS 2019.\n\n[3] Adversarial Attacks on Neural Networks for Graph Data. KDD 2018.\n\n[4] Adversarial Attacks on Graph Neural Networks via Meta Learning. ICLR 2019."}, {"review_id": "XQWdxALCOS", "reviewer": "Reviewer_2tSN", "summary": "This work introduces a robust GNN explainer for structurally-corrupted graphs. The key idea is to exploit the statistics of the graph's latent distributions insensitive to structural perturbations for reconstructing a new graph that will be further leveraged for subgraph (GNN explainer) identification. Through extensive experiments, the proposed approach is shown to be more robust than existing GNN explainers under strong graph structural perturbations.", "questions": "The statistical metrics mean and deviation is considered for extracting the latent distribution. Will other higher-order statistical metrics help in this step?\n", "limitations": "There should be a section discussing the runtime/space complexity of the proposed method. Additional runtime results should also be reported for graphs with different sizes.\n", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The idea of using GNNs to extract the graph's latent distributions for graph reconstruction is interesting and effective.\n2) The proposed adaptive explanation generator is designed based on a theoretically-sound variational upper bound, which also shows its effectiveness in extensive experimental results.", "weaknesses": "1) There should be more discussions of existing works that aim to reconstruct graphs based on properties insensitive to structural perturbations. For example, the graph spectral properties (e.g. the first few Laplacian eigenvalues/eigenvectors) are not sensitive to adversarial attacks and thus can be leveraged for graph reconstruction (see a recent work \"GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks\" published in LoG'22).\n2) There should be a section discussing the algorithm runtime/space complexity of the proposed framework. It is not clear if this method can be efficiently applied to large graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: There should be more discussions of existing works that aim to reconstruct graphs based on properties insensitive to structural perturbations. For example, the graph spectral properties (e.g., the first few Laplacian eigenvalues/eigenvectors) are not sensitive to adversarial attacks and thus can be leveraged for graph reconstruction (see a recent work \"GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks\" published in LoG'22).\n\nA1: Thanks for your suggestion. We will add the suggested reference and provide more discussions on the graph reconstruction methods. When explaining the structurally corrupted graphs, it is promising to defense the structural perturbations based on the graph spectral properties in GARNET [1]. As we state in line 46-56 of the paper, the structural corruption includes both the minor corruption and severe corruption, based on whether the prediction of downstream task is changed or not. For the minor corruption, introducing graph reconstruction methods as a noise filter may also be a reasonable solution, since the minor corruption does not affect the final prediction and the GNN explainer can identify the corresponding explanation. But, for the severe corruption, the final prediction has been changed. If the GNN explainer searches for the explanation based on the reconstructed graph, it cannot be guaranteed that the explanation is corresponding to the model prediction, since the reconstructed graph may have eliminated the severe corruption and recorrected the prediction.\n>Q2: There should be a section discussing the algorithm runtime/space complexity of the proposed framework. It is not clear if this method can be efficiently applied to large graphs. Additional runtime results should also be reported for graphs with different sizes.\n\nA2: Thanks for your comments. Our method can be efficiently applied to large graph. We will add a section to analyze the time/space complexity of the proposed model V-InfoR. The time complexity of V-InfoR to explain a new graph with $|V|$ nodes and $|E|$ edges is $O(|V|^2+|E|)$, which is similar to the previous works PGExplainer [2] ($O(|V|^2+|E|)$) and GNNExplainer [3] ($O(|V|^2+k*|E|)$). The space complexity is $O(|V|+|E|)$, since we need to restore the node representations. The average runtime on a single graph with a single NVIDIA GeForce 3060 GPU (6GB) is reported in the following table.\n|Dataset|Avg. #Nodes|Avg. #Edges|Avg. Runtime(ms)|\n|:-|:-|:-|:-|\n|BA-3Motifs|21.92|14.76|20.81|\n|Mutag|30.32|30.77|38.76|\n|Ogbg-molhiv|25.50|27.50|29.42|\n|Ogbg-ppa|243.40|2266.10|2584.60|\n\n>Q3: The statistical metrics mean and deviation is considered for extracting the latent distribution. Will other higher-order statistical metrics help in this step?\n\nA3: Thanks for your comment. When it comes to variational auto-encoder, we usually assume that the variational distribution belongs to Gaussian distribution. A Gaussian distribution can be determined by the mean $\\mu$ and variation $\\sigma^2$ and thus generally the mean and variation (deviation) are enough to deduce the latent distribution [4]. However, in some complex situation, Gaussian distribution may not be a reasonable assumption and then introduce some high-order statistics could achieve better performance. We will investigate the effect of the higher-order statistics in the future work.\n\n[1] Chenhui Deng, Xiuyu Li, Zhuo Feng, Zhiru Zhang. GARNET: Reduced-Rank Topology Learning for Robust and Scalable Graph Neural Networks. LoG 2022.\n\n[2] Parameterized Explainer for Graph Neural Network. NeurIPS 2020.\n\n[3] GNNExplainer: Generating Explanations for Graph Neural Networks. NeurIPS 2019.\n\n[4] Thomas N. Kipf, Max Welling. Variational Graph Auto-Encoders. NIPS 2016."}, {"review_id": "dXvdSteTDB", "reviewer": "Reviewer_cjXo", "summary": "This work aims at structurally corrupted graphs for a more robust explanation. It proposes a method called V-InFoR, which includes two components for minor and severe corruptions respectively. Experiments on synthetic and real data with different corruption ratios verify the effectiveness of the proposal.", "questions": "1. Major\n    1. In the ablation studies, GIB is more effective in both minor and major corruption cases - any further explanation or intuition behind this phenomenon is welcome.\n    2. For the results in Figure 3, further ablation studies of VAE and GIB are recommended.\n2. Minor\n    1. In Figure 2, the VAE loss should also be noted.\n\nIf I have missed anything, please let me know.", "limitations": "Limitations are included in the appendix. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The motivation is clearly presented by a pre-experiment. And the overall structure of the paper is easy to follow.\n2. The two components (VAE and GIB) of the proposed method are not trivial, especially the distribution representation may not be easy to train.\n3. The experimental results are convincing, especially those under adversarial attacks.", "weaknesses": "1. The authors provide several simulated examples of corruption, which is good. However, they could present more practical examples of corruption in the real world, just at the data level, which could be better for readers to understand the need for robustness.\n2. The motivation for the introduction of GIB beyond VAE should be further clarified (lines 180-183), as there is no precise dividing line for minor and severe corruption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: The authors provide several simulated examples of corruption, which is good. However, they could present more practical examples of corruption in the real world, just at the data level, which could be better for readers to understand the need for robustness.\n\nA1: Thanks for your suggestion. We will add a few practical examples of corruptions in the final version.\n1). On one hand, the raw data usually contain some noise naturally in real applications, and thus a robust model that considers the effect of such random noise is needed. In this case, our method can get improvement even when no extra noise is manually added. As shown in Fig 3, our method improves the model performance compared with baselines on the raw graphs without any noise added (noise ratio is 0%).\n2). On the other hand, the adversaries are common and the fake data can be easily injected into the raw data [1, 2], such as recommender systems, knowledge graphs, and social networks. For example, the fraudsters frequently manipulate online reviews and product websites and the spammers add fake connections to social networks.\n>Q2: The motivation for the introduction of GIB beyond VAE should be further clarified (lines 180-183), as there is no precise dividing line for minor and severe corruption.\n\nA2: Thanks for your comment. The fact is that the minor and severe corruptions are hard to separate and tend to exist simultaneously. Therefore, we need to combine VAE and GIB together to comprehensively mitigate both the minor and severe corruptions. As the ablation study shows, the explanation performance degrades when removing the GIB module. Moreover, we notice that the performance degradation on Mutag dataset increases from 1.13\\% to 5.42\\% as the noise ratio growing from 5\\% to 15\\%, which demonstrates the necessity of GIB, especially when explaining severely corrupted graphs.\n>Q3: In the ablation studies, GIB is more effective in both minor and major corruption cases - any further explanation or intuition behind this phenomenon is welcome.\n\nA3: Thanks for your suggestion. Actually, the “Noise” and “Attack” situation in the ablation studies may not totally correspond to the “minor” and “major” corruption, respectively. In real application scenarios, it is intractable to separate the minor and the severe corruptions, and both may exist simultaneously. Therefore, the effectiveness of GIB may imply that the severe corruptions can more significantly affect the GNN explainers than the minor corruptions. Furthermore, the information constraint term MI$(G,G_S)$ in GIB also functions as the sparsity regularization. This additional function may improve the explainer performance too.\n>Q4: For the results in Figure 3, further ablation studies of VAE and GIB are recommended.\n\nA4: Thanks for your suggestion. We will add more ablation studies in Appendix G of the final version. Specifically, we report the performance of the three variants (i.e., No-VAE, No-GIB, and No-VAE-GIB) under different noise ratios. The Fns-score on BA-3Motifs is listed in the following table.\n|Noise Ratio|V-InfoR|No-VAE|No-GIB|No-VAE-GIB|\n|:-|:-|:-|:-|:-|\n|0|0.6167|0.6003|0.5994|0.5956|\n|0.05|0.6076|0.5891|0.5703|0.5599|\n|0.1|0.5974|0.5530|0.5229|0.5164|\n|0.15|0.5239|0.5115|0.4827|0.4625|\n|0.2|0.4610|0.4387|0.4136|0.4080|\n|0.25|0.4310|0.4139|0.3894|0.3826|\n|0.3|0.4154|0.3921|0.3717|0.3672|\n\nThe Fns-score on Mutag is listed in the following table.\n|Noise Ratio|V-InfoR|No-VAE|No-GIB|No-VAE-GIB|\n|:-|:-|:-|:-|:-|\n|0|0.5280|0.5107|0.5112|0.5064|\n|0.05|0.4608|0.4529|0.4495|0.4423|\n|0.1|0.4066|0.3833|0.3746|0.3711|\n|0.15|0.3158|0.2848|0.2616|0.2528|\n|0.2|0.2852|0.2586|0.2415|0.2341|\n|0.25|0.2173|0.1969|0.1774|0.1632|\n|0.3|0.1803|0.1627|0.1439|0.1408|\n\nThe result shows that the performance of No-GIB degrades more significantly than No-VAE in all the cases. This implies that the severe corruption affects the GNN explanation more significantly than the minor corruption. Moreover, the inferiority of No-GIB and No-VAE to the full V-InfoR further reveals that merely adopting one of the two modules is unable to deal with the graphs with two types of structural corruptions.\n>Q5: In Figure 2, the VAE loss should also be noted.\n\nA5: Thanks for your suggestion. In the final version, we will note the VAE loss in Figure 2.\n\n[1] Adversarial Attacks on Neural Networks for Graph Data. KDD 2018.\n\n[2] NetFense: Adversarial Defenses Against Privacy Attacks on Neural Networks for Graph Data. TKDE 2023."}, {"review_id": "RIDc7SXr0a", "reviewer": "Reviewer_kswM", "summary": "The study focuses on the significance of explaining Graph Neural Networks (GNN) models for the development of reliable and trustworthy machine learning systems. Unlike previous research that assumes clean input graphs, this paper introduces a novel approach to constructing a more robust GNN explainer capable of handling graphs with structural corruptions such as noisy and adversarial edges. This is a crucial consideration as real-world graphs are often imperfect. The authors specifically address two scenarios: minor corruptions that do not alter the GNN's prediction results, and severe corruptions that lead to changes in prediction outcomes. To tackle these scenarios, the proposed model, V-InfoR, consists of two modules. The robust graph representation extractor module aims to handle the first scenario, while the graph information bottleneck module focuses on addressing the second scenario. V-InfoR incorporating the two modules can explain well on both the corrupted graphs and the raw graphs. The effectiveness of the proposal is validated through evaluations conducted on four datasets. \n", "questions": "Some questions are presented in the ‘Weaknesses’. Moreover, do the two terms in the total loss (Eq. (17)), i.e., LVAE and LGIB, need to be combined with a weighted hyper-parameter?", "limitations": "The authors have listed and discussed some potential limitations in the supplementary, including the node feature corruptions and the robust explanation on tasks besides graph classification. I wonder about the explanation efficiency of the proposed model.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "S1: This paper explores the concept of graph structure corruptions at two different levels and highlights how both levels can negatively impact the quality of GNN explanations. This novel and intriguing study addresses a new and practically significant problem, considering that real-world graphs are susceptible to corruption and attacks.\nS2: The use of variational inference to mitigate the effects of minor corruptions is a logical and robust approach. Additionally, the innovative GIB-based optimization framework effectively tackles the challenge of irregular severe corruptions. The utilization of the graph information bottleneck within the adaptive explanation generator appears to offer a more comprehensive and resilient model compared to existing methods. The integration of these two components allows for simultaneous handling of both types of structure corruptions. Overall, I think the proposed model is well-motivated and demonstrates technical solidity.\nS3: The organization and writing of this paper are easy to follow. The motivation behind the research is also clearly conveyed by providing a preliminary experiment.\nS4: The performance improvement of the proposed model, namely V-InfoR, is holistically verified on four datasets, including both the synthetic and real-world graphs.\n", "weaknesses": "W1: It is a little confusing that the primary results in experiment are presented and discussed in relation to random noise and adversarial attacks (referred to as adversarial edges in the main text). However, the authors establish definitions for both minor corruptions and severe corruptions. The authors may want to provide a clearer illustration of the relation and distinction between the two categories of corruptions (i.e., in experiment and in definition).\nW2: I find the result presented in Figure 7 somewhat unclear, particularly regarding Figure 7c, where the performance of V-InfoR appears to improve after the graph is corrupted. This raises the question of why V-InfoR demonstrates better performance under such circumstances.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: It is a little confusing that the primary results in experiment are presented and discussed in relation to random noise and adversarial attacks (referred to as adversarial edges in the main text). However, the authors establish definitions for both minor corruptions and severe corruptions. The authors may want to provide a clearer illustration of the relation and distinction between the two categories of corruptions (i.e., in experiment and in definition).\n\nA1: Thanks for your suggestion. We will add more explanation about the relation and distinction between the two categories of corruptions in final version. In the preliminary experiment, we want to investigate the effect of minor and severe corruptions, respectively. Hence, we manually select the graph whose prediction is unchanged to simulate the minor corruption, as well as the simulation of severe corruption. However, in real-world, it is intractable to separate the minor and the severe corruptions, and both may exist simultaneously. Therefore, we use random noise and adversarial attack as structural corruptions which represent the corruption naturally exists in real-world and the man-made malicious corruption, respectively.\n\n>Q2: I find the result presented in Figure 7 somewhat unclear, particularly regarding Figure 7c, where the performance of V-InfoR appears to improve after the graph is corrupted. This raises the question of why V-InfoR demonstrates better performance under such circumstances.\n\nA2: Thanks for your comments. When explaining severely corrupted graphs, the explainer must identify the subgraph which conforms to the after-corrupted-prediction. In Figure 7c, the severe corruption has changed the prediction to house class. Therefore, the explanation should be the \"house\" motif marked by \"after corrupted\". Only V-InfoR succeeds in identifying the \"house\" motif explanation.\n\n>Q3: Do the two terms in the total loss (Eq. (17)), i.e., LVAE and LGIB, need to be combined with a weighted hyper-parameter?\n\nA3: Thanks for your comment. According to our experimental results, L-VAE and L-GIB are on the same order of magnitude. In practical use, it is also easy to introduce a weighted hyper-parameter, if the training process is unstable and hard to converge."}, {"review_id": "X5lUAOYI18", "reviewer": "Reviewer_SeJw", "summary": "This paper proposed a robust GNN explaination method for structurally corrupted graphs. The novelty of the paper is that it considers the noise and corruptions in the graph, and verified that the corruptions can significantly affect the performance of existing GNN explainers. To address this issue, the authors proposed to use variational inference to sample a more robust graph representation and reduce the negative effect of the noise. The authors also formulate the problem as a graph information bottleneck optimization problem. Although straightforward, GIB method can effectively generate the explaination subgraph without any structural constrains, and thus is more general. The evaluations are extensively studied over one synthetic and three real graph datasets. By comparison with current SOTA models, the results show the significant performance improvement of the model in both minor and server corruptions.\nOverall, the paper is very well written and has clear technique contributions. The evaluation is also convincing.\n", "questions": "(1) Does the model still work well for the graphs without much structural noise? A comparison between the proposed model and existing models on clean graphs would make the result more convincing.\n(2) Although the authors focus on the structurally corrupted graphs, I still want to see whether the proposed method (like variational node representation) can be easily generalized to the attribute noise and corruptions? \n", "limitations": "Limitations are well discussed in the appendix, and I have no suggestions for improvement.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "(1) The paper studied the GNN explanation problem when the graphs are noisy or corrupted, which is novel and practically important. In real application scenarios, the graphs may contain noise and not reliable, thus it is important to design a more robust explaination model for GNNs.\n(2) The paper considers both mirror and severe corruptions on graph structures. To address the mirror corruptions, a variational inference based robust graph information extractor is proposed. An adaptive graph information constrained is also introduced into the GIB module. The proposed GIB optimization methods can capture both the regularity and irregularity of the corrupted graphs. \n(3) The paper is well written and easy to read. A theoretical analysis is also provided to derive the variational bound of the objective function.\n(4) The experiment is extensively conducted over both real and synthetic datasets. By comparison with current SOTA methods, the performance improvement of V-InfoR is significant.\n", "weaknesses": "(1) It seems that the robust graph representation extractor can effective filter minor noise. However, it the input graphs do not have minor noise, is this step still required? I wonder if the graph is reliable and do not contain much noise, whether the proposed method still works.\n(2) The paper only considers the structural corruptions on the graphs. The graphs may also contain noise in the attributes. Can the methods be generalized to graphs with attributes corruptions? It would be better that the authors can further discuss how to deal with the attributes noise issue.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Q1: It seems that the robust graph representation extractor can effectively filter minor noise. However, if the input graphs do not have minor noise, is this step still required? I wonder if the graph is reliable and do not contain much noise, whether the proposed method still works. Does the model still work well for the graphs without much structural noise? A comparison between the proposed model and existing models on clean graphs would make the result more convincing.\n\nA1: Thanks for your comments. Actually, in Figure 3, the performance with zero noise-ratio corresponds to that on clean graphs. Here, we summarize the result in the following table.\n|Model|BA-3Motifs|Mutag|\n|:-|:-|:-|\n|GradCAM|0.5440|0.4889|\n|IG|0.5982|0.5077|\n|GNNExplainer|0.5363|0.4982|\n|PGExplainer|0.5150|0.4939|\n|PGM-Explainer|0.5287|0.5028|\n|ReFine|0.5912|0.5037|\n|Ours|**0.6157**(2.93%↑)|**0.5281**(4.02%↑)|\n\nThe proposed method still achieves the best or top-tier performance when there are no corruptions. This reveals that even without any corruption, the robust representation extractor still extracts vital common graph information and the explanation generator adaptively identifies the explanations with regular structural properties.\n>Q2: The paper only considers the structural corruptions on the graphs. The graphs may also contain noise in the attributes. Can the methods be generalized to graphs with attributes corruptions? It would be better that the authors can further discuss how to deal with the attributes noise issue. \nAlthough the authors focus on the structurally corrupted graphs, I still want to see whether the proposed method (like variational node representation) can be easily generalized to the attribute noise and corruptions?\n\nA2: Thanks for your suggestion. The proposed method is able to generalize to the graphs with node attributes corruption and we may need to introduce some modules that is specially designed for the representation learning on node attributes. For example, we could filter the attribute noise and repair the node attribute based on the homophily assumption on node attributes. We leave the robust GNN explainer on node attributes corruption to the future work."}]

Author rebuttal:
Thank all reviewers again for your positive opinion of our paper and your valuable comments that have allowed us to improve the manuscript.

We have made point-to-point response to the comments of each reviewer.

Meta-review: The paper presents a novel method, V-InFoR, to explain Graph Neural Networks (GNNs) in the presence of structural corruptions in graphs. The method uses variational inference and an information bottleneck optimization problem to handle both minor and severe graph corruptions. While reviewers generally appreciate the paper's contributions and experimental validations, concerns were raised about the method's necessity and robustness which the authors addressed in their rebuttals. I highly encourage the authors to summarize and report all these new results in the next revision.
Decision: Accept (poster)