Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes Nested GNN, which encodes each node based on the subgraph rather than the subtree (as what GNN does) around it. The main difference between NGNN and GNN is that subgraph captures more information than the subtree, such as the interactions between a node's neighbors. The whole-graph representation can be pooled from each node representation, and can be applied in tasks such as graph classification. From theoretical perspective, this paper studies the limitations of expressive power of GNN and show that NGNN is more powerful. The proposed method shows good performance on multiple datasets. 
main_review: This paper studies the limitation of expressive power of GNN and proposes NGNN, which encodes each nodes representation based on the subgraph rather than the subtree around it. The point and the case study of when GNN would fail is valid, and the proposed method seems to perform well and is shown can discriminate r-regular graphs. I am a bit concerned about the novelty of the method since the first step (base GNN) seems to be just a way to learn each node representation (within the subgraph, while GNN learn it within the whole graph), and the second step is a standard graph pooling. I also have the following questions that hope the author could address:

1. Do you have any guidance on choosing the subgraph height at the base GNN step? I noticed the current experiment uniformly select height = 3, I think this is a parameter that should be related with the graph size or could be tuned in a principled way. 

2. The main concern is about the computational cost (also mentioned in the limitation section). I noticed that the average size of graphs in the datasets are relatively small. Have you tried or implemented the base GNN step in parallel? Also, related the first question, if your graph size is small, then extracting a height-3 subgraph rooted in a node would not have too much difference with the whole graph. Would be interesting to see the performance on graph with larger size, 

3. The base GNN layers allow a node (v) to have different representations within difference rooted subgraphs (call the root u), which I view it as a "contextual" representation of node v. Currently the method uses the contextual representation of v to pool the representation of the rooted node u. Besides that, could you make use of the contextual representation of v in different rooted subgraph in other ways, for example to encode v itself when it is the root?

