Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper utilizes Randomly Wired architectures to boost deep GNNs. Theoretical analyses verify that randomly wired architectures behave like path ensemble and it enables adaptive receptive field. Experimental results on three non-popular datasets demonstrate the strength of the proposed model. Overall, the idea is interesting. Yet this paper can be made better through the following aspects:

1. This paper contains confusing equations and notations. For example, in Eq 1., why w_ij equals \sigma(w_ij). What's the meaning of domain nodes and how do we connect the architecture nodes and the domain nodes. What's the definition of \mathcal{A}?
 
2. This paper only proposes the recursion formula but omits some basic definitions, i.e. the definition of h^{(i)}. Where does the recursion start?  Is there an initialized h^{(0)}?

3. The algorithm framework is not clearly depicted. How do R-GCNs accomplish the graph propagation process?
 
4. Insufficient experimental comparisons. How do R-GCNs and GCNs perform when L=2. How do R-GCNs perform on standard node classification datasets, such as Cora, Citeseer, and Reddit, since deep GCNs fail particularly on node  classificaiton. How do R-GCNs perform against other deep frameworks such as APPNP and JKNet, both of which resort to more sophisticated skip connections than ResGCN.

#############post-rebuttal############

I have carefully checked all other reviewers' comments, the authors' response, and the revised version. Thank the authors for their detailed feedback. They have addressed my concerns on the unclear presentation. However, joining the comments from other reviewers (particularly R3), I still think there are two major issues that prevent me from further increasing my score.

Q1. It is still unclear why the proposed model can tackle the over-smoothing issue in existing deep GCNs.

This paper has theoretically revealed the benefit of adaptive ensemble paths towards better trainability. Given the claim in Introduction, it is still unclear why such benefit can be used to relieve over-smoothing, particularly due to the missing analysis of the output dynamics. As already pointed out by R3, [3] has set up a nice notion of framework on explaining how over-smoothing happens and why deep GCN fails. It is a pity that this paper has not put their analyses into this framework and discussed the relation with the over-smoothing issue. Actually, a more in-depth discussion of over-smoothing on general GCNs (including ResGCN, APPNP) has also provided in an arXiv preprint paper [4]. It does show that the residual networks are capable of slowing down the convergence speed to the subspace and thus alleviating over-smoothing. Since the idea of random wiring is initially proposed in CNNs, the contribution of this paper that we expect is to answer how this idea can be utilized to solve the specific weakness in the graph domain.

Q2. The experimental evaluations are still unconvincing.

It is thankful that the authors have additionally provided the performance of SIGN and APPNP in the revised version. Yet, the reported accuracies of APPNP seem weird and much worse than other baselines. I do not agree with the authors' response that APPNP is not intended to address the over-smoothing problem. As experimentally shown in [5] and theoretically analyzed in [4], keeping the connection between each middle layer and the input layer is able to prevent the output from converging to the subspace caused by over-smoothing, and thereby deliver desired performance with the increase of depth. As this paper has conducted experiments on a newly-public benchmark under inconsistent experimental setting up (raised by R3), it is hard to justify the significance of the proposed idea compared with previous methods, specifically given the irrational observations on APPNP.

Hence, I still believe this paper is below the acceptance line. 

[3] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020. 
[4] Tackling Over-Smoothing for General Graph Convolutional Networks, arXiv 2020. [5] Simple and Deep Graph Convolutional Networks, NIPS 2020.
review_title: More details are needed.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:

The paper proposes a new method for building graph convolutional neural networks. It shows, that during the building of the network, instead of stacking many layers and adding the residual connection between them, one could employ a randomly-wired architecture, that can be a more effective way to increase the capacity of the network and thus it could obtain richer representations. The proposed method is an interesting direction in the field of graph convolutional neural networks. The new method could be seen asa generalization of the residual networks and the jumping knowledge networks.

=============================================================================

Pros:

1. The paper proposes a novel, randomly-wired architecture for building the graph convolutional neural networks. Moreover authors analyze proposed randomly-wired architectures and show that they are generalizations of ResNets.

2. The authors provide the theorethical analysis of the radius of te receptive field of GCN. They show that by using randomly-wired network, together with trainable weights on the architecture edges and sequential path, the network could tune the desired size of the receptive fields to be merged to achieve an optimal configuration for the problem.

3. The authors propose the MonteCarlo DropPath regularization - a novel regularization method for randomly-wired architectures, that is related to dropout, however is carried out at a higher level of abstraction.

4. The authors provide a comprehensive experimental results of the proposed method - they compare various GCN architectures, created on traditional and randomly-wired way, on three representative tasks - graph regression, graph classification and node classification. Moreover they show, that randomly-wired GCNs gets better results than ResNet GCNs on almost all tested cases. Moreover the authors shows that deeper randomly-wired GCNs always provide bigger gains with respect to their shallow counterpart than ResNet GCNs.

=============================================================================

Cons:

1. Figure 1 is not clear to me. I am not sure what the colored point cloud is about. The authors should consider rewriting a description of this figure.

2. In the final version of the paper, the ablation study should be reported on all datasets (however the authors remark that, they do not report results on this version of paper due to space constraints).

3. I would like to see the more extensive analysis of DropPath, e.g what are the scores for different levels of the drop probability.

=============================================================================

Questions during rebuttal period:

1. Why the authors use different types of GCNs during the ablation study?

=============================================================================

=============================================================================

Reasons for score: 
 
Overall, I vote for accepting this paper. The idea proposed by the authors is novel and confirmed theoretically and experimentally.
My major concern is about ablation study and the clarity of one figure. Hopefully the authors can address my concern in the rebuttal period. 
review_title: A nice paper about a randomly-wired GCNs

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

This paper extends the technique of randomly wired neural nets from [1] to Graph Neural Networks and show that they perform better than tradtional GNN architectures. They demonstrate the improved capacity of this architecture via a number of experiments on the benchmark in [2] and ablation studies.

Reason for score:

Pros:

  - The paper evaluates the technique on a widely accepted benchmark for Graph Neural Networks.
  - Diminishing model performance in GNNs with increased number of layers is an important problem and it looks like randomly wired GNNs provide monotonically increasing performance for up to  L = 32
  - The models generated using random wiring outperform the baseline model across a large number of settings such as the graph convolution operator used and the number of layers
  - Augmenting the randomly wired networks with a sequential path is interesting.
  - Ablation experiments are extensive and convincing.
  
Cons:
 
  - The novelty is only incremental, building on the core idea from [1], but the results are strong so this is not a big issue.
  - Why didn't the paper test on other tasks from the benchmark in [2] like PATTERN and TSP? A full set of experiments would rule out the possibility that the benchmark tasks were cherry picked.
  
Overall:

  Extension of an existing method to GNNs which produces strong results. I vote to accept this paper.
 
Questions:

 - How many iterations of inference do you'll do for MonteCarlo DropPath during testing?
 
 
References:

[1] Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neuralnetworks for image recognition. In Proceedings of the IEEE International Conference on ComputerVision, pp. 1284–1293, 2019.

[2] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: 
The authors proposed to randomly wire the GNN layers. They claim it can not only resolve over-smoothing problem but also enable the varied size of receptive fields.

Pros:
1.	Really great looking graphics.

Cons: 
1.	The motivation of why should we use Erdos-Renyi (ER) graph to generate DAG for the random rewiring is not clear.
2.	How can we learn from the results of the DAG statistics (such as averaged path length) is unclear. I don’t understand how this can help us design or improve the proposed architecture.
3.	The experimental results seem inconsistent to [1], where the authors claim to follow their experiment setting.

Detailed comments:

The main weakness of this paper is its motivation. I do not see any theoretical reasoning that we should use ER graph instead of the other choice of random graph generator. The authors mention that small world and scale-free networks have been studied and use in [2], but I don’t see any detailed comparison why the ER graph is a more preferred choice. Even in the experiment section, I do not aware of any comparison which is unsatisfactory. 

The other weakness is that the “theoretical analysis” mentioned in this paper neither leads to any reasoning in model design nor guarantee in performance. What can we learn from knowing Lemma 3.1 and 3.3? How do they explain why using ER graph for random wiring is favorable? I do not even see it helps on choosing the hyperparameter $p$.

The final but most questionable part is the experiment section. The authors claim that they adopt a recently proposed GNN benchmarking framework [1]. However, the reported results are significantly different and much worse than those reported in [1]. For example, GCN ($L=16$) has 68.5% of accuracy in the experiment on CLUSTER dataset in [1] (Table 2, Node classification). In contrast, the authors report GCN accuracy for only 48.57%. Of course, the hyperparameters might be chosen differently from [1], but then the question would be why not optimize it according to [1]? Also, why not report the performance of more shallow $L$ (say $L=2$ or $4$) which is a more common choice? All these inconsistency makes me hard to believe the proposed methodology   would work.

Reference:

[1] “Benchmarking Graph Neural Networks,” Dwivedi et al., arXiv preprint arXiv:2003.00982, 2020.

[2] “Exploring randomly wired neural networks for image recognition.,” Xie et al., In Proceedings of the IEEE International Conference on Computer Vision, pp. 1284–1293, 2019.


review_title: Questionable experiment result with unclear explanation of motivation

Meta-review: This paper proposes to use randomly wired architectures [1] in the context of GNNs and introduces a method for sampling random architectures based on the Erdős–Rényi model. The authors further include a theoretical analysis and two methodological contributions: sequential path embeddings and DropPath, a regularizer. Results are reported on two graph datasets (ZINC and CLUSTER) and on GNN-based CIFAR10 image classification.

The reviewers agree that the empirical results presented in the paper are compelling. The value of the contribution largely lies in this aspect, namely the empirical analysis of an existing technique (randomly wired architectures) in the context of GNNs, in addition to several smaller empirical methodological contributions. I agree with the reviewers in that the nature of the contribution and the otherwise limited novelty calls for a more extensive and detailed empirical evaluation (ideally incl. e.g. FLOPS, wall-clock time, memory usage) across a wide range of datasets and careful ablation studies, and I encourage the authors to improve on this aspect in a future version of the paper. The theoretical analysis is interesting, but, as pointed out by the reviewers both during the reviews and the later discussion period, does not add sufficient value to the main empirical contribution of the paper to push the paper beyond the acceptance threshold and does not satisfactorily address the question of how the method addresses the oversmoothing problem in GNNs.

[1] Xie et al., Exploring randomly wired neural networks for image recognition (ICCV 2019)

Decision: Reject