A Privacy-Preserving Computation Framework for Multisource Label Propagation Services

Multisource Private Label Propagation (MPLP) is designed for different organizations to collaboratively predict labels of unlabeled nodes through iterative propagation and label updates without revealing sensitive information. Aside from the privacy of the origin data, in some statistical prediction services, it is only needed to learn about the statistical results and concrete prediction results for the abnormal nodes. To do it, we first design a basic MPLP scheme, <small>PriLP</small>, to meet the requirements of the privacy of origin data and the concrete prediction of normal nodes. However, our basic achievement of <small>PriLP</small> relies heavily on Additive Homomorphic Encryption (AHE) due to the sparse graph representation in label propagation. To diminish reliance on AHE, our optimization facilitates data encryption in a more compact representation, resulting in encryption times that scale linearly with the number of graph nodes. Our experiments show <small>PriLP</small> closely matches plain-label propagation within <inline-formula><tex-math notation="LaTeX">$\leq 0.7\%$</tex-math></inline-formula> difference in accuracy, and the optimizations lead to up to <inline-formula><tex-math notation="LaTeX">$22.63\times$</tex-math></inline-formula> faster execution and <inline-formula><tex-math notation="LaTeX">$1.83\times$</tex-math></inline-formula> less communication than the basic implement.