Learning Graph Normalization for Graph Neural Networks
Authors: Yihao Chen
Xin Tang
Xianbiao Qi
Chun-Guang Li
Rong Xiao
Venue:  (2021)
Keywords: Graph Neural Network
Normalization
Graph Normalization

Abstract: Graph Neural Networks (GNNs) have emerged as a useful paradigm to process graph-structured data. Usually, GNNs are stacked to multiple layers and the node representations in each layer are computed through propagating and aggre- gating the neighboring node features with respect to the graph. To effectively train a GNN with multiple layers, some normalization techniques are necessary. Though the existing normalization techniques have been shown to accelerate train- ing GNNs, the structure information on the graph is ignored yet. In this paper, we propose two graph-aware normalization methods to effectively train GNNs. Then, by taking into account that normalization methods for GNNs are highly task-relevant and it is hard to know in advance which normalization method is the best, we propose to learn attentive graph normalization by optimizing a weighted combination of multiple graph normalization methods at different scales. By op- timizing the combination weights, we can automatically select the best or the best combination of multiple normalization methods for a specific task. We con- duct extensive experiments on benchmark datasets for different tasks and confirm that the graph-aware normalization methods lead to promising results and that the learned weights suggest the more appropriate normalization methods for specific task

Under review as a conference paper at ICLR 2021
LEARNING GRAPH NORMALIZATION FOR GRAPH NEURAL NETWORKS
ABSTRACT
Graph Neural Networks (GNNs) have emerged as a useful paradigm to process graph-structured data. Usually, GNNs are stacked to multiple layers and the node representations in each layer are computed through propagating and aggre- gating the neighboring node features with respect to the graph. To effectively train GNN with multiple layers, some normalization techniques are necessary. Though the existing normalization techniques have been shown accelerate train- ing GNNs, the structure information on the graph is ignored yet. In this paper, we propose two graph-aware normalization methods to effectively train GNNs. Then, by taking into account that normalization methods for GNNs are highly task-relevant and is hard to know in advance which normalization method is the best, we propose to learn attentive graph normalization by optimizing weighted combination of multiple graph normalization methods at different scales. By op- timizing the combination weights, we can automatically select the best or the best combination of multiple normalization methods for a specific task. We con- duct extensive experiments on benchmark datasets for different tasks and confirm that the graph-aware normalization methods lead to promising results and that the learned weights suggest the more appropriate normalization methods for specific task.
INTRODUCTION
Graph Neural Networks (GNNs) have shown great popularity due to their efficiency learning on graphs for various application areas, such as natural language processing (Yao et al. 2019: Zhang
al. 2018), computer vision (Li et al. 2020 Cheng al.) 2020). point cloud (Shi Raj Rajkumar
2020 drug discovery (Lim et al. 2019), citation networks (Kipf & Welling 2016). and social
networks (Chen al. 2018). graph consists of nodes and edges, where nodes represent individual objects and edges represent relationships among those objects. In the GNN framework, the node or edge representations are alternately updated by propagating information along the edges of graph via non-linear transformation and aggregation functions (Wu et al.) 20200; Zhang al. 2018). GNN captures long-range node dependencies via stacking multiple message- message-passing layers, allowing the information to propagate over multiple-hops (Xu al. 2018).
In essence, GNN is a new kind of neural networks which exploits neural network operations over graph structure. Among the numerous kinds of GNNs (Bruna et al., 2014 Defferrard et al. 2016 Maron et al. 2019 Xu et al. 2019), message-passing GNNs (Scarselli et al. 2009 Li et al. 2016 Kipf & Welling [0166] Velickovic al. 2018 Bresson & Laurent 2017 have been the most widely used due to their ability to leverage the basic building blocks of deep learning such as batching, normalization and residual connections. To update the feature representation of node, many ap- proaches are designed. For example, Graph ConyNet (GCN) (Kipf & Welling (016) employs an av- eraging operation over the neighborhood node with the same weight value for each of its neighbors; GraphSage (Hamilton et al.) (017) samples a fixed-size neighborhood of each node and performs mean aggregator or LSTM-based aggregator over the neighbors; Graph Attention Network (GAT) VVelickovic et al.) 2018) incorporates an attention mechanism into the propagation step. which up- dates the feature representation of each code via a weighted sum of adjacent node representations; MoNet (Monti et al. 2017) designs Gaussian kernel with learnable parameters assign different weights to neighbors; GatedGCN (Bresson & Laurent 2017) explicitly introduces edge features at each layer and updates edge features by considering the feature representations of these two con-

---

Under review as a conference paper at ICLR 2021
(a) 1/1
(b)NCou))
(c) g
(d) 1
(e) E,
(
(y)
(b) E
Figure 1:
Illustration for normalization methods on graph. Node features are normalized at four
levels: (a) Node-wise; (b) Adjacency-wise; (c) Graph-wise; and (d) Batch-wise. Similarly the four normalization methods can be extended to normalize edge features as shown in (e), (f), (g), and (h). nected nodes of the edge and has achieved state-of-art results on several datasets (Dwivedi et al. 2020). More detailed overview about GNNs are provided in Appendix A
It is well known that one of the critical ingredients to effectively train deep neural networks is normalization technique, e.g., Batch Normalization (BN) (loffe & Szegedy 2015) widely used to accelerate the deep neural networks training. Other than BN, several normalization methods have been developed from different perspectives. e.g., Layer Normalization (LN) (Ba et al., 2016) and Group Normalization (Wu & He 2018) which operate along the channel dimension, Instance Normalization (Ulyanov et al.] 2016) which performs a BN-like normalization for each sample, Switchable Normalization (Luo et al. (019) which utilizes three distinct scopes-includio channel, layer, and minibatch- to compute the first order and second order statistics. Each normalization method has its advantages and is suitable for some particular tasks. For instance, BN has achieved perfect performance in computer vision whereas LN outperforms BN in natural language processing Vaswani al. 2017).
As an analogue, in Dwivedi et al. (2020), BN is utilized for each graph propagation layer during training GNNs. In Zhao & Akoglu (2020), a novel normalization layer, denoted PAIRNORM, introduced to mitigate the over-smoothing problem and prevent all node representations from ho- mogenization by differentiating the distances between different node pairs. Although these methods mentioned above have been demonstrated being useful in training GNNs, the local structure and global structure of the graph are ignored these existing methods. Moreover, in previous work, only one of the mentioned normalization methods is selected and it is used for all normalization layers. This may limit the potential performance improvement of the normalization method and is also hard to decide which normalization method is suitable to specific task.
Graph data contains rich structural information. By considering the structure information in the graph, in this paper, we propose two graph-aware normalization methods at different scales: a) adjaceney-wise normalization, and b) graph-wise normalization. Unlike BN and LN, the adjacency- wise normalization takes into account the local structure in the graph whereas the graph-wise nor- malization takes into account the global structure the graph. On other hand, while multiple nor- malization methods are available for training GNNs and it is still hard to know in advance which normalization method is the most suitable to a specific task. To tackle with this deficiency, we further propose to learn attentive graph normalization by optimizing a weighted combination of multiple normalization methods. By optimizing the combination weights, we can select the best or the best combination of multiple normalization methods for training GNNs a specific task automatically.
The contributions of the paper are highlighted as follows.
We propose two graph-aware normalization methods: adjacency-wise normalization and graph- wise normalization. To the best of our knowledge, it is for the first time that the graph-aware normalization method is proposed for training GNNs.
We present to learn attentive graph normalization by optimizing a weighted combination of differ- normalization methods. By learning the combination weights, automatically select the
2

