Private Hierarchical Clustering and Efficient Approximation

Xianrui Meng, Dimitrios Papadopoulos, Alina Oprea, Nikos Triandopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationCCSW 2021 - Proceedings of the 2021 Cloud Computing Security Workshop, co-located with CCS 2021
Pages3-20
Number of pages18
ISBN (Electronic)9781450386531
DOIs
StatePublished - 15 Nov 2021
Event12th ACM Cloud Computing Security Workshop, CCSW 2021, co-located with CCS 2021 - Virtual, Online, Korea, Republic of
Duration: 15 Nov 2021 → …

Publication series

NameCCSW 2021 - Proceedings of the 2021 Cloud Computing Security Workshop, co-located with CCS 2021

Conference

Conference12th ACM Cloud Computing Security Workshop, CCSW 2021, co-located with CCS 2021
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period15/11/21 → …

Keywords

  • private hierarchical clustering
  • secure approximation
  • secure computation

Fingerprint

Dive into the research topics of 'Private Hierarchical Clustering and Efficient Approximation'. Together they form a unique fingerprint.

Cite this