Title: NETWORK OF GRAPH CONVOLUTIONAL NETWORKS TRAINED ON RANDOM WALKS Anonymous

Abstract: Graph Convolutional Networks (GCNs) are a recently proposed architecture which has had success in semi-supervised learning on graph-structured data. At the same time, unsupervised learning of graph embeddings has benefited from the information contained in random walks. In this paper we propose a model, Network of GCNs (N-GCN), which marries these two lines of work. At its core, N-GCN trains multiple instances of GCNs over node pairs discovered at different distances in random walks, and learns a combination of the instance outputs which optimizes the classification objective. Our experiments show that our proposed N-GCN model achieves state-of-the-art performance on all of the challenging node classification tasks we consider: Cora, Citeseer, Pubmed, and PPI. In addition, our proposed method has other desirable properties, including generalization to recently proposed semi-supervised learning methods such as GraphSAGE, allowing us to propose N-SAGE, and resilience to adversarial input perturbations.

1. INTRODUCTION:

Semi-supervised learning on graphs is important in many real-world applications, where the goal is to recover labels for all nodes given only a fraction of labeled ones. Some applications include social networks, where one wishes to predict user interests, or in health care, where one wishes to predict whether a patient should be screened for cancer. In many such cases, collecting node labels can be prohibitive. However, edges between nodes can be easier to obtain, either using an explicit graph (e.g. social network) or implicitly by calculating pairwise similarities (e.g. using a patient-patient similarity kernel, Merdan et al., 2017) .

Convolutional Neural Networks (LeCun et al., 1998) learn location-invariant hierarchical filters, enabling significant improvements on Computer Vision tasks (Krizhevsky et al., 2012; Szegedy et al., 2015; He et al., 2016) . This success has motivated researchers (Bruna et al., 2014) to extend convolutions from spatial (i.e. regular lattice) domains to graph-structured (i.e. irregular) domains, yielding a class of algorithms known as Graph Convolutional Networks (GCNs).

Formally, we are interested in semi-supervised learning where we are given a graph G = (V, E) with N = |V| nodes; adjacency matrix A; and matrix X ∈ R N ×F of node features. Labels for only a subset of nodes V L ⊂ V observed. In general, |V L | |V|. Our goal is to recover labels for all unlabeled nodes V U = V -V L , using the feature matrix X, the known labels for nodes in V L , and the graph G. In this setting, one treats the graph as the "unsupervised" and labels of V L as the "supervised" portions of the data.

Depicted in Figure 1 , our model for semi-supervised node classification builds on the GCN module proposed by Kipf & Welling (2017) , which operates on the normalized adjacency matrix Â, as in GCN( Â) , where Â = D -1 2 AD -1 2 , and D is diagonal matrix of node degrees. Our proposed extension of GCNs is inspired by the recent advancements in random walk based graph embeddings (e.g. Perozzi et al., 2014; Grover & Leskovec, 2016; Abu-El-Haija et al., 2017) . We make a Network of GCN modules (N-GCN), feeding each module a different power of Â, as in {GCN( Â0 ), GCN( Â1 ), GCN( Â2 ), . . . }. The k-th power contains statistics from the k-th step of a random walk on the graph. Therefore, our N-GCN model is able to combine information from various step-sizes. We then combine the output of all GCN modules into a classification sub-network, and we jointly train all GCN modules and the classification sub-network on the upstream objective, Figure 1 : Left: Model architecture, where Â is the normalized normalized adjacency matrix, I is the identity matrix, X is node features matrix, and × is matrix-matrix multiply operator. We calculate K powers of the Â, feeding each power into r GCNs, along with X. The output of all K × r GCNs can be concatenated along the column dimension, then fed into fully-connected layers, outputting C channels per node, where C is size of label space. We calculate cross entropy error, between rows prediction N × C with known labels, and use them to update parameters of classification subnetwork and all GCNs. Right: pre-relu activations after the first fully-connected layer of a 2-layer classification sub-network. Activations are PCA-ed to 50 dimensions then visualized using t-SNE. semi-supervised node classification. Weights of the classification sub-network give us insight on how the N-GCN model works. For instance, in the presence of input perturbations, we observe that the classification sub-network weights shift towards GCN modules utilizing higher powers of the adjacency matrix, effectively widening the "receptive field" of the (spectral) convolutional filters. We achieve state-of-the-art on several semi-supervised graph learning tasks, showing that explicit random walks enhance the representational power of vanilla GCN's.

