FedNE: Surrogate-Assisted Federated Neighbor Embedding for Dimensionality Reduction

Authors: ziwei  li
xiaoqi  wang
hong-you  chen
han-wei  shen
wei-lun  chao
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:45:59

Abstract: Federated learning (FL) has rapidly evolved as a promising paradigm that enables collaborative model training across distributed participants without exchanging their local data. Despite its broad applications in fields such as computer vision, graph learning, and natural language processing, the development of a data projection model that can be effectively used to visualize data in the context of FL is crucial yet remains heavily under-explored. Neighbor embedding (NE) is an essential technique for visualizing complex high-dimensional data, but collaboratively learning a joint NE model is difficult. The key challenge lies in the objective function, as effective visualization algorithms like NE require computing loss functions among pairs of data. 
In this paper, we introduce \textsc{FedNE}, a novel approach that integrates the \textsc{FedAvg} framework with the contrastive NE technique, without any requirements of shareable data. To address the lack of inter-client repulsion which is crucial for the alignment in the global embedding space, we develop a surrogate loss function that each client learns and shares with each other. Additionally, we propose a data-mixing strategy to augment the local data, aiming to relax the problems of invisible neighbors and false neighbors constructed by the local $k$NN graphs. We conduct comprehensive experiments on both synthetic and real-world datasets. The results demonstrate that our \textsc{FedNE} can effectively preserve the neighborhood data structures and enhance the alignment in the global embedding space compared to several baseline methods.

Main paper: 
 introduction: 
 Federated Learning (FL) has emerged as a highly effective decentralized learning framework in which multiple participants collaborate to learn a shared model without sharing the data. In recent years, FL has been extensively studied and applied across various domains, including image and text classifications [10, 31, 23, 9] , computer vision tasks [3, 41, 50] , and graph learning problems [42, 5, 16] . Despite the growing interest in FL, the area of dimensionality reduction within this framework has received limited investigation. However, visualizing and interpreting data from distributed sources is important, as real-world applications often generate large volumes of complex datasets that are stored locally by each participant. For example, different hospitals collect high-dimensional electronic health records (EHRs) [1] and securely store this patient data within their local systems. As each hospital might only collect limited data or focus on particular diseases, conducting data visualization on a combined dataset can substantially improve disease diagnosis and provide deeper insights. However, sharing sensitive patient information is restricted due to privacy protection. Thus, developing a shared dimensionality reduction model in the FL setting is crucial for facilitating collaborative analysis while maintaining data on local sites. Dimensionality reduction (DR) refers to constructing a low-dimensional representation from the input data while preserving the essential data structures and patterns. Neighbor embedding (NE) [6, 49] , a family of DR techniques, is widely utilized to visualize complex high-dimensional data due to its ability to preserve neighborhood structures and handle non-linear relationships effectively. Essentially, NE methods (e.g., t-SNE [44, 43] and UMAP [33] ) operate on an attraction-repulsion spectrum [6] , balancing attractive forces that pull similar data points together and repulsive forces that push dissimilar points apart. Defining the objective function requires access to any pairs of data points. Such a need to access pairwise data for determining the attraction and repulsion terms, however, poses critical challenges to the FL framework. As data are distributed across different clients, computing their pairwise distances becomes non-trivial, making it difficult to recover the centralized objective in an FL setting. Specifically, the absence of inter-client repulsive forces complicates the separation of dissimilar data points. Moreover, within a client, due to the unavailability of others' data, defining a faithful attraction term based on the top neighbors is challenging, often resulting in the inaccurate grouping of distant data points. This contrasts with traditional FL tasks, such as image classification, where learning objectives can be decomposed over individual training instances, allowing each client to calculate the loss independently and optimize the model based solely on its local dataset.To the best of our knowledge, only a few existing works address the problem of decentralized data visualization. Both dSNE [37] and F-dSNE [38] methods require publicly shared data that serves as a reference point for aligning the embeddings from different clients. This setup introduces additional assumptions that may not be feasible in real-world applications, and the quantity and representativeness of the reference data can significantly impact the resulting embeddings.To this end, we proposed a novel Federated neighbor embedding technique, called FEDNE, which follows the widely used FEDAVG pipeline. It trains a shared NE model that is aware of the global data distribution, without requiring any shareable data across participants. To compensate for the lack of much-needed inter-client repulsive force, besides training a local copy of the NE model, each client additionally learns a surrogate model designed to summarize its local repulsive loss function. During global aggregation, this surrogate model will be sent back to the server along with the local NE model, which other clients can use in the next round of local training. In detail, for a client m, its local surrogate model is designed to approximate the repulsion loss from an arbitrary point to its local data points. By sending the surrogate model to other clients, another client m ′ can incorporate it into its local loss function for training the NE model. Additionally, to handle the difficulty of estimating the neighborhood, we introduce an intra-client data mixing strategy to simulate the presence of potential neighbors residing on the other clients. This approach augments the local data to enhance the training of the NE model.To showcase the effectiveness of FEDNE, we conduct comprehensive experiments using both synthetic and real-world benchmark datasets used in the field of dimensionality reduction under various FL settings. Both qualitative and quantitative evaluation results have demonstrated that our method outperforms the baseline approaches in preserving the neighborhood data structures and facilitating the embedding alignment in the global space.Remark. It is worth discussing that we understand privacy-preserving is an important aspect to address in the FL framework. However, we want to reiterate the main focus of this paper is identifying the unique challenges in the federated neighbor embedding problem and proposing effective solutions rather than resolving all the FL challenges at once. We discuss the privacy considerations and our further work in section 6. 
