Technical Summary: Explaining the Explainers in Graph Neural Networks: A Comparative Study

Problem Statement

Graph Neural Networks (GNNs) have become the standard for graph-based learning, yet their "black-box" nature limits their deployment in safety-critical scenarios. Although numerous GNN explainers have emerged to interpret model decisions, the field lacks a systematic understanding of how different GNN architectures influence explainability, which explainer is optimal for specific settings, and how different problem types (e.g., counting substructures versus motif detection) affect explanation quality. Previous benchmarking efforts were constrained by evaluating only a single GNN architecture (typically GCN), using inconsistent metrics, or failing to distinguish between the plausibility of an explanation (alignment with human intuition/ground truth) and its fidelity (alignment with the model's actual decision process).

Methodology

The authors conducted a large-scale, systematic experimental study encompassing the following:

• Architectures: Eight representative message-passing GNN architectures, categorized by their computation mechanisms: Spectral (Cheb, GCN), Spatial (GraphSAGE, GIN, GAT), Higher-Order (GraphConv), and Pooling-based (MinCutPool, Set2Set).
• Explainers: Twelve instance-based explainers covering five categories: Gradient-based (GradExplNode, GuidedBP, IntegratedGradients, GradCam), Perturbation-based (GNNExplainer, PGExplainer, SubgraphX), Decomposition-based (CAM), Surrogate-based (PGMExplainer), and Generation-based (RG-Explainer).
• Datasets: Six carefully designed datasets for both graph and node classification tasks. These include synthetic benchmarks (Grid, Grid-House, Stars, House-Color, Shapes, Infection) where ground truths are known, enabling rigorous evaluation.
• Evaluation Metrics: The study employs two primary strategies:
  1. Plausibility: Measures the similarity between the explainer's mask and a known ground truth concept (using AUC-ROC).
  2. Fidelity: Measures how well the model's prediction is preserved when computed solely on the explanation subgraph. This is decomposed into Sufficiency (prediction on the explanation) and Comprehensiveness (prediction on the complement) and aggregated into an F1-Fidelity score.
• Experimental Protocol: Models were trained to achieve at least 95% training accuracy. Explanations were generated on the training set, filtered by informativeness, and aggregated across classes and datasets to rank architectures and explainers.

Main Contributions

1. Comprehensive Benchmarking: This study is the first to evaluate a broad spectrum of GNN architectures against a diverse set of explainers across multiple datasets, moving beyond the single-architecture bias of prior works.
2. Disentangling Plausibility and Fidelity: The authors highlight a common trade-off where high plausibility (alignment with human expectations) does not guarantee high fidelity (alignment with model behavior), and vice versa. They demonstrate that relying on a single metric can lead to misleading conclusions about an explainer's quality.
3. Identification of "Lazy" Learning: The study shows that GNNs often exhibit "laziness" by learning discriminative features only for one class (e.g., the positive class) and treating the other as default. Explanations for these "default" classes are often unreliable or misleading.
4. Architectural Influence on Explainability: The work isolates specific architectural components that significantly impact explainability, such as the choice of aggregation function (linear vs. non-linear) and the handling of edge features.

Main Results

Research Question 1: How does architecture influence explanations?

• Best Overall Performance: GraphConv (Higher-Order) achieved the highest aggregated scores for both plausibility and fidelity in graph classification tasks.
• Easiest to Explain: GCN was consistently the easiest architecture to explain across most datasets and metrics. The authors attribute this to its simple, linear message-passing mechanism, in contrast to more complex architectures.
• Hardest to Explain: GIN (Graph Isomorphism Network) was the most difficult to explain, despite its simple single-layer MLP structure. This suggests a potential bias in existing explainers, which are frequently developed and tested on GCNs.
• Node Classification: In node classification, GraphSAGE provided explanations that best aligned with ground truth (plausibility), while GIN offered the highest fidelity. Chebyshev (Cheb) was the hardest to explain, likely due to its broader receptive field.

Research Question 2: How do explainers influence explanations?

• Graph Classification: Edge-based explainers consistently outperformed node-based ones. SubgraphX (perturbation-based) was the most robust explainer across all architectures. Gradient-based methods excelled in plausibility, while generation-based methods performed best in fidelity.
• Node Classification: The trend reversed; node-based explainers (particularly GNNExplainer and GradCam) outperformed edge-based ones. Gradient-based methods were generally superior in node classification tasks.
• Mask Type: The superiority of edge-based masks in graph classification is attributed to their specific design for graphs, whereas node-based masks are often adaptations from tensor data.

Research Question 3: How do different problem types influence explanations?

• Motif Counting: In the "Stars" dataset (counting substructures), explainers struggled to align plausibility with fidelity. Models often required the entire graph context (including the background ER graph) to make correct predictions, meaning the "ground truth" motif alone was insufficient for high fidelity.
• Compositional Learning: In "Grid-House," models exhibited laziness, often learning to identify only one component (Grid or House) and predicting the other class by absence.
• Node Features: In "House-Color," where node features (colors) were discriminative, edge-based explainers still performed well; however, the study found that attention mechanisms (GAT), which rely heavily on node features, were poorly explained by the tested edge-based methods.

Significance and Claims

The work claims to make a "significant step towards explaining explainability" by moving beyond quantitative performance metrics to provide qualitative insights into why certain architectures and explainers succeed or fail.

• Practical Recommendations: The authors provide actionable guidelines: Use edge-based, perturbation or generation-based explainers (such as SubgraphX) for graph classification and node-based, gradient-based explainers (such as GradCam or GNNExplainer) for node classification.
• Critical Insight on Metrics: The study warns that high accuracy does not imply the model has learned the ground truth concept; a discrepancy between plausibility and fidelity often indicates that the model is "lazy" or has learned spurious correlations.
• Future Directions: The authors identify open problems, including the need for model-level explanations, defining explanations beyond subgraphs (e.g., centrality or global properties), and developing explainers for non-message-passing architectures (e.g., Transformers) and dynamic graphs. They emphasize that explainability should be considered as a design metric when creating new GNN architectures.

The work concludes that while progress has been made, a satisfactory understanding of GNN explainability remains elusive, particularly regarding the interaction between architectural choices, dataset characteristics, and the limitations of current evaluation metrics.