Introduction

Graph-structured data is ubiquitous in real-world applications, manifesting in various domains such as social networks (Fan et al. 2019), molecular structures (Mansimov et al. 2019; Chereda et al. 2019), and knowledge graphs (Liu et al. 2022). This has led to significant interest in learning methodologies specific to graphical data, particularly, graph neural networks (GNNs). GNNs commonly employ message-passing mechanisms, recursively transmitting and fusing messages among neighboring nodes on graphs. Thus, the learned node representation captures both node attributes and neighborhood information, thereby enabling diverse downstream tasks such as node classification (Kipf and Welling 2017; Veličković et al. 2018), graph classification (Xu et al. 2019), and link prediction (Lu et al. 2022).

Despite the success of GNNs in a wide range of domains, their inherent “black-box” nature and lack of interpretability, a characteristic shared among many contemporary machine learning methods, is a major roadblock in their utility in sensitive application scenarios such as autonomous decision systems. To address this, various GNN explanation methods have been proposed to understand the graph-structured data and associated deep graph learning models (Ying et al. 2019; Luo et al. 2020; Yuan et al. 2022). In particular, post-hoc instance-level explanation methods provide an effective way to identify determinant substructures in the input graph, which plays a vital role in trustworthy deployments (Ying et al. 2019; Luo et al. 2020). In the context of graph classification, the objective of graph explanation methods is, given a graph G, to extract a minimal and sufficient subgraph, G^*, that can be used to determine the instance label, Y . The Graph Information Bottleneck principle (GIB) (Wu et al. 2020) provides an intuitive principle that is widely adopted as a practical instantiation. At a high level, the GIB principle finds the subgraph G^* which minimizes the mutual information between the original graph G and the subgraph G^* and maximizes the mutual information between the subgraph G^* and instance label Y by minimizing I(G,G^*) - αI(G^*,Y ), where the hyperparameter α > 0 captures the tradeoff between minimality and informativeness of G^* (Miao, Liu, and Li 2022). As an example, the GNNExplainer method operates by finding a learnable edge mask matrix, which is optimized by the GIB objective (Ying et al. 2019). The PGExplainer also uses a GIB-based objective and incorporates a parametric generator to learn explanatory subgraphs from the model’s output (Luo et al. 2020).

There are several limitations in the existing explainability approaches. First, as shown analytically in this work, existing GIB-based methods suffer from perceptually unrealistic explanations. Specifically, we show that in a wide-range of statistical scenarios, the original GIB formulation of the explainability problem has a trivial solution where the achieved explanation G^*signals the predicted value of Y , but is independent of the input graph G, otherwise. That is, the Markov chain G^*↔ Y ↔ G holds. As a result, the explanation G^* optimizing the GIB objective may consist of a few disconnected edges and fails to align with the high-level notion of explainability. To alleviate this problem, PGExplainer includes an ad-hoc connectivity constraint as the regularization term (Luo et al. 2020). However, without theoretical guarantees, the effectiveness of the extra regularization is marginal in more complicated datasets (Shan et al. 2021). Second, although previous parametric explanation methods, such as PGExplainer (Luo et al. 2020) and ReFine (Wang et al. 2021), are efficient in the inductive setting, these methods neglect the existence of multiple motifs, which is routinely observed in real-life datasets. For example, In the MUTAG dataset (Debnath et al. 1991), both chemical components NO₂ and NH₂, which can be considered as explanation subgraphs, contribute to the positive mutagenicity. Existing methods over-simplify the relationship between motifs and labels to one-to-one, leading to inaccuracy in real-life applications.

To address these issues, we first analytically investigate the pitfalls of the application of the GIB principle in explanation tasks from an information theoretic perspective, and propose a modified GIB principle that avoids these issues. To further improve the inductive performance, we propose a new framework to unify existing parametric methods and show that their suboptimality is caused by their locality property and the lossy aggregation step in GNNs. We further propose a straightforward and effective factorization-based explanation method to break the limitation of existing local explanation functions. We summarize our main contributions as follows.

• For the first time, we point out that the gap between the practical objective function (GIB) and high-level objective is non-negligible in the most popular post-hoc explanation framework for graph neural networks.

• We derive a generalized framework to unify existing parametric explanation methods and theoretically analyze their pitfalls in achieving accurate explanations in complicated real-life datasets. We further propose a straightforward explanation method with a solid theoretical foundation to achieve better generalization capacity.

• Comprehensive empirical studies on both synthetic and real-life datasets demonstrate that our method can consistently improve the quality of the explanations.

Preliminary

Notations and Problem Definition

A graph G is parameterized by a quadruple (,;Z,A), where i) = {v₁,v₂,...,v_n} is the node/vertex¹ set, ii) ⊆× is the edge set, iii) Z ∈ℝ^n×d is the feature matrix, where the ith row of Z, denoted by z_i ∈ℝ^1×d, is the d-dimensional feature vector associated with node v_i,i ∈ [n], and iv) the adjacency matrix A ∈{0,1}^n×n is determined by the edge set , where A_ij = 1 if (v_i,v_j) ∈, A_ij = 0, otherwise. We write |G| and || interchangeably to denote the number of edges of G.

