  Graph convolutional neural networks (GCNs) are powerful tools for learning
graph-based knowledge representations from training data. However, they are
vulnerable to small perturbations in the input graph, which makes them
susceptible to input faults or adversarial attacks. This poses a significant
problem for GCNs intended to be used in critical applications, which need to
provide certifiably robust services even in the presence of adversarial
perturbations. We propose an improved GCN robustness certification technique
for node classification in the presence of node feature perturbations. We
introduce a novel polyhedra-based abstract interpretation approach to tackle
specific challenges of graph data and provide tight upper and lower bounds for
the robustness of the GCN. Experiments show that our approach simultaneously
improves the tightness of robustness bounds as well as the runtime performance
of certification. Moreover, our method can be used during training to further
improve the robustness of GCNs.
