Privacy-preserving eigenvector computation with applications in spectral clustering

Abstract

Eigenvectors give many useful information about the data. One of the applications that benefits from eigenvectors is spectral clustering in which the nodes of a graph that can be a representation of a data set, will be clustered based on the spectrum (eigenvalues) of the Laplacian matrix. However, in scenarios where the data is distributed among multiple data owners, privacy of the data is an important concept. In the current paper, we propose a privacy-preserving protocol to compute eigenvectors of the distributed data using homomorphic encryption and Jacobi method with the aim of being employed in spectral clustering. We show that the computation overhead of each data owner in our iterative protocol is O(nf2N), where n is the number of iterations, N is the total number of data owners and f is the total number of data records, which means that increasing the number of data owners leads to decreasing the computation overhead of each single data owner. Moreover, the total communication complexity of the whole protocol is O(nf2). In comparison with previous known spectral clustering schemes PrivateGraph (Sharma in IEEE Trans Knowl Data Eng 31(5):981–995, 2018) and PrivGED (Wang et al. in IEEE Trans Knowl Data Eng, 2022), on one hand our proposed scheme only uses one computing server and on the other hand there is no single data user entity to get the final result and instead, all of the data owners get the result. The time consumption of our proposed protocol on “Parkinson Disease”, “Brain Networks”, “Cervical Cancer” and “Lung Cancer” data sets is 22.24 min, 18.38 min, 19.45 min and 3.84 min, respectively. © The Author(s), under exclusive licence to Bharati Vidyapeeth's Institute of Computer Applications and Management 2024.