related work: 
 Federated learning. FL aims to train a shared model among multiple participants while ensuring the privacy of each local dataset. FEDAVG [34] is the foundational algorithm that established the general framework for FL. Subsequent algorithms have been proposed to further improve FEDAVG in terms of efficiency and accuracy. Some of the work focuses on developing advanced aggregation techniques from various perspectives such as distillation [46, 39] , model ensemble [30, 40] , and weight matching [45, 52] to better incorporate knowledge learned by local models. Moreover, to minimize the deviation of local models from the global model, many works focus on enhancing the local training procedures [21, 2, 51, 29] . FEDXL [15] was proposed as a novel FL problem framework for optimizing a family of risk optimization problems via an active-passive decomposition strategy. Even though FEDXL deals with the loss decomposition for pairwise relations, our main focus and application are very different.Neighbor embedding. Neighbor embedding (NE) is a family of non-linear dimensionality reduction techniques that rely on k-nearest neighbor (kNN) graphs to construct the neighboring relationships within the dataset [6] . The key of NE methods lies in leveraging the interplay between attractive forces which bring neighboring data points closer and repulsive forces which push uniformly sampled non-neighboring data pairs further apart. t-SNE [44] is a well-known NE algorithm. It first converts the data similarities to joint probabilities and then minimizes the Kullback-Leibler divergence between the joint probabilities of data pairs in the high-dimensional space and low-dimensional embedding space. Compared to t-SNE, UMAP [33] is better at preserving global data structure and more efficient in handling large datasets. A later study has analyzed the effective loss of UMAP [13] and demonstrated that the negative sampling strategy indeed largely reduces the repulsion shown in the original UMAP paper, which explains the reasons for the success of UMAP. Our federated NE work is built upon a recent work that has theoretically connected NE methods with contrastive loss [12, 19] . Their proposed framework unifies t-SNE and UMAP as a spectrum of contrastive neighbor embedding methods.Decentralized dimensionality reduction. As nowadays datasets are often distributively stored, jointly analyzing the data from multiple sources has become increasingly important especially when the data contains sensitive information. SMAP [47] is a secure multi-party t-SNE. However, as this framework requires data encryption, decryption, and calculations on the encrypted data, SMAP is very time-consuming and thereby it can be impractical to run in real-world applications. dSNE was proposed for visualizing the distributed neuroimaging data [37] . It assumes that a public neuroimaging dataset is available to share with all participants. The shareable data points act as anchors for aligning the local embeddings. To improve the privacy and efficiency of dSNE, Faster AdaCliP dSNE (F-dSNE) [38] was proposed with differential privacy to provide formal guarantees. While their goal is not to collaboratively learn a global predictive DR model and thus does not follow the formal FL protocols [22, 8, 34] defined in the literature. Both methods require a publicly available dataset to serve as reference gradients communicating across central and local sites. However, since a public dataset may not be available in most real-world scenarios, our FEDNE is designed without any requirements for the shareable data. 
fl framework for neighbor embedding: 
 In this section, we first provide background information on neighbor embedding techniques. We then formulate the problem within the context of FL and outline the unique challenges.The goal of general NE techniques is to construct the low-dimensional embedding vectors z 1 , ..., z N ∈ R d for input data points x 1 , ..., x N ∈ R D that preserve pairwise affinities of data points in the high-dimensional space. The neighborhood relationships are defined via building sparse k-nearest-neighbor (kNN) graphs over the entire dataset with a fixed k value. Contrastive NE [11] is a unified framework that establishes a clear mathematical relationship among a range of NE techniques including t-SNE [44] , UMAP [13] , and NCVis [4] , via contrastive loss. For parametric NE, an encoder network f θ is trained to map an input data point x to a low-dimensional representation z, i.e., z = f θ (x).In general, the contrastive NE algorithms first build kNN graphs to determine the set of neighbors p i for each data point x i in the high-dimensional space. A numerically stable Cauchy kernel is used for converting a pairwise low-dimensional Euclidean distance to a similarity measure:ϕ(z i , z j ) = 1 1+∥zi-zj ∥ 2 2. Then, the contrastive NE [11] loss is optimized via the negative sampling strategy:EQUATIONwhere p i denotes the set of neighboring data points of x i .In ∩ D m ′ = ∅ for ∀ m, m ′ ∈ [M ],and m ̸ = m ′ . Our goal is to learn a single neighbor embedding model such that the high-dimensional affinities of the global data can be retained in a global low-dimensional embedding (2D) space.It is natural to consider employing the FEDAVG [34] framework since the clients can collaborate by communicating their parametric NE models. Then, the learning objective can be formulated with x i , x j ∈ D m as following:EQUATIONwhereEQUATIONAs the client data cannot leave its own device, Equation 2 cannot be solved directly. EQUATIONDuring local training, each participating client m updates its model parameter θ m for only a few epochs based on the aggregated model θ(t-1) received from the server.However, besides the challenges posed by the non-IID data, simply decomposing the problem into Equation 3 indeed overlooks the pairwise data relationships existing across different clients. The major difference between the existing FL studies, e.g., image classification, and Federated neighbor embedding is that the objective function of the former problems is instance-based, where their empirical risk is the sum of the risk from each data point:EQUATIONAs a result, the FL objective in Equation 2, i.e.,|Dm| |D| L m (θ), is exactly the one as if all the clients' data were gathered at the server.In the context of Federated neighbor embedding, Equation 3 only considers x j to come from the same client as x i . Thus, simply adopting the vanilla FEDAVG framework can result in losing all the attractive and repulsive terms that should be computed between different clients. Therefore, we redefine the FL objective of the contrastive neighbor embedding problem to beEQUATIONwhere the pairwise empirical risk ℓ(x i , x j ; θ) can be further defined asℓ(x i , x j ; θ) = -1[x j ∈ p i ] log(ϕ(f θ (x i ), f θ (x j ))) Attractive force -b log(1 -ϕ(f θ (x i ), f θ (x j )))Repulsive force .Nonetheless, since the inter-client pairwise distances are unknown, Equation 7 cannot be solved directly when x i and x j come from different clients. Specifically, this decentralized setting brings two technical challenges: (1) Biased repulsion loss: Negative sampling requires selecting non-neighbor pairs uniformly across the entire data space. Under the FL setting, it is difficult for a client to sample from outside of its local dataset. (2) Incorrect attraction loss: Each client only has access to its local data points. This partitioning can result in an incomplete kNN graph, leading to incorrect p i , as some true neighbors of a data point might reside on other clients. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Justification: We have provided detailed formulations for our proposed approach and analysis made in the paper.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.• Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.• Theorems and Lemmas that the proof relies upon should be properly referenced. 
