Power Up! Robust Graph Convolutional Network via Graph Powering

We enhance adversarial robustness of GCNs by moving beyond spectral graph theory to robust graph theory. We introduce a novel convolution operator that is provably robust in the spectral domain and incorporate it into the GCN architecture to improve expressivity and interpretability. Extending the original graph to a sequence of graphs yields a robust training paradigm encouraging transferability across spatial and spectral characteristics. Extensive experiments show simultaneous gains in benign and adversarial settings.