Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper deals with the design of normalization layers for GNNs that boost their expressivity and prevent over-smoothing. To that, the authors propose a normalization layer that takes structural information, namely graph structure induced by the direct neighbors of a given vertex, into account. The expressivity and its capabilities with regard to the prevention of over-smoothing are investigated theoretically. Further, the new layer is evaluated empirically, on a large set of problems and datasets, showing promising performance. 



strength_and_weaknesses: **Strengths**
- Well done experimental study 
- Simple approach that seems to give some boosts to standard datasets and standard GNN architectures


**Weaknesses**
- The design of the normalization layer is not well motivated, the design seems adhoc
- Theorem statements/proofs are of a very handwavey nature, not clear  and not rigorous enough

**Suggestions, issues, questions, and comments**
- The formal statement of Theorem 1 is unclear. What is meant by the sentence after "while any"?
- Equation 2: This is a very specific GNN layer. Note that the layer does not use a non-linearity.
- Over-smoothing was only shown for very specific GNNs, it is not well understood if this holds for all possible GNN architectures. For example, 1-WL-equivalent GNNs, at least in theory, will not suffer from over-smoothing as the vertex partition gets finer as one increases the number of layers/iterations
- Section 3: It should be made more clear why it is essential to include the structural information, encoding the neighborhood subgraph into the normalization. Why not just add it as an extra feature to the node features?
- Section 3.1. before Theorem 2: The motivation/explanation of MotifNorm should be improved. This seems to be the main contribution but it is hard to follow although it seems to be quite simple 
- Below Equation (5): It is not clear what the term "segment averaging" refers to
- Equation (4): Do all normalization layers fit in the provided form? Can you provide a reference for this?

- Theorem 2: The statement is not formal enough. For example, it is unclear what "stabling and accelerating GNNs’ training" means.
- Theorem 3: The proof sketch is not helpful, e.g., make at least clear why GNNs+MotifNorm can distinguish the two graphs. Moreover, the statement "helps alleviate the over-smoothing issue when GNNs’ layers become deeper" is not formal enough for a theorem statement.
- Section 4.1: What is the reason for performing a "hierarchical dataset splitting strategy based on the structural statistics of graphs". Is this necessary to get good results?
- Table 3: The reported numbers for ZINC seem very high, e.g., compare to https://arxiv.org/abs/2003.00982. What is the reason for this?

**Minor points**
- Page 2: Your edges are directed as they are from $V_G \times V_G$
- Section 2.1: "Graph isomorphism problem" might be the better term ("isomorphism issue")
- Equation 1: Define the initial labeling, it might also be helpful to formally define the considered GNNs in the main paper
- Definition 2: "number of samples in a countable set" -> "cardinality"
clarity,_quality,_novelty_and_reproducibility: Many parts of the paper are unclear, e.g., many of the formal statements are of a too handwavey nature. The proposed normalization layer seems to be derived in an ad-hoc manner.
summary_of_the_review: The paper proposes a simple normalization layer that boosts standard GNNs' empirical performance on well-known benchmark datasets. However, the design of the layer seems ad-hoc, and the theoretical explanation lacks rigor. In its current form, the paper is not ready for a top-tier conference.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper, the authors propose a new normalization method called MotifNorm for GNNs, which explicitly considers the intra-connection information and graph instance-specific statistics. The authors provide theoretical analyses to show that GNNs with MotifNorm are more expressive than the 1-WL test in distinguishing $k$-regular graphs. Experiments on several datasets are conducted to demonstrate the effectiveness of the proposed MotifNorm.
strength_and_weaknesses: ### Strength

- Normalization methods are known to help the training of deep neural networks and it is an important direction to design normalization methods for GNNs.

- It is reasonable to conduct comprehensive experiments covering node/link/graph-level tasks to examine the proposed MotifNorm for different GNN variants.

### Weaknesses
Here are several critical points that need to be essentially addressed.

**[The motivation and novelty of the proposed MotifNorm]**

- The motivation is not strong. The authors state that the designed weight factor needs at least to distinguish two subgraphs shown in Figure 2 (in page 3). However, it is not general to just use one pair of graphs as measurement. Such motivation is not convincing to support the following network design. 

