TY - GEN
T1 - Graph-based clustering under differential privacy
AU - Pinot, Rafael
AU - Morvan, Anne
AU - Yger, Florian
AU - Gouy-Pailler, Cédric
AU - Atif, Jamal
N1 - Publisher Copyright:
© 2018 by Association For Uncertainty in Artificial Intelligence (AUAI) All rights reserved.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85059402723
M3 - Conference contribution
AN - SCOPUS:85059402723
T3 - 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018
SP - 329
EP - 338
BT - Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018
A2 - Globerson, Amir
A2 - Globerson, Amir
A2 - Silva, Ricardo
PB - Association For Uncertainty in Artificial Intelligence (AUAI)
T2 - 34th Conference on Uncertainty in Artificial Intelligence, UAI 2018
Y2 - 6 August 2018 through 10 August 2018
ER -