Towards Comprehensive and Prerequisite-Free Explainer for Graph Neural Networks

1 Introduction

Graph neural networks (GNNs), known for their capability to learn complex relational patterns in graphs, have gained significant attention and been widely applied in critical fields such as finance [Zhang et al., 2022; Xu et al., 2024] and healthcare [Golmaei and Luo, 2021]. For example, in healthcare, GNNs can utilize information from patients and others with similar conditions to offer medical recommendations [Min et al., 2024]. However, because users in these fields require reliable and accurate GNN predictions, the lack of transparency in the decision logic of GNNs has raised significant concerns about the credibility of GNN predictions. To address these concerns, the field of explainability of GNNs (XGNN) has emerged to enhance the transparency of the decision logic of GNNs and build up users' trust in GNN predictions. Existing XGNN methods [Ying et al., 2019; Yuan et al., 2020; Vu and Thai, 2020] typically perturb the input graph structures to influence GNN predictions and extract the key subgraphs (a.k.a., explanation subgraphs) that are most critical to support these predictions. These subgraphs are expected to represent the decision logic of GNNs to a certain extent, thereby effectively enhancing the predictions' reliability.

∗Corresponding author

However, existing XGNN methods face two major limitations in real-world scenarios. Limitation 1 (Incomplete Decision Logic): Existing methods fail to capture the complete decision logic of GNNs across diverse distributions in the entire dataset's sample space, which overall may consist of all possible graph structures. These methods assume that the testing dataset (testing samples in the entire dataset) follows the same distribution as the training dataset (a.k.a., IID scenario) and focus solely on extracting the decision logic of GNNs in the training dataset. However, in real-world applications, out-of-distribution (OOD) scenarios are more prevalent [Koch et al., 2024; Koch et al., 2022], where the testing dataset's distribution differs from that of the training dataset. In such cases, existing XGNN methods fail to provide reliable explanations because they focus either on OOD explanations that have different distributions from the training dataset or on the IID scenario. This limitation raises the demand of a novel comprehensive GNN explainer, which needs to capture the complete decision logic of the target GNN across diverse distributions in the entire dataset's sample space and thus can: (1) generate reliable explanations in OOD scenarios, (2) help identify flaws in GNN decision logic when prediction errors occur, and (3) support GNN design improvements to mitigate errors in OOD scenarios. Limitation 2 (Strict Prerequisites): Existing XGNN methods rely on strict prerequisites to achieve good performance, which can be divided into two aspects: (1) Most methods require GNN internal accessibility to extract the decision logic of GNNs. However, privacy protection laws and regulations often restrict such access, making these methods impractical for privacy-sensitive applications [Miller et al., 2020]; (2) Several recent methods [Wang and Shen, 2023; Chen et al., 2024b] generate learnable edge weights and require GNNs to use these weights for weighted message propagation. However, in critical fields like finance and healthcare, edge features (e.g., stock investment shares in finance and co-occurrence frequency of medical services in healthcare) are used to enhance data representation [Li et al., 2022; Xiong et al., 2021; Zhu et al., 2023]. These edge features differ from learnable edge weights in both semantics and data formats, yet they share the same position in the input graph. Thus, these XGNN methods impose a prerequisite on dataset properties, requiring that datasets do not contain edge features.

To address the abovementioned two major limitations in existing XGNN methods, we propose OPEN, a novel cOmprehensive and Prerequisite-free Explainer for graph Neural networks. Specifically, we propose the Non-Parametric Analysis Framework (NPAF), which infers the entire dataset's sample space from the training dataset samples and partitions this space into multiple environments. In addition, we propose the Graph Variational Generator (GVAG), which determines the sampling probabilities of graph structures by generating a large number of subgraphs in each environment during the training stage and analyzing their predictions. This enables GVAG to uncover the decision logic of the GNNs across a wide range of distributions in the sample space. To further enhance this uncovering process, GVAG incorporates node embeddings from other environments to actively construct OOD data. Compared to existing methods, OPEN can capture nearly complete decision logic of the GNNs, effectively addressing Limitation 1. Moreover, GVAG learns the correlations between embeddings and structure sampling probabilities, and directly samples explanation subgraphs from the sample space without accessing GNN internals or using edge weights, thereby eliminating the prerequisites required by existing methods and overcoming Limitation 2.

