  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.