The rest of this paper is organized as follows. Section 2 reviews background work that provides the foundation for this paper. In Section 3, we describe our proposed method, followed by experimental evaluation in Section 4. We compare our work with recent closely-related methods in Section 5. Finally, we conclude with our contributions and future work in Section 6.

2. BACKGROUND:



2.1. SEMI-SUPERVISED NODE CLASSIFICATION:

Traditional label propagation algorithms (Weston et al., 2012; Belkin et al., 2006a ) learn a model that transforms node features into node labels and uses the graph to add a regularizer term:

EQUATION

where f : R N ×d0 → R N ×C is the model, ∆ is the graph Laplacian, and λ ∈ R is the regularization coefficient hyperparameter.

2.2. GRAPH CONVOLUTIONAL NETWORKS:

Graph Convolution (Bruna et al., 2014) generalizes convolution from Euclidean domains to graphstructured data. Convolving a "filter" over a signal on graph nodes can be calculated by transforming both the filter and the signal to the Fourier domain, multiplying them, and then transforming the result back into the discrete domain. The signal transform is achieved by multiplying with the eigenvectors of the graph Laplacian. The transformation requires a quadratic eigendecomposition of the symmetric Laplacian; however, the low-rank approximation of the eigendecomposition can be calculated using truncated Chebyshev polynomials (Hammond et al., 2011) . For instance, Kipf & Welling (2017) calculates a rank-1 approximation of the decomposition. They propose a multi-layer Graph Convolutional Networks (GCNs) for semi-supervised graph learning. Every layer computes the transformation:

EQUATION

where H (l) ∈ R N ×d l is the input activation matrix to the l-th hidden layer with row H (l)

i containing a d l -dimensional feature vector for vertex i ∈ V, and W (l) ∈ R d l ×d l+1 is the layer's trainable weights. The first hidden layer H (0) is set to the input features X. A softmax on the last layer is used to classify labels. All layers use the same "normalized adjacency" Â, obtained by the "renormalization trick" utilized by Kipf & Welling (2017) , as

Â = D -1 2 AD -1 2 . 1

Eq. ( 2) is a first order approximation of convolving filter W (l) over signal H (l) (Hammond et al., 2011; Kipf & Welling, 2017) . The left-multiplication with Â averages node features with their direct neighbors; this signal is then passed through a non-linearity function σ(•) (e.g, ReLU(z) = max(0, z)). Successive layers effectively diffuse signals from nodes to neighbors.

Two-layer GCN model can be defined in terms of vertex features X and normalized adjacency Â as:

EQUATION

where the GCN parameters θ = W (0) , W (1) are trained to minimize the cross-entropy error over labeled examples. The output of the GCN model is a matrix R N ×C , where N is the number of nodes and C is the number of labels. Each row contains the label scores for one node, assuming there are C classes.

2.3. GRAPH EMBEDDINGS:

Node Embedding methods represent graph nodes in a continuous vector space. They learn a dictionary Z ∈ R N ×d , with one d-dimensional embedding per node. Traditional methods use the adjacency matrix to learn embeddings. For example, Eigenmaps (Belkin & Niyogi, 2003) calculates the following constrained optimization:

EQUATION

)