We summarize our main contributions as follows: (1) We identify two major limitations in XGNN: (a) its inability to capture the complete decision logic, and (b) the strict prerequisites imposed on target GNNs and datasets. These limitations significantly impact XGNN research, highlighting the need for effective solutions; (2) We propose OPEN, a framework that infers and partitions the sample space of the entire dataset, enabling the exploration of the decision logic of GNNs across diverse distributions. In addition, OPEN learns the decision logic by sampling a large number of subgraphs and analyzing their predictions. This approach not only captures a more comprehensive decision logic than existing methods, but also removes the required strict prerequisites; and (3) Comprehensive experimental results demonstrate that OPEN not only effectively extracts explanation subgraphs in prerequisite-free scenarios where most existing methods are inapplicable, but also outperforms state-of-the-art (SOTA) methods in prerequisitesatisfied scenarios. OPEN efficiently generates reliable and accurate explanations across various distributions, showcasing its adaptability to real-world applications.

2 RelatedWork

XGNN. The XGNN methods are initially inspired by computer vision techniques like Grad-CAM [Pope et al., 2019], and some methods also benefit from the explanatory power of GNN attention mechanisms [Veliˇckovi´c et al., 2018]. The introduction of GNNExplainer [Ying et al., 2019] marked a shift towards perturbing graph structures to weight message propagation along edges and extracting explanation subgraphs based on changes in GNN outputs, as demonstrated by later advancements [Qiu et al., 2024; Chen et al., 2024b; Chen et al., 2024a]. However, most existing methods rely on strict prerequisites to enable graph structure perturbation, which often restricts their practicality in real-world scenarios. Techniques like PGExplainer [Luo et al., 2020] enhance the understanding of how node embeddings correlate with node presence in explanation subgraphs, facilitating explanations post-learning without the need for fitting new instances [Zhang et al., 2023]. Nevertheless, these methods focus on learning the decision logic in the training dataset and thus fail to mine the complete decision logic of target GNNs, which causes them to provide unrelated explanations when the distribution of the input graph is different from that of the training dataset.

OOD Scenarios in XGNN. In the XGNN field, critiques [Chen et al., 2023; Chen et al., 2024b; Fang et al., 2024a; Kubo and Difallah, 2024; Fang et al., 2024b] note that traditional methods generate OOD explanations, arguing that these explanations fail to accurately reflect the decision logic of GNNs. To address this issue, they propose generating explanations that align with the training dataset's distribution. However, this further aggravates the performance degradation of these methods in OOD scenarios. Some argue that an XGNN method only needs to be faithful to the decision logic of a well-trained GNN in the training dataset's distribution, and does not need to uncover the reasoning behind incorrect predictions in OOD scenarios. However, such opinion not only significantly limits the practical use of XGNN in critical fields where OOD scenarios are prevalent, but also prevents XGNN from contributing to improvements in GNN design.

3 Preliminaries

Structural Causal Models (SCMs). Following prior works [Ahuja et al., 2021; Chen et al., 2022; Ding et al., 2025], SCMs are used to delineate causal relationships among variables. Fig. 1 demonstrates three typical distribution shift assumptions in SCMs: Covariate, Fully Informative Invariant Features (FIIF), and Partially Informative Invariant Features (PIIF). Specifically, we propose a Non-assumption SCM (shown in Fig. 1 (d)), which primarily explores potential causal relationships among variables Gc, Y , and Gs. We can find that relying solely on Y and G is insufficient for precise causal analysis among these variables. Therefore, we perform direct statistical analyses to deduce environmental variables E and identify variables with distinct causal relationships to either Y or E, effectively isolating relevant subsets of Gc and Gs and reducing the impact of spurious correlations. In addition, the target GNN M has causal relationships with both G and Y , indicating that when an XGNN method explains M's output, M opens a backdoor path between the XGNN method and Y . Therefore, XGNN methods also learn the relationships between Y and Gc, and are susceptible to OOD scenarios.

Problem Definition. We focus on providing post-hoc instance-level explanations. Given a graph G = (V, E,X) where V denotes the vertices, E denotes the edges, and X is the node features, the target problem is defined as follows:

Definition 1 (Mining complete decision logic of GNNs). Given a GNN model M trained on the training dataset Dtrain, consider an unseen testing dataset Dtest where graphs exhibit distribution shifts from those in Dtrain. For each G ∈ Dtest, the objective is to identify an explanation subgraph Gc ⊆ G that effectively elucidates the predictions made by M.

