FedNE: Surrogate-Assisted Federated Neighbor Embedding for Dimensionality Reduction

Questions regarding scalability and complexity

Please see the general response.

The paper proposes intra-client data mixing … However, this approach might not entirely mitigate the issue … More detailed comparisons with alternative methods …

Thank you for the insightful comment. As we pointed out in the paper, the bias in the local kNN graphs is one key blocker to the problem of Federated NE. Dealing with attraction term is more challenging than repulsion term as it requires knowing true data affinity across different clients (as discussed in Sect. 4.2). Such a problem has never been pointed out in prior work, but as emphasized in our paper (Line 209-217).

With this in mind, we made one of the first attempts to mitigate it. We acknowledge that our approach may not fully address the problem, but it demonstrates that reducing its effect can notably improve the overall performance (see Sect.5.3), setting up the foundation for future work to inspire more research in this new field including but not limited to addressing the attractive loss within the settings of FL.

We appreciate your comments on “alternative methods.” To our knowledge, none of the prior work in FL for dimensionality reduction aimed to address this issue. We would appreciate if you could provide references to the alternative methods you mentioned, and we will be happy to provide more discussions in the reviewer/author discussion phase.

… The validation results are performed only on the vision classification tasks … other domains could be beneficial.

Thanks for your valuable comment. We totally agree that the evaluation of our method is mainly on the vision datasets. The main reason we designed the experimental study in this way is mainly to follow a similar paradigm as other DR studies [33,44,55], with the purpose of fair comparisons. However, we admit that only evaluating vision data might be not enough. Therefore, in addition to the commonly used benchmark vision data, we also evaluated our method on a biological dataset, scRNA-Seq (see Tables 1 and 2 in the original manuscript). The scRNA-Seq dataset is a real-world dataset containing a collection of gene expression profiles obtained from individual cells of the mouse retina. We hope this additional biological dataset can give you a more comprehensive understanding of our effectiveness in different domains.

[33] “UMAP: Uniform manifold approximation and projection for dimension reduction.” arXiv preprint arXiv:1802.03426, 2018.

[44] "Visualizing data using t-SNE." JMLR 9.11 (2008).

[55] "SpaceMAP: Visualizing High-Dimensional Data by Space Expansion." ICML. 2022.

Could you provide more details on the process of training the surrogate models? Specifically, how do you ensure that these models effectively capture the repulsive forces between dissimilar data points across different clients?

Thanks for the comment. We have discussed in Sect. 4.1 and A.2 in the appendix, but we should have made this more clear. To train the surrogate repulsion model for a client $m$, we generate a set of low-dimensional (low-D) query points via grid sampling to serve as potential embedding positions of other clients’ data points. Then, for each newly sampled low-D query data $z_q$, we pre-compute the repulsive loss between $z_q$ and $b$ data points sampled within client $m$, which serve as the training targets.

The surrogate model is expected to learn a mapping from these newly sampled embedding positions to their corresponding repulsion loss, as measured within client $m$. According to the repulsive loss term introduced in Section 3.1, a larger low-D Euclidean distance will result in a smaller repulsive loss value [6]. Thus, the repulsion loss decreases as the distance between the data pairs increases. If two embedding points are close within a threshold, our surrogate model is able to approximate the repulsion force; if the points are far apart, the model estimates the repulsion force between them to be close to zero.

[6] "Attraction-repulsion spectrum in neighbor embeddings." JMLR 23.95 (2022): 1-32.

How does FEDNE handle extreme cases of non-IID data distribution? Have you considered any additional mechanisms to ensure robustness in such scenarios?

We agree that the ability to handle non-IID data is very important. Therefore, we have conducted experiments on the settings of Dirichlet(0.1) and Shards with C=2 to demonstrate the effectiveness of FedNE in handling extreme non-IID cases, as shown in Tables 2 and 6 in the original manuscript.

FedNE addresses non-IID data distribution exactly via the surrogate models. For example, under an extreme non-IID condition, each client may have data exclusively for certain clusters. In this scenario, the issue with the attraction term might be relaxed because the true neighboring points are likely to reside within the same client. However, in the global context, the dissimilar data pairs contributing to the repulsive loss term are located across different clients. As discussed in Sect. 3.3 and 4.1, our surrogate model is specifically designed for this condition by filling in the missing repulsion terms.

How sensitive is FEDNE to the choice of hyperparameters

