EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time
This work addresses the need for more efficient and transparent explanations of GNN predictions, which is crucial for enhancing their safety and trustworthiness in applications, though it is incremental in improving existing subgraph-level explainers.
The paper tackles the problem of inefficient and less-intuitive subgraph-level explanations for Graph Neural Networks (GNNs) by proposing EiG-Search, a training-free method that uses edge-induced subgraphs and a linear-time search algorithm, achieving superior performance and efficiency over leading baselines on seven datasets.
Understanding and explaining the predictions of Graph Neural Networks (GNNs), is crucial for enhancing their safety and trustworthiness. Subgraph-level explanations are gaining attention for their intuitive appeal. However, most existing subgraph-level explainers face efficiency challenges in explaining GNNs due to complex search processes. The key challenge is to find a balance between intuitiveness and efficiency while ensuring transparency. Additionally, these explainers usually induce subgraphs by nodes, which may introduce less-intuitive disconnected nodes in the subgraph-level explanations or omit many important subgraph structures. In this paper, we reveal that inducing subgraph explanations by edges is more comprehensive than other subgraph inducing techniques. We also emphasize the need of determining the subgraph explanation size for each data instance, as different data instances may involve different important substructures. Building upon these considerations, we introduce a training-free approach, named EiG-Search. We employ an efficient linear-time search algorithm over the edge-induced subgraphs, where the edges are ranked by an enhanced gradient-based importance. We conduct extensive experiments on a total of seven datasets, demonstrating its superior performance and efficiency both quantitatively and qualitatively over the leading baselines.