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):
- 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.
- The Dual-Collaborator Protocol:
- Collaborator T receives encrypted data and adds random noise.
- Collaborator S (who holds the decryption key) decrypts this noised data to compute distances.
- 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.
- 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