limitations_and_societal_impact: My concern about the this method is the computational cost. It applies base GNN for subgraph around each node, meanwhile the classical GNN learns node representation in a one-pass fashion. The authors mentions such limitation as in their Section 5.3, that NGNN does not scale to graph datasets with average node number > 400. I am wondering could you perform the base GNN step for all nodes in parallel, since extracting subgraph and train GNN on it should be independent for each node,
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a new architecture to strengthen message passing GNNs. Since the weaknesses of GNNs usually come from  the unidentifability of nodes, the authors suggest to first preprocess given graphs and add each node a new initial attribute, and then apply the outer GNN. The new node attributes come from another message passing GNN (called based GNN) applied to a subgraph of a certain depth (or height according to the paper's terminology) around each node. Then they prove that the new architecture can distinguish regular graphs with probability $1-o(1)$ (over the choice of a random regular graph), and so the new model is more expressive than MPNNs, since MPNNs can't. They finally evaluate their model in various settings.  

For me the contributions of the paper are: (1) proposing nested GNNs (NGNNs); (2) showing that NGNNs can distinguish almost all regular graphs; (3) and evaluating the new model through various experiments. 
main_review: 
Strengths: 

(1) The paper is really easy to understand. I could understand the manuscript at the first read. 

(2) They supported their theory with nice experiments. 

(3) The new theoretical result is of potential interest to the graph learning community since it provides significant contribution to the problem of learning regular graphs.

Weaknesses/comments/questions:

(0) A number of important previous works are missing. For example, in the context of counting substructures, people also considered strengthening GNNs with subgraph pooling [1]. In [1] the authors consider a similar setting where MPNNs are strengthened with pooling on a neighborhood around each node (similar idea), and instead of having base GNN, they consider Relational Pooling (RP). Please provide explanations why/how your paper is different from theirs, and compare the results (also see [4,5]). 
Also, if  we have random node IDs, then GNNs can approximate any functions (e.g., see [2]). So you need to also mention those papers in your paper and explain what is your contribution. The bound you get for the complexity is also a special case of what is appeared in a preprint [3]. The referred  papers below are only examples and you can find more related papers by tracking these examples (and references therein). However, I haven't seen your theorem on distinguishing regular graphs in any previous papers, so the paper contributes on the problem of learning with regular graphs. I suggest to rewrite some parts of the paper and mention that you essentially have an original theoretical result on learning with regular graphs, and also explain/discuss/mention all the related works.  I believe the paper has good contributions, but it is still vague how it is related to the previous works, it has missing references (just I provided a few examples below), and extensive revision is required.

 [1] Chen, Zhengdao, et al. "Can graph neural networks count substructures?." arXiv preprint arXiv:2002.04025 (2020).
 
 [2] Abboud, Ralph, et al. "The surprising power of graph neural networks with random node initialization." arXiv preprint arXiv:2010.01179 (2020).

[3] Tahmasebi, Behrooz, and Stefanie Jegelka. "Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results." arXiv preprint arXiv:2012.03174 (2020).

[4] Lou, Zhaoyu, et al. "Neural Subgraph Matching." arXiv preprint arXiv:2007.03092 (2020).

[5] Ying, Rex, et al. "Hierarchical graph representation learning with differentiable pooling." arXiv preprint arXiv:1806.08804 (2018).

(1) The lack of detailed motivation behind the theorem: since your theorem just concerns regular graphs, there should be a reasonable motivation for why we need to  do classification/regression on regular graphs (please provide examples that regular graphs arise, like in molecules, etc.).

(2) I think if the given graphs are strongly regular, then the model fails to distinguish them. Is it true? Please provide more discussion about this fact right after the main theorem because it could help the reader and it's also related to the future works.


(3) The proposed method is a feature augmentation trick, however, I couldn't find any literature review on that topic in the related works section. Please add related papers and also discuss how your model is different from theirs. 



(4) While the main body of the paper is quite understandable, the appendix is not. Specially, the proof of your main theorem is not clear at all. There is a reference  to a prior work which is not clear to me unless I read the reference. Can you add a few sentences about steps 1-3 in appendix (line 637) to make the proof more readable?  There is no page restriction for the appendix.



(5) In Equation 3, are the functions $U_t,M_t$ shared among nodes? Or each node has its specific function? I guess they share, but it is not so clear in the paper. 


(6) Figure 2 is great for understanding your model. Can put it earlier in the paper and give more references to it within the text?

(5) Line (229): I guess $O(cn^3)$ --> $O(cn^2)$.

(6) In the main theorem, can we have $\epsilon \to 0$, so we only need one layer message passing? How does the distinguishing error in Theorem 1 (i.e., the term $1-o(1)$) depend on $\epsilon,n,r,...$? I believe one important question is the term $o(1)$ in your proof. Can you quantify that in your theorem?    Please quantify the dependence of the $o(1)$ bound in your result to $\epsilon,n,r$ to allow comparison and help readers.  Also, please provide a few sentences as proof sketch right after the main result.


(7) I cannot understand why the new algorithm increase the computational load just by a constant? Do you mean $c$ in line 229 is $O(1)$? In your setting with regular graphs, we could even have $c = r^h = O(n^{0.5})$ if we apply those $r,h$ in Theorem 1.  Is it true? Hence, your algorithm does not always increase the computational load by a constant factor. It can grow with $n$. Please clearly mention in in the paper.  

 --------------------------------

After rebuttal:

The authors mostly agreed on the comments, and explained some of them, but to me some of the questions are still unanswered, or it is still not clear what exactly do they want to add to the paper after revision. I decided to keep my rating.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Since GNNs based on rooted subtrees are known with limited expressive power, this paper proposes to represent nodes with their rooted subgraphs. Its expressive power with respect to graph isomorphism testing is proven beyond 2-WL. Such a method is compatible to plug into popular GNNs to enhance their representation power. Enhanced GNNs show strong performances on graph classification and regression tasks.
main_review: This paper proposes an interesting method to define message passing on rooted subgraph, different from rooted subtrees. It is compatible with popular base GNNs. The method proves to go beyond 2-WL w.r.t. graph isomorphism testing. Real-world graph classification and regression tasks are conducted. It also presents necessary ablation study along with a synthetic experiment. This paper is well written. 

Pros:

1. different from rooted subtrees and higher-order structures, this paper designs a more expressive gnn with easy-to-follow rooted subgraphs.
2. the proposed method is compatible to plug into popular but weaker GNNs and results in a guaranteed boost of expressive power. Extra computation time it incurs is reasonable.
3. distance encoding is natural in the NGNN framework as feature augmentation bringing excellent results.
4. weaker GNNs enjoy impressive performance boosts in real-world experiments.
5. the synthetic experiment in Appendix C confirms the theoretical result.

Concerns:

1. it would be better to try NGNNs on the ZINC dataset, where many popular papers proposing novel models present their results these days. It will bring more impact for this paper.
2. where is the sentence ''our initial analysis...'' in line 220 pointing to?
3. ablation study of distance encoding on graph classification tasks is missing. It is not sure whether the gain is from distance encoding or rooted subgraphs.

I suggest an accepting score.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents a framework that applies GNN to subgraphs around each node independently to enhance node representations, followed by a global pooling layer to get graph-level embedding. The framework can be applied to any GNNs. The paper also demonstrates it's relative improvement over several real-world datasets, although the improvement seems marginal. From theoretical side, the paper proved formally that this framework can distinguish k-regular graphs where most traditional message passing based neural network cannot. 
main_review: 1. Originality: the idea of making use of subgraph to encode a better node representation is not new. In fact there some very similar papers that haven't been mentioned, and the architecture is exactly the same to their models except that the model mentioned in this paper can use any GNNs. One paper I remember is G-meta[1]. Please refer to their papers in detail and discuss the difference in terms of model architecture. The ability of using any type of GNNs seems a natural extension of their models. All in all the novelty is not enough considering the idea has been explored before. 

2. Quality: the architecture and the subgraph information is solid to me. Including more information from subgraph can outperform original 1-hop based message passing model. However the information provided in experiment section is not complete. The hyperparameter tuning is not very clear to me, whether the number shown in the paper follows a fair evaluation should be stated clearly and also by providing a link to their code to check. 

3. Clarity: the paper in general is well-written. The only part that is not clear to me is the "outer-GNN" mentioned in the paper. From my understanding the outer part is just a global pooling instead of a GNN model. Please explain this part clearly and if you only use a global pooling layer, please don't use the name "outer-GNN", instead use "global pooling" stage directly.  

4. Significance: The result is kind of questionable from my end. 

First, the TUDataset result is very different from the result in GIN paper, where GIN model has a lot better performance than the one shown in the paper. Maybe the experiment configuration is different. However, the paper mentioned that  "we uniformly use 4 message passing layers with 32 hidden dimensions each for all models" and "For NGNN, we uniformly use height-3 rooted subgraphs with mean pooling". This part sounds to me an unfair evaluation between NGNN and GNN models. I would question whether expand the pool of hyperparameter search will increase performance of GNN and decrease the performance of NGNN, as NGNN suffers more from overfitting than GNN. I suggest the author clearly state the pool of hyperparameters and provide a link to their code to have a look. 

Second, the performance on molhiv and molpcba is also questionable. Comparing GIN and Nested-GIN I do see a 1% performance improvement, however the performance of Nested-GIN is not high enough comparing with other more recent baselines. This question whether Nesting GNN is the correct way to improve expressiveness and real-world performance. The ensemble result is not attractive to me, as this is not a fair evaluation to other methods. In face the author should present other models' ensemble results. On the other perspective, the large variance of the result shows the unstable training of nested GNN. The experiment section needs a huge improvement and fair evaluation. 


[1] Graph Meta Learning via Local Subgraphs.  https://arxiv.org/pdf/2006.07889.pdf 
limitations_and_societal_impact: Not applicable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces Nested Graph Neural Networks (NGNNs), a novel kind of graph neural network that overcomes the limitations of typical message passing approaches by representing each node as a function of its nested subgraph, rather than its nested subtree. 
The result is a model provably more expressive than 1-WL and 2-WL, at the cost of a constant increase in computational complexity (although this has practical limitations, as the authors point out).

NGNN works on two levels: 

1. A "base GNN" is used to compute representations for each node, applying the GNN to the nested subgraph around the node and eventually pooling the subgraph to obtain the representation. 

2. An "outer GNN" processes the resulting graph to obtain the final node representations, and a global pooling is optionally applied to get graph-level embeddings. 

Therefore, NGNN can surpass 1-WL expressivity using only standard message-passing GNNs, making it very convenient and more computationally efficient than previous higher-order GNN variants. 

The authors prove the expressive power of NGNN in distinguishing n-sized r-regular graphs. 

The paper concludes with a thorough experimental analysis of NGNN on several benchmarks of graph classification and regression: QM9, ogb-molhiv, ogb-molpcba, and some TU datasets. 
The method achieves state-of-the-art performance on ogb-molpcba and several QM9 subtasks. 
main_review: **Originality**: the method is novel and smartly combines existing techniques, achieving impressive results. The work is contextualized well w.r.t. previous literature and highlights the similarities and advantages of NGNN.

**Quality**: the paper is technically sound. The claims are clearly stated at the beginning of the paper and methodically verified, with relevant proofs delegated to the Appendix. The goals of the experiments section are also clearly listed (which is something that one rarely sees in papers of this kind) and there is a final discussion that relates the results to the research questions. 
The limitations of NGNN are discussed openly: 

1. it is unclear whether NGNN is more powerful than 3-WL;
2. NGNN can only be used on graphs with up to 400 nodes on average, due to the memory limitations of GPUs.

**Clarity**: the paper is well written and organized. I have found only one minor typo: the comma after "because" on line 43 should be removed. 
A few more details on how to extract subgraphs, in practice, would be needed to reproduce the results only from the paper, although this is only for the reader's convenience. All other experimental details are clearly described. 

**Significance**: typical message-passing GNNs have significant limitations in terms of expressivity, and much of the research in the field is dedicated to designing more expressive GNNs. Most methods, however, resort to very expensive solutions (up to $O(n^3)$ complexity) which make them poorly applicable in real scenarios. NGNN overcomes the limitations of both message-passing GNNs and higher-order approaches. I can see how this paper could have a positive impact on the GNN community. 
Also, the method proposed achieves the state of the art on a significant benchmark (ogb-molpcba) through a novel approach, which is an important result. 
However, the other experimental results could be stronger and I ask the authors to comment on the points that I raise below, regarding the selection of baselines and the choice of datasets. 

**Comments**: I have a few comments to strengthen the paper

- As a subjective observation, the description of the rationale for subgraph pooling in lines 69-76 could be more clear, as Figure 1 doesn't do a good job of showing the differences between how subtrees and subgraphs are constructed. One objection that at first comes to mind is that the base GNN is still working on subtrees, and the figure should show more clearly how this is, in fact, not the case (e.g., by coloring the nodes to make the differences more visually striking). 
Since this is the core of the method, more effort should also be spent on its explanation in the text. 

- How is subgraph extraction implemented in practice? The paper should describe more clearly why it is necessary to "materialize" the subgraphs in GPU memory, since it is the most evident shortcoming of NGNN. This would allow readers to understand the problem better and possibly come up with solutions. 

- For OGB, how were the baselines selected? 
The top-4 best results on ogb-molhiv are above 0.8 ROC-AUC, while all baselines here are below 0.8, making NGNN the best method due to this selection bias. 

- The claimed improvements in performance on the TU datasets are often statistically insignificant (e.g., standard deviations up to 11.6 on MUTAG) and not very informative. 
Since all graphs in OGB's graph-property prediction tasks are within the limit of 400 nodes on average, why didn't the authors consider ogb-ppa and ogb-code2 instead of TU?

- The code for experiments was not included in the supplementary material with the submission. It is important that the code is made available to reviewers prior to the final AC decision regarding this paper. 

---
**After rebuttal**

My initial comments were minor and the authors have addressed most of them. Some issues remain about the computational complexity of the method, as also confirmed by the authors. 

My rating remains unchanged. 
limitations_and_societal_impact: The limitations of the work are adequately addressed.
The paper is unlikely to have a negative societal impact.
review_title: null

Meta-review: This work proposes a way to overcome some of the known expressivity issues of permutation invariant message-passing GNN. It does so by learning node features by applying a GNN on a subgraph around each node.

The reviewers agreed that the paper is well written and that it makes an interesting theoretical contribution. Moreover, the empirical evaluation (taking also into account the results presented during the rebuttal period) demonstrates that the proposed architecture can bring practical benefits in terms of accuracy. The main catch seems to be that the computational/memory complexity of the proposed method might be prohibitive for large graphs.

The reviewers were divided in their evaluations. The main issue expressed was that the proposed idea is not surprising given the literature and that a thorough discussion of relevant works was missing from the submitted paper. Even though these concerns are justified, it seems that the specific idea proposed has not been considered/tested before. Moreover, the authors acknowledged and explained the connections to previous works in the rebuttal period. Thus, I don't see an issue with accepting the work under the condition that the camera-ready version is updated appropriately.
Decision: Accept (Poster)