# GRAPHSHAP: Explaining Identity-Aware Graph Classifiers Through the Language of Motifs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 42 references that are in the map.
- First posted on arXiv 17 Feb 2022.

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

- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [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)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [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)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Explainable Machine Learning in Deployment](https://mlsanity.com/paper/1909.06342/) (2019)
- [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)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Human-Centered Artificial Intelligence: Reliable, Safe & Trustworthy](https://mlsanity.com/paper/2002.04087/) (2020)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [Higher-Order Explanations of Graph Neural Networks via Relevant Walks](https://mlsanity.com/paper/2006.03589/) (2020)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [Analysis of Explainers of Black Box Deep Neural Networks for Computer Vision: A Survey](https://mlsanity.com/paper/1911.12116/) (2019)
- [Distill-and-Compare: Auditing Black-Box Models Using Transparent Model Distillation](https://mlsanity.com/paper/1710.06169/) (2017)
- [RelEx: A Model-Agnostic Relational Model Explainer](https://mlsanity.com/paper/2006.00305/) (2020)
- [Counterfactual Graphs for Explainable Classification of Brain Networks](https://mlsanity.com/paper/2106.08640/) (2021)
- [Explainable Classification of Brain Networks via Contrast Subgraphs](https://mlsanity.com/paper/2006.05176/) (2020)
- [FairLens: Auditing Black-box Clinical Decision Support Systems](https://mlsanity.com/paper/2011.04049/) (2020)

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

- [GNNShap: Scalable and Accurate GNN Explanation using Shapley Values](https://mlsanity.com/paper/2401.04829/) (2024)
- [L2XGNN: Learning to Explain Graph Neural Networks](https://mlsanity.com/paper/2209.14402/) (2022)
- [Utilizing Description Logics for Global Explanations of Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2405.12654/) (2024)
- [Global Concept Explanations for Graphs by Contrastive Learning](https://mlsanity.com/paper/2404.16532/) (2024)
- [DistShap: Scalable GNN Explanations with Distributed Shapley Values](https://mlsanity.com/paper/2506.22668/) (2025)
- [Measuring What Matters: A Unified Evaluation Framework for GNN Explainability](https://mlsanity.com/paper/2607.04600/) (2026)

## Abstract (arXiv)

Most methods for explaining black-box classifiers (e.g. on tabular data, images, or time series) rely on measuring the impact that removing/perturbing features has on the model output. This forces the explanation language to match the classifier's feature space. However, when dealing with graph data, in which the basic features correspond to the edges describing the graph structure, this matching between features space and explanation language might not be appropriate. Decoupling the feature space (edges) from a desired high-level explanation language (such as motifs) is thus a major challenge towards developing actionable explanations for graph classification tasks. In this paper we introduce GRAPHSHAP, a Shapley-based approach able to provide motif-based explanations for identity-aware graph classifiers, assuming no knowledge whatsoever about the model or its training data: the only requirement is that the classifier can be queried as a black-box at will. For the sake of computational efficiency we explore a progressive approximation strategy and show how a simple kernel can efficiently approximate explanation scores, thus allowing GRAPHSHAP to scale on scenarios with a large explanation space (i.e. large number of motifs). We showcase GRAPHSHAP on a real-world brain-network dataset consisting of patients affected by Autism Spectrum Disorder and a control group. Our experiments highlight how the classification provided by a black-box model can be effectively explained by few connectomics patterns.