Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper aims at improving the computational efficiency of GCNs to effectively capture information from the larger multi-hop neighborhood. Conventionally, GCNs use information from all the neighbors up to a certain depth; in which case, with consideration of each further hop, the neighborhood size increases exponentially. To avoid the exponentially increasing memory and computational footprints of GCNs as a result of an exponential neighborhood expansion, this paper proposes a (hop) layer-wise sampling procedure that reduces the complexity to a linear factor. The sampling of nodes at a layer, ‘l’ is based on the transmission probabilities of the nodes at layer ‘l’ and their immediate neighbors sampled earlier in layer ‘l+1’ from both directions of diffusion. The proposed model is based on Graph ATtention Network (GAT) which is adopted here to aggregates neighborhood information only over the nodes sampled with their bi-diffusion sampler. 

Strengths of the paper: The paper intuitively suggests that some of the popular sampling-based scaling approaches for GCN may not be powerful enough as they don’t consider bi-directional influences. 

Weaknesses of this paper:
- Novelty: The idea is incremental. The paper is similar to the layer-wise sampling model, AS-GCN where instead of the base GCN model this paper uses GAT coupled with its proposed bi-diffusion sampler. 
- Experimental results: 
    - (a) Inconsistent baseline results: The performance of baselines reported here on standard train/test/val splits are significantly lower than the ones reported in the original papers. For ex: with FastGCN the original papers report 0.88 and 0.937 on PPI and Reddit which is ~0.03 more than what is reported here. With the case of AS-GCN, the original performance scores are superior to the proposed model in the paper, however here they are reported ~0.04 scores lower. Since the codes for all these baselines are available, it is only fair to use the original implementation; if not, it is important to replicate the original results before using a different implementation. 
    - (b) Variance and statistical significance results are missing
    - (c) Cluster-GCN though discussed, an experimental comparison with it is missing. Reported results from Cluster-GCN paper on Reddit and PPI suggests a superior performance over BLS-GAT. 
    - (d) BLS-GCN missing. This would be a fair comparison to FastGCN and AS-GCN. 
    - (e) Experimental comparison with Jumping Neural network (Xu et al) is missing to understand how the proposed solution improves over existing solutions for over-smoothing. It would be helpful to even couple it with Fast-GCN/AS-GCN sampler to better understand the benefits of this paper. 
- Writing:
    - The paper is not well written. Though there are only minor grammatical mistakes, multiple sections of the paper are not clear and are hard to read because of complex sentences and long paragraphs. 
    - Some of the terminologies used are not clearly described and are not explained prior to the usage. Some of them are neighbor-explosion, over-expansion, the width of neighborhood expansion, local correlations, etc, In some places, over-expansion is used to refer only neighbourhood explosion or only over-smoothing and both. It will be comprehensive if it is grounded. 
    - Numerous claims/ideas put forth in this paper are abstract and intuitive. The intuitions should be backed with proper support. Some of the major concerns are:-
        - (a) proof/arguments to show that layer-wise sampling may lead to sparse mini-batches and how does that in-turn impact over-smoothing 
        - (b) how does the proposed model avoid over-smoothing?
        - (c) why sub-graph methods are not effective ? .. etc
    - It is true that using a fixed neighborhood weightage function as with GCNs may not be optimal. However, the discussion made on GCN and its lack of an appropriate normalization/ neighbourhood weightage function is incorrect. GCNs aggregate information from further neighborhoods according to the respective higher-order diffusion laplacian matrix entries. You can see that by simply removing the nonlinearity+weights and recursively expanding the GCN equation. 