where I is identity vector. Skipgram models on text corpora (Mikolov et al., 2013) inspired modern graph embedding methods, which simulate random walks to learn node embeddings (Perozzi et al., 2014; Grover & Leskovec, 2016) . Each random walk generates a sequence of nodes. Sequences are converted to textual paragraphs, and are passed to a word2vec-style embedding learning algorithm (Mikolov et al., 2013) . As shown in Abu-El-Haija et al. (2017) , this learning-by-simulation is equivalent, in expectation, to the decomposition of a random walk co-occurrence statistics matrix D. The expectation on D can be written as:

EQUATION

where T = D -1 A is the row-normalized transition matrix (a.k.a right-stochastic adjacency matrix), and Q is a "context distribution" that is determined by random walk hyperparameters, such as the length of the random walk. The expectation therefore weights the importance of one node on another as a function of how well-connected they are, and the distance between them. The main difference between traditional node embedding methods and random walk methods is the optimization criteria: the former minimizes a loss on representing the adjacency matrix A (see Eq. 4), while the latter minimizes a loss on representing random walk co-occurrence statistics D.

3. OUR METHOD:



3.1. MOTIVATION:

Graph Convolutional Networks and random walk graph embeddings are individually powerful. Kipf & Welling (2017) uses GCNs for semi-supervised node classification. Instead of following tradi-tional methods that use the graph for regularization (e.g. Eq. 4), Kipf & Welling (2017) use the adjacency matrix for training and inference, effectively diffusing information across edges at all GCN layers (see Eq. 6). Separately, recent work has showed that random walk statistics can be very powerful for learning an unsupervised representation of nodes that can preserve the structure of the graph (Perozzi et al., 2014; Grover & Leskovec, 2016; Abu-El-Haija et al., 2017) .

Under special conditions, it is possible for the GCN model to learn random walks. In particular, consider a two-layer GCN defined in Eq. 6 with the assumption that first-layer activation is identity as σ(z) = z, and weight W (0) is an identity matrix (either explicitly set or learned to satisfy the upstream objective). Under these two identity conditions, the model reduces to:

EQUATION

where Â2 can be expanded as:

EQUATION

)

By multiplying the adjacency A with the transition matrix T before normalization, the GCN is effectively doing a one-step random walk.

3.2. EXPLICIT RANDOM WALKS:

The special conditions described above are not true in practice. Although stacking hidden GCN layers allows information to flow through graph edges, this flow is indirect as the information goes through feature reduction (matrix multiplication) and a non-linearity (activation function σ(•)).

Therefore, the vanilla GCN cannot directly learn high powers of Â, and could struggle with modeling information across distant nodes. We hypothesize that making the GCN directly operate on random walk statistics will allow the network to better utilize information across distant nodes, in the same way that node embedding methods (e.g. DeepWalk, Perozzi et al. ( 2014)) operating on D are superior to traditional embedding methods operating on the adjacency matrix (e.g. Eigenmaps, Belkin & Niyogi (2003) ). Therefore, in addition to feeding only Â to the GCN model as proposed by Kipf & Welling (2017) (see Eq. 6), we propose to feed a K-degree polynomial of Â to K instantiations of GCN. Generalizing Eq. ( 7) gives:

EQUATION

)

We also define Â0 to be the identity matrix. Similar to Kipf & Welling (2017) , we add selfconnections and convert directed graphs to undirected ones, making Â and hence Âk symmetric matrices. The eigendecomposition of symmetric matrices is real. Therefore, the low-rank approximation of the eigendecomposition Hammond et al. (2011) is still valid, and a one layer of Kipf & Welling (2017) utilizing Âk should still approximate multiplication in the Fourier domain.

3.3. NETWORK OF GCNS:

Consider K instantiations of {GCN( Â0 , X), GCN( Â1 , X), . . . , GCN( ÂK-1 , X)}. Each GCN outputs a matrix R N ×C k , where the v-th row describes a latent representation of that particular GCN for node v ∈ V, and where C k is the latent dimensionality. Though C k can be different for each GCN, we set all C k to be the same for simplicity. We then combine the output of all K GCN and feed them into a classification sub-network, allowing us to jointly train all GCNs and the classification sub-network via backpropagation. This should allow the classification sub-network to choose features from the various GCNs, effectively allowing the overall model to learn a combination of features using the raw (normalized) adjacency, different steps of random walks, and the input features X (as they are multiplied by identity Â0 ).

3.3.1. FULLY-CONNECTED CLASSIFICATION NETWORK:

From a deep learning prospective, it is intuitive to represent the classification network as a fullyconnected layer. We can concatenate the output of the K GCNs along the column dimension, i.e. concatenating all GCN(X, Âk ),

each ∈ R N ×C k into matrix ∈ R N ×C K where C K = k C k .

We add a fully-connected layer f fc : R N ×C K → R N ×C , with trainable parameter matrix W fc ∈ R C K ×C , written as:

N-GCN fc ( Â, A; W fc , θ) = softmax GCN( Â0 , X; θ (0) ) GCN( Â1 , X; θ (1) ) . . . W fc . (9)

The classifier parameters W fc are jointly trained with GCN parameters θ = {θ (0) , θ (1) , . . . }. We use subscript fc on N-GCN to indicate the classification network is a fully-connected layer.

3.3.2. ATTENTION CLASSIFICATION NETWORK:

We also propose a classification network based on "softmax attention", which learns a convex combination of the GCN instantiations. Our attention model (N-GCN a ) is parametrized by vector m ∈ R K , one scalar for each GCN. It can be written as:

EQUATION

)

where m is output of a softmax: m = softmax( m).

This softmax attention is similar to "Mixture of Experts" model, especially if we set the number of output channels for all GCNs equal to the number of classes, as in

C 0 = C 1 = • • • = C.

This allows us to add cross entropy loss terms on all GCN outputs in addition to the loss applied at the output NGCN, forcing all GCN's to be independently useful. It is possible to set the m ∈ R K parameter vector "by hand" using the validation split, especially for reasonable K such as K ≤ 6.

One possible choice might be setting m 0 to some small value and remaining m 1 , . . . , m K-1 to the harmonic series 1 k ; another choice may be linear decay K-k K-1 . These are respectively similar to the context distributions of GloVe (Pennington et al., 2014) and word2vec (Mikolov et al., 2013; Levy et al., 2015) . We note that if on average a node's information is captured by its direct or nearby neighbors, then the output of GCNs consuming lower powers of Â should be weighted highly.

3.4. TRAINING:

We minimize the cross entropy between our model output and the known training labels Y as:

EQUATION

)

where • is Hadamard product, and diag(V L ) denotes a diagonal matrix, with entry at (i, i) set to 1 if i ∈ V L and 0 otherwise. In addition, we can apply intermediate supervision for the NGCN a to attempt make all GCN become independently useful, yielding minimization objective:

EQUATION

3.5. GCN REPLICATION:

To simplify notation, our N-GCN derivations (e.g. Eq. 9) assume that there is one GCN per Â power. However, our implementation feeds every Â to r GCN modules, as shown in Fig. 1 .

3.6. GENERALIZATION TO OTHER GRAPH MODELS:

In addition to vanilla GCNs (e.g. Kipf & Welling, 2017) , our derivation also applies to other graph models including GraphSAGE (SAGE, Hamilton et al., 2017) . Algorithm 1 shows a generalization that allows us to make a network of arbitrary graph models (e.g. GCN, SAGE, or others). Algorithm 2 shows pseudo-code for the vanilla GCN. Finally, Algorithm 3 defines our full Network of GCN model (N-GCN) by plugging Algorithm 2 into Algorithm 1. Similarly, we list the algorithms for SAGE and Network of SAGE (N-SAGE) in the Appendix.