federated neighbor embedding: fedne: 
 To address the aforementioned challenges in applying the FL framework to the neighbor embedding problem, we develop a learnable surrogate loss function1 trained by each client and an intra-client data augmentation technique to tackle the problems in repulsion and attraction terms separately. The two components can be smoothly integrated into the traditional FEDAVG pipeline shown in Figure 1 .The repulsive force plays an important role in ensuring separation among dissimilar data points, contributing to the global data arrangement in the embedding space. In the centralized scenario, each data point can uniformly sample its non-neighbors across the entire dataset. In contrast, in the federated setting, as each client can only access its local data, the dissimilar points residing in other clients are invisible, and all the repulsion will be estimated within its own data space. In particular, under severe non-IID situations, where the data distributions across different clients vary significantly [54] , the non-neighboring samples selected to repel are very likely to come from the same clusters in high-dimensional space. As showcased in Figure 2 (a), without explicitly taking care of the repulsion between dissimilar data pairs across clients, those points may still overlap with each other in the embedding space.At a high level, we seek to learn a functionf rep m;w : d → R for each client m such that f rep m;w ≈ b log(1 -ϕ(f θ (x i ), f θ (x j ))) to estimate the repulsion, where x i and x j come from different clients. This surrogate model, once shared, enables other clients to input their local data points and obtain a pre-estimated repulsive loss to data points from the originating client.m;w via supervised learning at each round of FEDAVG. To do so, we generate a set of low-dimensional query points as inputs and pre-compute their corresponding repulsive loss to client m's data points based on the current projection model. We choose to sample a set of points Z q within 2D space for the following two reasons. Firstly, as non-neighboring points are uniformly selected across the data space, query points are not required to maintain any specific affinity with D m . Second, because the high-dimensional space is often much sparser than 2D space, generating sufficient high-dimensional samples to comprehensively represent the data distributions of all other clients is impractical. Therefore, each client employs a grid sampling strategy at every round, using a predefined step size and extensive ranges along the two dimensions. This procedure is informed by client m's current embedding positions, ensuring a more manageable and representative sampling process within the embedding space.In sum, given the sampled inputs Z q = {z q1 , z q2 , . . . , z q Nq }, we prepare the training targets by computing the repulsive loss between each z qi and b random data points in D m , i.e.,l rep qi = - b j log(1 -ϕ(z qi , z (j) m )).Then, the dataset for supervised training the surrogate repulsion function f rep m;w is constructed asD q = {(z qi , l rep qi )} |Dq| i=1 .Implementation details. After building the training dataset, each client trains its surrogate model f rep m;w using an MLP with one hidden layer to learn the mapping between the input embedding vectors and their corresponding repulsive loss measured within the client data by minimizing the mean squared error (MSE). The training objective is formulated as follows:EQUATIONTo mitigate the limitations of biased local kNN graphs and ensure better neighborhood representation, we propose an intra-client data mixing strategy. This approach generates additional neighboring data points within each client, thereby enhancing the local data diversity. To be specific, locally constructed kNN graphs can be biased by the client's local data distribution. As the associated data pairs for computing the attractive loss are distributed across multiple clients, the local neighborhood within each client can be very sparse. Consequently, data points within a client may miss some of their true neighbors (i.e., invisible neighbors) considered in the global space. Moreover, when the local data is extremely imbalanced compared to the global view, constructing the kNN graph with a fixed k value may result in incorrect neighbor connections between very distant data points (i.e., false neighbors). As demonstrated in Figure 2 (b), since data is partitioned across different clients, with a fixed k value, each local kNN graph can be even more sparse and erroneously connect very distinct data points.Intra-client data mixing. To address these problems, we employ a straightforward yet effective strategy, intra-client data mixing, to locally generate some data within a client by interpolating between data points and their neighbors. Our method shares a similar spirit to the mixup augmentation [53, 36] .In detail, given a data point x i and the set of its k nearest neighbor NN k (x i ), a new data point is generated by linearly interpolating x i and a random sample in NN k (x i ) denoted as x j :EQUATIONwhere λ is the weight sampled from the Beta distribution i.e., λ ∼ Beta(α).Once each client has received the surrogate loss functions of all the other participants (i.e., step 4 in Figure 1 ), it proceeds to its local training. By combining the original NE loss with the surrogate loss function on the augmented local training data, the new objective for client m can be formulated as:L m ( Dm ; θ) = - ij∼p log(ϕ(f θ (x m i ), f θ (x m j )))Original attractive loss- |D m | |D| ij log(1 -ϕ(f θ (x m i ), f θ (x m j )))Original repulsive lossEQUATIONwhere x m i , x m j ∈ Dm i.e., the augmented training set. For simplicity, we use p to represent the neighbor set constructed within Dm . f rep m ′ ;w is the surrogate model received from another client m ′ . Computation. At first glance, FEDNE may seem to introduce heavy computational overhead compared to the original FEDAVG framework, as it requires additional surrogate model training at every round. Moreover, a client needs to use multiple received surrogate models to do inference using its own local data. Nevertheless, we want to emphasize that the surrogate model contains only one hidden layer and takes 2D data points as inputs. Therefore, training and using them is manageable. We conducted experiments using MNIST with 20 clients on a server with 4 NVIDIA GeForce RTX 2080 Ti GPUs. Compared to FEDAVG, our FEDNE takes 35% more GPU time to complete one round of training. For future speed-up, we may consider applying strategies such as clustered FL and we leave this for future work. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We have provided the implementation details and experimental setups in our experiments and results sections, and also in the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.• While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experimental settings: 
 Datasets. We conduct experimental studies on four benchmark datasets that have been widely used in the field of dimensionality reduction [35, 55] : MNIST [26] , Fashion-MNIST [48] , mouse retina single-cell transcriptomes [32] , and CIFAR-10 [25] . Their statistical information and general settings are summarized in Table 1 . For CIFAR-10, since the Euclidean distances in the pixel space of a natural image dataset are not meaningful to preserve [7] , we adopted ImageNet-pretrained ResNet-34 [17] to extract a set of 512D feature vectors as input data. The resulting vectors still retain category-relevant structures that can be suitable for the Euclidean metric.Non-IID data partition. We consider two partitioning strategies to simulate the heterogeneous client distributions: (1) Dirichlet: For a class c, we sample q c from Dir(α) and assign data samples of that class c to a client m proportionally to q c [m]. The hyperparameter α controls the imbalance level of the data partition where a smaller α indicates a more severe non-IID condition [27, 18] . (2) Shards: each client holds data from C classes, and all samples from the same class are randomly and equally divided among all clients [27] .Evaluation metrics. We assess the quality of data embeddings by analyzing the input highdimensional data points and their corresponding 2D positions [14] . First, to evaluate the preservation of neighborhood structures, we compute trustworthiness and continuity scores. Trustworthiness quantifies the quality of a low-dimensional embedding by checking whether neighbors in the highdimensional space remain the same as the ones in the embedded low-dimensional space. Conversely, continuity verifies whether the neighbors in the embedded space correspond to neighbors in the original input space. We use kNN classification accuracy to measure the effectiveness in preserving the nearest neighbors in the embedded space, where higher scores indicate better class discrimination. We fix k = 7 for all the neighborhood metrics. Additionally, we employ steadiness and cohesiveness metrics to evaluate the reliability of the global inter-cluster structures [20] . Steadiness assesses the presence of false groups, while cohesiveness checks for the existence of any missing groups.Implementation and training details. We employ a fully connected neural network with three hidden layers for MNIST, Fashion-MNIST, and CIFAR-10 datasets and a network with two hidden layers for the RNA-Seq dataset. In all experiments, we use Adam optimizer [24] with learning rate annealing and a batch size of 512 where the batch size refers to the number of edges in the constructed kNN graphs. Furthermore, we assume full participation during the federated learning and each client performs one epoch of local training (E = 1). In addition, we set α = 0.2 to perform the intra-client data augmentation in our study.Baselines. We consider four approaches to compare with our FEDNE. (1) LocalNE: each client trains the NE model using only its local data without any communication. Two baseline methods:(2) FedAvg+NE and (3) FedProx+NE are implemented by applying the widely used FL frameworks [34, 28] to NE model training. (4) GlobalNE: the NE model trained using aggregated global data, serving as the upper bound for performance comparison. Moreover, we want to emphasize that we do not include dSNE and F-dSNE for comparison. Although, at first glance, their titles might imply that they tackled a similar problem, their method is built upon the non-parametric t-SNE and heavily relies on the shareable reference dataset. Thus, they are not comparable with our framework. In addition, the results of the Shards setting can be found in the appendix, i.e., Table 9 .Improved preservation of true neighbors. Both FEDNE and the baseline approaches achieved relatively high continuity scores, indicating that the models can easily learn how to pull the data points that are similar in the high-dimensional space closer in the 2D space. However, the lower trustworthiness scores observed with the two baselines, FedAvg+NE and FedProx+NE, imply that without properly addressing incorrect neighborhood connections and separation of data points across different clients, the resulting embeddings may contain false neighbors. Consequently, points that are positioned closely in the 2D space might not be neighbors in the original high-dimensional space.Enhanced class discrimination in the embedding space. Our method has significantly improved the kNN classification accuracy compared to the baseline results. This improvement highlights the limitations of locally constructed k-NN graphs, which may incorrectly pull distant data pairs closer in the embedding space. In particular, if two data points from different classes are mistakenly treated as neighbors, class separation will be largely reduced even when inter-client repulsion is considered. Our intra-client data mixing method is specifically designed to relax this problem, and when combined with our surrogate loss function, it ensures an enhanced class separation. For instance, the embedding visualization of FedAvg+NE in Figure 3 under the Dir(0.1) setup shows a significant overlap between points from different labels. In contrast, FEDNE effectively separates the top groups of features in the visualization.Better preservation of global inter-cluster structures. Furthermore, we observe large improvements in preserving the clustering structures according to measures of steadiness and cohesiveness. Specifically, higher steadiness achieved by FEDNE indicates that the clusters identified in the projected space better align with the true clusters in the original high-dimensional space. The higher cohesiveness scores imply that the clusters in the high-dimensional space in general can be retained in the projected space, i.e., not splitting into multiple parts. Overall, even though FEDNE is not explicitly designed to improve feature clustering, it can produce relatively reliable inter-cluster structures.To verify the effect of our design choices, we conduct ablation studies on removing one of the proposed technical components from the FEDNE pipeline in Figure 1 . First, we remove the data augmentation by intra-client data mixing technique and only keep the surrogate repulsion model. We then remove the surrogate model and only augment the local data using the intra-client data mixing approach. The comparison results under the setup of Dir(0.1) with 20 clients are shown in Table 3 .With any of the components removed, our FEDNE can still outperform the baseline FedAvg+NE.However, we cannot simply conclude which component impacts the most on the final embedding results since the data characteristics and client partitions are very different across different setups. Further studies on our design choices are included in the appendix. Privacy Preserving. As introduced in section 4, FEDNE incorporates the proposed surrogate models into the traditional FEDAVG framework where the surrogate models only take the low-dimensional randomly sampled data as inputs. After training, each surrogate model contains much-compressed information about the corresponding client. Thus, we consider the privacy concerns to be alleviated as one cannot directly reconstruct the original high-dimensional client data. To further enhance privacy protection, our framework can be integrated with various privacy-preserving techniques at different stages. For example, Gaussian mechanisms (GM) can be applied to the parameters of the surrogate model before it is sent to the server.Scalability and Computational Complexity. To our knowledge, the field of dimensionality reduction (DR) focuses on relatively smaller-scale datasets, compared to the studies of classification problems. This is because computational complexity is never a trivial problem even for many outstanding DR techniques, particularly for non-linear methods such as Isomap and t-SNE which have non-convex cost functions [44] . In our experiments, we have included the most widely used benchmarks in the DR literature. Moreover, we have considered more participants and larger scales of data compared to prior work [37, 38] . While, unlike the other FL studies focused on classification, our experimentshave not yet included much larger datasets or with increased numbers of clients, we expect our approach to be applicable in real-world settings, for example, cross-silo settings with manageable amounts of clients. In terms of computation, as discussed in section 4, our approach requires only 35% additional GPU time compared to FEDAVG, and we expect such overhead to remain similar when going to larger datasets. When the client number increases, we may optionally drop a portion of surrogate models in local training. 
