Graph-based clustering under differential privacy
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) T released under weight differential privacy constraints from the graph. Then, the underlying nonconvex clustering partition is successfully recovered from cutting optimal cuts on T . As opposed to existing methods, our algorithm is theoretically well-motivated. Experiments support our theoretical findings.
Origin : Files produced by the author(s)