# On the Probability of Necessity and Sufficiency of Explaining Graph Neural Networks: A Lower Bound Optimization Approach

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 84 references that are in the map.
- First posted on arXiv 14 Dec 2022.

## Builds on (most cited first, 30 of 45)

- [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)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [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)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [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)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [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)
- [Towards Causal Representation Learning](https://mlsanity.com/paper/2102.11107/) (2021)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Generative Causal Explanations for Graph Neural Networks](https://mlsanity.com/paper/2104.06643/) (2021)
- [CF-GNNExplainer: Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2102.03322/) (2021)
- [Probabilities of Causation: Bounds and Identification](https://mlsanity.com/paper/1301.3898/) (2013)

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

- [Counterfactual Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.01391/) (2023)
- [Feature Attribution with Necessity and Sufficiency via Dual-stage Perturbation Test for Causal Explanation](https://mlsanity.com/paper/2402.08845/) (2024)
- [Unifying Invariance and Spuriousity for Graph Out-of-Distribution via Probability of Necessity and Sufficiency](https://mlsanity.com/paper/2402.09165/) (2024)
- [Unifying Invariant and Variant Features for Graph Out-of-Distribution via Probability of Necessity and Sufficiency](https://mlsanity.com/paper/2407.15273/) (2024)
- [ATEX-CF: Attack-Informed Counterfactual Explanations for Graph Neural Networks](https://mlsanity.com/paper/2602.06240/) (2026)
- [Adapting to Change: Robust Counterfactual Explanations in Dynamic Data Landscapes](https://mlsanity.com/paper/2308.02353/) (2023)
- [Learning Marked Temporal Point Process Explanations based on Counterfactual and Factual Reasoning](https://mlsanity.com/paper/2508.11943/) (2025)
- [SEASONED: Semantic-Enhanced Self-Counterfactual Explainable Detection of Adversarial Exploiter Contracts](https://mlsanity.com/paper/2509.05681/) (2025)
- [Regional Explanations via Causal Sufficiency and Necessity](https://mlsanity.com/paper/2609.18049/) (2026)
- [RACE: Relation-Level Counterfactual Explanations for Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2609.37650/) (2026)
- [Where Privacy Belongs: Placement Diagnosis and Certified Selection for Private Counterfactual Explanations on Graphs](https://mlsanity.com/paper/2609.37667/) (2026)

## Abstract (arXiv)

The explainability of Graph Neural Networks (GNNs) is critical to various GNN applications, yet it remains a significant challenge. A convincing explanation should be both necessary and sufficient simultaneously. However, existing GNN explaining approaches focus on only one of the two aspects, necessity or sufficiency, or a heuristic trade-off between the two. Theoretically, the Probability of Necessity and Sufficiency (PNS) holds the potential to identify the most necessary and sufficient explanation since it can mathematically quantify the necessity and sufficiency of an explanation. Nevertheless, the difficulty of obtaining PNS due to non-monotonicity and the challenge of counterfactual estimation limit its wide use. To address the non-identifiability of PNS, we resort to a lower bound of PNS that can be optimized via counterfactual estimation, and propose a framework of Necessary and Sufficient Explanation for GNN (NSEG) via optimizing that lower bound. Specifically, we depict the GNN as a structural causal model (SCM), and estimate the probability of counterfactual via the intervention under the SCM. Additionally, we leverage continuous masks with a sampling strategy to optimize the lower bound to enhance the scalability. Empirical results demonstrate that NSEG outperforms state-of-the-art methods, consistently generating the most necessary and sufficient explanations.