Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Training GNNs is challenging due to high communication costs or large memory overheads. This paper proposes a communication-efficient distributed GNN training technique named Learn Locally, Correct Globally (LLCG) to periodically model averaging on the server using locally trained models.  It also applies global server corrections to refine the locally learned models and solve the irreducible performance degradation caused by ignoring node dependency. This paper provides the convergence analysis and shows the proposed method can address the residual error. The experimental results show significant improvement compared to existing methods.
main_review: Major comments: 

I am mainly concerned about the novelty of this submission. Local SGD [1] is not very novel in distributional optimization. This submission inserts an additional update on the server to eliminate the sampling error. In my opinion, It is difficult to say that this method was designed specifically for training GNN since one can extend this procedure to any dataset. (This paper argues that training GNN needs this step due to the residual error,  which I will comment on later.) The theoretical results are also not novel. The analysis follows the local sgd method. The only additional condition is the sampling error, which doesn't provide any new insight. 

The motivation regarding the proposed method is not well justified. The main contribution, if any novelty, is the full neighbor updates on the server. Why do local machines use sampled neighbors while the server uses full neighbors? The motivation discussed in the introduction mentioned local devices lack the global graph structure. In my opinion, this setting is more of partitioned graphs rather than sampling. This problem also partially involves my above comment. Since the residual error seems to come from the sampling, the improvement from the update on the server is not exciting.

The experimental results show some improvement, particularly for Reddit.  Besides numbers of communication, the running time is also necessary since the server requires additional updates. Table 1 and Figure 4 mentioned communication cost, which is not clearly defined anywhere in this submission.

[1] Stich, Sebastian U. ``Local SGD converges fast and communicates little." arXiv preprint arXiv:1805.09767 (2018).

Minor comments:

The experiments use neighbor sampling. It is interesting to see the impact of different samplers, e.g. importance sampling.

Typo and grammar mistakes, e.g., ``we theoretically analysis the convergence of our proposal LLCG'' -- > analyze. ``During the correction, the server first construct a mini-batch...'' -- > constructs. ``however, due to space limitations we differ the detailed discussion on these datasets to the Appendix'' -- > perhaps refer? Etc.

summary_of_the_review: This paper applies local SGD to GNN training. The idea is not very novel. The experimental results are promising, but some important points need clarification.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the problem of distributed training for graph learning tasks, under a setting where data privacy is significant for each individual machine and communication to/from a central parameter server is expensive. To preserve privacy each machine has only access to a distinct partition of the overall graph. The central server has access to the full graph. In the LLCG algorithm that the paper proposes, each machine trains on its local graph partition for some time before sending the parameters to the server. The server averages the received parameter, but additionally also does its own training using the full graph available to it. Theoretically the authors show that the proposed method avoids an error gap in the gradient norm that would exist if server correction is not performed. Experimental results show the proposed scheme performing similarly to GGS albeit with much lower communication costs.  
main_review: The paper is well-written and is enjoyable to read. The problem is clearly defined, and the solution steps are thoroughly explained. I do have some concerns, which I hope the authors will address:
- It would help if the GGS algorithm is explained (at least at a high level) in the paper since it figures some prominently in all the experiments. 
- In equation 1, the h update equation seems independent of input features x. 
- Since server correction is claimed to be crucial for performance, it would help if the authors can do an ablation study without server correction. I wonder if this is the same as PSGD-PA since LLCG uses exponential increasing round lengths whereas PSGD-PA does not. 
- Are the graph partitions at the local machines the same for PSGD-PA and LLCG in the experiments? 
- In the server correct step, does it help for the server to carefully choose the minibatch to include more of the cut-edges (i.e., edges that are not considered by the local machines)?
- What is T_global(r) and T_local(r) in Section 4.3?
- In Theorem 2, if T = \sum_{r=1}^R K\rho^r, how can \sum_{r=1}^R K^2 \rho^{2r} be less than O(\sqrt{T})? 
- In figure 4 (and others), the performance is plotted as a function of number of communication rounds. How does performance fare as a function of number of local training steps? 

summary_of_the_review: Well-written paper that considers an important problem and presents a simple, effective solution. There are some concerns however which I hope the authors will address.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper deals with the problem of distributed training of GNNs. Existing methods are either communication-intensive (sampling) or do not achieve good performance (averaging).

The authors propose a novel method, dubbed "LLCG: Learn Locally Correct Globally". Essentially, this method captures the idea of transmitting only local averages but adds a centralized step on the server to account for global structural information lost in the subgraph partition.

The authors further provide theoretical convergence guarantees. They both show that just averaging leads to an insurmountable residual error that explains the poor performance of averaging methods, as well as prove that this residual error disappears when adding the global correction step.
main_review: This paper deals with the problem of distributed training of GNNs. Existing methods are either communication-intensive (sampling) or do not achieve good performance (averaging).

