Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This is an interesting work on GCN. The idea is to form local graph for each node using PPR-Nibble, a local clustering method proposed before, and then use transformer on top of the local graph as encoder for node classification and link prediction. The algorithm is simple and easy to understand. I have several concerns for this paper:

1) It seems that the local clustering+transformer encoder performs best, while it is hard to tell whether local clustering is the key to this improvement. In Table 2, local clustering + GCN encoder performs even worse than most of GCN methods, which might indicate the local clustering is not useful. In other words, what if other comparing GCN methods are also using transformer encoder? Without this study, it is hard to tell what is the novelty of this paper and whether the local clustering is useful.

2) What is the time complexity of this method? It seems the proposed method is very computation expensive. As it needs to form transformer for each node in the graph, not even to mention the time for PPR-Nibble for each node as well. This method might be even slower than GCN itself.

3) All the theorems are not derived by this paper, but from other papers on PPR-Nibble. Will these theorems have assumptions about the underlying graphs? And will this theorem works for the graphs in the experiment parts? Do the proposed method only work with nodes with small numbers of neighbors? 

4)  Besides PPR-Nibble, there are many local clustering methods or even using on-line clustering so that the whole graph is not needed to fit into the memory to form the clustering, it will be interesting to see how various clustering methods work under the framework. 

 
review_title: interesting work, but needs more study

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:
This paper proposes to utilize local clustering to efficiently search for small but compact subgraphs for Graph Neural Networks (GNN) training and inference. The existing PPR-Nibble is adopted for the local clustering search. Experiments validate the effectiveness of the proposed method.

##########################################################################

Pros:
+ The paper is clear and well organized. 
+ The idea of using local clustering to design a lightweight, effective and scalable GNN framework is interesting.  
+ The analysis of the connection between GNNs and local clustering is also interesting. 
+ Extensive experiments are conducted to validate the effectiveness of the proposed method.

##########################################################################

Cons:
- One major concern about the paper is the lack of novelty. Although the idea of using local clustering is very interesting, it is straightforward to apply an existing local clustering algorithm into GNN especially considering the existing methods that utilize the global graph partition.   

- In the introduction, it is claimed that the graph sampling techniques may lead to the high variance issue, while from the experiment, we can see that compared to SOTA sampling methods (e.g. GraphSAINT), the proposed method has larger variance actually. The reason for this should be given.

- The advantage of the proposed method over the methods based on global graph partition (e.g., ClusterGCN) is not well illustrated. 

- In Table 6, only the result with "LCGNN-Transformer" is provided, and it is not clear whether the improvement is caused by the transformer encoder. The comparison of the learning paradigm is missing. For better comparison, especially with ClusterGCN, the result of "LCGNN-GCN" is expected. 

Minor issues:
- In the paper, it is claimed that "Compared to full-batch GNNs, sampling-based GNNs and graph partition-based GNNs, LCGNN performs comparably or even better...", while from the experiments, we can see that it can be worse for some tasks. Moreover, the improvement may be not mainly caused by LCGNN itself. It is better to make this clearer.

##########################################################################

Questions during the rebuttal period:
Please address and clarify the cons above.
review_title: Official Blind Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: [Summary]
In this paper, the authors study the connection between GNNs and local clustering, and find that short random-walks in GNNs have a high probability to be stuck at a local cluster. Based on this, they propose a light and scalable GNN learning framework called LCGNN, which first adopts the local clustering method PPR-Nibble to partition full graph into subgraphs, then use GNN modules on subgraphs for training and inference. The authors evaluate LCGNN on six OGB datasets, and the proposed approach outperforms the competitors on node classification and link prediction tasks.

[Pros]
+ The paper is well organized and easy to follow.
+ The idea of incorporating local clustering algorithms for GNN learning is simple but effective in terms of scalability.

[Cons]
- The proposed method is somewhat incremental since it only adds a local clustering step (with an existing clustering method) before adopting GNN models.
- The experiment is not very sufficient and supportive. 
  1. From Table 2, it seems that the improvement of incorporating local clustering (comparing LCGNN-GCN/LCGNN-SAGE with naïve GCN/SAGE) is not very large, and we could not find how much the local clustering improves Transformer. Similar problems appear in Table 3, 4, 6 – most performance improvement seems to come from the adoption of Transformer.
  2. How do clustering hyperparameters $\alpha$ and the maximum cluster size affect the results?
  3. No visualization for the clustering results or the learned node embeddings, which could help understand the effect of local clustering, is presented. 
