SMAP: A Joint Dimensionality Reduction Scheme for Secure Multi-Party Visualization

Jiazhi Xia, Tianxiang Chen, Lei Zhang, Wei Chen, Yang Chen, Xiaolong Zhang, Cong Xie, Tobias Schreck

TL;DR

SMAP introduces a secure, multi-party framework for t-SNE, allowing different organizations to visualize their combined datasets in a shared space without ever revealing their raw data to one another. By leveraging additive homomorphic encryption and a dual-collaborator architecture, the system produces a joint embedding that is mathematically identical to standard t-SNE while maintaining strict privacy guarantees.

What Problem Does This Paper Address?

In fields like healthcare or finance, data often exists in "isolated islands." Multiple hospitals might want to see how their patient populations compare to a global average, or a data buyer might want to verify the quality of a vendor's dataset before purchasing.

The standard tool for this—dimensionality reduction (like t-SNE)—usually requires gathering all raw data into a single central server. This is a non-starter for privacy-sensitive industries or under regulations like GDPR. Even if you anonymize the data, the resulting "distance matrix" (the record of how similar every point is to every other point) can often be used to reverse-engineer the original sensitive attributes. SMAP tackles the challenge of generating a high-quality global visualization while keeping both the raw data and the distance matrix hidden from all participants.

Methods

The authors reformulate the standard t-SNE algorithm into a Secure Multi-Party Computation (SMPC) protocol. The architecture relies on two "semi-honest," non-colluding collaborators (referred to as S and T):

  1. Additive Homomorphic Encryption (AHE): Participants encrypt their data before sending it. AHE allows the collaborators to perform mathematical operations (like addition) on the encrypted values without ever decrypting them.
  2. The Dual-Collaborator Protocol:
    • Collaborator T receives encrypted data and adds random noise.
  3. Collaborator S (who holds the decryption key) decrypts this noised data to compute distances.
  4. Because of a clever mathematical "fraction reduction" in the t-SNE probability formula, the noise added by T cancels out during the final computation. This ensures that S only sees noised distances, and T only sees encrypted data.
  5. Privacy-Aware Visualization: The system, SMAP (Secure Multi-pArty Projection), offers two levels of visualization. For lower privacy needs, it provides standard scatterplots. For stricter requirements, it uses density maps (heatmaps) to show global distributions without revealing individual data points.

Datasets

The researchers evaluated SMAP using three distinct scenarios:

  • Clothing 1M: A dataset of 1 million fashion images across 14 classes, used here to simulate a "data market" where a buyer evaluates a seller's data quality.
  • MNIST: The classic handwritten digit dataset, used to test how the system handles "non-IID" data (where different parties have very different distributions of data).
  • Real-world Health Data: A sensitive dataset containing physical examination and blood test records from three different community hospitals.

Key Insights and Ideas

  • Exact Accuracy: Unlike many privacy-preserving methods that add "differential privacy" noise (which degrades the final result), SMAP’s protocol is designed so that the noise cancels out. The resulting visualization is mathematically identical to a standard, non-secure t-SNE.
  • The Distance Matrix is the Weak Link: A major insight is that the distance matrix itself is a privacy risk. By ensuring no single party (not even the collaborators) ever sees the full, accurate distance matrix, the system closes a common leak in distributed machine learning.
  • Visual Abstraction as Security: The paper argues that visualization design is part of the security stack. By switching from scatterplots to density maps, the system prevents "point-level" relationship leaks, which is crucial when users are also data providers who might recognize their own outliers.

Key Results

  • Security: The protocol successfully prevents any participant or collaborator from obtaining or inferring the original data of others.
  • Utility: In the hospital case study, users were able to identify that while their datasets covered similar clinical areas, the density distributions differed significantly (e.g., one hospital had a much younger patient demographic), leading to better collaborative insights.
  • Performance: While secure computation is notoriously slow, the authors show that on a high-performance cluster (300 CPUs), the most intensive distance calculations can be reduced from 32 hours to roughly 29 seconds.

Limitations and Future Work

The primary limitation is computational overhead. On standard hardware, the encryption and decryption steps are extremely time-consuming for large datasets. The current implementation is also specifically tailored for t-SNE; while the authors mention that PCA could be supported, other popular methods like UMAP or ISOMAP present harder challenges because they rely on "k-nearest neighbor" graphs that are difficult to compute securely.

Future work aims to optimize the encryption speed and explore "secure collaborative visual analysis," where users can not only see the data but also interactively vote on or recommend interesting data points in a crowdsourced, privacy-preserving manner.

Summary updated

Abstract

Nowadays, as data becomes increasingly complex and distributed, data analyses often involve several related datasets that are stored on different servers and probably owned by different stakeholders. While there is an emerging need to provide these stakeholders with a full picture of their data under a global context, conventional visual analytical methods, such as dimensionality reduction, could expose data privacy when multi-party datasets are fused into a single site to build point-level relationships. In this paper, we reformulate the conventional t-SNE method from the single-site mode into a secure distributed infrastructure. We present a secure multi-party scheme for joint t-SNE computation, which can minimize the risk of data leakage. Aggregated visualization can be optionally employed to hide disclosure of point-level relationships. We build a prototype system based on our method, SMAP, to support the organization, computation, and exploration of secure joint embedding. We demonstrate the effectiveness of our approach with three case studies, one of which is based on the deployment of our system in real-world applications.
BibTeX
@inproceedings{xia2020smap,
  author = {Jiazhi Xia and Tianxiang Chen and Lei Zhang and Wei Chen and Yang Chen and Xiaolong Zhang and Cong Xie and Tobias Schreck},
  title = {{SMAP: A Joint Dimensionality Reduction Scheme for Secure Multi-Party Visualization}},
  booktitle = {IEEE VAST@IEEE VIS},
  year = {2020},
  url = {https://openreview.net/forum?id=0fVzQjKmPLz},
}

Loading related content...

Figure