Certified Robustness of Graph Classification against Topology Attack
  with Randomized Smoothing
  Graph classification has practical applications in diverse fields. Recent
studies show that graph-based machine learning models are especially vulnerable
to adversarial perturbations due to the non i.i.d nature of graph data. By
adding or deleting a small number of edges in the graph, adversaries could
greatly change the graph label predicted by a graph classification model. In
this work, we propose to build a smoothed graph classification model with
certified robustness guarantee. We have proven that the resulting graph
classification model would output the same prediction for a graph under $l_0$
bounded adversarial perturbation. We also evaluate the effectiveness of our
approach under graph convolutional network (GCN) based multi-class graph
classification model.
