Dimensional Reweighting Graph Convolution Networks
Authors: Xu Zou
Qiuye Jia
Jianwei Zhang
Chang Zhou
Zijun Yao
Hongxia Yang
Jie Tang
Venue:  (2020)
Keywords: graph convolutional networks
representation learning
mean field theory
variance reduction
node classification

Abstract: In this paper, we propose a method named Dimensional reweighting Graph Convolutional Networks (DrGCNs), to tackle the problem of variance between dimensional information in the node representations of GCNs. We prove that DrGCNs can reduce the variance of the node representations by connecting our problem to the theory of the mean field. However, practically, we find that the degrees DrGCNs help vary severely on different datasets. We revisit the problem and develop a new measure K to quantify the effect. This measure guides when we should use dimensional reweighting in GCNs and how much it can help. Moreover, it offers insights to explain the improvement obtained by the proposed DrGCNs. The dimensional reweighting block is light-weighted and highly flexible to be built on most of the GCN variants. Carefully designed experiments, including several fixes on duplicates, information leaks, and wrong labels of the well-known node classification benchmark datasets, demonstrate the superior performances of DrGCNs over the existing state-of-the-art approaches. Significant improvements can also be observed on a large scale industrial dataset.

Under review as a conference paper at ICLR 2020
DIMENSIONAL REWEIGHTING GRAPH CONVOLU- TIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose a method named Dimensional reweighting Graph Convolutional Networks (DrGCNs), to tackle the problem of variance between dimensional information in the node representations of GCNs. We prove that DiGCNs have the effect of stabilizing the training process by connecting problem to the theory of the mean field. However, practically, we find that the degrees DrGCNs help vary severely different datasets. We revisit the prob- lem and develop new measure K to quantify the effect. This measure guides when we should use dimensional reweighting GCNs and how much can help. Moreover, it offers insights to explain the improvement obtained by the proposed DrGCNs. The dimensional reweighting block is weightee and highly flex- ible to be built on most of the GCN variants. Carefully designed experiments, including several fixes on duplicates, information leaks, and wrong labels of the well-known node classification benchmark datasets, demonstrate the superior per- formances of DrGCNs over the existing state-of-the-art approaches. Significant improvements can also be observed on large scale industrial dataset.
INTRODUCTION
Deep neural networks (DNNs) have been widely applied in various fields, including computer vi- sion (He et al. [016 Hu et al. 2018), natural language processing (Devlin et al. 2019), and speech recognition (Abdel Hamid et al. 2014), among many others. Graph neural networks (GNNs) is proposed for learning node presentations of networked data (Scarselli et al.) 2009), and later be ex- tended to graph convolutional network (GCN) that achieves better performance by capturing topo- logical information of linked graphs (Kipf & Welling (017). Since then, GCNs begin to attract board interests. Starting from GraphSAGE (Hamilton et al. 2017) defining the convolutional neu- ral network based graph learning framework sampling and aggregation, many follow-up efforts attempt to enhance the sampling or aggregation process via various techniques, such as attention mechanism (Veličković et al. 2018), mix-hop connection (Abu-Ei-Haija al., 2019) and adaptive sampling (Huang et al. 2018).
In this paper, study the node representations in GCNs from the perspective of covariance between dimensions. Suprisingly, applying dimensional reweighting process to the node representations may be very useful for the improvement of GCNs. As an instance, under our proposed reweighting scheme, the input covariance between dimensions can be reduced by 68% on the Reddit dataset, which is extremely useful since we also find that the number of misclassified cases reduced by 40%, compared with the previous SOTA method.
We propose Dimensional reweighting Graph Convolutional Networks (DrGCNs), in which the input of each layer of the GCN is reweighted by global node representation information. Our discovery is that the experimental performance of GCNs can be greatly improved under this simple reweighting scheme. On the other hand, with the help of mean field theory (Kadanoff 2009 Yang et al. 2019), this reweighting scheme is also proved to improve the stability of fully connected networks, provding insight to GCNs. To deepen the understanding which extent the proposed reweighting scheme can help GCNs, we develop a new measure to quantify its effectiveness under different contexts (GCN variants and datasets).
Experimental results verify our theoretical findings ideally that we can achieve predictable improve- ments public datasets adopted in the literature over the state-of-the-aa GCNs. While studying on

---

Under review as a conference paper at ICLR 2020
these well-known benchmarks, notice that two of them (Cora, Citeseer) suffer from duplicates and feature-labe information leaks. We fix these problems and offer refined datasets for fair com- parisons. To further validate the effectiivnnss, we deploy the proposed DrGCNs A A company's recommendation system and clearly demonstrate performance improvements via offline evaluations.
DRGCNS: DIMENSIONAL REWEIGHTING GRAPH CONVOLUTIONAL NETWORKS
2.1 PRELIMINARIES
Notations. We focus on undirected graphs 9 (V, E X),, where V= } represents the node set, = {(vi, 0;)} indicates the edge set, and X stands for the node features. For specific GCN layer, use Rd (ri" ,..., ra denote the input node representations and Rout (x1"t ..... ro to symbolize the output representations
? For the whole layer-stacked GCN structure, we use H denote the input node representation the first layer, and H' 0) to signify the output node representation of the 1t layer, which is also the output representation of the (1 - 1) layer. Let A be the adjacency matrix with 0zj when (vi, 0y) & and a.j otherwise.
Graph Convolutional Networks (GCNs), Given the input node set V, the adjacency matrix A, and the input representations R" GCN layer uses such information generate output representations R out
R ord a(aggregator A)),
where is the activation function. Although there exist non-linear aggregators like the LSTM aggregator (Hamilton et al.) 2017), in most GCN variants the aggregator is a linear function which can be viewed 2017 Huang et al. 2018), followed by a matrix multiplication on a refined adjacency matrix A, with a blas added. The procedure can be formulated as follows:
weighted sum of node representations among the neighborhood (Kipf & Welling
R out o (WR Ä b),
(2)
where W is the projection matrix and b denotes the bias vector. Development on GCNs mainly lies in different ways to generate A. GCN proposed some variants including simply taking À = AD-1, which is uniform average among neighbors with D being the diagonal matrix of the degrees, or weighted by degree of each node A D AD 3. including self-loops À I++ ADD à Other methods include attention (Veličković et al. 2018). or gated attention (Zhang et al. 2018 or even neural architecture search methods (Gao et al. 2019) to generate Á. To improve scalability, some GCN variants contain sampling procedure, which samples a subset of the neighborhood for aggregation (Chen al. 2018 Huang al. 2018). We set all unsampled edges to 0 in Ā in sampling-based GCNs, in this case A even has some randomness.
2.2 MODEL FORMULATION FOR DRGCNS
Given input node representations of a GCN layer Rd the proposed DrGCN tries to learn a dimen- sional reweighting vector (s..... s4), where s; an adaptive scalar for each dimension This reweighting vector then helps reweighting each dimension of the node representation r to r E where ree i' s. Here we use to denote component-wer multiplication, i.c..
T 8 syr A1 < d, Ve E V.
We define S as the diagonal matrix with diagonal entries corresponding to the components of s. Then DrGCN layer can be formulated as:
oot a (WSR" A
Inspired by SENet (Hu et al. 2018), formulate the learning of the shared dimensional reweighting vector s in two stages. First we generate a global representation r'n, whose value is the expectation of pin the whole graph. Then we feed p' into two-layer neural network structure generate
'To preserve amonymity we use A for the company and dataset name.
For the convenience of our analysis, use columns of R. H, X instead of rows to represent node repre- sentations.
2

---

Under review as a conference paper at ICLR 2020
Node Represeniction
Reweighied Represeniation
B
B
Reweighting Vector
C
C
Global Representation
Component-size MuNippicatiion
D
Beatleneck Reprerentation
Figure 1: Our proposed dimensional reweighting block (Dr Block) in DrGCNs.
of the same dimension size. Equation (5) denotes the procedure to generate given node weight fweld E V, Evey W, = 1} and node representations { j V}:
in = E E
V
wor
W
NEV
(5)
g 0g W
bg).
s s= . bb).
where output of the first layer: W. W., and b, are parameters to be learnt. Figure summarizes the dimensional reweighting block (Dr Block) in DrGCNs.
Combining With Existing GCN variants. The proposed Dr Block can be implemented as an independent functional process and easily combined with GCNs. As shown in equation (4). Dr Block only applies on R and does not involve in the calculation of A, W and b. Hence, the proposed Dr Block can easily be combined with existing sampling or aggregation methods without causing any contradictions. In 4 we will experimentally test the combination of our Dr Block with different types of X, DrGCNs can be viewed follows:
GCN methods. Suppose that the input features are
H' 0 WW'''''-AA A' b'), AI
(6)
where H X and H being the output representation for a k-layer DrGCN:
Complexity Dr Block. Consider GCN layer with input and output channels, nodes and edges in sampled batch, the complexity of GCN layer is +be) The proposed Dr block has a complexity (ag)) where g is the dimension g. In most cases, have g < b and n >> 1, so we could have ( o(abn + be), which indicates that Dr block introduces negligible extra computational cost.
THEORETICAL ANALYSES
In this section, we connect our study to mean field theory YYagg et al. 2019). We theoretically prove that the proposed Dr Block is capable of reducing the learning variance brought by perturbations the input, making the update more stable in the long run. To deepen the understanding, we further develop a measure quantify the stability gained by Dr block.
3.1
MEAN FIELD APPROXIMATION
(Lee et al. 2018 Yang et al. 2019) employ mean field approximation to analyze fully-connected networks. Following their ideas, provide thcoretical analyses for Dr Blocks fully-connected networks. GCNs different from fully-connected networks only in A, and degrade to fully- connected networks when Ā
idea is to provide insight GCNs from the analysis of fully-connected networks. We assume the average of the data O in the following discussions as transformation does not affect the covariance structure. For simplicity, we only consider neural networks with constant width and assume all layers use the same activation function ó. We follow the pre-activation recurrence relation & = WS' o 1 in (Yang et al. 2019) to facilitate ReLU activation,
the problem. When being a diagonal matrix with positive entries, and o(SH) = So(H) holds for all H. We can take the pre- are-activation step as the post-activation step of the previous layer and generalize our analysis sis to post-activation. So the recursive relation
H' w (S'H
3

---

Under review as a conference paper at ICLR 2020
We apply the mean field approximation to replace the input data by normal random variable with the same mean and variance and define an estimator Va to characterize the fluctuation of the random variable H)
Vol ( C HI((S)))
Define:
In this equation H ~ N(0 C C)-1), & is the ReLU activation, and C' represents the covariance matrix of H', i.c. C' (H'). Note that V6 does not completely coincide with variance. but can reflect the covariance structure. We call it covariance matrix for convenience. With mean field approximation, the covariance matrix can be updated by (note that b' independent with H):
C² & C (WW)"" + Cou(b').
We assume this dynamical system has a BSB (Block Symmetry Breaking Yang et al. fixed point (where C' = CC-1), i.e. a solution having the form C ===0 q-((1- c I 11 of the following equation with respect to C:
2019)
C V'' (W!) + Cou(b').
(10)
Next we make a reduction of V so that only the second slot matters. Take Sth as whole, it follows (o, (O,,S'C* S'''-Ss') distribution. Note that S is diagonal so S = ST. Thus equation ( can be written as:
-'='V
Cov(b').
(11)
The derivative of C' measures the fluctuation our updating algorithm when input perturbations exist, hence it characterizes the sensitivity of the algorithm to the data structures and its robustness. We will turn to show that Dr can relieve this sensitivity. We fix the point C' where we are taking derivative For most common types of activation functions, this recursive map has a fixed point, at which this linearization is most useful. Recall that such a derivative will be linear map from symmetric matrices to symmetric matrices.
Jo(C,) CI (C,). lo
Define:
(12)
dC Here C₁ could be intuitively understood the increment near C². We denote by Ha the space of symmetric matrices of size x d. Using these notations, we prove that:
Theorem 1. There exist diagonal matrices S', constants < 7' 1 such that, ( S
"[ JIS' le for any fixed general C. By general, we mean there exists a Haar measure on the collection of symmetric matrices Hg with respect to which the statement fails has measure zero
o
Detailed proofs and explanations are included in the Appendix GH For symmetric matrices, with X denoting eigenvalues of A, we have:
A
(13)
This norm measures the overall magnitude of cigenvalues of the operator. This result demonstrates that our method brings variance reduction and improves the stability of the updating algorithms. To summarize, for any input data, there exists a vector s that improves the stability of the updating algorithms.
3.2 STABILITY MEASURE FOR DRGCNS
In this section we turn to define a quantified measurement of the improvement of the stability of DrGCNs.
E. - Eis Cis8181
Define:
K A
(14)
- ag) Σ.
where Cyy is the (i element of the convariance matrix C. Theorem suggests that measures the instability of the update. The measure is a relative covariance measure that when S = I (without Dr), K 1. This quantity only involves entries of C, and it is homogeneous degree with respect to these entries and invariant under scalar multiplication
these entries. Being the covariance
*|| [| the Frobenius norm, i.c. for matrix A (Ai)), ||A|| Er, Alg-
4

---

We use the following definitions to Under review as a conference paper at ICLR 2020
matrix of H. C does not change under the mean case of H. Consequently, could proceed our analyses under the dimensional normalized assumption without loss of generality. We turn to consider the dimensional normalized version of V by replacing & with dø. which is with normalization:
dg : R. TR. do (H) oi VdGS'H
(15)
GH
where G - - i.c. Gr = x pI,, 1 μ= ト
Theorem 2. Near the fixed point C* of Vag the exponential growth rate of the deviation of C' from C is proportional to K.
Here C* is used to denote the BSB1 fixed points of Va, (I, C) Since S'H H has covariance matrix S'CS', our scaling effect is that Va, (S, C) = VB, (I, ('') simplify notations.
(16) Theorem 3.6 of Yang et al. 2019) tells us the derivative of Va, (I, C) (as linear map) has a very explicit eigenspace decompositron, we describe it in Theorem 3 A simple reflection suggests that our linear operators still satisfy the DOS condition and the ultrasymmerry condition needed in the proof this theorem, so this decomposition still holds.
Defin::
Cg a GCG K(S, C) & SCS.
dVa.
Theorem 3. Ja,- == aC at C* has eigenspaces and eigenvalues:
1. Vo [Co Cg =
=0, 0}. with eigenvalue 0.
VG RG, with eigenvalue Ag.
3. A (d - 1) dimensional eigenspace Vz. { D diagonal, tr == 0}. =0)-
4. A 4(d-3) -imensional eigenspace VM = (C: CG C, diag C 0} with eigenvalue Xas-
2
ÄL Am 1, whereas AG >
So an appropriately chosen S can reduce the proportion that lies Vg. We prove that the Frobenius norm of the component in VG is proportional to K in Appendix H Thus, it is natural to consider the orthogonal (in terms of Frobenius norm and corresponding inner product) eigendecomposition listed above):
(with subindices indicating the corresponding eigenspaces
K(S, C) Co + CG + C₁ + CM-
(17)
The effect of Dr is to reduce the RG component at each step to make the dynamic system more stable. Since the decomposition is orthogonal, this is equivalent reducing
G : S'Cs', G
(18)
recall that = = LII", ie. Ga = x - pI, # == + E xg. Since we take the normalization assumption, only the relative magnitude of sti matters, and we can put any homogencous restriction. In order include the case su we consider the restriction Σ tt d. By definition Cyy = E[h hence we have
1 (I d
"'
= =Tr(S'CS") CT(S'CS'ITT
(19)
Σ casii Σ cyssus
Finally come to the effectiveness measure of the proposed Dr Block.
K Σ, G.sh - Eis Cijsn E.
(20)
G2) Σ.
"I is the d-dimensional vector with all component
All results involve BSB1 fixed point (Yang et al. 2019) require permutation, diagonal and off-diagonal symmetry, and hold for dimensional normalization, too. 'G. S above are symmetrie, the transpose is only introduced for the sake of notational balance
5

---

Under review as a conference paper at ICLR 2020
Table I: Dataset statisties.
CoraR
CiteseerR
Pubmed
PPI
Reddit
A
Nodes/Users 2,680
3,191
19,717
56,944
232,965
35,246,808
Edges 5,148
4,172
44,324
818,716
11,606,919
129,83 129,834,116
Classes/Items
7
6
121
41
6,338,428
Features
302
768
500
50
602
27
Training Nodes
1,180
1,691
18,217
44,906
152,410
35,246,808
Validation Nodes
500
500
500
6,514
23,699
Test Nodes
1,000
1,000
1,000
5,524
55,334
35,246,808
The denominator is chosen display the ratio of variance reduction for the proposed Dr Block. Without Dr, 8//- = 1 for all i, and we have = 1. From our calculation on the inner product, it can be discovered that this quantity is proportional to the part in Ve in the orthogonal decomposition, this proves Theorem 2] Since this is the only part for Ja, with eigenvalue larger than 1, the exponential growth rate is proportional improvement Dr Blocks make to the stability of the learning process under perturbation.
this quantity. Therefore, this quantity measures the magnitude of
EXPERIMENTS
In this section, we evaluate the proposed DrGCNs on a variety datasets compared to several SOTA methods. Detailed descriptions of the experiments and datasets are included in Appendix C
4.1 EXPERIMENTAL SETTINGS
Datasets We present the performance of DrGCNs on several public benchmark node classifica- tion datasets, including Pubmed (Yang et al. 2016), Reddit, PPI (Hamilton et al., 2017). We also conduct experiments on a large-scale real-world commercial recommendation A dataset. Table summarizes statistics of the datasets.
There are also two widely adopted Cora and Citeseer datasets (Yang et al. 2016) for citation net- works. We investigate the originality of these datasets not only from the public data provided by (Yang et al. 2016) but also from much earlier versions (McCallum et al. 2000; Lu & Getoor 2003) and find problems in those datasets. 32(1.2%) samples Cora and 16.84.8% samples Citeseer are duplicated, while 1, 1.145(42.3%) samples in Cora and 2,055(61. 1.8%) samples in Citeseer have in- formation leak that includes their labels directly dimension of their features. To address such problems, we remove duplicated samples, modify their features using word and text embeddings reduce information leak, and construct two refined datasets, CoraR and CiteseerR. For details of these refined datasets and A dataset, please refer to Appendix E
Competitors We compare the results of DrGCN with GCN Kipf & Welling 2017 GAT (Veličković et al.] 2018), MixHop (Abu-El-Haija et al., 2019), GraphSAGE (Hamilton et al, 2017) FastGCN (Chen et al. 2018) and ASGCN (Huang et al. 2018) on citation networks including CoraR, CiteseerR and Pubmed. We also provide results on the original Cora and Citeseer dataset in Appendix C Our DrGCN also works for inductive datasets that we evaluate the Dr-GAT with several statc-of-thed
methods on the PPI dataset, including GraphSAGE (Hamilton et al. 2017). LGCN (Gao et al., 2018). and GeniePath (Liu et al. 2019). As for A dataset, we compare our method with the company's previous best GraphSAGE model, see Appendix
DrGCNs We combine Dr block with five most representative GCN methods and compare with them on public datasets. Two full GCN methods include vanilla GCN (Kipf & Welling 2017)
and variant that exploits an attention aggregator GAT (Veličković et al.] (018)). Sampling GCN methods contain FastGCN (Chen et al. 2018). Adaptive Sampling GCN (Huang et al. 2018) and
A company's 's heterogeneous GraphSAGE model on A dataset. Every GCN layer is replaced by DrGCN layer as in Equation (4) Further implementation details are covered in Appendix
4.2 RESULTS AND ANALYSES
Table 2 iillustrates the performance of DrGCNs four transductive datasets when combined with four different variations of GCN models. Our results are averaged among 20 runs with different random seeds. Our DrGCNs achieve superior performances all of the datasets and demonstrate