Meanwhile, to eliminate the required prerequisites, we will not use learnable edge weights or access the GNN internal.

4 Methodology of OPEN

In this section, we present a novel framework, comprehensive and prerequisite-free explainer for GNNs (OPEN). Fig. 2 depicts the overview of OPEN. A summary of all symbols used in this paper is provided in Appendix A.1. OPEN uses the NonParametric Analysis Framework (NPAF) to analyze potential environments in the entire dataset's sample space, based on training dataset samples. NPAF employs statistical methods following the non-assumption SCM and assigns environmental labels to the graphs in the training dataset. Next, NodeVAE and the Graph Variational Generator (GVAG) generate node and graph invariant embeddings in each environment, respectively. GVAG then samples explanation subgraphs from the sample space based on these invariant embeddings. OPEN adjusts the sampling probability of explanations by comparing the predictions, thus uncovering the decision logic of GNNs. 1

4.1 NPAF for Environmental Label Inference

Taking the graph classification task as an example, NPAF determines the potential environmental label for each graph Gi ∈ Dtrain through the following procedure.

Obtain Structure-Based Embedding. NPAF leverages structure-based embeddings to infer environmental labels from the structural aspects of the training dataset. To generate these embeddings, we gather relevant structural information from the training dataset, such as node degrees and node categories.

1 Appendix can be found at https://github.com/zh2209645/OPEN

Using these details, we construct structure-based node features Xstr and apply a Weisfeiler Leman (WL) kernel-based GNNs [Togninalli et al., 2019] to derive the structure-based embeddings for nodes Hstr. We then employ pooling layers to extract the structure-based embedding hG,i ∈ HG for Gi.

Infer Potential Environmental Label Based on Structure. We infer potential environmental labels for graphs based on a commonly adopted assumption in this field [Wu et al., 2021; Chen et al., 2022], which states that a graph can be divided into two independent components: Gc, associated with the label Y , and Gs, influenced by the environment variable E. Graphs affected by the same E are expected to share similar connection patterns during generation. Thus, potential environmental labels E can be inferred by analyzing and classifying graph structures. To assign structure-based environmental labels, we apply the K-Means algorithm to cluster structure-based embeddings HG for Gi ∈ Dtrain. The number of clusters, K, determines the granularity of potential environments. A larger K indicates greater diversity and the presence of multiple potential environments, while a smaller K reflects less structural diversity. Based on the clustering results, each graph Gi is assigned an environmental label Es k ∈ Estr = {Es 1 , Es 2 , ..., EsK }.

Identify Causal Structure in Graphs. To identify nodes and edges in Gi that have a causal relationship with Es k , we leverage the idea that graphs influenced by the same E exhibit similar structural patterns. Specifically, structure-based embeddings of nodes belonging to the Gs should show higher similarity within the same environment. This is because the embeddings Hstr generated by the WL kernel effectively capture graph structures and reflect connection patterns. Since embeddings Hstr are highly correlated with E, they can be used to infer causal relationships between nodes and the environment. To pinpoint nodes irrelevant to the environment, we analyze the variance in their structure-based embeddings. For nodes sharing the same Es k and classification label Y within Dtrain, we calculate the variance Ss k,Y of their embeddings Hstr. By computing the gradient of Ss k,Y with respect to each node's embedding hi ∈ Hstr, we identify nodes with high gradients as irrelevant to the environment and group them into Vc. Nodes with lower gradients are assigned to Gs, indicating their potential causal relationships with the environment E.

To determine edge significance in Gs, we first generate a subgraph G′i from the original graph Gi by dropping edges randomly. We then measure the distance change between the subgraph's embedding h′G,i and the environment cluster centre of Gi. A substantial change suggests an edge's importance to Gs. By repeatedly testing each edge in Gi, we identify and quantify the significance of edges. Critical edges are included in Gs, while others are considered part of Gc.

