Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes a simple but interesting new graph sampling method for graph neural networks, called “deep GNN, shallow sampler”. Centered on the target nodes, they only sample shallow subgraphs within $L_0$-hop neighborhood and then run an $L$-layer GNN ($L>L_0$) on these subgraphs and aggregate their embeddings.  In this way, they can limit the message passing only within a shallow neighborhood to exclude noisy nodes; and they can also improve the expressivity by using deep GNN. To my understanding, the two most similar works are GraphSAGE and GraphSAINT. Compared to GraphSAGE, it samples the subgraphs instead of just $l$-hop nodes (it means they may contain more edges/circles), and it can be more expressive; compared to GraphSAINT, it requires the samples to be centered around target nodes and shallow, and it also changes the way of subgraph ensemble and makes it applied to the testing phase. 
In general, I think this paper has concentrated contributions and it could be impactful in practical use, but I still have some concern.
1.	When the authors compare the expressivity with “shallow GNN, shallow sampler”, it seems to me that $L=L_0+1$ is enough (we cannot have edges with distance more than $L_0+1$ to the target node). Adding more layers of GNN does not help with the expressivity. Even if my assumption is false and adding more layers is helpful, the authors also need to do more sensitive analysis on the impact of different numbers of GNN layers.  
2.	Experiments: 3-layer or 5-layer GNN can be regarded deep, we know directly running the original model does not perform well due to the over-smoothing issue. However, there are many tricks to solve it, such as Jumpingknowledge, Skip Connection, DropEdge. I think the baseline models should use one of these tricks to make the accuracy comparison more reasonable, and it will also be interesting to see whether these tricks are necessary for the proposed model. 
3.	One of the main advantages of graph sampling is its efficiency. In the experiments, the authors show the computation cost of each target node. This is OK but it seems to me that showing the running time is a more intuitive and better way. Also, it is better to add the comparison with GraphSAINT in terms of running time or epochs (e.g. adding the GraphSAINT results in Figure 2).

review_title: Interesting paper but some concerns

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a new extension of GNNs to deep GNNs, which use subgraphs to keep the computational costs low for training large graphs. It addresses the two main reasons that GNNs have not previously been extended to deep GNNs: expressivity and computational cost. Increasing the number of layers in a GNN leads to averaging over more nodes, which in turn collapses the learned embeddings. The paper claims that using shallow graphs instead of the full graphs avoids this oversmoothing issue. Additionally, using the full graph is computationally expensive since the neighborhood sizes grow with the number of neighbors. Using shallow subgraphs instead allows the size of the neighborhoods to remain constant as the number of layers increase. To this end, the paper presents SHADOW-GNN, a Deep GNN with shallow sampling. They extend this framework to GraphSAGE and GAT models and show that it improves performance over the original model with a lower computational cost. Overall, this method seems well-motivated, and both theoretical and empirical results support their claims. There are a few points on which clarification from the authors would be helpful. 

Strengths: 
++ The paper presents 3 motivations - (1) shallow neighborhood is sufficient to learn graph representation (2) it is necessary to reduce over smoothing issues (3) One still needs a deep GNN model to learn effectively form the shallow neighborhood - and it supports these claims by providing examples and formal proofs in the form of Proposition 3.1, Theorem 3.2, and Theorem 3.3, respectively. 

++ The paper recommends using two main samplers for sampling the shallow neighborhoods of a node - (1) $k$-hop sampler, which randomly selects $b$ neighbors and (2) Personalized PageRank (PPR) sampler, which uses the induced subgraph from the largest PPR scores $\pi$ for a node. According to the paper, both these methods are lightweight and scalable

++ The method is applied to extend GraphSAGE and GAT models and the paper presents empirical results for 5 different datasets. The results are presented in terms of classification performance (F1-score) and computational cost (Inference cost). Benchmarked against 5 baseline models (including a subsampling algorithm), the SHADOW extension gives SOTA performance at a reduced computational cost. 

++ The ablation study in the paper, further demonstrates that using an ensemble of subgraphs improves performance and is feasible using the SHADOW framework. 

++ The paper is well written and does a good job of putting the work in context and motivating the problem. 

Weaknesses:
-- The hyperparameters of the sampling algorithms, while mentioned in the Appendix tables, are not included in the tuning descriptions. I am curious to know if and how these hyperparameter choices affect the performance-cost tradeoff. 

-- Is there a performance-cost tradeoff for the subgraph ensemble setting suggested by the paper?

-- Description of the inference cost calculation would be useful. 

-- While the paper mentions two other extensions - SHADOW-GCN and SHADOW-GDC, the results do not include them. Is there a reason for that? 

Minor comments:
- Labeling Figure 1 with $v$ and $v'$ would make the example much clearer
- The transitions between the theorems and the discussions are sometimes hard to follow. More connections between notation and interpretation would be helpful.
- The “budget” term in the Appendix tables has not been connected to the hyperparameters of the sampling algorithms


