# QGShap: Quantum Acceleration for Faithful GNN Explanations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 35 references that are in the map.
- First posted on arXiv 1 Dec 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Learning Deep Features for Discriminative Localization](https://mlsanity.com/paper/1512.04150/) (2015)
- [Visualizing and Understanding Convolutional Networks](https://mlsanity.com/paper/1311.2901/) (2013)
- [Striving for Simplicity: The All Convolutional Net](https://mlsanity.com/paper/1412.6806/) (2014)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [Evaluating Explainability for Graph Neural Networks](https://mlsanity.com/paper/2208.09339/) (2022)
- [GraphSVX: Shapley Value Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.10482/) (2021)
- [Layerwise Relevance Visualization in Convolutional Text Graph Classifiers](https://mlsanity.com/paper/1909.10911/) (2019)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [GNNShap: Scalable and Accurate GNN Explanation using Shapley Values](https://mlsanity.com/paper/2401.04829/) (2024)
- [When is Shapley Value Computation a Matter of Counting?](https://mlsanity.com/paper/2312.14529/) (2023)
- [Learning Graph Representations](https://mlsanity.com/paper/2102.02026/) (2021)
- [The Complexity of the Shapley Value for Regular Path Queries](https://mlsanity.com/paper/2212.07720/) (2022)
- [Structural Explanations for Graph Neural Networks using HSIC](https://mlsanity.com/paper/2302.02139/) (2023)
- [A Shapley Value Estimation Speedup for Efficient Explainable Quantum AI](https://mlsanity.com/paper/2412.14639/) (2024)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have become indispensable in critical domains such as drug discovery, social network analysis, and recommendation systems, yet their black-box nature hinders deployment in scenarios requiring transparency and accountability. While Shapley value-based methods offer mathematically principled explanations by quantifying each component's contribution to predictions, computing exact values requires evaluating 2n coalitions (or aggregating over n! permutations), which is intractable for real-world graphs. Existing approximation strategies sacrifice either fidelity or efficiency, limiting their practical utility. We introduce QGShap, a quantum computing approach that leverages amplitude amplification to achieve quadratic speedups in coalition evaluation while maintaining exact Shapley computation. Unlike classical sampling or surrogate methods, our approach provides fully faithful explanations without approximation trade-offs for tractable graph sizes. We conduct empirical evaluations on synthetic graph datasets, demonstrating that QGShap achieves consistently high fidelity and explanation accuracy, matching or exceeding the performance of classical methods across all evaluation metrics. These results collectively demonstrate that QGShap not only preserves exact Shapley faithfulness but also delivers interpretable, stable, and structurally consistent explanations that align with the underlying graph reasoning of GNNs. The implementation of QGShap is available at https://github.com/smlab-niser/qgshap.