Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper deals with the very challenging and important problem of designing Graph Neural Networks (GNNs) that are more expressive. The authors propose a new GNN framework, that injects structural information into a message-passing aggregation scheme. The proposed architecture (GraphSNN) is shown to be more expressive than the 1-WL in distinguishing graph structure. Finally, the framework is validated in state-of-the-art node classification and graph classification benchmarks. 
main_review: The contribution of the work is definitely relevant and significant. The framework is solid, well-justified, and supported by proofs. The experimental results are quite convincing as they confirm the good performance of the method in classical datasets. 

I would however encourage the authors to work a bit more on the presentation of the paper. While the paper is generally well-written, there are parts that are difficult to follow for someone who is familiar with GNNs, but not working exactly on aspects of expressivity. For example, the notions of subgraph-isomorphic, overall-isomorphic, and subtree-isomorphic are very technical, and hard to follow. I would appreciate it if the authors could make them more clear, by for example, explaining better Fig. 2. 

Similarly, the proposed choice of \omega, in Eq. 4, should be better explained/motivated.  

Some additional minor comments:
   - '0.05 level of significance': how do you define it? Please elaborate. 
   - Any intuition on what the performance on the MUTAG dataset is not that great?
   - Please double check the References to make them complete and consistent (e.g., Waiss Azizian et al..., Cosro....'33'?,2020)


summary_of_the_review: This is a good paper, with some aspects of the presentation that should be improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes an efficient method for message passing that can incorporate structural information (that of neighborhood subgraphs) that is provably stronger than 1-WL. As compared to three strands of provably powerful (more than 1 WL) GNNs, the method has limited additional computational overhead, and can also show encouraging results on the oft-quoted "over smoothing problem". The benefit of better expressivity coupled with the simplicity of the method is borne out in extensive experimental results and a satisfactory ablation. 
main_review: This paper proposes an efficient method for message passing that can incorporate structural information (that of neighborhood subgraphs) that is provably more expressive than 1-WL. As compared to three strands of provably powerful (more than 1 WL) GNNs, the method has limited additional computational overhead, and can also show encouraging results on the oft-quoted "over smoothing" problem. This is borne out in extensive experimental results and a satisfactory ablation. 

In the recent literature on GNNs, there have emerged three directions of research that aim to construct procedures more expressive than 1 WL:
1. Higher-order WL-based methods, which often can get prohibitively expensive.
2. Using features generated from substructures (most of the papers taking this approach claim this information is available through domain knowledge, but often just use triangles and the likes). 
3. Augmenting node features with identifying information to improve expressive power. 

The central idea of the paper is grounded in the common observation that treating the neighborhood as a multiset of features ignores rich topological information, limiting the expressivity of message passing procedures that use such a representation. If the neighborhood is represented as a neighborhood subgraph, then 1-WL is only as powerful as distinguishing neighborhood subgraphs in terms of subtree structures.  The question then becomes if structural information can be incorporated in a way that can go beyond neighborhood subtree isomorphism. Towards this end, the authors show that there exists a class of isomorphic graphs that lie in between neighborhood subgraph isomorphism and neighborhood subtree isomorphism, which they call overlap subgraph isomorphism. It is shown that by incorporating structural information that can solve overlap subgraph isomorphism, one gets a message-passing network that is more expressive than WL. 

To be more specific, section 2 provides the hierarchy of local isomorphism mentioned above. Theorem 1 states that subgraph isomorphism implies overlap subgraph isomorphism but not vice-versa, and that overlap subgraph isomorphism implies subtree-isomorphism but not vice-versa. 1-WL can only distinguish those graphs that can solve for sub-tree isomorphism at each layer. In order to go beyond 1-WL, the authors focus on overlap-subgraph isomorphism and define a set of structural coefficients for each vertex based on overlap subgraphs. These coefficients depend on reasonable notions of closeness, density, and invariance. The exact form of such coefficients is shown in section 4, and it is also shown that incorporating such information can give a method strictly more powerful than 1 WL. Since it just admits the same message passing paradigm, the computational overhead is limited. 

Extensive experiments on node classification (Cora, CIteseer, Pubmed, NELL, ogbn-arxiv), graph classification for the commonly used small graph datasets, and large graphs show across-the-board improvement compared to the competition (including the higher-order methods). The ablation shows the importance of the structural coefficients. Further, another set of experiments show that the proposed method is able to avoid the so-called oversmoothing problem (however, the results are presented without comment -- it would be beneficial to share some intuition on why this is the case). 

In summary, I think the paper makes a solid contribution. It proposes a well-motivated method and validates it by extensive experimentation that leaves little doubt on its efficacy. 

Minor comments: 
- The paper will benefit from sharpening the writing in the abstract and intro -- it feels a little bit wayward and has some convoluted sentences. 
- The paper title, and most of the paper itself, uses the spelling "Lehman." The actual spelling is Leman. Somewhere after the intro, when the original WL paper is cited (and in some following sentences), the correct spelling is used. I would suggest either using the correct spelling throughout, or sticking to Lehman throughout (since it is widely used, and Leman himself did not mind it https://www.iti.zcu.cz/wl2018/pdf/leman.pdf)
- I don't believe that the citation of "Provably Powerful Graph Networks' of Maron et al. is accurate. It is cited as a powerful (3 WL) method that is expensive, however, I think it is an efficient method. The authors might want to verify this claim. 
- Line 4 from the bottom of page 1: typo "This solution enables GNNs to provably more expressive": -> "This solution enables GNNs to provably be more expressive"
- Line 2 from the bottom of page 1: "which require high computational overheads and are impractical" -> "which require high computational overhead and are impractical"
- Line 1 page 2: "(2), our method does not require any domain" I am not sure it is accurate to say that these methods require domain knowledge. They can certainly benefit from it, and this claim is made in those papers, but they just stick to simple sub-structures such as triangles that are easy to treat. This repeats on page 3. 
- Line 3 of the second paragraph, page 2: "capacity of a model" --> "capacity of the model"

Disclaimer: I have not verified the proofs for correctness. However, based on the statements of the theorems and the general idea, I can buy them to be true and base my review on that assumption (since I expect these statements to be true). 
summary_of_the_review: Well motivated method that is provably more powerful than 1-WL, which incorporates structural information in a principled manner using the notion of overlapping-subgraph ismorphism. Extensive experimentation shows strong performance compared to the competition (including the higher-order WL procedures).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: To overcome expressive weakness of message passing neural networks and computational efficiency of expressive GNNs, this paper proposes a new perspective by introducing overlap subgraphs and overlap isomorphism which is between subgraph isomorphism and subtree isomorphism. Based on that, it carefully design GraphSNN with local structural coefficients to control message passing to obtain more expressive power than 1-WL GNNs. Experiments are conducted on node-level and graph-level classification tasks with an abalation study on a key hyperparameter.
main_review: * Pros:

1. Overlap isomorphism is a nice point to find a balance between expressive power and computational efficiency. Based on that, it is persuasive to encorporate the three properties into structural coefficients.
2. The setting of $\lambda$ is very interesting to me. It brings the coefficients some flexibility so that different $\lambda$'s may capture inherent key information in different learning tasks, as shown in experiments.
3. GraphSNN shows impressive experiment results. On node classification, it improves the counterparts of traditional GNNs by considerable boost, but is also very easy to use. On graph classification, it outperforms baselines by an intriguingly large margin. The performance drops slowly when it stacks more layers.

* Concerns:

1. In the beginning of page 2, the sentence ``compared with the methods of augmenting node identifiers ...'' needs more explanation. If I understand correctly, the latter claim is from the ablation study of $\lambda$ in Section 5.3. But I do not see its relationship with node id/random feature models.
2. According to the definition of $\tilde{A}_{vu}$ with normalization above (5), can the first summation over $u\in \mathcal{N}(v)$ be simplified as 1?
3. Since structural coefficients emphasize strongly connected neighborhood, I am wondering whether it would hurt the performance when there is a task requiring long-range information [1] and the path is, to some extent, adversarially going through a path with weaker connectivity.
4. With respect to oversmoothing on node classification, I am wondering whether the graph operator (can be derived from (5)) with different $\lambda, \gamma$ has dominating subspace [3] that aligns well with the labels. A possible experiment is to send features through leading eigenvectors and then do pure MLP, following [2].
5. Expressive GNNs typically show better performance on graph regression tasks than graph classification. So it would be better to show comparision with expressive baselines on regression datasets such as QM9 and ZINC, instead of Table 4, if time permits.

Reference:

[1] On the bottleneck of graph neural networks and its practical implications. U Alon, E Yahav.

[2] Revisiting Graph Neural Networks: All We Have is Low-Pass Filters. NT Hoang, T Maehara.

[3] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. Kenta Oono, Taiji Suzuki.
summary_of_the_review: I would like to recommend to accept this paper, for its expressive, efficient and easy-to-use GNN component with intriguing performance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a general framework for designing message-passing neural networks (MPNNs) stronger than the 1-WL distinguishing power via structural information injection to the aggregation scheme in the message passing framework. Unlike common MPNNs which perform neighborhood aggregation based on a pre-defined fixed function (which does not depend on the neighborhood subgraph structure) or based on a learned function of the neighborhood node features, the paper suggests a weighting function in the aggregation step of MPNNs which depends on the structure of the neighborhood subgraph. The authors show that under reasonable conditions the resulting architecture has a superior expressive power than the 1-WL test. This also implies superiority in expressive power over common MPNNs while maintaining the same memory and time complexity. The paper introduces a hierarchy of 3 levels of neighborhood isomorphisms: subtree, overlap, and subgraph; which facilitate the proofs and theoretical guarantees. Furthermore, as a by-product, the authors show improved robustness to the notorious over smoothing problem in MPNNs.
main_review: 1. **Originality**  

The paper belongs to a body of recent works which aim to break the expressive power limit of MPNNs in a sub-quadratic memory complexity in the number of nodes. As far as I’m aware, the aggregation scheme suggested in the paper is novel, providing a constructive way to design more powerful architectures than the 1-WL test. 

3. **Experimental evaluation** 

   ***Strengths*** - the paper demonstrates a boost in performance on node and graph classification. 

   ***Weaknesses*** -

   1. Expressive power experiments  - also an experimental evaluation showing what types of structures the proposed architecture can distinguish would be interesting to see (e.g., cycles, d-regular graphs). 
   2. Over-smoothing - the empirical results are not explained. Do the authors have a conjecture as to why their proposed method circumvents over smoothing?

   ***Suggestions***

   - Further discussion on generalization to unseen graphs (With larger / smaller average neighborhoods)? Since the aggregation coefficients suggested are normalized (edges/vertices) it might be that the suggested model is more robust to size differences in graphs. It would be interesting to see how it performs. For example, a simple experiment like the ones performed in [1].

   
- **Clarity** - paper is well written; claims are well supported by theoretical proofs and guarantees.


[1] Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., & Maron, H. (2020). On Size Generalization in Graph Neural Networks. ArXiv, abs/2010.08853.




summary_of_the_review: A well written paper with strong theoretical exposition and results. 


---
**Post Rebuttal**: I am satisfied with the authors response and keep my original score.
review_title: null

Meta-review: This paper proposes an efficient method for message passing that can incorporate structural information that is provably stronger than 1-WL. As compared to three strands of provably powerful (more than 1 WL) GNNs, the method has limited additional computational overhead, and can also show encouraging results on the over smoothing problem. Overall speaking, all the reviewers like this paper quite a lot, although the also raised some minor concerns. The paper also attracted some unofficial reviewers who provided quite a few related works. The authors did a good job in interacting with the reviewers and addressing their minor concerns. So, we believe the paper is worth accepting, and could be a significant work in the field of graph neural networks.
Decision: Accept (Oral)