  Massive deployment of Graph Neural Networks (GNNs) in high-stake applications
generates a strong demand for explanations that are robust to noise and align
well with human intuition. Most existing methods generate explanations by
identifying a subgraph of an input graph that has a strong correlation with the
prediction. These explanations are not robust to noise because independently
optimizing the correlation for a single input can easily overfit noise.
Moreover, they do not align well with human intuition because removing an
identified subgraph from an input graph does not necessarily change the
prediction result. In this paper, we propose a novel method to generate robust
counterfactual explanations on GNNs by explicitly modelling the common decision
logic of GNNs on similar input graphs. Our explanations are naturally robust to
noise because they are produced from the common decision boundaries of a GNN
that govern the predictions of many similar input graphs. The explanations also
align well with human intuition because removing the set of edges identified by
an explanation from the input graph changes the prediction significantly.
Exhaustive experiments on many public datasets demonstrate the superior
performance of our method.