conclusion: 
 In this paper, we develop a federated neighbor embedding technique built upon the Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: We did not report the error bars or any statistical significance tests, but we did include the necessary statistical information in our paper.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: Yes, we have included the information in the main paper and also the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our work does not aim to address the societal impacts, and discussing societal impacts is not applicable to our paper.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We do not have any risks related to this.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA] Justification: Our paper does not release any new assets.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: Our work does not involve any crowdsourcing or research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: Our work does not need to involve any crowdsourcing or research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: The step size is used to control the resolution of grid sampling for training the surrogate models. In the main paper, the default step size is set to 0.3, and here, we experiment with using different step sizes. The experiments are conducted under the setting of Dirichlet(0.1) on the MNIST dataset with 20 clients. The results in Figure 4 demonstrate that the performance of FedNE is stable when the step size is below 1.0. However, when we increase the step size beyond 1.0, we observe a gradual decrease in performance, especially in terms of kNN classification accuracy and steadiness metrics. Despite this, FedNE still maintains better performance than FedAvg+NE.To construct the training set of the surrogate loss function in a more comprehensive and manageable way, each client employs a grid-sampling strategy in the 2D space. Here, we conduct experiments on MNIST and Fashion-MNIST datasets to compare the performance between using our grid-sampling strategy and using only local 2D embeddings as the training data. Table 6 and Table 7 show the comparison results for MNIST and Fashion-MNIST test data, respectively. We highlight the better results in both tables. The grid-sampling method outperforms the baseline approach (i.e., only using local embedding in surrogate function training), while the baseline still achieves better performance compared to FedAvg+NE. Overall, the results validate the effectiveness of employing the surrogate loss function during local training and also support our proposed grid-sampling strategy. In all experiments, the surrogate loss functions are retrained at every round. While frequent retraining introduces computational burdens for each client, using outdated surrogate loss functions can bias the optimization process of the repulsive loss. Thus, we conduct experiments on the MNIST dataset to showcase the impacts of the frequency of surrogate function updates. We conducted experiments with the other four setups, i.e., retraining the surrogate function every 5, 10, 15, or 20 more rounds. The default one is updating the surrogate function at every round. According to the line chart in Figure 5 , the performance decreased dramatically only when the surrogate loss function was updated more than every 10 rounds.In the main experiments, the surrogate loss function is integrated into local training after 30% of the total rounds have been finished. Here, we conduct further experiments on introducing the surrogate function at different time periods to confirm our decision, and the results are demonstrated in Figure 6 . First, the continuity is not affected too much and retains high scores under various setups. However, when the surrogate loss function is introduced too early, the trustworthiness and kNN accuracy drops, which may indicate that the inter-client repulsion is better to be involved after the intra-client forces have become relatively stable. Moreover, the performance of 55% also drops, particularly on kNN accuracy. This could be because the training process of FEDAVG has converged, making it too late to integrate additional constraints into the training procedure. We simulate the straggler problem by randomly sampling 10% of the clients involved in each round of communication under the setting of Dirichlet(0.1) on the MNIST dataset with 100 clients. While the performance under partial client participation is worse than under full client participation, the results in Table 8 show that FEDNE still performs notably better than the baseline method, FedAvg+NE.In addition to the table in the main paper, we also report the results of the Shards setting on MNIST, Fashion-MNIST, and CIFAR-10 datasets in Table 9 .We demonstrate the comprehensive visualization results from the centralized setting i.e., GlobalNE, our FEDNE and FedAvg+NE, and FedProx+NE on MNIST, Fashion-MNIST, RNA-Seq, and CIFAR-10 global test data. The five metrics are introduced in the main paper. judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Justification: Yes, our work was conducted with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).We use surrogate loss function and surrogate model interchangeably. 


