  While graph neural networks (GNNs) have shown a great potential in various
tasks on graph, the lack of transparency has hindered understanding how GNNs
arrived at its predictions. Although few explainers for GNNs are explored, the
consideration of local fidelity, indicating how the model behaves around an
instance should be predicted, is neglected. In this paper, we first propose a
novel post-hoc framework based on local fidelity for any trained GNNs - TraP2,
which can generate a high-fidelity explanation. Considering that both relevant
graph structure and important features inside each node need to be highlighted,
a three-layer architecture in TraP2 is designed: i) interpretation domain are
defined by Translation layer in advance; ii) local predictive behavior of GNNs
being explained are probed and monitored by Perturbation layer, in which
multiple perturbations for graph structure and feature-level are conducted in
interpretation domain; iii) high faithful explanations are generated by fitting
the local decision boundary through Paraphrase layer. Finally, TraP2 is
evaluated on six benchmark datasets based on five desired attributions:
accuracy, fidelity, decisiveness, insight and inspiration, which achieves
$10.2\%$ higher explanation accuracy than the state-of-the-art methods.
