Talk by Rafael Pinot (Université Paris-Dauphine & RIKEN AIP Human Computation Team)

Title: Graph-based Clustering under Differential Privacy

Abstract:
Weighted graph data is known to be a useful representation data type in many fields, such as bioinformatics or analysis of social, computer and information networks. Moreover, graph clustering is one of the key tools for understanding the underlying structure of such datasets. Nevertheless, it is critical that the data representation used in machine learning applications protects the private characteristics contained into it. Treating some datasets as non-private could lead to leaking information such as political, sexual, or religious preferences. As a standard for data privacy preservation, differential privacy has been designed. An algorithm is differentially private if, given two close databases, it produces statistically indistinguishable outputs. Since then, its definition has been extended to weighted graphs. After introducing the concepts of differential privacy on weighted graphs, we present the first differentially private clustering method for arbitrary-shaped node clusters in a graph. Our algorithm is theoretically well-motivated, and experiments support our theoretical findings.