---

Under review as a conference paper at ICLR 2020
Table 2: Summary of classification accuracy public transductive datasets(%) (6)).
Category
Method
CoraR
CiteseerR
Pubmed
Reddit
GCN
85,9
74.9 0.7
88.0 0.3
Full GCNs
GAT
86.9 0.4
76.5 0.4
85.0 0.2
Mix-Hop
85.9 0.5
75.3+ 0.3
88.1 0.2
GraphSage
84.9 0.5
70.6 0.8
84.2 0.3
94.8 0.1
Sampling based
FastGCN
81.7 0.4
74.7 0.6
88.3 0.4
92.5 0.2
GCNs
ASGCN
84.3 0.7
75.1 0.9
89.8 0.3
96.4 0.3
Dr-GCN Dr-GAT
86.8 0.5
77.5 0.6
88.4 0.3
DrGCNs
87.3 0.2
77.0 0.3
84.7 0.4
Dr- Dr-FastGCN
81.6# 0.5
75.5 0.5
88.2 0.3
94.0=t 0.1
DrGCNs(sampling based)
Dr-ASGCN
84.3 0.5
75.4 0.4
90.3 0.4
97.9 0.1
Table 3: Summary of performance (micro FI) on inductive PPI dataset.
Method
GGrahhSAGE
LGCN
GeniePath
GAT
Dr-GAT
micro F1
61.2
77.2
97.9
97.3
98.8 0.1
relatively significant improvement on the Reddit dataset. Dr-ASGCN even reduces the error rates by more than 40% (3.6% 2.1%), compared with previous state-of-the-arr method ASGCN.
The performance improvements can be explained by our stability measure proposed in Equation we expect Dr block to have limited ability in refining the rep-
20). Theoretically, when K resentation, while when K << we expect the vector to strengthen the stability of the model by reducing the magnitude of the derivatives of the covariance matrix and improve the performance. To verify the theoretical analyses. we collect the average K-value of the learnt reweighting vectors for different layers in the Dr-ASGCN model, see Table [] The K-value in the second layer around 1 on all datasets. However, the K-value for the first layer is around 1 for citation datasets, but 0.32 on the Reddit dataset, which emphatically explains why the DR-ASGCN achieves such massive improvement on the Reddit dataset.
On the inductive PPI dataset (Table 3 Block increases the miero fl-score of GAT by 1.5% and outperforms all previous methods. Table suggests that the Dr method can also accomplish substantial improvements on the real-world, large-scale recommendation datasct. demonstrates improvement on industrial measure recall @ 50, which is the rate of users clicking the top 50 pre- dicted items among 6 million different items within the next day of the training set, from 591% (previous best model) 5.26% (Dr Block added).
4.3 BATCH-NORM AND LAYER-NORM.
We also compare DrGCNs with other feature refining methods, including Batch-Norm (Tfff & Szegedy 2015) and Layer-Norm (Lei Ba al.) 2016). These methods variance information every single dimension to refine representations, while DrGCN joins information on each dimension and learns a reweighting vector adaptively. We provide results of DrGCN and these methods on the Reddit dataset for ASGCN( Table ( Batch-Norm and Layer-Norm also improve the performance of the ASGCN model on the Reddit dataset. Combining Dr and Layer-norm yields an even better result for ASGCN on Reddit. More detailed results are in Appendix
5 RELATED WORKS
The idea of using neural networks to model graph-based data can be traced back to Graph Neural Network (Scarselli et al. 2009). which adopts neural network structure on graph structure learning. GCN (Kipf & Welling 2017) proposes a deep-learning-basse method to learn node representations on graph using gathered information from the neighborhood of node. GraphS (Hamilton et al. 2017) formulated a sample and aggregation framework of inductive node embedding. The idea of the sample and aggregation framework is incorporate information from the neighborhood to generate node embeddings. Despite being uniform when first being proposed, both sampling and ag- gregation can be weighted. These methods, including FastGCN (Chen al.) 2018), GAT (Veličković
7

---

Under review as a conference paper at ICLR 2020
Table 4: Performance (Recall@50) A online recommendation system. GraphSAGE refers to A company's 's best heterogeneous GraphSAGE model.
Method
GraphSAGE
DrGraphSAGE
Recall @ (0)
5.19
5,26
Table 5: Classification accuracy of ASGCN and Dr-ASGCN model, with average K value learnt for each layer.
Method
Cora
Citeseer
CoraE
CiteseerE
Pubmed
Reddit
ASGCN
87.23
78.95
84.30
75.12
89.82
96.37
Dr-ASGCN
87.07
79.06
84.34
75.44
90.34
97.95
Improvement Rate(%)
-0.16
0.11
0.04
0.32
0.52
1.58
Learnt K-value(Layee Laayer 1)
1.04
1.01
0.90
0.95
0.98
0.32
Learnt K-value(Layer
1.00
1.00
0.99
1.04
0.98
1.14
Table 6: Accuracy and average training time per epoch for plain, batchnorm, layernorm and DrAS- GCN methods on Reddit dataset.
Method
ASGCN
Batch-norm
Layer-norm
Dr
Dr+LN
Accuracy(%)
96.37 0.22
96.99 0.15
97.68 0.15
97.95 0.13
98.02:t 0.12
Time(s/epoch)
17.99
17.90
18.74
17.46
17.93
et al. 2018). LGCN (Gao et al. 2018), ASGCN (Huang et al. 2018), GaAN (Zhang et al. 2018 and Mix Mix HAbjaa et al., 2019), treat all nodes the graph unequally and try to figure out more important nodes and assign them higher weights in sampling and aggregation procedure.
Feature imbalance phenomena have long been aware of. (Blum & Langley 1997) Different dimen- sions of the hidden representation generated by neural networks may also share such imbalance behavior. The idea of refining hidden representations in neural networks can traced back Net- work in Network (Lin et al.] 2014), whom proposes fully-connected neural network to refine the convolution
pixel-wise hidden representation before each convolutional layer-known as the layer which is widely adopted in modern convolutional neural networks. Squeeze and Excitation Networks (Hu et al. 2018) proposes a dimensional reweighting method called Squeeze and Excita- tion block, which involves the techniques of global average pooling and encoder-decoder structure. works well in computer vision CNNs and wins the image classification task of Imagenet 2017. The success attracts our concern that such dimensional reweighting methods might also be useful in node representation learning graphs.
Another natural idea refine representations of neural networks is normalization. Batch normaliza- tion (Ioffe & Szegedy 2015) is a useful technique in neural networks to normalize and reduce the variance input representations. Layer normalization (Lei Ba al. 2016) is improved version of BatchNorm, for it also works on a single sample.
Many also try to give theoretical analyses such normalization techniques. (Kohler et al. 2018 explains the efficiency of batch normalization in terms of convergence rate. (Bjorck et al. 2018) shows that batch normalization enables larger learning rates. (Yang et al. 2019) demonstrates the gradient explosion behaviors of batch normalization on fully-connected networks via mean field theory (Kadanoff 22009). our approach, we adopt some these methods and apply them to the analysis of DrGCNs.
CONCLUSION
We propose Dimensional reweighting Graph Convolutional Networks (DrGCNs) and prove that DrGCNs can improve the stability of GCN models via mean field theory. Further explorations lead to the proposal of new measure evaluate the effectiveness of DrGCNs. We conduct experiments on various benchmark datasets and compare DrGCNs with several GCN variations. Experimental results not only prove the efficiency of DrGCNs, but also support the thcoretical analysis on measure K. DrGCNs usefulness is likewise verified large-scale industrial datasct *
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ossama Abdel-Hamid, Abdel-rahman Mohamed, Hui Jiang. Li Deng, Gerald Penn, and Dong Yu. Convolutional neural networks for speech recognition. IEEE/ACM Transactions on audio, speech, and language processing, ((110)1533-115 2014.
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor. Hrayr Harutyunyan. Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing. In ICML, 2019.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (Nov):2399-2434, 2006.
Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. In Advances in Neural Information Processing Systems, pp. 7694-7705. 2018.
Avrim L. Blum and Pat Langley. Selection of relevant features and examples in machine learning. Artificial intelligence, 97(1-2))245-27 1997.
Jie Chen, Tengfei Ma. and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 2854-3852, 2016.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 4171-4186 2019.
Ming Ding. Jie Tang, and Jie Zhang. Semi-supervised learning graphs with generative adversarial nets. Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 913-922. ACM, 2018.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424. ACM, 2018.
Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graphnas: Graph neural architecture search with reinforcement learning. arXiv preprint urXiv:/9044 009909991111 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Jie Hu, Li Shen, and Gang Sun. Squeere-and-excination networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems, pp. 4558-446 4567, 2018.
Sergey Toffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Leo P Kadanoff. More is the same; phase transitions and mean field theories. Journal of Statistical Physics, 137(5-6):777, 2009. 2009.

---

Under review as a conference paper at ICLR 2020
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In ICLR, 2017.
Jonas Kohler, Hadi Daneshmand, Aurelien Lucchi, Ming Zhou, Klaus Neymeyr, and Thomas Hof- mann. Towards theoretical understanding of batch normalization. stat, 1050:27, 2018.
Jachoon Lec, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. In ICLR, 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. NIPS 2016 Deep Learning Symposium, 2016.
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. In ICLR, 2014.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4424-4431, 2019.
Qing Lu and Lise Getoor. Link-based classification. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 496-503, 2003.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5115- 5124, 2017.
Federico Monti, Oleksandr Shehur, Aleksandar Bojchevski, Or Litany, Stephan Günnemann, and Michael M Bronstein. Dual-primal graph convolutional networks. arXiv preprint N0KYv/8806007770 2018.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-9)) -0,99393332330 2008
Aravind Subramanian, Pablo Tamayo. Vamsi K Mootha, Sayan Mukherjee, Benjamin L Ebert, Michael A Gillette, Amanda Paulovich, Scott Pomeroy. Todd R Golub, Eric S Lander, et al. Gene set enrichment analysis: knowledge- approach for interpreting genome-wide expres- sion profiles. Proceedings of the National Academy of Sciences, 102(43):15545-1555 2005.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 990-998. ACM, 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In Neural Networks: Tricks of the Trade, pp. 639-655. Springer, 2012.
Greg Yang, Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel Schoenholz. A mean field theory of batch normalization. In ICLR, 2019.
10

