Smooth Anonymity for Sparse Graphs

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.