Motif-induced Graph Normalization
Authors: Kaixuan Chen
Shunyu Liu
Tongtian Zhu
Tongya Zheng
Haofei Zhang
Jie Song
Mingli Song
Venue: Submitted to ICLR 2023 (2023)

Abstract: Graph Neural Networks (GNNs) have emerged as a powerful category of learning architecture for handling graph-structured data in the non-Euclidean domain. Despite their success, existing GNNs typically suffer from the insufficient expressive power bottlenecked by Weisfeiler-Lehman (WL) test, and meanwhile are prone to the over-smoothing situation with increasing layer numbers. In this paper, we strive to strengthen the discriminative capabilities of GNNs by devising a dedicated plug-and-play normalization scheme, termed as Motif-induced Normalization (MotifNorm), that explicitly considers the intra-connection information within each node-induced subgraph. To this end, we embed the motif-induced structural weights at the beginning and the end of the standard BatchNorm, as well as incorporate the graph instance-specific statistics for improved distinguishable capabilities. In the meantime, we provide the theoretical analysis to support that, with the proposed elaborated MotifNorm, an arbitrary GNNs is capable of more expressive abilities than the 1-WL test in distinguishing k-regular graphs. Furthermore, the proposed MotifNorm scheme is also exemplified to be able to alleviate the over-smoothing phenomenon. Experimental results on ten popular benchmarks across all the tasks of the graph-, node-, as well as link-level property predictions, demonstrate the effectiveness of the proposed method. Our code is made available in the supplementary material.