For graph classification task, each graph G_i has a label Y _i ∈, with a GNN model f trained to classify G_i into its class, i.e., f : G{1,2,,||}. For the node classification task, each graph G_i denotes a K-hop sub-graph centered around node v_i, with a GNN model f trained to predict the label for node v_i based on the node representation of v_i learned from G_i.

Informative feature selection has been well studied in non-graph structured data (Li et al. 2017), and traditional methods, such as concrete autoencoder (Abid, Balin, and Zou 2019), can be directly extended to explain features in GNNs. In this paper, we focus on discovering important typologies. Formally, the obtained explanation G^* is characterized by a binary mask M ∈{0,1}^n×n on the adjacency matrix, e.g., G^* = (,,A ⊙M;Z), where ⊙ is elements-wise multiplication. The mask highlights components of G which influence the output of f.

Graph Information Bottleneck

The GIB principle refers to the graphical version of the Information Bottleneck (IB) principle (Tishby and Zaslavsky 2015) which offers an intuitive measure for learning dense representations. It is based on the notion that an optimal representation should contain minimal and sufficient information for the downstream prediction task. Recently, a high-level unification of several existing post hoc GNN explanation methods, such as GNNExplainer (Ying et al. 2019), and PGExplainer (Luo et al. 2020) was provided using this concept  (Wu et al. 2020; Miao, Liu, and Li 2022; Yu et al. 2021). Formally, prior works have represented the objective of finding an explanation graph G^* in G as follows:

(1)

where G^* is the explanation subgraph, γ ∈ℕ is the maximum expected size (number of edges) of the explanation, Y is the original or ground truth label, and α is a hyper-parameter capturing the trade-off between minimality and sufficiency constraints. At a high level, the GIB formulation given in equation 1 selects the minimal explanation G′, by minimizing I(G,G′) and imposing E(|G′|) ≤ γ, that inherits only the most indicative information from G to predict the label Y , by maximizing I(G′,Y ), while avoiding imposing potentially biased constraints, such the connectivity of the selected subgraphs and exact maximum size constraints (Miao, Liu, and Li 2022). Note that from the definition of mutual information, we have I(G′,Y ) = H(Y ) -H(Y |G′), where the entropy H(Y ) is static and independent of the explanation process. Thus, minimizing the mutual information between the explanation subgraph G′ and Y can be reformulated as maximizing the conditional entropy of Y given G′. That is:

(2)

Graph Information Bottleneck for Explanation

In this section, we study several pitfalls arising from the application of the GIB principle to explanation tasks. We demonstrate that, for a broad range of learning tasks, the original GIB formulation of the explainability problem has a trivial solution that does not align with the intuitive notion of explainability. We propose a modified version of the GIB principle that avoids this trivial solution and is applicable in constructing GNN explanation methods. The analytical derivations in subsequent sections will focus on this modified GIB principle. To elaborate, we argue that the optimization given in equation 2 is prone to signaling issues and, in general, does not fully align theoretically with the notion of explainability. More precisely, the GIB formulation allows for an explanation algorithm to output G^* which signals the predicted value of Y , but is independent of the input graph G otherwise. To state this more concretely, we consider the class of statistically degraded classification tasks defined in the following.

In order to show the limitations of the GIB in fully encapsulating the concept of explainability, in the sequel we focus on statistically degraded classification tasks involving graph inputs. That is, we take X = G, where G is the input graph. The next lemma shows that, for any statistically degraded task, there exists an explanation function Ψ(⋅) which optimizes the GIB objective function (equation 2), and whose output is independent of G given h(⋅). That is, although the explanation algorithm is optimal in the GIB sense, it does not provide any additional information about the input of the classifier, in addition to the information that the classifier output label h(G) readily provides.

The proof relies on the following modified data processing inequality.

The proof of Lemma 1 and Theorem 1 are included in Appendix.

As shown by Theorem 1, the original GIB formulation does not fully align with the notion of explainability. Consequently, we adopt the following modified objective function:

(3)

where Y ′≜ f(G′) is the predicted label of G′ made by the model to be explained f, and the cross-entropy CE(Y,Y ′) between the ground truth label Y and Y ′ is used in place of H(Y |G′) in the original GIB. The modified GIB avoids the signaling issues in Theorem 1, by comparing the correct label Y with the prediction output Y ′ based on the original model f(⋅). This is in contrast with the original GIB principle which measures the mutual information I(Y,G′), which provides a general measure of how well Y can be predicted from G′ (via Fano’s inequality (El Gamal and Kim 2010)), without relating this prediction to the original model f(⋅). It should be mentioned that several recent works have also adopted this modified GIB formulation (Ying et al. 2019; Luo et al. 2020). However, the rationale provided in these earlier studies was that the modified GIB serves as a computationally efficient approximation for the original GIB, rather than addressing the limitations of the original GIB shown in Theorem 1.