- The novelty of the proposed MotifNorm is limited. The core step Representation Calibration (RC) of the proposed MotifNorm is highly related to the Representative Batch Normalization (RBN) [1], and the proof of Theorem 2 mainly follows [1]. The authors should carefully discuss the relation between RBN and MotifNorm.

**[The correctness of theoretical analyses]**

- Definitions and theorems presented in this paper are not rigorously written. In Definition 1, there do not exist definitions of the symbol $u$ and $u'$. In Theorem 1, readers would be confused about which graphs the subgraphs $S_{v_i}$ and $S_{v_j}$ belong to (Please refer to [2] for formal statements). Moreover, both Theorem 2 and Theorem 3 are not quantitative analyses, which deliver little insightful information on the proposed MotifNorm. 

- There exist mistakes in proofs for these theorems. For example, in Appendix A.2, the authors remove the $\mathbf{M}$$_{RC}$ term to analyze the effect of representation calibration, however, it is non-trivial to conclude the final statements with the RC term. In Appendix A.3, the analysis on the over-smoothing issues is based on the equation 14, but this form largely differs from detailed implementations of the proposed MotifNorm. Thus, the correctness of theoretical analyses in this paper is doubtful.

**[The confidence of experimental results]**: 

- The results of baselines on several datasets are relatively lower than results in previous works. For example, for ZINC dataset, GCN with BatchNorm achieve 0.416 and 0.278 MAE respectively [3]. For ogbg-molhiv dataset, GCN with GraphNorm achieves 78.30 ROC-AUC [4]. For ogbn-proteins dataset, GCN with BatchNorm achieves 0.7251 ROC-AUC [3]. For ogbn-collab dataset, GraphSAGE with BatchNorm achieves 54.63% Hits@50 [3]. These results from previous works outperform the best results reported in this paper. Thus, the experimental results are doubtful and need to be clarified. Furthermore, many baselines are out-of-date and more recent methods such as  graph transformers should be considered as baselines [If the proposed MotifNorm cannot bring SoTA results, why should people use it?].

- Runtime/Memory Cost evaluation should be provided for completeness. In equation 3, the structural weight need to count the number of edges and nodes in the node-induced subgraph, which increase additional computational costs for standard normalization methods. It is better to provide runtime and memory cost evaluation for comparison. Besides, the authors report the number of epochs that each model take to achieve the corresponding performance in Table 2. We can see that GNNs with MotifNorm converges slower than GNNs with BatchNorm in some cases. Thus, it is also reasonable to provide the total time that GNNs with different normalization methods take to achieve the reported scores.

[1] Gao, Shang-Hua, et al. "Representative batch normalization with feature calibration." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.

[2] Wijesinghe, Asiri, and Qing Wang. "A New Perspective on" How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"." International Conference on Learning Representations. 2022.

[3] Dwivedi, Vijay Prakash, et al. "Benchmarking graph neural networks." arXiv preprint arXiv:2003.00982 (2020).

[4] Cai, Tianle, et al. "Graphnorm: A principled approach to accelerating graph neural network training." International Conference on Machine Learning. PMLR, 2021.

clarity,_quality,_novelty_and_reproducibility: As I described above, I found the paper has limited novelty and weak motivation. Besides, the correctness of theoretical analyses and confidence of empirical results are also doubtful.
summary_of_the_review: The current quality of the work (novelty, motivation, theoretical analysis, empirical results) is not ready for publishment in the venue, and I recommend rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper applied a motifnorm to introduce the graph structure into the node presentation and increased the expressive power over 1-WL test. It is well written and with extensive experiments.
strength_and_weaknesses: Strength: 
The paper is well written. And the theoretical analysis is also quite clear, which I truly appreciated. 
The proposed methods do boosted the performance and the ablation study also revealed the results.

Weakness:
Based on the formulation of "motifnorm", I do not think it is a normalization method. Essentially, it added the information on top of the feature information. And applied the normalization methods. And the definition of "motif" is not quite intuitive. Per my under standing, motif should be some rather stable structure in the graph. But from the method, the motif is equivalent to the subgraph including the node of interest, which makes the method quite similar to the methods like labeling trick (Zhang et al).  
I checked the proof of theorem 3. It seems, it does not show how the method will solve the over smooth issue. Actually even there is empirical result, the theorem is not intuitive to me. The norm is also a way to smoothing from the information from the "motif". How would it solve the over smoothing?


