Graph-based Clustering under Differential Privacy

Rafael Pinot, Anne Morvan, Florian Yger, Cedric Gouy-Pailler, Jamal Atif
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:328-337, 2018.

Abstract

In this paper, we present the first differentially private clustering method for arbitraryshaped 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-pinot18a, title = {Graph-based Clustering under Differential Privacy}, author = {Pinot, Rafael and Morvan, Anne and Yger, Florian and Gouy-Pailler, Cedric and Atif, Jamal}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {328--337}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/pinot18a/pinot18a.pdf}, url = {https://proceedings.mlr.press/r16/pinot18a.html}, abstract = {In this paper, we present the first differentially private clustering method for arbitraryshaped 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Graph-based Clustering under Differential Privacy %A Rafael Pinot %A Anne Morvan %A Florian Yger %A Cedric Gouy-Pailler %A Jamal Atif %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-pinot18a %I PMLR %P 328--337 %U https://proceedings.mlr.press/r16/pinot18a.html %V R16 %X In this paper, we present the first differentially private clustering method for arbitraryshaped 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. %Z Reissued by PMLR on 04 October 2026.
APA
Pinot, R., Morvan, A., Yger, F., Gouy-Pailler, C. & Atif, J.. (2018). Graph-based Clustering under Differential Privacy. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:328-337 Available from https://proceedings.mlr.press/r16/pinot18a.html. Reissued by PMLR on 04 October 2026.

Related Material