K-FactExplainer for Graph Neural Networks

In this section, we first theoretically show that existing parametric explainers based on the GIB objective, such as PGExplainer (Luo et al. 2020), are subject to two sources of inaccuracies: locality and lossy aggregation. Then we propose a straightforward and effective approach to mitigating the problem. In the subsequent sections, we provide simulation results that corroborate these theoretical predictions.

Theoretical Analysis

We first define the general class of local explanation methods.

The first condition in Definition 3 requires that the presence of each vertex v in the explanation G′ only depends on its neighboring vertices in G which are within its r local neighborhood. The second condition requires that G′ be a subgraph of G. It is straightforward to show that various explanation methods such as PGExplainer are local explanation methods due to the boundedness of their corresponding computation graphs. This is formalized in the following proposition.

Next, we argue that local explanation methods cannot be optimal in the modified GIB sense for various classification tasks. Furthermore, we argue that this issue may be mitigated by the addition of a hyperparameter k as described in subsequent sections in the context of the K-FactExplainer.

To provide concrete analytical arguments, we focus on a specific graph classification task, where the class labels are binary, the input graph has binary-valued edges, and the output label is a function of a set of indicator motifs. To elaborate, we assume that the label to be predicted is Y = max{E₁,E₂,,E_s}, where E_i,i ∈ [s] are Bernoulli variables, and if E_i = 1, then g_i ⊆ G for some fixed subgraphs g_i,i ∈ [s]. In the explainability literature, each of the subgraphs g_i,i ∈ [s] is called a motif for label Y = 1. Let us define G_e = ⋃ _i∈[s]g_i1(E_i = 1). So that G_e is the union of all the edges in the motifs that are present in G, and it is empty if Y = 0. Formally, the classification task under consideration is characterized by the following joint distribution:

(4)

where e^s ∈{0,1}^s, g_e ≜⋃ _i∈[s]g_i1(e_i = 1), and G₀ is the “irrelevant” edges in G with respect to the label Y .

In graph classification tasks characterized by equation 4, if the label of G is one, then at least one of the motifs is present in G. Note that the reverse may not be true as the motifs may randomly appear in the ‘irrelevant’ graph G₀ due to its probabilistic nature. A natural choice for the explanation function Ψ(⋅) of a classifier f(⋅) for this task is one which outputs one of the motifs present in G if f(G) = 1. For instance, in the MUTAG classification task, an explainer should output NH₂ or NO₂ subgraphs if the output label is equal to one. In the following, we argue that, in classification tasks involving more than one motif local explanation methods cannot produce the motifs accurately. Hence their output does not align with the natural explanation outlined above and is not optimal in the modified GIB sense. To make the result concrete, we further make the following simplifying assumptions:

i) The graph G₀ is Erdös-Rényi with parameter p ∈ (0,):

ii) There exists r,r′ > 0 such that the geodisc radius and geodisc diameter of g_i are less than or equal to r and r′, respectively, for all i ∈ [s].

iii) The geodisc distance between g_i and g_j is greater than r for all i≠j.

iv) E_i,i ∈ [s] are jointly independent Bernoulli variables with parameter p_i, where P_G0(g_i) ≤ p_i.

The proof of Theorem 2 is provided in the Appendix.

Figure 1: Illustration of K-FactExplainer method. Starting from the left, the node embeddings for graph G are produced using the original GNN. The edge embeddings and graph embedding are produced by concatenating the node embeddings. The MLP Ψ₀ assigns weight to the outputs of PGExplainer MLPs Ψ_t,t ∈ [k]. The resulting vector of edge probabilities Ω ≜ (∑ _t=1^kp_tω_i,j^t)_i,j∈[n] is used to produce the sampled explanation graph G^*. The explanation is fed to the original GNN and the output label is compared with the original prediction. The training proceeds by minimizing the cross-entropy term CE(Y ′,), where is GNN prediction for the original input graph G.

Theorem 2 can be interpreted as follows: for graph classification tasks with more than one motif, although local explanation methods are not optimal in general, one can “patch” together several local explanation methods Ψ₁(⋅),Ψ₂(⋅),,Ψ_k(⋅) into an explanation method Ψ^*(⋅), such that i) for any given input g, the output of Ψ^*(g) is equal to the output of one of the explanation functions Ψ₁(g),Ψ₂(g),,Ψ_k(g), and ii) Ψ^*(⋅) is optimal in the modified GIB sense. This insight motivates the K-FactExplainer method introduced in the following section.

K-FactExplainer and a Bootstrapping Algorithm

