Title: DIMENSIONAL REWEIGHTING GRAPH CONVOLU-TIONAL NETWORKS

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 have the effect of stabilizing the training process 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.

1. INTRODUCTION:

Deep neural networks (DNNs) have been widely applied in various fields, including computer vision (He et al., 2016; 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 extended to graph convolutional network (GCN) that achieves better performance by capturing topological information of linked graphs (Kipf & Welling, 2017) . Since then, GCNs begin to attract board interests. Starting from GraphSAGE (Hamilton et al., 2017) defining the convolutional neural network based graph learning framework as 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-El-Haija et al., 2019) and adaptive sampling (Huang et al., 2018) .

In this paper, we study the node representations in GCNs from the perspective of covariance between dimensions. Suprisingly, applying a 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 to 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 improvements on public datasets adopted in the literature over the state-of-the-art GCNs. While studying on these well-known benchmarks, we notice that two of them (Cora, Citeseer) suffer from duplicates and feature-label information leaks. We fix these problems and offer refined datasets for fair comparisons. To further validate the effectiveness, we deploy the proposed DrGCNs on A*1 company's recommendation system and clearly demonstrate performance improvements via offline evaluations.

2. DRGCNS: DIMENSIONAL REWEIGHTING GRAPH CONVOLUTIONAL NETWORKS:

2.1 PRELIMINARIES Notations. We focus on undirected graphs G = (V, E, X), where V = {v i } represents the node set, E = {(v i , v j )} indicates the edge set, and X stands for the node features. For a specific GCN layer, we use R in = (r in 1 , ..., r in n ) to denote the input node representations and R out = (r out 1 , ..., r out n ) to symbolize the output representations. 2 For the whole layer-stacked GCN structure, we use H 0 to denote the input node representation of the first layer, and H l (l > 0) to signify the output node representation of the l th layer, which is also the output representation of the (l -1) th layer. Let A be the adjacency matrix with a ij = 1 when (v i , v j ) ∈ E and a ij = 0 otherwise.

Graph Convolutional Networks (GCNs). Given the input node set V, the adjacency matrix A, and the input representations R in , a GCN layer uses such information to generate output representations R out :

EQUATION

)

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 as a weighted sum of node representations among the neighborhood (Kipf & Welling, 2017; Huang et al., 2018) , followed by a matrix multiplication on a refined adjacency matrix Ã, with a bias added. The procedure can be formulated as follows:

EQUATION

)

where W is the projection matrix and b denotes the bias vector. Development on GCNs mainly lies in different ways to generate Ã. 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 Ã = D -1 2 AD -1 2 , or including self-loops Ã = I + D -1 2 AD -1 2 . 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 a sampling procedure, which samples a subset of the neighborhood for aggregation (Chen et al., 2018; Huang et al., 2018) . We can set all unsampled edges to 0 in Ã in sampling-based GCNs, in this case Ã even has some randomness.

2.2. MODEL FORMULATION FOR DRGCNS:

Given input node representations of a GCN layer R in , the proposed DrGCN tries to learn a dimensional reweighting vector s = (s 1 , ..., s d ), where s i is an adaptive scalar for each dimension i. This reweighting vector s then helps reweighting each dimension of the node representation

EQUATION

We define S as the diagonal matrix with diagonal entries corresponding to the components of s.

Then a DrGCN layer can be formulated as:

EQUATION

Inspired by SENet (Hu et al., 2018) , we formulate the learning of the shared dimensional reweighting vector s in two stages. First we generate a global representation r in , whose value is the expectation of r in v on the whole graph. Then we feed r in into a two-layer neural network structure to generate 

EQUATION

)

where g is output of the first layer; W g , b g , W s , and b s are parameters to be learnt. Figure 1 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 in and does not involve in the calculation of Ã, 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 sample-and-aggregation GCN methods. Suppose that the input features are X, DrGCNs can be viewed as follows:

EQUATION

where H 0 = X and H k being the output representation for a k-layer DrGCN:

Complexity of Dr Block. Consider a GCN layer with a input and b output channels, n nodes and e edges in a sampled batch, the complexity of a GCN layer is O(abn+be). The proposed Dr block has a complexity of O(ag), where g is the dimension of g. In most cases, we have g < b and n >> 1, so we could have O(ag) = o(abn + be), which indicates that Dr block introduces negligible extra computational cost.

3. THEORETICAL ANALYSES:

In this section, we connect our study to mean field theory (Yang et al., 2019) . We theoretically prove that the proposed Dr Block is capable of reducing the learning variance brought by perturbations on the input, making the update more stable in the long run. To deepen the understanding, we further develop a measure to 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, we provide theoretical analyses for Dr Blocks on fully-connected networks. GCNs are different from fully-connected networks only in Ã, and degrade to fullyconnected networks when Ã = I, our idea is to provide insight to GCNs from the analysis of fully-connected networks. We assume the average of the data is 0 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 (Yang et al., 2019) to facilitate the problem. When S being a diagonal matrix with positive entries, and φ is ReLU activation, φ(SH) = Sφ(H) holds for all H. We can take the pre-activation step as the post-activation step of the previous layer and generalize our analysis to post-activation. So the recursive relation is:

h l i = W l σ l (S l • h l-1 i ) + b l in

EQUATION

We apply the mean field approximation to replace the input data by a normal random variable with the same mean and variance and define an estimator V φ to characterize the fluctuation of the random variable φ(S l H).

Define:

EQUATION

In this equation H ∼ N (0, C l-1 ), φ is the ReLU activation, and C l represents the covariance matrix of H l , i.e. C l = Cov(H l ). Note that V φ 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 l is independent with H):

EQUATION

We assume this dynamical system has a BSB1(Block Symmetry Breaking 1 (Yang et al., 2019) ) fixed point (where C l = C l-1 ) , i.e. a solution having the form

EQUATION

)

Next we make a reduction of V φ so that only the second slot matters. Take S l h as a whole, it follows N (0, S l C l-1 S l ) distribution. Note that S is diagonal so S = S T . Thus equation ( 9) can be written as:

EQUATION

)

The derivative of C l measures the fluctuation of 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 l where we are taking derivative at. 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 a linear map from symmetric matrices to symmetric matrices.

Define:

EQUATION

Here C 1 could be intuitively understood as the increment near C l . We denote by H d the space of symmetric matrices of size d × d. Using these notations, we prove that: Theorem 1. There exist diagonal matrices S l , constants 0 < γ l < 1 such that,

||J φ (S l CS l )|| F ≤ γ l ||J φ (C)|| F ||S l || F d

for any fixed general C. By general, we mean there exists a Haar measure on the collection of symmetric matrices H B with respect to which the statement fails has measure zero3 .

Detailed proofs and explanations are included in the Appendix G,H. For symmetric matrices, with λ i denoting eigenvalues of A, we have:

EQUATION

This norm measures the overall magnitude of eigenvalues 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.

Define:

EQUATION

where c ij is the (i, j) th element of the convariance matrix C. Theorem 2 suggests that K 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 of degree 0 with respect to these entries and invariant under scalar multiplication on these entries. Being the covariance matrix of H, C does not change under the mean zero case of H. Consequently, we 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:

EQUATION

where

G = I -1 d 1 1 T 4 , i.e. Gx = x -µ 1, µ = 1 d i x i . Theorem 2. Near the fixed point C * of V d φ , the exponential growth rate of the deviation of C l from C * is proportional to K.

Here C * is used to denote the BSB1 fixed points of V d φ (I, C)5 . Since S l H has covariance matrix S l CS l , our scaling effect is that

V d φ (S, C) = V B φ (I, S l CS l ).

We use the following definitions to simplify notations.

Define:

EQUATION

)

Theorem 3.6 of (Yang et al., 2019) tells us the derivative of V d φ (I, C) (as a linear map) has a very explicit eigenspace decomposition, we describe it in Theorem 3. A simple reflection suggests that our linear operators still satisfy the DOS condition and the ultrasymmetry condition needed in the proof of this theorem, so this decomposition still holds.

Theorem 3. J d φ := dV d φ

dC at C * has eigenspaces and eigenvalues:

1. V 0 = {C 0 : C G = 0}, with eigenvalue 0. 6 . 2. V G = RG, with eigenvalue λ G . 3. A (d -1) dimensional eigenspace V L . = {D G : D diagonal, trD = 0}. 4. A d(d-3) 2 -dimensional eigenspace V M = {C : C G = C, diag C = 0} with eigenvalue λ M . λ L , λ M < 1, whereas λ G > 1.

So an appropriately chosen S can reduce the proportion that lies in V G . We prove that the Frobenius norm of the component in V G 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 (with subindices indicating the corresponding eigenspaces we listed above):

EQUATION

)

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 to reducing

EQUATION

recall that

G = I -1 d 1 1 T , i.e. Gx = x -µ 1, µ = 1 d i x i .

Since we take the normalization assumption, only the relative magnitude of s li matters, and we can put any homogeneous restriction. In order to include the case s li = 1, we consider the restriction

EQUATION

)

Finally we come to the effectiveness measure of the proposed Dr Block.

K = i c ii s 2 li -1 d i,j c ij s li s lj ( i c ii -1 d i,j c ij ) × i s 2 li d .

(20) The denominator is chosen to display the ratio of variance reduction for the proposed Dr Block. Without Dr, s li = 1 for all i, and we have K = 1. From our calculation on the inner product, it can be discovered that this quantity is proportional to the part in V G in the orthogonal decomposition, this proves Theorem 2. Since this is the only part for J d φ with eigenvalue larger than 1, the exponential growth rate is proportional to this quantity. Therefore, this quantity measures the magnitude of improvement Dr Blocks make to the stability of the learning process under perturbation.

4. EXPERIMENTS:

In this section, we evaluate the proposed DrGCNs on a variety of datasets compared to several SOTA methods. Detailed descriptions of the experiments and datasets are included in Appendix C,D.

4.1. EXPERIMENTAL SETTINGS:

Datasets We present the performance of DrGCNs on several public benchmark node classification 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 1 summarizes statistics of the datasets.

There are also two widely adopted Cora and Citeseer datasets (Yang et al., 2016) for citation networks. 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 in Cora and 161(4.8%) samples in Citeseer are duplicated, while 1,145(42.3%) samples in Cora and 2,055(61.8%) samples in Citeseer have information leak that includes their labels directly as a dimension of their features. To address such problems, we remove duplicated samples, modify their features using word and text embeddings to reduce information leak, and construct two refined datasets, CoraR and CiteseerR. For details of these refined datasets and A* dataset, please refer to Appendix A,B,E.

Competitors We compare the results of our 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 state-of-the-art 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 E.

DrGCNs We combine Dr block with five most representative GCN methods and compare with them on public datasets. Two full GCN methods include the vanilla GCN (Kipf & Welling, 2017) and a variant that exploits an attention aggregator GAT (Veličković et al., 2018) . Sampling GCN methods contain FastGCN (Chen et al., 2018) , Adaptive Sampling GCN (Huang et al., 2018) The performance improvements can be explained by our stability measure proposed in Equation ( 20). Theoretically, when K ≈ 1, we expect Dr block to have limited ability in refining the representation, while when K 1 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 5 . The K-value in the second layer is 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 a massive improvement on the Reddit dataset.

On the inductive PPI dataset (Table 3 ), Dr Block increases the micro f1-score of GAT by 1.5% and outperforms all previous methods. Table 4 suggests that the Dr method can also accomplish substantial improvements on the real-world, large-scale recommendation dataset. It demonstrates improvement on industrial measure recall@50, which is the rate of users clicking the top 50 predicted items among 6 million different items within the next day of the training set, from 5.19% (previous best model) to 5.26% (Dr Block added).

4.3. BATCH-NORM AND LAYER-NORM:

We also compare DrGCNs with other feature refining methods, including Batch-Norm (Ioffe & Szegedy, 2015) and Layer-Norm (Lei Ba et al., 2016) . These methods use variance information on every single dimension to refine representations, while DrGCN joins information on each dimension and learns a reweighting vector S adaptively. We provide results of DrGCN and these methods on the Reddit dataset for ASGCN( Table 6 ). 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 F.

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 a neural network structure on graph structure learning. GCN (Kipf & Welling, 2017) proposes a deep-learning-based method to learn node representations on a graph using gathered information from the neighborhood of a node. GraphSAGE (Hamilton et al., 2017) formulated a sample and aggregation framework of inductive node embedding. The idea of the sample and aggregation framework is to incorporate information from the neighborhood to generate node embeddings. Despite being uniform when first being proposed, both sampling and aggregation can be weighted. These methods, including FastGCN (Chen et al., 2018) , GAT (Veličković Many also try to give theoretical analyses to 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, 2009) . In our approach, we adopt some of these methods and apply them to the analysis of DrGCNs.

6. 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 a new measure K to 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 theoretical analysis on measure K. DrGCNs' usefulness is likewise verified on large-scale industrial dataset A*. 

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 to 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 are 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-word(BOW) vectors that each dimension represents whether the document of the paper contains a 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 a dictionary size of 3,703.

A.1 CORA Cora originates in (McCallum et al., 2000) 7 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) 8 extracts a subset of 2,708 papers and assigns labels and BOW feature vectors to the papers. The dictionary is chosen from words(after stemming) 9 that occur 10 or 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 et al., 2016) .

There exist a lot of duplicated papers (one paper appears as multiple identical papers in the dataset) in the original Cora of (McCallum 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 is 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 classified 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 stemming). Altogether 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 11 ), which provides a URL based web API for each paper according to their doc-ids. (Lu & Getoor, 2003) 12 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. It is also reordered and adopted by Planetoid (Yang et al., 2016) .

Although the original version of Citeseer only consists of links that are unavailable now, a back-up version of Citeseer contains the title and abstract information of 3,186 of the papers. 13 We also find another 81 by author and year information using Google Scholar. Unfortunately, among the papers we collected from the Citeseer dataset, 161(4.8%) of them are actually duplicated.

Since the Citeseer dataset shares a 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. 

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 (Mc-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 use their titles to 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 a training set of 1,180 nodes, a validation set of 500 nodes and a test set of 1,000 nodes.

C IMPLEMENTATION DETAILS C.1 DR BLOCK CONFIGURATION:

For the dimensional reweighting part of each layer, the dimension of the encoder g is set to the closest integer of the square root of the dimension of the input node representation r i . The pooling weight w v is set to uniform weight w v = 1 |V| , 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 σ g and sigmoid activation for σ s . 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 representation dimension, batch size, weight decay, and regularization loss the same as 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 we run. We evaluate their performance mainly based on 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 (Kipf & Welling, 2017) We use the GCN code provided in AS-GCN14 , and use a 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ć et al., 2018) We use the GAT code provided by the authors15 . We use the dataset-specific structures described in (Veličković et al., 2018) and early stopping strategy mentioned in 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 on Pubmed, such a high dropout may have a chance to lead the original GAT model not to converge, so we adjusted the dropout rate to 0.35(which gives the best performance among all dropout rates from 0 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.

GAT forms a 2 layer structure for citation datasets. For Cora and Citeseer, GAT has 8 hidden units in every attention head in the first layer, and 8 attention heads in the first layer and 1 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), so we also adopt the Cora/Citeseer structure to Pubmed.

For PPI, GAT has a three layer structure, with 256 hidden units in 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 a number of hidden units equal to node classes. It also sets dropout equals to 0 and uses residual connection (He et al., 2016) .

FastGCN (Chen et al., 2018) We run the code provided by the authors. 16 We use 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 an average performance and variations.

ASGCN (Huang et al., 2018) We use the code provided by the authors17 . We use a neighborhood size of 128 for CoraR, CiteseerR, 256 for Pubmed and 512 for Reddit as the paper suggested. (Huang et al., 2018) Their original code seems to have a bug causing unnecessary test set 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. Mix-Hop (Abu-El-Haija et al., 2019) We use the code provided by the authors18 . We use 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, so we fix the network structure and tune the hyperparameter set for CoraR and CiteseerR ourselves.

