In Graph Neural Networks (GNNs), the graph structure is incorporated into the\nlearning of node representations. This complex structure makes explaining GNNs'\npredictions become much more challenging. In this paper, we propose\nPGM-Explainer, a Probabilistic Graphical Model (PGM) model-agnostic explainer\nfor GNNs. Given a prediction to be explained, PGM-Explainer identifies crucial\ngraph components and generates an explanation in form of a PGM approximating\nthat prediction. Different from existing explainers for GNNs where the\nexplanations are drawn from a set of linear functions of explained features,\nPGM-Explainer is able to demonstrate the dependencies of explained features in\nform of conditional probabilities. Our theoretical analysis shows that the PGM\ngenerated by PGM-Explainer includes the Markov-blanket of the target\nprediction, i.e. including all its statistical information. We also show that\nthe explanation returned by PGM-Explainer contains the same set of independence\nstatements in the perfect map. Our experiments on both synthetic and real-world\ndatasets show that PGM-Explainer achieves better performance than existing\nexplainers in many benchmark tasks.\n