review_title: The paper presents a shallow graph sampler combined with a deep graph neural network framework to train large graphs. Overall, this method seems well-motivated, and both theoretical and empirical results support their claims. There are few poins on which clarification from the authors would be helpful. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
To address the oversmoothing problem and reduce the computational cost of GNNs, this paper proposes to train deep GNNs with shallow subgraph samplers. The following two theoretical proofs provide insightful motivations of Shadow-GNN: (1 )Obtaining node embeddings within shallow subgraphs can avoid oversmoothing; (2)Deep GNNs are strictly more expressive than a shallow one. Experiments are performed on five different graph datasets with 3 and 5 layer GNNs coupling with a k-hop sampler or a Personalized PageRank (PPR) sampler.

Pros:

+ The paper is well-presented including nice illustrations and good examples;
+ Theorem 3.2 and Theorem 3.3 provide nice motivations of designing shallow subgraph samplers and deep GNNs respectively;
+ Variants of subgraph samplers and architectural extensions are discussed thoroughly, e.g., k-hop sampler, PPR sampler, subgraph ensemble and sampling the reconstructed graph.

Cons:

- Regarding Theorem 3.3 and the example in  Figure 1, It seems for a L-hop subgraph L+1-layer GNN has enough expressivity. In other words, do we need a deeper L’-layer GNN with  L’ > L+1? Or does a L’-layer GNN with  L’ > L+1 strictly more expressive a L+1-layer GNN? If not, it can not prove we need models deeper than L+1 layers for learning on a L-hop subgraph.
- Proposition 3.1 and Theorem 3.2 show a normal GNN suffers from over-smoothing as the number of layers approaches infinity but SHADOW-GNN does not. However, they are not well validated in the experiments for the following two reasons: (1) the assumed GNN formulate $\mathbf{M} = \text{lim}_{L\to \infty} \widetilde{\mathbf{A}}^{L} \mathbf{X}$ is very different from SAGE  and GAT used in the experiments; (2) the number of layers experimented are 3 and 5 layers which are far from "deep" compared to the infinite layers condition. Thus, it would be great to have experiments to bridge the gap between the theory and the practice. For example,  training a SGC (Wu et al., 2019) model with more than 20 layers to show the effectiveness of  Shadow-GNN would be interesting.
- Only comparing the inference cost of one node is not fair. For Shadow-GNN, each node will need to build one subgraph for the inference. This seems to be very computationally heavy. It would be great if there is a comparison of the inference time on the whole graph.

Minor Comment:
* The terms of Shadow-GNN and Shadow-GCN are used inconsistently. 

References:
* Wu, F., Souza Jr, A.H., Zhang, T., Fifty, C., Yu, T. and Weinberger, K.Q., 2019, January. Simplifying Graph Convolutional Networks. In ICML.


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

Post rebuttal Comments: 

Thank the authors for the response. After reading the rebuttal, I decided to change my rating to 5 for the following reasons:

* Theorem 3.3 in the original manuscript has a major flaw which is also mentioned in the review of reviewer 3. The remedied theorem is considered as a substantial change compared to the original one.
* Experiments do not fully justify the superiority of the proposed method in training deep GNNs. The performance on ogbn-product degrades when the depth of GNNs goes to 15. It is not clear whether shallow subgraph samplers really help with training "deep" models. 
* The empirical results are not strong enough to support the theoretical claims. The best results achieved by shaDow-GNN on ogbn-arxiv and ogbn-product are 72.28 and 80.09 which rank 15th and 9th respectively on the OGB leaderboard. The results should be improved before being accepted.

review_title: Good theoretical insights but a weak empirical validation of proposed theories

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposed a simple technique to improve the performance of message passing neural network models. The proposed idea is relatively simple, instead of applying GNN to the entire graphs, which leads to the over smoothing problem with enough number of layers, for each node, the model samples an ego-network of the target node, from which GNN can model representation of the node. The experimental results show the competitive results of the proposed method while preventing the over smoothing issue. Below, I listed some of my concerns about the paper:

- Theorem 3.3 seems incorrect. The statement ' L'-layer GNN is strictly more discriminative than the 1-WL test' seems incorrect. If you run WL test with L iteration, this statement seems okay, however, in general, when you run the WL test, the minimum number of iteration is not set to L. The paper referred to in the proof also mentioned that only GNN is theoretically as discriminative as 1-WL when the depth of the layers is sufficient enough [Xu et al. 2018a] 

- The paper emphasizes the necessity of deep architecture whereas in experiments 3-layer and 5-layer architectures, which seem not very deep, are used. It would be interesting to see how the performance changes as one increase the depth of layers.

- Experimental setup: Ablation study shows the best performance when multiple samplers are used, whereas the main results do not contain the result of the ensemble.

- Consistency between table1 and table 2: In table 1 2-hop sampler is used to show the best performance while in the ablation study 1-hop sampler is used. Is there a reason why different k-hop samplers are used in these cases?


review_title: Review of Deep Graph Neural Networks with Shallow Subgraph Samplers

Meta-review: In this paper, the authors propose a simple yet interesting new graph sampling method for graph neural networks.  It addresses the two main problems that GNNs have not previously been extended to deep GNNs: expressivity and computational cost.  Through experiments, the authors show the effectiveness of the proposed algorithm. 

Overall, the proposed approach is interesting.  However, the reviewers were still not convinced by the response, and the paper is still below the acceptance threshold.  I encourage the authors to revise the paper based on the reviewer's comments and resubmit it to a future venue. 
Decision: Reject