Decision: The paper presents a new federated learning approach for dimension reduction using contrastive neighbor embedding (NE). The key idea is the introduction of a surrogate loss function that each client learns and shares, which compensates for the lack of inter-client repulsion essential for global alignment in the embedding space. Additionally, the paper proposes a data-mixing strategy to augment local data, addressing issues of invisible and false neighbors in local kNN graphs. Comprehensive experiments demonstrate that FEDNE effectively preserves neighborhood data structures and enhances alignment in the global embedding space compared to several baseline methods.

1.	FEDNE introduces a novel integration of FEDAVG with contrastive NE techniques, addressing the unique challenges of pairwise data relationships in federated learning environments without requiring data sharing.

2.	The intra-client data mixing strategy effectively enhances local data diversity, mitigating the limitations of biased local kNN graphs and ensuring better neighborhood representation.

3.	The paper provides a thorough evaluation of FEDNE using various datasets and metrics, showcasing its superior performance compared to baseline methods in preserving neighborhood structures and clustering.

Weaknesses:
The title should not include the “privacy-preserving” as it doesn’t show additional privacy guarantee besides federated learning itself.

1.	Communication complexity: The method appears to be computationally inefficient. There are no experiments conducted on large datasets, such as those in real-world medical or other privacy-critical domains, where computational complexity could be a significant issue.