GraphSAGE (Hamilton et al., 2017) We use the code provided by the authors19 on CoraR, Cite-seerR and Pubmed. For Reddit this code does not work so we use another code also provided by the author20 

Other Methods Many of them do not have their codes released, so we use their reported performance in their papers, or reported performance of 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, 1 Reddit dataset, 1 inductive PPI dataset, and 1 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., 2008; Yang et al., 2016) There are two types of experimental settings, the semi-supervised setting for full GCNs (Kipf & Welling, 2017; Veličković et al., 2018) , which uses only a 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 statistics 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 10. We also provide our results on the semi-supervised setting on Cora, Citeseer, and Pubmed dataset in table 11.

PPI The protein-protein interaction dataset is collected by SNAP (Hamilton et al., 2017) from the Molecular Signatures Database (Subramanian et 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 et al., 2017) from Reddit posts. It is a node classification dataset for classifying different communities of each user by his/her posts. 

EQUATION

M u represents the top-N items recommended by the model and I u indicates the items clicked by the customer. The baseline model is the A* online heterogeneous GraphSAGE, and we add Dr block in it to compare Recall@N with the online model.

Recall@50 is the most commonly used metric in A* company. Experimental results show that we reach 5.264% on Recall@50, improving from the original best model's 5.188%. It is quite a 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 and layer-norm GCN results on publication datasets.

The results are averaged among 20 runs.

G PROOF OF THEOREM 1:

We also provide proof for theorem 1 in the main article.

Correspondingly we have:

||J φ (SCS)|| 2 F = d i,j=1 (J φ (SCS) ij ) 2 = d i=1 (us 2 i c ii ) 2 + i =j (vs 2 i c ii + vs 2 j c jj + ws i s j c ij ) 2 .

Since the inequality we want to prove is homogeneous of degree 2 with respect to s i on both sides, hence without loss of generality we can assume d i=1 s 2 i = d (this choice of gauge is intended to include the case in which all s i = 1). Consider the function of (nonzero) C ∈ H d :

K(C) := min S ||J φ (SCS)|| 2 F ||J φ (C)|| 2 F .

Here min S is minimizing over diagonal S with d i=1 s 2 i = 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 K(C) ≤ 1 and the equality will hold if and only if S = Id is the minimun point of:

K(C, S) : = ||J φ (SCS)|| 2 F = d i=1 (us 2 i c ii ) 2 + i =j

