Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes locality-based mini batching (LBMB), a method for extracting batches for GNN training. LBMB aims to reduce the computation cost of GNN training by treating primary (output) nodes and auxiliary nodes separately.  LBMB can be used for both training and inference, and speeds up both tasks substantially while maintaining comparable accuracy.
main_review: This paper proposes LBMB, a scalable and effective method for extracting mini batches (subgraphs) by primary node partitioning, followed by auxiliary node selection. This method can be applied to both training and inference, which is a strength of this work. Evaluation demonstrates that LBMB spends much less epoch time for training than existing methods, while maintaining comparable accuracy. Inference also shows significant speedups than existing methods (especially than those using the full graph). However, I still have several concerns/questions about this proposal as follows:

* *Methodology* - While the mini-batch precomputation is the major source of performance gains in LBMB, I am wondering how many sub-processes the authors used for runtime sampling (i.e., *num_workers* in PyTorch). I am asking because a runtime sampling method can often be fully pipelined with GNN computation if a sufficient number of sub-processes are used [R1][R2].

* *Space Overhead* - This work leverages space-time tradeoffs in extracting mini-batches via precomputation. That said, I am curious about the *space (memory) overhead* incurred by the proposed mini-batch precomputation.

* *Cost of Preprocessing* - The preprocessing time seems to be substantially higher than other schemes. The authors argue that the preprocessing is one-time cost, but this overhead can be compounded by hyperparameter tuning for LBMB such as the number auxiliary nodes per primiary node, batch size, and so on. Furthermore, the proposed preprocessing approach seems not feasible to am *inductive* setting where the GNN should deal with unseen data.

* *Applicability of Preprocessing* - Can the preprocessing idea be applied to the other mini batching methods for GNNs such as node-wise and layer-wise sampling methods?


[R1] Dong et al., Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs, KDD'21

[R2] Min et al., Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture, VLDB'21


summary_of_the_review: This paper proposes a scalable and effective method for extracting mini batches (subgraphs), which can be applied to both training and inference of GNNs. However, I still have several major issues/questions about this work, and would ask the authors to address them in their rebuttal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper addresses the task of training graph neural networks on large graphs. The authors propose a strategy to extract mini-batches that are locally connected. The technique involves dividing nodes into primary and auxiliary nodes, where the primary nodes are those for which an prediction is formed during the batch (usually training nodes). The auxiliary nodes are used for computation of the predictions. The authors propose two procedures for selecting the primary nodes in a minibatch. One uses distance-based partitioning (a greedy procedure building on personalized page rank as a distance measure). The other applies graph partitioning (METIS). After the primary nodes have been partitioned, auxiliary nodes are selected using local clustering techniques (a form of topic-sensitive PageRank is employed). The authors observe that this construction of mini-batches is also useful in the inference process. The paper proposes methods to mitigate the effect of the introduction of correlation in the gradients that arises due to the proximity-based partitioning. There are also strategies to prevent the optimizer from processing consecutive batches that are very similar. 

The paper provides experimental results for GAT and GCN for four large graph datasets, with a comparison to four baselines.  The results provide evidence that the proposed strategy leads to a significant reduction in training time and also has a major benefit during inference. The authors the impact of training set size and conduct an ablation study to verify that all proposed aspects of the proposed method yield performance improvement. 

main_review: Strengths of the paper

1. The paper proposes a novel approach to deriving minibatches for training graph neural networks.
2. The experiments indicate that the proposed technique achieves a significant reduction in training time and dramatically improves the inference time. The experiments appear to have been executed with care.
3. The ablation study and analysis of training set size provide useful insight into the behaviour of the algorithm. 

Weaknesses of the paper
1. The envisioned learning pipeline could be better articulated to make the trade-offs clearer in terms of time required for pre-processing and training time (number of epochs, time per epoch).  Related to this are concerns about how hyperparameter tuning factors into an assessment of the practical training time.
2. The procedure is novel, but Cluster-GCN already proposed the partitioning of the graph as part of the sampling process, so the contribution represents 
3. The proposed technique is heuristic, with existing techniques being selected and combined. The derivation of the overall algorithm is thus not based on a principled procedure. 
 