Under review as a conference paper at ICLR 2023
MOTIF-INDUCED GRAPH NORMALIZATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have emerged as powerful category of learn- ing architecture for handling graph-structured data. However, the existing GNNs usually follow the neighborhood aggregation scheme, ignoring the structural char- acteristics in the node-induced subgraphs, which limits their expressiveness for the downstream tasks of both the graph- and node-level predictions. In this paper, we strive to strengthen the general discriminative capabilities of GNNs by devising a dedicated plug-and-play normalization scheme, termed as Motiffinducce Normal- ization (MotifNorm), that explicitly considers the intra-connection information within each node-induced subgraph. To this end, we embed the motif-induced structural weights at the beginning and the end of the standard BatchNorm, well as incorporate the graph instance-specific statistics for improved distinguish- able capabilities. In the meantime, we provide the theoretical analysis to support that the MotifNorm scheme can help alleviate the over-smoothing issue, which is conducive to designing deeper GNNs. Experimental results on eight popular benchmarks across all the tasks of the graph, node, as well as link property pre- dictions, demonstrate the effectiveness of the proposed method. Our code is made available in the supplementary material.
INTRODUCTION
In recent years, Graph Neural Networks (GNNs) have emerged as the mainstream deep learning architectures to analyze irregular samples where information is present in the form of graphs, which usually employs the message-pant paasignggggngggggge aggregation mechanism encode node features from local neighborhood representations Kiip & Welling 2017 Veličković et al. 2018 Xu et al. 2019 Yang al. 2020b, Hao et al. 2021 Dwivedi et al. 2022b). As powerful class graph-relevant net- works, these architectures have shown encouraging performance in various domains such as cell clustering (Li et al. 2022 Alghamdi et al. 2021 I) chemical prediction (Tavakoli et al. 2022 Zhong ct al. 2022), social networks (Bouritsas et al.) 2022 Dwivedi et al.) 2022b), traffic networks (Bui
et al. 2021 Li & Zhu 2021). combinatorial optimization (Schuetz et al. 2022 Cappart et al. 2021
and power grids (Boyaci et al. 2021 Chen et al. 2022a).
However, the commonly used pussage-passsing mechanism, i.c., aggregating the representations from neighborhoods, limits the expressive capability of GNNs address the subtree-isomorpic phenomenon prevalent in the real world (Wijesinghe & Wang 2022). As shown in Figure [Ta]] subgraphs S,, Sy, induced by U1, U2 are subtree-isomorphicc which decreases the GNNs' expres- sivity in graph-level and node-level prediction, i.c., (1) Graph-level Straightforward neighborhood aggregations, ignoring the characterises of the node-induced subgraphs, lead complete indistin- guishability in the subtree-isomorphic case, which thus limits the GNNs' expressivity to be bottle- necked by the Weisfeiler-Lemaal (WL) (Weisfeiler & Leman 1968) test. (2) Node-level: Under the background of over-smoothing (as illustrated in Figure ((b) ). the smoothing problem among the root representations of jubrree-soomorphic substructures will become worser when aggregating the
similar representations from their neighborhoods without structural characterises be considered.
In this paper, we strive to develop a general framework, compensating for the ignored characteristics among the node-induced structures, to improve the graph expressivity over the prevalent message- passing GNNs for various graph downstream tasks, e.g., graph, node and link predictions. Driven by the fact that deep models usually follow the CNA architecture, i.e., stack of convolution, malization and activation, where the normalization module generally follows GNNs convolution operations, we accordingly focus developing higher-expressivity generalized normalization

---

Under review as a conference paper at ICLR 2023
Subgruph, root 1/2
Subgraph, root 1/2
GraphSage, L.
GraphSage, L 20
2
1.0
0.5
0.5
0.0
0.0
-0.5
-0.5
-1.0
-0.5
0.0
0.5
1.0
+1.9
-1.0
-0.5
0.0
0.5
1.0
(a) Subtree-isomorphic
(b) Over-smoothing phenomenon
Figure I: (a) The illustration the isomorecii phenomenon, where two subgraphs S.y and Sog are induced by root node t1 and U2 with the same degree k 4, but the connection information among neighborhoods is different. (b) The t-SNE illustration of over-smoothing issue on Cora dataset when GraphSage layer is up 20. Here, we show the first three categories for visualization.
scheme to enhance the discriminative abilities of various GNNs' architectures. Thus, the question is, "how to design such powerful and general normalization module with the characteristics of node-induced substructures embedded ?"
To address this challenge, this paper devises innovative normalization mechanism, termed as Motif-inducee Normalization (MotifNorm), that explicitly considers the intra-connection informa- tion each node-induced subgraph (i.e., motif (Leskovec) (021I) and embeds the achieved struc- tural factors into the normalization module to improve the expressive power of GNNs. Specifi- cally, we start by empirically disentangling the standard normalization into two stages, i.e., cen- tering & scaling (CS) and affine transformation (AT) operations. We then concentrate on mining the intra-connection information in the node-induced subgraphs, and develop two elaborated strate- gies, termed as representation calibration and representation enhancement, embed the achieved structural information into CS and AT operations. Eventually, we demonstrate that MotifNorm can generally improve the GNNs expressivity for the task of graph, node and link predictions via ex- tensive experimental analysis.
In sum, the contributions of this work can be summarized as follows:
Driven by the conjecture that a higher-expesssivity normalization with abundant graph structure power can generally strengthen the GNNs' performance, we develop novel normalization scheme, termed as MotifNorm, to embed structural information into GNNs' aggregations.
We develop two elaborated strategies, i.e., representation calibration and representation en- hancement, tailored to embed the motif-induced structural factor into CS and AT operations for the establishment of MotifNorm in GNNs.
We provide extensive experimental analysis eight popular benchmarks across various do- mains, including graph, node and link property predictions, demonstrating that the proposed model is efficient and consistently yield encouraging results.
It is worth mentioning that MotifNorm maintains the computational simplicity, which is beneficial to the model training for highly complicated tasks.
2 RELATED WORKS
In this section, we briefly introduce the existing normalization architectures in GNNs, which are commonly specific to the type of downstream tasks, i.e., graph-level and node-level tasks.
Graph-level Normalization. To address graph-level representation learning, Xu et al. (2019) adopt the standard BatchNorm (Toffe Szegedy 2015) module to GIN as a plug-in component to stabilize the model's training. Based on the BatchNorm, Dwivedi et al. (2022a) normalize the node features with respect to the graph size to resize the feature space, and propose the ExpreNorm. To address the expressiveness degradation of GNNs for highly regular graphs, Cai et al. (2021) propose the GraphNorm with a learnable parameter for each feature dimension based on instance normalization. To adopt the advances of different normalizations, Chen et al. (002cc) propose UnityNorm by op-
2

---

Under review as a conference paper at ICLR 2023
timizing a weighted combination of four normalization techniques, which automatically selects single best or the best combination for a specific task.
Node-level Normalization. This type of mechanism tries to rescale node representations for the purpose of alleviating over-smoothing issues (as shown in Figure [ Yang et al. (2020a) de- sign the MeanNorm trick to improve GCN training by interpreting the effect of mean subtraction as approximating the Fiedler vector. [hou et al. (2021) scale each node's ' features using its own stan- dard deviation and proposes variance-controllinng technique, termed as NodeNorm, to address the variance inflammation caused by GNNs. To constrain the pairwise node distance, ZZhao & Akoglu (2200)) introduce PairNorm prevent node embeddings from over-smoothing on the node classi- fication task. Furthermore, Liang et al. (2022) design ResNorm from the perspective of long-tailed degree distribution and add a shift operation a low-cost manner to alleviate over-smoothing.
However, these approaches are usually task-specific in GNNs' architectures, which means that they are not always significant in general contribution various downstream tasks. Further- more, the characteristics of node-induced substructures, which trouble GNNs performance in various downstream tasks, are ignored by these normalizations.
MOTIF-INDUCED GRAPH NORMALIZATION
In this section, we begin by give the preliminary with regard to our proposed MotfiNorm, along the way, introduce notations and a basis definition of motif-induced information.
Let = (Va, Fe) denotes a undirected graph with n vertices and m edges, where Va= (U1, U2, Un an set of vertices and EG is unordered set of edges. (Ne) {u E Val(v, u) E EG} } denotes the neighbor set of vertex v, and its neighborhood subgraph S, is induced by N(x) = (we) U which
contains all edges in EG that have both endpoints in (v).. As shown in Figure [(a] S., and S., are
the induced subgraphs of U1 and U2. Their structural information are defined as:
Definition 1. The motif-induced induced information E(Su,) denotes the structural weight of substructure subgraph (Leskovec 2021) with regard to where is formulated as:
Sau ie.,
E(Se,) ( DV((Vs..,))
B.e.ss//VVV..... where |-1 denotes cardinality. p((Es., Es,, 1/([V.,, s..1. (VV.,, and (VV.,, |Vsu, I respectively refers to the density and power of Su. This focuses while two different subgraphs are -iioorriioomophicc on the contrary, focuses more on node power.
focuses more on edge information
3.1
PRELIMINARY
Batch normalization can be empirically divided into two stages, i.c. centering & scaling (CS) and affine transformation (AT) operations. For the input features H E aa the CS and AT follow:
H E(H)
Hes VID(H +
(2)
AT: HAT Hes 3 07+ 3
where @ is the dot product with the broadcast mechanism. TEHH) and DHH) denote mean and variance statistics, and 7. B E R are the learned scale and bias factors. In this work, we aim embed structural weights into BatchNorm, and thus take batch of graphs for example to give notations.
Batch Graphs. For a batch of graphs G = (GI,..,,Gr, G. with node set Vo = Ve, U Ve..... Va... {ui,..., Un and feature matrix H E IRaxd Motif-induced weights of this batch nodes is rep- resented as Mg= {(Sv)) = [<(Sv,, ): 5:5(vv, ):... )] = )..,..)....,E( E(S.,)) Rax1, The segment cntiuttiionnommlzzaaiiii Max= [F(E(Sva, ((() F(ESs:, ))l m where F(g(Sva,)) = E(Svo,)) // E(Sve,) R/ x1, denotes the sunmation-normalzzaioo in each graph.
3.2 MOTIENORM FOR GNNS
The commonly used message-passingg aggregations are node-specific, i.c., ignoring the character- isties in the node-induced subgraphs, which limits the expressive capability of GNNs in various
3

---

Under review as a conference paper at ICLR 2023
downstream tasks. Therefore, present generalized graph normalization framework, termed as MotifNorm, to compensate for the ignored structural characteristics by GNNs, and develop two elaborated strategies: representation calibration (RC) and representation enhancement (RE).
Representation Calibration (RC). Before the CS stage, we calibrate the inputs by injecting the motif-induced weights as well as incorporate the graph instance-specific statistics into representa- tions, which balances the distribution differences along with embedding structural information. For the input feature Rnxd, the RC is formulated as:
RC: HEc H + whc @ Haa (Mac1a),
where 1 is the d-dimensional all-one cloumn vectors and denotes the dot product operation. Wec E R 1xd is learned weight parameter. Mge Maa Mg E R"x1 is the calibration factor for RC, which is explained in details in Appendix A.3 Hsa E R is the segment averaging of H, obtained by sharing the average node features of each graph with its nodes, where each individual graph is called a segment in the DGL implementation (Wang et al. 2019).
Representation Enhancement (RE). Right after the CS operation, node features Hes strained into a fixed variance range and distinctive information is slightly weakened. Thus, we design the RE operation embed motif-induced structural information into AT stage for the en- hancement the final representations. The formulation of RE is written as follows:
(4) where Wss 1 is learned weight parameter, and Pow(.) is the exponential function. To imitate affine weights in AT for each channel, we perform the segment uummation-normizatiin on calibration factor MRC and repeats columns obtain enhancement factor Maz Raad which ensures column signatures of P Pow (Mas, Wan) 1 are consistent.
RE: : HRg Hes Pow(MRe Wae),
Expressivity Analysis. MotfiNorm with injected RC and RE operation, compensating structural characteristics of subgraphs for GNNs, can generally improve graph expressivities as follows:
(1) Graph-level: For graph prediction tasks, MottiNorm compensates for the structural information to distinguish the uubtree-isomorphee case that 1-WL can not recognize, which could extend the GNNs more expressive than the 1-WL test. Specifically, an arbitrary GNN equipped with Motfi- Norm is capable of more expressive abilities than the 1-WL test in distinguishing k-regular graphs.
(2) Node-level: The ignored structural information strengthens the node representations, which beneficial to the downstream recognition tasks. Furthermore, MotifNorm with structural weights injected can help alleviate the over-smoothing issue, which is analyzed the following Theorem [
(3) Training stability: The RC operation is beneficial to stabilize model training, which makes nor- malization operation less reliant on the running means and balances the distribution differences by considering the graph instance-specific statistics and is analyzed in the following Proposition [
Theorem 1. MotifNorm helps alleviate the oversmoothing issue.
Proof. Given two extremely similar embeddings of u and v (i.e., |H Hyl2 2 S e). Assume for simplicity that ||H,]|2 = ||H,/la = 1, [|al||2 2| 2 c, and the motif-induced information scores between u and v differs considerable margin [l 12),, (Mac (Ma=1?) 12) 2 2e/c. We can obtain
[HH, + (Wec (Mac17)) Hμ Hy (H, + (wec @ (Msc 1 17),,
H, + H
l|
2
Hg + H
2 |H, - H [[((we @ (MRz (kr:17)), (weR ④ (Mrc 1)),)
l12
2
Ha + H 2
2 - - ||wxlll2 [M 17), (M3c (Mac17)ol1 12
11
2 - + 2e =
where the subscripts u, 2 denote the w-th and v-th row of matrix E x This inequality demon- strates that our RC operation could differentiate two nodes by margin even when their node embeddings become extremely similar after L-layer GNNs. Similarly, RE operation can also differ- entiates the embeddings, and the theoretical analysis is provided in A.1
4

---

Under review as a conference paper at ICLR 2023
Proposition 1. RC operation is beneficial to stabilzing the model training.
Proof. The complete proof is provided in Appendix A.2
3.3 THE IMPLEMENTATION OF MOTIFNORM
We merge RE operation into AT for simpler formultation. Given the input feature H R"xd the formulation of the MotifNorm is written as:
RC HRC H + WRC @ Haa (Ma=12),
Hac E(Hoc)
CS Hos (D(HRR)) +
(5)
AT HAT Hos (r + P)/2 + 8,
where I' PoW(MRR. Wae) and Har is the output of MotifNorm. To this end, we add RC and RE operations at the beginning and ending of the original BatchNorm layer to strengthen the expressivity power after GNNs' convolution. The additional RC and RE operations are the product in Raxd thus their time complexity is (nd).
4 EXPERIMENTS
To demonstrate the effectiveness of the proposed MotifNorm in different GNNs, we conduct exper- iments three types of graph tasks, including graph-, node- and link-level predictions.
Eight datasets are employed in three types of tasks, includ- ing (i) Graph predictions: IMDB-BINARY, ggbg-moltoxcast, ogbg-molhiv, and ZINC. (ii) Node predictions: Cora, Pubmed and ogbn-proteins. (iii) Link predictions: oghl- collab. Their basic statistics are summa- rized in Table
Benchmark Datasets.
Table The statistic information of the benchmark datasets under different graph-structured tasks.
Task
Avg. #nodes
Avg.
Dataset
#Graphs
level
#edges
graph
1,000
19.8
193.1
ogbg-mol molog-ootox
graph
8,576
18.8
19.3
ogbg-molhiv
graph
41,127
25.5
27.5
ZINC
graph
10,000
23.2
49.8
Baseline Methods. We compare our Mo- tifNorm to various types normaliza-
Cora
node
2,708
5,429
Pubmed
node
19,717
44,338
tion baselines for GNNs, including Batch-
ogbn-protccns
node
132,534
39,561,255
Norm (Ioffe & Szegedy 2015). Uni-
ogbl-collab
link
235,868
1,285,465
tyNorm (Chen et al.] 2022c), Graph-
Norm Cai et al. 2021) ExpreNorm (Dwivedi et al. 2022a) for graph predictions, and Group-
Norm (Zhou al.] (020). PairNorm (Zhao & Akoglu 2020a). MeanNorm (Yang al. 2020a
NodeNorm (Zhou et al. 2021) for all three tasks.
More details about the datasets, baselines and experimental setups provided in Appendix B.
In the following experiments, we aim to answer the questions: (i) Can MotifNorm improve the ex- pressivity for graph isomorphism test, especially go beyond 1-WL on k-regular graphs? (Section 4.1)
(ii) Can MotifNorm help alleviate the over-smoothing issue? (Section 4.2 (iii) Can MotifNNrr gen-
cralize to various graph tasks? (Section 4.3
4.1 EXPERIMENTAL ANALYSIS ON GRAPH ISOMORPHISM TEST
The IMDB BINARY is a well-known graph isomorphism test dataset consisting of various k-regular graphs, which has become a common-uss -uee benehmark for evaluating the expressivity of GNNs. To make the training, valid and test sets follow the same distribution as possible, we adopt hierarchical dataset splitting strategy based on the structural statistics of graphs (More detailed description are provided in Appendix B. For graph isomorphism test, Graph Isomorphism Network (GIN) (Xu et al. 2019) is known to be as powerful as 1-WL. Notably, GIN consists a neighborhood aggregation operation and a multi-layer perception layer (MLP), and this motivates comparison experiment: comparing a one-layer MLP+MMttfNorm with one-layer GIN to directly demonstrate MotifNorm's expressivities in distinguishing k-regular graphs.
5

---

Under review as a conference paper at ICLR 2023
0.8
0.8
MLP
Training ROC-AUC
Valid ROC-AUC AUC
0.65
GIN
MLP+MatiNNarm GIN+ MotifNorm
0.7-
0.7-
Training
MLP
MLP
0.60
0.6
MobifNom
0.6
MotfNoo
0.55
GIN+MotiNNorm
GIN+MotifNorm
0.5
0.5
50
100
150
50
100
150
50
100
150
Epoch
Epoch
Epoch
Figure 2: Learning curves of one-layer MLP, GIN, MLP + MotifNorm and GIN MotifNorm on
IMDB-BINARY dataset with various k-regular graphs.
Table 2: Experimental results on IMDB-BINARY dataset with various k-regular graphs. results under different backbones are highlighted with boldface.
The best
Normalization
ROC-AUC
LOSS
Layers
Batchnorm Mo Moci[Norm
Test Split
Valid Split
Test Split
Valid Split
56.66 1.09
57.05
0..1
0.6961
0.6961
MLP
56.86 0.72
57.83
0.6954
0.6954
78.16 0.52
78.69
0.44
0.5631
0.5581
77.40 =
77.69
0.13
0.5684
0.5658
GIN
78.11 = 0.10
0.5655
0,5593
78.42 0.15
78.89
0.15
0.5584
0,5565
+
77.54
0.16
0.5696
0.5688
GSN
78.18 0.23
78.13
0.11
0.5637
0.5633
GraphSNN
7
77.52 0.16
77.61
0.18
0.5691
0.5671
78.24 0.30
78.06
0.15
0.5631
0.5636
78.76
0.5625
0,5590
CIN
0.35 79.55
79.62
0.38
0.5539
0.5510
GCN
7
4
78.78
76.75
1.01
1.31
0.69 79.03
76.96
0.61
0.5755
0.5597
0.5640
0.5504
75.10
1.51
75.95
1.27
0.5866
0.5852
CAT
78.87 0.80
79.20
0.56
0,5559
0,5448
78.90 0.63
79.28
0.5555
0,5543
GSN
4
79.22
0.71
79.70
0.59
0.5536
0.5527
4
79.16
0.67
79.35
0.82
0.5541
0.5530
GraphSNN
79,89
0.74
79.93
0.77
0.5517
0,5506
As illustrated in Figure 2. the vanilla MLP cannot capture any structural information and perform poorly, while the proposed MotifNorm method successfully improve the performance of MLP and even exceeds the vanilla GIN. Furthermore, Table 2 provides the quantitative comparison results, where GSN (Bouritsas al. 2022) and GraphSNN (Wijesinghe & Wang 2022) are two recent popular methods realizing the higher expressivity than the 1-WL. From these comparison results, the performance of one-layer MLP with MotifNorm better than that of one-layer GIN, GSN, and GraphSNN, Moreover, the commonly used GNNs equipped with MotifNorm, e.g., GCN and GAT, achieve higher ROC-AUC than GIN when the layer is set as 4. GIN with MotifNorm achieves better performance and even goes beyond the GSN and GraphSNN. Furthermore, MotifNorm can further enhance the expressivity of GSN and GraphSNN. More detailed results on provided in Appendix B.2
4.2 EXPERIMENTAL ANALYSIS ON THE
ISSUE
To show the effectiveness MotifNorm for alleviating the over-smoothing issue GNNs, we visualize the first three categories of Cora dataset in 2D space for better illustration. We lect PairNorm, NodeNorm, MeanNorm. GroupNorm and BatchNorm for comparison and set the number of layer as 32. Figure 3(a) 3(f) show the t-SNE visualization of different normalization techniques, and we can find that none of them suffer from the over-smoothing issue like Graph- Sage with BatchNorm (shown in Figure ((b).. However, MotifNorm better distinguish different

---

Under review as a conference paper at ICLR 2023
1.0
1.0
0.5
0.5
0.0
0.0
-0.5
-0.5
-0.5
-1.0
-1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
MotifNorm, Layer=32
(b) GroupÑorm, Layer-32
(c) BatchNorm, Layer=32
1.0
1.0
0.0-
0.5
0.5
-1.0
110
-0.5
0.0
0.5
1.0
-10
1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
(d) NodeNorm, Layer-32
(c) MeanNorm, Layer=32
(f) PairNorm, Layer-32
Figure 3: The t-SNE visualization of node representations using GCN with different normalization methods on Cora dataset.
MotifNorm
GroupNorm
BatchNorm
NodeNorm
MeanNorm
0.8
0.12
0.30
0.6
0.11
0.4
0.09
0.20
0.2
0.08
30
30
layers
layers
layers
(a) Accuracy
(b) Intra-class distance
(c) Inter-class distance
Figure 4: Experimental results of GCN with different normalization methods Cora dataset.
categories into different clusters, i.e., the other normalization methods may lead to the loss of dis- criminant information and make the representations entangled.
Furthermore, we provide the quantitative results by considering three metrics including accuracy, intra-class distance and inter-class distance. In details, we set layers from 2 to 32 with the step size as 2, and visualize the line chart in Figure (a)uree((aaaae 4(a)-4(C) Figure 4(a) shows the accuracy with regard to layers, which directly demonstrates the superiority of MotifNorm when GNNs go deeper. In order to characterize the disentangling capability of different normalizations, distance and inter-class distance with layers increasing in Figure (bb) and [[c). As shown these two figures, MotifNorm obtains lower intra-class distance and higher inter-class distance, which means that the proposed MotifNorm enjoys better disentangling ability. We provide more t-SNE visualizations of different layer number and different GNNs' backbones in Appendix B.3
calculate the intra-class
4.3 MORE COMPARISONS ON THE OTHER SIX DATASETS
For graph prediction task, we compare normalizations ogbg-moltoxcast, ogbg-molhiv and ZINC by using GCN and GAT as backbones, where ZINC is a graph regression dataset. For node and conduct experiments
link property predictions protein-pros protein association network dataset (ogbn-proteins) and a collaboration network between authors (ogbl-collab) by using GCN as backbone. The details follow:
social network dataset (Pubmed), one

---

Under review as a conference paper at ICLR 2023
Table 3: Experimental results of different normalization methods the graph prediction task. We
use GCN, GAT as the backbones. The best results on cach dataset are highlighted with boldface.
ogbg moltoxcast
ogbg-molhiv molhiv
ZINC
Methods
[= 4
== 16
(
32
-= 4
-= 16
[ 32
(=4 4
= 16
= 32
NoNorm
61.13
59.34
56.08
76.01
71.90
60.59
0.643
0.690
0.748
GraphNorm
60.78
53.75
53.36
75.59
65.55
66.49
0.592
0.655
1.547
GCN
Bat catom
63.39
59.73
53.47
76.11
76.62
74.21
0.573
0.611
0.655
UnityNore rm
63.86
61.94
59.18
75.94
72.14
69.44
0.552
0.576
0.650
ExpreNors rm
64.97
57.91
57.82
76.05
76.75
72.36
0.564
0.570
0.646
MotifNorm 66.92
65.19
63.40
77.29
77.71
75.99
0.489
0.524
0.523
NoNorm 62.61
50.84
50.12
76.71
57.38
50.64
0.714
1.541
1.547
GraphNorm
60.53
52.79
53.22
75.30
73.86
64.03
0.576
1.254
1.537
GAT
Batchhorm 63.31
53.39
53.24
76.07
76.87
73.74
0.585
0.624
0.643
UnityNorn 63.47
58.76
57.13
75.91
76.19
75.46
0.563
0.621
0.777
ExpreNorn 65.56
57.65
57.60
76.99
72.24
72.56
0.555
0.562
1.451
MotiENorma
66.57
64.04
58.26
77.36
77.08
76.70
0.495
0.517
0.522
Table The comparison results of different normalization methods on the node prediction and link prediction task by using GCN as the backbone. The best results are highlighted with boldface.
Pubmed
ogbn- proteins
ogbl-collab
Settings
[ -
==
16
1 32
-=
16
[
32
4
16
= 32
NoNorm
76.16
54.67
45.58
69.16
63.24
63.15
35.38
22.11 11
15.24
PairNorm
74.25
56.24
55.13
69.28
63.15
63.00
31.26
23.22
14.69
GCN
NodeNorm
76.02
40.87
41.18
70.17
63.50
63.23
27.48
08.48
08.28
MeanNorm
76.05
73.40
65.34
69.14
63.05
62.40
33.28
22.56
16.16
GroupNorm
76.19
63.55
54.84
70.25
62.74
63.63
35.28
27.41
20.27
Bat rm
75.62
48.88
43.28
69.96
67.36
63.86
47.57
26.14 14
21.68
MotifNorm
77.08
76.66
67.81
71.69
68.66
68.05
51.65
50.01
47.65
Table 5: Comparisons with empirical tricks ogbg-molhiv and ZINC datasets.
Table 6: Comparisons with empirical tricks on oghn-proteins and ogbl-collab datasets.
Methods
ogbg-molhiv
ZINC
Methods
ogbn-proteins
ogbl-collab
NoNorm
77.21 0.430 0.473 + 0.006
PairNorm
69.84 + 0.533 47.75 0.190
UnityNorm
77.56 + 1.060 0.458 + 0.009
NodeNorm
72.53 + 1.514 48.28 = 1.100
ExpreNorm
77.99 = 0.545 0.436 = 0.008
MeanNorm
71.09 = 1.236 47.27 0.849
GraphNorm
78.10 + 1.115 0.396 = 0.008
GroupNorm
73.17 + 0.503 45.25 + 1.206
BatchNorm 78.07 = 0.782 0.398 = 0.003
BatchNorm
72.39 0.611 49.44 0.750
MotifNorm 78.76 + 0.371 0.358 = 0.009
MotifNorm 73.55 + 1.271 52.15 = 0.647
Firstly, we adopt the vanilla GNN model without any tricks (c.g., residual connection, etc.), and pro- vide the settings of the hyperparameter in Appendix B.I Accordingly the mean results (w.rt., 10 different seeds) shown Table B and Table we can conclude that MotifNorm generally improves the graph expressivity of GNNs for graph prediction task and help alleviate the over-smoothing issue with the increase of layers. Furthermore, we provide more comparison experiments by using GIN and GraphSage backbones in Appendix B.4
Secondly, we perform empirical tricks in GNNs for further comparison when generally obtaining better performances. The details of tricks different datasets: (1) oghg-molhiv: convolution with edge features, without input dropout, hidden dimension as 300, weight decay in (5e-5, le-5), resid- ual connection, GNN layers as 4. (2) ZINC: without input and hidden dropout, hidden dim 145, residual connection, GNN layers as 4. (3) ogbn-proteins: without input and hidden dropout, hidden dim as 256, GNN layers as 2. (4) ogbl-collab: initial connection (Chen et al., 2020). GNN layers as 4. The results in Table 5 and Table [ demonstrate that MotifNorm preserves the superiority in graph, node and link prediction tasks compared with other existent normalizations.
4.4 ABLATION STUDY AND DISCUSSION
To explain the superior performance of MotifNorm, we perform extensive ablation studies to eval- uate the contributions of its two key components, i.e., representation calibration (RC) and represen-
8

---

Under review as a conference paper at ICLR 2023
0.85
0.700
0.1
RC weight
RE weight
0.675
0.80
NotifNorm
0.650
MotifNorm
0.0
0.75
MotifNorm w/o RE
0.625
MotifNorm w/o RE
MotifNorm w/o RC
MotifNorm w/o RC
NatchNorm
0.600
BatchNorm
-0.1
0.70
100 epochs
200
100 epochs
200
0
10
20
layers
Training ROC-AUC
(b) Valid ROC-AUC
(c) Average weight Wac, Was
Figure 5: Abalation study of the Representation Calibration (RC) and Representation Enhance- ment (RE) operations in MotifNorm on the ogbg-moltoxcast dataset. Here we use GCN as the basic backbone to conduct the abalation study.
tation enhancement (RE) operations, Firstly. we show in Figure 5he ablation performance of GCN on ogbg- ogbg-moltoxcast. Figure ((a)ue((aaaaaa ((b)
the ROC-AUC results with regard to training epochs when the layer number is set to 4, which show that both RC and RE can improve the classification performance. Furthermore, by comparing these two figures, RC performs better than RE in terms of recognition results, which plugs at the beginning of BatchNorm with the graph instance-specific statistics embedded.
To further explore the significance of RC and RE at different layers, compute the mean values of Whc and WaE. which are visualized in Figure Fi)) As can be seen from the mean statistis of Wacs Wse among 32 layers' GCN, the absolute values of Wsc and tae become larger when the network goes deeper (especially in the last few layers), indicating that the structural information becomes more and more critical with the increase numbers of layers.
To evaluate the additional cost of RC and RE opera- tions, provide the runtime, parameter and memory comparison by using GCN (1 4) with BatchNorm and MotfiNorm on the ogbg-molhiv dataset. Here, we pro- vide the cost of runtime and memory by performing the code on NVIDIA A40, The cost information is provided in Table 7
Table 7: The cost comparisons between BatchNorm and MotifNorm.
runtime parameter memory
caNoom 15.2s/epoch
291.6K 2305M
MotifNorm 22, 22.6s/epuch
293.2K 2347M
Discussion. The main contribution this work is to propose a more expressive normalization mod- ule, which can be plugged into any GNN architecture. Unlike existing normalization methods that are usually task-specific and also without substructure information, the proposed method explicitly considers the subgraph information to strengthen the graph expressivity across various graph tasks. In particular, for the task of graph classification, MotifNorm extends GNNs beyond the 1-WL test in distinguishing k-regular graphs. On the other hand, when the number of GNNs layers becomes larger, MotifNorm can help alleviate the over-smoothing problem and meanwhile maintain better discriminative power for the node-relevant predictions.
CONCLUSION
In this paper, we introduce eigher-expressiviiyy normalization architecture with an abundance of graph structure-specific information embedded to generally improve GNNs' expressivities and rep- resentatives for various graph tasks. We first empirically disentangle the standard normalization into two stages, i.e., centering & scaling (CS) and affine transformation (AT) operations, and then develop two skillful strategies to embed the subgraph structural information into CS and AT op- erations. Finally, we provide theoretical analysis to support that MotifNorm can extend GNNs beyond the 1-WL test in distinguishing k- k-regular graphs and exemplify why can help alleviate the over-smoothing issue when GNNs go deeper. Experimental results 10 popular benchmarks show that our method is highly efficient and can generally improve the performance of GNNs for various graph tasks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Norah Alghamdi, Wennan Chang, Pengtao Dang, Xiaoyu Lu, Changlin Wan, Silpa Gampala, Zhi Huang, Jiashi Wang, Qin Ma, Yong Zang, al. A graph neural network model to estimate cell- wise metabolic flux using single-cell ma-seg data. Genome research, 31(10): 1877-1848778884 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 2022.
Osman Boyaci, Mohammad Rasoul Narimani, Katherine Davis, Muhammad Ismail, Thomas Overbye, and Erchin Serpedin. Joint detection and localization of stealth false data injection attacks in smart grids using graph neural networks. IEEE Transactions on Smart Grid, 13(1): 807-819, 2021.
Khac-Hoai Nam Bui, Jiho Cho, and Hongsuk Yi. Spatial-temporal graph neural network for traffic forecasting: An overview and open research issues. Applied Intelligence, pp. 1-12, 2021.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di Hc, Tic-yan Liu, and Liwei Wang. Graphnorm: A prin- cipled approach to accelerating graph neural network training. In International Conference Machine Learning, pp. 1204-1215. PMLR, 2021.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 2021.
Kaixuan Chen, Shunyu Liu, Na Yu, Rong Yan, Quan Zhang, Jie Song, Zunlei Feng, and Mingli Song. Distribution-awas aware graph representation learning for transient stability assessment of power system. International Joint Conference on Neural Networks (IJCNN), 2022a.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735, 2020.
Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenging Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: comprehensive benchmark study, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022b.
Yihao Chen, Xin Tang, Xianbiao Qi, Chun-Guang Guang Li, and Rong Xiao. Learning graph normalization for graph neural networks. Neurocomputing, 493:613 3-6555,66---- 2022c.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.009922 2022a.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2022b.
Shang-Hua Gao, Qi Han, Duo Li, Ming-Ming Cheng, and Pai Peng. Representative batch normal- ization with feature calibration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8669-8679, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 2017.
Yunzhi Hao, Xinchao Wang, Xingen Wang, Xinyu Wang, Chun Chen, and Mingli Song. Walking with attention: Self-guided walking for heterogeneous graph embedding. IEEE Transactions on Knowledge and Data Engineering, 2021.
Weihua Hu, Matthias Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 1022188222 18-2233,, 2020.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general graph convolutional networks. In International Conference on Learning Representations, ICLR 2020, 2020.
10

---

Under review as a conference paper at ICLR 2023
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448 456, 2015.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52 (7):1757-1768, 2012.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference on Learning Representation, 2017.
Jure Leskovec. Fast neural subgraph matching and counting. Stanford University, CS224W: Ma- chine Learning with Graphs, 2021. URL httttt/tp///2// 4w. wtwp:2222wwtaaaadddd.oooo
Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In International Conference Computer Vision, ICCV, pp. 9266-9275, 2019.
Jiachen Li, Siheng Chen, Xiaoyong Pan, Ye Yuan, and Hong-Bin Shen. Cell clustering for spatial transcriptomics data with graph neural networks. Nature Computational Science, 2(6):399-44) 2022.
Mengzhang Li and Zhanxing Zhu. Spatial-temporal fusion graph neural networks for traffic flow forecasting. In Proceedings of the AAAI conference arlificial intelligence, pp. 4189-4196, 2021.
Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, and Jieping Ye. Resnorm: Tackling long- tailed degree distribution issue in graph neural networks via normalization. arXiv, 2022. doi: 20.550//rXiv.220..0888
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 338-348, 2020.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference Learning Repre- sentations, ICLR 2020, 2020.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Mohammadamin Tavakoli, Aaron Mood, David Van Vranken, and Pierre Baldi. Quantum mechanics and machine learning synergies: graph attention neural networks to predict chemical reactivity. Journal of Chemical Information and Modeling, 6219))2121-2132, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference Learning Representation, 2018.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang- Deep graph library: graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv:1909.00 01515, 2019.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Asiri Wijesinghe and Qing Wang- A new perspective on" how graph neural networks go beyond "eisseileerleemman". In International Conference on Learning Representations, 2022.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871, 2019.
11

---

Under review as a conference paper at ICLR 2023
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, pp. 5449-5458, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens. arXiv preprint arXiv:2003.13663, 2020a.
Yiding Yang, Zunlei Feng, Mingli Song. and Xinchao Wang. Factorizable graph convolutional networks. Advances in Neural Information Processing Systems, 13:20286-20296 2020b.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International
Conference on Learning Representations, ICLR, 2020a.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, ICLR, 2020b.
Zipeng Zhong, Jie Song, Zunlei Feng, Tiantao Liu, Lingxiang Jia, Shaolun Yao, Min Wu, Tingjun Hou, and Mingli Song. Root-aligned smiles: tight representation for chemical reaction predic- tion. Chemical Science, 13(31):9023- 9034449922--994, 2022.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. Advances in neural information processing systems, 33:4917-4922,, 2020.
Kuangqi Zhou, Yanfei Dong. Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng- Understanding and resolving performance degradation in deep graph convolutional networks. In ACM International Conference on Information and Knowledge Management CIKM, pp. 2728- 2737, 2021.
12

---

Under review as a conference paper at ICLR 2023
A
THEOREM ANALYSIS
This section provides the corresponding proofs to support theorems in the main context.
A.1 PROOF FOR THEOREM
I
Theorem 1. MotifNorm helps alleviate the oversmoothing issue.
Proof. Given two extremely similar embeddings of and v (i.e., |[,, H 2 & c). Assume for simplicity that ||Hul|2 ||Hullz || 12 2 C1, and the motif-induced information scores between u and u differs considerable margin [[ 12) (MRx11).. 2 2e/c We can obtain
(H, + (Wec @ (M)c42)).. H., + H (H, + (Wac @ (Mac 1 )),
H. + H
112
2
H, + H
2 |H, - H + [[((wc @ 12)) - (WRe O (Mac12)),
l12
2
2 - + ||wzll2 [M - (Mac (M Hu + H
112
2
2 6 26 e,
where the subscripts u, denote the u-th and v-th row of matrix Raxd This inequal- ity demonstrates that our RC operation could differentiate two nodes by margin even when their node embeddings become extremely similar after L-layer GNNs. Similarly, by assuming [| w I C2 and [|oowMMRg, Wae), oowl (Mæs Wge), 2 (1+ c2) e, can prove that the RE operation differentiates the embedding with motif induced information:
WRR),, H. Pow (MRe WRE), H
|| Was), (H., H.) + [Pow(Mass War).. Pow(Mas, Wan).) Hullz
2 ||Poow (MaB, WRE), (H,, H2))l2 + ((Pow(Map WRE),, - Pow WRs),) H2ll2 02 e (1 02)
The proof is complete.
A.2 PROOF FOR PROPOSITION
Proposition 1. RC operation is beneficial to stabilzing the model training.
Proof. The RC operation is formulated as
HRC = Wkc @ Haa (Ma:12))
(6)
where and 1, is d-dimensional all-one column vector. Here Hşa. introduces the current graph's spsencc- information, i.e., mean representations each graph. Wac is a learnable weight balancing mini-batch and instance-specific statistics. Assume the number of nodes in each graph is consistent. The expectation of input features after RC, i.e., [E(Hec), can be represented as
E (HRc) (1 WPc (Mac 17)) E(H).
Let us respectively consider the following centering operation of normalization for the original input and the feature matrix Hgc after RC operation,
Hoenter-tn H B(H).
(8)
H Hgentor-RC Hgc E(H
where Hcenter-in and Heenter-Ro denote the centering operation H and Ha To compare the difference between these two centralized features, we perform
Hcenter RC Hoenter-T In
(Hac [E(Rc)) (H -E(H))
H + Who O (Mac 17) Has - (1 + WPc @ (Mac 12)) EE()) (H - E(H)
Who @ (Mac 1 (Hsa - B(H)),
13

---

Under review as a conference paper at ICLR 2023
G 4
G 4
Gp k=
G k=7
Figure 6: The illustration of four l--regular graphs with the same nodes but different structures. When directly performing the all weights will be equal to 1/8.
operation motif-induced information,
where the values in Mgc always positive numbers. When values in Wec close zero, the centering operation still relies on rumning statistics over the training set. On the other hand, the im- portance of graph instance-specific statisties grows when the absolute value of Whc becomes larger. Here, we ignore the affine transformation operation and assume values larger than the running mean, kept after the following activation layer, are important information for representations, and vice versa. In case of Wsc 0, while Hşa. > E(H), more important information tends to be preserved, and vice versa. In case of Wsc < O, while H5a > B(H), the noisy features tend be weakened, and vice versa. A similar analysis in BatchNorm2D has been provided in (Gao et al.] (202T), interested readers please refer to that for details. The main difference is that MotifNorm aims to embed struc- tural information to compensate for ignored characteristics in node-include subgraphs, while RBN proposed to address the distribution differences.
The proof is complete.
A.3 DESIGN THE REPRESENTATION CALIBRATION FACTOR
Here, we talk about the design of representation calibration factor M = Mar Mg, which is normalization for motif-induced weights Mg. we directly adopt the original weights, existing many unequal large values, it will make training oscillating. Thus, the normalization is essential for Mg- However, if we just perform summation normalizzaiiiiiiinnnnnnn. an arbitrary graph (i.e., Mss), will not distinguish two graphs with the same nodes but different degrees, e.g., four graphs in Figure 6 where each weight will become 1/8. To this end, we design the above normalization technique to strengthen the motif power for the representation calibration operation.
14

---

Under review as a conference paper at ICLR 2023
B EXPERIMENTAL DETAILS
B.1 MORE DETAILS OF BENCHMARK DATASETS AND BASELINE METHODS
Benchmark Datasets. For the task of graph property prediction, we select MIDR-BINARY, ogbg- moltoxcast, ogbg-molhiv and ZINC datasets. The BOBB-BINARY is k-regular dataset for binary classification task, which means that each node has a degree k. The ogbg-moltoxcast collected for multi-task classification task, where the number of the tasks is 617. The egbg-molhie is a molecule dataset that used for binary classification task, but the ouput dimension of the end-to-end GNNs is I because its metric is ROC-AUC. The ZINC is the real-world molecule dataset for the example reconstruction. In this paper, we follow the work in (Dwivedi et al., 2022a) to use ZINC for the task of graph regression. These graph prediction datasets from (Morris et al., 2020 Hu al., 2020 Irwin et al.] 2012) respectively. For the node level prediction, we select four benchmark datasets including Cora, Pubmed and ogbn-proteins. The first three datasets are the social network and the last one is a protein-protein association network dataset. For the evalutation of link property prediction. we select ogbl-collab dataset in this paper. These node and link prediction datasets are Hu et al. 2020) respectively. More detailed dataset information is
from (Kipf & Welling 2017:
provided in Table
Baseline Methods. To evalute our proposed MotifNorm module, we need to compare other normal- ization methods adopted in GNNs for various graph tasks, including BatchNorm (loffe & Szegedy) 2015), GraphNorm (Cai et al., (022). ExpreNorm (Dwivedi et al.] (022a) for graph property pre- diction, and PairNorm (Zhao & Akoglu 2020a), NodeNorm (Zhou et al. (02T), MeanNorm (Yang) 2020) for node and link property prediction. A part of these normalization methods are provided in (Chen et al. 2022b), and other source codes are provided by authors. For the backbone GNNs, we consider the most popuare sressage-passing architectures such as GCN (Kipf & Welling 2017), GAT (Veličković et al. 2018), GIN (Xu et al. 2019). SGC (Wu let al.] 2019) and GraphSage (Hamilton et al.] (017). Specially, we will compare with all above normlization modules. For the network architectures, we follow CNA architecture, i.e., convolution, normalization and activation. In this paper, we do not adopt any skills like drope-
cet al. 2020a). GroupNorm (Zhou et al.
MotifNorm
dge (Huang et al.) 22200 Rong et al. 2020). residual connection (Xu et al. 2018 Li et al. 2019 Liu
ct al. 2020), etc.
Experiment Setting, For different datasets, we provide more detailed statistics information in Ta-
ble X
The embedding dimension in each hidden layer on all datasets is set as 128. We optim the
by setting patience step as 10 or 15 to reduce learning rate. The learning rate 1e 3 for graph classification, and le
GNNs' architectures using porch.otii..l_scheeee
for node, link predictions. When the learning rate reduces to le - 5, the training will be termi- nated. More detailed statistics of experimental settings are provided in Table P Specially, we split the IMDB --BBAY dataset into train-valld--te format using a hierarchical architecture. In details, we first segment this dataset according to the edge density information into 10 set (i.c., the edge density E {0.0 - 0.1 U, {0.1 0.2)..., {0.9 1.0], and then sort the graphs using the average degree information. Finally, we select the samples in each segment using a fix step size as valid and test samples. The statistic information for splitting the valid and test set of Label-0 and Label-l on IMDB-BINARY is provide in Table I0 By adopting this splitting scheme, dis- tribution differences among train, valid and test sets are weakened (Experiment results show this contribution fact but without a theoretical basis now). The splitting details are implemented in the datasets/dgl imdb dataset.py. To reproduce the comparison results using single layer of MLP and GIN, the dropout is set to 0.0 and warming up the learning rate from 0.0 to le - 3 at the first 50 epoches. When layer is equal to 4, the doupout at the input layer is selected in {0.3, 0.4, 0.5) (i.e., -init_dp in the code), and hidden layer is set to 0.5. To draw the Figure 2 we remove the warmup operation for learning rate (i.c., remove warmuu in the shell files).
Implementation. MotifNorm needs to process the motif-induced weight into datasets and then load this processing information to embed structural information into node representations. Especially for the node-relevant classification, node representations need to contain the same power before MotifNorm. Thus, we perform the 1-2 normalization to ensure their power are consistent. The two scripts are at: datasets/preppooess.py and moduule//norm/moiifnoonm
15

---

Under review as a conference paper at ICLR 2023
Table 8: The statistic information of 8 benchmark datasets.
Avg.
Avg.
Dataset Name
Dataset Type
Task Type
#Graphs
#Nodes
#Edges
IMDB BINARY
molecular
Graph classification
1,000
19.8
193.1
oobg-toxcast
mo molecular Graph classification
8,576
18.8
19.3
ogbg molhiv
molecular Graph classification
41,127
25.5
27.5
2INC
molecular Graph regression
10,000
23.2
49.8
Cora
social Node classification
2,708
5,429
Pubmed
social Node classification
19,717
44,338
ogbn-proteins
proteins Node classification
132,534
39,561,252
ogbl-collab
social Link classification
235,868
1,285,465
Table 9; The detailed experimental settings of GNNs on various graph-structured tasks.
Name
Metries
Edge Conv.
Layers
LR Batch Size InitDim. HiDim. Weight decay Dropout
IMDB-BINARY
ROC-AUC False
1,4 le
32
128
128
0.0
0.0,
0.5
ogbg-toxcast
ROC-AUC
False
16, 32
128
9
128
0.0
0.5
ogbg-molhiv
ROC-AUC
False
4, 16,
256
128
0.0
2INC
MAE
False
4, 16, 32 1e
128
128
0.0
0.5
Cora
Accuracy
False
[0:2;32] le -
1433
128
0.0
0.5
Pubmed
Accuracy
False
4, 16, 32 le
500
128
0.0
0.5
ogbn-proteins
ROC-AUC
False
4, 16,
128
0.0
ogbl-collan
Hits@50
False
4, 16,
1024
128
0.0
0.0
Table 10: The statistic information for splitting IMDB-BINARE
0.0-0.1 0.1 0.2
0.2
0.3
0.3
0.4
0.5
0.6
0.7
0.7
0.7
0.8
0.8
0.9
0.9
1.0 Total Num.
Label-3
17
60
89
49
117
52
12
15
7
81
500
Tabal-1
81
145
58
97
30
1
0
500
Total Label
141
234
107
82
7
139
Steps
8
7
2
2
6
Label-3 Sel.
0
2
14
28
16
46
30
8
14
6
26
190
Label-1 - Sel.
4
20
40
18
38
14
4
0
0
18
156
Total Sel.
6
34
68
34
84
44
12
44
346
16

---

Under review as a conference paper at ICLR 2023
B.2 MORE COMPARISONS ON GRAPH ISOMORPHISM TEST
Experimental results on BIBB-BINARY dataset with various k-regular graphs. The best results under different backbones are highlighted with boldface.
Table 11:
Normalization
ROC-AUC
LOSS
NoNorm BatchNorm MotifNorm
Split
Valid Split
Train Split
Test Split
Valid Split Train Split
56.66 = 1.09 57.05 0.81 50.40 = 0.04
0.6961
0.6961
0.6927
MI.P
56.86
57.83 0.84 51.38 2.69
0.6954
0.6954
0.6923
78.16 0.52 78.69
0.44 79.05 0.34
0.5631
0.5581
0.5519
77.69
78.95 0.16
0.5684
0.5658
0.5525
GIN
77.71 0.19 78.11
0.10 79.65
0.23
0.5655
0.5593
0.5391
78.42 + 0.15 78.89
0.15 80.24 + 0.18
0.5584
0,5565
0,5281
V
77.50 0.18 77.54
0.16 78.67 0.17
0.5696
0.5688
0,5570
GraphSNN
/
77.52 : 0.16 77.61
0.18 78.90 + 0.15
0.5691
0.5671
0.5520
78.22 : 0.41 78.27
0.45 80.03 = 0.30
0.5602
0.5553
0.5304
78.41 0.21 78.76
0.17 80.10 = 0.14
0.5625
0.5590
0.5325
79.55 0.35
79.62
0.38 81.50
0.48
0.5539
0.5510
0.5133
68.99 1.38 69.08
1.81 68.09 1.81
0.6920
0.6921
0.6850
GCN
76.75 76.96
0.69
75.70
1.05
0.5755
0.5640
0.5838
4 78.78 1.01 79.03
0.61 78.69
0.84
0.5597
0.5504
0,5493
1.59 69.78 1.65 66.78
1.68
0.6904
0.6891
0.6887
GAT
4. 75.10 + 1.51 75.95
1.27 75.26 0.87
0.5866
0.5852
0.5978
4 78.87 + 0.80 79.20 0.56 79.19 + 0.78
0.5559
0.5448
0,5504
4 64.35 4.36 65.97 4.85 63.49 2.93
0.6923
0.6921
0.6918
GraphSage
75.06 1.77 76.12 1.31 75.95 1.05
0.5819
0.5748
0,5805
78.93 1: 0.99 79.02 = 0.64 79.23 = 0.49
0.5534
0.5481
0.5447
V
62.83 2.66 66.19 2.86 62.30 =:: 2.37
0.6951
0.6941
0.6876
SGC
4 70.94 + 1.33 73.51 +: 1.02 71.20 = 0.65
0.6231
0.6044
0.6109
78.85 0.70 78.53 0.83 78.61 0.63
0.5577
0.5556
0.5466
GSN
4. 78.90 1 0.63 79.28 0.70 80.70 = 0.37
0.5555
0.5543
0.5377
GraphaNN
79.16 0.67 79.35 0.82 80.74 + 0.44
0.5541
0.5530
0.5356
0.70
0.70
0.70
Training Loss
0.65
GIN
GIN
GIN
MLP MotifNorm
0.65
MLP MatifNNrmm GIN MotifNoom
Test Loss
0.65
MLP+ MatiiNorrm
GIN + MotifNoom
GIN MottfNomm
0.60
0.60
0.60
0.55
0.55
0.55
50
100
150
0
50
100
150
50
100
150
Epoch
Epoch
Epoch
0.8
0.8
0.8
Training ROC-AUC
Valid ROC-AUC AUC
Test ROC-AUC
0.7
0.7
0.7
MLP
MLP
MLP
GIN
GIN
GIN
0.6
MLP+ orm
0.6
MotiMNotooooooooo MotifNoor
0.6
MLP MotifNorm
MotifiNorm
GIN+ MotifNorm
0.5
0.5
0.5
50
100
150
50
100
150
0
50
100
150
Epoch
Epoch
Epoch
Figure 7: Learning curves of one-layer MLP, GIN, MLP + MotifNorm and GIN MotifNorm on IMDB-BINARY dataset (without learning rate warmup).
17

---

Under review as a conference paper at ICLR 2023
0.70
0.70
GIN+Matiinerm GiN-BBtchhoom GIN
Gotfffor
GlN+Matifnorm
Training Loss
Nir+BatchNorm GIN
GIN++BatchNomm GIN
0.65
Valid Loss
0.65
Test Loss
0.65
0.60
0.60
0.60
0.55
0.55
100
200
0
100
200
100
200
Epoch
Epoch
Epoch
Training ROC-AUC
Valid ROC-AUC AUC
Test ROC-AUC AUC
0.7
0.7
0.7
GIN-Motifnom
GIN Matifnorrm
GIN Motifnom
Batchhormm
0.6
GIN + BatchNorm
0.6
GIN+ BatchNorm
GIN
GIN
GIN
100
200
100
200
100
200
Epoch
Epoch
Epoch
Figure 8: Learning curves of one-layer GIN, GIN+BatchNorn and GIN+MotifNorm IMDB-
BINARY dataset with learning rate warmup (i.c., the curves of the reported scores in Table 2
18

---

Under review as a conference paper at ICLR 2023
B.3 MORE COMPARISONS ON THE OVER-SMOOTHING ISSUE
This section provide the illustration of GCN Kiipf & Welling 2017) and GraphSage (Hamilton al. 2017) with different six existent normalizations Cora dataset.
Given the node embedding X [11 J2, In. ]n E [R=xd where T; E RRd denotes the node embed- ding at layer The existing normalization methods for GNNs include PairNorm (Zhao & Akoglu 2020a), NodeNorm (Zhou et al. (021). McanNorm (Yang et al. 2020a), GroupNorm (Zhou et al.
2020) and BatchNorm (loffe Szegedy 2013) are depicted as follows:
PairNorm (Zhao & Akoglu 2020a).
==
T;
71
(10)
PairNorm(2,,s)
n
15s
i=
NodeNorm Zhou al. 2021).
(Dd std(
2i
(11)
MeanNorm Yang et al. 2020a).
MeanNorm(H(a)) = I(k) E[z(a]]
(12)
BatchNorm (loffe Szegedy 2015)
X - E(X)
BatchNorm(X)
V(X)+ + +
(13)
GroupNorm Zhou et al. 2020
GroupNorm X; = BatchNorr(Xgg,,
(14)
where X, = Softmax(X g) x.
MotifNorm please refer to Eq. (5) for details.
Here I() R denotes the i-th column X,, in PairNorm is hyperparameter controlling the av- erage pair-wise variance and we choose s = 1 our case. p in NodeNorm denotes the normalization order and paper uses p 2.
The t-SNE illustrations of different normalizations embedded in GCN and GraphSage are provided in Figure and 10 respectively. where the number of layers are 4, 16, 32. Figure 11 shows the over- smoothing phenomenon with the layers increasing using GraphSage, where the number of layers from 16 to 32 with the step size
19

---

Under review as a conference paper at ICLR 2023
1.0
1.0
1.0
0.5
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5-
-0.5
-1.0
-100
-0.5
0.0
0.5
1.0
-1.0
-10
-0.5
0.0
0.5
1.0
-1.0
110
-0.5
0.0
0.5
10
(a) MotifNorm, Layer=4
(b) MotifNorm, Layer=16
(c) MotifNorm, Layer=32
1.0
1.0
1.0
0.5
0.5-
0.0
0.0
0.0
-0.5
-0.5
1.0
1..
1.0
-0.5
0.0
0.5
1.0
11.0
-0.5
0.0
0.5
1.0
11.0
-0.5
0.0
0.5
1.0
(d) NodeNorm, Layer=4
(e) NodeNorm, Layer=16
(l) NodeNorm, Layer=32
1.0
1.0
0.5
0.5-
-0.5
-0.5
-1.0
-1.0
-1.0
1.0
-0.5
0.0
0.5
1.0
1.0
-055
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
10
(g) MeanNorm, Layer-4
(h) MeanNorm, Layer-16
(i) MeanNerm, Layer=32
-0.5
-1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-0.
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
(i) PairNorm, Laver=4
(k) PairNorm, Layer=16
()) PairNerm, Layer=32
-0.5
-0.5
-0.5
-1.0
1..0
-1.0
1.0
-0.5
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
1.0
(m) BatchNorm, Layer=4
(n) BatchNorm, Layer=16
(o) BatchNorm, Layer=32
1.0
0.0
0.0-
-0.5
-0.5
-0.5
-1.0
-1.0
-6.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
-0.5
0.5
(p) GroupNorm, Layer=4
(q) GroupNorm, Layer=16
(r) GroupNorm, Layer=32
Figure 9: The t-SNE visualization using GCN with different normalization methods on Cora dataset.
20

---

Under review as a conference paper at ICLR 2023
1.0
1.0
1.0
0.5
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5-
-0.5
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-100
-0.5
0.0
0.5
10
(a) MotifNorm, Layer=4
(b) MotifNorm, Layer=16
(c) MotifNorm, Layer=32
1.0
1.0
1.0
0.5
0.5-
0.0
0.0
0.0
-0.5
-0.5
1.00
1.0
1.0
-0.5
0.0
0.5
1.0
1100
-0.5
0.0
0.5
1.0
11.0
-0.5
0.0
0.5
1.0
(d) NodeNorm, Layer=4
(e) NodeNorm, Layer=16
(l) NodeNorm, Layer=32 32
1.0
1.0
0.5
0.5-
-0.5
-0.5
-1.0
-1.0
-1.0
1.0
-0.5
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
10
(g) MeanNorm, Layer=4
(h) MeanNorm, Layer-16
(i) MeanNerm, Layer=32
-0.5
-0.5
-1.01.
-0.5
0.0
0.5
1.0
-1.0
1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
005
0.0
0.5
1.0
(i) PairNorm, Laver=4
(k) PairNorm, Layer-16
()) PairNerm, Layer=32
-0.5
-0.5
-0.5
-1.0
-1.0
-1.0
1.0
0.5
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
1.0
1100
-0.5
0.0
0.5
100
(m) BatchNorm, Layer=4
(n) BatchNorm, Layer=16
(o) BatchNorm, Layer=32
0.5
0.5-
0.0
0.0-
-0.5
-0.5
-0.5
-1.0
1.0
0.5
0.0
0.5
10
-1.0
1.0
0.0
1.0
-1.0
-1.0
-0.5
0.5
(p) GroupNorm, Layer=4
(q) GroupNorm, Layer=16
(r) GroupNorm, Layer=32
Figure 10: The t-SNE visualization using GraphSage with different normalization methods on Cora dataset.
21

---

Under review as a conference paper at ICLR 2023
1.0
1.0
1.0
0.5
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5-
-0.5
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-100
-0.5
0.0
0.5
1.0
(a) Batcchor,, Layer=16
(b) BatchNorm, Layer=18
(c) BatchNorm, Layer=20
1.0
1.0
1.0
0.5
0.5-
0.0
0.0
0.0
-0.5
-0.5
-0.5
-1.0
1.0
-0.5
0.0
0.5
1.0
11.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
(d) BatchNorm, Layer=22
(e) BatchNorm, Layer=24
(1) BatchNorm, Layer=26
1.0
1.0
0.5
0.5-
-0.5
-1.0
-1.0
-1.0
1.0
-0.5
0.0
0.5
1.0
1.0
-0.5
0.0
0.5
1.0
11.0
-0.5
0.0
0.5
1.
(g) Batchhorm, Layer-28
(h) BatchNorm, Layer=30
(i) BatchNorm, Layer=32
1.0
-0.5
-1.%
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
GroupNorm, Laver=16
(k) GroupNorm, Layer=18
()) GroupNorm, Layer=20
-0.5
-0.5
-0.5
-1.0
1.0
-0.5
0.0
0.5
1.0
-1.0
1.0
-0.5
0.0
0.5
1.0
-1.0
1.0
-0.5
0.0
0.5
10
GroupNorm, Layer=22
(n) GroupNorm, L4yer=24
(o) GroupNorm, Layer=26
1.0
0.0
0.0-
-0.5
-0.5
-0.5
-1.0
-6.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-1.0
-0.5
0.5
(p) GroupNorm, Layer=28
(g) GroupNorm, Layer=30
(r) GroupNorm, Layer=32
Figure 11: The t-SNE visualization using GraphSage with BatchNorm and GroupNorm on Cora dataset.
22

---

Under review as a conference paper at ICLR 2023
B.4 MORE STATISTICS ON THE OTHER SIX DATASETS
Table Experimental results of different normalization methods on the graph prediction task. We use GCN, GAT and GIN as the basic backbones and set the number of layers as 4, 16 and 32. The best results on each dataset are highlighted with boldface.
ogbg-moltoxcast
ogbg-molhin
ZINC
Methods
4
16
32
4
16
32
4
16
32
NoNorm
61.13
59.34
56.08
76.01
71.90
60.59
0.643
0.690
0.748
PairNorm
60.69
59.45
55.07
74.06
72.13
62.25
0.573
0.569
0.597
NodeNorm
61.94
55.58
49.90
74.80
57.75
57.64
0.625
1.332
1.547
MeanNorm
63.21
60.42
54.76
74.42
72.39
60.59
0.602
0.637
0.695
GCN
GroupNorm
61.58
59.48
56.73
76.66
71.84
66.38
0.641
0.673
0.737
GraphNorm
60.78
53.75
53.36
75.59
65.55
66.49
0.592
0.655
1.547
BatchNorm
63.39
59.73
53.47
76.11
76.62
74.21
0.573
0.611
0.655
ExpreNorm
64.97
57.91
57.82
76.05
76.75
72.36
0.564
0.570
0.646
MotifNorm
66.92
65.19
63.40
77.29
77.71
75.99
0.489
0.524
0.523
NoNorm
62.61
50.84
50.12
76.71
57.38
50.64
0.714
1.541
1.547
GraphNorm
60.53
52.79
53.22
75.30
73.86
64.03
0.576
1.254
1.537
GAT
BatchNorm
63.31
53.39
53.24
76.07
76.87
73.74
0.585
0.624
0.643
ExpreNorm
65.56
57.65
57.60
76.99
72.24
72.56
0.555
0.562
1.451
MotifNorm
66.57
64.04
58.26
77.36
77.08
76.70
0.495
0.517
0.522
NoNorm
62.19
56.38
54.83
76.33
69.70
58.87
0.496
0.520
1.069
GraphNorm
62.44
54.95
55.72
76.55
66.00
67.01
0.462
1.203
1.446
GIN
BatchNorm
63.72
58.67
55.56
76.62
70.28
66.82
0.477
0.516
1.153
ExpreNorm 65,98
57.80
56.56
76.23
69.97
70.96
0.438
0.482
1.157
MotifNorm
66.65
63.01
57.46
77.38
73.03
72.89
0.410
0.458
0.902
Table 13: Experimental results of different normalization methods on the node prediction task and link prediction task. We GCN, and GraphSage the basic backbones and set the number of layers as 4, 16 and 32. The best results on each dataset are highlighted with boldface.
Pubmed
ogbn-proteins
ogbl-collab
Settings
16
32
16
32
4
16
32
NoNorm
76.16
54.67
45.58
69.16
63.24
63.15
35.38
22.11
15.24
PairNorm
74.25
56.24
55.13
69.28
63.15
63.00
31.26
23.22
14.69
NodeNorm
76.02
40.87
41.18
70.17
63.50
63.23
27.48
08.48
08.28
GCN
MeanNorm
76.05
73.40
65.34
69.14
63.05
62.40
33.28
22.56
16.16
GroupNorm
76.19
63.55
54.84
70.25
62.74
63.63
35.28
27.41
20.27
BatchNorm
75.62
48.88
43.28
69.96
67.36
63.86
47.57
26.14
21.68
MotifNorm
77.08
76.66
67.81
71.69
68.66
68.05
51.65
50.01
47.65
NoNorm
76.94
40.65
41.67
66.05
60.56
60.47
25.27
02.08
00.00
GraphSage
PairNorm
72.78
53.02
45,90
62.29
60.53
60.32
41.72
16.88
12.44
NodeNorm
77.22
40.64
40.64
64.48
62.63
61.89
19.74
02.57
02.62
MeanNorm
76.68
58.70
47.48
63.69
61.03
52.06
46.17
21.54
13.16
GroupNorm
76.83
40.42
43.49
68.09
61.58
60.60
45.43
23.98
15.43
BatchNorm
75,49
45.11
42.74
63.75
62.96
61.54
47.05
23.01
14.89
MotifNorm
77.48
76.54
73.68
67.81
67.02
66.07
52.31
48.94
48.39
23


Reviews:
[{"review_id": "osobaWPSoP", "reviewer": "Reviewer_iJ89", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "### Strength\n\n- Normalization methods are known to help the training of deep neural networks and it is an important direction to design normalization methods for GNNs.\n\n- It is reasonable to conduct comprehensive experiments covering node/link/graph-level tasks to examine the proposed MotifNorm for different GNN variants.\n\n### Weaknesses\nHere are several critical points that need to be essentially addressed.\n\n**[The motivation and novelty of the proposed MotifNorm]**\n\n- 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. \n\n- 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.\n\n**[The correctness of theoretical analyses]**\n\n- 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. \n\n- 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.\n\n**[The confidence of experimental results]**: \n\n- 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?].\n\n- 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.\n\n[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.\n\n[2] Wijesinghe, Asiri, and Qing Wang. \"A New Perspective on\" How Graph Neural Networks Go Beyond Weisfeiler-Lehman?\".\" International Conference on Learning Representations. 2022.\n\n[3] Dwivedi, Vijay Prakash, et al. \"Benchmarking graph neural networks.\" arXiv preprint arXiv:2003.00982 (2020).\n\n[4] Cai, Tianle, et al. \"Graphnorm: A principled approach to accelerating graph neural network training.\" International Conference on Machine Learning. PMLR, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jhw3xeZUax", "reviewer": "Reviewer_N94g", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\n\n", "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. ", "strength_and_weaknesses": "**Strengths**\n- Well done experimental study \n- Simple approach that seems to give some boosts to standard datasets and standard GNN architectures\n\n\n**Weaknesses**\n- The design of the normalization layer is not well motivated, the design seems adhoc\n- Theorem statements/proofs are of a very handwavey nature, not clear  and not rigorous enough\n\n**Suggestions, issues, questions, and comments**\n- The formal statement of Theorem 1 is unclear. What is meant by the sentence after \"while any\"?\n- Equation 2: This is a very specific GNN layer. Note that the layer does not use a non-linearity.\n- 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\n- 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?\n- 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 \n- Below Equation (5): It is not clear what the term \"segment averaging\" refers to\n- Equation (4): Do all normalization layers fit in the provided form? Can you provide a reference for this?\n\n- Theorem 2: The statement is not formal enough. For example, it is unclear what \"stabling and accelerating GNNs’ training\" means.\n- 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.\n- 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?\n- 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?\n\n**Minor points**\n- Page 2: Your edges are directed as they are from $V_G \\times V_G$\n- Section 2.1: \"Graph isomorphism problem\" might be the better term (\"isomorphism issue\")\n- Equation 1: Define the initial labeling, it might also be helpful to formally define the considered GNNs in the main paper\n- Definition 2: \"number of samples in a countable set\" -> \"cardinality\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZP-HenHH4DV", "reviewer": "Reviewer_WzdD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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 ", "summary_of_the_review": "The idea is novel. But the above problems should be addressed before publication. ", "strength_and_weaknesses": "Strengths\n\n1. MotifNorm, as a plug-in, makes GNNs more expressive (beyond 1-WL test) and less prone to the over-smoothing problem. \n2. The calibration and enhancement steps in MotifNorm is novel and efficient. \n3. Good experimental results. \n\nWeeknesses\n\n1. 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. \n2. 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. \n3. 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.\n4. 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?\n5. 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.\n\nReferences\n[1] Chen, Y., Tang, X., Qi, X., Li, C. G., & Xiao, R. (2022). Learning graph normalization for graph neural networks. Neurocomputing, 493, 613-625.\n[2] Liang, Langzhang, et al. \"ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization.\" arXiv preprint arXiv:2206.08181 (2022).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KBK8YrkERNZ", "reviewer": "Reviewer_BFQU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. ", "strength_and_weaknesses": "Strength: \nThe paper is well written. And the theoretical analysis is also quite clear, which I truly appreciated. \nThe proposed methods do boosted the performance and the ablation study also revealed the results.\n\nWeakness:\nBased 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).  \nI 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?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject