On Regularization for Explaining Graph Neural Networks: An Information Theory Perspective
Authors: Junfeng Fang
Wei Liu
An Zhang
Xiang Wang
Xiangnan He
Kun Wang
Tat-Seng Chua
Venue: Submitted to ICLR 2023 (2023)
Keywords: Explainability
Graph Neural Networks
Regularization

Abstract: This work studies the explainability of graph neural networks (GNNs), which is important for the credibility of GNNs in practical usage. Existing work mostly follows the two-phase paradigm to interpret a prediction: feature attribution and selection. However, another important component --- regularization, which is crucial to facilitate the above paradigm --- has been seldom studied. In this work, we explore the role of regularization in GNNs explainability from the perspective of information theory. Our main findings are: 1) regularization is essentially pursuing the balance between two phases, 2) its optimal coefficient is proportional to the sparsity of explanations, 3) existing methods imply an implicit regularization effect of stochastic mechanism, and 4) its contradictory effects on two phases are responsible for the out-of-distribution (OOD) issue in post-hoc explainability. Based on these findings, we propose two common optimization methods, which can bolster the performance of the current explanation methods via sparsity-adaptive and OOD-resistant regularization schemes. Extensive empirical studies validate our findings and proposed methods. Code is available at  https://anonymous.4open.science/r/Rethink_Reg-07F0.


Under review as a conference paper at ICLR 2023
ON REGULARIZATION FOR EXPLAINING GRAPH NEURAL NETWORKS: AN INFORMATION THEORY PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
This work studies the explainability of graph neural networks (GNNs), which is important for the credibility of GNNs in practical usage. Existing work mostly follows the two-phase paradigm to interpret a prediction: feature altribution and selection. However, another important component regularization, which is cru- cial to facilitate the above paradigm has been seldom studied. In this work. we explore the role of regularization in GNNs explainability from the perspec- tive of information theory. Our main findings are: 1) regularization is essen- tially pursuing the balance between two phases, 2) its optimal coefficient is pro- portional to the sparsity of explanations, 3) existing methods imply an implicit regularization effect of stochastic mechanism, and 4) its contradictory effects on two phases are responsible for the out-of-distribution (OOD) issue in post-hoc explainability. Based on these findings, we propose two common optimization methods, which can bolster the performance of the current explanation methods via sparsity-adaptive and OOD-resistant regularization schemes. Extensive em- pirical studies validate our findings and proposed methods. Code is available at https: //wp:////nnnnoooo////// 4open. science/ /tttt//////etittteeeee Rea--nkk_eee70000 07F0.
INTRODUCTION
Graph Neural Networks (GNNs) (Dwivedi et al., 2020; Wu et al., 2019) have achieved remarkable progress on various graph-related tasks (Mahmud et al., 2021; Zhao al., 2021; Guo & Wang, 2021). However, GNNs usually work as a black box, making the decision-making process obscure and hard to interpret (Ribeiro et al., 2016). Hence, answering the question: "What knowledge does the GNN use to make certain prediction?" is becoming crucial. To solve this question, most prior studies (Yu et al., 2021; Miao et al., 2022) realize post-hoc explainability by extracting the informative yet sparse subgraphs explanations, following the principle of graph information bottleneck (GIB) (Wu et al., 2020). The common paradigm of these explainers can be summarized the relay race of feature attribution and selection. Specifically, feature attribution distributes the prediction to the imput features and traces their importance, and feature selection sequentially fills features into the explanatory subgraph according to the importance rank, where regularization terms are introduced to constrain subgraph properties like size and connectivity.
However, existing explainers allocate little attention to the role of regularization in them, but is the focus of our work. On the one hand, without digging deeper into regularization theoretically, we hardly acquire a plain picture of how regularization specifically affects the process of feature attribution and selection. Furthermore, some regularization in existing explainers lacks concrete theoretical support and is seemingly not more than an empirical trick. For example, GNNExplainer (Ying et al., 2019) leverages the 4 norm to constrain the magnitude of masks and selects the edge with larger importance (i.e., larger mask). The key here is not the absolute magnitude the mask (i.e., l norm), but rather the relative magnitude between the masks. Thus, argue that the necessity of 1 norm needs more theoretical support.
In sight of this, endeavor to rethink the role of regularization in GNNs explainability from the perspective of information theory. Before starting, we first reshape the principle of GIB as GIBE (i.e., new GIB form tailored for GNNs Explainability) in the language of feature attribution and

---

Under review as a conference paper at ICLR 2023
selection. Specifically, GIBE unifies the current explanation methods via formulating the optimiza- tion objective of these two phases. It further explores the roles regularization in two phases respectively. Guided by these explorations, reveal the essence of regularization and propose four intriguing propositions in terms of it. We believe a better theory of regularization is fundamental:
The essence of regularization: Regularization in GNNs explainability is essentially the tradeoff scheme to pursue the balance between the phases of feature attribution and selection (Section 3.2).
On Sparsity: The optimal coefficients of regularization are proportional to the sparsity of the explanation, that is, high sparsity should require large regularization and vice versa (Section 4.1). On stochastic mechanism: Existing methods imply an implicit regularization effect of stochastic mechanism, which endows GNNs explainability with better compressibility (Section 4.2).
On OOD issue: The contradictory effects of regularization on two phases are responsible for the OOD issue in the post-hoc explainability (Section 4.3).
Furthermore, based on these findings, we propose two common optimization methods, which can bolster the performance of current explainers via sparsity-adaptiy and OOD-resistant regularization schemes. Extensive empirical studies validate our findings and proposed methods in Section 5.
2 PRELIMINARY AND RELATED WORK
GNNs explainability. While GNNs have achieved remarkable success in node classification (Zhou et al., 2019; Sankar et al., 2019), graph classification (Zhang et al., 2018; Chen et al., 2019), and link prediction (Ying al., 2018; You al., 2020) tasks, in this work, focus on the scenario of interpreting graph classification task comprising the data distribution 'D and the classifier f'- Specifically, the input graph G (X, A) ) is independent and identically distributed (IID) from D, where X is the features of all nodes and A is the adjacency matrix. Following Miao et al. (2022), we assume that there exists a subgraph G" such that the label Y for graph G is determined by Y = f("") + é for some as noise independent of G, where f is an invertible function projecting the set of subgraphs to the label space. Guided by the target of searching 9", current explainers mainly leverage feature attribution and selection to extract the subgraph (Wang et al., 2021).
Feature attribution. Current explainers mainly perform feature attribution by leveraging:
Gradient- like signals w.z.t the graph structure (Baldassarre & Azizpour, 2019; Pope et al., 2019). For example, SA (Baldassarre & Azizpour, 2019) directly calculates the gradients of GNN's loss w.t.t adjacency matrix as the importance scores of edges;
Attention scores of structural features (Luo et al., 2020; Miao et al., 2022). For example, GSAT (in its post-hoc working mode) (Miao et al., 2022) trains parameterized predictor to generate the stochastic attention for each edge as their importance;
Mask scores of structural features (Ying et al., 2019; Wang et al., 2021). For example, GNNEx- plainer (Ying et al., 2019) adds soft masks to the input features and trains them by maximizing the mutual information between the masked outcome and target prediction;
Prediction changes on structure perturbations (Yuan et al., 2021; Lin et al., 2021). For example, PGMExplainer ( Vu & Thai, 2020) collects the prediction change the random node perturbations and learns a Bayesian network from these observations.
Feature selection. With attribution scores of features, input features are sequentially filled into the set of salient features to generate the explanatory subgraph according to their importance rank. Many regularization terms are introduced to guide this process. For example, sparsity constraints (Ying et al., 2019; Schlichtkrull et al., 2021) typically leverage the I norm to guarantee that the selected subgraph remains within prescribed size; connective constraints (Luo et al., 2020; Wang et al., 2021) give more selective probabilities to the edges connecting with the part selected already; more recently, information bottleneck constraints (Miao et al., 2022) are proposed to squeeze the mutual information between the input graph and the selected subgraph.
RETHINKING THE ROLE OF REGULARIZATION
In this section, we rethink the role of regularization in GNNs explainers. We start with a new form of graph information bottleneck tailored for explainability and the formulation of the feature attribution and selection (Section 3.1). Guided by the above theory, we analyze the effect of regularization in two phases, respectively (Section 3.2).
2

