Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a graph convolutional operator based on graph powering and applies it to GCN architecture to improve the performance and robustness. This work is mainly motivated by the paper (Graph powering and spectral robustness, Abbe et al., 2018). The authors introduce the graph powering to graph convolution neural network domain to replace the original Laplacian operator. They further propose a graph sparsification/pruning strategy on the powered adjacency matrices in order to reduce the complexity and increase the robustness against adversarial attacks. They also provide theoretical analysis to prove that the proposed powering operator and subsequent methods have some spectral properties and theoretical feasibility. However, some conclusions are limited to the ideal situations or seem subjective. Extensive experiments are conducted to show better or comparable performance in both benign and adversarial situations. 

There are some concerns that need to be addressed or clarified:
A major concern is that the theoretical analyses in this paper are limited to graphs sampled from the SBM model. It is unclear how these analyses can be generalized to real graphs. Furthermore, the theorem 3 and proposition 5 are even limited to SBM model with 2 communities, which makes the analyses less convincing. 

Some of the arguments in the paper might be imprecise. For example, in Section 1.1, when discuss “why not graph Laplacian?”, a small spatial scope is claimed to be problematic. Although, it is correct for the GCN (Kipf & Welling, 2017), the powered Laplacian (mentioned earlier in the same section) does have a broad spatial scope.      

It would be better if the authors could provide more details about the sparsification. Specifically, how to choose the threshold (adaptively). 

In the performance part of Section 4.2, the improvement of the performance by replacing Laplacian with VPN is marginal (compared with the original GCN). Furthermore, the performance of VPN is close to or sometimes worse than the baseline RGCN. 

Suggestions:
In the Informative and robust low-frequency spectral signal part of Section 4.3, it would be better if the authors can clarify the experiments setting. Is it using the low-frequency part (first few eigenvectors) to recover the signal and then using the recovered signal to perform the classification task? The titles of Figure 7 and Figure 8 are a little bit confusing. 


Some minor problems:
There are many typos such as: “with the presence of absence of edges”, “normalizating”, “asymptotoic”, “benigh”, “ajdacency”, “sensitve”, “adajacent”, “one of the network”, etc.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors study the classic GCN and proposed the new convolution operator with wider spatial scope and robust properties. The proposed models could improve the accuracy in both benign and evasion setting on synthetic, ie., SBM dataset and real world benchmark graphs. However, I have the following questions for the authors:

1. In the paper, compared to the classic GCN, the authors replace the adjacent matrix $A$ with the proposed “variable power operator”. However, the proposed “variable power operator” is very similar to “k-th order polynomials of the Laplacian”, which has been fully discussed in [1]. Could you distinguish the differences between the proposed “variable power operator” and “k-th order polynomials of the Laplacian”? And as the authors proposed to use high-order matrix  some recent models which also explores high-order matrix such as [2, 3] may also need to be selected as baseline methods. 

2. As it is clearly defined in [4,5], all the five attack methods adopted in the paper are poisoning (training time) attacks methods. However, the proposed models are claimed to defense against evasion (testing) attacks. Why choose the poisoning attacks methods here? The experiment with the evasion attack method [6] is suggested to be added. 

3. When the proposed models are applied to other kind of graph data, ie., social network, according to the small world theory, the "variable power adjacency matrix" would be very dense when $r>2$ with 2-layer GCN. The efficiency of the proposed might be an issue. Is it possible to add one experiment with demonstrating the running time on the real world social network?

[1] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in neural information processing systems. 2016.
[2]Wu, Felix, et al. "Simplifying graph convolutional networks." International Conference on Machine Learning. 2019.
[3] Abu-El-Haija, Sami, et al. "Mixhop: Higher-order graph convolution architectures via sparsified neighborhood mixing."  International Conference on Machine Learning. 2019.
[4]Zügner, Daniel, and Stephan Günnemann. "Adversarial attacks on graph neural networks via meta learning." In ICLR 2019.
[5]Bojchevski, Aleksandar, and Stephan Günnemann. "Adversarial Attacks on Node Embeddings via Graph Poisoning." International Conference on Machine Learning. 2019.
[6] Dai, Hanjun, et al. "Adversarial attack on graph structured data." International Conference on Machine Learning. 2018.



review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 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
review_title: Official Blind Review #2

Meta-review: The paper identifies the limitation of graph neural networks and proposed new variants of graph neural works. However, the reviewers feel that the theory of the paper have some problems: 
1. A major concern is that the theoretical analyses in this paper are limited to graphs sampled from the SBM model. It is unclear how these analyses can be generalized to real graphs. 
2. The robustness definition is inconsistent. 
Furthermore, more extensive experiments on more datasets will also be helpful. 
Decision: Reject