2.	Additional privacy concerns: Sharing surrogate models introduces additional privacy risks, e.g., enabling reconstruction attacks or membership inference. While some recent work empirically shows that such private information is less leaked after the proposed method might be more vulnerable to privacy attacks without differential privacy. It lacks experiments and guarantees demonstrating the privacy preservation of the FedNE approach. 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.

Reviews: review: paper_summary: paper_summary: This paper addresses the challenge of distributed neural embedding (NE) with a focus on privacy protection. To achieve this, the authors extend the concept of federated learning (FL) to NE. However, NE tends to diverge because FL prevents clients from accessing each other's data, leading to inconsistent feature spaces across clients. To mitigate this issue, the authors employ surrogate loss models trained locally, which are then broadcast to all other clients to serve as an anchor. The experiments show promising performance compared to existing baselines.
strength_weakness: strength_weakness: 1. **Communication complexity**: If I understand correctly, every client in the proposed method must broadcast the surrogate models to all other clients. Although the surrogate models consist of only one hidden layer, this design results in a communication complexity of $\mathcal{O}(N^2)$. As the number of clients in the system increases, the additional communication costs will rise dramatically. This might be manageable in some cross-silo settings, where only a few clients participate.

2. **Straggler effect**: Following point (1), the proposed method requires communication among clients. 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.

3. **Additional privacy concerns**: Sharing surrogate models introduces additional privacy risks, e.g., enabling reconstruction attacks or membership inference. While some recent work empirically shows that such private information is less leaked after distillation (e.g., [1] and [2]), the proposed method might be more vulnerable to privacy attacks without differential privacy.

[1] Dong, Tian, Bo Zhao, and Lingjuan Lyu. "Privacy for free: How does dataset condensation help privacy?." International Conference on Machine Learning. PMLR, 2022.
[2] Wang, Hui-Po, et al. "Fedlap-dp: Federated learning by sharing differentially private loss approximations," Proceedings on Privacy Enhancing Technologies, 2024.
questions: questions: see weakness.
limitations: limitations: The authors have discussed some limitations. However, the authors are encouraged to discuss the use cases of the proposed method, such as cross-silo settings. Moreover, they are encouraged to discuss the additional privacy risks potentially introduced by their method.
paper_summary: paper_summary: The paper presents a new federated learning approach named FEDNE for dimension reduction using contrastive neighbor embedding (NE). The key idea is the introduction of a surrogate loss function that each client learns and shares, which compensates for the lack of inter-client repulsion essential for global alignment in the embedding space. Additionally, the paper proposes a data-mixing strategy to augment local data, addressing issues of invisible and false neighbors in local kNN graphs. Comprehensive experiments demonstrate that FEDNE effectively preserves neighborhood data structures and enhances alignment in the global embedding space compared to several baseline methods.
strength_weakness: strength_weakness: 1. The paper lacks investigation on the effect of choice of hyperparameter k.

2. The improvement of FEDNE is significant on some metrics (e.g., kNN) but is very limited in other metrics (e.g., conti.). The paper lacks a detailed exploration of why FEDNE produces different behavior for different metrics.

3. 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.
questions: questions: 1. How would the parameter k affect the performance of FEDNE? How to set k for different settings?

2. What are the major differences between the metrics? Why the improvement of FEDNE differ a lot across different metrics?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper "FEDNE: Surrogate-Assisted Federated Neighbor Embedding for Privacy-Preserving Dimensionality Reduction" presents a method for visualizing high-dimensional data while maintaining privacy without requiring any shareable reference data. 

Federated Neighbor Embedding (FEDNE): A framework combining federated averaging (FEDAVG) with contrastive neighbor embedding (NE) to create a joint NE model across multiple clients without compromising data privacy.

Surrogate Loss Function: An innovative loss function to enhance inter-client repulsion in the global embedding space, ensuring better separation of data points from different clients while preserving local data structures.

Data-Mixing Strategy: A technique to counter issues like invisible and false neighbors in local k-nearest neighbor (kNN) graphs by mixing data from various clients during training, thus improving the quality of the learned embeddings.
strength_weakness: strength_weakness: Privacy Concerns: While the approach is innovative, the paper does not sufficiently address privacy concerns. It lacks experiments and guarantees demonstrating the privacy preservation of the FedNE approach.

Computational Inefficiency: The method appears to be computationally inefficient. There are no experiments conducted on large datasets, such as those in real-world medical or other privacy-critical domains, where computational complexity could be a significant issue.