---

Under review as a conference paper at ICLR 2020
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volunn Volume 48, pp. 40-48. JMLR. org, 2016.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In UAI, 2018.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912-919, 2003.

---

Under review as a conference paper at ICLR 2020
Appendices
A PROBLEMS OF CORA AND CITESEER DATASET
We investigate the originality of the Cora and CiteSeer dataset. The two datasets are widely used for being light-weighted and easy handle. The most popular version is provided by Planetoid (Yang et al. 2016). The two datasets are both citation networks where each node represents a research paper, and each edge represents a citation relationship between two papers. Edges are directed but usually handled undirectedly by GCN methods. Each paper belongs to a sub-field in computer science and is marked as its label. Papers have features of bag-of ofrdor vectors that cach dimension represents whether the document of the paper contains particular word in the dictionary or not. Cora has 2,708 papers with a dictionary size of 1,433, while Citeseer has 3,327 papers with dictionary size of 3,703.
A.1 CORA
Cora originates in (McCallum et al. 2000 with extracted information(including titles, authors, abstracts, references, download links etc.) in plain-text form. Those download links are mostly unavailable now. Before they become unavailable, (Lu & Getoor, 2003 extracts subset of 2,708 papers and assigns labels and BOW feature vectors to the papers. The dictionary is chosen from words(after stemming, @ that occur 10 more times in all papers and result in a dictionary size of 1,433. Planetoid (Yang et al. 2016) reordered each node to form the benchmark Cora dataset (Yang al. 2016).
There exist a lot of duplicated papers (one paper appears as multiple identical papers in the dataset) in the original Cora of (MeCallum et al., 2000), and (Lu & Getoor 2003) inherits the problem of duplicated papers. In Cora, we find 32 duplicated papers among the 2,708 papers. Another problem the information leak. The generation process of the dictionary chooses words that occur more than 10 times, and does not exclude the label contexts of papers. Therefore, some papers may be clas- sified easily only by looking at their labels. For instance, 61.8% of papers labeled "reinforcement learning" contain exactly the word "reinforcement" "learning" in their title and abstract (after stem- ming). Altogether 1, 1,145(42.3%) of these papers contain their label as one or some of the dimensions of their features. 10
A.2 CITESEER
CiteSeer is a digital library maintained by PSU(Currently named as CiteSeerX IT b. which provides a based web API for each paper according their doc-ids. (Lu & Getoor 2003 extracts 3,327 nodes from the library to form a connected citation network in which 3,312 nodes are associated with a BOW vector of dictionary size 3,703. The rest 15 nodes' features are padded with zero vectors. is also reordered and adopted by Planetoid (Yang et al. 2016).
Although the original version of Citeseer only consists of links that unavailable now, back-up version of Citeseer contains the title and abstract information of 3,186 of the papers. We also find another 81 by author and year information using Google Scholar. Unfortunately, among the papers we collected from the Citeseer dataset, (41(4%)% of them are actually duplicated.
[33
Since the Citeseer dataset shares similar embedding generation method with Cora, there also exists the problem of information leak. For the data we collected, at least 2, 055 (61.8%) of the papers in Citeseer contain their labels in title or abstract, which are sure to become some of the dimensions of their feature representations.
data. soe. ucsc .ececceddu/ppee http:/uubbicc// hwt/ccra.tgc.p. "Stemming basically transforms word into its original form.
"I "e ieluencendee of the paper the rate becomes 86,1% see what GCN learns!
httpp///eiteseeex..srr....s
txt
12

---

Under review as a conference paper at ICLR 2020
Table 7: Label terms appearing in Cora's title and abstract.
Case Based
Probabilistic Methods
Rule Learning
Neural Networks
Reinforcement Learning
Genetic Algorithms
Theory
Total
Total Appeared Rate
298
351
426
180
818
217
418
2708
151
84
103
38
410
134
225
1145
50.7%
23.9%
24.2%
21.1%
50.1%
61.8%
53.8%
42.3%
Table 8: Label terms appearing in CiteSeer's title and abstract.
Human Computer Interface
Artificial Intelligence
Machine Learning
Information Retrieval
Database
Agents
Total
Total Appeared
264
590
668
701
596
508
3327
54
334
434
403
521
309
2055
Rate
20.5%
56.6%
65.0%
57.5%
87.4%
60.8%
61.8%
B THE REFINED CORAR AND CITESEERR DATASET
Due to the problems in Cora and Citeseer, we produce new datasets CoraR and CiteSeerR to address these issues. We remove duplicated nodes and generate indirect pre-trained word/text embeddings as node features to reduce the information leak.
B.1 CORAR
We double-check the articles belong to Cora (Lu & Getoor 2003) dataset in the original Cora MMc- Callum et al. 2000). Among the 2,708 papers, 474 of them have a wrong title that can hardly be found on any academic search engines such as google scholar or aminer (Tang et al.) 2008). We manually searched for these papers based on other information like author, abstract, references and feature vectors in Cora. Finally, we figure out that 32 of the total 2,708 papers are duplicated papers that actually belong to 13 identical ones. 9 papers are absolutely missing and not able to trace. We recover the actual title of the rest 2,680 papers, and their titles generate their features. We apply averaged GLOVE-300 (Pennington et al. 2014) word vector for their titles(with stop words removed) and we add two dimensions expressing the length of the title, and the length of the title with stop words removed. This leads to a 302 dimension feature representation for each node in CoraR. The average and word embedding process can better reduce the effect of label information leak than using simple BOW vectors. As in (Hamilton et al. 2017 Chen et al. 2018), we split the 2,680 nodes into training set of 1,180 nodes, validation of 500 nodes and a test set of 1 1,000 nodes.
B.2 CITESEERR
We use Cornelia's ' back-up extractions of CiteSeer and manually find some other documents using author and year information from academic search engines. For the rest we only have a numerical ID and invalid download link, so we are not able to trace them. We check the titles, abstracts and feature vectors and find 161 papers are actually 80 identical papers. We combine duplicated papers together and also remove 55 papers that are not able to trace. Our refined CiteSeerR has 3,191 nodes and 4,172 edges. We average over the last hidden state of BERT (Devlin et al.) 2019) for each sentence from the title and abstract and produce (68-dimensional feature for each paper. For pairs of duplicated papers with distinct labels, we manually assign a label for it. As in (Hamilton et al. 2017 Chen et al. 2018), we split the 3,191 nodes into training set of 1,691 nodes, validation set of 500 nodes and a test set of 1,000 nodes.
Both CoraR and CiteseerR included in the link of code.
13

---

Under review as a conference paper at ICLR 2020
C IMPLEMENTATION DETAILS
C.1 DR BLOCKK CONFIGURATION
For the dimensional reweighting part of each layer, the dimension of the encoder is set to the closest integer of the square root of the dimension of the input node representation r². The pooling weight Wy is set to uniform weight
= MV where [V] is the number of nodes in the graph for
full GCNs, and the batch size for batch-wise sampling GCNs. We use ELU activation for og and sigmoid activation for a.. We do not apply dropout, but apply weight regularization with the same coefficient as the original GCNs in the Dr Blocks of DrGCNs.
We keep all other settings, including learning rate, early stop criteria, loss function, hidden rep- resentation dimension, batch size, weight decay, and regularization loss the same the original models.
C.2 EVALUATION DETAILS
All of our methods and compared baseline methods are run 20 times, and we report the average accuracy and variation for methods that run. We evaluate their performance mainly based their released code and paper. For methods without codes, we use their reported performance if they share the same evaluation settings as ours.
C.3 METHOD DETAILS
We describe our method implementation details here.
GCN Kiipf & Welling, 2017) We use the GCN code provided AS-GCN and use 2-layer GCN model with 64 hidden units in layer 1. We run it 20 times and report the average and variance. For each running time, we use the model that performs best within 800 training epochs on the validation set for testing.
GAT Veličković al. 2018)
We use the GAT code provided by the authors We use the dataset-specific structures described in (Veličković et al., 2018)) and early stopping strategy mentioned the code repo. The original paper uses a high dropout rate of 0.6 on semi-supervised citation datasets test setting. We find that for CoraR, CiteseerR and the fully-supervised training set setting Pubmed, such a high dropout may have chance to lead the original GAT model not to converge, so we adjusted the dropout rate 0.35(which gives the best performance among all dropout rates from to 0.6) for both the original and our Dr-GAT. On PPI we simply follow their instructions and use their suggested structure and hyperparameters.
15
GAT forms 2 layer structure for citation datasets. For Cora and Citeseer, GAT has 8 hidden units in every attention head in the first layer, and attention heads in the first layer and in the second layer, which has the number of hidden units equal to node classes. We adopt the structure for CoraR and CiteseerR. We also discover that for the fully-supervised training set setting on Pubmed, the structure for Pubmed in GAT paper(which has 8 heads in the second layer) does not perform as good as the GAT structure for Cora and Citeseer (this setting achieves 82.5 + 0.3% under the best dropout rate),
also adopt the Cora/Citeseer structure Pubmed.
For PPI, GAT has three layer structure, with 256 hidden units every attention head in the first two layers. It has 4 attention heads in the first layer and 4 in the second layer, and 6 attention heads in the third layer, each third layer attention head has number of hidden units equal to node classes. It also sets dropout equals to 0 and uses residual connection (He et al. 2016).
https:://iithub.com
14

---

Under review as a conference paper at ICLR 2020
FastGCN (Chen al. 2018) We the code provided by the authors. We the weighted sampling method described in the paper, and use a neighborhood size of 400 for CoraR, CiteseerR, Pubmed and 512 for Reddit. We run 20 times and generate average performance and variations.
16
ASGCN (Huang et al. 2018) We the code provided by the authors We a neighborhood size of 128 for CoraR, CiteseerR, 256 for Pubmed and 512 for Reddit as the paper suggested. (Huang al. 2018) Their original code seems to have a bug causing unnecessary test information leaking during the validation process. We modified their code to avoid such problems. We choose the best model on validation set within 800 epochs for citation datasets and 200 epochs for Reddit and use that for testing.
et al., 2019) We use the code provided by the authors We the best author provided script for Pubmed. Unfortunately the parameters the authors provided for Cora and Citeseer does not work well for CoraR and CiteseerR, we fix the network structure and tune the hyperparameter set for CoraR and CiteseerR ourselves.
Mix-Hop
18
GraphSAGE (Hamilton et al. 2017 We use the code provided by the authors 19 on CoraR, Cite- seerR and Pubmed. For Reddit this code does not work so we use another code also provided by the
author 20
Other Methods Many of them do not have their codes released, so we use their reported perfor- mance in their papers, or reported performance their method by other papers, if we share a similar evaluation setting.
Specifically, the performances of all baseline methods in appendix table 11 are from their original papers (some non-GCN baseline results are from (Kipf & Welling 2017)). The performance of GraphSAGE, GeniePath, LGCN, GAT on the PPI dataset are from their original papers.
D DATASETS
The details of our datasets are listed in this section. We generally use 6 datasets, including 3 citation datasets, I Reddit dataset, 1 inductive PPI dataset, and sizeable online recommendation A dataset.
Citation Networks We evaluate the performance of our DR models on the three citation network datasets, CoraR, CiteseerR, and Pubmed (Sen et al. 20088 Yang et al. (016)) There are two types of experimental settings, the semi-supervised setting for full GCNs (Kipf & Welling 2017 Veličkovid et al., 2018). which uses only little fraction of the node labels on the graph and all link information for training. Another fully-supervised setting (Chen et al.) 2018 Huang et al.) 2018) uses node labels of the full graph except the validation and test set for training. The dataset statisties of original Cora, Citeseer, and Pubmed dataset under these two settings are shown in table 9 We double-check the adjacency matrices, remove self-loops, and correct the number of edges in these datasets, which is mistaken in various papers, including GCN (Kipf & Welling 2017). Besides evaluation on CoraR, CiteseerR, and Pubmed in the main article, we provide the result of the fully-supervised setting for Cora and Citeseer in table TO We also provide our results on the comi-supervised setting on Cora, Citeseer, and Pubmed dataset in table
PPI The protein-protein interaction dataset collected by SNAP (Hamilton et al.] 2017) from the Molecular Signatures Database (Subramanian al. 2005). which is an inductive multi-label node classification task. The training set contains 20 protein graphs, while the validation and test set contains two graphs each. We evaluate the performance of different models by micro F1-score.
Reddit The Reddit dataset is collected by SNAP (Hamilton al. 2017) from Reddit posts. It is node classification dataset for classifying different communities of each user by his/her posts.
15

