TY - GEN
T1 - Private Hierarchical Clustering and Efficient Approximation
AU - Meng, Xianrui
AU - Papadopoulos, Dimitrios
AU - Oprea, Alina
AU - Triandopoulos, Nikos
N1 - Publisher Copyright:
© 2021 ACM.
PY - 2021/11/15
Y1 - 2021/11/15
N2 - In collaborative learning, multiple parties contribute their datasets to jointly deduce global machine learning models for numerous predictive tasks. Despite its efficacy, this learning paradigm fails to encompass critical application domains that involve highly sensitive data, such as healthcare and security analytics, where privacy risks limit entities to individually train models using only their own datasets. In this work, we target privacy-preserving collaborative hierarchical clustering. We introduce a formal security definition that aims to achieve balance between utility and privacy and present a two-party protocol that provably satisfies it. We then extend our protocol with: (i) an optimized version for single-linkage clustering, and (ii) scalable approximation variants. We implement all our schemes and experimentally evaluate their performance and accuracy on synthetic and real datasets, obtaining very encouraging results. For example, end-to-end execution of our secure approximate protocol for over 1M 10-dimensional data samples requires 35sec of computation and achieves 97.09% accuracy.
AB - In collaborative learning, multiple parties contribute their datasets to jointly deduce global machine learning models for numerous predictive tasks. Despite its efficacy, this learning paradigm fails to encompass critical application domains that involve highly sensitive data, such as healthcare and security analytics, where privacy risks limit entities to individually train models using only their own datasets. In this work, we target privacy-preserving collaborative hierarchical clustering. We introduce a formal security definition that aims to achieve balance between utility and privacy and present a two-party protocol that provably satisfies it. We then extend our protocol with: (i) an optimized version for single-linkage clustering, and (ii) scalable approximation variants. We implement all our schemes and experimentally evaluate their performance and accuracy on synthetic and real datasets, obtaining very encouraging results. For example, end-to-end execution of our secure approximate protocol for over 1M 10-dimensional data samples requires 35sec of computation and achieves 97.09% accuracy.
KW - private hierarchical clustering
KW - secure approximation
KW - secure computation
UR - http://www.scopus.com/inward/record.url?scp=85121462948&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85121462948&partnerID=8YFLogxK
U2 - 10.1145/3474123.3486760
DO - 10.1145/3474123.3486760
M3 - Conference contribution
AN - SCOPUS:85121462948
T3 - CCSW 2021 - Proceedings of the 2021 Cloud Computing Security Workshop, co-located with CCS 2021
SP - 3
EP - 20
BT - CCSW 2021 - Proceedings of the 2021 Cloud Computing Security Workshop, co-located with CCS 2021
T2 - 12th ACM Cloud Computing Security Workshop, CCSW 2021, co-located with CCS 2021
Y2 - 15 November 2021
ER -