Motivated by the insights gained by the analytical results in the previous section, we propose a new graph explanation method. An overview of the proposed method is shown in Figure 1. To describe the method, let f(⋅) be the GNN which we wish to explain. Let Z_i,i ∈ [n] denote the node embedding for node v_i,i ∈ [n] produced by f(⋅). We construct the edge embeddings Z_i,j = (Z_i,Z_j),i,j ∈ [n] and graph embedding Z = (Z_i,i ∈ [n]) by concatenating the edge embeddings. Let k ∈ℕ be the upper-bound on the number of necessary local explainers from Theorem 2. We consider k multi-layer neural networks (MLPs) denoted by Ψ_t,t ∈ [k]. Each MLP Ψ_t individually operates in a similar fashion as the MLP used in the PGExplainer method. That is, Ψ_t operates on each edge embedding (Z_i,Z_j) individually, and outputs a Bernoulli parameter ω_i,j^t ∈ [0,1]. The parameter ω_i,j^t ∈ [0,1] can be viewed as the probability that the edge (v_i,v_j) is in the sampled explanation graph. Based on the insights provided by Theorem 2, we wish to patch together the outputs of Ψ_t,t ∈ [k] to overcome the locality issue in explaining GNNs in multi-motif classification tasks. This is achieved by including the additional MLP Ψ₀ which takes the graph embedding Z as input and outputs the probability distribution P_K on the alphabet [k]. At a high level, the MLP Ψ₀ provides a global view of the input graph, whereas each of the Ψ_t,t ∈ [k] MLPs provide a local perspective of the input graph. The outputs (ω_i,j^t)_i,j∈[n] of Ψ_t are linearly combined with weights associated with P_K(t),t ∈ [k] and the resulting vector of Bernoulli probabilities Ω = (∑ _t=1^kP_K(t)ω_i,j^t)_i,j∈[n] is used to sample the edges of the input graph G and produce the explanation graph G^*. In the training phase, G^* is fed to f(⋅) to produce the prediction Y ′. Training is performed by minimizing the cross-entropy term CE(Y ′,), where = f(G) is the label prediction of the GNN given input G. The next proposition provides an algorithm to bound the value of k, which determines the number of MLPs which need to be trained.

The proof of Proposition 2 is provided in the Appendix.

Proposition 2 provides a method to find an upper-bound on k; however, it requires that the motifs be known beforehand, so that G_e is known and the size of its minimal cover can be computed. In practice, we do not know the motifs before the start of the explanation process, since the explanation task would be trivial otherwise. We provide an approximate solution, where instead of finding the minimal cover for G_e, we use a bootstrapping method in which we find the minimal cover for the explanation graphs produced by another pre-trained explainer, e.g., a PGExplainer. To elaborate, It takes the GNN model to be explained f, a set of training input graphs G, and a post-hoc explainer Ψ as input. In our simulations, we adopt PGExplainer as the post-hoc explainer Ψ. Other explanation methods such as GNNExplainer (Ying et al. 2019) can also be used in this step. For each graph G ∈G, we first apply the explainer Ψ on G to get the initial explanation graph, whose nodes are listed in V_e and edge mask matrix is denoted by M. This is used as an estimate for G_e. To find its minimal cover, we rank the nodes in V_e based on their degrees and initialize k′ = 0. For each step, we select a node v from V_e and extract its k^*-hop neighborhood graph, G_v^(l). Then, we remove all nodes in G_v^(l) from V_e. After that, we add a count to k′ and select the next node in V_e until |V_e| = 0. We iterate all graphs in G and report the maximum value of k′ as , the estimate of k. A detailed algorithm can be found in Appendix.

Related Work

Graph neural networks (GNNs) have gained increasing attention in recent years due to the need for analyzing graph data structures (Kipf and Welling 2017; Veličković et al. 2018; Xu et al. 2019; Feng et al. 2020; Satorras, Hoogeboom, and Welling 2021; Bouritsas et al. 2022). In general, GNNs model messages from node representations and then propagate messages with message-passing mechanisms to update representations. GNNs have been successfully applied in various graph mining tasks, such as node classification (Kipf and Welling 2017), link prediction (Zhang and Chen 2018), and graph classification (Xu et al. 2019). Despite their popularity, akin to other deep learning methodologies, GNNs operate as black box models, which means their functioning can be hard to comprehend, even when the message passing techniques and parameters used are known. Furthermore, GNNs stand apart from conventional deep neural networks that assume instances are identically and independently distributed. GNNs instead integrate node features with graph topology, which complicates the interpretability issue.

Recent studies have aimed to interpret GNN models and offer explanations for their predictions (Ying et al. 2019; Luo et al. 2020; Yuan et al. 2020, 2022, 2021; Lin, Lan, and Li 2021; Wang and Shen 2023; Miao et al. 2023; Fang et al. 2023; Ma et al. 2022; Zhang, Luo, and Wei 2023). These methods generally fall into two categories based on granularity: i) instance-level explanation (Ying et al. 2019; Zhang et al. 2022), which explains predictions for each instance by identifying significant substructures; and ii) model-level explanation (Yuan et al. 2020; Wang and Shen 2023; Azzolin et al. 2023), designed to understand global decision rules incorporated by the target GNN. Among these methods, Post-hoc explanation ones (Ying et al. 2019; Luo et al. 2020; Yuan et al. 2021), which employ another model or approach to explain a target GNN. Post-hoc explanations have the advantage of being model-agnostic, meaning they can be applied to a variety of GNNs. Therefore, our work focuses on post-hoc instance-level explanations (Ying et al. 2019), that is, identifying crucial instance-wise substructures for each input to explain the prediction using a trained GNN model. A detailed survey can be found in  (Yuan et al. 2022).

