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) $\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.
Cite
Text
Pinot et al. "Graph-Based Clustering Under Differential Privacy." Conference on Uncertainty in Artificial Intelligence, 2018.Markdown
[Pinot et al. "Graph-Based Clustering Under Differential Privacy." Conference on Uncertainty in Artificial Intelligence, 2018.](https://mlanthology.org/uai/2018/pinot2018uai-graph/)BibTeX
@inproceedings{pinot2018uai-graph,
title = {{Graph-Based Clustering Under Differential Privacy}},
author = {Pinot, Rafael and Morvan, Anne and Yger, Florian and Gouy-Pailler, Cédric and Atif, Jamal},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2018},
pages = {329-338},
url = {https://mlanthology.org/uai/2018/pinot2018uai-graph/}
}