  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.

Machine Learning