Smooth Anonymity for Sparse Graphs
WWW '24: Companion Proceedings of the ACM on Web Conference May 13–17, 2024, Singapore, Singapore
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155161 |
| _version_ | 1824458000166813696 |
|---|---|
| author | Epasto, Alessandro Esfandiari, Hossein Mirrokni, Vahab Munoz Medina, Andres |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Epasto, Alessandro Esfandiari, Hossein Mirrokni, Vahab Munoz Medina, Andres |
| author_sort | Epasto, Alessandro |
| collection | MIT |
| description | WWW '24: Companion Proceedings of the ACM on Web Conference May 13–17, 2024, Singapore, Singapore |
| first_indexed | 2024-09-23T10:16:48Z |
| format | Article |
| id | mit-1721.1/155161 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:18:56Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1551612024-12-23T05:03:50Z Smooth Anonymity for Sparse Graphs Epasto, Alessandro Esfandiari, Hossein Mirrokni, Vahab Munoz Medina, Andres Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory WWW '24: Companion Proceedings of the ACM on Web Conference May 13–17, 2024, Singapore, Singapore In this work, we aim to manipulate and share an entire sparse dataset with a third party privately. As our first main result, we prove that any differentially private mechanism that maintains a reasonable similarity with the initial dataset is doomed to have a very weak privacy guarantee. Next, we consider a variation of k-anonymity, which we call smooth-k-anonymity, and design a simple large-scale algorithm that efficiently provides smooth-k-anonymity. We further perform an empirical evaluation and show that our algorithm improves the performance in downstream machine learning tasks on anonymized data. 2024-06-03T19:20:55Z 2024-06-03T19:20:55Z 2024-05-13 2024-06-01T07:47:38Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0172-6 https://hdl.handle.net/1721.1/155161 Epasto, Alessandro, Esfandiari, Hossein, Mirrokni, Vahab and Munoz Medina, Andres. 2024. "Smooth Anonymity for Sparse Graphs." PUBLISHER_POLICY en 10.1145/3589335.3651561 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Epasto, Alessandro Esfandiari, Hossein Mirrokni, Vahab Munoz Medina, Andres Smooth Anonymity for Sparse Graphs |
| title | Smooth Anonymity for Sparse Graphs |
| title_full | Smooth Anonymity for Sparse Graphs |
| title_fullStr | Smooth Anonymity for Sparse Graphs |
| title_full_unstemmed | Smooth Anonymity for Sparse Graphs |
| title_short | Smooth Anonymity for Sparse Graphs |
| title_sort | smooth anonymity for sparse graphs |
| url | https://hdl.handle.net/1721.1/155161 |
| work_keys_str_mv | AT epastoalessandro smoothanonymityforsparsegraphs AT esfandiarihossein smoothanonymityforsparsegraphs AT mirroknivahab smoothanonymityforsparsegraphs AT munozmedinaandres smoothanonymityforsparsegraphs |