Inadequate Analysis of Related Work: The related works section is not thoroughly analyzed or discussed, missing critical comparisons and context necessary for a comprehensive understanding of the state of the art.

The study's applicability could be strengthened by extending beyond benchmark datasets to encompass real-world, privacy-sensitive datasets found in domains such as healthcare or finance. This expansion would provide a more robust demonstration of the method's practical relevance and effectiveness. 

Additionally, addressing pairwise issues associated with attraction terms is essential for improving the preservation of neighborhood structures and enhancing clustering quality. 

Furthermore, it is crucial to conduct thorough analyses aimed at optimizing the computational efficiency and scalability of the algorithms, ensuring their capability to handle large-scale datasets effectively. Moreover, the method currently lacks explicit consideration of privacy guarantees. And on elucidating how privacy concerns are addressed within the framework and formalizing privacy guarantees to assure users and stakeholders.
questions: questions: Privacy Guarantees: The paper lacks a thorough discussion on the privacy guarantees of the proposed method, especially against adversarial attackers.The experimental evaluation focuses solely on utility results, with no evaluation of data privacy. How is privacy preservation quantified and ensured? What is the acceptable level of privacy preservation? The paper should include theoretical arguments and experiments demonstrating actual privacy management. From a privacy perspective, it would be helpful to provide guidance on the limitations of this method, particularly regarding transparency and explainability (e.g., OECD AI principle 1.3). What measures are in place to address these concerns?

Experiments: No experiments are conducted on downstream tasks related to the problem, aside from analyzing structural properties? Moreover,  no experiments conducted on large datasets? Lastly, how do the authors plan to tackle the problem of heavy computation? The method appears computationally intensive, which could hinder its practicality.

Reconstruction from Gradients: According to Zhu and Han’s study [1], model gradients can be used in some scenarios to partially reconstruct client data. How does the proposed method address this issue?

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 via repulsion loss and additional augmented data points via interpolation for the attractive loss. Given this, how does the strategy address the significant computational burden it introduces, and is it feasible for real-world applications where computational efficiency is critical?

[1] Ligeng Zhu, Zhijian Liu, and Song Han. 2019. Deep leakage from gradients. Advances in neural information processing systems 32 (2019)
limitations: limitations: No societal impacts.
paper_summary: paper_summary: The paper introduces a novel approach to address the challenge of collaboratively visualizing high-dimensional data in a federated learning (FL) environment. The proposed method, FEDNE, integrates the FEDAVG framework with contrastive neighbor embedding (NE) techniques, aiming to preserve data privacy while ensuring effective data visualization. By employing a surrogate loss function and an intra-client data mixing strategy, FEDNE seeks to enhance the alignment and preservation of neighborhood structures in the global embedding space. The paper includes comprehensive experiments on both synthetic and real-world datasets, demonstrating the effectiveness of FEDNE in outperforming several baseline methods in terms of neighborhood data structure preservation and clustering.
strength_weakness: strength_weakness: 1.	While the authors mention that FEDNE introduces only 35% more GPU time compared to FEDAVG, the overall complexity and scalability in a more extensive, real-world setting are not fully addressed. The authors should further investigate how FEDNE scales with a significantly larger number of clients and more complex datasets or models.
2.	The paper proposes intra-client data mixing as a solution to the bias in local kNN graphs. However, this approach might not entirely mitigate the issue of incorrect neighbor connections, especially in highly imbalanced datasets. More detailed comparisons with alternative methods or further enhancements could provide a more robust solution.
3.	The focus is primarily on dimensionality reduction. The validation results are performed only on the vision classification tasks. Extending the discussions and analyses to include applications in other domains could be beneficial.
questions: questions: 1.	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?
2.	Non-IID data is a common challenge in federated learning. How does FEDNE handle extreme cases of non-IID data distribution? Have you considered any additional mechanisms to ensure robustness in such scenarios?
3.	How sensitive is FEDNE to the choice of hyperparameters, such as the step size for grid sampling, the number of neighbors in kNN, and the weight in intra-client data mixing? Have you performed any sensitivity analysis?
limitations: limitations: The authors have addressed the works limitations and social impacts.

Comments: title: Re: Official Comment by Reviewer y2ZN
Re: Official Comment by Reviewer 4ZYS
Kindly request your reconsideration
Response to Author's rebuttal
Paper discussion
Response to the rebuttal
comment: Dear Reviewer BJv7,

Thank you for your timely response and further clarification of your concerns. We sincerely apologize if we have misunderstood your original review and your response to the rebuttal (on 08/10/2024). If we read them correctly, you encouraged us to **discuss** the additional privacy risks potentially introduced by their method, and **propose** a robust comparison protocol for future work that accounts for various privacy considerations. We have tried our best to follow your suggestions in our rebuttal and additional responses. However, it seems that your latest comment demands us to further provide **experiments with DP** to address your concern. While we will be happy to do so, we, unfortunately, cannot complete it on the last day of the discussion phase. Still, we sincerely thank you for all your constructive feedback and suggestions.


Best,

Authors
Dear Reviewer mP1Q,

We appreciate your timely feedback. We understand your point about the privacy concern of the general Federated Learning (FL) framework. To our understanding, FL was originally conceived to allow model training without centralized data collection. Such a framework enables users to keep their data without sharing. Since then, a significant portion of the work in FL has aimed to improve the performance of FL in terms of its accuracy and convergence, especially under heterogeneous settings and communication constraints. Meanwhile, another branch of the FL research focuses on the privacy guarantee as you mentioned, as they found that decentralizing the data alone is not sufficient to protect privacy. We think both branches (and several others, e.g., system-level consideration of FL) are valuable --- *while one single paper may not be able to address both aspects*, together they aim for a synergy to make FL a robust, widely applicable, and privacy-preserving framework. 

