Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes to control the receptive field of GNNs by extracting a small subgraph for every node, e.g. a 2-hop neighborhood. This has computational advantages since it is now easy to mini-batch nodes with their corresponding subgraphs and it allows to build deeper GNNs acting independently on each subgraph, thus avoiding oversmoothing. The paper demonstrated empirical improvements on several node classification benchmarks and a link prediction task.
main_review: - The proposed approach has computational advantages and leads to small empirical improvements, however, the main motivation is unclear. As the authors state, using $L$-hop subgraphs is equivalent to a GNN with $L$ layers. ShadowGNN allows to build models with $L' > L$ layers while keeping the receptive field to $L$ hops. I am not convinced that this is beneficial: while using more layers can be beneficial as it increases the number of parameters and overall depth, one can alternatively use a $L$-layer GNN with deeper MLPs (or ResNets, etc.) at every layer. I think it is important to conduct additional experiments to show that setting $L' > L$ in ShadowGNN is indeed beneficial as opposed to the aforementioned way of deepening GNNs. Currently, it is unclear, neither theoretically nor empirically, what is the benefit of allowing nodes to communicate with each other multiple times. In the datasets considered in experiments, since 2-hop neighborhood is sufficient to capture important information in the graph, I'd be interested to see a comparison to 2-layer GNNs with deeper feature extractors, i.e. $H^{(l)}$ can be a deeper MLP/ResNet to match the number of parameters of a $L'=5$ ShadowGNN.
- "a shallow neighborhood is necessary and sufficient for the GNN to learn well" - this is a very strong claim and I do not think that it is true. I recommend revising it and adding a discussion of the limitations of the proposed method in the context of capturing long-range dependencies. While a shallow neighborhood may be sufficient for social and citation network graphs, it could be insufficient to capture important properties of molecules in chemistry applications. The problem of designing GNNs that can capture long-range dependencies and not suffer from oversmoothing was studied in "On the bottleneck of graph neural networks and its practical implications" (2021) by Alon and Yahav.
- l342 says that $L' > 5$ can further improve accuracy, but the performance of $L' = 7$ in Table 14 in the appendix does not show any improvements.
- Could you please clarify what you mean by "a depth-3 $G_{[v]}$ differs from the 3-hop neighborhood$ in l359.

Minor:
- l63: "the a"
- l91: missing square brackets in the index
- l114: "sufficeint" -> sufficient
- l245: "we would a" - missing a verb
limitations_and_societal_impact: The authors do not discuss the limitations of their approach. The main limitation in my opinion is the strong assumption that "a shallow neighborhood is necessary and sufficient for the GNN to learn well" - this is not true in the problems where long-range dependencies are important, and where GNNs are currently underperforming due to oversmoothing. Please see the main review for more details.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work proposes a design principle (SHADOW) to enrich the expressive power of GNNs: it first extracts a localized subgraph as the fixed input receptive field to the GNN, and then the depth of the GNN can be selected separately. This work shows that the proposed design can be applied to various GNNs (e.g., SHADOW-GCN, SHADOW-SAGE, and SHADOW-GAT), and it provides theoretical analysis on the expressive power of three SHADOW-GNNs (the ones mentioned above) comparing to their original counterparts. It further conducts experiments on several large graph benchmark datasets and demonstrates the superior performance of SHADOW-GNNs.
main_review: This work proposes a "decoupling" design principle that separates the depth and scope of GNNs. The work provides some theoretical and empirical support to demonstrate the proposed design improves both the accuracy and computation efficiency. To be more specific, the work provides theoretical analysis on the expressive power of the proposed design, and hand-constructed cases where the SHADOW-GNNs are more expressive than its standard counterparts. The experimental results also show some improvements of the SHADOW-GNNs in test accuracies on ogbn benchmark datasets (6 node classification datasets and 1 link prediction dataset). The presentation of the work is very clear, and I enjoy reading it through. This work also tries to tackle two fundamental obstacles in deep GNNs: the expressive challenge and the computation, which are significant problems to be addressed in the community. 

