Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors describe a hierarchical strategy for storing large batches of GNN training data in multiple levels of memory in a single system. By partitioning the storage of GNN training data between the extremely large out-of-core disk, smaller but faster CPU DRAM main memory, and much more limited but fastest GPU DRAM memory they are able to train GNNs on graphs that are far too large to fit into either GPU or CPU DRAM memory much faster than naive strategies. To achieve this the authors compare and contrast the training accuracy vs performance tradeoff of their approach vs the traditional neighbor sampling strategy used by default in DGL. A detailed strategy for detailing the high variability in the degree of nodes in a given graph is also given and the authors propose a decomposition of the cache into dynamic and static components to keep the highest utilized nodes throughout the training process in fast memory. An ablation study shows the utility of their approach and the impact on both training accuracy and speed.
strength_and_weaknesses: Strengths
-------------------
- The experiments support the author's motivation to provide a static cache for a small number of highly connected nodes and re-using nodes within a mega-batch while loading additional nodes from disk during training.
- Ablation studies provide extensive data regarding the tradeoffs between the accuracy and performance of the different approaches.
- As the graphs of interest for GNN training continue to increase in size it will be of imperative importance to make effective use of the memory hierarchy of the entire system. As demonstrated in Section 4.2 the authors are able to train extremely large graphs using a fraction of the DRAM memory and incurring a moderate amount of degradation in performance.

Weaknesses
-------------------
- The major weakness is the lack of theoretical motivation to support the training scenario the authors describe in section 3.3. However, the authors acknowledge this weakness openly in the paper and pose it as an interesting area for future work.
- Though the ablation studies were beneficial to support the author's claims regarding the use of a static cache to store the nodes with the largest degrees it may have been more straightforward to use a typical metric for cache effectiveness, such as hit-rate per minibatch.
- The proposed scheme introduces yet another set of hyperparameters that much be tuned per input graph to yield the best results in terms of performance and accuracy, as illustrated in Figure 5.
- The costs and impact of different graph partitioning strategies are not provided (ie Metis partitions may be of low quality depending on a number of factors, would that have any notable impact on the accuracy of the results?).
clarity,_quality,_novelty_and_reproducibility: The writing is reasonably clear and provides a clear distinction regarding the problem, motivation, and novelty of the proposed solution. The experiments represent reasonable evidence to support the claims made by the authors. I believe the results could be reproduced based on the information provided in the text.
summary_of_the_review: Overall the paper addresses an important issue regarding the training of large graphs on machines with limited memory. The authors present a strategy to mitigate the limitations associated with training large GNNs and yield a training procedure that effectively utilizes the hierarchy of multiple memory systems of different capacities and performance characteristics. Though the authors mention the need to minimize the graph cut metric in Section 3.1, was Metis the easiest choice or the best? Also, in Section 3.1 the authors mention an out-of-core partitioner was used when the graph exceeded the memory capacity, please add a reference. It may be worth considering a simpler way to motivate the utility of the static cache size in terms of the hit rate over an epoch or similar metric of typical interest for studying the utility of caches. More information regarding the graph partitioning hyperparameters is provided in the Appendix, Section C.3, were the number of partitions chosen based only on memory considerations? It would be useful if the comment in section 3.1 regarding partitions that are too large or small could be supported by data.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In order to train GNN efficiently on large graphs with a single machine and external storage, this paper proposes a locality-aware training scheme to reduce the data movement time. First, it partitions the graph using METIS. The main idea is to save a mega-batch, which is randomly sampled from partitions in the main memory, and construct mini-batches from the mega-batch. To alleviate the performance from insufficient neighbors in mega-batch, it permanently saves nodes with the highest degree. Reusing each mega-batch several times and pipelining further reduces the total training time.
strength_and_weaknesses: ## Strength:  
The experiments show up to 20 times speedup than in-memory DGL on several large graphs. The analysis of hyper-parameters is in detail.

## Weakness:
1. My main concern is the convergence of the training because both static cache and reuse of mega-batch can change the sampling distribution of nodes. 
2. I guess the performance including speedup and accuracy is also highly dependent on the parameters, such as mega-batch size and reuse times. Do you need to tune these parameters?

## Questions:
1. Table 5 provides the partitions (N_d) in mega-batch for each dataset, but I’m not sure how the authors decide it. I think there is a trade-off between accuracy and data loading time when using different N_d.
2. How many mega-batches are in the main memory? I assume the number is two so that the main memory can read the next mega-batch from external memory and construct minibatches at the same time. 
clarity,_quality,_novelty_and_reproducibility: The paper is well written. The idea is not particularly novel. 
summary_of_the_review: Reducing the data movement of GNN training on CPU-GPU nodes has been extensively studied recently. The paper proposes a straightforward technique.  However, it is unclear whether the technique can be applied to more general GNN tasks.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes HierBatching, a framework that conducts out-of-core training for GNNs on giant data on small main memory. HierBatching organizes the graph into closely connected partitions and loads some partitions to main memory to conduct training for locality. The nodes with the largest degrees are cached in main memory as they are accessed frequently. Pipelining is used to overlap disk read and computation. Experiment results show that HierBatching runs significantly faster than a naïve solution that directly reads disk.
strength_and_weaknesses: Strengths

