# Combining Stochastic Explainers and Subgraph Neural Networks can Increase Expressivity and Interpretability

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

## Key facts

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

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

- [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)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Real Time Image Saliency for Black Box Classifiers](https://mlsanity.com/paper/1705.07857/) (2017)
- [Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism](https://mlsanity.com/paper/2201.12987/) (2022)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [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)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [A Gentle Introduction to Deep Learning for Graphs](https://mlsanity.com/paper/1912.12693/) (2019)
- [On Learning Sets of Symmetric Elements](https://mlsanity.com/paper/2002.08599/) (2020)
- [ProtGNN: Towards Self-Explaining Graph Neural Networks](https://mlsanity.com/paper/2112.00911/) (2021)
- [Reconstruction for Powerful Graph Representations](https://mlsanity.com/paper/2110.00577/) (2021)
- [Ordered Subgraph Aggregation Networks](https://mlsanity.com/paper/2206.11168/) (2022)
- [A Meta-Learning Approach for Training Explainable Graph Neural Networks](https://mlsanity.com/paper/2109.09426/) (2021)
- [Trust in AI: Interpretability is not necessary or sufficient, while black-box interaction is necessary and sufficient](https://mlsanity.com/paper/2202.05302/) (2022)

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

- [Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective](https://mlsanity.com/paper/2502.02719/) (2025)
- [GNN Explanations that do not Explain and How to find Them](https://mlsanity.com/paper/2601.20815/) (2026)
- [Interpreting Temporal Graph Neural Networks with Koopman Theory](https://mlsanity.com/paper/2410.13469/) (2024)

## Abstract (arXiv)

Subgraph-enhanced graph neural networks (SGNN) can increase the expressive power of the standard message-passing framework. This model family represents each graph as a collection of subgraphs, generally extracted by random sampling or with hand-crafted heuristics. Our key observation is that by selecting "meaningful" subgraphs, besides improving the expressivity of a GNN, it is also possible to obtain interpretable results. For this purpose, we introduce a novel framework that jointly predicts the class of the graph and a set of explanatory sparse subgraphs, which can be analyzed to understand the decision process of the classifier. We compare the performance of our framework against standard subgraph extraction policies, like random node/edge deletion strategies. The subgraphs produced by our framework allow to achieve comparable performance in terms of accuracy, with the additional benefit of providing explanations.