While the work studies an important problem, my main concern lies in the EXTRACT function of the proposed principle. 
1. It seems most theorems and corollaries presented in this work are highly dependent on some appropriate EXTRACT functions (e.g., Corollary 3.2.1, Corollary 3.2.2., and Theorem 3.3). In these cases, the EXTRACT function needs to generate a localized subgraph for each of the nodes to satisfy certain properties/constraints, but it is not clear how we can obtain such an EXTRACT function without too much prior information on the given tasks. As the success of a SHADOW-GNN is greatly dependent on a good EXTRACT function, as a design principle, it is also vital to provide clear guidance on how to find/design the EXTRACT function.
2. Although the authors slightly touch on 3 possible directions to come out with appropriate EXTRACT functions: heuristic-based, model-based, and learning-based, all of them still lack practical guidance. The model-based approaches need access to the generation process of the input graphs, which might not be available in real-world tasks. The authors also provide an example of a heuristic-based approach, which is based on a hand-engineered feature (the page rank score of other nodes to the given node), and such graph metrics are often based on human insights and expertise. The learning-based approach sounds interesting but is left to future work. 
3. How does the proposed design principle differ from neighbor-sampling (e.g. [1, 2]) and subgraph-sampling approaches (e.g. [3, 4])?

Minor comment: 
- provide a more direct comparison for the reduction in computation and hardware cost with their counterparts: e.g., add new legends to Figures 6 and 7 representing the performance of the standard GNNs.

[1] William L Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.

[2] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, 2018.

[3] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.  In Proceedings of the 25th ACMSIGKDD International Conference on Knowledge Discovery & Data Mining, pages 257–266, 2019.

