  Aside from graph neural networks (GNNs) attracting significant attention as a
powerful framework revolutionizing graph representation learning, there has
been an increasing demand for explaining GNN models. Although various
explanation methods for GNNs have been developed, most studies have focused on
instance-level explanations, which produce explanations tailored to a given
graph instance. In our study, we propose Prototype-bAsed GNN-Explainer (PAGE),
a novel model-level GNN explanation method that explains what the underlying
GNN model has learned for graph classification by discovering
human-interpretable prototype graphs. Our method produces explanations for a
given class, thus being capable of offering more concise and comprehensive
explanations than those of instance-level explanations. First, PAGE selects
embeddings of class-discriminative input graphs on the graph-level embedding
space after clustering them. Then, PAGE discovers a common subgraph pattern by
iteratively searching for high matching node tuples using node-level embeddings
via a prototype scoring function, thereby yielding a prototype graph as our
explanation. Using six graph classification datasets, we demonstrate that PAGE
qualitatively and quantitatively outperforms the state-of-the-art model-level
explanation method. We also carry out systematic experimental studies by
demonstrating the relationship between PAGE and instance-level explanation
methods, the robustness of PAGE to input data scarce environments, and the
computational efficiency of the proposed prototype scoring function in PAGE.