- Other comments:
    - Provide the complexity of the proposed model (GCN + sampler) and compare it with other sampling approaches. 
    - The connectivity structure + signal on the nodes of the graphs is the data that is being convolved and they are not the filters. The weights being learned are the filters. 
    - In Eqn: 2, I believe you are providing an equation for GS-GCN. In which case the fraction should be N(v)+1/ (N_s(V)+1) to match the original model/implementation for GraphSAGE (GS) paper. 
    - I think the summation in the denominator for AS-GCN following Eqn: 3 should run over V instead of V_l.
    - It will be helpful to run the model on directed datasets to see improved benefits of bi-diffusion sampling. 
    - Need more discussion about AS-GCN, Cluster-GCN and Jumping Neural networks (Xu 2018b)
   
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: The authors propose a sampling method for graph neural networks which is applicable to very large graphs (where not all nodes can be kept in memory at the same time). The method uses the transition probabilities of a random walk to construct a sampling probability of the nodes in the lower layer given the nodes in the upper layer. Since this samples nodes which can be one or multiple hops away, an attention mechanism is used to weight updates from connected nodes. Experiments show that this method is promising.

In its current state I would be inclined to reject this paper, but I could be convinced otherwise. The idea, although relatively straightforward, seems powerful and the experiments seem to support it. My main concern is that paper is not well written. It contains long meandering paragraphs (e.g., all of section 2 is a single paragraph) with high-level intuitions and ill-defined terms, making it hard to read. Similarly, results are badly presented. For example, table 3 should probably be given as relative speedups with the best results bold-faced rather than a long table with numbers. Illustrations would also be very helpful to provide an intuition about formulas 4, 5, and 6. Moreover, a simple ablation study is necessary (e.g., using bi-diffusion based sampling, but using constant weights instead of the attention mechanism, or vice-versa, using the attention mechanism with other types of sampling). It is currently impossible to disentangle the effects of the two parts of BLS-GAN.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper was an interesting read. The idea of this paper is to challenge the use of Laplacian matrix in GCN. Indeed, typical GCNs use the same adjacency matrix across different layers. In particular, this typically leads in Euclidean case to learning isotropic filters (because the euclidean Laplacian is isotropic). Consequently, such filters have no selectivity at all.(in the Euclidean case, that could correspond to the selectivity to orientations - no selectivity would lead to a difference of Gaussians) Furthermore, for non-sparse graphs, computing the iterations of the Laplacian matrix can require a significant computational power.

In order to tackle this problem, the authors introduced a diffusion factor to sample a set of nodes to build some GCN filters with finite support. At a given layer, the diffusion factors is based on the interaction with other layers of the GCN. Then, a layer-wise attention mechanism that will allow to weight the graph connectivity of the sampled nodes is used, which is supervisedly learned. Each numerical experiments lead to a significantly better accuracy, while the method trains in reasonable time. This is thus numerically convincing. Furthermore, this method is, to my knowledge, new.

The paper is clearly written, the numerical experiments are convincing and the authors address a difficult problem with a simple method: I'm leaning toward an "Accept".

Minor: 
- Tables 2/3 are hard to read.
- The paper is 10 pages long, yet this was an interesting read.

Post-discussion:
The other reviewers have made some good point, and thus I decided to lower my score. I still find the paper address an interesting problem.
review_title: Official Blind Review #2

Meta-review: This paper addresses the challenge of time complexity in aggregating neighbourhood information in GCNs. As we aggregate information from larger hops (deeper neighbourhoods) the number of nodes can increases exponentially thereby increasing time complexity. To overcome this the authors propose a sampling method which samples nodes layer by layer based on bidirectional diffusion between layers. They demonstrate the effectiveness of their approach on 3 large benchmarks.

While the ideas presented in the paper were interesting the reviewers raised some concerns which I have summarised fellow:

1) Novelty: The reviewers felt that the techniques presented were not very novel and is very similar to one existing work as pointed out by R4
2) Writing: The writing needs to be improved. The authors have already made an attempt towards this but it could be improved further
3) Comparisons with baselines: R4 has raised some concerns  the settings/configurations used for the baseline methods. In particular, the results for the baseline methods are lower than those reported in the original papers. I have read the author's rebuttal for this but I am not completely convinced about it. I would suggest that the authors address this issue in subsequent submissions

Based on the above reasons I recommend that the paper cannot be accepted. 

 
Decision: Reject