Identify Causal Dimension in Node Features. To identify causal dimensions in node features, we observe that the distribution of feature dimensions affected by the same E should exhibit similarity across different node types and graph labels. This is because node features in distinct dimensions typically represent independent characteristics. Based on the research of existing SCMs [Ahuja et al., 2021], nodes influenced by the same environment tend to show similar values in dimensions relevant to that environment. To determine these dimensions, we first group node features X by their node type (if applicable) and the classification label Y of their corresponding graph. For each feature dimension, we compute its probability density across these groups. Using these densities, we construct a Jensen-Shannon (JS) divergence confusion matrix to evaluate the similarity of distributions. If a feature dimension demonstrates high similarity across different node types and classification labels, it suggests that this dimension is not specific to node type or graph label but is instead primarily influenced by environmental variables. Such dimensions are classified as Dimenv, representing causal relationships to the environment. After identifying Dimenv, we use a pooling layer to aggregate these dimensions from X and generate graph-level features. These are then clustered using the K-Means to assign environmental labels Ef k ∈ Efeat = {Ef 1 , Ef 2 , ...,EfK }. However, the above procedure cannot completely exclude dimensions that are spuriously correlated with Y . To improve isolation, we assume dimensions influenced by the same E show consistent distributions across node types. We apply this method to nodes with the same Ef k , enhancing the precision of our analysis in identifying dimensions solely linked to node types.

Once environmental labels for graph structure (Es k ) and node features (Ef k ) are inferred, we can use node features with varying environmental labels to create contrastive learning samples that diverge from the training dataset's distribution. This method refines the proposed OPEN's ability to handle diverse distributions. In the inference stage, the learned cluster centres are used to predict environmental labels for new data.

4.2 Invariant Learning and Subgraph Generation

To explore how different environments affect graph structures and node features, we randomly initialize embeddings for environmental labels Estr and Efeat, refining them through the training process. The target GNNM is used to encode the graph G into node embeddings H, which are then aggregated via a pooling layer to form the graph embedding hG.

NodeVAE. NodeVAE, built on conditional variational autoencoders, ensures that node features from different distributions are mapped to a unified embedding space. Firstly, it predicts label Ef k using the NPAF module, and obtains the corresponding environmental embedding ei for node i. Then, the NodeVAE encoder gϕ1 (·), featuring a two-layers Multi-Layer Perceptrons (MLPs), processes node embedding hi ∈ H and ei to determine the distribution qϕ1 (zi|hi, env) as follows:

where ϕ1 represents the parameters of encoder models, µi and log(σ2i ) denote the mean and log-variance of the nodeinvariant representation distribution of node i, respectively. env denotes the environmental embedding(s). The node potential invariant embedding zi is sampled using reparameterization trick [Kingma and Welling, 2014]:

NodeVAE's decoder fθ1 (·) uses the learned distributions pθ1 (hi|zi, env) to reconstruct node embedding ˆhi from zi and ei. The decoder, parameterized by θ1, is followed by calculating the mean squared error between hi and ˆhi, forming the reconstruction loss Lmse. Thus, NodeVAE's final loss is:

where ωmse and ωKL are used to balance the two terms, and DKL(· ∥ ·) donates the Kullback-Leibler (KL) divergence.

GVAG. GVAG can take into account the characteristics of different environments when sampling explanation subgraphs. GVAG first computes the graph's environmental embedding eG by averaging both Es k and Ef k environmental embeddings. Then, GVAG's encoder gϕ2 (·), consisting of a two-layers MLPs, leverages eG and the graph embedding hG to generate the graph-invariant embedding zG as follows:

where µG and log(σ2G) denote the mean and log-variance of the graph-invariant representation distribution, respectively. Then, the graph-invariant embedding zG can be sampled with the reparameterization trick like Eq. 2.

The Novel Graph Decoder (NGD) in GVAG, unlike the GraphVAE [Simonovsky and Komodakis, 2018], which requires constructing and aligning a complete graph, directly models node and edge existence probabilities. Thus, GVAG improves scalability for large graphs and avoids the complexities of learnable edge weights, broadening its application range. The NGD consists of two decoders: fθ2 (·) models the probability distributions of nodes (pθ2 (vi|zG, zi, env)), and fθ3 (·) handles the distributions for edges (pθ3 (eij |zG, zi, zj , env)), both using zG, node-invariant embeddings znode, and eG. The specific formulas are as follows:

where Prob(vi) and Prob(eij) denote the probabilities that node i and edge eij exist on the explanation subgraph, respectively. By leveraging node-invariant and graph-invariant embeddings instead of standard node and graph embeddings, our subgraph generation method efficiently handles varying data distributions. In addition, GVAG employs another NGD instance to establish causal relationships between nodes, edges, and labels Y , serving as a regularization term to improve the refinement of environmental embeddings.

