FedNE: Surrogate-Assisted Federated Neighbor Embedding for Dimensionality Reduction

Ziwei Li, Xiaoqi Wang, Hong-You Chen, Han-Wei Shen, Wei-Lun Chao

Introduction

Neighbor Embedding (NE) techniques, such as t-SNE and UMAP, have become the gold standard for visualizing high-dimensional data by preserving local and global structures in a lower-dimensional space. However, as data privacy concerns grow, there is an increasing need to perform these visualizations within a Federated Learning (FL) framework, where data remains decentralized across multiple clients.

Implementing NE in a federated setting is notoriously difficult because these algorithms rely heavily on pairwise relationships—calculating "attraction" to pull similar points together and "repulsion" to push dissimilar points apart. This paper introduces FedNE, a novel framework that enables high-quality neighbor embedding across distributed participants without the need to exchange raw, sensitive data.

The Challenges of Federated Neighbor Embedding

Traditional NE algorithms struggle in siloed environments due to two primary hurdles:

  1. The Repulsion Gap: In a standard FL setup, a client can only calculate repulsion forces against its own local data. Because it lacks visibility into the data points held by other clients, it cannot effectively push away dissimilar global points. This often results in "inter-client overlap," where distinct clusters from different sources erroneously merge in the final visualization.
  2. The Neighborhood Bias: Because each client only sees a fraction of the global dataset, its local $k$-nearest neighbor ($k$NN) graph is frequently incomplete. A data point’s true neighbors might reside on a different server; without them, the model may force connections between points that should not be related, distorting the manifold.

The FedNE Framework

FedNE addresses these challenges by integrating the standard FedAvg pipeline with three innovative strategies designed to simulate global data relationships locally.

Surrogate Loss Functions

To bridge the repulsion gap, FedNE utilizes shared "surrogate models." Each client trains a lightweight Multi-Layer Perceptron (MLP) to approximate the repulsion loss that an arbitrary point would experience from that client's local data distribution. Instead of sharing raw data, clients exchange these surrogate models. During local training, a client uses the surrogates received from all other participants to "feel" the repulsive push of the global data, ensuring that clusters remain distinct across the entire network.

Intra-client Data Mixing

To mitigate neighborhood bias, FedNE employs a data-mixing strategy similar to "Mixup" augmentation. Clients generate synthetic data points by linearly interpolating between local points and their neighbors. This process helps "patch" the local manifold, making the embedding more robust to the absence of true neighbors stored on external servers.

Grid Sampling

Training surrogate models on high-dimensional input space is computationally expensive. To maintain efficiency, FedNE uses a grid-sampling strategy within the 2D embedding space. This allows the surrogate models to capture the density of the data effectively without requiring the complexity of the original high-dimensional features.

Experimental Evaluation

The researchers evaluated FedNE against four benchmark datasets: MNIST, Fashion-MNIST, CIFAR-10 (using ResNet-34 features), and a Mouse Retina scRNA-Seq biological dataset. To simulate realistic federated conditions, they utilized Dirichlet partitioning to create "non-IID" settings, where different clients hold significantly different data distributions.

Key Results

FedNE consistently outperformed standard federated baselines (such as FedAvg and FedProx applied to NE) across several metrics:

  • Quantitative Accuracy: On the MNIST dataset with high data imbalance, FedNE achieved a $k$NN classification accuracy of 0.72, a significant improvement over the 0.48 achieved by standard FedAvg+NE.
  • Structural Integrity: The framework showed higher scores in "trustworthiness" and "continuity," indicating that the 2D maps more faithfully represented the original high-dimensional relationships.
  • Visual Clarity: Qualitative analysis of the 2D plots revealed that FedNE successfully separated classes that other federated methods allowed to overlap, providing a much clearer global view of the data.

Insights and Privacy

The study highlights that while attraction forces create clusters, repulsion is the critical mechanism for aligning those clusters in a shared global space. By using surrogate models, FedNE achieves this alignment efficiently. Furthermore, these surrogates offer a layer of privacy; they act as lossy, compressed summaries of the data, making it significantly more difficult to reconstruct raw inputs compared to sharing gradients or anchor points.

Limitations and Future Work

While FedNE represents a major step forward, the authors note some areas for improvement:

  • Scalability: Currently, every client must run inference on surrogate models from every other client. In "cross-device" scenarios with thousands of participants, this could become a bottleneck. Future iterations may explore "Clustered FL" to reduce this overhead.
  • Formal Privacy Guarantees: While the surrogate models are more secure than raw data, the paper has not yet integrated formal Differential Privacy (DP) guarantees, which are essential for sensitive medical or financial applications.
  • Computational Costs: FedNE requires roughly 35% more GPU time per round than standard FedAvg. While the authors argue this is a reasonable trade-off for the gain in quality, optimizing the frequency of surrogate updates remains a goal for future research.

Summary updated

BibTeX
@inproceedings{li2024fedne,
  author = {Ziwei Li and Xiaoqi Wang and Hong-You Chen and Han-Wei Shen and Wei-Lun Chao},
  title = {{FedNE: Surrogate-Assisted Federated Neighbor Embedding for Dimensionality Reduction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=zBMKodNgKX},
}
Figure