# Faithful Explanations for Deep Graph Models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 38 references that are in the map.
- First posted on arXiv 24 May 2022.

## Builds on (most cited first, 29 of 29)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [RISE: Randomized Input Sampling for Explanation of Black-box Models](https://mlsanity.com/paper/1806.07421/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Interpretable Explanations of Black Boxes by Meaningful Perturbation](https://mlsanity.com/paper/1704.03296/) (2017)
- [Score-CAM: Score-Weighted Visual Explanations for Convolutional Neural Networks](https://mlsanity.com/paper/1910.01279/) (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)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [On the (In)fidelity and Sensitivity for Explanations](https://mlsanity.com/paper/1901.09392/) (2019)
- [Graph Neural Network-Based Anomaly Detection in Multivariate Time Series](https://mlsanity.com/paper/2106.06947/) (2021)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [DIG: A Turnkey Library for Diving into Graph Deep Learning Research](https://mlsanity.com/paper/2103.12608/) (2021)
- [Subgraph Neural Networks](https://mlsanity.com/paper/2006.10538/) (2020)
- [Knowledge-aware Coupled Graph Neural Network for Social Recommendation](https://mlsanity.com/paper/2110.03987/) (2021)
- [Influence-Directed Explanations for Deep Convolutional Networks](https://mlsanity.com/paper/1802.03788/) (2018)
- [Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes](https://mlsanity.com/paper/1903.08778/) (2019)
- [Fast Geometric Projections for Local Robustness Certification](https://mlsanity.com/paper/2002.04742/) (2020)
- [Interpreting Interpretations: Organizing Attribution Methods by Criteria](https://mlsanity.com/paper/2002.07985/) (2020)

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

- [What Makes a Good Explanation?: A Harmonized View of Properties of Explanations](https://mlsanity.com/paper/2211.05667/) (2022)
- [Spatio-Temporal Attention Graph Neural Network: Explaining Causalities With Attention](https://mlsanity.com/paper/2603.10676/) (2026)

## Abstract (arXiv)

This paper studies faithful explanations for Graph Neural Networks (GNNs). First, we provide a new and general method for formally characterizing the faithfulness of explanations for GNNs. It applies to existing explanation methods, including feature attributions and subgraph explanations. Second, our analytical and empirical results demonstrate that feature attribution methods cannot capture the nonlinear effect of edge features, while existing subgraph explanation methods are not faithful. Third, we introduce k-hop Explanation with a Convolutional Core (KEC), a new explanation method that provably maximizes faithfulness to the original GNN by leveraging information about the graph structure in its adjacency matrix and its k-th power. Lastly, our empirical results over both synthetic and real-world datasets for classification and anomaly detection tasks with GNNs demonstrate the effectiveness of our approach.