Thanks for the valuable suggestions. We have included experiments in Appendix B to analyze the sensitivity of some important hyperparameters in our method such as the frequency of surrogate function updates and the time to integrate the surrogate loss function into the local training.

Furthermore, we want to provide additional results on analyzing the sensitivity for the following hyperparameters: (1) Number of neighbors in the kNN graphs, (2) Step sizes in the grid sampling, and (3) The weight in intra-client data mixing. Due to the space limit, we included the detailed analysis in the figure captions. Please find the results and analysis in the attached PDF.

Thank you for your feedback and your willingness to increase the rating. We will incorporate our rebuttal into the revised version of our paper, and we would appreciate it if you would be supportive of the acceptance of our paper.

Questions related to privacy concerns

We found that major concerns mentioned in the weakness and questions are related to “privacy-preserving”, and these concerns may arise from the “privacy-preserving” term in our paper title. First, we want to apologize for the confusion caused by our title. The main focus of our paper is on a FL setting, aiming to bring up the unique FL challenges and propose effective solutions for the pairwise training objective in the problem of Federated Neighbor Embedding. Besides the privacy-preserving properties that a Federated setting has introduced, we do not specifically develop any privacy-preserving mechanisms and we certainly do not claim that our approach introduces additional privacy guarantees. We will surely refine our title and any writing to clarify this.

Introducing formal privacy guarantees is not a trivial task. Among the only two existing methods, dSNE [37] proposes a decentralized neighbor embedding framework and later, they extend dSNE to be privacy-guaranteed by incorporating differential privacy (DP) as F-dSNE [38]. We have to admit that, developing privacy-guaranteed Federated NE methods while addressing the lack of inter-client data relationships is an important but challenging task. Therefore, we will consider the privacy of FedNE as an orthogonal problem and will work toward incorporating DP or other techniques in our future work. We will add discussions on how to enhance FedNE with privacy-preserving techniques.

Inadequate Analysis of Related Work

Thanks for the valuable comment. As our work intersects with two research areas: FL and DR, we have structured the related work section into three subtopics in Sect. 2. In fact, we have compared FedNE with two closely related works, dSNE and F-dSNE in Sect. 2. However, due to the page limitations, we might have overlooked some relevant literature and we are happy to include additional work on FL and DR. However, we kindly believe that our literature review in the field of decentralized DR is thorough.

The study's applicability could be strengthened … to encompass real-world, privacy-sensitive datasets …

Thanks for the constructive suggestions. As clarified in our above response, our main focus is on FL for DR instead of particularly improving the privacy-preserving properties. Thus, we focus more on benchmark datasets in the field of DR. Specifically, we have included the standard datasets in the DR community but with more practical settings (i.e., more clients and larger datasets) compared to prior work (please see the general response).

With that being said, your comments are well received, and we will consider extending our study to some real-world privacy-sensitive datasets. However, we do want to point out some considerations. Datasets from different domains have unique properties. For example, the prior work [37] mentioned that, in the neuroimaging domain, not all data is private/unshareable, and many public MRI datasets are accessible. The only existing works [37,38] related to our problem focusing on neuroimaging data have made this unreasonable assumption which makes their method hard to generalize. In contrast, to prevent loss of generalizability, our FedNE was developed without assuming any domain-specific properties. Furthermore, we believe that adapting FedNE to the domain-specific datasets should not be difficult as we did not make any prior assumptions about the data properties.

Questions regarding scalability, complexity, and computational efficiency

Please see the general response.

The paper claims to operate without relying on shareable reference data, yet it utilizes additional 2D data points from grid sampling to estimate the training targets …

Thanks for your comment. We want to reiterate that our FedNE does not use any shareable reference data, as the publicly available dataset is often inaccessible in many real-world applications (Line 112-114). Moreover, the quality of the reference data can significantly affect the performance [37]. Given these more practical considerations, we propose surrogate models and intra-client data mixing to address the constraints and challenges brought by the Federated setting. We think the computational cost is still manageable, and more importantly, our work is valuable as it was developed within a more practical and general FL setting, even with some extra burden from data sampling.

No experiments are conducted on downstream tasks …

