Graph-based Clustering under Differential Privacy
In this paper, we present the first differentially private clustering method for arbitrary-shaped node clusters in a graph. This algorithm takes as input only an approximate Minimum Spanning Tree (MST) $\mathcal{T}$ released under weight differential privacy constraints from the graph. Then, the underlying nonconvex clustering partition is successfully recovered from cutting optimal cuts on $\mathcal{T}$. As opposed to existing methods, our algorithm is theoretically well-motivated. Experiments support our theoretical findings.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering
Graph clustering under the framework of differential privacy, which aims to process graph-structured data while protecting individual privacy, has been receiving increasing attention. Despite significant achievements in …
Graph ClusteringOn the Price of Differential Privacy for Hierarchical Clustering
Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clustering involve sensitive user information, t…
ClusteringPrivacy PreservingDifferentially private subspace clustering
Subspace clustering is an unsupervised learning problem that aims at grouping data points into multiple ``clusters'' so that data points in a single cluster lie approximately on a low-dimensional linear subspace. It is o…
ClusteringMotion SegmentationPrivacy-Preserving Approach PBCN in Social Network With Differential Privacy
Currently, lots of real social relations in social networks force users to face the potential risk of privacy leakage. Consequently, data holders would like to disturbor anonymize their individual data before publishing …
ClusteringGraph ReconstructionPrivacy PreservingDifferentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency
We study spectral graph clustering under edge differential privacy. We propose a matrix shuffling mechanism that combines randomized edge flipping with a random permutation of the adjacency matrix. While edge flipping al…
Graph Clustering