---

Under review as a conference paper at ICLR 2021
best normalization method or the best combination of multiple normalization methods for training GNNs at a specific task.
We conduct extensive experiments on benchmark datasets for different tasks and confirm that the graph-aware normalization methods leads promising results and that the learned weights suggest the more appropriate normalization methods for specific task.
GRAPH-AWARD NORMALIZATION AT DIFFERENT SCALES
Suppose that we have N graphs G1, G2, GN in mini-batch. Let G. (Vk, Ex) be the k-th graph, where Vx the set of nodes and & is the set of edges. We use Uk,s to denote the i-th node of graph Gk and use 6k,i.j to denote the edge between nodes Uk,i and Uk.j of graph Gu. Moreover, we hug. E Rd to represent the feature of node u, and he, ; to represent the j-th element of h We use (vw,)) to represent the neighbors of node 2k (including node Uk itself).
For clarity, we formulate the normalization methods for training GNNs from different scales, as illustrated in Figure (a)-(d), including node-wise normalization, adjacency-wisg normalization, graph-wise normalization and batch-wise normalization.
Wode-wise Normalization. Node-wise normalization on graph, denoted as GN,, considers to nor- malize the feature vector h.,, of each node Uk,i and compute the first and the second statistics over the d entries of the feature vector hov, follows:
d Σ
(())) P2.s
(hhr. w,))),
(I)
MR
A.A
(n) (n)
where Mi. and g,i are the mean and the standard deviation along the feature dimension for node Ukii and 1 E Rd represents a d-dimension vector of all 1. Note that node-wise normalization is equivalent to applying LN to each node the graph to reduce the "covariate shift" problem
Adjacency-wise Normalization. Each node in graph has its neighbors. However, node-wise nor- malization performs normalization on each node individually and igmores the local structure in the graph. Here, propose take into account the adjacency structure in the graph and normalize the node features of the adjacent neighbors. We term as adjacency-wis noted GN,, For each node uk in graph Gs. we consider its adjacent nodes (Vv,,), illustrated in Figure (b). Specifically, the adjacency-wise normalization for node ib is defined as follows:
normalization on graph, de-
hor M
(0)
h (a)
(2)
k
d
MR
(a) [Wi.))) x d
E
Σ
h
(3)
('EN( jml
(a) = \ ((r,s)) x d k.6
Σ
Innd - (a))2
(4)
(vx,()))))
(a) where Pk, and o,s are the first order and second order statistics over the adjacent nodes
(a)
Graph-wise Normalization. Note that nodes belonging graph G2 naturally form group. In order to preserve the global structure of graph, we propose to normalize the node feature based on the first and the second order statistics computed over graph Gs. Specifically, we define graph-wise
1 'The node-wise normalization method in Equation can also be used to normalize the feature at each edge, as illustrated in Figure (c). Forr the edge 6s,4.s Figure (f), the adjacent edges (eex.) . can be considered in similar way.
3

---