clarity,_quality,_novelty_and_reproducibility: The paper is clear written. I do not think there is an issue with reproducibility. 
summary_of_the_review: This paper is well written and quite complete. But I would have question about the definition of the "norm" and "motif". And the method in some extend shared certain similarity of current methods.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work looks to enhance the discriminate capabilities of GNNs by adding a normalization module after the convolution layer. Traditional GNNs suffer from limited expressive power, i.e., upper bounded by 1-WL test, and the over-smoothing problem when stacking multiple GNN layers. To tackle the above two challenges, a motif-induced normalization, MotifNorm, is proposed with theoretical analysis showing that MotifNorm make arbitrary GNNs more expressive than the 1-WL test in distinguishing k-regular graphs. It is also shown that MotifNorm is able to reduce the over-smoothing problem. The experiment results on ten benchmark datasets are promising 
strength_and_weaknesses: Strengths

1. MotifNorm, as a plug-in, makes GNNs more expressive (beyond 1-WL test) and less prone to the over-smoothing problem. 
2. The calibration and enhancement steps in MotifNorm is novel and efficient. 
3. Good experimental results. 

Weeknesses

1. This work only provides proof of the expressiveness of GNN+ MotifNorm beyond 1-WL in the case of k-regular graphs. However, there are few k-regular graphs in real applications. The expressiveness analysis will be more convincing if the author could give proof in more general cases. 
2. The motif-induced weight is predefined and does not consider any node or edge attributes, or the task for prediction. This limits MotifNorm ability to handle complex scenarios like heterogenous graphs or graphs with edge attributes. 
3. Table 2 does not provide the performance of GSM+MotifNorm and GraphSNN+MotifNorm. Since GSM and GraphSNN are convolutional approaches that achieves higher expressivity than 1-WL test, it is desired to see whether MotifNorm will further enhance the expressivity of GSM/ GraphSNN.
4. Figure 5(a): For GCN with shallow layers, GCN+MotifNorm performs worse than GroupNorm and NodeNorm. It seems MotifNorm really helps in alleviating over-smoothing but shows no advantages in shallow models. Could the authors explain a bit?
5. Missing discussions with popular normalization methods. Also, there are some recent related works. For example, [1] proposes a normalization technique with better flexibility. [2] also proposes a normalization approach to alleviate over-smoothing problem. It is better to compare with works with similar motivations and demonstrate the advantage of the proposed approach.

References
[1] Chen, Y., Tang, X., Qi, X., Li, C. G., & Xiao, R. (2022). Learning graph normalization for graph neural networks. Neurocomputing, 493, 613-625.
[2] Liang, Langzhang, et al. "ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization." arXiv preprint arXiv:2206.08181 (2022).

clarity,_quality,_novelty_and_reproducibility: 1. This manuscript is clearly written and easy to follow.
2. The calibration and enhancement steps in MotifNorm is novel and efficient.
3. The work provides sufficient instructions on reproduction.
4. Some typos, for example, the 3rd word in the first sentence from the batch graphs section of page 4, should be ‘batch’. 
5. Minor comment: The experimental settings may not be optimal for some baseline models. For example, in Table 3, the original paper result for GCN+GraphNorm on ogbg-molhiv is 78.30 (num_layer=5), but the reproduced result is 75.59 (num_layer=4). My concern for performance drop is that reproduction may not achieve optimal.

summary_of_the_review: The idea is novel. But the above problems should be addressed before publication.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Graph neural networks (GNNs) are known to suffer from over-smoothing issue, this paper proposes to solve this issue by adding a plug-and-play layer, i.e., motif-induced normalization layer, into GNNs. Theoretical analysis has been done, which shows over-smoothing problem can be alleviated, and the proposed operation can stabilize model training. Extensive experiments have been done to demonstrate the effectiveness of the proposed method.

Strengths 
- Extensive experiments have been done.
- Simple approach which seems can be combined with many existing GNNs.

Weaknesses
- Motivation of the design is not convincing. More discussion with existing works should be included.
- Theoretical statements are informal and not rigorous. The proofs need to be double-checked as well. 
justification_for_why_not_higher_score: - There are many works attempting to 1) address oversmoothing and 2) include motif into GNNs. Authors need to find a better position of their work and motivate their design more clearly.
- Authors also need to show the theoretical results in a more mathematical and formal way.
Decision: Reject