1 Introduction
Graph neural networks (GNNs) [1], [2] have exhibited impressive performance in a variety of tasks, where the data are graph-structured. Their success comes mainly from the powerful representation learning, which incorporates graph structure in an end-to-end fashion. Alongside performance, explainability becomes central to the practical impact of GNNs, especially in real-world applications on fairness, security, and robustness [3], [4], [5]. Aiming to answer questions like “Why the GNN model made a certain prediction?,” we focus on post-hoc [6], local [7], model-agnostic [8] explainability — that is, considering the target GNN model as a black-box (i.e., post-hoc), an explainer interprets its predictions of individual instances (i.e., local), which is applicable to any GNNs (i.e., model-agnostic). Towards this end, a prevalent paradigm is feature attribution and selection [9], [10], [11], [12]. Typically, given an input graph, it distributes the model’s outcome prediction to the input features (i.e., edges), and then selects the salient substructure (i.e., the subset of edges) as an explanatory subgraph. Such an explanatory subgraph is expected to provide insight into the model workings.