Graph convolutional networks (GCNs) are powerful tools for graph-structured data. However, they have been recently shown to be vulnerable to topological attacks. To enhance adversarial robustness, we go beyond spectral graph theory to robust graph theory. By challenging the classical graph Laplacian, we propose a new convolution operator that is provably robust in the spectral domain and is incorporated in the GCN architecture to improve expressivity and interpretability. By extending the original graph to a sequence of graphs, we also propose a robust training paradigm that encourages transferability across graphs that span a range of spatial and spectral characteristics. The proposed approaches are demonstrated in extensive experiments to simultaneously improve performance in both benign and adversarial situations.
This paper proposes a new architecture for graph convolutional network based on graph powering operation which generates a new graph based on the shortest distance between pair of nodes.  Its main motivation is to overcome the dominance of the first eigenvector in the existing GCN architectures based on the graph Laplacian operator. The theoretical evidence for the robustness is provided based on the signal-to-noise (SNR) ratio of the simplified stochastic block model (SBM). Two versions of the algorithms are proposed, namely the robust graph convolutional network (r-GCN) and variable power network (VPN). First, r-GCN is based on augmenting the graphs with graph powering operation. Next, VPN replaces the adjacency matrix of the graph convolutional operator by the newly proposed variable power operator. An additional sparsification scheme is proposed since the graph powering operation densifies the original graph.  
Overall, I like how the paper addresses the weakness of the existing graph Laplacian operators (dominance of the first eigenvector) and proposed a new method with theoretical justifications. Experiments were conducted thoroughly and results look great in the presented datasets. However, I also have concerns about the paper that I feel necessary to be resolved. 
Most importantly, the concept of "robustness" in GCN seems to be inconsistent throughout the paper.  Namely, the meaning of robustness in the neural network (adversarial robustness) and the SBM literature (spectral robustness) are different. This point is crucial since the paper use the spectral robustness for justification of the method, yet experiments are done on the adversarial attacks. More specifically, adversarial training methods for neural networks, e.g., adversarial attack methods [1] considered in the paper, typically make the loss function (or output of network) more persistent against the small perturbation of inputs. On the other side, the robustness for SBM models, e.g., Theorem 3 in the paper, cares more about the preservation of the original input characteristics. For illustration, an invertible neural network [2] is not necessarily robust to adversarial attacks (the first meaning of robustness) but preserves all the input characteristics (the second meaning of robustness). 
I also hope the paper could have done the experiments on more datasets since there exists some evidence on the unreliability of evaluations on citation networks [3].  However, I do not think this point is critical since the paper did a great job of evaluating the robustness in various aspects and they all show consistent improvement.  
Minor questions and suggestions: 
- The acronyms are slightly confusing to understand at first sight, since they first appear at the equations without any information on what the letters stand for.  Something like a "variable power network (VPN)" would make the paper more pleasant to read.
- In the r-GCN framework, there might be an edge case where the powered graph is almost identical to another graph. Would there be any justification for avoiding this?
- In the r-GCN framework, the terminology distillation is slightly confusing. Was this choice of word used for making a connection to the knowledge distillation [4]? How is the knowledge distilled between graphs? 
References
[1] Bojchevski and Günnemann. Adversarial attacks on node embeddings via graph poisoning. ICML 2019
[2] Jacobsen et al., i-RevNet: Deep Invertible Networks. ICLR 2018 
[3] Shchur et al., Pitfalls of Graph Neural Network Evaluation, Arxiv 2018
[4] Hinton et al., Distilling the Knowledge in a Neural Network, Arxiv 2015