[4] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In ICLR, 2019.
limitations_and_societal_impact: The authors do not discuss any potential negative societal impacts of their work. Some possible perspectives to think about potential societal impacts include energy consumption, reusability of trained models, easy deployment on mobile devices and so on.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper aims to tackle two challenges in GNN: oversmoothing and neighbor explosion. To this end, the authors introduce a model, SHADOW, to decouple GNN's depth (number of layers) and scope (receptive field). The proposed model enables GNNs to treat their depth and scope independently, leading to provable improved capacity for GCN, GraphSAGE, and GIN. Extensive experiments show SHADOW's clear advantage over state-of-the-art methods.
main_review: Strength:  
* Connections to existing works are well established. Section 3 describes the connection between SHADOW and GCN/GraphSAGE/GIN, and how SHADOW can improve these GNNs. Theoretically, SHADOW can: (1) help GCN to alleviate oversmoothing, (2) extend GraphSAGE to approximate functions while GraphSAGE solely can not, and (3) enable GIN to go beyond 1-WL.
* After decoupling, the depth and scope of GNN can be tuned independently. Notably, the authors explain why we need a larger depth than a larger scope. As an example, SHADOW-SAGE benefits from using a deep model, which may have larger depth than scope.
* The design of subgraph extraction functions is well studied. 
* The design of experiments is reasonable, involving various datasets. The choices of baselines are fair. 
Sufficient ablation studies validate the model choices (e.g., six GNNs are examined as model's backbone).
* The paper is well written and easy to follow. Code is provided for reproducible purposes.

I did not see outstanding weaknesses in this paper. Two recommendations:
* It is better to prioritize SHADOW-GIN results to the main text instead of appendix. Because one significant contribution is that SHADOW improves GIN to exceed the power of 1-WL.
Besides, empirical evaluation on SHADOW-GIN's ability to detect graph isomorphism can be considered. 

* For some graphs, distant neighbor matters, which could be a limitation for the proposed model. Though this paper claims many real-world graphs exhibit minor impacts on distant nodes, but mentioning such a limitation in the main paper is recommended.
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper introduces a framework to design GNNs with decoupled depth and scope. The main motivation of the paper is to overcome the caveats arising when training GNNs on very large graphs: (i) over-smoothing and (ii) expensive computation; that rise due to the need for a deep GNN to extract meaningful information. The basic idea of the paper is to apply a GNN only on predefined subgraph neighborhoods specified by an $\texttt{EXTRACT}$ operator for each node. The choice of the subgraph neighborhoods defines the GNN scope independently of the depth. The authors explain why this model prevents over-smoothing of the entire graph and shows greater expressivity over commonly used 1-WL GNNs.
main_review: 1. **Originality**

   The authors do not cite the work [1], which suggests a basically very similar idea. [1] could be thought of as a version of this work, where the $\texttt{EXTRACT}$ operator extracts K-hop ego networks and apply GNNs of depth $K$ and not $K’>K$ as suggested in this work. The theoretical result of superior expressivity over 1-WL is also already shown in [1].

   I therefore feel that the novelty of the ideas in this paper is incremental. 

2. **Experimental Evaluation**

   It appears that the authors have done an extensive experimental evaluation of their work. 

   However, although achieving state-of-the-art performance on most of the datasets, the performance gain is quite small (except for link prediction), and it seems that there are many “tricks” under the hood that were needed to get these results. Furthermore, I would have wanted to see experimental evidence for the need of $L'>L$ layers for a depth-$L$ neighborhood choice. I suspect the empirical benefits do not exist as [1] is able to reach good performance without it. 

3. **Theory**

   The authors discuss over-smoothing but then suggest applying a deep GNN on subgraphs which basically over-smooth subgraphs. I wonder whether the authors tried to apply fewer layers? 

   

   Since I’m not convinced by the experimental evaluation, and due to the similarity to [1], I, unfortunately, think that the contribution of this work is limited.

---

[1] You, J., Gomes-Selman, J.M., Ying, R., & Leskovec, J. (2021). Identity-aware Graph Neural Networks. *AAAI*.


limitations_and_societal_impact: The authors do not discuss societal impacts.
review_title: null

Meta-review: This paper presents an interesting idea of limiting GNNs to local neighborhoods around each node, which can be used to decouple the depth and scope dimensions of the model.  This change led to great empirical results and computational savings.

However, on the theoretical side the authors made some very strong claims without proper support.  To name a few:
* “A shallow neighborhood is necessary and sufficient for the GNN to learn well.”  This is clearly over-claiming.  Lots of problems that require global reasoning across a whole graph cannot be solved when restricting to small neighborhoods.
* “proposed a first-of-its-kind “decoupling” design principle for the general GNN architecture;” (in discussions)  This is over-claiming.  It is not unusual to see GNNs using more layers than the graph diameter.  For example [this paper](https://arxiv.org/abs/1802.03685) even used GNNs up to 1000-layers to solve certain problems.

Also after a closer inspection of the proofs of the various claims in the paper, the AC found that some proofs are questionable, or at least unclear.

For example, in the proof for shaDow-SAGE expressivity: in order to simulate a L-layer GraphSAGE, the EXTRACT function needs to return an L-hop neighborhood.  The proof notably does not cover cases where the neighborhood size is smaller than L which is the case targeted by the paper, and it is obvious that some functions that can be represented by L-layer GraphSAGE won’t be able to be represented by the proposed Shadow-SAGE with a neighborhood size < L.

Similarly, it is clear that there are some graphs distinguishable by shaDow-SAGE with a small neighborhood not distinguishable by 1-WL.  But on the other hand the provided proof does not cover cases where some graphs may be distinguished by 1-WL but potentially can not be distinguished by shaDow-SAGE with a small neighborhood size.

For these proofs it would be good to clarify when we are talking about shaDow-SAGE with a small neighborhood size (the most important and interesting case for this paper), and when we are talking about shaDow-SAGE with a full graph as the neighborhood size (not interesting and not even relevant for the main discussion of this paper).

I hope the authors can improve the writing of this paper based on the feedback and suggestions, and send the paper to the next venue.

AC
Decision: Accept (Poster)