Thanks for your suggestion. We want to emphasize that the main focus of this work is to propose a DR framework within the FL setting. Therefore, most of our evaluation metrics are designed for analyzing the structural properties of the embeddings. This is because metrics like preservation of neighborhood relationships and preservation of data clusters can provide a clear indication of how well our DR model performs [57,58] regardless of whether it is under the federated or centralized setting. We totally agree that evaluating on other downstream tasks might be valuable to provide a different understanding of our model performance. However, the metric to evaluate other downstream tasks might not be able to accurately assess our capability of preserving the neighborhood relationship as a DR framework. Thus, we respectfully think conducting experiments on downstream tasks e.g., classification might be biased to assess our effectiveness in DR.

[37] "See without looking: joint visualization of sensitive multi-site datasets." IJCAI. 2017.

[38] "Federated, Fast, and Private Visualization of Decentralized Data." Workshop of Federated Learning and Analytics in Practice (2023).

[57] "Toward a quantitative survey of dimension reduction techniques." IEEE TVCG 27.3 (2019): 2153-2173.

[58] "Dimensionality reduction: A comparative review." JMLR 10.66-71 (2009): 13.

[59] "Feature dimensionality reduction: a review." Complex & Intelligent Systems 8.3 (2022): 2663-2693.

How would the parameter k affect the performance of FEDNE? How to set k for different settings?

Thank you for the valuable comment. First, we want to reiterate that the value k is used for building local kNN graphs to capture the neighboring data structures. In general, as k increases, we may lose the neighboring information. When k is too small, it may result in many isolated clusters in the embedding space.

However, there is no clear consensus on how to select k in the dimensionality reduction (DR) community. As many recent DR papers use fixed k values [11], we followed them as well. We experimented with different k values under the setting of Dirichlet(0.1) on the MNIST dataset with 20 clients. Please find the results in the attached PDF. We found that within a certain range (i.e., 7 to 30), the performance of FedNE is relatively stable. When k is too large (e.g., k=50), the performance drops but our FedNE still outperforms the baseline methods, FedAvg+NE. This trend aligns with the general understanding of DR methods. Once there is a best practice to select k for different settings, it can be applied to our problem.

[11] “From t-SNE to UMAP with contrastive learning”. In ICLR, 2023.

What are the major differences between the metrics? Why the improvement of FEDNE differ a lot across different metrics?

Thanks for your thoughtful comment. We had some discussions in Sections 5.1 and 5.2, but we should have made this more clear.

Continuity, trustworthiness, and kNN classification accuracy are mainly used to evaluate the preservation of neighborhood data structures in the global reduced-dimensional space. Steadiness and cohesiveness aim to measure the preservation of inter-cluster structures since clusters can be distorted when projecting to the global low-dimensional space. Among the five metrics, trustworthiness, kNN classification accuracy, and steadiness have much more noticeable increases compared to continuity and cohesiveness.

The improvement differs a lot among the metrics mainly because in a simple FedAvg framework without any special treatment for the data pairs across different clients, the model cannot penalize those data pairs to be apart, which results in introducing false neighbors in the embedding space (Line 215 and 292). These false neighbors can further cause data points from different classes to overlap in the embedding space. This explains why the baseline methods achieve much lower trustworthiness scores and kNN classification accuracy, as trustworthiness measures whether neighbors in the embedding space are also neighbors in the high-dimensional space.

Due to similar reasons, without mitigating the incorrect neighbor connections and addressing the missing repulsion terms, the overlap in the embedding space will also mistakenly introduce false data clusters. Thereby, steadiness is also low for the baseline methods as it measures how well the model can avoid false clusters. However, both our surrogate models and intra-client data mixing strategy aim to prevent false neighbors in the embedding space. When true neighbors are preserved by FedNE, the trustworthiness and steadiness scores have increased and the points that are close in the embedding space are more likely to belong to the same class. Thus, the kNN classification accuracy is also notably increased (see Table 2 in the original manuscript).

Continuity measures how well the neighborhood of a data point in the high-dimensional space is preserved in the embedding space. Achieving higher continuity is often easier even under the context of FL because the original attraction term in the client’s local objective function already pulls the neighbors closer in the embedding space. Cohesiveness is for measuring how well the projection model can avoid missing clusters. We still can observe relatively larger improvements in cohesiveness compared to continuity. Improved cohesiveness demonstrates that FedNE will not mistakenly break the true clusters in the embedding space.

I suggest to highlight the best results in Table 2. Currently the results of FEDNE are highlighted although it may not achieve the best performance in some cases.

Thank you for the suggestion. We will change to highlight the best performance in the final version.

We appreciate your feedback and your positive opinion about our paper. If our rebuttal has addressed your concerns, we would also appreciate it if you would be willing to consider raising your original rating. Thank you for your consideration.

Communication complexity ... this design results in a communication complexity of $O(N^2)$ … This might be manageable in some cross-silo settings, where only a few clients participate.

Thanks for the thoughtful comment. Since each client will receive the surrogate models of all other clients from the server, we acknowledge that the size of the communication will be $O(N^2)$. We totally agree that our framework is more manageable in some cross-silo settings. However, as the size of the surrogate model is very small containing only one hidden layer (e.g., around 20K bytes), and nowadays data transfer has become much more efficient and affordable (e.g., 1.2 GB/s in modern wireless services), in our humble opinion, communication cost should not be a big problem.

Straggler effect … However, clients may drop out during training. It would be insightful if the authors could analyze how missing surrogate loss models would affect overall performance.

Thank you for the nice practical question. We follow your suggestion to experiment with the idea that only a random 10% of the clients are involved in each communication round. Specifically, these clients will only receive the surrogate models from the other 10% of the clients. We summarize our results in the attached PDF, under the setting of Dirichlet(0.1) on the MNIST dataset with 100 clients. We can see that while the performance under 10% client participation is worse than under full client participation, the results of FedNE are still notably better than the baseline methods, FedAvg+NE, demonstrating the effectiveness and applicability of our FedNE framework.

Additional privacy concerns: Sharing surrogate models introduces additional privacy risks, … the proposed method might be more vulnerable to privacy attacks without differential privacy.

Thank you so much for the comment. First, we want to apologize for the confusion caused by our title. The main focus of our paper is on a Federated setting, aiming to bring up the unique FL challenges and propose effective solutions for the pairwise training objective in the problem of Federated Neighbor Embedding. We appreciate your suggestions and will extend our discussion by adding a section in the camera-ready version to incorporate the points that you mentioned.

Besides the privacy-preserving properties that a Federated setting has introduced, we do not specifically develop any privacy-preserving mechanisms. Therefore, we will surely refine our title and any writing to clarify this.

With that being said, privacy-preserving is an important topic and we will explore incorporating differential privacy (or other techniques) in our future work. We will also investigate some characteristics of our algorithm to enhance privacy. For example, our surrogate models take the “low-dimensional” data as inputs. We will investigate whether this design improves privacy preservation since one cannot directly reconstruct the high-dimensional data. Moreover, since it is the server that collects surrogate models from all the clients and distributes them to each client, certain anonymization techniques may be applied so that each client does not know the owner of the surrogate function it receives.

I want to thank the authors for their time and response. Since the response only partially addressed my concerns, I'd like to follow up on those points.

Scalability

Despite the tiny surrogate model, the communication costs grow quadratically for the entire system and linearly for each client. It could be unfavorable when deployed in a million-scale system, but I can see the applications in common cross-silo settings.

Straggler effect

Thanks for the additional experiments. However, I was curious about the stale surrogate models instead of partial participation. In other words, what would happen if some clients send old surrogate models from previous rounds due to the network delay?

Privacy concerns

This remains my biggest concern. The authors do not provide any further analysis of it.

While the concept of using shared anchors is not entirely new (as previously explored in [1] and preliminary theoretical analyses like [2]), its application in federated clustering appears to be new. The primary concern still lies in the potential privacy and security risks. I'm currently torn in my recommendation. On one hand, this work could provide a foundational analysis that serves as a baseline for federated clustering. On the other hand, the improved performance is built upon the inherent compromise of privacy. Such compromise also makes future comparisons unfair and challenging if the threat model is not stated clearly, i.e., what is assumed to be safe. Therefore, unless the potential privacy leakage is thoroughly discussed or the compatibility with differential privacy is demonstrated, I remain cautiously optimistic but will slightly lower my score.

If the authors can propose a robust comparison protocol for future work that accounts for various privacy considerations, I would be willing to reconsider and potentially adjust my score.

[1] Wang, Hui-Po, et al. "Fedlap-dp: Federated learning by sharing differentially private loss approximations," Proceedings on Privacy Enhancing Technologies, 2024.
[2] Li, Bo, et al. "Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity." Transactions on Machine Learning Research.

Dear Reviewer BJv7,

We appreciate your timely feedback on our rebuttal. Given the limited author-reviewer discussion period, we have tried our best to further address it. Please see our response titled "Official Comment by Authors." If our latest response has addressed your concerns, we would appreciate it if you would be willing to consider raising your rating. Thank you for your consideration.

Best,

Authors