On the probability of necessity and sufficiency of explaining Graph Neural Networks: A lower bound optimization approach

• DOI: 10.1016/j.neunet.2024.107065
• Publication Date: 2024-12-24T16:48:10Z
• Authors: Ruichu Cai; Yuxuan Zhu; Xuexin Chen; Yuan Fang; Min Wu; Jie Qiao; Zhifeng Hao
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; 330; OS and Networks; 02 engineering and technology; Explainability; 004; Machine Learning (cs.LG); Causality; Explainable AI; 0202 electrical engineering, electronic engineering, information engineering; Interpretability; Graph Neural Networks; Numerical Analysis and Scientific Computing

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.<br/>Submitted to Neural Networks<br/>