Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The authors propose Chordal-GCN which is based on the chordal decomposition method post-ordered clique tree and propagates the features based on the order within each subgraph in order to reduce memory usage. The authors show that Chordal-GCN outperforms GCN [1] on all four datasets and argue that Chordal-GCN reduces memory usage.
The idea of using Chordal graphs to GCN is novel and interesting. However, my main concern lies in the experiment results.

1) To my best knowledge, the proposed Chordal- match SOTA results on Cora, Citeceer, and Pubmed. However, since these datasets are small and easy to run, I would like to see the mean and standard deviation of the accuracy of all models you ran. Can you also provide the results of the commonly used "random split setting"[1]?

2) What is the epoch time of the Chordal-GCN? Can you also report it in Table 2? Without including the pre-processing time, we don't know the overall training time of the method.

3) Given that the main concern is the memory usage, the authors should compare to a strong baseline, SGC [2], which is a linear classifier trained on top of propagated features with memory/space complexity O(d) when using mini-batch training. This is much smaller than the proposed method O(Lc_2d + Ld^2).
Also, SGC is at least two magnitudes faster to train (2.7s vs 0.987*410=367.8s + unknown pre-processing time) and more accurate (94.9 vs 94.2) than the proposed Chordal-GCN on the largest Reddit dataset. The authors emphasize that the proposed method is scalable. Please compare it to SGC in Table 2. 
Nevertheless, there is some chance that the authors can apply the same method to SGC and speed it up further as long as the preprocessing time is relatively small.

4) Based on Table 2, Cluster-GCN uses less memory and is more accurate and faster to train than Chordal-GCN. Can you justify why people should use the proposed method instead?

5) There are some missing citations. These papers [3,4,5,6] achieved previous SOTA results and should be included in the Tables. 

References:
[1] Kipf and Welling: Semi-Supervised Classification with Graph Convolutional Networks (ICLR 2017)
[2] Wu et al.: Simplifying Graph Convolutional Networks (ICML 2019)
[3] Klicpera et al.: Predict then Propagate: Graph Neural Networks meet Personalized PageRank (ICLR 2019)
[4] Gao and Ji: Graph U-Nets (ICML 2019)
[5] Zhang et al.: GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs (UAI 2018) 
[6] Fey: Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks (ICLR-W 2019)
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.
review_title: Official Blind Review #1

final_score: rating: 1: Reject
review_content: In this paper, the authors propose a new method referred to Chordal-GCN to optimize memory usage in large graphs. The authors borrow the ideas from Chordal Sparsity theory to first build a client tree. Then mini-batch updates are carried out individually on each clique from the leaves following the GCN loss. The authors add an additional consistency loss between shared node with children cliques. Experiments are carried out in four networks with comparison to several baselines.

Strength:
1. The authors study an interesting and important problem to reduce memory usage for GCN in large-scale graphs. The usage of chordal sparsity is interesting and innovative.
2. The authors carry out ablation study on the consistency loss components in the algorithm.

Weakness:
1. One major concern is that the reduction in memory usage is not large enough to justify the huge increment in running-time. For example, on Cora dataset, the memory is reduced by 4x while the running time is 16x compared to vanilla GCN.
2. It is not clear why Chordal-GCN can achieve better accuracy compared to vanilla GCN. Since Chordal-GCN serves as approximation for GCN as the authors claim that using entire graph will provide better accuracy. As a result, the vanilla GCN is expected to achieve better accuracy. It would be better if the authors could provide more intuition and explanations.
3. The evaluation does not take the graph preprocessing into consideration. The authors should report the time and memory taken to carry out the preprocessing steps as well.
4. For most real-world large-scale industry networks, it is hard to fit the graph into memory. Though the GCN training part could run in distributed way, it is not clear how to efficiently build the clique tree in similar method.
5. Given the main purpose of the algorithm is to reduce memory usage for large-scale networks, it is expected to see experiments on larger graphs where the large memory footprint becomes a real issue.

Detailed comments:
1. The description in Section 2.2 is not very clear. It would be better if the authors could provide a more detailed introduction to clique tree and the algorithms used.
2. For the Chordal-GCN in algorithm 1, for epoch 2 onwards, do we also add consistent-loss when training leaves as well?

review_title: Official Blind Review #2

Meta-review: The submission is proposed a rejection based on majority review.
Decision: Reject