SoK: Practical Aspects of Releasing Differentially Private Graphs

Computer Science > Cryptography and Security [Submitted on 19 Mar 2026] SoK: Practical Aspects of Releasing Differentially Private Graphs Nicholas D'Silva, Surya Nepal, Salil S. Kanhere Graph data is increasingly prevalent across domains, offering analytical value but raising significant privacy concerns. Edges may encode sensitive relationships, while node attributes may contain sensitive entity or personal data. Differential Privacy (DP) has gained traction for its strong guarantees, yet applying DP to graphs is challenging because of their complex relational structure, leading to trade-offs between privacy and utility. Existing methods vary in privacy definitions, utility goals, and contextual settings, complicating comparison. For practitioners, this is compounded by DP's interpretability issues, contributing to misleading protection claims. To address this, we propose a novel systemisation of existing methods tailored to practical considerations and adaptable to varying practitioner objectives. Our contributions include: (i) a comprehensive survey of differentially private graph release methods; (ii) identification of key vulnerabilities; and (iii) a practitioner-oriented, objective-based framework to guide the selection, interpretation, and sound evaluation of existing methods. We demonstrate the use of our systemisation through two exemplary scenarios in which we assume the role of a social network analyst, apply it, and conduct evaluations in accordance with our framework. Together, these two illustrative instantiations ultimately provide a unified benchmark for state-of-the-art methods in the social networks domain. Comments: 20 pages. Accepted to ACM ASIA CCS '26. DOI to be added once available Subjects: Cryptography and Security (cs.CR); Social and Information Networks (cs.SI) Cite as: arXiv:2603.18779 [cs.CR]   (or arXiv:2603.18779v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2603.18779 Focus to learn more Submission history From: Nicholas D'Silva [view email] [v1] Thu, 19 Mar 2026 11:30:59 UTC (616 KB) Access Paper: view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.SI References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)