GVAG utilizes direct reconstruction loss to refine graph generation by optimizing node and edge existence probabilities. This method maximizes the mutual information between the explanation subgraph and the predicted label, given the input graph, as follows:

where Gc denotes the generated subgraph, 1[·] is an indicator function, and Y and ˜ Y are the outputs of the GNN for the original graph G and the subgraph Gc, respectively. Furthermore, to optimize node and edge existence probabilities in explanations, we leverage the Reconstruction Regularization Loss (LRR). This approach adjusts probabilities by comparing the GNN prediction loss between the original graph Gi ∈ Dtrain and its explanation Gc,i, effectively emphasizing crucial substructures in the subgraph. The specific formula is as follows:

where L(·) is the loss function used to trainM.

Subgraph Generation. By utilizing the mean-field variational approximation theory [Kawamoto et al., 2018; Ying et al., 2019], we complete the subgraph generation process based on the probabilities of nodes and edges. OPEN dynamically constructs the explanation by adding nodes and edges based on Prob(vi) and Prob(eij). Pseudocode and computational complexity analysis can be found in the Appendix A.2. After subgraph Gc is generated, the probability of Gc is determined using the following equation:

This probabilistic method lets users adjust the scale and density of subgraphs, significantly improving explanation quality.

4.3 Regularization Terms

Causal Structure Regularization. We employ binary crossentropy to optimize environmental embeddings and predict causal relationships between graph structures and labels Y . The calculation formula of Rcausal is computed as follows:

where σ(·) denotes the sigmoid function, and zv and ze represent the prediction logits for the node v and edge e, respectively. yv = 1 if node v is part of Gc, otherwise yv = 0. Similarly, ye follows the same pattern as yv.

Hinge Regularization. We introduce hinge regularization to constrain OPEN learning process, ensuring the empirical loss of Gc is smaller than Gs. The formula is as follows:

Subgraph Node Count Regularization. We design constraints on the compactness of subgraphs. Specifically, given the loss function outputs for original graphs L(G) and explanation subgraphs L(Gc), subgraph node counts nsub, and prior node counts nprior, this loss for instance i is defined as:

where ϵ is a small constant to prevent division by zero, the overall regularization Rsubg_node is computed as the average of the Risubg_node for all graphs in Dtrain.

4.4 Other Loss Functions

Contrastive Loss. We implement a specialized contrastive learning loss in OPEN to bolster its resistance to environmental interference. Given a set of original graph embeddings and their perturbed counterparts grouped by class labels, the formula for the contrastive loss LCON is given by:

where sintra and sinter denote the similarity scores among graphinvariant embeddings within the same class and across different classes, respectively. ϵ is used to avoid calculation issues.

Last Action Rewards (LAR). Inspired by reinforcement learning, we introduce reward functions for mining explanations in OPEN. Rewards are assigned based on whether the prediction accuracy of explanations improves post-update; penalties apply if it worsens. The LAR is defined as:

where E(Ldiff) and E(Lold_diff) are the expectation of Ldiff in this epoch and last epoch, respectively.

Final Loss of OPEN. The final optimization function for our proposed method is as follows:

where ωNodeVAE, ωRECON, ωCON and ωLAR are hyperparameters.

5 Experiments

In this section, we conduct a series of experiments to comprehensively evaluate the effectiveness of OPEN. The primary objectives are to assess fidelity, robustness and efficiency across various OOD scenarios, answering the following research questions: RQ1: How does OPEN perform in terms of fidelity and robustness compared to baseline methods in prerequisitefree and prerequisite-satisfied scenarios? RQ2: How does OPEN perform in terms of explanation subgraph quality and interpretation efficiency compared to baseline methods? RQ3: How do different modules within OPEN contribute to its performance? More experiments can be found in Appendix B.