Experimental Study

In this section, we empirically verify the effectiveness and efficiency of the proposed K-FactExplainer by explaining both node and graph classifications. We also conduct extensive studies to verify our theoretical claims. Due to the space limitation, detailed experimental setups, full experimental results, and extensive experiments are presented in Appendix.

Experimental Setup.

We compare our method with representative GIB-based explanation methods, GNNExplainer (Ying et al. 2019) and PGExplainer (Luo et al. 2020), classic explanation methods, GRAD (Ying et al. 2019) and ATT (Veličković et al. 2018), and SOTA methods, RG-Explainer (Shan et al. 2021) and DEGREE  (Feng et al. 2022). We follow the routinely adopted framework to set up our experiments (Ying et al. 2019; Luo et al. 2020). Six benchmark datasets with ground truth explanations are used for evaluation, with BA-Shapes, BA-Community, Tree-Circles, and Tree-Grid (Ying et al. 2019) for the node classification task, and BA-2motifs (Luo et al. 2020) and MUTAG (Debnath et al. 1991) for the graph classification task. For each dataset, we train a graph neural network model to perform the node or graph classification task. Each model is a three-layer GNN with a hidden size of 20, followed by an MLP that maps these embeddings to the number of classes. After training the model, we apply the K-FactExplainer and the baseline methods to generate explanations for both node and graph instances. For each experiment, we conduct 10 times with random parameter initialization and report the average results as well as the standard deviation. Detailed experimental setups are put in the appendix.

Quantitative Evaluation

Comparison to Baselines.

We adopted the well-established experimental framework (Ying et al. 2019; Luo et al. 2020; Shan et al. 2021), where the explanation problem is framed as a binary classification of edges. Within this setup, edges situated inside motifs are regarded as positive edges, while all others are treated as negative. The importance weights offered by the explanation methods are treated as prediction scores. An effective explanation method, therefore, would assign higher weights to edges located within the ground truth motifs as opposed to those outside. To quantitatively evaluate the performance of these methods, we employed AUC as our metric. The average AUC scores and the associated standard deviations are reported in Table 1. We observe that with a manually selected value for k, K-FactExplainer consistently outperforms GNNExplainer and PGExplainer and competes with high-performing models like RGExplainer and DEGREE. The comparison demonstrates that our K-FactExplainer considers locality, providing more accurate, comprehensive explanations and mitigating common locality pitfalls seen in other models.

Model Analysis

Effectiveness of Bootstrapping Algorithm.

To directly show the effects of k in K-FactExplainer . We change the value of k from 1 to 60 and show the resulting performance in Table 2. We observe that, in general, a higher value of k leads to improved performance. The reason is that large k in K-FactExplainer mitigates the locality and lossy aggregation losses in parametric explainers as discussed previously. We use an underline to indicate the upper-bound for the value of k suggested by the bootstrap algorithm in Section 0.0. It should be noted that this upper-bound is particularly relevant to multi-motif scenarios considered in Theorem 2. Restricting to values of k that are less than or equal to the suggested upper-bound achieves the best performance in the multi-motif MUTAG task, which is aligned with our theoretical analysis.

Effects of Lossy Aggregation.

To evaluate the effects of lossy aggregation, we consider the BA-Community and Tree-Cycles in this part. As shown in Table 2, K-FactExplainer significantly outperforms PGExplainer. The reason is that the K-FactExplainer partially mitigates the aggregation loss in GNN explanation methods by combining the outputs of multiple MLPs, hence combining multiple ‘weak’ explainers into a stronger one. In addition, we observe that the performances of K-FactExplainer are positively related to k. Next, we increase the dimensionality of hidden representation in the GNN model from 20 to 80. This reduces the loss in aggregation as at each layer several low dimensional vectors are mapped to high dimensional vectors. The explanation performances are shown in Table 3. For these two datasets, the performance improves as k is increased when the dimension is 20, due to the mitigation of the aggregation loss, however, as expected, no improvement is observed when increasing k in explaining the GNN with dimension 80, since there is no significant aggregation loss to mitigate in that case.

Conclusion

In this work, we theoretically investigate the trivial solution problem in the popular objective function for explaining GNNs, which is largely overlooked by the existing post-hoc instance-level explanation approaches. We point out that the trivial solution is caused by the signal problem and propose a new GIB objective with a theoretical guarantee. On top of that, we further investigate the locality and lossy aggregation issues in existing parametric explainers and show that most of them can be unified within the local explanation Methods, which are weak at handling real-world graphs, where the mapping between labels and motifs is one-to-many. We propose a new factorization-based explanation model to address these issues. Comprehensive experiments are conducted to verify the effectiveness of the proposed method.

