Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focus on understanding the expressiveness of subgraph graph neural networks. Under its proposed node-based subgraph selection policy, the author demonstrates the representation power as strong as 3-WL test via bridging it with 3-IGNs. In the mean time, the algorithm is realized as Re-IGN and reports superior performance than other existing subgraph GNNs.
strengths_and_weaknesses: **Strengths**
1. The presentation is clear and easy to follow.
2. Subgraph GNN is a uprising research topic in graph neural networks, theoretical understanding and its symmetries to existing invariant or equivariant GNNs help explain the design choices and applications.
3. The extensive experiments in main paper and appendix not only shows its superior performance in family of subgraph GNNs but also on par performance with established traditional graph neural networks.


**Weaknesses**
Not I can think of. I think the experiment table 1 is missing an entry.
questions: 1. Compared with traditional GNNs that achieves better performance in benchmark datasets, what's the potential reason? I understand it is not a disadvantage that SUN can not beat GIN/CIN on existing benchmarks? Some insights that why SUN with 1 MLP operators cannot beat existing methods with geometric group symmetries, might be helpful for the community. 

2. Do you require pre-defined motifs in node-based selection policies?
limitations: N.A.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper extends and analyzes the class of Subgraph GNNs. Importantly, the authors proved that the expressive power of these Subgraph GNNs is bounded by 3-WL. Then, a new family of layers for the class of Subgraph GNNs is proposed, with better generalization abilities. Overall, this is a solid theory paper, and provides a deeper understanding for subgraph GNNs.
strengths_and_weaknesses: Strength: 1. Provide a deeper understanding of subgraph GNN
2. Design a novel Subgraph GNN, which unifies previous architectures and provides better empirical performance.
Weakness: 1. Scalability or computation/storage cost is not discussed. 
2. The empirical improvement is not impressive
questions: How is the complexity of subgraph GNN?  
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work provides a theoretical framework for subgraph GNNs. It first points out that the theoretical analysis of subgraph GNN with node-based subgraph policy can be simplified. Then, with the existing invariant graph networks (IGN) model, the author embeds node-based subgraph GNN into the 3-IGN and thus bounds the expressive power of node-based subgraph GNNs by 3-WL. Besides expressivity analysis, this work also provides a detailed illustration of the design space of subgraph GNN and a new subgraph GNN model, SUN. SUN exhibits good generalization ability in experiments.
strengths_and_weaknesses: Strength:
1. The paper is clear and well-written.
2. The connection between subgraph GNN and 3-WL is novel. 
3. The topic is significant as using subgraph is an important method to boost expressivity.

Weakness:
1. The discussion is heavily based on IGN. However, this paper does not introduce it.
2. The design space of subgraph GNN is based on extended IGN(2) and has little connection to the theoretical analysis based on IGN(3).
3. Time complexity is not discussed.
4. Discussing how subgraph selection rules affect expressivity will also be very interesting.
questions: 1. How large is the expressivity gap between IGN(3) and ReIGN(2)?

2. Time complexity of IGN(3)?
limitations: The societal impact is adequately addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a unified analysis of subgraph GNNs based on node selection (e.g., ego-networks, node deletion, etc), and shows that these GNNs map directly to 3-IGNs (invariant graph networks) by representing their different components (subgraph selection, layers, pooling, MLP) as 3-IGN layers. Based on this correspondence, the paper then shows that any subgraph GNN based on node selection (where every subgraph is computed through a bijection over the selected node and the original input graph) can be implemented through a 3-IGN. This result is shown first by proving that all known graph selection policies can be emulated by a 3-IGN (Lemma 4) and then showing how the following components of subgraph GNNs can also be captured by this same model (Lemma 5). Based on this result, the paper proves that all subgraph GNNs based on node selection have expressive power upper-bounded by 3-WL, the upper bound for 3-IGNs. 

Building on this insight, the paper then considers potentially novel designs for invariant/equivariant operations over nodes and subgraphs, and draws on the potential operations of 3-IGN and 2-IGN. In particular, it looks for equivariant functions with an at-most quadratic memory footprint (like 2-IGN) and then extends 2-IGNs with local node neighborhood aggregation (as standard in MPNNs) so as to naturally emulate subgraph GNNs. This extension, called ReIGN, is sufficient to capture all known subgraph GNNs. Finally, the paper proposes subgraph union networks (SUNs), which build on the ReIGN framework, and evaluate this model empirically on subgraph counting benchmarks, demonstrating strong performance.
strengths_and_weaknesses: Strengths: 
- The unified analysis of subgraph GNNs is very valuable, and the upper-bound is quite useful to understand the limitations of current models. I have briefly checked the 3-IGN construction in the appendix, and all proofs appear sound.
- The proposed ReIGN framework offers interesting avenues to extend subgraph GNNs, and the coverage of existing models is very good.

Weaknesses: 
- The experimental section is rather limited, as the paper makes no ablation analyses of the SUN model, nor does it conduct case studies to further validate its hypotheses. I believe an interesting question is how SUN performance changes relative to the different components in its equations (i.e., how much gain comes from, e.g., using different update functions v_theta1, v_theta2, using all the different components fed into the update equation).
- The intuition provided in the paper is not sufficient to fully understand the result. In particular, I had to consult the appendix on multiple occasions to understand orbits and the constructions for the proof. Therefore, I strongly recommend a slightly more detailed coverage of the 3-IGN construction and of orbits to facilitate the explanation
-  It seems that the font used in the submission differs from what is expected from the NeurIPS template: To demonstrate, the "Do not distribute" footer stretches into a second line, which isn't the case in the normal template. This could well be a bug, and clearly is to the disadvantage of the authors (i.e., the font is less generous in terms of space than it should be). Hence, I strongly suggest you revisit your source file. The added space could help you more clearly explain your proofs as suggested above. 
questions: None at the moment
limitations: Limitations: The model properties are thoroughly discussed in this paper, and the corresponding limitations of ReIGN are clear. However, SUN could have been better  analyzed in terms of the limitations stemming from its model choices (See ''Weaknesses" section for more details.)

Societal Impact: Not applicable
review_title: null

Meta-review: metareview: This paper studies the recent hot topic in GNN, namely subgraph-based GNNs which apply GNN to each node-centered subgraph copy of the original graph instead of directly applying GNN to the full graph. These GNNs were shown to be more expressive than 1-WL but were unknown in terms of their upper bound of expressive power. This paper shows that all these subgraph-based GNNs, including Nested GNN, ID-GNN, reconstruction GNN, GNN-AK etc., can be implemented by 3-IGN which is upper bounded by 3-WL, thus giving an upper bound to subgraph-based GNNs' expressive power. The novel perspective that views subgraphs as an additional tensor dimension which is also equivariant to node permutation is very insightful, and is the key to the 3-IGN implementations. Overall, I believe this paper is of great theoretical contribution to the GNN community and opens up some new design space.
confidence: Certain
Decision: Accept