(vs 2 i c ii + vs 2 j c jj + ws i s j c ij ) 2 , with this fixed C. In particular, we know that at s 1 = s 2 = ... = s d = 1 this function satisfties Karush-Kuhn-Tucker (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: then the KKT conditions (i.e., the extreme value condition for restricted optimization) are:

4u 2 s 3 i c ii + j =i

2(vs 2 i c ii + vs 2 j c jj + ws i s j c ij )(2vs i c ii + ws j c ij ) -2λs i = 0. Now evaluate at s 1 = ... = s d = 1, we have:

4u 2 c ii + j =i

2(vc ii + vc jj + wc ij )(2vc ii + wc ij ) -2λ = 0.

When v = 0, the coefficient of C 2 is nonzero. Thus this gives a quadratic defining function for those C where our statement may fail. Denote the left hand side of the equation by F i , when ∇ C F i = 0, it defines a smooth codimension 1 submanifold of H d . When ∇ C F i = 0, it gives rise to a linear equation, in which c ii has coefficient 4(d -1)v 2 , hence still gives rise to a codimension one smooth submanifold of H d . In particular, the union of them is a codimension 1 object (not necessarily smooth after we take union). Therefore, those C where K(C, S) could reach 1 have measure zero (this can be proved rigorously by outer regularity of the Haar measure µ on H d ). Thus, for µ-almost every matrix, we could choose an S with 

H CHARACTERIZATION OF THE OPERATOR IN THEOREM 1:

For T ∈ DOS(u, v, w), its eigenspace has clear characterization, which is useful in the study of the behavior of T. Let M d be the subspace of H d spanned by those matrices only has off-diagonal entries, which have dimension d(d-1) 2 and a basis M ij = E ij + E ji , where E ij is the matrix with 1 on (i, j) position and 0 anywhere else. And L d is the span of L i , which is defined as:

L i      • • • -v • • • • • • -v • • • -v -v • • • w -u -v • • • • • • -v • • • • • • -v • • •     

, where those non-zero entries are on i-th row and column. 

J PRE-ACTIVATION GCNS:

As discussed in section 3, Our theoretical analysis is based on the pre-activation setting, while common GCN methods use post activation. Although they are basically the same if 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 we also experiment pre-activation on GCN, see table 13 . Results are averaged among 20 runs.

:

To preserve anonymity we use A* for the company and dataset name.

For the convenience of our analysis, we use columns of R, H, X instead of rows to represent node representations.

|| • ||F is the Frobenius norm, i.e. for a matrix A= (Aij), ||A|| 2 F = i,j A 2 ij .

1 is the d-dimensional vector with all component 1.

All results involve the BSB1 fixed point(Yang et al., 2019) require permutation, diagonal and off-diagonal symmetry, and hold for dimensional normalization, too.

G, S above are symmetric, so the transpose is only introduced for the sake of notational balance

https://github.com/huangwb/AS-GCN

https://github.com/PetarV-/GAT

https://github.com/matenure/FastGCN

https://github.com/huangwb/AS-GCN

https://github.com/samihaija/mixhop

https://github.com/williamleif/graphsage-simple

https://github.com/williamleif/GraphSAGE

Figures and Tables:

Figure 1: Our proposed dimensional reweighting block (Dr Block) in DrGCNs. s of the same dimension size. Equation (5) denotes the procedure to generate s given node weight {w v |v ∈ V, v∈V w v = 1} and node representations {r in v |v ∈ V}:

i c ii + vs 2 j c jj + ws i s j c ij ) 2 -λ(

= d, such that ||J φ (SCS)|| F < ||J φ (C)|| F .That is, the scaling increases the stability of updates.

Figure 2: Diagram of a DrGCN layer. The "Sampling Neighbors" procudure is only applied in sampling-based DrGCNs.

Dataset statistics.

Table content: <table><tr><td/><td colspan="3">CoraR CiteseerR Pubmed</td><td>PPI</td><td>Reddit</td><td>A*</td></tr><tr><td>Nodes/Users</td><td>2,680</td><td>3,191</td><td>19,717</td><td>56,944</td><td>232,965</td><td>35,246,808</td></tr><tr><td>Edges</td><td>5,148</td><td>4,172</td><td colspan="4">44,324 818,716 11,606,919 129,834,116</td></tr><tr><td>Classes/Items</td><td>7</td><td>6</td><td>3</td><td>121</td><td>41</td><td>6,338,428</td></tr><tr><td>Features</td><td>302</td><td>768</td><td>500</td><td>50</td><td>602</td><td>27</td></tr><tr><td>Training Nodes</td><td>1,180</td><td>1,691</td><td>18,217</td><td>44,906</td><td>152,410</td><td>35,246,808</td></tr><tr><td>Validation Nodes</td><td>500</td><td>500</td><td>500</td><td>6,514</td><td>23,699</td><td>-</td></tr><tr><td>Test Nodes</td><td>1,000</td><td>1,000</td><td>1,000</td><td>5,524</td><td>55,334</td><td>35,246,808</td></tr></table>

Summary of classification accuracy on public transductive datasets(%).

Table content: <table><tr><td>Category</td><td>Method</td><td>CoraR</td><td>CiteseerR</td><td>Pubmed</td><td>Reddit</td></tr><tr><td/><td>GCN</td><td colspan="3">85.9±0.5 74.9± 0.7 88.0± 0.3</td><td>-</td></tr><tr><td>Full GCNs</td><td>GAT</td><td colspan="3">86.9± 0.4 76.5± 0.4 85.0± 0.2</td><td>-</td></tr><tr><td/><td>Mix-Hop</td><td colspan="3">85.9± 0.5 75.3± 0.3 88.1± 0.2</td><td>-</td></tr><tr><td>Sampling-based GCNs</td><td>GraphSage FastGCN ASGCN</td><td colspan="4">84.9± 0.5 70.6± 0.8 84.2± 0.3 94.8± 0.1 81.7± 0.4 74.7± 0.6 88.3± 0.4 92.5± 0.2 84.3± 0.7 75.1± 0.9 89.8± 0.3 96.4± 0.3</td></tr><tr><td>DrGCNs</td><td>Dr-GCN Dr-GAT</td><td colspan="3">86.8± 0.5 77.5± 0.6 88.4± 0.3 87.3± 0.2 77.0± 0.3 84.7± 0.4</td><td>--</td></tr><tr><td>DrGCNs(sampling based)</td><td colspan="5">Dr-FastGCN 81.6± 0.5 75.5± 0.5 88.2± 0.3 94.0± 0.1 Dr-ASGCN 84.3± 0.5 75.4± 0.4 90.3± 0.4 97.9± 0.1</td></tr></table>

Summary of performance (micro F1) on inductive PPI dataset. 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-art method ASGCN.

Table content: <table><tr><td colspan="5">Method GraphSAGE LGCN GeniePath GAT</td><td>Dr-GAT</td></tr><tr><td>micro F1</td><td>61.2</td><td>77.2</td><td>97.9</td><td colspan="2">97.3 98.8± 0.1</td></tr></table>

Performance (Recall@50) on A* online recommendation system. GraphSAGE refers to A* company's best heterogeneous GraphSAGE model.

Table content: <table><tr><td>Method</td><td colspan="2">GraphSAGE DrGraphSAGE</td></tr><tr><td>Recall@50(%)</td><td>5.19</td><td>5.26</td></tr></table>

Classification accuracy of ASGCN and Dr-ASGCN model, with average K value learnt for each layer.

Table content: <table><tr><td>Method</td><td colspan="6">Cora Citeseer CoraE CiteseerE Pubmed Reddit</td></tr><tr><td>ASGCN</td><td>87.23</td><td>78.95</td><td>84.30</td><td>75.12</td><td>89.82</td><td>96.37</td></tr><tr><td>Dr-ASGCN</td><td>87.07</td><td>79.06</td><td>84.34</td><td>75.44</td><td>90.34</td><td>97.95</td></tr><tr><td>Improvement Rate(%)</td><td>-0.16</td><td>0.11</td><td>0.04</td><td>0.32</td><td>0.52</td><td>1.58</td></tr><tr><td colspan="2">Learnt K-value(Layer 1) 1.04</td><td>1.01</td><td>0.90</td><td>0.95</td><td>0.98</td><td>0.32</td></tr><tr><td colspan="2">Learnt K-value(Layer 2) 1.00</td><td>1.00</td><td>0.99</td><td>1.04</td><td>0.98</td><td>1.14</td></tr></table>

Accuracy and average training time per epoch for plain, batchnorm, layernorm and DrAS-GCN methods on Reddit dataset.

Table content: <table><tr><td>Method</td><td>ASGCN</td><td colspan="2">Batch-norm Layer-norm</td><td>Dr</td><td>Dr+LN</td></tr><tr><td colspan="6">Accuracy(%) 96.37± 0.22 96.99± 0.15 97.68± 0.15 97.95± 0.13 98.02± 0.12</td></tr><tr><td>Time(s/epoch)</td><td>17.99</td><td>17.90</td><td>18.74</td><td>17.46</td><td>17.93</td></tr></table>

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-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.

Table content: <table><tr><td>Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian</td></tr><tr><td>fields and harmonic functions. In Proceedings of the 20th International conference on Machine</td></tr><tr><td>learning (ICML-03), pp. 912-919, 2003.</td></tr></table>

Label terms appearing in Cora's title and abstract.

Table content: <table><tr><td/><td>Case Based</td><td>Theory</td><td>Probabilistic Methods</td><td>Rule Learning</td><td>Neural Networks</td><td>Reinforcement Learning</td><td>Genetic Algorithms</td><td>Total</td></tr><tr><td>Total</td><td>298</td><td>351</td><td>426</td><td>180</td><td>818</td><td>217</td><td>418</td><td>2708</td></tr><tr><td>Appeared</td><td>151</td><td>84</td><td>103</td><td>38</td><td>410</td><td>134</td><td>225</td><td>1145</td></tr><tr><td>Rate</td><td colspan="2">50.7% 23.9%</td><td>24.2%</td><td>21.1%</td><td>50.1%</td><td>61.8%</td><td>53.8%</td><td>42.3%</td></tr></table>

Label terms appearing in CiteSeer's title and abstract.

Table content: <table><tr><td/><td>Artificial Intelligence</td><td>Machine Learning</td><td>Information Retrieval</td><td colspan="2">Database Agents</td><td>Human Interface Computer</td><td>Total</td></tr><tr><td>Total</td><td>264</td><td>590</td><td>668</td><td>701</td><td>596</td><td>508</td><td>3327</td></tr><tr><td>Appeared</td><td>54</td><td>334</td><td>434</td><td>403</td><td>521</td><td>309</td><td>2055</td></tr><tr><td>Rate</td><td>20.5%</td><td>56.6%</td><td>65.0%</td><td>57.5%</td><td>87.4%</td><td>60.8%</td><td>61.8%</td></tr></table>

Supplement of Dataset statistics for citation datasets.

Table content: <table><tr><td/><td colspan="3">Cora Citeseer Pubmed</td></tr><tr><td>Nodes</td><td>2,708</td><td>3,327</td><td>19,717</td></tr><tr><td>Edges</td><td>5,278</td><td>4,552</td><td>44,324</td></tr><tr><td>Classes</td><td>7</td><td>6</td><td>3</td></tr><tr><td>Features</td><td>1,433</td><td>3,703</td><td>500</td></tr><tr><td>Training Nodes(Semi)</td><td>140</td><td>120</td><td>60</td></tr><tr><td colspan="2">Training Nodes(Full) 1,208</td><td>1,827</td><td>18,217</td></tr><tr><td>Validation Nodes</td><td>500</td><td>500</td><td>500</td></tr><tr><td>Test Nodes</td><td>1,000</td><td>1,000</td><td>1,000</td></tr></table>

Summary of classification accuracy on fully supervised Cora and Citeseer(%).As for the industrial A* dataset we use. It is an item recommendation dataset, with the training set has about 35 million users and 6.3 million items with 120 million edges. Although the target is 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 a graph embedding model to generate embedding for both users and items. There are 27 user attributes and 33 item attributes. For every user, we use K nearest neighbor (KNN) with Euclidean distance to calculate the top-N items that the user is most likely to click, and the customer will see these recommended items in A* company's APP. We use the recall@N to evaluate the model:

Table content: <table><tr><td>Category</td><td>Method</td><td>Cora</td><td>Citeseer</td></tr><tr><td>Full GCNs</td><td colspan="3">GCN Kipf &amp; Welling (2017) 86.4±0.3 77.4± 0.2 GAT Veličković et al. (2018) 87.2± 0.4 77.8± 0.2</td></tr><tr><td>Sampling-based</td><td colspan="3">FastGCN Chen et al. (2018) 83.9± 0.4 78.6± 0.4</td></tr><tr><td>GCNs</td><td colspan="3">ASGCN Huang et al. (2018) 87.2± 0.2 79.0± 0.4</td></tr><tr><td>Dr GCNs(ours)</td><td>Dr-GCN Dr-GAT</td><td colspan="2">86.8± 0.2 77.5± 0.3 87.4±0.2 77.8± 0.2</td></tr><tr><td>Dr Sampling-based</td><td>Dr-FastGCN</td><td colspan="2">84.0± 0.4 78.3± 0.3</td></tr><tr><td>GCNs(ours)</td><td>Dr-ASGCN</td><td colspan="2">87.1± 0.2 79.1± 0.4</td></tr><tr><td colspan="3">E A* DATASET: DATASET, BASELINE AND EVALUATION</td><td/></tr></table>

Peer review (iclr2020):
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. I 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. Overall, I think the structure of the paper is fairly good. I feel that a few things should be modified for clarity. - 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%. - In section 2.1, did not know if the projection matrix W was learned or predefined. - 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. - 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. - 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. - 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. The 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. With 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. Minor comments - 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.* - 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?