Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper introduces a novel approach to partition the clients into $K$ groups and build personalized model for each group. The approach leverage graph clustering method for learning purpose. The paper also provided a list of learning bounds. The experimental results demonstrate the proposed $K$ models can produce learning results close to personalized models. 


strengths_and_weaknesses: Strengths: 

1. The problem is interestingly and timely. It can potentially be applied to many applications 
2. The approach is based on graph theoretical results
3. The paper provides rather rigorous theoretical analysis

Weaknesses: 
1. The writing can be improved and better organized
2. Lack of base lines for comparison; the experimental results are rather weak.
3. Some Figures are too small to read (like those in Figure 5) 
questions: 1. Can some greedy approach be applied here? like greedy clustering (merging the most similar pairs, or something along this line)
   
2. Is Lemma 1 essential? What about using other simple/alternative approaches for optimizing modularity (as this is a well studied problem) 
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the collaborative learning in personalized setting, which considers the heterogeneous distribution among clients. The paper proposes a method based on graph partition to learn personalized models for each partition group, which is shared by all clients within one partition group. The paper first provides the generalization bound for each client, from which the optimal personalized model is derived via optimizing on the contribution from the dataset of each client. Then, a contribution graph is constructed from the contribution weight, and similar clients are partitioned into one group. After filtering out bad clients, the personalized model for one group is learned based on the average weights of the clients within the group. The paper provides theoretically analysis on the increase of the upper bound of the excess risk due to the relaxation from optimal personalized model to group personalized model. Experiments demonstrate the group personalized model has similar performance with the optimal personalized model and justifies the proposed method.  

strengths_and_weaknesses: This paper has several merits. First, the theoretical part is clear, rigorous, and sound. It justifies the effectiveness of the proposed framework. Second, the proposed method, which is based on graph partition of client contribution, is novel and interesting to me. 
 
However, I am not very familiar with this research topic. My major concern is on the writing of this paper, as it is sometimes hard to follow. For example, there are no subsections within Section 4 "Our Work", but to my understanding this section first talks about the optimal model, then provides graph partition based learning algorithm, and last gives tighter bounds with further assumptions. Thus, I think section4 can be separated into at least 3 subsections. The authors are encouraged to improve the presentation of this work. I have some more questions to ask the authors. Please see the comment below.

questions: 1.One crucial step is to calculate the IPM between different data distributions. It is estimated by Eq 8, which involves the JS divergence between two data distributions. So how do you calculate the JS divergence between two datasets of clients.

2.It seems that model training of one group needs the datasets from all clients. Does that mean clients need to transfer their local datasets? It seems that if sharing gradients, each client is required to keep all models of all groups and calculate gradients K(number of groups) times. 



limitations: The paper does not discuss limitations of the work. It provides the discussion on social impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studied collaborative learning for heterogeneous clients. To achieve personalization while avoiding training personalized models for a large number of clients, the authors proposed methods to detect collaboration partners and adaptively learn models for client groups. The authors provide a theoretical guarantee that the expected risk of the learned group model is close to the personalized model. Empirical results on real-world datasets validated the theoretical result showing group model is a good approximation of the personalized model.
strengths_and_weaknesses: Strength:
The motivation of learning models for client clusters to balance between computation and personalization is intuitive. The two algorithms, ACLMM which applies Modularity Maximization to estimate client group, and ACLC which assumes intrinsic client clustering, both are analyzed with generalization bounds.

Weakness:
I only have mostly minor concerns. While the two proposed algorithms are theoretically analyzed, they are not directly compared. It seems that with the $(1 + \gamma, \epsilon)$-approximation-stability assumption in Theorem 4, ACLC has a better generalization bound than ACLMM (when $OPT_$\Phi(P)$ is small) and it would be interesting to compare the bounds in detail. It is also worth empirically testing ACLMM in Figure 5.
questions: Could the authors compare Theorem 3 and Theorem 4 under the same assumption, and discuss how much tighter Theorem 4 could be?
Will ACLC perform better than ACLMM following the setting of Figure 5, especially with large $N$?
limitations: See weakness.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the collaborative learning problem, in which different clients could have non-i.i.d data. Compared with existing global or personalized methods, this paper proposes to detect collaboration partners to achieve a better collaboration. The authors formalize this problem as measuring the similarity between clients and finding an optimal partition of the collaboration federated network. The authors give various theoretical analysis and provide experimental results to verify the effectiveness of the proposed method. 
strengths_and_weaknesses: ## Strengths:
1.This paper considers a challenging problem, the collaboration among multiple clients, which is very useful and significant in reality.

2.This paper mainly focuses on theoretical analysis, including the similarity measurement between clients, the optimization of the partition, and the error bound of the approximated partition;

## Weakness:
### Motivation:
1. The motivation in this paper is to find a partition for the collaboration network. It is reasonable and efficient. However, some related work and more discussions are missing, for example [1,2]. 

### Theory:
1.Some theoretical results I’m very familiar with, e.g., theorem 1 and theorem 2. I’m afraid they are quite similar to existing theoretical work in domain adaptation and domain generalization. For the other theoretical conclusions, the authors also seems to refer to existing work. That being said, it’s not a big problem. More discussions about the difference between the theoretical analysis and existing work are necessary;

### Experiments:
The experiments in this paper are seriously insufficient.
1.the idea in this paper is clustering similar or helpful clients. More baselines are necessary, for example [2].
2.the experiments focus on two image datasets. More other data are necessary.

### Privacy:
This paper considers the problem of collaborative learning. The proposed method needs to measure the similarity between clients, which could cause privacy leakage in a federated learning setting. Could the authors discuss more about the privacy concerns?

[1] Cui S, Liang J, Pan W, et al. Learning to Collaborate[J]. arXiv preprint arXiv:2108.07926, 2021.

[2]. Ghosh A, Chung J, Yin D, et al. An efficient framework for clustered federated learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 19586-19597.
questions: Please see weaknesses.
limitations: The authors claim that they describe the limitations, but I did not found.
review_title: null

Meta-review: metareview: In this submission, the authors propose a novel method to handle the heterogeneous clients challenge in FL by detecting collaboration partners and adaptively learning models for client groups. The authors provide the theoretical analysis of the error bound of the approximated partition, which justifies the effectiveness of the proposed method. The experimental results on the real-world dataset also validate that the group model is a good approximation of the personalized model. Due to these, I recommend accepting this submission.

However, I do have one major concern about the insufficiency of the experiment (as pointed out by reviewer XfiP). More datasets and baselines should be adopted. 

Further, this submission also can be improved based on the comments from all the reviewers and the discussion between reviewers and authors. Hope they find these useful, and make this submission a better one.

confidence: Certain
Decision: Accept