Graph convolutional networks (GCNs) are powerful deep neural networks for graph-structured data. However, GCN computes nodes' representation recursively from their neighbors, making the receptive field size grow exponentially with the number of layers.   Previous attempts on reducing the receptive field size by subsampling neighbors do not have any convergence guarantee, and their receptive field size per node is still in the order of hundreds. In this paper, we develop a preprocessing strategy and two control variate based algorithms to further reduce the receptive field size. Our algorithms are guaranteed to converge to GCN's local optimum regardless of the neighbor sampling size. Empirical results show that our algorithms have a similar convergence speed per epoch with the exact algorithm even using only two neighbors per node. The time consumption of our algorithm on the Reddit dataset is only one fifth of previous neighbor sampling algorithms. Graph convolution networks (GCNs) BID1 generalize convolutional neural networks (CNNs) (LeCun et al., 1995) to graph structured data. The "graph convolution" operation applies same linear transformation to all the neighbors of a node, followed by mean pooling. By stacking multiple graph convolution layers, GCNs can learn nodes' representation by utilizing information from distant neighbors. GCNs have been applied to semi-supervised node classification BID1 , inductive node embedding (Hamilton et al., 2017a) , link prediction (Kipf & Welling, 2016; BID1 and knowledge graphs (Schlichtkrull et al., 2017) , outperforming multi-layer perceptron (MLP) models that do not use the graph structure and graph embedding approaches (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016 ) that do not use node features.However, the graph convolution operation makes it difficult to train GCN efficiently. A node's representation at layer L is computed recursively by all its neighbors' representations at layer L − 1. Therefore, the receptive field of a single node grows exponentially with respect to the number of layers, as illustrated in FIG0 . Due to the large receptive field size, BID1 proposed training GCN by a batch algorithm, which computes the representation for all the nodes altogether. However, batch algorithms cannot handle large scale datasets because of their slow convergence and the requirement to fit the entire dataset in GPU memory. Hamilton et al. (2017a) made an initial attempt on developing stochastic algorithms to train GCNs, which is referred as neighbor sampling (NS) in this paper. Instead of considering all the neighbors, they randomly subsample D (l) neighbors at the l-th layer. Therefore, they reduce the receptive field size to l D (l) , as shown in FIG0 (b). They found that for two layer GCNs, keeping D (1) = 10 and D (2) = 25 neighbors can achieve comparable performance with the original model. However, there is no theoretical guarantee on the predictive performance of the model learnt by NS comparing with the original algorithm. Moreover, the time complexity of NS is still D(1) D (2) = 250 times larger than training an MLP, which is unsatisfactory.In this paper, we develop novel stochastic training algorithms for GCNs such that D (l) can be as low as two, so that the time complexity of training GCN is comparable with training MLPs. Our methods are built on two techniques. First, we propose a strategy which preprocesses the first graph convolution layer, so that we only need to consider all neighbors within L−1 hops instead of L hops. This is significant because most GCNs only have L = 2 layers BID1 ; Hamilton et al., 2017a) . Second, we develop two control variate (CV) based stochastic training algorithms. We show that our CV-based algorithms have lower variance than NS, and for GCNs without dropout, our algorithm provably converges to a local optimum of the model regardless of D (l) .We empirically test on six graph datasets, and show that our techniques significantly reduce the bias and variance of the gradient from NS with the same receptive field size. Our algorithm with D (l) = 2 achieves the same predictive performance with the exact algorithm in comparable number of epochs on all the datasets, while the training time is 5 times shorter on our largest dataset. The large receptive field size of GCN hinders its fast stochastic training. In this paper, we present a preprocessing strategy and two control variate based algorithms to reduce the receptive field size. Our algorithms can achieve comparable convergence speed with the exact algorithm even the neighbor sampling size D (l) = 2, so that the per-epoch cost of training GCN is comparable with training MLPs. We also present strong theoretical guarantees, including exact prediction and convergence to GCN's local optimum, for our control variate based algorithm. DISPLAYFORM0 H (l+1) DISPLAYFORM1 After one more epoch, all the activations h (l+1)CV,i,v are computed at least once for each v, soH DISPLAYFORM2 for all i > (l + 2)I. By induction, we know that after LI steps, we havē DISPLAYFORM3 2. We omit the time subscript i and denote DISPLAYFORM4 CV,v ). By back propagation, the approximated gradients by CV can be computed as follows DISPLAYFORM5 where • is the element wise product and σ (Z DISPLAYFORM6 CV ) is the element-wise derivative. Similarly, denote DISPLAYFORM7 v ), the exact gradients can be computed as follows DISPLAYFORM8 Applying EP = EP (1) ,...,P (L) to both sides of Eq. 8, and utilizing DISPLAYFORM9 we have DISPLAYFORM10 Comparing Eq. 10 and Eq. 9 we get DISPLAYFORM11
A control variate based stochastic training algorithm for graph convolutional networks that the receptive field can be only two neighbors per node.
{"src": "scitldr-AIC_train", "paper_id": "rylejExC-"}