  Despite the exploding interest in graph neural networks there has been little
effort to verify and improve their robustness. This is even more alarming given
recent findings showing that they are extremely vulnerable to adversarial
attacks on both the graph structure and the node attributes. We propose the
first method for verifying certifiable (non-)robustness to graph perturbations
for a general class of models that includes graph neural networks and
label/feature propagation. By exploiting connections to PageRank and Markov
decision processes our certificates can be efficiently (and under many threat
models exactly) computed. Furthermore, we investigate robust training
procedures that increase the number of certifiably robust nodes while
maintaining or improving the clean predictive accuracy.