As highlighted in a recent survey [1], FL still faces multiple unresolved challenges or deficiencies, including privacy protection, communication costs, systems heterogeneity, and deepening the research of FL in various fields. In Section 7, the survey paper said, “The development of FL is faced with multiple challenges, and no single strategy can comprehensively solve these bottlenecks in the practical application of FL technology.”

In our paper, we aim to extend FL's applicability (to a rarely studied ML problem) and address the associated performance challenges. We kindly want to reiterate that our focus is not to improve the general FL framework in terms of its privacy aspect but to explore a novel application domain of FL. 

We hope the above paragraphs clarify the position of our paper in the context of Federated Learning.


[1] Wen, Jie, et al. "A survey on federated learning: challenges and applications." International Journal of Machine Learning and Cybernetics 14.2 (2023): 513-535.

Best,

Authors
Dear Authors,

Thank you for your prompt response. I’ve carefully reviewed your feedback, and I’m glad to see that the authors agree on the privacy guarantee aspect. While I appreciate the explanation of the common practices in implementing differential privacy (DP), my primary concern remains that the paper might set an unfair baseline for future work if proper DP experiments are not included. Therefore, I will be maintaining my score.
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.
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.
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
Thank you for your response. However, my concerns about the privacy aspects of the proposed method remain unresolved. Federated learning, by design, aims to decentralize and collaboratively train models in a privacy-preserving manner, which inherently implies a need for privacy. This is precisely why one would choose this approach. However, recent research suggests that federated learning on its own may not be sufficient to guarantee privacy. Therefore, I will maintain my score.
Hi all,

Thanks again for your reviews!
If you haven't done so already, please respond to the rebuttals before the end of the author-reviewer discussion period. If you don't have any further questions for the authors then a simple "thank you for the rebuttal" would suffice.

All the best,
Area Chair
Thank you for your reply. I think the authors have addressed my concerns, especially with regard to the scalability and generality of the proposed method. Therefore, I decide to change the score to borderline accept.
Dear reviewer,

Thank you for reading our rebuttal and we apologize that our rebuttal has not fully addressed your concerns. We respond to your remaining concerns as follows.

We totally agree that our framework is more manageable in some cross-silo settings. Speaking of the communication cost on extremely large systems e.g., a million-scale system, this is still an unresolved problem in the existing literature. We have made one step further to relax the assumption of publicly available data and the next step in FL for NE could be reducing the communication cost.


Regarding the potential stale/old surrogate models due to network delay, we had a related experiment in Appendix B.2 where we studied whether reducing the frequency of surrogate model updates would impact the final performance (i.e., under the Shards setting with 20 clients on MNIST), even though in this experiment we assume that all clients may send out their outdated/stale surrogate models instead of only some of the clients. We can see that **the performance remains stable** and **the improvement is still notable compared to the baseline method, FedAvg+NE**, if the surrogate models are only outdated within a threshold of iterations i.e., 10 rounds of communication (Fig.4 in Appendix). While we know this experiment does not exactly match what you asked for, we hope it can still provide a better understanding of our method.


Lastly, we do agree that *privacy is a very important problem*. After serious consideration, there are several potential future directions on how to address and evaluate the privacy considerations in our framework. As demonstrated in Section 4 and the workflow in Figure 1, FedNE is built upon the traditional FedAvg framework. The potential privacy concerns mainly come from the FedAvg framework and the surrogate models that we proposed. 

To address the **privacy risks associated with FedAvg**, one potential solution is to implement a FedAvg version of DP-SGD [1]. In this approach, the Gaussian mechanism (GM) is applied to the global model updates, as described in line 10 of Algorithm 1 in [1], to achieve client-level differential privacy (DP). That is, each client’s entire dataset is protected against differential attacks from other clients.

To mitigate the **privacy concerns associated with** our proposed **surrogate models**, it is important to both anonymize client identities and address the potential risks inherent in sharing these models. To make the surrogate models differentially private, DP techniques can be integrated at different stages. One way is to incorporate DP before sharing the surrogate models. Even though the surrogate models are simple and only contain highly compressed information about the client data, the privacy risks can be further mitigated by applying the Gaussian mechanisms (GM) to the parameters of the surrogate model before it is sent to the server. Additionally, DP techniques can be incorporated during the training phase of the surrogate models through data synthesis. Specifically, to prepare the training targets, instead of using real data, each client can generate synthetic samples (e.g., via data distillation) to compute the repulsion loss values $l_q^{rep}$​ (as discussed in Lines 198-201), which are then used to train the surrogate models.

To ensure privacy guarantees, when GM is employed, a desired privacy budget can be set using Epsilon ($\epsilon$) and Delta ($\delta$), while balancing between privacy and utility. The moments accountant method can be utilized to track cumulative privacy loss over multiple iterations of FedNE. Furthermore, the privacy auditing algorithm [2] provides a valuable tool for estimating empirical privacy lower bounds within our framework. **The empirical Epsilon can be an indicator** (i.e., a lower Epsilon, a stronger privacy guarantee) **for comparing different methods**, e.g., FedAvg, FedNE, even FedNE integrated with DP, and other future works.

[1] Geyer, Robin C., Tassilo Klein, and Moin Nabi. "Differentially private federated learning: A client level perspective." arXiv preprint arXiv:1712.07557 (2017).

[2] Steinke, Thomas, Milad Nasr, and Matthew Jagielski. "Privacy auditing with one (1) training run." Advances in Neural Information Processing Systems 36 (2024).

Please kindly let us know if you have any further questions or concerns. We are more than happy to have a further discussion regarding it.

Best,

Authors
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.
Thanks for the authors' response. I'll keep my positive score.