---

Under review as a conference paper at ICLR 2023
Target
map to
O
map to
Ss
Instantiation
Feature Attribution
Feature Selection
approximate
binarize
Scheme
HC ( M),1)
GG O M:Y) GOM
O M'
gap1
gap2
Regularization
gapl- -
A
loose
Constraint orientation of M
tight
A
gap2
Figure 1: The role of regularization in the phases of feature attribution and feature selection.
3.1 GRAPH INFORMATION BOTTLENECK FOR EXPLAINABILITY
The principle of GIB is widely leveraged to guide the subgraph generation by prevailing GNNs explainers (Wu et al., 2020; Miao et al., 2022). The general formulation of GIB shown as follows:
Definition (GIB (Yu et al., 2021)) Given an input graph G and its label Y, GIB seeks for a maximally informative yet sparse subgraph by optimizing the following objective:
arg max (G,: BI (G.; s.t. 9s Gsub(9).
9.
where (g) indicates the set of all subgraphs of G and 3 is the Lagrangian multiplier.
To instantiate the objective of GIB, considering the discreteness and non-differentiability of sub- graph G.. existing explanation methods typically take G & M as the proxy of G.. where M the explanatory mask sharing the same size with A. Concretely, for mask-based methods, M is the trainable masks; for attention-ben based methods, M is the dualizztion the attention matrix; and for perturbation-bast methods, M is the matrix recording corresponding features are perturbed not.
In sight of this, we first replace G3 in Equation 1 with G @ M. Moreover, according to the invariance of the mutual information (MI) to invertible transformation, rewrite Equation to introduce the new GIB form tailored for GNNs explainability. Detailed derivation is provided in Appendix A.
Definition (GIBE) Given an input graph G and its label Y, GIBE seeks for the explanatory mask M to generale the explanation G @ M by optimizing the following objective:
arg max M
(g M +o (G C M: I M:9)..
(2)
altribution
feature selection
where is the tradeoff parameter which equals to 3/(1 -3) 3 in Definition 1.
Theoretically, employing Data Processing Inequality (DPI) (Cover & Thomas, 2006) along the Markov chain, G* + G - Y, the optimal solution M of Equation 2 can be proved to be equal to the adjacency matrix of g*. We provide detailed derivation in Appendix A.2.
Note that GIBE is the first attempt to in-depth combine the principle of GIB and the common paradigm of the post-hoe explainability (i.e., feature attribution and selection). Specifically, the first term of Equation is the optimization objective of feature attribution, which maps the informa- tion of feature importance in ς to mask, G + G c M; and the second term is the objective of feature selection, which maps the information the mask to subgraph, C M + G.. In conclusion, GIBE endows the GIB with better ability to directly guide the construction of the explanation methods.
3.2 REGULARIZATION IN TWO PHASES
Regularization in feature attribution. Directly calculating the training objective of feature at- tribution, I (g M; Y) is tough since the latent distribution F O M, Y) is notoriously in- tractable. Hence, existing explainers typically introduce the parameterized variational approxima- tion Pe (Y M) for (Y 5 @ M) according to:
(G O M; Y)
E [log Po (Y | M)) + H(Y)
(3)
+ E IKL (PP (Y ( Fg (Y G o M))]

---

Under review as a conference paper at ICLR 2023
Detailed derivation is provided in Appendix A.3. Treating classifier f as the proxy function of Po, the first term of Equation 3 is specified as the cross ertsoyy between Y and f In this case, since the second term H(Y) is constant, the gap between I (g @ M; Y) and above cross-entropy, shown as gap/ in Figure 1, solely depends on the third term of Equation 3. Note that this term is also the Kullback-Leibler (KI.) Divergence between IP (Y g o M) and ( ④ M).
To bridge this gap and maximize the effectiveness of feature attribution, regularization should play a o M) to f'. Since f' is trained for data distribution P(g, Y), this role transfers to constrain G O M to G. In this case, the constraint orientation of M should be loosened to A for squeezing gap in feature attribution O, as shown in the left side of Figure
role in constraining IP (Y) g
Regularization in feature selection. Feature selection typically binarizes M to achieve the map- ping 9 @ M G.. To bridge the gap between M and its binaryzation M', shown as gap2 in Figure 1, the optimization objective of feature selection, I (g @ G*) ) I (g o M: G) in Equation 2 is usually maximized by: (1) discrete constraint (Ying al., 2019) and connectivity constraint (Luo
et al., 2020), which are work for maximizing I (g @ M; (2) sparsity constraint (Schlichtkrull
et al., 2021), which leverages the I or l2 norm to minimize (G @ M)
That is, in the phase of feature selection, regularization plays role in constraining G @ M to G.- In other words, the constraint orientation of M should be tightened to A, (i.e., adjacency matrix of Ge) for squeezing the gap in feature selection to O, as shown in the right side of Figure 1.
In conclusion, while the constraint orientation of M is beneficial to feature attribution and the gap in feature attribution tends to zero, the gap in feature selection will inevitably become large, and vice versa. In other words, since the role of regularization is totally different across two phases, regularization is essentially tradeoff to guarantee the mapping effectiveness both in two phases:
Proposition 1 (Essence of Regularization) Regularization in GNNs explainability is essentially the tradeoff scheme to pursue the balance between the phases of feature altribution and selection.
4 PROPOSITIONS OF REGULARIZATION IN EXPLANATION METHODS
In this section, derive three intriguing propositions stem- ming from GIBE and Proposition 1, which respectively re- veal the relation between regularization and three important concepts in GNNs explainability (i.e., sparsity (Ying et al.,
Scenario: High sparsity
Scenario: Low sparsity
2019; Lucic et al., 2022), stochastic mechanism (Luo et al., 2020; Wang et al., 2021) and OOD issue (Miao et al., 2022; Wu et al., 2022)). Inspired by these propositions, we pro- pose two simple yet effective regularization schemes.
O OGM''))) 1G O M:
GG O M:G") -ig O M: g)
Ecutraliic via large regularization
ncutralzze small regulanization
MI Feature Selection
MI in
4.1 REGULARIZATION & SPARSITY
Feature Selection
We first focus on the relationship between regularization and predefined sparsity yj of targeted subgraph G", where 1 1 - 1 l/lg) According to Equation 2, sparsity vari- ation of G only affect the objective of feature selection, I (G C M I (G O M; Therefore, we aim to de- rive the relation between y and the phase of feature selec- tion in current explanation methods. The process of deriva- tion is exhibited as follows:
Keep Balance
Keep Balance
MI in
MI in Feature Attribution
Peature Attribution
The rationale of sparsity adaptive regularization scheme.
Figure/ 2:
To calculate this objective, we first introduce the variational approximation (9 @ M g") for PPG @ M G*) and Q for marginal distribution P(g O M) be derived as:
simultaneously. Then the lower bound of the objective
I ( C M:9") - I (g & M; Z EgoM,- [log Po (G o M [199)) H(Go M) -gGoM. [KL (P (G M [Q M))]
(4)
Detailed derivation is shown in Appendix A.4. While M is inherited from feature attribution, the above lower bound is in positive relation to its first term, Egem.g- [log Ie (g o M ) since the
rest of terms are constants. To calculate its first term, the variational distribution ( @ M g*) is defined follow: for every two directed node pair (u, v) in g", we sample the elements of M
4

---

Under review as a conference paper at ICLR 2023
by muv (ern(z) where [0, 1] is hyperparameter. Borrowing the above Ps, the first term of Equation is equal to:
Eoo.,-- [log Po (g M| 9*] =
Σ
May log
muae + (1 Muu) log
(1 Mbn))
(5)
(u.r)Eε*
where Ex is the set of edges in g". Note that the sum in Equation 5 has positive relation to the number of terms |8*), which equals to (1 - - since M is inherent and the values of every terms fixed. That is, in the phase of feature selection, the lower bound of the objective is in negative relation to It is worth to mention that Equation 5 is similar with the regularization terms proposed in GSAT (Miao et al., 2022). However, it is appropriate for mainly post-hoc explanation methods while terms proposed in GSAT is tailored for itself solely.
Therefore, for an interpreting task appealing low sparsity, the magnitude of objective in feature selection is large. Since regularization is the tradeoff' scheme between two phases (Proposition I), should be loosened to a favorable direction for feature attribution to keep the balance, and vise versa. We illustrate this process in Figure 2. More formally:
Proposition (Sparsity-adaptive Regularization) For a certain interpreting task, let K; and K; are the optimal coefficient vector of regularization under the predefined explanatory sparsity qi and mjj For all rj E (0, 1) we have:
m ny K, Kj
(6)
According to Proposition 2, we propose a simple yet effective scheme called Sparsity-adaptive Regularization Scheme (SRS) enhance the performance of existing explainers. Concretely, SRS first seeks for the optimal coefficients K, under the certain sparsity ni. by grid search, then for other sparsity n7. SRS sets Kj according to K;- 2 K, Specific implementation and experimental verification are provided in Section 5.2.
%
4.2 REGULARIZATION STOCHASTIC MECHANISM
In this part we focus on the relationship between the regularization and the stochastic mechanism. Recent years have witnessed surge in research that focuses on leveraging the stochastic mechanism to enhance the performance of GNNs explainability (Luo et al., 2020; Wang et al., 2021; Miao et al., 2022). Con- cretely, the probability of graph G is first factorized 1 if the
Scenarto: without Stochasticity
Scenario: add Stochasticity
G M:5")
iLG O M: Mig") 1G O M)
Improve
(M
IG O M: S>
as P(G) ((ee (euy), where eij edge (i exists, and 0 otherwise. Then the Bernoulli distribution is employed instantiate P (e.g). where the stochastic mechanism is introduced in this process (Luo et al., 2020). Meanwhile, the gumbel-softuax reparameterization trick is applied to make sure the gradient in the Bernoulli distribution is traceable (Jang al., 2017). However, despite the satisfactory perfor- mance of the stochastic mechanism, current researches mainly neglected the theoretical basis of the stochastic mechanism.
explicit regullarization
explicit regulatization:
impticit regularization
MI in.
MI in Feature Selection
Feature
Selection
Imbalance
Keep Balance
MI in
MI in Feature Attribution
Feature
Attribution
We argue that the stochastic mechanism bolsters the explanation methods via facilitating the feature selec- tion. Specifically. employing the stochastic mecha- nism to the training stage of M can be regarded as adding random noise to M (Shwartz-Ziv & Tishby, 2017). The entropy of the mask's 's distribution will continue to increase during this process under the constraints of the information bottleneck. That in turn maximizes the conditional entropy ( @ M). Since the entropy of input graph (g) is a constant, mutual information I(G O M, 9) = H(G) - H G O M) is minimized contributed to stochastic mechanism. In conclusion, the stochastic mechanism can accelerate the process of mini- mizing I(G @ M. 9). thus endowing the compression of the explanatory subgraph. That is, it can be regarded as the implicit regularization term in favor of the phase of feature selection. We summarize this rationale as Proposition 3 and verify it in Section 5.3.
Figure 3: Rationale of stochastic mecha- nism in explainability: an implicit regular- ization term.
5

---

Under review as a conference paper at ICLR 2023
Proposition 3 (Rationale of Stochastic Mechanism) Stochastic mechanism works as the implicit regularization term, which endows GNNs explainability with better compressibility.
4.3 REGULARIZATION & OOD
Many recent endeavors have been made towards revealing the nut-of-distributinn issue of the post- hoc explanation methods (Chang et al., 2019; Qiu et al., 2022; Wu et al., 2022; Miao et al., 2022). Concretely, OOD issue is posed in the data space since the distribution of full graph P(g) differs from that of subgraph PPG.)) w.r.l some properties of graph data such as size (Bevilacqua et al., 2021), degree (Tang al., 2020) and homophily (Lei al., 2022). Thus it is fallacious leverage the original GNN f'. which is trained for the full graphs, to estimate the MI in terms of subgraphs. Unfortunately, most previous explainers (Ying et al., 2019; Luo et al., 2020; Vu & Thai, 2020; Miao et al., 2022) simply feed G @ M into f', unaware of that I (f(G O M); Y) is not proportional to I (9 @ M; Y), sometimes not even close.
To reveal the relationship between OOD issue and regularization, we scrutinize the OOD between P(g) and (G..) and decouple into two phases: (1) OOD-AT between P(g) and (P @ M) posed in feature attribution and (2) OOD-SE between (P(g @ M) and IG.). posed in feature selection.
OOD-AT. We first focus on OOD-AT posed in feature attribution. According to Equation 3, fea- ture attribution searches for the optimal M via calculating the cross-entropy H O M), Y) to approximate (G の M; Y). The approximation error, also be illustrated as gapl in Figure 1, is given the sum of second and third term of Equation 3. For the second term, H (Y), since it is the constant across different candidates M, it will not affect the search results. Unfortunately, for the third term, KL (IP (Y] G C M) P& (Y g @ M)), OOD-AT makes this part far away from zero and inevitably fluctuate across different M.
This fluctuation degrades the fairness of the searching process of optimal M, and further degenerates the effectiveness of the mapping, 9 -> g @ M in feature attribution. Thus we formulate the tangible impact caused by OOD-AT as:
OOD-AT & DM (IP (Y ( M) [IPe (Y @ M)).
(7)
where ID is the Variance. If regularization pushes P(g @ M) close P(g) via constraining M to A, the Equation 7 will close to zero and OOD-AT will cause little degradation. Note that this process similar to the left side of Figure 1: the constrain orientation loosened to A eliminate the gap-
OOD-SE. We then focus on OOD-SE posed in feature selection. While feature selection binarizes M to get M' and generates 9, = G O M', the degree of OOD-SE can be simplified as the distance between M and A. That is, OOD-SE issue will be remedied if regularization pushes P(G O M) close to P(G.) via constraining M to A...
In conclusion, just similar to the dilemma of regularization between two phases described in Section 3.2, the optimal regularization scheme for remedying OOD-AT and OOD-SE is totally different. That is, for certain interpreting task, there is inherent uncooperativeness between OOD in feature attribution and OOD in feature selection. Note that the above analysis also explains why the OOD issue is the inherent limitation of post-hoc explainability: since can only remedy one side and ignore the other side, OOD can not be thoroughly settled by adjusting the training objective and hyperparameters solely. We formulate this proposition as:
Proposition 3 (Rationale of OOD) For a certain interpreting task, the OOD issue is imputed to the contradictory effects of regularization on the phases of feature attribution and selection.
Even though the OOD issue is inherent, we introduce a simple yet effective regularization scheme called OOD-resistant Regularization Scheme (ORS) to alleviate the above dilemma to some ex- tent. Specifically, in the early stage of training, loose regularization of M is performed in favor of alleviating OOD-AT for the more precise mapping G - G C M. Similarly, we then gradually tighten the regularization of M to alleviate the OOD-SE for the mapping G @ M + G.. ORS can achieve better explanation performance than the common invariable regularization scheme. Specific implementation and experimental verification are provided in Section 5.3.
EXPERIMENT
In this section, we conduct extensive experiments to answer the following questions:

---

Under review as a conference paper at ICLR 2023
GNNExplainer on BA3
(b) GNNExplainer on MUTAG
(c) GNNExplainer on MNIST
0.8
THE ACC AUC
1.--
ACC.ATC
1.00
THE ADC 802
ACC 402
Aocuracy
0.7
ACC g04
Accuracy
0.9
ACC 0
Accuracy
0.95
ACC ACCALC
0.0
0.8
0.80
NCC 2
0.03
0.5
0.73
0.4
0.35
10
10
Multiple.n regularization coefficient
Multiple regularization coefficient
Multiple of regularization coefficient
(d) GSAT BA3
(c) GSAT on MUTAG
(1 GSAT MNIST
0.8
AUC
1.0
1.00
ADC 022
ADC 602
0.7
ACC 804
ADC
g03
0.95
Accuracy
Accuracy
0.9
Accuracy
ACC 6.0
0.6
0.90
ACX g.0.
0.5
0.3
0.85
0.4
0:40
0.7
0.3
0.35
10 coeffiicc
Multiplc of regularization coefficient
Multiple of regularization coefficient
Multiple of regularization coefficient
Figure 4: The performance of baseline explainers averaged across 10 runs for different sparsity, while the coefficient of regularization is changed. Best viewed in color.
RQ1: Can Proposition provided in Section 3.2 and Proposition provided in Section 4.1 be verified? Furthermore, how does the SRS perform?
RQ2: Can Proposition provided in Section 4.2 and Proposition provided in Section 4.3 be verified? Furthermore, how does the ORS perform?
5.1 SETTINGS
Datasets and Target GNNs. We use one synthetic dataset and two real datasets which are publicly accessible and train three popular GNN models for them. More details be found in Appendix B.
BA-3motifs (Ying et al., 2019) contains 3,000 graphs attaching with the motif types: house, cycle, or grid, for which trained ASAP (Ranjan et al., 2020), has achieved 99.3% testing accuracy. MUTAG (Kazius et al., 2005) contains 4,337 molecule graphs categorized into two classes based on their mutagenic effect on the Gram-negative bacterium. The well-trained Graph Isomorphism Network (GIN) (Xu et al., 2019) has achieved 97.7% testing accuracy.
MNIST (Monti et al., 2017) superpixel converts 70,000 images into the graphs of superpixel adjacency. A trained Spline-based GNN (Fey al., 2018) has achieved 94.6% testing accuracy.
Evaluation Metrics and Baselines. We select three commonly used metrics evaluate results: Accuracy, Precision, and Fidelity. Moreover, we leverage six state-of-the-art methods to verify proposed propositions and schemes, covering the GNNExplainer (Ying al., 2019), PGExplainer (Luo et al., 2020), GraphMask (Schlichtkrull et al., 2021), CF-GNNExplainee (Lucic et al., 2022), Refine (Wang et al., 2021) and GSAT (Miao al., 2022). More details provided in Appendix B.
5.2 EVALUATION OF PROPOSITION 1, PROPOSITION 2 AND SRS (RQ1)
We first focus verifying the Proposition 1 and Proposition 2 provided in Section 3.2 and Sec- tion 4.1 simultaneously. Since the role of regularization to keep the balance between two phases (Proposition 1), the variation of its coefficient K will break the balance and ulteriorly impose oppo- site impacts on the performance under different sparsity 7) (Proposition 2).
In sight of this, we start with the optimal coefficients of regularization for ACC-AUC by grid search, then we deliberately increase K and record the accuracy under different 77. Experiment results are shown in Figure 4, where the horizontal axis represents the multiple of the increment of K and the length marker shows the variance. Note that the performance of other baselines have similar trends to the results in Figure 4.

---

Under review as a conference paper at ICLR 2023
Table 1:
The performance of baseline explainers averaged across 10 runs. methods are bold with blue lines, and the strongest baselines are underlined.
The best performing
BA3-motir 1005
Mutagenicity
MNIST Fidelity30.55
ACC-AUC
Precision
ACC-AUC
F00
ACC-AUC
Procision
GNNExplainer +SRS
0.4
0.389=004
0.532
0,841 =0011
0.442:0m0
0.798
0.274-10221
0.512
0.4131omx
0.597 1o
0.503
0,805
0.295 10000
0.542
PGExplainer
+,011
0.482=002
0.564
0.809
0,5474mm1
0.800
0,280
0.528
+SRS
0.558
0.502=002
0.617soms
a.84
0.586
0.822:004:
0.304
0.570
GraphMask
0.489
0.408=0022
0.579
0.826#9106
0.400=
0.817=0047
=.291
0.437=+0088
+SRS
0
0.444=0022
0.594
0,878
0.451=8m2
0.839
0.315
0.499:20.0
CF-GNNExplainer
0,45
0.416=0000
0. 0.508=0002
0.842+0.00
0,474
0.822x0037
0.22 -0203
0.507
+SRS
0.476aam
0.44518014
0.549
0.874_g00t
0.49618mm
0.8521am
0,260
0.556.10
Refine
0, 0.542
0.447goms
0. gonts
0.5791amM
0.854_0000
0.300
+SRS
0,550ammx
0.472.om
0.632:
0,921
0.593
0.870
0.333
0.574.00m
GSAT
0.582 Loaz?
a.477
0.602
0.8922um
0.322
2002
0.520
+SRS
1.6044000
0.490_00m
0.6291.400
0.913gmm
10
0.890_omg
0.142_0000
0,54220000
Relative Impro.
4.2%
7.2%
5.3%
6.1%
7.9%
3.4%
5.8%
8.0%
According to Figure 4 we have the following observations:
While K is changed, the fluctuation of overall performance (i.e., ACC-AUC) is not too strong (+7.25%) on average. However, the fluctuation of ACC in high sparsity and low sparsity is obviously larger (+21.86%) than that of ACC-AUC. These observations verify the role of regu- larization: a tradeoff to keep the balance and guarantee the overall performance at a high level. ACC under low sparsity and ACC-AUC are decreasing with the increment of the regularization coefficient. On the contrary, ACC in high sparsity is increasing by a large margin (29.63% 1) on average. These increases up maximum of 67.83% in MUTAG are counterintuitive and eccentric. Whereas, these observations exactly conform to the theoretical analysis in Propositon 2: loose constraint (i.e., large K) is beneficial to the performance in high sparsity, while tight constraint (i.e., small K) is in favor of the performance under low sparsity.
While the above observations verify the Proposition and Proposition 2, we now evaluate the effec- tiveness of the derived scheme, SRS. Specifically, for a certain interpreting task, we first seek for the optimal K under 1) = 0.5 by grid search, then we reduce or enlarge K proportionally to the variation of 1 in (0.1,..,, 0.9). Results are summarized in Table 1. We have the following observations:
The baseline explainers enhanced by SRS outperform themselves in all cases. To be more spe- cific, SRS achieves significant improvements over the six baselines w.r.f. fidelity by 7.9% and 7.2% averagely in MUTAG and BA3-motif, respectively. The improvement up to a maximum of 12.8% when GNNExplainer is employed to interpret graphs in MUTAG. It demonstrates the effectiveness and universality of SRS, and verifies that SRS can be leveraged to boost the aceu- racy of current explainers. We attribute these improvements to the ability that SRS can allocate the most adaptive coefficient of regularization for diverse explanatory sparsity.
SRS provides much stabler explanations than the baselines for the much smaller variance. More specifically, STD of SRS outperforms baseline by a larger margin (22.8% J) on average. This phenomenon verifies that the performance of most explainers is not stable since depends on the matching degree between the task and regularization terms, while SRS can avoid this dilemma by adaptively allocating regularization terms.
5.3 EVALUATION OF PROPOSITION 3, PROPOSITION 4 AND ORS (RQ2)
We now focus on verifying the Proposition 3 proposed in Section 4.2 and the Proposition 4 proposed in Section 4.3. According to Proposition 3, the stochastic mechanism endows GNNs explainability with better compressibility, which has a similar rationale to the regularization term. In sight of this, we gradually increase the magnitude of stochasticity in explainers and observe whether the performance has the same trends the results in Figure 4. The overall results are summarized in Figure 5. We have the following observations:
The ACC under low sparsity and ACC-AUC are decreasing (8. 7.% 1 and 19.85% J) with the in- crement of stochasticity magnitude, while the ACC under high sparsity is increasing (14.52% 1) in this case. These increases up to a maximum of 37.03% in MUTAG. Therefore, the large mag- nitude of stochasticity is beneficial to the performance in high sparsity and vice versa. This effect is similar the effect of regularization terms. In conclusion, the same trends between Figure
8

---

Under review as a conference paper at ICLR 2023
(a) PGExppainer on BA3
(b) PGExppainer on MUTAG
cc) PGExplainer on MNIST
0.88
ACD-AUI:
2-E ACCACIC
1.00-
ACD 8-0
ACC
Accuracy
0.7
0.
Accuracy
THE A00
Accuracy
ACC-UU 4 0.
0.6
0.80
ACC 88
0.4
1.2
1.6
1.0
1.2
1.4
1.6
1.8
2.0
12
14
16
2.0
Multiple of stochasticity magniuude
Multiple of stochasticity magnitude
Multiple of stochasticity magnitude
(d) GSAT on BA3
(c) GSAT on MUTAG
(1) GSAT on MNIST
0.8
ACC-AUC:
1.0
ACCALIC
1.00
ACC 03
Accuracy
0.7
ACC 0.04
Aguuracy
0.9
ACC ACC 0.9
Accuracy
0.95
3-E ACC AUC
ACC 0.2
0.6
1-
0.90
ACC 0.0
0.5
0.8
0.4
0.40
0.3
122
1.6
2.0
10
14
15
1.
2.0
1.2
1.6
200
Multiple stochasticity magnitude
Multiple of stocbusticity magnitude
Multiple of stochasticity magnitude
Figure 5: The performance of baseline explainers averaged across 10 runs for different sparsity while the magnitude of stochasticity is changed. Best viewed in color.
and Figure 5 verify that the stochastic mechanism has similar rationale with the regularization terms, and further verify the Proposition 3.
In terms of Proposition 4, since the degree of OOD is intractable, we directly leverage the derived scheme: ORS to remedy the OOD issue in explainers. We surmise the results in Table 2. We find that:
Table The performance of baseline explainers av- eraged across 10 runs. The best performing methods
are bold with blue line, and the strongest baselines are underlined.
The explainers enhanced by ORS get the higher accuracy on the graph classifica- tion tasks than themselves. Specifically, ORS achieves significant improvements over the strongest baselines w.r.t. ACC- AUC by 4.1% and 3.5% MUTAG and BA3-motif, respectively. These im- provements verify the reliability and ef- fectiveness of the ORS. We contribute these improvements mainly to the ad- vantage of remedying the OOD issue in the phases of feature attribution and se- lection. This observation further val- idates the theoretical analysis of the OOD issue in the above two phases (Proposition 4) indirectly.
BA3-motif
Mutagenicity
MNIST
GNNExplainer +ORS
0.439
0.841
0.79810047
0.466=0033
0.860
0.814
PGExplainer +ORS
0.51
0.809
0.800
0.537=0019
0.821
0.81310007
GraphMask +ORS
0.489=an51
0.826*0056
0.817=0047
0.496
0.844
0.828
CF-GNNExplainer +ORS
0.453
0.84210.08
0. 0.822.10:077
0.470.0006
1.853
0.84410.:25
Refine +ORS
0.5422003
0.905
0.85411002
0.511
+0011
0.86620.00
GSAT
0.582
0. 0.892+0.011
0.87140.0
+ORS
0.591
0.90310.05
0.083
Relative Impro.
3.3%
3.6%
3.1%
CONCLUSION
In this work, we rethink the role of regularization in GNNs explainability from the perspective of information theory. We first retrospect the concept of GIB and derive the new GIB form tailored for GNNs explainability: GIBE. The role of regularization in the phases of feature attribution and selection are explored respectively under the guidance GIBE. Moreover, four intriguing proposi- tions and two common optimization schemes of regularization are introduced inspired by the above insight. Extensive experiments are conducted on both synthetic and real-world datasets to validate the rationality of our propositions and the superiority of our scheme. This work represents initial attempt of digging deeper into the regularization in explainability theoretically, which provides a new perspective understand the role of regularization.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
In this work, we rethink the role of regularization in GNNs explainability from the perspective of information theory, where human subject is related. We believe digging deeper into the regular- ization theoretically is beneficial for performing the better explanations and consequently improving the model's transparency real-world applications.
REPRODUCIBILITY
We summarize the efforts made to ensure reproducibility in this work. (1) Datasets: We use one synthetic dataset and two real datasets which are publicly accessible, where the processing details are included Appendix B. (2) Model Training: We provide the training details (including hyper- parameter settings) in Appendix B which are consistent with our implementation in the code (ef. the anonymous link provided Abstract). (3) Theoretical Results: All assumptions and proofs can be referred to Appendix A.
REFERENCES
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. CoRR, 1bs//995..3366, 2019.
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. In ICML, volume 139 Proceedings of Machine Learning Research, pp. 837-851. PMLR, 2021.
Chun-Hao Chang, Elliot Creager, Anna Goldenberg, and David Duvenaud. Explaining image clas- sifiers by counterfactual generation. In ICLR (Poster). OpenReview.net, 2019.
Jianbo Chen, Le Song, Martin Wainwright, and Michael I. Jordan. Learning explain: An information-theorrtiic perspective on model interpretation. In ICML, volume 80, pp. 882-891, 2018.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? dissection on graph classification. CoRR, abs/1905.04579, 2019.
Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.
Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Process. Mag., 29(6):141-142. 2012.
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. CoRR, abs92003.00982, 2020.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splinecnn: Fast geometric deep learning with continuous b-spline kernels. In CVPR. Computer Vision Foundation / IEEE Computer Society, 2018.
Zhiwei Guo and Heng Wang. A deep graph neural network-based mechanism for social recommen- dations. IEEE Trans. Ind. Informatics, 17(4):2776-2788 2021.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameteriization with gumbel-softmax. In ICLR (Poster). OpenReview.net, 2017.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry, 48(1)312,3320 2005.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
Runlin Lei, Zhen Wang, Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. CoRR, abs/2205. 1392200511892. 13892, 2022.
10

---

Under review as a conference paper at ICLR 2023
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In ICML, volume 139, pp. 6666,6679, 2021.
Ana Lucic, Maartje A. ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cr- gnnexplainer: Counterfactual explanations for graph neural networks. AISTATS, PMLR, 2022.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In NeurIPS, 2020.
Mufti Mahmud, M. Shamim Kaiser, T. Martin McGinnity, and Amir Hussain. Deep learning in mining biological data. Cogn. Comput., 13(1):1-33, 2021.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic atten- tion mechanism. In ICML, pp. 15524-15543, 2022.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning graphs and manifolds using mixture model cnns. In CVPR, pp. 5425-5434, 2017.
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. CVPR, pp. 10772-10781, 2019.
Luyu Qiu, Yi Yang, Caleb Chen Cao, Yueyuan Zheng, Hilary Hei Ting Ngai, Janet Hui-wen Hsiao, and Lei Chen. Generating perturbation-basee explanations with robustness to out-of-distribus data. ACM, 2022.
Ekagra Ranjan, Soumya Sanyal, and Partha P. Talukdar. ASAP: adaptive structure aware pooling for learning hierarchical graph representations. In AAAI, pp. 1470-5477,20
Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should I trust you?": Explaining the predictions of any classifier. In KDD, pp. 1135-1144, 2016.
Kaspar Riesen and Horst Bunke. IAM graph database repository for graph based pattern recognition and machine learning. In SSPR/SPR, pp. 287-297, 2008.
Aravind Sankar, Xinyang Zhang, and Kevin Chen-Chuan Chang. Meta-gnn: metagraph neu- ral network for semi-supervised learning in attributed heterogeneous information networks. In ASONAM, pp. 137-144, 2019.
Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for NLP with diffcrentiable edge masking. In ICLR, 2021.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. CoRR, /oss//00000810 2017.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu C. Aggarwal, Prasenjit Mi- tra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional networks. In CIKM, pp.
ACM, 2020.
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In NeurIPS, 2020.
Xiang Wang, Ying-Xin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained explainability for graph neural networks. In NewrIPS, pp. 18446-18458, 2021.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. CORR, 12./2010.121111 2020.
Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering invariant rationales for graph neural networks. CoRR, abx/2201. 128722 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. CoRR, abs/1901. abs//190..0096, 2019.
11

---

Under review as a conference paper at ICLR 2023
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? In ICLR. OpenReview.net, 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hier- archical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer:
Generating explanations for graph neural networks. In NeurIPS, pp. 9240-9251, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurlPS, 2020.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. In ICLR. OpenReview.net, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. CoRR, Abs/2012.15445, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In ICML, volume 139, pp. 12241-12252. PMLR, 2021.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, pp. 4438-444 2018
Tianyi Zhao, Yang Hu, Linda R. Valsdottir, Tianyi Zang, and Jiajie Peng. Identifying drug-targe interactions based on graph convolutional network and deep neural network. Briefings Bioinform. 22(2):2441-2150, 2021.
Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Ji Geng. Meta-gnn: On few-shot node classification in graph meta-learning In CIKM, pp. 2357-2360, 2019.
A THE PROCESS DERIVATION IN TERMS OF INFORMATION THEORY
A. DERIVATION OF GIBE
We focus on the detailed derivation GIBE. Firstly, the proportion mutual information: imvari- invertible transformations (Shwartz-Ziv & Tishby, 2017) can be formulated as:
YX; = I (()))))))))
(8)
for any invertible functions v and é. Since Y is determined by G" in the sense that Y = f(g)) +e for some deterministic invertible function f according to Equation 8, I (G.; Y) in the objective of GIB (i.e., Equation 1) can be rewrote as (Miao al., 2022):
I (G.: Y) (G.:
(9)
Thus we can decompose the first term in the objective of GIB into:
TG,, Y) = (1 (G:; + BI (G.;9"),
(10)
for any 8 E (0, 1). Comparing Equation 10 and Equation 1, the objective of GIB can be rewritten
as:
arg max - (9:: Y) - 8 [7 (g @ M;g*) [g M:9)).
(11)
g.
We then substitute the coefficient a 33((1 - (3) into above equation:
arg max / (G.; Y) a (G,; -(
(12)
G.
Taking G o M as the substitution of G., the form of GIB for explainability can be derived as: arg max (g M; a (T M.g*) I [g M;9)),
(13)
which is the objective of GIBE.
12

---

Under review as a conference paper at ICLR 2023
A.2 PROOF OF THE CONVERGENCE OF GIBE
Theorem A.I. For any a E +x)+ we have: Go M 9 maximizes the objective of GIBE:
I (9 @ M; Y) + a (G @ M;
(g - M:9)].
Proof. Consider the following derivation,
I al[( M I(G o M:g)
= -
+ ++00:X|[G0MM-((C0000M..
-(1 +1=0/Xx.0)-(110000xXX0001 +a (oM) (
( M.Y)
=(1 =[1=0//X::0--000XX00000 - G
Y).
(14)
Since 7(Y; is a constant, for any a E (0. ), 9 ( M that maximizes the objective of GIBE
also minimizes T(g"; Y Go M) + aT @ M Y). As T(g:: Y g O M)
> 0 and
g M Y) > 0, so the lower bound of ((";; Y
g M) + aT M Y 0.
We have G O M 9 can make [("; Y G M) + (G";;
g M Y) 0. This is because (1)
Y = f("))++ where is independent of G so that / (g"; Y (90M) = 0 and (2) = (Y
where is independent of G that I( @ M Y) =0 0.
Therefore, 9 @ M = G" maximizes the objective of GIBE in Equation 2.
A.3 ESTIMATION OF MUTUAL INFORMATION IN FEATURE ATTRIBUTION
According to the definition of mutual information:
P (
I (G O M; Y) = Ego log
(15)
P(Y)
Since (Y g @ M) intractable, we introduce variational approximation Pg (Y 1 M) for it. Then, we can rewrite Equation 15 as:
log Po (Y (@M)
o M; EGOMY
P(Y)
+ EGOM KLL (IP (Y 9 O M) IP (Y g M))
(16)
EgoM, [log Po (Y G O M) (Y)
EGOM [KL (IP Y 9 O M) PP (Y T M))]
A.4 VARIATIONAL BOUNDS MUTUAL INFORMATION IN FEATURE SELECTION
We now focus on the lower bounds for mutual information in the phase of feature selection:
I (G M; (9 O M:9).
(17)
For the first term 7 i9 ④ M; by definition:
P 9*)
I (G M g*) Egom.. log
(18)
PCG & M)
Since IP (G c M G*) is intractable, we introduce a variational approximation P. (G ④ M g*) for it. Then, we obtain a lower bound for Equation 18:
Po ( M G*)
I (G C M: Egom.. log
P(G - M)
+ BoOM.S
[KL (P & M 9¹) (
(19)
PA (g @ M gt)
> EgOM...
log
P(g о M)
E
[log Fo (G O M g*)] + H1 M).
13

---

Under review as a conference paper at ICLR 2023
Then for the second term (g @ M; 9) we have:
O M M P(G O M)
[g O M;g) = EgoMo
log
(20)
Since (g & M) is intractable, we introduce variational upproximation Q for it. Then, we obtain upper bound for Equation 20:
P log
I (g o M; = EooMS
Q O M)
EGOM. (F M) [Q
(21)
P M 9)
ggoM,g
log
Q O M)
EgeM.9 [KL (IP O M
Q MM)]
Plugging in Equation 19 and Equation 21, we obtain a variational lower bound of Equation 17 as the objective of feature selection:
I (g (: I (g M:9) Egem. Po (9o H
(22)
RçOMs (PI M (0
B EXPERIMENT SETTING
Datasets and Target GNNs. We use synthetic dataset and real datasets which are publicly accessible. Three popular GNN models are trained to perform graph classification. The statistics of datasets and the configurations of GNN models summarized in table 3. Note that some benchmark datasets may not satisfy the assumption in Section 2, for further exploration, we still take them into consideration.
MUTAG (Kazius et al., 2005; Riesen & Bunke, 2008) contains 4,337 molecule graphs categorized into two classes based on their mutagenic effect on the Gram-negative bacterium.
BA-3motifss (Ying et al., 2019; Luo et al., 2020) contains 3,000 graphs attaching with one of three motif types: house, cycle, and grid, where Barabasi-Albert (BA) graphs are adopted as the base. MNIST (Monti et al., 2017; Deng, 2012) superpixel dataset converts 70,000 images into the graphs of superpixel adjacency, where every graph is labeled as one ten digit classes.
GIN (Xu et al., 2019) suppresses the popular GNN variants, such as Graph Convolutional Net- works and GraphSAGE in terms of expressive power, it generalizes the Weisfeiler Lehman graph isomorphism test and hence achieves maximum discriminative power under the neighbor- hood aggregation framework.
ASAP (Ranjan et al., 2020) utilizes a self-attention network along with a modified GNN formu- lation capture the importance of each node in given graph, and learns a sparse soft cluster assignment for nodes at each layer to effectively pool the subgraphs to form the pooled graph. Spline-based GNN (Fey et al., 2018) adopts novel convolution operator based on B-splines, which operates in the spatial domain and aggregates local features, applying a trainable continuous kernel function parametrized by trainable B-spline control values and allowing very fast training and inference computation.
Evaluation Metrics. It is crucial importance to evaluate the explanations quantitatively since human evaluations are highly dependent their subjective understanding. Prior studies have pro- posed some metrics to quantitatively assess the explanations (Yuani et al., 2020; Dwivedi et al., 2020), among which select three commonly used metries evaluate results. For clarity, denote G as the explanatory subgraph by taking top-K edges in G, and [ as the number of edges in graph G.
Predictive Accuracy (ACC@T) (Chen et al., 2018). This metric feeds the explanatory subgraph into the target model and measures the performance of the explanation by auditing how well it recovers the target prediction, where is the predefined sparsity. Formally, given the trained GNN models have
ACC@n Egg (T(T())) [G/
(23)
14

---

Under review as a conference paper at ICLR 2023
Table 3: Statistics of the datasets and configurations of GNN models.
MUTAG
BA3-motif
MNIST
Graphs#
4,337
3,000
70,000
Classes#
2
10
Avg.No Wyg.Noess#
30.32
31,44
66.87
Adg.Edges#
30.77
31.24
725.39
Target GNNs
GIN
ASAP
Spline-based GNN
Layers#
2
2
5
Testing Accuracy
0.977
0.993
0.946
where I(. is the indicator function that takes value when its two arguments are equal and takes value 0 otherwise. Moreover, plot the curve of ACC over different sparsity n E (0, 0.1. 0.9) on the test set and denote ACC-AUC as the area under the ACC curve. Note that ACC@n and ACC-AUC do not rely ground truth labels, and thus suitable for all the datasets.
Precision@N (Ying et al., 2019). This metric measures the consistency between the explanatory subgraph Go and the ground-truth subgraph G*. Concretely, the edges within G are positive G, while the remains are negative. In this case, precision can be adopted as the evaluation protocol. More formally,
1 n |
Precision@N N EEg
(24)
(Yuan al., 2020). The Fidelity metric studies the prediction change by removing important input features identified by explanation methods. Formally,
Fi
Fidelity @p Eg [9) - f (00xxxx0))
(25)
Baselines. We leverage the state-of-the-art methods to verify proposed propositions and optimiza- tion schemes, covering the followings:
GNNExplainer (Ying et al., 2019) directly learns an adjacency matrix mask through maximiz- ing the mutual information between a GNN's prediction and distribution of possible subgraph structures, which is performed via multiplying the mask to the input features.
PGExplainer (Luo et al., 2020) adopts a deep neural network to parameterize the generation process of explanations, which makes it natural approach to explaining multiple instances col- lectively. It can also provide global explanations for certain class.
GraphMask (Schlichtkrull et al., 2021) learns simple classifier that, for every edge in every layer, predicts if that edge can be dropped, in a fully differentiable fashion. Then by dropping edges without deteriorating the performance of the model, the remaining edges naturally form an explanation for the model's prediction.
CF-GNNExplainer (Lucic et al., 2022) focuses on the counterfactual explanations by figuring out the minimal perturbation to the input (graph) data such that the prediction changes. By instan- tiating the perturbation with only edge deletions, they find out the edges which are crucial for the original predictions.
Refine (Wang et al., 2021) develops a explainer that can generate multi-grained explanations by exploiting the pre-training and fine-tuning idea. Specifically, the pre-training phase exhibits global explanations with the prototypical patterns, and the fine-tuning phase further adapts the global cxplanations in the local context with high fidelity.
GSAT (Miao et al., 2022) leverages stochastic attention to block the information from the task- irrelevant graph components while learning stochasticity- relevant subgraphs for interpretation. Though it's naturally an inherently interpretable method, it also works in post-hoc way through fine-tuning fashion. We adopt this post-hoc working mode as one baseline.
attention select the task-
Training Optimization and Early Stopping. All experiments are done on a single Tesla V100 SXM2 GPU (32 GB). During training, use Adam (Kingma & Ba, 2015) optimizer. The maxi- mum number of epochs is 200 for all datasets. We use Stochastic Gradient Descent (SGD) for the optimization of all GNNs models. The initial learning rate is set to: 10-3 for BA3-motif. 10-2
15

---

Under review as a conference paper at ICLR 2023
for MNIST, and 10-3 for MUTAG. Also, exhibit early stopping avoid overfitting the training dataset. If the model's performance on the validation dataset is without improvement (i.e. valida- tion accuracy begins to decrease) for five epochs, stop the training process to prevent increased generalization error.
Hyperparameter Settings. The most erucial hyperparameter in this work is the coefficients of regularization. For MUTAG: the initial coefficient of sparsity constraints 0.05 and it grows at of 50% each epoch; the coefficient of discrete constraints is 0.5 and grows rate of 50% each epoch; For BA3, these coefficients are set to {0.04, 50%, 0.4, 50%]; For MNIST: these coefficients are {5 10 5, 100%, 10 4.5450%%
For other hyperparameters in baseline methods, we adopt a grid search for the optimal parame- ters using the validation datasets. To be more specific, the learning rate of Adam is tuned in (10-3, 10-2------0 10-1),-----0 ",, and the weight decay is searched in (10-6, 10-1, ,10-3). Other model-specific hyperparameters are set as follows: For PGExplainer, the temperature for reparameterization 0.1; For Refine, the temperature hyperparameter / is 1 and the trade-off hyperparameter is 5; For GSAT, the parameter of Bernoulli distribution r is fixed as 0.6.
C QUALITATIVE EVALUATION OF SRS
GraphMask
GraphMask SRS
GNNExplainer
GNNExplainer SRS
PGExplainer
PGExpliiner SRS
CF-GNNExplhiner
CF-GNNExphainer SRS
Refine
Refine SRS
GSAT
GSAT SRS
Figure 6: Selected explanations in BA3-motif, where the top-6 of directed edges highlighted by red lines. The ground-truth nodes are highlighted in green while the turbulence nodes are distin- guished blue. Best viewed in color.
To have visual inspections on the explanatory subgraphs generated by different explainers and the effectiveness of our proposed scheme SRS, we randomly choose graph instances from the synthetic dataset BA3-motif and present them in Figure 6. For each baseline explainer, we highlight the edges which have the top-K importance scores by red lines, where 6. The ground-truth nodes are highlighted in green while the turbulence nodes w.r.f. nodes in BA-motif are distinguished in blue. According to Figure 6 we can observe that:
Some blue edges which is not belonging to the ground-truth motifs are select by the baseline explanation methods. On the contrary, current explainers enhanced by our proposed scheme SRS inherit the ground-truth edges extracted by the original methods, and eliminate the edges which belong to the Barabasi-Albert (BA) graphs.
Current explainers enhanced by SRS take count of both accuracy and completeness. That is, SRS mainly focuses the edges belonging one ground-trute motifs. However, baseline explainers are often distracted by multiple ground- truth motifs.
completed motif while the graph contains more than
16

---

Under review as a conference paper at ICLR 2023
For blue nodes in Curabasi-Albert (BA) graphs, there are several more intrusive nodes which connected to ground-truth motifs. These nodes will cause higher interference to the generation of explanatory subgraphs. Fortunately, SRS framework can avoid these traps by extracting less turbulence nodes. This phenomenon demonstrates the robustness of our proposed SRS.
17


Reviews:
[{"review_id": "R97oT4vhL4", "reviewer": "Reviewer_eWP9", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to investigate the role of regularization used in existing GNN explainers. The paper analyzes the interpretable GNN model proposed by Miao et al. 2022 by rewriting the training objective function and mapping it into two parts, the feature attribution objective and the feature selection objective. And the authors claim to derive some findings about the \"regularization\" in this rewritten objective.", "summary_of_the_review": "Given the lack of clarity and the limited scope of analysis, I'm inclined to reject this paper as the problems are unlikely to be addressed during the author response period.", "strength_and_weaknesses": "Strength: The topic of this paper, theoretical understanding of GNN explainers, is an important research direction.\n\n\nWeaknesses:\n\n1) The writing of this paper needs to be largely improved. Many essential concepts are not well-defined in the main paper or the appendix. For example, what are the distribution assumptions on the graph data? In section 3.2, \"Treating target GNN f' as the proxy function ...\", what is f'? What is the formal definition of \"regularization\" in GIBE? The technical content is almost unreadable due to missing definitions.\n\n\n2) The paper claims to provide an understanding of the role of regularization for existing GNN explainers. However, the analysis is specific to a particular type of GNN (proposed by Miao et al. 2022) that has a certain interpretable mechanism. It is unclear how the analysis can be transferred to the more commonly used post-hoc explanation methods that can be applied to different types of GNNs.\n\n3) Many typos. For example, \n\n- right before section 3.2, \"... of Equation 2 can be proved to equal to ...\": to be equal to. \n- Many \":\" should be replaced by \",\", e.g., \"... employing Data Processing Inequality (DPI) along the Markov chain**:** ...\". \n- Proposition 2, \"let K_i and K_j is the ...\": let K_i and K_j be the ...\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GfMOionZVRg", "reviewer": "Reviewer_SjeN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the role of regularization in the explainability of GNNs. They find that regularization pursues a balance between feature attribution and selection as well as that optimal regularization is related to the sparsity of the explanations.", "summary_of_the_review": "Overall it's a promising paper, but the clarity/justification of the proposed methodology could be improved.", "strength_and_weaknesses": "Strength\n======\n\n- The paper introduces GIBE, which is similar to GIB but for GNNs explainability.  To my understanding, this is novel.\n- The authors do a good job at discussing the related literature and putting their work into perspective.\n\nWeakness\n========\n\n- Figures 4 and 5 could definitely be improved by using different line formats and markers to facilitate the task of distinguishing the results.\n- Overall, the proposed methodology in the paper is not easy to digest. In particular, I'm confused about the exact implementation/derivation of the proposed SRS method. Could you elaborate more on the rationale behind it? Is it just a grid search on $\\eta$ and then scaling $\\mathbf{K}$ by the best $\\eta$?\n\nQuestions\n========\n\n- What is the role of $\\alpha$ in Eq (2) given that its optimal solution is independent of it?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "57vCNfafpS", "reviewer": "Reviewer_HoXU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies GNNs' explainability from the perspective of graph information bottleneck (GIB). The authors first provide justification on why most existing methods are essentially studying the tradeoff between attribution and selection by modeling them as GIB questions. Based on this observation, the authors discuss the relationship between regularizing the selection in sparsity, stochastic attention and out-of-distribution (OOD) issue, and propose the SRS and ORS scheme. Experimental results demonstrate that the proposed SRS and ORS improves the fidelity and accuracy of the proposed method.", "summary_of_the_review": "The paper is interesting overall. It tries to explain the inherent regularization between attribution and selection for most existing works with the GIBE formulation. With the GIBE formulation, the authors discuss its relationships to sparsity, stochasticity and OOD. The technical contributions could be better highlighted in the literature. And some qualitative analysis would be helpful in understanding the superiority of the proposed method in real world scenarios.", "strength_and_weaknesses": "Strengths:\n- I like the idea of unifying most existing methods with GIB.\n- There are discussions for the relationships between GIBE and sparsity, stochastic attention mechanism and OOD. \n- Experimental results demonstrate the efficacy of the proposed techniques.\n\nConcerns:\n- In section 1, is it possible to better explain why the rank is better than L1 norm? A low-rank matrix is not necessarily sparse, but L1 norm can help control the size of the graph (#edges).\n- Regarding GIB, how do Eq. (1) ensure the sparsity of subgraph? And how do we define the subgraph are sparse enough? Moreover, for some motif structure, it might not be sparse but is very important in determining specific properties of the graph (e.g., the hydroxide group -OH in some molecular graphs). In this case, should we consider such motifs if we want the explanatory subgraph to be sparse?\n- Current definition 2 is not self-contained. It is better to explain what $G*$ is in the definition.\n- A similar definition of GIBE is presented in Theorem 4.1 in (Miao et al. 2022). It would be great to discuss the similarity and difference with that formulation. \n- I think some contents in section 3 (or maybe previous sections) needs adjustment. This is actually a key section to show that most existing methods fall into this GIB-type formulation and to explain the regularization between attribution and selection. This key connection is somehow not clear in previous sections. I get the key idea of this paper until I finished reading section 3.\n- It is better not to use gap1 and gap2 in the main body, as this is specific to Figure 1 and will confuse readers.\n- I didn't fully understand the purpose of Q in Eq. (4). Analytically, why do the introduction of variational approximation Q make it constant while original marginal distribution P is not?\n- Most contents in section 3, section 4.1 and section 4.2 are already studied in (Miao et al. 2022). It is better to spend more efforts in highlighting the contributions by the authors.\n- In addition to quantitative analysis on the proposed method, I am more interested in qualitative analysis like case studies. This is related to one last long-standing question of myself: We say explainability helps understand the behavior of black-box models. But why can we trust the explanations generated by another black-box model(s)? How should we trust this black-box explanation generator?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject