Paper 2022/1727

Find Thy Neighbourhood: Privacy-Preserving Local Clustering

Pranav Shriram A, National Institute of Technology Tiruchirappalli
Nishat Koti, Indian Institute of Science Bangalore
Varsha Bhat Kukkala, Indian Institute of Science Bangalore
Arpita Patra, Indian Institute of Science Bangalore
Bhavish Raj Gopal, Indian Institute of Science Bangalore

Identifying a cluster around a seed node in a graph, termed local clustering, finds use in several applications, including fraud detection, targeted advertising, community detection, etc. However, performing local clustering is challenging when the graph is distributed among multiple data owners, which is further aggravated by the privacy concerns that arise in disclosing their view of the graph. This necessitates designing solutions for privacy-preserving local clustering and is addressed for the first time in the literature. We propose using the technique of secure multiparty computation (MPC) to achieve the same. Our local clustering algorithm is based on the heat kernel PageRank (HKPR) metric, which produces the best-known cluster quality. En route to our final solution, we have two important steps: (i) designing data-oblivious equivalent of the state-of-the-art algorithms for computing local clustering and HKPR values, and (ii) compiling the data-oblivious algorithms into its secure realisation via an MPC framework that supports operations over fixed-point arithmetic representation such as multiplication and division. Keeping efficiency in mind for large graphs, we choose the best-known honest-majority 3-party framework of SWIFT (Koti et al., USENIX'21) and enhance it with some of the necessary yet missing primitives, before using it for our purpose. We benchmark the performance of our secure protocols, and the reported run time showcases the practicality of the same. Further, we perform extensive experiments to evaluate the accuracy loss of our protocols. Compared to their cleartext counterparts, we observe that the results are comparable and thus showcase the practicality of the designed protocols.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. PoPETs 2023
privacy-preserving local clustering privacy-preserving heat kernel PageRank secure multiparty computation
Contact author(s)
pranavshriram99 @ gmail com
kotis @ iisc ac in
varshak @ iisc ac in
arpita @ iisc ac in
bhavishraj @ iisc ac in
2022-12-15: approved
2022-12-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Pranav Shriram A and Nishat Koti and Varsha Bhat Kukkala and Arpita Patra and Bhavish Raj Gopal},
      title = {Find Thy Neighbourhood: Privacy-Preserving Local Clustering},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1727},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.