Datasets. We use the Graph Out-of-Distribution Benchmark (GOOD) [Gui et al., 2022] to provide OOD scenarios, and select two widely used datasets, Cora and Motif, from it. Each dataset includes two shift types (covariate and concept) and two shift domains, resulting in a total of eight cases (2 datasets × 2 types × 2 domains). Table 1 provides detailed dataset statistics. Specifically, Cora is a complex real-world dataset with high node and edge densities and diverse distributions. In contrast, Motif is a simpler artificial dataset with a lower average node degree and fewer distributions. However, as an artificially generated dataset, Motif introduces a two-level OOD issue in the basis domain: the first-level OOD issue results from distribution shifts in the base part of the graphs, while the second-level OOD issue arises from distribution shifts in the motif part. This combination encompasses nearly all factors influencing XGNN performance, supporting a balanced and comprehensive evaluation of OPEN.

Baselines. Considering dataset compatibility and GNN requirements, we select several Learning & Prediction (L&P) type XGNN methods as SOTA baselines, including: PGExp [Luo et al., 2020], MixupExp [Zhang et al., 2023], GMT-SAM [Chen et al., 2024a], and ProxyExp [Chen et al., 2024b]. This type of XGNN method is notably efficient and capable of providing explanations for new instances immediately after training. In addition, we include XGNN methods that do not have a learning phase and must fit each instance individually to identify the explanation subgraphs. Although these methods cannot learn the decision logic of the GNNs and are inefficient, they are unaffected by OOD scenarios and can, therefore, serve as an ideal performance for reference, representing the fidelity of the generated explanation subgraphs when complete decision logic is fully learnt. These include GradCAM [Pope et al., 2019], ATT [Veliˇckovi´c et al., 2018], GNNExp [Ying et al., 2019], PGMExp [Vu and Thai, 2020], CF-GNNExp [Lucic et al., 2022], and KRCW [Qiu et al., 2024]. We implement these methods using well-established libraries like torch-geometric [Fey and Lenssen, 2019] and DIG [Liu et al., 2021], among other reliable sources.

Setup. To evaluate the performance of ATT, we use a 3-layer GAT network [Veliˇckovi´c et al., 2018] as backbone GNNM. Other experimental setup, including the hardware and software platform, as well as the hyper-parameter settings, can be found in the Appendix B.1. Experiments on the hyperparameter sensitivity can be found in the Appendix B.2.

Evaluation Metrics. We select five widely used metrics to evaluate XGNN methods comprehensively [Amara et al., 2022; Agarwal et al., 2023]: (1) Negative Fidelity (fid-) measures the inconsistency between the predicted labels of Gc and G (lower is better). This metric highlights the relevance of the explanation subgraph to the model's decision logic and is the most important metric in relative terms. (2) Positive Fidelity (fid+) evaluates the inconsistency between predicted labels of Gs and G (higher is better). (3) Unfaithfulness (GEF) is quantified using KL divergence between prediction distributions of Gc and G, which provides insights into the reliability of explanations. Besides, (4) Node Density (ρv) and (5) Edge Density (ρe) are given to determine the compactness of explanations. Method complexity is evaluated by measuring the time (T ) required to generate explanations for 100 samples, expressed in seconds.

5.1 Performance Comparison (RQ1)

We evaluate the fidelity and robustness of OPEN and baselines under two scenarios: (1) prerequisite-free, where access to GNN internals and the use of learnable edge weights are prohibited; and (2) prerequisite-satisfied, where these operations are permitted. In the prerequisite-satisfied scenario, XGNN methods can perturb the internal dataflows of GNNs, and generate learnable edge weights and use them as part of the input when the dataset does not contain edge features.

Prerequisite-Free Comparisons. Because PGExp and MixupExp require perturbing the internal dataflows of GNNs, and ProxyExp relies on learnable edge weights as part of the input, only GMT-SAM is applicable in prerequisite-free scenarios. Thus, GMT-SAM serves as the sole baseline for OPEN in covariate shift settings. As shown in Table 2, OPEN outperforms GMT-SAM consistently. On the Cora dataset, OPEN shows a 356.26% average improvement across all metrics in both degree and word domains. On the Motif dataset, OPEN performs comparably to GMT-SAM, primarily due to its lower-than-expected performance in the basis domain. This is because the two-level OOD issue does not align with the SCM used by OPEN, which limits NPAF's ability to partition the sample space, resulting in its performance degradation. Overall, these results indicate that by inferring and partitioning the entire dataset's sampling space, OPEN captures a more complete GNN decision logic in complex datasets like Cora, leading to greater performance improvements than in simpler datasets like Motif. This makes OPEN more effective for complex datasets. In addition, by adopting a prerequisite-free approach, OPEN consistently provides more faithful explanations (i.e., lower fid- and GEF) than baselines, significantly improving fidelity and robustness.

