  As one of the most popular machine learning models today, graph neural
networks (GNNs) have attracted intense interest recently, and so does their
explainability. Users are increasingly interested in a better understanding of
GNN models and their outcomes. Unfortunately, today's evaluation frameworks for
GNN explainability often rely on few inadequate synthetic datasets, leading to
conclusions of limited scope due to a lack of complexity in the problem
instances. As GNN models are deployed to more mission-critical applications, we
are in dire need for a common evaluation protocol of explainability methods of
GNNs. In this paper, we propose, to our best knowledge, the first systematic
evaluation framework for GNN explainability, considering explainability on
three different "user needs". We propose a unique metric that combines the
fidelity measures and classifies explanations based on their quality of being
sufficient or necessary. We scope ourselves to node classification tasks and
compare the most representative techniques in the field of input-level
explainability for GNNs. For the inadequate but widely used synthetic
benchmarks, surprisingly shallow techniques such as personalized PageRank have
the best performance for a minimum computation time. But when the graph
structure is more complex and nodes have meaningful features, gradient-based
methods are the best according to our evaluation criteria. However, none
dominates the others on all evaluation dimensions and there is always a
trade-off. We further apply our evaluation protocol in a case study for frauds
explanation on eBay transaction graphs to reflect the production environment.