4. The experiments report results for only one choice of batch size. The batch size has a major impact on the performance of the sampling algorithms (both in terms of accuracy and convergence time), so it is important to explore a range of choices. The procedure for selecting the hyperparameters for the baselines is not entirely clear 

5. The experiments are only conducted for GAT and GCN. While these may be considered to be representative of many GNNs, they are no longer state-of-the-art. It is not entirely clear that the results will carry over to more recent methods that achieve considerably better performance for the addressed learning tasks. 

Recommendation and major reasons for the recommendation

I have recommended a “marginally below the acceptance threshold”. 

I think the core idea is clever and the authors have exhibited considerable skill in constructing the overall algorithm. On the other hand, there are several concerns that prevent me from recommending that the paper be accepted. 

(1) Novelty & heuristic nature: While I do acknowledge the novelty of the technique, the approach is strongly related to Cluster-GCN, and although the proposed method does represent a clear improvement over that approach, this does limit the novelty of the contribution. The technique is heuristic in nature, and is not developed based on a principled foundation. There is no theoretical characterization of the proposed method.  The results are reported for specific choices of local clustering and graph partitioning, so it’s not entirely clear whether the performance is strongly dependent on these selected methods (having said this, the paper does explore two different types of partitioning, and both yield similar performance, so this points in the direction of the technique performing satisfactorily for any reasonable graph partitioning strategy).  

(2) Application in practice and nature of the trade-off: It would be very helpful if the paper better articulated how the method would be applied in practice. In addition to the depicted training time, there is a hidden cost of determining hyperparameters that involves a grid search. The proposed method appears to introduce more hyperparameters than some of the other approaches. Moreover, the selected hyperparameters change from dataset to dataset, suggesting that the hyperparameter selection procedure needs to be performed for every dataset (although perhaps Table 6 hints that this is not the case). It then becomes questionable how valuable it is to reduce the training time for a dataset, since it would form only a small portion of the overall training overhead. 

The paper states in Section 3.3 that “a machine learning model is trained only once”, but later makes the argument that the pre-processing overhead involved in constructing the partitions is a one-time overhead compared to the training cost. If the model is only trained once, then is it fair to exclude the pre-processing time from the plots in Figure 1?

(3) Experimental procedure: The authors report that a grid search was conducted to find suitable parameters such that there was a similar memory usage, similar number of iterations per epoch, and maximum validation accuracy. Since there seem to be competing criteria and the ranges of the hyperparameter tuning process are not provided, it is difficult to understand exactly how the hyperparameters were selected. 

The performance when training on large graphs tends to be quite sensitive to batch size. It would be much better if results could be included for multiple batch sizes. At the least, it should be clear which range of batch sizes was selected for the hyperparameter tuning process. 

Questions

(1) GAT and GCN, while representative of many graph models, are not the state-of-the-art for many learning tasks. Is it clear that the results provided in the paper are likely to generalize to other GNN models? If so, why? 

(2) If possible, please provide a clarification of the hyperparameter tuning process, particularly for the baselines. 

(3) Please clarify the intended use of the approach (how would it be incorporated in a machine learning pipeline in a practical application). How long does hyperparameter tuning take relative to training time? If it takes as long or longer, is this an important consideration, or is it reasonable to focus entirely on training time? Is there an example scenario where training would be repeated multiple times without a requirement for re-tuning the hyperparameters. Is it clear that the pre-processing time should be excluded when comparing two methods?

summary_of_the_review: ** After modifications and discussion, I have increased the score to "marginally above the acceptance threshold".

The recommendation of the review is “marginally below the acceptance threshold”. 

The paper is considered to propose sufficiently novel techniques, although aspects of the approach are similar to prior work. The impact of the paper may be somewhat limited because of the heuristic nature of the proposed methodology. 

The paper introduces an increased pre-processing overhead in order to achieve a speed-up in training time. Although the pre-processing time is reported in tables, it is excluded in the figures that compare the overall train times. There appears to be a need for considerable hyperparameter tuning. This process, conducted via grid search, might take considerably longer than the actual reported training.

