SIsomap: Secure Collaborative Manifold Learning with Reducing Communication Costs

Secure manifold learning on datasets distributed among multiple data owners can benefit or even spawn many applications. For example, multiple service providers can jointly fit low-dimensional embeddings of their users' network behavior data to improve the accuracy of anomaly detection while addressing their privacy concerns about the datasets. In this paper, we focus on a classic manifold learning technique, known as isometric mapping (Isomap), and propose SIsomap, the first secure, distributed manifold learning system. We construct SIsomap based on secret sharing techniques and introduce careful optimizations. In particular, we propose two communication-efficient secure building blocks that focus on top-k and all-pairs shortest paths computation, respectively, and reduce secure operations by leveraging the characteristics of Isomap. Experimental results on both synthetic and real-world datasets demonstrate that our secure top-k and all-pairs shortest paths protocols are respectively up to 13.6× and 1818.5× faster than the state-of-the-art methods, and SIsomap as a whole is 11.1× to 28.8× faster than the baseline solution.