QGShap: Quantum Acceleration for Faithful GNN Explanations

• URL: http://arxiv.org/abs/2512.03099v1
• Date: Mon, 01 Dec 2025 16:19:15 GMT
• Title: QGShap: Quantum Acceleration for Faithful GNN Explanations
• Authors: Haribandhu Jena, Jyotirmaya Shivottam, Subhankar Mishra,
• Abstract summary: We introduce QGShap, a quantum computing approach that leverages amplitude amplification to achieve quadratic speedups in coalition evaluation.<n>Unlike classical sampling or surrogate methods, our approach provides fully faithful explanations without approximation trade-offs for tractable graph sizes.
• Score: 0.48998185508205744
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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 $2^n$ 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.

Related papers

• QGraphLIME - Explaining Quantum Graph Neural Networks [0.48998185508205744]
  Quantum graph neural networks offer a powerful paradigm for learning on graph-structured data.<n>QuantumGraphLIME treats model explanations as distributions over local surrogates fit on structure-preserving perturbations of a graph.
  arXiv  Detail & Related papers  (2025-10-07T08:39:13Z)
• Shapley-Value-Based Graph Sparsification for GNN Inference [1.5998912722142724]
  Graph sparsification is a technique for improving inference efficiency in Graph Neural Networks.<n> Shapley value based methods assign both positive and negative contributions to node predictions.<n>Our approach shows that Shapley value-based graph sparsification maintains predictive performance while significantly reducing graph complexity.
  arXiv  Detail & Related papers  (2025-07-28T01:30:09Z)
• Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation [6.542796128290513]
  We propose Shapley-Guided Utility Learning (SGUL), a novel framework for graph inference data valuation.<n>SGUL combines transferable data-specific and modelspecific features to approximate test accuracy without relying on ground truth labels.<n>We show that SGUL consistently outperforms existing baselines in both inductive and transductive settings.
  arXiv  Detail & Related papers  (2025-03-23T20:35:03Z)
• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  Shapley Interactions (SIs) quantify node contributions and interactions among multiple nodes.<n>By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction.<n>We introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly.
  arXiv  Detail & Related papers  (2025-01-28T13:37:44Z)
• Game-theoretic Counterfactual Explanation for Graph Neural Networks [13.583604117327697]
  Graph Neural Networks (GNNs) have been a powerful tool for node classification tasks in complex networks. Counterfactual explanations (CFE) have shown promise in enhancing the interpretability of machine learning models. We propose a semivalue-based, non-learning approach to generate CFE for node classification tasks.
  arXiv  Detail & Related papers  (2024-02-08T20:07:43Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks [32.345435955298825]
  Graph Neural Networks (GNNs) are neural models that leverage the dependency structure in graphical data via message passing among the graph nodes. 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.
  arXiv  Detail & Related papers  (2023-10-03T06:25:14Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Explainable Sparse Knowledge Graph Completion via High-order Graph Reasoning Network [111.67744771462873]
  This paper proposes a novel explainable model for sparse Knowledge Graphs (KGs) It combines high-order reasoning into a graph convolutional network, namely HoGRN. It can not only improve the generalization ability to mitigate the information insufficiency issue but also provide interpretability.
  arXiv  Detail & Related papers  (2022-07-14T10:16:56Z)
• FlowX: Towards Explainable Graph Neural Networks via Message Flows [59.025023020402365]
  We investigate the explainability of graph neural networks (GNNs) as a step toward elucidating their working mechanisms. We propose a novel method here, known as FlowX, to explain GNNs by identifying important message flows. We then propose an information-controlled learning algorithm to train flow scores toward diverse explanation targets.
  arXiv  Detail & Related papers  (2022-06-26T22:48:15Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.