  As Graph Neural Networks (GNNs) are increasingly being employed in critical
real-world applications, several methods have been proposed in recent
literature to explain the predictions of these models. However, there has been
little to no work on systematically analyzing the reliability of these methods.
Here, we introduce the first-ever theoretical analysis of the reliability of
state-of-the-art GNN explanation methods. More specifically, we theoretically
analyze the behavior of various state-of-the-art GNN explanation methods with
respect to several desirable properties (e.g., faithfulness, stability, and
fairness preservation) and establish upper bounds on the violation of these
properties. We also empirically validate our theoretical results using
extensive experimentation with nine real-world graph datasets. Our empirical
results further shed light on several interesting insights about the behavior
of state-of-the-art GNN explanation methods.