Prerequisite-Satisfied Comparisons. As shown in Table 3, on the Cora dataset, OPEN achieves up to a 275.7% improvement over baselines (in concept shift and word domain), with an average improvement of 218.6% for fid+, 45.76% for fid-, and 65.84% for GEF, respectively. Its performance is even comparable to the ideal performance, like PGMExp and CFGNNExp. On the Motif dataset, OPEN performs well in the size domain, improving fid- by 33.42% and GEF by 23.97%, though its fid+ performance is lower. In the basis domain, OPEN performs similarly to baselines, further supporting our findings in prerequisite-free comparisons. To summarize, in most cases that align with the SCM used by OPEN, it even achieves ideal performance, demonstrating its effectiveness in capturing a more complete GNN decision logic. By adopting a prerequisite-free method, OPEN maintains consistent performance across both prerequisite-free and prerequisite-satisfied scenarios, showcasing greater robustness than baselines.

5.2 Quality and Efficiency Comparisons (RQ2)

Table 4 lists the statistic results for the covariate shift scenarios. On complex datasets like Cora, OPEN reduces node density by up to 16.82% and edge density by 29.23% compared to PGExp, while also achieving an average speedup of 63.78 times. On simpler datasets like Motif, OPEN delivers performance comparable to baseline methods. Since OPEN provides more faithful explanations than baselines in most cases, these results suggest that OPEN better evaluates the contributions of graph structures to GNN predictions. This demonstrates that, compared to baselines, OPEN captures a more complete GNN decision logic while maintaining similar time complexity, and delivers higher-quality explanations on complex datasets. This demonstrates OPEN's scalability and superior generalizability in critical applications compared to baselines.

5.3 Ablation Study (RQ3)

Since GNN predictions in OOD scenarios involve uncertainties, accurately evaluating the role and contribution of each module in OPEN becomes challenging. Therefore, we conduct an ablation study on the basis domain of the Motif dataset under in-distribution conditions. We deactivate specific modules by setting the weights of the corresponding modules to zero. These modules include: last action rewards (LAR), the contrastive learning module (LCON), the reconstruction loss (LMI), and the reconstruction regularization loss (LRR). To evaluate the contribution of NPAF, we create a variant by reducing the number of environments to K = 1, meaning that the dataset's sample space is not partitioned.

The results in Table 5 highlight the necessity of each module for optimal performance. When all modules are active, OPEN achieves balanced and robust performance across all metrics. Disabling NPAF results in a 177.6% decrease in fidand a 47.02% decrease in GEF, highlighting its critical role in identifying diverse distributions in the dataset's sample space. This further demonstrates that partitioning the sample space enhances OPEN's capability to learn differences in GNN decision logic across various distributions. LMI is the second most influential module, as disabling it reduces fid- by 115.5% but also increases fid+ and GEF. This suggests that while it effectively selects important structures, it also incorporates some irrelevant structures into the explanations. Disabling either LCON or LAR reduces fid-, indicating that both modules help OPEN capture distribution differences and identify structures relevant to GNN predictions. Disabling LRR slightly reduces fid- and GEF, suggesting that LMI alone is insufficient to extract all critical structures for prediction.

6 Conclusion

OPEN has represented a major breakthrough in the field of XGNN by uncovering the nearly complete decision logic of GNNs. This research has introduced two key modules: NPAF and GVAG. These modules have collaboratively explored the decision logic of GNNs across the entire dataset's sample space, enhancing the OPEN's adaptability. Notably, GVAG's approach to generating explanation subgraphs has eliminated prerequisites on GNN internal accessibility and dataset properties, significantly extending OPEN's practical utility. Extensive evaluations across various datasets have confirmed the OPEN's capability to provide precise and reliable explanations, underscoring its relevance in real-world applications. In future work, we aim to address the current limitations of OPEN, including the inability to handle multi-level OOD issues and the challenge of verifying whether the complete decision logic of GNNs across all distributions has been fully captured, in order to develop a truly comprehensive GNN explainer.

Acknowledgements

This research is supported by the ARC Discovery Project DP230100676, Australia, the National Research Foundation, Singapore and Infocomm Media Development Authority under its Trust Tech Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of the National Research Foundation, Singapore and Infocomm Media Development Authority.