Although the experiments appear to have been conducted thoroughly, results are reported for only one set of hyperparameters. The selection process of these for the baselines is not particularly clear.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the training of graph neural networks and proposes a mini batching scheme that circumvents the expensive cost of traditional sampling approaches due to random memory access. The authors construct deterministic mini batches so that they can be laid out in consecutive memory, which speeds up training. The authors empirically show that such a mini batching scheme significantly improves training and inference time, at the cost of precomputation.
main_review: This work studies an important question that plagues the training and inference of graph neural networks in a large scale. Random memory access is not necessarily the root cause that prevents faster training, but indeed the extra cost to reorganize batch data into consecutive memory is an anchor of improvement. The authors precompute the batches and shift the burden from training to preprocessing; this is an interesting idea to explore.

Major issues:

Although generally it is argued that preprocessing is done only once and sounds less important, note that training (and inference) is also done only once for graph neural networks. Hence, a comprehensive study should also compare the total time in preprocessing plus training (possibly including also inference) across different methods. This is lacking in Table 1.

Another concern is the memory cost incurred to store the mini batches. A node may appear in multiple batches, causing multiple times storage increase compared to usual sampling methods. This problem is more pronounced when the training set is large (causing more overlaps among the batches). Certain analysis would be desirable.

A lot of technical details developed in the paper (such the the partitioning approaches and the approaches to selecting auxiliary nodes) follow straight intuition. The authors provide no theoretical analysis/support and they do not even prefer an approach, when multiple choices are equally plausible. This renders the paper rather empirical. Then, strong experiment results are needed to give a reader confidence to adopt the proposed techniques. However, the current empirical results are not sufficiently strong. For example, Table 1 does not appear to suggest an exclusively advantageous method. Moreover, the experiment section can be stronger if results of more networks (e.g., GraphSAGE and GIN) are demonstrated.

An important problem is that deterministic batches go entirely outside the realm of stochastic optimization, while also not being applicable to a usual deterministic optimization that requires the full gradient. Convergence and convergence rates are unclear and obviously the authors also face irregularities (such as "downward spikes" mentioned in Section 4). More in-depth study, from either the theoretical side or the empirical side, is needed to solidify the proposed work.

Minor issues/questions:

At the beginning of section 3, it is mentioned that the first step of LBMB obtains the $k$ most important auxiliary nodes for each primary node. However, section 3.1 discusses partitioning without the use of these auxiliary nodes. Could the authors clarify?

In table 1, preprocessing time for the papers100M data set is missing.

In table 1, is the inference time using "same method" or "full graph"?

Table 1 can benefit from also reporting the number of training epochs to reach the test accuracy listed thereof.

---

After rebuttal

The authors made good arguments regarding my initial concerns on expensive preprocessing time and costly memory consumption. I therefore adjust the score. There remain concerns regarding too many options (none preferred) in the proposed method and the unclear impact on training convergence. The idea by itself is illuminating and with polish and prudence in use, it may lead to a leap in the training of GNNs in a large scale.
summary_of_the_review: This paper studies an important question. The proposed method, however, has multiple issues including timing, storage, convergence, and insufficient empirical evidence.
review_title: null

Meta-review: The paper suggests a non-random strategy for selecting minibatches of nodes for training graph neural networks. The main argument is that consecutive memory accesses are faster than random accesses, and thus they claim a 20x speedup per epoch by precomputing batches at a small cost to accuracy. 

There are a number of discussion points. One reviewer finds the results hard to believe because previous work has shown that runtime sampling can be fully pipelined. The authors agree but say their speedups are still better, which isn’t a fully satisfying response, and it calls into question the quality of the baseline implementation. Another concern is about the effect of deterministic minibatches. The authors argue that the empirical results speak for themselves, while the reviewer worries about robustness. There also are some concerns about methodology around hyperparameters and special-casing of preprocessing for one dataset, though those appear mostly resolved.

On the whole, this is a borderline paper that lands just on the side of rejection. I’d encourage the authors to more thoroughly address the questions about quality of the baseline implementation and the reviewer’s concern about robustness of deterministic minibatches, and then resubmit to the next conference.
Decision: Reject