Acknowledgments

This project was partially supported by NSF grants IIS-2331908 and CCF-2241057. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

References

Appendix

Proofs

Proof of Lemma 1

Note that from the data processing inequality and B ↔ C ↔ A′, we have:

Also, from P_A|C = P_A′|C, we have:

Lastly, from A ↔ B ↔ C, we have:

Combining these three results, we get:

__

Proof of Theorem 1

Let us define γ_α ≜ min_G′I(G,G′) + αH(Y |G′), and let G_α^* be an explanation achieving γ_α. Define G′_α as a random graph generated conditioned on h(G) such that P_G′α|h(G) = P_Gα^*|h(G) and the Markov chain G,G_α^* ↔ h(G) ↔ G′_α holds. It can be observed that by construction the conditions in Lemma 1 are satisfied for A ≜ G_α^*,A′≜ G′_α,B ≜ G and C ≜ h(G). Hence, we have I(G′_α,G) ≤ I(G_α^*,G). As a result:

γα = I(G,Gα*) + αH(Y |G α*)	I(G,G′α) + αH(Y |Gα*)
	I(G,G′α) + αH(Y |G′α)

where in (a) follows from I(G′_α,G) ≤ I(G_α^*,G) and (b) follows from the fact that the task is statistically degraded, the Markov chain G_α^*G′_α ↔ h(G) ↔ Y and P_Gα^*|h(G) = P_G′α|h(G). Consequently, G′_α is also an optimal explanation in the GIB sense, i.e. achieves γ_α. The proof is completed by defining the explanation function as Ψ_α(G) = G′_α. __

Proof of Theorem 2

Part a): Note that the optimal Bayes classifier rule is given by f^*(g) = arg max_y∈{0,1}P(y|G = g). If ∄i ∈ [s] : g_i ⊆ g, then P(Y = 1|G = g) = 0 and hence f^*(g) = 0 as desired. So, it suffices to show that if ∃i ∈ [s] : g_i ⊆ g, then P(Y = 1|G = g) > P(Y = 0|G = g). Let = {i ∈ [s]|g_i ⊆ g}. Note that

Also,

P(G = g,Y = 1)	∏ i∈P(gi ⊆ Ge)P(g -∪i∈gi ⊆ G0 ⊆ g)
	(∏ i∈pi)P(g -∪i∈gi ⊆ G0 ⊆ g)	(5)

where (a) follows from the facts that i) if all indicator motifs are equal to one then Y = 1, ii) the indicator motifs are independent of each other, and iii) G_e and G₀ are independent of each other, and (b) follows from the fact that the indicator motifs are Bernoulli variables with parameters p_i,i ∈ [s]. On the other hand:

	P(G = g,Y = 0)P(G0 = g)
	∏ i∈P(gi ⊆ G0)P(g -∪i∈gi = G0 -∪i∈gi),

where (a) follows from the fact that if Y = 1 all indicator motifs are equal to zero, and in (b) we have used the fact that the graph G₀ is Erdös-Rényi, and the motif subgraphs do not overlap. So,

P(G = g,Y = 0) ≤ (∏ i∈pi)P(g -∪i∈gi ⊆ G0 ⊆ g),

(6)

where we have used the fact that from condition iv) in the problem formulation, we have P(g_i ⊆ G₀) ≤ p_i,i ∈ [s]. Combining equation 5 and equation 6 completes the proof of a).
Part b): We provide an outline of the proof. It can be observed that as α →∞, the optimal explanation algorithm in the modified GIB sense is the one that minimized the cross-entropy term CE(Y,Y ′). We argue that the optimal explanation algorithm outputs one of the motifs present in g if Y = 1. The reasons is that in this case, f^*(g) = f^*(Ψ(g)) for all input graphs g, and the cross-entropy term is minimized by the assumption that f^* is the optimal Bayes classifier rule.

Next, we argue that an r-local explanation method cannot produce the optimal explanation. The reason is that due to condition ii) and iii) in the problem formulation and definition of r-local explanation methods, the probability that an edge in a given motif is included in the explanation only depends on the presence of the corresponding motif in graph g and not the presence of the other motifs. To see this, let p_j,j′ be the probability that the edge (v_j,v_j′) in motif g_i ⊆ g is included in the explanation Ψ(g). Then, by linearity of expectation, we have:

So, we must have:

