  Graph neural networks (GNNs) have recently gained much attention for node and
graph classification tasks on graph-structured data. However, multiple recent
works showed that an attacker can easily make GNNs predict incorrectly via
perturbing the graph structure, i.e., adding or deleting edges in the graph. We
aim to defend against such attacks via developing certifiably robust GNNs.
Specifically, we prove the certified robustness guarantee of any GNN for both
node and graph classifications against structural perturbation. Moreover, we
show that our certified robustness guarantee is tight. Our results are based on
a recently proposed technique called randomized smoothing, which we extend to
graph data. We also empirically evaluate our method for both node and graph
classifications on multiple GNNs and multiple benchmark datasets. For instance,
on the Cora dataset, Graph Convolutional Network with our randomized smoothing
can achieve a certified accuracy of 0.49 when the attacker can arbitrarily
add/delete at most 15 edges in the graph.
