Research map / Graph learning / GNN architectures

Stratified GNN Explanations through Sufficient Expansion

AAAI 2024 · Graph learning › GNN architectures · approach: Graph structure learning · 4 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes STFExplainer, a stratified post-hoc GNN explainer that produces explanatory subgraphs at each level of a graph's hierarchical clustering, using a "sufficient expansion" to map high-level subgraphs back to the input graph for mutual-information optimization.

Problem

Explaining GNN predictions on hierarchically clustered graphs at multiple structural levels, which flat edge-level explainers and motif-centric hierarchy-aware explainers cannot provide.

Approach

Formulates multi-level GNN explanation as mutual-information maximization over level-l subgraphs, introduces a sufficient expansion function that maps a high-level subgraph to all its underlying low-level edges, and learns a hierarchy-aware coarsening module plus attribution module (on top of PGExplainer-style optimization) to score cluster-level edges.

Key results

• On real-world datasets, STFExplainer achieves fidelity ACC 0.951 on MUTAG (vs. 0.943 for SA) and ranks top-2 in several fidelity/recall metrics, with an average deviation of 11% from the best alternative.
• On the synthetic BA-Hierarchy-motif dataset, STFExplainer reaches recall 0.666 versus 0.560 for the best baseline (Motif-add), an average deviation of 8%.
• Wilcoxon tests show significant gains over the leading baseline on QMOFs fidelity (p<8e-6), while no significant difference on MUTAG fidelity (ACC p=0.4).

Measured effects reported in the paper

Surprising findings

• On MUTAG, SA and DeepLift outperform or match STFExplainer on some fidelity metrics, and the method outperforms the second-best method in only 2 of 5 metrics on the real-world data.
• On QMOFs, STFExplainer slightly lags PGMExplainer in fidelity.

Limitations

• Built on PGExplainer's optimization, so performance on non-hierarchical graphs is expected to be close to PGExplainer rather than superior.
• Explanations are extracted layer by layer; cross-layer optimization is not handled.
• On QMOFs fidelity it trails PGMExplainer; the method was not applied on top of other baselines due to cost.

Experimental setup

Datasets: MUTAG QMOFs BA-Hierarchy-motif

Benchmarks: MUTAG QMOFs BA-Hierarchy-motif

Metrics: fidelity (ACC) fidelity (CE) fidelity (R2) fidelity (MAE) recall sparsity

Baselines: Motif-mul Motif-add Motif-max SA DeepLift CXPlain GNNExplainer PGExplainer Refine-CT PGMExplainer

Builds on: PGExplainer GNNExplainer Refine MotifExplainer

Closest papers by meaning

• Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.92)
• GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules (NeurIPS 2024 · similarity 0.90)
• Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.90)
• Higher Order Structures for Graph Explanations (AAAI 2025 · similarity 0.90)
• GnnXemplar: Exemplars to Explanations - Natural Language Rules for Global GNN Interpretability (NeurIPS 2025 · similarity 0.90)
• Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.90)