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. 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, BID19 .Convolutional Neural Networks BID16 learn location-invariant hierarchical filters, enabling significant improvements on Computer Vision tasks BID15 BID23 BID12 . This success has motivated researchers BID7 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 FIG2 , our model for semi-supervised node classification builds on the GCN module proposed by BID14 , which operates on the normalized adjacency matrixÂ, as in GCN(Â), whereÂ = D , 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. BID22 BID9 BID1 . 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, 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. In this paper, we propose a meta-model that can run arbitrary Graph Convolution models, such as GCN BID14 and SAGE BID10 , 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.
We make a network of Graph Convolution Networks, feeding each a different power of the adjacency matrix, combining all their representation into a classification sub-network, achieving state-of-the-art on semi-supervised node classification. Proposes a new network of GCNs with two approaches: a fully connected layer on top of stacked features and attention mechanism that uses scalar weight per GCN. Presents a Network of Graph Convolutional Networks that uses random walk statistics to extract information from near and distant neighbors in the graph