Differential privacy is the gold standard when it comes to facilitating data analysis with strong privacy guarantees. The past decade has witnessed the design of numerous algorithms for differentially private graph analysis. These algorithms offer different privacy guarantees, and require different parameters and configurations for their usage. Some of these algorithms also suffer from poor scalability and are not equipped to handle large datasets. The combination of these factors makes determining the optimal algorithmic choice for a given scenario a non-trivial affair.
In this paper, we examine the trade-offs between the accuracy and performance of various classes of differentially private graph analysis algorithms by benchmarking them on real-world datasets. Our evaluation demonstrates that the optimal choice of algorithm is highly dependent on the properties of the underlying dataset as well as the performance and privacy requirements of a given user. This may explain why, despite a wealth of differentially private algorithms being available for graph analysis, their usage is not yet prevalent. We therefore urge the adoption of a standardized benchmarking platform, to facilitate the design and implementation of differentially private graph algorithms.
Huiyi Ning (University of Waterloo)
Sreeharsha Udayashankar (University of Waterloo)
Sara Qunaibi (University of Waterloo)
Karl Knopf (University of Waterloo)
Xi He (University of Waterloo)
More from the Same Authors
2021 : The Role of Adaptive Optimizers for Honest Private Hyperparameter Selection »
Shubhankar Mohapatra · Shubhankar Mohapatra · Sajin Sasy · Gautam Kamath · Xi He · Om Dipakbhai Thakkar
2021 : Unbiased Statistical Estimation and Valid Confidence Sets Under Differential Privacy »
Christian Covington · Xi He · James Honaker · Gautam Kamath