SoK: Practical Aspects of Releasing Differentially Private Graphs

• URL: http://arxiv.org/abs/2603.18779v1
• Date: Thu, 19 Mar 2026 11:30:59 GMT
• Title: SoK: Practical Aspects of Releasing Differentially Private Graphs
• Abstract summary: Graph data is increasingly prevalent across domains, offering analytical value but raising privacy concerns.<n>Applying Differential Privacy to graphs is challenging because of their complex relational structure.<n>Existing methods vary in privacy definitions, utility goals, and contextual settings, complicating comparison.<n>We propose a novel systemisation of existing methods tailored to practical considerations and adaptable to varying practitioner objectives.
• Score: 20.29082580927169
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Subgraph Federated Learning via Spectral Methods [52.40322201034717]
  FedLap is a novel framework that captures inter-node dependencies while ensuring privacy and scalability.<n>We provide a formal analysis of the privacy of FedLap, demonstrating that it preserves privacy.
  arXiv  Detail & Related papers  (2025-10-29T16:22:32Z)
• SynBench: A Benchmark for Differentially Private Text Generation [35.908455649647784]
  Data-driven decision support in high-stakes domains like healthcare and finance faces significant barriers to data sharing.<n>Recent generative AI models, such as large language models, have shown impressive performance in open-domain tasks.<n>But their adoption in sensitive environments remains limited by unpredictable behaviors and insufficient privacy-preserving datasets.
  arXiv  Detail & Related papers  (2025-09-18T03:57:50Z)
• Differentially Private Relational Learning with Entity-level Privacy Guarantees [17.567309430451616]
  This work presents a principled framework for relational learning with formal entity-level DP guarantees.<n>We introduce an adaptive gradient clipping scheme that modulates clipping thresholds based on entity occurrence frequency.<n>These contributions lead to a tailored DP-SGD variant for relational data with provable privacy guarantees.
  arXiv  Detail & Related papers  (2025-06-10T02:03:43Z)
• Distributed, communication-efficient, and differentially private estimation of KL divergence [15.294136011320433]
  Key task in managing distributed, sensitive data is to measure the extent to which a distribution changes.<n>We describe novel algorithmic approaches for estimating the KL divergence of data across federated models of computation, under differential privacy.
  arXiv  Detail & Related papers  (2024-11-25T15:20:40Z)
• ATTAXONOMY: Unpacking Differential Privacy Guarantees Against Practical Adversaries [11.550822252074733]
  We offer a detailed taxonomy of attacks, showing the various dimensions of attacks and highlighting that many real-world settings have been understudied. We operationalize our taxonomy by using it to analyze a real-world case study, the Israeli Ministry of Health's recent release of a birth dataset using Differential Privacy.
  arXiv  Detail & Related papers  (2024-05-02T20:23:23Z)
• A Unified View of Differentially Private Deep Generative Modeling [60.72161965018005]
  Data with privacy concerns comes with stringent regulations that frequently prohibited data access and data sharing. Overcoming these obstacles is key for technological progress in many real-world application scenarios that involve privacy sensitive data. Differentially private (DP) data publishing provides a compelling solution, where only a sanitized form of the data is publicly released.
  arXiv  Detail & Related papers  (2023-09-27T14:38:16Z)
• Independent Distribution Regularization for Private Graph Embedding [55.24441467292359]
  Graph embeddings are susceptible to attribute inference attacks, which allow attackers to infer private node attributes from the learned graph embeddings. To address these concerns, privacy-preserving graph embedding methods have emerged. We propose a novel approach called Private Variational Graph AutoEncoders (PVGAE) with the aid of independent distribution penalty as a regularization term.
  arXiv  Detail & Related papers  (2023-08-16T13:32:43Z)
• Privacy-preserving Graph Analytics: Secure Generation and Federated Learning [72.90158604032194]
  We focus on the privacy-preserving analysis of graph data, which provides the crucial capacity to represent rich attributes and relationships. We discuss two directions, namely privacy-preserving graph generation and federated graph learning, which can jointly enable the collaboration among multiple parties each possessing private graph data.
  arXiv  Detail & Related papers  (2022-06-30T18:26:57Z)
• Semantics-Preserved Distortion for Personal Privacy Protection in Information Management [65.08939490413037]
  This paper suggests a linguistically-grounded approach to distort texts while maintaining semantic integrity. We present two distinct frameworks for semantic-preserving distortion: a generative approach and a substitutive approach. We also explore privacy protection in a specific medical information management scenario, showing our method effectively limits sensitive data memorization.
  arXiv  Detail & Related papers  (2022-01-04T04:01:05Z)
• Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach [54.32266555843765]
  This paper studies a model that protects the privacy of the individuals sensitive information while also allowing it to learn non-discriminatory predictors. The method relies on the notion of differential privacy and the use of Lagrangian duality to design neural networks that can accommodate fairness constraints.
  arXiv  Detail & Related papers  (2020-09-26T10:50:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.