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.
In this work a new network of GCNs is proposed. Different GCNs utilize different powers of the transition matrix to capture varying neighborhoods in a graph. As an aggregation mechanism of the GCN modules two approaches are considered: a fully connected layer on top of stacked features and attention mechanism that uses a scalar weight per GCN. The later allows for better interpretability of the effects of varying degree of neighborhoods in a graph.
Proposed approach, as authors noted themselves, is quite similar to DCNN (Atwood and Towsley, 2016) and becomes equivalent if the combined GCNs have one layer each. While comparison to vanilla GCN is quite extensive, there is no comparison to DCNN at all. I would be curious to see at least portion of the experiments of the DCNN paper with the proposed approach, where the importance of number of GCN layers is addressed. DCNN did well on Cora and Pubmed when more training samples were used. It also was tested on graph classification datasets, but the results were not as good for some of the datasets. I think that comparison to DCNN is important to justify the importance of using multilayer GCN modules.
Some questions and concerns:
- I could not quite figure out how many layers did each GCN have in the experiments and how impactful is this parameter 
- Why is it necessary to replicate GCNs for each of the transition matrix powers? In section 4.3 it is mentioned that replication factors r = 1 and r = 4 were used, but it is not clear from Table 2 what are the results for respective r.
- Early stopping implementation seems a bit too intense. "We invoke many runs over all datasets" - how many? Mean and standard deviation are reported for top 3 performers, which is not enough to get a sense of standard deviation and mean. Kipf and Welling (2017) report results over 100 runs without selecting top performers if I understood correctly their setup. Could you please report mean and standard deviation of all the runs? Given relatively small performance improvement (comparatively to GCN), more than 3 (selected) runs are needed for comparison.
- I liked the attention idea and its interpretation in Fig. 2. Could you please add the error bars for the attention weights. It is interesting to see them shifting towards higher powers of the transition matrix, but also it is important to know if this phenomena is statistically significant.
- Following up on the previous item - did you try not including self connections when computing transition matrix powers? This way the effect of different degrees of neighborhoods in a graph could be understood better. When self-connections are present, each subsequent transition matrix power contains neighborhoods of lower degrees and interpretation becomes not as apparent.
Minor comments:
- Understanding of this paper quite heavily relies on the reader knowing Kipf and Welling (2017) paper. Particularly, the comment about approximations derived by Kipf and Welling (2017) in Section 3.3 and how directed graph was converted to undirected (Section 4.1) require a bit more details.
- I am not quite sure why Section 2.3 is needed. Connection to graph embeddings is not given much attention in the paper later on (except t-SNE picture).
- Typo in Fig. 1 caption - right and left are mixed up.
- Typo in footnote on page 3.