1. Graph-based Clustering under Differential Privacy
- Author
-
Pinot, Rafael, Morvan, Anne, Yger, Florian, Gouy-Pailler, Cédric, and Atif, Jamal
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Learning - Abstract
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.
- Published
- 2018