Research map / Graph learning / GNN architectures
Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks
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.
Shows that standard GNN explanation fidelity metrics (Fid+, Fid-, Fid_Delta) suffer from distribution shift when subgraphs are removed or isolated, and proposes robust edge-sampling-based fidelity variants whose correlation with edit-distance gold standard is much stronger.
Problem
Existing surrogate fidelity metrics for GNN explanations (Fid+, Fid-, Fid_Delta) can be misaligned with an information-theoretic definition of explainability because removing or isolating explanation subgraphs creates out-of-distribution inputs.
Approach
Define explainability information-theoretically (sufficient statistic subgraph with small size), then replace the deterministic edge removal/keeping in Fid+ and Fid- with stochastic edge sampling at rates alpha1 and alpha2, yielding a generalized family of fidelity measures that is provably well-behaved under mild conditions and less sensitive to OOD subgraphs.
Key results
- Fid_{alpha1,+} achieves Spearman correlation near -1.0 (e.g., -0.990 to -1.000) with gold-standard edit distance across all GCN and GIN settings except GIN on Tree-Grid, whereas original Fid+ has mixed signs (e.g., 0.229 on Tree-Cycles GCN).
- Fid_{alpha2,-} achieves correlation of about 1.0 across datasets, compared with original Fid- values such as -0.210 on Tree-Cycles GCN and -0.276 on MUTAG GCN.
- All fidelity measures, including the proposed ones, fail on GIN for Tree-Grid, which the authors attribute to GIN's limited node-classification generalization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GCN explanation evaluation · Tree-Cycles | Spearman correlation with gold-standard edit distance: 0.105 -> -0.990 | Helped |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GCN explanation evaluation · Tree-Grid | Spearman correlation with gold-standard edit distance: -0.781 -> -1.000 | Helped |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GCN explanation evaluation · BA-2motifs | Spearman correlation with gold-standard edit distance: -0.990 -> -1.000 | Helped |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GCN explanation evaluation · MUTAG | Spearman correlation with gold-standard edit distance: -0.105 -> -1.000 | Helped |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GIN explanation evaluation · Tree-Cycles | Spearman correlation with gold-standard edit distance: -0.286 -> -1.000 | Helped |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GIN explanation evaluation · Tree-Grid | Spearman correlation with gold-standard edit distance: 1.000 -> 1.000 | No clear effect |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GIN explanation evaluation · BA-2motifs | Spearman correlation with gold-standard edit distance: -1.000 -> -1.000 | No clear effect |
| replace Fid_Δ with generalized Fid_{α1,α2,Δ} | GIN explanation evaluation · MUTAG | Spearman correlation with gold-standard edit distance: -0.990 -> -1.000 | Helped |
| use generalized fidelity measures instead of original fidelity measures | GNN explanation evaluation · Tree-Cycles, Tree-Grid, BA-2motifs, MUTAG | alignment with gold-standard edit distance | Mixed |
Surprising findings
- Original Fid+ and Fid- give mixed-sign correlations with the gold standard, sometimes contradicting the intended direction.
- The commonly used edge-classification AUC aligns perfectly (-1.000) with edit distance in all settings.
Limitations
- Fidelity measures ignore explanation size, so whole-graph explanations still score optimally; the proposed metrics do not solve this.
- Well-behavedness proofs rely on restrictive assumptions (motif-based labels, typical-set classifiers, deterministic or near-Bayes-optimal settings).
- Gold-standard validation uses synthetic motif-based datasets plus MUTAG, and the GIN node-classification case fails for all metrics.
Experimental setup
Datasets: Tree-Cycles Tree-Grid BA-2motifs MUTAG
Benchmarks: Tree-Cycles Tree-Grid BA-2motifs MUTAG
Metrics: Spearman correlation with edit distance AUC
Baselines: Fid+ Fid- Fid_Delta
Builds on: Fid+ Fid- GNNExplainer PGExplainer
Closest papers by meaning
- Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs (ICLR 2025 · similarity 0.93)
- Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks (ICML 2024 · similarity 0.92)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.92)
- Stratified GNN Explanations through Sufficient Expansion (AAAI 2024 · similarity 0.92)
- Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective (ICML 2025 · similarity 0.91)
- Redundancy Undermines the Trustworthiness of Self-Interpretable GNNs (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.