Research map / Graph learning / GNN architectures

Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective

ICML 2025 · Graph learning › GNN architectures · approach: GNN explainability · 0 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.

Formalizes the explanations of sparsity- and information-bottleneck-based self-explainable GNNs as minimal explanations, compares them with prime implicant and faithful explanations, and proposes Dual-Channel GNNs that combine an SE-GNN with a sparse linear rule channel.

Problem

Self-explainable GNNs are popular, but the formal properties and limitations of the subgraph explanations they extract are poorly understood, including their informativeness and faithfulness relative to prime implicant and faithful explanations.

Approach

Shows that popular sparsity and IB-based SE-GNN losses optimize for minimal explanations, proves these match prime implicants for positive existential tasks but can be less informative and unfaithful in general, and proposes Dual-Channel GNNs that offload non-topological patterns to an interpretable linear rule channel combined via a LENs-based aggregator.

Key results

• On RedBlueNodes, DC-GSAT and DC-SMGNN reach 100% test accuracy versus 99% for GSAT and SMGNN, and DC-SMGNN reaches 100% on the OOD2 split versus 85% for SMGNN.
• On TopoFeature OOD1, DC-SMGNN achieves 93% accuracy versus 55% for SMGNN, and DC-GSAT achieves 87% versus 81% for GSAT.
• On real-world datasets, DC-GSAT improves AIDS F1 to 99% versus 97% for GSAT, and DC-SMGNN improves Graph-SST2 accuracy to 87% versus 86% for SMGNN.

Measured effects reported in the paper

Surprising findings

• Minimal explanations can be identical for two classifiers that differ, e.g. exists-edge and forall-exists-edge, so explanations alone cannot distinguish them.
• Minimal explanations can achieve zero faithfulness (NEC = 0) even on trivial tasks such as the existence of an edge.

Limitations

• Theoretical analysis focuses on sparsity- and IB-based SE-GNNs and does not cover other subgraph explainers.
• The interpretable channel is a simple sparse linear model; more advanced interpretable channels are left to future work.
• Prime implicant and faithful explanations can be exponentially large and intractable to find.

Experimental setup

Datasets: GOODMotif RedBlueNodes TopoFeature MUTAG BBBP MNIST75sp AIDS Graph-SST2

Benchmarks: GOODMotif RedBlueNodes TopoFeature MUTAG BBBP MNIST75sp AIDS Graph-SST2

Metrics: accuracy F1 AUC OOD accuracy

Baselines: GIN GISST GSAT SMGNN LRI GMT

Builds on: GSAT GISST Logic Explained Networks LRI GIN

Closest papers by meaning

• Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.93)
• Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs (ICLR 2025 · similarity 0.92)
• Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks (ICLR 2024 · similarity 0.91)
• GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking (ICLR 2024 · similarity 0.90)
• Redundancy Undermines the Trustworthiness of Self-Interpretable GNNs (ICML 2025 · similarity 0.90)
• GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules (NeurIPS 2024 · similarity 0.90)