We can recover the original algorithms GCN (Kipf & Welling, 2017) and SAGE (Hamilton et al., 2017) , respectively, by using Algorithms 3 (N-GCN) and 5 (N-SAGE, listed in Appendix) with r = 1, K = 1, identity CLASSIFIERFN, and modifying line 2 in Algorithm 1 to P ← Â. Moreover, we can recover original DCNN (Atwood & Towsley, 2016 ) by calling Algorithm 3 with L = 1, r = 1, modifying line 3 to Â ← D -1 A, and keeping K > 1 as their proposed model operates on the power series of the transition matrix i.e. unmodified random walks, like ours.

Algorithm 1 General Implementation: Network of Graph Models:

Require: Â is a normalization of A 1: function NETWORK(GRAPHMODELFN, Â, X, L, r = 4, K = 6, CLASSIFIERFN=FCLAYER) 2:

P ← I 3: GraphModels ← [] 4:

for k = 1 to K do 5:

for i = 1 to r do 6:

GraphModels.append(GRAPHMODELFN(P, X, L))

7: P ← ÂP 8:

return CLASSIFIERFN(GraphModels)

Algorithm 2 GCN (Kipf & Welling, 2017 )

Require: Â is a normalization of A 1: function GCNMODEL( Â, X, L) 2:

Z ← X 3:

for i = 1 to L do 4: Z ← σ( ÂZW (i) ) 5: return Z Algorithm 3 N-GCN 1: function NGCN(A, X, L = 2) 2: D ← diag(A1) Sum rows 3: Â ← D -1/2 AD -1/2 4:

return NETWORK(GCNMODEL, Â, X, L)

4. EXPERIMENTS:

We follow the experimental setup by Kipf & Welling (2017) and Yang et al. (2016) , including the provided dataset splits (train, validation, test) produced by Yang et al. (2016) .

4.1. DATASETS:

We experiment on three citation graph datasets: Pubmed, Citeseer, Cora, and a biological graph: Protein-Protein Interactions (PPI). We choose the aforementioned datasets because they are available online and are used by our baselines. The citation datasets are prepared by Yang et al. (2016) , and the PPI dataset is prepared by Hamilton et al. (2017) . Table 1 summarizes dataset statistics.

Each node in the citation datasets represents an article published in the corresponding journal. An edge between two nodes represents a citation from one article to another, and a label represents the subject of the article. Each dataset contains a binary Bag-of-Words (BoW) feature vector for each node. The BoW are extracted from the article abstract. Therefore, the task is to predict the subject of articles, given the BoW of their abstract and the citations to other (possibly labeled) articles. Following Yang et al. (2016) and Kipf & Welling (2017) , we use 20 nodes per class for training, 500 (overall) nodes for validation, and 1000 nodes for evaluation. We note that the validation set is larger than training |V L | for these datasets!

The PPI graph, as processed and described by Hamilton et al. (2017) , consists of 24 disjoint subgraphs, each corresponding to a different human tissue. 20 of those subgraphs are used for training, 2 for validation, and 2 for testing, as partitioned by Hamilton et al. (2017) .

4.2. BASELINE METHODS:

For the citation datasets, we copy baseline numbers from Kipf & Welling (2017) Lu & Getoor, 2003) ; Planetoid (Yang et al., 2016) ; vanilla GCN (Kipf & Welling, 2017) . For PPI, we copy baseline numbers from (Hamilton et al., 2017) , which include GraphSAGE with LSTM aggregation (SAGE-LSTM) and GraphSAGE with pooling aggregation (SAGE). Further, for all datasets, we use our implementation to run baselines DCNN (Atwood & Towsley, 2016) , GCN (Kipf & Welling, 2017) (Belkin et al., 2006b) 60.1 59.5 70.7 -(b) SemiEmb (Weston et al., 2012) 59.6 59.0 71.1 -(c) LP (Zhu et al., 2003) 45.3 68.0 63.0 -(d) DeepWalk (Perozzi et al., 2014) 43.2 67.2 65.3 -(e) ICA (Lu & Getoor, 2003) 69.1 75.1 73.9 -(f) Planetoid (Yang et al., 2016) 64.7 75.7 77.2 -(g) GCN (Kipf & Welling, 2017) 70.3 81.5 79.0 -(h) SAGE-LSTM (Hamilton et al., 2017) ---61.2 (i) SAGE (Hamilton et al., Table 2: Node classification performance (% accuracy for the first three, citation datasets, and f1 micro-averaged for multiclass PPI), using data splits of Yang et al. (2016) ; Kipf & Welling (2017) and Hamilton et al. (2017) . We report the test accuracy corresponding to the run with the highest validation accuracy. Results in rows (a) through (g) are copied from Kipf & Welling (2017) , rows (h) and (i) from (Hamilton et al., 2017) , and (j) through (l) are generated using our code since we can recover other algorithms as explained in Section 3.6. Rows (m) and (n) are our models. Entries with "-" indicate that authors from whom we copied results did not run on those datasets. Nonetheless, we run all datasets using our implementation of the most-competitive baselines.

and SAGE (with pooling aggregation, Hamilton et al., 2017) , as these baselines can be recovered as special cases of our algorithm, as explained in Section 3.6.

4.3. IMPLEMENTATION:

We use TensorFlow (Abadi et al., 2015) to implement our methods, which we use to also measure the performance of baselines GCN, SAGE, and DCNN. For our methods and baselines, all GCN and SAGE modules that we train are 2 layers, where the first outputs 16 dimensions per node and the second outputs the number of classes (dataset-dependent). DCNN baseline has one layer and outputs 16 dimensions per node, and its channels (one per transition matrix power) are concatenated into a fully-connected layer that outputs the number of classes. We use 50% dropout and L2 regularization of 10 -5 for all of the aforementioned models.

4.4. NODE CLASSIFICATION ACCURACY:

Table 2 shows node classification accuracy results. We run 20 different random initializations for every model (baselines and ours), train using Adam optimizer (Ba & Kingma, 2015) with learning rate of 0.01 for 600 steps, capturing the model parameters at peak validation accuracy to avoid overfitting. For our models, we sweep our hyperparameters r, K, and choice of classification subnetwork ∈ {fc, a}. For baselines and our models, we choose the model with the highest accuracy on validation set, and use it to record metrics on the test set in Table 2 .

Under review as a conference paper at ICLR 2018 Table 2 shows that N-GCN outperforms GCN (Kipf & Welling, 2017) and N-SAGE improves on SAGE for all datasets, showing that unmodified random walks indeed help in semi-supervised node classification. Finally, our proposed models acheive state-of-the-art on all datasets.

4.5. SENSITIVITY ANALYSIS:

We analyze the impact of K and r on classification accuracy in Figure 2 . We note that adding random walks by specifically setting K > 1 improves model accuracy due to the additional information, not due to increased model capacity. Contrast K = 1, r > 1 (i.e. mixture of GCNs, no random walks) with K > 1, r = 1 (i.e. N-GCN on random walks): in both scenarios, the model has more capacity, but the latter shows better performance. The same holds for SAGE, as shown in Appendix.

4.6. TOLERANCE TO FEATURE NOISE:

We test our method under feature noise perturbations by removing node features at random. This is practical, as article authors might forget to include relevant terms in the article abstract, and more generally not all nodes will have the same amount of detailed information. Figure 3 shows that when features are removed, methods utilizing unmodified random walks: N-GCN, N-SAGE, and DCNN, outperform convolutional methods including GCN and SAGE. Moreover, the performance gap widens as we remove more features. This suggests that our methods can somewhat recover removed features by directly pulling-in features from nearby and distant neighbors. We visualize in Figure 4 the attention weights as a function of % features removed. With little feature removal, there is some weight on Â0 , and the attention weights for Â1 , Â2 , . . . follow some decay function.

Maliciously dropping features causes our model to shift its attention weights towards higher powers of Â.

5. RELATED WORK:

The field of graph learning algorithms is quickly evolving. We review work most similar to ours. Defferrard et al. (2016) define graph convolutions as a K-degree polynomial of the Laplacian, where the polynomial coefficients are learned. In their setup, the K-th degree Laplacian is a sparse square matrix where entry at (i, j) will be zero if nodes i and j are more than K hops apart. Their sparsity analysis also applies here. A minor difference is the adjacency normalization. We use Â whereas they use the Laplacian defined as I -Â. Raising Â to power K will produce a square matrix with entry (i, j) being the probability of random walker ending at node i after K steps from node j. The major difference is the order of random walk versus non-linearity. In particular, their model calculates learns a linear combination of K-degree polynomial and pass through classifier function g, as in g( k q k A k ), while our (e.g. N-GCN) model calculates k q k g( A k ), where A is Â in our model and I -Â in theirs, and our g can be a GCN module. In fact, Defferrard et al. (2016) is also similar to work by Abu-El-Haija et al. ( 2017), as they both learn polynomial coefficients to some normalized adjacency matrix. Atwood & Towsley (2016) propose DCNN, which calculates powers of the transition matrix and keeps each power in a separate channel until the classification sub-network at the end. Their model is therefore similar to our work in that it also falls under k q k g( A k ). However, where their model multiplies features with each power A k once, our model makes use of GCN's (Kipf & Welling, 2017) that multiply by A k at every GCN layer (see Eq. 2). Thus, DCNN model (Atwood & Towsley, 2016 ) is a special case of ours, when GCN module contains only one layer, as explained in Section 3.6.

6. CONCLUSIONS AND FUTURE WORK:

In this paper, we propose a meta-model that can run arbitrary Graph Convolution models, such as GCN (Kipf & Welling, 2017) and SAGE (Hamilton et al., 2017) , on the output of random walks.

Traditional Graph Convolution models operate on the normalized adjacency matrix. We make multiple instantiations of such models, feeding each instantiation a power of the adjacency matrix, and then concatenating the output of all instances into a classification sub-network. Our model, Network of GCNs (and similarly, Network of SAGE), is end-to-end trainable, and is able to directly learn information across near or distant neighbors. We inspect the distribution of parameter weights in our classification sub-network, which reveal to us that our model is effectively able to circumvent adversarial perturbations on the input by shifting weights towards model instances consuming higher powers of the adjacency matrix. For future work, we plan to extend our methods to a stochastic implementation and tackle other (larger) graph datasets.

7. APPENDIX:

7.1 ALGORITHM FOR NETWORK OF SAGE Algorithms 4 and 5, respectively, define SAGE Hamilton et al. (2017) and Network of SAGE (N-SAGE). Algorithm 4 assumes mean-pool aggregation by Hamilton et al. (2017) , which performs on-par to their top performer max-pool aggregation. Further, Algorithm 4 operates in full-batch while Hamilton et al. (2017) offer a stochastic implementation with edge sampling. Nonetheless, their proposed stochastic implementation should be wrapped in a network, though we would need a way to approximate (e.g. sample entries) from dense Âk as k increases. We leave this as future work.

Algorithm 4 SAGE Model (Hamilton et al., 2017) Require: Â is a normalization of A 1: function SAGEMODEL( Â, X, L)

2:

Z ← X 3:

for i = 1 to L do return NETWORK(SAGEMODEL, Â, X, 2)

Using SAGE with mean-pooling aggregation is very similar to a vanilla GCN model but with three differences. First, the choice of adjacency normalization (D -1 A versus D -1 2 AD -1 2 ). Second, the skip connections in line 4, which concatenates the features with the adjacency-multiplied (i.e. diffused) features. We believe this is analogous in intuition of incorporating Â0 in our model, which keeps the original features. Third, the use of node-wise L2 feature normalization at line 5, which is equivalent to applying a layernorm transformation J. Ba (2016) . Nonetheless, it is worth noting Hamilton et al. (2017) 's formulation of SAGE is flexible to allow different aggregations, such as max-pooling or LSTM, which further deviates SAGE from GCN.

Earlier, in Table 2 , we showed the test performance corresponding to the model performing best on the validation split. The number of labeled nodes are small, and such model selection is important to avoid overfitting. For example, there can be up to 10% relative test accuracy difference when training the same model architecture but with different random seed. In this section, we programatically sweep hyperparameters r, K, choice of classification network (∈ {fc, a}), and whether or not we enable Â0 , for both N-GCN and N-SAGE models.

The settings when (K = 1, r = 1, and Â0 disabled), correspond to the vanilla base model. Further, the settings when (K = 1, r > 1, and Â0 disabled), correspond to an ensemble of the base model. These cases are outperformed when K > 1, showing that unmodified random walks indeed help these convolutional methods perform better, by gathering information from nearby and distant nodes.

The automatically generated tables are shown below: 

K = 1 K = 2 K = 3 K = 4 K = 5

:

with added self-connections added as Aii = 1, similar toKipf & Welling (2017)

Figures and Tables:

t-SNE visualization of fully-connected (fc) hidden layer of NGCN when trained over Cora graph.

Figure 2: Sensitivity Analysis. Model performance when varying random walk steps K and replication factor r. Best viewed with zoom. Overall, model performance increases with larger values of K and r. In addition, having random walk steps (larger K) boosts performance more than increasing model capacity (larger r), as seen by the cross-section cuts on along the K-axis versus the r-axis.

Figure 3: Classification accuracy for the Cora dataset with 20 labeled nodes per class (|V| = 20×C),but features removed at random, averaging 10 runs. We use a different random seed for every run (i.e. removing different features per node), but the same 10 random seeds across models.

r = 1 79.0 ± 0.163 79.5 ± 0.100 79.3 ± 0.372 79.4 ± 0.234 79.4 ± 0.337 r = 2 79.1 ± 0.283 79.3 ± 0.241 79.4 ± 0.134 79.4 ± 0.146 79.4 ± 0.160 r = 4 78.9 ± 0.181 79.4 ± 0.161 79.3 ± 0.163 79.5 ± 0.302 79.5 ± 0.227Table 4: N-GCN a results on Citeseer dataset, with Â0 disabled. Top-left entry corresponds to vanilla GCN. Left column corresponds to ensemble of GCN models.

, Dataset used for experiments. For citation datasets, 20 training nodes per class are observed, with |V L | = 20 × C

Table content: <table><tr><td>Dataset</td><td>Type</td><td>Nodes</td><td>Edges</td><td>Classes</td><td colspan="2">Features Labeled nodes</td></tr><tr><td/><td/><td>|V|</td><td>|E|</td><td>C</td><td>F</td><td>|V L |</td></tr><tr><td colspan="2">Citeseer citaction</td><td>3,327</td><td>4,732</td><td>6 (single class)</td><td>3,703</td><td>120</td></tr><tr><td>Cora</td><td>citaction</td><td>2,708</td><td>5,429</td><td>7 (single class)</td><td>1,433</td><td>140</td></tr><tr><td colspan="4">Pubmed citaction 19,717 44,338</td><td>3 (single class)</td><td>500</td><td>60</td></tr><tr><td>PPI</td><td colspan="4">biological 56,944 818,716 121 (multi-class)</td><td>50</td><td>44,906</td></tr><tr><td/><td>Method</td><td/><td/><td colspan="3">Citeseer Cora Pubmed PPI</td></tr><tr><td colspan="2">(a) ManiReg</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2018):
 The paper proposes a novel graph convolutional network in which a variety of random walk steps are involved with multiple GCNs. The basic idea, introducing long rage dependecy, would be interesting. Robustness for the feature remove is also interesting. The validation set would be important for the proposed method, but for creating larger validation set, labeled training set would become small. How the good balance of training-and-validation can be determined? Discussing choice of the degree would be informative. In introducing many degrees (GCNs) for small labeled nodes semi-supervised setting seems to cause over-fitting.