1. Training GNNs on giant data is important, and out-of-core training is interesting as it makes training more accessible for practitioners.
2. The paper is well-written with excellent clarity and logic flow.
3. The codes are open-source


Weakness
1. The novelties of the proposed techniques are limited. Partitioning a graph into strongly connected clusters is a standard method to achieve spatial locality in graph processing, DistDGL also uses it for the distributed training of GNNs. Caching hot nodes in has been used by [a, b] to handle limited GPU memory. Moreover, overlapping computation and IO is a common technique in system design.

2. HierBatching incurs accuracy loss, which may not be acceptable for some critical scenarios (e.g., recommendation, where marginal accuracy improvement translates into large revenue). 

3. The experiments can be improved. Figure 4 shows that HierBatching uses over 50% of the time for disk IO, which makes me wonder whether training with HierBatching is cheaper than using distributed in-memory solutions such as DistDGL. Note that DistDGL already conducts locality-aware graph partitioning, which reduces cross-machine communication. By using less time for IO, DistDGL may be cheaper than HierBatching is we purchase instances from AWS. Another interesting experiment is to show how the accuracy and training time of HierBatching changes with the amount of main memory. 

[a] https://arxiv.org/pdf/2111.05894.pdf
[b] https://dl.acm.org/do/10.5281/zenodo.6347456/full/

clarity,_quality,_novelty_and_reproducibility: Clarity excellent
Quality moderate
Novelty low
Reproducibility excellent
summary_of_the_review: I like that the paper tackles an important problem and conducts solid engineering. However, the utilized techniques are well-know and have limited novelty.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Proposes an out-of-core training approach for message-passing GNNs on very large graphs. Key idea is to partition the nodes + their features on disk, load a few partitions into memory, and then build batches on the subgraph induced by the currently loaded nodes as well as the most frequent nodes, and repeat. Also reports on a small experimental study.

strength_and_weaknesses: Strengths:

S1. Can handle large graphs

S2. I/O mostly sequential and interleaved with communication

S3. Seems to provide reasonable results in study

Weaknesses:

W1. Novelty unclear; related work cited but otherwise ignored

W2. Simplistic & purely heuristic, no analysis

W3. Results far from SOTA

W4. Experimental study setup shaky

Details:

On W1. The most relevant related work to this work is MariusGNN (cited here as Marius++). There is no discussion of how this work relates to MariusGNN, both technically and empirically. This is not acceptable. In fact, MariusGNN seems to use a more refined approach and perform experiments on (partly) larger graphs, smaller machines, with faster speed ups. (I coincidentally found a very short paragraph on Marius++ in the appendix after writing this review. I consider this discussion insufficient.)

On W2. The method proposed here is rather simplistic; e.g., is does not consider to exchange loaded partitions individually, but only all at once. More generally, the entire approach is driven by heuristics, but there is no analysis that justifies the approach. There is also no discussion of what could go wrong.

On W3. The test accuracies reported in Tab. 2 seem to be far away from SOTA. E.g., for ogbn-papers100M, this paper gives a test accuracy of 0.65 with SAGE. The OGB leaderboard lists an accuracy of .78 with GraphSAGE and goes up to >.85 in all of the top-10 approaches.

On W4. The experimental setup uses machines with more memory than used by the proposed methods. For evaluating out-of-core methods, this is not good: this memory may be used as a disk cache by the OS, for example.

clarity,_quality,_novelty_and_reproducibility: The exposition is clear, but unnecessarily wordy and overly formal (e.g., Alg 1 is not needed). This approach is simple and can be described much more concisely.

Novelty is unclear, see above.

Reproducibility is somewhat unclear, since details about the proposed methods are missing (e.g., how many partitions are used). This point can be addressed if the authors make the implementation available, though.

summary_of_the_review: Potentially useful approach, but falls short on novelty, comparison to related work, analysis, and quality of results. I recommend to reject this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a memory hierarchy aware batching scheme to efficiently train large graph neural network on modest compute resources which may not have very large main memory. The paper proposed a variety of useful heuristics and provide good experimental comparisons to demonstrate speedups. 

However, in the context of existing works the ideas presented are a combination of existing known ideas and follows from several recent lines of work. For example using graph reordering so that memory accesses are contiguous can significantly enhance graph traversal minimizing cache misses  was discussed in recent NeurIPS 2022 paper  "Graph Reordering for Cache-Efficient Near Neighbor Search". 



 


 
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Reject