  Graph Neural Networks (GNNs) have made significant advances on several
fundamental inference tasks. As a result, there is a surge of interest in using
these models for making potentially important decisions in high-regret
applications. However, despite GNNs' impressive performance, it has been
observed that carefully crafted perturbations on graph structures (or nodes
attributes) lead them to make wrong predictions. Presence of these adversarial
examples raises serious security concerns. Most of the existing robust GNN
design/training methods are only applicable to white-box settings where model
parameters are known and gradient based methods can be used by performing
convex relaxation of the discrete graph domain. More importantly, these methods
are not efficient and scalable which make them infeasible in time sensitive
tasks and massive graph datasets. To overcome these limitations, we propose a
general framework which leverages the greedy search algorithms and zeroth-order
methods to obtain robust GNNs in a generic and an efficient manner. On several
applications, we show that the proposed techniques are significantly less
computationally expensive and, in some cases, more robust than the
state-of-the-art methods making them suitable to large-scale problems which
were out of the reach of traditional robust training methods.