- Time and space complexity of the proposed framework is not provided. Intuitively the proposed method might enjoy better time and space complexity than existing methods, but some theoretical analysis or runtime evaluation would be better to illustrate the main claim of this paper.
- Could LCGNN handle the situation when nodes and edges are constantly added and removed?
- The authors claim that ‘the locality nature of LCGNN allows it to scale to graphs with 100M nodes and 1B edges on a single GPU’ but use 8 NVIDIA Tesla V100 in their experiments. Some results or explanation might be helpful to support this claim.
- There are many typos to be corrected.
  (a) Page 1: covers => cover
  (b) Page 2: we concludes => we conclude
  (c) Page 2: importance roles => important roles
  (d) Page 4: the the small world phenomenon => the small world phenomenon; staring in S => starting in S; I.e., => i.e., (cannot be used at the beginning of the sentence); The key point of Theomre 1 => The key point of Theorem 1; In this works => In this work
Other minor issues: It would be better to highlight the second best value in Table 2.

review_title: A good scalable GNN framework but somewhat incremental

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary: 
The authors proposed to first extract a subgraph $G_u$ for each node $u$. Then use GNNs to extract the hidden representation $h_u = GNN(G_u)$. The subgraph extraction uses PPR-Nibble with is a conductance based local clustering method. 

Pros:
1.	The model seems to be more efficient compare to GNN with global clustering method such as Cluster-GCN.
2.	Using local clustering method to determine the subgraph for each node might be better than random neighborhood sampling in some cases.

Cons:
1.	The intuition on using short random walk is problematic. (See detailed comments)
2.	The experimental results are insufficient to verify the proposed method.
3.	Insufficient related work on local clustering and PageRank-based methods.
4.	While the authors claim that they have theoretical analysis, all stated theorems are from the other papers. I do not aware of any theoretical contribution as claimed by the authors. 

Detailed comments:

The main weakness of the paper is the claim that short random walk is sufficient to extract topology information from graph. This contradicts to both [1] and [2]. In [1], the authors used Personalized PageRank (PPR) to build their GNN (APPNP) which shows that large propagation step is helpful ($K=10-20$). Notably, they show that using $K\geq 10$ gives significant improvement on Cora and PubMed dataset for node classification problem compare to using $K\leq 5$. On the other hand, the authors of [2] study the generalized PageRank method for local clustering (seed-set community detection) problem. They show that using large step propagation ($K\geq 10$) leads to better local clustering performance compare to small steps. These works show that using merely short random walk is insufficient to fully extract the topological information from graphs and thus the claim by the authors seems questionable to me.

The other weakness of this paper is their experimental results are insufficient to verify the proposed method outperforms the sampling-base method. For example, in Table 2 the test accuracy of LCGNN-SAGE is actually lower than GraphSAINT (SAGE aggr). Even if we compare LCGNN-GAT with GraphSAINT(GAT-aggr) the gain is not obvious. The model proposed by the authors that has the best performance is LCGNN-Transformer. However, it is not clear whether the performance gain is due to the local clustering procedure or the transformer.

Minor comments:
As the authors mentioned, the local clustering methodology is only reasonable for graphs that has low conductance with respect to all "cluster" (nodes with same label). This is exactly the "Homophily principle" which is true for most of the popular benchmark datasets such as citation networks (Core, Citeseer and PubMed). However, as pointed out in [3], there are also practical graphs that are heterophilic or low homophily. Although this is not the main theme of this paper, the existence of heterophilic graph should not be ignored.

Reference:

[1] “Predict then Propagate: Graph Neural Networks meet Personalized PageRank,” Klicpera et al., ICLR 2018.

[2] “Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection,” Li et al., NeurIPS 2019.

[3] “Geom-GCN: Geometric Graph Convolutional Networks,” Pei et al., ICLR 2020.

review_title: Interesting idea but the methodology and evaluation are unsatisfying.

Meta-review: The paper considers using local spectral graph clustering methods such at the PPR-Nibble method for graph neural networks.  These local spectral methods are widely used in social networks, and understanding neural networks from them is interesting.

In many ways, the results are interesting and novel, and they deserve to be more widely known, but there are several directions to make the work more useful to the community.   These are outlined in the reviewer comments, which the authors answered partially but not completely satisfactorily.  Much of this has to do with explaining how/where these (these very fundamental and ubiquitous) methods are useful in a particular application (GNNs here, and node embeddings below).  An example of a paper that successfully did this is "LASAGNE: Locality And Structure Aware Graph Node Embedding, E. Faerman, et al.  Proc. 2018 Conference on Web Intelligence."  (That is mentioned not since it is directly relevant to this paper, but since it provides an example of how to present the use of a method such as PPR-Nibble for the community.
Decision: Reject