Consequently, the r-local explanation method cannot output one of the motifs present in g with probability one since the edge probabilities p_j,j′ cannot be equal to one as their summation should be less than γ. This completes the proof of part b).
Part c): We construct an optimal explainer as follows. Let k = s and define Ψ_i(g) ≜ g_i1(g_i ∈ g). Furthermore, define the explainer Ψ^*(g) ≜ arg min_gi,i∈[s]{i|g_i ⊆ g}. Then, since for Y = 1, the output of Ψ^* is a motif that is present in the input graph, as explained in the proof of Part b), Ψ(g) is an optimal explanation function in the modified GIB sense as α →∞ as it yields the minimum cross-entropy term. Furthermore, Ψ(g) ∈{Ψ₁(g),Ψ₂(g),,Ψ_k(g)} by construction. This completes the proof. __

Proof of Proposition 2

Following the arguments in the proof of Theorem 2, it suffices to show that there exist Ψ_t,t ∈ [k^*] and Ψ(⋅) ∈{Ψ₁(⋅),Ψ₂(⋅),,Ψ_k^*(⋅)}, such that Ψ(g) is equal to a motif that is present in g whenever Y = 1. To construct such an explainer, let P = {_t,t ∈ [k^*]} be the minimal k^*-cover of G_e, and let g_i^* be the motif in the input graph with the smallest index among all motifs present in the input graph. We take Ψ_t,t ∈ [k^*] to be such that it assigns sampling probability one to the edges in _t belonging to the motif g_i in the input graph with the smallest index among all motifs whose edges overlap with _t and sampling probability zero to every other edge, i.e. it outputs the motif with the smallest index in its computation graph with probability one. Let Ψ₀ be such that it assigns probability one to an Ψ_t,t ∈ [k^*] for which _t overlaps with g_i^* and zero to all other Ψ_t. Then, it is straightforward to see that the resulting sampled graph from K-FactExplainer G^* would be equal to the motif with the smallest index among the motifs present in the input graph g_i^*. This completes the proof. __

Algorithm

The detailed algorithm for Bootstrapping is shown in Alg. 1.

---

Algorithm 1: Bootstrapping Algorithm to Bound the Number of MLPs

Require:  the GNN model to be explained, f, a set of graphs G, an explainer Ψ. 1:  ← 0.
2:  for each graph G = (,,X,A) ∈G do
3:  M ← Ψ(f,G) # get a mask of edges by applying g to explain f on G.
4:  m ← # get all node in the explanation graphs.
5:  V_e ←{v_i|m_i > 0} # get all node in the explanation graphs.
6:  Rank the nodes in V_e according to their degrees/betweenness.
7:  k′← 0
8:  while V_e is not empty do
9:  get a node v from V_e with smallest degree;
10:  G_v^(l) ← l-hop neighborhood graph with v.
11:  remove nodes of G_v^(l) from V_e
12:  k′← k′ + 1
13:  end while
14:  ← max(k′,).
15:  end for
16:  return  

---

Detailed Experimental Setups

Experimental Setup

In the experimental study, we first describe the synthetic and real-world datasets used for experiments, baseline methods, and experimental setup. After qualitative and quantitative analysis, we demonstrate that the K-FactExplainer is effective for explaining both node and graph instances, and it outperforms state-of-the-art explanation methods in various scenarios. We attribute the gains of K-FactExplainer to the mitigation of two types of performance losses, which were studied analytically in prior sections, namely, lossy aggregation and locality.

As mentioned in Remark 5, the first type of loss, aggregation loss, is due to the fact that the aggregator function at each layer of the GNN is not one-to-one, and hence loses information. This is particularly true if the mid-layers of the GNN have similar (low) dimensions. The second type of loss, the locality loss, manifests in multi-motif scenarios as shown in Theorem 2. In order to study each of these types of losses in isolation, we first focus on single-motif tasks and study lossy aggregation, then, we focus on multi-motif tasks and study the locality loss.

To prove that the explainer’s performance gains in single-motif tasks are indeed due to the mitigation of aggregation loss, it suffices to show that if the lossy aggregator is replaced by a (almost) lossless aggregator, the performance gains vanish. One can construct a GNN with almost lossless aggregation by choosing the dimensionality of the layers of the GNN to be sequentially increasing. Hence, to demonstrate our claim, we consider several single-motif classification tasks and show that increasing the hyperparameter k leads to performance gains if the GNN has similar low-dimensional mid-layers, whereas if the layers increase in dimension sequentially, no performance gain is observed when increasing k, thus confirming the hypothesis that the K-FactExplainer gains in single-motif scenarios are indeed due to lossy aggregation. To demonstrate the fact that the K-FactExplainer mitigates the locality loss suffered by conventional local explainers, we consider several multi-motif classification tasks, and show that the explainer’s accuracy increases as k is increased in accordance with the analytical results of Theorem 2 and Algorithm 1.

Datasets.

