# Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks

arXiv: https://arxiv.org/abs/2310.01820 · HTML: https://mlsanity.com/paper/2310.01820/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 53 references that are in the map.
- First posted on arXiv 3 Oct 2023.

## Builds on (most cited first, 30 of 35)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [The Out-of-Distribution Problem in Explainability and Search Methods for Feature Importance Explanations](https://mlsanity.com/paper/2106.00786/) (2021)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [DIG: A Turnkey Library for Diving into Graph Deep Learning Research](https://mlsanity.com/paper/2103.12608/) (2021)
- [Towards Self-Explainable Graph Neural Network](https://mlsanity.com/paper/2108.12055/) (2021)
- [Robust Counterfactual Explanations on Graph Neural Networks](https://mlsanity.com/paper/2107.04086/) (2021)
- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks](https://mlsanity.com/paper/2206.09677/) (2022)
- [Evaluations and Methods for Explanation through Robustness Analysis](https://mlsanity.com/paper/2006.00442/) (2020)
- [CLEAR: Generative Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2210.08443/) (2022)
- [GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games](https://mlsanity.com/paper/2201.12380/) (2022)
- [GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks](https://mlsanity.com/paper/2209.07924/) (2022)
- [Interpretable Geometric Deep Learning via Learnable Randomness Injection](https://mlsanity.com/paper/2210.16966/) (2022)
- [A Survey of Explainable Graph Neural Networks: Taxonomy and Evaluation Metrics](https://mlsanity.com/paper/2207.12599/) (2022)
- [Task-Agnostic Graph Explanations](https://mlsanity.com/paper/2202.08335/) (2022)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)

## Built on by (most cited first, 17 of 17)

- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [F-Fidelity: A Robust Framework for Faithfulness Evaluation of Explainable AI](https://mlsanity.com/paper/2410.02970/) (2024)
- [Reconsidering Faithfulness in Regular, Self-Explainable and Domain Invariant GNNs](https://mlsanity.com/paper/2406.15156/) (2024)
- [How Interpretable Are Interpretable Graph Neural Networks?](https://mlsanity.com/paper/2406.07955/) (2024)
- [Explaining Graph Neural Networks via Structure-aware Interaction Index](https://mlsanity.com/paper/2405.14352/) (2024)
- [A Self-Explainable Heterogeneous GNN for Relational Deep Learning](https://mlsanity.com/paper/2412.00521/) (2024)
- [GNN Explanations that do not Explain and How to find Them](https://mlsanity.com/paper/2601.20815/) (2026)
- [B-XAIC Dataset: Benchmarking Explainable AI for Graph Neural Networks Using Chemical Data](https://mlsanity.com/paper/2505.22252/) (2025)
- [Generating In-Distribution Proxy Graphs for Explaining Graph Neural Networks](https://mlsanity.com/paper/2402.02036/) (2024)
- [On the Feasibility of Fidelity^- for Graph Pruning](https://mlsanity.com/paper/2406.11504/) (2024)
- [PAC Learnability under Explanation-Preserving Graph Perturbations](https://mlsanity.com/paper/2402.05039/) (2024)
- [Empirical Characterization of Rationale Stability Under Controlled Perturbations for Explainable Pattern Recognition](https://mlsanity.com/paper/2604.04456/) (2026)
- [AIMing for Standardised Explainability Evaluation in GNNs: A Framework and Case Study on Graph Kernel Networks](https://mlsanity.com/paper/2605.14884/) (2026)
- [Learning Quantifiable Visual Explanations Without Ground-Truth](https://mlsanity.com/paper/2605.18681/) (2026)
- [A Polynomial Architecture-Attribution Co-Design Framework for Exact Aumann-Shapley Attribution in GNNs](https://mlsanity.com/paper/2607.21094/) (2026)
- [WOMBAT: Whitebox Oracle for Molecular Benchmarking and Attribution Testing](https://mlsanity.com/paper/2610.00713/) (2026)
- [Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark](https://mlsanity.com/paper/2610.03526/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are neural models that leverage the dependency structure in graphical data via message passing among the graph nodes. GNNs have emerged as pivotal architectures in analyzing graph-structured data, and their expansive application in sensitive domains requires a comprehensive understanding of their decision-making processes -- necessitating a framework for GNN explainability. An explanation function for GNNs takes a pre-trained GNN along with a graph as input, to produce a `sufficient statistic' subgraph with respect to the graph label. A main challenge in studying GNN explainability is to provide fidelity measures that evaluate the performance of these explanation functions. This paper studies this foundational challenge, spotlighting the inherent limitations of prevailing fidelity metrics, including Fid_+, Fid_-, and Fid_Delta. Specifically, a formal, information-theoretic definition of explainability is introduced and it is shown that existing metrics often fail to align with this definition across various statistical scenarios. The reason is due to potential distribution shifts when subgraphs are removed in computing these fidelity measures. Subsequently, a robust class of fidelity measures are introduced, and it is shown analytically that they are resilient to distribution shift issues and are applicable in a wide range of scenarios. Extensive empirical analysis on both synthetic and real datasets are provided to illustrate that the proposed metrics are more coherent with gold standard metrics. The source code is available at https://trustai4s-lab.github.io/fidelity.