  Perturbations targeting the graph structure have proven to be extremely
effective in reducing the performance of Graph Neural Networks (GNNs), and
traditional defenses such as adversarial training do not seem to be able to
improve robustness. This work is motivated by the observation that
adversarially injected edges effectively can be viewed as additional samples to
a node's neighborhood aggregation function, which results in distorted
aggregations accumulating over the layers. Conventional GNN aggregation
functions, such as a sum or mean, can be distorted arbitrarily by a single
outlier. We propose a robust aggregation function motivated by the field of
robust statistics. Our approach exhibits the largest possible breakdown point
of 0.5, which means that the bias of the aggregation is bounded as long as the
fraction of adversarial edges of a node is less than 50\%. Our novel
aggregation function, Soft Medoid, is a fully differentiable generalization of
the Medoid and therefore lends itself well for end-to-end deep learning.
Equipping a GNN with our aggregation improves the robustness with respect to
structure perturbations on Cora ML by a factor of 3 (and 5.5 on Citeseer) and
by a factor of 8 for low-degree nodes.
