Connected-C \(\textrm{F}^2\) : Learning the Explainability of Graph Neural Network on Counterfactual and Factual Reasoning via Connected Component

Structural data, such as social networks, molecules, citation networks, etc., exists everywhere in various fields. The complex topology makes it difficult to process and fully utilize such informative data. In recent years, Graph Neural Networks (GNNs) have achieved great success on learning representations for structural data. However, most of them are still considered as black boxes and the non-transparency of the models makes the explanation and interpretation of the predictions by GNNs non-trivial. This research seeks to solve the explainability problem of GNNs considering Counterfactual and Factual reasoning from casual inference theory on connected substructures of graphs, which are more human-intelligible and intuitive while ignored by most existing methods. In this paper, we propose an original method, Connected-C \(\mathbf {\textrm{F}^2}\) , to explain GNNs by formulating an optimization problem based on the counterfactual and factual reasoning condition and the connectivity condition of explanations. Two kinds of explanation strengths are given for the condition on reasoning, and the connectivity condition is a constraint on the number of connected components in graphs. This distinguishes Connected-C \(\mathbf {\textrm{F}^2}\) from previous explainability methods. Experiments show that Connected-C \(\mathbf {\textrm{F}^2}\) generates significantly improved explanations than the existing state-of-the-art methods.