Under review as a conference paper at ICLR 2021
normalization graph, denoted GN for node Vkli follows:
(g)
(how.:
M4 )Ak
(0)
(5)
(a)
P
(6)
(a) where 14 and As the first order and the second order statistics in graph 9s in which Ax is diagonal matrix with diagonal entry A is defined as
Σ 1E
(vee, - -4 92
(7)
FA
If the task has only single graph, then graph- wise normalization is similar to BN. However, unlike in BN, graph-wise normalization does not use a smoothing average updater
Batch-wise Normalization. To keep training stable, BN is of the most critical components.
For mini-batch, there are N graphs. We compute the mean and standard deviation across over the graphs of mini-batch, then each node feature h is normalized as follows:
(b) = (hre. (())AA Ub.4
(8)
N
1
h
T
k= t=1
where 7= E |9 matrix to keep the standard deviation of the note features over N graphs in which the diagonal entry A is defined
means the total number of the nodes in the N graphs and is diagonal
A
1 T
Σ
(h 12.
(10)
Note that batch-wise normalization graph, named GN, is effectively BN (loffe & Szegedy) 2015), which performs normalization over all nodes the N graphs in mini-batch.
The normalization methods applying to node features hes, also be extended to edge features hea,,, where hea.,, denotes the feature of edge Ci in graph Gk. as illustrated in Figure (e)-(h).
Remark. The properties of the four normalization methods summarized follows.
Node-wise normalization only considers to normalize the feature of each node individually but ignores the adjacency structure and the whole graph structures. It is equivalent to L.N (Ba al.) 2016) in operation.
Adjacency-wei normalization takes the adjacent nodes into account, whereas graph- wise nor- malization takes into account the features of all nodes in graph.
Batch-wise normalization is the same the standard batch normalization (loffe & Szegedy) 2015). If the task only involves single graph, then the batch-wise normalization is similar to the graph normalization except that momentum average used in batch-wise normalization is not used in the graph-wise normalization.
3 LEARNING ATTENTIVE GRAPH NORMALIZATION
Although we have defined several normalization methods for the graph-structured data, different tasks prefer to different normalization methods and for specific task, it is hard to decide which normalization method should be used. Moreover, one normalization approach is utilized in all nor- malization layers of GNN. This will sacrifice the performance of GNN.
To remedy these issues, we propose to learn attentive graph normalization for training GNNs by optimizing weighted combination of the normalization methods. Specifically, we combine the node feature h under different normalization methods as follows:
h (ax
(n) (x)
(a)
(a) (9) (()
ue. + +
+
(1I)
UK
For the edges & of graph G5 (Figure
(g)), we also define the normalization.
4

---

Under review as a conference paper at ICLR 2021
where a(()) a (a) a1 and (h)) R are trainable gate parameters with the same dimension as o Y E R and B R are the trainable scale and shift parameters, respectively.
Note that we attempt to use the learned a al)), ( and a (o)) indicate the contribution of the corresponding normalized feature to h Thus, we impose normalization constraints each di- mension of a!'), ((()), ae()) and (0 that 0j E [0, 1] where u E {n,, a, g. b} and j = =1, 1,,. ,d, (w) = where j 1,... .d. In this way, if normalization method is better for a specific task, the learned corresponding weights will be higher than others. Thus, we term the learned attentive graph normalization method in Equation [TT as Automatic Graph Normaliza- tion (AGN). In AGN, multiple normalization methods collaborate and compete with each others to improve the performance of GNNs.
and [n Oj
Different normalization methods are suitable for different tasks. In AGN, the attention weights ("),, (a) (9)) and (b) are optimized for a specific task and thus the best-performing normaliza- tion method will have a set of significant weights. Therefore AGN can serve as an effective strategy to select one of the best-peut rest-performing normalization method or the best combination of multiple nor-
malization methods for a specific task.
4 EXPERIMENTS
We evaluate GN GNa. GN,, GN,, and AGN under three GNN frameworks, including Graph Con- volution Network (GCN) Graph Attention Network (GAT) and GatedGCN. We also assess the performance of GNNs without normalization layer named as "No Norm". The benchmark datasets consist of three types of tasks including node classification, link prediction, and graph classifica- tion/regression. We use all seven datasets from Dwivedi et al. (2020), which are PATTERN, CLUS- TER, SROIE, TSP, COLLAB, MNIST, CIFARIO, and ZINC. In addition, we apply GatedGCN for key information extraction problem and evaluate the effect of different normalization methods on SROIE (Huang et al. 2019), which is used for extracting key information from receipt in ICDAR 2019 Challenge (task 3). The detailed statisties of the datasets are presented in Appendix C.T
The implementations of GCN, GAT and GatedGCN are from GNN benchmarking framwork The hyper-parameters and optimizers of the models and the details of the experimental settings are kept the same as in (Dwivedi et al.] 2020). We run experiments on CLUSTER and PATTERN datasets [, 16). respectively. For the other datasets, we fix the number
with GNNS of depth of layers of GCN layers to L = 4.
4.1 NODE CLASSIFICATION
For datasets CLUSTER and PATTREN, the average node-level accuracy which is weighted with respect to the class sizes is used to evaluate the performance of all models. For each model, we conduct 4 trials with different seeds {41, 95, 35, 12} to compute the average accuracy and the results are shown in Table
As can be read, graph-wise normalization (GN₂) outperforms batch-wise normalization (GN,) obvi- ously in most situations. For instance, when the depth of GNNs is 4, GatedGCN with GNg achieves 9% improvement over GN, CLUSTER. Batch-wise normalization computes the statisties over batch data and ignores the differences between different graphs. Different from GN GN₂ performs normalization only for each graph. Thus, GN, can learn the dedicated information of each graph and normalize the feature of each graph into reasonable range. As we known, the performance of the adjacency-wise normalization (GN₂) similar with that of the node-wise normalization (GN,). Compared with GN,, GN, consider the neighbors of each node and gets higher accuracies. AGN gets comparable results for different GNNs and the results of AGN are close to the best results in most cases due to its flexibility and adaptability. AGN can adaptively learn the optimal combination of the normalization methods which better adapt to the node classification task.
Moreover, we apply node classification to key information extraction on SROIE which consists of 626 receipts for training and 347 receipts for testing. Each image is annotated with text bounding
5

---

Under review as a conference paper at ICLR 2021
Ditaeei
CLUSTER
PATTERN
Netwock
OCN
GAT
GHRGGCN
GCN
GAI
GaREOOUN
Toin
Truin
Test
Train
Test
Tran
Train
Thia
Test
(Ace)
(Aae)
(Aee)
(Aee)
(A20)
(Aec)
(Aee)
No Noves
34.32119
$4,221,9
59.7201
39,0503
30022N
ST.426
61.92012
61.450.1
8133007
$2.5332
82.5334
GN.
57/21011
37012011
396200
390100
611100
003200
6432001
6401001
193320.3
74.730
B2612N
Layera
GN,
58.930.6
567:00.6
68.520.5
67.9055
63.5209
6300209
66.5=114
65.313.2
8200:044
81.1-04
$4.3500
84.5:00
IiN,
ON₂
85.1218
54.3215
59,360.4
586610
61.4302
803300.1
6483:02
63810.1
78.32122
7633:10
$4,500
84.51011
MGN
683110.3
0892202
08:2102
693330.3
10:320:1
1902204
763100
3533003
Nore
853310
12420.1
035223
306611.3
$23204
7342304
3551000
UR,
656270
7222304
340200
1382022
7.720
M14303
81.730.7
354500
Lager=16
ONN 667415
660-13
854+06
753402
8477406
141-003
148+17
707467
848-6.3
818-03
356400
853+00
GN;
8723304
725302
9.9103
734100
909305
74.2001
969101
763102
92:3:0.1
00.2002
$6.1002
853110
17N 676737
651225
1377303
790F16
220703
36.190
XGN
853300
873021
725106
15.300
7731003
N.2.00
373300
Table 1: Results on CLUSTER and PATTERN, Red: the best model, Violet: good models.
boxes (bbox) and the transcript of each text bbox. There are four entities to extract (i.e., Company, Date, Address and Total) from a receipt, as shown in Appendix C.2 For a receipt image, each text bounding box is label with five classes (i.e., Total, Date, Address, Company and Other). Then, the key information extraction is treated as node classification and we treat each text bounding box in receipt image node. Feature representation for each node will be supplied by Appendix (C.2 "Company" and "Address" usually consist of multiple text bounding boxes (nodes). The entity is recorded as "extracted successful" if and only if all nodes of each entity are classified correctly. In this experiment, we use GatedGCN, We compute the mean accuracy for each text field and the average accuracy for each receipt and show the results in Table 2
Text Field
No Norm
GN
GN,
GN,
GN.
AGN
Total
87.5
91.9
74.5
96.8
94.8
94.5
Date
96.5
98.0
95.9
98.8
97.4
97.4
Address
91.6
92.0
80.0
94.5
93.9
93.6
Company
92.2
93.3
87.8
94.5
93.0
94.8
Average
92.0
94.0
84.6
96.2
94.8
93.1
Table Performance (accuracy) comparison of different normalization approaches.
We can observe that GNg achieves the best performance among all compared normalization meth- ods. In the receipt, there are many nodes with only numeric texts. It is hard to differentiate the "Total" field from other nodes with numeric text. GNg performs well in this field and outperforms the second best by 2.0%. We believe that the graph-wise normalization can make the "Total" field stand out from the other bounding boxes with numeric text by aggregating the relevant anchor point information from its neighbors and removing the mean number information. Similarly, graph-wise normalization can promote extracting information for the other three key fields. It is interesting that the graph of each receipt is special with neighboring nodes that usually belong to different classes. Thus, the performance of adjacency-wise normalization is worse than node-wise normalization.
4.2 LINK PREDICTION
Link prediction is to predict whether there is link between two nodes i; and by in graph. Two node features of v; and vy. at both ends of edge esjy are concatenated to make a prediction. Experimental results are shown in Table 3 All the five normalization methods achieve similar performance on dataset TSP. Compared with others, the results of AGN are very stable. For each GNN, the result of AGN is comparable with the best result.
Dataset COLAB contains only graph with 235,868 nodes. Due to out-of-memory problem, we do report the results of GN, and AGN. Compared with GNNs with normalization layer, the results of GNNs without normalization layer (No Norm) seriously degenerates. GNg performs better than GNp- GatedGCN with GNg achieves the best result.
4.3 GRAPH CLASSIFICATION AND GRAPH REGRESSION
Graph classification is to assign one label to each graph. We conduce experiments on CIFAR10 and MNIST. Average class accuracy is reported in Table 4 ZINC a dataset for graph regression. The mean absolute error (MAE) between the predicted value and the ground truth is calculated for each
6

---

Under review as a conference paper at ICLR 2021
Network
GCN
GAT
GaadGGN
Daraset
Train (F1)
Test (FT))
Train (FI)
TSP
Test (FI)
Train (FI)
Test (FI)
No Norm
0.028:0.001
0.627:0.001
0.677=00.02
0.675=00.002
0.805=0.0005
0.804=000000
GN.
0.655:0.001
0.6344:0000
0.663:0.008
0.662=00.008
0.810=0.003
0.808:00.003
GN.
0.633:00.004
0.631+0.0044
0.678+00.003
0.676=00.003
0.80=000005
0.803=000004
GN₃
0.630:0.001
0.629:10.00]
0.669110.033
0.668:20001
0.890=0.001
0.806:20.001
GNo
06334-0.001
0.63240.001
0.673:00.044
0.601
0.701
0.789:00000
AGN
0.635100.001
0.633:100001
0.67310.001
0.671
0.804:00001
0.802:10.001
COLAB
Daraset
Train (Hits)
Test (Hiss
Train (Hits)
Test (Hits)
Train (Hits)
Test (Hits)
No Norm
73.02=77.03
38.32+-4.13
64,19+-4002 0,
32.69-4.48
38 18.55=8.13
22,60+33440
GN,
81.81:1..40
45.7511..14
95.9310.54
51.76-0.68
91.7243.40
51.55:11.44
GN₃
93.67=00.71
$2.27+1.22
97.11#0.65
51,36-1.15
97 27.5022.55
52.71:0.36
GN 91.88.10.04
51.1610.10
97.1110.43
51.54_00.0
95.31
51,87.0.41
Table 3: Link prediction results on the TSP and COLAB. Red: the best model, Violet: good models. group. Average MAE also is reported in Table We can see that GN, outperforms others in most cases. G does not work well on graph classification and regression. Furthermore, GNg affects the performance of AGN. In AGN, the normalized features of GN,, GN,, GNg. and GN, are integrated and automatically paid more attention to GN, due to its outstanding performance. Therefore, the performance of AGN is comparable with GN,-
Network
GAT
GatedGCN
Train (Ace)
Test (Aoc)
Train (Aee)
Test (Acc)
Train (Aoc)
Test (Ace)
Datavet
MNIST
No Norm
93.6220.22
10000000000
93.39-0.16
00.6
GN,
96.632091
50.5320.22
10000:0000
95.66-0.14
10000E0.00
97.21:0.12
GN,
95.65-0.75
89.6810.20
10000100000
95.41=0.22
10000010.00
96.87-00211
GN, 96.90=0.52
18.000000
100.00+00000
94.74-0.13
100.00+0.000
96.17:1.16
GN₂
97.16-1.06
90,51=0.22
99 99:99-0000
95.77-0119
100.00+0.000
97
AGN
97.34=0.66
90.4620.17
00000000000
95.75-0.2
100.00+0.000
07.4
Dataset
CIFARIO
No Norm
65.87=1688
54,5620533
88 80
62.13-0.31
85
03:44:0022
GN,
73.44 T.42
55.7740.31
876740881
0.00
901442205
67-86-065
GN,
71.48 1.27
34.310.322
10.00
62.72
0.26
50.510.32
67.21-0444 0044
GN,
21.352488
46.41:0029
89 2922011041
34,44
0.28
81.2916.37
32.913 28
GN,
69.34
2.47
15.14110.26
19.56.1411
64.34
15.7510.12
67.81 0.68
AGN
8..33=3.10
54.7320.68
94,48:1 558
62.98-0.47
98. 08.80.
66.8 06.1410.16
Train (MAE)
Test (MAE)
Train (MAE)
Tess (MAB)
Train (MAB)
Test (MAE)
Dataset
ZINC
No Norm
0:368:20:022
0.72440.005
0:270:00:029
0,400=00001
0,292:0.003
1.456==0.004
GN,
0.349=0.019
0.05
0.205=0.014
0.45620.001
0.260:0.021
0,428= 0005
GN,
0.351=0.013
0.291 +0,013
0.488=00001
0.274+0.023
0.457=0000 001
0.261-0.083
4.0429
0.228
2200000010
0.519+0.001
02166+0.019
GN
0.346- 0:019
1.465
10022
0.00010.003
0.200100033
0.451 10.007
AGN
0.357=0017
0.298+00018 0.006
0.403+
0.275+0.611
Table 4: Results on MNIST, CIFAR1O and ZINC. Red: the best model, Violet: good models.
4.4 ANALYSIS AND FURTIER INVESTIGATIONS
The above experimental results indicate that GNg outperforms batch normalization on most node classification tasks. For each single normalization method, it performs very well on some datasets, while its performance may decrease sharply on other datasets. Meanwhile, our proposed AGN which integrates several normalization methods into a unified optimization framework achieves competi- tive results compared with the best single normalization method on various datasets.
Behaviours of Learned Weights in AGN. To gain more insight into AGN, we conduct a set of experiments to analyze the effect of each normalization method on different datasets. Note that
AGN combines the results of several normalization methods and (e(")))unnaagg in Equation (1) indicate the importance of the corresponding normalization methods, respectively. We initialize the
(m) = 0.25 j, d and weights (*) Juen,agg,b in each layer with the equal values, i.e., aj
m {n, a. g, b). In the training phase, the value of each component of (a(()) JuEn,a.gbb changes between 0 and 1. On each dataset, we investigate the learned optimal weights on average at different layers of GatedGCN. Particularly, We collect the learned weights of each normalization method in each layer and calculate the averaged weights of each normalization method over all of the d entries of ("). We show the learned weights on average in Figure 2 As can be observed, the learned weights of each normalization method on average not only change for different dataset but also
7

---

Under review as a conference paper at ICLR 2021
CLUSTER (Are)
PATTERN (Ace]
SROIE
(SP(F))
MNIST (A0E)
CIPARIU (A0)
ZINCTMAEE
CN2
8083
97.25
67.86
0.4233
GN.
63,02
$4.53
GN
00.31
85.07
96.2
80.61
ON
96.8
97.47
67.83
04311
Table 5: Performance of different normalization methods on seven benchmark datasets. For each dataset, we give the performance of the best two normalization methods and new normalization method which combined the two best-performing normalization methods as Equation (TT).
vary for different layers. This implies that different layers prefer to different normalization method in order to yield good performance. We can also observe that the weights on GNg larger than others on node classification tasks and GN, is more important on others. Our proposed AGN has the ability automatically choose the suitable normalization method for specific task.
Evaluation on Selected Normalization Methods via AGN. To further evaluate the performance of the selected normalization methods, we select the two best-performing normalization methods, combine them into a new normalization method as in Equation (I), and conduct experiments on each dataset. The experimental results are listed Table We can read that the combined nor- malization method obtains the comparable results with the best normalization method. Therefore these results show that the learnt weights indicate whether the corresponding normalization method is suitable for the current task.
CLUSTER
PATTERN
SPOIE
0.6
0.28
0.30
Lambda Wegght
0.5
0.28
0.4
0.26
0.26
0.3
0.24
0.24
08g
0.1
0.22
2
4
2
6N
TSP
ZING
0.32
0.6
0.40
Lanbda Weight
0.30
0.35
0.28
0.26
0.25
0.24
0.2
0.20
0.22
0.1
0.15
Layer
Layer
Layer
Figure 2: Learnt weight distributions of normalization methods along with layers on different tasks.
Training Loss and Test Accuracy Curves vs. Iteration Steps. To show the effect of different normalization methods, we draw the curves of training loss and test result with respect to the iteration steps in Figures 4 and in Appendix C.3 We see that when proper normalization method is used, the training loss converges faster and better test accuracy can be obtained.
5 CONCLUSIONS
We formulated four normalization methods for training GNNs different scales: node-wise nor- malization, adjacency- wise normalization, graph-wise normalization, and batch-wise normalization. Particularly, the adjacency-wise normalization and graph- whse normalization are graph-aware nor- malization methods, which are designed with respect to the local and the global structure of the graph, respectively. Moreover, we proposed a novel optimization framework, called Automatic Graph Normalization, to learn attentive graph normalization by optimizing an attentively weighted combination of multiple graph normalization methods. We conducted extensive experiments on seven benchmark datasets different tasks and confirmed that the graph-aware normalization meth- ods and the automatically learned graph normalization method lead to promising results and that the learned optimal weights suggest more appropriate normalization methods for specific tasks.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. 2016.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. CoRR, abs/ 2017. URL
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. CoRR, abs/ 2014.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 2018.
Ke Cheng, Yifan Zhang, Xiangyu He, Weihan Chen, Jian Cheng, and Hanqing Lu. Skeleton-based action recognition with shift graph convolutional network. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 183-192, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Neofytos Dimitriou and Ognjen Arandjelovic. A new look ghost normalization. arXiv preprint arXiv:2007.08554, 2020.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2020.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIPS, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770- 778. 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Zheng Huang, Kai Chen, Jianhua He, Xiang Bai, Dimosthenis Karatzas, Shijian Lu, and CV Jawa- har. Icdar2019 competition scanned receipt ocr and information extraction. In 2079 Interna- tional Conference on Document Analysis and Recognition (ICDAR), pp. 1516-1520. IEEE, 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 448 456, Lille, France, 07-09 Jul 2015. PMLR. URL htt.:httpp/prceeeeeee mlr. wwtps//w7/eitee..../.
html
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. CoRR, 0bs//160.0000 002907, 2016. Uttp:t:: wwwp:/ioorrraaaaaao abs 609. .02.077977
Xia Li, Yibo Yang. Qijie Zhao, Tiancheng Shen, Zhouchen Lin, and Hong Liu. Spatial pyramid based graph reasoning for semantic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8950-8959, 2020.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. CoRR, abs/ 0tte//511.05540 1.0499, 2016.
Jaechang Lim, Seongok Ryu, Kyubyong Park, Yo Joong Choe, Jiyeon Ham, and Woo Youn Kim.
Predicting drug-target interaction using novel graph neural network with 3d structure-embedded graph representation. Journal of chemical information and modeling, 59(9):3981-3988 2019.
Ping Luo, Ruimao Zhang, Jiamin Ren, Zhanglin Peng, and Jingyu Li. Switchable normalization for learning-to tosee-ttoooooee normaallie deep representation. IEEE transactions on pattern analysis and machine intelligence, 2019.

---

Under review as a conference paper at ICLR 2021
Haggai Maron, Heli Ben-Hamu. Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurlPS, 2019.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolå, Jan Svoboda, and Michael M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model enns. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 5425-5434, 2017.
Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20( 2061))61-80, 2009.
Sheng Shen, Zhewei Yao, Amir Gholami, Michael W. Mahoney, and Kurt Keutzer. Powernorm: Rethinking batch normalization transformers, 2020.
Weijing Shi and Raj Rajkumar. Point-gnn: Graph neural network for 3d object detection in point cloud. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1711-1719, 2020.
Dmitry Ulyanov, Andrea Vedaldi, and Victor S. Lempitsky. Instance normalization: The missing ingredient for fast stylization. ArXiv, abs/1607.005 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.03762, 2017.
URL httt://///aax .rg. abs/ /ttbs/1755 1706. 03762
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ArXiv, abs/1710.11000/ 2018.
Yuxin Wu and Kaiming He. Group normalization. In ECCV, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint OrXiv:/806.033 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? ArXiv, abs//81000000 2019.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7370-7377, 2019.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: Algo- rithms, applications and open challenges. In International Conference on Computational Social Networks, pp. 79-91. Springer, 2018
Lingxiao Zhao and Leman Akoglu. 12s/1999.11223,, 2020.
Pairnorm: Tackling oversmoothing in gnns. ArXiv,
A GRAPH NEURAL NETWORKS
Velickovic al.) 2018) effective in learning graph representations. For node v. GNNs update its representation by utilizing itself and its adjacent neighbors. To capture high-order structure information of the graph, GNNs learn new feature rep- resentation of each node over multiple layers. In a layer of GNNs, each node u sends a "message" its feature representation, according to all collected information from the neighborhood ((v).. Mathematically, at the L-th layer, have
Graph neural networks (Kipf & Welling 2016
the nodes in Au); and then the feature representation of is updated
h (C(h
M(B ((o)))
(12)
10

---

Under review as a conference paper at ICLR 2021
where h. denote the feature vector at the f-th layer of node E N(v). i and & learnable functions, M is the aggregation function for nodes in (v), and C is utilized to combine the feature of node and its neighbors. Especially, the initial node representation h. 2. represents the original input feature vector of node u.
Graph ConvNets Kipf & Welling 2016) treats each neighbor node equally update the represen- tation of a node e as:
h f-1 ReLU(
E whh
(13)
dego wEN(v)
where W E R.dxd, deg. is the in-degree of node One graph convolutional layer only considers immediate neighbors. To use neighbors within & hops, in practice, multiple GCN layers are stacked. All neighbors contribute equally in the information passing of GCN. One key issue of the GCN an over-smoothing problem, which can be partially eased by residual shortcut across layers. Another effective approach to use spatial GNNs, such GAT (Velickovic al. 2018) and GatedGCN (Bresson & Laurent (0177).
GAT (Velickovic et al. 2018) learns to assign different weight to adjacent nodes by adopting atten- tion mechanism. In GAT, the feature representation of can be updated by:
h of Σ au, w.
(14)
(EN(()
where o measures the contribution of node u's feature to node v defined as follows: exp(g(a" [ [[WhhD)
(15)
EkEA(U) exp(g( xx(o((>"[W*> ([**)D)
where g()) LeaklyReLU activation function. a weight vector and the concatenation operation. Similar to Vaswani et al. (2017), to expand GAT's expressive capability and stabilize the learning process, multi-head attention employed in GAT. GAT has achieved an impressive improvement over GCN node classification tasks. However, the number of graph convolutional layers increases, nodes representations will converge to the same value. Unfortunately, the over- smoothing problem still exists.
To mitigate the over-smoothing problem, GatedGCN (Bresson & Laurent, 2017) integrates gated mechanism (Hochreiter & Schmidhuber 1997). batch normalization (loffe & Szegedy 2015), and residual connections (He et 20166) into the network design. Unlike GCNs, which treats all edges equally, GatedGCN uses an edge gated mechanism to give different weights to different nodes. Thus, for node v, the formulation for updating the feature representation is:
h f++
h + ReLU(BN(W' h
Σ
e OU (OUh"))
(16)
(EM(v)
where Wº, U E Raxd @ is the Hadamard product, and the edge gates et are defined as: a(ét.u)
é EVENTOO (et
(17)
L = c ReLU(BN(A +B'h &
where (-) is sigmoid function, c is small fixed constant, A Bº, OP Raxd, Different from traditional GNNs, GatedGCN explicitly considers edge feature 6,, at each layer.
B NORMALIZATION METHODS
B. BATCH NORMALIZATION
Batch normalization (BN) (loffe & Szegedy 2015) has become one of the critical components in training a deep neural network, which normalizes the features by using the first order and the second order statistics computed within mini-batch. BN can reduce the internal covariate shift problem and accelerate the training process. We briefly introduce the formulation of BN. Firstly, H = [h,, h2 hy.... hm E ddxm is denoted as the input a normalization layer, where m is the batch size and h; represents sample. Then, (m e Id and (m) e R denote the mean vector and the variance vector of the sample in H. respectively. BN normalizes each dimension of features
11

---

Under review as a conference paper at ICLR 2021
using (m)) and or (m)
h (h (m)))) ) (m)
+ B
/e (m)
(m)
1
(hij 14 (m)
hj:
(18)
m
j=1
μ == ap + (1 a a (m)
o² = ao² + (1 - (o
where // means element-wise division, y and are trainable scale and shift parameters, respectively. In Equation (18), f and a denote the running mean vector and the variance vector to approximate the mean vector and the variance vector of the dataset. During testing, they are used for normalization.
B.2 LAYER NORMALIZATION
Layer Normalization (LN) (Ba et al. 2016) is widely adopted in Natural Language Processing, spe- cially Transformer Vaswani et al.) 2017) incorporates LN as standard normalization scheme. BN computes mean and a variance over mini-batch and the stability of training is highly dependent on these two statistics. Shen et al. (2020) has showed that transformer with BN leads to poor perfor- mance because of the large fluctuations of batch statistics throughout training. Layer normalization computes the mean and variance along the feature dimension for each training case. Different from BN, for each sample h E Rd, LN computes mean n ()) and variance of (f across the feature dimen- sion. The normalization equations of LN are as follows:
h (L)
h 7 3
+ 3
(19)
d
1 = d hijs
L =
Σ (hi - 11g 1),
where hi E IRd is the normalized feature vector, 1 E I2 is a d dimension vector of 1's, y E Rd and B Rd are scale and shift parameters of dimension d.
Overall, there are many normalization approaches (Ulyanov et al. 2016 Wu & He 2018 Shen et al. 2020 Dimitriou & Arandjelovic 2020). [hhnn et al. (2020) has indicated that BN is suitable for computer vision tasks, while LN achieves better results NLP. For normalization approach, its performance may vary a lot in different tasks. Thus, it is very important to investigate the perfor- mance of normalization approaches in GNNs.
C DATASETS AND EXPERIMENTAL DETAILS
C.1 DATASET STATISTICS
Table C.I summarizes the statistics of the datasets used for our experiments.
C.2 SROIE
For receipt, each text bounding box (bbox) is viewed as a node of graph. The positions and the attributes of the bounding box, and the corresponding text are used as the node feature. To describe the relationships among all the text bounding boxes on a receipt, we consider the distance between two nodes v; and 0y- If the distance between two nodes less than a threshold 6, we connect ; and tj by an edge Ci,-- Since that the relative positions of two text bounding boxes are important for node classification, we encode the relative coordinates of v; and v to represent the edge Eij. In this way, such information extraction task from receipt can be treated as node classification task on a graph. Our goal is to label each node (i.e., text bounding box) with five different classes: "Company", "Date", "Address". "Total" and "Other". Since that GatedGCN explicitly exploits edge features and has achieved state-of-the-ard performance on various tasks, we use GatedGCN with GCN layers for this task.
12

---

Under review as a conference paper at ICLR 2021
Dataset
Graphs Nodes
Total Nodes
Edges
Total
Avg Edges
Task
Classes
Edges
PATTERN 14K
44-188
166,449
752-14,864
85,099,952
51.1
N.C.
2
CLUSTER
12K
41-190
140,643
488-10.820
51,620.680
36.7
N.C.
6
SROIE
971
18-153
52,183
70-2,031
420,903
8.1
N.C.
5
TSP
12K
50-499
3,309,140
1,250-
82,728,500
25
E.C.
2
12,475
COLLAB
235,868
235,868
2,358,104
2,358, 104
10
E.C.
2
MNIST
70K
40-75
4,939,668
320-600
39,517,344
8
G.C.
10
CIFARIO
60K
85-150
7,058,005
680-1,200
56,464,040
8
G.C.
10
ZINC
12K
9-37
277.864
16-84
597,970
2.1
G.R.
Table 6: Summary statistics of datasets used in our experiments. The 7th column (AvgEdges) rep- resents the average number of edges per node in graph. N.C., E.C., G.C., G.R. mean node classi- fication, edge classification, graph classification and graph regression independently.
3 01
MURAT JI DTABEL HOUSE 00766 K JLM ASTR U
Cameginry
POPULAR BOOK
Campany
Super Terminal 5dn
CO. (M) SDN BHD
(1150024-H)
CCB. KD. 3120-21
TAX INVOICE
Addren No. 6122100000 7/1188, Doss Tán Fazah -EapEr, Io la
Tanan Rudems
INV
TT Taan 1PP33
TEL: +009-225 2290
19884
VELOCLTE
0S1 000180299055
PCS
00-8O01 6281 /8000
PLTTE
Tab
13
12:38 Slip No. : 0540001037
1
59.30
UPP1N)
D16611 Art
Trane: 90243
SUGVA CONDESSOR (KG2)) 12V
5C1201//97)
Red Dat Fish
Asourt
Steared
Gi-nger luma (5)
Babbor Brer269ga
1.95
Boarcurd # Dao (5x
Dragon Dhiveo
15.00 00
00
CHATOE
Ino), of EST
Yotal Y.
-10, 05
2.
BULB SEOWA 1248 RX2 618.5
NUMBER MLASTIC
3.00.0
3.18
Pu (1-30
Count
8.00
6.36
aDT
Sunmar Asxuni (0N)
Tex 1843
Inclusive
Rioe
6.45
CAGH
Rics Sea
00
Savings
000
GGT Suntary
CHANGE
T301900
Sab Total
soount
PM 11.0 00
POPILAR CARD NEMBER
125
7.50
AND ENJOY SPECIAL D18COUMTS
Rourding Adjumeentt
Total Salos
RM 11:000 00
TRAMK YOU. PLEASE COME A0dIN.
wow pesular. con. my 3ez Enirese books unllee line www. www.llopo.llllloooo. Lnn. n03.
DKV NO:
1801 0UB893MA
TOTAL
110.0t
00
Figure 3: Sample images of the SROIE dataset. Four entities are highlighted in different colors. "Company", "Address", "Date", and "Total" are marked with Red, Blue, Yellow, and Purple indi- vidually. The "Company" and the "Address" entities usually consist of several text lines.
C.3 TRAINING AND TEST CURVES FOR NODE-WISED ADJACENCY-WISE, CRAPH-WISE BATCH- NORMAL.IZATION AND AUTO GRAPH NORMALIZATION.
D ACKNOWLEDGEMENT
We would like to thank Vijay el al. to release their benchmarking code for our research. We also want to thank the DGL team for their excellent toolbox.
13

---

Under review as a conference paper at ICLR 2021
Training Loss
Test Accuracy
1.8
Node wise
Adjccencywse
1.-
Graph-wise
65
Batch-w be
CLUSTER
AGN
60
55-
1.2
50
Node wise
Adjcienc-wse
1.0
Graph-wise
Batchswisse
0.8
AGN
Training Loss
Test Accuracy
0.70
Node-wise
85
0.65
Adjacency
Graph-wiz
80-
PATTERN
Batthh-we w be
AGN
0.35
0.45
65
Node
Adjecency-wise
60-
Graph-wise
Batch-wise
0.35
55
AGN
2000
4000
6000
8000
10000
12000
Training Loss
Test F1
0.8
Node-wise
Adjacencywse
0.25
Graph wise
0.7
Batch-wise
0.6
TSP
0.20
0.5
0.4
Node wise Adjacency-wise Graph wise Ratc/wwise
0.3
0.2
2000
4000
6000
8000
10000
12000
2000
4000
6000
8000
10000
12000
Step
Step
Figure 4: Training loss and test result of GatedGCN on CLUSTER, PATTERN and TSP vs. the number steps, with different normalization methods.
14

---

Under review as a conference paper at ICLR 2021
Training Loss
Test Accuracy
0.7
Node wise
20
Adjacensyewise
Groph
Ratch-wise
CIFAR10
Node wide-wiie
Adjccecy
0.5
Graph-eise
0.3
Batchvwise
ACN
30000
Training Loss
Accuracy
Node-wise
2.0
Adjaconcy wise
0.9
Graph-wise
MNIST
AGN
0.8
Adjacency-wise
Graph wise
0.5
AGN
2000
4000
8000
8000
10000
12000
2000
4000
6000
8000
10000
12000
Training Loss
Test MAE
1.4
Node-mise
Node-wise
Adjacency
0.80
Adjacencywwse
1.2
Groph-wise
0.75
Graph wise
Barch-wise
Batch-wise
0.70
ZINC
0.05
0.60
0.55
0.50
0.2
2000
4000
5000
8000
10000
12000
0
2000
4000
6000
8000
10000
12000
Step
Step
Figure 5: Training loss and test result of GatedGCN on CIFAR, MNIST and ZINC vs. the number of steps, with different normalization methods.
15


Reviews:
[{"review_id": "xdZmEKlllYc", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a unified view over different layer/batch normalization mechanisms for graph neural networks and formalizes an attention-driven approach to adaptively integrate the different forms of normalizations. An extensive empirical analysis is provided, spanning graph classification, link prediction and node classification tasks.\n\nOn the positive side, the paper is very well written and organised. Extremely clear while remaining concise and focused on the point. The idea of integrating several normalization mechanisms through an attention layer makes perfect sense. Also, I appreciate the attempt to provide an articulated empirical analysis spanning graphs and tasks of different nature.\n\nOn the negative side, the first issue is that of limited novelty. The original contributions of the paper seem to be: (i) graph-wise normalization and (ii) the attention-based integration mechanism. The former contribution seems to provide some form of empirical advantage (more on this later) but it is quite derivative and does not seem to provide any substantial novel insight on the quality of the learned representations nor on the representational power. The second contribution (AGN) has some additional novelty, but still marginal, as it is a straightforward application of standard attention. More importantly, the claim of AGN being an effective method to integrate contributions from different normalization mechanism is not supported by the empirical results.\n\nWhich brings me to the second key issue in the paper: the empirical results do not seem to strongly support the claims in the paper. First, when considering the predictive performance, one can see that the radically different normalization mechanisms have different performances (on the same dataset) only for   GCN and GAT. When considering GatedGCN (for the same number of layers), the differences between the attention mechanisms are minor. Hence it seems to suggest that the neural architecture is far more impacting than the choice of the attention mechanism. In this respect, the choice of GatedGCN to show the attention weight results in Figure 2 seems somehow driven to confirm the hypothesised “stability” of weight distributions. I would have liked to see the same analysis performed on the rather less stable GCN and GAT.\n\nAdditional issues as concerns the empirical analysis are:\n-\tOnly training/test results are reported: where is the validation set? If no validation set is used (I hope not), how are model selection and training convergence choices taken in a robust way? Figure 4 and 5 show that different methods are stopped at different epochs: so how is this choice taken without looking into the test?\n-\tGiven the number of configurations and datasets considered it is difficult to gain a high-level insight into which approach is truly performing best. The paper should include some sort of summarised statistics, like the average rank of each approach across the different tasks. This way one can also run some tests of statistical significance to tell which ranks are statistically different. \n-\tIt is unclear to me why GN_a fails with out of memory on COLLAB while other methods don’t. Where is the added memory complexity of GN_a that I am missing?\n\nI have one final concern as regards the definition of adjacency-wise normalization. Why is it using a feature-wise statistic (i.e. summing on the embedding features) instead of computing the actual first order (and second order) statistics w.r.t to the 1-hop neighbourhood of a node? While feature-wise statistics seems the only choice for node-wise normalization, I do not see it as a necessary case for the adjacency based one. There should be more discussion on this choice in the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "qFbntTcCme6", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "===== Summary =====\n\nThis paper proposes and evaluates different normalization techniques for graph neural networks. Also, the authors argue that the best normalization technique is task dependent, so they propose to use a weighted average of different normalizations that is learned during training, called AGN. In the paper they propose 4 different normalizations some of which are structure-dependent, and compare the performance of GCN, GAT and GatedGCN with and without these normalizations, and the learned combination of all of them.\n\n===== Pros =====\n* The paper explores normalization for Graph Neural Networks, which is a relevant topic.\n* In the experiments section the authors follow the benchmark proposed by Dwivedi et al. 2020, which uses standard tasks so that comparison with other methods is easier.\n\n===== Cons =====\n* The main concern about this paper is that the authors provide no justification about why the proposed normalizations are needed, or an explanation about why any of the proposed normalization techniques should perform better than the other techniques presented in this or other papers. Moreover, the authors only evaluate their proposed normalization methods without experimenting with other methods such as PairNorm or MsgNorm [2] which is also not cited.\n* Node-wise normalization is normalizing the feature vector of each node in each graph independently of all the other nodes in the same graph, therefore it is not equivalent to Layer Normalization as the authors say, because Layer Normalization would normalize all nodes in the same graph together.\n* Additionally, the Node-wise normalization has already been proposed as NodeNorm in [1]\n* The authors claim that adjacency-wise normalization and graph-wise normalization are both structure aware. While that is true for the former, since it normalizes nodes according to its neighbours, it isn’t true for the graph-wise normalization. The reason is that as explained by the authors in the beginning of section 2 each sample in the batch is a single graph, so normalizing across the graph is the same as normalizing across the whole sample, which doesn’t use the graph structure. It looks like this case is equivalent to Layer Normalization.\n\n==== Questions =====\n\n* I would like the authors to explain the motivation for their proposed normalization techniques beyond the empirical results. Why should they improve the vanilla GCN, GAT and GatedGCN models?\n* Specifically since it is a novel normalization technique presented in this paper, the authors should explain what is the motivation for the adjacency-wise normalization. Making an analogy to images, the proposed normalization would be the same as normalizing one unit in a convolutional layer by the value of its direct neighbours. Why is that useful for graphs?\n\n===== Minor comments =====\n\nSome sections of the paper are not very well written. For example the following sentence “On other hand, while multiple normalization methods are available for training GNNs and it is still hard to know in advance which normalization method is the most suitable to a specific task.” is not very clear.\n\nIt isn’t clear if AGN stands for “Automatic Graph Normalization” or “Attentive Graph Normalization” as both are used across the paper.\n\n===== Reasons for score =====\n\nBecause of the lack of motivation and explanation of the proposed normalization methods I vote for rejection. In my opinion the paper lacks justification and explanations of the proposed methods, and it isn’t clear why they are better than other normalization approaches.\n\n===== References =====\n\n[1] Zhou, K., Dong, Y., Lee, W. S., Hooi, B., Xu, H., & Feng, J. (2020). Effective training strategies for deep graph neural networks. arXiv preprint arXiv:2006.07107.\n[2] Li, G., Xiong, C., Thabet, A., & Ghanem, B. (2020). Deepergcn: All you need to train deeper gcns. arXiv preprint arXiv:2006.07739.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kV5uTen_LWT", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nSummary:\n\n\tThe authors propose two new graph-aware normalization techniques for training Graph Neural Networks, viz., (I) adjacency normalization (GN_a), and (ii) graph normalization (GN_g) and study them along with existing (iii) Node-wise (Layer Norm) and (iv) Batch normalization. Motivated by their experimental observation that different tasks work well with different normalization techniques, they propose an attention component that learns to weigh and combine the above four normalizations to best suit the end task. \n\n——\nPros:\n\n        - Paper is well written\n        - Results reported on multiple datasets and tasks\n\t- The proposed Graph level normalization seems useful for node classification tasks over multiple graphs.     \n——\nConcerns:\n\nMajor:\n\n\t- The paper lacks a clear model wise analysis of the usefulness of different normalization techniques\n\t- Though the paper mentions that the importance of normalization techniques varies with tasks, there seems to be no consistent model wise improvement under each task. A precise summary would help understand the pattern in the results.  \n\t- Need additional results on real-world datasets - Open Graph Benchmark, standard citation networks, etc.,.\n\t- Only the datasets in the Graph Classification/Regression task reported in Table 4 have all real-world datasets. Either of the existing Layer norm or Batch norm technique is the best or second-best normalization technique across all models on all three datasets. \n\t- It is not clear whether the difference with the proposed variants is statistically significant. Thus, a significance test on the same for all results would be helpful in understanding the usefulness of the proposed variants.\n\t- A GNN baseline with existing Layer norm and Batch norm combined is missing.\n\t- It not clear why the AGN model with GN_a didn't scale for the COLAB dataset \n\t- As the usefulness of GN_a and GN_g is not clear from the results, the need for the AGN model could not be appreciated. Albeit, the AGN model's importance is limited as there is no demanding need to learn the importance of a lot of components. Since AGN is not clearly the winner in most cases and as the results don't significantly improve with AGN, it might be better to test the different normalization techniques on a validation set and choose the one that works. Note that if the usefulness of GN_a and GN_g is clearly established, then the need for an attentive model is straightforward.\n\t\nDetailed concerns: \n\n\t(i) Node classification results are limited to datasets with multiple graphs. \n\tNo results on standard single graph benchmarks like Citation, Co-Purchase networks, Social networks, etc.. \n\tWould the proposed adjacency-based normalization do better the standard Layer norm and Batch norm?\n\t\n\t(ii) For node classification on multiple graphs, if the batch size is restricted to nodes from only one graph, how useful is adjacency normalization compared to layer norm and batch norm?\n\n\t(iii) Adjacency-Normalization (GN_a) performance is poor in the real dataset \n\t\t- From Table 2 on the SROIE dataset, the performance of GNN with GN_a drops ~8% points compared to the GNN with no Norm.\n\n\t(iv) Even on the artificial datasets, the performance gain with GN_a is not consistent \n\t\t- The GN_a + GCN model with 16 layers sees a drop of ~6% points \n\n\t(v) The baseline numbers are different than what is reported in Dwivedi et al. \n\t\t- 16 layers GCN+BN performance is lower than what is reported in Dwivedi et al. \n\t\t- While there is performance gain on \n\t", "extra_scores": {}, "extra_text": {}}, {"review_id": "Lgf5rviiXoA", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary and Strength: The authors propose two graph-wise normalization ways for graph neural network based applications. Combined with other two normalization strategies, a combination framework is proposed for weight learning of four normalizations. The experimental results  demonstrate the performance improvements of the proposed framework.\n\nConcerns:\n1. The novelty of graph-wise normalization is too thin. More insights are needed. For example, the authors might want to deliver why the normalization can bring the performance improvement, and the advantages and disadvantages of different normalization ways.\n2. The notations seem a little messy. It might be better if the authors use superscripts in Section 2.\n3. Combining with four different normalizations in Eq. (11), higher performance is expected due to more parameters. Without insights, the engineering work of this paper hardly inspires the readers. \n4. Some time complexities should be discussed.\n5. Significant tests are suggested to verify the gained improvements.\n6. How to interpret Figure 2?\n\nThis paper proposed different normalization ways for graph neural networks, unfortunately fails to answer the key questions that which is the best or default one. Instead, the authors combine them together with a weighted strategy, which lowers the technical contribution. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four knowledgeable referees have indicated reject mainly because of limited motivation [R1,R3,R4], limited insights on the proposed approach [R1,R2,R3,R4], and inconclusive results [R1,R2,R3,R4]. The claims of the paper could have been strengthened by e.g. discussing currently missing experimental details [R1], performing statistical significance tests [R2,R4], and including comparisons to baselines/previously introduced normalization strategies [R2,R3]. Unfortunately, there was no rebuttal. The paper is therefore rejected.
Decision: Reject