Graph-based clustering under differential privacy

Rafael Pinot; Anne Morvan; Florian Yger; Cédric Gouy-Pailler; Jamal Atif

Graph-based clustering under differential privacy

Rafael Pinot
, Anne Morvan
, Florian Yger
, Cédric Gouy-Pailler
, Jamal Atif

Université Paris Dauphine
LIST-DTSI-SLA CEA

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Citations (Scopus)

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.

Original language	English
Title of host publication	Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018
Editors	Amir Globerson, Amir Globerson, Ricardo Silva
Publisher	Association For Uncertainty in Artificial Intelligence (AUAI)
Pages	329-338
Number of pages	10
ISBN (Electronic)	9781510871601
Publication status	Published - 1 Jan 2018
Externally published	Yes
Event	34th Conference on Uncertainty in Artificial Intelligence, UAI 2018 - Monterey, United States Duration: 6 Aug 2018 → 10 Aug 2018

Publication series

Name	34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018
Volume	1

Conference

Conference	34th Conference on Uncertainty in Artificial Intelligence, UAI 2018
Country/Territory	United States
City	Monterey
Period	6/08/18 → 10/08/18

Cite this

Pinot, R., Morvan, A., Yger, F., Gouy-Pailler, C., & Atif, J. (2018). Graph-based clustering under differential privacy. In A. Globerson, A. Globerson, & R. Silva (Eds.), Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018 (pp. 329-338). (34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018; Vol. 1). Association For Uncertainty in Artificial Intelligence (AUAI).

Pinot, Rafael ; Morvan, Anne ; Yger, Florian et al. / Graph-based clustering under differential privacy. Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018. editor / Amir Globerson ; Amir Globerson ; Ricardo Silva. Association For Uncertainty in Artificial Intelligence (AUAI), 2018. pp. 329-338 (34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018).

@inproceedings{058d122a19864c28bf58b6cf07d001bb,

title = "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.",

author = "Rafael Pinot and Anne Morvan and Florian Yger and C{\'e}dric Gouy-Pailler and Jamal Atif",

note = "Publisher Copyright: {\textcopyright} 2018 by Association For Uncertainty in Artificial Intelligence (AUAI) All rights reserved.; 34th Conference on Uncertainty in Artificial Intelligence, UAI 2018 ; Conference date: 06-08-2018 Through 10-08-2018",

year = "2018",

month = jan,

day = "1",

language = "English",

series = "34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018",

publisher = "Association For Uncertainty in Artificial Intelligence (AUAI)",

pages = "329--338",

editor = "Amir Globerson and Amir Globerson and Ricardo Silva",

booktitle = "Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018",

}

Pinot, R, Morvan, A, Yger, F, Gouy-Pailler, C & Atif, J 2018, Graph-based clustering under differential privacy. in A Globerson, A Globerson & R Silva (eds), Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018. 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018, vol. 1, Association For Uncertainty in Artificial Intelligence (AUAI), pp. 329-338, 34th Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, United States, 6/08/18.

Graph-based clustering under differential privacy. / Pinot, Rafael; Morvan, Anne; Yger, Florian et al.
Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018. ed. / Amir Globerson; Amir Globerson; Ricardo Silva. Association For Uncertainty in Artificial Intelligence (AUAI), 2018. p. 329-338 (34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

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 - 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 -

Pinot R, Morvan A, Yger F, Gouy-Pailler C, Atif J. Graph-based clustering under differential privacy. In Globerson A, Globerson A, Silva R, editors, Uncertainty in Artificial Intelligence - Proceedings of the 34th Conference, UAI 2018. Association For Uncertainty in Artificial Intelligence (AUAI). 2018. p. 329-338. (34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018).

Graph-based clustering under differential privacy

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this