Despite the impressive success of graph convolutional networks (GCNs) on numerous applications, training on large-scale sparse networks remains challenging. Current algorithms require large memory space for storing GCN outputs as well as all the intermediate embeddings. Besides, most of these algorithms involves either random sampling or an approximation of the adjacency matrix, which might unfortunately lose important structure information. In this paper, we propose Chordal-GCN for semi-supervised node classification. The proposed model utilizes the exact graph structure (i.e., without sampling or approximation), while requires limited memory resources compared with the original GCN. Moreover, it leverages the sparsity pattern as well as the clustering structure of the graph. The proposed model first decomposes a large-scale sparse network into several small dense subgraphs (called cliques), and constructs a clique tree. By traversing the tree, GCN training is performed clique by clique, and connections between cliques are exploited via the tree hierachy. Furthermore, we implement Chordal-GCN on large-scale datasets and demonstrate superior performance.
This paper leverages the clique tree decomposition of the graph and design a new variant of GCN which does graph convolution on each clique and penalize the inconsistent prediction made on separators of each node and its children. Experiments on citation networks and the reddit network show that the proposed method is efficient.
Overall, this paper could be a significant contribution on improving GCN, with the caveat for some clarifications on the model and experiments. Given these clarifications in an author response, I would be willing to increase the score.
Pros:
1, I like the idea of exploiting graph decomposition. In my opinion, it may not only improve the scalability but also help the model learn representations which better capture the structure or speed up the learning process. It would be great if authors could show some evidence along this line.
2, The examples in Figure 2 and 3 are very helpful in understanding the concepts related to the clique tree decomposition.
3, The summarization of time and memory complexity is very helpful in comparing different models. 
4, I read the detailed questions and responses in the open review. It helps me understand more details about the experiments. Besides the typo of Table 2, I tend to believe that the experimental setup is reasonable and results are convincing although I did not run the code by myself. 
Cons & Questions:
1, The main motivation of exploiting the graph decomposition is to save memory such that GCN could be applied to large scale graphs without sacrificing the structural information. However, the scale of the largest experiments is still less impressive. To strengthen the paper, it would be great to try larger graph datasets which have been used in the literature.
2, I am confused by the writing on the final prediction made by the model. In particular, do you only keep the prediction of residual or do you average the predictions on the separators? It may be interesting to explore different ways of making predictions based on this decomposition based inference. In general, it would be great to separate the writing of loss (learning) and prediction (inference).
3, Why does Chordal-GCN take significant more epochs than GCN on Reddit and less epochs on all other datasets?
Suggestion:
1, I think the clique tree is very similar if not the same with the junction tree given the node ordering (see section 2.5.2 of [1]). It would be great to discuss the relationship between your chordal graph representation and the tree decomposition used by the probabilistic inference algorithms of graphical models. From the perspective of complexity, the junction tree method and yours both highly depend on the tree-width. Also, linking to probabilistic inference could help better motivate the method since tree-based inference algorithm is shown to converge faster in the literature.
2, It would be great to discuss and or compare with [2] as it uses graph partition algorithms to get clusters and apply GNN with a propagation schedule which alternates between within-cluster and between-cluster. It is closely related to the chordal-GCN as it uses the decomposition of graph clustering directly rather than the clique tree. Decomposition like multiple overlapping spanning trees are also studied in [2].
[1] Wainwright, M.J. and Jordan, M.I., 2008. Graphical models, exponential families, and variational inference. Foundations and Trends® in Machine Learning, 1(1–2), pp.1-305.
[2] Liao, R., Brockschmidt, M., Tarlow, D., Gaunt, A.L., Urtasun, R. and Zemel, R., 2018. Graph partition neural networks for semi-supervised classification. arXiv preprint arXiv:1803.06272.
======================================================================================================
Thank authors for the thorough reply! After I read authors' rebuttal and other reviewers' comments, I would like to keep my original rating. Again, I like this idea and believe better exploiting structure in the propagation could improve the inference in many ways. I hope authors could keep improving it, e.g., better motivating the proposed method (memory saving is just one angle which sometimes may need more engineering work to fully verify) and change the experiments accordingly.