The authors propose a novel method, dubbed "LLCG: Learn Locally Correct Globally". Essentially, this method captures the idea of transmitting only local averages but adds a centralized step on the server to account for global structural information lost in the subgraph partition.

The authors further provide theoretical convergence guarantees. They both show that just averaging leads to an insurmountable residual error that explains the poor performance of averaging methods, as well as prove that this residual error disappears when adding the global correction step.

The paper is fairly well written and the proposed result, albeit simple, is powerful. The theoretical guarantees provided round up the good work. More importantly, the topic is timely and very relevant, and I, therefore, recommend acceptance in the conference, provided they add standard deviation results to Table 1.

Some questions that could further enhance the discussion are as follows:

1) What would happen if all labeled nodes used for training end up in a single server. How long would it take to converge? Would it be affected?

2) Are there any best ways of partitioning the graphs into the servers? How does partitioning affect convergence?

Minor comments:

Beginning of Section 4.3: where it reads 'before processing' it should read 'before proceeding'

The paragraph 'datasets and evaluation metric' refers to six semi-supervised classification datasets and points to Table 2. However, the results are for four datasets and referenced in Table 1, not table 2. I understand that there are more experiments on the supplementary material, but refer to table 1 and just four datasets in this section since that are what is being shown in the main matter of the paper.

Fig 4 f, I understand this should be Proteins, and not Reddit (Reddit is in Fig 4h)
summary_of_the_review: The paper is fairly well written and the proposed result, albeit simple, is powerful. The theoretical guarantees provided round up the good work. More importantly, the topic is timely and very relevant, and I, therefore, recommend acceptance in the conference, provided they add standard deviation results to Table 1.

My assigned score is 7.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a distributed training technique for GNN. This technique includes local computations done in parallel by several machines and a correction phase done by a centralized server. A theoretical analysis is given for this technique, showing that the server correction phase reduces some irreducible error that happens due to splitting the graph and doing a local computation on each subgraph. Several experiments are made on real datasets which show the merits of this technique over previous techniques in terms of performance, communication steps, and size.
main_review: The paper presents an interesting method for distributed training of GNN which can be helpful when training on very large graphs. The paper is well presented and easy to follow. The theoretical analysis is important in my opinion, as it can provide motivation as to why this method is better than previous ones. Specifically, the importance of having a server correction phase. The empirical part is thorough, providing experiments on several datasets. The proposed training technique is being compared to either PSGD-PA which has worse performance, and GGS which has a much higher communication cost.

I have a couple of concerns regarding the theoretical part:

1) Theorem 1 basically shows an upper bound on the average norm of the gradients throughout T iterations. It is unclear why the “irreducible part” of this bound is really irreducible. I believe that if the authors want to prove that the algorithm from Theorem 2 is better than the one in Theorem 1, then they should show a lower bound in Theorem 1, and make a case that this term is really irreducible. 

2) I am not sure if the term discussed in the previous point is really irreducible. Theorem 1 & 2 only shows a bound on the norm of the gradients, averaged over T iterations. If the loss function L is smooth (which may be reasonable), then it would converge eventually to a stationary point. Hence, it is not clear why for a large enough T, this term can be lower bounded by some term independent of T.

3) In Theorems 1 & 2 the authors only show that the loss converges to a stationary point, which may as well be a saddle point or spurious minima. Can the authors elaborate on this? Is there some guarantee on to which point the loss converges to?

As I said, the empirical part is satisfactory in my opinion and shows the benefits of LLCG. It does seem that all the tasks consider node classification, and I wonder how this method would work on edge classification tasks. This may be an important case study since edges can be cut off when splitting the graph into subgraphs.

A few minor issues:

1) The indexing in algorithms 1 & 2 is a bit confusing because there are three loops (global epochs, local machine’s epochs, and server corrections). I think it would be better to use indices for \theta which represent the current global epoch, and either local machine epoch or server correction epoch.

2) Figures 4-7 are very small and hard to read. Due to the page limit constraint, I suggest highlighting fewer figures in the main part and giving the rest of the figures on a larger scale in the appendix.

I note that I’m not an expert in distributed computing, and may have missed some related works or important benchmarks which should have been mentioned.

summary_of_the_review: I think the optimization technique this paper presents is nice. The empirical results are thorough, showing advantages over previous methods. The theoretical part is a bit unclear. specifically, whether Theorem 1 actually shows a lower bound (i.e. is the second term there irreducible).
review_title: null

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period. The current discussions mostly lie on the acceptance side. 

Some prons of the paper include:

- Timely topic: This paper deals with the problem of distributed training of GNNs. 
- New algorithm: this method captures the idea of transmitting only local averages but adds a centralized step on the server to account for global structural information lost in the subgraph partition.
- Theory: The authors further provide theoretical convergence guarantees. 
- Clarity: The paper is fairly well written and the proposed result is simple and powerful. 

The current consensus is that the paper deserves publication.

Best AC
Decision: Accept (Poster)