---

Under review as a conference paper at ICLR 2020
Table 9: Supplement of Dataset statistics for citation datasets.
Cora
Citeseer
Pubmed
Nodes
2,708
3,327
19,717
Edges
5,278
4,552
44,324
Classes
6
Features
1,433
3,703
500
Training Nodes(Semi)
140
120
Training Nodes(Full)
1,208
1,827
18,217
Validation Nodes
500
500
500
Test Nodes
1,000
1,000
1,000
Table 10: Summary of classification accuracy fully supervised Cora and Citeseer(%)
Category
Method
Cora
Citeseer
GCN
Kipf & Welling
(017
86.4
77.4 0.2
Full GCNs
GAT
Velíčković et al.
(2018)
87.2 0.4
77.8 0.2
Sampling-hased
FastGCN Chen et al. (018
83.9+ 0.4
78.6 0.4
GCNs
ASGCN
Huang et al.
2018
87.2+ 0.2
79.0 0.4
Dr-GCN Dr-GAT
86.81: 0.2 87.4++022
77.5 0.3
Dr GCNs(ours)
77.8+ 0.2
Dr Sampling-based
Dr-FastGCN Dr-ASGCN
84.0 0.4 87.1 0.2
78.3+ 0.3
GCNs(ours)
79.1 0.4
E A DATASET: DATASET, BASELINE AND EVALUATION
As for the industrial A dataset use. It is item recommendation dataset, with the training set has about 35 million users and 6.3 million items with 120 million edges. Although the target node-classification like(to find the most likely items that each user may click), instead of simply taking each item as a class, A uses graph embedding model to generate embedding for both users and items. There are 27 user attributes and 33 item attributes. For every user, use K nearest neighbor (KNN) with Euclidean distance to calculate the top-N items that the user is most likely click, and the customer will see these recommended items in A company's APP. We use the recall @ N to evaluate the model:
MM [ud I.
recall@N mean
(21)
M,, represents the top-N items recommended by the model and L, indicates the items clicked by the customer. The baseline model is the A online heterogeneous GraphSAGE, and we add Dr block in compare Recall@N with the online model.
Recall @0 is the most commonly used metric in A company. Experimental results show that we reach 5. 5.264% on Recall @ 50, improving from the original best model's 5.188% It is quite good result, considering random guess will only give less than 0.001% (50/6,300,000).
F BATCH-NORM AND LAYER-NORM GCNS ON CITATION NETWORKS
In Table 12 we also provide the batch-norm norm and layer-norm GCN results on publication datasets. The results are averaged among 20 runs.
G PROOF OF THEOREM
We also provide proof for theorem in the main article.
16

---

Under review as a conference paper at ICLR 2020
Table 11: Summary of classification accuracy (%) of semi-superviisd labels citation datasets.
Category
Method
Cora
Citeseer
Pubmed
Non- Non-Graph Convolution
MLP
55.1
46.5
71.4
ManiReg (Belkin et al.
2006
59.5
60.1
70.7
SemiEmb (Weston et al 2012
59.0
59.6
71.1
LP (Zhu al. 2003
68.0
45.3
63.0
DeepWalk (Perozzi et al. 2014)
67.2
43.2
65.3
ICA (Lu & Getoor 20033
75.1
69.1
73.9
Planetord Yang et al. (0166)
75.7
64.7
77.2
GraphSGAN (Ding al.
83.0
73.1
Chebyshev (Defferrard et al. 2016
81.2
69.8
74.4
Graph Convolution
GCN (Kipf & Welling 2017
81.5
70.3
79.0
MoNet (Monti al. 2017)
81.7
78.8
DPFCNN (Monti et a..
2018
83.3
72.6
LGCN (Gao et al. 2018
83.3
73.0
79.5
GAT (Velickovic et al. 2018
83.0
72.5
79.0
Mix-Hop (Abu-El- Elajaa et al. 2019
81.9
71.4
80.8
DR-GCN DR-GAT
81.6 0.1
79.2+-0.4 71.0++0.6
DR-GCNs(ours)
83.6 + 0.5
72.8+ 0.8
79.1+0.3
Table 12: GCN, BatchNorm, LayerNorm and DrGCN methods accuracy(%) on citation datasets.
Method
CoraR
CiteseerR
Pubmed
GCN
85.9 0.5
74.9 0.7
88.0 0.3
Batch-norm
86.2 0.5
77.510.4
88.6 + 0.3
Layer-norm
85.6 0.7
0.9
89.9 0.4
Dr-GCN
86.8 0.5
0.6
88.4 0.3
Now we turn to prove theorem [ semidirect (DOS) if and only if:
We say a linear operator T Hd - Ha is dlagonal-off-diagome
VC E Ha,
T(C); voa + Uogs + wazj.
Here u, v, w are constants, and we will call the set of operators with these parameters DOS (u, v, w). By the definition of Va, the (i.j) component its output will only involve the th and th components of the input and symmetric with respect to them, hence itself and its derivatives J. will also involve them only and being symmetric with respect to them. Thus determined by Cii, Cij. Cjj. Furthermore, since Já is linear map, so it will have this form. The result in Theorem should hold general for DOS operators and do not require information about the fixed point structure.
Now Jo is DOS operator, hence will belong to DOS(u, v, w) for some u, v, w. Then we know:
[C)
Σ (J,(C),))²
i1=1
Σ
(ucx)² ) + Σ
(veu + vots + w
1=1
ifj
17

---

Under review as a conference paper at ICLR 2020
Conrespondingly have:
|| Σ (J(SS)))
Σ cx)²
Σ
(18fce u85c23 + w8ssscyy)
Since the inequality we want to prove is homogeneous of degree with respect to 8; on both sides, hence without loss of generality we can assume Σ o? (this choice of gauge is intended to include the case in which all 5; Consider the function of (nonzero) C Ha:
(SCS())
((C) ming [C)(
Here ming minimizing over diagonal S with Σ o² d, which is a compact set, hence the minimum is achieved at some point for any fixed C. And notice that at S Id. K 1, so (CC) S and the equality will hold if and only if Id is the minimun point of:
((C, S): = (SC(())))
(uston)) +
> (usfcH + usJo + ws,ssciy)
with this fixed C. In particular, we know that at Karush-Kuhn- Kuhn-Tuuckr (KKT) conditions (which could also be derived from the method of Lagrange multiplier in this case). Next we derive the KKT condition for each component. Define:
84 1 this function satisfties
[SS1,..., Sd. A)
(ust + E(sieoH us3cis + w8,8)07) 2- X d),
igf
then the KKT conditions (i.e., the extreme value condition for restricted optimization) are:
4u2 4u2 Cas + Σ 2(usfcn + us3e55 + (8:s)c;))(28s14 + wss0tt)
2)s; 0.
Now evaluate at
= 1, we have:
4u cis + Σ 2(UCH + vc,s + wcr)) + wory) - 2A 0.
When v o 0, the coefficient of C2 is nonzero. Thus this gives quadratic defining function for those C where our statement may fail. Denote the left hand side of the equation by F,, when Vc * O, defines a smooth codimension submanifold of Hμ. When VcF, = O, it gives rise to linear equation, in which qu has coefficient 4(d 1 hence still gives rise to codimension one smooth submanifold of Ha- In particular, the union of them is a codimension object (not necessarily smooth after we take union). Therefore, those where K (CC, S) could reach have measure zero (this can be proved rigorously by outer regularity of the Haar measure μ on Ha). Thus, for p-almost every matrix, we could choose S with Ed sÿ d, such that [| [[))(C))]p That is, the scaling increases the stability of updates.
H CHARACTERIZATION OF THE OPERATOR IN THEOREM
For T E (u, v w), its eigenspace has clear characterization, which is useful in the study of the behavior of T. Let Ma be the subspace of Ha spanned by those matrices only has off-diagonal
18

---

Under review as a conference paper at ICLR 2020
entries, which have dimension d(d-1) and basis M.j E,j + EJe, where E, is the matrix with on (i,j) position and anywhere else. And La is the span L,, which is defined as:
L -
-
2
u
where those non-zero entries are on i i-th row and column.
Theorem 4. For T E DOS(u, v w), w u, Mas La are its eigenspaces, with eigenvalues w, respectively.
Proof. Here the condition w * u ensures that La is linearly independent with elements in Ma since it spans the diagonal part of Hg. The results TM;- wM,j. TL; uL, could be calculated using the definition equations of (OS v, w) and consider them on component level. Since T is linear operator, verifying these eigen properties
the basis is enough for the result. Furthermore, the space we have specified spans a d(d-1) + d d(d++1 dimHHa dimensional space, hence the whole Ha. Thus we have completely characterized the eigenspaces of such T.
1 DIAGRAM OF DRGCN
Sampling Neighbors (for Sampling-bern based GCNs)
Dimensional Reweighting
Aggregate Neighbors
Fully-connected Network and activation
Figure 2: Diagram of DrGCN layer. The "Sampling Neighbors" procudure is only applied in sampling-basse DrGCNs.
J PRE-ACTIVATION GCNS
As discussed in section 3, Our theoretical analysis is based the pre-activation setting, while common GCN methods use post activation. Although they are basically the same we consider the activation in the pre-activation setting as the activation of the previous layer in the post-activation setting, there is still a little difference between pre and post activation that pre-activation activates the input feature. So also experiment pre-activation GCN, table T3 Results are averaged among 20 runs.
19

---

Under review as a conference paper at ICLR 2020
Table 13: Results of GCN with pre and post activation on citation datasets.
Method
CoraR
CiteseerR
Pubmed
GCN(pre activation)
84.7= 0.7
74.1 0.4
87.9: 0.3
Dr-GCN(pre activation)
85.1 0.6
74.8+10.8
88.2 = 0,2
GCN
85.9 0.7
74.9 0.7
88.0+ 0.3
Dr-GCN
86.8 0.5
77.5+ 0.6
88.4+ 0.3
20


Reviews:
[{"review_id": "Sklf99RT9S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "This paper proposes a method called \"Dimensional Reweighting\" for graph convolutional networks. The method involves a reparametrization of GCNs (by adding an extra reweighting block in each layer), which the authors show theoretically can reduce variance. The authors supplement this with extensive empirical experiments showing slightly improved performance by adding their method to existing methods.\n\nI would vote to weakly reject this paper for two key reasons - first, I think the writing can be improved and explanations can be clarified, especially for people less familiar with the field like myself. Second, I am not certain how significant the final experimental improvements are (other than on the Reddit dataset), as most of the numbers are not that far apart, and it seems that different methods in the literature already produce fairly different results.\n\nOverall, I think the structure of the paper is fairly good. I feel that a few things should be modified for clarity.\n- You claim a 40% improvement in error rate in the intro, which sounds enormous. I would say \"relative error rate\" to avoid overclaiming, because 40% improvement sounds like you are reducing (absolute) error from 60% to 20%, while in reality you are reducing error from 3.6% to 2.1%.\n- In section 2.1, did not know if the projection matrix W was learned or predefined.\n- I was not sure why you used sigma_g and sigma_s as opposed to just sigma in equation (5). Do you use different activation functions? Also, I did not find what activation function the authors end up using in their experiments.\n- I may have misunderstood something, but the theory does not seem to match the proposed method exactly. The mean-field theory analysis has the activation function after the reweighting by S but before multiplying by W, while the framework in Section 2.2 has the activation after the reweighting by S and after the multiplying by W. I am not sure how much this difference makes, or if it is significant, but I think it should be explained by the authors.\n- I also did not understand exactly what the \"variance\" the authors are reducing is. The authors talks about \"reducing the learning variance brought by perturbations on the input,\" but when is the input ever perturbed for GCNs? Explaining this more clearly would improve the motivation for this work.\n- I would appreciate a better intuitive explanation of the measure \"K.\" I gather that it is related to the \"variance\" being reduced, but it is different from that.\n\nThe experimental results are good overall, as the proposed method tends to give the best results (by a small margin) across the board. I especially appreciate that the authors performed many experiments over many different datasets and repeated runs 20 times to try to get confident estimates of how well each method performs. I also appreciate that the authors cleaned up the Citeseer and Cora datasets, and I hope the cleaned datasets will be useful for the research community.\nWith that said, I do not know how significant the improvement is. I think something that would be helpful would be to measure the \"variance\" that the method is supposed to be reducing (since it sounds like it is not exactly the same thing as K), and showing that in a table as well. This would show experimentally that the method achieves its intended goal.\n\nMinor comments\n- I would recommend that the authors proofread for English grammar and style in updated versions of the paper. For example, in the first paragraph of the introduction, the authors use \"is proposed\" instead of \"were proposed\" and typo \"broad\" as \"board.\"\n- Just curious, why did you choose a 2 layer network with 2 activation functions for the Dr block? Why not just have 1 hidden layer?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "Hyxi-Xp6qS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 is out of my research area. I could only provide little recommendation. I have tried to read this paper, but it was rather tedious with heavy notations. It would be more friendly to represent the models in visible way for example using diagrams as I can see that the model is a sequence matrix operators with non-linear transformations after that. The paper states that the proposed DrGCNs can improve the stability of GCN models via mean field theory. The experiments were conducted  on benchmark datasets and the proposed method was compared to several GCN variations. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "H1l1V3I-5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "This paper proposes a method, known as DrGCN, for reweighting the different dimensions of the node representations in graph convolutional networks (GCN). Specifically, the representation of every node is element-wise multiplied with a weight vector, which is parameterized as a function of the average input node representation, where the function is a two-layer neural network. \n\nAt a conceptual level, this is similar to various existing normalization schemes, such as batch normalization and weight normalization. While it is claimed in Section 4.3 that the difference is that “[batch normalization] reduces variance between samples, while DrGCN reduces variance between dimensions”, I am not sure if this characterization is accurate. Batch normalization actually makes each dimension have unit (sample) variance and so does not make the variance of each dimension small. What it does is to make the sample variance of each dimension equal, which is also what DrGCN tries to do, i.e.: reduce variance across dimensions (since samples in the case of GCNs are the representations of different nodes). DrGCN is also similar to weight normalization because like weight normalization, DrGCN learns a transformation on top of the vanilla representation (in the case of weight normalization, the vanilla representation is the normalized weight vector; in the case of DrGCN, the vanilla representation is the node representation before reweighting). The conceptual contribution therefore seems incremental. \n\nIncremental conceptual contributions would be fine if (1) they result in a surprising theoretical result, or if (2) they result in a surprising improvement in empirical performance. Unfortunately, neither seems to be demonstrated in this paper. \n\nIn the theoretical analysis, there are various occurrences of unjustified leaps of logic; as a result, what is claimed to be shown by the analysis is different from what is actually shown, and it is unclear what is actually shown is substantially related to the proposed method. For example, in Section 3.1, the paper says that “GCNs are different from fully-connected networks only in \\tilde{A}, and degrade to fully-connected networks when \\tilde{A} = I. So, our analysis can be somehow be generalized to DrGCNs.” The first sentence is true; in other words, it says that fully-connected networks are a special case of GCNs when \\tilde{A} = I. However, the second sentence does not follow - just showing a special case (which is what the subsequent analysis does) does not say much about the general case. Relatedly, the architecture that is analyzed is of the form H^l = W^l \\phi(S^l H^{l-1}) + b^l for l = 1, …, k, whereas the architecture that is proposed is H^l = \\phi(W^l S^l H^{l-1} \\tilde{A}^{l} + b^{l}) for l = 1, …, k. The latter cannot be cast as the former unless \\tilde{A} is diagonal. Also, the caveat of the mean field approximation are not stated - whatever result that is shown is only valid at the infinite width limit, which is different from what is claimed in the abstract, which says that \"We prove that DrGCNs can reduce the variance of the node representations by connecting our problem to the theory of the mean field.” Additionally, the analysis is done in the case where S is directly parameterized, whereas the proposed method parameterizes S as the output of a two-layer neural network. I presume the reason why latter was done in practice because it worked better empirically. Because this is not explained by the analysis, the theory is incomplete, and so this caveat should be clearly stated in the abstract. \n\nIn the experimental results, the performance improvement of DrGCN over layer normalization is not statistically significant. Also, DrGCN is only compared to other normalization schemes (batch normalization and layer normalization) on one dataset, and so there is insufficient evidence to conclude that DrGCN generally works better than existing methods empirically, \n\nAdditionally, in section 2.1, it is claimed that “sampling-based GCNs still lie within the framework of equation (2), as we can set all unsampled edges to 0 in \\tilde{A}”. This does not seem to be accurate, because in sample-based GCNs, different edges are sampled in every minibatch, and so there is no fixed choice of \\tilde{A} that makes these GCNs equivalent to the formulation in eq. (2). \n\nAlso, if the goal is to reduce variance across dimensions (as the paper claims in Section 4.3), why was the average node representation fed into the two-layer neural network rather than its reciprocal?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: As Reviewer 2 pointed out in his/her response to the authors' rebuttal, this paper (at least in current state) has significant shortcomings that need to be addressed before this paper merits acceptance.
Decision: Reject