Six benchmark datasets are used for evaluation, with BA-Shapes, BA-Community, Tree-Circles, and Tree-Grid (Ying et al. 2019) for the node classification task, and BA-2motifs (Luo et al. 2020) and MUTAG (Debnath et al. 1991) for the graph classification task. BA-Shapesis a dataset generated using the Barabási-Albert (BA) graph randomly attached with “house”-structured network motifs. BA-Community, also generated using the BA model, focuses on community structures within the graph, with nodes connected based on a preferential attachment model. Tree-Circlesis a dataset where cycle structures are embedded within trees, created by introducing cycles by connecting nodes in the trees. Lastly, Tree-Gridis a dataset that combines tree and grid structures by embedding grid structures within trees. MUTAG is a real-world dataset that comprises chemical compound graphs, where each graph represents a chemical compound, and the task is to predict whether the compound is mutagenic or not. These synthetic and real datasets allow us to evaluate the performance of the K-FactExplainer and baseline methods in controlled settings, providing insights into their effectiveness and interpretability for node classification tasks.

Baselines.

To assess the effectiveness of the proposed framework, we compare our method with representative GIB-based explanation methods, GNNExplainer (Ying et al. 2019) and PGExplainer (Luo et al. 2020). We also include other types of explanation methods, RG-Explainer (Shan et al. 2021) and DEGREE  (Feng et al. 2022), GRAD (Ying et al. 2019), and ATT (Veličković et al. 2018) for comparison. Specifically, GRAD computes gradients of GNN’s objective function w.r.t. each edge for its importance score. (2) ATT averages the edge attention weights across all layers to compute the edge weights. (3) GNNExplainer (Ying et al. 2019) is a post-hoc method, which provides explanations for every single instance by learning an edge mask for the edges in the graph. The weight of the edge could be treated as important. (4) PGExplainer (Luo et al. 2020) extends GNNExplainer by adopting a deep neural network to parameterize the generation process of explanations, which enables PGExplainer to explain the graphs in a global view. It also generates the substructure graph explanation with the edge importance mask. (5) RGExplainer (Shan et al. 2021) is an RL-enhanced explainer for GNN, which constructs the explanation subgraph by starting from a seed and sequentially adding nodes with an RL agent. (6) DEGREE  (Feng et al. 2022) is a decomposition-based approach that monitors the feedforward propagation process in order to trace the contributions of specific elements from the input graph to the final prediction.

For each dataset, we train a graph neural network model to perform the node or graph classification task. Each model is a three-layer GNN with a hidden size of 20, followed by an MLP that maps these embeddings to the number of classes. After training the model, we apply the K-FactExplainer and the baseline methods to generate explanations for both node and graph instances. For each experiment, we conduct 10 times with random parameter initialization and report the average results as well as the standard deviation.

Extra Experiments

Model Analysis

Effects of Locality in Multi-motif Tasks. So far, we have illustrated the gains due to the mitigation of the locality loss by considering the multi-motif MUTAG classification task (Table 1). To further empirically demonstrate these gains, in this section, we introduce a new graph classification dataset, BA-4motifs which includes 1000 stochastically generated graphs. The generation process follows the procedure described in equation 4. That is, for each graph, we first generate a base graph g₀ according to the BA model. Then, the graph is assigned a binary label randomly and uniformly (by generating E^s, the indicators of different motifs). Each label is associated with two motifs. The motif graph (g_e in equation 4) is generated based on E^s, and finally the graph g is produced by taking the union of g₀ and g_e.

As shown in Theorem 2, assuming that the classifier to be explained has optimal performance, the optimal explainer (in the modified GIB sense) outputs one of the motifs that are present in the graph. Consequently, we define the motif coverage rate (CR) as a measure of the performance of the explainer as follows. Recall that the explainer assigns a probability of being part of the explanation to each of the graph edges, e.g., the probability vector Ω in Figure 1. Let _r denote the r top-ranked edges in terms of probability of being part of the explanation, where r is the maximum motif size. For each motif g_i ∈ g with edge set _i, we define its coverage rate as CR_i ≜, i.e., the fraction of the motif’s edges that are top-ranked. The CR is defined as max_iCR_i, the maximum of coverage rate among all motifs. Table  4 shows that with more complex datasets, our method will significantly improve the faithfulness of the explanation in terms of coverage rate.

(a) Base BA-graph

(b) Motifs in Label 0

(c) Motifs in Label 1

Figure 2: Visualization of BA-4motifs dataset. A BA-graph is used as the base graph. Each label is associated with two motifs.

Efficiency Analysis

The proposed method comprises networks capable of generating inductive explanations for new instances across a population. Following (Luo et al. 2020), we measure the inference time, which is the time needed to explain a new instance with a trained model. Table 5 presents the running time for K-FactExplainer with various K values. The results indicate that the inference time of K-FactExplainer is comparably similar to that of the PGExplainer, which is one of the most sufficient explanation techniques.

Qualitative evaluation

We selected an instance to visually demonstrate the explanations given by GNNExplainer, PGExplainer, and K-FactExplainer in Table  6.

	Node Classification				Graph Classification
	BA-Shapes	BA-Community	Tree-Cycles	Tree-Grid	BA-2Motifs	MUTAG	BA-4Motifs
GNNExplainer
PGExplainer
K-FactExplainer
Motifs

Table 6: Qualitative Analysis