  Graph Neural Networks (GNNs) have received increasing attention due to their
ability to learn from graph-structured data. To open the black-box of these
deep learning models, post-hoc instance-level explanation methods have been
proposed to understand GNN predictions. These methods seek to discover
substructures that explain the prediction behavior of a trained GNN. In this
paper, we show analytically that for a large class of explanation tasks,
conventional approaches, which are based on the principle of graph information
bottleneck (GIB), admit trivial solutions that do not align with the notion of
explainability. Instead, we argue that a modified GIB principle may be used to
avoid the aforementioned trivial solutions. We further introduce a novel
factorized explanation model with theoretical performance guarantees. The
modified GIB is used to analyze the structural properties of the proposed
factorized explainer. We conduct extensive experiments on both synthetic and
real-world datasets to validate the effectiveness of our proposed factorized
explainer.
